This paper describes our participation in the QA4MRE 2011 task, targeted at reading comprehension tests and multiple choice question answering. Our system constructs a co-occurrence graph with words that are common or proper nouns and verbs extracted from each document. The documents are pre-selected through an information retrieval process for recovering only those that are most relevant to a particular question. An algorithm to detect communities of words with signi cant co-occurrence is applied to the co-occurrence graph. Each of the detected communities are treated as di erent contexts of a question in the corpus, and these contexts are used to nd the most suitable answer. Our evaluation results suggest that, the number of retrieved documents is an important factor in the results.
Participants are provided with questions from three topics. Associated with each topic, a reference corpus is available consisting of about 30,000 un-annotated documents related to the topic. Documents in the corpus are used to acquire the background knowledge needed to answer a test on the topic.
Each topic is composed by several tests and each test consists of one single document and a set of multiple choice questions having ve options each. Participants have the option of not answering the question or to answer the question by choosing one answer in each case. Our approach makes some assumptions that will be tested in the following sections, namely: 1. The documents included in the reference collection deal with issues related the topic they are associated. 2. It is possible to nd enough information in the Web to compile a background knowledge similar to that provided by organizers. 3. There may be a vocabulary gap between the questions and the answers, so the document from the test and the background can be used to bridge this gap. 4. It is better not to answer a question whose answer is uncertain than to provide a wrong answer. 5. Documents translated to di erent languages tend to contain redundant information. This assumption avoids the management of multilingual texts that would require additional processing time and linguistic resources. 3
In this section we present the system developed for the QA4MRE 2011 task. Our graph-based approach is speci cally designed to build a co-occurrence graph and uses the detected communities to nd the correct answer to each question proposed. 3.1
The background knowledge on which we work in this paper is a reference corpus consisting of about 30,000 un-annotated documents related to the topic.
Corpus preprocessing aims to create a structure of documents where every word is marked up as corresponding to a particular part of speech. All documents are lemmatised and PoS tagged using the GENIA tagger 1. Instead of using all words to construct the graph, only nouns and verbs are used, since they are more discriminative than adverbs and adjectives. Accordingly, only nouns and verbs are kept and lemmatised. 3.2
We consider a document to be a coherent piece of meaning, so that it is natural to make the basic assumption that all words appearing in the same document 1 www-tsujii.is.s.u-tokyo.ac.jp/GENIA/tagger share a common meaning. Our aim is to create a link joining every two words sharing a common meaning, so co-occurrence in the same document will be taken as a proxy for this.
In order to construct the graph our algorithm extracts from each document the words that are common or proper nouns and verbs. The rest of the words are considered too common to discriminate the meaning.
The extracted words are then applied a stemming process, reducing them to
their stem with the aim of increasing the signi cance of the number of
occurrences. This is done applying the Porter algorithm [
The weighted graph we have built contains the relationships between di erent words in the corpus. We apply an algorithm to detect communities of words with signi cant co-occurrence.
We have used the WalkTrap [
The algorithm starts from a partition of the graph into n communities corresponding to the vertices and merges communities in order to optimize a function called modularity which measures the quality of a partition. Distances between all adjacent vertices are computed and this partition evolves by means of an iterative process. Each iteration de nes a community merging which gives a hierarchical structure of communities called dendrogram. The algorithm merges the di erent communities taking into account the distances between adjacent vertices. The quality of the communities generated at each step is used to choose the optimal partition. 3.4
Each of the detected communities are treated as di erent contexts of a question in the corpus. In this way, the text of the question is assigned to a community and that community is considered the context of the question.
Each question is assigned to a community based on their similarity. The similarity between a question and each community is the co-occurrence of words in the text of the question and the community.
In the case of the answers the process is similar. First, each response is assigned to a community. Then, the response that has the highest similarity to the context of the question, is selected as the correct answer.
In some cases, it is not possible to assign the text of the question to just a community. Similarly, sometimes several answers get the highest similarity. In these cases the question is not answered.
In this section we present two background collections used for the QA4MRE 2011 task. In addition, the main tuning parameters are described in the next sections. 4.1
Participants were allowed to submit a maximum of 10 runs. Also, rst runs must have been produced using nothing more than the knowledge provided in the reference collection. For that reason, our rst submitted runs use only the information provided in the QA4MRE-2011-EN corpus. However, additional runs could include other sources of information. Accordingly, the next section describe the other corpus used in the task.
In order to reduce the computation time, we have not used the whole reference collection in the experiments, but we have carried out a selection of the most relevant documents in the corpus to build the co-occurrence graph. We have created an index with the documents in the reference collection to retrieve and use only those that are most relevant to a particular question. The most relevant documents are obtained from the similarity measure used by the search engine implemented. The score of query q for document d correlates to the cosinedistance between the document and the query vectors in a vector space model (VSM) of information retrieval. A document whose vector is closer to the query vector in that model is scored higher.
Accordingly, we have carried out an indexing process where every document
of the considered topics has been indexed by ltering stopwords extracted from
a public list in the University of Glasgow2. For indexing tasks we used Lucene[
Finally, the system has three di erent indices for each of the documents divided by topic. For each question, several queries are submitted to the index by retrieving a variable number of documents in each query. The number of documents retrieved in each case is a system parameter. Documents retrieved in each case are used to build the co-occurrence graph. 4.2
The second variant is a slight modi cation of our original proposal. In this case,
documents used to build the co-occurrence graph are retrieved from a commercial
search engine. For that, we have used the open search web services platform of
Yahoo! (BOSS4). Documents are obtained by submitting several queries to the
2 http://ir.dcs.gla.ac.uk/resources/linguistic utils/
3 http://snowball.tartarus.org/
4 http://developer.yahoo.com/search/boss/
search engine composed of terms extracted from the di erent sources (text of the
question, answers, topic). Our system performs a form of query expansion[
The experiments generated for the task have been carried out considering different parameters in their con guration. First, we have used two reference collections; the collection provided by the organizers and another one built from a set of queries submitted to a search engine. Second, the number of documents retrieved for each query is an important factor a ecting the size of the graph. Thus, several values were taken to analyze their in uence on the results. Finally, in some cases the documents have been indexed by ltering stopwords and in other cases we have not used any lter.
The con guration of the di erent runs can be seen in Table 1.
Run Collection uned1101enen QA4MRE-2011-EN uned1102enen QA4MRE-2011-EN uned1103enen QA4MRE-2011-EN uned1104enen QA4MRE-2011-EN uned1105enen QA4MRE-2011-EN uned1106enen QA4MRE-2011-EN uned1107enen QA4MRE-2011-EN uned1108enen QA4MRE-2011-EN uned1109enen API Yahoo! BOSS # Docs Filter 100 No Filter 75 Stopwords 75 No Filter 50 Stopwords 50 No Filter 40 Stopwords 40 No Filter 20 Stopwords 20 Stopwords Table 2 shows the results for the submitted runs, including answered questions, unanswered, answered right, answered wrong, unanswered right, unanswered wrong, unanswered empty, and c@1 measure.
Figure 1 illustrates the results for submitted runs per topic. Topic 3 that corresponds to Music and society obtains the best average results with respect
Run Ans. Unans. A.R. A.W. U.R. U.W. U.E. Overall c@1 uned1101enen 77 43 24 53 0 0 43 0.27 uned1102enen 63 57 17 46 0 0 57 0.21 uned1103enen 60 60 16 44 0 0 60 0.20 uned1104enen 53 67 12 41 0 0 67 0.16 uned1105enen 50 70 13 37 0 0 70 0.17 uned1106enen 45 75 11 34 0 0 75 0.15 uned1107enen 39 81 10 29 0 0 81 0.14 uned1108enen 16 104 2 14 0 0 104 0.03 uned1109enen 67 53 20 47 0 0 53 0.24 to each run submitted, it even improves results of the overall. Topic 2, that corresponds to 'Climate Change', gets the best c@1 measure, and far exceeds the runs 1 and 9 the overall measure. Topic 1 (AIDS) in almost all cases has obtained a c1 measure lower than overall. 6
Analyzing the results, it can be said that the in uence of the collection is a very important factor in the quality of the results. Although only one run (uned1109enen) has been submitted using the collection built from queries in a search engine, the di erence is clear when compared with the equivalent run generated from the reference collection (uned1108enen). First, the number of answered questions is four times greater (67 vs 16) than with the collection provided by the organizers. Second, the c@1 measure is eight times higher (0.24 vs 0.03). This di erence is surprising since the collection provided by the organizers should have only documents of a given topic, while queries in a search engine are performed on the whole Web.
The number of retrieved documents is also an important factor in the results. In the case of retrieving 20 documents for each query, the c@1 measure obtained is more than 9 times (0.03 vs. 0.27) than retrieving 100 documents.
Finally, it was probed that ltering stopwords has not produced a clear effect on the results, although in previous experiments that ltering provided a signi cant di erence as to compare the results. 7
This work has been partially supported by the Spanish Ministry of Science and Innovation within the project Holopedia (TIN2010-21128-C02-01) and the Regional Government of Madrid under the Research Network MA2VICMR (S2009/TIC1542).