python - 为什么单层感知器在没有归一化的情况下收敛如此之慢，即使边距很大？

Question

这个问题是在我用别人写的一段代码(可以找到 here )确认我的结果(Python Notebook 可以找到 here )后完全重写的。这是我检测的代码，用于处理我的数据并计算迭代数直到收敛:

import numpy as np
from matplotlib import pyplot as plt

class Perceptron(object):
    """Implements a perceptron network"""
    def __init__(self, input_size, lr=0.1, epochs=1000000):
        self.W = np.zeros(input_size+1)
        #self.W = np.random.randn(input_size+1)
        # add one for bias
        self.epochs = epochs
        self.lr = lr

    def predict(self, x):
        z = self.W.T.dot(x)
        return [1 if self.W.T.dot(x) >=0 else 0]

    def fit(self, X, d):
        errors = []
        for epoch in range(self.epochs):
            if (epoch + 1) % 10000 == 0: print('Epoch',epoch + 1)
            total_error = 0
            for i in range(d.shape[0]):
                x = np.insert(X[i], 0, 1)
                y = self.predict(x)
                e = d[i] - y
                total_error += np.abs(e)
                self.W = self.W + self.lr * e * x
                #print('W: ', self.W)
            errors += [total_error]
            if (total_error == 0):
                print('Done after', epoch, 'epochs')
                nPlot = 100
                plt.plot(list(range(len(errors)-nPlot, len(errors))), errors[-nPlot:])
                plt.show()
                break

if __name__ == '__main__':
    trainingSet = np.array([[279.25746446, 162.44072328,   1.        ],
                            [306.23240054, 128.3794866 ,   1.        ],
                            [216.67811217, 148.58167262,   1.        ],
                            [223.64431813, 197.75745016,   1.        ],
                            [486.68209275,  96.09115377,   1.        ],
                            [400.71323154, 125.18183395,   1.        ],
                            [288.87299305, 204.52217766,   1.        ],
                            [245.1492875 ,  55.75847006,  -1.        ],
                            [ 14.95991122, 185.92681911,   1.        ],
                            [393.92908798, 193.40527965,   1.        ],
                            [494.15988362, 179.23456285,   1.        ],
                            [235.59039363, 175.50868526,   1.        ],
                            [423.72071607,   9.50166894,  -1.        ],
                            [ 76.52735621, 208.33663341,   1.        ],
                            [495.1492875 ,  -7.73818431,  -1.        ]])
    X = trainingSet[:, :2]
    d = trainingSet[:, -1]
    d = np.where(d == -1, 1, 0)
    perceptron = Perceptron(input_size=2)
    perceptron.fit(X, d)
    print(perceptron.W)

训练集由 15 个点组成，具有较大的分离余量。 Perceptron 算法找到一个分隔符，如下所示，但在多达 122,346 个 epochs 之后:



正如 the Wikipedia article 解释的那样，感知器收敛所需的 epoch 数与向量大小的平方成正比，与边距的平方成反比。在我的数据中，向量的大小很大，但边距也很大。

我试图理解为什么需要这么多纪元。

更新: 根据评论中的要求，我更新了代码以绘制过去 100 个时期的总错误。这是情节:



P.S.:将要分布的特征缩放为 N(0,1) 后，算法在两个 epoch 后收敛。但是，我不明白为什么即使没有这种缩放算法也不会在合理的时间内收敛。

Answer 1

您面临的问题可以用一个简单的陈述来概括:您的示例的数量不利于收敛或您的感知器。

老实说，我不确定从您的合成示例中到底可以学到什么；无论如何，请不要误会我，在实验室里玩耍并从中学习总是那么好。在拟合神经网络时，有许多建议是通用的，其中一些建议反射(reflect)在对您的问题的评论中。 This paper 很旧但很好，你会看到它被引用。

特别是关于您的问题:这实际上不是标准化而是中心化的问题。问题是当你重新评估你的体重时

self.W = self.W + self.lr * e * x

