Approche hybride par segmentation
aveugle

Détection de rupture

Le mécanisme de la détection de rupture est généralement assez simple. On suppose que l’on observe le signal contenu dans une fenêtre d’analyse W de n échantillons représentés par les vecteurs x1, . . . , xn, et que l’on souhaite examiner l’hypothèse d’une rupture à l’indice t . On exploite pour cela les signaux des sous-fenêtres antérieure et postérieure, respectivement W1 = [x1, . . . , xt−1] et W2 = [xt, . . . , xn], de tailles respectives n1 = t et n2 = n−t. La figure 9.1 résume la configuration des fenêtres d’analyse mises en jeu.Les algorithmes proposés pour la détection de rupture se basent sur une modélisation stochastique des signaux des fenêtres d’analyse. Ainsi on suppose que les exemples de la fenêtre d’analyse W sont les réalisations d’une variable aléatoire gouvernée par la loi de probabilité P0(X); de même, les lois de probabilité P1(X) et P2(X) gouvernent respectivement la réalisation des exemples des fenêtres W1 et W2. 132 9.3. MÉTHODES CLASSIQUES Une taxonomie communément admise dans la littérature [49][120][250] distingue les quatre modalités suivantes pour la détection de rupture : • Approche énergétique : en se basant sur la supposition que les tours de parole sont généralement séparés par de courtes périodes de silence entre les locuteurs, certains algorithmes rudimentaires ne basent la segmentation que sur le seuillage d’un critère d’énergie court terme [249]. Cette approche, déjà contestée dans le domaine de la parole pure, n’est pas pertinente sur un signal audio quelconque, où la présence de silences intermédiaires est plutôt l’exception que la règle. • Approche par modèles : consiste à modéliser chacune des classes mises en jeu afin de classifier le contenu des fenêtres W1 et W2 sur le critère du maximum de vraisemblance [17]. En plus de ne pas être aveugle, cette approche est le processus exactement inverse de ce que nous recherchons ici puisque la classification est utilisée comme outil de segmentation. • Approche métrique : la détermination des frontières entre segments est basée sur la recherche des maxima locaux d’une métrique qui évalue la similarité entre les modèles des fenêtres W1 et W2 [217][89]. C’est l’approche que nous suivrons ici. • Approche sur critère d’information : cette approche est similaire à la précédente mais substitue aux critères métriques, nécessitant un seuil de décision, une mesure d’information appelée Critère d’Information Bayésienne (BIC, pour Bayesian Information Criterion), pour laquelle le seuil est implicite [49][45][61], comme nous le verrons par la suite. Ce critère implique en outre un autre paradigme de détection. Tandis que l’approche métrique évalue une mesure de distance entre les deux fenêtres W1 et W2, cette approche compare les hypothèses d’absence et de présence de rupture. Nous examinons cette approche plus en détail dans la section suivante. On trouve également dans la littérature plusieurs propositions d’algorithmes hybrides combinant les avantages complémentaires de deux approches ; par exemple la proposition de Kemp et al. [120] qui consiste en une approche par modèles basée sur un premier traitement par approche métrique, ou encore l’algorithme SEQDAC de Cheng et Wang [50]. De nombreux algorithmes hybrides [263][257][61][51] combinent le critère BIC à d’autres métriques comme la statistique T 2 (test basé sur les statistiques de premier et de second ordre de deux modèles probabilistes). Nous présentons dans la section suivante quelques-uns des algorithmes classiques de détection de rupture, notamment le critère BIC, très largement exploité, afin de montrer leurs implications sur la stratégie de recherche de points de rupture multiples dans un signal. Nous introduirons par la suite certains critères plus récents et plus élaborés tirant parti des résultats sur les espaces à noyaux reproduisants et les machines à noyaux dans les sections 9.4 et 9.5. 

Méthodes classiques

 Un exemple d’approche métrique

