scikit.learn手法徹底比較！ 決定木編

今回は決定木を用いて手書き文字データの分類を行う.

決定木の詳細はあらゆる所で解説されているので適当に調べて欲しい. このPDFを参考にしたけど, いい資料かは微妙.
決定木は各節に質問が, 葉にクラスラベルが結び付けられている木（データ構造の木）である. 各節では入力ベクトルのある次元の値に関する質問があり(ex. 入力ベクトルの１次元目は5以上か？), 新たなデータを分類する際は, その質問に対する答えによって, データはその節の左右に振り分けられる. それを再帰的に繰り返すと, データは各葉に振り分けられ, そのデータのクラスラベルは, 葉に割り当てられたクラスラベルになる.

学習段階では, その木の形と節に割り当てる質問を探索する. どのような質問がいいかは, その質問によるデータ集合の不純度(Impurity)の変化によって判断する. 不純度は確率変数の分布に対して割り当てられる量である. k個の値を取る確率変数の確率分布をとすると, 不純度は性質として

• 
• はとなるような確率分布において最小になる
• は全てのに対してとなるような確率分布において最大になる

を持つ. つまり確率が偏る程, 不純度は小さい値となり, 確率が均等になる程, 不純度は大きな値となる. 不純度として使える関数はいくつか種類があるが, エントロピーが最も有名だろう.

訓練集合中で, クラスラベルの各値がどの程度出現するかを確率分布によって表現することができる. 質問前の全データ集合で定義される確率分布の不純度と, 質問後に二つに別れたデータ集合, それぞれの不純度を平均したものとを比較し, 最も不純度が減少するような質問が望ましい. なぜなら, 不純度が小さなデータ集合は同じクラスラベルのものを多く含んでおり, そのようなデータ集合を生み出す質問はそのクラスを抽出する能力が高いと考えられるからだ.

このようにして訓練集合全体を質問の連続によって再帰的に分類していき, 葉に達するとその葉に属する訓練データから, その葉に結びつけるクラスラベルを決定する.

sklearnにおける決定木

さて, 手法の説明はこのぐらいにしてscikit.learnにおける決定木について述べる. scikit.learnではDecisionTreeClassifierを用いて決定木による分類を行う. 分類性能を左右するパラメーターは

• criterion : 不純度としてどのような関数を使うか. entropy(エントロピー)とgini(ジニ係数)がある.
• max_depth : 決定木を構成する際の, 決定木の深さの上限
• min_split : データを分割しながら決定木を構成する際, 節に割り当てられたデータ数がmin_split以下になるとそれ以上分割しない

max_depthとmin_splitはオーバーフィッティングを防ぐために設定する. あまりにデータ数わりあての小さい葉を認めると, ノイズに弱くなりやすいらしい.

実験では各criterion(entropy, gini)ごとに, max_depthを[5,10,20,40,NoLimit]から, min_splitを[1,5,10,20,40]から5-foldクロスバリデーションで最適なパラメーターに設定し, 性能を計測した.

criterion=entropyの場合

データ数	正答率	学習時間(sec)	平均予測時間(msec)
1000	0.6624	0.5122	0.00187
3000	0.7466	1.6600	0.00106
5000	0.7817	2.7806	0.00202
10000	0.8079	5.5169	0.00199
20000	0.8412	10.7413	0.00169

criterion=giniの場合

データ数	正答率	学習時間(sec)	平均予測時間(msec)
1000	0.6924	0.1841	0.00188
3000	0.7362	0.7163	0.00108
5000	0.7729	1.2658	0.00203
10000	0.8033	2.6406	0.00204
20000	0.8293	6.9938	0.00175

まず, 正答率に着目すると概ねentropyの方が少し高いがこの程度では差があると言えるか怪しい. また, データ数が増えるに従って正答率は上昇し続けているので, もっとデータ数を増やすと更なる性能上昇が見込めそう.

学習時間はデータ数に対して線形で増加するようだ. giniの方が一貫して低く, 計算コストが低いことが伺える. 一方, 平均予測時間はデータ数に関係なくわりと早い. そして当たり前だがcriterionとはあまり関係がない.

