scikit.learn手法徹底比較！ SVM編

Python 機械学習 scikit

問題設定や細かい実験手法は下のページを参照.
scikit.learn手法徹底比較！ イントロダクション

今回は言わずと知れたSVM(サポートベクターマシン)を試す. 訓練データ数を増やしていったときに, 手書き文字の分類性能がどのように推移していくかを調べる.

SVMの詳細な解説は別の文献を引いて欲しい. PRMLを読んでもいいしこのスライドは結構わかりやすい.
概略だけ書くとSVMは2クラス分類のためのアルゴリズムである. データが散らばる多次元空間を超平面で区切り, データを２つに分類する. その超平面をマージン最大化という基準でひくとわりとうまく行くねというアルゴリズムである. そこで元の空間で分類できなくともカーネルで定義された別の空間だとうまく行くことがあるため, 分野によって様々なカーネルが考案されている. カーネルは2つのデータを引数として取る関数でその値はおそらく類似度を意味する.

学習段階では学習データをうまく分離する超平面を求め, 分類段階ではそれを元にデータを分類する.

scikit.learnでは分類に関するSVMは

  • SVC
  • LinearSVC
  • NuSVC

の3つである. SVCは標準的なソフトマージン(エラーを許容する)SVMである. 一方, NuSVCはエラーを許容する表現が異なるSVMである. LinearSVCはカーネルが線形カーネルの場合に特化したSVMであり, 計算が高速だったり, 他のSVMにはないオプションが指定できたりする. NuSVCとSVCは数学的に等価らしいので, 今回はSVCとLinearSVCに絞って検証する.

なお, 全ての場合においてデータは正規化している. すなわち平均0, 分散1のデータに変換している. おそらくRBFカーネルでは不要なのだが(カーネル幅で等価な表現が可能), 線形カーネルでは多分重要.

SVCクラス

scikit(0.10)のSVCクラスは結構引数が多いが, 分類のみを必要とする際に重要なのは

  • どのカーネルを使うか
  • ペナルティ項Cをどれぐらいに設定するか

である. カーネルはRBFカーネル(Gaussカーネル), 線形カーネル, 多項式カーネル, シグモイドカーネル, ユーザーが計算済みのカーネル行列を使用, から選択できる. 全部試すのは面倒なので, 王道のRBFカーネルのみ試す. RBFカーネルを用いる場合はカーネル幅も決定する必要がある. ペナルティ項は誤分類にどの程度の罰則を与えるかを決める. 大きいほど誤分類に厳しく複雑な境界面を用いてでもデータを正しく分類しようとする.

ちなみにSVCクラスは多クラス分類を行う際に, one-vs-one戦略を採用している. これは, クラスの組み合わせごとに２クラス分類器を作成し, それらの分類器の投票によってクラスを決定する. この問題では, 10クラス存在するので, 10*9/2=45個の識別器が用いられる.

RBFカーネルは次の式で表される.

クロスバリデーションによって２つのパラメーター

を求める必要がある.

今回は, ペナルティ項の候補としてnumpy.logspace(4, 8 ,8), の候補としてnumpy.logspace(-4, -2, 8)を用いた. もう少し広い範囲と狭い範囲でもクロスバリデーションを行い, この範囲で十分だと判断した. コードでは次のように表現できる(実際は異なるコードを用いているが).

for sigma in np.logspace(-4, -2, 8):
  for C in np.logspace(4, 8, 8):
    clf = svm.SVC(C=C, gamma=sigma, scale_C=True)
    scores = cross_validation.cross_val_score(clf, datas, labels, cv=5, n_jobs=5)
    print "score(mean):",np.mean(scores)

SVCクラスの引数であるscale_Cは, ペナルティ項Cをデータ数で割るかどうかである.

訓練データ数を変化させ, それぞれクロスバリデーションで決定したパラメーターに対して, 正答率, 学習時間, 平均予測時間を求めた.

訓練データ数 正答率 学習時間(sec) 平均予測時間(msec)
1000 0.883 0.49 0.51
3000 0.916 2.63 1.14
5000 0.931 7.13 1.91
10000 0.946 29.47 3.70
20000 0.957 69.30 5.06

正答率は思ったより高かった. 画像の性質を使わず高次元データを直接入れてもこれぐらいは出るのか. また, 正答率はデータ数=10000のときに94.6%となっているが, この記事を読むと98.6%までいけるらしい. うーん, 使ってるデータが違うのか, クロスバリデーションが甘いのか.

