2012年4月22日,星期日

主动学习,漂移分布

我们现在有一个好主意该怎么做 IID设置中不可知论的主动学习.  在IID设置和完全对抗设置之间,存在环境随时间变化但忽略了我们的学习算法的情况。 这是刘洋最近发表的一篇论文的主题 主动学习,漂移分布.

被动学习与漂移分布


我对分布漂移的被动学习还不够熟悉,因此我不得不花一些时间来引用其中一项: 论漂移分布学习的复杂性 由Barve和Long撰写。

在IID设置中的被动学习中,我们可以通过经验平均值任意获得对真实期望的良好估计。这意味着对于有限VC维的假设集,我们很有可能在有足够数据的情况下任意接近最优值。

一旦世界开始随时间变化,我们可能或可能没有足够的信息来跟踪变化。 这里有多种建模选择可以形式化地描述世界的漂移方式,包括不常发生的大变化,以及方向和速度缓慢变化的大变化。 Barve和Long研究了世界变化缓慢的情况。 特别是,世界生成了可计数的训练数据序列,该序列由特征标签对$(X \ times Y)^ {\ mathbb {N}} $组成。 这些样本是独立的,但分布不同,并且$ D_t $表示$(x_t,y_t)$的分布。 $ D_t $通过总变化距离\ [
\ sup_U | D_t(U)-D_ {t + 1}(U)| \ leq \ gamma,
\]其中$ U $遍及所有可测量事件,例如,对于可以分配概率的任何事物,连续分布$ D_t $和$ D_ {t + 1} $分配的概率最多相差$ \ γ$。 在这种情况下,如果世界要发生重大变化,则必须向我们提供与中间状态相关的训练数据,这样学习算法才能成功。 Barve和Long表明不可知论学习的充分条件是\ [
\ gamma = O \ bigl(\ frac {\ epsilon ^ 3} {d \ ln(1 / \ epsilon)} \ bigr)。
\]其中$ d $是假设集的VC维,而$ \ epsilon $是我们的目标遗憾。 这是通过在最新示例的窗口上执行ERM来实现的,其中窗口大小由$ \ epsilon $和$ \ gamma $确定。 由于时间$ t $的后悔是相对于$ D_t $的,所以这是一个非常酷的结果。 请注意,$ X $和$ Y $的联合分布允许随时间变化,因此输入要素的分布和 有条件的标签密度(``概念'')正在变化。

不幸的是,这个结果表明我们无法使用无限的数据来任意准确。 事后看来,这并不奇怪,因为即使数据量不受限制,我们也仅将最近的历史记录用于我们的ERM。 分母中没有$ \ ln(1 / \ epsilon)$项的伴随必要条件表明此限制是基本的,而不仅仅是``窗口式ERM''策略的产物。

回到主动学习


回到刘洋,第一个观察是上述``慢漂''的假设不足以进行主动学习。 在主动学习中,我们要丢弃一些(大多数!)标签,这相当于加快世界发展速度(缩放$ \ gamma $)。 特别是,如果我们想被邀请参加“主动学习俱乐部”的VIP部分,我们真的希望获得一个亚线性的标签复杂性,就像使用$ \ gamma \ to \ infty $进行被动学习一样,我们从上面可以看出,这基本上没有准确性。 (但是,由于线性标签的复杂性是IID情况下不可知论主动学习的最坏情况下限,因此上面的``缓慢漂移''条件可能仍然值得研究。)

相反,Yang假定各种$ D_t $是从一组分布彼此接近的分布$ \ mathbb {D} $中得出的。 通过$ \ mathbb {D} $的最小$ \ epsilon $ -cover $ \ mathbb {D} _ {\ epsilon} $形式化,定义为$ \ mathbb {D} $的最小子集,在$ $ \ mathbb {D} $的任何成员的\ epsilon $,以总变化距离来衡量。 特别是,Yang假定$ \ forall \ epsilon>0,| \ mathbb {D} _ {\ epsilon} ||<\ infty $,并假设$ \ forall \ epsilon得到更精确的边界>0,| \ mathbb {D} _ \ epsilon |<c \ cdot \ epsilon ^ {-m} $对于某些常数$ c,m \ in [0,\ infty)$。

本质上,Yang不允许世界随时间任意改变,而是将世界限制在以有限的一组原型分布为特征的分布空间区域内反弹。 为了达到一定的准确性,我们只需要考虑原型分布之间的差异,这反过来表明,在合适的条件下,我们最终将积累足够的信息,我们可以放弃一些标签。

Yang进一步限制了给定要素的标签的条件分布是固定的,并且仅允许要素的分布随时间变化。 第二个假设意味着谈论可实现的情况是有意义的,在可实现的情况下,称为 CAL 如果(最大)漂移,则在这种漂移环境中实现亚线性错误边界和标签复杂性 分歧系数 足够小。 CAL的快速总结是,它仅在存在可以预测每个标签的经验完美假设的情况下才查询标签。否则,它会推断出未观察到的标签是与其余经验完美假设相关联的标签。 CAL使用了整个历史记录,但是利用可实现性取得了成功,并注意条件分布(因此可实现性)在这里是恒定的。

在扩展可实现的分析之后,Yang接下来考虑严格良性的噪声情况,定义为存在一个最佳假设,该假设在条件上总是正确而不是不正确(对于$ \ mathbb {D} $中的所有分布)。 在这种情况下,称为ACAL的CAL不可知变量将实现亚线性错误界限和标签复杂性。 像CAL一样,ACAL会推断标签,但是这样做是通过误差差异而不是要求经验完善。 在Yang的论文中,ACAL使用窗口化数据,其中周期性地丢弃所有历史记录,并且窗口大小以几何方式增加,但这不是由于漂移引起的;而是由于ACAL的标准规格假定了特定的标签预算,所以在线设置了无限制的流。 因此ACAL有效地使用了``所有数据''。

一些外卖

本文(和讨论的引文)帮助我认识到,如果环境在某种程度上受到全球环境变化的限制,那么在不断变化的环境中进行主动学习只会``有效''(从标签复杂性的角度来看)。

本文举例说明的一种研究策略是,针对IID案例采用现有的主动学习算法,并将其适应于某种世界漂移模型。 我当然想看 阿尔威特 这样处理:说起来容易做起来难! 将AALwC与Barve和Long进行混搭将建议在最近的数据窗口上运行AALwC,并且在窗口填满后不增加标签计数器。 这将具有线性标签复杂性,但有时恒定因素很重要(例如在我的Mechanical Turk发票上!)。 对于我来说,尚不清楚如果在更严格的Yang对世界漂移的假设下使用AALwC会发生什么。 ACAL实际上使用了所有历史数据的事实表明,AALwC可能在这些条件下可以通过仅减慢与降低查询概率相关的计划来工作。

一种不同的研究策略是在对抗性环境中理解主动学习,然后将不同的在线应用于批处理方案,以将追溯担保转换为多个预期担保。 这种方法有望产生一种在各种不同的世界漂移场景下都可以做到的最佳算法。 如果有人做到这一点,他们将是有名的!

没意见:

发表评论