Détection de ruptures

Nous présentons les notations communes aux deux méthodes puis celles qui leur sont spécifiques :

Notation commune

${\displaystyle {\mathcal {M}}(D)}$ l'ensemble des segmentions ${\displaystyle m=\{\{\tau _{0},\dots ,\tau _{1}-1\},\{\tau _{1},\dots ,\tau _{2}-1\},\dots ,\{\tau _{D-1},\dots ,\tau _{D}-1\}\}}$ en ${\displaystyle D}$ segments ${\displaystyle \left({\text{avec la convention}}~\tau _{0}=1,~\tau _{D}=T+1\right)}$.

Notations pour le cas de la détection de ruptures dans la moyenne

• ${\displaystyle X=(X_{1},\dots ,X_{T})}$ et ${\displaystyle s=(s_{1},\dots ,s_{T})}$.
• ${\displaystyle S_{m}^{\mathbb {R} }=\{u\in \mathbb {R} ^{T}:u_{\tau _{0}}=\dots =u_{\tau _{1}-1}\neq u_{\tau _{1}}=\dots =u_{\tau _{2}-1}\neq \dots \neq u_{\tau _{D-1}}=\dots u_{\tau _{D}-1}\}}$ : ${\displaystyle S_{m}^{\mathbb {R} }}$ est l'ensemble des vecteurs ${\displaystyle u\in \mathbb {R} ^{T}}$ constants par morceaux sur les segments de ${\displaystyle m}$.
• Estimateur du risque empirique : ${\displaystyle {\hat {s}}_{m}={\underset {u\in S_{m}^{\mathbb {R} }}{\operatorname {arg\,min} }}\|X-u\|_{2}^{2}}$.

Notations pour le cas de la détection de ruptures dans la distribution

• ${\displaystyle Y=(Y_{1},\dots ,Y_{T})}$ et ${\displaystyle \mu ^{*}=(\mu _{1}^{*},\dots ,\mu _{T}^{*})}$.
• ${\displaystyle Y_{s}^{e}=\{Y_{s},\dots ,Y_{e}\}}$ pour ${\displaystyle s<e}$ avec ${\displaystyle (s,e)\in [\![1,T]\!]^{2}}$.
• ${\displaystyle S_{m}^{\mathcal {H}}=\{u\in {\mathcal {H}}^{T}:u_{\tau _{0}}=\dots =u_{\tau _{1}-1}\neq u_{\tau _{1}}=\dots =u_{\tau _{2}-1}\neq \dots \neq u_{\tau _{D-1}}=\dots u_{\tau _{D}-1}\}}$ : ${\displaystyle S_{m}^{\mathcal {H}}}$ est l'ensemble des vecteurs ${\displaystyle u\in {\mathcal {H}}^{T}}$ constants par morceaux sur les segments de ${\displaystyle m}$.
• Norme dans ${\displaystyle {\mathcal {H}}^{T}}$ : ${\displaystyle \forall h\in {\mathcal {H}}^{T},~\|h\|_{{\mathcal {H}}^{T}}^{2}=\sum _{i=1}^{T}\|h_{i}\|_{\mathcal {H}}^{2}}$.
• Estimateur du risque empirique : ${\displaystyle {\hat {\mu }}_{m}={\underset {u\in S_{m}^{\mathcal {H}}}{\operatorname {arg\,min} }}\|Y-u\|_{{\mathcal {H}}^{T}}^{2}}$.

Les méthodes proposées ci-dessous utilisent le risque empirique comme critère à minimiser (${\displaystyle \|X-{\hat {s}}_{m}\|_{2}^{2}}$ pour la détection de ruptures dans la moyenne ; ${\displaystyle \|Y-{\hat {\mu }}_{m}\|_{{\mathcal {H}}^{T}}^{2}}$ pour la détection de ruptures dans la distribution). Pour le noyau linéaire ${\displaystyle k^{1}}$, ${\displaystyle \|X-{\hat {s}}_{m}\|_{2}^{2}=\|Y-{\hat {\mu }}_{m}\|_{{\mathcal {H}}^{T}}^{2}}$, les méthodes utilisées dans le cadre classique se déduisent de celles du cas des noyaux par le biais de ${\displaystyle k^{1}}$ : 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 ${\displaystyle D\in [\![1,D_{max}]\!]}$ la meilleure segmentation en ${\displaystyle D}$ segments minimisant le risque empirique i.e. :

