Avons-nous besoin d'une descente de gradient pour trouver les coefficients d'un modèle de régression linéaire?

31

J'essayais d'apprendre l'apprentissage automatique en utilisant le matériel Coursera . Dans cette conférence, Andrew Ng utilise un algorithme de descente de gradient pour trouver les coefficients du modèle de régression linéaire qui minimiseront la fonction d'erreur (fonction de coût).

Pour la régression linéaire, avons-nous besoin d'une descente de gradient? Il semble que je puisse différencier analytiquement la fonction d'erreur et la mettre à zéro pour résoudre les coefficients; Est-ce correct?

regression machine-learning linear-model gradient-descent Victor
la source
3
Les modèles linéaires ont été décemment bien gérés depuis les années 1700. Il existe une tonne de façons de les gérer qui ne nécessitent pas de descente en gradient (GD). Il existe des modèles non linéaires où la plupart de ces méthodes tombent à plat sur leur visage. Andrew vous fait utiliser une méthode peu familière mais très utile contre un problème très simple afin que vous puissiez déboguer votre approche. Lorsque vous êtes bon avec la méthode, vous pouvez l'appliquer aux problèmes étonnamment non linéaires pour lesquels GD est la seule méthode pour obtenir des résultats.
EngrStudent
10
Non, vous n'avez pas besoin d'utiliser des approches comme la descente de gradient (ce n'est pas la seule méthode d'optimisation, en tout cas). Vous pouvez en effet le résoudre analytiquement, comme vous le suggérez; vous différenciez par rapport à chaque paramètre, vous obtenez donc une équation par paramètre. Mais il est utile de résoudre des problèmes simples qui peuvent être résolus autrement. si vous connaissez déjà la réponse, vous pouvez être sûr lorsque vous obtenez la bonne réponse avec une descente en gradient.
Glen_b -Reinstate Monica
Si la fonction de coût est la pénalité quadratique («distance») habituelle, il existe une solution de forme fermée. Cependant, la descente en pente est généralement beaucoup plus rapide, c'est pourquoi elle est généralement utilisée.
aginensky
De plus, la descente de gradient peut être utilisée pour trouver des solutions numériques à des problèmes qui sont insolubles analytiquement. Je soupçonne qu'il utilise la descente en pente dès le début pour s'y habituer. Je crois qu'il utilise ensuite la descente en gradient avec des réseaux de neurones. Inutile de dire que la situation du réseau neuronal est plus compliquée. Je pense que d'une situation pédagogique, après les avoir vu auparavant, avec des modèles linéaires, la descente de gradient pour une utilisation avec des réseaux de neurones semble plus raisonnable.
aginensky
3
Merci d'avoir posté le lien vers les vidéos d'André Ng que j'ai regardées plusieurs fois. Je le savais déjà, mais pas à l'extrême, mais c'est effrayant de voir ce que la grande majorité des gens qui "apprennent" l'optimisation apprennent, sans parler de ce que certains au moins apprennent sur l'informatique statistique. Gene Golub, LE pionnier de l'informatique et de l'utilisation de SVD, se retournerait dans sa tombe s'il savait ce qui est enseigné maintenant dans son département d'informatique de Stanford. La vidéo la plus drôle est youtube.com/watch?v=B3vseKmgi8E , qui recommande et compare les 2 pires algorithmes pour les moindres carrés
Mark L. Stone

Réponses:

43

Les moindres carrés linéaires peuvent être résolus par

0) Utilisation d'un solveur de moindres carrés linéaires de haute qualité, basé sur SVD ou QR, comme décrit ci-dessous, pour les moindres carrés linéaires non contraints, ou basé sur une version de programmation quadratique ou d'optimisation conique pour les moindres carrés liés ou linéairement contraints, comme décrit ci-dessous. Un tel solveur est prêt à l'emploi, soumis à de nombreux tests et prêt à l'emploi - utilisez-le.

1) SVD, qui est la méthode la plus fiable et la plus précise numériquement, mais prend également plus de calcul que d'alternatives. Dans MATLAB, la solution SVD du problème des moindres carrés linéaires non contraints A * X = b est pinv (A) * b, ce qui est très précis et fiable.

