《统计学习方法》学习笔记——感知机
参考书目：《统计学习方法》
模型定义
感知机是二类分类的线性分类模型，其最后输出的类别只取+1和-1二值；会将对应的输入空间划分为正负两类的分离超平面，正类对应输出值+1，负类对应输出值-1，感知机学习的目的就是求出划分训练数据正负类的分离超平面，进而预测新的数据的分类。
定义：假设输入空间是\(x\subseteq R^n\)，输出空间是\(y\) \(=\) \(\{+1, -1\}\),\(x\in X\) 表示输入实例的特征向量，\(y\in Y\) 表示实例的类别
由输入空间到输出空间的函数是
\[f(x) = sign(w \cdot x+b) \]\(w\)为权值向量，\(b\)为偏置(bias), \(w \cdot x\) 表示为\(w\)和\(x\)的内积，\(sign\)是符号函数，只有+1和-1两个输出值
\[sign(x) = \left\{ \begin{array}{lr} +1 &, x \ge 0\\ -1 & , x < 0 \end{array} \right. \]
分离超平面\(S\)的线性方程是\(w \cdot x+b = 0\) ，\(w\)是平面的法向量，\(b\)是平面的截距。它的作用是可以将特征空间划分为两部分，将特征向量分为正负两类。
附图：
学习策略
关于数据集是否具有线性可分性
定义：给定一个数据集\(T = \{(x_1,y_1)(x_2,y_2),...,(x_n,y_n)\}\)，如果存在某个分离超平面\(S\), 满足\(w \cdot x+b = 0\)，对数据集中所有\(y_i =+1\)实例，都有\(w \cdot x_i+b > 0\)，同样对所有\(y_i =-1\)的实例，都有\(w \cdot x_i+b < 0\)，则称数据集\(T\)是线性可分性数据集，否则为线性不可分。
感知机学习策略
感知机学习的目的是为了找到分离超平面\(S\)，它的学习策略是定义损失函数并将损失函数极小化
感知机损失函数的选择是误分类点到超平面\(S\)的距离，输入空间中任意一点\(x_i\)到超平面距离公式是
\[\frac{1}{||w||}|w \cdot x_i+b| \]\(||w||\)是\(w\)的\(L2\)范数，即\(||w|| = \sqrt{\sum^n_iw_i^2}\)
【粗略理解就是微积分中点到平面的距离公式，A, B, C对应向量W， D对应b】
对于所有误分类数据\((x_i, y_i)\)，
\[-y_i(w \cdot x_i+b) > 0 \]
都成立;
就可得误分类点\(x_i\)到超平面\(S\)的距离是
\[-\frac{1}{||w||}y_i(w \cdot x_i+b) \]假设误分类点集合为M，所有误分类点到超平面的总距离为
\[-\frac{1}{||w||}\sum_{x_i \in M}y_i(w \cdot x_i+b) \]
当不考虑w的\(L2\)范数，就可得到感知机的损失函数（经验风险函数），定义为
\[L(w, b) = -\sum_{x_i \in M}y_i(w \cdot x_i+b) \]剩余的\(y(w \cdot x+b)\)为样本点的函数间隔
在超平面确定的情况下，\(|w \cdot x+b|\)相对的表示\(x\)距离超平面的远近，\(y\)的符号表示分类是否正确，可用\(y(w \cdot x+b)\)表示分类的正确性及正确度。（《统计学习方法》第七章）
感知机学习算法
方法：随机梯度下降
算法原始形式
输入：训练数据集\(T = \{(x_1,y_1)(x_2,y_2),...,(x_n,y_n)\}\)，学习率\(\eta (0 < \eta \leq 1)\)
输出：\(w, b\)
感知机模型：\(f(x)= sign(w\cdot x+b)\)
-
设定\(w, b\)初始值，\(w_0, b_0\)
-
选取训练数据集某一数据\((x_i, y_i)\)
-
判断是否为误分类点，即\(y_i(w \cdot x_i+b) \leq 0\)；
-
如果是误分类点，对\(w, b\)进行梯度更新，
\(w \leftarrow w+ \eta y_ix_i\)
\(b \leftarrow b+ \eta y_i\)
-
转回至过程2，直到数据集中不再出现误分类点
书例题2.1（python代码解法）
import numpy as np
# 正负实例点
x = np.array([[3, 3], [4, 3], [1, 1]])
y = np.array([1, 1, -1])
# 初始化参数
w = np.array([[0, 0]])
b = 0
n = 1
def check(xi, yi, w, b): # 判断是否为误分类点
fx = yi*((w*xi)[0] + (w*xi)[1] + b)
if fx <= 0:
return True
return False
def update(xi, yi, w, b, n): # 参数更新
w = w + n*yi*xi
b = b + n*yi
print('w={}，b={}'.format(w, b))
return w, b
while True:
flag = 1
if check(x[0], y[0], w[0], b):
w, b = update(x[0], y[0], w[0], b, n)
flag = 0
if check(x[1], y[1], w[0], b):
w, b = update(x[1], y[1], w[0], b, n)
flag = 0
if check(x[2], y[2], w[0], b):
w, b = update(x[2], y[2], w[0], b, n)
flag = 0
if flag:
break
print("分离超平面w={}, b={}".format(w, b))
算法收敛性
感知机算法在训练集上的误分类次数\(k\)满足不等式：
\[k \leq (\frac{R}{\gamma})^2 \]表示经过有限次搜索可以找到将训练数据完全正确分开的分离超平面，但其解不是唯一的，根据不同的\(w,b\)初始值和迭代顺序而不同
算法对偶形式
根据感知机算法原始形式，
\(w \leftarrow w+ \eta y_ix_i\)
\(b \leftarrow b+ \eta y_i\)
通过误分类点来修改\(w,b\)，假设一共修改了\(n\)次，\(w_0=0, b_0=0\)，则关于\(w, b\) 的增量就是\(\alpha_{i} y_ix_i\)和\(\alpha_i y_i\)
\(\alpha_i = \eta n_i\)，\(n_i\)表示误分类点\((x_i, y_i)\)被误分的次数，此时的\(w, b\)可以表示为
\(w = \sum^{N}_{i=i}\alpha_{i} y_ix_i\)
\(b = \sum^{N}_{i=1}\alpha_i y_i\)
某点更新的次数越多，意味着离分离超平面越近
算法：
输入：训练数据集\(T = \{(x_1,y_1)(x_2,y_2),...,(x_n,y_n)\}\)，学习率\(\eta (0 < \eta \leq 1)\)
输出：\(\alpha, b\)
感知机模型\(f(x) = sign(\sum^N_{j=1}\alpha_j y_j x_j \cdot x+b)\)
-
设初始值\(\alpha = 0,b=0\)
-
在训练数据集中选取\((x_i, y_i)\)
-
判断是否为误分类点，与原始算法不同，这里是
\(y_i(\sum^{N}_{i=1} \alpha_i y_j x_j \cdot x_i +b) \leq 0\)
-
如果此点是误分类，则进行梯度下降更新\(\alpha, b\)
$\alpha_i \leftarrow \alpha_i+ \eta $
\(b \leftarrow b+ \eta y_i\)
-
转回至过程2，直到没有误分类数据
先将训练数据中实例的所有内积计算出来，得到矩阵\(Gram\)
\[G = [x_i \cdot x_j]_{N \times N} \]书例题2.2中Gram矩阵求法
\[G = \left[ \begin{matrix} x1\cdot x1 & x1\cdot x2 & x1\cdot x3 \\ x2\cdot x1 & x2\cdot x2 & x2\cdot x3 \\ x3\cdot x1 & x3\cdot x2 & x3\cdot x3 \end{matrix} \right] \]
\[内部是向量的点乘\]