コンピュータはオー・ヘンリーとエドガー・アラン・ポーの文章を見分けられるか?(機械学習/パーセプトロン)

サイボウズ・ラボの中谷です。

以前は nakatani @ cybozu labs でブログを書いていましたが、この "Cybozu Development Inside Out" で書かせていただくことになりました。よろしくお願いします。

そして初回の記事は、なんと前回の続きです(ごめんなさい)。

前回記事「Perceptron を手で計算して理解してみる」では、オンライン機械学習の手法の一つ、パーセプトロンを紙と鉛筆で計算してみましたので、今回はそれを実装してみましょうというお話です。

ソースは github においています。 http://github.com/shuyo/iir/tree/master

Perceptron

実装は簡単。手で計算した後なら、空で実装できてしまいます。
学習対象は前回と同じ AND 演算とし、データもコード内に記述しちゃいましょう。

traindata = [  # AND
  [[0, 0], -1],
  [[1, 0], -1],
  [[0, 1], -1],
  [[1, 1], +1],
]

degree = traindata[0][0].size + 1
w = Array.new(degree, 0)

20.times do |c|
  # shuffle
  traindata = traindata.sort_by{rand}
  
  # training
  n_errors = 0
  traindata.each do |x, t|
    px = [1] + x # phai(x)
    s = 0        # sigma w^T phai(x_n)
    px.each_with_index do |x_i, i|
      s += w[i] * x_i
    end
    if s * t <= 0  # error
      puts [c+1, w, px, s, t].inspect
      n_errors += 1
      px.each_with_index do |x_i, i|
        w[i] += t * x_i
      end
    end
  end

  if n_errors == 0
    puts "convergence: #{c}"
    break
  end
end

puts "w= #{w.inspect}"

これで省略なし、ちゃんと動作するコード全体です。
やっぱり簡単すぎて、本当にこれで学習できるの……? な気分になります。 実行結果。

$ ./percep_test.rb
[1, [0, 0, 0], [1, 0, 0], 0, -1]
[1, [-1, 0, 0], [1, 1, 1], -1, 1]
[1, [0, 1, 1], [1, 0, 1], 1, -1]
[2, [-1, 1, 0], [1, 1, 1], 0, 1]
[2, [0, 2, 1], [1, 1, 0], 2, -1]
[2, [-1, 1, 1], [1, 0, 1], 0, -1]
[3, [-2, 1, 0], [1, 1, 1], -1, 1]
[4, [-1, 2, 1], [1, 1, 0], 1, -1]
[4, [-2, 1, 1], [1, 1, 1], 0, 1]
[5, [-1, 2, 2], [1, 1, 0], 1, -1]
[5, [-2, 1, 2], [1, 0, 1], 0, -1]
[6, [-3, 1, 1], [1, 1, 1], -1, 1]
[7, [-2, 2, 2], [1, 0, 1], 0, -1]
[7, [-3, 2, 1], [1, 1, 1], 0, 1]
[8, [-2, 3, 2], [1, 0, 1], 0, -1]
[8, [-3, 3, 1], [1, 1, 0], 0, -1]
[9, [-4, 2, 1], [1, 1, 1], -1, 1]
[10, [-3, 3, 2], [1, 1, 0], 0, -1]
[10, [-4, 2, 2], [1, 1, 1], 0, 1]
[11, [-3, 3, 3], [1, 1, 0], 0, -1]
convergence: 11
w= [-4, 2, 3]

期待通りの学習結果が出ました。
学習させる前にデータをランダムソートしているので、繰り返し実行してみるたびに収束回数や結果は微妙に異なりますが、だいだい 10周前後で収束します。

ただし実は、出力が 0 のときを正例として扱っていない点が、前回の手計算のときとは異なっています(一般的な実装例や擬似コードがすべてそうなっていたのでそれに倣いました)。
0 を正例としたい場合は "if s * t <= 0" となっているところを、"if (t>0)?(s<0):(s>=0)" などとする必要があります。

NLP なデータを作る

次はもう少し大きいデータで試しましょう。

過去記事 「Perceptron を勉強する前にオンライン機械学習ライブラリを試してみる」 で利用させてもらったのと同じ news20.binary でもいいんですが、中谷が興味があるのは NLP(自然言語処理) な分野なので、そういうデータを使いたいです。

材料は、いつもいつもお世話になっている Project Gutenberg から、O. Henry の "The Four Million"Edgar Allan Poe の "The Works of Edgar Allan Poe - Volume 1" の2つ。
これらの作品から 100 ワードずつ切りだして、使われている単語を素性とし、どちらの作家の文章かを正負であらわす訓練データを libsvm の形式で作成するスクリプト gen_libsvm.rb を書きました。

つまり「 100 ワードから、それがオー・ヘンリーの文章か、エドガー・アラン・ポーの文章か、機械学習によって見分けられるか」を検証します。
ええ、好きなんです、こういうの。

$ cd ./data
$ ./gen_libsvm.rb
gen_libsvm.rb [positive] [negative]

$ ./gen_libsvm.rb 2776.zip 2147-8.zip > henry-poe

スクリプトと O. Henry 対 Poe のデータはともに github にコミットしてあります。

