« October 2007 | Main | December 2007 »

2007.11.21

マルコフ情報源上で次の文字を予測する

文字列(単語列)を解析する際、i番目の文字はその直前(N-1)文字のみ依存するというマルコフ情報源を仮定することはいろいろな場面で現れます。

例えば音声認識とか機械翻訳では、次の単語を直前(N-1)単語を使って予測するというN-gramモデルが古くから今でも使われてますし、データ圧縮でもこれと全く同じように履歴を使って次の文字を予測し、その予測確率を用いて符号化するPPMモデルがあります。

ここで問題になるのは、何文字前まで見れば次の文字を予測できるかということが一般のデータだと分からないということです。例えば4文字前まで見た場合より5文字前まで見たほうが次の文字が確実に予想できそうですが、4文字前までは過去のデータで何回もでているのに5文字になると途端に出現回数が少なくなってサンプル数が少なくなってしまい予測精度が低下してしまう問題があります。

そのため大抵は1,2,3..,N文字前の文字を使ってそれぞれで予測した結果の線形結合を最終の予測として使ったり、もしくはk文字前まで見れば一番確信度が高いというようなkを別の方法で求めてk文字前までの結果を使って予測します。

で、最近でも様々な方法が提案されてきましたのでちょっと紹介

言語モデルでは最近mochihashiさんがSuffix Tree上に階層型Pitman-Yor Processを載せる方法("The Infinite Markov Model" [pdf])を提案していて、何文字(単語)前まで見て次の文字を予測するとよさそうなのかというのを求めてます。すごい。

データ圧縮の分野だとppmII("PPM: one step to practicality"[pdf])ので使われている方法が高精度です。どの深さまで見るかというのは、”見る履歴を一文字短くする”命令を表すescape文字の出力確率でコントロールできます。このエスケープ確率を様々なコンテキスト情報で条件付けて推定します。この推定には過去の情報を利用して最尤推定っぽいことをしています(SSEとよばれる部分)。コンテキスト情報は最頻の文字の頻度情報から、周期(英語だと単語の区切れ目で過去のことを忘れてよい確率が高くなる)などなどなんでも使ってます。例えば表データとかは一定文字数毎に全く違う分布に切り替わることがおこるのですが、そういった傾向もとらえることができます。

データ圧縮ではBWTという手法もあります。BWTでは履歴情報を直接扱わずに各出現文字を接尾辞をキーとして使ってソートします。この変換後の文字列は同じ文字が連続しやすく圧縮しやすくなっており、これを単純な符号法でencodeしてもかなり圧縮できることが知られており、任意のk文字前まで見て次の文字を予測して符号化した場合の結果にかなり近づくことが知られています("A simpler analysis of Burrows-Wheeler based compression"[ps] "Most Burrows-Wheeler based compressors are not optimal"[ps])。
bwtでの符号は昔はMTF + RunLengthが使われていたのですが、最近ではDistance Coding(A Simpler.. の中に説明あり)と呼ばれる手法が理論的にも実用的にも高精度だというのが知られてます。
しかし、Most Burrows-Wheer...で述べられているように本当にマルコフ情報源から生成されたデータでBWTを試すとLZ法とかと比べても性能が悪くなってしまう現象がおきます。自然言語はマルコフ情報源で仮定するのは大胆すぎるとはよくいわれていますが、BWTが自然言語上では実験的にはなぜ他の手法よりうまくいくのかを説明するあたりに、よりよい自然言語のモデル化があるのかもしれません(全くないかも)

#となるとbwt + distance codeから演繹される確率分布を使って次の文字を高精度に予測することができるかも、という怪しい話を今ためしにやっているところです。符号化の順番が前から後ろじゃないのでちょっと難しいですが・・

機械学習の分野では、確率を出さなくても、当てればいいというマージン法+Perceptronでやっている手法もあります。下記で紹介されてます(論文はないようで本でしか情報がないです。どこかに落ちてる?)
"Discriminative Learning of Prediction Suffix Trees with the Perceptron Algorithm", Ofer Dekel, et. al., Predicting Structured Data
各履歴がfeatureになっていてそれぞれに重みがついていて(重みは深くなると指数関数的に小さくなるようになている)、あたらなかった場合は通常のパーセプトロンのように現在の重みに足しこみます。これをそのままやった場合は、履歴の数は非常に多くなってしまい使うfeatureの数が膨大なものになります。しかし、ちょっと工夫することで木の深さを「間違えた回数」に制限しても性能は保証できることが示されてます。ただ、実験結果がないので実際試してみようかなぁ・・

| | Comments (56) | TrackBack (0)

2007.11.05

L1正則化付LLMの双対化

タイトルの内容で現在開催中のIBIS 2007で発表してきました。論文[pdf] 発表パワポ [ppt]

タイトルからしてよくわからない人もいると思うので”タイトル”を簡単に説明します。

まず LLM (Log Linear Model)というのは指数型分布族と一般に呼ばれるのですが、p(x; w) = exp(wx - Z'(w)) x∈R^m, w ∈R^mの形をしている確率分布です。自然言語処理などでは最大エントロピーモデルとかCRFとかいろいろ名前を変えて使われているモデルです。いろいろな確率分布(例えば正規分布)がこの形に属します.Log-linearというのはこの確率分布の対数をとると、log p(x) = wx - Z'(w) と線形の式がでてくるところからそう呼ばれています。

次は、L1正則化です。やりたいことは訓練データを利用して確率分布を決定するパラメータを推定することです.指数型分布族の場合はwを求めることになるのですが、オーバーフィットの問題が常につきまといます。例えば高次の多項式で二次元中のn点を通る関数を求めようとすると,がたがた振動するようなことがおきますが、今回推定する場合もwを推定するのに十分データがないので同様の問題が発生します。あまりフィットしないで滑らかで単純なモデルを選ぶように指定する部分が正則化になります。正則化の中でもL1正則化は最近注目されています。というのは、この正則化を適用すると多くの重みが0に潰されるといういい性質があるからです。自然言語処理タスクの場合はmが数百万にもなりwが数百万次元のベクトルとなるのですが、L1正則化を使うと、wの成分の殆どが0になってくれて、結果が分かりやすい、速い、省メモリといいところだらけです。

で、最後が双対化。今回の確率分布の推定問題は最適化問題を解くことによって得られます。最適化問題とはf(x)という関数があってこの関数の値を最大(最小)にするxを探す問題です。一般に最適化問題は難しい問題なのですが、今回解くのは、その中でも解きやすい凸最適化問題になっています。双対化は、この問題を直接解かずに、それと同じ解にたどり着くような解きやすい問題に変換するものです。今回も最終的に解く問題はパーセプトロンのような非常な単純な式になりました。数値最適化とかの手法とかは必要いらずで実装も簡単です。

ずいぶん適当にかいてみましたが、これで少しはタイトルが分かっていただけましたでしょうか。ppt, pdfをみていただける人が増えたら幸いです。いたらすごい。この論文で作った実装も将来的には公開する予定です。

ちょこちょこ修正してすいません。
 

| | Comments (7) | TrackBack (0)

tx bepの内部技術の発表

txとbepの内部で使われている技術についてグーグル東京で話してきました。
発表資料 [ppt/pdf]

txはloudsと呼ばれる木構造の簡潔表現を利用していて、bepは最小完全ハッシュ関数を利用しています。
その他こまごまとした実装も書いてあります(例えば、trieの枝についている文字情報はどう保存されているかとか)

いろいろ貴重な意見もいただいたのでそれを反映させていこうとおもいます。

| | Comments (31) | TrackBack (0)

« October 2007 | Main | December 2007 »