Analyse en composantes indépendantes

Pour les articles homonymes, voir ACI.

L'analyse en composantes indépendantes est une méthode d'analyse des données (voir aussi Exploration de données) qui relève des statistiques, des réseaux de neurones et du traitement du signal. Elle est notoirement et historiquement connue en tant que méthode de séparation aveugle de source mais est aujourd'hui appliquée à divers problèmes.

Historique

La première formulation du problème a été effectuée en 1985 par des chercheurs en neurosciences et traitement du signal pour modéliser biologiquement le codage du mouvement^[1]. Ces travaux ouvraient la voie à la formulation du problème de séparation de source aveugle^[2]. Une communauté a émergé autour de cette thématique dans la seconde moitié des années 1980 essentiellement en France et en Finlande^[3]. La communauté française du traitement du signal adopta un formalisme statistique tandis que les chercheurs finlandais visaient à étendre l'analyse en composantes principales au moyen d'un formalisme connexionniste. L'algorithme proposé en 1985 était étonnamment robuste mais les explications théoriques de ses propriétés étaient incomplètes. Un premier formalisme du problème de séparation de source aveugle, ainsi qu'un algorithme permettant d'en obtenir une solution, a été proposé par C. Jutten et J. Hérault en 1991^[2]. La formalisation mathématique dans le cas le plus simple (mélange linéaire instantané) a été effectuée en 1994 par P. Comon^[4] aboutissant au concept d' analyse en composantes indépendantes.

La recherche dans ce domaine devint très active à partir des années 1990 et des chercheurs du monde entier s'intéressèrent au problème. En plus des équipes européennes précédemment évoquées, des chercheurs américains et japonais s'intéressèrent au lien entre l'ACI et le codage neuronal. Il existe plusieurs ouvrages spécialisés donnant les détails de certaines solutions proposées^[5], ainsi que les développements théoriques s'y rattachant.

Une conférence internationale portant spécifiquement sur le sujet existe depuis 1999. Devant avoir initialement lieu tous les 18 mois, elle est désormais annuelle. Les premières éditions ont eu lieu à Aussois (France, 1999), Helsinki (Finlande, 2000), San Diego (Californie, 2001), Nara (Japon, 2003), Grenade (Espagne, 2004), Charleston (Caroline du Sud, Etats Unis, 2006), Londres (Royaume Uni, 2007) et Parati (Brésil, 2009).

Séparation de source (problème de la soirée cocktail)

Article détaillé : Méthode de séparation aveugle de source.

L'illustration classique de la séparation de sources est le problème de la soirée cocktail (cocktail party problem). Lors d'une telle soirée, on dispose P microphones dans une salle dense, où N personnes discutent par groupes de tailles diverses. Chaque microphone enregistre la superposition des discours des personnes à ses alentours et le problème consiste à retrouver la voix de chaque personne (« débarrassée » des autres voix considérées comme parasites).

Lors d'une soirée cocktail, bien que les discussions soient multiples et mêlées, un humain est capable de séparer le flux sonore qui l'intéresse (la voix de son interlocuteur) et d'ignorer les autres.

L'ACI permet de résoudre ce problème en considérant simplement que les personnes qui parlent à un instant donné ont des discours « indépendants ». Il ne s'agit pas de prendre en compte la sémantique de ces discours (on peut en effet espérer que certaines voix soient concordantes à ce niveau!) ni même l'acoustique (ce qui serait faux, ne serait-ce que lorsque les interlocuteurs ont des langues identiques...), mais de les considérer comme des signaux aléatoires statistiquement indépendants. Au contraire d'une chorale, les gens qui parlent en même temps à un instant donné émettent des sons indépendants.

La théorie assurant ce résultat pose néanmoins quelques hypothèses, en particulier que « le nombre de micros est supérieur ou égal au nombre de personnes ». Symétriquement, il reste aussi des indéterminations sur le résultat (les voix séparées). Celles-ci peuvent être interprétées de la façon suivante:

• on ne peut pas attribuer les voix aux personnes avec la seule connaissance des signaux retrouvés (mais un auditeur humain le pourrait). Autrement dit, on ne connaît pas l'ordre des signaux retrouvés.
• on ne connaît pas l'intensité de la voix des locuteurs. Celle-ci sera attribuée arbitrairement et un auditeur humain ne pourrait se fier qu'au ton de la voix et à la connaissance de la personne pour le déterminer.

Pour des raisons historiques et pédagogiques, l'ACI est souvent introduite comme permettant de résoudre le problème de séparation de sources. Néanmoins, il existe d'autres méthodes pour résoudre ce problème, ne faisant pas appel strictement à l'hypothèse d'indépendance statistique entre sources (la parcimonie par exemple).

