This paper describes the approach used in the system for the Question Answering Task based on Entrance Exams, which was presented at the CLEF 2014. The task aims to evaluate methods of text understanding with reading comprehension tests. The system should read a given document and answer multiple-choice questions about it. Our approach transforms the documents along with the multiple-choice answers into a graph-based representation that contains lexical, morphological, and syntactic features. After this, it traverses di erent paths both in the document itself and in the the graphs of the answers in order to nd these features of the graphs. It is performed by counting text components: lemmas, PoS tags, grammatical tags. As the result of this procedure, the system constructs several feature vectors: one for each traversed graph. Finally, a cosine based similarity is calculated over these feature vectors in order to rank the multiple-choice answers and select the correct one|with the best similarity with the graph that corresponds to the text itself. Our system obtained a c@1 of 0.375, which was outperformed only by one system in the competition.
In this paper we present the experiments carried out as part of the participation
in the Question Answering track based on Entrance Exams presented at the
CLEF 2014. The Entrance Exam task was proposed in 2013 as a pilot task [
Since the rst edition of QA4MRE task in 2011, and later in the 2012 and 2013, a single evaluation platform for the experimentation with new techniques and methodologies for this problem has provided. In this sense, we can take the systems presented at this conference as state of the art work in this research eld.
The rest of the paper is organized as follows. Section 2 describes our approach and the system architecture. Section 3 presents the con guration of the submitted runs and the evaluation results. Finally, Section 4 presents the conclusions and outlines some directions of future work. 2
For many problems in natural language processing, graph structure is an
intuitive, natural and direct way to represent data. There exist several research
works that have employed graphs for text representation in order to solve some
particular problem [
Document Preprocessing First we perform document (pre)processing. An XML parser receives as input a structured corpus in XML format as it is shown in Figure 1. This XML le contains all the documents, along with their respective questions and multiple choice answers. An XML interpreter extracts the documents, questions and associated answers. It stores the questions and answers identifying them according to the document, to which they belong, in order to be used in further processing. Further, the questions associated to each document are analyzed, identifying the \question keywords" (what, where, when, who, etc.), and the result is passed to
the next module. After this, hypothesis generation module formulates several candidate \answer hypotheses" as the modi ed versions of the original question, replacing these words with one of the possible answers given in the test data. For example, given the question: Who is the founder of the SING campaign? and the possible answer: Annie Lennox. The obtained hypothesis is: Annie Lennox is the founder of the SING campaign.
Afterwards, we perform anaphora resolution in the documents using the
JavaRAP3 system. It was observed that applying anaphora resolution in QA
systems improves the precision [
The output of this module is the set of answer hypotheses along with their reference documents.
g n iss e rc o P t n e m u c o D n o tirea n e G h p ra G
(Question + Answer)
MorTpahgogloergical ---- ---- ---- ---
- - - - - - - - - - - -
- Anaphora Resolution
(traversing graphs) re tion sn lid Final Answer w a A aV
and semantic relationships) in order to capture the majority of features present in the text.
The process of the graph generation is performed by the following submodules: Syntactic Parser is the base of the graph structure. We use the Stanford Dependency Parser4 for producing the parsed tree for each sentence of the documents. In this type of parsing, we detect grammatical relation between words of the sentences.
Morphological Tagger obtains PoS tags of the words. For this, we used the Stanford Log linear Part-Of-Speech Tagger5 for English. The Lancaster stemmer algorithm was used in order to obtain word stems.
Semantic Expansion uses the Wordnet taxonomy [
As the result of this process, each document is represented as a tree rooted in a ROOT 0 node. The vertices to sub-trees represent all sentences in the document. The nodes of the trees represent word or lemmas of the sentences along with their part-of-speech tags. The vertices between nodes represent the dependency tags between these connected nodes and the frequency label shows the number of occurrences of the pair (initial node, nal node) in the graph plus the frequency of the dependency tag of the same pair of nodes. In the same way all answer hypotheses are represented as trees with the same characteristics.
In Figure 2 we present the graph-based representation for the hypothesis \Annie Lennox is the founder of the SING campaign", whereas Figure 3 shows the graph-based representation for the rst three sentences of the reference document associated to this question.
ROOT-0 root:2 founder-NN nsubj:2 cop:2 prep:2
Lennox-NNP is-VBZ of-IN nn:3 det:3 pobj:2
The feature extraction starts by xing the root node of the hypothesis graph
as the initial node, whereas the selected nal nodes correspond to the rest nodes
4 http://nlp.stanford.edu/software/lex-parser.shtml
5 http://nlp.stanford.edu/software/tagger.shtml
of the hypothesis graph. We use the Dijkstra0s Algorithm [
ROOT-0 root:3 going-VBG xacoumx:4p:2 ’m-VBP prep:4 with-IN
share-VB dobj:2 story-NN pdreetp:5:4 as-IN root:3 aux:4 pcomp:2 campaigner-NN advmod:3 dep:2 nn:9 to-TO nsubj:5 aux:4 cop:4
Why-WRB am-VBP HIVAIDS-JJ an-DT Lennox-NNP nn:11 how-WRB have-VBP become-VBN
nn:9 pobj:3 campaign-NN appos:2
Campaign-NNP nn:9 SING-NNP This module receives several feature vectors (f!t;i) for each text. Thus, the reference document d is now represented by m features (d = ffd!;1; fd!;2; :::; fd!;mg), as well as the answer hypothesis h, (h = ffh!;1; fh!;2; :::; fh!;mg), being m the number of di erent paths that can be traversed in both graphs.
We use the following cosine similarity measure for calculating the degree of similarity in each traversed path:
Similarity(h ; d ) = m X Cosine(fh!;i; f!d;i) i=1 = Xm fh!;i f!d;i i=1 jjfh!;ijj m = X
jjf!d;ijj PjjV=j1 (f(h;i);j
f(d;i);j ) i=1 qPjjV=j1 (f(h;i);j )2 qPjjV=j1 (f(d;i);j )2 : (1)
After obtaining all similarity scores of the four hypotheses for each question, the hypothesis achieving the highest score is selected as the correct answer. We answered every question of the task using this methodology. 3
This section describes the data sets of the challenge used for evaluation of the systems. Additionally, the results obtained in the experiments are reported and discussed.
Following 2013 edition, the test set 2014 based on Entrance Exams was composed of tests for reading comprehension taken from the Japanese Center Test, which is a nation-wide achievement test for admission in Japanese universities.
The organizers released two di erent datasets, one for training and one for testing. Both data sets were composed of the following elements: { 12 test documents, { 60 questions (5 questions for each document), { 240 choices/options (4 for each question).
The main measure used in this evaluation is c@1, which is de ned as shown in equation 2. This measure was de ned in the QA4MRE task at CLEF 2011 with the purpose of allowing the systems to decide whether or not to answer a given question. The aim of this procedure is to reduce the amount of incorrect answers, maintaining the number of correct ones, i.e., a system is penalized for answering incorrectly and it is better not to answer at all if not sure: 1 nR ); n (nR + nU n (2) where: nR: number of correctly answered questions, nU : number of unanswered questions, n: total number of questions. competition from various research teams. We submitted eight runs with different con gurations of the system. The run that ranked highest was cicnlp-8, which obtained a c@1 of 0.375 answering 21 questions correctly. At the reading comprehension level the run cicnlp-8 only passed 3 out of 12 tests, whereas the run cicnlp-2 passed 4 out of 12 tests. Even though the run cicnlp-2 passed one more test than our best run, it only obtained a c@1 of 0.303. In the last column of Table 1 we show the quantity of tests passed by the runs (tests with c@1 > 0.5). and dependency tags (count). The runs cicnlp-7 and cicnlp-8 apply the feature extraction technique when the words in the hypothesis graph are expanded with their corresponding set of hypernyms (without applying the process of word sense disambiguation). The run cicnlp-8 uses stems instead of the full words in the graph-based representations. The features extracted in both runs are PoS tags (count) and dependency tags (count).
We found that as far as the reading level is concerned, di erent runs were able to pass di erent tests. For example, the run cicnlp-8 passed the tests 13, 16 and 18; the run cicnlp-3 passed the tests 13, 14, 15 and 16; the run cicnlp-6 passed the tests 13, 16 and 23. In future, we plan to combine di erent runs, and in this manner we would be able to pass 6 out of 12 tests. Besides, the run cicnlp-8 passed the test 13 correctly answering all questions. 4
Conclusion and Future Work We described the approach and the system developed as a part of our participation of QA task 2014 based on Entrance Exams. The approach uses a graph structure for representing the documents and the answer hypotheses. It extracts linguistic features from both graphs|documents and answer hypotheses|by traversing shortest paths. The features are further used for computing the similarity between the document and the answer hypotheses.
We sent eight runs to the competition. The best run (cicnlp-8 ) of our system achieves a c@1 of 0.375, which was outperformed only by one system.
For future work, we hope that the use of domain-speci c techniques of question answering will improve the performance of the algorithm for this particular problem. Textual entailment, named entity recognition, analysis of the type of question can improve the nal results of our system in the task.