${\displaystyle {\begin{aligned}{\hat {m}}_{D}={\underset {m\in {\mathcal {M}}(D)}{\operatorname {arg\,min} }}\|Y-{\hat {\mu }}_{m}\|_{{\mathcal {H}}^{T}}^{2}.\end{aligned}}}$

Nous présentons dans cette section l'algorithme de programmation dynamique appliquée au problème de détection de ruptures[3] - [4]. Dans un premier temps, nous exprimons le risque empirique ${\displaystyle \|Y-{\hat {\mu }}_{m}\|_{{\mathcal {H}}^{T}}^{2}}$ en fonction du noyau ${\displaystyle k}$ et de ${\displaystyle \{X_{i}\}_{i\in [\![1,T]\!]}}$ à l'aide des deux résultats suivants ci-dessous.

On montre tout d'abord que, pour ${\displaystyle m\in {\mathcal {M}}(D),~d\in [\![1,D-1]\!]}$, pour ${\displaystyle i\in [\![\tau _{d},\tau _{d+1}-1]\!]}$, ${\displaystyle \left({\hat {\mu }}_{m}\right)_{i}={\frac {1}{\tau _{d+1}-\tau _{d}}}\sum _{j=\tau _{d}}^{\tau _{d+1}-1}Y_{j}}$.

On montre que, pour ${\displaystyle m\in {\mathcal {M}}(D)}$,

${\displaystyle {\begin{aligned}\|Y-{\hat {\mu }}_{m}\|_{{\mathcal {H}}^{T}}^{2}=\sum _{d\in [\![1,D-1]\!]}C_{\tau _{d},\tau _{d+1}},\end{aligned}}}$

