hw03_model_sel.tex

\documentclass[11pt]{article}

\usepackage{fullpage}
\usepackage{amsmath, amssymb, bm, cite, epsfig, psfrag}
\usepackage{graphicx}
\usepackage{float}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{listings}
\usepackage{cite}
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{enumerate}
\usepackage{listings}
\usepackage{mathtools}
\lstloadlanguages{Python}
\usetikzlibrary{shapes,arrows}
%\usetikzlibrary{dsp,chains}

\DeclareFixedFont{\ttb}{T1}{txtt}{bx}{n}{9} % for bold
\DeclareFixedFont{\ttm}{T1}{txtt}{m}{n}{9}  % for normal
% Defining colors
\usepackage{color}
\definecolor{deepblue}{rgb}{0,0,0.5}
\definecolor{deepred}{rgb}{0.6,0,0}
\definecolor{deepgreen}{rgb}{0,0.5,0}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}

%\restylefloat{figure}
%\theoremstyle{plain}      \newtheorem{theorem}{Theorem}
%\theoremstyle{definition} \newtheorem{definition}{Definition}

\def\del{\partial}
\def\ds{\displaystyle}
\def\ts{\textstyle}
\def\beq{\begin{equation}}
\def\eeq{\end{equation}}
\def\beqa{\begin{eqnarray}}
\def\eeqa{\end{eqnarray}}
\def\beqan{\begin{eqnarray*}}
\def\eeqan{\end{eqnarray*}}
\def\nn{\nonumber}
\def\binomial{\mathop{\mathrm{binomial}}}
\def\half{{\ts\frac{1}{2}}}
\def\Half{{\frac{1}{2}}}
\def\N{{\mathbb{N}}}
\def\Z{{\mathbb{Z}}}
\def\Q{{\mathbb{Q}}}
\def\R{{\mathbb{R}}}
\def\C{{\mathbb{C}}}
\def\argmin{\mathop{\mathrm{arg\,min}}}
\def\argmax{\mathop{\mathrm{arg\,max}}}
%\def\span{\mathop{\mathrm{span}}}
\def\diag{\mathop{\mathrm{diag}}}
\def\x{\times}
\def\limn{\lim_{n \rightarrow \infty}}
\def\liminfn{\liminf_{n \rightarrow \infty}}
\def\limsupn{\limsup_{n \rightarrow \infty}}
\def\GV{Guo and Verd{\'u}}
\def\MID{\,|\,}
\def\MIDD{\,;\,}

\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{assumption}{Assumption}
\newtheorem{claim}{Claim}
\def\qed{\mbox{} \hfill $\Box$}
\setlength{\unitlength}{1mm}

\def\bhat{\widehat{b}}
\def\ehat{\widehat{e}}
\def\phat{\widehat{p}}
\def\qhat{\widehat{q}}
\def\rhat{\widehat{r}}
\def\shat{\widehat{s}}
\def\uhat{\widehat{u}}
\def\ubar{\overline{u}}
\def\vhat{\widehat{v}}
\def\xhat{\widehat{x}}
\def\xbar{\overline{x}}
\def\zhat{\widehat{z}}
\def\zbar{\overline{z}}
\def\la{\leftarrow}
\def\ra{\rightarrow}
\def\MSE{\mbox{\small \sffamily MSE}}
\def\SNR{\mbox{\small \sffamily SNR}}
\def\SINR{\mbox{\small \sffamily SINR}}
\def\arr{\rightarrow}
\def\Exp{\mathbb{E}}
\def\var{\mbox{var}}
\def\Tr{\mbox{Tr}}
\def\tm1{t\! - \! 1}
\def\tp1{t\! + \! 1}

\def\Xset{{\cal X}}

\newcommand{\one}{\mathbf{1}}
\newcommand{\abf}{\mathbf{a}}
\newcommand{\bbf}{\mathbf{b}}
\newcommand{\dbf}{\mathbf{d}}
\newcommand{\ebf}{\mathbf{e}}
\newcommand{\gbf}{\mathbf{g}}
\newcommand{\hbf}{\mathbf{h}}
\newcommand{\pbf}{\mathbf{p}}
\newcommand{\pbfhat}{\widehat{\mathbf{p}}}
\newcommand{\qbf}{\mathbf{q}}
\newcommand{\qbfhat}{\widehat{\mathbf{q}}}
\newcommand{\rbf}{\mathbf{r}}
\newcommand{\rbfhat}{\widehat{\mathbf{r}}}
\newcommand{\sbf}{\mathbf{s}}
\newcommand{\sbfhat}{\widehat{\mathbf{s}}}
\newcommand{\ubf}{\mathbf{u}}
\newcommand{\ubfhat}{\widehat{\mathbf{u}}}
\newcommand{\utildebf}{\tilde{\mathbf{u}}}
\newcommand{\vbf}{\mathbf{v}}
\newcommand{\vbfhat}{\widehat{\mathbf{v}}}
\newcommand{\wbf}{\mathbf{w}}
\newcommand{\wbfhat}{\widehat{\mathbf{w}}}
\newcommand{\xbf}{\mathbf{x}}
\newcommand{\xbfhat}{\widehat{\mathbf{x}}}
\newcommand{\xbfbar}{\overline{\mathbf{x}}}
\newcommand{\ybf}{\mathbf{y}}
\newcommand{\zbf}{\mathbf{z}}
\newcommand{\zbfbar}{\overline{\mathbf{z}}}
\newcommand{\zbfhat}{\widehat{\mathbf{z}}}
\newcommand{\Ahat}{\widehat{A}}
\newcommand{\Abf}{\mathbf{A}}
\newcommand{\Bbf}{\mathbf{B}}
\newcommand{\Cbf}{\mathbf{C}}
\newcommand{\Bbfhat}{\widehat{\mathbf{B}}}
\newcommand{\Dbf}{\mathbf{D}}
\newcommand{\Gbf}{\mathbf{G}}
\newcommand{\Hbf}{\mathbf{H}}
\newcommand{\Ibf}{\mathbf{I}}
\newcommand{\Kbf}{\mathbf{K}}
\newcommand{\Pbf}{\mathbf{P}}
\newcommand{\Phat}{\widehat{P}}
\newcommand{\Qbf}{\mathbf{Q}}
\newcommand{\Rbf}{\mathbf{R}}
\newcommand{\Rhat}{\widehat{R}}
\newcommand{\Sbf}{\mathbf{S}}
\newcommand{\Ubf}{\mathbf{U}}
\newcommand{\Vbf}{\mathbf{V}}
\newcommand{\Wbf}{\mathbf{W}}
\newcommand{\Xhat}{\widehat{X}}
\newcommand{\Xbf}{\mathbf{X}}
\newcommand{\Ybf}{\mathbf{Y}}
\newcommand{\Zbf}{\mathbf{Z}}
\newcommand{\Zhat}{\widehat{Z}}
\newcommand{\Zbfhat}{\widehat{\mathbf{Z}}}
\def\alphabf{{\boldsymbol \alpha}}
\def\betahat{\widehat{\beta}}
\def\betabf{{\boldsymbol \beta}}
\def\betabfhat{{\widehat{\bm{\beta}}}}
\def\epsilonbf{{\boldsymbol \epsilon}}
\def\mubf{{\boldsymbol \mu}}
\def\lambdabf{{\boldsymbol \lambda}}
\def\etabf{{\boldsymbol \eta}}
\def\xibf{{\boldsymbol \xi}}
\def\taubf{{\boldsymbol \tau}}
\def\sigmahat{{\widehat{\sigma}}}
\def\thetabf{{\bm{\theta}}}
\def\thetabfhat{{\widehat{\bm{\theta}}}}
\def\thetahat{{\widehat{\theta}}}
\def\mubar{\overline{\mu}}
\def\muavg{\mu}
\def\sigbf{\bm{\sigma}}
\def\etal{\emph{et al.}}
\def\Ggothic{\mathfrak{G}}
\def\Pset{{\mathcal P}}
\newcommand{\bigCond}[2]{\bigl({#1} \!\bigm\vert\! {#2} \bigr)}
\newcommand{\BigCond}[2]{\Bigl({#1} \!\Bigm\vert\! {#2} \Bigr)}
\newcommand{\tran}{^{\text{\sf T}}}
\newcommand{\herm}{^{\text{\sf H}}}
\newcommand{\bkt}[1]{{\langle #1 \rangle}}
\def\Norm{{\mathcal N}}
\newcommand{\vmult}{.}
\newcommand{\vdiv}{./}


% Python style for highlighting
\newcommand\pythonstyle{\lstset{
language=Python,
backgroundcolor=\color{backcolour},
commentstyle=\color{deepgreen},
basicstyle=\ttm,
otherkeywords={self},             % Add keywords here
keywordstyle=\ttb\color{deepblue},
emph={MyClass,__init__},          % Custom highlighting
emphstyle=\ttb\color{deepred},    % Custom highlighting style
stringstyle=\color{deepgreen},
%frame=tb,                         % Any extra options here
showstringspaces=false            %
}}

% Python environment
\lstnewenvironment{python}[1][]
{
\pythonstyle
\lstset{#1}
}
{}

% Python for external files
\newcommand\pythonexternal[2][]{{
\pythonstyle
\lstinputlisting[#1]{#2}}}

% Python for inline
\newcommand\pycode[1]{{\pythonstyle\lstinline!#1!}}

\begin{document}

\title{Introduction to Machine Learning\\
Homework 3:  Model Order Selection}
\author{Prof. Sundeep Rangan}
\date{Fall 2017}

\maketitle

\begin{enumerate}

\item For each of the following pairs of true functions $f_0(\xbf)$ and model classes $f(\xbf,\betabf)$
determine: (i) if the model class is linear; (ii) if there is no under-modeling; and (iii) if there
is no under-modeling, what is the true parameter?
\begin{enumerate}[(a)]
  \item $f_0(x) = 1+2x$,  $f(x,\betabf) = \beta_0+\beta_1x+\beta_2x^2$
  \item $f_0(x) = 1 + 1/(2+3x)$, $f(x,a_0,a_1,b_0,b_1) = (a_0+a_1x)/(b_0+b_1 x)$.
  \item $f_0(x) = (x_1-x_2)^2$ and
\[
    f(\xbf,a,b_1,b_2,c_1,c_2) = a + b_1x_1 + b_2x_2 + c_{1}x_1^2 +  + c_{2}x_2^2.
\]
\end{enumerate}

\item In this problem, we will see how to calculate the bias when
there is undermodeling.  Suppose that training data $(x_i,y_i)$, $i=1,\ldots,n$
is fit using a simple linear model of the form,
\[
    \hat{y} = f(x,\betabf) = \beta_0 + \beta_1 x.
\]
However, the true relation between $x$ and $y$ is given
\[
    y = f_0(x), \quad f_0(x)=\beta_{00} + \beta_{01}x + \beta_{02} x^2,
\]
where the ``true" function $f_0(x)$ is quadratic and
$\betabf_0=(\beta_{00},\beta_{01},\beta_{02})$ is the vector of the true parameters. There is no noise.
\begin{enumerate}[(a)]
\item Write an expression
for the least-squares estimate $\betabfhat = (\betahat_0,\betahat_1)$ in terms of the training data
$(x_i,y_i)$, $i=1,\ldots,n$.
These expressions will  involve multiple steps.
You do not need to simplify the equations.
Just make sure you state clearly how one would compute $\betabfhat$ from the training values.

\item Using the fact that $y_i=f_0(x_i)$ in the training data, write the expression for
$\betabf = (\betahat_0,\betahat_1)$ in terms of the values $x_i$ and the true parameter
values $\betabf_0$.
Again, you do not need to simplify the equations.
Just make sure you state clearly how one would compute $\betabfhat$ from the true
parameter vector $\betabf_0$ and $\xbf$.

\item
Suppose that the true parameters are $\betabf_0=(1,2,-1)$ and
the model is trained using 10 values $x_i$ uniformly spaced in $[0,1]$.
Write a short python program to compute the estimate parameters $\betabfhat$.
Plot the estimated function $f(x,\betabfhat)$ and true function $f_0(x)$
 for $x \in [0,3]$.

\item For what value $x$ in this range $x \in [0,3]$ is the bias
$\mathrm{Bias}^2(x) = (f(x,\betabfhat)-f_0(x))^2$ largest?
\end{enumerate}


\item A medical researcher wishes to evaluate a new diagnostic test for cancer.
A clinical trial is conducted where the diagnostic measurement $y$ of each patient is recorded along with
attributes of a sample of cancerous tissue from the patient.
Three possible models are considered for the diagnostic measurement:
\begin{itemize}
\item Model 1:  The diagnostic measurement $y$ depends linearly only on the cancer volume.
\item Model 2:  The diagnostic measurement $y$ depends linearly on the cancer volume and the patient's age.
\item Model 3:  The diagnostic measurement $y$ depends linearly on the cancer volume and the patient's age,
but the dependence (slope) on the cancer volume is different for two types of cancer -- Type I and II.
\end{itemize}


\begin{enumerate}[(a)]
  \item Define variables  for the cancer volume, age and cancer type and write a linear model
  for the predicted value $\hat{y}$ in terms of these variables for each of the three models above.
  For Model 3, you will want to use one-hot coding.
  
  \item What are the numbers of parameters in each model?  Which model is the most complex?

  \item Since the models in part (a) are linear, given training data, 
  we should have $\hat{\ybf} = \Abf\betabf$ 
  where $\hat{\ybf}$ is the vector of predicted values on the training data,
  $\Abf$ is a feature matrix and $\betabf$ is the vector of parameters.
  To test the different models, data is collected from 100 patients.  The records of the first three patients are shown below:
\begin{center}
\begin{tabular}[h]{|c|c|c|c|c|} \hline
Patient & Measurement & Cancer & Cancer  & Patient \\
 ID &  $y$ &type & volume & age \\ \hline
12 & 5 &  I  & 0.7 & 55  \\ \hline
34 & 10 & II & 1.3 & 65  \\ \hline
23 & 15 & II & 1.6 & 70  \\ \hline
$\vdots$ & $\vdots$ & $\vdots$ & $\vdots$  & $\vdots$  \\ \hline
\end{tabular}
\end{center}
Based on this data, what would be the values of first three rows of the three
$\Abf$ matrices be for the three models in part (a)?

  \item To evaluate the models, 10-fold cross validation is used with the following results.
\begin{center}
\begin{tabular}[h]{|c|c|c|c|c|} \hline
Model & Mean training  & Mean test      & Test RSS \\
      & RSS            & RSS            & std deviation \\ \hline
1 & 2.0  & 2.01 & 0.03 \\ \hline
2 & 0.7  & 0.72 & 0.04 \\ \hline
3 & 0.65 & 0.70 & 0.05 \\ \hline
\end{tabular}
\end{center}
All RSS values are per sample, and the last column is the (biased)
standard deviation -- not the standard error.
Which model should be selected based on the ``one standard error rule"?

\end{enumerate}



\end{enumerate}
\end{document}