在线学习

更新于 分类： 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 11 分钟

机器学习算法可以分成两类。离线学习和在线学习。在线机器学习指每次通过一个训练实例学习模型的学习方法。

Gama J, Žliobaitė I, Bifet A, et al. A survey on concept drift adaptation[J]. ACM computing surveys (CSUR), 2014, 46(4): 44.
Shalev-Shwartz S. Online learning and online convex optimization[J]. Foundations and Trends® in Machine Learning, 2012, 4(2): 107-194.
Žliobaitė I, Pechenizkiy M, Gama J. An overview of concept drift applications[M]//Big data analysis: new algorithms for a new society. Springer, Cham, 2016: 91-114.

A Gentle Introduction to Concept Drift in Machine Learning

Concept Drift:

I. 离线学习与在线学习

We can distinguish two learning modes: offline learning and online learning.

I.I. 离线学习

In offline learning the whole training data must be available at the time of model training. Only when training is completed the model can be used for predicting.

不同理解方式：

  • 也称批量学习（batch learning）：一个batch训练完才更新权重，这样的话要求所有的数据必须在每一个训练操作中（batch中）都是可用的，这样不会因为偶然的错误把网络带向极端。在监督学习的批量方法中，多层感知器的突出权值的调整在训练样本集合的所有N个例子都出现后进行，这构成了训练的一个回合。换句话说，批量学习的代价函数是由平均误差能量定义的。多层感知器的突触权值的调整是以回合-回合为基础的。相应地，学习曲线的一种实现方式是通过描绘平均误差能量对回合数的图形而得到，对于训练的每一个回合，训练样本集合的样例是随机选取的。学习曲线通过对足够大量的这样实现的总体平均来计算，这里每次实现是在随机选取不同初始条件下完成的。这一特点符合交叉验证的规律，实验中的实验集、验证集、测试集一般都是批量处理的典例。
    • 只有训练完成了之后，模型才能被拿来用。简而言之，先训练，再用模型，不训练完就不用模型。
  • 你有一个样本，你把第一条带入训练，调整权重，然后带入下一条，直至跑完整个样本，这个时候的误差率可能不让你满意，于是你把整个样本又做了上述操作，直到误差很小。 
    1
    2
    3
    4
    5
    6
    initialize all weights to random value
    repeat:
      for t in training_set:
        compute train_error for t
        adjust weights base on train_error
    until error rate is very small or error rate variation stops

优点：

  1. 消除样本顺序的影响
  2. 对梯度向量的精确估计，因此，在简单条件下，保证了这一方法最速下降到局部极小点的收敛性。
  3. 学习的并行性。

缺点：

  1. 有着存储需求

I.II. 在线学习

不同理解方式：

  • online and batch learning：在线算法按照顺序处理数据，一个数据点训练完了直接更新权重。它们产生一个模型，并在把这个模型放入实际操作中，而不需要在一开始就提供完整的训练数据集。随着更多的实时数据到达，模型会在操作中不断地更新。In contrast, online algorithms process data sequentially. They produce a model and put it in operation without having the complete training data set available at the beginning. The model is continuously updated during operation as more training data arrives. Less restrictive than online algorithms are incremental algorithms that process input examples one by one (or batch by batch) and update the decision model after receiving each example. Incremental algorithms may have random access to previous examples or representative/selected examples. In such a case, these algorithms are called incremental algorithms with partial memory. Typically, in incremental algorithms, for any new presentation of data, the update operation of the model is based on the previous one. Streaming algorithms are online algorithms for processing high-speed continuous flows of data. In streaming, examples are processed sequentially as well and can be examined in only a few passes (typically just one). These algorithms use limited memory and limited processing time per item.
    • 通常来讲，一种Online learning算法对于一个序列进行一系列处理可以分为三步1：第一步，算法获得一个训练实例；第二步，算法预测训练实例的类别；第三步，算法获得正确类别，并根据预测类别与正确类别更新模型假设。
    • 我们无法得知这一次的更新权重是正确的还是错误的，如果恰恰是错误的一次更新，那么我们的模型会有可能渐渐地走向错误方向，残差出现。
  • 你有一个样本，你把第一条带入训练，调整权重，再把这一条带进去一次，重复多次，直至误差率很小，然后再带入下一条，直至跑完整个样本。 
    1
    2
    3
    4
    5
    6
    initialize all weights to random value
      for t in training_set:
        repeat:
        compute train_error for t
        adjust weights base on train_error
      until error rate is very small or error rate variation stops

