Trees, SVMs, Kernels

A decision tree partitions the input space into axis-aligned rectangles, with a constant prediction in each rectangle. To classify a new point, you start at the root, ask one yes/no question per node (e.g., "is petal length > 2.45?"), and follow branches until you reach a leaf. The leaf's prediction is the majority class of training points that landed there.

That is the entire inference algorithm. A decision tree is a function from $\mathbb{R}^d$ to $\{1, \ldots, K\}$ defined by a sequence of axis-aligned splits.

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier, export_text

iris = load_iris(as_frame=True)
X, y = iris.data[["petal length (cm)", "petal width (cm)"]].values, iris.target

tree = DecisionTreeClassifier(max_depth=2, random_state=42)
tree.fit(X, y)
print(export_text(tree, feature_names=["petal_length", "petal_width"]))
# |--- petal_length <= 2.45
# |   |--- class: 0
# |--- petal_length >  2.45
# |   |--- petal_width <= 1.75
# |   |   |--- class: 1
# |   |--- petal_width >  1.75
# |   |   |--- class: 2

Four lines of output. The fitted tree fully described. That is the readability story.

Note on scale: trees do not require feature standardization. Splits are on raw thresholds; scaling a feature by 100 just changes the threshold by 100. This is unique among the model families in this book.

Sklearn's DecisionTreeClassifier implements CART (Classification And Regression Trees). The recipe at each node is greedy: pick the feature $j$ and threshold $t$ that minimize a weighted impurity:

where $m$ is the number of points at the node, $m_{\text{left}}$ and $m_{\text{right}}$ are the counts after the split, and $G$ is an impurity measure of the labels at that node.

Two common impurity measures.

Gini impurity for a node with class proportions $p_k$:

Maximum at $1/K$ for uniform class distribution (most uncertain), zero when one class dominates (pure leaf).

Entropy for the same node:

Same shape, slightly different curvature. In practice trees built with Gini and with entropy are nearly identical. Gini is the sklearn default, faster to compute.

CART tries every (feature, threshold) pair, picks the one minimizing $J$, recurses on the two children. Stop when the node is pure, or the depth limit hits, or fewer than min_samples_split examples remain.

tree = DecisionTreeClassifier(criterion="gini", max_depth=5, random_state=42)
tree.fit(X, y)
preds = tree.predict(X_test)

def gini(y):
    if len(y) == 0:
        return 0.0
    _, counts = np.unique(y, return_counts=True)
    p = counts / counts.sum()
    return float(1.0 - (p ** 2).sum())

def best_split(X, y):
    n, d = X.shape
    parent = gini(y)
    best_feat, best_thresh, best_gain = None, None, 0.0
    for f in range(d):
        for t in np.unique(X[:, f]):
            left_mask = X[:, f] <= t
            right_mask = ~left_mask
            if left_mask.sum() == 0 or right_mask.sum() == 0:
                continue
            weighted = (left_mask.sum() * gini(y[left_mask])
                        + right_mask.sum() * gini(y[right_mask])) / n
            gain = parent - weighted
            if gain > best_gain:
                best_gain, best_feat, best_thresh = gain, f, float(t)
    return best_feat, best_thresh, best_gain

def build_tree(X, y, max_depth=5, depth=0):
    if depth >= max_depth or len(np.unique(y)) == 1 or len(y) <= 1:
        return TreeNode(prediction=_majority(y))
    feat, thresh, gain = best_split(X, y)
    if feat is None or gain <= 0:
        return TreeNode(prediction=_majority(y))
    left_mask = X[:, feat] <= thresh
    left = build_tree(X[left_mask], y[left_mask], max_depth, depth + 1)
    right = build_tree(X[~left_mask], y[~left_mask], max_depth, depth + 1)
    return TreeNode(feature=feat, threshold=thresh, left=left, right=right)

def _predict_one(node, x):
    while node.prediction is None:
        node = node.left if x[node.feature] <= node.threshold else node.right
    return node.prediction

Run this on Iris with max_depth=2 and you get the same tree sklearn produced. The runtime is $O(m \log m \cdot d \cdot \text{depth})$ for sorted thresholds; the implementation above is $O(m^2 \cdot d \cdot \text{depth})$ because it does not sort. Sklearn sorts; the production code is more elaborate but the algorithm is the same.

A decision tree of unlimited depth will memorize the training set perfectly. Run sklearn's DecisionTreeClassifier(max_depth=None) on a 100-point dataset and you get 100% train accuracy. The corresponding test accuracy is typically poor.

The regularization hyperparameters for DecisionTreeClassifier are all about constraining the tree's growth:

• max_depth: hard cap on tree depth
• min_samples_split: minimum number of points required to split a node
• min_samples_leaf: minimum points in a leaf
• max_leaf_nodes: cap on total leaves
• max_features: at each node, consider only a random subset of features (this is the trick random forests exploit)
• ccp_alpha: cost-complexity pruning strength

