Goldwater and Johnson (2003): Learning OT Constraint Rankings Using a Maximum Entropy Model

Goldwater and Johnson's maximum entropy model of constraint-based phonology gives an output of an input the probability of eq. (1), the MaxEnt distribution maxEnt of the input's candidates. Learning maximizes the log pseudo-likelihood of the training pairs (eq. (2)) less a Gaussian penalty on the weights (eq. (3)). The log pseudo-likelihood is concave in the weights, as footnote 4 says, and the penalty makes the objective strictly concave, so at most one weighting maximizes it. Replicating the corpus r times while dividing the prior's variance by r rescales the objective by r, so only nσ² matters for the weights learned.

The learned weights of the Wolof tongue-root grammar (Table 1) are exponentially separated, the spacing that recovers strict domination in Johnson's limit. For Boersma and Hayes's Finnish genitive plurals, a model choosing between two candidates sees their violations only through the difference vector, so Table 2's naapuri and ministeri classes, distinct in violations but not in differences, are one class for the learner.

Main results

• concaveOn_logPseudoLikelihood, eq_of_isMaxOn_regularizedObjective: footnote 4.
• isGreatest_condEntropy_of_isMaxOn_logPseudoLikelihood: section 2's maximum entropy, the most likely grammar having the greatest conditional entropy among the models matching the training data.
• regularizedObjective_replicate: only nσ² matters.
• wolof_separated: Table 1's weights are exponentially separated.
• maxEnt_pairConstraintSet_real_zero, rows_collapse: a pair sees only differences (Table 3).

Implementation notes

Footnote 4 infers a single global maximum from concavity of the log conditional likelihood, but a concave function can be maximized on a whole convex set, as when two constraints are violated alike; uniqueness comes from the strictly convex penalty of (3).

The four Finnish rows carry Table 2's violation vectors as digit strings, one digit per constraint in Boersma and Hayes's order; Anttila's full grammar is in Studies/Anttila1997.lean. The Wolof weights are the learned values of Table 1; the error rates and Table 4 stay in the paper, as does the comparison with Boersma's Gradual Learning Algorithm.

References

• [GJ03]
• [BH01]
• [Boe97]
• [BDPDP96]
• [Joh02]
• [SL06]

noncomputable def GoldwaterJohnson2003.logPseudoLikelihood {I : Type u_1} {O : Type u_2} [MeasurableSpace O] {n : ℕ} (con : OptimalityTheory.ConstraintSet (I × O) (Fin n)) (w : Fin n → ℝ) (data : List (I × O)) : ℝ

The log pseudo-likelihood of the training pairs, eq. (2) logged, sums the log-probabilities of the observed outputs under the MaxEnt distributions (1) of their inputs' candidates.

Equations

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

noncomputable def GoldwaterJohnson2003.regularizedObjective {I : Type u_1} {O : Type u_2} [MeasurableSpace O] {n : ℕ} (con : OptimalityTheory.ConstraintSet (I × O) (Fin n)) (w : Fin n → ℝ) (data : List (I × O)) (σ : ℝ) : ℝ

Eq. (3) with the paper's common prior, mean zero and deviation σ for every weight.

Equations

• GoldwaterJohnson2003.regularizedObjective con w data σ = GoldwaterJohnson2003.logPseudoLikelihood con w data - ∑ j : Fin n, w j ^ 2 / (2 * σ ^ 2)

theorem GoldwaterJohnson2003.regularizedObjective_replicate {I : Type u_1} {O : Type u_2} [MeasurableSpace O] {n : ℕ} (con : OptimalityTheory.ConstraintSet (I × O) (Fin n)) (w : Fin n → ℝ) (data : List (I × O)) {r : ℕ} (hr : 0 < r) {σ σ' : ℝ} (hσ : 0 < σ) (h : ↑r * σ' ^ 2 = σ ^ 2) : regularizedObjective con w (List.replicate r data).flatten σ' = ↑r * regularizedObjective con w data σ

Replicating the corpus r times while dividing the prior's variance by r multiplies the objective by r: the weights learned depend on nσ² alone.

