コンテキスト・ミキシング

データ圧縮アルゴリズムにおいて、コンテキスト・ミキシング (context mixing) とは、次に現れる符号の予測を二つ以上の統計的モデルの組み合わせによって行う方法である。これによって、個々のモデルのみを用いるより正確に予測できることが期待できる。最も簡単な組み合わせ方を一つ挙げると、それぞれのモデルが算出する確率の平均をとって予測とする方法である。また、他の簡単な方法としては、ランダムフォレストが挙げられる。これはそれぞれのモデルが算出する予測の最頻値を最終的な答えとするものである。複数のモデルの組み合せは、機械学習の研究において活発な領域のひとつである。^[要出典]

Matt Mahoneyが2002年にPAQ 1をリリースしたことに始まるデータ圧縮プログラムPAQは、入力の個々のビットに対する確率を決めるためにコンテキストミキシングを使っている。

データ圧縮への応用

この問題はデータ圧縮で重要となっている。データ圧縮に応用して考えるとき、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 はこのアプローチをとっている^[1]。新しいバージョンではロジスティックミキシング（あるいはニューラルネットワーク）を使う。これは、まずはじめに確率の推定値 $p$ をロジスティック領域 $log (p /(1 - p))$ に変換してから平均をとる^[2]。これにより、0 や 1 に近い推定値に対して、より大きな重み付けが与えられるようにすることができる。この例の場合では、 $P(X|A)$ に対してより大きな重みがつけられる。また、どちらの平均を使う場合でも、過去の予測が正確であったモデルを重視するように付加的な重みを与えることができる。最初期のPAQ以外のバージョンではこの調節機能が使われている。

多くのコンテキストミキシング圧縮プログラムでは、1ビット単位で予測する。したがって出力する確率は次のビットが 1 であるかどうかという情報のみで足りる。

線形ミキシング

複数のモデルが予測する確率の集合 $P i (1) = n 1 i / n i$ が与えられたとする。ここで、 $n i = n 0 i + n 1 i$ で、 $n 0 i$ と $n 1 i$ はそれぞれ i 番目のモデルが当該コンテキスト下で、すでに観測した 0 のビット・1 のビットの数である。このとき、これらの線形ミキシングは、0 と 1 の数の重み付き和によって計算される。

$S 0 = Σ i w i n 0 i$
$S 1 = Σ i w i n 1 i$
$S = S 0 + S 1$
$P(0) = S 0 / S$
$P(1) = S 1 / S$

重み $w i$ は合計すると 1 になるようになっており、初期値としてはすべてが等しくなるように与えられる。データを読み込んでいくと、それぞれのモデルの実績に比例した重みがつけられるようになっているが、入力データを1ビット読み込むたびにより正確なモデルを重視するように調整される。仮に、モデルによるビットが 1 である確率の推定値 P(1) に対して、実際に読み込んだビットの値が $y$ (0 または 1) であったとしたら、重みの調整は以下のように行われる。

$n i = n 0 i + n 1 i$
$error = y - P(1)$
$w i \leftarrow w i + [(S n 1 i - S 1 n i) / (S 0 S 1)] error$

$n i$ に上限・下限を設けることで、この重み付けのバランスがよくなり、圧縮の性能が改善され得る。 PAQ6では、あるビットのカウントが 1 加算されたとき, ほかのビットのカウントは 2 以上あるとき半減される。例えば、シーケンス 000000001 を読み込むと、カウントは $(n 0, n 1) = (8, 0)$ の状態から、 $(5, 1)$ へと変化する。

ロジスティックミキシング

$P i (1)$ を $i$ 番目のモデルが予測する次のビットが 1 である確率とする。このとき、ロジスティックミキシングによる最終的な予測確率 $P(1)$ は以下のように計算される。

$x i = stretch(P i (1))$
$P(1) = squash(Σ i w i x i$ )

ここで、

$stretch(x) = ln(x / (1 - x))$
$squash(x) = 1 / (1 + exp(- x))$ ( $stretch$ の逆演算).

それぞれの予測の後、データを符号化するコストを最小化するように重みが調整される。

$w i \leftarrow w i + η x i (y - P(1))$

ここで $η$ は学習率 (典型的な値は 0.002 から 0.01)、 $y$ は予測ビット、 $(y - P(1))$ は予測エラー。

コンテキストミキシングを利用した圧縮プログラムの一覧

特に触れられていない場合、ロジスティックミキシングを使っている。

すべてのバージョンの PAQ (Matt Mahoney, Serge Osnach, Alexander Ratushnyak, Przemysław Skibiński, Jan Ondrus ら) . PAQAR と PAQ7 以前のバージョンは線形ミキシングを使っている。それ以後のバージョンではロジスティックミキシングを使っている。
すべてのバージョンの LPAQ (Matt Mahoney, Alexander Ratushnyak) .
ZPAQ (Matt Mahoney) [1].
WinRK 3.0.3 (Malcolm Taylor) の最大圧縮 PWCM モード。Version 3.0.2 は線形ミキシングに基づいている。
NanoZip (Sami Runsas) の最大圧縮モード。(オプション -cc)
xwrt 3.2 (Przemysław Skibiński) の最大圧縮モード (オプション -i10 から -i14) で辞書エンコーダのバックエンドとして使用。
cmm1 から cmm4, M1, および M1X2 (Christopher Mattern) は少ない種類のコンテキストを使うことで高速化している。 M1 と M1X2 遺伝的アルゴリズムを使い二つのビットマスクされたコンテキストを分離した最適化パスを選ぶ。
ccm (Christian Martelock).
bit (Osman Turan) [2].
pimple, pimple2, tc, および px (Ilia Muraviev) .
enc (Serge Osnach) PPM に基づいたいくつかの方法と、(線形) コンテキストミキシングによる方法を試行し、最も良い物を選ぶ。
fpaq2 (Nania Francesco Antonio) 高速化のために重みが固定された、重み付け平均を用いている。
cmix (Byron Knoll) はいくつものモデルをミックスするものであり、現在 "the Large Text Compression" ベンチマーク^[3]や Silesia コーパス ^[4] で一位をとっている。また、メモリの使い過ぎによって、賞が認められる条件を満たさないものの、Hutter Prizeを獲得した他のプログラムを超えた結果を残している。

出典

^ Mahoney, M. (2005), “Adaptive Weighing of Context Models for Lossless Data Compression”, Florida Tech. Technical Report CS-2005-16
^ Mahoney, M. "PAQ8 Data Compression Program".
^ Matt Mahoney (2015年9月25日). “Large Text Compression Benchmark”. 2015年11月4日閲覧。
^ Matt Mahoney (2015年9月23日). “Silesia Open Source Compression Benchmark”. 2015年11月4日閲覧。

[1] Mahoney, M. (2005), “Adaptive Weighing of Context Models for Lossless Data Compression”, Florida Tech. Technical Report CS-2005-16

[2] Mahoney, M. "PAQ8 Data Compression Program".

[largetext-3] Matt Mahoney (2015年9月25日). “Large Text Compression Benchmark”. 2015年11月4日閲覧。

[silesia-4] Matt Mahoney (2015年9月23日). “Silesia Open Source Compression Benchmark”. 2015年11月4日閲覧。

[1]

[2]

[3]

[4]