RubyでLIBSVM形式のファイルを扱うLibSVMLoaderをバージョンアップした

久しぶりにLibSVMLoaderをアップデートした。

$ gem install libsvmloader

これまでNMatrixで特徴ベクトルとラベルを表現していたが、これをRubyのArrayに変えた。Arrayにすることで、NMatrixだけでなくNumo::NArrayでも使用できる。

require 'libsvmloader'
require 'nmatrix/nmatrix'

# LIBSVM形式のファイルを読み込む。
samples, labels = LibSVMLoader.load_libsvm_file('foo.t')

# ArrayをもとにNMatrixによるサンプル行列・ラベルベクトルを生成する。
samples_nm = N[*samples]
labels_nm = N[*labels]

require 'libsvmloader'
require 'numo/narray'

# LIBSVM形式のファイルを読み込む。
samples, labels = LibSVMLoader.load_libsvm_file('foo.t')

# ArrayをもとにNumo::NArrayによるサンプル行列・ラベルベクトルを生成する。
samples_na = Numo::NArray[*samples]
labels_na = Numo::NArray[*labels]

また、liblinear-rubyは、RubyのArrayでデータをやりとりするので、より使いやすくなる。

$ gem install liblinear-ruby

例として、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

訓練は次のようになる。

require 'libsvmloader'
require 'liblinear'

# pendigitsの訓練データセットを読み込む。
samples, labels = LibSVMLoader.load_libsvm_file('pendigits')

# Liblinearで線形サポートベクターマシンを学習する。
Liblinear.quiet_mode
model = Liblinear.train(
  { solver_type: Liblinear::L2R_L2LOSS_SVC },
  labels,
  samples
)

# 学習したモデルを保存する。
model.save('pendigits.model')

そしてテストは次のようになる。

require 'libsvmloader'
require 'liblinear'

# pendigitsのテストデータセットを読み込む。
samples, labels = LibSVMLoader.load_libsvm_file('pendigits.t')

# 学習したモデルを読み込む。
model = Liblinear::Model.load('pendigits.model')

# テストデータのラベルを推定する（predictメソッドにはサンプルを1つずつ渡す）。
predicted = samples.map { |s| Liblinear.predict(model, s).to_i }

# 正解ラベル数をカウントする。
n_samples = labels.size
n_corrects = Array.new(n_samples) { |n| labels[n] == predicted[n] ? 1 : 0 }.count(1)

# 分類の正確度を出力する。
puts "Accuracy: %.4f" % (n_corrects.fdiv(n_samples))

これらのスクリプトを実行すると、正確度が出力される。約9割が正解している。

Accuracy: 0.8788

だいたい以上のような感じ。インターフェースはあまり変えなかった。label_dtypeやvalue_dtypeオプションを使用すると、ラベルや特徴ベクトルの型を指定できる。また、LIBSVM形式では、特徴ベクトルの添字が1から始まるが、zero_basedオプションにtrueを渡せば、0から始まるとして読み込みを行う。詳しくはドキュメントで。

https://www.rubydoc.info/gems/libsvmloader/0.2.0/LibSVMLoader

SVMKitにクラスタリングと行列分解を実装した

svmkit | RubyGems.org | your community gem host

クラスタリングはK-MeansとDBSCAN、行列分解は主成分分析（Principal Component Analysis, PCA）と非負値行列因子分解（Non-negative Matrix Factorization, NMF）を実装した。K-Meansは、K-Means++による初期値設定を実装した。PCAはベーシックなアルゴリズムでは固有値分解が必要になるが、Numo::NArrayには固有値分解はない（Numo::Linalgにある）ので、今回は不動点法（Fixed-point algorithm）によるものを実装した。DBSCANとNMFはベーシックな手法を実装した。

