Constraint Solving
Abstract:
In this section we show how we can extract the semantic representations of the vraious readings of a sentence from its constraimt graph, how to actually implement constraints and an enumeration procedure, and how we can use our semantics construction framework to derive constraints from the syntactic analysis of an NL sentence.From Constraints to Formulae: Now we know how to describe the possible readings of a scope ambiguity by means of a constraint graph. The next thing we need to find out is how we can extract the semantic representations of the readings from the graph. This is going to be the topic of the first part of this section. Later we will show you how to actually implement constraints and an enumeration procedure. Last not least, you will see how we can use our semantics construction framework to derive constraints from the syntactic analysis of an NL sentence.
Table of Contents
Constraint Solving When we deal with solving underspecified descriptions, the two algorithmic problems that concern us most are the following:
- Satisfiability
Given a constraint graph, we need to decide whether there is a λ-structure into which it can be embedded. - Enumeration
Given a constraint graph, we have to compute all λ-structures into which it can be embedded.
These are the problems adressed in this section. The concept of a
solved form will be central to the solutions that we develop.
An Algorithm For Solving ConstraintsGiven a solved form of a constraint it is almost trivial to get to a solution for it. What we don't know yet is how to get to the solved form itself, given an arbitrary constraint. In this section, we'll formulate an algorithm that enumerates the solved forms of arbitrary constraints.As we have argued before, it is almost trivial to get to a solution from a solved form. What we don't know yet is how to get to the solved form itself, given an arbitrary constraint. In this section, we'll formulate an algorithm that enumerates the solved forms of an arbitrary constraint.Our overall strategy will be as follows: starting with an arbitrary constraint graph, we'll try to work our way towards a set of constraints in solved form that together have the same solutions as the original constraint. For this, we'll use the algorithm discussed in the following part of this lecture. The set of solved forms will be the output of this algorithm.If we like to, we can then proceed to enumerate solutions (or just minimal solutions) of the solved forms after this, in the way described in the last section. But we don't have to. The main property of solved forms that we try to establish in our algorithm is that there are no nodes with two incoming dominance edges. Thus the central task of our algorithm is eliminating such nodes. We will now look in detail at the three steps that make up the algorithm: Applying the so called
Choice Rule,
Parent Normalization and
Redundancy Elimination.
Constraint Solving in Prolog After that much of theory we come to our implementation of constraint solving in Prolog. First, we will see how our constraints are represented in Prolog. Then we will look at how they are brought into solved form. As we have said above, it is quite straightforward to convert solved forms into solutions and then into our good old
λ-expressions. We leave it as an exercise to you to work through that part of our implementation (
» Beispiel: EX EX.CLLS.BEAUTYEX_EX.CLLS.BEAUTY).
Semantics Construction for Underspecified Semantics In this section we show you to you can derive underspecified representations from syntactic analyses. The semantics construction algorithm we present here uses the syntax/semantics framework laid out in the earlier chapters of this course.To conclude our chapter on underspecification, we will show you how you can derive underspecified representations from syntactic analyses. The semantics construction algorithm we present here uses the syntax/semantics framework laid out in the earlier chapters of this course. The relevant changes are:
- Devising the semantic macros that provide the meanings of words on the lexical level.
- Giving the combine-rules that combine smaller constraint graphs for subphrases to larger ones representing the meanings of the larger phrases.
As you will see, the division of labour between the two types of rules is different than what it used to be. Our implementation of Montague semantics was highly
lexicalized: The lexical entries were relatively rich, and the combine-rules just told us what was the functor and what was the argument in a functional application. Here it's going to be the other way round: Most lexical entries are going to be very simple, and the combination rules will do most of the work.
Running CLLSThis section introduces the driver predicate
clls/0 for CLLS-based semantic construction, and contains links to all files needed for running the program.
Exercise
Make sure that the clause of
combine/2 given in
» SEC_CLLS.BUILDUSR2B really corresponds to the tree representation given there: Print out the tree and try to decorate its nodes with all respective Prolog variables for the nodes.
- Write down the λ-expression that corresponds to the graph given in » SEC_CLLS.BEAUTY. Reduce this λ-expression to a first order formula.
Hint: the right half translates into λx.WALK@x. In the left half, there are two lam-nodes. Each translates into λPi where Pi is a new variable. The existential quantifier has to be treated likewise. var-nodes translate into the variables bound by their binder. - Look at our implementation of the predicate translate/4 (see cllsLib.pl) that translates solved constraints into λ-terms. Explain how the bindings are handled!
cllsLib.pl: View_Download
This predicate converts solved constraints directly to λ-terms. Note that we only compute one (minmal) solution for one solved form. But as we have discussed (» Solved Forms) solved forms stand for classes of solutions. Which clause of our predicate would we have to change in order to compute non-minimal solutions?
Test whether you understand the semantic macro for the indefinite determiner
a. The "naked" tree given in the figure in
» SEC_CLLS.BUILDUSR1B on the right is already decorated with the PROLOG variables from the semantic macro
detSem(indef,...). Print out this tree or draw it on a piece of paper. Go through the semantic macro and add the node labels and the binding edges to the tree.
Look at the two clauses of mergeUSR/2 (cllsLib.pl) and make sure that in the resulting constraint, the root node of the leftmost input constraint really ends up in front of all other nodes. Remember that we always interpret the first node of a constraint as its root node. This means we have to be able to formulate our calls of mergeUSR/2 such that we can determine which node will finally be the root node.
Design a test call
USR_A = usr([nodeA1,nodeA2,...],[nodeA1:lA1,...]...),
USR_B = usr(nodeB1,...),
USR_C = usr(...),
mergeUSR(merge(merge(USR_A,USR_B),USR_C),Result).
to practically test this.
Add a treatment of adjectives to the implementation of clls. The semantic macro for an adjective is a USR for a simple labeled node. Procede as follows: First, complete the semantic macro adjSem(_,_) for adjectives (to be found at the bottom of clls.pl). Second, add a clause of combine to clls.pl according to the following scheme.
 Figure 1: o3846 picture description dummy |
