4.1 Question analysis

The first stage of the pipeline performs a detailed analysis to identify key elements of the question (such as focus, lexical answer type (LAT), question class, question category, etc.) used by later stages of the pipeline. The focus is the part of the question that refers to the answer, and typically encompasses the string representing the (lexical) answer type. (In the data we use, questions are posed in a declarative format, with stylized marking of question focus; this should not detract from referring to them as ‘questions’.) An additionally distinguishing characteristic of Jeopardy! questions is that they are always accompanied by a category. This category is not, strictly speaking, indicative of a semantic type; it simply provides an additional dimension to the broad question content. An example question, with category of Fictional Animals, is shown below.

1. (5) Fictional Animals: The name of this character, introduced in 1894, comes from the Hindi for ‘bear’.

In (5), the focus is ‘this character’, and the LAT is captured by the string ‘character’, which refers to the type of the answer sought. The notion of LAT complements that of semantic type of the answer, as it is crucial to Watson's ability not to be tied to any particular domain (for a detailed discussion, see Lally et al. (Reference Lally, Prager, McCord, Boguraev, Patwardhan, Fan, Fodor and Chu-Carroll2012)). The system employs various lexico-syntactic rules for focus and LAT detection, and also uses a statistical ML model to refine the LAT(s). As we discuss later, focus and LAT are used during decomposition.

The question analysis stage also includes several general purpose natural language processing (NLP) components, such as parser, named entity detector, coreference resolver, etc., which are used by almost all of the components in the rest of the pipeline. These NLP capabilities are described in detail in Lally et al. (Reference Lally, Prager, McCord, Boguraev, Patwardhan, Fan, Fodor and Chu-Carroll2012), together with an evaluation of their impact on end-to-end system performance. For this work, specifically, the decomposition recognizer relies on a PAS built over a syntactic parse of the input question, itself delivered by the English Slot Grammar (ESG) parser (McCord Reference McCord1989; McCord, Murdock and Boguraev Reference McCord, Murdock and Boguraev2012). The latter citation also offers details concerning the parse-to-PAS process. In particular, it explains the properties of a tree-to-PAS transformation, causing the latter to be represented as a graph, with cycles and multiple incoming edges to certain predicate nodes.

4.2 Hypothesis generation

Following question analysis, the pipeline issues several queries derived from the question – largely based on syntactic and semantic relationships in it – to search the corpus of Watson's knowledge resources for relevant documents and passages, and then uses a variety of candidate answer generators to produce a list of hypotheses: candidate answers to the question. For details on effective query formulation against Watson's different knowledge sources, and on passage retrieval and candidate answer generation, see Chu-Carroll et al. (Reference Chu-Carroll, Fan, Schlaefer and Zadrozny2012b).

The configuration of Watson applied to the Jeopardy! challenge used a broad variety of content sources, primary among which were Wikipedia and Wiktionary; the motivation for source selection is presented in Chu-Carroll et al. (Reference Chu-Carroll, Fan, Schlaefer and Zadrozny2012c). Nothing about the decomposition task suggests that enhancing Watson for decomposition would require different, or additional, resources. In fact, during the experiments evaluating our approach to decomposition (Section 7), the content sources were held constant.

4.3 Hypothesis and evidence scoring

The system gathers supporting textual evidence from the corpus for each candidate answer and attempts to compute a match (or a degree of alignment) between the question text and the supporting passages found for a given candidate. For this, it uses a wide variety of answer scorers to evaluate the evidence. For Jeopardy!, Watson deployed over thirty answer scorers; detailed descriptions of some of them can be found in Kalyanpur et al. (Reference Kalyanpur, Patwardhan, Boguraev, Lally and Chu-Carroll2012a); Murdock et al. (Reference Murdock, Fan, Lally, Shima and Boguraev2012a, Reference Murdock, Kalyanpur, Welty, Fan, Ferrucci, Gondek, Zhang and Kanayama2012b); and Wang et al. (Reference Wang, Kalyanpur, Fan, Boguraev and Gondek2012).

