AdaBoost Binary Classification

Litsea uses the AdaBoost (Adaptive Boosting) algorithm for binary classification to determine word boundaries. This chapter explains the algorithm as implemented in Litsea.

Overview

AdaBoost combines many weak learners (simple classifiers) into a strong ensemble classifier. In Litsea:

• Positive label (+1) = word boundary
• Negative label (-1) = non-boundary (continuation of the current word)
• Weak learners = individual features (each feature is a binary “stump” – present or absent)

Training Algorithm

The training loop in AdaBoost::train() works as follows:

Initialization

1. Load features and instances from the training file
2. Initialize instance weights uniformly (later adjusted based on initial score)
3. All model weights start at zero

Iterative Boosting

For each iteration t (up to num_iterations):

Step 1: Calculate weighted errors

For each feature h, compute its weighted error over all instances:

error[h] -= D[i] * y[i]   (for each instance i that has feature h)

where D[i] is the instance weight and y[i] is the true label.

Step 2: Select the best weak learner

Find the feature with the lowest weighted error rate:

error_rate(h) = (error[h] + positive_weight_sum) / instance_weight_sum
h_best = argmax_h |0.5 - error_rate(h)|

The baseline competitor is the “all-negative” classifier (always predicts -1), whose error rate equals the fraction of positive instances. Any real feature must beat this baseline.

Step 3: Check convergence

If |0.5 - best_error_rate| < threshold, stop early – no feature can significantly improve the model.

Step 4: Compute the weak learner weight

alpha = 0.5 * ln((1 - error_rate) / error_rate)
model[h_best] += alpha

A lower error rate produces a higher alpha, giving more influence to better features.

Step 5: Update instance weights

For each instance i:
    prediction = +1 if h_best in features(i), else -1

    if y[i] * prediction < 0:  (misclassified)
        D[i] *= exp(alpha)     (increase weight)
    else:                       (correctly classified)
        D[i] /= exp(alpha)     (decrease weight)

Normalize: D[i] /= sum(D)

This ensures subsequent iterations focus on the instances that are still difficult to classify.

Prediction

Given an input set of features (attributes), the prediction is:

score = bias + sum(model[feature] for each feature in attributes)
prediction = +1 if score >= 0, else -1

Bias Term

The bias is computed as:

bias = -sum(all model weights) / 2.0

The value is cached in the learner and kept in sync by every weight-mutating path, so reading it during inference is O(1).

This centers the decision boundary. The empty-string feature ("") serves as the bias bucket during training. It is registered at feature index 0 on every construction path (new(), feature-file initialization, and model loading), so models trained through add_instance() train, save, and reload correctly.

Compiled Scoring in the Segmenter

predict() itself looks features up by string, and its semantics are unchanged. The Segmenter, however, does not call it on the hot path: after a model (re)load it compiles the learner’s (feature, weight) pairs into integer-indexed tables and scores each sentence in two passes (see Prediction Pipeline). The compiled tables mirror the model exactly; only the floating-point accumulation order differs, and the differential test suite pins that the segmentation output stays identical in practice.

Model File Format

The trained model is saved as a simple text file:

feature1\tweight1
feature2\tweight2
...
bias_value

• Each line contains a feature name and its weight (tab-separated)
• Zero-weight features are omitted
• The last line contains the bias term (a single number)

Malformed files (empty, truncated before the bias line, duplicate bias lines or features, non-finite weights) are rejected at load time. See Model File Format for details.

This page describes the AdaBoost training algorithm. The file format above is also how litsea stores the four bundled segmentation models (japanese.model, chinese.model, korean.model, english.model) – but as of issue #165, those are no longer produced by boosting. They are trained as a 2-class Averaged Perceptron and losslessly collapsed into this same scalar-weight format (see Pre-trained Models for the collapse procedure). Any file AdaBoost::load_model can read is a valid instance of this format, but that does not mean it was actually produced by the boosting loop described above.

Hyperparameters