Perceptron Hypothesis Set

信用卡批准问题回顾： 图2-1

那么对于这个问题，\(H\)究竟长什么样呢？

这里，我们可以把每个用户表示成一个向量： \[\mathbf{x} = (x_1, x_2, \cdots, x_d)\]

并计算一个加权的“分数”：

  • 如果\(\sum_{i=1}^dw_ix_i > threshold\)，那么批准信用卡的申请
  • 如果\(\sum_i=1^dw_ix_i < threshold\)，那么拒绝信用卡的申请

输出空间为\(Y: \{+1(good), -1(bad)\}\)。边界情况0经常被我们忽略， 因为它很少发生，也不太重要。那么我们的假设就是一个线性函数\(h \epsilon H\)： \[h(x) = sign((\sum_{i=1}^dw_ix_i)-threshold)\] 这个机器学习假设函数被叫做感知机（Perceptron），来源于早期类神经网络的研究者，因为很像人大脑中的一个神经元而得名。

这个\(h\)形式略麻烦，这里从符号上进行简化： 图2-2

使得每一个向量\(\mathbf w\)都表示一个假设函数\(h\)，而每一个向量\(\mathbf x\)都表示一个用户。

这么说起来还是很抽象，那么每一个\(h\)到底长什么样呢？这里有一个二维的例子： 图2-3

Perceptron Learning Algorithm (PLA)

现在我们的任务就是从所有的感知机（线、平面等）中选出我们想要的\(g\)：

  • 我们想要\(g \approx f\)。但是很难，因为\(f\)我们不知道
  • 我们只知道我们的资料是从\(f\)产生的，那我们可以要求在我们所拥有的数据\(D\)上，有： \[g(x_n) = f(x_n) = y_n\]
  • 但是即使到这一步了，也不是太容易。因为\(H\)无限大
  • 那我们的idea是：从一个不太好的\(g_0\)出发，然后不断地参考它在\(D\)上的错误 来修正它。 接下来，我们会用\(\mathbf w_0\)来代表\(g_0\)。

那么完整的PLA算法将是这样的： 图2-4 其中更新的思路大概是这样：

  • 如果在某\(\mathbf x\)处，其本身的label是\(y=1\)，结果\(h\)却输出\(y=-1\)， 那么说明\(\mathbf w\)和\(\mathbf x\)的夹角太大，可以在\(\mathbf w\)上加上 \(y\mathbf x\)让它向\(\mathbf x\)靠近一些。
  • 如果在某\(\mathbf x\)处，其本身的label是\(y=-1\)，结果\(h\)却输出\(y=1\)， 那么说明\(\mathbf w\)和\(\mathbf x\)的夹角太小，可以在\(\mathbf w\)上加上 \(y\mathbf x\)让它向\(\mathbf x\)远离一些。

其中的哲学可以说是：

知错能改，善莫大焉。

常见的PLA实现方式有：

循环PLA

  1. 对\(t=0,1,\ldots\)
    1. 找到\(\mathbf{w}_t\)犯的下一个错误\((x_{n(t)}, y_{n(t)})\) s.t. \[sign(\mathbf w_t^T \mathbf x_{n(t)}) \neq y_{n(t)}\]
    2. 按照以下方式纠正这个错误： \[\mathbf w_{t+1} \leftarrow \mathbf w_{t}+y_{n(t)}\mathbf x_{n(t)}\]
  2. 直到在一轮完整的循环中找不到错误

其中下一个既可以按照自然循环顺序\((1,2,\cdots,N)\)来遍历，也可以通过提前计算的随机循环顺序来遍历。

既然演算法停的时候就会找出一个好的Perceptron，那么：

  • 算法一定会停吗？
    • 按照自然循环会停吗？
    • 按照随机循环会停吗？
    • 其他的变种循环方式会停吗？
  • 以及，\(g\)和\(f\)像吗？
    • 就算在训练集\(D\)上想像，在\(D\)以外像吗？
    • 如果在\(D\)上不停的话，\(g\)和\(f\)的关系又会怎么样呢？

我们接下来试图证明，在一些情况下，循环过足够多次数后，PLA总会停下来。

Guarantee of PLA

线性可分

如果PLA能停下来，那么一个必要条件是数据集\(D\)允许某个\(\mathbf{w}\)不犯错误，此时我们称\(D\)为线性可分。

那么假设数据集\(D\)是线性可分的，PLA一定会停吗？

线性可分 \(\Leftrightarrow\) 存在一个完美的\(\mathbf w_f\)使得\(y_n = sign(\mathbf w_f^T \mathbf x_n)\). \(\mathbf w_f\)是完美的，因此每一个\(\mathbf x_n\)都完美地远离分界线： \[y_{n(t)}\mathbf w_f^T \mathbf x_{n(t)} > \min_n y_n\mathbf w_f^T \mathbf x_n > 0 \] 通过对于任意的错误\((x_{n(t)}, y_{n(t)})\)更新，我们有： \[ \begin{align} \mathbf{w}_f^T\cdot{\mathbf w_{t+1}} & = \mathbf w_f^T(\mathbf w_t + y_{n(t)}\mathbf x_{n(t)}) \\ & \ge \mathbf w_f^T\mathbf w_t + \min_{n}y_n\mathbf w_f^T\mathbf x_n \\ & > \mathbf{w}_f^T\mathbf{w}_t + 0 \end{align} \] 上面的结果实际上表明，每次纠正错误后，\(\mathbf{w}_f\)和\(\mathbf{w}_t\)的内积变大了。可能有两个原因：

  • \(\mathbf{w}_f\)和\(\mathbf{w}_t\)的夹角变小了。
  • \(\mathbf{w}_t\)的长度变大了。

