Gibt es Algorithmen zur Berechnung laufender linearer oder logistischer Regressionsparameter?

32

In einem Artikel "Genaue Berechnung der Laufabweichung" unter http://www.johndcook.com/standard_deviation.html wird gezeigt, wie der Laufmittelwert, die Laufabweichung und die Standardabweichungen berechnet werden.

Gibt es Algorithmen, bei denen die Parameter eines linearen oder logistischen Regressionsmodells ähnlich "dynamisch" aktualisiert werden können, wenn neue Trainingsaufzeichnungen bereitgestellt werden?

chl
quelle
1
Mit einem riesigen Trainingssatz oder einem kontinuierlichen Datenfluss können Sie iterative Algorithmen wie Stochastic Gradient Descent verwenden und die Eingabe in kleinen Stapeln erfassen, während Sie fortfahren. Haben Sie das gefragt?
andreister
1
Nachschlagen des RLS-Algorithmus und seiner Varianten. en.wikipedia.org/wiki/Recursive_least_squares_filter
Memming

Antworten:

20

Die linearen Regressionskoeffizienten von y=einx+b sind ein=cOv(x,y)/veinr(x) und b=meeinn(y)-einmeeinn(x) .

Alles, was Sie wirklich brauchen, ist eine inkrementelle Methode zur Berechnung von cOv(x,y) . Aus diesem Wert und der Varianz von x und dem Mittelwert von y und x Sie die Parameter a und b berechnen . Wie Sie im folgenden Pseudocode sehen werden, ist die inkrementelle Berechnung von cov(x,y) der inkrementellen Berechnung von var(x) sehr ähnlich . Dies sollte keine Überraschung sein, da var(x)=cov(x,x) .

Hier ist der Pseudocode, den Sie wahrscheinlich suchen:

init(): meanX = 0, meanY = 0, varX = 0, covXY = 0, n = 0

update(x,y):
n += 1
dx = x - meanX
dy = y - meanY
varX += (((n-1)/n)*dx*dx - varX)/n
covXY += (((n-1)/n)*dx*dy - covXY)/n
meanX += dx/n
meanY += dy/n

getA(): return covXY/varX
getB(): return meanY - getA()*meanX

Ich fand diese Frage, als ich nach einem äquivalenten Algorithmus suchte, der inkrementell eine Multi-Variate-Regression als R=(XX)1XY berechnet , so dass XR=Y+ϵ

chmike
quelle
4
Danke für Ihren Beitrag! Der Teil der Frage zur linearen Regression ist tatsächlich ein Duplikat von stats.stackexchange.com/questions/6920/…, dessen Antworten zeigen, wie ein Modell mit mehreren linearen Regressionen aktualisiert wird. Der vorliegende Thread darf stehen, da der logistische Regressionsteil der Frage unabhängig von Interesse ist. Tatsächlich wurde sogar der logistische Teil unter stats.stackexchange.com/questions/59174/… dupliziert .
whuber
1
Ich dachte, diese Antwort wäre angesichts des in der Frage angegebenen Referenztextes nützlich. Danke für den Link. Es ist jedoch nicht das, wonach ich suche. Mein Anwendungsfall ist offensichtlich spezifisch.
Chmike
3
Ich glaube, es kann nützlich sein und ist einzigartig im Anbieten von Arbeitscode.
Whuber
Darf ich Sie fragen, warum Sie dx * dy mal (n-1) / n lassen?
FavorMylikes
Können Sie den Code zur Berechnung des p-Werts verbessern?
Nathan
12

Für Ihre zwei spezifischen Beispiele:

Lineare Regression Die Arbeit "Online Lineare Regression und ihre Anwendung auf das modellbasierte Verstärkungslernen" von Alexander Strehl und Michael Littman beschreibt einen Algorithmus namens "KWIK Lineare Regression" (siehe Algorithmus 1), der eine Annäherung an die lineare Regressionslösung unter Verwendung von inkrementellen Aktualisierungen bietet . Beachten Sie, dass dies nicht geregelt ist (dh es handelt sich nicht um eine Ridge-Regression). Ich bin mir ziemlich sicher, dass die Methode von Strehl & Littman nicht auf diese Einstellung ausgedehnt werden kann.

Logistische Regression

Dieser Thread bringt Licht in die Sache. Zitat:

Auch ohne Regularisierungsbeschränkung ist die logistische Regression ein nichtlineares Optimierungsproblem. Es ist bereits keine analytische Lösung vorhanden, was normalerweise Voraussetzung für die Ableitung einer Aktualisierungslösung ist. Mit einer Regularisierungsbeschränkung wird dies zu einem eingeschränkten Optimierungsproblem. Dies führt eine ganze Reihe von nicht-analytischen Komplikationen ein, die zu denen hinzukommen, die das uneingeschränkte Problem bereits hatte.

