format: text

text:
# 1

Equations for Stochastic Macromolecular Mechanics of

Single Proteins: Equilibrium Fluctuations, Transient

Kinetics and Nonequilibrium Steady-State

Hong Qian

Department of Applied Mathematics

University of Washington, Seattle, WA 98195, U.S.A.

(206)-543-2584 (Phone), (206)-685-1440 (Fax)

qian@amath.washington.edu

ABSTRACT

> A modeling framework for the internal conformational dynamics and external mechanical movement of single biological macromolecules in aqueous solution at constant temperature is developed. Both the internal dynamics and external movement are stochastic; the former is represented by a master equation for a set of discrete states, and the latter is described by a continuous Smoluchowski equation. Combining these two equations into one, a comprehensive theory for the Brownian dynamics and statistical thermodynamics of single macromolecules arises. This approach is shown to have wide applications. It is applied to protein-ligand dissociation under external force, unfolding of polyglobular proteins under extension, movement along linear tracks of motor proteins against load, and enzyme catalysis by single fluctuating proteins. As a generalization of the classic polymer theory, the dynamic equation is capable of characterizing a single macromolecule in aqueous solution, in probabilistic terms, (1) its thermodynamic equilibrium with fluctuations, (2) transient relaxation kinetics, and most importantly and novel (3) nonequilibrium steady-state with heat dissipation. A reversibility condition which guarantees an equilibrium solution and its thermodynamic stability is established, an H-theorem like inequality for irreversibility is obtained, and a rule for thermodynamic consistency in chemically pumped nonequilibrium steady-state is given.
> Keywords: free energy, nano-biochemistry, Smoluchowski equation, stochastic process, thermal fluctuation

I. Introduction

Progress in optics, electronics, and computer science has now made it possible to study biological macromolecules in aqueous solution at constant temperature by observing experimentally and measuring quantitatively the behavior of single biological macromolecules. These studies have been providing and will continue to yield important information on the behavior and properties of individual biomolecules and to reveal molecular interactions in and the mechanisms of biological processes. The impact which single-molecule studies will have on molecular biology may be gauged by comparison with the pioneering studies on single channel proteins in membranes, which have revolutionized physiology.1 The highly quantitative data obtained in these novel measurements, with piconewton and nanometer precision on the forces and movements of single macromolecules, complement those from traditional kinetic studies and structural determinations at the atomic level.

The novel experimental approach requires a consistent theoretical framework for quantitatively understanding, interpreting, and integrating laboratory data.2-6 The objective is to develop a unifying molecular theory, with thermodynamic consistency, which is capable of integrating the three classes of quantitative measurements on macromolecules: macroscopic (spectroscopic kinetics), mesoscopic (single molecules), and microscopic (atomic structures). In this paper, we show how the spectroscopically defined kinetics, expressed in terms of discrete conformational states, is integrated with the mechanics of a macromolecule. The philosophy behind this approach, Stochastic Macromolecular Mechanics, is that we realize the impracticality of representing the entire conformational space of a macromolecule with a high-dimensional energy function. Hence we still rely on a discrete-state Markov model with experimentally defined “states” and kinetic parameters. However, we introduce a continuous energy landscape when there are relevant, mechanical data on the single molecule. Therefore the stochastic macromolecular mechanics is a mix of the discrete-state Markov kinetics with Brownian dynamics based on available and relevant experimental measurements. It is a mesoscopic theory with a single set of equations. The theoretical approach helps researchers to identify the relevant (random) variables and key parameters in a macromolecular system or process, and provides them with the necessary equations.

The discrete-state master equation approach has been long accepted as the natural mathematical description for biochemical kinetics of individual molecules.7,8 With more detailed information on molecular structures and energetics, the Smoluchowski’s continuous description of overdamped Brownian dynamics has found numerous applications in condensed matter physics, polymer chemistry, and biochemistry of macromolecules9,10. Hänggi et al.11 have reviewed the related work with Kramers’ approach to chemical rate theory in which the assumption on overdamping is not warranted. However, for biological macromolecules in aqueous solution, and with the time scale of biological interests, this assumption is generally acceptable. In dealing with a single protein molecule, the discrete approach is appropriate for spectroscopic studies3 while the continuous approach is necessary for mechanical measurements. By combining these two descriptions, the stochastic macromolecular mechanics treats the internal conformational dynamics of proteins as well as its external mechanics. In particular, both internal and external forces are explicitly considered. On the mathematical side, such a combination leads to coupled stochastic processes,12 giving rise to three different classes of problems: reversible stationary processes (in a physicist’s term, thermal equilibrium with fluctuations), nonstationary processes (kinetic transient), and irreversible stationary processes (nonequilibrium steady-state with dissipation). The last class of processes is novel13-15 and necessary for modeling motor protein (e.g. kinesin and myosin) movement and energetics,16-26 as well as other “active macromolecules”.

The differential equations in stochastic macromolecular mechanics are Fokker-Planck-master type (linear diffusion-convection equations with variable coefficients) based on conservation of probability.8 This type of equations is different from the well-studied nonlinear reaction-diffusion equations 27,28 with distinctly different mathematical properties.15,21

We would like to point out that there is already a large literature on both Smoluchowski equation and master equations. The novelty of our formalism is that (i) in order to combine the two types of equation into one, a condition analogous to the “thermodynamic box” in the elementary chemical kinetics needs to be introduced. This relation, called potential condition,29 yields a constraint between the energy functions in the Smoluchowski equation and the transition rates in the master equation. This constraint guarantees the time-reversibility of the stationary solution to the stochastic macromolecular mechanics (SM3), similar to that of fluctuation-dissipation relation required in modeling equilibrium Brownian motion. More importantly, however, is that (ii) for single macromolecules like motor proteins, this condition is violated due to the presence of chemical pumping (i.e., ATP hydrolysis).21,22 This latter class of models based on Smoluchowski-master equation is relatively new. Its relation to the phenomena of stochastic resonance has been revealed only recently.30,31 And finally, (iii) the stationary solution to the SM3 with chemical pumping defines a nonequilibrium steady-state the thermodynamics of which can be rigorously investigated. By thermodynamics, we mean the entropy production, heat dissipation, nonlinear irreversible force-flux relationship, and the law of thermodynamics. It is this third aspect of the SM3, we suggest, makes the Smoluchowski approach more powerful and fundamental than that is generally aware. SM3 as a statistical thermodynamic theory for macromolecules in isothermal aqueous solution, both passive and active, will have wide applications, and deserves further investigations in the light of single-molecule experiments.

A second objective of this paper is introducing the physical chemists who are interested in the Smoluchowski’s approach to the unique and exciting opportunity in the current biophysics of nonequilibrium macromolecules on the level of single molecules. In that sense, SM3 is a generalization of the classic polymer theory9 into the nonlinear (Sec. II) and nonequilibrium (Sec. III) regime.

The paper is organized with increasing complexity as follows. In Sec. II we show how external force is introduced into the kinetics of protein-ligand dissociation. We point out that mechanical measurements on single molecular complex depend critically on the experimental conditions - the stiffness of the force probe and the rate of its retraction. In Sec. III, polymers consisting of nonlinear subunits are introduced and we show how the internal kinetics is coupled to the external mechanics and movement. A Boltzmann’s H-theorem like inequality is obtained; and the importance of nonlinear spring in serial leading to complex mechanical behavior is discussed. Sec. IV introduces the ATP hydrolysis into the model. Detailed balance, nonequilibrium steady-state, and thermodynamic consistency are discussed. Sec. V. shows how SM3 can be applied to the well-studied problem of fluctuating enzyme and yields new insights. In particular, we show how the classic concepts such as thermodynamic linkage and induced fit are consequence of the detailed balance, and can be generalized and quantified. A summary is given in Sec. VI.

II. Macromolecular Mechanics of Protein-Ligand Dissociation

In this section, we discuss the dissociation of a single protein-ligand complex under an external force introduced by an experimenter.32-34 As in any mechanics measurement, one first is interested in the position of the ligand with respect to the center of the mass of the protein. The next mechnical quantity is what is the forces acting on the ligand. This leads to a Newtonian equation in which one neglects the acceleration term

$$\beta \frac{dx}{dt}=F_{int}(x)+F_{ext}(x,t)+f(t).$$
(1)
The four terms are $`(i)`$ frictional force with frictional coefficient $`\beta `$, $`(ii)`$ intermolecular force between the ligand and the protein, with potential energy function $`U_{int}(x)`$: $`F_{int}(x)`$=$`dU_{int}(x)/dx`$, $`(iii)`$ the external force, and $`(iv)`$ the stationary, pure random force due to collisions between the ligand and the solvent molecules: $`f(t)=0`$. Because of the presence of the random force $`f(t)`$, the movement $`x(t)`$ is stochastic, e.g., it is a Brownian motion. Mathematically equivalent, the Smoluchowski’s description of overdamped Brownian dynamics is based on a partial differential equation of parabolic type:29,35

$$\beta \frac{P(x,t)}{t}=k_BT\frac{^2P(x,t)}{x^2}\frac{}{x}\left[(F_{int}(x)+F_{ext}(x,t))P(x,t)\right]$$
(2)
where $`P(x,t)`$ is now the probability density of the ligand being at $`x`$ at time $`t`$. $`k_B`$ is the Boltzmann constant, and $`T`$ is temperature which characterizes the magnitude of the random force $`f(t)`$: $`f(t)f(t^{})=2k_BT\delta (tt^{})`$.

The above Eq. (1) and (2) lay the mathematical basis for all models, but the choices for $`U_{int}(x)`$ and $`F_{ext}`$ set the difference between different models. In the work of Shapiro and Qian,36-38 $`U_{int}=V_0[(x_0/x)^{12}2(x_0/x)^6]`$ with a smooth repulsive force, and $`F_{ext}=k(xd(t))`$ where $`k`$ is the stiffness of the force probe exerting the external force, and $`d(t)=vt`$ is the position of the piezoelectric motor which drives the force probe, $`v`$ is the retracting velocity. In the work of Evans and Ritchie,39,40 $`U_{int}=V_0(x_0/x)^n`$ $`(x>x_0)`$ with an abrupt repulsion at $`x_0`$, and $`F_{ext}=F(t)`$ is independent of $`x`$. These differences give qualitatively similar but qualitative different results. Hence they can be quantitatively tested against experimental date.

