\documentclass[10pt]{article}
\usepackage[left=1.5cm, right=1.5cm, top=0.8in, bottom=0.7in]{geometry}
\usepackage{fancyhdr}
\pagestyle{fancy}
\usepackage[most,breakable]{tcolorbox}
\usepackage{pdfcol,xcolor}
\usepackage{tikz}
\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
%\usepackage{url}
\usepackage{dsfont}
\usepackage{amssymb,amsmath}
\usepackage{xspace}
\usepackage[normalem]{ulem}
\usepackage{bm}
\usepackage[breaklinks=true,colorlinks,linkcolor=magenta,urlcolor=magenta,citecolor=black]{hyperref}
\usepackage{cleveref}
\usepackage{xpatch}
\xpretocmd{\algorithm}{\hsize=\linewidth}{}{}

\newtcolorbox[auto counter]{exercise}[1][]{%
	colback=yellow!10,colframe=red!75!black,coltitle=white,use color stack,enforce breakable,enhanced,fonttitle=\bfseries,before upper={\parindent15pt\noindent}, title={\color{white}Exercise~\thetcbcounter: #1}}
\pagecolor{yellow!10}

\lhead{
\textbf{University of Waterloo}
}
\rhead{\textbf{2025 Winter}
}
\chead{\textbf{
CS480/680
 }}
\lfoot{}
\cfoot{\textbf{Yao-Liang Yu (yaoliang.yu@uwaterloo.ca) \textcopyright 2025}}

\newcommand{\RR}{\mathds{R}}
\newcommand{\sign}{\mathop{\mathrm{sign}}}
\newcommand{\argmin}{\mathop{\mathrm{argmin}}}
\newcommand{\zero}{\mathbf{0}}
\newcommand{\one}{\mathbf{1}}
\newcommand{\av}{\mathbf{a}}
\newcommand{\bv}{\mathbf{b}}
\newcommand{\cv}{\mathbf{c}}
\newcommand{\ev}{\mathbf{e}}
\newcommand{\mv}{\mathbf{m}}
\newcommand{\wv}{\mathbf{w}}
\newcommand{\xv}{\mathbf{x}}
\newcommand{\Xv}{\mathbf{X}}
\newcommand{\Yv}{\mathbf{Y}}
\newcommand{\zv}{\mathbf{z}}
\newcommand{\yv}{\mathbf{y}}
\newcommand{\rv}{\mathbf{r}}
\newcommand{\inner}[2]{\langle #1, #2 \rangle}
\newcommand{\red}[1]{{\color{red}#1}}
\newcommand{\blue}[1]{{\color{blue}#1}}
\newcommand{\magenta}[1]{{\color{magenta}#1}}
\newcommand{\green}[1]{{\color{green}#1}}
\newcommand{\xbs}{\bm{\mathsf{x}}}
\newcommand{\wbs}{\bm{\mathsf{w}}}
\newcommand{\gbs}{\bm{\mathsf{g}}}
\newcommand{\EE}{\mathds{E}}
\newcommand{\argmax}{\mathop{\mathrm{argmax}}}
\newcommand{\Ysf}{\mathsf{Y}}
\newcommand{\Xsf}{\mathsf{X}}
\newcommand{\ea}{{et al.}\xspace}
\newcommand{\eg}{{e.g.}\xspace}
\newcommand{\ie}{{i.e.}\xspace}
\newcommand{\iid}{{i.i.d.}\xspace}
\newcommand{\cf}{{cf.}\xspace}
\newcommand{\wrt}{{w.r.t.}\xspace}
\newcommand{\aka}{{a.k.a.}\xspace}
\newcommand{\etc}{{etc.}\xspace}
\newcommand{\sgm}{\mathsf{sgm}}
\newcommand{\Dc}{\mathcal{D}}
\newcommand{\pred}[1]{[\![#1]\!]}
\newcommand{\ans}[1]{{\color{orange}\textsf{Ans}: #1}}


%===========================================================
\begin{document}

\begin{center}
\large{\textbf{CS480/680: Introduction to Machine Learning} \\ Homework 1\\ \red{Due: 11:59 pm, Jan 30, 2025}, \red{submit on Crowdmark}.} \\

{\bf \green{NAME}} \\
{\bf \green{student number}}

\end{center}

\begin{center}
Submit your writeup in pdf and all source code in a zip file (with proper documentation). Write a script for each programming exercise so that the TA can easily run and verify your results. Make sure your code runs!

[Text in square brackets are hints that can be ignored.]
\end{center}



\begin{exercise}[Perceptron (8 pts)]
\blue{\textbf{Convention:} All algebraic operations, when applied to a vector or matrix, are understood to be element-wise (unless otherwise stated).}
		
\begin{algorithm}[H]
\DontPrintSemicolon
	\KwIn{$X\in\RR^{d\times n}$, $\yv\in \{-1,1\}^n$, $\wv=\zero_d$, $b=0$, $\mathsf{max\_pass} \in \mathds{N}$}
	
	\KwOut{$\wv, b, mistake$}
	
	\For{$t=1, 2, \ldots, \mathsf{max\_pass}$ }{
		$mistake(t) \gets 0$
		
		\For{$i=1, 2, \ldots, n$}{
			\If{$y_i (\inner{\xv_i}{\wv}+b) \leq 0$}{
				$\wv \gets \wv + y_i\xv_i$ \tcp*{$\xv_i$ is the $i$-th column of $X$}
			
				$b \gets b + y_i$
			
				$mistake(t) \gets mistake(t) + 1$
			}	
		}
	}
	\caption{The perceptron.}
	\label{alg:perceptron}
\end{algorithm}
	
	\begin{enumerate}
	\item (2 pts)  \uline{Implement} the perceptron in \Cref{alg:perceptron}. Your implementation should take input as $X = [\xv_1, \ldots, \xv_n] \in \RR^{d \times n}$, $\yv \in \{-1,1\}^{n}$, an initialization of the hyperplane parameters $\wv\in\RR^{d}$ and $b\in \RR$, and the maximum number of passes of the training set [suggested $\mathsf{max\_pass} = 500$]. \uline{Run} your perceptron algorithm on the \href{https://archive.ics.uci.edu/dataset/94/spambase}{\textsf{spambase}} dataset (available on \href{https://cs.uwaterloo.ca/~y328yu/teaching/480}{course website}), and \uline{plot the number of mistakes ($y$-axis) \wrt the number of passes ($x$-axis)}.
	
	\ans{%
	\begin{center}
		\includegraphics[width=.4\textwidth]{example-image-a}
	\end{center}
	}
	
		
	\item (2 pts) Consider the (continuous) piece-wise function 
	\begin{align}
	f(\wv) := \max_k f_k(\wv),
	\end{align}
	where each $f_k$ is \href{https://en.wikipedia.org/wiki/Differentiable_function}{continuously differentiable}. 
	We define the \href{https://en.wikipedia.org/wiki/Subderivative}{derivative} of $f$ at any $\wv$ as follows: first find (any) $k$ such that $f(\wv) = f_k(\wv)$, \ie, $f_k(\wv)$ achieves the maximum among all pieces; then we let $f'(\wv) = f_k'(\wv)$. [Clearly, the index $k$ that achieves maximum may depend on $\wv$, the point we evaluate the derivative at.] Now consider the following problem [padding applied, $y_i \in \{\pm1\}$]: 
	\begin{align}
	\label{eq:bp}
	\min_{\wbs} ~ \sum_{i=1}^n \max\{ 0, -y_i (\inner{\xbs_i}{\wbs}) \}.
	\end{align}
	\uline{Prove} that in each iteration, the (binary) perceptron algorithm essentially picks a term from the above summation, computes the corresponding derivative (say $\gbs$), and performs a gradient update: 
	\begin{align}
	\wbs \gets \wbs - \gbs.
	\end{align}
	[You may ignore the degenerate case when $\inner{\xv_i}{\wbs} = 0$, and you can use  the usual \href{https://en.wikipedia.org/wiki/Chain_rule}{chain rule} for our derivative.]
	
	\ans{% 
	\vskip4cm
	}	

	\item (2 pts) Consider the following problem, where \red{$y_i \in \{1, 2, \ldots, c\}$}:
	\begin{align}
		\label{eq:mp}
		\min_{\wbs_1, \ldots, \wbs_c} ~ \sum_{i=1}^n \max_{k=1,\ldots, c} \Big [\inner{\xbs_i}{\wbs_k} - \inner{\xbs_i}{\wbs_{y_i}} \Big].
	\end{align}
	\uline{Show} that when $c=2$, we reduce to the binary perceptron problem in \eqref{eq:bp}. [Try to identify the weights $\wbs$, using some transformation.]
	
	\ans{%
	\vskip4cm
	}
	
	\item (2 pts) Based on the analogy to the binary case, \uline{develop and implement} a multiclass perceptron algorithm to solve \eqref{eq:mp} directly. \uline{Run} your implementation on the \href{https://archive.ics.uci.edu/dataset/240/human+activity+recognition+using+smartphones}{activity} dataset (available on \href{https://cs.uwaterloo.ca/~y328yu/teaching/480}{course website}) and \uline{report the final errors on the training and test sets}. [Hint: obviously, we want to predict as follows: $\hat y = \argmax\limits_{k=1, \ldots, c}~ \inner{\xbs}{\wbs_k}$, \ie, the class $k$ whose corresponding $\wbs_k$ maximizes the inner product. Explain your algorithm (\eg, through pseudo-code).]
	
	\ans{%
	\vskip6cm
	}
	\end{enumerate}
\end{exercise}


\begin{exercise}[Perceptron on non-separable dataset (6 pts)]
	In this exercise we develop a mistake bound for perceptron on even a non-separable dataset. For any normal vector $\wbs$ and scalar $s > 0$, define the margin on the $i$-th training example (assuming padding is applied):
	\begin{align}
		\label{eq:margin}
		m_i = \max\{0, s - y_i \inner{\xbs_i}{\wbs}\}.
	\end{align}
	For this exercise we only consider a single pass of \Cref{alg:perceptron} (\ie, $\mathsf{max\_pass} = 1$). 
	
	Our goal is to prove that 
	\begin{align}
		\label{eq:bound}
		mistake := mistake(1) \leq \left(\frac{R\|\wbs\|_2 + \|\mv\|_2}{s}\right)^2,
	\end{align}
	where recall that $R := \max_i \|\xbs_i\|_2$ and the vector $\mv \in \RR^n$ is defined in \eqref{eq:margin}.	
\begin{enumerate}
\item (1 pt) We construct a new dataset $\tilde\xv_i \in \RR^{d+n}, i = 1, \ldots, n$ such that 
\begin{align}
	\tilde\xv_i = \mathtt{concatenate}(\xv_i, c \cdot \ev_i),
\end{align}
where $\ev_i$ is the $i$-th standard basis in $\RR^n$ (\ie, with 1 at the $i$-th entry and 0 elsewhere) and $c > 0$ is a constant that we determine later. We keep the label $y_i$ the same as before. Prove that the new dataset is separable. In particular, consider the hyperplane 
\begin{align}
	\tilde\wbs = \mathtt{concatenate}(\wbs, \yv \odot \mv / c)
\end{align}
and \uline{show that for all $i$}, 
\begin{align}
	y_i \inner{\tilde\xbs_i}{\tilde\wbs} \geq s > 0.
\end{align}
[We remind that $\odot$ is the Hadamard product: if $\cv = \av \odot \bv$ then $c_i = a_i b_i$ for all $i$.]

\ans{%
\vskip 3cm
}


\item (2 pts) \uline{Apply} the perceptron convergence guarantee (on slide 22, with $\delta = 0$ and $\wbs$ initialized as $\zero$) to the above separable dataset $\{\tilde\xbs_i, y_i\}$ to \uline{bound the mistake}: 
\begin{align}
	mistake = mistake(1) \leq \frac{(R\|\wbs\|_2+\|\mv\|_2)^2}{s^2}.
\end{align}
[You need to decide the value of $c$.]

\ans{%
\vskip 3cm
}

\item (3 pts) \uline{Prove that the perceptron makes the same mistakes} on the dataset $\{(\xbs_i, y_i)\}$ and the new dataset $\{(\tilde\xbs_i, y_i)\}$. This completes our proof for a mistake bound of perceptron on a (possibly) non-separable dataset. 
We remind that we only consider $\mathsf{max\_pass} = 1$ and we pick the data points sequentially. 

[Hint: if $\wbs$ is the initialization of perceptron on the dataset $\{(\xbs_i, y_i)\}$, use $\tilde\wbs := \mathtt{concatenate}(\wbs, \zero)$ on the dataset $\{(\tilde\xbs_i, y_i)\}$. Apply induction. If get stuck, can run your implementation on the two datasets side by side to get further insights.]

\ans{%
	\vskip 6cm
}

\iffalse
\item {\color{gray} (0 pt) We remark that if we scale $\wbs$ and $s$ by the same positive number, then the bound \eqref{eq:bound} remains unchanged. Thus, we may simply set $s = 1$ to arrive at the mistake bound
\begin{align}
	R \|\wbs\|_2 + \sqrt{ \sum_i (1 - y_i \inner{\xbs_i}{\wbs})_+^2 },
\end{align}
where we use $(a)_+^2 := [\max\{0, a\}]^2$. Thus, we may regard soft-margin SVM as 
\begin{itemize}
	\item replacing $\|\wbs\|_2$ with $\|\wbs\|_2^2$ (not a big deal)
	\item further bounding $\sqrt{ \sum_i (1 - y_i \inner{\xbs_i}{\wbs})_+^2 } \leq \sum_i (1 - y_i \inner{\xbs_i}{\wbs})_+$.
\end{itemize}
}
\fi
\end{enumerate}
\end{exercise}


\begin{exercise}[Generalized linear models (6 pts)]
Recall that in logistic regression we assumed the \emph{binary} label $\Ysf_i \in \{0,1\}$ follows the Bernoulli distribution: $\Pr(\Ysf_i = 1 | \Xsf_i) = p_i$, where $p_i$ also happens to be the mean. Under the independence assumption we derived the (conditional) negative log-likelihood function:
\begin{align}
-\sum_{i=1}^n (1-y_i) \log(1-p_i) + y_i \log(p_i).
\end{align}
Then, we parameterized the mean parameter $p_i$ through the logit transform:
\begin{align}
\log\frac{p_i}{1-p_i} = \inner{\xv_i}{\wv} + b, \quad \mbox{ or equivalently } \quad p_i = \frac{1}{1+\exp(-\inner{\xv_i}{\wv} - b)}.
\end{align}
Lastly, we found the weight vector $\wv$ and $b$ by minimizing the negative log-likelihood function.

In the following we generalize the above idea significantly. Let the (conditional) density of $\Ysf$ (given $\Xsf= \xv$) be
\begin{align}
\label{eq:GLM}
p(y| \xv) = \exp\Big[ \mu(\xv)\cdot y - \lambda(\xv) \Big] \cdot q(y),
\end{align}
where $\mu:\RR^d \to \RR$ is a function of $\xv$ and $\lambda(\xv) = \log \int_y \exp\big( \mu(\xv) \cdot y \big)  q(y) \mathrm{d} y$ so that $p(y|\xv)$ is properly normalized wrt $y$ (i.e., integrate to 1). For discrete $y$ (such as in logistic regression), replace the density with the \href{https://en.wikipedia.org/wiki/Probability_mass_function}{probability mass function} and the integral with sum.

\red{As always, you need to supply sufficient derivation details to justify your final answer.}

\begin{enumerate}
\item (1 pt) Given a dataset $\{(\xv_i, y_i)\}_{i=1}^n$, \uline{derive the (conditional) negative log-likelihood function} of $y_1, \ldots, y_n$, assuming independence and the density form in \eqref{eq:GLM}. 

\ans{We have 
\begin{align}
TBD 
\end{align}
}

\item (1 pt) Plug the usual linear parameterization 
\begin{align}
\mu(\xv) = \inner{\xv}{\wv} + b = \inner{\xbs}{\wbs}
\end{align}
into your (conditional) \uline{negative log-likelihood} and \uline{compute the gradient of the resulting function}. [Hint: you may \href{https://en.wikipedia.org/wiki/Leibniz_integral_rule}{swap differentiation with integral} and your gradient may involve implicitly defined terms.]

\ans{
We have 
\begin{align}
\ell_n(\wbs) = 
\end{align}
and hence 
\begin{align}
\nabla \ell_n(\wbs) =
\end{align}
}


\item (1 pt) Let us revisit linear regression, where 
	\begin{align}
	p(y | \xv) =\tfrac{1}{\sqrt{2\pi}}\exp\big(-\tfrac{(y - \nu(\xv))^2}{2}\big)
	\end{align}
	\uline{Identify the functions $\mu(\xv)$, $\lambda(\xv)$ and $q(y)$} for the above specialization. Based on the linear parameterization in Ex~\green{3.2}, derive the \uline{negative log-likelihood} and \uline{gradient}. [Hint: you may simply plug into the more general result in Ex~\green{3.2}. Compare with what you already learned about linear regression to make sure both Ex~\green{3.2} and Ex~\green{3.3} are correct.]
	
\ans{
We have 
\begin{align}
\mu(\xv) &=  \\
\lambda(\xv) &= \\
q(y) &=  \\
\ell_n(\wbs) &= \\
\nabla\ell_n(\wbs) &=
\end{align}
}

\item (1 pt) Let us revisit logistic regression, where 
	\begin{align}
	\Pr( \Ysf = y | \xv) =[\nu(\xv)]^{y} [1-\nu(\xv)]^{1-y}, ~~\mbox{ where } ~~ y \in \{0, 1\}.
	\end{align}
	\uline{Identify the functions $\mu(\xv)$, $\lambda(\xv)$ and $q(y)$} for the above specialization. Based on the linear parameterization in Ex~\green{3.2}, derive the \uline{negative log-likelihood} and \uline{gradient}.  [Hint: Compare with what you already learned about logistic regression.]
	
\ans{
We have 
\begin{align}
\mu(\xv) &=  \\
\lambda(\xv) &= \\
q(y) &=  \\
\ell_n(\wbs) &= \\
\nabla\ell_n(\wbs) &=
\end{align}
}

\item (2 pts) Now let us tackle something new. Let 
	\begin{align}
	\Pr(\Ysf = y | \xv) = \frac{[\nu(\xv)]^y}{y!} \exp(-\nu(\xv)), ~~ \mbox{ where } ~~ y = 0, 1, 2, \ldots.
	\end{align}
	\uline{Identify the functions $\mu(\xv)$, $\lambda(\xv)$ and $q(y)$} for the above specialization. Based on the linear parameterization in Ex~\green{3.2}, derive the \uline{negative log-likelihood} and \uline{gradient}. [Hint: $\Ysf$ here follows the \href{https://en.wikipedia.org/wiki/Poisson_distribution}{Poisson distribution}, which is useful for modeling integer-valued events, \eg, the number of customers at a given time.]
	
\ans{
We have 
\begin{align}
\mu(\xv) &=  \\
\lambda(\xv) &= \\
q(y) &= \\
\ell_n(\wbs) &= \\
\nabla\ell_n(\wbs) &=
\end{align}
}	
	
\end{enumerate}
\end{exercise}


\end{document}
              