\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}}}




\begin{document}
\thispagestyle{empty}
{\large{\bf CS 3190: Foundations of Data Analysis \hfill Due: Friday 12.9 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 = (-3,-1), s_2 = (1,1), s_3 = (-2,2)\} \subset \mathbb{R}^2$.  
We will consider the following $5$ data points 
$X = \{x_1 = (-2,0), x_2 = (-2,1), x_3 = (-1,1), x_4 = (0, 0), x_5 = (-3, -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 $\sigma_1^2 = 0.3$, $\sigma_2^2 = 1.0$ and $\sigma_3^2 = 1.0$, and we assume they are univariate so the covariance matrices are $\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 $4$ points in $\b{R}^2$ and a set $S$ of $k=2$ sites so that Lloyds algorithm will have converged, but there is another set $S'$, of size $k=2$, 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{[20 points]}
Suppose we have a dataset $(X,y)$ where $y \in \{-1,+1\}$ and define a linear function $g(x) := \langle (1,x), \alpha \rangle$ where the overall cost is defined as $\c{L}(g,(X,y)) = \sum_{i=1}^n \ell_i(y_i \cdot g(x_i))$ for some loss function $\ell_i$
\begin{enumerate}
\item Explain why setting $\ell_i(x) = x^2$ would be inappropriate
\item If we suppose that $\ell_i$ is the $\Delta$ loss function, then explain why we defined $\c{L}(g,(X,y)) = \sum_{i=1}^n \ell_i(y_i \cdot g(x_i))$ and \textbf{not} $\c{L}(g,(X,y)) = \sum_{i=1}^n \ell_i(y_i - g(x_i))$ \\

For parts (c) and (d) of this question, we'll suppose 
\[
\ell_i(z) = \begin{cases}
0 & \text{ if } z> 1 \\
1-z & \text{ if } 0 \leq z \leq 1 \\
1 & \text{ if } z \leq 0.  
\end{cases}
\]
\item What problems might a gradient descent algorithm have when attempting to minimize $\c{L}$ by choosing the best $\alpha$?     
\item Explain if the problem would be better or worse using stochastic gradient descent?  
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item\textbf{[20 points]}
\begin{enumerate}
\item Construct and report a set of labeled points $(X,y)$ in $\b{R}^2$ that is not linearly separable (provide a plot).  
\item Explain what will happen if you run the perceptron algorithm for a linear classifier on this data set?   (don't allow a fixed upper bound on $T$ the number of steps)
\item  Describe another algorithm discussed in the class (Chapters 9.1 - 9.3) which would provides an acceptable linear classifier for set of points.  
\end{enumerate}



\end{enumerate}

\end{document}
