从最简单最基础的二分类问题出发,演示一个简单机器学习算法PLA的完整过程,见详细课件。
The Learning Problem:
takes
and
to get
that approximate target function
.
这节课foucus在Hypothesis Set,用Perceptron(linear binary classifiers)演示如何解决二分类问题。如根据用户age/salary/等特征判定是否发放信用卡。
算法形式极其简洁,权重x特征,大于零正例;小于零负例。
算法迭代步骤,关键点是有错才改:
最重要的是当发现误分类点时,更新权重:
ml-foundations-pla-intuition
最直观的Intutiton,每一步更新如何使结果更好?
: 误分则
和
夹角大于90度,更新
后使其往
靠近,夹角变小
: 误分则
和
夹角小于90度,更新
后使其离
更远,夹角变大
PLA算法有前提是数据集线性可分。
线性可分: Exists perfect
such that
如果数据集线性可分,能保证算法收敛吗?如何证明?思路是
完美分开数据集
至少线性增加
长度无法达到线性增加
会收敛到
Inner product of
and
grows fast; length of
grows slowly. PLA ‘lines’ are more and more aligned with
then halts.
因为
将每个数据都正确分类,所以:
利用归纳法容易得到:
证明每次迭代,其內积至少是线性增长。內积大一定程度上反映两个向量夹角更接近,当然还需要考虑其长度。
考虑向量长度:
其中:
可以看到,向量长度增加速度为
,达不到线性。且
长度固定,综合上面两个结论:
最后推论出
存在上界:
PLA只能处理线性可分数据集,Pocket PLA稍微改进:
If
makes fewer mistakes than
, replace
by
.
数据集不可分情况下也能保证找到较优的解。