Classical Machine Learning Algorithms Questions

Direct answer

Training a random forest with T trees on n samples and d features costs roughly $O(T \cdot m \cdot n \log n)$, where m is the number of features sampled per split (typically $\sqrt{d}$ for classification or $d/3$ for regression) and $\log n$ comes from the depth of a balanced tree grown to roughly $n$ leaves. Max depth caps the depth term, feature subsampling shrinks m, and the splitting-criterion computation determines the constant hiding inside that "per node, per feature" cost. If it's too slow, the first levers to pull are depth, row/feature subsampling, and histogram binning, in that order.

Structured elaboration

Per-tree cost. Growing one tree touches every sample at every level of the tree. At a given depth level, the n samples are partitioned across the nodes at that level, so a full pass over all n samples happens once per level. At each node, the algorithm evaluates candidate splits over the m sampled features. If features are pre-sorted (once per tree, cost $O(d \, n\log n)$) or discretized into a fixed number of histogram bins, evaluating all thresholds for one feature at one level costs $O(n)$ (a single linear scan with running sums for the impurity/variance statistic), not $O(n^2)$.

$$\text{PerLevelCost} = O(m \cdot n)$$

With D levels (max depth):

$$\text{PerTreeCost} = O(m \cdot n \cdot D)$$

For a balanced tree grown until leaves are small, $D \approx \log_2 n$, giving the familiar single-tree bound $O(m\, n \log n)$. Summing over T independent trees:

$$\text{TotalCost} = O(T \cdot m \cdot n \log n)$$

Where each factor comes from.

Memory. Each tree needs its own bootstrap sample indices (O(n)), and up to O(n) leaf nodes (a leaf needs at least min_samples_leaf points, so leaf count is bounded by n, not $2^D$, once D is large). Storing T trees costs O(T·n) in the worst case; histogram bin edges for continuous features can be computed once and shared across all trees, which keeps that part of memory independent of T.

Worked example

Take n = 1,000,000 samples, d = 100 features, m = $\sqrt{100} = 10$ sampled features per split, T = 100 trees, and a balanced tree with $D \approx \log_2(1{,}000{,}000) \approx 20$ levels.

Per-tree split-finding cost: $m \cdot n \cdot D = 10 \times 1{,}000{,}000 \times 20 = 2\times10^{8}$ elementary operations (one pass over samples per feature per level).

Total across T = 100 trees: $100 \times 2\times10^{8} = 2\times10^{10}$ operations.

If depth is capped at D = 10 instead of 20 (heavier pre-pruning), the per-tree cost halves to $1\times10^{8}$ and the total drops to $1\times10^{10}$, a 2x reduction that tracks the D term exactly, since every other factor (T, m, n) is unchanged. This is why depth and min-samples-leaf are the highest-leverage knobs: the cost model is linear in D, and D is the term most within your control without changing the statistical setup.

Trade-offs and pitfalls

• Reducing T cuts cost linearly but increases ensemble variance (fewer, less-correlated votes to average over); it's the least surgical lever.
• Reducing max depth / increasing min_samples_leaf attacks the log n term directly and is usually the biggest win per unit of accuracy lost, since real datasets rarely need trees grown to full purity.
• Feature subsampling (m/d ratio) trades decorrelation between trees (good for ensemble variance) against per-split cost (smaller m is cheaper); shrinking m too far can bias individual trees.
• Histogram binning turns the split-evaluation step into a fixed cost per feature per node instead of scanning every unique value, which helps most when continuous features have high cardinality; it introduces a small approximation error from bucketing that should be validated against the exact-split baseline.
• Row subsampling below n (as opposed to full bootstrap resampling of size n) directly shrinks the n term but reduces how much data each tree sees, a real bias-variance trade, not a free lunch.
• A common mistake is treating "random forests parallelize across trees" as a complexity fix: it changes wall-clock time on multi-core hardware but does not change the total work or the memory footprint, so it doesn't help if the bottleneck is memory rather than CPU time.

Direct answer

Because a tree predicts by falling into a leaf and returning that leaf's training-data statistic, any input beyond the range of values the tree saw during training lands in the same boundary leaf as the most extreme training examples and gets the same flat prediction, no matter how far out it goes. This bites hardest in trending or growing quantities (time, price, size, demand) where production data routinely drifts past the training range. A common fix is a hybrid: a linear (or otherwise extrapolation-aware) component captures the global trend, and a tree ensemble models the nonlinear residual structure on top of it.

Structured elaboration

Where it bites in practice.

