\documentclass[11pt]{article}
\usepackage{fullpage,url}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
\usepackage{euscript}
%\usepackage{latexsym}
%\usepackage{bbm}

\usepackage{algorithm}
\usepackage[noend]{algorithmic}


\usepackage[letterpaper,top=1in,bottom=1in,left=1in,right=1in,nohead]{geometry}

\setlength{\parindent}{0in}
\setlength{\parskip}{6pt}



\newcommand{\s}[1]{\textsf{#1}}
\renewcommand{\c}[1]{\ensuremath{\EuScript{#1}}}
\renewcommand{\b}[1]{\ensuremath{\mathbb{#1}}}
\renewcommand{\Pr}{\textbf{\s{Pr}}}
\newcommand{\E}{\textbf{\s{E}}}
\newcommand{\Var}{\textbf{\s{Var}}}
\newcommand{\rank}{\ensuremath{\mathsf{rank}}}
\renewcommand{\span}{\ensuremath{\mathsf{span}}}
\newcommand{\diag}{\ensuremath{\mathsf{diag}}}
\newcommand{\upd}[1]{{\color{red}#1}}




\begin{document}
\thispagestyle{empty}
{\large{\bf CS 3190: Foundations of Data Analysis \hfill Due: Friday 12.10 at 11:50pm}}\\

{\LARGE{\bf Homework 5: Clustering and Classification}}

\noindent\rule[0.5ex]{\linewidth}{1pt}

{\bf Instructions:} Your answers are due \textcolor{red}{at 11:50pm}. 
You \textcolor{red}{must turn in a pdf through} canvas  I recommend using latex (\url{http://www.cs.utah.edu/~jeffp/teaching/latex/}) for producing the assignment answers.  If the answers are too hard to read you will lose points, entire questions may be given a $0$
(e.g. \textbf{sloppy pictures with your phone's camera are not ok, but very careful ones are}) 

Please make sure your name appears at the top of the page. 

You may discuss the concepts with your classmates, but write up the answers entirely on your own.   {\bf Be sure to show all the work involved in deriving your answers! If you just give a final answer without explanation, you may not receive credit for that question.}

\vspace{-.1in}
\noindent\rule[0.5ex]{\linewidth}{1pt}




\begin{enumerate}


\item \textbf{[40 points]}
Consider this set of $3$ sites:
$S = \{s_1 = (1,1), s_2 = (0,3), s_3 = (-1,0)\} \subset \mathbb{R}^2$.  
We will consider the following $5$ data points 
$X = \{x_1 = (0,0), x_2 = (-1,4), x_3 = (2,1), x_4 = (0, 1), x_5 = (0, 2)\}$.  

For each of the following points compute the closest site (under Euclidean distance):
\begin{enumerate}
\item $\phi_S(x_1) = $
\item $\phi_S(x_2) = $
\item $\phi_S(x_3) = $
\item $\phi_S(x_4) = $
\item $\phi_S(x_5) = $
\end{enumerate}

Now consider that we have $3$ Gaussian distributions defined with each site $s_j$ as a center $\mu_j$.  The corresponding standard deviations are \upd{$\sigma_1 = 1/\sqrt{2}$}, $\sigma_2 = 1.0$ and \upd{$\sigma_3 = \sqrt{2}$}, and we assume they are univariate so the covariance matrices are \upd{$\Sigma_j = \left[\begin{array}{cc} \sigma_j^2 & 0 \\ 0 & \sigma_j^2 \end{array}\right]$}.

\begin{enumerate}\setcounter{enumii}{5}
\item Write out the probability density function (its likelihood $f_j(x)$ for each of the Gaussians.   
\end{enumerate}

Now we want to assign each $x_i$ to each site in a soft assignment.  For each site $s_j$ define the weight of a point as $w_j(x) = f_j(x) / (\sum_{j=1}^3 f_j(x))$.  
For each of the following points calculate the weight for each site
\begin{enumerate}\setcounter{enumii}{6}
\item $w_1(x_1), w_2(x_1), w_3(x_1) = $
\item $w_1(x_2), w_2(x_2), w_3(x_2) = $
\item $w_1(x_3), w_2(x_3), w_3(x_3) = $
\item $w_1(x_4), w_2(x_4), w_3(x_4) = $
\item $w_1(x_5), w_2(x_5), w_3(x_5) = $
\end{enumerate}








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \textbf{[20 points]}
Construct a data set $X$ with $5$ points in $\b{R}^2$ and a set $S$ of $k=3$ sites so that Lloyds algorithm will have converged, but there is another set $S'$, of size $k=3$, so that
$\textsf{cost}(X,S') < \textsf{cost}(X,S)$.  
Explain why $S'$ is better than $S$, but that Lloyds algorithm will not move from $S$.  







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item\textbf{[25 points]}
Consider a family of linear classifiers defined by the sign of function $g_{w,b}(x) = \langle w, x \rangle + b$, where $x \in \b{R}^2$ and so $w \in \b{R}^2$ and $b \in \b{R}$.  Given a data point $x_i$ and label $y_i \in \{-1, +1\}$.  We require that $\|w\|=1$.  

Now consider a uncertainty zone misclassification goal $\Lambda$ (in place of $\Delta$).  In this setting, we want to penalize a classifier with a cost of $1/4$ for any point within a distance of $2$ of the classification boundary -- even if it has the correct sign.  So the cost is
\[
\Lambda(g_{w,b}, (x_i, y_i)) = \begin{cases}
1 & \text{if } (x_i,y_i) \text{ is misclassified and } |g_{w,b}(x_i)| > 2
\\
1/4 & \text{if } 0 \leq |g_{w,b}(x_i)| ~\upd{ \leq 2}
\\
0 & \text{if } (x_i,y_i) \text{ is classified correctly and } |g_{w,b}(x_i)| > 2
\end{cases}
\]

\begin{enumerate}
\item Explain $\Lambda(g_{w,b}, (x_i, y_i))$ as a function of $z_i = y_i g_{w,b}(x_i)$.  
\item Design a loss function $\ell_\Lambda(z)$ as proxy for $\Lambda(z)$ that is (i) convex, (ii) has a derivative defined for all $z$, and (iii) for all values of $z$ satisfies $\ell_\Lambda(z) \geq \Lambda(z)$.  
\end{enumerate}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item\textbf{[15 points]}
Consider a data set $(X,y)$, where each data point $(x_{1,i}, x_{2,i}, y_i)$ is in $\b{R}^2 \times \{-1,+1\}$.  Provide the psuedo-code for the Perceptron Algorithm using a polynomial kernel of degree $2$.  You can have a generic stopping condition, where the algorithm simply runs for $T$ steps for some parameter $T$.  
\emph{(There are several correct ways to do this, but be sure to explain how to use a polynomial kernel clearly.)}




\end{enumerate}

\end{document}
