Computational Intelligence, SS08
2 VO 442.070 + 1 RU 708.070 last updated:
General
Course Notes (Skriptum)
Online Tutorials
Introduction to Matlab
Neural Network Toolbox
OCR with ANNs
Adaptive Filters
VC dimension
Gaussian Statistics
PCA, ICA, Blind Source Separation
Hidden Markov Models
Mixtures of Gaussians
Automatic Speech Recognition
Practical Course Slides
Homework
Exams
Animated Algorithms
Interactive Tests
Key Definitions
Downloads
Literature and Links
News
mailto:webmaster


Subsections



Modellierung der Problemstellung

Independent Component Analysis ist eine statistische Methode, die auf vereinfachenden Annahmen über den zugrundeliegenden Prozess und Messvorgang basiert:

  • Typischerweise werden die vermischten Signale, aus der die unabhängigen Komponenten extrahiert werden sollen, durch ein Array von $ M$ Mikrophonen/Sensoren aufgezeichnet. Die Anzahl $ M$ der Mikrophone spielt hier eine große Rolle, denn ICA ist nur durchführbar, wenn die Anzahl der unabhängigen Komponenten $ N$ kleiner oder höchstens gleich der Anzahl der Sensoren $ M$ ist.
  • Der zugrundeliegende Mischprozess wird in der Modellierung stark vereinfacht. Während in der Realität ein unabhängiges Quellsignal $ s[n]$ zwischen Quelle $ i$ und Sensor $ j$ durch eine beliebige Übertragungsfunktion $ H_{ji}(\omega)$ gefiltert wird (z.B.: Raumimpulsantwort in einem Büro), wird bei ICA der Übertragungsweg lediglich durch ein reines Skalar $ a_{ji}$ modelliert.
  • Der Effekt von additivem Rauschen, wie er in jedem physikalischen System auftritt, wird im Modell ignoriert.

Modellierung des Signals

Ein zeitdiskretes Signal $ x[n]$ wird im Folgenden als Zufallsvariable (ZV) $ x$ mit einer bestimmten Wahrscheinlichkeitsdichtefunktion (pdf) modelliert. Jeder zeitdiskrete Abtastwert $ x[n]$ stellt dabei eine Realisierung des durch die zugehörige pdf vollständig charakterisierten Zufallsexperiments dar.

Dementsprechend wird ein Array $ X[n]$ von Signalen

$\displaystyle \mathbf{x}[n]=(x_1[n], x_2[n],...,x_N[n])^T $
als Zufallsvektor
$\displaystyle \mathbf{x} = (x_1,x_2,...,x_N) $
modelliert.

Modellierung des Mischvorgangs

Wie bereits erwähnt, wird die Übetragungsfunktion des Signalpfads zwischen Quelle $ i$ und Sensor $ j$ durch ein Skalar $ a_{ji}$ modelliert. Da ein Sensor $ x_j$ die Summe aller unabhängigen Signale $ s_i$ aufzeichnet, ergibt sich:

$\displaystyle x_j = a_{j1} s_1 + a_{j2} s_2 + ... + a_{jN} s_N $
Figure 2: Modellierung des Mischvorgangs durch eine Mischmatrix A
\includegraphics[scale=0.3]{mischmodell}

Für die Gesamtheit der Sensorsignale ergibt sich daher (siehe auch Abbildung 2.2):



$\displaystyle \mathbf{x}$ $\displaystyle =$ $\displaystyle \mathbf{A} \mathbf{s}$ (1)


Dabei ist

  • der Sensorvektor $ \mathbf{x}$ ein Zufallsvektor der Dimension $ M \times 1$
  • der Quellvektor $ \mathbf{s}$ ein Zufallsvektor der Dimension $ N \times 1$
  • die Mischmatrix $ \mathbf{A}$ eine Matrix der Dimension $ M \times N$:

    $\displaystyle \mathbf{A}= \left(\begin{array}{rrrr} a_{11} & a_{12} & \ldots ... ...ts & \vdots \ a_{M1} & a_{M2} & \ldots & a_{MN} \ \end{array} \right) $

Prinzip des Lösungsverfahrens

Statistische Unabhängigkeit

Ziel der Independent Component Analysis ist die Extraktion der unabhängigen Komponenten in $ \mathbf{s}$ . Dazu benötigt man eine Entmischungsmatrix $ \mathbf{W}$:



$\displaystyle \mathbf{\hat s}$ $\displaystyle =$ $\displaystyle \mathbf{W} \mathbf{x}$ (2)


Dabei soll $ \mathbf{\hat s}$ eine möglichst genaue Annäherung bzw. Schätzung von $ \mathbf{s}$ sein.

Die Problematik besteht offensichtlich darin, dass keine Informationen über $ \mathbf{A}$ und $ \mathbf{s}$ vorliegen. (Wäre die Mischmatrix $ \mathbf{A}$ bekannt, könnte die Entmischungsmatrix $ \mathbf{W}$ sofort durch Invertierung von $ \mathbf{A}$ gefunden werden). Die einzigen Annahmen, die zur Vereinfachung über $ \mathbf{s}$ getroffen werden, sind:

  • Die unabhängigen Komponenten in $ \mathbf{s}$ (und somit auch in $ \mathbf{x}$) sind mittelwertfrei. Sollte dies nicht zutreffen, kann $ \mathbf{x}$ stets durch Subtraktion des Mittelwerts zentriert werden.
  • Die Varianz der einzelnen Komponenten in $ \mathbf{s}$ ist 1. Selbst wenn dies nicht der Wahrheit entsprechen sollte - das Gegenteil kann nur schwer bewiesen werden. Das willkürliche Normieren der Varianz auf 1 bewirkt dann lediglich eine Änderung der entsprechenden Koeffizienten in der Mischmatrix $ \mathbf{A}$ - die Modellierung bleibt gültig.