Es gibt jedoch auch andere Online- (oder inkrementelle) Methoden für die Regression, die Sie sich möglicherweise ansehen möchten, z. B. die lokal gewichtete Projektionsregression (LWPR).

tdc
quelle
In Bezug auf die logistische Regression sind Sie meines Erachtens unnötig pessimistisch. Die logistische Regression entspricht der Berechnung der hinteren Klassenwahrscheinlichkeiten für ein Zwei-Klassen-Problem, wobei jede Klasse mit unterschiedlichen Mitteln und einer gemeinsamen Kovarianz nach Gauß verteilt wird. Die MLE für die Kovarianz ist nur eine gewichtete Summe der Kovarianzen pro Klasse, daher sind die ausreichenden Statistiken nur die Anzahl, die Summe und die Summe der Quadrate pro Klasse. Offensichtlich ist es einfach, anhand der ausreichenden Statistiken ein genaues Update zu erstellen.
Robert Dodier
3
@RobertDodier Sie haben die lineare Diskriminanzanalyse und nicht die logistische Regression beschrieben. Der letzte Absatz der Einleitung hier verdeutlicht die Beziehung.
Ahfoss
@ahfoss Auch wenn die klassenbezogenen Daten nicht normal verteilt sind, kann ein Modell erstellt werden, das der logistischen Regression über klassenbezogene Kovarianzen entspricht.
Robert Dodier
1
@RobertDodier Was ist das entsprechende Modell? Sie scheinen zu implizieren, dass es eine offensichtliche Lösung für ein im Wesentlichen schwieriges Problem gibt. Ihre Lösung ist entweder brillanter als Sie denken oder viel weniger.
Ahfoss
11

Grundsätzlich gilt:

0) Sie behalten die ausreichenden Statistiken und die aktuellen ML-Schätzungen bei

1) Wenn Sie neue Daten erhalten, aktualisieren Sie die ausreichenden Statistiken und die Schätzungen

2) Wenn Sie nicht über ausreichende Statistiken verfügen, müssen Sie alle Daten verwenden.

3) Normalerweise haben Sie keine geschlossenen Lösungen. Verwenden Sie die vorherigen MLEs als Ausgangspunkt, und verwenden Sie eine geeignete Optimierungsmethode, um das neue Optimum von dort aus zu finden. Möglicherweise müssen Sie ein wenig experimentieren, um herauszufinden, welche Ansätze die besten Kompromisse für Ihre speziellen Arten von Probleminstanzen darstellen.

Wenn Ihr Problem eine spezielle Struktur hat, können Sie es wahrscheinlich ausnutzen.

Einige potenzielle Referenzen, die möglicherweise einen Wert haben oder nicht:

McMahan, HB und M. Streeter (2012),
Offenes Problem: Bessere Grenzen für die logistische Online-Regression ,
JMLR: Workshop and Conference Proceedings , Band 23, 44.1–44.3

Penny, WD und SJ Roberts (1999),
Dynamic Logistic Regression ,
Proceedings IJCNN '99

Glen_b - Setzen Sie Monica wieder ein
quelle
Ich bin mit der Idee einverstanden, ausreichende Statistiken zu führen (sofern diese für das Problem existieren), aber macht das Vorhandensein ausreichender Statistiken die anderen Dinge nicht unnötig? Wenn Sie über ausreichende Statistiken verfügen, können Sie aktualisierte Parameter genau so berechnen, als ob Sie den gesamten Datensatz verwendet hätten. Es ist nicht erforderlich, die aktuellen Parameter zu berücksichtigen und mit Optimierungsmethoden zu experimentieren.
Robert Dodier
2
Es ist jedoch wichtig zu beachten, dass eine ausreichende Statistik nicht bedeutet, dass Sie eine Lösung für die Gleichungen haben.
Glen_b
8

Zusätzlich zu der Antwort von tdc gibt es keine bekannten Methoden, um exakte Schätzungen der Koeffizienten zu irgendeinem Zeitpunkt mit nur konstanter Zeit pro Iteration zu berechnen. Es gibt jedoch einige Alternativen, die vernünftig und interessant sind.

Das erste zu betrachtende Modell ist die Online- Lerneinstellung. In dieser Einstellung kündigt die Welt zuerst einen Wert von x an, Ihr Algorithmus sagt einen Wert für y voraus, die Welt kündigt den wahren Wert y 'an und Ihr Algorithmus erleidet einen Verlust l (y, y'). Für diese Einstellung ist bekannt, dass einfache Algorithmen (unter anderem Gradientenabstieg und potenzierter Gradient) sublineares Bedauern hervorrufen. Dies bedeutet, dass, wenn Sie mehr Beispiele sehen, die Anzahl der zusätzlichen Fehler, die Ihr Algorithmus macht (im Vergleich zum bestmöglichen linearen Prädiktor), nicht mit der Anzahl der Beispiele wächst. Dies funktioniert auch in Gegnern. Es gibt ein gutes Papier , das eine beliebte Strategie erklärt, um diese Grenzen des Bedauerns zu belegen. Nützlich sind auch die Vorlesungsunterlagen von Shai Shalev-Schwartz .

