文字コードの自動判別を機械学習で


これはMachine Learning Advent Calendar2012の22日目の記事です。

まえがき


アルゴリズム使って実世界の問題を解決できるの面白いナー」とPRML読んだりしているのですが、
研究や仕事で機械学習を使っているわけでもなく、自分の中では純粋に趣味・老後の楽しみ的な位置づけになっています。
しかしせっかく勉強しているのだから何かに使おうと、「有名データを利用するのも面白くないし、良いネタはないか」
と探していたら、以前こんなことを言っていたのを思い出しました。

文字コードの自動判別を機械学習使ってやる、って誰かがやってそうだけど検索しても出てこない

https://twitter.com/tomerun/status/9729721761


というわけで試しにやってみます。
この記事の中で使ったコードはここに置いています。 https://github.com/tomerun/MachineLearning
コメントなどあまり付いてないけどご勘弁を


エンコーディングなんて規則は全部分かってるのだから、精度に関しては機械学習とか持ち出さずともヒューリスティックに判定する方が良いに決まってます。
この記事は、機械学習の手法を使ってみた例でしかないことに注意。

データの準備


データには、「日本語バランス文」の上位1000個を使います。


ダウンロードしてきたデータについて、次の前処理をやります。

  • 形態素がスペースで区切られているので、スペースを全て除去
  • 元はWikipediaから取られた文なので、脚注を表す「^ 」が先頭に付いているものがある。これを取り除く
  • 2箇所、nbspが紛れ込んでいるので除去
  • 1箇所、Shift_JISEUC-JPにマッピングできない文字であるホリゾンタルバー(U+2015)があるので半角ハイフンに置き換え
  • 深圳」の「圳」がShift_JISマッピングできないのでカタカナに置き換え
  • 英数や記号が全て全角になっているので、文ごとに1/2の確率で半角に変換


続いて、1000個の文をそれぞれ、UTF-8、UTF-16LE、Shift_JISEUC-JPの4通りのバイト列に変換します。
ランダムに500文を選んで、500文*4エンコーディングの2000個のバイト列を訓練データ、残りの2000個のバイト列をテストデータとします。


各バイト列を、0〜255の値がそのバイト列中にどのくらいの割合で出現するかを要素とする256次元ベクトルとします。
ベクトルの要素の値が小数だといろいろ面倒なので、割合の値を10倍した整数(小数点以下切り上げ)で扱います。
たとえば、あるバイト列が {1,2,1,3} だった場合、出現割合は1が0.5、2と3が0.25なので、ベクトルは {0, 5, 3, 3, 0, ... } になります。

データの様子


それぞれのエンコーディングについて、バイトごとの値の分布がどのようになっているかのHeat mapを描きました。






確かに傾向が出てますね。
バイトの値の割合を特徴量にするだけで分類できそうだと期待できます。

分類

ナイーブベイズ


以前実装していたナイーブベイズに入れてみます。
ゼロ頻度問題を避けるためのpseudocountは、適当に0.1で(パラメタいろいろ変えてみても結果にはっきりした変化はなかった)。


コード抜粋

NaiveBayesClassifier<Sentence> naiveBayes = new NaiveBayesClassifier<Sentence>(0.1);
naiveBayes.train(Arrays.asList(trainingSet));
int correct = 0;
for (Sentence testData : testSet) {
	int expect = testData.label();
	int actual = naiveBayes.classify(testData);
	if (expect == actual) {
		++correct;
	}
}
System.out.println("correct:" + correct);
System.out.println("wrong:" + (testSet.length - correct));


乱数を変えて5回実行するとこうなりました。

$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1977
wrong:23
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1972
wrong:28
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1984
wrong:16
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1976
wrong:24
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1984
wrong:16


平均正解率98.93%でした。

Random Forest


次はRandom Forestに入れてみます。
実装は以前独自にやっていたものです(なのでたぶんけっこう遅い)。

// RandomForest(決定木の数, 1つの決定木で使う特徴量の数, 1つの決定木の分岐数)
RandomForest<Sentence> randomForest = new RandomForest<Sentence>(500, 6, 300);
randomForest.train(Arrays.asList(trainingSet));
int correct = 0;
for (Sentence testData : testSet) {
	int expect = testData.label();
	int actual = randomForest.classify(testData);
	if (expect == actual) {
		++correct;
	}
}
System.out.println("correct:" + correct);
System.out.println("wrong:" + (testSet.length - correct));


これも5回実行するとこうなりました。

$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1980
wrong:20
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1990
wrong:10
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1989
wrong:11
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1993
wrong:7
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1984
wrong:16


平均正解率99.36%。はっきりとNaiveBayesよりも良い結果が出ています。
ただし、パラメタはいろいろ試行錯誤して一番良くなるように決めたものです。

  • 決定木の数は一定以上増やしても計算時間がかかるばかりで結果は良くならない
  • 1つの決定木で使う素性数を増やしすぎるとかえって悪くなる
  • 分岐数は、Wikipediaなどでは識別問題の場合は1が推奨と書かれているけど、この問題については大幅に増やした方が断然良かった
(参考)nkf


比較対象として、nkfに推定させてみました。
どうもnkfUTF-16が判定できないみたいなので、1000文*3エンコーディングの3000個のテストデータについて試しています。

$ ls UTF-8/*.dat | xargs nkf -g | grep -E "UTF-8$" | wc -l
     997
$ ls EUC-JP/*.dat | xargs nkf -g | grep -E "EUC-JP$" | wc -l
     997
$ ls Shift_JIS/*.dat | xargs nkf -g | grep -E "Shift_JIS$" | wc -l
     997


正解率99.7%でした。
テストデータの中には5文字くらいの極端に短い文も含まれているので、さすがにこのくらいが限界だと思います。

おわりに


けして高度な手法を使っているわけではないものの、それなりに満足のいく精度が出ました。
テストデータは平均40文字くらいとそう長くない文章だったのでどうだろうと思っていたのですが、エンコーディングごとのパターンがはっきりしているため良く分類できているのでしょう。


元データは人手によって一度整理されているものではあるけれども、現実世界のデータを扱うにはやはり前処理でいろいろとやらないといけないことが出てきますね。なかなか面倒


今回は単純にバイト値の出現頻度だけを使いました(これ、bag of featuresと呼ぶのかな??)が、エンコーディングについての一般的知識から、バイトの順序に意味があるはずなので、隣り合う値の組(byte 2-gram)を考慮に入れるようにすると精度上がるかもしれません。
ただしそれをやるなら、たぶん計算量がすごく大きくなるのでなにか工夫しないといけないと思いますが。

宣伝


Competitive Programming Advent CalendarでKaggleの紹介を書きました。こちらもよろしく
http://topcoder.g.hatena.ne.jp/tomerun/20121221/1356017174