Identifying ``Circles'' of Dependency

  
Figure 14: Problem Decomposition in Sample Sentence

Figure 13 clearly shows three sub-problems, or circles, that are relatively independent. If these circles could be identified, the processing involved in finding a complete solution could be decomposed into three sub-problems. Figure 14 displays the results of such a decomposition. The three circles represent sub-problems with 4, 8 and 4 possible solutions, respectively. Notice that there are still dependencies between the circles. The first two circles are connected because each contains the word adquirir; the second two are connected because they both contain the word compania. In the next section, we will show how to combine results from circles to form larger and larger solutions, the largest of which will be the solution to the whole problem.

We have taken a multi-phase approach to creating the circles that will guide the solution synthesis mechanism. The approach used is described next. The five phases of circle creation are as follows:

1. Create constraint-based circles. This is accomplished by identifying all cycles in a dependency graph such as Figure 13. As will be shown, the purpose of these constraint-based circles is to eliminate as early as possible in solution synthesis inconsistent variable assignments.
2. Create tree-based circles. Because dependencies are generally limited to structures in a governing relationship (section 3.5), the input tree can be used as a guide to the combination of smaller structures.
3. Decompose larger circles into a sequence of smaller circles plus individual nodes. Delete any ``orphan'' circles.
4. Identify which nodes in each circle are constrained outside the circle. These are the nodes for which branch-and-bound techniques can not choose optimal values. Eliminate any circle that does not have at least one node not effected outside the circle; it will not contribute toward the efficiency of the solution.
5. Some of the ``base'' circles can be further decomposed into groups of second-order nodes. The reason for this is intimately tied to the solution synthesis methodology, and thus will be described in the next section.

Step 1, identifying constraint-based circles, is relatively straightforward. Assuming we have a graph such as Figure 13 in the form of an array:

 effected[adquirir] = (grupo-roche, dr-andrew, a-traves-de, compania)

effected[grupo-roche] = (adquirir, dr-andrew)

effected[dr-andrew] = (adquirir, grupo-roche)

effected[a-traves-de] = (adquirir, compania)

effected[compania] = (adquirir, a-traves-de, su, en, espana)

effected[su] = (compania)

effected[en] = (compania, espana)

effected[espana] = (compania, en)

Then an algorithm for identifying circles in the graph is as follows:

 1 PROCEDURE Constraint-Circles

2 		 Circles <-- nil

3 		 FOR each Word

4 		 		 Circle <-- (Word)

  		 		 ;; create all the circles starting with Word and add to Circles

5 		 		 Circles <-- Circles + Extend-Path(Circle)

6 		 Circles <-- remove all identical circles.

7 		 RETURN Circles

8 PROCEDURE Extend-Path(Circle)

9 		 Last-Node-Added <-- LAST(Circle)

10		 Start-Node <-- FIRST(Circle)

  		 ;; find all the nodes that can extend the current path

11		 Effected-Nodes <-- effected[Last-Node-Added]

12		 Circles <-- nil

  		 ;; if Start-Node is in Effected-Nodes, then Circle is a circle

13		 IF MEMBER(Start-Node,Effected-Nodes) THEN

14		 		 Circles = Circles + Circle

  		 ;; remove any nodes already in Circle

15		 New-Nodes <-- Effected-Nodes - Circle

16		 FOR each New-Node, Node

17		 		 New-Circle <-- Circle + Node

18		 		 Circles = APPEND(Circles,Extend-Path(New-Circle))

19		 RETURN Circles

Each time Extend-Path is called by Constraint-Circles, Circle is length 1. In line 15, then, New-Nodes can have length N-1 if the Start-Node affects every other node. If this is the case, Extend-Path will be recursively called N-1 times. Each of these calls can, in turn, produce N-2 calls to Extend-Path, etc.. Thus, Extend-Path can theoretically be called N! times for each of the N Words, for a total complexity of O(N*N!). Actually, this complexity can be reduced by recognizing that any potential circle that contains a Word already processed by the FOR loop in line 3 will already have been identified. New-Nodes in line 15 can therefore also subtract any Words already processed. Thus, by the time the last Word is sent to Extend-Path by Constraint-Circles, no New-Nodes will be present.

This still leaves a potential complexity of O(N!) for Extend-Path when it is called for the first Word. This, however, assumes that every Word can affect every other Word, which fortunately is not the case in computational semantics. On the average, each word constrains less than two other words. In addition, most of the paths created in Extend-Path quickly do one of two things: either they loop back on themselves, creating a circle, or they end at a leaf node which cannot be extended to another Word not already in the current path (or already processed by Constraint-Circles). This is the nature of tree-like graphs. Only experimentation can determine if the time complexity is acceptable. In our experience, the computation of Constraint-Circles is almost instantaneous.

It can be debated whether step 1 is really necessary for computational semantics constraint problems. Given the tree-like nature of its inputs, and the general ``governing'' principle described in section 3.5, step 2, to be described next, seems to create most, if not all, of the relevant circles, without any question of exponential time difficulties. Identifying constraint-based circles, however, gives the advantage during solution synthesis that all co-dependent nodes are analyzed together as soon as possible, reducing the amount of ambiguity carried along. Because the practical time limits do not seem to be a problem, we have chosen to include step 1; however, further research may prove either that this step is, practically speaking, unnecessary, or that for larger problems (i.e. for whole texts with discourse relations, etc.), the time complexity becomes too great.

Step 2, creating tree-based circles is much easier. It can be accomplished by starting at the top of the input tree, making a circle of it and all the nodes below it, then progressing to each child node, making a circle of it and all the nodes below it, and so on down to the bottom of the tree. Figure 5 in the introduction shows an example of tree-based circles combined with constraint-based circles. .

In Step 3, larger circles are decomposed into smaller circles plus individual nodes. The solution synthesis algorithms will follow these progressions from small circles to large circles. This step is partly accomplished during step 2. During construction of the tree-based circles, a record is kept of which smaller circles the larger circles contain. All that is left is to use any of the constraint-based circles to further decompose any of the tree-based circles. At present, we decompose the smallest tree-shaped circle that has the constraint-based circle as a subset. If no such tree-based circles exist, the constraint-based circle is eliminated.

As will be shown below, the main savings gained from the combination solution synthesis / branch-and-bound methodology comes from synthesizing circles in which there is at least one node that is not constrained outside the circle. Thus, for each circle, these nodes are identified, and, if none exist, the circle is eliminated.