Un article intitulé «Calcul précis de la variance courante», disponible à l' adresse http://www.johndcook.com/standard_deviation.html, montre comment calculer la moyenne courante, la variance et les écarts types.
Existe-t-il des algorithmes dans lesquels les paramètres d'un modèle de régression linéaire ou logistique peuvent être mis à jour de manière "dynamique" de manière similaire à chaque nouvel enregistrement de formation fourni?
Réponses:
Les coefficients de régression linéairey= a x + b sont a = c o v ( x , y) / v a r ( x ) et b=mean(y)−a⋅mean(x) .
Donc, tout ce dont vous avez besoin, c’est d’une méthode incrémentale pour calculercov(x,y) . A partir de cette valeur et de la variance de x et de la moyenne de y et de x vous pouvez calculer les paramètres a et b . Comme vous le verrez dans le pseudo-code donné ci-dessous, le calcul incrémental de cov(x,y) est très similaire au calcul incrémental de var(x) . Cela ne devrait pas être une surprise parce que var(x)=cov(x,x) .
Voici le pseudo-code que vous recherchez probablement:
J'ai trouvé cette question en recherchant un algorithme équivalent calculant de manière incrémentielle une régression à variables multiples telle queR=(X′X)−1X′Y sorte que XR=Y+ϵ
la source
Pour vos deux exemples spécifiques:
Régression linéaire Le document "Régression linéaire en ligne et son application à l'apprentissage par renforcement basé sur un modèle" de Alexander Strehl et Michael Littman décrit un algorithme appelé "Régression linéaire KWIK" (voir l'algorithme 1) qui fournit une approximation de la solution de régression linéaire à l'aide de mises à jour incrémentielles. . Notez que ceci n’est pas régularisé (c’est-à-dire que ce n’est pas une régression de crête). Je suis à peu près sûr que la méthode de Strehl & Littman ne peut s'étendre à ce paramètre.
Régression logistique
Ce fil apporte un peu de lumière sur le sujet. Citant:
Il existe cependant d’autres méthodes de régression en ligne (ou incrémentielles) que vous pourriez souhaiter examiner, par exemple la régression à projection pondérée localement (LWPR)
la source
En principe général:
0) vous conservez les statistiques suffisantes et les estimations actuelles du BC
1) lorsque vous obtenez de nouvelles données, mettez à jour les statistiques suffisantes et les estimations
2) Lorsque vous ne disposez pas de statistiques suffisantes, vous devez utiliser toutes les données.
3) En règle générale, vous n'avez pas de solutions fermées; utilisez les MLE précédents comme point de départ, utilisez une méthode d’optimisation pratique pour trouver le nouvel optimum à partir de là. Vous devrez peut-être expérimenter un peu pour trouver les approches qui offrent les meilleurs compromis pour vos types de problèmes particuliers.
Si votre problème a une structure spéciale, vous pouvez probablement l'exploiter.
Quelques références potentielles pouvant ou non avoir une certaine valeur:
McMahan, HB et M. Streeter (2012),
Problème ouvert: de meilleures limites pour la régression logistique en ligne ,
JMLR: compte rendu des ateliers et des conférences , vol 23, 44.1–44.3.
Penny, WD et SJ Roberts (1999),
Régression logistique dynamique ,
Actes IJCNN '99
la source
Ajoutant à la réponse de tdc, il n’existe aucune méthode connue pour calculer des estimations exactes des coefficients à un moment donné, avec juste un temps constant par itération. Cependant, il existe des alternatives raisonnables et intéressantes.
Le premier modèle à examiner est le cadre d’ apprentissage en ligne . Dans ce paramètre, le monde annonce une valeur de x, votre algorithme prédit une valeur pour y, le monde annonce la valeur vraie y 'et votre algorithme subit une perte l (y, y'). Pour ce paramètre, il est connu que des algorithmes simples (descente de gradient et gradient exponentiel, entre autres) permettent d'obtenir un regret sous-linéaire. Cela signifie qu'au fur et à mesure que vous voyez plus d'exemples, le nombre d'erreurs supplémentaires commises par votre algorithme (par rapport au meilleur prédicteur linéaire possible) n'augmente pas avec le nombre d'exemples. Cela fonctionne même dans des contextes contradictoires. Il existe un bon article expliquant une stratégie populaire pour prouver ces limites de regret. Les notes de cours de Shai Shalev-Schwartz sont également utiles.
Il existe une extension du paramètre d'apprentissage en ligne appelée paramètre bandit où votre algorithme se voit uniquement attribuer un numéro représentant son erreur (et aucun pointeur vers la bonne réponse). De manière impressionnante, de nombreux résultats de l’apprentissage en ligne se retrouvent dans ce contexte, sauf qu’il faut ici explorer et exploiter, ce qui crée toutes sortes de défis intéressants.
la source
D'autres réponses ont mis en évidence le monde de l'apprentissage automatique, et c'est certainement un endroit où ce problème a été traité.
Cependant, une autre approche qui pourrait mieux convenir à vos besoins est l’utilisation de la factorisation QR avec des mises à jour de rangs faibles. Les approches pour le faire et l’utiliser pour résoudre les problèmes de moindres carrés sont présentées dans:
Mise à jour de la factorisation QR et du problème des moindres carrés par Hammerling et Lucas.
la source
la source
Ceci est à ajouter à la réponse @chmike.
La méthode semble être similaire à l'algorithme en ligne de l'écart type de BP Welford, qui calcule également la moyenne. John Cook donne une bonne explication ici . Tony Finch en 2009 fournit une méthode pour une moyenne mobile exponentielle et un écart type:
Observez la réponse précédemment publiée et développez-la pour y inclure une fenêtre en mouvement exponentiel:
Dans le "code" ci-dessus, désiréAlpha pourrait être mis à 0 et si tel était le cas, le code fonctionnerait sans pondération exponentielle. Il peut être suggéré de définir désiréeAlpha sur 1 / désiréeWindowSize comme suggéré par Modified_moving_average pour une taille de fenêtre en mouvement.
Question secondaire: des calculs alternatifs ci-dessus, quels commentaires sur ce qui est le mieux du point de vue de la précision?
Les références:
chmike (2013) https://stats.stackexchange.com/a/79845/70282
Cook, John (nd) Calculer avec précision la variance en cours d'exécution http://www.johndcook.com/blog/standard_deviation/
Finch, Tony. (2009) Calcul incrémental de la moyenne pondérée et de la variance. https://fanf2.user.srcf.net/hermes/doc/antiforgery/stats.pdf
Wikipédia. (nd) Algorithme en ligne de Welford https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm
la source