2) QR, qui est assez fiable et numériquement précis, mais pas autant que SVD, et est plus rapide que SVD. Dans MATLAB, la solution QR du problème des moindres carrés linéaires non contraints A * X = b est A \ b, ce qui est assez précis et fiable, sauf lorsque A est mal conditionné, c'est-à-dire qu'il a un grand nombre de conditions. A \ b est plus rapide à calculer que pinv (A) * b, mais pas aussi fiable ou précis.

3) Formation des équations normales (TERRIBLE du point de vue de la fiabilité et de la précision numérique, car elle évalue le nombre de conditions, ce qui est une très mauvaise chose à faire) et

3a) résolution par factorisation de Cholesky (pas bonne)

3b) matrice à inversion explicite (HORRIBLE)

4) Résolution d'un problème de programmation quadratique ou d'un problème de cône de second ordre

4a) Résolvez en utilisant un logiciel de programmation quadratique de haute qualité. Ceci est fiable et numériquement précis, mais prend plus de temps que SVD ou QR. Cependant, il est facile d'ajouter des contraintes linéaires liées ou générales, ou des termes de pénalisation ou de régularisation linéaires ou quadratiques (deux normes) à la fonction objectif, tout en résolvant le problème à l'aide du logiciel de programmation quadratique.

4b) Résoudre un problème de cône de second ordre à l'aide d'un logiciel d'optimisation conique de haute qualité. Les remarques sont les mêmes que pour le logiciel de programmation quadratique, mais vous pouvez également ajouter des contraintes linéaires liées ou générales et d'autres contraintes coniques ou termes de fonction objective, tels que des termes de pénalité ou de régularisation dans diverses normes.

5) Résolvez en utilisant un logiciel d'optimisation non linéaire à usage général de haute qualité. Cela peut toujours bien fonctionner, mais sera généralement plus lent que le logiciel de programmation quadratique ou d'optimisation conique, et peut-être pas aussi fiable. Cependant, il peut être possible d'inclure non seulement des contraintes linéaires liées et générales, mais également des contraintes non linéaires dans l'optimisation des moindres carrés. Peut également être utilisé pour les moindres carrés non linéaires et si d'autres termes non linéaires sont ajoutés à la fonction objectif.

6) Résolvez en utilisant des algorithmes d'optimisation non linéaires à usage général -> NE FAITES JAMAIS CECI.

7) Résoudre en utilisant LE PIRE algorithme d'optimisation non linéaire à usage général qui existe, c'est-à-dire la descente de gradient. N'utilisez ceci que si vous voulez voir à quel point une méthode de solution peut être mauvaise et peu fiable. Si quelqu'un vous dit d'utiliser la descente de gradient pour résoudre les problèmes des moindres carrés linéaires

7 i) En savoir plus sur le calcul statistique auprès de quelqu'un qui en sait quelque chose

7 ii) Apprenez l'optimisation de quelqu'un qui en sait quelque chose.

