Frage:
Was sind die Softwareeinschränkungen bei allen möglichen Teilmengenauswahlen in der Regression?
Levon
2011-03-01 09:09:40 UTC
view on stackexchange narkive permalink

Wenn ich eine abhängige Variable und $ N $ Prädiktorvariablen habe und möchte, dass meine Statistiksoftware alle möglichen Modelle untersucht, gibt es $ 2 ^ N $ mögliche resultierende Gleichungen.

Ich bin gespannt, welche Einschränkungen in Bezug auf $ N $ für wichtige / beliebte Statistiksoftware bestehen, da es mit zunehmender Größe von $ N $ zu einer kombinatorischen Explosion kommt.

I. Ich habe mich auf den verschiedenen Webseiten nach Paketen umgesehen, konnte diese Informationen jedoch nicht finden. Ich würde einen Wert von 10 - 20 für $ N $ vermuten?

Wenn jemand weiß (und Links hat), wäre ich für diese Informationen dankbar.

Abgesehen von R, Minitab, Ich kann mir diese Pakete SAS, SPPS, Stata, Matlab, Excel (?) Und alle anderen Pakete vorstellen, die ich in Betracht ziehen sollte?

@levon9 Diese Frage hat viele fundierte Antworten und Kommentare generiert, sodass ich +1 habe. Aber bitte vergessen Sie Excel, um ernsthafte Arbeit bei der Modellauswahl zu leisten ...
@levon9 - Ich konnte alle möglichen Teilmengen mit 50 Variablen in SAS generieren. Ich glaube nicht, dass es eine andere harte Einschränkung als Speicher und CPU-Geschwindigkeit gibt.-Ralph Winters
Für welche Größe des Datensatzes?
Vielen Dank sehr nützliche Informationen. Nur neugierig, hat das lange gedauert?
@chl .. ist das, weil Excel langsam oder einfach unfähig ist (dh ungenaue Ergebnisse liefern würde?).
@levon9, @chl Excel ist (im Prinzip) in der Lage, Modellauswahlalgorithmen korrekt zu implementieren. Das ist nicht sofort möglich. Hat jemand ein bestimmtes Add-In im Sinn?
@levon9 @whuber Mein Punkt zu Excel bezog sich nicht auf seine Leistung (die ich in diesem speziellen Fall nicht kenne), sondern lediglich auf "bessere" Software, die integrierte Tools für Modellbildung, Auswahl, Diagnose bietet (und ja, ich Ich muss zugeben, dass ich zu diesem Zweck ein bisschen voreingenommen gegenüber R oder Stata bin.
Vier antworten:
#1
+12
cardinal
2011-03-01 09:19:54 UTC
view on stackexchange narkive permalink

Ich vermute, 30-60 ist ungefähr das Beste, was Sie bekommen werden. Der Standardansatz ist der leaps-and-bounds -Algorithmus, bei dem nicht jedes mögliche Modell angepasst werden muss. In $ R $ ist das Paket Sprünge eine Implementierung.

Die Dokumentation für die Funktion regsubsets in leaps Paket gibt an, dass es bis zu 50 Variablen verarbeiten kann, ohne sich zu beschweren. Es kann "gezwungen" werden, mehr als 50 zu tun, indem das entsprechende boolesche Flag gesetzt wird.

Mit einer Parallelisierungstechnik können Sie vielleicht etwas besser abschneiden, aber die Anzahl der Gesamtmodelle, die Sie berücksichtigen können, wird (fast zweifellos) Skalieren Sie nur linear mit der Anzahl der verfügbaren CPU-Kerne. Wenn also 50 Variablen die Obergrenze für einen einzelnen Kern sind und Sie über 1000 Kerne verfügen, können Sie diese auf etwa 60 Variablen erhöhen.

** Sprünge ** ist großartig, ich mag die Handlungen davon, +1. In realen Anwendungen arbeiten einige Mittelungstechniken schneller (und besser) als vorgetestete Schätzer, die selbst aus allen Regressionsmodellen stammen. Daher würde ich vorschlagen, die Bayes'sche Modellmittelung (BMA-Paket) oder den Algorithmus zu wählen, den ich am meisten mag - gewichtete durchschnittliche kleinste Quadrate (WALS [1]), entwickelt von J. R. Magnus et al. Der Matlab-Code kann leicht in R-Code umgewandelt werden. Das Gute für WALS ist $ N $ Rechenschwierigkeit anstelle von $ 2 ^ N $. [1]: http://www.tilburguniversity.edu/research/institutes-and-research-groups/center/staff/magnus/wals/
@Dmitrij, danke für deine Kommentare. Ich habe versucht, in meiner Antwort bezüglich des Nutzens der Regression aller Teilmengen ziemlich agnostisch zu bleiben. Es scheint mir, dass es fast immer eine bessere Lösung gibt, aber ich hatte das Gefühl, dass eine Antwort auf die Frage des OP zu banal erscheint.
@Dmitrij, BMA über Haupteffektmodelle hätte immer noch die gleiche Rechenkomplexität wie die Regression aller Teilmengen. Nein? Der Hauptvorteil von BMA scheint mir darin zu liegen, herauszufinden, welche Kovariaten die Reaktion wahrscheinlich beeinflussen. BMA tut dies, indem es im Wesentlichen die Protokollwahrscheinlichkeiten über $ 2 ^ {n-1} $ Submodelle mittelt.
Danke für den Hinweis auf das leaps R-Paket! Ich wusste nichts davon und es könnte sich in Zukunft als nützlich erweisen. Wenn ich Informationen zu bestimmten Einschränkungen für N für andere beliebte Pakete erhalten könnte, wäre dies sehr hilfreich.
@levon9, Ich bezweifle, dass es je nach Paket sehr unterschiedlich sein wird. Der Algorithmus, den ** springt **, ist seit mindestens 20 Jahren auf dem neuesten Stand der Technik. Selbst wenn Sie eine Implementierung finden würden, die * doppelt * so schnell ist, würde dies bedeuten, dass Sie die Anzahl der Variablen, die Sie verarbeiten können, um eins erhöhen müssen. Für jede Verdoppelung der Geschwindigkeit erhalten Sie eine weitere Variable. Hardware, nicht algorithmische Einschränkungen, sind in diesem Fall Ihr Engpass.
@cardinal, genau, BMA hat den gleichen Nachteil der Rechenkomplexität wie die Regression aller Teilmengen (in Eviews wird es als kombinatorischer Ansatz bezeichnet ^ _ ^). Aus diesem Grund schätze ich WALS mehr, da beide die Kovariaten gewichten, schneller und nützlich sind, wenn wir * Fokus * -Parameter (gewichteter Schätzer hat einen kleineren * Vorspann * Bias) und Parameter haben, die zu Hilfsvariablen gehören, die wir nicht sind sicher über und, ja, es löst die Probleme, die @Dikran in seinem Beitrag erwähnt hat. Fokusvariablen basieren auf der Theorie (kein Raum, um falsch oder überanpassend zu werden). Ein großer Informationssatz bekämpft das Vorspannungsproblem vor dem Test gut.
#2
+10
Dikran Marsupial
2011-03-01 19:01:36 UTC
view on stackexchange narkive permalink

Nur eine Einschränkung, aber die Auswahl von Features ist ein riskantes Geschäft. Je mehr Features Sie haben, desto mehr Freiheitsgrade haben Sie, um das Kriterium der Feature-Auswahl zu optimieren, und desto größer ist das Risiko einer Überanpassung des Features Auswahlkriterium und erhalten so ein Modell mit schlechter Generalisierungsfähigkeit. Es ist möglich, dass Sie mit einem effizienten Algorithmus und sorgfältiger Codierung alle Teilmengen mit einer großen Anzahl von Funktionen auswählen können. Dies bedeutet jedoch nicht, dass dies eine gute Idee ist, insbesondere wenn Sie relativ wenige Beobachtungen haben. Wenn Sie die Auswahl aller Teilmengen verwenden, ist es wichtig, das gesamte Modellanpassungsverfahren ordnungsgemäß zu validieren (damit die Auswahl aller Teilmengen in jeder Falte der Kreuzvalidierung unabhängig durchgeführt wird). In der Praxis übertrifft die Gratregression ohne Merkmalsauswahl häufig die lineare Regression mit der Merkmalsauswahl (dieser Rat wird in Millars Monographie zur Merkmalsauswahl gegeben).

@Dikran, (+1) gute Kommentare. Ich habe versucht, es zu vermeiden, dorthin zu gehen, da es die Frage des OP nicht direkt ansprach. Aber ich stimme zu. All-Subsets sind selten der richtige Weg. Und wenn Sie diesen Weg gehen, müssen Sie alle Auswirkungen verstehen.
@Dirkan danke für die Kommentare, ich bin ein echter Statistik-Neuling. Ich erkenne die Gefahr einer Überanpassung des Modells, wenn zu viele Variablen im Spiel sind, und betrachte daher nur verschiedene automatisierte Methoden (dh ohne großen Nutzen von Einsichten) wie den schrittweisen Ansatz (der sich in lokalen Maxima verfangen könnte) und den Vollständiges Modell aller Teilmengen - und die damit verbundenen Rechengrenzen (und die durch Pakete auferlegten externen Einschränkungen)
@levon9, kann zu einer Überanpassung führen, die bei der Auswahl der Features genauso schwerwiegend ist, sodass die Feature-Auswahl nicht vor einer Überanpassung schützt. Stellen Sie sich ein logistisches Regressionsmodell vor, mit dem das Ergebnis des Werfens einer fairen Münze vorhergesagt wird. Die potenziellen Inputs sind das Ergebnis des Umwerfens einer großen Anzahl anderer fairer Münzen. Einige dieser Eingaben werden positiv mit dem Ziel korreliert, sodass das beste Modell für alle Teilmengen Eingaben auswählt (obwohl sie unbrauchbar sind) und Sie ein Modell erhalten, das anscheinend über Fähigkeiten verfügt, in Wirklichkeit jedoch nicht besser ist als zu raten.
@Dikran (+1) das gleiche wie @cardinal, Ich schrieb zuerst einen ähnlichen Text, entschied dann aber, dass es nicht das ist, was @levon9 fragte, weil er einfach neugierig auf die Komplexität war :)
@Dikran +1, weil ich solche Ratschläge mag.
@Dikran bedankt sich für die zusätzlichen Klarstellungen / Kommentare - und entschuldigt sich für den Tippfehler früher mit Ihrem Namen.
#3
+4
Ralph Winters
2011-03-01 20:56:20 UTC
view on stackexchange narkive permalink

