ML 向け勾配降下法アルゴリズム機械学習初心者向け勾配降下法アルゴリズム

[[197951]]

基本概念

このセクションでは、勾配降下法をより一般化するために、機械学習アルゴリズムとは独立して勾配降下法アルゴリズム [Gradient Descent、GD] について説明します。

始める前に、まず 2 つの基本的な概念を紹介します。これら 2 つの概念を理解しておけば、機械学習の知識がほとんどなくても、このセクションをうまく理解できるはずです。

機械学習の主なタスクの 1 つは、トレーニングを通じて最適なパラメータのセットを学習することです。コスト関数はパラメータ推定の機能としてよく使用されるため、機械学習のタスクはコスト関数を最小化することとなります。
最適化は機械学習アルゴリズムの非常に重要な要素であり、ほぼすべての機械学習アルゴリズムには最適化アルゴリズムがあります。

勾配降下法は、コスト関数を最小化するパラメータ値を見つけるために使用できる、広く使用されている最適化アルゴリズムです。勾配降下法を中学校数学の言語で説明すると、関数_が最小値に達すると、対応する独立変数_を見つけるプロセスになります。ここで、機械が学習したいのはパラメータであり、これはパラメータ推定に使用されるコスト関数であり、これはの関数です。したがって、基本的に中学校数学の知識があれば、勾配降下法アルゴリズムを理解できます。

勾配降下法の基本的な手順は次のとおりです。

コスト関数を微分して、特定の点における勾配を取得します。勾配の符号は、コスト関数の値が増加しているのか減少しているのかを示します。
コスト関数値が減少する方向、つまり勾配の負の方向を選択し、学習率で算出されたパラメータ更新量を乗算してパラメータを更新します。
最小コストが達成されるまで上記の手順を繰り返します。

上記は、勾配降下法アルゴリズムの最も基本的かつ中核的な概念です。非常にシンプルです。

以下は、勾配降下法アルゴリズムのいくつかのバリエーションです。バッチ勾配降下法 [BGD]、確率的勾配降下法 [SGD]、ミニバッチ勾配降下法 [MBGD]

アルゴリズムの紹介

ベグド

BGD は、勾配降下アルゴリズムの最も原始的な形式であり、パラメータが更新されるたびにトレーニングセット全体のデータを使用するという特徴があります。

BGD の具体的な実装は次のとおりです。

関数が次のとおりであると仮定します。
- いわゆる仮説関数は、入力を出力にマッピングするために使用されるツールであり、その戻り値は推定値とも呼ばれます。
コスト関数は次のようになります。
- は関数変数、はモデル入力、は入力に対応する実数値であることに注意してください。
- このコスト関数の実際に有効な部分は、後続の計算の便宜のために前の部分が追加されていることです。
コスト関数を導出するには、各パラメータの偏微分を取ってそれぞれの勾配を取得する必要があります。
- 機械学習モデルには通常、複数のパラメータがあります。コスト関数はパラメータ推定のためのツールです。各パラメータの最適値を推定するには、各パラメータの偏微分を個別に計算する必要があります。
各パラメータは勾配の負の方向に更新されます。

したがって、BGD の疑似コード形式は次のように簡単に記述できます。

繰り返す { 
 
     
 
    （すべての j = 0, 1, .. nについて） 
 
 }

上記の式の合計は、各反復で、勾配がトレーニングセット全体に基づいて計算されることを反映しています。

BGD は、常にトレーニングセット全体に基づいて勾配を計算するため、グローバル最適解が得られます。これが BGD の利点です。ただし、計算量が膨大になり、計算の反復速度が非常に遅くなります。

シンガポールドル

SGD はデータセット全体ではなく、一度に 1 つのサンプルの勾配を計算します。したがって、SGD はコスト関数から開始し、それを合計する必要はありません。単一サンプルのコスト関数は次のように記述できます。(これは、後続の計算の便宜上、ここでも設定されます)

