確率推定つきの SVM を libsvm.rb で試してみる

hfu2007-11-30

libsvm には、"-b 1" オプションという、確率推定機能があります。これを試してみました。学習には libsvm 付属のコマンド svm-train を使い、分類は自作の libsvm.rb を通じて JRuby 上で行えるようにしました。
英単語とドイツ語単語を分類するという例題に取り組んでみた結果、良好な分類性能と、意味ありげな推定確率が得られました。

libsvm の確率推定機能

libsvm のコマンド svm-train 及び svm-predict には、以下のような確率推定オプションがあります。

-b probability_estimates: whether to train a SVC or SVR model for probability estimates, 0 or 1 (default 0)

この確率推定が何を意味しているいるのかを体感するために、適当な例題に対して、実際にこの機能を使ってみました。

例題の設定

単語の入力に対し、それが英単語かドイツ語単語かを判別するタスクを考えます。英単語であればラベル 0 を、ドイツ語単語であればラベル 1 を出力するようにします。また、確率推定の結果も出力するようにします。

学習用入力データの取得

学習用入力データとしては、インターネット上に自由に公開されているテキストを使いました。具体的には、DigBib.Org の FaustとProject Gutenberg の Hamletから本文を 700 行程度取得し、それぞれ faust.txt, hamlet.txt として保存しました。

特徴ベクトル

SVM は次元の呪いに比較的強いとのことでしたので、特に何も考えず、「各単語の各文字の文字コードを並べたベクトル」を特徴ベクトルとします。Mac OS X 上で作業をするので、文字コードは UTF-8 を使っています。ä, ë, ö, ü あたりが分類に効いてきそうです。また、大文字小文字が区別されるところも分類に効いてきそうです。
例題だということで、手間を惜しんで特徴ベクトルの正規化はしないことにしました。

svm-train 入力データの作成

svm-train 用の入力データを、下記のスクリプトにより作成しました：

#!/opt/local/bin/ruby -Ku
# a program to make libsvm training data
require 'jcode'

settings = [{:file => 'faust.txt', :language => 'German', :label => 1},
            {:file => 'hamlet.txt', :language => 'English', :label => 0}]

File.open('train.dat', 'w') do |wf|
  settings.each do |setting|
    File.foreach(setting[:file]) do |line|
      words = line.split(/ |\.|,|\?|\(|\)|-|;|:|&#8211;|\n/)
      words.each do |word|
        next if word.size == 0
        wf.print "#{setting[:label]} "
        i = 1
        word.each_char do |char|
          wf.print "#{i}:#{char.unpack('U')[0]} "
          i += 1
        end
        wf.print "\n"
      end
    end
  end
end

これで、下記のような train.dat が作成されます：

1 1:90 2:117 3:101 4:105 5:103 6:110 7:117 8:110 9:103 
1 1:73 2:104 3:114 
...
0 1:109 2:121 
0 1:108 2:111 3:114 4:100

svm-train による分類モデルの作成

SVM は学習データが多い場合に、学習に時間がかかるところが難点なのだそうです。上記で作成した train.dat (9825 組の学習データ) に対して、以下のようにして確率推定付きのモデルを作成したところ、確かにある程度の時間がかかると感じました。

$ svm-train -b 1 train.dat 
.....*
optimization finished, #iter = 5749
nu = 0.409196
obj = -1909.685270, rho = -0.202575
nSV = 4060, nBSV = 1663
Total nSV = 4060
.....*
optimization finished, #iter = 5771
nu = 0.409420
obj = -1912.090214, rho = 0.203516
nSV = 4168, nBSV = 1631
Total nSV = 4168
.....*
optimization finished, #iter = 5823
nu = 0.416845
obj = -1947.654700, rho = 0.189889
nSV = 4181, nBSV = 1690
Total nSV = 4181
.....*
optimization finished, #iter = 5775
nu = 0.412067
obj = -1928.151754, rho = 0.205131
nSV = 4163, nBSV = 1665
Total nSV = 4163
.....*
optimization finished, #iter = 5560
nu = 0.409514
obj = -1921.051369, rho = 0.218980
nSV = 4172, nBSV = 1666
Total nSV = 4172
......*
optimization finished, #iter = 6786
nu = 0.386823
obj = -2268.001011, rho = -0.214623
nSV = 4774, nBSV = 1962
Total nSV = 4774

サポートベクトル 4774 個という、かなり大きなサポートベクトルマシンができてしまいました。
サポートベクトルマシンのパラメータは、train.dat.model という名前で保存されました。

とりあえず学習用データを分類

とりあえず、学習用データ train.dat に対して svm-predict で分類を行ってみました：

kuro:31_svm_word hfu$ svm-predict -b 1 train.dat train.dat.model output_file
Accuracy = 97.4351% (9573/9825) (classification)

正規化などしていない割に、悪くない結果と何となく思わせる結果が出ています。確率推定の結果は、output_file に格納されました。

確率推定の結果

output_file の内容は、以下のようになっています：

labels 1 0
1 0.957276 0.0427237
1 0.957285 0.0427148
1 0.957318 0.0426822
...
0 0.0320731 0.967927
0 0.0320746 0.967925
0 0.0320748 0.967925

例えば2行目は、「この単語はドイツ語単語と分類した。この分類の推定確率は 95.7%。」ということを言っているものと思います。
output_file 中で、誤推定のレコードは、例えば以下のようになっていました：

0 0.113879 0.886121
0 0.0320651 0.967935
0 0.0320651 0.967935
1 0.681938 0.318062
1 0.957352 0.0426484
1 0.7127 0.2873

かなり確信を持って間違った場合と、正解の確信が低くて間違った場合があるようです。

インタラクティブに分類させる JRuby プログラムを作成

そこで、libsvm.rb （を経由して java 版の libsvm ) を使って、インタラクティブに分類を行わせてみました。試行や確認が手間なくできるようになります。
標準入力から渡される文章の各単語に対して分類結果を出力する JRuby スクリプトとして、以下のようなスクリプトを作成しました：

