\documentclass[a4paper]{article}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{natbib}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{paralist}
\usepackage{epstopdf}
\usepackage{tabularx}
\usepackage{longtable}
\usepackage{multirow}
\usepackage{multicol}
\usepackage[hidelinks]{hyperref}
\usepackage{fancyvrb}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{float}
\usepackage{paralist}
\usepackage[svgname]{xcolor}
\usepackage{enumerate}
\usepackage{array}
\usepackage{times}
\usepackage{url}
\usepackage{fancyhdr}
\usepackage{comment}
\usepackage{environ}
\usepackage{times}
\usepackage{textcomp}
\usepackage{caption}





\urlstyle{rm}

\setlength\parindent{0pt} % Removes all indentation from paragraphs
\theoremstyle{definition}
\newtheorem{definition}{Definition}[]
\newtheorem{conjecture}{Conjecture}[]
\newtheorem{example}{Example}[]
\newtheorem{theorem}{Theorem}[]
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}

\floatname{algorithm}{Procedure}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\norm}[1]{\lVert#1\rVert}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\br}[1]{\{#1\}}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\renewcommand{\qedsymbol}{$\blacksquare$}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Cov}{\mathrm{Cov}}

\newcommand{\vc}[1]{\boldsymbol{#1}}
\newcommand{\xv}{\vc{x}}
\newcommand{\Sigmav}{\vc{\Sigma}}
\newcommand{\alphav}{\vc{\alpha}}
\newcommand{\muv}{\vc{\mu}}

\def\x{\mathbf x}
\def\y{\mathbf y}
\def\w{\mathbf w}
\def\v{\mathbf v}
\def\E{\mathbb E}
\def\V{\mathbb V}

\newcommand \expect {\mathbb{E}}
\newcommand \mle [1]{{\hat #1}^{\rm MLE}}
\newcommand \map [1]{{\hat #1}^{\rm MAP}}
%\newcommand \argmax {\operatorname*{argmax}}
%\newcommand \argmin {\operatorname*{argmin}}
\newcommand \code [1]{{\tt #1}}
\newcommand \datacount [1]{\#\{#1\}}
\newcommand \ind [1]{\mathbb{I}\{#1\}}
\newcommand \bs [1]{\boldsymbol{#1}}


% TO SHOW SOLUTIONS, include following (else comment out):
\newenvironment{soln}{
     \leavevmode\color{blue}\ignorespaces
 }{}

% TO ONLY SHOW HOMEWORK QUESTIONS, include following:
%\NewEnviron{soln}
% {}
% {}



\hypersetup{
%    colorlinks,
    linkcolor={red!50!black},
    citecolor={blue!50!black},
    urlcolor={blue!80!black}
}

\geometry{
  top=1in,            % <-- you want to adjust this
  inner=1in,
  outer=1in,
  bottom=1in,
  headheight=3em,       % <-- and this
  headsep=2em,          % <-- and this
  footskip=3em,
}


\pagestyle{fancyplain}
\lhead{\fancyplain{}{Homework 3: Linear and Logistic Regression}}
\rhead{\fancyplain{}{10-601 Introduction to Machine Learning}}
\cfoot{\thepage}

\title{\textsc{Homework 3: \\  Linear Regression and Logistic Regression}} % Title

\newcommand{\outDate}{Sep. 14, 2016}
\newcommand{\dueDate}{5:30 pm, Sep. 26, 2016}

\author{\href{http://www.cs.cmu.edu/~mgormley/courses/10601b-f16/}{CMU 10601: \textsc{Machine Learning (Fall 2016)}} \\
OUT: \outDate{} \\
DUE: \dueDate{} \\ 
TAs: Simon Shaolei Du, Tianshu Ren, Sriram Vasudevan} 

\date{}

\begin{document}

\maketitle 

\section*{Instructions}
\begin{itemize}
\item \textbf{Homework Submission:} Submit your answers and results to \href{https://www.gradescope.com}{Gradescope}.
You will use Autolab to submit your code in Problem 2.2. 
For Gradescope, you will need to specify which pages go with which question. 
We provide a LaTeX template which you can use to type up your solutions. 
Please check Piazza for updates about the homework.
\item \textbf{Collaboration policy}: 
The purpose of student collaboration is to facilitate learning, not to circumvent it. Studying the material in groups is strongly encouraged. It is also allowed to seek help from other students in understanding the material needed to solve a particular homework problem, provided no written notes (including code) are shared, or are taken at that time, and provided learning is facilitated, not circumvented. The actual solution must be done by each student alone. The presence or absence of any form of help or collaboration, whether given or received, must be explicitly stated and disclosed in full by all involved.
Please refer to the course \href{http://www.cs.cmu.edu/~mgormley/courses/10601b-f16/about.html}{webpage}.
  
\end{itemize}
\clearpage


\section{Linear Regression [40 pts]}
In this problem, you will derive the linear regression and ridge linear regression formulas from a statistical point of view.
First let's see how frequentists approach the following inference problem:\\
Consider the model 
$$p(y|\x) = \mathcal{N}(y|\w^\top\x,\sigma^2)$$ where $\x$ is the feature, $y$ is the label.
$\mathcal{N}(y|\mu,\sigma^2)$ is the Gaussian distribution with mean $\mu$ and variance $\sigma^2$.
Throughout this question, we assume $\sigma$ is known.
Suppose we have the following data independently generated from this model: $$\mathcal{D} = (\mathbf{X},\mathbf{y})$$ where $\mathbf{X} \in \mathbb{R}^{d \times n}$, the $i$-th column $\mathbf{X}_i$ are the features of the $i$-th training sample and $y \in \mathbb{R}^n$, $y_i$ is the label of the $i$-th training sample. 
\begin{enumerate}[(a)]
\item {\bf [10 Points]} Please write out the likelihood function $p\left(\mathcal{D}|\w\right)$ in terms of $\mathbf{X}$,$y$,$w$ and $\sigma$.
\newline
    \begin{soln}
    Your answer here.
    \end{soln}
\item {\bf [10 Points]} Maximum Likelihood Estimation: Please derive a formula for $\w$ that maximize $p\left(\mathcal{D}|\w\right)$ (hint: consider log-likelihood).
\vspace{0.3cm}
\newline
    \begin{soln}
    Your answer here.
    \end{soln}
\item {\bf [10 Points]} Now suppose we have become Bayesians and we have a prior for $\w$: 
\[
p(\w) = \Pi_{j=1}^d\mathcal{N}\left(w_j|0,\gamma^2\right),
\]i.e. each coordinate of $\w$ is independent of other coordinates and have the mean $0$ and variance $\gamma^2$.
Again, we assume variance $\gamma^2$ is known. Please write out the posterior probability: $p\left(\w|\mathcal{D}\right)$ in terms of $\mathbf{X}$, $y$, $\w$, $\sigma$ and $\gamma$.
\newline
    \begin{soln}
    Your answer here.
    \end{soln}
\item {\bf [10 Points]} Please derive a formula for $\w$ that maximize the posterior (hint: use Bayes' rule to simplify calculation).
\newline
    \begin{soln}
    Your answer here.
    \end{soln}
\end{enumerate}

\clearpage %do not erase

\section{Logistic Regression [60 pts]}
You will implement a logistic regression classifier and apply it to a two-class classification problem. 
Your code will be autograded by a series of test scripts that run on Autolab. 
To get started, download the template for Homework 3 from the course website, and extract the contents of the compressed directory. 
In the archive, you will find one~\code{.m} file for each of the functions that you are asked to implement, along with a file called \code{HW3Data.mat} that contains the data for this problem. 
You can load the data into Octave by executing \code{load("HW3Data.mat")} in the Octave interpreter. 
Make sure not to modify any of the function headers that are provided.
\subsection{Theoretical Derivation}

\begin{enumerate}[(a)]
\item {\bf [5 Points]} In logistic regression, our goal is to learn a set of parameters by maximizing the conditional log likelihood of the data. Assuming you are given a dataset with $n$ training examples and $p$ features, write down a formula for the conditional log likelihood of the training data in terms of the the class labels $y^{(i)}$, the features $x^{(i)}_1, \ldots, x^{(i)}_p$, and the parameters $w_0, w_1, \ldots, w_p$, where the superscript $(i)$ denotes the sample index. This will be your objective function for gradient ascent. \newline
    \begin{soln}
    Your answer here.
    \end{soln}
\item {\bf [5 Points]} Compute the partial derivative of the objective function with respect to $w_0$ and with respect to an arbitrary $w_j$, i.e.~derive $\partial f / \partial w_0$ and $\partial f / \partial w_j$, where $f$ is the objective that you provided above.
Please show all derivatives can be written in a finite sum form.\newline
    \begin{soln}
    Your answer here.
    \end{soln}
\end{enumerate}

    
\subsection{Implementation}
\begin{enumerate}[(a)]
\item {\bf [30 Points]} Implement a logistic regression classifier using stochastic gradient ascent by filling in the missing code for the following functions: 
\begin{itemize}
\item Calculate the value of the objective function: \code{obj = LR\_CalcObj(XTrain,yTrain,wHat)}
\item Calculate the stochastic gradient: \code{sg = LR\_CalcSG(x,y,wHat)}
\item Update the parameter value: \code{wHat = LR\_UpdateParams(wHat,sg,eta)}
\item Check whether gradient ascent has converged (whether the difference in the values is less than the tolerance): \code{hasConverged = LR\_CheckConvg(oldObj,newObj,tol)}
\item Complete the implementation of gradient ascent: \code{[wHat,objVals] = LR\_SGA(XTrain,yTrain)} (Note: Although this is supposed to be stochastic, please do not randomize your training instances for the purpose of this assignment, since we will be evaluating your code on Autolab.)
\item Predict the labels for a set of test examples: \\
\code{[yHat,numErrors] = LR\_PredictLabels(XTest,yTest,wHat)}
\end{itemize}
where the arguments and return values of each function are defined as follows:
\begin{itemize}
\item \code{XTrain} is an $n \times p$ dimensional matrix that contains one training instance per row
\item \code{yTrain} is an $n \times 1$ dimensional vector containing the class labels for each training instance
\item \code{x} is an $1 \times p$ dimensional vector that contains one training instance
\item \code{y} is a scalar, a class labels for a single training instance
\item \code{wHat} is a $p+1 \times 1$ dimensional vector containing the regression parameter estimates $\hat{w}_0, \hat{w}_1, \ldots, \hat{w}_p$
\item \code{hasConverged} is a scalar that is either true or false.
\item \code{sg} is a $p+1 \times 1$ dimensional vector containing the value of the a stochastic gradient of the objective function with respect to each parameter in \code{wHat}
\item \code{eta} is the gradient ascent step size that you should set to \code{eta = 0.5/sqrt(n)} where \code{n} is the iteration number
\item \code{obj}, \code{oldObj} and \code{newObj} are values of the objective function
\item \code{tol} is the convergence tolerance, which you should set to \code{tol = 0.0001}
\item \code{objVals} is a vector containing the objective value at each iteration of gradient ascent
\item \code{XTest} is an $m \times p$ dimensional matrix that contains one test instance per row
\item \code{yTest} is an $m \times 1$ dimensional vector containing the true class labels for each test instance
\item \code{yHat} is an $m \times 1$ dimensional vector containing your predicted class labels for each test instance
\item \code{numErrors} is the number of misclassified examples, i.e.~the differences between \code{yHat} and \code{yTest}
\end{itemize}
To complete the \code{LR\_SGA} function, you should use the helper functions \code{LR\_CalcObj}, \code{LR\_CalcSG}, \code{LR\_UpdateParams}, and \code{LR\_CheckConvg}, so we can give you partial credits.
\item {\bf [0 Points]} Train your logistic regression classifier on the data provided in \code{XTrain} and \code{yTrain} with \code{LR\_SGA}, and then use your estimated parameters \code{wHat} to calculate predicted labels for the data in \code{XTest} with \code{LR\_PredictLabels}. 
\item {\bf [5 Points]} Report the number of misclassified examples in the test set.\newline
    \begin{soln}
    Your answer here.
    \end{soln}
\item {\bf [5 Points]} Plot the value of the objective function on each iteration of stochastic gradient ascent, with the iteration number on the horizontal axis and the objective value on the vertical axis. 
Make sure to include axis labels and a title for your plot. 
Report the number of iterations that are required for the algorithm to converge.\newline
    \begin{soln}
    Your answer here.
    \end{soln}
\item {\bf [10 Points]} Next, you will evaluate how the training and test error change as the training set size increases. For each value of $k$ in the set $\{10, 20, 30, \ldots, 480, 490, 500\}$, first choose a random subset of the training data of size $k$ using the following code:
\begin{align*}
&\code{subsetInds = randperm(n,k)} \\
&\code{XTrainSubset = XTrain(subsetInds,:)} \\
&\code{yTrainSubset = yTrain(subsetInds)}
\end{align*}
Then re-train your classifier using \code{XTrainSubset} and \code{yTrainSubset}, and use the estimated parameters to calculate the number of misclassified examples on both the training set \code{XTrainSubset} and \code{yTrainSubset} and on the original test set \code{XTest} and \code{yTest}. Finally, generate a plot with two lines: in blue, plot the value of the training error against $k$, and in red, plot the value of the test error against $k$, where the error should be on the vertical axis and training set size should be on the horizontal axis. Make sure to include a legend in your plot to label the two lines. Describe what happens to the training and test error as the training set size increases, and provide an explanation for why this behavior occurs.\newline
    \begin{soln}
    Your answer here.
    \end{soln}
\end{enumerate}



\bibliographystyle{apalike}


%----------------------------------------------------------------------------------------


\end{document}