To illustrate how branch-and-bound dramatically reduces the search space, consider the results of applying it to the sample sentence.
------------------------------------------------ Circle Input-Circles 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 19. In that Figure, several of
the circles cannot be fully reduced due to interactions outside the
circle. Variable A in Circle 1 cannot be fully reduced
because of Arc a. Note, however, that when Circle 4 is
synthesized, Variable A can be reduced because, at that point,
it does not interact outside the larger circle. In Circle 4, Variable
B cannot be reduced because it interacts with Variable C. Likewise,
Variable C cannot be reduced in Circle 2 because of its interaction
with Variable B. In all of these cases, ambiguity must be carried
along until no interactions outside the circle exist. For Variables B
and C, that does not occur until Circle 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 circle. 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 following table shows actual results of analyses of various sized problems.
# plans 79 95 119 exh. combos 7,864,320 56,687,040 235,092,492,288 SS-GATHERER 179 254 327
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 SS-GATHERER. 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 SS-GATHERER 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 SS-GATHERER 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 SS-GATHERER, 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 SS-GATHERER, 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 SS-GATHERER 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. SS-GATHERER will enable large-scale investigations in the knowledge-based paradigm.
