LMS-Algorithmus

Der LMS-Algorithmus (Least-Mean-Squares-Algorithmus) ist ein Algorithmus zur Approximation der Lösung des Least-Mean-Squares-Problems, das z. B. 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 Methode des steilsten Abstiegs (Gradientenverfahren) und schätzt den Gradienten auf einfache Art. Der Algorithmus arbeitet zeitrekursiv, d. h. 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, u. a. bei adaptiven Filtern, adaptive Regelungen und Online-Identifikationsverfahren.

Ein bedeutender Nachteil des LMS-Algorithmus ist die Abhängigkeit seiner Konvergenzgeschwindigkeit von den Eingangsdaten, d. h. er findet unter ungünstigen Umständen (schnelle zeitliche Änderungen der Eingangsdaten) möglicherweise keine Lösung.

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

min w → ∑ i = 1 n ( y i − x i T w → ) 2 ⟺ min w ‖ y − X w → ‖ 2 2 {\displaystyle \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 {\displaystyle w_{1}} und wählt bei jedem Iterationsschritt i ≥ 1 {\displaystyle i\geq 1} die Funktion ( y i − x i T w → ) 2 {\displaystyle (y_{i}-x_{i}^{T}{\vec {w}})^{2}} aus und führt einen Gradientenabstieg für diese Funktion durch:

∂ ( y i − x i T w → ) 2 ∂ w → = − 2 x i ( y i − x i T w → ) w i + 1 → = w i → − h ∂ ( y i − x i T w → ) 2 ∂ w → = w i → + 2 h x i ( y i − x i T w i → ) {\displaystyle {\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 w → 1 n ∑ i = 1 n f i ( w ) {\displaystyle \min _{\vec {w}}{\frac {1}{n}}\sum _{i=1}^{n}f_{i}(w)}

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

w i + 1 → = w i → − h i ∇ f i ( w ) {\displaystyle {\vec {w_{i+1}}}={\vec {w_{i}}}-h_{i}\nabla f_{i}(w)}

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 x → ( n ) T w → ( n ) {\displaystyle {\vec {x}}(n)^{T}{\vec {w}}(n)} und vorgegebenen Referenzdaten y ( n ) {\displaystyle y(n)} minimiert wird.

Der LMS-Algorithmus hat dann folgende Form:

e ( n ) = y ( n ) − x → ( n ) T w → ( n ) {\displaystyle e(n)=y(n)-{\vec {x}}(n)^{T}{\vec {w}}(n)}

w → ( n + 1 ) = w → ( n ) + μ e ( n ) x → ( n ) {\displaystyle {\vec {w}}(n+1)={\vec {w}}(n)+\mu e(n){\vec {x}}(n)}

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

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

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

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

∇ h ^ H C ( n ) = ∇ h ^ H E { e ( n ) e ∗ ( n ) } = 2 E { ∇ h ^ H ( e ( n ) ) e ∗ ( n ) } {\displaystyle \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 ∇ {\displaystyle \nabla } der Gradientenoperator ist:

∇ h ^ H ( e ( n ) ) = ∇ h ^ H ( d ( n ) − h ^ H ⋅ x ( n ) ) = − x ( n ) {\displaystyle \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)}

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

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

h ^ ( n + 1 ) = h ^ ( n ) − μ 2 ∇ C ( n ) = h ^ ( n ) + μ E { x ( n ) e ∗ ( n ) } {\displaystyle {\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 μ 2 {\displaystyle {\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.

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

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

wobei N {\displaystyle N} die Anzahl der Stichproben angibt, die für diese Schätzfunktion verwendet wird.

Der einfachste Fall ist N = 1 {\displaystyle N=1} :

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

Für diesen Fall ist der Aktualisierungsalgorithmus wie folgt:

h ^ ( n + 1 ) = h ^ ( n ) + μ x ( n ) e ∗ ( n ) {\displaystyle {\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.

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.

• Methode der kleinsten Quadrate

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

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