Pourquoi ne pas utiliser la troisième dérivée pour l'optimisation numérique?

29

Si les Hessois sont si bons pour l'optimisation (voir par exemple la méthode de Newton ), pourquoi s'arrêter là? Utilisons les troisième, quatrième, cinquième et sixième dérivés? Pourquoi pas?

écho
la source
11
Une fois que vous avez trouvé l'optimum, pourquoi chercher plus loin? En effet, qu'essayez-vous vraiment de demander? Quelle est votre question statistique?
whuber
2
Dans de nombreux cas, la distribution limite des estimations qui résolvent des équations d'estimation optimales ou minimisent les fonctions objectives sont conjointement normales, de sorte qu'elles peuvent être entièrement caractérisées par leurs premier et deuxième moments.
AdamO
3
Si vous pouvez faire quelque chose, cela ne signifie pas que vous devriez le faire. Les dérivés d'ordre supérieur sont de plus en plus sensibles au bruit.
Vladislavs Dovgalecs
6
Je vote pour clore cette question comme hors sujet car il ne s'agit pas de statistiques. Il s'agit d'optimisation numérique
Aksakal
11
Vous n'avez pas fait de percée scientifique. Halley vous a battu d'environ 3 1/4 siècles. Halley, E., 1694, "Une méthode nouvelle, exacte et facile de trouver les racines de toutes les équations en général, et cela sans aucune réduction préalable" Philos. Trans. Roy. Soc. Londres, 18, 136-145. Les méthodes de dérivation 3e pour l'optimisation existent et sont étudiées depuis de nombreuses années, mais n'ont pas atteint une grande popularité. Si elle est bien implémentée, son plus grand avantage peut être une augmentation de la robustesse par rapport à une méthode de Newton bien implémentée. Cela peut être avantageux pour les problèmes les plus désagréables.
Mark L. Stone

Réponses:

31

J'interprète la question comme étant "Pourquoi la méthode de Newton n'utilise-t-elle que des dérivées premières et secondes, pas des dérivées tierces ou supérieures?"

En fait, dans de nombreux cas, le passage au troisième dérivé aide; Je l'ai déjà fait avec des trucs personnalisés. Cependant, en général, aller vers des dérivés plus élevés ajoute de la complexité de calcul - vous devez trouver et calculer tous ces dérivés, et pour les problèmes multivariés, il y a beaucoup plus de dérivées tierces que de premières dérivées! - qui dépasse de loin les économies de nombre de pas que vous obtenez, le cas échéant. Par exemple, si j'ai un problème tridimensionnel, j'ai 3 premières dérivées, 6 secondes dérivées et 10 troisièmes dérivées, donc passer à une version de troisième ordre fait plus que doubler le nombre d'évaluations que je dois faire (de 9 à 19), sans parler de la complexité accrue du calcul de la direction / taille des pas une fois que j'ai fait ces évaluations, mais ne réduira certainement pas le nombre de pas que je dois faire de moitié.

Maintenant, dans le cas général avec variables, la collection de n t h dérivées partielles numérotera , donc pour un problème avec cinq variables, le nombre total de troisième, quatrième et les cinquièmes dérivées partielles seront égales à 231, soit une augmentation de plus de 10 fois par rapport au nombre de première et deuxième dérivées partielles (20). Vous devriez avoir un problème qui est très, très proche d'un polynôme du cinquième ordre dans les variables pour voir une réduction suffisamment importante du nombre d'itérations pour compenser cette charge de calcul supplémentaire.knth(k+n-1k-1)