ちなみに。
最初は「コナン・ドイルとチェスタートンを見分けられるか?」にしようと思ったんですが、それぞれ特有の固有名詞があまりにも多くて、ちょっとフェアでないなあと断念しました(苦笑)。
あと、"The Works of Edgar Allan Poe - Volume 1" にはポー自身の文章だけではなく、「ポーについて書かれたほかの人の文章」も入ってしまっているのですが、そこは大目に見てやってください。

再び Perceptron

上のテストプログラムについて、libsvm 形式の訓練データを読み、学習結果を Marshal して出力するように改良したのが perceptron/train.rb です。
訓練データが疎な行列であることを考慮して、データの表現が Array から Hash になっていることと、Average Perceptron にも対応しているのが主な変更点です。

$ cd ./perceptron
$ ./train.rb
Usage: ./train.rb [options] trainfile modelfile
    -i [VAL]                         number of iteration
    -a [VAL]                         algorism

テストデータと学習結果のモデルとを読み込み、評価を出力するのが perceptron/test.rb です。出力形式はオンライン学習ライブラリ を真似させてもらいました。

$ ./test.rb
./test.rb testfile modelfile

まず、上記データを訓練データとテストデータに分けます。

$ sort -R ../data/henry-poe > henry-poe.random
$ wc -l henry-poe.random
1433 henry-poe.random

$ head -1200 henry-poe.random > henry-poe.train
$ tail -233 henry-poe.random > henry-poe.test

全部で 1433 件ありますので、これを 1200 件の訓練データと、233 件のテストデータに分けています。
これらを Perceptron で学習&評価します。

$ ./train.rb -aP henry-poe.train henry-poe.p
convergence: 7

$ ./test.rb henry-poe.test henry-poe.p
Accuracy 94.421% (220/233)
(Answer, Predict): (p,p):70 (p,n):9 (n,p):4 (n,n):150

学習はわずか7周で収束(=全ての訓練データについて、予測と正解が一致)してしまいました。残念ながらこれは訓練データ件数が少ないためです。
評価は 94.4% の精度でした。(p, p) は「正( O. Henry の文章)を O. Henry と予測した」、(p, n) は「O.Henry の文章だけど、負( Poe の文章)と予測した」の意味です。

正直、Perceptron 以前に、Bag of words でここまでの精度が出るとは思っていなかったので驚きました(しかも文章の区切りなども無視した 100ワード、stop word なども含めています)。
これなら「コンピュータはオー・ヘンリーとポーの文章を見分けられる」と言ってもよさそうです。

Average Perceptron も試します。

$ ./train.rb -aAP henry-poe.train henry-poe.ap
convergence: 9

$ ./test.rb henry-poe.test henry-poe.ap
Accuracy 95.279% (222/233)
(Answer, Predict): (p,p):70 (p,n):9 (n,p):2 (n,n):152

訓練データをランダムソート(シードがその都度変わる)しているので、収束回数も学習結果も毎回変わります。
そのため、1回の結果で Perceptron より Average Perceptron の精度が高くても、早合点はできません。
実際、Perceptron の学習を何度かやり直していると、97.0% まで精度が上がることがありました。

Average Perceptron は Perceptron より収束が早いことが期待されるのですが、この訓練データ件数では有為な差は出ないようです。

オンライン学習ライブラリで試す

せっかくだから、同じデータで オンライン学習ライブラリ を試してみます。
自分で書いたコードが妥当な結果を導いているかどうかも検証できます。
Windows(VC++) でビルドしたい人は 「Perceptron を勉強する前にオンライン機械学習ライブラリを試してみる」 参照。

オンライン機械学習ライブラリはさまざまなアルゴリズムに対応していますが、まずは Perceptron と Average Perceptron。 なお、oll_train のオプション -I(繰り返し回数)は Default 10 と書いてありますが、ちゃんと指定しないと繰り返し1回になってしまうようです。

$ ./oll_train.exe P henry-poe.train henry-poe.p -b=1.0 -I=10
$ ./oll_test.exe henry-poe.test henry-poe.p
Accuracy 93.991% (219/233)
(Answer, Predict): (p,p):67 (p,n):12 (n,p):2 (n,n):152

$ ./oll_train.exe AP henry-poe.train henry-poe.ap -b=1.0 -I=10
$ ./oll_test.exe henry-poe.test henry-poe.ap
Accuracy 94.850% (221/233)
(Answer, Predict): (p,p):70 (p,n):9 (n,p):3 (n,n):151

近い結果が出ています。一安心。
ほかのアルゴリズムで、おすすめと書いてある PA1 : Passive Agressive I と CW : Confidence Weighted も試してみましょう。

$ ./oll_train.exe PA1 henry-poe.train henry-poe.pa1 -b=1.0 -I=10
$ ./oll_test.exe .henry-poe.test henry-poe.pa1
Accuracy 96.137% (224/233)
(Answer, Predict): (p,p):71 (p,n):8 (n,p):1 (n,n):153

$ ./oll_train.exe CW henry-poe.train henry-poe.cw -b=1.0 -I=10
$ ./oll_test.exe henry-poe.test henry-poe.cw
Accuracy 98.283% (229/233)
(Answer, Predict): (p,p):75 (p,n):4 (n,p):0 (n,n):154

もっとデータ件数が多くないといけない、ということは置いておいても、Confidence Weighted Linear Classification は精度が高いですね! さすがおすすめ。