Structured Determinantal Point Processes.

Alex Kulesza, Ben TaskarNeurIPS 2010 · OpenReview

Abstract: We present a novel probabilistic model for distributions over sets of structures -- for example, sets of sequences, trees, or graphs. The critical characteristic of our model is a preference for diversity: sets containing dissimilar structures are more likely. Our model is a marriage of structured probabilistic models, like Markov random fields and context free grammars, with determinantal point processes, which arise in quantum physics as models of particles with repulsive interactions. We extend the determinantal point process model to handle an exponentially-sized set of particles (structures) via a natural factorization of the model into parts. We show how this factorization leads to tractable algorithms for exact inference, including computing marginals, computing conditional probabilities, and sampling. Our algorithms exploit a novel polynomially-sized dual representation of determinantal point processes, and use message passing over a special semiring to compute relevant quantities. We illustrate the advantages of the model on tracking and articulated pose estimation problems.

Introduction

In many complex prediction tasks, such as multi-target tracking or articulated pose estimation, the goal is not simply to find the single most likely configuration, but to identify a set of high-quality, diverse solutions. Standard structured probabilistic models, such as Markov Random Fields (MRFs), excel at identifying individual high-probability structures. However, they struggle to model sets effectively; independent sampling from these models often results in redundant configurations that cluster around a single mode of the distribution.

Determinantal Point Processes (DPPs) offer a mathematical framework for modeling "repulsion," where sets of dissimilar items are assigned higher probabilities. While powerful, standard DPPs require a kernel matrix proportional to the number of possible items ($N$). In structured domains where items are sequences or trees, $N$ is exponential in the size of the structure, rendering standard DPP inference computationally intractable.

Methodology

This work introduces Structured Determinantal Point Processes (SDPPs), bridging the gap between structured models and DPPs through three primary innovations:

  1. Factorization: The model decomposes the "quality" of a structure and its "similarity" features into local parts, mirroring the clique-based decomposition used in graphical models.
  2. Dual Representation: A key mathematical insight is that the non-zero eigenvalues of a massive $N \times N$ matrix (where $N$ is the number of all possible structures) are identical to those of a much smaller $D \times D$ matrix, where $D$ is the dimension of the feature space. By working in this dual space, global set operations become computationally feasible.
  3. Second-Order Semiring Message Passing: To compute the $D \times D$ matrix without enumerating all $N$ structures, the authors employ an efficient dynamic programming approach. Using message passing over a specialized "second-order semiring," the necessary moments can be computed in $O(D^2 T)$ time for structures of length $T$.

Experiments and Results

The model was evaluated on two distinct tasks: synthetic motion tracking and articulated pose estimation.

Synthetic Motion Tracking

In a 1D simulation of particles moving over 50 time steps, the SDPP was tasked with identifying multiple distinct trajectories. Unlike independent sampling, which repeatedly selected the same high-probability path, the SDPP successfully captured multiple modes of the distribution, providing superior coverage of the underlying particle movements.

Sampled particle trajectories showing the diversity of SDPP (top) vs. independent sampling (bottom).

Articulated Pose Estimation

The model was also applied to a dataset of 73 frames from TV shows to identify the poses of multiple people. SDPPs were compared against independent sampling and standard Non-Maxima Suppression (NMS).

Quantitative performance on articulated pose estimation across different match radii.

As shown in the results, the SDPP significantly outperformed both baselines, particularly as the "match radius" (the tolerance for a correct detection) increased. The performance gain was primarily driven by a boost in recall, as the model was able to identify individuals that were previously missed due to their proximity to other detections.

Conclusion

SDPPs provide a principled, probabilistic alternative to heuristic methods like NMS for ensuring diversity in structured outputs. By leveraging a dual representation and efficient message passing, the model enables exact inference over exponentially large sets of structures. Future work may explore scaling to higher-dimensional feature spaces and learning quality and similarity parameters simultaneously from data.

Summary updated

Abstract

We present a novel probabilistic model for distributions over sets of structures -- for example, sets of sequences, trees, or graphs. The critical characteristic of our model is a preference for diversity: sets containing dissimilar structures are more likely. Our model is a marriage of structured probabilistic models, like Markov random fields and context free grammars, with determinantal point processes, which arise in quantum physics as models of particles with repulsive interactions. We extend the determinantal point process model to handle an exponentially-sized set of particles (structures) via a natural factorization of the model into parts. We show how this factorization leads to tractable algorithms for exact inference, including computing marginals, computing conditional probabilities, and sampling. Our algorithms exploit a novel polynomially-sized dual representation of determinantal point processes, and use message passing over a special semiring to compute relevant quantities. We illustrate the advantages of the model on tracking and articulated pose estimation problems.
BibTeX
@inproceedings{kulesza2010structured,
  author = {Alex Kulesza and Ben Taskar},
  title = {{Structured Determinantal Point Processes.}},
  booktitle = {NeurIPS},
  year = {2010},
  url = {https://openreview.net/forum?id=fco5pr5Opnm},
}
Figure