Approximate evaluation of marginal association probabilities with belief propagation

Jason L. Williams; Roslyn A. Lau

Source-linked AI summary

Approximate evaluation of marginal association probabilities with belief propagation

Jason L. Williams, Roslyn A. Lau

arXiv:1209.6299v2Sep 12, 2012cs.AIcs.CV

TL;DR

Data association requires marginal target–measurement probabilities, but exact computation is intractable for all but small problems. This paper applies belief propagation to a graphical model, proving convergence and iteration bounds. Experiments report accurate estimates with favorable computation-time trade-offs against alternative methods.

Problem
Exact marginal association probabilities are computationally intractable for all but the smallest data-association problems.
Method
The paper uses belief propagation on a graphical-model formulation to approximate marginal association probabilities and provides convergence and iteration guarantees.
Results
BP errors are 0.015 or less in most cases, while outperforming LMIPDA and BAA with errors reduced by a factor of ten in most cases.
Takeaways & Limitations
The approximate method offers a favorable accuracy-versus-computation-time trade-off compared with state-of-the-art alternatives.

Abstract

from arXiv · show

Data association, the problem of reasoning over correspondence between targets and measurements, is a fundamental problem in tracking. This paper presents a graphical model formulation of data association and applies an approximate inference method, belief propagation (BP), to obtain estimates of marginal association probabilities. We prove that BP is guaranteed to converge, and bound the number of iterations necessary. Experiments reveal a favourable comparison to prior methods in terms of accuracy and computational complexity.

I. INTRODUCTION

The paper formulates classical data association as estimating marginal measurement-to-target probabilities in a large single-sensor tracking problem. It develops belief propagation as a practical approximation, proving convergence and iteration bounds, then evaluates accuracy and computational trade-offs.

The problem assigns each target and measurement at most one correspondence while estimating marginal association probabilities for tracking methods such as JPDA.
Exact marginal-probability calculation is generally intractable because it is closely related to evaluating the permanent of a non-negative matrix.
The paper develops belief propagation as a practical approximation that remains accurate despite cycles in its graphical-model formulation.
Its contributions include convergence proofs for common nonzero false-alarm and nonunit detection settings, complexity analysis, and iteration guarantees.
Experiments compare accuracy and computation time with state-of-the-art tracking methods, locating the approximation on an accuracy-versus-computation-time trade-off.

B. Graphical models

Graphical models represent joint distributions through factorization, enabling belief propagation to perform exact inference on trees and approximate inference on cyclic graphs. This paper studies a cyclic case with convergence guarantees despite BP’s usual limitations.

Graphical models exploit factorization to represent and manipulate joint distributions involving many variables efficiently.
Belief propagation passes messages between neighboring nodes using iterative sum-product updates, and at convergence produces node marginal distributions.
On cyclic graphs, BP may fail to converge or converge to an incorrect answer, although it often performs well empirically.
BP’s Bethe-free-energy and feasible-set approximations can produce large errors or infeasible solutions in some circumstances.
On trees, BP is exact because the Bethe free energy is convex and the feasible set is exact.
The paper studies a case with guarantees on BP convergence despite the non-tree graphical structure.

C. Graphical models, matching and permanents

Data association can be represented as a weighted matching problem, linking marginal-probability computation to matchings and matrix permanents. The paper applies BP to this matching-based model and proves convergence on a restricted graph class.

A matching contains edges with no shared endpoints, and most-likely data association is formulated as a maximum weighted matching problem.
Max-product BP can solve assignment problems optimally, while convergence in general matching problems depends on a unique integral optimum of the LP relaxation.
The paper instead computes marginal probabilities on the same bipartite model, with counting matchings as a special equal-weight case.
Its convergence proof is related to the cavity method and treats a weighted matching problem on a restricted bipartite graph class.
For similar perfect-matching models, prior work parameterized the Bethe free energy by marginal probabilities and established convexity and feasibility.

III. BELIEF PROPAGATION DATA ASSOCIATION

The data-association BP formulation uses redundant target-to-measurement and measurement-to-target variables in a bipartite graphical model. Simplified updates reduce computation, after which the paper proves convergence and bounds iterations.