したがって、SGD のパラメータ更新ルールは次のように記述できます。

SGD の疑似コード形式は次のとおりです。

繰り返す { 
 
 i = 1, .., m の場合{ 
 
         
 
        （すべての j = 0, 1, .. nについて） 
 
    } 
 
 }

SGD の重要なポイントは、サンプルをランダムな順序で選択することです。SGD には局所最適ジレンマがあるため、毎回同じ順序でサンプルを選択すると、同じ場所で局所ジレンマに陥ったり、収束が遅くなったりする可能性が高くなります。したがって、SGD をより適切に機能させるには、ランダム化によってもたらされる利点を最大限に活用する必要があります。つまり、各反復 (疑似コード内の最も外側のループ) の前に、トレーニングセットをランダムに配置できます。

勾配降下法では毎回 1 つのサンプルのみが取得されるため、SGD のトレーニング速度は非常に高速ですが、ノイズが発生し、精度が低下します。つまり、すべての反復がグローバル最適値に到達するわけではなく、すべての反復でコスト関数値を削減できるわけではありません。ただし、言い換えると、ノイズによってある程度はローカル最適値を回避できます。

SGD のもう 1 つの利点は、オンライン学習に使用できることです。つまり、モデルがトレーニングされた後、新しいデータが到着する限り、モデルは新しいデータを使用して再学習し、パラメータを更新して新しい変更に適応できます。

ＭＢＤ

MBGD は、BGD と SGD の欠点を解決するために考案された妥協的なアルゴリズムであり、BGD と SGD の利点を活用しています。基本的な考え方は、パラメータが更新されるたびに、すべてではなく 1 つでもなく、n 個のサンプルが使用されるというものです。(SGD は、n=1 の MBGD の特殊なケースと見なすことができます)

MBGD のコスト関数やその導関数式、パラメータ更新規則式はここでは示しませんが、基本的には BGD と同じです (上記を参照)。

MBGD の疑似コードは次のとおりです。

例えばb=10、m=1000、
繰り返す {
 i = 1, 11, 21, .., 991の場合{ 
         
        （すべての j = 0, 1, .. nについて）
    }
 }

上記の 3 つの勾配降下アルゴリズムの長所と短所をまとめます。

勾配降下法アルゴリズム	アドバンテージ	欠点
ベグド	全体最適解	計算量が多く、反復速度が遅く、トレーニング速度が遅い
シンガポールドル	1. トレーニング速度が速い 2. オンライン学習をサポートする	精度が低下し、ノイズが存在し、ソリューションが全体的に最適ではない
ＭＢＤ	1. ミニバッチの数に応じてトレーニング速度が速くなる 2. オンライン学習をサポートする	BGDほど正確ではなく、まだノイズが多く、グローバルな最適解ではない

ヒント

勾配降下アルゴリズムを使用する際のヒントをいくつか紹介します。

適切な学習率を選択します。選択する最良の方法は、目的関数値 (この記事ではコスト関数値) の学習曲線を時間の経過とともに監視することです。
コスト時間曲線を描いて、反復によってコストがどのように変化するか、つまり勾配がどのように変化するかを観察します。反復によってコストが減少しない場合は、学習率が大きすぎる (発散している) ことを意味します。
学習率は通常、0.1、0.001、0.0001 などの非常に小さい実数値です。学習率が大きすぎると、コスト関数が収束せず、発散状態のままになる可能性があります。
アルゴリズムを学習する前に、特徴スケーリングによって勾配降下法を改善できます。(テスト済み! 大きな学習率を使用するとコスト関数は収束しませんでしたが、特徴スケーリングを使用すると収束しました)
MBGD を使用する場合、学習プロセス中にミニバッチのサイズを徐々に増やして、BGD と SGD の利点をより適切に組み合わせることができます。

高度な

以下の内容は少し難解で、著者はいくつかの概念にあまり詳しくないので、記録だけ残しておきます。

