Abstract

Change point analysis involves the identification of potential shifts in

the underlying data distribution and the precise estimation of the location of such

a change point. Recent attention has been directed towards the adoption of nonparametric testing methods to address the former objective. However, existing

research on the asymptotic behavior of change point tests is somewhat limited due

to their reliance on an infinite series of nonparametric statistics. To address this

limitation, we develop a CUSUM likelihood ratio test statistic based on nonparametric density estimation in the framework of reproducing kernel Hilbert spaces.

Furthermore, we present a comprehensive non-asymptotic theoretical framework

for nonparametric density estimation. We achieve an asymptotic control over

type-I errors and can pinpoint the change point at an optimal rate. Besides simulations, our numerical studies also include a real-world application on neonatal

seizure detection with multiple electrical signal channels.

Information

Preprint No.SS-2024-0320
Manuscript IDSS-2024-0320
Complete AuthorsXin Xing, Zuofeng Shang, Hongyu Miao, Pang Du
Corresponding AuthorsPang Du
Emailspangdu@vt.edu

References

  1. Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1948.
  2. Sylvain Arlot, Alain Celisse, and Zaid Harchaoui. A kernel multiple change-point algorithm via model selection. Journal of machine learning research, 20(162), 2019.
  3. Daniel Barry and John A Hartigan. A bayesian analysis for change point problems. Journal of the American Statistical Association, 88(421):309–319, 1993.
  4. Edward G Carlstein, David Siegmund, et al. Change-point problems. IMS, 1994.
  5. Alain Celisse, Guillemette Marot, Morgane Pierre-Jean, and GJ Rigaill. New efficient algorithms for multiple change-point detection with reproducing kernels. Computational Statistics & Data Analysis, 128:200–220, 2018.
  6. Uikyu Chae, Hyogeun Shin, Nakwon Choi, Mi-Jung Ji, Hyun-Mee Park, Soo Hyun Lee, Jiwan
  7. Woo, Yakdol Cho, Kanghwan Kim, Seulkee Yang, et al. Bimodal neural probe for highly co-localized chemical and electrical monitoring of neural activities in vivo. Biosensors and Bioelectronics, 191:113473, 2021.
  8. Hao Chen and Nancy Zhang. Graph-based change-point detection. Annals of Statistics, 43:
  9. 139–176, 2015.
  10. Jie Chen and Arjun K Gupta. Parametric statistical change point analysis: with applications to genetics, medicine, and finance. 2012.
  11. Zhanshou Chen and Zheng Tian. Modified procedures for change point monitoring in linear models. Mathematics and computers in simulation, 81(1):62–75, 2010.
  12. Haeran Cho and Piotr Fryzlewicz. Multiple-change-point detection for high dimensional time series via sparsified binary segmentation. Journal of the Royal Statistical Society: Series
  13. B (Statistical Methodology), 77(2):475–507, 2015.
  14. Lynna Chu and Hao Chen. Asymptotic distribution-free change-point detection for multivariate and non-Euclidean data. Annals of Statistics, 47:382–414, 2019. John HJ Einmahl and Ian W McKeague.
  15. Empirical likelihood based hypothesis testing. Bernoulli, 9(2):267–290, 2003.
  16. Farida Enikeeva and Zaid Harchaoui. High-dimensional change-point detection under sparse alternatives. The Annals of Statistics, 47(4):2051–2079, 2019. Piotr Fryzlewicz.
  17. Wild binary segmentation for multiple change-point detection. Annals of Statistics, 42(6):2243–2281, 2014.
  18. Damien Garreau and Sylvain Arlot. Consistent change-point detection with kernels. Electronic
  19. Journal of Statistics, 12(2):4440–4486, 2018.
  20. BR Greene, S Faul, WP Marnane, G Lightbody, I Korotchikova, and GB Boylan. A comparison of quantitative eeg features for neonatal seizure detection. Clinical Neurophysiology, 119
  21. (6):1248–1261, 2008.
  22. Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Sch¨olkopf, and Alexander
  23. Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(Mar):723–
  24. 773, 2012.
  25. Chong Gu. Smoothing spline ANOVA models, volume 297. Springer Science & Business Media, 2013.
  26. Zaid Harchaoui and Olivier Capp´e. Retrospective mutiple change-point estimation with kernels.
  27. In 2007 IEEE/SP 14th Workshop on Statistical Signal Processing, pages 768–772. IEEE, 2007.
  28. Michael J. Katz. Fractals and the analysis of waveforms. Computers in Biology and Medicine, 18(3):145 – 156, 1988.
  29. Rebecca Killick, Paul Fearnhead, and Idris A Eckley. Optimal detection of changepoints with a linear computational cost. Journal of the American Statistical Association, 107(500):
  30. 1590–1598, 2012.
  31. Young-Ju Kim and Chong Gu. Smoothing spline gaussian regression: more scalable computation via efficient approximation. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 66(2):337–356, 2004.
  32. Solt Kov´acs, Peter B¨uhlmann, Housen Li, and Axel Munk. Seeded binary segmentation: a general methodology for fast and optimal changepoint detection. Biometrika, 110(1):249–
  33. 256, 2023.
  34. Marc Lavielle and Gilles Teyssiere. Detection of multiple change-points in multivariate time series. Lithuanian Mathematical Journal, 46(3):287–306, 2006.
  35. Brian Litt and Javier Echauz. Prediction of epileptic seizures. The Lancet Neurology, 1(1):
  36. 22–30, 2002.
  37. Greta M Ljung and George EP Box. On a measure of lack of fit in time series models. Biometrika, 65(2):297–303, 1978.
  38. David S Matteson and Nicholas A James. A nonparametric approach for multiple change point analysis of multivariate data. Journal of the American Statistical Association, 109(505):
  39. 334–345, 2014.
  40. Erich Novak, Mario Ullrich, Henryk Wo´zniakowski, and Shun Zhang. Reproducing kernels of sobolev spaces on Rd and applications to embedding constants and tractability. Analysis and Applications, 16(05):693–715, 2018.
  41. Carlos Misael Madrid Padilla, Haotian Xu, Daren Wang, Oscar Hernan Madrid Padilla, and
  42. Yi Yu. Change point detection and inference in multivariable nonparametric models under mixing conditions. NeurIPS 2023, 2023.
  43. Oscar Hernan Madrid Padilla, Yi Yu, Daren Wang, and Alessandro Rinaldo. Optimal nonparametric change point analysis. Electronic Journal of Statistics, 15(1), 2021a.
  44. Oscar Hernan Madrid Padilla, Yi Yu, Daren Wang, and Alessandro Rinaldo. Optimal nonparametric multivariate change point detection and localization. IEEE Transactions on
  45. Information Theory, 68(3):1922–1944, 2021b.
  46. Aleksey S Polunchenko and Alexander G Tartakovsky. State-of-the-art in sequential changepoint detection. Methodology and computing in applied probability, 14:649–684, 2012.
  47. Garvesh Raskutti, Martin J. Wainwright, and Bin Yu. Minimax-optimal rates for sparse additive models over kernel classes via convex programming. Journal of Machine Learning Research, 13(13):389–427, 2012. URL http://jmlr.org/papers/v13/raskutti12a.html.
  48. Gaetano Romano, Idris Eckley, Paul Fearnhead, and Guillem Rigaill. Fast online changepoint detection via functional pruning cusum statistics. arXiv preprint arXiv:2110.08205, 2021.
  49. Zuofeng Shang and Guang Cheng. Local and global asymptotic inference in smoothing spline models. The Annals of Statistics, 41(5):2608–2638, 2013.
  50. Le Song, Jonathan Huang, Alex Smola, and Kenji Fukumizu. Hilbert space embeddings of conditional distributions with applications to dynamical systems. In Proceedings of the
  51. 26th annual international conference on machine learning, pages 961–968, 2009.
  52. Michal Teplan et al. Fundamentals of eeg measurement. Measurement science review, 2(2):
  53. 1–11, 2002. Hazem Toutounji and Daniel Durstewitz.
  54. Detecting multiple change points using adaptive regression splines with application to neural recordings. Frontiers in neuroinformatics, page 67, 2018.
  55. Linda G.M. van Rooij, Lena Hellstrm-Westas, and Linda S. de Vries. Treatment of neonatal seizures. Seminars in Fetal and Neonatal Medicine, 18(4):209 – 215, 2013.
  56. Grace Wahba. Spline models for observational data, volume 59. Siam, 1990.
  57. Tengyao Wang and Richard J Samworth. High dimensional change point estimation via sparse projection. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80
  58. (1):57–83, 2018.
  59. Xin Xing, Zuofeng Shang, Pang Du, Ping Ma, Wenxuan Zhong, and Jun S Liu. Minimax nonparametric multi-sample test under smoothing. Statistica Sinica, 2023.
  60. Yun Yang, Zuofeng Shang, and Guang Cheng. Non-asymptotic theory for nonparametric testing.
  61. arXiv preprint arXiv:1702.01330, 2017.
  62. A. Zeileis, F. Leisch, C. Kleiber, and K. Hornik. Monitoring structural change in dynamic econometric models. Journal of Applied Econometrics, 20(1):99–121, 2005.
  63. Changliang Zou, Guosheng Yin, Long Feng, and Zhaojun Wang. Nonparametric maximum likelihood approach to multiple change-point problems. 2014.

Acknowledgments

The authors are grateful of the Assoicate Editor and two anonymous reviewers for their insightful comments that have significantly improved the

paper. Xing’s research was partially supported by U.S. NSF Grant DMS-

  1. Shang’s research was supported by NSF DMS 1821157.

Supplementary Materials

The online Supplementary Material contains the proofs of the main theorems as well as some auxiliary results.

Supplementary materials are available for download.