Vitesse, dépenses de calcul de PCA, LASSO, filet élastique

18

J'essaie de comparer la complexité de calcul / la vitesse d'estimation de trois groupes de méthodes de régression linéaire comme distingué dans Hastie et al. "Elements of Statistical Learning" (2e éd.), Chapitre 3:

  1. Sélection de sous-ensemble
  2. Méthodes de retrait
  3. Méthodes utilisant des directions d'entrée dérivées (PCR, PLS)

La comparaison peut être très approximative, juste pour donner une idée. Je suppose que les réponses peuvent dépendre de la dimension du problème et de la façon dont cela correspond à l'architecture informatique, donc pour un exemple concret, on peut considérer un échantillon de 500 et 50 régresseurs candidats. Je suis surtout intéressé par la motivation derrière la complexité de calcul / la vitesse d'estimation, mais pas par le temps qu'il faudrait à un certain processeur pour l'exemple donné.

Richard Hardy
la source
Lors de l'utilisation de la PCR ou du PLS, le nombre de composants est un paramètre de réglage (similaire à dans la régression de crête). Ces méthodes devront donc également être validées de manière croisée pour trouver le nombre optimal de composants. LASSO a également un paramètre de régularisation, mais le filet élastique en a deux (filet élastique = crête + LASSO), donc la validation croisée est plus coûteuse. En dehors de cela, LASSO est probablement plus lent à installer que tous les autres modèles, car il n'a pas de solution de forme fermée. λ
amibe dit Réintégrer Monica
Je vous remercie! Votre commentaire ferait une bonne réponse si vous incluiez deux autres détails: (1) combien coûte une itération de PCR et de PLS par rapport à une exécution OLS de la régression régulière; (2) quantifier plus précisément la vitesse de LASSO pour la rendre comparable à la vitesse de la régression régulière (est-ce polynomial, exponentiel ou linéairement plus cher, et pourquoi).
Richard Hardy
Malheureusement, je n'ai pas de réponse toute prête à cela, en particulier à (2). C'est pourquoi je n'ai laissé qu'un commentaire. +1, au fait, et félicitations avec 5k rep!
amibe dit Réintégrer Monica
1
@amoeba, merci! Je ne pouvais pas m'attendre à atteindre 5 km lorsque j'ai commencé (très lentement) l'année dernière. Mais c'est très excitant et gratifiant d'être un membre actif ici à Cross Validated!
Richard Hardy
@amoeba, je pense avoir compris la complexité de LASSO si l'algorithme LARS est utilisé; J'ai mis à jour mon message en conséquence. Mais je n'ai pas lu attentivement le document LARS, donc je ne suis pas sûr qu'il soit correct ...
Richard Hardy

Réponses:

5

Groupe 1 :
La complexité / vitesse du groupe 1. ne semble pas trop difficile à déterminer si des algorithmes de force brute sont utilisés (bien qu'il puisse y avoir des alternatives plus efficaces telles que l'algorithme "sauts et limites"). Par exemple, une sélection complète de sous-ensembles nécessitera régressions pour être ajustée étant donné un pool de fonctionnalités candidates. Un ajustement OLS d'une régression linéaire a la complexité de (selon ce post ) où est la taille de l'échantillon. Par conséquent, la complexité totale de la sélection de sous-ensemble complet par force brute devrait être . K O ( K 2 n ) n O ( 2 K K 2 n )2KKO(K2n)nO(2KK2n)

Groupe 2 :
La complexité / vitesse du groupe 2. est discutée dans les sections 3.8 et 3.9 du livre. Par exemple, une régression de crête avec une pénalité donnée a la même complexité de calcul qu'une régression régulière. Étant donné que doit être trouvé à l'aide de la validation croisée, la charge de calcul augmente linéairement dans le nombre de divisions de données utilisées dans la validation croisée (par exemple, ). Si la grille a points, la complexité totale de la régression de crête avec le réglage du paramètre sera . On en parle pas malλ S λ L λ O ( L S K 2 n ) λ λ O ( L S K 2 n ) O ( A L S K 2 n ) A αλλSλLλO(LSK2n)
LASSO dans le livre, mais je n'ai pas trouvé exactement ce dont j'avais besoin. Cependant, j'ai trouvé à la p. 443 d'Efron et al. "Least Angle Regression" (2004) que la complexité de LASSO pour un donné est la même que la complexité d'un ajustement OLS de régression linéaire si la méthode LARS est utilisée. La complexité totale de LASSO avec le réglage du paramètre sera alors . (Je n'ai pas lu attentivement ce document, alors corrigez-moi si je me trompe.) Le filet élastique combine crête et LASSO; les deux ont la même complexité de calcul; par conséquent, la complexité du filet élastique doit être où est la taille de la grille du paramètre de réglageλλO(LSK2n)
O(ALSK2n)Aα qui équilibre les poids de la crête par rapport à LASSO.

Groupe 3 :
Je manque encore une note sur la complexité / vitesse pour le groupe 3. qui se compose de la régression des composantes principales (PCR) et des moindres carrés partiels (PLS).

Richard Hardy
la source
2

C'est seulement pour une partie de la question 2 sur le groupe 3 ci-dessus (à savoir PLS), mais peut être informative néanmoins: Srinivasan et al (2010, rapport technique; voir https://www.umiacs.umd.edu/~balajiv/Papers/ UMD_CS_TR_Pls_Gpu.pdf ) a fait quelques mesures sur PLS en utilisant l'algorithme NIPALS - en déclarant que la complexité temporelle (et spatiale) de cet algorithme soit O (dN) - pour l'extraction et en l'incluant dans différents modèles pour a) la détection des humains dans les images, et b ) reconnaissance de visage. Les mesures ont été effectuées à l'aide de leur propre implémentation basée sur GPU.

jf1
la source