This section will examine constraint analysis in computational semantic problems. As will be demonstrated in section 3.5, these types of problems typically consist of bundles of tightly constrained sub-problems, each of which combine at higher, relatively constraint-free levels to produce the complete solution. Algorithms that identify these bundles, or ``circles,'' along with their constraint dependencies, will be given here. A simple, ``literal,'' semantic problem will be solved using CSP consistency algorithms. The problem of non-literal meanings will be presented, with the solution to this problem to be presented in the ``Using Branch-and-Bound in an Uncertain World'' section.
Consider Figure 10, an example of a very simple Spanish sentence analyzed by the Mikrokosmos semantic analyzer. The Spanish sentence along with possible word senses are shown. Figure 11 shows the decision tree for this sentence. The paths leading to leaves at the bottom of the tree represent possible solutions. In this case, there are 32 such solutions.
Figure 12: Decision Tree after CSP
Figure 12 shows the results when some fairly obvious ``literal''
semantic constraints are imposed and propagated using arc consistency.
Only one valid path remains. Obviously, CSP techniques help out
immensely in this literal-interpretation paradigm. Some of the
constraints that were used to eliminate sub-trees in Figure 11 are as
follows:
Unfortunately, a literal imposition of constraints does not work in computational semantics. For example, a-traves-de could very well be location, because corporation names are often used metonymically to stand for ``the place of the location:''
I walked to IBM.
I walked to where IBM's building is.
Therefore, the fact that compania is not literally a place only biases the result towards a different interpretation. In fact, under certain contexts, the location interpretation might be preferred; certainly it cannot be ruled out completely, as was done in Figure 12. Constraint satisfaction techniques such as arc-consistency, therefore, will be of limited value. The ``Using Branch-and-Bound in an Uncertain World'' section will describe how to combine branch-and-bound techniques with solution synthesis and knowledge of constraint dependencies. Here, we prepare for that section by describing how constraint dependencies can be identified, and how they typically look in computational semantic problems.
Figure 13: Constraint Dependencies in Sample Sentence
Figure 13 gives a different view of this same problem by
graphically displaying the constraint dependencies present in Figure
10. These constraint dependencies can be identified simply by
iterating through the list of constraints and
connecting with an arc any words involved in the same
constraint.
