Analýza nezávislých komponent

Analýza nezávislých složek (v angličtině, analýza nezávislých složek nebo ICA ) je metoda analýzy dat (viz Data Mining ), která spadá do statistik , neuronových sítí a zpracování signálu . Je dobře známá a historicky známá jako metoda separace slepých zdrojů, ale následně byla aplikována na různé problémy. Hlavní příspěvky byly shromážděny v knize vydané v roce 2010 P.Comonem a C. Juttenem.

Historický

První formulaci problému provedli v roce 1984 J. Hérault a B. Ans, dva vědci v neurovědě a zpracování signálu, aby biologicky modelovali kódování pohybu. Tato práce připravila půdu pro formulaci problému oddělení slepého zdroje . Ve druhé polovině 80. let vznikla kolem tohoto tématu komunita, zejména ve Francii a Finsku. Francouzská komunita zpracovávající signály přijala statistický formalismus, zatímco finští vědci se snažili rozšířit analýzu hlavních komponent pomocí konekcionistického formalismu . Algoritmus navržený v roce 1985 byl překvapivě robustní, ale teoretická vysvětlení jeho vlastností byla neúplná. První formalismus problému separace slepých zdrojů , stejně jako algoritmus umožňující získat řešení, navrhli C. Jutten a J. Hérault v roce 1991. Byla provedena matematická formalizace v nejjednodušším případě (lineární snímek míchání) v roce 1994 P. Comonem, což vedlo ke konceptu nezávislé analýzy komponent .

Výzkum v této oblasti se stal velmi aktivním od 90. let 20. století a o problém se začali zajímat vědci z celého světa. Kromě výše zmíněných evropských týmů se američtí a japonští vědci zajímali o souvislost mezi ACI a neurálním kódováním . Existuje několik specializovaných prací poskytujících podrobnosti o určitých navrhovaných řešeních a také s nimi související teoretický vývoj.

Mezinárodní konference zabývající se konkrétně tímto tématem existuje od roku 1999. Původně se měla konat každých 18 měsíců, nyní je každoroční. První vydání se konala v Aussois (Francie, 1999), Helsinkách (Finsko, 2000), San Diegu (Kalifornie, 2001), Nara (Japonsko, 2003), Granadě (Španělsko, 2004), Charlestonu (Jižní Karolína, USA, 2006), Londýn (Velká Británie, 2007) a Paraty (Brazílie, 2009).

Oddělení zdroje (problém s koktejlovou párty)

Klasickým příkladem oddělení zdrojů je problém s koktejlovou párty . Během takového večera jsou mikrofony umístěny v husté místnosti, kde lidé diskutují ve skupinách různých velikostí. Každý mikrofon zaznamenává superpozici projevů lidí v jeho okolí a problém spočívá v nalezení hlasu každého člověka („osvobozeného“ od ostatních hlasů považovaných za rušení). P{\ displaystyle P}NE{\ displaystyle N}

ACI tento problém řeší pouhým zvážením toho, že lidé hovořící v daném čase mají „nezávislé“ projevy. Nejde o zohlednění sémantiky těchto projevů (lze skutečně doufat, že určité hlasy jsou na této úrovni konzistentní!) Nebo dokonce o akustiku (což by bylo špatné, i kdyby jen tehdy, kdyby měli účastníci stejné jazyky.) ..), ale považovat je za statisticky nezávislé náhodné signály . Na rozdíl od sboru lidé, kteří v danou dobu hovoří současně, vydávají nezávislé zvuky .

Teorie zajišťující tento výsledek nicméně nabízí určité předpoklady, zejména to, že „počet mikrofonů je větší nebo roven počtu lidí“. Symetricky existují také nejistoty ohledně výsledku (samostatné hlasy). Lze je interpretovat takto:

• člověk nemůže přiřadit hlasy lidem pouze s vědomím nalezených signálů (ale lidský posluchač ano). Jinými slovy, neznáme pořadí nalezených signálů.
• neznáme intenzitu hlasu reproduktorů. To bude přiděleno libovolně a lidský posluchač se mohl spolehnout pouze na tón hlasu a znalost osoby, která to určí.

