A Maximum Entropy Approach to Natural Language Processing

3.6 Computing the parameters

1. Why is the dual function convenient to optimize, and with which methods?
   It is smooth and concave in \(\lambda\), so standard numerical methods work: coordinate-wise ascent (the Brown algorithm), gradient methods, or iterative scaling designed for maximum entropy.
   • Berger et al., 1996, A Maximum Entropy Approach to Natural Language Processing (Computational Linguistics), §3.6
2. Describe Improved Iterative Scaling (IIS).
   Start with all \(\lambda_i = 0\). Repeatedly, for each feature, find the increment \(\Delta\lambda_i\) solving \(\sum_{x,y} \tilde{p}(x)\, p(y \mid x)\, f_i(x, y)\, e^{\Delta\lambda_i f^\#(x, y)} = \tilde{p}(f_i)\), where \(f^\#(x, y) = \sum_i f_i(x, y)\) is the number of active features, and update \(\lambda_i \leftarrow \lambda_i + \Delta\lambda_i\) until convergence.
   • Berger et al., 1996, A Maximum Entropy Approach to Natural Language Processing (Computational Linguistics), §3.6
3. What is the IIS update when every event has the same number \(M\) of active features?
   \(\Delta\lambda_i = \frac{1}{M} \log \frac{\tilde{p}(f_i)}{p_\lambda(f_i)}\); otherwise the increment is found numerically (e.g. Newton’s method). Darroch and Ratcliff’s original Generalized Iterative Scaling additionally requires features to sum to 1.
   • Berger et al., 1996, A Maximum Entropy Approach to Natural Language Processing (Computational Linguistics), §3.6