Docs / Pragmatics / Probabilistic / AlternatingMaximization

The RSA recursion as alternating maximization

import Linglib.Pragmatics.Probabilistic.AlternatingMaximization · namespace RSA

A speaker observes the state through a kernel and addresses a listener, who hears her utterance and infers the state. The expected utility is minus the information the listener loses, the expected surprisal of the state under her interpretation, and the expected cost of the utterance, and the free energy of a speaker and a listener is the conditional entropy of the utterance given the observation plus the rationality times the expected utility. A listener who rules out a state the speaker's utterance may come from loses infinitely much, and at a positive rationality the free energy is then ⊥.

The two agents of the Rational Speech Act recursion are the two partial maximizers of the free energy. The loss of any listener exceeds that of the Bayesian listener, which is the conditional entropy of the state given the utterance, by the expected divergence of the Bayesian listener from her. The free energy of any speaker falls short of that of the speaker of RSA.speaker at the Bayesian belief by her expected divergence from it. Going up a level of the recursion therefore never lowers the free energy, which rises and converges along it, and since each speaker update raises it by at least the divergence of the old speaker from the new, that divergence tends to zero, which does not by itself make the speakers converge. Against a fixed listener, a speaker does as well as the speaker at the Bayesian belief only by being her at every observation made; when that speaker is the zero measure at such an observation, no utterance being open to her there, every speaker's free energy is ⊥ and the comparison is empty.

Implementation notes

  • The free energy is the functional the source calls the RSA tradeoff. At each observation it is the free energy of the Gibbs variational principle, entropy plus expected log-weight, for the weights the speaker normalizes.
  • The expected utility depends on the speaker and her observation kernel only through their composite, the channel from states to utterances, and is stated for a channel.
  • The speaker's belief is any family b that agrees with the posterior of the prior given her observation at almost every observation, b =ᵐ[κ ∘ₘ μ] κ†μ. The listener listener μ κ of the observation kernel is one, and so is the point mass for a speaker who observes the state itself (ProbabilityTheory.dirac_ae_eq_posterior_id).
  • The source states the two decompositions as maximality claims and proves them, by Lagrange multipliers, for a speaker who knows the state. The statements here are for a speaker who observes it through a kernel, and they give the size of the gap.

References

The speaker at one observation

L73–78
L82–114

The expected utility

The listener's step. The information a listener loses exceeds the conditional entropy of the state given the utterance by the expected divergence of the posterior from her (InformationTheory.informationLoss_eq_posterior_add), and the Bayesian listener is the posterior at every utterance heard.

L129–133
L142–150
L152–166
L172–174
L178–181
L183–187

The free energy

L199–202
L204–207
L209–216

The speaker's step

Where the free energy is not ⊥ it is the real number realFreeEnergy, and the identity for the speaker at one observation, averaged over her observations, gives the gap.

L279–291

Against a fixed listener, the free energy of a speaker falls short of that of the speaker at the Bayesian belief by her expected divergence from it over the observations made. It is ⊥ exactly when she uses, at such an observation, an utterance that speaker never uses.

theorem freeEnergy_eq_freeEnergy_speaker_subL388–427
{W : Type u_1} {O : Type u_2} {U : Type u_3} [MeasurableSpace W] [MeasurableSpace O] [MeasurableSpace U] {μ : MeasureTheory.Measure W} {κ : ProbabilityTheory.Kernel W O} {C : U → ℝ} {α : ℝ} [Fintype W] [Fintype O] [Fintype U] [MeasurableSingletonClass W] [MeasurableSingletonClass O] [MeasurableSingletonClass U] [MeasureTheory.IsFiniteMeasure μ] [ProbabilityTheory.IsFiniteKernel κ] [Nonempty W] {b : O → MeasureTheory.Measure W} (hb : b =ᵐ[μ.bind ⇑κ] ⇑(ProbabilityTheory.posterior κ μ)) [∀ (o : O), MeasureTheory.IsFiniteMeasure (b o)] (hα : 0 ≤ α) (S : ProbabilityTheory.Kernel O U) [ProbabilityTheory.IsFiniteKernel S] (L : ProbabilityTheory.Kernel U W) [∀ (u : U), MeasureTheory.IsZeroOrProbabilityMeasure (L u)] [ProbabilityTheory.IsMarkovKernel S] :
freeEnergy μ κ C α S L = freeEnergy μ κ C α (speaker α C (⇑L) b) L - ↑(∑ o : O, (μ.bind ⇑κ) {o} * InformationTheory.klDiv (S o) ((speaker α C (⇑L) b) o))

Built from

L429–434

A speaker has the free energy of the speaker at the Bayesian belief exactly when she is that speaker at every observation made.

theorem freeEnergy_eq_freeEnergy_speaker_iffL442–458
{W : Type u_1} {O : Type u_2} {U : Type u_3} [MeasurableSpace W] [MeasurableSpace O] [MeasurableSpace U] {μ : MeasureTheory.Measure W} {κ : ProbabilityTheory.Kernel W O} {C : U → ℝ} {α : ℝ} [Fintype W] [Fintype O] [Fintype U] [MeasurableSingletonClass W] [MeasurableSingletonClass O] [MeasurableSingletonClass U] [MeasureTheory.IsFiniteMeasure μ] [ProbabilityTheory.IsFiniteKernel κ] [Nonempty W] {b : O → MeasureTheory.Measure W} (hb : b =ᵐ[μ.bind ⇑κ] ⇑(ProbabilityTheory.posterior κ μ)) [∀ (o : O), MeasureTheory.IsFiniteMeasure (b o)] (hα : 0 ≤ α) (S : ProbabilityTheory.Kernel O U) [ProbabilityTheory.IsFiniteKernel S] (L : ProbabilityTheory.Kernel U W) [∀ (u : U), MeasureTheory.IsZeroOrProbabilityMeasure (L u)] [ProbabilityTheory.IsMarkovKernel S] :
freeEnergy μ κ C α S L = freeEnergy μ κ C α (speaker α C (⇑L) b) L ↔ ∀ (o : O), (μ.bind ⇑κ) {o} ≠ 0 → S o = (speaker α C (⇑L) b) o

