Editing Perceptron (section)

== Learning algorithm for a single-layer perceptron ==
[[File:Perceptron_example.svg|right|thumb|310x310px|A diagram showing a perceptron updating its linear boundary as more training examples are added]]
Below is an example of a learning algorithm for a single-layer perceptron with a single output unit. For a single-layer perceptron with multiple output units, since the weights of one output unit are completely separate from all the others', the same algorithm can be run for each output unit.

For [[multilayer perceptron]]s, where a hidden layer exists, more sophisticated algorithms such as [[backpropagation]] must be used. If the activation function or the underlying process being modeled by the perceptron is [[Nonlinear system|nonlinear]], alternative learning algorithms such as the [[delta rule]] can be used as long as the activation function is [[Differentiable function|differentiable]]. Nonetheless, the learning algorithm described in the steps below will often work, even for multilayer perceptrons with nonlinear activation functions.

When multiple perceptrons are combined in an artificial neural network, each output neuron operates independently of all the others; thus, learning each output can be considered in isolation.

=== Definitions ===

We first define some variables:
*<math>r</math> is the [[learning rate]] of the perceptron. Learning rate is a positive number usually chosen to be less than 1. The larger the value, the greater the chance for volatility in the weight changes.
*<math>y = f(\mathbf{z}) </math> denotes the ''output'' from the perceptron for an input vector <math>\mathbf{z}</math>.
*<math>D = \{(\mathbf{x}_1,d_1),\dots,(\mathbf{x}_s,d_s)\} </math> is the ''training set'' of <math>s</math> samples, where:
** <math>\mathbf{x}_j</math> is the <math>n</math>-dimensional input vector.
** <math>d_j </math> is the desired output value of the perceptron for that input.
We show the values of the features as follows:
*<math>x_{j,i} </math> is the value of the <math>i</math>th feature of the <math>j</math>th training ''input vector''.
*<math>x_{j,0} = 1 </math>.
To represent the weights: 
*<math>w_i </math> is the <math>i</math>th value in the ''weight vector'', to be multiplied by the value of the <math>i</math>th input feature.
*Because <math>x_{j,0} = 1 </math>, the <math>w_0 </math> is effectively a bias that we use instead of the bias constant <math>b</math>.
To show the time-dependence of <math>\mathbf{w}</math>, we use:
*<math>w_i(t) </math> is the weight <math>i</math> at time <math>t</math>.

=== Steps===
{{Ordered list 
| Initialize the weights. Weights may be initialized to 0 or to a small random value. In the example below, we use 0.
| For each example {{mvar|j}} in our training set {{mvar|D}}, perform the following steps over the input <math>\mathbf{x}_j </math> and desired output <math>d_j </math>:
{{Ordered list |list_style_type=lower-alpha
|Calculate the actual output:
:<math>\begin{align}
y_j(t) &= f[\mathbf{w}(t)\cdot\mathbf{x}_j] \\
&= f[w_0(t)x_{j,0} + w_1(t)x_{j,1} + w_2(t)x_{j,2} + \dotsb + w_n(t)x_{j,n}]
\end{align}</math>
|Update the weights:
:<math>w_i(t+1) = w_i(t) \; \boldsymbol{+} \; r\cdot(d_j - y_j(t)) x_{j,i} </math>, for all features <math>0 \leq i \leq n</math>, <math>r</math> is the [[learning rate]].
}}
| For [[offline learning]], the second step may be repeated until the iteration error <math>\frac{1}{s} \sum_{j=1}^s |d_j - y_j(t)| </math> is less than a user-specified error threshold <math>\gamma </math>, or a predetermined number of iterations have been completed, where ''s'' is again the size of the sample set. 
}}
The algorithm updates the weights after every training sample in step 2b.

