\chapter{Perceptrons}
\section{Threshold Logic Unit}
The basic computing element in a perceptron is a device known in the literature as a {\em threshold logic unit\/} (TLU). An TLU is parametrized by a set of weights and a threshold. Suppose that we are given an TLU with $n$ weights, $w_1,w_2,\ldots,w_n$, and a threshold denoted by $t$. Given an input vector $\b x_i =\left[\begin{array}{cccc}
x_{i,1} & x_{i,2} & \cdots & x_{i,n}
\end{array}\right]^T
\in \mb{\Bb R}^n$, then the corresponding output of the TLU is defined as
\[
y_i=\mb{sign}\left(\sum_{j=1}^n w_jx_j -t \right),
\]
where
\[
\mb{sign}(z)=\left\{\begin{array}{ccc}
-1&\mb{if}& z < 0\\
1&\mb{if}& z\ge0.
\end{array}\right.
\]
We note that, sometimes in the literature, the signum function, denoted here by sign, is undefined at 0, or it is defined as a point to a set mapping, that is, $\mb{sign}(0)\in [-1,1]$. However, in this book, for computational purposes we define $\mb{sign}(0)=1$.

Using scalar product notation, we can represent the expression for $y_i$ as
\[
y_i=\mb{sign}\left( \langle \b w,\b x_i\rangle -t\right).
\]
Note that $y_i \in \{-1,1\}$. Specifically,
\[
y_i=\left\{\begin{array}{ccc}
-1&\mb{if}& \langle \b w,\b x_i\rangle -t<0\\
1&\mb{if}& \langle \b w,\b x_i\rangle -t\ge0
\end{array}\right.
\]

In this section, we study properties of the TLU. In particular, we explore issues involving learning using an TLU. We assume that we are given $m$ training pairs $\left(\b x_1,d_1\right),\left(\b x_2,d_2\right),\ldots,\left(\b x_m,d_m\right)$, where for $i=1,2,\ldots,m$, the input vectors $\b x_i \in \mb{\Bb R}^n$ and $d_i \in \{-1,1\}$ represent the desired responses. We would like to determine a hyperpalne
\[
\langle \b w^*,\b x\rangle -t^*=0,
\]
such that each input vector lies on a pre-assigned side of the hyperplane. If such a hyperplane exists for the given training set, then the set of input vectors is referred to as {\em linearly separable\/}, and the hyperplane is referred to as a {\em separating hyperplane\/}. If no such hyperplane exists, then the traning set is referred to as {\em linearly nonseparable}. Finding a separting hyperplane is equivalent to finding a corresponding weight vector and a threshold. If we find such a weight vector and a treshold, then we say that the TLU correctly classifies the training set. Thus, designing an TLU that correctly classifies the given training set amounts to finding a weight vector $\b w^*$ and a threshold $t^*$ such that for $i=1,2,\ldots,m$, we have
\[
\begin{array}{ccc}
\langle \b w^*,\b x_i\rangle -t^*<0&\mb{if}& d_i=-1\\
\langle \b w^*,\b x_i\rangle -t^*>0&\mb{if}& d_i=1.
\end{array}
\]
If a traning set is linearly separable, then the following training algorithm will determine a separating hyperplane.
\begin{center}
{\bf The Perceptron Learning Algorithm}
\end{center}
Given a set of training pairs $\left\{(\b x_1,d_1),\ldots,(\b x_i,d_i),\ldots,(\b x_m,d_m)  \right\}$.
\begin{enumerate}
\item {\bf Initialize Weight Vector and Threshold}\\
Set the values of the components of the initial weight vector $\b w_0$ and threshold $t$ to zero or to small random values.
\item {\bf Present New Input Vector and Desired Output}\\
Present the new input vector, $\b x_i$ and the corresponding desired output $d_i$. 
\item {\bf Calculate Actual Output}
\[
y_k=\mb{sign}\left( \langle \b w_k,\b x_i \rangle-t\right).
\]
\item {\bf Adapt Weight Vector and Threshold}
\begin{eqnarray*}
\b w_{k+1}&=&\b w_k+\frac{1}{2}(d_i-y_k)\b x_i\\
t_{k+1} &=& t_k-\frac{1}{2}(d_i-y_k).
\end{eqnarray*}
Note that the weight vector and threshold are unchanged if the correct decision is made by the perceptron.
\item {\bf Repeat by Going to Step 2}
\end{enumerate}

Our goal now is to prove that the Perceptron Learning Algorithm can always find a separating hyperplane for a linearly separable input vectors. In our proof we use some technical results that we present next.
\begin{lemma}
\label{lemma:newt}
Let $\b x_1,\b x_2,\ldots,\b x_m$, $\b x_i \in \mb{\Bb R}^n$, be a set on $m$ input vectors, $\b w \in \mb{\Bb R}^n$ be a weight vector of an $n$-input TLU, and $t\in \mb{\Bb R}$ its threshold. Then, there exists a threshold $t^{\prime}$ such that, for $i=1,2,\ldots,m$,
\[
\langle \b w,\b x_i \rangle -t^{\prime} \ne 0,
\]
and
\[
\mb{\rm sign}\left(\langle \b w,\b x_i \rangle -t \right)=\mb{\rm sign}\left( \langle \b w,\b x_i \rangle -t^{\prime} \right).
\] 
\end{lemma}
{\bf Proof}\quad Assume, without loss of generality, that the input vectors are sorted into two sets $\left\{\b x_1,\ldots,\b x_l\right\}$ and $\left\{\b x_{l+1},\ldots,\b x_m\right\}$ such that the desired response of the vectors from the first set is $d_i=-1$, while the desired response of the vectors from the second set is $d_i=1$. Let
\[
\delta=\min\left\{\left| \langle \b w,\b x_i \rangle -t\right|:1\le i \le l  \right\}.
\]
Note that $\delta>0$. Let $t^{\prime}=t-\delta/2$. Then,
\begin{eqnarray*}
\langle \b w,\b x_i \rangle -t^{\prime} &=&\langle \b w,\b x_i \rangle -t + \delta/2\\
&\ne& 0 \quad \mb{for}\quad i=1,\ldots,m,
\end{eqnarray*}
and the output of the TLU with the modified threshold, $t^{\prime}$, is the same as the output of the TLU with the old threshold, $t$.\\
\hspace*{5.5in}$\Box$

By the above lemma, we can always assume that $\langle \b w,\b x_i \rangle -t^{\prime}\ne 0$, for $i=1,\ldots,m$ and that the output of an TLU can be defined as
\[
y_i=\left\{\begin{array}{ccc}
-1&\mb{if}& \langle \b w,\b x_i\rangle -t<0\\
1&\mb{if}& \langle \b w,\b x_i\rangle -t>0
\end{array}\right.
\] 
Furthermore, we can assume the threshold value, $t$ to be equal zero. We can achieve this by increasing the dimension of every input vector, $\b x_i$, by augmenting it with an entry equal to $-1$, and by increasing the dimension of the weight vector to $n+1$ by augmenting it with $t$. Indeed,
\begin{eqnarray*}
y_i&=&\mb{sign}\left( \langle \b w,\b x_i\rangle -t\right)\\
&=& \mb{sign}\left( \left\langle \tilde{\b w},\tilde{\b x}_i\right\rangle\right),
\end{eqnarray*}
where $\tilde{\b w}^{T}=\left[\begin{array}{ccccc}
w_1&w_2&\cdots&w_n&t
\end{array}\right]$ and $\tilde{\b x}_i^{T}=\left[\begin{array}{ccccc}
x_{1,1}&x_{1,2}&\cdots&x_{1,n}&-1
\end{array}\right]$. In our further discussion, we assume that the given input vectors have been already augmented. In view of the above, we can equivalently express the problem of training an TLU as follows:\\
{\bf TLU Learning Problem}: Given $m$ training pairs $\left(\b x_1,d_1\right),\ldots,\left(\b x_m,d_m\right)$, where $\b x_i \in \mb{\Bb R}^{n+1}$ and $d_i \in \{-1,1\}$. Determine a weight vector $\b w \in \mb{\Bb R}^{n+1}$, if there exixts one, such that for $i=1,\ldots,m$,
\[
\mb{sign}\left( \left\langle \b w,\b x_i\right\rangle\right)=d_i.
\] 
We further simplify the formulation of the TLU Learning Problem by preprocessing training pairs. Specifically, we replace every training pair, $\left(\b x_i,d_i\right)$ with $d_i=-1$ with their negative, $\left(-\b x_i,-d_i\right)$. After performing the above preprocessing, the TLU Learning Problem can be reformulated in a simple form that we use while proving the Perceptron Learning Algorithm.\\ 
{\bf Simplified TLU Learning Problem}: Given a set of input vectors $\left\{ \b x_1,\ldots,\b x_m \right\}$. Determine a weight vector $\b w$ such that for $i=1,\ldots,m$,
\[
\left\langle \b w,\b x_i\right\rangle>0.
\]
Then, the Perceptron Learning Algorithm can be equivalently stated as follows:
\begin{center}
{\bf Simplified Perceptron Learning Algorithm}
\end{center}
\begin{enumerate}
\item {\bf Initialize Weight Vector}\\
Set the values of the components of the initial weight vector $\b w_0$ to zero.
\item {\bf Test}\\
If $\left\langle \b w,\b x_i\right\rangle\le 0$, go to {\bf Add}, else {\bf Test} next input vector.
\item {\bf Add}
\[
\b w_{k+1}=\b w_k+\b x_i,\quad k=k+1.
\]
Go to {\bf Test}.
\end{enumerate}
The algorithm is said to {\em converge\/} if for some $k<\infty$,
\[
\left\langle \b w,\b x_i \right\rangle >0,\quad \mb{for}\quad i=1,\ldots,m.
\]
The following theorem states that if the set of input vectors is linearly separable, then the Perceptron Learning Algorithm converges.
\begin{thm}[The Perceptron Convergence Theorem]
If the set of vectors\\$\left\{ \b x_1,\b x_2,\ldots\b x_m\right\}$ is linearly separable, then the perceptron learning algorithm determines a weight vector $\b w$ in a finite number of steps, such that $\langle \b w,\b x_i\rangle>0$ for $i=1,2,\ldots,m$
\end{thm}
{\bf Proof}\quad The proof is adapted from Siu, Roychowdhury, and Kailath~\cite{siu95}. We begin by observing that since the set of input vectors is linearly separable, there exists a weight vector $\b w^*$, with $\left\Arrowvert \b w^*\right\Arrowvert=1$, and a constant $\delta>0$ such that for $i=1,2,\ldots,m$ we have
\[
\langle \b w^*,\b x_i \rangle >\delta.
\]
We assume that $\left\Arrowvert \b x_i\right\Arrowvert\le L$, for $i=1,2,\ldots,m$, that is, the lenghts of all the input vectors are bounded above by $L$. Let $k$ denote the number of times the weight vector $\b w$, in the perceptron learning algorithm, has been updated, and let $\b w_k$ be the value of the weight vector, $\b w$, after the $k$-th update. Our goal is to show that $k$ is bounded above.

To proceed, we note that if an input vector $\b x_i$ is used for the $k$-th update in the algorithm, then
\[
\b w_k=\b w_{k-1}+\b x_i,
\]
where $\langle \b w_{k-1},\b x_i \rangle =\b w^{T}_{k-1} \b x_i \le 0$. We first derive an upper bound on $\|\b w_k\|$. We have
\begin{eqnarray*}
\|\b w_k\|^2 &=& \|\b w_{k-1} + \b x_i \|^2\\
&=& \left( \b w_{k-1} + \b x_i \right)^{T}\left( \b w_{k-1} + \b x_i \right)\\
&=& \b w^{T}_{k-1}\b w_{k-1}+\b x^{T}_i \b x_i+ 2\b w^{T}_{k-1} \b x_i\\
&\le& \|\b w_{k-1}\|^2 +L^2,
\end{eqnarray*}
because $\b w^{T}_{k-1}\b x_i \le 0$ and $\|\b x_i\|^2 \le L^2$. Suppose now that for the $(k-1)$-st update the input vector $\b x_j$ was used, that is,
\[
\b w_{k-1}=\b w_{k-2}+\b x_j.
\]
Hence,
\begin{eqnarray*}
\|\b w_k\|^2 &\le& \|\b w_{k-1}\|^2 +L^2\\
&=& \|\b w_{k-2}+\b x_j\|^2+L^2\\
&\le& \|\b w_{k-2}\|^2 + 2L^2.
\end{eqnarray*}
Continuing in this manner we get
\[
\|\b w_k\|^2 \le k L^2,
\]
because we assumed that $\b w_0=\b 0$.

We next derive a lower bound on $\|\b w_k\|$. We have
\begin{eqnarray*}
\left\langle \b w^*,\b w_k \right\rangle &=& \left\langle \b w^*,\b w_{k-1} \right\rangle+ \left\langle \b w^*,\b x_i \right\rangle\\
&\ge& \left\langle \b w^*,\b w_{k-1} \right\rangle + \delta,
\end{eqnarray*}
because we assumed that $\langle \b w^*,\b x_i \rangle >\delta$. Observing that $\b w_{k-1}=\b w_{k-2}+\b x_j$, we get
\begin{eqnarray*}
\left\langle \b w^*,\b w_k \right\rangle &\ge&\left\langle \b w^*,\b w_{k-1} \right\rangle + \delta\\
&\ge& \left\langle \b w^*,\b w_{k-2} \right\rangle + 2\delta. 
\end{eqnarray*}
Continuing in this manner we obtain
\[
\left\langle \b w^*,\b w_k \right\rangle \ge k\delta.
\]
Applying the Cauchy-Schwarz inequality yields
\[
\|\b w^*\|\|\b w_k\| \ge \left\langle \b w^*,\b w_k \right\rangle \ge k\delta.
\]
By assumption $\|\b w^*\|=1$. Hence,
\[
\|\b w_k \| \ge k \delta.
\]
Combining the obtained upper and lower bounds on $\|\b w_k\|$ we obtain
\[
k^2\delta^2 \le \|\b w_k\|^2 \le k L^2.
\]
Therefore,
\[
k \le \frac{L^2}{\delta^2},
\]
which implies that the perceptron learning algorithm reaches a solution in no more than $k$ steps. The proof of the Perceptron Convergence Theorem is complete.\\
\hspace*{5.5in} $\Box$

We now present a sufficient condition for linear nonseparability.
\begin{thm}
\label{thm:nonseparability}
If there exists a positive linear combination (PLC) that equals $\b 0$ of the given set of input vectors, then the given set of input vectors is linearly nonseparable.
\end{thm}
{\bf Proof}\quad We prove the theorem by contradiction. Assume that there exists a PLC equal $\b 0$ of the given input vectors. Then, there exist nonnegative constants, $q_i$, such that for some $j$, $1\le j\le m$, we have $q_j>0$, and
\[
\sum_{i=1}^m q_i\b x_i =\b 0.
\]
Suppose now that the given input vectors are linearly separable, that is, there is a weight vector, $\b w$, such that $\left\langle \b w,\b x_i\right\rangle >0$ for $i=1,\ldots,m$. We premultiply $\sum_{i=1}^m q_i\b x_i=\b 0$ by $\b w^{T}$ to get
\begin{eqnarray*}
\b w^{T}\sum_{i=1}^m q_i\b x_i &=& \sum_{i=1}^m q_i\langle\b w,\b x_i \rangle\\
&>& 0
\end{eqnarray*}
since $\left\langle \b w,\b x_i\right\rangle >0$ and $q_j>0$. However, we arrived at a contradiction because $\sum_{i=1}^m q_i\b x_j =\b 0$ which completes the proof.\\
\hspace*{5.5in} $\Box$

\begin{example}\rm
Suppose we are given the following traning set:
\begin{eqnarray*}
\b x_1&=&\left[\begin{array}{c}
-1\\
-1
\end{array}\right],\; d_1=-1;\quad \b x_2=\left[\begin{array}{c}
1\\
1
\end{array}\right],\; d_2=-1;\\
\b x_3&=&\left[\begin{array}{c}
-1\\
1
\end{array}\right],\; d_3=1;\quad \b x_4=\left[\begin{array}{c}
1\\
-1
\end{array}\right],\; d_4=1.
\end{eqnarray*}
The above training set represents the 2-input Exclusive-OR (XOR) function. Let us now preprocess the traning set, so we can apply Theorem~\ref{thm:nonseparability}. The result of the preprocessing are the following input vectors:
\[
\b x_1=\left[\begin{array}{c}
1\\
1\\
1
\end{array}\right],\quad \b x_2=\left[\begin{array}{c}
-1\\
-1\\
1
\end{array}\right],\quad \b x_3=\left[\begin{array}{c}
-1\\
1\\
-1
\end{array}\right],\quad \b x_4=\left[\begin{array}{c}
1\\
-1\\
-1
\end{array}\right].
\]
Note that $\sum_{i=1}^4\b x_i=\b 0$. It follows from Theorem~\ref{thm:nonseparability} that the given input vectors are not linearly separable.
\end{example}

\section{Exercises}
\begin{exercise}\rm
Show
\end{exercise}