Source-linked AI summary
Question Answering via Integer Programming over Semi-Structured Knowledge
Daniel Khashabi, Tushar Khot, Ashish Sabharwal, Peter Clark, Oren Etzioni, Dan Roth
TL;DR
Science questions often require combining facts beyond retrieval or statistical co-occurrence, motivating structured reasoning over text-derived knowledge. TableILP formulates answer support as an ILP over semi-structured tables, and it outperforms prior structured reasoning while complementing IR and PMI. It also shows greater robustness than PMI to simple answer perturbations.
Problem
Many science QA systems use retrieval or statistical correlation, while science questions can require multi-step inference that combines multiple facts.
Source: §1 · p. 1Method
TableILP searches for the best-supported answer graph by formulating support over a text-derived semi-structured knowledge base as an ILP.
Source: §1 · pp. 1–2, §3.3 · p. 3Results
Takeaways & Limitations
Abstract
from arXiv · showhide
Answering science questions posed in natural language is an important AI challenge. Answering such questions often requires non-trivial inference and knowledge that goes beyond factoid retrieval. Yet, most systems for this task are based on relatively shallow Information Retrieval (IR) and statistical correlation techniques operating on large unstructured corpora. We propose a structured inference system for this task, formulated as an Integer Linear Program (ILP), that answers natural language questions using a semi-structured knowledge base derived from text, including questions requiring multi-step inference and a combination of multiple facts. On a dataset of real, unseen science questions, our system significantly outperforms (+14%) the best previous attempt at structured reasoning for this task, which used Markov Logic Networks (MLNs). It also improves upon a previous ILP formulation by 17.7%. When combined with unstructured inference methods, the ILP system significantly boosts overall performance (+10%). Finally, we show our approach is substantially more robust to a simple answer perturbation compared to statistical correlation methods.
1 Introduction
Many natural-language QA systems retrieve explicit facts or exploit statistical word co-occurrence, but science questions may require combining facts through multi-step reasoning. TableILP searches for structured support in a semi-structured knowledge base and improves on prior structured reasoning and IR-based methods.
1 Introduction
- IR and statistical-correlation methods rely on explicit answer statements or question-word co-occurrence, but do not suit questions requiring multi-fact reasoning.The paper frames such reasoning as a key ability assessed by standardized science exams.Source: §1 · p. 1
- TableILP addresses questions that require chaining facts and combining evidence, such as inferring June from New York’s hemisphere and the timing of the summer solstice.Figure 1 depicts the support graph leading to June.Source: §1 · p. 1, Figure 1 · p. 1
- TableILP represents question constituents and table cells in a graph, then uses ILP constraints and preferences to select the best-supported answer.Its semi-structured knowledge base contains tables of natural-language instances of n-ary relations, and it uses SCIP to optimize the formulation.Source: §1 · pp. 1–2
- +14% absolute higher test score than the previous best structured MLN approach on unseen NY Regents science questions; combining TableILP with IR and PMI adds +10% absolute over IR alone.The evaluation used non-diagram questions from six years of 4th-grade science exams.Source: §1 · p. 2
- TableILP combines facts from multiple tables or rows, and its score exceeds an IR system using the same table-row knowledge by +10%.The system also improves on a previous ILP formulation by 17.7%.Source: §1 · pp. 1–2
- Under a simple incorrect-answer perturbation, IR and PMI performance drops relatively by 20% and 33%, respectively, while TableILP drops by 12%.The perturbations replace incorrect options with high-frequency strings from search results.Source: §1 · pp. 1–2
2 Related Work
Prior work combines retrieval, statistical association, rule-based reasoning, and ILP for science QA, while this paper adds constraints and preferences to the ILP component. The paper situates its approach between fact retrieval and formal reasoning, and distinguishes it from entailment and table-query work.
2 Related Work
- The system extends the earlier ensemble’s ILP model with additional constraints and preferences, including semantic relation matching, and improves its score by 17.7%.The earlier ensemble combined information retrieval, statistical association, rule-based reasoning, and an ILP solver operating on semi-structured knowledge [Clark et al., 2016].Source: §2 · p. 2
- Unlike factoid systems that retrieve explicit answers or formal scientific reasoners requiring logic or restricted English, this work targets natural-language questions needing combined information.The paper describes its goal as operating between those two extremes.Source: §2 · p. 2
- RTE focuses primarily on linguistic equivalence, whereas this work adds structured scientific reasoning and uses an RTE engine to compare table cells.The paper contrasts its approach with Natural Logic extensions to RTE.Source: §2 · p. 2
- Unlike prior ILP and table-query work focused on other NLP tasks or database queries, this system starts from a natural-language question and seeks its best-supported answer.The paper focuses on a semi-structured table representation for QA.Source: §2 · p. 2
3 QA as Subgraph Optimization
TableILP casts science question answering as selecting a well-supported answer subgraph over semi-structured tables, then optimizes that selection with ILP. Its design accommodates lookup, parallel evidence, table-to-table chaining, and semantic relations expressed in questions.
3.1 Semi-Structured Knowledge as Tables
- The knowledge base represents n-ary relations as tables whose natural-language headers define schemas and whose rows instantiate those relations.Different tables may express the same entity in different ways, creating an inference challenge.Source: §3.1 · pp. 2–3
3 QA as Subgraph Optimization
- TableILP treats QA as selecting the answer option with the strongest support graph over question constituents and table knowledge.The graph search is formulated as an optimization problem over a knowledge base of tables.Source: §3 · p. 2, §3.2 · p. 3
3.2 QA as a Search for Desirable Support Graphs
- A support graph links question constituents to one answer through table cells and optionally headers, using weighted entailment or similarity alignments.The augmented graph includes links for cells in the same row and for cells with their headers, and must be connected.Source: §3.2 · p. 3
3.3 ILP Formulation
- The ILP selects graph elements and alignments with binary variables, maximizing a weighted linear objective subject to constraints that encode desirable support.Alignment variables are instantiated only when their scores exceed a threshold.Source: §3.3 · pp. 3–4
Basic Lookup
- For basic lookup questions, the objective rewards question-to-table alignments while penalties and alignment limits discourage irrelevant tables and overly influential matches.The model seeks a row with high aggregate alignment to question constituents.Source: Basic Lookup · p. 4
Parallel Evidence
- For parallel evidence, TableILP can activate multiple rows in one table and requires those rows to use the same set of columns.A penalty for each active row helps restrict the graph to relevant evidence.Source: Parallel Evidence · pp. 4–5
Evidence Chaining
- For evidence chaining, the model aligns cells across tables and penalizes inter-table links while requiring semantically meaningful header joins.The paper describes chaining as a join between tables.Source: Evidence Chaining · p. 5
Semantic Relation Matching
- Semantic relation matching annotates related table columns and favors question alignments whose linguistic patterns express those relations.For example, the pattern “X to a Y” can match the fromTo relation between liquid and solid.Source: Semantic Relation Matching · p. 5
4 Evaluation
The evaluation tests TableILP on unseen NY Regents science questions against structured and unstructured solvers, then examines complementary performance, model behavior, ablations, and answer perturbations. TableILP outperforms the prior structured baseline and improves results when combined with IR and PMI.
4 Evaluation
- The hidden test set contains 129 questions, and a score difference of 9% is significant at the 95% confidence interval under the binomial exact test.The question set is divided into 108 development questions and 129 hidden test questions.Source: §4 · p. 5
- The Table Corpus includes 65 manually designed tables with about 5,000 rows and four Open IE-style tables with about 2,600 rows.Evaluation scores are percentages, with partial credit for ties that include the correct answer.Source: §4 · p. 5
4.1 Solvers
- TableILP selects seven tables and up to 20 overlapping rows per table, then solves an ILP with SCIP; the MLN baseline is Praline using 47,000 science rules.IR ranks matching sentences, while PMI ranks answer options by average n-gram co-occurrence.Source: §4.1 · pp. 5–6
4.2 Results
- +14% over the MLN baseline and +10% over IR using the same table knowledge; TableILP’s score was 43.8% for the preliminary ILP system.Table 3 reports the structured and same-knowledge comparisons.Source: Table 3 · p. 6, §4.2 · p. 6
Complementary Strengths
- TableILP answered 27 of 50 questions missed by PMI correctly, scoring 54% versus 25% random chance; its score on questions missed by IR was 47.6%.The ensemble of TableILP, IR, and PMI reached 69%, significantly improving over individual solvers.Source: Complementary Strengths · p. 6, Table 4 · p. 6
ILP Solution Properties
- TableILP uses about 4 seconds per question, versus 17 seconds for the MLN solver reasoning with four rules, and combines information from an average of 2.3 rows.The ILP is solved in 2.1 seconds on average; model creation takes 1.9 seconds.Source: ILP Solution Properties · pp. 6–7, Table 5 · p. 6
4.3 Ablation Study
- Restricting inference to one row drops performance by 10.5%, removing relation matching by 6%, removing Open IE tables by 9%, and replacing lexical entailment with word overlap by 11%.These ablations indicate contributions from multi-row inference, table semantics, Open IE knowledge, and lexical entailment.Source: §4.3 · p. 7, Table 6 · p. 7
4.4 Question Perturbation
- On 1,080 perturbed questions, TableILP’s score drops by 12%, while PMI drops by 33% relatively.The perturbation replaces incorrect options with frequent strings; TableILP also loses performance because answer-type matching is imperfect.Source: §4.4 · p. 7, Table 7 · p. 7
5 Conclusion
TableILP addresses science question answering by selecting a support subgraph from a semi-structured knowledge base and optimizing that selection as an ILP. It combines multiple facts and outperforms prior structured reasoning and IR comparisons in the reported experiments.
5 Conclusion
- TableILP treats question answering as support-subgraph selection over a semi-structured knowledge base and formulates the task as an ILP.The formulation supports combining multiple semi-formally expressed facts, which the passage says is outside the scope of IR-based QA systems.Source: §5 · p. 7
- The approach significantly outperforms both the previous best structured-reasoning attempt and an IR engine using the same knowledge.The passage also reports significant gains when TableILP is combined with unstructured IR and PMI methods.Source: §5 · p. 7
- Natural-language science questions are challenging because they require extensive domain knowledge and often combine multiple facts.The passage contrasts this with factoid retrieval.Source: §5 · p. 7
- The reported results suggest that structured inference with TableILP is viable and promising for natural-language question answering.Source: §5 · p. 7
A Appendix: ILP Model for TableILP
The appendix specifies TableILP as a weighted binary-variable optimization over a support graph. Its variables and constraints encode graph structure, answer correctness, and sparsity.
A Appendix: ILP Model for TableILP
- The ILP maximizes a weighted objective subject to linear constraints and integer-valued variables.The appendix introduces the objective weights and constraint coefficients before defining the full program.Source: A Appendix: ILP Model for TableILP · p. 9
Variables
- Basic variables are binary indicators for elements and pairs of elements, with pairwise variables representing support-graph edges.For example, a pairwise variable is 1 if and only if the corresponding edge is present; higher-level unary variables help impose structural constraints.Source: A Appendix: ILP Model for TableILP · p. 9
- Pairwise variables are created only for element pairs whose entailment scores exceed specified thresholds.The thresholds for creating these variables are listed in Table 10.Source: A Appendix: ILP Model for TableILP · p. 9
Objective function
- Every basic variable can contribute to the weighted objective, whose weights are set by Table 9; auxiliary variables linearize more intricate constraints.Auxiliary variables trade a larger variable set for linearized constraints.Source: A Appendix: ILP Model for TableILP · p. 9
Active variable constraints
- Active-variable constraints link element, pairwise, and higher-level variables so active rows correspond to active cells.The appendix also describes constraints relating unary variables to basic pairwise variables.Source: A Appendix: ILP Model for TableILP · p. 9
Correctness and sparsity constraints
- Correctness constraints require exactly one answer option and a minimum number of question constituents, while sparsity constraints cap the number of knowledge-base tables used.The table cap is intended to avoid unreasonably long and likely error-prone answer chains.Source: A Appendix: ILP Model for TableILP · p. 9
B Appendix: Features in Solver Combination
The solver-combination appendix describes logistic regression that maps solver predictions and proof-graph properties to answer-option probabilities. It distinguishes solver-independent features from TableILP-specific features and includes structural constraints on the proof graphs.
Solver combination
- A logistic regression model combines predictions from all solvers to return a probability that each answer option is correct.Source: B Appendix: Features in Solver… · p. 9
Solver-independent features
- Solver-independent features are generated for each answer option from the scores assigned to all options by each solver.The passage introduces these features but does not enumerate them here.Source: B Appendix: Features in Solver… · p. 9
TableILP-specific features
- TableILP-specific features summarize constituent and choice alignments, active cells, graph edges, and ILP size.The listed features include average and minimum alignment scores, active-constituent counts and fractions, and logs of variable and constraint counts.Source: B Appendix: Features in Solver… · p. 9
Constraints
- Structural constraints tie active tables, rows, columns, cells, constituents, and answer options to active connected elements or alignments.These constraints require graph components to be supported by active variables and alignments.Source: B Appendix: Features in Solver… · p. 11
- Correctness and sparsity constraints select one answer option and limit active tables, rows, and columns.A lower bound on active question constituents requires use of the question definition in answering.Source: B Appendix: Features in Solver… · p. 11
TableILP-specific features
- When the question contains a “which” term, the model activates an auxiliary variable with objective weight 1.5.Source: B Appendix: Features in Solver… · p. 12