:  Pisa’s Question Answering System
Giuseppe Attardi, Antonio Cisternino, Francesco Formica, Maria Simi, 
Alessandro Tommasi, Cesare Zavattari 
Dipartimento di Informatica, Università di Pisa
{attardi, cisterni, formicaf, simi, tommasi, zavatt}@di.unipi.it

 
“Computers are useless:  they can only give answers” – Pablo Picasso 
Abstract
 is based on a series of filters which rule out sentences that do not answer to a given natural language question.  The architecture of the system is straightforward in its conceptions, yet some of the modules bear intrinsic complexity.  Syntactical text analysis is done through Minipar, a dependency-based parser, and , always accessed through a disambiguation system.  Question analysis includes keyword extraction and expansion for IR-like search and answer type detection.  The only truly “selective” filter is the first one, which retrieves a relatively small number of sentences from the collection basing on the extracted keywords.  NE tagging is performed on the retrieved paragraphs so as to rule out those which do not contain the required type.  Syntactical dependencies as identified by Minipar are “abstracted” as a set of relations among words both in the question and in the candidate answer; a match between the two sets of relations is then performed, selecting those paragraphs which “better” suit the question’s requirements according to an empirical/experimental measure.  The whole system is completely automatic from the question to the answer, and is set in loops so that larger recall is imposed on the IR-style search if no answer was found. 

1.  Overall structure
As a preliminary step, the documents of the collection are indexed using IXE[2], an indexing an retrieval tool we have developed.  Documents are indexed as plain text and information about sentence boundaries and term positions are stored in the index.
The processing of a question is performed in five steps:  
•	question analysis; 
•	keyword search; 
•	type filter; 
•	relationship unification filter; 
•	query expansion. 
During question analysis the question is parsed, its expected answer type is identified, and relevant keywords for an information-retrieval-like search are extracted.  Those keywords are used to select a relatively small number of sentences to be evaluated as candidate answers.  PIQASso uses a dependency parser, Minipar[?], to analyze questions and paragraphs.
The type filter analyses the candidate answers verifying that they do contain entities of the type expected by the question, discarding those which do not.
The last, and more semantic filter, identifies a set of relationships among words in the question, and compares such relationships with those found in the candidate answer.  Such relationships are determined basing on the analysis provided by Minipar.  Sentences have a matching cost depending on how different such relationships are from the question’s, and are returned sorted according to such cost.  Sentences whose matching cost is above a ceiling are discarded.  Sentences which pass the last filter are compared, and the most popular answer is selected.
Should no sentence get through all the filters, question expansion is performed so as to allow for more (and different) sentences to be analysed:  the cycle is therefore reentered from the keyword search step.  Query expansion really merges with query extraction, and is therefore described along with question analysis.
 is a completely vertical system; all work is done by one process, which performs textual analysis, keyword search and all the filters; the only separate program is the document indexer.
