4

我正在解决加州理工学院机器学习课程的作业 1 ( http://work.caltech.edu/homework/hw1.pdf )。为了解决问题 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 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)

4

1 回答 1

4

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

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

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

通过替换随机抽样，您可能会导致自己花费更长的时间（尽管根据数据样本的分布和大小，这当然不太可能，因为您大致预计任何 15 个点都可以做到前 15 个）。

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

这意味着您的代码将检测到它已正确分类所有点的唯一方法是，如果它评估它们的特定随机序列（在内部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 中进行此类操作的工作、实习和实践技能，而不是与本机数据类型作斗争以做一些它们不是为（数组计算）而设计的事情。

于 2014-05-29T21:14:18.160 回答