avec, pour ${\displaystyle ~(\tau ,\tau ^{'})\in [\![1,T]\!]^{2},~\tau <\tau ^{'}}$, ${\displaystyle C_{\tau ,\tau ^{'}}=\sum _{i=\tau }^{\tau ^{'}-1}k(X_{i},X_{i})-{\frac {1}{\tau ^{'}-\tau }}\sum _{i=\tau }^{\tau ^{'}-1}\sum _{j=\tau }^{\tau ^{'}-1}k(X_{i},X_{j}).}$

KPGD est l'implémentation du principe de la programmation dynamique à noyau appliquée au problème de détection de ruptures. Elle prend en paramètre la matrice de coût ${\displaystyle C=(C_{i,j})_{(i,j)\in [\![1,T]\!]}(i<j)}$ et elle renvoie ${\displaystyle \{{\hat {m}}_{D}\}_{D\in [\![1,D_{max}]\!]}}$.

 algorithme KPGD (${\displaystyle C}$) 
   for ${\displaystyle d\in [\![2,D_{max}]\!]}$ do
     for ${\displaystyle \tau ^{'}\in [\![d,T]\!]}$ do
       ${\displaystyle L_{d,\tau ^{'}}=\min _{\tau \leq \tau ^{'}}\{L_{d-1,\tau }+C_{\tau ,\tau ^{'}+1}\}}$
       ${\displaystyle m_{d,\tau ^{'}+1}={\underset {\tau \leq \tau ^{'}}{\operatorname {arg\,min} }}\{L_{d-1,\tau }+C_{\tau ,\tau ^{'}+1}\}}$
     end for        
   end for
 Fin algorithme

avec ${\displaystyle \forall \tau >1,L_{1,\tau }=C_{1,\tau }}$.

La sélection de modèle[4] permet de récupérer ${\displaystyle {\hat {D}}}$ un estimateur du nombre de segments ${\displaystyle D^{*}}$. ${\displaystyle {\hat {D}}}$ est défini par

${\displaystyle {\begin{aligned}{\hat {D}}={\underset {D\in [\![1,D_{max}]\!]}{\operatorname {arg\,min} }}\{\|Y-{\hat {\mu }}_{{\hat {m}}_{D}}\|_{{\mathcal {H}}^{T}}^{2}+pen({\hat {m}}_{D})\},\end{aligned}}}$

avec ${\displaystyle \mathrm {pen} ({\hat {m}}_{D})={\frac {CD}{n}}\left(1+\log \left({\frac {n}{D}}\right)\right)}$. La méthode utilisée pour calibrer la constante ${\displaystyle C}$ est l'heuristique de pente[5]. On obtient ainsi un estimateur ${\displaystyle {\hat {m}}_{\hat {D}}}$.

L'heuristique de segmentation binaire[6] est une méthode, fonctionnant par dichotomie, permettant de récupérer un minimiseur local ${\displaystyle {\hat {m}}_{D}}$ du risque empirique ${\displaystyle \|Y-{\hat {\mu }}_{m}\|_{{\mathcal {H}}^{T}}^{2}}$. Plus précisément, la segmentation binaire cherche à la première itération l'indice ${\displaystyle j_{1}\in [\![2,T-1]\!]}$ de l'instant de ruptures candidat qui minimise le risque empirique ${\displaystyle \|Y-{\hat {\mu }}_{m}\|_{{\mathcal {H}}^{T}}^{2}}$ : cet indice est l'indice de notre premier instant de ruptures estimé. Puis, elle détermine récursivement, à la deuxième itération, deux instants de ruptures candidats ${\displaystyle j_{2},j_{3}}$ sur chacun des segments délimités par les instants de ruptures estimés. Elle retient comme second instant de ruptures estimé celui (parmi ces deux instants de ruptures candidats) qui minimisent le risque empirique. Puis, on procède de la même manière pour les itérations suivantes. Nous illustrons sur un exemple le fonctionnement de l'algorithme utilisant le principe de la segmentation binaire :

• Étape 1 : A l'itération ${\displaystyle k=1}$, on cherche ${\displaystyle j_{1}}$ qui minimise le risque empirique ${\displaystyle \|Y-{\hat {\mu }}_{m_{1}}\|_{{\mathcal {H}}^{T}}^{2}}$ avec ${\displaystyle m_{1}=\{1,j,T\}}$ pour ${\displaystyle j\in [\![2,T-1]\!]}$ avec :

${\displaystyle {\begin{aligned}\|Y-{\hat {\mu }}_{m_{1}}\|_{{\mathcal {H}}^{T}}^{2}=C_{1,j}+C_{j,T}.\end{aligned}}}$

${\displaystyle j_{1}}$ est notre premier instant de ruptures estimé noté ${\displaystyle {\hat {\tau }}_{1}}$.

• Étape 2 : A l'itération on ${\displaystyle k=2}$, on cherche ${\displaystyle j_{2},~j_{3}}$ minimisant le risque empirique sur ${\displaystyle [\![2,{\hat {\tau }}_{1}-1]\!]}$ et ${\displaystyle [\![{\hat {\tau }}_{1}+1,T-1]\!]}$ respectivement. Par exemple,

${\displaystyle j_{2}={\underset {j\in [\![2,{\hat {\tau }}_{1}-1]\!]}{\operatorname {arg\,min} }}\|Y_{1}^{{\hat {\tau }}_{1}}-{\hat {\mu }}_{m_{2}}\|_{{\mathcal {H}}^{{\hat {\tau }}_{1}}}^{2},}$

avec ${\displaystyle m_{2}=(1,j,{\hat {\tau }}_{1},T)}$. Puis on choisit parmi les instants de ruptures candidats ${\displaystyle j_{2},~j_{3}}$ celui qui minimise le risque empirique ${\displaystyle \|Y-{\hat {\mu }}_{m}\|_{{\mathcal {H}}^{T}}^{2}}$
et on le note ${\displaystyle {\hat {\tau }}_{2}}$ . Puis, on continue récursivement.

Ainsi, au bout de ${\displaystyle k}$ itérations, on récupère une segmentation en ${\displaystyle D=k+1}$ segments vérifiant :

${\displaystyle {\begin{aligned}{\hat {m}}_{D}={\underset {m\in {\mathcal {M}}_{D}({\hat {\tau }}_{1},\dots ,{\hat {\tau }}_{D-2})}{\operatorname {arg\,min} }}\|Y-{\hat {\mu }}_{m}\|_{{\mathcal {H}}^{T}}^{2},\end{aligned}}}$

avec ${\displaystyle {\mathcal {M}}_{D}({\hat {\tau }}_{1},\dots ,{\hat {\tau }}_{D-2})}$ l'espace des segmentations en ${\displaystyle D}$ segments où les instants de ruptures estimés ${\displaystyle {\hat {\tau }}_{1},\dots ,{\hat {\tau }}_{D-2}}$ ont été calculés aux itérations précédentes.

Une méthode alternative de segmentation binaire avec temps d'arrêt[7] permet d'estimer le nombre de segments et donc de récupérer un estimateur ${\displaystyle {\hat {m}}_{\hat {D}}}$ de ${\displaystyle m^{*}}$ .