これ以前に、0.4系では、RMSPropやNADAMといったOptimizerを実装した。Optimizerは深層学習で使われるイメージが強いが、最適化法が確率的勾配降下法（Stochastic Gradient Descent, SGD）であれば、SVMやロジスティック回帰でも有効である。動機としては、SGDなFactorization Machine（FM）が安定せず、その解決策に導入した。FMは、勾配に二乗が含まれるため、学習率のスケジュールがシンプルだと、一時的にでも大きな値が入ると、NaNが出まくるということがあった。また学習率の初期値が適切ではないと、ものすごく低い分類精度になったりした（これら最初は実装誤りを疑ったがlibfmなどでも同じ現象が見られた）。RMSProp系のOptimizerは、勾配を正規化するような形の学習率を求めるので、FMにおいて多少勾配が大きくなっても、NaNが出まくるような暴走はしなくなった。

これで、SVMKitでは、教師あり学習（分類・回帰）と教師なし学習（クラスタリング・次元圧縮）の基本的なことができるようになった。これからはコード整備とパフォーマンスの向上をメインに据えつつ、ちょこちょことアルゴリズムを増やしていこうと思う。

SVMKitでの回帰の実装をだいたい終えました

svmkit | RubyGems.org | your community gem host

• SVMKitの0.3系では、回帰手法の実装を目標としていたが、代表的な手法を実装して、だいたい終えた（※カーネルSVMによる回帰の実装を見送った。SVMKitではStochastic Gradient Descent, SGDでの実装を基本としているが、その場合、回帰に限らず分類器でもカーネルSVMで旨味がでない。別の最適化手法かカーネル近似を充実させることを検討したほうが良さそうで、ひとまず保留とした）。
• RidgeとLassoを実装できたのが良かった。Ridgeについては、最もベーシックな実装をすれば逆行列計算が必要となるが、SVMKitではSGDを用いて実装してある。
• Lassoについては、正則化パラメータを調整することで、スパースな重みベクトルが得られるのが、改めて（現象として）おもしろいなと思った。
• Factorization Machineによる回帰で、学習率とかのハイパーパラメータの設定によってNaNが出まくることに苦心した。試しに、AdaGradやNesterovモーメンタムなど、最近？の深層学習で使われているものを試してみたら、見事に安定して収束するようになった（のでRidge回帰にも導入した。ロス関数が同じ二乗誤差なため）。
• これまでSVMKitでは、最適化にPegasosアルゴリズムによるmini-batch SGDを用いてきたが、もう少しモダンなSGDに切り替えようと思っている。最適化アルゴリズムが変わるのは（仮に分類精度に影響が出ないとしても）、breaking changeなので、0.4系でやっていこうと思う。

SVMKitで回帰の実装をはじめました

はじめに

これまでSVMKitでは、分類とそれに関連する手法の実装を進めていたが、回帰の実装をはじめた。手始めに線形サポートベクター回帰とk-近傍法による回帰を実装した。

svmkit | RubyGems.org | your community gem host

これにあわせて、交差検定を回帰にも対応させたり、決定係数を計算するクラスを追加したりした。

使い方

LIBSVM Dataにあるabaloneという回帰問題のデータセットを使って、

$ wget https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/regression/abalone

線形サポートベクター回帰の5交差検定を行う。

require 'svmkit'

# libsvm形式のデータセットを読み込む．
# 説明変数と目的変数どちらも，整数値で構成される場合は，Numo::Int32を使う実装にしているので、
# 念のためNumo::DFloatに型変換している．
samples, values = SVMKit::Dataset.load_libsvm_file('abalone_scale')
samples = Numo::DFloat.cast(samples)
values = Numo::DFloat.cast(values)

# 線形サポートベクター回帰を定義する．
svr = SVMKit::LinearModel::SVR.new(reg_param: 0.005, epsilon: 0.1, max_iter: 1000, batch_size: 50, random_seed: 1)

# 評価尺度には平均絶対誤差を用いる．
ev = SVMKit::EvaluationMeasure::MeanAbsoluteError.new

# 5-交差検定を行う．
kf = SVMKit::ModelSelection::KFold.new(n_splits: 5, shuffle: true, random_seed: 1)
cv = SVMKit::ModelSelection::CrossValidation.new(estimator: svr, splitter: kf, evaluator: ev)
report = cv.perform(samples, values)

# 結果を表示する．
mae = report[:test_score].inject(:+) / kf.n_splits
puts(sprintf("MAE: %.4f", mae))

これを実行すると次のような感じ。

$ ruby svmkit_svr.rb
MAE: 1.9211

