R18 · Week 18 Recall & Drill

Assessment scope

This revision joins probability estimation to decisions, then connects penalties, learning curves, greedy trees and ensembles. A classifier's probability model and its action threshold are different objects. The NumPy labs make that distinction measurable without claiming production calibration or a universal winner among estimators.

Sessions covered

• S086 — Logistic Regression — Sigmoid, Cross-Entropy, from Scratch
• S087 — Regularization — L1, L2, Elastic Net
• S088 — Bias–Variance Trade-off & Learning Curves
• S089 — Decision Trees — Gini, Entropy, Splits
• S090 — Random Forest & Bagging

90-min structure

Use the budget as pacing, not as a guarantee that all extensions fit one sitting.

Blank-page reconstruction · 30 min

S086 · Logistic Regression

1. Write the sigmoid and explain the modeling assumption, not just its range.
2. Derive cross-entropy from Bernoulli likelihood.
3. When is a precision-recall view especially useful, and when is 0.5 optimal?

Solutions. Set z = x.T @ w + b and assume the log odds are linear: log(p/(1-p)) = z. Solving gives p = 1/(1+exp(-z)). Its (0,1) range permits a Bernoulli parameter, but other links also map into that range; the log-odds assumption is the specific reason for this model. For independent observations, likelihood is the product of p_i**y_i * (1-p_i)**(1-y_i). Taking negative logs and averaging yields

The derivative with respect to each logit is (p_i-y_i)/n. For fixed features this gives a convex unregularized logistic objective; perfect separation can mean no finite minimizer. Squared probability error is a legitimate Brier scoring rule, but composing it with a sigmoid is generally nonconvex in weights and introduces an additional saturation factor in the gradient. It is not meaningless merely because the task is classification.

For a calibrated deployment posterior p, false-positive cost Cfp and false-negative cost Cfn, positive action costs Cfp*(1-p) and negative action costs Cfn*p. Choose positive when p >= Cfp/(Cfp+Cfn) (ties are equal cost; this lesson chooses positive). Equal costs imply 0.5 regardless of prevalence; priors are already inside p. A balanced dataset is not an extra requirement. Arbitrary sigmoid-transformed scores are not automatically calibrated posteriors. Select thresholds on validation data for cost, recall or capacity, then evaluate once on test data. Under prior/calibration shift, reassess the policy.

ROC plots TPR against FPR; PR plots precision against recall. At rare prevalence even a small FPR can create many false alerts, so PR and absolute counts often clarify an alerting task. Neither curve specifies deployment cost by itself. Precision can fluctuate as a finite-sample threshold moves; recall is nonincreasing as a score >= threshold rule becomes stricter.

S087 · Regularization

1. Write ridge, lasso and elastic-net objectives with compatible units.
2. Why does L1 encourage zeros while L2 generally shrinks?
3. How should scaling and penalty strength be chosen?

Solutions. With centered data and an unpenalized intercept handled separately, use squared loss ||Xw-y||²/(2n). Add lambda*||w||²/2 for ridge, lambda*||w||_1 for lasso, or lambda*(alpha*||w||_1 + (1-alpha)*||w||²/2) for elastic net. Different libraries normalize these terms differently; equal displayed lambdas are not automatically equal regularization strengths.

L1's constraint diamond has corners on coordinate axes; its subgradient at zero is an interval, allowing an optimum exactly at zero. In the orthogonal design case, each coefficient is soft-thresholded. L2 is smooth and ordinarily shrinks without selecting, but can yield zero for a coordinate with zero target correlation—“never exactly zero” is false. Correlated features can make lasso selection unstable; elastic net's L2 part can encourage sharing while retaining some sparsity. No penalty certifies causal feature relevance.

Coefficient units matter. Rescaling x to 1000*x divides its equivalent coefficient by 1000, changing an L1 penalty by 1000 and an L2 penalty by a million. Standardizing using training-only means/scales is a common way to make penalties comparable, not a universal requirement when physical units or deliberately chosen priors should carry meaning. Tune lambda and mixing strength inside validation/CV, fitting the scaler separately in each training fold. Compare against an unregularized baseline and inspect both accuracy and stability.

