在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

紧接上文,我们讲述在线分类问题

在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2为0-1损失,我们做出如下的简化假设:

在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

学习者的目标是相对于hypotheses set: H具有low regret,其中H中的每个函数是从在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2到{0,1}的映射,并且regret被定义为:

在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

我们首先证明这是一个不可能完成的任务——如果在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2,没有算法可以获得次线性regret bound。考虑在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2是一个总是返0的函数,在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2是一个总是返1的函数。通过简单地等待学习者的预测然后提供相反的答案作为真实答案,攻击者可以使任何在线算法的错误数等于T。相反,对于任何真实答案序列,令b为在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2中的大多数标签,则在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2的错误数最多为T/2。因此,任何在线算法的regret可能至少是T-T/2 =T/2,这不是T的次线性。

为了回避Cover’s impossibility result,我们进一步限制对抗环境的能力。下面展示两种方法。

  第一种方法是增加额外的一个假设:

  在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

  接下来,我们描述和分析在线学习算法,假设有限假设类(Finite Hypothesis Class)和输入序列的可实现性(realizability)。最自然的学习规则是使用(在任何在线回合)任何与过去所有例子一致的假设。

  在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2  

  Consistent 算法维持一个与在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2一致的所有假设的集合在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2。此集合通常称为version space。然后它从中选择任何假设并根据该假设进行预测。

  Consistent 算法的mistake bound:

  在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

  Halving算法:

  在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

  Having算法的mistake bound:

  在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

  证明:

在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

  第二种方法是随机化(Randomization):  

  如果学习机输出在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2),则它在t回合上的期望损失是:在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

  对predictions domain做改变,此时predictions domain不等于target domain:

  在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

  在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

  根据这个假设,可以推导出如下定理中所述的low regret算法:

  在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

  在线学习和在线凸优化(online learning and online convex optimization)—在线分类问题2

  我们已经提出了两种不同的方法来回避Cover’s impossibility result: realizability 和 randomization。这两种方法似乎有些不同。然而,有一个深层的基本概念将它们连接起来。事实上,我们将证明这两种方法都可以解释为凸化技术。凸性是推导在线学习算法的中心主题,我们在下一节中进行研究。

  未完,待续。。。。。。

  下一节分析在线凸优化技术。

  

上一篇:国内固定电话正则验证:'tel': [/0\d{2,3}-\d{7,8}(|([-\u8f6c]{1}\d{1,5}))$/, "请填写有效的电话号码"],


下一篇:在线学习和在线凸优化(online learning and online convex optimization)—FTL算法5