Chart Semirings¶

Semiring abstractions for parameterizing chart parsing (Goodman 1999). Selecting a semiring changes what the CKY skeleton computes: marginal log-probability, a Viterbi best parse, boolean recognition, or a derivation count.

semiring ¶

Semiring abstractions for parameterizing chart parsing.

A semiring (S, ⊕, ⊗, 0, 1) provides the algebraic structure for chart parsing (Goodman, 1999). Different semirings yield different parsing algorithms from the same CKY skeleton:

LogProbSemiring: marginal log-probability (logsumexp / +)
ViterbiSemiring: best-derivation log-probability (max / +)
BooleanSemiring: recognition (or / and)
CountingSemiring: derivation counting (+ / ×)

Each semiring defines:

times(a, b): multiplicative combination (⊗)
plus(scores, dim): additive aggregation (⊕) over a dimension
zero: additive identity (0): score for impossible derivations
one: multiplicative identity (1): score for trivial derivations

Categorical perspective

Semirings are the decategorification of rig categories (bimonoidal categories). The times operation corresponds to the tensor product, plus to the coproduct. Chart parsing is a functor from the free monoidal category (grammar) to the semiring.

The connection to algebras: an algebra is a complete lattice with an associative binary operation distributing over arbitrary joins. The log-probability semiring is the algebra ([-∞, 0], logsumexp, +).

ChartSemiring ¶

Bases: ABC

Abstract semiring for chart parsing.

Subclasses implement the four semiring operations. All operations must be differentiable (where applicable) to support gradient-based learning.

zero `abstractmethod` `property` ¶

zero: float

Additive identity: the score of an impossible derivation.

one `abstractmethod` `property` ¶

one: float

Multiplicative identity: the score of a trivial derivation.

times `abstractmethod` ¶

times(a: Tensor, b: Tensor) -> Tensor

Multiplicative combination (⊗).

Combines scores from two chart cells being joined by a rule.

PARAMETER	DESCRIPTION
`a`	Left operand scores. TYPE: `Tensor`
`b`	Right operand scores. TYPE: `Tensor`

RETURNS	DESCRIPTION
`Tensor`	Combined scores.

Source code in src/quivers/stochastic/semiring.py

@abstractmethod
def times(self, a: torch.Tensor, b: torch.Tensor) -> torch.Tensor:
    """Multiplicative combination (⊗).

    Combines scores from two chart cells being joined by a rule.

    Parameters
    ----------
    a : torch.Tensor
        Left operand scores.
    b : torch.Tensor
        Right operand scores.

    Returns
    -------
    torch.Tensor
        Combined scores.
    """

plus `abstractmethod` ¶

plus(scores: Tensor, dim: int) -> Tensor

Additive aggregation (⊕) over a dimension.

Marginalizes over multiple derivations of the same span.

PARAMETER	DESCRIPTION
`scores`	Scores to aggregate. TYPE: `Tensor`
`dim`	Dimension to aggregate over. TYPE: `int`

RETURNS	DESCRIPTION
`Tensor`	Aggregated scores.

Source code in src/quivers/stochastic/semiring.py

@abstractmethod
def plus(self, scores: torch.Tensor, dim: int) -> torch.Tensor:
    """Additive aggregation (⊕) over a dimension.

    Marginalizes over multiple derivations of the same span.

    Parameters
    ----------
    scores : torch.Tensor
        Scores to aggregate.
    dim : int
        Dimension to aggregate over.

    Returns
    -------
    torch.Tensor
        Aggregated scores.
    """

plus_pair `abstractmethod` ¶

plus_pair(a: Tensor, b: Tensor) -> Tensor

Binary additive combination (⊕) of two tensors.

Used for combining a cell with unary rule contributions.

PARAMETER	DESCRIPTION
`a`	First operand. TYPE: `Tensor`
`b`	Second operand. TYPE: `Tensor`

RETURNS	DESCRIPTION
`Tensor`	Combined scores.

Source code in src/quivers/stochastic/semiring.py

@abstractmethod
def plus_pair(self, a: torch.Tensor, b: torch.Tensor) -> torch.Tensor:
    """Binary additive combination (⊕) of two tensors.

    Used for combining a cell with unary rule contributions.

    Parameters
    ----------
    a : torch.Tensor
        First operand.
    b : torch.Tensor
        Second operand.

    Returns
    -------
    torch.Tensor
        Combined scores.
    """

LogProbSemiring ¶

Bases: ChartSemiring

Log-probability semiring: (logsumexp, +, -∞, 0).

This is the default semiring for marginal parsing. times is addition in log-space (= multiplication of probabilities) and plus is logsumexp (= addition of probabilities in log-space).

zero `property` ¶

zero: float

Negative infinity, the log-probability of an impossible derivation.

