Inter-Sentence Features andThresholded Minimum Error Rate Training:
NAIST at CLEF 2013 QA4MRE
Philip Arthur, Graham Neubig, Sakriani Sakti,
Tomoki Toda, and Satoshi Nakamura
Nara Institute of Science and Technology,
8916-5, Takayama-cho, Ikoma-shi, Nara 630-0192 JAPAN{philip-a,neubig,ssakti,tomoki,s-nakamura}@is.naist.jp

Abstract. 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 defines the certainty withwhich 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.
Keywords: discriminative learning, minimum error rate training, linear feature model, question answering, machine reading, inter-sentence
features1

Introduction

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 [9] and TREC [3] have resulted in a large
number of distinct proposals about how to build robust systems that can provide
correct answers in the general domain. One of the features of QA that is widely
accepted is that “two heads are better than one” [2]. By combining different
information sources, we gain the ability to cover up the disadvantages of one
system with another information source, which results in more effective QA on
the whole. One way to combine multiple systems is to weight each system’s scorewith some value and choose the maximum value from a linear combination [12].
Another important aspect of QA is that it is sometimes good not to answer thequestion [8]. Many systems currently return No Answer (NoA) if they are notconfident because a wrong answer is often worse than no answer [1]. Our system
for the CLEF QA4MRE this year is based on these two principles, devising a

2

NAIST at CLEF 2013 QA4MRE

number of features that provide useful information to identify the correct answer,
and combining them together with a learning framework that is also able to learn
when not to answer questions.
We introduce several new features that span multiple sentences in addition tomore traditional features such as cosine similarity. These features are combinedin a framework that learns both how and when to answer questions in a single
weighted linear model. In particular, we find how to answer questions by learning
appropriate weigths for each feature, with final score of an answer being theirweighted linear combination. We define 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 thresholdusing minimum error rate training.
As results for the 2013 evaluation, our best run in main task scored 28% foronly main questions and 33% when auxiliary questions are also included.

2

System Description

2.1

Architecture

Fig. 1. System Architecture

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.
2.2

Preprocessing

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Inter-sentence Features and TMERT for Question Answering

3machine-readable format. First, the tokenization step splits the sentence into alist of tokens. Second, the named entity recognition step uses the Stanford namedentity 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 [5]. Next, the lowercasing step alters all tokens into
lowercase form and the stop word deletion step deletes all words that appear
in a stop word list.2 Finally, stemming uses the Porter stemmer to reduce all
conjugated forms of some words into their stem.
In addition, we made a few refinements 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 namedentity.
– “I” is replaced by the first PERSON entity that occurs in the passage, whichis 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

Scoring

The scoring criterion is based on linear combination of several weighted features,[12]nXs(aj,k | qj , D) =wi ∗ φi (aj,k , qj , D),(1)
i=1

where s is a function specifying the score of candidate aj,k given question qj anddocument 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

Answer Selection

The answer selection module chooses which, if any, question to answer. Letaj,k be a candidate answer for a given qj and D, and let sk be the score from
evaluation s(aj,k | q, D). If aj,k1 is the answer with the highest score among all
candidates for qj , we define the certainty of the answer to be
cj,k1 = min (s(aj,k1 | qj , D) − s(aj,k2 | qj , D))
k2 6=k1

1
2

http://nlp.stanford.edu/software/CRF-NER.shtml
http://www.lextek.com/manuals/onix/stopwords2.html

(2)

4

NAIST at CLEF 2013 QA4MRE

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 toperform training. Intuitively, we choose 20% questions with lowest score from
Equation (1) to be assigned with the candidate answer “none of the above”.

3

Model

3.1

Sentence-Matching Criterion

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 = {“We”, “are”, “scientists”}, 2-gram = {“We are”,“are scientists”}, 3-gram = {“We are scientists”}. The model that we used is amodel consisting of bags-of-words for all n-grams and is defined as follows:model = 1-gram ∪ 2-gram ∪ 3-gram.
In preliminary experiments, we found n = 3 achieved higher precision thann = 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 [11] weighted cosinesimilarity [5] as the weight of term i . Most of our features are based on the cosine
similarity measure, which is commonly used in many IR systems


