Die kanonische Form diskreter dynamische
Modelle und ihr Einsatz als Filter

Referat von Arno Schödl im Seminar Moderne Methoden Neuronaler Netze im SoSe 97

Betreuer Prof. Dr. Obermayer

1 Die kanonische Form eines diskreten dynamischen

Modells

Ein System kann allgemein durch seinen Zustand beschrieben werden, modelliert durch eine

Menge von Zustandsvariablen. Dieser Zustand ändert sich mit der Zeit. Die Modellierung ist

dann diskret, wenn der Wert der Zustandsvariablen nicht zu jeder beliebigen Zeit, sondern nur

in regelmäßigen Zeitschritten betrachtet wird. Die Zustand des Modells

xi

zu einem Zeitschritt

t

+1 ist eine Funktion

i

, die allgemein abhängt von den aktuellen und vergangenen Eingaben

in das Modell

ui

und dem internen Zustand des Modells

xi

in der Vergangenheit:

Allgemein ist dann eine Teilmenge der internen Zustände als Ausgabe interessant.

Ein einfaches Beispiel eines dynamischen Systems ist ein frei fliegender Körper. Die externe

Eingabe ist die Kraft, die auf den Körper wirkt. Der Zustand des Körpers ist seine Position

und seine Lage im Raum, modelliert durch drei Positionskoordinaten und drei Drehwinkel.

Zur Bestimmung einer neuen Position müssen neben unveränderlichen Parametern des

Körpers (Masse, Drehträgheit) die aktuell wirkende Kraft und die Position der letzten beiden

Zeitschritte bekannt sein. Die letzten beiden Zeitschritte werden benötigt, um die

1.1 Die Bestimmung der minimalen Zustandsmenge

Geschwindigkeit des Körpers zu bestimmen, die sich gemäß der wirkende Kraft verändert.

Daraus wird dann die neue Position und Lage bestimmt.

Die Bestimmung der minimalen

2

2

Zustandsmenge geschieht mithilfe von

Die Abhängigkeit der Funktion

i

für jede Zustandsvariable

xi

von den vergangenen

Graphtransformationen. Dazu wird der

2

3

Zuständen und den Eingaben kann in einem Graph dargestellt werden, hier anhand eines

1

2

6

4

5

A usgab e

angegebene Graph 1 in eine andere

4

2

Beispielmodells, das wir im nächsten Abschnitt noch weiter betrachten. Mit jedem Zeitschritt

Darstellung überführt. Wir fassen alle

2

wird nach den Funktionen der Zustandsvariablen aus vergangenen Zuständen und externen

0

3

Knoten eines Zustands zu verschiedenen

D elay de s

Eingaben ein neuer Satz Zustandsvariablen erzeugt (siehe Bild rechts).

Zeiten im vorgestellten Graph zu einem

x E in gangs um

6

3

0

7

Knoten zusammen. Benötigt nun ein

x Z eits chritte

Möchte man ein solches System implementieren, steht man vor einem Problem: Zur

Zustand

x

Berechnung eines neuen Zustands werden alte Eingaben und Zustände benötigt, die

i

den Wert eines vergangenen

Zustands

x

gespeichert werden müssen. Man möchte jedoch nur möglichst wenig Zustände für möglichst

j

zur Berechnung, geht also eine Kante in Graph 1 von einer vergangenen Ausgabe

des Zustands

x

kurze Zeitabschnitte speichern. Der erste Teil des Referats beschäftigt sich mit der

j

zu dem Zustand

xi

, so wird im neuen Graph 2 auch eine Kante von

xj

nach

xi

eingeführt, die die Länge der Verzögerung hat. Die Länge der Kante ist 0, wenn der aktuelle

Bestimmung dieses minimalen Zustandsvektors der gespeicherten Variableninhalte.

(und schon irgendwie neu berechnete) Wert der Zustandsvariable gebraucht wird. Eine solche

Der zweite Teil des Referats beschreibt die Anwendung dieser diskreten dynamischen

Kante kann man sich als eine Art Warteschlange mit dieser Länge vorstellen, der Wert des

Modelle als adaptive Filter, d. h. solche, die sich während des Filtervorgangs an die zu

Zustands wird dort bei jedem Zeitschritt eingeschoben, je nach Länge fällt am anderen Ende

filternden Daten anpassen können. Dazu werden die Zustandsfunktionen des dynamischen

der Kante ein vergangener Wert des Zustands heraus. Wichtig ist, daß immer nur der letzte

Systems als neuronale Netze implementiert und die Netze anhand der zu filternden Daten

Wert der Warteschlange zur Verfügung steht, Werte in der Mitte der Warteschlange sind

trainiert.

unzugänglich. Das Bild rechts oben zeigt diesen Graph für das Beispielmodell.

---

Zuerst wird die minimale Anzahl von Zustandsvariablen bestimmt. Dazu ist zunächst die

2.2 Ebenso können Knoten, die alle ihre Eingaben nur von einem

0

0

2

Beobachtung wichtig, daß Zustandsvariablen, die sich nicht innerhalb von Zyklen befinden,

einzigen Knoten bekommen, und deren Ausgaben auch nur an

0

1

4

also Teilsystemen, in denen die Ausgabe verzögert wieder als Eingabe dient, unnötig sind.

