text:
# c(2x2) Interface Alloys in Co/Cu Multilayers - Influence on Interlayer Exchange Coupling and GMR

## 1 Introduction

In the context of magnetoelectronic applications structural properties of the interfaces in nanostructured devices have attracted huge attention. Especially, the properties of the ferromagnet/nonmagnet (FM/NM) interface are expected to be crucial for new phenomena like oscillatory IXC and GMR that occur in magnetic layered systems. Several experiments have shown that even in the best homoepitaxially grown samples interdiffusion at the interfaces exists. The formation of, even partially ordered surface alloys on a Cu(001) substrate was reported for, e.g. Mn , Fe  and Co . Recent experiments on Co/Cu spin valve systems have shown the high sensitivity of the magnetotransport on the interface properties by introducing 3d scattering centers at various positions in the Co and Cu layer ($`\delta `$-layer doping) . The Co/Cu(001) system is a model system for magnetism in systems with reduced dimension . The lattice mismatch is rather small (about 2%) and the materials are completely immiscible in the bulk phase. Our investigations are focussed on the electronic properties of ordered interface alloys in a Co/Cu(001) multilayer system. The formation of QWS arises from the confinement of the Cu electrons. The strong correlation between IXC and quantum well states will be demonstrated. The influence on magnetotransport properties will be discussed.

## 2 Method

The electronic structure of the considered systems was calculated selfconsistently using a Screened Korringa-Kohn-Rostoker (KKR) method  based on a Green’s function multiple scattering formalism. The screening procedure is an exact reformulation of the traditional KKR method  to accelerate and simplify the numerical solution of the Dyson equation for the Green’s function. The numerical effort scales linearly with the size of the unit cell for systems with a prolonged supercell. The systems were modelled as superlattices with a complex unit cell periodically repeated in 3 dimensions. That means, we consider infinite multilayer structures and exclude the influence of surfaces. The Co layer thickness was fixed to 9 monolayers (ML), $`1.6nm`$ following the experimentally investigated systems. We neglect all lattice relaxations at the interfaces. All atomic positions are fixed to an ideal fcc lattice with a lattice constant of $`6.76a.u.`$. The chosen lattice constant lies between the bulk lattice constant of magnetic fcc Co ($`6.7a.u.`$) and fcc Cu ($`6.83a.u.`$). We use spherical potentials in the atomic sphere approximation (ASA). The exchange and correlation part is described by means of the local spin density approximation in the parametrization of Vosko, Wilk and Nusair . The angular momentum expansion of the Green’s function was treated up to $`l_{max}=3`$ and for the charge density up to $`l_{max}=6`$. To simulate the c(2x2) ordered interface alloy we replace every second atom in the Co interface layer by a 3d element (V, Cr, Mn, Fe, Co, Ni, and Cu, resp.), which causes an increase of the in-plane unit cell by a factor of 2.

## 3 Stability of ordered Interface Alloy

It was shown by several authors  that the structural properties of the interfaces play an important role for the interlayer exchange coupling and GMR. The amplitude of IXC and the GMR ratio can change drastically. We demonstrate that the structural properties of the interfaces are crucial for magnetotransport properties in multilayer systems. The interface structure depends strongly on growth conditions during the preparation process. Besides mesoscopic roughness and interdiffusion the formation of an ordered interface alloy may occur. The paper is focussed on the role of ordered interface alloys. First of all we will discuss the stability of the interface alloys in a Co/Cu multilayer. For this purpose we compare the total energy of three different interface configurations: 0) the ideal atomically flat interface with c(1x1) symmetry, 1) one intermixed interface layer with the same number of Co and Cu atoms equally distributed with c(2x2) symmetry, and 2) two intermixed interface layers with c(2x2) symmetry. The considered superlattice of type 0 consist of 9 ML Co and 7 ML Cu. For type 1 and 2 the number of Co layers is reduced by the intermixed layers to keep the Cu thickness constant. The interface formation energy is defined to be

$$E^f=E^In_{Co}E_{Co}n_{Cu}E_{Cu}$$
(1)
where $`E^I`$ denotes the total energy of the superlattice with one of the above described interface configurations. $`E^I`$ is compared with the total energies of the bulk systems Co and Cu, respectively. The bulk calculations have been performed at the same lattice constant used in the supercell calculation. $`n_{Co}`$ and $`n_{Cu}`$ are the numbers of $`Co`$ and $`Cu`$ atoms in the unit cell, respectively. $`E^f`$ and all other energies are normalized to an interface area of the c(1x1) structure. We obtain the following values: $`E_0^f=190meV`$ for the ideal interfaces, $`E_1^f=240meV`$ for one intermixed atomic layer and $`E_2^f=410meV`$ for two intermixed interface layers. The energetical most favourable configuration is the ideal Co/Cu interface. This result is in line with the inmiscibility of the materials at low temperatures. The energy difference of $`50meV`$ between the ideal and the one intermixed layer configuration is of the order of the total energy difference resolution of our method. Kinetic reasons during the growth process can stabilize the configuration with one intermixed layer. The formation energy of the interface with 2 intermixed layers is remarkable larger. These results indicate that the c(2x2) structures found at surfaces with monolayer and submonolayer coverage of $`Co`$ on $`Cu(001)`$  should remain at interfaces in multilayers, too. The magnetic interaction of the Co layers (IXC) mediated by the Cu electrons is RKKY-like and for this system about $`1meV`$. The magnetic interaction of adjacent interfaces due to the finite Co thickness is expected to be of the same order. Both contributions are negligible in comparison to the interface formation energy $`E^f`$.

## 4 Local Density of States

We discuss the spin dependent local density of states (LDOS) derived from the diagonal part of the Green’s function and the obtained magnetic moments of the alloy constituents to characterize the electronic structure

$$n^\sigma (E,𝐫)=\frac{1}{\pi }mG^\sigma (E,𝐫,𝐫).$$
(2)
We denote the alloy constituents by impurities in the sense of a periodic impurity arrangement in the interface atomic layer.