2.  Indexing
The architecture of our document indexing and retrieval subsystem is based on IXE[2], a high-performance C++ class library for building full-text search engines. We tailored the library to build a paragraph retrieval tool suitable for question answering.  In fact, the straightforward solution of using a traditional IR system for indexing paragraphs instead of documents is not appropriate, since qualifying terms might appear in nearby sentences.
Our solution is to index full documents, but to add sentence boundary information to the index, i.e.  for each document, the offset to the start of each sentence.  A sentence splitting tool, also based on a maximum entropy learning algorithm, is applied to each document before indexing. The sentence splitter is an implementation of the one described by Reynar and Ratnaparkhi[9].
Since sentence splitting is quite time consuming, performing it at indexing time improves significantly PIQASso performance. On a 1 MHz Pentium 3, a paragraph search takes less than 50 msec.
The IXE paragraph search engine stores the full documents in compressed form but returns single paragraphs.  The actual queries used in PIQASso consist of a proximity search for the most important terms in the query (i.e.  closer to the root of the parse tree) combined in AND with the other terms.
3.  Question analysis
Question analysis has the goal of extracting as much information as possible from the question, with the purpose of matching it with analogous information extracted from candidate answers.
The kinds of information extracted from the question are:  
•	the set of keywords to be used in keyword search; 
•	the expected named entity type of the answer; 
•	relationships among the relevant words. 
These three major pieces of information correspond to three successive steps in the process of question answering:  keyword based retrieval, a filtering step based on the answer type, and a filtering step accounting for logical relationships among sentences.
The question is parsed by means of Minipar.  The tree returned by the parser is then enriched with additional informations as a result of the analysis.
3.1  Minipar
A fundamental tool for our system is Minipar[?], the dependency parser we have used.  Given a sentence, the dependency parser returns a set of dependencies among words:  it makes explicit the syntactical/logical relationship that each word has with the word it depends on.  In a sentence like “John loves Mary”, Minipar tells us that “John” is a noun, that “loves” is a verb whose root is “love”, that “Mary” is a noun.  Furthermore, it says that “John” is tied to “loves” with the role of subject, while “Mary” has the role of object.  This allows us to identify a semantic relation between the words “John” and “Mary”, being that the first loves the second.  A sentence like “John likes Mary” has the same structure, and would convey the same meaning, as far as loving and liking do.  The resulting dependencies can be seen as a tree, since every word depends on only one other word, and a virtual empty node is always included as root.
In order to account for particular syntactic structures, other empty nodes may be inserted in the tree.  For instance, in parsing the sentence “It’s the early bird that gets the worm”, the word “that” is correctly identified as the subject of the “gets the worm” part of the sentence, and an empty node is also inserted in the resulting tree.  Such node is also recognized as the subject of the verb “gets”, and it is made to refer to the word “bird”. The parser has therefore identified “that” as the syntactical subject of “gets” and “the early bird” as the logical one.
This problem is sometimes referred to as coreference resolution:  identifying to what entity in the sentence (or in previous sentences) do pronouns refer.  Although Minipar does not help with cross-sentence coreference resolution, or even pronoun resolution, its resolving it within the sentence is extremely useful in a question answering task.  From the above sentence we gather that the early bird gets the worm, enabling us to answer directly a question like “who gets the worm? ”, even if question and answer were stated in slightly different syntactic forms.
Minipar is not a perfect tool:  not all phrases are parsed correctly, and the dependency-based mechanism itself, sometimes, seems to leave a bit of arbitrariety in the choice of relationships, so that two similar phrases can be parsed very differently, although both correctly.  This means that the job of identifying the essential and relevant relationships for comparison with the question requires some more work and ingenuity.
Minipar is available as a library, making its integration in very straightforward.
Table 1 shows a non-comprehensive list of the relations a word can have with respect to the father.

