On the Convex Combination of Determinantal Point Processes

Tatsuya Matsuoka (NEC Corporation)*; Naoto Ohsaka (NEC Corporation); Akihiro Yabe (Fanfare Inc.)
PMLR Page

Abstract

Determinantal point processes (DPPs) are attractive probabilistic models for expressing item quality and set diversity simultaneously. Although DPPs are widely-applicable to many subset selection tasks, there exist simple small-size probability distributions that any DPP cannot express. To overcome this drawback while keeping good properties of DPPs, in this paper we investigate the expressive power of convex combinations of DPPs. We provide upper and lower bounds for the number of DPPs required for exactly expressing any probability distribution. For the approximation error, we give an upper bound on the Kullback--Leibler divergence $n-\lfloor \log t\rfloor +\epsilon$ for any $\epsilon >0$ of approximate distribution from a given joint probability distribution, where $t$ is the number of DPPs. Our numerical simulation on an online retail dataset empirically verifies that a convex combination of only two DPPs can outperform a nonsymmetric DPP in terms of the Kullback--Leibler divergence. By combining a polynomial number of DPPs, we can express probability distributions induced by bounded-degree pseudo-Boolean functions, which include weighted coverage functions of bounded occurrence.