在监督学习的在线方法下，对于多层感知器突触权值的调整是以样例-样例为基础的，用来最小化的代价函数是全体瞬时误差能量。和批量学习一样，在线学习的学习曲线是通过足够大量的随机选取的初始条件上的总体平均来计算的。对于给定的网络结构，在线学习下获得的学习曲线和批量学习下获得的学习曲线有着很大的不同。

给定训练样本以随机的方式呈现给网络，在线学习的使用使得在多维权值空间中的搜索事实上是随机的；正是由于这个原因，在线学习方法有时被称为随机方法。

优点：

  1. 容易执行
  2. 对于大规模和困难模式分类问题它提供有效解。
  3. 随机性使得不容易陷入局部极值点
  4. 存储量少得多

II. 增量式算法

增量式算法就是每当新增数据时，并不需要重建所有的知识库，而是在原有知识库的基础上，仅做由于新增数据所引起的更新，这更加符合人的思维原理。一个增量学习算法应同时具有以下特点：

  • 可以从新数据中学习新知识；
  • 以前已经处理过的数据不需要重复处理；
  • 每次只有一个训练观测样本被看到和学习；
  • 学习新知识的同时能保存以前学习到的大部分知识；
  • —旦学习完成后训练观测样本被丢弃；
  • 学习系统没有关于整个训练样本的先验知识；

III. 减量式算法

decremental learning，即抛弃“价值最低”的保留的训练样本。这两个概念在incremental and decremental svm这篇论文里面可以看到具体的操作过程。

Cauwenberghs G, Poggio T. Incremental and decremental support vector machine learning[C]//Advances in neural information processing systems. 2001: 409-415.
Gâlmeanu H, Andonie R. Implementation issues of an incremental and decremental SVM[C]//International Conference on Artificial Neural Networks. Springer, Berlin, Heidelberg, 2008: 325-335.

IV. 实例

两种典型在线机器学习算法：Perceptron、MIRA，他们都属于线性分类算法族，它们具有相同的模型形式。在学习阶段，算法对于每个类别，通过训练数据估计一个参数向量w。在推理阶段，算法在给定一组参数向量w和数据x的条件下，以w和x的乘积作为数据与该类的相似度度量。

IV.I. 在线学习的二值分类

机器学习番外篇之在线学习(I):Online Learning与感知器

