洋食の日記

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

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

Ruby 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での回帰の実装をだいたい終えました

Ruby 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で回帰の実装をはじめました

Ruby 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 近傍探索

はじめに

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の研究の発端となった最初期の手法である。多くの研究ではベースラインとして使われているが、これを見直した論文がある。

多くの 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系分類器に事後確率を推定するメソッドを追加した

Ruby SVMKit 機械学習 データ分析

はじめに

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

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