Es gibt eine Erweiterung der Online-Lerneinstellung, die als Banditeneinstellung bezeichnet wird, bei der Ihrem Algorithmus nur eine Zahl zugewiesen wird, die angibt, wie falsch er war (und kein Zeiger auf die richtige Antwort). Beeindruckend ist, dass viele Ergebnisse des Online-Lernens auf diese Umgebung übertragen werden, mit der Ausnahme, dass hier sowohl Exploits als auch Exploits durchgeführt werden müssen, was zu allen möglichen interessanten Herausforderungen führt.

Alexandre Passos
quelle
6

Andere Antworten haben auf die Welt des maschinellen Lernens hingewiesen, und dies ist sicherlich ein Ort, an dem dieses Problem angegangen wurde.

Ein weiterer Ansatz, der möglicherweise besser auf Ihre Bedürfnisse zugeschnitten ist, ist die Verwendung der QR-Faktorisierung mit Updates mit niedrigem Rang. Ansätze dazu und zur Lösung von Problemen der kleinsten Fehlerquadrate finden Sie in:

Aktualisierung der QR-Faktorisierung und des Problems der kleinsten Fehlerquadrate durch Hammerling und Lucas.


quelle
5

yt=βtxt+εt,βt=βt-1+ηt
βt=βt-1

yt=lOGicht(βtxt+εt),βt=βt-1+ηt
Kochede
quelle
2

Dies ist zu @chmike Antwort hinzuzufügen.

Die Methode scheint dem Online-Algorithmus von BP Welford für die Standardabweichung zu ähneln, der auch den Mittelwert berechnet. John Cook gibt eine gute Erklärung hier . Tony Finch im Jahr 2009 bietet eine Methode für einen exponentiellen gleitenden Durchschnitt und eine Standardabweichung:

diff := x – mean 
incr := alpha * diff 
mean := mean + incr 
variance := (1 - alpha) * (variance + diff * incr)

Schauen Sie sich die zuvor gepostete Antwort an und erweitern Sie sie um ein sich exponentiell bewegendes Fenster:

init(): 
    meanX = 0, meanY = 0, varX = 0, covXY = 0, n = 0,
    meanXY = 0, varY = 0, desiredAlpha=0.01 #additional variables for correlation

update(x,y):
    n += 1
    alpha=max(desiredAlpha,1/n) #to handle initial conditions

    dx = x - meanX
    dy = y - meanY
    dxy = (x*y) - meanXY #needed for cor

    varX += ((1-alpha)*dx*dx - varX)*alpha
    varY += ((1-alpha)*dy*dy - varY)*alpha #needed for corXY
    covXY += ((1-alpha)*dx*dy - covXY)*alpha

    #alternate method: varX = (1-alpha)*(varX+dx*dx*alpha)
    #alternate method: varY = (1-alpha)*(varY+dy*dy*alpha) #needed for corXY
    #alternate method: covXY = (1-alpha)*(covXY+dx*dy*alpha)

    meanX += dx * alpha
    meanY += dy * alpha
    meanXY += dxy  * alpha

getA(): return covXY/varX
getB(): return meanY - getA()*meanX
corXY(): return (meanXY - meanX * meanY) / ( sqrt(varX) * sqrt(varY) )

In dem obigen "Code" könnte gewünschtes Alpha auf 0 gesetzt werden, und wenn dies der Fall ist, würde der Code ohne exponentielle Gewichtung arbeiten. Es kann vorgeschlagen werden, "desiredAlpha" auf "1 / desiredWindowSize" zu setzen, wie von " Modified_moving_average" für eine sich bewegende Fenstergröße vorgeschlagen.

Nebenfrage: Welche der obigen alternativen Berechnungen sind vom Standpunkt der Präzision aus besser?

Verweise:

chmike (2013) https://stats.stackexchange.com/a/79845/70282

Cook, John (nd) Genaue Berechnung der Laufvarianz http://www.johndcook.com/blog/standard_deviation/

Finch, Tony. (2009) Inkrementelle Berechnung von gewichtetem Mittelwert und Varianz. https://fanf2.user.srcf.net/hermes/doc/antiforgery/stats.pdf

Wikipedia. (nd) Welfords Online-Algorithmus https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm

Chris
quelle