Fig. 1 shows the results of simulations on the force-displacement curve for a protein-ligand complex with a simple 6-12 Lennard-Jones potential, measured using an elastic force probe. It is important to note that all the differences between the curves are due to the difference in the stiffness of the force probe ($`k`$), the rate of retraction ($`v`$), and the temperature ($`k_BT`$) at which the measurements are carried out. Therefore, this calculation demonstrates that the “raw” experimental data can only be understood, in general, in terms of a molecular model. It is important to realize the significance of the measurement aparatus on the experimental data.

III. Macromolecular Mechanics of Polyglobular Protein Unfolding

In the previous section on protein-ligand dissociation, we have completely neglected the conformational change within the protein itself. The protein was treated as a rigid body exerting a force on the ligand. A more realistic model must consider the possibility of the protein’s internal conformational change due to the external force, acting via the ligand. In this section, we study the unfolding of a polyglobular protein under extensional force. This problem naturally involves the internal dynamics of the macromolecules.

To be concrete, let’s consider the recent experimental work on giant muscle protein titin.41-43 Titin is a protein with many globular domains (subunits) in serial. The subunits unfold under an external force pulling the entire molecule. The folded state of each subunit is rigid, and the unfolded state of each subunit can be regarded as a coiled polymer spring. Hence the conformational state of the entire protein, to a first order approximation, can be characterized by $`n`$: the number of unfolded subunits within the molecule. Let’s assume the total number of subunits are $`N`$, and let $`x`$ be the total extension of the titin molecule (along the axis of external force), then a realistic characterization of a titin molecule is by two dynamic variables $`(x,n)`$, $`(x0,0nN)`$.

The equation of motion for $`x`$ is again

$$\beta \frac{dx}{dt}=\frac{dU_{int}(x,n)}{dx}+F_{ext}+f(t)$$
(3)
in which $`n`$ is itself a random (discrete-state Markov) process. Hence the above equation is coupled to a master equation

$$\frac{P(n,t)}{t}=(Nn+1)\lambda _u(x,n1)P(n1,t)+(n+1)\lambda _f(x,n+1)P(x,n+1,t)$$

$$[n\lambda _f(x,n)+(Nn)\lambda _u(x,n)]P(n,t)$$
(4)
where $`P(n,t)`$ is the probability for $`n`$ at time $`t`$. $`\lambda _f`$ and $`\lambda _u`$ are folding and unfolding rate constants of individual subunits. They are functions of the force acting on the subunit, which in turn is determined by the total extension of the molecule ($`x`$) and the number of unfolded domains in the chain ($`n`$).

A comprehensive description of both the internal dynamics and external movement can be obtained by combining Eq. (3) and (4). We therefore have

$`{\displaystyle \frac{P(x,n,t)}{t}}`$ $`=`$ $`\left({\displaystyle \frac{k_BT}{\beta }}\right){\displaystyle \frac{^2P(x,n,t)}{x^2}}+{\displaystyle \frac{1}{\beta }}{\displaystyle \frac{}{x}}\left[\left({\displaystyle \frac{dU_{int}(x,n)}{dx}}+F_{ext}\right)P(x,n,t)\right]`$ (5)
$`+`$ $`(Nn+1)\lambda _u(x,n1)P(x,n1,t)`$
$`+`$ $`(n+1)\lambda _f(x,n+1)P(x,n+1,t)`$
$``$ $`[n\lambda _f(x,n)+(Nn)\lambda _u(x,n)]P(x,n,t)`$
where $`P(x,n,t)`$ is the joint probability distribution of the titin molecule having internally $`n`$ unfolded domains and external extension $`x`$.

As in the previous section, particular models will provide specific $`\lambda _f(x,n)`$, $`\lambda _u(x,n)`$, and $`U_{int}(x,n)`$. These functions are not totally independent, however. Microscopic reversibility dictates that

$$\frac{\lambda _u(x,n)}{\lambda _f(x,n+1)}=\frac{n+1}{Nn}\mathrm{exp}\left[\frac{U_{int}(x,n+1)U_{int}(x,n)}{k_BT}\right].$$
(6)
This condition guarantees that the stationary solution to Eq. (5) is a thermodynamic equilibrium with time reversibility. Furthermore, this reversibility condition (also known as potential condition and detailed balance) also guarantees the thermodynamic stability of the equilibrium state in terms of a generalized free energy function. As we shall see below, without (6), the stationary solution in general represents a nonequilibrium steady-state with dissipation.

With the reversibility condition and in the absence of external force $`F_{ext}`$, it is easy to verify that the stationary solution to Eq. (5) is

$$P^{}(x,n)=Z^1e^{U(x,n)/k_BT}$$
(7)
where

$$Z=\underset{n=0}{\overset{N}{}}_0^{\mathrm{}}e^{U(x,n)/k_BT}.$$

The time-dependent solutions to (5) are dynamic models for nonstationary transient kinetics of macromolecules.

We now show that the equilibrium solution $`P^{}(x,n)`$ is asymptotically stable. By stability, we mean a molecule approaches to its equilibrium state irrespective of its initial state. We introduce a free energy functional:

$`\mathrm{\Psi }[P(x,n,t)]`$ $`=`$ $`{\displaystyle \underset{n=0}{\overset{N}{}}}{\displaystyle _0^{\mathrm{}}}\left(U(x,n)P(x,n,t)+k_BTP(x,n,t)\mathrm{ln}P(x,n,t)\right)𝑑x`$
$`=`$ $`k_BT\mathrm{ln}Z+k_BT{\displaystyle \underset{n=0}{\overset{N}{}}}{\displaystyle _0^{\mathrm{}}}P(x,n,t)\mathrm{ln}\left({\displaystyle \frac{P(x,n,t)}{P^{}(x,n)}}\right)𝑑x`$
in which the second term (known as relative entropy44,45) is always nonnegative and equal to zero if and only if $`P(x,n,t)=P^{}(x,n)`$.29 Based on Eq. (5) the time derivative of $`\mathrm{\Psi }`$ is

$$\dot{\mathrm{\Psi }}[P(x,n,t)]=\underset{n=0}{\overset{N}{}}_0^{\mathrm{}}\left[\beta ^1J^2(x,t)P^1+k_BT\left(J_n^+J_n^{}\right)\mathrm{ln}\left(\frac{J_n^+}{J_n^{}}\right)\right]𝑑x0$$
(8)
where

$$J(x,t)=k_BT\frac{P(x,n,t)}{x}\frac{dU(x,n)}{dx}P(x,n,t)$$

and

$$J_n^+(t)=(n+1)\lambda _f(x,n+1)P(x,n+1,t),J_n^{}(t)=(Nn)\lambda _u(x,n)P(x,n,t).$$

The integrand in Eq. (8) is always positive. Hence $`\mathrm{\Psi }`$ is a Lyapunov functional for the time-dependent solution of Eq. (5), which guarantees $`P^{}`$ to be asymptotically stable. Furthermore, because of the reversibility condition, the differential equation in (5) is symmetric and all its eigenvalues are real, indicating relaxations in such systems can not oscillate.

The physical interpretation of the above result is important: It relates the equation of SM3 to the second law of thermodynamics. The $`\mathrm{\Psi }`$-function is the generalization of the equilibrium free energy of a closed, isothermal molecular system. $`\mathrm{\Psi }`$ decreases monotonically to its minimum $`k_BT\mathrm{ln}Z`$, the Gibbs free energy, when the system reaches its equilibrium. It is intriguing to note that the dynamics in Eq. (5) is not governed by the gradient of the free energy. Nevertheless, one should see the analogy between Eq. (8) and the H-theorem of Boltzmann in his approach to irreversibility in an isolated system (microcanonical ensemble).

To analyze the stochastic dynamics of a complex macromolecule under extensional force, it is important first to have an essential understanding of its nonlinear mechanical property. A polyglobular protein model is a generalization of the classic “bead-and-spring” to nonlinear spring.9 The protein subunits all have two energy minima while a simple Hookean spring has only one. This leads to fundamentally different behavior of the macromolecule. To illustrate this, let’s apply the elementary Ohm’s law for nonlinear springs in serial: the force on the springs are the same while the displacement is additive. For simplicity, assume each subunit has a potential function (and force) given in Fig. 2. This energy function has been used in recent work on globular protein folding kinetics. Then Fig. 3 gives a quantitative force-extension curve expected from a polyglobular protein with three subunits. As one can see, the most striking feature is the possibility of multiple branches of the curve with a given force. This is due to the combinatorics shown in Table I.

IV. Macromolecular Mechanics of Motor Protein Movement

With the presence of the reversibility (potential) condition, the previous model represents a “passive” complex molecule. Without the external force, such molecules relax, multi-exponentially, to a thermodynamic equilibrium. They are biochemically interesting, but they are not “alive”. One could argue that one of the fundamental properties of a living organism is the ability to convert energy among different forms (solar to electrical, electrical to chemical, chemical to mechanical, etc.). We now show how stochastic macromolecular mechanics can be used to develop models for chemomechanical energy transduction16,17 in single motor proteins.46 In the absence of an external force, a motor protein is undergoing nonequilibrium steady-state with ATP hydrolysis and generating heat – representing a rudimentary form of energy metabolism.

The key for developing a theory for motor protein is to consider that while biochemical studies of a protein in test tubes probe a set of discrete conformational states of the molecule, the mechanical studies of a protein measure positions and forces. Internally, a motor protein has many different conformational states within a hydrolysis cycle, and a reaction scheme usually can be deduced from various kinetic studies. While the protein is going through its conformational cycles, its center of mass moves along its designated linear track (e.g., kinesin on a microtubule, myosin on an actin filament, and polymerase on DNA) which usually has a periodic structure. The movement is stochastic; the interaction between the motor and the track (the force field) are usually different for different internal states of the molecule.