relation  	 meaning 	
i  	 the main verb 	
subj, s  	 subject of the verb 	
obj, objn  	 object of the verb 	
pcomp-n  	 prepositional complement 	
appo  	 apposition 	
gen  	 genitive 	
inside  	 location specifier 	
nn  	 nominal compound 	
lex-mod  	 lexical modifier 	
det  	 determiners 	
mod  	 modifiers (adjs, advs, preps) 	
pred  	 predicate 	
aux  	 auxiliary verb 	
neg  	 nagative particle 	

 
Table 1:  some of Minipar’s relations
Minipar is also able, to an extent, to identify and classify named entity.  Basing on its own internal dictionary, plus a few rules, it is able to attach to a group of words a tag, telling us, for instance, that such a group refers to a person, a geographic location, an amount of money.  While this is a very interesting capability, we found that it is heavily based on the parser’s internal dictionary. To overcome some limitations, we experimented integrating this named entity tagger with an external named entity tagger we developed.
[Sorry. Ignored \begin{small} ... \end{small}]
Table 2:  a parsed example
In table 2 we see Minipar’s output tree for the sentence:  “Galileo was the son of a court musician who made some of the earliest experiments in opera.” Aside each node are printed:  the relation with the father, the node label (which, when numerical, is its position in the sentence), the part of speech tag, the morphological root, and, among brackets, the list of semantig tags owned by the node, and, in the case of empty nodes, the node to which they refer (after the ’@’).
3.2  Named Entity tagger
The Named Entity extractor identifies the person names, locations, quantities and dates, assigning them the types defined in the MUC task [4]. It is based on a maximum entropy probabilistic model[3], uses TreeTagger[?] and gazetters to calculate the features.
The NE tagger is trained over a tagged corpus.
The types identified by the NE tagger for a given word are added to the semantic features of that word according to Minipar.
3.3  Keyword extraction and expansion
Determining the set of keywords to use is straightforward at the beginning, but gets more tricky when expansion is required.
In the current state of the system, five steps of extraction, each allowing larger recall in the search, are defined.  The first, a simple one, returns all adjectives, adverbs, nouns and verbs of a question, with some exceptions.  Some nouns, such as “type”, “sort”, “kind”, “name” ..., frequently occurring in questions are not suitable to be included in the search, since very likely they will not occur in the answer. There are very few of such nouns, and they have been determined experimentally.  Verbs have exceptions too, like “call” and “be”. As for adjectives, qualifiers of “how” (as in how long, how far, etc.) will not be included in the search.  Finally, unrecognized words (words for which the parser did not tell the part-of-speech tag) were included or not in different experiments, without a clear effect on performance.
The first step of expansion substitutes each keyword with its prefix, obtained by means of the stemmer. This substitution accounts for most morphological variations of the word.  At the same time some prefixes, which are very common in questions are discarded from the keywords.  Examples are “locate”, “find”, “situate” for questions expecting a location as an answer, “day”, “date”, “year” for questions expecting a date and so on.  There are very few of such exceptions in  (about a dozen), and these are the cases in which the type makes these words superfluous.
In order to perform stemming, we have integrated in  the code of an implementation of Lovins’s stemmer by Linh Huynh, described in [6]. According to the author the implementation has some small difference from the original algorithm.  The code is freely available (under GNU General Public Licence, see [1]) from 
http://www.cs.waikato.ac.nz/~eibe/stemmers/. Being straight C code, and being the algorithm rather simple, it was extremely straightforward to insert it directly into ’s C++ code.
The second expansion step consists in adding to the previous search terms their synonyms (in or), so that a broader search can be performed.  For each keyword, its synonyms are searched in  with respect to the word sense as determined by WNSense (see section ). Only the stem of such synonyms is introduced, so that their morphological variations will be caught as well.
[7]has proven to be an extremely effective tool, deployed by many of the TREC participants, among which last year’s best performing system FALCON[5]. The semantic links which  establishes among terms are of great use whenever the hyperonyms or hyponims of a word are to be found, and it also comes in handy for disambiguating word senses and classifying them.
The third and fourth expansion steps, as very little can now be added to the search terms, take risks, by dropping away search terms, in order to get better recall.  It is very hard to tell which search term is absolutely necessary; we have adopted the following heuristic. During the third phase, adverbs are dropped.  Looking for the name of the first man on the moon?  We will be looking for a man on the moon if nothing better can be found, and “hope” (or verify through the last filter) that it is the first one.
During the last expansion cycle, and if more than 3 keywords in and are still in the query, then a more drastic approach is taken.  Verbs are discarded, and so are person’s first names when the second name is there as well.  If after such a pruning there are still more than 3 keywords in and, then we also strip away those keywords whose father (as from the dependence tree) is already within the keywords to be searched.  This has the effect, if looking for a black cat, to perform a search for a cat, black being a modifier of cat, and therefore depending on it.
3.4  WNSense
WNSense (Sense) is a tool we have developed which constitutes an interface to . It is able to determine the type of a word, a accomplish simple word sense disambiguation, and establish semantic similarity between words with respect to the hypernonymy and synonymy relationships.
3.4.1  The “type” of a word
’s synsets are organized into 45 lexical files based on syntactic categories (verbs, nouns, etc.) and logical ones (substance, person, animal, etc.). Of these we have used the 23 files for the nouns, in order to determine the type of a given word.
A word can have multiple meanings, which result in different types (“cat” can refer to an animal or a person), and therefore, a disambiguation must be performed.  At this level, no context of the word exists, therefore the disambiguation is done according to ’s arrangement of the senses by frequency.  The heuristic used for determining the most likely type of a word with senses S={s0,...,sn}, ranked by frequency computes the probability (bar normalization) that the word has type Ti. 

	P(Ti)=Sj=0ng(sj)

