python - 感知器学习算法需要大量迭代才能收敛？

Question

我正在解决加州理工学院机器学习类(class) (http://work.caltech.edu/homework/hw1.pdf) 的家庭作业 1。要解决问题 7-10，我们需要实现 PLA。这是我在 python 中的实现:

import sys,math,random

w=[] # stores the weights
data=[] # stores the vector X(x1,x2,...)
output=[] # stores the output(y)


# returns 1 if dot product is more than 0
def sign_dot_product(x):
    global w
    dot=sum([w[i]*x[i] for i in xrange(len(w))])
    if(dot>0):
        return 1
    else :
        return -1

# checks if a point is misclassified
def is_misclassified(rand_p):
    return (True if sign_dot_product(data[rand_p])!=output[rand_p] else False)


# loads data in the following format:
# x1 x2 ... y
# In the present case for d=2
# x1 x2 y
def load_data():
    f=open("data.dat","r")
    global w
    for line in f:
        data_tmp=([1]+[float(x) for x in line.split(" ")])
        data.append(data_tmp[0:-1])
        output.append(data_tmp[-1])


def train():
    global w
    w=[ random.uniform(-1,1) for i in xrange(len(data[0]))] # initializes w with random weights
    iter=1
    while True:

        rand_p=random.randint(0,len(output)-1) # randomly picks a point
        check=[0]*len(output) # check is a list. The ith location is 1 if the ith point is correctly classified
        while not is_misclassified(rand_p):
            check[rand_p]=1
            rand_p=random.randint(0,len(output)-1)
            if sum(check)==len(output):
                print "All points successfully satisfied in ",iter-1," iterations"
                print iter-1,w,data[rand_p]
                return iter-1
        sign=output[rand_p]
        w=[w[i]+sign*data[rand_p][i] for i in xrange(len(w))] # changing weights
        if iter>1000000:
            print "greater than 1000"
            print w
            return 10000000
        iter+=1

load_data()

def simulate():
   #tot_iter=train()
    tot_iter=sum([train() for x in xrange(100)])
    print float(tot_iter)/100

simulate()

根据问题 7 的答案，当训练集大小时，感知器需要大约 15 次迭代 才能收敛，但我的实现平均需要 50000 次迭代 。训练数据是随机生成的，但我正在为简单的线条生成数据，例如 x=4、y=2、..等。这是我得到错误答案的原因还是有其他问题。我的训练数据样本(可使用 y=2 分离):

1 2.1 1
231 100 1
-232 1.9 -1
23 232 1
12 -23 -1
10000 1.9 -1
-1000 2.4 1
100 -100 -1
45 73 1
-34 1.5 -1

格式为x1 x2 output(y)

Answer 1

很明显，您在学习 Python 和分类算法方面做得很好。

但是，由于您的代码在文体上有些低效，因此很难为您提供帮助，并且有可能部分问题是您与教授之间的沟通不畅。

例如，教授希望您在“在线模式”或“离线模式”下使用 Perceptron？在“在线模式”中，您应该按顺序移动通过数据点，您不应该重新访问任何点。根据作业的猜想，它应该只需要 15 次迭代才能收敛，我很好奇这是否意味着前 15 个数据点按顺序排列会导致分类器线性分离您的数据集。

通过替换随机抽样，您可能会花费更长的时间(尽管根据数据样本的分布和大小，这不太可能发生，因为您大致预计任何 15 个点都可以做大约以及前 15 个)。

另一个问题是，在您检测到一个正确分类的点之后(当 not is_misclassified 评估为 True 的情况)如果您随后看到一个新的随机点 被错误分类，然后您的代码将进入外部 while 循环的较大部分，然后返回顶部，它将覆盖 check全为 0 的向量。

这意味着您的代码检测到它已正确分类所有点的唯一方法是它评估它们的特定随机序列(在内部 while 循环中)恰好是一个字符串所有 1 的神奇能力除外，在任何特定的 0 上，在通过数组的情况下，它都能正确分类。

我不能完全形式化为什么我认为这会使程序花费更长的时间，但看起来你的代码需要一种更严格的收敛形式，它必须在一个整体上同时学习所有内容在已经更新了一堆之后，在训练阶段后期通过了。

检查我的直觉是否糟糕的一种简单方法是将行 check=[0]*len(output) 移到 while 循环 之外全部放在一起，只初始化一次。

一些使代码更易于管理的一般建议:

1. 不要使用全局变量。相反，让您的函数加载和准备数据返回内容。

2. 有几个地方可以说，比如

   返回(如果 sign_dot_product(data[rand_p]) 为真!=output[rand_p] 否则为假)

   这种事情可以简化为

   返回 sign_dot_product(data[rand_p]) != output[rand_p]

   哪个更容易阅读，并以更直接的方式传达您要检查的标准。

3. 我怀疑效率是否起着重要作用，因为这似乎是一种教学练习，但有许多方法可以重构您对列表理解的使用，这可能是有益的。如果可能，只需使用具有原生数组类型的 NumPy。目睹其中一些操作如何必须用 list 操作来表达是令人遗憾的。即使您的教授不希望您使用 NumPy 来实现，因为她或他正在尝试教您纯粹的基础知识，我也会说忽略它们并去学习 NumPy。与使用 native 数据类型进行非设计用途(数组计算)相比，它对您在 Python 中进行此类操作的工作、实习和实践技能的帮助要大得多。