Source-linked AI summary
Compositional Semantic Parsing on Semi-Structured Tables
Panupong Pasupat, Percy Liang
TL;DR
Semantic parsing needs to handle both broad, open-ended knowledge sources and deep logical compositionality, but rigid schemas restrict answerable questions and deeper composition creates many spurious logical forms. This paper introduces question answering over HTML tables, using graph-based logical forms and compositional operations, and evaluates it on a new Wikipedia-table dataset, achieving 37.1% accuracy versus 12.7% and 24.3% baselines.
Problem
Rigid schemas restrict the scope of answerable questions, while deeper compositionality creates many nonsensical logical forms that can execute to correct denotations.
Method
The paper represents tables as graphs with augmented Next and Index edges and uses lambda DCS logical forms combined through compositional operations.
Results
37.1% accuracy on unseen tables exceeded the information retrieval baseline of 12.7% and the simple semantic parsing baseline of 24.3% on WIKITABLEQUESTIONS.
Takeaways & Limitations
The work simultaneously increases knowledge-source breadth and logical compositionality for semantic parsing on semi-structured tables.
Takeaways & Limitations
The approach is scoped to HTML tables, with future work proposing broader semi-structured formats and general web pages as knowledge sources.
Abstract
from arXiv · showhide
Two important aspects of semantic parsing for question answering are the breadth of the knowledge source and the depth of logical compositionality. While existing work trades off one aspect for another, this paper simultaneously makes progress on both fronts through a new task: answering complex questions on semi-structured tables using question-answer pairs as supervision. The central challenge arises from two compounding factors: the broader domain results in an open-ended set of relations, and the deeper compositionality results in a combinatorial explosion in the space of logical forms. We propose a logical-form driven parsing algorithm guided by strong typing constraints and show that it obtains significant improvements over natural baselines. For evaluation, we created a new dataset of 22,033 complex questions on Wikipedia tables, which is made publicly available.
1 Introduction
The paper targets semantic parsing that combines broad, open-ended table knowledge with deep logical compositionality. It introduces complex question answering over semi-structured HTML tables and a parser designed to address the resulting challenges.
- The task uses semi-structured HTML tables as knowledge sources for questions involving comparison, superlatives, aggregation, and arithmetic.
- Unlike fixed-schema knowledge bases, test tables contain previously unseen relations and entities, preventing a lexicon from being constructed in advance.
- Deeper compositionality and additional logical operations create an exponential growth in possible logical forms.
- The parser encodes tables as graphs, generates high-coverage candidate logical forms, reranks them, and uses type and denotation pruning during beam search.
- 37.1% accuracy on unseen tables exceeds the information retrieval baseline of 12.7% and the simple semantic parsing baseline of 24.3%.
2 Task
The task asks systems to answer arbitrary questions from HTML tables while generalizing to tables withheld during training. The authors construct WIKITABLEQUESTIONS from Wikipedia tables and crowdsourced question-answer pairs.
- Given a table and question, the system outputs a list of values answering the question according to the table.
- Training and test tables are disjoint, so test-time tables do not appear during training.
- Questions may range from simple lookups to those requiring multiple logical operations.
- Dataset: The dataset was built by asking workers to write trivia questions using generic prompts encouraging complex utterances, then answer them from the tables.
- Dataset: 22,033 examples span 2,108 tables, with 20% of tables and associated questions held out for testing.
3 Approach
The approach converts each table into a knowledge graph, parses the question into candidate logical forms, scores them, and executes the best candidate. Training maximizes regularized likelihood over logical forms producing the observed answer.
- Prediction: The prediction pipeline deterministically converts a table into a knowledge graph and generates candidate logical forms using information from that graph.
- Prediction: Each candidate receives features and a log-linear score, after which the highest-probability logical form is executed to produce the answer denotation.
- Training: The model maximizes regularized log-likelihood of the correct answer denotation marginalized over logical forms.
- Training: The world representation is deterministically generated from each training table.
- Training: AdaGrad runs for three passes with L1 regularization using λ = 3 × 10−5 selected by cross-validation.
4 Knowledge graph
The table is deterministically represented as a knowledge graph whose rows, cell entities, and column relations support normalization and compositional queries. Graph augmentation adds structure for operations such as ordering and indexing.
- Rows become row nodes, cell strings become entity nodes, and table columns become directed row-to-entity edges labeled by column headers.
- Repeated occurrences of the same string are represented by one entity node.
- Normalization edges allow strings such as “1900” to be interpreted as numbers, dates, or proper names depending on context.
- Each row node receives Next and Index edges, enabling questions about adjacent rows and row positions.
- The graph can be queried directly using a logical formalism for knowledge graphs.
5 Logical forms
The parser uses lambda DCS to represent table queries as compositional unary and binary logical forms, combined through operations that yield larger expressions.
- Lambda DCS logical forms denote either lists of values as unaries or lists of pairs as binaries.
- Singletons represent entities or numbers, while relations such as City, Next, and >= provide binary mappings between typed values.
- Logical forms compose through operations listed in Table 1, with each operation producing a unary except lambda abstraction.
6 Parsing and ranking
The parsing system freely generates and composes logical forms for semi-structured tables, then uses model scoring, typing, denotation constraints, and pruning to control the resulting search space.
- Floating parser: The floating parser generates logical predicates independently of utterance spans, unlike chart parsing, enabling relations unseen during training to be considered.
- Floating parser: Floating cells track category and logical-form size rather than token spans, and composition proceeds by increasing logical-form size.
- Example derivation: Figure 4 illustrates a derivation where Greece is anchored to the question, while Year and other predicates are generated as floating logical forms.
- Search control: Strong typing constraints prevent nonsensical derivations, while beam search and pruning remove low-scoring, invalid, empty, or redundant candidates.
- Anchoring: Entities and atomic values are anchored to token spans, while relations and operations remain floating so their language connections can be learned.
- Ranking: The parser constructs candidate logical forms with deduction rules, extracts question-table-candidate features, and reranks candidates using a log-linear model.
7 Experiments
Experiments show that WIKITABLEQUESTIONS combines broad relational coverage with substantial logical-operation diversity, while the parser benefits from pruning and lexicalized features but remains limited by generation and normalization errors.
- Dataset breadth: 3,929 unique column headers across 13,396 columns demonstrate broad relational coverage, with correct logical forms using 2,056 unique headers.The 2,056 headers exceed the 635 Freebase relations reported for FREE917.
- Dataset breadth: Freebase answered only 20% of a 50-example sample, indicating that WIKITABLEQUESTIONS contains facts beyond its coverage.The sample was answered manually using Freebase.
- Logical-operation coverage: The dataset requires varied logical operations, and 21% of 200 manually classified examples cannot be answered by the current deduction rules.The covered operations range from simple table lookup to more advanced compositions.
- System analysis: Pruning improves both oracle and accuracy by preventing bad logical forms from clogging the beam, while lexicalized phrase-predicate features are the most influential ablated feature type.The features connect phrases with operations and relations, such as “last” with argmax and “before” with < or Next.
- Error analysis: 53.5% of manually annotated logical forms are generated as candidates, with missing cases mainly involving lexical anchoring mismatches or complex forms expressed by one phrase.Examples include “Italian” → Italy and “May 2010” → >=.2010-05-01 ⊓ <=.2010-05-31.
8 Discussion
The paper positions WIKITABLEQUESTIONS as a broader and more varied semantic-parsing benchmark than earlier resources, using semi-structured HTML tables directly rather than forcing web information into a fixed schema.
- Logical coverage: WIKITABLEQUESTIONS includes a more diverse set of logical operations than Geoquery while retaining fairly compositional questions on average.It does not contain Geoquery’s most extremely compositional examples.
- Parsing approach: The parser avoids anchoring relations and operations to utterance phrases, taking an approach similar to logical-form growing for generalization to unseen data.Earlier systems commonly rely on lexicons mapping phrases to entities, relations, and operations.
- Knowledge domain: Semi-structured tables provide open-ended web data without the information loss and schema constraints introduced by extracting content into systematically organized knowledge bases.The paper therefore works directly with HTML tables.
- Future work: Future work extends the framework to colon-delimited pairs, bulleted lists, top-k lists, and general web pages.The proposed direction combines this work’s logical compositionality with broader web-page coverage.