Detecting possibly frequent change-points: Wild Binary Segmentation 2 and steepest-drop model selection

다국어 초록 (Multilingual Abstract)

Many existing procedures for detecting multiple change-points in data sequences fail in frequent-change-point scenarios. This article proposes a new change-point detection methodology designed to work well in both infrequent and frequent changepoint settings. It is made up of two ingredients: one is “Wild Binary Segmentation 2” (WBS2), a recursive algorithm for producing what we call a ‘complete’ solution path to the change-point detection problem, i.e. a sequence of estimated nested models containing 0, …, T − 1 change-points, where T is the data length. The other ingredient is a new model selection procedure, referred to as “Steepest Drop to Low Levels” (SDLL). The SDLL criterion acts on the WBS2 solution path, and, unlike many existing model selection procedures for change-point problems, it is not penalty-based, and only uses thresholding as a certain discrete secondary check. The resulting WBS2.SDLL procedure, combining both ingredients, is shown to be consistent, and to signifcantly outperform the competition in the frequent change-point scenarios tested. WBS2.SDLL is fast, easy to code and does not require the choice of a window or span parameter.

참고문헌 (Reference)

1 Baranowski, R., "wbs: Wild binary segmentation for multiple change-point detection"

2 Zeileis, A., "strucchange : An R package for testing for structural change in linear regression models" 7 : 1-38, 2002

3 Pein, F, "stepR: Multiscale change-point inference"

4 Meier, A., "mosum: Moving sum based procedures for changes in the mean"

5 Pierre-Jean, M., "jointseg: Joint segmentation of multivariate (copy number) signals"

6 Rigaill, G., "fpop: Segmentation using Optimal Partitioning and Function Pruning"

7 James, N., "ecp : An R package for nonparametric multiple change point analysis of multivariate data" 62 : 1-25, 2014

8 Muggeo V., "cumSeg: Change point detection in genomic sequences"

9 Killick, R., "changepoint: An R package for changepoint analysis"

10 Arlot, S, "capushe: CAlibrating Penalities Using Slope HEuristics"

11 Fryzlewicz, P., "breakfast: Multiple change-point detection and segmentation"

12 Fryzlewicz, P., "Wild binary segmentation for multiple change-point detection" 42 : 2243-2281, 2014

13 Lavielle, M., "Using penalized contrasts for the change-point problem" 85 : 1501-1510, 2005

14 Wang, D., "Univariate mean change point detection: Penalization" CUSUM and optimality 2018

15 Salarijazi, M., "Trend and change-point detection for the annual stream-fow series of the Karun River at the Ahvaz hydrometric station" 7 : 4540-4552, 2012

16 Hansen, B., "The new econometrics of structural change : Dating breaks in U. S. labour productivity" 15 : 117-128, 2001

17 Fryzlewicz, P., "Tail-greedy bottom-up data decompositions and fast multiple change-point detection" 46 : 3390-3421, 2018

18 Davis, R., "Structural break estimation for nonstationary time series models" 101 : 223-239, 2006

19 Du, C., "Stepwise signal extraction via marginal likelihood" 111 : 314-330, 2016

20 Braun, J., "Statistical methods for DNA sequence segmentation" 13 : 142-162, 1998

21 Tibshirani, R., "Sparsity and smoothness via the fused lasso" 67 : 91-108, 2005

22 Baudry, J. -P., "Slope heuristics : Overview and implementation" 22 : 455-470, 2012

23 Wu, Y., "Simultaneous change point analysis and variable selection in a regression problem" 99 : 2154-2171, 2008

24 Truong, C., "Selective review of ofine change point detection methods" 167 : 107299-, 2020

25 Cleynen, A., "Segmentor3IsBack: A fast segmentation algorithm"

26 Rinaldo, A., "Properties and refnements of the fused lasso" 37 : 2922-2952, 2009

27 Huskova, M., "Permutation tests for multiple changes" 37 : 605-622, 2001

28 Ross, G. J., "Parametric and nonparametric sequential change detection in R : the cpm package" 66 : 1-20, 2015

29 Ranganathan, A., "PLISS : Labeling places using online changepoint detection" 32 : 351-368, 2012

30 Killick, R., "Optimal detection of changepoints with a linear computational cost" 107 : 1590-1598, 2012

31 Maidstone, R., "On optimal multiple changepoint algorithms for large data" 27 : 519-533, 2017

32 Rojas, C., "On change point detection using the fused lasso method"

33 Bosq, D., "Nonparametric statistics for stochastic processes" Springer 1998

34 Brodsky, B., "Nonparametric methods in change-point problems" Kluwer Academic Publishers 1993

35 Baranowski, R., "Narrowest-Over-Threshold detection of multiple change-points and change-point-like features" 81 : 649-672, 2019

36 Cho, H., "Multiscale interpretation of taut string estimation and its connection to Unbalanced Haar wavelets" 21 : 671-681, 2011

37 Frick, K., "Multiscale change-point inference(with discussion)" 76 : 495-580, 2014

38 Cho, H., "Multiscale and multilevel technique for consistent segmentation of nonstationary time series" 22 : 207-229, 2012

39 Galceran, E., "Multipolicy decision-making for autonomous driving via changepoint-based behavior prediction" 11 : 2015

40 Fryzlewicz, P., "Multiple-change-point detection for auto-regressive conditional heteroscedastic processes" 76 : 903-924, 2014

41 Braun, J., "Multiple changepoint ftting via quasilikelihood, with application to dna sequence segmentation" 87 : 301-314, 2000

42 Harchaoui, Z., "Multiple change-point estimation with a total variation penalty" 105 : 1480-1493, 2010

