This section will examine Hunter-Gatherer's use in computational semantic problems. As will be argued in section 7, 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. The algorithms that identify these bundles, or subgraphs, along with their constraint dependencies, will be demonstrated 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 26, 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 27 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.
When some fairly obvious ``literal'' constraints are imposed, most of these paths can be eliminated. Obviously, CSP techniques can help immensely in this literal-interpretation paradigm. Some of the constraints that could be used to eliminate sub-trees in Figure 27 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. Constraint satisfaction techniques such as arc-consistency, therefore, will be of limited value. This will be true of any problem whose constraints cannot be stated in terms of yes/no answers. HG overcomes this limitation by using branch-and-bound as the primary mechanism for pruning the search space.
Figure 28: Constraint Dependencies in Sample Sentence
Figure 28 gives a different view of this same problem by
graphically displaying the constraint dependencies present in Figure
26. These constraint dependencies can be identified simply by
iterating through the list of constraints
Figure 29: Problem Decomposition in Sample Sentence
Figure 28 clearly shows three sub-problems, or subgraphs, that are relatively independent. If these subgraphs could be identified, the processing involved in finding a complete solution could be decomposed into three sub-problems. Figure 29 displays the results of such a decomposition. The three subgraphs represent sub-problems with 4, 8 and 4 possible solutions, respectively. Notice that there are still dependencies between the subgraphs. The first two subgraphs are connected because each contains the word adquirir; the second two are connected because they both contain the word compania.
Section 5.2 will describe how the solution synthesis algorithms can be used to combine results from subgraphs to form larger and larger solutions, the largest of which will be the solution to the whole problem. Section 5.3 then goes through the branch-and-bound optimization stages for this example. But first, section 5.1 is devoted to the decomposition of the original problem into subgraphs which are the inputs to the later stages of processing.