次にクロスバリデーションの感想. このデータではmin_split=1, max_depth=NoLimitという全くオーバーフィッティング対策をしないセッティングでも性能の劣化は生じなかった. 一方, max_depth=5としたときは大きな性能の劣化が生じた. 計算時間もあまりパラメーターに依存しなかったが, max_depth=5のときは少し早かった. criterion=entropy, N=10000のときのクロスバリデーション結果を記載しておく.

分類性能

min_split＼max_depth	5	10	20	40
1	0.6855	0.8058	0.8029	0.8029
5	0.6855	0.8041	0.8018	0.8018
10	0.6855	0.8041	0.8027	0.8027
20	0.6855	0.8003	0.7993	0.7993
40	0.6855	0.7894	0.7881	0.7881

計算時間

min_split＼max_depth	5	10	20	40
1	4.15	6.23	6.27	6.33
5	4.11	6.05	6.31	6.32
10	4.05	5.87	6.18	6.12
20	3.91	5.92	6.05	6.07
40	4.02	5.77	5.87	6.00

その他のパラメーター

ここまでで触れていないDecisionTreeClassifierのいくつかのパラメーターについて説明する.

• max_features : どのような質問がいいか探索する際に, 入力ベクトルの各次元ごとに質問を試し, 不純度の減少度を比較するのだが, 全部の次元で試すのは計算コストがかかるので, ランダムにmax_features個だけ試す
• min_density : 用いるデータ数の割合が, min_densityより小さくなった場合, データのコピーが発生する. その代わり, maskによる除外サンプルの計算が不要になるので計算速度は速くなる
• compute_importances : 入力ベクトルの各次元がどの程度エラーの削減に寄与したかを計算するかどうか（あまりちゃんと調べていない）

max_featuresは例えば"sqrt"に設定すると, sqrt(次元数)個の次元の中から, 質問するのに最適な次元を選択する. この設定を試してみたところデータ数1万, criterion=entropyで分類性能が76.2%と大きく劣化した. これは考えてみれば当たり前で, この画像データの場合, 情報をあまり含んでいない次元（隅の方とか）が存在するためと思われる.

min_densityは上の説明だけではわかりづらい. コードを読めば一目瞭然である.

if n_node_samples / X.shape[0] <= min_density:
  X = X[sample_mask]
  sample_mask = np.ones((X.shape[0],), dtype=np.bool)

sklearnのDecisionTreeの実装では, 現在の分岐に関わる要素を取り出すのにsample_mask変数を用いて, 必要になった際にその都度取り出すことでメモリコピーを防いでいる. しかし, これは毎回データを取り出すためにオーバーヘッドが生じるため, メモリ使用量とそのオーバーヘッドのトレードオフを制御するのがmin_densityである.

上のコードでは, Xは入力ベクトル全体の集合なのだが, 入力ベクトルの個数中, n_node_samples(今回の分岐に関わるデータ数)の割合がmin_density以下の場合, sample_maskでデータを取り出すのを辞め, 現在使っているデータをコピーし入力ベクトル全体とみなすことで, それ以降の取り出しの手間を省いている.

実験としてmin_density=1.0, つまり毎回コピーするようにしてみたが, このデータでは１割程度の性能改善にしかならなかった.

おまけ実験

公式ヘルプには「次元削減手法を試してみろ」とあるので, 次元削減手法として確率的PCA(主成分分析)と, 入力ベクトルの各次元ごとにラベルとの関連度(本当はちょっと違うが)を調べ上位のもののみを残すSelectKBestを用いて実験を行なってみた. なお, criteria=entropy, データ数1万とする.

まず, PCAで次元削減を行った. 結果は以下の表である. 次元削減時間はPCAにかかった時間である. またoriginalは, 次元削減を行わない際の結果である.

次元数	正答率	次元削減時間	学習時間(sec)	平均予測時間(msec)
10	0.764	22.06	0.68	0.00023
30	0.781	22.30	1.93	0.00025
50	0.779	22.52	3.20	0.00027
100	0.772	23.08	6.39	0.00033
200	0.770	24.26	12.84	0.00068
original(784)	0.808	0.00	5.52	0.00200

PCAによる次元削減によって正答率は残念ながら大きく減少してしまう. 次元削減時間も非常に大きく, 計算量の削減にも寄与しない.