|v|
,
(3)
tf-idf(i, v) = tf(i, v) × log
n(i, v)
where tf(i, v) is the occurrence frequency of term i in passage v, |v| is the total
number of sentences in D, and n(i, v) is the number of sentences in v in whichterm i occurs.
3.2

Features

Following from (3), the equation for cosine similarity between question q andsentence dj is
Pp(tf-idf(i, q) × tf-idf(i, dj ))pPpsim(q, dj ) = pPp i=1
.
(4)
2
2
i=1 tf-idf(i, q) ×
i=1 tf-idf(i, dj )Each feature gives a score to each pair of {q, D} and {ak }. We use three intrasentence features that are widely known in previous work:

Inter-sentence Features and TMERT for Question Answering

5

1. Greatest Cosine (GC) finds the most related sentence to q and ak . If thisvalue is high, we have more certainty in the candidate answer. This feature
concatenates the question and answer and finds the greatest cosine similarity
value for a sentence in the document.Let p be a query where q and ak areconcatenated 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 (|(q ∪ ak ) ∩ dj |).
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 ← |D1 ∩D2 | where D1 = {dj | sim(q, dj ) > l} ∧ D2 = {dj | sim(ak , dj ) > l}
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 find 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 defined 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 = {dj | sim(ak , dj ) > l}.
j

ClM =


 min (|index(r) − index(dj )|)if D 6= ∅0otherwise

dj ∈D

2. Closest Sentence (ClS) is quite similar to ClM, but instead of finding 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 find no answer.

4

Weight LearningThis section describes a unified minimum error rate training [7] framework tolearn how and when to answer questions by adjusting w and its scaling withrespect to threshold t.

6

NAIST at CLEF 2013 QA4MRE

4.1

QA Evaluation Measures

Before learning, we must formally define how good any particular values of w
are. One definition of the “goodness” of w is the accuracy, or percentage ofquestions answered correctlya(w, t, Q) =c(w, t, Q)
|Q|

(5)

where c(w, t, Q) is the number of questions in Q answered correctly given w andt. However, while this measure is intuitive, it also cannot distinguish between
unanswered and incorrectly answered questions. As a remedy to this, [8] propose“c@1,” which gives partial credit to unanswered questions, in proportion to theaccuracyc(w, t, Q) + n(w, t, Q)a(w, t, Q)(6)
c@1(w, t, Q) =|Q|
where n(w, t, Q) is the number of no-answers.
4.2

Minimum Error Rate Training

Fig. 2. Optimization of w3 : (a) training examples and initial w, (b) slopes of eachexample, (c) whether qj is correct for ranges of w3 , (d) total number of correct answers,(e) the accuracy and new value of w3 .

Next, we want to find a value of w that allows our system to score wellon these evaluation measures. To do so, we first adopt the minimum error rate
training (MERT) framework of [7], which can learn weights w for arbitrary
evaluation measures that do not consider a threshold (t = 0).
The basic idea of MERT is to efficiently find weights that minimize somemeasure of error of the system. For example, we could define our error as one
minus the accuracy of the system, and find weights that minimize this valueŵ = argmin 1 − a(w, 0, Q)
w(7)

Inter-sentence Features and TMERT for Question Answering

7

As exactly solving Equation (7) is computationally difficult, [7] proposes anapproximate algorithm using the coordinate ascent method of [10].3 We will
give a conceptual overview of the procedure here, and readers may refer to [6]or the supplementary code for a more complete algorithmic explanation. The
basic idea of this method is that we iterate through each single element wi ∈ w,
and find the value of wi that minimizes error, given that all other elements of w
(represented as w\wi ) are kept constant:ŵi = argmin 1 − a(w, 0, Q)

(8)

wi

