Reliability Measurement without Limits

In computational linguistics, a reliability measurement of 0.8 on some statistic such as is widely thought to guarantee that hand-coded data is fit for purpose, with 0.67 to 0.8 tolerable, and lower values suspect. We demonstrate that the main use of such data, machine learning, can tolerate data with low reliability as long as any disagreement among human coders looks like random noise. When the disagreement introduces patterns, however, the machine learner can pick these up just like it picks up the real patterns in the data, making the performance figures look better than they really are. For the range of reliability measures that the field currently accepts, disagreement can appreciably inflate performance figures, and even a measure of 0.8 does not guarantee that what looks like good performance really is. Although this is a commonsense result, it has implications for how we work. At the very least, computational linguists should look for any patterns in the disagreement among coders and assess what impact they will have.

Introduction
In computational linguistics, 0.8 is often regarded as some kind of magical reliability cut-off guaranteeing the quality of hand-coded data (e.g., Reithinger and Kipp 1998;Shriberg et al. 1998;Galley et al. 2004), with 0.67 to 0.8 tolerable-although it is as often honored in the breech as in the observance. The argument for the meaning of 0.8 arises originally from Krippendorff (1980, page 147), in a comment about practice in the field of content analysis. He states that correlations found between two variables using their hand-coded values "tend to be insignificant" when the hand-codings have a reliability below 0.8. He uses a specific reliability statistic, α, for his measurements, but Carletta (1996) implicitly assumes kappa-like metrics are similar enough in practice for the rule of thumb to apply to them as well. A detailed discussion on the differences and similarities of these, and other, measures is provided by Krippendorff (2004); in this article we will use Cohen's κ (1960) to investigate the value of the 0.8 reliability cut-off for computational linguistics.
Modern computational linguists use data in a completely different way from 1970s content analysts. Rather than correlating two variables, we use hand-coded data as training and test material for automatic classifiers. The 0.8 rule of thumb is irrelevant for this purpose, because classifiers will be affected by disagreement differently than correlations. Furthermore, Krippendorff's argument comes with a caveat: the disagreement must be due to random noise. For his case of correlations, any patterns in the disagreement could accidentally bolster the relationship perceived in the data, leading to false results. To be sure that data is fit for the intended purpose, Krippendorff advises the analyst to look for structure in the disagreement and consider how it might affect data use. Although computational linguists have rarely followed this advice, it is just as relevant to us. Machine-learning algorithms are designed specifically to look for, and predict, patterns in noisy data. In theory, this makes random disagreement unimportant. More data will yield more signal and the learner will ignore the noise. However, as Craggs and McGee Wood (2005) suggest, this also makes systematic disagreement dangerous, because it provides an unwanted pattern for the learner to detect. We demonstrate that machine learning can tolerate data with a low reliability measurement as long as the disagreement looks like random noise, and that when it does not, data can have a reliability measure commonly held to be acceptable but produce misleading results.

Method
To explain what is wrong with using 0.8 as a cut-off, we need to think about how data is used for classification tasks. Consider Figure 1, which shows a relation between some features A and a class label B. Learning labels from a set of features is a common task in computational linguistics; for instance, in Shriberg et al. (1998), which assumes a pre-existing dialogue act segmentation, the labels are dialogue act types, and they are learned from automatically derived prosodic features. In this way of using data, only one of the variables-the output dialogue act label-is hand-coded. In the figure, the real relationship between prosody and dialogue act label is shown on the left; R relates the prosodic features A to the output act B.

Figure 1
Hand-coded target labels are used to train classifiers to automatically predict those labels from features.
In theory, there is one correct label for any given act. However, in practice human coders disagree, choosing different labels for the same act (sometimes even with divergences that make one question whether there is one correct answer). The data actually available for analysis is shown in the middle of the figure. Here, the automatic features, A, are the same as before, but there are multiple, possibly differing labels for the same act, B obs , coming from different human annotators. Finally, on the right the figure shows the classifier. It takes the same prosodic features A and uses them to predict a dialogue act label B pred on new data, using the relationship learned from the observed data, R ML . Projects vary in how they choose data from which to build the classifier when coders disagree, but whatever they do is colored by the observations they have available to them. We often think of reliability assessment as telling us how much disagreement there is among the human coders, but the real issue is how their individual interpretations of the coding scheme make R ML differ from R.
There is a problem that arises for anyone using this methodology. Without the "real" data, it is impossible to judge how well the learned relationship reflects the real one. Classification performance for B pred can only be calculated with respect to the "observed" data B obs . In this article, we surmount this problem by simulating the real world so that we can measure the differences between this "observed" performance and the "real" performance. Our simulation uses a Bayesian network (Pearl 1988) to create an initial, "real" data set with 3,000 samples of features (A) and their corresponding target labels (B). For simplicity, we use a single five-valued feature and five possible labels. The relative label frequencies vary between 17% and 25%. This gives us a small amount of variation around what is essentially equally distributed data. We corrupt the labels (B) to simulate the "hand-coded" observed data (B obs ) corresponding to the output of a human coder, and then train a neural network constructed using the WEKA toolkit (Witten and Frank 2005) on 2,000 samples from B obs . Finally, we calculate the neural network's performance twice, using as test data either the remaining 1,000 samples from B obs or the initial, "real" versions of those same 1,000 samples.
There are three ways in which we need to vary our simulation in order to be systematic. The first is in the strength of the relationship between the features the machine learner takes as input and the target labels, which we achieve simply by changing the probabilities in the Bayesian network that creates the data set. In the simulation, we vary the strength of the relationship in eight graded steps. 1 The second is in the amount of disagreement we introduce when we create the observed data (B obs ). We create 200 different versions of the hand-coded data that cover a range of values from κ = 0 to 1 We use Cramer's phi to measure the strength of a relationship. Cramer's phi is defined as with N the number of samples and df smaller the smallest degree of freedom of the two involved variables, and is a measure of association for nominal variables with more than two values. It can be "considered like a correlation coefficient" (Aron and Aron 2003) that takes data set size into account and can easily be derived for a Bayesian network from the priors and the conditional probability tables. We varied the strength of the network between φ c = 0.06 and φ c = 0.45. Following Cohen (1988), for a five-way distinction Aron and Aron (page 527) would consider 0.06 to represent a small real relationship-that is, one with not much effect-and 0.3, a large one. Thus we describe 0.06 as "weak," 0.45 as "very strong," and intermediate points as "moderate" and "strong." It is an open question what strengths of relationships actually occur in computational linguistics data, although there may be no point in learning a relationship that's too strong.

Figure 2
Machine-learning performance obtained on annotations with noise-like disagreements for (a) weak (φ c = 0.06), (b) moderate (φ c = 0.20), (c) strong (φ c = 0.32), and (d) very strong (φ c = 0.45) relationships between the features and labels. κ = 1, by introducing a varying amount of observation errors in the simulated coding process. 2 The third is in the type of disagreement with which we degrade the real data to create the observed data (B obs ), representing the types of coding errors the human annotators make. Again for simplicity, we describe the effects of both random errors and the overuse of a single coding label. Figure 2 shows how a neural network performs when coders make random mistakes in their coding task, that is, for noise-like disagreement, for the cases of (a) weak, (b) moderate, (c) strong, and (d) very strong relationships between the features (A) and labels (B). Here, the y axis shows "accuracy," or the percentage of samples in the test data for which the network chooses the correct label. The x axis varies the amount of coder errors in the data to correspond to different κ values, with the two black lines marking the values of κ = 0.67 and κ = 0.8.

The Case of Noise
Look first at the series depicted as a line. It shows accuracy measured by using the "observed" version of the test data, which is how testing is normally done. For each relationship strength, as κ increases, so does accuracy. In all cases, at κ = 0 (that is, when the coders fail to agree beyond what one would expect if they were all choosing their labels randomly) accuracy is at 20%, which is what one would expect if the classifier were choosing randomly as well. For any given κ value, the stronger the underlying relationship, the more benefit the neural network can derive from the data. Now look at the other of the two series, depicted as small squares. It shows accuracy measured by using the "real" version of the data. Interestingly, the "real" performance, that is, the power of the learned model to predict reality, is higher than performance as measured against the observed data. This is because for some samples, the classifier's predictions are correct, but because the observations contain errors, the test data actually gets them wrong. The stronger the relationship in the real data, the more marked this effect becomes. The neural network is able to disregard noise-like coding errors at very low κ values simply because the errors contain no patterns for it to learn.

