Monolingual Machine Translation for Paraphrase Generation

We apply statistical machine translation (SMT) tools to generate novel paraphrases of input sentences in the same language. The system is trained on large volumes of sentence pairs automatically extracted from clustered news articles available on the World Wide Web. Alignment Error Rate (AER) is measured to gauge the quality of the resulting corpus. A monotone phrasal decoder generates contextual replacements. Human evaluation shows that this system outperforms baseline paraphrase generation techniques and, in a departure from previous work, offers better coverage and scalability than the current best-of-breed paraphrasing approaches.

Introduction
The ability to categorize distinct word sequences as "meaning the same thing" is vital to applications as diverse as search, summarization, dialog, and question answering. Recent research has treated paraphrase acquisition and generation as a machine learning problem (Barzilay & McKeown, 2001;Lin & Pantel, 2002;Shinyama et al, 2002, Barzilay & Lee, 2003, Pang et al., 2003. We approach this problem as one of statistical machine translation (SMT), within the noisy channel model of Brown et al. (1993). That is, we seek to identify the optimal paraphrase T* of a sentence S by finding: We describe and evaluate an SMT-based paraphrase generation system that utilizes a monotone phrasal decoder to generate meaning-preserving paraphrases across multiple domains. By adopting at the outset a paradigm geared toward generating sentences, this approach overcomes many problems encountered by task-specific approaches. In particular, we show that SMT techniques can be extended to paraphrase given sufficient monolingual parallel data. 1 We show that a huge corpus of comparable and alignable sentence pairs can be culled from ready-made topical/temporal clusters of news articles gathered on a daily basis from thousands of sources on the World Wide Web, thereby permitting the system to operate outside the narrow domains typical of existing systems.

Related work
Until recently, efforts in paraphrase were not strongly focused on generation and relied primarily on narrow data sources. One data source has been multiple translations of classic literary works (Barzilay & McKeown 2001;Ibrahim 2002;Ibrahim et al. 2003). Pang et al. (2003) obtain parallel monolingual texts from a set of 100 multiply-translated news articles. While translation-based approaches to obtaining data do address the problem of how to identify two strings as meaning the same thing, they are limited in scalability owing to the difficulty (and expense) of obtaining large quantities of multiply-translated source documents.
Other researchers have sought to identify patterns in large unannotated monolingual corpora. Lin & Pantel (2002) derive inference rules by parsing text fragments and extracting semantically similar paths. Shinyama et al. (2002) identify dependency paths in two collections of newspaper articles. In each case, however, the information extracted is limited to a small set of patterns. Barzilay & Lee (2003) exploit the metainformation implicit in dual collections of news-wire articles, but focus on learning sentence-level patterns that provide a basis for generation. Multisequence alignment (MSA) is used to identify sentences that share formal (and presumably semantic) properties. This yields a set of clusters, each characterized by a word lattice that captures n-grambased structural similarities between sentences. Lattices are in turn mapped to templates that can be used to produce novel transforms of input sentences. Their methodology provides striking results within a limited domain characterized by a high frequency of stereotypical sentence types. However, as we show below, the approach may be of limited generality, even within the training domain.

Data collection
Our training corpus, like those of Shinyama et al. and Barzilay & Lee, consists of different news stories reporting the same event. While previous work with comparable news corpora has been limited to just two news sources, we set out to harness the ongoing explosion in internet news coverage. Thousands of news sources worldwide are competing to cover the same stories, in real time. Despite different authorship, these stories cover the same events and therefore have significant content overlap, especially in reports of the basic facts. In other cases, news agencies introduce minor edits into a single original AP or Reuters story. We believe that our work constitutes the first to attempt to exploit these massively multiple data sources for paraphrase learning and generation.

Gathering aligned sentence pairs
We began by identifying sets of pre-clustered URLs that point to news articles on the Web, gathered from publicly available sites such as http://news.yahoo.com/, http://news.google.com and http://uk.newsbot.msn.com. Their clustering algorithms appear to consider the full text of each news article, in addition to temporal cues, to produce sets of topically/temporally related articles. Story content is captured by downloading the HTML and isolating the textual content. A supervised HMM was trained to distinguish story content from surrounding advertisements, etc. 2 Over the course of about 8 months, we collected 11,162 clusters, comprising 177,095 articles and averaging 15.8 articles per cluster. The quality of these clusters is generally good. Impressionistically, discrete events like sudden disasters, business announcements, and deaths tend to yield tightly focused clusters, while ongoing stories like the SARS crisis tend to produce very large and unfocused clusters.
To extract likely paraphrase sentence pairs from these clusters, we used edit distance (Levenshtein 1966) over words, comparing all sentences pairwise within a cluster to find the minimal number of word insertions and deletions transforming the first sentence into the second. Each sentence was normalized to lower case, and the pairs were filtered to reject: • Sentence pairs where the sentences were identical or differed only in punctuation; • Duplicate sentence pairs; • Sentence pairs with significantly different lengths (the shorter is less than two-thirds the length of the longer); • Sentence pairs where the Levenshtein distance was greater than 12.0. 3 A total of 139K non-identical sentence pairs were obtained. Mean Levenshtein distance was 5.17; mean sentence length was 18.6 words.

Word alignment
To this corpus we applied the word alignment algorithms available in Giza++ (Och & Ney, 2000), a freely available implementation of IBM Models 1-5 (Brown, 1993) and the HMM alignment (Vogel et al, 1996), along with various improvements and modifications motivated by experimentation by Och & Ney (2000). In order to capture the many-to-many alignments that identify correspondences between idioms and other phrasal chunks, we align in the forward direction and again in the backward direction, heuristically recombining each unidirectional word alignment into a single bidirectional alignment (Och & Ney 2000). Figure 1 shows an example of a monolingual alignment produced by Giza++. Each line represents a uni-directional link; directionality is indicated by a tick mark on the target side of the link.
We held out a set of news clusters from our training data and extracted a set of 250 sentence pairs for blind evaluation. Randomly extracted on the basis of an edit distance of 5 ≤ n ≤ 20 (to allow a range of reasonably divergent candidate pairs while eliminating the most trivial substitutions), the gold-standard sentence pairs were checked by an independent human evaluator to ensure that they contained paraphrases before they were hand word-aligned.
To evaluate the alignments, we adhered to the standards established in Melamed (2001) and Och & Ney (2000. Following Och & Ney's methodology, two annotators each created an initial annotation for each dataset, subcategorizing alignments as either SURE (necessary) or POSSIBLE (allowed, but not required). Differences were highlighted and the annotators were asked to review their choices on these differences. Finally we combined the two annotations into a single gold standard: if both annotators agreed that an alignment should be SURE, then the alignment was marked as SURE in the gold-standard; otherwise the alignment was marked as POSSIBLE.
To compute Precision, Recall, and Alignment Error Rate (AER) for the twin datasets, we used exactly the formulae listed in Och & Ney (2003). Let A be the set of alignments in the comparison, S be the set of SURE alignments in the gold standard, and P be the union of the SURE and POSSIBLE alignments in the gold standard. Then we have: Measured in terms of AER 4 , final interrater agreement between the two annotators on the 250 sentences was 93.1%. 4 The formula for AER given here and in Och & Ney (2003) is intended to compare an automatic alignment against a gold standard alignment. However, when comparing one human against another, both comparison and reference distinguish between SURE and POSSIBLE links. Because the AER is asymmetric (though each direction Table 1 shows the results of evaluating alignment after trainng the Giza++ model. Although the overall AER of 11.58% is higher than the best bilingual MT systems (Och & Ney, 2003), the training data is inherently noisy, having more in common with analogous corpora than conventional MT parallel corpora in that the paraphrases are not constrained by the source text structure. The identical word AER of 10.57% is unsurprising given that the domain is unrestricted and the alignment algorithm does not employ direct string matching to leverage word identity. 5 The non-identical word AER of 20.88% may appear problematic in a system that aims to generate paraphrases; as we shall see, however, this turns out not to be the case. Ablation experiments, not described here, indicate that additional data will improve AER.

Identifying phrasal replacements
Recent work in SMT has shown that simple phrase-based MT systems can outperform more sophisticated word-based systems (e.g. Koehn et al. 2003). Therefore, we adopt a phrasal decoder patterned closely after that of Vogel et al. (2003).
We view the source and target sentences S and T as word sequences s 1 ..s m and t 1 ..t n . A word alignment A of S and T can be expressed as a function from each of the source and target tokens to a unique cept (Brown et al. 1993); isomorphically, a cept represents an aligned subset of the source and target tokens. Then, for a given sentence pair and word alignment, we define a phrase pair as a subset of the cepts in which both the source and target tokens are contiguous. 6 We gathered all phrase differs by less than 5%), we have presented the average of the directional AERs. 5 However, following SMT practice of augmenting data with a bilingual lexicon, we did append an identity lexicon to the training data. 6 While this does preclude the usage of "gapped" phrase pairs such as or → either … or, we found such map-  pairs (limited to those containing no more than five cepts, for reasons of computational efficiency) occurring in at least one aligned sentence somewhere in our training corpus into a single replacement database. This database of lexicalized phrase pairs, termed phrasal replacements, serves as the backbone of our channel model. As in (Vogel et al. 2003), we assigned probabilities to these phrasal replacements via IBM Model 1. In more detail, we first gathered lexical translation probabilities of the form P(s | t) by running five iterations of Model 1 on the training corpus. This allows for computing the probability of a sequence of source words S given a sequence of target words T as the sum over all possible alignments of the Model 1 probabilities: (Brown et al. (1993) provides a more detailed derivation of this identity.) Although simple, this approach has proven effective in SMT for several reasons. First and foremost, phrasal scoring by Model 1 avoids the sparsity problems associated with estimating each phrasal replacement probability with MLE (Vogel et al. 2003). Secondly, it appears to boost translation quality in more sophisticated translation systems by inducing lexical triggering (Och et al. 2004). Collocations and other non-compositional phrases receive a higher probability as a whole than they would as independent single word replacements.
One further simplification was made. Given that our domain is restricted to the generation of monolingual paraphrase, interesting output can be produced without tackling the difficult problem of inter-phrase reordering. 7 Therefore, along the lines of Tillmann et al. (1997), we rely on only monotone phrasal alignments, although we do allow intra-phrasal reordering. While this means certain common structural alternations (e.g., active/passive) cannot be generated, we are still able to express a broad range of phenomena: pings to be both unwieldy in practice and very often indicative of poor a word alignment. 7 Even in the realm of MT, such an assumption can produce competitive results (Vogel et al. 2003). In addition, we were hesitant to incur the exponential increase in running time associated with those movement models in the tradition of Brown el al (1993), especially since these offset models fail to capture important linguistic generalizations (e.g., phrasal coherence, headedness). Our channel model, then, is determined solely by the phrasal replacements involved. We first assume a monotone decomposition of the sentence pair into phrase pairs (considering all phrasal decompositions equally likely), and the probability P(S | T) is then defined as the product of the each phrasal replacement probability. The target language model was a trigram model using interpolated Kneser-Ney smoothing (Kneser & Ney 1995), trained over all 1.4 million sentences (24 million words) in our news corpus.

Generating paraphrases
To generate paraphrases of a given input, a standard SMT decoding approach was used; this is described in more detail below. Prior to decoding, however, the input sentence underwent preprocessing: text was lowercased, tokenized, and a few classes of named-entities were identified using regular expressions.
To begin the decoding process, we first constructed a lattice of all possible paraphrases of the source sentence based on our phrasal translation database. Figure 2 presents an example. The lattice was realized as a set of |S| + 1 vertices v 0 ..v |S| and a set of edges between those vertices; each edge was labeled with a sequence of words and a real number. Thus a edge connecting vertex v i to v j labeled with the sequence of words w 1 ..w k and the real number p indicates that the source words s i+1 to s j can be replaced by words w 1 ..w k with probability p. Our replacement database was stored as a trie with words as edges, hence populating the lattice takes worst case O(n 2 ) time. Finally, since source and target languages are identical, we added an identity mapping for each source word s i : an edge from v i-1 to v i with label s i and a uniform probability u. This allows for handling unseen words. A high u value permits more conservative paraphrases.
We found the optimal path through the lattice as scored by the product of the replacement model and the trigram language model. This algorithm reduces easily to the Viterbi algorithm; such a dynamic programming approach guarantees an efficient optimal search (worst case O(kn), where n is the maximal target length and k is the maximal number of replacements for any word). In addition, fast algorithms exist for computing the n-best lists over a lattice (Soong & Huang 1991).
Finally the resultant paraphrases were cleaned up in a post-processing phase to ensure output was not trivially distinguishable from other systems during human evaluation. All generic named entity tokens were re-instantiated with their source values, and case was restored using a model like that used in Vita et al. (2003). Barzilay & Lee (2003) have released a common dataset that provides a basis for comparing different paraphrase generation systems. It consists of 59 sentences regarding acts of violence in the Middle East. These are accompanied by paraphrases generated by their Multi-Sequence Alignment (MSA) system and a baseline employing WordNet (Fellbaum 1998), along with human judgments for each output by 2-3 raters.

Alternate approaches
The MSA WordNet baseline was created by selecting a subset of the words in each test sentence-proportional to the number of words replaced by MSA in the same sentence-and replacing each with an arbitrary word from its most frequent WordNet synset.
Since our SMT approach depends quite heavily on a target language model, we presented an alternate WordNet baseline using a target language model. 8 In combination with the language model described in section 3.4, we used a very simple replacement model: each appropriately inflected member of the most frequent synset was proposed as a possible replacement with uniform probability. This was intended to isolate the contribution of the language model from the replacement model.
Given that our alignments, while aggregated into phrases, are fundamentally word-aligned, one question that arises is whether the information we learn is different in character than that learned from much simpler techniques. To explore this hypothesis, we introduced an additional baseline that used statistical clustering to produce an automated, unsupervised synonym list, again with a trigram language model. We used standard bigram clustering techniques (Goodman 2002) to produce 4,096 clusters of our 65,225 vocabulary items.

Evaluation
We have experimented with several methods for extracting a parallel sentence-aligned corpus from news clusters using word alignment error rate, or AER, (Och & Ney 2003) as an evaluation metric. A brief summary of these experiments is provided in Table 1. To evaluate the quality of generation, we followed the lead of Barzilay & Lee (2003). We started with the 59 sentences and corresponding paraphrases from MSA and WordNet (designated as WN below). Since the size of this data set made it difficult to obtain statistically significant results, we also included 141 randomly selected sentences from held-out clusters. We then produced paraphrases with each of the following systems and compared them with MSA and WN: • WN+LM: WordNet with a trigram LM • CL: Statistical clusters with a trigram LM • PR: The top 5 sentence rewrites produced by Phrasal Replacement.
For the sake of consistency, we did not use the judgments provided by Barzilay and Lee; instead we had two raters judge whether the output from each system was a paraphrase of the input sentence. The raters were presented with an input sentence and an output paraphrase from each system in random order to prevent bias toward any particular judgment. Since, on our first pass, we found inter-rater agreement to be somewhat low (84%), we asked the raters to make a second pass of judgments on those where they disagreed; this significantly improved agreement (96.9%). The results of this final evaluation are summarized in Table 2.  Table 2 shows that PR can produce rewordings that are evaluated as plausible paraphrases more frequently than those generated by either baseline techniques or MSA. The WordNet baseline performs quite poorly, even in combination with a trigram language model: the language model does not contribute significantly to resolving lexical selection. The performance of CL is likewise abysmal-again a language model does nothing to help. The poor performance of these synonymbased techniques indicates that they have little value except as a baseline.
The PR model generates plausible paraphrases for the overwhelming majority of test sentences, indicating that even the relatively high AER for non-identical words is not an obstacle to successful generation. Moreover, PR was able to generate a paraphrase for all 200 sentences (including the 59 MSA examples). The correlation between acceptability and PR sentence rank validates both the ranking algorithm and the evaluation methodology.
In Table 2, the PR model scores significantly better than MSA in terms of the percentage of paraphrase candidates accepted by raters. Moreover, PR generates at least five (and often hundreds more) distinct paraphrases for each test sentence. Such perfect coverage on this dataset is perhaps fortuitous, but is nonetheless indicative of scalability. By contrast Barzilay & Lee (2003) report being able to generate paraphrases for only 59 out of 484 sentences in their training (test?) set, a total of 12%.
One potential concern is that PR paraphrases usually involve simple substitutions of words and short phrases (a mean edit distance of 2.9 on the top ranked sentences), whereas MSA outputs more complex paraphrases (reflected in a mean edit distance of 25.8). This is reflected in Table 3, which provides a breakdown of four dimensions of interest, as provided by one of our independent evalua-tors. Some 47% of MSA paraphrases involve significant reordering, such as an active-passive alternation, whereas the monotone PR decoder precludes anything other than minor transpositions within phrasal replacements.
Should these facts be interpreted to mean that MSA, with its more dramatic rewrites, is ultimately more ambitious than PR? We believe that the opposite is true. A close look at MSA suggests that it is similar in spirit to example-based machine translation techniques that rely on pairing entire sentences in source and target languages, with the translation step limited to local adjustments of the target sentence (e.g. Sumita 2001). When an input sentence closely matches a template, results can be stunning. However, MSA achieves its richness of substitution at the cost of generality. Inspection reveals that 15 of the 59 MSA paraphrases, or 25.4%, are based on a single high-frequency, domain-specific template (essentially a running tally of deaths in the Israeli-Palestinian conflict). Unless one is prepared to assume that similar templates can be found for most sentence types, scalability and domain extensibility appear beyond the reach of MSA.
In addition, since MSA templates pair entire sentences, the technique can produce semantically different output when there is a mismatch in information content among template training sentences. Consider the third and fourth rows of Table  3, which indicate the extent of embellishment and lossiness found in MSA paraphrases and the topranked PR paraphrases. Particularly noteworthy is the lossiness of MSA seen in row 4. Figure 3 illustrates a case where the MSA paraphrase yields a significant reduction in information, while PR is more conservative in its replacements.
While the substitutions obtained by the PR model remain for the present relatively modest, they are not trivial. Changing a single content word is a legitimate form of paraphrase, and the ability to paraphrase across an arbitrarily large sentence set and arbitrary domains is a desideratum of paraphrase research. We have demonstrated that the SMT-motivated PR method is capable of generating acceptable paraphrases for the overwhelming majority of sentences in a broad domain.

Future work
Much work obviously remains to be done. Our results remain constrained by data sparsity, despite the large initial training sets. One major agenda item therefore will be acquisition of larger (and more diverse) data sets. In addition to obtaining greater absolute quantities of data in the form of clustered articles, we also seek to extract aligned sentence pairs that instantiate a richer set of phenomena. Relying on edit distance to identify likely paraphrases has the unfortunate result of excluding interesting sentence pairs that are similar in meaning though different in form. For example: We are currently experimenting with data extracted from the first two sentences in each article, which by journalistic convention tend to summarize content (Dolan et al. 2004). While noisier than the edit distance data, initial results suggest that these can be a rich source of information about larger phrasal substitutions and syntactic reordering. Although we have not attempted to address the issue of paraphrase identification here, we are currently exploring machine learning techniques, based in part on features of document structure and other linguistic features that should allow us to bootstrap initial alignments to develop more data. This will we hope, eventually allow us to address such issues as paraphrase identification for IR.
To exploit richer data sets, we will also seek to address the monotone limitation of our decoder that further limits the complexity of our paraphrase output. We will be experimenting with more sophisticated decoder models designed to handle reordering and mappings to discontinuous elements. We also plan to pursue better (automated) metrics for paraphrase evaluation.

Conclusions
We presented a novel approach to the problem of generating sentence-level paraphrases in a broad semantic domain. We accomplished this by using methods from the field of SMT, which is oriented toward learning and generating exactly the sorts of alternations encountered in monolingual paraphrase. We showed that this approach can be used to generate paraphrases that are preferred by humans to sentence-level paraphrases produced by other techniques. While the alternations our system produces are currently limited in character, the field of SMT offers a host of possible enhancements-including reordering models-affording a natural path for future improvements.
A second important contribution of this work is a method for building and tracking the quality of large, alignable monolingual corpora from structured news data on the Web. In the past, the lack of such a data source has hampered paraphrase research; our approach removes this obstacle.


extfieldsofstudy:
Computer Science
Medicine

text:
Obol: Integrating Language and Meaning in Bio-Ontologies

Ontologies are intended to capture and formalize a domain of knowledge. The ontologies comprising the Open Biological Ontologies (OBO) project, which includes the Gene Ontology (GO), are formalizations of various domains of biological knowledge. Ontologies within OBO typically lack computable definitions that serve to differentiate a term from other similar terms. The computer is unable to determine the meaning of a term, which presents problems for tools such as automated reasoners. Reasoners can be of enormous benefit in managing a complex ontology. OBO term names frequently implicitly encode the kind of definitions that can be used by computational tools, such as automated reasoners. The definitions encoded in the names are not easily amenable to computation, because the names are ostensibly natural language phrases designed for human users. These names are highly regular in their grammar, and can thus be treated as valid sentences in some formal or computable language.With a description of the rules underlying this formal language, term names can be parsed to derive computable definitions, which can then be reasoned over. This paper describes the effort to elucidate that language, called Obol, and the attempts to reason over the resulting definitions. The current implementation finds unique non-trivial definitions for around half of the terms in the GO, and has been used to find 223 missing relationships, which have since been added to the ontology. Obol has utility as an ontology maintenance tool, and as a means of generating computable definitions for a whole ontology. The software is available under an open-source license from: http://www.fruitfly. org/~cjm/obol. Supplementary material for this article can be found at: http://www. interscience.wiley.com/jpages/1531-6912/suppmat.

Introduction
The Gene Ontology (GO) is a collection of three ontologies, partitioned into orthogonal domains: molecular function, biological process and cellular component [1,2]. GO is part of the Open Bio-Ontologies (OBO) project [3], which includes ontologies for other biologically relevant domains, such as anatomy, cell type [4], chemical compounds and phenotypic descriptors [5,6].
Ontologies in OBO consist of terms, which are used to describe biological data, such as gene products. Each term must have a name, which is a concise phrase capturing the meaning of the term; e.g. 'negative regulation of interleukin-2 biosynthesis', 'cardioblast differentiation' and 'small ribosomal subunit'. Terms may also have one or more synonyms.
Terms are interconnected via typed binary relationships, such as 'interleukin is a cytokine' or 'small ribosomal subunit part of mitochondrial ribosome'.
Text definitions precisely state the exact meaning of a term. Not all terms have text definitions. Text definitions are interpreted by users, not computers. An OBO term has little in the way of computable definitions, which makes it difficult to perform certain kinds of reasoning over the terms in the ontology [7,8].
It has been noted [7,[9][10][11] that many term names are compositional, and indicate implicit relationships to terms, possibly in a different ontologies; e.g. 'cardioblast differentiation' in the biological process ontology has an implicit relationship to the term 'cardioblast' in the cell ontology, yet this relationship is absent from both ontologies; currently there are no explicit relationships between different ontologies in OBO. A computable definition of 'cardioblast differentiation' would by necessity reference 'cardioblast'.
The existence of composite terms leads to redundancy in both text definitions and relationships [12]. For example, the term 'cytokine' has redundant definitions embedded in the text definitions for 'cytokine metabolism' and 'cytokine biosynthesis'. The redundancy in relationships manifests itself as 'cytokine metabolism' and 'cytokine biosynthesis' being related via is a to both 'protein metabolism' and 'protein biosynthesis'.
The compositional nature of many terms leads to an increase in the number of relationships and consequent increase in complexity of the ontology. This is particularly true of the GO; the term 'positive regulation of T-helper 2 cell differentiation' has 114 distinct paths through the relationships in the ontology to the root term. This complexity can have a negative impact on both users and curators, searching and maintaining the ontologies.
We could integrate OBO by providing computable definitions for all existing terms. This would bring benefits, such as the ability to reason over the ontology and automatically derive certain relationships. However, adding and maintaining these computable definitions is a significant undertaking, and it is unclear whether the benefits would outweigh the costs.
An alternative approach is to use implicit knowledge encoded in a term name to derive the intended meaning of the term. OBO term names exhibit a high degree of regularity in phrase structure, and in how that structure relates to meaning. In fact, OBO term names can be viewed as phrases written in a formal language, described using logical rules. The formal language of OBO term phrases is a subset of natural language, and it thus serves the dual purpose of specifying meaning for both human users and computers.
This paper describes the attempt: • To elucidate the formal language underlying OBO, called Obol. • To use this language to derive the meaning of existing OBO terms. • To use these derived meanings to help manage the redundancy and complexity within OBO.

Source ontologies
A subset of OBO was used for constructing and testing Obol. The system described here was constructed using the three GO ontologies, the biochemical ontology and the cell ontology [4]. These ontologies were downloaded on 24 July 2004. Currently there is neither a generic (nonspecies-specific) anatomy or protein family ontology in OBO.

Tokenization
Each term in OBO has exactly one primary name, which is a string of characters containing a phrase or sequence of words, indicated here by W*. The first step in determining the implicit meaning of a term is tokenizing the term name string. Tokenization breaks a term name phrase-string into an ordered sequence of word-strings. Each of these word-strings is treated as an atomic (nondecomposable) token. The phrase-string is split on white-space characters and non-alphanumeric characters. White-space characters are discarded, but non-alphanumeric characters (e.g. the hyphen character '-') are preserved and treated as special word tokens. For example:

Atomic vocabularies (AVs)
Each word token is matched against an atomic vocabulary (AV) of words. The AV contains words, not phrases. It thus overlaps and is distinct from the Obol: integrating language and meaning in bio-ontologies 511 OBO-controlled vocabulary of phrases, where each phrase consists of one or more words. The atomic vocabulary assigns each word a domain, and a lexical category (also known as a part of speech). The domains typically correspond to the domains of existing ontologies within OBO (e.g. molecular function, cellular component, cell, biochemical) and also to domains that are not presently covered by OBO (environment, protein, generic anatomy). Table 1 shows a list of domains defined by Obol.
The lexical category of a word defines the role that word plays in a phrase. For example, in the phrase 'negative regulation', the word 'negative' plays the role of adjective. For simplicity we assume that each word in the AV has exactly one lexical category. The lexical categories used include typical linguistic categories, such as nouns, adjectives, prepositions and relational adjectives. Relational adjectives are useful for linking adjectives to the noun form of that adjective. They are treated as binary relations between words; e.g. relational adj(epidermal, epidermis). There is also an additional category for numbers, roman numerals, words designating Greek symbols and alphanumeric characters used as 'type designators'; e.g. 'myosin II', 'interferon-alpha' and 'interleukin-2'. OBO terms typically do not contain verbs, so there is no need for such a category. Inflected verbs (e.g. 'regulation', the inflected form of 'regulate') are treated no differently from other nouns. It is rare for OBO term names to include the definite or indefinite article ('the' or 'a'), and other lexical categories commonly used in natural language ('it', 'they', 'he', 'she'). It is also rare for there to be different variants of the same word, so there is no requirement for reducing words to stem forms.
The phrase 'negative regulation of interleukin-2 biosynthesis' can be tokenized into words that are categorized into the following lexical-categories and domains: • negative (adjective, general).

Constructing the atomic vocabulary
All term names in the source ontology were tokenized; this resulted in a set of word tokens, which comprised the initial AV. Domains and lexical categories were assigned both manually and semiautomatically, using the OBO grammar (see next section).
As OBO changes, the AVs must also change. However, the atomic vocabularies need not be completely up-to-date, because the system exhibits graceful degradation with incomplete or incorrectly categorized AVs; performance is impacted, but not severely.

OBO term grammar
A computational (or formal) grammar is a way to describe a formal language, analogous to the concept of grammars for natural languages [13,14]. A formal language is a set of sequences (e.g. sentences) over a finite alphabet (e.g. words).

C. J. Mungall
A computational grammar G consists of: occurrences of terminal and non-terminal symbols]. • A symbol S in N that is indicated as the start symbol.
The language of a formal grammar G = (N , , P , S ), denoted as L(G), is defined as all those strings over that can be generated by starting with the start symbol S and then applying the production rules P until no more non-terminal symbols are present.
A grammar can be used for either generating or parsing sequences of tokens. Parsing a sequence of tokens with a grammar will produce a parse tree, which can be used to elucidate the structure of the sequence. A sequence of tokens may have zero or more parse trees.
OBO term names are both natural language phrases and well-formed phrases conforming to a formal grammar.
The formal grammar G OBO contains terminal symbols OBO equivalent to the word tokens from the AVs. The set of non-terminal symbols N OBO is the union of the set of lexical categories (nouns, adjectives, etc.) and the set of phrase types used to construct a term. Examples of phrase types are noun phrases and prepositional phrases.
The start symbol S OBO refers to a complete OBO term name.
The production rules P OBO specify how larger phrases are recursively constructed from smaller phrases and from words. A simplified subset of the production rules is included below; the entire grammar can be viewed by downloading the system. Non-terminal symbols are indicated with a leading upper-case character, terminal symbols in lowercase: • S OBO → NounPhrase (an OBO term name is a noun phrase; e.g. the noun phrase 'negative regulation of protein biosynthesis') • NounPhrase → Noun (a noun phrase can be a single noun; e.g. 'regulation' or 'biosynthesis') • NounPhrase → AdjectiveNounPhrase (a noun phrase can be an adjective immediately followed by a noun phrase; e.g. 'negative regulation' or 'smooth muscle contraction') • NounPhrase → NounPhrase' − ' Token (a noun phrase can be a noun phrase immediately followed by a type designator; e.g. 'myosin II ' or 'interleukin-2 ' or 'interferon-alpha') • NounPhrase → NounPhrase NounPhrase (a noun phrase can be a stem noun phrase immediately preceded by a modifier noun phrase; e.g. 'interleukin-2 biosynthesis' or 'muscle contraction'). Note that this rule is left-recursive, which can cause problems with some computational systems.

• PrepPhrase → Prep NounPhrase
(a prepositional phrase can be a noun phrase immediately preceded by a preposition; e.g. 'of interleukin-2 biosynthesis' or 'by pheromones') • NounPhrase → NounPhrase PrepPhrase (a noun phrase can be a noun phrase immediately followed by a prepositional phrase; e.g. 'negative regulation of interleukin-2 biosynthesis') (lexical categories map to words in the AVs. Note the use of the pipe symbol '|' to indicate 'or') Not shown here are rules for dealing with relational adjectives (e.g. 'cytosolic ribosome') and for Boolean connectors (e.g. 'recognition and cleavage').
G OBO production rules typically have one symbol on the left-hand side and one or two symbols on the right-hand side. When a rule has two symbols on the right-hand side, one symbol acts as the stem phrase, the other as the supplementary phrase. In the example rules given above, supplementary phrases are indicated with italics.
An example syntax parse of the GO term with name 'negative regulation of interleukin-2 biosynthesis' is shown in Figure 1. Stem phrases are indicated with the bold lines.  The syntax parse can also be shown as a bracketed expression. There are actually two possible parses under G OBO : biosynthesis noun )))) P OBO is augmented with precedence rules (not shown) to favour the first parse. P OBO was constructed manually. Not all GO term names are in L(G OBO ), which is to say that not all term names can be parsed. Some term names have more that one possible parse tree, indicating possible ambiguity in the syntactic structure (and thus in the interpreted meaning of the term).
L(G OBO ) contains an infinite amount of potential term names, a finite subset of which correspond to meaningful biological phrases. The next step is to derive these meaningful phrases.