S088 · Bias–Variance

1. State the squared-error decomposition and its assumptions.
2. Diagnose a large train/validation gap and name three interventions.
3. Diagnose high, close errors and name three different interventions.

Solutions. For y=f(x)+epsilon, zero conditional noise mean and variance sigma²(x), and randomness over training sets D independent of the new test noise,

The cross terms vanish by those zero-mean assumptions. This is not the same decomposition for arbitrary classification loss. A learning curve estimates training and validation loss as training size increases under a fixed protocol; it does not measure the three terms directly.

Low train error and high validation error suggest variance: try more representative data, stronger regularization, or less capacity (depth/features). First exclude leakage, train/eval preprocessing mismatch, distribution shift and a nonrepresentative validation set. Both errors high and close suggest limited capacity or signal, excessive regularization, insufficient optimization or noisy labels. Try richer capacity, better features, or weaker regularization/longer verified optimization. More data cannot remove a fixed model family's approximation bias, but may still reduce estimation variance, change coverage or improve feature discovery. “More data does nothing” and “the gap is the diagnosis” overstate what a pair of curves can establish.

S089 · Decision Trees

1. Define Gini or entropy and derive a weighted split score.
2. Describe the greedy split loop.
3. Name controls for overfitting and interpret importance carefully.

Solutions. Gini is 1-sum(p_k²); entropy is -sum(p_k*log(p_k)) with zero terms defined by continuity. A pure node has zero impurity. For a candidate split minimize (n_left/n)*H(left)+(n_right/n)*H(right), equivalently maximize the parent impurity reduction. Enumerate permitted features/thresholds, evaluate valid children, select the best local reduction and recurse until a stop rule; greedy local choices need not give a globally optimal tree.

A six-row node with three positives and three negatives has Gini 0.5. A split into [0,0,0] and [1,1,1] gives zero weighted impurity and gain 0.5. A split into [0,0,1] and [0,1,1] has weighted Gini 4/9 and gain 1/18. Very deep trees can isolate noisy cases. Limit max depth, minimum leaf size, minimum gain, feature availability or apply cost-complexity pruning, selecting controls on validation data.

Impurity importance reflects training reductions and favors features offering many candidate splits, including high-cardinality random IDs. Held-out permutation importance measures score degradation after disrupting a feature and avoids that split-search mechanism, but correlated substitutes can make each individually look unimportant; unrealistic shuffled combinations are another caveat. Group correlated features where justified, repeat permutations, and validate a proposed removal by refitting. Neither importance is causal attribution.

S090 · Random Forest & Bagging

1. Explain bootstrap aggregation and the variance it can reduce.
2. Compute the expected unique-row fraction and use of out-of-bag rows.
3. What does per-split feature subsampling add?

Solutions. Fit members on size-n bootstrap samples (sampling rows with replacement), then average predictions. A particular row is absent with probability (1-1/n)**n, approaching exp(-1); expected distinct fraction approaches 0.632, not an exact fraction in every sample. Out-of-bag predictions for a row use only trees whose bootstrap excluded it. Global learned preprocessing can compromise that holdout boundary; out-of-bag scoring is not a free final test after extensive tuning.

For M equally variable predictors with common pairwise correlation rho, the variance of their mean is sigma²*(rho+(1-rho)/M), obtained by summing M variances and M(M-1) covariances and dividing by M². Correlation limits the benefit, but positive correlation does not make bagging worthless. Restricting candidate features at each split can decorrelate trees at the cost of weakening individual members. The trade must be measured; forcing a stump away from the only useful feature can reduce accuracy even while correlation falls. A real forest repeats this choice at every node, whereas the lab deliberately uses one-split trees.

Hands-on drill · 30 min

Run the Python fences in order. The programs share imports but each data fixture has an explicit seed. These are small numerical experiments, not a random-forest library benchmark.

Step 1 — the threshold is a business decision (8 min)

