Jäger (2007): Maximum Entropy Models and Stochastic Optimality Theory

This file formalizes Jäger's result that Boersma's Gradual Learning Algorithm (GLA) for Stochastic Optimality Theory is stochastic gradient ascent on the log-likelihood of a maximum entropy model of the kind Goldwater and Johnson propose. The expected GLA adjustment is the plasticity times the excess of the expected violations over the observed, which is the gradient of the log-likelihood once violations are read as non-positive features. Since that log-likelihood is concave, the maximum entropy learner reaches its global maximum, the guarantee Stochastic OT lacks. The file also reruns Boersma and Levelt's acquisition simulation over five syllable-structure constraints.

Main results

• expected_glaUpdate, expected_glaUpdate_eq_self_iff: the expected GLA adjustment, which vanishes exactly when the expected and observed violations agree.
• gla_eq_sga: the GLA step is the stochastic gradient step of the maximum entropy model.
• produced_stages: as FAITH overtakes the markedness constraints one by one, the syllable types are produced in the nested order CV, CVC, {V, VC}, {CVCC, VCC}, {CCV, CCVC, CCVCC}.
• corpusRate_order: over the corpus of Table 1 the markedness ranks fall in the order of their violation rates, *CODA first and *COMPLEXONSET last.

Implementation notes

• The maximum entropy probabilities are the HarmonicGrammar.maxEnt distributions of each input's candidates, as in Goldwater and Johnson's model; the sampled estimate of the expected violations is stated over an arbitrary distribution on the candidates.
• Table 1 is the paper's data, in permyriad; the initial ranks, 0 for FAITH and 10 for the markedness constraints, the learning rate 0.1 and the trajectory of Figure 1 are reported, not derived. The simulation's acquisition order refines the stages' ties by frequency, placing CVCC before VCC; the stages alone leave them tied.

References

• G. Jäger, Maximum Entropy Models and Stochastic Optimality Theory (2007)
• P. Boersma, Functional Phonology (1998)
• S. Goldwater and M. Johnson, Learning OT Constraint Rankings Using a Maximum Entropy Model (2003)

The Gradual Learning Algorithm as Stochastic Gradient Ascent

noncomputable def Jaeger2007.glaSign (r η : ℝ) (obs hyp : ℕ) : ℝ

The GLA update of Section 2 on a single rank, which adds the plasticity times the sign of the excess of the sampled hypothesis's violations over the observation's.

Equations

• Jaeger2007.glaSign r η obs hyp = r + η * ↑(SignType.sign (↑hyp - ↑obs))

def Jaeger2007.glaUpdate (r η : ℝ) (obs hyp : ℕ) : ℝ

The GLA update of a rank on binary constraints, which adds the plasticity times the excess of the sampled hypothesis's violations over the observation's, raising a constraint that favours the observation and lowering one that favours the hypothesis.

Equations

• Jaeger2007.glaUpdate r η obs hyp = r + η * (↑hyp - ↑obs)

theorem Jaeger2007.glaSign_eq_glaUpdate (r η : ℝ) {obs hyp : ℕ} (ho : obs ≤ 1) (hh : hyp ≤ 1) : glaSign r η obs hyp = glaUpdate r η obs hyp

On binary constraints the sign is idle, and the GLA update is the plain excess.

theorem Jaeger2007.expected_glaUpdate {O : Type u_1} [Fintype O] (p : O → ℝ) (hp : ∑ h : O, p h = 1) (c : O → ℕ) (o : O) (r η : ℝ) : ∑ h : O, p h * glaUpdate r η (c o) (c h) = r + η * (∑ h : O, p h * ↑(c h) - ↑(c o))

Over a distribution on the hypotheses, the expected GLA update of a rank is the plasticity times the excess of the expected violations over the observed (equation (1)).

theorem Jaeger2007.expected_glaUpdate_eq_self_iff {O : Type u_1} [Fintype O] (p : O → ℝ) (hp : ∑ h : O, p h = 1) (c : O → ℕ) (o : O) (r : ℝ) {η : ℝ} (hη : η ≠ 0) : ∑ h : O, p h * glaUpdate r η (c o) (c h) = r ↔ ∑ h : O, p h * ↑(c h) = ↑(c o)

The learner is at rest exactly when the expected and the observed violations agree, the convergence criterion of Section 4 shared by the GLA and Stochastic Gradient Ascent.

