林轩田机器学习2

目标公式林轩田机器学习2

林轩田机器学习2线性分类器:
林轩田机器学习2这里先介绍一下向量点乘和叉乘:
向量的点乘:(粗体代表向量)
向量的点乘又称为内积,设两个向量为 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 的方向。

林轩田机器学习2
当目标为+1时,得出的结果为-1,说明w、x之间的夹角过大,应当把钝角改为锐角
当目标为-1时,得出的结果为+1,说明w、x之间的夹角过小,应当把锐角改为钝角
林轩田机器学习2
Cyclic PLA
(1)find the next mistake of Wt called (Xn(t),Yn(t))
林轩田机器学习2
(2)correct the mistake by
林轩田机器学习2

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

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

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​的内积:林轩田机器学习2

从推导可以看出,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​向量长度的关系:林轩田机器学习2

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

下面贴出来该结论的具体推导过程:
林轩田机器学习2林轩田机器学习2
上述不等式左边其实是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()
上一篇:林轩田机器学习基石课程个人笔记-第二讲


下一篇:PLA(perceptron learning algorithm)感知机学习