API REFERENCE/omnibias-struct

omnibias.struct.verified

0.1.0a2AlphaPython >=3.10AGPL / commercial

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

import omnibias.struct.verified

Module contract & mathematical conventions

Public verified (interval) soft-DP surface -- sound, outward-rounded enclosures.

Re-exports the rigorous register of the soft DP from omnibias.struct._core.verified: lse_beta_iv / pairwise_lse_iv reductions and the chain_value_iv / dag_value_iv / dtw_value_iv / align_value_iv / ctc_value_iv recurrences that enclose V_beta for every point in an input box, the certified chain_marginals_iv forward-backward enclosure, the matrix_tree_partition_iv interval determinant, plus the box constructor. These are the beta -> inf relaxation computed with directed rounding; scope is always the given local_box.

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

align_value_iv

omnibias.struct.verified.align_value_ivSource ↗

align_value_iv(a: object, b: object, sub: Sequence[Sequence[Number]], gap: Number, beta: float) -> Interval

Sound interval enclosure of omnibias.struct.torch.soft_align over a param box.

sub is a (K, K) substitution-score box and gap a scalar gap box. Global alignment is a longest-path DAG, so this assembles the interval edge-cost matrix and reuses dag_value_iv; the enclosure contains the true soft score for every (sub, gap) in the box (repeated substitution entries are treated independently, so it is sound but not tight).

Parameters

Name	Type & default	Contract
apositional-or-keyword	objectRequired	See the operation contract and implementation below.
bpositional-or-keyword	objectRequired	See the operation contract and implementation below.
subpositional-or-keyword	Sequence[Sequence[Number]]Required	See the operation contract and implementation below.
gappositional-or-keyword	NumberRequired	See the operation contract and implementation below.
betapositional-or-keyword	floatRequired	See the operation contract and implementation below.

ReturnsInterval

Executed regression · align value iv encloses brute force over box

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_align_value_iv_encloses_brute_force_over_box() -> None:
    rng = np.random.default_rng(11)
    k = 3
    sub0 = rng.standard_normal((k, k))
    gap0, radius, beta = -1.0, 0.2, 2.0
    a, b = np.array([0, 1, 2]), np.array([0, 2])
    iv = align_value_iv(a, b, box(sub0, radius), Interval(gap0 - radius, gap0 + radius), beta)
    for _ in range(150):
        subp = sub0 + rng.uniform(-radius, radius, sub0.shape)
        gapp = gap0 + float(rng.uniform(-radius, radius))
        assert iv.lo - TOL <= brute_force_soft_align(a, b, subp, gapp, beta) <= iv.hi + TOL

python -m pytest "packages/omnibias-struct/tests/test_verified.py::test_align_value_iv_encloses_brute_force_over_box" -q

Read the implementation

def align_value_iv(
    a: object, b: object, sub: Sequence[Sequence[Number]], gap: Number, beta: float
) -> Interval:
    r"""Sound interval enclosure of :func:`omnibias.struct.torch.soft_align` over a param box.

    ``sub`` is a ``(K, K)`` substitution-score box and ``gap`` a scalar gap box. Global
    alignment is a longest-path DAG, so this assembles the interval edge-cost matrix and
    reuses :func:`dag_value_iv`; the enclosure contains the true soft score for every
    ``(sub, gap)`` in the box (repeated substitution entries are treated independently, so it
    is sound but not tight).
    """
    ai = np.asarray(a, dtype=int).reshape(-1)
    bj = np.asarray(b, dtype=int).reshape(-1)
    lattice = AlignmentLattice(ai.shape[0], bj.shape[0])
    dag, labels = lattice.build_dag()
    zero = Interval.point(0.0)
    weight: list[list[Interval]] = [[zero] * lattice.num_nodes for _ in range(lattice.num_nodes)]
    for (u, v), (kind, i, j) in labels.items():
        if kind == "sub":
            weight[u][v] = -_as_interval(sub[int(ai[i])][int(bj[j])])
        else:
            weight[u][v] = -_as_interval(gap)
    return -dag_value_iv(weight, dag, beta)

Related APIsomnibias.struct.AlignmentLattice↗omnibias.struct.verified.dag_value_iv↗

FUNCTION

box

omnibias.struct.verified.boxSource ↗

box(center: object, radius: float) -> list[Interval] | list[list[Interval]]

Build a symmetric interval box [c - radius, c + radius] for a 1-D / 2-D array.

Parameters

Name	Type & default	Contract
centerpositional-or-keyword	objectRequired	See the operation contract and implementation below.
radiuspositional-or-keyword	floatRequired	See the operation contract and implementation below.

Returnslist[Interval] | list[list[Interval]]