theorem GoldwaterJohnson2003.regularizedObjective_replicate_le_iff {I : Type u_1} {O : Type u_2} [MeasurableSpace O] {n : ℕ} (con : OptimalityTheory.ConstraintSet (I × O) (Fin n)) (w w' : Fin n → ℝ) (data : List (I × O)) {r : ℕ} (hr : 0 < r) {σ σ' : ℝ} (hσ : 0 < σ) (h : ↑r * σ' ^ 2 = σ ^ 2) : regularizedObjective con w' (List.replicate r data).flatten σ' ≤ regularizedObjective con w (List.replicate r data).flatten σ' ↔ regularizedObjective con w' data σ ≤ regularizedObjective con w data σ

The same weights maximize the objective before and after replication.

noncomputable def GoldwaterJohnson2003.empirical {I : Type u_1} {O : Type u_2} [MeasurableSpace O] [MeasurableSpace I] (data : List (I × O)) : MeasureTheory.Measure (I × O)

The empirical distribution of the training pairs.

Equations

• GoldwaterJohnson2003.empirical data = (↑data.length)⁻¹ • ∑ i : Fin data.length, MeasureTheory.Measure.dirac data[i]

theorem GoldwaterJohnson2003.isProbabilityMeasure_empirical {I : Type u_1} {O : Type u_2} [MeasurableSpace O] [MeasurableSpace I] (data : List (I × O)) (h : data ≠ []) : MeasureTheory.IsProbabilityMeasure (empirical data)

theorem GoldwaterJohnson2003.concaveOn_logPseudoLikelihood {I : Type u_1} {O : Type u_2} [MeasurableSpace O] {n : ℕ} [Fintype O] [MeasurableSingletonClass O] (con : OptimalityTheory.ConstraintSet (I × O) (Fin n)) (data : List (I × O)) : ConcaveOn ℝ Set.univ fun (w : Fin n → ℝ) => logPseudoLikelihood con w data

The log pseudo-likelihood is concave in the weights (footnote 4), as a sum of the log-likelihoods of single observations.

theorem GoldwaterJohnson2003.strictConcaveOn_regularizedObjective {I : Type u_1} {O : Type u_2} [MeasurableSpace O] {n : ℕ} [Fintype O] [MeasurableSingletonClass O] (con : OptimalityTheory.ConstraintSet (I × O) (Fin n)) (data : List (I × O)) {σ : ℝ} (hσ : σ ≠ 0) : StrictConcaveOn ℝ Set.univ fun (w : Fin n → ℝ) => regularizedObjective con w data σ

With the Gaussian prior the objective (3) is strictly concave in the weights.

theorem GoldwaterJohnson2003.eq_of_isMaxOn_regularizedObjective {I : Type u_1} {O : Type u_2} [MeasurableSpace O] {n : ℕ} [Fintype O] [MeasurableSingletonClass O] (con : OptimalityTheory.ConstraintSet (I × O) (Fin n)) (data : List (I × O)) {σ : ℝ} (hσ : σ ≠ 0) {w w' : Fin n → ℝ} (hw : IsMaxOn (fun (w : Fin n → ℝ) => regularizedObjective con w data σ) Set.univ w) (hw' : IsMaxOn (fun (w : Fin n → ℝ) => regularizedObjective con w data σ) Set.univ w') : w = w'

At most one weighting maximizes the objective (3), footnote 4's single global maximum.

Maximum entropy (section 2)

theorem GoldwaterJohnson2003.logPseudoLikelihood_eq {I : Type u_1} {O : Type u_2} [MeasurableSpace O] {n : ℕ} [Fintype O] [MeasurableSingletonClass O] [MeasurableSpace I] [Fintype I] [MeasurableSingletonClass I] (con : OptimalityTheory.ConstraintSet (I × O) (Fin n)) (data : List (I × O)) (h : data ≠ []) (w : Fin n → ℝ) : logPseudoLikelihood con w data = ↑data.length * HarmonicGrammar.condLogLikelihood con.violations (empirical data) w

The log pseudo-likelihood (2) is the number of training pairs times the conditional log-likelihood of their empirical distribution.

theorem GoldwaterJohnson2003.isGreatest_condEntropy_of_isMaxOn_logPseudoLikelihood {I : Type u_1} {O : Type u_2} [MeasurableSpace O] {n : ℕ} [Fintype O] [MeasurableSingletonClass O] [MeasurableSpace I] [Fintype I] [MeasurableSingletonClass I] (con : OptimalityTheory.ConstraintSet (I × O) (Fin n)) (data : List (I × O)) (h : data ≠ []) {w : Fin n → ℝ} (hw : IsMaxOn (fun (w : Fin n → ℝ) => logPseudoLikelihood con w data) Set.univ w) : IsGreatest ((fun (q : ProbabilityTheory.Kernel I O) => InformationTheory.condEntropy Prod.snd Prod.fst ((empirical data).fst.compProd q)) '' {q : ProbabilityTheory.Kernel I O | ProbabilityTheory.IsMarkovKernel q ∧ ∫ (z : I × O), con.violations z ∂(empirical data).fst.compProd q = ∫ (z : I × O), con.violations z ∂empirical data}) (InformationTheory.condEntropy Prod.snd Prod.fst ((empirical data).fst.compProd (HarmonicGrammar.condMaxEnt con.violations w)))

Maximum entropy models "have as high an entropy as possible under the constraint that they match the training data" (section 2). Weights maximizing the log pseudo-likelihood give the grammar of greatest conditional entropy among the conditional models whose violations, averaged over the training inputs, are the training data's.

Two candidates: learning from differences (section 3.2)

def GoldwaterJohnson2003.pairConstraintSet {n : ℕ} (win lose : Fin n → ℕ) : OptimalityTheory.ConstraintSet (Fin 2) (Fin n)

Two candidates as a constraint set, the winner at 0 and the loser at 1.

Equations

• GoldwaterJohnson2003.pairConstraintSet win lose j c = if c = 0 then win j else lose j

theorem GoldwaterJohnson2003.maxEnt_pairConstraintSet_real_zero {n : ℕ} (w : Fin n → ℝ) (win lose : Fin n → ℕ) : (HarmonicGrammar.maxEnt (pairConstraintSet win lose).violations w).real {0} = (∑ j : Fin n, w j * (↑(lose j) - ↑(win j))).sigmoid

A two-candidate model sees the violations only through their difference, the winner's probability being the sigmoid of the weighted difference vector.

theorem GoldwaterJohnson2003.maxEnt_pairConstraintSet_real_zero_eq_of_diff_eq {n : ℕ} (w : Fin n → ℝ) {win lose win' lose' : Fin n → ℕ} (h : (fun (j : Fin n) => ↑(lose j) - ↑(win j)) = fun (j : Fin n) => ↑(lose' j) - ↑(win' j)) : (HarmonicGrammar.maxEnt (pairConstraintSet win lose).violations w).real {0} = (HarmonicGrammar.maxEnt (pairConstraintSet win' lose').violations w).real {0}

Two candidate pairs with the same difference vector get the same winner probability under every weighting.

Table 1: the Wolof tongue-root grammar

noncomputable def GoldwaterJohnson2003.wolofWeights : Fin 5 → ℝ

The weights learned for Boersma's five Wolof constraints *RTRHI, PARSE[RTR], GESTURE[CONTOUR], PARSE[ATR] and *ATRLO (Table 1, nσ² ≈ 1,200,000).

Equations

• GoldwaterJohnson2003.wolofWeights 0 = 3389 / 100
• GoldwaterJohnson2003.wolofWeights 1 = 17
• GoldwaterJohnson2003.wolofWeights 2 = 10
• GoldwaterJohnson2003.wolofWeights 3 = 353 / 100
• GoldwaterJohnson2003.wolofWeights 4 = 41 / 100

theorem GoldwaterJohnson2003.wolof_separated : HarmonicGrammar.ExponentiallySeparated wolofWeights 1

The learned weights are exponentially separated, each exceeding the sum of all lower ones, the spacing under which Harmonic Grammar reproduces the strict domination of the ranking the Gradual Learning Algorithm finds ([Joh02], lex_imp_lower_violations).

Tables 2 and 3: Finnish genitive plurals

def GoldwaterJohnson2003.digits (s : String) : List ℕ

The digits of a feature string as violation counts, one per constraint.

Equations

• GoldwaterJohnson2003.digits s = List.map (fun (c : Char) => c.toNat - '0'.toNat) s.toList

def GoldwaterJohnson2003.vec (l : List ℕ) : Fin 11 → ℕ

A violation vector over [BH01]'s eleven constraints.

Equations

• GoldwaterJohnson2003.vec l j = l.getD (↑j) 0

structure GoldwaterJohnson2003.Row : Type

A stem class, given by the violation vectors of the winning and the losing genitive plural.

• winner : Fin 11 → ℕ
• loser : Fin 11 → ℕ

def GoldwaterJohnson2003.instDecidableEqRow.decEq (x✝ x✝¹ : Row) : Decidable (x✝ = x✝¹)

Equations

• GoldwaterJohnson2003.instDecidableEqRow.decEq { winner := a, loser := a_1 } { winner := b, loser := b_1 } = if h : a = b then h ▸ if h : a_1 = b_1 then h ▸ isTrue ⋯ else isFalse ⋯ else isFalse ⋯

@[instance_reducible]

instance GoldwaterJohnson2003.instDecidableEqRow : DecidableEq Row

Equations

• GoldwaterJohnson2003.instDecidableEqRow = GoldwaterJohnson2003.instDecidableEqRow.decEq

def GoldwaterJohnson2003.Row.ofDatum (ex : Datum) : Option Row

Equations

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

def GoldwaterJohnson2003.Row.diff (r : Row) : Fin 11 → ℤ

Table 3's learning signal, the loser's violations minus the winner's.

Equations

• r.diff j = ↑(r.loser j) - ↑(r.winner j)

def GoldwaterJohnson2003.rows : List Row

The four stem classes of Table 2.

Equations

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

theorem GoldwaterJohnson2003.rows_collapse : ∃ r₁ ∈ rows, ∃ r₂ ∈ rows, r₁.winner ≠ r₂.winner ∧ r₁.diff = r₂.diff

Two of Table 2's classes differ in their violation vectors but not in their differences (Table 3), so a learner that sees only differences treats them as one class.

theorem GoldwaterJohnson2003.rows_collapse_prob : ∃ r₁ ∈ rows, ∃ r₂ ∈ rows, r₁ ≠ r₂ ∧ ∀ (w : Fin 11 → ℝ), (HarmonicGrammar.maxEnt (pairConstraintSet r₁.winner r₁.loser).violations w).real {0} = (HarmonicGrammar.maxEnt (pairConstraintSet r₂.winner r₂.loser).violations w).real {0}

The two classes receive the same winner probability under every weighting.