These basic facts lead to the following equation

$`{\displaystyle \frac{P(x,n,t)}{t}}`$ $`=`$ $`\left({\displaystyle \frac{k_BT}{\beta }}\right){\displaystyle \frac{^2P(x,n,t)}{x^2}}+{\displaystyle \frac{1}{\beta }}{\displaystyle \frac{}{x}}\left[\left({\displaystyle \frac{dU_{int}(x,n)}{dx}}+F_{ext}\right)P(x,n,t)\right]`$ (9)
$`+`$ $`{\displaystyle \underset{k=1}{\overset{N}{}}}\left[\lambda _{kn}(x)P(x,k,t)\lambda _{nk}(x)P(x,n,t)\right],`$
where $`P(x,n,t)`$ denote the joint probability of a motor protein with internal state $`n`$ and external position $`x`$. $`U_{int}(x,n)`$ is the interaction energy between the protein in state $`n`$ and the track. $`\lambda _\mathrm{}m(x)`$ is the transition rate constant from internal state $`\mathrm{}`$ to state $`m`$ when the protein is located at $`x`$. Some of the $`\lambda `$’s are pseudo-first order rate constants which contain the concentrations \[ATP\], \[ADP\], and \[Pi\].

When the ratio \[ADP\]\[Pi\]/\[ATP\] = $`K_{eq}`$, the equilibrium constant for the hydrolysis reaction, the $`U(x,n)`$ and $`\lambda _\mathrm{}m^{}(x)`$ are again constrained by the reversibility (the superscript  is to indicate that the pseudo-first order rate constants are calculated in terms of the equilibrium concentrations):

$$\frac{\lambda _\mathrm{}m^{}(x)}{\lambda _m\mathrm{}^{}(x)}=\mathrm{exp}\left(\frac{U_{int}(x,m)U_{int}(x,\mathrm{})}{k_BT}\right).$$
(10)
This relation was called “thermodynamic-consistency” by T. L. Hill47 in his landmark contribution to the Huxley’s theory of muscle contraction48. It has to be satisfied by every motor protein models. It is clear, however, that the ATP, ADP, and Pi can be kept at arbitrary values. Hence in general the stationary solution of the Eq. (9) will be a nonequilibrium steady-state. Sustaining the concentrations is a form of “pumping” which keeps the system at nonequilibrium steady-state31 with positive entropy production and heat generation.14,15 Such a molecular device is also known as isothermal ratchet.18,19,22 See Ref. 21 and 15 for reviews of the vast literature. If the concentrations are not actively sustained, then they will change slowly (since there is only a single molecule at work hydrolyzing ATP) and eventually reach a thermal equilibrium state in which (10) is satisfied.

As in the previous sections, a practical model requires specific choices for the parameters $`U`$ and $`\lambda `$. In the past several years, a large amount of work have appeared on modeling translational motor proteins such as myosin and kinesin15,18,19,21,25,21 and rotational motor proteins such as ATP synthase.49,50 A thermodynamically valid model for a motor protein has to satisfy Eq. (10) when \[ADP\]\[Pi\]/\[ATP\] = $`K_{eq}`$, but in general without a potential function. This rule has not been enforced in some of the models.

Simpler but phenomenological models based on discrete-state kinetics have also been developed for motor protein kinetics and energetics.20,23-25 It is important to point out that these models are completely in accord with the present continuous theory. However, drastic simplifications are used in order to make the models more accessible to experimental data. Fig. 4 shows the conceptual relationship between these two classes of models. Therefore, the discrete model should not be viewed as an alternative to the SM3, rather it is a simplification which can be further scrutinized in terms of the general theory of SM3. The stistical thermodynamics associated with the continuous approach, however, can be developed in parallel for the discrete models.25

V. Macromolecular Mechanics of Fluctuating Enzyme

Equilibrium conformational fluctuation of proteins play an important role in enzyme kinetics. The theory of fluctuating enzyme51 can be developed naturally in terms of the above equations for stochastic macromolecular mechanics. Let’s consider a single enzyme, with its internal conformation characterized by $`x`$, and $`N`$ number of substrate molecules. The enzyme catalyzes a reversible isomerization reaction between two forms of the substrate (reactant and product), with rate constants $`\lambda _+(x)`$ and $`\lambda _{}(x)`$.

The equation for the catalytic reaction coupled with the enzyme conformational fluctuation, according to stochastic macromolecular mechanics, is

$$\frac{P(n,x,t)}{t}=[n\lambda _++(Nn)\lambda _{}]P(n,x,t)+(n+1)\lambda _+P(n+1,x,t)$$

$$+(Nn+1)\lambda _{}P(n1,x,t)+D\frac{^2P(n,x,t)}{x^2}+k\frac{}{x}(xP(n,x,t)),$$
(11)
$$(0nN)$$

where $`P(n,x,t)`$ is the probability of at time $`t`$ having $`n`$ number of reactant molecules and the enzyme internal conformation being at $`x`$. $`D`$ and $`k`$ characterize the protein conformational fluctuation. $`x`$ is perpendicular to the isomerization reaction coordinate as first proposed by Agmon and Hopfield,10 in contrast to the other models which address random energy landscape along the reaction coordinate.52 Eq. (11), which is essentially the same equation for the modeling of polyglobular protein unfolding (Eq. 5), unifies and generalizes most of the important works on fluctuating enzymes.

Along this approach, most work in the past have addressed the non-stationary, time-dependent solution to (11). These studies are motivated by macroscopic experiments which are initiated ($`t=0`$) with all the substrate in only the reactant form. If $`\lambda _{}(x)=0`$ and $`N=1`$, Eq. (11) is reduced to that of Agmon and Hopfield.10 If $`\lambda _{}(x)=0`$ but $`N`$ is large, then one can introduce a continuous variable $`\xi =n/N`$, known as the survival probability, and Eq. (11) can be approximated as (see Appendix I for more discussion)

$$\frac{P(\xi ,x,t)}{t}=\lambda _+(x)\frac{}{\xi }(\xi P(\xi ,x,t))+D\frac{^2P(\xi ,x,t)}{x^2}+k\frac{}{x}(xP(\xi ,x,t)).$$
(12)
At $`t=0`$, Prob$`\{\xi =1\}=1`$.

The moments of $`\xi `$, $`\xi ^m(x,t)=_0^1\xi ^mP(\xi ,x,t)𝑑\xi `$, can be easily obtained from Eq. (12):

$$\frac{\xi ^m}{t}=m\lambda _+(x)\xi ^m+D\frac{^2\xi ^m}{x^2}+k\frac{}{x}\left(x\xi ^m\right).$$
(13)
Note Eq. (11) with $`N=1`$ and Eq. (13) for $`\xi `$ are idential. For $`\lambda _+(x)=\alpha x^2+\beta x+\gamma `$, Eq. (13) can be exactly solved by various methods if one realizes that its solution has a Gaussian form53-55 (also see Appendix II). From Eq. (13) one immediately sees that high-order moments $`\xi ^m`$ is related to $`\xi `$ by $`\lambda _+(x)m\lambda _+(x)`$.56

Different choices for $`\lambda _+(x)`$ lead to quantitatively different models for fluctuating enzymes in the literature. $`\lambda _+(x)e^{\alpha x}`$ represents a fluctuating activation energy barrier;10 $`\lambda _+(x)=\alpha (x+\overline{x})`$ $`(>0)`$ representing a fluctuating cofactor concentration;57 $`\lambda _+(x)`$ = $`\alpha x^2`$ representing a fluctuating geometric bottleneck.53

We now consider the reversible reaction (with $`\lambda _{}(x)0`$) which has not been discussed previously. This class of models is more appropriate for recent measurements in single-molecule enzymology.3 Again we assume $`N`$ being large. Hence we have

$$\frac{P(\xi ,x,t)}{t}=\frac{}{\xi }\left(D_\xi (\xi ,x)\frac{P(\xi ,x,t)}{\xi }\right)+\frac{}{\xi }\left(V_\xi (\xi ,x)P(\xi ,x,t)\right)$$

$$+D\frac{^2P(\xi ,x,t)}{x^2}+\frac{}{x}(V_x(x,\xi )P(\xi ,x,t))$$
(14)
where $`D_\xi (\xi ,x)=[\xi \lambda _++(1\xi )\lambda _{}]/2N`$ and $`V_\xi =\xi \lambda _+(1\xi )\lambda _{}`$. Eq. (14) is a 2D diffusion-convection equation similar to a continuous model we proposed for motor protein movement.21 One important consequence of this formulation and the reversibility condition is realizing that conformational fluctuations of the enzyme, $`V_x`$ can not be independent of the substrate. This constitutes the essential idea of induced fit58-60 and thermodynamic linkage!61,57 For equilibrium fluctuation, again reversibility (i.e., potential condition) dictates:21

$$\frac{V_x(x,\xi )}{\xi }=D\frac{}{x}\left(\frac{V_\xi (\xi ,x)}{D_\xi (\xi ,x)}\right)=\frac{4ND(\lambda _{}\lambda _+^{}\lambda _+\lambda _{}^{})\xi (1\xi )}{[\xi \lambda _++(1\xi )\lambda _{}]^2}$$
(15)
where $`\lambda ^{}=d\lambda (x)/dx`$. Therefore,

$$V_x(x,\xi )=\frac{\xi }{(\lambda _+\lambda _{})^2}+\frac{\lambda _++\lambda _{}}{(\lambda _+\lambda _{})^3}\mathrm{ln}[\lambda _+\xi +\lambda _{}(1\xi )]$$

$$+\frac{\lambda _+\lambda _{}}{(\lambda _+\lambda _{})^3[\lambda _+\xi +\lambda _{}(1\xi )]}+V_0(x)$$
(16)
where $`V_0(x)`$ is an arbitrary function of $`x`$ but it is independent of $`\xi `$. As can be seen, if $`\lambda _{}<<\lambda _+`$, then there is no requirement for $`\xi `$-dependent $`V_x`$.

