みかん箱

[388] [387] [386] [385] [384] [383] [382] [381] [380] [379] [378]

category:
DATE : 2024/04/25 (Thu)

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

category: 未分類
DATE : 2010/11/24 (Wed)

「Google日本語入力Tech Talk 2010」まとめ

2010年10月23日に、六本木ヒルズにあるGoogle日本オフィスで開催された「Google日本語入力Tech Talk 2010」に行ってきました。Google Developer Day 2010の基調講演で本Tech Talkの存在を知り、興味がわいたことと、ちょうど東京出張の間に開催されることもあって応募、参加しました。以下に、その際に自分がとったメモや、本Tech Talkに参加された方のレポート、その他参考文献から文章にまとめました。

文章をまとめる際に私がとった方針は次の通りです。まず、私自身はMozcの開発に興味があるというよりも、Mozcの仕組みや開発手法に興味がありました。そのため、前述の部分を中心にまとめ、Mozcを改良する部分についての記述は薄くなっています。またMozcの仕組みをまとめるに当たって、講演では触れられていなかった部分では参考文献から推測を行いました。具体的には、サンドボックスや仮名漢字変換の際に用いられるコストの計算には、参考文献からの私の推測が含まれています。次に、できるだけ内容をまとめたかったため、質疑応答は講演と区別せずに文章に組み込みました。表記については、「Mozc」と明言されなかった、もしくは明言されたか否か記憶があやふやな部分に関しては「Google日本語入力」としています。数式については、上付き文字や下付き文字についてTeXの表記法を採用しています。

Google日本語入力ができるまで（小松弘幸氏）

Google日本語入力は、予測入力IMEであるPRIMEを開発した小松弘幸氏と形態素解析エンジンMeCabの工藤拓氏との20%プロジェクトからスタートした。Anthy, sskimeなどのIME開発経験者が社内にいたため、まずは彼らと半年ほど、週に数回集まって議論を行った。特に、開発したIMEで成功した部分、失敗した部分を出し合い、これから開発するIMEのコンセプトを固める足場とした。Google日本語入力のマルチプラットフォームを意識した設計は、この時の議論によるものである。しかし議論を重ね続けたものの、動作するコードが書かれる気配はなかった。そこで実装する時間を週に一度設けて、libanthy互換のライブラリとして試作を行った。社内での試用の結果、20%ルールのプロジェクトから本プロジェクトへと昇格した。

社内での試用では、既存のIMEとの振る舞いの違いについて特に意見が出た。既存のIMEにある機能がないことや、細かい振る舞いが既存のIMEと異なるといった意見が多かった。

そこから、既存のIMEから移行する労力を最小にすることが重要だとわかった。IMEは特に手に馴染んだツールである。ほんのわずかな振る舞いの違い、機能の足りなさがユーザの不満を募らせるのだ。

リリース直前には、ユニットテスト、ストレステストを含めとにかくテストを繰り返した。テストコードがメインのコードの2倍、3倍となるモジュールも珍しくなかった。UI部分は、できるだけテストコードに落とし込めるように設計を行った。それでもできない部分は手作業でテストした。

Google日本語入力は、次のようなプロセスを経てリリースしている。まず、毎日更新される成果物を社内で試用する。継続的インテグレーションとして自動的にユニットテストやストレステストを走らせる。もしビルドや自動テストに失敗すると、最後にコミットした人とそのコミットをレビューした人とにメールが飛ぶ。そして常に成果物ができるように素早く修正する。Web上に公開されている「開発版」は、数週間おきに更新している。アップデートテストなど最小限のテストを行い、クラッシュレポートや、入力した文字数などの利用統計情報を利用する。入力した文字列は全く送信していない。これらの結果を反映して「ベータ版」を数ヶ月おきに更新している。リリースから外される機能もある。クラッシュレポートが多い上にIssue listからなかなか消えることがないモジュールや、修正が困難であると見なされたモジュールなどである。

Mozcは、Google日本語入力をオープンソース化したものである。社内の開発者も、Google日本語入力のことをMozcと呼ぶことがある。辞書など、Google日本語入力と違いのある部分もあるが、MozcはIMEの基本機能を網羅している。研究などにもぜひ活用して欲しい。

Google日本語入力の設計概要（工藤拓氏）