• Time-indexed or growth features: a model trained on 2023-2024 sales data has never seen "days since launch = 800"; if the true relationship keeps growing, the tree flatlines at the value of its last training bucket.
• Monotonic business quantities: square footage, years of experience, account age, order volume; any of these can exceed the training range as the business scales, and the tree silently under- or over-predicts by defaulting to boundary-leaf behavior instead of failing loudly.
• Distribution shift in production: even without a true trend, if the training sample happened not to cover the full feature range (a sampling gap, not real extrapolation), a tree behaves identically: flat prediction at the edge, with no signal that it's operating out of its comfort zone.

Why trees behave this way. A regression tree's prediction is the mean of the training targets in the leaf a query point falls into; splits are chosen only within the observed range of each feature. There is no notion of "beyond the last split point, keep going in the same direction," because a tree has no parametric form to project outward with. Gradient boosting inherits the same property leaf by leaf, even though the ensemble as a whole can produce a step-like approximation.

Hybrid linear + tree design. Model the target as $y \approx g(x) + h(x)$, where $g$ is a simple linear (or otherwise monotonic, extrapolation-safe) term capturing the global trend, and $h$ is a tree ensemble capturing nonlinear interactions and local structure. A practical two-stage recipe:

1. Fit $g$ (e.g., ordinary least squares, or a linear model with monotonic constraints on the trending feature) to the full training data.
2. Compute residuals $r_i = y_i - g(x_i)$.
3. Fit a tree ensemble to the residuals $r$, using the remaining features (interactions, nonlinearities the linear term misses).
4. At inference, predict $\hat y(x) = g(x) + h(x)$; the linear term keeps extrapolating sensibly outside the training range, while the tree term contributes whatever local correction it learned, which naturally saturates near its own training boundary rather than dominating out-of-range behavior.

An alternative that avoids a strict two-stage pipeline: feed the linear model's prediction in as an additional feature to the tree ensemble, letting the trees learn corrections on top of it; this is more flexible but requires care that the ensemble doesn't simply relearn (and then flatten) the linear signal itself.

Worked example