einen einzigen Knoten gehen, gelöscht und die Kanten paarweise

Wird der Wert einer Variablen innerhalb eines Zyklus als Eingabe innerhalb eines zweiten

zu neuen Kanten direkt vom Eingabe- zum Ausgabeknoten

Zyklus gebraucht, so genügt es, den Zyklus um einige Zeitschritte verzögert laufen zu lassen.

kombiniert werden. Die im gelöschten Knoten berechnete

0

0

+

0

2

Werden neuere Werte der gleichen Variablen gebraucht, so kann für jeden Zeitschritt, der die

Funktion wird dabei einfach so oft dupliziert, wie ihre Ausgabe

0

1

+

0

2

Variable später benötigt wird, das Funktionsnetz des ersten Zyklus einmal dupliziert werden.

im Ausgabeknoten gebraucht wird. Die neu gebildeten Kanten

0

0

+

4

Das Ergebnis dieses duplizierten Funktionsnetzes mit den aktuellen Zuständen des

stellen sicher, daß die Eingaben zur Berechnung der Funktion zur

0

1

4

+

4

ursprünglichen Zyklus als Eingabe sind dann die Variablen des Zyklus einen Zeitschritt

rechten Zeit zur Verfügung stehen.

später. Das gleiche Verfahren des Duplizierens ganzer Teile des Modells wird beim Löschen

paralleler Kanten im Netz später im Verfahren noch einmal angewandt.

0

2

1. Alle Kanten, die zu keinem Zyklus gehören, werden also zunächst gelöscht. Nun isolierte

3

stehende Knoten werden ebenfalls gelöscht. Dann sieht unser Beispielgraph so aus:

0

4

4

5

2

2

2

3

2.3 Werden zwei Knoten von mehreren parallelen Kanten

0

2

1

2

4

5

4

2

verbunden, können alle Kanten außer die mit dem größten Delay

3

2

gelöscht werden. Denn steht irgendwo im Funktionsnetz nur ein

0

4

3

älterer Wert zur Verfügung, kann zur Berechnung einer endlichen

4

5

Anzahl folgender Zeitschritte der Teil des Funktionsnetzes

3

mitsamt Rückkopplungen auseinandergefaltet und dupliziert

werden.

0

5

Nach dieser ersten Transformation werden die nun folgenden drei Transformationen solange

nacheinander wiederholt, bis sich der Graph nicht mehr verändert:

Wir wenden die Schritte 2.1-2.3 auf unseren Beispielgraph an. Schritt 2.1 wird hier nicht

2.1 Knoten, deren zuführende Kanten alle den Delay 0 haben,

benötigt:

können gelöscht werden. Statt das Ergebnis der Funktion zu

0

0

x

verzögern, können auch alle Eingaben der Funktion um die

gleiche Zeit verzögert werden und die Funktion selbst in den

2

2

Knoten, die die Ausgabe der Funktion benötigen, berechnet

0

0

y

werden.

2

3

1

2

4

5

4

2

2

2

0

x

2

3

2

2.2

1

2

4

5

0

x

4

3

0

y

0

y

5

2.3

2

5

2

1

2

4

5

2.2

2

5

2.3

7

2

4

7

5

2

4

---

Durch die Wahl der Transformationen haben wir sichergestellt, daß wir alle Variablen in den

Die folgende Formel rechnet gemäß den vorangegangenen Überlegungen die Anzahl der

Zyklen des Systems mit den nun noch übriggebliebenen gespeicherten Variablen vollständig

gespeicherten Variableninhalte aus, die für den ersten Zeitschritt initialisiert und von

berechnen können, wenn wir sie in geeigneten Zeitbereichen speichern, so daß sie

Zeitschritt zu Zeitschritt gespeichert werden müssen:

entsprechend den Kanten verzögert zur Berechnung eines neuen Zeitschritts zur Verfügung

N

stehen. Wichtig ist, daß die Speicherung von Zuständen nur für Zyklen notwendig ist und die

v

= max(

M

min

M

0

,

i

-

e ji

{

Ri

} (

j

-

ji

) )

Größe des Zustandsvektors, also die minimale Anzahl der Speicherplätze für Variablen, für

i

das auf seine Zyklen reduzierte Modell die gleiche ist wie für das vollständige Modell.

wobei

N

die Anzahl der Knoten ist,

Die gespeicherten vergangenen Inhalte von Variablen müssen vor der Berechnung des ersten

Mi

der größte Delay ist an einer Kante, die zum Knoten

i

hinführt,

Zeitschritts mit irgendwelchen Werten initialisiert werden, da sie ja auch schon für die

Ri

die Menge der von Knoten

i

wegführenden Kanten ist,

Berechnung des ersten Zeitschritts gebraucht werden. Auf dieser Grundlage überlegen wir

ji

der Delay an der Kante ist, die von Knoten

i

nach Knoten

j

führt.

nun, wie viele Variableninhalte einer bestimmten Zustandsvariablen in der Vergangenheit

initialisiert werden müssen, um die Berechnung eines Zeitschritts zu ermöglichen.

Für unser Beispielmodell ist die Berechnung ziemlich einfach:

Um eine Variable

i

auszurechnen, müssen ja alle Eingaben der Berechnungsfunktion

i

max (7 ­ min (7 ­ 7), 0) + max (5 ­ min (5 ­ 5), 0) = 12