Z historických a vzdělávacích důvodů se ACI často zavádí jako řešení problému oddělení zdrojů . Existují však i jiné metody řešení tohoto problému, které nevyžadují striktně předpoklad statistické nezávislosti mezi zdroji ( například šetrnost ).

Matematický formalismus

V nejjednodušším případě ( okamžitý lineární model bez šumu) je teorie velmi dobře zvládnuta. Tento směšovací model se však často zdá příliš omezující na modelování praktických případů. Práce na složitějších směšovacích modelech je dosud předmětem aktivního výzkumu.

Bezhlučný okamžitý lineární model

Když je jako konkrétní kontrastní funkce zvolena vzájemná informace , analýza nezávislé složky náhodného vektoru se rovná identifikaci následujícího bezhlučného okamžitého lineárního generativního modelu: X_=(X1,X2,...,Xp){\ displaystyle {\ underline {x}} = \ left (x_ {1}, x_ {2}, \ dots, x_ {p} \ right)}

X_=NAs_{\ displaystyle {\ underline {x}} = A {\ podtržení {s}}}

kde složky vektoru jsou navzájem nezávislé a matrice má pevnou velikostí . Nicméně tyto podmínky identifikovatelnosti musí být ověřeno, takže si můžeme být jisti, že budou moci najít model (teoreticky): si{\ displaystyle s_ {i}}s_=(s1,s2,...,sne){\ displaystyle {\ underline {s}} = \ left (s_ {1}, s_ {2}, \ dots, s_ {n} \ right)}NA{\ displaystyle A}p×ne{\ Displaystyle p \ krát n}

• nanejvýš jeden ze zdrojů (komponent ) může sledovat normální (gaussovské) rozdělení,s_{\ displaystyle {\ podtržení {s}}}
• hodnost matice se musí rovnat počtu zdrojů (k nalezení).NA{\ displaystyle A}

První podmínka je výsledkem neplatnosti momentů a kumulantů řádů větších než dva pro Gaussovo rozdělení. Nezávislost se pak rovná jednoduché dekorelaci a hypotéza statistické nezávislosti neumožňuje oddělit gaussovské zdroje. Je však možné najít další negaussovské zdroje.

Druhá podmínka vyžaduje pozorování přinejmenším tolik dat, kolik je zdrojů k identifikaci. Práce na šetrných reprezentacích však ukázala, že je možné získat více zdrojů než dostupná pozorování. Naopak je vždy možné zmenšit velikost dostupných pozorování, například pomocí analýzy hlavních komponent (PCA).

Po ověření těchto dvou podmínek identifikovatelnosti však zůstávají dvě nejistoty :

• Změna pořadí zdrojů nemění jejich vzájemnou nezávislost. V důsledku toho nejsou zdroje identifikované ACI řazeny (na rozdíl od PCA, kde jsou zdroje řazeny podle vlastních čísel variance / kovarianční matice)
• Statistická nezávislost je udržována, když jsou komponenty vynásobeny nenulovou konstantou. Jinými slovy, na amplitudě zdrojů je neurčitost.

Tyto dvě neurčitosti nejsou specifické pro bezhlučný okamžitý lineární model a jsou ověřeny v obecném případě.

Hlučný okamžitý lineární model

Realističtější než předchozí model, to znamená identifikaci následujícího modelu:

X_=NAs_+σ{\ displaystyle {\ underline {x}} = A {\ podtržení {s}} + \ sigma}

kde je hluk. σ{\ displaystyle \ sigma}

Ne okamžitý lineární model

Směs může být konvoluční. Nicméně se pak můžeme snížit na lineární model, například pomocí Fourierovy transformace .

Nelineární směsi

Toto je nejobecnější případ, kdy pozorování vyplývají z nelineární transformace zdrojů:

X_=F(s_){\ displaystyle {\ underline {x}} = F ({\ underline {s}})}

