前言

大家好，我是鬼仔。今天带来《机器学习高频面试题详解》专栏的第一章监督学习的第一节：感知机，接下来鬼仔将每周更新1～2篇文章，希望每篇文章能够将一个知识点讲透、讲深，也希望读者能从鬼仔的文章中有所收获。

欢迎大家订阅该专栏，可以先看看专栏介绍。如果对文章内容或者排版有任何意见，可以直接在讨论区提出来，鬼仔一定虚心接受！

一、原理

1. 感知机模型

感知机模型是一个最经典古老的分类方法，现在基本没人拿它来作为实际的分类模型，但是其原理很经典，以至于很多算法都是基于感知机模型设计的，比如SVM、神经网络等。下面先介绍感知机模型原理。

假设在一个二维平面内（黑线表示xy轴坐标），有两类数据点：蓝点和黄点，感知机模型希望能找到一个分类平面，将这两类数据点区分开。

用形式化的语言表示，存在k个样本，每个样本对应n维特征和一个二元类别输出y，如下：

其中,

我们的目标是找到一个分类超平面：，其中w和x分别表示n维的向量，使得蓝点样本满足，而黄点样本满足。如果数据是线性可分的，那么满足条件的超平面有很多，比如上图中蓝色、黄色和粉色的平面。

因此，感知机模型可定义为：，其中表示符号函数。

2. 感知机损失函数

感知机的损失函数定义为：所有误分类点到分类平面的距离之和，即，其中M表示所有误分类点的集合，显然该损失函数是非负的，其优化目标就是使得误分类的所有样本，到分类平面的距离之和尽可能最小。

3. 感知机优化算法

感知机优化算法是经典的随机梯度下降，每次随机选取一个误分类点使损失函数的梯度下降，而不是一次性计算所有误分类点的梯度。

优化算法的伪代码如下：

输入：训练集，其中x表示n维特征的向量，。学习步长为α，α值一般在0～1之间。

输出：进而得到感知机模型。

（1）选取的初值：；

（2）在训练集中选取数据点;

（3）判断该数据点是否为误分类，如果，则对进行一次随机梯度下降的迭代：

（4）检查训练集里是否还存在误分类的点，如果没有或者已达到循环次数上限，则算法结束，否则转至第（2）步。

上述优化算法是感知机学习的基本算法，在此基础上还能延伸出对偶形式，但这方面内容，在算法岗面试中基本不出现，所以这里就不讲了，后面SVM的对偶形式会稍微展开讲讲。

4. 多层感知机模型

感知机模型有个明显的缺陷：无法解决XOR问题，这时多层感知机模型登场了。多层感知机（Multi-Layer Perceptron，MLP）有着另一个大家熟悉的名字深度神经网络（Deep Neural Networks，DNN），最主要的特点如下：

（1）加入多个隐藏层，增强模型的表达能力，可轻易解决XOR问题。

（2）输出层拓展到多个，能应用到分类回归任务上。

（3）引入更多类型的激活函数，不局限于()函数，比如sigmoid，tanh，ReLU函数等，进一步增强了模型的表达能力。

5. 反向传播算法

多层感知机增加了多个神经元层，每个神经元都有其对应的参数，那么如何训练得到那么多的最优参数呢？做法还是先定义一个损失函数，然后对损失函数用梯度下降法进行迭代优化求极小值（矩阵计算），这个过程即为反向传播算法。

简单来说，训练数据输入到MLP中，每一层神经元都会利用上一层的输出计算下一层的输出，最后输出结果（前向传播算法）。而反向传播算法将MLP最后输出的结果计算其误差，并且利用链式法则将误差反向逐层传递下去，以此更新权重矩阵。

二、面试真题

1. 感知机算法和SVM算法的区别？

（1）感知机算法的优化目标是最小化所有误分类点到分类平面的距离（函数间隔）之和，所以只要求所有样本分类正确即可，类似于下图中的黄线，很容易过拟合（试想最下面的绿点是噪点的话）。






（2）SVM算法的优化目标是最大化几何间隔，在追求数据点大致分类正确的同时，避免过拟合，类似于下图中的蓝线。

2. 将多层感知机的sigmoid函数改为sign函数，能否解决非线性问题？

可以。sign函数和sigmoid函数一样具有非线性，所以理论上使用sign激活函数的多层感知机就可以逼近任意非线性函数了。之所以后面改为sigmoid函数，是因为它的实际效果会更好，后面还拓展出了更多的激活函数：tanh，ReLU等，后续的章节会详细介绍。