The implementation of
liftDominanceConstraints/2 we presented immediately removes the old, lifted dominance edge with
select/3 (see
» (Parent) Normalization).
There is a problem if we use member/2 instead of select/3? Try it out! Why does this problem occur? Can you think of an elegant solution to it?
Hint: look what predicates we've already got for cleaning up constraints!
[optional]
In the implementation of clls we presented, the meaning of a determiner as given in the semantic macros is a relatively complex λ-structure (tree). It represents e.g. the λ-term λPλQ.∀x(P(x)→Q(x)) in the case of the universal quantifier. The only part of such trees that is relevant for the semantics construction process is its root node. The rest of the tree remains stable during the whole construction process: There is no place inside these trees where further material can be inserted. To enhance the readability of the underspecified structures, one can for example represent the meaning of an universal quantifier as a node labeled every during the semantics construction process. Then, before the final β-reduction is done, these abbreviations can be be expanded into the well-known λ-terms like λPλQ.∀x(P@x→Q@x).
Try to change the implementation of clls accordingly. You may proceed as follows. First, replace the entries of the determiners in the semantic macros by simple labeled nodes (like the entries of nouns for example). Then, build a PROLOG module ExpandQuantifiers that exports a predicate ExpandQuantifiersList/2. This predicate should expand a list of λ-terms containing abbreviations like [every@man@lambda(A,walk@A)] into the list [lambda(P, lambda(Q, exists(X,(P@X)&(Q@X))))@man@lambda(A,walk@A)] Finally, integrate the predicate ExpandQuantifiersList/2 into the predicate clls.
Hint: use the predicate compose/3 (comsemLib.pl) to decompose terms like every@man@lambda(A,walk@A) .
[Mid-Term Project]
Our implementation of solve/2 is a straightforward implementation of the enumeration algorithm. It is an example of imperative programming. For example, the solutions of two distributed constraints are computed at once and then they are solved recursively. Finally, the results are appended.
The same could have been achieved in a more declarative fashion with backtracking and two clauses of distribute. Reimplement the predicate in a more declarative manner!
Hint: use Prolog search (like bagof) to enumerate all solutions.