import numpy as np
from fractions import Fraction
probabilities=[Fraction(1,100),Fraction(1,10),Fraction(2,5),Fraction(4,5)]
for fp_cost,fn_cost in [(1,1),(1,4),(4,1)]:
    threshold=Fraction(fp_cost,fp_cost+fn_cost)
    decisions=[p>=threshold for p in probabilities]
    oracle=[fp_cost*(1-p)<=fn_cost*p for p in probabilities]
    assert decisions==oracle
    print("posterior policy",fp_cost,fn_cost,"threshold",threshold,"positive",decisions)
# Empirical validation scores need not be calibrated. Do not plug them into the posterior formula.
scores=np.array([.95,.85,.8,.7,.6,.4,.3,.2,.1,.05])
y=np.array([1,0,1,0,0,1,0,0,0,0])
def confusion(threshold):
    pred=scores>=threshold
    return tuple(int(np.sum(mask)) for mask in [pred&(y==1),pred&(y==0),~pred&(y==1),~pred&(y==0)])
rows=[]
for threshold in [0.,.3,.4,.5,.8,1.]:
    tp,fp,fn,tn=confusion(threshold)
    precision=tp/(tp+fp) if tp+fp else None
    recall=tp/(tp+fn)
    cost=fp+4*fn
    rows.append((cost,threshold))
    print(threshold,(tp,fp,fn,tn),"precision",precision,"recall",recall,"cost",cost)
assert confusion(.5)==(2,3,1,4)
assert min(rows)==(3,.4)
assert np.mean(y==0)==.7
print("best candidate validation threshold",min(rows)[1])

At 0.5 the cost is 7; at 0.4 it is 3 because the missed positive is recovered without another false positive. Always negative has 70% accuracy yet cost 12. This fixture does not prove always-negative accuracy exceeds every classifier's accuracy; at 0.4 the accuracy is also 70%, and the cost differs sharply. A real selection process freezes the chosen threshold before a separate test evaluation and accounts for sampling uncertainty and capacity constraints.

Step 2 — shrink versus select (8 min)

rng=np.random.default_rng(7)
n,d=120,12
X=rng.normal(size=(n,d)); X[:,5]=X[:,3]+rng.normal(scale=.01,size=n)
w_true=np.zeros(d); w_true[[0,3,9]]=[2.5,-1.8,1.1]
yreg=X@w_true+rng.normal(scale=.5,size=n)
Xs=(X-X.mean(0))/X.std(0); yc=yreg-yreg.mean()
def ridge(lam):
    return np.linalg.solve(Xs.T@Xs/n+lam*np.eye(d),Xs.T@yc/n)
def lasso(lam,steps=6000):
    # Step <= inverse Lipschitz constant of squared-loss gradient.
    rate=1/np.linalg.norm(Xs,2)**2*n
    w=np.zeros(d)
    for _ in range(steps):
        z=w-rate*(Xs.T@(Xs@w-yc)/n)
        w=np.sign(z)*np.maximum(abs(z)-rate*lam,0.)
    return w
for lam in [.01,.1,1.,5.]:
    r,l=ridge(lam),lasso(lam)
    residual=Xs.T@(Xs@l-yc)/n
    active=abs(l)>1e-7
    assert np.max(abs(residual[active]+lam*np.sign(l[active])),initial=0)<.005
    assert np.max(abs(residual[~active]),initial=0)<=lam+.005
    assert np.allclose(Xs.T@(Xs@r-yc)/n+lam*r,0,atol=1e-10)
    print("lambda",lam,"ridge near-zero",int(np.sum(abs(r)<1e-8)),"lasso active",np.flatnonzero(active).tolist())
# Exact orthogonal oracle: X.T X/n = I, X.T y/n = c.
c=np.array([2.,-.5,0.]); lam=.75
ridge_oracle=c/(1+lam); lasso_oracle=np.sign(c)*np.maximum(abs(c)-lam,0)
assert np.array_equal(lasso_oracle,[1.25,0.,0.])
assert ridge_oracle[2]==0  # ridge can have an exact zero
print("orthogonal ridge/lasso",ridge_oracle,lasso_oracle)

