prob_mult_reg.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}
\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\betabf{{\boldsymbol \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\phibf{{\boldsymbol \phi}}
\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\\
Problems Unit 3:  Multiple Linear Regression}
\author{Prof. Sundeep Rangan}
\date{}

\maketitle

\begin{enumerate}

\item An online retailer like Amazon wants to determine which products
 to promote based on reviews.  They only want to promote products that are likely
 to sell. For each product, they have past sales as well as
 reviews.  The reviews have both a numeric score (from 1 to 5) and text.
\begin{enumerate}[(a)]
\item To formulate this as a machine learning problem, suggest
a target variable that the online retailer could use.

\item For the predictors of the target variable, a data scientist
suggests to combine the numeric score with frequency of occurrence
of words that convey judgement like ``bad", ``good", and ``doesn't work."
Describe a possible linear model for this relation.

\item Now, suppose that
some reviews have a numeric score from 1 to 5 and others have a score
from 1 to 10.  How would change your features?

\item Now suppose the reviews have either (a) a score from 1 to 5;
(b) a rating that is simply good or bad; or (c) no numeric rating at all.
How would you change your features?

\item For the frequency of occurrence of a word such as ``good",
which variable would you suggest to use as a predictor:
(a) total number of reviews with the word ``good";
or (b) fraction of reviews with the word ``good"?
\end{enumerate}

\item Suppose we are given data:
\begin{center}
\begin{tabular}[h]{|c|c|c|c|c|} \hline
$x_{i1}$ & 0 & 0 & 1 & 1 \\ \hline
$x_{i2}$ & 0 & 1 & 0 & 1 \\ \hline
$y_i$ &    1 & 4 & 3 & 7  \\ \hline
\end{tabular}
\begin{enumerate}[(a)]
\item Write an equation for a linear model for $y$ in terms of $x_1$ and $x_2$.

\item Given the data compute the least-squares estimate for the parameters
in the model.
\end{enumerate}
\end{center}


\item Write each of the following models as transformed linear models.
That is, find a parameter vector $\betabf$ in terms of the given parameters $a_i$
and a set basis functions of functions $\phibf(\xbf)$ such that $\hat{y}=\betabf\tran\phi(\xbf)$.
Also, show how to recover the original parameters $a_i$ from the parameters $\beta_j$:
\begin{enumerate}[(a)]
\item $\hat{y} = (a_1x_1+a_2x_2)e^{-x_1-x_2}$.
\item $\hat{y} = \begin{cases}
    a_1 + a_2x & \mbox{if } x < 1 \\
    a_3 + a_4x & \mbox{if } x \geq 1
    \end{cases}$
\item $\hat{y} = (1+a_1x_1)e^{-x_2+a_2}$.
\end{enumerate}

\item An automobile engineer wants to model the relation
between the accelerator control and the velocity of the car.
The relation may not be simple since there is a lag in depressing
the accelerator and the car actually accelerating.  To determine
the relation, the engineers measures the acceleration control input $x_k$
and velocity of the car $y_k$ at time instants $k=0,1,\ldots,T-1$.
The measurements are made at some sampling rate, say once every 10~ms.
The engineer then wants to fit a model of the form
\beq \label{eq:yxfilt}
    y_k = \sum_{j=1}^M a_j y_{k-j} + \sum_{j=0}^N b_j x_{k-j} + \epsilon_k,
\eeq
for coefficients $a_j$ and $b_j$.
In engineering this relation is called a \emph{linear filter} and
it statistics it is called an \emph{auto-regressive moving average (ARMA)}
model.
\begin{enumerate}[(a)]
\item Describe a vector $\betabf$ with the unknown parameters.
How many unknown parameters are there?

\item Describe the matrix $\Abf$ and target vector $\ybf$ so that we can
rewrite the model \eqref{eq:yxfilt} in matrix form,
\[
    \ybf = \Abf \betabf + \epsilonbf.
\]
Your matrix $\Abf$ will have entries of $y_k$ and $x_k$ in it.

\item (Graduate students only)
Show that, for $T \gg N$ and $T \gg M$,
the coefficients of $(1/T)\Abf\tran\Abf$ and $(1/T)\Abf\tran\ybf$
can be approximately
computed from the so-called auto-correlation functions
\[
    R_{xy}(\ell) = \frac{1}{T} \sum_{k=0}^{T-1} x_ky_{k+\ell}, \quad
    R_{yy}(\ell) = \frac{1}{T} \sum_{k=0}^{T-1} y_ky_{k+\ell}, \quad
    R_{xx}(\ell) = \frac{1}{T} \sum_{k=0}^{T-1} x_k x_{k+\ell}, \quad
\]
In the sum, we take $x_k=0$ or $y_k=0$ whenever $k < 0$ or $k \geq T$.

\end{enumerate}

\item In audio processing, one often wants to find tonal sounds in
segments of the recordings.  This can be formulated as follows:
We are given samples of an audio segment,
$x_k$, $k=0,\ldots,N-1$, and wish to fit a model of the form,
\beq \label{eq:xsincos}
    x_k \approx \sum_{\ell = 1}^L a_\ell \cos(\Omega_\ell k) + b_\ell \sin(\Omega_\ell k),
\eeq
where $L$ are a number of tones present in the audio segment;
$\Omega_\ell$ are the tonal frequencies and $a_\ell$ and $b_\ell$ are
the coefficients.
\begin{enumerate}[(a)]
\item Show that if the frequencies $\Omega_\ell$ are given, we can solve
for the coefficients $a_\ell$ and $b_\ell$ using linear regression.
Specifically, rewrite the model \eqref{eq:xsincos} as
$\xbf \approx \Abf\betabf$ for appropriate $\xbf$, $\Abf$ and $\betabf$.
Then describe exactly how we obtain the coefficients $a_\ell$ and $b_\ell$
from this model.

\item Now suppose the frequencies $\Omega_\ell$ were not known.
If we had to solve for the parameters $a_\ell$, $b_\ell$ and $\Omega_\ell$,
would the problem be a linear regression problem?
\end{enumerate}

\item \emph{Python broadcasting}.  Rewrite the following code without for-loops using
vectorization and python broadcasting.
\begin{enumerate}[(a)]
\item Given a data matrix \pycode{X} and vector \pycode{beta} compute a vector \pycode{yhat}:
\begin{python}
    n = X.shape[0]
    yhat = np.zeros(n)
    for i in range(n):
        yhat[i] = beta[0]*X[i,0] + beta[1]*X[i,1] + beta[2]*X[i,1]*X[i,2]
\end{python}

\item Given vectors \pycode{x}, \pycode{alpha}, and \pycode{beta} computes a vector \pycode{yhat}:
\begin{python}
    n = len(x)
    m = len(alpha)
    yhat = np.zeros(n)
    for i in range(n):
        for j in range(m):
            yhat[i] += alpha[j]*np.exp(-beta[j]*x[i])
\end{python}

\item Given arrays \pycode{x} and \pycode{y}, find the squared distances \pycode{dist}:
\begin{python}
    n,d = x.shape
    m,d = y.shape
    dist = np.zeros((n,m))
    for i in range(n):
        for j in range(m):
            for k in range(d):
                dist[i,j] += (x[i,k]-y[j,k])**2
\end{python}

\end{enumerate}

\end{enumerate}

\end{document}