Learning the Parameters of Determinantal Point Process Kernels

Introduction

A determinantal point process (DPP) provides a distribution over configurations of points. The defining characteristic of the DPP is that it is a repulsive point process, which makes it useful for modeling diversity. Recently, DPPs have played an increasingly important role in machine learning and statistics with applications both in the discrete setting—where they are used as a diverse subset selection method [kulesza2010structured, kulesza2011k, gillenwater2012discovering, affandi2012markov, snoek2013determinantal, Affandi:AISTATS2013]— and in the continuous setting for generating point configurations that tend to be spread out[affandi2013approximate, zou2012priors].

Building on work of kulesza2010structured, it is intuitive to decompose the kernel $L$ as

One of the remarkable aspects of DPPs is that they offer efficient algorithms for inference, including computing the marginal and conditional probabilities [kulesza2012determinantal], sampling [hough2006determinantal, kulesza2010structured, Affandi:AISTATS2013, affandi2013approximate], and restricting to fixed-sized point configurations ($k$-DPPs)[kulesza2011k]. However, an important component of DPP modeling, learning the DPP kernel parameters, is still considered a difficult, open problem. Even in the discrete $\Omega$ setting, DPP kernel learning has been conjectured to be NP-hard [kulesza2012determinantal]. Intuitively, the issue arises from the fact that in seeking to maximize the log-likelihood of Eq. (1), the numerator yields a concave log-determinant term whereas the normalizer contributes a convex term, leading to a non-convex objective. This non-convexity holds even under various simplifying assumptions on the form of $L$.

In Sec. 2, we review DPPs and their fixed-sized counterpart ($k$-DPPs). We then explore likelihood maximization algorithms for learning DPP and $k$-DPP kernels. After examining the shortcomings of the MLE approach, we propose a set of techniques for Bayesian posterior inference of the kernel parameters in Sec. 3, and explore modifications to accommodate learning large-scale and continuous DPPs. In Sec. LABEL:sec:moments, we derive a set of DPP moments assuming a known kernel eigenstructure and explore using these moments as a model-checking technique. In low-dimensional settings, we can use a method of moments approach to learn the kernel parameters via numerical techniques. Finally, we test our methods on both simulated and real-world data. Specifically, in Sec. LABEL:sec:applications we use DPP learning to study the progression of diabetic neuropathy based on spatial distribution of nerve fibers and also to study human perception of diversity of images.

Background

In many applications, we are instead interested in the probability distribution which gives positive mass only to subsets of a fixed size, $k$. In these cases, we consider fixed-sized DPPs (or $k$-DPPs) with probability distribution on sets $A$ of cardinality $k$ given by

where ${\lambda_{1},\ldots,\lambda_{N}}$ are eigenvalues of $L$ and $e_{k}(\lambda_{1},\ldots,\lambda_{N})$ is the $k$th elementary symmetric polynomial [kulesza2011k]. Note that $e_{k}(\lambda_{1},\ldots,\lambda_{N})$ can be efficiently computed using recursion [kulesza2012determinantal].

2 Continuous DPPs/k𝑘k-DPPs

where $\lambda_{1},\lambda_{2},\ldots$ are eigenvalues of the operator $L$.

The $k$-DPP also extends to the continuous case with

where ${\lambda_{1:\infty}=(\lambda_{1},\lambda_{2},\ldots)}$.

In contrast to the discrete case, the eigenvalues $\lambda_{i}$ for continuous DPP kernels are generally unknown; exceptions include a few kernels such as the exponentiated quadratic. However, affandi2013approximate showed that a low-rank approximation to $L$ can be used to recover an approximation to a finite truncation of the eigenvalues representing an important part of the eigenspectrum. This enables us to approximate the normalizing constants of both DPPs and $k$-DPPs, and will play a crucial role in our proposed methods of Sec. LABEL:sec:largescale.

Learning Parametric DPPs

Assume that we are given a training set consisting of samples $A^{1},A^{2},\ldots,A^{T}$, and that we model these data using a DPP/$k$-DPP with parametric kernel

with parameters $\Theta$. We denote the associated kernel matrix for a set $A^{t}$ by $L_{A^{t}}(\Theta)$ and the full kernel matrix/operator by $L(\Theta)$. Likewise, we denote the kernel eigenvalues by $\lambda_{i}(\Theta)$. In this section, we explore various methods for DPP/$k$-DPP learning.

To learn the parameters $\Theta$ of a discrete DPP model, we can maximize the log-likelihood

lavancier2012statistical suggests that the Nelder-Mead simplex algorithm [nelder1965simplex] can be used to maximize $\mathcal{L}(\Theta)$. This method is based on evaluating the objective function at the vertices of a simplex, then iteratively shrinking the simplex towards an optimal point. While this method is convenient since it does not require explicit knowledge of derivates of $\mathcal{L}(\Theta)$, it is regarded as a heuristic search method and is known for its failure to necessarily converge to a stationary point [mckinnon1998convergence].

Gradient ascent and stochastic gradient ascent provide more attractive approaches because of their theoretical guarantees, but require knowledge of the gradient of $\mathcal{L}(\Theta)$. In the discrete DPP setting, this gradient can be computed straightforwardly, and we provide examples for discrete Gaussian and polynomial kernels in the Supplementary Material. We note, however, that these methods are still susceptible to convergence to local optima due to the non-convex likelihood landscape.

The log likelihood of the $k$-DPP kernel parameter is

which presents an addition complication due to needing a sum over ${n\choose k}$ terms in the gradient.

For continuous DPPs/$k$-DPPs, gradient ascent can only be used in cases where the exact eigendecomposition of the kernel operator is known with a differentiable form for the eigenvalues (see Eq. (5)). This restricts the applicability of gradient-based likelihood maximization to a limited set of scenarios, such as a DPP with Gaussian quality function and similarity kernel. Furthermore, for kernel operators with infinite rank (such as the Gaussian), an explicit truncation has to be made, resulting in an approximate gradient of $\mathcal{L}(\Theta)$. Unfortunately, such approximate gradients are not unbiased estimates of the true gradient, so the theory associated with attractive stochastic gradient based approaches does not hold.

2 Bayesian Learning for Discrete DPPs

Instead of optimizing the likelihood to get an MLE, here we propose a Bayesian approach to that samples from the posterior distribution over kernel parameters:

Here, $\mathcal{P}(\Theta)$ is the prior on $\Theta$. Since neither Eq. (10) nor Eq. (11) yield a closed form posterior, we resort to approximate techniques based on Markov chain Monte Carlo (MCMC). We highlight two techniques: random-walk Metropolis-Hastings (MH) and slice sampling, although other MCMC methods can be employed without loss of generality.