Geschwindigkeit, Rechenaufwand von PCA, LASSO, elastisches Netz

18

Ich versuche, die rechnerische Komplexität / Schätzgeschwindigkeit von drei Gruppen von Methoden für die lineare Regression zu vergleichen, wie sie in Hastie et al. "Elemente des statistischen Lernens" (2. Aufl.), Kapitel 3:

  1. Auswahl der Teilmenge
  2. Schrumpfmethoden
  3. Methoden mit abgeleiteten Eingaberichtungen (PCR, PLS)

Der Vergleich kann sehr grob sein, nur um eine Vorstellung zu vermitteln. Ich verstehe, dass die Antworten von der Dimension des Problems und der Anpassung der Computerarchitektur abhängen können. Für ein konkretes Beispiel kann man eine Stichprobengröße von 500 und 50 Regressionskandidaten in Betracht ziehen. Ich interessiere mich hauptsächlich für die Motivation hinter der Komplexität der Berechnung / Schätzgeschwindigkeit, aber nicht dafür, wie lange ein bestimmter Prozessor für das gegebene Beispiel benötigt.

Richard Hardy
quelle
Bei Verwendung von PCR oder PLS ist die Anzahl der Komponenten ein Abstimmungsparameter (ähnlich wie bei der Ridge-Regression). Daher müssen diese Methoden auch gegenseitig validiert werden, um die optimale Anzahl von Komponenten zu finden. LASSO hat auch einen Regularisierungsparameter, aber das elastische Netz hat zwei (elastisches Netz = Kamm + LASSO), so dass die Kreuzvalidierung teurer ist. Abgesehen davon passt LASSO wahrscheinlich langsamer als alle anderen Modelle, da es keine geschlossene Lösung gibt. λ
Amöbe sagt Reinstate Monica
Vielen Dank! Ihr Kommentar wäre eine gute Antwort, wenn Sie zwei weitere Details hinzufügen würden: (1) Wie teuer ist eine Iteration von PCR und PLS im Vergleich zu einem OLS-Lauf der regulären Regression? (2) Quantifizieren Sie die Geschwindigkeit von LASSO genauer, um sie mit der Geschwindigkeit der regulären Regression vergleichbar zu machen (ist sie polynomiell, exponentiell oder linear teurer und warum?).
Richard Hardy
Leider habe ich keine Antwort darauf, insbesondere auf (2). Deshalb habe ich nur einen Kommentar hinterlassen. +1 übrigens und herzlichen Glückwunsch mit 5k rep!
Amöbe sagt Reinstate Monica
1
@amoeba, danke! Ich hätte nicht damit gerechnet, 5 km zu erreichen, als ich letztes Jahr (sehr langsam) angefangen habe. Aber es ist sehr aufregend und lohnend, hier bei Cross Validated ein aktives Mitglied zu sein!
Richard Hardy
@amoeba, ich glaube, ich habe die Komplexität von LASSO verstanden, wenn der LARS-Algorithmus verwendet wird. Ich habe meinen Beitrag entsprechend aktualisiert. Aber ich habe die LARS-Zeitung nicht sorgfältig gelesen, daher bin ich mir nicht ganz sicher, ob sie korrekt ist ...
Richard Hardy

Antworten:

5

Gruppe 1 :
Die Komplexität / Geschwindigkeit von Gruppe 1 scheint nicht allzu schwierig zu sein, wenn Brute-Force-Algorithmen verwendet werden (obwohl es effizientere Alternativen geben kann, wie den "leaps and bounds" -Algorithmus). Für die vollständige Auswahl von Teilmengen sind beispielsweise Regressionen erforderlich , um bei einem Pool von Kandidatenmerkmalen angepasst zu werden. Eine OLS-Anpassung einer linearen Regression hat die Komplexität von (gemäß diesem Beitrag ), wobei die Stichprobengröße ist. Daher sollte die Gesamtkomplexität der vollständigen Brute-Force-Teilmengenauswahl . K O ( K 2 n ) n O ( 2 K K 2 n )2KKO(K2n)nO(2KK2n)

Gruppe 2 :
Die Komplexität / Geschwindigkeit von Gruppe 2 wird in den Abschnitten 3.8 und 3.9 des Buches erörtert. Zum Beispiel Grat Regression mit einer bestimmten Strafe hat die gleiche Rechenkomplexität als reguläre Regression. Da mithilfe der Kreuzvalidierung ermittelt werden muss, steigt die Rechenlast linear in der Anzahl der bei der Kreuzvalidierung verwendeten Datenaufteilungen (z. B. ). Wenn das Gitter Punkte hat, ist die Gesamtkomplexität der Kammregression mit dem Einstellen des Parameters . Es wird ziemlich viel darüber geredetλ S λ L λ O ( L S K 2 n ) λ λ O ( L S K 2 n ) O ( A L S K 2 n ) A αλλSλLλO(LSK2n)
LASSO im Buch, aber ich konnte nicht ganz finden, was ich brauche. Ich fand jedoch auf p. 443 von Efron et al. "Least Angle Regression" (2004), dass die LASSO-Komplexität für ein gegebenes der Komplexität einer OLS-Anpassung der linearen Regression entspricht, wenn die LARS-Methode verwendet wird. Dann ist die Gesamtkomplexität von LASSO mit der Einstellung des Parameters . (Ich habe dieses Papier nicht sorgfältig gelesen. Bitte korrigieren Sie mich, wenn ich dieses falsch verstanden habe.) Elastisches Netz kombiniert Kamm und LASSO. die beiden haben die gleiche rechnerische Komplexität; daher sollte die Komplexität des elastischen Netzes wobei die Gittergröße des Abstimmungsparameters istλλO(LSK2n)
O(ALSK2n)Aα , das die Gewichte des Kamms gegen LASSO ausgleicht.

Gruppe 3 :
Ich vermisse immer noch eine Anmerkung zur Komplexität / Geschwindigkeit der Gruppe 3. Diese besteht aus der Regression der Hauptkomponenten (PCR) und den partiellen kleinsten Quadraten (PLS).

Richard Hardy
quelle
2

Dies gilt nur für einen Teil von Frage 2 in Gruppe 3 (nämlich PLS), kann jedoch dennoch informativ sein: Srinivasan et al. (2010, technischer Bericht; siehe https://www.umiacs.umd.edu/~balajiv/Papers/ UMD_CS_TR_Pls_Gpu.pdf ) führte einige Messungen an PLS mit dem NIPALS-Algorithmus durch. Dabei wurde angegeben, dass die zeitliche (und räumliche) Komplexität dieses Algorithmus O (dN) beträgt ) Gesichtserkennung. Die Messungen wurden mit einer eigenen GPU-basierten Implementierung durchgeführt.

jf1
quelle