Executed regression · dtw value iv encloses brute force over box

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_dtw_value_iv_encloses_brute_force_over_box() -> None:
    rng = np.random.default_rng(10)
    center = rng.standard_normal((3, 3))
    radius, beta = 0.3, 2.0
    iv = dtw_value_iv(box(center, radius), beta)
    samples = _corners(center, radius) + [
        center + rng.uniform(-radius, radius, center.shape) for _ in range(80)
    ]
    for cost in samples:
        assert iv.lo - TOL <= brute_force_soft_dtw(cost, beta) <= iv.hi + TOL

python -m pytest "packages/omnibias-struct/tests/test_verified.py::test_dtw_value_iv_encloses_brute_force_over_box" -q

Regression example · matrix tree partition iv raises when positivity not provable

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_matrix_tree_partition_iv_raises_when_positivity_not_provable() -> None:
    # A wide, high-beta box loses the smaller trees to interval wrapping -- honest scope limit.
    rng = np.random.default_rng(15)
    arc0 = rng.standard_normal((5, 5))
    arc0[:, 0] = 0.0
    try:
        matrix_tree_partition_iv(box(arc0, 0.5), 4.0)
    except ValueError:
        return
    raise AssertionError("expected a ValueError on a box too wide to certify det > 0")

python -m pytest packages/omnibias-struct/tests/test_verified.py -k test_matrix_tree_partition_iv_raises_when_positivity_not_provable -q

Read the implementation

def box(center: object, radius: float) -> list[Interval] | list[list[Interval]]:
    r"""Build a symmetric interval box ``[c - radius, c + radius]`` for a 1-D / 2-D array."""
    c = np.asarray(center, dtype=float)
    r = float(radius)
    if c.ndim == 1:
        return [Interval(float(c[i]) - r, float(c[i]) + r) for i in range(c.shape[0])]
    if c.ndim == 2:
        return [
            [Interval(float(c[i, j]) - r, float(c[i, j]) + r) for j in range(c.shape[1])]
            for i in range(c.shape[0])
        ]
    raise ValueError(f"box supports 1-D or 2-D centers, got ndim {c.ndim}")

Related APIsomnibias.core.verified.Interval↗

FUNCTION

chain_marginals_iv

omnibias.struct.verified.chain_marginals_ivSource ↗

chain_marginals_iv(emissions: Sequence[Sequence[Number]], transitions: Sequence[Sequence[Number]], beta: float, *, start: Sequence[Number] | None=None) -> list[list[Interval]]

Sound interval forward-backward enclosure of the (T, S) state-occupancy marginals.

mu[t][s] encloses P_beta(state s at time t) -- equivalently d soft_viterbi / d emissions[t, s] -- for every emission / transition matrix in the box. Uses the log-domain identity mu = exp(beta (alpha + backward - Z)) with outward-rounded lse_beta forward / backward passes; sound (not tight), local_box scope. Each row soundly encloses the simplex point (sum_s mu[t][s] contains 1).

Parameters

Name	Type & default	Contract
emissionspositional-or-keyword	Sequence[Sequence[Number]]Required	See the operation contract and implementation below.
transitionspositional-or-keyword	Sequence[Sequence[Number]]Required	See the operation contract and implementation below.
betapositional-or-keyword	floatRequired	See the operation contract and implementation below.
startkeyword-only	Sequence[Number] | NoneDefault: None	See the operation contract and implementation below.

Returnslist[list[Interval]]

Executed regression · chain marginals iv encloses brute force and the simplex

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_chain_marginals_iv_encloses_brute_force_and_the_simplex() -> None:
    rng = np.random.default_rng(13)
    n_steps, n_states = 3, 2
    center = rng.standard_normal((n_steps, n_states))
    transitions = rng.standard_normal((n_states, n_states))
    start = rng.standard_normal(n_states)
    radius, beta = 0.15, 2.0
    mu_iv = chain_marginals_iv(box(center, radius), transitions, beta, start=start)
    samples = _corners(center, radius) + [
        center + rng.uniform(-radius, radius, center.shape) for _ in range(60)
    ]
    for emissions in samples:
        mu = _brute_chain_marginals(emissions, transitions, start, beta)
        for t in range(n_steps):
            for s in range(n_states):
                assert mu_iv[t][s].lo - TOL <= mu[t, s] <= mu_iv[t][s].hi + TOL
    # every row soundly encloses the simplex constraint sum_s mu = 1
    for t in range(n_steps):
        lo = sum(mu_iv[t][s].lo for s in range(n_states))
        hi = sum(mu_iv[t][s].hi for s in range(n_states))
        assert lo - TOL <= 1.0 <= hi + TOL

python -m pytest "packages/omnibias-struct/tests/test_verified.py::test_chain_marginals_iv_encloses_brute_force_and_the_simplex" -q

