Ich versuche, mich über die Forschung im Bereich der hochdimensionalen Regression zu informieren. wenn größer als ist, ist das . Es scheint, als würde der Begriff häufig als Konvergenzrate für Regressionsschätzer verwendet.n p > > n log p / n
Zum Beispiel hier die Gleichung (17) sagt , dass das lasso fit, erfüllt 1
Normalerweise impliziert dies auch, dass kleiner als .
- Gibt es eine Ahnung, warum dieses Verhältnis von so bedeutend ist?
- Aus der Literatur geht auch hervor, dass das hochdimensionale Regressionsproblem kompliziert wird, wenn . Wieso ist es so?
- Gibt es eine gute Referenz, die die Probleme bespricht, wie schnell und im Vergleich zueinander wachsen sollten?
regression
lasso
convergence
high-dimensional
Greenparker
quelle
quelle
Antworten:
(Von Kommentaren zu einer Antwort verschoben, wie von @Greenparker angefordert)
Teil 1)
Der Term stammt aus der (Gaußschen) Maßkonzentration. Insbesondere wenn Sie IID Gaußsche Zufallsvariablen [F1] haben, liegt ihr Maximum mit hoher Wahrscheinlichkeit in der Größenordnung von . pσ √Logp----√ p σLogp----√
Der Faktor ergibt sich aus der Tatsache, dass Sie den durchschnittlichen Vorhersagefehler betrachten - dh, er stimmt mit dem Faktor auf der anderen Seite überein -, wenn Sie den Gesamtfehler betrachten, wäre er nicht vorhanden. n - 1n- 1 n- 1
Teil 2)
Im Wesentlichen müssen Sie zwei Kräfte steuern:
In der klassischen Statistik fixieren wir und lassen ins Unendliche: Dieses Regime ist für die hochdimensionale Theorie nicht besonders nützlich, da es (asymptotisch) konstruktionsbedingt im niedrigdimensionalen Regime liegt .np n
Alternativ könnten wir ins Unendliche gehen lassen und fest bleiben, aber dann explodiert unser Fehler, da das Problem im Wesentlichen unmöglich wird. Abhängig vom Problem kann der Fehler ins Unendliche gehen oder an einer natürlichen Obergrenze enden ( z. B. 100% Fehlklassifizierungsfehler).np n
Da diese beiden Fälle etwas nutzlos sind, betrachten wir stattdessen beide als unendlich, so dass unsere Theorie beide relevant ist (hochdimensional bleibt), ohne apokalyptisch zu sein (unendliche Merkmale, endliche Daten).n , p
Zwei "Knöpfe" zu haben, ist im Allgemeinen schwieriger als ein einziger Knopf, also setzen wir für ein festes und lassen gegen unendlich gehen (und daher geht indirekt gegen unendlich). [F2] Die Wahl von bestimmt das Verhalten des Problems. Aus Gründen in meiner Antwort auf Teil 1 stellt sich heraus, dass die "Bösartigkeit" der zusätzlichen Funktionen nur als wächst, während die "Güte" der zusätzlichen Daten als wächst .f n p f log p np = f( n ) f n p f Logp n
Dieses letzte Regime wird in der Literatur manchmal als "ultrahochdimensional" bezeichnet. Der Begriff "ultrahochdimensional" hat meines Wissens keine strenge Definition, aber es ist informell nur "das Regime, das das Lasso und ähnliche Schätzer durchbricht".
Wir können dies mit einer kleinen Simulationsstudie unter ziemlich idealisierten Bedingungen demonstrieren. Hier nehmen wir eine theoretische Anleitung zur optimalen Auswahl von aus [BRT09] und wählen .λ = 3 √λ λ = 3 log( p ) / n-------√
Betrachten Sie zunächst einen Fall mit . Dies ist in dem oben beschriebenen 'traktierbaren' hochdimensionalen Regime und wie die Theorie vorhersagt, sehen wir, dass der Vorhersagefehler gegen Null konvergiert:p = f( n ) = 3 n
Zu reproduzierender Code:
Wir können dies mit dem Fall vergleichen, in dem ungefähr konstant bleibt: Ich nenne dies das ultrahochdimensionale "Grenzregime", aber das ist kein Standardbegriff:Logpn
Hier sehen wir, dass der Vorhersagefehler (unter Verwendung des gleichen Designs wie oben) abfällt, anstatt auf Null zu bleiben.
Setzt man , schneller zu wachsen als , ( zB , ), die Vorhersagefehler zunimmt , ohne Schranke. Diese ist lächerlich schnell und führt zu enormen Problemen / numerischen Problemen, daher hier ein etwas langsameres, aber immer noch UHD-Beispiel:P en en2 en2
(Ich habe ein spärliches zufälliges für die Geschwindigkeit verwendet, also versuche nicht, die Zahlen direkt mit den anderen Darstellungen zu vergleichen.) In diesem Diagramm ist kaum ein Anstieg zu erkennen, vielleicht, weil wir das UHD-Wachstum nicht zu "ultra" in der Grafik dargestellt haben Name der Rechenzeit. Die Verwendung eines größeren Exponenten (wie ) würde das asymptotische Wachstum etwas deutlicher machen.X en1.5
Ungeachtet dessen, was ich oben gesagt habe und wie es aussehen mag, ist das ultrahochdimensionale Regime nicht wirklich völlig hoffnungslos (obwohl es eng ist), aber es erfordert viel ausgefeiltere Techniken als nur ein einfaches Maximum von Gaußschen Zufallsvariablen, um den Fehler zu kontrollieren. Die Notwendigkeit, diese komplexen Techniken anzuwenden, ist die ultimative Quelle für die Komplexität, die Sie feststellen.
Es gibt keinen besonderen Grund zu der Annahme, dass in irgendeiner Weise "zusammenwachsen" sollte ( dh es gibt keinen offensichtlichen "realen" Grund, zu beheben ), aber Mathematik fehlen im Allgemeinen Sprache und Werkzeuge zur Diskussion Grenzen mit zwei "Freiheitsgraden", also ist es das Beste, was wir tun können (fürs Erste!).p , n p = f( n )
Teil 3)
Ich kenne leider keine Bücher in der statistischen Literatur, die sich wirklich explizit mit dem Wachstum von vs befassen. (Möglicherweise ist etwas in der Literatur zu Drucksensoren enthalten.)Logp n
Meine derzeitige Lieblingsreferenz für diese Art von Theorie sind die Kapitel 10 und 11 des Statistischen Lernens mit Sparsity [F3], aber es wird im Allgemeinen der Ansatz verfolgt, festzuhalten und (nicht asymptotische) Eigenschaften mit endlicher Stichprobe zu erhalten, um ein "Gut" zu erhalten "Ergebnis. Dies ist tatsächlich ein leistungsfähigerer Ansatz - sobald Sie das Ergebnis für ein beliebiges , ist es einfach, die Asymptotik zu betrachten -, aber diese Ergebnisse sind im Allgemeinen schwieriger abzuleiten, sodass wir sie derzeit nur für Schätzer vom Lasso-Typ haben, soweit ich weiß kennt.n , p n , p
Wenn Sie sich wohlfühlen und bereit sind, sich mit Forschungsliteratur zu befassen, schaue ich mir Werke von Jianqing Fan und Jinchi Lv an, die den größten Teil der grundlegenden Arbeit an ultrahochdimensionalen Problemen geleistet haben. ("Screening" ist ein guter Suchbegriff)
[F1] Eigentlich jede subgaußsche Zufallsvariable, aber das fügt dieser Diskussion nicht viel hinzu.
[F2] Wir könnten auch die "wahre" Sparsity einstellen , dass sie von abhängt ( ), aber das ändert die Dinge nicht allzu sehr.s n s = g( n )
[F3] T. Hastie, R. Tibshirani und M. Wainwright. Statistisches Lernen mit Sparsamkeit. Monographien zu Statistik und angewandter Wahrscheinlichkeit 143. CRC Press, 2015. Abrufbar unter https://web.stanford.edu/~hastie/StatLearnSparsity_files/SLS.pdf
[BRT] Peter J. Bickel, Ya'acov Ritov und Alexandre B. Tsybakov. "Simultane Analyse von Lasso und Dantzig Selector." Annals of Statistics 37 (4), p. 1705-1732, 2009. http://dx.doi.org/10.1214/08-AOS620
quelle