one `property` ¶

one: float

Zero, the log-probability of a certain derivation.

times ¶

times(a: Tensor, b: Tensor) -> Tensor

Multiply probabilities by adding log-probabilities.

PARAMETER	DESCRIPTION
`a`	Left operand scores. TYPE: `Tensor`
`b`	Right operand scores. TYPE: `Tensor`

RETURNS	DESCRIPTION
`Tensor`	The combined scores.

Source code in src/quivers/stochastic/semiring.py

def times(self, a: torch.Tensor, b: torch.Tensor) -> torch.Tensor:
    """Multiply probabilities by adding log-probabilities.

    Parameters
    ----------
    a : torch.Tensor
        Left operand scores.
    b : torch.Tensor
        Right operand scores.

    Returns
    -------
    torch.Tensor
        The combined scores.
    """
    return a + b

plus ¶

plus(scores: Tensor, dim: int) -> Tensor

Sum probabilities over dim by logsumexp.

PARAMETER	DESCRIPTION
`scores`	Scores to aggregate. TYPE: `Tensor`
`dim`	Dimension to aggregate over. TYPE: `int`

RETURNS	DESCRIPTION
`Tensor`	The aggregated scores, with `dim` removed.

Source code in src/quivers/stochastic/semiring.py

def plus(self, scores: torch.Tensor, dim: int) -> torch.Tensor:
    """Sum probabilities over ``dim`` by logsumexp.

    Parameters
    ----------
    scores : torch.Tensor
        Scores to aggregate.
    dim : int
        Dimension to aggregate over.

    Returns
    -------
    torch.Tensor
        The aggregated scores, with ``dim`` removed.
    """
    return torch.logsumexp(scores, dim=dim)

plus_pair ¶

plus_pair(a: Tensor, b: Tensor) -> Tensor

Sum two log-probabilities by logaddexp.

PARAMETER	DESCRIPTION
`a`	First operand. TYPE: `Tensor`
`b`	Second operand. TYPE: `Tensor`

RETURNS	DESCRIPTION
`Tensor`	The combined scores.

Source code in src/quivers/stochastic/semiring.py

def plus_pair(self, a: torch.Tensor, b: torch.Tensor) -> torch.Tensor:
    """Sum two log-probabilities by logaddexp.

    Parameters
    ----------
    a : torch.Tensor
        First operand.
    b : torch.Tensor
        Second operand.

    Returns
    -------
    torch.Tensor
        The combined scores.
    """
    return torch.logaddexp(a, b)

ViterbiSemiring ¶

Bases: ChartSemiring

Viterbi semiring: (max, +, -∞, 0).

Finds the single best derivation. plus takes the max over derivations rather than summing. Useful for Viterbi parsing and best-first decoding.

zero `property` ¶

zero: float

Negative infinity, the score of an impossible derivation.

one `property` ¶

one: float

Zero, the score of a trivial derivation.

times ¶

times(a: Tensor, b: Tensor) -> Tensor

Multiply probabilities by adding log-probabilities.

PARAMETER	DESCRIPTION
`a`	Left operand scores. TYPE: `Tensor`
`b`	Right operand scores. TYPE: `Tensor`

RETURNS	DESCRIPTION
`Tensor`	The combined scores.

Source code in src/quivers/stochastic/semiring.py

def times(self, a: torch.Tensor, b: torch.Tensor) -> torch.Tensor:
    """Multiply probabilities by adding log-probabilities.

    Parameters
    ----------
    a : torch.Tensor
        Left operand scores.
    b : torch.Tensor
        Right operand scores.

    Returns
    -------
    torch.Tensor
        The combined scores.
    """
    return a + b

plus ¶

plus(scores: Tensor, dim: int) -> Tensor

Take the best score over dim.

PARAMETER	DESCRIPTION
`scores`	Scores to aggregate. TYPE: `Tensor`
`dim`	Dimension to aggregate over. TYPE: `int`

RETURNS	DESCRIPTION
`Tensor`	The aggregated scores, with `dim` removed.

Source code in src/quivers/stochastic/semiring.py

def plus(self, scores: torch.Tensor, dim: int) -> torch.Tensor:
    """Take the best score over ``dim``.

    Parameters
    ----------
    scores : torch.Tensor
        Scores to aggregate.
    dim : int
        Dimension to aggregate over.

    Returns
    -------
    torch.Tensor
        The aggregated scores, with ``dim`` removed.
    """
    return scores.max(dim=dim).values

plus_pair ¶

plus_pair(a: Tensor, b: Tensor) -> Tensor

Take the elementwise best of two scores.

PARAMETER	DESCRIPTION
`a`	First operand. TYPE: `Tensor`
`b`	Second operand. TYPE: `Tensor`

