Szybkość, koszty obliczeniowe PCA, LASSO, siatka elastyczna

18

Próbuję porównać złożoność obliczeniową / szybkość estymacji trzech grup metod regresji liniowej, jak wyróżniono w Hastie i in. „Elementy statystycznego uczenia się” (wydanie drugie), rozdział 3:

  1. Wybór podzbioru
  2. Metody skurczowe
  3. Metody wykorzystujące pochodne kierunki wprowadzania (PCR, PLS)

Porównanie może być bardzo przybliżone, aby dać pewien pomysł. Rozumiem, że odpowiedzi mogą zależeć od wymiaru problemu i tego, jak pasuje to do architektury komputera, więc na konkretny przykład można rozważyć próbkę o wielkości 500 i 50 kandydatów na regresory. Najbardziej interesuje mnie motywacja związana ze złożonością obliczeniową / szybkością szacowania, ale nie to, jak długo zajmie to procesorowi w danym przykładzie.

Richard Hardy
źródło
Podczas korzystania z PCR lub PLS liczba składników jest parametrem dostrajającym (podobnie jak w regresji grzbietu). Dlatego te metody będą również musiały zostać poddane walidacji krzyżowej, aby znaleźć optymalną liczbę składników. LASSO ma również jeden parametr regularyzacji, ale elastyczna siatka ma dwa (elastyczna siatka = grzbiet + LASSO), więc walidacja krzyżowa jest droższa. Poza tym LASSO jest prawdopodobnie wolniejszy w montażu niż wszystkie inne modele, ponieważ nie ma rozwiązania w formie zamkniętej. λ
ameba mówi Przywróć Monikę
Dziękuję Ci! Twój komentarz byłby dobrą odpowiedzią, gdybyś dodał dwa dodatkowe szczegóły: (1) jak drogie jest jedno powtórzenie PCR i PLS w porównaniu z jednym przebiegiem OLS regresji zwykłej; (2) dokładniej obliczyć prędkość LASSO, aby uczynić ją porównywalną z prędkością regresji regularnej (czy jest ona wielomianowa, wykładniczo lub liniowo droższa i dlaczego).
Richard Hardy,
Niestety nie mam gotowej odpowiedzi na to pytanie, szczególnie na (2). Dlatego zostawiłem tylko komentarz. Nawiasem mówiąc, +1 i gratuluję 5k powtórzeń!
ameba mówi Przywróć Monikę
1
@amoeba, dzięki! Nie mogłem oczekiwać, że osiągnę 5 000, kiedy zacząłem (bardzo powoli) w zeszłym roku. Ale bycie aktywnym członkiem Cross Validated jest bardzo ekscytujące i satysfakcjonujące!
Richard Hardy,
@amoeba, myślę, że opanowałem złożoność LASSO, jeśli użyty jest algorytm LARS; Zaktualizowałem odpowiednio swój post. Ale nie przeczytałem dokładnie artykułu LARS, więc nie jestem całkowicie pewien, czy jest poprawny ...
Richard Hardy

Odpowiedzi:

5

Grupa 1 :
Złożoność / szybkość grupy 1. nie wydaje się zbyt trudnym do ustalenia, czy stosowane są algorytmy brutalnej siły (chociaż mogą istnieć bardziej wydajne alternatywy, takie jak algorytm „przeskakiwania”). Na przykład, pełny wybór podzbioru będzie wymagał dopasowania regresji, biorąc pod uwagę pulę funkcji kandydujących. Dopasowanie OLS jednej regresji liniowej ma złożoność (jak w tym poście ), gdzie jest rozmiarem próbki. Zatem całkowita złożoność wyboru pełnego podzbioru siły brutalnej powinna wynosić .2KKO(K2n)nO(2KK2n)

Grupa 2 :
Złożoność / szybkość grupy 2. omówiono w rozdziałach 3.8 i 3.9 książki. Na przykład regresja kalenicowa z określoną karą ma taką samą złożoność obliczeniową jak regresja regularna. Ponieważ należy znaleźć za pomocą walidacji krzyżowej, obciążenie obliczeniowe rośnie liniowo w liczbie podziałów danych wykorzystywanych w walidacji krzyżowej (powiedzmy ). Jeśli siatka ma punkty , całkowita złożoność regresji grzbietu z dostrajaniem parametru będzie wynosić . Trochę się mówiλλSλLλO(LSK2n)
LASSO w książce, ale nie mogłem znaleźć dokładnie tego, czego potrzebowałem. Znalazłem jednak na str. 443 Efron i in. „Regresja najmniejszego kąta” (2004), że złożoność LASSO dla danej jest taka sama, jak złożoność dopasowania regresji liniowej OLS, jeśli stosowana jest metoda LARS. Wtedy całkowita złożoność LASSO z dostrajaniem parametru będzie wynosić . (Nie przeczytałem dokładnie tego artykułu, więc proszę mnie poprawić, jeśli go pomyliłem.) Elastyczna siatka łączy grzbiet i LASSO; oba mają tę samą złożoność obliczeniową; stąd złożoność siatki elastycznej powinna wynosić gdzie jest rozmiarem siatki parametru strojeniaλ O ( L S K 2 n ) O ( A L S K 2 n ) A αλλO(LSK2n)
O(ALSK2n)Aα która równoważy wagi grzbietu w porównaniu z LASSO.

Grupa 3 :
ja nadal brakuje żadnej wiadomości od złożoności / prędkości dla grupy 3., który składa się z głównych składników regresji (PCR) i częściowych najmniejszych kwadratów (PLS).

Richard Hardy
źródło
2

Dotyczy tylko jednej części pytania 2 w grupie 3 powyżej (a mianowicie PLS), ale może mieć jednak charakter informacyjny: Srinivasan i in. (2010, raport techniczny; patrz https://www.umiacs.umd.edu/~balajiv/Papers/ UMD_CS_TR_Pls_Gpu.pdf ) wykonał pewne pomiary PLS przy użyciu algorytmu NIPALS - stwierdzając, że złożoność tego algorytmu w czasie (i przestrzeni) wynosi O (dN) - w celu wyodrębnienia i włączenia ich w różnych modelach dla a) wykrycia ludzi na obrazach oraz b ) rozpoznawanie twarzy. Pomiary przeprowadzono przy użyciu ich własnej implementacji opartej na GPU.

jf1
źródło