imported>Acky69: s.auch hinzu

2024-11-13T08:14:39Z

s.auch hinzu

Neue Seite

Der '''LMS-Algorithmus''' ('''''L'''east-'''M'''ean-'''S'''quares-'''Algorithmus''''') ist ein [[Algorithmus]] zur [[Approximation]] der Lösung des ''Least-Mean-Squares''-Problems, das z. B. in der [[Digitale Signalverarbeitung|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ätzung #Schätzungen_in_der_Statistik|schätzt]] den [[Gradient]]en auf einfache Art. Der Algorithmus arbeitet zeit[[rekursiv]], 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 [[Maschinelles Lernen|Einlernen]] des [[Adaline-Modell]]s verwendet.<ref name="widrow"/>

Der LMS-Algorithmus wird auf Grund seiner geringen Komplexität häufig eingesetzt, u. a. bei [[Adaptiver Filter|adaptiven Filtern]], [[adaptive Regelung]]en und [[Online]]-[[Identitätsfeststellung|Identifikation]]s<nowiki></nowiki>verfahren.

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.

== Algorithmus ==
Beim Problem der kleinsten Quadrate muss ein [[Vektor]] <math>\vec{w}</math> bestimmt werden, so dass die Differenzen <math>y_i - x_i^T \vec{w}</math> insgesamt minimiert werden. Daraus ergibt sich die Formel

:<math>\min_{\vec{w}} \sum_{i=1}^{n}(y_i - x_i^T \vec{w})^2 \Longleftrightarrow \min_{w} \|y - X \vec{w}\|_2^2</math>

Der LMS-Algorithmus startet an einem bestimmten Punkt <math>w_1</math> und wählt bei jedem Iterationsschritt <math>i \geq 1</math> die Funktion <math>(y_i - x_i^T \vec{w})^2</math> aus und führt einen [[Gradientenabstieg]] für diese Funktion durch:

:<math>\begin{align}
\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{align}
</math>

Für das verallgemeinerte [[Optimierungsproblem]]

:<math>\min_{\vec{w}} \frac{1}{n} \sum_{i=1}^{n} f_i(w)</math>

wird für den [[Vektor]] <math>\vec{w}</math> der verallgemeinerte Iterationsschritt

:<math>\vec{w_{i+1}} = \vec{w_i} - h_i \nabla f_i(w)</math>

mit dem [[Nabla-Operator]] durchgeführt.<ref>Jiantao Jiao, University of California, Berkeley: [https://people.eecs.berkeley.edu/~jiantao/225a2020spring/scribe/EECS225A_Lecture_16.pdf Gradient Descent and Least Mean Squares Algorithm]</ref>

Beim LMS-Algorithmus geht es darum, die Koeffizienten eines [[Filter mit endlicher Impulsantwort|FIR-Filters]] so zu bestimmen, dass der Fehler zwischen Ausgangsdaten des Filters <math>\vec x(n)^T \vec w(n)</math> und vorgegebenen Referenzdaten <math>y(n)</math> minimiert wird.

Der LMS-Algorithmus hat dann folgende Form:

:<math>e(n) = y(n) - \vec x(n)^T \vec w(n)</math>

:<math>\vec w(n+1) = \vec w(n) + \mu e(n) \vec x(n)</math>

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

== Ableitungsfunktion ==
Die Idee hinter LMS-Filtern besteht darin, den [[Gradientenverfahren|steilsten Abstieg]] zu verwenden, um Filtergewichte <math> \hat{\mathbf{h}}(n)</math> zu finden, die eine Kostenfunktion minimieren. Wir beginnen mit der Definition der Kostenfunktion als

:<math>C(n) = E\left\{|e(n)|^{2}\right\}</math>

wobei <math>e(n)</math> die Abweichung bei der aktuellen Stichprobe <math>n</math> ist und <math>E\{\cdot\}</math> den [[Erwartungswert]] bezeichnet. Diese Kostenfunktion ist die [[mittlere quadratische Abweichung]] und wird vom LMS-Algorithmus minimiert. Die Anwendung des steilsten Abstiegs bedeutet, die [[Partielle Ableitung|partiellen Ableitungen]] in Bezug auf die einzelnen Einträge des Filterkoeffizienten-Vektors

:<math>\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\}</math>

zu nehmen, wobei <math>\nabla</math> der [[Nabla-Operator|Gradientenoperator]] ist:

:<math>\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)</math>
:<math>\nabla C(n) = -2E\left\{\mathbf{x}(n) \, e^{*}(n)\right\}</math>

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

:<math>\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\}</math>

wobei <math>\frac{\mu}{2}</math> 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 <math>{E}\left\{\mathbf{x}(n) \, e^{*}(n)\right\} </math> approximiert werden. Dies kann erfolgen mit der folgenden [[Erwartungstreue|erwartungstreuen]] [[Schätzfunktion]]

:<math>\hat{E}\left\{\mathbf{x}(n) \, e^{*}(n)\right\}=\frac{1}{N}\sum_{i=0}^{N-1}\mathbf{x}(n-i) \, e^{*}(n-i)</math>

wobei <math>N</math> die Anzahl der [[Stichprobe]]n angibt, die für diese Schätzfunktion verwendet wird.

Der einfachste Fall ist <math>N=1</math>:

:<math>\hat{E}\left\{\mathbf{x}(n) \, e^{*}(n)\right\}=\mathbf{x}(n) \, e^{*}(n)</math>

Für diesen Fall ist der Aktualisierungsalgorithmus wie folgt:

:<math>\hat{\mathbf{h}}(n+1)=\hat{\mathbf{h}}(n)+\mu \mathbf{x}(n) \, e^{*}(n)</math>

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

== Verwendung in der Neuroinformatik ==
Der LMS-Algorithmus gehört zur Gruppe der [[Überwachtes Lernen|ü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ünstliches neuronales Netz|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.

== Siehe auch ==
* [[Methode der kleinsten Quadrate]]

== Weblinks ==
* [https://neuromant.de/2018/12/16/Tutorial_Das-Perzeptron-Teil-3/#Unsere-kleine-Formelsammlung Ausführliche Herleitung der Delta-Regel für Neuronale Netze]

== Einzelnachweise ==
<references>
<ref name="widrow">{{Literatur |Autor = Bernard Widrow und Marcian Edward Hoff | Titel = Adaptive switching circuits | Verlag = IRE WESCON Convention Record, vol. 4 | Ort = Los Angeles | Seiten = 96-104 | Jahr = 1960 | Online = [https://isl.stanford.edu/~widrow/papers/c1960adaptiveswitching.pdf PDF]}}</ref>
</references>

[[Kategorie:Algorithmus|Lms-Algorithmus]]
[[Kategorie:Neuroinformatik|Lms-Algorithmus]]
[[Kategorie:Digitale Signalverarbeitung]]

LMS-Algorithmus - Versionsgeschichte

imported>Acky69: s.auch hinzu