Question:
Quelles sont les limitations logicielles dans toutes les sélections de sous-ensembles possibles dans la régression?
Levon
2011-03-01 09:09:40 UTC
view on stackexchange narkive permalink

Si j'avais une variable dépendante et des variables prédictives $ N $ et que je voulais que mon logiciel de statistiques examine tous les modèles possibles, il y aurait des équations résultantes $ 2 ^ N $ possibles.

Je suis curieux de savoir quelles sont les limitations concernant $ N $ pour les logiciels de statistiques majeurs / populaires car à mesure que $ N $ devient grand, il y a une explosion combinatoire.

I J'ai parcouru les différentes pages Web pour trouver des paquets mais je n'ai pas pu trouver ces informations. Je soupçonne une valeur de 10 à 20 pour $ N $?

Si quelqu'un sait (et a des liens), je serais reconnaissant pour cette information.

À part R, Minitab, Je peux penser à ces packages SAS, SPPS, Stata, Matlab, Excel (?), Tout autre package que je devrais envisager?

@levon9 Cette question a généré beaucoup de réponses et de commentaires sonores, donc j'ai +1. Mais, s'il vous plaît, oubliez Excel pour faire un travail sérieux dans la sélection de modèles ...
@levon9 - J'ai pu générer tous les sous-ensembles possibles en utilisant 50 variables en SAS. Je ne pense pas qu'il y ait de limitation stricte autre que la mémoire et la vitesse du processeur.-Ralph Winters
Pour quelle taille de jeu de données?
Merci des informations très utiles. Curieux, est-ce que cela a pris du temps?
@chl .. est-ce parce qu'Excel est lent, ou tout simplement incapable (c'est-à-dire donnerait des résultats inexacts?).
@levon9, @chl Excel est (en principe) capable d'implémenter correctement des algorithmes de sélection de modèle. Il ne le fait pas hors de la boîte. Quelqu'un a-t-il un complément en tête?
@levon9 @whuber Mon point sur Excel n'était pas lié à ses performances (que je ne connais pas dans ce cas particulier) mais il s'agissait simplement de pointer vers de "meilleurs" logiciels qui fournissent des outils intégrés pour la construction de modèles, la sélection, les diagnostics (et oui je Je dois admettre que je suis un peu biaisé vers R ou Stata à cette fin).
Quatre réponses:
#1
+12
cardinal
2011-03-01 09:19:54 UTC
view on stackexchange narkive permalink

Je suppose que 30 à 60 est à peu près le meilleur que vous obtiendrez. L'approche standard est l'algorithme sauts et limites qui ne nécessite pas d'ajuster tous les modèles possibles. Dans $ R $, le package sauts est une implémentation.

La documentation de la fonction regsubsets dans la sauts indique qu'il traitera jusqu'à 50 variables sans se plaindre. Il peut être "forcé" d'en faire plus de 50 en définissant le drapeau booléen approprié.

Vous pourriez faire un peu mieux avec une technique de parallélisation, mais le nombre de modèles totaux que vous pouvez considérer sera (presque sans aucun doute) mise à l'échelle uniquement linéairement avec le nombre de cœurs de processeur dont vous disposez. Donc, si 50 variables est la limite supérieure pour un seul cœur, et que vous avez 1000 cœurs à votre disposition, vous pouvez augmenter cela à environ 60 variables.