Der eigentliche Schlüssel zur Lösung des Problems liegt jedoch in der Annahme, dass die einzelnen Komponenten in $ \mathbf{s}$ statistisch unabhängig voneinander sind:

$\textstyle \parbox{11cm}{\emph{Zwei Zufallsvariablen X,Y sind statistisch vonei... ... der einen Variable keine Schlüsse auf den Wert der anderen Variable zulässt.}}$

Mathematisch formuliert:



$\displaystyle f_{XY}(x,y)$ $\displaystyle =$ $\displaystyle f_X(x) f_Y(y)$ (3)


Dabei ist $ f_{XY}$ die gemeinsame Wahrscheinlichkeitsdichte zweier Zufallsvariablen X und Y und $ f_X$ ist die Wahrscheinlichkeitsdichte einer ZV X.

Beispiel

Figure 3: Verteilung von zwei statistisch unabhängigen ZV $ s_1$ und $ s_2$
\includegraphics[scale=0.5]{example1}
Figure 4: Verteilung der ZV nach dem Mischprozess
\includegraphics[scale=0.5]{example2}

Bevor näher auf die Lösungsidee eingegangen wird, soll das Prinzip der statistischen Unabhängigkeit zweier unabhängiger Komponenten und die Auswirkung des Mischvorgangs anhand eines Beispiels erläutert werden. Abbildung 2.3.2 zeigt Realisierungen eines Zufallsvektors $ s = (s_1,s_2)^T$, wobei $ s_1$ und $ s_2$ statistisch voneinander unabhängig sind und jeweils gleichverteilt sind gemäß:

$\displaystyle f_{s_i}(s_i)=\begin{array}\{{cc}. 0.5 & \vert s_i\vert \leq 1\ 0 & sonst \end{array} $

Da beide Signale statistisch unabhängig voneinander sind, kann allein durch Kenntnis des Wertes einer Realisierung von $ s_1$ in keiner Weise auf den zugehörigen Wert der Realisierung von $ s_2$ geschlossen werden (und umgekehrt). Die zugehörige Kovarianzmatrix $ \mathbf{C_s}$ lautet:

$\displaystyle \mathbf{C_s}= E\{s s^T\}= \left(\begin{array}{rr} \frac{1}{3} & 0\ 0 & \frac{1}{3}\ \end{array} \right) $

Aufgrund der statistischen Unabhängigkeit der beiden Signale $ s_1$ und $ s_2$ ist die Kovarianzmatrix $ \mathbf{C_s}$ eine Diagonalmatrix, wobei der Wert in der i-ten Zeile und i-ten Spalte der Varianz des Signals $ s_i$ entspricht. Die Kovarianz zwischen den einzelnen Signalen ist Null. Die Umkehrung gilt jedoch im Allgemeinen nicht. Zwei Signale sind nicht automatisch statistisch unabhängig, wenn die Kovarianz zwischen diesen Signalen gleich Null ist. Statistische Unabhängigkeit erfordert Trennung der Momente jeder Ordnung, nicht nur der zweiten Ordnung (Varianz: Moment zweiter Ordnung).

Nun sei angenommen, dass die Signale $ s_i$ gemäß Gleichung (1) gemischt werden und in zwei Sensorsignalen $ x_1$ und $ x_2$ resultieren. Die resultierenden Realisierungen werden in Abbildung 4 dargestellt, die zugehörige Mischmatrix $ A$ lautet:

$\displaystyle \mathbf{A}= \left(\begin{array}{rr} 0.4 & 0.7\ 0.6 & 0.2\ \end{array} \right) $

Wie hier gut beobachtet werden kann, sind die resultierenden Sensorsignale $ x_i$ nicht mehr statistisch unabhängig. Beispielsweise kann durch Kenntnis von $ x_1 = 1.1$ darauf geschlossen werden, dass der Wert des zugehörigen Samples von $ x_2$ im Bereich $ 0.62-0.8$ liegen muss. Die zugehörige Kovarianzmatrix $ \mathbf{C_x}$ lautet nun:

$\displaystyle \mathbf{C_x}= E\{x x^T\}= \left(\begin{array}{rr} 0.215 & 0.125\ 0.125 & 0.131\ \end{array} \right) $

Die Kovarianz zwischen $ x_1$ und $ x_2$ ist somit $ 0.125$, die Signale sind nicht statistisch unabhängig.



Erreichen von statistischer Unabhängigkeit

Das grundlegende Prinzip von ICA ist es nun, die Werte von $ \mathbf{x}$ auf eine andere Basis zu projezieren, sodass die aus dieser Projektion resultierenden Signale statistisch unabhängig sind:



$\displaystyle \mathbf{u}$ $\displaystyle =$ $\displaystyle \mathbf{W} \mathbf{x}$ (4)


$\textstyle \parbox{11cm}{...wähle $\mathbf{W}$ so, dass die einzelnen Komponenten in $\mathbf{u}$ paarweise statistisch unabhängig sind.}$

Dabei sind die Basisvektoren $ w_i$ der Projektion (Basiswechsel) die Reihen der Entmischungsmatrix $ \mathbf{W}$:

$\displaystyle \mathbf{W}= \left(\begin{array}{r} w_1^T\ w_2^T\ \vdots\ w_n^T\ \end{array} \right) $

Wie kann nun eine solche Basis gefunden werden? Mit diesem Thema beschäftigen sich die nächsten beiden Sektionen. Sektion 3 beschreibt das Verfahren der Principal Component Analysis, die oft einen wertvollen Vorverarbeitungsschritt für ICA darstellt. In Sektion 4 wird schließlich auf das Verfahren der Independent Component Analysis eingegangen.