Effiziente lineare Online-Regression

53

Ich analysiere einige Daten, bei denen ich eine normale lineare Regression durchführen möchte. Dies ist jedoch nicht möglich, da ich es mit einer Online-Einstellung mit einem kontinuierlichen Strom von Eingabedaten zu tun habe (die schnell zu groß für Speicher werden) und benötigt um Parameterschätzungen zu aktualisieren, während diese verbraucht werden. Das heißt, ich kann nicht einfach alles in den Speicher laden und eine lineare Regression für den gesamten Datensatz durchführen.

Ich gehe von einem einfachen linearen multivariaten Regressionsmodell aus

y = A x + b + e

$\mathbf y = \mathbf A\mathbf x + \mathbf b + \mathbf e$

Welcher Algorithmus eignet sich am besten, um eine kontinuierlich aktualisierte Schätzung der linearen Regressionsparameter und zu erstellen ? $\mathbf A$ $\mathbf b$

Im Idealfall:

Ich hätte gerne einen Algorithmus, der die meiste Raum- und Zeitkomplexität pro Aktualisierung aufweist, wobei die Dimensionalität der unabhängigen Variablen ( ) und die Dimensionalität der abhängigen Variablen ( ). $\mathcal O(N\cdot M)$ $N$ $\mathbf x$ $M$ $\mathbf y$
Ich möchte in der Lage sein, einige Parameter anzugeben, um zu bestimmen, wie stark die Parameter von jeder neuen Stichprobe aktualisiert werden, z. B. würde 0,000001 bedeuten, dass die nächste Stichprobe ein Millionstel der Parameterschätzung liefern würde. Dies würde eine Art exponentiellen Zerfalls für die Wirkung von Proben in der fernen Vergangenheit ergeben.

time-series regression algorithms real-time mikera
quelle

2

Nachschlagen (1) Flexible lineare Regression, (2) Kalman-Filter.

Jase

31

Maindonald beschreibt eine sequentielle Methode, die auf Givens Rotationen basiert . (A Givens - Rotation ist eine orthogonale Transformation der zwei Vektoren , die in einer der Vektoren einen gegebenen Eintritts Nullen.) Bei dem vorherigen Schritt die zerlegt haben Designmatrix in eine Dreiecksmatrix über eine orthogonale Transformation so dass . (Es ist schnell und einfach, die Regressionsergebnisse aus einer Dreiecksmatrix zu erhalten.) Wenn Sie an eine neue Zeile unterhalb von angrenzen , erweitern Sie effektiv um eine Zeile ungleich Null Sagen Sie auch $\mathbf{X}$ $\mathbf{T}$ $\mathbf{Q}$ $\mathbf{Q}\mathbf{X} = (\mathbf{T}, \mathbf{0})'$ $v$ $\mathbf{X}$ $(\mathbf{T}, \mathbf{0})'$ $t$ . Die Aufgabe besteht darin, diese Zeile auf Null zu setzen, während die Einträge in der Position von diagonal bleiben. Eine Folge von Givens-Rotationen führt dies aus: Die Rotation mit der ersten Zeile von das erste Element von auf ; dann setzt die Drehung mit der zweiten Zeile von das zweite Element auf Null und so weiter. Der Effekt ist, dass durch eine Reihe von Rotationen vormultipliziert wird , was seine Orthogonalität nicht ändert. $\mathbf{T}$ $\mathbf{T}$ $t$ $\mathbf{T}$ $\mathbf{Q}$

Wenn die Entwurfsmatrix Spalten enthält (was bei der Regression von Variablen plus einer Konstanten der Fall ist ), überschreitet die Anzahl der erforderlichen Umdrehungen nicht und jede Umdrehung ändert zwei -Vektoren. Der für benötigte Speicher ist . Somit hat dieser Algorithmus sowohl zeitlich als auch räumlich einen Rechenaufwand von . $p+1$ $p$ $p+1$ $p+1$ $\mathbf{T}$ $O((p+1)^2)$ $O((p+1)^2)$

Mit einem ähnlichen Ansatz können Sie die Auswirkung des Löschens einer Zeile auf die Regression bestimmen. Maindonald gibt Formeln; so tun Belsley, Kuh & Welsh . Wenn Sie also nach einem sich bewegenden Fenster für die Regression suchen, können Sie die Daten für das Fenster in einem Ringpuffer speichern, der an das neue Datum angrenzt, und bei jeder Aktualisierung das alte löschen. Dies verdoppelt die Aktualisierungszeit und erfordert zusätzlichen Speicher für ein Fenster mit der Breite . Es scheint, dass das Analogon des Einflussparameters wäre. $O(k (p+1))$ $k$ $1/k$