vorliegen. Läuft das System zu einem Zeitpunkt t0 los, kann selbst, wenn die Werte aller

Variablen ab diesem Zeitpunkt bekannt sind, ein neuer Wert der Variablen

i

erst nach Ablauf

Es müssen also 12 verschiedene Variableninhalte gespeichert werden.

des längsten Delays einer Eingabe von

i

berechnet werden. Alle früheren Inhalte der

Variablen

i

in der Vergangenheit müssen zunächst vor Systemstart initialisiert werden,

ausgerechnet werden können sie nicht.

1.2 Die Bestimmung des Zustandsvektors

Aber warum sollen wir Variableninhalte initialisieren, nach denen uns nie jemand fragt, mit

anderen Worten, die keiner anderen Funktion

Nun ist die Größe des Zustandsvektors bekannt, also die minimale Anzahl der Werte von

j

einer Variablen

j

als Eingabe dienen? Die

Variable

j

wird ebenso wie die Variabel

i

erst ab dem Zeitpunkt berechnet, ab dem die

Variablen, die gespeichert werden müssen, um das Modell ablaufen zu lassen. Welche

Eingabe mit dem längsten Delay von

konkreten Variablen jedoch zu welchen konkreten Zeitabschnitten gespeichert werden

j

zur Verfügung steht. Ist der Delay der Variablen

i

,

die

müssen, hängt auch von den Zusammenhängen zwischen den Zyklen ab. Zur Beantwortung

j

als Eingabe erhält, nun kürzer als der maximale Delay einer Eingabe von

j

, benötigt

wird der Graph des Modells deshalb ganz ähnlich vereinfacht, wie bereits oben gezeigt, nur

zumindest

j

die ältesten Werte der Variablen

i

nicht. Gilt das für alle Funktionen x, die die

müssen Beziehungen zwischen den Zyklen erhalten bleiben, weil ja Variableninhalte eines

Variable

i

als Eingabe haben, müssen diese ältesten Inhalte nicht initialisiert und eben auch

Zyklus für einen anderen Zyklus als Eingabe dienen können und zu diesem Zweck erhalten

nicht gespeichert werden. Das folgende Bild veranschaulicht noch einmal den Sachverhalt:

werden müssen.

xg

7

frühestm ö gliche B erech nung b estim m t v om

Zunächst werden die Knoten der Eingabevariablen und von ihnen abgehende Kanten aus dem

größ ten D ela y einer zuführenden K ante

M

Graph gelöscht, da davon ausgegangen wird, daß die Eingabedaten für jeden beliebigen

i

xh

5

Zeitpunkt zur Verfügung stehen, also nicht noch extra gespeichert werden müssen. Dann wird

x

mit der gleichen Argumentation wie oben der Graph gemäß Schritt 2.1 bis 2.3 vereinfacht.

i

Die nächste Grafik zeigt die einzelnen Schritte mit unserem Beispielgraph:

6

xj

xk

8

M uß nicht initialisiert w erden, da

die W erte nie gebraucht w erden.

---

oder äquivalent

2

2

k

w

k

k

j

-

i

+

ji

i

j

+

ji

- 1

2

3

1

2

6

4

5

4

2

Für jede Kante ergibt sich eine solche Zeile. Nun müssen für alle Variablen

i

nur Werte

ki

,

wi

2

E ing aben a bsch neiden

0

3

gefunden werden, die alle aufgestellten Bedingungen erfüllen. Zum Lösen solcher

2

2

Ungleichungssysteme mit der Nebenbedingung, daß die Summe der Warteschlangenlängen

6

3

0

7

2

3

gleich der Größe des Zustandsvektors sein muß, kann der Simplex-Algorithmus benutzt

1

2

6

4

5

werden.

4

2

2

3

Die zeitlichen Verhältnisse sehen für unser Beispielmodell wie folgt aus:

2.2

2

2

3

t - k - w + 1

t - k

2

2

2

x

2

2

1

2

6

4

5

4

7

2.3

5

2

2

6

5

2

1

2

6

4

5

x 4

2.2

5

t - k - w + 1

t - k

4

4

4

2

2

Daraus ergeben sich die folgenden Ungleichungen:

7

2

6

4

5

2.3

7

5

t

­

k

2 ­

w

2 + 1 + 7

t

­

k

2 + 1

t

­

k

2 + 7

2

6

4

t

­

k

2 ­

w

2 + 1 + 7

t

­

k

4 + 1

t

­

k

2 + 6

t

­

k

4 ­

w

4 + 1 + 7

t

­

k

4 + 1

t

­

k

4 + 7

Zustandsvariablen, die gespeichert werden müssen, befinden sich nur in Zyklen. Alle Knoten,

Außerdem muß gelten:

die außerhalb von Zyklen liegen, werden daher im letzten Schritt mitsamt ankommenden und

abgehenden Kanten gelöscht. Kanten, die Zyklen miteinander verbinden, bleiben so erhalten.

w

2 +

w

4 = 12

Die übriggebliebenen Knoten sind die Zustandsvariablen des Systems und die Kanten zeigen

Ein möglicher Zustandsvektor unseres Systems ist demnach:

die notwendigen Verzögerungen der Werte dieser Zustandsvariablen bei der Berechnung