Google日本語入力は、使う人にIMEの存在を意識させず作業に集中しやすい「空気のようなIME」として以下の面を重視して設計している。

マルチプラットフォーム
スピード
セキュリティ
安定性

まず初めに、日本のIMEはとても複雑であることを理解する必要がある。20年以上の歴史があり、その間さまざまな機能が積み重ねられてきた。おそらく、すべての機能を使いこなしている人はいないだろう。

そのように複雑なIMEであるが、IMEはDLLとして実装を行うため、そのDLLはすべてのアプリケーションのプロセスに読み込まれる。従来のIMEでは、そのDLLにIMEの機能すべてを実装している。つまり、すべてのアプリケーションに読み込まれたIMEのおのおののインスタンスが、システム辞書ひとつを共有する構造となる。その結果、以下の弱点が生まれる。

クラッシュに弱い: アプリケーションがクラッシュすると、IMEも巻き込まれてクラッシュする。逆にIMEがクラッシュすると、アプリケーションも巻き込んでクラッシュする。アプリケーション上で保存していないユーザの情報が失われる可能性や、IMEのシステム辞書が壊れる可能性がある。つまりIMEは決してクラッシュしてはならない。しかしクラッシュしないプログラムを書くのは不可能である。
セキュリティが弱い: すべてのアプリケーションのプロセスに読み込まれるということは、特権レベルで動作する、例えばログイン画面などのアプリケーションにもIMEが読み込まれることを指す。すると、IMEにセキュリティホールがあると、悪意のあるユーザが特権レベルでなんでも行えてしまう。つまりIMEにはセキュリティホールがあってはならない。セキュリティホールが全くないプログラムも、書くことは困難である。仮にリリース時にはなかったとしても、それは見つからなかっただけで、後々見つかる可能性もある。

これらの弱点を克服するため、Google日本語入力では役割に応じて処理を複数のプロセスに分割した。

まずアプリケーションのプロセスに読み込まれるDLLに実装する機能は小さくし、クラッシュしにくくした。Google日本語入力では、アプリケーションのプロセスに読み込まれるDLL（Client）、変換を行うプロセス（Converter）、変換結果や変換候補などを描画するプロセス（Renderer）にプロセスを分離している。プロセスを分離することによって、ConverterやRendererがクラッシュしても、アプリケーションを巻き込んでしまうことはなくなった。つまり、クラッシュしない構造にしたと言うよりも、クラッシュしてもアプリケーションを巻き込んでしまうことのない構造としたのである。Clientは、Converterに発生したキーイベントを渡し、Converterから返ってくる、表示に必要な情報を受け取りRendererに渡すだけである。ローマ字から仮名への変換さえもConverterの役割である。Client自身は内部に状態を持たない。Statelessとすることで、クラッシュする可能性をできる限り減らした。

分離されたプロセス同士は、プロセス間通信（IPC）を用いて処理を行う。IPCとして、Windowsではnamed pipeを、MacOSではMach IPCを、LinuxではUnix Domain Socketを用いた。理由は、セキュリティのためである。例えばUnix Domain Socketを用いると、送信元のプロセスIDやユーザIDが分かり、送信元を確かめることができる。TCPソケットを用いればプラットフォームごとにわざわざIPC部分を実装し直す手間は省けるが、送信元が偽装されるセキュリティ上のリスクがある。

また分離したプロセスにサンドボックスを用いることで、仮にセキュリティホールがあったとしても、OSや他のアプリケーションに影響を与えないようにしている。サンドボックスについては講演中には触れられなかったが、Google Chromeと同じ仕組みであると仮定すると、分離したプロセスのおのおのに対してOS特有の機能を用いて最低限のアクセス権限を与えることでサンドボックスを実現しているのだろう。

CannaやWnnといった従来のIMEでも、クライアントとサーバとでプロセスが分離されているものがある。これらのIMEでは、ローマ字から仮名への変換はクライアントが担い、仮名漢字変換をサーバが担当する。そして変換結果をクライアントが描画する。しかし、クラッシュしやすいのはクライアント部分である。クライアント、サーバ方式では、これまでに述べたようなクラッシュのリスクは減らない。ちなみにGoogle日本語入力にも関わっている、Anthyを開発した田畑悠介氏は、講演後のLightning TalkでAnthyとGoogle日本語入力との設計を対比し、AnthyではできるだけOSへ依存しないように作られていることを示した。そのため、Anthyは数多くのプラットフォームへ移植できた実績がある。しかし、セキュリティ面ではGoogle日本語入力にはかなわないと語っていた。OSに依存しないように設計されているため、OSが持つセキュリティ機能を十分に利用できないためなのだろう。

