最近主要是看 机器学习基石 文章还是半成品，需要继续修改

PLA算法

首先，我们使用人工数据集来研究PLA。数据集下载 点击查看，数据集的每一行包含一个，其中 。该行的前4个数字包含 有序的分量，最后一个数字是 。请使用 初始化算法，并将设为。作为友情提醒，请记住一如既往地添加

1. 通过使用数据集中的示例顺序访问na循环中的示例来实现PLA的版本。在数据集上运行算法。
2. 通过在整个算法中以固定的，预定的随机周期访问示例来实现PLA的版本。在数据集上运行算法。请重复您的实验2000次，每次都有不同的随机种子。算法停止前的平均更新次数是多少？绘制直方图（https://en.wikipedia.org/wiki/Histogram）以显示更新次数与频率的关系。
3. 通过在整个算法中以固定的，预定的随机周期访问示例来实现PLA的版本，同时将更新规则更改为：重量+ 1→WT +ηyn（t）的XN（t）的
   η=0.5η= 0.5。请注意，上一个问题中的PLA对应于η=1η= 1。请重复您的实验2000次，每次都有不同的随机种子。算法停止前的平均更新次数是多少？绘制直方图以显示更新次数与频率的关系。将您的结果与上一个问题进行比较，并简要讨论您的发现。

原理说明（待补充）

代码实现

import numpy as np#for array compute
from numpy import *
import random

def pla():
    W=np.ones(4)#initial all weight with 1
    count=0
    dataset=[[1,0.10723,0.64385, 0.29556    ,1],
            [1 ,0.2418, 0.83075, 0.42741,   1],
            [1 ,0.23321 ,0.81004 ,0.98691,  1],
            [1 ,0.36163, 0.14351 ,0.3153,   -1],
            [1, 0.46984, 0.32142, 0.00042772,   -1],
            [1, 0.25969, 0.87208 ,0.075063, -1],
            ]

    while True:
        count+=1
        iscompleted=True
        for i in range(0,len(dataset)):
            X=dataset[i][:-1]
            Y=np.dot(W,X)#matrix multiply
            if sign(Y)==sign(dataset[i][-1]):
                continue
            else:
                iscompleted=False
                W=W+(dataset[i][-1])*np.array(X)
        if iscompleted:
            break
    print("final W is :",W)
    print("count is :",count)
    return W

def main():
    pla()

if __name__ == '__main__':
    main()

Pocket PLA算法

接下来，我们使用口袋算法。修改问题16中的PLA以纯粹随机访问示例，然后将“口袋”步骤添加到算法中。我们会用点击查看 作为训练数据集D，和 点击查看 作为“验证”算法返回的g的测试集（参见关于验证的第4讲）。这些集的格式与前一个集相同。

1. 运行口袋算法，在D上总共进行50次更新，并使用测试集验证w pocket的性能。请重复您的实验2000次，每次都有不同的随机种子。测试集上的平均错误率是多少？绘制直方图以显示错误率与频率的关系。
2. 修改算法以在50次更新后返回w50w50（50次更新后的PLA矢量）而不是w（袖珍矢量）。在D上运行修改后的算法，并使用测试集验证性能。请重复您的实验2000次，每次都有不同的随机种子。测试集上的平均错误率是多少？绘制直方图以显示错误率与频率的关系。将您的结果与上一个问题进行比较，并简要讨论您的发现。
3. 修改问题18中的算法以运行100次更新而不是50次，并使用测试集验证w pocket的性能。请重复您的实验2000次，每次都有不同的随机种子。测试集上的平均错误率是多少？绘制直方图以显示错误率与频率的关系。将您的结果与问题18进行比较，并简要讨论您的发现。

原理说明（待补充）

代码实现

import sys
import string
import random
import time
from numpy import *
from numpy.linalg import *
 
def Data_Pretreatment(path):
    rawData = open(path).readlines()
    dataNum = len(rawData)
    dataDim = len(rawData[0].strip().split(' ')) + 1
    dataIdx = 0
    X = zeros([dataNum, dataDim])
    X[:, 0] = 1
    Y = zeros(dataNum)
    print(dataNum, dataDim)
    for line in rawData:
        temp = line.strip().split('\t')
        temp[0] = temp[0].split(' ')
        Y[dataIdx] = string.atof(temp[1])
        X[dataIdx, 1:] = double(temp[0])
        dataIdx += 1
    return (X, Y)
 
