python - 为什么感知器学习算法不收敛？

Question

我已经在 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 次迭代后仍不收敛？

Answer 1

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

如果您确定您的数据集是线性可分的，您可以尝试为每个数据向量添加偏差，如问题所述:Perceptron learning algorithm not converging to 0 -- 添加偏差有助于对不通过原点的决策边界进行建模。

或者，如果您想使用保证收敛到指定宽度边距的感知器学习算法的变体，即使对于不可线性分离的数据集，请查看 Averaged Perceptron -- PDF .平均感知器是投票感知器的近似值，它在 Freund 和 Schapire 的一篇不错的论文中介绍(据我所知)，"Large Margin Classification Using the Perceptron Algorithm" -- PDF .

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