The BP update equations are transformed into an equivalent form that reduces computational complexity from O(n^3) to O(n_tm_t).
The formulation represents target and measurement associations with paired random variables whose values identify hypothesized counterparts or null associations.
The simplified updates support a convergence proof, a bound on required iterations, and a practical stopping criterion.

A. Formulation

The paper formulates data association as a bipartite graphical model linking target and measurement association variables. Belief propagation alternates message updates between the two variable sets, with a simplified implementation reducing per-iteration computation.

A. Formulation: The model is bipartite, connecting every target association variable to every measurement association variable.
A. Formulation: BP alternates two half-iterations between messages from target variables to measurement variables and vice versa.
A. Formulation: The formulation specifies message-update equations after omitting the time index from the association variables.
A. Formulation: Naive implementation has O(n_t^3) complexity per iteration because each message carries vectors over the opposite variable set.
B. Simplified algorithm: Each message contains only two distinct values, corresponding to whether the associated target or measurement index matches.
B. Simplified algorithm: Renormalizing by one message value converts the messages to scalar representations without changing their information.
B. Simplified algorithm: The simplified scalar updates use sums over all nonzero indices other than the current target or measurement index.
B. Simplified algorithm: After convergence, the scalar messages produce approximate marginal association probabilities, with an O(n_t m_t) Matlab implementation per iteration.

C. Proof of convergence

The convergence proof shows that the alternating BP updates are contractions despite the model's infinite dynamic range. Because the graph is bipartite, contracting each half-update establishes convergence of their compound operation to an initialization-independent stationary point.

Unlike standard dynamic-range analyses, the proof applies despite the association factor having infinite dynamic range.
The contraction arguments handle zero messages by noting that zeros correspond to zero association factors and remain zero under subsequent updates.
The proof uses a logarithmic message distance metric whose triangle inequality is established explicitly.
The update maps g and h are each contractions with factor α(¯L, W*) on bounded message domains.
The assumptions used in the contraction lemmas are guaranteed for messages produced by the corresponding BP updates.
Theorem 1 states that loopy BP converges to the same stationary point regardless of initialization.
Bipartite structure lets the proof compose the alternating g and h contractions into a contraction for g(h(·)).

D. Bound on complexity

The complexity analysis separates approximation error from iteration deviation and derives guarantees for how many iterations are needed for beliefs to approach their converged values. A numerical corollary tightens the conservative closed-form bound by exploiting improving contraction factors.

The analysis distinguishes error from deviation: error compares converged BP beliefs with the exact solution, while deviation compares finite-iteration beliefs with converged beliefs.
Message deviation bounded by ϵ implies belief deviation at most δ(ϵ) = exp(2ϵ) − 1 ≈ 2ϵ for small ϵ.
Theorem 2 gives a closed-form iteration condition guaranteeing belief deviation no greater than ϵ from initialization ν_j→i,0 = 1.
The bound combines contraction factors from the two alternating half-iterations and depends on W* and W ∗.
The closed-form analysis is conservative because it holds the contraction factor at its initial worst-case value.
Corollary 1 provides a tighter computable bound by reducing the contraction factor as iterations approach the optimal solution.
For δ = 10−3, the computable bound is approximated by cW*log log W*, whereas the closed-form bound is approximated by c′W*log W*.

E. Interpretation of complexity

The convergence parameter W* reflects measurement intensity around predicted track measurements and therefore depends on clutter, detection and existence probabilities, and target spacing. Its practical effect can differ from conservative offline iteration guarantees.

The expected W_i is interpreted as measurement intensity in the vicinity of a track's predicted measurement distribution.
W_i decreases as false-alarm intensity increases, with smaller reductions when false alarms already dominate measurement intensity.
W_i decreases as target existence and detection probabilities decrease, while increasing rapidly as those probabilities approach unity.
W_i increases when targets become closely spaced because multiple targets contribute to the measurement intensity near the track of interest.
Improved measurement accuracy aids convergence when it separates targets, but can increase W_i and convergence time when targets remain unresolved.

F. Stopping criterion

The stopping analysis bounds deviation from the converged messages and supports convergence checks based on successive message iterates, with an analogous guarantee for alternate messages.