Figure 1 shows the LDOS in the impurity Wigner-Seitz sphere for both spin directions. The energy is given relative to the Fermi level which is fixed by the underlying $`Co/Cu`$ superlattice. The system with the ideal interfaces corresponds to the $`Co`$ interface alloy and has c(1x1) symmetry. The local density of states are comparable to that obtained for 3d impurities in bulk $`Co`$ . For $`V`$, $`Cr`$ and $`Mn`$ we obtain a sharp virtual bound state above the Fermi level. The less attractive Coulomb potential for the early 3d elements cannot be counterbalanced by a larger exchange-correlation potential. For the later elements $`Fe`$, $`Ni`$, and $`Cu`$ the exchange-correlation and Coulomb potential act in opposite directions for the majority electrons. The majority d-states remain filled and nearly unchanged and the minority states are shifted to lower energies and cause a reduced magnetic moment. This behaviour reflects the differences of the impurity potentials with respect to the Co potential at the ideal $`Co/Cu(001)`$ interface. The nearly unchanged majority spin potential along with the drastic changes in the minority channel have a strong impact on the magnetotransport properties. This will be discussed later in detail.

The magnetic moments of the impurities are shown in Fig. 2. For the early 3d impurities $`V`$, $`Cr`$, and $`Mn`$ our calculation yields the antiferromagnetic alignment of the impurity moment relative to the Co moment as ground state. For the second half of the 3d series $`Fe`$, $`Ni`$ and $`Cu`$ the ferromagnetic state is energetically preferred. The size of the local moment nearly follows Hund’s rule with a maximum at half d-band filling.

## 5 Interlayer Exchange Coupling

For the calculation of the strength of IXC we apply the frozen potential approximation (FPA)  neglecting the double counting parts in the total energy. We calculate the electronic structure for the parallel (P) alignment of the Co magnetic moments selfconsistently. The antiparallel (AP) configuration was obtained by flipping the magnetization direction in every second Co layer interchanging the fixed spin dependent ASA potentials. The strength of the IXC is then given by the single particle contributions to the total energy

$`\mathrm{\Delta }E`$ $`=`$ $`E_{SP}^PE_{SP}^{AP}`$ (3)
$`E_{SP}`$ $`=`$ $`{\displaystyle \frac{1}{\pi }}{\displaystyle \underset{\sigma }{}}m{\displaystyle _{\mathrm{}}^\mu }𝑑E{\displaystyle d^3𝐫(E\mu )G^\sigma (E,𝐫,𝐫)}\mu N`$ (4)
with $`\mu `$ denoting the chemical potential and $`N`$ the total number of valence electrons. The total energy difference $`\mathrm{\Delta }E`$ is proportional to the strength of the bilinear coupling term which has a cosine dependence on the angle between adjacent Co layer magnetization directions. To determine higher order coupling terms one has to consider non-collinear magnetic configurations. Usually, the amplitudes of these contributions are much smaller than the bilinear one and consequently negligible .

The strength of IXC varies with the thickness $`d`$ of the NM spacer layer. In the asymptotic region at large spacer thicknesses $`\mathrm{\Delta }E`$ is a superposition of oscillatory contributions. The oscillation periods are determined by stationary points of the spacer Fermi surface . For a $`Cu`$ spacer in (001)-orientation 2 wellknown contributions exist, a short period from the neck region and a long period from the belly region of the ’dogs bone’ orbit.

In systems with a periodic c(2x2) superstructure the in-plane real space periodicity is increased. The Fermi surface of Cu has to be folded down into a smaller Brillouin zone. This is equivalent to the occurence of Umklapp processes due to different symmetries of spacer and FM layer. As it was shown by Kudrnovský et al. a new stationary point on the Cu Fermi surface appears . The corresponding period is very short ($`2.15ML`$). All stationary points and periods obtained in our calculation are summarized in Tab. 1.

The different oscillatory contributions to the IXC energy are characterized by their amplitudes $`A_i`$ and phases $`\varphi _i`$

$$\mathrm{\Delta }E=\underset{i=1}{\overset{3}{}}\frac{A_i}{d^2}\mathrm{sin}\left(\frac{2\pi }{\lambda _i}d+\varphi _i\right).$$
(5)
These parameters are determined by the coupling of the Cu electrons to the polarized electrons in the Co layers. They are influenced by the thickness and chemical composition of the FM layer and the interface structure. The decay with the square of the spacer thickness arises from the screening of a 2-dimensional perturbation in a noninteracting electron gas. To determine the oscillatory contributions of IXC we calculated the coupling strength in dependence on the Cu spacer thickness. The Co layer thickness was fixed and both interfaces of the Co layers were decorated with an ordered c(2x2) alloy of the 3d elements. The Cu thickness was varied in integer steps between 7 and 60 ML. Calculating the single-particle contribution of the total energy the density of states is obtained from the diagonal part of the Green’s function by a Brillouin zone integration. To accelerate this integration a Fermi-Dirac occupation function for the single-particle states with a finite temperature of $`400K`$ is used . This smearing of the Fermi edge results in an exponential damping of the coupling energy for spacer thicknesses much larger than a critical value L . The decay length L is about 20 ML for the used temperature, spacer material and crystal orientation.

From a discrete Fourier transformation at the known periods $`\lambda _i`$ we obtain the amplitudes and phases of the different contributions. Figure 3 shows the amplitudes $`A_i`$ and phases $`\varphi _i`$ for the three contributions. The amplitude $`A_1`$ of the long period oscillation is very small for all considered systems including the ideal Co/Cu superlattice. The amplitude $`A_2`$ of the short period oscillation dominates the coupling energy for nearly all systems and varies by about 30%. The largest variations were found for the amplitude $`A_3`$ of the oscillation caused by the superstructure. Due to symmetry arguments the amplitude $`A_3`$ vanishes for the system with ideal interfaces. This sytem has a c(1x1) in-plane symmetry and $`𝒌_3`$ is not a stationary point at the Cu Fermi surface. The amplitude $`A_3`$ dominates for the systems with $`Cr`$ and $`Mn`$ interface alloys and is about 3 times larger than the short period amplitude $`A_2`$. To elucidate the origin of this large contribution to the interlayer coupling strength we focus on the formation of quantum well states in the multilayer structure.

