9

我已经在 Python 中实现了感知器学习算法，如下所示。即使有 500,000 次迭代，它仍然不会收敛。

我有一个带有目标向量 Y 的训练数据矩阵 X 和一个要优化的权重向量 w。

我的更新规则是：

while(exist_mistakes): 
    # dot product to check for mistakes
    output = [np.sign(np.dot(X[i], w)) == Y[i] for i in range(0, len(X))]

    # find index of mistake. (choose randomly in order to avoid repeating same index.) 
    n = random.randint(0, len(X)-1)
    while(output[n]): # if output is true here, choose again
        n = random.randint(0, len(X)-1)

    # once we have found a mistake, update
    w = w + Y[n]*X[n]

这是错的吗？或者为什么它在 500,000 次迭代之后仍然没有收敛？

4

2 回答 2

15

Minsky和 ​​Papert 的感知器（in）在 1969 年著名地证明了感知器学习算法不能保证对于非线性可分的数据集收敛。

如果您确定您的数据集是线性可分的，您可以尝试为每个数据向量添加偏差，如以下问题所述：感知器学习算法不收敛到 0——添加偏差可以帮助建模决策边界不通过原点。

或者，如果您想使用能够保证收敛到指定宽度边距的感知器学习算法的变体，即使对于不能线性分离的数据集，请查看平均感知器 - PDF。平均感知器是投票感知器的近似值，据我所知，这是在 Freund 和 Schapire 的一篇好论文“使用感知器算法的大边距分类”- PDF中介绍的。

使用平均感知器，您可以在训练期间每次展示训练示例后制作参数向量的副本。最终分类器使用所有参数向量的平均值。

于 2013-10-03T03:06:36.547 回答
0

基本问题是随机选择的点不一定是线性可分类的。

然而，算法中还有一个更糟糕的问题：

即使您参考了 Vapnik 的“统计学习理论”等很好的参考资料，也不会遇到 OP 算法中最大的问题。问题也不在于学习率参数。证明学习率参数对算法是否收敛没有实际影响是微不足道的——这是因为学习率参数只是一个标量。

想象一组要分类的四个点。这四个点是长度为 sqrt(2) 的正交向量。“课堂”点是（-1,1）。“课外”点是 (-1,-1)、(1,1) 和 (1,-1)。无论学习率如何，OP 的原始算法永远不会收敛。

原始发布者的算法无法收敛的原因是缺少偏置项（实际上是第 0 维项的系数），它必须增加其他维项。没有偏置项，感知器就没有完全定义。在 1D 或 2D 空间中通过手动建模感知器来证明这一点是微不足道的。

偏见术语在文献中经常被当作“转移”超平面的一种方式，但这似乎主要是因为许多人倾向于在 2D 空间中教授/学习感知器以用于教学目的。术语“移位”不能充分解释为什么在高维空间中需要偏置项（“移位”100 维超平面是什么意思？）

人们可能会注意到，证明感知器平均收敛时间的文献排除了偏差项。这是因为如果您假设感知器会收敛，则可以简化感知器方程（参见 Vapnik，1998，Wiley，p.377）。对于证明来说，这是一个很大的（但必要的）假设，但是通过假设一个不完整的实现是无法充分实现感知器的。

Alex BJ Novikoff 的 1962/1963 年感知器收敛证明包括这个零维项。

于 2021-02-26T17:48:48.340 回答