VI. Conclusions

Biological macromolecules are the cornerstone of molecular biology. Mathematical modeling of biomolecular processes requires a comprehensive and thermodynamically consistent theoretical basis upon which quantitative analyses can be carried out and rigorously compared with experiments. In this paper, a formal theory, we call stochastic macromolecular mechanics, is presented. The theory offers a dynamic equation for describing the internal kinetics as well as external motion of macromolecules in aqueous solution at constant temperature. Systematically applying this theory to various biomolecular processes will bring molecular biophysics closer to the standard of theoretical chemistry and physics. At present time, Smoluchowski is well-known for its importance in calculating the microscopic fluctuations of an isothermal equilibrium system.8,9,29,35 It is less known that it can also be a cogent model for a macromolecules under chemical pumping.18,19,30,21 What has not been appreciated is that this mesoscopic model also yields equilibrium and nonequilibrium thermodynamics for the macromolecule. Therefore, it deserves the same status as that of Newton’s for mechanics, Navier-Stokes’ for fluid dynamics, Maxwell’s for electrodynamics, Schrödinger’s for quantum mechanics, and Boltzmann’s for statistical mechanics of isolated systems.

Acknowledgement

I like to dedicate this paper to Professor Joel Keizer. Officially I have not worked with him. However, he had been a mentor to me in the past 10 years because our common interests in nonequilibrium statistical mechanics and biophysics, and because of Terrell Hill. One can easily find his influence on my work presented here. He will be sorely missed.

Appendix I

Let’s use the well-known linear death process62 as an example to illustrate the continuous approximation for the discrete model:

$$\frac{dP_n(t)}{dt}=n\lambda P_n(t)+(n+1)\lambda P_{n+1}(t)$$
(17)
where $`P_n(t)`$ is the probability of survival population being $`n`$ at time $`t`$. The solution to this equation is well known62

$$P_n(t)=\frac{N!}{n!(Nn)!}e^{n\lambda t}\left(1e^{\lambda t}\right)^{Nn}$$

where $`N`$ is the total population at time $`t=0`$. It is easy to show that the moments

$`n(t)`$ $`=`$ $`Ne^{\lambda t},`$
$`{\displaystyle \frac{n^2(t)}{n(t)^2}}`$ $`=`$ $`1+{\displaystyle \frac{1}{N}}\left(e^{\lambda t}1\right),`$ (18)
$`{\displaystyle \frac{n^3(t)}{n(t)^3}}`$ $`=`$ $`1+{\displaystyle \frac{3(N1)}{N^2}}\left(e^{\lambda t}1\right)+{\displaystyle \frac{1}{N^2}}\left(e^{2\lambda t}1\right).`$
We now consider the continuous counterpart of (17) with $`\xi =n/N`$:

$$\frac{P(\xi ,t)}{t}=\frac{}{\xi }\left(\xi P(\xi ,t)\right)$$

which has solution

$$P(\xi ,t)=e^{\lambda t}\delta \left(\xi e^{\lambda t}1\right)$$

for initial condition $`P(\xi ,0)=\delta (\xi 1)`$. The moments for $`\xi `$ are

$$\xi ^k(t)=e^{k\lambda t}.$$
(19)
Comparing (18) and (19), we note that the continuous approximation is valid when the $`N`$ is large and $`t`$ is small. More precisely, $`\mathrm{ln}N\lambda t`$.

Appendix II

Let’s consider the following equation

$$\frac{u}{t}=D\frac{^2u}{x^2}+k\frac{}{x}(xu)(\alpha x^2+\beta x+\gamma )u$$

In Gaussian form53 which is equivalent to path integral calculation54 $`u(x,t)`$ = $`[2\pi \sigma (t)]^{1/2}`$ $`\mathrm{exp}\left\{\nu (t)[x\mu (t)]^2/2\sigma ^2(t)\right\}`$, and equate coefficients of like order terms in $`x`$ we have

$`d\nu /dt`$ $`=`$ $`\alpha [\mu ^2(t)+\sigma ^2(t)]\beta \mu (t)\gamma `$
$`d\mu /dt`$ $`=`$ $`[k+2\alpha \sigma ^2(t)]\mu (t)\beta \sigma ^2(t)`$
$`d\sigma ^2/dt`$ $`=`$ $`2D2k\sigma ^2(t)2\alpha \sigma ^4(t)`$
with initial condition $`\sigma ^2(0)=D/k`$, $`\mu (0)=0`$, and $`\nu (0)=0`$. We thus have

$`\sigma ^2(t)`$ $`=`$ $`2D{\displaystyle \frac{(\omega +k)+(\omega k)e^{2\omega t}}{(\omega +k)^2(\omega k)^2e^{2\omega t}}}`$
$`\mu (t)`$ $`=`$ $`\left({\displaystyle \frac{2\beta D}{\omega }}\right){\displaystyle \frac{1+e^{\omega t}}{(\omega +k)(\omega k)e^{\omega t}}}`$
$`\nu (t)`$ $`=`$ $`\left({\displaystyle \frac{\beta ^2D}{\omega ^2}}{\displaystyle \frac{\omega k}{2}}\gamma \right)t+{\displaystyle \frac{4\beta ^2D}{\omega (\omega k)}}\left[{\displaystyle \frac{1}{(\omega +k)(\omega k)e^{\omega t}}}{\displaystyle \frac{1}{2k}}\right]`$
$`{\displaystyle \frac{1}{2}}\mathrm{ln}\left[{\displaystyle \frac{(\omega +k)^2(\omega k)^2e^{2\omega t}}{4\omega k}}\right]`$
where $`\omega ^2=k^2+4D\alpha `$.

References

1 B. Sakmann and E. Neher, Single-channel recording, 2nd Ed. (Plenum Press, New York, 1995)

2 X. S. Xie, and J. K. Trautman, Ann. Rev. Phys. Chem. 49, 441 (1998).

3 X. S. Xie and H. P. Lu, J. Biol. Chem. 274, 15967 (1999).

4 H. Qian and E. L. Elson, Biophys. J. 76, 1598 (1999).

5 H. Qian, Biophys. J. 79 137 (2000).

6 H. Qian, J. Math. Biol. 41, 331 (2000).

7 D. A. McQuarrie, J. Appl. Prob. 4, 413 (1967).

8 J. Keizer, Statistical Thermodynamics of Nonequilibrium Processes (Springer-Verlag, New York, 1987).

9 M. Doi and S. F. Edwards, The Theory of Polymer Dynamics (Clarendon, Oxford, 1986).

10 N. Agmon, and J. J. Hopfield, J. Chem. Phys. 78, 6947 (1983).

11 P. Hänggi, P. Talkner, and M. Borkovec, Rev. Mod. Phys. 62, 251 (1990).

12 M. Qian, and B. Zhang, Acta Math. Appl. Sinica 1, 168 (1984).

13 M.-P. Qian, M. Qian, and G. L. Gong, Contemp. Math. 118, 255 (1991).

14 H. Qian, Proc. R. Soc. Lond. A. , in the press (2001).

15 H. Qian, J. Math. Chem. 27, 37 (2000).

16 T. L. Hill, Free Energy Transduction in Biology (Academic Press, New York, 1977).

17 T. L. Hill, Free Energy Transduction and Biochemical Cycle Kinetics (Springer-Verlag, New York, 1989).

18 C.S. Peskin, G.B. Ermentrout, and G.F. Oster, in Cell Mechanics and Cellular Engineering, edited by V.C. Mow, F., Guilak, R. Tran-Son-Tay, and R. M. Hochmuth (Springer-Verlag, New York, 1994), pp. 479-489.

19 R.D. Astumian, Science 276, 917 (1997).

20 H. Qian, Biophys. Chem. 67, 263 (1997).

21 F. Jülicher, A., Ajdari, and J. Prost, Rev. Mod. Phys. 69, 1269 (1997).

22 H. Qian, Phys. Rev. Lett. 81, 3063 (1998).

23 M. E. Fisher and A. B. Kolomeisky, Proc. Natl. Acad. Sci. USA 96, 6597 (1999).

24 M. E. Fisher and A. B. Kolomeisky, Physica A 274, 241 (1999).

25 H. Qian, Biophys. Chem. 83, 35 (2000).

26 D. Keller and C. Bustamante, Biophys. J. 78, 541 (2000).

27 J. D. Murray, Mathematical Biology, 2nd, corrected Ed. (Springer-Verlag, New York, 1993).

28 H. Qian, and J.D. Murray, App. Math. Lett. 14, 405 (2001).

29 H. Risken, The Fokker-Planck Equation: Methods of Solution and Applications (Springer-Verlag, New York, 1984).

30 L. Gammaitoni, P. Hänggi, P. Jung, and F. Marchesoni, Rev. Mod. Phys. 70, 223 (1998).

31 H. Qian and M. Qian, Phys. Rev. Lett. 84, 2271 (2000).

32 E. Florin, V. T. Moy, and H. E. Gaub, Science 264, 415 (1994).

33 V. T. Moy, E. Florin, and H. E. Gaub, Science 266, 257 (1994).

34 A. Chilkoti, T. Boland, R. D. Ratner, and P. S. Stayton, Biophys. J. 69, 2125 (1995).

35 N. G. van Kampen, Stochastic Processes in Physics and Chemistry, Revised and enlarged Ed. (North-Holland, Amsterdam, 1997).

36 B. E. Shapiro and H. Qian, Biophys. Chem. 67, 211 (1997).

37 B. E. Shapiro and H. Qian, J. Theoret. Biol. 194, 551 (1998).

38 H. Qian and B. E. Shapiro, Prot: Struct. Funct. Genet. 37, 576-581 (1999).

39 E. Evans and K. Richie, Biophys. J. 72, 1541 (1997).

40 E. Evans and K. Richie, Biophys. J. 76, 2439 (1999).

41 M. S. Z. Kellermayer, S. B. Smith, H. L. Granzier, and C. Bustamante, Science 276, 1112 (1997).

