Learning to recognize features of valid textual entailments

This paper advocates a new architecture for textual inference in which finding a good alignment is separated from evaluating entailment. Current approaches to semantic inference in question answering and textual entailment have approximated the entailment problem as that of computing the best alignment of the hypothesis to the text, using a locally decomposable matching score. We argue that there are significant weaknesses in this approach, including flawed assumptions of monotonicity and locality. Instead we propose a pipelined approach where alignment is followed by a classification step, in which we extract features representing high-level characteristics of the entailment problem, and pass the resulting feature vector to a statistical classifier trained on development data. We report results on data from the 2005 Pascal RTE Challenge which surpass previously reported results for alignment-based systems.

Introduction
During the last five years there has been a surge in work which aims to provide robust textual inference in arbitrary domains about which the system has no expertise. The best-known such work has occurred within the field of question answering (Pasca and Harabagiu, 2001;Moldovan et al., 2003); more recently, such work has continued with greater focus in addressing the PASCAL Recognizing Textual Entailment (RTE) Challenge (Dagan et al., 2005) and within the U.S. Government AQUAINT program. Substantive progress on this task is key to many text and natural language applications. If one could tell that Protestors chanted slogans opposing a free trade agreement was a match for people demonstrating against free trade, then one could offer a form of semantic search not available with current keywordbased search. Even greater benefits would flow to richer and more semantically complex NLP tasks.
Because full, accurate, open-domain natural language understanding lies far beyond current capabilities, nearly all efforts in this area have sought to extract the maximum mileage from quite limited semantic representations. Some have used simple measures of semantic overlap, but the more interesting work has largely converged on a graphalignment approach, operating on semantic graphs derived from syntactic dependency parses, and using a locally-decomposable alignment score as a proxy for strength of entailment. (Below, we argue that even approaches relying on weighted abduction may be seen in this light.) In this paper, we highlight the fundamental semantic limitations of this type of approach, and advocate a multi-stage architecture that addresses these limitations. The three key limitations are an assumption of monotonicity, an assumption of locality, and a confounding of alignment and evaluation of entailment.
We focus on the PASCAL RTE data, examples from which are shown in table 1. This data set contains pairs consisting of a short text followed by a one-sentence hypothesis. The goal is to say whether the hypothesis follows from the text and general background knowledge, according to the intuitions of an intelligent human reader. That is, the standard is not whether the hypothesis is logically entailed, but whether it can reasonably be inferred.

Approaching a robust semantics
In this section we try to give a unifying overview to current work on robust textual inference, to present fundamental limitations of current methods, and then to outline our approach to resolving them. Nearly all current textual inference systems use a single-stage matching/proof process, and differ mainly in the sophistication of the matching stage. The simplest approach is to base the entailment prediction on the degree of semantic overlap between the text and hypothesis using models based on bags of words, bags of n-grams, TF-IDF scores, or something similar (Jijkoun and de Rijke, 2005). Such models have serious limitations: semantic overlap is typically a symmetric relation, whereas entailment is clearly not, and, because overlap models do not account for syntactic or semantic structure, they are easily fooled by examples like ID 2081.
A more structured approach is to formulate the entailment prediction as a graph matching problem (Haghighi et al., 2005;de Salvo Braz et al., 2005). In this formulation, sentences are represented as normalized syntactic dependency graphs (like the one shown in figure 1) and entailment is approximated with an alignment between the graph representing the hypothesis and a portion of the corresponding graph(s) representing the text. Each possible alignment of the graphs has an associated score, and the score of the best alignment is used as an approximation to the strength of the entailment: a betteraligned hypothesis is assumed to be more likely to be entailed. To enable incremental search, alignment scores are usually factored as a combination of local terms, corresponding to the nodes and edges of the two graphs. Unfortunately, even with factored scores the problem of finding the best alignment of two graphs is NP-complete, so exact computation is intractable. Authors have proposed a variety of approximate search techniques. Haghighi et al. (2005) divide the search into two steps: in the first step they consider node scores only, which relaxes the problem to a weighted bipartite graph matching that can be solved in polynomial time, and in the second step they add the edges scores and hillclimb the alignment via an approximate local search.
A third approach, exemplified by Moldovan et al. (2003) and Raina et al. (2005), is to translate dependency parses into neo-Davidsonian-style quasilogical forms, and to perform weighted abductive theorem proving in the tradition of (Hobbs et al., 1988). Unless supplemented with a knowledge base, this approach is actually isomorphic to the graph matching approach. For example, the graph in figure 1 might generate the quasi-LF rose(e1), nsubj(e1, x1), sales(x1), nn(x1, x2), Mitsubishi(x2),dobj(e1,x3),percent(x3),num(x3,x4),46(x4). There is a term corresponding to each node and arc, and the resolution steps at the core of weighted abduction theorem proving consider matching an individual node of the hypothesis (e.g. rose(e1)) with something from the text (e.g. fell(e1)), just as in the graph-matching approach. The two models become distinct when there is a good supply of additional linguistic and world knowledge axioms-as in Moldovan et al. (2003) but not Raina et al. (2005). Then the theorem prover may generate intermediate forms in the proof, but, nevertheless, individual terms are resolved locally without reference to global context.
Finally, a few efforts (Akhmatova, 2005;Fowler et al., 2005;Bos and Markert, 2005) have tried to translate sentences into formulas of first-order logic, in order to test logical entailment with a theorem prover. While in principle this approach does not suffer from the limitations we describe below, in practice it has not borne much fruit. Because few problem sentences can be accurately translated to logical form, and because logical entailment is a strict standard, recall tends to be poor.
The simple graph matching formulation of the problem belies three important issues. First, the above systems assume a form of upward monotonicity: if a good match is found with a part of the text, other material in the text is assumed not to affect the validity of the match. But many situations lack this upward monotone character. Consider variants on ID 98. Suppose the hypothesis were Arafat targeted for assassination. This would allow a perfect graph match or zero-cost weighted abductive proof, because the hypothesis is a subgraph of the text. However, this would be incorrect because it ignores the modal operator could. Information that changes the validity of a proof can also exist outside a matching clause. Consider the alternate text Sharon denies Arafat is targeted for assassination. 1 The second issue is the assumption of locality. Locality is needed to allow practical search, but many entailment decisions rely on global features of the alignment, and thus do not naturally factor by nodes and edges. To take just one example, dropping a restrictive modifier preserves entailment in a positive context, but not in a negative one. For example, Dogs barked loudly entails Dogs barked, but No dogs barked loudly does not entail No dogs barked. These more global phenomena cannot be modeled with a factored alignment score.
The last issue arising in the graph matching approaches is the inherent confounding of alignment and entailment determination. The way to show that one graph element does not follow from another is to make the cost of aligning them high. However, since we are embedded in a search for the lowest cost alignment, this will just cause the system to choose an alternate alignment rather than recognizing a non-entailment. In ID 152, we would like the hypothesis to align with the first part of the text, to be able to prove that civilians are not members of law enforcement agencies and conclude that the hypothesis does not follow from the text. But a graphmatching system will to try to get non-entailment by making the matching cost between civilians and members of law enforcement agencies be very high. However, the likely result of that is that the final part of the hypothesis will align with were civilians at the end of the text, assuming that we allow an alignment with "loose" arc correspondence. 2 Under this candidate alignment, the lexical alignments are perfect, and the only imperfect alignment is the subject arc of were is mismatched in the two. A robust inference guesser will still likely conclude that there is entailment.
We propose that all three problems can be resolved in a two-stage architecture, where the alignment phase is followed by a separate phase of entailment determination. Although developed independently, the same division between alignment and classification has also been proposed by Marsi and Krahmer (2005), whose textual system is developed and evaluated on parallel translations into Dutch. Their classification phase features an output space of five semantic relations, and performs well at distinguishing entailing sentence pairs.
Finding aligned content can be done by any search procedure. Compared to previous work, we emphasize structural alignment, and seek to ignore issues like polarity and quantity, which can be left to a subsequent entailment decision. For example, the scoring function is designed to encourage antonym matches, and ignore the negation of verb predicates. The ideas clearly generalize to evaluating several alignments, but we have so far worked with just the one-best alignment. Given a good alignment, the determination of entailment reduces to a simple classification decision. The classifier is built over features designed to recognize patterns of valid and invalid inference. Weights for the features can be hand-set or chosen to minimize a relevant loss function on training data using standard techniques from machine learning. Because we already have a complete alignment, the classifier's decision can be con-ditioned on arbitrary global features of the aligned graphs, and it can detect failures of monotonicity.

System
Our system has three stages: linguistic analysis, alignment, and entailment determination.