次元削減時間は削減後の次元数にほとんど依存しない. 一方, 学習時間は次元数に対して線形となる. そして, 次元数200のときは次元削減を行わない場合よりも学習時間が大きくなってしまう. 決定木の実装詳細を知らないので原因は不明であるが, 元のデータはスパースなのがPCAによってスパースでなくなるのが学習時間を延ばしていると推測している.

次に, SelectKBestで次元削減を行った. PCAは各特徴(次元)の線形結合を新たな特徴として用いることで次元削減を行うが, こちらは一部の特徴のみを使うことで次元削減を行う.

次が次元削減を行うコードである.

transformer = feature_selection.SelectKBest(feature_selection.f_classif, k=feature_components)
transformer.fit(datas, labels)
datas = transformer.transform(datas)

feature_componentsに削減後の次元数を与える. 今回の場合, ここに50などを指定しても次元数は274になってしまう. これは, 同じぐらい重要な特徴は全部取り込んでしまう実装になっているためである.

次元300で試した結果が次の表である.

次元数	正答率	次元削減時間	学習時間(sec)	平均予測時間(msec)
300	0.812	0.410	3.403	0.00092
original	0.808	0.00	5.52	0.00200

正答率を維持したまま次元削減時間, 学習時間をあわせても時間が短縮されており, 次元削減として有効に働いていることが分かる.

まとめ

やはりSVMなどに比べると性能が低い. ただ, K近傍法に比べて性能が大きく劣るのは意外だった. 決定木とK近傍法の対比としてこちらの資料では

• K近傍法は領域を区切るときに, 入力した値のみを問題にしている. 一方で決定木はラベルを考慮している
• K近傍法は全領域において同じkを用いている. これは領域によって適した値が変わるはずである. 一方, 決定木は領域の区切り方は場所によって様々なサイズを取りうる

としている. これらの利点を活かすにはデータ数が不足していたのかもしれない.

補足情報として, sklearnでは, 決定木にpruning(枝かり)の機能がない. これは, 学習データの一部をよけておき, それぞれの節の分岐が性能向上に寄与するかどうかをそのデータでチェックし, 結果によってはその節を取り除くことで, 過学習を防ぐ枠組みである. これを用いるとおそらく, そこまでmin_splitなどを気にする必要がなくなるため, 結構不便かも知れない.

scikit.learn手法徹底比較！ K近傍法編

今回はK近傍法を用いて手書き文字データを分類する.

K近傍法は, あるデータのクラスを分類する際に, そのデータから距離が近い順にK個訓練集合からデータを取り出し, それらのラベルの投票によって分類対象のラベルを決定するシンプルなアルゴリズムである.

一見, 学習段階では何もしなくて良さそうだが, 与えられたデータと近いデータを効率的に探索するためのデータ構造を構築する必要がある. また, バリエーションとしてはラベルの投票の際に, 投票の重みを均一にせず, 距離に応じた重みを用いるものなどがある.

scikit.learnで近傍法を扱うクラスは

• KNeighborsClassifier
• RadiusNeighborsClassifier

の２つである. 前者は上で説明したK近傍法で, 後者は分類対象から近いものK個の投票ではなく, 分類対象から与えられた距離以内に存在するデータの投票によってラベルを決定する.

KNeighborsClassifier

チューニングするパラメーターは

• K : いくつのデータ点の投票でラベルを決定するか
• weights : 投票の重みを均一(uniform)にするか距離に応じた重み(distance)にするか

のみである. 使いやすくて素晴らしい.

パラメーターKは候補range(1,15,2)からクロスバリデーションによって決定した.
このパラメーターを用いて計測した結果は次の通りである.

データ数	正答率(uniform)	正答率(distance)	学習時間(sec)	平均予測時間(msec)
1000	0.831	0.831	0.030	0.753
3000	0.880	0.886	0.159	2.630
5000	0.896	0.899	0.360	4.375
10000	0.910	0.916	1.083	8.985
20000	0.925	0.928	3.563	18.044

学習時間や平均予測時間は, weightsに関わらない. 正答率は投票の重みをdistanceにすることで少し上昇している(あまり上昇しないとも言える). データ数を増やすにつれ, この範囲では安定に正答率が上昇しており, モデルに囚われないノンパラメトリックな手法の強さを感じる.

学習時間に関して議論する前に, K近傍法の探索アルゴリズムについて説明する.
K近傍法ではパラメーターalgorithmによって近傍点の探索方法を切り替えられる

