专栏首页用户2133719的专栏CS229 课程笔记之八:在线学习

CS229 课程笔记之八:在线学习

1 在线学习

之前我们讨论的学习都是「批量学习」(batch learning)。批量学习的特点是我们会基于一个训练集进行学习,然后在独立的测试数据上评估学习得到的假设

h

。本节将讨论「在线学习」(online learning)。

在线学习的特点是算法需要在学习时「实时」进行预测。在线学习的过程如下:

首先,一个样本序列

(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\ldots, (x^{(m)},y^{(m)})

会按顺序输入算法;算法依次对每一个样本作出预测,然后使用真实值进行修正。具体来说,算法首先会看到

x^{{(1)}}

,然后被要求预测

y^{(1)}

的值,预测完成后

y^{(1)}

的真实值会暴露给算法,对模型进行修正;然后,算法会看到

x^{(2)}

,同样被要求进行预测,重复上一步的操作,直至到达

(x^{(m)},y^{(m)})

我们关心的是在线学习在整个过程中产生的误差数量。因此,在线学习是对算法需要在学习过程中进行预测的应用的建模。

2 感知器与大间隔分类器

下面将给出感知器算法的在线学习误差数量的上界。为了简化推导,这里将分类标签定义为

y \in \{-1,1\}

我们知道感知器算法的参数

\theta \in \mathbb{R}^{n+1}

,其假设函数为:

h_\theta(x)= g(\theta^Tx) \tag{1}

其中:

g(z)=\left\{ \begin{align*} & 1 \quad \text{if} \;\text{z} \ge 0\\ & -1 \quad \text{if} \;\text{z} < 0 \end{align*} \right.

给定一个训练样本

(x,y)

,感知器算法的学习规则如下:

如果

h_\theta(x) = y

,那么参数不发生变化,否则:

\theta := \theta + yx

该规则与第二章的相比有所不同,因为这里分类标签为

\{-1,1\}

。此外,学习速率被省略了,这只会影响到参数的大小,对算法本身的行为没有影响。

下面的定理将给出感知器算法在线学习误差数量的上界。当其作为在线算法运行时,每一次得到分类样本错误的时候会进行一次更新,注意下面给出的误差数量上界与序列样本数量

m

和输入维度

n

并没有直接关系。

「定理(Block, 1962, and Novikoff, 1962)」

给定一个样本序列

(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\ldots, (x^{(m)},y^{(m)})

,假设对于所有的样本,都有

||x^{(i)}|| \le D

(欧几里得范数),并且存在一个单位长度向量

u

||u||= 1

),使得对于所有样本都有:

y^{(i)} \cdot (u^Tx^{(i)}) \ge \gamma

成立,即

u

将数据以至少为

\gamma

的间隔分离,具体来说,当

y^{(i)} = 1

u^{T} x^{(i)} \geq \gamma

;当

y^{(i)}=-1

u^{T} x^{(i)} \leq-\gamma

。那么感知器算法对于该序列的总预测误差数量最多为

(D/\gamma)^2

「证明」

感知器只有当发现错误时才会更新参数,定义

\theta^{(k)}

为出现第

k

个错误时的权重。那么有

\theta^{(1)}=\vec 0

(因为权重初始化为 0)。

如果第

k

个错误出现时的样本为

(x^{(m)},y^{(m)})

,那么

g((x^{(i)})^T\theta^{(k)}) \ne y^{(i)}

,即:

(x^{(i)})^T\theta^{(k)}y^{(i)} \le 0 \tag{2}

根据感知器算法的学习规则,我们有

\theta^{(k+1)} = \theta^{(k)}+ y^{(i)}x^{(i)}

,据此有:

\begin{align*} (\theta^{(k+1)})^Tu &= (\theta^{(k)})^Tu+ y^{(i)}(x^{(i)})^Tu \\ &\ge (\theta^{(k)})^Tu+ \gamma \end{align*}

通过一个简答的数学归纳法证明,可以得到:

(\theta^{(k+1)})^Tu \ge k\gamma \tag{3}

此外,我们还有:

\begin{align*} ||\theta^{(k+1)}||^2 &= || \theta^{(k)}+ y^{(i)}x^{(i)}||^2 \\ &= ||\theta^{(k)}||^2 + ||x^{(i)}||^2 + 2(x^{(i)})^T\theta^{(k)}y^{(i)} \\ &\le ||\theta^{(k)}||^2 + ||x^{(i)}||^2 \\ &\le ||\theta^{(k)}||^2 + D^2 \tag{4} \end{align*}

第三步使用了公式 (2) 的结论。基于数学归纳法可以得到:

||\theta^{(k+1)}||^2 \le kD^2 \tag{5}

将 (3) 和 (5) 式结合起来可以得到:

\begin{align*}\sqrt k D &\ge ||\theta^{(k+1)}|| \\&\ge (\theta^{(k+1)})^Tu \\&\ge k\gamma\end{align*}

第二步的推导来自于

z^Tu = ||z||\cdot ||u||\,cos\phi \le ||z||\cdot||u||

因此,如果感知器算法发现了第 k 个错误,可以证明

k \le (D/\gamma)^2

3 思维导图

本文分享自微信公众号 - 口仆(roito33),作者:口仆

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CS229 课程笔记:机器学习的实用建议

    对于一个学习算法,有着各种各样的调试手段,不同的调试手段可以解决不同的问题,需要根据实际情况进行选择。学习算法的问题大致可以分为两类:「高偏差/方差」问题以及「...

    口仆
  • Playing Atari with Deep Reinforcement Learning

    本文是对 DQN 原始论文 Playing Atari with Deep Reinforcement Learning 的详细解读。

    口仆
  • CS229 课程笔记之九:EM 算法与聚类

    为了证明 k-means 算法能否保证收敛,我们定义「失真函数」(distortion function)为:

    口仆
  • 机器学习在自动驾驶方面的应用

    概要:不同的自动驾驶算法。 来源:雷锋网 将汽车内外传感器的数据进行融合,借此评估驾驶员情况、进行驾驶场景分类,都要用到机器学习。本文中,我们讲解了不同的自动驾...

    IT派
  • 机器学习算法在自动驾驶领域的应用大盘点!

    AI 研习社按:本文原载于 kdnuggets,由林立宏、吴楚编译。 将汽车内外传感器的数据进行融合,借此评估驾驶员情况、进行驾驶场景分类,都要用到机器学习。本...

    AI研习社
  • 机器学习算法在自动驾驶领域的应用大盘点!

    AI科技评论按:本文原载于 kdnuggets,由林立宏、吴楚编译。 将汽车内外传感器的数据进行融合,借此评估驾驶员情况、进行驾驶场景分类,都要用到机器学习。本...

    AI科技评论
  • 深度 | Pedro Domingos解析机器学习五大流派中的算法精髓

    Pedro Domingos是华盛顿大学计算机科学与工程学教授,也是国际机器学习协会的联合创始人之一。他曾在IST Lisbon获得电子工程和计算科学的硕士学位...

    AI科技评论
  • 算法(1)

    Dwyane
  • 机器学习 刀光剑影 之屠龙刀

    机器学习是一个大武林,这里面江湖人士颇多,“发明”出来的算法兵器也是五花八门,浩瀚如海,足够你数上三天两夜了。然而,这些兵器行走江湖能用的不多,真正无敌的更是屈...

    腾讯大数据
  • 机器学习-常用的机器学习算法

    谷歌的自动驾驶汽车和机器人得到了很多新闻,但该公司真正的未来是机器学习,这种技术使计算机变得更聪明,更个性化。 - Eric Schmidt(谷歌主席)

    亚乐记

扫码关注云+社区

领取腾讯云代金券