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

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.

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ć .$2^K$$K$$\mathcal{O}(K^2 n)$$n$$\mathcal{O}(2^K K^2 n)$

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$\lambda$$\lambda$$S$$\lambda$$L$$\lambda$$\mathcal{O}(LSK^2 n)$
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 $\lambda$$\lambda$$\mathcal{O}(LSK^2 n)$
$\mathcal{O}(ALSK^2 n)$$A$$\alpha$ 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).

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.