Read the implementation

def chain_marginals_iv(
    emissions: Sequence[Sequence[Number]],
    transitions: Sequence[Sequence[Number]],
    beta: float,
    *,
    start: Sequence[Number] | None = None,
) -> list[list[Interval]]:
    r"""Sound interval forward-backward enclosure of the ``(T, S)`` state-occupancy marginals.

    ``mu[t][s]`` encloses ``P_beta(state s at time t)`` -- equivalently
    ``d soft_viterbi / d emissions[t, s]`` -- for every emission / transition matrix in the
    box. Uses the log-domain identity ``mu = exp(beta (alpha + backward - Z))`` with
    outward-rounded ``lse_beta`` forward / backward passes; sound (not tight), ``local_box``
    scope. Each row soundly encloses the simplex point (``sum_s mu[t][s]`` contains ``1``).
    """
    n_steps = len(emissions)
    n_states = len(emissions[0])
    emit = [[_as_interval(emissions[t][s]) for s in range(n_states)] for t in range(n_steps)]
    trans = [[_as_interval(transitions[i][j]) for j in range(n_states)] for i in range(n_states)]
    start_iv = (
        [Interval.point(0.0) for _ in range(n_states)]
        if start is None
        else [_as_interval(start[s]) for s in range(n_states)]
    )
    alpha = [[start_iv[s] + emit[0][s] for s in range(n_states)]]
    for t in range(1, n_steps):
        alpha.append(
            [
                emit[t][s] + lse_beta_iv([alpha[t - 1][sp] + trans[sp][s] for sp in range(n_states)], beta)
                for s in range(n_states)
            ]
        )
    bwd: list[list[Interval]] = [[Interval.point(0.0) for _ in range(n_states)] for _ in range(n_steps)]
    for t in range(n_steps - 2, -1, -1):
        bwd[t] = [
            lse_beta_iv(
                [trans[s][sp] + emit[t + 1][sp] + bwd[t + 1][sp] for sp in range(n_states)], beta
            )
            for s in range(n_states)
        ]
    z = lse_beta_iv(alpha[n_steps - 1], beta)
    return [
        [exp_iv(beta * (alpha[t][s] + bwd[t][s] - z)) for s in range(n_states)]
        for t in range(n_steps)
    ]

Related APIsomnibias.core.verified.exp_iv↗omnibias.struct.verified.lse_beta_iv↗

FUNCTION

chain_value_iv

omnibias.struct.verified.chain_value_ivSource ↗

chain_value_iv(emissions: Sequence[Sequence[Number]], transitions: Sequence[Sequence[Number]], beta: float, *, start: Sequence[Number] | None=None) -> Interval

Sound interval enclosure of soft_viterbi over a box of emissions / transitions.

emissions is (T, S) and transitions is (S, S) of numbers or Interval; start is (S,) or None. Encloses the true soft value for every point in the box (local scope).

Parameters

Name	Type & default	Contract
emissionspositional-or-keyword	Sequence[Sequence[Number]]Required	See the operation contract and implementation below.
transitionspositional-or-keyword	Sequence[Sequence[Number]]Required	See the operation contract and implementation below.
betapositional-or-keyword	floatRequired	See the operation contract and implementation below.
startkeyword-only	Sequence[Number] | NoneDefault: None	See the operation contract and implementation below.

ReturnsInterval

Executed regression · enclosures widen with radius but contain the point

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_enclosures_widen_with_radius_but_contain_the_point() -> None:
    rng = np.random.default_rng(4)
    center = rng.standard_normal((3, 2))
    transitions = rng.standard_normal((2, 2))
    beta = 2.0
    point = chain_value_iv(box(center, 0.0), transitions, beta)
    wide = chain_value_iv(box(center, 0.5), transitions, beta)
    assert point.width < wide.width  # sound-not-tight: wider box -> wider enclosure
    true = brute_force_partition(ChainTrellis(center, transitions, np.zeros(2)), beta)
    assert point.lo - TOL <= true <= point.hi + TOL

python -m pytest "packages/omnibias-struct/tests/test_verified.py::test_enclosures_widen_with_radius_but_contain_the_point" -q

Regression example · chain value iv encloses brute force over box

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_chain_value_iv_encloses_brute_force_over_box() -> None:
    rng = np.random.default_rng(2)
    n_steps, n_states = 3, 2
    center = rng.standard_normal((n_steps, n_states))
    transitions = rng.standard_normal((n_states, n_states))
    start = rng.standard_normal(n_states)
    radius = 0.3
    beta = 2.0
    iv = chain_value_iv(box(center, radius), transitions, beta, start=start)
    samples = _corners(center, radius) + [
        center + rng.uniform(-radius, radius, center.shape) for _ in range(100)
    ]
    for emissions in samples:
        true = brute_force_partition(ChainTrellis(emissions, transitions, start), beta)
        assert iv.lo - TOL <= true <= iv.hi + TOL

