線形予測の機械学習ツールliblinearで効果最大化のための最適な定数Cを探る

作者: Drew Conway,John Myles White
出版社/メーカー: Oreilly & Associates Inc
発売日: 2012/02/28
メディア: ペーパーバック
クリック: 63回
この商品を含むブログを見る

liblinear

LIBLINEAR -- A Library for Large Linear Classification

10秒で設定可能なlibsvmで機械学習を行う - Yuta.Kikuchiの日記

R言語でSVM(Support Vector Machine)による分類学習 - Yuta.Kikuchiの日記

今日はliblinearを用いた機会学習の話です。今まではSVMを利用するときはkernelオプション付きのR言語のSVM/libsvm/svm-lightを利用していましたが、学習データが多い時に計算時間が何時間も掛かる事に不便を感じていました。そこでSVMのツールについて色々と調べてみたところ、線形予測に特化したliblinearの存在を知りました。公式のDocumentにもlibsvmとliblinearでの線形予測での処理時間が桁違いにliblinearの方が優れていることが記述されています。以下にliblinearの特徴を記述します。

liblinearはinstanceや特徴が100万桁のデータを線形分離するためのtoolであり以下をサポートしています。

L2正則化の分類

L2-loss linear SVM, L1-loss linear SVM, and logistic regression (LR)

L1正則化の分類

L2-loss linear SVM and logistic regression (LR)

Support Vechtor RegressionのL2正則化

L2-loss linear SVR and L1-loss linear SVR

正則化とはOverfittingを回避するために罰則項を与える事です。種類としてはL1,L2,L1L2の3つが良く利用されるもので精度とスパース性によって異なります。L1は精度が低くスパース性が高い、L2は精度が高くスパース性が低い、L1L2は両方を取り入れ精度を高く保ちながらスパース性を高くすることです。

以下の特徴も含んでいます。

LIBSVMのデータformatをサポートし、一般的なSVM ツールと同じ目的で、使い方も似ています。

Multi-Classへの分類が可能。1 ) 2値分類、2 ) Crammer and Singer

モデル選択に対するCross-Validation。

確率推定(logistic regression限定で)が可能。

アンバランスなデータに対しての重み付け。

Matlab/Octave、JAVA、Python、Rubyのinterfaceがある。

liblinear vs libsvm CrossValidation

liblinear、libsvmでの線形予測で統一したCrossValidationの精度と実行時間を比較します。データセットに対して5fold-cross-validationを行います。cross-validationのデータとしてはgisetteのscaleデータを利用しました。LIBSVM Data: Classification (Binary Class) 結果としてはliblinearがAccurary、処理速度ともにlibsvmを上回る結果となりました。

Tool	Accurary	処理時間
liblinear	96.2119%	4.89s
libsvm	96.1417%	96.22s

liblinear

$time /home/yuta/work/liblinear/liblinear-1.91/train -v 5 gisette_scale   
....*
optimization finished, #iter = 45
Objective value = -0.281585
nSV = 657
....*
optimization finished, #iter = 44
Objective value = -0.268779
nSV = 677
....*
optimization finished, #iter = 45
Objective value = -0.266992
nSV = 658
....*
optimization finished, #iter = 48
Objective value = -0.270758
nSV = 663
....*
optimization finished, #iter = 48
Objective value = -0.282720
nSV = 677
Cross Validation Accuracy = 96.2119%
/home/yuta/work/liblinear/liblinear-1.91/train -v 5 gisette_scale  4.89s user 1.68s system 48% cpu 13.452 total

libsvm

/home/yuta/work/libsvm/libsvm-3.12/svm-train -v 5 -t 0 gisette_scale           
.*.*
optimization finished, #iter = 2876
nu = 0.000235
obj = -0.268630, rho = 0.708937
nSV = 638, nBSV = 0
Total nSV = 638
.*.*
optimization finished, #iter = 2921
nu = 0.000246
obj = -0.280181, rho = 0.300795
nSV = 660, nBSV = 0
Total nSV = 660
.*..*
optimization finished, #iter = 3122
nu = 0.000249
obj = -0.283893, rho = 0.352812
nSV = 674, nBSV = 0
Total nSV = 674
.*.*
optimization finished, #iter = 2791
nu = 0.000239
obj = -0.272718, rho = 0.532717
nSV = 623, nBSV = 0
Total nSV = 623
.*.*
optimization finished, #iter = 2837
nu = 0.000236
obj = -0.268811, rho = 0.831119
nSV = 642, nBSV = 0
Total nSV = 642
Cross Validation Accuracy = 96.1417%
Positive (+1) class:
  precision = 0.960545
     recall = 0.960545
   F1 value = 0.960545

Negative (-1) class:
  precision = 0.962251
     recall = 0.962251
   F1 value = 0.962251

/home/yuta/work/libsvm/libsvm-3.12/svm-train -v 5 -t 0 gisette_scale  96.22s user 24.09s system 52% cpu 3:49.32 total

liblinearのPrecision、recall、F値を求める

