読者です 読者をやめる 読者になる 読者になる

Web就活日記

愛と夢と人生について書きます

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

Machine Learning for Hackers

Machine Learning for Hackers

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

liblinear

今日は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/OctaveJAVAPythonRubyのinterfaceがある。

liblinear vs libsvm CrossValidation

liblinear、libsvmでの線形予測で統一したCrossValidationの精度と実行時間を比較します。データセットに対して5fold-cross-validationを行います。cross-validationのデータとしてはgisetteのscaleデータを利用しました。LIBSVM Data: Classification (Binary Class) はてなブックマーク - 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
/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 はてなブックマーク - 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定数を小さくすれば条件は緩く、大きくすれば条件を厳しくすることになる。

スポンサーリンク