Inferring Logical Forms From Denotations

ACL-2016

  • Panupong Pasupat
    Computer Science Department Stanford University ppasupat@cs.stanford.edu
  • Percy Liang
    Computer Science Department Stanford University pliang@cs.stanford.edu

Introduction

Challenge:

  • Computational: number of LF grows exponentially
  • Spurious LF: those LFs happen to get the right denotation

Task:

QQ20161220-1.png

World:

QQ20161220-0.png

LF (Lambda DCS):

QQ20161220-2.png

Rules

$LF \in Categories = {Set, Rel, Map, (TokenSpan?)}$

Deduction rules works over two categories of LFs, output LF with some other category of LF.

Basic Rules with following forms:

QQ20161220-3.png

Compositional Rules have the following forms:

QQ20161220-4.png

Map Category

  • execution of partial LF is sometimes impossible, e.g. $\lambda x.count(x)$
  • partial LF may be complex, e.g. z3

Introduce a map (from set to map, then map to map, finally map back to set)

A map is a pair of a finite unary set u and a binary relation b: (u, b)

Denotaion of $(u, b) = (u)$ is $([u]_w, [b]’_w)$ where $[b]$ is restricted to $[u]$

QQ20161220-5.png

e.g. $argmax(Position.1st, Index)$

  1. B1 TokenSpan to Set: 1st
  2. B5 Empty to Relation: Position
  3. C1 Set + Rel to Set:
  4. M1 Set to Map:
  5. B5 Empty to Relation: Index
  6. M2 Map + Rel to Map:
  7. M6 Map to Set:

All the LFs of each category c and size s reside in the same $cell(c, s)$.

e.g. Rule C1: Set + Rel to Set may

  • choose $Number.1$ from (Set, 1)
  • choose $Position$ from (Rel, 0)
  • create $Position.Number.1$ to (Set, 0 + 1 + 1 = 2)

up to max size (=7)

After populating each cell, the list of logical forms is pruned to a fixed beam size on model scores.

Beam search may suffer from the propagating errors when the size goes large.

Dynamic Programming on Denotations (DPD)

  • The number of LFs goes exponential but many of them share the same denotation.
  • The number of denotations are much more controlled.

collapse LFs with the same denotation in $cell(c, s, d)$

Two pass algorithm:

QQ20161220-6.png

  1. Find relevant cell combinations only.
    • One LF per cell and discard others further encountered.
    • Populate cells up to max size
    • Use the cells with correct denotation, collect all rule combinations (cell1, [cell2,] rule) yielding it, combinations of discarded LFs also
  2. Find actual LFs. Use the rule combinations only found before. (98.7% search space are reduced)

without denotation we can do nothing, e.g. testing

Fictitious worlds

Semantically correct LF should give correct denotations in world (table) other than the original one.

Sampling

  • All entities and relations in Z must be presented in the new fictitious world
  • Columns are the same
  • Resample the cells in each column (with replacement or not)
  • Keep the sorted column sorted

QQ20161220-7.png

Annotation

Some LFs got the same denotation across all the fictitious worlds, thus they fall into a equivalence class.

QQ20161220-8.png

There’re too many fictitious worlds(=30), choose a subset(=5) of them, thus some equivalence classes may fall into the same partition.

Notations:

Choose a subset that maximize expected information gain (reduction in entropy):

Experiments

more generated LFs

annotated 252 out of 300 (84%) examples from training set of WikiTableQuestions with LFs.

76% of the first 300 (agianst 53.5% of the first 200, [P and L, 2015]) were generated successfully.

QQ20161220-9.png

DPD

search space is reduced by 98.7%

QQ20161220-10.png

more LFs generated than Beam search

QQ20161220-11.png

Fictitious Worlds

30 worlds is enough (5% are different when 300 worlds)

in the 252 annotated examples, 98.3% of spurious LFs are ruled out.

32.7% of 252, only 1 equivalence classes is left. 51.3% of 252, only 3.

Randomly choose 5 worlds (rather than using the information gain)

22.6% and 36.5%.