「サイボウズ・アドベントカレンダー」の10日目です。2週間をクリアしました。残るはあと1週間。まだまだ続きます（これまでの記事一覧）。
サイボウズ・ラボの中谷です。 サイボウズ・アドベントカレンダー10日目の今日はみなさんが日頃お世話になっている「言語判定」をテーマにお話します。
「言語判定」とは、文章が何語で書かれているのかを推定することです。例えばこの文章は日本語ですね。 そんなのにお世話になった覚えはないって？ いえいえ、おそらくこれをお読みになっているほぼ全員が毎日「言語判定」の恩恵を受けていますよ。
例えば検索エンジン。"iPhone" を検索した時、単純に重要度順なら英語のページが上位を占めても不思議ないのに、ちゃんと日本語のページばかり表示されます。 スパムメールフィルタは使われている単語などを見てスパムかそうでないか分類するので、日本語のメールには日本語のフィルタが、英語のメールには英語のフィルタが必要です。 Web ページの翻訳も、ページの言語を指定しなくても正しく翻訳してくれます。 これらはみな、言語判定を使って web ページやメールの言語を推定してくれているおかげです。
サイボウズ・ラボでは言語判定を行う language-detection というライブラリを開発し、Apache ライセンスで公開しています。
- language-detection
- http://code.google.com/p/language-detection/
language-detection は 53 の言語を 99% 以上の精度で判定し、全文検索エンジンの Apache Solr にも組み込まれるなど、広く使っていただいています。 そんな言語判定をどういう仕組みで実現しているか、その種明かしが今日のお話です。
language-detection では最近ちょっと流行ってきている機械学習を使っています。 あー今ブラウザ閉じようとした人待って待って。ものすごく具体的に説明するのでご安心を。
まず簡単のために、英語とイタリア語の２つの言語に話を絞ります。 英語くらい見ればわかるって？ だから片方は英語がいいんじゃあないですか。スペイン語とイタリア語だと「ほら正解でしょ？」って言っても大半の人にはわかりませんからね(笑)。
機械学習にはポイントが幾つかありますが、最も大切なことは「お手本になるデータ」（訓練データ）が必要ということ。 そこで英語とイタリア語の両方とも手に入れやすいデータとして、著作権切れテキストを収集しているデータベース Project Gutenberg で公開されている「不思議の国のアリス」を使いましょう。 機械翻訳をするわけではないので同じ内容である必要はなく、同じくらいのサイズであればお好きなデータを使ってもらっても構いません。
- 英語版「不思議の国のアリス」
- http://www.gutenberg.org/ebooks/11
- イタリア語「不思議の国のアリス」
- http://www.gutenberg.org/ebooks/28371
なお、Project Gutenberg のテキストに必ずついている長いヘッダーとフッターは今回のお話には不要なので、手作業でそれらを取り除いたものを使いました。
ここで言語判定はちょっとおいといて、まずはこのお手本データの中で各文字が何回ずつ使われているのかを数えてみることにします。 まずは英語版「不思議の国のアリス」から。簡単のため、対象はアルファベットと空白の27文字とし、それぞれの回数と総数(=132738)で割った割合を計算するとこのようになりました。アルファベットの大文字は小文字にし、句読点や記号は無視しています。
| 文字 | 回数 | 割合 | 文字 | 回数 | 割合 | |
|---|---|---|---|---|---|---|
| " " | 25045 | 0.1887 | n | 7013 | 0.0528 | |
| a | 8791 | 0.0662 | o | 8145 | 0.0614 | |
| b | 1475 | 0.0111 | p | 1524 | 0.0115 | |
| c | 2398 | 0.0181 | q | 209 | 0.0016 | |
| d | 4930 | 0.0371 | r | 5437 | 0.0410 | |
| e | 13572 | 0.1022 | s | 6500 | 0.0490 | |
| f | 2000 | 0.0151 | t | 10687 | 0.0805 | |
| g | 2531 | 0.0191 | u | 3465 | 0.0261 | |
| h | 7374 | 0.0556 | v | 846 | 0.0064 | |
| i | 7511 | 0.0566 | w | 2676 | 0.0202 | |
| j | 146 | 0.0011 | x | 148 | 0.0011 | |
| k | 1158 | 0.0087 | y | 2262 | 0.0170 | |
| l | 4713 | 0.0355 | z | 78 | 0.0006 | |
| m | 2104 | 0.0159 |
この表を見ると、空白以外で登場回数が一番多いのは e、その次は t であることがわかります。これはアリスに限らず英語の一般的な傾向で、ポーの「黄金虫」やドイルの「踊る人形」などの小説では、こういった英語の文字分布の傾向が物語の鍵になっています。
一方、同じ事をイタリア語版でもやってみましょう。
| 文字 | 回数 | 割合 | 文字 | 回数 | 割合 | |
|---|---|---|---|---|---|---|
| " " | 23231 | 0.1713 | s | 6586 | 0.0486 | |
| a | 12671 | 0.0934 | t | 6385 | 0.0471 | |
| b | 1111 | 0.0082 | u | 3533 | 0.0260 | |
| c | 5880 | 0.0434 | v | 2366 | 0.0174 | |
| d | 3766 | 0.0278 | w | 1 | 0.0000 | |
| e | 13236 | 0.0976 | x | 12 | 0.0001 | |
| f | 1155 | 0.0085 | y | 2 | 0.0000 | |
| g | 2160 | 0.0159 | z | 739 | 0.0054 | |
| h | 1482 | 0.0109 | à | 196 | 0.0014 | |
| i | 10884 | 0.0802 | è | 452 | 0.0033 | |
| j | 33 | 0.0002 | é | 1 | 0.0000 | |
| k | 1 | 0.0000 | ê | 2 | 0.0000 | |
| l | 6897 | 0.0508 | ì | 239 | 0.0018 | |
| m | 2786 | 0.0205 | í | 3 | 0.0000 | |
| n | 7648 | 0.0564 | ï | 6 | 0.0000 | |
| o | 10252 | 0.0756 | ò | 801 | 0.0059 | |
| p | 3254 | 0.024 | ô | 1 | 0.0000 | |
| q | 651 | 0.0048 | ù | 142 | 0.0010 | |
| r | 7073 | 0.0521 |
アクセント記号の付いたアルファベットも使われているなど、英語とは結構違ってます。 まず j, k, w, x, y の登場回数が極端に少ないのが目につきます。実はイタリア語ではこれらの5文字は外来語にしか使いません。お手本データが英語からの翻訳なため、これでもイタリア語にしては多いくらい。 次に英語と比べて少ないのは h です。イタリア語では h は発音しない文字で、英語で have に相当する動詞と、あとは ch と gh という形でしか使われません。 逆にイタリア語のほうがよく使う文字は z, q, v というあたりでしょうか。z は特に差が大きいですが、これはどちらかというと英語が z をあまり使わない言語で、イタリア語の方が普通な感じだったりします。 英語で一番使われている文字は e で、次は t でした。一方イタリア語の一番は同じく e なのですが、その後 a, i, o と母音が続きます。イタリア語の単語は原則として母音で終わるので、母音の使用割合が自然と多くなります。
この文字分布表2つだけでも、こんな調子でみなさんご飯何杯でもおかわりできるでしょうが、それではいつまでたっても話が本題に入らないので、泣く泣く言語判定に戻りましょう。
言語判定とは、文章の言語を推定するものでした。 ここで「文章が英語で書かれている確率」と「イタリア語で書かれている確率」を求めて、その大きい方を答えるというアプローチを考えます。
実はこの時、上で掲げた文字分布表が使えます。 まず表にある各文字の割合を、「それぞれの言語でその文字が使われる確率」とみなします。確率は同時に起こることを掛け算しますから、言語を推定したい文章で実際に使われている文字の確率を全部掛け算すると、「英語でその文章が書かれた確率」と「イタリア語で書かれた確率」が求まります。 ここで確率のベイズの公式というものを使うと、この掛け算した確率の大きいほうが文章の書かれた言語である確率も大きい、ということが示せます(本当はちょっとした前提条件が必要ですが、そこは目をつむります)。 言語が３つ以上になっても同じく、掛け算した確率が一番大きい言語が答えになります。
ちょっとややこしかったですか？ まとめると「割合を掛け算して、一番大きいのが答え！」ということ。 本当にそんな簡単なことで言語判定ができるのか、実際にやってみましょう。
"thank you" の確率を今説明した方法で計算します。確率の記法にならって、求める確率を p(文章|言語) で表します。 英語版の文字数の合計は 132738、t の登場回数は 10687 回、だからその確率は 10687/132738、同様に h の確率は 7374/132738、……という調子で求めたものを全部掛け算すると、確率 p(thank you|英語) が求まります。
同様にイタリア語(伊語)についても求めましょう。
比べると英語の確率のほうが大きいので、答えはめでたく英語ということになりました。正解ですね！ イタリア語の文章でも試しましょう。イタリア語の「こんにちは」は "buon giorno" です。確率を計算すると、
こちらもちゃんとイタリア語と判定できました。イタリア語での確率が高い "o" が 3つも出てきているところが効いてますね。
大体７割から８割くらいはこれでうまくいきます。が、やっぱりうまくいかない例はどうしても出てきてしまいます。 "good morning" の確率も同様に求めてみると、
あらら、イタリア語の確率のほうが大きくなってしまいましたが、もちろん正解は英語です。 "buon giorno" と同じく "o" が3つ使われているので、どうしてもイタリア語の確率が高くなってしまうんでしょう。 困りましたね。どうしましょうか。
そもそも人間はどうして "good morning" が英語だとわかるのでしょう。 もちろん知ってる単語だからってのもあるでしょうが、仮に知らない単語でも「英語っぽい」「イタリア語っぽい」を見分けられる特徴はあります。 例えば、イタリア語の単語は母音で終わります(一部例外あり)。だから d や g で終わる単語はイタリア語っぽくありません。 またイタリア語はたしかに母音をよく使うのですが、"oo" のように同じ母音文字が2つ続く綴りは滅多にありません。
そこで、お手本データの中で「"o" の次に使われている文字」の分布をとってみましょう。 まずは英語から。
| 文字 | 回数 | 割合 | 文字 | 回数 | 割合 | |
|---|---|---|---|---|---|---|
| o" " | 1245 | 0.1529 | on | 1059 | 0.1300 | |
| oa | 29 | 0.0036 | oo | 452 | 0.0555 | |
| ob | 42 | 0.0052 | op | 103 | 0.0126 | |
| oc | 100 | 0.0123 | oq | 11 | 0.0014 | |
| od | 103 | 0.0126 | or | 674 | 0.0828 | |
| oe | 48 | 0.0059 | os | 134 | 0.0165 | |
| of | 620 | 0.0761 | ot | 429 | 0.0527 | |
| og | 41 | 0.0050 | ou | 1557 | 0.1912 | |
| oh | 52 | 0.0064 | ov | 87 | 0.0107 | |
| oi | 127 | 0.0156 | ow | 543 | 0.0667 | |
| ok | 208 | 0.0255 | ox | 11 | 0.0014 | |
| ol | 169 | 0.0207 | oy | 12 | 0.0015 | |
| om | 287 | 0.0352 | oz | 2 | 0.0002 |
次にイタリア語。
| 文字 | 回数 | 割合 | 文字 | 回数 | 割合 | |
|---|---|---|---|---|---|---|
| o" " | 3763 | 0.3671 | on | 1644 | 0.1604 | |
| oa | 65 | 0.0063 | oo | 14 | 0.0014 | |
| ob | 20 | 0.0020 | op | 199 | 0.0194 | |
| oc | 396 | 0.0386 | oq | 28 | 0.0027 | |
| od | 105 | 0.0102 | or | 906 | 0.0884 | |
| oe | 42 | 0.0041 | os | 746 | 0.0728 | |
| of | 50 | 0.0049 | ot | 243 | 0.0237 | |
| og | 207 | 0.0202 | ou | 16 | 0.0016 | |
| oh | 40 | 0.0039 | ov | 281 | 0.0274 | |
| oi | 223 | 0.0218 | oz | 35 | 0.0034 | |
| oj | 16 | 0.0016 | oè | 7 | 0.0007 | |
| ol | 765 | 0.0746 | où | 1 | 0.0001 | |
| om | 440 | 0.0429 |
特に o に注目すると、イタリア語ではもともと "o" 単独の使用割合は大きかったのに、「"o" の次」という条件が入ると英語の 1/40 まで小さくなっちゃうことがわかります。 そうです、これをさっきの確率の代わりに使えばうまくいきそうです。 具体的には、
p(good morning|言語)=(g の割合)×(g の次に o が来る割合)×(o の次に o が来る割合)×……×(n の次に g が来る割合)
として文章の確率を計算します。そうと決まれば早速やってみましょう。
逆転！ 今度はちゃんと英語の勝ちになりました。すばらしい。 実はここで試したそれぞれの手法には機械学習でちゃんと名前がついていて、最初の「1文字ずつの確率の掛け算」はユニグラム、後の「次の文字の確率の掛け算」はバイグラム（または1次のマルコフ連鎖）と呼ばれています。かっこいいですね。
ここではまだ2文字のつながり方しか見ていませんが、3文字やもっと長い文字のつながり方まで見ればさらに精度は上がります。 言語や諸条件によって多少は違うものの、１文字（ユニグラム）では上で言った通り７～８割の精度だったものが、２文字（バイグラム）では 90%、３文字（トライグラムと言います）だと 95% くらいまで向上します。実際、language-detection ではトライグラムが用いられています。 ただし！ ただ単純に長くするだけでいいわけではありません。その理由を確かめるために、例として「"go" の次に使われている文字の分布」を求めて、3文字のつながり方が実際にどのようになっているか確認してみましょう。 英語のお手本データから求めるとこのようになりました。
| 文字 | 回数 | 割合 |
|---|---|---|
| go" " | 52 | 0.2488 |
| goa | 3 | 0.0144 |
| goe | 9 | 0.0431 |
| gof | 2 | 0.0096 |
| goh | 4 | 0.0191 |
| goi | 27 | 0.1292 |
| gol | 9 | 0.0431 |
| gon | 17 | 0.0813 |
| goo | 29 | 0.1388 |
| gos | 1 | 0.0048 |
| got | 54 | 0.2584 |
| gou | 1 | 0.0048 |
| gov | 1 | 0.0048 |
文字の種類が激減しています。それぞれの登場回数もとても小さく、ほとんどが一桁回数ばかりになっていますね。 それもそのはず、アルファベット26種類を使った3文字の並べ方は単純計算で 26^3=17576 通り。実際にはこの中から英語ではありえない並べ方を除けば多少小さくなるにしても、ずいぶん大きな数です。場合の数が増えたのにデータの量がそのままなら、それぞれの回数は当然小さくなります。 つまり、つながりを長くするときはその分だけデータを増やさないといけません。 とはいえ、データを増やすにもどこかで限界があるので、データが十分でない場合にも良い性能を出すための工夫も行われています。が、それはこの記事ではもう扱いきれませんので、興味のある方は「言語モデル」や「スムージング」などのキーワードで探して勉強してみてくださいね。
次回は来週月曜日。「サイボウズ Office チームの分散開発」をお送りします。良い週末を。
【修正履歴】 2012年12月21日：用字の間違いを修正しました（「単独の仕様割合」を「単独の使用割合」に）
