文章目录
Lecture 2:Learning to Answer Yes/No
Perceptron Hypothesis Set
举个栗子：
某银行要决定是否要给客户发放信用卡，评价的依据有拥护的年龄、性别、收入、工作时间等等。
我们把每一个客户用一个向量 x = ( x 1 , x 2 , . . . , x d ) x=(x_1,x_2,...,x_d) x=(x1,x2,...,xd)，向量的每一个分量都代表客户的某一种特征，比如 x 1 x_1 x1代表年龄， x 2 x_2 x2代表收入等，可以把这些维度综合起来计算一个“分数”，如果分数超过了阈值就可以发给用户信用卡，反之不可。计算分数的过程中，不同特征的重要性是不同的，所以要给这些特征乘上不同的权重来进行区分。
在上一个Lecture中介绍了机器学习的简要过程：使用某种算法
A
A
A，通过数据集
D
D
D的训练，在假设集中（潜在的候选函数的集合）选出与目标
f
f
f最接近的假设
g
g
g
上图的 h ( x ) h(x) h(x)其实就是一个假设集，这个模型叫做感知机模型
向量化表示：
h
(
x
)
=
s
i
g
n
(
(
∑
i
=
1
d
w
i
x
i
)
−
t
h
r
e
s
h
o
l
d
)
=
s
i
g
n
(
(
∑
i
=
1
d
w
i
x
i
)
+
(
−
t
h
r
e
s
h
o
l
d
)
∗
(
+
1
)
)
=
s
i
g
n
(
(
∑
i
=
1
d
w
i
x
i
)
+
w
0
∗
x
0
)
=
s
i
g
n
(
∑
i
=
0
d
w
i
x
i
)
=
s
i
g
n
(
w
T
x
)
\begin{aligned} h(x) &= sign((\sum^{d}_{i=1}w_ix_i)-threshold)\\\\ &= sign((\sum^{d}_{i=1}w_ix_i)+(-threshold)*(+1))\\\\ &= sign((\sum^{d}_{i=1}w_ix_i)+w_0*x_0)\\\\ &= sign(\sum_{i=0}^{d}w_ix_i)\\\\ &= sign(w^Tx)\\\\ \end{aligned}
h(x)=sign((i=1∑dwixi)−threshold)=sign((i=1∑dwixi)+(−threshold)∗(+1))=sign((i=1∑dwixi)+w0∗x0)=sign(i=0∑dwixi)=sign(wTx)
为了更具体的表示
h
h
h到底是什么样子，让
x
x
x成为一个二维向量，也就是让表示客户特征的向量表示为平面上一个点，数据集中能发卡的客户与不能被发卡的客户用两种不同的点表示，假设集就是
h
(
x
)
=
s
i
g
n
(
w
0
+
w
1
x
1
+
w
2
x
2
)
h(x)=sign(w_0+w_1x_1+w_2x_2)
h(x)=sign(w0+w1x1+w2x2)，最终学习得到的
g
g
g就是一组
w
0
,
w
1
,
w
2
w_0,w_1,w_2
w0,w1,w2,在二维平面上表示为一条线。
在这个模型中所说的感知机就是一条直线，被称作linear(binary) classifier
在更高维度中形如 w T x w^Tx wTx的线性模型也属于linear(binary) classifier
Perceptron Learning Algorithm(PLA)
上面提到了最终需要的 g g g看作是二维平面中的一条线，那么如何在所有的线（假设集）中选出需要的那一条？
思路：先确定一条线 g 0 g_0 g0，然后逐渐地进行修正
对于当前直线，找出某个使用当前线分类错误的点，变换直线的位置，使之能够正确分类这个点。然后对下一个分类错误点继续进行相同的修正过程，直到对数据集中所有点都分类正确。这就是PLA的思想。
右侧两个图的解释：
-
右上：如果正类被误分类成负类，也就是当前 w T x > 0 w^Tx>0 wTx>0,说明 w w w与 x x x夹角大于90度，而 w w w是直线的法向量，所以 x x x位于直线的相对于法向的另一侧，修正的方法就是让二者夹角小于90度，方法是 w : = w + x w:=w+x w:=w+x
-
右下：同理，方法是 w : = w − x w:=w-x w:=w−x
注意：修正直线，后有可能会出现之前分类正确的点变成错误点这种情况，但是经过不断迭代，最终会将所有点完全正确分类
把所有点都遍历一遍，如果出现分类错误的点就修正，直到遍历一遍都没有分类错误的点
图示：
一开始所有的点都是分类错误点（因为没有直线）
分界直线更新成与法向量垂直方向，然后找一个新的错误分类点
更新法向量后继续更新直线
仍然需要考虑的问题：
- PLA一定会停止吗
- 如果停下来了，得到的 g ≈ f ? g\approx f? g≈f?
Guarantee of PLA
PLA的终止条件是找到一条直线将平面上所有的点都分类正确，要达到这个条件，至少要保证对于数据集
D
D
D存在至少一条直线将两种样本分开（
D
D
D线性可分），否则PLA不会停止
假设数据集是线性可分的，说明存在直线可以划分，设此时的权重向量为 w f w_f wf也就是：对于每个点，都满足 y n = s i g n ( w f T x n ) y_n=sign(w_f^Tx_n) yn=sign(wfTxn)
上图的第一部分说明了如果使用 w f w_f wf，对于每个点都能够正确分类，那么代表选中的点的公式（紫色部分）求出的值肯定大于等于离分界线最近的点的值（蓝色部分）大于0
第二部分说明了使用内积衡量两个向量的相似程度，使用第一部分的代换最终得到结论：经过更新之后， w t w_t wt似乎是与理想的 w f w_f wf更加相似的
但是内积更大了有可能是向量长度更大了，所以还要证明 w t + 1 w_{t+1} wt+1与 w t w_t wt向量长度之间的关系：
上图说明了如果只在分类错误的情况下更新 w t w_t wt，那么修正后的 ∣ ∣ w t + 1 ∣ ∣ 2 ||w_{t+1}||^2 ∣∣wt+1∣∣2相对于修正前的 ∣ ∣ w t ∣ ∣ 2 ||w_t||^2 ∣∣wt∣∣2的增量不超过 m a x ∣ ∣ x n ∣ ∣ 2 max||x_n||^2 max∣∣xn∣∣2,也就是更新前后的向量长度相差不会太大。
上图黄色框中公式推导（经过T次更新之后，两个正规化向量乘积>=
C
T
C\sqrt{T}
CT
,正规化之后消去了向量长度的影响，内积仅考虑二者的靠近程度。两个向量不可能无限制地靠近，其内积最大为1，所以会靠近到一定程度停下来，这也证明了算法最终会停止）
w
f
T
w
t
=
w
f
T
(
w
t
−
1
+
y
n
(
t
−
1
)
x
n
(
t
−
1
)
)
≥
w
f
T
w
t
−
1
+
m
i
n
n
y
n
w
f
T
x
n
≥
w
0
+
T
×
m
i
n
n
y
n
w
f
T
x
n
≥
T
×
m
i
n
n
y
n
w
f
T
x
n
\begin{aligned} w_f^Tw_t&=w_f^T(w_{t-1}+y_{n(t-1)}x_{n(t-1)})\\\\ &\geq w_f^Tw_{t-1}+min_n y_nw_f^Tx_n\\\\ &\geq w_0+T\times min_n y_nw_f^Tx_n\\\\ &\geq T\times min_n y_nw_f^Tx_n\\\\ \end{aligned}
wfTwt=wfT(wt−1+yn(t−1)xn(t−1))≥wfTwt−1+minnynwfTxn≥w0+T×minnynwfTxn≥T×minnynwfTxn
∣ ∣ w t ∣ ∣ 2 = ∣ ∣ w t − 1 + y n ( t − 1 ) x n ( t − 1 ) ∣ ∣ 2 = ∣ ∣ w t − 1 ∣ ∣ 2 + 2 y n ( t − 1 ) x n ( t − 1 ) + ∣ ∣ y n ( t − 1 ) x n ( t − 1 ) ∣ ∣ 2 ≤ ∣ ∣ w t − 1 ∣ ∣ 2 + 0 + ∣ y n ( t − 1 ) x n ( t − 1 ) ∣ ∣ 2 （ 因 为 是 错 误 分 类 ， 中 间 项 是 负 数 ） ≤ ∣ ∣ w t − 1 ∣ ∣ 2 + m a x n ∣ ∣ x n ∣ ∣ 2 ≤ ∣ ∣ w 0 ∣ ∣ + T × m a x n ∣ ∣ x n ∣ ∣ 2 = T × m a x n ∣ ∣ x n ∣ ∣ 2 \begin{aligned} ||w_t||^2 &= ||w_{t-1} + y_{n(t-1)}x_{n(t-1)}||^2 \\\\ &= ||w_{t-1}||^2 + 2y_{n(t-1)}x_{n(t-1)} + ||y_{n(t-1)}x_{n(t-1)}||^2\\\\ &\leq ||w_{t-1}||^2 + 0 + |y_{n(t-1)}x_{n(t-1)}||^2 （因为是错误分类，中间项是负数）\\\\ &\leq ||w_{t-1}||^2 + max_n||x_n||^2\\\\ &\leq ||w_{0}||+T\times max_n||x_n||^2=T\times max_n ||x_n||^2 \end{aligned} ∣∣wt∣∣2=∣∣wt−1+yn(t−1)xn(t−1)∣∣2=∣∣wt−1∣∣2+2yn(t−1)xn(t−1)+∣∣yn(t−1)xn(t−1)∣∣2≤∣∣wt−1∣∣2+0+∣yn(t−1)xn(t−1)∣∣2（因为是错误分类，中间项是负数）≤∣∣wt−1∣∣2+maxn∣∣xn∣∣2≤∣∣w0∣∣+T×maxn∣∣xn∣∣2=T×maxn∣∣xn∣∣2
w f T ∣ ∣ w f ∣ ∣ w T ∣ ∣ w T ∣ ∣ = T × m i n n y n w f T x n ∣ ∣ w f T ∣ ∣ ∣ ∣ w t ∣ ∣ ≥ T × m i n n y n w f T x n ∣ ∣ w f T ∣ ∣ T × m a x n ∣ ∣ x n ∣ ∣ ≥ T × m i n n y n w f T x n ∣ ∣ w f T ∣ ∣ m a x n ∣ ∣ x n ∣ ∣ = C T \begin{aligned} \frac{w_f^T}{||w_f||}\frac{w_T}{||w_T||}&=\frac{T\times min_n y_nw_f^Tx_n}{||w_f^T||||w_t||}\\\\ &\geq \frac{T\times min_n y_nw_f^Tx_n}{||w_f^T||\sqrt T\times max_n ||x_n||}\\\\ &\geq\frac{\sqrt T\times min_n y_nw_f^Tx_n}{||w_f^T||max_n ||x_n||}=C\sqrt T \end{aligned} ∣∣wf∣∣wfT∣∣wT∣∣wT=∣∣wfT∣∣∣∣wt∣∣T×minnynwfTxn≥∣∣wfT∣∣T ×maxn∣∣xn∣∣T×minnynwfTxn≥∣∣wfT∣∣maxn∣∣xn∣∣T ×minnynwfTxn=CT
由于二者点乘小于等于1，故
T
×
m
i
n
n
y
n
w
f
T
x
n
∣
∣
w
f
T
∣
∣
m
a
x
n
∣
∣
x
n
∣
∣
≤
1
T
≤
∣
∣
w
f
T
∣
∣
2
m
a
x
n
∣
∣
x
n
∣
∣
2
m
i
n
n
2
y
n
w
f
T
x
n
=
R
2
ρ
2
\frac{\sqrt T\times min_n y_nw_f^Tx_n}{||w_f^T||max_n ||x_n||}\leq 1\\\\ T\leq \frac{||w_f^T||^2max_n ||x_n||^2}{min_n^2 y_nw_f^Tx_n}=\frac{R^2}{\rho^2}
∣∣wfT∣∣maxn∣∣xn∣∣T
×minnynwfTxn≤1T≤minn2ynwfTxn∣∣wfT∣∣2maxn∣∣xn∣∣2=ρ2R2
Non-Separable Data
PLA优点：
- 易于实现
- 快速
- 适用于任何维度
PLA缺点：
- 无法处理非线性可分（应用PLA时假设线性可分，但如果假设错误，则PLA不会停下来）
- 无法完全确定停止用时多长(推导中的 ρ \rho ρ取决于 w f w_f wf)\
大多数情况下的训练集中都或多或少掺杂了噪声数据，这时候就可以看成是非线性可分的，这种情况下可以容忍有错误点，那么当错误点最少时，权重
w
w
w：
这已经被证明是一个NP-hard问题
可以使用pocket algorithm得到近似最好的一条线：
- 首先初始化权重
- 计算当前权重下，分类错误点个数
- 修正错误点更新权重
- 得到的新的直线计算分类错误点个数
- 如果相对于更新前错误点数目较少，则更新最佳直线
- 迭代一定次数，最终的直线当作最好的直线
Summary
这节课主要介绍了感知机模型以及PLA算法。证明了对于线性可分问题，PLA可以停下来并实现正确分类。对于非线性可分的问题，可以使用Pocket Algorithm来解决。