Google日本語入力ではさらに、安定性とスピードを確保するため、システム辞書・言語モデル・設定ファイルはすべてバイナリ化して実行バイナリに組み込んでいる。テキストとして用意したそれらのファイルをコードジェネレータでビルド時にC++コードに変換する。こうすることで、システム辞書ファイルを外部化していた場合に発生しうる実行時のエラーを、ビルド時に発見することができる。システム辞書も壊れない。システム辞書が壊れていた場合はIMEの実行バイナリ自体が壊れるためだ。システム辞書についてのファイルI/Oもない。I/Oの部分はプラットフォームによってかなり差があり、実行バイナリに組み込むことで、プラットフォームによるI/O部分の違いを考慮しなくとも済む。同時に、I/Oがないため動作も高速化する。システム辞書のフォーマットの互換性を気にする必要もない。IMEを更新するとシステム辞書も入れ替わるためである。

Google日本語入力は、OSの再起動不要でアップデートが可能である。アプリケーションのプロセスにIMEのすべてが読み込まれる従来のIMEでアップデートを行った場合、アップデート完了後に起動したアプリケーションにのみアップデート後のIMEが読み込まれる。その時点ですでに起動済みのアプリケーションは、アップデート前のIMEを使い続ける。そして、古いIMEと新しいIMEとでシステム辞書などのリソースを共有することになる。もしも、アップデートの前後でシステム辞書などにフォーマットの違いが生じた場合は、複雑な処理が必要となる。しかし、Google日本語入力ではプロセスが分離されているため、ConverterやRendererのみのアップデートが可能である。アプリケーションに読み込まれたClientは、アップデート前に接続していたプロセスをkillしてアップデート後のプロセスに接続し直せばよい。システム辞書もバイナリに組み込まれているため、システム辞書の互換性の問題も発生しない。ユーザがキーの入力の途中でConverterがアップデートした場合でも問題ない。Clientは、セッションプレイバックという機能を備えているためである。これは、ユーザが入力したキーを蓄えておく仕組みで、Converterがクラッシュしたりアップデートによって新しいConverterに接続し直した場合に動作する。Clientと新しいConverterとがユーザの入力中に接続を確立すると、これまでにユーザの入力したキーをClientは新しいConverterに送り直す。

Google日本語入力の設計は以上である。しかし、IMEである以上、いかに設計を考慮していても仮名漢字変換がうまくできなければ意味がない。Google日本語入力は、どのように仮名漢字変換を行っているのだろうか。

Google日本語入力では、文節の区切りや単語の変換に最小コスト法を用いている。これは、文を文節で区切ったときに、単語間の連接コスト、つまり単語の繋がりの不自然さと単語ごとの単語生起コスト、つまりその単語の出現しにくくさとが全体で最小になるものを選ぶというものである。文全体でコストが最小になる文節の区切りは、ビダビアルゴリズムで探索を行って決める。

コストは、次のようにして求めている。

まず、xはユーザがキーボードから入力した読み、yはユーザが想定している仮名漢字交じりの日本語とする。すると、変換結果の日本語文y'は、「y' = argmax_y p(y|x)」と表せる。p(y|x)は、ユーザがキーボードから入力した読みがxであったときに、ユーザの想定する仮名漢字交じりの日本語がyである確率である。yについて、p(y|x)の一番高いものが、変換結果y'となる。「y' = argmax_y p(y|x)」をベイズの定理を用いて変形し、yについて最大化するという観点で順序関係が重要であるという点から分母を除くと、「y' = argmax_y p(y)p(x|y)」と書き直せる。p(y)は、仮名漢字交じりの日本語yが日本語らしい確率であり、p(x|y)は、仮名漢字交じりの日本語yをxという読みで読む確率である。