We make a special note here of the role of the Jeopardy! category provided with the question. While most of the answer scorers focus on the information provided in the question, some of the scorers also use the set of terms in the category as topically related words for the answer. The category words, therefore, play a role in answer scoring and contribute to the final confidences of the candidate answers.

We highlight the role of the Jeopardy! category terms because the question re-writer (described in Section 6) relies on categories to ensure that none of the contextual information is lost in the sub-questions.

4.4 Candidate ranking

Finally, the system uses ML models to weigh the analyzed evidence and rank the candidate answers. The models (Gondek et al. Reference Gondek, Lally, Kalyanpur, Murdock, Duboue, Zhang, Pan, Qiu and Welty2012) generate a confidence for each candidate being the correct answer to the given question, and the system answers with the top-ranked candidate. Watson can also choose to refrain from answering if it has a low confidence in all of its candidates. This ML framework – a logistic regression classifier – is used in the base system independent of decomposition processing, which, as we will see below, deploys its own ML for answer synthesis and re-ranking (cf. Figure 1).

5.1 Decomposition patterns

There are numerous syntactic cues that are reliable indicators for decomposition, and it is predominantly such cues we exploit for driving the recognition and typing of decomposable questions. These include: ways in which clauses are embedded into subordinate positions, ways in which arguments cluster around an underlying predicate, distinctions between ‘bare’ and ‘information-rich’ noun phrases (essentially relating the syntactic structure of a noun phrase to constraints on its head noun), and so forth. For instance, the insight that a subordinate clause usually expresses an independent fact about an entity, within a larger question, leads to a conceptualization that patterns for detecting such subordinate constructions would identify questions as candidates for decomposition. In Section 5.1.1 we present a detailed example of such category of patterns.

As we discuss later in Section 7.2, we have no ground truth for question decom- positions, and therefore have to rely on our intuitions – rationalized by data analysis of complex decomposable questions – to articulate cues like the ones listed above.

Even though pattern-defining notions like clause subordination and embedding, and pre- and post-modification of head nouns, are inherently syntactic, our decomposition framework is designed to operate over the PAS derived from the syntactic parse of the question. We use PAS graphs (see Section 4.1), instead of parse trees as output by the ESG parser, since they provide a simplified view over ‘raw’ syntactic trees, as well as normalize across ranges of different tree structures which express essentially the same meaning (McCord et al. Reference McCord, Murdock and Boguraev2012), offer detailed description of PAS, its relationship to syntactic output, and the process of parse-to-PAS transformation. An extra level of convenience is provided by the PAS retaining the dependency labels from the original syntactic representation (as illustrated in Figure 3: in essence, the PAS is not only stating that a predication introduce[X,character,in(1894)] holds, but also that its syntactic realization was that of a non-finite verb phrase modifying a noun, nnfvp, as indicated by the incoming edge label to the ‘introduce’ node).

Fig. 3.

PAS graph for ‘The name of this character, first introduced in 1894, comes from the Hindi for “bear”’: an example of independent subtrees.

We identify three major categories of syntactically informed decomposition patterns: independent subtrees, composable units, and qualified segments. Patterns are implemented as rules matching over (PAS) graphs. Pattern categories are realized as rule sets. The specific rules underlying an implementation depend on the language style, domain, and syntactic analysis framework deployed by a particular QA system configuration. Across decomposition frameworks targeting different base systems, rules may, or may not, have to be modified (consider, for instance, that different analytical frameworks will have different ways of representing non-finite verb clauses). We emphasize, however, that the three pattern categories above are general, in the sense that they capture relationships between syntactic characteristics of a question and its status with respect to decomposability (namely, subordinate clauses, of which non-finite verb phrases are one instance, are indicative of a decomposable question). Thus, differences in rule sets implementations do not affect our analysis of syntactically cued decomposition recognition.

