之前我们都是讨论的batch learning，就是给了一堆样例后，在样例上学习出假设函数 h。而在线学习就是要根据新来的样例，边学习，边给出结果。

假设样例按照到来的先后顺序依次定义为 $(x_1, y_1), (x_2, y_2), ...,(x_m, y_m)$。$x$ 为样本特征，$y$ 为类别标签。我们的任务是到来一个样例 $x$，给出其类别结果 $y$ 的预测值，之后我们会看到 $y$ 的真实值，然后根据真实值来重新调整模型参数，整个过程是重复迭代的过程，直到所有的样例完成。这么看来，我们也可以将原来用于批量学习的样例拿来作为在线学习的样例。

在在线学习中我们主要关注在整个预测过程中预测错误的样例数。

perception algorithm

首先给出感知器学习最简单的形式，也就是学习函数：

$h_{\theta}(x)=g\left(\theta^{T} x\right)$

其中 x 是 n 维特征向量，θ是 n+1 维参数权重。函数$g$用来将$\theta^T x$计算结果映射到-1和 1上，其中：

$g(z)=\left\{\begin{aligned}1 & \text { if } z \geq 0 \\-1 & \text { if } z<0\end{aligned}\right.$

我们只对分类错误的点进行更新，损失函数可以表示为：

$\min _{\theta} L(\theta)=-\sum_{x_{i} \in M} y_{i}(\theta^T x)$

可以得到更新公式为：

$\theta :=\theta+y x$

也就是说，如果对于预测错误的样例，$\theta$进行调整时只需加上(实际上为正例)或者减去(实际负例)样本特征$x$值即可。$\theta$初始值为向量 0。这里我们关心的是$\theta^Tx$的符号，而不是它的具体值。调整方法非常简单。然而这个简单的调整方法还是很有效的，它的错误率不仅是有上界的，而且这个上界不依赖于样例数和特征维度。

Block and Novikoff

该定理给出了感知机学习预测的错误样例数的上界：

给定按照顺序到来的$\left(x^{(1)}, y^{(1)}\right),\left(x^{(2)}, y^{(2)}\right), \ldots\left(x^{(m)}, y^{(m)}\right)$样例。假设对于所有的样例$\left\|x^{(i)}\right\| \leq D$，也就是说特征向量长度有界为$D$。更进一步，假设存在一个单位长度向量$u( || u||_ 2=1)$且使得$y^{(i)} \cdot\left(u^{T} x^{(i)}\right) \geq \gamma$。$u$能够有$\gamma$的间隔将正例和反例分开。

那么感知算法的预测的错误样例数不超过$(D/\gamma)^2$。

具体证明可见CS229，不再阐述。

可以发现，该定理与SVM非常像，如果我们把$D$认为是几何间隔，定理描述的就是在线性可分的情况下最大化几何间隔的分类错误数。