python -m pytest packages/omnibias-struct/tests/test_verified.py -k test_chain_value_iv_encloses_brute_force_over_box -q

Read the implementation

def chain_value_iv(
    emissions: Sequence[Sequence[Number]],
    transitions: Sequence[Sequence[Number]],
    beta: float,
    *,
    start: Sequence[Number] | None = None,
) -> Interval:
    r"""Sound interval enclosure of ``soft_viterbi`` over a box of emissions / transitions.

    ``emissions`` is ``(T, S)`` and ``transitions`` is ``(S, S)`` of numbers or
    :class:`Interval`; ``start`` is ``(S,)`` or ``None``. Encloses the true soft value for
    every point in the box (local scope).
    """
    n_steps = len(emissions)
    n_states = len(emissions[0])
    emit = [[_as_interval(emissions[t][s]) for s in range(n_states)] for t in range(n_steps)]
    trans = [[_as_interval(transitions[i][j]) for j in range(n_states)] for i in range(n_states)]
    start_iv = (
        [_as_interval(0.0) for _ in range(n_states)]
        if start is None
        else [_as_interval(start[s]) for s in range(n_states)]
    )
    alpha = [start_iv[s] + emit[0][s] for s in range(n_states)]
    for t in range(1, n_steps):
        alpha = [
            emit[t][s] + lse_beta_iv([alpha[sp] + trans[sp][s] for sp in range(n_states)], beta)
            for s in range(n_states)
        ]
    return lse_beta_iv(alpha, beta)

Related APIsomnibias.struct.verified.lse_beta_iv↗

FUNCTION

ctc_value_iv

omnibias.struct.verified.ctc_value_ivSource ↗

ctc_value_iv(log_probs: Sequence[Sequence[Number]], lattice: CTCLattice, beta: float) -> Interval

Sound interval enclosure of the soft CTC log-partition over a log_probs box.

log_probs is the (T, C) box; lattice fixes the target label sequence. Runs the blank-augmented forward recursion with outward-rounded lse_beta and encloses the true CTC soft value (omnibias.struct.brute_force_partition) for every log_probs in the box (local_box scope).

Parameters

Name	Type & default	Contract
log_probspositional-or-keyword	Sequence[Sequence[Number]]Required	See the operation contract and implementation below.
latticepositional-or-keyword	CTCLatticeRequired	See the operation contract and implementation below.
betapositional-or-keyword	floatRequired	See the operation contract and implementation below.

ReturnsInterval

Explicit validation & failure cases

• When not reachable, raises ValueError('no CTC alignment reaches an accepting state (T too small?)').

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

Executed regression · ctc value iv encloses brute force over box

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_ctc_value_iv_encloses_brute_force_over_box() -> None:
    rng = np.random.default_rng(12)
    lattice = CTCLattice(np.array([1]), num_classes=3, blank=0)
    n_steps = 3
    center = rng.standard_normal((n_steps, 3))
    radius, beta = 0.2, 2.0
    iv = ctc_value_iv(box(center, radius), lattice, beta)
    samples = _corners(center, radius) + [
        center + rng.uniform(-radius, radius, center.shape) for _ in range(80)
    ]
    for lp in samples:
        assert iv.lo - TOL <= brute_force_partition(lattice, beta, lp) <= iv.hi + TOL

python -m pytest "packages/omnibias-struct/tests/test_verified.py::test_ctc_value_iv_encloses_brute_force_over_box" -q

Read the implementation

def ctc_value_iv(
    log_probs: Sequence[Sequence[Number]], lattice: CTCLattice, beta: float
) -> Interval:
    r"""Sound interval enclosure of the soft CTC log-partition over a ``log_probs`` box.

    ``log_probs`` is the ``(T, C)`` box; ``lattice`` fixes the target label sequence. Runs the
    blank-augmented forward recursion with outward-rounded ``lse_beta`` and encloses the true
    CTC soft value (``omnibias.struct.brute_force_partition``) for every ``log_probs`` in the
    box (``local_box`` scope).
    """
    lp = [[_as_interval(log_probs[t][c]) for c in range(len(log_probs[t]))] for t in range(len(log_probs))]
    n_steps = len(lp)
    ext = [int(x) for x in lattice.extended_labels()]
    m = len(ext)
    alpha: list[Interval | None] = [None] * m
    alpha[0] = lp[0][ext[0]]
    if m > 1:
        alpha[1] = lp[0][ext[1]]
    for t in range(1, n_steps):
        nxt: list[Interval | None] = [None] * m
        for s in range(m):
            preds = [alpha[p] for p in lattice.incoming(s) if alpha[p] is not None]
            if not preds:
                continue
            nxt[s] = lp[t][ext[s]] + lse_beta_iv([p for p in preds if p is not None], beta)
        alpha = nxt
    ends = [alpha[m - 1]] + ([alpha[m - 2]] if m >= 2 else [])
    reachable = [e for e in ends if e is not None]
    if not reachable:
        raise ValueError("no CTC alignment reaches an accepting state (T too small?)")
    return lse_beta_iv(reachable, beta)

