统计机器学习-------第二章 感知机
0. 介绍
-
本章不从神经网络单元的角度考虑,单纯的把它抽象出来,看作一个简单的二分类线性模型.
-
感知机是神经网络和支持向量机的基础.
1. 感知机模型
~~~~ 感知机模型是一个线性二分类模型,学习的目的是寻找一个可以将实例划分为正负两类的超平面,其模型如下:
- 作用: 输入数据的特征向量 x,输出数据的类别(-1,+1),很明显这是一个判别模型.
f ( x ) = s i g n ( w ⋅ x + b ) \ f(x) = sign(w \cdot x + b) f(x)=sign(w⋅x+b)
- w,b为模型的参数, w ⋅ x w \cdot x w⋅x表示两者内积,sign为符号函数,如下
s i g n ( x ) = { + 1 , x ≥ 0 − 1 , x < 0 sign(x) = \begin{cases} +1 & , & x \ge 0 \\ -1 & , & x < 0 \end{cases} sign(x)={+1−1,,x≥0x<0
2. 学习策略
-
我们使用此模型的前提是数据线性可分
-
上述模型中,w , b 未知,而学习的策略就是为了找到一个超平面(w,b决定)能够完全将正实例和负实例分开.
-
我们引入经验损失函数,将上述描述转化为,学习找到使得损失函数值最小的w,b
2.1 损失函数选择策略
2.1.1 分类损失函数
-
参考[1],常见的损失函数以及其常用的模型如下
-
以上公式,y*f(x)-L的函数关系曲线如下图所示
- 无论是哪种损失函数，本质上都是希望成为0-1 loss的代理，尽可能地继承0-1 loss的完美判别属性的同时，又能有凸函数的性质。
- 可以看到无论是Hinge loss，log loss，exponential loss还是perceptron loss，它们在横轴0点的某一侧（事实上整体都是）都是凸函数，凸函数对于函数求解可是重大利好，所以这一点十分重要。
- 如右子图所示，有一个一飞冲天的loss，即的exponential loss，由于它在离0点较远处惩罚值相当大，所以对训练样本的离群点反应强烈，鲁棒性不好，这个问题也成了使用exponential los的boosting算法的天然缺陷。
2.1.2 回归损失函数
~~~~ 详情可见参考文章: 机器学习总览,损失函数
2.13 感知机的损失函数
~~~~ 对于感知机,在选择损失函数时要优先考虑连续可导的函数,因此以误分类点个数总数为损失函数不可取,选择以误分类点到超平面的距离S为损失函数
- 任意一点到超平面距离公式:
d 0 = 1 ∣ ∣ w ∣ ∣ ∣ w ⋅ x 0 + b ∣ d_{0} = \frac{1}{||w||} |w \cdot x_{0} + b| d0=∣∣w∣∣1∣w⋅x0+b∣
-
由于对于误分类的点来说:
− y i ( w ⋅ x i + b ) > 0 -y_{i}(w \cdot x_{i} + b) > 0 −yi(w⋅xi+b)>0 -
所以对于误分类的点来说,其到平面距离为(去绝对值)
d i = − 1 ∣ ∣ w ∣ ∣ y i ( w ⋅ x i + b ) d_{i} = -\frac{1}{||w||} y_{i}(w \cdot x_{i} + b) di=−∣∣w∣∣1yi(w⋅xi+b)
- 针对所有误分类点,可得损失函数(不考虑
−
1
∣
∣
w
∣
∣
-\frac{1}{||w||}
−∣∣w∣∣1):
L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) L(w,b) = - \sum_{x_{i} \in M}y_{i}(w \cdot x_{i} + b) L(w,b)=−xi∈M∑yi(w⋅xi+b)
3 学习算法
- 有了学习目标:损失函数最小,现在需要用算法将这个目标实现.很明显这是一个最优化问题,感知机选择的优化算法是随机梯度下降法,具体其他优化算法介绍可见:[2,3,4]
原始算法:(基于随机梯度下降)
~~~~
输入:训练集数据,学习率为
η
\eta
η
~~~~
输出:w,b
~~~~~~~
(1) 选取初值
w
0
w_{0}
w0,
b
0
b_{0}
b0
~~~~~~~
(2)在训练集和中选取一个
x
i
x_{i}
xi,
y
i
y_{i}
yi
~~~~~~~
(3)如果
y
i
(
w
⋅
x
i
+
b
≤
0
)
y_{i}(w \cdot x_{i} + b \leq 0)
yi(w⋅xi+b≤0)
~~~~~~~~~~~~~~~
w
←
w
+
η
y
i
x
i
w \gets w + \eta y_{i} x_{i}
w←w+ηyixi
~~~~~~~~~~~~~~~
b
←
b
+
η
y
i
b \gets b + \eta y_{i}
b←b+ηyi
~~~~~~~~~~~~~~~
注:上述更新公式通过简单的对下式求偏导得出
L
(
w
,
b
)
=
−
y
i
(
w
⋅
x
i
+
b
)
L(w,b) = - y_{i}(w \cdot x_{i} + b)
L(w,b)=−yi(w⋅xi+b)
~~~~~~~
(4) 转至(2),直至训练集中没有误分类点
4.对偶形式
详细讨论可见:[5],这里截取部分Zongrong Zheng的笔记,
对应公式和<统计学细方法>有差别,但是更容易理解.
- 对偶形式的感知机，把每轮迭代的时间复杂度的数据规模从特征空间维度n转移到了训练集大小 N上，但增加了预先计算Gram矩阵的时间。所以对于维度高，数量少的训练数据，可以提高每次迭代的性能。
参考
1. 机器学习总览,损失函数
2. 深度学习——优化器算法Optimizer详解（BGD、SGD、MBGD、Momentum、NAG、Adagrad、Adadelta、RMSprop、Adam）
3. 机器学习中的最优化算法总结
4. 优化算法笔记-optimization
5. 如何理解感知机学习算法的对偶形式？知乎讨论