next up previous
Next: Further Reading Up: Algorithms for Inductive Learning Previous: Motivation

Basic model construction

The basic incremental growth procedure may be outlined as follows. Every stage of the process is characterized by a set of active features tex2html_wrap_inline2120 . These determine a space of models

  eqnarray1064

The optimal model in this space, denoted by tex2html_wrap_inline2124 , is the model with the greatest entropy:

  eqnarray1068

By adding feature tex2html_wrap_inline2128 to tex2html_wrap_inline2130 , we obtain a new set of active features tex2html_wrap_inline2132 . Following (22), this set of features determines a set of models

eqnarray1074

The optimal model in this space of models is

eqnarray1077

Adding the feature tex2html_wrap_inline2138 allows the model tex2html_wrap_inline2140 to better account for the training sample; this results in a gain tex2html_wrap_inline2142 in the log-likelihood of the training data

  eqnarray1082

At each stage of the model-construction process, our goal is to select the candidate feature tex2html_wrap_inline2150 which maximizes the gain tex2html_wrap_inline2152 ; that is, we select the candidate feature which, when adjoined to the set of active features tex2html_wrap_inline2154 , produces the greatest increase in likelihood of the training sample. This strategy is implemented in

     algorithm1086

One issue left unaddressed by this algorithm is the termination condition. Obviously, we would like a condition which applies exactly when all the ``useful'' features have been selected. One reasonable stopping criterion is to subject each proposed feature to cross-validation on a held-out sample of data. If the feature does not lead to an increase in likelihood of the held-out sample of data, the feature is discarded.

Another outstanding issue is the efficiency of Algorithm 2. It is impractical for any reasonable size of tex2html_wrap_inline2184 to imagine performing Algorithm 1 once for each tex2html_wrap_inline2186 at every iteration. The interested reader is referred to the list of further readings at the end of this document for pointers to articles containing efficient algorithms for model construction.



next up previous
Next: Further Reading Up: Algorithms for Inductive Learning Previous: Motivation



Adam Berger
Fri Jul 5 11:43:50 EDT 1996