感知器算法的实现，但运行时效率不高

Question

当样本大小设置为 10 时，直到收敛的平均迭代次数应该在 15 左右。但是，在我的代码中实现该算法时，大约需要 225（或更多！）次迭代才能达到收敛。这让我怀疑我的代码中的 while 循环可能存在问题，但我无法识别它。

def gen_data(N=10):
    size = (N, 2)
    data = np.random.uniform(-1, 1, size)
    point1, point2 = data[np.random.choice(data.shape[0], 2, replace=False), :]
    m = (point2[1] - point1[1]) / (point2[0] - point1[0])
    c = point1[1] - m * point1[0]
    labels = np.array([+1 if y >= m * x + c else -1 for x, y in data])
    data = np.column_stack((data, labels))
    return data, point1, point2


class PLA:
    def __init__(self, data):
        m, n = data.shape
        self.X = np.hstack((np.ones((m, 1)), data[:, :2]))
        self.w = np.zeros(n)
        self.y = data[:, -1]
        self.count = 0

    def fit(self):
        while True:
            self.count += 1
            y_pred = self.predict(self.X)
            misclassified = np.where(y_pred != self.y)[0]
            if len(misclassified) == 0:
                break

            idx = np.random.choice(misclassified)
            self.update_weight(idx)

    def update_weight(self, idx):
        self.w +=  self.y[idx] * self.X[idx]

    def sign(self, z):
        return np.where(z > 0, 1, np.where(z < 0, -1, 0))

    def predict(self, x):
        z = np.dot(x, self.w)
        return self.sign(z)

Answer 1

问题不在于你的右循环，而在于你的数据生成函数。

您从

N

随机点中选择两个点来定义您的决策线：

point1, point2 = data[np.random.choice(data.shape[0], 2, replace=False), :]

但它们随后仍保留在您的数据集中，因此它们被标记为 1 并且正好位于您的决策线上。

如果您随机选取两个不在数据集中的点，那么该算法应按照我测试的大约 10 个步骤收敛（只需采样

N + 2

点并选择前两个点来定义您的决策线，其他点用于您的数据集） ).

那么为什么这个微小的差异会减慢收敛所需的步数呢？

我想说，因为数据集中的两个点位于决策线上，所以学习零误差模型可能是最困难的，特别是当其他点接近它时，因为一次模型更新可能会导致模型仍然不完美。

定义决策线以使数据集中没有点位于其上是否相关？

我会说是，因为域空间是连续的。