Ich konnte alle möglichen Teilmengen mit 50 Variablen in SAS generieren. Ich glaube nicht, dass es eine andere harte Einschränkung als die Speicher- und CPU-Geschwindigkeit gibt.

Bearbeiten

Ich habe die 2 besten Modelle für N = 1 bis 50 Variablen für 5000 Beobachtungen generiert.

@ levon9 - Nein, dies dauerte weniger als 10 Sekunden. Ich habe 50 Zufallsvariablen aus (0,1)

-Ralph Winters

generiert
Für welche Größe des Datensatzes?
Vielen Dank sehr nützliche Informationen. Nur neugierig, hat das lange gedauert?
Ich habe diesen Beitrag nicht gelöscht (und einen weiteren Ihrer Kommentare in einer Bearbeitung zusammengeführt), weil das OP ihn nützlich fand und andere möglicherweise auch. Danke für Ihren Beitrag; Mach bitte weiter so! (Wenn Sie wirklich der Meinung sind, dass es gelöscht werden sollte, machen Sie es einfach; ich werde Ihren Wünschen nicht noch einmal widersprechen.)
Anscheinend verwenden Sie zwei verschiedene nicht registrierte Konten. Ich habe sie zusammengeführt, aber Sie müssen sich noch registrieren.
#4
+3
probabilityislogic
2011-03-01 16:17:03 UTC
view on stackexchange narkive permalink

