- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper is addressing probabilistic combinatorial optimisation, in which we need to assign the values of one variable (e.g. measurements) to the values of another (e.g. sensors) with a probability. Each assignment is assumed to have a score, and so we want to find the probability of each assignment, (a Gibbs distribution). The issue is that if we want to find , we have to marginalise over all combinations with that assignment of , and the number of possible assignments scale as , so this quickly becomes intractable. As a result, despite the optimal allocation being reasonably easy to find (i.e. select the assignments with the highest score), determining is difficult.
Perturb & MAP's solution is to take the optimal set of scores (easy to find), add random noise and find the resulting best assignments. This process is repeated thousands of times, each output of which is treated as a sample. However, after sampling, the assignments no longer follow a Gibbs distribution. This paper derives the assignments' distribution after sampling, and shows how to correct them to be Gibbs distributed.
Critical strengths
I've been thinking carefully about this, but have struggled to identify concrete strengths supporting acceptance. The technical aspects of the work are rigorous, but until my concerns about motivation are resolved, I'm not convinced they're significant enough to warrant acceptance.
Critical weaknesses
There are 2 key issues I would need to see resolved to change my score:
1. Clarity
This paper is exceptionally difficult to read - it is littered with technical jargon that's very difficult to interpret and has little intuitive explanation. There is far far too much assumed knowledge of probabilistic combinatorial optimisation, Perturb-and-MAP and Gumbel-max. These things should be explained much more carefully. Accordingly, it takes a lot of additional reading to understand the problem being solved, and as far as I could tell no motivated is provided at all. The introduction needs to make it substantially clearer what probabilistic combinatorial optimisation is, why it's important, common areas where you might see these problems, how Perturb-and-MAP solves them, limitations of Perturb-and-MAP, and where this paper's contribution lies.
2. Motivation
The paper leaps into technical jargon from the first sentence of the abstract without motivating the problem at all. I could not understand why probabilistic combinatorial optimisation is important, common approaches to solving it, why perturb-and-map is the norm and what its limitations are. As a result, it's very difficult to interpret the technical significance of the work. More than this, it appears to me to solve a problem that is reasonably inconsequential. More detail on this is provided in the text below.
Questions for authors
I thank the authors for the work they've put into the paper, and while I appreciate my review scores are low, I have tried to offer the most honest and thorough assessment of their work of which I am capable. Aside from clarity, my key issue with this work was its motivation, which has left me with a couple of clarifying questions:
1. When is probabilistic combinatorial optimisation important?
What are real-world scenarios where probabilistic combinatorial optimisation is important? The example mentioned in Section 6 is multi-target tracking, which is extraordinarily broad. In computer vision, where the sensor is a camera, this optimisation isn't difficult at all - being able to maintain tracks between successive images is largely solved and reasonably inconsequential. As a result, I don't understand why this is a problem worth pursuing, and moreover, if it's straightforward to find the optimal allocation - when is it important to know the allocation uncertainty?
2. Why can't we just use Perturb-and-MAP?
My understanding is that modern approaches to combinatorial optimisation allocate a score to each assignment, say that the true distribution must follow a Gibbs distribution (), and use Perturb-and-MAP to estimate assignment probabilities. This work is then showing that the result after Perturb-and-MAP does not follow a Gibbs distribution, and therefore proves the corrections required to estimate a Gibbs distribution. However I don't understand why we need these to follow a Gibbs distribution. I can understand that the perturb-and-MAP sampling technique might lead to a slightly incorrect distribution, but surely in the real world all score metrics will always be imperfect and noisy, so why can we be so confident that the true probabilities are proportional to ? Surely instead, this is just an imperfect model we use to make a good allocation decision, and if so then why does the error introduced by perturb-and-MAP need correcting - why can't we just use the results from perturb-and-MAP? This question is the reason for my "Soundness" score of 2, as it is not clearly explained in the paper.
3 comments
Response to Reviewer qoMi (2/3)
Question 1. When the uncertainty of the allocation matters. It matters when the best allocation is likely to be wrong in part and a wrong pairing has consequences, and tracking shows both. A sonar that follows several nearby targets keeps a track for each of them, an estimate of its motion. Every scan returns a set of measurements, which may include false alarms, called clutter, and the sonar cannot tell which measurement came from which target. An assignment pairs each track with a different measurement or marks it as missed. The sensor model gives every assignment a score that combines how well the measurements fit the tracks with how likely the misses and false alarms are, and given the scan an assignment with score has posterior probability proportional to .
The best assignment is easy to find, but that does not make it likely to be correct. On our simulated random scenes, with 20 targets that are close together compared with the uncertainty of their predicted positions, all detected and without clutter, a measurement that the best assignment gives to a track belongs to that track with posterior probability 0.18 on average (Appendix F.3). In expectation, about 16 of its 20 pairings are therefore wrong. A tracker that commits to this assignment updates those tracks with the measurements of other targets, which pulls them toward the wrong targets. Probabilistic data association was introduced for this reason. Instead of committing to one assignment, it updates every track with every measurement, weighted by the probability that the measurement belongs to that track (Bar-Shalom and Tse, 1975), and Fortmann et al. (1983) used it to track multiple targets by sonar. Current trackers approximate the same probabilities by belief propagation (Williams and Lau, 2014). The probabilities of the pairings, which express the uncertainty of the allocation, are thus what such a tracker needs at every scan.
How hard the association is depends on the sensor. A radar or a sonar returns positions, and when targets are close together compared with the measurement noise, one measurement can fit several tracks. A camera also records what an object looks like, so the same object can be recognized in the next frame, and this often settles the association, as you note. When the objects look alike, trackers have to rely more on position and motion, as with a radar. Two recent benchmarks show this case. In DanceTrack the people look alike and move in diverse ways, and state-of-the-art trackers perform markedly worse on it than on earlier benchmarks (Sun et al., CVPR 2022). On the sports benchmark SportsMOT the authors identify association as the key challenge (Cui et al., ICCV 2023). A camera can thus leave several plausible assignments as well, and when the probability is spread over them, even the best one is unlikely to be correct.
Response to Reviewer qoMi (3/3)
Question 2. Can we just use perturb-and-MAP? If only the best allocation were needed, the Hungarian algorithm would give it and no sampling would be required. Perturb-and-MAP is used when probabilities are needed, and the frequencies of its samples converge to the probabilities of its own distribution. What follows depends on what one takes as the model, and your question raises both possibilities.
Suppose first that you want the probabilities that your scores specify, as a tracker does. Its sensor model may be imperfect, and it still determines how much weight each measurement gets in the update. Plain perturb-and-MAP estimates the probabilities of its own distribution instead, however many samples are drawn, and we prove how the two differ. With two tracks and two measurements there are two assignments. When one of them scores 1 more than the other, the model gives it probability 0.73 and perturb-and-MAP with standard Gumbel noise gives it 0.66 (Section 2.3). In general, for tracks and measurements with equal scores, the probabilities of perturb-and-MAP respond to a small change of the scores at times the rate of the model (Theorem 3). This factor depends on the number of targets, so one fixed recalibration of the scores does not absorb it. Scaling the noise by it for each matches the two rates at equal scores and leaves a difference elsewhere. On scenes with 16 to 30 closely spaced targets, the tight formations of Section 6, the pairing probabilities estimated from perturb-and-MAP samples have a mean error of about 0.03 to 0.08 on the ambiguous pairings even with this scaling, more than ten times the error of our reweighted estimator with as many samples (Table F.3). And by Theorem 1, once there are two or more tracks and three or more measurements, no choice of noise makes the samples follow the Gibbs distribution at every score vector. Our weights, built from the formula of Theorem 2, turn the same samples into estimates that converge to the probabilities of the model.
Suppose instead that one takes the distribution of the perturb-and-MAP samples itself as the model, as your question suggests and as Tarlow et al. (2012) and Berthet et al. (2020) do. No correction is then needed, and the sample frequencies estimate the probabilities that one has chosen. To fit the scores of such a model to data by maximum likelihood, however, one needs the probability that the sampler returns each observed assignment. For assignments under independent Gumbel noise this probability had not been computed before, and Theorem 2 gives the first explicit formula for it.
The distribution of the samples thus gives the weights in the first case and the likelihood in the second. The revised introduction now states where the Gibbs distribution comes from and why the difference from it persists.
We hope that the revised paper and these answers make clear which problem the paper solves and why it matters, and we would be glad to revise any passage that you still find hard to follow. Thank you again for the effort and expertise that you have devoted to our work in this review. Your comments on clarity and motivation have made the paper better.
Response to Reviewer qoMi (1/3)
Thank you for your honest and careful review, and for stating precisely what would have to change. We agree that the submitted version had shortcomings in the clarity of its writing and presentation, and that it did not motivate its problem clearly. We have substantially rewritten the abstract and the introduction and added a pen-and-paper example to the main text. The theorems are unchanged in content apart from one added case, and new and substantively changed text is marked in red in the revised paper.
Clarity. The revised introduction follows the order that you propose: the problem, where it arises and why it matters, how perturb-and-MAP addresses it and where it falls short, and what the paper contributes. It explains the Gibbs distribution, perturb-and-MAP and the Gumbel-max trick where they first appear, and the new Section 2.3 works out a small pen-and-paper example with two rows and two columns, that is, two tracks and two measurements. The paragraphs below give the motivation along the lines of the revised introduction.
Motivation. Many models need probabilities over whole structures, such as a subset of k out of n items, a ranking, a spanning tree or a matching of two sets, which we call an assignment. A structure with score s, the sum of the scores of its elements, has probability proportional to es. This is the Gibbs distribution, and the problem of the paper is to sample from it and to compute probabilities under it. In machine learning the structure is a hidden part of a model, such as a latent subset, permutation or matching (Niepert et al., 2021; Mena et al., 2018; Linderman et al., 2018), and training on observed structures uses these probabilities, which make up the gradient of the log-likelihood (Berthet et al., 2020). In survey sampling, k units are drawn from a population with unequal probabilities, for example firms in proportion to their size. A classical design for this, the rejective sampling of Hájek (1964), is the Gibbs distribution on the subsets of size k.
Tracking is a third case. A tracker that follows several nearby targets receives a set of position measurements at every scan and does not know which measurement belongs to which target. It can find the best assignment of measurements to targets, but if it commits to this assignment and part of it is wrong, it updates a track with the measurement of another target. It needs the probability that a given measurement belongs to a given target, by which to weight the measurements. Question 1 below develops this example.
In all these cases the best structure is easy to find, by sorting, by a greedy algorithm or by the Hungarian algorithm. Probabilities are harder, because the probability of an element is a sum over all structures that contain it. With n tracks and n measurements the normalizing sum runs over n! assignments and is #P-hard to compute.
Perturb-and-MAP turns the easy problem into a sampler. It adds random noise to the score of every element and returns the best structure for the perturbed scores, so one sample takes one run of the optimization algorithm. For a single choice among several options with independent standard Gumbel noise this is the Gumbel-max trick, whose samples follow the Gibbs distribution exactly. Independent Gumbel noise on every whole structure would also be exact, but there can be exponentially many structures. Perturb-and-MAP puts the noise on the elements, so that the fast algorithm still applies, and its samples then follow a different distribution in general. Since its introduction for random fields in computer vision (Papandreou and Yuille, 2011), the method has been applied to subsets, permutations, assignments and other structures (Tarlow et al., 2012; Kool et al., 2019; Mena et al., 2018; Paulus et al., 2020; Berthet et al., 2020; Niepert et al., 2021). The distribution that its samples follow has been regarded as intractable (Papandreou and Yuille, 2011; Mena et al., 2018), so the difference from the Gibbs distribution was hard to quantify.
The paper quantifies this difference and shows how to correct for it. We prove that, apart from the simplest cases, no choice of noise makes the samples follow the Gibbs distribution for all scores. For assignments under independent Gumbel noise we give the distribution that the samples follow as an explicit formula. From this formula we obtain weights that turn the samples into estimates that converge to the probabilities under the Gibbs distribution. For the tracking task the weights give a new estimator of the pairing probabilities. On scenes with 30 closely spaced targets its mean error on the ambiguous pairings is 0.005. Belief propagation, an enumeration of the likeliest assignments and a Markov chain, the methods that trackers use, have about 5 to 18 times this error, the last two even with budgets one to three orders of magnitude larger than ours (Section 6).