Table 1 shows example decompositions within pattern categories; note that within a category, typically there are rule sets for parallel and nested decomposition types. Overall, we have the order of 120 rules for nested decomposition, and seventy for parallel. (The smaller number of rules for parallel decomposition is attributable to the fact that the syntactic composition of two independent facts is simpler than that for nested ones.)

Table 1.

Decomposition categories and examples

More than one rule set may trigger over the same question; for clarity, we only show, in the third column, the result of activating the particular rule set, in the first column, over an example question, in the second column. When multiple decomposition hypotheses are at play, decisions about which rules do eventually apply to a question are deferred to the decomposition filters (Section 5.2) and the ML approach for weighing the contributions of rules (Section 6.2).

5.1.2 Composable units

An alternate strategy for identifying sub-questions is to ‘compose’ a fact by combining elements from the question. In contrast to the previous category, the ‘composable units’ rules combine separate parts of the PAS into a fact. For instance, a sub-question can be created by associating the focus head with its premodifiers and postmodifiers. If the premodifiers and postmodifiers are sufficiently specific, we obtain reasonably independent sub-questions, with parallel-decomposable behavior.

Three parallel decomposition rule sets are defined in this category: verb-args, focus-mod, and triple (see Table 1, row (2.P)). The rules in verb-args ‘compose’ a fact from the verb and its arguments (subject, object, PP complements). The focus-mod rules combine the head of the focus NP with its modifiers to generate a sub-question. Triple rules are similar to verb-arg rules in that they also generate facts by bridging across arguments to an underlying predicate, but unlike the verb-arg rules, this composition always links only two of the arguments to the underlying predicate, creating e.g. subject–verb–object or subject–verb–complement triples. The resulting facts state fewer constraints compared to full question predications, and are thus more likely to retrieve an answer-bearing passage.

Here also, a particular configuration around the focus may indicate a question requiring nested processing. For nested, the ‘composable units’ category has two rule sets: explicit-link and descriptive-np (Table 1, row (2.N)).

In contrast to questions where modifiers of the focus can be cues for parallel decomposition (i.e. the focus-mod rules above), the ‘explicit-link’ rules detect nested decomposition, signaled by the focus itself being a modifier. Figure 4 is an example for this type of rule set, applied to the PAS graph of the question: ‘To honor his work, this man's daughter took the name Maria Celeste when she became a nun in 1616’. Here the focus (‘this man’) is a possessive determiner to an underspecified node (‘daughter’). Intuitively, traversing the graph without descending to the level of the focus would ‘carve out’ an inner sub-question itself focused on that underspecified node (‘daughter’): ‘[this] daughter took the name Maria Celeste when . . .’ (also see Table 1, row (2.N)).

Fig. 4.

Example of composable units.

Operationally, the two upper triangles in Figure 4 denote the sub-graphs which describe aspects of the inner sub-question: the basic predication covering the ‘daughter’ node and a vsubconj (‘when’) post-modification to it. The sub-question itself is composed as concatenation of the corresponding question fragments. The bottom triangle in the figure demarcates the skeleton of the outer sub-question. Answering (the inner) with ‘Virginia Gamba’ allows the framework to plug it into the outer sub-question.

Two inter-related rules play part in this decomposition. The first detects a syntactic configuration indicative of nestedness (focus node in modifier position to a higher node):

• 

The second is very similar to the decomposableFact rule introduced earlier, for parallelly decomposable questions, but here we require additionally that FactAnchor participate in both inner and outer sub-questions:

• 

The ‘descriptive-np’ rule set finds ‘parenthetical’ descriptions of underspecified nouns in the primary question, as in e.g. ‘This arboreally named area was made famous by [a prince in the region noted for impaling enemies on stakes]’: the nested-decomposable nature of this question is captured in the descriptive phrase (in square brackets) functioning as an inner sub-question.