Mark L. Stone
la source
Bon post, pourquoi pensez-vous que Cholesky n'est pas bon étant donné que votre système est PD cependant? (et pas avec un numéro de condition ridicule) BTW, je pense que vous voulez dire (ou ajouter) la notion d'inverse généralisé (utilisé principalement à des fins éducatives évidemment) soit au point "SVD" soit au point "explicitement inversant".
usεr11852 dit Réintégrer Monic le
2
BTW, il est ridicule de voir à quelle fréquence les matrices avec des nombres de condition très élevés sont générées, en particulier par les masses non lavées (c'est-à-dire la majorité des gens qui font des moindres carrés linéaires, en particulier compte tenu de la démocratisation de l'accès), qui ne sont pas à l'écoute.
Mark L. Stone
1
mldivide, c.-à-d. la barre oblique inverse, c'est-à-dire que \ utilise QR lorsque m ~ = n (moindres carrés), comme je l'ai dit dans la 2ème phrase de mon paragraphe (2) ci-dessus. Vous seriez surpris de voir à quel point il y a de la merde dans MATLAB - pas seulement dans les boîtes à outils, dont certaines sont absolument horribles, mais dans une moindre mesure dans certaines des fonctions de base également.
Mark L. Stone
1
@ MarkL.Stone, excellente réponse! pourriez-vous s'il vous plaît expliquer un peu plus pourquoi il n'est pas conseillé d'utiliser la descente de gradient pour résoudre le moindre carré! (à ma connaissance, c'est juste une approche itérative par rapport aux autres (approches de solution de direction) que vous avez mentionnées ci-dessus). De plus, pourriez-vous également commenter le problème: "si j'ai n> = 30 000 fonctionnalités pour un problème, la méthode d'équation normale sera très lente car inverser la matrice n * n serait terrible! D'autre part, GD fonctionnerait dans ce cas joli! toutes les pensées sur la façon dont SVD et QR fonctionneront ". toute suggestion serait utile.
anu
1
@ anu N'utilisez la descente en pente qu'en dernier recours. et ce ne serait que si le problème était trop important pour être résolu par SVD ou QR. Ne formez jamais les équations normales, et encore moins inverser explicitement une matrice pour résoudre les équations normales, JAMAIS. 30 000 fonctionnalités ne semblent pas très nombreuses de nos jours.
Mark L. Stone
0

La recherche de coefficients d'un modèle linéaire est techniquement le processus de recherche de solutions à un ensemble d'équations linéaires .

Pour le calcul de telles solutions, beaucoup optimization techniquesont été développées et en Gradient Descentfait partie.
Ainsi, Gradient Descent n'est pas le seul moyen de le faire.

Andrew Ng l'utilise dans le cours parce qu'il est simple à comprendre, sans traiter d'algèbre linéaire avancée et de calcul numérique.

Vikas Raturi
la source
Bien que ce ne soit pas faux, je pense que votre réponse passe à côté de la situation en se concentrant sur un cas non standard. La grande majorité des modèles de régression linéaire sont ajustés en utilisant la décomposition QR en utilisant une solution sous forme fermée. GD-gradient decent- est utilisé comme exemple pour introduire des méthodes plus avancées (par exemple SGD- stochastique GD).
usεr11852 dit Réintégrer Monic le
Pouvez-vous expliquer en quoi consiste la décomposition QR?
Victor
3
Vous voulez résoudre . Étant donné où est triangulaire supérieur et est orthogonal, qui peut être résolu par une substitution en arrière (c'est-à-dire rapide) car est triangulaire et . Pour les très grandes matrices (millions d'entrées), cela peut être plus cher qu'un solveur itératif, par exemple. . Comme la plupart des gens n'ont pas de très grandes matrices, la décomposition QR est meilleure. En général, la décomposition QR a façonné le monde numérique; SIAM l'a sélectionné comme l'un des 10 meilleurs algorithmes du 20e siècle. Ax=bA=QRRQAx=b⇒QRx=b⇔Rx=QTbRQTQ=ISGD
usεr11852 dit Réintégrer Monic
@ usεr11852 oui bien sûr. Cela parce que, je voulais garder la réponse simple, afin d'éviter des concepts tels que la décompostion QR, restant pertinents dans le domaine du niveau de cours de Ng.
Vikas Raturi
3
QR était l'un des 10 meilleurs algorithmes du 20e siècle. Mais le temps passe, et même si les algorithmes efficaces pour calculer la SVD remontent aux années 1960, il faut se pencher sur l'importance des domaines d'application. Par conséquent, je crois que SVD est l'algorithme TOP du 21e siècle. Franchement, avez-vous déjà entendu parler de l'utilisation de QR pour recommander des films? Non, SVD est utilisé pour cette application critique. SVD est clairement l'algorithme de choix lorsque Twitter envoie des recommandations non sollicitées à de vieux connaisseurs conservateurs quant aux célébrités adolescentes à suivre. Voyons voir QR faire ça !!!
Mark L. Stone