MaxEnt grammars #
A MaxEnt grammar makes harmonies into probabilities: a candidate whose violation vector is T c
has probability proportional to the exponential of its harmony -(w ⬝ᵥ T c). As a measure, the
MaxEnt distribution is the counting measure on the candidates tilted by harmony, the exponential
family with statistic T and parameter -w. Violations are counts for a constraint set
(OptimalityTheory.ConstraintSet.violations) and may be any reals, as when a lexicon scales them.
The name records a duality. Among the distributions of the candidates with the same expected violations as a MaxEnt distribution, the MaxEnt one has the greatest entropy, and no other has as much. The log-likelihood of an empirical distribution is concave in the weights, with gradient the expected less the observed violations, so the weights that maximize it are exactly those whose distribution has the observed expected violations, and the most likely MaxEnt grammar is the maximum-entropy one. A conditional grammar, a Markov kernel from inputs to the MaxEnt distributions of their candidates, satisfies the same duality with conditional entropy, the expected violations averaged over the observed inputs.
Main definitions #
HarmonicGrammar.maxEnt T w: the MaxEnt distribution of the candidates.HarmonicGrammar.logPartition T w: the log of its normalizing constant.HarmonicGrammar.logLikelihood T p w: the expected log-probability, under the grammar, of the candidates drawn fromp.HarmonicGrammar.condMaxEnt T w,HarmonicGrammar.condLogLikelihood T p w: the conditional grammar and its log-likelihood on input–output pairs drawn fromp.
Main results #
maxEnt_real_singleton: a candidate's probability is the softmax of the harmonies.log_maxEnt_real_singleton_div: log-odds are harmony differences.maxEnt_real_singleton_of_pair: of two candidates, one has the sigmoid of its harmony advantage.isGreatest_measureEntropy_maxEnt,eq_maxEnt_of_measureEntropy_eq: the maximum entropy principle.concaveOn_logLikelihood,hasFDerivAt_logLikelihood: the log-likelihood is concave, with gradient the expected less the observed violations.isMaxOn_logLikelihood_iff,isGreatest_measureEntropy_of_isMaxOn: maximum likelihood is matching the observed violations, and gives the maximum-entropy distribution.maxEnt_sum: additive violations over several inputs give independent outputs.isGreatest_condEntropy_condMaxEnt,isMaxOn_condLogLikelihood_iff,condLogLikelihood_eq_neg_condEntropy,isGreatest_condEntropy_of_isMaxOn: the conditional duality.tendsto_maxEnt_smul_atTop: scaling the weights concentrates the distribution on the harmony maximum.
Implementation notes #
- The candidates of one input form a finite type. A conditional grammar takes, at an input
i, the violations(con.comap (i, ·)).violationsof the candidates paired withi, andcondMaxEntassembles these into a kernel over finitely many inputs. - Goldwater and Johnson write the exponent as
∑ i, wᵢ fᵢwithout a sign; harmony negates the weighted violations here, as in Hayes and Wilson, so that positive weights penalize. - The log-likelihood takes the empirical distribution of a sample; the log-probability of
ndraws isntimes it.
References #
The log-partition function, the log of the normalizing constant of the MaxEnt distribution.
Equations
- HarmonicGrammar.logPartition T w = Real.log (∑ c : C, Real.exp (HarmonicGrammar.harmony T w c))
Instances For
The log-partition function is convex in the weights, a log-sum-exp of harmonies linear in them.
The MaxEnt distribution of candidates with violation vectors T under weights w weighs each
candidate by the exponential of its harmony.
Equations
- HarmonicGrammar.maxEnt T w = MeasureTheory.Measure.count.tilted (HarmonicGrammar.harmony T w)
Instances For
A MaxEnt distribution depends on the violations and weights only through the harmonies.
The log-likelihood of an empirical distribution p under a grammar is the expected
log-probability of the candidates drawn from p.
Equations
- HarmonicGrammar.logLikelihood T p w = ∫ (c : C), Real.log ((HarmonicGrammar.maxEnt T w).real {c}) ∂p
Instances For
The log-likelihood of a single observation is its log-probability.
On finitely many candidates the expected violation vector is a weighted sum.
Probabilities #
Every candidate has positive probability, so every distribution of the candidates is absolutely continuous with respect to the MaxEnt distribution.
Harmony is log-probability up to the log of the normalizing constant.
The log-odds of two candidates are their harmony difference, -(w ⬝ᵥ (T a - T b)), linear
in the weights.
Of exactly two candidates, one has the sigmoid of its harmony advantage over the other.
Scaling the weights scales the harmonies, so the MaxEnt distribution concentrates on a candidate of strictly greatest harmony.
Expected log-probability #
The expected log-probability of the candidates under a distribution q depends on q only
through its expected violations.
The maximum entropy principle #
The divergence of q from the MaxEnt distribution and the entropy of q add up to the
expected penalty w ⬝ᵥ ∫ c, T c ∂q plus the log of the normalizing constant.
A distribution with the expected violations of a MaxEnt distribution falls short of its entropy by its divergence from it.
The maximum entropy principle. No distribution with the expected violations of a MaxEnt distribution has more entropy.
The MaxEnt distribution is the only distribution with its expected violations and its entropy.
The MaxEnt distribution has the greatest entropy among the distributions with its expected violations.
Learning #
The gradient of the log-partition function is minus the expected violation vector.
The log-likelihood is concave in the weights: it is linear in them less the log-partition function.
The gradient of the log-likelihood is the expected less the observed violation vector.
The partial derivative of the log-likelihood in the weight of constraint j is that
constraint's expected violations less its observed ones.
Weights maximize the log-likelihood exactly when their MaxEnt distribution has the observed expected violations.
The most likely MaxEnt grammar of an empirical distribution gives the maximum-entropy distribution among those with the observed expected violations.
Joint evaluation #
When the violations of an output tuple add up its coordinates' violations, the MaxEnt distribution of the tuples is the product of the coordinates' MaxEnt distributions, so the coordinates are independent.
The marginal of such a distribution at a coordinate is that coordinate's MaxEnt distribution.
Conditional MaxEnt #
The conditional MaxEnt grammar takes each input to the MaxEnt distribution of its candidates,
whose violation vectors are T (x, ·).
Equations
- HarmonicGrammar.condMaxEnt T w = { toFun := fun (x : X) => HarmonicGrammar.maxEnt (fun (y : Y) => T (x, y)) w, measurable' := ⋯ }
Instances For
The conditional log-likelihood of an empirical distribution p of input–output pairs is the
expected log-probability of each output given its input.
Equations
- HarmonicGrammar.condLogLikelihood T p w = ∫ (z : X × Y), Real.log (((HarmonicGrammar.condMaxEnt T w) z.1).real {z.2}) ∂p
Instances For
Averaged over inputs drawn from ν, the divergence of a conditional model q from the
conditional MaxEnt grammar and the conditional entropy of q add up to the expected penalty
plus the average log-partition function.
The conditional entropy of the conditional MaxEnt grammar.
A conditional model with the expected violations of a conditional MaxEnt grammar falls short of its conditional entropy by its average divergence from it.
The conditional maximum entropy principle. No conditional model whose expected violations, averaged over the inputs, are those of a conditional MaxEnt grammar has more conditional entropy.
A conditional model with those expected violations and that conditional entropy is the conditional MaxEnt grammar at every input of positive mass.
The conditional MaxEnt grammar has the greatest conditional entropy among the conditional models with its average expected violations.
The conditional log-likelihood is concave in the weights.
The gradient of the conditional log-likelihood is the expected less the observed violation vector, the expectation taken over the observed inputs.
Weights maximize the conditional log-likelihood exactly when the expected violations of their grammar, over the observed inputs, are the observed ones.
At weights matching the observed violations the conditional log-likelihood is minus the conditional entropy of the grammar, the common value of the two dual problems.
The most likely conditional MaxEnt grammar of an empirical distribution has the greatest conditional entropy among the conditional models with the observed expected violations.