Résolution de paramètres de régression dans une descente en forme fermée par rapport à un gradient

72

Dans son cours d'apprentissage automatique, Andrew Ng introduit la régression linéaire et la régression logistique, et montre comment ajuster les paramètres du modèle à l'aide de la méthode de la méthode de Newton et de la méthode de descente par gradient.

Je sais que la descente sur gradient peut être utile dans certaines applications d’apprentissage automatique (par exemple, une backpropogation), mais dans le cas plus général, existe-t-il une raison quelconque pour laquelle vous ne résolveriez pas les paramètres sous forme fermée, c’est-à-dire en prenant la dérivée de la fonction de coût et la résolution via Calcul?

Quel est l’avantage d’utiliser un algorithme itératif tel que la descente de gradient par rapport à une solution de forme fermée en général, lorsqu’il en existe un?

Jeff
la source
9
Je ne pense pas qu'il existe une solution de forme fermée pour la MLE des paramètres de régression dans la plupart des glms (par exemple, la régression logistique). La régression linéaire avec des erreurs normales est une exception.
Macro
5
Intéressant ... Cela signifie-t-il que différents logiciels de statistiques peuvent donner des réponses différentes pour la régression logistique en fonction, par exemple, des paramètres initiaux, du nombre d'itérations, de plusieurs minima locaux, etc. - ou existe-t-il une procédure conventionnelle qui suivre? (Bien que je sois sûr que toutes les différences, si elles existent, sont minimes dans la plupart des cas)
Jeff
3
(+1) À votre question et à votre commentaire, Jeff. Les GLM utilisant le lien canonique (comme la régression logistique) bénéficient des propriétés intéressantes de la convexité. Il peut y avoir plus d'un algorithme pour résoudre de tels problèmes, mais le résultat de base est que (modulo quelques détails assez mineurs), des algorithmes numériques bien implémentés donneront des résultats cohérents entre eux.
cardinal
2
Personnellement, je n'aime pas le cours d'Andrew Ng parce qu'il a amené les gens à croire que la régression linéaire est un "apprentissage automatique".
Digio

Réponses:

86

