J'implémente Ridge Regression dans un module Python / C, et je suis tombé sur ce "petit" problème. L'idée est que je souhaite échantillonner les degrés de liberté effectifs plus ou moins également espacés (comme le graphique de la page 65 sur les "Éléments de l'apprentissage statistique" ), c'est-à-dire, échantillon: où sont les valeurs propres de la matrice , à partir de à \ mathrm {df} (\ lambda _ {\ min}) = p . Un moyen simple de définir la première limite est de laisser \ lambda _ {\ max} = \ sum_i ^ p d_i ^ 2 / c (en supposant \ lambda _ {\ max} \ gg d_i ^ 2 ), où c
Comme le titre l'indique, j'ai besoin d'échantillonner de à à une certaine échelle de telle sorte que soit échantillonné (environ), par exemple, dans intervalle de à ... existe-t-il un moyen facile de le faire? J'ai pensé résoudre l'équation pour chaque utilisant une méthode de Newton-Raphson, mais cela ajoutera trop d'itérations, spécialement lorsque est grand. Aucune suggestion?
la source
Réponses:
Ceci est une longue réponse . Alors, donnons-en une version courte ici.
R
code mort cérébral en l' absence de toute tentative d'optimisation peut calculer une grille de taille 100 avec en quelques secondes. Un code soigneusement rédigé réduirait cela d'au moins 2 à 3 ordres de grandeur.C
Deux schémas sont donnés ci-dessous pour garantir la convergence monotone. On utilise les limites indiquées ci-dessous, qui semblent aider à enregistrer une étape de Newton ou deux à l'occasion.
Exemple : et une grille uniforme pour les degrés de liberté de taille 100. Les valeurs propres sont Pareto-distribuées, donc fortement asymétriques. Voici les tableaux du nombre d'étapes de Newton pour trouver chaque racine.p=100000
Il n'y aura pas de solution de forme fermée pour cela , en général, mais il y a beaucoup de structure présente qui peut être utilisée pour produire des solutions très efficaces et sûres en utilisant des méthodes de recherche de racines standard.
Avant de creuser trop profondément dans les choses, collectons quelques propriétés et conséquences de la fonction
Propriété 0 : est une fonction rationnelle de . (Cela ressort de la définition.) Conséquence 0 : aucune solution algébrique générale n'existera pour trouver la racine . En effet, il existe un problème de recherche de racines polynomial équivalent de degré et donc si n'est pas extrêmement petit (c'est-à-dire moins de cinq), aucune solution générale n'existera. Nous aurons donc besoin d'une méthode numérique. λdf λ
df(λ)−y=0 pp p
Propriété 1 : La fonction est convexe et décroissante sur . (Prenez les dérivés.) Conséquence 1 (a) : l'algorithme de recherche de racines de Newton se comportera très bien dans cette situation. Soit les degrés de liberté souhaités et la racine correspondante, c'est-à-dire . En particulier, si nous commençons avec une valeur initiale (donc, ), alors la séquence d'itérations de Newton convergera de façon monotone vers le solution unique λ ≥ 0df λ≥0 y λ0 y=df(λ0) λ1<λ0 df(λ1)>y λ1,λ2,… λ0 .
λ1>λ0 λ2≤λ0 df df λ , cela fournit une bonne raison de préférer commencer à gauche de la racine souhaitée. Sinon, nous devons vérifier que l'étape de Newton n'a pas donné lieu à une valeur négative pour la racine estimée, ce qui peut nous placer quelque part dans une partie non convexe de .
Conséquence 1 (c) : Une fois que nous avons trouvé la racine pour certains et que nous recherchons ensuite la racine à partir de certains , en utilisant telle sorte que comme garantie initiale, nous commençons à la gauche de la deuxième racine. Ainsi, notre convergence est garantie d'être monotone à partir de là.df
y1 y2<y1 λ1 df(λ1)=y1
λ 0 y = d f ( λ 0 )
Conséquence 1 (b) : En outre, si nous , la première étape donnerait , d'où elle augmentera de façon monotone jusqu'à la solution par la conséquence précédente (voir la mise en garde au dessous de). Intuitivement, ce dernier fait suit parce que si nous commençons à droite de la racine, la dérivée est "trop" superficielle en raison de la convexité de et donc la première étape de Newton nous mènera quelque part à gauche de la racine. NB Puisque n'est pas en général convexe pour négatif
Propriété 2 : Des limites raisonnables existent pour donner des points de départ "sûrs". En utilisant des arguments de convexité et l'inégalité de Jensen, nous avons les limites suivantes Conséquence 2 : cela nous indique que la racine satisfaisant obéit Donc, jusqu'à une constante commune, nous avons pris en sandwich la racine entre les moyennes harmonique et arithmétique du .
Cela suppose que pour tout . Si ce n'est pas le cas, alors la même borne tient en considérant uniquement le positif et en remplaçant par le nombre de positifs . NB : Puisque supposant que tous les , alors , d'où les bornes sont toujours non triviales (par exemple, la borne inférieure est toujours non négative).di>0 i di p di df(0)=p di>0 y∈(0,p]
Voici un tracé d'un exemple "typique" de avec . Nous avons superposé une grille de taille 10 pour les degrés de liberté. Ce sont les lignes horizontales de l'intrigue. Les lignes vertes verticales correspondent à la borne inférieure de .df(λ) p=400 (⋆)
Un algorithme et un exemple de code R
Un algorithme très efficace étant donné une grille de degrés de liberté in consiste à les trier par ordre décroissant puis à trouver séquentiellement la racine de chacun, en utilisant la racine précédente comme point de départ pour les éléments suivants 1. Nous pouvons affiner cela en vérifiant si chaque racine est supérieure à la borne inférieure de la racine suivante, et sinon, nous pouvons commencer l'itération suivante à la borne inférieure à la place.y1,…yn (0,p]
Voici un exemple de code
R
, sans aucune tentative d'optimisation. Comme on le voit ci-dessous, il est encore assez rapide même s'ilR
est - pour le dire poliment - horriblement, terriblement, terriblement lent aux boucles.Ci-dessous se trouve l'algorithme complet final qui prend une grille de points, et un vecteur du ( pas !).di d2i
Exemple d'appel de fonction
la source
De plus, il existe deux méthodes qui permettront de calculer efficacement le chemin de régularisation complet:
Ce qui précède sont tous des packages R, car vous utilisez Python, scikit-learn contient des implémentations pour ridge, lasso et élastique net.
la source
ols
fonction durms
package R peut utiliser l'optimisation numérique pour trouver la pénalité optimale à l'aide d'un AIC efficace. Mais il faut prévoir la peine maximale qui n'est pas toujours facile.Une alternative possible selon la source ci-dessous semble être:
Source: https://onlinecourses.science.psu.edu/stat857/node/155
la source