Berger, Della Pietra and Della Pietra (1996): A Maximum Entropy Approach to Natural Language Processing

Berger, Della Pietra and Della Pietra model a process that outputs y in a context x by the most uniform conditional distribution consistent with the statistics of a sample. A statistic is the expectation of a feature f(x, y); a model satisfies its constraint when its expectation of the feature, averaged over the sample's contexts, is the sample's (4), and among the models satisfying every constraint the maximum entropy principle chooses the one of greatest conditional entropy (5)–(6). The maximizer of the Lagrangian (7) for fixed multipliers λ has the exponential form (10), and the maximum entropy model is the member of that family that maximizes the likelihood of the sample (§3.5).

The motivating example (§2) translates English in by one of five French phrases. With only the phrases known the most uniform model is uniform; requiring p(dans) + p(en) = 3/10 makes it 3/20, 3/20, 7/30, 7/30, 7/30; adding p(dans) + p(à) = 1/2 gives the solution the paper leaves to the reader (§3.4), with p(dans) = (9 − √51)/10.

Main results

• isGreatest_uniform, isGreatest_two, isGreatest_three: the maximum entropy models of §2.
• lagrangian_le_lagrangian_model: the model p_λ of (10) maximizes the Lagrangian (8).
• lagrangian_model_eq_neg_logLik: the value of the Lagrangian at p_λ is minus the log-likelihood (13) of p_λ.
• model_mem_constraints, isGreatest_condEntropy_model, condEntropy_model_eq_neg_logLik: the Kuhn–Tucker conclusion of §3.5. The parameters of greatest likelihood give the maximum entropy model in C, whose entropy is minus that likelihood.
• eq_model_of_condEntropy_eq: the maximum entropy model is unique at the observed contexts.
• concaveOn_logLik_model: the log-likelihood is concave in the parameters (§3.6).

Implementation notes

• Features are real-valued, f : X × Y → ι → ℝ, binary in the paper. The model (10) is HarmonicGrammar.condMaxEnt f (-λ), the substrate's harmony being minus the weighted statistic, and the paper's conditional entropy (5) is H[Prod.snd | Prod.fst ; p̃.fst ⊗ₘ q], its footnote 1's H(Y | X) under the joint p̃(x) p(y|x).
• With the Lagrangian (7), the value at its maximizer is ∑ p̃(x) log Z_λ(x) − λ · p̃(f), which is −L(p_λ); (11) prints this dual function with the opposite sign, as L(p_λ) (14), and so poses the dual as a maximization. The dual of (7) is minimized; maximizing L(p_λ) is the same problem.
• §3.3 says the maximum entropy model in C is unique; it is unique at the contexts of positive empirical mass, and unconstrained at the others.

TODO

• Footnote 2's unattained case, where the maximum entropy model is a limit of models p_λ.
• Improved iterative scaling (§3.6), feature selection (§4) and the applications of §5.

References

• [BDPDP96]

The translation example (§2)

inductive BergerDellaPietraDellaPietra1996.Phrase : Type

The French renderings of in in the expert's sample.

• dans : Phrase
• en : Phrase
• à : Phrase
• auCoursDe : Phrase
• pendant : Phrase

@[instance_reducible]

instance BergerDellaPietraDellaPietra1996.instDecidableEqPhrase : DecidableEq Phrase

Equations

• BergerDellaPietraDellaPietra1996.instDecidableEqPhrase x✝ y✝ = if h : x✝.ctorIdx = y✝.ctorIdx then isTrue ⋯ else isFalse ⋯

@[instance_reducible]

instance BergerDellaPietraDellaPietra1996.instFintypePhrase : Fintype Phrase

Equations

• One or more equations did not get rendered due to their size.

@[instance_reducible]

instance BergerDellaPietraDellaPietra1996.instInhabitedPhrase : Inhabited Phrase

Equations

• BergerDellaPietraDellaPietra1996.instInhabitedPhrase = { default := BergerDellaPietraDellaPietra1996.instInhabitedPhrase.default }

@[instance_reducible]

instance BergerDellaPietraDellaPietra1996.instMeasurableSpacePhrase : MeasurableSpace Phrase

