extfieldsofstudy:
Computer Science
Medicine

text:
On the Impact of Entropy Estimation on Transcriptional Regulatory Network Inference Based on Mutual Information

The reverse engineering of transcription regulatory networks from expression data is gaining large interest in the bioinformatics community. An important family of inference techniques is represented by algorithms based on information theoretic measures which rely on the computation of pairwise mutual information. This paper aims to study the impact of the entropy estimator on the quality of the inferred networks. This is done by means of a comprehensive study which takes into consideration three state-of-the-art mutual information algorithms: ARACNE, CLR, and MRNET. Two different setups are considered in this work. The first one considers a set of 12 synthetically generated datasets to compare 8 different entropy estimators and three network inference algorithms. The two methods emerging as the most accurate ones from the first set of experiments are the MRNET method combined with the newly applied Spearman correlation and the CLR method combined with the Pearson correlation. The validation of these two techniques is then carried out on a set of 10 public domain microarray datasets measuring the transcriptional regulatory activity in the yeast organism.

Introduction
The inference of regulatory networks by modeling dependencies at the transcription level aims at providing biologists with an additional insight about cell activities. This task belongs to the domain of systems biology which studies the interactions between the components of biological systems and how these interactions give rise to the function and the behavior of the whole system. This approach differs from the so-called "reductionist approach" that limits its focus to the building blocks of the system without providing a global picture of the cell behavior, as stated in [1]: "the reductionist approach has successfully identified most of the components and many of the interactions but, unfortunately, offers no convincing concepts or methods to understand how system properties emerg . . . the pluralism of causes and effects in biological networks is better addressed by observing, through quantitative measures, multiple components simultaneously and by rigorous data integration with mathematical models." The reverse engineering of transcriptional regulatory networks (TRNs) from expression data is known to be a very challenging task because of the large amount of noise intrinsic to the microarray technology, the high dimensionality, and the combinatorial nature of the problem. Also, a gene-to-gene network inferred on the basis of transcriptional measurements returns only a rough approximation of a complete biochemical regulatory network since many physical connections between macromolecules might be hidden by shortcuts. Notwithstanding, in recent years, computational techniques have been applied with success to this domain, as witnessed by successful validations of the interaction networks predicted by the algorithms [2].
Network inference consists in representing the stochastic dependencies between the variables of a dataset by means of a graph. Mutual information networks are an important category of network inference methods.
Information-theoretic approaches typically rely on the estimation of mutual information (MI) from expression data in order to measure the statistical dependence between genes [3]. In these methods, a link between two nodes is established if it exhibits a significant score estimated by mutual information. The role of the mutual information estimator is therefore essential to guarantee a high accuracy rate. Notwithstanding, few experimental studies about the impact of the estimator on the quality of the inferred network exist [4]. To the best of our knowledge, this paper presents the first comprehensive experimental comparison of several mutual information estimation techniques and state-of-theart inference methods like MRNET [3], ARACNE [5], and CLR [6]. An additional contribution of this paper is the study of the impact of the correlation estimator (notably Spearman and Pearson) on the mutual information computation once a hypothesis of normality is done. Interestingly enough, the Spearman-and the Pearson-based information estimators emerge as the most competitive techniques once combined with the MRNET and the CLR inference strategies, respectively.
The first part of the experimental session aims at studying the sensitivity to noise and missing values of different discretization, estimation, and network inference methods. For this purpose, a synthetic benchmark is created by means of the SynTReN data generator [7].
In the second part, the techniques which appeared to be the most effective in the synthetic session are assessed by means of a biological microarray benchmark which integrates several public domain yeast microarray datasets.
The outline of the paper is as follows. Section 2 reviews the most important mutual information estimators. Section 3 introduces some state-of-the-art network inference algorithms. Section 4 contains the description of the synthetic data generator, the description of the real data setting, and the related discussions of the results. Section 5 concludes the paper.

Estimators of Information
An information theoretic network inference technique aims at identifying connections between two genes (variables) by estimating the amount of information between them. Different information measures exist in the literature [8]. In this article, we focus on the mutual information measure and the related estimation techniques. Note that, if the estimation technique has been conceived for discrete random variables, a discretization procedure has to be executed before applying the estimation procedure to expression data.

Mutual Information.
Mutual information is a wellknown measure which quantifies the stochastic dependency between two random variables without making any assumption (e.g., linearity) about the nature of the relation [9].
Let X be a discrete random vector whose ith component takes values in the discrete set X i of size |X i |. The (i, j)th element of the mutual information matrix (MIM) associated to X is defined by where the entropy of a discrete random variable X i is defined as and I(X i ; X j ) is the mutual information between the random variables X i and X j .

Entropy Estimation.
In practical setups, the underlying distribution p of the variables is unknown. Consequently, the entropy terms in (1) cannot be computed directly but require an estimation. Many different approaches to entropy estimation have been introduced. In this paper, we restrict the choice to the following five estimators: empirical, Miller-Madow, shrink, Pearson and Spearman correlation.

Empirical.
Let X be a continuous random variable taking values in the real interval [a, b]. Suppose the interval is partitioned into |X| bins, where X denotes the bin index vector, nb(x k ) denotes the number of data points in the kth bin, and m = k∈X nb(x k ) stands for the total number of observations. The empirical estimator, also known as the maximum likelihood estimator, is the entropy of the empirical distribution It has been shown in [10] that the asymptotic bias of this estimator amounts to

Miller-Madow.
The Miller-Madow estimator [10] corrects the biased empirical estimator by removing the estimated bias term from it (4): This estimator reduces the bias of (3) without increasing its variance.

Shrink.
The shrink estimator [8] combines two different estimators, one with low variance and one with low bias, by using the weighting factor λ ∈ [0, 1]: EURASIP Journal on Bioinformatics and Systems Biology 3 Let λ * = arg min be the value minimizing the mean square function [8]. It has been shown in [11] that the optimal λ is given by

Pearson Correlation.
Correlation is a statistic measuring the strength and the direction of the linear relationship between two random variables. The Pearson correlation between two random variables X and Y is defined as Correlation takes values in [−1, 1], where |ρ| = 1 denotes a linear relation between the variables X and Y . If the variables are independent, the correlation is equal to zero while the opposite is not necessarily true (e.g., nonlinear dependency). It can be shown that correlation and mutual information are related if the joint distribution is normal. Let be the density of a multivariate Gaussian variable X with mean μ and covariance matrix C. The entropy of this distribution is given by where |C| is the determinant of the covariance matrix [12]. The mutual information between two variables X i and X j is then given by where ρ is the Pearson's correlation.
Since the functional relation (13) between the mutual information and the correlation is a monotone function, it is sufficient to use ρ 2 when computing this value.
The Pearson correlation can be estimated from the measurements x i and y i of two genes X and Y by the following equation: 2.2.5. Spearman Correlation. The Spearman rank correlation coefficient is a special case of the Pearson correlation in which the data are converted to rankings before calculating the coefficient. The Spearman correlation can be calculated using (14), where the terms x i and y i are replaced by their respective ranks. Note that the Spearman rank correlation coefficient generalizes the Pearson correlation coefficient by being able to detect not only linear relationships between the variables but also any kind of monotone relation without making any assumptions about the distributions of the variables.

Discretization Methods.
The mutual information estimators in Sections 2.2.1, 2.2.2, and 2.2.3 apply to discrete random variables. In order to use them for continuous random variables, a discretization step is required. The two most widely used methods for discretization are the equal width and the equal frequency methods [13].
Equal Width. This discretization method partitions the domain of X into |X| subintervals of equal size. As a consequence, the number of data points in each bin is likely to be different.
Equal Frequency. This method divides the interval [a, b] into |X| subintervals, each containing the same number of data points. It follows that subinterval sizes are typically different.
The number of subintervals should be chosen so that all bins contain a significant number of samples. In [14], the authors propose to use |X| = √ m, where m is the total number of samples.

Network Inference Algorithms
The network inference proceeds in two steps. In the first step, the mutual information matrix is calculated. In the second step, the chosen algorithm is applied to the mutual information matrix in order to compute a score that is used to weigh the links between network nodes. [3] is based on the maximum relevance/minimum redundancy (MRMR) feature selection technique [15]. This iterative selection technique chooses at each step, among the least redundant variables, the one having the highest mutual information with the target.

The MRNET Method. The MRNET method
The method ranks the set of inputs according to a score which is the difference between the mutual information with the output variable Y (maximum relevance) and the average mutual information with the previously ranked variables (minimum redundancy). The network is inferred by deleting all edges whose score lies below a given threshold.
Direct interactions should be well ranked whereas indirect interactions should be badly ranked. In the first step, variable X i which has the highest mutual information to the target Y is selected. The second selected variable X j will be the one with a high information I(X j ; Y ) to the target and at the same time a low information I(X j ; X i ) to the previously selected variable.

