PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Weighting of Training Data in Adaptive Coding

Yuriy Reznik

arXiv:2609.27783v1cs.IT

TL;DR

Adaptive coders often use training data that do not match the source being encoded, so deciding how much to trust them matters. The paper weights training counts in a KT estimator and derives a redundancy-minimizing weight. Under mismatch, the effective training information is capped regardless of how much data were collected.

  • Problem

    Adaptive coders use training data that may not match the encoded source, leaving how much to trust that data as a design question.

    Source: §1 · p. 1

  • Method

    The paper scales training counts by ξ∈[0,1] in a KT estimator and derives a closed-form optimal weight from training length and KL divergence.

    Source: §1 · p. 2

  • Results

    ξ*=d/(2ℓD+d) minimizes redundancy, and any mismatch caps usable training information at d/(2D) symbols.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Three selectors address unknown D: offline estimation from training-set spread, a decoded-prefix plug-in loop, or a twice-universal mixture with no estimate.

    Source: §1 · p. 2

    The analysis assumes independent training and message sequences drawn from unknown distributions over a finite alphabet, which need not coincide.

    Source: §2 · p. 2

Abstract

from arXiv · show

Adaptive coders are commonly primed with training data, turned into context tables or shipped dictionaries. The training data generally do not match the source being encoded, and the coder must decide how much to trust them. We make that trust a design variable: a Krichevsky--Trofimov (KT) estimator over an $m$-ary alphabet whose training counts are scaled by $ξ\in[0,1]$. For a training sequence of length $\ell$ at Kullback--Leibler divergence $D$ nats per symbol from the message source, the redundancy-minimizing weight is $ξ^*=d/(2\ell D+d)$, $d=m-1$. The effective training length $ξ^*\ell$ follows a harmonic law: any mismatch caps the usable training information at $d/(2D)$ symbols, however much was collected. Three implementable selectors supply the unknown $D$: offline, from the spread of the training set; by a plug-in loop, from the decoded prefix; and by a twice-universal mixture, with no estimation at all. On the ten English texts of the Calgary and Canterbury corpora, weighting removes up to $22.7\%$ of the redundancy of the classical KT code, the $ξ=0$ endpoint, and beats both endpoints on every file. An open-source implementation is provided.

1 Introduction

Adaptive coders use training data that may mismatch the message source, making the degree of trust a design choice. The paper scales KT training counts by a weight, derives its optimum, and describes selectors for the unknown mismatch.

1 Introduction

  • Earlier mismatch treatments selected which training data to retain and how much, with finite full-weight use optimal under divergence D.For heterogeneous memories with mixture sources, prior work instead described clustering and full-weight use of matched data.Source: §1 · p. 2
  • The paper makes the weight of retained training data a control variable, scaling KT counts by ξ∈[0,1] and deriving a closed-form choice.The construction applies the power prior to the KT estimator.Source: §1 · p. 2
  • ξ*=d/(2ℓD+d) minimizes redundancy, and any mismatch caps effective training information at d/(2D) symbols.At D=0, the training data receive full weight; weighting also strictly beats truncation.Source: §1 · p. 2
  • Three selectors address unknown D: training-set spread offline, a decoded-prefix plug-in loop, or a twice-universal mixture requiring no estimate.The paper evaluates them on ten English texts from the Calgary and Canterbury corpora.Source: §1 · p. 2

2 The Weighted KT Code

The weighted KT code combines training and message counts while allowing the training contribution to be discounted. Its analysis defines source mismatch through KL divergence and measures the resulting code's excess length as redundancy.

2 The Weighted KT Code

  • Training and message sequences are independent draws from unknown distributions, and their mismatch is D=D(PT∥PS).The sequences need not share a distribution.Source: §2 · p. 2
  • Here d=m−1 is model dimension, and d/2 nats is the expected amount by which a fitted m-ary model over-describes its sample.The paper calls this quantity the Wilks excess.Source: §2 · pp. 2–3
  • The coder scales training counts by ξ∈[0,1] while message counts enter at full weight.At ξ=1 training data are treated as part of the message; at ξ=0 they are discarded, yielding classical KT.Source: §2 · p. 3
  • Scaling counts by ξ gives effective training length ℓeff=ξℓ, the number of matched symbols that would be equally informative.The trained prior is a Dirichlet distribution with parameters ξkx(xT)+1/2, and an arithmetic coder uses the resulting conditionals.Source: §2 · p. 3
  • Redundancy is expected excess code length over message entropy, averaged over the training sequence, and decomposes into per-symbol excesses.It is measured in nats.Source: §2 · p. 3

3 Redundancy Analysis

The section derives a redundancy expansion for weighted KT coding and uses it to characterize optimal weighting, effective training length, and comparisons with full weighting and truncation.

