Hierarchical Orderings of Textual Units

Text representation is a central task for any approach to automatic learning from texts. It requires a format which allows to interrelate texts even if they do not share content words, but deal with similar topics. Furthermore, measuring text similarities raises the question of how to organize the resulting clusters. This paper presents cohesion trees (CT) as a data structure for the perspective, hierarchical organization of text corpora. CTs operate on alternative text representation models taking lexical organization, quantitative text characteristics, and text structure into account. It is shown that CTs realize text linkages which are lexically more homogeneous than those produced by minimal spanning trees.

Introduction
Text representation is a central task for approaches to text classification or categorization. They require a format which allows to semantically relate words, texts, and thematic categories. The majority of approaches to automatic learning from texts use the vector space or bag of words model. Although there is much research for alternative formats, whether phraseor hyperonym-based, their effects seem to be small (Scott and Matwin, 1999). More seriously (Riloff, 1995) argues that the bag of words model ignores morphological and syntactical information which she found to be essential for solving some categorization tasks. An alternative to the vector space model are semantic spaces, which have been proposed as a highdimensional format for representing relations of semantic proximity. Relying on sparse knowledge resources, they prove to be efficient in cognitive science (Kintsch, 1998;Landauer and Dumais, 1997), computational linguistics (Rieger, 1984;Schütze, 1998), and information retrieval.
Although semantic spaces prove to be an alternative to the vector space model, they leave the question unanswered of how to explore and visualize similarities of signs mapped onto them. In case that texts are represented as points in semantic space, this question refers to the exploration of their implicit, content based relations. Several methods for solving this task have been proposed which range from simple lists via minimal spanning trees to cluster analysis as part of scatter/gahter algorithms (Hearst and Pedersen, 1996). Representing a sign's environment in space by means of lists runs the risk of successively ordering semantically or thematically diverse units. Obviously, lists neglect the poly-hierarchical structure of semantic spaces which may induce divergent thematic progressions starting from the same polysemous unit. Although clustering proves to be an alternative to lists, it seeks a global, possibly nested partition in which clusters represent sets of indistinguishable objects regarding the cluster criterion. In contrast to this, we present cohesion trees (CT) as a data structure, in which single objects are hierarchically ordered on the basis of lexical cohesion. CTs, whose field of application is the management of search results in IR, shift the perspective from sets of clustered objects to cohesive paths of interlinked signs.
The paper is organized as follows: the next section presents alternative text representation models as extensions of the semantic space approach. They are used in section (3) as a background of the discussion of cohesion trees. Both types of models, i.e. the text representation models and cohesion trees as a tool for hierarchically traversing semantic spaces, are evaluated in section (4). Finally, section (5) gives some conclusions and prospects future work. This paper uses semantic spaces as a format for text representation. Although it neglects sentence as well as rhetorical structure, it departs from the bag of words model by referring to paradigmatic similarity as the fundamental feature type: instead of measuring intersections of lexical distributions, texts are interrelated on the basis of the paradigmatic regularities of their constituents. A coordinate value of a feature vector of a sign mapped onto semantic space measures the extent to which this sign (or its constituents in case of texts) shares paradigmatic usage regularities with the word defining the corresponding dimension. Because of this sensitivity to paradigmatics, semantic spaces can capture indirect meaning relations: words can be linked even if they never co-occur, but tend to occur in similar contexts. Furthermore, texts can be linked even if they do not share content words, but deal with similar topics (Landauer and Dumais, 1997). Using this model as a starting point, we go a step further in departing from the bag of words model by taking quantitative characteristics of text structure into account (see below).
Semantic spaces focus on meaning as use as described by the weak contextual hypothesis (Miller and Charles, 1991), which says that the similarity of contextual representations of words contributes to their semantic similarity. Regarding the level of texts, reformulating this hypothesis is straightforward: Contextual hypothesis for texts: the contextual similarity of the lexical constituents of two texts contributes to their semantic similarity.
In other words: the more two texts share semantically similar words, the higher the probability that they deal with similar topics. Clearly, this hypothesis does not imply that texts having contextually similar components to a high degree also share propositional content. It is the structural (connotative), not the propositional (denotative) meaning aspect to which this hypothesis applies. Moreover, this version of the contextual hypothesis neglects the structural dimension of similarity relations: not only that a text is structured into thematic components, each of which may semantically relate to different units, but units similar to the text as a whole do not form isolated, unstructured clumps. Neglecting the former we focus on the latter phenomenon, which demands a supplementary hypothesis: Structure sensitive contextual hypothesis: units, which are similar to a text according to the contextual hypothesis, contribute to the structuring of its meaning.
Since we seek a model for automatic text representation for which nonlinguistic context is inaccessible, we limit contextual similarity to paradigmatic similarity. On this basis the latter two hypotheses can be summarized as follows: Definition 1. Let C be a corpus in which we observe paradigmatic regularities of words. The textual connotation of a text x with respect to C includes those texts of C, whose constituents realize similar paradigmatic regularities as the lexical constituents of x. The connotation of x is structured on the basis of the same relation of (indirect) paradigmatic similarity interrelating the connoted texts.
In order to model this concept of structured connotation, we use the space model M0 of (Rieger, 1984) as a point of departure and derive three text representation models M1, M2, M3. Since M0 only maps words onto semantic space we extend it in order to derive meaning points of texts. This is done as follows: M0 analyses word meanings as the result of a two-stage process of unsupervised learning. It builds a lexical semantic space by modeling syntagmatic regularities with a correlation coefficient α : W → C ⊂ R n and their differences with an Euclidean metric δ : C → S ⊂ R n , where W is the set of words, C is called corpus space representing syntagmatic regularities, and S is called semantic space representing paradigmatic regularities. |W | = n is the number of dimensions of both spaces. Neighborhoods of meaning points assigned to words model their semantic similarity: the shorter the points' distances in semantic space, the more paradigmatically similar the words.
The set of words W , spanning the semantic space, is selected on the basis of the criterion of document frequency, which proves to be of comparable effectiveness as information gain and χ 2 -statistics (Yang and Pedersen, 1997). Fur-thermore, instead of using explicit stop word lists, we restricted W to the set of lemmatized nouns, verbs, adjectives, and adverbs.
M1: In a second step, we use S as a format for representing meaning points of texts, which are mapped onto S with the help of a weighted mean of the meaning points assigned to their lexical constituents: (1) x k is the meaning point of text x k ∈ C, a i the meaning point of word a i ∈ W , and W (x k ) is the set of all types of all tokens in x k . Finally, w ik is a weight having the same role as the tfidfscores in IR (Salton and Buckley, 1988). As a result of mapping texts onto S, they can be compared with respect to the paradigmatic similarity of their lexical organization. This is done with the help of a similarity measure σ based on an Euclidean metric δ operating on meaning points and standardized to the unit interval: σ is interpreted as follows: the higher σ( x, y) for two texts x and y, the shorter the distance of their meaning points x and y in semantic space, the more similar the paradigmatic usage regularities of their lexical constituents, and finally the more semantically similar these texts according to the extended contextual hypothesis. This is the point, where semantic spaces depart from the vector space model, since they do not demand that the texts in question share any lexical constituents in order to be similar; the intersection of the sets of their lexical constituents may even be empty. M2: So far, only lexical features are considered. We depart a step further from the bag of words model by additionally comparing texts with respect to their organization. This is done with the help of a set of quantitative text characteristics used by (Tuldava, 1998) for automatic genre analysis: type-token ratio, hapax legomena, (variation of) mean word frequency, average sentence length, and action coefficient (i.e. the standardized ratio of verbs and adjectives in a text). In order to make these features comparable, they were standardized using z-scores so that random variables were derived with means of 0 and variances of 1. Be-yond these characteristics, a further feature was considered: each text was mapped onto a so called text structure string representing its division into sections, paragraphs, and sentences as a course approximation of its rhetorical structure. For example, a text structure string denotes a text T of two sections D, where the first includes 1 and the second 3 sentences S.
Using the Levenshtein metric for string comparison, this allows to measure the rhetorical similarity of texts in a first approximation. The idea is to distinguish units connoted by a text, which in spite of having similar lexical organizations differ texturally. If for example a short commentary connotes two equally similar texts, another commentary and a long report, the commentary should be preferred. Thus, in M2 the textual connotation of a text is not only seen to be structured on the basis of the criterion of similarity of lexical organization, but also by means of genre specific features modeled as quantitative text characteristics. This approach follows (Herdan, 1966), who programmatically asked, whether difference in style correlates with difference in frequency of use of linguistic forms. See (Wolters and Kirsten, 1999) who, following this approach, already used POS frequency as a source for genre classification, a task which goes beyond the scope of the given paper. On this background a compound text similarity measure can be derived as a linear model: a. where σ 1 (x, y) = σ( x, y) models lexical semantics of texts x, y according to M1; b. σ 2 uses the Levenshtein metric for measuring the similarity of the text structure stings assigned to x and y; c. and σ 3 measures, based on an Euclidean metric, the similarity of texts with respect to the quantitative features enumerated above.
ω i biases the contribution of these different dimensions of text representation. We yield good results for ω 1 = 0.9, ω 2 = ω 3 = 0.05. M3: Finally, we experimented with a text representation model resulting from the aggre-gation (i.e. weighted mean) of the vector representations of a text in both spaces, i.e. vector and semantic space. This approach, which demands both spaces to have exactly the same dimensions and standardized coordinate values, follows the idea to reduce the noise inherent to both models: whether syntagmatic as in case of vector spaces, or paradigmatic as in case of semantic spaces. We experimented with equal weights of both input vectors.
In the next section we use the text representation models M1, M2, M3 as different starting points for modeling the concept of structured connotation as defined in definition (1):