def PLA_Cycle(X, Y, eta, IsRandom):
    # X : input set of training data, Y : output set of..., eta : learning ratio (0 ~ 1)
    # IsRandom == False -> Naive Cycle,  IsRandom == True -> Random Cycle
    (dataNum, dataDim) = X.shape
    W = zeros(dataDim)
    permutation = range(0, dataNum)
    if IsRandom:
        random.shuffle(permutation)
    else:
        pass
    upDateTimes = 0
    lastUpDateIdx = 0;
    pmtIdx = 0
    dataIdx = 0
    iteCnt = 0
    halt = False
    while not halt:
        dataIdx = permutation[pmtIdx]
        dotProduct = dot(W, X[dataIdx])
        if dotProduct * Y[dataIdx] > 0:
            if dataIdx == lastUpDateIdx:
                halt = True
            else:
                pass
        else:
            # PLA update: W(t+1) = W(t) + eta*Y(n)*X(n)
            W += eta * Y[dataIdx] * X[dataIdx]
            upDateTimes += 1
            lastUpDateIdx = dataIdx
        pmtIdx = (pmtIdx + 1) % dataNum
        iteCnt += 1
        # print(iteCnt, W)
    print('upDateTimes: ', upDateTimes, '\n')
    return (W, upDateTimes)
 
 
def Is_Same_Sign(W, vector, y):
    if (dot(W, vector) > 0 and y > 0) or (dot(W, vector) <= 0 and y < 0):
        return True
    else:
        return False
 
def Get_Err_Num(X, Y, W):
    (dataNum, dataDim) = X.shape
    Sum = 0
    for i in range(0, dataNum):
        if not Is_Same_Sign(W, X[i], Y[i]):
            Sum += 1
    return Sum
 
def Pocket_Algo(X, Y, eta, iterateTimes):
    (dataNum, dataDim) = X.shape
    W_p = zeros(dataDim)
    id_p = 0
    ErrNum_p = Get_Err_Num(X, Y, W_p)
    W = zeros(dataDim)
    ErrNum = 0
    iterate = 0
    dataIdx = 0
    #random.seed(int(time.time() % 3000))
    while iterate <= iterateTimes:
        dataIdx = random.randint(0, dataNum - 1)
        if not Is_Same_Sign(W, X[dataIdx], Y[dataIdx]):
            iterate += 1
            W = W + eta * Y[dataIdx] * X[dataIdx] #!!!! W += eta * Y[dataIdx] * X[dataIdx] will change value of W_p
            ErrNum = Get_Err_Num(X, Y, W)
            if ErrNum < ErrNum_p:
                W_p = W
                ErrNum_p = ErrNum
    # print 'ErrNum_p: ' + str(ErrNum_p)
    return W_p
 
 
if __name__ == '__main__':
    """
    (X, Y) = Data_Pretreatment('train.txt')
    #W = PLA_Cycle(X, Y, 1, 'N')
    #print W
    sum = 0
    for i in range(0, 2000):
        (W, upDateTimes) = PLA_Cycle(X, Y, 0.5, True)
        sum += upDateTimes
    print str(int(sum/2000))
    """
    (X_train, Y_train) = Data_Pretreatment('18_train.txt')
    (X_test, Y_test) = Data_Pretreatment('18_test.txt')
    errSum = 0
 
    for times in range(0, 100):
        #random.seed(times)
        W_pocket = Pocket_Algo(X_train, Y_train, 1, 100)
        errNum_out = Get_Err_Num(X_test, Y_test, W_pocket)
        errSum += errNum_out
        print str(errNum_out)
 
    errRate_out = errSum/100
    print str(errRate_out)

参考资料

---

原理部分
林轩田机器学习基石课程学习笔记1 — The Learning Problem
林轩田机器学习基石课程学习笔记2 — Learning to Answer Yes/No
林轩田机器学习基石课程学习笔记3 — Types of Learning
林轩田机器学习基石课程学习笔记4 — Feasibility of Learning

---

代码部分
PLA算法python实现
PLA和pocket算法：简单Python实现
机器学习基石 作业1 实现PLA和Pocket算法