Block-Wise MAP Inference for Determinantal Point Processes with Application to Change-Point Detection
This work addresses the problem of scalable DPP inference for practitioners in fields like signal processing, offering an incremental improvement by adapting DPPs to block structures for specific applications.
The paper tackles the computational challenge of MAP inference for determinantal point processes (DPPs) by introducing BwDPPs, which use an almost block diagonal kernel matrix to enable efficient block-wise inference, and applies this to change-point detection, resulting in a method that outperforms existing approaches on five real-world datasets with improved accuracy and efficiency.
Existing MAP inference algorithms for determinantal point processes (DPPs) need to calculate determinants or conduct eigenvalue decomposition generally at the scale of the full kernel, which presents a great challenge for real-world applications. In this paper, we introduce a class of DPPs, called BwDPPs, that are characterized by an almost block diagonal kernel matrix and thus can allow efficient block-wise MAP inference. Furthermore, BwDPPs are successfully applied to address the difficulty of selecting change-points in the problem of change-point detection (CPD), which results in a new BwDPP-based CPD method, named BwDppCpd. In BwDppCpd, a preliminary set of change-point candidates is first created based on existing well-studied metrics. Then, these change-point candidates are treated as DPP items, and DPP-based subset selection is conducted to give the final estimate of the change-points that favours both quality and diversity. The effectiveness of BwDppCpd is demonstrated through extensive experiments on five real-world datasets.