Data driven quickest change detection: An algorithmic complexity approach
Data driven quickest change detection: An algorithmic complexity approach
复制标题
数据驱动的最快变化检测：算法复杂性方法
DOI：
10.1109/isit.2016.7541253
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Husheng Li
中科院分区：
文献类型：
--
作者：
Husheng Li
传统的最快变化检测方法是检测随机过程中的分布变化，需要完全或部分地了解样本变化前或变化后的分布。在实际应用中，可能先验信息不可用，这禁止了诸如累积和（Cumulative Sum，CSCUM）算法的现有算法的直接应用。本文研究了数据驱动的最快检测问题，仅假设平稳遍历（不需要独立同分布）。或马尔可夫）过程。为了充分利用概率框架内的现有算法，算法复杂性理论（a.k.a. Kolmogorov复杂度）被应用于桥接观测样本和未知概率分布。特别是，数据压缩算法，如Lempel-Ziv算法被用来衡量无条件和条件算法的复杂性。数值仿真结果验证了所提算法的有效性。
Traditional quickest change detection, which detects distribution changes in random processes, requires full or partial knowledge of pre-change or post-change distributions of samples. In practice, it is possible that the prior information is unavailable, which prohibits the direct application of existing algorithms such as the cumulative sum (CUSUM) algorithm. In this paper, data driven quickest detection is studied, with only the assumption of stationary ergodic (not necessary i.i.d. or Markovian) processes. To fully exploit existing algorithms within the probabilistic framework, the theory of algorithmic complexity (a.k.a. Kolmogorov complexity) is applied to bridge the observed samples and unknown probability distributions. In particular, data compression algorithms such as Lempel-Ziv algorithm are used to measure the unconditional and conditional algorithm complexities. Numerical simulations are carried out to demonstrate the validity of the proposed algorithms.