theorem Jaeger2007.hasDerivAt_log_maxEnt_update {O : Type u_1} [Fintype O] {I : Type u_2} [MeasurableSpace O] [MeasurableSingletonClass O] {n : ℕ} (con : OptimalityTheory.ConstraintSet (I × O) (Fin n)) (w : Fin n → ℝ) (j : Fin n) (i : I) (o : O) (t : ℝ) : HasDerivAt (fun (t : ℝ) => Real.log ((HarmonicGrammar.maxEnt (OptimalityTheory.ConstraintSet.comap (fun (x : O) => (i, x)) con).violations (Function.update w j t)).real {o})) ((∫ (o' : O), (OptimalityTheory.ConstraintSet.comap (fun (x : O) => (i, x)) con).violations o' ∂HarmonicGrammar.maxEnt (OptimalityTheory.ConstraintSet.comap (fun (x : O) => (i, x)) con).violations (Function.update w j t)) j - ↑(con j (i, o))) t

With the other weights held fixed, the derivative of the log probability of an observation in weight j is its expected violations of constraint j less the observed ones, which is the observed feature less its expectation once violations are read as non-positive features (equation (2)).

def Jaeger2007.sgaUpdate (r η observed sampled : ℝ) : ℝ

The Stochastic Gradient Ascent step of Section 4 on a single weight, which follows the gradient (2) with the empirical expectation replaced by the observed feature value and the model's expectation by the feature value of a sampled hypothesis.

Equations

• Jaeger2007.sgaUpdate r η observed sampled = r + η * (observed - sampled)

theorem Jaeger2007.gla_eq_sga (r η : ℝ) (obs hyp : ℕ) : glaUpdate r η obs hyp = sgaUpdate r η (-↑obs) (-↑hyp)

The GLA update is the Stochastic Gradient Ascent step once violations are read as the non-positive features of the maximum entropy model (Section 4).

The Dutch syllable types of Table 1

@[reducible, inline]

abbrev Jaeger2007.Syl : Type

A syllable type, given by the numbers of consonants in its onset and its coda, at most two each.

Equations

• Jaeger2007.Syl = (Fin 3 × Fin 3)

def Jaeger2007.cv : Syl

The nine types of Table 1.

Equations

• Jaeger2007.cv = (1, 0)

def Jaeger2007.cvc : Syl

Equations

• Jaeger2007.cvc = (1, 1)

def Jaeger2007.vc : Syl

Equations

• Jaeger2007.vc = (0, 1)

def Jaeger2007.v : Syl

Equations

• Jaeger2007.v = (0, 0)

def Jaeger2007.cvcc : Syl

Equations

• Jaeger2007.cvcc = (1, 2)

def Jaeger2007.ccvc : Syl

Equations

• Jaeger2007.ccvc = (2, 1)

def Jaeger2007.ccv : Syl

Equations

• Jaeger2007.ccv = (2, 0)

def Jaeger2007.vcc : Syl

Equations

• Jaeger2007.vcc = (0, 2)

def Jaeger2007.ccvcc : Syl

Equations

• Jaeger2007.ccvcc = (2, 2)

def Jaeger2007.Row.ofDatum (e : Datum) : Option (Syl × ℕ)

The row of Table 1 recorded by an example, a syllable type with its frequency in permyriad.

Equations

• Jaeger2007.Row.ofDatum e = do let on ← e.nat? "onset" let co ← e.nat? "coda" let f ← e.nat? "permyriad" if h : on < 3 ∧ co < 3 then some ((⟨on, ⋯⟩, ⟨co, ⋯⟩), f) else none

def Jaeger2007.rows : List (Syl × ℕ)

Table 1.

Equations

• Jaeger2007.rows = List.filterMap Jaeger2007.Row.ofDatum Jaeger2007.Examples.all

The constraints of Section 5

def Jaeger2007.starCoda : OptimalityTheory.Constraint (Syl × Syl)

*CODA, which penalizes a coda.

Equations

• Jaeger2007.starCoda = OptimalityTheory.Constraint.binary fun (c : Jaeger2007.Syl × Jaeger2007.Syl) => 1 ≤ c.2.2

def Jaeger2007.onset : OptimalityTheory.Constraint (Syl × Syl)

ONSET, which penalizes a vowel-initial syllable.

Equations

• Jaeger2007.onset = OptimalityTheory.Constraint.binary fun (c : Jaeger2007.Syl × Jaeger2007.Syl) => c.2.1 = 0

def Jaeger2007.starComplexCoda : OptimalityTheory.Constraint (Syl × Syl)

*COMPLEXCODA, which penalizes a complex coda.

Equations

• Jaeger2007.starComplexCoda = OptimalityTheory.Constraint.binary fun (c : Jaeger2007.Syl × Jaeger2007.Syl) => c.2.2 = 2

def Jaeger2007.starComplexOnset : OptimalityTheory.Constraint (Syl × Syl)

*COMPLEXONSET, which penalizes a complex onset.

Equations

• Jaeger2007.starComplexOnset = OptimalityTheory.Constraint.binary fun (c : Jaeger2007.Syl × Jaeger2007.Syl) => c.2.1 = 2

def Jaeger2007.faith : OptimalityTheory.Constraint (Syl × Syl)

FAITH, which penalizes an output that differs from its input.

Equations

• Jaeger2007.faith = OptimalityTheory.Constraint.binary fun (c : Jaeger2007.Syl × Jaeger2007.Syl) => c.1 ≠ c.2

def Jaeger2007.con : OptimalityTheory.ConstraintSet (Syl × Syl) (Fin 5)

The constraint set, in the order of the converged ranking FAITH ≫ *COMPLEXONSET ≫ *COMPLEXCODA ≫ ONSET ≫ *CODA.

Equations

• Jaeger2007.con = ![Jaeger2007.faith, Jaeger2007.starComplexOnset, Jaeger2007.starComplexCoda, Jaeger2007.onset, Jaeger2007.starCoda]

def Jaeger2007.cands : Syl → Finset Syl

Every syllable type is a candidate output for every input.

Equations

• Jaeger2007.cands x✝ = Finset.univ

theorem Jaeger2007.faithful_iff (σ : OptimalityTheory.Ranking (Fin 5) 5) (i : Syl) : OptimalityTheory.PicksAt cands con σ i i ↔ ∀ (k : Fin 5), con k (i, i) = 1 → σ.Dominates 0 k

A ranking produces an input faithfully exactly when every markedness constraint the input violates is ranked below FAITH.

def Jaeger2007.produced (S : Finset (Fin 5)) : Finset Syl

The syllable types produced faithfully once the markedness constraints in S are below FAITH, namely those violating no other markedness constraint.

Equations

• Jaeger2007.produced S = {i : Jaeger2007.Syl | ∀ (k : Fin 5), Jaeger2007.con k (i, i) = 1 → k ∈ S}

theorem Jaeger2007.mem_produced_iff (σ : OptimalityTheory.Ranking (Fin 5) 5) (i : Syl) : i ∈ produced (Finset.filter (σ.Dominates 0) Finset.univ) ↔ OptimalityTheory.PicksAt cands con σ i i

The types a ranking produces faithfully are those of the stage it is at.

theorem Jaeger2007.produced_stages : produced ∅ = {cv} ∧ produced {4} = {cv, cvc} ∧ produced {4, 3} = {cv, cvc, v, vc} ∧ produced {4, 3, 2} = {cv, cvc, v, vc, cvcc, vcc} ∧ produced {4, 3, 2, 1} = Finset.univ

The stages at which FAITH overtakes *CODA, ONSET, *COMPLEXCODA and *COMPLEXONSET in turn produce the syllable types in the nested order CV; CVC; V, VC; CVCC, VCC; CCV, CCVC, CCVCC.

theorem Jaeger2007.cv_unmarked (i : Syl) (k : Fin 5) : k ≠ 0 → con k (i, cv) = 0

CV violates no markedness constraint.

theorem Jaeger2007.initial_glaUpdate (r η : ℝ) (o : Syl) (k : Fin 5) (hk : k ≠ 0) : ∑ h : Syl, Pi.single cv 1 h * glaUpdate r η (con k (o, o)) (con k (o, h)) = r - η * ↑(con k (o, o))

A learner producing CV with certainty, the initial state with FAITH at 0 and the markedness constraints at 10, lowers each markedness rank by the plasticity times the observation's violations, (1).

def Jaeger2007.corpusRate (k : Fin 5) : ℕ

The violation rate of a constraint in the corpus of Table 1, in permyriad.

Equations

• Jaeger2007.corpusRate k = (List.map (fun (r : Jaeger2007.Syl × ℕ) => r.2 * Jaeger2007.con k (r.1, r.1)) Jaeger2007.rows).sum

theorem Jaeger2007.corpusRate_order : corpusRate 0 = 0 ∧ corpusRate 1 < corpusRate 2 ∧ corpusRate 2 < corpusRate 3 ∧ corpusRate 3 < corpusRate 4

FAITH is never violated in the corpus, and the markedness ranks fall fastest for *CODA, then ONSET, *COMPLEXCODA and *COMPLEXONSET, the order in which FAITH overtakes them.