5.1.3 Qualified segments

This category of rules covers situations where the modifier of the focus is a relative qualifier, for instance ‘the first’, ‘only’, ‘the westernmost’, and so forth. In such cases, information from another clause is usually required to complete the relative qualifier: consider e.g. the incomplete (underspecified) ‘the third man’ versus the fact ‘the third man . . . to climb Mt. Everest’). For configurations like these, rules in this category combine the characteristics of ‘composable units’ rules with those of ‘independent subtrees’. An example decomposition for ‘Winning in 1965 and 1966, he was the first man to win the Masters golf tournament in two consecutive years’ is shown in Figure 5. Having detected a suitably qualified focus node, we find the larger sub-graph above it representing the basic predication over the focus (the top triangle in Figure 5), and the sub-graph below it, for the supporting relative clause elaborating on the qualification (the bottom triangle). We ‘compose’ these to derive a sub-question. As illustrated in Table 1 (row (3.P)), for parallel decomposition our rule set covers sub-questions expressed as superlatives. We do not have any rules of this type for the nested case.

Fig. 5.

Example of qualified segments.

5.2 Decomposition filters

All three pattern categories above rely only on a syntactic analysis of the question. When rules fire, they also identify question segments proposed as sub-questions.

Patterns tend to over-generate. Left unconstrained, they suggest decomposition of questions that are, arguably, not decomposable to begin with. For example, the triple rule set for parallel decomposition incorrectly decomposed Example (6), to derive ‘Charles Dickens called it’ as a sub-question. Similarly, the descriptive-np rule set for nested decomposition incorrectly decomposed Example (7) generating the inner sub-question: ‘This tiered steeple of St. Bride's Church in London’.

1. (6) Holiday Stuff: In an 1850 essay Charles Dickens called it ‘that pretty German toy’

2. (7) Architecture & Society: The tiered steeple of St. Bride's Church in London inspired the traditional form of this festive item

Also, by themselves, the rules cannot guarantee that the sub-questions are specific enough to point to a single answer. For example, the facts ‘this controversial 1979 war film’ and ‘this quaint old brownstone building’ are syntactically identical. From a semantic point of view, however, the first fact is more likely to point to a unique answer as opposed to the second one, underscoring the fact that it is unrealistic to rely solely on syntax for decomposing questions.

To mitigate against the rules over-generating, we apply the following heuristic filters to the proposed sub-questions. The set of filters was developed and tuned on the basis of error analysis.

We look for decomposable facts pertaining only to the question focus. We discard sub-questions that do not contain either a named entity, a quoted string, or a time or date expression (these are detected by the ESG parser): cf. ‘this quaint old brownstone building’. Additionally, we discard sub-questions that almost completely overlap the entire question or a sub-question from a prior rule. A partial priority order is imposed on rule application, based on observations of how informative the facts generated by a rule are; this order is reflected on a per-type basis in Table 1: e.g. within type row (2.P) we prefer verb-args to triple since the latter tends to produce less constrained facts than the former: cf. ‘Charles Dickens called it’.

Some statistics concerning how often rules are activated, in an end-to-end system configuration, are given in Section 7.3. Below we offer an estimate of the relative sizes of parallel- and nested-decomposable questions, detected on a per-rule category basis.

5.3 Analysis

In Section 7.2 we discuss the difficulties of creating a reliable gold standard for decomposable questions, made even more challenging by the fact that there may well be multiple ways to decompose a question, and that the utility of different decompositions (and therefore the choice of an optimal one) tends to be tied to the overall content of the background corpus.