## 6 Quantum Well States

The description of the IXC in the RKKY picture was succesfully applied to explain the oscillatory contributions and the periods . To determine the phases and amplitudes of the oscillations the resulting electronic structure of the multilayer has to be examined. Crucial for the IXC is the occurence of spin polarized localized states (QWS) in the spacer layer near the Fermi level. The boundary conditions caused by the spin dependent potential give rise to the formation of QWS. Changing the relative orientation of the magnetization direction of adjacent Co layers the energy of the QWS is shifted. In case quantum well states are shifted across the Fermi level the redistribution of electrons causes a change in the total energy and leads to the preference of one magnetic configuration to the other.

To elucidate the drastic changes in the amplitudes of the IXC contributions in dependence on the alloy constituent we investigated the $`𝒌`$-projected partial LDOS (kpLDOS) at the Fermi level. We obtain this quantity by integrating the diagonal part of the one-electron Green’s function in real space over the Wigner Seitz sphere and in reciprocal space over $`k_{}`$ perpendicular to the plane

$$n_l^\nu (𝒌_{})=\frac{1}{\pi }\underset{m}{}𝑑k_{}mG_{LL}^{\nu \nu }(z,𝒌_{},k_{}).$$
(6)
$`L=(l,m)`$ is a short hand notation for orbital and magnetic quantum number, $`\nu `$ is the site index in the unit cell and $`z`$ the Fermi energy $`ϵ_F`$ with a small complex part $`\mathrm{\Gamma }`$ of about $`0.2eV`$ to achieve a better convergence in the $`k_{}`$ integration. The kpLDOS is related to the probability amplitude of the eigenstates at the Fermi level

$`n_l^\nu (𝒌_{})`$ $`={\displaystyle \frac{1}{\pi }}{\displaystyle \underset{m}{}}{\displaystyle 𝑑E𝑑k_{}\left|\mathrm{\Psi }_{(𝒌_{},k_{})}^{\nu L}(E)\right|^2\frac{\mathrm{\Gamma }}{(Eϵ_F)^2+\mathrm{\Gamma }^2}}`$ (7)
$`{\displaystyle \underset{k_perp}{}}\delta (Eϵ_F)\left|\mathrm{\Psi }_{(𝒌_{},k_{})}^{\nu L}(ϵ)\right|^2.`$ (8)
The typical probability amplitude for confined states in a layered strucure can be obtained for a free electron model with potential wells in growth direction. From the boundary condition that the wave function decreases exponentially in the potential barrier one obtains an oscillatory probability amplitude inside the potential well. The oscillation period is given by the wave vector of the free states without any barrier. In the NM/FM multilayer system the potential barrier corresponds to the FM layers and the states in the NM spacer are confined in the resulting potential. The oscillation of the probability amplitude is given by the unperturbed spacer states. A strong oscillatory variation of the probability amplitude inside the the spacer indicates a strong confinement and a large contribution to the IXC from the considered stationary $`𝒌_{}`$ vector.

Figure 4 shows the $`𝒌`$-projected partial LDOS at the stationary $`𝒌_{}^3`$ point for the system with ideal interfaces, the $`Cr`$, and the $`Mn`$ alloy. The spin-dependent kpLDOS is shown for every atomic layer for the P alignement of the $`Co`$ magnetic moments. We remind the reader that every atomic layer is represented by 2 atoms. On the left and right are the Co layers, the dashed vertical lines mark the alloyed Co interface layers and in between is the Cu spacer. For the ideal system the states at $`𝒌_{}^3`$ have a nearly constant amplitude in the Cu spacer and a strong hybridization with the Co states for both spin directions. In contrast, the minority states in the $`Cr`$ and $`Mn`$ alloyed sytems show strong indications of quantum confinement in the spacer region. The s- and d-angular momentum contributions show clear oscillations with a period of about $`2ML`$. This coincides with the Fermi wave vector of $`Cu`$ at $`𝒌_{}^3`$ which determines the oscillation period of the superstructure contribution to IXC. At the position of the stationary point $`𝒌_{}^2`$ we found for all the considered systems confined states in the $`Cu`$ spacer for minority and majority spin electrons.

## 7 Giant MagnetoResistance

For the calculation of transport properties we use Mott’s two-current model  neglecting spin flip scattering. For the considered systems assuming non-Kondo-impurities only this assumption should be reasonable. The linearized Boltzmann equation in relaxation time approximation was solved. One yields the spin dependent conductivity $`\sigma ^\sigma `$ from a Fermi surface integral weighted with an isotropic relaxation time neglecting the anisotropy of the scattering operator

$$\sigma ^\sigma =\frac{e^2}{V}\tau \underset{𝒌}{}\delta (ϵ_𝒌^\sigma ϵ_F)𝒗_𝒌^\sigma 𝒗_𝒌^\sigma .$$
(9)
The superscript $`\sigma `$ denotes the spin direction and $`V`$ the crystal volume. A modified tetrahedron method was used to obtain the Fermi surface integrals . Assuming the same spin independent relaxation times $`\tau `$ for both magnetic configurations of the Co moments (P,AP) this quantity does not enter the expression for the GMR ratio. The GMR ratio is defined in the usual way by normalizing the resistivity drop in a sufficient large magnetic field by the saturation resistivity. In terms of conductivities for the P and AP configurations this is

$$R=\frac{\sigma ^P}{\sigma ^{AP}}\mathrm{\hspace{0.17em}1}.$$
(10)
In Fig. 5 (upper panels) the spin resolved conductivity contributions for the P configuration are shown in dependence on the interface alloy constituent. The conductivities are calculated for current in-plane (CIP) and perpendicular-to-plane (CPP) geometry. For defects with a moment parallel to the Co magnetization a large spin anisotropy occurs. The conductivity is dominated by the fast majority channel, especially pronounced in the CPP geometry. The occurence of one dominating spin channel in the P configuration is essential to establish a large GMR ratio. In $`Co/Cu`$ systems the majority potential for both materials is nearly equal whereas the minority potential has strong quantum well modulations. For the AP configuration the effective potential for both spin channels is a mixing of majority and minority potentials and causes averaged conductivities. The same effect is produced by defects with an antiparallel moment relative to the $`Co`$ moment causing a strong perturbation of the majority potential even in the P configuration.

