Soit un signal réel, provenant d'observations recueillies au cours des instants , présentant des changements dans la distribution. En notant la loi de probabilité de , la distribution de vérifie :
avec étant les vrais instants de ruptures (on note avec la convention et ). On cherche à estimer ces instants de ruptures à l'aide d'un algorithme.
Dans le cas de la détection de rupture dans la moyenne, le modèle est :
avec est la fonction de régression et est un bruit d'espérance nulle et de variance . La fonction de régression est supposée constante par morceaux avec des discontinuités à chaque vrai instant de ruptures .
Dans le cas de la détection de ruptures dans la distribution, on recode les observations initiales par de nouvelles observations définies par où est un noyau symétrique et semi-défini positif (en) (par exemple : est le noyau linéaire ; autre exemple : est le noyau Gaussien de paramètre ). Pour un noyau symétrique et semi-défini positif , le théorème de Moore-Aronszahn assure l'existence d'un espace de Hilbert à noyau reproduisant (RKHS en anglais) de noyau reproduisant .
Le modèle est :
avec est la fonction de régression et est un bruit d'espérance nulle et de variance . De plus, appartiennent à . La fonction de régression est supposée constante par morceaux avec des discontinuités à chaque vrai instant de ruptures .
La résolution du problème de détection de ruptures utilise le formalisme de la sélection de modèle : chaque segmentation candidate (i.e. liste d'instants de ruptures candidats) est reliée à un modèle qu'il faut choisir. Nous présentons deux approches : l'une utilisant le principe de la programmation dynamique et l'autre l'heuristique de segmentation binaire dans le cadre classique de la détection de ruptures dans la moyenne puis dans le cas général de la détection de ruptures dans la distribution. Pour chacune de ces deux méthodes, nous présentons les algorithmes permettant de calculer une segmentation en D segments optimisant un critère (ici, le risque empirique).
Nous présentons les notations communes aux deux méthodes puis celles qui leur sont spécifiques :
Notation commune
l'ensemble des segmentions en D segments .
Notations pour le cas de la détection de ruptures dans la moyenne
- et .
- : est l'ensemble des vecteurs constants par morceaux sur les segments de m.
- Estimateur du risque empirique : .
Notations pour le cas de la détection de ruptures dans la distribution
- et .
- pour avec .
- : est l'ensemble des vecteurs constants par morceaux sur les segments de m.
- Norme dans : .
- Estimateur du risque empirique : .
Les méthodes proposées ci-dessous utilisent le risque empirique comme critère à minimiser ( pour la détection de ruptures dans la moyenne ; pour la détection de ruptures dans la distribution). Pour le noyau linéaire ,
, ceux dans le cadre classique se déduisent du cas des noyaux par le biais de : donc on ne présentera les algorithmes que dans le cas des noyaux.
La méthode de la programmation dynamique utilise le principe d'optimalité de Bellman : toute solution optimale s'appuie elle-même sur des sous-problèmes résolus localement de façon optimale. On utilise cette méthode exacte pour récupérer pour la meilleure segmentation en D segments minimisant le risque empirique i.e. :
Nous présentons dans cette section l'algorithme de programmation dynamique appliquée au problème de détection de ruptures. Dans un premier temps, nous exprimons le risque empirique en fonction du noyau k et de à l'aide des deux résultats suivants ci-dessous.
On montre tout d'abord que, pour , pour , .
Démonstration
Pour , notons, pour , la valeur commune de et, pour , ,
Pour ,
Ainsi, est minimale si et seulement si pour chaque .
On montre que, pour ,
avec, pour ,
Démonstration
KPGD est l'implémentation du principe de la programmation dynamique à noyau
[1],[2] appliquée au problème de détection de ruptures. Elle prend en paramètre la matrice de coût et elle renvoie .
,
algorithme KPGD ()
for do
for do
end for
end for
Fin algorithme
avec .
La sélection de modèle permet de récupérer un estimateur du nombre de segments par heuristique de pente[3]. On obtient ainsi un estimateur .
L'heuristique de segmentation binaire est une méthode, fonctionnant par dichotomie, permettant de récupérer un minimiseur local du risque empirique . Nous illustrons sur un exemple le fonctionnement de l'algorithme utilisant le principe de la segmentation binaire :
- Etape 1 : A l'itération , on cherche qui minimise le risque empirique avec pour avec :
est notre premier instant de ruptures estimé noté .
- Etape 2 : A l'itération on , on cherche minimisant le risque empirique sur et respectivement. Par exemple,
avec . Puis on choisit parmi les instants de ruptures candidats celui qui minimise le risque empirique
et on le note . Puis, on continue récursivement.
Ainsi, au bout de itérations, on récupère une segmentation en D=k+1 segments vérifiant :
avec l'espace des segmentations en D segments où les instants de ruptures estimés ont été calculés aux itérations précédentes.
Une méthode alternative de segmentation binaire avec temps d'arrêt[4] permet d'estimer le nombre de segments et donc de récupérer un estimateur de .