next up previous
Next: 5 Restricting the Space Up: Experiments Using Stochastic Search Previous: 3 Evaluating RST trees

4 Using Stochastic Search for Text Planning

Using the above evaluation metric for RS trees, we have experimented with a range of stochastic search methods. Space does not permit us to discuss more than one initial experiment in this section. In the next section, we describe a couple of methods based on genetic algorithms which proved more productive.

4.1 Subtree Swapping

The subtree swapping approach produces new trees by swapping random subtrees in a candidate solution. It works as follows:

  1. Initialise with a tree for each combination of interesting (non-elaboration) relations, with any fact only appearing in one. Make into a complete tree by combining together these relations and any unused facts with ``joint'' relations (or better ones if available).
  2. Repeatedly select a random tree and swap over two random subtrees, repairing all relations. Add the new tree to the population.
When two subtrees are swapped over in an RS tree, some of the relations indicated in the tree no longer apply (i.e. those higher relations that make use of the nuclei of the subtrees). These are ``repaired'' by in each case selecting the ``best'' valid relation that really relates the top nuclei (i.e. a non-elaboration relation is chosen if possible, otherwise an elaboration if that is valid, with ``joint'' as a last resort).

We investigated variations on this algorithm, including having initial random balanced trees (including the ``best'' relation at each point) and focussing the subtree swapping on subtrees that contributed to bad scores, but the above algorithm was the one that seemed most successful.

4.2 Initial Results

Figure 2 shows an example text generated by subtree swapping. Note that we have taken liberties in editing by hand the surface text (for instance, by introducing better referring expressions and aggregation). The ordering of the material and the use of rhetorical relations are the only things which are determined by the algorithm.

 


: Example Text from Subtree Swapping 

Results for subtree swapping are shown together with later results in Figure 5 (the example text shown for subtree swapping is for the item named j-342540). The most obvious feature of these results is the huge variability of the results, which suggests that there are many local maxima in the search space. Looking at the texts produced, we can see a number of problems. Unfortunately, if there is only one way smoothly to include a fact in the text, the chance of finding it by random subtree swapping is very low. The same goes for fixing other local problems in the text. The introduction of ``the previous jewel'' is an example of this. This entity can only be introduced elegantly through the fact that it, like the current item, is encrusted with jewels. The text is still suffering from material getting between a satellite and its nucleus. For instance, there is a relation (indicated by the colon) between ``It is encrusted with jewels'' and ``it has silver links encrusted asymmetrically...'', but this is weakened by the presence of ``and is an Organic style jewel'' in the middle).

The trouble is that subtree swapping needs incrementally to acquire all good features not present in whichever initial tree develops into the best solution. It can only acquire these features ``accidentally'' and the chances of stumbling on them are small. Different initial trees will contain different good fragments, and it seems desirable to be able to combine the good parts of different solutions. This motivates using some sort of crossover operation that can combine elements of two solutions into a new one [Goldberg 89]. But it is not immediately clear how crossover could work on two RS trees. In particular, two chosen trees will rarely have non-trivial subtrees with equal fringes. Their way of breaking up the material may be so different that it is hard to imagine how one could combine elements of both.

 


: Ordinal and Path Representations  



next up previous
Next: 5 Restricting the Space Up: Experiments Using Stochastic Search Previous: 3 Evaluating RST trees



Ilex