On the Convex Combination of Determinantal Point Processes

Tatsuya Matsuoka, Naoto Ohsaka, Akihiro Yabe
Proceedings of The 13th Asian Conference on Machine Learning, PMLR 157:158-173, 2021.

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 \emph{convex combinations of DPPs}. We provide upper and lower bounds for the number of DPPs required for \emph{exactly} expressing any probability distribution. For the \emph{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v157-matsuoka21a, title = {On the Convex Combination of Determinantal Point Processes}, author = {Matsuoka, Tatsuya and Ohsaka, Naoto and Yabe, Akihiro}, booktitle = {Proceedings of The 13th Asian Conference on Machine Learning}, pages = {158--173}, year = {2021}, editor = {Balasubramanian, Vineeth N. and Tsang, Ivor}, volume = {157}, series = {Proceedings of Machine Learning Research}, month = {17--19 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v157/matsuoka21a/matsuoka21a.pdf}, url = {https://proceedings.mlr.press/v157/matsuoka21a.html}, 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 \emph{convex combinations of DPPs}. We provide upper and lower bounds for the number of DPPs required for \emph{exactly} expressing any probability distribution. For the \emph{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.} }
Endnote
%0 Conference Paper %T On the Convex Combination of Determinantal Point Processes %A Tatsuya Matsuoka %A Naoto Ohsaka %A Akihiro Yabe %B Proceedings of The 13th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Vineeth N. Balasubramanian %E Ivor Tsang %F pmlr-v157-matsuoka21a %I PMLR %P 158--173 %U https://proceedings.mlr.press/v157/matsuoka21a.html %V 157 %X 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 \emph{convex combinations of DPPs}. We provide upper and lower bounds for the number of DPPs required for \emph{exactly} expressing any probability distribution. For the \emph{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.
APA
Matsuoka, T., Ohsaka, N. & Yabe, A.. (2021). On the Convex Combination of Determinantal Point Processes. Proceedings of The 13th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 157:158-173 Available from https://proceedings.mlr.press/v157/matsuoka21a.html.

Related Material