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

Question

我已经在Python中实现了Perceptron学习算法,如下所示.即使有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

感知由斯基和帕佩特(上)在1969年著名表明感知学习算法并不保证收敛为不是线性可分数据集.

如果您确定数据集是线性可分的,则可以尝试为每个数据向量添加偏差,如问题所述:感知器学习算法未收敛到0 - 添加偏差可以帮助建模决策边界没有通过原点.

或者,如果您想使用感知器学习算法的变体保证收敛到指定宽度的边距,即使对于不可线性分离的数据集,也可以查看Averaged Perceptron - PDF.平均感知器是投票感知器的近似值,据Freund和Schapire在"使用感知器算法进行大幅度保证金分类" - PDF的一篇好文章中介绍(据我所知).

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