require 'libsvm'
require 'jcode'

$machine = SVM::Machine.new('train.dat.model')
print "ready:\n"

while gets
  words = $_.split(/ |\.|,|\?|\(|\)|-|;|:|&#8211;|\n/)
  words.each do |word|
    next if word.size == 0
    vector = word.each_char.map {|c| c[0]} # unpack('U') -> malformed UTF-8...
    probs = $machine.probs(vector)
    if probs[0] > probs[1]
      print "> #{word} is #{sprintf('%.2f', probs[0] * 100)}% German word.\n"
    else
      print "> #{word} is #{sprintf('%.2f', probs[1] * 100)}% English word.\n"
    end
  end
end

ここで、libsvm.rb は、http://d.hatena.ne.jp/hfu/20071119/1195448558 で作成したものです。

インタラクティブに分類

このプログラムを実際に動かしてみると、以下のような表示を得られます：

$ jruby interactive.rb
ready:
Auf den Füßen geht's nicht mehr,
> Auf is 95.73% German word.
> den is 95.91% German word.
> Füßen is 63.75% German word.
> geht's is 65.63% German word.
> nicht is 95.73% German word.
> mehr is 95.73% German word.
Lord. The King and Queen and all are coming down.
> Lord is 96.79% English word.
> The is 96.79% English word.
> King is 96.79% English word.
> and is 96.79% English word.
> Queen is 96.79% English word.
> and is 96.79% English word.
> all is 96.80% English word.
> are is 96.79% English word.
> coming is 96.80% English word.
> down is 96.79% English word.

上記の文（学習用データの範囲外から引用したものです。）については、良好な分類結果が得られていることが分かります。

分類の結果

もう少し多く分類してみた結果をソートして以下に示します：

Auf is 95.73% German word.
Auf is 95.73% German word.
Drum is 95.73% German word.
Füßen is 63.75% German word.
Geschöpfen is 63.75% German word.
Ham is 96.79% English word.
Heer is 94.73% German word.
I is 96.79% English word.
If is 96.79% English word.
In is 69.49% German word.
King is 96.79% English word.
Köpfen is 63.75% German word.
Lord is 96.79% English word.
Queen is 96.79% English word.
Sanssouci is 63.75% German word.
The is 96.79% English word.
Von is 96.09% German word.
able is 92.24% German word.
all is 96.80% English word.
and is 96.79% English word.
and is 96.79% English word.
are is 96.79% English word.
as is 96.79% English word.
auf is 95.73% German word.
be is 96.79% English word.
coming is 96.80% English word.
das is 95.73% German word.
den is 95.91% German word.
den is 95.91% German word.
down is 96.79% English word.
fitness is 61.24% German word.
gehn is 93.92% German word.
geht's is 65.63% German word.
happy is 54.70% German word.
heißt is 63.75% German word.
his is 96.80% English word.
is is 99.31% English word.
lustigen is 63.76% German word.
mehr is 95.73% German word.
mine is 96.79% English word.
nicht is 95.73% German word.
now is 96.79% English word.
now is 96.79% English word.
or is 96.79% English word.
provided is 63.75% German word.
ready is 72.50% German word.
so is 96.79% English word.
so is 96.79% English word.
speaks is 61.23% German word.
time is 96.79% English word.
whensoever is 60.25% German word.
wir is 95.73% German word.
Drum is 95.73% German word.
Füßen is 63.75% German word.
Geschöpfen is 63.75% German word.
Ham is 96.79% English word.
Heer is 94.73% German word.
I is 96.79% English word.
If is 96.79% English word.
In is 69.49% German word.
King is 96.79% English word.
Köpfen is 63.75% German word.
Lord is 96.79% English word.
Queen is 96.79% English word.
Sanssouci is 63.75% German word.
The is 96.79% English word.
Von is 96.09% German word.
able is 92.24% German word.
all is 96.80% English word.
and is 96.79% English word.
and is 96.79% English word.
are is 96.79% English word.
as is 96.79% English word.
auf is 95.73% German word.
be is 96.79% English word.
coming is 96.80% English word.
das is 95.73% German word.
den is 95.91% German word.
den is 95.91% German word.
down is 96.79% English word.
fitness is 61.24% German word.
gehn is 93.92% German word.
geht's is 65.63% German word.
happy is 54.70% German word.
heißt is 63.75% German word.
his is 96.80% English word.
is is 99.31% English word.
lustigen is 63.76% German word.
mehr is 95.73% German word.
mine is 96.79% English word.
nicht is 95.73% German word.
now is 96.79% English word.
now is 96.79% English word.
or is 96.79% English word.
provided is 63.75% German word.
ready is 72.50% German word.
so is 96.79% English word.
so is 96.79% English word.
speaks is 61.23% German word.
time is 96.79% English word.
whensoever is 60.25% German word.
wir is 95.73% German word.

安易な特徴ベクトルで正規化もせずに学習させた割には、直感的には良好な分類が得られているような気がします。英語をドイツ語と間違う場合には、推定確率がかなり落ちてくれます。
単語レベルでこの程度の信頼性の判別ができるのであれば、例えば文レベルや文章レベルで言語を判別することは、それほど難しくないように思えました。

結論

SVM は確かに使いやすいかもしれません。推定確率も、使いでがありそうな気がします*1。

*1:推定確率の意味などは、あとで調べたいと思っています。