EURASIP Journal on Bioinformatics and Systems Biology
In the next steps, given a set X S of selected variables, the criterion updates X S by choosing the variable that maximizes the score which can be described as a relevance term minus a redundancy term. For each pair {X i , X j }, the algorithm returns two scores s i and s j and computes the maximum of the two. All edges with a score below a given threshold are then deleted.

The ARACNE Method.
The algorithm for the reconstruction of accurate cellular networks (ARACNEs) [5] is based on the data processing inequality [16]. This inequality states that if the interaction between X 1 and X 3 depends on X 2 , then The algorithm assigns a weight to each pair of nodes which is equal to the mutual information between the variables. Then, the minimal mutual information between three variables is computed, and eventually the edge with the lowest value is interpreted as an indirect connection and removed if the difference between the two lowest weights is above a given threshold.

The CLR Method.
In the context likelihood or relatedness (CLR) algorithm [6], the mutual information is calculated for each pair of variables. Then, a score related to the empirical distribution of these MI values is computed. In particular, instead of considering the information I(X i ; X j ) between two variables X i and X j , the algorithm takes into account the score z i j = z 2 i + z 2 j , where and μ i and σ i are, respectively, the mean and the standard deviations of the empirical distribution of the mutual information values I(X i , X k ), k = 1, . . . , n.

