2010年10月26日,星期二

为什么广告服务器使用回归?

帖子标题有点冒昧,因为1)我不知道所有广告服务器都使用回归,以及2)即使它们做到了,也很难推测原因。所以这确实是,``过去为什么要在广告投放中使用回归?''但这并不那么吸引人。

为什么还要问这个问题?因为广告投放看起来像是对成本敏感的多类分类,而将对成本敏感的多类分类减少到回归会导致遗憾的界限,而后悔的界限要比减少成二进制分类更糟。

因此,这里列出了我过去遇到的问题,回归减少如何处理以及二进制分类的减少如何处理这些问题。

一整套行动正在发生变化

首先,让我说,即使在一组动作并没有真正迅速改变的情况下,我也使用了回归。例如,我参与了一个域货币化产品,其中的操作是一个出价关键字短语列表(通过驱动到搜索引擎结果页面来货币化)。这样的列表很少(例如每月)更改并且适度(每单位时间制作的``Lady Gaga''数量不多)。真的,我在那里没有任何借口。

如果这组操作确实确实会随着时间发生显着变化(例如,以赞助商搜索广告为背景的目标定位,其中新广告频繁出现),则很容易想到,接受过先前数据训练的回归器会合理地推广到一个新实例,毕竟,新实例将与现有实例(例如单词和单词短语)共享许多功能,并在相似的上下文(例如网页)中显示。这很诱人,但很危险。我学到了一种艰难的方式,即必须谨慎对待从勘探到开发流量的操作。 (``学习艰难的方式''是对``我建立了行不通的东西''的很好委婉说法)。尽管如此,即使承认从勘探政策过渡到开采政策所需的谨慎,也可以说回归使``混合新行动''变得容易。

鉴于从勘探到开采的过渡是受控过程,它如何在简化为二分类的过程中起作用?这些减少中的一些被组织为以二叉树形式组织的锦标赛。考虑添加一个动作。在这种情况下,可以创建一个新的根节点,其子节点是旧的根节点和新的动作。这个新的根节点本质上必须学习:``在什么情况下我应该采取新的行动,而不是在不采取新行动时做我之前会做的事?''以这种方式构建树会导致非常不平衡的树。由于可以在新的根节点下缝合整棵树,因此一次扫描中添加许多动作将稍微缓解该问题,但是除非动作数量加倍,否则仍将导致缺乏平衡。但是,使用$ | A_ {new} |作为增量操作可能是一个不错的选择。 + 1 $个新颖的二进制分类子问题,可训练包含$ \ log_2(| A_ {new} |)$个连续步骤的子问题。

另一种策略是在叶级添加新操作(或删除旧操作)。将现有叶子转换为内部子节点,并将子节点作为新动作,而在前一个叶子上的动作将需要$ 1 + \ log_2(| A_ {old} |)$新的二进制分类子问题来进行训练,因为到根的整个路径必须重新学习。保守地,如果对一组新动作执行此操作,则重新训练的总数将按$ | A_ {new} | $进行缩放,但是实际上,如果替换项在树中彼此靠近,则将共享许多到根的路径。我怀疑实际费用约为$ | A_ {new} | + \ log_2(| A_ {old} | / | A_ {new} |)$,即$ | A_ {new} | $分类符的完整树,加上一条长度为$ \ log_2(| A_ {old}的共享路径| / | A_ {new} |)$到根。我还怀疑可以在$ \ log_2(| A_ {old} |)$连续步骤中完成这些重新训练。

在某些情况下,简单地考虑对整个树进行重新训练并不是没有道理的。每个级别都可以并行训练,因此连续步骤的数量为$ \ log_2(| A |)$,再训练的总数为$ | A | $。考虑到非平稳性,功能创新等,无论如何都必须定期进行全面的重新培训。

查询内约束

这类似于一组动作的更改,但是上一节是关于如何更改可能的动作范围的,而本节是关于在单个实例上如何不允许某些动作。

两种不同的情况 我已经确定第一种,我称为``平均约束CSMC'',涉及到的约束变化非常缓慢(如果有的话),因此可以使用训练和测试数据绘制的IID将它们建模为问题实例的一部分。这些是``不允许在带有色情内容的网页上刊登此广告''之类的事情,在广告的生命周期内几乎永远都不会发生变化(可能由于广告活动说明错误而在一开始)。

第二种,我称为``极小约束CSMC'',涉及快速变化的约束,因此训练集上约束的分布与测试集上约束的分布无关。这些就像``这位广告客户用尽了预算''之类的东西一样,因为广告客户尝试预算的方式可能非常不稳定。这里的约束是对抗性建模的,需要一种解决方案才能对所有可能的约束设置都感到遗憾。

一个有趣的结果是argmax回归减少具有 同样的遗憾 适用于无约束,平均约束和极小约束的CSMC。这可以通过对该实例允许的一组操作上的回归得分简单地使用argmax来实现。

在一般受限的情况下,可以修改基于树的缩减量,以使不允许的动作丧失其锦标赛资格,并且 类似的遗憾 可以得出无约束的情况。对于基于树的约简的minimax约束案例,我还没有任何结果,尽管我有一个小的问题示例,表明仅放弃并不能取得良好的结果。

我强烈怀疑必须充分了解minimax约束的CSMC,才能将回归从广告中淘汰。

查询间约束

这是指需要在一组查询中强制执行的属性。预算约束就是一个典型的例子,其中贪婪的交付具有最坏情况的竞争比率\\ frac {1} {2} $。再次,没有理由(除了缺乏知识),即使在没有查询间约束的情况下,我也使用了回归:一种用于上下文定位eBay联盟广告的系统。会员计划仅在获得付款时才向您付款,因此从本质上讲它们有无限的预算。

但是,通常必须解决这些限制。 要么 数十年来一直在处理此类约束,并且OR普遍减少到回归。如果预算以美元指定,并且回归估计声称是预期收入,则可以使用网络流算法来攻击某些预算受限的广告投放问题。这样的算法足够快,可以在实际流量流入时定期重新运行,以克服流量估算中不可避免的大误差。 (随着CPU和内存的价格降低,可以利用此方法的广告网络的规模会随之增加)。

通过使用诸如动态编程的策略学习之类的方法将广告投放减少到对成本敏感的多类分类中,似乎有可能在这种情况下拒绝回归。对于某些人来说,这可能是一个不错的博士学位论文(有点实用,所以也许没有什么生气)。在此期间,我会坚持下去:我已经提高了 我对随机最短路径的直觉 并最终希望减少流向CSMC的流量。

我还想知道在预算约束条件下进行优化的近似在线方法是否也适用于其他CSMC降低,这些方法涉及在调整后的回归估算中使用argmax。例如与 梅塔(Mehta)等的 $ \ psi(x)= 1-e ^ {x-1} $剩余预算折现函数,可以使用剩余预算折现的观察报酬而不是实际的观察报酬训练基于树的减少量。这是否有意义还需要进一步思考:我对此类算法的分析的理解是,他们认为回归是完美的,而性能限制是由于查询序列的在线性质所致。有趣的是,在回归分析中增加了其他表示遗憾的术语,这样可以说基于树的方法可以做得更好。

