Pegasos: Primal Estimated sub-GrAdient SOlver for SVM

March 12, 2022

Pegasosは、SVMの学習のための反復的なアルゴリズムであり、2022年3月現在、scikit-learnのSGDClassifierで学習率を更新に採用されている。 Pegasosは、目的関数の最小値の近似値をもとめる。 求める最小値との誤差を\(\epsilon\), SVMの正則化パラメタを\(\lambda\), 各サンプルの説明変数の0でない要素数の上限を\(d\)とすると、線形カーネルをつかうSVMの時間計算量は、\(\tilde{O}(d/\lambda \epsilon)\)になる。 訓練データの数が計算量に影響しないので、教師データの数に対してスケールする。

教師データを説明変数を\(\boldsymbol{\rm x}_i\in \mathbb{R}^n\), 目的変数を\(y_i\in\{+1, -1\}\)、学習データを\(S=\{(\boldsymbol{\rm x}_i, y_i)\}^m_{i=1}\)として、バイアス項のない目的関数を $$ \min_{\boldsymbol{\rm w}}\frac{\lambda}{2}\mid\mid \boldsymbol{\rm w}\mid\mid^2+\frac{1}{m}\sum_{(\boldsymbol{\rm x}, y)\in S} l(\boldsymbol{\rm w}; (\boldsymbol{\rm x}, y)) $$ $$ l(\boldsymbol{\rm w};(\boldsymbol{\rm x}, y)) = \max \{0, 1-y \langle\boldsymbol{\rm w}, \boldsymbol{\rm x} \rangle\} $$ とおく。 このとき、目的関数の最小値から誤差\(\epsilon\)におさまる値を算出できる\(\boldsymbol{\rm w}\)をもとめる。 なお、バイアス項をふくめる目的関数の学習方法は複数あり、その解説は、論文の後半にある。

ハイパーパラメタは、一度の反復でつかう学習データ数\(k\)と反復回数回数\(T\)の2つである。 確率\(1-\delta\)で最適解から誤差\(\epsilon\)以下の解をえるために必要な反復回数は\(\tilde{O}(1/\delta\lambda\epsilon)\)である。 はじめに、\(\boldsymbol{\rm w}_1\)をノルムが高々\(1/\sqrt{\lambda}\)になる値に初期化する。 以降は、要素数\(k\)の学習データの部分集合\(A_t \subseteq S \)をえらび、\(T\)回以下の手順をくりかえす。 $$ \begin{align} A^+_t &:= \{(\boldsymbol{\rm x}, y)\in A_t : y\langle \boldsymbol{\rm w_t}, \boldsymbol{\rm x} \rangle < 1\}\\ \eta_t &:= \frac{1}{\lambda t}\\ \boldsymbol{\rm w}_{t + \frac{1}{2}} &:= (1-\eta_t\lambda)\boldsymbol{\rm w}_t + \frac{\eta_t}{k}\sum_{\boldsymbol{\rm w}, y\in A_t^+}y\boldsymbol{\rm x}\\ w_{\boldsymbol{w}_{t+1}} &:= \min\left( 1, \frac{1/\sqrt{\lambda}}{\mid\mid \boldsymbol{\rm w}_{t+\frac{1}{2}}\mid\mid} \right)\boldsymbol{\rm w}_{t+\frac{1}{2}} \end{align} $$

論文をこちらからダウンロードできます。