43 Korkas, K., "Multiple change-point detection for non-stationary time series using wild binary segmentation" 27 : 287-311, 2017

44 Cho, H., "Multiple change-point detection for high-dimensional time series via sparsifed binary segmentation" 77 : 475-507, 2015

45 Ciuperca, G., "Model selection by LASSO methods in a change-point model" 55 : 349-374, 2014

46 Birgé, L., "Minimal penalties for Gaussian model selection" 138 : 33-73, 2007

47 Arlot, S., "Minimal penalties and the slope heuristics : A survey" 160 : 1-106, 2019

48 Davies, P. L., "Local extremes, runs, strings and multiresolution" 29 : 1-48, 2001

49 Lavielle, M., "Least-squares estimation of an unknown number of shifts in a time series" 21 : 33-59, 2000

50 Yao, Y. -C., "Least-squares estimation of a step function" 51 : 370-381, 1989

51 Efron, B., "Least angle regression" 32 : 407-499, 2004

52 Wang, Y., "Jump and sharp cusp detection by wavelets" 82 : 385-397, 1995

53 Younes, L., "Inferring changepoint times of medial temporal lobe morphometric change in preclinical Alzheimer’s disease" 5 : 178-187, 2014

54 D’Angelo, M., "Incipient fault detection in induction machine stator-winding using a fuzzy-Bayesian change point detection approach" 11 : 179-192, 2011

55 Liu, D., "Impacts of climate change and human activities on surface runof in the Dongjiang River basin of China" 24 : 1487-1495, 2010

56 Anastasiou, A., "IDetect: Detecting multiple generalized change-points by isolating single ones"

57 Wang, T., "High dimensional change point estimation via sparse projection" 80 : 57-83, 2018

58 Birgé, L., "Gaussian model selection" 3 : 203-268, 2001

59 National Research Council, "Frontiers in Massive Data Analysis" The National Academies Press 2013

60 Pezzatti, G., "Fire regime shifts as a consequence of fre policy and socio-economic development: An analysis based on the change point approach" 29 : 7-18, 2013

61 Li, H., "FDRSeg: FDR-control in multiscale change-point segmentation"

62 Li, H., "FDR-control in multiscale change-point segmentation" 10 : 918-959, 2016

63 Huang, C. -Y., "Estimation and analysis of some generalized multiple change-point software reliability models" 60 : 498-514, 2011

64 Yao, Y. -C., "Estimating the number of change-points via Schwarz’ criterion" 6 : 181-189, 1988

65 Lee, C. -B., "Estimating the number of change points in a sequence of independent normal random variables" 25 : 241-248, 1995

66 Muggeo, V., "Estimating regression models with unknown break-points" 22 : 3055-3071, 2003

67 Bai, J., "Estimating multiple breaks one at a time" 13 : 315-352, 1997

68 Muggeo, V., "Efcient change point detection for genomic sequences of continuous measurements" 27 : 161-166, 2011

69 Lavielle, M., "Detection of multiple changes in a sequence of dependent variables" 83 : 79-102, 1999

70 Vostrikova, L., "Detecting ‘disorder’ in multidimensional random processes" 24 : 55-59, 1981

71 Anastasiou, A., "Detecting multiple generalized change-points by isolating single ones" 2018

72 Lebarbier, E., "Detecting multiple change-points in the mean of Gaussian process by model selection" 85 : 717-736, 2005

73 Andreou, E., "Detecting multiple breaks in fnancial market volatility dynamics" 17 : 579-600, 2002

74 Chen, K. -M., "Consistent multiple testing for change points" 102 : 1339-1343, 2011

75 Venkatraman, E. S., "Consistency results in multiple change-point problems" Department of Statistics, Stanford University 1992

76 Boysen, L., "Consistencies and rates of convergence of jump-penalized least squares estimators" 37 : 157-183, 2009

77 Bai, J., "Computation and analysis of multiple structural change models" 18 : 1-22, 2003

78 Olshen, A., "Circular binary segmentation for the analysis of array-based DNA copy number data" 5 : 557-572, 2004

79 Amiri, A., "Change point estimation methods for control chart postsignal diagnostics : A literature review" 28 : 673-685, 2012

80 Pan, J., "Application of modifed information criterion to multiple change point problems" 97 : 2221-2241, 2006

81 Mallows, C., "Another comment on O’Cinneide" 45 : 257-, 1991

82 Lin, K., "Advances in neural information processing systems" Curran Associates, Inc 6884-6893, 2017

83 Guntuboyina, A., "Adaptive risk bounds in univariate total variation denoising and trend fltering" 48 : 205-229, 2020

84 Tibshirani, R., "Adaptive piecewise polynomial estimation via trend fltering" 42 : 285-323, 2014

85 Reeves, J., "A review and comparison of changepoint detection techniques for climate data" 46 : 900-915, 2007

86 Rigaill, G., "A pruned dynamic programming algorithm to recover the best segmentations with 1 to kmax change-points" 156 : 180-205, 2015

87 Matteson, D., "A nonparametric approach for multiple change point analysis of multivariate data" 109 : 334-345, 2014

88 Zhang, N., "A modifed Bayes information criterion with applications to the analysis of comparative genomic hybridization data" 63 : 22-32, 2007

89 Ciuperca, G., "A general criterion to determine the number of change-points" 81 : 1267-1275, 2011

90 Venkatraman, E. S., "A faster circular binary segmentation algorithm for the analysis of array CGH data" 23 : 657-663, 2007

91 Eichinger, B., "A MOSUM procedure for the estimation of multiple random change points" 24 : 526-564, 2018