Exercises

{0}------------------------------------------------

$\text{CS}4220$ laboratory course manual

2019

David M.J. Tax, Marco Loog

Image /page/0/Picture/4 description: The image shows the logo for "studeersnel". The logo consists of a stylized "S" symbol to the left of the word "studeersnel", which is written in a bold, sans-serif font.

{1}------------------------------------------------

{2}------------------------------------------------

Image /page/2/Picture/2 description: The image contains the number 3.

Image /page/2/Picture/3 description: The image contains the text "Dit document is beschikbaar op".

{3}------------------------------------------------

{4}------------------------------------------------

Course contents and goals

This course will provide you with a practical introduction to pattern recognition and machine learning. The techniques are discussed at a level such that you will be able to apply them in your research. The emphasis is on using the computer as a tool for pattern recognition. Starting from the basis for any pattern recognition application, measurements, the topics discussed will be:

• $\bullet$ classification:
• $\bullet$ evaluation;
• complexity;
• $\bullet$ regression;
• feature selection and extraction;
• $\bullet$ clustering.

After you have succesfully completed this course, you should:

• understand pattern recognition theory to such an extent that he/she is able to read recent literature on the topic in engineering-oriented journals (e.g. IEEE Tr. on PAMI);
• know which statistical methods to apply to which problems, on which assumptions they are based and how these methods interrelate;
• be able to construct a learning system to solve a given simple problem, using existing $\text{software.}$

Prior knowledge

Basic working knowledge of multivariate statistics and linear algebra is required to follow the course. Next to that, it is expected that you have had the course CSE22A Machine Learning, or something comparable.

Software Originally, this course use MATLAB to do the programming exercises. After many requests, the change to Python is made. Although both programming languages are very

studeersnel

{5}------------------------------------------------

similar, the devil is in the details. It may be, that in some locations, still MATLAB notation is used. Please let us know when you find something!

You get get PRTOOLS for Python from https://github.com/DMJTax/prtools.

Notation

Most weeks contain a few optional exercises, indicated like this:

_ OPTIONAL .

An exercise between these lines is optional. This means that you are not required to do it. It can give you some extra background and tips. Only work on it if you think the subject is interesting and if you have sufficient time left.

$\_$ END OPTIONAL $\_$

Some other notational conventions are:

$\bullet$ Variables and code will be indicated using the teletype font (for example: $x$ , $mean(x)$ ). For larger pieces of code, we will use the notation:

>>> % A piece of test code
>>> import numpy as np
\gg x = np.random.rand(10,2);
>>> np.mean(x)
\gg np.std(x)

Here, $\gg$ is the prompt. If pieces of code are not preceded by $\gg$ it will mean it's wiser to write a script.

• $\bullet$ An alert sign like the one in the margin here indicates it is essential you read the text next to it carefully.

⊠್

• $X,$ Slides
• A book sign indicates where you can read more on the theory behind the subject discussed. Numbers indicate chapters and sections in "Statistical Pattern Recognition". "Slides" means the theory is discussed in the slides, which can be downloaded in handout format from the Blackboard site.

Image /page/5/Picture/15 description: The image contains the number 6.

{6}------------------------------------------------

$\text{Week 1}$

Basics of Machine Learning

Objectives When you have done the exercises for this week, you

• should be able to mathematically derive decision boundaries given simple probability density functions,
• should be able to perform simple computations with Bayes' rule,
• should be familiar with working under Python,
• understand some PRTOOLS commands,
• know what an object and a dataset are,
• should be able to construct, visualize and classify some simple datasets.

Decision Theory $1.1$

Exercise 1.1 (a) Assume that we managed to represent objects from a two-class classification problem by a single feature. We know that the objects from class $\omega_1$ have a Gaussian distribution with $\mu_1 = 0$ and ${\sigma }_1^2=$ , and the objects from class have a Gaussian distribution with and . Derive the position of the decision boundary when both class priors are equal.