jbowman
la source
3
Pourriez-vous expliquer comment vous utilisez des dérivés plus élevés?
whuber
5
@whuber Ce à quoi l'OP fait référence, je dois l'admettre très clairement, c'est la méthode d'optimisation de Newton. La question est vraiment "Pourquoi la méthode de Newton n'utilise-t-elle que des dérivées première et deuxième, pas des dérivées troisième ou supérieure?". C'est hors sujet et on ne sait pas exactement ce qu'il demande, mais j'ai pensé que je donnerais une réponse plutôt que de voter pour clore pour une raison ou une autre.
jbowman
4
+1 Je pense que c'est une bonne réponse, mais elle pourrait être améliorée en montrant ce que vous faites en fonction de l'expansion de Taylor.
Matthew Drury
8
Comme un de mes professeurs - un consultant très prospère aussi - nous a dit une fois: "Chaque fois que vous pensez avoir compris comment construire une meilleure souricière, essayez de comprendre pourquoi les 1000 personnes qui ont eu exactement la même idée avant de le mettre sur le marché. " L'intérêt de Newton est de sauver le calcul - sinon, nous ferions simplement une recherche exhaustive. Je vous assure que l'ajout d'une troisième dérivée à un problème tridimensionnel paiera très, très rarement le doublement du calcul à chaque étape avec des itérations considérablement réduites à moins que la fonction ne soit ~ un cube.
jbowman
9
Non, ce n'est pas - c'est un commentaire un peu plus profond qu'il n'y paraît. Le point est double: la plupart des idées qui semblent bonnes au premier abord ne le sont pas, pour des raisons qui ne sont pas du tout évidentes, et la véritable clé d'une rupture n'est peut-être pas l'idée elle-même, mais quelque chose qui surmonte ou contourne le défaut l'idée. Ce raisonnement, en effet, le souligne et vous dit de rechercher les faiblesses de l'idée. Il ne s'agit pas d'abandonner, il s'agit de réfléchir aux choses, et avec un œil critique à cela.
jbowman
22

Je ne vois pas vraiment quel est l'aspect statistique de cette question, je vais donc répondre à la partie optimisation.

La convergence comporte deux parties: le coût d'itération et le nombre d' itérations

Presque toutes les réponses ici se concentrent uniquement sur le coût d'itération et ignorent le nombre d' itérations . Mais les deux comptent. Une méthode qui itère en 1 nanoseconde mais qui prend itérations pour converger ne vous sera d'aucune utilité. Et une méthode qui explose n'aidera pas non plus, peu importe le coût de son itération.dix20

Voyons ce qui se passe.

Alors: pourquoi ne pas utiliser> des dérivés de second ordre?

En partie parce que (et cela est vrai aussi pour le 2ème ordre, mais plus à ce sujet dans un peu):

Les méthodes d'ordre supérieur ne convergent généralement plus rapidement que lorsqu'elles sont proches de l'optimum .

En revanche, ils explosent plus facilement lorsqu'ils sont plus éloignés de l'optimum!

(Bien sûr, ce n'est pas toujours vrai; par exemple, un quadratique convergera en une étape avec la méthode de Newton. Mais pour les fonctions arbitraires dans le monde réel qui n'ont pas de belles propriétés, cela est généralement vrai.)

Cela signifie que lorsque vous êtes plus éloigné de l'optimum, vous voulez généralement une méthode de faible ordre (lire: premier ordre). Ce n'est que lorsque vous êtes proche que vous souhaitez augmenter l'ordre de la méthode.

Alors pourquoi s'arrêter au 2ème ordre lorsque vous êtes près de la racine?

Parce que le comportement de convergence "quadratique" est vraiment "assez bon"!

Pour voir pourquoi, vous devez d'abord comprendre ce que signifie «convergence quadratique» .

Mathématiquement, la convergence quadratique signifie que, si est votre erreur à l'itération , alors ce qui suit est finalement vrai pour une constante : k cϵkkc

|ϵk+1|c |ϵk|2

En clair, cela signifie que, une fois que vous êtes proche de l'optimum (important!), Chaque étape supplémentaire double le nombre de chiffres de précision .

Pourquoi? C'est facile à voir avec un exemple: pour et , vous avez , , etc., ce qui est ridiculement rapide . (C'est super exponentiel !)| ϵ 1 | = 0,1 | ϵ 2 | 0,01 | ϵ 3 | 0,0001c=1|ϵ1|=0,1|ϵ2|0,01|ϵ3|0,0001

Pourquoi ne pas s'arrêter au 1er ordre plutôt qu'au 2e ordre?