选择一套

华润上华减少是从一组操作中选择一个操作,但是在投放广告时,通常会一次选择多个广告。但是,并非总是如此:展示广告通常是单个广告展示,并且移动屏幕的空间可能很稀缺。对于赞助搜索(或赞助搜索广告的上下文广告投放),填充多个职位是常态。

如果与集合相关的奖励是单个动作奖励的总和,则回归将很自然地处理集合选择:仅通过估计值选择前$ m $个动作,而不是第一个。的 后悔 几乎与单一操作情况相同,只是有一个额外的$ \ sqrt {\ min \ {m,| A | -m \}} $。保留了对回归者后悔的(不希望的)平方根依赖性。幸运的是,这个问题也可以 减少到平均受限CSMC。基本策略是“选择最佳操作,然后选择下一个最佳操作,等等。”后悔有一个额外的因素,即$ m $(更糟),但保留了对CSMC后悔的线性依赖关系(更好)。

但是,对于广告投放而言,实践中通常认为线性奖励的假设过于强烈,因为通常会产生重大的排名影响。幸运的是,如果奖励依赖于位置 交换至上和维持相对秩序 (如独立于单调动作的乘法位置调制所暗示),则 相似的技术 当与集合相关联的奖励是通过减少到平均约束CSMC来获得单个动作位置奖励的总和时,可以用于解决选择最佳动作的问题。

如果一组动作的报酬不是单个动作报酬的总和,则一种选择是将整个组视为动作。在广告投放中,这通常是不可行的,但在内容优化(例如,自适应用户界面)中,这是可行的。如果动作之间的外部性仅按位置排列(例如,垂直显示中的串行扫描模型),则直观上感觉像是随机的最短路径问题,但我尚未对此进行验证。

在我工作过的每台广告服务器中,都将一组动作的奖励假定为与单个动作奖励呈线性关系,并且可能会进行位置校正。因此,仅仅因为问题涉及选择集合,使用回归实际上就没有任何借口。

概要

总体而言,我认为阻止从广告投放中淘汰回归的两个主要问题是:1)对抗性强加的查询内约束和2)查询间约束。任何不具有这些属性的广告投放问题都应该是扣篮,以进一步降低CSMC的数量。例如,任何通过搜索引擎目标网页获利的广告投放问题(例如,动作是出价的短语)都不会表现出这些属性;元货币化问题(例如,在多个广告网络之间动态选择)也没有。

我将在业余时间讨论CSMC的查询内和查询间约束。

2010年10月22日,星期五

优先学习机器学习第二部分

因此,我在我的讨论中讨论了经验性的政策估计量 以前的帖子 提供一种解决我被问到时出现的难题的方法 ``提议对决策系统进行变更会对业务产生什么影响?'' 有一些问题和建议,但没有表演障碍。

第一个问题是,我被要求预知的主系统无法通过频繁做出涉及一些动作的决策来运行(例如,就像广告服务器一样);取而代之的是,它很少做出涉及大量动作的决定(例如,就像航空公司在计划其航班时刻表时那样)。幸运的是,它已经进行了足够多次,因此我可以认为自己拥有以下形式的数据样本$ H $:$ \ {(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \})\} $。这就暗示了类似集合启示的经验值估计器,\ [\ sum _ {(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p)\ in H} r(\ pi(x))\ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {p(\ pi(x)\ in \ mathcal {A} | x)}。 \]展望未来,我仍然会在大型决策中做出决策,而不是单独做出决定,但是我假设一个集合的奖励是对动作的奖励之和,因此这应该可行$ \ ldots $

除了第二个问题外,历史政策$ p(\ mathcal {A} | x)$是未知的。这是因为历史策略实际上是确定性的全局优化例程。在这里,我希望可以使用 斯特雷尔等等 将历史数据视为隐含探索性的,估计$ \ hat p(\ mathcal {A} | x)$,并使用\ [\ sum _ {(x,\ mathcal {A},\ {r(a) | a \ in \ mathcal {A} \})\ in H} r(\ pi(x))\ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {\ max \ {\ tau ,\ hat p(\ pi(x)\ in \ mathcal {A} | x)\}}。 \]我需要验证分析 斯特雷尔等等,用于单个操作,在选择和显示集合时成立(大概是)。我还需要安排新策略以提供足够的历史支持,即,我不能选择$ \ hat p $太小的操作(必须编写实际代码来强制执行此操作)。因此,由于我希望有可能突破历史链条,因此我将必须在决策过程中包括一些探索性决策(目前还没有)。

最后,附带条件:此技术仅适用于预测与单个动作明确相关的奖励。所以我需要在这里设定期望。例如,``由于该决策系统的调整,用户在下一年的支出将如何变化?''(对于上述技术)不是一个公平的问题。但是,一个相关且公平的问题是``由于决策系统的调整,用户将如何立即响应操作的变化而立即支出?'',并希望可以采用其他一些挥霍之手来基于短期预测纵向支出花。

2010年10月11日,星期一

相依奖励启示和离线评估

在我的 以前的帖子 我通过探索性学习问题继续了我大部分失败的斗争,其中探索性学习揭示的奖励集取决于奖励矢量的值(又称``依赖奖励启示'')。激励性的例子是价格差异。到目前为止,我在训练期间无法利用历史数据中的其他信息。在这里,我还将表明,对于价格差异问题,我也不能使用其他信息进行脱机策略评估(也许不足为奇,因为学习和评估是相互关联的)。这样说来就更令人惊讶了,因为它说的类似于``即使对于一个特定的历史实例,人们知道拟议的新政策将如何执行,但人们却不能无偏见地使用这些信息。''

当绘制示例IID时,可以使用离线策略估计器来评估静态策略。假设分布$ D = D_x \ times D_ {r | x} $,其中$ x $是与实例关联的特征向量,而$ r:A \ to [0,1] $是与每个动作关联的奖励。我有一个建议的策略$ \ pi:X \ to A $,我想估计$ D $,$ E _ {(x,r)\ sim D} \ left [r \ left(\ pi( x)\ right)\ right] $。

进一步假设历史策略在给定实例$ p(a | x)$的情况下对操作使用已知的条件分布。历史策略定义了由定义的历史数据的分布$ S $
  1. 从$ D $中提取$(x,r)$。
  2. 从$ p(a | x)$中提取$ a $。
  3. 输出实例$ \ left(x,a,r(a),p(a | x)\ right)$。
