Bayesian Model Selection for Change Point Detection and Clustering

Othmane Mazhar, Cristian Rojas, Carlo Fischione,  Mohammad Reza Hesamzadeh
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3433-3442, 2018.

Abstract

We address a generalization of change point detection with the purpose of detecting the change locations and the levels of clusters of a piecewise constant signal. Our approach is to model it as a nonparametric penalized least square model selection on a family of models indexed over the collection of partitions of the design points and propose a computationally efficient algorithm to approximately solve it. Statistically, minimizing such a penalized criterion yields an approximation to the maximum a-posteriori probability (MAP) estimator. The criterion is then analyzed and an oracle inequality is derived using a Gaussian concentration inequality. The oracle inequality is used to derive on one hand conditions for consistency and on the other hand an adaptive upper bound on the expected square risk of the estimator, which statistically motivates our approximation. Finally, we apply our algorithm to simulated data to experimentally validate the statistical guarantees and illustrate its behavior.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-mazhar18a, title = {{B}ayesian Model Selection for Change Point Detection and Clustering}, author = {Mazhar, Othmane and Rojas, Cristian and Fischione, Carlo and edit Mohammad Reza Hesamzadeh}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3433--3442}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/mazhar18a/mazhar18a.pdf}, url = {https://proceedings.mlr.press/v80/mazhar18a.html}, abstract = {We address a generalization of change point detection with the purpose of detecting the change locations and the levels of clusters of a piecewise constant signal. Our approach is to model it as a nonparametric penalized least square model selection on a family of models indexed over the collection of partitions of the design points and propose a computationally efficient algorithm to approximately solve it. Statistically, minimizing such a penalized criterion yields an approximation to the maximum a-posteriori probability (MAP) estimator. The criterion is then analyzed and an oracle inequality is derived using a Gaussian concentration inequality. The oracle inequality is used to derive on one hand conditions for consistency and on the other hand an adaptive upper bound on the expected square risk of the estimator, which statistically motivates our approximation. Finally, we apply our algorithm to simulated data to experimentally validate the statistical guarantees and illustrate its behavior.} }
Endnote
%0 Conference Paper %T Bayesian Model Selection for Change Point Detection and Clustering %A Othmane Mazhar %A Cristian Rojas %A Carlo Fischione %A Mohammad Reza Hesamzadeh %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-mazhar18a %I PMLR %P 3433--3442 %U https://proceedings.mlr.press/v80/mazhar18a.html %V 80 %X We address a generalization of change point detection with the purpose of detecting the change locations and the levels of clusters of a piecewise constant signal. Our approach is to model it as a nonparametric penalized least square model selection on a family of models indexed over the collection of partitions of the design points and propose a computationally efficient algorithm to approximately solve it. Statistically, minimizing such a penalized criterion yields an approximation to the maximum a-posteriori probability (MAP) estimator. The criterion is then analyzed and an oracle inequality is derived using a Gaussian concentration inequality. The oracle inequality is used to derive on one hand conditions for consistency and on the other hand an adaptive upper bound on the expected square risk of the estimator, which statistically motivates our approximation. Finally, we apply our algorithm to simulated data to experimentally validate the statistical guarantees and illustrate its behavior.
APA
Mazhar, O., Rojas, C., Fischione, C. & Mohammad Reza Hesamzadeh, . (2018). Bayesian Model Selection for Change Point Detection and Clustering. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3433-3442 Available from https://proceedings.mlr.press/v80/mazhar18a.html.

Related Material