Documentation

Provenance.Semirings.Viterbi

Viterbi m-semiring #

This file defines the Viterbi semiring over non-negative reals in [0,1]. Addition is max, multiplication is the usual product, zero is 0, and one is 1.

The Viterbi semiring is absorptive and idempotent, and satisfies left-distributivity of multiplication over monus.

This semiring is discussed in Green & Tannen, The Semiring Framework for Database Provenance.

References #

Viterbi semiring (max-times) over probabilities in [0,1].

Equations
Instances For
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    theorem Viterbi.ext {a b : Viterbi} (h : ↑a = ↑b) :
    a = b
    Dependency graph
    theorem Viterbi.ext_iff {a b : Viterbi} :
    a = b ↔ ↑a = ↑b
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    @[instance_reducible]
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]
    noncomputable instance Viterbi.instSub :
    Equations
    Dependency graph
    Dependency graph
    Dependency graph
    Dependency graph
    Dependency graph
    Dependency graph

    Viterbi has characteristic 0 in the CharP sense: it is idempotent and nontrivial.

    Dependency graph
    noncomputable def Viterbi.deltaInd (a : Viterbi) :

    ProvSQL's Viterbi::delta: the support indicator.

    Equations
    Instances For
      Dependency graph
      Dependency graph
      @[instance_reducible]

      Viterbi is a commutative m-semiring. The natural order is the usual order on [0,1], and the monus is a if a > b, 0 if a ≤ b.

      Equations
      • One or more equations did not get rendered due to their size.
      Dependency graph
      Dependency graph
      theorem Viterbi.no_hom_from_BoolFunc {Y : Type} [Inhabited Y] :
      ∃ (ν : Y → Viterbi), ¬∃ (φ : BoolFunc Y →+* Viterbi), ∀ (i : Y), φ (BoolFunc.var i) = ν i

      There is no semiring homomorphism from BoolFunc Y to Viterbi sending the variables to arbitrary values: Viterbi multiplication (ordinary product on [0,1]) is not idempotent, contradicting var i * var i = var i in BoolFunc Y.

      Dependency graph

      The Viterbi semiring is not exclusive. It is absorptive and totally ordered, so not_exclusive_of_absorptive_of_total applies to any probability strictly between 0 and 1; concretely ½ ⊗ (𝟙 ⊖ ½) = ½ ⊗ 𝟙 = ½, since 𝟙 ⊖ ½ = 𝟙 on a chain. As Viterbi is also left-distributive (Viterbi.mul_sub_left_distributive), exclusivity follows from neither absorptivity nor distributivity.

      Dependency graph
      Dependency graph