In this paper, we are primarily interested in the impact of the decompositions on end-to-end QA performance (see Section 7.3). Still, even without component-level evaluation, we can get an estimate of the coverage of the decomposition recognizers. Table 2 presents a distribution of the decomposition pattern categories after applying the recognizers to a batch of 517 representative Jeopardy! questions used as our development set (Section 7.1).Footnote ⁵ Approximately 50% of the questions are identified as parallel decomposable, and about 25% are identified as nested. The recall of the recognizers is not clear from this, but Table 2 does give an idea of the proportion of questions that go through the question rewriting and answer re-ranking process later in the decomposition framework.

Table 2.

Distribution of rule types

6.1 Question rewriting

For parallel decomposition, the goal is to solve the original question Q by solving sub-questions independently and combining results appropriately. For example, consider the Jeopardy! questionFootnote ⁶

1. (8) Historic People: The life story of this man who died in 1801 was chronicled in an A&E Biography DVD titled ‘Triumph and treason’

We get two decompositions:

1. Q₁: This man who died in 1801

2. Q₂: The life story of this man was chronicled in an A&E Biography DVD titled ‘Triumph and treason’

Submitting sub-questions– unmodified – to the base QA system raises at least two problems. Sub-questions are often much shorter than the original question, and in many cases no longer have a unique answer. Moreover, some of the information from the original question that was dropped in a sub-question may be relevant contextual cues that the QA system needs to come up with the correct answer. Q₁ above illustrates these problems: it does not have a unique answer, and suffers from a recall problem (the correct answer is not in the candidate answers list of the base system when it considers this sub-question alone).

Our solution is to insert contextual information into sub-questions. In a two-step process for a sub-question Q₁, we obtain the set of all named entities and nouns (ignoring stopwords) in the original question text outside Q₁, and we insert these keywords into the original question category. In Jeopardy! questions, the category field is the context/topic information which the underlying QA system needs in order to use the decomposition framework, as stated in Section 3. In general, a QA system may derive such information in a variety of ways, e.g. by exploiting the problem description in a technical assistance QA setting, or a patient's medical history in a medical QA setting. What is important here is that the base system treats such information differently from the question itself. Rewriting takes advantage of this differential weighting to ensure that the larger context of the original question is taken into account when evaluating a sub-question, albeit with less weight.

The rewritten Q₁/Q₂ for Example (8) are:

1. (8-1) Historic People (A&E Biography DVD ‘Triumph and Treason’): This man who died in 1801

2. (8-2) Historic People (1801): The life story of this man was chronicled in an A&E Biography DVD titled ‘Triumph and treason’

The keywords are inserted in parentheses, to ensure a clear separation between the original category terms and the context terms added. Other systems may need a different rewriting tactic.

The above rewriting technique is used for both parallel and nested decomposable questions. For the nested case, there is an additional rewriting step that needs to be done – after solving the inner question, we need to substitute its answer into the outer when solving for it. Thus, the first example in Table 1, row(1.N) would have its inner focus ‘When “60 Minutes” premiered” replaced with ‘In 1968’ creating the outer question ‘In 1968, this man was US President’ whose solution is the answer to the original question.

6.2 Candidate answer re-ranking: parallel

The base QA system will process the rewritten category/sub-question pairs, and will produce a set of ranked candidate lists with confidences (cf. Section 4.4). These need to be combined into a final answer list for the original question, accounting for information across all sub-question candidate lists.

If the score for a candidate answer generated by the base QA systems corresponded to a probability that this answer was correct, and if the sub-questions derived by decomposition were independent, a final score for each candidate answer to the original question could be calculated as a product of the scores for all of its sub-questions. These assumptions, however, are not valid. The confidence of a candidate answer is not a probability – in the strict mathematical sense – that it is correct (cf. Sections 3 and 4.4). Also, even if sub-questions were independent of each other, question rewriting breaks this assumption as it brings information from the remainder of the question into the sub-question context.