Deriving class definitions
The grammar G OBO specifies a syntactic parse of OBO terms; this elucidates the compositional structure of term names. The next step is to derive a semantic parse; in other words, to derive the meaning encoded in a term name. The meaning of a term can be formally specified as an Obol definition, modelled after Aristotelian definitions [15].
An Obol definition consists of a genus and differentiae. The genus is a broad category (as distinct from genus, sensu phylogeny). Obol considers each word in the AV to be a distinct genus. The differentiae are a set of necessary and sufficient conditions that distinguish a term from other terms of the same genus. The differentiae are similar to standard relationships between OBO terms. However, they are different in that these standard relationships are not always sufficient to distinguish one term from other terms of the same genus. For example, the term 'interleukin-2 biosynthesis' is defined as having genus 'biosynthesis' and the differentia 'forms interleukin-2'. The property of creating interleukin-2 proteins is sufficient to discriminate this term from all other kinds of biosynthesis.
Definitions can be nested. The definition for 'interleukin-2' would have genus 'interleukin' and differentia 'type token 2'. Using the notation <genus><rel − type> = (<definition>) to specify a definition, and simply <genus> for a primitive definition. Figure 2 shows the definitional structure of the GO term 'negative regulation of interleukin-2 biosynthesis'.
Genus-differentiae definitions are useful for automated reasoning. For example, we can prove that 'interleukin-2 biosynthesis' is a 'interleukin biosynthesis' is a 'cytokine biosynthesis' from a single relationship 'interleukin' is a 'cytokine', given some ontology of protein families.
It is possible to derive candidate definitions for phrases using a grammar, G, a set of is a relationships, R, ranging over the genus categories in an AV, and set of biological relationship types, Q. OBO has minimal set of logical relations defined in the relations ontology [16]. This was manually   augmented to get Q OBO . Here, a relationship type belonging to Q is defined by a set of domain, range and grammatical context triples. The domain and range specify to which genus or genera a relationship type pertains. The grammatical context specifies how a relationship is linguistically manifested in a phrase. For example, consider the relationship type affects in Q OBO . This type can have the domain 'regulation' and the range 'process' occurring with the preposition 'of' in some phrase. Because 'biosynthesis' is a 'process', the phrase 'regulation of biosynthesis' is equivalent to the definition regulation affects = (biosynthesis). Table 2 shows some example relationships and the contexts in which they are used. OBO term names are remarkably consistent in mapping grammatical structure to meaning. A term with name as 'regulation of transcription' would never use a different grammatical context (except as a synonym). An example of a different grammatical context is a relational adjective modifier, as in 'transcriptional regulation'.