The two regimes:

Pre-pruning (the hyperparameters above): never let the tree grow past a complexity bound. Post-pruning (ccp_alpha > 0): grow the tree fully, then snip back leaves whose contribution to training error is too small relative to their complexity cost.

In practice, max_depth in the range 3-10 combined with min_samples_leaf=5 covers most use cases. Tune with cross-validation.

from sklearn.model_selection import GridSearchCV

params = {"max_depth": [3, 5, 7, 10, None], "min_samples_leaf": [1, 5, 10]}
grid = GridSearchCV(DecisionTreeClassifier(random_state=42), params, cv=5)
grid.fit(X, y)
print(grid.best_params_, grid.best_score_)

The same algorithm works for regression. Change the impurity from Gini to mean-squared-error of the labels at a node:

The leaf prediction is the mean of training labels that landed there, not the majority vote.

from sklearn.tree import DecisionTreeRegressor

reg = DecisionTreeRegressor(max_depth=3, random_state=42)
reg.fit(X_train, y_train)

Regression trees produce piecewise-constant predictions: every leaf is a single number, so the prediction surface is a step function. This is the right tool when the relationship is piecewise rather than smooth. For smooth surfaces, a linear or kernel model is usually better. For the piecewise step-function case (say, predicting house prices where there are real discontinuities at school-district boundaries), trees are ideal.

Train a decision tree on 100 random points from Iris. Train another on a different 100 random points from Iris. The two trees will pick different root splits, different thresholds, possibly different feature orderings.

This is the instability problem. Trees have high variance because the greedy split decisions at the top of the tree are extremely sensitive to which examples landed in the training set. Once the root split is locked in, every downstream decision is conditioned on it.

Géron's Figure 6-7 in 08-geron-notebooks/06_decision_trees shows the same dataset trained twice (with two different random seeds in the data subsampling) producing visibly different decision boundaries. This is not a bug in CART. It is the cost of greedy decisions over discrete splits.

There are two fixes.

Fix 1: more data per node. If each node sees thousands of points, the greedy choice becomes statistically stable.

Fix 2: average many trees. Train $T$ trees, each on a bootstrap sample of the data (a fresh set of $m$ points drawn with replacement, so some examples repeat and roughly a third are left out), and take majority vote. This is bagging, and it is the foundation of random forests (another chapter). Variance drops by roughly $1/T$ if the trees are uncorrelated.

The instability of single trees is why random forests work. Single trees are unstable, but the aggregate of many unstable trees is stable, in the same way that the mean of many noisy measurements is precise.

Switch tracks. Support vector machines are the second classical workhorse. The idea: among all linear decision boundaries that separate two classes, pick the one whose margin (distance to the nearest training point on either side) is maximum.

For linearly separable data with labels $y_i \in \{-1, +1\}$, the model is $\hat{y} = \text{sign}(\mathbf{w}^T \mathbf{x} + b)$. The hard-margin SVM problem is:

The constraint says "every training point is on the correct side of the boundary and at least margin 1 away (in scaled units)". The objective says "make the weight vector as small as possible". Combined, you get the largest geometric margin, because the geometric margin equals $1 / \|\mathbf{w}\|$.

For non-separable data (real data), allow some slack:

$\xi_i$ is the slack for example $i$ (how much it violates the margin). $C$ is the regularization knob. Small $C$ = soft margin, large violations tolerated. Large $C$ = hard margin, model is forced to fit every example.

This is the soft-margin SVM and it is what SVC(kernel='linear') solves.

from sklearn.svm import LinearSVC
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

svm = Pipeline([
    ("scaler", StandardScaler()),
    ("svc", LinearSVC(C=1, loss="hinge", random_state=42)),
])
svm.fit(X, y)

The SVM problem above is a convex quadratic program (a "convex QP": minimize a convex quadratic objective subject to linear constraints, the smallest step up from the linear least-squares fits of another chapter). By Lagrangian duality, the standard move of folding each constraint into the objective with a multiplier so a constrained problem becomes an equivalent one, every convex QP has a dual problem. For SVMs the dual is:

with one Lagrange multiplier $\alpha_i \geq 0$ per training point (the multiplier introduced by the duality step above). The matrix of all pairwise inner products $\mathbf{x}_i^T \mathbf{x}_j$ is the Gram matrix $K$; the whole dual depends on the data only through it.

Three things to notice.

The data appears only as inner products $\mathbf{x}_i^T \mathbf{x}_j$ (the dot product: $\mathbf{x}^T \mathbf{z} = \sum_k x_k z_k$, the sum of elementwise products of two vectors). This is the key observation. Everything about the input vectors is mediated by these inner products. If you can compute the inner product, you can solve the SVM. The features themselves can stay implicit.

