421
个编辑
更改
跳到导航
跳到搜索
第179行：
第179行： − +
→收敛性
假设分属于两个类的输入向量可以被一个线性超平面分割成两个类，且样本到超平面的间距为 <math>\gamma </math>。即存在一个权重向量 <math>\mathbf{w}</math> 且 <math>||\mathbf{w}||=1</math>，以及一个偏置项 <math>b</math> 使得对于所有的 <math>d_j=1</math> 对应 j 有 <math>\mathbf{w}\cdot\mathbf{x}_j > \gamma </math> 和 <math> d_j=0</math>对应的 j 有 <math>\mathbf{w}\cdot\mathbf{x}_j < -\gamma </math> 。且如果引入 <math>R</math> 表示输入向量最大的维度。Novikoff (1962)证明了感知机可以在 <math>O(R^2 \gamma^2)</math>轮迭代中完成收敛。证证明的思路是权重向量可以被有负[[点积]]的约束值在一个方向上修正，因此可以被 <math>Osqrt{t}</math> 的下界约束，这里的 <math>t</math> 是权重向量更新的次数。然而，它也可以被 <math> O(t)</math> 的上界约束。因为如果存在一个未知的满足条件的权重向量，那么在这个方向上每一次权重向量的改变都只取决于输入向量。
假设分属于两个类的输入向量可以被一个线性超平面分割成两个类，且样本到超平面的间距为 <math>\gamma </math>。即存在一个权重向量 <math>\mathbf{w}</math> 且 <math>||\mathbf{w}||=1</math>，以及一个偏置项 <math>b</math> 使得对于所有的 <math>d_j=1</math> 对应 j 有 <math>\mathbf{w}\cdot\mathbf{x}_j > \gamma </math> 和 <math> d_j=0</math>对应的 j 有 <math>\mathbf{w}\cdot\mathbf{x}_j < -\gamma </math> 。且如果引入 <math>R</math> 表示输入向量最大的维度。Novikoff (1962)证明了感知机可以在 <math>O(R^2 \gamma^2)</math>轮迭代中完成收敛。证证明的思路是权重向量可以被有负[[点积]]的约束值在一个方向上修正，因此可以被 <math>Osqrt{t}</math> 的下界约束，这里的 <math>t</math> 是权重向量更新的次数。然而，它也可以被 <math> O(t)</math> 的上界约束。因为如果存在一个未知的满足条件的权重向量，那么在这个方向上每一次权重向量的改变都只取决于输入向量。
当感知机算法在训练集线性可分的条件下会在某个解中达到收敛，而且会在多个质量不同且满足条件的解中任意选一个。<ref>Bishop, Christopher M. "Chapter 4. Linear Models for Classification". Pattern Recognition and Machine Learning. Springer Science+Business Media, LLC. p. 194. ISBN [https://en.wikipedia.org/wiki/Special:BookSources/978-0387-31073-2 978-0387-31073-2].</ref>''最佳稳定性感知机''现在一般称为[[SVM支持向量机]]，就是设计用来解决这个问题的。<ref name="KrauthMezard87">W. Krauth and M. Mezard. Learning algorithms with optimal stability in neural networks. J. of Physics A: Math. Gen. 20: L745-L752 (1987)</ref>
当感知机算法在训练集线性可分的条件下会在某个解中达到收敛，而且会在多个质量不同且满足条件的解中任意选一个。<ref>Bishop, Christopher M. "Chapter 4. Linear Models for Classification". Pattern Recognition and Machine Learning. Springer Science+Business Media, LLC. p. 194. ISBN [https://en.wikipedia.org/wiki/Special:BookSources/978-0387-31073-2 978-0387-31073-2].</ref>'''最佳稳定性感知机'''现在一般称为[[SVM支持向量机]]，就是设计用来解决这个问题的。<ref name="KrauthMezard87">W. Krauth and M. Mezard. Learning algorithms with optimal stability in neural networks. J. of Physics A: Math. Gen. 20: L745-L752 (1987)</ref>
[[File:Perceptron cant choose.svg.png|thumb|300px|两种种类的点和无限多的可以分割它们的线性边界。即使这两条线性边界是直角相对的，感知机算法也无法从其中选择。]]
[[File:Perceptron cant choose.svg.png|thumb|300px|两种种类的点和无限多的可以分割它们的线性边界。即使这两条线性边界是直角相对的，感知机算法也无法从其中选择。]]