CONCLUSION

Decision list learners always need a default strategy since learners will likely encounter some future observations that are not covered by the learned rules. A default strategy is responsible for giving a reasonable classification for the future observations when this happens. The performance of the default strategy is of great importance to the global performance of a decision list learner, especially when the training set is small and not many rules can be learned.

BruteDL is a decision list learner that learns homogeneous rules by a brute-force search with several pruning methods over the training data. It provides satisfactory performance on adequately large training data sets. When the training data sets are not big enough, BruteDL's performance may be very poor. This is often because of the performance of its default strategy. BruteDL's default strategy is to use a default rule, which always classifies a future observation that is not covered by any existing rules as a member of the most frequently seen class among the (uncovered) training data. This default strategy's performance is affected by the characteristics of the training data set and cannot provide a reasonably accurate prediction for an observation if the training set is small or the training examples are evenly distributed among the possible classes.

To improve the performance of BruteDL, we applied several different strategies:

1. Applying an OSR-like algorithm -- Minimum OSR -- to generate new rules for the uncovered future observations instead of simply using the default rule.
2. Relaxing the storage constraints and storing many more homogeneous rules in the decision list.
3. Using the closest partially matching rule instead of the default rule.

The default rule is still appended at the end of the learner's output no matter which default strategy we use and is always the last choice to match a future observation. Among the listed default strategies, OSR improves the system's performance when the learner is not adequately trained. The others do not provide notable, if any, improvement.

The Minimum OSR strategy takes the future observations into account when none of the existing rules is appropriate for them. A search under the guidance by the future observation is done and a rule is generated for a future observation whenever needed. This is a reliable strategy especially when the training set is small and no rules other than the default rule exist in the decision list. The prediction accuracy of BruteDL is greatly increased by Minimum OSR on the small data sets and the time consumption is not significantly high.

As noted, the latter two methods were motivated by a desire to further reduce cost, while retaining OSR's advantages; the idea behind them are natural and reasonable. The unsatisfactory results we got may be only due to our implementation. They might provide significant improvement if we could implement them suitably. For example, as described in chapter 5, the left hand side of the default rule is actually not empty. In fact, it contains some implied conditions according to the previous rules. A possible alternative strategy can be using the complete implied conditions to match a future observation. Improvements with Minimum OSR suggest that there remains untapped information in the training data, which can be better extracted at training time, rather than reinvoking an OSR search during classification.