学習時間はデータ数の２乗オーダー程度で推移しているかに見える. マニュアルによると, データ数の２乗から３乗程度の速度らしい. 予測時間は訓練データ数に対して線形に近い. これはサポート数と比例関係にあるのではと予想しているが検証していない. なお, が大きな値にするほど計算時間は増加した. 例えばデータ数3000のとき, が10^-4のときに比べ10^-2のときは計算時間が3倍程度に増加している. 一方, 上の範囲ではペナルティ項は計算時間にさほど影響を与えなかった.

クロスバリデーションでは, Cが小さすぎると悲しい程結果がでないが(正答率0.10付近), Cが大きすぎてもそこまでの性能劣化は無かった. また, 上のコードのパラメーター集合では, データ数が変化しても, 最適なパラメーターはあまり変わらなかった. データ数10000のときにクロスバリデーションにおいて得たスコアと, クロスバリデーションにかかった時間をまとめた表をリンクしておく.

その他のパラメーター

ここまでで説明していないSVCクラスのパラメーターとして

  • cache_size
  • shrinking

がある. cache_sizeはカーネル行列(カーネル関数の計算結果をまとめたもの)をキャッシュするサイズを指す. カーネル行列はデータ数によっては大きすぎるので, 全てを前もって計算せずに必要なときに計算してキャッシュするようだ. データ数20000のときにデフォルトの200MBから2GBに上げてみたが全く効果がなかった(カーネル行列は1.6GB程あるのだが). もっとデータ数が大きくなったら効いてくるのかもしてない.

shrinkingはBool値で, Trueのときは, 双対問題のパラメーターにおいて最終的に0となるパラメーターを早い段階で検出し, それを問題から取り除くことで計算時間を短縮するテクニックっぽい. データ数20000のときに試しにFalseにしてみた（デフォルトはTrue）が計算時間は変化しなかった. データ数の問題かデータの性質のせいかはわからない.

線形カーネル

線形カーネルでは内積をカーネルとして用いる. scikit.learnはSVMの処理を通常LIBSVMというライブラリに丸投げしているようだが, LinearSVCではLIBLINEARが裏では動いている.
そして多クラス分類にはone-vs-all戦略を用いている. これはそれぞれのクラスごとに, そのクラスと残りのクラスに分ける分類器を作成し, それらをまとめたものから最終的に分類結果を決定する手法である. 今回は10クラスなので分類器は10個となる. そしておそらくデータは, 全ての分類器の中で注目したクラスに割り当てられたもののうち, データが分離境界線から最も離れた分類器のクラスに割り当てられる(未確認).

LinearSVCでは以下の項目をチューニングする.

  • 損失関数をL1にするかL2にするか. L1ならヒンジロスになり, L2なら二乗ヒンジロスになる.
  • 正則化項をL1にするかL2にするか. 通常のSVMはL2であるが, L1にすることでパラメーターが疎になることが期待できる
  • C : ペナルティ項
  • intercept_scaling : 入力ベクトルに付加する定数項(超平面の平行移動に該当)

このスライドの19ページに詳しいが, SVMの最小化する目的関数は次のように表せる.

第一項が予測と実際のラベルとの差を表す損失関数, 第二項が大きすぎるパラメーターにペナルティを与える正則化項である. LinearSVCでは, これらをL1にするかL2にするか選べる. 更に, LinearSVCでは多クラス分類用の実装が存在する. その論文は読んでいないので細かい手法はわからない.

これらのことから次の4つのLinearSVCのバリエーションを比較する.

  • Standard : 損失関数L1, 正則化項L2 (通常のSVM)
  • LossL2 : 損失関数L2, 正則化項L2
  • PenaltyL1 : 損失関数L2, 正則化項L1
  • Multi : 多クラス用SVM

それぞれ次のようなコードで生成できる.

Standard = svm.LinearSVC(C=C, intercept_scaling=intercept, multi_class=False, scale_C=True, loss="l1", penalty="l2", dual=True)
LossL2 = svm.LinearSVC(C=C, intercept_scaling=intercept, multi_class=False, scale_C=True, loss="l2", penalty="l2", dual=True)
PenaltyL1 = svm.LinearSVC(C=C, intercept_scaling=intercept, multi_class=False, scale_C=True, loss="l2", penalty="l1", dual=False)
Multi = svm.LinearSVC(C=C, intercept_scaling=intercept, multi_class=True, scale_C=True)

