3.1.1 Motivating examples

Feature transformation is an approach in which we manually transform the features (the inputs) before using them in the standard linear regression. In our case, we will try the log transformation by creating a new set of inputs as \(\tilde{x_i} = \log(x_i), \ i=1, \ldots, n\).

We continue working with the simple linear regression model from section 2.3 but instead of the original feature \(x\) we now use the transformed \(\tilde{x} = \log(x)\) \[y \approx w_0 + w_1 \tilde{x}, \qquad \tilde{x} = \log(x) \enspace .\] We will next follow the matrix approach introduced in section 2.3.3 simply replacing everywhere the original \(x\) with the transformed \(\tilde{x}\). We will first augment the data by the column of ones so that \(\mathbf{\tilde{x}}_i = (1, \tilde{x})_i\) is a \(2\)-dimensional vector for every \(i = 1, \ldots, n\). We then work the \(n \times 2\) matrix \(\mathbf{\tilde{X}}\) and we minimize the loss function \[L(\mathbf{w}) = \frac{1}{n} || \, \mathbf{y} - \mathbf{\tilde{X}} \mathbf{w} \, ||_2^2\] In analogy with the result in section 2.3.3. the minimizing solution is \[ \widehat{\mathbf{w}} = \big(\mathbf{\tilde{X}}^T\, \mathbf{\tilde{X}} \big)^{-1} \mathbf{\tilde{X}}^T \, \mathbf{y} \enspace . \]

---

Let’s explore one more, perhaps more obvious example. Here clearly fitting a line to the original data does not do a great job. However, applying first the feature transformation \(\tilde{x} = x^2\) and then performing the linear regression \[y \approx w_0 + w_1 \tilde{x} = w_0 + w_1 x^2\] seems to work rather well!

3.1.2 Feature map

In the examples above we followed the same strategy. Inspecting the data, we suspected that the hypotheses of linear relationship between the inputs \(x \in \mathcal{X}\) and \(y \in \mathcal{Y}\) is not quite satisfactory. Instead of working with the original inputs \(x \in \mathcal{X}\) and trying to figure out how to learn a complex nonlinear model, we first applied a suitable nolinear feature transformation to the data using a feature map \(\phi: \mathcal{X} \to \tilde{\mathcal{X}}, \ \tilde{x} = \phi(x)\) and performed the linear regression in this tranformed feature space \(\tilde{\mathcal{X}}\).

\[y \approx w_0 + w_1 \phi(x)\]

This neat trick allowed us to get from the very restrictive world of linear relationships to highly nonlinear ones while keeping the math and machinery simple!

In the examples above we used a single nonlinear transformation to a single input dimension. It is, however, possible to apply multiple transformations to the the same variable creating a vector of transformed inputs \(\tilde{\mathbf{x}} = (\phi_1(x), \phi_2(x), \ldots, \phi_2(x))^T\). Instead of simple linear regression we then need to work with multivariate regression with the parameters vector \(\mathbf{w}\) of length \(d+1\).

The most common transformations are powers \((x^2, x^3, \ldots)\). This is sometimes referred to as polynomial regression because the hypotheses is a polynomial in the original feature space \(\mathcal{X}\) (while still a simple linear regression in the transformed feature space \(\tilde{\mathcal{X}}\)).

---

When the original feature space \(\mathcal{X} \subseteq \mathbb{R}^d\) is multi-dimensional, we can apply various non-linear transformations (such as powers) to each dimension \(x_i\). These may or may not be the same for each dimension. Furthermore, we can account for interactions between dimensions by working with products such as \(x_i x_j\). The regression model is then \[y \approx \phi(\mathbf{x})^T \mathbf{w} \enspace ,\] where \(\phi: \mathcal{X} \to \tilde{\mathcal{X}}\) is the vector nonlinear transformation function.

In fact, the feature transformation is such a common approach that you can often see simply \[y \approx \mathbf{\phi}^T \mathbf{w} \enspace ,\] where everybody understands that this is a linear regression problem after first applying some non-linear transformation to the original data. Everything we discussed for the linear regression over the original input \(\mathbf{x}\) vectors and \(\mathbf{X}\) matrix can be rewritten using the transformed feature vectors \(\phi\) and matrix \(\Phi\).

---

There are two major take-home messages from this:

• First, while linear regression seems almost too trivial, it is at the core of ML theory and many ML algorithms. It is mathematically very simple, yet can be rather powerful when combined well with suitable data transformations.
• Second, the idea of feature transformations is not specific to linear regression. It is a general tool that you can use in all ML algorithms and if used correctly, it may very much improve your modelling efforts.

3.1.3 Feature ingeneering

