Principle:Dotnet Machinelearning Segment Encoding Optimization
| Knowledge Sources | |
|---|---|
| Domains | Machine Learning, Data Compression, Dynamic Programming |
| Last Updated | 2026-02-09 12:00 GMT |
Overview
Segment encoding optimization uses dynamic programming to find the minimum-cost partitioning of histogram bins into a bounded number of variable-length segments, enabling compact representation of decision tree feature splits.
Description
In gradient boosted decision tree implementations, features are first quantized into a potentially large number of histogram bins (e.g., 256 or more). However, many adjacent bins often have similar gradient statistics, meaning they contribute similar information to the split-finding process. Segment encoding compresses the bin representation by grouping consecutive bins into segments, where all bins within a segment share a single representative output value.
The optimization problem is: given B bins with associated output values, partition them into at most S segments to minimize the total distortion (encoding cost). The distortion for a segment is the sum of squared differences between each bin's true output and the segment's representative value. This is a classic optimal quantization or segmentation problem.
The constraint that segments must consist of contiguous bins (i.e., the partitioning must be a segmentation, not an arbitrary clustering) enables an efficient dynamic programming solution. The contiguity constraint arises naturally from the ordered nature of histogram bins along the feature axis.
The maximum number of segments S determines the bit-width of the compressed representation:
- S = 7 requires 3 bits per encoded value.
- S = 15 requires 4 bits per encoded value.
- S = 21 requires approximately 4.4 bits (stored as 5 bits with unused codes).
- S = 31 requires 5 bits per encoded value.
The trade-off is between compression ratio (fewer segments = fewer bits) and distortion (fewer segments = more information loss). The dynamic programming solution finds the Pareto-optimal point for any given segment budget.
Usage
This principle is applied during feature pre-processing in FastTree training. After the initial histogram bins are established but before the main training loop, the segment optimizer evaluates whether each feature can be compressed into fewer segments without unacceptable distortion. Features that benefit from segmentation are re-encoded, reducing memory consumption and potentially improving cache performance during the histogram accumulation inner loop. The cost-only variants allow a quick evaluation of whether segmentation is worthwhile before committing to the full path computation.
Theoretical Basis
Problem formulation:
Given an ordered sequence of B bins with output values y_0, y_1, ..., y_{B-1} and bin counts n_0, n_1, ..., n_{B-1}, find a partition into at most S contiguous segments that minimizes the total weighted squared error:
Minimize: sum over segments s of (sum over bins b in segment s of n_b * (y_b - mu_s)^2)
where mu_s = (sum of n_b * y_b for b in segment s) / (sum of n_b for b in segment s)
Subject to: at most S segments, each segment is a contiguous range of bins.
Dynamic programming recurrence:
Let C(j, k) be the minimum cost of partitioning bins 0..j into exactly k segments.
Base case:
C(j, 1) = Cost(0, j) for all j
where Cost(a, b) is the weighted squared error of bins a..b assigned to a single segment.
Recurrence:
C(j, k) = min over i in {k-1, ..., j} of [ C(i-1, k-1) + Cost(i, j) ]
Optimal solution:
OPT = min over k in {1, ..., S} of C(B-1, k)
Segment cost computation:
The cost of grouping bins a through b into a single segment with representative value mu is:
Cost(a, b) = sum_{i=a}^{b} n_i * (y_i - mu)^2
where mu = (sum_{i=a}^{b} n_i * y_i) / (sum_{i=a}^{b} n_i)
This can be computed incrementally using running sums:
SumNY = sum of n_i * y_i from a to b
SumN = sum of n_i from a to b
SumNY2 = sum of n_i * y_i^2 from a to b
Cost(a, b) = SumNY2 - SumNY^2 / SumN
Viterbi-like path reconstruction:
The algorithm maintains a backtrace array P(j, k) recording the optimal split point:
P(j, k) = argmin over i of [ C(i-1, k-1) + Cost(i, j) ]
The optimal segmentation is recovered by tracing back from P(B-1, k*) where k* is the optimal number of segments.
Complexity analysis:
- Time: O(B^2 * S) in the general case, with incremental cost computation reducing the constant factor. SIMD parallelism across segment candidates provides further speedup.
- Space: O(B * S) for the cost and backtrace tables.
- Practical performance: For typical values (B = 256, S = 15), the computation is fast enough to run per-feature during pre-processing.
Bitfield-constrained segmentation:
The bits parameter in the implementation allows certain bin boundaries to be excluded from consideration as segment boundaries. When bit i is set in the bitmask, bin i is eligible as a segment start. This enables the algorithm to respect external constraints (e.g., enforcing that segment boundaries align with semantically meaningful feature value thresholds).