おわりに

Ridge回帰を検討したが、ベーシックな実装だと逆行列の計算が必要となり、その場合numo-linalgとかに依存することになるので、今回は見送った。

0.3系では回帰の実装すすめていきます。 つまらないものですが、よろしくお願い致します。

Rubyで近似最近傍探索ライブラリを作った話

はじめに

Rubyで動く近似最近傍探索（Approximate Nearest Neighbor search, ANN）ライブラリが欲しくなって作成した。

hanny | RubyGems.org | your community gem host

FLANNのRubyバインディングがあり検討したが、FLANN自体の開発が止まっているので、勉強の意味でもゼロから作ることにした。手法は様々なものがあるが、シンプルな実装・データ構造になるものが良いと思い、ハッシュ型ANNを選択した。

ハッシュ型ANN

ハッシュ型ANNでは、ベクトルデータ（特徴ベクトル）をバイナリコードに変換し、それをキーとしてハッシュテーブルを作成する。このとき、もとのベクトルデータが類似しているもの同士は、同じバイナリコードになるような変換にする。検索クエリが与えられると、ハッシュテーブルを作成したときと同様にしてバイナリコードに変換し、ハッシュテーブルを探索する。

再訪 Locality Sensitive Hashing

ハッシュ型ANNは、バイナリコードを計算する処理が重要となる。この処理に関して、たくさんの、xxx Hashingが提案されている（もちろん深層学習を使ったDeep Hashingもある、ハッシュ型ANNの黎明期？にSemantic HashingというDeep Belief Networkをベースにしてた手法もあった）。そのなかで、Locality Sensitive Hashing（LSH）は、ハッシュ型ANNの研究の発端となった最初期の手法である。多くの研究ではベースラインとして使われているが、これを見直した論文がある。

• Deng Cai, “A Revisit of Hashing Algorithms for Approximate Nearest Neighbor Search,” CoRR abs/1612.07545, 2016.

多くの xxx Hashingでは、コード長が短い場合で実験していて、128-bitを超えるコード長も含めて実験してみたら、ランダム射影ベースのLSH（LSHは近似するメトリックで複数種あるが、実験で使われたのはコサイン類似度を近似したもの）は良い感じで、過小評価されてるんじゃないか？という内容になっている。

論文では、複数のハッシュテーブルを用意する探索手法と、バイナリコードのハミング距離をもとに探索する手法との比較も行われており、コード長が32-bitを超える場合は、ハミング距離をもとにする手法が良いらしい（もともとは複数のハッシュテーブルを用意する探索手法があって、空間計算量の節約のためには、ハッシュテーブル上で近接するバケツも探索するのが良いよという話が出て、元のベクトルデータの類似関係がバイナリコードの類似関係に反映されてたほうが良いよねとなって、xxx hashingがたくさん出てきたと記憶している。現在は多くの研究でハミング距離をもとに探索する手法が主流なはず。）

実装のちょっとしたところ

そういったわけで、LSHでハミング距離による探索を実装した。線形代数を必要とするのでNumo::NArrayを用いて実装した。Numo::NArrayにはバイナリコードを表現できるBitクラスがあるので、ハミング距離の計算が簡潔に書けることもある。irbで試すとすれば以下のような感じになる。

> require 'numo/narray'
> a = Numo::Bit[0, 1, 0, 1]
> b = Numo::Bit[0, 1, 1, 0]
> (a ^ b).count # ^ がxorで、countメソッドは1を数える
=> 2

使い方は、READMEのUsageの節が全てです。

おわりに

READMEにExperimentの節を用意して掲載したが、MNISTで簡単にテストしたところ、brute-forceな方法よりも20倍はやく検索できた（もちろん元のベクトルデータの次元数やクエリ数とかで変わってくる）。

今後、xxx hashingを追加していくかは未定で（たくさん手法が提案されていて、どれがベストかはベクトルデータにも寄るので、実装するなら代表的なモノ全てを実装した方が良さそうで、面白いだろうけど大変そう）、LSHのようなdata independentなアプローチで発展があれば、ちょこちょこと実装しても良いかな〜ぐらいに思ってます。

つまらないものですが、よろしくお願い致します。