しかし、p(y)p(x|y)は文全体についての確率であり、文節を区切ったあとのコストを見る最小コスト法へ適用するには都合が悪い。そこで、p(y)p(x|y)を形態素単位で表現する。文献「確率的モデルによる仮名漢字変換」を参考に、mを形態素、hを文中の形態素の数とし、Google日本語入力で用いられている言語モデルが2-gramと仮定して「y' = argmax_y p(y)p(x|y)」を展開すると、「y' = argmax_m Π_{i=1}^{h+1} (i-1番目の品詞c_{i-1}に対して、i番目の品詞c_iが出現する確率） * (品詞c_iにおいて、形態素m_iが読みx_iで出現する確率)」となる。

ここで、前者の「(i-1番目の品詞c_{i-1}に対して、i番目の品詞c_iが出現する確率)」が最終的に連接コストとなり、後者の「(品詞c_iにおいて、形態素m_iが読みx_iで出現する確率)」が最終的に単語生起コストとなる。しかし、最小コスト法ではコストの小さい方を採用するため、確率が高いほどコストも高くなってしまうのは良くない。そこで、上記の確率の積に対して負の数を乗じておく。Google日本語入力では、この負の数は-500としている。また最小コスト法では、連接コストと単語生起コストは積ではなく和で計算する。そこで、上記の確率の積に対して対数をとる。対数をとるのは、対数内の積は対数同士の和で表現できるためである。このような処置を行うことで最小コスト法のモデルと「y' = argmax_y p(y|x)」とが一致することになる。結果、コストcは次の式で求まる。「c = Π_{i=1}^{h+1} -500 * (log(i-1番目の品詞c_{i-1}に対して、i番目の品詞c_iが出現する確率) + log(品詞c_iにおいて、形態素m_iが読みx_iで出現する確率))」。

Googleでは、コストを求めるために使用する「(i-1番目の品詞c_{i-1}に対して、i番目の品詞c_iが出現する確率)」や「(品詞c_iにおいて、形態素m_iが読みx_iで出現する確率)」をWeb上の文書から求めている。具体的には、Web上の文書からMeCabで形態素解析を行ったコーパスを作成し、上記の確率を求めている。しかし、「(品詞c_iにおいて、形態素m_iが読みx_iで出現する確率)」を求めるのは容易ではなかった。それは、熟語の読みを解析する一般的な方法がないためである。読みと文字とが1対1に対応している熟語（例えば、「熟語」は「じゅく」と「ご」と、読みと文字とが1対1に対応している）は、単漢字辞書があればそれなりに求めることができる。実際に、ipadicからEMアルゴリズムを用いて単漢字辞書を作成し、読みを推定した。しかし、読みと文字とが熟語では1対1に対応しない熟語（例えば「大人」は、どこの文字が「と」を含むのか分からない）や当て字（例えば「強敵」と書いて「とも」と読む）もある。そこで、単漢字辞書の他に、Google検索の「もしかして機能」などを総動員して読みを推定した。

このように収集した連接コストと単語生起コストから作成したシステム辞書は、Trie木で格納し、LOUDSアルゴリズムで圧縮している。Key-Value構造は使用していない。なぜなら、Key-Value構造では完全一致でしか検索を行えないためである。また次のような日本語変換特有の検索が必要となるためでもある。

Common Prefix Search（入力が長い、通常の変換に用いられる）
Predictive Search（入力が短い、予測変換に用いられる）

システム辞書は、語彙が多ければ多いほど良いと考えがちだ。しかし実際には、辞書の副作用として、語彙を多くすると一般的な変換結果よりも特殊な変換結果が優先されてしまい、一般的な文が変換できないということもある。例えば、「アイマス」と「会います」という2単語が辞書に含まれている場合、「明日彼と会います」が「明日彼とアイマス」に変換されてしまうことがある。つまり、語彙数が多ければよいと言うものではない。ユーザにとっては、辞書の語彙数よりも、一般的な文が変換が当たり前に変換できるかどうかが重要なのである。そのため一般的な文の変換が失敗すると、このIMEは使い物にならないとユーザに見なされてしまう。そこで、対立候補も考慮して単語のランク付けを行うようにしている。また、必ず変換できなければならない一般的な文の変換を自動回帰テストで行うようにしており、そのテストと機械的な評価とを用いることで変換精度を評価するようにしている。システム辞書のipadicレベルの単語に対しては、人手でチューニングすることもある。しかし単語のランキングについては人手では調整せず、すべて自動的に求めている。

なお、ユーザ辞書はヒープ上に置いている。ユーザがユーザ辞書に書き込むと、Protocol Buffersを使ってテキストファイルに書き出し、その後Converterがそのファイルを読み込むようになっている。

Mozcソースコードレビュー

Mozcのソースコードは、「mozc - Project Hosting on Google Code」で公開している。C++コンパイラがありSTLが利用可能であること、かつPOSIXをサポートする環境であれば動作するはずである。しかしビッグエンディアンは現在のところサポート外である。

ソースコードの文字エンコーディングにはUTF-8を用いている。コンパイラがUTF-8に対応していない場合もあるため、UTF-8のコードを16進エスケープシーケンスにして文字列リテラルを表現している。例えば「か」はUTF-8でE3 81 8Bなので、「\xE3\x81\x8B」と文字列リテラルに記述する。その文字列リテラルの上部に、コメントとして元の文字列を記入している。

Mozcのソースコードには、メインコードの他にテストコードも含まれている。具体的には、ユニットテストとストレステストである。例えばConverterのストレステストでは、起動したプロセスに対してキーイベントを絶え間なく送りつけるような処理を行いストレステストを行う。

ビルドシステム（向井淳氏）

ビルドツールには、GYPを使用している。GYPは、元々Google Chrome用に作られたビルドツールである。

以前はSConsを使用していた。しかし以下の問題があった。

SConsはPythonでビルドスクリプトを書くため、なんでもできる。しかしそれ故にビルドスクリプトを保守に手間がかかる場合がある。
マルチプラットフォームのサポートが弱い。アプリケーションやIMEのビルドには、そのOSやIDE付属のコマンドが必要なことがある。SConsでもできなくはないが、ビルドスクリプトが複雑になり保守が面倒になる。

GYPでは、ビルドツールでありながらビルド自体は行わない。その代わり、ビルドファイルを生成する。例えば、Windowsではvcbuildを、Linuxではmakeを、Mac OSではXcode用のビルドファイルを生成する。Xcodeではdistccを使った分散ビルドができるため、GYPは分散ビルドを行うビルドファイルを生成する。結果、GYPを使うと手でビルドファイルを作成するよりもビルドが高速化することもある。

GYPには、それ自身を起動するgypコマンドが存在する。しかし、コマンドがインストールされている場所がプラットフォームによって異なったりするため、Mozcではラッパースクリプトであるbuild_mozc.pyを用意している。

システム辞書はMozcのバイナリの中に統合されている。しかし、ソースツリー内にはテキストファイルとして存在しており、ビルド時にPythonスクリプトを使用してC++コードに変換している。

Mozcでは以下のようにビルドを2段階に分けて行う。

システム辞書を生成するツールなどのMozcをビルドするのに必要なツール類のビルド。
Mozc自身のビルド

すべてを一気にビルドすることもでき、2番目のみをビルドすることもできる。ビルドを2段階に分けることで、最終的な成果物に関係のない変更をシステム辞書を生成するツールなどに行った場合でも、Mozc自身のビルドのみを行うことができビルド時間を短縮できる。

Client（小松弘幸氏）

Clientは、キーイベントの受け取りや変換結果の表示を行う。つまり、OSに依存したInput Method Frameworkとやりとりする。ローマ字から仮名への変換を含めて、変換に関わる処理はすべてConverterに任せる。

Protocol Buffersを用いてシリアライズしたデータをConverterとやりとりする。Converterがアップデートすると、Clientの想定よりも新しいConverterとデータのやりとりをおこなうことになる。しかし、後方互換性はProtocol Buffersが保ってくれる。

Clientは、セッション単位でConverterやRendererとやりとりする。セッションは、入力ボックス1つにつき1つ作られる。セッションの作成方法は次の通りである。まず、ClientがCREATE_SESSIONメッセージをConverterに送る。するとConverterはSession IDを生成して返す。以降の処理では、セッションの識別に生成されたSession IDを用いる。Session IDはConverterが生成するためセッションの同一性はConverterが保証する。

Converterからの応答には、表示に必要な情報をすべて含んでいる。これは、入力中であることを示す、画面上では下線として現れる部分や、ある部分が変換済みか否かを表す情報をも含む。Clientはその情報をRendererに渡し、Rendererがそれに従って画面に表示する。

Converter（工藤拓氏）

変換結果は、key-value形式で表現している。keyが読みで、valueが表記を表す。

Converter内では、以下のデータ構造で文を表現する。

Segmentsオブジェクト : 文節の集合
Segmentオブジェクト : 文節ひとつ
Segment.Candiateオブジェクト : 変換候補
metadata : メタデータ

SegmentsインスタンスひとつはSegmentインスタンスを複数含み、SegmentインスタンスひとつはSegment.Candiateインスタンス複数とmetadataを含む。

Converterは、ConverterInterfaceを実装している各Converterオブジェクトの結果から変換結果を作る。ConverterInterfaceは、Segmentsインスタンスに対する操作を行う。ConverterInterfaceを実装しているクラスは以下のとおりである。

ImmutableConverter : 仮名漢字変換を行う。常に同じ変換結果を返すConverter。
Rewriter : 後処理を行うConverterの総称。ヒューリスティックに変換候補の書き換えや追加を行うConverter。
Predictor : 予測変換を行うConverter。

ImmutableConverterの結果は、品詞IDとコストとですべてが決まる。品詞は、ipadicに定義されているものを拡張して用いている。品詞から単語が生成される確率（生起確率）とひとつ前の単語の品詞と単語の所属する品詞同士が繋がる確率（連接確率）を各単語ごとに掛け合わせて、その単語の出現確率とする。コストは、-500 * log(出現確率)である。単語の生起確率は品詞ごとに求まるため、品詞間でコストを比較することはできない。つまり、名詞のある単語コスト500と助詞のある単語コスト500は同じ生起確率を表さない。また、各単語は、左品詞IDと右品詞IDを持つ。複合語の場合、左にある単語から見る場合と右にある単語から見る場合とで品詞が変わる場合があるためである。例えば、「山田太郎」という複合語は、その複合語の左にある単語から見れば「山田」の名字が見えるが、右にある単語から見れば「太郎」の名前が見える。

システム辞書への単語の追加は推奨できない。それは、コストは自動生成しており、品詞IDとコストで結果が決まるためである。どうしても追加したい場合は、その単語が含まれている十分な量の文書を集め、システム辞書内にある単語の出現頻度と追加したい単語の出現頻度との比をとって、それを基に追加したい単語のコストを求める方法を推奨する。

またシステム辞書へサードパーティ製の辞書を追加する場合は、辞書のライセンスに注意する必要がある。システム辞書はバイナリ化されて実行バイナリに組み込まれるため、例えばGPLの辞書がシステム辞書に組み込まれたMozcはGPLとして配布しなければならない。

文節区切りルールはsegmenter.defに定義してある。品詞テーブルであるid.defと合わせて、ビルド時にif-thenルールを生成している。初めはC++コードに変換していたが、CPU使用率が高い部分であったため、すべて展開してビット配列にまとめて圧縮した。結果、ルックアップだけで済むようになり、高速化を実現できた。

Rewriter（向井淳氏）

Rewriterは、ImmutableConverterの後処理として特殊な変換や履歴の学習などを行う。例えば、電卓機能やおみくじ機能はRewriterで実装されている。

顔文字変換もRewriterで実装している。この顔文字辞書は人手で作成している。工藤氏によると、経験上、1000件までは人手でも辞書を保守できるそうである。

RewriterInterfaceを実装して、rewriter.ccやビルドスクリプトにその実装を行ったクラスを追加するとRewriterを追加できる。

Rewriterは変換キーが押されるたびに呼び出されるため、処理を行うべきかどうかを素早くチェックしなければならない。

Storage（花岡俊行氏）

前述の通り、システム辞書はビルド時にバイナリの中に統合している。それに対して、ユーザ辞書はProtocol Buffersでシリアライズしたファイルである。

システム辞書に含まれている単語の中には、予測変換には出したくない候補がある。そこで、その単語をビルド前にファイルへ列挙しておき、そこに含まれているか否かを予測変換の実行時に調べている。この処理はBloom filterで実装している。Bloom filterには、本当は含まれていないにもかかわらず含まれていると判断してしまう擬陽性があるが、予測変換なので問題ないとして採用している。

LRU Storageは、変換候補のユーザの選択履歴を保持する。