Locally-Weighted Logistic Regression

Chapter 1: Recap — Logistic Regression, Rebuilt

Before we add the "locally-weighted" twist, let's rebuild ordinary logistic regression from scratch in one chapter, so the new pieces have somewhere to attach. If this is fresh, the full Logistic Regression Gleam goes slower; here we move briskly but skip nothing essential.

We have training data: pairs (x⁽ⁱ⁾, y⁽ⁱ⁾) for i = 1, …, m. Each x⁽ⁱ⁾ is a feature vector (in our clinic, [heart rate, oxygen]), and each label y⁽ⁱ⁾ ∈ {0, 1}. We want a function that takes a new x and outputs a probability that y = 1.

A raw linear score θ^Tx can be any real number — from −∞ to +∞. A probability must live in (0, 1). The bridge between them is the sigmoid (logistic) function, which squashes any real number into (0, 1):

Here g(z) = 1/(1 + e^−z). At z = 0 it gives 0.5 (a coin flip). As z → +∞ it saturates to 1; as z → −∞ it saturates to 0. By the bias trick we set x₀ = 1, so θ^Tx = θ₀ + θ₁x₁ + θ₂x₂ — the θ₀ term is the intercept that lets the boundary float off the origin.

Why we maximize something: the likelihood

We need a number that says "how well does this θ explain the data?" so we can search for the θ that scores best. That number is the likelihood: the probability the model assigns to the labels we actually observed.

For one example with label y, the model's predicted probability of that specific label is a clever one-liner: h(x)^y(1−h(x))^1−y. Check it: if y = 1 the second factor is anything⁰ = 1, leaving h(x). If y = 0 the first factor is anything⁰ = 1, leaving 1−h(x). One formula, both cases.

Assuming examples are independent, the likelihood of the whole dataset is the product over all i. Products of many small numbers underflow and are painful to differentiate, so we take the logarithm — turning the product into a sum (log of a product is a sum of logs). The log-likelihood is:

We maximize ℓ(θ) because a bigger ℓ means the model assigned higher probability to the labels we truly saw — it "explains the data better." (If you've met cross-entropy loss, it's exactly −ℓ: maximizing log-likelihood and minimizing cross-entropy are the same act, sign-flipped.)

Let's make this concrete with one worked number. Suppose for some example y = 1 and the model currently predicts h(x) = 0.8. Its contribution to ℓ is 1·log(0.8) + 0·log(0.2) = log(0.8) = −0.223. Now suppose the model had predicted only h(x) = 0.3 for that same y = 1 example: contribution = log(0.3) = −1.204. The first θ gives a less-negative (better) log-likelihood, exactly because it put more probability on the correct label. Maximizing ℓ pushes h(x) up where y = 1 and down where y = 0.

The decision boundary is where z = 0

Once θ is fixed, we predict class 1 when h(x) ≥ 0.5. Since the sigmoid hits 0.5 exactly at z = 0, the decision boundary is the set of points where θ^Tx = 0 — a straight line (in 2D) or hyperplane (in higher D). That straightness is the limitation Chapter 0 ran into. LWLR's whole job is to let that boundary curve, without abandoning this machinery.

Chapter 2: The Weighting Kernel — A Soft Spotlight

Here is where LWLR earns its name. We will attach to each training example a weight w_i ∈ (0, 1] that says, "for this query, how much should example i count?" Nearby examples get weights near 1; far examples get weights near 0. The weight formula is a single, beautiful exponential bump:

Let's name every piece, because each one carries the whole intuition:

• x is the query point — the location we're trying to classify right now. The weights depend on it, which is exactly why re-querying elsewhere gives a different fit.
• x⁽ⁱ⁾ is the i-th training example.
• ‖x − x⁽ⁱ⁾‖² is the squared Euclidean distance between query and example — the straight-line distance, squared. In 2D with x = [a, b]: (a−a_i)² + (b−b_i)².
• τ (tau) is the bandwidth — the radius of the spotlight. It sets how quickly weight falls off with distance. This is the lesson's one tuning knob, and Chapter 4 is devoted to it.