Furthermore, the sub-questions are generated by decomposition rules that have varying precision and recall, and thus should not be weighted equally. If the rules’ quality could be evaluated precisely, by itself, an approach could be designed to weigh them appropriately when generating the final confidence. But, as we discuss in the evaluation section (7.2), this is impractical, given the difficult nature of creating a question decomposition gold standard. We also have to consider the possibility of bad (and wrong) sub-questions – e.g. due to a bad parse – when a fall-back to the original question would necessitate that the confidence for the candidate answer for the entire question be also considered in making a final decision.

For all these reasons we use a ML approach to combine information across sub-question answer confidences, with features designed to capture the above information. The features used in the model are shown in Table 3; for features associated with specific rules, the value of a feature is the answer confidence for a decomposed sub-question found by the rule. In case a candidate answer is not in the answer list of the full question or any of the decomposed sub-questions, the corresponding feature value is set to missing. If a rule generates multiple sub-questions, its corresponding feature value for the candidate answer is set to the sum of the confidences obtained for that answer across all sub-questions. The model is trained using Weka's (Witten and Frank Reference Witten and Frank2000) logistic regression algorithm with instance weighting.

Table 3.

Features in parallel re-ranking model

6.3 Candidate answer re-ranking: nested

Nested questions decompose into inner/outer question pairs. The task is to solve the inner question first, substitute the answer obtained, based on its confidence, into the outer, and solve that for the final answer. This is contingent upon selecting answers to the inner question which might profitably be plugged into the outer; substituting incorrect answers will only lead to noisy final answers, with negative impact to overall accuracy.

We rely on the ability of the underlying QA system to produce meaningful confidences for its answers, and only consider the top answer to the inner question for substitution into the outer – if its confidence exceeds some threshold.

Finally, the answers to the outer question need to be related to the full question answer list to produce the final ranked answers. For answer re-ranking, we use the following heuristic selection strategy. For the answer obtained through decomposition and rewriting, we compute aggregate confidence as the product of the inner-question answer confidence and the outer-question answer confidence. We then compare this value with that of the confidence for the top answer to the entire question, as computed by the base QA system (see the left-most pathway in Figure 1). The answer with the higher confidence is then selected as our final answer. Note that this re-ranking strategy is different from the one used in parallel decomposition where we combine results from multiple sub-questions into a single confidence.

7.1 Evaluation data

As we already mentioned (in Section 1), the Jeopardy! data contains a set of questions which are particularly challenging. Final Jeopardy! questions are often long and complex, with multiple facts or constraints that need to be satisfied. Frequently, the nature of these makes it unrealistic to expect that all of them will be articulated within a single, brief passage in our content sources. This is not a statement specific just to the corpora we prepared for Jeopardy! (Chu-Carroll et al. Reference Chu-Carroll, Fan, Schlaefer and Zadrozny2012c). Finding the answer to such questions typically requires additional processing, implementing some kind of a one-or-more hops across intermediate stages of answer determination (Chu-Carroll et al. Reference Chu-Carroll, Fan, Schlaefer and Zadrozny2012a). Question decomposition, in the sense we discuss in this paper, is one such strategy, and FJ questions can significantly benefit from our decomposition approach. Example (5) in Section 4.1 earlier illustrates the decomposition-related characteristics of an FJ question.

FJ questions are also typically much harder to answer than regular Jeopardy! questions, both for humans (based on statistics mined from the website; see Section 7.3) and for our base QA system (based on its performance over FJ questions as compared with regular Jeopardy! questions). The test set comprises close to 3,000 FJ questions, broken into 1,138 for training, 517 for development, and 1,269 questions for testing (as blind data). Since we do not have a gold standard for decomposable questions (see Sections 5.1 and 7.2), this split was made randomly.

7.2 Experiments

The decomposition rules (Section 5) and re-ranking parameters (Sections 6.2 and 6.3) were defined and tuned on the development set. The final re-ranking model was trained over the training set, using the features described in Section 6.2, and logistic regression with instance weighting: the negative instance weight was set 0.25 times lower, based on analysis over the development set, and reflecting the fact that the underlying QA system generates many more negative answers than positive.