kde je libovolná nelineární funkce. V tomto případě nevíme o obecné metodě. Někteří autoři nicméně navrhli metody pro konkrétní případy. Jedná se o velmi aktivní oblast výzkumu. V nejobecnějším případě není problém se špatným nastavením řešení zdaleka jedinečný. F(.){\ displaystyle F (.)}

Hlavní algoritmy

Cílem této části je poskytnout hlavní myšlenky nejslavnějších algoritmů pro řešení problému ACI. Tyto algoritmy byly vybrány tak, aby představovaly pestrou škálu přístupů. Ve vědecké literatuře lze nalézt mnoho dalších metod.

Považujeme zde bezhlučný okamžitý lineární model a hledáme odhad nezávislých zdrojů i separační matici ověřující: yi{\ displaystyle y_ {i}}si{\ displaystyle s_ {i}}Ž{\ displaystyle W}

y_=ŽX_=ŽNAs_{\ displaystyle {\ podtržení {y}} = W {\ podtržení {x}} = WA {\ podtržení {s}}}

Algoritmus HJ

První algoritmus ACI (pojmenovaný po dvou jeho autorech) vychází z neuromimetického přístupu : jedná se o použití nástrojů pro zpracování signálu k modelování jevu inspirovaného neuronálním fungováním. Tento algoritmus byl typu Robins-Monro a iterativně hledal společné nuly dvou funkcí. Je založen na rekurzivní neurální síti, jejíž váhy jsou ne-diagonální členy separační matice , přičemž úhlopříčné členy jsou omezeny na null. Odhad zdroje je tedy dán vztahem: Ž{\ displaystyle W}

y_=(Já+Ž)-1X_{\ displaystyle {\ podtržení {y}} = (I + W) ^ {- 1} {\ podtržení {x}}}

S následujícím pravidlem přizpůsobení pro ne-diagonální výrazy:

Δwij=F(yi)×G(yj){\ displaystyle \ Delta w_ {ij} = f (y_ {i}) \ krát g (y_ {j})}

F(.){\ displaystyle f (.)}a různé liché nelineární funkce, které mají být vybrány jako funkce hustoty pravděpodobnosti zdrojů, které mají být odhadnuty. Následná práce zdůvodnila podobu tohoto pravidla učení a ukázala, že nelineární funkce musela být zvolena ve smyslu maximální pravděpodobnosti . Mírou nezávislosti, která je základem tohoto algoritmu, je zrušení kumulantů vyššího řádu. G(.){\ displaystyle g (.)}

Maximalizace kontrastu (CoM)

Tuto rodinu algoritmů navrhl Comon v roce 1991. Tyto algoritmy postupují postupným skenováním všech dvojic výstupů. Algoritmus CoM může vypočítat buď všechny kumulanty pozorování (jako JADE), nebo na vyžádání pokaždé, když se vypočítá optimální rotace. Lze zvolit tak, aby se minimalizovala digitální složitost.

Bylo navrženo několik verzí, v závislosti na použitém kontrastu. V roce 1991 to byl například součet čtvercových modulů mezních kumulantů výstupů: tento kontrast se nyní nazývá CoM2. Později Moreau navrhl další kontrast, CoM1: součet modulů mezních kumulantů výstupů. Pokud zdroje mají mezní kumulanty se stejným znaménkem, ukázalo se, že absolutní hodnotu lze odstranit. Toto zjednodušení dalo vzniknout dalšímu kompaktní algebraickému řešení vyvinutému Comonem.

V literatuře byly následně navrženy další obecnější formy kontrastu založené na kumulantech.

NEFRIT

( Společná přibližná diagonalizace vlastních čísel )

Tenzor z cumulants (za čtyři) je matice, která obsahuje všechny čtyři trojrozměrné zkřížené cumulants objednávky čtyři. Je to také lineární mapa jednoho maticového prostoru o velikosti do jiného maticového prostoru stejné velikosti. Diagonalizace této lineární aplikace umožňuje za určitých podmínek provést požadovanou separaci. Ve skutečnosti je zde statistická nezávislost vnímána jako hledání tendence k nulitě všech momentů a kumulantů (ve všech řádech), což se rovná zrušení všech ne-diagonálních prvků matice spojených s výše uvedenou lineární mapou. Cardoso a Souloumiac navrhli metodu společné diagonalizace, která umožní uplatnit tento princip v praxi. To se rovná minimalizaci součtu čtverců všech „diagonálních“ kumulantů (na objednávku čtyři) (kumulace mezi dvěma různými signály). V praxi JADE vyžaduje výpočet všech kumulantů řádu čtyři, a proto má složitost . NE×NE{\ displaystyle N \ krát N}Ó(ne4){\ displaystyle O (n ^ {4})}

