DiscreteSearch - GTSAM Docs

Search is an alternative to exact discrete inference, which can be exponential. DiscreteSearch enumerates the best assignments of a discrete model in increasing error order, returning each complete assignment and its negative-log error as a DiscreteSearchSolution.

Authors: Frank Dellaert, et al. (see THANKS for the full author list)

See LICENSE for the license information

try:
    import google.colab
    %pip install --quiet gtsam-develop
except ImportError:
    pass

import gtsam
import numpy as np
from gtsam.symbol_shorthand import M, X
from IPython.display import Markdown, display

Constructing the search problem¶

FromFactorGraph() eliminates a graph into the internal search representation. The explicit ordering controls that preprocessing; setting buildJunctionTree=True selects the junction-tree construction path.

A = (gtsam.symbol("A", 0), 2)
B = (gtsam.symbol("B", 0), 2)

graph = gtsam.DiscreteFactorGraph()
graph.add(A, "0.6 0.4")
graph.add([B, A], "0.8 0.2 0.3 0.7")

ordering = gtsam.Ordering()
ordering.push_back(B[0])
ordering.push_back(A[0])
search = gtsam.DiscreteSearch.FromFactorGraph(graph, ordering)

Ranked solutions¶

run(K) returns at most K DiscreteSearchSolution objects. assignment is a DiscreteValues map and error is the additive objective; lower error means higher probability. lowerBound() reports the search object’s current lower bound.

solutions = search.run(K=3)
for rank, solution in enumerate(solutions, start=1):
    assignment = {
        gtsam.DefaultKeyFormatter(k): value
        for k, value in solution.assignment.items()
    }
    print(rank, assignment, "error =", solution.error)

assert all(
    solutions[i].error <= solutions[i + 1].error
    for i in range(len(solutions) - 1)
)

Alternative inputs¶

The constructor also accepts an existing DiscreteEliminationTree, DiscreteJunctionTree, DiscreteBayesNet, or DiscreteBayesTree. Reuse one of those when elimination has already been performed. Search is useful for N-best hypotheses; use DiscreteFactorGraph.optimize() when only the single MPE solution is needed.

Source¶

DiscreteSearch.h

AI assistance caveat¶

AI was used to help draft this documentation, and inaccuracies could be present.