Efficiency of Processing

The efficiency of a content realizer can be evaluated more straightforwardly. There are four areas that can be judged: the basic algorithmic complexity, the extent of backtracking, the ability to prune the search space and the processing speed of each node in the tree.

1. algorithmic complexity: The underlying algorithm this system uses is recursive descent. A basic recursive descent algorithm will have worst case complexity b**n, where b is the average branching factor of the rules and n is the number of input nodes. This fact will become important below, since the systems ability to prune the search space directly lowers the average branching factor, and the ability to eliminate backtracking indirectly lowers the complexity by simplifying the worst case.

2. ability to prune the search space: One of the main advantages this approach has is its ability to decrease the search space by eliminating useless combinations of plans. An 80 percent decrease was found in the number of rules needed to be considered in the example text compared to what a ``normal'' text planner would face. This result is magnified by the exponential nature of the recursive descent algorithm. The actual data from the experiment follows:

   number of nodes in input tree: 124

   number of rules in tree before processing: 715

   number of rules after ``look-ahead'': 305 = 57 percent decrease

   number of islands after ``look-ahead'': 62

   number of rules after initial island processing: 156 = 78 percent decrease (49 percent decrease compared to after ``look-ahead'')

   • rules still active (1's): 62 = 91 percent decrease (80 percent)
   • number of islands (2's): 94 (52 percent increase)
   • number of failed rules (0's): 149

   The ``baseline'' I would use for comparison is the number of rules in the tree after ``look-ahead'' (305). This is because the ``look-ahead'' function uses many simple techniques to trim the tree which most text planners would have available. After initial island processing, then, there are only 156 rules that have not been eliminated (a 49 percent decrease). The situation is actually much better than this, though, because of these 156 rules, 94 of them are associated with an island. Because of the optimization techniques described above, islands require no further processing. Thus only 62 rules need to actually be considered, a reduction of 80 percent over the baseline. Note also that the initial processing increases the number of islands 52 percent over the baseline.

3. extent of backtracking (in addition to above)

   The elimination of backtracking serves to increase the efficiency by making the solution significantly better than the ``worst case''. The worst case scenario occurs when the maximum amount of backtracking possible actually occurs, and the correct solution is the last one tried. This system eliminates backtracking, first of all, by reducing the number of alternatives that are tried, as described directly above. Backtracking is also eliminated because the system recognizes an impossible plan at the earliest moment possible, instead of carrying the plan through and only finding out later that it must be failed. The results of processing on the sample text follow:

   To find the first 10 answers in example text:

   • nodes traversed using soundness, island processing, optimization: 41
   • nodes traversed without these: 55 (34 percent increase)

   Thus, a decrease of 34 percent (over and above the 80 percent reduction in search space, which has an exponential benefit) was attained. It was interesting to note the relative contributions of the soundness processing versus the island processing components. Contrary to my expectations, the soundness principle almost completely overwhelmed the island principle during the initial processing. Much of this is due to the fact that the soundness principle is applied first, but, nevertheless, all but one of the island-related failures had already been accounted for by the soundness processing. This needs further research to determine if this is a general effect, or simply related to the example text and rule set used.

4. relative contributions of soundness vs island processing

   before modified recursive descent

   • island-initiated fail requests: 137
   • island-initiated actual fails: 1
   • soundness-initiated fail requests: 187
   • soundness-initiated actual fails: 148

   during modified recursive descent

   • island-initiated fail requests: 107
   • island-initiated actual fails: 4
   • soundness-initiated fail requests: 5
   • soundness-initiated actual fails: 4