Description
Task: In this homework you will experimenting with kernel methods for regression and classification problems using kernel ridge regression and support vector machine (SVM).
1. Kernel Ridge Regression: This is a kernel regression method. Let {xi
, yi} be the set of inputs, the
problem consists on finding the w that minimizes,
X
i
(xi
· w − yi)
2 + λkwk
2
2
(1)
where, the first term corresponds to the squared loss in the estimation, and the second is a regularization term. As seen during the lectures, one can apply a transformation to the samples (which increases
their dimensionality) and perform the linear regression in this new higher dimensional space, which
will correspond to a non-linear regression in the original space. An extremely important note regarding this is that, in order to estimate the value corresponding to a new sample xnew, only the inner
product xnew · xi
is necessary. Thus, the kernel trick is applicable.
2. SVM: This is a classification method that can assign classes to new samples using only the inner
product between the new samples and the samples in the training data. This allows us to use several
different kernels, which makes SVM an extremely powerful classification method.
2
Data: You will work with three datasets,
• Synthetic: Use this dataset to check equivalence between basis expansion and the use of kernels
in regression settings. You are provided four files: data_train.txt, label_train.txt, data_test.txt and
label_test.txt.
• Shellfish: This dataset has eight attributes and one output, all real numbers. We treat this is as
a regression problem. The attributes correspond to different features of shellfish, and the output
measures the number of rings (which helps us to compute their age) on their shells. You are provided
three files: train_x.npy, train_y.npy and test_x.npy.
• Currency: This dataset has four attributes and a binary output. We treat this as a classification
problem. The attributes are different measurements obtained by wavelet transformation of currency
notes. You are provided three files: train_x.npy, train_y.npy and test_x.npy.
Code to load datasets is provided in run_me.py. Below is a summary of the datasets, allowed python functions per dataset and performance metric to report in your HW03 pdf report which matches with Kaggle’s
performance reporting.
Dataset Python functions Use Metric
Synthetic sklearn.kernel_ridge.* Not allowed Mean squared error
Inbuilt Basis expansions Not allowed (regression)
sklearn.linear_model.Ridge Allowed
Credit Card sklearn.kernel_ridge.* Allowed Mean squared error
sklearn.model_selection.* Allowed (regression)
Tumor sklearn.svm.* Allowed Accuracy
sklearn.model_selection.* Allowed (classification)
Questions:
1. (75 points) Kernel Ridge Regression:
(11) a. Kernel Ridge Regression was introduced above. The goal is to find w that minimizes
X
i
(xi
· w − yi)
2 + λkwk
2
2
(2)
Once the optimal w, w
∗
, is found, it can be used to estimate the value of new samples as yest =
w
∗
· xnew. Show that, without using basis expansion nor kernels, the optimal w is,
w
∗ =
X
i
xi x
T
i + λ I−1X
i
xi yi (3)
(4) b. Show the solution for the case in which a basis expansion x → Φ(x) is used, what is the expression
of w
∗
?
(10) c. As mentioned above, for this type of regression the kernel trick is applicable. This means that it is
not necessary to know the transformation Φ; having an expression for Φ(x1) · Φ(x2) (inner product
of two samples in the new space) suffices. Given a new sample xnew, derive an expression for ynew
that depends only on inner products between samples.
