\documentclass{article}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{fancyhdr}
\usepackage[top=2cm, bottom=4.5cm, left=2.5cm, right=2.5cm]{geometry}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{hyperref}
\usepackage{enumitem}
\usepackage{physics}
\usepackage{amsmath}
\usepackage{tikz}
\usepackage{mathdots}
\usepackage{yhmath}
\usepackage{cancel}
\usepackage{color}
\usepackage{siunitx}
\usepackage{array}
\usepackage{multirow}
\usepackage{amssymb}
\usepackage{gensymb}
\usepackage{tabularx}
\usepackage{extarrows}
\usepackage{booktabs}
\usepackage{xcolor}
\usetikzlibrary{fadings}
\usetikzlibrary{patterns}
\usetikzlibrary{shadows.blur}
\usetikzlibrary{shapes}

\setlength\parindent{0pt}



\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}

% Edit these as appropriate
\newcommand\course{CS 1420}
\newcommand\semester{Spring 2026}            % <-- current semester
\newcommand\hwnumber{7}                      % <-- homework number
\newcommand\duedate{Thursday, April 2, 2026 at 12:00pm \textbf{(Noon)}}

\begin{document}
   \begin{center}
      \huge\textbf{Homework \hwnumber}
   \end{center}

   \begin{center}
        \large{Due: \duedate}
   \end{center}

\section*{Written Assignment}

\subsection*{Problem 1: Kernels (25 points)}

In lecture, we described a kernel $K(\mathbf{u},\mathbf{v})=\langle \psi(\mathbf{u}),\psi(\mathbf{v}) \rangle$ as a function that allows us to compute inner products in high dimensions efficiently. However, some functions $K:\mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$ are not valid kernels for any mapping $\psi:\mathbb{R}^d \rightarrow \mathbb{R}^e$. While it is occasionally easy to find a $\psi$ that proves $K$ is a valid kernel, it is often easier to prove that $K$ is a valid kernel without explicitly finding $\psi$. \\

To determine if there exists some mapping $\psi$ for which $K$ is a valid kernel, we define the \textit{Gram matrix} $G$ for a kernel function $K$ and a dataset $\mathbf{u}_1,...,\mathbf{u}_n \in \mathbb{R}^d$ to be:
\begin{equation*}
    G_K := \begin{bmatrix}
        K(\mathbf{u}_1,\mathbf{u}_1) & K(\mathbf{u}_1,\mathbf{u}_2) & \hdots & K(\mathbf{u}_1,\mathbf{u}_n) \\
        K(\mathbf{u}_2,\mathbf{u}_1) & K(\mathbf{u}_2,\mathbf{u}_2) & \hdots & K(\mathbf{u}_2,\mathbf{u}_n) \\
        \vdots & \vdots & \ddots & \vdots \\
        K(\mathbf{u}_n,\mathbf{u}_1) & K(\mathbf{u}_n,\mathbf{u}_2) & \hdots & K(\mathbf{u}_n,\mathbf{u}_n) \\
    \end{bmatrix}
