\documentclass[12pt]{article}
\input{defs}

\usepackage{amsmath,amsfonts,color,graphicx}

\setlength{\parindent}{0pt}
\setlength{\parskip}{4pt}

\addtolength{\evensidemargin}{-0.5in}
\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\textwidth}{1in}
\addtolength{\topmargin}{-0.5in}
\addtolength{\textheight}{1in}

% \renewcommand{\comment}[1]{\begin{minipage}{6in}\color{red}{#1}\end{minipage}}

\renewcommand{\today}{Due Tuesday, October 22 , in class}
\title{\Large\bf 6.867 Machine Learning}
\author{\bf Problem set 3}

\begin{document}
\maketitle
\input{../guide.tex}
\section*{Problem 1: regularization}
{\bf Reference:} Lectures 6,7.


Here we try to understand a bit better how regularization works in
terms of limiting ``effective'' number of choices. Consider again a
simple logistic regression model of the form
\[
P(y=1|x,\bw) = g(\,w_0+w_1x\,)
\]
where $x\in{\cal R}$ is the input and $\bw = [w_0\:w_1]^T$ are the
parameters. We are interested in the probability that the label is
``1'' for a specific input $x = -1$. In other words, we need to
evaluate $P(y=1|x=-1,\bw) = g(w_0-w_1)$, where the parameters are
estimated on the basis of a training set discussed below. 

Small differences in our predictions, say differences smaller than
$\epsilon = 0.1$, are considered immaterial. By predictions we mean here
probabilities $P(y=1|x=-1,\bw)$ and not log-probabilities $\log
P(y=1|x=-1,\bw)$. One way to capture the idea that some predictions
can be considered equivalent is to divide the set of possible
predictions (interval $[0,1]$) into smaller regions. We care only
about which region our prediction falls into but not variations within
each region. For $\epsilon = 0.1$, such regions could be
\begin{equation}
[0,0.1], [0.1,0.2],\ldots, [0.9,1]
\label{intervals}
\end{equation}
For simplicity we don't care about the single point of overlap between
each consecutive region.

\begin{enumerate}
\item[] 
\problem{10} Plot the regions in the parameter
space $(w_0,w_1)$ corresponding to \eqref{intervals}. For example, one such region should consist of all
the parameters $\bw$ for which $P(y=1|x=-1,\bw)\in [0,0.1]$.

\problem{5} Suppose now that we estimate the parameters $\bw$ by
maximizing the log-likelihood of the training labels subject to a
regularization constraint $\|\bw\|\leq 1$. How many different
predictions can we possibly make as a result? In other words, are
there intervals in eq. \eqref{intervals} that our predictions for the
test point $x=-1$ could not possibly reach regardless of the training
set?

\problem{15} Consider now four possible training sets, each containing
only two training examples: 
\begin{eqnarray}
1. && (x=0,y=1), (x=1,y=1)\\
2. && (x=0,y=0), (x=1,y=1)\\
3. && (x=0,y=1), (x=1,y=0)\\
4. && (x=0,y=0), (x=1,y=0)
\end{eqnarray}
The parameters in each case will be estimated by maximizing penalized
log-likelihood. For example, in response to the first training set, we
would find $\hat{\bw}$ that maximize
\begin{eqnarray}
\lefteqn{\log P(y=1|x=0,\bw) + \log P(y=1|x=1,\bw) - \frac{\lambda}{2}
\|\bw\|2}
&& \\
&=& \log g(\,w_0\,) + \log g(\,w_0+w_1\,) - \frac{\lambda}{2}(w_0^2+w_1^2)
\label{penlik}
\end{eqnarray}
where $\lambda>0$ is a regularization parameter. We would like to
understand a bit the effect of the regularization parameter. In
particular, we'd like to find a setting of this parameter such that
our predictions $P(y=1|x=-1,\bw)$ for the test point $x=-1$ would be
considered equivalent regardless of which one of the four training
sets we would use. In practice we would never set the regularization
parameter to such a value since our predictions would not vary
sufficiently on the basis of the actual training examples (one could
call this over-regularization). The process of finding the value is
nevertheless instructive and hopefully help us understand
regularization a bit better. Let's proceed in stages:
\begin{enumerate}
\item[a)] By increasing regularization (increasing $\lambda$) can we
guarantee that the predictions will eventually fall within a single
interval defined in eq. (\ref{intervals}) regardless of the training
set? If yes, give the interval.  If not, give another interval of
length 0.1 for which the guarantee does hold.
\item[b)] What are the inequality constraints that the parameters must
satisfy so that the predictions always fall within your choice of the
interval?
\item[c)] Suppose we regularize the parameters by imposing a strict
norm constraint $\|\bw\|\leq c$ rather than adding a penalty to the
log-likelihood function. What would $c$ have to be so that all the
predictions would fall within your choice of the interval?
\item[d)] Let's now switch back to ``soft'' regularization by
including $\lambda/2\,\|\bw\|^2$ as a penalty in the log-likelihood
function, as in eq. (\ref{penlik}). What order of magnitude do you
expect $\lambda$ has to be so that the resulting $\hat\bw$ would
satisfy $\|\hat\bw\|\leq c$ for any of the four training sets?
\end{enumerate}

