ダブル配列ライブラリDarts-cloneのRuby bindingを作成した

はじめに

Susumu Yataさんが作られたDarts-cloneは、Darts（Double-ARray Trie System）というライブリのクローンで、共通接頭辞検索を実現するデータ構造のダブル配列（Double Array）の実装である。Darts-cloneは、DartsとAPI互換性があり、検索の機能や速度そのままに、辞書サイズの削減を実現している。ダブル配列は、MeCabをはじめ、多くの形態素解析器で採用されているデータ構造で、例えばSudachiPyは、Darts-clonenのPython bindingを使用している。また、Darts-cloneは、Taku Kudoさんが書かれた形態素解析器に関する本でも取り上げられており、ダブル配列を利用するなら標準的なものと言える。

実践・自然言語処理シリーズ2　形態素解析の理論と実装

以前から、Ruby製の形態素解析器のSuikaで、辞書の読み込みの遅さを改善したいと思っていた。解決策にDarts-cloneを利用することを考えたが、Ruby bindingが見つからなかったので、まずはコレを作ることにした。

dartsclone | RubyGems.org | your community gem host

使い方

インストールは、native extensionをビルドできれば、gemコマンドでインストールできる。別で外部ライブラリをインストールする必要はない。

gem install dartsclone

darts-clone.rbによる共通接頭辞検索は以下のようになる。

require 'dartsclone'

da = DartsClone::DoubleArray.new

# 辞書を構築する. 単語は事前にソートされている必要がある.
keys = ['東京', '東京都', '東京都中野区', '東京都庁']
da.build(keys)

# 共通接頭辞を検索する. 検索結果は, 単語と添字によるArrayを返す.
k, v = da.common_prefix_search('東京都中野区')
p k
# => ["東京", "東京都", "東京都中野区"]
p v
# => [0, 1, 2]

# 検索結果がゼロ件の場合は、空のArrayを返す.
p da.common_prefix_search('中野区')
# => []

# 完全一致検索もできる. 添字を返す. 
p da.exact_match_search('東京都中野区')
# => 2

# 辞書にない単語の場合は-1を返す.
p da.exact_match_search('中野区')
# => -1

# 外部ファイルへの保存・読込は次のようになる.
da.save('foo.dat')
da2 = DartsClone::DoubleArray.new
da2.open('foo.dat')
p da2.common_prefix_search('東京都中野区')
# => [["東京", "東京都", "東京都中野区"], [0, 1, 2]]

Darts-cloneの仕様上、辞書を作成するbuildメソッドに渡す単語のArrayは、ソートされている必要がある。最初の単語の並びに意味がある場合は、buildメソッドに、その添字によるArrayをvaluesキーワード引数で渡すとよい。

require 'dartsclone'

# ソートされていない単語によるArray.
base_keys = ['うえお', 'いうえ', 'あいう']

# 単語とその添字によるArrayを作成する.
base_sets = base_keys.map.with_index { |v, i| [v, i] }.sort_by { |v| v.first }
p base_sets
# => [["あいう", 2], ["いうえ", 1], ["うえお", 0]]

# 単語と添字それぞれでArrayを作る.
keys = base_sets.map(&:first)
vals = base_sets.map(&:last)
p keys
# => ["あいう", "いうえ", "うえお"]
p vals
# => [2, 1, 0]

# ダブル配列を作り検索する.
da = DartsClone::DoubleArray.new
da.build(keys, values: vals)
# 検索で元の配列の添字が返る.
p da.exact_match_search('あいう')
# => 2

おわりに

Darts-cloneは、完成されたライブラリであるが、更新あればdarts-clone.rbでも追随したいと思う。また、bugfixはもちろんのこと、私のnative extension力の向上にあわせて改善していきたいと思う。次はSuikaに適用してみて、辞書の読み込み速度改善に効果があるかを、調査・検討したい。

github.com

Rumale::SVMに線形One-Class SVMを追加した

はじめに

LIBLINEARがバージョンアップして、線形One-Class SVM（Linear one-class support vector machine, LOCSVM）が追加された。これに合わせて、Numo::LiblinearとRumale::SVMをアップデートして、LOCSVMに対応した。LOCSVMは、データの分布を推定するような、教師なし学習である。原点からデータまでの距離をマージンと考え、SVMを学習することで、原点に向かってデータの端に決定境界ができるような感じになる。与えられたデータが、学習したデータ分布にちかしいかを判定できるので、応用として外れ値検出がある。

numo-liblinear | RubyGems.org | your community gem host

rumale-svm | RubyGems.org | your community gem host

Numo::Liblinearは、RubyとLIBLINEARのデータの受け渡しに、Numo::NArrayを使う薄いラッパーのようなものなので、以降、APIをRumaleに合わせたRumale::SVMをつかってLOCSVMを試す。

使い方

Gemコマンドでインストールできる。別の外部ライブラリをインストールする必要はない。

$ gem install rumale-svm

LOCSVMでの外れ値検出を試すために人工データを作る。原点から離れて正常データがあり、そこから、離れたところに外れ値データがある（外れ値データであるかは本来不明）。