引数dualはTrueのとき元の最小化問題の双対問題を解くことでパラメーターを求める. StandardとPenaltyL1はそれぞれTrueとFalseしか選択できない. またMultiではこのパラメーターは無視される. よって実質dualが影響するのはLossL2のみである.

それぞれの分類器において, パラメーターC, intercept_scalingをそれぞれ候補numpy.logspace(-1, 4, 8), numpy.logspace(-2,3,8)から5-foldクロスバリデーションによって選択した. しかし, 選択したパラメーターはSVCの場合と異なり正答率が最大のものではない. LinearSVCでは, わずかながらの正答率の向上と引き換えに, 計算時間が大きく増加(ときには8倍程度)してしまうケースが多い. そのため, 正答率が最大のケースeから0.3%以内でクロスバリデーションが最も短時間で終了したパラメーターを使用する. また, たぶん大丈夫だとは思うがSVC程気合を入れてパラメーター調整をしていないため, 必死でやればもう少し性能が向上するかもしれない.

結果は次のようになった

正答率
データ数 Standard LossL2 PenaltyL1 Multi
1000 0.849 0.849 0.843 0.852
3000 0.880 0.884 0.875 0.886
5000 0.892 0.894 0.886 0.899
10000 0.901 0.903 0.903 0.910
20000 0.910 0.908 0.908 0.914

どの手法もそこまで大きな差はない.

学習時間, 平均予測時間

学習時間(秒)

データ数 Standard LossL2 LossL2Dual PenaltyL1 Multi
1000 0.60 0.47 0.43 1.27 0.57
3000 0.87 1.66 0.87 3.95 1.12
5000 1.13 3.97 2.21 5.98 1.29
10000 1.80 9.39 4.77 32.18 5.43
20000 7.23 19.82 9.88 63.81 7.69

LossL2Dualは双対問題を解いた場合のLossL2である. 一方, LossL2は主問題を解いた場合である.
LinearSVCはパラメーターによって学習時間は大きく影響を受けるため, あまりこの値は正確ではなく桁以上の情報は期待できない. ただ, 傾向として双対問題を解く手法(Standard, LossL2Dual)は主問題を解く手法(LossL2, PenaltyL1)よりも速い. これはデータ数 > 入力データの次元ならば主問題を解いた方がいいという公式の解説と異なる(なんでだろう？). データ数に対する反応もパラメーターが変化しているため不安定だが, データ数に線形っぽい.

平均予測時間(ミリ秒)

データ数 Standard LossL2 PenaltyL1 Multi
1000 0.0090 0.0090 0.0090 0.0090
3000 0.0093 0.0093 0.0093 0.0093
5000 0.0096 0.0096 0.0096 0.0096
10000 0.0097 0.0097 0.0098 0.0098
20000 0.0099 0.0099 0.0099 0.0099

平均予測時間は手法ごとに差はない. また, データ数が増えるにつれて微増している. L1正則化によりスパースなパラメーターベクトルを与えると期待されたPenaltyL1も別に速くない. この程度の次元では意味がないのか, うまく疎な解が求まらなかったのか.

クロスバリデーションで感じたのは, 学習時間がパラメーターに強く影響を受けることである. そのため, 最初に何も考えず広い範囲のパラメーター候補に対してクロスバリデーションを行なってしまうと不当に大きい計算コストを支払わされるかもしれない. また, 先程も述べたように, あるパラメーターに対して正答率がわずかに高いパラメーターが, 学習時間が数倍だったりするため場合によっては最も正答率が高いパラメーターを使う選択はベストではない.

Multiに関してはintercept_scalingによってあまり正答率は左右されないように見えた. 一方, 計算時間はパラメーターに大きく左右される.

参考のため各手法のクロスバリデーション結果の一部を表にまとめた.

まとめ

あまりきちんとscikit.learnのSVMを使ったことがなかったので勉強になった. 特にパラメーター変化による計算量の変化はあまりきちんと意識していなかったので, 思ったより大きいことに驚いた(まあそもそもLinearSVCを使ったの初めてだけど).

SVCとLinearSVCの比較は後の記事に譲るつもりだが, やはりSVCは正答率が高い(一般には言えないが). しかし, 予測時間に大きな差があるためLinearSVCを使いたくなる場面も出てくるのかもしれない.