機械学習において確率的勾配降下法（Stochastic gradient descent, SGD）ってよく耳にするけどよく分からない。「確率的勾配降下法わかりやすく」でググった人は数知れないだろう。自分も SGD の本質がどこにあるのか分かっていなかったので改めて調べてみた。

準備：パラメータを "動かす"

本記事のトピックである勾配法では "パラメータを動かす" という考え方が重要となる。そこで、線型回帰を例としてパラメータを "動かす" とはどういうことか説明してみる。ここでは1変数の線形回帰を例として説明する。もちろん線形回帰は降下法なんか使わなくても最適なパラメータを求めることができる。あくまで説明のため線形回帰を例にしているに過ぎない。

1変数の線形回帰とは、与えられた複数の点 $(x_1, y_1), \dots (x_n, y_n)$ に対して誤差の和が最小になるような直線 $y = f(x)$ を引く問題である。たとえば以下の図では赤い直線が解である。

f:id:t-keita:20210801020123p:plain:w500

直線と複数の点の誤差の和は残差の二乗和（esidual sum of squares, RSS）として計算されることが一般的である。具体的には以下の式で与えられる。

$\text{RSS} = \Sigma^{n}_{i=1} (y_{i} - f(x_{i}))^{2}$

いまは $y = f(x)$ は直線なので $f(x) = ax + b$ と表される。中学数学を思い出すと、 $a$ は直線の傾きで、 $b$ は $y$ 切片である。これをふまえて上記の二乗和を $a, b$ の関数 $Q(a,b)$ とみなす。

$Q(a, b) = \Sigma^{n}_{i=1} (y_{i} - (ax_{i} + b)))^{2}$

要するに、与えられた点 $(x_1, y_1), \dots (x_n, y_n)$ は固定であり、パラメータ $a, b$ の値を変えることで関数 $Q(a, b)$ の値が定まると考える。パラメータ $a, b$ を "動かす" ことで、目的関数 $Q(a, b)$ の値をなるべく小さくするアプローチこそが勾配法である。

パラメータ $a, b$ を動かす様子を図示してみる。まずは直線の傾き $a$ のみを動かしてみる。以下の図は赤線で傾き $a=1$ のとき、緑線で傾き $a=2$ のときの直線を示している。

f:id:t-keita:20210801020216p:plain:w400

当然、 $a$ の値を大きくすると傾きが大きくなり、小さくすると傾きが小さくなる。それと同時に点線の長さの和、すなわち残差の二乗和 $Q(a, b)$ の値も変化する。 $a$ の値を動かしながら $Q(a, b)$ の変化を観察すれば、 $Q(a, b)$ の値を小さくするような $a$ の値が分かりそうである。

同様に、切片 $b$ の値のみを動かしてみる。赤線で切片 $b = -1$ 、緑線で切片 $b = 3$ のときの直線を示している。

f:id:t-keita:20210801020405p:plain:w400

こちらも $b$ の値を動かすことで $Q(a, b)$ の値を小さくするような $b$ の値が分かりそうである。

最急降下法

ここまでの話で、パラメータを動かすと目的関数（誤差）の値も動くことを見てきた。このようにパラメータと目的関数の関係を用いて誤差を最小化する方法として最急降下法（gradient descent）がある。ちなみにこの手法を適用するためには、目的関数 $Q(a, b)$ がパラメータ $a, b$ によって偏微分可能である必要がある。

最急降下法の説明をする前に、先ほどの線型回帰においてパラメータ $a, b$ に応じて目的関数 $Q(a, b)$ がとる値を等高線として図示してみる。この図は横軸が $a$ の値、縦軸が $b$ の値になっている。この平面上の点ごとに回帰直線が一意に定まることに注意したい。この平面上を動くことがまさにパラメータを動かすことになる。

f:id:t-keita:20210801020833p:plain:w400

結果として図示されるものは同心円状の等高線になっており、中心に行くほど目的関数（誤差）の値が小さくなっている。つまり、中心に行くほど望ましいパラメータになっている。

最急降下法は、適当なパラメータ $a, b$ からスタートして、この等高線と直交するようなルートをたどって最も低いところへ進んでゆく手法である。いわばアリジゴクの底に落ちるようなルートをたどる。具体的には、点 $(a, b)$ 上において進む方向はその点における勾配を下る方向であり、その勾配はベクトル $\nabla Q = (\frac{\partial Q}{\partial a}, \frac{\partial Q}{\partial b})$ に $(a, b)$ の値を代入することで計算できる。したがって、適当な $(a_0, b_0)$ からスタートし、以下のようにパラメータ $(a_n, b_n)$ を更新してゆけばよい。