require 'rumale'
require 'rumale/svm'

# プロットのためにnumo-gnuplotを用いる.
# $ brew install gnuplot
# $ gem install numo-gnuplot
require 'numo/gnuplot' 

# 人工データを作る.
x = Rumale::Utils.rand_normal([90, 2], Random.new(1), 3.0, 0.5)
x_out = Rumale::Utils.rand_normal([10, 2], Random.new(1), 1.0, 0.1)
samples = Numo::NArray.vstack([x, x_out])

# 人工データをpngで出力する.
Numo.gnuplot do
  set(terminal: 'png')
  set(output: 'ocsvm_.png')
  plot('[0:5] [0:5]', samples[true, 0], samples[true, 1], pt: 6, ps: 1)
end

人工データ

作成した人工データをLOCSVMに与えてデータ分布を学習する。LOCSVMのハイパーパラメータにnuがある。これは正則化のためのパラメータだが、外れ値がどの程度含まれているかを表す。人工データは100点で、そのうち10点が外れ値なので、0.1を与えた。これらは本来わからないので、実データでは、このハイパーパラメータのnuの調整が重要となる。

# LOCSVMを定義する.
ocsvm = Rumale::SVM::LinearOneClassSVM.new(nu: 0.1)

# LOCSVMで人工データの分布を学習する.
ocsvm.fit(samples)

# 人工データのラベルを推定する.
# 1であれば正常データ, -1であれば外れ値データといったところ.
labels = ocsvm.predict(samples)

# 結果をpngで出力する.
a = samples[true, 0]
b = samples[true, 1]
plots = labels.to_a.uniq.sort.map do |l|
  [a[labels.eq(l)], b[labels.eq(l)], t: l.to_s, ps: 2]
end

Numo.gnuplot do
  set(terminal: 'png')
  set(output: 'ocsvm.png')
  plot('[0:5] [0:5]', *plots)
end

これを実行すると、以下のようになる。正常値・外れ値としたものがきれいにわかれている。

推定結果

当たり前だが、実際には訓練に使ったものをテストに使うことはない。正常値・外れ値に見立てたデータを与えみても上手くいった。 特徴抽出なり変換なりで、はっきり外れ値が分かれるような場合には、LOCSVMは有効だと考える。

pp ocsvm.predict([[2.3, 2.8], [0.8, 0.5]])
# => 
# Numo::Int32#shape=[2]
# [1, -1]

おわりに

正直、LIBLINEARがバージョンアップされて、新しいアルゴリズムが追加されるとは思わなかった。One-class SVMは、外れ値検出が有名だが、文書分類に応用した研究もあるので、使い方によってはおもしろいことができると思う。あと、deep化したものもあったりして、研究としても続いているようだ。

github.com

近似最近傍探索ライブラリAnnoyのRuby bindingを作成した

はじめに

Annoy (Approximate Nearest Neighbors Oh Yeah) は、C++で書かれた近似最近傍探索ライブラリである。近似最近傍探索とは、その名のとおり、クエリに対して厳密ではなく近似的に近傍にあるものを探索する。高速に探索できるので、大規模データの画像の類似検索などに使われる。インデックスの木の構築では、データ数を二分割するような2点を選び、それらでできる超平面で分割することを繰り返す。k-means tree (vocabulary tree) をアレンジしたような手法になっている。Annoyでは、Python bindingが提供されていて、pipでインストールできる。そのため、Pythonライブラリなイメージがあるが、実際は一つのヘッダーファイルからなるシンプルなライブラリである。これを、native extensionsから叩くかたちでgemにした。

annoy-rb | RubyGems.org | your community gem host

使い方

インストールは、普通にgemコマンドでインストールできる。特別な外部ライブラリもPythonも必要ない。

$ gem install annoy-rb

APIは、AnnoyのPython bindingに合わせた。Python版を使ったことがあれば、すぐに使えると思う。

まずは、検索インデックスを作成する。AnnoyIndexをnewする際に、ベクトルの次元数と、距離基準を指定する（angularはコサイン距離で、他にユークリッド距離やマンハッタン距離などがある）。add_itemメソッドで、データの番号とRuby Arrayによるベクトルを登録していく。そして、buildメソッドで検索インデックスを作成する。作成したインデックスはsaveメソッドで保存できる。

require 'annoy'

n_features = 40 # 検索インデックスに追加するベクトルの次元数
t = Annoy::AnnoyIndex.new(n_features: n_features, metric: 'angular')

# ランダムな値からなるベクトルを1000件追加する.
1000.times do |i|
  v = Array.new(n_features) { rand }
  t.add_item(i, v)
end

# インデックスを構築する. この際, 構築する木の数を指定できる.
# 木の数は, 多いほど検索精度は上がるが遅くなる.
n_trees = 10
t.build(n_trees)

# インデックスを保存する.
t.save('foo.ann')

検索は、get_nns_by_itemとget_nns_by_vectorメソッドで行う。get_nns_by_itemは、検索インデックス中のベクトルを番号で指定し、それをクエリとして検索を行う。get_nns_by_vectorは、クエリとして任意のベクトルをRuby Arrayで与えて検索を行う。

