Perceptron算法需要大量迭代才能收敛？

Question

我正在解家庭作业-1的加州理工学院机器学习课程(http://work.caltech.edu/homework/hw1.pdf) .为了解决问题7-10，我们需要实施解放军。这是我在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 iterations来收敛，但是我的实现需要平均50000 iteration。训练数据是随机生成的，但我正在为简单的行(如x=4、y=2、..etc )生成数据。这是我得到错误答案的原因，还是其他错误的原因。我的培训数据样本(使用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和分类算法。

但是，由于您的代码在风格上有些效率低下，因此很难帮助您，这也为您和教授之间的错误沟通创造了一个机会。

例如，教授是否希望您在“联机模式”或“脱机模式”中使用感知器？在“联机模式”中，您应该顺序地通过数据点，并且不应该重新访问任何点。从赋值的猜想中，它应该只需要15次迭代就能收敛，我很好奇这是否意味着前15个数据点，按顺序顺序，会导致一个分类器，线性地分离您的数据集。

通过随机抽样和替换，您可能会让自己花费更长的时间(尽管，取决于数据样本的分布和大小，这是不太可能的，因为您可以大致地预期任何15个点都可以处理前15个问题)。

另一个问题是，当您检测到一个正确的分类点(在not is_misclassified计算为True的情况下)之后，如果您看到一个新的随机点被错误分类，那么您的代码将被踢到外部while循环的更大部分，然后返回到顶部，它将覆盖所有0的check向量。

这意味着您的代码检测所有点的正确分类的唯一方法是，如果它计算它们的特定随机序列(在内部while循环中)恰好是所有1的字符串，除了在任何特定的0上具有神奇的能力之外，在通过数组的过程中，它正确地分类。

我不太清楚为什么我认为这会使程序花费更长的时间，但是你的代码似乎需要一种更严格的收敛形式，在已经更新了一堆之后，在训练阶段的后期，它必须一次学习所有的东西。

一个简单的方法来检查我对这件事的直觉是否糟糕，那就是把线check=[0]*len(output)全部移到while loop之外，并且只初始化它一次。

让代码更易于管理的一些一般性建议：

1. 不要使用全局变量。相反，让您的函数加载和准备数据返回的东西。
2. 你说有几个地方，例如， return (True if sign_dot_product(data[rand_p])!=output[rand_p] else False) 这类事情可以简化为 return sign_dot_product(data[rand_p]) != output[rand_p] 这是更容易阅读和传达的标准，您正试图以更直接的方式检查。
3. 我怀疑效率是否起着重要的作用，因为这似乎是一项教学练习，但是有许多方法可以重构你对清单理解的使用，这可能是有益的。如果可能，只需使用具有本机数组类型的NumPy。目睹这些操作中的一些必须用list操作来表达是令人遗憾的。即使你的教授不希望你用NumPy来实现，因为她或他试图教你纯粹的基础知识，我还是说忽略它们，去学习NumPy。它将帮助您在Python中进行此类操作的工作、实习和实际技能，而不仅仅是与本地数据类型搏斗来完成他们设计不适合的事情(数组计算)。