Domanda:
Quali sono i limiti del software in tutte le possibili selezioni di sottoinsiemi nella regressione?
Levon
2011-03-01 09:09:40 UTC
view on stackexchange narkive permalink

Se ho una variabile dipendente e variabili predittive $ N $ e volevo che il mio software di statistica esaminasse tutti i modelli possibili, ci sarebbero $ 2 ^ N $ possibili equazioni risultanti.

Sono curioso di scoprire quali sono i limiti per quanto riguarda $ N $ per i principali / popolari software di statistica poiché quando $ N $ diventa grande c'è un'esplosione combinatoria.

I ho sfogliato le varie pagine web per i pacchetti ma non sono riuscito a trovare queste informazioni. Sospetto un valore di 10 - 20 per $ N $?

Se qualcuno lo sa (e ha collegamenti) sarei grato per questa informazione.

A parte R, Minitab, Mi vengono in mente questi pacchetti SAS, SPPS, Stata, Matlab, Excel (?), Altri pacchetti che dovrei considerare?

@levon9 Questa domanda ha generato molte risposte e commenti validi, così ho fatto +1. Ma, per favore, dimentica Excel per fare un lavoro serio nella selezione del modello ...
@levon9 - Sono stato in grado di generare tutti i possibili sottoinsiemi utilizzando 50 variabili in SAS. Non credo che ci siano limiti rigidi oltre alla memoria e alla velocità della CPU.-Ralph Winters
Per quale dimensione del set di dati?
Grazie informazioni molto utili. Sono solo curioso, ci è voluto molto tempo?
@chl .. è perché Excel è lento o semplicemente incapace (cioè darebbe risultati imprecisi?).
@levon9, @chl Excel è (in linea di principio) in grado di implementare correttamente gli algoritmi di selezione del modello. Non lo fa fuori dagli schemi. Qualcuno ha in mente un particolare componente aggiuntivo?
@levon9 @whuber Il mio punto su Excel non era correlato alle sue prestazioni (che non conosco in questo caso particolare) ma era semplicemente per indicare un software "migliore" che fornisce strumenti integrati per la creazione di modelli, la selezione, la diagnostica (e sì io devo ammettere che sono un po 'sbilanciato verso R o Stata per quello scopo).
Quattro risposte:
cardinal
2011-03-01 09:19:54 UTC
view on stackexchange narkive permalink

Sospetto che 30-60 sia il massimo che otterrai. L'approccio standard è l'algoritmo passi da gigante che non richiede l'adattamento di ogni modello possibile. In $ R $, il pacchetto leaps è un'implementazione.

La documentazione per la funzione regsubsets nel salti afferma che gestirà fino a 50 variabili senza lamentarsi. Può essere "forzato" a fare più di 50 impostando il flag booleano appropriato.

Potresti fare un po 'meglio con qualche tecnica di parallelizzazione, ma il numero di modelli totali che puoi considerare lo farà (quasi senza dubbio) scalare linearmente solo con il numero di core della CPU disponibili. Quindi, se 50 variabili è il limite superiore per un singolo core e hai 1000 core a tua disposizione, potresti portarlo a circa 60 variabili.

** salti ** è fantastico, mi piacciono le trame, +1. Nelle applicazioni reali alcune tecniche di calcolo della media funzionano più velocemente (e meglio) degli stimatori pretestati trovati anche da tutti i modelli di regressione. Quindi suggerirei di utilizzare la media del modello bayesiano (pacchetto BMA) o l'algoritmo che mi piace di più - Minimi quadrati medi pesati (WALS [1]) sviluppato da J.R. Magnus et al. Il codice Matlab è facilmente trasformabile in codice R. La cosa buona per WALS è la difficoltà di calcolo $ N $ invece di $ 2 ^ N $. [1]: http://www.tilburguniversity.edu/research/institutes-and-research-groups/center/staff/magnus/wals/
@Dmitrij, grazie per i tuoi commenti. Ho cercato di rimanere abbastanza agnostico nella mia risposta sull'utilità della regressione di tutti i sottoinsiemi. Mi sembra che ci sia quasi sempre una soluzione migliore, ma ho sentito che potrebbe sembrare una risposta troppo banale alla domanda dell'OP.
@Dmitrij, BMA rispetto ai modelli con effetti principali avrebbe ancora la stessa complessità computazionale della regressione di tutti i sottoinsiemi. No? Il vantaggio principale in BMA mi sembra essere nel cercare di capire quali covariate potrebbero influenzare la risposta. BMA fa ciò essenzialmente calcolando la media delle probabilità di log su sottomodelli $ 2 ^ {n-1} $.
Grazie per il puntatore al pacchetto R di salti! Non lo sapevo e potrebbe tornare utile in futuro. Se potessi ottenere alcune informazioni su limitazioni specifiche per N per altri pacchetti popolari, sarebbe molto utile.
@levon9, Dubito che varierà molto in base al pacchetto. L'algoritmo utilizzato da ** salti ** è all'avanguardia da almeno 20 anni circa. Anche se hai trovato un'implementazione * due volte * più veloce, ciò significherebbe che devi aumentare il numero di variabili che puoi gestire di uno. Per ogni raddoppio della velocità, ottieni una variabile in più. Le limitazioni hardware, non algoritmiche, sono il tuo collo di bottiglia in questo caso.
@cardinal, esattamente, BMA ha lo stesso svantaggio di complessità computazionale della regressione di tutti i sottoinsiemi (in Eviews è chiamato approccio combinatorio ^ _ ^). È per questo che apprezzo di più WALS, poiché entrambi pesa le covariate, è più veloce ed è utile se abbiamo parametri * focus * (lo stimatore ponderato ha bias * pre-test * più piccoli) e parametri che vanno a variabili ausiliarie che non lo siamo certo e, sì, risolve i problemi menzionati da @Dikran nel suo post. Le variabili focus sono basate sulla teoria (non c'è spazio per essere spurie o over-fitting), un ampio set di informazioni combatte bene il problema del bias pre-test.
Dikran Marsupial
2011-03-01 19:01:36 UTC
view on stackexchange narkive permalink

Solo un avvertimento, ma la selezione delle caratteristiche è un'attività rischiosa e più funzioni hai, più gradi di libertà hai con cui ottimizzare il criterio di selezione delle caratteristiche, e quindi maggiore è il rischio di adattamento eccessivo della caratteristica criterio di selezione e in tal modo ottenere un modello con scarsa capacità di generalizzazione. È possibile che con un algoritmo efficiente e un'attenta codifica sia possibile eseguire la selezione di tutti i sottoinsiemi con un gran numero di funzionalità, ciò non significa che sia una buona idea farlo, soprattutto se si hanno relativamente poche osservazioni. Se si utilizza la selezione di tutti i sottoinsiemi, è fondamentale convalidare correttamente l'intera procedura di adattamento del modello (in modo che la selezione di tutti i sottoinsiemi venga eseguita indipendentemente in ogni piega della convalida incrociata). In pratica, la regressione della cresta senza selezione di feature spesso supera la regressione lineare con la selezione di feature (questo consiglio è fornito nella monografia di Millar sulla selezione di feature).

@Dikran, (+1) buoni commenti. Stavo cercando di evitare di andarci poiché non rispondeva direttamente alla domanda dell'OP. Ma sono d'accordo. Tutti i sottoinsiemi sono raramente la strada da percorrere. E, se vai in quel modo, devi capire tutte le implicazioni.
@Dirkan grazie per i commenti, sono un vero principiante delle statistiche. Mi rendo conto del pericolo di sovradattare il modello quando sono in gioco troppe variabili, quindi sto solo osservando vari modi automatizzati (cioè senza molto beneficio di intuizione) come l'approccio graduale (che potrebbe rimanere intrappolato in un massimo locale) e il modello esaustivo di tutti i sottoinsiemi e dei limiti computazionali che deve affrontare (e dei limiti esterni imposti dai pacchetti)
@levon9, puoi ottenere un adattamento eccessivo che è altrettanto serio quando scegli le caratteristiche, quindi la selezione delle caratteristiche non protegge dall'eccessivo adattamento. Considera un modello di regressione logistica utilizzato per prevedere il risultato del lancio di una moneta equa. I potenziali input sono il risultato del lancio di un gran numero di altre monete giuste. Alcuni di questi input saranno correlati positivamente con l'obiettivo, quindi il miglior modello di tutti i sottoinsiemi selezionerà gli input (anche se sono inutili) e otterrai un modello che sembra avere abilità, ma in realtà non è meglio che indovinare.
@Dikran (+1) lo stesso di @cardinal, Ho scritto per la prima volta un testo simile, ma poi ho deciso che non era quello che chiedeva @levon9, perché semplicemente era curioso della complessità :)
@Dikran +1 perché mi piace questo consiglio.
@Dikran grazie per i chiarimenti / commenti aggiuntivi - e scusa per l'errore di battitura precedente con il tuo nome.
Ralph Winters
2011-03-01 20:56:20 UTC
view on stackexchange narkive permalink

Sono stato in grado di generare tutti i possibili sottoinsiemi utilizzando 50 variabili in SAS. Non credo che ci siano limiti rigidi oltre alla memoria e alla velocità della CPU.

Modifica

Ho generato i 2 migliori modelli per N = 1 a 50 variabili per 5000 osservazioni.

@ levon9 - No, è stato eseguito in meno di 10 secondi. Ho generato 50 variabili casuali da (0,1)

-Ralph Winters

Per quale dimensione del set di dati?
Grazie informazioni molto utili. Sono solo curioso, ci è voluto molto tempo?
Ho annullato l'eliminazione di questo post (e ho unito un altro dei tuoi commenti in una modifica) perché l'OP lo ha trovato utile e potrebbero farlo anche altri. Grazie per il tuo contributo; per favore continuate così! (Se pensi davvero che debba essere cancellato, vai avanti e fallo; non contravverò più i tuoi desideri.)
Sembra che tu stia utilizzando due diversi account non registrati. Li ho uniti ma dovrai comunque registrarti.
probabilityislogic
2011-03-01 16:17:03 UTC
view on stackexchange narkive permalink

Man mano che $ N $ cresce, la tua capacità di usare la matematica diventa assolutamente cruciale. la matematica "inefficiente" ti costerà al PC. Il limite superiore dipende dall'equazione che stai risolvendo. Evitare i calcoli inversi o determinanti della matrice è un grande vantaggio.

Un modo per aiutare ad aumentare il limite è usare i teoremi per scomporre una matrice inversa grande da in inversi di matrice più piccoli. Questo spesso può significare la differenza tra fattibile e non fattibile. Ma questo comporta un duro lavoro e manipolazioni matematiche spesso piuttosto complicate! Ma di solito ne vale la pena. Fai i conti o il tempo!

I metodi bayesiani potrebbero essere in grado di fornire un modo alternativo per ottenere il tuo risultato - potrebbero essere più veloci, il che significa che il tuo "limite superiore" aumenterà (se non altro perché ti dà due modi alternativi per calcolare la stessa risposta: il più piccolo tra due sarà sempre più piccolo di uno di essi!).

Se puoi calcolare un coefficiente di regressione senza invertire una matrice, probabilmente salverai un Un sacco di tempo. Ciò può essere particolarmente utile nel caso bayesiano, perché "all'interno" di un normale integrale di marginalizzazione, la matrice $ X ^ {T} X $ non ha bisogno di essere invertita, si calcola solo una somma di quadrati. Inoltre, la matrice determinante farà parte della costante di normalizzazione. Quindi "in teoria" potresti usare tecniche di campionamento per valutare numericamente l'integrale (anche se ha un'espressione analitica) che sarà eoni più veloce rispetto al tentativo di valutare l '"esplosione combinatoria" di inverse di matrice e determinanti. (sarà ancora una "esplosione combinatoria" di integrazioni numeriche, ma potrebbe essere più veloce).

