\documentclass[a4paper]{article} \usepackage{geometry} \usepackage{graphicx} \usepackage{natbib} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsthm} \usepackage{paralist} \usepackage{epstopdf} \usepackage{tabularx} \usepackage{longtable} \usepackage{multirow} \usepackage{multicol} \usepackage[hidelinks]{hyperref} \usepackage{fancyvrb} \usepackage{algorithm} \usepackage{algorithmic} \usepackage{float} \usepackage{paralist} \usepackage[svgname]{xcolor} \usepackage{enumerate} \usepackage{array} \usepackage{times} \usepackage{url} \usepackage{fancyhdr} \usepackage{comment} \usepackage{environ} \usepackage{times} \usepackage{textcomp} \usepackage{caption} \urlstyle{rm} \setlength\parindent{0pt} % Removes all indentation from paragraphs \theoremstyle{definition} \newtheorem{definition}{Definition}[] \newtheorem{conjecture}{Conjecture}[] \newtheorem{example}{Example}[] \newtheorem{theorem}{Theorem}[] \newtheorem{lemma}{Lemma} \newtheorem{proposition}{Proposition} \newtheorem{corollary}{Corollary} \floatname{algorithm}{Procedure} \renewcommand{\algorithmicrequire}{\textbf{Input:}} \renewcommand{\algorithmicensure}{\textbf{Output:}} \newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\norm}[1]{\lVert#1\rVert} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\Nat}{\mathbb{N}} \newcommand{\br}[1]{\{#1\}} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\argmax}{arg\,max} \renewcommand{\qedsymbol}{$\blacksquare$} \definecolor{dkgreen}{rgb}{0,0.6,0} \definecolor{gray}{rgb}{0.5,0.5,0.5} \definecolor{mauve}{rgb}{0.58,0,0.82} \newcommand{\Var}{\mathrm{Var}} \newcommand{\Cov}{\mathrm{Cov}} \newcommand{\vc}[1]{\boldsymbol{#1}} \newcommand{\xv}{\vc{x}} \newcommand{\Sigmav}{\vc{\Sigma}} \newcommand{\alphav}{\vc{\alpha}} \newcommand{\muv}{\vc{\mu}} \def\x{\mathbf x} \def\y{\mathbf y} \def\w{\mathbf w} \def\v{\mathbf v} \def\E{\mathbb E} \def\V{\mathbb V} \newcommand \expect {\mathbb{E}} \newcommand \mle [1]{{\hat #1}^{\rm MLE}} \newcommand \map [1]{{\hat #1}^{\rm MAP}} %\newcommand \argmax {\operatorname*{argmax}} %\newcommand \argmin {\operatorname*{argmin}} \newcommand \code [1]{{\tt #1}} \newcommand \datacount [1]{\#\{#1\}} \newcommand \ind [1]{\mathbb{I}\{#1\}} \newcommand \bs [1]{\boldsymbol{#1}} % TO SHOW SOLUTIONS, include following (else comment out): \newenvironment{soln}{ \leavevmode\color{blue}\ignorespaces }{} % TO ONLY SHOW HOMEWORK QUESTIONS, include following: %\NewEnviron{soln} % {} % {} \hypersetup{ % colorlinks, linkcolor={red!50!black}, citecolor={blue!50!black}, urlcolor={blue!80!black} } \geometry{ top=1in, % <-- you want to adjust this inner=1in, outer=1in, bottom=1in, headheight=3em, % <-- and this headsep=2em, % <-- and this footskip=3em, } \pagestyle{fancyplain} \lhead{\fancyplain{}{Homework 4: SVMs and Kernels}} \rhead{\fancyplain{}{10-601 Introduction to Machine Learning}} \cfoot{\thepage} \title{\textsc{Homework 4: \\ SVMs and Kernels}} % Title \newcommand{\outDate}{Sep. 26, 2016} \newcommand{\dueDate}{5:30 pm, Oct. 05, 2016} \author{\href{http://www.cs.cmu.edu/~mgormley/courses/10601b-f16/}{CMU 10601: \textsc{Machine Learning (Fall 2016)}} \\ OUT: \outDate{} \\ DUE: \dueDate{} \\ TAs: Simon Shaolei Du, Tianshu Ren, Hsiao-Yu Fish Tung} \date{} \begin{document} \maketitle \section*{Instructions} \begin{itemize} \item \textbf{Homework Submission:} Submit your answers and results to \href{https://www.gradescope.com}{Gradescope}. You will use Autolab to submit your code in Problem 2.2. For Gradescope, you will need to specify which pages go with which question. We provide a LaTeX template which you can use to type up your solutions. Please check Piazza for updates about the homework. \item \textbf{Collaboration policy}: The purpose of student collaboration is to facilitate learning, not to circumvent it. Studying the material in groups is strongly encouraged. It is also allowed to seek help from other students in understanding the material needed to solve a particular homework problem, provided no written notes (including code) are shared, or are taken at that time, and provided learning is facilitated, not circumvented. The actual solution must be done by each student alone. The presence or absence of any form of help or collaboration, whether given or received, must be explicitly stated and disclosed in full by all involved. Please refer to the course \href{http://www.cs.cmu.edu/~mgormley/courses/10601b-f16/about.html}{webpage}. \end{itemize} \clearpage \section{Support Vector Machine (50 pts + 10 pts Extra Credits)} Suppose we have the following data $$\mathcal{D} = (\mathbf{X},\mathbf{y})$$ where $\mathbf{X} \in \mathbb{R}^{d \times n}$, the $i$-th column $x_i$ are the features of the $i$-th training sample and $y_i$ is the label of the $i$-th training sample. $y \in \left\{-1,1\right\}^n$ if this is a classification problem and $y \in \mathbb{R}^n$ if this is a regression problem. \subsection{SVM for Classification (Hard Margin)} In this problem, you will derive SVM objective from large margin principle. We use linear discriminant function \[ f(x) = w^\top x \] for classification: we classify $x$ into class $-1$ if $f(x) <0$ and into class $1$ otherwise. If the data is linearly separable, and $f$ is the target function, then $y\cdot f(x) > 0$. This fact allows us to define \[ \gamma = \frac{y\cdot f(x)}{\norm{w}_2}. \] as distance of $x$ from the decision boundary, i.e., margin. \begin{enumerate} \item (20 pts) We would like to make this margin $\gamma$ as large as possible, i.e. maximize the perpendicular distance to the closest point. Thus our objective function becomes\begin{align} \max_w \min_{i=1}^n \frac{y_if(x_i)}{\norm{w}_2}. \label{eqn:maxmin} \end{align} (Think about why we use this function). Show that \eqref{eqn:maxmin} is equivalent to the following problem:\begin{align*} &\min_w \frac{1}{2}\norm{w}_2^2\\ \text{such that } & y_i\cdot \left(w^\top x_i\right) \ge 1, i=1,\cdots n. \end{align*} (Hint: Does it matter if we rescale $w \rightarrow kw$?) \begin{soln} Your answer here. \end{soln} \item (10 pts) In the linearly separable case if one of the training samples is removed, will the decision boundary shift toward the point removed or shift away from the point remove or remain the same? Justify your answer. \begin{soln} Your answer here. \end{soln} \end{enumerate} \subsection{SVM for Classification (Soft Margin)} Recall from the lecture notes that if we allow some misclassification in the training data, the primal optimization of SVM is given by $$ \begin{aligned} & \underset{w, \xi_i}{\text{minimize}} && \frac{1}{2}||w||_2^2 + C\sum_{i=1}^n\xi_i\\ & \text{subject to} && y_i(w^Tx_i) \geq 1-\xi_i & \forall i = 1,\ldots, n\\ & && \xi_i \geq 0 & \forall i = 1,\ldots, n \end{aligned} $$ Recall from the lecture notes $\xi_1,\ldots, \xi_n$ are called slack variables. The optimal slack variables have intuitive geometric interpretation as shown in Fig.~\ref{fig:svmmargin}. Basically, when $\xi_i = 0$, the corresponding feature vector $x_i$ is correctly classified and it will either lie on the margin of the separator or on the correct side of the margin. Feature vector with $0 < \xi_i \leq 1$ lies within the margin but is still be correctly classified. When $\xi_i > 1$, the corresponding feature vector is misclassified. Support vectors correspond to the instances with $\xi_i > 0$ or instances that lie on the margin. \begin{enumerate} \item (5 pts) Suppose the optimal $\xi_1,\ldots,\xi_n$ have been computed. Use the $\xi_i$ to obtain an upper bound on the number of misclassified instances. \begin{soln} Your answer here. \end{soln} \item (15 pts) In the primal optimization of SVM, what's the role of the coefficient $C$? Briefly explain your answer by considering two extreme cases, i.e., $C\rightarrow 0$ and $C\rightarrow\infty$. \begin{soln} Your answer here. \end{soln} \end{enumerate} \subsection{SVM for Regression (10 pts Extra Credits)} Let $x \in \mathbb{R}^d$ be the feature vector and $y \in \mathbb{R}$ be the label. In this question, we use a linear predictor for the label, i.e. given the feature vector, we predict the label by \[ \hat{y}\left(x\right) = w^\top x \] where $w \in\mathbb{R}^d$ is the linear coefficient vector. In this question, we consider the \textbf{epsilon insensitive loss function}, defined by\begin{align*} L_{\epsilon}\left(y,\hat{y}\right) = \begin{cases} 0 \qquad &\text{if } \abs{y-\hat{y}} < \epsilon \\ \abs{y-\hat{y}} - \epsilon \qquad &\text{otherwise}. \end{cases} \end{align*} where $\epsilon$ is a tuning parameter. To obtain a good $w$, we would like to solve the following optimization: \begin{align} J\left(w\right) = \frac{1}{n}\sum_{i=1}^{n}L_\epsilon\left(y,\hat{y}\left(x_i\right)\right) + \lambda\norm{w}_2^2. \label{eqn:svr} \end{align} \begin{enumerate} \item (2 pts) What kind of loss is $L_\epsilon$ if $\epsilon = 0$? \begin{soln} Your answer here. \end{soln} \item (3 pts) When it is beneficial to use $L_\epsilon$ for $\epsilon > 0$? Give a real world example. (Hint: think about the name of this loss function.) \begin{soln} Your answer here. \end{soln} \item (5 pts) Notice that~\eqref{eqn:svr} is not a differentiable. Show how to convert \eqref{eqn:svr} into a optimization problem whose objective is differentiable and constraints are linear by introducing slack variables. \begin{soln} Your answer here \end{soln} \end{enumerate} \section{Kernels (50 pts)} \subsection{Kernel Basics (10 pts)} \begin{enumerate} \item (5 pts) Suppose the input space is three-dimensional $\mathbf{x} = (x_1, x_2,x_3)^T$. Define the feature mapping $\phi(\mathbf{x}) = (x_1^2, x_2^2, x_3^2, \sqrt{2}x_1x_2, \sqrt{2}x_1x_3, \sqrt{2}x_2x_3)^T$. What is the corresponding kernel function, i.e. $K(\mathbf{x}, \mathbf{z})$? Express your answer in terms of $x_1, x_2, x_3, z_1, z_2, z_3$. \begin{soln} Your answer here. \end{soln} \item (5 pts) With the same feature map in the previous question, suppose we want to compute the value of kernel function $K(\mathbf{x},\mathbf{z})$ on two vectors $\mathbf{x}, \mathbf{z} \in \mathbb{R}^3$. How many additions and multiplications are needed if you \begin{enumerate} \item map the input vector to the feature space and then perform dot product on the mapped features? \begin{soln} Your answer here. \end{soln} \item compute through kernel function you derived in part (a)? \begin{soln} Your answer here. \end{soln} \end{enumerate} \end{enumerate} \subsection{Programming Kernel Perceptron (40 pts)} In this section you implement the kernel perceptron algorithm to between handwritten digits $4$ and $7$ of MNIST dataset. Also you will compare kernel perceptron with linear perceptron on a synthetic dataset. \\ For your convenience, we have provided full code for linear perceptron in \texttt{perceptron\_run.m} and starter codes for kernel perceptron in the handout, which you may download from Autolab. You may also test the correctness of your program with the offline dataset we provided, however you will be evaluated on a separate dataset on Autolab. For problem 2.1 - 2.4, you are expected to experiment on \texttt{perceptron\_train.mat} and \texttt{perceptron\_test.mat}. For problem 2.5, you are expected to experiment on \texttt{synthetic\_train.mat} and \texttt{synthetic\_test.mat}.\\ To submit the code, make sure you put all your files (excluding data) in a folder called \textbf{hw4} and run the following command in its top directory: \texttt{tar -cvf hw4.tar hw4}. Then submit the tarball created to Autolab.\\ In order to create faster code we approach the kernel perceptron by first building a kernel matrix, $K$, and then querying that kernel matrix every time we are interested in using some kernel evaluation $k(x_i, x_j)$. \\ The kernel matrix $K$ stores the evaluations of the kernel $X1 \in R^{d\times n}$ and $X2 \in R^{d\times m}$ where $X1$ is usually the training set and $X2$ the testing set. Thus, $K\in R^{n\times m}$ has dimensions $n \times m$. \\ Recall the kernel perceptron algorithm we learned in class for $x_i\in R^d$ and $y_i \in \{-1,1\}$ \begin{itemize} \item \texttt{Initialize the counting vector} $\alpha \in R^n$ \item \texttt{Iterate until convergence:} \begin{itemize} \item \texttt{For $i=1\dots n$:} \begin{itemize} \item $\hat{y_i} = \varphi(\sum_{r=1}^n\alpha_ry_rK_{i,r})$ \item \texttt{If:} $\hat{y_i} \neq y_i$\texttt{; Then:} $\alpha_i=\alpha_i+1$ \end{itemize} \end{itemize} \end{itemize} where \[ \varphi(z) = \begin{cases} -1 & \texttt{if} \mbox{ } z\leq 0 \\ 1 & \texttt{otherwise} \end{cases}. \] Note that in the code we use $a$ instead of $\alpha$. \begin{enumerate} \item (5 pts) Complete \texttt{polykernel.m}: the function \texttt{K = polykernel(X1,X2)} computes a kernel matrix of a non-homogeneous polynomial kernel of degree-3 with an offset of $1$. The kernel matrix should be constructed such that if $X1 \in R^{d\times n}$ and $X2 \in R^{d\times m}$, then $K\in R^{n\times m}$.\\ The polynomial kernel of degree-3 with an offset of $1$ is defined as: \begin{align*} k(x_i, x_j) = (x_i^Tx_j + 1)^3 \end{align*} \item (10 pts) Complete \texttt{kernel\char`_perceptron\char`_pred.m}: the function \texttt{kernel\char`_perceptron\char`_pred(a, Y, K, i)} takes in a counting vector, $a$, class labels, $Y$, the kernel matrix $K$, and the index of the sample we are interested in evaluating, $i$. The output should be the predicted label for $x_i$. \begin{soln} Submit code on Autolab. \end{soln} \item (10 pts) Complete \texttt{w = kernel\char`_perceptron.m}: the function \texttt{w = kernel\char`_perceptron(a0, X, Y)} runs the kernel perception training algorithm taking in an initial counting vector $a0$, a matrix of features $X$, and vector of labels $Y$. It outputs a learned weight vector. \begin{soln} Submit code on Autolab. \end{soln} \item (10 pts) Run \texttt{kernel\char`_perceptron\char`_run.m} on \texttt{perceptron\char`_train.mat} and \texttt{perceptronb\char`_test.mat} to perform training and see the performance on training and test sets. Report your accuracy on both datasets. \begin{soln} Submit code on Autolab. \end{soln} \item (5 pts) We have provided you linear perceptron codes and another data set: \texttt{synthetic\char`_train.mat} and \texttt{synthetic\char`_test.mat}. Please run \texttt{perceptron\char`_run.m} and report the accuracy of linear perceptron. Next test your kernel perceptron on this new data set. Compare the classification accuracy of these two methods. Which one is better? Why is this the case? \begin{soln} Your answer here. \end{soln} \end{enumerate} \section{Perceptron and Subgradient (10 pts Extra Credits) } In this problem you will find the connection between Perceptron algorithm and (stochastic) subgradient descent. First, please look at the following two definitions: \begin{definition}[Hinge Loss] For $y,y' \in \mathbb{R}$, the Hinge loss is defined by: \begin{align*} L(y,y') =\max(0,1-y\cdot y'). \end{align*} \end{definition} \begin{definition} [Subgradient] Given a function $F(x)$, which may be non-differentiable, $v(x)$ is a subgradient of $F(x)$ if and only if for any $x'$, the following holds: \begin{align*} F(x') \ge F(x) + v(x)^\top \left(x'-x\right). \end{align*} \end{definition} \begin{enumerate} \item (5 pts) Let $\left(x,y\right)$ be a sample from the training data where $x \in \mathbb{R}^d$ and $y \in \mathbb{R}$. Define $F(w) = L(y,w^\top x)$. What is the subgradient of $F(w)$? (hint: there are 3 cases). \begin{soln} Your answer here. \end{soln} \item (5 pts) For a given function $F(w) = \frac{1}{n}\sum_{i=1}^{n}F_i(w)$, Cyclic Subgradient Descent Algorithm is following procedure \begin{itemize} \item \texttt{Initialize the variable} $w \in R^d$. \item \texttt{Iterate until convergence:} \begin{itemize} \item \texttt{For $i=1\dots n$:} \begin{itemize} \item Find a subgradient of $v_i(w)$ of $F_i(w)$. \item $w \leftarrow w - \eta v_i(w)$ where $\eta \in \mathbb{R}^{+}$ is the step size. \end{itemize} \end{itemize} \end{itemize} Show why perceptron is a special case of Cyclic Subgradient Descent Algorithm. \begin{soln} Your answer here. \end{soln} \end{enumerate} \bibliographystyle{apalike} %---------------------------------------------------------------------------------------- \end{document}