目标公式

线性分类器：
这里先介绍一下向量点乘和叉乘：
向量的点乘：（粗体代表向量）
向量的点乘又称为内积，设两个向量为 A{x1,2,x3…xn}，B{y1,y2,y3,…yn}，该向量的点乘结果为对应子项的乘积和，也就是x1 * y1 + x2 * y2 + x3 * y3 +…+ xn * yn，点乘结果为一个数值。向量点乘的另一种表达式为 A * B = |A| * |B| * cos\theta
该形式表明，当两个向量的夹角为90度时，两向量的点乘结果为0，此时两向量互相垂直，或者也可以称为两向量正交（0向量和任何向量都正交）。从第二种表达式中，还可以发现 |A| * cos\theta 就是 A 在 B 上的投影，那么点乘就是 A 在 B 上的投影乘以 B 的长度，可以理解为用来体现两个向量平行程度的大小，当两向量垂直时，平行度最小，值为0。

向量的叉乘：
向量的叉乘又称为向量的外积，设两个向量为 A{a,b,c}, B{d,e,f}，两向量的叉乘结果为C{bf - ce, cd - af, ae - bd}，计算结果还是个向量。向量叉乘的另一种表达式为A * B = |A| * |B| * sin\theta，类似的 |A| * sin\theta 就是 A 在 B 垂直方向上的分量，所以两向量的叉乘可以表示两向量的垂直程度，当两个向量平行时，叉乘值为0 ，也就是垂直度最小。

向量叉乘的一个重要性质：
假设 A 和 B 的叉乘结果为 C，则 C 向量分别和 A ，B 正交，C 的方向可以由右手守则来判定。用右手食指指向 A，中指指向 B，此时大拇指的方向就是 C 的方向。

当目标为+1时，得出的结果为-1，说明w、x之间的夹角过大，应当把钝角改为锐角
当目标为-1时，得出的结果为+1，说明w、x之间的夹角过小，应当把锐角改为钝角

Cyclic PLA
(1)find the next mistake of Wt called (Xn(t),Yn(t))

(2)correct the mistake by

PLA什么时候会停下来呢？根据PLA的定义，当找到一条直线，能将所有平面上的点都分类正确，那么PLA就停止了。要达到这个终止条件，就必须保证D是线性可分（linear separable）。如果是非线性可分的，那么，PLA就不会停止。

对于线性可分的情况，如果有这样一条直线，能够将正类和负类完全分开，令这时候的目标权重为wfw_fwf​，则对每个点，必然满足yn=sign(wfTxn)y_n=sign(w_f^Tx_n)yn​=sign(wfT​xn​)，即对任一点：

PLA会对每次错误的点进行修正，更新权重wt+1w_{t+1}wt+1​的值，如果wt+1w_{t+1}wt+1​与wfw_fwf​越来越接近，数学运算上就是内积越大，那表示wt+1w_{t+1}wt+1​是在接近目标权重wfw_fwf​，证明PLA是有学习效果的。所以，我们来计算wt+1w_{t+1}wt+1​与wfw_fwf​的内积：

从推导可以看出，wt+1w_{t+1}wt+1​与wfw_fwf​的内积跟wtw_twt​与wfw_fwf​的内积相比更大了。似乎说明了wt+1w_{t+1}wt+1​更接近wfw_fwf​，但是内积更大，可能是向量长度更大了，不一定是向量间角度更小。所以，下一步，我们还需要证明wt+1w_{t+1}wt+1​与wtw_twt​向量长度的关系：

wtw_twt​只会在分类错误的情况下更新，最终得到的∣∣wt+12∣∣||w_{t+1}^{2||∣∣wt+12​∣∣相比∣∣wt2∣∣||w_{t}}2||∣∣wt2​∣∣的增量值不超过max∣∣xn2∣∣max||x_n^2||max∣∣xn2​∣∣。也就是说，wtw_twt​的增长被限制了，wt+1w_{t+1}wt+1​与wtw_twt​向量长度不会差别太大！

如果令初始权值w0=0w_0=0w0​=0，那么经过T次错误修正后，有如下结论：
wfT∣∣wf∣∣wTwT≥T⋅constant\frac{w_f^T}{||w_f||}\frac{w_T}{w_T}\geq \sqrt T\cdot constant∣∣wf​∣∣wfT​​wT​wT​​≥T​⋅constant

下面贴出来该结论的具体推导过程：

上述不等式左边其实是wTw_TwT​与wfw_fwf​夹角的余弦值，随着T增大，该余弦值越来越接近1，即wTw_TwT​与wfw_fwf​越来越接近。同时，需要注意的是，T⋅constant≤1\sqrt T\cdot constant\leq 1T
​⋅constant≤1，也就是说，迭代次数T是有上界的。根据以上证明，我们最终得到的结论是：wt+1w_{t+1}wt+1​与wfw_fwf​的是随着迭代次数增加，逐渐接近的。而且，PLA最终会停下来（因为T有上界），实现对线性可分的数据集完全分类。

PLA算法

import numpy as np
import matplotlib.pyplot as plt

#建立随机点
def createData():
    points=np.array([[1,3],[3,8],[8,4],[3,4]])
    labels=[-1,-1,1,1]
    return points, labels
#训练感知器模型
class Perceptron:
    def __init__(self,x,y,a=1):
        self.x=x
        self.y=y
        self.a=a
        #w矩阵初始化
        self.w=np.zeros((x.shape[1],1))
        self.b=0

    def sign(self,x,w,b):
        y=np.dot(x,w)+b
        return int(y)

    def update(self,labels_i,data_i):
        # self.w=self.w+labels_i*data_i*self.a
        # self.b=self.w+labels_i*self.a
        tmp = labels_i * self.a * data_i
        tmp = tmp.reshape(self.w.shape)
        # 更新w和b
        self.w = tmp + self.w
        self.b = self.b + labels_i * self.a


    def train(self):
        isFind=False
        while not isFind:
            count=0
            for i in range(self.x.shape[0]):
                tempY=self.sign(self.x[i,:],self.w,self.b)
                if tempY*self.y[i]<=0:
                    count+=1
                    self.update(self.y[i],self.x[i,:])
            if count==0:
                isFind=True
        return self.w,self.b


class Picture:
    def __init__(self,data,w,b):
        self.b=b
        self.w=w
        plt.figure(1)
        plt.title('Perceptron Learing Algorithe',size=10)
        plt.xlabel('x0_axis',size=14)
        plt.ylabel('x1_axis',size=14)

        xData=np.linspace(0,5,10)
        yData=self.expression(xData)
        plt.plot(xData,yData,color='r',label='samples data')

        plt.scatter(data[0][0],data[0][1],s=50)
        plt.scatter(data[1][0], data[1][1], s=50)
        plt.scatter(data[2][0], data[2][1], s=50,marker='x')
        plt.scatter(data[3][0], data[3][1], s=50,marker='x')

    def expression(self,x):
        y=(-self.b-self.w[0]*x)/self.w[1]
        return y

    def show(self):
        plt.show()


if __name__=='__main__':
    sample,labels=createData()
    myperceptron=Perceptron(x=sample,y=labels)
    weights,bias=myperceptron.train()
    picture=Picture(sample,weights,bias)
    picture.show()