机器学习的第一篇, 写给浮躁的自己
感知机（perceptron）是二分类的线性分类模型，输入为实例的特征向量，输出为实例的类别，取 +1 和 -1 二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。感知机学习算法具有简单而易于实现的优点，是神经网络与支持向量机的基础。
感知机的以一个实数值向量作为输入，计算这些输入的线性组合，如果结果大于某个阈值则输出 +1 否则输出 -1. 如 输入为 x1,x2,...,xn ，则输出为：
f(x)={1,ifw0+w1x1+...+wnxn>0−1,otherwise
其中 wi 是一个实数常量，称为权重(weight)，用来表示 xi 对输出的贡献率。 w0 又写作 b 称为偏置(bias). 在这里 −w0 表示阈值. 为了简化表示, 我们给输入变量增加一个 x0=1 这样式子可以写成向量形式 w⃗ ⋅x⃗ >0 ( x,w∈Rn+1 ), 进一步引入 sign 函数, 上式化简为:
f(x)=sign(w⋅x)
sign 函数:
sign(x)={1,ifx>0−1,otherwise为了方便说明, 这里将 w⃗ ⋅x⃗ ( x,w∈Rn+1 )写作 w⃗ ⋅x⃗ +b ( x,w∈Rn ).
对于线性方程:
w⃗ ⋅x⃗ +b=0
对应于 特征空间 Rn 中一个超平面 S , w 是超平面的法向量, b 是超平面的截距. 这个超平面将特征空间划分为两个部分: 一类为正, 感知器输出 1 ; 一类为负, 感知器输出 -1. 此时超平面 S 被称为 分离超平面(separating hyperplane) 又称为 超平面决策面. 如图 2.1 所示:
在数学中，超平面（Hyperplane）是 n 维欧氏空间中余维度等于 1 的线性子空间。这是平面中的直线、空间中的平面之推广。 设 F 为域（为初等起见，可考虑 F=R）。 n 维空间 Fn 中的超平面是由方程
a1x1+⋯+anxn=b 定义的子集，其中 a1,…,an∈F 是不全为零的常数。 超平面 - 维基百科为什么这么费劲的引入几何解释, 超平面的概念? 因为这对下面的损失函数的推导很有帮助, 而且最重要的是这个概念的引入令我对 n 维空间的距离感变近了.
应用感知机的数据集(训练样本集)必须完全线性可分, 线性可以指的是 给定的数据集 对所有的 yi=−1 , 有 w⃗ ⋅x⃗ +b<0 , 对所有的 yi=1 , 有 w⃗ ⋅x⃗ +b>0 , 几何表示为 超平面 w⃗ ⋅x⃗ +b=0 能够完全将数据集中的正负实例点分开. 那什么是线性不可分的? 举个例子 异或逻辑(XOR).
既然提到异或逻辑, 感知机的一个应用就是用来表示原子布尔函数. 比如一个二输入的感知机就可以表示 AND 和 OR 逻辑. 感知机能表示 AND OR N 逻辑 这一点很重要, 如果我们将他们互联, 两层深度的感知机便可以表示所有布尔函数. 我们现在使用的电脑就是由这些逻辑组合起来的.
为了找出超平面, 即 w,b 我们需要构造一个学习策略, 即定义经验损失函数并将其最小化.
损失函数的一个自然选择就是误分类的总数, 但是这样的损失函数不是参数 w,b 的连续可导函数, 不方便优化. 所以我们选择 误分类点到超平面 S 的距离.
做数学之美妙
下面我们来推导这个损失函数
首先, 写出输入空间中任一点 xi 到超平面的距离
1∥w∥|w⋅xi+b|
∥w∥ 是 w 的 L2 范数.
对于实数 p≥1 , p 范数定义为 ∥x∥p=(|x1|p |x2|p ⋯ |xn|p)1p. 当 p=2 即为 L2 范数, 又称欧几里得范数.
∥x∥2=(x21+x22+⋯+x2n)12. 值得注意的是, p=0 时有两个定义. 一个是数学定义, 另一个是函数. 我们在机器学习中用到的是后者, 即非零元素的总数: |x1|0+|x2|0+⋯+|xn|0. Lp space: #The p-norm in finite dimensions - wikipedia然后, 由于损失函数需要始终大于 0 , 对误分类的数据 (xi,yi) 有
−yi(w⋅xi+b)>0
当 w⋅xi+b>0 时, yi=−1 , 当 w⋅xi+b<0 时, yi=1
这里的 yi 为输出结果(假设输出)
因此, 误分类点 xi 到超平面 S 的距离为
−1∥w∥yi(w⋅xi b)
这样, 假设超平面的误分类点集合为 M , 那么所有误分类点到超平面的总距离为
−1∥w∥∑xi∈Myi(w⋅xi b)
忽略 1∥w∥ , 得到感知机学习的损失函数
L(w,b)=−∑xi∈Myi(w⋅xi+b)
损失函数 L(w,b) 是非负的.没有误分类点时值为 0 , 误分类点越少, 误分类点离超平面越近, L(w,b) 越小. 对于一个样本点, 误分类时是参数 w,b 的线性函数, 正确分类时值为 0, 因此给定训练数据集 T , 损失函数 L(w,b) 是 w,b 的连续可导函数.
分原始模式和对偶模式两种, 使用随机梯度下降方法.
对参数 w,b 的求解转化为求解
minw,bL(w,b)=−∑xi∈Myi(w⋅xi+b)
极小化过程中不是一次使 M 所有误分类点的梯度下降, 二是一次随机选取一个误分类点使其梯度下降.
假设误分类点集合 M 是固定的, 那么损失函数 L(w,b) 梯度由
▽wL(w,b)=−∑xi∈Myixi
▽bL(w,b)=−∑xi∈Myi
给出.
随机选取一个误分类点 (xi,yi) , 对 w,b 进行更新
w←w+ηyixi
b←b+ηyi
η(0<η≤1) 是步长, 又称学习率(leaning rate). 这样, 通过迭代可以使损失函数 L(w,b) 不断减少, 直到为 0 .
关于 delta 法则, 梯度下降, 随机梯度下降 将会另起另一篇
用最开始讲到的简化后的模型简化后的<统计学习方法>算法2.1:
xi=(1,x(1),x(2),...,x(n))T wi=(w(0),w(1),w(2),...,w(n))T
输入: 训练数据集 T={(x1,y1),(x1,y1),...,(xN,yN)} , 其中 xi∈X=Rn+1 , yi∈Y=+1,−1,i=1,2,3,...,N 学习率 η(0<η≤1) 输出: w ; 感知机模型 f(x)=sign(w⋅x)
(1) 选取初值 w
(2) 在训练集中选取数据 (xi,yi)
(3) 如果 yi(w⋅xi)≤0
w←w+ηyixi
(4) 转至 (2) ,直至训练集中没有误分类点
直观解释是 如果有了误分类则调整 w 的值,使分离超平面向该误分类点的一侧移动, 以减少该误分类点与超平面的距离, 直至超平面越过该误分类点使其被正确分类.
留坑, 将例题 2.1 可视化
对偶形式, 指的是从不同的形式去解答一个问题, 但问题的解释一样的.
对偶形式的基本想法是, 将 w 表示为实例 xi 和标记 yi 的线性组合的形式, 通过求解其系数而求得 w
在感知机学习算法的原始形式中, 对误分类点 (xi,yi) 逐步修改 w , 设修改了 n 次, 则 w 关于 (xi,yi) 的增量记作 αiyixi , 其中 αi=niη , 这样学习过程可以表示为
w=∑i=1Nαiyixi
算法 2.2 (简化版原始形式的对偶形式)
输入: 训练数据集 T={(x1,y1),(x1,y1),...,(xN,yN)} , 其中 xi∈X=Rn+1 , yi∈Y=+1,−1,i=1,2,3,...,N 学习率 η(0<η≤1) 输出: α ; 感知机模型 f(x)=sign(∑Nj=1αjyjxj⋅x) , 其中 α=(α1,α2,...,αN)T
(1) α←0
(2) 在训练集中选取数据 (xi,yi)
(3) 如果 yi(∑Nj=1αjyjxj⋅xi)≤0
αi←αi+η
(4) 转至 (2) ,直至训练集中没有误分类点
可以看到对偶形式中训练实例仅以内积的形式出现, 引入 Gram 矩阵形式 储存实例间的内积
G=[xi⋅xj]N×N
比如现在有 3 个实例点 x1,x2,x3 对应 y1,y2,y3
G=⎡⎣⎢x1x1x2x1x3x1x1x2x2x2x3x2x1x3x2x3x3x3⎤⎦⎥
对算法第三步, 可以改写为
(3) 如果 yi(∑Nj=1αjyjGji)≤0
αi←αi+η[1] 李航. 《统计学习方法》[M]. 北京：清华大学出版社，2012：25-35 [2] Tom M. Mitchell. 《机器学习》[M] 曾华军，张银奎等译. 北京：机械工业出版社，2015：63-69 [3] 超平面 - 维基百科 [4] Lp space: #The p-norm in finite dimensions - wikipedia
