| |
Inference of Semantics from Examples:
From Context-Free to Definite-Clause Grammars
My work on this subject concerns the problem of synthesizing mappings from syntactic structures to meaning representations
given a grammar and sample sentence-meaning pairs. The motivation for this work stems from the potential use of
such techniques in the development of natural language front-ends, e.g., natural query languages. The central technical
problem addressed is the mechanical transformation of a context-free grammar (CFG) into a definite clause grammar
(DCG) using sample sentence-meaning pairs of the form <s, m>, where s is a sentence
belonging to the language defined by CFG and m is the semantic representation (meaning) of s. The
resulting DCG would be such that it could be executed, by the interpreter of a logic programming language, to compute
the semantic representation(s) for every sentence of the original CFG. Two important assumptions underlie the proposed
approach: (1) the semantic representation language is the simply typed lambda-calculus, and (2) the semantic representation
of a sentence can be obtained from the semantic representations of its parts (compositionality).
The basic technique involves an enumeration of a representative finite set of sentences and formation of a corresponding
set of equations over (typed) function variables. Each function variable represents the meaning of a particular
grammar rule, and effectively serves to augment the original CFG in order to derive a higher-order DCG. The main
research topics investigated here are: (1) formulation of a solution technique using a variant of Huet's unification
procedure for the simply-typed lambda-calculus; (2) efficient implementation of the solution using constraints
from multiple examples, "macro" substitution rules that package common sequences of more basic substitutions,
and a dependency-directed backtracking search; (3) development of a provably-correct partial execution procedure
to convert the constructed higher-order DCG into a first-order DCG, for more efficient execution; and (4) the application
of the entire methodology for developing a natural query language--a variant of the CHAT-8O query language--starting
from a grammar and sample sentence-meaning pairs.
An Adaptive Problem Solver
This is an extended adaptive planning project. The plan construction process is defined in the following way:
Given an initial state and a goal state description, the planner tries to find a sequence of actions which will
transform the initial state into the goal state. The planner of the system discussed here is similar to other planners
in that the operators which are used by the planner to convert a given state description into another state description
consist of three lists: the list of preconditions, the add-list and the delete-list.
In most domains a state can be represented by a list of objects which have their location attached to them. Therefore
a basic predicate for representing states would be something like 'location(Object,X)', where X is some constant
characterizing the location, e.g., a set of coordinates or another object. Given those basic predicates, other
convenient predicates can be defined. E.g. in the blocks world domain 'on(X,Y)' would be a basic predicate, whereas
'clear(X)' or 'above(X,Y)' can be defined in terms of the basic predicate 'on'. The overall efficiency of the system
will be higher if only the basic
predicates are used to describe a current state, whereas both basic and derived predicates can be used to describe
goal states. This means the add-lists and delete-lists of
the operators should contain only basic predicates, whereas the list of preconditions can contain also derived
predicates. The planner then uses the definitions of the derived predicates to check if they hold in a given state.
During the planning process the planner maintains a list of achieved subgoals to ensure that they are not undone
while the planner is working on the remaining subgoals. Which subgoal to work on next is determined by the subgoaling
rules whose generation is discussed in the full report. Given a subgoal, the planner tries to identify in the usual
way the rule which can achieve that subgoal. If the corresponding preconditions are not satisfied by the current
state, the planner is called recursively using those preconditions as goal description.
If no suitable operator can be identified for a particular subgoal, the planner makes use of reformulation rules;
i.e. the current subgoal is replaced by a set of other subgoals which imply the original subgoal. For each of the
new subgoals an operator to achieve that subgoal can then be identified. The generation of reformulation rules
is discussed in the full report.
If the achievement of a subgoal has to be delayed in order not to run into a dead end, the planner uses guidance
rules. Guidance rules insert intermediate state descriptions in order to rearrange the current configuration in
such a way that all component goals can be
achieved in series, i.e without undoing already-achieved component goals.
Note: All presentations at this site are in abstract format. Feel free to email
me for detailed documents.
Related Publications
"From Context-Free to Definite-Clause Grammars: A Type-Theoretic Approach," J. Haas, B. Jayaraman,
Journal of Logic Programming, Vol 30(1), 1-23, January 1997.
"Interactive Synthesis of Definite-Clause Grammars," J. Haas and B. Jayaraman, Proceedings of the
Joint International Conference and Symposium on Logic Programming, Washington, D.C., November 1992.
|
Part
I. Inference of semantics from examples