Most $\alpha_i$ end up at zero. Only training points exactly on the margin (or violating it) have $\alpha_i > 0$. These are the support vectors. The rest of the dataset contributes nothing to the decision function. Once trained, you can throw away every non-support-vector example and still get the same predictions.

The decision function is a weighted sum of inner products with support vectors:

This last form is what makes the kernel trick (§9) possible.

svm = SVC(kernel="linear", C=10.0)
svm.fit(X, y)
w = (svm.dual_coef_ @ svm.support_vectors_).ravel()
sv = svm.support_vectors_

import cvxpy as cp
import numpy as np

X = np.array([[1, 2], [2, 3], [3, 3], [2, 1], [3, 2], [4, 1]])
y = np.array([1, 1, 1, -1, -1, -1])
m = len(y)
C = 10.0

alpha = cp.Variable(m, nonneg=True)
K = X @ X.T                                  # Gram matrix of inner products
obj = cp.Maximize(cp.sum(alpha)
                  - 0.5 * cp.quad_form(cp.multiply(alpha, y), K))
constraints = [alpha <= C, alpha @ y == 0]
prob = cp.Problem(obj, constraints)
prob.solve()

w = (alpha.value * y) @ X                    # recover primal w
support_vectors = X[alpha.value > 1e-5]      # alpha_i > 0 => support vector

Run this and verify the resulting w and support vectors match sklearn.svm.SVC(kernel='linear', C=10) to floating-point tolerance.

There is a second, fully equivalent way to look at the SVM. Instead of constrained optimization, treat it as regularized empirical risk minimization with the hinge loss:

The second term is the hinge loss: zero for examples correctly classified with margin ≥ 1, linearly growing otherwise. The first term is L2 regularization on the weights.

This perspective is useful because it puts SVMs on the same footing as logistic regression. Logistic regression minimizes log-loss + L2; SVM minimizes hinge + L2. The only difference is the loss function. And once you see SVM this way, training it with SGD is trivial: just plug hinge into the loss in another chapter's training loop.

sklearn.linear_model.SGDClassifier(loss='hinge') does exactly this and trains SVMs on millions of examples that the dual solver cannot handle.

svm = SGDClassifier(loss="hinge", alpha=0.0001, max_iter=1000, random_state=42)
svm.fit(X_scaled, y)
preds = svm.predict(X_test)

def hinge_loss(w, b, X, y, C):
    y_pm = np.where(y == 0, -1, 1).astype(np.float64)
    margins = 1 - y_pm * (X @ w + b)
    return float(0.5 * (w @ w) + C * np.maximum(0, margins).sum())

def svm_sgd(X, y, C=1.0, eta=0.01, n_epochs=100, seed=0):
    rng = np.random.default_rng(seed)
    m, d = X.shape
    y_pm = np.where(y == 0, -1, 1).astype(np.float64)
    w = np.zeros(d)
    b = 0.0
    for ep in range(n_epochs):
        idx = rng.permutation(m)
        for i in idx:
            xi, yi = X[i], y_pm[i]
            margin = yi * (xi @ w + b)
            if margin < 1:
                grad_w = w - C * yi * xi
                grad_b = -C * yi
            else:
                grad_w = w
                grad_b = 0.0
            w = w - eta * grad_w
            b = b - eta * grad_b
    return w, b

def predict_svm(w, b, X):
    scores = X @ w + b
    return (scores >= 0).astype(int)

Recall the dual: data appears only as inner products $\mathbf{x}_i^T \mathbf{x}_j$. The decision function is a weighted sum of inner products with support vectors. Nowhere do you need to compute features explicitly. You only need to evaluate the inner product.

What if you want non-linear decision boundaries? The classical move is to expand features. Polynomial regression added $x^2$, $x^3$, $x_1 x_2$ as new columns. SVMs can do this too. But explicit polynomial expansion grows quickly: for degree-$k$ polynomials in $d$ dimensions (including lower-degree terms), the feature count is $\binom{d+k}{k}$. With $d = 100$ and $k = 5$, that is 96,560,646 features—usually impractical to materialize for a nontrivial dataset.

The kernel trick says: do not build the matrix. For the polynomial kernel of degree $k$:

If you expand the algebra, this equals $\phi(\mathbf{x})^T \phi(\mathbf{z})$ for some implicit feature map $\phi$ that produces all monomials of degree $\leq k$. You never compute $\phi(\mathbf{x})$. You evaluate $K$ in $O(d)$ time. The implicit feature space might have millions of dimensions; you compute the inner product without visiting any of them.

The RBF (radial basis function) kernel is even better:

This corresponds to an infinite-dimensional implicit feature space. The Taylor expansion of $e^x$ has infinitely many terms. You still compute $K$ in $O(d)$ time. The dual SVM is now operating in an infinite-dimensional space, and the model has no idea.

