Description
In this assignment, you will train and evaluate different kernels for both classification and regression on three datasets. Please install Python 3.6 via Anaconda on your personal machine. For this homework you will only be using numpy, scipy, sklearn and matplotlib packages. Download the homework file HW03.zip via Moodle. Unzipping this folder will create the directory structure shown below, HW03 — HW03.pdf — Data |–Synthetic |–Shellfish |–Currency — Submission |–Code |–Figures |–Predictions |–Shellfish |–Currency The data files for each data set are in ‘Data’ directory respectively. You will write your code under the Submission/Code directory. Make sure to put the deliverables (explained below) into the respective directories. Deliverables: This assignment has three types of deliverables: • Report: The solution report will give your answers to the homework questions (listed below). Try to keep the maximum length of the report to 5 pages in 11 point font, including all figures and tables. Reports longer than five pages will only be graded up until the first five pages. You can use any software to create your report, but your report must be submitted in PDF format. You can use an additional two pages to answer extra credit questions only. • Code: The second deliverable is the code that you wrote to answer the questions, which will involve implementing kernel methods. Your code must be Python 3.6 (no iPython notebooks or other formats). You may create any additional source files to structure your code. However, you should aim to write your code so that it is possible to re-produce all of your experimental results exactly by running python run_me.py file from the Submissions/Code directory. • Kaggle Submissions: We will use Kaggle, a machine learning competition service, to evaluate the performance of your regression models. You will need to register on Kaggle using a *.edu email address to submit to Kaggle (you can use any user name you like). You will generate test prediction files, save them in Kaggle format (helper code provided called Code/kaggle.py) and upload them to 1 Kaggle for scoring. Your scores will be shown on the Kaggle leaderboard. The Kaggle links for each data set are given under respective questions. Submitting Deliverables: When you complete the assignment, you will upload your report and your code using the Gradescope.com service. Place your final code in Submission/Code, and the Kaggle prediction files for your best-performing submission only for each data set in Submission/Predictions//best.csv. Naming your files something other than best.csv breaks our grading scripts. Please try to name them best.cav. If you used Python to generate report figures, place them in Submission/Figures. Finally, create a zip file of your submission directory, Submission.zip (NO rar, tar or other formats). Upload this single zip file on Gradescope as your solution to the ’HW03-Kernels’ assignment. Gradescope will run checks to determine if your submission contains the required files in the correct locations. Finally, upload your pdf report to the ’HW03-Kernels-PDF’ assignment. When you upload your report please make sure to select the correct pages for each question respectively. Failure to select the correct pages will result in point deductions. The submission time for your assignment is considered to be the later of the submission timestamps of your code, report and Kaggle submissions. Some students have requested to be able to submit an IPython notebook to save time. This is permissible if you just export the notebook to a .pdf and upload that .pdf to gradescope. However, the same rules apply as if you prepared the report using any other writing system! In particular, your code should not be in the notebook itself (other than perhaps a tiny command like plot_answer_2b() before each plot. Academic Honesty Statement: Copying solutions from external sources (books, internet, etc.) or other students is considered cheating. Sharing your solutions with other students is also considered cheating. Posting your code to public repositories like GitHub, stackoverflow is also considered cheating. Any detected cheating will result in a grade of -100% on the assignment for all students involved, and potentially a grade of F in the course. 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.