There is one question we haven’t yet answered. How do you know which feature transformation you shall apply? This indeed is a very critical question and the answer is anything but obvious. The process of finding suitable feature transformations is called feature ingeneering. It is usually very much based on domain knowledge and experience and if done right can bring rather impressive improvements to the basic ML models. Two classical examples come from computer vision and natural language processing.

In computer vision you often work with images. These can be initially represented either as \(2\)-d matrices \(x \in \mathcal{X} \in [0,1]^2\) where each element represents the gray-scale intensity of the pixel in the image, or \(3\)-d cubes \(x \in \mathcal{X} \in [0,1]^3\) with intensities of the Red, Green and Blue channels. Computer vision experts have discovered quite long ago that what typically matters in images (for tasks such as classification) are the important parts of the images such as edges, corners, blobs, etc. They have therefore developed a multitude of feature detectors of which probably the most successful one is the SIFT (Scale-Invariant Feature Transform). It performs a series of transformations to the the original pixel values of the images to find the important and part of the image and encodes them into an transformed feature space \(\tilde{x} \in \tilde{\mathcal{X}}\).

In natural language processing the original input data \(x \in \mathcal{X}\) are often simply pieces of text (one for each instance). In the bag of words (BOW) approach we treat the text as a set of words disregarding their order and grammar. We can then create features by counting the number of occurrences of all words in each of the text.

3.2.1 Centering

The goal of centering is to move the average of all the data to zero. One of the major reasons for this is to get rid of the intercept term \(w_0\) in the linear regression and the need to expand the inputs \(\mathbf{X}\) by the 1st column of ones.

The centering transformation removes the mean from the data and is defined as follows (\(C\) stands for centered) \[x^{(C)} = \phi_{C}(x) = x - \bar{x} = x - \frac{1}{n} \sum_i^n x_i\] It is rather easy to show that the centered variable has zero mean (see related homework).

Revisiting the minimizing solution for the intercept \(w_0\) in simple linear regression (section 2.3.2) \[\widehat{w}_0 = \bar{y} - \widehat{w}_1 \bar{x} \enspace ,\] we see that when working with the centered data we get always \[\widehat{w}_0 = \bar{y}^{(C)} - \widehat{w}_1 \bar{x}^{(C)} = 0 - \widehat{w}_1 0 = 0 \enspace .\] We can thus drop the parameter \(w_0\) from the regression altogether (it is always zero) and there is not need to augment our data matrix by the column of ones.

3.2.2 Rescaling

The goal of rescaling is to remove from the data the effect of using different measurement scales which make comparisons of variability difficult. We re-scale the variables by their standard deviation making the variance (and standard deviation) of the re-scaled variable equal to one.

3.2.3 Normalization

Normalization is the composition of centering and re-scaling and is define as follows (\(N\) stands for normalized) \[x^{(N)} = \phi_{N}(x) = \frac{x - \bar{x}}{\sigma_x} = \frac{x^{(C)}}{\sigma_x} \enspace ,\] where \(\bar{x}\) and \(\sigma_x\) are the empirical mean and standard deviation of \(x\).

It is rather easy to show that normalized variable has unit (~ equal to one) variance (see related homework).

3.3.1 Expected loss minimization

In the above, we developed arguments for using the expected loss as the correct measure of the quality of a hypotheses \(h(x)\). It is therefore natural to use this measure in the search for the best regression function and define the best regression function \(h^*(x)\) as the one minimizing the expected loss \[h^* = \text{arg min}_h \, \mathbb{L}_{MSE} (h) = \text{arg min}_h \, \mathbb{E} \, \big( h(\mathbf{x}) - y \big)^2 \enspace .\]

Without anyhow limiting the hypotheses space \(h \in \mathcal{H}\) (i.e. not limiting \(\mathcal{H}\) to the space of e.g. linear functions) the best such hypotheses \(h^*(x)\) is called the Bayes predictive function.

3.5.1 Overfitting

In the homework Ex4 part2: feature transformation we used polynomial feature transformations to extend our hypotheses space \(\mathcal{H}\) from the simple linear functions to more complex polynomial functions (quadratic and higher degree polynomials).

We see in the plot above that the 12-degree polynomial has much more flexibility to capture all the little variances in the training data (the blue points) and therefore achieves lower mse over the training set than the 3-degree polynomial. However, checking the plot, the 12-degree polynomial regression function seems somehow unsatisfactory. Though we cannot be sure (because the only data we have to do the analysis are the blue points in the plot) it somehow seems unlikely that for a point \(x = -1.6\) the output value would really be around \(\hat{y} = 2.8\), and for points around \(x = -2.5\) so low that it cannot even fit the plot.