Built from

The recursion

The speaker who answers the listener of a speaker is again a probability kernel, so the two steps alternate along the recursion.

L476–482
L485–489
L492–499

The free energy rises along the recursion.

theorem monotone_freeEnergy_iterate_recurseL505–512
{W : Type u_1} {O : Type u_2} {U : Type u_3} [MeasurableSpace W] [MeasurableSpace O] [MeasurableSpace U] {μ : MeasureTheory.Measure W} {κ : ProbabilityTheory.Kernel W O} {C : U → ℝ} {α : ℝ} [Fintype W] [Fintype O] [Fintype U] [MeasurableSingletonClass W] [MeasurableSingletonClass O] [MeasurableSingletonClass U] [MeasureTheory.IsProbabilityMeasure μ] [ProbabilityTheory.IsMarkovKernel κ] [Nonempty W] {b : O → MeasureTheory.Measure W} [∀ (o : O), MeasureTheory.IsFiniteMeasure (b o)] (hb : b =ᵐ[μ.bind ⇑κ] ⇑(ProbabilityTheory.posterior κ μ)) (hα : 0 ≤ α) (hκ : ∀ (o : O), (μ.bind ⇑κ) {o} ≠ 0) (L : ProbabilityTheory.Kernel U W) [∀ (u : U), MeasureTheory.IsZeroOrProbabilityMeasure (L u)] [ProbabilityTheory.IsMarkovKernel (speaker α C (⇑L) b)] :
Monotone fun (n : ℕ) => freeEnergy μ κ C α (speaker α C (⇑((recurse μ κ b α C)^[n] L)) b) ((recurse μ κ b α C)^[n] L)

Built from

The free energy converges along the recursion to a real number, being monotone, bounded above and nowhere ⊥.

theorem exists_tendsto_freeEnergy_iterate_recurseL546–554
{W : Type u_1} {O : Type u_2} {U : Type u_3} [MeasurableSpace W] [MeasurableSpace O] [MeasurableSpace U] {μ : MeasureTheory.Measure W} {κ : ProbabilityTheory.Kernel W O} {C : U → ℝ} {α : ℝ} [Fintype W] [Fintype O] [Fintype U] [MeasurableSingletonClass W] [MeasurableSingletonClass O] [MeasurableSingletonClass U] [MeasureTheory.IsProbabilityMeasure μ] [ProbabilityTheory.IsMarkovKernel κ] [Nonempty W] {b : O → MeasureTheory.Measure W} [∀ (o : O), MeasureTheory.IsFiniteMeasure (b o)] (hb : b =ᵐ[μ.bind ⇑κ] ⇑(ProbabilityTheory.posterior κ μ)) (hα : 0 ≤ α) (hκ : ∀ (o : O), (μ.bind ⇑κ) {o} ≠ 0) (L : ProbabilityTheory.Kernel U W) [∀ (u : U), MeasureTheory.IsZeroOrProbabilityMeasure (L u)] [ProbabilityTheory.IsMarkovKernel (speaker α C (⇑L) b)] :
∃ (g : ℝ), Filter.Tendsto (fun (n : ℕ) => freeEnergy μ κ C α (speaker α C (⇑((recurse μ κ b α C)^[n] L)) b) ((recurse μ κ b α C)^[n] L)) Filter.atTop (nhds ↑g)

Built from

L556–580

The expected divergence of each speaker of the recursion from the next tends to zero. This does not by itself give convergence of the speakers.

theorem tendsto_sum_klDiv_speaker_iterate_recurseL582–588
{W : Type u_1} {O : Type u_2} {U : Type u_3} [MeasurableSpace W] [MeasurableSpace O] [MeasurableSpace U] {μ : MeasureTheory.Measure W} {κ : ProbabilityTheory.Kernel W O} {C : U → ℝ} {α : ℝ} [Fintype W] [Fintype O] [Fintype U] [MeasurableSingletonClass W] [MeasurableSingletonClass O] [MeasurableSingletonClass U] [MeasureTheory.IsProbabilityMeasure μ] [ProbabilityTheory.IsMarkovKernel κ] [Nonempty W] {b : O → MeasureTheory.Measure W} [∀ (o : O), MeasureTheory.IsFiniteMeasure (b o)] (hb : b =ᵐ[μ.bind ⇑κ] ⇑(ProbabilityTheory.posterior κ μ)) (hα : 0 ≤ α) (hκ : ∀ (o : O), (μ.bind ⇑κ) {o} ≠ 0) (L : ProbabilityTheory.Kernel U W) [∀ (u : U), MeasureTheory.IsZeroOrProbabilityMeasure (L u)] [ProbabilityTheory.IsMarkovKernel (speaker α C (⇑L) b)] :
Filter.Tendsto (fun (n : ℕ) => ∑ o : O, (μ.bind ⇑κ) {o} * InformationTheory.klDiv ((speaker α C (⇑((recurse μ κ b α C)^[n] L)) b) o) ((speaker α C (⇑((recurse μ κ b α C)^[n + 1] L)) b) o)) Filter.atTop (nhds 0)