Editing Perceptron (section)

===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>