This paper describes our participation to the Entrance Exams Task of CLEF 2015's Question Answering Track. The goal is to answer multiple-choice questions on short texts. Our system rst retrieves passages relevant to the question, through lexical expansion involving WordNet and word vectors. Then a tree edit model is used on graph representations of the passages and answer choices to extract edit sequences. Finally, features are computed from those edit sequences and used in various machine-learned models to take the nal decision. We submitted several runs in the task, one of which yielding a c@1 of 0.36, which makes our team the second best on the task.
in Figure 1. Its pipeline is composed of mainly ve modules: preprocessing, passage retrieval, graph enrichment, beam search with tree edit model and nal classi ers for validation/invalidation. The remaining of this section is dedicated to the detailed description of those modules.
We use Stanford CoreNLP as the main Natural Language annotation tool. Each
sentence from the document, questions or answer choices is tagged with
PartOf-Speech [
The passage retrieval module aims at extracting relevant short snippets from the document to pass to the more computationally expensive modules further down the pipeline. Words of the question and the answer choice act as the query. However, it is very rare that words of the question exactly appear in the relevant passage of the document, so we have to use some form of query expansion. We enrich the lemmas with coreference information, WordNet relations (synonyms, antonyms, hypernyms, hyponyms), and weigh the words by the IDF score of the original word in the document.
If the words of the query are not found using the previous expansion methods,
we use a vector-based representation of words to compute a similarity measure.
Word vectors are those found in [
The passages were syntactically parsed with Stanford CoreNLP to obtain the
initial dependency graphs. We fuse those graphs together by linking their roots
with a followed-by arc which materializes in the single remaining graph that a
sentence is followed by another in the passage. Then we use ConceptNet [
ConceptNet is a semantic triplet base containing relations about common-knowledge of the world, designed to be used especially for machine understanding of text written by people. It is built from nodes representing words or short phrases of natural language, and labeled relationships between them (the nodes are called "concepts" for tradition, but they'd be better known as "terms".) For example, ConceptNet contains everyday basic knowledge, like MotivatedByGoal(learn, knowledge): you would learn because you want knowledge. It also contains cultural knowledge, like UsedFor(saxophone, jazz): a saxophone is used for jazz. Our assumption is that understanding the documents in the Entrance exams corpus requires a lot of human common-sense, easily acquired by human readers of that level, but di cult to grasp for computers. So we want to enrich the text with relations which attempt to ll that gap.
Concepts from ConceptNet are mainly single words, like \saxophone" or \jazz", so they are easy to link to our original graph. However, it is not easy to integrate relations to our graph, because they have labels that are potentially composed of several words, like UsedFor or MotivatedByGoal. We could split those labels into words and use those in the graph, but we preferred attaching to the original graph the parse tree of the surfaceText element of the relations. Surface texts are the original natural language text that expressed the statement, like \a saxophone is used for jazz". We attach the parse tree of these sentences to any concept whose head word is in the original graph. We only retrieve from ConceptNet relations that are indicative of an entailment relation of any kind, namely: IsA, PartOf, MemberOf, UsedFor, CapableOf, Causes, HasPrerequisite, MotivatedByGoal, Desires. 2.4
Tree edit model Our goal is to characterize a sequence of transformations applied to the passage to obtain the answer choice. Those transformations a ect the graph built in the previous section, which is made of parse trees, and the transformations will be called edits, hence a tree edit model. Basically, we apply di erent edits iteratively to the tree, modifying it each time, so that the edited tree is closer to the tree of the answer choice. When we nd an edit sequence to turn the passage into the answer choice, we look at the nature of edits that were e ectively applied, and if they are elements of proof that the passage is indeed close to the answer choice, or if it is too far to conclude anything. This will be done in the subsequent sections.
Table 1 presents the supported edit operations. Figure 2 presents an example of successive applications of three of them.
Beam search The main problem is that there are many choices to make when applying an edit. Which edit to choose? Where to apply changes in the tree? What new elements must be added? What to do next? Any of these choices is an easy source of error, so rather than picking one each time and hoping to nd Edit operation Description Delete(d: Tree) Delete the node d and replace it with its children. Insert(i: Word, p: Tree) Insert the word i under its new parent p. Rename(t: Tree, w: Word) Replace the word attached to the node t with w. Move(m: Tree, op: Tree, np: Tree) Move the subtree m from under op to under np. the right edit sequence, we apply a lot of the possible edits, and explore only the most promising using a satisfyingly good heuristic.
Beam search is an optimization of best- rst search that reduces its memory requirements. It uses breadth- rst search to build its search space. At each step of the search, we generate all possible edits of the trees at the current step, sorting them in increasing order of heuristic cost de ned below. However, we only store a predetermined number of best trees at each level, called the beam width. Only those trees are edited next and the rest is discarded. This method allows to netune via the beam width the probability to nd useful edit sequences and the memory and time costs.
Partial Tree Kernel as a heuristic We need a heuristic measure of how far
a tree at the current step is from the target tree (the dependency tree of an
answer choice). We implement the Partial Tree Kernel de ned in [
Algorithm At the start of the algorithm, the working set consists solely of the enriched dependency graphs of all the retrieved passages. The target tree is the answer choice (or the question plus the answer choice when the answer is an end to the question sentence as can be the case in the CLEF dataset). In our experiments, we keep at most 10 passages in the retrieval step. Then, every possible relevant edit operation is applied to each passage. Inserts and renames can only add a node that is present in the target tree. Moves can only move a node under a parent so that the link parent ! child is present in the target tree. Those edited trees are added to the working set, and the partial tree kernel with the target tree is computed for all of them. The working set is then ltered to only the top 50 trees with the best kernel score (50 is our beam width) and the algorithm can now start again with the application of the edit operations on the new working set.
It stops when 10 di erent edit sequences have been found (some ltering is done to ensure that we do not obtain mere variations of the rst sequence found), or after 200 edit steps, whichever comes rst. 2.5
The goal is to classify an edit sequence with two di erent machine-learned classi ers, one to decide if the related answer choice is validated, and one to decide if it is invalidated. The design of features is thus primordial. In practice, we will use the same features and the same machine learning algorithm for the two classi ers, so the only di erence will be the training data, discussed in the next section.
Most features are counts of speci c edit unigrams or bigrams in the edit sequence, and are summarized in Table 2. Pre-processing informations that were not used in the beam search are used at this point, like dependency relations in the parse tree, coreferences, and whether what we edit was part of the ConceptNet additions or can be linked in WordNet. 3
3.1
Our data consist of the trial and test sets at CLEF 2015 Question Answering Track, Task 2: Entrance Exams. The trial data is composed of the test sets at CLEF 2013 and 2014, each containing a series of 12 texts, and for each of them, 4 to 6 multiple-choice questions to answer, for about 120 questions in total. In the 2015 test set, there are 19 documents, and a total of 89 questions. There are 4 answer choices possible for each of the questions. This corpus has been extracted from the Tokyo University Entrance Exam in English as a foreign language. Systems are evaluated according to their c@1, de ned in equation 2. n1 (nR + nU nnR ) (2) with n the total number of questions, nR the number of correctly answered questions, nU the number of unanswered questions. moveTotal moveVerb ... moveConceptNet moveMoreThan2Nodes All bigram combinations of the above Number of pairs of the successive given edits in the sequence dependencyEditSequence Number of pairs of successive edits applied to 2 nodes in a dependency relation originalTotal Fraction of the original words, verbs, nouns, originalVerb proper nouns, that was not edited in the se... quence
Description Total number of edits in the sequence Number of total delete edits, edits which delete a verb, a noun, a proper noun, a subject (indicated by the subj Stanford dependencies), an object, the root of the tree, a negation (indicated by the neg dependency), and something added to the graph through ConceptNet Analogous to the above, for insert edits Analogous to the above, for rename edits + edits which rename a word into its synonym in WordNet, or into its antonym in WordNet, or into a hypernym/hyponym in Wordnet, edits which rename a word into another with strong word vector similarity (above a threshold, de
ned empirically), edits which rename a pronoun into its referent according to the Stanford coreference resolution, and edits which rename a pronoun into some other referent Analogous to the above, for move edits + edits which move more than 2 nodes 3.2
The classi er pair, for validation and invalidation, uses the feature set de ned in
the previous section. We experimented with two models, logistic regression and
random forest, both implemented in Weka [
We create the learning (passage, answer choice) pairs by annotating them following the semantics described in Figure 3. In this gure, RP stands for right passage, RA for right answer, WA for any wrong answer, WAx for the wrong answer choice x, WPx for the passage expressing it, OP for any other passage than the one expressing the paired answer choice. To summarize, the only time we can either validate or invalidate are when we operate on passages relevant to some answer choice: we annotate as validated only if we have both the right passage and the right answer, and invalidated if we have a wrong answer choice with either the passage which expresses it in the document or the right passage. This follows the intuition that as readers, given a question, a passage and an answer choice, we can probably tell if the provided passage is self-su cient in expressing the right answer to the question or if there is a mismatch between an answer choice and the passage in the text it refers to.
Then the edit sequences for this data are computed, their features are extracted, and sequences for both classi ers are labeled using the aforementioned semantics. Implicitly, as this is not visible in Figure 3, if an edit sequence is labeled 1 (valide/invalidate) for one classi er, it is labeled 0 for the other. The thin dashed arrows simply symbolize that the label is 0 for both classi ers.
For the test run, the algorithm runs on the test data, and the answer is chosen based on the regression numbers output by the two classi ers. First, for each answer choice, the edit sequence with the highest max (validationScore, invalidationScore) is selected. Ideally we want an edit sequence which is characteristic of either a high con dence validation, or a high con dence invalidation, so that we may classify the answer choice con dently as either correct or incorrect in the next step. Then, the answer choice whose selected sequence has the highest validationScore invalidationScore is nally picked: we want in RP / WA WPx / RA WPx / WAx WPx / WAy OP / RA OP / WA
Validated Cannot judge Invalidated 1 0 1
Validation Classifier Invalidation
Classifier correctly classi ed answer choices as much separation between their validation and invalidation scores as possible. If they have a similar validation and invalidation score, the system just ends up guessing. We acknowledge that this is a very basic decision process and address this point more in detail in Section 3.5. 3.3
In this section, we report the results of our two learning models on the testing set of questions. Table 3 presents those results. A c@1 of 0.36 gave us the second place among teams which participated in the task.
Random forest Logistic regression 89 89 57 61 0.360 0.314
8 4 0.360 0.314
The random forest model performed better on the test run, which con rms what we expected during development. 3.4
Qualitative analysis A pertinent qualitative analysis is always delicate to do for machine learning systems with such low performances. It is indeed always possible to draw examples that look like the system is obviously supposed to correctly handle but end up as errors. Conversely, it is always possible to nd a complex instance on which the system somewhat miraculously worked (i.e. made a lucky guess).
Nevertheless, we rst report some of the simple errors that our system made. In the following passage/question pair, our system got lured by answer 3, closest in surface form to the relevant passage. ConceptNet does not link "held" to "trapped", and "its original nature" from the correct answer could not be linked to anything in the passage (it is however found further in the text). Several years ago, certain scientists developed a way of investigating the nature of the atmosphere of the past by studying air caught in the ice around the North or South Pole. According to their theory, when snow falls, air is trapped between the snow akes. The snow turns to ice with the air still inside. Certain scientists claimed that 1) atmospheric gases increase the yearly amount of snow 2) falling snow akes change the chemical balance of the air 3) the action of atmospheric gases causes snow to turn into ice 4) the air held between snow akes keeps its original nature (correct) In the following passage/question pair, our system picked the answer choice 3. It would have been easy to pick the correct answer 1 if "wrong" could have been linked to "mistake", but in ConceptNet, this is a RelatedTo relation, which we did not consider. We realize that there is actually a lot of information in those RelatedTo relations, and ideally our system should handle them, but we decided in the design phase to remove them because they are not semantically precise. Everyone stared. That was embarrassing enough, but it was worse when I nished my co ee and got ready to leave. My face went red - as red as his hair - when I realized I'd made a mistake.
The woman's face turned red 1) because she realized that she had been quite wrong about the boy (correct) 2) because she realized that the boy was poor and hungry 3) because she saw everyone staring at her 4) because she hated being shouted at In both those cases, a more precise characterization of correct passages would have been useful, because in the rst case, our answer choice skips over the sentence which contains the correct answer, and in the second case, the sentence containing our answer choice appears way before the sentence containing both question and correct answer.
Finally we report an example of correctly answered question through mostly invalidation. In the following passage/question pair, our system frankly invalidated answer choice 1 (due to the added negation) and answer choice 4 (due to the rst sentence of the passage saying the opposite). Then, answer choice 2 had edit sequences which hinted at both validation and invalidation, so it was still a risky pick (but with slightly more invalidation). In the end, the remaining answer choice (3), for which the system found neither validation nor invalidation, was correctly picked by default.
Kate was an energetic woman who expected people always to be doing something, and she found plenty of jobs for Fred to do. This made him feel part of the household, but now he really wanted to be able to sit and re ect on the events of his life. If he had continued to live alone, he would have had the time to do this to his heart's content. One afternoon he felt he simply had to get away from the house. "I'm going for a walk," he said, closing the door behind him. Leaving the town, he walked across the elds and followed a slow-moving stream toward the hills. After a while he came to a pool in the stream under some trees. Here, he thought, was a place he could come to when he needed to re ect on the past. Although the stream seemed unlikely to have any sh, he would simply tell Kate he had found a place to go shing. When he mentioned the stream that night, his son-in-law, Jim, said in disbelief, "There aren't any sh there. That stream runs dry half the summer." Why did Fred tell Kate that he had found a place to go shing? 1) He didn't feel part of the household with Kate and Jim. 2) He enjoyed shing very much and was glad to be able to do it again. 3) He wanted a way to leave the house without hurting Kate's feelings. 4) He was bored in the house because there were few things to do. Quantitative analysis The general trend was that our system performed better when edit sequences remained short, with over 40% accuracy when the chosen edit sequences are shorter than 6 edits (on average on all the answer choices). We considered this was still not signi cant enough of an advantage to choose not to answer questions based on a length threshold of edit sequences. 3.5
We did not take advantage of the possibility to choose not to answer a question. In our experience, every missed answer adds variance when running on the test set (we are evaluated on even fewer questions, when there are not many to begin with), so we did not prioritize exploiting this feature of the evaluation. However, we believe our learning method has the potential to handle it. In future works, it would be interesting to design a meta-classi er working on the output of the two current classi ers.
Our system has been developed to answer multiple-choice questions. We extract features from edit sequences obtained from our tree edit beam search method, and learn two classi ers for validation and invalidation of answer choices. In the CLEF 2015 evaluation campaign, Question Answering track, Entrance Exams task, our best submitted run obtained the second performance among teams. In further works, we plan to improve our graph enrichment method, which seems to be a promising avenue. We are considering adding paraphrases to the graph. Moreover, we plan to develop a meta-classi er dealing with the nal decision, based on the individual validation/invalidation scores per answer choice, instead of relying on manually crafted rules.