Liblinear-Rubyによる線形SVMを試すついでにカーネル近似も試した

はじめに

Liblinearは、線形SVMの実装として有名なライブラリ/ツールである。これをRubyから叩くライブラリとして、Liblinear-Rubyがある。 Rubyの配列で表現された、特徴ベクトルとラベルをわたすだけで、線形SVMの訓練・テストが行える。これで線形SVMによる分類器が簡単にできるので、ついでにカーネル近似も試した。

インストール

Liblinear-Rubyでは、内部的にswigを使っているので、HomebrewでLiblinearだけでなくswigもインストールする。

$ brew install liblinear swig
$ gem install liblinear-ruby

libsvm形式ファイルの読み込み

Rubyでlibsvmフォーマットのファイルを読み込むメソッド書いていたが、どうにも汚くなってしまったので、 PyCallでScikit-Learnのload_svmlight_fileを叩くことにした。トリッキーだけど、PyCallで得られたnumpy.arrayをNMatrixに変換することを、考えてみたかったのもある。あんまりいい感じにならなかったけど。

require 'nmatrix/lapacke'

require 'pycall/import'
include PyCall::Import
pyfrom 'sklearn.datasets', import: 'load_svmlight_file'

def load_libsvm_file(filename)
  # PyCallで呼び出したload_svmlight_fileでlibsvm形式のデータを読み込む。
  py_samples, py_labels = load_svmlight_file.(filename, zero_based: false)
  # サンプル数と次元数を得て、サンプル用のNMatrixとラベル用のNVectorを用意する。
  n_samples, n_dimensions = py_samples.shape
  samples = NMatrix.zeros [n_samples, n_dimensions]
  labels = NVector.zeros n_samples
  # NMatrixとNVectorに変換する。
  n_samples.times do |r|
    labels[r] = py_labels[r].to_i
    n_dimensions.times do |c|
      samples[r,c] = py_samples[r,c].to_f
    end
  end
  return samples, labels
end

Liblinear-Rubyでの分類

まず、動作確認のためのサンプルデータとして、libsvmのサイトからpendigitsデータをダウンロードしておく。

$ wget https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass/pendigits
$ wget https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass/pendigits.t

これらを読み込んで、訓練・テストを行うコードは次の様になる。

# 訓練データを読み込む。
samples, labels = load_libsvm_file 'pendigits'

# Liblinear-Rubyで線形SVMな分類器の訓練を行う。
# データの入力にはRubyの配列を用いるので、
# to_aやto_flat_aでNMatrixを配列に変換する。
Liblinear.quiet_mode
model = Liblinear.train(
  { solver_type: Liblinear::L2R_L2LOSS_SVC },
  labels.to_flat_a,
  samples.to_a)

# テストデータを読み込む。
test_samples, test_labels = load_libsvm_file 'pendigits.t'

# テストデータのラベルを推定する。
# predictメソッドでは、テストデータをまとめて与えるのではなく、
# 特徴ベクトルの一つ一つを与える形になる。
pred_labels = test_samples.to_a.map do |smpl|
  Liblinear.predict(model, smpl).to_i
end

# 正解しているラベルをカウントする。
n_correctly_preds = 0
n_test_samples = test_labels.size
n_test_samples.times do |n|
  n_correctly_preds += 1 if test_labels[n] == pred_labels[n]
end

# Accuracyを計算して出力する。
accuracy = n_correctly_preds / n_test_samples.to_f
puts sprintf("Accuracy = %.4f%% (%d/%d)", 
  accuracy * 100.0, n_correctly_preds, n_test_samples)

これを実行すると、次の様な結果を得られた。これは、当然ながら、Liblinearのコマンドで訓練・テストした場合のAccuracyと一致した。

$ ruby hoge.rb
Accuracy = 87.8788% (3074/3498)

カーネル近似による非線形分類

Liblinearで得られるのは線形分類器なので、特徴空間上で非線形に分布するデータは、正しく分類できない。これを解決する方法で有名なのが、カーネル法だが、データ数が多いと重くなったり、下手をすると動かなかったりする。この問題に対して、カーネルを近似するような変換を考えよう、というアプローチがある。最も有名なのが、ガウスカーネルを近似した、Random Fourier Features（RFF）である。 RFFでは、D個の正規ランダムベクトルwと特徴ベクトルxとの積による変換で表される。

