Pourquoi optimiser la probabilité maximale du journal au lieu de la probabilité

66

Dans la plupart des tâches d’apprentissage automatique où vous pouvez formuler une probabilité qui doit être maximisée, nous optimisons en fait la probabilité de au lieu de la probabilité de certains paramètres . Par exemple, dans l'entraînement à probabilité maximum, il s'agit généralement du log-vraisemblance. Lorsque vous faites cela avec une méthode de gradient, cela implique un facteur:plogpθ

logpθ=1ppθ

Voir ici ou ici pour quelques exemples.

Bien sûr, l'optimisation est équivalente, mais le gradient sera différent, de sorte que toute méthode basée sur le gradient se comportera différemment (en particulier les méthodes à gradient stochastique). Existe-t-il une quelconque raison pour laquelle le dégradé fonctionne mieux que le dégradé ?logpp

Albert
la source
3
vous devez remarquer que nous maximisons généralement la probabilité d’utilisation de dérivés. D'autre part, dans de nombreux cas, la condition d'indépendance est appliquée, ce qui signifie que la vraisemblance est le produit de certaines fonctions de densité de probabilité iid. De plus, le produit de nombreuses petites valeurs (dans l'intervalle [0,1]) donne une très petite valeur. Cela entraîne une difficulté de calcul.
TPArrow
@ AlejandroRodriguez consultez ma réponse ici pour plus de détails.
Paul

Réponses:

65

Les méthodes de dégradé fonctionnent généralement mieux en optimisant que car le gradient de est généralement plus bien mis à l’échelle . C'est-à-dire que sa taille reflète de manière cohérente et utile la géométrie de la fonction objectif, ce qui facilite la sélection d'une taille de pas appropriée et l'optimisation optimale en moins de pas.logp(x)p(x)logp(x)

Pour voir ce que je veux dire, comparons le processus d'optimisation de gradient pour et . En tout point , le gradient de estSi nous multiplions cela par , nous obtenons la taille de pas exacte nécessaire pour atteindre l'optimum global à l'origine, peu importe ce quep(x)=exp(x2)f(x)=logp(x)=x2xf(x)

f(x)=2x.
1/2xest. Cela signifie que nous n’avons pas à travailler trop pour avoir une bonne taille de pas (ou «taux d’apprentissage» dans le jargon du ML). Peu importe où se trouve notre objectif initial, nous fixons simplement notre pas à la moitié de la pente et nous serons à l'origine en une étape. Et si nous ne connaissons pas le facteur exact nécessaire, nous pouvons simplement choisir une taille de pas d'environ 1, faire un peu de recherche de ligne et nous trouverons très rapidement une bonne taille de pas, qui fonctionne bien, peu importe où. est. Cette propriété est robuste à la traduction et à la mise à l'échelle de . Bien que la mise à l'échelle entraîne la différence d'échelle optimale entre l'étape 1/2, au moins l'échelle sera-t-elle la même quel que soit , il suffit donc de trouver un paramètre pour obtenir une optimisation efficace basée sur les gradients schème.xf(x)f(x)x

En revanche, le gradient de a de très mauvaises propriétés globales d’optimisation. Nous avonsCeci multiplie le très bon et bien dégradé avec un facteur qui décroît (plus vite que) de façon exponentielle à mesure que augmente. À , nous avons déjà , de sorte qu'un pas le long du vecteur de gradient est environ fois trop petit. Pour obtenir une taille de pas raisonnable vers l'optimum, il faudrait redimensionner le gradient en fonction de la réciproque, une énorme constantep(x)

p(x)=f(x)p(x)=2xexp(x2).
2xexp(x2)xx=5exp(x2)=1.4101110111011. Un tel gradient mal dimensionné est pire qu'inutile à des fins d'optimisation - nous ferions mieux d'essayer un pas unitaire dans la direction en montée plutôt que de le définir en nous ajustant à ! (Dans de nombreuses variables, devient un peu plus utile puisque nous obtenons au moins des informations directionnelles à partir du gradient, mais le problème de la mise à l'échelle demeure.)p(x)p(x)

En général, rien ne garantit que aura de telles propriétés d’échelle de gradient que cet exemple de jouet, en particulier lorsque nous avons plus d’une variable. Cependant, pour à peu près tous les problèmes non triviaux, sera bien meilleur que . En effet, la probabilité est un gros produit avec un tas de termes, et le journal le transforme en une somme, comme indiqué dans plusieurs autres réponses. À condition que les termes de la probabilité soient bien conçus du point de vue de l'optimisation, leur journal est généralement bien tenu, et la somme des fonctions bien comportées est bien conduite. Par sage je veux direlogp(x)logp(x)p(x)f(x)ne change pas trop ni trop rapidement, ce qui conduit à une fonction presque quadratique facile à optimiser par les méthodes de gradient. La somme d'un dérivé est le dérivé de la somme, quel que soit son ordre, ce qui permet de s'assurer que cette grosse pile de termes de somme a une dérivée seconde très raisonnable!

