[GJ03]: Learning OT Constraint Rankings Using a Maximum Entropy Model

[GJ03]

[GJ03] introduce Maximum Entropy models to constraint-based phonology. Their eq (1) defines the conditional probability of output y given input x as:

Pr(y|x) = exp(Σ wᵢfᵢ(y,x)) / Z(x)

This IS softmax(harmonyScore constraints, 1) — the same softmax from Core.Agent.RationalAction used throughout linglib for RSA pragmatics. The phonology–pragmatics connection is structural: both are log-linear models over weighted features, differing only in what the features measure.

Key contributions formalized here

1. MaxEnt = softmax (§1): gjProb is eq (1) by definition — the conditional probability is softmax (harmonyScore con w (i, ·)), a constraint set con : CON (I × O) n weighted by w : Fin n → ℝ and softmax-decoded.

2. Log-likelihood (§2): The learning objective is log pseudo-likelihood, which decomposes as Σⱼ (H(yⱼ,xⱼ) − logSumExp(H(·,xⱼ))) — the harmony of each observed output minus the log-partition function.

3. Concavity (§2): Log-likelihood is concave in each weight (concavity via logConditional_concaveOn). The decomposition log P(y|x;w) = affine(wⱼ) − logSumExpOffset(s,r,wⱼ) makes this affine minus convex = concave, guaranteeing a unique global maximum.

4. Learning gradient = E[feature] (§3): The derivative of log-likelihood w.r.t. each weight equals observed minus expected feature value (gradient via hasDerivAt_logConditional). At the optimum, observed feature counts equal expected feature counts.

5. Wolof data (§4): The learned weights for a categorical grammar are exponentially separated (ExponentiallySeparated wolofWeights 1), confirming that MaxEnt reproduces OT for categorical data — the empirical counterpart of maxent_ot_limit.

noncomputable def GoldwaterJohnson2003.gjProb {I O : Type} [Fintype O] {n : ℕ} (con : Constraints.CON (I × O) n) (w : Fin n → ℝ) (i : I) (o : O) : ℝ

[GJ03] eq (1): the conditional probability of output o given input i is the softmax of the harmony score over a constraint set con weighted by w — Pr(o ∣ i) ∝ exp(-harmonyScore con w (i, o)). Mirrors the per-mapping probability of a classical MaxEnt grammar (a constraint set + weight vector, no record).

Equations

• GoldwaterJohnson2003.gjProb con w i o = Core.softmax (fun (o' : O) => Constraints.harmonyScore con w (i, o')) o

theorem GoldwaterJohnson2003.eq1_is_softmax {I O : Type} [Fintype O] {n : ℕ} (con : Constraints.CON (I × O) n) (w : Fin n → ℝ) (i : I) (o : O) : gjProb con w i o = Core.softmax (fun (o' : O) => Constraints.harmonyScore con w (i, o')) o

[GJ03] eq (1) is gjProb by definition — both are softmax(harmonyScore con w, 1).

The same softmax function powers RSA pragmatic reasoning (Core.Agent.RationalAction): both phonological grammar and pragmatic inference are log-linear models over weighted features.

noncomputable def GoldwaterJohnson2003.logPseudoLikelihood {I O : Type} [Fintype O] {n : ℕ} (con : Constraints.CON (I × O) n) (w : Fin n → ℝ) (data : List (I × O)) : ℝ

Log pseudo-likelihood of training data under a MaxEnt grammar (eq (2)).

logPL(w) = Σⱼ log P_w(yⱼ | xⱼ)

Each term decomposes as H(yⱼ, xⱼ) − logSumExp(H(·, xⱼ), 1) via softmax_exponential_family.

Equations

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

noncomputable def GoldwaterJohnson2003.regularizedObjective {I O : Type} [Fintype O] {n : ℕ} (con : Constraints.CON (I × O) n) (w : Fin n → ℝ) (data : List (I × O)) (σ : ℝ) : ℝ

Regularized objective (eq (3)): log-likelihood minus L2 penalty.

J(w) = logPL(w) − Σᵢ (wᵢ − μᵢ)² / (2σᵢ²)

[GJ03] use μᵢ = 0, σᵢ = σ for all constraints, so the penalty is Σⱼ wⱼ² / (2σ²) over the grammar's weight vector.

Equations

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

theorem GoldwaterJohnson2003.concavity {ι : Type u_1} [Fintype ι] [Nonempty ι] (s r : ι → ℝ) (y : ι) : ConcaveOn ℝ Set.univ fun (wⱼ : ℝ) => wⱼ * s y + r y - Core.logSumExp (wⱼ • s + r)

Concavity of log-likelihood (fn. 4): the log conditional likelihood of a single observation is concave in each weight, guaranteeing a unique global maximum.

When all weights except wⱼ are held fixed, log P(y|x;w) decomposes as (wⱼ · sᵧ + rᵧ) − logSumExpOffset(s, r, wⱼ) where sᵢ = −cⱼ(yᵢ,x) and rᵢ = Σₖ≠ⱼ wₖ(−cₖ(yᵢ,x)). The first term is affine (hence concave); the second is convex (logSumExpOffset_convex). Concave − convex = concave.

This is logConditional_concaveOn from Core.Agent.RationalAction.

theorem GoldwaterJohnson2003.gradient {ι : Type u_1} [Fintype ι] [Nonempty ι] (s r : ι → ℝ) (y : ι) (wⱼ : ℝ) : HasDerivAt (fun (w : ℝ) => w * s y + r y - Core.logSumExp (w • s + r)) (s y - ∑ i : ι, Core.softmax (wⱼ • s + r) i * s i) wⱼ

Learning gradient = observed − expected (§2, §4.2):

∂/∂wⱼ log P(y|x) = sᵧ − Σᵢ softmaxOffset(s,r,wⱼ)ᵢ · sᵢ

where sᵢ = −cⱼ(yᵢ,x) (negated violation count of constraint j on candidate i) and rᵢ = Σₖ≠ⱼ wₖ(−cₖ(yᵢ,x)) (contribution of other constraints, constant w.r.t. wⱼ).

At the maximum, this derivative is zero, so sᵧ = E_P[s]: the observed feature value equals the expected feature value.

This is hasDerivAt_logConditional from Core.Agent.RationalAction.

noncomputable def GoldwaterJohnson2003.wolofWeights : Fin 5 → ℝ

Wolof tongue-root harmony constraints (§3.1, from Boersma 1999).

The five constraints in ranked order, with learned MaxEnt weights from 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_pos (i : Fin 5) : 0 < wolofWeights i

All Wolof weights are positive.

theorem GoldwaterJohnson2003.wolof_separated : HarmonicGrammar.ExponentiallySeparated wolofWeights 1

The learned Wolof weights are exponentially separated (M = 1): each weight exceeds the sum of all lower-ranked weights.

This is the empirical counterpart of maxent_ot_limit: for a categorical grammar (no free variation), MaxEnt learning produces weights that satisfy ExponentiallySeparated, recovering OT's strict ranking. The theoretical direction is:

ExponentiallySeparated ⟹ lex_imp_lower_violations ⟹ HG = OT

Here we verify the converse empirically: OT-like data ⟹ learning produces ExponentiallySeparated weights.