Introduction to Machine Learning

Feature Engineering
and Generalization

When a better fit is a worse model

Reality and the Model

Reality
Model
compression
prediction

The model is a compression of reality. Today: how much can we compress before prediction breaks?

The Recipe, So Far

1 · hypothesis
\( h_\theta(x) = \theta^\top x \)
2 · cost
\( J(\theta) = \tfrac12 \sum_i (h_\theta(x^{(i)}) - y^{(i)})^2 \)
3 · minimize
\( \hat\theta = \arg\min_\theta J(\theta) \)
4 · optimal predictor
\( y = h_{\hat\theta}(x) \)
5 · predict unseen data
\( y_{\text{pred}} = h_{\hat\theta}(x_{\text{new}}) \)

Step 5 is the one we have never checked. Unseen is the whole point.

How Do You Choose the Hypothesis?

Every one of these fits the points. They disagree everywhere between the points.

\(h\) Does Not Have to Be Linear in \(x\)

Assume a linear hypothesis, and it can still bend: build a polynomial model.

\( h_\theta(x) = \theta_0 + \theta_1 x + \theta_2 x^2 + \theta_3 x^3 + \dots \)

Still linear in the parameters, which is all the math needed:

\( h_\theta(x) = \underbrace{[\theta_0, \theta_1, \theta_2, \dots]}_{\theta} \cdot \underbrace{[1, x, x^2, \dots]}_{\phi(x)} = \theta^\top \phi(x) \)

Feature Engineering

The feature map \( h_\theta(x) = \theta^\top \phi(x) \)
What it is \(\phi\) turns raw input into the quantities the model actually sees: powers, products, logs, counts, anything you can compute.
Why it matters Choosing \(\phi\) is choosing the shape of what can be learned. It is modeling, done by hand.

Examples: \( \phi(x) = [1, x] \),   \( \phi(x) = [1, x, x^2] \),   \( \phi(x) = [1, x_1, x_2, x_1 x_2] \)

How Do We Choose \(\phi(x)\)?

Underfitting: high bias

Just right

Overfitting: high variance

the middle panel follows your slider

How Can We Tell If \(\phi(\cdot)\) Is Good?

The purpose of machine learning To generalize to unseen data.
Hold out a test set Keep part of the data aside. Never fit on it. It stands in for the future.
Two numbers, not one
\( J_{\text{train}} = \frac{1}{2 d_{\text{tr}}} \sum_{\text{train}} (\theta^\top \phi(x^{(i)}) - y^{(i)})^2 \)
\( J_{\text{test}} = \frac{1}{2 d_{\text{te}}} \sum_{\text{test}} (\theta^\top \phi(x^{(i)}) - y^{(i)})^2 \)

The Variance-Bias Trade-off

Training error Falls forever. More parameters always fit the data you have better.
Test error Falls, then rises. The rise is the model memorizing noise.
The sweet spot Lowest test error, not lowest training error.

error as a function of complexity, that is, of the number of parameters

Other Hyperparameters

\(\phi\) is not the only unknown we choose rather than learn.

T
number of epochs
η
step size
φ
feature vector

Parameters are fit by the data. Hyperparameters are chosen by you, and they need their own evidence.

The Machine Learning Workflow

What is the problem with this workflow? We picked \(\phi\) using the test set, so the test set is no longer unseen.

Optimize Over \(\phi\) With a Validation Set

Training set Fit \(\theta\).
\( J_{\text{train}} = \frac{1}{2d_{\text{tr}}}\sum_{\text{train}} (\theta^\top\phi(x^{(i)}) - y^{(i)})^2 \)
Validation set Choose \(\phi\) and the other hyperparameters.
\( J_{\text{val}} = \frac{1}{2d_{\text{va}}}\sum_{\text{val}} (\theta^\top\phi(x^{(i)}) - y^{(i)})^2 \)
Test set Touched once, at the very end, to report honestly.

Cross Validation

The idea Rotate which fold plays validation, fit on the rest, and average the scores. Every point gets used for both fitting and checking.
Why bother One split is a lucky or unlucky draw. \(k\) splits give an estimate with an error bar, which matters most when data is scarce.

Remedies to Overfitting

Practical tips to decrease overfitting:

  • Make the model simpler if it is overfitting, and more complex if it is underfitting, while tracking both losses
  • Recursive feature elimination: start with all features and drop them one by one
  • Get rid of features you believe are irrelevant to the desired output
  • Add a regularization term to the cost function

Regularization

Force the fitting parameters to be smaller: shrink the hypothesis class.

Regularized cost \( J_{\text{reg}}(\theta) = J(\theta) + \lambda R(\theta) \)
L1 · lasso
\( R(\theta) = \lVert \theta \rVert_1 = |\theta_0| + |\theta_1| + \dots \)
drives coefficients to exactly zero: it selects features
L2 · ridge
\( R(\theta) = \lVert \theta \rVert_2 = (\theta_0^2 + \theta_1^2 + \dots)^{1/2} \)
shrinks all coefficients smoothly toward zero

The Geometry of L1 and L2

L2: a disc, so the corner is never special

L1: a diamond, and its corners sit on the axes

The solution is where the cost contours first touch the budget. On a diamond that touch usually happens at a corner, where a coefficient is exactly zero.

The Whole Workflow in Code

num_points = 1000
var, a, b, c = 1, 3, 2, 1

x = np.linspace(0, 5, num_points)
y = c + a*x + b*x**2 + var*np.random.normal(0, 1, num_points)

def design_matrix(x, degree):
    X = np.ones((len(x), degree + 1))
    for i in range(1, degree + 1):
        X[:, i] = x ** i
    return X

idx = np.random.permutation(num_points)
x_train, x_test = x[idx[:800]], x[idx[800:]]
y_train, y_test = y[idx[:800]], y[idx[800:]]

theta, J_hist = gradient_descent(
    design_matrix(x_train, degree), y_train,
    theta0, learning_rate, num_iters)

Synthetic data, a feature map, an honest split, then gradient descent. Outputs on the right are computed live.

Summary

The feature map
\( h_\theta(x) = \theta^\top \phi(x) \)

still linear in \(\theta\), any shape in \(x\)

The honest score
\( J_{\text{test}} \ne J_{\text{train}} \)

train, validate, and test on different data

The trade-off

too simple underfits, too complex memorizes noise;
pick the minimum of test error

Regularization
\( J + \lambda R(\theta) \)

L1 selects, L2 shrinks

Next: classification, where the output is a label.