\end{enumerate}


\section*{Problem 2: Support Vector Machines}
{\bf Reference:} Lectures 7,8. 

In this problem we will look at a very simple example of Support
Vector Machine.
We are given a set of 6 2D points in the space $(x_1,x_2)$ , labeled as belonging to one of the two
classes:\\

\begin{minipage}[t]{.6\textwidth}
\begin{tabular}{llll}
Class 0 & $\mathbf{x}_1=[0,0]^T$, & $\mathbf{x}_2=[-1,1]^T$,
&$\mathbf{x}_3=[-1,-1]^T$   \\
Class 1 & $\mathbf{x}_4=[1,1]^T$, & $\mathbf{x}_5=[2,0]^T$,
&$\mathbf{x}_6=[2,-1]^T$ 
\end{tabular}
\end{minipage}[t]
\;\;
\begin{minipage}{.3\textwidth}
\includegraphics[width=.95\textwidth]{svmpoints}
\end{minipage}


\begin{enumerate}
\problem{10} Find by inspection (i.e. without using Lagrange multipliers) the maximum
margin hyperplane separating the training examples. Turn in the
resulting line equation, and a plot of the resulting decision boundary. 
What is the margin induced by the hyperplane you've found?

\problem{15}\label{q:svm} Now write down formulation of margin maximization as an
optimization problem, using Lagrange multipliers, and solve it. Turn
in the Matlab command(s) you used, and the values of Lagrange multipliers associated with each of the 6
training points. What are the support vectors?

\begin{advice}
In question \ref{q:svm}, you will need to use Matlab's quadratic
programming routines. In Matlab 5, the most convenient function to use
is \texttt{quadprog}. Note that the Matlab optimization functions are
formulated in terms of \emph{minimization} of the objective function,
while our notation defines a maximization problem; this can be easily
overcome, however, by turning the sign of the objective function. That
is, you
need to minimize
\[
\frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j\bx^T\bx_j) -
\sum_i \alpha_i 
\]
\end{advice}


\problem{5} Find the bias term $w_0$ for the SVM hyperplane given by your
solution 
in question \ref{q:svm}. What is the resulting margin? 

\item[] You are now told that the 6 training points were in fact sampled
from two Gaussian distributions: \\
\begin{tabular}{lcc}
Class 0 & $\mathbf{\mu}_0=[-0.5,0]^T$ &
$\mathbf{\Sigma}_0=\left(\begin{array}{cc}12 & -4\\-4 & 18\end{array}\right)$\\
Class 1 & $\mathbf{\mu}_1=[1.5,0]^T$ &
$\mathbf{\Sigma}_1=\mathbf{\Sigma}_0$\\
\end{tabular}
\problem{5}\label{q:bayes} What is the Bayes optimal decision boundary for this
classification problem? 

