API REFERENCE/omnibias-struct

omnibias.struct.torch.semiring

0.1.0a2AlphaPython >=3.10AGPL / commercial

Differentiable dynamic programs for sequences and parses, structured distributions, and finite-temperature bounds.

import omnibias.struct.torch.semiring

Module contract & mathematical conventions

Differentiable semiring / hypergraph DP driver (torch).

Bit-identical twin of omnibias.struct.jax.semiring (float64). Runs the ~omnibias.struct._core.semiring.LogSemiring (lse_beta) reduction of a ~omnibias.struct._core.semiring.Hypergraph over a backend edge_weights vector, unrolled so autograd flows through it (semiring_value), and reads off the closed-form **edge marginals** by one extra backward (outside) sweep and the tower softmax exp(beta (inside_tails + edge_weight + outside_head - value)) (semiring_marginals). The marginal of edge e equals d value / d edge_weights[e] -- the inside-outside generalization of the forward-backward path marginal -- which the tests pin equal to autograd.

This is the general engine the CKY / Eisner families lift to; it reproduces the hand-written ~omnibias.struct.torch.soft_viterbi / soft_shortest_path / soft_dtw / soft_align layers to < 1e-12 (the additive-safety cross-check), without modifying them. The beta -> inf reduction is the relaxation axis; the delta -> 0 tower differentiates it exactly -- do not conflate the two.

Shared formulas do not imply universal floating-point identity. Verify dtype, shape, derivative-order support, and the stated numerical assumptions for the path you use.

Module source ↗Source revision 9a2d73df0573Running reference examples →

FUNCTION

semiring_marginals

omnibias.struct.torch.semiring_marginalsSource ↗

semiring_marginals(graph: Hypergraph, edge_weights: Tensor, beta: float=1.0) -> Tensor

Closed-form edge marginals mu[e] = P_beta(edge e in the derivation) ((num_edges,)).

Inside-outside with the tower softmax; mu[e] = d semiring_value / d edge_weights[e] (the exact gradient), and the marginals of the edges into root sum to 1. As beta -> inf the mass concentrates on the best derivation (omnibias.struct.best_derivation).

Parameters

Name	Type & default	Contract
graphpositional-or-keyword	HypergraphRequired	See the operation contract and implementation below.
edge_weightspositional-or-keyword	TensorRequired	See the operation contract and implementation below.
betapositional-or-keyword	floatDefault: 1.0	See the operation contract and implementation below.

ReturnsTensor

Explicit validation & failure cases

