Asymptotically consistent estimation of the number of change points in highly dependent time series

Azadeh Khaleghi, Daniil Ryabko
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):539-547, 2014.

Abstract

The problem of change point estimation is considered in a general framework where the data are generated by arbitrary unknown stationary ergodic process distributions. This means that the data may have long-range dependencies of an arbitrary form. In this context the consistent estimation of the number of change points is provably impossible. A formulation is proposed which overcomes this obstacle: it is possible to find the correct number of change points at the expense of introducing the additional constraint that the correct number of process distributions that generate the data is provided. This additional parameter has a natural interpretation in many real-world applications. It turns out that in this formulation change point estimation can be reduced to time series clustering. Based on this reduction, an algorithm is proposed that finds the number of change points and locates the changes. This algorithm is shown to be asymptotically consistent. The theoretical results are complemented with empirical evaluations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-khaleghi14, title = {Asymptotically consistent estimation of the number of change points in highly dependent time series}, author = {Khaleghi, Azadeh and Ryabko, Daniil}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {539--547}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/khaleghi14.pdf}, url = {https://proceedings.mlr.press/v32/khaleghi14.html}, abstract = {The problem of change point estimation is considered in a general framework where the data are generated by arbitrary unknown stationary ergodic process distributions. This means that the data may have long-range dependencies of an arbitrary form. In this context the consistent estimation of the number of change points is provably impossible. A formulation is proposed which overcomes this obstacle: it is possible to find the correct number of change points at the expense of introducing the additional constraint that the correct number of process distributions that generate the data is provided. This additional parameter has a natural interpretation in many real-world applications. It turns out that in this formulation change point estimation can be reduced to time series clustering. Based on this reduction, an algorithm is proposed that finds the number of change points and locates the changes. This algorithm is shown to be asymptotically consistent. The theoretical results are complemented with empirical evaluations.} }
Endnote
%0 Conference Paper %T Asymptotically consistent estimation of the number of change points in highly dependent time series %A Azadeh Khaleghi %A Daniil Ryabko %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-khaleghi14 %I PMLR %P 539--547 %U https://proceedings.mlr.press/v32/khaleghi14.html %V 32 %N 1 %X The problem of change point estimation is considered in a general framework where the data are generated by arbitrary unknown stationary ergodic process distributions. This means that the data may have long-range dependencies of an arbitrary form. In this context the consistent estimation of the number of change points is provably impossible. A formulation is proposed which overcomes this obstacle: it is possible to find the correct number of change points at the expense of introducing the additional constraint that the correct number of process distributions that generate the data is provided. This additional parameter has a natural interpretation in many real-world applications. It turns out that in this formulation change point estimation can be reduced to time series clustering. Based on this reduction, an algorithm is proposed that finds the number of change points and locates the changes. This algorithm is shown to be asymptotically consistent. The theoretical results are complemented with empirical evaluations.
RIS
TY - CPAPER TI - Asymptotically consistent estimation of the number of change points in highly dependent time series AU - Azadeh Khaleghi AU - Daniil Ryabko BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-khaleghi14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 1 SP - 539 EP - 547 L1 - http://proceedings.mlr.press/v32/khaleghi14.pdf UR - https://proceedings.mlr.press/v32/khaleghi14.html AB - The problem of change point estimation is considered in a general framework where the data are generated by arbitrary unknown stationary ergodic process distributions. This means that the data may have long-range dependencies of an arbitrary form. In this context the consistent estimation of the number of change points is provably impossible. A formulation is proposed which overcomes this obstacle: it is possible to find the correct number of change points at the expense of introducing the additional constraint that the correct number of process distributions that generate the data is provided. This additional parameter has a natural interpretation in many real-world applications. It turns out that in this formulation change point estimation can be reduced to time series clustering. Based on this reduction, an algorithm is proposed that finds the number of change points and locates the changes. This algorithm is shown to be asymptotically consistent. The theoretical results are complemented with empirical evaluations. ER -
APA
Khaleghi, A. & Ryabko, D.. (2014). Asymptotically consistent estimation of the number of change points in highly dependent time series. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(1):539-547 Available from https://proceedings.mlr.press/v32/khaleghi14.html.

Related Material