4. Expected Model Change Selection with a Linear Model

Why Expected Model Change Differs from Uncertainty

Uncertainty sampling asks a simple question: where is the current model least confident? Expected model change (EMC) asks a different, more decision-oriented question: which unlabeled point, if labeled, would move the model the most? For a linear classifier these two criteria can disagree sharply. A point sitting exactly on the decision boundary is maximally uncertain, but if it is nearly collinear with the current weight vector's orthogonal direction, labeling it barely rotates the hyperplane. Conversely, a point that is only moderately uncertain but far from the boundary along a direction the model has never seen can produce a large parameter update. EMC captures that second effect; uncertainty sampling does not.

This case implements EMC for a binary linear classifier trained with logistic loss, then runs a controlled comparison against entropy-style uncertainty sampling on a synthetic two-dimensional dataset where the ground-truth boundary is known. Because the data is 2-D, we can plot the decision boundary after every query and see exactly why the two strategies diverge.

The EMC Objective for a Linear Model

Let the model be p(y=1|x) = σ(w·x + b) with parameters θ = [w, b]. After adding a candidate point (x, y) to the labeled set and retraining to convergence, the parameters become θ'. The expected model change for that candidate is the expected parameter displacement over the unknown label:

EMC(x) = Σ_{y∈{0,1}} p(y|x) · ||θ'(x,y) − θ||₂

Computing θ' exactly for every candidate requires a full retrain per candidate, which is wasteful. The standard practical approximation uses the gradient of the loss at the candidate, scaled by the Fisher-information-like curvature of the current model. For logistic regression the per-sample gradient with respect to θ is g(x,y) = (σ(w·x+b) − y) · [x, 1], and a widely used EMC surrogate is:

EMC_approx(x) = p(x) · (1 − p(x)) · ||[x, 1]||₂

where p(x) = σ(w·x+b). The factor p(1−p) is the Bernoulli variance — it peaks at the boundary — while ||[x,1]|| rewards points far from the origin, i.e. points that carry more leverage on the linear parameters. This surrogate is cheap (one forward pass per candidate) and is what we will implement. It is an approximation, and the experiment below is designed to show where it helps and where it does not.

Controlled Dataset and Experimental Setup

We generate 400 points from two Gaussian blobs with means (−1.5, 0) and (1.5, 0), unit covariance, and a small overlap so the task is not trivially separable. The true boundary is the vertical line x₁ = 0. We start from 8 randomly chosen labeled points, then run 20 query rounds. In each round the active learner picks one point, the label is revealed, and the model is refit with L2-regularized logistic regression (C = 1.0). We track test accuracy on a held-out set of 2000 points after every round. The same seed and the same initial labeled set are used for both strategies so the comparison is paired.

The left panel shows the two fitted boundaries after 20 queries. The EMC fit sits almost on the true boundary; the uncertainty fit is pulled left because uncertainty sampling kept querying points near the current (initially biased) boundary, reinforcing the bias. The right panel shows the paired accuracy curves: EMC reaches 0.90 test accuracy roughly six labels earlier than uncertainty sampling in this run. These are illustrative results from the described setup, not a guarantee — on other seeds the gap narrows, and on well-separated data both strategies converge quickly.

Implementation

The full script below is self-contained: it generates the data, defines both acquisition functions, runs the paired experiment, and prints the label counts at which each strategy first reaches 0.85 and 0.90 accuracy.

import numpy as np
from sklearn.linear_model import LogisticRegression

rng = np.random.default_rng(7)

def make_data(n=400, seed=7):
    r = np.random.default_rng(seed)
    X0 = r.normal(loc=(-1.5, 0.0), scale=1.0, size=(n // 2, 2))
    X1 = r.normal(loc=( 1.5, 0.0), scale=1.0, size=(n // 2, 2))
    X = np.vstack([X0, X1])
    y = np.hstack([np.zeros(n // 2), np.ones(n // 2)])
    idx = r.permutation(n)
    return X[idx], y[idx]

X_pool, y_pool = make_data()
X_test, y_test = make_data(n=2000, seed=99)

def fit(X, y):
    return LogisticRegression(C=1.0, solver="lbfgs", max_iter=1000).fit(X, y)

def proba(model, X):
    return model.predict_proba(X)[:, 1]

def emc_scores(model, X):
    p = proba(model, X)
    leverage = np.linalg.norm(np.hstack([X, np.ones((len(X), 1))]), axis=1)
    return p * (1.0 - p) * leverage

def uncertainty_scores(model, X):
    p = proba(model, X)
    return -(p * np.log(p + 1e-12) + (1 - p) * np.log(1 - p + 1e-12))

def run(strategy, n_init=8, rounds=20, seed=7):
    r = np.random.default_rng(seed)
    labeled = list(r.choice(len(X_pool), n_init, replace=False))
    unlabeled = [i for i in range(len(X_pool)) if i not in labeled]
    history = []
    for _ in range(rounds + 1):
        model = fit(X_pool[labeled], y_pool[labeled])
        acc = (model.predict(X_test) == y_test).mean()
        history.append((len(labeled), acc))
        if not unlabeled:
            break
        Xu = X_pool[unlabeled]
        scores = emc_scores(model, Xu) if strategy == "emc" else uncertainty_scores(model, Xu)
        pick = unlabeled[int(np.argmax(scores))]
        labeled.append(pick)
        unlabeled.remove(pick)
    return history

def first_reach(history, target):
    for n, acc in history:
        if acc >= target:
            return n
    return None

for strat in ("emc", "uncertainty"):
    h = run(strat)
    print(f"{strat:12s}  acc@8={h[0][1]:.3f}  acc@28={h[-1][1]:.3f}  "
          f"labels->0.85={first_reach(h, 0.85)}  labels->0.90={first_reach(h, 0.90)}")

Expected output shape (values depend on the seed):

emc           acc@8=0.612  acc@28=0.941  labels->0.85=18  labels->0.90=22
uncertainty   acc@8=0.612  acc@28=0.918  labels->0.85=24  labels->0.90=28

Both strategies start from the same 8 labels, so acc@8 must be identical — if it is not, the initial labeled set is not being shared and the comparison is invalid. The labels->0.85 and labels->0.90 columns are the label-efficiency metric: lower is better.

Reading the Result and Common Failure Modes

• EMC wins when the initial boundary is biased. The ||[x,1]|| leverage term pulls queries toward the tails of the feature distribution, which is where the current boundary is most likely to be wrong. If your initial 8 labels happen to be well spread, the advantage shrinks.
• Uncertainty sampling can lock in. If the first few queries all land near a mis-placed boundary, the model keeps refining the wrong region. Watch for a flat accuracy curve over several rounds — that is the symptom.
• Feature scaling matters. The leverage term is not scale-invariant. If one feature has variance 100× the other, EMC will over-query along that axis. Standardize features before computing emc_scores, or the comparison is confounded.
• Regularization interacts with EMC. A large C makes the model move more per label, which amplifies the EMC advantage; a small C damps both strategies toward the same behavior. Keep C fixed across strategies.

Verification Checklist

If the EMC run does not beat uncertainty on your seed, do not conclude EMC is broken — check feature scaling first, then the initial labeled set spread. The controlled setup here is deliberately favorable to EMC so the mechanism is visible; the honest takeaway is that EMC buys label efficiency when the current boundary is misaligned with the data, and buys little when it is already close.