Linguistic analysis
Our goal in this stage is to compute linguistic representations of the text and hypothesis that contain as much information as possible about their semantic content. We use typed dependency graphs, which contain a node for each word and labeled edges representing the grammatical relations between words. Figure 1 gives the typed dependency graph for ID 971. This representation contains much of the information about words and relations between them, and is relatively easy to compute from a syntactic parse. However many semantic phenomena are not represented properly; particularly egregious is the inability to represent quantification and modality.
We parse input sentences to phrase structure trees using the Stanford parser (Klein and Manning, 2003), a statistical syntactic parser trained on the Penn TreeBank. To ensure correct parsing, we preprocess the sentences to collapse named entities into new dedicated tokens. Named entities are identified by a CRF-based NER system, similar to that described in (McCallum and Li, 2003). After parsing, contiguous collocations which appear in Word-Net (Fellbaum, 1998) are identified and grouped.
We convert the phrase structure trees to typed dependency graphs using a set of deterministic handcoded rules (de Marneffe et al., 2006). In these rules, heads of constituents are first identified using a modified version of the Collins head rules that favor semantic heads (such as lexical verbs rather than auxiliaries), and dependents of heads are typed using tregex patterns (Levy and Andrew, 2006), an extension of the tgrep pattern language. The nodes in the final graph are then annotated with their associated word, part-of-speech (given by the parser), lemma (given by a finite-state transducer described by Minnen et al. (2001)) and named-entity tag.

Alignment
The purpose of the second phase is to find a good partial alignment between the typed dependency graphs representing the hypothesis and the text. An alignment consists of a mapping from each node (word) in the hypothesis graph to a single node in the text graph, or to null. 3 Figure 1 gives the alignment for ID 971.
The space of alignments is large: there are O((m + 1) n ) possible alignments for a hypothesis graph with n nodes and a text graph with m nodes. We define a measure of alignment quality, and a procedure for identifying high scoring alignments. We choose a locally decomposable scoring function, such that the score of an alignment is the sum of the local node and edge alignment scores. Unfortunately, there is no polynomial time algorithm for finding the exact best alignment. Instead we use an incremental beam search, combined with a node ordering heuristic, to do approximate global search in the space of possible alignments. We have experimented with several alternative search techniques, and found that the solution quality is not very sensitive to the specific search procedure used.
Our scoring measure is designed to favor alignments which align semantically similar subgraphs, irrespective of polarity. For this reason, nodes receive high alignment scores when the words they represent are semantically similar. Synonyms and antonyms receive the highest score, and unrelated words receive the lowest. Our hand-crafted scoring metric takes into account the word, the lemma, and the part of speech, and searches for word relatedness using a range of external resources, including WordNet, precomputed latent semantic analysis matrices, and special-purpose gazettes. Alignment scores also incorporate local edge scores, which are based on the shape of the paths between nodes in the text graph which correspond to adjacent nodes in the hypothesis graph. Preserved edges receive the highest score, and longer paths receive lower scores.

Entailment determination
In the final stage of processing, we make a decision about whether or not the hypothesis is entailed by the text, conditioned on the typed dependency graphs, as well as the best alignment between them.  Because we have a data set of examples that are labeled for entailment, we can use techniques from supervised machine learning to learn a classifier. We adopt the standard approach of defining a featural representation of the problem and then learning a linear decision boundary in the feature space. We focus here on the learning methodology; the next section covers the definition of the set of features. Defined in this way, one can apply any statistical learning algorithm to this classification task, such as support vector machines, logistic regression, or naive Bayes. We used a logistic regression classifier with a Gaussian prior parameter for regularization. We also compare our learning results with those achieved by hand-setting the weight parameters for the classifier, effectively incorporating strong prior (human) knowledge into the choice of weights.
An advantage to the use of statistical classifiers is that they can be configured to output a probability distribution over possible answers rather than just the most likely answer. This allows us to get confidence estimates for computing a confidence weighted score (see section 5). A major concern in applying machine learning techniques to this classification problem is the relatively small size of the training set, which can lead to overfitting problems. We address this by keeping the feature dimensionality small, and using high regularization penalties in training.

Feature representation
In the entailment determination phase, the entailment problem is reduced to a representation as a vector of 28 features, over which the statistical classifier described above operates. These features try to capture salient patterns of entailment and non-entailment, with particular attention to contexts which reverse or block monotonicity, such as negations and quantifiers. This section describes the most important groups of features.
Polarity features. These features capture the presence (or absence) of linguistic markers of negative polarity contexts in both the text and the hypothesis, such as simple negation (not), downward-monotone quantifiers (no, few), restricting prepositions (without, except) and superlatives (tallest).
Adjunct features. These indicate the dropping or adding of syntactic adjuncts when moving from the text to the hypothesis. For the common case of restrictive adjuncts, dropping an adjunct preserves truth (Dogs barked loudly |= Dogs barked), while adding an adjunct does not (Dogs barked |= Dogs barked today). However, in negative-polarity contexts (such as No dogs barked), this heuristic is reversed: adjuncts can safely be added, but not dropped. For example, in ID 59, the hypothesis aligns well with the text, but the addition of in Iraq indicates non-entailment.
We identify the "root nodes" of the problem: the root node of the hypothesis graph and the corresponding aligned node in the text graph. Using dependency information, we identify whether adjuncts have been added or dropped. We then determine the polarity (negative context, positive context or restrictor of a universal quantifier) of the two root nodes to generate features accordingly.
Antonymy features. Entailment problems might involve antonymy, as in ID 971. We check whether an aligned pairs of text/hypothesis words appear to be antonymous by consulting a pre-computed list of about 40,000 antonymous and other contrasting pairs derived from WordNet. For each antonymous pair, we generate one of three boolean features, indicating whether (i) the words appear in contexts of matching polarity, (ii) only the text word appears in a negative-polarity context, or (iii) only the hypothesis word does.
Modality features. Modality features capture simple patterns of modal reasoning, as in ID 98, which illustrates the heuristic that possibility does not entail actuality. According to the occurrence (or not) of predefined modality markers, such as must or maybe, we map the text and the hypothesis to one of six modalities: possible, not possible, actual, not actual, necessary, and not necessary. The text/hypothesis modality pair is then mapped into one of the following entailment judgments: yes, weak yes, don't know, weak no, or no. For example: (not possible |= not actual)? ⇒ yes (possible |= necessary)? ⇒ weak no Factivity features. The context in which a verb phrase is embedded may carry semantic presuppositions giving rise to (non-)entailments such as The gangster tried to escape |= The gangster escaped. This pattern of entailment, like others, can be reversed by negative polarity markers (The gangster managed to escape |= The gangster escaped while The gangster didn't manage to escape |= The gangster escaped). To capture these phenomena, we compiled small lists of "factive" and non-factive verbs, clustered according to the kinds of entailments they create. We then determine to which class the parent of the text aligned with the hypothesis root belongs to. If the parent is not in the list, we only check whether the embedding text is an affirmative context or a negative one.
Quantifier features. These features are designed to capture entailment relations among simple sentences involving quantification, such as Every company must report |= A company must report (or The company, or IBM). No attempt is made to handle multiple quantifiers or scope ambiguities. Each quantifier found in an aligned pair of text/hypothesis words is mapped into one of five quantifier categories: no, some, many, most, and all. The no category is set apart, while an ordering over the other four categories is defined. The some category also includes definite and indefinite determiners and small cardinal numbers. A crude attempt is made to handle negation by interchanging no and all in the presence of negation. Features are generated given the categories of both hypothesis and text. Number, date, and time features. These are designed to recognize (mis-)matches between numbers, dates, and times, as in IDs 1806 and 231. We do some normalization (e.g. of date representations) and have a limited ability to do fuzzy matching. In ID 1806, the mismatched years are correctly identified. Unfortunately, in ID 231 the significance of over is not grasped and a mismatch is reported. Alignment features. Our feature representation includes three real-valued features intended to represent the quality of the alignment: score is the raw score returned from the alignment phase, while goodscore and badscore try to capture whether the alignment score is "good" or "bad" by computing the sigmoid function of the distance between the alignment score and hard-coded "good" and "bad" reference values.