Paul
la source
4
+1 Cette réponse appelle et souligne des points qui vont au coeur du problème.
whuber
47

Sous débordement

L'ordinateur utilise une représentation à virgule flottante à chiffres flottants à chiffres limités, ce qui multiplie le nombre de probabilités très proches de zéro.

Avec , nous n'avons pas ce problème.log

Uri Goren
la source
3
+1 pour la stabilité numérique - ceci et la réponse de Yuril devraient en être un!
Alec Teal le
1
Vous pouvez calculer le produit dans l'espace journal, ainsi il devient une somme, puis le transférer à nouveau. Ou vous calculez qui est égal à . La stabilité numérique n’est donc pas la question. logpθppθ
Albert
1
N'oubliez pas que le vous avez mentionné correspond à la multiplication des probabilités de tous les événements de l'échantillon et que est l'élément sujet à un dépassement inférieur. pp
Uri Goren le
5
@Filip La terminologie utilisée dans ce fil de discussion est quelque peu déconseillée. Nous discutons des densités de probabilité , pas des probabilités. Les densités sont arbitraires: elles dépendent des unités de mesure. De plus, pour des tailles d'échantillon suffisantes, la densité de probabilité de tout échantillon simple issu d'un modèle paramétrique sera éventuellement inférieure à . Dans les grands problèmes (avec des millions de données), les densités de probabilité sont systématiquement de ou moins. Même un échantillon de taille de la distribution normale standard a presque certainement une densité de probabilité inférieure à . 212721000000802127
whuber
4
@ FilipHaglund: whuber est correct, cependant, le fait que ce soient ses densités n'est pas l'observation cruciale ici. Nous pourrions tout aussi bien discuter d'un processus discret et parler de probabilités réelles (et en fait, le PO n'a rien dit qui exclue ce cas). Mais nous parlons de probabilités pour des résultats très spécifiques (par exemple, un million d'observations allant d'une manière particulière). Un seul résultat spécifique est improbable, mais dans l'inférence bayésienne, les rapports de probabilités sont importants. Nous avons donc besoin de savoir quelle est plus grande une probabilité infime sur une autre.
Meni Rosenfeld
34
  1. Le logarithme de la probabilité des probabilités jointes multiples se simplifie pour résumer la somme des logarithmes des probabilités individuelles (et la règle de somme est plus facile que la règle du produit pour la différenciation)

    log(iP(xi))=ilog(P(xi))

  2. Le logarithme d'un membre de la famille des distributions de probabilité exponentielles (qui inclut la normale omniprésente) est polynomial dans les paramètres (c'est-à-dire que le maximum de vraisemblance est réduit aux moindres carrés pour les distributions normales).

    log(exp(12x2))=12x2

  3. Cette dernière forme est à la fois plus stable numériquement et plus facile à différencier sur le plan symbolique que la première.

  4. Enfin et surtout, le logarithme est une transformation monotone qui préserve les emplacements des extrema (en particulier, les paramètres estimés dans max-vraisemblance sont identiques pour la formulation originale et la formulation transformée par log).

TemplateRex
la source
5
La raison 2 ne peut pas être assez soulignée. Pour maximiser la log-vraisemblance d'un modèle linéaire à bruit gaussien, il suffit de résoudre un problème de moindres carrés, ce qui revient à résoudre un système d'équations linéaire.
Paul
Les motifs 1 et 3 décrivent simplement comment le calculer. Vous pouvez le calculer de cette manière, puis le reconvertir (multiplier par ) pour obtenir . En fait, il est assez courant de calculer en logarithmique la stabilité numérique. Mais cela n'explique pas pourquoi vous utilisez ce dégradé. La raison 4 n'est pas non plus une raison pour laquelle le gradient de est meilleur. Vous pouvez le faire avec beaucoup d'autres transformations. La raison 2 est intéressante mais je ne sais toujours pas pourquoi le gradient d'un polynôme est meilleur que celui d'une autre fonction. ppθlogp
Albert
@Albert, la dérivée d'un polynôme est un polynôme d'un degré inférieur (en particulier, le quadratique va en linéaire), alors que les exponentielles ne font pas que sous différencier
TemplateRex le
@TemplateRex: Oui, c'est clair. Mais je parle des propriétés de convergence dans une méthode de gradient stochastique.
Albert
25

Il est beaucoup plus facile de prendre un dérivé de somme de logarithmes que de prendre un dérivé de produit, qui contient, par exemple, 100 multiplicateurs.