Take a toy pricing relationship $\text{price} = 100{,}000 + 200 \times \text{sqft}$, and suppose training data covers sqft in $[500, 2800]$. At the training boundary, $\text{price}(2800) = 100{,}000 + 200 \times 2800 = 660{,}000$; a pure tree's boundary leaf predicts this same $660{,}000$ value for any query at or beyond 2800 sqft, since that leaf's training examples top out there. Query a 5000 sqft property: the tree still outputs $660{,}000$, a flat prediction, while the true (and the linear component's) value is $100{,}000 + 200 \times 5000 = 1{,}100{,}000$, an underprediction of $1{,}100{,}000 - 660{,}000 = 440{,}000$, exactly the extrapolation gap the linear term is meant to close. In the hybrid, the linear term alone accounts for the full trend at 5000 sqft, and the tree-fitted residual term only needs to add whatever local nonlinear correction it learned near the edge of its own training range, not carry the entire extrapolation.

Trade-offs & pitfalls

• The hybrid only helps if the linear term's functional form is roughly right; if the true trend is itself nonlinear beyond the training range, a plain linear extrapolation can be just as wrong as the tree's flat one, only in a different direction.
• Fit the two stages with the same cross-validation discipline as any two-stage pipeline: compute residuals only from a model trained on the current fold's training data, never on data that includes the validation or test fold, or the residual-fitting step leaks information.
• Monotonic constraints (available natively in XGBoost and LightGBM) are a lighter-weight alternative to a full linear+tree hybrid when you only need the tree ensemble itself to keep moving in a known direction past the training range, without a separate linear model.
• In production, the real defense is detection, not just architecture: log when incoming features exceed the training range and flag those predictions as extrapolated, since even a hybrid model's confidence in that regime is lower than the metrics computed on in-range validation data suggest.

Direct answer

When missing fraud is much more expensive than a false alarm, optimize for recall while tracking precision as the cost of that recall, and pick the operating threshold by turning the business's cost asymmetry into an explicit expected-cost calculation rather than defaulting to 0.5. Precision-recall AUC (not ROC-AUC) is the right curve to compare models on, since it's sensitive to exactly the trade-off the business cares about.

Metrics and model selection

• Precision-recall curve, not ROC. With fraud rates typically well under 5%, ROC-AUC can look strong even for a mediocre model because the false-positive-rate denominator (all legitimate transactions) is huge. Precision and recall are both computed against the small positive class, so the PR curve directly shows the trade-off you're navigating.
• $F_\beta$ score with $\beta > 1$ if you want a single tuning number that weights recall above precision; $\beta$ can be derived from the cost ratio (shown below), rather than guessed.
• Report an operational number alongside the statistical one: at your chosen threshold, how many transactions per day get flagged for review, since that's a capacity constraint the fraud team actually lives with, not just a modeling detail.
• Calibrate probabilities before treating the model's output as a probability for cost calculations: a raw model score can rank transactions correctly (higher score means more likely fraud) while still being a bad probability estimate, so you fit a small correction on top of it, either Platt scaling (fits a logistic curve mapping raw scores to calibrated probabilities) or isotonic regression (fits a non-decreasing step function instead, more flexible but needs more data). An uncalibrated score can still rank well while being useless for "expected cost" math.

Choosing the operating threshold from cost

Define $C_{fn}$ as the cost of a missed fraud and $C_{fp}$ as the cost of investigating a false alarm. For a given threshold $t$, the expected cost on a validation set is:

$$\text{ExpectedCost}(t) = C_{fn} \cdot FN(t) + C_{fp} \cdot FP(t)$$

Sweep $t$ across the range of predicted scores, compute $FN(t)$ and $FP(t)$ at each point from the confusion matrix, and pick the $t^\ast$ that minimizes expected cost. If the business instead states a hard floor ("we must catch at least 90% of fraud"), find the lowest threshold that meets that recall and, among thresholds satisfying it, minimize false positives or expected cost. The two approaches usually point to a similar region of the curve; the cost-floor version is often easier to defend to stakeholders because it's phrased as their constraint, not a modeling choice.

Worked example: two thresholds, real costs

Take a validation set of 1,000 transactions with 20 true fraud cases (2%), and set $C_{fn} = 500$ (average loss per missed fraud) and $C_{fp} = 5$ (cost of a wasted investigation).

Threshold A (looser): 15 true positives, 50 false positives, 5 false negatives.

$$\text{recall} = \frac{15}{20} = 0.75, \qquad \text{precision} = \frac{15}{65} = 0.231$$ $$\text{ExpectedCost}_A = 500(5) + 5(50) = 2{,}500 + 250 = 2{,}750$$

Threshold B (stricter): 10 true positives, 10 false positives, 10 false negatives.

$$\text{recall} = \frac{10}{20} = 0.50, \qquad \text{precision} = \frac{10}{20} = 0.50$$ $$\text{ExpectedCost}_B = 500(10) + 5(10) = 5{,}000 + 50 = 5{,}050$$

Even though threshold B looks better by the usual "balanced" precision/recall instinct (both at 0.50), it is nearly twice as expensive in real terms, because at this cost ratio ($C_{fn}/C_{fp}=100$) each additional missed fraud is far more expensive than dozens of false alarms. Threshold A, the looser one, is the better operating point given these costs. This is the concrete argument for computing expected cost directly instead of eyeballing precision and recall.

Trade-offs and pitfalls

• Getting $C_{fn}$ and $C_{fp}$ from stakeholders is the actual hard part; a threshold derived from made-up costs is precise-looking but not more correct than a guess, so treat those numbers as an explicit, revisitable assumption, not a constant.
• Investigator capacity is a real constraint the expected-cost formula ignores: a threshold that's optimal on paper but floods the fraud team with more alerts than they can review in a day isn't actually deployable; incorporate a capacity constraint (e.g. review at most $k$ cases/day, rank by score) rather than a pure threshold.
• Fraud labels are frequently delayed (a chargeback shows up weeks later) or incomplete (undetected fraud is recorded as legitimate); training and evaluating against those labels understates the true false-negative rate, so periodically revisit performance as labels mature.
• Thresholds drift: as fraud patterns and the legitimate-transaction mix change over time, a fixed threshold's expected cost changes with it. Recompute periodically rather than treating threshold selection as a one-time decision.

Direct answer

The hyperparameters that matter most for a decision tree all control the same underlying thing: how much freedom the tree has to keep splitting. Tighter constraints (shallower trees, larger minimum leaf/split sizes) push toward higher bias and lower variance; looser constraints push the other way. The practical starting point is to constrain depth and leaf size lightly, validate, and loosen or tighten from there rather than guessing a final configuration up front.

Key hyperparameters and their bias/variance effect

Why min_samples_leaf usually beats min_samples_split for control

Both limit how far the tree can subdivide the data, but min_samples_split only checks the parent node before allowing a split, it says nothing about how the resulting children are sized. A parent can pass the min_samples_split check and still produce one very small, unstable child leaf. min_samples_leaf directly constrains every resulting leaf, which is a tighter and more direct guarantee against the specific failure mode (leaves fit to a handful of points) that causes overfitting.

Worked example: reading the depth/leaf-size trade-off directly from the impurity math

For a classification tree, a leaf's prediction is the majority class among the samples that land in it, and its error contribution is $\min(p, 1-p)$ where $p$ is the fraction of the majority class. A leaf with min_samples_leaf=1 that ends up with exactly 1 training point always has $p=1$ (perfect purity, since a single point can't be impure), contributing zero training error, exactly the mechanism that lets very small leaves memorize noise: a leaf of size 1 is definitionally "pure" regardless of whether the point it captured represents a real pattern or a mislabeled outlier. Raising min_samples_leaf to, say, 20 forces every leaf's prediction to be an average over at least 20 points, so a single mislabeled or unusual point can shift that leaf's prediction only slightly instead of defining it outright. This is the direct, mechanical link between the hyperparameter and the bias/variance trade-off: larger minimum leaf size forces averaging over more points, which is smoothing (higher bias, lower variance) by construction, not just a heuristic correlation.