Evaluation
We present results based on the First PASCAL RTE Challenge, which used a development set containing 567 pairs and a test set containing 800 pairs. The data sets are balanced to contain equal numbers of yes and no answers. The RTE Challenge recommended two evaluation metrics: raw accuracy and confidence weighted score (CWS). The CWS is computed as follows: for each positive integer k up to the size of the test set, we compute accuracy over the k most confident predictions. The CWS is then the average, over k, of these partial accuracies. Like raw accuracy, it lies in the interval [0, 1], but it will exceed raw accuracy to the degree that predictions are well-calibrated.
Several characteristics of the RTE problems should be emphasized. Examples are derived from a broad variety of sources, including newswire; therefore systems must be domain-independent. The inferences required are, from a human perspective, fairly superficial: no long chains of reasoning are involved. However, there are "trick" questions expressly designed to foil simplistic techniques. The definition of entailment is informal and approximate: whether a competent speaker with basic knowledge of the world would typically infer the hypothesis from the text. Entailments will certainly depend on linguistic knowledge, and may also depend on world knowledge; however, the scope of required  world knowledge is left unspecified. 4 Despite the informality of the problem definition, human judges exhibit very good agreement on the RTE task, with agreement rate of 91-96% (Dagan et al., 2005). In principle, then, the upper bound for machine performance is quite high. In practice, however, the RTE task is exceedingly difficult for computers. Participants in the first PASCAL RTE workshop reported accuracy from 49% to 59%, and CWS from 50.0% to 69.0% (Dagan et al., 2005). Table 2 shows results for a range of systems and testing conditions. We report accuracy and CWS on each RTE data set. The baseline for all experiments is random guessing, which always attains 50% accuracy. We show comparable results from recent systems based on lexical similarity (Jijkoun and de Rijke, 2005), graph alignment (Haghighi et al., 2005), weighted abduction (Raina et al., 2005), and a mixed system including theorem proving (Bos and Markert, 2005).
We then show results for our system under several different training regimes. The row labeled "alignment only" describes experiments in which all features except the alignment score are turned off. We predict entailment just in case the alignment score exceeds a threshold which is optimized on development data. "Hand-tuning" describes experiments in which all features are on, but no training occurs; rather, weights are set by hand, according to human intuition. Finally, "learning" describes experiments in which all features are on, and feature weights are trained on the development data. The 4 Each RTE problem is also tagged as belonging to one of seven tasks. Previous work (Raina et al., 2005) has shown that conditioning on task can significantly improve accuracy. In this work, however, we ignore the task variable, and none of the results shown in table 2 reflect optimization by task.
figures reported for development data performance therefore reflect overfitting; while such results are not a fair measure of overall performance, they can help us assess the adequacy of our feature set: if our features have failed to capture relevant aspects of the problem, we should expect poor performance even when overfitting. It is therefore encouraging to see CWS above 70%. Finally, the figures reported for test data performance are the fairest basis for comparison. These are significantly better than our results for alignment only (Fisher's exact test, p < 0.05), indicating that we gain real value from our features. However, the gain over comparable results from other teams is not significant at the p < 0.05 level.
A curious observation is that the results for handtuned weights are as good or better than results for learned weights. A possible explanation runs as follows. Most of the features represent high-level patterns which arise only occasionally. Because the training data contains only a few hundred examples, many features are active in just a handful of instances; their learned weights are therefore quite noisy. Indeed, a feature which is expected to favor entailment may even wind up with a negative weight: the modal feature weak yes is an example. As shown in table 3, the learned weight for this feature was strongly negative -but this resulted from a single training example in which the feature was active but the hypothesis was not entailed. In such cases, we shouldn't expect good generalization to test data, and human intuition about the "value" of specific features may be more reliable. Table 3 shows the values learned for selected feature weights. As expected, the features added adjunct in all context, modal yes, and text is factive were all found to be strong indicators of entailment, while date insert, date modifier insert, widening from text to hyp all indicate lack of entailment. Interestingly, text has neg marker and text & hyp diff polarity were also found to disfavor entailment; while this outcome is sensible, it was not anticipated or designed.

Conclusion
The best current approaches to the problem of textual inference work by aligning semantic graphs,  using a locally-decomposable alignment score as a proxy for strength of entailment. We have argued that such models suffer from three crucial limitations: an assumption of monotonicity, an assumption of locality, and a confounding of alignment and entailment determination. We have described a system which extends alignment-based systems while attempting to address these limitations. After finding the best alignment between text and hypothesis, we extract highlevel semantic features of the entailment problem, and input these features to a statistical classifier to make an entailment decision. Using this multi-stage architecture, we report results on the PASCAL RTE data which surpass previously-reported results for alignment-based systems.
We see the present work as a first step in a promising direction. Much work remains in improving the entailment features, many of which may be seen as rough approximations to a formal monotonicity calculus. In future, we aim to combine more precise modeling of monotonicity effects with better modeling of paraphrase equivalence.


A Multimodal Result Ontology for Integrated Semantic Web Dialogue Applications

General purpose ontologies and domain ontologies make up the infrastructure of the Semantic Web, which allow for accurate data representations with relations, and data inferences. In our approach to multimodal dialogue systems providing question answering functionality (SMARTWEB), the ontological infrastructure is essential. We aim at an integrated approach in which all knowledge-aware system modules are based on interoperating ontologiesin a common data model. The discourse ontology is meant to provide the necessary dialogue- and HCI concepts. We present the ontological syntactic structure of multimodal question answering results as partof this discourse ontology which extends the W3C EMMA annotation framework and uses MPEG-7 annotations. In addition, we describe anextension to ontological result structures where automatic and context-based sorting mechanisms can be naturally incorporated.

Introduction
Integrating ontologies means to allow for transformations between generated ontologies and the already existing ones as Semantic Web artefacts available at the start of a Semantic Web project. General ontologies such as SUMO (Niles and Pease, 2001) and DOLCE (Gangemi et al., 2002) exist to be used and exploited as general purpose conceptual terminologies. The use of different ontologies in a unique application assumes the presence of a upper model ontology defining baseconcepts and relations to be inherited from the subordinate domain ontologies, providing suitability for fast reasoning and consistent representation. For SMARTWEB 1 SUMO and DOLCE have been merged. The SMARTWEB foundational ontology (Cimiano et al., 2004) brings together the conceptual clarity of DOLCE, due to the Ontoclean (Guarino and Welty, 2004) methodology used to model it, and the accessibility of SUMO. Connecting and merging different data-and knowledge sources representing knowledge of special domains like football or chemistry is a difficult task, even if such upper level ontology models exist. Although difficult to establish, an integrated data approach is the key for functionalities such as query decomposition, ontological inference, and at least trust and transparency in the results obtained. Therefore, all knowledge-intensive sub-modules of a Semantic Web application should themselves be represented by an ontological infrastructure, e.g. RDF-based data exchange 2 (Randal, 1998) which we used finally. With the help of our discourse ontology (DISCONTO) the 1 SMARTWEB (Wahlster, 2004; aims at developing a context-aware, mobile and multimodal interface to the Semantic Web. In the main scenario, the user carries a smartphone and is able to pose multimodal open-domain questions using speech, pen, and gesture among other input modalities. The user input is transmitted via UMTS or WLAN to a backend server, where the multimodal recogniser, the Semantic Web access subsystems and the dialogue manager for result generation resist. 2 http://www.w3.org/TR/rdf-primer/ pertinent concepts and relations for content-based fusion of input modalities, semantic-based interpretation of user input (query template filling) for ontology-based similarity search, and multimodal output filtering, aggregation, and generation can be modelled concurrently. What follows in section 2. is a brief introduction of the SMARTWEB ontological framework, focusing on a specific branch of the discourse ontology, the concepts for representing multimedia results syntactically, with contentbased semantic annotations. In the question answering (QA) scenario as metaphorical basis of the user-system interaction, the presentation of multimodal results is very important, which is reflected in the detailed ontologicial description for this data types. Nonetheless the integration of dialogue-and QA-based concepts into the upper model ontology is a difficult task, since the conceptual clarity of the upper model must not become blurred. In addition, specific domain-and task-oriented ontologies like ontologies for dialogue and discourse processing must not present a narrow-sighted view on the relevant concepts and relations.
In the remainder of this text, we present our approach to integrate question answering and multimodal dialogue concepts into the ontological frame, focusing on concept for result presentation. Group (list) results and sorting criteria for QA results are presented in detail.

Ontological Framework
SMARTWEB joins together multimodal and mobile user interface technology with question answering technology. The dialogue functionality of Smartweb can basically be summarised as a question answer game; the user can ask constituent interrogative questions and refer to objects previously mentioned in the dialogue. Most prominent are single instance questions of semantic classes such as persons, locations, and dates. The application we describe is a dialogue system, where the user can ask questions about a specific domain (football) as well as open domain questions. In addition, the input and output is multimodal, which on the one hand increases naturalness in query formulation, but on the other hand restricts the usability of a textual question answering system. Example questions for single instance constituents are the following: • Who was world champion in 1990?
• Show me the goal of Alexandersson.
• Show me the world cup mascot 2006.
• Where is Brandenburg Gate located?
• What is the capital of Germany?
• When does the next football match take place?
Example questions for enumeration of constituents are the following: • Show me the World Cup mascot.
• When was Italy world champion?
• Who was world champion for more than three times?
• Which games had more than 100000 spectators?
• Which games took place in Stuttgart?
• Who scored in the final match Germany vs. Brasil?
To reach the goal to correctly answer the questions we combine different kinds of domain ontologies into an integrated and modular knowledge base. For this purpose we defined an upper model ontology based on SUMO and DOLCE and integrated each domain ontology in it. This way we could guarantee interoperability and modelling consistency between the different ontologies. A domain-ontology is the primary knowledge server for answering question. This offers great opportunity for more specific questions in a dialogical interaction, on the other hand the difficulties in speech recognition, language understanding and information coverage uncover the demand for open-domain QA functionality (Neumann and Sacaleanu, 2005) obvious, which does not necessarily require complex syntactic/semantic question parsing, and may use answer redundancy as a surrogate for semantic understanding of questions (Lin, 2002). However, for particular question types, i.e. enumeration questions, ontology-based systems outperform standard open-domain QA system for the following two reasons: (1) Redundancy information 3 often does not help very much for list questions, (2) ontological representation of multimodal list result allow for deeper structuring, filtering, and sorting. We present a multimodal ontological result structure where automatic and context-based sorting mechanism can be naturally incorporated.

The Upper Model Ontology
Over the DISCONTO we link concepts of the domain specific ontologies to a media representation ontology SMARTMEDIA that provides concepts for multimodal presentation. The SMARTWEB upper model ontology basically proposes the upper-level concepts of DOLCE with the distinction between endurant, perdurant, abstract and qualities, and the adoption of several concepts from SUMO adding rich taxonomies which feature specific concepts such as Hotel or Organization which we use as semantic answer types. The upper model (SmartSUMO) was modelled in three steps: • Define relevant concepts from the DOLCE ontology (SmartDOLCE).
• Define relevant concepts from the SUMO ontology.
The SmartDOLCE ontology includes a relevant module (sub-ontology) of DOLCE called Descriptions & Situations (D&S) (Gangemi and Mika, 2003) to standardise a variety of reified contexts and states of affairs. We use this module for representing contexts for sorting criteria on group results (section 2.6.).

The Discourse Ontology
The DISCONTO discourse ontology is meant to provide concepts for dialogical interaction with the user (HCI) and the interaction with the Semantic Web access sub-systems, which are based on the ontological infrastructure. We identified the following top-level constructs of the DISCONTO ontology: (1) dialogue acts, (2) dialogue memory, dialogue model, (3) lexical rules for syntactic/semantic mapping, and (4) concepts for multimodal results to be presented to the user which incorporate concepts for question answering as a sub-category. User interaction is modelled in a generic way in the discourse ontology. As opposed to other contributes like in (Pfleger et al., 2003) where a three layer model (linguistic, discourse and dialog layer) is used, or (Niekrasz and Purver, 2005), a semiotic approach to discourse, in our approach we concentrate on discourse interactions within a question answering scenario. The DISCONTO (Smartweb Discourse Ontology) divides dialogue acts in Queries and Results concepts. Specific discourse phenomena like ellipsis or anaphora are resolved in a dedicated multimodal fusion and discourse processing module (Pfleger, 2005).

Concepts for Multimedia Results
The discourse ontology branch describing the multimodal interaction is based on the W3C EMMA standard 4 . EMMA was primarily designed to code interpretations of multimodal input devices such as the output of a speech recogniser. We extended the EMMA language to meet the requirements of representing special multimodal answer types in the context of the ontological infrastructure. What we present here, is the ontological representation of multimodal result objects which serve as the answers obtained from the Semantic Web information retrieval step. We provide a new namespace swemma for our extensions to the emma:container and emma:interpretation classes. One of these extensions is the swemma:Result class, extended by disconto:GroupResult, and disconto:IncrementalResult. Figure 1 shows the ontological structure. 5 We focus on the answerTypes slot of the Result base class. Answer types are multimodal, hierarchical dialogue concepts of the results to be presented to the user. To ensure full coverage of all forms of multiple answers, and to be able to factor in deviations and special requirements, a typology is being developed. More general answer types should be overwritten by more specific ones, if possible.
(See e.g. (Eduard Hovy and Ravichandran, 2001) for similar approaches for a uni-modal textual context. This taxonomy consists of mainly semantic answer types 6 . The result structure as a whole combines semantic answer types with a syntactic result structure by the GroupResult concept. We exemplify the modelling of results by discussing an actual result instance.

An MPEG-7 Ontology
We represent output results with a MPEG-7-based media annotation ontology named SMARTMEDIA. MPEG-7 7 is conceived for describing multimedia content data. Primarily the concepts mpeg7:MediaFormat for file format and the coding parameters, mpeg7:MediaProfile for coding schemes like resolution, compression, and mpeg7:SegmentDecomposition for decompositions of the audio, visual, textual segments in space, time, and frequency are imported into SMARTMEDIA following the approach in (Hunter, 2001) restricting the number of the modelled concepts to those that fit well to the project. Concept instances (ContentAnswer) of the SMART-MEDIA ontology are linked to the result instances by the discourse:answerTypes slot in the representation of results as shown in figure 2. The important thing to notice is that all answer types refer to media types as multimodal SMARTMEDIA concepts imported into our upper layer ontology with namespaces smartmedia and mpeg7. In this way we bridge the discourse ontology with the extended SUMO ontology to arrive at a common data model.

SmartWeb Integrated Ontology (SWINTO)
The concepts of the DISCONTO have been aligned to the SMARTWEB integrated ontology (SWINTO). The EMMA derived concepts inherit from smartsumo:Software. Dialog acts have been mapped as intentional processes to smartsumo:Communication. The discourse:Query concept relates to the domain specific concepts over a discourse:content relation defining a partially instantiated instance used as search pattern for the semantic knowledge base (ontobroker) (Decker et al., 1999), and the discourse:focus relation expresses which part of the content represents the knowledge base instance or atomic value the user asks for. The SMARTMEDIA ontology is connected to the Smart-SUMO by a high level semantic concept called smart-7.htm

media:ContentAnnotation.
This concept directly relates to the top level concept smartdolce:entity and to the higher concept in the smartmedia taxonomy smartmedia:ContentOrSegment. Over this concept a medium instance (e.g. video, picture, text) is associated with domain specific concepts.

Defining and Declaring Sort Criteria for Group Results
In order to properly sort results for presentation purpose, we realised a context sensitive mechanism for determining parameters of an arbitrary sorting function. We observe by inspecting different list results, that correct sorting of results for presentations heavily depends on user expectations, similar to answer types. Those expectation can be partly deduced from context information. For example, if a user asks for "nearby cities where a football match takes place", he expects the cities to be ordered with respect to the distance from the place he is situated. We adopted the approach of ontological patterns for modelling schematic knowledge of the pragmatics of spatial navigation. as described in (Loos and Porzel, 2005). In our approach we use ontological pattern to generate a description for an ordering function in a situative context. The description of SortResults would sequences a SortGroupResults use roles -such as discourse:SortCriterion played by smartsumo:City and a parameter such as smartsumo:Nation, which follow the con-straints in D&S, for which roles are played by endurants, parameterized by regions.

Declaring a Sort Function
We presented a multimodal ontological result structure where automatic and context-based sorting mechanism can be naturally incorporated. In this section we focus on the sorting aspect. Expressive power of logic-based ontology languages can be measures using a so-called bisimulation (Blackburn et al., 2001). The expressive power of the RDF-based ontological representation is quite low, on the other hand allows for decidable and fast inferences in the knowledge base (ONTOBROKER) (Decker et al., 1999) as well as for similar representations among different components, such as a dialogue system and the backend server  . On interesting research question is how to boost expressiveness of ontological languages by adding additional operators and relations in addition to subsumptions. Unfortunately, description languages do not offer the necessary expressiveness for arbitrary (semantic) sorting criteria we would like to use. Driven by pragmatic issues, and algorithmic concerns, we do not attempt to extend the expressive power of the ontology for Group Results. Instead, we use the JENA-Java framework (McBride, 2001) to implement arbitrary sorting functions on instance lists. Since the JENA-Java framework uses the same terminological box (T-Box) and assertion box (A-Box) as the reasoning mechanism of the ontology, a type-save but rather independent bridge to object-oriented programming can be established. The sorting functions can thus be implemented in an arbitrary fashion, and can be executed on deeper structured ontological group result instances. Hence al relevant phenomena and contextual factors that have to be taken into account for sorting QA results for presentation can be taken into account without the need for a direct representation within the ontological framework.

Conclusion
In project SMARTWEB, the ontology serves as a basis for defining the semantics and the content of information exchanged between various system modules so that modules only receive messages whose content is congruent to the terminological and structural distinctions of the ontology. This serves as communication interfaces between NLP components. The natural extension is an ontological framework towards QA result design. Our multimodal result structure extends the W3C EMMA annotation framework (for syntactic) and uses MPEG7 annotations (for semantic) ontological QA result representations. We made the domain assumptions more explicit and operational by linking the Sorting Criteria ontology concepts towards a JENA-Java framework to write and execute arbitrary (semantic) sorting functions.

Acknowledgements
We would like to thank our partners in SmartWeb. This research was funded by the German Federal Ministry for


TermProfile.com - Supporting a Conference Interpreter’s Workflow

Termprofile.com is a tool that helps you to search for terms on the Internet, distinguishing between the countries of origin of the hits, presenting relative frequency and comparative numbers for alternative terms in one language or different languages at a glance, TermProfile is one of the instruments that can significantly enhance interpreters' (and of course translators') workflow. TermProfile shows whether terms or expressions in a certain language are used in the respective countries. It offers an interface to perform three queries in parallel and then displays the search result figures on one screen. For each query it is possible to enter a second term ("control term") in order to obtain a relative frequency of a term. TermProfile offers a web-statistics profile of terms and expressions with dimensions and relations that far exceed a simple Google search.

THE SITUATION
The Internet is becoming increasingly popular as an instrument for checking the commonness of terms. Translators, interpreters, journalists, technical editors, terminologists and authors all check the frequency of use of terms by entering them in search engines such as Google.
The Internet is a huge text corpus of all languages, countries, topics, population groups -free-ofcharge and in real time. An opportunity. Search engines generally provide hits of all possible origins; there is no linguistic (and certainly not an editorial) check. A risk. This is because seemingly common terms can be based on faulty translations and thus be fairly common.

THE TERMPROFILE PRINCIPLE
TermProfile shows whether terms are also used in countries where the native languages are spoken. In addition, TermProfile provides an at-a-glance list of figures. In other words, a web-statistics profile of the checked expressions with comparative figures for alternative expressions or various countries of origin.
TermProfile presents statistic correlations and orders of magnitude about the use of expressions in countries and language areas, which are not visible with a simple entry in Google. Of course, you can analyse terms both in the narrower sense of "specialist terms", but also as general expressions, sayings, theoretically any possible character sequence.
Not least, TermProfile trains your sense of dimensions of the frequency of use of expressions by language, country and specialist subject.

THE TECHNICAL SIDE
TermProfile is based on an official interface to the data set of Google. Via a so-termed API, short for Application Programming Interface, TermProfile forwards complex queries to the Google database. A part of the information on the results is the statement on the country of origin of the respective web document. Accordingly, the search functions like those in Google also apply, e.g. the use of quotation marks for groups of words and Boolean operators like the automatic "AND" search, the use of "OR" for alternative terms, etc.
TermProfile is in its experimental phase. At this stage, Google enables 1,000 queries a day. Therefore, the availability of TermProfile is not guaranteed. Technical comments and suggestions are highly appreciated.

THE FUNCTION
You can limit the search of a term to certain countries (or in the case of EN and ES, country groups). By way of comparison, you can perform a search for this term in parallel in several countries/country groups and worldwide. The hits for the various country constellations are presented as ratios.

WHAT IT MEANS
-How frequently is a term used in one country in relation to other countries? -How frequent is a second or third term in comparison to this? One indicator for the correctness of the language used is the country of origin of the text, if we assume that there is a greater probability that a native speaker in the respective country has written the text.
If e.g. a term has disproportionately more hits worldwide than in the countries in which this language is spoken, it is less probable that this term is correct. If the term "muñón del eje" is found on only a few or no Spanish-speaking sites, but on a few (numerous) German sites, this indicates that it might be a translation of the German "Achsstummel" (axle end or axle journal) due to lack of a genuine equivalent in the target language, and that it is not a term coined in Spanish-speaking countries. In this case, further investigation is advisable. If an English collocation in relation to the total hits is rarely found in US, UK, AU, CN, it is less probable that this term is correct. Regionalisms (e.g. all Spanishspeaking countries v Spain; US v UK) can also be recognised in this way.
The number of hits for the respective countries in relation to the number of worldwide hits are displayed in the second results column in order to illustrate the specific ratio. The ratio of hits of "muñón del eje" in Germany to hits worldwide is 1:13; in Spanish-speaking countries 1:11 (thus for one hit in Spanish-speaking countries, there are 11 on the whole Internet). The ratio should actually be more in favour of Spanish-speaking countries (thus the number on the right should be lower). If all hits on the whole Internet could be found in this pre-defined group of Spanish-speaking countries, the ratio would be 1:1.

THE FUNCTION
By way of comparison, you can perform a search for several terms in parallel (and then search for these respectively in the various country constellations). The hits for the various terms and countries are presented as ratios.

WHAT IT MEANS
A term may be frequently used in a certain country or a group of countries and still be wrong. That is why it always makes sense to consider whether there are any alternative terms/synonyms in this language which may be more common or more correct. Examples: a) The term "Mund-zu-Mund-Propaganda" appears to have a large number of hits -78,300; but if you perform a check you will see that "Mundpropaganda" -with 275,000 hits -is ten-times as common. b) The English equivalent of "Nutzungspopularität" is "user popularity" and not "usage popularity".

