Regresja wielowymiarowa: dlaczego wyjątkowy?

16

Próbuję przeczytać o badaniach w dziedzinie regresji wielowymiarowej; gdy jest większe niż , to znaczy p >> n . Wydaje się, że termin \ log p / n pojawia się często w odniesieniu do wskaźnika konwergencji dla estymatorów regresji.pnp>>nlogp/n

Na przykład tutaj równanie (17) mówi, że dopasowanie lasso, β^ spełnia

1nXβ^Xβ22=OP(σlogpnβ1).

Zwykle oznacza to również, że logp powinien być mniejszy niż n .

  1. Czy jest jakaś intuicja, dlaczego ten stosunek logp/n jest tak znaczący?
  2. Również z literatury wydaje się, że problem regresji wielowymiarowej komplikuje się, gdy logpn . Dlaczego tak jest
  3. Czy istnieje dobre odniesienie omawiające problemy dotyczące tego, jak szybko p i n powinny rosnąć w stosunku do siebie?
Greenparker
źródło
2
1. Termin pochodzi od (miar Gaussa) koncentracji miary. W szczególności, jeśli masz losowe zmienne Gaussa IID, ich maksimum jest rzędu z dużym prawdopodobieństwem. Współczynnik przychodzi właśnie dlatego, że patrzysz na średni błąd prognozy - tzn. Pasuje on do po drugiej stronie - jeśli spojrzysz na błąd całkowity, nie będzie go. pσlogpp n - 1 n - 1σlogpn1n1
mweylandt
1
2. Zasadniczo masz dwie siły, które musisz kontrolować: i) dobre właściwości posiadania większej ilości danych (więc chcemy, aby była duża); ii) trudności mają więcej (nieistotnych) cech (dlatego chcemy, aby było małe). W statystyce klasycznej zwykle naprawiamy i pozwalamy przejść do nieskończoności: ten reżim nie jest super przydatny w teorii wielowymiarowej, ponieważ z założenia jest reżimem niskowymiarowym. Alternatywnie, możemy pozwolić przejdź do nieskończoności i pobytu stałej, ale wtedy nasz błąd tylko dmucha się i dąży do nieskończoności. p p n p nnppnpn
mweylandt
1
Dlatego musimy wziąć pod uwagę że idą w nieskończoność, aby nasza teoria była zarówno istotna (pozostaje wielowymiarowa) bez apokaliptyczności (cechy nieskończone, dane skończone). Posiadanie dwóch „pokręteł” jest zwykle trudniejsze niż posiadanie jednego pokrętła, więc naprawiamy dla niektórych i pozwalamy przejść do nieskończoności (a zatem pośrednio). Wybór określa zachowanie problemu. Z powodów w mojej odpowiedzi na pytanie 1 okazuje się, że „zło” z dodatkowych funkcji rośnie tylko jako podczas gdy „dobroć” z dodatkowych danych rośnie jako . p = f ( n ) f n f log pn,pp=fa(n)fanpfalogpn
mweylandt
1
Dlatego jeśli pozostaje stały (równoważnie, dla niektórych ), traktujemy wodę. Jeśli ( ) asymptotycznie osiągamy błąd zerowy. A jeśli ( ), błąd ostatecznie przechodzi w nieskończoność. Ten ostatni reżim jest czasem nazywany w literaturze „ultra-wysokowymiarowym”. Nie jest to beznadziejne (choć jest blisko), ale wymaga znacznie bardziej wyrafinowanych technik niż zwykłe maksimum Gaussów do kontrolowania błędu. Konieczność zastosowania tych złożonych technik jest ostatecznym źródłem złożoności, na którą zwracasz uwagę. logp/np=f(n)=Θ(Cn)Clogp/n0p=o(Cn)logp/np=ω(Cn)
mweylandt
@mweylandt Dzięki, te komentarze są bardzo przydatne. Czy mógłbyś zmienić je na oficjalną odpowiedź, abym mógł przeczytać je bardziej spójnie i głosować?
Greenparker

Odpowiedzi:

17

(Przeniesiono z komentarzy do odpowiedzi na żądanie @Greenparker)

Część 1)

Termin pochodzi od (miar Gaussa) koncentracji miary. W szczególności, jeśli masz IID zmienne losowe Gaussa [F1], ich maksimum jest rzędu z dużym prawdopodobieństwem. pσlogppσlogp

Współczynnik przychodzi właśnie dlatego, że patrzysz na średni błąd prognozy - tzn. Pasuje on do po drugiej stronie - jeśli spojrzysz na błąd całkowity, nie będzie go. n - 1n1n1

Część 2)

Zasadniczo masz dwie siły, które musisz kontrolować:

  • i) dobre właściwości posiadania większej ilości danych (więc chcemy, aby była duża);n
  • ii) trudności mają więcej (nieistotnych) cech (dlatego chcemy, aby było małe).p