\end{equation*}
The following equivalence is \textit{Mercer's condition}: $K$ is a valid kernel if and only if $G_K$ is symmetric and positive semidefinite (PSD) for all possible
datasets $\{\mathbf{u}_1, \dots, \mathbf{u}_n\}$. Furthermore, a matrix $M$ is PSD if and only if
$\mathbf{a}^T M \mathbf{a} \geq 0$ for all $\mathbf{a} \in \mathbb{R}^n$. You may find this fact useful for this
problem, but you are not required to use it. \\

In this problem, you will prove that the polynomial kernel $K_p(\mathbf{u},\mathbf{v})=(b\langle
\mathbf{u},\mathbf{v} \rangle +c)^d$ is a valid kernel function when $b>0$, $c \geq 0$,
and $d \in \mathbb{Z}^+$.

\begin{enumerate}[label=\alph*.]

    \item Prove that the linear kernel $K(\mathbf{u},\mathbf{v})=\langle \mathbf{u},\mathbf{v} \rangle$ is a valid kernel.

% TODO: add your solution here!
%
%
%
%
%
%
    
    \item Show that, assuming $K_1$ is a valid kernel and $b>0$, $K(\mathbf{u}, \mathbf{v}) 
    = bK_1(\mathbf{u},\mathbf{v})$ is a valid kernel by showing that the Gram matrix of $K$ is symmetric and PSD.
    
% TODO: add your solution here!
%
%
%
%
%
%
    
    \item Prove that if $K_1$ is a valid kernel and $c \geq 0$, then $K(\mathbf{u}, \mathbf{v})
    = K_1(\mathbf{u},\mathbf{v})+c$ is a valid kernel. \\\\
    \textit{Hint: Let $\psi_1(\mathbf{u})$ be the mapping for $K_1$. How could you use $\psi_1(\mathbf{u})$ to construct another mapping, $\psi(\mathbf{u})$, for which $K$ is a valid kernel?}

% TODO: add your solution here!
%
%
%
%
%
%
    
    \item Using the fact that, assuming $K_1$ and $K_2$ are valid kernels,
    $K_1(\mathbf{u}, \mathbf{v}) \cdot K_2 (\mathbf{u}, \mathbf{v})$
    is a valid kernel and parts (a)-(c), show
    that the polynomial kernel $K_p(\mathbf{u}, \mathbf{v}) = (b\langle \mathbf{u}, \mathbf{v}
    \rangle + c)^d$ is a valid kernel.

% TODO: add your solution here!
%
%
%
%
%
%
    
\end{enumerate}

\pagebreak

\subsection*{Problem 2: Deriving a Kernel Function (5 points)}
In the programming portion, we will see a binary classification problem with features $\mathbf{x} \in \mathbb{R}^2$.
Unfortunately, the given training set is not linearly separable in the original feature space $\mathbb{R}^2$, so we 
will embed $\mathbf{x}$ into $\mathbb{R}^3$ using the \textit{polar embedding} $\psi: \mathbb{R}^2 \to \mathbb{R}^3$, which
is given by
\begin{equation*}
    \psi(\mathbf{x}) = (x_1, x_2, x_1^2 + x_2^2)
\end{equation*}
However, manually embedding is very costly, so we would like to have a kernel representation so we can avoid this.
Show that
\begin{equation*}
     K(\mathbf{x'}, \mathbf{x}) = \langle \mathbf{x}', \mathbf{x} \rangle + \Vert \mathbf{x}'\Vert_2^2\Vert 
     \mathbf{x}\Vert_2^2 = \langle \psi(\mathbf{x}'), \psi(\mathbf{x})\rangle,
\end{equation*}
which implies that $K : \mathbb{R}^2 \times \mathbb{R}^2 \to \mathbb{R}$ as above is a kernel representation of $\psi$. \\

% TODO: add your solution here!
%
%
%
%
%
%

\pagebreak

\section*{Programming Assignment (30 points)}
\subsection*{Background}
Recall the soft SVM optimization objective:
\begin{gather}\label{eq:equation_1}
\argmin_{\mathbf{w}, \xi} \lambda \| \mathbf{w} \|^2 + \frac{1}{m}\sum_{i=1}^{m} \xi_i\\
\text{s.t. } \forall i \in [m],\;y_i \langle \mathbf{w}, \mathbf{x}_i \rangle \geq 1 - \xi_i,\;\xi_i \geq 0, \nonumber
\end{gather}
for $\mathbf{x}_i$ a training example and $\mathbf{w}$ a vector, normal to the hyperplane. In lecture, we saw that the optimizer $\mathbf{w}^*$ can be written
\begin{equation}\label{eq:equation_2}
    \mathbf{w}^* = \sum^m_{i=1} \alpha_i\mathbf{x}_i,
\end{equation}
that the classifier $h(x)$ can be written
\begin{equation}\label{eq:equation_3}
    h(\mathbf{x}) = \text{sign}(\langle \mathbf{w}, \mathbf{x} \rangle) = \text{sign}\left(\sum^m_{i=1}\alpha_i\langle \mathbf{x}_i, \mathbf{x} \rangle\right),
\end{equation}
and that, in cases where the data is not linearly separable, it may be favorable to embed the data into a higher dimensional feature space. For an embedding function $\psi(\mathbf{x})$, \eqref{eq:equation_2} and \eqref{eq:equation_3} become, respectively,
\begin{gather}\label{eq:equation_4}
    \mathbf{w}^* = \sum^m_{i=1} \alpha_i\psi(\mathbf{x}_i), \\
    \label{eq:equation_5}
    h(\mathbf{x}) = \text{sign}\left(\sum^m_{i=1}\alpha_i\langle \psi(\mathbf{x}_i), \psi(\mathbf{x}) \rangle\right).
\end{gather}
Assuming there exists a valid kernel function $K$ corresponding to $\psi(x)$, by definition, \eqref{eq:equation_5} becomes
\begin{equation}\label{eq:equation_6}
    h(\mathbf{x}) = \text{sign}\left(\sum^m_{i=1}\alpha_iK(\mathbf{x}_i, \mathbf{x})\right).
\end{equation}
So, the corresponding hyperplane is
\begin{equation}\label{eq:equation_7}
    H(\mathbf{x}) = \sum^m_{i=1}\alpha_iK(\mathbf{x}_i, \mathbf{x}) = 0.
\end{equation}

\newpage

\subsection*{Introduction}
You can find and download the stencil code here: \texttt{\href{https://classroom.github.com/a/A6huAOFm}{HW7 on Github}}.

All four parts of the coding portion of this assignment will be related to producing visualizations which you will be asked to reflect upon. We will be using \texttt{sklearn}'s implementation of a support vector machine classifier. You can find documentation related to svm.SVC \href{https://scikit-learn.org/1.0/modules/generated/sklearn.svm.SVC.html}{here}. You can find documentation about overall implementation details of \texttt{sklearn}'s SVM library \href{https://scikit-learn.org/1.0/modules/svm.html#svm}{here}. \\

\texttt{sklearn}'s SVM implementation and treatment of the optimization objective use an explicit intercept value, so  \eqref{eq:equation_6} and \eqref{eq:equation_7} are respectively implemented as
\begin{equation}\label{eq:equation_8}
    h(\mathbf{x}) = \text{sign}(H(\mathbf{x}))= \text{sign}\left(\sum_{i\in SV}\alpha_iK(\mathbf{x}_i, \mathbf{x}) + b\right)
\end{equation}
\begin{equation}\label{eq:equation_9}
    H(\mathbf{x}) = \sum_{i \in SV}\alpha_iK(\mathbf{x}_i, \mathbf{x}) + b
\end{equation}
where $b$ is some scalar representing the intercept or bias, and $SV$ is the set of indices of support vectors. Both of these are discovered by the optimization algorithm used by \texttt{sklearn} after calling \texttt{svm.fit()}.\\

You will need to modify the following files:
\begin{itemize}
    \item \texttt{decision\_surface\_visualization.py}: Most of the implementation logic for getting the data to plot in part 1, 2.
    \item \texttt{support\_vector\_visualization.py}: All of the plotting and data generation for part 4 is done here.
    \item \texttt{main.py}: Here is where you'll call the functions you filled out in \texttt{decision\_surface\_visualization.py} and \texttt{support\_vector\_visualization.py}
\end{itemize}
You will \textit{not} need to modify \texttt{utils.py}; however, we strongly recommend you take a look at it to understand some of the plotting logic and what the parameters do.

\subsection*{Before you start}
Since this assignment relies on external libraries, some of the features used in the stencil require certain versions or above of these libraries. Please ensure that the installed libraries in the version of Python you're using is at least of versions:
\begin{itemize}
    \item \texttt{sklearn}: 1.0.2
    \item \texttt{numpy}: 1.22.2
    \item \texttt{matplotlib}: 3.5.1
\end{itemize}

Finally, we highly encourage you to read the \texttt{SVC} documentation and become familiar with the methods and attributes available, as you will be using some of them in this assignment. (Don't worry about implementation details)
\newpage
\subsection*{Part 1}
First, you'll be visualizing the decision boundary from $H(\mathbf{x})$ in both the higher dimensional feature space and the original feature space.
\subsubsection*{Visualizing The Embedding Space}
As mentioned in problem 2 of the written portion, we'll use the \textit{polar embedding}, 
\begin{equation*}
    \phi((x_1, x_2)) \rightarrow (x_1, x_2, x_1^2 + x_2^2).
\end{equation*}
The data provided is not linearly separable in the
original space it's given in; however, it is linearly separable in this embedding space. To 
do so, we manually calculate the higher dimensional feature space coordinates. We then 
train an SVM using a linear kernel using those manually calculated coordinates.
\\ \\
\textit{This has the same effect as training on the original data and using a Kernel representation.} We will visually confirm this in Part 2. 
\\ \\
\texttt{TODO}: Implement the polar embedding function and its kernel representation. You'll need to modify:
\begin{itemize}
    \item\texttt{polar\_embedding()} in \texttt{decision\_boundary\_visualization.py}
    \item\texttt{polar\_kernel()} in \texttt{decision\_boundary\_visualization.py}
\end{itemize}

To plot our hyperplane, imagine a standard $x,y,z$ Cartesian coordinate space. We will plot our new feature values from the embedding, $x_1^2 + x_2^2$, on the $z$-axis, $x_1$ on the $x$-axis, and $x_2$ on the $y$-axis. We would like to find what $x_1^2 + x_2^2$ values on our hyperplane correspond to each pair $x_1$ and $x_2$. We can do this with some simple elementary algebra
\begin{align}
        \label{eq:equation_10}
    H(\mathbf{x}) =& w_1x_1 + w_2x_2 + w_3(x_1^2 + x_2^2) + b= 0 \\
        \label{eq:equation_11}
    & w_1x_1 + w_2x_2 + b = -w_3(x_1^2 + x_2^2) \\
        \label{eq:equation_12}
    & -\frac{w_1}{w_3}x_1 - \frac{w_2}{w_3}x_2 - \frac{b}{w_3} = x_1^2 + x_2^2
\end{align}
Once we have fit our SVM, \texttt{sklearn} provides us with $\mathbf{w}^*$ and $b^*$, so we have everything we need to implement \eqref{eq:equation_12}.
Now, generate an image of
\begin{itemize}
    \item The decision boundary in the point's original space, along with the original points.
    \item The decision boundary in the higher dimensional feature space, along with the embeddings of the points.
\end{itemize}
This will be done by implementing \eqref{eq:equation_12}, and calculating the new feature values, $x_1^2 + x_2^2$, over a grid of points $(x_1, x_2)$.
\\ \\
\texttt{TODO}: In the recommended order, you'll need to modify
\begin{enumerate}
    \item \texttt{generate\_new\_feature\_values()} in \texttt{decision\_boundary\_visualization.py}
    \item \texttt{visualize\_decision\_boundary\_embedded\_space()} in \texttt{main.py}
\end{enumerate}

\newpage

\subsection*{Part 2}
Now, we'll visualize $H(\mathbf{x})$ in its own space. This time, instead of letting the $z$-axis represent the feature $x_1^2 + x_2^2$, it will represent values of $H(\mathbf{x})$. We would also like to visually confirm that there's no difference in the solution found (when all the samples are linearly separable in embedding space) when training a linear SVM in embedding space and when training an SVM using the kernel trick which corresponds to the same embedding space.
\\ \\
This process should feel similar to part (1). Implement equation \eqref{eq:equation_9}, then calculate the value of $H(\mathbf{x})$ over a grid.
\\ \\
\texttt{TODO}: In the recommended order, you'll need to modify
\begin{enumerate}
    \item The remaining \texttt{TODO}'s in \texttt{decision\_boundary\_visualization.py}
    \item \texttt{visualize\_H()} in \texttt{main.py}
\end{enumerate}

\subsection*{Part 3}
In this part you will be observing the effect of the regularization $\lambda$ on the decision surface found by the SVM.
\\
Without changing anything else in our optimization objective we can express \eqref{eq:equation_1} as
\begin{equation}\label{eq:equation_13}
\argmin_{\mathbf{w}, \xi} \Vert \mathbf{w} \Vert^2 + \frac{1}{\lambda}\sum^m_{i=1}\xi_i
\end{equation}
The constant coefficients will differ from representation to representation, but regardless the effect of $\lambda$ as a regularization parameter stays the same. Rather than $\lambda$, \texttt{sklearn} uses $C$ to denote the regularization parameter which is defined by equating the below with \eqref{eq:equation_13}:
\begin{equation}\label{eq:equation_14}
\argmin_{\mathbf{w}, \xi} \Vert \mathbf{w} \Vert^2 + C\sum^m_{i=1}\xi_i.
\end{equation}
Notice that $C$ is inversely proportional to $\lambda$.
\\ \\
To see this, we'll plot the decision surface in $\mathbb{R}^2$ using an SVM with the RBF (Radial Basis Function) kernel, given by
\begin{equation*}
    K(\mathbf{u}, \mathbf{v} ) = \exp\left(-\gamma\Vert \mathbf{u} - \mathbf{v} \Vert^2 \right)
\end{equation*}
wherein $\gamma$ is a tunable parameter. Note that if we express $\gamma$ as $\gamma = \frac{1}{2\sigma^2}$, we get the Gaussian kernel similar to how it's presented in lecture. The RBF kernel is an extremely popular choice as it provides a lot of representational power -- in fact, it provides an infinite dimensional embedding. See \href{https://pages.cs.wisc.edu/~matthewb/pages/notes/pdf/svms/RBFKernel.pdf}{this resource} from the University of Wisconsin--Madison for more info. For this assignment, we will use the default value of $\gamma$ used by \texttt{sklearn}.
\\ \\
At this point, all the code you need outside of \texttt{visualize\_slack\_penalty()} should be completed from previous parts. Your job here is to just fill in the rest of the function and observe the difference between each plot.
\\ \\
\texttt{TODO}: Fill out \texttt{visualize\_slack\_penalty()} in \texttt{main.py}

\newpage

\subsection*{Part 4}
In this part, we will focus on the support vectors themselves. Using some linearly separable data in $\mathbb{R}^2$, and a large $C$ value to mimic a hard margin SVM, we'll visualize which points get picked as support vectors, and verify that they lie exactly on the margins.
\\ \\
Recall that in equation \eqref{eq:equation_9}, for all $x_i$ which are not support vectors, $\alpha_i = 0$, which means that non support vector points do not contribute to the decision boundary at all. We'll demonstrate this by first training with all points and then training with only support vectors.
\\ \\
We would also like to see how the support vectors directly affect the margin. To do this, we will iterate some number of times, and, in each iteration, we will remove the support vectors from the data set and retrain.

\subsubsection*{Plotting the Margins}
Plotting the decision boundary is a similar process as in part (1), but with one fewer feature. Let the $y$-axis be $x_2$ and write $x_2$ in terms of $x_1, w_1, w_2, b$. Then, calculate $x_2$ for a range of values of $x_1$. Plotting the margins is a bit more involved. One approach is to use the points of the decision boundary we've already calculated then just add or subtract the ``vertical" distance between the decision boundary and the margins in $\mathbb{R}^2$.
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        
\begin{center}

\begin{tikzpicture}[x=0.56pt,y=0.42pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,457); %set diagram left start at 0, and has height of 457

%Straight Lines [id:da7988896686114517] 
\draw    (124.44,387.01) -- (520.63,387.01) ;
\draw [shift={(522.63,387.01)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da9512401936863182] 
\draw    (124.44,387.01) -- (126.64,43.9) ;
\draw [shift={(126.65,41.9)}, rotate = 90.37] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da21105640836024975] 
\draw [color={rgb, 255:red, 189; green, 16; blue, 224 }  ,draw opacity=1 ] [dash pattern={on 0.84pt off 2.51pt}]  (124.44,295.59) -- (474.54,49.91) ;
\draw [shift={(476.18,48.76)}, rotate = 144.94] [color={rgb, 255:red, 189; green, 16; blue, 224 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da8052542454303266] 
\draw [color={rgb, 255:red, 189; green, 16; blue, 224 }  ,draw opacity=1 ] [dash pattern={on 0.84pt off 2.51pt}]  (241.69,391.58) -- (587.38,141.35) ;
\draw [shift={(589,140.18)}, rotate = 144.1] [color={rgb, 255:red, 189; green, 16; blue, 224 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da8369680453419197] 
\draw    (124.44,387.01) -- (532.07,95.63) ;
\draw [shift={(533.7,94.47)}, rotate = 144.44] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da9132390487110433] 
\draw [color={rgb, 255:red, 235; green, 21; blue, 21 }  ,draw opacity=1 ]   (300.31,172.17) -- (299.33,262.27) ;
%Straight Lines [id:da6923226190831544] 
\draw [color={rgb, 255:red, 8; green, 21; blue, 234 }  ,draw opacity=1 ]   (300.31,172.17) -- (340.71,233.13) ;
%Shape: Circle [id:dp1456472862304481] 
\draw  [fill={rgb, 255:red, 43; green, 137; blue, 48 }  ,fill opacity=0.96 ] (120.23,291.38) .. controls (120.23,289.06) and (122.12,287.18) .. (124.44,287.18) .. controls (126.76,287.18) and (128.65,289.06) .. (128.65,291.38) .. controls (128.65,293.7) and (126.76,295.59) .. (124.44,295.59) .. controls (122.12,295.59) and (120.23,293.7) .. (120.23,291.38) -- cycle ;
%Shape: Circle [id:dp8734980317892069] 
\draw  [fill={rgb, 255:red, 56; green, 161; blue, 37 }  ,fill opacity=0.96 ] (120.23,387.01) .. controls (120.23,384.68) and (122.12,382.8) .. (124.44,382.8) .. controls (126.76,382.8) and (128.65,384.68) .. (128.65,387.01) .. controls (128.65,389.33) and (126.76,391.21) .. (124.44,391.21) .. controls (122.12,391.21) and (120.23,389.33) .. (120.23,387.01) -- cycle ;

% Text Node
\draw (523.63,383.41) node [anchor=north west][inner sep=0.75pt]    {$x_{1}$};
% Text Node
\draw (110.11,23.88) node [anchor=north west][inner sep=0.75pt]    {$x_{2}$};
% Text Node
\draw (240.91,229.79) node [anchor=north west][inner sep=0.75pt]  [color={rgb, 255:red, 243; green, 5; blue, 5 }  ,opacity=1 ,xslant=-0.04]  {$b_{1} -b_{2}$};
% Text Node
\draw (316.74,155.74) node [anchor=north west][inner sep=0.75pt]  [color={rgb, 255:red, 19; green, 15; blue, 231 }  ,opacity=1 ]  {$d\ \ =\ \frac{1}{\Vert \mathbf{w} \| }$};
% Text Node
\draw (102,280.4) node [anchor=north west][inner sep=0.75pt]    {$\textcolor[rgb]{0.25,0.46,0.02}{b_{1}}$};
% Text Node
\draw (102,375.4) node [anchor=north west][inner sep=0.75pt]    {$\textcolor[rgb]{0.25,0.46,0.02}{b}\textcolor[rgb]{0.25,0.46,0.02}{_{2}}$};
% Text Node
\draw (523,71.4) node [anchor=north west][inner sep=0.75pt]    {$H(\mathbf{x}) \ =\ 0$};
\end{tikzpicture}
    
\end{center}
Luckily, as discussed in lecture, the margins are parallel to the decision boundary. The distance between parallel lines at $x_1 = 0$ is well known to be
\begin{equation}\label{eq:equation_15}
    d = \frac{b_1 - b_2}{\sqrt{1 + s^2}}
\end{equation}
Where $s$ is the slope both lines share, and $b_1, b_2$ are the intercepts, $b_2 - b_1$ is the vertical distance. We also know the distance between the decision boundary and a point $\mathbf{a}$ on the margin is $\frac{\vert \langle \mathbf{w}, \mathbf{a} \rangle \vert}{\Vert \mathbf{w} \Vert}$, since the margins are the points where $\langle \mathbf{w}, \mathbf{x} \rangle = \pm 1$, the distance between the decision boundary and either margin is $\frac{1}{\Vert \mathbf{w} \Vert}$.
\begin{equation*}
 \frac{1}{\Vert \mathbf{w} \Vert} = \frac{b_1 - b_2}{\sqrt{1 + s^2}}
\end{equation*}
\begin{equation}\label{eq:equation_16}
    \text{vertical distance} = b_1 - b_2 = \frac{\sqrt{1 + s^2}}{\Vert \mathbf{w} \Vert}
\end{equation}
\\ \\
\texttt{TODO}: You'll need to modify
\begin{enumerate}
    \item All of \texttt{support\_vector\_visualization.py}
    \item \texttt{visualize\_support\_vectors()} in \texttt{main.py}
\end{enumerate}

\subsection*{Project Report (40 points)} 
\begin{enumerate}
    \item Add all the plots generated as part of this assignment. \textbf{This is how we will be primarily grading correctness of your code.} For the 3d plots, just take a screen shot from any angle. 
    \item In part 1, we saw that the embedding, $\phi((x_1, x_2)) \rightarrow (x_1, x_2, x_1^2 + x_2^2)$, was able to make our non linearly separable data in $\mathbb{R}^2$ perfectly linearly separable in the higher dimensional feature space. Give a non rigorous explanation using the embedding function and the nature of the data regarding why the polar embedding was able to make \textit{this particular dataset} perfectly linearly separable. Would this embedding be able to make any data set linearly separable? Feel free to use the plots generated in part 1 to support your answer
    \item In part 2, we visually confirmed the solution found by the SVM by manually embedding and training a linear SVM vs training a SVM using a corresponding kernel were the same. In lecture we mathematically proved that they are the same. If this is the case, then why would we use a kernel function rather than manually embedding? Give two reasons why this is the case.
    \item In part 3, what trend do you see regarding the complexity of the decision boundaries as $C$ increases? When would we want to use low $C$ values or high $C$ values?
    \item In part 4, does the plot of the SVM trained on the entire dataset vs the plot of the SVM trained on only the support vectors match your expectations? Explain why you had those expectations. It's fine if the plots contradicted your expectations.
    \item In part 4, comment on the margins as we remove support vectors. Explain why this is the case using the optimization problem presented in lecture, and the definition of support vectors. 
\end{enumerate}

\subsection*{Grading Breakdown}

Note that the coding portion score is based on your submission including your graphs. Otherwise you will at best get partial credit from manually grading your code. The grading breakdown for this assignment is as follows:
\begin{center}
\begin{tabular}{| l | r |}
    \hline
    Written Questions & 30 points \\
    \hline
    Coding Portion & 30 points \\
    \hline
    Report & 40 points \\
    \hline
    Total & 100 points \\
    \hline
\end{tabular}
\end{center}

\subsection*{Handing in}
You will hand in both the written assignment and the coding portion on gradescope, separately. 

\begin{enumerate}
    \item Your written assignment should be uploaded to gradescope under ``Homework 7". 
    \item Submit your hw7 github repo containing all your source code and your project report named \textbf{report.pdf} on gradescope under ``Homework 7 Code". \textbf{report.pdf} should live in the root directory of your code folder; the autograder will check for the existence of this file and inform you if it is not found. For questions, please consult the \href{https://docs.google.com/document/d/1RbsJ_IKfzuAyL7yDma4Z7bCVTwiNJfPAHbBAd2WeIEE/edit?usp=sharing}{download/submission guide}.
\end{enumerate}


\subsubsection*{Anonymous Grading}
You need to be graded anonymously, so do not write your name anywhere on your handin. 


\subsection*{Academic Integrity}
The \href{https://cs.brown.edu/courses/csci1420/assets/docs/collaboration.pdf}{CSCI 1420 Collaboration Policy} applies to this assignment.
As outlined in the \href{https://college.brown.edu/design-your-education/academic-policies/academic-code}{Brown Academic Code} and the \href{https://graduateschool.brown.edu/academics-research/rules-regulations/academic-code}{Brown Academic Code, Graduate Student Edition}, attempting to pass off another's work or AI-generated work as your own can result in failing the assignment, failing this course, or even dismissal or expulsion from Brown.  More than that, you will be missing out on the goal of your education, which is the cultivation of your own mind, thoughts, and abilities.  Please review this course's collaboration policy and if you have any questions, please contact the instructor.

\end{document}