===Convergence of one perceptron on a linearly separable dataset===
[[File:Perceptron convergence theorem.svg|thumb|284x284px|Illustration of the perceptron convergence. In the picture, <math>\gamma = 0.01, R = 1, r = 1 </math>. All data points have <math>y = +1</math>, since the negative samples are equivalent to <math>y = +1</math> after reflection through the origin. As the learning proceeds, the weight vector performs a somewhat random walk in the space of weights. Each step is at least 90 degrees away from its current direction, thus increasing its norm-square by at most <math>R</math>. Each step adds to <math>w</math> by a point in the samples, and since all the samples have <math>x_1 \geq 0.01</math>, the weight vector must move along <math>x_1</math> by at least <math>0.01</math>. Since the norm grows like <math>\sqrt t</math> but the <math>x_1</math>-component grows like <math>t</math>, this would eventually force the weight vector to point almost entirely in the <math>x_1</math> direction, and thus achieve convergence.]]
A single perceptron is a [[linear classifier]]. It can only reach a stable state if all input vectors are classified correctly. In case the training set {{mvar|D}} is ''not'' [[linearly separable]], i.e. if the positive examples cannot be separated from the negative examples by a hyperplane, then the algorithm would not converge since there is no solution. Hence, if linear separability of the training set is not known a priori, one of the training variants below should be used. Detailed analysis and extensions to the convergence theorem are in Chapter 11 of ''Perceptrons'' (1969).