The results of applying the decomposition rules followed by the re-ranking model to 1,269 test questions are shown in Table 4. The row labeled ‘Baseline’ is the performance of the underlying QA system used in our meta-framework without any decomposition components, applied to the same test set.

Table 4.

End-to-end QA evaluation (1,269 test questions)

We evaluated separately the impact on parallel decomposition of our question rewriting strategy (cf. Section 6.1), which maintains contextual information from the original question into the sub-questions (‘QR’ in Table 4 stands for Question Rewriting). For this purpose, we altered our algorithm to issue the sub-question text as-is, using the original category (without rewriting), retrained the model, and evaluated the resulting model again on the test set. The results are shown in the row labeled ‘Parallel (no QR)’. The results for parallel, and separately nested, decomposition with question rewriting are in the rows labeled ‘Parallel (with QR)’ and ‘Nested (with QR)’, respectively. Finally, the row labeled ‘Parallel + Nested (with QR)’ contains the end-to-end performance of the QA system with both parallel and nested decomposition (with rewriting) enabled.

Table 5 presents an end-to-end QA performance on just the ‘decomposable’ subset of test questions: namely, the set of questions recognized as decomposable by our decomposition recognizers. For parallel decomposition, the system judged 598 of the 1,269 test questions to be decomposable. On the other hand, only 255 questions triggered nested decomposition. Like Table 4, this table too presents QA performance for the system without decomposition (in rows labeled ‘Baseline (no decomposition)’), performance of parallel decomposition without and with question rewriting (in rows labeled ‘Parallel (no QR)’ and ‘Parallel (with QR)’), and performance of nested decomposition with question rewriting (in the row labeled ‘Nested (with QR)’).

Table 5.

QA accuracy on decomposable subsets

We do not offer separate analysis of decomposition recognition. As we mentioned in Section 5.1, there is no gold standard for question decomposition. Manual creation of such a standard is highly nontrivial, largely due to the numerous alternative ways to decompose a question, and to synthesize unique facts from the segments (a particular issue here is that the effectiveness of a given decomposition is affected by the content in the entire underlying corpus). Indeed, this is precisely the motivation for weighting the decomposition rules in a trained re-ranking model (Section 6.2). Given this, we are interested only in measuring the impact of decomposition on end-to-end QA performance.

7.3 Results and discussion

One observation from Tables 4 and 5 is that according to our rules – which, when constrained by the decomposition filters, are reasonably precise – significant percentage of FJ (blind test) questions have decomposition potential. Given that our data analysis separately established that decomposition would help in solving FJ questions (Section 7.1), this offers some validation of the decomposition recognition rules – even though without ground truth for decomposable questions, we cannot perform accuracy analysis.

The parallel decomposition rules were able to decompose a large fraction of the test set (598 out of 1,269 questions: 47%). Interestingly, the performance of the baseline QA system on the decomposable set was 56.6%, which is 6% higher than the overall performance over the entire test set. One reason for this result would be that parallel decomposable questions typically contain more information (more than one fact or constraint that the answer must satisfy) about the same answer, and the system in some cases is able to exploit this redundancy – such as when one fact is strongly associated with the correct answer and there is evidence supporting this in the sources.

A different, important result is that using the decomposition algorithm without question rewriting did not show impact over the baseline. This highlights the importance of contextual information for QA. On the other hand, when using rewriting to maintain context (Section 6.1), our parallel decomposition algorithm was able to achieve a gain of 1.4% on the parallel decomposable question set, which translated to an end-to-end gain of 0.6%.

Separately, Table 5 shows that roughly a fifth (255 out of 1,269 questions) of the entire test set were recognized as nested decomposable. The performance of the baseline QA system on the nested decomposable set was roughly the same as the overall performance (and much lower than the parallel decomposable cases). The likely explanation here is that nested questions require solving for an inner fact first, and it is the answer to this which often provides the necessary missing information required to find the correct answer: this staged dependency makes nested questions much harder to solve than parallel decomposable ones with their multiple independent facts. Our nested decomposition algorithm using the heuristic re-ranking approach (Section 6.3) was able to achieve a gain of 2% on the nested decomposable question set, which translated to an end-to-end gain of 0.4%.

