变点问题的公式推导
变点问题的公式推导
变点检测是统计学和信号处理中的一个重要问题，特别是在时间序列分析中。本文详细介绍了变点检测的背景、关键定义、动态规划框架，并重点证明了一个定理，该定理提供了一个数学工具，用于在变点检测问题中高效筛选候选变点。
背景与关键定义
变点检测问题
变点检测的目标是在给定的观测序列$y_1, y_2, \dots, y_T$中，找到一个或多个点（变点），使得每段子序列（即变点划分的区间）能被一个较简单的模型（比如常数均值模型）很好地拟合。
代价函数$\mathcal{C}$
$\mathcal{C}$表示给定一段子序列（如$y_{(t+1):s}$）的拟合代价（cost）。代价越小，说明这段序列被拟合得越好。
引入变点的目标
通常我们希望通过引入变点，使得划分后的子序列总代价减少。公式 (2) 的假设反映了这一点：
$\mathcal{C}\left(y_{(t+1): s}\right)+\mathcal{C}\left(y_{(s+1): T}\right)+K \leq \mathcal{C}\left(y_{(t+1): T}\right),$
表示将序列$y_{(t+1): T}$划分成两段（用变点$s$分开）后，总代价会减少。
动态规划框架
动态规划求解变点检测问题时，我们递归计算：
$F(T) = \min_{\tau} { F(\tau) + \mathcal{C}(y_{(\tau+1):T}) + \beta },$
其中：
- $F(\tau)$：序列$y_{1:\tau}$的最优划分代价。
- $\beta$：引入一个变点的固定代价（penalty）。
- $\tau$：候选的上一个变点。
因为枚举所有可能的$\tau$代价很高，我们希望通过数学分析提前剔除一些不可能成为最优解的候选变点。
定理 3.1 的主要内容
目标：如果某个点$t$不可能成为未来某个时间点$T > s$的最优变点，我们希望尽早把它剔除，从而减少动态规划的计算量。
定理的核心思想：如果$t$满足：
$F(t) + \mathcal{C}\left(y_{(t+1):s}\right) + K \geq F(s),$
那么对于所有未来的$T > s$，$t$不可能是最优变点。
直观解释：
- 变点$t$的分段代价（加上$K$）已经超过从$s$开始分段的代价$F(s)$。
- 这说明从$t$开始分段的效果不如从$s$开始分段，因此$t$永远不会成为未来的最优选择。
证明的关键步骤
假设 (3) 成立：
$F(t) + \mathcal{C}\left(y_{(t+1):s}\right) + K \geq F(s).$
我们在$t$和$s$两种可能分段中，发现$t$比$s$的代价更大。
添加未来段的代价：
考虑$T > s$，加入$\mathcal{C}\left(y_{(s+1):T}\right)$：
$F(t) + \mathcal{C}\left(y_{(t+1):s}\right) + K + \mathcal{C}\left(y_{(s+1):T}\right) \geq F(s) + \mathcal{C}\left(y_{(s+1):T}\right).$
这说明即使考虑未来序列，选择$t$作为变点的代价依然不如选择$s$的代价。
结合动态规划公式：
根据动态规划的递归公式：
$S_T = {F(\tau) + \mathcal{C}(y_{(\tau+1):T}) + \beta, \tau = 0, 1, \dots, T-1}.$
$t$的值不会比$s$小，因此$t$永远不会成为集合$S_T$的最优解。
结论：
$t$可以从候选集合中剔除。
定理的重要意义
加速动态规划
在变点检测的动态规划算法中，通过剔除不可能的候选变点，可以减少计算量，显著加快算法。
数学条件的合理性
定理基于变点的代价函数$\mathcal{C}$满足一定的“单调性”假设，这在实际问题中是常见的。
适用范围广
这种剔除策略不仅限于特定代价函数或数据集，具有通用性。
总结
- 定理 3.1 提供了一个数学工具，用于在变点检测问题中高效筛选候选变点。
- 证明利用了动态规划的递归公式，结合代价函数的性质，展示了某些变点在特定条件下无法成为最优解。
- 实际应用中，这一结果能显著优化计算效率，尤其是当数据规模较大时。
我们详细推导定理 3.1 的证明。目标是从假设$F(t) + \mathcal{C}(y_{(t+1):s}) + K \geq F(s)$出发，证明$t$无法成为未来时间$T > s$的最优变点。
前置公式和假设
动态规划的核心公式是：
$F(T) = \min_{\tau=0,1,\ldots,T-1} { F(\tau) + \mathcal{C}(y_{(\tau+1):T}) + \beta },$
其中：
- $F(T)$：从起点到时间$T$的最优代价。
- $\mathcal{C}(y_{(\tau+1):T})$：从$\tau + 1$到$T$的拟合代价。
- $\beta$：添加一个变点的固定代价。
- $\tau$：候选变点。
假设 (3) 是：
$F(t) + \mathcal{C}(y_{(t+1):s}) + K \geq F(s),$
表示在时间$s$，从$t$到$s$的分段代价（加上$K$）不小于从$s$开始分段的代价$F(s)$。
从 (2) 可知，引入变点的代价函数是非增的，即：
$\mathcal{C}(y_{(t+1):s}) + \mathcal{C}(y_{(s+1):T}) + K \leq \mathcal{C}(y_{(t+1):T}).$
证明步骤
第一步：结合假设 (3) 和未来代价
我们希望证明$t$无法成为未来时间$T > s$的最优变点。
从假设 (3) 出发，加入固定的惩罚项$\beta$：
$F(t) + \mathcal{C}(y_{(t+1):s}) + K + \beta \geq F(s) + \beta.$
这表示在时间$s$，以$t$为变点的代价高于以$s$为变点的代价。
考虑$T > s$，加入从$s + 1$到$T$的代价$\mathcal{C}(y_{(s+1):T})$：
$F(t) + \mathcal{C}(y_{(t+1):s}) + K + \beta + \mathcal{C}(y_{(s+1):T}) \ \geq F(s) + \beta + \mathcal{C}(y_{(s+1):T}).$
这是因为两边都添加了同样的项$\mathcal{C}(y_{(s+1):T})$。
第二步：利用代价的可加性
我们使用代价函数的可加性性质（公式 (2)）：
$\mathcal{C}(y_{(t+1):s}) + \mathcal{C}(y_{(s+1):T}) + K \leq \mathcal{C}(y_{(t+1):T}).$
将其代入左边的不等式：
$F(t) + \mathcal{C}(y_{(t+1):T}) + \beta \geq F(s) + \beta + \mathcal{C}(y_{(s+1):T}).$
这表示，加入从$t$到$T$的代价后，总代价依然大于从$s$到$T$的代价。
第三步：动态规划公式中的推论
根据动态规划公式：
$S_T = {F(\tau) + \mathcal{C}(y_{(\tau+1):T}) + \beta, \tau = 0, 1, \ldots, T-1}.$
- $t$对应的代价是$F(t) + \mathcal{C}(y_{(t+1):T}) + \beta$。
- $s$对应的代价是$F(s) + \mathcal{C}(y_{(s+1):T}) + \beta$。
由前面的推导可知：
$F(t) + \mathcal{C}(y_{(t+1):T}) + \beta \geq F(s) + \mathcal{C}(y_{(s+1):T}) + \beta.$
因此，$t$对应的代价比$s$大，$t$不可能是$S_T$的最优解。
第四步：剔除$t$
因为$t$的代价在所有$T > s$的情况下都比$s$大，因此$t$不可能成为未来任何时间点的最优变点。
结论是：
- 在动态规划中，$t$可以从候选集合中剔除。
- 这减少了后续计算的复杂度。
关键逻辑总结
- 假设$F(t) + \mathcal{C}(y_{(t+1):s}) + K \geq F(s)$表示$t$的代价在$s$处已经不如$s$。
- 使用代价函数的可加性，将$t$的代价扩展到未来时间$T > s$。
- 结合动态规划公式，说明$t$在所有未来时间$T > s$的代价都不如$s$。
- 结论是$t$无法成为未来的最优变点，动态规划时可以剔除$t$。