This process continues until no wi can be modified to decrease the error rate.
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 affected by wi and the partaffected by w\wi :Xs(qj , aj,k ) = wi φi (qj , aj,k , D) +wh φh (qj , aj,k , D)
(9)
h6=i

Figure 2 (b) plots Equation (9) as a linear equation over wi in the formy = cx+d where c = φi (qj , aj,k , D), x = wi and d is equal to the right hand sum.
These plots demonstrate for which values of wi each answer aj,k will be assigned
a particular score, with the highest line being the one chosen by the system. For
q1 , the chosen answer will be a1,1 for wi < −2, to a1,2 for −2 < wi < 2, and to
a1,3 for 2 < wi as indicated by the range where the answer’s corresponding line
is greater than the others.
Next, we take the information of answers chosen in Figure 2 (b) and, given theinformation about what answers are correct, convert this into a graph as Figure
2 (c) where the value is one for regions covered by the correct answer and zerootherwise. The ranges for each question are then combined into a single graphindicating the total number of correct answers for each value of wi (Figure 2 (d)).
Finally, given the statistics in Figure 2 (d), we can calculate the error functionused in Equation (8) and choose a point in the center of the region with theminimal error as shown in Figure 2 (e).
4.3

Thresholded MERT

While the previous procedure can minimize errors that are merely concernedwith the highest scoring answer, when considering a threshold t we also needto keep track of whether the best answer exceeds the second best answer bymore than t. We present a modification to the standard MERT procedure thatallows us to learn weights in the face of a threshold, which we will refer to as
thresholded minimum error rate training (TMERT).43[4] present a method to improve the efficiency of exact MERT, but it is still significantly less efficient and more complicated than approximate solutions.
4
Our implementations is available open source at http://phontron.com/tmert

8

NAIST at CLEF 2013 QA4MRE

Fig. 3. Minimum error rate training with thresholds.

Figure 3 demonstrates our proposed algorithm, emphasizing parallels anddifferences to traditional MERT. The first difference is that for each answer liney = cx + d in Figure 2 (b), we add an additional threshold line y = cx + d + t
raised by t. This encodes the information that if a particular answer line for
aj,k1 is less than or equal to the threshold line for aj,k2 , aj,k1 has failed to exceed
aj,k2 by t, and thus no answer should be returned. To find the response that will
be provided by the system for any region in Figure 3 (b), we examine not theline with the highest score, but the line with the second highest score. For eachrange where the second highest line is an answer line for aj,k1 , we know the firsthighest line is the corresponding threshold line for aj,k1 , so aj,k1 has exceeded
all other answers by at least t and thus will be returned as the answer by thesystem. For each range where the second highest line is a threshold line, we cantell that the margin between the first and second answers is less than t, and thus
the system will return no answer.
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 thequestion was unanswered. Given these statistics, we can calculate accuracy formeasures that reward non-response such as c@1 and choose a value of wi thatminimizes 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 thethreshold t; having large weights is equivalent to having a small threshold, andvice-versa. Thus, any t > 0 will have the same effect on our thresholded learningalgorithm, so we simply set t = 1.5

5

It is also possible to more efficiently adjust the scale of w by taking an additional
TMERT optimization step for a scaling factor λ, then scale w ← λ̂w.

Inter-sentence Features and TMERT for Question Answering

5

Evaluation

5.1

Experimental Setup

9

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, classified 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
confidence. While the main task is quite similar to the past years, this year eachquestion contains “none of the above” as a candidate answer.
To train the parameters of our model, we use both test set documents frompast CLEF 2011 and 2012 QA4MRE campaigns [9]. As they provide 120 + 160
question with correct answers, we use this as our primary training data. We train
the weights of the features using the described TMERT training algorithm. After
training, the system achieved 112 correct answers, 15 answers with no candidate,and 153 wrong answers, yielding a c@1 score of 42% on the training data.
5.2

Main Task Results