require 'annoy'

# 作成した検索インデックスを読み込む.
n_features = 40
u = Annoy::AnnoyIndex.new(n_features: n_features, metric: 'angular')
u.load('foo.ann')

# アイテム番号0番に近い10件を検索する.
# 近傍とされるアイテムの番号がRuby Arrayで返る.
neighbor_ids = t.get_nns_by_item(0, 10)

# 任意のベクトルに近い10件を検索する.
# include_distancesにtrueを与えると, 距離も返す.
q = Array.new(n_features) { rand }
neighbor_ids, neighbor_dists = t.get_nns_by_vector(1, 10, include_distances: true)

おわりに

Annoyをbindingしたgemを作成した。シンプルにnative extensionsで繋いでるだけで（コードも300行程度）、今後大きくコードを改善する箇所はあまりないが、bugfixやAnnoy側のアップデートなどに対応するなど、ちょこちょこ面倒を見ていきたい。

github.com

Numo::OpenBLASでOpenBLASのダウンロードとビルドのタイミングを変えた

はじめに

Numo::OpenBLASで、インストール時のOpenBLASのダウンロードとビルドを、native extensionの作成時に行うようにして、version 0.2.0 としてリリースした。

numo-openblas | RubyGems.org | your community gem host

使い方

使い方に変更はない。Gemコマンドでインストールできる。インストール時に、OpenBLASをダウンロードしてビルドする。

$ gem install numo-openblas

使用方法はrequireするのみで、Numo::NArrayとNumo::Linalgもrequireされる。

require 'numo/openblas'

x = Numo::DFloat.new(5, 2).rand
c = x.transpose.dot(x)
eig_val, eig_vec = Numo::Linalg.eigh(c)

また、本 version から、OpenBLASのビルドオプションの一部が確認できるようになった。

> require 'numo/openblas'
=> true
> Numo::OpenBLAS::OPENBLAS_VERSION
=> " OpenBLAS 0.3.10 "
> Numo::OpenBLAS::OPENBLAS_CHAR_CORENAME
=> "HASWELL"
> Numo::OpenBLAS::OPENBLAS_NUM_CORES
=> 8

RubyGemsのhooks

前バージョンまでは、RubyGemsのpost_install hookを使って、インストール時のOpenBLASのダウンロードとビルドを行っていた。このRubyGemsのhooksが、動かないことがあるという話があり、自分でも体験したので、どうしたものかな〜と思っていた。また一方、別の話で、OpenBLASのビルド時に自動設定されるオプション（CPUの名前とかコア数とか）が、openblas_config.hに書かれるので、これを参照できないかな〜と思っていた。

この2つを解決するために、native extensionを導入することにした。native extensionをビルドする際に、OpenBLASのダウンロードとビルドを行うようにした（Makefileを作成するextconf.rbにpost_install hookに書いていたものを移植した）。native extensionのビルドは確実に動くので、いい感じになったと思う。ただし、使う側としては「native extensionのビルドがスゴイ重い!!」みたいに見えるようになった。

おわりに

numpyでも、pipでインストールするかcondaでインストールするかで、バックエンドライブラリが違うとかあって、線形代数ライブラリにとって、BLAS/LAPACKをどう使うかは永遠の課題なんだろうなと思う。

github.com

Rumaleからdeprecatedにしてた分類器などを削除した

はじめに

RumaleからFactorization MachineやNadamなど、deprecatedにしていたものを削除して version 0.20.0 としてリリースした。本 version で分類器などの追加はない。シンプルに削除だけでバージョンを切った。

rumale | RubyGems.org | your community gem host

徒然なるままに

Rumaleを良い意味で普通の機械学習ライブラリにするため、過去に個人的な興味で追加したものをdeprecatedにして、時間をおいて削除した。Factorization Machine（FM）は、Rumale（SVMKit）の初期からあるもので、派生アルゴリズムを追加するつもりだった。また、最近の確率的勾配降下法（Stochastic Gradient Descent, SGD）の発展を上手く利用して、FMを実装できないかという興味もあった。ただ、多くの包括的な機械学習ライブラリで、FMは外部ライブラリで拡張するものだったりするので、これにあわせることにした。同じくOptimizerも、Yellow Finなんかを実装したりもしたが、ここをいたずらに増やしてもな、というところで削除した。ちなみに、Rumaleでは、ロジスティック回帰やLassoなどは標準的なSGDで、多層パーセプトロンはAdamで学習するようになっている。Optimizerの削除は、これらには影響しない。FMは色んなバリエーションがあっておもしろいので、Rumale-FMとかそういう名前で、ライブラリを作ってみたい。

おわりに

Rumaleは、機械学習ライブラリとして、それなりにアルゴリズムが充実してきた。それをうけて、最近のRumaleの開発は、ユーティリティ的なモノの追加を進めている。やみくもに大きくしたくないのもある。また、Rumaleを中心として周辺ライブラリの作成もガンバらないとな、と思っている。

github.com