Related APIsomnibias.struct.verified.lse_beta_iv↗

FUNCTION

dag_value_iv

omnibias.struct.verified.dag_value_ivSource ↗

dag_value_iv(weights: Sequence[Sequence[Number]], dag: DAG, beta: float) -> Interval

Sound interval enclosure of soft_shortest_path (softmin cost) over a weight box.

weights is (n, n) of numbers or Interval (only dag edge entries are read). Returns -alpha[sink] in the max convention (the softmin cost enclosure).

Parameters

Name	Type & default	Contract
weightspositional-or-keyword	Sequence[Sequence[Number]]Required	See the operation contract and implementation below.
dagpositional-or-keyword	DAGRequired	See the operation contract and implementation below.
betapositional-or-keyword	floatRequired	See the operation contract and implementation below.

ReturnsInterval

Explicit validation & failure cases

• When sink is None, raises ValueError('sink is not reachable from source in this DAG').

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

Executed regression · align value iv encloses brute force over box

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_align_value_iv_encloses_brute_force_over_box() -> None:
    rng = np.random.default_rng(11)
    k = 3
    sub0 = rng.standard_normal((k, k))
    gap0, radius, beta = -1.0, 0.2, 2.0
    a, b = np.array([0, 1, 2]), np.array([0, 2])
    iv = align_value_iv(a, b, box(sub0, radius), Interval(gap0 - radius, gap0 + radius), beta)
    for _ in range(150):
        subp = sub0 + rng.uniform(-radius, radius, sub0.shape)
        gapp = gap0 + float(rng.uniform(-radius, radius))
        assert iv.lo - TOL <= brute_force_soft_align(a, b, subp, gapp, beta) <= iv.hi + TOL

python -m pytest "packages/omnibias-struct/tests/test_verified.py::test_align_value_iv_encloses_brute_force_over_box" -q

Regression example · dag value iv encloses brute force over box

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_dag_value_iv_encloses_brute_force_over_box() -> None:
    rng = np.random.default_rng(3)
    n = 4
    base_edges = {(0, 1): 1.0, (0, 2): 1.5, (1, 2): 0.5, (1, 3): 0.8, (2, 3): 0.6}
    dag = DAG(n, base_edges, sink=n - 1)
    center = np.zeros((n, n))
    for (u, v), w in base_edges.items():
        center[u, v] = w
    radius = 0.25
    beta = 2.0
    iv = dag_value_iv(box(center, radius), dag, beta)
    edge_keys = list(base_edges)
    corners = itertools.product((-1.0, 1.0), repeat=len(edge_keys))
    samples = [
        {k: base_edges[k] + radius * s for k, s in zip(edge_keys, signs, strict=True)}
        for signs in corners
    ] + [
        {k: base_edges[k] + float(rng.uniform(-radius, radius)) for k in edge_keys}
        for _ in range(100)
    ]
    for edges in samples:
        dag_pt = DAG(n, edges, sink=n - 1)
        true_cost = -brute_force_partition(dag_pt, beta)  # cost = -(max-convention soft value)
        assert iv.lo - TOL <= true_cost <= iv.hi + TOL

python -m pytest packages/omnibias-struct/tests/test_verified.py -k test_dag_value_iv_encloses_brute_force_over_box -q

Read the implementation

def dag_value_iv(
    weights: Sequence[Sequence[Number]],
    dag: DAG,
    beta: float,
) -> Interval:
    r"""Sound interval enclosure of ``soft_shortest_path`` (softmin cost) over a weight box.

    ``weights`` is ``(n, n)`` of numbers or :class:`Interval` (only ``dag`` edge entries
    are read). Returns ``-alpha[sink]`` in the max convention (the softmin cost enclosure).
    """
    alpha: list[Interval | None] = [None] * dag.num_nodes
    alpha[dag.source] = _as_interval(0.0)
    for v in range(dag.num_nodes):
        if v == dag.source:
            continue
        preds = [u for u in dag.incoming(v) if alpha[u] is not None]
        if not preds:
            continue
        contribs = [alpha_u - _as_interval(weights[u][v]) for u in preds if (alpha_u := alpha[u]) is not None]
        alpha[v] = lse_beta_iv(contribs, beta)
    sink = alpha[dag.sink]
    if sink is None:
        raise ValueError("sink is not reachable from source in this DAG")
    return -sink