更新式： $(a_{n+1}, b_{n+1}) = (a_n, b_n) - \eta \nabla Q(a_n, b_n)$

ただし、 $\eta$ は学習率（Learning rate）であり、更新の大きさを調整する役割がある。

たとえば線型回帰の場合、 $\nabla Q$ は以下の2つの要素からなる。

$\frac{\partial Q}{\partial a} = -2 \Sigma^{n}_{i=1} x_{i}(y_{i} - (ax_{i} + b))$
$\frac{\partial Q}{\partial b} = -2 \Sigma^{n}_{i=1} (y_{i} - (ax_{i} + b))$

これらを用いて、パラメータの初期値 $(a, b) = (3.5, -2)$ として最急降下法を実行した結果は以下である。ただし学習率は 0.001 とし、勾配が十分に小さくなるまでパラメータの更新を繰り返した。

f:id:t-keita:20210801113515p:plain:w400

初期値に対応する点からアリジゴクの坂を下るように底に落ちてゆく様子が見て取れる。ここで重要なことは、初期値が同じであれば何度実行しても同じルートをたどって同じ値に落ち着くということである。つまり "確率的" な挙動はしない。

最急勾配法はパラメータの更新にすべての点との誤差 $Q(a,b)$ の偏微分を用いる。このようにパラメータの更新にすべてのデータを使用する学習方法は "バッチ学習" と呼ばれている。実はバッチ学習はあまり実用的でない。というのも、バッチ学習の計算量は学習データや各データの複雑さに依存するため、たとえば学習データが1億件ある場合、1回のパラメータの更新に1億件に対する誤差の和を計算する必要がある。学習データが1億件というのは現代の機械学習では珍しいことではないというのが怖いところである。

確率的勾配降下法

最急勾配法の課題を解決するため、最急勾配法を乱択アルゴリズムとして近似したのが確率的勾配降下法（Stochastic gradient descent, SGD）である。

SGD の基本的な仕組みは最急勾配法と同じであるが、パラメータの更新ごとにランダムに選んだデータ1つのみを用いるのが改良点である。つまり、パラメータの更新ごとにすべてのデータを用いる代わりに1つのデータだけ用いることで計算量を大幅に削減する。具体的には、ランダムに $i$ を選んだ点 $(x_i, y_i)$ と現在の直線の誤差をもとにパラメータの更新を行う。

更新式： $(a_{n+1}, b_{n+1}) = (a_n, b_n) - \eta \nabla Q_{i}(a_n, b_n)$

ここで、 $Q_{i}$ は $i$ 番目のデータと直線の誤差であり、線型回帰の例では $Q_{i} = (y_{i} - (ax_{i} + b)))^{2}$ である。これを各パラメータ $a, b$ によって偏微分して得られるベクトルが $\nabla Q_{i}$ である。線型回帰の例では具体的に以下である。ここに $\Sigma$ はない。

$\frac{\partial Q_{i}}{\partial a} = -2 x_{i}(y_{i} - (ax_{i} + b))$
$\frac{\partial Q_{i}}{\partial b} = -2 (y_{i} - (ax_{i} + b))$

より理解を深めるために補足すると、SGD では現状のパラメータに対応する直線（下図の赤色の直線）とランダムに選んだ1点との距離のみを考慮してパラメータを更新する。下図の例だと直線の傾き $a$ も切片 $b$ も増加する方向にパラメータが更新されるはずである。

f:id:t-keita:20210801121148p:plain:w400

そして、先ほどと同様にパラメータの初期値を $(a, b) = (3.5, -2)$ として SGD を3回実行した様子を以下に示す。

f:id:t-keita:20210801130155p:plain:w600

3回の実行をそれぞれ赤色、青色、緑色で示している。見てのとおり実行ごとに異なるルートをたどっている。これはもちろん学習に用いるデータをランダムに決めているからであり、乱択アルゴリズムとしての特徴が現れているといえる。これゆえ SGD は "確率的" な挙動をする。

ちなみに、SGD のように1つのデータだけを考慮してパラメータの更新を行うやり方は "オンライン学習" と呼ばれる。SGD はオンライン学習であるが、SGD の本質（stochastic と呼ばれる理由）は乱択アルゴリズムである部分にある。世の中には「最急勾配法をオンライン学習にしたものが SGD である」という説明が見られるが、これだけではランダムネスに言及できていないので説明として不十分であると思ったほうがよさそう。実際、少数のデータをパラメータ更新に用いる "ミチバッチ学習" も（オンライン学習ではないが） SGD の一種として有名である。