加载中…
个人资料
微博
  • 博客等级：
  • 博客积分：
  • 博客访问：
  • 关注人气：
  • 获赠金笔：0支
  • 赠出金笔：0支
  • 荣誉徽章：
正文 字体大小：大 中 小

几种机器学习的方法-supervise,unsupervise,self-taught,online,semi

(2014-12-10 12:29:41)
标签：

股票

 分类： ML_DL

在andrew Ng的视频中提到了下面三种learning模式:

Stochastic learning：每次处理一个ｔｒａｉｎｉｎｇ数据

batch learning:　所有的ｔｒａｉｎｉｎｇ数据一次处理。

mini-batch learning ：一次处理一个ｍｉｎｉ－ｂａｔｃｈ　ｓｉｚｅ的数据比如１０笔。
但是在以上的三种学习模式中，在学习开始之前，所有的ｔｒａｉｎｉｎｇ的数据都是ｒｅａｄｙ的。

online learning ：training 数据来自于网络，在学习开始的时候，并不是所有的training都是ready的，而是等待网络输入。在线学习的一个主要限制是当前只能看到当前的和过去的数据，未来是未知，有可能完全颠覆现在的认知。因此，对在线学习而言，它追求的是知道所有数据时所能设计的最优策略。同这个最优策略的差异称之为后悔（regret）：后悔没能一开始就选对最优策略。我们的希望是，时间一久，数据一多，这个差异就会变得很小。因为不对数据做任何假设，最优策略是否完美我们不关心（例如回答正确所有问题）。我们追求的是，没有后悔（no-regret）。

如果与统计学习一样对数据做独立同分布假设，那么在线学习里的最优策略就是在得知所有数据的离线学习所能得到最优解。因此在线学习可以看成是一种优化方法：随着对数据的不断访问来逐步逼近这个离线最优解。online learning是一个Stochastic learning.

http://s3/mw690/002mfkyxgy6P7z03tVE32&690

从上面的图中可以看到，batch learning的梯度是垂直于轮廓线的，而online learning因为是一个输入一个输入的处理的，因此梯度是垂直于水平和垂直最陡的梯度方向做zig-zag的。但是最终也是会收敛到优化点。但是online learning在有些情况下的学习速度是很慢的，因为它不是直接朝着优化点去的，而是一直在震荡向前。

http://s6/mw690/002mfkyxgy6P7z5oFSt45&690

漫谈在线学习：专家问题


从训练数据的类型来分类：
supervise learning
unsupervise learning
self-taugh : 数据中包含标注和未标注的数据，这两种数据可以来自于不同的分布 ，比如从网上随机找来的数据(UFLDL中有解释)
semi-supervise： 标注的数据和未标注的数据必须来自于同一个分布
  比如当前正在区分汽车和摩托车，self-taught的图片可以从网上下载，里面有些未标注的图片可以不是汽车也不是摩托车；但是semi-supervise要求的未标注的图片必须是车或者摩托车，只不过是没有给出标注而已。
online learning ：training 数据来自于网络，在学习开始的时候，并不是所有的training都是ready的，而是等待网络输入。



Stochastic versus Batch learning

一. Pros of Stochastic Learning

  1. 学习过程比Batch Learning快 
    假设样本集中有10个样本，然后每个样本生成9个自身的copy，这样就有100个样本。 Stochastic只需要10个样本就完成了一个epoch。 而Batch则需要计算100个样本才能完成一次epoch(而且其中90次是无用的计算)
  2. 学习的效果一般比较好 
    因为Stochastic的过程比较振荡，容易跳过一些局部最小值，找到更好的局部最小值。而Batch在初始参数定了以后其最终的局部最小值就定了
  3. 可以用来跟踪学习样本的变化 
    样本的变化，会立即反应到训练中，这也是其另一个名字Online Lerning的由来