In Fig. 5 (central panel) the total conductivities for the P and AP confuguration are compared. The relative difference determines the GMR ratio. We obtain a CIP-GMR ratio of $`31\%`$ for the system with ideal interfaces. For the alloys of $`Fe`$, $`Ni`$, and $`Cu`$ with a moment parallel to the $`Co`$ moment the value is increased by nearly a factor of 2. In the contrary, for systems with alloys of $`V`$, $`Cr`$, and $`Mn`$ with antiparallel moment the CIP-GMR ratio is reduced systematically. As a result, we can conclude the following empirical rule for the influence of interface alloys on CIP transport. Magnetic ordered structures with moments parallel to the ferromagnetic layers increase the GMR ratio whereas alloy constituents with antiparallel moments decrease the ratio.

In CPP geometry the GMR ratio changes by about 60% for alloys with parallel moments. In the case of antiparallel moment of the alloy constituent the spin asymmetry of the conductivity in the P configuration changes the sign and the conductivity is dominated by the minority channel. Additionally, the conductivity for AP configuration decreases rapidly for the earlier 3d elements and causes a strong enhancement of GMR for $`V`$ and $`Cr`$ interface alloys.

## 8 Summary

We demonstrated that the electronic structure of a Co/Cu(001) multilayer systems is strongly influenced by the formation of an ordered interface alloy. The correspondence between the formation of quantum well states and the strength of oscillatory IXC in dependence on the interface structure was demonstrated. We found a third oscillatory contribution to IXC arising from the c(2x2) interface alloy symmetry. The amplitude of this contribution varies strongly in dependence on the alloy constituent. Due to the very short oscillation period the experimental confirmation of this contribution would be a strong challenge. The GMR ratio is mainly determined by the coherent potential landscape of the multilayer. The resistivity drop is caused by the occurence of a fast and slow channel in the P configuration. The GMR ratio decreases rapidly with the vanishing spin asymmetry of the conductivity in P configuration due to alloy constituents with an antiparallel moment.

We would like to thank G. Güntherodt, P.H. Dederichs, and J. Binder for stimulating discussions. P.Z. ackknowledges the support by the German BMBF-Leitprojekt ”Magnetoelektronik” (contract 13N7379).


format: text

text:
# A Comparison between Supervised Learning Algorithms for Word Sense Disambiguation

## 1 Introduction

Word Sense Disambiguation (WSD) is the problem of assigning the appropriate meaning (or sense) to a given word in a text or discourse. Resolving the ambiguity of words is a central problem for large scale language understanding applications and their associate tasks \[Ide and Véronis, 1998\]. Besides, WSD is one of the most important open problems in NLP. Despite the wide range of approaches investigated \[Kilgarriff and Rosenzweig, 2000\] and the large effort devoted to tackle this problem, to date, no large-scale broad-coverage and highly accurate WSD system has been built.

One of the most successful current lines 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 previously semantically annotated corpus) have obtained better results than unsupervised methods on small sets of selected ambiguous words, or artificial pseudo-words. Many standard ML algorithms for supervised learning have been applied, such as: Decision Lists \[Yarowsky, 1994, Agirre and Martínez, 2000\], Neural Networks \[Towell and Voorhees, 1998\], Bayesian learning \[Bruce and Wiebe, 1999\], Exemplar-Based learning \[Ng, 1997a\], and Boosting \[Escudero et al., 2000a\], etc. Further, in \[Mooney, 1996\] some of the previous methods are compared jointly with Decision Trees and Rule Induction algorithms, on a very restricted domain.

Although some comparative studies between alternative algorithms have been reported \[Mooney, 1996, Ng, 1997a, Escudero et al., 2000a, Escudero et al., 2000b\], none of them addresses the issue of the portability of supervised ML algorithms for WSD, i.e. to test whether the accuracy of a system trained on a certain corpus can be extrapolated to other corpora or not. We think that the study of the domain dependence of WSD —in the style of other studies devoted to parsing \[Sekine, 1997, Ratnaparkhi, 1999\]— is needed to assess the validity of the supervised approach, and to determine to which extent a pre–process of tuning is necessary to make real WSD systems portable. In this direction, this work compares five different ML algorithms and explores their portability and tuning ability by training and testing them on different corpora.

## 2 Learning Algorithms Tested

#### Naive-Bayes (NB).

Naive Bayes is intended as a simple representative of statistical learning methods. It has been used in its most classical setting \[Duda and Hart, 1973\]. That is, assuming independence of features, it classifies a new example by assigning the class that maximizes the conditional probability of the class given the observed sequence of features of that example.

Model probabilities are estimated during training process using relative frequencies. To avoid the effect of zero counts when estimating probabilities, a very simple smoothing technique has been used, which was proposed in \[Ng, 1997a\].

Despite its simplicity, Naive Bayes is claimed to obtain state–of–the–art accuracy on supervised WSD in many papers \[Mooney, 1996, Ng, 1997a, Leacock et al., 1998\].

Exemplar-based Classifier (EB). In exemplar, instance, or memory–based learning \[Aha et al., 1991\] no generalization of training examples is performed. Instead, the examples are stored in memory and the classification of new examples is based on the classes of the most similar stored examples. In our implementation, all examples are kept in memory and the classification of a new example is based on a $`k`$–NN (Nearest–Neighbours) algorithm using Hamming distance to measure closeness. For $`k`$’s greater than 1, the resulting sense is the weighted majority sense of the $`k`$ nearest neighbours —where each example votes its sense with a strength proportional to its closeness to the test example.

Exemplar–based learning is said to be the best option for WSD \[Ng, 1997a\]. Other authors \[Daelemans et al., 1999\] point out that exemplar–based methods tend to be superior in language learning problems because they do not forget exceptions.

#### SNoW: A Winnow–based Classifier.

SNoW stands for Sparse Network Of Winnows, and it is intended as a representative of on–line learning algorithms. In the SNoW architecture there is a Winnow \[Littlestone, 1988\] node for each class, which learns to separate that class from all the rest. In this paper, our approach to WSD using SNoW follows that of \[Escudero et al., 2000c\].