** sauts ** est génial, j'aime les intrigues, +1. Dans les applications réelles, certaines techniques de calcul de la moyenne fonctionnent plus rapidement (et mieux) que les estimateurs prétestés même trouvés à partir de tous les modèles de régression. Je suggérerais donc d'opter pour la moyenne du modèle bayésien (package BMA) ou l'algorithme que j'aime le plus - Moyenne pondérée des moindres carrés (WALS [1]) développé par J.R. Magnus et al. Le code Matlab est facilement transformable en code R. La bonne chose pour WALS est la difficulté de calcul $ N $ au lieu de $ 2 ^ N $. [1]: http://www.tilburguniversity.edu/research/institutes-and-research-groups/center/staff/magnus/wals/
Merci @Dmitrij, pour vos commentaires. J'ai essayé de rester assez agnostique dans ma réponse concernant l'utilité de la régression de tous les sous-ensembles. Il me semble qu'il y a presque toujours une meilleure solution, mais j'ai pensé que cela pouvait sembler une réponse trop banale à la question du PO.
@Dmitrij, BMA sur les modèles à effets principaux aurait toujours la même complexité de calcul que la régression de tous les sous-ensembles. Non? Le principal avantage de la BMA me semble être d'essayer de déterminer quelles covariables sont susceptibles d'influencer la réponse. Pour ce faire, BMA fait essentiellement la moyenne des probabilités logarithmiques sur les sous-modèles $ 2 ^ {n-1} $.
Merci pour le pointeur sur le package leaps R! Je ne savais pas à ce sujet et cela pourrait être utile à l'avenir. Si je pouvais obtenir des informations sur les limitations spécifiques de N pour d'autres packages populaires, ce serait très utile.
@levon9, Je doute que cela varie beaucoup d'un package à l'autre. L'algorithme qui ** bondit ** utilise est à la pointe de la technologie depuis au moins 20 ans. Même si vous trouviez une implémentation * deux * plus rapide, cela signifierait que vous devez incrémenter le nombre de variables que vous pouvez gérer par un. Pour chaque doublement de la vitesse, vous obtenez une autre variable. Les limitations matérielles et non algorithmiques sont votre goulot d'étranglement dans ce cas.
@cardinal, exactement, BMA a le même inconvénient de complexité de calcul que la régression tous sous-ensembles (dans Eviews, il est appelé approche combinatoire ^ _ ^). C'est pourquoi j'évalue davantage WALS, car il pondère à la fois les covariables, est plus rapide et est utile si nous avons des paramètres * focus * (l'estimateur pondéré a un biais * pré-test * plus petit) et des paramètres qui vont aux variables auxiliaires que nous ne sommes pas certain sur et, oui, il résout les problèmes @Dikran mentionnés dans son message. Les variables de focalisation sont basées sur la théorie (il n'y a pas de place pour devenir faux ou sur-ajusté), un grand ensemble d'informations combat bien le problème de biais pré-test.
#2
+10
Dikran Marsupial
2011-03-01 19:01:36 UTC
view on stackexchange narkive permalink

Juste une mise en garde, mais la sélection de fonctionnalités est une activité risquée, et plus vous avez de fonctionnalités, plus vous disposez de degrés de liberté pour optimiser le critère de sélection de fonctionnalités, et donc plus le risque de sur-ajustement de la fonctionnalité est élevé. critère de sélection et, ce faisant, obtenir un modèle avec une faible capacité de généralisation. Il est possible qu'avec un algorithme efficace et un codage soigné, vous puissiez effectuer la sélection de tous les sous-ensembles avec un grand nombre de fonctionnalités, cela ne signifie pas que c'est une bonne idée de le faire, surtout si vous avez relativement peu d'observations. Si vous utilisez la sélection de tous les sous-ensembles, il est essentiel de valider correctement l'ensemble de la procédure d'ajustement du modèle (afin que la sélection de tous les sous-ensembles soit effectuée indépendamment dans chaque pli de la validation croisée). En pratique, la régression de crête sans sélection d'entités surpasse souvent la régression linéaire avec sélection d'entités (ces conseils sont donnés dans la monographie de Millar sur la sélection d'entités).