where 

	g(sj)= {
	(1-k)*(j/n)	ifsjÎTi
	0	altrimenti.

k is a paramether of the heuristic, roughly the probability that the first sense is the right one.
3.4.2  Disambiguation
When the context of a word is available (typically, there is not enough context in questions, while some is available in answering sentences), disambiguation can be performed more accurately. We have used the Specification Marks Method[8] to disambiguate nouns.
3.4.3  Word similarity
Word similarity for hyperonyms depends on the difference of depths of senses in the  taxonomy.  While it is acknowledged that this is not a very good measure of word similarity, it only affects one sense of a word.  As all senses are considered according to the probability computed either naively or via disambiguation, the overall value is more reliable.
Also, the depth difference is normalized by the taxonomy depth, so that depth difference of 1 in a detailed taxonomy is much less than difference 1 in a more coarse one.
Synonimy too is computed over all senses of words, by accessing ’s synsets for the words.
3.4.4  Word alternatives
WNSense also helps when alternatives for a word must be found, as for keyword expansion.  For this task, the heuristic is:  consider all words in all synset of the word w.  For each of these words, verify if they are synonyms of w (according to the measure sketched above). In practice, this is requiring that not only are such words synonym of w, but the vice versa is also true.  This is done to avoid cases in which a synonym of a word is a word with multiple meanings, few of which are related to the first word.
3.5  Expected answer type
The expected answer type is the type of entity which is expected as answer to the question.  Obviously, the expected answer type is only helpful when questions are factual, and do not require for complex explanations, whose “type” is not well defined.
It is possible to rule out irrelevant sentences by verifying if they contain an entity of the expected type.  TREC 2001 requires the answer not to be longer than 50 characters and this practically means that only the answering entity should be returned. Finding an entity of the proper type, therefore, not only helps ruling out candidate answers, but it is necessary, as a matter of fact, to produce a valid answer.
3.5.1  Wh-driven taxonomy
The taxonomy in which to organize questions must necessarily reflect the ability one has to detect the type of entities in the answer.  We have defined a coarse grained taxonomy basing on entity tagging as performed by Minipar, and we have extended it by means of ’s classification of terms as performed via WNSense.  The categories we have defined are:  person, organization, time, quantity, location. It is worth noting that a question may have type person or organization, like in the case of “Who killed John Fitzgerald Kennedy? ”. These categories correspond to the cases in which the type of a question can be determined easily by the so-called wh-word:  “who” for the first two categories, “when” for the third, “how many” or “how much” for the fourth, “where” for the fifth.
Of course, these categories do not cover all questions, nor all question expecting a location begin (or even contain at all) the word “where”. Particular care must be taken for the case of “what” questions, whose analysis is more complex.
3.5.2  The “What” case
Perhaps the most straightforward “what” question is the one expecting a definition:  “what is narcolepsy? ”, “what is molybdenum? ”. In this case, the type of the answer is nothing but the answer itself:  a disease, a metal.  For these cases, our first attempt was of looking up  for the type of the word requiring the definition, but soon found out that the lack of context made the choice of the right sense problematic.  Therefore, we decided to treat “definition questions” as typeless questions:  entities of any type (as long as they do have a type) may be the right answer (and therefore the type filter does not apply), provided of course they appear in structures such as “narcolepsy is something” or “molybdenum is something else”.
After “what” there can often be a specifier, which can help alone telling the type of expected answer.  In “what king signed the Magna Charta? ”, looking up (by WNSense) the type of “king” is enough to know that the expected answer type belongs to category person. For this purpose, some of the 26  top-level categories are mapped to our own five when such a mapping was straightforward (there are categories such as “person”, but also such as “feeling”). If the ’s category does not fit any of ours, it is taken as is:  “what metal has the highest melting point” has the type “substance”, as WNSense gathers from .
3.5.3  Proper or common nouns
An additional step is taken when the expected answer type is detected to be a person. A question like “who is Zsa Zsa Gabor? ” expects a definition, and therefore common nouns, while a question like “who is the king who signed the Magna Charta? ” expects a proper noun.  A finer control can therefore be performed on the person category:  if the question provides with a proper noun, a common noun is expected and vice versa.
3.6  Relationships among words
Relationships among the words in the question are identified by Minipar.  In a question like “who killed John F. Kennedy”, Minipar identifies the verb “killed”, having “Kennedy” as object, and an “unknown” subject.  Matching answering sentences therefore have to provide a “kill” verb with the same “Kennedy” as object.  Obviously, things can be stated in a different syntactical form, which can shuffle up the dependencies in the sentence.  To an extent, this problem is taken care of during the matching (as will be described for the last filter), so that as far as question analysis go, the output of Minipar is not particularly modified.
3.6.1  Placing the “Type node”
As it happens, if a sentence puts words in the same relations as the question, and contains an entity of the proper type, it is still not guaranteed to be an answer.  There is still a lack of connection between the answering entity and the words appearing in the question. Table 3 shows the relations extracted from the question “What instrument did Glenn Miller play? ”.

node1  	 relation  	 node2 	
play  	 obj  	 instrument 	
play  	 s  	 Miller 	
play  	 s  	 Glenn 	
Miller  	 lex-mod  	 Glenn 	

 
Table 3:  relations for “what instrument did Glenn Miller play? ”
The type of the question is “artifact”, the type of the word “instrument”. An answer like:  “Glenn Miller played trombone” obviously put the answer entity (“trombone”) in the place the word “instrument” had in the question.
For this reason, we have extended the relationships of the question by inserting a type node, that is an empty node which is supposed to be matched against the answering entity.  Placing such node in the right spot is crucial.  In the case “who killed John F. Kennedy”, such node should be the subject of the verb.
Experimenting over the questions, and analyzing Minipar’s output, we were able to see that, several times, such type node could be put at the place of the first “empty” subject found in the question.  This is because the main verb of the question is often the first one, and because an empty subject means that the actual subject was not in the question (the missing, required entity).
An exception to this rule is when the required entity does not participate in the action as a subject, as in question “in what year did the Titanic sink? ”. In this case, the answer is a complement, and the type node is therefore required to be in relation with the verb. The second, and perhaps most important exception is the “Glenn Miller” case shown above.  When the question is a “what” question which provides a specifier like “instrument” (hence it is not a definition question, the type is determined by the specifier), the type node should be put at the specifier’s place (in the example, as object of the verb).
4.  Keyword search
Keyword search is performed to select candidate answer sentences from the (quite large) TIPSTER collection of documents.
While we do have projects aimed at the integration of information coming from different sentences, in this version of  we have limited the search of the answer to those which were fully justified within a sentence.  This, obviously, also simplifies textual analysis, as only a contextless sentence had to be analysed at once.
To index, store and retrieve sentences, we have used a search engine developed within our group, and called IXE[2]. Such indexer and search engine guarantees state of the art versatility and terrific performance.  Thanks to it, integrating it with the sentence splitter, we were able to index all of the TIPSTER collection, obtaining an index which:  
•	contains all of the original, plain-text material; 
•	for each word, not only stores the documents it was found in, but the position inside of the documents as well; 
•	stores sentence splitting information (for each document, the offset at which each new sentence begins). 
In theory, several other kinds of information could be stored in the index, like the tag context a term appears in, but as we have treated documents as plain texts (stripping off the tags), such feature was not exploited.  Also, eager to perform all of the experimentation possible, we preferred to avoid index time computation, so that parameters could be changed easily without re-indexing the whole collection at the cost of a little overhead in the retrieval phase.
IXE allows for complex searches to be performed on the index.  It is worth noting that, although sentence boundaries information have been stored in the index, search is performed document-wise, in order to guarantee better recall.  Imagine two sentences like:  “Neil Armstrong walked on the moon.  Armstrong was the first man to walk on Earth’s only satellite”. Now, a question like “Who was the first man to walk on the moon? ” likely yields to the keywords “first”, “walk”, “moon”, and arguably “man”. Note that while the two sentences above do contain all those keywords, none of them does by itself (of course, we will match “walked” with “walk” by means of prefix search and the stemmer). Instead of looking for the keywords sentence by sentence,  performs a proximity search, in which terms are looked for within a specified number of words. An example of such query is:  
proximity 100 ((first) & (walk*) & (moon)) 
which looks for the term “first”, for the prefix “walk” and for the word “moon” within a window of one hundred words.  In the example above, such window spans across the two sentences, which would therefore both be returned, individually, as candidate answers.
Keyword expansion would hardly propose “satellite” as an alternative to “moon”, and therefore the second sentence would not be returned if it was not for proximity search.  When evaluating the second sentence within the last filter, it is possible to match “moon” against “satellite”, at a cost.
Determining the size of the proximity window is somehow tricky.  An answer to a short question may appear in the middle of a very long one, and vice versa, an answer to a complex question could be much smaller than the question itself (even a fully-justifying sentence as we expect to find). However, while question and answer lengths are not that intimately related, it seems reasonable that the keywords in a justifying answering sentence would not likely be spread apart.  We have therefore resolved to make it twice the number of nodes in the analysis of the question, both relevant and irrelevant (irrelevant nodes may account for complicated constructions, and were therefore counted as well).
The heuristic proposed for keyword extraction works fine for short questions, but returns way too many terms for long questions.  Thus, we have divided keywords in two sets:  those which must fall within the proximity window, and those which are only requested to be found in the document. The query issued is therefore, in the most general case, an and of terms required to be found in the document, and of a proximity.
The criterion with which terms are put in either of the two sets is based on the depth of the terms itself in the parse tree.  Those closer to the root, and therefore more “central” to the question, are required to be found within the proximity window, while the others (“accessory” in a sense), are only requested to be in the document, and may therefore be missing in the sentence.
5.  Type filter
Once the expected answer type has been identified during the question analysis phase, the sentences obtained from the search can be analysed so as to make sure they contain entities of the proper type.
Sentences are parsed by Minipar and entities are tagged in this process, with the possible integration of the NE tagger.  The tree is then visited, looking for at least a node which is tagged as the question expects.
One further check we introduced is that such an entity found in the sentence must not be already present in the question.  Consider a question like “Who is George Bush’s wife? ”. This question expects a proper noun of person as answer.  A sentence like “George Bush and his wife visited Italy” does contain a proper name (“George Bush”), but does not answer the question at all.  Because such sentences are indeed frequent (the search keywords being “George”, “Bush” and “wife”), it is very useful to be able to rule them out at this point.
Sentences which do not verify this condition are rejected.
6.  Relation unification filter
Sentences which survive the type filter, are further verified by the relationship unification filter, which is the last and more “semantic” one.
Through Minipar, a set of relationships among pairs of words are identified both in the question and in the candidate answer.  The idea is to verify that the sentence puts words in the same relationship that the question does, so that if question is looking for a man who walked on the moon, candidate answers will talk about a man who walked on the moon.
The processing of the filter can be summarized:  
•	determine a set of relationships among nodes in the question and in the sentence; 
•	try and find the relationships in the question among those in the answer; 
•	evaluate the cost of the proposed matching, and find the solution with the lower cost. 
In order to abstract a little from the parser’s tree view, we have flattened the parse tree into a set of triples, which also allowed us to introduce new relationships.  This is justified by multiple reasons.  First, not all nodes in the question and in the answers are considered “relevant”. The criterion for a node to be considered “relevant” with respect to this filter is the same for which it is considered as keyword:  nouns, verbs, adjectives and adverbs are considered (including dates and words of unknown tag), the rest is discarded.
The ceiling cost for a sentence to pass the filter is still pretty roughly determined as either:  a) very high, so that each sentence providing with a match for the type node can pass the filter or b) proportional to the “not match” cost times the number of nodes in the question.  We did implement a simple tighting strategy for which the ceiling gets higher (by modifying the proportional constant) as keyword expansion rises, in order to make sure no garbage gets through.
There are several reasons to integrate the relationships found by the parser with others, which somehow “spoil” the tree structure.  In cases like “Man first walked on the moon in 1969”, “1969” depends on “in”, which in turns depends on “moon” (as far as Minipar tells). By processing the output of the parser, we can establish that whenever two relevant nodes are linked by means of an irrelevant one, then there should be a relationship between the two terms.  This way, in the sentence above, we have a direct link between “moon” and “1969”.
6.1  The rules
We have tried a preliminar (as time lacked for a comprehensive study) analysis of questions and answers in order to add to the relations found in the question those which may appear in an answering sentence.  Such approach had to be conservative, so that no incorrect answer would show the same relations.  Sometimes, when telling correct from incorrect was not possible, we have made sure the incorrect case costed more to the matching procedure.
We have defined a set of rules which, basing on Minipar’s output and previously computed relations, establish whether there is a relation between nodes A and B (and relations are directed). The final set of relations is the closure of the empty set with respect to such rules, which are listed, and motivated, in the following.
Direct link
A and B are in relation if B is child of A in Minipar’s output, and the relation among them is the relation they have in the parse tree.
Conjunctions
Two conjuncted (tied by a conj) nodes have the same relations, therefore a node related by conj to another is put in relation with everything its father is in relation with.
This is to account for cases like “Jack and John love Mary”, in which, for Minipar, the only relation John has is that of being tied to Jack by a conjunction.  We add his loving of Mary to the relations.
Predicates
A and B are in relation if they are both child of a “to be” verb, the first with the role of subject, the second as predicate (which is the relation between them). This is because a question like “who is the Pope? ” is often answered by phrases such as “The Pope, John Paul II, ...” in which the answer does not goes through a “to be” verb.
Possession
A and B are in relation with the relation of genitive if A is the subject of a verb “to have” and B is the object.  To enable matching “John’s car” with “John has a car”.
Location
A and B are in inside relation if there is a subj-in relation among B and A (phrase of the form “A is in B”). To enable mathching “Paris is in France” with “Paris, France”.
Invertible relations
Some relations are invertible, so that A and B are in relation if B and A are in relation as either apposition or by the person relation.
Transitive relations
Similarly, some relations are transitive, so that if A and C and in one of those relations, and C is in relation to B, then A and C are. Such relations depend intimately from the parser and its way to parse, for instance, measures (such as “50 inches”).
Dates
Minipar will always attach a modifier like “in 1986” to the closest noun:  we felt it made sense to include a relation between the main verb (describing the action), and the date.
Empty nodes
Empty nodes represent implicit element of the sentence; Minipar is occasionally able to tell us to what actual word they refer to, so that we can add a relation between A and B if there is a relation between A and C, and C is an empty node referring to B (and dually for the first node in the relation).
The case of “not”
There is only one negative rule, with precedence over the others:  two nodes are not in relation if they both depend from a node which has a negative particle as a child.  This accounts for negative phrases like “John is not a policeman” not to cause the insertion of relations between, in the example, “John” and “policeman”
6.2  Finding a match
Suppose we have the following relations  in the question:  qr1 = (A, r1, B) and qr2 = (A, r3, C). Suppose also that the sentence we are considering brings the relations:  ar1 = (1, R1, 2), ar2 = (2, R2, 3) and ar3 = (1, R3, 3). We consider all matches between triples in the question and in the answer provided that no one node is put in correspondance with more than one node:  if we match qr1 with ar1, we cannot match qr2 with ar2, or node A in the question would have to match both nodes 1 and 2 in the answer.
All valid matches are considered and evaluated; the best scoring one is returned.
6.3  Costs
The way a cost is evaluated for a candidate answer with respect to the question is complex, and requires experimentation and fine tuning, which has not yed been completed.
The overall cost of the matching is the sum of 3 components:  
•	for each node to node assignment, a cost is computed by means of WNSense 
•	for each relation to relation assignment, a cost is paid if relations mismatch 
•	a cost is paid for each node in the question which was not matched. 
6.3.1  Node to node cost
The cost is obtained by means of WNSense, which takes care of smoothing out the different senses of the word (always according for the knowledge of the word as coming from ), and working out the “similarity” between the two words.
WNSense returns a value on a continuous scale from 0 to 1 representing the “degree of difference” between the words; such value is multiplied to a cost for node mismatch which is computed for each node in the question.
The mismatch cost for the nodes in the question depends on their role. A node identifying the type of the question (the node “instrument” in a previous example) may be missing in the answer, and has therefore a low cost.  Nodes which depends on other relevant nodes have half a mismatch cost than their father, as they provide specification which may be missing in a correct answer.  The mismatch cost is therefore a constant multiplied by a multiplier established for each node.
Additional costs are added to account for particular situations, such as when an extra specificity in the answer is really unwanted:  if the question is “Who was the first man in Space? ”, then an answer like “The first American in space was...” is really not wanted, contrary to a naive rule that wants a specific answer correct for a general question.
The type node is what puts the supposed answer in relation with the rest of the entities.  To account for the candidate answer to be acceptable, it is required that the type node finds a match (of the appropriate type) in the answering sentence.  Such requirements is simply implemented by making the cost for not matching the type node so high it makes the sentence unacceptable.
6.4  The threshold
When the cost of a sentence surpasses a threshold, it is discarded.  Such a threshold varies depending on the struction of the question and on the keyword expansion degree.
In general, a fixed cost is “allowed” for each node, mutiplied by the multiplier also used for their mismatch cost.
An additive component to the threshold is then added, which is inversionally proportional to the expansion degree.  This is so as to make sure the filter is tighter when broader recall is requested.
7.  Authoring answers
A module not yet developed at the time the output for the TREC was generated, verifying the “authority” of answers, has proven to be very effective.
All the answers returned are grouped by the node associated with the type node, which constitutes the actual, stripped answer.  Every such group is evaluated by the sum of all the answer costs over the square of the number of such answers.  Groups are sorted according to this measure, and the best scoring answer of each group is returned.
This simple mechanism gives a boost to frequent answers, and helps avoid answers which, although perfectly stated syncactically, are incorrect.
8.  Future work and directions
 was developed as a vertical application, from the bottom layer, indexer and search engine, up to question analysis and the more semantic filter.  Being such a big project, we somehow had to rush in order to meet this year’s TREC deadlines, and several parts of the system are left with considerable work to do.
