# Optimal Detection of Changepoints with a Linear Computational Cost 阅读笔记

## note of PELT

Posted by SHIELD-SKY on March 17, 2020

One commonly used approach to identify multiple change points is to minimize

$\sum_{i=1}^{m+1}[\mathcal{C}(y_{(\tau_{i-1}+1):\tau_{i}})] + \beta f(m)$

Here $$\mathcal{C}$$ is a cost function for a segment and $$\beta f(m)$$ is a penalty to guard against overfitting.

### 几种cost function：

1. twice th negative log-likelihood

3. cumulative sums

4. based on both the segment log-likelihood and the length of the segment

### penalty

1. most common choice : $$\beta f(m) = \beta m$$

• Akaike’s information criterion (AIC; Akaike 1974) (β = 2p)

• Schwarz information criterion (SIC, also known as BIC; Schwarz 1978) (β = p log n, where p is the number of additional parameters introduced by adding a changepoint).

### A brief history

At the time of writing(2012):

binary segment(BS) proposed by Scott and Knott(1974) is most widely used change point search method. $$\mathcal{O} (n log n)$$

$\mathcal{C}(y_{1:\tau}) + \mathcal{C}({y_{(\tau+1):n}})+\beta < \mathcal{C}(y_{1:n})$

#### Exact Methods

Serveral exact search method are base on dynamic programming.

segment neighborhood(SN) method proposed by Auger and Lawrence (1989) is $$\mathcal{O}(Qn^2)$$ . Q 是希望搜索的变化点的最大个数。变化点随着n线性增长，计算复杂度会是cubic

The OP Method. An alternative dynamic programming algorithm is provided by optimal partitioning (OP) approach of Jackson et al.(2005) $$\mathcal{O}(n^2)$$

### 要想理解OP method 首先需要理解dynamic programming！

OP method 将上一个变化点 之前的cost 与 变化点之后的cost 联系起来。原文中这样描述：Following Jackson et al. (2005), the OP method begins by first conditioning on the last point of change. It then relates the optimal value of the cost function to the cost for the optimal partition of the data prior to the last changepoint plus the cost for the segment from the last changepoint to the end of the data.

### 本文方法

We present a new approach to search for changepoints, which is exact and, under mild conditions, has a computational cost that is linear in the number of data points: the pruned exact linear time (PELT) method.

This approach is based on the algorithm of Jackson et al. (2005), but involves a pruning step within the dynamic program. This pruning reduces the computational cost of the method, but does not affect the exactness of the resulting segmentation.

PELT 在OP的基础之上加入了 pruning

$\mathcal{C}(y_{(\tau+1):s}) + \mathcal{C}(y_{(s+1):T}) +K \leqslant \mathcal{C}(y_{(t+1):T})$

Then , if

$F(t) + \mathcal{C}(y_{(t+1):s}) + K \geqslant F(S)$

Holds, at a future time T > s, t can never be the optimal last changepoint prior to T.

### 感想

1. 传统经典算法就是经典，一开始忘记了动态规划的思想，论文代码一点都没通。疫情在家，翻了翻算导，重新拾起动态规划，发现其实OP method的核心idea 就是动态规划。每一个经典算法之上成果真是枝繁叶茂。

2. 再次强调一下英语阅读和语文能力。在学校读这论文时好像正是期末考试，也是心烦意乱，没能领略作者的idea。 感谢这疫情超长假期，在家读完了word power made easy ，感觉再回来读论文，信息的接收理解比以前流畅了不少。