4

Caltech Machine Learning Course ( 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 iterationsですが、私の実装では平均50000 iteration. トレーニング データはランダムに生成されますが、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)

4

1 に答える 1

4

Python と分類アルゴリズムの両方を学習して、すばらしい仕事をしていることは明らかです。

ただし、コードの文体が非効率的であるため、支援が難しくなり、問題の一部が教授との間の誤解である可能性が生じます。

たとえば、教授はパーセプトロンを「オンライン モード」または「オフライン モード」で使用することを望んでいますか? 「オンライン モード」では、データ ポイントを順番に移動する必要があり、どのポイントにも再訪しないでください。収束するのに 15 回の反復のみが必要であるという割り当ての推測から、これが最初の 15 個のデータ ポイントが連続した順序で、データ セットを線形に分離する分類子になることを意味するかどうかに興味があります。

代わりに置換でランダムにサンプリングすることにより、はるかに長い時間がかかる可能性があります (ただし、データ サンプルの分布とサイズによっては、15 ポイントが約最初の 15)。

もう 1 つの問題は、正しく分類されたポイント ( が にnot is_misclassified評価される場合) を検出した後、誤って分類されTrueた新しいランダム ポイントを発見した場合、コードは外側のループのより大きなセクションにキックダウンしてから、に戻ることです。ベクトルをすべて 0 で上書きする上部。whilecheck

これは、コードがすべてのポイントを正しく分類したことを検出する唯一の方法は、(内側のwhileループで) それらを評価する特定のランダム シーケンスがたまたますべて 1 の文字列である場合であるということです。特定の 0 は、配列を通過する際に正しく分類されます。

なぜそれがプログラムの所要時間を大幅に長くするのか、完全に形式化することはできませんが、あなたのコードはより厳密な形の収束を必要としているようです。すでにたくさん更新された後のトレーニング段階で。

これについての私の直感がくだらないかどうかを確認する簡単な方法の 1 つは、行を一緒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 に答える