W statystyce klasycznej zazwyczaj naprawiamy i pozwalamy przejść do nieskończoności: ten reżim nie jest super przydatny w teorii wielowymiarowej, ponieważ jest (asymptotycznie) w reżimie niskowymiarowym z uwagi na konstrukcję .npn

Alternatywnie, możemy pozwolić przejdź do nieskończoności i pobytu stałej, ale wtedy nasz błąd tylko wysadza jako problem staje się w zasadzie niemożliwe. W zależności od problemu błąd może osiągnąć nieskończoność lub zatrzymać się na pewnej naturalnej górnej granicy ( np. Błąd 100% błędnej klasyfikacji).npn

Ponieważ oba te przypadki są nieco bezużyteczne, zamiast tego rozważamy, że oba idą w nieskończoność, dzięki czemu nasza teoria jest istotna (pozostaje wielowymiarowa) bez apokaliptyczności (cechy nieskończone, dane skończone).n,p

Posiadanie dwóch „pokręteł” jest na ogół trudniejsze niż posiadanie jednego pokrętła, więc naprawiamy dla niektórych stałych i pozwalamy przejść do nieskończoności (a zatem idzie do nieskończoności pośrednio). [F2] Wybór określa zachowanie problemu. Z powodów w mojej odpowiedzi do części 1 okazuje się, że „zło” z dodatkowych funkcji rośnie tylko jako podczas gdy „dobroć” z dodatkowych danych rośnie jako .f n p f log p np=f(n)fnpflogpn

  • Jeśli pozostaje stały (równoważnie, dla niektórych ), traktujemy wodę, a problemem jest zmywanie (błąd pozostaje ustalony asymptotycznie); p=f(n)=Θ(Cn)Clogpnp=f(n)=Θ(Cn)C
  • jeśli ( ) asymptotycznie osiągamy zero błędów;p=o(Cn)logpn0p=o(Cn)
  • a jeśli ( ), błąd ostatecznie przechodzi w nieskończoność.p=ω(Cn)logpnp=ω(Cn)

Ten ostatni reżim jest czasem nazywany w literaturze „ultra-wysokowymiarowym”. O ile mi wiadomo, termin „ultra-wysoko-wymiarowy” nie ma ścisłej definicji, ale nieformalnie jest po prostu „reżimem, który łamie lasso i podobne estymatory”.

Możemy to wykazać za pomocą małego badania symulacyjnego w dość wyidealizowanych warunkach. Tutaj bierzemy teoretyczne wskazówki na temat optymalnego wyboru z [BRT09] i wybieramy .λ = 3 λλ=3log(p)/n

Najpierw rozważmy przypadek, w którym . Dzieje się tak w „realnym” reżimie wielowymiarowym opisanym powyżej i, jak przewiduje teoria, widzimy, że błąd prognozy zbiega się do zera:p=f(n)=3n

Asymptotyka wielowymiarowa

Kod do reprodukcji:

library(glmnet)
library(ggplot2)

# Standard High-Dimensional Asymptotics: log(p) / n -> 0

N <- c(50, 100, 200, 400, 600, 800, 1000, 1100, 1200, 1300)
P <- 3 * N

ERROR_HD <- data.frame()

for(ix in seq_along(N)){
  n <- N[ix]
  p <- P[ix]

  PMSE <- replicate(20, {
    X <- matrix(rnorm(n * p), ncol=p)
    beta <- rep(0, p)
    beta[1:10] <- runif(10, 2, 3)
    y <- X %*% beta + rnorm(n)

    g <- glmnet(X, y)

    ## Cf. Theorem 7.2 of Bickel et al. AOS 37(4), p.1705-1732, 2009. 
    ## lambda ~ 2*\sqrt{2} * \sqrt{\log(p)/n} 
    ## is good scaling for controlling prediction error of the lasso
    err <- X %*% beta - predict(g, newx=X, s=3 * sqrt(log(p)/n))
    mean(err^2)
  })

  ERROR_HD <- rbind(ERROR_HD, data.frame(PMSE=PMSE, n=n, p=p))
}

ggplot(ERROR_HD, aes(x=n, y=PMSE)) + geom_point() + theme_bw() + 
xlab("Number of Samples (n)") + 
ylab("Mean Prediction Error (at observed design points)") + 
ggtitle("Prediction Error Converging to 0 under High-Dim Asymptotics") + 
scale_x_continuous(sec.axis = sec_axis(~ 3 * ., name="Number of Features (p)")) + 
scale_y_log10()

Możemy to porównać do przypadku, w którym pozostaje w przybliżeniu stały: nazywam to „ultra-wymiarowym reżimem„ granicznym ”, ale to nie jest standardowy termin:logpn

P <- 10 + ceiling(exp(N/120))

Tutaj widzimy, że błąd przewidywania (przy użyciu tego samego projektu co powyżej) wyrówna się zamiast kontynuować do zera.

