2012年2月29日,星期三

主动学习与情境强盗

现在,主动学习是 越来越好理解,背景强盗(CB)是理所当然的下一个焦点。我对随机CB的最新技术的了解如下:
  1. 我们拥有在计算上可行的算法,这些算法在经验上可以很好地发挥作用(例如, 汤普森采样),但不能提供强有力的不可知论的理论保证。 (这是一个很好的说法 青年汽车)。
  2. 我们提供的算法可提供强有力的不可知论的理论保证(例如, 取消政策),但在计算上不可行。
这里取得的进展超出了理论上的兴趣:随机的CB设置描述了我多年来试图解决的许多问题。

所以我最近(天真?)认为:“嘿,主动学习算法真的很好,它们正在做出类似于探索/利用的决策,所以也许我可以将其用于随机CB解决方案。”事实证明,这是这不是一个好主意,但是理解为什么很有趣。

为了说明起见,请考虑具有二进制奖励的2臂式上下文强盗(注意:以上下文为条件的预期奖励不一定是二进制的;仅奖励的任何特定实现都是二进制的)。在这种情况下,二进制分类器和随机CB策略之间存在自然的对应关系。这表明以下将两臂式随机CB减少为二进制主动学习。
算法:主动学习随机强盗
利用主动学习二进制Oracle $ \ mathcal {O} $的两臂上下文强盗算法。
  1. 获取上下文$ X_k $。
  2. 将上下文$ X_k $作为未标记的数据传递到$ \ mathcal {O} $,并接收决策$ Q_k \ in \ {0,1 \} $来查询标签和预测类$ \ hat Y_k \ in \ {0, 1 \} $。
  3. 如果$ Q_k = 0 $,拉动手臂$ \ hat Y_k $并在\ {0,1 \} $中获得奖励$ R _ {\ hat Y_k} \ in。
  4. 如果$ Q_k = 1 $,
    1. 以相等的概率(即50-50)选择$ A_k \ in \ {0,1 \} $。
    2. 拉动手臂$ A_k $并观察\ $ 0,1 \} $中的奖励$ R_ {A_k}。
    3. 让\ [
      Y_k:= \ begin {cases} A_k&R_ {A_k} = 1 \\ 1-A_k&R_ {A_k} = 0 \ end {cases}。
      \]
    4. 当$ Q_k = 1 $时,按预期将$(X_k,Y_k)$传递给$ \ mathcal {O} $。
基本思想如下:当主动学习算法请求标签时,通过使动作随机化来``探索'';当主动学习算法不请求标签时,通过执行基础分类器想要的操作来``利用''。问题解决了!

当然不是。让我们分析一下算法。首先,说服自己,呈现给基础oracle的数据的0-1分类损失与基础分类器定义的策略损失成正比。由于主动学习算法的学习速度与被动学习算法的学习速度基本相同(但不消耗所有标签),这意味着``剥削策略''将立即产生$ O的遗憾(\ sqrt {\ log(T)/ T})$。但是,在上下文强盗中,重要的是由学习算法引起的策略的遗憾。当主动学习算法请求标签时,遗憾是$ O(1)$,并且由于标签复杂性不可知论主动学习的下限,可以在一定时间内请求标签;这意味着由学习算法引起的策略的最坏情况瞬时遗憾是$ O(1)$。这种遗憾不会让您在上下文强盗理论爱好者垂青的那种聚会上受到欢迎。

现在也许在实践中利用主动学习来实现随机CB确实有效。当然,如果做出适当的低噪声假设,则可以限制主动学习算法的标签复杂度,并且可以使总体遗憾看起来可观。但是,这使我们回到了``在计算上可行的启发式''区域,而不是``不可知论随机CB算法的圣杯''区域。

这是特别有趣的事情:主动学习从根本上比随机CB困难。我之所以这样说是因为标签复杂性下界问题不会困扰直接解决随机CB问题。来自的惊人结果 杜迪克等等 对于学习算法产生的策略,总是有可能实现$ O(\ sqrt {\ log(T)/ T})$后悔。当前,如何以有效的计算方式进行操作是一个悬而未决的问题,但是我们已经可以说以下几点:必须选择是否接收任何奖励信息(主动学习)与被迫仅接受奖励之间存在很大差异。有关所选动作的信息(背景匪徒)。就上述算法而言,问题在于只要$ Q_k = 0 $,我们就``丢弃''信息;并利用该信息是恒定的最坏情况瞬时遗憾与随时间衰减的最坏情况瞬时遗憾之间的差异。

非常感谢John Langford耐心地向我解释了这一点。现在,我迷上了背景强盗!到目前为止,很自然地,我在不可知论的情况下实现$ O(\ sqrt {\ log(T)/ T})$遗憾的尝试并没有成功,但这确实很有趣。