THE FUNCTION
For a term to be checked, you can enter a second control term, which is then searched for in the same selected country constellation. The results of both terms arc presented as ratios.

WHAT IT MEANS
-How frequently is a term used in relation to other words of the same/other language? In order to see the frequency of a term in relation to the overall text stock of the Internet, you can compare the number of hits to the number of hits of a very general, commonly used word such as "and". Absolute numbers of hits can sometimes be misleading: 500 hits in Germany may have a different status to hits in the USA.
The fact that the word Spaltrohrmotor (in connection with the word "Pumpe") is less frequent than the little word "and" goes without saying. But what is the exact ratio? In Germany, in terms of absolute measurements, the words "Spaltrohrmotor" and "Pumpe" (in one document) are used precisely 22times more frequently than in Austria; in relation to the little word "and", the Germany frequency of use is however "only" twice as high (1:680,000 in comparison to 1: 1 270,000, i.e. for 1 x "Spaltrohrmotor" in combination with "pump" in Germany, there are 680,000 x "and", and in Austria 1,270,000 x). The corresponding ratios of the English-speaking countries, the USA and the United Kingdom are fairly homogeneous (approx. 1:550,000). In terms of absolute figures, they are significantly higher, but relatively they are definitely comparable to the German-Austrian values or, in particular, the German value. These ratios should also contribute to you developing a feel for relative frequencies of use of terms.