42 M. Rief, M. Gautel, F. Oesterhelt, J. M. Fernandez, and H. E. Gaub, Science 276, 1109 (1997).

43 L. Tskhovrebova, J. Trinick, J. A. Sleep, and R. M. Simmons, Nature 387, 308 (1997).

44 M. C. Mackey, Rev. Mod. Phys. 61, 981 (1989).

45 H. Qian, Phys. Rev. E. in the press.

46 J. Howard, Ann. Rev. Physiol. 58, 703 (1996).

47 T. L. Hill, Progr. Biophys. Mol. Biol. 28, 267 (1974).

48 A. F. Huxley, Progr. Biophys. 7, 255 (1957).

49 T. Elston, H.Y. Wang, and G. Oster, Nature 391, 510 (1998)

50 H.Y. Wang, and G. Oster, Nature 396, 279 (1998).

51 C. Blomberg, J. Mol. Liquids 42, 1 (1989).

52 R. Zwanzig, Proc. Natl. Acad. Sci. USA, 85, 2029 (1988).

53 R. Zwanzig, J. Chem. Phys. 97, 3587 (1992).

54 J. Wang and P.G. Wolynes, Chem. Phys. Lett. 212, 427 (1993).

55 J. Wang and P.G. Wolynes, Chem. Phys. 180, 141 (1994).

56 J. Wang and P.G. Wolynes, Phys. Rev. Lett. 74, 4317 (1995).

57 E. Di Cera, J. Chem. Phys. 95, 5082 (1991).

58 D. E. Koshland, Proc. Natl. Acad. Sci. USA 44, 98 (1958).

59 H. Qian and J. J. Hopfield, J. Chem. Phys. 105, 9292 (1996).

60 H. Qian, J. Chem. Phys. 109, 10015 (1998).

61 J. Wyman, J. Mol. Biol. 11, 631 (1965).

62 H. M. Taylor and S. Karlin,An Introduction to Stochastic Modeling, 3rd Ed. (Academic Press, San Diego, 1998).

63 R. Zwanzig, Proc. Natl. Acad. Sci. U.S.A. 92, 9801 (1995).

64 R. Doyle, K.T. Simon, H. Qian, and D. Baker, Prot: Struct. Funct. Genet. 29, 282 (1997).

65 H. Qian and S.I. Chan, J. Mol. Biol. 286, 607 (1999).

Figure Captions

Figure 1. The force-displacement curve for a simple Lennard-Jones bond calculated based on the solution of stochastic dynamics Eq. (2). The $`F_{int}=1/x^71/x^{13}`$ which equals zero when $`x=1`$, and $`F_{ext}(x)=k(xvt1)`$. The ordinate is $`F`$ = $`_0^{\mathrm{}}F_{ext}(x)P(x,t)𝑑x`$, and the abscissa is $`x`$. The line labeled LJ is the expected Lennard-Jones force. As one can see, with increasing temperature, decreasing retracting rate, and stiffer probe, the measured force-displacement curve approaches to the LJ curve. It is also noted that with small $`k_BT`$, there is a mechanical “bond rupturing”36,38, while at larger $`k_BT`$, the maximal force can be significantly smaller than that of LJ due thermally activated transtion.

Figure 2. (A) A conceptual energy landscape for a globular protein, cooperative folding63-65 (not to the appropriate scale) with a transition state at $`x^{}`$. For a single domain of titin, the reasonable $`x_o=10\AA `$ and $`L=30nm`$. The folded state is represented by the deep energy well and unfolded (random coil) state is represented by a shallow well with large entropy. The reaction coordinate (the abscissa) is uniquely defined by the direction of the mechanical force which pulls the molecule. At very small $`x`$, there is a closely packed core of all the atoms in the domain. Large $`x`$ asymptotically approaches the contour length $`L`$ of the polypeptide chain:

$$E(x)=\alpha \left\{\frac{V_0}{x_o}\left[2\left(\frac{x_o}{x}\right)^6+\left(\frac{x_o}{x}\right)^{12}\right]\right\}\beta x+\gamma \left[\frac{k_BTL}{\mathrm{}_p(1x/L)}\right]$$

where $`x_o`$ is the size of folded protein, $`V_0`$ is the energy of the folded state, and $`\mathrm{}_p`$ is the persistence length of the polypeptide random coil. $`\alpha `$, $`\beta `$ and $`\gamma `$ are parameters characterizing folded, unfolded, and stretched states of the molecule. In the figure they are chosen as $`\alpha V_0/x_o=20`$, $`\beta =1`$, and $`\gamma k_BTL/\mathrm{}_p=1`$, and $`L=10`$. (B) The corresponding force as function of displacement, $`F_1(x)=dE(x)/dx`$. $`I`$, $`II`$, and $`III`$ are used to label the three monotonic regions of the curve. Note region $`II`$ including the transition state is mechanically unstable.

Figure 3. The force-extension relation for a series of three globular domains each of which is characterized by Fig. 2B. The integers by the curves are labels for the branches in the curve. For three subunits in serial, the force is the same on different subunits and the total extension is the sum of the three individual extensions. Each branch is a sum of three from the $`I`$, $`II`$, and $`III`$ in Fig. 2B. Therefore, there are total 27 branches for a trimer, but only 10 are distinguishable (see Table I). Any branch involves $`II`$ (dotted lines) is mechanically unstable. The stable branches are 1, 5, 8, 10. The dashed lines with the slope $`k`$ represent the force-displacement for the elastic force probe with stiffness $`k`$.36,38 The bold sawtooth curve42 is expected from a mechanical force-extension experiment. A measurement using a force probe with less stiffness and slower rate will show less of the sawtooth pattern.

Figure 4. $`x`$ = $`n1`$, $`n`$, $`n+1`$, … in the figure represent the periodic binding sites of a motor protein along its track. $`A`$, $`B`$ and $`C`$ are the chemical states of the motor protein, i.e., the cyclic hydrolysis reaction can be written as $`ABCA`$. If the potential energy $`U_{int}(x,k)`$ is such that the motor can move along the track only simultaneously when $`BC`$, and there is well-defined energy barriers between $`x=n`$ and $`x=n+1`$ for $`A`$, $`B`$, and $`C`$, then we have a simplified discrete model (line with bold face) for the stochastic kinetics of a motor protein. One of the most important consequences of these assumptions is that the ATP hydrolysis and the motor protein stepping are tightly coupled.25

Table I

curve # 1 2 3 4 5 6 7 8 9 10  composition I,I,I I,I,II I,II,II II,II,II I,I,III I,II,III II,II,III I,III,III II,III,III III,III,III  multiplicity 1 3 3 1 3 6 3 3 3 1

Table Caption

Table I Each branch in Fig. 3 consists of a sum of 3 terms in Fig. 2B: $`I`$, $`II`$, and $`III`$ (Colume 2). There are total 27 branches, but some of them overlap and Colume 3 shows the multiplicity.


text:
# Boosting Applied to Word Sense Disambiguation

## 1 Introduction

Word Sense Disambiguation (WSD) is the problem of assigning the appropriate meaning (sense) to a given word in a text or discourse. This meaning is distinguishable from other senses potentially attributable to that word. Resolving the ambiguity of words is a central problem for language understanding applications and their associated tasks , including, for instance, machine translation, information retrieval and hypertext navigation, parsing, spelling correction, reference resolution, automatic text summarization, etc.

WSD is one of the most important open problems in the Natural Language Processing (NLP) field. Despite the wide range of approaches investigated and the large effort devoted to tackling this problem, it is a fact that to date no large–scale, broad coverage and highly accurate word sense disambiguation system has been built.

The most successful current line of research is the corpus–based approach in which statistical or Machine Learning (ML) algorithms have been applied to learn statistical models or classifiers from corpora in order to perform WSD. Generally, supervised approaches (those that learn from a previously semantically annotated corpus) have obtained better results than unsupervised methods on small sets of selected highly ambiguous words, or artificial pseudo–words. Many standard ML algorithms for supervised learning have been applied, such as: Naive Bayes , , Exemplar–based learning Decision Lists , Neural Networks , etc. Further, Mooney  has also compared all previously cited methods on a very restricted domain and including Decision Trees and Rule Induction algorithms. Unfortunately, there have been very few direct comparisons of alternative methods on identical test data. However, it is commonly accepted that Naive Bayes, Neural Networks and Exemplar–based learning represent state–of–the–art accuracy on supervised WSD.

Supervised methods suffer from the lack of widely available semantically tagged corpora, from which to construct really broad coverage systems. This is known as the “knowledge acquisition bottleneck”. Ng  estimates that the manual annotation effort necessary to build a broad coverage semantically annotated corpus would be about 16 man-years. This extremely high overhead for supervision and, additionally, the also serious overhead for learning/testing many of the commonly used algorithms when scaling to real size WSD problems, explain why supervised methods have been seriously questioned.

Due to this fact, recent works have focused on reducing the acquisition cost as well as the need for supervision in corpus–based methods for WSD. Consequently, the following three lines of research can be found: 1) The design of efficient example sampling methods ; 2) The use of lexical resources, such as WordNet , and WWW search engines to automatically obtain from Internet arbitrarily large samples of word senses ; 3) The use of unsupervised EM–like algorithms for estimating the statistical model parameters . It is also our belief that this body of work, and in particular the second line, provides enough evidence towards the “opening” of the acquisition bottleneck in the near future. For that reason, it is worth further investigating the application of new supervised ML methods to better resolve the WSD problem.

Boosting Algorithms. The main idea of boosting algorithms is to combine many simple and moderately accurate hypotheses (called weak classifiers) into a single, highly accurate classifier for the task at hand. The weak classifiers are trained sequentially and, conceptually, each of them is trained on the examples which were most difficult to classify by the preceding weak classifiers.

The AdaBoost.MH algorithm applied in this paper  is a generalization of Freund and Schapire’s AdaBoost algorithm , which has been (theoretically and experimentally) studied extensively and which has been shown to perform well on standard machine–learning tasks using also standard machine–learning algorithms as weak learners .

