Xu, Kemp, Frermann & Xu (2024): Word Reuse and Combination Support Efficient Communication

This file formalizes the efficient-communication account of lexicalization in [XKFX24]. A novel concept enters the lexicon by reusing an existing form or by combining existing forms into a compound, and both strategies are shaped by a tradeoff between speaker effort, the expected length of the form, and information loss, the expected surprisal of the intended concept under the listener's distribution (costs). The speaker produces from the expanded lexicon while the listener, who has not yet acquired the new pairs, interprets each form as the label of a category with a prototype, assigning concepts probability by a similarity choice rule (listener), the softmax of the negative distances to the prototype (real_listener), so that under a form a concept closer to the prototype is less surprising and incurs less information loss (surprisal_listener_le). The combined objective weights the two costs by a tradeoff parameter and, with need held fixed, decomposes into an item-level objective, so an encoding that is optimal concept by concept is optimal overall (weightedCost_costs, weightedCost_le_of_forall). Along the frontier the optimal encodings trade length for informativeness as the parameter grows (Pragmatics.Efficiency.frontier_antitone), and a compound is longer than the constituent it reuses (length_compound), the length half of the tradeoff the paper reports between the two strategies. An item is literal when the intended concept is a hyponym of an existing sense of the reused form or of the compound's head (Literal).

Implementation notes

The speaker's distribution is a point mass on the intended concept, so the expected Kullback–Leibler divergence of the paper is the expected surprisal. Need probabilities and the production policy enter through one weight per concept over a deterministic encoding, the case under which the paper computes its frontier. The corpus results, the fitted sensitivity parameter, the sentence-encoder prototypes, and the baseline encodings are not restated; the attested items of the paper's first table and the near-synonyms of its second are recorded as examples. Surprisal is measured in nats; bits differ by the factor log 2, which rescales the tradeoff parameter.

References

• [XKFX24]
• [KR12a]
• [ZKRT18]
• [RKK15]

The listener

noncomputable def XuEtAl2024.listener {C : Type u_1} {W : Type u_2} {Q : Type u_3} [Fintype C] [MeasurableSpace C] [Countable W] [MeasurableSpace W] [MeasurableSingletonClass W] (γ : ℝ) (d : C → Q → ℝ) (q : W → Q) : ProbabilityTheory.Kernel W C

The similarity choice listener: on hearing a form, a distribution over concepts whose weight falls off exponentially, at rate γ, with the concept's distance from the form's prototype.

Equations

• XuEtAl2024.listener γ d q = ProbabilityTheory.Kernel.ofWeights fun (w : W) (c : C) => ENNReal.ofReal (Real.exp (-γ * d c (q w)))

instance XuEtAl2024.instIsMarkovKernelListenerOfNonempty {C : Type u_1} {W : Type u_2} {Q : Type u_3} [Fintype C] [MeasurableSpace C] [Countable W] [MeasurableSpace W] [MeasurableSingletonClass W] (γ : ℝ) (d : C → Q → ℝ) (q : W → Q) [Nonempty C] : ProbabilityTheory.IsMarkovKernel (listener γ d q)

theorem XuEtAl2024.real_listener {C : Type u_1} {W : Type u_2} {Q : Type u_3} [Fintype C] [MeasurableSpace C] [MeasurableSingletonClass C] [Countable W] [MeasurableSpace W] [MeasurableSingletonClass W] (γ : ℝ) (d : C → Q → ℝ) (q : W → Q) (w : W) (c : C) : ((listener γ d q) w).real {c} = Real.softmax (fun (c : C) => -γ * d c (q w)) c

The listener's probability of a concept is the softmax of the negative scaled distances.

theorem XuEtAl2024.surprisal_listener_le {C : Type u_1} {W : Type u_2} {Q : Type u_3} [Fintype C] [MeasurableSpace C] [MeasurableSingletonClass C] [Countable W] [MeasurableSpace W] [MeasurableSingletonClass W] (γ : ℝ) (d : C → Q → ℝ) (q : W → Q) [Nonempty C] (hγ : 0 ≤ γ) {w : W} {c c' : C} (h : d c (q w) ≤ d c' (q w)) : InformationTheory.surprisal ((listener γ d q) w) c ≤ InformationTheory.surprisal ((listener γ d q) w) c'