SNoW is proven to perform very well in high dimensional domains, where both, the training examples and the target function reside very sparsely in the feature space \[Roth, 1998\], e.g: text categorization, context–sensitive spelling correction, WSD, etc.

#### Decision Lists (DL).

In this setting, Decision Lists are ordered lists of features extracted from the training examples and weighted by a log–likelihood measure \[Yarowsky, 1994\]. The aproximation described in \[Agirre and Martínez, 2000\] has been fully used (using also their pruning and smoothing techniques).

Decision Lists were one of the most succesful systems on the 1st edition of the Senseval competition \[Kilgarriff and Rosenzweig, 2000\].

#### LazyBoosting (LB).

The main idea of boosting algorithms is to combine many simple and moderately accurate hypotheses (called weak classifiers) into a single, highly accurate classifier. 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.

LazyBoosting \[Escudero et al., 2000a\], is a simple modification of the AdaBoost.MH algorithm \[Schapire and Singer, to appear\], which consists of reducing the feature space that is explored when learning each weak classifier. More specifically, a small proportion of attributes are randomly selected and the best weak rule is selected only among them. This modification significantly increases the efficiency of the learning process with no loss in accuracy.

## 3 Setting

The set of comparative experiments has been carried out on a subset of 21 words of the DSO corpus, which is a semantically annotated English corpus collected by Ng and colleagues \[Ng and Lee, 1996\], and available from the Linguistic Data Consortium (LDC)111 http://www.ldc.upenn.edu/. Each word is treated as a different classification problem. They are 13 nouns (age, art, body, car, child, cost, head, interest, line, point, state, thing, work) and 8 verbs (become, fall, grow, lose, set, speak, strike, tell). The average number of senses per word is close to 10 and the number of training examples is close to 1,000.

The DSO corpus contains sentences from two different corpora, namely Wall Street Journal (WSJ) and Brown Corpus (BC). Therefore, it is easy to perform experiments about the portability of alternative systems by training them on the WSJ part (A part, hereinafter) and testing them on the BC part (B part, hereinafter), or vice-versa.

Two kinds of information are used to train classifiers: local and topical context. The former consists of the words and part-of-speech tags appearing in a window of $`\pm `$ 3 items around the target word, and collocations of up to three consecutive words in the same window. The latter consists of the unordered set of content words appearing in the whole sentence.

## 4 Experiments

### 4.1 Comparing the five approaches

The five algorithms, jointly with a naive Most-Frequent-sense Classifier (MFC), have been tested on 7 different combinations of training–test sets222The combinations of training–test sets are called: A+B–A+B, A+B–A, A+B–B, A–A, B–B, A–B, and B–A, respectively. In this notation, the training set is placed at the left hand side of symbol “–”, while the test set is at the right hand side. For instance, A–B means that the training set is corpus A and the test set is corpus B. The symbol “$`+`$” stands for set union.. Accuracy figures, averaged over the 21 words, are reported in table 1. The comparison leads to the following conclusions:

LazyBoosting outperforms the other three methods in all tests. The difference is statistically significant in all cases except when comparing LazyBoosting to the Exemplar Based approach in the case marked with an asterisk333Statistical tests of significance applied: McNemar’s test and 10-fold cross-validation paired Student’s $`t`$-test at a confidence value of 95% \[Dietterich, 1998\]..

Extremely poor results are observed when testing the portability of the systems. Restricting to LazyBoosting results, we observe that the accuracy obtained in A–B is 47.1% while the accuracy in B–B (which can be considered an upper bound for LazyBoosting in B corpus) is 59.0%, that is, a drop of 12 points. Furthermore, 47.1% is only slightly better than the most frequent sense in corpus B, 45.5%.

Apart from accuracy figures, the observation of the predictions made by the five methods on the test sets provides interesting information about the comparison of the algorithms. Table 2 shows the agreement rates and the Kappa ($`\kappa `$) statistics444The Kappa statistic $`k`$ \[Cohen, 1960\] is a better measure of inter–annotator agreement which reduces the effect of chance agreement. It has been used for measuring inter–annotator agreement during the construction of some semantic annotated corpora \[Véronis, 1998, Ng et al., 1999\]. between all pairs of methods in the A+B–A+B case. ‘DSO’ stands for the annotation of DSO corpus, which is taken as the correct. Therefore the agreement rate with DSO contains the accuracy results previously reported. Some interesting conclusions can be drawn from those tables:

#### 1.

NB obtains the most similar results with regard to MFC in agreement rate and Kappa values in all tables. The agreement ratio is 76%, that is, more than 3 out of 4 times it predicts the most frequent sense.

#### 2.

LB obtains the most similar results with regard to DSO (accuracy) in agreement rate and Kappa values, and it has the less similar Kappa and agreement values with regard to MFC . This indicates that LB is the method that better learns the behaviour of the DSO examples.

#### 3.

The Kappa values are very low. But, as it is suggested in \[Véronis, 1998\], evaluation measures, such as precision and recall, should be computed relative to the agreement between the human annotators of the corpus and not to a theoretical 100%. It seems pointless to expect more agreement between the system and the reference corpus than between the annotators themselves. Contrary to the intuition that the agreement between human annotators should be very high in the WSD task, some papers report surprisingly low figures. For instance, \[Ng et al., 1999\] reports an accuracy rate of 56.7% and a Kappa value of 0.317 when comparing the annotation of a subset of the DSO corpus performed by two independent research groups555A Kappa value of 1 indicates perfect agreement, while 0.8 is considered as indicating good agreement \[Carletta, 1996\].. Similarly, \[Véronis, 1998\] reports values of Kappa near to zero when annotating some special words for the ROMANSEVAL corpus666 http://www.lpl.univ-aix.fr/projects/romanseval . From this point of view, the Kappa values of 0.44 achieved by LB in A+B–A+B could be considered excellent results. Unfortunately, the subset of the DSO corpus and that used in this report are not the same and, therefore, a direct comparison is not possible.

### 4.2 About the tuning to new domains

