\documentclass{article}

\usepackage{fullpage}
\usepackage{color}
\usepackage{amsmath}
\usepackage{url}
\usepackage{verbatim}
\usepackage{graphicx}
\usepackage{parskip}
\usepackage{amssymb}
\usepackage{nicefrac}
\usepackage{listings} % For displaying code
\usepackage{algorithm2e} % pseudo-code

% Answers
\def\ans#1{\par\gre{Answer: #1}}

% Colors
\definecolor{blu}{rgb}{0,0,1}
\def\blu#1{{\color{blu}#1}}
\definecolor{gre}{rgb}{0,.5,0}
\def\gre#1{{\color{gre}#1}}
\definecolor{red}{rgb}{1,0,0}
\def\red#1{{\color{red}#1}}
\def\norm#1{\|#1\|}

% Math
\def\R{\mathbb{R}}
\def\argmax{\mathop{\rm arg\,max}}
\def\argmin{\mathop{\rm arg\,min}}
\newcommand{\mat}[1]{\begin{bmatrix}#1\end{bmatrix}}
\newcommand{\alignStar}[1]{\begin{align*}#1\end{align*}}
\def\half{\frac 1 2}

% LaTeX
\newcommand{\fig}[2]{\includegraphics[width=#1\textwidth]{a5f/#2}}
\newcommand{\centerfig}[2]{\begin{center}\includegraphics[width=#1\textwidth]{a5f/#2}\end{center}}
\def\items#1{\begin{itemize}#1\end{itemize}}
\def\enum#1{\begin{enumerate}#1\end{enumerate}}


\begin{document}

\title{CPSC 540 Assignment 1 (due January \red{12}th at midnight)}
\author{}
\date{}
\maketitle
\vspace{-4em}

\textbf{IMPORTANT!!!!! Before proceeding, please carefully read the homework instructions}:\\ \url{www.cs.ubc.ca/~schmidtm/Courses/540-F17/assignments.pdf}

\textbf{We will deduct 50\% on assignments that do not follow the instructions}.

Most of the questions below are related to topics covered in CPSC 340, or other courses listed on the prerequisite form. There are several ``notes'' available on the webpage which can help with some relevant background.

If you find this assignment to be difficult overall, that is an early warning sign that you may not be prepared to take CPSC 540
at this time. Future assignments will be longer and more difficult than this one.

We use \blu{blue} to highlight the deliverables that you must answer/do/submit with the assignment.

\section*{Basic Information}


\blu{\enum{
\item Name:
\item Student ID:
\item Faculty (e.g., applied science):
\item Department (e.g., computer science):
\item Graduate students in CPSC/EECE/STAT must submit the prerequisite form as part of a1sol.zip:\\
\url{https://www.cs.ubc.ca/~schmidtm/Courses/540_prereqs.pdf}
}}


\section{Very-Short Answer Questions}


Give a short and concise 1-sentence answer to the below questions.

\blu{
\enum{
\item Why is the IID assumption important in supervised learning?
\ans{You can enter your answers like this if you want.}
\item Suppose we have a supervised learning problem where we think the examples $x_i$ form clusters. To deal with this, we combine our training and test data together and fit a k-means model. We then add the cluster number as an extra feature, fit our supervised learning model based on the training data, then evaluate it on the test data. What have we done wrong?
\item What is the difference between a validation \red{set} error and the test error?
\item Describe a setting where using a validation set to choose hyper-parameters can lead to overfitting.
\item What is the effect of the number of features $d$ that our model uses on the training error and on the approximation error? 
\item What is wrong with with using $\frac{1}{n}\sum_{i=1}^n(\hat{y}_i == \tilde{y}_i)$ as the validation error of a regression model?
\item Describe a situation where it could be better to use gradient descent than the normal equations to solve a least squares problem.
\item  How does $\lambda$ in an L0-regularizer (like BIC) affect the sparsity pattern of the solution, the training error, and the approximation error?
\item Minimizing the squared error with L0-regularization is NP-hard, what does this imply?
\item For a fixed target $y$, what is the likely effect of increasing the condition number of $X$ (in a least squares problem) on the approximation error?
\item For supervised training of a linear model $w^Tx^i$ with $y_i \in \{-1,+1\}$, why do we use the logistic loss intead of the squared error?
\item What is the key difference between ``one vs.~all'' logistic regression and training using the softmax loss?
\item Give a supervised learning scenario where you would use the Laplace likelihood and a scenario where you would use a Laplace prior.
\item What do we use the backpropagation algorithm for?
\item What are the two key properties of a problem that let us use dynamic programming?
\item Consider a deep neural network with 1 million hidden units. Explain whether this is a parametric or a non-parametric model.
\item What are two reasons that convolutional neural networks overfit less than classic neural networks?
}
}


\section{Calculation Questions}



\subsection{Minimizing Strictly-Convex Quadratic Functions}

Solve for the minimizer $w$ of the below strictly-convex quadratic functions:
\blu{\enum{
\item $f(w) = \frac{1}{2}(w-u)^T\Sigma(w-u)$ (projection of $u$ onto the real space under $\Sigma$-norm).
\item $f(w)= \frac{1}{2\sigma^2}\norm{Xw - y}^2 + \frac{\lambda}{2}\norm{w}^2$ (ridge regression with known variance).
\item $f(w) = \frac{1}{2}\sum_{i=1}^n v_i(w^Tx^i - y^i)^2 + \frac{1}{2}(w-u)^T\Lambda(w-\red{u})$ (weighted least squares shrunk towards $u$).
}}
Above we use our usual supervised learning notation. In addition, we assume that $u$ is $d \times 1$ and $v$ is $n \times 1$, while $\Sigma$ and $\Lambda$ are positive-definite $d \times d$ matrices. You can use $V$ as a diagonal matrix with $v$ along the diagonal. Hint: \red{positive-definite matrices are invertible}.


\subsection{Norm Inequalities}

Show that the following inequalities hold for vectors $w \in \R^d$ and $u \in \R^d$:
\blu{\enum{
\item $\norm{w}_\infty \leq \norm{w}_2 \leq \norm{w}_1$ (relationship between decreasing $p$-norms)
\item $\norm{w}_1 \leq \sqrt{d}\norm{w}_2 \leq d\norm{w}_\infty$ (relationship between increasing $p$-norms)
\item $\frac{1}{2}\norm{w+u}_2^2 \leq \norm{w}^2 + \norm{u}^2$ (``not the triangle inequality'' inequality)
}
}
You should use the definitions of the norms, but should not use the %triangle inequality or the 
known equivalences between these norms (since these are the things you are trying to prove).
Hint: for many of these it's easier if you work with squared values (and you may need to ``complete the square"). Beyond non-negativity of norms, it may also help to use the Cauchy-Schwartz inequality and/or to use that $\norm{x}_1 = x^T$sign$(x)$.




\subsection{MAP Estimation}


In 340, we showed that under the assumptions of a Gaussian likelihood and Gaussian prior,
\[
y^i \sim \mathcal{N}(w^Tx^i,1), \quad w_j \sim \mathcal{N}\left(0,\frac{1}{\lambda}\right),
\]
that the MAP estimate is equivalent to solving the L2-regularized least squares problem
\[
f(w) = \frac{1}{2}\sum_{i=1}^n (w^Tx^i - y^i)^2 + \frac \lambda 2 \sum_{j=1}^d w_j^2,
\]
in the ``loss plus regularizer'' framework.
For each of the alternate assumptions below, write it in the ``loss plus regularizer'' framework (simplifying as much as possible):
\blu{\enum{
\item Gaussian likelihood with separate variance for each training example and Laplace prior
\[
y^i \sim \mathcal{N}(w^Tx^i,\sigma_i^2), \quad w_j \sim \mathcal{L}\left(0,\frac{1}{\lambda}\right).
\]
\item Robust student-$t$ likelihood and Gaussian prior centered at $u$.
\[
p(y^i | x^i, w) = \frac{1}{\sqrt{\nu}B\left(\frac 1 2,\frac \nu 2\right)}\left(1 + \frac{(w^Tx^i - y^i)^2}{\nu}\right)^{-\frac{\nu + 1}{2}}, \quad w_j \sim \mathcal{N}\left(u_j,\frac{1}{\lambda}\right),
\]
where $u$ is $d \times 1$, $B$ is the ``Beta" function, and the parameter $\nu$ is called the ``degrees of freedom".\footnote{This likelihood is more robust than the Laplace likelihood, but leads to a non-convex objective.}
\item Time-independent censored survival analysis likelihood with per-variable Laplace prior,
\[
p(y^i, v^i | x^i, w) = \exp(v^iw^Tx^i)\exp(-y^i\exp(w^Tx^i)), \quad w_j \sim \mathcal{N}\left(0,\frac{1}{\lambda_j}\right).
\]
Here, $y^i$ is a positive number giving the latest time that we observed patient $i$, and $v^i = 1$ if patient $i$ has quit the study while $v^i = 0$ if they are still in it.\footnote{This likelihood can be used to estimate survival times when some patients are still alive.}
}}
For this question, you do not need to convert to matrix notation.


\subsection{Gradients and Hessian in Matrix Notation}

Express the gradient $\nabla f(w)$ and Hessian $\nabla^2 f(w)$ of the following functions in matrix notation, simplifying as much as possible:
\blu{
\enum{
\item The quadratic function
\[
f(w) = w^Tu + u^TAw + \frac{1}{2}w^Tw + w^TAw,
\]
wher $u$ is $d \times 1$ and $A$ is $d \times d$ (not necessarily symmetric).
\item L2-regularized weighted least squares with non-Euclidean quadratic regularizaiton,
\[
f(w) = \frac{1}{2}\sum_{i=1}^n v_i(w^Tx^i - y^i)^2 + \frac{1}{2}\sum_{i=1}^d\sum_{j=1}^d w_iw_j\lambda_{ij}
\]
where you can use $V$ as a matrix with the $v_i$ along the diagonal and $\Lambda$ as a positive-definite $d \times d$ (symmetric) matrix with $\lambda_{ij}$ in position $(i,j)$.
\item Weighted L2-regularized probit regression,
\[
f(w) = - \sum_{i=1}^n \log p(y^i | x^i w) + \frac{1}{2}\sum_{j=1}^d u_jw_j^2.
\]
where $u$ is $d \times 1$, $y^i \in \{-1,+1\}$, and the likelihood of a single example $i$ is given by
\[
p(y^i| x^i, w) = \Phi(y^iw^Tx^i).
\]
where $\Phi$ is the cumulative distribution function (CDF) of the standard normal distribution.
}}

Hint: You can use the results from the linear and quadratic gradients and Hessians notes to simplify the derivations. You can use $0$ to represent the zero vector or a matrix of zeroes and $I$ to denote the identity matrix. It will help to convert the second question to matrix notation first. For the last question, it is useful to define a vector $c$ containing the CDF $\Phi(y^iw^Tx^i)$ as element $c_i$ and a vector $p$ containing the corresponding PDF as element $p_i$. For the probit question you'll need to define new vectors to express the gradient and Hessian in matrix notation (and remember the relationship between the PDF and CDF). As a sanity check, make sure that your results have the right dimension.




\section{Coding Questions}

\subsection{Regularization and Cross-Validation}



Download \emph{a1.zip} from the course webpage, and start Julia (verison of 0.6) in a directory containing the extracted files. If you run the script \emph{example\_nonLinear}, it will:
\enum{
\item Load a one-dimensional regression dataset.
\item Fit a least-squares linear regression model.
\item Report the test set error.
\item Draw a figure showing the training/testing data and what the model looks like.
}
This script uses the \emph{JLD} package to load the data and the \emph{PyPlot} package to make the plot. If you have not previously used these packages, they can be installed using:\footnote{Last term, several people (eventually including myself) had a runtime problem on some system. This seems to be fixed using the answer of 
K. Gkinis at this url: \url{https://stackoverflow.com/questions/46399480/julia-runtime-error-when-using-pyplot}}
\begin{verbatim}
Pkg.add("JLD")
Pkg.add("PyPlot")
\end{verbatim}

Unfortunately, this is not a great model of the data, and the figure shows that a linear model is probably not suitable.
\enum{
\item Write a function called \emph{leastSquaresRBFL2} that implements \emph{least squares using Gaussian radial basis functions (RBFs) and L2-regularization}. \\You should start from the \emph{leastSquares} function and use the same conventions: $n$ refers to the number of training examples, $d$ refers to the number of features, $X$ refers to the data matrix, $y$ refers to the targets, $Z$ refers to the data matrix after the change of basis, and so on. Note that you'll have to add two additional input arguments ($\lambda$ for the regularization parameter and $\sigma$ for the Gaussian RBF variance) compared to the \emph{leastSquares} function. To make your code easier to understand/debug, you may want to define a new function \emph{rbfBasis} which computes the Gaussian RBFs for a given training set, testing set, and $\sigma$ value. \blu{Hand in your function and the plot generated with $\lambda = 1$ and $\sigma = 1$.}
\item When dealing with larger datasets, an important issue is the dependence of the computational cost on the number of training examples $n$ and the number of features $d$. \blu{What is the cost in big-O notation of training the model on $n$ training examples with $d$ features under (a) the linear basis, and (b) Gaussian RBFs (for a fixed $\sigma$)? What is the cost of classifying $t$ new examples under these two bases? } Assume that multiplication by an $n$ by $d$ matrix costs $O(nd)$ and that solving a $d$ by $d$ linear system costs $O(d^3)$.
\item Modify the script to split the training data into a ``train'' and ``validation'' set (you can use half the examples for training and half for validation), and use these to select $\lambda$ and $\sigma$. \blu{Hand in your modified script and the plot you obtain with the best values of $\lambda$ and $\sigma$.}
\item There are reasons why this dataset is particularly well-suited to Gaussian RBFs are that (i) the period of the oscillations stays constant and (ii) we have evenly sampled the training data across its domain. If either of these assumptions are violated, the performance with our Gaussian RBFs might be much worse.
\blu{Consider a scenario where either (i) or (ii) is violated, and describe a way that you could address this problem.}
}

Note:  the \emph{distancesSquared} function in \emph{misc.jl} is a vectorized way to quickly compute the squared Euclidean distance between all pairs of rows in two matrices.




\subsection{Multi-Class Logistic Regression}


The script \emph{example\_multiClass.jl} loads a multi-class classification dataset and fits a ``one-vs-all'' logistic regression classifier, then reports the validation error and shows a plot of the data/classifier. The performance on the validation set is ok, but could be much better. For example, this classifier never even predicts some of the classes.

Using a one-vs-all classifier hurts performance because the classifiers are fit independently, so there is no attempt to calibrate the columns of the matrix $W$. An alternative to this independent model is to use the softmax probability,
\[
p(y^i | W, x^i) = \frac{\exp(w_{y^i}^Tx^i)}{\sum_{c=1}^k\exp(w_c^Tx^i)}.
\]
Here $c$ is a possible label and $w_{c}$ is column $c$ of $W$. Similarly, $y^i$ is the training label, $w_{y^i}$ is column $y^i$ of $W$. The loss function corresponding to the negative logarithm of the softmax probability is given by
\[
f(W) = \sum_{i=1}^n \left[-w_{y^i}^Tx^i + \log\left(\sum_{c' = 1}^k \exp(w_{c'}^Tx^i)\right)\right].
\]
Make a new function, \emph{softmaxClassifier}, which fits $W$ using the softmax loss from the previous section  instead of fitting $k$ independent classifiers. \blu{Hand in the code and report the validation error}.

Hint: you can use the \emph{derivativeCheck} function to help you debug the gradient of the softmax loss. 




\subsection{Robust Regression}



The script \emph{example\_outliers.jl} loads a one-dimensional regression dataset that has a non-trivial number of ``outlier'' data points. These points do not fit the general trend of the rest of the data, and pull the least squares model away from the main cluster of points. One way to improve the performance in this setting is simply to remove or downweight the outliers. However, in high-dimensions it may be difficult to determine whether points are indeed outliers (or the errors might simply be heavy-tailed). In such cases, it is preferable to replace the squared error with an error that is more robust to outliers. 

\enum{
\item
Write a new function, \emph{leastAbsolutes(X,y)}, that adds a bias variable and fits a linear regression model by minimizing the absolute error instead of the square error,
\[
f(w) = \norm{Xw- y}_1.
\]
You should turn this into a \emph{linear program} as shown in class, and you can solve this linear program using the \emph{linprog} function the \emph{MathProgBase} package. \blu{Hand in the new function and the updated plot.}
\item The previous question assumes that the ``outliers" are points that we don't want to model. But what if we want good performance in the worst case across \emph{all} examples (including the outliers)? In this setting we may want to consider a ``brittle" regression method that chases outliers in order to improve the worst-case error. For example, consider minimizing the absolute error in the worst-case,
\[
f(w) = \norm{Xw- y}_\infty.
\]
This objective function is non-smooth because of the absolute value function as well as the max function.
\blu{Show how to formulate this non-smooth optimization problem as a linear program}. 
\item Write and hand in a function, \emph{leastMax}, that fits this model using \emph{linprog} (after adding a bias variable). \blu{Hand in the new function and the updated plot.}
}
To use the \emph{linprog} function, you can  use:
\begin{verbatim}
using MathProgBase, GLPKMathProgInterface
solution = linprog(c,A,b,d,lb,ub,GLPKSolverLP())
x = solution.sol
\end{verbatim}
This requires installing the appropriate packages, and finds a vector $x$ minimizing the function $c^Tx$ subject to $d \leq Ax \leq b$ and lb $\leq x \leq $ ub. You can set values of $c$ to 0 for variables that don't affect the cost function, and you can set values in $b/d/$lb/ub (or the other variables) to appropirate infinite values if there are no lower/upper bounds.


 
\end{document}