良くある損失関数の勾配
NIPS 2012の"A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets"(pdf)を読んで思い出したのでメモ。
上記の論文では、stochastic gradient (SG) methodを高速化したstochastic average gradient (SAG) methodを提案している。大雑把な説明をすると、SAGではiterationごとに全てのサンプルに対する勾配の和を用いてパラメータ(重み)ベクトルを更新するのだが、その時にSGと同じようにランダムに選択したサンプルに対する勾配のみを計算してアップデートし、そのほかの勾配は前のiterationで計算したものを用いる(詳細は論文の式(5)のあたりを参照)。単純な実装では、各サンプルに対する勾配とそれらの和が必要になり、スパースベクトルを用いてもデータ量と同じメモリを必要とする。しかし4章の"Implementation Details"に記されているように、多くの損失関数でサンプルに対する勾配は、サンプルのベクトルのスカラ倍で表現できるため、このスカラと全ての勾配の和のみを保持すればよい(サンプルのベクトルは保持しているものと仮定)。
話が回りくどくなってしまったが、以下では良くある損失関数の勾配についてメモしておく(とても簡単な計算だが実装しようとした時によく忘れているため)。
二値分類の目的変数yは+1/-1をとるものとする。以下のx, u, vはサンプル(データ)をあらわすベクトルである。
パラメータ(重み)wがベクトルもしくは行列のとき、zをそれぞれ以下のように定義する。
wがベクトルの時(よくある線形分類の場合) z = y w^T x ∂z/∂w = y x wが行列の時 z = y u^T w v ∂z/∂w = y u v^T
hinge lossの場合、
L(w) = max(0, 1 - z) z < 1の時 ∂L(w)/∂w = -∂z/∂w
hinge lossの2乗の場合、
L(w) = max(0, 1 - z)^2 (1 - z)^2 = 1 - 2z + z^2 z < 1の時 ∂L(w)/∂w = -2 ∂z/∂w + 2z ∂z/∂w = -2 (1 - z) ∂z/∂w
logistic lossの場合、
L(w) = - log (1 / (1 + exp(-z))) = log(1 + exp(-z)) ∂L(w)/∂w = (exp(-z) / (1 + exp(-z))) ∂(-z)/∂w = - (1 / (1 + exp(z))) ∂z/∂w
上の3つの例では、wがベクトルの場合に∂z/∂w = y xのスカラ倍となっており、勾配はサンプルベクトルxのスカラ倍で表せるということが分かる。
ベクトルや行列の計算は以下を参照。