If the boundaries you found in questions \ref{q:svm} and
\ref{q:bayes} are identical, do you expect this to happen for any
classification problem and any training set? Justify your answer. If
the decision boundaries are different, explain why, and under what conditions on the training set would you expect them to
be more similar to each other?

\end{enumerate}

\section*{Problem 3: Naive Bayes, feature selection}
{\bf Reference:} Lectures 8,9. 


In this problem we will apply Naive Bayes generative model to the
problem of binary text classification. The documents, as well as
available Matlab code, are available from the course website.

We are concerned with two classes of documents -- more specifically,
email messages posted to online discussion boards, one for users of MS
Windows and another for users of X Windows. We want a
classifier that would label a new message as belonging to one of the groups. In
this problem we will try to build such a classifier based on Naive
Bayes model (as detailed in the lectures).

There are 900 documents from each class; we divided them into training
and text sets of equal size. To save space (and time), we ran the word
detection on the documents, and the data available to you consist of
binary feature vector for each document. Upon loading data from
\texttt{docdata.mat} the Matlab environment will contain variables
\texttt{xtrain,xtest,ytrain,ytest}.

The list of 600 words which were used as feature detectors is found in the file
\texttt{detectors}; you can load it into a Matlab cell array by saying
\begin{verbatim}
>> detectors = textread('detectors','%s');
\end{verbatim}

The following Matlab functions are available from the website:
\begin{verbatim}
theta = NBest(X,Y,p,n);
\end{verbatim}
estimates the parameters of Naive Bayes model from observations in the
rows of \texttt{X}  (\texttt{X(n,:)} is the observed word
detections in the $n$-th document). \texttt{Y(n)} gives the class
label (1 or 2) for the $n$-th document. \texttt{n,p} are the
hyperparameters of the beta prior. You can experiment with different
values, but please use the values \texttt{p=0.01,n=10} in the
experiments reported in your solution. (To remind you, these values correspond to a
``fictitious data set'' of 10 documents with each word appearing with
probability 1/100.) The result is a 2-by-$N$ matrix (where $N$ is the
number of words in our detector set - and is, of course, equal to the
number of columns in \texttt{X}), such that \texttt{theta(y,k)} is th
estimated probability of the word $k$ to appear in a document of
class $y$. You can find out what is the actual word $k$  by looking at \texttt{detectors\{k\}}. 

\begin{verbatim}
y = NBclas(X,theta);
\end{verbatim}
returns in \texttt{Y} the labels of the data represented by the rows of
\texttt{X}, using Naive Bayes model with parameters \texttt{theta}.

\begin{verbatim}
chosen = selGreedy(K,X,Y,cvK);
\end{verbatim}
performs greedy feature selection. It starts with an empty set of
features and adds one feature at a time, when the next features is
chosen which minimizes the cross-validation error if it is added to currently
selected features. The argument \texttt{cvK} specifies the number of
``folds'' in cross-validation - that is, to haw many parts should the
data be divided. Note that \texttt{cvK = 1} means no cross-validation, that is
error is simply computed  on the whole training set. The result
\texttt{chosen} contains the indices of the selected features. 

\begin{verbatim}
er = cv(X,Y,cvK);
\end{verbatim}
returns in \texttt{er} the \texttt{cvK}-fold cross-validation estimate of the Naive
Bayes error based on the data \texttt{(X,Y)}. That is, i.e., the data
points are partitioned into \texttt{cvK} roughly equal parts $S_1,\ldots,S_{cvK}$, and for
each part $S_i$,
Naive Bayes classifier is trained on
$S_1,\ldots,S_{i-1},S_{i+1},\ldots,S_{cvK}$  and tested on $S_i$; the
average of the so obtained  \texttt{cvK} test errors is the
\texttt{cvK}-fold cross-validation estimate of the error.
  