from sklearn.svm import SVC

poly_svm = SVC(kernel="poly", degree=3, coef0=1, C=5)
rbf_svm  = SVC(kernel="rbf", gamma=5, C=0.001)
poly_svm.fit(X_scaled, y)
rbf_svm.fit(X_scaled, y)

Hyperparameters:

• C is regularization (same as before): small = soft margin, large = hard.
• gamma (RBF only) is "kernel width". Large gamma = sharp peaks around each support vector, decision boundary wiggles. Small gamma = smooth boundary.
• degree and coef0 (poly only) control the polynomial.

Tune with cross-validation. Default gamma='scale' is a sensible starting point.

What the kernel trick does NOT do. It does not let you somehow extract the implicit features. They stay implicit forever. You can predict at new points (in $O(d \cdot |SV|)$ time per prediction) but you cannot interpret the model in the implicit feature space. The kernel trick is opaque by construction.

Caveat (Mercer's theorem): Not every function is a valid kernel. $K(\mathbf{x}, \mathbf{z})$ must be symmetric and positive semi-definite — meaning the Gram matrix $K$ (§7) on any finite set of inputs is symmetric and satisfies $\mathbf{z}^T K \mathbf{z} \geq 0$ for every vector $\mathbf{z}$, which is exactly what guarantees the dual stays a convex QP. Polynomial and RBF satisfy this. So do linear, sigmoid (sometimes), and Laplace. Inventing your own kernel without checking PSD is a way to get a model that does not train, or trains to garbage.

Sometimes you want polynomial features explicitly (for interpretability, or because you want to combine them with a non-SVM model). sklearn's PolynomialFeatures does this:

from sklearn.preprocessing import PolynomialFeatures
from sklearn.linear_model import LinearRegression

poly = PolynomialFeatures(degree=3, include_bias=False)
X_poly = poly.fit_transform(X)
linear_reg = LinearRegression()
linear_reg.fit(X_poly, y)

This is the explicit version of what the polynomial kernel does implicitly. For small $d$ and small degree, the explicit version can be attractive because you keep readable feature names. As the expansion grows, alternatives include a kernel method, sparse/selected interactions, approximate feature maps, or a different nonlinear model; the right choice depends on sample count, latency, and interpretability needs.

The decision boundary you get from SVC(kernel='poly', degree=3) is, up to regularization details, the same boundary you would get from PolynomialFeatures(degree=3) + LinearSVC on small problems. Verify this on a toy 2D dataset and you internalize the kernel trick.

SVMs were the dominant classification algorithm from roughly 1998 to 2012. Then deep learning took over for image and text, and gradient-boosted trees (XGBoost, LightGBM) took over for tabular. Where does that leave SVMs in 2026?

SVMs win when:

• The dataset is small (~100 to ~10k examples). The dual SVM has a sample-efficient theory and tight margins.
• Features are dense and the decision boundary is smooth but non-linear. RBF kernel SVMs interpolate cleanly.
• You need a model with a clear theoretical guarantee. SVM generalization bounds (VC dimension, margin-based bounds) are sharp.
• You have a kernel that encodes domain knowledge. String kernels for biological sequences, graph kernels for chemistry. Replacing the kernel with a deep encoder is harder than tuning C and gamma.

SVMs lose when:

• The dataset is large (> 100k examples). Dual solvers scale as $O(m^2)$ or worse. SGD-trained linear SVMs are fine but lose the kernel advantage.
• Features are tabular and heterogeneous. XGBoost handles this better and gives feature importances.
• Decision boundary is highly non-smooth. Trees handle discontinuities natively; RBF SVMs smooth them out.
• The task is image / text / audio / video. Convolutional or transformer-based models dominate.

The honest verdict: SVMs are rarely the right first choice in 2026. They are still the right choice for a small set of small-data problems with kernels that bring in domain knowledge. Knowing them matters because (a) the kernel trick generalizes to other algorithms (kernel ridge regression, kernel PCA, Gaussian processes), and (b) the duality and margin reasoning shows up in the theory of every supervised learner. The SVM is not the deployment target; it is the conceptual scaffold.

Single decision trees have high variance (§5). Many slightly different trees averaged together have much lower variance. That is bagging.

Random forest is bagging applied to decision trees, with one extra trick: at each split, consider only a random subset of features (max_features='sqrt' for classification). This decorrelates the trees, which makes the averaging effect stronger.

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(n_estimators=100, max_features="sqrt", random_state=42)
rf.fit(X, y)

That is a teaser. another chapter is the full story: random forests, AdaBoost, gradient boosting, XGBoost, LightGBM, stacking. For now, internalize: a single tree is a starter; an ensemble of trees is the production answer. The classical-ML state of the art on tabular data in 2026 is gradient-boosted trees, not deep learning, not SVMs.