This experiment explores the effect of a simple tuning process consisting of adding to the original training set a relatively small sample of manually sense tagged examples of the new domain. The size of this supervised portion varies from 10% to 50% of the available corpus in steps of 10% (the remaining 50% is kept for testing). Results indicate that: LazyBoosting is again superior to their competitors.

Summarizing, the results obtained show that for Naive Bayes, Exemplar Based, SNoW and Decision Lists methods it is not worth keeping the original training examples. Instead, a better (but disappointing) strategy would be simply using the tuning corpus. However, this is not the situation of LazyBoosting, for which a moderate (but consistent) improvement of accuracy is observed when retaining the original training set.

We observed that part of the poor results obtained is explained by: 1) Corpus A and B have a very different distribution of senses, and, therefore, different a–priori biases; Furthermore, 2) Examples of corpus A and B contain different information, and, therefore, the learning algorithms acquire different (and non interchangeable) classification cues from both corpora. The study of the rules acquired by LazyBoosting from WSJ and BC helped understanding the differences between corpora. On the one hand, the type of features used in the rules were significantly different between corpora, and, additionally, there were very few rules that apply to both sets; On the other hand, the sign of the prediction of many of these common rules was somewhat contradictory between corpora \[Escudero et al., 2000c\].

### 4.3 About the training data quality

The observation of the rules acquired by LazyBoosting also could help improving data quality. 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 LazyBoosting as a way to improve the training corpus.

A preliminary experiment has been carried out in this direction by studying the rules acquired by LazyBoosting from the training examples of word state. The manually revision of the 50 highest scored rules allowed us to identify a high number of noisy training examples –there were 11 of 50 tagging errors–, and, additionally, 17 examples of 50 not coherently tagged, probably due to the too fine grained or not so clear distinctions between the senses involved in these examples. Thus, there were 28 of 50 examples with some problem, that is more than 1 of each two cases have a problem.

## 5 Conclusions and Future Work

This work reports a comparative study of five ML approaches to WSD, and focuses on studying their portability. The main conclusions are:

LazyBoosting algorithm outperforms the other four state-of-the-art supervised ML methods in all domains tested. Furthermore, this algorithm shows better properties when is tuned to new domains.

Portability is a very important issue that has been paid little attention up to the present. In this paper we show that a process of tuning to the domain of application is required to assure the portability of WSD systems (at least if the learning–testing corpora differ so as BC and WSJ do). This evidence questions the idea of “robust broad-coverage WSD” introduced by \[Ng, 1997b\], in which a supervised system trained on a large enough corpora (say a thousand examples per word) should provide fairly accurate disambiguation on any corpora. To determine the viability of the supervised approach to WSD we belief that a serious effort should be devoted to study the problem of obtaining representative enough training corpora at a reasonable cost.

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

#### 1.

Since most of the knowledge learned from a domain is not useful when changing to a new domain, further investigation is needed on tuning strategies, specially on those using non-supervised algorithms.

#### 2.

It has been noted 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. It could provide the methodologies to automatic verify the semantic annotation of corpora and the grouping of senses.

#### 3.

Moreover, the inspection of the rules learned by LazyBoosting could provide evidence about similar behaviours of a–priori different senses. This type of knowledge could be useful to perform clustering of too fine-grained or artificial senses.


text:
# Origin of complexity in multicellular organisms

## Abstract

Through extensive studies of dynamical system modeling cellular growth and reproduction, we find evidence that complexity arises in multicellular organisms naturally through evolution. Without any elaborate control mechanism, these systems can exhibit complex pattern formation with spontaneous cell differentiation. Such systems employ a ‘cooperative’ use of resources and maintain a larger growth speed than simple cell systems, which exist in a homogeneous state and behave ’selfishly’. The relevance of the diversity of chemicals and reaction dynamics to the growth of a multicellular organism is demonstrated. Chaotic biochemical dynamics are found to provide the multi-potency of stem cells.

Multicellular organisms consist of differentiated cell types, with rather complex biochemical dynamics exhibited by complex metabolic and genetic networks. Through the course of development, cells differentiate into several types and often form complex patterns. The molecular mechanisms existing of each stage of development have been elucidated experimentally . However, it is still not clear why multicellular organisms should have such complexity, nor why such inhomogeneities in cell types and patterns are common. These are not trivial problems , since a simple biochemical network would be sufficient (and perhaps more fit) to produce identical cells rapidly and faithfully. Here we give an answer to the problem of why multicellular organisms in general have diverse cell types with complex patterns and dynamics.

Indeed, by considering dynamical systems of appropriate biochemical networks, it is possible to show that inhomogeneous patterns with diverse cell types can emerge. Such work was pioneered by Turing , and extended in Refs. . Differentiation into several cell types has also been studied by using random genetic networks . Still, it is not known how biochemical and genetic networks allowing for diversity are evolved.

Any theory accounting for such cellular diversity requires a specific choice of the genetic and biochemical reaction networks and parameters. Then, to explain the ubiquitous nature of cellular diversity in multicellular organisms, we must understand how such reaction dynamics allowing for cell differentiation can evolve, without postulating a finely tuned mechanism. Here we study the relationship between the growth of multicellular organisms and some characteristics of intra-cellular dynamics, to understand the origin of cellular diversity. Since the question we address is rather general, we seek an answer that does not rely on detailed knowledge of specific cellular processes in existing organisms. Instead, we adopt dynamical systems models that display only essential features of the developmental process. In a minimal model of cellular dynamics, we include only intra-cellular biochemical reactions with enzymes, simple cell-cell interactions through diffusion, and cell division as a result of biochemical reactions within each cell. By studying a class of models with this general and minimal content, we show that cell differentiation from a stem cell and development producing a complex pattern are natural consequences of evolution.

Model: First, cells are assumed to be completely surrounded by a one-dimensional medium. The state of a cell $`i`$ is assumed to be characterized by the cell volume and $`c_i^{(m)}(t)`$, the concentrations of $`k`$ chemicals($`m=1,\mathrm{},k`$). The concentrations of chemicals change as a result of internal biochemical reaction dynamics within each cell and cell-cell interactions communicated through the surrounding medium. The corresponding chemical concentration in the medium is denoted by $`C^{(m)}(x,t)`$, where $`x`$ denotes the position along the one-dimensional axis. We use a one-dimensional model only for its tractability; conclusions we draw in this case are consistent with the result of preliminary simulations of a two-dimensional model.