EQUIVALENCY
The possibilities of using web-statistics methods to find out about the equivalency between two expressions of various languages are relatively limited as equivalency is defined on a semantic level and -in contrast to the country of origin of a document or a frequency of use of a term-is scarcely quantifiable or statistically recordable. Nevertheless, supplementary information is still possible: -A similar web-statistics profile can confirm equivalency or very different frequencies of use may indicate that there has to be another term.
-Context words (in the same search entry field as the term you are actually searching for) help to define the meaning (e.g. search for the word "well" together with "water" to avoid finding "well" as an adverb instead of the noun). Ultimately, a look at several direct application contexts is decisive for determining the equivalency.

RELATIVISING FACTORS
-Various frequencies of use can be related to different kinds of industrial, cultural, political, etc. environments.
-It may be the case that there is not yet a target language equivalent for a term and this has thus previously only been coined by translators and is thus also in use.
-As some countries are multilingual, the selection of countries might not enable you to precisely limit your search to native language texts. The "digital" origin of a document does not guarantee anything with regard to its genuine origin either. The TermProfile figures are thus only indications.
-Some expressions have several meanings in one language (EN: well) and are therefore more frequent than the equivalent in the other language. The origin of a site does not provide any definitive information on the origin of the site operator either, but merely expresses a probability -just like the other figures. The reliability of an Internet text and thus the language can ultimately be somewhat guaranteed only by checking the author (private person, public institution, specialist company).
-For every query which sends a request to Google, another server is addressed. Consequently, repeated, identical queries may also lead to deviating results.

IMPROVEMENT
In the future, there are plans for further possible functions: -Definition of further country groups for French and German.
-An exclusive country group option, e.g. "all countries except Germany". -Search for domain endings, e.g. org in order to exclusively find sites with relatively "official" content.
-Definition of individual user profiles (default country groups).
Hopefully, suggestions for further refinement will come up with the application of TermProfile by language professionals, so to make the best possible use of the Internet as a huge multilingual text corpus.


Tagging Portuguese with a Spanish Tagger Using Cognates

We describe a knowledge and resource light system for an automatic morphological analysis and tagging of Brazilian Portuguese. 1 We avoid the use of labor intensive resources; particularly, large annotated corpora and lexicons. Instead, we use (i) an annotated corpus of Peninsular Spanish, a language related to Portuguese, (ii) an unannotated corpus of Portuguese, (iii) a description of Portuguese morphology on the level of a basic grammar book. We extend the similar work that we have done (Hana et al., 2004; Feldman et al., 2006) by proposing an alternative algorithm for cognate transfer that effectively projects the Spanish emission probabilities into Portuguese. Our experiments use minimal new human effort and show 21% error reduction over even emissions on a fine-grained tagset.