SGD の Keras 実装では、decay、momentum、nestrov という 3 つのキーワード引数が提供されていることに気付きました。

decay – 各反復における学習率の減少を意味します。
勢い – 勢いとは学習を加速することを意味します。これについては後で説明します。
nesterov – ネステロフ運動量アルゴリズムを使用するかどうかを示すアルゴリズム名。

BGD が最小値に達すると、コスト関数全体の真の勾配は非常に小さくなり、最終的には 0 に減少するため、BGD は固定学習率を使用できます。ただし、SGD の勾配推定によって導入されたノイズ源は最小値でも消えないため、SGD の収束を確実にするために、時間の経過とともに学習率を徐々に減らす必要があります。

実際には、学習率は通常、反復まで線形に減少します。

このうち、は k 回目の反復を表し、は番目の反復を表します。

上記の式では、設定する必要がある量には、初期学習率、最終学習率、終了反復が含まれます。通常、値は数百で、に設定されます。したがって、残る主な問題は適切な値を選択することです。値が大きすぎると、学習曲線が激しく揺れ、コストが大幅に増加します。値が小さすぎると、学習プロセスが非常に遅くなります。

前述のように、勾配降下法では、学習を加速するためにモメンタムの概念が導入されており、特に、高曲率（曲率：曲線が直線から外れている度合い）、小さいながらも一貫した勾配、またはノイズの多い勾配の処理に顕著な加速効果があります。モメンタムアルゴリズムは、前回の指数関数的に減衰した勾配の移動平均（移動平均：時系列データを分析するための効果的なツール）を蓄積するため、その方向に進み続けることができ、コストを継続的に削減できます。

正式には、運動量アルゴリズムは、パラメータ空間におけるパラメータの移動方向と速度を表す速度の役割を導入します。これは負の勾配の指数関数的減衰平均に設定され、その更新規則は次のとおりです。

上記の式から導き出される結論の 1 つは、に対してが大きいほど、前の勾配が現在の方向に与える影響が大きくなるということです。

運動量の概念が導入される前は、更新ステップサイズは勾配ノルムに学習率を掛けた値に過ぎません。運動量が導入された後は、勾配シーケンスのサイズと配置に依存します。連続する多くの勾配が同じ方向を指している場合、最大ステップサイズは次のようになります。

ネステロフ運動量アルゴリズムは標準運動量アルゴリズムのバリエーションであり、その更新規則は次のとおりです。

ネステロフ運動量アルゴリズムと標準運動量アルゴリズムの違いは、勾配の計算です。勾配は現在の速度を適用した後に計算され、標準運動量法に補正係数を追加するものと解釈できます。

話題外

最適化アルゴリズムの収束率を調べる場合、通常は追加誤差を測定します。これは、現在のコストが最小のコストを超える量です。SGD を凸問題 (凸集合で定義された凸関数の最小化を含む問題) に適用すると、k ステップの追加誤差はの桁になり、強く凸な場合はになります。追加の条件が想定されない限り、これ以上の改善は不可能です。

Cramer-Rao 境界は、一般化誤差がより速く減少することはできないことを示しています。したがって、Bottou と Bousquet は、機械学習タスクの場合、より速く収束する最適化アルゴリズムを探すことは価値がないと考えています。その理由は次のとおりです。

収束が速いということは、過剰適合に相当する可能性がある

サンプルコード

以下は、BGD、SGD、MBGD の Python コード実装です。これには、高度な部分で説明した高度な内容は含まれていません。

 numpyをnpとしてインポートする
pylab をインポートする
sklearn.datasets.samples_generatorからmake_regression をインポートします
 
 
 def bgd(アルファ、x、y、反復回数):
 「インターネットからコピー」 「 」  
    m = x.shape[0] #サンプル数
    シータ = np.ones(2)
    J_リスト = [] 
 
    x_transpose = x.transpose()
