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} $$

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