[PYTHON] J'ai essayé de combattre le minimum local de la fonction Goldstein-Price

Auparavant, j'avais appris qu'il y avait une fonction RosenBrock pour les tests d'Optimizer dans la bibliothèque SciPy, mais lorsque j'ai cherché sur Wikipédia, j'ai trouvé qu'il existe diverses fonctions de benchmarking autres que RosenBrock.

https://en.wikipedia.org/wiki/Test_functions_for_optimization

On s'attend à ce que la forme la plus simple de la fonction Sphère soit facile à trouver la solution optimale (point de valeur minimum) intuitivement, mais d'autres fonctions peuvent être difficiles à trouver la solution optimale. Cette fois, je voudrais reprendre "Goldstein Price Function" de cette liste.

Fig. Sphere Function (Chiffre de référence, c'est facile à manipuler ...)

Fig. Goldstein-Price Function (Cette fois, nous allons traiter de cela.)

Caractéristiques de Goldstein de la fonction de prix

Premièrement, la formule de la fonction est la suivante.

f(x,y) = (1+(x+y+1)^2 (19 -14x+3x^2-14y+6xy+3y^2))\\
(30 + (2x -3y)^2 (18 - 32x +12x^2 +48y -36xy+27y^2)

Comme le montre le graphique 3D de la figure ci-dessus, la non-linéarité de la fonction est importante car les valeurs sur l'axe z sont plus grandes que les valeurs sur l'axe x et l'axe y. Le point de valeur minimum (solution optimale) de cette fonction est

f(0, -1) = 3

Comme indiqué, z = 3 est obtenu par (x, y) = (0, -1), mais il y a plusieurs points minimum (minimum local) autour de cela. J'ai dessiné un diagramme de contour pour voir la situation en détail.

Il y a une forme en forme de rainure en forme de croix diagonale, et le point d'intersection de la rainure est le point Global Minumum (x, y) = (0, -1). Il y a une île dans une zone légèrement grande près de (1, 0,2) en haut à droite, et il est possible qu'elle prenne le minimum local. De plus, de petits candidats Local Mimimum sont observés dans la forme de la rainure. Cela semble difficile à gérer.

Résoudre avec TensorFlow

Puisque nous avons divers optimiseurs, nous avons décidé de le résoudre en utilisant TensorFlow. Le code ressemble à ceci:

La première est la définition de la fonction Goldstein-Price. Il est codé selon la définition de la fonction, mais le calcul du carré utilise «tf.square ()».

def goldsteinprice_tf(x, y):
    # goal : (x, y) = (0., -1.0)
    term1 = (19. - 14. * x + 3. * x * x -14. * y + 6. * x * y + 3. * y * y)
    term2 = 1. + tf.square((x + y + 1.0)) * term1
    term3 = 18. -32. * x + 12. * x * x + 48. * y - 36. * x * y + 27. * y * y
    term4 = 30. + tf.square((2. * x - 3. * y)) * term3
    z = term2 * term4
    return z

Définissez la valeur initiale et donnez la fonction Goldstein-Price comme coût.

    # set initial parameter
    x0, y0 = (0., 0.)
    x = tf.Variable(x0)
    y = tf.Variable(y0)
    loss = goldsteinprice_tf(x, y)

L'optimiseur peut être sélectionné parmi 6 types d'optimiseur TensorFlow.

    lrate = 1.e-03    #Taux d'apprentissage
    sw = 4            # Optimizer Selection
    
    # need to check sw = [2, 5]
    if sw == 1:
        optimizer = tf.train.GradientDescentOptimizer(lrate)
    elif sw == 2:
        optimizer = tf.train.AdagradOptimizer(lrate, initial_accumulator_value=0.1)
    elif sw == 3:
        optimizer = tf.train.MomentumOptimizer(lrate, momentum=0.0)
    elif sw == 4:
        optimizer = tf.train.AdamOptimizer(lrate)
    elif sw == 5:
        optimizer = tf.train.FtrlOptimizer(lrate)
    elif sw == 6:
        optimizer = tf.train.RMSPropOptimizer(lrate, decay=0.0)
    else:
        print('Error.')
    
    train_op = optimizer.minimize(loss)

Il ne vous reste plus qu'à initialiser les variables et exécuter la session.

   init = tf.initialize_all_variables()

    with tf.Session() as sess:
        sess.run(init)
        print('Training...')
        print('initial (x, y) = (%8.4f, %8.4f) : loss = %8.4f' 
            % (sess.run(x), sess.run(y), sess.run(loss)))
        
        for i in range(10001):
            train_op.run()

            if i % 100 == 0:
                loss_ = float(sess.run(loss))
                # loss_log.append(loss_)
                x_ = sess.run(x)
                y_ = sess.run(y)
            
            if i % 1000 == 0:                # echo status on screen
                print('(x, y) = (%8.4f, %8.4f) : loss = %8.4f' 
                    % (x_, y_, loss_))

        # Check trained parameter
        print('final (x, y) = (%8.4f, %8.4f) : loss = %8.4f' 
            % (sess.run(x), sess.run(y), sess.run(loss)))

Les paramètres de calcul qui peuvent être sélectionnés sont --Valeur initiale (x0, y0) --Type d'optimiseur

• Taux d'apprentissage et nombre de processus de boucle Il devient.

À titre d'exemple de calcul, le résultat de l'exécution des paramètres de liste ci-dessus (valeur initiale (0,0), AdamOptimizer, Loop 10 000 fois) est le suivant.

Training...
initial (x, y) = (  0.0000,   0.0000) : loss = 600.0000
(x, y) = ( -0.0010,  -0.0010) : loss = 598.5597
(x, y) = ( -0.5198,  -0.4769) : loss =  31.8792
(x, y) = ( -0.5756,  -0.4230) : loss =  30.2262
(x, y) = ( -0.5987,  -0.4012) : loss =  30.0007
(x, y) = ( -0.6000,  -0.4000) : loss =  30.0000
(x, y) = ( -0.6000,  -0.4000) : loss =  30.0000
(x, y) = ( -0.6000,  -0.4000) : loss =  30.0000
(x, y) = ( -0.6000,  -0.4000) : loss =  30.0000
(x, y) = ( -0.6000,  -0.4000) : loss =  30.0000
(x, y) = ( -0.6000,  -0.4000) : loss =  30.0000
(x, y) = ( -0.6000,  -0.4000) : loss =  30.0000
final (x, y) = ( -0.6000,  -0.4000) : loss =  30.0000

La situation est brillamment prise dans le minimum local (-0,6, -0,4). À propos, lorsque la valeur initiale a été définie près du minimum global et calculée, il a été confirmé qu'elle convergeait correctement vers le point minimum (0, -1).

Méthode d'optimisation globale "méthode de cuisson"

Ici, quittons TensorFlow et essayons la méthode d'optimisation globale "Simulated Annealing". [Wikipédia](https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3 L'explication en% 95) est la suivante.

Lorsque l'algorithme SA trouve à plusieurs reprises une solution, il trouve une solution dans le voisinage aléatoire de la solution actuelle, qui est affectée par la valeur de la fonction donnée à ce moment-là et le paramètre global T (signifiant température). Ensuite, la valeur de T (température) diminue progressivement en raison de la similitude avec le processus physique mentionné ci-dessus. Par conséquent, puisque T est grand au début, la solution change hardiment, mais elle converge lorsque T s'approche de zéro. Au début, vous pouvez facilement gravir la pente, vous n'avez donc pas à vous demander quoi faire lorsque vous tombez dans un minimum local qui pose un problème avec l'escalade.

La chose merveilleuse était que le pseudo code était également posté, donc je l'ai converti en code Python et l'ai exécuté.

La partie principale du code est la suivante.

def sim_anneal(startState, maxIter, goalE):
    state = startState
    x_, y_ = state[0], state[1]
    e = goldsteinprice(x_, y_)
    bestState = state
    bestE = e
    for iter in range(0, maxIter):
        delta = np.random.rand(2) - 0.5
        nextState = state + delta * 1.
        nextE = goldsteinprice(nextState[0], nextState[1])
        
        if bestE > nextE:
            bestState = nextState
            bestE = nextE
            if goalE >= bestE:
                return bestState
        r = np.random.rand()
        if probability(e, nextE, temperature(10.0, iter/maxIter)) >= r:
            state = nextState
            e = nextE
        if iter % 100 ==0:
            print('iter: nextE, bestE, goalE = (%5d, %9.3f, %9.3f, %9.3f)' 
               % (iter, nextE, bestE, goalE))
            
    return bestState

Lorsque le calcul est exécuté, il atteint le voisinage de Global Munimum (0.0, -1.0).

Fig. Parameter(x,y) Path (Simulated Annealing)

Dans ce calcul également, il existe diverses options de paramètres de calcul en plus de la valeur initiale. De plus, ce que j'ai remarqué après avoir exécuté le calcul plusieurs fois, c'est qu'il est affecté par la nature des nombres aléatoires. Dans certains cas, si la graine du nombre aléatoire n'était pas définie et que le calcul était exécuté plusieurs fois, le calcul se terminerait à un endroit complètement différent. Les résultats sont difficiles à lire, ce n'est donc pas une méthode de calcul polyvalente.

Refaire avec TensorFlow Optimizer

Pour voir l'effet de la valeur initiale, 9 valeurs initiales: «[[0., 0.], [0., 1.], [1., 0.], [1., 1.], [0., -1.], [-1., 0. ], [-1., -1.], [-1., 1.], [1., -1.]] `.

Tout d'abord, le résultat du calcul à l'aide d'Adagrad Optimizer est présenté dans la figure ci-dessous.

Fig. Parameter(x,y) path from 9 points (Adagrad)

Aucun d'entre eux n'a atteint le point minimum, à l'exception des cas qui étaient dans le minimum global depuis le début. (Il peut être amélioré en ajustant le taux d'apprentissage et d'autres paramètres.) Le résultat de l'utilisation d'Adam Optimizer est présenté ci-dessous.

Fig. Parameter(x,y) path from 9 points (Adam)

Ici, le point minimum est atteint dans deux cas, mais si l'un est exclu car la valeur initiale était le point minimum, le cas de (x0, y0) = (1.0, -1.0) réussit également.

À partir de la situation ci-dessus, j'ai finalement essayé d'utiliser un nombre aléatoire pour définir la valeur initiale. Normalement, dans l'apprentissage des réseaux neuronaux, des nombres aléatoires sont utilisés pour initialiser les poids, et le but est de «favoriser la progression de l'apprentissage en éliminant la symétrie du réseau». Cette fois, compte tenu de la possibilité de tomber au minimum local, la signification est légèrement différente car les nombres aléatoires sont initialisés afin d'attribuer largement des paramètres.

    num_jobs = 10

    with tf.Session() as sess:
        for job in range(num_jobs):
            init_param = tf.Variable(tf.random_uniform([2], minval=-1., maxval=1.))
            x = tf.slice(init_param, [0], [1])
            y = tf.slice(init_param, [1], [1])

            loss = goldsteinprice_tf(x, y)
(Omis)

Comme mentionné ci-dessus, tf.random_uniform () a généré un nombre aléatoire de -1,0 à 1,0 et l'a utilisé comme valeur initiale. Le résultat du calcul est le suivant.

Fig. Parameter(x,y) path from random point (J'ai essayé de séparer les couleurs de Path.)

Bien qu'il soit un peu plus pessimiste par rapport au résultat de la valeur initiale de 9 points, il a atteint (0, -1) du Global Minumum avec une probabilité élevée. Vous pouvez trouver le minimum de Golobal avec une probabilité de 30% ou plus.

Cette fois, j'ai essayé de "me battre" avec la fonction Goldestein-Price sans but pratique, mais j'ai découvert diverses difficultés pour trouver le point optimal. En utilisant un nombre aléatoire comme valeur initiale, le problème du minimum local peut être évité dans une certaine mesure, mais qu'en est-il de la plage du nombre aléatoire? Il ne semble pas y avoir de réponse générale à cela.

Cependant, en supposant une situation où les données d'apprentissage sont entrées dans un problème de classification réel, il peut y avoir des situations où les données d'apprentissage elles-mêmes ont une erreur et ne sont pas capturées par le minimum local en utilisant la méthode de descente de gradient probabiliste. Je crois. (Bien sûr, il est très utile d'essayer diverses valeurs initiales dans une situation où vous pouvez passer du temps.)

Références (site Web)

--Test des fonctions d'optimisation (wikipedia) ... Un beau diagramme de fonction (tracé 3D) est affiché. https://en.wikipedia.org/wiki/Test_functions_for_optimization

• Méthode de brûlage (wikipesida) https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3%95 --Tensorflow Document ... ver. 0.7.0. (Au 22 février 2016) https://www.tensorflow.org/ ――Apprenez à nouveau les bases de Theano ―― Qiita http://qiita.com/TomokIshii/items/1f483e9d4bfeb05ae231