Source:
Die lineare Regression ist einer der grundlegenden Algorithmen für viele Bereiche der Datenanalyse. Der Grund dafür liegt auf der Hand. Dabei handelt es sich um einen sehr einfachen und verständlichen Algorithmus, der seit vielen Dutzenden, wenn nicht Hunderten von Jahren zu seiner weiten Verbreitung beigetragen hat. Die Idee besteht darin, dass wir eine lineare Abhängigkeit einer Variablen von einer Menge anderer Variablen annehmen und dann versuchen, diese Abhängigkeit wiederherzustellen.
In diesem Artikel geht es jedoch nicht darum, lineare Regression zur Lösung praktischer Probleme zu verwenden. Hier betrachten wir interessante Merkmale der Implementierung verteilter Algorithmen zu ihrer Wiederherstellung, auf die wir beim Schreiben eines Moduls für maschinelles Lernen gestoßen sind . Ein wenig grundlegende Mathematik, maschinelles Lernen und verteiltes Rechnen können Ihnen dabei helfen, herauszufinden, wie Sie eine lineare Regression durchführen, selbst wenn Ihre Daten über Tausende von Knoten verteilt sind.
Worüber reden wir?
Wir stehen vor der Aufgabe, die lineare Abhängigkeit wiederherzustellen. Als Eingabedaten wird eine Menge von Vektoren vermeintlich unabhängiger Variablen angegeben, die jeweils einem bestimmten Wert der abhängigen Variablen zugeordnet sind. Diese Daten können in Form von zwei Matrizen dargestellt werden:
Da nun die Abhängigkeit angenommen wird und darüber hinaus linear ist, schreiben wir unsere Annahme in Form eines Matrizenprodukts (zur Vereinfachung der Aufzeichnung wird hier und im Folgenden davon ausgegangen, dass sich dahinter der freie Term der Gleichung verbirgt). und die letzte Spalte der Matrix enthält Einheiten):
Klingt sehr nach einem System linearer Gleichungen, nicht wahr? Es scheint, aber höchstwahrscheinlich wird es für ein solches Gleichungssystem keine Lösungen geben. Der Grund dafür ist Rauschen, das in fast allen realen Daten vorhanden ist. Ein weiterer Grund könnte das Fehlen einer linearen Abhängigkeit als solche sein, die durch die Einführung zusätzlicher Variablen, die nichtlinear von den ursprünglichen Variablen abhängen, bekämpft werden kann. Betrachten Sie das folgende Beispiel:
Source:
Dies ist ein einfaches Beispiel einer linearen Regression, das die Beziehung einer Variablen (entlang der Achse) zeigt ) von einer anderen Variablen (entlang der Achse). ). Damit das diesem Beispiel entsprechende lineare Gleichungssystem eine Lösung hat, müssen alle Punkte genau auf derselben Geraden liegen. Aber das ist nicht so. Sie liegen jedoch aufgrund von Rauschen (oder weil die Annahme einer linearen Beziehung falsch war) nicht auf derselben Geraden. Um eine lineare Beziehung aus realen Daten wiederherzustellen, ist es daher normalerweise notwendig, eine weitere Annahme einzuführen: Die Eingabedaten enthalten Rauschen, und dieses Rauschen hat . Sie können Annahmen über andere Arten der Rauschverteilung treffen, aber in den allermeisten Fällen wird die Normalverteilung berücksichtigt, auf die weiter eingegangen wird.
Maximum-Likelihood-Methode
Daher haben wir das Vorhandensein von zufälligem normalverteiltem Rauschen angenommen. Was tun in einer solchen Situation? Für diesen Fall gibt es und wird er in der Mathematik häufig verwendet . Kurz gesagt, sein Wesen liegt in der Wahl und seine anschließende Maximierung.
Wir kehren zur Wiederherstellung einer linearen Beziehung aus Daten mit normalem Rauschen zurück. Beachten Sie, dass die angenommene lineare Beziehung die mathematische Erwartung ist bestehende Normalverteilung. Gleichzeitig steigt die Wahrscheinlichkeit, dass nimmt je nach Vorhandensein von Observablen den einen oder anderen Wert an sieht so aus:
Lassen Sie uns stattdessen stattdessen ersetzen и Die Variablen, die wir brauchen, sind:
Es bleibt nur noch, den Vektor zu finden , bei dem diese Wahrscheinlichkeit maximal ist. Um eine solche Funktion zu maximieren, ist es zweckmäßig, zunächst einen Logarithmus davon zu erstellen (der Logarithmus der Funktion erreicht am selben Punkt wie die Funktion selbst ein Maximum):
Was wiederum darauf hinausläuft, die folgende Funktion zu minimieren:
Das nennt man übrigens eine Methode . Oft werden alle oben genannten Überlegungen weggelassen und einfach diese Methode verwendet.
QR-Zerlegung
Das Minimum der obigen Funktion kann ermittelt werden, indem der Punkt ermittelt wird, an dem der Gradient dieser Funktion Null ist. Und der Farbverlauf wird wie folgt geschrieben:
ist eine Matrixmethode zur Lösung des Minimierungsproblems, das in der Methode der kleinsten Quadrate verwendet wird. In diesem Zusammenhang schreiben wir die Gleichung in Matrixform um:
Also zerlegen wir die Matrix zu Matrizen и und führen Sie eine Reihe von Transformationen durch (der QR-Zerlegungsalgorithmus selbst wird hier nicht berücksichtigt, sondern nur seine Verwendung in Bezug auf die jeweilige Aufgabe):
Matrix ist orthogonal. Dadurch können wir uns die Arbeit ersparen :
Und wenn Sie ersetzen auf , dann wird es klappen . Bedenkt, dass ist eine obere Dreiecksmatrix, sie sieht so aus:
Dies kann mit der Substitutionsmethode gelöst werden. Element liegt als , vorheriges Element liegt als und so weiter.
Hierbei ist zu beachten, dass die Komplexität des resultierenden Algorithmus aufgrund der Verwendung der QR-Zerlegung gleich ist . Darüber hinaus ist es trotz der Tatsache, dass die Matrixmultiplikationsoperation gut parallelisiert ist, nicht möglich, eine effektive verteilte Version dieses Algorithmus zu schreiben.
Gradientenabstieg
Wenn man über die Minimierung einer Funktion spricht, sollte man sich immer an die Methode des (stochastischen) Gradientenabstiegs erinnern. Dies ist eine einfache und effektive Minimierungsmethode, die auf der iterativen Berechnung des Gradienten einer Funktion an einem Punkt und ihrer anschließenden Verschiebung in die entgegengesetzte Richtung zum Gradienten basiert. Jeder dieser Schritte bringt die Lösung näher an das Minimum. Der Farbverlauf sieht immer noch gleich aus:
Aufgrund der linearen Eigenschaften des Gradientenoperators ist diese Methode auch gut parallelisiert und verteilt. Beachten Sie, dass in der obigen Formel unter dem Summenzeichen unabhängige Terme stehen. Mit anderen Worten: Wir können den Gradienten für alle Indizes unabhängig berechnen vom ersten bis Berechnen Sie parallel dazu den Gradienten für Indizes mit auf . Fügen Sie dann die resultierenden Farbverläufe hinzu. Das Ergebnis der Addition ist dasselbe, als ob wir sofort den Gradienten für die Indizes vom ersten bis berechnen würden . Wenn die Daten also auf mehrere Datenteile verteilt sind, kann der Gradient für jedes Datenteil unabhängig berechnet werden, und dann können die Ergebnisse dieser Berechnungen summiert werden, um das Endergebnis zu erhalten:
Aus Umsetzungssicht passt dies zum Paradigma . Bei jedem Schritt des Gradientenabstiegs wird an jeden Datenknoten eine Aufgabe gesendet, um den Gradienten zu berechnen. Anschließend werden die berechneten Gradienten gesammelt und das Ergebnis ihrer Summe zur Verbesserung des Ergebnisses verwendet.
Trotz der einfachen Implementierung und der Möglichkeit der Ausführung im MapReduce-Paradigma hat der Gradientenabstieg auch Nachteile. Insbesondere ist die Anzahl der Schritte, die zum Erreichen der Konvergenz erforderlich sind, im Vergleich zu anderen spezialisierteren Methoden deutlich höher.
LSQR
ist eine weitere Methode zur Lösung des Problems, die sowohl zur Wiederherstellung der linearen Regression als auch zur Lösung linearer Gleichungssysteme geeignet ist. Sein Hauptmerkmal besteht darin, dass es die Vorteile von Matrixmethoden und einem iterativen Ansatz kombiniert. Implementierungen dieser Methode finden Sie in beiden Bibliotheken und in . Eine Beschreibung dieser Methode wird hier nicht gegeben (sie ist im Artikel zu finden). ). Stattdessen wird ein Ansatz demonstriert, um LSQR an die Ausführung in einer verteilten Umgebung anzupassen.
Die LSQR-Methode basiert auf . Hierbei handelt es sich um ein iteratives Verfahren, wobei jede Iteration aus den folgenden Schritten besteht:
Aber wenn wir davon ausgehen, dass die Matrix horizontal partitioniert ist, kann jede Iteration als zwei MapReduce-Schritte dargestellt werden. Auf diese Weise ist es möglich, die Datenübertragungen während jeder Iteration zu minimieren (nur Vektoren mit einer Länge gleich der Anzahl der Unbekannten):
Dieser Ansatz wird bei der Implementierung der linearen Regression verwendet .
Abschluss
Es gibt viele lineare Regressionswiederherstellungsalgorithmen, aber nicht alle können unter allen Bedingungen angewendet werden. Daher eignet sich die QR-Zerlegung hervorragend für eine genaue Lösung kleiner Datensätze. Der Gradientenabstieg ist einfach zu implementieren und ermöglicht es Ihnen, schnell eine ungefähre Lösung zu finden. Und LSQR kombiniert die besten Eigenschaften der beiden vorherigen Algorithmen, da es verteilt werden kann, im Vergleich zum Gradientenabstieg schneller konvergiert und im Gegensatz zur QR-Zerlegung auch ein frühzeitiges Stoppen des Algorithmus ermöglicht, um eine Näherungslösung zu finden.
Source: habr.com