Class definition derivation method
Given a set of relationship types Q, as defined above, we can attempt to infer a class definition for any syntax parse tree.
Starting at the root of the parse tree, S, we recursively build the class definition. The production rules, P , are constructed such that each node in the parse tree should have one or two children. If it has one child, then the class definition at the parent node is equal to the class definition at the child node. If the node has two children -one stem node n 1 and another supplementary node n 2 -then the class definition will be the combination of the class definition D 1 at n 1 with a relationship, r, to the class definition D 2 at n 2 , where the possible relationship types are constrained by the grammatical type of the current node, n, together with the domain and range types matched to D 1 and D 2 , according to Q.
When we reach the leaf nodes of the parse tree, we assign a primitive definition, which is simply a genus lacking differentiae.

Obol: integrating language and meaning in bio-ontologies 515
Deriving a class definition is also known as semantic parsing. This extension to a standard grammar is called a semantic grammar. A semantic grammar is reversible, allowing for the generation of phrases from definitions. Table 3 gives an example of the semantic parse of the term name 'negative regulation of interleukin-2 biosynthesis'.
If we augment our definition of a grammar G with relationship types and a set of is a relationships over genera, giving a semantic grammar = (N , , P , S , Q, R IS A ), then the language of , denoted as L( ), is defined as all those meaningful strings over belonging to L(G). If OBO is defined perfectly, then L( OBO ) should correspond to the universe of meaningful biological terms. We refer colloquially to L( OBO ) as Obol.
Definitions can be exported using either the obo flat-file format (http://www.geneontology.org/ GO.format.html#oboflat) or using a description logic (DL) format, such as Ontology Web Language (OWL) [17].
The candidate class definitions can be considered an end in and of themselves, or they can be used for reasoning.

Reasoning
Class definitions can be used for reasoning over the ontologies. This can be done using an external third-party reasoner, such as FaCT [18] or RACER [19]. There is also an advantage to integrating some simple reasoning facility into the grammar system.
Some of the things we may wish to do with a reasoner and some class definitions include: • Check for inconsistent or missing relationships, or missing terms. • Automatically assign relationships for new terms. • Extract implicit ontologies from GO.
The reasoner can also be used to feed back information to the class builder, to help filter ambiguous parses.
The Obol reasoner uses a rule-based system for performing these tasks. An example of a simple Obol rule is one involving subsumption (subtyping). Here the notation is a + means transitive is a, and T is a + T means that T can be reached from T by following a chain of one or more is a relationships.
T is a + T if (T is a X and X is a + T )or(T is a T ) There are rules for inferring contingent inclusion is a relationships [16] that are based on natural is a relationships using genus-differentiae definitions (where G = genus, and the differentia is Q = (D), and D is itself a definition). Here is a subset of the Obol rule-set: Using rule 1, and the semantic grammar, the Obol system infers an is a relationship between 'chromoplast membrane' (membrane surrounds = chromoplast) and 'plastid membrane' (membrane surrounds = plastid) based on the is a relationship between 'chromoplast' and 'plastid'.
An example of applying rule 2 is to discover that 'vitamin E biosynthesis' (biosynthesis forms = vitaminE) is a 'vitamin E metabolism' (metabolism forms = vitaminE), based on the is a relationship between 'biosynthesis' and 'metabolism'.
An example of applying rule 3 is to discover that 'primary septum' (septum type = primary) is a 'septum', based on the fact that there is no OBO term 'primary' and thus no parent for that term.
Rules such as these can be used to find errors of omission in an ontology, to automatically add relationships for newly created terms, to suggest intermediate terms, and to determine which relationships in the ontology are true by contingency. Table 4 has the complete set of all relationships that can be derived for the term named 'negative regulation of interleukin-2 biosynthesis'. Note that all these derived relationships are currently present in GO due to curator diligence.

Implementation
The grammar, class builder and reasoner, described above, are all specified and implemented in Prolog. The grammar is implemented as a Definite Clause Grammar (DCG) [20]. Prolog allows for direct specification of DCGs as part of the language. Prolog is a high-level declarative logic programming language, and is considerably different from Table 4. Examples of relationships that can be automatically derived by semantically parsing the term 'negative regulation of interleukin-2 biosynthesis'. Note that all 16 of these relationships are currently present in GO, so Obol tells us nothing new here. However, manual curation of these derivable relationships is an onerous and error-prone task. Obol can help maintain these. Note also that in order to make all of these derivations Obol requires an ontology of proteins, such as interleukins. No such ontology currently exists within OBO -an example of one was generated for this particular test. This highlights the importance of OBO for the GO project  languages typically used in bioinformatics, such as perl, C and java. It is particularly well suited to implementing logical rules, the foundations of the Obol system. We use XSB Prolog [21], which provides tabling in addition to a standard prolog system. This allows grammar production rules to be left-recursive, as is the case for the P OBO . The go-perl library [22] is used to convert OBO files to prolog fact files. Interaction with the system is either via prolog interpreter or via a UNIX makefile. The system has been tested on both Linux and Mac OS X, and is available under an open source licence from http://www.fruitfly.org/∼cjm/obol.

Parsing
Any OBO term can have zero, one or multiple ambiguous syntactic or semantic parses. We tested the system on all terms in GO (but not the rest of OBO). Ideally, one semantic parse (class definition) would be generated for each GO term, but in practice this is currently only achieved for about half of all terms. Ideally, the semantic parse would reflect the actual meaning of the term, but in some cases inaccurate meanings are derived. Typically, term names with lots of words generate multiple ambiguous parses. In particular, term names that contain long sequences of nouns result in an exponential increase in syntactic parses; this is due to the rule NounPhrase → NounPhrase NounPhrase. Note that it is still possible to do reasoning with ambiguous parses.
The histograms in Figures 3, 4 and 5 show the distribution of the number of parses, both syntactic and semantic, for the three GO ontologies. Singleword terms have been excluded, since these are trivially parsed to the corresponding genus. The histograms have been truncated at five parses; one particular molecular function term ('receptor signaling protein tyrosine kinase signaling protein activity') has 132 syntactic parses (of which none derive a definition).
Note that the molecular function ontology has the highest number of terms that cannot be parsed. One reason is that the tokenizer and grammar originally did not deal adequately with term names containing chemical notation, such as '5(S )hydroxyperoxy−6E , 8Z , 11Z , 14Z -icosatetraenoic  Improving the AVs will reduce the number of incorrect syntax parses (and thus reduce the incorrect semantic parses). Many words are incorrectly categorized or are not yet present in the AVs. This can be improved by manual and semi-automatic AV curation. Refining the set of relationship types will improve semantic parsing. Currently only very general relationship types are used. More specific relationship types could help filter out ambiguous parses, and provide more specific meanings.

Exporting definitions
The derived definitions can be represented as an OWL file. An export of all of the source ontologies is available as Online Supplementary Material at: http://www.interscience.wiley.com/jpages/1531-6912/suppmat. This file was generated automatically. An OWL definition is provided only if there is exactly one semantic parse for a term.

Missing relationships
We found 400 candidate missing relationships over two iterations. The first run was performed on the March 2004 version of GO, with an earlier version of the code; the second run was performed on the July 2004 version of GO. Of these 400, at least 223 have since been added to GO. Each term was parsed to derive a class definition. Reasoning rules were applied over the class definitions to infer missing relationships. Table 5 shows some examples of the missing relationships detected.

Deriving existing relationships
We examined all 23 306 relationships in GO to determine which could be automatically derived. We compared two methods. The first method uses the semantic grammar OBO and relationship derivation rules, as above. The second method is similar to that described in [10], in which a relationship is derivable if all the words in the parent term are an ordered subset of words in the child term. Table 6 shows the numbers of derivable relationships in GO. This gives a rough indication of what proportion of GO relationships reflect biological knowledge, and what proportion are true by their logical definition.
Use of a semantic grammar has lower sensitivity than a subset-or substring-based approach. This is because many terms cannot be parsed by OBO , The sensitivity will improve as OBO improves. It is difficult to measure specificity, because GO relationships may be incomplete.

Generating implicit ontologies
The GO biological process ontology contains an implicit generic anatomy ontology, encoded in term names such as 'haltere disc metamorphosis' and corresponding relationships. This implicit anatomical ontology has been extracted, and could be used as the basis for a cross-species generic anatomy.

Limitations
Not all composite term names reflect the exact meaning of the term. For example, 'dense nuclear body' refers to something more specific than what is suggested by the individual words. This can lead to errors in reasoning, such as 'dense nuclear body' is a 'nuclear body'. This can be overcome by manually creating formal definitions that override

Future directions
OBO terms occasionally use concise colloquial term names rather than term names that explicitly indicate the meaning according to OBO . These terms typically have an exact synonym. Future implementations will also parse exact synonyms. Another simple extension would allow for automatic generation of synonyms for terms. Text definitions also conform to a regular structure, and so it should be possible to decompose and generate these. However, these are less concise than term names, and have a more complex grammar. A different approach is required for parsing text definitions.
The main benefit of using Obol is as an aid to the curation process, in that they assist with deriving relationships. In this mode, the end-user of the ontology would not use the grammar in any way. However, it is in theory possible to use Obol to enhance searching and navigation. For example, if a user searches for genes involved in 'transcriptional regulation', Obol could map this onto the correct term name 'regulation of transcription'. Other end-users who may benefit from the richer definitions that come from parsing include bioinformatics users who use measures of semantic similarity [23].
While it is important to stress that parsing a highly restrictive language (such as the language of OBO terms) is much simpler than parsing natural language, it may be possible to use parts of OBO as an aid to natural language processing. An example application is deriving the meaning of sentences in Medline abstracts. Another possibility is alternative grammars and lexical mappings to aid automatic translation of OBO term names to languages other than English.
The software described here was designed with the needs of the OBO community in mind. However, much of it could be applied to ontologies that are not part of OBO, biological or otherwise. This would only be worthwhile if the target ontology contained a large number of compound terms, with the implicit knowledge encoded in highly regular term names not reflected in the term definitions. Different domains may require alterations to the grammar production rules, as well as their own AVs and relationship types; however, the core parts of the Obol software could be used unaltered.
One of the most intriguing possibilities offered by Obol is to assist in the permanent manual transition of OBO from the existing representation to a more formal representation, such as a genus-differentiae paradigm as outlined here, or a description logic [7] paradigm. Such a transition would be extremely daunting without computational assistance. This would mark a significant change in OBO curation, but could have significant benefits for curators in terms of time spent creating and maintaining compound terms.