En fait, les gens le font souvent lorsque les dérivés de second ordre deviennent trop chers. Mais la convergence linéaire peut être très lente. Par exemple, si vous obtenez vous aurez peut-être besoin de 10 000 000 d'itérations avec convergence linéaire pour obtenir , mais seulement 23 itérations avec convergence quadratique. Vous pouvez donc voir pourquoi il y a une différence drastique entre la convergence linéaire et quadratique. Ce n'est pas le cas pour la convergence de 2ème et 3ème ordre, par exemple (voir paragraphe suivant).| ϵ | < 0,5ϵk=0,9999999|ϵ|<0,5

À ce stade, si vous connaissez l'informatique, vous comprenez qu'avec la convergence de second ordre, le problème est déjà résolu . Si vous ne voyez pas pourquoi, voici pourquoi: il n'y a rien de pratique à gagner en triplant le nombre de chiffres à chaque itération au lieu de le doubler - qu'est-ce que ça va vous acheter? Après tout, dans un ordinateur, même un doublenombre de précision a 52 bits de précision, soit environ 16 chiffres décimaux. Peut-être que cela réduira le nombre d'étapes dont vous avez besoin de 16 à 3 ... ce qui sonne bien, jusqu'à ce que vous vous rendiez compte que cela vient au prix d'avoir à calculer des dérivées tierces à chaque itération, où se trouve la malédiction de la dimensionnalitévous frappe fort. Pour un problème à dimensions, vous venez de payer un facteur de pour obtenir un facteur de , ce qui est stupide. Et dans le monde réel, les problèmes ont au moins des centaines de dimensions (voire des milliers voire des millions), pas seulement ! Ainsi, vous gagnez peut-être un facteur de 20 en payant un facteur de, disons, 20 000 ... à peine un compromis judicieux.6 5 66656

Mais encore une fois: rappelez-vous que la malédiction de la dimensionnalité est la moitié de l'histoire .

L'autre moitié est que vous obtenez généralement un comportement pire lorsque vous êtes loin de l'optimum, ce qui affecte généralement le nombre d'itérations que vous devez faire.

Conclusion

Dans un cadre général, les méthodes d'ordre supérieur à 2 sont une mauvaise idée. Bien sûr, si vous pouvez apporter des hypothèses supplémentaires utiles à la table (par exemple , peut - être vos données ne ressemblent à un polynôme haut degré, ou si vous avez des moyens de délimitation de l'emplacement de l'optimum, etc.), vous pouvez peut - être trouver qu'ils sont une bonne idée, mais ce sera une décision spécifique au problème, et non une règle générale à suivre.

