Docs / Studies / Studies.GriffithsKalish2007

Language Evolution by Iterated Learning With Bayesian Agents

Griffiths, T. L. & Kalish, M. L. (2007). Cognitive Science, 31(3), 441–480

With a production kernel $\kappa$ and a learning kernel $L$, the languages of successive learners form a Markov chain with transition $L \circ \kappa$. Learners who sample from the posterior under a prior $\mu$ keep the prior stationary. Between two languages with noisy production, learners who take a language of greatest posterior mass have one stationary distribution, the same for every bias the model allows, so they keep the prior only when it already has that value, and their chain converges to that distribution from any start.

Implementation notes

  • Stationarity is mathlib's Kernel.Invariant; the chains are compositions of kernels, so they get no definitions. The sampling results hold for any likelihood on a standard Borel space of languages, as the paper's first note says finiteness is not necessary, so they live with the posterior in Linglib/Core/Probability/Kernel/Posterior.lean. There the sampler also keeps the data at the prior predictive (ProbabilityTheory.invariant_comp_posterior) and, as a Gibbs sampler, the joint (ProbabilityTheory.invariant_id_prod_comp_prodMkLeft_posterior).
  • The sampling learner is mathlib's posterior κ†μ, which is fixed only up to a null set of data. ProbabilityTheory.invariant_comp_of_ae_eq_posterior therefore takes any learner that agrees with it on the data the prior predicts.
  • The MAP learner (eq. (41)) chooses uniformly among tied languages. On a datum no language produces, every language ties.
  • In the two-language model the parameters are real: the prior α of L₁, the production noise ε, and the agreement s, the mass of the objects on which the languages agree. The paper's conditions α > 1/2 and ε < 1 - α already give ε < 1/2. The characterization of the MAP chain's stationary distribution assumes 0 < ε, which makes q₁₂ + q₂₁ = s + 2 (1 - s) ε positive.

TODO

  • Eq. (8), convergence of an ergodic finite chain to its stationary distribution from any start, is imported by the paper from Markov chain theory. Mathlib has Kernel.IsIrreducible and Matrix.IsPrimitive but no Perron–Frobenius or Doeblin convergence theorem for finite Markov kernels; once it does, the sampler's convergence to the prior follows. Here only the two-state case is proved.
  • §6's compositionality simulations (eqs. (44)–(45)) and §7's population dynamics are not formalized.

References

The MAP learner

L69–72
L74–75
L77–80

Two languages

L86–90
L96
L98
L109–111
L113–115
L117–123

Two-state chains

A Markov kernel Q on the two languages is fixed by q₁₂ = Q two {one} and q₂₁ = Q one {two}, the paper's notation for the chance of moving to the first index from the second.

L134–139
L143–151
L154–160
L163–175

A two-state chain whose second eigenvalue 1 - q₁₂ - q₂₁ has modulus below one converges, from any start, to the stationary probability q₁₂ / (q₁₂ + q₂₁) of the first state.

theorem Language.tendsto_pow_comp_real_oneEqs. (14)–(15)L177–192
(Q : ProbabilityTheory.Kernel Language Language) [ProbabilityTheory.IsMarkovKernel Q] (ν : MeasureTheory.Measure Language) [MeasureTheory.IsProbabilityMeasure ν] (h₀ : 0 < (Q two).real {one} + (Q one).real {two}) (h₂ : (Q two).real {one} + (Q one).real {two} < 2) :
Filter.Tendsto (fun (n : ℕ) => (ν.bind ⇑(Q ^ n)).real {one}) Filter.atTop (nhds ((Q two).real {one} / ((Q two).real {one} + (Q one).real {two})))

Built from

The two-language model

The learners see one object x, drawn from P whatever the language, and whether it elicits the utterance (y). Language i elicits the utterance on the objects of G i, and a speaker answers correctly with chance 1 - ε.

L207–210
L212–214
L216–217
L219–222
L224–225
L227–230
L232–241
L247–251
L261–262
L266–269

MAP estimation with two languages

L290–303
L306–311
L363–374
L377–388

Table 1, ε < 1 - α: with noise, MAP learners between two languages have exactly one stationary distribution. It gives L₁ probability (s + (1 - s) ε) / (s + 2 (1 - s) ε), where s is the mass of the objects on which the languages agree, and does not depend on the prior α.

theorem invariant_mapLearner_comp_produce_iffL390–420
{X : Type u_1} [Fintype X] [MeasurableSpace X] [MeasurableSingletonClass X] {P : MeasureTheory.Measure X} {G : Language → Set X} [(i : Language) → DecidablePred fun (x : X) => x ∈ G i] {ε : ℝ} [MeasureTheory.IsProbabilityMeasure P] {α : ℝ} (hα : 1 / 2 < α) (hαε : ε < 1 - α) (hε : 0 < ε) (ν : MeasureTheory.Measure Language) [MeasureTheory.IsProbabilityMeasure ν] :
((mapLearner (produce P G ε) (prior α)).comp (produce P G ε)).Invariant ν ↔ ν = prior ((P.real {x : X | x ∈ G Language.one ↔ x ∈ G Language.two} + (1 - P.real {x : X | x ∈ G Language.one ↔ x ∈ G Language.two}) * ε) / (P.real {x : X | x ∈ G Language.one ↔ x ∈ G Language.two} + 2 * (1 - P.real {x : X | x ∈ G Language.one ↔ x ∈ G Language.two}) * ε))

Built from , , ,

L424–434