LMS-Algorithmus

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.

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.

Algorithmus

Beim Problem der kleinsten Quadrate muss ein Vektor ${\vec {w}}$ bestimmt werden, so dass die Differenzen $y_{i}-x_{i}^{T}{\vec {w}}$ insgesamt minimiert werden. Daraus ergibt sich die Formel

$\min _{\vec {w}}\sum _{i=1}^{n}(y_{i}-x_{i}^{T}{\vec {w}})^{2}\Longleftrightarrow \min _{w}\|y-X{\vec {w}}\|_{2}^{2}$

Der LMS-Algorithmus startet an einem bestimmten Punkt $w_{1}$ und wählt bei jedem Iterationsschritt $i\geq 1$ die Funktion $(y_{i}-x_{i}^{T}{\vec {w}})^{2}$ aus und führt einen Gradientenabstieg für diese Funktion durch:

${\begin{aligned}{\frac {\partial (y_{i}-x_{i}^{T}{\vec {w}})^{2}}{\partial {\vec {w}}}}&=-2x_{i}(y_{i}-x_{i}^{T}{\vec {w}})\\{\vec {w_{i+1}}}&={\vec {w_{i}}}-h{\frac {\partial (y_{i}-x_{i}^{T}{\vec {w}})^{2}}{\partial {\vec {w}}}}\\&={\vec {w_{i}}}+2hx_{i}(y_{i}-x_{i}^{T}{\vec {w_{i}}})\\\end{aligned}}$

Für das verallgemeinerte Optimierungsproblem

$\min _{\vec {w}}{\frac {1}{n}}\sum _{i=1}^{n}f_{i}(w)$

wird für den Vektor ${\vec {w}}$ der verallgemeinerte Iterationsschritt

${\vec {w_{i+1}}}={\vec {w_{i}}}-h_{i}\nabla f_{i}(w)$

mit dem Nabla-Operator durchgeführt.

Beim LMS-Algorithmus geht es darum, die Koeffizienten eines FIR-Filters so zu bestimmen, dass der Fehler zwischen Ausgangsdaten des Filters ${\vec {x}}(n)^{T}{\vec {w}}(n)$ und vorgegebenen Referenzdaten $y(n)$ minimiert wird.

Der LMS-Algorithmus hat dann folgende Form:

$e(n)=y(n)-{\vec {x}}(n)^{T}{\vec {w}}(n)$

${\vec {w}}(n+1)={\vec {w}}(n)+\mu e(n){\vec {x}}(n)$

Dabei ist ${\vec {x}}(n)$ ein Vektor mit Eingangsdaten der Zeitpunkte $n-(M+1)$ bis $n,y(n)$ ein Referenzdatum zum Zeitpunkt $n$, ${\vec {w}}(n)$ der aktuelle Vektor der Filtergewichte des Transversalfilters der Ordnung $M,\mu$ ein Faktor zur Einstellung der Geschwindigkeit und Stabilität der Adaption und ${\vec {w}}(n+1)$ der neu zu bestimmende Filtervektor der Ordnung $M$. Es wird also zu jedem Zeitpunkt der aktuelle Fehler bestimmt und daraus werden die neuen Filtergewichte ${\vec {w}}(n+1)$ berechnet.

Ableitungsfunktion

Die Idee hinter LMS-Filtern besteht darin, den steilsten Abstieg zu verwenden, um Filtergewichte ${\hat {\mathbf {h} }}(n)$ zu finden, die eine Kostenfunktion minimieren. Wir beginnen mit der Definition der Kostenfunktion als

$C(n)=E\left\{|e(n)|^{2}\right\}$

wobei $e(n)$ die Abweichung bei der aktuellen Stichprobe $n$ ist und $E\{\cdot \}$ 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

$\nabla _{{\hat {\mathbf {h} }}^{H}}C(n)=\nabla _{{\hat {\mathbf {h} }}^{H}}E\left\{e(n)\,e^{*}(n)\right\}=2E\left\{\nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))\,e^{*}(n)\right\}$

zu nehmen, wobei $\nabla$ der Gradientenoperator ist:

$\nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))=\nabla _{{\hat {\mathbf {h} }}^{H}}\left(d(n)-{\hat {\mathbf {h} }}^{H}\cdot \mathbf {x} (n)\right)=-\mathbf {x} (n)$

$\nabla C(n)=-2E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}$

Nun ist $\nabla C(n)$ 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 $\nabla C(n)$ machen. Um das mathematisch auszudrücken

${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)-{\frac {\mu }{2}}\nabla C(n)={\hat {\mathbf {h} }}(n)+\mu \,E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}$

wobei ${\frac {\mu }{2}}$ 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

Für die meisten Systeme muss die Erwartungsfunktion ${E}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}$ approximiert werden. Dies kann mit der folgenden erwartungstreuen Schätzfunktion

${\hat {E}}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}={\frac {1}{N}}\sum _{i=0}^{N-1}\mathbf {x} (n-i)\,e^{*}(n-i)$

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

${\hat {E}}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}=\mathbf {x} (n)\,e^{*}(n)$

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

${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+\mu \mathbf {x} (n)\,e^{*}(n)$

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

Verwendung in der Neuroinformatik

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.

Weblinks

• Ausführliche Herleitung der Delta-Regel für Neuronale Netze