Formalisme mathématique

Dans le cas le plus simple (modèle linéaire instantané non bruité), la théorie est très bien maîtrisée. Néanmoins, ce modèle de mélange semble souvent trop restrictif pour modéliser les cas pratiques. Les travaux sur les modèles de mélange plus complexes font l'objet de recherches actives à ce jour.

Modèle linéaire instantané non bruité^[4]

Quand l'information mutuelle est choisie comme fonction de contraste particulière, l'analyse en composantes indépendantes du vecteur aléatoire $\underline{x}=\left(x_1,x_2,\dots,x_p\right )$ revient à identifier le modèle génératif linéaire instantané non bruité suivant:

$\underline{x}=A\underline{s}$

où les composantes s_i du vecteur $\underline{s}=\left(s_1,s_2,\dots,s_n\right )$ sont mutuellement indépendantes et la matrice A est de taille fixe $p\times n$. Néanmoins, les conditions d'identifiabilité suivantes doivent être vérifiées pour que l'on soit assuré de pouvoir retrouver le modèle (théoriquement):

• au plus une des sources (composantes de $\underline{s}$) peut suivre une distribution normale (gaussienne),
• le rang de la matrice A doit être égal au nombre de sources (à retrouver).

La première condition résulte de la nullité des moments et cumulants d'ordre supérieur à deux pour une distribution gaussienne. L'indépendance revient alors à une simple décorrélation et l'hypothèse d'indépendance statistique ne permet pas de séparer les sources gaussiennes. Il est cependant possible de retrouver les autres sources non gaussiennes.

La seconde condition impose d'observer au moins autant de données qu'il y a de sources à identifier. Les travaux sur les représentation parcimonieuses ont cependant montré qu'il était possible d'extraire plus de sources que d'observations disponibles. Réciproquement, il est toujours possible de réduire la dimension des observations disponibles, au moyen d'une analyse en composantes principales (ACP) par exemple.

Quand ces deux conditions d'identifiabilité sont vérifiées, il reste cependant deux indéterminations:

• Changer l'ordre des sources ne modifie pas leur indépendance mutuelle. En conséquence, les sources identifiées par ACI ne sont pas ordonnées (au contraire de l'ACP où les sources sont ordonnées selon les valeurs propres de la matrice de variance/covariance)
• L'indépendance statistique est conservée quand les composantes sont multipliées par une constante non nulle. Autrement dit, il y a une indétermination sur l'amplitude des sources.

Ces deux indéterminations ne sont pas propres au modèle linéaire instantané non bruité et se vérifient dans le cas général.

Modèle linéaire instantané bruité

Plus réaliste que le modèle précédent, cela revient à identifier le modèle suivant:

$\underline{x}=A\underline{s}+\sigma$

où σ est le bruit.

Modèle linéaire non instantané

Le mélange peut être convolutif. Néanmoins on peut alors se ramener à un modèle linéaire, en utilisant une transformée de Fourier par exemple.

Mélanges non linéaire

Il s'agit du cas le plus général où les observations résultent d'une transformation non linéaire des sources:

$\underline{x}=F(\underline{s})$

où F(.) est une fonction non linéaire quelconque. Nous ne connaissons pas de méthode générale dans ce cas. Certains auteurs ont néanmoins proposé des méthodes pour des cas particuliers. Il s'agit d'un domaine de recherche très actif. Dans le cas le plus général, le problème étant mal-posé la solution est loin d'être unique^[6].

Principaux algorithmes

Le but de cette section est de donner les principales idées des algorithmes les plus connus permettant de résoudre le problème d'ACI. Ces algorithmes ont été choisis de manière à présenter un panel varié d'approches. On trouvera de nombreuses autres méthodes dans la littérature scientifique.

Nous considérons ici le modèle linéaire instantané non bruité^[4] et cherchons une estimation y_i des sources indépendantes s_i ainsi qu'une matrice de séparation W vérifiant:

$\underline{y}=W\underline{x}=WA\underline{s}$

Algorithme HJ

Architecture de l'algorithme HJ^[1].

Le premier algorithme d'ACI (du nom de ses auteurs^[1],[2]) procède d'une approche neuromimétique: il s'agit d'une utilisation des outils du traitement du signal pour modéliser un phénomène inspiré du fonctionnement neuronal. Cet algorithme était de type Robins-Monro, et recherchait itérativement des zéros communs de deux fonctions^[7]. Il est basé sur un réseau de neurones récursif dont les poids sont les termes non diagonaux de la matrice de séparation W, les termes diagonaux étant contraints à la nullité. L'estimation des sources est ainsi donnée par:

$\underline{y}=(I+W)^{-1} \underline{x}$