\begin{enumerate}

\item[] To make sure you understand the format of the data, train
Naive Bayes classifier on the data in \texttt{xtrain,ytrain} and test
it on \texttt{xtest,ytest}. You should get training error of
\textbf{0.0778} and test error of \textbf{0.2256}.
Note the large gap between the trainng and the test errors in this case.
Ten-fold cross-validation on the training set should yield \textbf{0.1522}, which is somewhat closer
to the test error. 

\problem{10} Implement in Matlab function \texttt{MI} that computes
mutual information between features and labels for text classification
problem. The function should be called:
\begin{verbatim}
mi = MI(theta);
\end{verbatim} 
where \texttt{theta(1:2,:)} are the estimated parameter vectors for
classes 1 and 2, and the $k$-the element of the result
column vector \texttt{mi} is $I(\phi_k,y)$.
  Assume equal prior probabilities $1/2$
for both classes. Turn in your code, and the list of 10 words found to
have the highest mutual information with the label (based on the
parameters estimated on \texttt{xtrain,ytrain}), along with the
corresponding values
of MI.

\begin{advice}
Unfortunately, Matlab is notorious for its extremely slow loops. In order to make your function fast, you will have to use Matlab's
vectorized notation. For instance, to compute 
\[
b = \sum_{i=1}^nc_i\log_2 a_i,
\]
where \texttt{c} and \texttt{a} are $n$-element vectors (say, row
vectors) in Matlab, you can call 
\begin{verbatim}
b = sum(c.*log2(a));
\end{verbatim}
-- note  the use of element-wise multiplication operation\texttt{.*}
here. Similarly, if you need to compute a vector \texttt{x} such that
\texttt{x(i)=a(i)/c(i)+y(i)} , a fast way of doing this is to call
\begin{verbatim}
x = a./c+y;
\end{verbatim}
Look at the code of \texttt{NBclas} for an additional example.
\end{advice}

\problem{3} In one or two sentences, explain why in our case
$I(\phi_k,y)$ can not exceed 1.

\problem{10}\label{q:MI} One could use Mutual Information criterion to select
$K$ features with the highest value of $I(\phi_k,y)$, as described in
the lecture. Plot the graph
of the 5-fold cross-validation error of Naive
Bayes based on $K$ features so selected as a function of $K$, for $K$ from 1 to 40. 
Suggest a way of choosing the suitable value of $K$ withing this range, find
such value (let us denote it $K^\ast$) and report the
training error, 5-fold cross-validation error and test error of the classifier that uses the $K^\ast$ features with the
highest  $I(\phi_k,y)$.

\problem{10} Select the same number of features (i.e., $K^\ast$ which
you found in  \ref{q:MI}) using greedy feature selection
approach implemented in \texttt{selGreedy} with 5-fold cross-validation. Report the training error,
cross-valifation error and test error of the resulting Naive Bayes classifier. 
Which feature selection method has a higher gap between the \textbf{training} and
\textbf{test} error of the classifier? Explain why this happens.

\begin{advice}
A few Matlab tips:

In order to use only some subset of features, say indexed by
an array \texttt{features}, you can just take the corresponding column
from the data - e.g., use \texttt{xtrain(:,features)}. Also, note that
the estimate of Naive Bayes parameter $\theta_{y,k}$ does not depend
on $\theta_{y,j}$ for any $j\ne k$, so that you can estimate the
$\theta$s once for all 600 features and then simply use a subset of
the parameters corresponding to the features you are looking at,
e.g. if you have \texttt{theta = NBest(xtrain,ytrain)} you can simply
use \texttt{theta(:,features)}. 

You can look at a subset of a cell array by indexing it like a usual
array, e.g. \texttt{detectors(1:10)}. 

\end{advice}



\end{enumerate}
\end{document}






