Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Tree-based and support vector regression

Clear, exam-oriented notes on decision-tree (CART) regression and support vector regression (SVR): how they work, key formulas, derivations, worked examples, common mistakes and exam tips.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Tree-based regression and support vector regression are widely used when you need non-linear function approximation with interpretable structure (trees) or robust margin-based fitting (SVR). An engineer uses decision trees for fast, explainable predictions and SVR when controlling model complexity and using kernels to handle nonlinearity.

Key ideas

(Define terms first, in plain language.)

  • Regression: predicting a numeric target y from input x. The aim is to approximate the unknown function f(x) ≈ y.
  • Decision tree regression: a model that splits the input space into regions and predicts a constant (or simple function) in each region. We call each final region a leaf. A tree's internal nodes test feature values (e.g. x1 ≤ t).
  • CART: Classification And Regression Trees. For regression, CART builds binary trees by choosing splits that reduce error (commonly squared error). CART uses greedy top-down splitting.
  • Mean Squared Error (MSE): for n targets y_i and prediction ŷ_i, MSE = (1/n) Σ (y_i − ŷ_i)^2. In a leaf, the best constant prediction that minimizes squared error is the mean of the y_i in that leaf.

Exact statement and short proof used in exams:

  • Proposition: Given values y_1,...,y_n, the constant b that minimizes Σ_{i=1}^n (y_i − b)^2 is the sample mean \bar{y} = (1/n)Σ y_i. Proof: Differentiate S(b) = Σ (y_i − b)^2 w.r.t. b: dS/db = −2 Σ (y_i − b). Set 0 → b = (1/n) Σ y_i. Second derivative 2n > 0 confirms minimum.

  • Splitting rule (regression CART): for a candidate split s that partitions data into left (L) and right (R), define SSE (sum of squared errors) of a node S as Σ_{i in S} (y_i − mean_S)^2. CART chooses split s that minimizes SSE_left + SSE_right (equivalently maximises parent_SSE − (SSE_left + SSE_right)). This is a greedy local choice.

What to draw for an exam (decision tree split): draw X on horizontal axis and y on vertical axis for 1D feature; mark data points; draw a vertical line at candidate split t; label left mean and right mean; annotate SSE on each side and parent SSE. Label nodes and leaves.

  • Pruning: trees can overfit. Post-pruning or cost-complexity pruning trades off fit and tree size. Cost-complexity objective: R_α(T) = R(T) + α|T_leaves|, where R(T) is total SSE and |T_leaves| is number of leaves; α ≥ 0 controls penalty.

  • Support Vector Regression (SVR): a margin-based regression method. Key ideas:

    • ε-insensitive loss: errors smaller than ε are ignored. Loss for residual r = y − f(x) is max(0, |r| − ε).
    • Primal SVR problem (linear case): choose w and b to minimise 1/2 ||w||^2 + C Σ (ξ_i + ξ*_i) subject to y_i − (w·x_i + b) ≤ ε + ξ_i, (w·x_i + b) − y_i ≤ ε + ξ*_i, ξ_i, ξ*_i ≥ 0. Here ξ_i, ξ*_i are slack variables for violations beyond ε; C>0 trades off model complexity and training error.
    • Dual formulation introduces Lagrange multipliers α_i, α*_i. The dual is a quadratic program; only points with non-zero (α_i − α*_i) become support vectors (they lie outside or on the ε-tube). Prediction uses inner products, so we can apply the kernel trick: replace x·x' by K(x,x'). To recover b from the dual/KKT, pick any support vector with 0 < α_i < C and set b = y_i − Σ_j (α_j − α*_j) K(x_j, x_i) − ε; if instead 0 < α*_i < C, use b = y_i − Σ_j (α_j − α*_j) K(x_j, x_i) + ε; in practice, average b over all such margin support vectors.

Exact dual (statement often required in exams): maximize −1/2 Σ_{i,j} (α_i − α*_i)(α_j − α*_j) K(x_i,x_j) − ε Σ_i (α_i + α*_i) + Σ_i y_i (α_i − α*_i) subject to Σ_i (α_i − α*_i) = 0 and 0 ≤ α_i, α*_i ≤ C for all i.

Mention of KKT conditions: At optimality, complementary slackness determines which points are support vectors: if 0 < α_i < C or 0 < α*_i < C, the corresponding point lies exactly on the boundary of the ε-insensitive tube; if α_i = C or α*_i = C, the point violates the ε constraint. If α_i = α*_i = 0, the point lies strictly inside the ε-insensitive tube.