我们当然希望是第一种情况发生了，这样我们就能说明\(\mathbf{w}_t\)在不断向\(\mathbf{w}_f\)靠近。那么我们如何说明呢？

我们还没有利用一个性质，那就是$_t $ 在 \((\mathbf{x}_{n(t)}, y_{n(t)})\)处犯了错误： \[ sign(\mathbf{w}_t^T\mathbf{x}_{n(t)}) \neq y_{n(t)} \Leftrightarrow y_{n(t)}\mathbf{w}_t^T\mathbf{x}_{n(t)} \le 0 \]

我们可以利用这个性质证明：\(\mathbf{w}_t\)其实变长的不太快，即使是关于最长的\(\mathbf{x}_n\)进行更新时： \[ \begin{align} {\|\mathbf{w}_{t+1}\|}^2 & = {\|\mathbf{w}_{t} +y_{n(t)} \mathbf{x}_{n(t)}\|}^2 \\ & = {\|\mathbf{w}_{t}\|}^2 + 2y_{n(t)}\mathbf{w}_{t}^T\mathbf{x}_{n(t)} + {\| y_{n(t)}\mathbf{x}_{n(t)} \|}^2 \\ & \le {\|\mathbf{w}_{t}\|}^2 + 0 + {\| y_{n(t)}\mathbf{x}_{n(t)} \|}^2 \\ & \le {\|\mathbf{w}_{t}\|}^2 + \max_n{\| y_n\mathbf{x}_n \|}^2 \\ & \le {\|\mathbf{w}_{t}\|}^2 + \max_n{\|\mathbf{x}_n \|}^2 \end{align} \] 如此一来，我们便排除了第二种情况，说明了随着循环次数的增长，\(\mathbf{w}_f\)和\(\mathbf{w}_t\)的夹角不断变小。

这里老师还留了一个有趣的小问题。从\(\mathbf{w}_{0}=\mathbf{0}\)开始，经过\(T\)次错误纠正，我们有： \[\frac{\mathbf{w}_f^T}{\|\mathbf{w}_f\|} \frac{\mathbf{w}_T}{\|\mathbf{w}_T\|} \ge \sqrt{T}\cdot{constant}\] 问这个\(constant\)应该是多少。 这个问题不算太难，通过上面的两个不等式，经过推导，我们可以得到： $$constant = \frac {\min_n y_{n}\mathbf{w}_f^T\mathbf{x}_n} {{\|\mathbf{w}_{f}\|}^2 \max_n {\|\mathbf{x}_n \|}^2}$$

Non-Seperable Data

上面我们证明了，只要我们的数据是线性可分，且每次都修正一个错误：

  • \(\mathbf{w}_f\)和\(\mathbf{w}_t\)的内积快速变大，而且\(\mathbf{w}_t\)的长度增长的不快
  • 也就是说：PLA这条线越来越接近\(\mathbf{w}_f\)直到停止

这样的好处是：实现很简单，对任何纬度\(d\)都work。

坏处是：

  • 不知道会不会停下来（因为不知道\(\mathbf{w}_f\)）。
  • 就算知道会停下来，也不知道多久会停下来（因为计算\(\rho\)需要用到\(\mathbf{w}_f\)）。

那如果我们的数据集不是线性可分的话，我们怎么办呢？也就是用噪声数据进行学习： 图2-5

假设噪声是“小”的，即大部分情况下\(y_n = f(\mathbf{x}_n)\)。 如果这样的话，那么我们也希望我们求得的\(g\)在大部分情况下有\(y_n = g(\mathbf{x}_n)\)。 于是，我们可以这样来求\(\mathbf{w}_g\)： \[\mathbf{w}_g \leftarrow \mathop{\arg\min}_{\mathbf{w}} \sum_{n=1}^{N}(y_n \neq sign(\mathbf{w}^T\mathbf{x}_n))\] 但是很不幸，这个问题被证明是NP-hard的。

那么既然不好找到精确解，我们能不能通过修改PLA来近似地找到一个还能接受的g呢？

Pocket Algorithm

把最好的那条线抓在手上。

  1. 初始化Pocket权重为\(\hat{\mathbf{w}}\)
  2. 对\(t = 0, 1, \cdots\)
    1. （随机）找到\(\mathbf{w}_t\)所犯的一个错误\((\mathbf(x)_{n(t)}, y_{n(t)})\)
    2. （尝试）通过以下方法修复错误： \[ \mathbf{w}_{t+1} \leftarrow \mathbf{w}_{t} + y_{n(t)}\mathbf{x}_{n(t)} \]
    3. 如果\(\mathbf{w}_{t+1}\)比\(\hat{\mathbf{w}}\)犯的错误还要少，那么我们用前者来替换后者。

直到经过了足够多次循环。 返回\(\hat{\mathbf{w}}\)（我们称为\(\mathbf{w}_{POCKET}\)）为我们所求的\(g\)。

已有理论能够证明，如果数据集线性可分，那么PLA可以做得很好；如果不线性可分，那么Pocket Algorithm将会做得还不错。

Summary

图2-6

图2-6