您的错误项 e 将是 +1 或 -1，具体取决于您错误分类的示例(例如，如果示例目标为 1 并且被分类为 0，则为 +1)，但大多数情况下为 +1，因为有更多的正类，以及您在 x 中的坐标和大多数正值。因此，大多数情况下，您将 将 加到您的权重上，而不是 减去 ，这样感知器找到解决方案的速度显然很慢。

如果你只是缩放你的 X

X = scale(X, with_mean=True, with_std=False)

收敛只需要 1461 个时期。

分类器看起来像这样



边界与正类非常接近是有道理的，因为它们很多；一旦感知器把所有的正类都弄对了，工作就快完成了。

此外，如果您重新平衡数据 - 我已经以这种懒惰的方式进行了测试

trainingSet = np.array([[279.25746446, 162.44072328,   1.        ],
                        [306.23240054, 128.3794866 ,   1.        ],
                        [216.67811217, 148.58167262,   1.        ],
                        [223.64431813, 197.75745016,   1.        ],
                        [486.68209275,  96.09115377,   1.        ],
                        [400.71323154, 125.18183395,   1.        ],
                        [288.87299305, 204.52217766,   1.        ],
                        [245.1492875 ,  55.75847006,  -1.        ],
                        [245.1492875 ,  55.75847006,  -1.        ],
                        [245.1492875 ,  55.75847006,  -1.        ],
                        [245.1492875 ,  55.75847006,  -1.        ],
                        [ 14.95991122, 185.92681911,   1.        ],
                        [393.92908798, 193.40527965,   1.        ],
                        [494.15988362, 179.23456285,   1.        ],
                        [235.59039363, 175.50868526,   1.        ],
                        [423.72071607,   9.50166894,  -1.        ],
                        [423.72071607,   9.50166894,  -1.        ],
                        [423.72071607,   9.50166894,  -1.        ],
                        [423.72071607,   9.50166894,  -1.        ],
                        [423.72071607,   9.50166894,  -1.        ],
                        [ 76.52735621, 208.33663341,   1.        ],
                        [495.1492875 ,  -7.73818431,  -1.        ],
                        [495.1492875 ,  -7.73818431,  -1.        ],
                        [495.1492875 ,  -7.73818431,  -1.        ],
                        [495.1492875 ,  -7.73818431,  -1.        ]])

获得这个分类器需要 2 个时期(令人惊讶)



希望能帮助到你。

评论后编辑

(1) 关于只加减的误差

让我们以正类为例

[279.25746446, 162.44072328,   1.        ]

对于这些，由于 d 等于 0，如果分类器正确， e 只能为 0，如果分类器错误，则只能为 -1。

e = d[i] - self.predict(x)

( predict 返回 0 或 1)

将权重相加时，如果分类器正确，则不增加任何内容，如果错误，则为 -1 * x * 学习率。对于这个例子，假设 lr == 1 ，如果这个正例中存在错误，它将精确减去 (1, 279.25746446, 162.44072328) 。

现在，看看所有正面的例子。如果不变换 X，所有坐标都有正值，因此所有分类误差都会减去权重。

现在让我们举一个反面例子:

[245.1492875 ,  55.75847006,  -1.        ]

对于这些，由于 d 等于 1，如果分类器正确， e 只能为 0，如果分类错误则为 +1。同样，除了第三个反例中的一个坐标外，所有坐标都是正的。因此，几乎所有负类的错误都会增加。

但是只有 3 个负类示例和 12 个正类示例。因此，误差将主要是减去而不是增加权重。 (对不起，我在编辑之前把它放在了我的文本中)。如果你什么都不做，收敛会很慢，如果你集中数据，收敛会更快，这是合理的。 (人们甚至可能想知道它是如何收敛的。)

(2) 关于重采样

我的意思是说，重采样(和居中)的收敛速度非常快，2 个 epoch。然而，重采样使收敛更快是合理的，因为在将输出拉向一个方向或另一个方向的误差之间有更多的平衡。

希望现在更清楚了。

更多评论后编辑

我知道，样本之间的平衡以及它们如何提取解决方案的重要性可能并不是很直观。实际上，我面对您的问题的方式可能正好相反:通过查看您的损失函数，并考虑可能出现的问题，以及我过去遇到的类似问题和我的直觉，我想到了重新平衡 - 然后尝试relabalance 和 after 使数据居中并确认了我对您的损失函数的直觉。直到后来我才试图为你建立一个解释。

