We present SFS-QA, an automatic realtime question-answering system, that can answer free-text questions within a minute. SFS-QA system analyzes a question and transforms it into a boolean keyword query using Stanford Dependency Parser and MetaMap tagger. The query is used to obtain matching web pages from the World Wide Web through Google Search API. In addition, two specific data sources: Yahoo! Answers and Wikipedia are used for matching the documents. The resulting web pages are mined for candidate answers. Finally, Learning to Rank based LambdaMart, and Recurrent Neural Network based BLSTM algorithms are used to learn, rank, and select the best answer from candidate answers. For empirical evaluation, TREC LiveQA 2015 and 2016 datasets which consist of about 1000 questions each were used. The results demonstrate that our system substantially outperforms strong baselines.
Even with modern search engines, there are many scenarios where the users struggle to find the information they are looking for. This is especially true when the information need is complex, and when the user is unable to distill down their information need into a few keywords. These factors motivate many users to seek answers on community based Question-Answering (QA) sites, such as, Yahoo! Answers1, and Quora2, where the question can be posted in natural language, as opposed to keyword query, and the answer(s) to the 1https://answers.yahoo.com 2https://www.quora.com question is provided by the members of the online community. Compared to the experience that users have with commercial search engines, the QA sites provide two key advantages: (i) freedom to specify their information need (question) in free flowing natural language, and (ii) convenience of receiving focused answer(s) to the question, as opposed to receiving 10 web pages that have to be read and parsed to identify the answer to the question. On the other hand, one clear advantage of search engines over QA sites is the information response time. The search results are available to the user instantaneously, whereas human-authored answers may take much longer to be posted.
These observations motivate our QA system that allows the user to specify the question in natural language, which in turn is internally transformed into a boolean query composed of key terms and phrases. Our approach works on the premise that the answers for the majority of questions are already available on some web page(s) on WWW. Thus the goal of the next phase of our system is to obtain these web pages, and extract concise answers from the content of the pages. An additional objective that we set for the QA system is to have low latency: every question has to be answered in less than one minute. This requirement influences many design decisions made for the system’s architecture.
The key contributions of this work are
designing and developing: (i) a light-weight but
effective question to query transformation approach
(ii) a multi-sourced document retrieval approach,
and (iii) a highly effective answer ranking
approach. A thorough empirical evaluation of
individual phases of the system, and of the
end-toend system was undertaken, which demonstrates
that the proposed QA system performs
substantially better than strong baselines while meeting
the response time requirement.
Liu et al. analyzed the difference between queries
and questions in the context of community QA
sites
Savenkov et al. introduced a new QA
system that uses multiple data resources such as
Wikipedia data, WWW, and Yahoo! Answer
Collection
Shtok et al. proposed a new approach to
answer a new question from CQA site such as
Yahoo! Answers by reusing past answers from
previous similar questions from CQA site itself
Pinter et al. introduced a new method that
applied a grammatical dependency parser to
identify segments of CQA questions to generate
queries
Soricut and Brill
Our QA system is structured as a pipeline of four components: Query formulation, Document retrieval, Candidate answer extraction, and Answer selection. The first module is responsible for parsing, and transforming the question into a query, that is used by the second phase to retrieve documents that may contain the answer, the third phase is tasked with identifying the minimal unit of text that answers the original question, and the fourth phase selects the unit of text that serves best as the answer to the question. The architecture of the system is shown in Figure 1. This module transforms free-text questions to a well-formed boolean conjunctive queries that can be evaluated by a search engine. This is a challenging problem because questions are often verbose. Questions often contain information that is useful for a human reader but is superfluous, or even misleading, if included in the search query. We address this verbosity problem at multiple levels.
First, not every sentence in the question
contributes to the final query. Only sentences that
start with WH-words (e.g. Who, When, Where,
Why) and end with a question mark do
The English closed class terms (pronouns, determiners, prepositions) in the question are often ignored since they do not capture the central topic of the question. However, in certain situations the prepositions should be included in the query. In case of the following question, “How much should I pay for a round trip direct flight from NYC to Chicago in early November?”, if the preposition words, from and to, are ignored then the information about the travel direction is lost. Preposition detection is used to address this issue where the grammatical tree structure of the sentence is leveraged to identify the preposition phrases, such as, from NYC and to Chicago, and these are included as-is in the boolean query.
The verb phrase is another important dependency phrase that the system needs to identify because sometimes single verb term is too broad, and thus not useful in retrieving relevant documents. However, in such circumstances the verb phrase provides a focused search query. As an example question, “How to map dowse using a pendulum?”, without the verb phrase detection, the system generates the query: (map) AND (dowse) AND (use) AND (pendulum). Once the query is run through a search engine, it might retrieve a distorted set of documents because the verb map is ambiguous between mapping either dowse or pendulum. The verb phrase detection, however, generates a more explicit query: (map dowse) AND (use pendulum) that is less likely to retrieve ambiguous result set.
All of the above transformations are necessary when the question is verbose. However, when the question is well-articulated and succinct, no transformations are performed. Questions with 8 words or less are considered concise, and used as search queries as-is.
A substantial fraction of the posted questions on
the community sites are related to health. These
questions also tend to have certain unique
properties, such as, the larger vocabulary gap between
the question and the content of the relevant
documents. A vocabulary gap exists between two
units of text when they use different vocabulary
to convey the same meaning. Since the questions
are authored by ordinary people they tend to use
the common names for diseases, conditions, and
symptoms, while the relevant documents written
by medical professionals/experts tend to use the
technical names for these concepts. As a result,
a document that is relevant to the question might
have very little word overlap with the question,
and thus not be retrieved. To avoid this, query
expansion is often proposed as the solution.
Doing effective query expansion for medical text is
a non-trivial problem. Fortunately there exists an
excellent resource, MetaMap tagger3, that we use
in our work for health category questions
In summary, the input to the Query Formulation Module is the user question, and QFM transforms it into a query, which is handed over to the next phase. 3.2
The goal of this module is to use the generated query to obtain a set of web pages that are likely to contain answer(s) for the question. First, however, it is checked if the current question has already been answered on Yahoo! Answers. If that is the case then the answer that has been voted as the best answer is returned by the system. Finding an exact match of the question on Yahoo! Answers is however a rare occurrence.
A targeted search is conducted on two online knowledge sources: English Wikipedia, and Yahoo! Answers. To facilitate faster query response time, we maintain a local copy of the English Wikipedia, and the query is run against this local copy. The top three wiki pages returned for the query are added to the set of answer-bearing web pages. We use Solr/Lucene to index and search the Wikipedia copy.
For Yahoo! Answers (Y!A), we use a twopronged strategy to provide short query response time. A local copy is maintained of the Webscope L6 dataset 4, which is a snapshot of the Y!A site captured in October 2007. This data consist of 4.4+ million questions and all the posted answers, along with metadata, such as, question category, and best voted answer. This data is also indexed with Solr/Lucene for efficient access and search. In addition to L6, the system is also capable of conducting a site search of Yahoo! Answers, in order to obtain the most up-to-date data. The site search functionality of Bing Search API is used to accomplish this. It was found that Google Search API is biased against Yahoo! Answers, and thus Bing was chosen for this task. The top three an3https://metamap.nlm.nih.gov 4https://webscope.sandbox.yahoo.com swer pages are added to the set of answer-bearing web pages.
Finally, the larger World Wide Web is searched using the Google Search API. The top three web pages returned for the query are added to the set of answer-bearing web pages. In total, this module identifies at most nine web pages that are passed on to the next module. 3.3
The set of web pages identified by the Document Retrieval Module are downloaded, and each page is passed through the following text processing pipeline. The first step extracts ASCII text from the web page using an html2text library5. We refer to the extracted text as a document. This document is next split into passages, where each passage consists of four consecutive sentences, the most popular answer length in Yahoo! Answers dataset. A sliding span of four consecutive sentences is used to generate the passages. Thus, a document containing five sentences would generate two passages. This approach generates many passages, specifically, 1 + (n 4), where n is the total number of sentences in the document. The passage length of four sentences was chosen based on data. On an average, high quality answers in the L6 dataset contain four sentences. Shorter answer lengths (single sentence) are common for factoid questions but majority of the L6 questions cannot be categorized as purely factoid.
Passages that do not contain any of the query terms, or that contain more than 2 line breaks, or more than 10 punctuation marks, or non-printable symbols are eliminated. Also, passages that are not in English are filtered out. The langdetect library6 is employed for language identification. All the passages that survive the filtering step are considered as candidate answers. 3.4
In this final step of the QA pipeline, the best
answer from all the candidate answers is chosen.
We experiment with three algorithms for this task:
(i) Learning To Rank (LeToR) based LambdaMart
algorithm
There is a rich history of LeToR approaches
being applied to automated QA
Recurrent Neural Network (RNN) based
approaches have received a lot of attention from the
QA community recently
The third answer selection approach that we investigate simply combines the above two approaches. The score assigned by BLSTM to each <question, answer>pair is used as an additional feature in the feature set used by the LLTR ranking algorithm. 4
We conduct a thorough empirical evaluation of the individual components of our system, and of the end-to-end system. The results of these evaluations are presented in this section. 4.1
Evaluation Data: Recall that QFM module is tasked with understanding the question, and compiling a set of web pages (URLs) that are likely to contain the answer(s) to the question. Evaluation dataset for this task is not readily available. We had to thus re-purpose the annotated datasets that are available for another task – questionanswer evaluation. Specifically, we used the TREC LiveQA 2015 and 2016 datasets, which consist of 1000 questions each. For each question there are one or more answers, and each answer is assessed for its relevance to the question by a human, and assigned a score between 0 (nonrelevant) and 3 (very relevant). The LiveQA 2016 dataset provides the source URL for each answer. For the LiveQA 2015 dataset we had to locate the source URL for each answer, since it is not included in the dataset. This gives us an annotated set of <Question,URL,score>tuples which we use to evaluate the effectiveness of QFM.
Baselines: The LiveQA 2015 and 2016 questions consist of three fields, title, body, and category. Since these questions are generated by real users the question can be either in title or in description. Based on this observations we have defined three baselines to compare with the proposed QFM: 1. Original-Q: This baseline tests the minimalist approach where no processing is performed on the question. The question is used as query as-is. Here the intuition is that since the questions are authored by humans, no information should be filtered out or added into the original question. As such, the question title, along with the body field is used as the query. 2. QuestionMark-Q: This baseline works with the assumption that humans often add superfluous details to the question, and these details typical occur in sentences that do not end with question mark. As such, sentences in title and body fields, that end with question mark are used as the query. 3. Unigram-Q: This last baseline seeks to filter out unnecessary information further by removing stopwords, and by applying morphological normalization using Krovetz stemmer to sentences ending with question mark in title and body fields. The terms that remain are treated as unigrams and compiled into a boolean AND query.
Evaluation Metrics: For the task at hand, the generated query is said to be effective if it can retrieve one or more answer-bearing web pages in the first three ranks, since these pages are mined for candidate answers in the next phase. As such, this is a precision oriented task, and thus inspires our choice of evaluation metrics: Precision@ranks1,2,3 and NDCG@ranks1,2,3. The latter models the different grades of relevance that are present in the annotation scores.
Results & Analysis: Table 1 reports the results for the three baselines and QFM with and without site search of Yahoo! Answers. It should be noted that URLs for which human scores are not available are considered non-relevant in this assessment. This is an important point that leads to overall low values seen in Table 1.
The prominent trend in these results is that QFM outperforms all the baselines substantially across all the metrics. The results for the OriginalQ baseline demonstrate that using the user question as-is often does not lead to relevant web pages. This justifies the need of a Query Formulation Module. The QuestionMark-Q results show that filtering out the sentences without question mark improves the performance by reducing
3 the unnecessary information and noise. But filtering out stopwords, and loosing the grammatical structure of the question completely is detrimental, which is demonstrated by the Unigram-Q results. As is described in Section 3.1, QFM attempts to balance two conflicting objectives: (i) distill down the question to the bear minimal query (ii) keep the necessary units of the question intact. These results indicate that this intuition behind QFM is correct. 4.2
Evaluation data: To evaluate the performance of ASM, we use the questions TREC 2015 LiveQA evaluation set. Since answers are rated by judges, it is possible to check how good our system is at ordering of these answers.
Baselines: For the baseline, we use the results
obtained by Encoder-Decoder system which was
the best performing system of 2016 year. They
were testing their version of ASM on 2015 data,
and therefore we can compare their system to ours
on this dataset
Evaluation Metrics: The effectiveness of the system was evaluated using standard evaluation: NDCG (Normalized Discounted Cumulative Gain), MAP (Mean average precision) at rank X, and MRR (Mean Reciprocal Rank) at rank X. Results & Analysis: Table 2 provides the results for the evaluation of the ASM. LLTR is less effective than the state-of-the-art approach across all the metrics. However, the neural network based approach, BLSTM performs substantially better than Encoder-Decoder and LLTR for both datasets. The results for LLTR+BLSTM illustrate that two approaches have complementary strengths that can be combined to obtain the best results for the task. The difference between LLTR and LLTR+BLSTM is statistically significant.
The results for MAP show that in 55% of the
cases our system selects the answer with at least
fair quality (2+), and in 21% of the cases the
quality is excellent. The performance on TREC
2016 is better than on TREC 2015. For
reference, Table 2 provides the performance of the
TREC 2016 LiveQA winning system –
EncoderDecoder
We believe that quality of the model can be
improved by sanitizing the training dataset.
Currently, two main problems are: (i) presence of
words with misspellings which make
computations of statistical features imprecise; (ii) quality
of the best answers manually selected by voters.
There exist a few approaches to diminish impact
of both issues such as
Evaluation data: For the end-to-end system evaluation, the existing datasets cannot be reused because the system generated answers can be different from the previously annotated answers. Thus, we undertook the task of manual assessment of the answers generated by our system. Each answer was rated on the same scale as in TREC LiveQA competition which is 0 (non-relevant) through 3 (very relevant). We selected at random 100 questions from LiveQA 2015, and 100 from LiveQA 2016, and assessed their respective answers on the 4-point scale.
Baselines: We compare our results with those
produced by the winning systems at TREC
LiveQA 2015, and 2016, the Open Advancement
of Question Answering (OAQA)
X=annotation score + 1. The avgScore is the average score of the answers produced by a system, where answer scores’ range is 0-3.
Results & Analysis: The results are presented in Table 3. Our system performed substantially better than the state-of-the-art for both 2015 and 2016. This is especially prominent at higher score levels, indicating that our system is able to generate better quality results. For 2015, the system produced 53% of answers which could be considered as fair, 40% questions as good, and 25% questions were considered as excellent answers. For the 2016, 67% of answers have a fair grade, 45% are good and 23% are excellent. The average scores, although higher than those of state-of-theart, indicate that there is plenty of room for improvement.
On an average, the system generates an answer for a submitted question in less than half a minute on a non-specialized commodity computer. The Query Formulation Module transforms the question into a query in 3 seconds, the Document Retrieval Module and the Candidate Answer Extraction Module together take 8 seconds to generate all the candidate answers, and the last module of Answer Selection needs 15 seconds to select the best answer, which amounts to 26 seconds per query, on average.
Table 4 presents examples of the user questions, the corresponding queries, and the answers generated by SFS-QA system. The first example includes an instance of query expansion using MetaMap. The scientific name of bats, Chiroptera, is sourced from MetaMap. The query generated for the second question shows an example of verb phrase and adjective phrase. Other queries also show examples of noun phrases. In general, these examples illustrate how the QFM module retains the important bigrams and phrases while reducing the superfluous terms. The generated answers, more often than not, provide the necessary information, at least partially. 5
We presented an automated question answering system that accepts questions in natural language and responds with a focused answer in less than half a minute. With thorough empirical evaluation we demonstrated that a light-weight questionto-query transformation module can be developed that is also highly effective. We also illustrated SFS-QA OAQA SFS-QA Encoder-Decoder 0.250 0.190 that various existing information sources can be leveraged to obtain answer-bearing web pages. Finally, we established that advances in deep learning can be utilized to select the best answer for the question.