它是 容易展示 那\ [
\ begin {aligned}
E _ {(x,a,r(a),p)\ sim S} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x )| x)} \ right]&= E _ {(x,r)\ sim D} \ left [E_ {a \ sim p | x} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x)| x)} \ right] \ right] \\
&= E _ {(x,r)\ sim D} \ left [r(\ pi(x))\ frac {1} {p(\ pi(x)| x)} E_ {a \ sim p | x} \ left [1 _ {\ pi(x)= a} \ right] \ right] \\
&= E _ {(x,r)\ sim D} \ left [r \ left(\ pi(x)\ right)\ right],
\ end {aligned}
\]在给定历史数据集$ H $的情况下使用经验策略估计量进行证明,\ [\ frac {1} {| H |} \ sum _ {(x,a,r(a),p)\ in H} r (\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x)| x)}。\]这也是针对上下文强盗的argmax回归方法的基础(即,学习$ r(a)/ p(a | x)$的回归值,以及针对上下文强盗的重要性加权方法(即,将每个历史示例视为具有权重$ r(a)的多类分类问题/ p(a | x)$),尽管这两种方法的后悔界限比偏移树更糟。

到目前为止,一切都是标准的。现在,我将添加一个细微的皱纹,并假设历史策略可能在每个实例中产生一个以上的显示奖励,但仍与奖励值无关。在这种情况下,历史策略会使用已知的操作集$ \ mathcal {A} \ in \ mathcal {P}(A)$中的条件分布,并赋予实例$ p(\ mathcal {A} | x)$,并且历史策略定义了由定义的历史数据的分布\\ mathcal {S} $
  1. 从$ D $中提取$(x,r)$。
  2. 从$ p(\ mathcal {A} | x)$中绘制$ \ mathcal {A} $。
  3. 输出实例$ \ left(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p(\ mathcal {A} | x)\ right)$。
定义$ p(\ mathcal {A} | x)= E _ {\ mathcal {A} \ sim p} \ left [1_ {a \ in \ mathcal {A}} \ right] $,我可以证明\ [
\ begin {aligned}
E _ {(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p)\ sim \ mathcal {S}} \ left [r(\ pi(x)) \ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {p(\ pi(x)\ in \ mathcal {A} | x)} \ right]&= E _ {(x,r) \ sim D} \ left [E _ {\ mathcal {A} \ sim p} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {p (\ pi(x)\ in \ mathcal {A} | x)} \ right] \ right] \\
&= E _ {((x,r)\ sim D} \ left [\ frac {r(\ pi(x))} {p(\ pi(x)\ in \ mathcal {A} | x)} E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ pi(x)\ in A} \ right] \ right] \\
&= E _ {((x,r)\ sim D} \ left [r(\ pi(x))\ right],
\ end {aligned}
\]到目前为止,这都是非常文明的。这表明经验政策评估者\ [\ frac {1} {| H |} \ sum _ {(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p) \ in H} r(\ pi(x))\ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {p(\ pi(x)\ in \ math {A} | x)} ; \]一种argmax回归方法,其中每个历史示例都为估计$ r(a)/ p(a \ in \ mathcal {A} | x)$)贡献了多个回归训练示例;以及一种成本敏感的多类方法,其中奖励向量的非零元素的成本为$ -r(a)/ p(a \ in \ mathcal {A} | x)$。最后两种方法是否有比后一种方法更糟糕的遗憾 滤波偏移树?我应该弄清楚(大概是)。

但是现在,我将假设一些适用于价格差异的附加结构:行动就是价格;行动就是价格;行动就是价格。奖励是零(如果没有购买发生)或价格的已知函数(如果发生购买);以特定价格购买意味着将以任何较小的价格购买;而未按特定价格购买则意味着不会以更大的价格进行购买。更普遍地讲,有一项历史政策选择单个动作$ p(a | x)$,然后世界选择依赖地揭示某些特征$ q(\ mathcal {A} | x,a,r)$。这定义了由定义的历史数据的分布$ \ mathcal {S} ^ \ prime $
  1. 从$ D $中提取$(x,r)$。
  2. 从$ p(a | x)$中提取$ a $。
  3. 从$ q(\ mathcal {A} | x,a,r)$中绘制$ \ mathcal {A} $。
  4. 输出实例$ \ left(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p(a | x),q(\ mathcal {A} | x,a ,r)\ right)$。
现在定义$ p(a \ in \ mathcal {A} | x,r)= E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q} \ left [1_ {a \ in \ mathcal {A}} \ right] \ right]。$然后\ [
\ begin {aligned}
&E _ {(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p,q)\ sim \ mathcal {S} ^ \ prime} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {p(\ pi(x)\ in \ mathcal {A} | x,r)} \ right] \\
&= E _ {((x,r)\ sim D} \ left [E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {p(\ pi(x)\ in \ mathcal {A} | x,r)} \ right] \ right] \ right] \\
&= E _ {((x,r)\ sim D} \ left [\ frac {r(\ pi(x))} {p(\ pi(x)\ in \ mathcal {A} | x,r)} E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q} \ left [1 _ {\ pi(x)\ in \ mathcal {A}} \ right] \ right] \ right] \\
&= E _ {((x,r)\ sim D} \ left [r(\ pi(x))\ right]。
\ end {aligned}
\]很棒,除了问题再次在于$ p(\ mathcal {A} | x,r)$通常无法计算,因为评估它所必需的奖励向量的元素不可用。特别是对于价格差异,我无法确定未选择的较大价格是否会产生购买,因此有助于显示特定价格的价值。

2010年10月9日,星期六

相依奖励启示:第二部分

在我的 以前的帖子 我谈到了价格差异,以及价格差异是如何激发依赖的奖励启示的,这是一种很好的说法,即揭示哪些奖励取决于奖励价值。我必须承认,我对如何利用这些附加信息有些困惑。

我将在这里重复设置:
  1. 世界从$ D $中选择$(x,\ omega,r)$并显示$(x,\ omega)$。
  2. 玩家通过$ p(a | x,\ omega)$在A $中选择$ a \。
  3. 世界通过$ q(\ mathcal {A} | x,\ omega,r,a)$选择$ \ mathcal {A} \ in \ mathcal {P}(A)$,其中$ a \ in \ mathcal {A} $是必需的。
  4. 世界揭示$ \ {r(a)| \ mathcal {A} \} $中的\ in。
通常的``看看你做了什么''的情况是$ q(\ mathcal {A} | x,\ omega,r,a)= 1 _ {\ mathcal {A} = \ {a \}} $差异是\ [
q(\ mathcal {A} | x,\ omega,r,a)=
\ begin {cases}
\{ a^\prime | a^\prime \leq a \} & \mbox{if } r (a) > 0; \\
\ {a ^ \ prime | a ^ \ prime \ geq a \}和\ mbox {if} r(a)= 0。
\ end {cases}
\]因为需要$ a \ in \ mathcal {A} $,所以我总是可以扔掉其他信息,并将任何$ q $转换为$ q = 1 _ {\ mathcal {A} = \ {a \}} $,然后使用 偏移树。这似乎很浪费,但是目前我没有别的选择可以解决价格差异问题。

滤镜偏移样式更新(失败)


