第二章 感知机
-
二分类线性模型，输入实例的特征向量，输出+1，-1二值代表的类别。 -
公式：
f
(
x
)
=
s
i
g
n
(
ω
?
x
+
b
)
f(x) = sign(\omega \cdot x + b)
f(x)=sign(ω?x+b)，
s
i
g
n
(
x
)
sign(x)
sign(x) 函数将正负值规约到±1。 -
本质是用一个
N
N
N 维的超平面将特征空间划分为正负两部分。
ω
,
b
\omega, b
ω,b 就是超平面的法向量和截距。 -
损失函数：误分类的点个数不是
ω
,
b
\omega, b
ω,b 的连续可导函数，不易优化。采用误分类点到超平面
S
S
S 的总距离。空间中任意一点到
x
0
x0
x0 到
S
S
S 的距离：
1
∥
ω
∥
∣
ω
?
x
+
b
∣
\frac{1}{\|\omega\|}\vert\omega \cdot x + b\vert
∥ω∥1?∣ω?x+b∣
又对于误分类的数据，有
∣
ω
?
x
i
+
b
∣
\vert\omega \cdot x_i + b\vert
∣ω?xi?+b∣ 与
y
i
y_i
yi?（±1） 异号，故可以通过乘
y
i
y_i
yi?去掉绝对值，再对全体误分类点求和，忽略系数，得到感知机学习的损失函数：
L
(
ω
,
b
)
=
?
∑
x
i
∈
M
y
i
(
ω
?
x
i
+
b
)
L(\omega,b) = -\sum_{x_i \in M}y_i(\omega \cdot x_i + b)
L(ω,b)=?xi?∈M∑?yi?(ω?xi?+b)
其中
M
M
M 为误分类点的集合。 -
导数：一元函数
y
=
f
(
x
)
y=f(x)
y=f(x) 在某一点沿
x
x
x 轴正方向的变化率（一个值）；
偏导数：多元函数沿某个轴正方向的变化率（一个值）；
方向导数：函数沿任意方向的变化率（一个值）；
梯度：函数在空间中变化率最大的方向，是一个向量，记作
?
f
\nabla f
?f。这个方向在每个轴上的分量就是沿该轴的偏导数。 -
对于我们的最优化问题，可以将参数
ω
,
b
\omega, b
ω,b 和损失函数的取值对应为一个三维空间的
x
,
y
,
z
x, y, z
x,y,z 轴，我们要找出“山”上海拔最低的位置。从任意点出发，每次计算“下山”最快的梯度方向，然后向该方向前进一小步，不断迭代直至损失函数减小至0。每次前进的距离称为步长（或学习率）。 -
L
L
L 关于
ω
,
b
\omega, b
ω,b 的偏导分别为
?
ω
L
(
ω
,
b
)
=
?
∑
x
i
∈
M
y
i
x
i
?
ω
b
(
ω
,
b
)
=
?
∑
x
i
∈
M
y
i
\nabla_{\omega}L(\omega, b) = - \sum_{x_i \in M}y_ix_i \\ \nabla_{\omega}b(\omega, b) = - \sum_{x_i \in M}y_i
?ω?L(ω,b)=?xi?∈M∑?yi?xi??ω?b(ω,b)=?xi?∈M∑?yi?
每次随机选一个误分类点，依据该点数据对参数进行更新：
ω
←
ω
+
η
y
i
x
i
b
←
b
+
η
y
i
\omega \leftarrow \omega + \eta y_i x_i \\ b \leftarrow b + \eta y_i
ω←ω+ηyi?xi?b←b+ηyi? -
由此得到感知机学习算法的原始形式：
- 选取初值
ω
0
,
b
0
\omega_0, b_0
ω0?,b0? ；
- 在训练集中选取数据
(
x
i
,
y
i
)
(x_i, y_i)
(xi?,yi?) ；
- 如果
y
i
(
ω
?
x
i
+
b
≤
0
)
y_i(\omega \cdot x_i + b \leq 0)
yi?(ω?xi?+b≤0), 使用上面的公式更新
ω
,
b
\omega, b
ω,b ；
- 转至2，直至训练集中没有误分类点。
-
可以证明（P42），误分类次数有上界，经过有限次搜索可以找到将训练数据完全正确分开的超平面。 -
感知机学习算法的对偶形式：由
ω
,
b
\omega, b
ω,b 的更新公式可知，假设一个点
x
i
x_i
xi? 被使用（误分类）了
n
i
n_i
ni? 次，令
a
i
=
n
i
η
a_i = n_i \eta
ai?=ni?η 则最终学习到的
ω
,
b
\omega, b
ω,b 可以用以下形式代替：
ω
=
∑
i
=
1
N
a
i
y
i
x
i
b
=
∑
i
=
1
N
a
i
y
i
\omega = \sum_{i=1}^N a_i y_i x_i \\ b = \sum_{i=1}^N a_i y_i
ω=i=1∑N?ai?yi?xi?b=i=1∑N?ai?yi?
于是问题转变为对变量
a
i
(
n
i
)
a_i(n_i)
ai?(ni?) 的学习。算法：
-
α
←
0
,
b
←
0
\alpha \leftarrow 0, b \leftarrow 0
α←0,b←0；
- 在训练集中选取数据
(
x
i
,
y
i
)
(x_i, y_i)
(xi?,yi?)；
- 如果
y
i
(
∑
j
=
1
N
α
j
y
j
x
j
?
x
i
+
b
)
≤
0
y_i \left (\sum\limits_{j=1}^N \alpha _j y_j x_j \cdot x_i + b \right) \leq 0
yi?(j=1∑N?αj?yj?xj??xi?+b)≤0，更新：
α
i
←
α
i
+
η
b
←
b
+
η
y
i
(
o
r
:
?
n
i
←
n
i
+
1
)
\alpha_i \leftarrow \alpha_i + \eta \\ b \leftarrow b + \eta y_i \\ (or: \ n_i \leftarrow n_i + 1)
αi?←αi?+ηb←b+ηyi?(or:?ni?←ni?+1) - 转至2，直到没有误分类数据。
-
结果上与原始形式是等价的，主要作用是可以通过预计算实现效率提升。原始形式中，判断分类正误的公式中
ω
?
x
i
\omega \cdot x_i
ω?xi? 内积计算复杂度为
O
(
n
)
O(n)
O(n)，其中
n
n
n 为特征空间维数；而对偶形式中由于内积均以
x
i
?
x
j
x_i \cdot x_j
xi??xj? 形式出现，故可以预先计算出所有组合，形成一个对称/三角矩阵（Gram矩阵），复杂度由求和项决定，即
O
(
N
)
O(N)
O(N) ，转移到了训练集大小
N
N
N 上。对于训练数据量远小于特征空间维数的数据集，该方法可以有效提升效率。
|