Mehrdad
la source
Excellente réponse, mais je pense que le théorème d'Abel-Ruffini est un hareng rouge. Tout d'abord, nous parlons de problèmes multivariés, donc le calcul de zéros de polynômes univariés est tout au plus un sous-problème facile d'intérêt limité. Et, plus important encore, peu importe qu'il existe ou non une formule fermée pour la solution: dans la pratique, pour autant que je sache, les gens n'utilisent pas de formules fermées même pour les polynômes de degré 4. Ils sont tout simplement trop longs, compliqués et instables. Les zéros des polynômes sont calculés numériquement, en pratique (en utilisant QR sur la matrice associée).
Federico Poloni
@ FedericoPoloni: Oui, les mêmes pensées me sont venues à l'esprit quand j'ai décidé de le mettre. Je ne l'avais pas à l'origine ... Je pensais que je devrais peut-être le mettre comme juste un autre exemple de la raison pour laquelle des degrés plus élevés peuvent avoir problèmes inattendus. Mais je suppose que je vais le retirer à nouveau si cela ne sert à rien, merci pour le commentaire.
Mehrdad
@FedericoPoloni: PS pendant que nous sommes sur le sujet du calcul numérique, vous pourriez trouver les fonctions Sturm intéressantes (si vous n'en avez pas déjà entendu parler).
Mehrdad
7

Même le calcul de Hessians est un peu de travail:

H=[2FX122FX1X22FX1Xn2FX2X12FX222FX2Xn2FXnX12FXnX22FXn2].

Maintenant, voyez à quoi ressemble la dérivée troisième: Il s'agit d'une matrice tridimensionnelle. Voici à quoi ressemblent ses éléments:

H/X=[HX1HX2HXn]
(H/X)jejk=3FXjeXjXk

La dérivée de Sixième sera une matrice à six dimensions:

6FXjeXjXkXlXmXn

Habituellement, le compromis n'est pas favorable pour aller après supérieur à la Hesse. Je veux dire le compromis entre le gain potentiel de vitesse en utilisant des approximations d'ordre supérieur par rapport à l'amplification du bruit. Vous avez toujours du bruit dans les entrées parce que nous parlons d'applications statistiques. Ce bruit sera amplifié par les dérivés.

Si vous jouez au golf, l'analogie de l'optimisation consiste à balancer d'abord en essayant d'atteindre le green, ne vous inquiétez pas trop pour un trou. Une fois, sur le green, nous mettrons en visant un trou.

Aksakal
la source
4

En règle générale, lorsque vous analysez l'efficacité de ces algorithmes, vous trouverez des résultats tels qu'une étape d'un algorithme du quatrième ordre ayant à peu près la même efficacité que deux étapes d'un algorithme du deuxième ordre.

Ainsi, le choix de l'algorithme à utiliser est relativement simple: si une étape de l'algorithme du quatrième ordre prend deux fois plus de travail ou plus d'une étape de l'algorithme du deuxième ordre, vous devez utiliser ce dernier à la place.

C'est la situation typique pour ce type de méthodes: l'algorithme classique a le rapport travail / efficacité optimal pour les problèmes généraux. Bien qu'il existe des problèmes occasionnels où une approche d'ordre supérieur est inhabituellement facile à calculer et peut surpasser la variante classique, ils sont relativement rares.


la source
2

Vous pouvez considérer l'ordre des dérivées comme l'ordre d'une approximation polynomiale de la fonction. La plupart des routines d'optimisation reposent sur la convexité. Un polynôme quadratique sera convexe / concave partout alors qu'un polynôme de 3e ordre ou supérieur ne sera pas convexe partout. La plupart des routines d'optimisation reposent sur des approximations successives de fonctions convexes avec quadratique pour cette raison. Une approximation quadratique convexe nécessite d'imposer une condition de définition positive pour que le quadratique soit convexe.

Lucas Roberts
la source
3
Non, les quadratiques ne sont pas nécessairement convexes ou concaves (pensez à ). X2-y2
Dirk
@Dirk égal à quoi? X2-y2
Ovi
1
C'est une fonction quadratique mais ni convexe ni concave.
Dirk
@ Dirk oui vous avez raison, j'aurais dû ajouter une mise en garde semi-définie positive. J'ajouterai cela à ma réponse.
Lucas Roberts
1

Permettez-moi d'être le seul ici à défendre des méthodes de troisième ordre pour la convergence SGD, mais certainement pas dans tout l'espace ce qui aurait besoin de coefficients, mais par exemple dans une seule direction, qui n'a besoin que d'un seul coefficient supplémentaire si ayant déjà un modèle de 2e ordre dans cette direction.jem3/6

Pourquoi un modèle unidirectionnel de 3e ordre peut-il être avantageux? Par exemple, parce que près de zéro dérivée seconde dans cette direction signifie essentiellement deux scénarios alternatifs: plateau ou point d'inflexion - seul le premier nécessite une taille de pas plus grande, et la dérivée 3e permet de les distinguer.

Je crois que nous irons vers des méthodes hybrides multi-ordres: méthode du 2ème ordre dans un sous-espace de faible dimension, par exemple à partir de PCA de gradients récents, ce qui permet toujours une descente de gradient simultanée libre du 1er ordre vers une partie du gradient orthogonal à ce sous-espace ... et en plus J'ajouterais par exemple un modèle de troisième ordre pour une seule direction la plus pertinente.

Jarek Duda
la source