We next generate 100 new test data points and calculate the MSE of the two learned models over these new test data. What we observe is that the more flexible 12-degree polynomial actually performs very badly on these, having much higher mse over the test data. The problem we see in the plot is related to an important problem of many machine learning models: overfitting the training data sample.

Overfitting is closely related to the complexity of the hypotheses. Complex models often have enough capacity to capture all the variations in the training data, even those coming from the noise \(\epsilon\) instead of focusing on the important variations explaining the outputs, they overfit. Too simple models, on the other hand, cannot capture the variability in the data sufficiently and do not perform well either, they underfit. For example, a simple linear model would underfit the data in the example above.

In the image below we plot the MSE calculated over the train and test data for polynomials of degree 1 (linear) to 8. The patterns is fairly typical in any supervised learning. The training error monotonically decreases as the complexity (and therefore flexibility) of the model increases. However, the test error is high in the beginning when the model is not flexible enough and underfits, then decreases for a while and then starts increasing again as the hypothesis becomes too flexible and overfits.

3.5.2 Estimating prediction error

Important take-away message from the previous section is to never use the MSE over the training as an indicator of the accuracy of the model for predictions on new data.

3.6.1 Single model class

For example, when we decide to work with the class of linear regression models \(h(\mathbf{x}) \in \mathcal{H}_{linear}\), so that \(h(\mathbf{x}) = \mathbf{x}^T \mathbf{w}\), the model class is fixed a priori (from the beginning). Therefore there is nothing to select from. We can only train (learn) the model within the given class by minimizing the problem-specific objective over the training data \(S_n\) (e.g. the training MSE in the regression case). The optimal model \(\hat{h}(\mathbf{x}) = \mathbf{x}^T \widehat{\mathbf{w}}\) is the minimizer of the training loss found by using the selected algorithm. There is just one such optimal model and therefore there is nothing to select from!

3.6.2 Multiple model classes

In contrast, we may decide to explore multiple classes of models. We have seen an example of classes of polynomials of increasing degree, \(h^{(1)}(\mathbf{x}) \in \mathcal{H}_{linear}\), \(h^{(2)}(\mathbf{x}) \in \mathcal{H}_{quadratic}\), \(h^{(3)}(\mathbf{x}) \in \mathcal{H}_{cubic}\), etc., so that \(h^{(i)}(\mathbf{x}) = \phi^{(i)}(\mathbf{x})^T \mathbf{w}^{(i)}\), where \(\phi^{(i)}(\mathbf{x})\) is a suitable feature transformation function. But the classes may be less related to one another. For example, for a classification problem the classes my be \(h^{(1)}(\mathbf{x}) \in \mathcal{H}_{perceptron}\), \(h^{(2)}(\mathbf{x}) \in \mathcal{H}_{logistic}\), \(h^{(3)}(\mathbf{x}) \in \mathcal{H}_{neuralnet}\), etc. Another example of different model classes are neural nets with different architectures. Yet another is standard models with different regularization functions - these we will see soon in our course.

Once we decided which classes to explore, we use the training data \(S_n\) to learn the model of each class, that is find for each class the optimal model \(\widehat{h^{(i)}}(\mathbf{x}) =\phi^{(i)}(\mathbf{x})^T \widehat{\mathbf{w}^{(i)}}\) by minimizing the problem-specific objective. Out of these multiple optimal models (one per each class) we then typically want to select only a single model to keep for future work, for predictions on new data.

Clearly, the model we want to keep is the one that is likely to predict the best (with the lowest errors) on new data. This is where model selection and model evaluation meet. Any of the procedures described in the section 3.5 Model evaluation can be used to evaluate the models with the caveats and pros and cons explained there. However, for a full fairness of the comparisons, the evaluation procedure should be exactly the same for each of the competing models. For example, if we use random splits in a cross-validation procedure, the splits should be exactly the same when evaluating all the models. Moreover, all the settings of your evaluation procedure shall be well explained and documented to make your work transparent, trustful and reproducible!

3.6.3 Bias-variance trade off

What we noted already in the homework Ex4 part2: feature transformation is that when we use different training data \(S_i, \, i=1, \ldots, k\) to learn the models \(\hat{h}_i\), these models can be rather different. In result, there is quite a lot of variability in their predictions \(\hat{h}_i(x), \, i=1, \ldots, k\) for any single data point \(x\). This variability in the models and their predictions based on their underlying training sets has an important consequence for the error analysis.

Using an independent test set, we could calculate the test set error for each of the samples as \(E_i = \frac{1}{n}\sum_j^n (\hat{h}_i(x_j) - y_j)^2\) and then estimate the generalization error, similarly as in the cross-validation procedure, as the average of these errors.

