Block-Wise MAP Inference for Determinantal Point Processes with Application to Change-Point Detection
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Change Point DetectionDiversityPoint ProcessesSimilar Papers 제목 키워드 기반
Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling
We analyze the convergence rate of the randomized Newton-like method introduced by Qu et. al. (2016) for smooth and convex objectives, which uses random coordinate blocks of a Hessian-over-approximation matrix $\bM$ inst…
Point ProcessesStructured Determinantal Point Processes
We present a novel probabilistic model for distributions over sets of structures -- for example, sets of sequences, trees, or graphs. The critical characteristic of our model is a preference for diversity: sets containin…
DiversityPoint ProcessesPose EstimationOnline MAP Inference and Learning for Nonsymmetric Determinantal Point Processes
In this paper, we introduce the online and streaming MAP inference and learning problems for Non-symmetric Determinantal Point Processes (NDPPs) where data points arrive in an arbitrary order and the algorithms are const…
Point ProcessesvalidMulti-Document Summarization with Determinantal Point Processes and Contextualized Representations
Emerged as one of the best performing techniques for extractive summarization, determinantal point processes select the most probable set of sentences to form a summary according to a probability measure defined by model…
Document SummarizationExtractive SummarizationMulti-Document SummarizationPoint Processes+1DPPNet: Approximating Determinantal Point Processes with Deep Networks
Determinantal Point Processes (DPPs) provide an elegant and versatile way to sample sets of items that balance the point-wise quality with the set-wise diversity of selected items. For this reason, they have gained promi…
DiversityPoint Processes