[PYTHON] Ich habe versucht, das lokale Minimum der Goldstein-Preis-Funktion zu bekämpfen

Zuvor habe ich erfahren, dass es in der SciPy-Bibliothek eine RosenBrock-Funktion zum Testen des Optimierers gibt. Bei der Suche in Wikipedia stellte ich jedoch fest, dass es neben RosenBrock verschiedene andere Benchmarking-Funktionen gibt.

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

Es wird erwartet, dass die einfachste Form der Kugelfunktion intuitiv leicht die optimale Lösung (Minimalwertpunkt) zu finden ist, andere Funktionen können jedoch schwierig sein, die optimale Lösung zu finden. Dieses Mal möchte ich "Goldstein Price Function" aus dieser Liste aufnehmen.

Fig. Sphere Function (Referenzfigur, das ist einfach zu handhaben ...)

Fig. Goldstein-Price Function (Dieses Mal werden wir uns darum kümmern.)

Goldstein-Eigenschaften der Preisfunktion

Erstens lautet die Formel der Funktion wie folgt.

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)

Wie im 3D-Diagramm in der obigen Abbildung gezeigt, ist die Nichtlinearität der Funktion groß, da die Werte auf der z-Achse größer sind als die Werte auf der x-Achse und der y-Achse. Der Minimalwertpunkt (optimale Lösung) dieser Funktion ist

f(0, -1) = 3

Wie gezeigt, wird z = 3 durch (x, y) = (0, -1) erhalten, aber es gibt mehrere minimale Punkte (lokales Minimum) um dieses herum. Ich habe ein Konturdiagramm gezeichnet, um die Situation im Detail zu sehen.

Es gibt eine rillenartige Form in einer diagonalen Kreuzform, und der Schnittpunkt der Rille ist der globale Mindestpunkt "(x, y) = (0, -1)". Es gibt eine Insel in einem etwas großen Gebiet in der Nähe von (1, 0,2) oben rechts, und es besteht die Möglichkeit, dass das lokale Minimum erreicht wird. Zusätzlich werden kleine Local Mimimum-Kandidaten in der Rillenform beobachtet. Dies scheint schwierig zu handhaben.

Löse mit TensorFlow

Da wir verschiedene Optimierer haben, haben wir uns entschlossen, diese mit TensorFlow zu lösen. Der Code sieht folgendermaßen aus:

Erstens ist die Definition der Goldstein-Preis-Funktion. Es wird gemäß der Definition der Funktion codiert, aber die Quadratberechnung verwendet "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

Stellen Sie den Anfangswert ein und geben Sie die Goldstein-Preis-Funktion als Kosten an.

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

Der Optimierer kann aus 6 Arten von TensorFlow-Optimierern ausgewählt werden.

    lrate = 1.e-03    #Lernrate
    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)

Jetzt müssen Sie nur noch die Variablen initialisieren und die Sitzung ausführen.

   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)))

Folgende Berechnungsparameter können ausgewählt werden

• Anfangswert (x0, y0)
• Art des Optimierers
• Lernrate und Anzahl der Loop-Prozesse Es wird.

Als Berechnungsbeispiel lautet das Ausführungsergebnis der obigen Listeneinstellungen (Anfangswert (0,0), AdamOptimizer, Schleife 10.000 Mal) wie folgt.

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

Die Situation ist im lokalen Minimum (-0,6, -0,4) hervorragend erfasst. Übrigens, als der Anfangswert in der Nähe des globalen Minimums eingestellt und berechnet wurde, wurde bestätigt, dass er ordnungsgemäß zum Minimalpunkt (0, -1) konvergierte.

Globale Optimierungsmethode "Backmethode"

Verlassen wir hier TensorFlow und probieren die globale Optimierungsmethode "Simuliertes Tempern" aus. [Wikipedia](https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3 Die Erklärung in% 95) lautet wie folgt.

Wenn der SA-Algorithmus wiederholt eine Lösung findet, findet er eine Lösung in der zufälligen Umgebung der aktuellen Lösung, die vom Wert der angegebenen Funktion und dem globalen Parameter T (dh Temperatur) beeinflusst wird. Dann nimmt der Wert von T (Temperatur) aufgrund der Ähnlichkeit mit dem oben erwähnten physikalischen Prozess allmählich ab. Da T zunächst groß ist, ändert sich die Lösung daher kühn, konvergiert jedoch, wenn T gegen Null geht. Zuerst können Sie den Hang leicht erklimmen, sodass Sie nicht darüber nachdenken müssen, was zu tun ist, wenn Sie in ein lokales Minimum fallen, das beim Bergsteigen ein Problem darstellt.