Related APIsomnibias.struct.verified.lse_beta_iv↗

FUNCTION

dtw_value_iv

omnibias.struct.verified.dtw_value_ivSource ↗

dtw_value_iv(cost: Sequence[Sequence[Number]], beta: float) -> Interval

Sound interval enclosure of omnibias.struct.torch.soft_dtw over a cost box.

cost is the (n, m) local-cost box (numbers or Interval). The soft-DTW recursion is a per-cell **softmin** (-lse_beta of the negated predecessors), which equals the flat softmin over all monotonic paths; the interval version encloses the true soft value for every cost matrix in the box (local_box scope).

Parameters

Name	Type & default	Contract
costpositional-or-keyword	Sequence[Sequence[Number]]Required	See the operation contract and implementation below.
betapositional-or-keyword	floatRequired	See the operation contract and implementation below.

ReturnsInterval

Explicit validation & failure cases

• When out is None, raises ValueError('DTW sink is unreachable').

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

Executed regression · dtw value iv encloses brute force over box

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_dtw_value_iv_encloses_brute_force_over_box() -> None:
    rng = np.random.default_rng(10)
    center = rng.standard_normal((3, 3))
    radius, beta = 0.3, 2.0
    iv = dtw_value_iv(box(center, radius), beta)
    samples = _corners(center, radius) + [
        center + rng.uniform(-radius, radius, center.shape) for _ in range(80)
    ]
    for cost in samples:
        assert iv.lo - TOL <= brute_force_soft_dtw(cost, beta) <= iv.hi + TOL

python -m pytest "packages/omnibias-struct/tests/test_verified.py::test_dtw_value_iv_encloses_brute_force_over_box" -q

Read the implementation

def dtw_value_iv(cost: Sequence[Sequence[Number]], beta: float) -> Interval:
    r"""Sound interval enclosure of :func:`omnibias.struct.torch.soft_dtw` over a cost box.

    ``cost`` is the ``(n, m)`` local-cost box (numbers or :class:`Interval`). The soft-DTW
    recursion is a per-cell **softmin** (``-lse_beta`` of the negated predecessors), which
    equals the flat softmin over all monotonic paths; the interval version encloses the true
    soft value for every cost matrix in the box (``local_box`` scope).
    """
    d = [[_as_interval(cost[i][j]) for j in range(len(cost[i]))] for i in range(len(cost))]
    n, m = len(d), len(d[0])
    r: list[list[Interval | None]] = [[None] * m for _ in range(n)]
    r[0][0] = d[0][0]
    for i in range(n):
        for j in range(m):
            if i == 0 and j == 0:
                continue
            preds = [
                r[pi][pj]
                for pi, pj in ((i - 1, j), (i, j - 1), (i - 1, j - 1))
                if pi >= 0 and pj >= 0 and r[pi][pj] is not None
            ]
            r[i][j] = d[i][j] + _softmin_iv([p for p in preds if p is not None], beta)
    out = r[n - 1][m - 1]
    if out is None:
        raise ValueError("DTW sink is unreachable")
    return out

FUNCTION

lse_beta_iv

omnibias.struct.verified.lse_beta_ivSource ↗

lse_beta_iv(values: Sequence[Number], beta: float) -> Interval

Outward-rounded enclosure of lse_beta over interval-valued scores.

Uses the scalar-shift identity for stability; the result soundly encloses beta^-1 log sum_i exp(beta v_i) for every point selection v_i in values_i.

Parameters

Name	Type & default	Contract
valuespositional-or-keyword	Sequence[Number]Required	See the operation contract and implementation below.
betapositional-or-keyword	floatRequired	See the operation contract and implementation below.

ReturnsInterval

Explicit validation & failure cases

• When beta <= 0.0, raises ValueError(f'beta must be > 0, got {beta}').
• When not ivs, raises ValueError('lse_beta_iv needs at least one value').

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

Executed regression · dtw value iv encloses brute force over box

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_dtw_value_iv_encloses_brute_force_over_box() -> None:
    rng = np.random.default_rng(10)
    center = rng.standard_normal((3, 3))
    radius, beta = 0.3, 2.0
    iv = dtw_value_iv(box(center, radius), beta)
    samples = _corners(center, radius) + [
        center + rng.uniform(-radius, radius, center.shape) for _ in range(80)
    ]
    for cost in samples:
        assert iv.lo - TOL <= brute_force_soft_dtw(cost, beta) <= iv.hi + TOL

python -m pytest "packages/omnibias-struct/tests/test_verified.py::test_dtw_value_iv_encloses_brute_force_over_box" -q

