コンテキストの混合

コンテキストミキシングは、 2 つ以上の統計モデルの次のシンボル予測を組み合わせて、個々の予測よりも正確な予測を生成するデータ圧縮 アルゴリズムの一種です。たとえば、1 つの簡単な方法 (必ずしも最善とは限りません) は、各モデルによって割り当てられた確率を平均することです。ランダム フォレストは別の方法です。これは、個々のモデルによって出力された予測の最頻値である予測を出力します。モデルの組み合わせは、機械学習の研究が活発に行われている分野です。^{[引用が必要]}

PAQシリーズのデータ​​圧縮プログラムは、コンテキスト ミキシングを使用して、入力の 個々のビットに確率を割り当てます。

2 つの条件付き確率とが与えられていて、条件と の両方が与えられた場合にイベント X が発生する確率を推定したいとします。確率論で結果を出すには情報が不十分です。実際、結果がどのようなものになるかがまったくわからないシナリオを作成することは可能です。しかし、直感的には、結果は 2 つの平均のようなものになると考えられます。 ${\displaystyle P(X|A)}$${\displaystyle P(X|B)}$${\displaystyle P(X|A,B)}$${\displaystyle A}$${\displaystyle B}$

この問題は、データ圧縮にとって重要です。このアプリケーションでは、およびはコンテキストであり、は、圧縮されるデータの次のビットまたはシンボルが特定の値を持つイベントであり、およびは、2 つの独立したモデルによる確率推定値です。圧縮率は、推定された確率が、イベント の真だが未知の確率にどれだけ近づくかによって決まります。コンテキスト およびが、各コンテキストでの の発生回数を数えることによっておよび を正確に推定できるほど頻繁に発生していることはよくありますが、2 つのコンテキストが同時に頻繁に発生していないか、または組み合わせたケースの統計を収集するためのコンピューティング リソース (時間とメモリ) が不足しています。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle X}$${\displaystyle P(X|A)}$${\displaystyle P(X|B)}$${\displaystyle X}$${\displaystyle A}$${\displaystyle B}$${\displaystyle P(X|A)}$${\displaystyle P(X|B)}$${\displaystyle X}$

たとえば、テキスト ファイルを圧縮しているとします。前の文字がピリオド (コンテキスト) であり、最後の改行が 72 文字前 (コンテキスト ) に発生したことを前提として、次の文字が改行かどうかを予測します。改行が、最後の 5 つのピリオドのうちの 1 つの後 ( ) および最後の 10 行のうちの 5 行の 72 列目 ( ) で以前に発生したとします。これらの予測をどのように組み合わせればよいでしょうか。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle P(X|A=0.2}$${\displaystyle P(X|B)=0.5}$

線形混合とロジスティック混合という 2 つの一般的なアプローチが使用されています。線形混合では、証拠によって重み付けされた予測の加重平均が使用されます。この例では、 はより多くのテストに基づいているため、 の方が重みが大きくなります。PAQ の古いバージョンでは、このアプローチが使用されています。^[1]新しいバージョンでは、平均化する前に、まず予測をロジスティック領域 log(p/(1-p)) に変換することにより、ロジスティック (またはニューラル ネットワーク) 混合が使用されています。 ^[2]これにより、0 または 1 (この場合は ) に近い予測に大きな重みが付けられます。どちらの場合も、各入力モデルに追加の重みが与えられ、過去に最も正確な予測を行ったモデルが優先されるように調整される場合があります。PAQ の最も古いバージョンを除くすべてのバージョンでは、適応型重み付けが使用されます。 ${\displaystyle P(X|B)}$${\displaystyle P(X|A)}$${\displaystyle P(X|B)}$${\displaystyle P(X|A)}$

ほとんどのコンテキスト ミキシング コンプレッサーは、一度に 1 ビットの入力を予測します。出力確率は、次のビットが 1 になる確率です。

予測値のセット P _i (1) = n _1i /n _iが与えられます。ここで、n _i = n _0i + n _1iであり、n _0iと n _1iはそれぞれ i 番目のモデルの 0 ビットと 1 ビットの数です。確率は 0 と 1 のカウントの加重加算によって計算されます。

• S ₀ = Σ _i w _i n _0i
• S ₁ = Σ _i w _i n _1i
• S = S ₀ + S ₁
• P(0) = S ₀ / S
• P(1) = S ₁ / S

重み w _iは最初は等しく、常に合計が 1 になります。初期条件では、各モデルは証拠に比例して重み付けされます。その後、重みはより正確なモデルを優先するように調整されます。予測される実際のビットが y (0 または 1) であると仮定します。この場合、重みの調整は次のようになります。

• n _i = n _0i + n _1i
• 誤差 = y – P(1)
• w _i ← w _i + [(S n _1i - S ₁ n _i ) / (S ₀ S ₁ )] エラー

圧縮は、モデルの重み付けがよりバランスよくなるようにn _{i を}制限することによって改善できます。PAQ6 では、ビット カウントの 1 つが増加するたびに、もう 1 つのカウントの 2 を超える部分が半分になります。たとえば、シーケンス 000000001 の後、カウントは (n ₀、 n ₁ ) = (8、0) から (5、1) になります。

P _i (1)をi番目のモデルによる次のビットが1になるという予測とします。最終的な予測P(1)は次のように計算されます。

• x _i = ストレッチ(P _i (1))
• P(1) = squash(Σ _i w _i x _i )

ここでP(1)は次のビットが1になる確率、P _{i (1)は}i番目のモデルによって推定される確率、

• ストレッチ(x) = ln(x / (1 - x))
• squash(x) = 1 / (1 + e ^−x ) （伸張の逆関数）。

各予測の後、コーディングコストを最小限に抑えるために重みを調整してモデルが更新されます。

• w _i ← 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、その他）[1]。PAQARおよびPAQ7より前のバージョンでは線形混合が使用されていました。それ以降のバージョンではロジスティック混合が使用されました。
• すべてのLPAQバージョン（Matt Mahoney、Alexander Ratushnyak）[2]。
• ZPAQ（マット・マホニー）[3]
• WinRK 3.0.3（マルコム・テイラー）の最大圧縮PWCMモード[4]。バージョン3.0.2は線形混合に基づいていました。
• NanoZip（Sami Runsas）の最大圧縮モード（オプション-cc）[5]
• xwrt 3.2 (Przemysław Skibiński)の最大圧縮モード(オプション-i10から-i14) [6] を辞書エンコーダのバックエンドとして使用します。
• cmm1 から cmm4、M1、および M1X2 (Christopher Mattern) は、高速化のために少数のコンテキストを使用します。M1 と M1X2 は、遺伝的アルゴリズムを使用して、別の最適化パスで 2 つのビット マスクされたコンテキストを選択します。
• ccm（クリスチャン・マーテロック）。
• ビット（オスマン・トゥラン）[7]。
• pimple、pimple2、tc、px（イリア・ムラヴィエフ）[8]。
• enc（Serge Osnach）はPPMと（線形）コンテキストミキシングに基づくいくつかの方法を試し、最適なものを選択しました。[9]
• 高速化のために固定重み平均を使用する fpaq2 (Nania Francesco Antonio)。
• cmix（Byron Knoll）は多くのモデルを混合しており、現在Large Text Compressionベンチマーク^[3]とSilesiaコーパス^[4]で1位にランクされており、メモリ使用量が多すぎるため対象外ではあるものの、Hutter Prizeの受賞作品を上回っています。