A Maximum Entropy Approach to Natural Language Processing

4 Feature selection

1. Why is feature selection necessary in maximum entropy modeling?
   The principle only combines constraints; it doesn’t say which facts matter. Candidate features can number in the millions, and with a finite sample many empirical expectations \(\tilde{p}(f)\) are unreliable, so only a subset of “active” features should be used.
   • Berger et al., 1996, A Maximum Entropy Approach to Natural Language Processing (Computational Linguistics), §4
2. How does incremental feature selection grow a maximum entropy model?
   Start with no features (the uniform model). At each step, for every candidate feature compute the gain in training log-likelihood from adding it, \(\Delta L(\mathcal{S}, f) = L(p_{\mathcal{S} \cup f}) - L(p_{\mathcal{S}})\), add the feature with the largest gain, re-fit, and repeat until a stopping criterion. Each added feature shrinks the set of allowed models.
   • Berger et al., 1996, A Maximum Entropy Approach to Natural Language Processing (Computational Linguistics), §4
3. Why is basic feature selection impractical, and what approximation fixes it?
   It needs a full maximum entropy fit for every candidate at every step. Instead, assume adding \(f\) changes only its own new parameter \(\alpha\), keeping the other \(\lambda\)s fixed: the approximate gain is a one-dimensional optimization over \(\alpha\) (a line search, e.g. Newton’s method), at the cost of probably underestimating gains.
   • Berger et al., 1996, A Maximum Entropy Approach to Natural Language Processing (Computational Linguistics), §4
4. How do Berger et al. decide when to stop adding features?
   Cross-validation: grow the model on part of the data and monitor log-likelihood on held-out data. Training likelihood keeps rising, but when held-out likelihood stops increasing the model has begun fitting noise (overtraining), so stop.
   • Berger et al., 1996, A Maximum Entropy Approach to Natural Language Processing (Computational Linguistics), §4