Trade-offs and pitfalls

• Tuning every hyperparameter simultaneously via a large grid search is expensive and makes it hard to build intuition about which knob is doing the work; max_depth and min_samples_leaf alone usually capture most of the achievable bias/variance trade-off for a single tree, tune those first.
• A very shallow tree (max_depth=2 or 3) can look attractively simple and interpretable but may underfit badly if the true relationship needs more splits; don't equate "more constrained" with "safer" without checking validation error.
• max_features has almost no effect on a single, standalone tree's quality (there's no ensemble to decorrelate), so tuning it there is often wasted effort; it becomes one of the most important knobs the moment the tree is used inside a random forest.
• Hyperparameter defaults that work well for one dataset size don't transfer; a min_samples_leaf of 5 is aggressive smoothing on a 200-row dataset but nearly unconstrained on a 2-million-row one, always set these relative to your actual training set size.

Direct answer

For a modest tabular dataset, I would default to linear regression when I expect roughly linear relationships, need interpretable coefficients, or need fast, predictable inference latency in production. I would reach for KNN when I expect meaningfully non-linear local structure, have relatively low dimensionality, and can tolerate or optimize away its per-query cost.

Structured elaboration

Dataset size and dimensionality. KNN's distance metric becomes less meaningful as dimensionality grows (the curse of dimensionality: in high dimensions, distances between points concentrate, so "nearest" stops being informative). Linear regression's cost and sample requirements scale gently with dimensionality by comparison.

Feature scaling. KNN requires careful standardization since it is entirely distance-based, an unscaled feature with a large numeric range will dominate the distance calculation regardless of its actual predictive relevance. Linear regression doesn't strictly require scaling for correctness, though it helps numerically and makes coefficients comparable.

Interpretability. Linear regression gives directly interpretable coefficients (sign, relative magnitude, confidence intervals). KNN is non-parametric: you can inspect which neighbors drove a prediction, but there's no global "effect of this feature" statement to make.

Inference latency.

Worked example

Take a dataset with n = 1,000 training rows and d = 10 features, a small but realistic tabular size.

Linear regression, per prediction: one dot product of length 10 plus an intercept add.

$O(d) = 10 \text{ multiplies} + 1 \text{ add} = 11 \text{ flops}$

Brute-force KNN, per prediction: a squared-distance computation (d subtractions and multiplies) against every one of the 1,000 training points, ignoring the subsequent top-k selection.

$O(n \cdot d) = 1{,}000 \times 10 = 10{,}000 \text{ flops}$

$10{,}000 / 11 \approx 909$

At this scale, a single KNN prediction does roughly 909 times more arithmetic than a single linear regression prediction, and that ratio grows linearly with n as the dataset gets larger, while linear regression's cost stays fixed at $O(d)$ regardless of how much training data you have.

Trade-offs & pitfalls

• KNN's cost grows with data, linear regression's doesn't. This is the single biggest production consideration: a linear model's latency is flat as you collect more training data; KNN's latency (or memory, if you precompute a structure) keeps growing.
• Regularized linear regression (ridge/lasso) narrows some of the flexibility gap with KNN while keeping the interpretability and latency advantages, worth trying before jumping to a non-parametric method.
• KNN needs an explicit strategy for irrelevant features: unlike a regularized linear model, plain KNN has no built-in way to downweight a noisy or irrelevant dimension, it will happily let that dimension corrupt every distance calculation.
• Pitfall: picking KNN for its simplicity to implement while ignoring that its "training" is trivial but its serving cost is the opposite, an approximate nearest-neighbor index (KD-tree, ball-tree, or ANN library) is close to mandatory once n grows past a few thousand and latency matters.