Wenn $ N $ groß wird, wird Ihre Fähigkeit, Mathematik zu verwenden, absolut entscheidend. "Ineffiziente" Mathematik kostet Sie am PC. Die Obergrenze hängt davon ab, welche Gleichung Sie lösen. Das Vermeiden von inversen oder determinanten Matrixberechnungen ist ein großer Vorteil.

Eine Möglichkeit, die Grenze zu erhöhen, besteht darin, Theoreme zum Zerlegen einer großen inversen Matrix in kleinere Matrixinverse zu verwenden. Dies kann oft den Unterschied zwischen machbar und nicht machbar bedeuten. Dies erfordert jedoch harte Arbeit und oft recht komplizierte mathematische Manipulationen! Aber normalerweise ist es die Zeit wert. Rechnen Sie nach oder nehmen Sie sich Zeit!

Bayesianische Methoden können möglicherweise einen alternativen Weg bieten, um Ihr Ergebnis zu erzielen - möglicherweise schneller, was bedeutet, dass sich Ihre "Obergrenze" erhöht (schon allein, weil es Ihnen gibt Zwei alternative Methoden zur Berechnung derselben Antwort - die kleinere von zwei ist immer kleiner als eine davon!).

Wenn Sie einen Regressionskoeffizienten berechnen können, ohne eine Matrix zu invertieren, speichern Sie wahrscheinlich a viel Zeit. Dies kann im Bayes'schen Fall besonders nützlich sein, da "innerhalb" eines normalen Marginalisierungsintegrals die $ X ^ {T} X $ -Matrix nicht invertiert werden muss, sondern nur eine Summe von Quadraten berechnet wird. Ferner wird die Determinantenmatrix Teil der Normalisierungskonstante sein. "Theoretisch" könnten Sie also Stichprobenverfahren verwenden, um das Integral numerisch zu bewerten (obwohl es einen analytischen Ausdruck hat), was Äonen schneller ist als der Versuch, die "kombinatorische Explosion" von Matrixinversen und -determinanten zu bewerten. (Es wird immer noch eine "kombinatorische Explosion" numerischer Integrationen sein, aber dies kann schneller gehen.)