Fast-ICA

Hyvärinen a Oja navrhují odhadnout nezávislé složky pomocí míry „ne-gaussianity“. Opravdu, centrální limitní teorém říká, že suma nezávislých proměnných inklinuje asymptoticky směrem k normálnímu rozdělení . V uvažovaném případě jsou odhady takovým součtem nezávislých proměnných ( ), a proto směřují ke Gaussovu distribuci . Snahou o maximalizaci ne-Gaussianity bude každá z jejích složek inklinovat k odhadu nezávislých zdrojů (kromě dvou neurčitostí). Bylo navrženo několik opatření „ne-gaussianity“, nejčastěji používanou negentropií, což je rozdíl mezi entropií Gaussovy proměnné a entropií měřeného vektoru. Hyvärinen navrhl různé aproximace tohoto opatření umožňující algoritmickou implementaci exponovaného principu. y_=ŽNAs_{\ displaystyle {\ underline {y}} = WA {\ podtržení {s}}}y_{\ displaystyle {\ podtržení {y}}}

Aby se zabránilo tomu, že se všechny odhady sblíží ke stejnému zdroji, je nutné zavést ortogonalitu (pod omezením bělení to znamená dekorelaci dat, například pomocí analýzy hlavních komponent ). K zavedení této ortogonality existují dvě metody. Takzvaná „deflační“ verze iterativně odhaduje zdroje a ortogonalizuje každý odhad pomocí Gram-Schmidtovy metody . „Symetrická“ verze současně ortogonalizuje všechny odhady. yi{\ displaystyle y_ {i}}

„Fast-ICA“ tak zdůrazňuje silné vazby mezi analýzou nezávislých komponent a snahou o projekci .

Infomax

Tento princip, formulovaný Linskerem, stanoví, že implementace modelu kognitivních schopností savců pomocí umělých neuronových sítí musí být taková, aby rychlost informací přenášených z jedné vrstvy neuronů do další byla maximální. Tuto rychlost informací lze měřit zejména entropií, když se podíváme na shannonský formalismus .

Nadal a Parga prokázali, že za určitých podmínek byl tento princip ekvivalentní principu redukce redundance, který uvádí, že cílem senzorických systémů savců je efektivní kódování podnětů (vizuálních, zvukových atd.). Opětovným umístěním do shannonského formalismu to znamená minimalizaci redundance informací o jejich prostředí a získání faktoriálního kódování (tj. Kódování, které minimalizuje statistické závislosti mezi dimenzemi, nazývané také kódování minimální entropie).

Bell a Sejnowsky tuto ekvivalenci využili tím, že ji napsali:

∂Já(y,X)∂w=∂H(y)∂w{\ displaystyle {\ frac {\ částečné I (y, x)} {\ částečné w}} = {\ frac {\ částečné H (y)} {\ částečné w}}}

kde je vzájemná informace mezi výstupy a vstupy neuronové sítě, parametry této sítě a entropie výstupů. Výše uvedený vztah přesně vyjadřuje, že maximalizace vzájemné informace o výstupech sítí (tj. Získání co nejefektivnějšího faktorového kódu) je stejná jako maximalizace informace, která „prochází“ sítí. Já(y,X){\ displaystyle I (y, x) \,}y{\ displaystyle y \,}X{\ displaystyle x \,}w{\ displaystyle w \,}H(y){\ displaystyle H (y) \,}

Odvodili pravidlo pro učení parametrů sítě, které po určitých zjednodušeních a použití pravidla typu „relativního přechodu“ dosahuje:

