Instruction

This HW includes both theory and implementation problems. Please note,

• Your code must work with Python 3.5+ (you may install the Anaconda distribution of Python)

• You need to submit a report in PDF including all written deliverable and plots via Gradescope, and
all implementation codes via Canvas so one could regenerate your results.

• For non-linear classifier problem, you need to submit a Jupyter notebook for each algorithm and all
complementary python codes so one could reproduce your results. Submit your code in Problem4*.py
and replace * witn the name of classifier.

• For clustering problem, you are NOT allowed to use the implementation from scikit-learn or import
it and should submit your own implementation. Submit your code in Problem5.py.

The submission for this homework should be a single PDF file with solutions of theory problems, figures,
and any text explaining your results of programming problems via Gradescope and a single ‘zip‘
file containing all of the relevant code via Canvas.

SVM & Kernel Methods

Problem 1 (10 points) In this problem we would like to compare the solutions of hard and
soft SVMs on a linearly seperable dataset.

Let n > 1 be a fixed number. Is it true that there exists C > 0 such that for every sample
S of n training examples with binary label, which are linearly separable, the hard-SVM
and the soft-SVM (with parameter C) solutions will return exactly the same weight vector.

Justify your answer. (Hint: consider n = 2, d = 1 and S = {(x1, y1) , (x2, y2)}. Let a > 0 and
consider x1 = a, y1 = 1, x2 = −a, y2 = −1. Derive the optimal solution for hard and soft SVM
and compare the results.)

Problem 2 (10 points) In this problem you are asked to find the explicit mapping function
Φ(·) for the Gaussian kernel k (x, z) = exp − ∥x − z∥2 /2γ2 by showing that it can be
expressed as the inner product of an infinite-dimensional feature space by a mapping Φ.

a) Assume x, z ∈ R1 (only one feature per training example). Use the Taylor expansion of
the kernel function κ (to be precise, the exp(·) function) and derive the explicit mapping Φ
the kernel correspond to.

b) Answer the above question in general case where x, z ∈ Rd. Assume ∥x∥2 = ∥z∥2 = 1. EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

E-mail: easydue@outlook.com  微信:easydue

EasyDue™是一个服务全球中国留学生的专业代写公司