Regression example · lse beta iv encloses grid and random

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_lse_beta_iv_encloses_grid_and_random() -> None:
    rng = np.random.default_rng(0)
    center = rng.standard_normal(4)
    radius = 0.4
    for beta in (1.0, 4.0):
        iv = lse_beta_iv(box(center, radius), beta)
        pts = _corners(center, radius) + [center + rng.uniform(-radius, radius, 4) for _ in range(200)]
        for x in pts:
            m = float(np.max(beta * x))
            true = (m + np.log(np.sum(np.exp(beta * x - m)))) / beta
            assert iv.lo - TOL <= true <= iv.hi + TOL

python -m pytest packages/omnibias-struct/tests/test_verified.py -k test_lse_beta_iv_encloses_grid_and_random -q

Read the implementation

def lse_beta_iv(values: Sequence[Number], beta: float) -> Interval:
    r"""Outward-rounded enclosure of ``lse_beta`` over interval-valued scores.

    Uses the scalar-shift identity for stability; the result soundly encloses
    ``beta^-1 log sum_i exp(beta v_i)`` for every point selection ``v_i in values_i``.
    """
    if beta <= 0.0:
        raise ValueError(f"beta must be > 0, got {beta}")
    ivs = [_as_interval(v) for v in values]
    if not ivs:
        raise ValueError("lse_beta_iv needs at least one value")
    shift = max(iv.hi for iv in ivs)
    total = exp_iv(beta * (ivs[0] - shift))
    for iv in ivs[1:]:
        total = total + exp_iv(beta * (iv - shift))
    return shift + ln_iv(total) * (1.0 / beta)

Related APIsomnibias.core.verified.exp_iv↗omnibias.core.verified.ln_iv↗

FUNCTION

matrix_tree_partition_iv

omnibias.struct.verified.matrix_tree_partition_ivSource ↗

matrix_tree_partition_iv(arc: Sequence[Sequence[Number]], beta: float) -> Interval

Sound interval enclosure of the Matrix-Tree log-partition log det L(beta) / beta.

arc is the (n + 1, n + 1) arc-score box (row / column 0 is the ROOT wall). The Kirchhoff Laplacian is built with a fixed column-max log-shift (so exp arguments stay <= 0) and its determinant is enclosed by the Leibniz permutation sum -- exact for tiny n, and the log-partition encloses omnibias.struct.brute_force_arborescence for every arc matrix in the box. This is the rigorous register of the *exact* determinant partition (not an lse_beta relaxation); local_box scope.

Parameters

Name	Type & default	Contract
arcpositional-or-keyword	Sequence[Sequence[Number]]Required	See the operation contract and implementation below.
betapositional-or-keyword	floatRequired	See the operation contract and implementation below.

ReturnsInterval

Explicit validation & failure cases

• When beta <= 0.0, raises ValueError(f'beta must be > 0, got {beta}').
• When n < 1, raises ValueError(f'need at least one word (arc >= 2x2), got n={n}').
• When det.lo <= 0.0, raises ValueError('Laplacian determinant enclosure is not strictly positive over the box').

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

Executed regression · matrix tree partition iv raises when positivity not provable

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_matrix_tree_partition_iv_raises_when_positivity_not_provable() -> None:
    # A wide, high-beta box loses the smaller trees to interval wrapping -- honest scope limit.
    rng = np.random.default_rng(15)
    arc0 = rng.standard_normal((5, 5))
    arc0[:, 0] = 0.0
    try:
        matrix_tree_partition_iv(box(arc0, 0.5), 4.0)
    except ValueError:
        return
    raise AssertionError("expected a ValueError on a box too wide to certify det > 0")

python -m pytest "packages/omnibias-struct/tests/test_verified.py::test_matrix_tree_partition_iv_raises_when_positivity_not_provable" -q

Regression example · enclosures widen with radius but contain the point

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_enclosures_widen_with_radius_but_contain_the_point() -> None:
    rng = np.random.default_rng(4)
    center = rng.standard_normal((3, 2))
    transitions = rng.standard_normal((2, 2))
    beta = 2.0
    point = chain_value_iv(box(center, 0.0), transitions, beta)
    wide = chain_value_iv(box(center, 0.5), transitions, beta)
    assert point.width < wide.width  # sound-not-tight: wider box -> wider enclosure
    true = brute_force_partition(ChainTrellis(center, transitions, np.zeros(2)), beta)
    assert point.lo - TOL <= true <= point.hi + TOL

python -m pytest packages/omnibias-struct/tests/test_verified.py -k test_enclosures_widen_with_radius_but_contain_the_point -q

Read the implementation