Regarding Natural Language (NL) problems, AdaBoost.MH has been successfully applied to Part–of–Speech (PoS) tagging , Prepositional–Phrase–attachment disambiguation , and, Text Categorization  with especially good results.

The Text Categorization domain shares several properties with the usual settings of WSD, such as: very high dimensionality (typical features consist in testing the presence/absence of concrete words), presence of many irrelevant and highly dependent features, and the fact that both, the learned concepts and the examples, reside very sparsely in the feature space. Therefore, the application of AdaBoost.MH to WSD seems to be a promising choice. It has to be noted that, apart from the excellent results obtained on NL problems, AdaBoost.MH has the advantages of being theoretically well founded and easy to implement.

The paper is organized as follows: Section 2 is devoted to explain in detail the AdaBoost.MH algorithm. Section 3 describes the domain of application and the initial experiments performed on a reduced set of words. In Section 4 several alternatives are explored for accelerating the learning process by reducing the feature space. The best alternative is fully tested in Section 5. Finally, Section 6 concludes and outlines some directions for future work.

## 2 The Boosting Algorithm AdaBoost.MH

This section describes the Schapire and Singer’s AdaBoost.MH algorithm for multiclass multi–label classification, using exactly the same notation given by the authors in .

As already said, the purpose of boosting is to find a highly accurate classification rule by combining many weak hypotheses (or weak rules), each of which may be only moderately accurate. It is assumed that there exists a separate procedure called the WeakLearner for acquiring the weak hypotheses. The boosting algorithm finds a set of weak hypotheses by calling the weak learner repeatedly in a series of $`T`$ rounds. These weak hypotheses are then combined into a single rule called the combined hypothesis.

Let $`S=\{(x_1,Y_1),\mathrm{},(x_m,Y_m)\}`$ be the set of $`m`$ training examples, where each instance $`x_i`$ belongs to an instance space $`𝒳`$ and each $`Y_i`$ is a subset of a finite set of labels or classes $`𝒴`$. The size of $`𝒴`$ is denoted by $`k=|𝒴|`$.

The pseudo–code of AdaBoost.MH is presented in figure 1. AdaBoost.MH maintains an $`m\times k`$ matrix of weights as a distribution $`D`$ over examples and labels. The goal of the WeakLearner algorithm is to find a weak hypothesis with moderately low error with respect to these weights. Initially, the distribution $`D_1`$ is uniform, but the boosting algorithm updates the weights on each round to force the weak learner to concentrate on the pairs (examples,label) which are hardest to predict.

More precisely, let $`D_t`$ be the distribution at round $`t`$, and $`h_t:𝒳\times 𝒴`$ the weak rule acquired according to $`D_t`$. The sign of $`h_t(x,l)`$ is interpreted as a prediction of whether label $`l`$ should be assigned to example $`x`$ or not. The magnitude of the prediction $`|h_t(x,l)|`$ is interpreted as a measure of confidence in the prediction. In order to understand correctly the updating formula this last piece of notation should be defined. Thus, given $`Y𝒴`$ and $`l𝒴`$, let $`Y[l]`$ be +1 if $`lY`$ and -1 otherwise.

Now, it becomes clear that the updating function increases (or decreases) the weights $`D_t(i,l)`$ for which $`h_t`$ makes a good (or bad) prediction, and that this variation is proportional to $`|h_t(x,l)|`$.

Note that WSD is not a multi–label classification problem since a unique sense is expected for each word in context. In our implementation, the algorithm runs exactly in the same way as explained above, except that sets $`Y_i`$ are reduced to a unique label, and that the combined hypothesis is forced to output a unique label, which is the one that maximizes $`f(x,l)`$.

Up to now, it only remains to be defined the form of the WeakLearner. Schapire and Singer  prove that the Hamming loss of the AdaBoost.MH algorithm on the training set111i.e. the fraction of training examples $`i`$ and labels $`l`$ for which the sign of $`f(x_i,l)`$ differs from $`Y_i[l]`$. is at most $`_{t=1}^TZ_t`$, where $`Z_t`$ is the normalization factor computed on round $`t`$. This upper bound is used in guiding the design of the WeakLearner algorithm, which attempts to find a weak hypothesis $`h_t`$ that minimizes: $`Z_t=_{i=1}^m_{l𝒴}D_t(i,l)\mathrm{exp}(Y_i[l]h_t(x,l))`$.

### 2.1 Weak Hypotheses for WSD

As in , very simple weak hypotheses are used to test the value of a boolean predicate and make a prediction based on that value. The predicates used, which are described in section 3.1, are of the form “$`f=v`$”, where $`f`$ is a feature and $`v`$ is a value (e.g.: “previous\_word = hospital”). Formally, based on a given predicate $`p`$, our interest lies on weak hypotheses $`h`$ which make predictions of the form:

$`h(x,l)=\{\begin{array}{cc}c_{0l}\hfill & \mathrm{if}p\mathrm{holds}\mathrm{in}x\hfill \\ c_{1l}\hfill & \mathrm{otherwise}\hfill \end{array}`$

where the $`c_{jl}`$’s are real numbers.

For a given predicate $`p`$, and bearing the minimization of $`Z_t`$ in mind, values $`c_{jl}`$ should be calculated as follows. Let $`X_1`$ be the subset of examples for which the predicate $`p`$ holds and let $`X_0`$ be the subset of examples for which the predicate $`p`$ does not hold. Let $`[[\pi ]]`$, for any predicate $`\pi `$, be 1 if $`\pi `$ holds and 0 otherwise. Given the current distribution $`D_t`$, the following real numbers are calculated for each possible label $`l`$, for $`j\{0,1\}`$, and for $`b\{+1,1\}`$:

$`W_b^{jl}=_{i=1}^mD_t(i,l)[[x_iX_jY_i[l]=b]]`$

That is, $`W_{+1}^{jl}`$ ($`W_1^{jl}`$) is the weight (with respect to distribution $`D_t`$) of the training examples in partition $`X_j`$ which are (or not) labelled by $`l`$.

As it is shown in , $`Z_t`$ is minimized for a particular predicate by choosing:

$`c_{jl}=\frac{1}{2}\mathrm{ln}(\frac{W_{+1}^{jl}}{W_1^{jl}})`$

These settings imply that:

$`Z_t=2_{j\{0,1\}}_{l𝒴}\sqrt{W_{+1}^{jl}W_1^{jl}}`$

Thus, the predicate $`p`$ chosen is that for which the value of $`Z_t`$ is smallest.

Very small or zero values for the parameters $`W_b^{jl}`$ cause $`c_{jl}`$ predictions to be large or infinite in magnitude. In practice, such large predictions may cause numerical problems to the algorithm, and seem to increase the tendency to overfit. As suggested in , smoothed values for $`c_{jl}`$ have been used.

## 3 Applying Boosting to WSD

### 3.1 Corpus

In our experiments the boosting approach has been evaluated using the DSO corpus containing 192,800 semantically annotated occurrences222These examples are tagged with a set of labels which correspond, with some minor changes, to the senses of WordNet 1.5 . of 121 nouns and 70 verbs. These correspond to the most frequent and ambiguous English words. The DSO corpus was collected by Ng and colleagues  and it is available from the Linguistic Data Consortium (LDC)333LDC e-mail address: ldc@unagi.cis.upenn.edu.

For our first experiments, a group of 15 words (10 nouns and 5 verbs) which frequently appear in the related WSD literature has been selected. These words are described in the left hand–side of table 1. Since our goal is to acquire a classifier for each word, each row represents a classification problem. The number of classes (senses) ranges from 4 to 30, the number of training examples from 373 to 1,500 and the number of attributes from 1,420 to 5,181. The MFS column on the right hand–side of table 1 shows the percentage of the most frequent sense for each word, i.e. the accuracy that a naive “Most–Frequent–Sense” classifier would obtain.

The binary–valued attributes used for describing the examples correspond to the binarization of seven features referring to a very narrow linguistic context. Let “$`w_2w_1ww_{+1}w_{+2}`$” be the context of 5 consecutive words around the word $`w`$ to be disambiguated. The seven features mentioned above are exactly those used in : $`w_2`$, $`w_1`$, $`w_{+1}`$, $`w_{+2}`$, $`(w_2,w_1)`$, ($`w_1,w_{+1}`$), and $`(w_{+1},w_{+2})`$, where the last three correspond to collocations of two consecutive words.

### 3.2 Benchmark Algorithms and Experimental Methodology

AdaBoost.MH has been compared to the following algorithms:
Naive Bayes (NB). The naive Bayesian classifier has been used in its most classical setting . To avoid the effect of zero counts when estimating the conditional probabilities of the model, a very simple smoothing technique has been used, which was proposed in .

Exemplar–based learning (EBk). In our implementation, all examples are stored in memory and the classification of a new example is based on a $`k`$–NN algorithm using Hamming distance to measure closeness (in doing so, all examples are examined). If $`k`$ is greater than 1, the resulting sense is the weighted majority sense of the $`k`$ nearest neighbours (each example votes its sense with a strength proportional to its closeness to the test example). Ties are resolved in favour of the most frequent sense among all those tied.

The comparison of algorithms has been performed in series of controlled experiments using exactly the same training and test sets for each method. The experimental methodology consisted in a 10-fold cross-validation. All accuracy/error rate figures appearing in the paper are averaged over the results of the 10 folds. The statistical tests of significance have been performed using a 10-fold cross validation paired Student’s $`t`$-test with a confidence value of: $`t_{9,0.975}=2.262`$.

### 3.3 Results

Figure 2 shows the error rate curve of AdaBoost.MH, averaged over the 15 reference words, and for an increasing number of weak rules per word. This plot shows that the error obtained by AdaBoost.MH is lower than those obtained by NB and EB15 ($`k`$=15 is the best choice for that parameter from a number of tests between $`k`$=1 and $`k`$=30) for a number of rules above 100. It also shows that the error rate decreases slightly and monotonically, as it approaches the maximum number of rules reported444The maximum number of rounds considered is 750, merely for efficiency reasons..