Equations

• BergerDellaPietraDellaPietra1996.instMeasurableSpacePhrase = ⊤

instance BergerDellaPietraDellaPietra1996.instMeasurableSingletonClassPhrase : MeasurableSingletonClass Phrase

theorem BergerDellaPietraDellaPietra1996.Phrase.sum_eq {M : Type u_1} [AddCommMonoid M] (g : Phrase → M) : ∑ φ : Phrase, g φ = g dans + g en + g à + g auCoursDe + g pendant

def BergerDellaPietraDellaPietra1996.Phrase.dansOrEn : Phrase → ℝ

The feature of the second constraint, the expert choosing dans or en.

Equations

• BergerDellaPietraDellaPietra1996.Phrase.dans.dansOrEn = 1
• BergerDellaPietraDellaPietra1996.Phrase.en.dansOrEn = 1
• x✝.dansOrEn = 0

def BergerDellaPietraDellaPietra1996.Phrase.dansOrÀ : Phrase → ℝ

The feature of the third constraint, the expert choosing dans or à.

Equations

• BergerDellaPietraDellaPietra1996.Phrase.dans.dansOrÀ = 1
• BergerDellaPietraDellaPietra1996.Phrase.à.dansOrÀ = 1
• x✝.dansOrÀ = 0

theorem BergerDellaPietraDellaPietra1996.integral_eq (q : MeasureTheory.Measure Phrase) [MeasureTheory.IsFiniteMeasure q] (g : Phrase → ℝ) : ∫ (φ : Phrase), g φ ∂q = q.real {Phrase.dans} * g Phrase.dans + q.real {Phrase.en} * g Phrase.en + q.real {Phrase.à} * g Phrase.à + q.real {Phrase.auCoursDe} * g Phrase.auCoursDe + q.real {Phrase.pendant} * g Phrase.pendant

theorem BergerDellaPietraDellaPietra1996.isGreatest_uniform : IsGreatest (InformationTheory.measureEntropy '' {q : MeasureTheory.Measure Phrase | MeasureTheory.IsProbabilityMeasure q}) (InformationTheory.measureEntropy (HarmonicGrammar.maxEnt (fun (x : Phrase) => 0) 0)) ∧ ∀ (φ : Phrase), (HarmonicGrammar.maxEnt (fun (x : Phrase) => 0) 0).real {φ} = 1 / 5

Knowing only the five phrases, the maximum entropy model is uniform. With no features, every distribution satisfies the constraints, and the uniform one has the greatest entropy.

def BergerDellaPietraDellaPietra1996.twoFeatures (φ : Phrase) : Fin 1 → ℝ

The statistic of the first two constraints.

Equations

• BergerDellaPietraDellaPietra1996.twoFeatures φ = ![φ.dansOrEn]

@[reducible, inline]

noncomputable abbrev BergerDellaPietraDellaPietra1996.twoModel : MeasureTheory.Measure Phrase

The model maximizing entropy subject to p(dans) + p(en) = 3/10.

Equations

• BergerDellaPietraDellaPietra1996.twoModel = HarmonicGrammar.maxEnt BergerDellaPietraDellaPietra1996.twoFeatures ![Real.log (14 / 9)]

theorem BergerDellaPietraDellaPietra1996.twoModel_real_singleton : twoModel.real {Phrase.dans} = 3 / 20 ∧ twoModel.real {Phrase.en} = 3 / 20 ∧ twoModel.real {Phrase.à} = 7 / 30 ∧ twoModel.real {Phrase.auCoursDe} = 7 / 30 ∧ twoModel.real {Phrase.pendant} = 7 / 30

theorem BergerDellaPietraDellaPietra1996.isGreatest_two : IsGreatest (InformationTheory.measureEntropy '' {q : MeasureTheory.Measure Phrase | MeasureTheory.IsProbabilityMeasure q ∧ q.real {Phrase.dans} + q.real {Phrase.en} = 3 / 10}) (InformationTheory.measureEntropy twoModel)

Requiring p(dans) + p(en) = 3/10, the most uniform model gives dans and en 3/20 each and the other three phrases 7/30 each.