def matrix_tree_partition_iv(arc: Sequence[Sequence[Number]], beta: float) -> Interval:
    r"""Sound interval enclosure of the Matrix-Tree log-partition ``log det L(beta) / beta``.

    ``arc`` is the ``(n + 1, n + 1)`` arc-score box (row / column ``0`` is the ROOT wall).
    The Kirchhoff Laplacian is built with a fixed column-max log-shift (so ``exp`` arguments
    stay ``<= 0``) and its determinant is enclosed by the Leibniz permutation sum -- exact for
    tiny ``n``, and the log-partition encloses :func:`omnibias.struct.brute_force_arborescence`
    for every arc matrix in the box. This is the rigorous register of the *exact* determinant
    partition (not an ``lse_beta`` relaxation); ``local_box`` scope.
    """
    if beta <= 0.0:
        raise ValueError(f"beta must be > 0, got {beta}")
    a = [[_as_interval(arc[h][m]) for m in range(len(arc[h]))] for h in range(len(arc))]
    n = len(a) - 1
    if n < 1:
        raise ValueError(f"need at least one word (arc >= 2x2), got n={n}")
    # Fixed scalar log-shift per modifier column (uses the box upper bound; any fixed c is sound).
    c = [max((beta * a[h][m]).hi for h in range(n + 1) if h != m) for m in range(1, n + 1)]
    ltilde: list[list[Interval]] = [[Interval.point(0.0) for _ in range(n)] for _ in range(n)]
    for m in range(1, n + 1):
        for h in range(n + 1):
            if h == m:
                continue
            wt = exp_iv(beta * a[h][m] - c[m - 1])
            ltilde[m - 1][m - 1] = ltilde[m - 1][m - 1] + wt
            if h >= 1:
                ltilde[h - 1][m - 1] = ltilde[h - 1][m - 1] - wt
    det = _interval_det(ltilde)
    if det.lo <= 0.0:
        raise ValueError("Laplacian determinant enclosure is not strictly positive over the box")
    return (ln_iv(det) + float(sum(c))) * (1.0 / beta)

Related APIsomnibias.core.verified.exp_iv↗omnibias.core.verified.ln_iv↗

FUNCTION

pairwise_lse_iv

omnibias.struct.verified.pairwise_lse_ivSource ↗

pairwise_lse_iv(a: Number, b: Number, beta: float) -> Interval

Outward-rounded pairwise lse_beta(a, b) = a + beta^-1 softplus(beta (b - a)).

Parameters

Name	Type & default	Contract
apositional-or-keyword	NumberRequired	See the operation contract and implementation below.
bpositional-or-keyword	NumberRequired	See the operation contract and implementation below.
betapositional-or-keyword	floatRequired	See the operation contract and implementation below.

ReturnsInterval

Explicit validation & failure cases

• When beta <= 0.0, raises ValueError(f'beta must be > 0, got {beta}').

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

Executed regression · pairwise lse iv encloses and matches vector form

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_pairwise_lse_iv_encloses_and_matches_vector_form() -> None:
    rng = np.random.default_rng(1)
    for _ in range(50):
        a, b = rng.standard_normal(2)
        beta = 3.0
        iv = pairwise_lse_iv(a, b, beta)
        true = (np.logaddexp(beta * a, beta * b)) / beta
        assert iv.lo - TOL <= true <= iv.hi + TOL

python -m pytest "packages/omnibias-struct/tests/test_verified.py::test_pairwise_lse_iv_encloses_and_matches_vector_form" -q

Regression example · dtw value iv encloses brute force over box

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_dtw_value_iv_encloses_brute_force_over_box() -> None:
    rng = np.random.default_rng(10)
    center = rng.standard_normal((3, 3))
    radius, beta = 0.3, 2.0
    iv = dtw_value_iv(box(center, radius), beta)
    samples = _corners(center, radius) + [
        center + rng.uniform(-radius, radius, center.shape) for _ in range(80)
    ]
    for cost in samples:
        assert iv.lo - TOL <= brute_force_soft_dtw(cost, beta) <= iv.hi + TOL

python -m pytest packages/omnibias-struct/tests/test_verified.py -k test_dtw_value_iv_encloses_brute_force_over_box -q

Read the implementation

def pairwise_lse_iv(a: Number, b: Number, beta: float) -> Interval:
    r"""Outward-rounded pairwise ``lse_beta(a, b) = a + beta^-1 softplus(beta (b - a))``."""
    if beta <= 0.0:
        raise ValueError(f"beta must be > 0, got {beta}")
    ai, bi = _as_interval(a), _as_interval(b)
    return ai + softplus_iv(beta * (bi - ai)) * (1.0 / beta)

Related APIsomnibias.core.verified.softplus_iv↗

← Package overviewRunnable learning examples →