Feature Mapping
Learning Objectives
After reading this page, you should be able to:
- Define a feature mapping.
- Explain feature mapping allows a linear model to learn a non-linear function.
- Apply a polynomial feature mapping to a dataset.
- Describe how the polynomial degree \(M\) affects underfitting and overfitting.
- Explain how to choose the polynomial degree \(M\) to achieve good generalization.
1 Introduction
In the previous chapter, we learned about the linear regression model, which is simple and versatile method for fitting a linear relationship. However, many interesting real-world datasets do not follow a linear pattern. For example, a scatter plot of the data may reveal a clear curve rather than a straight line, or domain knowledge may suggest that the relationship involves squares, products, or periodic terms. Figure 1 shows such a dataset. The points follow a smooth wave, and no straight line could fit them well.
Noisy sinusoidal training data
Does this mean the linear regression model is useless for most interesting datasets? It turns out that we can still use linear regression for these datasets, just not with the original features. The key idea is to create new features based on the original ones so that the non-linear relatinoship becomes linear in the transformed features. This approach is called feature mapping (or basis expansion).
Definition: A feature mapping (or basis expansion) is a function \[\psi: \mathbb{R}^D \rightarrow \mathbb{R}^{D'}\] that maps each input \(\mathbf{x} \in \mathbb{R}^D\) to a new feature vector \(\psi(\mathbf{x}) \in \mathbb{R}^{D'}\).
To train linear regression with this mapping, we replace every original training input with its mapped version. The original training set \[\{(\mathbf{x}^{(i)}, t^{(i)})\}_{i=1}^N\] becomes \[\{(\psi(\mathbf{x}^{(i)}), t^{(i)})\}_{i=1}^N.\] The targets \(t^{(i)}\) are unchanged.
The resulting model is linear in \(\psi(\mathbf{x})\), but can represent nonlinear relationships in the original input \(\mathbf{x}\).
In general, \(\psi\) can be any function. In practice, a few choices are common. The most frequently used is polynomial feature mapping. A scalar input \(x\) is expanded into its powers \[\psi(x) = \begin{bmatrix} 1 & x & x^2 & \cdots & x^M \end{bmatrix}^\top,\] or a multi-dimensional input \(\mathbf{x}\) is expanded to include products and squares of its components. We cover this in detail in the next section.
Polynomial mappings are not the only option. For data with periodic structure, such as temperature varying over the course of a year, a better choice may be a sinusoidal (Fourier) mapping. \[\psi(x) = \begin{bmatrix} 1 & \sin(2\pi x) & \cos(2\pi x) & \sin(4\pi x) & \cos(4\pi x) & \sin(6\pi x) & \cos(6\pi x) & \cdots \end{bmatrix}^\top.\] This mapping uses sines and cosines at increasing frequencies as its basis functions. After applying \(\psi\), we can again use ordinary linear regression. The model becomes a linear combination of sinusoidal basis functions, which can represent a wide variety of periodic patterns.
2 Polynomial Feature Mapping
A polynomial feature mapping is a common choice. If our initial input is 1D, we simply map each input \(x\) into a vector of its powers \(\begin{bmatrix} 1 & x & x^2 & \cdots & x^M \end{bmatrix}^\top\).
Definition: A polynomial feature mapping of degree \(M\) for a scalar input \(x \in \mathbb{R}\) is the map \[\psi(x) = \begin{bmatrix}1\\ x\\ x^2 \\ \vdots \\ x^M\end{bmatrix} \in \mathbb{R}^{M+1}.\] Applied to the input \(x\), this mapping produces an \((M+1)\)-dimensional feature vector consisting of the first \(M+1\) powers of \(x\). \(M\) is a hyperparameter called the degree of the polynomial.
Table 1 makes the scalar case concrete, expanding a 1D input to degree-3 polynomial features.
| \(x\) | \(t\) |
|---|---|
| 1.0 | 3.0 |
| 2.0 | 7.1 |
| 3.0 | 14.9 |
| 4.0 | 31.2 |
| \(x^0\) | \(x^1\) | \(x^2\) | \(x^3\) | \(t\) |
|---|---|---|---|---|
| 1 | 1.0 | 1.0 | 1.0 | 3.0 |
| 1 | 2.0 | 4.0 | 8.0 | 7.1 |
| 1 | 3.0 | 9.0 | 27.0 | 14.9 |
| 1 | 4.0 | 16.0 | 64.0 | 31.2 |
What changes when the input is a vector rather than a scalar? Powers of a single variable are no longer enough, because the target may also depend on how two features vary together. For a vector input \(\mathbf{x} \in \mathbb{R}^D\), the degree-\(M\) polynomial feature mapping therefore includes every monomial, meaning every product of features, whose total degree is at most \(M\).
Suppose that we want to transform a 2-dimension input \(\mathbf{x} = \begin{bmatrix} x_1 & x_2 \end{bmatrix}^\top\) into degree-2 polynomial features. The polynomial feature mapping is
\[\psi(\mathbf{x}) = \begin{bmatrix}1 & x_1 & x_2 & x_1 x_2 & x_1^2 & x_2^2\end{bmatrix}^\top \in \mathbb{R}^6.\]
These six entries are exactly the monomials of total degree at most 2. The cross-term \(x_1 x_2\) is the term that we would not produce when mapping a scalar input to polynomial features. Table 2 shows this mapping applied to three leaves, measured by width \(x_1\) and height \(x_2\).
| \(x_1\) (cm) | \(x_2\) (cm) | \(t\) |
|---|---|---|
| 7.0 | 12.0 | 4.3 |
| 9.0 | 6.0 | 2.8 |
| 10.0 | 18.0 | 7.6 |
| \(1\) | \(x_1\) | \(x_2\) | \(x_1 x_2\) | \(x_1^2\) | \(x_2^2\) | \(t\) |
|---|---|---|---|---|---|---|
| 1 | 7.0 | 12.0 | 84.0 | 49.0 | 144.0 | 4.3 |
| 1 | 9.0 | 6.0 | 54.0 | 81.0 | 36.0 | 2.8 |
| 1 | 10.0 | 18.0 | 180.0 | 100.0 | 324.0 | 7.6 |
The mapping adds four features to the original \(x_1\) and \(x_2\), and a linear regression model trained on this data set uses all six of them to predict the target. The target values \(t\) are unchanged. In general, the number of features grows as \(\binom{D+M}{M}\), which becomes large quickly as \(D\) or \(M\) increases.
In practice, a linear regression model built on polynomial features is so commonplace that the method is called polynomial regression.
Definition: Polynomial regression of degree \(M\) fits a model of the form \[y = w_0 + w_1 x + w_2 x^2 + \dots + w_M x^M = \sum_{j=0}^M w_j x^j\] to the training data.
Despite the nonlinear appearance, this is a linear regression problem. Writing \(\psi(x) = \begin{bmatrix} 1 & x & x^2 & \cdots & x^M \end{bmatrix}^\top\), the model is \(y = \psi(x)^\top \mathbf{w}\), which is linear in the parameters \(w_0, w_1, \ldots, w_M\). We therefore apply the same least squares or gradient descent procedure as before, using \(\psi(\mathbf{x}^{(i)})\) in place of \(\mathbf{x}^{(i)}\) throughout.
The visualization below shows polynomial regression for several values of \(M\). Use the slider to change the polynomial degree and observe how the fitted curve changes.
Interactive polynomial regression
2.1 Model Complexity and Generalization
The degree \(M\) of the polynomial controls the number of input features, and thus the complexity of the resulting regression model. As we increase \(M\), the model gains more parameters and becomes capable of fitting increasingly intricate patterns in the training data. However, a more complex model is not always a better model.
When \(M\) is very small (e.g., \(M=0\), a constant prediction, or \(M=1\), a straight line), the model is too simple to capture the true pattern in the data. Recall that this is called underfitting. The model has high bias, and its predictions are systematically off for most inputs. A model that underfits achieves high error on both the training set and any new data.
When \(M\) is very large (e.g., \(M=9\) for a handful of data points), the model has enough parameters to pass through or very near every training point. Recall that this is called overfitting. The model has memorized the specific noise values in this training set rather than learning the underlying pattern. The training error is near zero, but the model generalizes poorly. Its predictions on new data are unreliable because the learned weights reflect the idiosyncrasies of one particular training set, not the true relationship.
Good generalization requires choosing \(M\) to be neither too small nor too large. Selecting the right value of \(M\) is yet another example of hyperparameter tuning. We choose \(M\) using a held-out validation set, not the training set, precisely to avoid rewarding a model for memorizing its training data.
3 Summary
Feature mapping lets linear regression fit nonlinear data by changing the representation of each input rather than the learning algorithm. We replace every original input with its mapped features, then apply the same least squares procedure as before.
This is Fundamental Idea #4: ML Describes Geometric Processes. A feature mapping sends points from the original input space into a new feature space. Relationships that are curved in the original coordinates can become linear in the new ones. The choice of mapping, whether polynomial powers, sinusoids, or something else, is a choice of geometry. It decides which patterns a linear model can represent easily.
The same mapping also illustrates Fundamental Idea #2: ML Requires Balancing Tradeoffs in Sources of Error. Raising the polynomial degree adds features and parameters, so the model can fit more intricate curves. If the degree is too small, the model underfits. If the degree is too large, it overfits the noise in the training set. A good mapping is rich enough to capture the true pattern and not so rich that it memorizes one particular sample.