はじめに

今回はディープラーニングなどで使用される最適化問題アルゴリズムの一つ勾配降下法について、概要の説明とPythonを用いた実装を行っていきたいと思います。

1.最適化問題

最適化問題についてWikipediaでは以下のように記述されています。

最適化問題（さいてきかもんだい、英: optimization problem）とは、特定の集合上で定義された実数値関数または整数値関数についてその値が最小（もしくは最大）となる状態を解析する問題である

つまり、「特定の値を最小もしくは最大にする問題」と言い換えることができます。
機械学習の教師あり学習などにおいては「誤差を最小にする問題」と言い換えることができます。

今回は例題として、「以下の関数の出力値が最小となるパラメータxを求める」ことを目的として勾配降下法を用いて解いていきましょう。

f(x) = (x-1)^2

2.勾配降下法

勾配降下法は最適化問題アルゴリズムの一つです。
あくまで最適化アルゴリズムの一つであり機械学習アルゴリズムではありません。
しかし、ディープラーニングなどのパラメータが非常に多いモデルをチューニングする手法として利用されているため、ディープラーニングを理解するために必須な最適化問題アルゴリズムとなっています。

f(x) = (x-1)^2

今回は、以上の関数の出力値が最小となるxを求めることが目的でした。
この関数の出力値が最小となるxはグラフを見ればわかる通り、xが1のときに関数の出力値が0で最小となります。
なので、今回はxの値が1になるようにすることが目的です。

ではどのようにして、xの値を1に近づければよいのでしょうか？
それには微分で求めた傾きを利用します。
微分によってグラフにおける傾きを知ることで、傾きがマイナスの場合にはプラスの方向に、逆に傾きがプラスの場合にはマイナスの方向にxの値を変化させていくことで、xの値を1に近づけていきます。

以下が変数の更新式となります

x_{i+1} = x_{i} - η \frac{d}{dx} g(x_{i})

η（イータ）は学習率と呼ばれます。
学習率が大きければ一度の更新も大きくなり、逆に学習率が小さければ一度の更新は小さくなります。
一度の更新は大きい方が、早く最適解に近づくようになるのでは？と思うかもしれません。
しかし問題点として、更新が大きすぎて最適解を飛び越えてしまい、いつまでも最適解にたどり着けない（収束しない）可能性が出てきます。
ただし学習率が小さすぎると、今度はいつまでたっても最適解にたどり着かないので、学習率はほどほどに小さめなことが基本です。
また、最初は学習率を大きくし学習が進むと学習率を下げるなど学習率を変化させる手法も存在しますが、今回は特に使用しません。

今回の式を確認しましょう
まず、誤差を測るための関数（現在値 - 最小値）です

E = (p - y)

次に勾配降下法の更新式です。

x_{i+1} = x_{i} - η \frac{d}{dx} g(x_{i})

先ほどの誤差関数に関数(x-1)²を組み合わせましょう

E(x) = ((x-1)^2 - y)

次に、誤差関数に勾配降下法の更新式を組み合わせましょう

x_{i+1} = x_{i} - η \frac{dE}{dx}

最後に誤差関数Eをxで微分しましょう。

\frac{dE}{dx} = (x-1)^2 - y \\
\frac{dE}{dx} = x^2 - 2x + 1 - y\\
\frac{dE}{dx} = 2x-2

となります。
これを更新式に当てはめると

x_{i+1} = x_{i} - η (2x_{i}-2)

となります。
あとはこれをプログラムで記述し、パラメータを更新してみましょう

3.Pythonによる実装

勾配降下法


def f(x):
    return (x-1)**2

def e(x,min):
    return f(x) - min

def update_x(x,lnr):
    return x - lnr * (2*x-2)

def gradient():
    x = -1
    lnr = 0.1
    min = 0
    
    while True:        
        error = e(x,min)
        x = update(x,lnr)
        
        if error < 0.0001:
            break
    return x

x = gradient()

学習率（η）は0.1、誤差が0.0001以内になるように学習しました。
実行結果のグラフが以下になります

24回学習した結果、xの値は0.99になりました。

これを学習率をもっと大きくして実行するとどうなるでしょうか？
学習率を0.1から0.9999にしてみましょう
結果は、

のようになりました。
これは、徐々に性能はよくなっていますが学習率が0.1の時と比較してみると、
xを200回更新しても誤差は4.0から3.7程度しか減っていないことが分かり、収束するのにまだまだ更新回数が必要なことが分かります。

これは、xの更新する様子が

このように更新するのではなく、

このように最適解となる1を飛び越えてxの値を更新してしまうため、一度に更新する値が大きいすぎるため、収束しづらくなっていることが分かります。

4.まとめ

最適化問題
・特定の値を最小もしくは最大にする
・教師あり学習においては誤差を最小にする

勾配降下法
・微分で求めたパラメータの傾きをもとにパラメータの値を更新していく
・学習率（η）が重要でほどほどに小さくする
　　小さすぎると一回の更新する量が少なく中々収束しない
　　大きすぎると一回の更新する量が多すぎて最適な値を飛び越えてしまう

5.最後に

今回は、ディープラーニングなどでパラメータチューニングに用いられる最適化問題アルゴリズムの一つ勾配降下法を用いて、単純な関数の出力値を最小になるように最適化していきました。

勾配降下法のほかの種類として、確率的勾配降下法やバッチ勾配降下法、学習率を調整する方法としてRMSPropやMomentum、Adamなどいろいろな種類があります。

今後はそれらについても言及していきたいと思います。