(b) Again, assume we have a two-class classification problem in a 1D feature space, but now assume that objects from class $\omega_1$ have a uniform distribution between 0 and 1, and objects from class $\omega_2$ have a uniform distribution between 2 and 3. Where is the decision boundary now?

(c) And where is the decision boundary when the objects from class $\omega_2$ have a uniform distribution between 0.5 and 1.5? (The distribution of $\omega_1$ did not change, classes have $equal prior.)$

(d) And where is the decision boundary when the objects from class $\omega_2$ have a uniform distribution between 0.5 and 2.5? (The distribution of $\omega_1$ did not change, classes have $equal prior.)$

Exercise 1.2 (a) Assume we represent the objects in a two-class classification problem by $\mathbf{L}$ a single feature. We know that the objects from class $\omega_1$ have a Gaussian distribution

Image /page/6/Picture/17 description: The image is a blank white square.

(L

$2.2$

Image /page/6/Picture/18 description: The image shows the logo for Studeersnel. The logo consists of a stylized "S" symbol to the left of the word "studeersnel" in bold, sans-serif font.

{7}------------------------------------------------

with $\mu_1 = 0$ and $\sigma_1^2 = 1/2$ , and the objects from class have a Gaussian distribution with and . Derive the position of the decision boundary when both class priors are equal, but we have a loss matrix of:

L = \left[ \begin{array}{cc} 0 & 0.5 \\ 1.0 & 0 \end{array} \right]. \tag{1.1}

$(b)$ Assume again we have a two-class classification problem in a 1D feature space, but now assume that objects from class $\omega_1$ have a uniform distribution between 0 and 1, and objects from class $\omega_2$ have a uniform distribution between 0.5 and 2.5. Given the loss matrix , where is the decision boundary now?

Image /page/7/Figure/3 description: The image is a graph with two lines. The x-axis ranges from -2 to 4, and the y-axis ranges from 0 to 1. The first line is a dashed line that starts at (-1, 0), goes up to (0, 1), and then goes down to (1, 0). The second line is a solid line that starts at (0, 0), goes up to (2, 0.5), and then goes down to (4, 0). The y-axis is labeled p(x|ωi), and the x-axis is labeled x.

Figure 1.1: The class-conditional probabilities of two classes $p(x|\omega_1)$ (dashed blue line) and $p(x|\omega_2)$ (solid black line) in a 1-dimensional feature space.

Exercise 1.3 In figure 1.1 two triangular-shaped class conditional probability density functions are given. The first one $p(x|\omega_1)$ is indicated by a dashed blue line and the second $p(x|\omega_2)$ with a solid black line. The class priors are assumed equal here.

(a) Again, use the Bayes' rule to derive the class posterior probabilities of the following objects: $x = 3, x = -0.5, x = +0.5$ . To which class are the objects therefore $assigned?$

• (b) Which object is on the decision boundary of the Bayes classifier?
• Exercise 1.4 Now assume that class $\omega_1$ in figure 1.1 is twice as small as class $\omega_2$ . That means $p(\omega_1) = 1/3$ and .

{8}------------------------------------------------

Prools for Python $1.2$

In order to learn something about many machine learning methods, the toolbox PRTools was developed. Originally, it is a MATLAB toolbox, but it has been, provisionally, translated into PYTHON. It should mimic the most important parts of PRTOOLS for MATLAB.

Again, you get get PRTools for Python from https://github.com/DMJTax/prtools.

The advantages of PRTOOLS (for MATLAB or PYTHON) are:

• 1. A uniform interface to datasets and mappings. It is very straightforward to wrap datasets or machine learning algorithms in mappings. This then allows for a consistent visualisation, fitting and evaluation of models.
• 1. This standarization also allows for the combination (in particular, the sequential stacking) of mappings. This makes it very easy to combine preprocessing steps, feature reduction methods and classfiers or regressors into one mapping. The training and evaluation of such combined mappings is identical to the training and evaluation of a single mapping.

Of course, you are not required to use PRTOOLS. If you feel more comfortable with (for instance) scikit-learn, please use that. But then we will not be able to help with bugs or implementation problems.

When you are starting with PYTHON, we assume that you already imported numpy and $\text{PRTools}, \text{like}^1$ :

>>> import numpy as np
>>> import prtools as pr

For plotting purposes we also use matplotlib, so also include:

>>> import matplotlib.pyplot as plt

$1.3$ $\text{Datasets}$

One key entity in Machine Learning is the idea of an object. We always assume we can represent any object by a set of values, often just measurements. Whatever object we are considering, in order to perform operations on an object by a computer, we have to encode this object by some numbers. An object in real life and in the computer are therefore two different things. Furthermore, in this course we will use the convention that each object is represented by a row vector of measurements (thus an $1 \times d$ array).

When you want to conclude something from data, it is often not from one object, but from a set of objects. We assume we have a set of objects from which we want to obtain some knowledge. This set is called a dataset. A dataset is a set of n objects and is stored in a $n \times d$ array.

After you have specified the problem you want to solve, you have to collect examples and do measurements on these examples. For that, you have to define what features are likely to be informative for the problem you specified.

Image /page/8/Picture/18 description: The image shows the logo for "studeersnel". The logo consists of a stylized "S" shape on the left, followed by the word "studeersnel" in a sans-serif font. The "S" shape is black and has a white diamond shape in the middle.

Image /page/8/Picture/19 description: The image shows a cursor with a hand pointing to the left.

$^{1}$ To get the Python code, please have a look at the link given on page 6.

{9}------------------------------------------------

Exercise 1.6 (a) Make a fake dataset containing 10 objects with 3 measurements each. Invent the measurement values yourself. Below is an example piece of code which fills the matrix $x$ with 2 objects, each containing 3 measurements:

$\gg x = \text{np.array}([[ 0.7,0.3,0.2],[2.1,4.5,0]])$

Make your own matrix $x$ .

(b) Compute the means (using np.mean) and standard deviations (np.std) of your 3 measurements of 10 objects. What is the difference between $mean(x), mean(x, axis=0)$ and $mean(x, axis=1)$ ?

Exercise 1.7 (a) When a dataset contains just two features per object, it can be visualized in a scatterplot (we come back to this later). Make a scatterplot by:

$pltscatter(x[:,0],x[:,1])$

Looking at the data matrix you created in Exercise 1.6, find out which object is plotted where in the plot.

(b) When you look at the scatterplot, can you identify outlier objects, or structure in the data?

When the dataset is used to train classifiers, it is also required that for each object a class label is present. This indicates from which class the object originates, according to the expert $(i.e. you).$

Exercise 1.8 (a) Invent labels for the objects that you defined in the previous question. The labels can be numbers, like 1 or 2. Store them in a column vector lab, and create a PRTools dataset by

lab = $np.array([1,1,1,1,2,2,2,2,2,2])$ .T a = pr.prdataset(x,lab)

Check if the resulting dataset has the correct number of objects, the correct number of features and correct number of classes (correct here means: what you expect). You can do that by just typing the variable on the Matlab command line:

print(a)

A scatterplot is the most simple plot you can make: it simply plots the first measurement against the second measurement. If you have three measurements, you can use 3D plots; if you have even more, you will have to select at most three of them by hand (although later we will discuss ways of visualising more measurements at once).

Exercise 1.9 Load the dataset "boomerangs" (use the function boomerangs and choose the number of objects to generate).

(a) Use pr.scatterd(a) to make a scatterplot of the first two features, and $prƙ$ (a[:,[1,2]]) for the features 2 and 3 (note that Python starts counting with $0$ ).

{10}------------------------------------------------

There are many other (artificial) datasets defined in PRTOOLS. The table below lists a few of them:

1.4 Creating mappings and decision boundaries

On the prdataset you can perform operations. If the dataset is labeled, you can train a classifier. If the dataset has arbitrary real-valued targets, you can train a regressor. But you can also do feature normalisation, feature reduction, or clustering. All these operations are stored in a $\text{prmapping}$ .

Assume we want to train a nearest mean classifier on the Banana dataset. In PRTOOLS you do:

>>> a = pr.gendatb()
\gg w = pr.nmc(a)
>>> print(w)
Nearest mean, 2 to 2 trained mapping

When a mapping is trained, it can be applied to a dataset using the operator *: $\gg b = a*w$ >>> print(b) Banana dataset 100 by 2 prdataset with 2 classes: [50 50]

The result of the operation $a*w$ is again a dataset. It is the classified, rescaled or mapped result of applying the mapping definition stored in $w$ to $a$ .

For mappings which change the labels of the objects (so the mapping is actually a classifier) the routines labeld and testc are useful. labeld and testc are the general classification and testing routines respectively. They can handle any classifier from any routine.

\gg lab = b*pr.labeld()
>>> print(lab)
[[-1][-1][-1][-1]...
 [ 1]
 [ 1]]
>>> e = b*pr.testc()
0.14

Note that in the above examples we use the typical MATLAB conventions: everything is a matrix, and operations are often defined in terms of 'multiplication' *. If you prefer the

Image /page/10/Figure/11 description: The image shows a hand cursor pointing to the left.

studeersnel

{11}------------------------------------------------

PYTHON way of working, you can also call the methods explicitly:

a = pr.gendatb() $\gg w = \text{pr.nmc()}$ >>> w.train(a) $\gg$ b = w.eval(a) >>> e = pr.testc(b)

A few of the available classifiers is listed below:

The list is not complete. Feel free to add your favorite classifier!

Some classifiers require additional hyperparameters to be specified. For instance, in the support vector classifier, you can specify the kernel, a kernel parameter, and a regularisation parameter. Or in the k-nearest neighbor classifier you can specify the number of neighbors k. You can supply that as additional input during training:

$w = pr.svc(a,(`rbf`,4.5,1))$

You can also specify an untrained mapping beforehand with the required hyperparameters, and train it afterwards on some training set:

>>> u = pr.svc((\text{"rbf"},4.5,1))\gg w = a*u\text{or}>>> w = pr.svc((\text{"rbf"},4.5,1))>>> w.train(a)

Finally, you can also visualise the decision boundary of classifiers. This is done using the function plotc. In order to see the relevant region in the feature space, first a scatterplot of the (training) dataset has to be made. For example:

>>> a = pr.gendath()
\gg w = pr.parzenc(a)
>>> pr.scatterd(a)
>>> pr.plotc(w)

Exercise 1.10 Practice the use of PRTOOLS. Create some of the artificial datasets, make scatterplots of the data, train some classifiers and plot their decision boundaries.

{12}------------------------------------------------

(a) Train a classifier and plot its decision boundary (together with the training set). Can you verify that the function tests gives the correct classification rate on the training set as you see in the plot?

$1.5$ Density estimation using Parzen densities

Next to classifiers, PRTOOLS also has the possibility to estimate densities. In this section we are going to estimate the density using a Parzen density estimator, called parzenm in $\mathbf{PRTools}.$

Exercise 1.11 (a) We start with creating a simple dataset with:

>>> a = pr.gendats([20,20],1,8);

(Type $help(pr.\text{gendats})$ to understand what type of data we have now.)

(b) We define the width parameter $h$ for the Parzen kernel:

$h = 0.5$ :

$(c)$ The function parzenm estimates a density for a given dataset. In most cases a PRTOOLS prdataset is labeled, and these labels are used in the function parzenm to estimate a density for each class. To define a Parzen density estimator with a certain width parameter $h$ on the entire dataset, ignoring labels, type:

\gg a = pr.prdataset(+a)
\gg w = pr.parzenm(a,h)

This mapping can now be plotted along with the data:

>>> pr.scatterd(a); pr.plotm(w)

If your graphs look a little "bumpy", you can increase the grid size PRTOOLS uses for plotting:

>>> pr.plotm(w,gridsize=100)

and try the above again.

(d) Plot the Parzen density estimate for different values of h. What is the best value of h?

When you want to evaluate a fit of a density model to some data, you have to define an error. One possibility is to use the log-likelihood, defined as:

\text{LL}(\boldsymbol{X}) = \log\left(\prod_{i} \hat{p}(\boldsymbol{x}_{i})\right) = \sum_{i} \log\left(\hat{p}(\boldsymbol{x}_{i})\right) \tag{1.2}

studeersnel

The better the data $\boldsymbol{x}$ fits in the probability density model $\hat{p}$ , the higher the values of $\hat{p}(\boldsymbol{x})$ will be. This will result in a high value of . When we have different probability density estimates , we have to use the one which has the highest value of LL.

Note that when we fill in different values for the width parameters $h$ in the Parzen density estimation, we have different estimates $\hat{p}$ . Using the log-likelihood as a criterion, we can optimize the value of this free parameter $h$ to maximise LL.

{13}------------------------------------------------

To get an honest estimate of the log-likelihood, we have to evaluate the log-likelihood $(1.2)$ on a test set. That means that we have to make (or measure) new data from the same distribution as where the training data came from. When we would evaluate the log-likelihood on the data on which the probability density was fitted, we would get a too optimistic estimation of the error. We might conclude that we have fitted the data very well, while actually a new dataset from the same distribution does not fit in the density at all! Therefore, if you want to evaluate the performance of an estimated $\hat{p}$ , use an independent test set!

Exercise 1.12 Use the data from the same distribution as in the previous exercise to train a Parzen density estimator for different values of $h$ . Compute the log-likelihood of this training set given the estimated densities (for different $h$ ):

# Generate data
   a = pr.gendats([20, 20], 1, 8)a = pr.prdataset(+a)hs = [0.01, 0.05, 0.1, 0.25, 0.5, 1, 1.5, 2, 3, 4, 5] # Array of h's to try
LL = np.zeros(len(hs))for i in range(len(hs)):
                                              # For each h...
   w = pr.parent(a, hs[i])#
                                                  estimate Parzen density
   LL[i] = np.sum(np.log(+(a*w)));#
                                                  calculate log-likelihood

# Plot log-likelihood as function of h

(since w is the estimated density mapping w, the estimated density $\hat{p}$ for objects in a dataset a is given by $+(a*w)$ .

plt.plot(hs,LL);

(a) What is the optimal value for $h$ , i.e. the maximal likelihood? Is this also the best density estimate for the dataset?

Exercise 1.13 (a) Use the same data as in the previous exercise, but now split the data into a training and test set of equal size. Estimate a Parzen density on the training set and compute the Parzen density for the test set. Compute the log-likelihood on both the training and test sets for $h = [0.1, 0.25, 0.5, 1, 1.5, 2, 3, 4, 5]$ . Plot these log-likelihood vs. $h$ curves:

[trn, tst] = pr.gendat(a, 0.5)# Split into trn and tst, both 50%
hs = [0.01, 0.05, 0.1, 0.25, 0.5, 1, 1.5, 2, 3, 4, 5] % Array of h's to try
\text{Ltrn} = \text{np.zeros}(\text{len}(\text{hs}))\text{Ltst} = \text{np.zeros}(\text{len}(\text{hs}))for i in range(len(hs)):
                                                # For each h...
   w = pr.parent(\text{trn,hs[i]})estimate Parzen density
                                                #
   \text{Ltrn}[i] = np.sum(np.log+(\text{trn}*w)))#
                                                     calculate trn log-likelihood
   \text{Ltst}[i] = np.sum(np.log+(tst*w)))#
                                                     calculate tst log-likelihood