eines neuen Zeitschritts an.

{

x

2(

t

),

x

2(

t

-1), ...,

x

2(

t

-6),

x

4(t),

x

4(

t

-1), ...,

x

4(

t

-4) }

Von jeder Variablen

i

wird nun eine bestimmte Warteschlange gespeichert. Es muß das Alter

des ersten Werts der Warteschlange

ki

bestimmt werden. Ist

ki

= 0, steht bei der

Neuberechnung des nächsten Zeitschritts

t

+1 der Wert der Variable i zum Zeitpunkt

t

zur

1.3 Die kanonische Form

Verfügung und ihr Wert für

t

+1 wird in diesem Zeitschritt berechnet. Ist

ki

>0, hängt die

Berechnung der Variablen

i

entsprechend viele Zeitschritte hinterher.

Ist der Zustandsvektor bekannt, kann nun die kanonische Form des Netzes erzeugt werden. In

jedem Zeitschritt müssen die Werte des Zustandsvektors aktualisiert werden. Ebenso wie das

Der Parameter

wi

ist dagegen einfach die Länge der Warteschlange. Haben wir die Größe des

Bestimmen von etwaigen Ausgabevariablen, die nicht im Zustandsvektor enthalten sind,

Zustandsvektors v nach Abschnitt 1.1 schon bestimmt, muß nun natürlich gelten

erfolgt das Bestimmen der neuen Werte des Zustandsvektors durch Berechnen der

Bildungsfunktion der jeweiligen Variable. Jede Funktion benötigt bestimmte Variablen

w

=

v

i

mit bestimmten Verzögerungen als Eingaben. Sind diese Variablen mit den gewünschten

Verzögerungen nicht direkt im Zustandsvektor enthalten, so werden diese Variablen

Geht nun im Graph eine Kante von Variable

i

nach Variable

j

mit der Verzögerung

ji

, muß

wiederum berechnet gemäß ihrer Funktion und die Eingaben dieser Funktion werden

bei Neuberechnung der Variable

j

zu jedem neuen Zeitschritt

t

+1, wenn der Werte der

wiederum dem Zustandsvektor entnommen oder berechnet, solange, bis alle Eingaben der

Variablen zur Zeit

t

+1-

kj

bestimmt werden soll, der Wert der Variablen

i

mit der

Funktion im Zustandsvektor enthalten sind. Die korrekte Wahl des Zustandsvektors stellt

entsprechenden zusätzlichen Verzögerung in der Warteschlange stehen. Also muß gelten:

sicher, daß das irgendwann der Fall ist. Viele Variablen müssen dabei nur einmal berechnet

t

-

k

-

w

+ 1 +

t

-

k

+ 1

n

-

k

+

werden und werden von mehreren Funktionen als Eingabe gebraucht. Trotzdem kann der

i

i

ji

j

i

ji

Rechenmehraufwand im Vergleich zu einer naiven Implementierung mit einem größeren

---

Zustandsvektor erheblich sein. Eingabevariablen stehen dabei, wie weiter oben schon gesagt,

2 Der Einsatz neuronaler Netze als Filter

vereinbarungsgemäß zu jedem beliebigen Zeitpunkt zur Verfügung.

Jede Funktion zur Berechnung einer Variablen kann dabei innerhalb der kanonischen Form

Filter arbeiten auf einer zeitlich geordneten Folge von Eingaben, dem Eingabestrom, und

mehrfach vorkommen zur Berechnung der Variablen zu unterschiedlichen Zeitpunkten. Wird

liefern eine ebenso zeitlich geordnete Folge von Ausgaben. Man unterscheidet grundsätzlich

die Funktion dabei von einem neuronalen Feedforward-Netz repräsentiert, muß dieses Netz

zwei verschiedene Arten von Filtern.

zum Beispiel für das Training per Backpropagation mehrfach vorhanden sein. Allerdings ist

die repräsentierte Funktion jedesmal die gleiche, die Gewichte des Netzes sollten also in allen

seinen Instanzen übereinstimmen. Man spricht dabei von Shared Weights, die Gewichte des

Finite Impulse Response (FIR) Filter

Netzes, das die entsprechende Funktion berechnet, kommen eben mehrfach vor, müssen aber

durch entsprechende Updategesetze beim Training des Netzes gleich gehalten werden, weil

Diese Filter haben als Eingabe einen zeitlich beschränkten Ausschnitt aus dem Eingabestrom

sie ja die gleiche Funktion berechnen sollen.

und keine Rückkopplung, speichern also keine Zustände. Ihre Ausgabe hängt nur von dem

diesem Ausschnitt aus dem Eingabestrom ab, weiter in der Vergangenheit liegende Eingaben

Das hier vorgestellte Verfahren zur Bestimmung der kanonischen Form eines diskreten

haben keinen Einfluß auf die Filterausgabe. Der Name Finite Impulse Response rührt daher,

dynamischen Modells ist nicht nur vollständig automatisierbar, sondern auch noch

daß, wenn die Eingabe verschwindet, also Null wird, nach endlicher Zeit auch die Ausgabe

polynomiell in Rechenzeit und Speicherplatz.

verschwindet oder zumindest konstant wird. Die Antwort auf einen Impuls der Eingabe ist

Zum Schluß noch die kanonische Form unseres Beispielmodells, es kommen keine Shared

