In this paper the methodology followed to build a question-answering system for the Portuguese language is described. The system has two modules: preliminary analysis of documents (information extraction) and query processing (information retrieval). The proposed approach is based on computational linguistic theories: syntactical analysis (constraint grammars); followed by semantic analysis using the discourse representation theory; and, finally, a semantic/pragmatic interpretation using ontologies and logical inference.
The system was evaluated under the CLEF'05 question and answering track with a collection of documents from two newspapers: Público (Portuguese) and Folha de São Paulo (Brazilian).
This paper describes an ongoing project at the Informatics Department of the University of Évora, Portugal, aiming to develop a question answering system for the Portuguese language.
The system has two modules: preliminary analysis of documents (information extraction) and query processing (information retrieval).
The analysis of the document collection and queries is done using models from computational linguistic theories. This processing includes: syntactical analysis of sentences using the constraint grammar Palavras [3]; semantical analysis using discourse representation theory [5]; and, finally, semantic/pragmatic interpretation using ontologies and logical inference.
Knowledge representation and ontologies are handled through the use of an extension to PRO-LOG, ISCO [1,2], which allows to integrate logic programming and external databases. In this way it is possible to solve scalability problems like the need to represent more than 10 millions of discourse entities.
The QA system, in order to satisfy CLEF requirements, should be able to answer queries in natural language, based on information conveyed by a collection of documents. The answer to a specific question is: a set of words and the identification of the document and sentence, which was used as the source of information. For instance, for the following question:
Who is John Lennon's widow?
Our system answers: Yoko Ono -document: publico/publico95/950807/001 -sentence: 2 At the moment, the system is able to answer questions about:
• Places:
Where is Régua?
• Dates: When was Mr. X arrested?
• Definitions:
What is ONU?
• Specific: How many times was Mr. X accused of being a drug dealer? What crimes as Mr. Y committed? However, the system can also be used to improve other information retrieval tasks:
• Improve the performance of information retrieval systems, helping to obtain the set of relevant documents.
Given a query, the system can be used to retrieve all documents having a sentence which verifies the query.
For the question "Who is John Lennon's widow" our system is able to retrieve all documents having a sentence which verifies the following term:
∃X, Y : widow(X, Y ), name(X, John Lennon )
• Help to structure documents in a semi-automatic way.
The system is able to extract facts from the documents and to give them a structure (accordingly with an ontology).
The proposed system is an evolution of a previous system evaluated at CLEF 2004 [7]. Some of the existing problems were solved, namely, the need to use a pre-processing information retrieval engine to decrease the complexity of the problem. In this CLEF edition, we were able to solve this major scalability problem via the use of ISCO and its power to connect PROLOG and relational databases.
However, the pre-processing of the collection of documents took more time than we expected and we were not able to answer questions to the Folha de S. Paulo newspaper. As we will point out in the evaluation section this was our major problem and it is the reason why our results didn't improve from CLEF04 to CLEF05.
In the next section the architecture of the system is described. In sections 3 and 4 the syntactical and the semantical modules are described in detail. Section 5 presents the knowledge representation approach. Section 6 describes the semantic-pragmatic interpretation of the documents, based on the previous analysis and on the ontology. Section 7 shows the processing of a query and the generation of the correspondent answer. In section 8 the evaluation results are presented. Finally, in section 9 some conclusions and future work are discussed. The QA system has two main modules:
This module extracts information from the documents and it creates a knowledge base.
The module, see figure 1, is composed by several sub-modules:
-Syntactical analysis: sentences are processed with the Palavras [3] parser.
After this phase, a new collection of documents (with the parsing result) is obtained.
-Semantic analysis: the new collection of sentences in rewritten [5] creating another collection, where each document has a DRS (structure for the discourse representation), a list of discourse referents and a set of conditions.
-Semantic and pragmatic interpretation: in this phase the previous collection of documents is processed, taking into account an ontology and, as a result, a knowledge base is built. This knowledge base contains instances of the ontology.
This module processes the query and it generates the answer: a set of words and the identification of the document and sentence where the answer was found. -Syntactical analysis: using the parser Palavras [3].
-Semantic analysis: from the parser output, a discourse structure is built, a DRS [5] with the correspondent referents.
-Semantic/Pragmatic interpretation: in this phase, some conditions are rewritten, taking into account the ontology, and generating a new DRS.
-Query Processing: the final query representation is interpreted in the knowledge base through the unification of the discourse entities of the query with documents discourse entities (see section 7).
In the next sections these sub-modules are described in more detail.
Syntactical analysis is obtained through the use of the PALAVRAS parser from Eckhard Bick [3], developed in the context of the VISL 1 project at the University of Southern Denmark. This parser gives good morpho-syntactical information and it has a god coverage of the Portuguese language. For instance, in our system the verb lemma (infinitive form) is used as the name of the predicates in the semantic analysis.
As an example, consider the following sentence (3.1):
Um patologista defendeu que Jimi Hendrix morreu de asfixia após ter ingerido álcool e uma dose excessiva de barbitúricos. (3.1)
"A pathologist argued that Jimi Hendrix died of asphyxia after drinking alcoholic beverages and an excessive dose of barbiturics".
The syntactical structure of this sentence is the following:
The semantic analysis rewrites the syntactical structure in to a discourse representation structure [5], DRS. At present, we only deal with factual sentences, i.e., sentences with existential quantification over the discourse entities. So, our discourse structures are sets of referents, existentially quantified variables, and sets of conditions, first order predicates.
Each syntactical tree, represented in Prolog, is rewritten accordingly with a set of rules and integrated in a DRS.
In order to allow alternative interpretations, the link between prepositional phrases in done using the relation rel with 3 arguments, the preposition and two discourse entities. This predicate rel allows the semantic/pragmatic interpretation to infer the adequate connection between the referents. For instance, the sentence 'O dono do cão'/'The owner of the dog', is represented by the following DRS: drs( entities:[ A:(def, male, sing), B:(def, male, sing)], conditions:[owner(A), dog(B), rel(of,A,B)] )
As it can be seen in the next section, this representation allows the semantic/pragmatic interpretation to rewrite the DRS, obtaining the following structure: This representation is obtained because "Como/How" is interpreted as "de que/of what". In the semantic-pragmatic interpretation and in the query processing phase, the structure (4.1) might unify with sentence (3.1) and we may obtain the following answer: "Jimi Hendrix died of asphyxia".
In order to represent the ontology and the extracted facts, we use an extension to logic programming, ISCO [1,2], which allows Prolog to access databases. This technology is fundamental to our system because we have a very large database of referents: more than 9 millions only for the Público newspaper.
Databases are defined in ISCO from ontologies. Our system uses two different ontologies:
• one ontology built by us aiming to model common knowledge, such as, geography (mainly places), and dates;
This kind of knowledge is important to correctly extract facts from the documents and to be able to answer questions about places. The ontology defines places (cities, countries, . . . ) and relations between places.
• one ontology generated automatically from the document collection [9,8];
This ontology, although being very simple, allows the representation of the domain knowledge.
The ontology can be defined directly in ISCO or in OWL (Ontology Web Language) and transformed in ISCO [8].
The knowledge extraction module identifies facts (instances of an ontology classes) and inserts them as rows in a database table.
For instance, sentence (3.1), with semantic representation in page 7, would generate several tuples in the database. First order logical expressions are skolemized, i.e., each variable existentially quantified is replaced by a different identifier:
In the document processing phase, our system uses the first sentence interpretation (note that for each sentence there might exist several distinct interpretations). This is caused by temporal and spacial complexity problems but it does not seem to decrease much the performance of the system. Nevertheless, additional measures should be done in order to fully evaluate the impact of this option.
Additionally, we also add information in the database linking referents with the documents and sentences were they appeared. For instance the tuple (123,'publico/publico95/950605/005',4) would be added to table referred in.
Semantic/pragmatic interpretation tries to reinterpret semantical information, taking into account the considered ontology.
This process receives as input a discourse representation structure, DRS, and it interprets it using rules obtained from the knowledge ontology and the information in the database.
In order to obtain a good interpretation, our strategy is to search for the best explanation that supports the sentence logical form. This strategy for pragmatic interpretation was initially proposed by [4].
The knowledge base for the pragmatic interpretation is built from the ontology description in ISCO. The inference in the knowledge base uses abduction and finite domain constraint solvers.
Suppose the following sentence:
"A. conduz com uma taxa de alcoolemia de 2.15." "A. drives with an alcoholic rate of 2.15.".
which, by the semantic analysis, is transformed into the following structure: one DRS, four discourse referents, and a set of conditions: drs( entities:[A:(def,male,sing), B:(indef,fem,sing), C:(indef,fem,sing), D:(def,male,sing)] conditions:[name(A, 'A.'), drive(A), rel(with,A,B),
The semantic/pragmatic interpretation process, using information from the ontology, will rewrite the DRS into the following one: drs( entities:[A:(def,male,sing), B:(def,male,sing)] conditions:[name(A, 'A.'), person(A), drive(A,_,_,_,B), alcohol\_rate(B,2,15)] )
The interpretation of rel(with,A,B) as drive( A, , , ,B) is possible because the ontology has a class drive, which relates persons driving in a time interval with a alcoholic rate in blood.
One of the major problems of this phase is to correctly identify the distinct referents in the documents. It is important to use the same skolem constant to identify the same referent but, in any situation, different individuals should have the same identifier (skolem constant).
The generation of the answer is done in two steps:
1. identification of the database referent that unifies with the referent of the interrogative pronoun in the question.
2. retrieval of the referent properties and generation of the answer.
In order to illustrate this process, suppose the following question:
"Quem cometeu um homicídio por conduzir alcoolizado?" "Who committed an homicide because he/she was driving drunk?"
This question is represent by the following DRS, after syntactical and semantical analysis:
drs( entities:[A:(who,male/fem,sing), B:(indef,male,sing), C:(indef,male,sing)], conditions:[committed(A,B), homicide(B), rel(because,A,C), drunk(C), drive(C)] )
The semantic/pragmatic interpretation of this question is done using the ontology of concepts and it allows to obtain the following DRS: drs( entities:[A:(who,male/fem,sing), B:(indef,male/fem,sing/plu), C:(def,fem,sing), conditions:[homicide(A,B), person(A), person(B), drive(A,_,_,_,C), alcohol\_rate(C),C>0.5] )
• In order to perform the first step of the answer generation:
We keep the referent variables of the question and we try to prove the conditions of the DRS in the knowledge base. If the conditions can be satisfied in the knowledge base, the discourse referents are unified with the identifiers (skolem constants) of the individuals.
• The next step is to retrieve the words that constitute the answer:
In this phase we should retrieve the conditions about the identified referent A and choose which ones better characterize the entity. Our first option is to choose a condition with the predicate name (name(A,Name)). However, it is not always simple to find the adequate answer to a question. See, for instance, the following questions:
-What crimes committed X? -How many habitants has Kalininegrado?
-What is the nationality of Miss Universe? -Who is Flavio Briatore?
In order to choose the best answer to a question our systems has an algorithm which takes into account the syntactical category of the words that may appear in the answer and it tries to avoid answers with words that appear in the question.
Questions about places or dates have a special treatment involving the access to a database of places or dates.
Note that several answers may exist for a specific question. In CLEF05 we decided to calculate all possible answers and to choose the most frequent one.
CLEF05 also imposes that the answer is supported by a single sentence in a specific document. Our system is able to obtain answers with conditions in several documents but we constrained the system to obtain only answers with referents introduced in the same sentence (predicate referred in allows to obtain that information -see page 8).
The evaluation of our system was performed in the context of CLEF -Cross Language Evaluation Forum -2005. In this forum a set (200) of questions is elaborated by a jury and given to the system. The system's answers are, then, evaluated by the same jury.
Our system had the following results:
• 25% of correct answers (50 answers).
• 1.5% correct but unsupported answers (3 answers).
• 11% inexact answers -too many (or too few) words (22 answers).
• 62.5% wrong answers (125 answers).
The system had 125 wrong answers, but it is important to point out that 105 of these wrong answers were NIL answers, i.e., situations were the system was not able to find any answer to the questions. So, only in 10% of the situations (20 answers) our system gave a really wrong answer.
The major problem with the remaining 105 no-answers is the fact that, due to time constraints we were not able to process the collection of documents from the Folha de S. Paulo newspaper. At present, we do not know how many of these no-answers would be answered by this collection, but we expect our results to improve significatively.
A preliminary analysis of the other incorrect answers showed that the main cause of problems in our system is related with lack of knowledge: wrong syntactical analysis; lack of synonyms; and, mostly, an incomplete ontology. In fact, most problems are related with incorrect pragmatic analysis due to an incomplete ontology.
However, and taking into account that our answers were computed using only one collection of documents (the Público newspaper), and comparing with the CLEF2004 results, we believe our system produced good and promising results. In fact, it showed to have a quite good precision on the non NIL answers: only 10% of these answers were wrong.
We propose an architecture for a question answering system for the Portuguese language.
Our system uses natural language processing techniques to create a knowledge base with the information conveyed by documents. Queries are analysed by the same tools and logical inferences over the knowledge base are performed, trying to find an adequated answer. The inference process is performed using a logic programming framework and the Prolog inference engine.
The system main problems are related with errors in the several NLP tools and with the lack of coverage of the ontology.
At present, we are re-evaluating our system using a knowledge base with the two newspaper collection. We expect our results to improve significatively.
As future work, we intend to explore the problem of automatically build ontologies. The improvement of the used NLP tools is another area needing much work. We also intend to handle anaphoric relations in the documents, allowing the reduction of the number of distinct referents.