Internal reaction dynamics: For the internal chemical reaction dynamics, we choose a catalytic network among the $`k`$ chemicals, represented by a matrix $`Con(\mathrm{},j,m)`$ which takes on unity when the reaction from the chemical $`\mathrm{}`$ to $`m`$ is catalyzed by $`j`$, and 0 otherwise. The rate of increase of $`c_i^{(m)}(t)`$ (and decrease of $`c_i^{(\mathrm{})}(t)`$) through this reaction is given by $`c_i^{(\mathrm{})}(t)(c_i^{(j)}(t))^\alpha `$, where $`\alpha `$ is the degree of catalyzation($`\alpha =2`$ in most simulations here). Each chemical has several paths to other chemicals, and thus a complex reaction network is formed.

Besides, we take into account the change in the volume of a cell, that varies as a result of transportation of chemicals into the cell from the environment. For simplicity, we assume that the volume is proportional to the sum of chemicals in the cell. The concentrations of chemicals are diluted as a result of an increase in the volume of the cell. With the above assumption, this dilution effect is tantamount to imposing the restriction $`_{\mathrm{}}c_i^{(\mathrm{})}=const.`$

Of course, real biochemical processes within a cell are much more complicated. Instead of taking such details into account, we employ this simple model, and consider a variety of reaction networks created randomly, to elucidate a general relationship between the growth of cells and cellular dynamics.

Cell-cell interactions through a medium: Cells interact with each other through the transport of chemicals out of and into the surrounding medium. As a minimal case, we consider only indirect cell-cell interactions through diffusion of chemicals via the medium. The diffusion coefficient should depend on the chemical. Here, we assume that there are two types of chemicals, one which can penetrate the membrane and one which can not. We use the notation $`\sigma _m`$, which takes the value 1 if the chemical $`c_i^{(m)}`$ is penetrable, and 0 otherwise.

To sum up all these process, the dynamics of chemical concentrations in each cell is represented as follows:

$$dc_i^{(\mathrm{})}(t)/dt=\mathrm{\Delta }c_i^{(\mathrm{})}(t)c_i^{(\mathrm{})}(t)\underset{l=1}{\overset{k}{}}\mathrm{\Delta }c_i^{(\mathrm{})}(t),$$
(1)
with

$`\mathrm{\Delta }c_i^{\mathrm{}}(t)={\displaystyle \underset{m,j}{}}Con(m,j,\mathrm{})e_1c_i^{(m)}(t)(c_i^{(j)}(t))^\alpha `$
$`\text{ }{\displaystyle \underset{m^{},j^{}}{}}Con(\mathrm{},j^{},m^{})e_1c_i^{(\mathrm{})}(t)(c_i^{(j^{})}(t))^\alpha `$
$`+\sigma _{\mathrm{}}D(C^{(\mathrm{})}(p_i^x,t)c_i^{(\mathrm{})}(t)).`$ (2)
The variable $`p_i^x`$ denotes the location of the $`i`$-th cell. The second term in Eq. (1) represents the dilution effect by changing the volume of the cell. On the other hand, the diffusion of chemicals in the medium are governed by the following equation for $`C^{(\mathrm{})}`$:

$`C^{(\mathrm{})}(x,t)/t=\stackrel{~}{D}^2C^{(\mathrm{})}(x,t)`$
$`+{\displaystyle \underset{i}{}}\delta (xp_i^x)\sigma _{\mathrm{}}D(C^{(\mathrm{})}(x,t)c_i^{(\mathrm{})}(t))`$ (3)
where the boundary condition is chosen to be $`C(0,t)=C(x_{max},t)=const.`$, $`\stackrel{~}{D}`$ is the diffusion constant of the environment, and $`x_{max}`$ denotes the extent of the medium. This boundary condition can be interpreted as a chemical bath outside of the medium, which supplies those penetrable chemicals that are consumed to the medium via a constant flow to the cell.

Cell Division:

Each cell takes penetrable chemicals from the medium as the nutrient, while the reaction in the cell transforms them to unpenetrable chemicals which construct the body of the cell. As a result of these reactions, the volume of the cell is increased. In this model, the cell is assumed to divide into two almost identical cells when the volume of the cell is doubled.

During this division process, all chemicals are almost equally divided, with tiny random fluctuations (e.g., $`10^6`$ $`c_i^{(\mathrm{})}`$). The case of equal division is assumed, since we do not intend to introduce an elaborate mechanism, while the fluctuations are introduced because we wish to study development processes that are robust with respect to molecular fluctuations. After cell division, two daughter cells appear around their mother cell’s position, and the positions of all cells are adjusted so that the distances between adjacent cells are 1. As a result, the total length of the chain of cells increases.

As the initial state, a single cell, whose chemical concentrations are determined randomly, is placed. According to the process described above, cells divide to form a chain. Of course, the behavior of the model depends on each intra-cellular reaction network. We have carried out simulations of the model by considering 800 different reaction networks, generated randomly. Throughout the paper, the number of chemical species $`k`$ is 20, and each chemical has 6 reaction paths to other chemicals, chosen randomly. Each chemical reaction path is catalized by other (or the same) chemical, again chosen randomly. Among the 20 chemicals, 3 chemicals can penetrate cell membranes. The parameter are fixed at $`e_1=1.0,D=1.0,\stackrel{~}{D}=2.0`$, and $`x_{max}=500`$.

As results, we found that each growth curve using different reaction network can be classified into two classes: (I) ‘fast’ growth in which the increase of cell number grows exponentially in time $`t`$, and (II) ‘slow’ growth in which the cell number grows linearly in time. Under the parameters presented above, approximately 5% of randomly chosen reaction networks show the case (I) behavior. These two classes, indeed, are also distinguished by the nature of the corresponding cellular dynamics.