Avec la règle d'adaptation suivante pour les termes non diagonaux:

$\Delta w_{ij}=f(y_i)\times g(y_j)$

f(.) et g(.) étant des fonctions non linéaires impaires différentes à choisir en fonction des densités de probabilité des sources à estimer. Des travaux ultérieurs^[8] ont justifié la forme de cette règle d'apprentissage et ont montré que la fonction non linéaire devait être choisie au sens du maximum de vraisemblance. La mesure d'indépendance sous-jacente à cet algorithme est l'annulation des cumulants d'ordre supérieur.

Maximisation de Contraste (CoM)

Cette famille d'algorithmes a été proposée par Comon en 1991. Ces algorithmes procèdent en balayant toutes les paires de sorties à tour de rôle. L'algorithme CoM peut calculer soit tous les cumulants des observations (comme JADE), soit à la demande, à chaque fois qu'une rotation optimale est calculée. Le choix peut être fait de manière a minimiser la complexité numérique.

Plusieurs versions ont été proposées, suivant le contraste utilisé. En 1991, il s'agissait par exemple de la somme des modules carrés des cumulants marginaux des sorties: ce contraste est maintenant appelé CoM2. Plus tard, un autre contraste, CoM1, a été proposé par Moreau: la somme des modules des cumulants marginaux des sorties. Lorsque les sources ont des cumulants marginaux toutes de même signe, il a été montré que la valeur absolue peut être retirée. Cette simplification a donné lieu à une autre solution algébrique compacte, développée par Comon.

D'autres formes plus générales de contraste basés sur les cumulants ont été ensuite proposées dans la littérature.

JADE

(Joint Approximate Diagonalization of Eigenmatrices)

Un tenseur de cumulants (à l'ordre quatre) est une matrice à quatre dimensions contenant tous les cumulants croisés d'ordre quatre. C'est aussi une application linéaire d'un espace de matrice de taille NxN dans un autre espace de matrice de même taille. La diagonalisation de cette application linéaire permet d'effectuer la séparation voulue sous certaines conditions^[9]. En effet, l'indépendance statistique est vue ici comme la recherche à tendre vers la nullité de tous les moments et cumulants (à tous les ordres), ce qui revient à annuler tous les éléments non diagonaux de la matrice associée à l'application linéaire sus-citée. Cardoso et Souloumiac ont proposé^[10] une méthode de diagonalisation jointe permettant de mettre en pratique ce principe. Cela revient à minimiser la somme du carrés de tous les cumulants (à l'ordre quatre) « hors diagonale » (cumulant entre deux signaux différents). En pratique, JADE nécessite le calcul de tous les cumulants d'ordre quatre et a donc une complexité en O(n⁴).

Fast-ICA

Hyvarinen et Oja proposent d'estimer les composantes indépendantes au moyen d'une mesure de « non gaussianité »^[5]. En effet, le théorème central limite stipule que la somme de variables indépendantes tend asymptotiquement vers une distribution normale. Dans le cas considéré, les estimations sont une telle somme de variables indépendantes ($\underline{y}=WA\underline{s}$) et tendent donc vers une distribution gaussienne. En cherchant à maximiser la non gaussianité de $\underline{y}$, chacune de ses composantes tendra vers une estimation des sources indépendantes (aux deux indéterminations près). Plusieurs mesures de « non gaussianité » ont été proposées, la plus usitée étant la néguentropie qui est la différence entre l'entropie d'une variable gaussienne et l'entropie du vecteur mesuré. Hyvarinen a proposé différentes approximations de cette mesure permettant une mise en œuvre algorithmique du principe exposé.