def BergerDellaPietraDellaPietra1996.threeFeatures (φ : Phrase) : Fin 2 → ℝ

The statistic of all three constraints.

Equations

• BergerDellaPietraDellaPietra1996.threeFeatures φ = ![φ.dansOrEn, φ.dansOrÀ]

theorem BergerDellaPietraDellaPietra1996.maxEnt_three_real_singleton {d e a c : ℝ} (he : 0 < e) (ha : 0 < a) (hc : 0 < c) (hR : e * a = d * c) (hN : d + e + a + 2 * c = 1) : (HarmonicGrammar.maxEnt threeFeatures ![-Real.log (e / c), -Real.log (a / c)]).real {Phrase.dans} = d ∧ (HarmonicGrammar.maxEnt threeFeatures ![-Real.log (e / c), -Real.log (a / c)]).real {Phrase.en} = e ∧ (HarmonicGrammar.maxEnt threeFeatures ![-Real.log (e / c), -Real.log (a / c)]).real {Phrase.à} = a ∧ (HarmonicGrammar.maxEnt threeFeatures ![-Real.log (e / c), -Real.log (a / c)]).real {Phrase.auCoursDe} = c ∧ (HarmonicGrammar.maxEnt threeFeatures ![-Real.log (e / c), -Real.log (a / c)]).real {Phrase.pendant} = c

A positive distribution of the five phrases in which au cours de and pendant are equally likely and p(en) p(à) = p(dans) p(au cours de) is the exponential model of threeFeatures, the exponentials of the two multipliers being p(en)/p(au cours de) and p(à)/p(au cours de).

@[reducible, inline]

noncomputable abbrev BergerDellaPietraDellaPietra1996.threeModel : MeasureTheory.Measure Phrase

The model maximizing entropy subject to all three constraints, which §3.4 leaves to the reader.

Equations

• One or more equations did not get rendered due to their size.

theorem BergerDellaPietraDellaPietra1996.threeModel_real_singleton : threeModel.real {Phrase.dans} = (9 - √51) / 10 ∧ threeModel.real {Phrase.en} = (√51 - 6) / 10 ∧ threeModel.real {Phrase.à} = (√51 - 4) / 10 ∧ threeModel.real {Phrase.auCoursDe} = (11 - √51) / 20 ∧ threeModel.real {Phrase.pendant} = (11 - √51) / 20

theorem BergerDellaPietraDellaPietra1996.isGreatest_three : IsGreatest (InformationTheory.measureEntropy '' {q : MeasureTheory.Measure Phrase | MeasureTheory.IsProbabilityMeasure q ∧ q.real {Phrase.dans} + q.real {Phrase.en} = 3 / 10 ∧ q.real {Phrase.dans} + q.real {Phrase.à} = 1 / 2}) (InformationTheory.measureEntropy threeModel)

Requiring also p(dans) + p(à) = 1/2, the most uniform model gives dans (9 − √51)/10.

Maximum entropy modeling (§3)

def BergerDellaPietraDellaPietra1996.constraints {X : Type u_1} {Y : Type u_2} {ι : Type u_3} [MeasurableSpace X] [MeasurableSpace Y] [Fintype ι] (f : X × Y → ι → ℝ) (p : MeasureTheory.Measure (X × Y)) : Set (ProbabilityTheory.Kernel X Y)

The models satisfying the constraints (4), conditional distributions whose expectations of the features, averaged over the sample's contexts, are the sample's.

Equations

• BergerDellaPietraDellaPietra1996.constraints f p = {q : ProbabilityTheory.Kernel X Y | ProbabilityTheory.IsMarkovKernel q ∧ ∫ (z : X × Y), f z ∂p.fst.compProd q = ∫ (z : X × Y), f z ∂p}

noncomputable def BergerDellaPietraDellaPietra1996.model {X : Type u_1} {Y : Type u_2} {ι : Type u_3} [Fintype X] [MeasurableSpace X] [MeasurableSingletonClass X] [MeasurableSpace Y] [Fintype ι] (f : X × Y → ι → ℝ) (θ : ι → ℝ) : ProbabilityTheory.Kernel X Y

