scikit.learn手法徹底比較！ SVM編
問題設定や細かい実験手法は下のページを参照.
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手法徹底比較！ ナイーブベイズ編
scikit.learnの分類手法を比較するこの企画. 今回はナイーブベイズを検証する.
ナイーブベイズはi番目の入力ベクトルの各次元が, クラスラベル
が与えられると互いに独立, すなわち
となると仮定する分類手法である. ただし, は
の次元数,
はi番目の入力ベクトルのj個目の要素を指す.
学習段階では訓練データから各クラスjごとに確率分布を学習し, 分類する際には
が最大になるようなクラスに分類する.
scikit.learnが提供するナイーブベイズのクラスは
- Gaussian Naive Bayes
- Bernoulli Naive Bayes
- Multinomial Naive Bayes
の3つがある.
Gaussian Naive Bayesは分布をガウス分布で表現するクラスである. 訓練データからこのガウス分布のパラメーターを学習する.
Bernoulli Naive Bayesは入力ベクトルの要素が[0,1]の２値を取る場合のナイーブベイズである. 分布はベルヌーイ分布で表現される.
Multinomial Naive Bayesでは, 入力ベクトルの要素がi番目のデータにおいてj個目の要素が何回出現するか(例えば, ある記事において単語soupが何回出現しているか)を表す. なんかテキスト分類とかに使われているらしい.
今回は入力ベクトルとして各次元が画素の値(0-255)なので使えそうなのはGaussianとBernoulliである. Bernoulliの場合はオプションの閾値を設定すると, 入力ベクトルの値が閾値以上の場合は1, 以下なら0として扱う.
なお入力データは正規化している.
Gaussian Naive Bayes
コンストラクタに引数がないシンプルなクラスnaive_bayes.GaussianNBを用いる.
簡単に使えるかと思いきや
/usr/lib/pymodules/python2.7/sklearn/naive_bayes.py:174: RuntimeWarning: divide by zero encountered in log n_ij = - 0.5 * np.sum(np.log(np.pi * self.sigma_[i, :]))
というエラーメッセージが発生し, 真っ当に動作しなかった.
エラーメッセージから察するに, おそらく分散の無い要素(特定のクラスで常に一定の値を取る要素)が存在する場合, 0割りが発生しうまく動作しないのだろう.
そこで, とりあえずの解決策として, 全要素である程度の分散を持つために元のデータにガウス分布から生成したノイズを足しあわせた. その結果正常に動作するようになったが, データ数1万のケースでも分類精度が75%程度でしかもバッドノウハウにも程がある感じだったので, 詳細な検証は取りやめた.
Bernoulli Naive Bayes
調整するパラメーターは次の3つである.
- fit_prior : 事前分布(クラスごとのデータ数の偏り)を考慮するかどうか
- alpha : 各次元において1を取る確率に関する事前分布を制御する
- binarize : 元のデータを２値化するときに用いる閾値
alphaに関しては詳細な説明が必要だろう. alphaを用いることで, クラスcに属するデータのj番目の要素が1となる確率は
と学習される. ここでは学習データにおいてクラスがcである要素の数,
は学習データにおいてクラスがcでかつj番目の要素が1となる要素の数である. alphaが小さい程, この確率は純粋なデータ内の比率に近づく.
元のデータのラベル比率が均等に近いためか, fit_priorはTrueにしてもFalseにしてもあまり結果が変わらなかったため, 以下fit_priorはTrueと設定する.
クロスバリデーションによってalphaをnumpy.logspace(-5, 0, 6), binarizeをnp.linspace(-0.2,1.2,6)から選んだ. その選んだパラメーターに対して得られた結果は次の通り.
| 訓練データ数 | 正答率 | 学習時間(sec) | 平均予測時間(msec) |
|---|---|---|---|
| 1000 | 0.8134 | 0.0377149582 | 0.0484575987 |
| 3000 | 0.8166 | 0.1247229576 | 0.0482898951 |
| 5000 | 0.8152 | 0.221326828 | 0.0484192133 |
| 10000 | 0.8157 | 0.4449100494 | 0.047160697 |
| 20000 | 0.8179 | 0.919823885 | 0.0482817888 |
正答率が見事に上がらないｗ. やはりモデルの仮定に無理があるためか, 2値化の際の情報の損失が激しいのか. 一方, 学習時間はデータ数に対して線形である. また平均予測時間はデータ数に影響を受けない. これらはアルゴリズムを想像すればまあ納得の行く結果である.
クロスバリデーションをして得た感じとしては, 学習時間は全くパラメーターの影響を受けない. また正答率もalphaなら0から1, binarizeなら0から1という常識的な値から選んでいればそこまで変化しなかった.