plt.plot(hs,Ltrn,'b-')
                                    # Plot trn log-likelihood as function of h
plt.plot(hs,Ltst,'r-')
                                         # Plot tst log-likelihood as function of h
What is a good choice of h?

This week you saw the basis of machine learning: object definition, data collection, and Bayes' rule. Starting from good measurement data, the rest of the analysis (visualisation, clustering,

{14}------------------------------------------------

classification, regression) becomes much easier. Starting from poorly defined objects or poorly sampled datasets with insufficient example objects, your analysis becomes very hard and no clear conclusions will be possible (except that more data is needed).

Image /page/14/Picture/2 description: The image contains the text "Dit document is beschikbaar op" on the left, followed by a logo and the word "studeersnel" on the right. The logo is a stylized "S" shape.

{15}------------------------------------------------

{16}------------------------------------------------

$\text{Week 2}$

Complexity

Objectives When you have done the exercises for this week, you

• should know the fundament of the support vector classifier (i.e. maximum margin),
• should be able to kernelize a nearest mean classifier,
• optimise a hyperparameter using crossvalidation.

$2.1$ The Support Vector Machine, svc

Exercise 2.1 Consider the following 2D two-class data set. Class one contains two points: $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$ and $\begin{bmatrix} 0 \\ 3 \end{bmatrix}$ . Class two has a single data point: .