The exponential model (10) with multipliers θ, the paper's λ.

Equations

• BergerDellaPietraDellaPietra1996.model f θ = HarmonicGrammar.condMaxEnt f (-θ)

noncomputable def BergerDellaPietraDellaPietra1996.lagrangian {X : Type u_1} {Y : Type u_2} {ι : Type u_3} [MeasurableSpace X] [MeasurableSpace Y] [Fintype ι] (f : X × Y → ι → ℝ) (p : MeasureTheory.Measure (X × Y)) (q : ProbabilityTheory.Kernel X Y) (θ : ι → ℝ) : ℝ

The Lagrangian (7), the conditional entropy (5) plus each multiplier times its constraint's violation.

Equations

• BergerDellaPietraDellaPietra1996.lagrangian f p q θ = InformationTheory.condEntropy Prod.snd Prod.fst (p.fst.compProd q) + θ ⬝ᵥ (∫ (z : X × Y), f z ∂p.fst.compProd q - ∫ (z : X × Y), f z ∂p)

noncomputable def BergerDellaPietraDellaPietra1996.logLik {X : Type u_1} {Y : Type u_2} [MeasurableSpace X] [MeasurableSpace Y] (p : MeasureTheory.Measure (X × Y)) (q : ProbabilityTheory.Kernel X Y) : ℝ

The log-likelihood (13) of a conditional model on the sample.

Equations

• BergerDellaPietraDellaPietra1996.logLik p q = ∫ (z : X × Y), Real.log ((q z.1).real {z.2}) ∂p

theorem BergerDellaPietraDellaPietra1996.logLik_model {X : Type u_1} {Y : Type u_2} {ι : Type u_3} [Fintype X] [MeasurableSpace X] [MeasurableSingletonClass X] [MeasurableSpace Y] [Fintype ι] (f : X × Y → ι → ℝ) (p : MeasureTheory.Measure (X × Y)) (θ : ι → ℝ) : logLik p (model f θ) = HarmonicGrammar.condLogLikelihood f p (-θ)

theorem BergerDellaPietraDellaPietra1996.lagrangian_le_lagrangian_model {X : Type u_1} {Y : Type u_2} {ι : Type u_3} [Fintype X] [MeasurableSpace X] [MeasurableSingletonClass X] [MeasurableSpace Y] [Fintype ι] (f : X × Y → ι → ℝ) (p : MeasureTheory.Measure (X × Y)) [Fintype Y] [MeasurableSingletonClass Y] [Nonempty Y] [MeasureTheory.IsProbabilityMeasure p] (θ : ι → ℝ) (q : ProbabilityTheory.Kernel X Y) [ProbabilityTheory.IsMarkovKernel q] : lagrangian f p q θ ≤ lagrangian f p (model f θ) θ

The model p_θ maximizes the Lagrangian for fixed multipliers (8), (10).

theorem BergerDellaPietraDellaPietra1996.lagrangian_model_eq_neg_logLik {X : Type u_1} {Y : Type u_2} {ι : Type u_3} [Fintype X] [MeasurableSpace X] [MeasurableSingletonClass X] [MeasurableSpace Y] [Fintype ι] (f : X × Y → ι → ℝ) (p : MeasureTheory.Measure (X × Y)) [Fintype Y] [MeasurableSingletonClass Y] [Nonempty Y] [MeasureTheory.IsProbabilityMeasure p] (θ : ι → ℝ) : lagrangian f p (model f θ) θ = -logLik p (model f θ)

The value of the Lagrangian at its maximizer is minus the log-likelihood of p_θ.

theorem BergerDellaPietraDellaPietra1996.model_mem_constraints {X : Type u_1} {Y : Type u_2} {ι : Type u_3} [Fintype X] [MeasurableSpace X] [MeasurableSingletonClass X] [MeasurableSpace Y] [Fintype ι] {f : X × Y → ι → ℝ} {p : MeasureTheory.Measure (X × Y)} [Fintype Y] [MeasurableSingletonClass Y] [Nonempty Y] [MeasureTheory.IsProbabilityMeasure p] {θ : ι → ℝ} (h : IsMaxOn (fun (θ : ι → ℝ) => logLik p (model f θ)) Set.univ θ) : model f θ ∈ constraints f p

