2012-12-22
■[機械学習]文字コードの自動判別を機械学習で 
これはMachine Learning Advent Calendar2012の22日目の記事です。
まえがき
「アルゴリズム使って実世界の問題を解決できるの面白いナー」とPRML読んだりしているのですが、
研究や仕事で機械学習を使っているわけでもなく、自分の中では純粋に趣味・老後の楽しみ的な位置づけになっています。
しかしせっかく勉強しているのだから何かに使おうと、「有名データを利用するのも面白くないし、良いネタはないか」
と探していたら、以前こんなことを言っていたのを思い出しました。
文字コードの自動判別を機械学習使ってやる、って誰かがやってそうだけど検索しても出てこない
https://twitter.com/tomerun/status/9729721761
というわけで試しにやってみます。
この記事の中で使ったコードはここに置いています。 https://github.com/tomerun/MachineLearning
コメントなどあまり付いてないけどご勘弁を
※エンコーディングなんて規則は全部分かってるのだから、精度に関しては機械学習とか持ち出さずともヒューリスティックに判定する方が良いに決まってます。
この記事は、機械学習の手法を使ってみた例でしかないことに注意。
データの準備
データには、「日本語バランス文」の上位1000個を使います。
ダウンロードしてきたデータについて、次の前処理をやります。
- 形態素がスペースで区切られているので、スペースを全て除去
- 元はWikipediaから取られた文なので、脚注を表す「＾ 」が先頭に付いているものがある。これを取り除く
- 2箇所、nbspが紛れ込んでいるので除去
- 1箇所、Shift_JISやEUC-JPにマッピングできない文字であるホリゾンタルバー（U+2015）があるので半角ハイフンに置き換え
- 「深圳」の「圳」がShift_JISにマッピングできないのでカタカナに置き換え
- 英数や記号が全て全角になっているので、文ごとに1/2の確率で半角に変換
続いて、1000個の文をそれぞれ、UTF-8、UTF-16LE、Shift_JIS、EUC-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に推定させてみました。
どうもnkfでUTF-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の紹介を書きました。こちらもよろしく
2012-07-17
■[contest]ICFPC 2012 
http://icfpcontest2012.wordpress.com/
年に1度のICFP Contestでした。
O(nwn)というチームで参加していました。自分以外のメンバー：@uwitenpen,@kou_miyam,@hasi_t,@nico_shindannin,@WtbH
ICFPC4回目の参加で初めてチームを作ってみた。
1日目
問題読んで、ああー普通のMarathon系かーと思う。仕様変更だるそう…
そのうちuwiさんがシミュレータを実装して、hasiさんがそれをラップしたブラウザで動くGUIを作ってくれたので、サンプルのマップを遊んでみる
→むずい。これ仕様追加が無くてもこれだけで十分72時間のコンテストになりそう
アルゴリズムの案をいくつか考えてみるけどかなり無理ゲーな予感が
詰将棋的に、特定の経路で動いて岩をよけたりしておかないとのちのち死亡確定、みたいなマップが解けるAIを作れる気がしない
寝ようとしたら追加ルールでFloodが来て、うげーこれは完全に殺しに来てる…どうすんだこれ…と絶望感に浸る
とりあえずMarathonMatchで用意されてるみたいなCUIで実行するテスターを作ってこの日は終了
2日目
テストケースになるマップを自分で作らないとなあ、と思うもどのくらいまで想定して良いかがわからないので難しい
とりあえずランダムなマップのジェネレータだけは作った、けど生成されたマップを見ても全然面白くない…
誰かがパズルマップを作っていたのでそれを手で解くのに熱中し始める。このときが一番面白かったかもしれない
診断人さんによってuwiさんのJava製シミュレータをC++に移植されていたので、それをベースにして、ランダムウォークしつつテキトーな評価関数を元によさげな方向を選んで歩き回るのを書いてみる
ひとまずは取れるλからどんどん取っていけばいいんじゃね、ということで、評価関数の要素は取ったλの数と近くにλがあるかどうか（到達可能かどうかも考慮）、くらい
contest1.mapやcontest2.mapくらいはゴールできていた。けど、局所的に目先のλを取りに行くだけのAIなのでちょっとややこしい盤面になるとてんで話にならない
あとはこの日はこれのバグを取りつつ終了。何かトランポリンとか来てたけど無視って寝る
3日目
起きたらbeardが仕様追加で来てた。
草と岩がぶつかったときの仕様がよくわからなくて多少紛糾する→バリデータ様が正義
この辺で、バリデータの動作が最後にAbort付けなくてもAbort扱いになっていることに気づく。Aとはなんだったのか
もう一個仕様追加来る予定なのであまり気は進まなかったが新仕様を黙々と反映させる
実装し終わった頃に最後の仕様追加horockが来た
もっと派手なのが来ると思ってたけど、このくらいの変更では物足りない、と思うようになってしまっていた
これも実装
あとは評価関数に新仕様の要素を反映させたり微妙な高速化をやったり、
探索しきれないようなでかい盤面対策に、ランダムウォークの結果を1ステップずつ進めていたのを複数ステップ一気に進めるようにしたり
4日目
提出に向けて、SIGINTをトラップして終了できるようにしたり、細かいバグを直したりちまちま高速化したり。
来た方向に即戻る移動は意味が無いことが多いので起きづらいようにしたらまあまあスコアが上がった（ゴールできない盤面がゴールできるようになるわけではないけど）
今の評価関数ではgreedyに近いλから取りに行ってしまうのでどうしてもcontest6.mapがクリアできない。
改善できないかと、状態を複数保存するbeam search的な探索も書いてみたけど遅すぎてどうにもならなかった
最後にhasiさんに提出してもらおうとしたら、Linux上でコンパイルしたらちゃんと動かず"A"しか返さないという問題が発生していた
結局解決できず、審判環境では動くことを願ってそのまま提出することになった。各自の手元では動いてるし環境依存するようなコードはたぶん入れてないと思うのに、謎
最終的にはサンプルマップのスコア合計はbestの80%くらいだったかな
AtCoderの非公式ジャッジに（勝手に）提出してみると、京都チームには負けてるっぽい
反省
オンラインでのチーム戦は難しいなー
ICPC的なコンテストだったら各自別々の問題を解く、でよいけど、こういう巨大な一つの問題に取り組む、というときは作業をうまく分割して分担しないといけない
そしてこれは分割が難しめなタイプの問題だった
次回参加するときはチームで現地に集まる、というのをやってみたいですね
最初の方絶望に浸っている時間が長くて、仕様追加が予告されているというのもあって最初の実装ができるまでに時間が掛かってしまった。
とりあえずスコアが取れる実装ができたときにはもうlightning終わっていた
やっぱりスコアが一つも出てない状態というのはモチベーション上がりにくい。1つでもベンチマークになるスコアが出るとそれを超えようという意識が生まれる
マップのupadteは、毎ターンで盤面全コピなとても遅いのしか作れなかった。変化する可能性のある岩やWだけトラッキングする、という方針でやったらどうにかin-placeに高速にできるのかな…
あと探索のヒューリスティクスはもっと入れて良かった。岩の隣を開けるとか
あとから仕様変更が来るのは自分としては結構つらかった。ルールが決まってる問題を集中して考えたいです
2012-06-18
■[algorithm]選択肢式のテストで同じ答えが連続する確率 
選択肢式のテストで同じ回答が何個も続いたとき、「これは怪しい、自分間違ってるんじゃないか」と思ってしまう、というのを経験したことがある人は多いんじゃないでしょうか。
同じ答えが続くことがどのくらいの確率で起こるかはちょっとプログラムを書いたら簡単に計算できるので、やってみました。
4択で100問のテストについての結果です。
同じ答えが連続する長さの最大値がちょうどiである確率 1: 0.0000000000 2: 0.0051914968 3: 0.2991464221 4: 0.4469730949 5: 0.1809903269 6: 0.0505544773 7: 0.0128794318 8: 0.0032085392 9: 0.0007949317 10: 0.0001966696 11: 0.0000486359 12: 0.0000120251 13: 0.0000029728 14: 0.0000007348 15: 0.0000001816 16: 0.0000000449 17: 0.0000000111 18: 0.0000000027 19: 0.0000000007 20: 0.0000000002 同じ答えが連続する長さの最大値がi以上である確率 1: 1.0000000000 2: 1.0000000000 3: 0.9948085032 4: 0.6956620811 5: 0.2486889862 6: 0.0676986593 7: 0.0171441821 8: 0.0042647503 9: 0.0010562111 10: 0.0002612794 11: 0.0000646098 12: 0.0000159739 13: 0.0000039488 14: 0.0000009760 15: 0.0000002412 16: 0.0000000596 17: 0.0000000147 18: 0.0000000036 19: 0.0000000009 20: 0.0000000002
これを見ると、いちばん可能性が高いのが4連続で、5連続以上が起こる確率が1/4。
6連続以上でも7%弱だからそこまで稀なことではない、となりました。
コードは次の通り（Java）。
public class Main { public static void main(String[] args) throws Exception { final int N = 100; final int selection = 4; double[][][] p = new double[N][N + 1][N + 1]; // p[i][j][k] = i番目の問題までで、現在j個同じ答えが連続してて、 // これまで同じ答えが連続した最大の長さがk となる確率 p[0][1][1] = 1; for (int i = 1; i < N; ++i) { for (int j = 1; j <= i; ++j) { for (int k = j; k <= i; ++k) { p[i][1][k] += p[i - 1][j][k] * (selection - 1) / selection; if (k == j) { p[i][j + 1][k + 1] += p[i - 1][j][k] / selection; } else { p[i][j + 1][k] += p[i - 1][j][k] / selection; } } } } double[] ans = new double[N + 1]; for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { ans[i] += p[N - 1][j][i]; } } System.out.println("同じ答えが連続する長さの最大値がちょうどiである確率"); for (int i = 1; i <= 20; ++i) { System.out.printf("%3d: %.10f\n", i, ans[i]); } System.out.println(); System.out.println("同じ答えが連続する長さの最大値がi以上である確率"); double sum = 0; for (int i = 1; i <= 20; ++i) { System.out.printf("%3d: %.10f\n", i, 1 - sum); sum += ans[i]; } } }