We submit a total of 2 runs for the main task separating the results from different
strategies. Run1 uses the strategy of choosing some answers as “none of theabove” as mentioned in Section 2.4 while Run2 does not.
Run1
Run2
Main +Aux Main +Aux
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
Topic

Table 1. Result of Participation in Main Task

First, we show the results as measured by c@1 in Table 1. Our strategy inRun1 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 benefit.
Overall, the system’s best topic is “Alzheimer” and worst topic is “AIDS”.
The accuracies for the topic “Music and society” and “Climate change” arerelatively similar. However as we did not use any form of knowledge except

10

NAIST at CLEF 2013 QA4MRE

reading the document itself, we cannot provide further analysis on why oursystem is good or bad at certain topic.
The results in Table 1 also indicates that the system is relatively weak at themain questions. In particular taking a look at the sample question r id=5 andq id=6:
Of all Cramer’s works, the one that has had the greatest enduring value ishis 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 effectively
4. because it shows the influence of Scarlatti
5. none of the above
The system return the answer of “1” because there are many matching keywordsof the candidate answer and question in the same sentence and our anaphoraresolution module failed to match the word “This” as “Studio per il pianoforte”.
However, our inter-sentence features are also able to answer some questions thatneed an inter-sentence analysis (taken from r id=7, q id=9):The major Hollywood studios of the so-called Golden Age (c1935-55) wereMGM, Paramount, RKO, Warner Brothers and 20th Century-Fox. Eachhoused 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 films in the GoldenAge?
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, whichfinds a distance of one between the question and candidate answer. The question
matched the first 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 final 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 scoreof 32.51%.

Inter-sentence Features and TMERT for Question Answering

611Conclusion

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, butlacks 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 toanswer the questions. Luckily our described framerwork for a linear combinationof 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 andthe background collections by adding more features.

References
1. Brill, E., Dumais, S., Banko, M.: An Analysis of the AskMSR Question-Answering
System. In: In Proceedings of EMNLP. pp. 257–264 (2002)
2. Chu-Carroll, J., Czuba, K., Prager, J., Ittycheriah, A.: In Question Answering,
Two Heads Are Better Than One. In: In HLT-NAACL. pp. 24–31 (2003)
3. Dang, H.T., Lin, J.J., Kelly, D.: Overview of the TREC 2006 Question Answering
Track 99. In: TREC (2006)
4. Galley, M., Quirk, C.: Optimal Search for Minimum Error Rate Training. In: Proceedings of EMNLP. pp. 38–49 (2011)
5. Jurafsky, D., Martin, J.H.: Speech and Language Processing. Pearson Education,
Upper Saddle River, NJ, 2 edn. (2008)
6. Koehn, P.: Section 9.3: Parameter tuning. In: Statistical Machine Translation, pp.
263–271. Cambridge Press (2010)
7. Och, F.J.: Minimum error rate training in statistical machine translation. In: Proceedings of ACL (2003)
8. Peñas, A., Rodrigo, A.: A Simple Measure to Assess Non-response. In: Proceedings of ACL. pp. 1415–1424. Association for Computational Linguistics, Portland,
Oregon, USA (June 2011)
9. Peñas, A., Hovy, E.H., Forner, P., Rodrigo, Á., Sutcliffe, R.F.E., Forascu, C.,
Sporleder, C.: Overview of QA4MRE at CLEF 2011: Question Answering for Machine Reading Evaluation. In: Petras, V., Forner, P., Clough, P.D. (eds.) CLEF
(Notebook Papers/Labs/Workshop) (2011)
10. Powell, M.: An efficient method for finding the minimum of a function of several
variables without calculating derivatives. The Computer Journal 7(2), 155–162(1964)
11. Salton, G., Buckley, C.: Term-weighting approaches in automatic text retrieval. In:
Information Processing and Management. pp. 513–523 (1988)
12. Tufis, D.: Natural Language Question Answering in Open Domains. The Computer
Science Journal of Moldova 19(2), 146–164 (2011)