Editing Context mixing (section)

=== Linear Mixing ===

We are given a set of predictions <math display="inline">P_i(1) = n_{1i}/n_i</math>, where <math display="inline">n_i = n_{0i} + n_{1i}</math>, and <math>n_{0i}</math> and <math>n_{1i}</math> are the counts of 0 and 1 bits respectively for the <math>i</math>'th model. The probabilities are computed by weighted addition of the 0 and 1 counts:

*<math display="inline">S_0 = \sum_i w_i n_{0i}</math>
*<math display="inline">S_1 = \sum_i w_i n_{1i}</math>
*<math display="inline">S = S_0 + S_1</math>
*<math display="inline">P(0) = \frac{S_0}{S}</math>
*<math display="inline">P(1) = \frac{S_1}{S}</math>

The weights <math>w_i</math> are initially equal and always sum to 1. Under the initial conditions, each model is weighted in proportion to evidence. The weights are then adjusted to favor the more accurate models. Suppose we are given that the actual bit being predicted is <math>y</math> (0 or 1). Then the weight adjustment is:<ref>Mahoney, M. V. (2005). [http://mattmahoney.net/dc/cs200516.pdf Adaptive weighing of context models for lossless data compression.]</ref><math display="block">w_i \leftarrow \max[0, w_i + (y - P(1)) \frac{S n_{1i} - S_1n_i}{S_0S_1}]</math>Compression can be improved by bounding <math display="inline">n_i</math> so that the model weighting is better balanced. In PAQ6, whenever one of the bit counts is incremented, the part of the other count that exceeds 2 is halved. For example, after the sequence 000000001, the counts would go from <math display="inline">(n_0, n_1) = (8, 0)</math> to <math display="inline">(5, 1)</math>.