Implementation of Robbins monro

Robbins monro の実装

sorry, this page is Japanese only. 

今回はRobbins monro の実装をしてみました。
Robbins monroは確率勾配降下法の学習率を入りテーション回数の逆数で割っていくものです。
使っているprogram言語はpython 3です。osはwindowsです。(macほしい...)


アルゴリズム
確率勾配降下方とは目的関数の最適解を求めるアルゴリズムです。目的関数をf(X)とすると、手順は以下のようになっています。

1. 初期学習率$n_0$を決めます。訓練データDを用意します。この訓練データは複数の初期値の集まりです。
2. 訓練データから一つ初期値をランダムに取り出し、これを$x_0$とし、最初の予測値とします。
3. 次の式に現在の予測値$x_0$を代入し、新たな予測値$x_{n+1}$を得ます。$$x_{n+1} = x_{n} - \frac{n_0}{n} grad f(X_n)$$
4. 収束して入れば4へ、収束していなければ2で得られた値$x{n+1}$を新たに$x_n$としてもう一度2を行う。
5. 訓練データを一周していなければ2へ、一周していれば各初期値から得られた解の中から目的関数を最も小さくするものを選ぶ。　　

実装例

以下の目的関数を最小化させてみましょう。

$$f(x,y) = (x-2)^2 + (y-3)^2 $$

コマンドラインでpythonを実行していきます。

予想通り、（２，３）という解を導き出してくれました。目的関数が簡単だったので、初期値をどの値でとってもばっちり正解にたどり着いてくれました。

CODE

以下にRobbins monroの関数だけ置いておきます。こちらにすべてのコードを載せています。

def Robbins_monro(function,grad,number_variable_gradient):

    init_learning_rate = 1.5

    stepsize = 1000

    init_value = np.array([range(-1000,1020,20) for i in range(number_variable_gradient)])

    possibility_solution = np.zeros((number_variable_gradient,101))
    for n in range(len(init_value[0,:])):
        old_estimation = init_value[:,n]
        for step in np.arange(1,stepsize+1):
            n_step = init_learning_rate/step
            old_estimation_t = old_estimation

            new_estimation = old_estimation - n_step*grad(old_estimation)
            old_estimation = new_estimation

        if n % 10 == 0:
            print('%s taimes step is comlicated \n'%n)
        possibility_solution[:,n] = new_estimation

    estimation = possibility_solution[:,0]
    for j in range(len(possibility_solution[:,0])):
        if function(estimation) > function(possibility_solution[:,j]):
            estimation = possibility_solution[:,j]

    return estimation