RETURNS	DESCRIPTION
`Tensor`	The combined scores.

Source code in src/quivers/stochastic/semiring.py

def plus_pair(self, a: torch.Tensor, b: torch.Tensor) -> torch.Tensor:
    """Take the elementwise best of two scores.

    Parameters
    ----------
    a : torch.Tensor
        First operand.
    b : torch.Tensor
        Second operand.

    Returns
    -------
    torch.Tensor
        The combined scores.
    """
    return torch.maximum(a, b)

BooleanSemiring ¶

Bases: ChartSemiring

Boolean semiring: (or, and, 0, 1).

For recognition only: determines whether a parse exists without computing scores. Values are 0.0 (false) and 1.0 (true).

zero `property` ¶

zero: float

0.0, false.

one `property` ¶

one: float

1.0, true.

times ¶

times(a: Tensor, b: Tensor) -> Tensor

Conjoin truth values in {0, 1} by multiplication.

PARAMETER	DESCRIPTION
`a`	Left operand scores. TYPE: `Tensor`
`b`	Right operand scores. TYPE: `Tensor`

RETURNS	DESCRIPTION
`Tensor`	The combined scores.

Source code in src/quivers/stochastic/semiring.py

def times(self, a: torch.Tensor, b: torch.Tensor) -> torch.Tensor:
    """Conjoin truth values in {0, 1} by multiplication.

    Parameters
    ----------
    a : torch.Tensor
        Left operand scores.
    b : torch.Tensor
        Right operand scores.

    Returns
    -------
    torch.Tensor
        The combined scores.
    """
    # and in {0, 1}: min or product
    return a * b

plus ¶

plus(scores: Tensor, dim: int) -> Tensor

Disjoin truth values in {0, 1} over dim by max.

PARAMETER	DESCRIPTION
`scores`	Scores to aggregate. TYPE: `Tensor`
`dim`	Dimension to aggregate over. TYPE: `int`

RETURNS	DESCRIPTION
`Tensor`	The aggregated scores, with `dim` removed.

Source code in src/quivers/stochastic/semiring.py

def plus(self, scores: torch.Tensor, dim: int) -> torch.Tensor:
    """Disjoin truth values in {0, 1} over ``dim`` by max.

    Parameters
    ----------
    scores : torch.Tensor
        Scores to aggregate.
    dim : int
        Dimension to aggregate over.

    Returns
    -------
    torch.Tensor
        The aggregated scores, with ``dim`` removed.
    """
    # or in {0, 1}: clamp of sum or max
    return scores.max(dim=dim).values

plus_pair ¶

plus_pair(a: Tensor, b: Tensor) -> Tensor

Disjoin two truth values by elementwise max.

PARAMETER	DESCRIPTION
`a`	First operand. TYPE: `Tensor`
`b`	Second operand. TYPE: `Tensor`

RETURNS	DESCRIPTION
`Tensor`	The combined scores.

Source code in src/quivers/stochastic/semiring.py

def plus_pair(self, a: torch.Tensor, b: torch.Tensor) -> torch.Tensor:
    """Disjoin two truth values by elementwise max.

    Parameters
    ----------
    a : torch.Tensor
        First operand.
    b : torch.Tensor
        Second operand.

    Returns
    -------
    torch.Tensor
        The combined scores.
    """
    return torch.maximum(a, b)

CountingSemiring ¶

Bases: ChartSemiring

Counting semiring: (+, ×, 0, 1).

Counts the number of derivations. plus sums counts and times multiplies them (product rule for independent choices).

Note: Not differentiable in a useful sense for gradient-based learning, but useful for analysis.

zero `property` ¶

zero: float

0.0, the count of an impossible derivation.

one `property` ¶

one: float

1.0, the count of a trivial derivation.

times ¶

times(a: Tensor, b: Tensor) -> Tensor

Multiply derivation counts.

PARAMETER	DESCRIPTION
`a`	Left operand scores. TYPE: `Tensor`
`b`	Right operand scores. TYPE: `Tensor`

RETURNS	DESCRIPTION
`Tensor`	The combined scores.

Source code in src/quivers/stochastic/semiring.py

def times(self, a: torch.Tensor, b: torch.Tensor) -> torch.Tensor:
    """Multiply derivation counts.

    Parameters
    ----------
    a : torch.Tensor
        Left operand scores.
    b : torch.Tensor
        Right operand scores.

    Returns
    -------
    torch.Tensor
        The combined scores.
    """
    return a * b

plus ¶

plus(scores: Tensor, dim: int) -> Tensor

Sum derivation counts over dim.

PARAMETER	DESCRIPTION
`scores`	Scores to aggregate. TYPE: `Tensor`
`dim`	Dimension to aggregate over. TYPE: `int`