also endlich. Ein FIR-Filter ist immer stabil in dem Sinne, daß bei endlicher Eingabe keine

Weights vor:

über alle Grenzen wachsende Ausgabe auftreten kann, eine überall endliche Filterfunktion

vorausgesetzt. FIR-Filter können durch Feedforward-Netze realisiert werden.

y (t+ 1 )

x (t+1 )

x (t+1 )

2

4

x (t-1 )

x (t-1 )

1

5

x (t-4 )

3

Infinite Impulse Response (IIR) Filter

Ihr Eingabebereich ist nicht begrenzt, beliebig weit in der Vergangenheit oder Zukunft

liegende Eingaben können Einfluß auf die Ausgabe haben. In der Praxis lassen sich Einflüsse

beliebig lang zurückliegender Eingaben nur durch das Speichern von Zuständen erreichen,

x (t-6 ) x (t-4 ) x (t-2 )

x (t)

x (t)

x (t-2 ) x (t-4 )

2

2

2

2

4

4

4

IIR-Filter sind also Filter mit Rückkopplung. Auch wenn die Eingabe verschwindet, kann sich

1

1

durch die Rückkopplung die Filterausgabe noch beliebig lang ändern, daher rührt der Name

u (t-4 ) x (t-5 ) x (t-3 ) x (t-1 ) u (t-1 ) x (t-1 ) x (t-3 )

7

2

2

2

6

4

4

Infinite Impulse Response. IIR-Filter können instabil sein, durch die Rückkopplung kann die

Filterausgabe über alle Grenzen wachsen. IIR-Filter können durch Feedback-Netze realisiert

werden, sie sind letztendlich nichts anderes als dynamische Systeme, die wir im ersten Teil

des Referats betrachtet haben.

---

2.1 Adaptiver FIR-Filter mit Feedforward-Netz

Man kann sich auch darauf beschränken, nicht jeden, sondern nur alle n Zeitschritte eine

Trainingsphase einzulegen und dazwischen das Netz unverändert als Filter arbeiten zu lassen.

E in einzelne r Ze itschritt:

Wir wollen nun den Einsatz

Das spart Rechenzeit, und es sind nicht für alle Zeitschritte Zielausgaben erforderlich.

neuronaler Netze als adaptive Filter

betrachten. Diese Filter werden

während des Filtervorgangs an die

2.2 Adaptiver IIR-Filter mit Feedback-Netz

wechselnde Charakteristik der Daten

angepaßt. Das setzt voraus, daß wir

Hier wird ein dynamisches System, wie wir es im ersten Teil betrachtet haben, als Filter

eine Zielausgabe des Filters zur

eingesetzt. Die externe Eingabe des Systems ist wie beim FIR-Filter ein zeitlich begrenzter

Verfügung haben. Während des

gew ün schte

Ausschnitt aus der Eingabefolge, der wie beim FIR-Filter in jedem Zeitschritt ein Element

Filtervorgangs wird die Ausgabe des

Filterausga be d(t-2)

weiter geschoben wird.

Filters mit der Zielausgabe verglichen

w ij(t-1)

und die Gewichte des neuronalen

Der Feedforward-Teil eines Feedback-Netzes hat zusätzlich zu den Eingaben aus dem zu

Netzes entsprechend trainiert.

filternden Datenstrom noch seine Zustandsvariablen als Eingaben. Es gibt mehrere

1

w (t)

Möglichkeiten, diese Zustandsvariablen zu initialisieren.

i j

Die Eingabe des Feedforward-Netzes

d(t-1)

ist entsprechend dem Konzept des

FIR-Filters ein zeitlich beschränkter

w (t-1 )

2.2.1 Hard Clamping ­ Directed Algorithm

i j

Bereich der Eingabefolge, im

nebenstehenden Beispiel werden drei

+ 2

w (t)

Am einfachsten ist es, wenn nicht nur

i j

aufeinanderfolgende Werte zu einem

für die Filterausgaben, sondern für alle

Eingabeblock zusammengefaßt. In

d(t)

Zustandsvariablen Zielwerte zur

jedem Zeitschritt wird dieser

Verfügung stehen. Man kann dann in

Abschnitt um ein Wert

S o llzustand zum Zeitp unkt t-3

w (t-1 )

jedem Zeitschritt diese Sollwerte in

i j

weitergeschoben. Um den Netzfehler

das Netz geben und die Gewichte so

klein zu halten, kann es günstig sein,

+ 3

w (t)

D (t-3)

trainieren, daß die Sollwerte des

i j

nicht nur den aktuellen

Filterausga be y(t)

nächsten Zeitschritts als Ergebnis

D (t-2)

Eingabebereich als Trainingsdaten zu

w (t)

i j

generiert werden. Die Zustände können

benutzen, sondern auch einige

w (t) = w (t-1) + w (t)

dann als zusätzliche Eingabe in ein

w ij(t-1)

i j

i j

i j

Zeitschritte zurückliegende Eingabe-

Feedforward-Netz aufgefaßt werden.

blöcke noch einmal zum Training

Das Training erfolgt genauso wie beim

1

w ij (t)

heranzuziehen. Wie weit man dabei zurückgeht, bestimmt einmal die verfügbare Rechenzeit,

D (t-2)

reinen Feedforward-Netz per