Read the formula as a story. The query shines a soft circular spotlight on the data. Right at the query (distance 0), the exponent is 0, so w = e⁰ = 1: full brightness. As an example sits farther away, the squared distance grows, the exponent goes more negative, and the weight fades smoothly toward 0: that example slips into the dark. There is no hard cutoff — the light dims gradually. That smoothness is what makes the resulting boundary smooth too.

Worked by hand: computing four weights

Let's actually compute some weights, every step. Put the query at x = (0, 0), and use bandwidth τ = 1, so 2τ² = 2·1² = 2. Here are four training points and their weights:

Trace the meaning: the point sitting exactly on the query counts fully (1.000). One unit away, it's already down to 0.607 — still a strong vote. Two units away (diagonally), 0.368. And the point three units out is essentially switched off at 0.011 — it contributes about a hundredth of a normal example. That far point will barely budge the local fit, which is the whole point: the classifier we build at the origin should be shaped by the origin's neighborhood, not by distant data.

Now watch what τ does to those same four points. Redo x⁽⁴⁾ with a bigger bandwidth τ = 3, so 2τ² = 18: w₄ = e^−9/18 = e^−0.5 = 0.607. The far point that was nearly dead (0.011) is now a full participant (0.607)! A larger τ widens the spotlight so even distant points count — pushing LWLR back toward treating all data equally, i.e., toward ordinary logistic regression. A smaller τ shrinks the spotlight to a pinprick. Hold that lever; Chapter 4 pulls it hard.

Two design choices in this kernel are worth pausing on, because they reveal why the formula has this exact shape (Concept + Realization — we don't accept a formula we can't justify):