Dieser Vorschlag oben ist eine Art "Gedankenblase" von mir. Ich möchte es tatsächlich testen, um zu sehen, ob es etwas Gutes ist. Ich denke, es wäre (5.000 Simulationen + Exp berechnen (Summe der Quadrate) + Berechnen des gewichteten durchschnittlichen Beta sollte schneller sein als die Matrixinversion für eine ausreichend große Matrix.)

Die Kosten sind eher ungefähre als genaue Schätzungen. Nichts hindert Sie daran, denselben Satz von Pseudozufallszahlen zur numerischen Auswertung des Integrals zu verwenden, was wiederum viel Zeit spart.

Es hindert Sie auch nichts daran, eine Kombination zu verwenden von beiden Techniken. Verwenden Sie genau, wenn die Matrizen klein sind, verwenden Sie die Simulation, wenn sie groß sind. Dies liegt daran, dass in diesem Teil der Analyse. Es sind nur verschiedene numerische Techniken - wählen Sie einfach die Technik aus, die am schnellsten ist!

Natürlich sind dies alles nur ein paar "handgewellte" Argumente, ich kenne nicht genau die besten Softwarepakete, die verwendet werden können - und schlimmer noch, versuchen herauszufinden, welche Algorithmen sie tatsächlich verwenden.