Pour éviter que toutes les estimations convergent vers la même source, il est nécessaire d'imposer l'orthogonalité des y_i (sous contrainte de blanchiment, cela revient à décorreler les données, au moyen d'une analyse en composantes principales par exemple). Deux méthodes existent pour imposer cette orthogonalité. La version dite « par déflation » estime itérativement les sources et orthogonalise chaque estimation au moyen d'un procédé de Gram-Schmidt. La version « symétrique » orthogonalise simultanément toutes les estimations.

« Fast-ICA » met ainsi en évidence de forts liens entre l'analyse en composantes indépendantes et la poursuite de projection.

Infomax

Formulé par Linsker^[11], ce principe stipule que l'implémentation d'un modèle des capacités cognitives des mammifères au moyen d'un réseaux de neurones artificiel doit être telle que le taux d'information transmis d'une couche de neurones à la suivante soit maximal. Ce taux d'information peut notamment être mesuré par l'entropie lorsque l'on se place dans le formalisme de Shannon.

Nadal et Parga ont montré^[12] que sous certaines conditions, ce principe était équivalent au principe de réduction de redondance^[13] qui énonce que le but des systèmes sensoriels des mammifères est de coder efficacement les stimuli (visuels, sonores...). En se plaçant à nouveau dans le formalisme de Shannon, cela revient à minimiser la redondance d'information de leur environnement et obtenir un codage factoriel (i.e un codage qui minimise les dépendances statistiques entre dimensions, aussi appelé codage à entropie minimale).

Bell et Sejnowsky ont exploité cette équivalence^[14] en l'écrivant:

$\frac{\partial I(y,x)}{\partial w} = \frac{\partial H(y)}{\partial w}$

où $I(y,x)\,$ est l'information mutuelle entre les sorties $y\,$ et les entrées $x\,$ d'un réseau de neurones, $w\,$ les paramètres de ce réseau et $H(y)\,$ l'entropie des sorties. Le relation ci-dessus exprime exactement que rendre maximale l'information mutuelle des sorties des réseaux (i.e obtenir un code factoriel le plus efficace possible) est identique à rendre maximale l'information qui « passe » à travers le réseau.

Ils en déduisirent une règle d'apprentissage des paramètres du réseau qui, après quelques simplifications et l'exploitation d'une règle du type « gradient relatif »^[15], revient à:

ΔW = [I − Ktanh(y)y^T − yy^T]W

K étant une matrice diagonale dont les éléments valent 1 pour les sources sur-gaussiennes et -1 pour les sources sous-gaussiennes.

Il a été montré une équivalence de cette approche et de l'approche par maximum de vraisemblance.

Voir aussi

• analyse en composantes principales
• les cartes auto organisatrices
• la séparation (aveugle) de sources

Liens externes

• (fr)Analyse en Composantes Indépendantes par J.-F Cardoso
• (fr)Analyse en Composantes Indépendantes État de l'art (2003).
• (en) What is independent component analysis? by A. Hyvärinen
• (en) Tutoriel par Aapo Hyvärinen.
• (en) ICA central: site spécialisé réunissant la communauté scientifique.
• (fr)Livre de synthèse sur la Séparation de Sources et l'Analyse en Composantes Indépendantes février 2007, par P.Comon et C.Jutten

Références

1. ↑ ^{a, b et c} J. Hérault, C. Jutten, and B. Ans, “Détection de grandeurs primitives dans un message composite par une architecture de calcul neuromimétique en apprentissage non supervisé,” in Actes du X^e colloque GRETSI, vol. 2, Nice, France, Mai 1985, pp. 1017–1022.
2. ↑ ^{a, b et c} C. Jutten and H. Hérault, “Blind separation of sources, part i: an adaptative algorithm based on neuromimetic architecture,” Signal Processing, vol. 24, pp. 1–10, 1991
3. ↑ Jutten, Ch. and Taleb, A. “Source separation: From dusk till dawn ICA 2000, pages 15-26 (invited paper), Helsinki, Finland, June 2000.
4. ↑ ^{a, b et c} P. Comon, “Indépendant component analysais - a new concept?” Signal Processing, vol. 36, no. 3, pp. 287–314, 1994.
5. ↑ ^{a et b} A. Hyvärinen, J. Karhunen, and E. Oja, “Independent Component Analysis”. John Wiley and Son, 2001
6. ↑ C. Jutten and J. Karhunen, Advances in blind source separation (BSS) and independent component analysis (ICA) for nonlinear mixtures. International Journal of Neural Systems, Vol. 14, No. 5, 2004, pp. 267-292.
7. ↑ P.Comon, C. Jutten and H. Hérault, “Blind separation of sources, part II: problem statement,” Signal Processing, vol. 24, pp. 11-20, 1991
8. ↑ D.T. Pham, P. Garat. IEEE T Signal Processing, 45(7):1712-1725, 1997
9. ↑ Tong L., Inouye Y., Liu R-W, wavefomr-preserving blind estimation of multiple independent sources, IEEE T. Signal Processing, 41(7):2461-2470, 1993
10. ↑ Cardoso J.-F, Souloumiac A., Blind beamforming for non-gaussian signals, IEE proceedings-F, 140(6):362-370, 1993
11. ↑ Linsker R., "Self-organisation in a perceptual network", IEEE Computer, 21:105-117, 1988
12. ↑ Nadal J;-P., Parga N., Network: computation in neural systems, 5:565-581, 1994
13. ↑ Barlow H.B., Sensory Communication, ed. WA Rosenblith, pp 217-34. Cambridge, MA:MIT press, 1961
14. ↑ Bell T, Sejnowsky T.J., Neural Computation, 7:1129-1159, 1995
15. ↑ Cardoso J.-F, Laheld, IEEE T. Signal Processing, 44(12):3017-3030, 1996