• ball_tree : BallTreeと呼ばれるデータ構造を用いる. 詳細はFive Balltree Construction Algorithmsを読めばよさそう
• kd_tree : KD木と呼ばれるデータ構造を用いる. 有名
• brute : 単純に全ての点との距離を計算する(ブルートフォース)
• auto : 自動で適切なアルゴリズムを選択する

autoにしたときは次のように用いるアルゴリズムが決定される.

 if self._fit_method == 'auto':
   # BallTree outperforms the others in nearly any circumstance.
   if self.n_neighbors < self._fit_X.shape[0] / 2:
     self._fit_method = 'ball_tree'
   else:
     self._fit_method = 'brute'

要はデータ数が投票に用いる近傍数Kの２倍以上ならBallTreeを用いる(ほぼ常にそうなるだろう). よって上の時間の計測結果はBallTreeに関するものである. そこでアルゴリズムごとにかかる時間を計測した.

学習時間（秒）

データ数	brute	kd_tree	ball_tree
1000	0.001003027	0.0169811249	0.030
3000	0.00289011	0.0603270531	0.159
5000	0.0047779083	0.1013519764	0.360
10000	0.0138828754	?	1.083
20000	0.0262858868	?	3.563

平均予測時間（ミリ秒）

データ数	brute	kd_tree	ball_tree
1000	0.3043016195	4.178539896	0.753
3000	0.9247073889	14.1015777111	2.630
5000	1.5461462021	21.6120795012	4.375
10000	3.1277508974	たくさん	8.985
20000	6.5119547844	たくさん	18.044

学習時間に関しては, さすが何もしないだけあってbruteの経過時間はあってなきがごとしである. kd_treeの方がball_treeより少し速かった. 平均予測時間に関しては意外なことにbruteが一番速い. kd_treeは多次元データに弱いため非常に遅い. ball_treeの特性はよく知らないので誰か教えてください.

この実験より, autoはそこまで信用できないことがわかる. K近傍法を用いると決めた場合は自分でアルゴリズムを試した方がいいかもしれない.

クロスバリデーションをした印象は, 正答率・必要時間ともにKの値に関してそこまで敏感ではなかった. 特に必要時間はball_treeの場合もbruteの場合もほとんど変化しなかった. 正答率のみ記載しておく.

K＼データ数	N=1000	N=3000	N=5000	N=10000	N=20000
1	0.824	0.862	0.886	0.909	0.921
3	0.805	0.863	0.887	0.907	0.924
5	0.791	0.870	0.889	0.907	0.926
7	0.787	0.869	0.888	0.906	0.922
9	0.780	0.863	0.885	0.902	0.919
11	0.777	0.858	0.881	0.904	0.917
13	0.763	0.854	0.877	0.899	0.915

RadiusNeighborsClassifier

データから与えた距離以内の点を元にクラスラベルを決定するクラスである. パラメーターとして距離を指定しなければいけない. クロスバリデーションによって広い範囲から最適な距離を探索したが, 真っ当な性能が出る距離が見つけられなかった. また, 小さすぎる距離(おそらく点と点の間の最短距離以下の距離)を指定した場合, 不親切なエラーメッセージと共に終了してしまう. これらの理由から, このクラスに関しては細かい検証を打ち切った. パラメーターの探索方法が悪かったか, 使い方を間違っていた可能性がある.

まとめ

たくさんデータがある場合は, そこそこ性能が出る印象のあるK近傍法. 今回の実験でもそこそこの正答率を観測できた.

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という常識的な値から選んでいればそこまで変化しなかった.

まとめ

その性能の低さから「論文で負けるためにある分類器」と言われることもあるナイーブベイズさん. この問題でも性能は低かった. だがテキスト分類など一部の分野では使われており, また学習時間も超短いため, 活躍する領域があるんだろう. ナイーブベイズの仮定がうまく効いてくるデータセットでも試してみたい.

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

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

scikit.learn手法徹底比較！ イントロダクション

MNIST手書き文字データセットを利用してscikit.learnのsupervisedな分類アルゴリズムを比較する. パラメーターチューニングや計算時間の感覚が掴みたくて, １回やってみたかった.