考虑一个 滤波偏移树 样式解决方案。修复$(x,\ omega,r)$,并考虑使用输入$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $输入的固定内部节点。 $ \ lambda $的预期重要性权重为\ [
\ begin {aligned}
w _ {\ lambda | r}&= E_ {a \ sim p} \ biggl [E _ {\ mathcal {A} \ sim q | r,a} \ biggl [\ alpha _ {\ lambda,\ neg \ phi} 1_ { \ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} 1_ {r(\ lambda)\ geq \ frac {1} {2}} \ left(r(\ lambda) -\ frac {1} {2} \ right)\\
&\ quad \ quad \ quad + \ alpha _ {\ neg \ lambda,\ phi} 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} 1_ {r(\ phi)\ leq \ frac {1} {2}} \ left(\ frac {1} {2}-r(\ phi)\ right)\\
&\quad\quad\quad + \alpha_{\lambda, \phi} 1_{\lambda \in \mathcal{A}} 1_{\phi \in \mathcal{A}} 1_{r (\lambda) > r (\phi)} \left( r (\lambda) - r (\phi) \right) \biggr] \biggr] \biggl/ \\
&E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} + 1 _ {\ lambda \ in \ mathcal {A}} + 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]。
\ end {aligned}
\]与滤波器偏移量更新的类比建议了选择
\ begin {aligned}
\ alpha _ {\ lambda,\ neg \ phi}&=(1-\ gamma)\ frac {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1_ { \ phi \ in \ mathcal {A}} + 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]]} {E_ {a \ sim p } \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in A} 1 _ {\ phi \ not \ in \ mathcal {A}} \ right] \ right]},\\
\ alpha _ {\ neg \ lambda,\ phi}&=(1-\ gamma)\ frac {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1_ { \ phi \ in \ mathcal {A}} + 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]} {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ not \ in A} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]},\\
\ alpha _ {\ lambda,\ phi}&= \ gamma \ frac {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1_ { \ phi \ in \ mathcal {A}} + 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]} {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in A} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]},
\ end {aligned}
\] for some $\gamma \in [0, 1]$. Unfortunately in general these quantities cannot be computed since $r$ is only partially revealed per instance. For the price differentiation $q$, for instance, only when $a$ is the largest possible price 和 $r (a) > 0$, or when $a$ is the smallest possible price 和 $r (a) = 0$, can these quantities be computed.

我的怀疑是进行此偏移滤镜样式更新的唯一方法是,始终显示$ q $所依赖的一组奖励。所以类似\ [
q(\ mathcal {A} | x,\ omega,r,a)=
\ begin {cases}
\{ \tilde a \} \cup \{ a^\prime | a^\prime \geq a \} & \mbox{if } r (\tilde a) > 0; \\
\ {a,\ tilde a \}& \mbox{if } r (\tilde a) = 0; \\
\ {\ tilde一个\} \ cup \ {a ^ \ prime | a ^ \ prime \ leq a \}和\ mbox {if} r(\ tilde a) < 0, \end{cases} \] would work since $q$ only depends upon $r (\tilde a)$ which is always revealed, so the above expectations can always be computed. With such a cooperative $q$, 其余的偏移滤镜树曲柄 可以转向,加权因子为\ [
\ begin {aligned}
\ alpha _ {\ lambda,\ neg \ phi}&= \ frac {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1_ { \ phi \ in \ mathcal {A}} \ right] \ right]} {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in A} 1 _ {\ phi \ not \ in \ mathcal {A}} \ right] \ right]},\\
\ alpha _ {\ neg \ lambda,\ phi}&= \ frac {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1_ { \ phi \ in \ mathcal {A}} \ right] \ right]} {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ not \ in A} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]},\\
\ alpha _ {\ lambda,\ phi}&= 1,
\ end {aligned}
\]很好,但仍然让我想知道如何利用价格差异问题中可用的其他信息。

2010年10月7日,星期四

价格差异和相关奖励启示

为某人提供商品或服务的价格选择始终是一个重要的选择,在某些情况下可以 改善社会福利。特别是在Internet上,当您提供的服务的有效边际成本通常有效地为零时,如果您可以说服bean计数器提高产量,则有很大的空间可以有选择地降低价格。

想象一下,我有一个与每个用户相关联的丰富特征向量$ x $,并且我必须在一组价格$ A $之间进行选择,以便为用户提供单位数量的单一商品。想象一下价格是粘性的(用户无法获得新的身份来获取新的价格)并且是不可转让的(用户无法给他人提供的价格)。当我向用户提供价格时,我看到他们对该价格的响应,但没有看到我本可以提供给他们的其他价格。如果他们选择购买,我会得到一种奖励,它是所提供价格的已知函数(例如,价格减去成本),否则则为零。 (我要等多久才能决定他们永远不会购买?这是一个好问题。)这种设置看起来像是通过探索获得的经典学习方法,可以通过使用 偏移树 与在线探索策略一起热烈开始。问题解决了!

除了$ \ ldots $,感觉这里还有更多信息。具体来说,如果我向用户提供特定价格$ a $并且他们购买了商品,我可以假设他们会以任何价格$ a ^ \ prime \ leq a $购买商品,并且由于奖励是给定购买价格的已知函数这意味着额外的奖励正在显露。类似地,如果我为用户提供特定价格$ a $而他们没有购买,我可以假设他们不会以任何价格$ a ^ \ prime \ geq a $购买,因此再次显示了其他奖励。对于非奢侈品,这些假设似乎是合理的。

没问题吧?的 滤波偏移树 可以处理每个历史实例何时显示多个奖励,因此我应该使用它。但是,不幸的是,在过滤器偏移树情况下显示其奖励的一组动作是独立于奖励选择的。在这里,揭示其奖励的一组动作取决于奖励,这是产生偏见的秘诀。这种情况类似于向朋友询问最近的一次拉斯维加斯之旅:如果他们赢了钱,他们会谈论数小时,而如果他们输了钱,您得到的一切就是``还可以''。

可以这样形式化设置:
  1. 世界从$ D $中选择$(x,\ omega,r)$并显示$(x,\ omega)$。
  2. 玩家通过$ p(a | x,\ omega)$在A $中选择$ a \。
  3. 世界通过$ q(\ mathcal {A} | x,\ omega,r,a)$选择$ \ mathcal {A} \ in \ mathcal {P}(A)$。
    1. 在\ mathcal {A} $中要求$ a \似乎很合理。换句话说,我总是至少观察到我选择的动作。也许这不是严格要求的,但似乎符合实际情况。
  4. 世界揭示$ \ {r(a)| \ mathcal {A} \} $中的\ in。
通常的``看看你做了什么''的情况是$ q(\ mathcal {A} | x,\ omega,r,a)= 1 _ {\ mathcal {A} = \ {a \}} $如上\
q(\ mathcal {A} | x,\ omega,r,a)=
\ begin {cases}
\{ a^\prime | a^\prime \leq a \} & \mbox{if } r (a) > 0; \\
\ {a ^ \ prime | a ^ \ prime \ geq a \}和\ mbox {if} r(a)= 0。
\ end {cases}
\]现在我想知道在什么情况下可以使用这些额外信息。显然,我总是可以丢弃多余的信息,而仅检查$ r(a)$,这将是普通的偏移量树。我可以做得更好吗?

2010年10月3日,星期日

位置偏移树