Experiments
This section contains two parts. In the first part, several inference methods and estimators are applied to synthetic datasets with different noise and missing values configurations. The aim of this part is to identify the best combination of estimator and inference method. Once the assessment on the synthetic benchmark is done, the best performing techniques are then applied to a biological problem. The aim of this second experiment is to assess the capability of the algorithms of discovering interactions of the yeast transcriptome uniquely on the basis of expression data. All computations were carried out using the R-package MINET [17] (http://cran.r-project.org/web/packages/ minet). This recently introduced package allows the use of three different inference methods, namely, ARACNE [5], CLR [6], and MRNET [3].
The following entropy estimators are also made available to calculate the mutual information: empirical, Miller-Madow, shrink, and Pearson correlation.
Note that, in order to apply the first three estimators to expression data, two different discretization methods are implemented: equal frequency and equal width discretization with default size |X| = √ m.

Synthetic Data
The synthetic benchmark relies on several artificial microarray datasets generated by the SynTReN generator [7]. This simulator emulates the gene expression process by adopting topologies derived from subnetworks of E.coli and S.cerevisiae networks. Interaction kinetics are modeled by nonlinear differential equations based on Michaelis-Menten and Hill kinetics.
We used the SynTReN generator to create twelve benchmark datasets whose number m of samples and number n of genes are detailed in Table 1.

Introducing Missing Values.
In order to study the impact of missing values, expression values were removed from the generated datasets. The number of missing values is distributed according to the β(a, b) distribution with parameters a = 2 and b = 5. The maximal allowed number of missing values is a third of the entire dataset. This distribution was utilized, instead of the uniform distribution, because the latter one could have favored the empirical estimator.

Setup.
For each experiment, ten repetitions were carried out. Each dataset was analyzed using three inference methods (i.e., MRNET, ARACNE, and CLR) and the following estimators: Pearson correlation, empirical, Miller-Madow, shrink, and the Spearman correlation coefficient. The empirical, the Miller-Madow, and the shrink estimator were computed applying the equal width and the equal frequency discretization approaches. Furthermore, the computation was carried out with and without additive Gaussian noise (having 50% variance of the observed values). Each of these setups was also assessed with introduced missing values.

Validation. Network inference algorithms infer either the presence or the absence of an edge for each pair of nodes.
Similarly to classification, we define the possible outcomes of inference as follows. A true positive (TP) occurs when an edge is correctly predicted as existing, a false positive (FP) occurs when a nonexisting edge is inferred, true negative (TN) occurs when a nonexisting edge is not inferred, and false negative (FN) occurs when an existing edge is not detected.
Precision measures the fraction of real edges among the ones classified as positive while recall quantifies the fraction of real edges that are correctly inferred. A weighted harmonic average of precision and recall is returned by the F-score [18]: which attains its maximum value 1 when the returned network is without any error.
To validate the simulation's results, the maximal F-score was computed for each experiment. Using a paired t-test, the maximal F-scores were then compared and statistically validated.

Discussion of Results.
The results of the synthetic benchmark are collected in Table 2 which returns the Fscore for each combination of inference method, mutual information estimator, and nature of the dataset (noisy versus not noisy, complete versus missing data). Note that the maximal F-score is highlighted together with the F-scores which are not significantly different from the best.
We analyze the results according to four different aspects: the impact of the estimator, the impact of the discretization, the impact of the inference algorithm, and the influence of sample and network size.
The section concludes with the identification of the best combination of inference algorithm and estimator.
Impact of the Estimator. In case of complete datasets with no noise, the empirical and the Miller-Madow estimators with equal-frequency binning lead to the highest F-scores for the MRNET and the ARACNE inference methods. The Spearman correlation is not significantly different from the best, in case of ARACNE, and is close to the best in case of MRNET. The CLR method is less sensitive to the estimator, and the best result is obtained with the Pearson correlation.
In case of noisy data or missing value (NA) configurations, the Pearson correlation and the Spearman correlation lead to the highest F-score for all inference methods. A slight better accuracy of the Pearson correlation can be observed in presence of missing values. The Spearman correlation outperforms the other estimators in MRNET and ARACNE when complete yet noisy datasets are considered. In CLR, Pearson and Spearman correlations lead the ranking without being significantly different.
Impact of the Discretization. In case of complete datasets with no noise, the equal frequency binning approach outperforms the equal width binning approach for all discrete estimators. The gap between the two discretization methods is clearly evident in MRNET and less striking in ARACNE and CLR. In case of noisy or missing data configurations, differences are attenuated.
Impact of the Inference Algorithm. In case of complete datasets with no noise, the MRNET inference technique outperforms the other algorithms.
The situation changes in presence of noisy or missing values. Here, CLR appears to be the most robust by returning the highest F-scores for all combinations of noise and missing values.

Impact of Number of Sample and Network
Sizes. The role of network size is illustrated in Figure 1 (first row) which shows how the F-score decreases as long as the network size increases. This behavior can be explained by the increasing difficulty of recovering a larger underlying network in front of an increasing dimensionality of the modeling task.
In Figure 1 (second row), the values of the F-score seem not to be influenced substantially by the number of samples.

Conclusion.
A concise summary of the previously discussed results is displayed in Table 3 which averages the accuracy over the different data configurations.
It emerges that the most promising combinations are represented by the MRNET algorithm with the Spearman estimator and the CLR algorithm with the Pearson correlation. The former seems to be less biased because of its good performance in front of nonnoisy datasets while the latter seems to be more robust since it is less variant in front of additive noise.

Biological Data.
The second part of the experimental session aims to assess the performance of the two selected techniques once applied to a real biological task.
We proceeded by (i) setting up a dataset which combines several public domain microarray datasets about the yeast transcriptome activity, (ii) carrying out the inference with the two selected techniques, and (iii) assessing the quality of the inferred network with respect to two independent sources of information: the list of interactions measured by means of an alternative genomic technology and a list of biologically known gene interactions derived from the TRANSFAC database.

The Dataset.
The dataset was built by first normalizing and then joining ten public domain yeast microarray datasets, whose number of samples and origin is detailed in Table 4. The resulting dataset contains the expression of 6352 yeast genes in 711 experimental conditions.

Assessment by ChIP-Chip
Technology. The first validation of the network inference outcome is obtained by comparing the inferred interactions with the outcome of a set of ChIP-chip experiments. The ChIP-chip technology, detailed in [28], measures the interactions between proteins and DNA by identifying the binding sites of DNA-binding proteins. The procedure can be summarized as follows. First, the protein of interest is cross-linked with the DNA site it binds to, then double-stranded parts of DNA fragments are extracted. The ones which were cross-linked to the protein of interest are filtered out from this set and reverse cross-linked. Also, their DNA is purified. In the last step, the fragments are analyzed using a DNA microarray in order to identify gene-gene connections. For our purposes, it is interesting to remark that the ChIp-chip technology returns for each pair of genes a probability of interaction. In particular we use, for the validation of our inference procedures, the ChIp-chip measures of the yeast transcriptome provided in [29].

Assessment by Biological
Knowledge. The second validation of the network inference outcome relies on existing biological knowledge and in particular on the list of putative interactions in Saccharomyces cerevisiae published in [30].  This list contains 1222 interactions involving 725 genes, and in the following we will refer to this as the Simonis list.
Note that this assessment considers as true only the interactions contained in the Simonis list. Figure 2 displays the ROC curves, and Table 5 reports the associated AUC for the following techniques: the ChIP-chip technique, the MRNET-Spearman correlation combination, the CLR-Gaussian combination, the CLR-Miller-Madow combination, the MRNET-Miller-Madow combination, and the random guess.
A first consideration to be made about these results is that network inference methods are able to be significantly better than a random guess also in real biological settings. Also the two combinations which appeared to be the best in synthetic datasets confirmed their supremacy over the Miller-Madowbased techniques also in real data.
However, the weak, though significative, performance of the networks inferred from microarray data requires some specific considerations.

EURASIP Journal on Bioinformatics and Systems Biology
(1) With respect to the ChIP-chip technology, it is worth mentioning that the information coming from microarray datasets is known to be less informative than the one coming from the ChIP-chip technology. Microarray datasets remain nowadays however more easily accessible to the experimental community, and techniques able to extract complex information from them are still essential for system biology purposes.
(2) Both the microarray dataset we set up for our experiment and the list of known interactions we used for assessment are strongly heterogeneous and concern different functionalities in yeast. We are confident that more specific analysis on specific functionalities could increase the final accuracy.
(3) Like in any biological validation of bioinformatics methods, the final assessment is done with respect to a list of putative interactions. It is probable that some of our false positives could be potentially true interactions or at least deserve additional investigation.

Conclusion
The paper presented an experimental study of the influence of the information measure and the estimator on the quality of the inferred interaction network. The study concerned both synthetic and real datasets. The study on synthetically generated datasets allowed to identify two effective techniques with complementary properties. The MRNET method combined with the Spearman correlation appeared to be effective mainly in front of complete and accurate measures. The CLR method combined with the Pearson correlation was ranked as the best one in the case of noisy and missing values.
The experiments on real microarray data confirmed the potential of these inference methods and showed that, though in presence of noisy and heterogeneous datasets, the techniques are able to return significative results.


extfieldsofstudy: Physics Mathematics

text:
Second Quantized Kolmogorov Complexity

The Kolmogorov complexity of a string is the length of its shortest description. We define a second quantised Kolmogorov complexity where the length of a description is defined to be the average length of its superposition. We discuss this complexity's basic properties. We define the corresponding prefix complexity and show that the inequalities obeyed by this prefix complexity are also obeyed by von Neumann entropy.

I. INTRODUCTION
Quantum physics is a more accurate description of physical phenomena than classical mechanics. If we therefore wish to speak about the complexity of some processes or some physical states in nature, it is more accurate to use a quantum mechanical model. An important question is (in very simple terms), given a physical system in some state, how difficult is it for us to reproduce it. If we wish to have a universal measure of this difficulty (which applies to all systems and states) a way to proceed is to follow the prescription of Kolmogorov.
Kolmogorov complexity is a very general measure of information. The Kolmogorov complexity of a state is defined as the shortest description of that state on a universal computer. The intuition is that if a state can be described very succinctly, then that state is very simple, whereas complex states have very long descriptions. Kolmogorov complexity is a well-developed field with a plethora of applications in areas such as computer science, physics, pure mathematics and philosophy [12]. In this paper, a second quantised Kolmogorov complexity based on average lengths of indeterminate length descriptions is defined. It is called second quantised because, as we shall explain, the physical interpretation of this complexity is of a system in the second quantisation. Its basic properties are then discussed; its physical interpretation, its incompressibility, the complexity of multiple copies of a state. We then define the corresponding prefix complexity and show that it is also incompressible, that it is related to von Neumann entropy, and that any inequality obeyed by the prefix complexity is also obeyed by von Neumann entropy.

II. SYNOPSIS
Section III describes the basic properties of classical Kolmogorov complexity. In Section IV, the related previous work in quantum information theory is described. In Section V, the second quantised Kolmogorov complexity based on average length descriptions is defined and its basic properties are discussed. In Section VI, the corresponding prefix Kolmogorov complexity is defined. It is shown that the complexity of a superposition is not additive and that the expected complexity of a mixture is closely related to its von Neumann entropy.

III. CLASSICAL KOLMOGOROV COMPLEXITY
Kolmogorov complexity is an information complexity based on the intuition that a simple string has a short description. The string 00000000000000000000, which can be described as "twenty 0's", seems much simpler than say 10010111011010100010 in which there is no obvious pattern (though one might exist). To avoid self-contradictory statements such as "the shortest string that cannot be described in less than one hundred words", Kolmogorov complexity is defined with respect to a Turing machine.
Definition III.1 (Kolmogorov complexity with respect to T ) The Kolmogorov complexity of a string x can be defined with respect to a particular Turing machine T as the length of the shortest string p, which when inputted into T , outputs x.
Sometimes it is useful to be able to input two strings x and y into a classical Turing machine. However, x and y cannot be obtained from the string z = xy without encoding where the string x ends. Here is a simple way to encode a pair or a sequence of strings as input.
Definition III.2 (Encoding ordered sequences) For any pair of binary strings x 1 and x 2 , let (x 1 , x 2 ) = 1 l(x1) 0x 1 x 2 (where 1 n means n copies of 1). For any sequence of binary strings For example, (110, 1000) = 11101101000. Reading 11101101000 from left to right, the first three 1s followed by a 0 show that the first string has length 3. The next three bits give the value of the first string 110, the remaining four bits give the second string 1000.
An essential feature of Kolmogorov complexity is that it does not really matter which Turing machine is used to define it. The Kolmogorov complexity of a string x is invariant in the sense that there is a universal Turing machine U such that for any Turing machine T a constant exists which bounds C T (x) − C U (x) for any x.

Theorem III.3 (Invariance theorem)
There is a universal Turing machine U such that for any Turing machine T there exists a constant c T (dependent only on T and U ) such that for all x: Each Turing machine has a finite set of instructions, hence the set of all Turing machines can be enumerated. Let T 1 , T 2 , . . . be an enumeration of the Turing machines. Let U be a Turing machine which on input (i, p), generates a description of the instructions of Turing machine T i and simulates T i on input p (i.e. U (i, p) = T i (p)). If p is a description of x on Turing machine T i , then where c T is a constant, independent of x, dependent on the number of bits used to describe i.
Let us now fix the universal Turing machine U in the invariance theorem, and define Kolmogorov complexity with respect to this reference machine U .

Definition III.4 (Kolmogorov complexity)
The Kolmogorov complexity of a string x is defined as the shortest description of x with respect to the universal Turing machine: where U is the fixed universal Turing machine as in the Invariance Theorem (Theorem III.

3).
Sometimes it is also useful to define the complexity of x conditional on knowing another string y. For example, conditional complexity can be used to define how much information y provides about x.

Definition III.5 (Conditional Kolmogorov complexity)
The conditional Kolmogorov complexity of a string x given a string y is defined as where U is the fixed universal Turing machine as in the Invariance Theorem (Theorem III.3).

A. Incompressibility
Many "long strings" have short descriptions. For example, there is a Turing machine T that outputs 2 2 2 n on input n, so for all n, 2 2 2 n can be described using log(n) + c bits. One might hope that many large strings can be described by short strings. However, the incompressibility theorem shows that not all strings are compressible.
Theorem III.6 (Incompressibility theorem) For any integer n > 0, there is at least one string x of length l(x) = n which has a Kolmogorov complexity is at least n.
Proof. The proof of the incompressibility theorem is a simple pigeon hole argument. There are 2 n strings of length n but only 2 0 + . . . + 2 n−1 < 2 n strings of length less than n. Therefore at least one string of length n cannot be compressed to a string of length less than n.

B. Prefix Kolmogorov Complexity
The standard Kolmogorov complexity C which has been described so far does not deal with prefix free strings. Kolmogorov complexity can be related simply to Shannon entropy by defining a prefix Kolmogorov complexity K where the descriptions are prefix free.
Another advantage of prefix complexity over standard complexity is that K is additive, that is K(x, y) ≤ K(x) + K(y) + c (since (x, y) can be described by concatenating prefix free descriptions of x and y). On the other hand, C(x, y) ≤ C(x)+C(y)+c does not hold in general [12]. There are (n + 1)2 n pairs (x, y) such that l(x) + l(y) = n. Thus by incompressibility, there exists at least one such pair (x, y) that has complexity

Prefix Kolmogorov Complexity
In order to define prefix Kolmogorov complexity, in which the descriptions are prefix free, let us define a prefix quantum Turing machine.

Definition III.7 (Prefix Turing machine) T is a prefix Turing machine if any two inputs x and y upon which T halts are prefix free.
This definition is equivalent to restricting all inputs to be infinite length and defining the length of the input to be the number of bits on the input tape that are used during computation. A universal prefix Turing machine U can be defined by enumerating the Turing machines T 1 , T 2 , . . . and using self-delimiting descriptions of each Turing machine. In this way, prefix Kolmogorov complexity is invariant up to an additive constant.

Definition III.8 (Prefix Kolmogorov complexity)
The prefix Kolmogorov complexity K of a string x is: where U is the reference universal prefix machine.

Prefix Kolmogorov Complexity and Shannon Entropy
The expected prefix complexity of a random variable is closely related to the random variable's Shannon entropy. The expected prefix complexity of a random variable is defined as its average prefix complexity. Definition III.9 (Expected prefix Kolmogorov complexity of a random variable) Let X be a random variable. The expected prefix Kolmogorov complexity of X is: On the other hand, the complexity of a random variable X is the complexity of describing X itself, given some suitable encoding. where x 1 ≤ x 2 ≤ . . . ≤ x m and for all x with P (X = x) > 0, there exists a unique 1 ≤ i ≤ m such that x = x i and p i = P (X = x). The prefix Kolmogorov complexity of X is the prefix Kolmogorov complexity of its encoding: Since a compression algorithm can be implemented by a Turing machine, E(K(X)) and H(X) are closely related.

Lemma III.11 (Relationship between H and K)
There exists a constant c such that for any random variable X, Proof. By Shannon's Noiseless Coding Theorem for Lossless Codes [28], there is no prefix free encoding of X whose expected length is less than X, thus E(K(X)) ≥ H(X). On the other hand, by describing the random variable X, a prefix code F which encodes X using E(F (X))) = H(X) + 1 bits can be described. Thus E(K(X)) ≤ H(X) + K(X) + c.

IV. PREVIOUS WORK
In this section, the previous attempts to define a quantum Kolmogorov complexity and some of the previous work on indeterminate length quantum strings are described. The first attempt to define a quantum Kolmogorov complexity was by Svozil [29] in 1996. The attempts to define a quantum Kolmogorov complexity [3,7,14,27,29,30,31,32] assume that the descriptions have determinate lengths. Second quantised Kolmogorov complexity differs from the others in that it uses indeterminate length quantum strings.

A. Indeterminate Length Quantum Strings
Indeterminate length quantum strings have been discussed in the context of lossless quantum data compression [1,4,23,26]. When a mixture of non-orthogonal strings is compressed using a variable length string, the resulting compressed state may be in a superposition of different lengths. Such a string is called an indeterminate length string [26].
Definition IV.1 (Indeterminate length string) |ψ = i α i |i is an indeterminate length quantum string if there exists i and j with |α i | > 0 and |α j | > 0 and l(i) = l(j).
Determinate length strings of length n exist in the Hilbert space H ⊗n . Indeterminate length strings exist in the Fock space The analysis of indeterminate length strings in the Fock space has recently been discussed [20]. It was shown that an indeterminate string in the Fock space H ⊕ can be considered as a string on a quantum Turing machine, where a finite set of cells beginning from the first cell are non-blank. The other cells contain the character |# which is orthogonal to |0 and |1 .
Boström and Felbinger [4] defined two ways to quantify the lengths of indeterminate length strings.

Definition IV.2 (Lengths of indeterminate length strings) The base length L of an indeterminate length string is the length of the longest part of its superposition
The average length l of an indeterminate length quantum string is the average length of its superposition If the length of a quantum string is observed, then l is the expected length that is observed and L is the maximum length that can be observed.

From Lossless Coding to Lossy Coding
Schumacher and Westmoreland [26] demonstrated that by projecting onto n(S(E) + δ) qubits, if a mixture E ⊗n is encoded with a variable length condensable code, a fixed length lossy code can be obtained [6]. If E is a mixture with density operator ρ, where ρ's spectral decomposition is: Then E can be encoded by encoding each |i as a prefix free string of length ⌈− log(p i )⌉ with zero-padding. ρ ⊗n can be encoded in the same fashion. Almost every string |i in the typical subspace of ρ ⊗n has probability arbitrarily close to 2 −nS(ρ) as n grows large. Thus almost every string in the typical subspace of ρ is encoded as a string of length arbitrarily close to nS(ρ). By projecting onto n(S(ρ) + δ) qubits, the compressed state is projected onto the encoded typical subspace of ρ. The typical subspace can be decoded to obtain the original mixture E with arbitrarily high (but not perfect) probability and fidelity. Thus the minimum expected average length of a variable length code is related to von Neumann entropy.
From this encoding, it can be seen that the average lengths of condensable codes obey Kraft's inequality (if they did not, then a mixture could be lossily compressed to less than its von Neumann entropy).

Lemma IV.3 (Kraft's inequality for condensable strings) If ξ is a set of orthogonal condensable strings then
Proof. Let ξ = {|ψ 1 , . . . , |ψ n } be a set of orthogonal condensable strings and let Let ρ be density operator defined by: Then the expected average length of ρ is: As discussed above, it is possible to design a lossy quantum code which has rate of compression E(l(ρ)). If c > 1 then E(l(ρ)) < S(ρ). Therefore c ≤ 1 as required.

B. Quantum Kolmogorov Complexity
Berthiaume, van Dam and Laplante [3] defined a quantum Kolmogorov complexity based on Bernstein and Vazirani's model of a quantum Turing machine [2]. This quantum Kolmogorov complexity is invariant up to an additive constant with respect to a universal quantum Turing machine U which can simulate any other quantum Turing machine from its classical description. The quantum Kolmogorov complexity QC was defined as the base length of its shortest quantum description on U QC|ψ = min It was shown that the complexity of n copies of a state |ψ is at most The first term is the logarithm of the dimensions of the symmetric subspace H ⊗n p where H p is the space containing the shortest description of |ψ , p. The second term comes from describing n in a self-delimiting way. The third term comes from describing dim(H p ) = log(QC(|ψ ) in a self-delimiting way. The second and third terms contain a big-O term since the descriptions of n and dim(H p ) are self-delimiting so that they can be concatenated together with the symmetric vectors.
Müller [17,19] studied the precise definition of quantum Kolmogorov complexity in detail, and gave a detailed analysis of the invariance theorem of quantum Kolmogorov complexity. He showed that there is a universal reference Turing machine U that can simulate another quantum Turing machine T using a constant number of qubits, even if T and U have access to a different finite sets of gates (given that the time of computation is not known in advance). Müller [18] also gave a detailed proof that classical strings have the same classical and quantum Kolmogorov complexities up to an additive constant factor.

C. Quantum Kolmogorov Complexity based on Classical Descriptions
Vitanyi [32] defined a prefix quantum Kolmogorov complexity based on classical descriptions. The idea behind this complexity is as follows. Suppose that |p is a self-delimiting classical input to a quantum Turing machine T which outputs a state T |p = |φ and that |ψ is some state close to |φ . It can be said that |p is a description of |ψ but a penalty factor can be added depending on the distance between |ψ and |φ . Suppose |ψ = α|φ + β|φ ⊥ where |φ ⊥ is orthogonal to |φ . Then the idea is that |φ can be described by using an additional log(|β 2 |) to encode |φ ⊥ using lossless compression. Thus log(|β 2 |) is the penalty factor depending on the distance between |ψ and |φ . The conditional prefix free string complexity K Q of a string |ψ was defined as: The first term l(p) is the length of the shortest program, the second term is the number of bits used to encode the orthogonal state to |φ .
This complexity can be understood by considering an example.

Example IV.4 (Quantum Kolmogorov complexity base on classical descriptions) Consider describing the state
as |0 . Then the complexity of |ψ n is where c and k are constants independent of n.
More generally, any state |ψ = i α i |i can be described by describing the easiest part |i of |ψ and incurring a − log(1 − |α i | 2 ) penalty so that the complexity (based on classical descriptions) of |ψ is bounded by

D. Application of Classical Kolmogorov Complexity to Quantum Computation
There have been several papers [10,11,14,15,16,29] which apply classical Kolmogorov complexity directly to quantum mechanics. Laplante and Magniez [11] used Kolmogorov complexity to study lower bounds for randomized and quantum query complexity. Laplante, Lee and Szegedy [10] also used classical Kolmogorov complexity to study quantum algorithms. They produced new results in quantum computational complexity. Laplante, Lee and Szegedy showed that the quantum adversary argument can be used on formula size lower bounds. Thus using results in quantum computing, they produced new results in classical computational complexity.
Svozil [29] was the first to discuss defining a quantum Kolmogorov complexity back in 1996. Svozil used a circuit based model of quantum computation, and said that descriptions must be classical, so that the prefix complexity obeys Kraft's inequality. In the sense that the descriptions are purely classical, this is an application of classical Kolmogorov complexity to quantum information theory. Svozil described the basic properties of this complexity.
Mora and Breigel [14,15] also used classical Kolmogorov complexity to define the complexity of quantum states. According to Mora and Briegel, an important feature of a description of a quantum object is that the description can be copied [14], therefore a quantum description is necessarily not quantum, but classical. Therefore Mora and Briegel [14,15] defined the algorithmic entropy of a quantum state to be the classical Kolmogorov complexity of a circuit that describes the quantum state up to a given degree ǫ (unfortunately this complexity increases beyond a constant factor as ǫ decreases). Mora and Briegel showed that the algorithmic complexity of a quantum state can be bounded in terms of the Schmidt number of its entanglement (although the converse does not hold). Mora, Briegel and Kraus [16] applied algorithmic complexity to various problems in quantum communication and computation to produce new proofs of already known results. An application of a quantum Kolmogorov complexity would be to analyse a fully generalised quantum Maxwell's demon [24]. Mora, Briegel and Kraus [16] also applied the algorithmic complexity of quantum states to begin to look at the effect of entanglement on Maxwell's demon.

E. A Priori Probability
Gacs [7] and Tadaki [30,31] both defined quantum Kolmogorov complexity like measures based on probability theory. Gacs attempted to define a universal probability measure, which unfortunately does not correspond to any length measure [32]. Tadaki [31] extended the semi-POVM to infinite dimensions and derived a quantum generalisation of Chaitin's halting probability [5] as the probability of any measurement outcome on the maximal infinite dimensional semi-POVM.
As is usual in quantum information theory, Berthiaume et al assume that quantum strings are not in superpositions of different lengths. However, a quantum string might be in a superposition of a very simple string and a very complex string, in which case, its "shortest description" seems to naturally be a superposition of a very short string and a very long string. Therefore it seems natural to allow the shortest description to exist in a superposition of different lengths. The length of the shortest description is defined to be its average length.
Second quantised Kolmogorov complexity can be defined with respect to a specific Turing machine T .

Definition V.1 (Second quantised Kolmogorov complexity with respect to T )
The second quantised Kolmogorov complexity QC T of a string |ψ with respect to a quantum Turing machine T is: Each quantum Turing machine has a finite number of instructions. The quantum Turing machines can therefore be enumerated and a reference universal Turing machine can be defined using this enumeration. In this definition, |1 l(i) 0i is simply a prefix free description of i.
The general second quantised complexity can be defined with respect to this reference universal quantum Turing machine.

Definition V.3 (Second quantised Kolmogorov complexity)
The second quantised Kolmogorov complexity QC of a string |ψ is defined the minimum average length of a description of |ψ with respect to the reference quantum Turing machine U .
The conditional second quantised Kolmogorov complexity C of a string |ψ given a string |χ is: Following the same reasoning for classical Kolmogorov complexity, second quantised Kolmogorov complexity is invariant up to an additive constant (for simplicity, it is assumed that all quantum Turing machines have access to the same set of universal gates).

Examples
A simple example of second quantised Kolmogorov complexity is the complexity of |φ n = α|0 + β|n which is given by the average complexity of the two parts, |0 and |n : Unlike Berthiaume et al's quantum Kolmogorov complexity, the second quantised complexity of |φ n is continuous at |β| → 0 Another simple example of second quantised Kolmogorov complexity is to bound the complexity of a state from above by its average length, using the identity machine.

Lemma V.5 (Upper bound on complexity) There exists a constant c such that for any string |ψ
Proof. Let T I be the identity quantum Turing machine which copies its input to the output tape. Then there exists some j such that T I = T j where T 1 , T 2 , . . . is the enumeration of quantum Turing machines used in the definition of the reference universal quantum Turing machine. On input 1 l(j) 0j|ψ , the universal quantum Turing machine outputs |ψ . Thus any state |ψ can be described using at most l(|ψ ) + 2l(j) + 1 qubits.

A. Second Quantised Kolmogorov Complexity as Energy
Rallan and Vedral described a physical interpretation of the average length of indeterminate length strings as energy in a system in the second quantization [21]. This gives second quantised Kolmogorov complexity an intuitive physical interpretation.
A Hilbert space H ⊗n can be realised by a sequence of photons |φ 1 ⊗ . . . ⊗ |φ n in which |φ i represents exactly one photon with frequency ω i . The value of the qubit |φ i is realised by the polarisation of its photon, either horizontal |0 or vertical |1 . The absence of a photon at a particular frequency can be represented by |# which is orthogonal to |0 and |1 . Indeterminate length strings are obtained by allowing the number of photons to exist in superposition and ordering the photons by their frequencies.
The first |# (which can be in a superposition of positions) is used to mark the end of the string.
The frequency of each photon |φ i is chosen to be approximately equal so that ω i ≈ ω for some value ω. The energy in a superposition of photons is the average energy required to either create or destroy that superposition ( ω per photon of frequency ω where is Planck's constant). Thus the energy of an indeterminate length string of photons |φ is proportional to its average length and is given by (approximately) ωl(|φ ). The average length of an indeterminate length quantum string is therefore proportional to the energy within the string.
In this physical implementation of quantum mechanics, the second quantised Kolmogorov complexity of a state represents the minimum energy required to describe that state.

B. Incompressibility
A fundamental property of classical Kolmogorov complexity is that it is incompressible. Second quantised Kolmogorov complexity is also incompressible in the sense that it is not possible to compress a set of quantum strings arbitrarily. This incompressibility theorem is analogous to the incompressibility theorem given by Berthiaume et al [3]. Theorem V.6 (Incompressibility) Let |ψ 1 , . . ., |ψ m be quantum strings (which are possibly non-orthogonal). Then there exists 1 ≤ i ≤ m such that: The result is an application Schumacher and Westmoreland's average length compression scheme [26] (which was described in Section IV A 1). They showed that given a mixture of states if U is any prefix free encoding of the |ψ i 's then the expected average length after compression is bounded below by ρ's von Neumann entropy: (where ρ is defined as in the theorem). Since E(l(U (E))) ≥ S(ρ), it must be the case that for some i, So far, it has been assumed that U is prefix free. Suppose that E is compressed using a variable length unitary code V (which is not necessarily prefix free). Let S be the unitary operation so that S transforms each string |x into a self-delimiting string S|x . In which case, SV is a prefix free mapping. Using Eq. V B, there is some |ψ i such that: Rearranging gives the result.
The bound in the theorem can of course be improved by choosing a more efficient encoding of the length information in the proof (i.e. choosing a different function S).

C. Complexity of Multiple Copies
A simple but non-trivial example of second quantised Kolmogorov complexity is the complexity of n copies of a qubit. The second quantised complexity of n copies can be much smaller than the corresponding quantum Kolmogorov complexity of Berthiaume et al [3].

Theorem V.7 (Complexity of Multiple Copies) Let
Let X be a random variable such that for 0 ≤ i ≤ n: Then, given n, the conditional complexity of |ψ ⊗n is at most: where c X is dependent on X but not on n.
Proof. n copies of |ψ can be expanded out as: where S(i, n) is the symmetric superposition of strings containing i |0 's and n − i |1 's. Given n and a description of X, each S(i, n) can be described as a string of length log(|α i β n−i | 2 ) qubits. Thus each |ψ ⊗n can be described using H(X)+ c X qubits, where the constant c X comes from describing the probability distribution X.
This bound is not tight. If some state |ψ is close to |+ , then H(X) is large however if a basis change is performed (using n Hadamard operations) from {|0 , |1 } to {|− , |+ }, then H(X) is dramatically reduced in this basis.

VI. PREFIX COMPLEXITY
A prefix Kolmogorov complexity can be defined by defining a prefix quantum Turing machine which takes as input prefix free strings.

Definition VI.1 (Prefix quantum Turing machine) A quantum Turing machine T is a prefix quantum Turing machine if any two orthogonal inputs to T are prefix free.
As with classical Kolmogorov complexity, all inputs can be defined to have infinite length, and the average of the maximum lengths of the number of qubits used (on the input tape) during computation can be defined to be the length of the input. The prefix quantum Turing machines can then be enumerated to define a reference universal prefix quantum Turing machine in the same manner as for classical Kolmogorov complexity [12]. A prefix complexity can be defined with respect to the reference prefix Turing machine.

Definition VI.2 (Second quantised prefix Kolmogorov complexity)
Let U be the universal reference prefix quantum Turing machine. The second quantised prefix Kolmogorov complexity QK of a state |ψ is:

A. Incompressibility
In proving the incompressibility theorem for the non-prefix complexity (Theorem V.6) the incompressibility theorem for prefix complexity has inadvertently been proved. Here it is. Theorem VI.3 (Incompressibility of prefix complexity) Let |ψ 1 , . . ., |ψ m be quantum strings (which are possibly nonorthogonal). Then there exists 1 ≤ i ≤ m such that: Proof. See proof of Theorem V.6.

B. Relationship of Prefix Complexity to von Neumann entropy
Since the expected average length of an optimal encoding of a mixture is its von Neumann entropy, prefix complexity is related to von Neumann entropy. Let us define the expected complexity of a density operator in the same way that it is defined classically.

Definition VI.4 (Expected prefix Kolmogorov complexity of ρ) Let
be a density operator in its diagonalised form. The expected prefix Kolmogorov complexity of ρ is: A density operator may have more than one possible diagonalisation. The complexity of a density operator is therefore defined to be the minimum complexity of describing a mixture that corresponds to that density operator.

Definition VI.5 (Prefix Kolmogorov complexity of ρ)
Let E = {(p i , |ψ i )} be a mixture of quantum states. Let ≤ be a total ordering on quantum states and without loss of generality, suppose that |ψ 1 ≤ |ψ 2 ≤ . . . ≤ |ψ m . An encoding f of E is: The second quantised prefix Kolmogorov complexity of E is defined as: The second quantised prefix Kolmogorov complexity of a density operator ρ is defined as: The relationship between von Neumann is the same as for Shannon entropy and classical prefix complexity.
Theorem VI.6 (Relationship of S and QK) Let E = {(p i , |ψ i )} be a mixture of quantum states with density operator ρ. Let Then there exists a constant c, independent of ρ, such that Proof. By Schumacher and Westmoreland's result [26], if E is encoded by a prefix free encoding, then the expected average length of that prefix free encoding is bounded below by the von Neumann entropy of the mixture's density operator. Since the orthogonal inputs to a prefix Turing machine are prefix free, their expected length is bounded below by S(ρ). On the other hand, an expected length of S(ρ) + 1 qubits can be achieved by encoding ρ in its diagonal basis. There exists a Turing machine T ρ (which can be described using approximately QK(ρ) qubits) which carries out this encoding, hence the result follows.

C. Additivity of Superpositions
The incompressibility theorem (Theorem VI.3) can also be used to show that prefix second quantised Kolmogorov complexity is not additive in the sense that the complexity of a superposition is not bounded above or below by the complexity of its parts. In other words, the following two inequalities do not hold.
This additivity does not hold even when the states in the superposition are restricted to being orthogonal.

D. Inequalities of Von Neumann Entropy
It has been shown that the same inequalities hold for classical Kolmogorov complexity and Shannon entropy [8] and that the same inequalities hold for classical Kolmogorov complexity and the size of sets [9,25]. However, very little is known about the inequalities for von Neumann entropy and most of the known inequalities for von Neumann entropy can be derived from subadditivity [13]. We now show that the inequalities obeyed by second quantised prefix complexity are also obeyed by von Neumann entropy.
To discuss general inequalities, we first define some notation. For this, we follow Hammer, Romashchenko and Vereshchagin [8]. Let ρ X1⊗...⊗Xn = ρ X1 ⊗ . . .⊗ ρ Xn be any n-partite state state in the Hilbert space X 1 ⊗ . . .⊗ X n . For any W ⊆ {1, . . . , n}, let Then, since conditional and mutual entropies can be expanded out as the sums of joint entropies, any inequality of von Neumann entropy can be written as λ W E(QK(ρ WX )) ≥ 0 holds for all n-partite spaces X 1 ⊗ . . . ⊗ X n and for all states ρ ∈ X 1 ⊗ . . . ⊗ X n , then the inequality W ∈Z λ W S(ρ WX ) ≥ 0 also holds for all density operators ρ in all n-partite spaces X 1 ⊗ . . . ⊗ X n .
Proof. Let ρ be any density operator in some n-partite space X 1 ⊗ . . . ⊗ X n . Then for each set W ⊆ {1, . . . , n} and each integer m > 0: Let Y m i = X ⊗m i (we shall apply Eq. VI.8 to W Y m rather than W X ). Then Now (ρ ⊗m ) W Y m can be described by describing m, ρ and W . Thus Assuming that the corresponding inequality holds for second quantised complexity for all states ρ in all n-partite spaces (Eq. VI.8), as m grows large ≥ 0

VII. CONCLUSIONS
We have defined a second quantised Kolmogorov complexity that has an intuitive physical interpretation. We have discussed its basic properties. We have also shown that the second quantised prefix complexity is closely related to von Neumann entropy.

VIII. ACKNOWLEDGMENTS
We thank Sougato Bose and Andreas Winter for useful comments. We thank Markus Müller for making valuable points on previous versions of this work. We thank the Engineering and Physical Sciences Research Council in the UK for financial support. V. Vedral thanks the Royal Society and Wolfson Foundation for financial support. This work was partly supported by the National Research Foundation and Ministry of Education (Singapore).


Evaluating an Ontology-Driven WYSIWYM Interface

This paper describes an evaluation study of an ontology-driven WYSIWYM interface for metadata creation. Although the results are encouraging, they are not as positive as those of a similar tool developed for the medical domain. We believe this may be due, not to the WYSIWYM interface, but to the complexity of the underlying ontologies and the fact that subjects were unfamiliar with them. We discuss the ways in which ontology development might be influenced by issues stemming from using an NLG approach for user access to data, and the effect these factors have on general usability.

Introduction
In the PolicyGrid 1 project we are investigating how best to support social science researchers through the use of Semantic Grid (De Roure et al., 2005) technologies. The Semantic Grid is often described as an 'extension of the current Grid in which information and services are given well-defined meaning, better enabling computers and people to work in cooperation'. Semantic Grids thus not only share data and compute resources, but also share and process metadata and knowledge, e.g. through the use of RDF 2 (Resource Description Framework, a metadata model for making statements about resources) 1 Funded under the UK Economic and Social Research Council e-Social Science programme; grant reference RES-149-25-1027 (http://www.policygrid.org) 2 http://www.w3.org/RDF/ or OWL 3 (knowledge representation language for authoring ontologies). Numerous e-science applications rely on metadata descriptions of resources. But how does metadata come into existence? Ideally the user should create it. However, metadata creation is a complex task, and few users know how to create them in RDF. To enable our users to describe their resources, we need to provide a tool that facilitates creation, querying and browsing of metadata by users with no prior experience of such technologies.
Existing tools that provide access to RDF metadata are often graphical, e.g. (Handschuh et al., 2001;Catarci et al., 2004). However, we believe that, for social scientists, natural language is the best medium to use, as the way they conduct their research and the structure of their documents and data indicate that they are more oriented towards text than graphics. Natural language approaches include GINO (Bernstein and Kaufmann, 2006), an ontology editor with an approach reminiscent of Natural Language Menus (Tennant et al., 1983), and using Controlled languages such as PENG-D (Schwitter and Tilbrook, 2004). Such natural language approaches tend to restrict expressivity to ensure that every entry can be parsed, limiting the language and often making it stilted, so that there is a small learning curve before the user knows which structures are allowed. In order to maintain full expressivity and to shorten the learning curve, we have elected to use WYSIWYM (What You See Is What You Meant) (Power et al., 1998). This is a natural language generation approach where the system generates a feed-back text for the user that is based on a semantic representation. This representation is edited directly by the user by manipulating the feedback text. WYSI-WYM has been used by a number of other projects, such as MILE (Piwek et al., 2000) and CLEF (Hallett, 2006). As evaluation results in both of these projects were very positive (Piwek, 2002;Hallett et al., 2007), we felt that WYSIWYM would be a suitable approach to use in our work.
We have developed a metadata elicitation tool that enables users to create metadata in the shape of ontology instance data; the tool is driven by the ontologies that define those instances. We are currently implementing a WYSIWYM tool for querying, that uses the same interface as the metadata creation tool. We also aim to develop a tool for presenting the results of the query, and for browsing the descriptions in the database. These three tools will be integrated into one consistent interface, so that users can switch effortlessly between querying, browsing and editing ontology instance data. This aim is similar to the support that the graphical tool SHAKEN provides for ontology editing and browsing (Thoméré et al., 2002). We want to ensure that these tools are generic, so that if the ontologies change over time or are replaced, the tools will still function. That means that all domain specific information (as much as is possible) should be contained in the ontologies. In this paper we explore the ways in which Natural Language Generation issues influence ontology building and vice versa. This paper is structured as follows: section 2 describes the tool for metadata creation that we have implemented; section 3 discusses issues in ontology development and Natural Language Generation; and section 4 presents an evaluation study of the metadata creation tool. In section 5 the results of this study are discussed and compared to those of the CLEF project; we argue that different domains and ontologies affect the usability and complexity of metadata access interfaces.

The Metadata Creation Tool
We have developed a WYSIWYM tool that enables users to upload resources (e.g. acadamic papers, statistical datasets, interview transcripts) and create metadata descriptions for them, even if these users are unfamiliar with ontologies. First, the user selects the type of resource he is depositing (e.g. a Transcript). The tool then generates a brief feedback text that presents the information specified by the user. The feedback text contains anchors, phrases in red boldface and blue italics that signal where new information can be added. When the user clicks on an anchor, a menu pops up listing the kinds of information that can be added here (see Figure 1). After selecting a menu item, the user is prompted to enter an appropriate value; this may be a date, a free-text string, or another object that may or may not be in the text already. The feedback text is regenerated whenever the user has added some information.
The tool is driven by one or more ontologies. Their class hierarchies are presented when users are selecting a resource type, or creating a new object as range for a property. The anchors correspond to individuals in the ontology; the menu items to the properties of those individuals. The feedback text is divided into paragraphs which correspond to the individuals; each property of an individual is realised as (part of) a sentence in its paragraph. Each property in the ontology is associated with a linguistic specification, a Dependency Tree (Mel'cuk, 1988) that corresponds to a sentence. The specification has slots where the source and target of the property should be inserted, and is sufficiently detailed to support processes such as aggregation, through which the feedback text is made more fluent. For a more extensive description of the metadata cre-ation tool and its implementation, see Hielkema et al. (2007b).
In August 2007 we ran a pilot evaluation study (Hielkema et al., 2007a) on this tool. This study was heuristic in nature, with subjects discussing the interface with the experimenter while performing set tasks. It highlighted a number of aspects which we felt it was necessary to improve before embarking on the formal evaluation. Apart from there being standard usability considerations such as a need for better undo and help functions, it became evident that the underlying ontology was neither extensive enough nor sufficiently well-structured: subjects struggled to find the options they needed, and were often not satisfied with the options' names or their location in the sub-menus. We therefore decided that, as well as improving the basic usability of the interface, we needed to redevelop the ontology that was driving the interface. Users, we felt, would find it easier to navigate the menus when this ontology matched their mental model of the domain. Throughout the development of this new ontology, user requirements and feedback were gathered through a number of focus group sessions. The next section describes the ways in which this ontology development was affected by the demands of the metadata interface.

Ontologies in NLG
Portability has always been a major issue in NLG. Language generation involves the use of much information that is domain-specific, and cannot be generalised without a cost in the expressivity of the resulting text. If we want to create an application that is domain-independent, we have to find a way to store all domain-specific information in a structure that is easily extended or replaced.
We have decided to use an ontology, a common structure whose use has become widespread in knowledge representation. Ideally, we would like to create a generator that can be applied to any domain, provided there is an appropriate domain-specific ontology. But what information should such an ontology contain? How should it be structured? In this section we explore issues that occur when developing or adapting ontologies for use in the WYSI-WYM tool; we believe that this can at least in part be generalised to NLG. The ontologies we have used so far were developed at the same time as the WYSI-WYM tool, so that both tool and ontology influenced each other's development. We are currently adapting an ontology from another e-science project for use in our WYSIWYM interface, to further investigate such issues (see section 5).
There are a number of existing tools that generate language from ontologies, using various approaches. Wilcock (2003) describes an ontology verbaliser using XML-based generation. As Wilcock states, his approach is domain-specific, and therefore probably incompatible with more general ontologies (and presumably with ontologies from a different domain).
MIAKT (Bontcheva and Wills, 2004) is a system that generates textual medical reports from an RDF description. It uses a medical domain ontology and an NLG lexicon that contains lexicalisations for the concepts and instances in the ontology. In order to verbalise properties, MIAKT's surface realiser needs lexical specifications for them. Four basic property types are distinguished whose sub-properties can mostly be realised automatically through the grammar rules in the realiser. This technique increases the portability of the system, but does affect the variability and expressivity of the generator.
We do not aim to generate from any ontology in a domain, but to generate texts with high expressivity and clarity from ontologies that are designed in an 'NLG-aware' way. We are investigating what requirements an ontology has to meet in order to be usable for our application, so that for any domain an ontology can be built or adapted which we can use to produce a usable NL-interface. As many ontology developers are not linguists, ideally we want to support the adaptation to 'NLG-aware' ontologies without requiring linguistic expertise, for instance through a supporting software tool. Ontologies are primarily built to model domain-specific knowledge, making domain assumptions explicit, and to facilitate reasoning with this knowledge. These aims may sometimes conflict with the requirements of NLG applications, but they do frequently coincide (e.g. the need for clear, unambiguous resource names.

Domain Ontologies for WYSIWYM
What information does our WYSIWYM application need its ontologies to provide? First of all, the parts of it that will be shown to the user need to be easily mapped to natural language. The purpose of the tool is to support creation of ontology instance data by users unfamiliar with ontologies, so the parts they see should be comprehensible to novices. The names of properties are used to populate the popup menus, while the class names are shown in the class hierarchy. These names are mapped to natural language by replacing capitals and underscores with whitespace, and if necessary adding a determiner. Therefore, they need to correspond to phrases in natural language in order to be understood by the user, with individual words separated by capitals or underscores. If there is no intuitive NL-phrase to represent a class, it probably does not correspond to a concept in the domain either and might confuse the user, so it should be removed from the hierarchy. Classes whose instances are best presented by some distinctive name (e.g. Person or Paper) should have a name or title property whose value can be used (e.g. 'John'). For other classes (e.g. Interview), the class name can be used (e.g. 'some interview').
We need a linguistic specification for each property, sufficiently detailed to support aggregation and pronominalisation, but also to produce more than one surface form: a query is presented differently than a description, even if it contains the same information (compare the texts in Figure 1 and 2). The linguistic specification should be sufficiently rich to support the generation of these different surface forms. For this purpose we are using Dependency Trees, whose richness in both syntactic and semantic information provides ample support for such transformations. These trees can be associated with the domain ontology 4 . This specification also contains the header of the submenu in which the property should appear.
Some peculiarities in natural language are domain-independent. For instance, an address is presented in a very specific way and cannot be realised in the standard manner without sacrificing clarity (e.g. 'The address' street is Union Street. Its place is Aberdeen'). Such 'utility' classes are used across domains. In PolicyGrid we have created a utility ontology that contains classes such as 'Person', 'Address' and 'Date' 5 . Instances of these classes are generated to a special surface form. In order to get the best realisation from the WYSIWYM tool, domain ontologies should use the classes from this utility ontology. As the properties of the utility classes are already furnished with linguistic specifications, they are already NLG-aware. Another way to hasten the process is to use, where possible, properties from this ontology instead of those from the domain ontology.

WYSIWYM for Ontologies
What should the WYSIWYM application do in order to provide access to ontologies? For metadata creation it is essential that users can only produce 'correct' metadata, which does not violate the constraints in the ontology. The feedback text should be presented coherently, while the Text Planner only uses information that is either domain independent or present in the ontology. Perhaps most importantly, the application should support easy creation of the linguistic information that the ontology must contain, as we cannot expect ontology developers to have the linguistic expertise to create Dependency Trees. We are devising a way for users to create a specification by manipulating the surface form of a 'template' specification. We currently have 12 templates which represent commonly used sen-tences to present ontology properties in text. The user can fine-tune the surface form by adding adjectives, changing morphological information and the root of individual words; actions for which only a basic linguistic knowledge is needed. This approach is outlined in more detail in (Hielkema et al., 2007b). The main challenge with this approach is that the specification is used to generate two surface forms; it remains to be seen whether a specification that is fine-tuned through one surface form will accommodate the accurate generation of another.
The Penman Upper Model (Bateman, 1990) supports the specification of linguistic information through a different approach. The Upper Model is a domain-independent ontology that supports sophisticated NLP. To make a domain ontology available for NLP, its resources have to be placed in the hierarchy of the Upper Model; their place there determines their surface realisation. This task appears to require considerable linguistic expertise, but like the creation of our Dependency Trees could probably be made easier for non-linguists through some specialpurpose interface.

Usability Evaluation
The best evaluation of our tool would be to let users deposit their resources in real-life contexts, but our tool is not ready for a full deployment. Another way would be to compare its usability to another metadata creation tool in an experiment where users completed the same tasks with both tools. Unfortunately, most metadata tools focus on providing support for ontology editing (e.g. Protégé 6 or GINO (Bernstein and Kaufmann, 2006)), or query formulation (e.g. SEWASIE (Catarci et al., 2004)). A number of tools for metadata creation use formal (RDF) or controlled languages, which are difficult to use for those wholly unfamiliar with formal logic. Other tools were developed for one specific purpose, e.g. CREAM (Handschuh et al., 2001) which was developed for the annotation of web pages, and could not easily be adapted to our purposes. We were not aware of any tool that we could adapt to the e-social science ontologies and thus use in an experiment.
Alternatively, we could have compared our interface to direct authoring of RDF; but in an environ-ment where most users have no experience of ontologies or metadata this seemed spurious. Instead, we adopted an approach similar to that used in the CLEF project (Hallett et al., 2007). They evaluated their WYSIWYM system (which enabled users to create SQL queries for a database in a medical domain) by measuring the performance of fifteen subjects on four consecutive tasks, after a brief introduction. These subjects were all knowledgeable in the domain, and all but two knew the representation language of the repository and how the data contained in it was structured. These subjects achieved perfect results from the second task onwards, and became faster with each task, especially after the first. We also expected users to become faster and more accurate with each completed task, and indeed hoped for perfect scores on their last task.
Subjects Sixteen researchers and PhD students from various social science-related disciplines participated in the experiment. None of them had prior experience of the metadata elicitation interface, and only two of the subjects had any previous experience of using ontologies. The ontology driving the system models the description of social science resources and was based on requirements gathering sessions, in which a few subjects had participated. None of the subjects knew its precise structure.
Methodology After providing some information about their background, subjects viewed a video introduction 7 of six minutes. This video showed the construction of a simple resource description, highlighting the main functionalities of the interface, while a voice-over explained what was happening on the screen.
Subjects were then handed four short resource descriptions expressed as paragraphs of English (see 'Materials') and asked to reproduce these descriptions as closely as possible using the tool. To avoid making the choice of the correct options too obvious, we tried to avoid phrases that corresponded literally to those in the menus. Each subject received the descriptions in a different order, in case there were differences in the complexity of the tasks. Subjects were allowed as much time as they needed to complete each task. For each task, the tool recorded the completion time, the produced description, the number of operations used to produce it, and the frequency with which various operation types were used, such as 'undo' or the 'help' functions. After the subjects had completed all four tasks, they were asked to rate the usability (very difficult -difficult -OK -easyvery easy) and usefulness (useless -not much use -adequate -useful -very useful) of the tool on a five-point Likert scale, and to note any feedback they might have. The entire experiment took on average 50 min. per subject.
Materials We used four resource descriptions, one of which was: You are depositing the transcript of an interview that was held by Dr. Rivers in 1907, at Eddystone. The interview mainly discussed 'male-female relationships', 'burial practices' and 'the social impact of the interdiction on head hunting'. Access to this transcript should remain private. Figure 1 shows the corresponding description that could be produced with the tool. The separation of the transcript from the interview is an example of the clear distinctions necessary for knowledge representation. In natural language, this distinction would not necessarily be made, and indeed this step was missed by a number of users.
To ensure that tasks did not repeat identical subtasks, we tried to use different parts of the ontology in each task. Every task described a different resource type (conference paper, transcript, academic paper, report), which corresponded to a different class in the ontology. We were also careful to choose varying menu items (corresponding to properties in the ontology), although some repetition was unavoidable (e.g. specifying names). In fact, a reallife use of the tool would involve rather more task repetition (specifying titles, authors and dates would be necessary for practically any resource) than the artificial descriptions in this study.

Results
To analyse the accuracy of the produced descriptions, we divided each description task into 8 to 10 subtasks. For the task shown in the previous paragraph, these subtasks were: • Specify that you are depositing a 'Transcript' • Specify that access is private • Specify that it is a transcript of an 'Interview' (creating an 'interview' object) -Specify the three main topics -Add an interviewer (creating a 'Person' object) * Call this person 'Dr. Rivers' -Specify the location of the interview -Specify the date of the interview As some subtasks are more complicated than others and take longer, we did not try to give each task exactly the same number of subtasks, but instead ensured that all tasks needed the same number of operations (e.g. menu item selections, button clicks, etc.) in order to be completed. Each subtask that was missing or completed differently than in the description shown in 'Materials' was counted as one error. Erroneous ways to complete subtasks included choosing a different menu item and adding information to the wrong object. For instance, a number of subjects, instead of specifying an interviewer for the interview, added a creator for the transcript; this was counted as one erroneously completed subtask, and therefore one error.
The list of subtasks above shows that some subtasks depend on the successful completion of other tasks; for instance, you cannot add an interviewer unless you have created an 'interview' object. We therefore analysed two error counts: the total number of errors, and the 'avoidable' errors. The 'avoidable' errors were the total number of errors minus those subtasks that depended on another subtask that was missing or had been completed incorrectly.
We analysed the mean completion times, number of operations used and the two error counts of the tasks that were completed first, second, third and last, using a repeated measures ANOVA (see Table 1 for the means and standard deviations). Mean completion times went down significantly (Huynh-Feldt p-value < 0.01). Tukey's HSD post-hoc (applied to a univariate ANOVA, with task order as the independent variable) test shows that both the third (p-value < 0.01) and the fourth (p-value 0.030) were completed significantly faster than the first task. However, no significant differences were found for the number of operations (Huynh-Feldt p-value 0.062), the total number of errors (Huynh-Feldt p-value .322) or the number of avoidable errors (Huynh-Feldt p-value .931).
Subject feedback on the tool was positive: it was perceived as useful (µ 3.94; 1='useless', 5='very useful'), and OK or easy to use (µ 2.69; 1='very easy', 5='very difficult'). Five subjects expressed a preference for a form-based interface, and five others for a NL-interface such as the one tested. In feedback, subjects indicated a desire for more formbased elements in the interface, to speed up the creation of the standard description elements (e.g. name/title, author), and complained that the environment was initially unfamiliar, with some menu items overlapping. This unfamiliarity meant that items that were necessary to complete the description were often overlooked; subjects often solved this by choosing the closest approximation they could find, e.g. 'creator' instead of 'interviewer'.

Discussion and Future Work
Although users quickly gained speed using the tool, and were positive in their feedback, the evaluation results are not nearly as positive as those found for CLEF (see section 4). The mean number of errors decreased, but this effect was not significant and only five out of sixteen subjects received a perfect score on the last task (four other subjects performed some earlier task(s) perfectly). Evidently there is a difference in usability of both tools -but what causes it? No doubt the difference can partly be ascribed to differences in the implementation of the interface. However, the most common feedback we received from the subjects was that they were overwhelmed by the large number of options available to them. Each class in the social science ontology has on average 30 properties, which means a description with three objects provides 90 options. In contrast, the number of available options in the CLEF system was deliberately kept small (max. three) for 'non-terminal anchors'. Especially in the first task, users had trouble finding the option they wanted, and although it became easier in the later tasks as they familiarised themselves with the system, the results indicate that it remained a problem. This was likely aggravated by our deliberate avoidance of subtask-repetition; more standard descriptions, which always involve titles and authors, might have produced a greater learning effect. CLEF was developed for a medical domain, which is well defined and understood by the experimental subjects. The social science domain encompasses many different theories and concepts, not just about what subjects are investigated, but also about how the research should be conducted. PolicyGrid has tried to develop an ontology that the different disciplines in social science could be satisfied with. As a result, it is quite large and complex, and most users will only recognise parts of it. Thus the number of available options in the tool driven by this ontology is large, and users have to explore the ontology and learn to navigate it where their domain knowledge does not suffice. This flattens the learning curve and decreases the usability of the tool.
Half the users preferred a form-based interface over an NLG interface. Although forms are an easily understood mechanism which are just as familiar to users as natural language, we have three reasons for preferring the WYSIWYM approach. First, the large number of options in the ontology means that a form would reach truly daunting proportions. Sec-ond, we want our resource descriptions to be connected through shared people, projects, institutions, etc; using the expressivity that RDF offers us. This would be more difficult to achieve in an interface where the user completes a form by providing each property with a free-text description. Thirdly, forms can be confusing for the user as well; the brief descriptions provided for each element are frequently ambiguous and therefore misunderstood. An NLGinterface, which provides feedback by presenting the property in a complete sentence, should help to clarify the meaning of the property name for the user.
As we discussed earlier, there are many constraints on the development of domain ontologies that can be accessed through NLG, and the evaluation indicates that the structure of the ontology is essential for the tool's usability. Still, the evaluation is sufficiently positive that we believe the WYSIWYM approach suitable for providing access to ontologies, especially for users who are unfamiliar with ontologies or their graphical representations. Navigation could be made easier by providing users with an overview of the underlying ontology, possibly presented as an index of objects, and the information that can be specified about each object. An online manual with some worked examples and screenshots might also help users get started on the more obvious parts of a description. We are currently attempting to adapt an ontology developed in another UK escience project 8 for use in the WYSIWYM metadata elication tool. Instead of assuming the depositing of a resource, this ontology was developed to capture user-elicited metadata for video annotation. Part of this metadata is captured automatically, part of it is elicited from the user. We hope that the adaptation of an ontology that was originally developed for a different purpose for use in an NLG application will highlight other issues involved in the use of ontologies in NLG.
One way in which subjects did tasks erroneously was by using the 'hasComment' property when they could not find the option they wanted. This is not precisely wrong: the metadata it produces is correct and any human readers will understand the description. But it is not the best description for querying purposes. We think some subjects may have 8 http://www.ncess.ac.uk/research/digital records/ had trouble grasping the exact purpose of the produced descriptions. We hope that users who have used the query tool to find (the descriptions of) resources, will have a better understanding of what an effective metadata description is.
We intend to run more evaluation experiments, to assess the usability but also the usefulness of the combined toolset. Rather than asking subjects to copy descriptions or queries, we may ask them to find a particular resource, or to try to deposit and describe one of their own papers. If possible, it would also be interesting to see how they perform the same tasks using a different interface for metadata access, e.g. a graphical interface such as SHAKEN (Thoméré et al., 2002).

Conclusion
We have presented a WYSIWYM interface for the creation of RDF metadata, which will be extended by the addition of querying and browsing tools. This tool is driven by an ontology that contains all domain-specific information needed to present it in natural language. We have highlighted a number of issues in ontology development for access through NLG. We have evaluated the tool's usability through an experiment with potential users. The results were encouraging, but indicate that the structure and familiarity of the underlying ontology strongly influence the usability of the interface.