python - 投票感知器对偶形式

Question

这是投票的感知器算法:

#this is a pseudo code
#m is the number of examples

initialize k = 0, w1 := 0, c1 := 0
repeat for T epochs:
    for i = 1 to i = m (this is one epoch)
        if (x[i],y[i]) is classified correctly then 
           c[k] = c[k] + 1
        otherwise:
           w[k+1] = w[k] + y[i]x[i]
           c[k+1]=1
           k = k+1

该算法报告于 http://curtis.ml.cmu.edu/w/courses/index.php/Voted_Perceptron

我想制作一个投票感知器对偶形式。这是我的伪代码:

#m is the number of examples

Initialize k = 0, a1 := 0, c1 := 0
Repeat for T epochs:
    for i = 1 to i = m
        if (x[i], y[i]) is classified correctly then
            c[k] = c[k] + 1
        otherwise
            k = k + 1
            a[k][i] = a[k][i]+1
            c[k] = 1

输出是以下列表:(a_1, c1),(a_2,c2),...,(a_k,ck) 其中每个 a_i 是一个向量

是否正确？我必须添加偏差吗？

在这里，我报告了我对这个投票的双感知器的 python 实现:

类感知器(对象):

def __init__(self, kernel = linear_kernel, epochs = 50):
    self.kernel = kernel
    self.epochs = epochs

def summation(self, a, y, x, xi, b):
    s = 0
    for j in range(0, len(x)):
        s += (a[j]*y[j]*(self.kernel(x[j], xi))) + b
    return s

def maxNorm(self, x):
    v = np.linalg.norm(x[0])
    for i in range(1, len(x)):
        if (np.linalg.norm(x[i]) > v):
            v = np.linalg.norm(x[i])
    return v

def training(self, x, y):
    k = 0
    a = np.zeros(len(x), dtype=np.int)
    alfa = []
    alfa.append(a.copy())
    print(alfa)
    b = 0
    bias = []
    bias.append(0)
    c = []
    c.append(0)
    for _ in range(self.epochs):
        for i in range(len(y)):
            if (y[i] * self.summation(a, y, x, x[i], b))<=0:
                a[i] = a[i] + 1
                alfa.append(a.copy())
                b = b + (y[i]*(self.maxNorm(x)**2))
                bias.append(b)
                c.append(1)
                k = k+1
            else:
                c[k] += 1
    self.alfa = alfa
    self.b = bias
    self.c = c
    print("b: ",len(self.b))
    print("c: ",len(self.c))

def predict(self,xTest, yTest, xTrain, yTrain):
    print("a: ",self.alfa)
    print("\nc:", self.c)
    print(yTest)
    print(yTrain)
    SumFin=0
    Err = np.zeros(len(xTest))
    nErr = 0
    yPredict = []
    for i in range(len(xTest)):
        for j in range(len(self.c)):
             print(self.c[j]*(np.sign(self.summation(self.alfa[i], yTrain, xTrain, xTest[i], self.b[i]))))
             SumFin += (self.c[j]*(np.sign(self.summation(self.alfa[i], yTrain, xTrain, xTest[i], self.b[i]))))
        yPredict.append(np.sign(SumFin))

    for i in range(len(yTest)):
        print("i = ",i," | yTest = ",yTest[i]," | yPredict = ",yPredict[i])
        if(yTest[i] != yPredict[i]):
            nErr += 1
            Err[i] += 1
    print("Error rate: ", ((100*nErr)/len(xTest)), "%")
    self.Err = Err

我认为这段代码行不通，因为如果我预测训练集，我会得到 75% 的错误率。

谁能帮帮我？谢谢

Answer 1

训练: Voted Perceptron Training Algorithm

def voted_perceptron(x, target=y, nb_epoch=1):
    k = v = c = 0
    V = C = []
    for epoch in nb_epoch:
        for i in range(len(x)):
            y_pred = sign(v*k)
            if y_pred == y:
                c += 1
            v += y[i]*x[i]
            c = 1
            k += 1
            V.append(v)
            C.append(c)

    return V,C

预测: Voted Perceptron Prediction Algorithm

def  vp_predict(V, C, X):
    predictions = []
    for x in X:
        s  = 0
        for w,c in zip(V,C):
            s = s + c*sign(np.dot(w,x))
        predictions.append(sign(s))
    return predictions