Rumaleのロジスティック回帰の最適化手法にL-BFGSを追加した

はじめに

Rumaleのロジスティック回帰のsolverにL-BFGSを追加し、これをデフォルトとして、ver. 0.22.0 としてリリースした。Rumaleのロジスティック回帰では、最適化に確率的勾配降下法（Stochastic Gradient Descent, SGD）を用いていた。データによって、反復回数やミニバッチの大きさなど、ハイパーパラメータを調整する必要があり、手軽に使える感じではなかった。また、Scikit-learnのロジスティック回帰では、L-BFGSを用いるのがデフォルトになっている（以前はLIBLINEARによるものがデフォルトだった）。そこで、Rumaleのロジスティック回帰にもL-BFGSのものを追加した。また、L-BFGSを用いる場合には、多値分類を多項ロジスティック回帰で実現する。

rumale | RubyGems.org | your community gem host

使い方

Rumaleをインストールすれと、L-BFGSのために依存でlbfgb.rbも一緒にインストールされる。

$ gem install rumale

多値分類の例として、LIBSVM DATAのpendigitsデータセットを分類する。

require 'rumale'

# LIBSVM形式のpendigitsデータを読み込む.
x, y = Rumale::Dataset.load_libsvm_file('pendigits')

# ランダム分割で訓練とテストに分割する.
ss = Rumale::ModelSelection::ShuffleSplit.new(n_splits: 1, test_size: 0.2, random_seed: 1)
train_ids, test_ids = ss.split(x, y).first
x_train = x[train_ids, true]
y_train = y[train_ids]
x_test = x[test_ids, true]
y_test = y[test_ids]

# ロジスティック回帰による分類器を学習する.
cls = Rumale::LinearModel::LogisticRegression.new
cls.fit(x_train, y_train)

# テストデータで正確度を計算する.
puts "Accuracy: %.3f" % cls.score(x_test, y_test)

$ wget https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass/pendigits
$ time ruby logit.rb
Accuracy: 0.956
ruby logit.rb  1.15s user 0.16s system 99% cpu 1.317 total

従来のSGDを用いた学習を行う場合はsolverオプションに 'sgd' を渡す。

# SGDはNumo::NArrayでの行列積や内積を行うので, 
# 高速化のために, Numo::Linalgをロードして, OpenBLASを叩くようにする.
require 'numo/openblas'
# SGDでは多値分類はone-vs-rest法を用いる. 
# 各2値分類器の学習を並行して行えるようにParallel gemを使う.
require 'parallel'

...

cls = Rumale::LinearModel::LogisticRegression.new(
  solver: 'sgd',
  learning_rate: 0.001, momentum: 0.9,
  max_iter: 1000, batch_size: 10,
  n_jobs: -1,
  random_seed: 1
)

...

SGDによる最適化の実行時間は、max_iterとbatch_sizeにより変化するが、Numo::LinalgやParallelを使ってもL-BFGSのよりも遅くなっている。

$ time ruby logit.rb
Accuracy: 0.935
ruby logit.rb  394.07s user 56.87s system 574% cpu 1:18.49 total

おわりに

月に一度はRumaleの新しいバージョンをリリースしたいと思っていたが、11月はギリギリになってしまった。最適化にL-BFGSを使うアイディアは以前からあったが、そのベースとなるL-BFGS-Bをgem化するのに、思ったよりも時間がかかってしまった。Numo::NArrayとNumo::Linalg、そしてlbfgs.rbを使えば、Rubyで多くの機械学習アルゴリズムを実装できると考える。Rumaleも色々と発展を予定している。

github.com

非線形最適化手法L-BFGS-BのGemを作成した

はじめに

非線形最適化手法の一つであるL-BFGS-Bは、scipy.optimize.minimizeのデフォルト手法として採用されているなど、最適化手法ではde facto standardの様な存在である。Rではoptim関数がサポートしていたり、Juliaではbindingライブラリがあったりするが、探した限りRubyにはなかったので作成した。

lbfgsb | RubyGems.org | your community gem host

使い方

インストールは、native extensionをビルドできれば、gemコマンドでインストールできる。別で外部ライブラリをインストールする必要はない。Lbfgsb.rbでは、ベクトルをNumo::NArrayで表現するので、一緒にインストールされる。