我的 以前的帖子 总结了我最近关于在考虑到位置影响的情况下对具有部分反馈的成本敏感型最佳客户(CSBM-PF)的想法。一个主要的启发性应用程序是优化内容(或广告)元素集,对于这些元素而言,位置效果通常很重要。经过一番尝试之后,我决定挥舞理论上的白旗,并简化了将奖励因素分解为特定于动作的位置独立因素和特定于位置的动作独立因素的假设。但是,事实证明,即使这样,我也无法很好地利用来自较新职位的数据来告知较早职位的遗憾。我开始怀疑从以后的位置使用数据存在根本性的错误。

该方法包括两个部分。第一部分是对偏移树的修改,其中包含了位置效应,这就是本文的内容。第二部分是对从CSBM还原为CSMC以构建整个集合的略微修改。我将专注于这篇文章的第一部分。最重要的是,通过规范每个动作的位置呈现历史,我可以使用先前位置的数据来告知当前位置的遗憾。

设置如下。有一个分布$ D = D_x \ times D _ {\ omega | x} \ times D_ {r | \ omega,x} $,其中$ r:A \ times [1,m] \ to [0,1] \ cup \ {-\ infty \} $以单位间隔中的值加上$-\ infty $,并且将$ r $的特定实例中$-\ infty $值的分量显示为问题的一部分通过$ \ omega \ in \ mathcal {P}(A \ times [1,m])$中的实例(即$ \ omega $是$ A \ times [1,m] $的子集)。响应问题实例所允许的输出是$ A $上的$ m $-矢量,没有重复,表示为\ [\ Xi_m = \ {\ xi \ in A ^ m | \ xi_i = \ xi_j \ iff i = j \}。\]特定确定性策略$ h的遗憾:X \ times \ mathcal {P}(A)\ to \ Xi_m $由\ [v(h)给出= E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [\ max_ {s \ in \ Xi_m} \; E_ {r \ sim D_ {r | \ omega,x}} \ left [\ sum_ {n = 1} ^ mr(\ xi_n,n)\ right]-E_ {r \ sim D_ {r | \ omega,x }} \ left [\ sum_ {n = 1} ^ mr(h_n(x,\ omega),n)\ right] \ right]。 \]我假定历史策略在给定实例$ p(\ xi | x,\ omega)$的情况下对$ \ Xi_m $使用已知的条件分布。注意,对于某些$ \ omega $,可能没有$ \ Xi_m $可行的元素,即获得有限奖励的元素;在这种情况下,后悔永远是零。因此,问题空间中有趣的部分是那些$ \ xi_m $可行的$ \ omega $。

简化的假设是,动作位置对因子的奖励为\ [r(a,i)= \ kappa(i)\ tilde r(a)\]其中$ i>j \暗示\ kappa(i)<\ kappa(j)$和$ \ kappa(i)\ geq 0 $表示所有$ i $。注意$ \ kappa $是一个随机变量(例如$ \ tilde r $)。尽管我被迫假设$ \ kappa $和$ \ tilde r $独立变化,但我不假定位置因子是已知的或固定的。我将不再谈论$ D_ {r | x,\ omega} $谈论$ D _ {\ tilde r | x,\ omega} \ times D _ {\ kappa | x,\ omega} $。

根据以上假设,可以发现,以贪婪的方式按位置选择动作是最佳的。位置偏移树的要点是使用来自多个位置的数据来通知对特定位置上的动作的选择。我将转向谈论选择单个动作$ h的遗憾:X \ times \ mathcal {P}(A)\ to a $在特定的固定位置$ z $,\ [
\ begin {aligned}
v_z(小时)&= E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ \max_{a \in A}\;E_ {r \ sim D_ {r | x,\ omega}} \ left [r(a,z)\ right]-E_ {r \ sim D_ {r | x,\ omega}} \ left [r(h(x,\ omega),z)\ right] \ right] \\
&= E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ E_{\kappa \sim D_{\kappa|x,\omega}} \left[ \kappa (z) \right] \left( \max_{a \in A}\;E _ {\\ t​​ilde r \ sim D _ {\ tilde r | \ omega,x}} \ left [\ tilde r(a)\ right]-E _ {\ tilde r \ sim D _ {\ tilde r | \ omega,x} } \ left [\ tilde r(h(x,\ omega))\ right] \ right)\ right]。
\ end {aligned}
\]不能在单个位置看到重复的约束,但是在实践中通过将$ \ omega $减少为按位置的单个动作选择,可以通过操作$ \ omega $来满足。
算法:位置没收偏移树火车
数据: 部分标记的约束位置CSMC训练数据集$ S $。
输入: 为其创建分类器的位置$ z $。
输入: 重要性加权的二进制分类程序$ \ mbox {Learn} $。
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
结果: 经过训练的分类器$ \ {\ Psi_ \ nu | \ nu \ in \ Lambda(T)\} $。
对于从叶到根的每个\\ nu \ in \ Lambda(T)$:
  1. $ S_ \ nu = \ emptyset $。
  2. 对于每个示例$(x,\ omega,\ xi,\ {r(a,i)|(a,i)\ in \ xi \},p(\ cdot | x,\ omega))\ in S $:
    1. 假设$ \ lambda $和$ \ phi $是输入到$ \ nu $的两个类(分别针对输入$(x,\ omega)$的左和右子树的预测)。
    2. 如果$(\ lambda,z)\ in \ omega $,预测$ \ phi $以便为父节点构建训练输入(``$ \ lambda $遗忘'');
    3. 否则,如果$(\ phi,z)\ in \ omega $,预测$ \ lambda $以便为父节点构建训练输入(``$ \ phi $遗忘'');
    4. 否则foreach $ n $ in $ \ Upsilon _ {\ lambda,\ phi} = \ {n \ in [1,z] | E _ {\ xi \ sim p} \ left [1 _ {\ xi_n = \ lambda} 1 _ {(\ lambda,n)\ not \ in \ omega} \ right] E _ {\ xi \ sim p} \ left [1_ { \ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]> 0 \}$:
      1. 假设$ \ alpha = | \ Upsilon _ {\ lambda,\ phi} | ^ {-1} \ frac {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi} } 1 _ {\ xi_n = \ lambda} 1 _ {(\ lambda,n)\ not \ in \ omega} + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right ]} {E _ {\ xi ^ \ prime \ sim p} \ left [1 _ {\ xi ^ \ prime_n = \ xi_n} 1 _ {(\ xi_n,n)\ not \ in \ omega} \ right]} $
      2. 令$ y = 1 _ {\ xi_n = \ lambda} $。
      3. 如果$ r(\ xi_n,n)<\ frac {1} {2} $,$ S_ \ nu \ leftarrow S_ \ nu \ cup \ left \ {\ left(x,1-y,\ alpha \ left(\ frac {1} {2}-r( \ xi_n,n)\ right)\ right)\ right \} $;
      4. 其他$ S_ \ nu \ leftarrow S_ \ nu \ cup \ left \ {\ left(x,y,\ alpha \ left(r(\ xi_n,n)-\ frac {1} {2} \ right)\ right) \ right \} $。
  3. 令$ \ Psi_ \ nu = \ mbox {Learn}(S_ \ nu)$。
