\input{/home/sc/yip/cs201-macro.tex}
\input{psfig}

\setlength{\textwidth}{6.25 in}
%\setlength{\textheight}{9.0 in}
\setlength{\topmargin}{-.6 in}

\def\problem#1{%
 \addtocounter{subsection}{1}%
 \setcounter{subsubsection}{0}%	
 \subsection*{Problem \arabic{subsection}. #1}%
}
\begin{document} 
\pagestyle{empty}

\psetheader{Fall Semester, 1996}{Practice Problems -- Nov 5, 1996}

\problem{Bayes' Decision Rule and Nearest Neighbor}

Recall that to minimize the probability of misclassifying a new
pattern $x$, Bayes' decision rule takes the form of maximum posterior
probability, i.e., $x$ belongs to class $C_i$ if and only if
\[ p( C_i \mid x) > p( C_j \mid x) \;\; \mbox{for all $i \neq j$} \]

Assume the likelihood function is given by the 1-dimensional Gaussian:
\[ p (x \mid C_i) = \frac{1}{\sqrt{2 \pi} \sigma} e^{-\frac{(x -
\mu_i)^2}{2 \sigma^2}} \]
for each $i$, and all the prior probabilities are equal.

Show that the decision rule is equivalent to: $x$ belongs to 
class $C_i$ if and only if
\[ (x - \mu_i)^2 <  (x - \mu_j)^2 \;\; \mbox{for all $i \neq j$} \]

Answer: \\ \onebox{6in}{2in}

\clearpage

\problem{Bayes' Decision Rule and Logistic Function}

Consider a 2-class classification problem where the likelihood
functions are the 1-dimensional Gaussian with means $\mu_1$ and
$\mu_2$, and equal variance $\sigma^2$.  Using the Bayes theorem, show
that the posterior probability of membership of class $C_1$ is given by:
\[ p (C_1 \mid x) = \frac{1}{1 + e^{-a}} \]
where $a = w^T.x + w_0$ for some weight vector $w$ and constant $w_0$.

Answer: \\ \onebox{6in}{2in}

\clearpage

\problem{Delta Rule}

Consider a linear 1-layer network with two input units and one output
unit.  The training set consists of two 2-element input vectors and their
respective outputs:
\[ (2,1) \rightarrow 1, (0.5,1) \rightarrow 1 \]
Suppose you are to train the network with the delta rule:
\[ \Delta w = \rho (y^* - y) x \]
where $y^*$ is the target output, $y$ is the output of the network,
and $x$ is the input vector.

(a) Using a learning rate $\rho = 0.1$ and an initial weight vector $w =
(0,0)$, write down the weight vector after {\it one} iteration over
the data set.

Answer: \onebox{1in}{.2in}

(b) In the graph below, estimate geometrically the weight vector that
correctly maps the two input vectors in the data set.

\bigskip 

\centerline{\psfig{figure=lms.ps,height=3in,width=3in}}

\clearpage
\problem{Bound on learning rate}

The delta rule for minimizing the mean square error between the output
of a single layer network and the target output is called the {\it
Widrow-Hoff} algorithm.  Show that a necessary condition for
convergence of the Widrow-Hoff algorithm is: \[ 0 < \rho < \frac{2}{\|
x \|^2} \]

Hint: Show that $\mid y^* - y^{\mbox{new}} \mid \;\; < \;\; \mid y^* - y^{\mbox{old}} \mid$

Answer: \\ \onebox{6in}{2in}
\end{document}