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

文字列（単語列）を解析する際、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の数が膨大なものになります。しかし、ちょっと工夫することで木の深さを「間違えた回数」に制限しても性能は保証できることが示されてます。ただ、実験結果がないので実際試してみようかなぁ・・