gem install lbfgsb

使い方は簡単というか、minimizeというmodule functionが一つあるだけである。

require 'lbfgsb'

result = Lbfgsb.minimize(
  fnc: 目的関数, jcb: 目的関数を微分したもの, 
  x_init: 初期ベクトル, args: 目的関数などへの引数
)

p ressult[:x] # 最適化したベクトル

例として、二値分類なロジスティック回帰を実装してみる。ちなみに、現在のScikit-learnのLogisticRegressionも、デフォルトではL-BFGS-Bで最適化を行う。

class LogisticRegression
  def fit(x, y)
    # 切片を得るために特徴ベクトルに1を継ぎ足す.
    xb = Numo::DFloat.hstack([
      x, Numo::DFloat.ones(x.shape[0]).expand_dims(1)
    ])
    # Lbfgsb.rbで最適化する.
    result = Lbfgsb.minimize(
      fnc: method(:obj_fnc), jcb: method(:d_obj_fnc), 
      x_init: xb.mean(0), args: [xb, y]
    )
    # 重みベクトルを得る.
    @weight_vector = result[:x]
  end

  def predict_proba(x)
    # どちらのクラスに属するかの確率を推定する.
    xb = Numo::DFloat.hstack([
      x, Numo::DFloat.ones(x.shape[0]).expand_dims(1)
    ])
    1.0 / (Numo::NMath.exp(-xb.dot(@weight_vector)) + 1.0)
  end

  def predict(x)
    # クラス確率をもとにラベルを付与する.
    probs = predict_proba(x)
    predicted = Numo::Int32.zeros(x.shape[0])
    predicted[probs >= 0.5] = 1
    predicted[probs <  0.5] =-1
    predicted
  end

  private

  # 目的関数
  def obj_fnc(w, x, y)
    Numo::NMath.log(1 + Numo::NMath.exp(-y * x.dot(w))).sum
  end

  # 目的関数を微分したもの. 勾配ベクトルを得る.
  def d_obj_fnc(w, x, y)
    (y / (1 + Numo::NMath.exp(-y * x.dot(w))) - y).dot(x)
  end
end

このロジスティック回帰に、適当なデータを与えて分類を行ってみる。今回は、LIBSVM Dataからsvmguide3というデータを取得した。

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

LIBSVM形式の読み込みと、正確度の計算にはRumaleを使う。

$ gem install rumale

require 'rumale'

# 訓練・テストデータを読み込む.
x, y = Rumale::Dataset.load_libsvm_file('svmguide3')
x_test, y_test = Rumale::Dataset.load_libsvm_file('svmguide3.t')

# ロジスティック回帰による分類器を学習する.
logit = LogisticRegression.new
logit.fit(x, y)

# ラベルを推定する.
predicted = logit.predict(x_test)

# 正確度を計算し, 結果を出力する.
evaluator = Rumale::EvaluationMeasure::Accuracy.new
puts 'ground truth:'
pp y_test
puts 'predicted:'
pp predicted
puts("\nAccuracy: %.1f%%" % (100.0 * evaluator.score(predicted, y_test)))

実行すると以下のようになる。 同様のことを、scikit-learnのLogisticRegressionでも行うと、正確度が61.0%となった。 L-BFGS-Bにより最適化を行うロジスティック回帰を実装できた。 ※scikit-learnの場合、L2正則化項がつくので、ハイパーパラメータを C=1000, max_iter=1000 と調整した。

$ ruby logit.rb
ground truth:
Numo::DFloat#shape=[41]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...]
predicted:
Numo::Int32#shape=[41]
[1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, -1, ...]

Accuracy: 61.0%

苦労話

L-BFGS-B自体は、FORTRAN 77で書かれている。Pythonには、F2PYという、PythonとFortranとをつなぐinterfaceを生成するものがあり、わりと簡単にFortranで書かれた科学計算ライブラリを扱える。Rubyにはそういったものがないので、L-BFGS-BをC言語に翻訳して、native extensionsで叩くことにした。C言語への翻訳には、まず定番のF2Cを使用した。F2Cで生成したC言語のコードは、当然ながらF2Cに依存する箇所がある。例えば、文字列の比較に、strncmp関数を使わずに、s_cmpという独自の関数を使用する。これらF2C独自の関数を、標準的なC言語で書き換えて、F2C依存を消していった。機械的に生成されたコードなため可読性が低く、なかなか骨の折れる作業であった。

