Rumale::SVMにClustered SVMによる分類器を追加した

はじめに

Clustered Support Vector Machine（CSVM）は、データをクラスタリングし、各クラスターごとに線形SVMを学習することで、非線形な分類器を実現する手法である。また、Rumale::SVMは、Rubyの機械学習ライブラリであるRumaleと同様のインターフェースで、様々なSVM アルゴリズムを利用できるGemである。このRumale::SVMに、CSVMを実装した。

Gu, Q., and Han, J., "Clustered Support Vector Machines," In Proc. AISTATS'13, pp. 307--315, 2013.

インストールと使い方

Rumale::SVMのインストールは、gemコマンドで行う。

gem install rumale-svm

例として、LIBSVM Dataにあるletterデータセットの分類を行う。

wget https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass/letter.scale.tr
wget https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass/letter.scale.t

分類性能の評価のためrumale-evaluation_measureをインストールする。

gem install rumale-evaluation_measure

letterのデータを分類して、その分類の正確度を出力するスクリプトは以下の様になる。

require 'rumale/dataset'
require 'rumale/evaluation_measure'
require 'rumale/svm'

# letterデータを読み込む.
x_train, y_train = Rumale::Dataset.load_libsvm_file('letter.scale.tr')
x_test, y_test = Rumale::Dataset.load_libsvm_file('letter.scale.t')

# CSVMによる分類器を生成する.
# パラメータであるクラスタ数は128, 大域正則化パラメータは0.1, 正則化パラメータは10.0とした.
classifier = Rumale::SVM::ClusteredSVC.new(n_clusters: 128, reg_param_global: 0.1, reg_param: 10.0, random_seed: 42)

# 学習データで学習する.
classifier.fit(x_train, y_train)

# テストデータのラベルを推定する.
y_pred = classifier.predict(x_test)

# 推定結果の正確度を出力する.
acc = Rumale::EvaluationMeasure::Accuracy.new
puts format('Accuracy: %.1f%%', (100.0 * acc.score(y_test, y_pred)))

これを実行すると正確度は92.3%となった。

$ ruby example.rb
Accuracy: 92.3%

同様にして、線形SVMの正確度は69.7%、RBFカーネルなカーネル SVMだと正確度は94.6%となった。CSVMが、線形SVMをベースとしているにも関わらず、非線形な分類器であるカーネル SVMに匹敵する結果を得られることがわかる。

アルゴリズムの説明

CSVMは、データをクラスタリングして、各クラスターごとに線形SVMを学習するというコンセプトだが、大域正則化というデータ全体での重みベクトルも学習することで、実際には一つに線形SVMの学習にたどり着く。

$n$ 個のラベル $y_{i}$ が付与されたデータ $\lbrace\mathbf{x}_{1}\ldots\mathbf{x}_{n}\rbrace$ が与えられ、クラスタリング手法により $k$ 個のクラスタ $\lbrace\mathbf{C}_{1}\ldots\mathbf{C}_{k}\rbrace$ に分けられたとする。また、 $l$ 番目のクラスターに含まれるデータ数を $n_{l}$ とする。このとき、CSVMの目的関数は次の様になる。

$\displaystyle \text{argmin}_{\mathbf{w},\mathbf{w}_{l},\xi_{i}^{l}\leq0}\frac{\lambda}{2}||\mathbf{w}||^{2}+\frac{1}{2}\sum_{l=1}^{k}||\mathbf{w}_{l}-\mathbf{w}||^{2}+C\sum_{l=1}^{k}\sum_{i=1}^{n_{l}}\xi_{i}^{l}$

$\displaystyle \text{s.t.} \quad y_{i}^{l}\mathbf{w}_{l}^{\top}\mathbf{x}_{i}^{l}\leq 1-\xi_{i}^{l}, i=1,\ldots,n_{l},\forall l$

ここで、 $\mathbf{w}_{l}$ は $l$ 番目のクラスターでの線形分類するための重みであり、 $\mathbf{w}$ はデータ全体での線形分類するための重みである。 $\xi_{i}^{l}$ はスラック変数である。目的関数の第2項 $\frac{1}{2}\sum_{l=1}^{k}||\mathbf{w}_{l}-\mathbf{w}||^{2}$ は、大域正則化項で、各クラスターに過学習することを防ぐ。いま、 $\mathbf{v}_{l}=\mathbf{w}_{l}-\mathbf{w}$ とおくと、目的関数は次の様に書き直せる。

$\displaystyle \text{argmin}_{\mathbf{w},\mathbf{v}_{l},\xi_{i}^{l}\leq0}\frac{\lambda}{2}||\mathbf{w}||^{2}+\frac{1}{2}\sum_{l=1}^{k}||\mathbf{v}_{l}-\mathbf{w}||^{2}+C\sum_{l=1}^{k}\sum_{i=1}^{n_{l}}\xi_{i}^{l}$

$\displaystyle \text{s.t.} \quad y_{i}^{l}(\mathbf{v}_{l}+\mathbf{w})^{\top}\mathbf{x}_{i}^{l}\leq 1-\xi_{i}^{l}, i=1,\ldots,n_{l},\forall l$

さらに、問題を簡単にするため、データと重みベクトルをもとに、以下を定義する。

$\displaystyle \tilde{\mathbf{w}}=\big\lbrack \sqrt{\lambda}\mathbf{w}^{\top},\mathbf{v}_{1}^{\top},\ldots,\mathbf{v}_{k}^{\top} \big\rbrack^{\top}$

$\displaystyle \tilde{\mathbf{x}}_{i}^{l}=\big\lbrack \frac{1}{\sqrt{\lambda}}\mathbf{x}_{i}^{l \top},\mathbf{0}^{\top}\ldots,\mathbf{x}_{i}^{l \top}\dots,\mathbf{0}^{\top} \big\rbrack^{\top}$

ここで、 $\tilde{\mathbf{x}}_{i}^{l}$ の $(l+1)$ 番目の要素は $\mathbf{x}_{i}^{l}$ となる。これにより、目的関数は一般的な線形SVMと同様のものに簡単化できる。

$\displaystyle \text{argmin}_{\tilde{\mathbf{w}},\xi_{i}^{l}\leq0}\frac{\lambda}{2}||\tilde{\mathbf{w}}||^{2}+C\sum_{l=1}^{k}\sum_{i=1}^{n_{l}}\xi_{i}^{l}$

$\displaystyle \text{s.t.} \quad y_{i}^{l}\tilde{\mathbf{w}}^{\top}\tilde{\mathbf{x}}_{i}^{l}\leq 1-\xi_{i}^{l}, i=1,\ldots,n_{l},\forall l$

このように、CSVMでは、各クラスタごとに線形SVMを学習するというところから、特徴変換により単一の線形SVMの問題にたどり着く。

よくある2-moonsデータで、CSVMの決定境界を示すと次のようになる。クラスタ数は8とした。

非線形な決定境界が得られているのがわかる。クラスタ数を32と増やすとより滑らかな決定境界が得られる。

おわりに

Clustered Support Vector Machine（CSVM）は、各クラスタごとに線形SVMを学習することで、非線形な分類を実現しようという手法である。その最適化問題は、大域正則化を取り入れることで、特徴変換と単一の線形SVMの学習にいたるのがおもしろい。ただ、特徴変換後の特徴ベクトルの次元数は、クラスタ数に依存する。非線形でなめらかな決定境界を得ようとして、クラスタ数を大きくしたくなるが、そうすると、特徴変換後の特徴ベクトルの次元数が大きくなりすぎる。特に、元の特徴ベクトルの次元数が大きいと、安易にクラスタ数を増やすことはできない。