Introduction
Part of speech (POS) tagging is an important step in natural language processing. Corpora that have been POS-tagged are very useful both for linguistic research, e.g. finding instances or frequencies of particular constructions (Meurers, 2004) and for further computational processing, such as syntactic parsing, speech recognition, stemming, wordsense disambiguation. Morphological tagging is the process of assigning POS, case, number, gender and other morphological information to each word in a corpus. Despite the importance of morphological tagging, there are many languages that lack annotated resources of this kind, mainly due to the lack of training corpora which are usually required for applying standard statistical taggers.
Applications of taggers include syntactic parsing, stemming, text-to-speech synthesis, wordsense disambiguation, information extraction. For some of these getting all the tags right is inessential, e.g. the input to noun phrase chunking does not necessarily require high accuracy fine-grained tag resolution.
Cross-language information transfer is not new; however, most of the existing work relies on parallel corpora (e.g. Hwa et al., 2004; which are difficult to find, especially for lesser studied languages. In this paper, we describe a cross-language method that requires neither training data of the target language nor bilingual lexicons or parallel corpora. We report the results of the experiments done on Brazilian Portuguese and Peninsular Spanish, however, our system is not tied to these particular languages. The method is easily portable to other (inflected) languages. Our method assumes that an annotated corpus exists for the source language (here, Spanish) and that a text book with basic linguistic facts about the source language is available (here, Portuguese). We want to test the generality and specificity of the method. Can the systematic commonalities and differences between two genetically related languages be exploited for crosslanguage applications? Is the processing of Portuguese via Spanish different from the processing of Russian via Czech (Hana et al., 2004;Feldman et al., 2006) Notice also that in the Spanish example (2b) the dative pronoun se 'her' is obligatory even when the prepositional phrase a María 'to Mary' is present.

Tagset
For both Spanish and Portuguese, we used positional tagsets developed on the basis of Spanish CLiC-TALP tagset (Torruella, 2002). Every tag is a string of 11 symbols each corresponding to one morphological category. For example, the Portuguese word partires 'you leave' is assigned the tag VM0S---2PI-, because it is a verb (V), main (M), gender is not applicable to this verb form (0), singular (S), case, possesor's number and form are not applicable to this category(-), 2nd person (2), present (P), indicative (I) and participle type is not applicable (-).
A comparison of the two tagsets is in Table 2. 2 When possible the Spanish and Portuguese tagsets use the same values, however some differences are unavoidable. For instance, the pluperfect is a compound verb tense in Spanish, but a separate word that needs a tag of its own in Portuguese. In addition, we added a tag for "treatment" Portuguese pronouns.
The Spanish tagset has 282 tags, while that for Portuguese has 259 tags.

Training corpora
Spanish training corpus. The Spanish corpus we use for training the transition probabilities as well as for obtaining Spanish-Portuguese cognate pairs is a fragment (106,124 tokens, 18,629 types) of the Spanish section of CLiC-TALP (Torruella, No  . CLiC-TALP is a balanced corpus, containing texts of various genres and styles. We automatically translated the CLiC-TALP tagset into our system (see Sect. 3.1) for easier detailed evaluation and for comparison with our previous work that used a similar approach for tagging (Hana et al., 2004;Feldman et al., 2006).

Raw Portuguese corpus.
For automatic lexicon acquisition, we use NILC corpus, 3 containing 1.2M tokens.

Evaluation corpus
For evaluation purposes, we selected and manually annotated a small portion (1,800 tokens) of NILC corpus.

Morphological Analysis
Our morphological analyzer (Hana, 2005) is an open and modular system. It allows us to combine modules with different levels of manual input -from a module using a small manually provided lexicon, through a module using a large lexicon automatically acquired from a raw corpus, to a guesser using a list of paradigms, as the only resource provided manually. The general strategy is to run modules that make fewer errors and less overgenerate before modules that make more errors and overgenerate more. This, for example, means that modules with manually created resources are used before modules with resources 3 Núcleo Interdisciplinar de Lingüística Computacional; available at http://nilc.icmc.sc.usp.br/nilc/, we used the version with POS tags assigned by PALAVRAS. We ignored the POS tags. automatically acquired. In the experiments below, we used the following modules -lookup in a list of (mainly) closed-class words, a paradigm-based guesser and an automatically acquired lexicon.

Portuguese closed class words
We created a list of the most common prepositions, conjunctions, and pronouns, and a number of the most common irregular verbs. The list contains about 460 items and it required about 6 hours of work. In general, the closed class words can be derived either from a reference grammar book, or can be elicited from a native speaker. This does not require native-speaker expertise or intensive linguistic training. The reason why the creation of such a list took 6 hours is that the words were annotated with detailed morphological tags used by our system.

Portuguese paradigms
We also created a list of morphological paradigms. Our database contains 38 paradigms. We just encoded basic facts about the Portuguese morphology from a standard grammar textbook (Cunha and Cintra, 2001). The paradigms include all three regular verb conjugations (-ar, -er, -ir), the most common adjective and nouns paradigms and a rule for adverbs of manner that end with -mente (analogous to the English -ly). We ignore majority of exceptions. The creation of the paradigms took about 8 h of work.

Lexicon Acquisition
The morphological analyzer supports a module or modules employing a lexicon containing information about lemmas, stems and paradigms. There is always the possibility to provide this information manually. That, however, is very costly. Instead, we created such a lexicon automatically.
Usually, automatically acquired lexicons and similar systems are used as a backup for large high-precision high-cost manually created lexicons (e.g. Mikheev, 1997;Hlaváčová, 2001). Such systems extrapolate the information about the words known by the lexicon (e.g. distributional properties of endings) to unknown words. Since our approach is resource light, we do not have any such large lexicon to extrapolate from.
The general idea of our system is very simple. The paradigm-based Guesser, provides all the possible analyses of a word consistent with Portuguese paradigms. Obviously, this approach mas-sively overgenerates. Part of the ambiguity is usually real but most of it is spurious. We use a large corpus to weed the spurious analyses out of the real ones. In such corpus, open-class lemmas are likely to occur in more than one form. Therefore, if a lemma+paradigm candidate suggested by the Guesser occurs in other forms in other parts of the corpus, it increases the likelihood that the candidate is real and vice versa. If we encounter the word cantamos 'we sing' in a Portuguese corpus, using the information about the paradigms we can analyze it in two ways, either as being a noun in the plural with the ending -s, or as being a verb in the 1st person plural with the ending -amos. Based on this single form we cannot say more. However if we also encounter the forms canto, canta, cantam the verb analysis becomes much more probable; and therefore, it will be chosen for the lexicon. If the only forms that we encounter in our Portuguese corpus were cantamos and (the nonexisting) cantamo (such as the existing word ramo and ramos) then we would analyze it as a noun and not as a verb.
With such an approach, and assuming that the corpus contains the forms of the verb matar 'to kill', mato 1sg matas 2sg , mata 3sg , etc., we would not discover that there is also a noun mata 'forest' with a plural form matas -the set of the 2 noun forms is a proper subset of the verb forms. A simple solution is to consider not the number of form types covered in a corpus, but the coverage of the possible forms of the particular paradigm. However this brings other problems (e.g. it penalizes paradigms with large number of forms, paradigms with some obsolete forms, etc.). We combine both of these measures in Hana (2005).
Lexicon Acquisition consists of three steps: 1. A large raw corpus is analyzed with a lexicon-less MA (an MA using a list of mainly closed-class words and a paradigm based guesser); 2. All possible hypothetical lexical entries over these analyses are created.
3. Hypothetical entries are filtered with aim to discard as many nonexisting entries as possible, without discarding real entries.
Obviously, morphological analysis based on such a lexicon still overgenerates, but it overgenerates much less than if based on the endings alone.  Consider for example, the form funções 'functions' of the feminine noun função. The analyzer without a lexicon provides 11 analyses (6 lemmas, each with 1 to 3 tags); only one of them is correct. In contrast, the analyzer with an automatically acquired lexicon provides only two analyses: the correct one (noun fem. pl.) and an incorrect one (noun masc. pl., note that POS and number are still correct). Of course, not all cases are so persuasive.
The evaluation of the system is in Table 3. The 98.1% recall is equivalent to the upper bound for the task. It is calculated assuming an oracle-Portuguese tagger that is always able to select the correct POS tag if it is in the set of options given by the morphological analyzer. Notice also that for the tagging accuracy, the drop of recall is less important than the drop of ambiguity.

Tagging
We used the TnT tagger (Brants, 2000), an implementation of the Viterbi algorithm for secondorder Markov model. In the traditional approach, we would train the tagger's transitional and emission probabilities on a large annotated corpus of Portuguese. However, our resource-light approach means that such corpus is not available to us and we need to use different ways to obtain this information.
We assume that syntactic properties of Spanish and Portuguese are similar enough to be able to use the transitional probabilities trained on Spanish (after a simple tagset mapping).
The situation with the lexical properties as captured by emission probabilities is more complex. Below we present three different ways how to obtains emissions, assuming: 1. they are the same: we use the Spanish emissions directly ( §5.1).
2. they are different: we ignore the Spanish emissions and instead uniformly distribute the results of our morphological analyzer. ( §5.2) 3. they are similar: we map the Spanish emissions onto the result of morphological analysis using automatically acquired cognates. ( §5.3)

Tagging -Baseline
Our lowerbound measurement consists of training the TnT tagger on the Spanish corpus and applying this model directly to Portuguese. 4 The overall performance of such a tagger is 56.8% (see the the min column in Table 4). That means that half of the information needed for tagging of Portuguese is already provided by the Spanish model. This tagger has seen no Portuguese whatsoever, and is still much better than nothing.

Tagging -Approximating Emissions I
The opposite extreme to the baseline, is to assume that Spanish emissions are useless for tagging Portuguese. Instead we use the morphological analyzer to limit the number of possibilities, treating them all equally -The emission probabilities would then form a uniform distribution of the tags given by the analyzer. The results are summarized in Table 4 (the e-even column) -accuracy 77.2% on full tags, or 47% relative error reduction against the baseline.

Tagging -Approximating Emissions II
Although it is true that forms and distributions of Portuguese and Spanish words are not the same, they are also not completely unrelated. As any Spanish speaker would agree, the knowledge of Spanish words is useful when trying to understand a text in Portuguese. Many of the corresponding Portuguese and Spanish words are cognates, i.e. historically they descend from the same ancestor root or they are mere translations. We assume two things: (i) cognate pairs have usually similar morphological and distributional properties, (ii) cognate words are similar in form.
Obviously both of these assumptions are approximations: 1. Cognates could have departed in their meanings, and thus probably also have dif- Nevertheless, we believe that these examples are true exceptions from the rule and that in majority of cases, the cognates would look and behave similarly. The borrowings, counter-borrowings and parallel developments of the various Romance languages have of course been extensively studied, and we have no space for a detailed discussion.
Identifying cognates. For the present work, however, we do not assume access to philological erudition, or to accurate Spanish-Portuguese translations or even a sentence-aligned corpus. All of these are resources that we could not expect to obtain in a resource poor setting. In the absence of this knowledge, we automatically identify cognates, using the edit distance measure (normalized by word length).
Unlike in the standard edit distance, the cost of operations is dependent on the arguments. Similarly as Yarowsky and Wicentowski (2000), we assume that, in any language, vowels are more mutable in inflection than consonants, thus for example replacing a for i is cheaper that replacing s by r. In addition, costs are refined based on some well known and common phonetic-orthographic regularities, e.g. replacing a q with c is less costly than replacing m with, say s. However, we do not want to do a detailed contrastive morpho-phonological analysis, since we want our system to be portable to other languages. So, some facts from a simple grammar reference book should be enough.
Using cognates. Having a list of Spanish-Portuguese cognate pairs, we can use these to map the emission probabilities acquired on Spanish corpus to Portuguese.
Let's assume Spanish word w s and Portuguese word w p are cognates. Let T s denote the tags that w s occurs within the Spanish corpus, and let p s (t) be the emission probability of a tag t (t ∈ T s ⇒ p s (t) = 0). Let T p denote tags assigned to the Portuguese word w p by our morphological analyzer, and the p p (t) is the even emission probability: p p (t) = 1 |Tp| . Then we can assign the new emission probability p p (t) to every tag t ∈ T p in the following way (followed by normalization): Results. This method provides the best results. The full-tag accuracy is 82.1%, compared to 56.9% for baseline (58% error rate reduction) and 77.2% for even-emissions (21% reduction). The accuracy for POS is 87.6%. Detailed results are in column e-cognates of Table 4.

Evaluation & Comparison
The best way to evaluate our results would be to compare it against the TnT tagger used the usual way -trained on Portuguese and applied on Portuguese. We do not have access to a large Portuguese corpus annotated with detailed tags. However, we believe that Spanish and Portuguese are similar enough (see Sect. 2) to justify our assumption that the TnT tagger would be equally successful (or unsuccessful) on them. The accuracy of TnT trained on 90K tokens of the CLiC-TALP corpus is 94.2% (tested on 16K tokens). The accuracy of our best tagger is 82.1%. Thus the error-rate is more than 3 times bigger (17.9% vs. 5.4%). Branco and Silva (2003) report 97.2% tagging accuracy on 23K testing corpus. This is clearly better than our results, on the other hand they needed a large Portuguese corpus of 207K tokens. The details of the tagset used in the experiments are not provided, so precise comparison with our results is difficult.

Related work
Previous research in resource-light language learning has defined resource-light in different ways. Some have assumed only partially tagged training corpora (Merialdo, 1994); some have begun with small tagged seed wordlists (Cucerzan and Yarowsky, 1999) for named-entity tagging, while others have exploited the automatic transfer of an already existing annotated resource in a min e-even e-cognates   , requiring no direct supervision in the target language). Ngai and Yarowsky (2000) observe that the total weighted human and resource costs is the most practical measure of the degree of supervision. Cucerzan and Yarowsky (2002) observe that another useful measure of minimal supervision is the additional cost of obtaining a desired functionality from existing commonly available knowledge sources. They note that for a remarkably wide range of languages, there exist a plenty of reference grammar books and dictionaries which is an invaluable linguistic resource.

Resource-light approaches to Romance languages
Cucerzan and Yarowsky (2002) present a method for bootstrapping a fine-grained, broad coverage POS tagger in a new language using only one person-day of data acquisition effort. Similarly to us, they use a basic library reference grammar book, and access to an existing monolingual text corpus in the language, but they also use a medium-sized bilingual dictionary. In our work, we use a paradigm-based morphology, including only the basic paradigms from a standard grammar textbook. Cucerzan and Yarowsky (2002) create a dictionary of regular inflectional affix changes and their associated POS and on the basis of it, generate hypothesized inflected forms following the regular paradigms.
Clearly, these hypothesized forms are inaccurate and overgenerated. Therefore, the authors perform a probabilistic match from all lexical tokens actually observed in a monolingual corpus and the hypothesized forms. They combine these two models, a model created on the basis of dictionary information and the one produced by the morphological analysis. This approach relies heavily on two assumptions: (i) words of the same POS tend to have similar tag sequence behavior; and (ii) there are sufficient instances of each POS tag labeled by either the morphology models or closedclass entries. For richly inflectional languages, however, there is no guarantee that the latter assumption would always hold.
The accuracy of their model is comparable to ours. On a fine-grained (up to 5-feature) POS space, they achieve 86.5% for Spanish and 75.5% for Romanian. With a tagset of a similar size (11 features) we obtain the accuracy of 82.1% for Portuguese. Carreras et al. (2003) present work on developing low-cost Named Entity recognizers (NER) for a language with no available annotated resources, using as a starting point existing resources for a similar language. They devise and evaluate several strategies to build a Catalan NER system using only annotated Spanish data and unlabeled Catalan text, and compare their approach with a classical bootstrapping setting where a small initial corpus in the target language is hand tagged. It turns out that the hand translation of a Spanish model is better than a model directly learned from a small hand annotated training corpus of Catalan. The best result is achieved using cross-linguistic features. Solorio and López (2005) follow their approach; however, they apply the NER system for Spanish directly to Portuguese and train a classifier using the output and the real classes.

Cognates
Mann and Yarowsky (2001) present a method for inducing translation lexicons based on trasduction modules of cognate pairs via bridge languages. Bilingual lexicons within language families are induced using probabilistic string edit distance models. Translation lexicons for abitrary distant language pairs are then generated by a combination of these intra-family translation models and one or more cross-family online dictionaries. Similarly to Mann and Yarowsky (2001), we show that languages are often close enough to others within their language family so that cognate pairs between the two are common, and significant portions of the translation lexicon can be induced with high accuracy where no bilingual dictionary or parallel corpora may exist.

Conclusion
We have shown that a tagging system with a small amount of manually created resources can be successful. We have previously shown that this approach can work for Czech and Russian (Hana et al., 2004;Feldman et al., 2006). Here we have shown its applicability to a new language pair. This can be done in a fraction of the time needed for systems with extensive manually created resources: days instead of years. Three resources are required: (i) a reference grammar (for information about paradigms and closed class words); (ii) a large amount of text (for learning a lexicon; e.g. newspapers from the internet); (iii) a limited access to a native speaker -reference grammars are often too vague and a quick glance at results can provide feedback leading to a significant increase of accuracy; however both of these require only limited linguistic knowledge.
In this paper we proposed an algorithm for cognate transfer that effectively projects the source language emission probabilities into the target language. Our experiments use minimal new human effort and show 21% error reduction over even emissions on a fine-grained tagset.
In the near future, we plan to compare the effectiveness (time and price) of our approach with that of the standard resource-intensive approach to annotating a medium-size corpus (on a corpus of around 100K tokens). A resource-intensive system will be more accurate in the labels which it offers to the annotator, so annotator can work faster (there are fewer choices to make, fewer keystrokes required). On the other hand, creation of the infrastructure for such a system is very time consuming and may not be justified by the intended application.
The experiments that we are running right now are supposed to answer the question of whether training the system on a small corpus of a closely related language is better than training on a larger corpus of a less related language. Some preliminary results (Feldman et al., 2006) suggest that using cross-linguistic features leads to higher pre-cision, especially for the source languages which have target-like properties complementary to each other.


Fusion of FNA-cytology and gene-expression data using Dempster-Shafer Theory of evidence to predict breast cancer tumors.

Decision-in decision-out fusion architecture can be used to fuse the outputs of multiple classifiers from different diagnostic sources. In this paper, Dempster-Shafer Theory (DST) has been used to fuse classification results of breast cancer data from two different sources: gene-expression patterns in peripheral blood cells and Fine-Needle Aspirate Cytology (FNAc) data. Classification of individual sources is done by Support Vector Machine (SVM) with linear, polynomial and Radial Base Function (RBF) kernels. Out put belief of classifiers of both data sources are combined to arrive at one final decision. Dynamic uncertainty assessment is based on class differentiation of the breast cancer. Experimental results have shown that the new proposed breast cancer data fusion methodology have outperformed single classification models.

Since there are number of factors that determined the risk of breast cancer, so it is not advisable to rely on just one source of information for diagnosis. There is a well established association between different symptoms of breast cancer e.g. germline BRCA1 or BRCA2 mutations are associated with increased lifetime risk of developing breast cancer [3] but not all mutation carriers develop breast cancer and the age of onset of breast cancer remains unpredictable.
[4] There is a well established association between atypical ductal epithelium identified by histological biopsy, nipple aspiration (NA) or fine needle aspiration (FNA) and an increased risk of future breast cancer.
[4] The relative risk of developing invasive breast carcinoma for women found to have atypical ductal hyperplasia on breast biopsy is 4.3 times that of the general population and, when combined with a positive family history, the relative risk of invasive breast cancer rises to 9.7 times that of the general population. Association between the different symptoms are not only factor that contribute the idea of fusing information from different resources but the limitation of diagnostic methods are one of the major fact as well e.g. mammographic screening is the most reliable method but often fails to detect tumors that are less then 5mm in size and also dense breast tissue are difficult to interpret. Medical information fusion has been demonstrated by Azuaje et al., [9] an information fusion technique based on a knowledge discovery model and the case-based reasoning decision framework using data from heart disease risk estimation domain. Fusion techniques combine information at the retrieval-outcome level and data at the discovery-input level.
[9] Paquerault et al., proposed a technique based on the fusion of one-view and two-view information to improve the performance of mammography mass detection of breast cancer. A classifier was trained to differentiate the true mass pairs from the false pairs. A final fusion stage combined the twoview object pair information with the one-view object scores.

[10]
There is wide recognition of Fine Needle Aspiration (FNA) and microarray analysis as the principal diagnostic methods.
[1, 18] Microarray methodology involves placing a large number of DNA fragments corresponding to the different genes to be studied on a glass slide or glass wafer. [3] Microarray analysis determined the level of expression in a tissue sample of many genes simultaneously. Microarray experiments generate large datasets with expression values for thousands of genes [4], but usually not more than a few dozens of array, that gives rise to the issue of the curse of dimension. FNA cytology is the technique that involves the insertion of a fine needle (between 21 and 25 gauge) into a lesion and the extraction of a small sample of cellular material which is The aim of our work is to study and apply Dumpster Shafer theory of mathematical belief to fuse breast cancer data obtained from different diagnostic techniques in the management of breast disease. Input data, consisting of feature vectors ported into three different classifiers as input. The classifiers we used in this study are SVM with linear, Polynomial and RBF kernel. Each classifier provides beliefs of two classes benign and malignant. These beliefs are then combined to reach a final diagnosis using Dempster's combination formula. The experiments are carried on two types of breast cancer data. One is Fine Needle Aspirates Cytology (FNAc) data, other is obtained from gene expression pattern in peripheral blood cells. FNAc breast cancer data collected by physician W.O. Wolberg, University of Wisconsin Hospitals, contained 699 samples, 458 of which were benign and 241 of which were malignant.
[1] FNAc data set is publicly available on UCI machine learning repository. Gene expression data consist of 60 blood samples obtained from 56 different women of which 24 were malignant and 36 were benign.
[6] We have used leave one out cross validation. To implement this method, the available data was divided into k disjoint sets; k models were trained using different combination of k−1 partitions and were tested on the remaining partition. Cross-validation makes good use of the available data as each sample is used both as training and test data. Cross-validation is therefore especially useful where the amount of available data is insufficient to form the usual training, validation and test partitions required for split-sample training. [12] Methodology: To describe the methodology in figure 1 we start with the visualization of FNAc and microarray data. Each element of FNA cytology pattern sets consisted of 9 cytological characteristics. Each of 9 cytological characteristics of breast Fine Needle Aspirates (FNA) differs between benign and malignant samples. The nine independent parameters of FNAc data are: clump thickness, uniformity of cell size, uniformity of cell shape, marginal adhesion, single epithelial cell size, bare nuclei, bland chromatin, normal nucleoli, and mitoses. [18] Each of these characteristics is assigned a number between 1 and 10, with the largerest numbers generally indicating a greater likelihood of malignancy. However, not a single measurement by itself can be used to determine whether the sample is benign or malignant.   The classifiers provide the category of the cancer class: benign and malignant. Each classifier provides belief for classes. These beliefs are then combined using Dempster's rule of combination. Dempster's combination involves evaluation of beliefs and uncertainties from individual classifiers along with classifier decision. The SVM believe is calculated using decision function in equation (6). Uncertainty is calculated using equation (13). Dempster's rules of combining belief and uncertainty are described in equation (12). Dempster's rules of combination involve evaluation of beliefs and uncertainties from individual data source along with classifier decision. We perform classification on all three kernels and chose the best classification result out of three. We then combined the beliefs of SVM classifier of microarray (S mic ), and SVM classifier of FNA (S fna ). Let's assume that Bel_S mic (B) is the classifier beliefs of microarray and Bel_S fna (B) is the beliefs of FNA of class benign. Uncertainties for two data sources are U_S mic and U_S fna . Combined belief for benign class is as follows:

Bel_comb(M)=[Bel_S mic (M) * Bel_S fna (M)]+[U_S fna* Bel_S c (M)]+[Bel_S mic (M) * U_S fna]]
(2) Support Vector Machine Support vector machines are systems based on regularization techniques which performed well in many classification In our experiments, a linear, polynomial (of degree 2 to 20) and RBF functions were used. The hyper plane found by an SVM in the feature space corresponds to a decision boundary in the input space. The value of the decision function can be used to evaluate belief masses. The SVM constructs a decision function that is represented in higher dimensional space by