The Case of Overusing a Label
Now consider the case where instead of random coding errors, the coder over-uses the least frequent one of the five labels for B. Figure 3 shows the results for this kind of coding error. Remember that in the graphs, the series depicted as a line shows the observed performance of the classifier-that is, performance as it is usually measured. The two black lines again mark the κ values of interest (κ = 0.67 and κ = 0.8).
The graphs show an entirely different effect from the one obtained for noise-like coding errors: For lower values of κ, the observed performance is spuriously high. This makes perfect sense-κ is low when the pattern of label overuse is strong, and the neural network picks it up. When the observed data is used to test performance, some of the samples match not because the classifier gets the label right, but because it overuses the same label as the human coder. For data with a very strong correlation between the input features A and the output labels B, the turning point below which performance is spuriously high occurs at around κ = 0.55 (Figure 3d), a value the community holds to be pretty low but which is not unknown in published work. However, when the underlying relationship to be learned is moderate or strong (Figures 3b and 3c), the spuriously high results already occur for κ values commonly held to be tolerable. With a weak relationship, the turning point can occur at κ > 0.8 (Figure 3a).

Discussion
Our simulation highlights a danger for current practice in computational linguistics, among other fields. Overuse of a label is a realistic type of error for human annotators to make. For instance, imagine a coding scheme for dialogue acts that distinguishes backchannel utterances from utterances which indicate agreement. In data containing many utterances where the speech consists of "Yeah," individual coders can easily have a marked bias for either one of these two categories. Clearly, in actual coding, not all disagreement will be of one type, but will contain a mix of different systematic and noise-like errors. In addition, the underlying relationships that our systems attempt to learn vary in strength. This makes discerning the degree of danger more difficult, but does not change the substance of our argument.
Although the graphs we show are for a specific simulation, the general pattern we describe is robust. In particular, using α in place of κ does not markedly change the results; neither does increasing or decreasing the data set size. Our simulations and results are presented for a machine-learning context. However, that does not mean that other types of data use are immune to the problems we describe here. Other statistical uses of data will be affected in their own ways by the difference between structural and noise-like disagreement.

Implications
At the moment, much of the effort we devote to reliability measurement as a community is used to establish one or more overall reliability statistics for our data sets and to argue about which reliability statistic is most appropriate. Methodological discussions focus on questions such as how to force annotated data structures into the mathematical form necessary to calculate κ, or what effects certain aspects of the annotation have on the values of some metric rather than on possible uses of the resulting data (Marcu, Amorrortu, and Romera 1999;Di Eugenio and Glass 2004;Artstein and Poesio 2005). Computational linguists are of course aware that no overall reliability measure can give a complete story, but often fail to spend time analyzing coder disagreements further. Unfortunately, our results suggest that current practice is insufficient, at least where the data is destined to be input for a machine-learning process and quite possibly for other data uses as well. This complements observations of Artstein and Poesio: Besides the fact that many different ways of calculating reliability metrics lead to different values, which makes comparing them to a threshold difficult (Artstein and Poesio in press), the very idea of having any such single threshold in the first place turns out to be impossible to hold. Instead of worrying about exactly how much disagreement there is in a data set and how to measure it, we should be looking at the form the disagreement takes. A headline measurement, no matter how it is expressed, will not show the difference between noise-like and systematic disagreement, but this difference can be critical for establishing whether or not a data set is fit for the purpose for which it is intended.
To tease out what sort of disagreement a data set contains, Krippendorff suggests calculating odd-man-out and per-class reliability to find out which class distinctions are problematic (1980, page 150). Bayerl and Paul (2007) discuss methods for determining which factors (schema changes, coding team changes, etc.) were involved in causing poor annotation quality. Wiebe, Bruce, and O'Hara (1999) suggest looking at the marginals and how they differ between coders to find indications of whether disagreements are caused by systematic bias (as opposed to being random) and in which classes they occur. Although clearly useful techniques, none of these diagnostics is specifically designed to address the needs of machine learners which are designed to recognize patterns. Overusing a label is just one simple example of a type of systematic disagreement that adds unwanted patterns that a machine learner can find. Any spurious pattern could be a problem. For this reason, we should be looking specifically for patterns in the disagreement itself.
Our suggestion for one possible diagnostic technique is based on the following observation: If the disagreements between two coders contain no pattern, any test for association or correlation, when performed on only the disagreed items, should show no relation between the labels assigned by the two coders. For certain patterns in the disagreement, however, a correlation would show up. (To see this, consider the case where one coder tends to label rhetorical questions as yes/no-questions and the other coder assigns both labels correctly: If this happens often enough, tests for association would come up with a relation between the labels for the two coders for the disagreed items.) If the test shows a correlation, the disagreements add patterns for the machine learner to find. Unfortunately, the converse does not necessarily hold: It is possible that not all patterns that could be picked up by a machine learner will show up in correlations between disagreed items, for example because the amount of multiplyannotated data is too small. The computational linguistics community therefore needs to develop additional diagnostics for patterns in the coder disagreements.
It should go without saying that analysts will benefit from keeping how they intend to use the data firmly in mind at all times. As Krippendorff (2004, page 429) recommends, one should test reliability for the "distinctions that matter" and perform "suitable experiments of the effects of unreliable data on the conclusions." Patterns found for an overall coding scheme will not always affect every possible data use. For instance, we often build classifiers not for complete coding schemes, but for some subset of the labels or some "class map" that transforms the scheme into a smaller set of classes. In these cases, what is important is disagreement for the subset or transformation, not the entire scheme. Similarly, where classifier performance is reported per class, the reliability for that particular label will be the most important. Finally, different machinelearning algorithms may react differently to different kinds of patterns in the data and to combinations of patterns in different relative strengths. In complicated cases, perhaps the safest way to assess whether or not there is a problem with systematic disagreement is to run a simulation like the one we have reported but with the kind and scale of disagreement suspected of the data, and to use that to estimate the possible effects of unreliable data on the performance of machine-learning algorithms.


Postulates for measures of genuine multipartite correlations

A lot of research has been done on multipartite correlations. However, it seems strange that there is no definition of so called genuine multipartite correlations. In this paper we propose three reasonable postulates which each measure or indicator of genuine multipartite correlations (or genuine multipartite entanglement) should satisfy. We also introduce degree of correlations which gives partial characterization of multipartite correlations. Then, we show that covariance does not satisfy two postulates and hence, it cannot be used as an indicator of genuine multipartite correlations. Finally, we propose candidate for a measure of genuine multipartite correlations based on the work that can be drawn from local bath by means of a multipartite state.

I. INTRODUCTION
One of the most important problems in quantum information theory is the problem of quantifying correlations. Henderson and Vedral raised the problem of separating total correlations in a bipartite state into quantum and classical parts [1] (see also in this context [2][3][4]).They also proposed a measure of purely classical bipartite correlations . It was shown in [5] that there exist bipartite states which have almost maximal entanglement of formation and almost no mutual information and hence, almost no classical correlations. In a series of papers a thermodynamical approach to quantifying correlations was developed [6][7][8]. It is well known that bits of information can be used to extract work from a heat bath [9]. If we have a bipartite quantum state one can ask how much work can be extracted from the heat bath under different classes of operations. In particular quantum information deficit was defined. It is the difference between globally and locally (with the use of local operations and classical communication) extractable work from the heat bath. Recently it was shown that under some restricted scenario of work extraction there exist quantum states for which quantum information deficit is equal to quantum mutual information [10]. As a result, all correlations behave, as if they were exclusively quantum.
The problem of coexistence of quantum and classical correlations in multipartite systems was considered in [11]. It was shown that there exist n-qubit states which consist of an equal mixture of two W states with an odd number of qubits, for which n-party covariance defined as Cov(X 1 , ...X n ) = (X 1 − X 1 )...(X n − X n ) is zero for all choices of local observables X i and the state is genuinely entangled. Based on these observations the authors argued that genuine multipartite correlations can exist without classical correlations. However, the conclusion is based on assumption that covariance is an indicator of genuine multipartite correlations.
In this paper we formulate three postulates which any measure or indicator of genuine multipartite correlations should satisfy. We show that covariance does not satisfy two postulates when applied to more than two-partite systems. Our counterexamples will be the states considered in [11]. Hence, vanishing of covariance for multipartite states does not imply absence of genuine multipartite classical correlations but rather shows that covariance cannot be an indicator of genuine multipartite classical correlations. As a by-product we obtain a protocol of distillation of W states from a wide class of states (for distillation of W states from generic states see [12]).
The paper is organized as follows. In Section II, we formulate reasonable postulates for measures or indicators of genuine multipartite correlations and introduce degree of correlations. In Section III we show that covariance does not satisfy postulates. In Section IV we discuss relation between multipartite correlations and work extraction. In Section V we draw our conclusions.