(a) Determine the classifier that maximizes the margin on this classification problem, using a graphical/geometrical reasoning (probably you cannot do the minimization of the support vector error function by hand). How many support vector are obtained.

Shift the first point above, $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$ , to $\begin{bmatrix} 0 \\ -1 \end{bmatrix}$ .

(b) How does the new maximum margin classifier look? What happened to the number of support vectors?

• Exercise 2.2 (a) Demonstrate, possibly graphically/geometrically, that the support vector classifier is sensitive to feature scaling. Hint: this can be done in 2D based on a training set of size 3 (like in $(a)$ and $(b)$ ) and a single test point.
• Exercise 2.3 (a) Reconsider the 2D configurations from $5.2 \text{ (a)}-\text{(b)}$ above and compare the solution of the LDA classifier to those obtained by means of an SVM. In what cases do they differ? Do you see the pattern?

___ OPTIONAL ___

Exercise 2.4 Make exercise $3.17$ in the book.

$\_$ END OPTIONAL $\_$

Image /page/16/Picture/18 description: The image shows the logo for Studeersnel. The logo consists of a stylized 'S' symbol on the left, followed by the word 'studeersnel' in a bold, sans-serif font.

Section $3.8$

{17}------------------------------------------------

$2.2$ The Nonlinear Support Vector Machine, svc

