Zaslavsky, Kemp, Regier and Tishby (2018): Efficient Compression in Color Naming #
This file formalizes the communication model of [ZKRT18], in which
a color naming system is an encoder that compresses meanings, distributions over the colors of
the environment, into words, and languages are hypothesized to trade off the complexity of the
lexicon against the accuracy of communication as the Information Bottleneck principle of
[TPB99] prescribes. The meanings are a Markov kernel from M to the
environment U, the cognitive source a probability measure on M, and the encoder a Markov
kernel from M to the words W. The listener is the Bayesian decoder, interpreting a word as
the posterior mixture of meanings (decoder), and no other decoder has lower expected
distortion (distortion_le). Complexity is the information the words carry about the meanings
(complexity), accuracy the information they carry about the environment (accuracy), and the
expected Kullback–Leibler distortion between the speaker's meaning and the listener's
interpretation is the information about the environment that the lexicon loses
(distortion_eq), so that minimizing distortion is maximizing accuracy. Accuracy is bounded by
complexity and by the information the meanings carry (accuracy_le_complexity,
accuracy_le_sourceInfo), and a lexicon that ignores the meaning has complexity 0
(complexity_const).
The Information Bottleneck objective F_β = I(M;W) − β I(W;U) (objective) is, up to a
constant, the β-scalarized cost of Pragmatics.Efficiency on the pair of distortion and
complexity (objective_eq_weightedCost), and a language's deviation from optimality at β is
the substrate's efficiencyLossAt (deviation_eq_efficiencyLossAt). Below β = 1 the
meaning-blind lexicon is optimal (objective_const_le). Every minimizer of F_β has the
self-consistent Boltzmann form in which a word's probability decays exponentially in its
divergence from the meaning (ibUpdate, IsIBOptimum, isIBOptimum_of_forall_objective_le), so
that at finite β the optimal categories are soft (IsIBOptimum.real_pos).
The cognitive source is the least informative source of the SI (§2). A least informative prior
of a naming distribution maximizes the entropy of the meaning less its conditional entropy given
the word (IsLeastInformative, eq. S10); that objective is the complexity of the lexicon
(measureEntropy_sub_condEntropy, eq. S11), so the least informative priors are the
capacity-achieving priors (isLeastInformative_iff) and, with positive mass everywhere, the
fixed points of the Blahut–Arimoto update of [Bla72] and [Ari72]
(IsLeastInformative.eq_blahutArimoto). The complexity is also the word average of the
divergence of the posterior from the prior (complexity_eq_sum_klDiv_posterior, eq. S12), and the
universal source averages the least informative priors of the languages (averagePrior,
eq. S13).
Implementation notes #
- The information quantities are the mutual informations
Im[·]ofInformationTheory, and the distortion the divergencesklDivof mathlib; the paper's forms with the word marginal in the denominator are the averaged divergences ofInformationTheory.measureMutualInfo_compProd(complexity_eq). On finite alphabets no positivity assumption is needed: a meaning and a word that co-occur make the meaning absolutely continuous with respect to the word's interpretation. distortion_eqanddistortion_leare the compensation identityInformationTheory.sum_mul_toReal_klDivfor the meanings channel, applied at each word's posterior over meanings.- Eq. 7 is a fixed-point equation: the Boltzmann encoder
ibUpdatetilts the word marginal row by row (Measure.tilted), andisIBOptimum_of_forall_objective_leis the Gibbs variational principle ofCore.Probability.GibbsVariationalapplied to each row.F_β + β I(M;U)is the source average of the negative free energies of the encoder's rows against its own word marginal and Bayesian decoder, and at most that average against any other; each row's free energy is at most its log partition function, with equality only at the tilt (eq_tilted_of_freeEnergy_eq_cgf). The theorem assumes a source and meanings of full support, as the paper's Gaussian meanings are. - The efficiency loss
ε_ldivides the minimal deviation by the fittedβ_l; the fit itself is a numerical optimization outside the formalization. The empirical encoders of the World Color Survey are not in the library.
References #
- N. Zaslavsky, C. Kemp, T. Regier and N. Tishby, Efficient compression in color naming and its evolution (2018)
- N. Tishby, F. C. Pereira and W. Bialek, The information bottleneck method (1999)
- C. E. Shannon, A Mathematical Theory of Communication (1948)
- R. E. Blahut, Computation of channel capacity and rate-distortion functions (1972)
- S. Arimoto, An algorithm for computing the capacity of arbitrary discrete memoryless channels (1972)
The Bayesian listener #
The listener's interpretation of a word (eq. 1), the posterior mixture of meanings
m̂_w(u) = ∑ m, q(m | w) m(u).
Equations
- ZaslavskyKempRegierTishby2018.decoder meanings source encoder = meanings.comp (ProbabilityTheory.posterior encoder source)
Instances For
The interpretations, weighted by the word marginal, recover the environment marginal.
Complexity, accuracy and distortion #
The complexity of the lexicon, I_q(M;W).
Equations
- ZaslavskyKempRegierTishby2018.complexity source encoder = InformationTheory.measureMutualInfo (source.compProd encoder)
Instances For
The accuracy of the lexicon, I_q(W;U), between a word and the listener's interpretation.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The information the meanings carry about the environment, I(M;U), independent of the
encoder.
Equations
- ZaslavskyKempRegierTishby2018.sourceInfo meanings source = InformationTheory.measureMutualInfo (source.compProd meanings)
Instances For
The expected distortion E_q[D[m ‖ m̂_w]] between the speaker's meaning and the listener's
interpretation (eq. 4).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Complexity in the paper's form (eq. 2): the source average of the divergence of each meaning's naming distribution from the word marginal.
A lexicon that ignores the meaning, such as a single word for every meaning, has the minimal
complexity 0.
Eq. 5: the expected distortion is the information about the environment that the lexicon
loses, E_q[D[M ‖ M̂]] = I(M;U) − I_q(W;U).
The Bayesian listener of eq. 1 is optimal: no decoder whose interpretations allow every state that a meaning allows has lower expected distortion.
The information plane #
Accuracy is bounded by the information the meanings carry about the environment.
Accuracy is bounded by complexity: the words carry no more information about the environment than about the meanings they compress.
The Information Bottleneck objective #
The Information Bottleneck objective (eq. 6), F_β = I_q(M;W) − β I_q(W;U).
Equations
- ZaslavskyKempRegierTishby2018.objective meanings source encoder β = ZaslavskyKempRegierTishby2018.complexity source encoder - β * ZaslavskyKempRegierTishby2018.accuracy meanings source encoder
Instances For
The distortion–complexity cost pair of the lexicon.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Up to the encoder-independent constant β I(M;U), the objective is the β-scalarized cost
of distortion and complexity.
For β ≤ 1 the objective is minimized by a lexicon that ignores the meaning, at 0: the
IB optima are informative only above β = 1, and eq. 6 takes β ≥ 1.
The right side of eq. 7: the encoder whose row at a meaning tilts the word marginal by −β
times the divergence of the meaning from each word's interpretation.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The self-consistent form of the Information Bottleneck optima (eq. 7): the encoder is its own update.
Equations
- ZaslavskyKempRegierTishby2018.IsIBOptimum meanings source encoder β = (encoder = ZaslavskyKempRegierTishby2018.ibUpdate meanings source encoder β)
Instances For
Eq. 7 pointwise: each word's probability decays exponentially, at rate β, in the
divergence between the meaning and the word's interpretation.
At finite β the IB optima induce soft categories: a word in use has positive probability
under every meaning.
Eq. 7: for a source and meanings of full support, every minimizer of the objective at
β ≥ 0 has the self-consistent Boltzmann form.
The deviation ΔF_β of the lexicon from a reference encoder at β.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The deviation of the lexicon from a reference encoder over the same meanings and source is
the substrate's efficiency loss at β.
The efficiency loss ε_l = ΔF_{β_l} / β_l at the fitted trade-off.
Equations
- ZaslavskyKempRegierTishby2018.efficiencyLoss meanings source encoder encoder' β = ZaslavskyKempRegierTishby2018.deviation meanings source encoder encoder' β / β
Instances For
Against an optimal encoder at a positive β, the efficiency loss is nonnegative.
The least informative source #
A least informative prior for a naming distribution (SI eq. S10): a prior over the meanings maximizing the entropy of the meaning less its conditional entropy given the word.
Equations
- One or more equations did not get rendered due to their size.
Instances For
SI eq. S11: the objective of a least informative prior is the complexity of the lexicon under that prior, the information the words carry about the meanings.
SI eq. S11: the least informative priors are the capacity-achieving priors of the naming distribution, under which the lexicon is maximally complex.
SI eq. S12: the complexity is the word average of the divergence of the posterior over meanings from the prior, so a least informative prior keeps the posteriors as far from it as the lexicon allows.
A least informative prior "can be evaluated using the Blahut–Arimoto algorithm" (SI §2.1): one of positive mass everywhere is a fixed point of the Blahut–Arimoto update.
SI eq. S13: the universal least informative source averages the least informative priors of
L languages.
Equations
- ZaslavskyKempRegierTishby2018.averagePrior priors = (↑L)⁻¹ • ∑ l : Fin L, priors l