zum anderen die Veränderlichkeit der Datencharakteristik. Ändert sich die Charakteristik der

Backpropagation.

D (t-1)

Daten sehr schnell, muß das Netz sehr flexibel lernen. Alte Blöcke aus dem Datenstrom

haben dann kaum noch Relevanz für die aktuell verlangte Filterstruktur. Ändert sich die

Die Ausgabe weicht nur durch einen

w ij(t-1)

Charakteristik langsam, können auch die Eingabeblöcke, die vor einigen Zeitschritten aktuell

Zeitschritt vom Sollwert ab, damit ist

2

waren, noch als Trainingsdaten genutzt werden. Im Beispiel werden die letzten drei der

+

das Ergebnis des Trainings sehr gut.

w (t)

i j

D (t-1)

jeweils drei Werte großen Eingabeblöcke zum Training benutzt.

Diesen Algorithmus bezeichnet man

D (t)

auch als directed algorithm oder Hard-

Das Trainieren des Netzes ist trivial. Das Netz kann behandelt werden wie jedes

clamping, weil der Zustand des

Feedforward-Netz. Jeder Eingabeblock wird an das Netz angelegt, per Backpropagation

w (t-1 )

dynamischen Systems auf den Sollwert

i j

werden für jeden Eingabeblock der Fehler und das Gewichtsupdate berechnet. Die Summe

festgeklemmt wird und sich nicht frei

+ 3

w (t)

der Updates der drei Blöcke ergibt den Gesamtupdate, gemäß dem die Gewichte für den

i j

verändern kann.

nächsten Zeitschritt verändert werden. Die Ausgabe des Netzes für den aktuellen Block ist die

y(t)

w (t)

aktuelle Filterausgabe.

i j

w

wij(t)

i j ( t) = w i j ( t-1 ) +

Dieser einfache Algorithmus kann in mehrere Richtungen modifiziert werden. Soll der

Ausgabefehler noch kleiner gemacht werden, können pro Zeitschritt mehrere

Trainingsschritte durchgeführt werden. Nach jedem Trainingsschritt werden die Gewichte

gew ü n schte Zustä nd e

verändert und danach mit den gleichen Eingabeblöcken wieder trainiert. Die Ausgabe des

tats ächliche Z ustä n de

letzten Trainingsschritts ist dann die aktuelle Filterausgabe.

berechn eter Fehle r

---

2.2.2 Semidirected Algorithm

2.2.3 Undirected Algorithm

Um die Zahl der notwendigen

Sollzustände zu reduzieren, wird

W ird be hand elt w ie ein große s

d(t-3)

hier nur der erste Trainingsblock

N etzw erk m it E in- un d A usgabe n

Initia lisierung aus e rstem

mit seinem Sollzustand initialisiert,

inne rhalb in nerer S chichten.

w (t-2)

i j

B lock des vorhe rge hend en

für alle anderen Trainingsblöcke

Ze itschritts

muß wieder nur eine Sollausgabe

D (t-3)

zur Verfügung stehen. Die Nach-

folgeblöcke benutzen, wie beim

d(t-2)

d(t-2)

dynamischen System eigentlich

w (t-1)

gedacht, den Zustand, der im

i j

w (t-1)

i j

D ie U pd ates, d ie w eit o ben

vorhergehenden Trainingsblock

1

bere chn et w erden, sin d stark

berechnet wurde, als Eingabe.

w (t)

i j

von den a lten G ew ich ten w (t-2)

Insgesamt bilden die über ihre

i j

d(t-1)

d(t-1) bee influßt u nd w e rde n de shalb

Zustandsvariablen kaskadierten

nicht verw en d et.

Feedforward-Netze des Filters ein

w (t-1)

i j

w ij(t-1)

großes Feedforward-Netz mit dem

2

Sollzustand und dem ersten Block

+ w (t)

1

i j

w (t)

i j

aus dem Datenstrom als Eingaben

an der ersten Schicht und weiteren

d(t)

d(t)

Datenblöcken an verborgenen

Schichten, wenn mehr als ein

w (t-1)

i j

w (t-1)

i j

Trainingsblock vorhanden ist.

+ 3

w (t)

2

Ebenso gibt es Ausgaben sowohl

i j

+ wij (t)

am Ende, das ist die Filterausgabe

y(t)

w (t)

y(t)

i j

w (t)

w (t) = w (t-1) +

w (t)

für diesen Zeitschritt, als auch in

i j

i j

i j

i j

w (t) = w (t-1) + w (t)

den Zwischenschichten, das sind

i j

i j

i j

die Ausgaben der anderen

Stehen überhaupt keine Sollwerte für die Zustandsvariablen zur Verfügung, kann der erste

Trainingsblöcke, die auf älteren

Trainingsblock mit den Zustandsvariablen gefüttert werden, die vom ersten Trainingsblock

Abschnitten des Datenstroms arbeiten.

des vorhergehenden Zeitschritts berechnet wurden. Die übrigen Trainingsblöcke laufen dann

wieder auf den Zustandsvariablen des vorhergehenden Blocks. Die

Gelernt wird wieder per (auf Ein- und Ausgaben in Zwischenschichten erweitertem)

hintereinandergeschalteten Trainingsblöcke ergeben wieder ein Gesamtnetzwerk mit Ein- und