おわりに

最適化手法のライブラリがあると、機械学習手法を実装するのが簡単になることが多い。Lbfgs.rbも、Rumaleの開発であるといいな、と思ったので作成した。以前に作成した最適化手法gemのMopti内のアルゴリズムの一種として実装しようかと思ったが、binding libraryとして単体であったほうが、取り回しが良いかなと思って、このような形にした。L-BFGS-B自体がバージョンアップすることはなさそうなので、今後の開発は、bugfixやC言語なコードの修正が、主となる予定である。

github.com

Rubyな形態素解析器Suikaのトライをdarts-clone.rbにした

はじめに

Rubyな形態素解析器Suikaの単語検索のためのトライを、先日リリースしたdarts-clone.rbに変更してバージョンを上げた。

suika | RubyGems.org | your community gem host

使い方

変更は内部的なものなので、Suikaの使い方自体は変わらない。

gem install suika

Suika::Taggerをnewして、parseメソッドに文字列を与えると形態素解析の結果をArrayで返す。今のところ、これ以外の機能はない。辞書はIPADICをベースに、令和の年号を足したものである。

irb(main):001:0> require 'suika'
=> true
irb(main):002:0> tagger = Suika::Tagger.new
irb(main):003:0> puts tagger.parse('時代は平成から令和に変わる')
時代    名詞,一般,*,*,*,*,時代,ジダイ,ジダイ
は      助詞,係助詞,*,*,*,*,は,ハ,ワ
平成    名詞,固有名詞,一般,*,*,*,平成,ヘイセイ,ヘイセイ
から    助詞,格助詞,一般,*,*,*,から,カラ,カラ
令和    名詞,固有名詞,一般,*,*,*,令和,レイワ,レイワ
に      助詞,格助詞,一般,*,*,*,に,ニ,ニ
変わる  動詞,自立,*,*,五段・ラ行,基本形,変わる,カワル,カワル
=> nil
irb(main):004:0> tagger.parse('時代は平成から令和に変わる')
=> ["時代\t名詞,一般,*,*,*,*,時代,ジダイ,ジダイ", "は\t助詞,係助詞,*,*,*,*,は,ハ,ワ", "平成\t名詞,固有名詞,一般,*,*,*,平成,ヘイセイ,ヘイ
セイ", "から\t助詞,格助詞,一般,*,*,*,から,カラ,カラ", "令和\t名詞,固有名詞,一般,*,*,*,令和,レイワ,レイワ", "に\t助詞,格助詞,一般,*,*,*,
に,ニ,ニ", "変わる\t動詞,自立,*,*,五段・ラ行,基本形,変わる,カワル,カワル"]

変更箇所

大きな変更は、トライをrambling-trieからdarts-clone.rbにしたことである。Suikaでは、辞書の読み込みの遅さが、問題になっていた。darts-clone.rbはサイズがコンパクトになる利点があり、効果があると期待した。私のメインPCは、MacBook Early 2016だが、雑に読み込み時間を数回測ってみて平均したところ、ver. 0.1.4で8.4秒、ver. 0.2.0で5.7秒だった。 その他、Arrayのappendメソッドを使っていたところをpushにしたり、keyword_init引数を使ったStructを普通のクラスに置き換えたりした。これで、Ruby 2.4以前でも動く様になったと思う（Ruby本体の公式サポートが切れているのでCIではテストしていない）。

おわりに

darts-clone.rbはnative extensionsを使用しているので、それに依存するSuikaがPure Rubyなのか怪しいが、辞書の読込時間が改善したので良しとしたい。ひとまず辞書まわりはコレくらいにして、基本的なところはできた。こうなってくると、Rubyな自然言語処理ライブラリも欲しくなってくるが、どういうものが良いんだろうか？といったところ。

ダブル配列ライブラリ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