À moins que la solution de forme fermée ne soit extrêmement coûteuse à calculer, c'est généralement la solution à suivre lorsqu'elle est disponible. cependant,

  1. Pour la plupart des problèmes de régression non linéaire, il n'y a pas de solution sous forme fermée.

  2. Même en régression linéaire (l'un des rares cas où une solution sous forme fermée est disponible), il peut être impossible d'utiliser la formule. L'exemple suivant montre une façon par laquelle cela peut se produire.

Pour une régression linéaire sur un modèle de la forme , où est une matrice avec rang de colonne complet, la solution des moindres carrés,y=XβX

β^=argminXβy2

est donné par

β^=(XTX)1XTy

Imaginons maintenant que soit une matrice très grande mais clairsemée. Par exemple, peut avoir 100 000 colonnes et 1 000 000 de lignes, mais seulement 0,001% des entrées dans sont non nulles. Il existe des structures de données spécialisées pour stocker uniquement les entrées non nulles de ces matrices creuses. XXX

Imaginez également que nous ne sommes pas chanceux et que est une matrice assez dense avec un pourcentage beaucoup plus élevé d'entrées non nulles. Stocker une matrice dense de éléments de 100 000 sur 100 000 nécessiterait alors nombres à virgule flottante (à 8 octets par nombre, cela équivaut à 80 gigaoctets.) mais un superordinateur. De plus, l'inverse de cette matrice (ou plus communément d'un facteur de Cholesky) aurait également tendance à avoir des entrées généralement non nulles. XTXXTX1×1010

Cependant, il existe des méthodes de résolution du problème des moindres carrés qui ne nécessitent pas plus de stockage que , , et et ne jamais former explicitement le produit de la matrice . Xyβ^XTX

Dans cette situation, l'utilisation d'une méthode itérative est beaucoup plus efficace sur le plan des calculs que l'utilisation de la solution de forme fermée au problème des moindres carrés.

Cet exemple peut paraître absurdement volumineux. Cependant, dans la recherche en tomographie sismique, les méthodes itératives sur ordinateurs de bureau résolvent systématiquement les problèmes épars de moindres carrés de cette taille.

Brian Borchers
la source
4
Il convient également de mentionner qu’il existe également des problèmes d’exactitude numérique qui peuvent rendre l’utilisation de la solution de forme fermée au problème des moindres carrés déconseillée. Cependant, cela nécessiterait une discussion sur le mauvais conditionnement qui semble dépasser l'entendement actuel de l'affiche originale.
Brian Borchers
17
n'hésitez pas à poster une réponse car vous ne pensez pas que je vais la comprendre. D'abord, il ne me fera pas de mal de fournir plus d'informations, même si cela me demande quelques recherches pour pouvoir les comprendre. deuxièmement, le modèle stackexchange suppose que cette question et cette réponse bénéficieront aux autres à l'avenir. En d'autres termes, ne répondez pas à la question en fonction de ce que le PO connaît, à votre avis, sinon vous ne rendrez pas service aux autres.
Jeff
2
@Brian, je pense que votre commentaire touche plus au cœur du problème et est un peu en contradiction avec la première phrase de la réponse. Je ne pense pas qu'aucun logiciel des moindres carrés (dans son esprit) utilise la solution fermée. :)
cardinal
4
Cardinal - en pratique, il est préférable d'utiliser la factorisation QR ou SVD pour résoudre des problèmes de moindres carrés à petite échelle. Je dirais qu'une solution utilisant l'une de ces factorisations orthogonales est également une "solution de forme fermée" par rapport à l'utilisation d'une technique itérative telle que LSQR. Je n’ai pas approfondi cette question dans ma réponse car elle attire inutilement l’attention de mon sujet principal.
Brian Borchers
2
Mauvais conditionnement? Solution de manuel fermée? J'aime l'odeur des chiffres d'état au carré le matin. Vous avez un grand numéro de condition? Pourquoi ne pas le cadrer et le rendre encore plus grand? Vous n'avez pas un si grand nombre de condition? Pourquoi ne pas le confronter et le rendre grand.
Mark L. Stone
2

Plusieurs articles ont été publiés sur l'apprentissage automatique (ML) et la régression. ML n'est pas nécessaire pour résoudre les moindres carrés ordinaires (MCO), car il implique une opération en sandwich matricielle en une étape pour résoudre un système d'équations linéaires - c'est-à-dire, . Le fait que tout soit linéaire signifie que seule une opération en une étape est nécessaire pour résoudre les coefficients. La régression logistique est basée sur la maximisation de la fonction de vraisemblance , qui peut être résolue à l'aide de Newton-Raphson ou d'autres méthodes d'ascension sur gradient ML, de métaheuristiques (ascension, algorithmes génétiques, intelligence en essaim, optimisation de colonies, etc.) . β=(XTX)1XTyL=ipi

En ce qui concerne la parcimonie, l’utilisation de ML pour MLS serait une perte de temps car l’apprentissage itératif est inefficace pour la résolution des MLS.

Revenons maintenant à votre vraie question sur les approches dérivées par rapport aux approches ML pour la résolution de problèmes fondés sur les gradients. Spécifiquement, pour la régression logistique, l’approche de Newton-Raphson sur la descente de gradient (basée sur les dérivées) est couramment utilisée. Newton-Raphson exige que vous connaissiez la fonction objectif et ses dérivées partielles pour chaque paramètre (continu dans la limite et différentiable). ML est principalement utilisé lorsque la fonction objectif est trop complexe ("narly") et que vous ne connaissez pas les dérivées. Par exemple, un réseau de neurones artificiels (RNA) peut être utilisé pour résoudre un problème d'approximation de fonction ou de classification supervisée lorsque la fonction n'est pas connue. Dans ce cas, l'ANN est la fonction.

Ne commettez pas l'erreur d'utiliser les méthodes ML pour résoudre un problème de régression logistique, simplement parce que vous le pouvez. Pour la logistique, Newton-Raphson est extrêmement rapide et constitue la technique appropriée pour résoudre le problème. ML est couramment utilisé lorsque vous ne connaissez pas la fonction. (D'ailleurs, les ANN appartiennent au domaine de l'intelligence informatique, et non à ML).

JoleT
la source