@Dikran, (+1) bons commentaires. J'essayais d'éviter d'y aller car cela ne répondait pas directement à la question du PO. Mais, je suis d'accord. Tous les sous-ensembles sont rarement la voie à suivre. Et, si vous suivez cette voie, vous devez comprendre toutes les implications.
Merci @Dirkan pour les commentaires, je suis un vrai débutant en stats. Je me rends compte du danger de surajustement du modèle lorsque trop de variables sont en jeu, donc je regarde simplement différentes méthodes automatisées (c'est-à-dire sans grand avantage de perspicacité) telles que l'approche par étapes (qui pourrait être prise dans un maximum local) et le modèle exhaustif de tous les sous-ensembles - et les limites de calcul auxquelles il est confronté (et les limitations externes imposées par les packages)
@levon9,, vous pouvez obtenir un ajustement excessif qui est tout aussi sérieux lorsque vous choisissez les fonctionnalités, de sorte que la sélection des fonctionnalités ne protège pas contre un ajustement excessif. Considérons un modèle de régression logistique utilisé pour prédire le résultat du retournement d'une pièce équitable. Les intrants potentiels sont le résultat du retournement d'un grand nombre d'autres pièces justes. Certaines de ces entrées seront positivement corrélées avec la cible, de sorte que le meilleur modèle tous sous-ensembles sélectionnera les entrées (même si elles sont inutiles) et vous obtiendrez un modèle qui semble avoir des compétences, mais en réalité, ce n'est pas mieux que de deviner.
@Dikran (+1) identique à @cardinal, J'ai d'abord écrit un texte similaire, mais j'ai ensuite décidé que ce n'était pas ce qu'@levon9 avait demandé, car il était simplement curieux de connaître la complexité :)
@Dikran +1 parce que j'aime ces conseils.
Merci @Dikran pour les clarifications / commentaires supplémentaires - et désolé pour la faute de frappe plus tôt avec votre nom.
#3
+4
Ralph Winters
2011-03-01 20:56:20 UTC
view on stackexchange narkive permalink

J'ai pu générer tous les sous-ensembles possibles en utilisant 50 variables dans SAS. Je ne pense pas qu'il y ait de limitation stricte autre que la mémoire et la vitesse du processeur.

Modifier

J'ai généré les 2 meilleurs modèles pour N = 1 à 50 variables pour 5000 observations.

@ levon9 - Non, cela a duré moins de 10 secondes. J'ai généré 50 variables aléatoires à partir de (0,1)

-Ralph Winters

Pour quelle taille de jeu de données?
Merci des informations très utiles. Curieux, est-ce que cela a pris du temps?
J'ai annulé ce message (et fusionné un autre de vos commentaires dans une modification) car l'OP l'a trouvé utile et d'autres pourraient aussi. Nous vous remercions de votre contribution; s'il vous plaît continuez comme ça! (Si vous pensez vraiment qu'il devrait être supprimé, allez-y et faites-le; je ne contreviendrai plus à vos souhaits.)
Il semble que vous utilisez deux comptes non enregistrés différents. Je les ai fusionnés mais vous devrez tout de même vous inscrire.
#4
+3
probabilityislogic
2011-03-01 16:17:03 UTC
view on stackexchange narkive permalink

À mesure que $ N $ prend de l'ampleur, votre capacité à utiliser les mathématiques devient absolument cruciale. Les mathématiques "inefficaces" vous coûteront au PC. La limite supérieure dépend de l'équation que vous résolvez. Éviter les calculs inverses matriciels ou déterminants est un gros avantage.

Une façon d'aider à augmenter la limite est d'utiliser des théorèmes pour décomposer une grande matrice inverse à partir d'inverses matriciels plus petits. Cela peut souvent faire la différence entre faisable et non faisable. Mais cela implique un travail acharné et souvent des manipulations mathématiques assez compliquées! Mais cela en vaut généralement la peine. Faites le calcul ou faites le temps!

Les méthodes bayésiennes pourraient être en mesure de donner une autre façon d'obtenir votre résultat - peut-être plus rapide, ce qui signifie que votre "limite supérieure" augmentera (ne serait-ce que parce qu'elle vous donne deux méthodes alternatives pour calculer la même réponse - la plus petite des deux sera toujours plus petite que l'une d'entre elles!).