Exercise 2.5 (a) Assume we have two objects, represented by 1-dimensional feature vectors x and $\chi$ . Find a feature mapping $\phi$ that leads to the inner product $\exp(-(x-\chi)^2)$ . Hints: expand the term $-$ and write as a series based on the Taylor series of the exponential.

(b) What is the dimensionality of the space that $\phi$ maps a 1-dimensional feature vector $to?$

Exercise 2.6 Let's kernelize nmc.

(a) Express the distance to any class mean in terms of regular inner products between the test point x and, say, the $N_C$ samples $x_i^C$ from class C.

(b) Kernelize the nearest mean classifier by mean of the Gaussian kernel, $K(x,\chi)$ = $\exp(-\frac{\|x-\chi\|^2}{2\sigma^2})$ . Can you show that this boils down to something like a Parzen classifier? You may limit yourself to the two-class case.

• Exercise 2.7 The function svc can be used to both construct linear and nonlinear support vector machines. The following kernels $K$ are defined: 'linear' $linear \; kernel \; (default)$
  • 'polv' polynomial kernel with degree par

To define the kernel in svc, supply a second input argument with a list of kernel type, kernel parameter, and tradeoff parameter $C$ : \texttt{svc(a, (kernel_type, par, C))} .

(a) On $a = \text{gendatb}([20,20])$ , train an svc with a rbf' kernel, i.e., the Gaussian kernel, for kernel widths that vary from fairly small $(0.1?)$ to fairly large $(10?)$ . Check with a large (enough) independent banana test set how the performance varies for the different choices of kernel widths.

