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



Independent Component Analysis

Prinzip der Gaußähnlichkeit

Wie im vorherigen Abschnitt erläutert wurde, kann mit Hilfe von Principal Component Analysis das Problem des Findens einer Entmischungsmatrix $ \mathbf{W}$ bis auf eine Rotation gelöst werden. Um auch diese Rotation rückgängig zu machen und somit die unabhängigen Signale $ s_i$ zu erhalten, ist es notwendig die inverse Rotationsmatrix zu finden.

Wie schon in Abschnitt 2.3.3 erläutert, basiert das Prinzip von ICA auf dem Auffinden einer neuen Basis (notiert durch eine Matrix $ \mathbf{W}$), sodass die Signalvektorkomponenten nach Projektion auf diese Basis paarweise statistisch unabhängig sind. Die Qualität der Projektion wird dabei von einer sog. Kontrastfunktion $ J$ bewertet. Dabei wird unterschieden zwischen einer

  • one-unit contrast function $ J(\mathbf{w_i})$: Diese Funktion bewertet die Qualität eines einzelnen Basisvektors
  • multi-unit contrast function $ J(\mathbf{W})$: Diese Funktion bewertet die Qualität der gesamten Basis

Mit Hilfe einer geeigneten Kontrastfunktion kann dann mit Hilfe von numerischen Optimierungsverfahren (z.B. Gradient Descent) eine optimale Basis $ \mathbf{W}$ gefunden werden.

Nun stellt sich die grundlegende Frage, $ wie$ die Qualität einer Projektion quantitativ bewertet werden kann. Diese Frage ist gleichbedeutend mit der Frage, wie die statistische Unabhängigkeit der auf die neue Basis projezierten Variablen $ \mathbf{u}$ bewertet werden kann. Einen möglichen Ansatz zur Beantwortung dieser Frage liefert der zentrale Grenzwertsatz aus der Statistik:

$\textstyle \parbox{11cm}{\emph{Die Summe von vielen beliebig verteilten Zufallsgrößen ist näherungsweise normalverteilt.}}$

Angenommen, die unabhängigen Quellsignale $ s_i$ sind nicht gaußverteilt. Dann gilt für die Sensorsignale $ x_i$, dass diese gaußähnlicher sein müssen als die unabhängigen Signale $ s_i$, da jedes $ x_i$ eine Summe der einzelnen $ s_i$ darstellt. Unter der Voraussetzung, dass die unabhängigen Signale $ s_i$ nicht gaußverteilt sind, kann somit statistische Unabhängigkeit durch Nicht-Gaußähnlichkeit bewertet werden. Ziel einer Kontrastfunktion $ J$ ist es deshalb, die Gaußähnlichkeit eines projezierten Sensorvektors $ \mathbf{u}$ und dadurch die Qualität der Projektion $ \mathbf{W}$ zu bewerten.

Nun stellt sich im weiteren die Frage, wie die (Nicht-)Gaußähnlichkeit einer Zufallsvariable bestimmt werden kann. Zwei dafür häufig herangezogene Konzepte sind die Kurtosis und die Negentropie, die in den folgenden Abschnitten beschrieben werden.

Kurtosis

Die Kurtosis $ \gamma_2$ einer Zufallsvariable $ X$ ist ein statistisches Moment 4. Ordnung und ist definiert als:



$\displaystyle \gamma_2 = \frac{E\{ (X - E\{X\})^4\}}{(E\{X^2\})^2}-3$     (9)


Für die Berechnung der Kurtosis eines Sensorsignals reduziert sich dieser Ausdruck auf



$\displaystyle \gamma_2 = E\{X^4\}-3$     (10)


da das Signal mittelwertfrei und auf Varianz 1 normiert ist.

Figure 8: Kurtosis von Gleichverteilung, Normalverteilung und Laplaceverteilung
\includegraphics[scale=0.5]{kurt}

Die Kurtosis einer Zufallsvariable $ X$ bewertet die Konzentration der zugehörigen Wahrscheinlichkeitsdichte (Peak der Wahrscheinlichkeitsdichte) um den Mittelwert von $ X$. Dieser Zusammenhang ist in Abbildung 8 dargestellt. Die Gaußverteilung (rot) hat per Definition die Kurtosis Null. Eine pdf mit einer höheren Konzentration der Dichte um den Mittelwert - wie beispielsweise die Laplaceverteilung (grün) - besitzt eine positive Kurtosis. Eine pdf mit einer gleichmäßiger verteilten Dichte - wie beispielsweise die Gleichverteilung (blau) - besitzt eine negative Kurtosis. In diesem Zusammenhang wird eine pdf mit positiver Kurtosis auch als super-gauß und eine pdf mit negativer Kurtosis auch als sub-gauß bezeichnet.

In den Anwendungen der ICA wird oft die quadratische Kurtosis als Kontrastfunktion definiert:



$\displaystyle J(\mathbf{w_i}) = (E\{(\mathbf{w_i}^T \mathbf{x_i})^4\}-3)^2$     (11)


Diese ist leicht berechenbar und stets positiv. Je gaußähnlicher ein Zufallsvektor ist, desto kleiner wird die zugehörige quadratische Kurtosis.

