Sequential change diagnosis revisited and the Adaptive Matrix CuSum. (English) Zbl 07874418
Summary: The problem of sequential change diagnosis is considered, where observations are obtained on-line, an abrupt change occurs in their distribution, and the goal is to quickly detect the change and accurately identify the post-change distribution, while controlling the false alarm rate. A finite set of alternatives is postulated for the post-change regime, but no prior information is assumed for the unknown change point. A drawback of many algorithms that have been proposed for this problem is the implicit use of pre-change data for determining the post-change distribution. This can lead to very large conditional probabilities of misidentification, given that there was no false alarm, unless the change occurs soon after monitoring begins. A novel, recursive algorithm is proposed and shown to resolve this issue without the use of additional tuning parameters and without sacrificing control of the worst-case delay in Lorden’s sense. A theoretical analysis is conducted for a general family of sequential change diagnosis procedures, which supports the proposed algorithm and revises certain state-of-the-art results. Additionally, a novel, comprehensive method is proposed for the design and evaluation of sequential change diagnosis algorithms. This method is illustrated with simulation studies, where existing procedures are compared to the proposed.
MSC:
| 62L10 | Sequential statistical analysis |
References:
| [1] | Bakhache, B. and Nikiforov, I. (1999). Reliable detection of faults in navigation systems. In Proceedings of the 38th IEEE Conference on Decision and Control (Cat. No. 99CH36304) 5 4976-4981. IEEE. |
| [2] | Bissell, A. (1969). Cusum techniques for quality control. J. R. Stat. Soc. Ser. C. Appl. Stat. 18 1-25. |
| [3] | Chen, Y., Wang, T. and Samworth, R.J. (2022). High-dimensional, multiscale online changepoint detection. J. R. Stat. Soc. Ser. B. Stat. Methodol. 84 234-266. 10.1111/rssb.12447 MathSciNet: MR4400396 · Zbl 07593410 |
| [4] | Chen, Y.C., Banerjee, T., Dominguez-Garcia, A.D. and Veeravalli, V.V. (2015). Quickest line outage detection and identification. IEEE Trans. Power Syst. 31 749-758. |
| [5] | Dayanik, S., Goulding, C. and Poor, H.V. (2008). Bayesian sequential change diagnosis. Math. Oper. Res. 33 475-496. 10.1287/moor.1070.0307 MathSciNet: MR2416004 · Zbl 1297.62179 |
| [6] | Dayanik, S., Powell, W.B. and Yamazaki, K. (2013). Asymptotically optimal Bayesian sequential change detection and identification rules. Ann. Oper. Res. 208 337-370. 10.1007/s10479-012-1121-6 MathSciNet: MR3100637 · Zbl 1365.62322 |
| [7] | Fellouris, G. and Sokolov, G. (2016). Second-order asymptotic optimality in multisensor sequential change detection. IEEE Trans. Inf. Theory 62 3662-3675. 10.1109/TIT.2016.2549042 MathSciNet: MR3506755 · Zbl 1359.94221 |
| [8] | Fienberg, S.E. and Shmueli, G. (2005). Statistical issues and challenges associated with rapid detection of bio-terrorist attacks. Stat. Med. 24 513-529. 10.1002/sim.2032 MathSciNet: MR2134521 |
| [9] | Gösmann, J., Stoehr, C., Heiny, J. and Dette, H. (2022). Sequential change point detection in high dimensional time series. Electron. J. Stat. 16 3608-3671. 10.1214/22-ejs2027 MathSciNet: MR4444665 · Zbl 1493.62524 |
| [10] | Han, D. and Tsung, F. (2007). Detection and diagnosis of unknown abrupt changes using CUSUM multi-chart schemes. Sequential Anal. 26 225-249. 10.1080/07474940701404765 MathSciNet: MR2327978 · Zbl 1116.62081 |
| [11] | Hawkins, D.M., Qiu, P. and Kang, C.W. (2003). The changepoint model for statistical process control. J. Qual. Technol. 35 355-366. |
| [12] | Hinkley, D.V. (1970). Inference about the change-point in a sequence of random variables. Biometrika 57 1-17. 10.1093/biomet/57.1.1 MathSciNet: MR0273727 · Zbl 0198.51501 |
| [13] | Huang, Y.-C., Huang, Y.-J. and Lin, S.-C. (2021). Asymptotic optimality in Byzantine distributed quickest change detection. IEEE Trans. Inf. Theory 67 5942-5962. 10.1109/TIT.2021.3100423 MathSciNet: MR4345046 · Zbl 1486.94032 |
| [14] | Joe Qin, S. (2003). Statistical process monitoring: Basics and beyond. J. Chemom. 17 480-502. |
| [15] | Lai, T.L. (1998). Information bounds and quick detection of parameter changes in stochastic systems. IEEE Trans. Inf. Theory 44 2917-2929. 10.1109/18.737522 MathSciNet: MR1672051 · Zbl 0955.62084 |
| [16] | Lai, T.L. (2000). Sequential multiple hypothesis testing and efficient fault detection-isolation in stochastic systems. IEEE Trans. Inf. Theory 46 595-608. 10.1109/18.825826 · Zbl 0994.62078 |
| [17] | Lai, T.L. and Shan, J.Z. (1999). Efficient recursive algorithms for detection of abrupt changes in signals and control systems. IEEE Trans. Automat. Control 44 952-966. 10.1109/9.763211 MathSciNet: MR1690539 · Zbl 0956.93060 |
| [18] | Lai, T.L. and Xing, H. (2010). Sequential change-point detection when the pre- and post-change parameters are unknown. Sequential Anal. 29 162-175. 10.1080/07474941003741078 MathSciNet: MR2747518 · Zbl 1190.62147 |
| [19] | Lau, T.S., Tay, W.P. and Veeravalli, V.V. (2019). A binning approach to quickest change detection with unknown post-change distribution. IEEE Trans. Signal Process. 67 609-621. 10.1109/TSP.2018.2881666 MathSciNet: MR3912276 · Zbl 1415.94336 |
| [20] | Liang, Y. and Veeravalli, V.V. (2022). Non-parametric quickest mean-change detection. IEEE Trans. Inf. Theory 68 8040-8052. MathSciNet: MR4544930 · Zbl 1534.62058 |
| [21] | Lorden, G. (1971). Procedures for reacting to a change in distribution. Ann. Math. Stat. 42 1897-1908. 10.1214/aoms/1177693055 MathSciNet: MR0309251 · Zbl 0255.62067 |
| [22] | Ma, X., Lai, L. and Cui, S. (2021). Two-stage Bayesian sequential change diagnosis. IEEE Trans. Signal Process. 69 6131-6147. 10.1109/TSP.2021.3115426 MathSciNet: MR4352880 · Zbl 07908784 |
| [23] | Malladi, D.P. and Speyer, J.L. (1999). A generalized Shiryayev sequential probability ratio test for change detection and isolation. IEEE Trans. Automat. Control 44 1522-1534. 10.1109/9.780416 MathSciNet: MR1707049 · Zbl 0957.90040 |
| [24] | Mei, Y. (2006). Sequential change-point detection when unknown parameters are present in the pre-change distribution. Ann. Statist. 34 92-122. 10.1214/009053605000000859 MathSciNet: MR2275236 · Zbl 1091.62064 |
| [25] | Mei, Y. (2010). Efficient scalable schemes for monitoring a large number of data streams. Biometrika 97 419-433. 10.1093/biomet/asq010 MathSciNet: MR2650748 · Zbl 1406.62088 |
| [26] | Moustakides, G.V. (1986). Optimal stopping times for detecting changes in distributions. Ann. Statist. 14 1379-1387. 10.1214/aos/1176350164 MathSciNet: MR0868306 · Zbl 0612.62116 |
| [27] | Nikiforov, I.V. (1995). A generalized change detection problem. IEEE Trans. Inf. Theory 41 171-187. 10.1109/18.370109 · Zbl 0826.93064 |
| [28] | Nikiforov, I.V. (2000). A simple recursive algorithm for diagnosis of abrupt changes in random signals. IEEE Trans. Inf. Theory 46 2740-2746. 10.1109/18.887891 MathSciNet: MR1807403 · Zbl 1002.94514 |
| [29] | Nikiforov, I.V. (2003). A lower bound for the detection/isolation delay in a class of sequential tests. IEEE Trans. Inf. Theory 49 3037-3047. 10.1109/TIT.2003.818398 MathSciNet: MR2027584 · Zbl 1301.94035 |
| [30] | Nikiforov, I.V. (2016). Sequential detection/isolation of abrupt changes. Sequential Anal. 35 268-301. 10.1080/07474946.2016.1206354 MathSciNet: MR3547963 · Zbl 1356.62114 |
| [31] | Nikiforov, I., Varavva, V. and Kireichikov, V. (1993). Application of statistical fault detection algorithms to navigation systems monitoring. Automatica 29 1275-1290. |
| [32] | Oskiper, T. and Poor, H.V. (2002). Online activity detection in a multiuser environment using the matrix CUSUM algorithm. IEEE Trans. Inf. Theory 48 477-493. 10.1109/18.979323 MathSciNet: MR1891258 · Zbl 1071.94515 |
| [33] | Page, E.S. (1954). Continuous inspection schemes. Biometrika 41 100-115. 10.1093/biomet/41.1-2.100 MathSciNet: MR0088850 · Zbl 0056.38002 |
| [34] | Pergamenchtchikov, S.M., Tartakovsky, A.G. and Spivak, V.S. (2022). Minimax and pointwise sequential changepoint detection and identification for general stochastic models. J. Multivariate Anal. 190 Paper No. 104977, 22. 10.1016/j.jmva.2022.104977 MathSciNet: MR4396577 · Zbl 1520.62101 |
| [35] | Pollak, M. (1985). Optimal detection of a change in distribution. Ann. Statist. 13 206-227. 10.1214/aos/1176346587 MathSciNet: MR0773162 · Zbl 0573.62074 |
| [36] | Rolka, H., Burkom, H., Cooper, G.F., Kulldorff, M., Madigan, D. and Wong, W.-K. (2007). Issues in applied statistics for public health bioterrorism surveillance using multiple data streams: Research needs. Stat. Med. 26 1834-1856. 10.1002/sim.2793 MathSciNet: MR2359196 |
| [37] | Ru, J., Jilkov, V.P., Li, X.R. and Bashi, A. (2009). Detection of target maneuver onset. IEEE Trans. Aerosp. Electron. Syst. 45 536-554. |
| [38] | Shewhart, W.A. (1931). Economic Control of Quality of Manufactured Product. London: Macmillan And Co Ltd. |
| [39] | Shin, J., Ramdas, A. and Rinaldo, A. (2022). E-detectors: A nonparametric framework for online changepoint detection. arXiv preprint arXiv:2203.03532. |
| [40] | Shiryaev, A.N. (1963). On optimum methods in quickest detection problems. Theory Probab. Appl. 8 22-46. 10.1137/1108002 MathSciNet: MR0155708 · Zbl 0213.43804 |
| [41] | Shiryaev, A.N. (2008). Optimal Stopping Rules. Stochastic Modelling and Applied Probability 8. Berlin: Springer. Translated from the 1976 Russian second edition by A. B. Aries, Reprint of the 1978 translation. MathSciNet: MR2374974 |
| [42] | Siegmund, D. (1979). Corrected diffusion approximations in certain random walk problems. Adv. in Appl. Probab. 11 701-719. 10.2307/1426855 MathSciNet: MR0544191 · Zbl 0422.60053 |
| [43] | Siegmund, D. (2013). Change-points: From sequential detection to biology and back. Sequential Anal. 32 2-14. 10.1080/07474946.2013.751834 MathSciNet: MR3023983 · Zbl 1271.62191 |
| [44] | Siegmund, D. and Venkatraman, E.S. (1995). Using the generalized likelihood ratio statistic for sequential detection of a change-point. Ann. Statist. 23 255-271. 10.1214/aos/1176324466 MathSciNet: MR1331667 · Zbl 0821.62044 |
| [45] | Tartakovsky, A.G. (2008). Multidecision quickest change-point detection: Previous achievements and open problems. Sequential Anal. 27 201-231. 10.1080/07474940801989202 MathSciNet: MR2422959 · Zbl 1274.62540 |
| [46] | Tartakovsky, A.G. (2021). An asymptotic theory of joint sequential changepoint detection and identification for general stochastic models. IEEE Trans. Inf. Theory 67 4768-4783. 10.1109/TIT.2021.3064344 MathSciNet: MR4306295 · Zbl 1475.62223 |
| [47] | Tartakovsky, A.G., Li, X.R. and Yaralov, G. (2003). Sequential detection of targets in multichannel systems. IEEE Trans. Inf. Theory 49 425-445. 10.1109/TIT.2002.807288 MathSciNet: MR1966790 · Zbl 1063.94518 |
| [48] | Tartakovsky, A., Nikiforov, I. and Basseville, M. (2015). Sequential Analysis: Hypothesis Testing and Changepoint Detection. Monographs on Statistics and Applied Probability 136. Boca Raton, FL: CRC Press. MathSciNet: MR3241619 |
| [49] | Tartakovsky, A.G., Rozovskii, B.L., Blazek, R.B. and Kim, H. (2006b). A novel approach to detection of intrusions in computer networks via adaptive sequential and batch-sequential change-point detection methods. IEEE Trans. Signal Process. 54 3372-3382. · Zbl 1373.68144 |
| [50] | Tartakovsky, A.G., Rozovskii, B.L., Blažek, R.B. and Kim, H. (2006a). Detection of intrusions in information systems by sequential change-point methods. Stat. Methodol. 3 252-293. 10.1016/j.stamet.2005.05.003 MathSciNet: MR2240956 · Zbl 1248.94032 |
| [51] | Warner, A. and Fellouris, G. (2022). CuSum for sequential change diagnosis. In 2022 IEEE International Symposium on Info. Theory 486-491. 10.1109/ISIT50566.2022.9834755 |
| [52] | Warner, A. and Fellouris, G. (2024). Supplement to “Sequential change diagnosis revisited and the Adaptive Matrix CuSum.” 10.3150/23-BEJ1671SUPP |
| [53] | Wei, S. and Xie, Y. (2022). Online kernel CUSUM for change-point detection. arXiv preprint arXiv:2211.15070. |
| [54] | Xie, L., Moustakides, G.V. and Xie, Y. (2023). Window-limited CUSUM for sequential change detection. IEEE Trans. Inf. Theory 69 5990-6005. MathSciNet: MR4635159 · Zbl 07883347 |
| [55] | Xie, Y. and Siegmund, D. (2013). Sequential multi-sensor change-point detection. Ann. Statist. 41 670-692. 10.1214/13-AOS1094 MathSciNet: MR3099117 · Zbl 1267.62084 |
| [56] | Xie, L., Zou, S., Xie, Y. and Veeravalli, V.V. (2021). Sequential (quickest) change detection: Classical results and new directions. IEEE J. Sel. Areas Inf. Theory 2 494-514. |
| [57] | Yang, H., Hadjiliadis, O. and Ludkovski, M. (2017). Quickest detection in the Wiener disorder problem with post-change uncertainty. Stochastics 89 654-685. 10.1080/17442508.2016.1276908 MathSciNet: MR3607746 · Zbl 1361.60029 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