返回$ \ {\ Psi_ \ nu | \ nu \ in \ Lambda(T)\} $。

算法:位置没收偏移树测试
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
输入: 经过训练的分类器$ \ {\ Psi_ \ nu | \ nu \ in \ Lambda(T)\} $。
输入: 实例实现$ {x,\ omega)$。
结果: 预测标签$ k $。
  1. 令$ \ nu $为根节点。
  2. 重复直到$ \ nu $是叶节点:
    1. 如果$ \ nu $左子树中所有叶子的标签都在$ \ omega $中,则遍历右孩子;
    2. 否则,如果$ \ nu $右子树中所有叶子的标签都在$ \ omega $中,则遍历到左孩子;
    3. 否则,如果$ \ Psi_ \ nu(x)= 1 $,则遍历到左孩子;
    4. 否则(当$ \ Psi_ \ nu(x)= 0 $并且每个子树中至少有一个标签不在$ \ omega $中时),遍历到正确的孩子。
  3. 返回叶子标签$ k $。

激励更新

基本思想是对历史数据进行重要性加权,以使要比较的每对广告都得到相同的预期位置处理。这将对历史政策的要求从``一般化是不安全的,除非一个动作有机会在特定位置展示''到``一般化是不安全的,除非每对动作都有机会在特定位置展示''在考虑中的一个或之前的特定职位''。 (好吧,也许有点让人难以理解)。

对于固定的$(x,\ omega,\ kappa,\ tilde r)$和内部节点为左输入$ \ lambda $和右输入$ \ phi $的情况,$ \ lambda $的预期重要性权重为\ [
\ begin {aligned}
w _ {\ lambda | \ tilde r,\ kappa} = \ frac {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}}} 1 _ {\ xi_n = \ lambda } 1 _ {(\ lambda,n)\ not \ in \ omega} \ alpha _ {\ lambda,n} \ left(\ kappa(n)\ tilde r(\ xi_n)-\ frac {1} {2} \ right )_ + + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ alpha _ {\ phi,n} \ left(\ frac {1} {2}-\ kappa( n)\ tilde r(\ xi_n)\ right)_ + \ right]} {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} 1 _ {\ xi_n = \ lambda} 1 _ {((lambda,n)\ not \ in \ omega} + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]},
\ end {aligned} \]其中$ \ alpha _ {\ lambda,n} $和$ \ alpha _ {\ phi,n} $要确定比例因子,而\ [\ Upsilon _ {\ lambda,\ phi} = \ {n \ in [1,z] | E _ {\ xi \ sim p} \ left [1 _ {\ xi_n = \ lambda} 1 _ {(\ lambda,n)\ not \ in \ omega} \ right] E _ {\ xi \ sim p} \ left [1_ { \ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]>0 \} \]是在当前位置或之前获得共享支持的可行位置的集合。这表明\ [
\ alpha _ {\ lambda,n} \ propto
\ frac {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} 1 _ {\ xi_n = \ lambda} 1 _ {((lambda,n)\ not \ in \ omega} + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]} {E _ {\ xi \ sim p} \ left [1 _ {\ xi_n = \ lambda } 1 _ {(\ lambda,n)\ not \ in \ omega} \ right]},
\]产生\ [
\ begin {aligned}
w _ {\ lambda | \ tilde r,\ kappa}&\ propto \ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} \ left(\ kappa(n)\ tilde r(\ lambda)-\ frac { 1} {2} \ right)_ + + \ left(\ frac {1} {2}-\ kappa(n)\ tilde r(\ phi)\ right)_ +,\\
w _ {\ phi | \ tilde r,\ kappa}&\ propto \ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} \ left(\ kappa(n)\ tilde r(\ phi)-\ frac { 1} {2} \ right)_ + + \ left(\ frac {1} {2}-\ kappa(n)\ tilde r(\ lambda)\ right)_ +,\\
w _ {\ lambda | \ tilde r,\ kappa}-w _ {\ phi | \ tilde r,\ kappa}&\ propto \ left(\ tilde r(\ lambda)-\ tilde r(\ phi)\ right)\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} \ kappa(n)。
\ end {aligned}
\]由于位置因素是未知的随机变量,因此无法使其完全等于策略遗憾差异,但是单调性约束意味着$ \ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} \ kappa( n)\ geq | \ Upsilon _ {\ lambda,\ phi} | \ kappa(z)$。因此,选择\ [
\ begin {aligned}
\ alpha _ {\ lambda,n}&=
| \ Upsilon _ {\ lambda,\ phi} | ^ {-1} \ frac {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} 1 _ {\ xi_n = \ lambda} 1 _ {((\ lambda,n)\ not \ in \ omega} + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]} {E_ { \ xi \ sim p} \ left [1 _ {\ xi_n = \ lambda} 1 _ {((\ lambda,n)\ not \ in \ omega} \ right]},\\
\ alpha _ {\ phi,n}&=
| \ Upsilon _ {\ lambda,\ phi} | ^ {-1} \ frac {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} 1 _ {\ xi_n = \ lambda} 1 _ {((\ lambda,n)\ not \ in \ omega} + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]} {E_ { \ xi \ sim p} \ left [1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]},
\ end {aligned}
\]我们得到一个预期的重要权重差,该权重差既有正确的符号,又具有至少等于位置$ z $的政策遗憾的幅度,
\ begin {aligned}
E_ {D _ {\ tilde r | x,\ omega} \ times D _ {\ kappa | x,\ omega}} \ left [w _ {\ lambda | \ tilde r,\ kappa}-w _ {\ phi | \ tilde r,\ kappa} \ right]&= E_ {D _ {\ tilde r | x,\ omega}} \ left [\ tilde r(\ lambda)-\ tilde r(\ phi)\ right] E_ {D _ {\ kappa | x,\ omega}} \ left [\ frac {1} {| \ Upsilon _ {\ lambda,\ phi} |} \ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} \ kappa(n)\ right ],\\
\ mbox {sgn} \ left(E_ {D _ {\ tilde r | x,\ omega} \ times D _ {\ kappa | x,\ omega}} \ left [w _ {\ lambda | \ tilde r,\ kappa}- w _ {\ phi | \ tilde r,\ kappa} \ right] \ right)&= \ mbox {sgn} \ left(E_ {D _ {\ kappa | x,\ omega}} [[\ kappa(z)] E_ { D _ {\\ t​​ilde r | x,\ omega}} \ left [\ tilde r(\ lambda)-\ tilde r(\ phi)\ right] \ right),\\
\ left | E_ {D _ {\ tilde r | x,\ omega} \ times D _ {\ kappa | x,\ omega}} \ left [w _ {\ lambda | \ tilde r,\ kappa}-w _ {\ phi | \ tilde r,\ kappa} \ right] \ right | &\ geq E_ {D _ {\ kappa | x,\ omega}} [\ kappa(z)] \ left | E_ {D _ {\ tilde r | x,\ omega}} \ left [\ tilde r(\ lambda)-\ tilde r(\ phi)\ right] \ right |。
\ end {aligned}
\]这足以使后悔的证明策略起作用。相反,如果我尝试在共享支持下使用所有位置的数据,最终我将$ E_ {D _ {\ kappa | x,\ omega}} [\ kappa(m)] $作为最后一个不平等的主要因素,太小$ E_ {D _ {\ kappa | x,\ omega}} [\ kappa(z)] / E_ {D _ {\ kappa | x,\ omega}} [\ kappa(m)] $ 。我可以扩展条件后悔的范围,并提出另一个证明界限,但是该界限对我没有用,因为在实践中我无法计算$ \ kapp $的比率。

