机器学习之感知机

作者: Vophan | 来源:发表于2019-01-14 12:58 被阅读22次

    更新...
    最近在一点一滴的实现机器学习的算法。
    很多本来看来简单的东西,现在看来并没有那么简单,只不过是自己想的太简单了。
    就比如说感知机。
    我本来就以为是我下面说的那样,但是知道,我用python去实现他的每一个细节时,才发现并没有那么简单。

    感知机的两个形式

    感知机其实是有两种形式的,一种叫做原始形式,一种叫做对偶形式,我们先来谈谈原始形式

    原始形式

    这就要谈到什么是感知机了?现在我看来,感知机就是一个分类模型,一个解决线性可分问题的分类模型。在空间中有两坨线性可分的点,我们用一条直线,或者一个平面,或者更高维度的表示,去将他们全部分开。没错,就是全部,不会有一个错误分类点。
    然后,我们就要探究一下,它的原理。
    他是怎么做到的?
    我们首先要理解机器学习的问题,实际上,机器学习问题就是一个优化问题,就是我们可以通过调整一些东西(参数),来使系统有更好的性能,这就叫学习。而学习要有学习策略,我们的学习策略就是使损失函数最小。
    现在就要提出感知机的原理了。感知机是一种错误驱动的模型,什么叫做错误驱动呢?就是说我们要根据错误分类点对模型参数进行矫正,从而使模型有更好的性能。从而我们得到了感知机的损失函数:就是所有误分类点到直线的距离之和最小。


    Loss Function 误分类判据

    下面我们要根据学习策略转换一下问题:
    使用一种方法最小化Loss Function,我们这里使用梯度下降法,来对Loss Function进行优化。
    具体梯度下降法,请见我的另一篇文章。
    说一下算法的具体步骤吧。
    1、首先我们初始化所有的变量,权重w和偏置b
    2、然后遍历所有的点,找出所有的误分类点,
    3、根据误分类点进行参数(w,b)的更新,至于如何更新,这就涉及到了梯度下降的内容,剧透一下,因为我们知道,对于一个函数,他的梯度的反方向是他降低的最快的方向,所以我们想要通过更新参数的方式来最小化Loss Function,我们就要让参数沿着梯度方向更新,这样我们就得到了参数更新的内容。


    weight
    bias

    3、检测是否还有误分类点,如果有重复上述过程。


    结果

    这就是原始形式的感知机。
    代码如下:

    import numpy as np
    import pandas as pd
    import matplotlib.pyplot as plt
    
    def generator_data():
        data = {
            'x': [],
            'y': []
        }
        np.random.seed(1)
        x1 = np.random.randint(0, 100, 50)
        y1 = np.random.randint(0, 100, 50)
    
        x2 = np.random.randint(100, 200, 50)
        y2 = np.random.randint(100, 200, 50)
    
        point_x = np.hstack((x1, x2))
        # print(len(point_x))
        point_y = np.hstack((y1, y2))
    
        for i in range(100):
            data['x'].append((point_x[i], point_y[i]))
            if(i < 50):
                data['y'].append(-1)
            else:
                data['y'].append(1)
    
        plt.scatter(x1, y1)
        plt.scatter(x2, y2)
    
        return data
    
    
    class Perceptron(object):
        def __init__(self, data):
            self.x = data['x']
            self.y = data['y']
            self.w = np.ones(2)
            self.b = 1
            self.lr = 0.1
    
        def update(self, x, y):
            self.w += self.lr * np.dot(y, x)
            self.b += self.lr * y
    
        def update1(self, x, y):
            return self.lr * np.dot(y, x), self.lr * y
        
        def judge(self, x, y):
            w = self.w
            t = np.dot(w, x) + self.b
            # print('t', t)
            # print('错误样本', w, t)
            if t * y <= 0:
                return True
            return False
    
        def train(self):
            tran_len = len(self.x)
            wrong_sample = True
            wrong_sample_num = 0
            while wrong_sample:
                wrong_sample_num = 0
                for i in range(tran_len):
                    if self.judge(self.x[i], self.y[i]):
                        self.update(self.x[i], self.y[i])
                        wrong_sample_num += 1
                if not wrong_sample_num:
                    wrong_sample = False
    
    def main():
        data = generator_data()
        p = Perceptron(data)
        p.train()
        w = p.w
        b = p.b
        print(w, b)
       
    if __name__ == "__main__":
        main()
    

    那么我们就有一个问题了,我们的特征空间有1000维,那么我们就要进行1000次矩阵乘法,这样我们就占用很大时间,那么我们怎么才能减少这些时间呢?
    这就引出了对偶形式。

    对偶形式

    对偶形式的出现就是为了解决特征空间维度较高时,我们所耗费的计算时间,我们通过一个Gram矩阵,先把所有N个样本所有矩阵的乘法算出来,然后用到的时候查表这样,就把时间复杂度从O(n),变成了O(N).
    代码如下:

    import numpy as np
    import matplotlib.pyplot as plt
    
    
    class antithesis:
    
        def __init__(self, data):
            self.lr = 0.5
            self.data = data
            self.alpha = np.zeros((1, len(data))).reshape(len(data))
            self.bias = 0
            self.gram = np.zeros((len(data), len(data)))
            self.wrong_num = 0
    
        def judge(self, index):
    
            w = 0
            for i in self.data:
                w += self.alpha[self.data.index(i)]*self.data[self.data.index(i)]['flag'] * \
                    self.gram[self.data.index(i)][index]
                
                # print('-----------------------')
                # print('alpha:',self.alpha)
                # print('w:',w)
                # print('bias',self.bias)
                # print('point:',i)
    
            judge = self.data[index]['flag'] * (w + self.bias)
            print('judge:', judge)
            
            if judge <= 0:
                return True        # True means wrong answer
            else:
                return False
    
        def cal_wrong_sample(self):
            for i in self.data:
                if self.judge(self.data.index(i)):
                    self.wrong_num += 1
                else:
                    continue
    
        def update(self, index):
            # print('i have updated')
            self.alpha[index] += self.lr
            self.bias += self.data[index]['flag']
    
        def get_gram(self):
    
            for i in self.data:
                for j in self.data:
                    index_1 = self.data.index(i)
                    index_2 = self.data.index(j)
                    self.gram[index_1][index_2] = np.dot(i['data'], j['data'])
    
    
    def data_produce():
    
        x1 = np.random.randint(0, 100, 10)
        y1 = np.random.randint(0, 100, 10)
        x2 = np.random.randint(100, 200, 10)
        y2 = np.random.randint(100, 200, 10)
    
        x = np.hstack((x1, x2))
        y = np.hstack((y1, y2))
    
        final_data = []
    
        for i in range(20):
            data = [x[i], y[i]]
            if(i < 10):
                data_dict = {'data': data, 'flag': -1}
            else:
                data_dict = {'data': data, 'flag': 1}
            final_data.append(data_dict)
    
        return final_data
    
    if __name__ == "__main__":
    
        real_data = data_produce()
    
        # print(real_data)
    
        a = antithesis(real_data)
        a.get_gram()                 # cal the gram matrix
    
        while True:
            wrong_num = 0
            for i in a.data:
                i_index = a.data.index(i)
                if a.judge(i_index):
                    wrong_num += 1
                    a.update(i_index)
    
            # a.cal_wrong_sample()
            print('[*]: wrong number: ', wrong_num)
            if wrong_num == 0:
                break
    
        w = np.zeros((1, 2)).reshape(2)
        for i in a.data:
    
            index = a.data.index(i)
            w += a.alpha[index] * a.data[index]['flag'] * \
                np.array(a.data[index]['data']).reshape(2)
    
        print(w)
        print(a.bias)
    
        testx1 = -100
        testy1 = testx1 * w[0] / (-1 * w[1]) + a.bias/(-1 * w[1])
        testx2 = 200
        testy2 = testx2 * w[0] / (-1 * w[1]) + a.bias/(-1 * w[1])
    
        x1 = np.random.randint(0,100,10)
        y1 = np.random.randint(0,100,10)
        x2 = np.random.randint(100,200,10)
        y2 = np.random.randint(100,200,10)
        
        plt.scatter(x1,y1)
        plt.scatter(x2, y2)
        plt.plot([testx1,testx2],[testy1,testy2])
        plt.show()
    

    联想

    在学习感知机过程中,我理解了他为什么叫做神经网络与支持向量机的基础。
    我们知道,感知机的基础是给我们一组线性可分的数据,但是如果给我们一组不可分的数据呢?
    我有两个办法:
    一是下面提到:多层感知机
    二是:支持向量机

    多层感知机,也就是神经网络的雏形,但是他有一个不好的地方是什么呢?
    就是,他得手动调参,相比神经网络误差反向传播,他很麻烦。
    然后呢?
    还有支持向量机:
    他通过核技巧来解决线性不可分问题。
    所以,他被称为支持向量机和感知机的雏形。
    以上是我个人的见解,如果有错误的地方,欢迎大家给我指出。


    什么是感知机

    我认为感知机其实就是一个多输入单输出的处理机制

    就是设定一个阈值来判断所有输入信号的加权和是否能够引起输出信号。 {70%}

    其实就是这样的一个东西,他是神经网络的雏形。

    感知机如何工作

    感知机的每一个单元都有一个权重(weight),然后还有一个阈值(theta),当然还包括输入与输出信号。

    感知机通过得到所有输入信号与权重的乘积得到一个值,这个值与我们所设定好的阈值所比较。

    如果这个值大于阈值,则输出信号输出1(输出),如果小于阈值,则输出0(不输出)。

    举例子

    两输入的感知机

    \begin{equation} y=\left\{ \begin{array}{**lr**} 0\qquad(w_1x+w_2x\leq\theta)\\ 1\qquad(w_1x+w_2x>\theta)\\ \end{array} \right. \end{equation}

    这就是两输入的感知机的公式。

    感知机实现简单门电路

    def AND(x1,x2):
        w1 = 0.5,w2 = 0.5,theta = 0.8
        if w1*x1 + w2*x2 <theta:
            return 0
        else:
            return 1
    
    AND(0,1)
    AND(0,0)
    
    #... and so on
        
    

    存在的问题

    • 首先,一层的感知机只能解决线性可分的问题,怎么解释这个线性可分呢?

      其实可以把感知机模型理解为一个分类模型,用来分别不同输出情况的分类模型。

      但是只有一层的话他的判别条件就是一维空间上的一条直线,只能分别出线性可分的问题。

    • 其次,我们知道多层的感知机也可以拟合出比较复杂的情况,但是也存在问题,就是权重和偏差这些参数是需要我们自己给出的。这就是最大的问题。

    补充

    单层感知机通常被称为朴素感知机,激活函数为阶跃函数

    多层感知机是指神经网络,即使用了sigmoid函数等平滑的激活函数的多层神经网络

    相关文章

      网友评论

        本文标题:机器学习之感知机

        本文链接:https://www.haomeiwen.com/subject/ukmddqtx.html