Backpropagation. Wichtig ist, daß das zusammengefaßte Netz aus in unserem Fall drei

Ausgaben in verborgenen Schichten. Bereits der Zustand des ersten Trainingsblocks weicht

Instanzen des Feedforward-Teils unseres Feedback-Netzes besteht. Die Gewichte sind daher

vom Sollzustand ab. Zur Korrektur der Gewichte werden die in den einzelnen

in jedem Exemplar gleich. Für das Lernen per Backpropagation müssen nur die

Trainingsblöcken ermittelten Updates wieder zu einem Gesamtupdate addiert.

Speicherplätze für Neuronausgabe und ­ableitung dupliziert werden. Für jedes Gewicht

werden dann wieder so viele Updates berechnet, wie Trainingsblöcke da sind, und die

Gewichte mit der Summe der Einzelupdates aktualisiert.

Der Zustand ist nur für den ersten Trainingsblock exakt, danach weicht er durch Netzfehler

gew ün sch te Zu stände

mehr und mehr vom Soll ab.

tatsä ch lich e Zustä n de

berechnete r Fe hler

Es gibt allerdings einen einschneidenden Unterschied zu den beiden oben beschriebenen

Trainingsmethoden. Die Ermittlung der Gewichtsupdates kann nicht durch Backpropagation

gew ün schte Z ustände

erfolgen. Wie im nächsten Abschnitt gezeigt, setzt Backpropagation voraus, daß die Eingaben

tatsä chlich e Zu stä nde

des Netzes von den Netzgewichten unabhängig sind. In unserem Fall, wo wir es eigentlich

mit einem echten rekurrenten Netz zu tun haben, die Eingaben also von dem Netz selbst

berechneter F ehler

stammen, ist der vom vorherigen Zeitschritt übernommene Zustandsvektor nicht unabhängig

von den Gewichten. Diese Abhängigkeit sollte berücksichtigt werden, indem zu jeder

---

Zustandsvariablen die Abhängigkeit bezüglich der Gewichte in Form eines Gradienten mit

Das ist die Ausgabe eines Neurons:

übergeben werden. Die Berechnung des Netzfehlers durch Forward Computation erlaubt

diese Berücksichtigung.

o

f

w o

p

=

pk k

k

Die Berücksichtigung des Gradienten des vom vorhergehenden Zeitschritt übernommenen

Zustands macht die Berechnung zwar genauer, jedoch auch nicht exakt, weil sich der vom

wobei

op

die Ausgabe des Neurons

p

ist,

vorhergehenden Zeitschritt übernommene Gradient auf die Werte der Gewichte dieses

wpk

das Gewicht an der Synapse von Neuron

j

nach Neuron

i

ist,

Zeitschritts bezieht, nicht auf die aktuellen Gewichte, die bereits durch das Gewichtsupdate

k

die Neuronen sind, von denen das Neuron

p

einen Input erhält,

korrigiert wurden. Ein gewisser Fehler bei der Berechnung des Gewichtsupdates kann daher

f

die Squashing function oder Sigmoide ist.

nicht vermieden werden. Eine Möglichkeit, den Fehler klein zu halten, ist, die errechneten

Updates der ersten Trainingsblöcke nicht in das Gesamtupdate einzubeziehen, da sie noch zu

Die einfach ausgerechnete Ableitung der Ausgabe ist:

stark von den alten Gewichten beeinflußt sind. Im Beispiel wurde das Update des ersten

Trainingsblocks verworfen.

op

=

f

o

w o

w

o

pk

k

k

pk

+

w

j i

=

p

w

ij

k

k

Natürlich kann Backpropagation trotz allem benutzt werden, es ist erheblich schneller als

ij

Forward Computation, nur ist das Gewichtsupdate dann entsprechend stärker fehlerbehaftet.

Wie man sieht, werden die Ableitungen der Neuroneingabe für die Berechnung der Ableitung

der Ausgabe benötigt. Wieviele Summanden müssen verarbeitet werden? Für jeden Eingang

eines Neurons steht ein Term in den Summen. Im ganzen Netz stehen so viele Terme in den

2.3 Methoden zur Berechnung des Fehlergradienten

Summen, wie es Eingänge in Neurone und damit Gewichte im Netz gibt. Die Komplexität der

Berechnung der oben genannten Formel ist daher O(n), wenn n die Anzahl der Gewichte ist.

Wichtig ist, daß die oben genannte Formel für jedes (!) Gewicht ausgerechnet werden muß,

denn sie bezeichnet nur die Ableitung nach einem Gewicht, es wird aber die Ableitung nach

2.3.1 Forward Computation

jedem Gewicht benötigt, zusammen bilden die Ableitungen dann wieder den Gradientvektor

des Neuronausgangs. Also muß die Formel für nicht nur einmal, sondern n mal für jedes

Forward Computation ist die intuitivere der beiden Methoden zur Berechnung des Netzfehlers

Neuron angewandt werden. Die Komplexität der Forward Computation ist daher O(n2).

und seines Gradienten. Jedes Eingabeneuron bringt zusätzlich zu seiner Aktivität noch die

Ableitungen der Aktivität nach allen Gewichten als ein Gradientvektor in das Netz. Ist die

Der Vorteil diese langsamen Verfahrens ist, daß ein Gradient der Eingabe leicht