二. Pros of Batch Learning

  1. 学习的过程比较平稳 
    Batch的学习过程比较平稳，容易收敛，而Stochastic比较振荡，因此一般Stochastic的学习率都比较小。可以采用mini-batch来折衷，既可以跳过局部最小，也可以相对平稳
  2. 一些加速算法只能用在Batch模式下(如:conjugate gradient，hessian-based) 
    可以现基于训练集学习得到一些加速算法需要的参数，再应用到Stochastic方法中，但是在Online就不行了(因为没有提前准备好的数据集)。

Batch Versus On-line Learning

The on-line and batch modes are slightly different, although both will perform well for parabolic performance surfaces. One major difference is that the batch algorithm keeps the system weights constant while computing the error associated with each sample in the input. Since the on-line version is constantly updating its weights, its error calculation (and thus gradient estimation) uses different weights for each input sample. This means that the two algorithms visit different sets of points during adaptation. However, they both converge to the same minimum.Note that the number of weight updates of the two methods for the same number of data presentations is very different. The on-line method (LMS) does an update each sample, while batch does an update each epoch, that is,LMS updates = (batch updates) x (# of samples in training set).The batch algorithm is also slightly more efficient in terms of number of computations


from http://yjliu.net/blog/2012/07/14/a-brief-talk-about-online-learning.html

浅谈在线机器学习算法

前言

这篇博客的内容基本是我本科毕设论文的第二章。 其中包括从毕设开始到现在，关于在线机器学习算法的一些粗浅的理解、算法的一些性质的证明以及算法如何从分类问题迁移到结构化预测问题，有些内容我也比较模糊，还有些内容太过繁琐，读者尽可能选择自己愿意接受的内容看，其他略过就好。

 

机器学习的回顾

机器学习是人工智能的一个分支。抽象讲，机器学习理论主要是设计和分析一些让计算机可以自动__“学习”__的算法。 机器学习算法是一类从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。

通常来讲，机器学习分为__学习__以及__推理__两个阶段。在学习阶段，机器学习算法从数据中自动分析获取规律；在推理阶段，算法利用学习阶段学习到的规律对未知数据进行预测。

序列标注问题

在现实世界中，我们处理的某些机器学习任务，其面对的数据往往是序列性的。 在一个已知的类别体系下，算法需要对数据序列中的每个元素标注类别。 例如，中文分词任务需要给字序列中的每个字标“词首”、“词中”、“词尾”、“单字成词”四类中的某一类，词性标注任务需要将词序列中每个词标注一个已知词性集合下的词性。

结合之前关于机器学习的定义，可以将序列标注问题按如下方式定义，根据已知的序列性数据，学习一个假设h，并在这个假设h给定的条件下，预测某些未知序列性数据的序列标注。

形式化地，在给定一个序列性训练数据的集合 (wi[1:n],ti[1:n])的条件下，算法在学习阶段，从数据中学习一个假设h；在推理阶段，对于一个未知标注的序列w[1:n]，计算z[1:n]=h(w[1:n])。下面的讨论都会沿用这里对于序列和标注的形式化定义。

在线机器学习

(并不是指在网上授课机器学习课程)

在机器学习领域，在线机器学习(Online learning)指每次通过一个训练实例学习模型的学习方法。 Online learning的目的是正确预测训练实例的标注。其最重要的一个特点是当一次预测完成时，其正确结果便被获得，这一结果可直接用来修正模型。 通常来讲，一种Online learning算法对于一个序列进行一系列处理可以分为三步：第一步，算法获得一个训练实例；第二步，算法预测训练实例的类别；第三步，算法获得正确类别，并根据预测类别与正确类别更新模型假设。

下面介绍两种典型在线机器学习算法Perceptron、MIRA，他们都属于线性分类算法族。 介绍这两种算法在分类问题中如何从训练实例中学习模型参数，两种算法的收敛性。 同时介绍如何将这两种算法应用于解决序列标注问题。

线性分类族

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

Perceptron

Perceptron一种有监督线性分类算法。算法将输入的实例分为正例、负例两类。在学习结果，算法从训练数据中实例估计w。推理阶段，算法基于特征向量x与参数向量w乘积的符号对于输入数据的类别进行预测。

算法流程与收敛性

推理阶段，算法接受一个输入实例x，并根据权向量w确定其类别。设输入x是一个D维实向量，w是模型的权重向量，也是D维实向量。二元感知器按照输出函数wTx将输入x分为两类。将wTx>0的实例x分为正例；反之，分为负例。

学习阶段，根据给定训练数据，感知器算法所学习的是模型的权重向量w，其学习算法下面所示。

初始化权向量w为0，不失一般性，可以假设所有训练实例是单位向量。并置迭代次数t为1。利用感知器模型，对x的类别进行预测。如果wtx>0，x是正例；否则，是负例。在判断正负例出错时，
  • 将正例判成负例时，w(t+1)←w(t)+x
  • 将负例判成正例时，w(t+1)←w(t)−x

训练算法迭代T轮，每轮迭代中枚举所有训练实例，按照推理阶段使用的方法预测训练实例类别。如果预测出错，则更新权重。直观上讲，算法给正确的分类的权向量增加，给错误分类的权向量减少。

可以证明上面的算法在训练数据线性可分以及线性不可分的情况下都是收敛的。 在线性可分情况下，具体证明思路设一个理想的分类界面w∗，再定义一个margin γ=min|w∗x|||x||。 然后证明随着迭代次数的增加，出错次数的下届增长得不是太慢，上届不是增长得不是太快，最后得到出错次数的一个界，也就证明了算法的收敛性。 具体可以看这里。

对于线性不可分的情况，证明方法是把不可分的数据“拉”到符合w∗和γ的位置。 由于这个“拉”的代价是一个有界的值TD_{\gamma}$，在推导收敛性时，考虑这个值，其余的模仿线性可分的情况就好了。

MIRA

如前文所述，线性分类算法可以将实例分为二类。但是，实际问题面对的类别个数往往多于二类，需要将模型从二类问题推广到多类问题。

一种可行的将二类推广到多类的方法是”one-against-rest strategy”。这一策略将k类分类问题转化为k个二类分类问题。第r个二类分类器完成将训练实例分为是r类和不是r类两类。多于第r个类别的线性分类器，以其权向量wr与训练实例x的乘积作一种相似度度量。如果训练实例x的范数为1，那么，这一乘积可以从几何意义上解释为训练实例到类r的分类面的距离。之前江枫师兄说：“一般认为离分类面r越远的数据点，其属于r类的可能性就越大。”实际使用online算法处理多类问题时，也把和数据点x乘积最大的wr作为x的类别。

MIRA算法也是一种有监督在线机器学习算法，与perceptron相似，MIRA算法也是一种线性分类算法。在使用MIRA解决分类问题时，算法从训练实例中学习一个k行的参数矩阵M，其中第r行Mr表示第r类的参数向量。

算法流程与收敛性

在推理阶段，算法计算训练实例x和各类参数向量的乘积，作为该训练实例与该类的相似度。并将相似度最高的一类作为对训练实例类别的预测。

在学习阶段，算法流程如下

  1. 对于k类分类问题，设由各类权向量组成的矩阵M。其中M有k行，第r行向量Mr对应第r类的分类权向量。
  2. 从1到T循环每个训练实例xt
    • 对于每个训练实例xt，依照y=argrmaxMrx预测xt的类别。
    • 依照下面的优化目标和约束条件： obj. minτ12∑r||Mr+τrx(t)||2
      st.(1)τr≤σx,yt
      (2)∑τr=0
  3. 依照M(t+1)r=M(t)r+τrxt更新M

MIRA的收敛性证明要比perceptron复杂，但是思路也是证明“出错次数的下届增长得不是太慢，上届不是增长得不是太快”。如果感兴趣，可以看Crammer的Ultraconservation Online Algorithms for Multiclass Problems

从分类问题到序列标注问题

如之前对于序列标注问题的描述，假如序列长度为n，有k个类别，那么这个序列就存在nk种标注。 所以，在推理阶段将y=argrmaxMrxt换成z[1:ni]=argmaxu[1:ni]∈Tni∑sαsΦs(wi[1:ni],u[1:ni])，也就是将用分类面判断类别变成求序列的最优标注。 这样序列标注问题就转化为分类问题了。

当然，对于用perceptron处理序列标注问题来讲，直接用viterbi求一个最优标注并用这个最优标注和标准结果更新参数就好了。 但是，我们注意到MIRA在用一个训练实例更新参数时，实际对于各个类别都进行了更新。而序列标注问题的类别数是指数级别，对每个类别都更新显然是不现实的。 McDonald在Online Large-Margin Training of Dependency Parsers这篇论文中提出这一问题的一个解决方案，即假设影响参数更新的序列只有少数解码过程中分数比较高的序列。 所以，用k-best viterbi算法求k个序列标注结果。 然后用这k个结果按照mira算法中的二次规划求第r类的更新权重τr并更新参数。 这里，McDonald也提到，实验表明，k如果过大，算法就很快过拟合训练数据了。



from http://mli7.wordpress.com/2011/03/25/online_learning_expert_problem/

两个故事

从前，网络的一头住着个挨踢男，另一头住着一小编。每天小编写一封垃圾邮件给挨踢男。苦命的挨踢男日日分析邮件设计过滤器来过滤垃圾邮件。但聪明的小编每天检查邮件有没有被挨踢男收到，不断增加更多的甜言蜜语来忽悠挨踢男。较量一直进行下去，挨踢男是否能摆脱小编的骚扰呢？

这个故事都属于博弈论里的重复游戏（repeated game），它是对在线学习（online learning）最贴切的刻画：数据不断前来，我们需根据当前所能得到的来调整自己的最优策略。

熟悉机器学习的稳拿可能注意到了在线学习与在机器学习（统计学习）里所讨论的（离线）学习的区别。前者认为数据的分布是可以任意的，甚至是为了破坏我们的策略而精心设计的，而后者则通常假定数据是服从独立同分布。这两种不同的假设带来不一样的设计理念和理论模型。

统计学习考虑算法所求得到的模型与真实模型的差距。数据由真实模型产生，如果能有无限数据、并在包含有真实模型的空间里求解，我们大概率能求得真实模型。但实际上我们只有有限数据，且只能考虑某类模型，因此很可能我们得不到真实解。所以，好的算法是能够用不多的数据来得到一个效果不错的模型。

在线学习的一个主要限制是当前只能看到当前的和过去的数据，未来是未知，有可能完全颠覆现在的认知。因此，对在线学习而言，它追求的是知道所有数据时所能设计的最优策略。同这个最优策略的差异称之为后悔（regret）：后悔没能一开始就选对最优策略。我们的希望是，时间一久，数据一多，这个差异就会变得很小。因为不对数据做任何假设，最优策略是否完美我们不关心（例如回答正确所有问题）。我们追求的是，没有后悔（no-regret）。

如果与统计学习一样对数据做独立同分布假设，那么在线学习里的最优策略就是在得知所有数据的离线学习所能得到最优解。因此在线学习可以看成是一种优化方法：随着对数据的不断访问来逐步逼近这个离线最优解。

很早以前优化界都在追求收敛很快的优化算法，例如牛顿迭代法。而最近learning的人却发现，好的优化算法很可能是坏的learning算法。这类算法虽然迭代一些次就能算出一个精度很高的解，但每一步都很贵，而且数据一大根本算不动。而向来被优化界抛弃的在线学习、随机优化算法（例如stochastic gradient descent），虽然收敛不快，不过迭代代价很低，更考虑到learning算法的解的精度要求不高，所以在实际应用中这些方法通常比传统的优化算法快很多，而且可以处理非常大的数据。

随便看看这些年ICML，NIPS，JMLR上online, stochastic关键字文章的数量就知道这类算法的大红大紫了。一个通常的规律是learning界火过的topic在computer vision，data mining等偏应用的方向上会接着火几年，所以肯定CVPR, ICCV, KDD之类会议上还会有茫茫多这类paper。因为最近一直在做这个topic，所以想乘自己知识还新，就自己的理解来谈谈它。希望能用通俗的语言为大家介绍这个topic，为国内learning界做做贡献。

当然，相对于老地主online learning，stochastic绝对是新贵。我会接下来谈这类算法，以及他们动辄数页的convergence rate的证明。我的另外一个topic是大规模矩阵的低秩近似，也算大规模机器里面的一个重要问题，我想有时间也来浅出一下。

下面是有公式的正文。

准确点的定义

我们把挨踢男都称之为learner，并从learner的角度来看问题。在http://s0.wp.com/latex.php?latex=y_t+&bg=ffffff&fg=000000&s=0。

用损失函数http://s0.wp.com/latex.php?latex=R(T)+&bg=ffffff&fg=000000&s=0，有

\displaystyle R(T)=\sum_{t=1}^T\ell_t(h_t)-\min_{h\in\mathcal{H}}\sum_{t=1}^T\ell_t(h).

learner的目标就是每次挑不错的http://s0.wp.com/latex.php?latex=T+&bg=ffffff&fg=000000&s=0变大而变小。我们称一个online算法是不是no-regret，或者说online learnable的，意味着

\displaystyle \lim_{T\rightarrow\infty}\frac{R(T)}{T}\rightarrow 0.

这个定义不是很准确，因为问题http://s0.wp.com/latex.php?latex=x_t+&bg=ffffff&fg=000000&s=0是随机给的，所以这里我们要考虑最坏情况（小编写最狠的邮件）。为了符号的简单，就免去精确的数学定义了。（事实上，除非是统计人写的文章，优化或者机器学习的文章很多采用这种简单的写法）。

听专家的话

no-regret是不是很难达到呢？事实证明很多简单的算法都是no-regret。举个最经典的例子，假设我们有http://s0.wp.com/latex.php?latex=m+&bg=ffffff&fg=000000&s=0个专家，他们在每轮问题都会给出的答案。简单起见假设答案就两种，0和1。平方损失在这里就是0-1损失函数，答案正确损失为0，否则为1.

先考虑最简单的情况：假设至少有一个完美专家，她永远给出正确的答案。那么什么才是learner的好策略呢？最简单的很work：看多数专家怎么说罗。learner在时刻http://s0.wp.com/latex.php?latex=t-1+&bg=ffffff&fg=000000&s=0轮一直是给正确答案的专家们，然后采用他们中多数人给出的那个答案。

此方法被称做Halving Algorithm。记http://s0.wp.com/latex.php?latex=/log_2(m)+&bg=ffffff&fg=000000&s=0的损失。另一方面，最优策略当然是一直选中一位完美专家，总损失为0，所以regret的上界是个常数

http://s0.wp.com/latex.php?latex=/displaystyle+R(T)/le+/log_2(m).+&bg=ffffff&fg=000000&s=0

现在考虑并没有传说中的完美专家存在的情况。这时维护http://s0.wp.com/latex.php?latex=t+&bg=ffffff&fg=000000&s=0时刻的答案。

关键是在于如何调整信任度。直观上来说，对于在某一轮预测不正确的专家，我们需降低对她们的信任度，而对预测正确的，我们则可以更加的相信她们。一种常见的调整策略是基于指数的。我们先维护一个没有归一化（和不为1）的信任度http://s0.wp.com/latex.php?latex=i+&bg=ffffff&fg=000000&s=0专家在上一轮的损失，记为\ell_{t-1}(e^i) ，来做如下调整：

\displaystyle u_{t}^i=u_{t-1}^i\exp(-\eta\ell_{t-1}(e^i)),

这里http://s0.wp.com/latex.php?latex=u_t+&bg=ffffff&fg=000000&s=0归一化来得到我们要的分布：w_t^i=u_t^i/\sum_i u_t^i 。此算法被称之为Exponential Weights或者Weighted Majority。

基于指数的调整的好处在于快速的收敛率（它是强凸的），以及分析的简单性。我们有如下结论：如果选择学习率\eta=\sqrt{8\ln m/T} ，那么

\displaystyle R(T)\le \sqrt{\frac{T\ln m}{2}}.

证明先分析\sum_i u^i_{t}/\sum_i u^i_{t-1} ，其上界是关于最优策略的损失，下界是关于learner的损失，移项就得regret的上界（online/stochastic算法的收敛性分析大都走这种形似）。具体的证明这里略过，后面后补上文献。

一个值得讨论的问题是，设定最优学习率http://s0.wp.com/latex.php?latex=T+&bg=ffffff&fg=000000&s=0，而在实际的应用中一般不能知道样本到底会有多少。所以如果设定work的参数很trick。在以后的算法中还会遇到这类需要上帝之手设定的参数，而如何使得算法对这类控制速率的参数不敏感，或者有意的调整参数来控制算法的灵敏度，都是当前研究的热点。这是后话了。

另外一个值得注意的是，同前面存在完美专家的情况相比，regret的上界由http://s0.wp.com/latex.php?latex=/log_2+m+&bg=ffffff&fg=000000&s=0增到了\sqrt{T\ln m/2} 。这两者在实际的应用中有着很大差别。例如我们的目标是要使得平均regret达到某个数值以下，假设前一种方法取1,000个样本（迭代1,000次）就能到了，那么后一种算法就可能需要1,000,000个样本和迭代。这样，在时间或样本的要求上，前者明显优于后者。类似的区别在后面还会更多的遇到，这类算法的一个主要研究热点就是如何降低regret，提高收敛速度。

这次谈的都是online的经典算法。下回我们介绍convex online optimization，这与机器学习更相关。

传统的SVM和adaboost都是batch mode learning. 所谓的batch mode learning， 简单说，就是所有的训练数据都是available的（或则说所有训练数据都已经在内存中）。这种方法主要有2个缺点：

1）  有时候数据量太大，在内存中放不下，处理起来不方便

2）  由于应用环境限制，有时候无法在训练之前得到所有训练数据

而Online learning， 他的数据是come in sequence，也就是说traning sample 是一个一个来，或则是几个几个来，然后classifer 根据新来的samples进行更新。Online learning是比较困难的，主要原因是你无法知道将来的训练数据是如何的。显然adaboost和svm是行不通的。最近几年也有一些人做online learning的研究，主要方法还是集中在online boosting这一块。推荐2篇不错的文章：

1）  online adaboost [1], 并把他用在object tracking等方面。这篇文章发表于CVPR2006引用率蛮高。这几年的cvpr上的几篇做tracking的文章以这个idea为基础。tracking的方法是用最近比较流行的tracking-by-detection的方法。简答的说就是在tracking的时候，observation model这一块是用一个在线训练的分类器。tracking的过程如下图所示（图中还有一步是用跟踪的结果作为训练器的新的输入）：

http://www.vision.ee.ethz.ch/boostingTrackers/images/overviewBoost.png<wbr>learning" ACTION-DATA="http://www.vision.ee.ethz.ch/boostingTrackers/images/overviewBoost.png" ACTION-TYPE="show-slide" STYLE="margin: 0px; padding: 0px; list-style: none;" />

这篇文章online 训练的时候，用tracking 的结果作为online classifier的positive samples。显然这种数据是有噪声的，最后tracking会drift掉。而且需要指出的是，这种方法没有严格证明，只是模仿batch mode adaboost. 我把这个算法用在uci的训练数据上，效果不是很好。作者的主页是：http://www.vision.ee.ethz.ch/~hegrabne/. 这个是他用online learning 做tracking的项目主页：http://www.vision.ee.ethz.ch/boostingTrackers/。 有现成代码和demo。

2）  去年的一篇论文是关于online random forest[2]。网上有现成的代码。我跑了一下，挺牛逼的，效果没比offline mode差不多。如果你需要做online learning的话十分推荐。

[1].On-line Boosting and Vision. 06CVPR.

[2]. Online random forest. 09ICCV workshop on online machine learning.

喜欢

0

阅读┊ 收藏 ┊ 喜欢▼ ┊打印┊举报/Report
  

新浪BLOG意见反馈留言板　欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

Copyright © 1996 - 2022 SINA Corporation, All Rights Reserved

新浪公司 版权所有