To illustrate how branch-and-bound dramatically reduces the search space, consider the results of applying it to the sample sentence.
------------------------------------------------------ Subgraph Input-Subgraphs Input-Combos Reduced-Combos ====================================================== 1 none 2*2*1 = 4 2 ------------------------------------------------------ 2 none 2*2*2 = 8 4 ------------------------------------------------------ 3 none 2*2*1 = 4 2 ------------------------------------------------------ 4 2 and 3 synth only 2 ------------------------------------------------------ 5 1 and 4 synth only 1 ======================================================
The total number of combinations examined is the sum of the input combos; in this case 4+8+4=16. Compare this to an exhaustive search, which would examine (2*1*2*2*2*1*2*1) = 32 combinations. As the input problem size increases, the savings are even more dramatic. This happens because the problem is broken up into manageable sub-parts; the total complexity of the problem is the addition of the individual complexities. Without these techniques, the overall complexity is the product of the individual complexities.
The only way multiplicative growth can occur is when there are
constraints across trees, as in Figure 34. In that Figure, several of
the subgraphs cannot be fully reduced due to interactions outside the
subgraph. Variable A in Subgraph 1 cannot be fully reduced
because of Arc a. Note, however, that when Subgraph 4 is
synthesized, Variable A can be reduced because, at that point,
it does not interact outside the larger subgraph. In Subgraph 4, Variable
B cannot be reduced because it interacts with Variable C. Likewise,
Variable C cannot be reduced in Subgraph 2 because of its interaction
with Variable B. In all of these cases, ambiguity must be carried
along until no interactions outside the subgraph exist. For Variables B
and C, that does not occur until Subgraph 6, the entire problem, is
processed.
As is argued below, in computational semantic problems interactions such as Arc a and
Arc b generally do not occur. ``Governed'' interactions such as
Variable D directly constraining Variable A can occasionally occur,
but these only delay reduction to the next higher subgraph. Thus, some
local multiplicative effects can occur, but over the whole problem,
the complexity is additive.
To illustrate this point, consider what happens as the size of the problem increases. The table in Figure 35 shows actual results of analyses of various sized problems.
Figure 35: Results of Semantic Analysis
It is interesting to note that a 20% increase in the number of total
plans (79 to 95)
results in a 626% increase (7.8M to 56M) in the number of exhaustive
combinations possible, but only a 42% increase (179 to 254) in the
number of combinations considered by HG. As one moves on to
even more complex problems, a 25% increase (95 to 119) in the number
of plans catapults the exhaustive complexity 414,600% (56M to 235B)
and yet only increases the HG complexity 29% (254 to 327).
As the problem size increases, the minor effects of ``local
multiplicative'' influences diminishes with respect to the size of the
problem. We expect, therefore, the behavior of this algorithm to move
even closer to linear with larger problems (i.e. discourse). And,
again, it is important to note that HG is guaranteed to
produce the same results as an exhaustive search.
Although time measurements are often misleading, it is important to state the practical outcome of this type of control advancement. Prior to implementing HG, all computational attempts to process larger sentences failed. The largest sentence above was analyzed for more than a day with no results. This is the nature of exponential search space. Using HG, on the other hand, the same problem was finished in 17 seconds. It must be pointed out as well that this is not an artificially inflated example. It is a real sentence occurring in natural text; and not an overly large sentence at that. Techniques such as HG must be employed to process real-life problems. Knowledge-based semantics has been severely limited until now, subject to arguments that it only works in ``toy'' environments. HG will enable large-scale investigations in the knowledge-based paradigm.
