Classical Machine Learning Algorithms Questions

Direct answer

Add polynomial terms (x, x^2, x^3, ...) or interaction terms (x1*x2) as new columns and fit ordinary linear regression on the expanded feature set. The model stays linear in its parameters, so it keeps the same fitting machinery and interpretability, but as you raise the degree the parameter count grows and, with a fixed number of data points, you can eventually have as many parameters as data points, at which point the model can memorize the training data and generalizes badly.

Structured elaboration

Why it still works as linear regression: linear regression only requires linearity in the parameters, not the raw inputs. Feeding it phi(x) = [1, x, x^2, ...] lets it fit curves while remaining ordinary linear regression under the hood.

Parameter growth: a degree-d polynomial on one feature adds d terms; with p original features and all pairwise interactions, the interaction count grows like O(p^2), and a full degree-d expansion across p features grows combinatorially.

Effect on bias and variance: low degree underfits (high bias, misses real curvature) but has low variance. Higher degree lowers bias but variance grows quickly, because more parameters are being estimated from the same amount of data, and the added polynomial columns are highly correlated with each other (x and x^2 move together for x > 0), which is the same instability mechanism as ordinary multicollinearity.

Controls:

• Cross-validate the degree instead of picking it by training error.
• Standardize or use an orthogonal polynomial basis to reduce numerical correlation between terms.
• Apply ridge or lasso on top of the expanded features so unnecessary high-degree terms shrink toward zero.
• Prefer splines when only certain regions of x are nonlinear, since local basis functions don't oscillate far from the data the way a single high-degree global polynomial can. (This oscillation near the edges of the fitted range, worse at higher degree, is known as Runge's phenomenon.)

Worked example

Fit y from x with only n = 3 points: x = [0, 1, 2], y = [1, 3, 2].

A degree-1 fit (a line, 2 parameters) via least squares gives intercept 1.5 and slope 0.5:

$\hat y = 1.5 + 0.5x$

giving predictions [1.5, 2.0, 2.5] and a sum of squared errors of 1.5, an honest approximation that doesn't pass through every point.

A degree-2 fit (a parabola, 3 parameters, exactly matching the 3 data points) solves exactly:

$\hat y = 1 + 3.5x - 1.5x^2$

giving predictions [1.0, 3.0, 2.0], a perfect match, sum of squared errors = 0. That zero error is not evidence of a better model, it's evidence that zero degrees of freedom are left: with as many parameters as data points, the parabola threads exactly through every point, including whatever noise those points happen to contain, and there is no held-out data left to check whether it generalizes. In practice this parabola would swing wildly if evaluated between or beyond the three fitted points.

Trade-offs & pitfalls

