RLS-Algorithmus
Der RLS-Algorithmus (Recursive-Least-Squares-Algorithmus) basiert auf der Methode der kleinsten Quadrate. Er wird zur Lösung überbestimmter linearer Gleichungssysteme und insbesondere zur Schätzung von Modellparametern bei der Identifikation linearer Systeme oder in der Neuroinformatik genutzt. Die Rekursivität erlaubt die Online-Nutzung mit aktuell anfallenden Daten bei gleichbleibender Komplexität in jedem Rekursionsschritt.
Der RLS-Algorithmus (Recursive-Least-Squares-Algorithmus) basiert auf der Methode der kleinsten Quadrate. Er wird zur Lösung überbestimmter linearer Gleichungssysteme und insbesondere zur Schätzung von Modellparametern bei der Identifikation linearer Systeme oder in der Neuroinformatik genutzt. Die Rekursivität erlaubt die Online-Nutzung mit aktuell anfallenden Daten bei gleichbleibender Komplexität in jedem Rekursionsschritt.
Herleitung
[Bearbeiten | Quelltext bearbeiten]Die Basis für den rekursiven Algorithmus ist zunächst das formale quadratische Minimierungsproblem. Im Beispiel der Systemidentifikation liegen Paare aus Ein- und Ausgangsdaten in der Matrix
X
{\displaystyle \mathbf {X} }
-
y
_
=
X
⋅
Θ
^
_
{\displaystyle {\underline {y}}=\mathbf {X} \cdot {\underline {\hat {\Theta }}}}
Das entsprechende Optimierungsproblem formuliert sich zu:
-
min
Θ
^
_
f
(
Θ
^
_
)
=
min
Θ
^
_
1
2
|
|
y
_
−
X
⋅
Θ
^
_
|
|
2
=
min
Θ
^
_
[
1
2
(
y
_
−
X
⋅
Θ
^
_
)
T
(
y
_
−
X
⋅
Θ
^
_
)
]
{\displaystyle {\underset {\underline {\hat {\Theta }}}{\min }}f({\underline {\hat {\Theta }}})={\underset {\underline {\hat {\Theta }}}{\min }}{\frac {1}{2}}||{\underline {y}}-\mathbf {X} \cdot {\underline {\hat {\Theta }}}||^{2}={\underset {\underline {\hat {\Theta }}}{\min }}\left[{\frac {1}{2}}\left({\underline {y}}-\mathbf {X} \cdot {\underline {\hat {\Theta }}}\right)^{T}\left({\underline {y}}-\mathbf {X} \cdot {\underline {\hat {\Theta }}}\right)\right]}
![{\displaystyle {\underset {\underline {\hat {\Theta }}}{\min }}f({\underline {\hat {\Theta }}})={\underset {\underline {\hat {\Theta }}}{\min }}{\frac {1}{2}}||{\underline {y}}-\mathbf {X} \cdot {\underline {\hat {\Theta }}}||^{2}={\underset {\underline {\hat {\Theta }}}{\min }}\left[{\frac {1}{2}}\left({\underline {y}}-\mathbf {X} \cdot {\underline {\hat {\Theta }}}\right)^{T}\left({\underline {y}}-\mathbf {X} \cdot {\underline {\hat {\Theta }}}\right)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5437f28f9ce38e0cbf36fe879dc5507f0077fc3)
Es soll das Quadrat der Differenz aus Mess- und Modelldaten minimiert werden. Dieses Vorgehen hat den Vorteil, dass eine quadratische Funktion genau ein globales Extremum in ihrem Scheitelpunkt besitzt. An dieser Stelle wird die erste Ableitung zu Null, was zur Lösung des Minimierungsproblems führt:
-
∂
f
(
Θ
^
_
)
∂
Θ
^
_
=
−
X
T
⋅
(
y
_
−
X
⋅
Θ
^
_
)
=
!
0
{\displaystyle {\frac {\partial f({\underline {\hat {\Theta }}})}{\partial {\underline {\hat {\Theta }}}}}=-\mathbf {X} ^{T}\cdot \left({\underline {y}}-\mathbf {X} \cdot {\underline {\hat {\Theta }}}\right){\overset {!}{=}}0}
Umstellen liefert den gesuchten Parametervektor:
-
Θ
^
_
=
(
X
T
⋅
X
)
−
1
⋅
X
T
⋅
y
_
{\displaystyle {\underline {\hat {\Theta }}}=\left(\mathbf {X} ^{T}\cdot \mathbf {X} \right)^{-1}\cdot \mathbf {X} ^{T}\cdot {\underline {y}}}
Zur Lösung muss die Anzahl der Datenpaare mindestens der Anzahl der gesuchten Parameter entsprechen. Je mehr Datenpaare vorliegen, desto mehr Einträge hat die Matrix
X
{\displaystyle \mathbf {X} }
Rekursion
[Bearbeiten | Quelltext bearbeiten]Beim Übergang zur rekursiven Berechnung bleibt auch bei Hinzukommen neuer Daten in jedem Schritt der Rechenaufwand gleich, da das vorherige Ergebnis als Ausgangspunkt genutzt wird und so nur je ein neues Datenpaar in die Kalkulation involviert ist.
Im Rekursionsschritt
k
{\displaystyle k}
-
y
_
(
k
)
=
X
(
k
)
⋅
Θ
^
_
(
k
)
{\displaystyle {\underline {y}}(k)=\mathbf {X} (k)\cdot {\underline {\hat {\Theta }}}(k)}
mit der zugehörigen Lösung für den Parametervektor
Θ
^
_
(
k
)
{\displaystyle {\underline {\hat {\Theta }}}(k)}
-
Θ
^
_
(
k
)
=
(
X
T
(
k
)
⋅
X
(
k
)
)
−
1
⋅
X
T
(
k
)
⋅
y
_
(
k
)
{\displaystyle {\underline {\hat {\Theta }}}(k)=\left(\mathbf {X} ^{T}(k)\cdot \mathbf {X} (k)\right)^{-1}\cdot \mathbf {X} ^{T}(k)\cdot {\underline {y}}(k)}
Für
k
+
1
{\displaystyle k+1}
-
y
_
(
k
+
1
)
=
X
(
k
+
1
)
⋅
Θ
^
_
(
k
+
1
)
{\displaystyle {\underline {y}}(k+1)=\mathbf {X} (k+1)\cdot {\underline {\hat {\Theta }}}(k+1)}
und für die Lösung gilt entsprechend:
-
Θ
^
_
(
k
+
1
)
=
(
X
T
(
k
+
1
)
⋅
X
(
k
+
1
)
)
−
1
⋅
X
T
(
k
+
1
)
⋅
y
(
k
+
1
)
{\displaystyle {\underline {\hat {\Theta }}}(k+1)=\left(\mathbf {X} ^{T}(k+1)\cdot \mathbf {X} (k+1)\right)^{-1}\cdot \mathbf {X} ^{T}(k+1)\cdot y(k+1)}
Die Daten im Schritt
k
+
1
{\displaystyle k+1}
-
y
_
(
k
+
1
)
=
[
y
_
(
k
)
y
(
k
+
1
)
]
,
X
(
k
+
1
)
=
[
X
(
k
)
x
_
T
(
k
+
1
)
]
{\displaystyle {\underline {y}}(k+1)={\begin{bmatrix}{\underline {y}}(k)\\y(k+1)\end{bmatrix}},\qquad \mathbf {X} (k+1)={\begin{bmatrix}\mathbf {X} (k)\\{\underline {x}}^{T}(k+1)\end{bmatrix}}}
Einsetzen in die Gleichung für den Parametervektor liefert:
-
Θ
^
_
(
k
+
1
)
=
(
[
X
T
(
k
)
x
_
(
k
+
1
)
]
⋅
[
X
(
k
)
x
_
T
(
k
+
1
)
]
)
−
1
⋅
[
X
T
(
k
)
x
_
(
k
+
1
)
]
⋅
[
y
_
(
k
)
y
(
k
+
1
)
]
{\displaystyle {\underline {\hat {\Theta }}}(k+1)=\left({\begin{bmatrix}\mathbf {X} ^{T}(k)&{\underline {x}}(k+1)\end{bmatrix}}\cdot {\begin{bmatrix}\mathbf {X} (k)\\{\underline {x}}^{T}(k+1)\end{bmatrix}}\right)^{-1}\cdot {\begin{bmatrix}\mathbf {X} ^{T}(k)&{\underline {x}}(k+1)\end{bmatrix}}\cdot {\begin{bmatrix}{\underline {y}}(k)\\y(k+1)\end{bmatrix}}}
Der Ausdruck lässt sich noch weiter ordnen zu:
-
Θ
^
_
(
k
+
1
)
=
(
X
T
(
k
)
⋅
X
(
k
)
+
x
_
(
k
+
1
)
⋅
x
_
T
(
k
+
1
)
)
−
1
⋅
(
X
T
(
k
)
⋅
X
(
k
)
⋅
Θ
^
_
(
k
)
+
x
_
(
k
+
1
)
⋅
y
(
k
+
1
)
)
{\displaystyle {\underline {\hat {\Theta }}}(k+1)=\left(\mathbf {X} ^{T}(k)\cdot \mathbf {X} (k)+{\underline {x}}(k+1)\cdot {\underline {x}}^{T}(k+1)\right)^{-1}\cdot \left(\mathbf {X} ^{T}(k)\cdot \mathbf {X} (k)\cdot {\underline {\hat {\Theta }}}(k)+{\underline {x}}(k+1)\cdot y(k+1)\right)}
Mit der Abkürzung
P
−
1
=
X
T
(
k
)
⋅
X
(
k
)
{\displaystyle \mathbf {P} ^{-1}=\mathbf {X} ^{T}(k)\cdot \mathbf {X} (k)}
-
Θ
^
_
(
k
+
1
)
=
(
P
(
k
)
−
P
(
k
)
⋅
x
_
(
k
+
1
)
⋅
x
_
T
(
k
+
1
)
⋅
P
(
k
)
1
+
x
_
T
(
k
+
1
)
⋅
P
(
k
)
⋅
x
_
(
k
+
1
)
)
⋅
(
P
−
1
(
k
)
⋅
Θ
^
_
(
k
)
+
x
_
(
k
+
1
)
⋅
y
(
k
+
1
)
)
{\displaystyle {\underline {\hat {\Theta }}}(k+1)=\left(\mathbf {P} (k)-{\frac {\mathbf {P} (k)\cdot {\underline {x}}(k+1)\cdot {\underline {x}}^{T}(k+1)\cdot \mathbf {P} (k)}{1+{\underline {x}}^{T}(k+1)\cdot \mathbf {P} (k)\cdot {\underline {x}}(k+1)}}\right)\cdot \left(\mathbf {P} ^{-1}(k)\cdot {\underline {\hat {\Theta }}}(k)+{\underline {x}}(k+1)\cdot y(k+1)\right)}
Vereinfacht:
-
Θ
^
_
(
k
+
1
)
=
Θ
^
_
(
k
)
+
P
(
k
)
⋅
x
_
(
k
+
1
)
1
+
x
_
T
(
k
+
1
)
⋅
P
(
k
)
⋅
x
_
(
k
+
1
)
⏟
Verstärkungsterm
γ
_
(
k
)
⋅
(
y
(
k
+
1
)
−
x
_
T
(
k
+
1
)
⋅
Θ
^
_
(
k
)
)
⏟
Korrekturterm
{\displaystyle {\underline {\hat {\Theta }}}(k+1)={\underline {\hat {\Theta }}}(k)+\underbrace {\frac {\mathbf {P} (k)\cdot {\underline {x}}(k+1)}{1+{\underline {x}}^{T}(k+1)\cdot \mathbf {P} (k)\cdot {\underline {x}}(k+1)}} _{{\text{Verstärkungsterm }}{\underline {\gamma }}(k)}\cdot \underbrace {\left(y(k+1)-{\underline {x}}^{T}(k+1)\cdot {\underline {\hat {\Theta }}}(k)\right)} _{\text{Korrekturterm}}}
Die Aktualisierung der Matrix
P
{\displaystyle \mathbf {P} }
-
P
(
k
+
1
)
=
P
(
k
)
−
γ
_
(
k
)
⋅
x
_
T
(
k
+
1
)
⋅
P
(
k
)
{\displaystyle \mathbf {P} (k+1)=\mathbf {P} (k)-{\underline {\gamma }}(k)\cdot {\underline {x}}^{T}(k+1)\cdot \mathbf {P} (k)}
Im Vergleich zum nichtrekursiven Algorithmus ist ersichtlich, dass keine Inversion der Matrix
(
X
T
⋅
X
)
{\displaystyle \left(\mathbf {X} ^{T}\cdot \mathbf {X} \right)}
Vergessensfaktor
[Bearbeiten | Quelltext bearbeiten]Durch die Einführung eines Vergessensfaktors
λ
<
1
{\displaystyle \lambda <1}
-
Θ
^
_
(
k
+
1
)
=
Θ
^
_
(
k
)
+
P
(
k
)
⋅
x
_
(
k
+
1
)
λ
+
x
_
T
(
k
+
1
)
⋅
P
(
k
)
⋅
x
_
(
k
+
1
)
⏟
Verstärkungsterm
γ
_
(
k
)
⋅
(
y
(
k
+
1
)
−
x
_
T
(
k
+
1
)
⋅
Θ
^
_
(
k
)
)
⏟
Korrekturterm
{\displaystyle {\underline {\hat {\Theta }}}(k+1)={\underline {\hat {\Theta }}}(k)+\underbrace {\frac {\mathbf {P} (k)\cdot {\underline {x}}(k+1)}{\lambda +{\underline {x}}^{T}(k+1)\cdot \mathbf {P} (k)\cdot {\underline {x}}(k+1)}} _{{\text{Verstärkungsterm }}{\underline {\gamma }}(k)}\cdot \underbrace {\left(y(k+1)-{\underline {x}}^{T}(k+1)\cdot {\underline {\hat {\Theta }}}(k)\right)} _{\text{Korrekturterm}}}
-
P
(
k
+
1
)
=
1
λ
⋅
(
P
(
k
)
−
γ
_
(
k
)
⋅
x
_
T
(
k
+
1
)
⋅
P
(
k
)
)
{\displaystyle \mathbf {P} (k+1)={\frac {1}{\lambda }}\cdot \left(\mathbf {P} (k)-{\underline {\gamma }}(k)\cdot {\underline {x}}^{T}(k+1)\cdot \mathbf {P} (k)\right)}
Anwendung
[Bearbeiten | Quelltext bearbeiten]Der RLS-Algorithmus benötigt für ein gutes Ergebnis maximal so viele Rekursionsschritte wie Parameter identifiziert werden sollen. Diese Schnelligkeit und seine einfache Berechenbarkeit ermöglichen vielfältige Online-Anwendungsmöglichkeiten zur Systemidentifikation oder als adaptives Filter auch auf weniger potenten Mikroprozessorsystemen. Zu Beginn der Rekursion müssen sowohl
Θ
^
_
{\displaystyle {\underline {\hat {\Theta }}}}
Damit das Verfahren stabil bleibt, muss die Matrix
P
{\displaystyle \mathbf {P} }
Beispiel
[Bearbeiten | Quelltext bearbeiten]Für ein zu identifizierendes System wurde ein PT2-System als Modellfunktion gewählt, dessen zeitdiskrete Realisierung in Form der folgenden Rekursionsgleichung vorliegt:
-
y
^
(
k
)
=
−
a
1
⋅
y
^
(
k
−
1
)
−
a
2
⋅
y
^
(
k
−
2
)
+
a
3
⋅
u
(
k
−
1
)
+
a
4
⋅
u
(
k
−
2
)
{\displaystyle {\hat {y}}(k)=-a_{1}\cdot {\hat {y}}(k-1)-a_{2}\cdot {\hat {y}}(k-2)+a_{3}\cdot u(k-1)+a_{4}\cdot u(k-2)}
Mit der Zusammenfassung von Modellein- und -ausgang zu
h
_
T
=
[
−
y
^
(
k
−
1
)
−
y
^
(
k
−
2
)
u
(
k
−
1
)
u
(
k
−
2
)
]
{\displaystyle {\underline {h}}^{T}={\begin{bmatrix}-{\hat {y}}(k-1)&-{\hat {y}}(k-2)&u(k-1)&u(k-2)\end{bmatrix}}}
-
y
^
(
k
)
=
h
_
T
⋅
Θ
^
_
{\displaystyle {\hat {y}}(k)={\underline {h}}^{T}\cdot {\underline {\hat {\Theta }}}}
Für den gewählten Modellansatz ergibt sich nun folgende Realisierung des RLS-Algorithmus:
-
Θ
^
_
(
k
+
1
)
=
Θ
^
_
(
k
)
+
P
(
k
)
⋅
h
_
(
k
+
1
)
λ
+
h
_
T
(
k
+
1
)
⋅
P
(
k
)
⋅
h
_
(
k
+
1
)
⋅
(
y
(
k
+
1
)
−
h
_
T
(
k
+
1
)
⋅
Θ
^
_
(
k
)
)
{\displaystyle {\underline {\hat {\Theta }}}(k+1)={\underline {\hat {\Theta }}}(k)+{\frac {\mathbf {P} (k)\cdot {\underline {h}}(k+1)}{\lambda +{\underline {h}}^{T}(k+1)\cdot \mathbf {P} (k)\cdot {\underline {h}}(k+1)}}\cdot \left(y(k+1)-{\underline {h}}^{T}(k+1)\cdot {\underline {\hat {\Theta }}}(k)\right)}
-
P
(
k
+
1
)
=
1
λ
⋅
(
P
(
k
)
−
γ
_
(
k
)
⋅
h
_
T
(
k
+
1
)
⋅
P
(
k
)
)
{\displaystyle \mathbf {P} (k+1)={\frac {1}{\lambda }}\cdot \left(\mathbf {P} (k)-{\underline {\gamma }}(k)\cdot {\underline {h}}^{T}(k+1)\cdot \mathbf {P} (k)\right)}
Literatur
[Bearbeiten | Quelltext bearbeiten]- Dierk Schröder: Intelligente Verfahren. Springer-Verlag, Berlin, Heidelberg 2010, ISBN 978-3-642-11397-0.
- Martin Werner: Digitale Signalverarbeitung mit MATLAB®-Praktikum. Vieweg & Sohn Verlag, Wiesbaden 2008, ISBN 978-3-8348-0393-1.