FOBOS

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

概要

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

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

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

  • 更新式について

    • 更新前のパラメータを$w_t$とおく
    • 損失項の劣勾配法による処理を終えたときに得たパラメータを$v$をおく
    • 第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がL1正則化関数なら，$\bold{w}_{t+1}$の$i$番目の値は$sign(v_i) \max(0, |v_i| - \hat{\lambda})$と計算できる．つまり，「パラメータの各値を定数分だけ$0$に近づけ，符号が変わったら$0$で打ち止め（クリッピング）にする」という更新になる

実装上の工夫

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

参考文献