F. Stopping criterion: The analysis bounds the distance between iteration-k messages and the converged messages using a contraction factor and the initial-iterate deviation.The bound is expressed in terms of α(ϵ, W∗), the convergence threshold ϵ, and the distance between successive message vectors.
F. Stopping criterion: The proof obtains geometric decay of successive message differences from the contraction property.For k′ ≥ k, the difference is bounded by α^(k′−k)ϵ under the theorem’s assumption.
F. Stopping criterion: A similar convergence guarantee applies to the alternate messages ν.

G. Algorithm

The BP algorithm computes approximate marginal association beliefs from thresholded single-target weights, while exploiting the bipartite graphical formulation and convergence results.

G. Algorithm: Convergence results from Lemma 4 and Theorem 3 are incorporated into the algorithm’s convergence test.Checks are performed every N iterations, with suggested values from 5 to 20, to reduce computational overhead.
G. Algorithm: BP computes approximate marginal association probabilities, or beliefs, from track and measurement association weights.The algorithm requires the numbers of tracks and measurements, single-target weights ψ_i(j), a convergence criterion, and an iteration interval N.
G. Algorithm: The junction-tree alternative merges variables into hyper-nodes to convert a cyclic graph into a tree for exact inference, but its complexity can grow exponentially.
G. Algorithm: The junction-tree formulation uses a simpler equivalent graph because redundant target and measurement association variables increase the exact-inference variable count.
G. Algorithm: Thresholding node potentials to zero for infeasible associations creates sparsity exploited by the junction-tree algorithm.The bipartite formulation is reported to outperform direct BP on the cyclic graph in both accuracy and convergence.

B. Correlation decay

The correlation-decay approach truncates an exact recursion to obtain bounded error with polynomial complexity under bounded-connectivity and bounded-weight conditions, and is compared experimentally with BP.

B. Correlation decay: The correlation-decay method uses a recursion over remaining tracks and measurements, limited to a maximum number of recursion steps t.The recursion is exact when it never revisits nodes, but then has exponential complexity.
B. Correlation decay: Bounded error and polynomial complexity are possible as graph size grows when maximum connectivity and maximum single-target association weight remain constant.
B. Correlation decay: Experiments compare the correlation-decay algorithm with the proposed BP method using marginal-estimate error and computation time.The evaluation averages the largest marginal-distribution difference over Monte Carlo trials and targets.

A. Comparison algorithms

The experiments compare BP with LMIPDA, BAA, junction tree, MCMCDA, and correlation decay across accuracy, computation time, and convergence behavior. BP offers a favorable accuracy–computation trade-off, while exact or sampling-based alternatives can be substantially more expensive.

Accuracy and computation: BP achieves average marginal errors of 0.015 or less in most cases, rising to 0.02–0.04 for high Pd or low measurement noise.These high-SNR cases correspond to Pd = 0.9 and r = 0.1; accuracy shows little deterioration as target count increases in large-scale problems.
Accuracy and computation: BP reduces errors by a factor of ten in most cases relative to LMIPDA and BAA, while costing only a few times more computationally.BP averages fractions of a millisecond in six-target problems and a little over a millisecond in 90- and 100-target problems.
Accuracy and computation: Junction tree is more accurate than BP with thresholds of 0.01 or 0.001, but requires 2–4 orders of magnitude more computation and often exceeds memory limits.With threshold 0.1, junction-tree error is globally worse than BP and computation is 1–2 orders of magnitude higher; 9×9 and 10×10 experiments were not completed.
Accuracy and computation: MCMCDA is generally comparable to BP with 10^5 iterations in six-target cases, but degrades with larger target counts and has 2–4 orders of magnitude higher complexity.In larger cases, BP is similar to or better than MCMCDA with 10^6 iterations.
Accuracy and computation: BP generally outperforms correlation decay with t = 3 and t = 5, while the relative accuracy at t = 7 depends on target spacing.Correlation decay can be slightly faster in some cases, but is 2–3 orders of magnitude slower in many others and 4–5 orders slower in large-scale problems.
Convergence behavior: The convergence parameter W* is smallest for well-spaced targets and largest for closely spaced targets; an offline bound near 3000 iterations contrasted with a practical maximum of 87.The offline closed-form and computable bounds were therefore much looser than the online termination criterion.