当然，并不是我在脑海中处理了损失函数并知道它在做什么。无论如何，我建议您建立自己的直觉，因为您的目标是学习，并且您可以这样做:绘制分隔线如何在历元之间移动。

从您的代码:

labels = [1, 0]
labelColors = ['blue', 'green']

def showData(X, y, plt = plt): 
    colors = [(labelColors[0] if el == labels[0] else labelColors[1]) for el in y] 
    plt.scatter(X[:,0],X[:,1],c=colors)

def plotW(xs, w):
    plt.plot(xs, (w[0] + w[1] * xs)/-w[2], color = 'red', linewidth=4)

import numpy as np
from matplotlib import pyplot as plt
from sklearn.preprocessing import scale

class Perceptron(object):
    """Implements a perceptron network"""
    def __init__(self, input_size, lr=0.1, epochs=1000000):
        self.W = np.zeros(input_size+1)
        #self.W = np.random.randn(input_size+1)
        # add one for bias
        self.epochs = epochs
        self.lr = lr

    def predict(self, x):
        z = self.W.T.dot(x)
        return [1 if self.W.T.dot(x) >=0 else 0]

    def fit(self, X, d):
        errors = []
        for epoch in range(self.epochs):
            if (epoch + 1) % 10000 == 0: print('Epoch',epoch + 1)
            total_error = 0
            for i in range(d.shape[0]):
                x = np.insert(X[i], 0, 1)
                y = self.predict(x)
                e = d[i] - y
                total_error += np.abs(e)
                self.W = self.W + self.lr * e * x
                #print('W: ', self.W)
            errors += [total_error]
            showData(X, d)
            plotW(X[:,0], self.W)
            plt.show()
            if epoch == 100:
                break
            if (total_error == 0):
                print('Done after', epoch, 'epochs')
                nPlot = 100
                plt.plot(list(range(len(errors)-nPlot, len(errors))), errors[-nPlot:])
                plt.show()
                break

if __name__ == '__main__':
    trainingSet = np.array([[279.25746446, 162.44072328,   1.        ],
                            [306.23240054, 128.3794866 ,   1.        ],
                            [216.67811217, 148.58167262,   1.        ],
                            [223.64431813, 197.75745016,   1.        ],
                            [486.68209275,  96.09115377,   1.        ],
                            [400.71323154, 125.18183395,   1.        ],
                            [288.87299305, 204.52217766,   1.        ],
                            [245.1492875 ,  55.75847006,  -1.        ],
                            [ 14.95991122, 185.92681911,   1.        ],
                            [393.92908798, 193.40527965,   1.        ],
                            [494.15988362, 179.23456285,   1.        ],
                            [235.59039363, 175.50868526,   1.        ],
                            [423.72071607,   9.50166894,  -1.        ],
                            [ 76.52735621, 208.33663341,   1.        ],
                            [495.1492875 ,  -7.73818431,  -1.        ]])
    X = trainingSet[:, :2]
    X = scale(X, with_mean=True, with_std=False)
    d = trainingSet[:, -1]
    d = np.where(d == -1, 1, 0)
    perceptron = Perceptron(input_size=2)
    perceptron.fit(X, d)
    print(perceptron.W)

并比较不同设置中生产线的演变。如果您比较居中与不居中时的前 100 个时期，您会发现当您不将数据居中时，线条往往会以某种循环的方式颠簸，而居中时，线条移动得更平滑。 (这实际上与您在降低学习率时通常得到的效果相同，正如一些人在评论中所建议的那样。)

我并不是说查看这些图是损失函数行为的分析证据。我什至不假装这是对您问题的真正答案。但无论如何，如果它可以帮助您建立直觉，那么这将是值得的。

有大量关于收敛的工作，正如您可能知道的那样，由于它是一个关键问题，因此在深度学习中得到了广泛的应用。你肯定听说过不同的优化器以及它们如何影响损失函数的收敛，在深度学习或一般的复杂神经网络中，这当然很难理解，也无法通过分析来解决。