Docs / Processing / LanguageModel / Tight

Tight autoregressive sequence models

import Linglib.Processing.LanguageModel.Tight · namespace AutoregressiveSequenceModel

Survival is the probability that no end symbol appears in the first n steps. The string probabilities and the limit of survival sum to one, so a model is tight exactly when survival tends to zero, and since survival is the product of one minus the conditional end probability at each step, exactly when that probability reaches one or has a divergent sum. In a tight model the strings extending a prefix have total probability its prefix probability, the conditionals are the next-symbol laws of the string law, the model after a prefix generates the continuation, and the expected length is the total survival after the first step.

The model is also a Galton–Watson process whose types are the prefixes, each with at most one offspring, and it is tight exactly when that process dies out, which is how a probabilistic context-free grammar is tight.

Implementation notes

  • The product criterion behind isTight_iff is ENNReal.hasProd_one_sub_zero_iff, Du et al. 2023's Corollary 4.6 extended to factors that may vanish.
  • Du et al. 2023 count steps from one, so their conditional end probability at step t is eosHazard (t - 1). Where survival is zero the ratio is 0 by the convention of ℝ≥0∞ division; the characterization is unaffected, since survival first reaching zero forces a conditional end probability of one.

References

Survival

L59–61
L63–64
L87–96
L115–119
L172–175

The conditional end probability

L190–195
L205–218
L220–226
L228–240
L242–249
L251–254
L256–259

Expected length

The law of the generated string is a sum of point masses, so an integral against it is a sum weighted by the string probabilities. Survival to n is at least the probability of a string of length at least n, with equality in a tight model, so the tail-sum formula bounds the expected length by the total survival after the first step.

L320–326
L328–332
L334–339
L355–365

The model as a branching process

A model is a Galton–Watson process whose types are the prefixes: a prefix has no offspring when the string ends after it, and otherwise one, the prefix extended by the next symbol. Its family tree is a path, finite exactly when the string ends, so tightness is extinction.

The model as a Galton–Watson process on prefixes: a prefix has no offspring with the probability of ending after it, and the prefix extended by a with the probability of a.

galtonWatsonL400–403
noncomputable def AutoregressiveSequenceModel.galtonWatson {α : Type u_1} [MeasurableSpace α] (M : AutoregressiveSequenceModel α) :
ProbabilityTheory.Kernel (List α) (List (List α))
  • M.galtonWatson = { toFun := fun (c : List α) => MeasureTheory.Measure.map (fun (o : Option α) => List.map (fun (x : α) => c ++ [x]) o.toList) (M.next c), measurable' := ⋯ }

Used by lintegral_galtonWatson, instIsMarkovKernelListGaltonWatson, extinctWithin_galtonWatson, extinctionProb_galtonWatson, isTight_iff_extinctionProb

L405–410