Dempster Shafer Theory of Evidence
DST is a generalization of the bayesian theory of subjective probability. Bayesian theory requires probabilities for each question of interest, while belief functions allow us to base degrees of belief on the probabilities of related question. The belief and the ignorance or uncertainty concerning a question can be modeled independently.
[19] In a Dempster-Shafer reasoning system, all the mutually exclusive context interpretations are enumerated in a "frame-of-discernment", denoted Θ. A mathematical function that translates degree of support to belief is known as a Belief Function.
[19] Basic belief m(X), which represents the strength or belief mass of some evidence for event X provided by the source of information under consideration, has the following properties ( ) 0 Here φ is empty, indicates belief of empty set is always zero and Θ  represents the total event space. The belief function for an event A is given by To understand how DST is related to our work, let's consider, there is a cancer patient, and from the reality constraints person have "Malignant" or "Benign" cancer. Now our task is to specify the cancer as one of the four possibilities described as: Meaning person is "Malignant", "Benign", "either Malignant or Benign" (which is actually an indication of ignorance or uncertainty), or φ "neither Malignant nor Benign" (which is an indication of exceptional situation). With the frame of discernment Θ defined, each data source Di would contribute its outcome by assigning its beliefs over Θ. This assignment function is called the "probability mass function" of Di, denoted mi. So, according to Di's outcome, the probability that "the cancer is Malignant" is indicated by a "confidence interval" whose lower bound is a "belief" and whose upper bound is an "Uncertainty".
[Belief i (M), Uncertainty i (M)] Belief i (M) is quantified by all pieces of evidence E k that support proposition "Malignant" For each proposition in Θ, e.g., "Malignant", Dempster-Shafer theory gives a rule of combining data source Di's outcome mi and data source Dj's outcome mj The evaluation of uncertainty We used Decision function in SVM to evaluate the belief masses 'm (i) '. Now we evaluate the uncertainty according to belief masses. If the value of beliefs for K classes is close to each other, then the classifier is more uncertain about its decision.
[19] This mean as the beliefs start spreading apart uncertainty starts decreasing. Let uncertainty be denoted as S(U)