II. GENUINE n-PARTITE CORRELATIONS
We do not know what it means that a state has genuine multipartite correlations. Hence we give reasonable postulates which each measure or indicator of genuine multipartite correlations should satisfy. In Subsection A we formulate postulates for genuine n-partite correlations of an n-partite state while in Subsection B we formulate postulates for genuine n-partite correlations of an arbitrary multipartite state and introduce degree of correlations as an indicator of genuine n-partite correlations for an arbitrary multipartite state. The postulates apply to correlations in general, hence, in particular, they apply also to genuine multipartite entanglement or genuine multipartite classical correlations. arXiv:0805.3060v2 [quant-ph] 16 Jan 2010 A. Genuine n-partite correlations of an n-partite state Each measure or indicator of genuine n-partite correlations for an n-partite state should satisfy the following postulates: Postulate 1. If an n-partite state does not have genuine n-partite correlations and one adds a party in a product state then the resulting n + 1 partite state does not have genuine n-partite correlations.
Postulate 2. If an n-partite state does not have genuine n-partite correlations then local operations and unanimous postselection (which mathematically correspond to the operation Λ 1 ⊗ Λ 2 ⊗ ... ⊗ Λ n where m is the number of particles and each Λ i is trace non-increasing operation acting on i-th party's subsystem) cannot generate genuine n-partite correlations.
Postulate 3. If an n-partite state does not have genuine n-partite correlations then if one party splits his system into two, i.e. sends part of his system to new party which is product with the remainder of the system then the resulting n + 1-partite state does not have genuine n + 1-partite correlations.
One can also require (compare Postulate 2) for each measure C(ρ) of genuine n-partite correlations that it does not increase on average under local opertions, i.e.
where E j i are Krauss operators acting on j-th subsystem satisfying i E j † i E j i ≤ I and p i1,i2,...,in = T r( It seems that this requirement should be added to postulates of Henderson and Vedral for measures of classical bipartite correlations [1].
Let us now propose a definition of genuine multipartite of correlations. Definition 1. A state of n particles has genuine npartite correlations if it is non-product in every bipartite cut.
Below we prove that genuine multipartite correlations defined above satisfy Postulates 1-3.
Observation 1. If genuine n-partite correlations are defined as in Definition 1 then they satisfy Postulates 1-3.
Proof. It is clear that genuine n-partite correlations satisfy Postulate 1.
To show that they satisfy Postulate 2 we observe that an n-partite state which does not have genuine n-partite correlations is of the form where ρ (n1) and ρ (n2) are states of n 1 and n 2 particles respectively (n 1 + n 2 = n). It is clear that this product form is preserved by the operation Λ 1 ⊗ Λ 2 ⊗ ... ⊗ Λ n .
To show that genuine n-partite correlations satisfy Postulate 3 we observe that a state which does not have genuine n-partite correlations after sending part of a one party's system is of the following forms where ρ (n1+1) , ρ (n2) , are states of n 1 +1 and n 2 particles respectively or where ρ (n1) , ρ (n2+1) are states of n 1 , n 2 + 1 particles respectively. Hence, we see that it does not have genuine n + 1-partite correlations.
Remark. The postulates apply also to entanglement. However, the Definition 1 does not. More precisely, it does apply to pure state entanglement, i.e. one can say that pure state has genuine multipartite entanglement iff it is nonproduct with respect to any bipartite cut. To obtain definition of genuine multipartite entanglement for mixed states, we proceed in a standard way [13], i.e. we say that a state ρ has genuine n-partite entanglement, if it is not a mixture of pure states that do not have genuine n-partite entanglement. Thus, to rule out correlations that do not represent entanglement, we can add fourth postulate, saying, that by mixing states which do not have n-partite entanglement, we cannot obtain genuine n-partite entanglement.

B. Degree of correlations
We introduce the concept of degree of correlations. We do not define it first but rather require that it should satisfy the following postulates: Postulate 1 . If one adds a party in a product state with the remainder of the system then degree of correlations cannot change.
Postulate 2 . Local operations and postselection cannot increase degree of correlations. In particular local unitary operations cannot change degree of correlations.
Postulate 3 . If one party splits his system into two, i.e. sends part of his system to new party who is not correlated with the remainder of the system, then degree of correlations can increase at most by 1.
Let us now propose a definition of degree of correlations.
Definition 2. A state has degree of correlations equal to n if there exists a subset of n particles which has genuine n-particle correlations and there does not exist a subset of m particles which has genuine m-particle correlations for any m > n.
Example 1. An n-partite state of the form has 2-, 3-, ...,n-partite correlations and degree of correlations equal to n. Example 2. An n-partite state of the form has only n-partite correlations and degree of correlations equal to n. It does not have 2-, 3-, ...,n − 1-partite correlations.
We can now find the form of a state which has degree of correlations equal to n.
Observation 2. A state which has degree of correlations equal to n is of the form: where ρ (n) , ρ (m1) ,..., ρ (m M ) are states of n, m 1 ,..., m M particles which are non-product in any bipartite cut and n ≥ m 1 , ..., m M . Proof. It is clear that arbitrary state can be written in this form for some n. The state has degree of correlations at least equal to n because the reduced state of first n particles is non-product in any bipartite cut. To show that degree of correlations cannot be greater than n it is enough to notice that if we trace some particles then if the state is product in some cut before we trace particles then it will be product in this cut after we trace particles.
Below we prove that the degree of correlations defined above satisfies Postulates 1 -3 .
Observation 3. If genuine n-partite correlations and degree of correlations are defined as in Definition 1 and Definition 2 then degree of correlations satisfies Postulates 1 -3 .
Proof. It is clear that degree of correlations satisfies Postulate 1 .
To show that it satisfies Postulate 2 we use the fact proved in Observation 1 that a state which has degree of correlations equal to n is of the form: where ρ (n) , ρ (m1) ,..., ρ (m M ) are states of n, m 1 ,..., m M particles respectively which are non-product in any bipartite cut and n ≥ m 1 , ..., m M . It is clear that this product form is preserved by the operation To show that degree of correlations satisfies Postulate 3 we observe that a state which has degree of correlations equal to n after sending part of a one party's system is of the following form where ρ (n+1) , ρ (m1) ,..., ρ (m M ) are states of n + 1, m 1 ,..., m M particles or where idi denotes the identity map acting on qubit i and Λ a ij denotes any completely positive map acting on qubits i and j. (c) The third and the fourth party send ancillas to the fifth and sixth party, respectively. If the initial state has degree of correlations less than n then the final state cannot have degree of correlations greater or equal to n + 2.
Using Postulates 1-3 we can prove the following Observation.
Observation 4. If the initial state has degree of correlations less than n then if the parties add k ancillas in a product state, perform local operations on their particles and their ancillas, and send ancillas to k new parties in such a way that each new party receives an ancilla from only one party then the final state cannot have degree of correlations greater or equal to n + k.
Proof. First, k parties add ancillas in a product state. Degree of correlations cannot change (Postulate 1 ). Next, k parties apply local operations to their original qubits and added ancillas. Degree of correlations cannot increase (Postulate 2 ). Finally, k parties send ancillas to k new parties. Degree of correlations can increase at most by k (it can increase by 1 for each sent ancilla) (Postulate 3 ).

III. COVARIANCE DOES NOT SATISFY POSTULATES
A. Postulate 2 Before we show that covariance does not satisfy Postulate 2 we present a purification protocol which allows the distillation of W states from certain mixed state. The protocol consists of two steps. In the first step each party performs a measurement on his particle -the so called local filtering [14][15][16]. The measurements performed by all parties are independent, i.e. they are not conditioned on the results of the measurements performed by other parties. In the second step the parties postselect a state. The postselected state can have fidelity with W state as close to 1 as one wants. However, the probability of distilling such a state decreases with fidelity. This protocol is a multipartite version of the so called quasi-distillation process [17,18].
Let us consider a state which is a mixture of W state and a normalized state ρ (1) with support contained in the 2 n − n − 1-dimensional Hilbert space spanned by all vectors which have 2 or more 1's, i.e.
Let each party perform a measurement described by the following Kraus operators The action of E ⊗n S on states with m 1's and n − m 0's is given by the following formula A similar result applies for all permutations of m 1's and n − m 0's. Hence, if each party obtains S as the result of the measurement then the post-measurement state is proportional to where ρ (1) is unnormalized state with the sum of eigenvalues less or equal to 1 and with support contained in the (2 n − n − 1)-dimensional Hilbert space orthogonal to the W state. The probability that each party obtains S as the result of the measurement is q = Tr(ρ ) > p.
The fidelity of the post-measurement state with the W state is: If is small then the fidelity is close to 1. Hence, with small probability it is possible to distill a state close to W . More precisely, the probability that we distill state W with fidelity F satisfies Consider now as example the n-partite state from [11] which is an equal mixture of W and W states consisting of an odd number of qubits, i.e., where and One can show that for this state all n-partite covariances vanish [11] (For completeness we show it in Appendix A.). Let the parties apply just described protocol to the state of Eq. (18) mixtures of two W states. If each party obtains S as the result of the measurement then the state is proportional to The probability that each party obtains S as the result of measurement is The fidelity of the post-measurement state with W state is: Let us take = 1 − 1 √ n and calculate the limit of q and F for large n. We have and More generally, the probability that we distill the state W with fidelity F is: In Fig. 2, we show how the probability of distillation depends on the fidelity of the distilled state for mixtures of two W states. For large n, the probability of obtaining a state close to W is close to 1 2 . Hence, asymptotically the measurement effectively projects the initial state on W state.
We have thus shown that we can transform with local operations and postselection the state of Eq. (18) into a state of the form where 0 < F < 1 can be arbitrary close to 1. The n-partite covariance Cov(σ 1 z , ...σ n z ) of the above state is given by the following expression (we show it in Appendix A).
In Fig. 3, we present how it depends on the fidelity F for a 3-qubit state and a 9-qubit state. For both states the covariance vanishes only for F = 1 2 . Let us summarize this result. The parties start with a state for which all covariances vanish. Then they apply local filtering and postselect a state. They can choose measurements in such a way that the postselected state has nonvanishing covariance. Hence, we have shown that covariance does not satisfy our second postulate. This once again shows that covariance should not be regarded as an indicator of genuine multipartite classical correlations. Let n parties share a state of Eq. (18). Let each party add to his original qubit an auxiliary qubit in state |0 , performs CNOT gate (the original qubit is control qubit and the auxiliary qubit is target qubit) and send the ancilla to new party. Each new party receives an ancilla from only one party. The 2n-partite state is One can show that the following covariance is equal to 1. We see that covariance does not satisfy Postulate 3 when applied to more than two-partite states.

IV. MULTIPARTITE CORRELATIONS AND WORK EXTRACTION
In this section we investigate the relation between multipartite correlations and the amount of work that can be extracted from the environment [6,8,9,19]. Let us suppose that two parties share a quantum state ρ AB . It is well known that this state can be used to extract work from the environment in many different ways. We consider two scenarios. In the first one the parties are allowed to perform closed local operations, i.e., they can perform local unitary operations and local dephasing (CLO). In the second one they are allowed to perform closed local operations and send classical communication, i.e. send subsystem down a completely dephasing channel (CLOCC). If for the state ρ AB the parties can extract more work with CLOCC than with CLO then the state ρ AB has classical correlations. Let us now consider multipartite states. By analogy we expect that if the parties can extract more work with CLOCC and with sending classical information across any bipartite cut than with CLOCC and without sending classical information across at least one cut then the state has genuine multipartite classical correlations. The difference between extractable work in those two scenarios minimized overall bipartite cuts we shall denote by δW .
Example 1. Here we compare the amount of work extractable with the use of an equal mixture of two tripartite W states when three parties cooperate, i.e., there is classical communication across any cut, and when two parties cooperate, i.e., there is not classical communication across one cut. Let us first suppose that three parties cooperate. If the parties dephase their qubits in {|0 , |1 } basis and the first two parties send their qubits to the third party (This is equivalent to sending qubits down a completely dephasing channel) then the third party will hold the state He can now extract 3 − log 2 6 ≈ 0.4150 bits of work. Another protocol is the following: one party measures in a chosen basis, and tells the result to other parties, who then draw work from the resulting pure state they share. If the basis is |0 , |1 , the result is the same as above. The complementary basis |+ , |− gives 0.4499, while the optimal basis is 1 3 |0 + 2 3 |1 , 2 3 |0 − 1 3 |0 , providing 0.4502 bits of work. We do not know, whether by general CLOCC protocol one can extract more work.
Let us now suppose that only two parties cooperate, i.e. the first and the second one. The reduced state of the third party is maximally mixed state and he cannot extract any work at all. The reduced state of the first two parties is Bell diagonal state where If the first party dephase his qubit in {|+ , |− } basis, where and send his qubit to the second party then the second party after applying local unitary operation will hold the state σ 12 = 5 12 |01 01| + 5 12 |10 10| + + 1 12 |00 00| + 1 12 |11 11| (38) He can now extract 1−H( 5 6 ) 0.3499 bits of work, where x) is binary entropy. This is maximal work which can be extracted with help of one-way classical communication even if one takes into account POVMS and asymptotic limit of many copies [8]. However, again, it is not known if one can extract more work with help of two-way classical communication.
To summarize, we showed, that if the communication through A:BC cut is allowed, then we can extract at least 0.4502 bits of work, while if it is not allowed, we were able to provide a protocol which extracts 0.3499 bits of work (this concerns all possible cuts, as the state is permutationally symmetric). If the latter protocol were optimal, we would have δW 0.1. This supports existence of genuine tripartite correlations in the state.
Example 2. On the other hand if the parties can extract the same amount of work with CLOCC and with sending classical information across any bipartite cut than with CLOCC and without sending classical information across at least one cut then we cannot conclude that the state does not have genuine multipartite classical correlations. Let us consider the following tripartite state If three parties cooperate they can extract one bit of work. However if only the first and the second party cooperate they can also extract one bit of work. On the other hand the state is non-product across any bipartite cut and according to Definition 2 it has genuine tripartite classical correlations.
The above two examples show that on one hand δW can indicate multipartite correlations, on the other hand it may vanish, even though the state is non-product against any cut. This is analogous to behavior of some entanglement measures: e.g. distillable entanglement can vanish for states despite they are entangled. Thus δW quantifies some particular type of genuine multipartite correlations, which may be absent in some states even though they contain genuinely multipartite correlations.
Let us note that the above property of δW is similar to covariance, which disappears for state (18), even though it has genuine multipartite correlations with respect to some other criteria. One basic difference is however, that covariance can be positive even for states such as product of EPR pairs Ψ + AB ⊗ Ψ + CD which quite obviously do not represent multipartite entanglement (example of such covariances are those of Pauli matrices in cases when pairs of the same Pauli matrices are measured on each of the EPR pair). Moreover, we believe (though have not proven) that δW would satisfy our postulates, i.e. having been zero for some state, it will not go up under the operations described in the formulation of the postulates, while covariance, as we have shown in previous sections violates two postulates.

V. CONCLUSIONS
In conclusion we have proposed reasonable postulates which each measure or indicator of genuine multipartite correlations (or genuine multipartite entanglement) should satisfy. We also introduced degree of correlations which gives partial characterization of multipartite correlations. We have shown that covariance does not satisfy proposed postulates and it cannot be used as an indicator of genuine multipartite classical correlations. In particular, our postulates show that the claim that there exist genuine n-partite quantum correlations without genuine n-partite classical correlations is not justified. As a by-product we obtain a protocol of distillation of W states from a wide class of states. Finally we propose a candidate for a measure of genuine multipartite correlations based on work that can be drawn from local environments by means a multipartite state. We hope that our results, especially the proposed postulates, will allow to develop understanding and quantitative description of genuine multipartite correlations.


extfieldsofstudy: Mathematics Physics

text:
Insights into classical irreversible computation using quantum information concepts

The method of using concepts and insight from quantum information theory in order to solve problems in reversible classical computing (introduced in Ref. [1]) have been generalized to irreversible classical computing. The method have been successfully tested on two computational tasks. Several basic logic gates have been analyzed and the nonlocal content of the associate quantum transformations have been calculated. The results provide us with new interesting insight into the notion of complexity of logic operations.

I. INTRODUCTION
The field of quantum information theory was born from a symbiosis of classical information theory and quantum mechanics. The main driving force behind the development of the new field is a vision of new computation and communication protocols and devices that would outperform their classical counterparts. At the same time, one might expect certain benefits to the classical theory as a "side effect" of this development. Such a feedback might be in interesting manifestation of the dynamical coexistence of the two fields from both theoretical and practical perspectives.
The first steps in this direction were made in Ref. [1], where a method of evaluating (the bounds on) the number of Toffoli gates in a classical reversible circuit using quantum information concepts was proposed.
Here we generalize this approach to irreversible classical circuits, which provides an interesting insights into the nature of classical computing.
The structure of the article is as follows. Section II gives a brief overview of the method in [1]. Section III presents the details of how the method is generalized to irreversible case. In Section II we give two examples of its implementation.

II. THE METHOD
Let us recall the basic principles of the approach in [1].
The key idea is to map classical bits onto special orthogonal quantum states, i.e. 0 → |0 and 1 → |1 , thereby mapping strings of n bits on the associate products of n quantum states such as Subsequently, the action of the logic gates is mapped onto corresponding transformations acting on these states. For reversible circuits the corresponding associate quantum transformations are unitary. Then, the study of the properties of the quantum transformation that is associated to the classical computation can provide information about the classical circuit. The property of a quantum transformation was chosen to be its nonlocal content as expressed via two quantities: first, its entangling capacity E ↑ , second its entanglement cost, E cost (which always satisfy E ↑ ≤ E cost ) [2]. The number of elementary gates needed to implement a particular classical computation is bounded from below by the following ratio for the associate quantum transformations To realize this programme the two states |0 and |1 have to be nonlocal (entangled) states. In particular, the following states were used in [1] Thus, classical logic bits are encoded in orthogonal maximally entangled states of two qubits.

III. GENERALIZATION TO IRREVERSIBLE
Here we generalize this approach to classical irreversible circuits. In this case the associate quantum transformations become non-unitary. In addition to entangling capacity and entanglement cost we will associate a third quantitydisentangling capacity, E ↓ -with a nonunitary operation. For in the case of reversible computing E ↓ was not very important since it does not affect the bound in Eq. (3). For irreversible computing the interplay between E ↑ , E ↓ and E cost become much more interesting.
A. 1-bit logic gates: RESET Let us start with a trivial example of the simple logic operation RESET (to zero) with corresponding truth- The operation G reset is a superoperator or CPTP map, and is able to create 1 ebit of entanglement, which becomes evident if we consider unentangled input state 1/ √ 2(|0 +|1 ). On the other hand 1 ebit is also sufficient to implement G reset . This task can be accomplished, for example, if one simply replaces the original pair by an ancillary pair in a state |0 and discards the original pair. More formally, this procedure can be presented as a SWAP operation on the original pair and an ancillary pair in the state |0 followed by discarding the ancillary pair. Thus, E ↑ (G RESET ) = E cost (G RESET ) = 1. It is obvious that G RESET cannot destroy any entanglement since it always has a maximally entangled state as its output, i.e. E ↓ (G RESET ) = 0.
Corollary, E ↓ = 0 for a quantum counterpart of any deterministic (surjective) logic operation, with equal numbers of inputs and outputs.

It is mapped on the non-unitary transformation
Note, that unlike 1-bit transformations, G XOR is not trace preserving, because it is accompanied by loss of subsystems. We can account for this loss by introducing a purification. For example, G XOR can be obtained if one implements (unitary) CNOT and discards the first pair. Nonlocal CNOT transformation is equivalent to two local CNOT transformations on corresponding qubits and therefore has zero entanglement cost [1]. Therefore, E cost (G XOR ) = 0. However, since the first pair is discarder it effectively involves "dissipation" of entanglement. In other words, whatever the mechanism inside the box is it will "dissipate" entanglement of the first pair. Therefore, C. Universal 2-bit gates: NAND and NOR Conceptually, the most interesting are NAND and NOR gates, because each of them is a universal gate for irreversible computation. Let us consider now the NAND gate A purification of G N AN D may arise if the two original pairs interact with a third, ancillary, pair in a standard state |0 via unitary transformation and consequently the ancilla and the second pair are discarded (traced out). In other words, it is a trace out of a Toffoli gate with one standard input. It should be noted that the realization (purification) in Eq. (6) is not unique. In fact, specification of the mapping of basis states in Eq. (5) does not fully determine G N AN D , that is to say that Eq. (5) does not prescribe how an arbitrary linear combination of basis states will evolve. (This is the nature of a trace-non-preserving operations -they do not supply full information about the evolution of the system.) We will come back to this problem later. Now let us calculate (bounds on) E ↑ and E cost . It is a difficult task to calculate the explicit value of E ↑ for a quantum operation. At the time this paper was written the only known method of calculating it was a direct numerical optimization over all states accessible to the operation (even including ancillas). The value of E cost can be obtained by providing an explicit way of implementation, though its optimality has to be also proven.
However, it is much easier to find bound on these quantities -a lower bound on E ↑ and an upper bound on E cost . If the two bounds happen to coincide then one is lucky to obtain exact values of E ↑ and E cost . As we will see below, our calculations leave the gap between the two bounds in the case of NAND. Nevertheless, it will suffice to bound the number of gates N gates as in Eq. (3).
To obtain a lower bound on E ↑ (G N AN D ) we choose a special input state, the test state |Ψ test in and obtain the corresponding output state The difference between the amounts of entanglement possessed by ρ test out and |Ψ test in bounds from below the entangling capacity of G N AN D . Any test state that leads to an increase of entanglement gives a lower bound. The higher the bound the better. The higher bounds can be obtained either by direct numerical search of by trial and error.
Consider, for example, the following disentangled state as an input, Of course, the input state for a gate inside an irreversible circuit will be most likely a mixed state.
However, the following unitary will do the job as well, in which case Thus, G N AN D represents the whole family of quantum maps. The most general unitary extension will give where a, b, c and d are complex amplitudes. The output state, therefore, will be It can be shown that the minimum is achieved at |d| = 1, i.e. Re(a + b + c) = Im(a + b + c) = 0 and equal 1 − H [1/4]. Recall that E test in = 0 ebits and we obtain To provide an upper bound on E cost let us consider the following protocol. In addition to the first two pairs |x 1 and |x 2 we use an ancillary pair in a standard state |0 3 and apply on these three pairs a nonlocal Toffoli gate as in [1]. This utilizes 2 ebits. Then we discard first two pairs and are left with one pair in the desired final state. The total cost of this procedure is 3 ebits. Therefore, E cost ≤ 3.
Thus, we obtain Interestingly, the NOR gate, an alternative universal gate for irreversible computing, has the same values of E ↑ , E ↓ , and E cost .

D. Calculating bounds
Now, if we are given a classical circuit all we have to do is to calculate (a lower bound on) E ↑ of the associate quantum transformation and obtain the bound on N gates using Eq. (3). As NAND (or NOR) is a universal gate any circuit can be build from NAND gates alone. The present method is unable to provide a bound in this case. This is because some of the NAND gates in a circuit will replace other gates that have E cost = 0, and thus even if the whole quantum transformation has E ↑ = 0 we will need nonzero number of NAND gates. On the other hand, we might consider universal sets of two or more gates, e.g. NAND and XOR. The bound (3) provides us with a meaningful result when one tries to minimize the usage of NAND gates by supplementing them by other gates, e.g. XOR gates.
Entanglement cost of the gates in a sense gives us an insight into the computation complexity of the gates. The fact that E cost (G XOR ) = 0 while E cost (G N AN D ) > 0 emphasized an essential difference between XOR and NAND gates -XOR gates involve less computational effort than NAND gates so to speak.

IV. EXAMPLE OF IRREVERSIBLE COMPUTATION
A. Example I: Parity calculation Consider a trivial example of the circuit that calculates a parity function, i.e. for a binary string of n bits it calculates whether the number of zeros is even or odd. Obviously, half of all possible input strings will have even number of zeros and half will have odd number of zeroes. Therefore, if we use a uniform superposition of corresponding quantum sequences as an input, then the output will be ρ out = 1 2 |0 0| + 1 2 |1 1| which has zero entanglement. In fact, numerical calculation indicate that any input states will lead to no increase of entanglement, i.e. E ↑ = 0. Thus, application of our method, i.e. Eq.
(3), yields N N AN D ≥ 0. Indeed, the whole computation can be easily accomplished by sequential application of XOR gates, and therefore no NAND gates are needed to implement the computation [3]. As we have shown XOR gates have zero entanglement cost and therefore their combination cannot increase overall entanglement.

B. Example II: First step in Shannon compression
As a more complex example let us consider the first step in Shannon compression -the majority measurement. For n bit input string the circuit calculates the number of 1's, k [4]. There are n + 1 possible values of k, therefore we have m = ⌈log 2 (n + 1)⌉ bit output string Without loss of generality let us assume that the output strings represent the values of k of corresponding input string in a binary form, e.g. 0011 → 10, 0101 → 10, (17) 0111 → 11, etc.
As before we take the initial state to be a uniform superposition of all basis states The corresponding output state is is a binary to decimal converter, that assigns a corresponding value of k to every sequence (term) in the sum in Eq. (19). As there are ⌈log 2 (n + 1)⌉ pairs of qubits involved in the output state it might give us a clue that the output entanglement scales not faster than log 2 n. This intuition is supported by the results showed in Fig. 1. Therefore, the lower bound on the number of NAND gates required to implement the computation grows as 0.1962 log 2 n − 0.1775. Thus, our results clearly indicate, that for n < 70 at least one NAND gate is required. Interestingly, this conclusion is corroborated by known circuits implementing the Full Adder (n = 3), which is constructed out of two NAND gates, three XOR gates and two NOT gates.

V. DISCUSSION
This work demonstrates that the method of Ref. [1] can be successfully to irreversible classical computing. Following that method we have constructed quantum counterparts of several logic gates, namely RESET, XOR, NAND and NOR, and have calculated nonlocal content of these quantum transformations. Three quantities were associated with the entanglement contententangling capacity, E ↑ , disentangling capacity, E ↓ and entanglement cost, E cost . Together with the number of logic bits these quantities provide a non-trivial characterization of gates. We have seen that deterministic, but irreversible, one-to-one-bit gate, RESET, has E ↓ = 0 and E ↑ = E cost = 1. An irreversible two-to-one-bit gate, XOR, exhibits completely different properties, namely E ↓ = 1 and E ↑ = E cost = 0. The third type -two-totwo irreversible universal gates, NAND and NOR, have E ↓ = 1 and 0.189 ≤ E ↑ ≤ E cost ≤ 3. The entanglement cost, E cost , was an essential ingredient for estimating lower bounds on the number of universal gates. Every circuit can be built from the universal gates alone. However, since NOT and XOR gates have E cost = 0, our method can only provide bounds on the minimal number of universal gates when the numbers of NOT and XOR gates are not limited, i.e. when one aims to minimize the number of universal gates by using other gates, if possible. It is worth emphasizing that our method is not constructive in the sense that the bounds it provides do not tell us how a particular circuit can be built from a certain type of gates.
The method was tested on two computational task. As a first task we have chosen the calculation of the parity of a binary string of n bits. Our method indicates that no NAND or NOR gates are needed to construct a circuit which realizes this calculation. This conclusion is consistent with the fact, that this computation can be achieved by simple cascade of XOR gates. The second task is the first step in Shannon data compression, i.e. calculating the number of 1s in a binary n-bit string. Our method provides the lower bound on N N AN D of a fraction of log 2 n. It is worth noting that our method can provide minimal bounds of at most m = ⌈log 2 (n + 1)⌉, because the corresponding output quantum state can posses at most m ebits of entanglement.
Our results provide an interesting insight into complexity of computation. The link between our approach and computation complexity was already established in [1]. Indeed, in the reversible scenario it was shown that E cost of the quantum counterpart of Toffoli gate (a universal gate) is non-zero whereas two-bit gates, e.g. CNOT, and one-bit gates, NOT, do not consume any entanglement at all. Therefore, one can use E cost as a kind of measure of the complexity of the associate classical logic gate itself. However, in the reversible case the distinction between Toffoli and two-or one-bit gates in term of their complexity is intuitively straightforward -Toffoli is more complex because it performs a nontrivial computation on more bits. In the case of irreversible computation this distinction becomes much more subtle. This is why the results of this work provide us with much more interesting and powerful insight. Indeed, here universal gates are not distinguishable from other two-to-one-bit gates simply by the number of inputs/outputs. than NAND and NOR are in certain sense computationally (logically) stronger, than XOR. One-to-one-bit RESET gate stands alone for having a nonzero E cost . However, we note that RESET gate does not actually perform a computational task.


Assessment of PLSDA cross validation

Classifying groups of individuals based on their metabolic profile is one of the main topics in metabolomics research. Due to the low number of individuals compared to the large number of variables, this is not an easy task. PLSDA is one of the data analysis methods used for the classification. Unfortunately this method eagerly overfits the data and rigorous validation is necessary. The validation however is far from straightforward. Is this paper we will discuss a strategy based on cross model validation and permutation testing to validate the classification models. It is also shown that too optimistic results are obtained when the validation is not done properly. Furthermore, we advocate against the use of PLSDA score plots for inference of class differences.

Introduction
The research area of metabolomics is growing fast due to an enormous improvement of analytical technology as LCMS, GCMS and NMR (Bollard et al. 2005;Van Der Greef and Smilde 2005). The application field is rather wide, ranging from plants (Bino et al. 2004;Fiehn 2002) to microbial (van der Werf et al. 2005), medical (Clayton et al. 2006) and even nutritional applications (Van Dorsten et al. 2006;van Ommen 2004). The typical metabolomics study involves two groups of individuals, often called case and control (Broadhurst and Kell 2006). Such a study can be used in an exploratory way or in a predictive way. An explorative study is used to see whether the specific data contains sufficient information to distinguish between the two groups. E.g. recently the use of MALDI to detect metabolites has been explored, but it was unknown whether these data contained sufficient information to make a distinction between diseased and control groups (Ragazzi et al. 2006;Vaidyanathan and Goodacre 2007). Then there is need for a predictive model that can predict whether an unseen individual belongs to the case or control group.
An often used data analysis tool for classification in the metabolomics area is PLSDA (Barker and Rayens 2003) or OPLSDA (Bylesjo et al. 2006;Trygg 2002;Trygg and Wold 2002). These classification tools are based on the PLS model in which the dependent variable is chosen to represent the class membership. The large number of peaks in these spectra that are all potential biomarkers create modelling and validation challenges. The number of samples needed to accurately describe such a classification problem increases exponentially with the number of variables measured. However, the number of samples used in these applications is usually much smaller than the number of variables. This can easily lead to chance classifications, i.e. models that just by chance give a good classification of the two groups.
A good start for the analysis of any data analysis method is to use a set of random data and see how the method deals with it. A convincing example that validation of PLSDA models is of major importance is the classification of a set of random data. Using PLSDA to discriminate a random data set of size e.g. 40 9 100 (comparable to the size of metabolomics data) into two groups does almost always give a PLS score plot with perfect separation between the two arbitrary classes. Please try this using your own software.
A similar example is given in Fig. 1. Here NMR spectra (382 channels) of a group of 23 healthy volunteers are arbitrarily divided into two classes of 11 and 12 class members. Cross validation revealed a Q 2 value of -0.18 which is usually considered not to be a good classification model. However, the PLSDA score plot in Fig. 1 shows a clear separation between the two classes. PLSDA is eager to please and thus its results should be handled with great care. The problem is that in the 382 dimensional megavariate space there is almost always a perfect separation possible between the 23 samples and PLSDA has no problems finding it. The PLSDA score plot therefore does not give a good representation of class difference between the groups. This is probably the reason why others already started to show cross validated score plots (Cloarec et al. 2005). However, the problem with that plot is that each score value is based on a different loading and therefore they should not be plotted into one figure as they cannot directly be compared.
Although the score plot should not be used to infer class separation, it might reveal structure (e.g. subgroups) within a class. Since the model is not forced to show this difference, this is not a result of overfit, and thus such information could be inferred from the score plot.
Validation of PLSDA models has received a lot of attention. Very recently a number of papers appeared discussing various aspects of the validation and claiming that in many applications, proper validation of the classification models were lacking (Brereton 2006;Broadhurst and Kell 2006;Harrington 2006;Rubingh et al. 2006). Broadhurst and Kell summarize the main problems in the analysis of megavariate data. The most important one might be the too small sample size. Due to the very expensive experiments, the number of samples is usually too small. A good criterion of sample size is hard to give as multivariate power calculations are not well understood at the moment. A good starting point here is the use of Monte Carlo simulations to determine the appropriate number of samples (Martens et al. 2000). Most important however is that the samples chosen contain sufficient information to provide the answers searched for (Trygg et al. 2007).
Cross validation is performed in most cases to validate the results found, but often not performed in a proper manner (Anderssen et al. 2006). Various parameters have been used to quantify a certain classification, e.g. Q 2 values, number of misclassifications, many combinations of sums or ratios of True Positives, True Negatives and False positives and False Negatives of a confusion matrix. Also the area under curve of a receiver operating characteristic (ROC) curve (AUROC) is used often. Problem with all these measures is that it is unknown which value corresponds to a good discrimination between the groups. A measure for statistical significance (e.g. a P-value) is usually not given. Furthermore, this value depends on the number of samples in the training and test set. Another problem with the cross validation procedure is that in each of the many models built during the cross validation, a different number of PLS components seem important for each of the submodels. At the moment there are no accepted criteria for the way to choose the overall model, when returning to the full dataset based on the conclusion obtained from the many models developed from subsets of the samples.
In this paper we will tackle most of the problems discussed above. The main message we will bring in this paper is that by analysing many versions of the data with randomly assigned class labels, a reference distribution for the H0 hypothesis that no difference exist between the two classes is obtained. Using these permutations we will show that improper use of cross validation leads to a too optimistic classification result. Although many papers have pointed to this problem, we clearly show that too few misclassifications are obtained when cross validation is used wrongly. Furthermore using the permutations each quality parameter used to assess the quality of the classification (e.g. Q 2 , AUROC or the number of misclassifications) is accompanied with its own H0 distribution of values that can be obtained in case of no difference between the classes. From this it can be observed e.g. which Q 2 value corresponds to a statistically significant classification model. We argue against the use of a single final model, but instead promote  Fig. 1 PLSDA score plot of an NMR data set of healthy volunteers which were arbitrarily divided into two classes. Q 2 value of this model was -0.18. Still a clear separation between the classes is observed in this score plot the use of many slightly different models to obtain a range of class membership predictions. This range can be used as a confidence measure for class membership assignment. Note that although we use PLSDA here as the test case, the same approach can be used for other classification methods.

PLS-DA
Partial least squares discriminant analysis (PLSDA) is a frequently used classification method and is based on the PLS approach (Barker and Rayens 2003). The standard PLS algorithm can be used and for the dependent y vector, class labels can be used. In the two-class case, usually the values of the dependent variable are given 1 for one class and 0 or -1 for the other class. In case of more than 2 classes, dummy variables are defined and a PLS2 algorithm is used. A much used variant of PLSDA is OPLSDA where the first components orthogonal to the dependent variable are removed from the data (Trygg and Wold 2002). This gives a model with a single classification component while the other components describe the other variation that is orthogonal to the class information. OPLS enhances the interpretation of PLS by forcing all classification information into a single component. The prediction power of both models is usually the same (Trygg and Wold 2002). Typical applications of two class classifications using PLSDA show a score plot of the classified samples. This plot is often accompanied with a Q 2 value indicating the validity of the discrimination. Figure 2 shows such a typical score plot of a PLSDA classification between men and women based on NMR spectra of their urine. The data presented here is described in more detail in the experimental section.
As demonstrated in the introduction of this paper, a score plot indicating separation between two groups has no meaning as similar plots can be obtained when random data is classified. It is also unknown what the corresponding Q 2 value of 0.51 indicates. Is this a good separation? As long as there are no values to compare the Q 2 value with, the value of this number is meaningless.

Permutation tests
A permutation test can evaluate whether the specific classification of the individuals in the two designed groups is significantly better than any other random classification in two arbitrary groups (Golland et al. 2005;Mielke Jr and Berry 2001). In a permutation test, the class labels of case and control are permuted, they are randomly assigned to different individuals. With the 'wrong' class labels, again a classification model is calculated. The rationale behind the permutation test is that with the wrong class labels, the newly calculated classification model should not be able to predict the classes very well. As the groups are formed in a random way, the assumption is that no difference exists between them. By repeating the permutation test many times, a H0 distribution of classifications that are expected not to be significant is formed. From these classifications, H0 distributions for Q 2 , AUROC and for regression coefficients etc can be obtained. The results obtained from the non permuted set of samples should be outside the 95 or 99% confidence bounds of the H0 distribution from the permuted classifications to be significant.
A major advantage of the permutation test is that the H0 reference distribution is always based on models based on the same number of samples that also show the same amount of variation, outliers, missing data etc. The reference distribution therefore perfectly matches the analysis results of the original model. The permutation test is integrated in the currently described validation procedure. It will be used to validate the metabolic differences. It will also be used to evaluate validation procedures such as cross validation.

Cross validation
Cross validation is often used for validation of a classification model due to the low number of samples available. As separation into training, validation and test set is often not possible, cross validation makes better use of the data. However, cross validation only gives a reliable error rate when the complete modelling procedure is cross validated.
The object that is predicted should in no way be used in the development of the model (Anderssen et al. 2006;Brereton 2006;Broadhurst and Kell 2006). This is repeatedly mentioned in many papers, however, it is still not common practise in the many applications found in the recent literature. For a proper cross validation, the total data should be divided into a training set, a validation (sometimes called optimization) set and a test set. Using the validation and training set a model is developed and optimized. The test set is only used to test the model performance. By repeating the procedure in a way that each sample appears once and only once in the test set, the prediction error is representative for new samples. For a complete independent test set, it should also not be used in data pre-treatment and pre-processing, scaling etc.
In this paper we will use three versions of cross validation that will be compared using the permutation strategy.
FIT: Using the single cross validation strategy (1CV, see below), the optimal number of PLS components is found. A PLSDA model is then built on all samples using this optimal number of components. Then the class labels of all samples are ''predicted'' using this model. Note that here predicted is placed inside quotation marks to indicate that this is not a real prediction, but merely a resubstitution. Based on the predictions of the class labels in this way, Q2_FIT, AUROC and number of misclassifications can be obtained.
1CV: Single cross validation is generally used in many applications. With single cross validation, some of the individuals are removed from the data and used as a validation set. The remainder of the individuals that form the training set are used to develop a series of classification models with 1 to many PLS components. For each of these models, a prediction of the validation set is given and the prediction errors of all of these models are stored. This procedure is repeated for a new set of individuals until all individuals have been in the validation set once (and only once). The total prediction error for all the models over all individuals is calculated, and the model with the lowest total prediction error is selected as the best. The prediction errors obtained using the 1CV approach can be used to calculate the number of misclassifications and the Q2_1CV. It has to be realized that the same individuals (in the validation set) were also used to find the best overall model parameter and thus they are not completely independent as is requested for a proper cross validation.
2CV: In order to overcome the dependency between the prediction error for new individuals and the optimization of the model parameter, cross model validation (2CV) was suggested. In 2CV one set of individuals is set aside completely as the test set. Then the remainder of the individuals are subjected to a single cross validation regime. In this regime the remaining individuals are again split into a validation and a training set. The single cross validation will result in an optimal number of PLS components. Then all training and validation individuals are used to build a final classification model with the optimal number of PLS components. This final model is then used to predict the individuals in the test set. The whole procedure is repeated until all individuals have been in de test set once (and only once). It is important that the selection of the validation samples is done randomly to enforce different combinations of validation sets and training set for each new test set. In this way the model has been built in absolute absence of the test set, the prediction is independent of the model optimization (Stone 1974).
Summarizing, the 1CV method assesses the variability of the estimated parameters and its effect on the prediction, while the 2CV method also assesses the variability of the meta parameters and their effect on the prediction. Table 1 gives a summary of the dependence of the sample that is predicted and some of the model parameters. Only when 2CV is used for validation, the sample that is predicted is truly independent, leading to a correct prediction error.

Final calibration model
Note that now the prediction of each separate test set is performed on slightly different models that have different optimal model parameters. This complicates the development of a final calibration model, because it is not known what model parameters to choose for the final model (Brereton 2006). The precision of a final calibration model is not allowed to be smaller than the models that were developed during the cross validation procedure. However those models were always based on a subset of the samples. Therefore the full potential of the final calibration model is never used. However, such a final model is also not necessary. Instead of having one final model, a group of models (one for every test set) is available to classify future individuals. Instead of one class prediction, a group of class predictions is given for each individual. This group of predictions can be combined into an average prediction and it can also be used to obtain a confidence interval for the class prediction. This is related to the bagging approach introduced by Breiman (Breiman 1996(Breiman , 1998. Furthermore, the various models give insight in the stability of the optimized model parameters.

Quality assessment
Many measures exist to quantify the quality of a specific classification such as measures, derived from the confusion table, which consist of the number of False Positives, False Negatives, True Positives and True Negatives exist (Broadhurst and Kell 2006). For the Case individuals, the fraction of True positives is referred to as the sensitivity while the fraction of False Positives is referred to as (1-specificity). Combining the two leads to the receiver operator characteristic (ROC) that we will use in this paper. The ROC unifies two characteristics that are often used to evaluate the performance of a (clinical) test or method. A ROC curve plots the sensitivity of a test versus 1-specificity of a test. The sensitivity is defined as the number of true positives found as a percentage of all positives (diseased people), while 1-specificity is the number of false positives as a percentage of all negatives (controls, healthy people). Sensitivities are between 0 and 1 and should be close to 1. The specificity should preferably be close to 1, and 1-specificity should be close to 0. Both specificity and sensitivity depend on the setting of the classification boundary of the classifier used by a method. By shifting the classification boundary more true positives may be detected, but the number of false positives also increases, and the other way around. The ROC curve therefore is a characteristic of a method, describing the sensitivity and specificity of a method for different classification boundaries. Each point on a line gives the sensitivity of a classifying model versus 1-specificity of the model. Each point on the ROC curve refers to a value chosen for the classifier boundary. Instead of choosing 0 as the classified boundary, one can select a slightly lower value to increase the sensitivity of class +1. Of course this goes together with a loss of 1-specificity. As a quality measure we use the area under the ROC curve (AUROC). This value goes to 1 for a perfect separation between the classes. If there is no separation then a value close to 0.5 is obtained.
The prediction error measure Q 2 , which is the default parameter used in PLSDA discriminations focuses on how well the class label can be predicted from new data. Q 2 is defined as follows: whereŷ i refers to the predicted value of class membership for sample i while " y refers to the mean value of y for all samples. The optimal Q 2 value of 1 is difficult to reach as this requires that the class prediction of each individual should be exactly equal to its class label. This is hard to get due to the inherent variation between the individuals in the same class. The Q 2 depends on the between class separation but also on the within class variability. This makes it difficult to give a general Q 2 value that corresponds to a good classification. Therefore we use permutations to provide a whole distribution of Q 2 values for models of no effect to relate the original Q 2 value to.
The ROC and number of misclassifications are both classification error measures (they only make a distinction between good and wrongly classified). The Q 2 value is a prediction error that makes a distinction between slightly wrong and very wrong. A prediction of -0.2 is penalized more than a prediction of 0.4 for a class label of 1 while the classification error measures treat these predictions both equally as wrong. In a further study we will examine the power of these measures.

Human urine samples
Twenty-four-hour urine samples were collected from 23 healthy male and female volunteers in the age range between 19 and 78 years, i.e. 12 women (mean age: 42.0 years, range: 20-78 years) and 11 men (mean age: 44.4 years, range: 19-74 years). All samples were stored frozen at -20°C prior to analysis and thawed on the day of analysis.
3.2 1 H NMR Spectroscopy 1 H NMR spectra were acquired at 600.13 MHz on a Bruker Avance 600 spectrometer. Urine samples were prepared for 1 H NMR spectroscopy by diluting 300 ll of urine 1:1 with 2 H 2 O, followed by spinning down non-soluble particles for 10 min at 14,000 rpm in an Eppendorf centrifuge. Urine NMR spectra were measured at 303 K using a standard Assessment of PLSDA cross validation 85 water-suppressed 1D-NOESY pulse sequence, i.e. RD-90°t 1 -90°-t m -90°-acquire. Here, RD is a relaxation delay of 1.5 s during which the water resonance was selectively irradiated, and t 1 corresponds to a fixed delay of 0.15 s. A total of 128 transients were collected into 32 k data points, with a spectral width of 7,000 Hz. Prior to Fourier transform (FT) the free induction decays (FIDs) were multiplied by a 0.3-Hz exponential line-broadening function and zerofilled by a factor of 2.All spectra were manually phase-and baseline-corrected using XWINNMR (Bruker GmbH, Germany), and referenced internally to the creatinine methyl peak at d 3.10.

NMR spectral data reduction
The NMR spectral dataset between 0.4 and 10.0 ppm was automatically reduced into regions of equal width (0.02 ppm), to minimize the effects of (pH-dependent) peak shifts, and the integral of each region was determined using AMIX software (Bruker GmbH, Germany). The spectral region from 4.0-6.0 ppm was excluded from analysis to remove the effect of variations in the suppression of the water resonance and variations in the urea signal. The peak integral within each 0.02-ppm spectral region was normalized to a constant sum of 1,000 for each spectrum, to account for differences in urinary volume.

Data analysis
In the single and double cross validation procedures, the samples were split into six groups; a 6-fold cross validation strategy is used. It was enforced that in each validation set (1CV) or test set (2CV) individuals of both classes were present. Thus six different models are created. The single cross validation inner loop of the double cross validation, which is used to obtain the optimal number of PLS components, used a leave one out CV1. The selection of the test sets, validation sets and training sets were randomized to enforce a different combination of samples. The class labels of 0 and 1 were used for men and women respectively.

Evaluation of cross validation
In the first part of the results and discussion section we evaluate the different versions of cross validation discussed in the theory section. The number of misclassification is used here as a measure because of its known expected value in the fully randomized case. Here we mean that if the individuals are randomly permuted over the classes that the average number of misclassifications should be half of the samples in a two-class problem. Predictions of class labels using the actual data were performed 20 times in which the combination of samples in training set, validation set and test set was varied. The numbers of misclassifications were averaged over the 20 cross validation runs. The data was permuted 2,000 times. Of each permuted set, the cross validation was repeated 20 times and the average number of misclassifications was calculated.
Using the permutations, a distribution is developed for the H0 hypothesis being that no difference exists between the two classes. When no difference exists between the classes, an average of 11.5 misclassifications is expected. Thus the validation procedure should on average give 11.5 misclassifications for the permuted datasets. In the evaluation of cross validation procedures we calculate the number of misclassifications using the FIT, 1CV and 2CV approach. Figure 3 shows histograms of the number of misclassifications of the permuted data. When the FIT approach is used, many good classifications are made on the permuted data. The average number of misclassifications using the FIT approach is 1.5, which is clearly much too optimistic as the expected number of misclassifications of the permuted data is 11.5. Note that even in the FIT approach a single cross validation step was used to select the number of PLS components. But this is in no way sufficient for a proper validation.
The single cross validation (1CV) procedure leads to an average number of misclassifications of 10.0 for the permuted data. This is still a too optimistic result. In single cross validation the predicted individuals are still not Fig. 3 Misclassifications of gender PLSDA as classification method with FIT, 1CV and 2CV as validation strategies with permutated data representative of a completely new individual as they are also used to define the optimal number of PLSDA components. Only when a double cross validation (2CV) strategy is used, the number of misclassifications equals the expected value of 11.5.

Quality assessment
Is there a difference between the groups? How to statistically quantify whether a difference exists? If the number of misclassifications is lower than half of the number of samples, then there is a difference. If the area under the ROC curve is above the 0.5 then there is also a difference. The default parameter in PLSDA, the Q 2 value, does not provide an answer to this question. It is unknown which value Q 2 value to expect for a good classification of two groups. Therefore we will again use the permutation approach to obtain a distribution of Q 2 values that correspond to the H0 of no difference between the two classes. In this case the Q 2 values and the AUROC and also the number of misclassifications are obtained using predictions of class labels in a cross model validation setup. Thus the predictions of class labels are performed for samples that have not been used to develop the model. Figure 4 shows the number of misclassifications, the Q 2 values and the AUROC values for the original classifications in red and for the permutations in blue based on predictions in a cross model validation framework. For all assessment parameters there is a clear distinction between the permutation distribution and the original classification. This shows that the specific classification is significant. If we compare the average value of the original classification with all the permutations then a P-value can be obtained.
Using double cross validation to predict the class label, the original classification has on average 3.35 misclassifications. Of the 2,000 permutations none had a number of misclassifications lower than 3.35 leading to a P \ 0.0005. The Q 2 values of the permutations show a distribution around -0.5. Six percent of the permutations show a Q 2 value above 0. The original labelling had a Q 2 value of 0.5. This also leads to a P \ 0.0005 as none of the permutations had an average Q 2 value above 0.5. The average AUROC value is indeed 0.5 as expected while the average AUROC of the original labelling was 0.80 (P \ 0.0005). For the set of 2,000 permutations no difference between the three assessment criteria were found.

Variation in class prediction using PLSDA
There is a major problem to translate the optimization results obtained during the cross validation to a final model. If a successful predictive model is obtained, it is then necessary to choose a model that will be applicable to new samples using all samples available. However, the assessment of the model has been performed on multiple subsets of samples, each with its own number of components, variables selected, scaling etc. At the moment no consensus exist how to choose the overall model based on submodel results (Brereton 2006). Therefore instead of having one final model with a single class prediction for new samples, multiple class predictions can be obtained from many different models that were developed during the cross validation procedure. Instead of having a single prediction of gender, it is interesting to know the variability in class prediction when many related models are used. Furthermore, often the average of multiple models is a better estimate of class, then a single prediction. This idea goes back to bagging predictors (Breiman 1996(Breiman , 1998. The average of a set of predictors can have a smaller variance than a single predictor. In cross model validation each of the multiple models is developed using a smaller sample size and therefore will probably have a somewhat higher prediction error. However, because of the multiple related models, a good idea is obtained of the spread in class prediction. This spread can be used as a confidence measure for the class prediction, while the average of all prediction will probably have a lower variance. Therefore 1,000 models were developed within the cross model validation, each time with a different combination of samples. The prediction of the class labels is performed using models that are unrelated to the sample of which the class is predicted. The class predictions are presented in Fig. 5. Figure 5 shows the spread in y-value prediction and thus the classification. Samples 1-11 are males and were coded 0. Samples 12-23 are females and were coded as 1. It can be seen that some males are always classified correctly (1, 4, 5, 10 and 11) and also some females are always classified correctly (21 and 22). Individual 12 is almost always classified wrongly, while others are in almost half of the cases classified wrongly. The predicted range is indicative of the confidence in class membership.

Conclusion
Classification problems in metabolomics data analysis are complex due to the many variables few samples issue. This makes that many solutions can be found to separate the classes. Most models therefore suffer from overfit, meaning that the model classifies the training data well, but future samples are classified poorly. In this paper we describe the use of permutation testing and cross model validation to assess the validation of classification models. Permutation tests show that when cross validation is not applied appropriately, it leads to overoptimistic results. Moreover, the permutation test gives a sensible measure for the Q 2 value. Cross model validation leads to good results. Although not new and shown in other fields, it is unfortunately almost completely ignored in the metabolomics research field.
The PLSDA score plots as presented in most classification applications in the metabolomics research field present an overoptimistic view of the separation between the classes. Although within class variation can be revealed by this plot, it should not be used to examine between class separation. This was clearly shown by the classification of randomly assigned class membership. Class separation results should be based on predictions instead of on fitted values (such as the PLSDA scores). It is therefore much more informative to present class predictions as was shown here in this paper.