Si vous pouvez calculer un coefficient de régression sans inverser une matrice, vous économiserez probablement un beaucoup de temps. Cela peut être particulièrement utile dans le cas bayésien, car "à l'intérieur" d'une intégrale de marginalisation normale, la matrice $ X ^ {T} X $ n'a pas besoin d'être inversée, vous calculez simplement une somme de carrés. En outre, la matrice déterminante fera partie de la constante de normalisation. Donc, "en théorie", vous pouvez utiliser des techniques d'échantillonnage pour évaluer numériquement l'intégrale (même si elle a une expression analytique) qui sera des éons plus rapides que d'essayer d'évaluer "l'explosion combinatoire" des inverses et des déterminants de la matrice. (ce sera toujours une "explosion combinatoire" d'intégrations numériques, mais cela peut être plus rapide).

Cette suggestion ci-dessus est un peu une de mes "bulles de pensée". Je veux vraiment le tester, voir si c'est bon. Je pense que ce serait (5000 simulations + calculer exp (somme des carrés) + calculer le bêta moyen pondéré devrait être plus rapide que l'inversion de matrice pour une matrice assez grande.)

Le coût est approximatif plutôt que des estimations exactes. Rien ne vous empêche d'utiliser le même ensemble de nombres pseudo aléatoires pour évaluer numériquement l'intégrale, ce qui vous fera encore gagner beaucoup de temps.

Rien ne vous empêche également d'utiliser une combinaison de l'une ou l'autre technique. Utilisez exact quand les matrices sont petites, utilisez la simulation quand elles sont grandes. C'est parce que dans cette partie de l'analyse. Ce ne sont que des techniques numériques différentes - choisissez simplement la technique la plus rapide!

Bien sûr, ce ne sont que des arguments "ondulés à la main", je ne connais pas exactement les meilleurs logiciels à utiliser - et pire, en essayant de comprendre quels algorithmes ils utilisent réellement.