Why squared distance, and why the exponential? Squaring makes the bump perfectly round and smooth at the center (no kink at d = 0) and, paired with the exp, gives the Gaussian "bell" shape — the same shape as a normal distribution. That smoothness matters: a kinked or hard-cutoff weighting would produce a kinked decision boundary. The exponential guarantees weights are always positive (you can't have a "negative amount of trust") and decay gracefully rather than dropping to zero abruptly.

Why the 2τ² in the denominator and not just τ? It's a convention borrowed from the Gaussian, where 2σ² appears. The "2" and the "square" make τ behave like a standard deviation — a natural "one-sigma radius" where the weight has dropped to e^−1/2 ≈ 0.607. So "τ = 1" literally means "points one unit out still count 61%." That interpretability is the payoff.

Chapter 3: Newton's Method on the Weighted Objective

We now have weights. Let's bolt them onto the log-likelihood and then actually solve for the best local θ. The weighted log-likelihood simply drops a w_i in front of each example's term — "count this example w_i times":

Two new symbols. The ∑ term is the familiar log-likelihood, now weighted. The leading −(λ/2)θ^Tθ is a ridge (L2) penalty with a tiny λ = 10⁻⁴. Why is it there? Because in a local fit, the spotlight sometimes lands on a region where one class is entirely absent — the data is perfectly separable locally, and the unpenalized optimizer would drive θ to infinity chasing ever-higher confidence. The minuscule ridge gently pulls θ back toward 0, keeping the matrices invertible and the arithmetic finite. It's a numerical seatbelt, not a modeling choice; λ is small enough to barely affect the answer where data is plentiful.

Why Newton's method, not gradient descent?

To maximize ℓ we need to find where its slope is zero. Gradient ascent would take many small uphill steps. Newton's method does something smarter: it uses the curvature (the second derivative) to jump, in essentially one or a few steps, straight to the peak of a bowl-shaped function. Because the logistic log-likelihood is concave (one smooth hill, no false summits), Newton converges in a handful of iterations — here, six is plenty. For LWLR this speed is precious: remember, we re-solve from scratch at every query point, so a slow optimizer would be agony. Newton's curvature-awareness is what makes per-query refitting practical.

Newton's update for maximizing a function is θ ← θ − H⁻¹∇, where ∇ is the gradient (vector of first derivatives) and H is the Hessian (matrix of second derivatives). Let's derive both for our weighted objective — every term justified.

The gradient: ∇ = X^Tz − λθ

Take the derivative of ℓ with respect to θ. The key fact we lean on is the sigmoid's clean derivative: ∂h/∂(θ^Tx) = h(1−h). Working through the log terms (using that derivative and the chain rule), each example's weighted contribution to the gradient collapses to a strikingly simple form:

Define z_i = w_i(y⁽ⁱ⁾ − h(x⁽ⁱ⁾)) — the weighted residual for example i, "how wrong are we here, scaled by how much this point counts." Stacking all the x⁽ⁱ⁾ as rows of a matrix X and all z_i into a vector z, the sum ∑_i z_i x⁽ⁱ⁾ is exactly the matrix-vector product X^Tz. So:

The −λθ is the derivative of the ridge term −(λ/2)θ^Tθ. Read the whole thing: the gradient pushes θ in the direction of weighted, signed errors. Where we under-predict (y > h) on a heavily-weighted point, z_i is positive and large, and θ moves to fix it.

The Hessian: H = X^TDX − λI

Differentiate the gradient once more to get the Hessian (the matrix of how the gradient changes). Each example contributes a term proportional to its weight times h(1−h) — the slope of the sigmoid, biggest where the model is most uncertain (h near 0.5). Collecting these into a diagonal matrix D:

and the full Hessian is:

The −λI comes from differentiating −λθ once more (the derivative of −λθ w.r.t. θ is −λI, the identity scaled). Every D_ii is negative (weights, h, and 1−h are all positive, with a leading minus sign), which makes H negative-definite — the mathematical signature of a concave hill with a single peak. That's the guarantee Newton needs to march uphill reliably.

One Newton step, entirely by hand

Let's do a single Newton update on a tiny one-dimensional example so every number is visible. We'll drop the bias to keep θ a single scalar (so X, z, H are all 1×1 — just numbers). Setup: two training points, both with weight w = 1 for simplicity, ridge λ = 0, starting from θ = 0.

One step moved θ from 0 to +1.0. Sanity-check the direction: x⁽¹⁾ = 2 has label 1, x⁽²⁾ = −2 has label 0, so a positive θ correctly says "bigger x → class 1." With θ = 1, the prediction at x = 2 is g(2) = 0.88 (was 0.5) and at x = −2 is g(−2) = 0.12 — both moved decisively toward their true labels in a single step. That one-jump efficiency is the gift of using curvature.

Chapter 4: The Bandwidth τ — The Bias/Variance Knob

This is the heart of the lesson. We have one knob, τ, and turning it sweeps LWLR across the entire spectrum from "memorize every wiggle" to "draw one straight line." Understanding τ is understanding the bias/variance trade-off in the most tactile way you'll ever see it.

Recall the spotlight from Chapter 2. τ is its radius. Now think about what radius does to the decision boundary, which is what we actually care about:

Tiny τ: a wiggly boundary that hugs the data (high variance)

With a very small τ, the spotlight is a pinprick. At each query, only the two or three nearest training points have non-negligible weight; everything else is dark. The local fit therefore bends to satisfy just those few neighbors. Move the query a little and a different tiny set of neighbors takes over, so the boundary can swerve sharply. The result is a boundary that hugs the data — it threads between individual points, even chasing single noisy outliers.

This is high variance: the boundary is exquisitely sensitive to the exact training sample. Resample the data slightly and the wiggly boundary changes shape completely. It memorizes noise. In the τ → 0 limit, LWLR essentially becomes a nearest-neighbor classifier — each query just copies its closest point's label.

Huge τ: a straight line — ordinary logistic regression (high bias)

Now crank τ up. The spotlight floods the whole dataset; every point's weight approaches the same value (they're all "near" relative to the enormous radius). When all weights are roughly equal, the weighted log-likelihood is just a scalar multiple of the unweighted one — and maximizing it gives the same θ as ordinary, global logistic regression. The location of the query stops mattering. Every query produces the same straight-line boundary.

This is high bias: the model is too rigid to follow a curved truth, so it's systematically wrong wherever the real boundary bends — exactly the failure from Chapter 0. As τ → ∞, LWLR becomes ordinary logistic regression. That's a beautiful unification: ordinary logistic regression is just LWLR with the spotlight turned up to infinity.