According to the plot in figure 2, no overfitting is observed while increasing the number of rules per word. Although it seems that the best strategy could be “learn as many rules as possible”, in  it is shown that the number of rounds must be determined individually for each word since they have different behaviours. The adjustment of the number of rounds can be done by cross–validation on the training set, as suggested in . However, in our case, this cross–validation inside the cross–validation of the general experiment would generate a prohibitive overhead. Instead, a very simple stopping criterion (sc) has been used, which consists in stopping the acquisition of weak rules whenever the error rate on the training set falls below 5%, with an upper bound of 750 rules. This variant, which is referred to as ABsc, obtained comparable results to AB750 but generating only 370.2 weak rules per word on average, which represents a very moderate storage requirement for the combined classifiers.

The numerical information corresponding to this experiment is included in table 1. This table shows the accuracy results, detailed for each word, of NB, EB1, EB15, AB750, and ABsc. The best result for each word is printed in boldface.

As it can be seen, in 14 out of 15 cases, the best results correspond to the boosting algorithms. When comparing global results, accuracies of either AB750 or ABsc are significantly greater than those of any of the other methods. Finally, note that accuracies corresponding to NB and EB15 are comparable (as suggested in ), and that the use of $`k`$’s greater than 1 is crucial for making Exemplar–based learning competitive on WSD.

## 4 Making Boosting Practical for WSD

Up to now, it has been seen that AdaBoost.MH is a simple and competitive algorithm for the WSD task. It achieves an accuracy performance superior to that of the Naive Bayes and Exemplar–based algorithms tested in this paper. However, AdaBoost.MH has the drawback of its computational cost, which makes the algorithm not scale properly to real WSD domains of thousands of words.

The space and time–per–round requirements of AdaBoost.MH are $`𝒪(mk)`$ (recall that $`m`$ is the number of training examples and $`k`$ the number of senses), not including the call to the weak learner. This cost is unavoidable since AdaBoost.MH is inherently sequential. That is, in order to learn the ($`t`$+1)-th weak rule it needs the calculation of the $`t`$-th weak rule, which properly updates the matrix $`D_t`$. Further, inside the WeakLearner, there is another iterative process that examines, one by one, all attributes so as to decide which is the one that minimizes $`Z_t`$. Since there are thousands of attributes, this is also a time consuming part, which can be straightforwardly spedup either by reducing the number of attributes or by relaxing the need to examine all attributes at each iteration.

### 4.1 Accelerating the WeakLearner

Four methods have been tested in order to reduce the cost of searching for weak rules. The first three, consisting in aggressively reducing the feature space, are frequently applied in Text Categorization. The fourth consists in reducing the number of attributes that are examined at each round of the boosting algorithm.
Frequency filtering (Freq): This method consists in simply discarding those features corresponding to events that occur less than $`N`$ times in the training corpus. The idea beyond that criterion is that frequent events are more informative than rare ones.
Local frequency filtering (LFreq): This method works similarly to Freq but considers the frequency of events locally, at the sense level. More particularly, it selects the $`N`$ most frequent features of each sense.
RLM ranking: This third method consists in making a ranking of all attributes according to the RLM distance measure  and selecting the $`N`$ most relevant features. This measure has been commonly used for attribute selection in decision tree induction algorithms555RLM distance belongs to the distance–based and information–based families of attribute selection functions. It has been selected because it showed better performance than seven other alternatives in an experiment of decision tree induction for PoS tagging ..
LazyBoosting: The last method does not filter out any attribute but reduces the number of those that are examined at each iteration of the boosting algorithm. More specifically, a small proportion $`p`$ of attributes are randomly selected and the best weak rule is selected among them. The idea behind this method is that if the proportion $`p`$ is not too small, probably a sufficiently good rule can be found at each iteration. Besides, the chance for a good rule to appear in the whole learning process is very high. Another important characteristic is that no attribute needs to be discarded and so we avoid the risk of eliminating relevant attributes666This method will be called LazyBoosting in reference to the work by Samuel and colleagues . They applied the same technique for accelerating the learning algorithm in a Dialogue Act tagging system..

The four methods above have been compared for the set of 15 reference words. Figure 3 contains the average error–rate curves obtained by the four variants at increasing levels of attribute reduction. The top horizontal line corresponds to the MFS error rate, while the bottom horizontal line stands for the error rate of AdaBoost.MH working with all attributes. The results contained in figure 3 are calculated running the boosting algorithm 250 rounds for each word.

The main conclusions that can be drawn are the following:

* All methods seem to work quite well since no important degradation is observed in performance for values lower than 95% in rejected attributes. This may indicate that there are many irrelevant or highly dependent attributes in our domain.
* LFreq is slightly better than Freq, indicating a preference to make frequency counts for each sense rather than globally.
* The more informed RLM ranking performs better than frequency–based reduction methods Freq and LFreq.
* LazyBoosting is better than all other methods, confirming our expectations: it is worth keeping all information provided by the features. In this case, acceptable performance is obtained even if only 1% of the attributes is explored when looking for a weak rule. The value of 10%, for which LazyBoosting still achieves the same performance and runs about 7 times faster than AdaBoost.MH working with all attributes, will be selected for the experiments in section 5.

## 5 Evaluating LazyBoosting

The LazyBoosting algorithm has been tested on the full semantically annotated corpus with $`p=10\%`$ and the same stopping criterion described in section 3.3, which will be referred to as ABl10sc. The average number of senses is 7.2 for nouns, 12.6 for verbs, and 9.2 overall. The average number of training examples is 933.9 for nouns, 938.7 for verbs, and 935.6 overall.

The ABl10sc algorithm learned an average of 381.1 rules per word, and took about 4 days of cpu time to complete777The current implementation is written in PERL-5.003 and it was run on a SUN UltraSparc2 machine with 194Mb of RAM.. It has to be noted that this time includes the cross–validation overhead. Eliminating it, it is estimated that 4 cpu days would be the necessary time for acquiring a word sense disambiguation boosting–based system covering about 2,000 words.

The ABl10sc has been compared again to the benchmark algorithms using the 10-fold cross–validation methodology described in section 3.2. The average accuracy results are reported in the left hand–side of table 2. The best figures correspond to the LazyBoosting algorithm ABl10sc, and again, the differences are statistically significant using the 10-fold cross–validation paired $`t`$-test.

The right hand–side of the table shows the comparison of ABl10sc versus NB and EB15 algorithms, respectively. Each cell contains the number of wins, ties, and losses of competing algorithms. The counts of statistically significant differences are included in brackets. It is important to point out that EB15 only beats significantly ABl10sc in one case while NB does so in five cases. Conversely, a significant superiority of ABl10sc over EB15 and NB is observed in 107 and 86 cases, respectively.

## 6 Conclusions and Future Work

In the present work, Schapire and Singer’s AdaBoost.MH algorithm has been evaluated on the word sense disambiguation task, which is one of the hardest open problems in Natural Language Processing. As it has been shown, the boosting approach outperforms Naive Bayes and Exemplar–based learning, which represent state–of–the–art accuracy on supervised WSD. In addition, a faster variant has been suggested and tested, which is called LazyBoosting. This variant allows the scaling of the algorithm to broad-coverage real WSD domains, and is as accurate as AdaBoost.MH. Further details can be found in an extended version of this paper .

Future work is planned to be done in the following directions:

* Extensively evaluate AdaBoost.MH on the WSD task. This would include taking into account additional attributes, and testing the algorithms in other manually annotated corpora, and especially on sense–tagged corpora automatically obtained from Internet.
* Confirm the validity of the LazyBoosting approach on other language learning tasks in which AdaBoost.MH works well, e.g.: Text Categorization.
* It is known that mislabelled examples resulting from annotation errors tend to be hard examples to classify correctly, and, therefore, tend to have large weights in the final distribution. This observation allows both to identify the noisy examples and use boosting as a way to improve data quality . It is suspected that the corpus used in the current work is very noisy, so it could be worth using boosting to try and improve it.


text:
# 1 Decomposing one density operator

## 1 Decomposing one density operator

A density operator, representing a state, is a positive operator with trace one. However, it is convenient for the following considerations not to insist in normalization.
We shall assume, mainly for technical simplicity, a finite dimensional Hilbert space, $``$, the dimension of which is denoted by $`dim=d`$. Thus, mathematically, we are just dealing with positive operators (and with the Null operator) of a finite dimensional Hilbert space.

Let $`\tau `$ be a positive operator on our Hilbert space. Its decreasingly ordered eigenvalues are denoted by $`\lambda _1,\lambda _2,\mathrm{}`$, i. e.

$$\text{spec}(\tau )=\{\lambda _1\lambda _2\mathrm{}\}$$

By a decomposition of $`\tau `$ I denote every set of vectors $`|\chi _j`$ such that

$$\tau =|\chi _j\chi _j|$$
(1)
As I showed in

$$\underset{j=1}{\overset{m}{}}\lambda _j\underset{j=1}{\overset{m}{}}\chi _j|\chi _j$$
(2)
is valid for all $`1mdim`$. Moreover, equality is reached if and only if $`|\chi _j`$ is an eigenvector for $`\lambda _j`$ of $`\tau `$ for all $`j=1,\mathrm{},m`$.
The motivation for asking questions of that kind has been the problem whether the von Neumann entropy of a density operator is already fixed by its position as a point in the convex set of all density operators. The result just quoted gives, if written with normalized vectors, an affirmative answer. Indeed, my aim was to define on every (compact) convex set a function which just gives the von Neumann entropy if applied to state spaces of a quantum system. Up to day I do not know whether the construction is of any use for other convex sets than quantum state spaces.

In  M. A. Nielsen proved the reversed statement: If $`p_j`$ are positive numbers which are majorized by spec$`(\tau )`$, then there exists a decomposition (1) such that $`p_j=\chi _j|\chi _j`$.