Für den exponentiellen Zerfall denke ich (spekulativ), dass Sie diesen Ansatz an gewichtete kleinste Quadrate anpassen könnten, indem Sie jedem neuen Wert eine Gewichtung größer als 1 zuweisen. Es sollte nicht erforderlich sein, einen Puffer mit vorherigen Werten zu pflegen oder alte Daten zu löschen.

Verweise

JH Maindonald, Statistische Berechnung. J. Wiley & Sons, 1984. Kapitel 4.

DA Belsley, E. Kuh, RE Welsch, Regressionsdiagnostik: Identifizierung von Einflussdaten und Quellen der Kollinearität. J. Wiley & amp; Söhne, 1980.

whuber
quelle

1

Ist die von Maindonald beschriebene Methode mit dem Gentleman-Algorithmus verwandt oder identisch? jstor.org/stable/2347147

onestop

6

In diesem Fall siehe auch die Erweiterungen von Alan Miller jstor.org/stable/2347583 . Ein Archiv seiner Fortran-Software-Site befindet sich jetzt unter jblevins.org/mirror/amiller

onestop

5

Ein expliziter Algorithmus wird am Ende von p angezeigt. 4 von saba.kntu.ac.ir/eecd/people/aliyari/NN%20%20files/rls.pdf . Dies kann durch Googeln "rekursive kleinste Quadrate" gefunden werden. Es sieht nicht nach einer Verbesserung des Gentleman / Maindonald-Ansatzes aus, ist aber zumindest klar und explizit beschrieben.

whuber

2

Der letzte Link sieht aus wie die Methode, die ich vorschlagen wollte. Die von ihnen verwendete Matrix-Identität ist an anderen Orten als Sherman-Morrison-Woodbury-Identität bekannt. Es ist auch numerisch sehr effizient zu implementieren, aber möglicherweise nicht so stabil wie eine Givens-Rotation.

Kardinal

2

@suncoolsu Hmm ... Maindonalds Buch wurde neu veröffentlicht, als ich damit anfing :-).

Whuber

8

Ich denke, wenn Sie Ihr lineares Regressionsmodell in ein Zustandsmodell umwandeln , erhalten Sie das, wonach Sie suchen. Wenn Sie R verwenden, können Sie das Paket dlm verwenden und sich das Begleitbuch von Petris et al.

F. Tusell
quelle

Vielleicht bin ich verwirrt, aber dies scheint sich auf ein Zeitreihenmodell zu beziehen? Mein Modell ist eigentlich einfacher, da es sich bei den Samples nicht um Zeitreihen handelt (im Grunde genommen handelt es sich um unabhängige (x-> y) Samples, sie werden im Laufe der Zeit nur in großen Mengen akkumuliert)

mikera

1

Ja, im Allgemeinen wird dies für Zeitreihen mit nicht unabhängigen Beobachtungen verwendet. Sie können jedoch immer eine Korrelation zwischen aufeinanderfolgenden Beobachtungen annehmen, was für Sie den speziellen Fall von Interesse darstellt.

F. Tusell

7

Sie können die Summe der Quadrate, die für die Parameter Ihres Modells kosten, immer nur mit einem Gefälle absteigen . Nehmen Sie einfach den Gradienten, aber entscheiden Sie sich nicht für die geschlossene Form, sondern nur für die Suchrichtung. $E$ $W$

Lassen sind die Kosten der i - ten Trainingsprobe gegeben die Parameter . Ihr Update für den j-ten Parameter lautet dann $E(i; W)$ $W$

W_{j} \leftarrow W_{j} + α \frac{\partial E (i; W)}{\partial W_{j}}

$W_{j} \leftarrow W_j + \alpha \frac{\partial{E(i; W)}}{\partial{W_j}}$

Wobei eine Schrittrate ist, die Sie über eine Kreuzvalidierung oder ein gutes Maß auswählen sollten. $\alpha$

Dies ist sehr effizient und die Art und Weise, wie neuronale Netze typischerweise trainiert werden. Sie können sogar viele Samples (z. B. 100) effizient parallel verarbeiten.

Natürlich können auch komplexere Optimierungsalgorithmen (Impuls, konjugierter Gradient, ...) angewendet werden.

bayerj
quelle

Scheint diesem Artikel sehr ähnlich. Eprints.pascal-network.org/archive/00002147/01/… . Es wurde in einem Open-Source-Projekt namens jubatus implementiert.

Saccharine

3

Überrascht hat dies bisher noch niemand angerührt. Die lineare Regression hat eine quadratische Zielfunktion. Ein Newton-Raphson-Schritt von jedem Ausgangspunkt aus führt Sie direkt zum Optima. Angenommen, Sie haben bereits eine lineare Regression durchgeführt. Die Zielfunktion ist:

L (β) = (y - X β)^{t} (y - X β)

$L(\beta) = (y - X \beta)^t (y - X \beta)$ Der Gradient wird zu Und das Hessische:

\nabla L (β) = - 2 X^{t} (y - X β)