Linear separability is testable in time <math>\min(O(n^{d/2}), O(d^{2n}), O(n^{d-1} \ln n)) </math>, where <math>n</math> is the number of data points, and <math>d</math> is the dimension of each point.<ref>{{Cite web |title=Introduction to Machine Learning, Chapter 3: Perceptron |url=https://openlearninglibrary.mit.edu/courses/course-v1:MITx+6.036+1T2019/courseware/Week2/perceptron/?activate_block_id=block-v1:MITx+6.036+1T2019+type@sequential+block@perceptron |access-date=2023-10-27 |website=openlearninglibrary.mit.edu |language=en}}</ref>

If the training set ''is'' linearly separable, then the perceptron is guaranteed to converge after making finitely many mistakes.<ref>{{Cite journal|last=Novikoff|first=Albert J.|date=1963|title=On convergence proofs for perceptrons|journal=Office of Naval Research}}</ref> The theorem is proved by Rosenblatt et al.

{{Math theorem|name=Perceptron convergence theorem|note=|math_statement=

Given a dataset <math display="inline">D</math>, such that <math display="inline">\max_{(x,y) \in D}\|x\|_2 = R</math>, and it is linearly separable by some unit vector <math display="inline">w^*</math>, with margin <math display="inline">\gamma</math>: <math display="block">\gamma := \min_{(x,y) \in D} y(w^*\cdot x )</math>

Then the perceptron 0-1 learning algorithm converges after making at most <math display="inline">(R/\gamma)^2</math> mistakes, for any learning rate, and any method of sampling from the dataset.
}}The following simple proof is due to Novikoff (1962). The idea of the proof is that the weight vector is always adjusted by a bounded amount in a direction with which it has a negative [[dot product]], and thus can be bounded above by {{math|''O''({{sqrt|''t''}})}}, where {{mvar|t}} is the number of changes to the weight vector. However, it can also be bounded below by {{math|''O''(''t'')}} because if there exists an (unknown) satisfactory weight vector, then every change makes progress in this (unknown) direction by a positive amount that depends only on the input vector.{{Math proof|title=Proof|proof=

Suppose at step <math display="inline">t</math>, the perceptron with weight <math display="inline">w_t</math> makes a mistake on data point <math display="inline">(x, y)</math>, then it updates to <math display="inline">w_{t+1} = w_t + r(y-f_{w_t}(x) ) x</math>.

If <math display="inline">y = 0</math>, the argument is symmetric, so we omit it.

[[WLOG]], <math display="inline">y = 1</math>, then <math display="inline">f_{w_t}(x) = 0</math>, <math display="inline">f_{w^*}(x) = 1</math>, and <math display="inline">w_{t+1} = w_t + rx</math>.

By assumption, we have separation with margins: <math display="block">w^* \cdot x \geq \gamma</math> Thus,<br />
<math display="block">w^* \cdot w_{t+1} - w^* \cdot w_{t} = w^* \cdot (rx) \geq r\gamma</math>

Also <math display="block">\|w_{t+1}\|_2^2 - \|w_{t}\|_2^2 = \|w_{t} + rx\|_2^2 - \|w_{t}\|_2^2 = 2r (w_t \cdot x) + r^2 \|x\|_2^2</math> and since the perceptron made a mistake, <math display="inline">w_t \cdot x \leq 0</math>, and so<br />
<math display="block">\|w_{t+1}\|_2^2 - \|w_{t}\|_2^2 \leq \|x\|_2^2 \leq r^2R^2</math>

Since we started with <math display="inline">w_0 = 0</math>, after making <math display="inline">N</math> mistakes, <math display="block">\|w\|_2 \leq \sqrt{Nr^2R^2}</math> but also<br />
<math display="block">\|w\|_2 \geq w \cdot w^* \geq Nr\gamma</math>

Combining the two, we have <math display="inline">N \leq (R/\gamma)^2</math>
}}

[[File:Perceptron cant choose.svg|thumb|300px|Two classes of points, and two of the infinitely many linear boundaries that separate them. Even though the boundaries are at nearly right angles to one another, the perceptron algorithm has no way of choosing between them.]]
While the perceptron algorithm is guaranteed to converge on ''some'' solution in the case of a linearly separable training set, it may still pick ''any'' solution and problems may admit many solutions of varying quality.<ref>{{cite book |last=Bishop |first=Christopher M |title=Pattern Recognition and Machine Learning |publisher=Springer Science+Business Media, LLC |isbn=978-0387-31073-2 |chapter=Chapter 4. Linear Models for Classification |pages=194|date=2006-08-17 }}</ref> The ''perceptron of optimal stability'', nowadays better known as the linear [[support-vector machine]], was designed to solve this problem (Krauth and [[Marc Mézard|Mezard]], 1987).<ref name="KrauthMezard87">{{cite journal |first1=W. |last1=Krauth |first2=M. |last2=Mezard |title=Learning algorithms with optimal stability in neural networks |journal=Journal of Physics A: Mathematical and General |volume=20 |issue= 11|pages=L745–L752 |year=1987 |doi=10.1088/0305-4470/20/11/013 |bibcode=1987JPhA...20L.745K }}</ref>

=== Perceptron cycling theorem ===
When the dataset is not linearly separable, then there is no way for a single perceptron to converge. However, we still have<ref>{{Cite journal |last1=Block |first1=H. D. |last2=Levin |first2=S. A. |date=1970 |title=On the boundedness of an iterative procedure for solving a system of linear inequalities |url=https://www.ams.org/proc/1970-026-02/S0002-9939-1970-0265383-5/ |journal=Proceedings of the American Mathematical Society |language=en |volume=26 |issue=2 |pages=229–235 |doi=10.1090/S0002-9939-1970-0265383-5 |issn=0002-9939|doi-access=free }}</ref>
{{Math theorem
| name = Perceptron cycling theorem
| note = 
| math_statement = If the dataset <math>D</math> has only finitely many points, then there exists an upper bound number <math>M</math>, such that for any starting weight vector <math>w_0</math> all weight vector <math>w_t</math> has norm bounded by <math>\|w_t\| \leq \|w_0\|+M</math>
}}This is proved first by [[Bradley Efron]].<ref>Efron, Bradley. "The perceptron correction procedure in nonseparable situations." ''Rome Air Dev. Center Tech. Doc. Rept'' (1964).</ref>

=== Learning a Boolean function ===
Consider a dataset where the <math>x</math> are from <math>\{-1, +1\}^n</math>, that is, the vertices of an n-dimensional hypercube centered at origin, and <math>y = \theta(x_i)</math>. That is, all data points with positive <math>x_i</math> have <math>y=1</math>, and vice versa. By the perceptron convergence theorem, a perceptron would converge after making at most <math>n</math> mistakes.

If we were to write a logical program to perform the same task, each positive example shows that one of the coordinates is the right one, and each negative example shows that its ''complement'' is a positive example. By collecting all the known positive examples, we eventually eliminate all but one coordinate, at which point the dataset is learned.<ref name=":3">{{Cite book |last1=Simon |first1=Herbert A. |title=The Sciences of the Artificial, reissue of the third edition with a new introduction by John Laird |last2=Laird |first2=John E. |date=2019-08-13 |publisher=The MIT Press |isbn=978-0-262-53753-7 |edition=Reissue |location=Cambridge, Massachusetts London, England |language=English |chapter=Limits on Speed of Concept Attainment}}</ref>

This bound is asymptotically tight in terms of the worst-case. In the worst-case, the first presented example is entirely new, and gives <math>n</math> bits of information, but each subsequent example would differ minimally from previous examples, and gives 1 bit each. After <math>n+1</math> examples, there are <math>2n</math> bits of information, which is sufficient for the perceptron (with <math>2n</math> bits of information).<ref name=":2" />

However, it is not tight in terms of expectation if the examples are presented uniformly at random, since the first would give <math>n</math> bits, the second <math>n/2</math> bits, and so on, taking <math>O(\ln n)</math> examples in total.<ref name=":3" />