Lineare Regression und Methoden ihrer Wiederherstellung.

Quelle: xkcd

Die lineare Regression ist einer der grundlegenden Algorithmen für viele Bereiche der Datenanalyse. Der Grund dafür ist offensichtlich. Es handelt sich um einen sehr einfachen und verständlichen Algorithmus, der seit vielen Jahrzehnten, wenn nicht Jahrhunderten, weit verbreitet ist. Die Idee besteht darin, eine lineare Abhängigkeit einer Variablen von einer Reihe anderer Variablen anzunehmen und dann zu versuchen, diese Abhängigkeit zu rekonstruieren.

In diesem Artikel geht es jedoch nicht um die Anwendung der linearen Regression zur Lösung praktischer Aufgaben. Wir werden interessante Aspekte der Implementierung verteilter Algorithmen zu ihrer Rekonstruktion betrachten, mit denen wir während der Entwicklung des Machine-Learning-Moduls in Apache Ignite. Ein wenig Grundlagenwissen in Mathematik, den Grundprinzipien des maschinellen Lernens und der verteilten Berechnungen wird helfen, zu verstehen, wie man die lineare Regression rekonstruieren kann, selbst wenn die Daten auf Tausenden von Knoten verteilt sind.

Worum geht es?

Unser Ziel ist es, eine lineare Abhängigkeit wiederherzustellen. Als Eingabedaten wird eine Menge von Vektoren bereitgestellt, von denen angenommen wird, dass sie unabhängige Variablen darstellen, und jeder dieser Vektoren ist mit einem bestimmten Wert einer abhängigen Variablen verknüpft. Diese Daten können in Form von zwei Matrizen dargestellt werden:

Da eine Abhängigkeit angenommen wird, und zwar eine lineare, drücken wir unsere Annahme in Form des Produkts von Matrizen aus (zur Vereinfachung wird hier und im Folgenden angenommen, dass der freie Term der Gleichung verborgen ist hinter , und die letzte Spalte der Matrix enthält Einsen):

Das sieht sehr nach einem System linearer Gleichungen aus, nicht wahr? Es scheint so, aber wahrscheinlich hat ein solches Gleichungssystem keine Lösungen. Der Grund dafür ist das Rauschen, das in nahezu allen realen Daten vorhanden ist. Ein weiterer Grund kann das Fehlen einer linearen Abhängigkeit an sich sein, gegen die man versuchen könnte, durch Einführung zusätzlicher Variablen vorzugehen, die nichtlinear von den ursprünglichen abhängen. Betrachten wir folgendes Beispiel:

Quelle: Wikipedia

Dies ist ein einfaches Beispiel für lineare Regression, das die Abhängigkeit einer Variablen (auf der Achse ) von einer anderen Variablen (entlang der Achse ). Damit das entsprechende System linearer Gleichungen eine Lösung hat, müssen alle Punkte genau auf einer Linie liegen. Das ist jedoch nicht der Fall. Und sie liegen nicht auf einer Linie genau wegen des Rauschens (oder weil die Annahme einer linearen Abhängigkeit fehlerhaft war). Daher ist es üblich, eine weitere Annahme einzuführen, um die lineare Abhängigkeit aus realen Daten wiederherzustellen: Die Eingabedaten enthalten Rauschen, und dieses Rauschen hat eine normale Verteilung. Man kann auch Annahmen über andere Arten von Rauschverteilungen treffen, aber in der überwiegenden Mehrheit der Fälle wird tatsächlich die normale Verteilung betrachtet, über die hier weiter gesprochen wird.

Das Maximum-Likelihood-Verfahren

Also haben wir das Vorhandensein von zufälligem, normalverteiltem Rauschen angenommen. Wie gehen wir in einer solchen Situation damit um? In der Mathematik gibt es hierfür ein Konzept, das weit verbreitet ist das Maximum-Likelihood-Verfahren. Kurz gesagt, es geht darum, der Likelihood-Funktion. und diese dann zu maximieren.

Kehren wir zurück zur Wiederherstellung der linearen Abhängigkeit aus Daten mit normalem Rauschen. Beachten Sie, dass die angenommene lineare Abhängigkeit das mathematische Erwartungswert darstellt. eine normale Verteilung. Gleichzeitig ist die Wahrscheinlichkeit, dass einen bestimmten Wert annimmt, unter der Annahme, dass beobachtbare , folgendermaßen aus:

Nun setzen wir anstelle von und die benötigten Variablen ein:

Es bleibt nur der Vektor zu finden , bei dem diese Wahrscheinlichkeit maximal ist. Um eine solche Funktion zu maximieren, ist es sinnvoll, sie zunächst zu logarithmieren (der Logarithmus der Funktion erreicht sein Maximum an demselben Punkt wie die Funktion selbst):

Was wiederum darauf hinausläuft, die folgende Funktion zu minimieren:

Übrigens nennt man dies die Methode der kleinsten Quadrate.Oft werden alle oben genannten Überlegungen weggelassen und einfach diese Methode verwendet.

QR-Zerlegung

Das Minimum der oben genannten Funktion kann gefunden werden, wenn der Punkt gefunden wird, an dem der Gradient dieser Funktion gleich null ist. Der Gradient wird folgendermaßen dargestellt:

QR-Zerlegung ist ein matrixbasierter Ansatz zur Lösung von Minimierungsproblemen, der in der Methode der kleinsten Quadrate verwendet wird. Daher schreiben wir die Gleichung in Matrixform um:

Also zerlegen wir die Matrix in Matrizen und und führen eine Reihe von Transformationen durch (der Algorithmus der QR-Zerlegung wird hier nicht behandelt, nur seine Anwendung auf die gegebene Aufgabe):

Die Matrix ist orthogonale. Dies ermöglicht es uns, das Produkt zu eliminieren :

Und wenn wir findet man ersetzen, dann erhalten wir . Da eine obere Dreiecksmatrix ist, sieht das folgendermaßen aus:

Dies kann mit der Substitutionsmethode gelöst werden. Das Element liegt vor als , das vorherige Element liegt vor als usw.

Hier sei darauf hingewiesen, dass die Komplexität des resultierenden Algorithmus aufgrund der Verwendung der QR-Zerlegung gleich ist . Dabei ist es, obwohl die Matrixmultiplikation gut parallelisiert werden kann, nicht möglich, eine effiziente verteilte Version dieses Algorithmus zu schreiben.

Gradientenabstieg

Wenn es um die Minimierung einer bestimmten Funktion geht, sollte man immer die Methode des (stochastischen) Gradientenabstiegs im Hinterkopf behalten. Dies ist eine einfache und effektive Minimierungsmethode, die auf der iterativen Berechnung des Gradienten der Funktion an einem Punkt basiert und anschließend eine Verschiebung in die entgegengesetzte Richtung des Gradienten vornimmt. Jeder solche Schritt bringt die Lösung dem Minimum näher. Der Gradient sieht dabei weiterhin so aus:

Diese Methode lässt sich gut parallelisieren und verteilt dank der linearen Eigenschaften des Gradientoperators. Es ist zu beachten, dass in der oben genannten Formel unter dem Summenzeichen unabhängige Summanden stehen. Mit anderen Worten, wir können den Gradient unabhängig für alle Indizes berechnen. von eins bis , gleichzeitig den Gradienten für die Indizes von bis zu zu berechnen. Anschließend werden die berechneten Gradienten addiert. Das Ergebnis der Addition ist dasselbe, als hätten wir den Gradienten direkt für die Indizes von eins bis berechnet. Somit kann, wenn die Daten auf mehrere Teile verteilt sind, der Gradient unabhängig für jeden Teil berechnet und die Ergebnisse dieser Berechnungen zur Erzielung des endgültigen Ergebnisses summiert werden:

Aus der Sicht der Implementierung passt dies in das Paradigma MapReduce. Bei jedem Schritt des Gradientenabstiegs wird jedem Datenknoten ein Auftrag zur Berechnung des Gradienten zugewiesen, dann werden die berechneten Gradienten zusammengeführt, und das Ergebnis ihrer Summierung wird zur Verbesserung des Ergebnisses verwendet.

Trotz der Einfachheit der Implementierung und der Möglichkeit, im MapReduce-Paradigma ausgeführt zu werden, hat der Gradientabstieg auch seine Nachteile. Insbesondere ist die Anzahl der Schritte, die zur Erreichung der Konvergenz erforderlich sind, im Vergleich zu anderen, spezialisierteren Methoden erheblich höher.

LSQR

LSQR ist ein weiterer Ansatz zur Lösung des Problems, der sowohl zur Wiederherstellung linearer Regressionen als auch zur Lösung von Systemen linearer Gleichungen geeignet ist. Sein Hauptmerkmal ist, dass es die Vorteile von Matrixmethoden und iterativen Ansätzen vereint. Implementierungen dieser Methode sind in Bibliotheken zu finden SciPyals auch in MATLAB. Eine Beschreibung dieser Methode wird hier nicht gegeben (sie kann in dem Artikel gefunden werden LSQR: An algorithm for sparse linear equations and sparse least squares). Stattdessen wird ein Ansatz demonstriert, der es ermöglicht, LSQR für den Einsatz in einer verteilten Umgebung anzupassen.

Die Grundlage der LSQR-Methode ist die bidiagonalization. Dies ist ein iterativer Prozess, wobei jede Iteration aus den folgenden Schritten besteht:


Doch wenn man davon ausgeht, dass die Matrix Wenn die Daten horizontal partitioniert sind, kann jede Iteration in zwei Schritte von MapReduce unterteilt werden. Dadurch wird die Datenübertragung während jeder Iteration minimiert (nur Vektoren mit einer Länge, die der Anzahl der Unbekannten entspricht):

Dieser Ansatz wird bei der Implementierung der linearen Regression in Apache Ignite ML.

Fazit

Es gibt viele Algorithmen zur Wiederherstellung der linearen Regression, aber nicht alle können unter allen Bedingungen angewendet werden. Das QR-Zerlegungsverfahren eignet sich hervorragend für die genaue Lösung bei kleinen Datensätzen. Der Gradientenabstieg lässt sich einfach umsetzen und ermöglicht eine schnelle Annäherung an die Lösung. LSQR kombiniert die besten Eigenschaften der beiden vorherigen Algorithmen, da er verteilbar ist, schneller konvergiert als der Gradientenabstieg und im Gegensatz zur QR-Zerlegung eine vorzeitige Beendigung des Algorithmus zur Suche nach einer Approximationslösung zulässt.

Quelle: habr.com