$\nabla L (\beta) = -2 X^t (y - X \beta)$

\nabla^{2} L (β) = X^{t} X

$\nabla^2 L (\beta) = X^t X$

Jetzt haben Sie einige vergangene Daten erhalten und eine lineare Regression durchgeführt. Sie sitzen mit Ihren Parametern ( ). Der Gradient an diesem Punkt ist per Definition Null. Der Hessische ist wie oben angegeben. Ein neuer Datenpunkt ( ) kommt an. Sie berechnen die Steigung für den neuen Punkt einfach über: $\beta$ $x_{new}, y_{new}$

\nabla L_{n e w} (β) = - 2 x_{n e w} (y_{n e w} - x_{n e w}^{T} β)

$\nabla L_{new}(\beta) = -2 x_{new} (y_{new}-x_{new}^T \beta)$ und das wird Ihr Gesamtfarbverlauf (da der Farbverlauf aus den vorhandenen Daten Null war) . Das Hessische für den neuen Datenpunkt ist:

\nabla^{2} L_{n e w} = x_{n e w} x_{n e w}^{T}

$\nabla^2 L_{new} = x_{new}x_{new}^T$ .

Fügen Sie dies dem oben angegebenen alten Hessischen hinzu. Dann machen Sie einfach einen Schritt nach Newton Raphson.

β_{n e w} = β_{o l d} + (\nabla^{2} L)^{- 1} \nabla L_{n e w}

$\beta_{new} = \beta_{old} + (\nabla^2L)^{-1} \nabla L_{new}$

Und du bist fertig.

ryu576
quelle

1

\nabla L_{n e w}

$\nabla L_{new}$

p,

$p,$

O (p^{3})

$O(p^3)$

O (p^{3})

$O(p^3)$

p

$p$

(I - A)^{- 1} = I + A + A^{2} + \dots

$(I-A)^{-1}=I+A+A^2+ \dots$

2

Die standardmäßige Anpassung der kleinsten Quadrate ergibt Regressionskoeffizienten

$\beta = ( X^T X )^{-1} X^T Y$

$\beta$

$X^T X$ $X^T Y$ $M^2+M$ $\beta$

Wenn beispielsweise M = 1 ist, ist der eine Koeffizient

$\beta = \frac{\sum_{i=1}^N{x_i y_i}}{\sum_{i=1}^N{x_i^2}}$

Jedes Mal, wenn Sie einen neuen Datenpunkt erhalten, aktualisieren Sie beide Summen, berechnen das Verhältnis und erhalten den aktualisierten Koeffizienten.

$X^T X$ $X^T Y$ $(1-\lambda)$ $\lambda$

Mark Higgins
quelle

2

β

$\beta$

X^{T} X

$X^T X$

X^{T} Y

$X^T Y$

6

X^{'} X

$X'X$

1

C^{- 1} x

$C^{-1}x$

C

$C$

x

$x$

z_{t + 1} = z_{t} + x - C z_{t}

$z_{t+1}=z_t + x - Cz_t$

z \to C^{- 1} x

$z\to C^{-1}x$

t \to \infty

$t\to\infty$

1

Das Problem lässt sich leichter lösen, wenn Sie die Dinge ein wenig umschreiben:

Y = y

X = [x, 1]

dann

Y = A * X

Eine einmalige Lösung wird durch Berechnung gefunden

V = X '* X

und

C = X '* Y

Beachten Sie, dass das V die Größe N-by-N und C die Größe N-by-M haben sollte. Die Parameter, die Sie suchen, sind dann gegeben durch:

A = inv (V) * C

Da sowohl V als auch C durch Summieren Ihrer Daten berechnet werden, können Sie A bei jeder neuen Stichprobe berechnen. Dies hat jedoch eine zeitliche Komplexität von O (N ^ 3).

Da V quadratisch und semi-definit positiv ist, existiert eine LU-Zerlegung, die die Invertierung von V numerisch stabiler macht. Es gibt Algorithmen zur Durchführung von Rang-1-Aktualisierungen der Inverse einer Matrix. Finden Sie diese und Sie haben die effiziente Implementierung, die Sie suchen.

Die Update-Algorithmen für Rang 1 finden Sie in "Matrix-Berechnungen" von Golub und van Loan. Es ist ein hartes Material, aber es bietet einen umfassenden Überblick über solche Algorithmen.

Hinweis: Die obige Methode liefert bei jedem Schritt eine Schätzung der kleinsten Quadrate. Sie können den Aktualisierungen von X und Y ganz einfach Gewichte hinzufügen. Wenn die Werte von X und Y zu groß werden, können sie mit einem einzelnen Skalar skaliert werden, ohne das Ergebnis zu beeinflussen.

Herr weiß
quelle

Effiziente lineare Online-Regression

Antworten:

Verweise