libsvmでもdefaultのソースではCross-Validation時にPrecision、recall、F値を求めるコードは書かれていませんが、Patchにより差分を加える事でそれらの値を求める事が可能でした。libsvmのCross-ValidationでPrecision、Recall、F値を求めるPatch 同じようにliblinearでもpatchが無いか調べたところ、親切な人がgithubに上げてくれていました。LIBLINEARのcross validationオプションでprecision/recallを出力する ― Gist このpatchをdownloadして元のソースに当ててみます。
$ wget https://raw.github.com/gist/3341000/723cad7b81d28164bb7def833767b93a591cdca0/train.patch
$ patch < train.patch
$ gmake 
$ home/yuta/work/liblinear/liblinear-1.91/train -v 5 gisette_scale
....*
optimization finished, #iter = 45
Objective value = -0.281585
nSV = 657
....*
optimization finished, #iter = 44
Objective value = -0.268779
nSV = 677
....*
optimization finished, #iter = 45
Objective value = -0.266992
nSV = 658
....*
optimization finished, #iter = 48
Objective value = -0.270758
nSV = 663
....*
optimization finished, #iter = 48
Objective value = -0.282720
nSV = 677
Cross Validation Accuracy = 96.2119%
Positive (+1) class:
  precision = 0.962697
     recall = 0.959943
   F1 value = 0.961318

Negative (-1) class:
  precision = 0.961565
     recall = 0.964212
   F1 value = 0.962887

効果最大なCを探る

SVMは多次元にPlotされた座標のマージン最大化を行う分離線を求める手法です。データが奇麗に分けられるような境界線を常に求められれば問題はありませんが、ノイズやデータのオーバーラップなどの影響を受けて正確に分離が行えない事もあります。データの誤りを許さないような方法はハードマージン、ある程度データの誤りを許すがペナルティを与えるのがソフトマージンと呼ばれるものです。ソフトマージンで利用するパラメータにはスラック変数のζ(ゼータ)と外部変数のCがあります。Cパラメータは正則化と同じように誤りに対するペナルティ項です。SVMではスラック変数のゼータと外部パラメータのCの関係はCを大きくする = ゼータを小さくする、Cを小さくする = ゼータを大きくするという調整になっています。
目的関数 : $\frac{1}{2} ||W^2|| + C\Sigma_{i=1}^n + \zeta_{i}$
制約条件 : $y_{i}(W^Tx_{i} + b ) \geq 1 - \zeta_{i}, \zeta_{i} \geq 0$
Cはペナルティ項なのでCを大きくするのは制約を大きくすることを意味するのでCを無限に近づければハードマージン化させることを意味し、逆にCを小さくするとソフトマージン化させることになります。それで最適なCを求めるにはどうしたら良いか？これは総当たりの実験で求めていくしか手段が無いようです。以下のPythonコードでC=0.1〜1、1〜10の5fold-cross-validationを実行してみます。結果としてはC=0.4,0.6,0.9,3,4の時にValidation Accuracy = 96.282%という最大数を得る事が分かりました。Cを掛けた時のAccuraryが線形に変化すると予測していたのですが、どうもバラバラの結果となってしまいました。
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import os,sys
filename = sys.argv[1]

for i in range( 1, 11 ) :
    c = i
    print "5fold-cross-validation C=" + str( c )
    os.system( '/home/yuta/work/liblinear/liblinear-1.91/train -v 5 -c ' + str( c ) + ' ' + filename )
    print "\n"
$ python cross-validation.py /home/yuta/work/data/gisette_scale
5fold-cross-validation C=0.1 Cross Validation Accuracy = 96.2469%
5fold-cross-validation C=0.2 Cross Validation Accuracy = 96.1417%
5fold-cross-validation C=0.3 Cross Validation Accuracy = 96.1768%
5fold-cross-validation C=0.4 Cross Validation Accuracy = 96.282%
5fold-cross-validation C=0.5 Cross Validation Accuracy = 96.2469%
5fold-cross-validation C=0.6 Cross Validation Accuracy = 96.282%
5fold-cross-validation C=0.7 Cross Validation Accuracy = 96.1768%
5fold-cross-validation C=0.8 Cross Validation Accuracy = 96.2469%
5fold-cross-validation C=0.9 Cross Validation Accuracy = 96.282%
5fold-cross-validation C=1 Cross Validation Accuracy = 96.2119%
5fold-cross-validation C=2 Cross Validation Accuracy = 96.2119%
5fold-cross-validation C=3 Cross Validation Accuracy = 96.282%
5fold-cross-validation C=4 Cross Validation Accuracy = 96.282%
5fold-cross-validation C=5 Cross Validation Accuracy = 96.1768%
5fold-cross-validation C=6 Cross Validation Accuracy = 96.2119%
5fold-cross-validation C=7 Cross Validation Accuracy = 96.2119%
5fold-cross-validation C=8 Cross Validation Accuracy = 96.2119%
5fold-cross-validation C=9 Cross Validation Accuracy = 96.2119%
5fold-cross-validation C=10 Cross Validation Accuracy = 96.2119%
まとめ

liblinearは様々な正則化に対応している。

liblinearはSVMの線形予測を行うツールだがlibsvmより処理速度が速い。

SVMの線形データの分離の制限はC定数にて行う。C定数を小さくすれば条件は緩く、大きくすれば条件を厳しくすることになる。

Links

SVM実践ガイド

SVM実践ガイド (A Practical Guide to Support Vector Classification) from sleepy_yoshi

統計的機械学習入門 | 中川研究室