This paper describes the Nara Institute of Science and Technology's system for the main task of CLEF 2013 QA4MRE. The core of the system is a log linear scoring model that couples both intra and intersentence features. Each of the features receives an input of a candidate answer, question, and document, and uses these to assign a score according to some criterion. We use minimum error rate training (MERT) to train the weights of the model and also propose a novel method for MERT with the addition of a threshold that de nes the certainty with which we must answer questions. The system received a score of 28% c@1 on main questions and 33% c@1 when considering auxiliary questions on the CLEF 2013 evaluation.
While years of research on Question Answering (QA) have greatly improved
the state-of-the-art, we know that this problem is far from solved. Question
answering campaigns such as CLEF [
We introduce several new features that span multiple sentences in addition to more traditional features such as cosine similarity. These features are combined in a framework that learns both how and when to answer questions in a single weighted linear model. In particular, we nd how to answer questions by learning appropriate weigths for each feature, with nal score of an answer being their weighted linear combination. We de ne when not to answer by not returning candidates for which scores are less than a set threshold t from other candidates. Finally, we propose a method to intelligently weight the features and threshold using minimum error rate training.
As results for the 2013 evaluation, our best run in main task scored 28% for only main questions and 33% when auxiliary questions are also included. 2 2.1
Our QA system has a modular pipeline architecture, making it easy to modify
some modules without changing other parts of the system. The system is divided
into three major modules: preprocessing, scoring, and answer selection.
As the raw input is full of noise that can drastically reduce the ability to
generate appropriate hypotheses, preprocessing is necessary to process the text into
machine-readable format. First, the tokenization step splits the sentence into a
list of tokens. Second, the named entity recognition step uses the Stanford named
entity annotator1 to recognize the existence of named entities. We use the
Stanford 4 tag set, which consists of PERSON, LOCATION, ORGANIZATION, and
MISC. Third, the anaphora resolution module is based on the \last introduced
named entity" constraint [
In addition, we made a few re nements to choose which named entity best replaces the Referring Expression (RE). This module focuses on RE that represent humans according to the following rules: { \They" and \we" are replaced by the most recent ORGANIZATION named entity. { \I" is replaced by the rst PERSON entity that occurs in the passage, which is generally the speaker. { \You" is replaced \theaudience." { \He" and \she" are replaced by the most recent PERSON named entity. { \It" may refer to either LOCATION, ORGANIZATION, or MISC. { The remaining pronouns are simply left unaltered. 2.3
The scoring criterion is based on linear combination of several weighted features,
[
(1) n X wi i=1 where s is a function specifying the score of candidate aj;k given question qj and document D. i(aj;k; qj ; D) is a feature function, wi is its corresponding weight, and D is a sequence of sentences. We describe the features in more detail in section 3.2, and the weight training algorithm in section 4 2.4
The answer selection module chooses which, if any, question to answer. Let aj;k be a candidate answer for a given qj and D, and let sk be the score from evaluation s(aj;k j q; D). If aj;k1 is the answer with the highest score among all candidates for qj , we de ne the certainty of the answer to be cj;k1 = min (s(aj;k1 j qj ; D) k26=k1 s(aj;k2 j qj ; D)) (2) 1 http://nlp.stanford.edu/software/CRF-NER.shtml 2 http://www.lextek.com/manuals/onix/stopwords2.html If our certainty exceeds a threshold t, we provide the answer aj;k1 and if it does not, the system returns no answer.
As the main test data for this year evaluation contains a \none of the above" candidate answer for every question, we choose to answer 20% of the questions with this answer. This heuristic strategy is applied because our system is currently incapable to provide an analysis toward this type of negation and we do not have any gold-standard training data from previous years on which to perform training. Intuitively, we choose 20% questions with lowest score from Equation (1) to be assigned with the candidate answer \none of the above". 3 3.1
Our system uses a bags-of-n-grams vector space model for sentence matching. For example, if we have the sentence \We are scientists", we will have bags-ofwords as follow: 1-gram = f\We", \are", \scientists"g, 2-gram = f\We are", \are scientists"g, 3-gram = f\We are scientists"g. The model that we used is a model consisting of bags-of-words for all n-grams and is de ned as follows: model = 1-gram [ 2-gram [ 3-gram.
In preliminary experiments, we found n = 3 achieved higher precision than n = 1; 2; 4; 5, and that it was necessary to take the union of higher and lower order n-grams.
To measure similarity between vectors, we used TF/IDF [
jvj n(i; v) ; where tf(i; v) is the occurrence frequency of term i in passage v, jvj is the total number of sentences in D, and n(i; v) is the number of sentences in v in which term i occurs. 3.2
Following from (3), the equation for cosine similarity between question q and sentence dj is sim(q; dj ) = pPp i=1 tf-idf(i; q)2 Pp i=1 (tf-idf(i; q)
tf-idf(i; dj )) pPp i=1 tf-idf(i; dj )2 : Each feature gives a score to each pair of fq; Dg and fakg. We use three intrasentence features that are widely known in previous work: (3) (4) 1. Greatest Cosine (GC) nds the most related sentence to q and ak. If this value is high, we have more certainty in the candidate answer. This feature concatenates the question and answer and nds the greatest cosine similarity value for a sentence in the document.Let p be a query where q and ak are concatenated together.
GC max(sim(p; dj )).
j 2. Greatest Matching (GM) does not adopt cosine matching, but simply counts the maximum number of words that match both the ak and q in a single sentence. This feature simply counts the greatest number of words overlapping between one sentence in the background text and the concatenated question and answer.
GM max (j(q [ ak) \ dj j).
j 3. Cosine Matching (CosM) distinguishes whether the question and candidate answers occur in the same sentences in D or not. Here l is some threshold, which we set to 0.1 after preliminary tests.
CosM
jD1\D2j where D1 = fdj j sim(q; dj ) > lg ^ D2 = fdj j sim(ak; dj ) > lg We also propose new inter-sentence features that help capture answers that span multiple sentences in a simple manner: 1. Closest Matching (ClM) aims to nd candidate answers that are not in the same sentence as q but close in proximity. We represent this using the distance from representative sentence r, which is de ned as the sentence most similar to the question, and all answer candidate sentences. Let index(dj ) be a function that indicates the location of dj in the passage, r = argmax(sim(q; dj )) and D = fdj j sim(ak; dj ) > lg.
j
ClM = 8<dmj2inD(jindex(r) :0 index(dj )j) if D 6= ; otherwise 2. Closest Sentence (ClS) is quite similar to ClM, but instead of nding a representative sentence r, it counts the distance from all sentences that exceed the threshold t. 3. Unmatched (UM) is a binary feature active when ClM or ClS nd no answer. 4
This section describes a uni ed minimum error rate training [
Before learning, we must formally de ne how good any particular values of w
are. One de nition of the \goodness" of w is the accuracy, or percentage of
questions answered correctly
a(w; t; Q) =
c(w; t; Q)
jQj
where c(w; t; Q) is the number of questions in Q answered correctly given w and
t. However, while this measure is intuitive, it also cannot distinguish between
unanswered and incorrectly answered questions. As a remedy to this, [
(5) (6)
Next, we want to nd a value of w that allows our system to score well
on these evaluation measures. To do so, we rst adopt the minimum error rate
training (MERT) framework of [
The basic idea of MERT is to e ciently nd weights that minimize some measure of error of the system. For example, we could de ne our error as one minus the accuracy of the system, and nd weights that minimize this value w^ = argmin 1 w a(w; 0; Q)
As exactly solving Equation (7) is computationally di cult, [
Figure 2 shows this procedure on two questions with answers and their corresponding features in Figure 2 (a). First note that for answer aj;k to question qj , Equation (1) can be decomposed into the part a ected by wi and the part a ected by wnwi: (8) (9) s(qj ; aj;k) = wi i(qj ; aj;k; D) +
X wh h(qj ; aj;k; D)
h6=i
While the previous procedure can minimize errors that are merely concerned
with the highest scoring answer, when considering a threshold t we also need
to keep track of whether the best answer exceeds the second best answer by
more than t. We present a modi cation to the standard MERT procedure that
allows us to learn weights in the face of a threshold, which we will refer to as
thresholded minimum error rate training (TMERT).4
3 [
During the aggregation of statistics in Figure 3 (c), we collect information not only on regions where the answer was correct, but also on regions where the question was unanswered. Given these statistics, we can calculate accuracy for measures that reward non-response such as c@1 and choose a value of wi that minimizes the error accordingly.
We can also indirectly optimize threshold t itself in this framework. To do so, we note that the overall scale of the weights w is inversely proportional to the threshold t; having large weights is equivalent to having a small threshold, and vice-versa. Thus, any t > 0 will have the same e ect on our thresholded learning algorithm, so we simply set t = 1.5 5 It is also possible to more e ciently adjust the scale of w by taking an additional TMERT optimization step for a scaling factor , then scale w ^w. 5.1
For this year's QA4MRE, our system used only the English test set document and did not reference the background collection.
The main task consists of 284 questions, classi ed into 4 main topics (\AIDS", \Climate Change", \Music and Society" and \Alzheimer") and main task questions and documents that in standard and relatively simple language. There are 16 test documents (4 for each topic) and approximately 15{20 questions with 5 candidate answers for each test document. The system is required to choose answer from these multiple choices and only 1 correct candidate answer is available for each question. The system can leave the question answered if it lacks con dence. While the main task is quite similar to the past years, this year each question contains \none of the above" as a candidate answer.
To train the parameters of our model, we use both test set documents from
past CLEF 2011 and 2012 QA4MRE campaigns [
We submit a total of 2 runs for the main task separating the results from di erent strategies. Run1 uses the strategy of choosing some answers as \none of the above" as mentioned in Section 2.4 while Run2 does not.
Topic MaRinu+n1Aux MaRinu+n2Aux Alzheimer 0.36 0.36 0.29 0.29 Music and society 0.28 0.37 0.29 0.39 Climate Change 0.29 0.32 0.24 0.28 AIDS 0.19 0.25 0.15 0.23
Average C@1 0.28 0.33 0.24 0.30
First, we show the results as measured by c@1 in Table 1. Our strategy in Run1 resulted in a gain in system performance for an additional 3{4% over Run2, for evaluation in both main and +Aux questions. It indicates that the strategy is able to slightly raise accuracy for our system. The gains are relatively stable among the topics, with the topic \Alzheimer" receiving the most bene t.
Overall, the system's best topic is \Alzheimer" and worst topic is \AIDS". The accuracies for the topic \Music and society" and \Climate change" are relatively similar. However as we did not use any form of knowledge except reading the document itself, we cannot provide further analysis on why our system is good or bad at certain topic.
The results in Table 1 also indicates that the system is relatively weak at the main questions. In particular taking a look at the sample question r id=5 and q id=6:
Of all Cramer's works, the one that has had the greatest enduring value is his celebrated set of 84 studies for the piano, published in two sets of 42 each in 1804 and 1810 as "Studio per il pianoforte". This collection has long been considered a cornerstone of pianistic technique and is the only work of Cramer's that is generally known today.
Question: Why is the "Studio per il pianoforte" well known even today? 1. because there are 84 studies 2. because the studies are structurally simple 3. because it teaches piano technique very e ectively 4. because it shows the in uence of Scarlatti 5. none of the above The system return the answer of \1" because there are many matching keywords of the candidate answer and question in the same sentence and our anaphora resolution module failed to match the word \This" as \Studio per il pianoforte". However, our inter-sentence features are also able to answer some questions that need an inter-sentence analysis (taken from r id=7, q id=9):
The major Hollywood studios of the so-called Golden Age (c1935-55) were MGM, Paramount, RKO, Warner Brothers and 20th Century-Fox. Each housed a permanent music department, with contracted composers, arrangers, orchestrators, librarians and music editors, as well as a resident orchestra, all working under a senior music director.
Question: What sort of music was written for Hollywood lms in the Golden Age? 1. music for orchestra with strong melodies 2. music for singer and piano 3. music for youth audiences 4. music with four-track stereo sound 5. none of the above This question was successfully answered with the help of the ClM features, which nds a distance of one between the question and candidate answer. The question matched the rst sentence because the term \Golden Age" and \Hollywood" appeared in it and the next sentence matched candidate answer 1 because term \orchestra" appeared in it. So the system returned \1" as its nal answer.
For the evaluation measure (7), the function c, and n are respectively the number of correct answers and no answers for paticular test set. Run1 achieved 88 correct answers, 182 wrong answers, and 14 unanswered, resulting a c@1 score of 32.51%. As part of our participation in QA4MRE@CLEF 2013, we have developed QAsystem that is simple but able to answer certain types of questions. In particular it achieved higher accuracy for simpler types of questions in the main task, but lacks in terms of answering more complex question types that need more sophisticated processing. For future work, we believe that it is necessary to use external knowledge such as background knowledge so the system can provide further analysis in classifying questions and determining certain type of strategies to answer the questions. Luckily our described framerwork for a linear combination of experts and the proposed MERT training metric are conducive to adding additional components to capture this information. Further work will be focussed on integrating external knowledge derived from sources such as Wikipedia and the background collections by adding more features.