divergence de Kullback Leibler Le principe de l’approche métrique consiste à déterminer les points de rupture par une mesure de distance entre les fenêtres voisines W1 et W2, soumise à un seuil de détection adéquat. La stratégie de recherche appliquée est généralement celle des fenêtres glissantes [257][153][128][34], qui consiste à échantilloner la mesure de distance entre les fenêtres W1 et W2 de tailles fixes et égales à M, en glissant itérativement ces dernières d’un pas fixe du début à la fin de la séquence de trames. La figure 9.2 illustre le principe de la recherche par fenêtres glissantes, que nous suivons dans notre cadre expérimental. Le choix de la métrique est un problème ouvert, et les sections suivantes apporteront diverses propositions pour ce point. Siegler et al. [217] proposent par exemple l’usage de la divergence de Kullback-Leibler, définie par : KL(P | Q) = EP [log P(X) − log Q(X)] .

Critère d’Information Bayésienne (BIC)

En 1972, Akaike [11] est le premier à proposer un critère d’information théorique, appelé AIC (Akaike Information Criterion) permettant de prendre en compte la complexité du modèle dans les tests d’hypothèses impliquant un rapport de vraisemblance. Il ajoute à la mesure de vraisemblance une pénalité k mesurant le nombre de paramètres libres du modèle, soit pour un modèle donné de loi P : AIC(P) = log P(x1, . . . , xn) − k. Dans le cas d’un modèle gaussien, on dénombre le nombre suivant de paramètres libres pour la moyenne µ et la matrice de covariance Σ : k = d + d(d + 1) 2 . Par la suite, Schwarz propose [215] le Critère d’Information Bayésienne qui pénalise plus fortement les modèles construits sur une large collection d’exemples en ajoutant un facteur multiplicatif log n au facteur de pénalité ; on y joint généralement un facteur multiplicatif λ de manière à contrôler le compromis entre la vraisemblance et la complexité du modèle, bien que celui-ci soit absent de la proposition originale de Schwartz. Ainsi le critère devient : BIC(P) = log P(x1, . . . , xn) − λ k 2 log n. Schwarz justifie ce critère par le fait qu’il est asymptotiquement optimal pour le choix de modèle, tandis que le critère AIC à tendance à choisir le modèle le plus complexe lorsque n → ∞. Rissanen montre par ailleurs [198] que, pour λ = 1, le critère BIC est égal à la MDL (Minimum Description Length), grandeur en Théorie de l’Information décrivant le nombre de bits minimum nécessaires pour coder le modèle, ce qui rejoint la notion de complexité du modèle. Le critère fut plus tard introduit dans le contexte de la détection de rupture [49]. Le test d’hypothèse consiste à évaluer la différence des valeurs BIC entre l’hypothèse de rupture et de non-rupture, sur des modèles gaussiens ; soit : ∆BIC(t) = R(t) + 1 2 λ Å d + d(d + 1) 2 ã log n. (9.3) où, R(t) est le critère GLR introduit dans l’équation 9.2. Les auteurs revendiquent la supériorité du critère ∆BIC sur les approches métriques, du fait que celui-ci prend en compte la complexité des modèles et permet ainsi d’appliquer un seuil naturel de décision à 0. Cependant, malgré la valeur théorique λ = 1, le facteur λ constitue en pratique un paramètre supplémentaire à déterminer [227][183], qui se substitue au seuil de décision. La taille de la fenêtre d’analyse est un point essentiel dans le comportement du critère BIC et doit fixer un compromis entre les deux contraintes suivantes : • Une fenêtre trop large est susceptible de contenir plus d’un point de rupture, ce qui affecte directement le taux d’omissions (MD, Missed Detections). • Une fenêtre trop étroite comporte peu d’exemples, ce qui affaiblit l’estimation des modèles. 135 CHAPITRE 9. APPROCHE HYBRIDE PAR SEGMENTATION AVEUGLE Cette seconde contrainte constitue l’une des limites du critère BIC. En effet, ce dernier est choisi pour son comportement asymptotique optimal, mais le facteur de pénalité propre au critère (k log n) favorise les modèles les plus simples [263] lorsque le modèle est estimé sur un nombre restreint d’exemples. De plus, le fait qu’il soit exclusivement basé sur des statistiques du second ordre (les matrices de covariances) accroît cette faiblesse, puisque l’estimation du modèle se trouve ellemême pénalisée [227][44]. On trouve ainsi plusieurs propositions d’approches hybrides appliquant une première étape de détection moins fiable mais plus simple, dont le seuil est fixé de manière à minimiser le taux d’omissions, basée par exemple sur le critère GLR [108], la statistique T 2 [264] [263], ou une approche métrique [61][50]. Un autre inconvénient majeur du critère BIC est sa complexité. En effet, le calcul des inverses des matrices de covariances est une opération lourde (de l’ordre de O( n 3 6 ) en utilisant la décomposition de Cholesky). On peut cependant réduire ce coût par des heuristiques, comme la mise à jour incrémentale des matrices de covariance [45][218]. Nous nous contenterons de suivre l’exemple d’Ajmera et al. [10] qui n’exploitent que des matrices de covariance diagonales. Il est important de préciser que l’algorithme BIC s’accompagne à l’origine [49] d’une stratégie de recherche par maxima locaux par élargissement itératif des fenêtres d’analyse, qui permet d’affiner progressivement les modèles de distributions. Cependant, s’il est théoriquement plus pertinent, cet algorithme n’est pas adapté à un traitement en ligne (ou online, c’est-à-dire avec un retard de réponse borné) des données ; aussi nous préférons n’employer que la méthode des fenêtres glissantes, ce qui nous permet en outre de comparer les différents critères de distance sur les mêmes bases méthodologiques.

 SVM à une classe