由于我不使用以后的数据,因此我怀疑我可以放宽我的假设并仅假设 交换至上保持相对秩序 而且仍然可以解决问题。

后悔分析

位置没收偏移树的后悔分析与没收偏移树的后悔分析非常相似。主要区别在于,预期重要性权重差不等于策略遗憾,而只是策略遗憾。这足以使证明策略起作用,并且在其他情况下最好注意,即可以做的最好的事情就是限制策略后悔。

令$ \ Psi =(T,\ {\ Psi_ \ nu | \ nu \ in \ Lambda(T)\})$表示特定的位置丧失补偿树(即,选择二叉树和特定的节点集)分类器),令$ z $表示训练树的固定位置,令$ h ^ \ Psi $表示从树得到的策略。后悔分析利用三元组(x ^ \ prime,y,w)$上的诱导重要性加权二元分布$ D ^ \ prime(\ Psi)$,定义如下:
  1. 从$ D $绘制$(x,\ omega,\ kappa,\ tilde r)$。
  2. 在二叉树的内部节点$ \ Lambda(T)$上绘制$ \ nu $制服。
  3. 令$ x ^ \ prime =(x,\ nu)$。
  4. 假设$ \ lambda $和$ \ phi $是输入到$ \ nu $的两个类(分别针对输入$ x $的左和右子树的预测)。
  5. 如果$(\ lambda,z)\ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,0,0)$;
  6. 否则,如果$(\ phi,z)\ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,1,0)$;
  7. 其他(当$ {\ lambda,z)\ not \ in \ omega $和$ {\\ phi,z)\ not \ in \ omega $时):
    1. 在$ \ Upsilon _ {\ lambda,\ phi} $上绘制$ n $制服。
    2. 从$ p(\ xi | x,\ omega)$中绘制$ \ xi $。
    3. 如果$ \ xi_n \ neq \ lambda $和$ \ xi_n \ neq \ phi $,则拒绝样本;
    4. 否则,如果$(\ xi_n,n)\ in \ omega $,则拒绝样本;
    5. 其他(当($ \ xi_n = \ lambda $或$ \ xi_n = \ phi $)和$(\ xi_n,n)\ not \ in \ omega $时:
      1. 假设$ \ alpha = | \ Upsilon _ {\ lambda,\ phi} | ^ {-1} \ frac {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi} } 1 _ {\ xi_n = \ lambda} 1 _ {(\ lambda,n)\ not \ in \ omega} + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right ]} {E _ {\ xi ^ \ prime \ sim p} \ left [1 _ {\ xi ^ \ prime_n = \ xi_n} 1 _ {(\ xi_n,n)\ not \ in \ omega} \ right]} $
      2. 设$ y = 1 _ {\ xi_n = \ lambda} $
      3. 如果$ r(\ xi_n,n)<\ frac {1} {2} $,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1-y,\ alpha \ left(\ frac {1} {2}-r(\ xi_n,n ) \是的是的);\]
      4. 否则,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,y,\ alpha \ left(r(\ xi_n,n)-\ frac {1} {2} \ right)\ right)。 \]
诱导分布$ D ^ \ prime(\ Psi)$取决于特定的树,但是对于任何固定的树都是很好定义的。现在,我想将$ h ^ \ Psi $的政策遗憾与$ \ Psi $的重要性加权二进制遗憾联系起来,\ [\ begin {aligned} q(\ Psi)&= E_{(x^\prime, y, w) \sim D^\prime (\Psi)} \left[ w 1_{y \neq \Psi (x^\prime)} \right] \\ &= \frac{1}{|\Lambda (T)|} \sum_{\nu \in \Lambda (T)} E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ q_\nu (\Psi | x, \omega) \right], \ end {aligned} \] where \[ q_\nu (\Psi | x, \omega) = \ begin {cases} 0 & \mbox{if } \Gamma (\nu_\lambda) \setminus \omega_z = \emptyset \mbox{ or } \Gamma (\nu_\phi) \setminus \omega_z = \emptyset; \\ 0 & \mbox{if } \Psi_\nu (x) = 1_{w_\lambda >w_ \ phi}; \\ \左| w_ \ lambda-w_ \ phi \ right | &\ mbox {otherwise},\ end {cases} \]是内部节点$ \ nu $,$ \ Gamma(\ nu)$的重要性加权后悔的重要性,它是指根于$ \的子树中的一组标签(叶)。 nu $,$ \ nu_ \ lambda $表示$ n $的左子代,$ \ nu_ \ phi $表示$ n $的右子代,$ \ omega_z = \ {a | (a,z)\ in \ omega \} $是在此位置不可行的操作集合,$ w_ \ lambda $是以$(x,\ omega)$和$ w_为条件的左孩子的预期重要性权重\ phi $是以$(x,\ omega)$为条件的正确孩子的预期重要性权重。
定理:遗憾的结界
对于所有部分标记的CSMC分布$ D $,使得$ r = \ kappa \ tilde r $如上所述;所有历史策略$ p(\ xi | x,\ omega)$,以便对于所有对动作$ \ lambda,\ phi $,$ \ Upsilon _ {\ lambda,\ phi} \ neq \ emptyset $每当$(\ lambda ,z)\ not \ in \ omega $和$(\ phi,z)\ not \ in \ omega $;和所有位置丧失的偏移树$ \ Psi $,\ [v_z(h ^ \ Psi)\ leq(| A |-1)q(\ Psi)\]其中$ q(\ Psi)$是重要性加权二进制对引起的子问题感到遗憾。

证明: 看到 附录.
因此,使用来自$ z $和先前位置的数据针对位置$ z $训练的特定位置没收偏移树可以用于选择特定$ z $处的最佳动作。下一步是通过将CSBM简化为CSMC,并稍加修改,将位置$ z $传递给每个子问题,将单个位置丧失的偏移树组合成集合选择器。

