python - 我的玩具 SVM 的 Python 版本有什么错误？

Question

我目前正在浏览 Andrej Karpathy 的 Hacker's guide to Neural Networks .在第 2 章:机器学习、二元分类中，他给出了一个(非常基础的)SVM 示例。这是 Karpathy 的代码:

var a = 1, b = -2, c = -1; // initial parameters
for(var iter = 0; iter < 400; iter++) {
  // pick a random data point
  var i = Math.floor(Math.random() * data.length);
  var x = data[i][0];
  var y = data[i][1];
  var label = labels[i];

// compute pull
  var score = a*x + b*y + c;
  var pull = 0.0;
  if(label === 1 && score < 1) pull = 1;
  if(label === -1 && score > -1) pull = -1;

// compute gradient and update parameters
  var step_size = 0.01;
  a += step_size * (x * pull - a); // -a is from the regularization
  b += step_size * (y * pull - b); // -b is from the regularization
  c += step_size * (1 * pull);
}

以下是我的 Python 版本:

import numpy
import random

X = numpy.array([[1.2, 0.7],
                 [-0.3, 0.5],
                 [-3, -1],
                 [0.1, 1.0],
                 [3.0, 1.1],
                 [2.1, -3]])

labels = [1, -1, 1, -1, -1, 1]

a = 1
b = -2
c = -1

l = len(X)-1

steps = 400

for n in range(0, steps):
    i = random.randint(0, l)
    x = X[i][0]
    y = X[i][1]
    label = labels[i]

    if n == 0:
            for j in range(0, l+1):
                x = X[j][0]
                y = X[j][1]
                label = labels[j]
                score = a*x + b*y + c
                print x,",",y,"-->", label, "vs.", score

    score = a*x + b*y + c
    pull = 0.0
    if label == 1 and score < 1:
        pull = 1
    if label == -1 and score > -1:
        pull = -1

    step_size = 0.01
    a += step_size * (x * pull - a)
    b += step_size * (y * pull - b)
    c += step_size * (1 * pull)

    if n == steps-1:
        print ""
        for j in range(0, l+1):
            x = X[j][0]
            y = X[j][1]
            label = labels[j]
            score = a*x + b*y + c
            print x,",",y,"-->", label, "vs.", score

问题是，即使在超过建议的 400 次迭代之后，对于某些向量，参数也不会产生正确的标签。

这是 400 次迭代后的输出:

1.2 , 0.7 --> 1 vs. -0.939483353298
-0.3 , 0.5 --> -1 vs. -0.589208602761
-3.0 , -1.0 --> 1 vs. 0.651953448705
0.1 , 1.0 --> -1 vs. -0.921882586141
3.0 , 1.1 --> -1 vs. -1.44552077331
2.1 , -3.0 --> 1 vs. 0.896623596303

“-->”后的第一个值是正确的标签，第二个值是分数，即学习的标签。

除第一个标签外，所有矢量/学习标签都是正确的(在被赋予具有正确符号的值的意义上)。

我不确定这是什么原因:我的代码有误吗？我检查了几次，但没有找到任何东西。或者我在这里忘记了一些特定于 Python 的东西。或者，最后，在这种情况下是否有一些与 ML 相关的原因导致没有学习到正确的标签。尽管对此表示怀疑，否则 Karpathy 得到正确的结果是没有意义的。

非常感谢任何意见或帮助解决这个问题。

Answer 1

我相信我找到了问题:

(A) 您的数据集没有线性切割。

(B) Karpathy 的“蒙特卡洛”梯度下降法在这样的数据集上颠簸。

(C) 你和 Karpathy 使用了不同的数据。

DATA SETS
label   Karpathy's      yours
  1     [1.2, 0.7]      [1.2, 0.7]
 -1     [-0.3, -0.5]    [-0.3, 0.5]
  1     [3.0, 0.1]      [-3, -1]
 -1     [-0.1, -1.0]    [0.1, 1.0]
 -1     [-1.0, 1.1]     [3.0, 1.1]
  1     [2.1, -3]       [2.1, -3]

你给的数据集差不多有一条切割线(超平面)大概在y = 1/3x + 1/2，但是接近直线的三个点不断地争论除法。事实证明，最好的分隔符明显不同，将 [1.2, 0.7] 严重地留在了错误的一边，但对此非常不高兴。

原始数据在大约 y = -3x + 1 处有一条整齐的切割线，该算法大致近似为(四舍五入)0.6x - 0.1y - 0.5

同样，该算法正在寻找最小成本拟合，而不是最宽分离 channel 的“纯”SVM。即使有一条整齐的切割线，该算法也不会收敛；相反，它会设法接近可接受的解决方案。

它选择一个随机点。如果该点被可靠地分类——分数是正确的标志，大小 > 1——什么都不会发生。但是，如果该点位于线的错误一侧，或者距离太近而不舒适，则它会拉取参数以获得更有利的处理。

除非 channel 宽度为 2 个单位，否则争议领土内的点将继续轮流来回插入它。没有收敛标准……而且，事实上，在某一点之后没有收敛保证。

仔细查看 Karpathy 的代码:主要算法对分数 < 1 或 > -1 的数据点进行更改(取决于训练类别)。然而，如果结果的符号是正确的，评估算法就宣告胜利。这是合理的，但与训练函数并不完全一致。在我的试验中，第一个点的分数总是小于 0.07，但实际值在 0 的两边华夫饼。其他点很清楚 0，但只有两个点超过 1。有四个点争论这条线应该在哪里。

---

这是否为您解决了问题？