Questo suggerimento sopra è un po 'una mia "bolla di pensiero". Voglio provarlo davvero, vedere se va bene. Penso che sarebbe (5.000 simulazioni + calcolare exp (somma dei quadrati) + calcolare il beta medio ponderato dovrebbe essere più veloce dell'inversione di matrice per una matrice abbastanza grande.)

Il costo è approssimativo piuttosto che una stima esatta. Non c'è niente che ti impedisca di usare lo stesso insieme di numeri pseudo casuali per valutare numericamente l'integrale, il che ti farà risparmiare molto tempo.

Niente ti impedisce anche di usare una combinazione di entrambe le tecniche. Usa l'esatto quando le matrici sono piccole, usa la simulazione quando sono grandi. Questo perché in questa parte dell'analisi. Sono solo tecniche numeriche diverse: scegli la tecnica più veloce!

Ovviamente questo è solo un po 'di argomenti "ondeggianti", non conosco esattamente i migliori pacchetti software da usare - e peggio ancora, cercando di capire quali algoritmi usano effettivamente.

@probabilityislogic, mentre la tua risposta è interessante, forse potrebbe essere riorientata per rispondere meglio alla domanda dell'OP. Inoltre, *** nessun software per il calcolo delle soluzioni dei minimi quadrati esegue l'inversione della matrice, tanto meno un determinante. Mai. A meno che non stia invertendo una matrice $ 1 \ times 1 $.
@probabilityislogic, che gestisce i casi $ 2 ^ n $ in modo efficiente e veloce supera di gran lunga i problemi $ O (n ^ 3) $ di una soluzione efficiente dei minimi quadrati. È qui che entra in gioco l'algoritmo * balzi e limiti *.
Grazie per il post. "Fai i conti o il tempo!" :-) .. in realtà non sto nemmeno cercando di capire gli algoritmi sottostanti usati dai pacchetti (pensato che sia interessante sapere), a questo punto sto davvero cercando informazioni specifiche riguardanti i limiti di N da parte dei pacchetti principali.
@cardinal Gli algoritmi di aggiornamento e downdating esistono anche per varie procedure di decomposizione della matrice, sospetto che sia ciò che si intendeva per "matrice inversa" ecc.
-1
@cardinal - Sono curioso del tuo commento sui "minimi quadrati" che non eseguono mai l'inversione di matrice. L'equazione principale per le stime è $ \ beta = (X ^ {T} X) ^ {- 1} X ^ {T} Y $. Inoltre la varianza di queste stime è data da $ \ sigma ^ {2} (X ^ {T} X) ^ {- 1} $. La matrice inversa è fondamentale per la tipica regressione ai minimi quadrati, almeno in matematica. Anche se sto mostrando la mia ignoranza nelle effettive procedure di calcolo seguite.
@probabilityislogic, un approccio comune consiste nell'utilizzare (qualche variante di) una scomposizione $ QR $. Quindi, scriviamo $ X = Q R $, dove $ Q $ è una matrice con colonne ortogonali e $ R $ è una matrice triangolare quadrata. È un esercizio facile vedere che i residui possono essere scritti come $ \ hat {y} = QQ ^ T y $ e le stime dei parametri sono la soluzione quindi il sistema triangolare di equazioni $ R \ hat {\ beta} = Q ^ T y $. I sistemi triangolari sono molto efficienti da risolvere. La scomposizione $ Q R $ utilizzando le riflessioni di Householder o le rotazioni di Givens è numericamente molto stabile. Nessuna inversione di matrice necessaria.
@cardinal - grazie per questo. Quindi suppongo che la mia "bolla di pensiero" si riduca al confronto tra la velocità di decomposizione QR e l'integrazione numerica
-1
@cardinal - Suggerirei che il metodo MC ha la capacità di essere "ridimensionato" (più simulazioni) o "ridimensionato" (meno) in base alla precisione richiesta. Con il metodo QR, sebbene esatto, sei bloccato in una certa misura con lo stesso tempo di elaborazione. Per qualcosa come la regressione di tutti i sottoinsiemi, l'esattezza della risposta potrebbe non essere la priorità numero uno. Ancora una volta, se hai due metodi, uno di questi sarà più veloce. Espandere la mia bolla di pensiero consisterebbe in quali condizioni sono necessarie affinché un metodo sia più veloce dell'altro - ea quale costo.
@probabilityislogic, il problema è ancora che il lavoro $ O (2 ^ n) $ per tutti i sottoinsiemi è molto più grande del lavoro $ O (n p ^ 2) $ di una decomposizione $ QR $. Nel caso $ QR $, una volta ottenute le stime iniziali di regressione completa, è plausibile che si possano fare solo semplici aggiornamenti di un rango per trovare le stime dei parametri per i modelli più piccoli. Questi aggiornamenti al primo posto sono veloci. Ma, per tutti i sottoinsiemi, dovrebbe essere eseguita * ogni * combinazione di tali aggiornamenti. Il tuo metodo richiederebbe una nuova stima dell'integrale ogni volta che $ X $ cambia e non è esatto. Azzardo l'ipotesi che sia molto meno efficiente.
@cardinal - non sarebbe necessario "rivalutare" l'integrale numerico. Ignori semplicemente i campioni posteriori per quelle parti del modello che vengono escluse. Hai solo bisogno di 1 simulazione dal modello completo e non sono richiesti aggiornamenti di livello 1: è qui che penso che risparmierai molto tempo. Una di queste domande potrebbe essere "$ \ beta_j $ è rilevante per il mio modello, * indipendentemente da quali altri parametri ci sono nel modello? *". Deciderlo molto velocemente - basta guardare la distribuzione simulata marginale per $ \ beta_j $.
@cardinal - aggiungendo al punto precedente, supponi di avere una "regione di rifiuto", ad es. $ \ frac {| \ beta_j |} {SE (\ beta_j)} \ leq 1 $ che sei pronto a dichiarare che il coefficiente è "zero" e rimuoverlo dal modello. Quindi la regressione $ 2 ^ n $ di tutti i sottoinsiemi sul set di dati simulato si riduce al problema di una tabella di contingenza a n vie, ogni modo ha 2 risultati - nella regione o meno. I "modelli migliori" hanno la probabilità più alta in questa tabella
@probabilityislogic, i tuoi commenti non hanno davvero nulla a che fare con la regressione di tutti i sottoinsiemi e non proverei a forzarli in quel quadro. Sembrano avere più a che fare con la * selezione del modello * nella regressione. Esistono una moltitudine di tali metodi, sia classici che moderni, inclusi approcci a soglia come quello che descrivi. Il lazo è un esempio e ha persino un'interpretazione bayesiana. Solitamente è necessaria una condizione vicina all'ortogonalità della matrice di progetto per garantire buone prestazioni (anche asintoticamente!).


ⓘ
Questa domanda e risposta è stata tradotta automaticamente dalla lingua inglese. Il contenuto originale è disponibile su stackexchange, che ringraziamo per la licenza cc by-sa 2.0 con cui è distribuito.
Loading...