激活函数需要满足的条件：1）非线性，处处可导（也可个别点不可导）；2）导数尽量简单，这样方便求解；3）导数值域范围固定，以免梯度消失或者爆炸。

3. 随机梯度下降算法（SGD）和反向传播算法（BP）有什么区别？

（1）梯度下降算法是求解损失函数极小值，更新神经元权重和偏置的一种方法，梯度指向的方向是其函数值上升最快的方向，也即其反方向是下降最快的方向。梯度下降法有批量（Batch），小批量(mini-Batch)，随机（stochastic）三种类型，区别在于迭代时训练样本的选择不同，工业界使用最多的是mini-Batch的梯度下降法。






（2）反向传播算法是梯度下降算法在DNN上的具体实现方式，将损失反向地进行传播，利用链式法则快速地计算网络中每一个神经元的梯度。

4. 给定数据集（Y，X），运用感知机模型，用python求出其分类平面，不能使用sklearn库。

def perceptron(X, y, iter=50):
    '''
    感知器训练过程
    :param X:训练集的特征数据，二维向量 (list)
    :param y: 训练集的标签，一维向量(list)
    :param iter: 迭代次数，默认50
    :return: 训练好的w和b
    '''
    print('start to trans')
    #将数据转换成矩阵形式（在机器学习中因为通常都是向量的运算，转换称矩阵形式方便运算）
    #转换后的数据中每一个样本的向量都是横向的
    XMat = np.mat(X)
    #将标签转换成矩阵，之后转置(.T为转置)。
    #转置是因为在运算中需要单独取label中的某一个元素，如果是1xN的矩阵的话，无法用label[i]的方式读取
    #对于只有1xN的label可以不转换成矩阵，直接label[i]即可，这里转换是为了格式上的统一
    yMat = np.mat(y).T
    #获取数据矩阵的大小，为m*n
    m, n = np.shape(XMat)
    #创建初始权重w，初始值全为0。
    #np.shape(XMat)的返回值为m，n -> np.shape(XMat)[1])的值即为n，与
    #样本长度保持一致
    w = np.zeros((1, n))
    #初始化偏置b为0
    b = 0
    #初始化步长，也就是梯度下降过程中的n，控制梯度下降速率
    h = 0.0001

    #进行iter次迭代计算
    for k in range(iter):
        #对于每一个样本进行梯度下降
        for i in range(m):
            #获取当前样本的向量
            xi = XMat[i]
            #获取当前样本所对应的标签
            yi = yMat[i]
            #判断是否是误分类样本
            #误分类样本特征为： -yi(w*xi+b)>=0
            if -1 * yi * (w * xi.T + b) >= 0:
                #对于误分类样本，进行梯度下降，更新w和b
                w = w + h *  yi * xi
                b = b + h * yi
        #打印训练进度
        print('Round %d:%d training' % (k, iter))

    #返回训练完的w、b
    return w, b

有些严格的面试官甚至还会要求不能使用任何基础库，这时我们自定义一个矩阵运算的函数即可。

5. 用python实现单层感知机的与门、与非门、或门，以及多层感知机的异或门。

参考这篇博客，把具体的代码贴上来：

import numpy as np
 
def yufei(x1,x2):
    """单层感知机与非门的实现"""
    x=np.array([x1,x2])
    w=np.array([-0.5,-0.5])
    b=0.7
    value=np.sum(w*x)+b
    if value<=0:
        return 0
    else:
        return 1

def huo(x1,x2):
    """单层感知机或门的实现，只有参数不一样"""
    x=np.array([x1,x2])
    w=np.array([0.5,0.5])
    b=-0.2
    value=np.sum(w*x)+b
    if value<=0:
        return 0
    else:
        return 1

def yu(x1,x2):
    """单层感知机与门的实现，只有参数不一样"""
    x=np.array([x1,x2])
    w=np.array([0.5,0.5])
    b=-0.7
    value=np.sum(w*x)+b
    if value<=0:
        return 0
    else:
        return 1  

def yihuo(x1,x2):
    """两层感知机异或门的实现"""
    s1=yufei(x1,x2)
    s2=huo(x1,x2)
    y=yu(s1,s2)
    return y

yihuo(0,0)  #输出0
yihuo(1,0)  #输出1
yihuo(0,1)  #输出1
yihuo(1,1)  #输出0

点击下面卡片链接就可以进入专栏，右上角有订阅选项，欢迎大家订阅～