Geodesic
A pruned dynamic programming algorithm to recover the best segmentations with 1 to K m a x change-points
[Un algorithme de programmation dynamique élagué pour trouver les meilleures segmentations avec 1 à K m a x ruptures]
Journal de la société française de statistique, Tome 156 (2015) no. 4, pp. 180-205

Voir la notice de l'article provenant de la source Numdam

A common computational problem in multiple change-point models is to recover the segmentations with 1 to K m a x change-points of minimal cost with respect to some loss function. Here we present an algorithm to prune the set of candidate change-points which is based on a functional representation of the cost of segmentations. We study the worst case complexity of the algorithm when there is a unidimensional parameter per segment and demonstrate that it is at worst equivalent to the complexity of the segment neighbourhood algorithm: 𝒪 ( K m a x n 2 ) . For a particular loss function we demonstrate that pruning is on average efficient even if there are no change-points in the signal. Finally, we empirically study the performance of the algorithm in the case of the quadratic loss and show that it is faster than the segment neighbourhood algorithm.

Dans les modèles de ruptures multiples la recherche des segmentations de coût minimal, au sens d’une certaine fonction de perte, avec une à K m a x ruptures est un problème algorithmique courant. Ici, nous présentons un algorithme, basé sur une représentation fonctionnelle des segmentations, qui élague l’ensemble des ruptures candidates. Nous étudions la complexité au pire de cet algorithme quand il y a un paramètre unidimensionnel par segment. Nous démontrons dans ce cas que ça complexité est équivalente à celle de l’algorithme « segment neighborhood » en 𝒪 ( K m a x n 2 ) . Pour une fonction de perte particulière nous démontrons que l’élagage est en moyenne efficace quand il n’y a pas de ruptures dans le signal. Enfin nous étudions empiriquement les performances de l’algorithme dans le cas de la perte quadratique et montrons qu’il est plus rapide que l’algorithme « segment neighborhood »

Keywords: multiple-change-point detection, dynamic programming, functional cost, segment neighbourhood
Mots-clés : détection de ruptures multiples, programmation dynamique, coût fonctionnel 
@article{JSFS_2015__156_4_180_0,
     author = {Rigaill, Guillem},
     title = {A pruned dynamic programming algorithm to recover the best segmentations with $1$ to $K_{max}$ change-points},
     journal = {Journal de la soci\'et\'e fran\c{c}aise de statistique},
     pages = {180--205},
     publisher = {Soci\'et\'e fran\c{c}aise de statistique},
     volume = {156},
     number = {4},
     year = {2015},
     mrnumber = {3436653},
     zbl = {1381.90094},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JSFS_2015__156_4_180_0/}
}
TY  - JOUR
AU  - Rigaill, Guillem
TI  - A pruned dynamic programming algorithm to recover the best segmentations with $1$ to $K_{max}$ change-points
JO  - Journal de la société française de statistique
PY  - 2015
SP  - 180
EP  - 205
VL  - 156
IS  - 4
PB  - Société française de statistique
UR  - http://geodesic.mathdoc.fr/item/JSFS_2015__156_4_180_0/
LA  - en
ID  - JSFS_2015__156_4_180_0
ER  - 
%0 Journal Article
%A Rigaill, Guillem
%T A pruned dynamic programming algorithm to recover the best segmentations with $1$ to $K_{max}$ change-points
%J Journal de la société française de statistique
%D 2015
%P 180-205
%V 156
%N 4
%I Société française de statistique
%U http://geodesic.mathdoc.fr/item/JSFS_2015__156_4_180_0/
%G en
%F JSFS_2015__156_4_180_0
Rigaill, Guillem. A pruned dynamic programming algorithm to recover the best segmentations with $1$ to $K_{max}$ change-points. Journal de la société française de statistique, Tome 156 (2015) no. 4, pp. 180-205. http://geodesic.mathdoc.fr/item/JSFS_2015__156_4_180_0/