Nyström Approximation for Large-Scale Determinantal Processes

Raja Hafiz Affandi, Alex Kulesza, Emily Fox, Ben Taskar
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:85-98, 2013.

Abstract

Determinantal point processes (DPPs) are appealing models for subset selection problems where diversity is desired. They offer surprisingly efficient inference, including sampling in $O(N^3)$ time and $O(N^2)$ space, where $N$ is the number of base items. However, in some applications, $N$ may grow so large that sampling from a DPP becomes computationally infeasible. This is especially true in settings where the DPP kernel matrix cannot be represented by a linear decomposition of low-dimensional feature vectors. In these cases, we propose applying the Nystrom approximation to project the kernel matrix into a low-dimensional space. While theoretical guarantees for the Nystrom approximation in terms of standard matrix norms have been previously established, we are concerned with probabilistic measures, like total variation distance between the DPP generated by a kernel matrix and the one generated by its Nystrom approximation, that behave quite differently. In this paper we derive new error bounds for the Nystrom-approximated DPP and present empirical results to corroborate them. We then demonstrate the Nystrom-approximated DPP by applying it to a motion capture summarization task.

Cite this Paper

BibTeX
@InProceedings{pmlr-v31-affandi13a, title = {Nystrom Approximation for Large-Scale Determinantal Processes}, author = {Affandi, Raja Hafiz and Kulesza, Alex and Fox, Emily and Taskar, Ben}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {85--98}, year = {2013}, editor = {Carvalho, Carlos M. and Ravikumar, Pradeep}, volume = {31}, series = {Proceedings of Machine Learning Research}, address = {Scottsdale, Arizona, USA}, month = {29 Apr--01 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v31/affandi13a.pdf}, url = {https://proceedings.mlr.press/v31/affandi13a.html}, abstract = {Determinantal point processes (DPPs) are appealing models for subset selection problems where diversity is desired. They offer surprisingly efficient inference, including sampling in $O(N^3)$ time and $O(N^2)$ space, where $N$ is the number of base items. However, in some applications, $N$ may grow so large that sampling from a DPP becomes computationally infeasible. This is especially true in settings where the DPP kernel matrix cannot be represented by a linear decomposition of low-dimensional feature vectors. In these cases, we propose applying the Nystrom approximation to project the kernel matrix into a low-dimensional space. While theoretical guarantees for the Nystrom approximation in terms of standard matrix norms have been previously established, we are concerned with probabilistic measures, like total variation distance between the DPP generated by a kernel matrix and the one generated by its Nystrom approximation, that behave quite differently. In this paper we derive new error bounds for the Nystrom-approximated DPP and present empirical results to corroborate them. We then demonstrate the Nystrom-approximated DPP by applying it to a motion capture summarization task.} }
Endnote
%0 Conference Paper %T Nyström Approximation for Large-Scale Determinantal Processes %A Raja Hafiz Affandi %A Alex Kulesza %A Emily Fox %A Ben Taskar %B Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2013 %E Carlos M. Carvalho %E Pradeep Ravikumar %F pmlr-v31-affandi13a %I PMLR %P 85--98 %U https://proceedings.mlr.press/v31/affandi13a.html %V 31 %X Determinantal point processes (DPPs) are appealing models for subset selection problems where diversity is desired. They offer surprisingly efficient inference, including sampling in $O(N^3)$ time and $O(N^2)$ space, where $N$ is the number of base items. However, in some applications, $N$ may grow so large that sampling from a DPP becomes computationally infeasible. This is especially true in settings where the DPP kernel matrix cannot be represented by a linear decomposition of low-dimensional feature vectors. In these cases, we propose applying the Nystrom approximation to project the kernel matrix into a low-dimensional space. While theoretical guarantees for the Nystrom approximation in terms of standard matrix norms have been previously established, we are concerned with probabilistic measures, like total variation distance between the DPP generated by a kernel matrix and the one generated by its Nystrom approximation, that behave quite differently. In this paper we derive new error bounds for the Nystrom-approximated DPP and present empirical results to corroborate them. We then demonstrate the Nystrom-approximated DPP by applying it to a motion capture summarization task.
RIS
TY - CPAPER TI - Nyström Approximation for Large-Scale Determinantal Processes AU - Raja Hafiz Affandi AU - Alex Kulesza AU - Emily Fox AU - Ben Taskar BT - Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-affandi13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 85 EP - 98 L1 - http://proceedings.mlr.press/v31/affandi13a.pdf UR - https://proceedings.mlr.press/v31/affandi13a.html AB - Determinantal point processes (DPPs) are appealing models for subset selection problems where diversity is desired. They offer surprisingly efficient inference, including sampling in $O(N^3)$ time and $O(N^2)$ space, where $N$ is the number of base items. However, in some applications, $N$ may grow so large that sampling from a DPP becomes computationally infeasible. This is especially true in settings where the DPP kernel matrix cannot be represented by a linear decomposition of low-dimensional feature vectors. In these cases, we propose applying the Nystrom approximation to project the kernel matrix into a low-dimensional space. While theoretical guarantees for the Nystrom approximation in terms of standard matrix norms have been previously established, we are concerned with probabilistic measures, like total variation distance between the DPP generated by a kernel matrix and the one generated by its Nystrom approximation, that behave quite differently. In this paper we derive new error bounds for the Nystrom-approximated DPP and present empirical results to corroborate them. We then demonstrate the Nystrom-approximated DPP by applying it to a motion capture summarization task. ER -
APA
Affandi, R.H., Kulesza, A., Fox, E. & Taskar, B.. (2013). Nyström Approximation for Large-Scale Determinantal Processes. Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:85-98 Available from https://proceedings.mlr.press/v31/affandi13a.html.

Related Material