(b) How does the kernel width of parzenc relate to the width of the radial basis function?

(c) Why can the $\texttt{svc}$ , potentially, perform much faster at test time than the Parzen $\text{classifier?}$

Exercise 2.8 The prcrossval function allows you to perform a cross-validation on a given data set using a particular classifier. You should supply a dataset, an untrained mapping and, optionally, the number of folds. The function then returns an error estimate for each of the folds:

e = prcrossval(a,svc([],('rbf',2.0,1.),k=10)

Given the banana dataset with 200 objects per class, $a = \text{gendatb}([200, 200])$ , we want to optimise the hyperparameter of an RBF support vector classifier.

(a) Choose a range of possible hyperparameter-values for the radial basis kernel (something like $s = [0.2, 0.5, 1.0, 2.0, 5.0, 7.0, 10.0, 25.0]$ ?). Estimate for each s the crossvalidation error. Which $s$ is optimal?

{18}------------------------------------------------

$\text{Week 3}$

Regression and Some Related Stuff

It should be noted that these exercises are meant to give you both some practice with the material covered in the lectures and the literature and an impression of what you are expected to know. Besides this, there are some exercises deemed optional, which are just, well, optional. So, judge for yourself which exercises you need to, want to, or should practice. There are probably too many to go through in the 2 hours of exercise lab that we have. On another note, at this point, the lecturer (ML) cannot claim that all exercises are thoroughly checked, though he really did his best.¹ If you think something is wrong, unclear, etc., let us (i.e., me , any of the other lecturers, or any of the $TAs$ ) know.

Objectives When you have done the exercises for this week, you should

• be able to formulate the basic least squares regression models (regularized, probabilistic, etc.) and derive its optimal estimators,
• comprehend the idea and use of polynomial, transformed, and kernelized regression,
• be capable of identifying the trade-off between bias and variance in regression and classification and measure it,
• be able to formulate $L_1$ regularization and understand its feature selection abilities,
• understand how Fisher's linear discriminant is formulated in terms of standard linear regression,
• appreciate the general formulation of a learning problem in terms of hypotheses, $loss, and regularizer,$

$3.1$ Linear Least Squares without and with Intercept

Exercise 3.1 Consider standard linear regression with the squared loss as the performance $\mathbf{S}$ $measure:$

$\sum_{i=1}^{N} (x_i^T w - y_i)^2 = \|Xw - Y\|^2.$ (3.1)

studeersnel

$^{1}$ Sure he did...

{19}------------------------------------------------

Note that in the expression above there is some confusing notation going on. The (feature) vector $x_i \in \mathbb{R}^d$ is a column vector, while all features per object in $X \in \mathbb{R}^{N \times d}$ are in rows. is an -vector with all corresponding outputs.

The aim is to minimizing this sum of squared residuals between the linearly predicted and actual output over $w \in \mathbb{R}^d$ .

(a) Assume that $(X^T X)^{-1}$ exists. Show that $(X^T X)^{-1} X^T Y$ gives a least squares solution to the above problem, i.e., it minimizes .

(b) Given that $(X^T X)^{-1}$ exists, what does that tell us about the data? More specifically, what limitation on the number of observations does this imply, what does invertibility say about the dimensionality of the (affine) subspace our data is in, and what difference does the presence or absence of the origin in this subspace make? To what extent are these limitations enough to guarantee invertibility?

Let us now allow for an intercept (or bias term), i.e., we also model a constant offset in the regression function. We do this by the trick of adding a column of ones to the matrix $X$ . Let $Z$ refer to this new matrix.

Consider standard linear regression (with intercept) with the squared loss as the performance measure, $||Zw - Y||^2$ , which we want to minimize for w.

Exercise 3.2 (a) Assume that $(Z^TZ)^{-1}$ exists. Show that $(Z^TZ)^{-1}Z^TY$ gives a least squares solution to this least squares problem.

(b) Given that $(Z^TZ)^{-1}$ exists, what does that tell us about how the data is scattered? Can you formulate necessary and sufficient requirements to for the existence of this inverse?

(c) Construct an example data set, for which the inverse of $X^T X$ exists, while the inverse for $Z^TZ$ does not.

Exercise 3.3 Let us consider a couple of settings in which we have very few observations. These problems may be referred to as underdetermined (do you understand the choice of adjective?).

(a) Given a data set consisting of one training point only. The input is $x = \pi$ in 1D, while the output $y$ equals e. Sketch/describe all linear solutions with intercept that minimize the squared loss on this data set.

• (b) Give a mathematical expression for the (set of) solutions of this 1D problem.
• (c) Describe how the linear least squares solutions look if $X = \begin{pmatrix} 1 & 1 \ -2 & 1 \end{pmatrix}$ and

(d) For this last problem with 2D inputs, what is the value that the minimizer takes on? In other words, what is the sum of the squared residuals in this case?

(e) Forget about the intercept for a moment and describe how the linear least squares solutions look if $X = (1, 1)$ and $Y = \pi$ .

$(f)$ Look again at the three solution sets that you have determined for the three regression problems above. Could you come up with a good rule to single out an element from every one of these three sets? What is your reason for singling out this solution?

{20}------------------------------------------------

$3.2$ Regularization

Exercise 3.4 Consider standard linear regression with the squared Euclidean norm as the $\mathbf{S}$ so-called regularizer (also referred to as $L_2$ regularization):

$\sum_{i=1}^{N} (x_i^T w - y_i)^2 + \lambda \|w\|^2 = \|Xw - Y\|^2 + \lambda \|w\|^2.$ (3.2)

The aim is to minimizing this over $w \in \mathbb{R}^d$ . The regularizer tries to keep the weights small. This form of regression is also referred to as ridge regression (ridger).

In the next exercise, we investigate the effect of this regularization term a bit. First, however, some more math.

(a) Show that $X^T X + \lambda I$ , with $\lambda > 0$ and I the $d \times d$ -identify matrix, is always invertible.

(b) Show that $(X^T X + \lambda I)^{-1} X^T Y$ gives the least squares solution to the above prob- $$

(c) Assume $\lambda$ is fixed to a positive value, what solution do you find if the data set grows larger and larger? Or in other words, how does the regularizer's influence change with a growing data set size?

• (d) What solution is obtained in the limit of $\lambda$ going to infinity?
• Exercise 3.5 We consider a regression data set where the inputs $x$ are drawn uniformly from the interval $[0, 1]$ . The corresponding outputs y are obtained by adding Gaussian noise to the inputs: $y = x + \varepsilon$ with a random sample from the standard normal distribution. You can generate regression data sets by means of . Ridge regression is carried out using ridger.

(a) Create a training data set of size 2 and a large test data set (1,000 \text{ or } 10,000 \text{ or } 10,000 \text{ or } 10,000 \text{ or } 10,000 \text{ or } 10,000 \text{ or } 10,000 \text{ or } 10,000 \text{ or } 10,000 \text{ or } 10,000 \text{ or } 10,000 \text{ or } 10,000 \text{ or } 10,000 \text{ samples will do). Study the regression fit to the training data for different amounts of regularization (using command like scatterr and plotr). Also check how the squared error varies for different $\lambda$ s (using commends like testr). Check a couple of new draws for the training set and also try a different set size of, for instance, of 100. Try regularization parameters varying from 0 (or something smallish like $10^{-3}$ ) to something larger like $10^3$ .

(b) Determine (roughly) which value for the regularization parameter gives, on average, the best performance. Determine this optimum for a training set size of 2, of $10$ , and for a training set size of 100. You can limit your search to $\lambda$ s in the range $[10^{-3}, 10^{3}]$ .

(c) Estimate the bias and the variance of the prediction using the optimal regularization parameters for the three training set sizes and compare their values to the ones obtained by the unregularized solution.

Exercise 3.6 Set up an experiment demonstrating that ridger does, in fact, not regularize the intercept.

studeersnel

{21}------------------------------------------------

$3.3$ Bias and Variance in Classification

Exercise 3.7 Generate a small Banana data set, using gendatb, say, with 10 samples per class. Let us use a linear classifier on this data set, for instance, LDA, logistic regression, or the $\text{NMC}$ .

(a) Determine which parts of this data set are as good as always misclassified. Is this a manifestation of the bias or the variance?

(b) Determine for which parts of the feature space the classifiers often disagree. Is this a manifestation of the bias or the variance?