由于结果有点让人不知所措,因此最好将其转过头再说如下:按位置归一化演示历史记录不足以证明使用较晚位置的数据来告知较早位置的遗憾,即使给出了非常强的结构假设奖励如何随职位而变化如果确实使用了所有位置的数据,则结果将以\ [v_z(h ^ \ Psi)\ leq(| A |-1)E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [\ frac {E _ {\ kappa \ sim D _ {\ kappa | x,\ omega}}} \ left [\ kappa(z)\ right]} {E _ {\ kappa \ sim D _ {\ kappa | x,\ omega}} \ left [\ kappa(m)\ right]} q(\ Psi | x,\ omega)\ right],\]尽管足以建立简化的一致性,对我而言尚不清楚如何在实践中加以利用:我不知道如何管理不同$(x,\ omega)$之间的优化权衡,因为我不知道$ \ frac {E _ {\ kappa \ sim D_ {\ kappa | x,\ omega}} \ left [\ kappa(z)\ right]} {E _ {\ kappa \ sim D _ {\ kappa | x,\ omega}} \ left [\ kappa(m)\ right ]} $。

附录

这就是后悔的证明。它是根据$ r $而不是$ \ kappa \ tilde r $来完成的,因此我可以轻松地将其适应于较弱的假设 交换至上保持相对秩序.

考虑一个固定的$(x,\ omega)$。讨论内部节点$ \ nu $,\ [v_z(h ^ \ Psi | x,\ omega,\ nu)= \ max_ {k \ in \ Gamma(\ nu)中遇到的条件策略后悔是很有用的} E_ {r \ sim D_ {r | x,\ omega}} \ left [r(a,z)\ right]-E_ {r \ sim D_ {r | x,\ omega}} \ left [r(h_ \ nu ^ \ Psi(x,\ omega),z)\ right]。 \]其中$ h_ \ nu ^ \ Psi $是内部节点$ \ nu $的预测。当$ \ nu $是树的根时,$ v_z(h ^ \ Psi | x,\ omega,\ nu)$是有条件的抵消树策略,遗憾地以$(x,\ omega)$为条件。

证明策略是通过归纳绑定$ v_z(h ^ \ Psi | x,\ omega,\ nu)\ leq \ sum_ {m \ in \ Lambda(\ nu)} q_m(\ Psi | x,\ omega)$ 。对于只有一片叶子(没有内部节点)的树,基本情况很容易满足,因为它的值为$ 0 \ leq 0 $。为了显示在特定内部节点$ \ nu $上的递归,让$ \ lambda $和$ \ phi $是左子树($ \ nu_ \ lambda $)和右子树($ \ nu_ \ phi $)的预测。
情况1:$ \ Gamma(\ nu_ \ lambda)\ setminus \ omega_z = \ emptyset $。在这种情况下,$(\ lambda,z)\在\ omega $中并没有收益,因此选择了$ \ phi $。右子树中必须有一个最大化器,因为左子树中的所有值都是$-\ infty $。此外,对于$ m = \ nu $和$ m \ in \ Lambda(\ nu_ \ lambda)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v_z(h ^ \ Psi | x,\ omega,\ nu)&= \ max_ {k \ in \ Gamma(\ nu)} E_ {r \ sim D_ {r | \ omega, x}} \ left [r(k,z)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ phi,z)\ right] \\&= \ max_ {k \ in \ Gamma(\ nu_ \ phi)} E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k,z)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ phi,z)\ right] \\&= v_z(h ^ \ Psi | x,\ omega,\ nu_ \ phi)\\&\ leq \ sum_ {m \在\ Lambda(\ nu_ \ phi)} q_m(\ Psi | x,\ omega)\\&= \ sum_ {m \ in \ Lambda(\ nu)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]
情况2:$ \ Gamma(\ nu_ \ lambda)\ setminus \ omega_z \ neq \ emptyset $和$ \ Gamma(\ nu_ \ phi)\ setminus \ omega_z = \ emptyset $。在这种情况下,$(\ phi,z)\ in \ omega $和$(\\ lambda,z)\ not \ in \ omega $,因此选择了$ \ phi $充公和$ \ lambda $。左子树中必须有一个最大化器,因为右子树中的所有值都是$-\ infty $。此外,对于$ m = \ nu $和$ m \ in \ Lambda(\ nu_ \ phi)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v_z(h ^ \ Psi | x,\ omega,\ nu)&= \ max_ {k \ in \ Gamma(\ nu)} E_ {r \ sim D_ {r | \ omega, x}} \ left [r(k,z)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ lambda,z)\ right] \\&= \ max_ {k \ in \ Gamma(\ nu_ \ lambda)} E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k,z)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ lambda,z)\ right] \\&= v_z(h ^ \ Psi | x,\ omega,\ nu_ \ lambda)\\&\ leq \ sum_ {m \在\ Lambda(\ nu_ \ lambda)} q_m(\ Psi | x,\ omega)\\&= \ sum_ {m \ in \ Lambda(\ nu)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]
情况3:$ \ Gamma(\ nu_ \ lambda)\ setminus \ omega_z \ neq \ emptyset $和$ \ Gamma(\ nu_ \ phi)\ setminus \ omega_z \ neq \ emptyset $。这是``正常''偏移树情况,其中$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $都没有,所以没收没收。如 如上所示,以$(x,\ omega)$为条件的预期重要性权重差与$(\ lambda,z)$和$(\ phi,z)$之间的政策遗憾具有相同的符号,并且幅度为至少等于$(\ lambda,z)$和$(\ phi,z)$之间的策略遗憾。

不失一般性地假设分类器选择$ \ phi $。如果最大化器来自右子树,则\ [\ begin {aligned} v_z(h ^ \ Psi | x,\ omega,\ nu)&= \ max_ {k \ in \ Gamma(\ nu_ \ phi)} E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k,z)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ phi, z)\ right] \\&= v_z(h ^ \ Psi | x,\ omega,\ nu_ \ phi)\\&\ leq \ sum_ {m \ in \ Lambda(\ nu_ \ phi)} q_m(\ Psi | | x,\ omega)\\&\ leq \ sum_ {m \ in \ Lambda(\ nu)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]如果最大化器来自左子树,则\ [\ begin {aligned} v_z(h ^ \ Psi | x,\ omega,\ nu)&= \ max_ {k \ in \ Gamma( \ nu_ \ lambda)} E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k,z)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \左[r(\ phi,z)\ right] \\&= E_ {r \ sim D_ {r | \ omega,x}} \左[r(\ lambda,z)-r(\ phi,z)\右] + v_z(h ^ \ Psi | x,\ omega,\ nu_ \ lambda)\\&\ leq q_ \ nu(\ Psi | x,\ omega)+ v_z(h ^ \ Psi | x,\ omega, \ nu_ \ lambda)\\和\ qq q_nu(\ Psi | x,\ omega)+ \ sum_ {m \ in \ Lambda(\ nu_ \ lambda)} q_m(\ Psi | x,\ omega)\\ &\ leq \ sum_ {m \ in \ Lambda(\ nu)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]在根处终止归纳会产生\ [v_z(h ^ \ Psi | x,\ omega)\ leq \ sum _ {\ nu \ in \ Lambda(T)} q_ \ nu(\ Psi | x,\ omega)= | \ Lambda(T)| q(\ Psi | x,\ omega)。 \]考虑双方对$ D_x \ times D _ {\ omega | x} $的期望,并注意$ | \ Lambda(T)| =(| A |-1)$完成证明。