Borderline Ultra High Dimensional Asyptotics

Jeśli zestaw rośnie szybciej niż ( na przykład , ), przy czym błąd przewidywania wzrasta bez ograniczenia. Te są absurdalnie szybkie i prowadzą do ogromnych problemów / problemów numerycznych, więc oto nieco wolniejszy, ale wciąż przykład UHD:Penen2en2

P <- 10 + ceiling(exp(N^(1.03)/120))

Asymptotyki o bardzo wysokich wymiarach

(Użyłem rzadkiego losowego dla prędkości, więc nie próbuj porównywać liczb bezpośrednio z innymi wykresami). Trudno jest zauważyć poprawę na tym wykresie, być może dlatego, że powstrzymaliśmy wzrost UHD od zbyt „ultra” w nazwa czasu obliczeniowego. Zastosowanie większego wykładnika (np. ) sprawiłoby, że asymptotyczny wzrost byłby nieco wyraźniejszy.Xen1.5

Pomimo tego, co powiedziałem powyżej i jak może się wydawać, reżim ultra-wymiarowy nie jest w rzeczywistości całkowicie beznadziejny (choć jest blisko), ale wymaga znacznie bardziej wyrafinowanych technik niż tylko zwykła maksymalna zmienna losowa Gaussa do kontrolowania błędu. Konieczność zastosowania tych złożonych technik jest ostatecznym źródłem złożoności, na którą zwracasz uwagę.

Nie ma żadnego szczególnego powodu, aby sądzić, że powinno rosnąć „razem” w jakikolwiek sposób ( tj . Nie ma oczywistego powodu, aby naprawić ), ale matematyki na ogół brakuje języka i narzędzi do dyskusji z dwoma „stopniami swobody”, więc jest to najlepsze, co możemy zrobić (na razie!).p,np=f(n)

Część 3)

Obawiam się, że nie znam żadnych książek w literaturze statystycznej, które naprawdę koncentrują się na wzroście kontra . (W literaturze dotyczącej wykrywania kompresji może być coś)logpn

Moim ulubionym odniesieniem do tego rodzaju teorii są rozdziały 10 i 11 Statystycznego uczenia się ze sparsity [F3], ale ogólnie przyjmuje podejście polegające na rozważeniu stałej i nadaniu właściwości skończonej próbki (nie asymptotycznej) uzyskania „dobrego „wynik. Jest to w rzeczywistości bardziej wydajne podejście - gdy uzyskasz wynik dla dowolnego , łatwo rozważyć asymptotykę - ale te wyniki są na ogół trudniejsze do uzyskania, więc obecnie mamy je tylko dla estymatorów typu lasso, o ile wiedzieć.n,pn,p

Jeśli czujesz się swobodnie i chętnie zagłębiasz się w literaturę badawczą, przyjrzałbym się pracom Jianqing Fan i Jinchi Lv, którzy wykonali większość fundamentalnych prac nad problemami ultra-wymiarowymi. („Badanie przesiewowe” to dobry termin do wyszukiwania)

[F1] Właściwie dowolna subgaussowska zmienna losowa, ale to nie dodaje zbyt wiele do tej dyskusji.

[F2] Możemy również ustawić, że „prawdziwa” rzadkość zależy od ( ), ale to nie zmienia zbyt wiele rzeczy.sns=g(n)

[F3] T. Hastie, R. Tibshirani i M. Wainwright. Nauka statystyczna ze rzadkością. Monografie dotyczące statystyki i prawdopodobieństwa stosowanego 143. CRC Press, 2015. Dostępne do pobrania za darmo na https://web.stanford.edu/~hastie/StatLearnSparsity_files/SLS.pdf

[BRT] Peter J. Bickel, Ya'acov Ritov i Alexandre B. Tsybakov. „Jednoczesna analiza Selektora Lasso i Dantzig”. Annals of Statistics 37 (4), s. 1. 1705-1732, 2009. http://dx.doi.org/10.1214/08-AOS620

mweylandt
źródło
1
(+1) Dzięki, jest to bardzo pomocne i naprawdę godne nagrody (poczekam chwilę przed przyznaniem nagrody, aby utrzymać zainteresowanie). Jedno pytanie: czy możesz rozwinąć więcej w „ pozostaje stały, stąpamy po wodzie”? Czy to ważne, czy ta stała jest większa niż 1 czy mniejsza niż 1? logp/n
Greenparker
Jasne - dodałem małe badanie symulacyjne w celu wyjaśnienia dynamiki „bieżnika po wodzie”. Pod względem asymptotycznej dynamiki nie ma znaczenia, co to jest stała, ale błąd będzie proporcjonalny do tej stałej, więc oczywiście wolałby mniejszy ceteris paribus (jest to równoważne z posiadaniem większej liczby co zawsze jest dobrą rzeczą) . n
mweylandt