$\displaystyle \phi(\mathbf{x})=\sqrt{1/D}[ \sin(\mathbf{w}_{1}^{\top}\mathbf{x}),\ldots,sin(\mathbf{w}_{D}^{\top}\mathbf{x}), \cos(\mathbf{w}_{1}^{\top}\mathbf{x}),\ldots,cos(\mathbf{w}_{D}^{\top}\mathbf{x}) ]$

これは、正規ランダムベクトルを並べた正規ランダム行列Wを考えると、処理自体は行列-ベクトル積となるので重くない。

$\displaystyle W=[\mathbf{w}_{1},\ldots,\mathbf{w}_{D}]^{\top}$

このRFFの改良版が、NIPS'16においてGoogle ResearchのF X. Yuらが提案した、Orthogonal Random Features（ORF）である。 ORFでは、ランダム行列Wを、カイ分布からサンプルされた要素からなる対角行列S、一様分布なランダム直交行列Qで表す。 ※Qは正規ランダム行列GをQR分解することで得られるそうな。

$\displaystyle W=\frac{1}{\sigma}SQ$

また、次の簡単化したモノも提案されている。

$\displaystyle W=\frac{\sqrt{d}}{\sigma}Q$

直交化することで、カーネル近似の精度が上がるとのこと。さらに論文では、Structured ORFとしてWalsh-Hadamard行列を用いたものも提案されている。

ORFの実装

今回、ORFを試そうと思ったのは、NMatrixのQR分解を試したかったからである。 NMatrixには、正規ランダム行列を生成するメソッドがないので、まずこれを実装する。よくあるBox-Muller法を用いた。

def randn(shape, mu=0.0, sigma=1.0)
  x = NMatrix.random shape
  y = NMatrix.random shape
  ((x.log * -2.0).sqrt * (y * 2.0 * Math::PI).sin) * sigma + mu
end

さらに、正規ランダム行列をQR分解して直交行列を得るメソッドと、特徴変換を行うメソッドは、次のようになる。

# Random Fourier Featuresのための変換行列を得る。
def rff_transform_mat(samples, sigma=100.0)
  n_samples, n_dimensions = samples.shape
  rand_mat = randn [n_dimensions, n_dimensions]
  transform_mat = rand_mat * (1.0 / sigma)
end

# Orthogonal Random Featuresのための変換行列を得る。
def orf_transform_mat(samples, sigma=100.0)
  n_samples, n_dimensions = samples.shape
  rand_mat = randn [n_dimensions, n_dimensions]
  orth_rand_mat, r = rand_mat.factorize_qr
  transform_mat = orth_rand_mat * (Math.sqrt(n_dimensions) / sigma)
end

# 特徴変換を行う。
def mapping(samples, transform_mat)
  n_samples, n_dimensions = samples.shape
  features = samples.dot transform_mat.transpose
  mapped = (features.sin.hconcat features.cos) * Math.sqrt(1.0 / n_dimensions.to_f)
end

これを、訓練データとテストデータに適応する。

# 訓練データを読み込む。
samples, labels = load_libsvm_file 'pendigits'

# 変換行列を計算し、特徴変換を行う。
trans_mat = orf_transform_mat samples
samples = mapping samples, trans_mat

...

# テストデータを読み込む。
test_samples, test_labels = load_libsvm_file 'pendigits.t'

# 特徴変換を行う。
test_samples = mapping test_samples, trans_mat

...

これで実験してみると、RFFのAccuracyが91.84%±1.41で、ORFのAccuracyが93.94%±0.67となった。たしかに、ORFの方がわずかに良い。データセットによりけりだろうけど、元の特徴ベクトルのAccuracyが87.88%なので、カーネル近似による特徴変換により分類精度が向上することが確認できた。

おわりに

思いのほか長くなってしまったので、Liblinear-Rubyとカーネル近似の話で、記事を分けたほうが良かった感。

洋食の日記

「だ・である」調ではなく「です・ます」調で書きはじめれば良かったなと後悔してる人のブログです