@probabilityislogic, si votre réponse est intéressante, peut-être pourrait-elle être recentrée pour mieux répondre à la question du PO. De plus, *** no *** logiciel de calcul des solutions des moindres carrés effectue une inversion de matrice, et encore moins un déterminant. Déjà. Sauf s'il inverse une matrice $ 1 \ times 1 $.
@probabilityislogic, qui gère efficacement les cas $ 2 ^ n $ dépasse de loin les problèmes $ O (n ^ 3) $ d'une solution efficace des moindres carrés. C'est là qu'intervient l'algorithme de * sauts et limites *.
Merci pour le post. "Faites le calcul ou faites le temps!" :-) .. Je n'essaye même pas de comprendre les algorithmes sous-jacents utilisés par les paquets (c'est intéressant à savoir), à ce stade, je recherche vraiment des informations spécifiques concernant les limitations de N par les principaux paquets.
@cardinal Les algorithmes de mise à jour et de mise à jour existent également pour diverses procédures de décomposition matricielle, je suppose que c'est ce que l'on entendait par «matrice inverse», etc.
@Dikran, il existe plusieurs approches efficaces et numériquement stables des moindres carrés, y compris des méthodes pour augmenter ou réduire une matrice de conception d'une colonne à la fois. Parfois, il est bon de comprendre ce qui se passe sous la surface, même si la plupart du temps, vous n'avez pas besoin de vous en soucier.
@cardinal - Je suis curieux de connaître votre commentaire sur les "moindres carrés" qui n'effectuent jamais l'inversion de matrice. L'équation principale des estimations est $ \ beta = (X ^ {T} X) ^ {- 1} X ^ {T} Y $. De plus, la variance de ces estimations est donnée par $ \ sigma ^ {2} (X ^ {T} X) ^ {- 1} $. La matrice inverse est fondamentale pour la régression typique des moindres carrés, du moins en mathématiques. Bien que je montre mon ignorance dans les procédures de calcul réelles suivies.
@probabilityislogic, une approche courante consiste à utiliser (une variante de) une décomposition $ QR $. Donc, nous écrivons $ X = Q R $, où $ Q $ est une matrice avec des colonnes orthogonales et $ R $ est une matrice triangulaire carrée. C'est un exercice facile de voir que les résidus peuvent être écrits comme $ \ hat {y} = QQ ^ T y $ et les estimations de paramètres sont la solution, donc le système triangulaire d'équations $ R \ hat {\ beta} = Q ^ T y $. Les systèmes triangulaires sont très efficaces à résoudre. La décomposition $ Q R $ utilisant les réflexions de Householder ou les rotations de Givens est numériquement très stable. Aucune inversion de matrice nécessaire.
@cardinal - merci pour cela. Donc je suppose que ma "bulle de pensée" se réduit à comparer la vitesse de décomposition QR avec l'intégration numérique
La décomposition de @probabilityislogic, $ QR $ ne devrait jamais être pire que $ O (n p ^ 2) $, et cela fournit une réponse exacte (avec une précision numérique près). Pour comparer cela à l'intégration de Monte Carlo, il vous faudrait spécifier au moins quelques notions de précision souhaitée.
@cardinal - Je dirais que la méthode MC a la capacité d'être «mise à l'échelle» (plus de simulations) ou «réduite» (moins) selon la précision requise. Avec la méthode QR, bien qu'exacte, vous êtes coincé dans une certaine mesure avec le même temps de calcul. Pour quelque chose comme la régression de tous les sous-ensembles, l'exactitude de la réponse peut ne pas être la priorité numéro un. Encore une fois, si vous avez deux méthodes, l'une d'elles sera plus rapide. L'élargissement de ma bulle de pensée consisterait à déterminer les conditions requises pour qu'une méthode soit plus rapide que l'autre - et à quel prix.
@probabilityislogic,, le problème est toujours que le travail $ O (2 ^ n) $ pour tous les sous-ensembles est beaucoup plus grand que le travail $ O (n p ^ 2) $ d'une décomposition $ QR $. Dans le cas de $ QR $, une fois que les estimations initiales de régression complète sont obtenues, on peut concevoir que seules de simples mises à jour à un rang puissent être effectuées pour trouver les estimations de paramètres pour des modèles plus petits. Ces mises à jour de premier rang sont rapides. Mais, pour tous les sous-ensembles, * chaque * combinaison de ces mises à jour devrait être faite. Votre méthode nécessiterait de ré-estimer l'intégrale chaque fois que $ X $ change et n'est pas exacte. Je risquerais de penser que c'est beaucoup moins efficace.
@cardinal - il ne serait pas nécessaire de "ré-estimer" l'intégrale numérique. Vous ignorez simplement les échantillons postérieurs pour les parties du modèle qui sont exclues. Vous n'avez besoin que d'une simulation à partir du modèle complet et aucune mise à jour de rang 1 n'est requise - c'est là que je pense que vous gagnerez beaucoup de temps. Une de ces questions pourrait être «est $ \ beta_j $ pertinent pour mon modèle, * quels que soient les autres paramètres du modèle? *». Très vite pour décider ceci - il suffit de regarder la distribution simulée marginale pour $ \ beta_j $.
@cardinal - en ajoutant à mon point ci-dessus, supposons que vous ayez une "région de rejet", par exemple $ \ frac {| \ beta_j |} {SE (\ beta_j)} \ leq 1 $ que vous êtes prêt à déclarer que le coefficient est "zéro" et à le supprimer du modèle. Ensuite, la régression $ 2 ^ n $ tous les sous-ensembles sur l'ensemble de données simulé se réduit au problème d'une table de contingence à n voies, chaque voie a 2 résultats - dans la région ou non. Les "meilleurs modèles" ont la probabilité la plus élevée dans ce tableau
@probabilityislogic, vos commentaires n'ont vraiment rien à voir avec la régression de tous les sous-ensembles et je n'essaierais pas de les forcer dans ce cadre. Ils semblent avoir plus à voir avec la * sélection du modèle * dans la régression. Il existe une multitude de méthodes de ce type, à la fois classiques et modernes, y compris des approches à seuil comme celle que vous décrivez. Le lasso en est un exemple et il a même une interprétation bayésienne. Habituellement, vous avez besoin d'une condition proche de l'orthogonalité de la matrice de conception pour garantir de bonnes performances (même asymptotiquement!).


Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 2.0 sous laquelle il est distribué.
Loading...