データ圧縮への応用

ウィキペディア小見出し辞書

データ圧縮への応用

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/09 06:04 UTC 版)

「コンテキスト・ミキシング」の記事における「データ圧縮への応用」の解説

条件付き確率 P(X|A) と P(X|B) が与えられた時、 P(X|A, B) つまり A と B の両方が起きているという条件下で事象 X が起こる確率を推定したいとする。確率論 によれば、これら P(X|A) と P(X|B) は P(X|A, B)を推定するのに十分な情報とはいえない。実際に、それに対応する適当なケースを考えれば、結果 P(X|A, B) はどんな値でもとることができる。しかし直観的には、その結果は二つのある種の平均となることを期待できるだろう。 この問題はデータ圧縮で重要となっている。データ圧縮に応用して考えるとき、AとBは文脈（コンテキスト）を指し、事象 X は次のビットや符号をある値に圧縮できることを指す。また、P(X|A) と P(X|B) は、（それぞれ文脈 A、B を情報として用いる）ふたつの独立したモデルが算出する X が起こる確率の推定値を指す。コンテキストミキシングは扱おうとする問題は、P(X|A) と P(X|B) は X の現れる回数を数えることで正確な推定値を求めることができるが、P(X|A, B) を計算できるほど文脈 A ・ B が両方同時に現れる場面がなかったり、それらの文脈の組み合わせが莫大な量となるため記録するための十分な計算資源（時間やメモリ）がとれない場合であっても、推定値 P(X|A, B) をなんとか計算したいということである。 たとえば、テキストファイルを圧縮しようとする場合を考えよう。ここで、次の文字が改行であるかどうかを予測しようとしたとする。ここで、この予測しようとしている文字の手前の一文字はピリオドであり（これをコンテキスト A とする）、前回の改行は 72 文字前に現れた（コンテキスト B とする）ことがわかっているものとする。 ここで、これまでに現れたテキストで直近の 5 つのピリオドをみるとそのうち 1 つでその直後に改行が見られ (P(X|A) = 1/5 = 0.2) 、また、1行の中の72文字目という場所に注目すると10行中5行でその位置で改行されているとする(P(X|B) = 5/10 = 0.5)。これらの予測は、どのように組み合わせるべきだろうか。 ここで、線形ミキシングやロジスティックミキシングといった、コンテキストミキシングの一般的なアプローチを使われることになる。線形ミキシングは、実績により加重された二つの予想の平均をとる。この例では、P(X|B) は P(X|A) より重い重み付けが与えられる。なぜなら、P(X|B)はより多くの実績に基づいているからである。 古いバージョンの PAQ はこのアプローチをとっている。新しいバージョンではロジスティックミキシング（あるいはニューラルネットワーク）を使う。これは、まずはじめに確率の推定値 p をロジスティック領域 log (p/(1 − p)) に変換してから平均をとる。これにより、0 や 1 に近い推定値に対して、より大きな重み付けが与えられるようにすることができる。この例の場合では、P(X|A) に対してより大きな重みがつけられる。また、どちらの平均を使う場合でも、過去の予測が正確であったモデルを重視するように付加的な重みを与えることができる。最初期のPAQ以外のバージョンではこの調節機能が使われている。 多くのコンテキストミキシング圧縮プログラムでは、1ビット単位で予測する。したがって出力する確率は次のビットが 1 であるかどうかという情報のみで足りる。