Text Linkage
Departing from ordinary list as well as cluster structures, we model the connotation of a text as a hierarchy, where each node represents a single connoted text (and not a set of texts as in case of agglomerative cluster analysis). In order to narrow down a solution for this task we need a linguistic criterion, which bridges between the linguistic knowledge represented in semantic spaces and the task of connotative text linkage. For this purpose we refer to the concept of lexical cohesion introduced by (Halliday and Hasan, 1976); see (Morris and Hirst, 1991;Hearst, 1997;Marcu, 2000) who already use this concept for text segmentation. According to this approach, lexical cohesion results from reiterating words, which are semantically related on the basis of (un-)systematic relations (e.g. synonymy or hyponymy). Unsystematic lexical cohesion results from patterns of contextual, paradigmatic similarity: "[. . . ] lexical items having similar patterns of collocation-that is, tending to appear in similar contexts-will generate a cohesive force if they occur in adjacent sentences." (Halliday and Hasan, 1976, p. 286). Several factors influencing this cohesive force are decisive for reconstructing the concept of textual connotation:(i) the contextual similarity of the words in question, (ii) their syntagmatic order, and (iii) the distances of their occurrences. These factors cooperate as follows: the shorter the distance of similar words in a text the higher their cohesive force. Furthermore, preceding lexical choices restrict (the interpretation of) subsequent ones, an effect, which retards as their distance grows. But longer dis-tances may be compensated by higher contextual similarities so that highly related words can contribute to the cohesion of a text span even if they distantly co-occur. By means of restricting contextual to paradigmatic similarity and therefore measuring unsystematic lexical cohesion as a function of paradigmatic regularities, the transfer of this concept to the task of hierarchically modeling textual connotations becomes straightforward. Given a text x, whose connotation is to be represented as a tree T , we demand for any path P starting with root x: (i) Similarity: If text y is more similar to x than z, then the path between x and y is shorter than between x and z, supposed that y and z belong to the same path P .
(ii) Order: The shorter the distance between y and z in P , the higher their cohesive force, and vice versa: the longer the path, the higher the probability that the subsequent z is paradigmatically dissimilar to y.
(iii) Distance: A cohesive impact is preserved even in case of longer paths, supposed that the textual nodes lying in between are paradigmatically similar to a high degree.
The reason underlying these criteria is the need to control negative effects of intransitive similarity relations: in case that text x is highly similar to y, and y to z, it is not guaranteed that (x, y, z) is a cohesive path, since similarity is not transitive. In order to reduce this risk of incohesive paths, the latter criteria demand that there is a cohesive force even between nodes which are not immediately linked. This demand decreases as the path distance of nodes increases so that topic changes latently controlled by preceding nodes can be realized. In other words: adding text z to the hierarchically structured connotation of x, we do not simply look for an already inserted text y, to which z is most similar, but to a path P , which minimizes the loss of cohesion in the overall tree, when z is attached to P . These comments induce an optimality criterion which tries to optimize cohesion not only of directly linked nodes, but of whole paths, thereby reflecting their syntagmatic order. Looking for a mathematical model of this optimality criterion, minimal spanning trees (MST) drop out, since they only optimize direct node-to-node similarities disregarding any path context. Furthermore, whereas we expect to yield different trees modeling the connotations of different texts, MSTs ignore this aspect dependency since they focus on a unique spanning tree of the underlying feature space. Another candidate is given by dependency trees (Rieger, 1984) which are equal to similarity trees (Lin, 1998): for a given root x, the nodes are inserted into its similarity tree (ST) in descending order of their similarity to x, where the predecessor of any node z is chosen to be the node y already inserted, to which z is most similar. Although STs already capture the aspect dependency induced by their varying roots, the path criterion is still not met. Thus, we generalize the concept of a ST to that of a cohesion tree as follows: First, we observe that the construction of STs uses two types of order relations: the first, let it call ≤ 1 x , determines the order of the nodes inserted dependent on root x; the second, let it call ≤ 2 y , varies with node y to be inserted and determines its predecessor. Next, in order to build cohesion trees out of this skeleton, we instantiate all relations ≤ 2 y in a way, which finds the path of minimal loss of cohesion when y is attached to it. This is done with the help of a distance measure which induces a descending order of cohesion of paths: Definition 2. Let G = V, E be a graph and P = (v 1 , . . . , v k ) a simple path in G. The path sensitive distanceδ(P, y) of y ∈ V with respect to P is defined aŝ where v i ∈V (P ) ω i ≤ 1, max(δ) is the maximal value assumed by distance measure δ, and V (P ) is the set of all nodes of path P .
It is clear that for any of the text representation models M1, M2, M3 and their corresponding similarity measures we get different distance measuresδ which can be used to instantiate the order relations ≤ 2 y in order to determine the end vertex of the path of minimal loss of cohesion when y is attached to it. In case of increasing biases ω i for increasing index i in definition (2) the syntagmatic order of path P is reflected in the sense that the shorter the distance of x to any vertex in P , the higher the impact of their (dis-)similarity measured by δ, the higher their cohesive force. Using the relations ≤ 2 y we can now formalize the concept of a cohesion tree: Definition 3. Let G = V, E, ω be a complete weighted graph induced by a semantic space, and x ∈ V a node. The graph D(G, x) = V, E, ν with E = {{v, w} | v < 1 x w ∧ ¬∃y ∈ V : y < 1 x w ∧ y < 2 w v} and ν : E → R, the restriction of ω to E, is called cohesion tree induced by x.
Using this definition of a cohesion tree (CT) we can compute hierarchical models of the connotations of texts, in which not only aspect dependency induced by the corresponding root, but also path cohesion is taken into account.
A note on the relation between CTs and cluster analysis: CTs do not only depart from cluster hierarchies, since their nodes represent single objects, and not sets, but also because they refer to a local, contextsensitive building criterion (with respect to their roots and paths). In contrast to this, cluster analysis tries to find a global partition of the data set. Nevertheless there is a connection between both methods of unsupervised learning: Given a MST, there is a simple procedure to yield a divisive partition (Duda et al., 2001). Moreover, single linkage graphs are based on a comparable criterion as MSTs. Analogously, a given CT can be divided into non-overlapping clusters by deleting those edges whose length is above a certain threshold. This induces, so to say, perspective clusters organized dependent on the perspective of the root and paths of the underlying CT.