Assumptions: in CART we assume squared-error loss and greedy single-feature binary splits. For SVR primal→dual derivation we assume convexity (quadratic objective and linear constraints) so strong duality holds.

Formulas

mean_leaf = (1/n) · Σ_{i=1}^n y_i — mean prediction in a leaf; y in same units as target (unitless if none).

SSE(S) = Σ_{i in S} (y_i − mean_S)^2 — sum of squared errors in node S; y in units squared.

MSE = (1/n) · Σ_{i=1}^n (y_i − ŷ_i)^2 — mean squared error; units = (target unit)^2.

split_gain = SSE(parent) − [SSE(left) + SSE(right)] — improvement by a split; units = (target unit)^2.

Primal SVR: minimize (1/2)||w||^2 + C Σ (ξ_i + ξ*_i) subject to y_i − (w·x_i + b) ≤ ε + ξ_i, (w·x_i + b) − y_i ≤ ε + ξ*_i, ξ_i, ξ*_i ≥ 0.

ε-insensitive loss L_ε(r) = max(0, |r| − ε) — units = same as y.

Dual SVR (kernel K): maximize −(1/2) Σ_{i,j} (α_i − α*_i)(α_j − α*_j) K(x_i,x_j) − ε Σ_i (α_i + α*_i) + Σ_i y_i (α_i − α*_i) subject to Σ_i (α_i − α*_i) = 0 and 0 ≤ α_i, α*_i ≤ C.

Prediction f(x) = Σ_i (α_i − α*_i) K(x_i, x) + b — units same as target.

(When kernel is linear, K(x_i,x_j) = x_i·x_j.)

Worked examples

Example 1 (numerical decision-tree split): Data (1 feature x in unitless, target y in unitless): Index: 1 2 3 4 5 x: 1 2 3 4 5 y: 2 2 3 7 8 Goal: find best split among x ≤ 1.5, 2.5, 3.5, 4.5 for first binary split using SSE. Step 1: parent mean = (2+2+3+7+8)/5 = 22/5 = 4.4. Parent SSE = Σ (y_i − 4.4)^2 = (2−4.4)^2 + (2−4.4)^2 + (3−4.4)^2 + (7−4.4)^2 + (8−4.4)^2 = 5.76 + 5.76 + 1.96 + 6.76 + 12.96 = 33.2.

Evaluate split at x ≤ 1.5 (left indices {1}): Left mean = 2. Left SSE = (2−2)^2 = 0. Right indices {2,3,4,5}, right mean = (2+3+7+8)/4 = 20/4 = 5. Right SSE = (2−5)^2 + (3−5)^2 + (7−5)^2 + (8−5)^2 = 9 + 4 + 4 + 9 = 26. Total SSE = 0 + 26 = 26. Split gain = 33.2 − 26 = 7.2.

Split at x ≤ 2.5 (left {1,2}): left mean = (2+2)/2 = 2; left SSE = 0. Right {3,4,5} mean = (3+7+8)/3 = 18/3 = 6; right SSE = (3−6)^2 + (7−6)^2 + (8−6)^2 = 9 + 1 + 4 = 14. Total SSE = 14. Split gain = 33.2 − 14 = 19.2.

Split at x ≤ 3.5 (left {1,2,3}): left mean = (2+2+3)/3 = 7/3 ≈ 2.3333; left SSE = (2−2.3333)^2 + (2−2.3333)^2 + (3−2.3333)^2 = 0.1111 + 0.1111 + 0.4444 = 0.6666. Right {4,5} mean = (7+8)/2 = 7.5; right SSE = (7−7.5)^2 + (8−7.5)^2 = 0.25 + 0.25 = 0.5. Total SSE ≈ 1.1666. Split gain ≈ 33.2 − 1.1666 = 32.0334.

Split at x ≤ 4.5 (left {1,2,3,4}): left mean = (2+2+3+7)/4 = 14/4 = 3.5; left SSE = (2−3.5)^2 + (2−3.5)^2 + (3−3.5)^2 + (7−3.5)^2 = 2.25 + 2.25 + 0.25 + 12.25 = 17.0. Right {5} SSE = 0. Total SSE = 17. Split gain = 33.2 − 17 = 16.2.

