Yuta Hayashibe

FOBOS

  • 劣勾配法の問題点
    • 収束が遅い
    • L1正則化に適用してみても，0になる重みの数があまり多くならない

概要

  • 勾配法に似たオンライン学習アルゴリズム

  • 各データについてのパラメーター更新を，勾配法では一気にしていたが，FOBOSでは2ステップに分けている

    1. 損失項の劣勾配法による処理
    2. 正則化項の閉じた形での最適解の計算

  • 更新式について

    • 更新前のパラメータをwtw_tとおく
    • 損失項の劣勾配法による処理を終えたときに得たパラメータをvvをおく
    • 第2ステップの更新式は w_{t+1} = \arg \min_{\bold{w}} \frac{1}{2} || \bold{w} – \bold{v} || ^2 + \hat{\lambda} R(\bold{w})
      • λ^\hat{\lambda}は学習率
      • R()R()は正則化関数
      • RがL1正則化関数なら，wt+1\bold{w}_{t+1}のii番目の値はsign(vi)max⁡(0,∣vi∣−λ^)sign(v_i) \max(0, |v_i| - \hat{\lambda})と計算できる．つまり，「パラメータの各値を定数分だけ00に近づけ，符号が変わったら00で打ち止め（クリッピング）にする」という更新になる

実装上の工夫

  • 正則化の計算の遅延
    • 愚直に毎回，正則化パラメータの全ての次元の値を計算する（定数をひく）のをやめる
    • 損失項の計算に必要になったときにまとめてその次元を計算する（「定数かける更新をサボった回数」をひく）

参考文献