# Cascade Correlation

Kaskadenkorrelation (englisch: Cascade Correlation) ist ein mathematisches konstruktives Verfahren zur Erzeugung und zum Training von künstlichen neuronalen Netzen. Veröffentlicht wurde Kaskadenkorrelation 1990 von Scott E. Fahlman und Christian Lebiere in der Arbeit „The Cascade-Correlation Learning Architecture“.
Die Idee hinter Kaskadenkorrelation ist nicht nur das Training eines neuronalen Netzes, sondern auch der Aufbau dessen Struktur (konstruktives Verfahren). Der große Vorteil dabei ist, dass sich das neuronale Netzwerk in seiner Größe an die Problemstellung (Trainingsdaten) anpasst. Das Verfahren kommt insbesondere bei mehrschichtigen Feedforward-Netzen zum Einsatz, welche mittels Backpropagation trainiert werden.

## Verfahren

Der Algorithmus startet mit einem für die Aufgabenstellung minimalen neuronalen Netz, das nur aus Eingabezellen und Ausgabezellen besteht. Die Neuronen sind dabei über Gewichte vollständig miteinander verbunden. Das Training der Gewichte erfolgt nun mit Hilfe eines Lernverfahrens (Quickprop). Wird über mehrere Trainingsepochen keine signifikante Verbesserung des Netzwerkfehlers mehr erreicht, wird das Training beendet. Die gefundenen Gewichte werden beibehalten und ein neues (verdecktes) Neuron wird zum Netzwerk hinzugefügt. Das verdeckte Neuron (Candidate Unit) wird dabei zu einer bestehenden Hidden-Layer hinzugefügt oder bildet einen neuen Layer. Dabei erhält es als Eingänge Verbindungen von allen Eingabezellen und eventuell zuvor hinzugefügten verdeckten Zellen. Der Ausgang des zugefügten Neurons hat vorerst keine Verbindung zum Netzwerk. Es erfolgt nun das Training für die Gewichte des neuen Neurons. Ziel des Trainings ist es, $S_{j}$, die Summe der Beträge der Kovarianz zwischen $o_{j}$, der Ausgabe der Candidate Unit, und $\delta _{k}$, dem Restfehler der Ausgabezelle k, über alle Ausgabezellen zu maximieren.
$S_{j}=\sum _{k}\left|\sum _{p}(o_{pj}-{\bar {o}}_{j})\,(\delta _{pk}-{\bar {\delta }}_{k})\right|$
Hierbei ist j der Index der Candidate Unit, k der Laufindex über alle Ausgangsneuronen, p der Index der Muster, ${\bar {o}}_{j}$ die mittlere Ausgabe von Neuron j über alle Muster p und ${\bar {\delta }}_{k}$ der mittlere Fehler der Ausgabezellen k über alle Muster p. Der Fehler $\delta _{k}$ ist gegeben durch die Differenz zwischen erwünschten Ausgang und dem tatsächlichen Ausgang. Ziel ist es, $S_{j}$ zu maximieren. Daher muss die partielle Ableitung von $S_{j}$ nach jedem Gewicht $w_{ij}$ der Zelle gebildet werden.
${\frac {\partial S_{j}}{\partial \,w_{ij}}}=\sum _{k}\sum _{p}\sigma _{k}\cdot f'_{act}(net_{pj})\,o_{pi}\,(\delta _{pk}-{\bar {\delta }}_{k})$
Mit der Definition:
$\sigma _{k}=sgn\left[\sum _{p}(o_{pj}-{\bar {o}}_{j})\,(\delta _{pk}-{\bar {\delta }}_{k})\right]$
und
$o_{pj}=f_{act}\left(net_{pj}\right)$
Ist die partielle Ableitung zu jedem Gewicht der Candidate Unit bestimmt, kann ein Gradientenaufstieg durchgeführt werden. Das Training wird so lange fortgesetzt, bis keine wesentliche Veränderung von $S_{j}$ mehr erfolgt. Der Ausgang des zugefügten Neurons liefert nun ein maximales Ausgangssignal, wenn der Fehler des restlichen Netzwerkes am größten ist. Die Gewichte der Candidate Unit werden jetzt permanent eingefroren und der Ausgang der Zelle vollständig mit jedem vorhandenen Ausgangsneuronen verbunden. Ein neues Training der Gewichte aller Ausgangsneuronen wird nun gestartet. Ist nach dem Training der gewünschte Ausgangsfehler noch nicht erreicht, wird, wie oben beschrieben, ein weiteres verdecktes Neuron dem Netzwerk zugeführt und trainiert.
Das Bild unten zeigt ein Kaskadenkorrelationsnetzwerk mit drei verdeckten Neuronen. Die Gewichte sind hierbei als Quadrate auf den Verbindungsstellen zwischen Ausgängen und Eingängen der Neuronen dargestellt. Das on-Neuron dient für alle Neuronen des Netzwerkes zur Einstellung der Ansprechschwelle; es besitzt als Ausgabe immer den Wert 1.
Beim Kaskadenkorrelations-Algorithmus werden verdeckte Zellen nur einmal trainiert und die gefundenen Gewichte nicht mehr verändert, während die Gewichte für die Ausgangsneuronen in jedem Schritt neu angepasst werden.
Das Verfahren konvergiert verhältnismäßig gut, da immer nur eine Schicht des Netzwerks trainiert wird. Damit vermeidet man das Problem bei komplexen Netzwerken, dass sich gleichzeitig alle Neuronen durch ein Training auf ein gegebenes Eingangsmuster anpassen, während sie nur mit lokalen Informationen über den zurückpropagierten Fehler über die direkten Nachbarn versorgt werden.

## Implementierungen

Implementierung der Kaskadenkorrelation finden sich in verschiedenen Softwareanwendungen, darunter:
* MemBrain
* SNNS (JavaNNS)
* Tlearn