3 Redundancy Analysis

  • The expansion is valid across training-to-message information ratios, while the stated practice regime has ξℓ≫1 and ξℓ≪n.A cancellation leaves the estimation cost with coefficient d/2 regardless of how well the trained model is centered; mismatch enters through the divergence term.Source: §3 · p. 4
  • For D>0, redundancy is minimized at the stationary point of a strictly convex objective; as ℓ grows at fixed D, ξ*→0 while ℓeff→ℓ∞.At D=0, the optimum uses matched data in full.Source: §3 · p. 5
  • A factor-k error in estimating D changes redundancy by d/2(1/k − 1 + ln k) nats, independent of ℓ, D, and n.The paper concludes that estimating D requires only order-of-magnitude accuracy.Source: §3 · p. 5
  • Under mismatch, full weighting costs ℓD − d/2 ln(1 + 2ℓD/d) nats over the optimum, while ξ=0 costs d/2 ln ℓeff nats over it.The paper describes the full-weight penalty as growing linearly in ℓD and says long mismatched training at full weight is worse than using no training data.Source: §3 · p. 5
  • Discounting a heterogeneous database beats curating a matched subset of the same effective size; its advantage over truncation grows to d/2 nats as ℓ grows.Truncation is treated as ξ=1 applied to a prefix.Source: §3 · p. 5
  • No decaying schedule improves on the constant optimal weight: each per-symbol leading-term minimizer is time-independent, and count updates already decay training influence.The paper says manual decay would double-count that fade.Source: §3 · pp. 5–6

4 Implementations

The section turns unknown mismatch D into implementable weights: a design-time database-spread estimate, a prefix-feedback estimate, or a weight-grid mixture. Shared training data let the decoder reproduce updates without side information.

4 Implementations

  • The shared divergence estimate uses KT-smoothed empirical distributions, correcting second-order Wilks excess and staying finite when the samples have differing supports.The correction removes the plug-in divergence’s second-order overshoot.Source: §4 · p. 6

4.1 Offline: the Database Spread

  • Pairwise divergences among training sequences estimate population spread, whose average fixes the weight at design time.If the estimate clamps to zero, the selector returns ξ*=1; held-out messages can provide a direct estimate when available.Source: §4.1 · pp. 6–7, Figure 1 · p. 7

4.2 Plug-in: a Feedback Loop

  • At prefix lengths 1, 2, 4, 8, …, the plug-in selector estimates training-to-prefix divergence and resets the weight.Logarithmic updates track the estimate’s improvement rate; the decoder reproduces the schedule, and the initialization price is bounded by a constant of order d nats.Source: §4.2 · pp. 7–8, Figure 2 · p. 7

4.3 Mixture: Twice-Universal over the Weight

  • Posterior weighting combines a grid of weighted KT codes; decoded symbols update the mixture without selecting or signaling an arm.The mixture is twice universal across source and weight, and its boundary arms represent the limiting regimes.Source: §4.3 · p. 8, Figure 3 · p. 8

4.4 Complexity of the Proposed Approaches

  • All selectors retain the O(mn) coding baseline except the mixture, which costs O(log ℓ) times that baseline.The plug-in adds O(m log n) overhead, while the offline selector adds no coding-time cost.Source: §4.4 · p. 9

5 Experimental Results

The experiments compare three data-weight selectors with the classical KT endpoints on ten English texts under a shared byte-alphabet model. The selectors beat both endpoints on every file, with the mixture closest to the oracle.

5 Experimental Results

  • The leave-one-out evaluation uses each of ten Calgary and Canterbury files as the message and concatenates the other nine as training data.The model is a memoryless byte-alphabet source (m = 256), shared across conditions despite real text not being i.i.d.Source: §5 · p. 9
  • The six conditions include cold-start and full-weight KT, offline and plug-in weights, a 24-arm mixture, and a hindsight oracle.The oracle selects the best fixed weight using the scored file’s code lengths and is not an implementable coder.Source: §5 · p. 9
  • Table 1 reports empirical entropies, offline divergence estimates, and selected weights; Table 2 reports per-file redundancies and length-weighted averages.The final Table 2 row gives the average relative change against the cold start.Source: §5 · pp. 9–10, Table 1 · p. 10, Table 2 · p. 10
  • 22.7%: the mixture removes this much redundancy versus the cold start, within 0.0003 bits per symbol of the oracle’s 23.2% ceiling; weighted coding beats both endpoints on every file.The offline and plug-in weights remove 19.9% and 18.1%, respectively; full weight multiplies cold-start redundancy twenty-three-fold.Source: Table 2 · p. 10, §5 · p. 10
  • 420–650 characters: optimal effective lengths against training sequences of about three million symbols, with 99.98% of training data discounted away.Estimated divergences range from 0.28 to 0.43 bits per symbol; on book2, plug-in tracks realized mismatch at 0.74 while offline uses population spread at 0.17.Source: §5 · p. 10

6 Conclusions

The paper makes the training-data weight a design variable for adaptive coding and derives its optimum from training length and source mismatch. The resulting law caps usable training information under mismatch, while selectors and conditional-coder extensions make the approach applicable to practical settings.

6 Conclusions

  • For training length ℓ and divergence D nats per symbol, the optimal weight is ξ* = d/(2ℓD + d), with d = m − 1; effective training length is capped at d/(2D) under any mismatch.The same optimal weight and harmonic law apply per context and in aggregate for conditional coders.Source: §6 · p. 11
  • Three selectors address unknown divergence: an offline estimate from training-set spread, a plug-in loop using the decoded prefix, and a twice-universal mixture requiring no estimate.The aggregate conditional-coder formulation uses context-specific training lengths and divergences.Source: §6 · p. 11
  • For context-based coders, per-context weights can replace hand-tuned CABAC initialization strengths with computed values; segmented and random-access formats can turn shared-dictionary use into a dial.The paper also describes sliding-window use for drifting sources and weighting a pretrained model according to its fit on encoded data.Source: §6 · p. 11
Loading 2609.27783v1…