Here ridge and lasso use the same averaged loss normalization; the original formulas did not. The stationarity/subgradient checks assess optimization, not recovery of a true sparse causal model. Feature 5 is a near-duplicate of 3, so interpretation should consider the pair, not announce one uniquely real feature from one run. Means/scales use this fitting fixture only; cross-validation would refit them inside each fold.

Step 3 — learning curves as a diagnosis (7 min)

rng=np.random.default_rng(2)
x=rng.uniform(-1,1,1400)
ycurve=np.sin(5*x)+.8*x*x+rng.normal(scale=.2,size=len(x))
def design(values,degree):
    return np.vander(values,N=degree+1,increasing=True)
def curve(degree):
    result=[]
    for m in [20,40,100,300,900]:
        train=np.arange(m); val=np.arange(1000,1400)
        assert set(train).isdisjoint(val)
        A=design(x[train],degree)
        w=np.linalg.lstsq(A,ycurve[train],rcond=None)[0]
        rmse=lambda rows:float(np.sqrt(np.mean((design(x[rows],degree)@w-ycurve[rows])**2)))
        result.append((m,rmse(train),rmse(val)))
    return result
for degree in [1,12]:
    print("degree",degree)
    for row in curve(degree): print(row)
# A transparent decomposition at one x: predictors 0,2; true f=1; noise -1,+1.
predictors=[0.,2.]; noises=[-1.,1.]
observed=np.mean([(1+noise-pred)**2 for pred in predictors for noise in noises])
bias2=(np.mean(predictors)-1)**2; variance=np.var(predictors); noisevar=np.var(noises)
assert observed==bias2+variance+noisevar==2.
print("decomposition",bias2,variance,noisevar,observed)

The curves report actual losses, not assertions that every row must improve monotonically. A degree-one fit cannot represent the sine shape; the degree-twelve model can fit more structure but its small-data coefficients can be unstable. Fixed validation rows make comparisons meaningful, while repeated seeds/splits are needed to quantify uncertainty. Looking at optimization residuals and label noise prevents mistaking all high close errors for capacity bias.

Step 4 — decorrelation is the mechanism (7 min)

rng=np.random.default_rng(11)
Xf=rng.normal(size=(500,8)); yf=(3*Xf[:,0]+.5*Xf[:,1]+rng.normal(scale=.7,size=500)>0).astype(int)
Xe=rng.normal(size=(200,8)); ye=(3*Xe[:,0]+.5*Xe[:,1]+rng.normal(scale=.7,size=200)>0).astype(int)
def gini(labels):
    p=float(np.mean(labels)); return 2*p*(1-p)
def stump(A,b,features):
    best=None
    for j in sorted(features):
        for t in np.unique(np.quantile(A[:,j],[.25,.5,.75])):
            left=A[:,j]<=t
            if not left.any() or left.all(): continue
            impurity=left.mean()*gini(b[left])+(~left).mean()*gini(b[~left])
            record=(impurity,int(j),float(t),float(b[left].mean()),float(b[~left].mean()))
            if best is None or record[:3]<best[:3]:best=record
    if best is None:return (None,0.,float(b.mean()),float(b.mean()))
    return best[1:]
def predict_stump(model,A):
    j,t,left,right=model
    return np.full(len(A),left) if j is None else np.where(A[:,j]<=t,left,right)
def forest(mtry):
    rng=np.random.default_rng(99)  # same seed for reproducible comparison
    predictions=[]; roots=[]
    for _ in range(32):
        idx=rng.integers(0,len(yf),len(yf))
        features=rng.choice(Xf.shape[1],mtry,replace=False)
        model=stump(Xf[idx],yf[idx],features)
        roots.append(model[0]); predictions.append(predict_stump(model,Xe))
    P=np.array(predictions)
    usable=P[np.std(P,axis=1)>0]
    corr=np.corrcoef(usable); off=corr[np.triu_indices(len(usable),1)]
    return roots,P,float(np.mean(off)) if len(off) else None