範囲(0, numIterations)内の反復の場合:
        仮説 = np.dot(x, theta)
        損失 = y - 仮説
        J = np.sum (損失 ** 2) / (2 * m) # コスト
        J_リストに追加(J)
        print( "iter %s | J: %.3f" % (iter, J)) 
 
        勾配 = np.dot(x_transpose, 損失) / m
        シータ += アルファ * 勾配 #更新  
 
    pylab.plot(範囲(numIterations), J_list, "k-" )
シータを返す
 
 
 sgd(アルファ、x、y、num_iter)を定義します。
 「」 「kissg によって書かれた」 「」  
    m = x.shape[0] #サンプル数
    シータ = np.ones(2)
    J_リスト = [] 
 
    # シーケンスをランダム化
    idx = np.random.permutation(y.shape[0])
    x, y = x[idx], y[idx] 
 
 jが範囲内(num_iter)の場合: 
 
 idxのiの場合:
            単一仮説 = np.dot(x[i], θ)
            単一損失 = y[i] - 単一仮説
            勾配 = np.dot(x[i].transpose(), single_loss)
            シータ += アルファ * 勾配 #更新  
 
        仮説 = np.dot(x, theta)
        損失 = y - 仮説
        J = np.sum (損失 ** 2) / (2 * m) # コスト
        J_リストに追加(J)
        print( "iter %s | J: %.3f" % (j, J)) 
 
    pylab.plot(範囲(num_iter), J_list, "r-" )
シータを返す
 
 
 def mbgd(alpha, x, y, num_iter, ミニバッチ):
 「」 「kissg によって書かれた」 「」  
    m = x.shape[0] #サンプル数
    シータ = np.ones(2)
    J_リスト = [] 
 
 jが範囲内(num_iter)の場合: 
 
        idx = np.random.permutation(y.shape[0])
        x, y = x[idx], y[idx]
        mini = np.array_split(range(y.shape[0]), ミニバッチ) 
 
 miniのiの場合:
            mb_hypothesis = np.dot(x[i], θ) です。
            mb_loss = y[i] - mb_hypothesis
            勾配 = np.dot(x[i].transpose(), mb_loss) / ミニバッチ
            シータ += アルファ * 勾配 #更新  
 
        仮説 = np.dot(x, theta)
        損失 = y - 仮説
        J = np.sum (損失 ** 2) / (2 * m) # コスト
        J_リストに追加(J)
        print( "iter %s | J: %.3f" % (j, J)) 
 
    pylab.plot(範囲(num_iter), J_list, "y-" )
シータを返す
 
 
 __name__ == '__main__'の場合: 
 
    x, y = make_regression(n_samples=100, n_features=1, n_informative=1,
                           ランダム状態=0、ノイズ=35)
    m, n = np.shape(x)
    x = np.c_[np.ones(m), x] #挿入 列、バイアス
    アルファ = 0.01 # 学習率
 
    pylab.plot(x[:, 1], y, 'o' )をプロットします。 
 
    print( "\n#***BGD***#\n" )
    theta_bgd = bgd(アルファ、x、y、800)
 iが範囲内(x.shape[1])の場合:
        y_bgd_predict = theta_bgd * x
    pylab.plot(x, y_bgd_predict, 'k--' )をプロットします。 
 
    print( "\n#***SGD***#\n" )
    θ_sgd = sgd(アルファ、x、y、10)
 iが範囲内(x.shape[1])の場合:
        y_sgd_predict = theta_sgd * x
    pylab.plot(x, y_sgd_predict, 'r--' )をプロットします。 
 
    print( "\n#***MBGD***#\n" )
    θ_mbgd = mbgd(アルファ、x、y、50、10)
 iが範囲内(x.shape[1])の場合:
        y_mbgd_predict = theta_mbgd * x
    pylab.plot(x, y_mbgd_predict, 'y--' )をプロットします。 
 
    pylab.show()
    print( "完了しました!" )