We describe Joost, our QA system for Dutch, which makes extensive use of dependency relations. We analyzed the full Dutch CLEF QA corpus syntactically and mined it o -line for information that may be useful for QA. Joost answers questions either by table look-up, or by searching for answers in paragraphs returned by an IR engine. In both cases, dependency relations are used to identify and rank potential answers.
2.1
This research was carried out as part of the research program for Interactive Multimedia Information Extraction, imix, nanced by nwo, the Dutch Organisation for Scienti c Research. consists of over 500 grammar rules (de ned using inheritance) and a large and detailed lexicon (over 100.000 lexemes). To ensure coverage, heuristics have been implemented to deal with unknown words and ungrammatical or out-of-coverage sentences (which may nevertheless contain fragments that are analyzable). The grammar provides a 'deep' level of syntactic analysis, in which whmovement, raising and control, and the Dutch verb cluster (which may give rise to 'crossing dependencies') are given a principled treatment. The output of the system is a dependency graph, compatible with the annotation guidelines of the Corpus of Spoken Dutch.
A left-corner chart parser is used to create the parse forest for a given input string. A manually
corrected treebank of 140.000 words was used to train a maximum entropy disambiguation model.
Beam-search is used as a heuristic to extract the most probable parse from the parse forest e
eciently.
A second extension of the system for QA, was the inclusion of a Named Entity Classi er. The Alpino system already includes heuristics for recognizing proper names. Thus, the classi er needs to classify strings which have been assigned a name part of speech by grammatical analysis, as being of the subtype per, org, geo or misc.1 To this end, we collected lists of person names (120K), geographical names (12K), organization names (26k), and miscalleneous items (2K). The data are primarily extracted from the Twente News Corpus, a collection of over 300 million words of newspaper text, which comes with annotation for the names of people, organizations, and locations, involved in a particular news story. For unknown names, a maximum entropy classi er was trained, using the Dutch part of the shared task for conll 2003.2 The accuracy on unseen conll data of the resulting classi er (which combines dictionary look-up and a maximum entropy classi er) is 88.2%.
To this end, the text collection was tokenized (into 78 million words) and segmented into (4.1 million) sentences. Parsing this amount of text takes well over 500 CPU days. We used a Beowulf Linux cluster of 128 Pentium 4 processors3 to complete the process in about three weeks. The dependency trees are stored as (25 Gb of) XML. 2.2
Several researchers have attempted to use syntactic information, and especially dependency
relations, in QA. One approach is to look for an exact match between dependency tuples derived
from the question and those present in a potential answer
We have implemented a system in which dependency patterns derived from the question must be matched by equivalent dependency relations in a potential answer. The dependency analysis of a sentence gives rise to a set of dependency relations of the form hHead/HIx, Rel, Dep/DIxi, where Head is the root form of the head of the relation, and Dep is the head of the constituent that is the dependent. Hix and DIx are string indices, which distinguish repeated occurrences of the same token in a string, and Rel is the name of the dependency relation. For instance, the dependency analysis of sentence (1-a) is (1-b). (1)
Mengistu kreeg asiel in Zimbabwe (Mengistu was given asylum in Zimbabwe) hkrijg/2, su, mengistu/1i; hkrijg/2, obj1, asiel/3i; hkrijg/2, mod, in/4i; hin/4, obj1, zimbabwe/5i A dependency pattern is a set of (partially underspeci ed) dependency relations: 1Various other entities which sometimes are dealt with by NEC, such as dates and measure phrases, can be identi ed using the information present in POS tags and dependency labels.
2http://cnts.uia.ac.be/conll2003/ner/ 3which is part of the High-Performance Computing centre of the University of Groningen (2)
hkrijg/K, obj1, asiel/Ai; hkrijg/K, su, Su/Si A pattern may contain variables, represented here by (words starting with) a capital. A pattern P matches a set of dependency relations R if P R, under some substitution of variables. The pattern in (2) matches with the set in (1-b), instantiating Su as mengistu.
Equivalences can be de ned to account for the fact that in some cases we want a pattern to match a set of dependency relations that slightly di ers from it, but nevertheless expresses the same semantic relation. For instance, the subject of an active sentence may be expressed as a PP-modi er headed by door (by) in the passive: (3)
Zimbabwe verleende asiel aan Mengistu (Zimbabwe gave asylum to Mengistu) Aan Mengistu werd asiel verleend door Zimbabwe (Mengistu was given asylum by Zimbabwe)
fhVb/V,su,Su/Sig ,
hword/W,vc,Vb/Vi; hVb/V,mod,door/Di; hdoor/D,obj1,Su/Si Here, the verb word is (the root form of) the passive auxiliary, which takes a verbal complement headed by the verb Vb.
Given an equivalence Lhs , Rhs, a pattern P containing Lhs is equivalent to a pattern P 0, which is identical to P , except that Lhs has been replaced by Rhs. A pattern P now also matches with a set of relations R if there is some equivalent pattern P 0, and P 0 is a subset of R, under some substitution of variables.
We have implemented 13 additional equivalence rules, to account for, among others, word
order variation within appostions, the equivalence of genitives and van-PPs, equivalence between
appositions and simple predicative sentence, coordination, and relative clauses. The equivalence
rules we have implemented so far express linguistic equivalences, and thus are both general and
domain independent. In Bouma, Mur, and
O -line methods have proven to be very e ective in QA
Jijkoun, Mur, and de Rijke (2004) show that extraction patterns de ned in terms of dependency relations are more e ective than regular expression patterns over surface strings. Following this observation, we used the module for dependency pattern matching to exhaustively search the parsed corpus for potential answers to frequently occurring question types. For instance, the pattern in (4) extracts information about organizations and their founders. (4)
hricht op/R, su, Founder/Si; hricht op/R, obj1, Founded/Oi The verb oprichten (to found) can take on a wide variety of forms (active, with the particle op split from the root, participle, and in nitival, either the founder or the organization can be the rst constituent in the sentence, in passives the founder may be part of a door (by) phrase, and in control constructions the founder may be found as the subject of a governing clause. In all cases, modi ers may intervene between the relevant constituents: (5) a.
Minderop richtte de Tros op toen .... (Minderop founded the Tros when...)
Function Inhabitants Nobel Prize
Kasparov heeft een nieuwe Russische Schaakbond opgericht en... (Kasparov has founded a new Russian Chess Union and...) ... toen de Generale Bank bekend maakte met de Belgische Post een "postbank" op te richten. (when the General Bank announced to found a \postal bank" with the Belgian Mail).
Such variation is almost impossible to capture accurately using regular expressions, whereas dependency relations can exploit the fact that in allmost all cases the organization and its founder can be identi ed as the object and subject of the verb with the root form oprichten. The pattern in (4) su ces to extract this relation from all of the examples above.
Equivalence rules can be used to deal with other forms of syntactic variation. For instance, once we de ne a pattern to extract the country and its capital from (6-a), the equivalence rules can be used to match this pattern against the alternative formulations in (6-b)- (6-d) as well. (6)
de hoofdstad van Afghanistan, Kabul (the capital of Afghanistan, Kabul) Kabul, de hoofdstad van Afghanistan (Kabul, the capital of Afghanistan) Afghanistans hoofdstad, Kabul (Afghanistan's capital, Kabul)
Kabul is de hoofdstad van Afghanistan (Kabul is the capital of Afghanistan) Of course, the same holds for all other relations that are extracted o -line, and thus, the development e ort per relation decreases, while recall typically increases.
Table 1 lists all the relations we extracted. Each second and third column list the overall number of extracted tuples and extracted unique tuples (types) respectively. 2.4
Fine-grained named entity classi cation is useful for answering wh-questions and de nition
questions. Both
From the fully parsed Dutch CLEF text collection, we extracted 295 unique apposition tuples,
consisting of a noun (used as class label) and a named entity. The resulting table contains, for
instance, 112 names of ferry boats (Estonia, Anna Maria Lauro, Sally Star etc.) and no less
than 2951 national team coaches (Bobby Robson, Jack Charlton, Menotti, Berti Vogts etc.). By
focussing on the most frequent label for a named entity, most of the noise can be discarded. For
instance, Guus Hiddink occurs 17 times in the extracted apposition tuples, 5 times as bondscoach
(national team chef), and once with various other labels (boss, colleague, guest, newcomer, ...).
In van der Plas and
In this section, we describe the components of our QA system, Joost. Questions are analyzed and assigned a question class. If the class corresponds to a relation for which information has been extracted o -line, answers and corresponding document id's are retrieved from the relevant relation table. Otherwise, Information Retrieval is used to nd paragraphs relevant to the question. Linguistic techniques are used to extract potential answers from these paragraphs. Potential answers are ranked on the basis of a score which combines, among others, IR-score, frequency of the answer, and the amount of overlap in dependency relations between question and the sentence from which the answer was extracted. 3.1
Question analysis is the task of assigning a speci c class (person, location, date, ...) to a question. Syntactic analysis helps to determine the question stem in complex wh-phrases (With which Palestinian organization...) and can help to identify additional properties of the question (i.e. Give the name of a Japanese city that was struck by an earthquake asks for the name of a city, not of an earthquake). Lexical semantic knowledge is required to recognize that Which region in the US has ... asks for a geographical named entity, whereas Which car factory was bought by ... asks for an organizational named entity.
Each incoming question is parsed by Alpino. To improve parsing accuracy on this speci c task, the disambiguation model was retrained on a corpus which contained annotated and manually corrected dependency trees for 650 quiz questions.4 The retrained model achieves an accuracy of 92.7% and 88.3% on the CLEF 2003 and 2004 questions, respectively. For CLEF 2005, we used a model which was trained on data which also included (manually corrected dependency trees of) the CLEF 2003 and 2004 questions. It achieved an accuracy of 97.6 on CLEF 2005 questions.
On the basis of the dependency relations returned by the parser the question class is determined. Joost distinguishes between 29 di erent question classes. 18 question classes are related to the relation tuples that were extracted o -line. Note that a single relation can often be questioned in di erent ways. For instance, whereas a frequent question type asks for the meaning of an acronym (What does the abbreviation RSI stand for?), a less frequent type asks for the abbreviation of a given term (What is the abbreviation of Mad Cow Disease?). The other 11 question classes identify questions asking for an amount, the date or location of an event, the ( rst) name of a person, the name of an organization, how-questions, wh-questions, and de nition questions.
For each question class, one or more syntactic patterns are de ned. For instance, the following pattern accounts for questions asking for the capital of a country: (7) hwat/W, wh, is/Ii; his/I, su, hoofdstad/Hi hhoofdstad/H, mod, van/Vi; hvan/V, obj1, Country/Ci Depending on the question class, it is useful to identify one or two additional arguments . For instance, the dependency relations assigned to the question Wat is de hoofdstad van Togo? (What is the capital of Togo?) match with the pattern in (7), and instantiate Country as Togo. Therefore, the question class capital is assigned, with Togo as additional argument. Similarly, Who is the king of Norway? is classi ed as function(king,Norway), and In which year did the Islamic revolution in Iran start? is classi ed as date(revolution).
Some question classes require access to lexical semantic knowledge. For instance, to determine
that In which American state is Iron Mountain? asks for a location, the systeem needs to know that
state refers to a location, and to determine that Who is the advisor of Yasser Arafat? should be
classifed as function(advisor,Yasser Arafat), it needs to know that advisor is a function. We
obtained such knowledge mainly from Dutch EuroWordNet (Vossen, 1998). The list of function
words (indicating function roles such as president, queen, captain, secretary-general, etc.) was
4From the Winkler Prins spel, a quiz game. The material was made available to us by the publisher, Het
Spectrum, bv.
expanded semi-automatically with words from the corpus that were distributionally similar to
those extracted from EWN (see van der Plas and
Question classi cation was very accurate for the CLEF 2005 questions. There were a few cases where the additional arguments selected by the system did not seem the most optimal choice. Two clear mistakes were found (e.g. What is the currency of Peru? was classi ed as currency(of) and not as currency(Peru)). 3.2
For questions which cannot be answered by the relation tables, traditional keyword-based information retrieval (IR) is used to narrow down the search space for the linguistically informed part of the QA system which identi es answers. On the basis of keywords from the question, the IR system retrieves relevant passages from the corpus.
Keywords are derived from the question using its content words. Function words and other
irrelevant words are removed using a static stop word list. We implemented an interface to seven
publicly available IR engines
Earlier experiments have shown that a segmentation into paragraphs is most e cient for IR performance in QA. We used the existing markup in the corpus to determine the paragraph boundaries. This resulted in about 1.1 million paragraphs (including headers that have been marked as paragraphs). We did experiments with additional pre-processing, e.g., including proper lemmatization (using Alpino root forms) but we could not improve the IR performance compared to the baseline using standard settings. However, we did include labels of named entities found by Alpino in each paragraph as additional tokens. This makes it possible to search for paragraphs including certain types of named entities (e.g. location names and organizations) and special units (e.g. measure names and temporal expressions) corresponding to question types found by the question analyses component.
For CLEF, Zettair returns the 40 most relevant paragraphs given a query. For the QA@CLEF 2003 data, this gives a recall of 75%. 3.3
For questions that are answered by means of table look-up, the relation table provides an exact answer string. For other questions, it is necessary to extract answer strings from the set of paragraphs returned by IR. Given a set of paragraph id's, we retrieve from the parsed corpus the dependency relations for the sentences occurring in these paragraphs.
Various syntactic patterns are de ned for (exact) answer identi cation. For questions asking for the name of a person, organization, or location, or for an amount or date, a constituent headed by a word with the appropriate named entity class has to be found. As all of these occur frequently in the corpus, usually many potential answers will be identi ed. An important task is therefore to rank potential answers.
The following features are used to determine the score of a short answer A extracted from sentence S:
Syntactic Similarity The proportion of dependency relations from the question which match with dependency relations in S.
Names The proportion of proper names, nouns, and adjectives from the query which can be found in S and the sentence preceding S.
IR The score assigned to the paragraph from which A was extracted.
The score for syntactic similarity implements a preference for answers from sentences with a syntactic structure that overlaps with that of the question. Answer context implements a preference for answers that occur in the context of certain terms from the question. Given a question classi ed as date(Event), for instance, date expressions which occur as a modi er of Event are preferred over date expressions occurring as sisters of Event, which in turn are preferred over dates which have no syntactic relation to Event.
The overall score for an answer is the weighted sum of these features. Weights were determined manually using previous CLEF data for tuning. The highest weights are used for Syntactic Similarity and Answer Context. The highest scoring answer is returned as the answer.
Ranking of answers on the basis of various features was initially developed for IR-based QA only. Answers found by table look-up were ranked only by frequency. Recently, we have started to use the scoring mechanism described above also for answers stemming from table look-up. As the tables contain pointers to the sentence from which a tuple was extracted, we can easily go back to the full sentence, and apply the scoring mechanisms described above.5 Using more features to rank an answer provides a way to give the correct answer to questions like Who is the German minister of Economy?. The function table contains several names for German ministers, but does not distinguish between di erent departments. The most frequent candidate is Klaus Kinkel (54 entries), who is minister of foreign a airs. The correct name, Gunter Rexrodt, occurs only 11 times. Using Syntactic Similarity and Names as an additional features, Joost manages to give the correct answer. 3.4
Temporally Restricted Questions. The CLEF 2005 test set contained a number of questions which were temporally restricted: (8)
Who was the mayor of Moscow in 1994? The temporal information in these questions was treated similarly to all other information in the question, and we did not try to implement techniques which deal speci cally with temporal restrictions. The mechanism for scoring potential answers takes into account the syntactic similarity and the overlap in names (including date expressions) between question and answer sentence, and this implements a preference for answers which are extracted from contexts referring to the correct date. Note that, as the same scoring technique is used for answers found by table look-up, this strategy should also be able to nd the correct answer for questions such as (8-b), for which the function table might contain more than one answer.
Which-questions. General wh-questions, such as (9), are relatively di cult to answer. Whereas for most question types, the type of the answer is relatively clear (i.e. it should the name of a person or organization, or a date, etc.), this is not the case for wh-questions. (9)
Which ferry sank southeast of the island Uto? To improve the performance of our system on such questions, we make use of two additional knowledge sources. From EuroWordNet, we imported all hypernym relations between nouns. Question (9-a) is assigned the question class which(fruit). We use the hypernym relations to assign a higher score to answers which are hypernyms of fruit.6
As EuroWordNet does hardly include proper names, we also used the isa-relations extracted from appositions containing a named entity, as described in section 2.4. Question (9-b) is assigned 5As no IR is involved in this case, the IR score is set to 1 for all answers.
6Unfortunately, EuroWordNet only contains two hypernyms for the synset fruit, none of which could be used to identify an answer to (9-a).
Temporally Restricted Factoid De nition Overall the question class which(ferry). Candidate answers that are selected by Joost are: Tallinn, Estonia, Raimo Tiilikainen etc. Since, according to our apposition database, Estonia is the only potential answer which isa ferry, this answer is selected.
De nition Questions. An important category in CLEF 2005 are questions asking for the de nition of a person or organization (i.e. What is Sabena?, Who is Antonio Matarese?). No less than 60 questions were of this type. Again, we used the isa-relations extracted from appositions to answer such questions. More in particular, our strategy for answering de nition questions consisted of two phases:
Phase 2: The sentences which mention the named entity and the class are retrieved and searched for additional information which might be relevant. Snippets of information that are in a adjectival relation or which are a prepositional complement to the class label are selected.
Frequency is important to ensure that an appropriate class is chosen. The named entity Sabena, for instance, occurs frequently in the corpus, but often with class labels assigned to it, which are not suitable for inclusion in a de nition (possibility, partner, company,,.... By focussing on the most frequent class label assigned to a named entity (airline company in this case), we hope to select the most appropriate label for a de nition. A disadvantage of this technique is that the class label by itself is not always su cient for an adequate de nition. Therefore, we expand the class labels with modi ers which typically need to be included in a de nition. For the question What is Sabena?, our system produces Belgian airline company as answer. 4
The results of the CLEF evaluation are given in table 2. The scores are satisfactory for factoid questions and de nitions. It is unclear to us at the moment what the explanation is for the fact that the system performed less well on temporally restricted questions.
Of the 140 factoid questions, 46 questions were assigned a type corresponding to a relation table. For 35 of these questions, an answer was actually found in one of the tables. The other 11 questions were answered by using the IR-based strategy as fall-back. 52 of the 60 de nition questions were answered by the strategy described in section 3.4. For the other de nition questions, the general IR-based strategy was used as fall-back. Three de nition questions received nil as an answer.
Parsing errors are the cause of some wrong or incomplete answers. The question Who is Javier Solana?, for instance, is answered with Foreign A airs, which is extracted from a sentence containing the phrase Oud-minister van buitenlandse zaken Javier Solana (Ex-minister of foreign a airs, Javier Solana). Here, Javier Solana was erroneously analyzed as an apposition of a airs. Similarly, the wrong answer United Nations for the question What is UNEP?, which was extracted from a sentence containing the environment programme of the United Nations (UNEP), which contained the same attachment mistake.
A frequent cause of errors were answers that were echoing (part of) the question. Currently, the system only lters answers which are a literal substring of the question. This strategy fails in cases like: (10)
Q: In which city does one nd the famous Piazza dei Miracoli? A: at the Piazza dei Miracoli
Q: In which American state is Iron Mountain located? A: The United States. It seems cases like (10-a) and (10-b) could be easily ltered as well. Cases like (10-c) are harder, as they involve two (near) synonyms. Note nally that not all answers which overlap with the question should be ltered, as the answer in (11) is valid, eventhough the word rocket also occurs in the question. (11)
Q: What is the name of the rocket used to launch the satellite Clementine? A: Titan rocket Our strategy for answering de nition questions seemed to work reasonably well, although it did produce a relatively large number of inexact answers (of the 18 answers that were judged inexact, 13 were answers to de nition questions). As we explained in section 3.4, this is due to the fact that we select the most frequent class label for a named entity, and only expand this label with adjectival and pp modi ers that are adjacent to the class label (a noun) in the corresponding sentence. Given the constituent the museum Hermitage in St Petersburg, this strategy fails to include in St Petersburg, for instance. We did not include relative clause modi ers, as these tend to contain information which is not appropriate for a de nition. However, for the question, Who is Iqbal Masih, this leads the system to answer twelve year old boy, extracted from the constituent twelve year old boy, who fought against child labour and was shot sunday in his home town Muritke. Here, at least the rst conjunct of the relative clause should have been included. Similarly, we did not include purpose clauses, which leads the system to respond large scale American attempt to the question what was the Manhattan project, instead of large scale American attempt to develop the rst (that is, before the Germans) atomic bomb. 5
We have shown that dependency parsing of both questions and the full document collection is useful for developing an adequate QA system. Dependency patterns can be used to search the corpus exhaustively for answers to frequent question types and for class labels for named entities, which are used to improve the performance of the system on which-questions and de nition questions. Selection of the most likely answer to a question uses a syntactic similarity metric based on dependency relations.
We have used a limited number of equivalences over dependency relations. An obvious next
step is to expand this set with equivalences derived automatically from the parsed corpus (i.e. as
in
Vossen, P. 1998. Eurowordnet a multilingual database with lexical semantic networks.