Choose split x ≤ 3.5 because it gives largest split_gain ≈ 32.0334. Leaf predictions: left leaf predict ≈ 2.3333, right leaf predict = 7.5. Final answer (rounded): left prediction = 2.3333, right prediction = 7.5.

Example 2 (SVR dual derivation — model exam answer): Given primal linear SVR: minimize 1/2 ||w||^2 + C Σ (ξ_i + ξ*_i) subject to y_i − (w·x_i + b) ≤ ε + ξ_i, (w·x_i + b) − y_i ≤ ε + ξ*_i, ξ_i, ξ*_i ≥ 0.

Form the Lagrangian with multipliers α_i ≥ 0 for the first inequality, α*_i ≥ 0 for the second, and η_i ≥ 0, η*_i ≥ 0 for the nonnegativity constraints ξ_i ≥ 0, ξ*_i ≥ 0. L = 1/2||w||^2 + C Σ (ξ_i + ξ*_i) + Σ α_i [y_i − w·x_i − b − ε − ξ_i] + Σ α*_i [w·x_i + b − y_i − ε − ξ*_i] − Σ η_i ξ_i − Σ η*_i ξ*_i.

Differentiate L wrt primal variables and set to zero: ∂L/∂w = w − Σ (α_i − α*_i) x_i = 0 ⇒ w = Σ (α_i − α*_i) x_i. ∂L/∂b = − Σ (α_i − α*_i) = 0 ⇒ Σ (α_i − α*_i) = 0. ∂L/∂ξ_i = C − α_i − η_i = 0 ⇒ α_i ≤ C (since η_i ≥ 0). Similarly α*_i ≤ C.

Substitute w and eliminate primal variables to get dual objective (convex QP): maximize −1/2 Σ_{i,j} (α_i − α*_i)(α_j − α*_j) x_i·x_j − ε Σ_i (α_i + α*_i) + Σ_i y_i (α_i − α*_i) subject to Σ_i (α_i − α*_i) = 0 and 0 ≤ α_i, α*_i ≤ C.

Explain kernelization: replace x_i·x_j by kernel K(x_i,x_j) and the same dual and prediction formula hold, with prediction f(x) = Σ_i (α_i − α*_i) K(x_i,x) + b.

This derivation uses convexity to exchange min and max (strong duality): the primal is convex and Slater's condition holds (there exists a strictly feasible point, e.g., by choosing large ξ_i), so strong duality applies.

Common mistakes

  • In CART splitting, mixing up gain formula signs; always compute parent SSE − (left SSE + right SSE) to get positive gain.
  • For SVR, confusing α and α* signs in dual and forgetting constraint Σ (α_i − α*_i) = 0.
  • Thinking all non-zero α correspond to points strictly outside the ε tube; points on the boundary can also have 0 < α < C (KKT details).
  • Omitting kernel replacement x·x' → K(x,x') when moving from linear to non-linear SVR.

For your exam

Kinds of questions:

  • Definitions: define CART, leaf prediction, ε-insensitive loss, support vectors, kernel trick.
  • Short notes: explain pruning and cost-complexity pruning; explain hyperparameters C and ε and their effects (C large → less regularisation; ε large → wider tube, less sensitivity to small errors).
  • Derivations: prove mean minimizes SSE in a leaf; derive the SVR dual from the primal (Lagrangian, derivatives, substitute into Lagrangian).
  • Numericals: compute best split in 1D by evaluating candidate thresholds (like Example 1). Show all SSE computations and units.
  • Diagrams: draw 1D data points and a candidate vertical split; label left/right means and SSEs.

What full-marks answers include:

  • Clear definitions (bold the term and give its meaning), stated assumptions, step-by-step algebra (differentiate the Lagrangian or the SSE), correct final formulas and any constraints, and a short interpretive sentence explaining the result.

Quick check

  1. For squared-error regression, what constant prediction minimizes Σ (y_i − c)^2?
  2. Give the primal form of linear SVR (write objective and constraints).
  3. In the SVR dual, what constraint ties the α and α* multipliers together?

Answers: 1. The sample mean c = (1/n)Σ y_i. 2. Minimize 1/2||w||^2 + C Σ (ξ_i+ξ*_i) subject to y_i − (w·x_i + b) ≤ ε+ξ_i, (w·x_i + b) − y_i ≤ ε+ξ*_i, ξ_i, ξ*_i ≥ 0. 3. Σ_i (α_i − α*_i) = 0.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?