02 Learning to Answer Yes/No

从最简单最基础的二分类问题出发，演示一个简单机器学习算法PLA的完整过程，见详细课件。

回顾

The Learning Problem:

A

takes

D

and

H

to get

g

that approximate target function

f

.

这节课foucus在Hypothesis Set，用Perceptron(linear binary classifiers)演示如何解决二分类问题。如根据用户age/salary/等特征判定是否发放信用卡。

PLA算法

算法形式极其简洁，权重x特征，大于零正例；小于零负例。

h(x) = sign(w^Tx)

算法迭代步骤，关键点是有错才改：

• 初始化

\textbf w_0 = \textbf 0

• 找一个误分类点

y_n \textbf w_t^T \textbf x_n < 0

• 更新权重

\textbf w_{t+1} = \textbf w_t + y_n\textbf x_n

• 直到没有误分类点，返回

\textbf w

最重要的是当发现误分类点时，更新权重：

\textbf w_{t+1} = \textbf w_t + y_n\textbf x_n

Intuition

ml-foundations-pla-intuition

最直观的Intutiton，每一步更新如何使结果更好？

y = +1

: 误分则

\textbf w

和

\textbf x

夹角大于90度，更新

\textbf w

后使其往

\textbf x

靠近，夹角变小

y = -1

: 误分则

\textbf w

和

\textbf x

夹角小于90度，更新

\textbf w

后使其离

\textbf x

更远，夹角变大

收敛性证明

PLA算法有前提是数据集线性可分。

线性可分: Exists perfect

\textbf w_f

such that

y_n=sign(\textbf w_f^T\textbf x_n)

如果数据集线性可分，能保证算法收敛吗？如何证明？思路是

• 假设目标

\textbf w_f

完美分开数据集

• 证明每一轮

\textbf w_f^T \textbf w_t

至少线性增加

• 证明每一轮

\textbf w_t

长度无法达到线性增加

• 其夹角会递减，有限迭代后，

\textbf w_t

会收敛到

\textbf w_f

Inner product of

\textbf w_f

and

\textbf w_t

grows fast; length of

\textbf w_f

grows slowly. PLA ‘lines’ are more and more aligned with

\textbf w_f

then halts.

因为

\textbf w_f

将每个数据都正确分类，所以：

y_n\textbf w_f^Tx_n \ge min_{n\in[1, N]} y_n\textbf w_f^Tx_n = \rho > 0

利用归纳法容易得到：

\begin{split} \textbf w_f^T \textbf w_t & = \textbf w_f^T \textbf w_{t-1} + y_n \textbf w_f^T\textbf x_n \\ & \ge \textbf w_f^T \textbf w_{t-1} + \rho \\ & \ge t\rho \end{split}

证明每次迭代，其內积至少是线性增长。內积大一定程度上反映两个向量夹角更接近，当然还需要考虑其长度。

考虑向量长度：

\begin{split} ||\textbf w_t||^2 &= ||\textbf w_{t-1}||^2 + 2y_n\textbf w_{t-1}\textbf x_n + ||y_n\textbf x_n||^2 \\ &\le ||\textbf w_{t-1}||^2 + R^2 \\ &\le tR^2 \end{split}

其中：

R = max_{n\in[1, N]}||\textbf x_n||

可以看到，向量长度增加速度为

\sqrt t

，达不到线性。且

\textbf w_f

长度固定，综合上面两个结论：

\frac {\textbf w_f^T \cdot \textbf w_t}{||\textbf w_f|| \cdot ||\textbf w_t||} \ge \frac{\rho \sqrt t}{R ||\textbf w_f||}

最后推论出

t

存在上界：

t \le \frac {R^2 ||\textbf w_f||^2}{\rho^2}

PLA改进

PLA只能处理线性可分数据集，Pocket PLA稍微改进：

If

\textbf w_{t+1}

makes fewer mistakes than

\textbf w_{t}

, replace

\textbf w_{t+1}

by

\textbf w_{t+1}

.

数据集不可分情况下也能保证找到较优的解。