% -*- Mode: TeX -*-
\documentstyle[12pt]{article}

\input nofill.tex
\input texcom.tex

\parskip=2ex

\begin{document}

\centerline{\bf \huge ??. Concept Learning}

\section{Problems}


\noindent
{\bf Problem 1}  This problem is about setting the weights of neural networks.  Consider
``neural network'' that computes a weighted sum of $n$ inputs plus all the
pairwise products of those inputs.  There are $n + n^2$ weights that can
be adjusted in this network.  The output of the network on inputs $x_1$, $\ldots$ $x_n$
can be written as
$$N(x_1,\;\ldots,\;x_n)  = \sum_{1 \leq i \leq n} a_i x_i + \sum_{1 \leq i \leq n, 1 \leq j \leq n} b_{i,j}x_i x_j$$
Also suppose that we are given $m$ input pairs
$\tuple{\vec{x}_1,\;y_1}$, $\tuple{\vec{x}_2,\;y_2}$, $\ldots$
$\tuple{\vec{x}_m,\;y_m}$ where $\vec{x}_i$ is a vector of $n$ input values
and $y_i$ is a desired output value for input $\vec{x}_i$.  For a given
set of parameters $a_i$ and $b_{i,j}$ we define the network error
for this data as follows.

$$\mbox{error} = \sum_{1 \leq k \leq m} (y_k - N(\vec{x}_k))^2$$

Give a procedure for computing values of $a_i$ and $b_{i,j}$ which minimizes
this error.  Your procedure should calculate the coefficients (without search)
and should take polynomial time in the number of inputs $n$.

{\bf Problem 2} Consider a linear sum of $n$ inputs defined by

$$N(x_1,\;\ldots,\;x_n)  = \sum_{1 \leq i \leq n} a_i x_i$$

We now define another function $M$ of $n$ inputs by computing a polynomial
in $N$.  More specifically we define $M(\vec{x})$ as follows

$$M(\vec{x}) = b_0 + b_1N(\vec{x}) + b_2N^2(\vec{x}) + \ldots + b_kN^k(\vec{x})$$

where $N^j(\vec{x})$ denotes the $j'th$ power of the number $N(\vec{x})$.

{\bf a.} Explain why your solution to problem 1 can not be used to compute the
parameters $a_i$ and $b_j$ that minimize the error of the ``network'' $M$
relative to a given set of desired input output pairs.

{\bf b.}  Assume that you are given the parameters $a_i$ and $b_j$ that define
the function $M$ and a single input output pair $\tuple{\vec{x},\;y}$.
Give a gradient descent procedure for computing a small change in the
network parameters $a_i$ and $b_j$ that reduces the
error on this input output pair.  Explain how your procedure can be used
as an ``on line'' method of training this network to simulate a desired
function.

\bibliographystyle{named}

\bibliography{/home/c2/dam/biblio/master}

\end{document}