ΔŽ=[Já-K.tnaneh(y)yT-yyT]Ž{\ displaystyle \ Delta W = [I-Ktanh (y) y ^ {T} -rr ^ {T}] W}

K je úhlopříčná matice, jejíž prvky mají hodnotu 1 pro super gaussovské zdroje a -1 pro sub gaussovské zdroje.

Ukázalo se, že tento přístup je ekvivalentní přístupu maximální pravděpodobnosti.

Podívejte se také

• analýza hlavních komponent
• karty samostatně organizovat
• že separační (slepé) zdroje

externí odkazy

• (en) Analýza nezávislých komponent J.-F Cardoso
• (fr) Analýza nezávislých komponent Stav techniky (2003)
• (en) Co je to analýza nezávislých komponent? A. Hyvärinen
• (en) Výukový program Aapo Hyvärinen.

Reference

1. P.Comon, C. Jutten, Handbook of Blind Source Separation, Independent Component Analysis and Applications , Academic Press, 2010. ( ISBN  978-0-12-374726-6 )
2. J. Hérault a B. Ans, „Neuronová síť s modifikovatelnými synapsemi: dekódování složených smyslových zpráv bez dohledu a permanentního učení“, Comptes Rendus de l'Académie des Sciences Paris, série 3 , 299: 525-528, 1984.
3. J. Herault, Jutten C a B. let, "Detekce primitivní veličin ve složeném zprávy s neuronové výpočetní architektury v učení bez učitele", v Proceedings of the X th konference GRETSI, sv. 2, Nice, Francie, květen 1985, s. 1017–1022.
4. C. Jutten a H. Hérault, „Slepá separace zdrojů, část i: adaptivní algoritmus založený na neuromimetické architektuře“, Signal Processing, sv. 24, s. 1–10, 1991
5. Jutten, Ch. A Taleb, A. Oddělení zdrojů: Od soumraku do úsvitu ICA 2000, strany 15–26 (pozvaný referát), Helsinky, Finsko, červen 2000.
6. P. Comon, „Analýza nezávislých komponent - nový koncept?“ Zpracování signálu, sv. 36, č. 3, s. 287–314, 1994.
7. A. Hyvärinen, J. Karhunen a E. Oja, „Analýza nezávislých komponent“. John Wiley and Son, 2001
8. C. Jutten a J. Karhunen, Pokroky v separaci slepých zdrojů (BSS) a analýze nezávislých složek (ICA) pro nelineární směsi. International Journal of Neural Systems, Vol. 14, č. 5, 2004, s. 267-292.
9. P.Comon, C. Jutten a H. Hérault, „Slepá separace zdrojů, část II: prohlášení o problému“, Signal Processing, sv. 24, s. 11-20, 1991
10. DT Pham, P. Garat. Zpracování signálu IEEE T, 45 (7): 1712-1725, 1997
11. P. Comon, Kontrasty, Analýza nezávislých komponent a Slepá dekonvoluce, „Int. Journal Adapt. Control Sig. Proc.“, Wiley, duben 2004. HAL odkaz
12. Tong L., Inouye Y., Liu RW, slepý odhad více nezávislých zdrojů zachovávající vlnovou vlnu , IEEE T. Signal Processing, 41 (7): 2461-2470, 1993
13. Cardoso J.-F, Souloumiac A., Blind beamforming pro negaussovské signály , IEE řízení-F, 140 (6): 362-370, 1993
14. Linsker R., "Samoorganizace v percepční síti", IEEE Computer , 21: 105-117, 1988
15. Nadal J ;-P., Parga N., Network: computation in neurural systems , 5: 565-581, 1994
16. Barlow HB, senzorická komunikace, ed. WA Rosenblith, s. 217-34. Cambridge, MA: MIT press, 1961
17. Bell T, Sejnowsky TJ, Neural Computation , 7: 1129-1159, 1995
18. Cardoso J.-F, Laheld, IEEE T. Zpracování signálu , 44 (12): 3017-3030, 1996
19. H. Le Borgne, Analýza scén nezávislými komponentami , disertační práce, INP Grenoble, 2004. Kapitola 3.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">