Evaluation
Figure (1) exemplifies a CT based on M3 using a textual root dealing with the "BSE Food Scandal" from 1996. The text sample belongs to a corpus of 502 texts of the German newspaper Süddeutsche Zeitung of about 320,000 running words. Each text belongs to an element of a set T of 18 different subject categories (e.g. politics, sports). Based on the lemmatized corpus a semantic space of 2715 lexical dimensions was built and all texts were mapped onto this space according to the specifications of M3. In figure (1) each textual node of the CT is represented by its headline and subject category as found in the newspaper. All computations were performed using a set of C++ programs especially implemented for this study.
In order to rate models M1, M2, M3 in comparison to the vector space model (VS) using MSTs, STs and CTs as alternative hierarchical models we proceed as follows: as a simple measure of representational goodness we compute the average categorial cohesion of links of all MSTs, STs and CTs for the different models and all texts in the corpus. Let G = V, E be a tree of textual nodes x ∈ V , each of which is assigned to a subject category τ (x) ∈ T , and P (G) the set of all paths in G starting with root x and ending with a leaf, then the categorial cohesion of G is the average number of links (v i , v j ) ∈ E per path P ∈ P (G), where τ (v i ) = τ (v j ). The more nodes of identical categories are linked in paths in G, the more categorially homogeneous these paths, the higher the average categorial cohesion of G. According to the conceptual basis of CTs we expect these trees to be of highest categorial link cohesion, but this is not true: MSTs produce the highest cohesion values in case of VS and M3. Furthermore, we observe that model M3 induces trees of highest cohesion and lowest variance, whereas VS shows the highest variance and lowest cohesion scores in case of STs and CTs. In other words: based on semantic spaces, models M1, M2, and M3 produce more stable results than the vector space model.
Using M3 as a starting point it can be asked more precisely, which tree class produces the most cohesive model of text connotation. Clearly, the measure of categorial link cohesion is not sufficient to evaluate the classes, since two immediately linked texts belonging to the same  (Steinbach et al., 2000) propose a measure which estimates the overall cohesion of a cluster. This measure can be directly applied to trees: let P v 1 ,vn = (v 1 , . . . , v n ) be a path in tree G = V, E starting with root v 1 = x, we compute the cohesion of P irrespective of the order of its nodes as follows: The more similar the nodes of path P according to metric δ, the more cohesive P . δ is derived from the distance measure operating on the semantic space to which texts v i are mapped. As before, all scores ξ(P ) are summed up for all paths in P (G) and standardized by means of |P (G)|. This guarantees that neither trees of maximum height (MHT) nor of maximum degree (MDT), i.e. trees which trivially correspond to lists, are assigned highest cohesion values. The results of summing up these scores for all trees of a given class for all texts in the test corpus are shown in  CTs and STs realize the most cohesive structures. This is more obvious if the scores ξ(G) are compared for each text in separation: in 494 cases, CTs are of highest cohesion according to measure (5). In only 7 cases, MST are of highest cohesion, and in only one case, the corresponding ST is of highest cohesion. Moreover, even the stochastically organized so called random successor trees (RST), in which successor node's and their predecessors are randomly chosen, produce more cohesive structures than lists (i.e. MDTs and MHTs), which form the predominant format used to organize search results in Internet. To sum up: Table (2) rates CTs in combination with model M3 on highest level. Thus, from the point of view of lexical semantics CTs realize more cohesive branches than MSTs. But whether these differences are significant, is hard to evaluate, since their theoretical distribution is unknown. Thus, future work will be on finding these distributions.