• When edge_weights.shape[0] != graph.num_edges, raises ValueError(f'edge_weights must have length num_edges={graph.num_edges}, got {edge_weights.shape[0]}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · sampler empirical marginals converge

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_sampler_empirical_marginals_converge(backend: str) -> None:
    pytest.importorskip(backend)
    assert probe_sampling(0, BETA, backend).ok

python -m pytest "packages/omnibias-struct/tests/test_refinement_families.py::test_sampler_empirical_marginals_converge[torch]" -q

Regression example · sample paths empirical marginals

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_sample_paths_empirical_marginals() -> None:
    w = _weights(0)
    wt = torch.tensor(w)
    beta = 2.0
    counts, samples = st.sample_paths(GRAPH, wt, beta, 6000, seed=0)
    assert len(samples) == 6000
    empirical = counts.mean(0).numpy()
    closed_form = st.semiring_marginals(GRAPH, wt, beta).numpy()
    assert float(np.max(np.abs(empirical - closed_form))) < 0.03  # Monte-Carlo error ~ 1/sqrt(6000)

python -m pytest packages/omnibias-struct/tests/test_operators.py -k test_sample_paths_empirical_marginals -q

Read the implementation

def semiring_marginals(graph: Hypergraph, edge_weights: Tensor, beta: float = 1.0) -> Tensor:
    r"""Closed-form edge marginals ``mu[e] = P_beta(edge e in the derivation)`` (``(num_edges,)``).

    Inside-outside with the tower softmax; ``mu[e] = d semiring_value / d edge_weights[e]``
    (the exact gradient), and the marginals of the edges into ``root`` sum to ``1``. As
    ``beta -> inf`` the mass concentrates on the best derivation
    (:func:`omnibias.struct.best_derivation`).
    """
    if edge_weights.shape[0] != graph.num_edges:
        raise ValueError(
            f"edge_weights must have length num_edges={graph.num_edges}, got {edge_weights.shape[0]}"
        )
    inside = _inside(graph, edge_weights, beta)
    value = inside[graph.root]
    neg = torch.full((), _NEG, dtype=edge_weights.dtype, device=edge_weights.device)
    outside: list[Tensor] = [neg] * graph.num_nodes
    outside[graph.root] = torch.zeros((), dtype=edge_weights.dtype, device=edge_weights.device)
    # For each node, the incoming edges in which it appears as a tail (with sibling tails).
    as_tail: list[list[tuple[int, int]]] = [[] for _ in range(graph.num_nodes)]
    for ei, e in enumerate(graph.edges):
        for pos, t in enumerate(e.tails):
            as_tail[t].append((ei, pos))
    for v in range(graph.num_nodes - 1, -1, -1):
        if v == graph.root:
            continue
        rows: list[Tensor] = []
        for ei, pos in as_tail[v]:
            e = graph.edges[ei]
            term = edge_weights[ei] + outside[e.head]
            for j, t in enumerate(e.tails):
                if j != pos:
                    term = term + inside[t]
            rows.append(term)
        if rows:
            outside[v] = logsumexp_beta(torch.stack(rows), beta, axis=-1)
    marg: list[Tensor] = []
    for ei, e in enumerate(graph.edges):
        term = edge_weights[ei] + outside[e.head]
        for t in e.tails:
            term = term + inside[t]
        marg.append(torch.exp(beta * (term - value)))
    return torch.stack(marg)

Related APIsomnibias.struct.torch.logsumexp_beta↗

Other public import paths

• omnibias.struct.torch.semiring_marginals
• omnibias.struct.torch.semiring.semiring_marginals

FUNCTION

semiring_value

omnibias.struct.torch.semiring_valueSource ↗

semiring_value(graph: Hypergraph, edge_weights: Tensor, beta: float=1.0) -> Tensor

Soft (lse_beta) value of graph at its root for the edge_weights vector.

edge_weights is (graph.num_edges,); differentiable in it. Generalises omnibias.struct.torch.soft_shortest_path's topological reduce to arbitrary arity-1/2 hyperedges (parse spans, dependency arcs). -> max derivation score as beta -> inf.

Parameters

Name	Type & default	Contract
graphpositional-or-keyword	HypergraphRequired	See the operation contract and implementation below.
edge_weightspositional-or-keyword	TensorRequired	See the operation contract and implementation below.
betapositional-or-keyword	floatDefault: 1.0	See the operation contract and implementation below.

ReturnsTensor

Explicit validation & failure cases

• When edge_weights.shape[0] != graph.num_edges, raises ValueError(f'edge_weights must have length num_edges={graph.num_edges}, got {edge_weights.shape[0]}').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · parse marginals match autodiff

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_parse_marginals_match_autodiff(backend: str) -> None:
    pytest.importorskip(backend)
    assert probe_parse_marginals(0, BETA, backend).ok

python -m pytest "packages/omnibias-struct/tests/test_refinement_families.py::test_parse_marginals_match_autodiff[torch]" -q

Regression example · best derivation agrees with hard value

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_best_derivation_agrees_with_hard_value() -> None:
    g, w = _toy_graph()
    value, deriv = best_derivation(g, w)
    assert abs(value - hard_value(g, w)) < TOL
    # the derivation's edge weights sum back to the value
    assert abs(sum(w[e] for e in deriv) - value) < TOL

python -m pytest packages/omnibias-struct/tests/test_semiring.py -k test_best_derivation_agrees_with_hard_value -q

Read the implementation

def semiring_value(graph: Hypergraph, edge_weights: Tensor, beta: float = 1.0) -> Tensor:
    r"""Soft (``lse_beta``) value of ``graph`` at its ``root`` for the ``edge_weights`` vector.

    ``edge_weights`` is ``(graph.num_edges,)``; differentiable in it. Generalises
    :func:`omnibias.struct.torch.soft_shortest_path`'s topological reduce to arbitrary
    arity-1/2 hyperedges (parse spans, dependency arcs). ``-> max derivation score`` as
    ``beta -> inf``.
    """
    if edge_weights.shape[0] != graph.num_edges:
        raise ValueError(
            f"edge_weights must have length num_edges={graph.num_edges}, got {edge_weights.shape[0]}"
        )
    value: Tensor = _inside(graph, edge_weights, beta)[graph.root]
    return value

Other public import paths

• omnibias.struct.torch.semiring_value
• omnibias.struct.torch.semiring.semiring_value

← Package overviewRunnable learning examples →