Eingabe unabhängig von den Gewichten, das ist normalerweise der Fall, sind diese

berücksichtigt werden kann.

Ableitungen eben alle Null.

Nun berechnet jedes Neuron aus der Ableitung seiner Eingänge nach den Gewichten die

2.3.2 Backpropagation

Ableitung seines Ausgangs nach den Gewichten. So wird von den Eingängen zum

Netzausgang die Ableitung der Gewichte zusammen mit der Netzausgabe durch das Netz

Wir sind eigentlich ja nicht an der Ableitung irgendwelcher Neuronausgaben interessiert,

propagiert. Am Ende erfolgt dann die Berechnung der Ableitung des Netzfehlers, die hier

sondern nur an der Ableitung des Fehlers nach den Gewichten, am Ende sollen schließlich

nicht angegeben, weil trivial ist.

Gewichtsupdates bestimmt werden, die den Fehler minimieren. Nun stellen wir folgende

Schlüsselbeobachtung an: Ändere ich ein Gewicht

wij

, ändert sich dadurch für das Netz nur

die Ausgabe des Neurons

i

, an dessen Eingang das Gewicht

wij

liegt. Die Fragestellung

reduziert sich dann darauf, wie sich der Netzfehler E mit der Ausgabe des Neurons i ändert:

E

E

o

i

=

w

o

w

ij

i

ij

wobei

E

der Netzfehler ist,

oi

die Ausgabe des Neurons

i

ist,

wij

das Gewicht an der Synapse von Neuron

j

nach Neuron

i

ist.

Die beiden Faktoren lassen sich nach der Kettenregel noch weiter zerlegen. Das veränderte

Gewicht

wij

verändert die Ausgabe des Neurons

i

, indem es die kumulierte Eingabe des

Neurons verändert:

---

o

o

net

Die noch fehlende Ableitung der kumulierten Netzeingabe nach dem Gewicht an der

i

i

i

=

w

net

w

zuführende Kante ist einfach die Ausgabe des Neurons, das über diese Kante feuert.

ij

i

ij

E

E

net

E

wobei

i

=

=

o j

w

net

w

net

ij

ij

ij

i

net

w o

i

=

ij j

j

Schon im Ansatz steckt, daß die Veränderung eines Gewichts nur anhand der durch sie

bewirkten Änderung der Eingabe des damit verbundenen Neurons berücksichtigt wird. Ein

die kumulierte Eingabe des Neurons

i

ist.

Gradient der Eingaben kann daher nicht berücksichtigt werden.

Die Ausgabe des Neurons

i

verändert den Netzfehler durch die Veränderung der kumulierten

Backpropagation ist schnell: Es gibt im ganzen Netz wieder soviel Terme der Summe, wie es

Neuroneingabe der nachgeschalteten Neurone

k

, die Summe über alle nachgeschalteten

Kanten bzw. Gewichte gibt, aber für jedes Neuron wird die Formel nur einmal ausgewertet.

Neurone

k

ergibt die Gesamtänderung:

Die Komplexität von Backpropagation ist daher O(n), wenn n die Anzahl der Gewichte ist.

E

=

E

netk

Der Trade-off zwischen Forward Computation und Backpropagation wird jetzt deutlich: Bei

o

net

o

i

k

k

i

Backpropagation kann sich die Veränderung eines Gewichts nur an einer der n Kanten

auswirken. Bei der Forward Computation kann theoretisch jedes Gewicht den Gradienten an

Insgesamt ergibt sich

jeder Kante verändern, es ist nicht zwingend, daß jedes Gewicht nur an seiner Kante wirkt,

wie es in der Praxis neuronaler Netze geschieht. Die Reduktion von n möglichen Kanten zu

E

E

net

o

net

k

i

i

=

.

der einen, der das Gewicht wirklich zugeordnet ist, ergibt die Komplexitätsverbesserung um

w

net

o

net

w

ij

k

k

i

i

ij

den Faktor n, gleichzeitig aber die genannte Einschränkung, daß Gradienten irgendwelcher

Eingaben nicht berücksichtigt werden können.

Literatur:

G. Dreyfus et al., The Canonical Form of Nonlinear Discrete-Time Models

O. Nerrand et al., Neural Networks and Nonlinear Adaptive Filtering: Unifying Concepts and
New Algorithms

F. J. Pineda, Recurrent Backpropagation Networks

Donald R. Tveter, The Backprop Algorithm

In einem Backpropagationsschritt wird für jedes Neuron zunächst der verteilte Fehler

berechnet:

E

= -

E

net

o

w f

(

net

)

i

=

k

i

= -

k ik

net

net

o

net

i

k

k

i

i

i

k

wobei

-

k

der verteilte Fehler des Neurons

k

ist.

Wie man sieht, wird dazu der verteilte Fehler der nachgeschalteten Neuronen gebraucht, der

im vorhergehenden Schritt berechnet wurde und nun zurückpropagiert wird. Die Ableitung

der kumulierten Netzeingabe des Neurons

k

nach der Ausgabe des Neurons

i

, das seine

Ausgabe an Neuron

k

schickt, ist einfach das Gewicht zwischen beiden Neuronen. Die

Ableitung der Ausgabe von Neuron

i

nach seiner kumulierten Eingabe ist die Ableitung der

Squashing function.

---