Implementation of Robbins monro

Robbins monro の実装

sorry, this page is Japanese only.

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

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

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

このブログの人気の投稿

K-means 理論編

Introduction English ver 今日はK-meansアルゴリズムの理論について書きます。 K-meansアルゴリズムはクラスタリングのためのアルゴリズムです。 K-meansの実装の記事はカーネルK-meansの実装を御覧ください。この記事はカーネルK-menasの実装についての記事ですが、通常のK-meansの実装も行っています。カーネルK-meansについてはまた、今度別の記事で紹介したいと思います。概要 1 of K 符号化法プロトタイプ歪み尺度最適化 1 of K 符号化法 K-meansはK個のクラスについて分類することを考えます。 K-meansでは $x_n$がkのクラスに属していることを次のように表します。ベクトル$r_n:1 \times K$ を $$r_n := (0,0,..,1,..,0)$$ このベクトルはk番目にのみ1を持ち、それ以外は0を要素に持つようなベクトルです。こののような表現の仕方を1 of K符号化法と呼びます。プロトタイプ K-meansではプロトタイプと呼ばれるベクトルを選びます。このベクトルは各クラスに一つあり、そのクラスの代表のようなベクトルです。 K-means ではそのようなベクトルは各クラスの平均ベクトルとなります。これは目的関数から自然と導かれます。歪み尺度プロトタイプベクトルを $\mu_i ~\forall k \in K$とします。この時、k-meansの目的関数は次のようになります。 $$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$ ここで、 $r_{nk}$ は$r_n$のk番目の要素です。この目的関数について少し説明をします。$r_{n}$は$x_n$が属しているクラスのラベルの場所だけ1で他は０であるので、 $$J = \sum_{n=1}^{N} ||x_n - \mu_{x_n}||$$ ここで、$\mu_{k_n}$は$x_n$が属しているクラスのプロトタイプです。よって、 $$J = ||x_1 - \mu_{x_1}|| + ||x_2 -\mu_{x_2}|| + ...

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。このスライドはダイクストラ法を説明したスライドです。 Overview アルゴリズム実装アルゴリズムこのアルゴリズムはスタート始点のノードを決める。そして、それをAと名付ける。各ノードに$d=\infty$を割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。 For adj in adj_list: If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除くグラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。となっています。このアルゴリズムを図を用いて説明します。このグラフを使って説明します。初めに、スタート地点を決めます。そして、各ノードに$d=\infty$を割り当てます。 Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。次にAを取り除きます。次はBから始まります。Aと同じことをやります。このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。実装このアルゴリズムでは$O(log(|V|^2))$という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...

カーネル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$としま...

journey of Froakie (ケロマツの旅路)

このブログを検索