In case (II), the chemical compositions and dynamics of all cells are identical. These dynamics fall into either a fixed point or a limit-cycle attractor. In this situation, only a few cells around the edges of the chain can divide. Since cells are not differentiated, chemicals required for cell growth are identical for all cells. Thus, once the cells at the edges consume the required resources, the remaining cells can no longer grow. This is the reason for the linear growth.

In case (I) with exponential growth, it is found that the chemical reaction dynamics of the cells are more complex than in case (II). The microscopic differences between the chemicals in two daughter cells are amplified through the internal biochemical dynamics and the cell-cell interaction, leading to chaotic chemical dynamics. For most such cases, the cells differentiate into various cell types that are defined by distinct chemical dynamics and compositions (see Fig.1). Even though no external mechanism of differentiation is implemented, the instability that results from the intra-cellular dynamics and the cell-cell interactions brings about transitions to various cell types . Indeed, this differentiation is a general feature of a system of interacting units that each possesses some non-linear internal dynamics , as has been clarified by isologous diversification theory .

In case (I), the division of cells is not restricted to the edge of the chain. There is a flow of the nutritive chemicals into the inside of the chain, that can maintain the growth of internal cells. This flow is sustained by the diffusion between cells possessing different chemical compositions and exhibiting different phases of chemical oscillations. Here, the capability for cell division is also differentiated as the development progresses. The total increase in cell number is due to the division of certain type(s) of cells, and most other cell types stop dividing.

In the developmental processes in case (I), initial cell types exhibit transitions to other types. Cells of the initial cell types either proliferate or switch to other types stochastically. They can be regarded as a stem cell . The dynamics of a stem-type cell, that can produce different cell types after divisions, exhibit chaotic oscillation(see Fig.1, and also). The type of differentiated cells maintain their type after divisions.

Next, we compare the growth of a single cell with that of an ensemble of cells. In Fig.2 the growth speeds of a single cell and an ensemble of cells are plotted. Here each point corresponds to a different reaction network.

The points around the peak of the growth for an ensemble correspond to case (I) of exponential growth. Here, the growth speed of a single cell is not large. In each cell, a variety of chemicals coexist, supporting complex reaction dynamics and cell differentiation. In case (I), organisms with cellular diversity, plotted by green points, have a larger growth speed of an ensemble than those without diversity. Indeed, in the former case, cells differentiate in the use of nutrients to take them efficiently.

In case (II), there are much simpler intra-cellular reaction processes, with only a few auto-catalytic reactions used dominantly, that can produce the rapid replication of a single cell. In this case, the growth speed of a single cell is often large (represented by some of the blue points in Fig.2), while the growth speed of an ensemble always remains small. In some sense, simple cells with rapid growth are ‘selfish’: Although such simple cells with low diversity of chemical species can exhibit large growth speeds as single cells, they cannot grow cooperatively, and their growth speeds as ensembles are suppressed because of strong competition for resources.

The developmental process presented in case (I) is irreversible. Initially, cells have complex chaotic internal dynamics and a variety of chemicals. They have the potential to differentiate into cell types with simpler cellular dynamics, for example, with a fixed-point and regular oscillation (see Fig.1 as an example). This type of cell with simpler dynamics can produce cells of the same type or stop dividing. Hence, the loss of multipotency, known to exist in the developmental process of real organisms , is explained in terms of the decrease in time of diversity in the intra-cellular dynamics and chemicals. Indeed, the decrease in complexity of dynamics with the loss of multipotency has been confirmed quantitatively, for example by computing the Kolmogorov-Sinai(KS) entropy of the intra-cellular dynamics. Using the data in Fig.2, we have found that case (I) has a positive KS entropy while for the case (II) it is zero. Furthermore, there is positive correlation between the KS entropy and the growth speed as an ensemble. The decrease of KS entropy in going from a stem cell to other differentiated cells has also been confirmed. For example, the KS entropy of the stem-type “red” cells in Fig.1 is approximately $`2.4\times 10^4`$, while it is $`3.1\times 10^5`$ for “green”, $`4.5\times 10^5`$ for “blue”, less than $`1.0\times 10^5`$ for “yellow” cells.

Our results are robust against the change in model parameters, as long as the internal reaction and intra-cellular diffusion terms have a comparable order of magnitude. The results are also independent of the details of the model, in particular, of the choice of catalyzation degree $`\alpha =1`$ or 3. The same two classes and the same relation between the growth and cellular diversity are obtained, as long as the number of chemicals is sufficient (say for $`k>10`$) and number of the reaction paths is in the medium range (e.g., 3$``$9 for each chemical at $`k=20`$; otherwise, the intra-cellular dynamics fall onto a fixed point for most cases without differentiation).

To sum up, our study has provided evidence that an ensemble of cells with a variety of dynamics and stable states (cell types) has a larger growth speed than an ensemble of simple cells with a homogeneous pattern, because of the greater capability of the former to transport and differentiation in the use of nutritive chemicals. Note that no elaborate mechanism is required for the appearance of such heterogeneous cell ensembles. Some fraction of the randomly chosen biochemical networks we considered exhibit dynamics sufficiently complex to allow for spontaneous cell differentiation.

Our result suggests that complexity of multicellular organisms with differentiated cell types is a necessary course in evolution, once a multicellular unit emerges from cell aggregates. In fact, by carrying out the evolution experiment numerically, with mutation to reaction networks and selection of the cell ensembles with higher growth speed, we have confirmed that cells of the case (I) emerge and survive through evolution.

Our result concerning the relationship between the diversity of chemicals and dynamics and the growth speed of a single cell and ensemble provides experimentally testable predictions. Since even primitive organisms such as Anabena  and Volvox  exhibit differentiation in cell types and some spatial pattern, the relationship can be verified. In fact, for a mutant of Volvox that possesses only homogeneous cells, the growth becomes slower in comparison to the wild-type .

Chaotic intra-cellular dynamics and the diversity of chemicals present in a stem cell are also experimentally verifiable. Decrease of diversity in chemical composition and of complexity in their temporal variation is expected with the decrease of multipotency of a cell.

We would like to thank Tetsuya Yomo for stimulating discussions. This research was supported by Grants-in-Aid for Scientific Research from the Ministry of Education, Science, and Culture of Japan (11CE2006)