The parameters of greatest likelihood give a model satisfying the constraints.

theorem BergerDellaPietraDellaPietra1996.isGreatest_condEntropy_model {X : Type u_1} {Y : Type u_2} {ι : Type u_3} [Fintype X] [MeasurableSpace X] [MeasurableSingletonClass X] [MeasurableSpace Y] [Fintype ι] {f : X × Y → ι → ℝ} {p : MeasureTheory.Measure (X × Y)} [Fintype Y] [MeasurableSingletonClass Y] [Nonempty Y] [MeasureTheory.IsProbabilityMeasure p] {θ : ι → ℝ} (h : IsMaxOn (fun (θ : ι → ℝ) => logLik p (model f θ)) Set.univ θ) : IsGreatest ((fun (q : ProbabilityTheory.Kernel X Y) => InformationTheory.condEntropy Prod.snd Prod.fst (p.fst.compProd q)) '' constraints f p) (InformationTheory.condEntropy Prod.snd Prod.fst (p.fst.compProd (model f θ)))

The Kuhn–Tucker conclusion of §3.5. The model in the parametric family that maximizes the likelihood of the sample is the maximum entropy model in C.

theorem BergerDellaPietraDellaPietra1996.condEntropy_model_eq_neg_logLik {X : Type u_1} {Y : Type u_2} {ι : Type u_3} [Fintype X] [MeasurableSpace X] [MeasurableSingletonClass X] [MeasurableSpace Y] [Fintype ι] {f : X × Y → ι → ℝ} {p : MeasureTheory.Measure (X × Y)} [Fintype Y] [MeasurableSingletonClass Y] [Nonempty Y] [MeasureTheory.IsProbabilityMeasure p] {θ : ι → ℝ} (h : IsMaxOn (fun (θ : ι → ℝ) => logLik p (model f θ)) Set.univ θ) : InformationTheory.condEntropy Prod.snd Prod.fst (p.fst.compProd (model f θ)) = -logLik p (model f θ)

The primal and dual values agree, the greatest entropy in C being minus the greatest log-likelihood.

theorem BergerDellaPietraDellaPietra1996.eq_model_of_condEntropy_eq {X : Type u_1} {Y : Type u_2} {ι : Type u_3} [Fintype X] [MeasurableSpace X] [MeasurableSingletonClass X] [MeasurableSpace Y] [Fintype ι] {f : X × Y → ι → ℝ} {p : MeasureTheory.Measure (X × Y)} [Fintype Y] [MeasurableSingletonClass Y] [Nonempty Y] [MeasureTheory.IsProbabilityMeasure p] {θ : ι → ℝ} (h : IsMaxOn (fun (θ : ι → ℝ) => logLik p (model f θ)) Set.univ θ) {q : ProbabilityTheory.Kernel X Y} (hq : q ∈ constraints f p) (hH : InformationTheory.condEntropy Prod.snd Prod.fst (p.fst.compProd q) = InformationTheory.condEntropy Prod.snd Prod.fst (p.fst.compProd (model f θ))) {x : X} (hx : p.fst {x} ≠ 0) : q x = (model f θ) x

A model in C with the greatest entropy is the maximum entropy model at every context of positive empirical mass.

theorem BergerDellaPietraDellaPietra1996.concaveOn_logLik_model {X : Type u_1} {Y : Type u_2} {ι : Type u_3} [Fintype X] [MeasurableSpace X] [MeasurableSingletonClass X] [MeasurableSpace Y] [Fintype ι] (f : X × Y → ι → ℝ) (p : MeasureTheory.Measure (X × Y)) [Fintype Y] [MeasurableSingletonClass Y] [Nonempty Y] [MeasureTheory.IsProbabilityMeasure p] : ConcaveOn ℝ Set.univ fun (θ : ι → ℝ) => logLik p (model f θ)

The log-likelihood of the model is concave in the multipliers (§3.6).