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なアプローチで発展があれば、ちょこちょこと実装しても良いかな〜ぐらいに思ってます。

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

SVMKitのSVM系分類器に事後確率を推定するメソッドを追加した

はじめに

SVMKitのSupport Vector Machine（SVM）系の分類器であるSVCとKernelSVCに、ロジスティック回帰と同様に事後確率を推定するpredict_probaメソッドを追加した。

svmkit | RubyGems.org | your community gem host

これにあわせて、Log-Lossを評価するクラスを追加した。そして、それを良い感じに動かすために、ラベル情報に整数を割り当ててベクトルにするLabelEncoderや、ラベル情報からOne-hot-vectorを生成するOneHotEncoderを追加した。

使い方

事後確率の推定には、SVMの識別関数の値をもとに、シグモイド関数のモデルを当てはめる手法を用いている（詳しくはdocumentのreferenceにある論文を参照）。SVMKitでは、Scikit-Learnにならって、コンストラクタにprobablity引数を追加したので、これをtrueにすると事後確率のためのモデルを計算する。

require 'svmkit'

# LIBSVM形式のデータを読み込む．
samples, labels = SVMKit::Dataset.load_libsvm_file('pendigits')
samples = Numo::DFloat.cast(samples)

# 線形SVMを定義する．事後確率の推定のためprobability引数にtrueを指定する．
svc = SVMKit::LinearModel::SVC.new(reg_param: 1.0, max_iter: 1000, probability: true, random_seed: 1) 

# 評価手法にLogarithmic Lossを用いる．
ev = SVMKit::EvaluationMeasure::LogLoss.new

# 10-交差検定で評価する．
kf = SVMKit::ModelSelection::StratifiedKFold.new(n_splits: 10, shuffle: true, random_seed: 1)
cv = SVMKit::ModelSelection::CrossValidation.new(estimator: svc, splitter: kf, evaluator: ev)
report = cv.perform(samples, labels)

# 結果を出力する
mean_logloss = report[:test_score].inject(:+) / kf.n_splits
puts("Mean log-loss: %.3f" % mean_logloss) 

これを実行すると、平均Log-Lossが出力される。

Mean log-loss: 0.293

マルチクラスなLog-Lossを計算するために、いわゆるLabelEncoderやOneHotEncoderが必要になったので、これも追加した。

おわりに

0.2系も0.2.9にまで達したので、分類器がらみの実装はひとまず置いて、回帰を実装していこうと思う。リファクタリングできる箇所も多いが（基本的に確率的勾配降下法を用いていて共通化できるコードが多い）それもグッと我慢して、分類以外のタスクにも使えるようにすることを優先しよう、という思う。

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

SVMKitのLogistic Regressionの勾配計算に間違いがあったので修正した

はじめに

SVMKitのSVMKit::LinearModel::LogisticRegressionの勾配計算に間違いがあったので修正して0.2.8としてリリースした。

svmkit | RubyGems.org | your community gem host

0.2.8では、与えられたパラメータのチェックなどの細かな部分を補うことを予定していた。そのチェックを兼ねて実データで実験していて間違いに気づいた。

反省

SVMKitでは、基本的に各クラスにspecを用意していて、coverallsでcoverageも100%となっている。学習アルゴリズムの確認には、toydataとも言えるシンプルな合成データを用いていて、LogisticRegressionのspecでも、正しく分類できていた。今回、偶然に試した、手書き数字画像データの分類で、LogisticRegressionを用いた場合のAccuracyが、SVMKit::LinearModel::SVCのAccuracyと比較して30%も低かったことで気づくことができた。今後は、アルゴリズムを追加した場合は、実データでの交差検定で動作を確認していきたい。

おわりに

0.2.8では、予定通り、パラメータのチェックもくわえた。例えば、サンプルはNumo::DFloatの行列、ラベルはNumo::Int32のベクトルで与えないとTypeErrorをraiseする。

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