Maximum Entropy (Maxent) Models

• applying Optimization where the objective function is the entropy formula 𝐻_𝐏(𝐏) and subjected with any additional constraints

Maxent Model - Example

let’s consider a discrete random variable 𝐶 with 2 outcomes: ℎ and 𝑡

• 𝐏(𝐶=ℎ) = probability of seeing heads
• 𝐏(𝐶=𝑡) = probability of seeing tails

below is the formula for univariate entropy, in which we want to maximize 𝐻_𝐏(𝐏) with respect to the constraints of the model

• 𝐻_𝐏(𝐏) = 𝛴_𝑥∊𝐶[ - 𝐏(𝐶=𝑥) 𝑙𝑛 𝐏(𝐶=𝑥) ]

below are 3 different models

Why Find Maximum Entropy Model?

maximizing entropy in effect helps us find an estimated distribution model 𝐏ˆ that:

• minimizes commitment (which is another way of saying maximizes entropy)
• resembles some reference to the true population distribution (actually empirical distribution)

this is what we want in the estimated distribution model 𝐏ˆ

Solution

is to maximize entropy 𝐻, subject to feature-based constraints:

• 𝐄_𝐏[𝑓_𝑖] = 𝐄_𝐏ˆ[𝑓_𝑖] ↔ 𝛴_{𝑥∊𝑓𝑖}𝐏_𝑥 = 𝐶_𝑖

adding constraints/features:

• lowers maximum entropy
• raises the maximum likelihood of data
• brings the distribution model further from the uniform distribution
• brings the distribution model closer to the empirical distribution

Maxent - Properties

maximum entropy models are convex

a model 𝐹 is convex when: 𝐹(𝛴𝑖𝑤𝑖𝑥𝑖) ≥  𝛴𝑖𝑤𝑖𝐹(𝑥𝑖) where 𝛴𝑖𝑤𝑖 = 1 convexity guarantees a single, global maximum because any higher points are greedily reachable maximum entropy models 𝐻𝐏(𝐏) = 𝛴𝑥∊𝐶[ - 𝐏(𝐶=𝑥) 𝑙𝑛 𝐏(𝐶=𝑥) ] are convex 𝐏(𝐶=𝑥) 𝑙𝑛 𝐏(𝐶=𝑥) is convex 𝛴𝑥∊𝐶[ - 𝐏(𝐶=𝑥) 𝑙𝑛 𝐏(𝐶=𝑥) ] is convex (sum of convex functions is convex) the feasible-region of constrained 𝐻𝐏(𝐏) is a linear subspace that is convex the constrained entropy surface is therefore convex

the Maximum Likelihood Estimation (MLE) exponential model formulation is also convex (dual)

Subpages

• Feature Overlapping - Feature Interaction - Double／Overcounting Counting
• Maxent - NLP PoS Example

Resources

• Stanford’s NLP Video Lecture