Chasing training R^2 by raising the degree without cross-validation is the classic trap this example illustrates directly. Interaction terms without polynomial terms should still be checked for multicollinearity using VIF (variance inflation factor: how much a term's coefficient variance is inflated by its correlation with the other predictors, with values above roughly 5-10 flagged as concerning), since x1*x2 correlates with both x1 and x2 individually. Extrapolating a polynomial fit outside the training range is especially dangerous because polynomial curvature can diverge quickly. High-degree polynomial design matrices are also numerically unstable to compute directly (they resemble ill-conditioned Vandermonde matrices); centering and scaling x, or using an orthogonal polynomial basis, mitigates this on top of the statistical fix.

Direct answer

Nested cross-validation is two CV loops in one: an outer loop that estimates how well the whole modeling pipeline generalizes, and an inner loop, run entirely inside each outer training fold, that picks hyperparameters or features. You need it whenever the same data is used both to tune the model and to report its performance, because tuning on the same data you evaluate on leaks information and inflates the reported score.

Structured elaboration

Why plain k-fold CV is not enough here. If you run k-fold CV once to pick the best hyperparameters (by, say, taking the config with the highest mean CV score) and then report that same mean CV score as your generalization estimate, you have used the test folds to make a selection decision, so the reported number is optimistically biased. The gap grows with the size of the hyperparameter search space: the more configurations you try, the more likely one of them fits the validation folds' noise, not just signal.

Outer/inner structure.

• Outer loop ($K_\text{outer}$ folds): each outer fold is held out entirely and touched only once, at the very end, purely for scoring. It never influences any modeling decision.
• Inner loop ($K_\text{inner}$ folds, run on the outer-training portion only): performs the hyperparameter search or feature selection, using its own train/validation splits. Whatever it selects (say, the config with the best mean inner-validation score) is refit on the full outer-training set.
• The refit model is then scored once on the untouched outer-test fold. Averaging that score across all outer folds gives an unbiased estimate of how well "the pipeline, including its tuning procedure" generalizes.
• Any preprocessing that looks at the target (target encoding, feature selection by correlation with $y$, scaling parameters) must be fit only on the current inner-training data, never on the inner-validation or outer-test data, or the same leakage reappears one level down.

Computational cost. Every hyperparameter configuration gets fit $K_\text{inner}$ times per outer fold just to be scored, then the winner gets refit once more on the full outer-training set. Total model fits:

$$\text{total fits} = K_\text{outer} \times (G \times K_\text{inner} + 1)$$

where $G$ is the number of hyperparameter configurations evaluated. This is roughly $K_\text{inner}$ times more expensive than a single k-fold search (precisely $K_\text{inner} + 1/G$), which is why nested CV is usually reserved for the final reported generalization number rather than for every exploratory tuning pass.

Worked example

Suppose $K_\text{outer} = 5$, $K_\text{inner} = 3$, and a grid search over $G = 10$ hyperparameter configurations.

$$\text{total fits} = 5 \times (10 \times 3 + 1) = 5 \times 31 = 155$$

Compare that to a single (non-nested) k-fold grid search used just to pick hyperparameters, at $G \times K = 10 \times 5 = 50$ fits, with no separately reported unbiased generalization estimate. Nested CV costs about $155 / 50 \approx 3.1\times$ more fits here, and the ratio grows directly with $K_\text{inner}$: doubling $K_\text{inner}$ to 6 gives $5 \times (10 \times 6 + 1) = 305$ fits, roughly double, because the inner search dominates the total.

Trade-offs & pitfalls

• Nested CV answers "how good is this tuning procedure, on average," not "what hyperparameters should I ship." The winning configuration can differ across outer folds; for deployment, refit once on the full dataset using the inner-loop procedure (or the single most frequently selected configuration) after nested CV has validated that the procedure is trustworthy.
• Under a tight compute budget, replace grid search with randomized or Bayesian search in the inner loop to shrink $G$ without shrinking the search space explored, or reduce $K_\text{inner}$ to 3 (a common compromise, since the inner loop only needs to rank configurations relatively, not report a final number).
• Skipping the inner loop and just using a single train/val split inside each outer fold is a cheaper approximation, but reintroduces some tuning variance into the outer score; it is a reasonable trade-off for very expensive models, not for cheap ones where full nested CV is affordable.
• The single most common implementation bug: fitting a preprocessing step (scaler, target encoder, feature selector) once on the whole dataset before either loop starts. That silently defeats the entire point of nesting.

Direct answer

For 10M rows, 200 mixed-type features, under 100ms inference latency, under 500MB memory, on CPU, with weekly retraining, I'd shortlist a gradient-boosted tree ensemble (LightGBM or CatBoost) as the primary candidate, a regularized linear model with hashed features as a low-risk fallback, and a small distilled neural net only if the GBM can't hit the latency or accuracy target on its own. The final pick is the GBM, with an explicit distillation step held in reserve, because it offers the best combination of tabular accuracy, controllable model size, and weekly-retrain-friendly training cost.

Structured elaboration

Shortlist and configuration.

How the constraints drive the choice. At 10M rows and 200 features, a GBM trains in a bounded, well-understood amount of compute that fits a weekly cadence without heroics. The latency and memory ceilings are what push the tuning direction: instead of a large, deep, unconstrained GBM, cap num_leaves and n_estimators to a size that's been validated to serve under 100ms and 500MB on the target CPU, and treat any accuracy gap from that cap as the cost of the production constraint, not something to fight by growing the model back out. If the capped GBM still doesn't clear the accuracy bar, distillation lets you train a larger, more accurate teacher offline (where latency/memory don't matter) and compress it into a serving-sized student that inherits most of the teacher's accuracy.

Why not the linear model or the neural net as the primary pick. The linear model is the safest bet on latency and memory, but churn typically has real feature interactions (tenure × usage pattern, plan type × support-ticket count) that a purely linear model has to have hand-engineered as crosses; that's more design overhead than letting a GBM learn interactions natively. A small neural net with embeddings can match or exceed a GBM's accuracy on high-cardinality categoricals, but hitting a hard CPU latency target with a neural net requires deliberate quantization and graph optimization work that a GBM gets closer to by default, and weekly retraining of a neural net is a heavier operational commitment than retraining a GBM.

Worked example

Assume a validated per-tree inference cost budget: on the target CPU, a single decision path through one tree of depth 10 costs on the order of 10 comparisons. For a GBM with 400 trees, worst-case inference touches $400 \times 10 = 4{,}000$ comparisons per prediction, well within a 100ms budget for a single row on any modern CPU, since comparisons are sub-microsecond operations; the actual bottleneck in practice is typically feature preprocessing and I/O, not the tree traversal itself, which is why the latency budget should be validated end-to-end (feature lookup, preprocessing, model inference) rather than assumed from tree count alone. For memory, num_leaves=128 with max_depth=10 across 400 trees gives at most $400 \times 128 = 51{,}200$ leaf nodes; storing a leaf value plus a small number of split conditions per node is a few bytes each, putting total model size on the order of single-digit megabytes, far under the 500MB ceiling, so a capped GBM has considerable headroom before distillation is even needed. This arithmetic is meant to sanity-check that the shortlist is plausible against the stated budget, not a substitute for profiling the actual serving path before shipping.

Trade-offs and pitfalls

• Capping num_leaves and n_estimators trades some accuracy for a guaranteed latency/memory envelope; that trade should be validated against a real accuracy metric (AUC, log loss) on a held-out set, not assumed acceptable.
• Feature hashing for the linear fallback introduces hash collisions, a small but real accuracy cost that grows as the hash space shrinks relative to the true cardinality; size the hash space generously if this path is used.
• A neural net's headline accuracy numbers from research benchmarks often assume GPU serving; deploying under a strict CPU latency budget requires quantization and can erode part of that advantage, a gap that's easy to underestimate if you only benchmark training-time accuracy.
• The common wrong turn is picking the model family that scores best in an offline notebook without accounting for the production constraints at all; a marginally more accurate model that blows the memory or latency budget is not a valid production candidate, whatever its offline metric says.
• Weekly retraining means the pipeline needs to be robust to feature drift between the tabular schema over 10M rows; monitor for categorical cardinality growth (new customer segments, new plan types) since that directly changes both accuracy and, for the linear+hashing path, collision rates.

Direct answer

PCA is a closed-form, deterministic linear projection that is fast to fit, easy to interpret via component loadings, and provably optimal among all linear rank-k reconstructions. An autoencoder is a trained nonlinear model that can capture curved (nonlinear) structure in the data and can beat PCA's reconstruction error when the data actually lives on a nonlinear manifold, but it costs more to train, tune, and maintain, and its latent dimensions are not directly interpretable. The extra complexity pays off specifically when the data has real nonlinear structure that a linear subspace cannot capture and you have enough data and infrastructure to train and monitor a neural network reliably; otherwise PCA is the better engineering default.

Structured elaboration

Why PCA is provably optimal for the linear case. The Eckart-Young theorem states that among all rank-$k$ approximations $\hat{X}$ of a centered matrix $X$, the one built from PCA's top $k$ components minimizes the reconstruction error $\|X - \hat{X}\|_F^2$ (the Frobenius norm squared, written $\|\cdot\|_F^2$, is just the sum of every entry of a matrix squared, so this is the total squared reconstruction error added up across every point and every feature). That is a hard ceiling: no other linear method can beat PCA's reconstruction error at a given $k$. It is also a known result (Baldi & Hornik showed this in 1989) that a linear autoencoder, meaning one with no nonlinear activation functions at all, with a bottleneck of width $k$, trained to minimize squared reconstruction error, converges to the same subspace PCA finds; the citation is there so you can look up the proof, not as a name to memorize. So a linear autoencoder is not a meaningfully different tool from PCA; the real comparison is always PCA versus a genuinely nonlinear autoencoder.

When the extra complexity pays off:

• The data plausibly lies on a nonlinear manifold (natural images, audio spectrograms, embeddings from another nonlinear process) where a linear subspace is a poor fit no matter how many components you keep.
• You have enough training data to fit the nonlinear model without it overfitting the reconstruction task, and enough infrastructure (GPU training, experiment tracking, drift monitoring) to operate it responsibly.
• The measured gain in downstream task performance (not just lower reconstruction loss) justifies the added training and serving cost; a lower reconstruction error does not automatically translate into a better feature for whatever comes after it.

When PCA is the better engineering choice:

• The relationship between features is plausibly linear, or you have no strong reason to believe otherwise.
• You need determinism, fast iteration, or a lightweight, easily-reproduced pipeline (PCA has no training instability and no random initialization to control for).
• You need to explain the reduced features to a non-technical stakeholder via loadings.
• Sample size is limited, since a nonlinear model with many parameters is more prone to overfitting in that regime than a closed-form linear method.

Worked example

Reuse the small 2D example from the PCA definition to make the "provably optimal reconstruction" claim concrete rather than asserted. Four points $(1,2), (3,3), (5,6), (7,7)$, centered mean $(4, 4.5)$, give covariance eigenvalues $\lambda_1 \approx 12.187$ and $\lambda_2 \approx 0.146$ (derived above). Eckart-Young says the sum-of-squared reconstruction error from keeping only the first component equals exactly the discarded variance scaled back up by $(n-1)$:

$$\text{SSE}_{k=1} = \lambda_2 \cdot (n-1) \approx 0.146 \times 3 = 0.438$$

This can be checked directly: projecting the four points onto the first principal component and reconstructing gives a total squared reconstruction error of about 0.438, matching the formula exactly. No linear method, however constructed, can do better than this at $k=1$ on this dataset; only a nonlinear model exploiting information beyond a straight-line fit could, and here there is nothing nonlinear to exploit since the points already lie almost on a line, which is why an autoencoder would not help on data shaped like this.

Trade-offs & pitfalls

• Comparing PCA and an autoencoder purely on reconstruction loss is a common trap; a nonlinear model can always fit the training reconstruction task better with enough capacity, but that does not mean the learned latent features are better for whatever downstream task actually matters. Compare on the downstream metric.
• Starting a project with a full autoencoder before establishing a PCA baseline makes it easy to miss that a much cheaper method already gets most of the value; treat PCA as the baseline to beat, not a fallback.
• Autoencoder latent spaces can drift as the input distribution shifts in ways that are harder to detect than PCA's explained-variance diagnostics, since there is no closed-form "explained variance" analog without extra instrumentation.

Direct answer

A 0.02 mean-score edge for Model B is not meaningful once you account for its much larger fold-to-fold variability: its performance swings enough that the true difference between A and B could easily be zero, or could even favor A on a bad day. For a production decision, I would lean toward Model A unless I can explain and control the source of Model B's instability.

Structured elaboration

Read the numbers as a distribution, not a point estimate. A cross-validation score is itself a random variable, since it depends on which folds happened to land where. A mean of 0.78 with std 0.01 says "consistently around 0.78 no matter how the data is split." A mean of 0.80 with std 0.07 says "somewhere between roughly 0.7 and 0.9 depending on the split," a seven-fold larger spread. The higher mean could reflect a genuinely better model, or it could reflect one or two folds where Model B got lucky (e.g., an easy subset of data, or a fold correlated with a spurious feature it latched onto).

Turn the spread into an interval. With $k$ folds, the standard error of the mean CV score is approximately $\text{SE} = \text{std}/\sqrt{k}$ (treating fold scores as roughly independent, which is an approximation since folds share the same training data, but a standard one for a sanity check). Assuming the common default of $k=5$ folds:

$$\begin{aligned} \text{SE}_A &= 0.01/\sqrt{5} \approx 0.0045, \quad 95\%\ \text{CI}_A \approx 0.78 \pm 2(0.0045) = [0.771,\ 0.789] \\\\ \text{SE}_B &= 0.07/\sqrt{5} \approx 0.0313, \quad 95\%\ \text{CI}_B \approx 0.80 \pm 2(0.0313) = [0.737,\ 0.863] \end{aligned}$$

Model A's interval sits almost entirely inside Model B's, so the two are statistically indistinguishable on this evidence; the 0.02 gap is well within B's own noise band.

What drives high variance, and what to check. Common causes: B is more sensitive to which examples land in train vs. validation (small effective sample size per fold, or a few high-leverage outliers), B is overfitting on some folds (deeper trees, less regularization), or there is a subtle leakage or preprocessing bug that helps on some folds and not others. Before trusting B, I would inspect the per-fold scores directly rather than just the summary statistics, and check whether the bad folds correlate with a specific data slice (time period, customer segment, source).

Worked example

See the interval computation above, it is the worked example: given the assumed $k=5$, A's approximate 95% CI is $[0.771, 0.789]$ and B's is $[0.737, 0.863]$. The intersection of the two intervals is $[0.771, 0.789]$, about 1.8 percentage points wide, and it sits entirely inside B's interval, versus a raw mean gap of only 2 points. That overlap is the concrete reason to not treat B as the winner on mean score alone.

Trade-offs & pitfalls

• Production risk is not just about the expected metric, it is about the worst realistic case. A model whose CV std is 7x another's is more likely to have a bad month on live traffic that drifts even slightly from the training distribution.
• Don't default to A blindly either: if B's instability is diagnosed and traceable to a fixable cause (e.g., one noisy fold from a known bad data batch), fixing that cause could make B the better choice with a tightened std.
• A paired comparison (same folds, same splits, difference-per-fold) is more powerful than comparing two independently-summarized mean/std pairs, since it removes fold-to-fold difficulty variation common to both models; if available, prefer that over the interval-overlap heuristic used above.
• Calibration matters as much as discrimination for production: a model with unstable CV performance often also has unstable predicted probabilities, which matters if downstream thresholds or business rules depend on calibrated scores.