2.3 感知机学习算法

一、感知机学习算法的原始形式

算法

输入：
输出：w,b;

1. 选取初值
2. 在训练集中选取数据
3. 如果

1. 转至2，直至训练集中没有误分类点

感知机算法采取不同的初值或者选取不同的误分类点，解可以不同

二、算法的收敛性

相关证明略

当训练数据集线性可分时，感知机学习算法收敛

三、感知机学习算法的对偶形式

对偶形式的思想：将w和b看作是实例和标签的线性组合。对于每一个样本(xi,yi)，有次中将该样本作为了误分类点，故用它去更新参数。而一共有N个样本。

算法

输入：
输出：

1. 
2. 在训练集中选取数据
3. 如果
4. 转至2，直至训练集中没有误分类点

Gram matrix

对偶形式中，训练实例仅以内积的形式出现。
为了方便可预先将训练集中的实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵

四、代码

感知机python代码（原始形式）

import numpy as np
import logging
logging.basicConfig(level=logging.INFO, format='%(asctime)s - %(name)s - %(levelname)s - %(message)s')
logger = logging.getLogger(__name__)
def perceptron(dataArr,labelArr,iter=50):
    print('start')
    dataMat = np.mat(dataArr)
    labelMat = np.mat(labelArr).T
    m,n = np.shape(dataMat)
    w = np.zeros((1,n))
    b = 0
    h = 1
    for k in range(iter):
        for i in range(m):
            xi = dataMat[i]
            yi = labelMat[i]
            if -1*yi*(w*xi.T+b) >=0:
                w += h*yi*xi
                b += h*yi
        logger.info('round %d:%d training' % (k,iter))
    return w,b
data_raw = np.loadtxt("CH02/Input/data_2-1.txt")
X = data_raw[:, :2]
y = data_raw[:, -1]
w,b=perceptron(X,y,6)
def model_test(dataArr, labelArr, w, b):
    print('start to test')
    dataMat = np.mat(dataArr)
    labelMat = np.mat(labelArr).T
    m, n = np.shape(dataMat)
    errorCnt = 0
    for i in range(m):
        xi = dataMat[i]
        yi = labelMat[i]
        result = -1 * yi * (w * xi.T + b)
        if result >= 0: errorCnt += 1
    accruRate = 1 - (errorCnt / m)
    return accruRate
accruRate = model_test(X, y, w, b)
print(accruRate)