@probabilityislogic, Während Ihre Antwort interessant ist, könnte sie möglicherweise neu ausgerichtet werden, um die Frage des OP besser zu beantworten. Außerdem führt *** no *** Software zur Berechnung von Lösungen der kleinsten Quadrate eine Matrixinversion durch, geschweige denn eine Determinante. Je. Es sei denn, es wird eine $ 1 \ mal 1 $ -Matrix invertiert.
@probabilityislogic,, das die $ 2 ^ n $ -Fälle effizient und schnell behandelt, übertrifft die $ O (n ^ 3) $ -Probleme einer effizienten Lösung der kleinsten Quadrate bei weitem. Hier kommt der * leaps-and-bounds * -Algorithmus ins Spiel.
Danke für den Beitrag. "Mach die Mathe oder mach die Zeit!" :-) .. Ich versuche eigentlich nicht einmal, die zugrunde liegenden Algorithmen herauszufinden, die von den Paketen verwendet werden (das ist interessant zu wissen), und suche an dieser Stelle wirklich nach spezifischen Informationen bezüglich der Einschränkungen von N durch die Hauptpakete.
@cardinal Die Aktualisierungs- und Downdating-Algorithmen existieren auch für verschiedene Matrixzerlegungsverfahren. Ich vermute, dass dies mit "Matrixinverse" usw. gemeint war.
@Dikran, Es gibt mehrere effiziente und numerisch stabile Ansätze für kleinste Quadrate, einschließlich Methoden zum Erweitern oder Reduzieren einer Entwurfsmatrix um jeweils eine Spalte. Manchmal ist es gut zu verstehen, was unter der Oberfläche passiert, auch wenn Sie sich an den meisten Tagen nicht darum kümmern müssen.
@cardinal - Ich bin gespannt auf Ihren Kommentar zu "kleinsten Quadraten", die niemals eine Matrixinversion durchführen. Die Hauptgleichung für die Schätzungen lautet $ \ beta = (X ^ {T} X) ^ {- 1} X ^ {T} Y $. Ferner ist die Varianz dieser Schätzungen durch $ \ sigma ^ {2} (X ^ {T} X) ^ {- 1} $ gegeben. Die inverse Matrix ist zumindest in der Mathematik grundlegend für die typische Regression der kleinsten Quadrate. Obwohl ich meine Unwissenheit in den tatsächlich berechneten Berechnungsverfahren zeige.
@probabilityislogic, Ein üblicher Ansatz ist die Verwendung (einer Variante davon) einer $ QR $ -Zerlegung. Wir schreiben also $ X = Q R $, wobei $ Q $ eine Matrix mit orthogonalen Spalten und $ R $ eine quadratische Dreiecksmatrix ist. Es ist leicht zu erkennen, dass die Residuen als $ \ hat {y} = QQ ^ T y $ geschrieben werden können und die Parameterschätzungen die Lösung sind, sodass das dreieckige Gleichungssystem $ R \ hat {\ beta} = Q ^ T ist y $. Dreieckssysteme sind sehr effizient zu lösen. Die $ Q R $ -Zerlegung unter Verwendung von Householder-Reflexionen oder Givens-Rotationen ist numerisch sehr stabil. Keine Matrixinversion erforderlich.
@cardinal - danke dafür. Ich nehme an, meine "Gedankenblase" reduziert sich auf den Vergleich der QR-Zerlegungsgeschwindigkeit mit der numerischen Integration
Die @probabilityislogic, $ QR $ -Zerlegung sollte niemals schlechter als $ O (n p ^ 2) $ sein, und dies liefert eine genaue Antwort (mit numerischer Genauigkeit). Um dies mit der Monte-Carlo-Integration zu vergleichen, müssten Sie mindestens ein paar Begriffe der gewünschten Präzision angeben.
@cardinal - Ich würde vorschlagen, dass die MC-Methode je nach erforderlicher Genauigkeit "vergrößert" (mehr Simulationen) oder "verkleinert" (weniger) werden kann. Mit der QR-Methode bleiben Sie, obwohl genau, bis zu einem gewissen Grad bei gleicher Rechenzeit hängen. Bei so etwas wie der Regression aller Teilmengen ist die Genauigkeit der Antwort möglicherweise nicht die Priorität Nummer eins. Noch einmal, wenn Sie zwei Methoden haben - eine davon ist schneller. Die Erweiterung meiner Gedankenblase würde darin bestehen, welche Bedingungen erforderlich sind, damit eine Methode schneller als die andere ist - und zu welchen Kosten.
@probabilityislogic, das Problem ist immer noch, dass die $ O (2 ^ n) $ Arbeit für alle Teilmengen viel größer ist als die $ O (n p ^ 2) $ Arbeit einer $ QR $ Zerlegung. Im Fall $ QR $ können möglicherweise nur einfache Aktualisierungen mit einem Rang vorgenommen werden, um die Parameterschätzungen für kleinere Modelle zu finden, sobald die anfänglichen Schätzungen der vollständigen Regression erhalten wurden. Diese Rang-1-Updates sind schnell. Für alle Teilmengen müsste jedoch * jede * Kombination solcher Aktualisierungen vorgenommen werden. Ihre Methode würde eine Neuschätzung des Integrals jedes Mal erfordern, wenn sich $ X $ ändert, und ist nicht genau. Ich würde eine Vermutung wagen, dass das weit weniger effizient ist.
@cardinal - man müsste das numerische Integral nicht "neu schätzen". Sie ignorieren einfach die hinteren Stichproben für die Teile des Modells, die ausgeschlossen werden. Sie benötigen nur eine Simulation aus dem vollständigen Modell, und es sind keine Aktualisierungen für Rang 1 erforderlich. Hier werden Sie meiner Meinung nach viel Zeit sparen. Eine solche Frage könnte lauten: "Ist $ \ beta_j $ für mein Modell relevant, * unabhängig davon, welche anderen Parameter im Modell enthalten sind? *". Sehr schnell, um dies zu entscheiden - schauen Sie sich einfach die simulierte Randverteilung für $ \ beta_j $ an.
@cardinal - Wenn Sie zu meinem obigen Punkt hinzufügen, nehmen wir an, Sie haben einen "Ablehnungsbereich", z. $ \ frac {| \ beta_j |} {SE (\ beta_j)} \ leq 1 $, die Sie bereit sind zu deklarieren, dass der Koeffizient "Null" ist, und ihn aus dem Modell entfernen. Dann reduziert sich die Regression von $ 2 ^ n $ all Teilmengen auf den simulierten Datensatz auf das Problem einer n-Wege-Kontingenztabelle. Jeder Weg hat zwei Ergebnisse - in der Region oder nicht. Die "besten Modelle" haben die höchste Wahrscheinlichkeit in dieser Tabelle
@probabilityislogic, Ihre Kommentare haben wirklich nichts mit der Regression aller Teilmengen zu tun, und ich würde nicht versuchen, sie in dieses Framework zu zwingen. Sie scheinen mehr mit * Modellauswahl * in der Regression zu tun zu haben. Es gibt eine Vielzahl solcher Methoden, sowohl klassische als auch moderne, einschließlich Schwellenwertansätzen wie dem von Ihnen beschriebenen. Das Lasso ist ein Beispiel und hat sogar eine Bayes'sche Interpretation. Normalerweise benötigen Sie eine Bedingung nahe der Orthogonalität der Entwurfsmatrix, um eine gute Leistung zu gewährleisten (auch asymptotisch!).


Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 2.0-Lizenz, unter der er vertrieben wird.
Loading...