Yurii
la source
10
De plus, vous réduisez les problèmes numériques potentiels lorsque les termes deviennent très petits ou grands.
Björn le
8
Au contraire, le PO fournit implicitement un excellent moyen de calculer la dérivée de tout produit de fonctions non négatives: multipliez la somme des dérivés des journaux par le produit lui-même. (Cette multiplication est mieux réalisée en termes de logarithmes, ce qui élimine également les problèmes numériques mentionnés dans le commentaire de @ Björn.) Ainsi, la "facilité" n'offre aucun pouvoir explicatif réel, ni la question plus significative de la comparaison des gradients .
whuber
10

En règle générale, le problème d'optimisation le plus simple et le plus simple consiste à optimiser une fonction quadratique. Vous pouvez facilement trouver l’optimum d’une telle fonction, peu importe votre point de départ. La façon dont cela se manifeste dépend de la méthode utilisée, mais plus votre fonction est proche d'un quadratique, mieux c'est.

Comme indiqué par TemplateRex, dans une grande variété de problèmes, les probabilités utilisées pour calculer la fonction de vraisemblance proviennent de la distribution normale ou sont approximées par celle-ci. Donc, si vous travaillez sur le journal, vous obtenez une belle fonction quadratique. Alors que si vous travaillez sur les probabilités, vous avez une fonction qui

  1. N'est pas convexe (le fléau des algorithmes d'optimisation partout)
  2. Croise rapidement plusieurs échelles et a donc une plage très étroite où les valeurs de fonction indiquent où diriger votre recherche.

Quelle fonction préférez-vous optimiser, ceci ou cela ?

(C’était en fait une tâche facile; dans les applications pratiques, votre recherche peut commencer tellement loin de l’optimum que les valeurs et les gradients de la fonction, même si vous avez été en mesure de les calculer numériquement, seront indissociables de 0 et seront inutiles pour l’optimisation. algorithme. Mais la transformation en une fonction quadratique en fait un morceau de gâteau.)

Notez que cela est tout à fait compatible avec les problèmes de stabilité numérique déjà mentionnés. La raison pour laquelle log log est nécessaire pour utiliser cette fonction est exactement la même que celle pour laquelle la probabilité de journalisation est beaucoup mieux gérée (pour l'optimisation et à d'autres fins) que l'originale.

Vous pouvez également aborder cette autre manière. Même s'il n'y avait aucun avantage au journal (ce qui existe) - nous allons quand même utiliser l'échelle du journal pour les dérivations et les calculs, alors quelle raison y a-t-il d'appliquer la transformation exp uniquement pour calculer le gradient? Nous pouvons aussi bien rester en accord avec le journal.

Meni Rosenfeld
la source
@TemplateRex: le journal d'une fonction positive convexe (vers le bas) est convexe, mais l'inverse n'est pas vrai. Les probabilités ne sont pas convexes, elles n'ont donc rien à préserver, mais le log est convexe. Regardez les graphiques que j'ai liés - exp (-10x ^ 2) est évidemment non convexe, mais -10x ^ 2 l'est.
Meni Rosenfeld
4

En utilisant nous augmentons la dynamique de l'algorithme d'optimisation. Le dans les applications est généralement un produit de fonctions. Par exemple, dans l'estimation du maximum de vraisemblance, il est le produit de la forme , où Est la fonction de densité, qui peut être supérieur ou inférieur à 1, entrelnppL(x|θ)=Πi=1nf(xi|θ)f(.)

Ainsi, lorsque est très grand, à savoir un grand échantillon, votre fonction de vraisemblance est généralement loin de 1: il est soit très petit ou très grand, car il est une fonction de puissance .nL(.)Lf(.)n

En prenant un journal, nous améliorons simplement la plage dynamique de tout algorithme d'optimisation, lui permettant de travailler avec des valeurs extrêmement grandes ou petites de la même manière.

Aksakal
la source
0

Quelques bonnes réponses ont déjà été données. Mais j'ai récemment rencontré un nouveau:

Souvent, on vous donne un énorme ensemble de données d'entraînement , vous définissez un modèle probabiliste et vous voulez maximiser la probabilité pour . Ils sont supposés indépendants, c'est-à-dire que vous avez Maintenant, vous faites souvent une sorte d’entraînement basé sur un gradient stochastique (mini-batch), c’est-à-dire que dans chaque étape, pour votre perte , vous optimisez pour , c'est-à-dire Xp(x|θ)xX

p(X|θ)=xXp(x|θ).
LL(X|θ)XX
θ:=θxXL(x|θ)θ.
Maintenant, ces étapes stochastiques sont cumulées de manière additive. Pour cette raison, vous souhaitez que la propriété C'est le cas pour
L(X|θ)=xXL(x|θ).
L(x|θ)=logp(x|θ).

Albert
la source