バッチ勾配降下法は : θj:=θj+α∑(yi-h(xi))xji for every j.
確率的勾配降下法は次のとおりです。
loop
{
for i=1 to m,
{
θj:=θj+α(yi-h(xi))xji for every j.
}
}
2 つのアルゴリズムの複雑さの違いに興味があります。複雑さは同じだと思います！どちらも O(m*n) ですが、バッチ勾配は m*n で、確率論は n*m で、順序が違うだけですよね?
A) それは SGD のやり方ではありません。「i」をランダムに選択するか、各ラウンドでデータをシャッフルします。
B) データを通じて固定数のエポックのみを実行すると決定した場合にのみ、あなたは正しいです。
実際には、解に収束するまでアルゴリズムを実行し続ける必要があります。SGD と GD では収束率が異なり、「ランタイムが大きい O(f(x))」という単純なものではありません。それぞれの方法は、異なる目標に到達するまでにかかる時間が異なります。これらは、損失関数やその他の要因によってさらに変化します。
エポックごとに 1 回だけ更新を実行する場合は、より良い代替手段があるため、GD は実際には使用されません。
C) 「m*n、ストキャスティクスは n*m です。順序が違うだけですよね?」あなたの大きなOステートメントが正しければ、それは正しいでしょう。
D) 問題の次元を大きな O に含めるのを忘れていました。
2 つの方法の漸近的な複雑さは、ある意味では同じです。外側のループの複数の反復で両方を実行すると、漸近的に同じ量の作業を行います。違いは、メソッドが実際にどのように動作するかです。
通常、確率的勾配降下法は、非常に大きなトレーニング セットを処理する方法として使用されます。トレーニング セットに 10 億個のアイテムがあるとします。バッチ勾配降下法では、モデル パラメーター (シータ) を更新するたびに、10 億個のアイテムすべてを調べる必要があります。確率的勾配降下法は、処理される各トレーニング セット アイテムのモデル パラメーターのフィッティングを継続的に (より小さな増分ではありますが) 進めます。
トレーニング データセットが非常に大きく、その順序に偏りがない場合は、(示されているように) データセットを順番に繰り返しループすることができます。データセットの連続実行で異なる順序が使用されていないという事実は、実際には問題になりません。