Ein adaptiver Algorithmus ist ein Algorithmus , der sein Verhalten während seiner Ausführung [ 1 ] basierend auf verfügbaren Informationen und einem vorab definierten Belohnungsmechanismus (oder -kriterium) ändert. Diese Informationen können beispielsweise kürzlich empfangene Daten, Informationen über die verfügbaren Rechenressourcen oder andere zur Laufzeit gewonnene (oder vorab bekannte) Informationen über die Umgebung, in der der Algorithmus arbeitet, sein.

Zu den am häufigsten verwendeten adaptiven Algorithmen zählt der Widrow-Hoff-Algorithmus der kleinsten mittleren Quadrate (LMS) . Er repräsentiert eine Klasse stochastischer Gradientenabstiegsalgorithmen, die in der adaptiven Filterung und im maschinellen Lernen eingesetzt werden. In der adaptiven Filterung dient der LMS dazu, einen gewünschten Filter zu simulieren, indem er die Filterkoeffizienten findet, die die kleinste mittlere quadratische Abweichung des Fehlersignals (Differenz zwischen gewünschtem und tatsächlichem Signal) erzeugen.

Beispielsweise hat die stabile Partitionierung ohne zusätzlichen Speicher eine Laufzeit von O ( n log n ), kann aber mit O ( n ) Speicher auf O ( n ) reduziert werden. Die in der C++-Standardbibliothek implementierte Partitionierung stable_partitionist adaptiv und reserviert daher so viel Speicher wie möglich (maximal den benötigten) und wendet den Algorithmus mit diesem verfügbaren Speicher an. Ein weiteres Beispiel ist die adaptive Sortierung , deren Verhalten sich nach der Vorsortierung der Eingabedaten richtet.

Ein Beispiel für einen adaptiven Algorithmus in Radarsystemen ist der CFAR-Detektor ( Constant False Alarm Rate ).

Im maschinellen Lernen und in der Optimierung sind viele Algorithmen adaptiv oder verfügen über adaptive Varianten. Dies bedeutet in der Regel, dass die Algorithmusparameter, wie beispielsweise die Lernrate, automatisch anhand von Statistiken über die bisherige Optimierung (z. B. der Konvergenzrate ) angepasst werden. [ 2 ] Beispiele hierfür sind adaptives Simulated Annealing , adaptiver Koordinatenabstieg , adaptive Quadratur , AdaBoost , Adagrad , Adadelta, RMSprop und Adam . [ 3 ]

Bei der Datenkomprimierung können adaptive Codierungsalgorithmen wie die adaptive Huffman-Codierung oder die Vorhersage durch partielles Abgleich einen Datenstrom als Eingabe nehmen und ihre Komprimierungstechnik auf der Grundlage der bereits erfassten Symbole anpassen. [ 4 ]

In der Signalverarbeitung wird der in MiniDisc- Recordern verwendete Adaptive Transform Acoustic Coding (ATRAC)-Codec als „adaptiv“ bezeichnet, weil sich die Fensterlänge (die Größe eines Audio-„Chunks“) je nach Art des zu komprimierenden Klangs ändern kann, um die bestmögliche Kompressionsstrategie zu erreichen.

Siehe auch

Referenzen

  1. ^ Anthony Zaknich (25. April 2005). Prinzipien adaptiver Filter und selbstlernender Systeme . Springer Science & Business Media. ISBN 978-1-85233-984-5Die
  2. ^ Goodfellow, Ian ; Bengio, Yoshua ; Courville, Aaron (2016). Deep Learning . MIT Press. ISBN 978-0-26203561-3Die
  3. ^ Murphy, Kevin (2021). Probabilistic Machine Learning: An Introduction . MIT Press . Abgerufen am 10. April 2021 .{{cite book}}: |website=ignoriert ( Hilfe )
  4. ^ Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9. April 2014). Grundlagen der Multimedia . Springer Science & Business Media. ISBN 978-3-319-05290-8Die