Regresja wielowymiarowa: dlaczego wyjątkowy?

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.$p$$n$$p >> n$$\log p/n$

Na przykład tutaj równanie (17) mówi, że dopasowanie lasso, $\hat{\beta}$ spełnia

Zwykle oznacza to również, że $\log p$ powinien być mniejszy niż $n$ .

1. Czy jest jakaś intuicja, dlaczego ten stosunek $\log p/n$ jest tak znaczący?
2. Również z literatury wydaje się, że problem regresji wielowymiarowej komplikuje się, gdy $\log p \geq n$ . 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?

(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σ$\sqrt{\log p}$$p$$\sigma\sqrt{\log p}$

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 - $n^{-1}$$n^{-1}$

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ę .$p$$n$

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).$p$$n$

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 $p=f(n)$$f$$n$$p$$f$$\log p$$n$

• 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)$\frac{\log p}{n}$$p=f(n)=Θ(C^n)$$C$
• jeśli ( ) asymptotycznie osiągamy zero błędów;p=o(Cn$\frac{\log p}{n} \to 0$$p=o(C^n)$
• a jeśli ( ), błąd ostatecznie przechodzi w nieskończoność.p=ω(Cn$\frac{\log p}{n}→\infty$$p=\omega(C^n)$

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 $\lambda$$\lambda = 3 \sqrt{\log(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$

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:$\frac{\log p}{n}$

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.

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:$P$$e^n$$e^{n^2}$$e^{n^2}$

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

(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.$X$$e^{n^1.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, n$$p = 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ś)$\log p$$n$

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, p$$n, 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.$s$$n$$s = 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