Conclusion
This paper proposed 3 numerical representation formats as means for modeling the hierarchical connotation of texts in combination with cohesion trees. This was done by extending the weak contextual hypothesis onto the level of texts in combination with a reinterpretation of the concept of lexical cohesion as a source for text linkage. Although the formats used depart from the bag of words model there is still the need of investigating numerical formats which rely on linguistically more profound discourse models.


SOAT: A Semi-Automatic Domain Ontology Acquisition Tool from Chinese Corpus

In this paper, we focus on the domain ontology acquisition from Chinese corpus by extracting rules designed for Chinese phrases. These rules are noun sequences with part-of-speech tags. Experiments show that this process can construct domain ontology prototypes efficiently and effectively.

Introduction
Domain ontology is important for large-scale natural language application systems such as speech recognition (Flett & Brown 2001), question answering (QA), knowledge management and organization memory (KM/OM), information retrieval, machine translation (Guarino 1998), and grammar checking systems (Bredenkamp 2000). With the help of domain ontology, software systems can perform better in understanding natural language. However, building domain ontology is laborious and time consuming. Previous works suggest that ontology acquisition is an iterative process which includes keyword collection as well as structure reorganization. The ontology will be revised, refined, and filled in detail during iteration. (Noy and McGuinness 2001) For example (Hearst 1992), in order to find a hyponym of a keyword, the human editor must observe sentences containing this keyword and its related hyponyms. The editor then deduces rules for finding more hyponyms of this keyword. As such cycle iterates, the editor refines the rules to obtain better quality pairs of keyword-hyponyms. In this work we try to speed up the above labor-intensive approach by designing acquisition rules that can be applied recursively.
A human editor only has to verify the results of the acquisition. The extraction rules we specified are templates of part-of-speech (POS) tagged phrase structure. Parsing a phrase by POS tags (Abney 1991) is a well-known shallow parsing technique, which provides the natural language processing function for different natural language applications including ontology acquisition (Maedche and Staab 2000). In previous works (Hsu et al. 2001), we have constructed a knowledge representation framework, InfoMap, to integrate various linguistic knowledge, commonsense knowledge and domain knowledge. InfoMap is designed to perform natural language understanding. It has been applied to many application domains, such as QA system and KM/OM (Wu et al. 2002) and has obtained encouraging results. An important characteristic of InfoMap is to extract events from a sentence by capturing the topic words, usually noun-verb (NV) pairs or noun-noun (NN) pairs, which is defined in domain ontology. We design the SOAT as a semi-automatic domain ontology acquisition tool following the ontology framework, InfoMap. We shall review the InfoMap ontology framework in section 2. The domain ontology acquisition process and extraction rules will be discussed in Section 3. Experimental results are reported in section 4. We conclude our work in Section 5.