The aggregate impact of parallel and nested decomposition was a 1.5% gain in accuracy on the decomposable set, and a 1% gain on end-to-end system accuracy (in our case the questions that are classified as parallel or nested form disjoint sets).

To put these results in perspective, we emphasize that the baseline QA system represents state of the art in solving Jeopardy! questions. The FJ questions, which exclusively comprise our test data, are known to be harder than regular Jeopardy!: qualified Jeopardy! players’ accuracy on this kind of questions is 48%,Footnote ⁷ and the underlying QA system has an accuracy close to 51% on previously unseen FJ questions. A gain of 1% end-to-end on such questions, therefore, represents a strong improvement. Also, using the statistical McNemar's test (McNemar Reference McNemar1947), we found the net end-to-end impact to be statistically significant at a 99% confidence interval.

As we showed earlier in the paper, decomposition relies crucially on correctly instantiated PAS graphs corresponding to syntactic analysis of the questions. Given that the PAS builder is, in effect, a mapper for syntactic dependency trees, correct syntactic parses would ensure correct PAS structures. Thus, of all the NLP components in the question analysis pipeline (Section 4), the ones that make our approach to decomposition both viable and effective are the ESG parser and the focus and LAT detector: independent accuracy analysis of the parser shows it to perform in the 90 percentile for accuracy (92% over Jeopardy! data, and 88.7% over Wikipedia content) (McCord et al. Reference McCord, Murdock and Boguraev2012); similarly, the focus/LAT detection (itself also dependent upon the parser) performs at F1 = 0.796, with a very high per-question recall, 0.905.

We note that our error analysis of the test questions shows a wide variety of reasons for their failures beyond question decomposition. To further improve the system on this test set would require advances beyond deciding whether to take a single-shot or decomposable approach to questions, which is beyond the scope of this paper.

Broadly speaking, decomposable questions are questions which ‘over-specify’ the answer. Search queries derived from such questions are likely to result in recall failures – because the juxtaposition of multiple facts about the answer may not be encountered in a QA system's content sources. The decomposition-based approach to answering such questions relies crucially on the assumption that searching for separate, smaller facts which are independently true of the answer would be more productive than searching for co-located mentions of all the facts (Section 1).

It follows that processing decomposable questions via a conventional QA pipeline may lead to not enough support for the correct answer. On the other hand, processing sub-questions derived as fact-based decompositions will find more relevant passages for some, or all, of its decompositions, as relevance is now redefined with respect to sub-question-bound facts about the answer.

Our analysis of system logs corroborates this: We observe apposite supporting passages retrieved by the decomposition-enabled system for sub-questions, while the conventional system produced no recall for some of the facts in full questions. We are unable, however, to quantify this observation: not only due to the lack of gold standard for decompositions but also because we do not have an answer key for such sub-questions. Additionally, we do not have the scaffolding for side-by-side comparison of different system architectures to expose the differences between multiple interactions between passage scoring and candidate answer ranking introduced by different regimes of passage retrieval.

Nonetheless, our work substantiates the notion that there are intrinsic merits to fact-based decomposition when answering questions which may – for whatever reason (e.g.intended complexity, as in FJ, or the realities of complex domains such as financial consulting or medical diagnosis) – exhibit the characteristics of conflating multiple independent facts together in a single question. Detecting decomposable questions, deriving appropriate sub-questions, and composing the individually obtained answers correctly is a very hard task (as evidenced earlier in this section), in the light of which a performance boost as the one we report here is not just a significant improvement of a particular system but also indicative of the value of paying due attention to question details.