MNIST手書き文字データセットとは, 機械学習初学者が何故か必ず与えられると言われている0から9の手書き文字が描かれた画像のデータセットである.

データ概要

次元: 28*28の784次元
値の範囲: 0-255の整数
クラス数: 0-9の10クラス

評価環境:

scikit.learn(sklearn): 0.10
CPU: Xeon E5-2667 (6コア 2.9 GHz)
メモリ: 8GB

この条件でscikit.learnが提供しているアルゴリズムを適用していく. 訓練データ数は, 1000から20000まで変化させ分類精度, 学習時間, 分類時間の推移を観察する. 最終的には全手法の結果をまとめるがしばらくは手法ごとに結果や考察を記事にしていく.

実験詳細

実験の詳しい手続きなど. 細かいことが気になる人以外は読まなくても大丈夫.

実験の主目的

scikit.learnの各分類手法について使い方をまとめる. 使い方というのはパラメーターとしてどのような選択肢があるか, そのパラメーターがどのように性能に影響を与えるかである.

性能への影響の与え方を見るためにMNISTデータセットの分類結果を用いる. しかし分類性能はあくまでこのデータセットに対するものであり, また上下関係はたまたま起こったものである可能性を考慮して欲しい.

実験手順

訓練集合のデータ数を[1000 3000 5000 10000 20000]と変化させて,
それぞれで以下の実験を行う.

1.訓練集合を用いて分類器のパラメーターを決定する
訓練集合を5つに分割し, そのうちの4つで学習, 1つでテストを行い, 分類精度を求める. これを5回繰り返し(5-fold cross validation), 特に注釈のない限り, 平均精度が最も高かった際のパラメーターを以後用いる.

2.テスト集合を用いて分類器の性能を計測する
テスト集合は訓練集合と異なる10000個のデータを使用する. 分類器は1で決定したパラメーターで訓練集合全体を用いて訓練を行う.

計測対象は
・分類精度(正答率)
・学習時間
・平均分類時間
の3つである.

実験手法に対する考察

なぜこのような実験手法を選んだかとバリエーションに関する考察.

有意差検定はしないの？

今回の企画の主旨は, 各分類器の使い方のチュートリアルであって最強の分類器を決めたいわけではない(手書きデータセットだけでやっても...). だから有意差検定はやらなくいいかなー. あと多群の有意差検定で, どれを使うべきかの調査がめんどくさい...

性能計測において正答率の分散を求めないのか

テスト集合のデータ数1万でテストすれば, そこまで大きな誤差は生まれ無いと判断した. 以下詳細.

k個目のデータが分類に成功した際に1, 失敗した際に0を取る確率変数をとする.
今, 分類するデータ数をnとすると中心極限定理より

となる. ただしμとσ^2はそれぞれの平均と分散であり, Nは正規分布を表す. この式の左辺は分類精度に相当する.

σ^2は平均0.5のときに1/4となり最大となる. よってデータ数1万のとき最悪でも分類精度の標準偏差は1/200となる. これより分類精度は±1%の範囲に95.5%程度の確率で収まる.
この実験なら1%程度の誤差ならどうでもいいかなー, ということで分散は与えていない.

訓練集合の取り方は１種類でいいのか？

上の手順では, 訓練集合を全て用いて訓練した分類器によって性能を計測している. しかし訓練集合によって性能が変化することを考えると, 用いる訓練集合を変更して何度か性能を計測し平均などを求めるべきではないか？

うーん...確かにそうなんだけど, 手元にある手描き文字データセットのデータ数が4万ちょっとなので, 最初にテスト集合を定めて, 残りから訓練集合を決定する場合, 訓練データ数2万のとき, オーバーラップしない訓練集合は一つしか取れない. オーバーラップするように訓練集合を取れば, 何種類か訓練集合を取れるけど果たしてそれにどの程度意味があるのか... (クロスバリデーションではオーバーラップするように取ってるけど)

ある実験では訓練集合だったデータを, 次の実験ではテスト集合として用いる操作を許容するともう少し使えるデータは増えるが, その場合, 全実験でクロスバリデーションによるパラメーター決定をしないと「テスト集合を観測する前に全てのパラメーターを決定する」という原則に反してしまう. これはちょっとめんどくさい.

これらの理由から今回は上記のように訓練集合を取ることにした.