for mtry in [8,3]:
    roots,P,corr=forest(mtry)
    accuracy=float(np.mean((P.mean(0)>=.5)==ye))
    print("mtry",mtry,"root0",roots.count(0),"mean probability correlation",corr,"held-out accuracy",accuracy)
assert gini(np.array([0,0,0,1,1,1]))==.5
assert stump(np.array([[0.],[1.],[2.],[3.]]),np.array([0,0,1,1]),[0])[0]==0
assert np.array_equal(predict_stump((0,1.5,0.,1.),np.array([[0.],[3.]])),[0.,1.])
print("bootstrap expected unique fraction n=500",1-(1-1/500)**500)

These are predictions from learned leaf probabilities, not left/right membership indicators mislabeled as predictions. Both ensembles are evaluated on independent synthetic rows. Report accuracy alongside correlation: a lower correlation does not alone prove a better classifier. The finite constant-output fallback is explicit; a full forest would grow deeper trees and subsample features separately at each split.

What was measured? The printed correlation varies the held-out input row while holding each fitted stump fixed. The variance formula in S090 instead describes randomness of predictors (for example, over training samples) at a fixed input under its equal-variance/equal-correlation assumptions. Prediction correlation across these 200 rows is a diversity diagnostic, not a direct estimate of that population error covariance or the forest's variance reduction. Shared signal can make two accurate predictors strongly correlated; independently noisy predictors can have low correlation and poor accuracy.

The identical seed makes each forest(mtry) call reproducible, but does not pair every bootstrap across the two settings: drawing different-sized feature subsets consumes the RNG stream differently before the next row sample. For a controlled mtry comparison, pre-generate one bootstrap index array per tree and reuse it across settings, with a separate feature-choice RNG; repeat the paired experiment across seeds and report held-out score uncertainty. The present unpaired fixture remains a valid illustration, not an isolated causal estimate of changing mtry. Finally, the finite-n expected unique fraction is 1-(1-1/n)**n: at n=2 the four equally likely ordered bootstrap samples contain 1, 2, 2 and 1 distinct rows, averaging 1.5/2=0.75, not 0.632. The limiting 63.2% rule is neither a finite-n identity nor a promise for one realized sample.

Answer constraints and corrections

Misconception: “Averaging cancels mistakes, so bootstrapping is enough.” Averaging reduces variance to the extent allowed by covariance; bootstrapping alone can help, and feature subsampling offers another diversity/strength trade. Neither guarantees superior performance.

Quiz answers. (1) Cross-entropy is Bernoulli negative log-likelihood; Brier loss is valid but sigmoid composition changes optimization geometry. (2) A 0.5 threshold is optimal for equal costs and a calibrated deployment posterior, without a balanced-class assumption. (3) L1's subgradient admits zeros; L2 usually shrinks, and feature scaling makes penalty units intentional. (4) A gap suggests variance: data, regularization, capacity are candidate fixes; high close errors suggest bias/optimization/noise: capacity, features and weaker penalties are candidate fixes, not a diagnosis from two numbers. (5) Before dropping low-importance features, examine training-only impurity bias, correlated substitutes, permutation distribution shift and score uncertainty. Use repeated held-out grouped permutation and a refit/removal comparison; report predictive dependence, never causation.

Gap analysis + next week preview · 10 min

Retest the threshold rule on equal-cost posteriors with 1% prevalence, construct a ridge zero coefficient, or explain why randomizing away the only signal can reduce correlation and accuracy simultaneously. The next sessions cover boosting, metrics, preprocessing, imbalance and selection; they reuse this distinction between fitted model, decision policy and untouched evaluation.

Corrective source notes

Versioned primary references: scikit-learn 1.7 linear models, trees, ensembles, calibration, precision-recall thresholds, metrics and cross-validation, snapshots checked 2026-10-07. Decision-cost, covariance and orthogonal-penalty formulas are derived here and tested with independent finite examples. No scikit-learn training run, production cost calibration or population bias/variance estimate is claimed.

Additional mechanism references: permutation importance and correlated features, learning curves, and Stanford CS229 likelihood notes.

Part of the 6-month evergreen learning plan.