The results mentioned above will be slightly extended to the case that there are two decompositions of one and the same $`\tau `$. Thus let

$$\tau =|\chi _j^{}\chi _j^{}|$$
(3)
be a further decomposition of $`\tau `$. Adding (1) and (3) we get a decomposition of $`2\tau `$ and

$$\underset{j=1}{\overset{m}{}}(\chi _j|\chi _j+\chi _j^{}|\chi _j^{})2\underset{j=1}{\overset{m}{}}|\chi _j|\chi _j^{}|$$

Equality takes place iff $`|\chi _j`$ differs from $`|\chi _j^{}`$ by a phase factor only. Because the eigenvalues of $`2\tau `$ are just $`2\lambda _j`$ we get

Proposition 1: Let (1) and (3) be decompositions of $`\tau `$ and $`\lambda _1\lambda _2\mathrm{}`$ the decreasingly ordered eigenvalues of $`\tau `$, and $`1md`$. Then

$$\underset{j=1}{\overset{m}{}}\lambda _j\underset{j=1}{\overset{m}{}}|\chi _j|\chi _j^{}|$$
(4)
Equality holds if and only if for $`1jm`$

$$\tau |\chi _j=\lambda _j|\chi _j,|\chi _j^{}=ϵ_j|\chi _j$$
(5)
with unimodular numbers $`ϵ_j`$.

## 2 Decomposing two density operators

Let us now consider a pair, $`\rho `$ and $`\omega `$, of positive operators.
Definition:$`F_m^+(\rho ,\omega )`$ denotes the sum of the $`m`$ largest eigenvalues of

$$(\sqrt{\rho }\omega \sqrt{\rho })^{1/2}$$
(6)
The definition works well for $`1md`$. It is sometimes convenient to extend it by $`F_m^+=F_d^+`$ if $`md`$ and to set $`F_m^+=0`$ for $`m=0`$.
Remark that $`F_d^+`$ is the square root of the transition probability . The square root of the transition probability is called fidelity and is denoted by $`F(\rho ,\omega )`$ in the present paper. Notice, however, that Jozsa, who showed its use in quantum information theory , identified the general transition probability with his fidelity concept (and not with its square root).
A further remark is the following: In  I considered another quantity: The $`k`$-fidelity, $`F_k`$, which is the sum of all but the first $`k`$ eigenvalues of (6). These partial fidelities are jointly concave (and super-additive) in its arguments for $`k`$ = 0, 1, … Obviously,

$$F_m^+(\rho ,\omega )=F(\rho ,\omega )F_m(\rho ,\omega )$$

In contrast to the partial fidelities, the quantity (8) seems to be neither concave nor convex if $`m`$ is smaller than $`dim`$.
Finally, let us rewrite (4) of proposition 1 as

$$F(\tau ,\tau )\underset{j=1}{\overset{m}{}}|\chi _j|\chi _j^{}|,$$
(7)
Remember that equality in (7) can be reached by eigenvector decompositions of $`\tau `$ with decreasingly ordered eigenvalues.

Theorem 1:Let be $`1md`$. It is

$$F_m^+(\rho ,\omega )=\mathrm{max}\underset{j=1}{\overset{m}{}}|\psi _j|\phi _j|$$
(8)
where the maximum is to perform over all possible decompositions

$$\rho =|\psi _j\psi _j|,\omega =|\phi _j\phi _j|.$$
(9)
If the length of a decomposition is less than $`dim`$, or if the length of the two compositions (9) are different, one adds some zero vectors to get decompositions of equal and large enough length.

The proof of the theorem starts by stating the invariance of the eigenvalues of (6) with respect of a transformation

$$\{\rho ,\omega \}\{\rho ,\omega \}^X:=\{X\rho X^{},(X^1)^{}\omega X^1\}$$
(10)
for any invertible operator $`X`$, see . ((In the present paper the Hermitian adjoint of an operator $`A`$ is denoted by $`A^{}`$ and not by $`A^{}`$.)) Hence the sum of the $`m`$ largest eigenvalues of (6) cannot be changed by such a transformation. On the other hand, if we simultaneously transform decompositions (9) according to

$$|\psi _jX|\psi _j,|\phi _j(X^1)^{}|\phi $$
(11)
then the right hand side of (8) remains unchanged. Therefore, if the assertion of the theorem is true for a pair of density operators $`\{\rho ,\omega \}`$, it is true for every pair $`\{\rho ,\omega \}^X`$.
Let now $`\rho `$ and $`\omega `$ be invertible (i. e. faithful). If we then can choose $`X`$ such that

$$\{\rho ,\omega \}^X:=\{\tau ,\tau \}$$
(12)
with a certain $`\tau `$ yet to be determined, we are done: For the pair $`\{\tau ,\tau \}`$ the theorem is equivalent to proposition 1. But

$$X\omega X^{}=(X^1)^{}\rho X^1:=\tau $$
(13)
is valid if $`X^{}X`$ is the geometric mean  of $`\rho `$ and $`\omega ^1`$, i.e.

$$X^{}X=\omega ^{1/2}\left(\omega ^{1/2}\rho \omega ^{1/2}\right)^{1/2}\omega ^{1/2}$$
(14)
Hence, the theorem is true for invertible $`\rho `$ and $`\omega `$.
Indeed, the proof covers the case of any pair $`\rho `$, $`\omega `$, with equal supports: To see it we only have to replace $``$ by the supporting Hilbert subspace because neither to $`F_m^+`$ nor to the decompositions there is a non-zero contribution from the null spaces (i.e. the kernels) of $`\rho `$ and $`\omega `$.

We now prove that the right hand side of (8) never exceeds $`F_m^+`$. Denote by $`P_0`$, $`Q_0`$ the projection operators onto the null spaces of $`\rho `$ and $`\omega `$. We choose decompositions of $`P_0`$ and $`Q_0`$ with vectors $`|\psi _i^{}`$ and $`|\phi _i^{}`$ respectively. We complement arbitrarily chosen decompositions (9) to those of $`\rho ^{}=\rho +c_1P_0`$ and $`\omega ^{}=\omega +c_2Q_0`$ with $`c_j>0`$. For $`\rho ^{}`$ this is done by

$$\rho ^{}=\rho +c_1P_0=|\psi _j\psi _j|+c_1|\psi _j^{}\psi _j^{}|$$

and similarly we proceed with $`\omega ^{}`$. Because $`\rho ^{}`$ and $`\omega ^{}`$ are invertible, we already can apply theorem 1 to them. Because $`F_m^+(\rho ^{},\omega ^{})`$ is approaching $`F_m^+(\rho ,\omega )`$ if $`c_j0`$ we are done.

What remains to show is the following: There are decompositions (9) such that $`|\psi _i,\phi _i|`$ is equal to $`F_m^+`$, whatsoever the support properties of $`\rho `$ and $`\omega `$ may be. To get this we first assert:
Let $`Q`$ be the projection operator onto the supporting space of $`\omega `$. For all decompositions (9) we get

$$Q\psi _i|\phi =\psi _i|Q|\phi =\psi _i|\phi $$

because every vector of a decomposition of $`\omega `$ must be an eigenvector of $`Q`$. That is, every one of the sums in question for $`\rho ,\omega `$ gives one for $`Q\rho Q,\omega `$ yielding the same value. On the other hand, if we start with decompositions of $`Q\rho Q,\omega `$, we can add terms orthogonal to $`\omega `$ into the decomposition of $`\rho `$ to get a decompositions of $`\rho ,\omega `$ without changing the value of the sum. Below we shall show the equality of $`F_m^+(\rho ,\omega )`$ with $`F_m^+(Q\rho Q,\omega )`$, and, all together, we obtain: If and only if theorem 1 is true for the pair $`Q\rho Q,\omega `$ it is true for the pair $`\rho ,\omega `$. Now we can proceed as following: If the supports of $`Q\rho Q`$ and $`\omega `$ are equal, we are done. If not, we consider the projection operator $`P_1`$ onto the support of $`Q\rho Q`$, yielding the same statement for the pairs $`\rho ,\omega `$, $`Q\rho Q,\omega `$, and $`Q\rho Q,P_1\omega P_1`$. Either the last pair is of equal support, and we are done, or continue the same game with the projection operator $`Q_1`$ onto the support of $`P_1\omega P_1`$. This procedure must terminate after a finite number of steps yielding a pair with equal supports. The obvious reason: In every necessary step, the rank of one member of the pair under consideration is diminished, and we are in finite dimensions.
The proof of theorem 1 is done after showing the equality of $`F_m^+(\rho ,\omega )`$ with $`F_m^+(Q\rho Q,\omega )`$ if $`Q`$ is the support projection of $`\omega `$. This assertion is a particular case with $`X=Q`$ of the equation

$$F_m^+(\rho ,X^{}\omega X)=F_m^+(X\rho X^{},\omega )$$
(15)
For invertible $`X`$ the transformation (10) does not change the eigenvalues of (6). By the replacement $`\omega X^{}\omega X`$ we thus get (15) for invertible $`X`$. But $`F_m^+`$ is continuous in its arguments, and (15) is valid for all $`X`$.

Let us underline the main point in constructing decompositions (9) satisfying

$$F_m^+(\rho ,\omega )=\underset{j=1}{\overset{m}{}}\psi _j|\phi _j,m=1,2,\mathrm{}$$
(16)
We have to solve (13) so that $`X`$ and $`\tau `$ are at our disposal. From the spectral decomposition of $`\tau `$,

$$\tau =|\chi _j\chi _j|,\chi _j|\chi _k=\lambda _j\delta _{jk}$$
(17)
we get an optimal decomposition satisfying (16) by

$$|\psi _j=X^1|\chi _j,|\phi _j=X^{}|\chi _j$$
(18)
Such a choice fulfills the bi-orthogonal relations

$$\psi _k|\phi _j=\psi _j|\phi _k=\lambda _j\delta _{jk}$$
(19)
Acknowledgement. I like to thank P. M. Alberti, B. Crell, Ch. Fuchs, and M. Nielsen for valuable discussions and correspondence.