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 Sphere_func0.png (Chiffre de référence, c'est facile à manipuler ...)

Fig. Goldstein-Price Function Goldstein_price_func2.png (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. GoldsteinPrice_contour1.PNG

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

À 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) GoldsteinPrice_SA.png

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) gsp_p1_Adagrad.png

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) gsp_p1_Adam.png

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 gsp_p2_Adam.png (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

Recommended Posts

J'ai essayé de combattre le minimum local de la fonction Goldstein-Price
J'ai essayé d'obtenir l'index de la liste en utilisant la fonction énumérer
J'ai essayé la fonction de tableau croisé dynamique des pandas
J'ai essayé de corriger la forme trapézoïdale de l'image
J'ai essayé de vectoriser les paroles de Hinatazaka 46!
J'ai essayé de résumer la forme de base de GPLVM
J'ai essayé d'approcher la fonction sin en utilisant le chainer
J'ai essayé de visualiser les informations spacha de VTuber
J'ai essayé d'effacer la partie négative de Meros
J'ai essayé de classer les voix des acteurs de la voix
J'ai essayé de résumer les opérations de chaîne de Python
J'ai essayé de trouver l'entropie de l'image avec python
[Courses de chevaux] J'ai essayé de quantifier la force du cheval de course
J'ai essayé d'obtenir les informations de localisation du bus Odakyu
J'ai essayé de trouver la moyenne de plusieurs colonnes avec TensorFlow
J'ai fait une fonction pour vérifier le modèle de DCGAN
[Python] J'ai essayé de visualiser la relation de suivi de Twitter
J'ai essayé un peu le comportement de la fonction zip
[Apprentissage automatique] J'ai essayé de résumer la théorie d'Adaboost
J'ai essayé de lancer le cluster ipython au minimum sur AWS
J'ai essayé d'approcher la fonction sin en utilisant chainer (re-challenge)
J'ai essayé de déplacer le ballon
J'ai essayé d'estimer la section.
Je veux obtenir le nom de la fonction / méthode en cours d'exécution
J'ai essayé d'automatiser l'arrosage du pot avec Raspberry Pi
J'ai essayé de créer l'image de démarrage SD de LicheePi Nano
J'ai essayé d'agrandir la taille du volume logique avec LVM
J'ai essayé d'améliorer l'efficacité du travail quotidien avec Python
J'ai essayé de visualiser la condition commune des téléspectateurs de la chaîne VTuber
J'ai essayé le serveur asynchrone de Django 3.0
J'ai essayé de résumer la commande umask
J'ai essayé de résumer la modélisation graphique.
J'ai essayé d'estimer le rapport de circonférence π de manière probabiliste
J'ai essayé de toucher l'API COTOHA
J'ai essayé d'adapter la fonction exponentielle et la fonction logistique au nombre de patients positifs au COVID-19 à Tokyo
J'ai essayé de transformer l'image du visage en utilisant sparse_image_warp de TensorFlow Addons
J'ai essayé d'informer le serveur Zabbix d'une erreur d'exécution de la fonction AWS Lambda
J'ai essayé d'obtenir les résultats de Hachinai en utilisant le traitement d'image
J'ai essayé de visualiser la tranche d'âge et la distribution des taux d'Atcoder
J'ai essayé de transcrire les actualités de l'exemple d'intégration commerciale sur Amazon Transcribe
zoom J'ai essayé de quantifier le degré d'excitation de l'histoire lors de la conférence
J'ai essayé d'estimer la similitude de l'intention de la question en utilisant Doc2Vec de gensim
J'ai essayé d'améliorer la précision de mon propre réseau neuronal
J'ai mesuré 6 méthodes pour obtenir l'indice de la valeur maximale (valeur minimale) de la liste
J'ai essayé d'obtenir le code d'authentification de l'API Qiita avec Python.
(Python) J'ai essayé d'analyser 1 million de mains ~ J'ai essayé d'estimer le nombre d'AA ~
J'ai essayé de résumer la manière logique de penser l'orientation objet.
J'ai essayé de trouver l'itinéraire optimal du pays des rêves par recuit (quantique)
J'ai essayé de vérifier et d'analyser l'accélération de Python par Cython
J'ai essayé d'analyser la négativité de Nono Morikubo. [Comparer avec Posipa]
J'ai essayé de visualiser le texte du roman "Weather Child" avec Word Cloud
[Linux] J'ai essayé de vérifier la méthode de confirmation sécurisée du FQDN (CentOS7)
J'ai essayé d'obtenir automatiquement le RSS de la chanson la plus populaire de l'iTunes Store
J'ai essayé d'obtenir les informations sur le film de l'API TMDb avec Python
J'ai essayé d'afficher la valeur d'altitude du DTM dans un graphique
J'ai essayé l'histoire courante de l'utilisation du Deep Learning pour prédire la moyenne Nikkei
En utilisant COTOHA, j'ai essayé de suivre le cours émotionnel de la course aux meros.
J'ai essayé de vérifier le résultat du test A / B avec le test du chi carré
Python: je souhaite mesurer proprement le temps de traitement d'une fonction