LMS-Algorithmus

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Deltaregel)
Zur Navigation springen Zur Suche springen

Der LMS-Algorithmus (Least-Mean-Squares-Algorithmus) ist ein Algorithmus zur Approximation der Lösung des Least-Mean-Squares-Problems, das zum Beispiel in der digitalen Signalverarbeitung vorkommt. In der Neuroinformatik ist der Algorithmus vor allem als Delta-Regel oder Widrow-Hoff-Regel bekannt.

Der Algorithmus beruht auf der sogenannten Methode des steilsten Abstiegs (Gradientenverfahren) und schätzt den Gradienten auf einfache Art. Der Algorithmus arbeitet zeitrekursiv, das heißt, mit jedem neuen Datensatz wird der Algorithmus einmal durchlaufen und die Lösung aktualisiert. Die Regel wurde erstmals 1960 von Bernard Widrow und Marcian Edward Hoff für das Einlernen des Adaline-Modells verwendet.[1]

Der LMS-Algorithmus wird auf Grund seiner geringen Komplexität häufig eingesetzt. Einsatzgebiete sind unter anderem adaptive Filter, adaptive Regelungen und Online-Identifikationsverfahren.

Ein bedeutender Nachteil des LMS-Algorithmus ist die Abhängigkeit seiner Konvergenzgeschwindigkeit von den Eingangsdaten, das heißt, der Algorithmus findet unter ungünstigen Umständen möglicherweise keine Lösung. Ungünstige Umstände sind schnelle zeitliche Änderungen der Eingangsdaten.

Beim Problem der kleinsten Quadrate muss ein Vektor bestimmt werden, so dass die Differenzen insgesamt minimiert werden. Daraus ergibt sich die Formel

Der LMS-Algorithmus startet an einem bestimmten Punkt und wählt bei jedem Iterationsschritt die Funktion aus und führt einen Gradientenabstieg für diese Funktion durch:

Für das verallgemeinerte Optimierungsproblem

wird für den Vektor der verallgemeinerte Iterationsschritt

mit dem Nabla-Operator durchgeführt.[2]

Beim LMS-Algorithmus geht es darum, die Koeffizienten eines FIR-Filters so zu bestimmen, dass der Fehler zwischen Ausgangsdaten des Filters und vorgegebenen Referenzdaten minimiert wird.

Der LMS-Algorithmus hat dann folgende Form:

Dabei ist ein Vektor mit Eingangsdaten der Zeitpunkte bis ein Referenzdatum zum Zeitpunkt , der aktuelle Vektor der Filtergewichte des Transversalfilters der Ordnung ein Faktor zur Einstellung der Geschwindigkeit und Stabilität der Adaption und der neu zu bestimmende Filtervektor der Ordnung . Es wird also zu jedem Zeitpunkt der aktuelle Fehler bestimmt und daraus werden die neuen Filtergewichte berechnet.

Ableitungsfunktion

[Bearbeiten | Quelltext bearbeiten]

Die Idee hinter LMS-Filtern besteht darin, den steilsten Abstieg zu verwenden, um Filtergewichte zu finden, die eine Kostenfunktion minimieren. Wir beginnen mit der Definition der Kostenfunktion als

wobei die Abweichung bei der aktuellen Stichprobe ist und den Erwartungswert bezeichnet. Diese Kostenfunktion ist die mittlere quadratische Abweichung und wird vom LMS-Algorithmus minimiert. Die Anwendung des steilsten Abstiegs bedeutet, die partiellen Ableitungen in Bezug auf die einzelnen Einträge des Filterkoeffizienten-Vektors

zu nehmen, wobei der Gradientenoperator ist:

Nun ist ein Vektor, der auf den steilsten Anstieg der Kostenfunktion zeigt. Um das Minimum der Kostenfunktion zu finden, müssen wir einen Schritt in die entgegengesetzte Richtung von machen. Um das mathematisch auszudrücken

wobei die Schrittgröße (Anpassungskonstante) ist. Das heißt, wir haben einen sequentiellen Aktualisierungsalgorithmus gefunden, der die Kostenfunktion minimiert. Leider ist dieser Algorithmus erst realisierbar, wenn wir E kennen. Im Allgemeinen wird der obige Erwartungswert nicht berechnet. Um den LMS-Algorithmus stattdessen in einer Online-Umgebung (Aktualisierung nach Erhalt jedes neuen Beispiels) auszuführen, verwenden wir eine Schätzfunktion dieses Erwartungswerts.

Vereinfachungen

[Bearbeiten | Quelltext bearbeiten]

Für die meisten Systeme muss die Erwartungsfunktion approximiert werden. Dies kann mit der folgenden erwartungstreuen Schätzfunktion

erfolgen, wobei die Anzahl der Stichproben angibt, die wir für diese Schätzfunktion verwenden. Der einfachste Fall ist :

Für diesen einfachen Fall ist der Aktualisierungsalgorithmus wie folgt:

Dies stellt tatsächlich den Aktualisierungsalgorithmus für den LMS-Filter dar.

Verwendung in der Neuroinformatik

[Bearbeiten | Quelltext bearbeiten]

Der LMS-Algorithmus gehört zur Gruppe der überwachten Lernverfahren. Dazu muss ein externer Lehrer existieren, der zu jedem Zeitpunkt der Eingabe die gewünschte Ausgabe, den Zielwert, kennt.

Er kann auf jedes einschichtige künstliche neuronale Netz angewendet werden, dabei muss die Aktivierungsfunktion differenzierbar sein. Das Backpropagation-Verfahren verallgemeinert diesen Algorithmus und kann auch auf mehrschichtige Netze angewandt werden.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Bernard Widrow und Marcian Edward Hoff: Adaptive switching circuits. IRE WESCON Convention Record, vol. 4, Los Angeles 1960, S. 96–104 (PDF).
  2. Jiantao Jiao, University of California, Berkeley: Gradient Descent and Least Mean Squares Algorithm