L’approche précédente tire parti du kernel trick en étendant la pertinence du modèle gaussien par son application dans un espace de dimension supérieure. Nous avons vu que les machines à noyaux reposent sur la conjonction du kernel trick et du principe de maximisation de la marge, qui implique à la fois la minimisation du Risque Structurel et une sélection parcimonieuse des exemples essentiels pour la fonction de décision. Ce second principe n’est pas appliqué dans l’approche précédente. Nous présentons dans cette section les SVM à une classe, qui adaptent le formalisme des SVM pour la caractérisation du support d’une distribution donnée. Après en avoir présenté le principe, nous verrons comment ce dernier peut être exploité pour la détection de rupture. 137 CHAPITRE 9. APPROCHE HYBRIDE PAR SEGMENTATION AVEUGLE 9.5.1 Principe des SVM à une classe Le problème posé par Schölkopf et al. dans [209] et [212] consiste à estimer à partir de réalisations x1, . . . , xn le support d’une distribution de probabilité P donnée, c’est-à-dire à déterminer un sous-ensemble S de l’espace d’origine tel qu’on ait idéalement : P(x) > 0 ∀ x ∈ S P(x) = 0 ∀ x ∈/ S. Le problème se heurte aux mêmes écueils que le problème de classification. En effet, il est possible d’apprendre « par cœur » la distribution des exemples d’apprentissage (voir figure 9.3(a)) mais on se trouve alors en situation de sur-apprentissage et l’ensemble déterminé ne pourra se généraliser correctement sur des données inconnues. Il est donc nécessaire de lisser la frontière de l’ensemble S en régularisant le problème ; la figure 9.3(b) représente un exemple de solution mieux régularisée. Le principe de minimisation du risque structurel nous permet à nouveau de faire face à cette contrainte.

Rapport de vraisemblance par SVM1C (LLR)

Loosli et al. [137] exploitent les SVM à une classe sur la base du Rapport de Vraisemblance Généralisé (GLR), présenté précédemment dans la section 9.3.2. Ils adaptent ce dernier en excluant du test d’hypothèses la fenêtre globale W et son modèle P0(X), et supposent dans tous les cas que les échantillons de la fenêtres W1 sont décrits par le modèle P1(X). Le test d’hypothèses se résume ainsi à évaluer l’égalité entre les distributions P1 et P2, ce qui revient à appliquer une approche métrique.