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.
The subtree swapping approach produces new trees by swapping random subtrees in a candidate solution. It works as follows:
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.
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