Results & Discussion:
This section provides the results of individual classifiers as well as the combination of classifiers using DST for breast cancer data. The performance of SVM based classifiers with linear, polynomial and RBF kernel has been evaluated using sensitivity, specificity, positive predicted value (PPV), Sensitivity is the probability for a class A sample to be correctly predicted as class A, Specificity is the probability for a non class A sample to be correctly predicted as non-A, PPV is the probability that a sample predicted as class A actually belongs to class A, NPV is the probability that a sample predicted as non class A actually does not belong to class A. For each classification method and each class, these parameters are listed in the tables below. Table 1 shows the results of SVM classifiers on FNA data. The overall accuracy is 90.25% with sensitivity of malignant is 91.6% and benign is 88.8%. Table 2 shows the performance of the microarray data the overall accuracy is 81.94% with sensitivity of malignant is 80.50% and benign is 83.30%. Table 3 shows the result of application of DST to fuse the classifiers. The overall accuracy shown in Table 3 is 94.4% with sensitivity of malignant is 97.1% and benign is 94.4%. Table 3 shows improved accuracy using information fusion with DST.  Table 4 shows the classification results of classes Malignant (M) and Benign (B) classes. Fusion with DST shows the maximum accuracy where 35 malignant classes were correctly identified while 1 was classified as benign. The use of FNA data with the SVM classifiers identified 33 benign classes and 3 were incorrectly classified as malignant. Table 5 shows that when two single sources of data: gene expression and Cytology FNA data were fused using Dempster Shafer it showed higher accuracy.  Overall accuracies of individual and DST classifiers in Table 5 show that fusion by DST has improved the breast cancer prediction as compared to individual classifiers.

Conclusion:
We have looked at the fusion of data from disparate sources for the prediction of breast cancer tumors. We have demonstrated our methodologies for fusing data form FNAc and microarray data set to achieve a batter overall prediction of breast cancer tumors. The paper has presented a method for fusing medical data using multiple classifiers where uncertainty and unequal costs of errors are present. The fusion framework has been presented for the computation of belief functions and uncertainty values from individual classifiers and data fusion through the Dempster-Shafer theory, in which class differentiation quality is used for the computation of uncertainties. The fusion approach has shown the best classification accuracy of breast tumor classification. The fusion approach remained robust in the presence of fairly different classifier performances. The ability to handle such situations robustly and the ability to classify samples in the presence of classifier uncertainty, makes this approach attractive for healthcare applications.