\[\hat{E} = \frac{1}{k}\sum_i^k E_i = \frac{1}{k}\sum_i^k \frac{1}{n}\sum_j^n \big( \hat{h}_i(x_j) - y_j \big)^2\].

For simplicity, imagine our test set is very tiny. In fact, it contains only single data pair \((x,y)\). The average test error is then simply \[\hat{E} = \frac{1}{k}\sum_i^k E_i = \frac{1}{k}\sum_i^k \big( \hat{h}_i(x) - y \big)^2\].

We will now use this simplified error equation to derive an important result \[\begin{eqnarray} \hat{E} & = & \frac{1}{k}\sum_i^k E_i = \frac{1}{k}\sum_i^k \big( \hat{h}_i(x) - y \big)^2 \\ & = & \frac{1}{k}\sum_i^k \big( \hat{h}_i(x) - \frac{1}{k}\sum_i^k \hat{h}_i(x) + \frac{1}{k}\sum_i^k \hat{h}_i(x) - y \big)^2 \\ & = & \underbrace{\frac{1}{k}\sum_i^k \big( \hat{h}_i(x) - \frac{1}{k}\sum_i^k \hat{h}_i(x) \big)^2}_A + \underbrace{\frac{1}{k}\sum_i^k \big( \frac{1}{k}\sum_i^k \hat{h}_i(x) - y \big)^2}_B + 2 \underbrace{\frac{1}{k}\sum_i^k \big( \hat{h}_i(x) - \frac{1}{k}\sum_i^k \hat{h}_i(x) \big) \big( \frac{1}{k}\sum_i^k \hat{h}_i(x) - y \big)}_C \end{eqnarray}\]

For the \(C\) term we have \[\begin{eqnarray} \frac{1}{k}\sum_i^k \big( \hat{h}_i(x) - \frac{1}{k}\sum_i^k \hat{h}_i(x) \big) \big( \frac{1}{k}\sum_i^k \hat{h}_i(x) - y \big) & = & \big( \frac{1}{k} \sum_i^k \hat{h}_i(x) - \frac{1}{k}\sum_i^k \hat{h}_i(x) \big) \big( \frac{1}{k}\sum_i^k \hat{h}_i(x) - y \big) \\ & = & \big( 0 \big) \big( \frac{1}{k}\sum_i^k \hat{h}_i(x) - y \big) = 0 \end{eqnarray}\]

For the \(B\) term we have \[\begin{eqnarray} \frac{1}{k}\sum_i^k \big( \frac{1}{k}\sum_i^k \hat{h}_i(x) - y \big)^2 & = & \big( \frac{1}{k}\sum_i^k \hat{h}_i(x) - y \big)^2 = \big( bias \big)^2 \end{eqnarray}\]

For the \(A\) term we have \[\begin{eqnarray} \frac{1}{k}\sum_i^k \big( \hat{h}_i(x) - \frac{1}{k}\sum_i^k \hat{h}_i(x) \big)^2 & = & \frac{1}{k} \sum_i^k \big( \hat{h}_i(x) - \frac{1}{k}\sum_i^k \hat{h}_i(x) \big)^2 & = & variance \end{eqnarray}\]

Therefore we get this important result for the generalization error estimate \(\hat{E}\) calculated by averaging the errors of hypotheses \(\hat{h}_i\) learned over different training samples \(S_i\) \[\hat{E} = \frac{1}{k}\sum_i^k E_i = \big( bias \big)^2 + variance \enspace ,\]

where the \(bias\) term represents the extent to which the average of the predictions over all the models \(\frac{1}{k}\sum_i^k \hat{h}_i(x)\) differs from the desired true output value \(y\), and the \(variance\) term describes how much the predictions of the individual models \(\hat{h}_i(x)\) vary around their average \(\frac{1}{k}\sum_i^k \hat{h}_i(x)\).

In the above we showed the relation between the generalization error estimated over a single-sample test set. But this can be easily extended to larger samples (by simply calculating an extra average over all the points in the test set) and in fact holds even when not working with test sample averages but with the population averages in terms of expectations.

An important consequence of the above result is that there are in principal two ways to minimise the generalization error. One is to reduce the bias of our hypotheses, that is whatever training sample we use, on average the hypotheses shall be as close as possible to the true values. The other is to reduce the variance in the hypotheses, that is the hypotheses shall not vary too much when we use different training sample.

We have actually seen this informally in the homework Ex4 part2: feature transformation already. The 12-degree polynomial models estimated from different training samples varied a lot and indeed reached a very large test error. The 3rd-degree polynomial models seemed more similar to each other, they varied a lot less, and in consequence reached a lot lower generalization error.