A Maximum Entropy Approach to Natural Language Processing

3.4 Exponential form

1. What form does the maximum entropy model take?
   An exponential (log-linear) model with one parameter per feature: \(p_\lambda(y \mid x) = \frac{1}{Z_\lambda(x)} \exp\big(\sum_i \lambda_i f_i(x, y)\big)\), with \(Z_\lambda(x) = \sum_y \exp\big(\sum_i \lambda_i f_i(x, y)\big)\).
   • Berger et al., 1996, A Maximum Entropy Approach to Natural Language Processing (Computational Linguistics), §3.4
2. How is the maximum entropy model found via Lagrange multipliers?
   Introduce a multiplier \(\lambda_i\) per constraint; maximizing the Lagrangian over \(p\) for fixed \(\lambda\) gives the exponential form \(p_\lambda\) and a dual function \(\Psi(\lambda)\). By the Kuhn–Tucker theorem the maximum entropy model is \(p_{\lambda^*}\) with \(\lambda^* = \arg\max_\lambda \Psi(\lambda)\).
   • Berger et al., 1996, A Maximum Entropy Approach to Natural Language Processing (Computational Linguistics), §3.4