A Complete Variational Tracker
We introduce a novel probabilistic tracking algorithm that incorporates combinatorial data association constraints and model-based track management using variational Bayes. We use a Bethe entropy approximation to incorporate data association constraints that are often ignored in previous probabilistic tracking algorithms. Noteworthy aspects of our method include a model-based mechanism to replace heuristic logic typically used to initiate and destroy tracks, and an assignment posterior with linear computation cost in window length as opposed to the exponential scaling of previous MAP-based approaches. We demonstrate the applicability of our method on radar tracking and computer vision problems.
The field of tracking is broad and possesses many applications, particularly in radar/sonar [1], robotics [14], and computer vision [3]. Consider the following problem: A radar is tracking a flying object, referred to as a target, using measurements of range, bearing, and elevation; it may also have Doppler measurements of radial velocity. We would like to construct a track which estimates the trajectory of the object over time. The Kalman filter [16], or a more general state space model, is used to filter out measurement errors. The key difference between tracking and filtering is the presence of clutter (noise measurements) and missed detections of true objects. We must determine which measurement to "plug in" to the filter before applying it; this is known as data association. Additionally complicating the situation is that we may be in a multi-target tracking scenario in which there are multiple objects to track and we do not know which measurement originated from which object.
There is a large body of work on tracking algorithms given its standing as a long-posed and important problem. Algorithms vary primarily on their approach to data association. The dominant approach uses a sliding window MAP estimate of the measurement-to-track assignment, in particular the multiple hypothesis tracker (MHT) [1]. In the standard MHT, at every frame the algorithm finds the most likely matching of measurements to tracks, in the form of an assignment matrix, under a one-to-one constraint (see Figure 1). One track can only result in one measurement, and vice versa, which we refer to as framing constraints. As is typical in MAP estimation, once an assignment is determined, the filters are updated and the tracker proceeds as if these assignments were known to be correct. The one-to-one constraint makes MAP estimation a bipartite matching task where algorithms exist to solve it exactly in polynomial time in the number of tracks N T [15]. However, the multi-frame MHT finds the joint MAP assignment over multiple frames, in which case the assignment problem is known to be NP-hard, although good approximate solvers exist [20]. 
The field of tracking is broad and possesses many applications, particularly in radar/sonar [1], robotics [14], and computer vision [3]. Consider the following problem: A radar is tracking a flying object, referred to as a target, using measurements of range, bearing, and elevation; it may also have Doppler measurements of radial velocity. We would like to construct a track which estimates the trajectory of the object over time. The Kalman filter [16], or a more general state space model, is used to filter out measurement errors. The key difference between tracking and filtering is the presence of clutter (noise measurements) and missed detections of true objects. We must determine which measurement to "plug in" to the filter before applying it; this is known as data association. Additionally complicating the situation is that we may be in a multi-target tracking scenario in which there are multiple objects to track and we do not know which measurement originated from which object.
There is a large body of work on tracking algorithms given its standing as a long-posed and important problem. Algorithms vary primarily on their approach to data association. The dominant approach uses a sliding window MAP estimate of the measurement-to-track assignment, in particular the multiple hypothesis tracker (MHT) [1]. In the standard MHT, at every frame the algorithm finds the most likely matching of measurements to tracks, in the form of an assignment matrix, under a one-to-one constraint (see Figure 1). One track can only result in one measurement, and vice versa, which we refer to as framing constraints. As is typical in MAP estimation, once an assignment is determined, the filters are updated and the tracker proceeds as if these assignments were known to be correct. The one-to-one constraint makes MAP estimation a bipartite matching task where algorithms exist to solve it exactly in polynomial time in the number of tracks N T [15]. However, the multi-frame MHT finds the joint MAP assignment over multiple frames, in which case the assignment problem is known to be NP-hard, although good approximate solvers exist [20]. Despite the complexity of the MHT, it only finds a sliding window MAP estimate of measurementto-track assignments. If a clutter measurement is by chance associated with a track for the duration of a window then the tracker will assume with certainty that the measurement originated from that track, and never reconsider despite all future evidence to the contrary. If multiple clutter (or otherwise incorrect) measurements are associated with a track, then it may veer "off into space" and result in spurious tracks. Likewise, an endemic problem in tracking is the issue of track swaps, where two trajectories can cross and get mixed up as shown in Figure 1. Alternatives to the MAP approach include the probabilistic MHT (PMHT) [9,Ch. 4] and probabilistic data association (PDA). However, the PMHT drops the one-to-one constraint in data association and the PDA only allows for a single target. This led to the development of the joint PDA (JPDA) algorithm for multiple targets, which utilizes heuristic calculations of the assignment weights and does not scale to multiple frame assignment. Particle filter implementations of the JPDA have tried to alleviate these issues, but they have not been adopted into real-time systems due to their inefficiency and lack of robustness. The probability hypothesis density (PHD) filter [19] addresses many of these issues, but only estimates the intensity of objects and does not model full trajectories; this is undesirable since the identity of an object is required for many applications including the examples in this paper.
Lázaro-Gredilla et al. [18] made the first attempt at a variational Bayes (VB) tracker. In their approach every trajectory follows a Gaussian process (GP); measurements are thus modeled by a mixture of GPs. We develop additional VB machinery to retain the framing constraints, which are dropped in Lázaro-Gredilla et al. [18] despite being viewed as important in many systems. Secondly, our algorithm utilizes a state space approach (e.g. Kalman filters) to model tracks, providing linear rather than cubic time complexity in track length. Hartikainen and Särkkä [11] showed by an equivalence that there is little loss of modeling flexibility by taking a state space approach over GPs.
Most novel tracking algorithms neglect the critical issue of track management. Many tracking algorithms unrealistically assume that the number of tracks N T is known a priori and fixed. Additional "wrapper logic" is placed around the trackers to initiate and destroy tracks. This logic involves many heuristics such as M -of-N logic [1,Ch. 3]. Our method replaces these heuristics in a model-based manner to make significant performance gains. We call our method a complete variational tracker as it simultaneously does inference for track management, data association, and state estimation.
The outline of the paper is as follows: We first describe the full joint probability distribution of the tracking problem in Section 1. This includes how to solve the track management problem by augmenting tracks with an active/dormant state to address the issue of an unknown number of tracks. By studying the full joint we develop a new conjugate prior on assignment matrices in Section 2. Using this new formulation we develop a variational algorithm for estimating the measurement-totrack assignments and track states in Section 3. To retain the framing constraints and efficiently scale in tracks and measurements, we modify the variational lower bound in Section 4 using a Bethe entropy approximation. This results in a loopy belief propagation (BP) algorithm being used as a subroutine in our method. In Sections 5-6 we show the improvements our method makes on a difficult radar tracking example and a real data computer vision problem in sports.
Our paper presents the following novel contributions: First, we develop the first efficient deterministic approximate inference algorithm for solving the full tracking problem, which includes the framing constraints and track management. The most important observation is that the VB assignment posterior has an induced factorization over time with regard to assignment matrices. Therefore, the computational cost of our variational approach is linear in window length as opposed to the exponential cost of the MAP approach. The most astounding aspect is that by introducing a weaker approximation (VB factorization vs MAP) we lower the computational cost from exponential to linear; this is a truly rare and noteworthy example. Second, in the process, we develop new approximate inference methods on assignment matrices and a new conjugate assignment prior (CAP). We believe these methods have much larger applicability beyond our current tracking algorithm. Third, we develop a process to handle the track management problem in a model-based way.
This paper describes a probabilistic model-based approach to tracking.  The probabilistic model includes important aspects of the tracking problem (namely track management) that are often left to external heuristics and thus not included in the joint probabilistic inference (hence the term "complete" in the paper's title).  In addition, by performing a richer kind of Bayesian inference (namely a mean field method with conjugate exponential family pairs as opposed to e.g. a MAP approximation) the proposed method offers a more complete representation of posterior uncertainty, improving performance and avoiding some (apparently) common tracker failure modes.The model's construction includes Markov structure (namely in the (conditionally) linear dynamical systems (X_t,Y_t) and the Markov structure on the meta-states (S_t), shown in Figure 1) that allows the corresponding mean field updates to be carried out efficiently, requiring time only linear in the sequence (or sliding window) length as opposed to the cubic complexity in a recent Gaussian Process-based method (though at the cost of a somewhat less rich class of dynamical models for the tracks themselves).  Finally, to make efficient another update required in the mean field algorithm, this paper introduces (or at least clarifies, c.f. line 117) a conjugate assignment prior (CAP) on the assignment matrices A and shows that, while some mean field computations with such variational factors are likely intractable to perform exactly (lines 193-201), a loopy belief propagation update (Section 4) can be used to estimate the expectation required to perform the mean field updates (and, possibly, to compute a lower bound on the intended mean field variational lower bound on the model evidence, c.f. 288-290 and 323).  The CAP's definition is naturally related to the prior used in corresponding MAP methods (Section 2) and the choice of method for approximating the expectation is naturally related to other variational approximations (namely the Bethe entropy approximation) and to the use of similar belief propagation algorithms for the matrix permanent problem.This is a high-quality paper. The writing is extremely clear and the explanations are very thorough.  The problem, model, and approximate inference algorithms are very well motivated, and the choices made all sound reasonable.I'm not familiar with the literature on trackers, and so my estimates of the originality and significance of this work may be both noisy and biased upwards (affecting my confidence score below).  That also means I'm not in a good position to be critical of the experiments, which certainly look reasonable from my naive perspective.  However, given the summary of prior work provided in Section 1, this work sounds like a clear step forward, with originality both in its more thorough Bayesian approach as well as its model and inference algorithm choices, which involve nice (if not "major") technical contributions.  It may not be a "major impact" paper (I wish the impact score weren't binary...) in that its direct impact may be limited to work on trackers.  But it may have a significant impact for those interested in Bayesian tracking methods (hard for me to judge) and, perhaps more importantly, I think many others in the broader NIPS community would enjoy reading this paper as much as I did.Here are some miscellaneous comments and questions:- I don't like using "vec" around line 175; instead, one can just define an inner product on matrices using trace.- As a personal pet peeve, "variatonal Bayes" is somewhat less descriptive than "a mean field variational approximation to the posterior". It might be nice to include the phrase "mean field" at least once in the paper.- Line 42, is "a complex discrete optimization task" just bipartite matching?  If so, it might be nice to name.- Around 210-212, you might consider saying "local and global" or "extensive and intensive" since those phrases are sometimes used in the literature.- Around 164-165, the phrase "we must to compute" probably wasn't meant to include the word "to".- On lines 96-99 and again on 426-428 you say it's surprising that by using mean field instead of MAP the (update) complexity is reduced from exponential to linear. However, since MAP can in many cases be written as mean field where some factors are constrained to be delta functions, it's not clear to me where the gain is coming from. On lines 44-45 you imply the exponential complexity comes from considering multiple frames; is the reduction in complexity really from the imposed Markov structure (namely on the s variables) which makes the assignment matrices conditionally iid? If so, it's not very surprising. If not, anything you can say to clarify the issue would be appreciated!