Ein Nachteil der Kurtosis ist allerdings deren Anfälligkeit gegenüber Ausreißern: Bei der Schätzung der Kurtosis anhand nur weniger Realisierungen von $ X$ kann es passieren, dass die Häufigkeitsverteilung dieser Realisierungen an manchen Stellen nicht der tatsächlichen pdf entsprechen. Gerade für solche Realisierungen mit hohem Betrag wird dann die Schätzung der Kurtosis völlig falsch.

Aus diesem Grund ist es wünschenswert, robustere Verfahren zur Schätzung der Gaußähnlichkeit herzuleiten. Eines dieser robusten Verfahren ist die Negentropie.

Negentropie

Die Negentropie leitet sich aus dem Konzept der Entropie ab. Die Entropie $ H$ eines Signals ist ein Maß für dessen Informationsgehalt. Beispielsweise trägt ein über die Zeit stets konstantes Signal offensichtlich überhaupt keine Information, die Entropie dieses Signals ist dementsprechend Null. Je weniger vorhersagbar bzw. je überraschender ein zukünftiges Sample eines Signals andererseits ist, desto mehr Information kann in diesem Signal stecken. Daraus wird klar, dass die Entropie eines Signals eng mit dessen zugrundeliegender Wahrscheinlichkeitsverteilung verknüpft ist. Die Entropie $ H$ einer Zufallsvariable $ X$ ist definiert als:



$\displaystyle H(X) = -\int f_X(\eta) log(f_X(\eta)) d\eta$     (12)


Dabei ist $ f_X$ die X zugrundeliegende Wahrscheinlichkeitsdichte.

Auf der Suche nach einer geeigneten Bewertung der Gaußähnlichkeit kommt nun ein Theorem aus der Informationstheorie zu Hilfe:

$\textstyle \parbox{11cm}{\emph{In der Menge aller möglichen Zufallsvariablen mit gleicher Varianz hat die gaußverteilte Zufallsvariable die größte Entropie.}}$

Aus diesem Theorem kann nun das Konzept der Negentropie abgeleitet werden. Die Negentropie $ J$ einer Zufallsvariable $ X$ ist definiert als:



$\displaystyle J(X) = H(X_{gauss}) - H(X)$     (13)


Dabei ist $ X_{gauss}$ eine gaußverteilte Zufallsvariable mit gleicher Varianz wie X. Auf diese Weise wird $ J(X)$ dann und nur dann gleich Null, wenn $ X$ gaußverteilt ist. Je weniger gauß-ähnlich $ X$ ist, desto größer wird $ J(X)$.

Aus Sicht der Statistik ist die Negentropie ein optimaler Schätzoperator für die Gaußähnlichkeit einer Zufallsvariable. Ein großer Nachteil der Negentropie ist allerdings, dass zur Berechnung die pdf von $ X$ bekannt oder geschätzt werden muss, was sich als aufwendig und rechenlastig herausstellt.

Aus diesem Grund wird versucht, die Negentropie mit weniger rechenlastigen Funktionen zu approximieren. Für solche Funktionen hat sich folgende Struktur als nützlich herausgestellt:



$\displaystyle J(X)$ $\displaystyle =$ $\displaystyle k_1 (E\{ G_1(X) \})^2 + k_2 (E\{ G_2(X) \} - E\{ G_2(\nu ) \} )^2$ (14)


Dabei ist $ \nu$ die standardisierte Gaußvariable und $ G_1$ bzw. $ G_2$ sind nichtlineare Funktionen, die so gewählt werden müssen dass die Schätzung robust ist. Eine beliebte Wahl für $ G_1$ und $ G_2$ ist beispielsweise:



$\displaystyle G_1(x)$ $\displaystyle =$ $\displaystyle \frac{1}{a_1 log(cosh(a_1 x))}$ (15)
$\displaystyle G_2(x)$ $\displaystyle =$ $\displaystyle -e^{-\frac{x^2}{2}}$ (16)


Insgesamt stellt die Approximation der Negentropie einen guten Kompromiss zwischen den beiden Varianten Kurtosis und Negentropie dar, da sie einerseits effizient berechenbar und andererseits robust ist.

Zusammenfassung

Independent Component Analysis basiert auf der Annahme, dass

  • die einzelnen Quellen $ s_i$ statistisch unabhängig sind
  • nur maximal eine Quellen $ s_i$ gaußverteilt ist (alle anderen Quellen müssen nicht gaußverteilt sein).
  • die Mischmatrix $ A$ muss vollen Rang besitzen.

Sind diese Annahmen erfüllt, kann der Mischprozess gemäß Gleichung (1) durch den Entmischprozess gemäß Gleichung (2) rückgängig gemacht werden.

Ein großer Nachteil von ICA besteht in der Tatsache, dass die Anzahl der Sensoren $ M$ größer oder mindestens gleich der Anzahl der unabhängigen Quellen $ N$ sein muss. Dies ist in der Praxis besonders dann ein Problem, wenn im Vorhinein nicht abgeschätzt werden kann, wie viele unabhängige Quellen auftreten werden bzw. wenn aufgrund der zu hohen Anzahl an Quellen das Setup nicht mehr durchführbar ist.