We, of course, regard this as a positive thing in our system, for we have extremely large improvement margins.  A sketch of what can be done follows.
8.1  Text analysis tools
Some of our analysis tools, like  are fairly stable.  Others, like the named entity tagger or the stemmer, may need better tuning, in order to perform at their best.  For time constraints we have picked what was available “off the shelf”, and could not evaluate those systems intensively or accurately, so that they may need performance twitching, or even substituting.  As errors add up to each other, it is crucial that such basic components work at their best.
Similarly goes for Minipar; our evaluation of the parser was empirical, but the ability of Minipar to detect named entity taggers, and the particular set of relationships it identifies, and to which of course our system had to adapt, make it a harder component to substitute.
What can be done, however, is to account for the cases in which its parsing is “peculiar”, so as to work around certain idiosyncrasies.
Word sense disambiguation needs complete evaluation, and so does hyperonym, hyponym matching between words.  The heuristic deployed, which is crucial to the sentence matching, needs to be evaluated and, for misbehaviors which would be found, fixed and improved.
8.2  Question analysis
Question analysis can be improved very easily by adopting a more fine-grained taxonomy for expected answer type.  Such granularity would, however, have to be supported by the named entity tagger.
To add to this, better support needs to be given for the less direct questions, namely those in which the focus is not the subject of the phrase.
Not unrelated to this is perhaps the most crucial point of the question analysis we have performed:  the position of the type node.  For the system to come up with the correct answer, regardless of the filters, which all work sentence-wise, it is essential for the type node to be placed in the “correct” position.  The problem here is that there is no such notion of “correctness”, and a bit of experimentation has to be carried on (which has not been done very much in the present version of ). The position of the type node would be “correct” if the actual entity answering to the question would be in such a relationship with respect to the other words in the sentence.  A bit of general rules must therefore be identified to expent the present rather limited heuristic.
Keyword extraction/expansion would directly benefit from a better identification of the sense of a word, so that fewer, and more to the point, alternatives can be put in the query.
8.3  Filters
While little can be said about the type filter, whose effectiveness is proportianal to the granularity and the accuracy of the taxonomy, there is much work which can be performed on the relationship unification filter.
Apart from Minipar identified relationships, few others have been inserted, basing on experimental evidence.  We hope to abstract the meaning of a sentence by means of such relationships, and we therefore need more experimenting.  Such experimentation is clearly driven by the parser, as it is from its output that we figure out by what other relationships the same concept can be espressed as well.  It is important to note that, apart for particular figures of speech, such process is almost totally syntactical.  For instance, it is important to account for the difference between a passive and an active form, or, as it has been done already, for the way the predicate of a verb can be directly linked to the subject.
Once this has been, to an extent, accomplished, two other important tasks may be tackled, although they definitely require more effort. The first one is to take account of semantic to allow completely different sintactical expression to match.  At the present system level, it is impossible to match the sentence “John flew across the ocean” and “John completed a flight across the ocean” . This is due to the high cost of matching “completed” with “flew”, the system being unable to realize that “completing a flight” is not that far from “flying”.
The second large modification to be performed concerns the possibility of integraing the information coming from several sentences.  Such integration could be done by just considering the union of the relationships in all sentences, provided:  
•	coreference resolution is performed so as to be able to consider the same entities in different senteces as the same node, therefore putting the information the different sentences convey together; 
•	sentences which should be considered together are carefully selected:  the cost of the matching procedure is rather concerned with the number of relationships, and it is therefore crucial to only select the necessary sentences (as opposed to, for instance, collecting all the relationships from a document or even from the whole collection). 
The second of these problems may be tackled by selecting (from the same document, for coherency), those sentence whose are either adjacent or which contain the appropriate keywords.
References
[1]	 Free Software Foundation, GNU General Public Licence, http: //www.gnu.org/licenses/gpl.html 
[2]	 G. Attardi, A. Cisternino, Reflection support by means of template metaprogramming, Proceedings of Third International Conference on Generative and Component-Based Software Engineering, LNCS , Springer-Verlag, Berlin, 2001 
[3]	 A. Berger, S. Della Pietra, and M. Della Pietra, A Maximum Entropy Approach to Natural Language Processing, Computational Linguistics.  22(1),1996. 
[4]	 Grishman, R. and B. Sundheim, Design of the muc-6 evaluation, In NIST, editor, the Sixth MEssage Understanding Conference (MUC-6), Clumbia, MD. NIST, Morgan-Kauffmann Publisher, 1995. 
[5]	 Harabagiu, Moldovan et al., FALCON:  Boosting Knowledge for Answering Engines, TREC 2000 proceedings, 2000 
[6]	 J. B. Lovins, Development of a Stemming Algorithm, Mechanical Translations and Computational Linguistics, 11: 22-31, 1968 
[7]	 G. Miller, Five papers on WordNet, Special issue of International Lexicography 3(4), 1990 
[8]	 Montoyo, A. and Palomar M. Word Sense Disambiguation with Specification Marks in Unrestricted Texts, Proc 11 th International Workshop on Database and Expert Systems Application (DEXA 2000). 103-108, Greenwich, London, UK. 
[9]	 J. C. Reyner and A. Ratnaparkhi, A Maximum Entropy Approachg to Identify Sentence Boundaries, Computational Language, 1997