RETURNS	DESCRIPTION
`Tensor`	The aggregated scores, with `dim` removed.

Source code in src/quivers/stochastic/semiring.py

def plus(self, scores: torch.Tensor, dim: int) -> torch.Tensor:
    """Sum derivation counts over ``dim``.

    Parameters
    ----------
    scores : torch.Tensor
        Scores to aggregate.
    dim : int
        Dimension to aggregate over.

    Returns
    -------
    torch.Tensor
        The aggregated scores, with ``dim`` removed.
    """
    return scores.sum(dim=dim)

plus_pair ¶

plus_pair(a: Tensor, b: Tensor) -> Tensor

Add two derivation counts.

PARAMETER	DESCRIPTION
`a`	First operand. TYPE: `Tensor`
`b`	Second operand. TYPE: `Tensor`

RETURNS	DESCRIPTION
`Tensor`	The combined scores.

Source code in src/quivers/stochastic/semiring.py

def plus_pair(self, a: torch.Tensor, b: torch.Tensor) -> torch.Tensor:
    """Add two derivation counts.

    Parameters
    ----------
    a : torch.Tensor
        First operand.
    b : torch.Tensor
        Second operand.

    Returns
    -------
    torch.Tensor
        The combined scores.
    """
    return a + b

Semiring singletons¶

Stochastic morphisms: Markov kernels over finite sets.

This module provides the probabilistic layer for quivers, implementing the category FinStoch of finite sets and stochastic maps (Markov kernels). This is the Kleisli category of the Giry monad restricted to finite sets, where:

Objects are finite sets (same as the base category).
Morphisms A -> B are stochastic matrices: tensors of shape (|A|, |B|) whose rows sum to 1.
Composition is standard matrix multiplication.
Identity is the Kronecker delta.

The package also re-exports MarkovAlgebra and its singleton MARKOV from quivers.core.algebras, the algebra these morphisms compose under.

Submodules

morphisms : StochasticMorphism, CategoricalMorphism families : Discretized distribution families transforms : condition, mix, factor, normalize queries : prob, marginal_prob, expectation giry : GiryMonad, FinStoch categories : Category types including atoms, slashes, products, unit, modals semiring : Chart semiring abstractions (LogProb, Viterbi, Boolean, Counting) schema : Composable rule schemas (functors CategorySystem -> RuleSystem) rules : Rule systems and the CCG / Lambek presets span : Span-based CKY components (LexicalAxiom, BinarySpanDeduction, etc.) parsers, ccg, lambek : Chart parsers inside : The inside algorithm over a rule system agenda : The agenda-driven weighted-deduction engine effect_lifts : Effect-lifted rule schemas for deduction systems deduction : Abstract weighted deductive system framework and its operations stdlib : Pre-registered deduction systems

LOG_PROB `module-attribute` ¶

LOG_PROB = LogProbSemiring()

The log-probability semiring singleton, the default for chart parsing.

VITERBI `module-attribute` ¶

VITERBI = ViterbiSemiring()

The Viterbi (max-product in log space) semiring singleton.

BOOLEAN `module-attribute` ¶

BOOLEAN = BooleanSemiring()

The Boolean (or-and) semiring singleton, for recognition.

COUNTING `module-attribute` ¶

COUNTING = CountingSemiring()

The counting (sum-product over naturals) semiring singleton.

Chart Semirings¶

semiring ¶

ChartSemiring ¶

zero abstractmethod property ¶

one abstractmethod property ¶

times abstractmethod ¶

plus abstractmethod ¶

plus_pair abstractmethod ¶

LogProbSemiring ¶

zero property ¶

one property ¶

times ¶

plus ¶

plus_pair ¶

ViterbiSemiring ¶

zero property ¶

one property ¶

times ¶

plus ¶

plus_pair ¶

BooleanSemiring ¶

zero property ¶

one property ¶

times ¶

plus ¶

plus_pair ¶

CountingSemiring ¶

zero property ¶

one property ¶

times ¶

plus ¶

plus_pair ¶

Semiring singletons¶

LOG_PROB module-attribute ¶

VITERBI module-attribute ¶

BOOLEAN module-attribute ¶

COUNTING module-attribute ¶

zero `abstractmethod` `property` ¶

one `abstractmethod` `property` ¶

times `abstractmethod` ¶

plus `abstractmethod` ¶

plus_pair `abstractmethod` ¶

zero `property` ¶

one `property` ¶

zero `property` ¶

one `property` ¶

zero `property` ¶

one `property` ¶

zero `property` ¶

one `property` ¶

LOG_PROB `module-attribute` ¶

VITERBI `module-attribute` ¶

BOOLEAN `module-attribute` ¶

COUNTING `module-attribute` ¶