假设样例按照到来的先后顺序依次定义为\(((x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\cdots,(x^{(m)},y^{(m)}))\)。\(X\)为样本特征，\(y\)为类别标签。我们的任务是到来一个样例\(x\)，给出其类别结果\(y\)的预测值，之后我们会看到\(y\)的真实值，然后根据真实值来重新调整模型参数，整个过程是重复迭代的过程，直到所有的样例完成。

我们的假设函数为:

\[ \begin{equation} h_{\theta}(x) = g(\theta^T x) \end{equation} \]

其中\(x\)是\(n+1\)维特征向量,最后一维为常量\(1\)，\(\theta\)是\(n+1\)维参数权重,最后一维表示Bias。函数\(g\)用来将\(\theta^Tx\)计算结果映射到\(-1\)和\(1\)上。具体公式如下：

\[ \begin{equation} \begin{split} g(z) = \left \lbrace \begin{array}{cc} 1 & \text{if} \ z \geq 0 \\ -1 & \text{if} \ z < 0 \end{array} \right. \end{split} \end{equation} \]

这个也是logistic回归中\(g\)的简化形式。

现在我们提出一个在线学习算法如下：

新来一个样例\((x,y)\)，我们先用从之前样例学习到的\(h_{\theta}(x)\)来得到样例的预测值\(y\)，如果\(h_{\theta}(x) = y\)（即预测正确），那么不改变\(\theta\)，反之

\[ \begin{equation} \theta := \theta + yx \end{equation} \]

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

下面定理阐述了错误率上界：

定理（Block and Novikoff）: 给定按照顺序到来的\((x^{(1)},y^{(1)}),(x^{(2)},y^{(2)},\cdots,(x^{(m)},y^{(m)}))\)样例。假设对于所有的样例\(||x^{(i)} \leq D\)，也就是说特征向量长度有界为\(D\)。更进一步，假设存在一个单位长度向量\(u\)且\(y^{(i)}(u^Tx^{(i)})\geq \gamma\)。也就是说对于\(y=1\)的正例，\(u^Tx^{(i)} \geq \gamma\)，反例\(u^Tx^{(i)} \leq -\gamma\)，\(u\)能够有\(\gamma\)的间隔将正例和反例分开。那么感知算法的预测的错误样例数不超过\(({D \over \gamma})^2\)。

根据对SVM的理解，这个定理就可以阐述为：如果训练样本线性可分，并且几何间距至少是\(\gamma\)，样例样本特征向量最长为\(D\)，那么感知算法错误数不会超过\(({D \over \gamma})^2\)。这个定理是62年提出的，63年Vapnik提出SVM，可见提出也不是偶然的，感知算法也许是当时的热门。

定理证明

感知算法只在样例预测错误时进行更新，定义\(\theta^{(k)}\)是第\(k\)次预测错误时使用的样本特征权重，\(\theta^{(1)} = \vec{0}\) 初始化为\(\vec{0}\)向量。假设第\(k\)次预测错误发生在样例\((x^{(i)},y^{(i)})\)上，利用\(\theta^{(k)}\)计算\(y^{(i)}\)值时得到的结果不正确。也就是说下面的公式成立：

\[ \begin{equation} (x^{(i)})^T\theta^{(k)}y^{(i)} \leq 0 \end{equation} \]

根据感知算法的更新方法，我们有\(\theta^{(k+1)} = \theta^{(k)} + y^{(i)}x^{(i)}\)。这时候，两边都乘以\(u\)得到:

\[ \begin{equation} \begin{split} (\theta^{(k+1)})^Tu &= (\theta^{(k)})^u + y^{(i)}(x^{(i)})^Tu \\ &\geq (\theta^{(k)})^Tu + \gamma \end{split} \end{equation} \]

这个式子是个递推公式，就像等差数列一样\(f_{n+1}=f_n+d\)。由此我们可得

\[ \begin{equation} (\theta^{(k+1)})^Tu \geq k\gamma \end{equation} \]

因为初始\(\theta\)为\(\vec{0}\)。

下面我们利用前面推导出的\((x^{(i)})^T\theta^{(k)}y^{(i)} \leq 0\)和\(||x^{(i)}|| \leq D\)得到

\[ \begin{equation} \begin{split} ||\theta^{(k+1)}||^2 &= ||\theta^{(k)} + y^{(i)}x^{(i)}||^2 \\ &= ||\theta^{k}||^2 + ||x^{(i)}||^2 + 2y^{(i)}(x^{(i)})^T\theta^{(i)} \\ &\leq ||\theta^{k}||^2 + ||x^{(i)}||^2 \\ &\leq ||\theta^{k}||^2 + D^2 \end{split} \end{equation} \]

也就是说\(\theta^{(k+1)}\)的长度平方不会超过\(\theta^{(k)}\)与\(D\)的平方和。

又是一个等差不等式，得到：

\[ \begin{equation} ||\theta^{k+1}||^2 \leq kD^2 \end{equation} \]

两边开根号得：

\[ \begin{equation} \begin{split} \sqrt{k}D & \geq ||\theta^{(k+1)}|| \\ & \geq (\theta^{(k+1)})^Tu \\ & \geq k\gamma \end{split} \end{equation} \]

其中第二步可能有点迷惑，我们细想\(u\)是单位向量的话:

\[ \begin{equation} z^Tu = ||z||||u||cos \phi \leq ||z||||u|| \end{equation} \]

因此上面的不等式成立，最后得到：

\[ \begin{equation} k \leq (D/\gamma)^2 \end{equation} \]

也就是预测错误的数目不会超过样本特征向量\(x\)的最长长度除以几何间隔的平方。实际上整个调整过程中\(\theta\)就是\(x\)的线性组合。

V. 代码资源

  1. 浅谈在线机器学习算法↩