Under a form, a concept closer to the prototype is less surprising to the listener, so it incurs less information loss.

theorem XuEtAl2024.real_listener_zero {C : Type u_1} {W : Type u_2} {Q : Type u_3} [Fintype C] [MeasurableSpace C] [MeasurableSingletonClass C] [Countable W] [MeasurableSpace W] [MeasurableSingletonClass W] (d : C → Q → ℝ) (q : W → Q) (w : W) (c : C) : ((listener 0 d q) w).real {c} = 1 / ↑(Fintype.card C)

With no sensitivity the listener is uniform.

Communicative costs

noncomputable def XuEtAl2024.costs {C : Type u_1} {W : Type u_2} [Fintype C] [MeasurableSpace C] [MeasurableSpace W] (p : C → ℝ) (l : W → ℝ) (m : ProbabilityTheory.Kernel W C) (f : C → W) : Pragmatics.Efficiency.CostPair

The costs of an encoding f of the emerging concepts under need p, form length l, and listener m: expected length and expected surprisal of the intended concept.

Equations

• XuEtAl2024.costs p l m f = { cost₁ := ∑ c : C, p c * l (f c), cost₂ := ∑ c : C, p c * InformationTheory.surprisal (m (f c)) c }

noncomputable def XuEtAl2024.itemObjective {C : Type u_1} {W : Type u_2} [MeasurableSpace C] [MeasurableSpace W] (l : W → ℝ) (m : ProbabilityTheory.Kernel W C) (β : ℝ) (c : C) (w : W) : ℝ

The item-level objective: the surprisal of the concept under the form, plus the weighted length of the form.

Equations

• XuEtAl2024.itemObjective l m β c w = InformationTheory.surprisal (m w) c + β * l w

theorem XuEtAl2024.weightedCost_costs {C : Type u_1} {W : Type u_2} [Fintype C] [MeasurableSpace C] [MeasurableSpace W] (p : C → ℝ) (l : W → ℝ) (m : ProbabilityTheory.Kernel W C) (f : C → W) (β : ℝ) : Pragmatics.Efficiency.weightedCost (costs p l m f) β = ∑ c : C, p c * itemObjective l m β c (f c)

The combined objective is the need-weighted sum of the item-level objectives.

theorem XuEtAl2024.weightedCost_le_of_forall {C : Type u_1} {W : Type u_2} [Fintype C] [MeasurableSpace C] [MeasurableSpace W] {p : C → ℝ} (hp : ∀ (c : C), 0 ≤ p c) (l : W → ℝ) (m : ProbabilityTheory.Kernel W C) {f g : C → W} (β : ℝ) (h : ∀ (c : C), itemObjective l m β c (f c) ≤ itemObjective l m β c (g c)) : Pragmatics.Efficiency.weightedCost (costs p l m f) β ≤ Pragmatics.Efficiency.weightedCost (costs p l m g) β

An encoding that is optimal for every concept is optimal overall.

Reuse and combination

def XuEtAl2024.compound {A : Type u_1} (w₁ w₂ : List A) : List A

A compound concatenates two existing forms.

Equations

• XuEtAl2024.compound w₁ w₂ = w₁ ++ w₂

theorem XuEtAl2024.length_compound {A : Type u_1} (w₁ : List A) {w₂ : List A} (h : w₂ ≠ []) : w₁.length < (compound w₁ w₂).length

A compound is longer than a constituent it could have reused.

def XuEtAl2024.compoundPrototype {A : Type u_1} {Q : Type u_3} [Add Q] (q : List A → Q) (w₁ w₂ : List A) : Q

The prototype of a compound is the sum of its constituents' prototypes.

Equations

• XuEtAl2024.compoundPrototype q w₁ w₂ = q w₁ + q w₂

def XuEtAl2024.Literal {A : Type u_1} {C : Type u_2} (Hypo : C → C → Prop) (senses : List A → Set C) (carrier : List A) (c : C) : Prop

An item is literal when its concept is a hyponym of an existing sense of the form that carries it: the reused form, or the head of a compound.

Equations

• XuEtAl2024.Literal Hypo senses carrier c = ∃ c' ∈ senses carrier, Hypo c c'