Das Wunderbare war, dass der Pseudocode auch gepostet wurde, also habe ich ihn in Python-Code konvertiert und ausgeführt.

Der Hauptteil des Codes lautet wie folgt.

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

Wenn die Berechnung ausgeführt wird, erreicht sie die Nähe von Global Munimum (0.0, -1.0).

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

Auch bei dieser Berechnung gibt es neben dem Anfangswert verschiedene Berechnungsparameteroptionen. Nach mehrmaliger Ausführung der Berechnung ist mir auch aufgefallen, dass sie von der Art der Zufallszahlen abhängt. In einigen Fällen würde die Berechnung an einer völlig anderen Stelle enden, wenn der Startwert der Zufallszahl nicht festgelegt und die Berechnung viele Male ausgeführt wurde. Die Ergebnisse sind schwer zu lesen, daher handelt es sich nicht um eine vielseitige Berechnungsmethode.

Wiederholen Sie mit TensorFlow Optimizer

Um die Auswirkung des Anfangswertes zu sehen, 9 Anfangswerte: [[0., 0.], [0., 1.], [1., 0.], [1., 1.], [0., -1.], [-1., 0. ], [-1., -1.], [-1., 1.], [1., -1.]] .

Zunächst wird das Berechnungsergebnis mit dem Adagrad Optimizer in der folgenden Abbildung dargestellt.

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

Keiner von ihnen hat den Mindestpunkt erreicht, außer in dem Fall, in dem er von Anfang an im globalen Minimum lag. (Es kann durch Anpassen der Lernrate und anderer Parameter verbessert werden.) Das Ergebnis der Verwendung von Adam Optimizer ist unten dargestellt.

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

Hier wird der Minimalpunkt in zwei Fällen erreicht, aber wenn einer ausgeschlossen wird, weil der Anfangswert der Minimalpunkt war, ist auch der Fall von "(x0, y0) = (1.0, -1.0)" erfolgreich.

Aus der obigen Situation habe ich schließlich versucht, den Anfangswert mit einer Zufallszahl festzulegen. Normalerweise werden beim Lernen des neuronalen Netzes Zufallszahlen verwendet, um die Gewichte zu initialisieren, und der Zweck besteht darin, "den Lernfortschritt durch Eliminieren der Symmetrie des Netzes zu fördern". In Anbetracht der Möglichkeit, auf das lokale Minimum zu fallen, unterscheidet sich die Bedeutung dieses Mal geringfügig, da die Zufallszahlen initialisiert werden, um Parameter weitgehend zuzuweisen.

    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)
(Weggelassen)

Wie oben erwähnt, hat tf.random_uniform () eine Zufallszahl von -1,0 bis 1,0 generiert und als Anfangswert verwendet. Das Berechnungsergebnis ist wie folgt.

Fig. Parameter(x,y) path from random point (Ich habe versucht, die Farben des Pfades zu trennen.)

Obwohl es vom Ergebnis des 9-Punkte-Anfangswertes etwas pessimistischer war, hat es mit hoher Wahrscheinlichkeit (0, -1) von Global Minumum erreicht. Sie finden das Golobal-Minimum mit einer Wahrscheinlichkeit von 30% oder mehr.

Dieses Mal habe ich versucht, ohne praktischen Zweck mit der Goldestein-Preis-Funktion zu "kämpfen", aber ich habe verschiedene Schwierigkeiten beim Finden des optimalen Punktes herausgefunden. Durch die Verwendung einer Zufallszahl als Anfangswert kann das Problem des lokalen Minimums bis zu einem gewissen Grad vermieden werden. Wie steht es jedoch mit dem Bereich der Zufallszahl? Darauf scheint es keine allgemeine Antwort zu geben.

Unter der Annahme einer Situation, in der Trainingsdaten in ein tatsächliches Klassifizierungsproblem eingegeben werden, kann es jedoch Situationen geben, in denen die Trainingsdaten selbst einen Fehler aufweisen und nicht vom lokalen Minimum erfasst werden, indem die probabilistische Gradientenabstiegsmethode verwendet wird. Ich glaube. (Natürlich ist es sehr nützlich, verschiedene Anfangswerte in einer Situation auszuprobieren, in der Sie Zeit verbringen können.)

Referenzen (Website)

--Testfunktionen zur Optimierung (Wikipedia) ... Ein schönes Funktionsdiagramm (3D-Plot) wird veröffentlicht. https://en.wikipedia.org/wiki/Test_functions_for_optimization

• Brennmethode (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-Dokument ... Version 0.7.0. (Stand 22. Februar 2016) https://www.tensorflow.org/ ――Lerne die Grundlagen von Theano noch einmal ―― Qiita http://qiita.com/TomokIshii/items/1f483e9d4bfeb05ae231