The InfoMap Framework
Gruber defines an ontology to be a description of concepts and relationships (Gruber 1993

The Structure of InfoMap
InfoMap consists of domain concepts and their associated attributes, activities, etc., which are its related concepts. Each of the concepts forms a tree-like taxonomy. InfoMap defines "reference" nodes to connect nodes on different branches, thereby integrating these concepts into a semantic network. InfoMap not only classifies concepts, but also classifies the relationships among concepts. There are two types of nodes in InfoMap: concept nodes and function nodes. The root node of a domain is the name of the domain. Following the root node, topics are found in this domain that may be of interest to users. These topics have sub-categories that list related sub-topics in a recursive fashion.

Function Nodes in InfoMap
InfoMap uses function nodes to label different relationships among related concept nodes. The basic function nodes are: category, attribute, synonym, and activity, which are described below. 1. Category: Various ways of dividing up a concept A. For example, for the concept of "people", we can divide it into young, mid-age and old people according to "age". Another way is to divide it into men and women according to "sex", or rich and poor people according to "wealth", etc. For each such partition, we shall attach a "cause". Each such division can be regarded as an angle of viewing concept A. 2. Attribute: Properties of concept A. For example, the attributes of a human being can be the organs, the height, the weight, hobbies, etc. 3. Associated activity: Actions that can be associated with concept A. For example, if A is a "car", then it can be driven, parked, raced, washed, repaired, etc. 4. Synonym: Expressions that are synonymous to concept A in the context.

The Contextual View of InfoMap
Generally speaking, an ontology consists of definitions of concepts, relations and axioms. A well known ontology, WordNet (Miller 1990), has the following features: hypernymy, hyponymy, antonymy, semantic relationship, and synset. Comparing with the globlal view of concepts in WordNet, InfoMap defines category, event, atttibute, and synonym in a more contextual fashion. For example, the synonym of a concept in InfoMap is valid only in this particular context. This is very different from the synset in WordNet. Each node B underneath a function node (synonym, attribute, activity or category) of A can be treated as a related concept of A and can be further expanded by describing other relations pertaining to B. However, the relations for B described therein will be "limited under the context of A". For example, if A is "organization" and B is the "facility" attribute of A, then underneath the node B we shall list those facilities one can normally find in an organization, whereas for the "facility" attribute of "hotel", we shall only list those existing facilities in hotel.

The Inference Engine of InfoMap
The kernel program can map a natural language sentence into a set of nodes and uses the edited knowledge to recognize the events in the user's sentences. Technically, InfoMap matches a natural language sentence to a collection of concept notes. There is a firing mechanism that finds nodes in InfoMap relevent to the input sentence. Suppose we want to find the event of the following sentence: "How do I invest in stocks?" and the interrogative word "how" can fire the word "method". Then along the path from "method" to "stock" the above sentence has fired the concepts "stock" and "invest". Thus, the above sentence will correspond to the path: stock -eventinvest -attributemethod Given enough knowledge about the events related to the main concept, InfoMap can be used to parse Chinese sentences. Readers can refer to (Hsu et al. 2001) for a thorough description of InfoMap.

Automatic Domain Ontology Acquisition
To build an ontology for a new domain, we need to collect domain keywords and find the relationships among them. An acquisition process, SOAT, is designed that can construct a new ontology through domain corpus. Thus, with little human intervention, SOAT can build a prototype of the domain ontology. As described in previous sections, InfoMap consists of two major relations among concepts, i.e., Taxonomic relations (category and synonym) and Non-taxonomic relations (attribute and event). We defined sentence templates, which consists of patterns of keywords and variables, to capture these relations.

Description of SOAT
Given the domain corpus with the POS tag, our SOAT can be described as follows. Input: domain corpus with the POS tag Output: domain ontology prototype Steps: 1 Select a keyword (usually the name of the domain) in the corpus as the seed to form a potential root set R 2 Begin the following recursive process: 2.1 Pick a keyword A as the root from R 2.2 Find a new related keyword B of the root A by extraction rules and add it into the domain ontology according to the rules. 2.3 If there is no more related keywords, remove A from R 2.4 Put B into the potential root set 2.5 Repeat step 2, until either R becomes empty or the total number of nodes generated exceeds a prescribed threshold. We find that most of the domain keywords are not in the dictionary. So the traditional TF/IDF method would fail. Instead, we use the high frequency new words discovered by PAT-tree as the seeds. Ideally, SOAT can generate an domain ontology prototype automatically. However, the extraction rules need to be refined and updated by a human editor. The details of SOAT extraction rules are in Section 3.2.

The Extraction Rules of SOAT
The extraction rules in Tables 1, 2, 3 and 4, consists of a specific noun as the root, and the POS tags of the neighboring words. A rule is a linguistic template for finding keywords related to the root. The target of extraction is usually a word or a compound word, which has strong semantic links to the root. Our rules are especially effective in identifying essential compound words for a specific domain. We use POS tags defined by CKIP (CKIP 1993), in which Na is the generic noun, Nb is the proper noun, and Nc is the toponym. Generally, an Na can be a subject or an object in a sentence, including concrete noun and abstract noun, such as "cloth", "table", "tax", and "technology". An Nc is the name of a place. Readers can refer to CKIP (CKIP 1993) for more information about the POS tag. In our experiment, we focus on Na and Nc, because the topics that we are interested in usually fall in these two categories. The extraction rules of finding categorical (taxonomy) relationships from a given Na (or Nc) are in Table 1 (and 3). The rules of finding attribute (non-taxonomy) relationships from a given Na (or Nc) are in Table 2 (and 4).    Li and Thompson (1981) describe Mandarin Chinese as a Topic-prominent language in which the subject or the object is not as obvious as in other languages. Therefore, the highly precise shallow parsing result (Munoz et al. 1999) on NN and SV pairs in English is probably not applicable to Chinese.

The Experiment of Extraction Rate
To test the qualitative and quantitative performance of SOAT, we design two experiments. We construct three domain ontology prototypes for three different domains and corpora. Table 5 shows the result in which the frequently asked questions (FAQs) for stocks are taken from test sentences of the financial QA system. The university and bank corpora are collected from the CKIP corpus (CKIP 1995). We select sentences containing the keyword "University" or "Bank" as the domain corpora. The results in Table 5 show that SOAT can capture related keywords and the relationships among them from limited sentences very efficiently without using the frequency.

Results from Different Corpora
We select three different corpora from different information resources in the "network" domain. The first corpus is a collection of FAQ sentences about computer network. The second corpus is a collection of sentences containing the keyword "network" from the CKIP corpus. The third corpus is the collection of sentences from Windows 2000 online help document. To reduce the cost of human verification, we limit the size of corpus to 275 sentences. The result in Table 6 shows that there is a trade-off between extraction rate and the accuracy rate. The quantity is estimated on 4*(25+42)=268 FAQ query concepts at least. Thus, the productivity of using SOAT is approximated 268% times. It is obvious that SOAT can help reducing the cost of building a new domain ontology.

Conclusion
We present a semi-automatic process of domain ontology acquisition from domain corpus. The ontology schema we used is general enough for different applications and specific enough for the task of understanding the Chinese natural language. The main objective of the research is to extract useful relationships from domain articles to construct domain ontology prototypes in a semi-automatic fashion. The SOAT extraction rules we developed can identify keywords with strong semantic links, especially those compound words in the domain.
We have discussed how to extract related NN pairs in Section 3 for SOAT. However, the extraction rules for NN pairs do not apply for NV pairs. In the future we shall follow the approach in  to extract the relationships between nouns and its related verbs. The main restriction of SOAT is that the quality of the corpus must be very high, namely, the sentences are accurate and abundant enough to include most of the important relationships to be extracted.


A Simple Pattern-matching Algorithm for Recovering Empty Nodes and their Antecedents

This paper describes a simple pattern-matching algorithm for recovering empty nodes and identifying their co-indexed antecedents in phrase structure trees that do not contain this information. The patterns are minimal connected tree fragments containing an empty node and all other nodes co-indexed with it. This paper also proposes an evaluation procedure for empty node recovery procedures which is independent of most of the details of phrase structure, which makes it possible to compare the performance of empty node recovery on parser output with the empty node annotations in a gold-standard corpus. Evaluating the algorithm on the output of Charniak's parser (Charniak, 2000) and the Penn treebank (Marcus et al., 1993) shows that the pattern-matching algorithm does surprisingly well on the most frequently occuring types of empty nodes given its simplicity.

Introduction
One of the main motivations for research on parsing is that syntactic structure provides important information for semantic interpretation; hence syntactic parsing is an important first step in a variety of * I would like to thank my colleages in the Brown Laboratory for Linguistic Information Processing (BLLIP) as well as Michael Collins for their advice. This research was supported by NSF awards DMS 0074276 and ITR IIS 0085940. useful tasks. Broad coverage syntactic parsers with good performance have recently become available (Charniak, 2000;Collins, 2000), but these typically produce as output a parse tree that only encodes local syntactic information, i.e., a tree that does not include any "empty nodes". (Collins (1997) discusses the recovery of one kind of empty node, viz., WH-traces). This paper describes a simple patternmatching algorithm for post-processing the output of such parsers to add a wide variety of empty nodes to its parse trees.
Empty nodes encode additional information about non-local dependencies between words and phrases which is important for the interpretation of constructions such as WH-questions, relative clauses, etc. 1 For example, in the noun phrase the man Sam likes the fact the man is interpreted as the direct object of the verb likes is indicated in Penn treebank notation by empty nodes and coindexation as shown in Figure 1 (see the next section for an explanation of why likes is tagged VBZ t rather than the standard VBZ).
The broad-coverage statistical parsers just mentioned produce a simpler tree structure for such a relative clause that contains neither of the empty nodes just indicated. Rather, they produce trees of the kind shown in Figure 2. Unlike the tree depicted in Figure 1, this type of tree does not explicitly represent the relationship between likes and the man.
This paper presents an algorithm that takes as its input a tree without empty nodes of the kind shown 1 There are other ways to represent this information that do not require empty nodes; however, information about non-local dependencies must be represented somehow in order to interpret these constructions. in Figure 2 and modifies it by inserting empty nodes and coindexation to produce a the tree shown in Figure 1. The algorithm is described in detail in section 2. The standard Parseval precision and recall measures for evaluating parse accuracy do not measure the accuracy of empty node and antecedent recovery, but there is a fairly straightforward extension of them that can evaluate empty node and antecedent recovery, as described in section 3. The rest of this section provides a brief introduction to empty nodes, especially as they are used in the Penn Treebank.
Non-local dependencies and displacement phenomena, such as Passive and WH-movement, have been a central topic of generative linguistics since its inception half a century ago. However, current linguistic research focuses on explaining the possible non-local dependencies, and has little to say about how likely different kinds of dependencies are. Many current linguistic theories of non-local dependencies are extremely complex, and would be difficult to apply with the kind of broad coverage described here. Psycholinguists have also investigated certain kinds of non-local dependencies, and their theories of parsing preferences might serve as the basis for specialized algorithms for recovering certain kinds of non-local dependencies, such as WH dependencies. All of these approaches require considerably more specialized linguitic knowledge than the pattern-matching algorithm described here. This algorithm is both simple and general, and can serve as a benchmark against which more complex approaches can be evaluated. The pattern-matching approach is not tied to any particular linguistic theory, but it does require a treebank training corpus from which the algorithm extracts its patterns. We used sections 2-21 of the Penn Treebank as the training corpus; section 24 was used as the development corpus for experimentation and tuning, while the test corpus (section 23) was used exactly once (to obtain the results in section 3). Chapter 4 of the Penn Treebank tagging guidelines (Bies et al., 1995) contains an extensive description of the kinds of empty nodes and the use of co-indexation in the Penn Treebank. Table 1 contains summary statistics on the distribution of empty nodes in the Penn Treebank. The entry with POS SBAR and no label refers to a "compound" type of empty structure labelled SBAR consisting of an empty complementizer and an empty (moved) S (thus SBAR is really a nonterminal label rather than a part of speech); a typical example is shown in Figure 3. As might be expected the distribution is highly skewed, with most of the empty node tokens belonging to just a few types. Because of this, a system can provide good average performance on all empty nodes if it performs well on the most frequent types of empty nodes, and conversely, a system will perform poorly on average if it does not perform at least moderately well on the most common types of empty nodes, irrespective of how well it performs on more esoteric constructions.

A pattern-matching algorithm
This section describes the pattern-matching algorithm in detail. In broad outline the algorithm can

POS
Label Count Description NP NP * 18,334 NP trace (e.g., Sam was seen *) NP * 9,812 NP PRO (e.g., * to sleep is nice) WHNP NP *T* 8,620 WH trace (e.g., the woman who you saw *T*) *U* 7,478 Empty units (e.g., $ 25 *U*) 0 5,635 Empty complementizers (e.g., Sam said 0 Sasha snores) S S *T* 4,063 Moved clauses (e.g., Sam had to go, Sasha explained *T*) WHADVP ADVP *T* 2,492 WH-trace (e.g., Sam explained how to leave *T*) SBAR 2,033 Empty clauses (e.g., Sam had to go, Sasha explained (SBAR)) WHNP 0 1,759 Empty relative pronouns (e.g., the woman 0 we saw) WHADVP 0 575 Empty relative pronouns (e.g., no reason 0 to leave) Table 1: The distribution of the 10 most frequent types of empty nodes and their antecedents in sections 2-21 of the Penn Treebank (there are approximately 64,000 empty nodes in total). The "label" column gives the terminal label of the empty node, the "POS" column gives its preterminal label and the "Antecedent" column gives the label of its antecedent. The entry with an SBAR POS and empty label corresponds to an empty compound SBAR subtree, as explained in the text and Figure 3. be regarded as an instance of the Memory-Based Learning approach, where both the pattern extraction and pattern matching involve recursively visiting all of the subtrees of the tree concerned. It can also be regarded as a kind of tree transformation, so the overall system architecture (including the parser) is an instance of the "transform-detransform" approach advocated by Johnson (1998). The algorithm has two phases. The first phase of the algorithm extracts the patterns from the trees in the training corpus. The second phase of the algorithm uses these extracted patterns to insert empty nodes and index their antecedents in trees that do not contain empty nodes. Before the trees are used in the training and insertion phases they are passed through a common preproccessing step, which relabels preterminal nodes dominating auxiliary verbs and transitive verbs.

Auxiliary and transitivity annotation
The preprocessing step relabels auxiliary verbs and transitive verbs in all trees seen by the algorithm. This relabelling is deterministic and depends only on the terminal (i.e., the word) and its preterminal label. Auxiliary verbs such as is and being are relabelled as either a AUX or AUXG respectively. The relabelling of auxiliary verbs was performed primarily because Charniak's parser (which produced one of the test corpora) produces trees with such labels; experiments (on the development section) show that auxiliary relabelling has little effect on the algorithm's performance.
The transitive verb relabelling suffixes the preterminal labels of transitive verbs with " t". For example, in Figure 1 the verb likes is relabelled VBZ t in this step. A verb is deemed transitive if its stem is followed by an NP without any grammatical function annotation at least 50% of the time in the training corpus; all such verbs are relabelled whether or not any particular instance is followed by an NP.
Intuitively, transitivity would seem to be a powerful cue that there is an empty node following a verb. Experiments on the development corpus showed that transitivity annotation provides a small but useful improvement to the algorithm's performance. The accuracy of transitivity labelling was not systematically evaluated here.

Patterns and matchings
Informally, patterns are minimal connected tree fragments containing an empty node and all nodes co-indexed with it. The intuition is that the path from the empty node to its antecedents specifies important aspects of the context in which the empty node can appear.
There are many different possible ways of realizing this intuition, but all of the ones tried gave approximately similar results so we present the simplest one here. The results given below were generated where the pattern for an empty node is the minimal tree fragment (i.e., connected set of local trees) required to connect the empty node with all of the nodes coindexed with it. Any indices occuring on nodes in the pattern are systematically renumbered beginning with 1. If an empty node does not bear an index, its pattern is just the local tree containing it. Figure 4 displays the single pattern that would be extracted corresponding to the two empty nodes in the tree depicted in Figure 1.
For this kind of pattern we define pattern matching informally as follows. If p is a pattern and t is a tree, then p matches t iff t is an extension of p ignoring empty nodes in p. For example, the pattern displayed in Figure 4 matches the subtree rooted under SBAR depicted in Figure 2.
If a pattern p matches a tree t, then it is possible to substitute p for the fragment of t that it matches. For example, the result of substituting the pattern shown in Figure 4 for the subtree rooted under SBAR depicted in Figure 2 is the tree shown in Figure 1. Note that the substitution process must "standardize apart" or renumber indices appropriately in order to avoid accidentally labelling empty nodes inserted by two independent patterns with the same index.
Pattern matching and substitution can be defined more rigorously using tree automata (Gécseg and Steinby, 1984), but for reasons of space these definitions are not given here.
In fact, the actual implementation of pattern matching and substitution used here is considerably more complex than just described. It goes to some lengths to handle complex cases such as adjunction and where two or more empty nodes' paths cross (in these cases the pattern extracted consists of the union of the local trees that constitute the patterns for each of the empty nodes). However, given the low frequency of these constructions, there is probably only one case where this extra complexity is justified: viz., the empty compound SBAR subtree shown in Figure 3.

Empty node insertion
Suppose we have a rank-ordered list of patterns (the next subsection describes how to obtain such a list). The procedure that uses these to insert empty nodes into a tree t not containing empty nodes is as follows. We perform a pre-order traversal of the subtrees of t (i.e., visit parents before their children), and at each subtree we find the set of patterns that match the subtree. If this set is non-empty we substitute the highest ranked pattern in the set into the subtree, inserting an empty node and (if required) co-indexing it with its antecedents.
Note that the use of a pre-order traversal effectively biases the procedure toward "deeper", more embedded patterns. Since empty nodes are typically located in the most embedded local trees of patterns (i.e., movement is usually "upward" in a tree), if two different patterns (corresponding to different non-local dependencies) could potentially insert empty nodes into the same tree fragment in t, the deeper pattern will match at a higher node in t, and hence will be substituted. Since the substitution of one pattern typically destroys the context for a match of another pattern, the shallower patterns no longer match. On the other hand, since shal-lower patterns contain less structure they are likely to match a greater variety of trees than the deeper patterns, they still have ample opportunity to apply.
Finally, the pattern matching process can be speeded considerably by indexing patterns appropriately, since the number of patterns involved is quite large (approximately 11,000). For patterns of the kind described here, patterns can be indexed on their topmost local tree (i.e., the pattern's root node label and the sequence of node labels of its children).

Pattern extraction
After relabelling preterminals as described above, patterns are extracted during a traversal of each of the trees in the training corpus. Table 2 lists the most frequent patterns extracted from the Penn Treebank training corpus. The algorithm also records how often each pattern was seen; this is shown in the "count" column of Table 2.
The next step of the algorithm determines approximately how many times each pattern can match some subtree of a version of the training corpus from which all empty nodes have been removed (regardless of whether or not the corresponding substitutions would insert empty nodes correctly). This information is shown under the "match" column in Table 2, and is used to filter patterns which would most often be incorrect to apply even though they match. If c is the count value for a pattern and m is its match value, then the algorithm discards that pattern when the lower bound of a 67% confidence interval for its success probability (given c successes out of m trials) is less than 1/2. This is a standard technique for "discounting" success probabilities from small sample size data (Witten and Frank, 2000). (As explained immediately below, the estimates of c and m given in Table 2 are inaccurate, so whenever the estimate of m is less than c we replace m by c in this calculation). This pruning removes approximately 2,000 patterns, leaving 9,000 patterns.
The match value is obtained by making a second pre-order traversal through a version of the training data from which empty nodes are removed. It turns out that subtle differences in how the match value is obtained make a large difference to the algorithm's performance. Initially we defined the match value of a pattern to be the number of subtrees that match that pattern in the training corpus. But as ex-plained above, the earlier substitution of a deeper pattern may prevent smaller patterns from applying, so this simple definition of match value undoubtedly over-estimates the number of times shallow patterns might apply. To avoid this over-estimation, after we have matched all patterns against a node of a training corpus tree we determine the correct pattern (if any) to apply in order to recover the empty nodes that were originally present, and reinsert the relevant empty nodes. This blocks the matching of shallower patterns, reducing their match values and hence raising their success probability. (Undoubtedly the "count" values are also over-estimated in the same way; however, experiments showed that estimating count values in a similar manner to the way in which match values are estimated reduces the algorithm's performance).
Finally, we rank all of the remaining patterns. We experimented with several different ranking criteria, including pattern depth, success probability (i.e., c/m) and discounted success probability. Perhaps surprisingly, all produced similiar results on the development corpus. We used pattern depth as the ranking criterion to produce the results reported below because it ensures that "deep" patterns receive a chance to apply. For example, this ensures that the pattern inserting an empty NP * and WHNP can apply before the pattern inserting an empty complementizer 0.

Empty node recovery evaluation
The previous section described an algorithm for restoring empty nodes and co-indexing their antecedents. This section describes two evaluation procedures for such algorithms. The first, which measures the accuracy of empty node recovery but not co-indexation, is just the standard Parseval evaluation applied to empty nodes only, viz., precision and recall and scores derived from these. In this evaluation, each node is represented by a triple consisting of its category and its left and right string positions. (Note that because empty nodes dominate the empty string, their left and right string positions of empty nodes are always identical).
Let G be the set of such empty node representations derived from the "gold standard" evaluation corpus and T the set of empty node representations Table 2: The most common empty node patterns found in the Penn Treebank training corpus. The Count column is the number of times the pattern was found, and the Match column is an estimate of the number of times that this pattern matches some subtree in the training corpus during empty node recovery, as explained in the text. derived from the corpus to be evaluated. Then as is standard, the precision P , recall R and f-score f are calculated as follows: Table 3 provides these measures for two different test corpora: (i) a version of section 23 of the Penn Treebank from which empty nodes, indices and unary branching chains consisting of nodes of the same category were removed, and (ii) the trees produced by Charniak's parser on the strings of section 23 (Charniak, 2000).
To evaluate co-indexation of empty nodes and their antecedents, we augment the representation of empty nodes as follows. The augmented representation for empty nodes consists of the triple of category plus string positions as above, together with the set of triples of all of the non-empty nodes the empty node is co-indexed with. (Usually this set of antecedents is either empty or contains a single node). Precision, recall and f-score are defined for these augmented representations as before.
Note that this is a particularly stringent evaluation measure for a system including a parser, since it is necessary for the parser to produce a non-empty node of the correct category in the correct location to serve as an antecedent for the empty node. Table 4 provides these measures for the same two corpora described earlier.
In an attempt to devise an evaluation measure for empty node co-indexation that depends less on syntactic structure we experimented with a modified augmented empty node representation in which each antecedent is represented by its head's category and location. (The intuition behind this is that we do not want to penalize the empty node antecedentfinding algorithm if the parser misattaches modifiers to the antecedent). In fact this head-based antecedent representation yields scores very similiar to those obtained using the phrase-based representation. It seems that in the cases where the parser does not construct a phrase in the appropriate location to serve as the antecedent for an empty node, the syntactic structure is typically so distorted that either the pattern-matcher fails or the head-finding algorithm does not return the "correct" head either.

Section 23
Parser output POS Label  Table 3: Evaluation of the empty node restoration procedure ignoring antecedents. Individual results are reported for all types of empty node that occured more than 100 times in the "gold standard" corpus (section 23 of the Penn Treebank); these are ordered by frequency of occurence in the gold standard. Section 23 is a test corpus consisting of a version of section 23 from which all empty nodes and indices were removed. The parser output was produced by Charniak's parser (Charniak, 2000).  Table 4: Evaluation of the empty node restoration procedure including antecedent indexing, using the measure explained in the text. Other details are the same as in Table 4.

Empty node
This paper described a simple pattern-matching algorithm for restoring empty nodes in parse trees that do not contain them, and appropriately indexing these nodes with their antecedents. The patternmatching algorithm combines both simplicity and reasonable performance over the frequently occuring types of empty nodes. Performance drops considerably when using trees produced by the parser, even though this parser's precision and recall is around 0.9. Presumably this is because the pattern matching technique requires that the parser correctly identify large tree fragments that encode long-range dependencies not captured by the parser. If the parser makes a single parsing error anywhere in the tree fragment matched by a pattern, the pattern will no longer match. This is not unlikely since the statistical model used by the parser does not model these larger tree fragments. It suggests that one might improve performance by integrating parsing, empty node recovery and antecedent finding in a single system, in which case the current algorithm might serve as a useful baseline. Alternatively, one might try to design a "sloppy" pattern matching algorithm which in effect recognizes and corrects common parser errors in these constructions. Also, it is undoubtedly possible to build programs that can do better than this algorithm on special cases. For example, we constructed a Boosting classifier which does recover *U* and empty complementizers 0 more accurately than the pattern-matcher described here (although the pattern-matching algorithm does quite well on these constructions), but this classifier's performance averaged over all empty node types was approximately the same as the pattern-matching algorithm.
As a comparison of tables 3 and 4 shows, the pattern-matching algorithm's biggest weakness is its inability to correctly distinguish co-indexed NP * (i.e., NP PRO) from free (i.e., unindexed) NP *. This seems to be a hard problem, and lexical information (especially the class of the governing verb) seems relevant. We experimented with specialized classifiers for determining if an NP * is co-indexed, but they did not perform much better than the algorithm presented here. (Also, while we did not sys-tematically investigate this, there seems to be a number of errors in the annotation of free vs. co-indexed NP * in the treebank).
There are modications and variations on this algorithm that are worth exploring in future work. We experimented with lexicalizing patterns, but the simple method we tried did not improve results. Inspired by results suggesting that the patternmatching algorithm suffers from over-learning (e.g., testing on the training corpus), we experimented with more abstract "skeletal" patterns, which improved performance on some types of empty nodes but hurt performance on others, leaving overall performance approximately unchanged. Possibly there is a way to use both skeletal and the original kind of patterns in a single system.