论文标题
长期记忆的在线多任务学习
Online Multitask Learning with Long-Term Memory
论文作者
论文摘要
我们介绍了一个新颖的在线多任务设置。在此设置中，每个任务都分为学习者未知的一系列段。与每个段相关的是一些假设类别的假设。我们提供的算法旨在利用有许多这样的细分市场但相关假设的情况大大减少的情况。我们证明了对任务的任何细分以及任何假设与细分市场的任何关联的遗憾界限。在单任务设置中，这等同于[Bousquet和warmuth的意义上的长期记忆转换； 2003]。我们提供了一种算法，该算法在假设类是有限的假设数量中在时间线性中预测的每个试验。我们还考虑了无限假设类别从复制核心空间中，我们给出了一种算法，该算法在累积试验的数量中，其每次试时间复杂性是立方体的。在单任务特殊情况下，这是具有长期记忆的有效遗憾的切换算法的第一个示例，用于非参数假设类别。
We introduce a novel online multitask setting. In this setting each task is partitioned into a sequence of segments that is unknown to the learner. Associated with each segment is a hypothesis from some hypothesis class. We give algorithms that are designed to exploit the scenario where there are many such segments but significantly fewer associated hypotheses. We prove regret bounds that hold for any segmentation of the tasks and any association of hypotheses to the segments. In the single-task setting this is equivalent to switching with long-term memory in the sense of [Bousquet and Warmuth; 2003]. We provide an algorithm that predicts on each trial in time linear in the number of hypotheses when the hypothesis class is finite. We also consider infinite hypothesis classes from reproducing kernel Hilbert spaces for which we give an algorithm whose per trial time complexity is cubic in the number of cumulative trials. In the single-task special case this is the first example of an efficient regret-bounded switching algorithm with long-term memory for a non-parametric hypothesis class.