Let's anchor this with a number. Suppose the true boundary is a gentle arc and we have m = 200 points with a bit of label noise. With τ = 0.05, a query's effective sample size — the sum of weights, roughly "how many points actually vote" — might be just 2 or 3. Fitting a classifier on 3 noisy points is a recipe for wild swings. With τ = 5, the effective sample size is nearly all 200, so the fit is stable but blind to local curvature. With τ = 0.4, maybe 25–40 points vote — enough to average out noise, few enough to stay local. That "effective number of voters = sum of weights" is the cleanest way to feel what τ trades off.

The showcase: turn τ and watch the boundary transform

Here is the payoff — the simulation this whole lesson was building toward. Two classes interleave along a curve (a curved truth no straight line can capture). The shaded region is LWLR's decision boundary, recomputed at every pixel by running the full Newton solve from Chapter 3. Drag τ and watch the boundary breathe: small τ makes it wiggle tightly around individual points; large τ straightens it toward a single line. Find the τ where it cleanly traces the curve.

Play with it until the lesson clicks: at τ ≈ 0.12 the boundary is a jagged, paranoid thing that loops around stray points (variance). At τ ≈ 2.5 it's nearly a straight diagonal that slices through the middle, getting the curve's ends wrong (bias). Somewhere around τ ≈ 0.4–0.6 it smoothly follows the true arc. That region — not too tight, not too loose — is the goal of every bias/variance trade-off you'll ever tune.

How do you actually pick τ?

You don't eyeball it in practice — you use cross-validation. Hold out part of the data, fit LWLR with several candidate τ values, and measure validation accuracy (or held-out log-likelihood) for each. The τ with the best validation score wins. The curve of "validation error vs. τ" is famously U-shaped: high on the left (tiny τ, overfit), high on the right (huge τ, underfit), with a minimum in the middle. Picking τ = the bottom of that U is the disciplined version of the eyeballing you just did.

Chapter 5: Cost, Connections & the Cheat Sheet

We've built the whole thing. Now the honest accounting: what does this power cost, where does LWLR sit in the family of methods, and what should you carry away?

The price of laziness: cost at query time

Ordinary logistic regression is parametric and eager: it does expensive work once (training), boils the entire dataset down to a fixed vector θ, then throws the data away. Prediction is a single dot product — lightning fast, and the model is tiny regardless of how much data trained it.

LWLR is the opposite: non-parametric and lazy. It does no training. It keeps the entire training set forever, because every prediction needs all of it. For each query, it computes m weights (one per training point), then runs ~6 Newton iterations, each of which builds and inverts a (d×d) Hessian where d is the feature dimension. So per query the cost is roughly O(m·d + d³) — and there's no amortization, because nothing is reused between queries.

Concretely: classify 10,000 new points against 50,000 training examples, and you run 10,000 independent Newton solves, each touching all 50,000 points. That's why LWLR shines on small-to-medium datasets with low feature dimension and curved boundaries, and becomes impractical at large scale. The Code Lab below paints its boundary by solving at every grid cell — you'll feel the cost as the few seconds it takes to run.

Where LWLR sits in the family

The deep connection: LWLR sits between ordinary logistic regression (its τ→∞ limit, a global straight line) and k-Nearest Neighbors (its τ→0 limit, a purely local vote). The Gaussian weight is a kernel — the same idea that powers kernel SVMs and kernel density estimation — but here it's used to re-weight examples for a local fit rather than to lift data into a high-dimensional space. And the locally-weighted trick isn't specific to classification: swap the logistic log-likelihood for squared error and you get locally-weighted linear regression (the original CS229 LWR), which curves a regression line the same way we just curved a classifier.

The cheat sheet

Related Gleams

· Logistic Regression & the Perceptron — the global classifier LWLR localizes; LWLR is this with τ→∞.
· Linear Regression & LMS — the regression cousin; apply the same weighting trick to get locally-weighted linear regression.
· Contrastive Learning / similarity — the Euclidean-distance kernel is a similarity measure, the same currency as embeddings & kNN.

Now scroll down. The Workbook drills the hand calculations — weights, a Newton step, the limits, the sign bug. Then the Code Lab hands you the real thing: edit τ, press Run, and watch the boundary you've been reasoning about paint itself.