Processing math: 100%
スキップしてメイン コンテンツに移動

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を実行していきます。




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

CODE
以下にRobbins monroの関数だけ置いておきます。こちらにすべてのコードを載せています。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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


コメント

このブログの人気の投稿

ヘッセ行列

Introduction English ver 今日は、ヘッセ行列を用いたテイラー展開について書こうと思います。 これは最適化を勉強するにあたって、とても大事になってくるので自分でまとめて残しておくことにしました。とくに、機械学習では最適化を必ず行うため、このブログのタイトルにもマッチした内容だと思います。 . 概要 ヘッセ行列の定義 ベクトルを用いたテイラー展開 関数の最適性 ヘッセ行列の定義 仮定 f は次のような条件を満たす関数です。. f はn次元ベクトルから実数値を出力します。 このベクトルは次のように表せます。 x = [x_1,x_2,,,,x_n] \forall x_i , i \in {1,2,,,n}, f は二回偏微分可能です。 定義 ヘッセ行列は \frac{\partial^2}{\partial x_i \partial x_j}を (i,j)要素に持ちます。 よってヘッセ行列は次のように表せます。 \[ H(f) = \left( \begin{array}{cccc} \frac{\partial^ 2}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & &\ldots \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^ 2 f}{\partial x_1 \partial x_2} & \frac{\partial^ 2 f}{\partial x_2^ 2} & \ldots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \ldo...

カーネルK-means 理論編

Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編 の記事を見ていただけるとよいのではないかと思います。 カーネルK-meansの実装編 も併せてご覧ください。 概要 K-meansの弱点 カーネルトリック カーネルK-means アルゴリズム K-meansの弱点 例えば、次のようなデータを用意します。 このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。 プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。 このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。 カーネルK-meansはK-meansの弱点を補います。 カーネルトリック 初めに、カーネルトリックを説明します。 線形分離できないようなデータXを例えば次のように線形分離できるように\phi(x)に送る写像\phiを考えます。 カーネルは次のように定義されます。 K(x,y) = \phi(x)^T \phi(y) \phiを具体的に計算することは難しいですが、K(x,y)を計算することなら簡単です。 この手法をカーネルトリックと呼ばれます。 カーネルK means K-meansの目的関数を復習しておきます。 J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2 ここで、 プロトタイプは\mu_i ~\forall k \in Kとしま...