显示带有标签的帖子 约束条件. 显示所有帖子
显示带有标签的帖子 约束条件. 显示所有帖子

2010年11月22日,星期一

Minimax受约束的CSMC:进展不大

在一个 以前的帖子 我谈到了广告投放,以及为什么基于回归的方法仍然占主导地位,即使其他针对成本敏感的多类分类(CSMC)的方法具有较低的遗憾界限。我认为,这归结为实际问题,而广告投放中的一个重要的实际问题是,给定决策实例(广告投放请求)所允许的一组操作(广告)可能是易变的。此外,在许多情况下,例如,由于广告商尝试预算,没有理由相信训练集和测试集之间的约束模式在统计上是稳定的。因此,我认为最好以对抗性方式建模约束,这种情况称为minimax约束CSMC。

我将对minimax受约束的CSMC重复设置。有一个分布$ D = D_x \ times D _ {\ tilde c | x} $,其中$ \ tilde c:K \ to \ mathbb {R} $的取值以正实数$ \ mathbb {R} $为单位。然后,一个对手进入,并通过将某些成分设置为$ \ infty $,在扩展实数$ \ mathbf {R} $中制造成本向量$ c $;在做出决定之前,这些选择会通过$ \ omega $显示出来。在这种情况下,特定分类器$ h的遗憾:X \ times \ mathcal {P}(K)\ to K $由\ [\ nu(h)= E_ {x \ sim D_x} \ left [\ max_ {\ omega \ in \ mathcal {P}(K)} \ left \ {E _ {\ tilde c \ sim D _ {\ tilde c | x}} \ left [c(h(x,\ omega))\ right] -\ min_ {k \ in K} \; E _ {\\ t​​ilde c \ sim D _ {\\ t​​ilde c | x}} \ left [c(k)\ right] \ right \} \ right]。 \] 与平均受约束的CSMC相反,后者的约束分布($ \ omega $)从训练到测试数据都是稳定的。对于受约束的普通CSMC,基于树的减少量在经过修改以禁止其选择放弃其锦标赛时起作用。但是,这对于minimax约束的CSMC不起作用,如下面的简单反例所示。假设$ X = \ emptyset $,$ K = \ {1、2、3 \} $和$ \ tilde c $是确定性的,使得$ \ tilde c(1) < \tilde c (3) < \tilde c (2)$, and suppose the tree first pairs $\{1, 2\}$ while giving 3 a pass, 和n pairs $\{1, 3\}$. Suppose the classifier used 在 each tree node 是 $1_{f (a) > f(b)} $用于某些函数$ f:K \ to \ mathbb {R} $。如果仅使用$ \ omega = \ emptyset $的数据进行训练,则在$ f(1)= 1 $,$ f(3)= 3 $和$ f的情况下,对训练数据的后悔可以归零。 (2)= 2 $。但是,当$ \ omega = \ {1 \} $在测试时会感到遗憾。

这里发生了什么?这种情况类似于分类的降级,其中$ f $引起元素的线性排序。在那种情况下,在输入对上平均的分类误差为在输入集上平均的AUC误差提供了界限。当然,AUC对于目标函数而言过于粗糙,因为它仅对排序误差敏感,而对幅度不敏感。但是,这的确表明除了在过滤树的一次通过期间进行的$(| K |-1)$比较之外,还需要在训练期间比较更多对元素。如果必须在训练期间比较每对,则可能需要$ | K | / 2 $通过过滤树。

因此,请考虑在[1,| K |] $中由$ n \索引的平均约束CSMC分类器$ \ Psi_n $的序列。这些会诱发一个序列$ \ {\ tilde \ omega_n | n \ in [0,| K |] \} $通过\ [
\ begin {aligned}
\ tilde \ omega_0&= \ emptyset,\\
\ tilde \ omega_n&= \ tilde \ omega_ {n-1} \ cup \ {\ Psi_n(x,\ tilde \ omega_ {n-1})\}。
\ end {aligned}
\] 本质上,这是一系列平均约束CSMC分类器,它们确定最佳动作,次佳动作等(以与减少 成本敏感的最佳m到成本敏感的多类)。接下来考虑索引\ [
\ eta(x,\ omega)= \ min \ {n \ in [1,| K |] | \ Psi_n(x,\ tilde \ omega_ {n-1})\ not \ in \ omega \}。 \] 如果$ \ omega \ neq K $,则此索引始终存在。当$ \ omega \ neq K $通过\ [h(x,\ omega)= \ Psi _ {\ eta(x,\ omega)}(x,\ tilde \ omega _ {\ eta(x, \ omega)-1})。
\] (当$ \ omega = K $时,无论分类器做出何种选择,遗憾总是为零,因此我将忽略这种情况)。特定$(x,\ omega)$的遗憾由\ [
\ begin {aligned}
\ nu(x,\ omega)&= E_{\tilde c \sim D_{\tilde c|x}} \left[ c (h (x, \omega)) \right] - \min_{k \in K}\;E _ {\\ t​​ilde c \ sim D _ {\\ t​​ilde c | x}} \ left [c(k)\ right] \\
&= E _ {\波浪线c \ sim D _ {\波浪线c | x}} \ left [c(h(x,\ omega))\ right]-\ min_ {k \ in K \ setminus \ tilde \ omega _ {\ eta(x,\ omega)-1}} E _ {\波浪线c \ sim D _ {\波浪线c | x}} \ left [c(k)\ right] \\
&= E _ {\\ t​​ilde c \ sim D _ {\\ t​​ilde c | x}} \ left [c \ left(\ Psi _ {\ eta(x,\ omega)}(x,\ tilde \ omega _ {\ eta(x, \ omega)-1})\ right)\ right]-\ min_ {k \ in K \ setminus \ tilde \ omega _ {\ eta(x,\ omega)-1}}} E _ {\ tilde c \ sim D _ {\代字号c | x}} \ left [c(k)\ right],\\
\ end {aligned}
\] ,其中第二行从$ \ tilde \ omega _ {\ eta(x,\ omega)-1} \ subseteq \ omega $开始,第三行从$ h $的定义开始。现在,最后一行是针对每个实例的$ \ eta(x,\ omega)^ {\ textrm {th}} $平均受约束CSMC分类器的遗憾,该CSMC分类器是根据第一个$(\ eta(x,\ omega)-1)$个分类器。因此\ [
\ max _ {\ omega \ in \ mathcal {P}(K)} \ nu(x,\ omega)= \ max_n \ left \ {E _ {\ tilde c \ sim D _ {\ tilde c | x}} \ left [ c(\ Psi_n(x,\ tilde \ omega_n))\ right]-\ min_ {k \ in K \ setminus \ tilde \ omega_ {n-1}} E _ {\ tilde c \ sim D _ {\ tilde c | x }} \ left [c(k)\ right] \ right \}。
\] 这建议一个过程,其中每个实例完成$ | K | $个没用的过滤树通过;虽然这似乎是2的太多,但注意没收不会生成分类实例,从而消除了一半的比较。 minimax限制了CSMC的遗憾是“ [
\ nu(h)\ leq(| K |-1)E_ {x \ sim D_x} \ left [\ max_n \; q_n(x,\ tilde \ omega_ {n-1})\ right]
\] 其中$ q_n(x,\ tilde \ omega_ {n-1})$是在分配诱导下训练的$ n ^ {\ textrm {th}} $没收过滤树的平均每节点重要性加权后悔被第一个$(n-1)$没收的过滤树。

乍一看,这看起来实在太笨拙,无法在实践中使用,但是有两种修改可能使其实用。第一种是为每个$ \ Psi_n $重用同一棵树,而不是将$ n $个树分开。尽管正确的训练程序对我来说不是立即显而易见的,但遗憾的束缚依然存在。第二种是考虑约束数量(即$ | \ omega |)有界的情况。 \ leq z \ ll | K | $,这样培训和测试成本仅增加$ z $。实际上,这似乎是合理的。

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年9月23日,星期四

汇总没收偏移树注释

在一个 以前的帖子 我讨论了聚合没收偏移树,该树处理在反馈是聚合的情况下使用部分反馈进行学习的问题,即仅观察到部分动作的总奖励。遗憾的证明需要满足一种历史的历史政策。 ``详细余额''条件,即两套\ [
\ begin {aligned}
\ Upsilon _ {\ lambda,\ neg \ phi}&= \{ \mathcal{A} | \mathcal{A} \cap \omega = \emptyset, \lambda \in \mathcal{A}, \phi \not \in \mathcal{A}, E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A}^\prime = \mathcal{A}} ] > 0 \}, \\
\ Upsilon _ {\ neg \ lambda,\ phi}&= \{ \mathcal{A} | \mathcal{A} \cap \omega = \emptyset, \lambda \not \in \mathcal{A}, \phi \in \mathcal{A}, E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A}^\prime = \mathcal{A}} ] > 0 \}.
\ end {aligned}
\] had to be the same when $\lambda$ was replaced by $\phi$ in each set. Basically, if a set containing $\lambda$ and not $\phi$ 是 possible in the historical policy, the corresponding set with $\lambda$ replaced by $\phi$ had to be possible as well. This way, the expected contribution of the other rewards cancels 和 reward of the individual action 是 revealed. Also, $|\Upsilon_{\lambda, \neg \phi}| =| \ Upsilon _ {\ neg \ lambda,\ phi} ||>0 $,即需要有一些集合,且只有一个动作,而没有另一个动作。

好吧,我想提醒自己,如果历史政策不遵守该详细的平衡条件,则可以修改历史数据以创建一个有效的历史政策来遵守该条件。例如,如果$ | \ Upsilon _ {\ lambda,\ neg \ phi} |>| \ Upsilon _ {\ neg \ lambda,\ phi} ||>0 $,我可以拒绝$ \ Upsilon _ {\ lambda,\ neg \ phi} $中的一些额外集合,这样$ | \ Upsilon _ {\ lambda,\ neg \ phi} | = | \ Upsilon _ {\ neg \ lambda,\ phi} | $。当然,依赖于历史策略$ p $的所有归一化常数和因子都需要进行调整,因为现在历史策略为$ p ^ \ prime $($ p $,然后是拒绝步骤)。

2010年9月19日,星期日

聚合没收偏移树

在一个 以前的帖子 我谈到了带有部分反馈的成本敏感型最佳m(CSBM)。想法是选择一组动作,其中该组的奖励是各个元素奖励的总和。我之前考虑过的部分反馈的性质是,只揭示了所选动作组的奖励,但是揭示了该组动作中的每个奖励。另一个可能的情况是,仅揭示所选动作组的总奖励。这比较困难,因为它既是部分反馈又是汇总反馈。但是,在我目前的工作中,存在一个问题,即要优化一组页面元素,但是用户只能通过一种方式与页面进行积极的交互,即,各个页面组件是决策的单元,而不是决策单元。用户反馈的单位。如果所讨论集合的基数很小,则可以将整个集合视为动作并直接利用偏移树。对于我在这里处理的第一个问题,有$ {9 \ choose 2} = 36 $个组合,因此这是完全可行的。占据页面的更多部分可能会将其扩大2或3个数量级,但是我有很多数据,因此也许仍然可以使用。

不过,还是有痒的感觉,我希望使用$ \ ldots $ 偏移树 方法,但对于未设置的单个动作,请使用 约束CSBM约束CSMC减少。第一步是使用汇总反馈来解决约束的CSMC,即从给定的历史数据中选择最佳操作,该历史数据由操作集和相关的总奖励构成。受约束的CSMC设置如下。有一个分布$ D = D_x \ times D _ {\ omega | x} \ times D_ {r | \ omega,x} $其中$ r:A \ to [0,1] \ cup \ {-\ infty \} $以单位间隔上增加$-\ infty $的值,并通过$ \ omega \ in \ mathcal将特定实例的$ r $的分量作为$-\ infty $的值作为问题实例的一部分进行显示。 {P}(A)$(即$ \ omega $是$ A $的子集)。特定确定性策略$ h的遗憾:X \ times \ mathcal {P}(A)\ to A $是\ [v(h)= E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [\ max_ {k \ in A} \\; E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(h(x, \ omega))\ right] \ right]。 \] 我假设历史策略在给定实例$ p(\ mathcal {A} | x,\ omega)$的情况下,在操作的力量集合上使用了已知的条件分布。我将使用缩写$ \ mathcal {A} $来指代$ \ mathcal {P}(A)$的实现。而不是包含$ \ mathcal {A} $每个元素的奖励的历史数据,而是只有$ \ sum_ {a \ in \ mathcal {A}} r(a)$。
算法:汇总没收偏移树火车
数据: 受约束的CSMC具有汇总反馈培训数据集$ S $。
输入: 重要性加权的二进制分类程序$ \ mbox {Learn} $。
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
结果: 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
  1. 从叶子到根的每个$ n \ in \ Lambda(T)$:
    1. $ S_n = \ emptyset $。
    2. 对于每个示例$ \ left(x,\ omega,\ mathcal {A},\ sum_ {a \ in \ mathcal {A}}} r(a),p(\ cdot | x,\ omega)\ right)\ in带$ \ mathcal {A}的S $ \ cap \ omega = \ emptyset $:
      1. 假设$ \ lambda $和$ \ phi $是输入到$ n $的两个类(分别预测输入$(x,\ omega)$的左和右子树)。
      2. 如果$ \ lambda \ in \ omega $,预测$ \ phi $以便为父节点构建训练输入(``$ \ lambda $ forfeits'');
      3. 否则,如果$ \ phi \ in \ omega $,预测$ \ lambda $以便为父节点构建训练输入(``$ \ phi $ forfeits'');
      4. 否则(($ \ lambda \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $))或($ \ lambda \ not \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $):
        1. 让\ [\ alpha = {| A \ setminus \ omega | -2 \ choose | \ mathcal {A} | -1} ^ {-1} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset}(1 _ {\ lambda \ in \ mathcal { A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}})\ right]} { E _ {\ mathcal {A} ^ \ prime \ sim p} [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]}。 \]
        2. 如果$ \ sum_ {a \ in \ mathcal {A}} r(a)<\ frac {| \ mathcal {A} |} {2} $,$ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1 _ {\ phi \ in \ mathcal {A}},\ alpha \ left( \ frac {| \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r(a)\ right)\ right)\ right \} $;
        3. else $ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1 _ {\ lambda \ in \ mathcal {A}},\ alpha \ left(\ sum_ {a \ in \ mathcal {A}}} r(a )-\ frac {| \ mathcal {A} |} {2} \ right)\ right)\ right \} $。
    3. 令$ \ Psi_n = \ mbox {Learn}(S_n)$。
  2. 返回$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
评论: 这假设一个历史策略,其中$ | \ mathcal {A} | $几乎可以肯定是一个常数,并且所有可行集都具有正概率。
算法:汇总没收偏移树测试
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
输入: 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
输入: 实例实现$ {x,\ omega)$。
结果: 预测标签$ k $。
  1. 令$ n $为根节点。
  2. 重复直到$ n $是叶节点:
    1. 如果$ n $左子树中所有叶子的标签都在$ \ omega $中,则遍历右孩子;
    2. 否则,如果$ n $的右子树中所有叶子的标签都在$ \ omega $中,则遍历到左孩子;
    3. 否则,如果$ \ Psi_n(x)= 1 $,则遍历左孩子;
    4. 否则(当$ \ Psi_n(x)= 0 $并且每个子树中至少有一个标签不在$ \ omega $中时),遍历右孩子。
  3. 返回叶子标签$ k $。

激励更新

基本思想是将总奖励用作偏移树中的信号,但仅当一个节点的输入(而非全部)都在一组动作中时才进行归因。利用过滤树样式后悔约束证明策略的关键是确保内部节点上的预期重要性权重差等于对该节点的两个输入而言的策略后悔。由于总奖励是各个奖励的线性组合,因此可以通过评估与相同动作同时出现的动作值之间的差异来比较动作值。选择该更新,使得当采用期望时,仅在输入到特定节点的动作上不同的集合组合以有助于期望的重要性权重差。

对于固定的$(x,\ omega,r)$和一个内部节点,其左输入$ \ lambda \ not \ in \ omega $和右输入$ \ phi \ not \ in \ omega $, $ \ lambda $的预期重要性权重为\ [
\ begin {aligned}
w _ {\ lambda | r}&= \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal { A}} 1 _ {\ phi \ not \ in \ mathcal {A}} \ alpha _ {\ lambda,\ neg \ phi} \ left(\ sum_ {a \ in \ mathcal {A}} r(a)-\ frac {| \ mathcal {A} |} {2} \ right)_ + \ right]} {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset } 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \在\ mathcal {A}}中1 _ {\ phi \在\ mathcal {A}}中\ right]} \\
&\ quad + \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ alpha _ {\ neg \ lambda,\ phi} \ left(\ frac {| \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal { A}} r(a)\ right)_ + \ right]} {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A }} 1 _ {\ phi \ in \ mathcal {A}} \ right]},
\ end {aligned}
\] 其中$(x)_ + = \ max(x,0)$和$ \ alpha _ {\ lambda,\ neg \ phi} $和$ \ alpha _ {\ neg \ lambda,\ phi} $确定比例因子。这表明\ [
\ alpha _ {\ neg \ lambda,\ phi} = \ alpha _ {\ lambda,\ neg \ phi} \ propto \ begin {cases} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right]} {E _ {\ mathcal {A} ^ \ prime \ sim p} [ 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]}& \mbox{if } E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A} \cap \omega = \emptyset} 1_{\mathcal{A}^\prime = \mathcal{A}} ] >0; \\ 0&\ mbox {否则},\ end {cases}
\] 产生\ [
\ begin {aligned}
w _ {\ lambda | r}&\ proto \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ lambda,\ neg \ phi}} \ left(\ sum_ {a \ in \ mathcal {A}} r(a )-\ frac {| \ mathcal {A} |} {2} \ right)_ + + \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ neg \ lambda,\ phi}}} left(\ frac { | \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r(a)\ right)_ +,\\
w _ {\ phi | r}&\ propto \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ neg \ lambda,\ phi}} \ left(\ sum_ {a \ in \ mathcal {A}} r(a )-\ frac {| \ mathcal {A} |} {2} \ right)_ + + \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ lambda,\ neg \ phi}}} left(\ frac { | \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r(a)\ right)_ +,\\
\ end {aligned}
\] \\
\ begin {aligned}
\ Upsilon _ {\ lambda,\ neg \ phi}&= \{ \mathcal{A} | \mathcal{A} \cap \omega = \emptyset, \lambda \in \mathcal{A}, \phi \not \in \mathcal{A}, E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A}^\prime = \mathcal{A}} ] > 0 \}, \\
\ Upsilon _ {\ neg \ lambda,\ phi}&= \{ \mathcal{A} | \mathcal{A} \cap \omega = \emptyset, \lambda \not \in \mathcal{A}, \phi \in \mathcal{A}, E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A}^\prime = \mathcal{A}} ] > 0 \}.
\ end {aligned}
\] 现在,如果并且仅在历史策略下可能用$ \ lambda $而不是$ \ phi $的集合在历史策略下是可能的,并且只有我将用$ \ Upsilon _ {\ lambda,\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda,\ phi} $表示,那么预期的重要权重差为\ [
w _ {\ lambda | r}-w _ {\ phi | r} \ propto | \ Upsilon | \ left(r(\ lambda)-r(\ phi)\ right),
\] 和refore the proper choice when $|\Upsilon_{\lambda,\neg \phi}| =| \ Upsilon _ {\ neg \ lambda,\ phi} ||\doteq |\Upsilon| > 0$ 是 \[
\ alpha _ {\ phi,\ neg \ lambda} = \ alpha _ {\ lambda,\ neg \ phi} = \ begin {cases} | \ Upsilon | ^ {-1} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right]} {E _ {\ mathcal {A} ^ \ prime \ sim p} [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]} & \mbox{if } E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A} \cap \omega = \emptyset} 1_{\mathcal{A}^\prime = \mathcal{A}} ] >0; \\ 0和\ mbox {否则}。 \ end {cases}
\] 在最简单的情况下,在历史政策下所有完全可行的集合都具有正概率,并且由历史政策构造的所有集合都具有相同的$ | \ mathcal {A} | $,然后$ | \ Upsilon | = {| A \ setminus \ omega | -2 \ choose | \ mathcal {A} | -1} $。

在某些情况下,可以遵循不遵循$ \ Upsilon _ {\ lambda,\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda,\ phi} $的历史策略 通过拒绝修改 历史数据的一部分变成有效的历史策略,该策略确实遵循$ \ Upsilon _ {\ lambda,\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda,\ phi} $。

后悔分析

总计没收偏移树的后悔分析与没收偏移树的后悔分析几乎相同。

令$ \ Psi =(T,\ {\ Psi_n | n \ in \ Lambda(T)\})$表示特定的合计没收偏移树(即,选择二叉树和一组特定的节点分类器),并令$ h ^ \ Psi $表示因没收补偿树而产生的策略。后悔分析利用三元组(x ^ \ prime,y,w)$上的诱导重要性加权二元分布$ D ^ \ prime(\ Psi)$,定义如下:
  1. 从$ D $绘制$(x,\ omega,r)$。
  2. 在二叉树的内部节点$ \ Lambda(T)$上绘制均匀的$ n $。
  3. 设$ x ^ \ prime =(x,n)$。
  4. 假设$ \ lambda $和$ \ phi $是输入到$ n $的两个类(分别预测输入$ x $的左和右子树)。
  5. 如果$ \ lambda \ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,0,0)$;
  6. 否则,如果$ \ phi \ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,1,0)$;
  7. 其他(当$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $时):
    1. 从$ p(\ mathcal {A} | x,\ omega)$中绘制$ \ mathcal {A} $。
    2. 如果$ \ mathcal {A} \ cap \ omega \ neq \ emptyset $,则拒绝样本;
    3. 否则(($ \ lambda \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $))或($ \ lambda \ not \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $):
      1. 让\ [\ alpha = | \ Upsilon | ^ {-1} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset}(1_ { \ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A} }} \ right]} {E _ {\ mathcal {A} ^ \ prime \ sim p} [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]},\],其中$ | \ Upsilon | $为 以上定义.
      2. 如果$ \ sum_ {a \ in \ mathcal {A}} r(a)<\ frac {| \ mathcal {A} |} {2} $,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1 _ {\ phi \ in \ mathcal {A}},\ alpha \ left( \ frac {| \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r(a)\ right)\ right); \]
      3. 否则(当$ \ sum_ {a \ in \ mathcal {A}} r(a)\ geq \ frac {| \ mathcal {A} |} {2} $)时,创建重要性加权的二进制示例\ [\ left( x ^ \ prime,1 _ {\ lambda \ in \ mathcal {A}},\ alpha \ left(\ sum_ {a \ in \ mathcal {A}} r(a)-\ frac {| \ mathcal {A} | } {2} \ right)\ right); \]
    4. 否则拒绝样品。
诱导分布$ 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_{n \in \Lambda (T)} E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ q_n (\Psi | x, \omega) \right], \ end {aligned} \] where \[ q_n (\Psi | x, \omega) = \begin{cases} 0 & \mbox{if } \Gamma (n_\lambda) \setminus \omega = \emptyset \mbox{ or } \Gamma (n_\phi) \setminus \omega = \emptyset; \\ 0 & \mbox{if } \Psi_n (x) = 1_{w_\lambda >w_ \ phi}; \\ \左| w_ \ lambda-w_ \ phi \ right | &\ mbox {otherwise},\ end {cases} \] 是内部节点$ n $上的重要性加权后悔,$ \ Gamma(n)$指的是根于$ n $的子树中的一组标签(叶), $ n_ \ lambda $表示$ n $的左子代,$ n_ \ phi $表示$ n $的右子代,$ w_ \ lambda $是在$(x, \ omega)$和$ w_ \ phi $是以$(x,\ omega)$为条件的正确孩子的预期重要性权重。

定理:遗憾的结界
对于所有CSMC发行版$ D $;所有历史政策$ p $,这样对于所有对动作$ \ lambda $和$ \ phi $,$ \ Upsilon _ {\ lambda,\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda,\ phi} \ neq \ emptyset $,只要$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $,并且使得$ E _ {\ mathcal {A} \ sim p} [1_ {a \ in \ mathcal { A}} | x,\ omega]>每当$ a \ not \ in \ omega $时为0 $;以及所有合计没收的偏移树$ \ Psi $,\ [v(h ^ \ Psi)\ leq(| A |-1)q(\ Psi),\]其中$ q(\ Psi)$是重要性加权关于引起的子问题的二元遗憾。

证明: 看到 附录.
尽管这很整洁,但仍然存在缺陷:在以前的情况下,确定对特定动作进行惩罚的约束似乎很自然,但是在这里,更合理的情况是对特定动作组合进行惩罚。它开始看起来像是随机最短路径(SSP),而没有求助于部分(汇总?)反馈和未完全连接的图。在OR中,它们减少了SSP的许多问题,因此,既然我对偏移树有了更好的命令,也许是时候重新访问SSP了。

附录

这就是后悔的证明。

考虑一个固定的$(x,\ omega)$。讨论内部节点$ n $,\ [v(h ^ \ Psi | x,\ omega,n)= \ max_ {k \ in \ Gamma(n)} E_ { r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(h ^ \ Psi_n(x ,\ omega))\ right]。 \] 其中$ h_n ^ \ Psi $是内部节点$ n $的预测。当$ n $是树的根时,$ v(h ^ \ Psi | x,\ omega,n)$是后悔的,以$(x,\ omega)$为条件的抵消树策略。

证明策略是通过感应绑定$ v(h ^ \ Psi | x,\ omega,n)\ leq \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)$。对于只有一片叶子(没有内部节点)的树,基本情况很容易满足,因为它的值为$ 0 \ leq 0 $。为了显示在特定内部节点$ n $上的递归,让$ \ lambda $和$ \ phi $为左子树($ n_ \ lambda $)和右子树($ n_ \ phi $)的预测。

情况1:$ \ Gamma(n_ \ lambda)\ setminus \ omega = \ emptyset $。在这种情况下,\ omega $中的$ \ lambda \和为假,因此选择了$ \ phi $。右子树中必须有一个最大化器,因为左子树中的所有值都是$-\ infty $。此外,对于$ m = n $和$ m \ in \ Lambda(n_ \ lambda)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v(h ^ \ Psi | x,\ omega,n)&=
\max_{k \in \Gamma (n)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\phi) \right] \\ &= \max_{k \in \Gamma (n_\phi)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\phi) \right] \\ &= v (h^\Psi | x, \omega, n_\phi) \\ &\leq \sum_{m \in \Lambda (n_\phi)} q_m (\Psi | x, \omega) \\ &= \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]
情况2:$ \ Gamma(n_ \ lambda)\ setminus \ omega \ neq \ emptyset $和$ \ Gamma(n_ \ phi)\ setminus \ omega = \ emptyset $。在这种情况下,\ omega $中的$ \ phi \和\\ omega $中的$ \ lambda \,而不是\ omega $中的$ \ phi $,因此选择了$ \ phi $充公和$ \ lambda $。左子树中必须有一个最大化器,因为右子树中的所有值都是$-\ infty $。此外,对于$ m = n $和$ m \ in \ Lambda(n_ \ phi)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v(h ^ \ Psi | x,\ omega,n)&=
\max_{k \in \Gamma (n)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\lambda) \right] \\ &= \max_{k \in \Gamma (n_\lambda)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\lambda) \right] \\ &= v (h^\Psi | x, \omega, n_\lambda) \\ &\leq \sum_{m \in \Lambda (n_\lambda)} q_m (\Psi | x, \omega) \\ &= \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]
情况3:$ \ Gamma(n_ \ lambda)\ setminus \ omega \ neq \ emptyset $和$ \ Gamma(n_ \ phi)\ setminus \ omega \ neq \ emptyset $。这是``正常''偏移树情况,其中$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $都没有,所以没收没收。如 如上所示,以$(x,\ omega,r)$和$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $为条件的期望重要性权重满足\ [| w_ \ lambda-w_ \ phi | = \ left | E_ {r \ sim D_ {r | \ omega,x}} \ left [w _ {\ lambda | r}-w _ {\ phi | r} \ right] \ right | = \ left | E_ {r \ sim D_ {r | \ omega,x}} [r(\ lambda)-r(\ phi)] \ right |,\],即内部节点的重要性加权后悔等于策略对于输入到该节点的两个动作感到遗憾。

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

2010年9月13日,星期一

没收的滤波器偏移树

他们说,随着描述中形容词数量的减少,互联网公司的价值也随之上升。我希望在机器学习中并非如此!

所以当我尝试减少时,我遇到的第一件事 平均约束成本敏感最佳 将部分反馈转换为带有部分反馈的平均受限成本敏感型多类分类(CSMC-PF)的原因是,鉴于我设置子问题的方式,每个历史实例通常揭示的奖励向量中不止一个元素。需要的是将 没收过滤树没收的偏移树,当内部节点的两个输入都显示了值时,它将使用丧失的过滤树更新,否则,只有内部节点的一个输入被揭示时,将使用丧失的偏移树更新。

平均受限CSMC-PF设置如下。有一个分布$ D = D_x \ times D _ {\ omega | x} \ times D_ {r | \ omega,x} $其中$ r:A \ to [0,1] \ cup \ {-\ infty \} $以单位间隔上增加$-\ infty $的值,并通过$ \ omega \ in \ mathcal将特定实例的$ r $的分量作为$-\ infty $的值作为问题实例的一部分进行显示。 {P}(A)$(即$ \ omega $是$ A $的子集)。特定确定性策略$ h的遗憾:X \ times \ mathcal {P}(A)\ to A $是\ [v(h)= E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [\ max_ {k \ in A} \\; E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(h(x, \ omega))\ right] \ right]。 \] 在训练数据中,只有部分反馈可用,但与 以前的帖子 我假设奖励向量的潜在多个元素被揭示。我假设历史策略在给定实例$ p(\ mathcal {A} | x,\ omega)$的情况下,在操作的幂集上使用了已知的条件分布。我将使用缩写$ \ mathcal {A} $来指代$ \ mathcal {P}(A)$的实现。
算法:没收滤胶偏移树火车
数据: 受约束的CSMC-PF训练数据集$ S $。
输入: 重要性加权的二进制分类程序$ \ mbox {Learn} $。
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
结果: 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
  1. 从叶子到根的每个$ n \ in \ Lambda(T)$:
    1. $ S_n = \ emptyset $。
    2. 对于每个示例$(x,\ omega,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p(\ cdot | x,\ omega))\ in S $:
      1. 假设$ \ lambda $和$ \ phi $是输入到$ n $的两个类(分别预测输入$(x,\ omega)$的左和右子树)。
      2. 如果$ \ lambda \ in \ omega $,预测$ \ phi $以便为父节点构建训练输入(``$ \ lambda $ forfeits'');
      3. 否则,如果$ \ phi \ in \ omega $,预测$ \ lambda $以便为父节点构建训练输入(``$ \ phi $ forfeits'');
      4. 否则,如果$ \ lambda \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $
        1. $ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1_ {r(\ lambda)>r(\ phi)},| r(\ lambda)-r(\ phi)| \ right)\ right \} $。
      5. 否则,如果$ \ lambda \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $:
        1. 如果$ r(\ lambda)<\ frac {1} {2} $,$ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,0,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E_ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}}]} \ left(\ frac {1} {2} -r(\ lambda)\ right)\ right)\ right \} $;
        2. else $ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p } [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}}]} \ left(r(\ lambda)-\ frac {1} {2} \ right) \ right)\ right \} $。
      6. 否则,如果\\ lambda \ not \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $:
        1. 如果$ r(\ phi)<\ frac {1} {2} $,$ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E_ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} \ left(\ frac {1} {2} -r(\ phi)\ right)\ right)\ right \} $;
        2. else $ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,0,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p } [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} \ left(r(\ phi)-\ frac {1} {2} \ right) \ right)\ right \} $。
    3. 令$ \ Psi_n = \ mbox {Learn}(S_n)$。
  2. 返回$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
算法:没收过滤器偏移树测试
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
输入: 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
输入: 实例实现$ {x,\ omega)$。
结果: 预测标签$ k $。
  1. 令$ n $为根节点。
  2. 重复直到$ n $是叶节点:
    1. 如果$ n $左子树中所有叶子的标签都在$ \ omega $中,则遍历右孩子;
    2. 否则,如果$ n $的右子树中所有叶子的标签都在$ \ omega $中,则遍历到左孩子;
    3. 否则,如果$ \ Psi_n(x)= 1 $,则遍历左孩子;
    4. 否则(当$ \ Psi_n(x)= 0 $并且每个子树中至少有一个标签不在$ \ omega $中时),遍历右孩子。
  3. 返回叶子标签$ k $。

激励更新

利用过滤树样式后悔约束证明策略的关键是确保内部节点上的预期重要性权重差等于对该节点的两个输入而言的策略后悔。当两个奖励值都已知时,过滤器树更新通过区别输入直接完成工作。当仅知道一个奖励值时,偏移树更新将根据观察的相对概率进行加权,从而得出正确的结果。想象一下两者的结合,以$(x,\ omega,r)$和$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $为条件的左输入的预期重要性权重为\ [\ begin {aligned} w _ {\ lambda | r}&= E_{\mathcal{A}\sim p} \biggl[ 1_{\lambda \in \mathcal{A}} 1_{\phi \not \in \mathcal{A}} 1_{r (\lambda) \geq \frac{1}{2}} \alpha_{\lambda, \neg \phi} \left( r (\lambda) - \frac{1}{2} \right) \\ &\quad \quad \quad \quad + 1_{\lambda \not \in \mathcal{A}} 1_{\phi \in \mathcal{A}} 1_{r (\phi) <\ frac {1} {2}} \ alpha _ {\ neg \ lambda,\ phi} \ left(\ frac {1} {2}-r(\ phi)\ right)\\&\quad \quad \quad \quad + 1_{\lambda \in \mathcal{A}} 1_{\phi \in \mathcal{A}} 1_{r (\lambda) >r(\ phi)} \ alpha _ {\ lambda,\ phi} \ bigl(r(\ lambda)-r(\ phi)\ bigr)\ biggr] \ biggl / \\&\quad \quad E_{\mathcal{A} \sim p} \left[ 1_{\lambda \in \mathcal{A}} + 1_{\phi \in \mathcal{A}} - 1_{\lambda \in \mathcal{A}} 1_{\phi \in \mathcal{A}} \right], \ end {aligned} \] where $\alpha_{\lambda,\neg \phi}$ 是 a (to be determined) scaling factor for when only $\lambda$ 是 observed and exceeds $\frac{1}{2}$ or when only $\phi$ 是 observed and does not exceed $\frac{1}{2}$;$ \ alpha _ {\ neg \ lambda,\ phi} $用于仅观察到$ \ phi $并且超过$ \ frac {1} {2} $,或者仅观察到$ \ lambda $并且不超过$ \ frac {1} {2} $;和$ \ alpha _ {\ lambda,\ phi} $适用于同时观察到$ \ lambda $和$ \ phi $的情况。检查表明\ [\ begin {aligned} \ alpha _ {\ lambda,\ neg \ phi}&=(1- -gamma)\ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ lambda \在\ mathcal {A}} + 1 _ {\ phi \ in \ mathcal {A}}中-1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right]} { E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}}]},\\ \ alpha _ {\ neg \ lambda ,\ phi}&=(1- -gamma)\ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ lambda \ in \ mathcal {A}} + 1 _ {\ phi \ in \ mathcal {A}}-1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right]} {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]},\\ \ alpha _ {\ lambda,\ phi}&= \ gamma \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ lambda \ in \ mathcal {A}} + 1 _ {\ phi \ in \ mathcal {A}}-1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \在\ mathcal {A}} \ right]}中{E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} ,\ end {aligned} \] 对于任何$ \ gamma \ in [0,1] $,将导致\ [\ begin {aligned} w _ {\ lambda | r}&=(1-\ gam ma)\ left(r(\ lambda)-\ frac {1} {2} \ right)_ + +(1-\ gamma)\ left(\ frac {1} {2}-r(\ phi)\ right )_ + + \ gamma \ bigl(r(\ lambda)-r(\ phi)\ bigr)_ +,\\ w _ {\ phi | r}&=(1-\ gamma)\ left(r(\ phi )-\ frac {1} {2} \ right)_ + +(1-\ gamma)\ left(\ frac {1} {2}-r(\ lambda)\ right)_ + + \ gamma \ bigl( r(\ phi)-r(\ lambda)\ bigr)_ +,\\ w _ {\ lambda | r}-w _ {\ phi | r}&= r(\ lambda)-r(\ phi)。 \ end {aligned} \] $ \ gamma $呢?我没有选择任何理论上的理由,我只是想将$ \ gamma $设置为过滤器更新的相对概率将给出正确的限制行为(即,在给出相应$ p的情况下,精确地重现偏移量或过滤树( \ mathcal {A} | x,\ omega)$)。这意味着\ [\ gamma = \ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E_ {\ mathcal {A} \ sim p} \ left [1 _ {\ lambda \ in \ mathcal {A}} + 1 _ {\ phi \ in \ mathcal {A}}-1 _ {\ lambda \ in \ mathcal {A} } 1 _ {\ phi \ in \ mathcal {A}} \ right]},\]和\ [\ begin {aligned} \ alpha _ {\ lambda,\ neg \ phi}&= \ frac {E _ {\ mathcal {A } \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} ]},\\ \ alpha _ {\ neg \ lambda,\ phi}&= \ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}}} 1 _ {\ phi \不是\ in \ mathcal {A}} + 1 _ {\ lambda \不是\ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]},\\ \ alpha _ {\ lambda,\ phi}&=1。\ end {aligned} \] 另一个想法是选择$ \ gamma $以使期望的重要性权重最小化,但是我没有任何结果e行。

后悔分析

没收滤波器偏移树的后悔分析与没收偏移树的后悔分析几乎相同。

令$ \ Psi =(T,\ {\ Psi_n | n \ in \ Lambda(T)\})$表示特定的没收滤波器偏移量树(即,选择二叉树和一组特定的节点分类器) ,并让$ h ^ \ Psi $表示因失去过滤器偏移树而产生的策略。后悔分析利用三元组(x ^ \ prime,y,w)$上的诱导重要性加权二元分布$ D ^ \ prime(\ Psi)$,定义如下:
  1. 从$ D $绘制$(x,\ omega,r)$。
  2. 在二叉树的内部节点$ \ Lambda(T)$上绘制均匀的$ n $。
  3. 设$ x ^ \ prime =(x,n)$。
  4. 假设$ \ lambda $和$ \ phi $是输入到$ n $的两个类(分别预测输入$ x $的左和右子树)。
  5. 如果$ \ lambda \ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,0,0)$;
  6. 否则,如果$ \ phi \ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,1,0)$;
  7. 其他(当$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $时):
    1. 从$ p(\ mathcal {A} | x,\ omega)$中绘制$ \ mathcal {A} $。
    2. 如果$ \ lambda \ not \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $,则拒绝样本;
    3. 否则,如果$ \ lambda \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $,则创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1_ {r(\ lambda)>r(\ phi)},| r(\ lambda)-r(\ phi)| \对);\]
    4. 否则,如果$ \ lambda \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $:
      1. 如果$ r(\ lambda)<\ frac {1} {2} $,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,0,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E_ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}}]} \ left(\ frac {1} {2} -r(\ lambda)\ right)\ right); \]
      2. 否则(当$ r(\ lambda)\ geq \ frac {1} {2} $)时,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}}] } \ left(r(\ lambda)-\ frac {1} {2} \ right)\ right); \]
    5. 其他(当$ \ lambda \ not \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $中时):
      1. 如果$ r(\ phi)<\ frac {1} {2} $,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E_ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} \ left(\ frac {1} {2} -r(\ phi)\ right)\ right); \]
      2. 否则(当$ r(\ phi)\ geq \ frac {1} {2} $)时,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,0,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}] } \ left(r(\ phi)-\ 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_{n \in \Lambda (T)} E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ q_n (\Psi | x, \omega) \right], \ end {aligned} \] where \[ q_n (\Psi | x, \omega) = \begin{cases} 0 & \mbox{if } \Gamma (n_\lambda) \setminus \omega = \emptyset \mbox{ or } \Gamma (n_\phi) \setminus \omega = \emptyset; \\ 0 & \mbox{if } \Psi_n (x) = 1_{w_\lambda >w_ \ phi}; \\ \左| w_ \ lambda-w_ \ phi \ right | &\ mbox {otherwise},\ end {cases} \] 是内部节点$ n $上的重要性加权后悔,$ \ Gamma(n)$指的是根于$ n $的子树中的一组标签(叶), $ n_ \ lambda $表示$ n $的左子代,$ n_ \ phi $表示$ n $的右子代,$ w_ \ lambda $是在$(x, \ omega)$和$ w_ \ phi $是以$(x,\ omega)$为条件的正确孩子的预期重要性权重。

算法:没收滤胶偏移树火车
对于所有部分标记的CSMC分布$ D $;所有历史政策$ p $,例如$ E _ {\ mathcal {A} \ sim p} [1_ {a \ in \ mathcal {A}} | x,\ omega]>每当$ a \ not \ in \ omega $时为0 $;以及所有没收的滤波器偏移树$ \ Psi $,\ [v(h ^ \ Psi)\ leq(| A |-1)q(\ Psi)\]其中$ q(\ Psi)$是重要性加权关于引起的子问题的二元遗憾。
证明: 看到 附录.

对于偏移树设置,每个实例仅显示一个奖励成分,$(| A |-1)$依赖性很严格。另一方面,如果每个实例都显示了所有奖励组成部分,则减少的结果会令人遗憾,与操作数无关。我怀疑偏移量树纸的下限可以概括为$ | \ mathcal {A} | $的分布的函数。实际上,这意味着当每个历史实例显示多于1个奖励时,与没收的偏移树不同的是,没收的过滤器偏移树不会``尽其所能''。

好了,现在我准备看一下具有部分反馈的对成本敏感的最佳产品。

附录

这就是后悔的证明。

考虑一个固定的$(x,\ omega)$。讨论内部节点$ n $,\ [v(h ^ \ Psi | x,\ omega,n)= \ max_ {k \ in \ Gamma(n)} E_ { r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(h ^ \ Psi_n(x ,\ omega))\ right]。 \] 其中$ h_n ^ \ Psi $是内部节点$ n $的预测。当$ n $是树的根时,$ v(h ^ \ Psi | x,\ omega,n)$是后悔的,以$(x,\ omega)$为条件的抵消树策略。

证明策略是通过感应绑定$ v(h ^ \ Psi | x,\ omega,n)\ leq \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)$。对于只有一片叶子(没有内部节点)的树,基本情况很容易满足,因为它的值为$ 0 \ leq 0 $。为了显示在特定内部节点$ n $上的递归,让$ \ lambda $和$ \ phi $为左子树($ n_ \ lambda $)和右子树($ n_ \ phi $)的预测。

情况1:$ \ Gamma(n_ \ lambda)\ setminus \ omega = \ emptyset $。在这种情况下,\ omega $中的$ \ lambda \和为假,因此选择了$ \ phi $。右子树中必须有一个最大化器,因为左子树中的所有值都是$-\ infty $。此外,对于$ m = n $和$ m \ in \ Lambda(n_ \ lambda)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v(h ^ \ Psi | x,\ omega,n)&=
\max_{k \in \Gamma (n)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\phi) \right] \\ &= \max_{k \in \Gamma (n_\phi)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\phi) \right] \\ &= v (h^\Psi | x, \omega, n_\phi) \\ &\leq \sum_{m \in \Lambda (n_\phi)} q_m (\Psi | x, \omega) \\ &= \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]
情况2:$ \ Gamma(n_ \ lambda)\ setminus \ omega \ neq \ emptyset $和$ \ Gamma(n_ \ phi)\ setminus \ omega = \ emptyset $。在这种情况下,\ omega $中的$ \ phi \和\\ omega $中的$ \ lambda \,而不是\ omega $中的$ \ phi $,因此选择了$ \ phi $充公和$ \ lambda $。左子树中必须有一个最大化器,因为右子树中的所有值都是$-\ infty $。此外,对于$ m = n $和$ m \ in \ Lambda(n_ \ phi)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v(h ^ \ Psi | x,\ omega,n)&=
\max_{k \in \Gamma (n)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\lambda) \right] \\ &= \max_{k \in \Gamma (n_\lambda)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\lambda) \right] \\ &= v (h^\Psi | x, \omega, n_\lambda) \\ &\leq \sum_{m \in \Lambda (n_\lambda)} q_m (\Psi | x, \omega) \\ &= \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]
情况3:$ \ Gamma(n_ \ lambda)\ setminus \ omega \ neq \ emptyset $和$ \ Gamma(n_ \ phi)\ setminus \ omega \ neq \ emptyset $。这是``正常''偏移树情况,其中$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $都没有,所以没收没收。如 如上所示,以$(x,\ omega,r)$和$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $为条件的期望重要性权重满足\ [| w_ \ lambda-w_ \ phi | = \ left | E_ {r \ sim D_ {r | \ omega,x}} \ left [w _ {\ lambda | r}-w _ {\ phi | r} \ right] \ right | = \ left | E_ {r \ sim D_ {r | \ omega,x}} [r(\ lambda)-r(\ phi)] \ right |,\],即内部节点的重要性加权后悔等于策略对于输入到该节点的两个动作感到遗憾。

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

2010年9月12日,星期日

没收的偏移树

因此,在我寻求从OR清除回归的过程中,到目前为止我一直在考虑的问题有一个不现实的方面。例如,在没有追索权的SSP中,我假设历史数据中的每个图都可以使用与每个边相关的成本。假设只知道与历史上实际经过的边线相关的成本,这似乎更为现实。这是一个例子 通过探索学习,尤其是热启动问题,其中存在具有部分信息的历史数据可用于学习策略。

偏移树 是从具有部分反馈的成本敏感型多类分类(CSMC)减少到二进制分类。它用于在固定类(例如香草CSMC)和历史数据中只有一个决策的情况下,其中仅揭示了所选决策的价值(不同于香草CSMC)。附带说明一下,这种区别是根本的,因为从CSMC到二进制分类都有减少,而遗憾的是与类数无关。而偏移树后悔界限(与$ | A |-1 $成比例)是可证明的下界。

因此,自然要问的一个问题是:我是否可以简化问题的完整信息版本(例如, SSP无追索权)到CSMC子问题集,是否可以将问题的部分信息版本简化为带有部分反馈子问题的CSMC集(并利用偏移树)?我不确定,但我怀疑。

但是,为了建立直觉,我将从一些简单的事情开始。由于我实际上是想减少约束CSMC的问题,因此我需要一些可以处理带有部分反馈的约束CSMC的东西。这建议定义类似于 没收过滤树.

设置如下。有一个分布$ D = D_x \ times D _ {\ omega | x} \ times D_ {r | \ omega,x} $其中$ r:A \ to [0,1] \ cup \ {-\ infty \} $以单位间隔上增加$-\ infty $的值,并通过$ \ omega \ in \ mathcal将特定实例的$ r $的分量作为$-\ infty $的值作为问题实例的一部分进行显示。 {P}(A)$(即$ \ omega $是$ A $的子集)。特定确定性策略$ h的遗憾:X \ times \ mathcal {P}(A)\ to A $是\ [v(h)= E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [\ max_ {k \ in A} \\; E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(h(x, \ omega))\ right] \ right]。 \] 到目前为止,这与CSMC相同,只是进行了外观上的更改以与强化学习文献保持一致:成本(现称为“奖励”)已被抵消,并压缩为单位间隔;和类现在称为``动作''。这是因为唯一真正的区别在于训练数据的部分性质,其仅通过子问题的诱导分布来体现出来。为了定义归纳分布,我将假定历史策略在给定实例$ p(a | x,\ omega)$的情况下对操作使用已知的条件分布;在实践中,有一些方法可以 放松这个假设.
算法:没收偏移树火车
数据: 部分标记的受限CSMC训练数据集$ S $。
输入: 重要性加权的二进制分类程序$ \ mbox {Learn} $。
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
结果: 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
  1. 从叶子到根的每个$ n \ in \ Lambda(T)$:
    1. $ S_n = \ emptyset $。
    2. 对于每个示例$(x,\ omega,a,r(a),p(\ cdot | x,\ omega))\ in S $:
      1. 假设$ \ lambda $和$ \ phi $是输入到$ n $的两个类(分别预测输入$(x,\ omega)$的左和右子树)。
      2. 如果$ \ lambda \ in \ omega $,预测$ \ phi $以便为父节点构建训练输入(``$ \ lambda $ forfeits'');
      3. 否则,如果$ \ phi \ in \ omega $,预测$ \ lambda $以便为父节点构建训练输入(``$ \ phi $ forfeits'');
      4. 否则(当$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $时)如果$ a = \ lambda $或$ a = \ phi $:
        1. 如果$ a = \ lambda $,则$ a ^ \ prime = \ phi $;否则$ a ^ \ prime = \ lambda $。
        2. 设$ y = 1_ {a ^ \ prime = \ lambda} $,即$ a ^ \ prime $来自$ n $的左子树。
        3. 如果$ r(a)<\ frac {1} {2} $,$ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,y,\ frac {p(a | x,\ omega)+ p(a ^ \ prime | x, \ omega)} {p(a | x,\ omega)} \ left(\ frac {1} {2}-r(a)\ right)\ right)\ right \} $;
        4. 其他$ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1-y,\ frac {p(a | x,\ omega)+ p(a ^ \ prime | x,\ omega)}} p( a | x,\ omega)} \ left(r(a)-\ frac {1} {2} \ right)\ right)\ right \} $。
    3. 令$ \ Psi_n = \ mbox {Learn}(S_n)$。
  2. 返回$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
算法:没收偏移树测试
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
输入: 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
输入: 实例实现$ {x,\ omega)$。
结果: 预测标签$ k $。
  1. 令$ n $为根节点。
  2. 重复直到$ n $是叶节点:
    1. 如果$ n $左子树中所有叶子的标签都在$ \ omega $中,则遍历右孩子;
    2. 否则,如果$ n $的右子树中所有叶子的标签都在$ \ omega $中,则遍历到左孩子;
    3. 否则,如果$ \ Psi_n(x)= 1 $,则遍历左孩子;
    4. 否则(当$ \ Psi_n(x)= 0 $并且每个子树中至少有一个标签不在$ \ omega $中时),遍历右孩子。
  3. 返回叶子标签$ k $。
没收偏移树几乎与无约束的部分标记的CSMC的偏移树减少相同,此外,不可行的选择会自动失去他们参加的任何锦标赛(如果两个参赛者都不可行,则可以任意选择)。由于该规则,仅调用底层的二进制分类器来区分可行的选择,而后悔分析本质上是相同的。请注意,即使历史探索政策$ p(a | x,\ omega)$从未选择不可行的行动,但在训练内部节点时没收对于确定``替代行动''仍然很重要。如果历史探索政策实际上选择了不可行的措施,那么将跳过那些训练示例。

后悔分析

对于没收的偏移树的后悔分析与对偏移树的后悔分析非常相似,只是没收案件的附加论据。

令$ \ Psi =(T,\ {\ Psi_n | n \ in \ Lambda(T)\})$表示特定的没用偏移树(即,选择二叉树和一组特定的节点分类器),并且令$ h ^ \ Psi $表示因没收偏移树而产生的策略。后悔分析利用三元组(x ^ \ prime,y,w)$上的诱导重要性加权二元分布$ D ^ \ prime(\ Psi)$,定义如下:
  1. 从$ D $绘制$(x,\ omega,r)$。
  2. 在二叉树的内部节点$ \ Lambda(T)$上绘制均匀的$ n $。
  3. 设$ x ^ \ prime =(x,n)$。
  4. 假设$ \ lambda $和$ \ phi $是输入到$ n $的两个类(分别预测输入$ x $的左和右子树)。
  5. 如果$ \ lambda \ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,0,0)$;
  6. 否则,如果$ \ phi \ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,1,0)$;
  7. 其他(当$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $时):
    1. 从$ p(a | x,\ omega)$中提取$ a $。
    2. 如果$ a \ neq \ lambda $和$ a \ neq \ phi $,则拒绝样本;
    3. 其他(当$ a = \ lambda $或$ a = \ phi $时):
      1. 如果$ a = \ lambda $,则$ a ^ \ prime = \ phi $;否则$ a = \ phi $,$ a ^ \ prime = \ lambda $。
      2. 设$ y = 1_ {a ^ \ prime = \ lambda} $
      3. 如果$ r(a)<\ frac {1} {2} $,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,y,\ frac {p(a | x,\ omega)+ p(a ^ \ prime | x, \ omega)} {p(a | x,\ omega)} \ left(\ frac {1} {2}-r(a)\ right)\ right); \]
      4. 否则,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1-y,\ frac {p(a | x,\ omega)+ p(a ^ \ prime | x,\ omega)} {p (a | x,\ omega)} \ left(r(a)-\ 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_{n \in \Lambda (T)} E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ q_n (\Psi | x, \omega) \right], \ end {aligned} \] where \[ q_n (\Psi | x, \omega) = \begin{cases} 0 & \mbox{if } \Gamma (n_\lambda) \setminus \omega = \emptyset \mbox{ or } \Gamma (n_\phi) \setminus \omega = \emptyset; \\ 0 & \mbox{if } \Psi_n (x) = 1_{w_\lambda >w_ \ phi}; \\ \左| w_ \ lambda-w_ \ phi \ right | &\ mbox {otherwise},\ end {cases} \] 是内部节点$ n $上的重要性加权后悔,$ \ Gamma(n)$指的是根于$ n $的子树中的一组标签(叶), $ n_ \ lambda $表示$ n $的左子代,$ n_ \ phi $表示$ n $的右子代,$ w_ \ lambda $是在$(x, \ omega)$和$ w_ \ phi $是以$(x,\ omega)$为条件的正确孩子的预期重要性权重。
定理:没收偏移树后悔绑定
对于所有部分标记的CSMC分布$ D $;所有历史政策$ p $,例如$ p(a | x,\ omega)>每当$ a \ not \ in \ omega $时为0 $;和所有没收的偏移树$ \ Psi $,\ [v(h ^ \ Psi)\ leq(| A |-1)q(\ Psi)\]其中$ q(\ Psi)$是重要性加权二元遗憾关于诱导的子问题。

证明: 看到 附录.
这与偏移树的界限相同,这表明引入约束不会改变问题设置的基本属性。顺带说一句,为了理解$ \ frac {1} {2} $因子的起源,必须简化到二元分类的所有方式,在这种情况下,预期重要性的最坏情况成为一个因子,并且通过选择$ \ frac {1} {2} $(或每个内部节点的中位数奖励(如果可以先验))将其最小化。

自然的下一步就是看 成本敏感性最佳 有部分反馈;在这种情况下,也许没用的补偿树会很有用。

附录

这就是后悔定理的证明。

考虑一个固定的$(x,\ omega)$。讨论内部节点$ n $,\ [v(h ^ \ Psi | x,\ omega,n)= \ max_ {k \ in \ Gamma(n)} E_ { r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(h ^ \ Psi_n(x ,\ omega))\ right]。 \] 其中$ h_n ^ \ Psi $是内部节点$ n $的预测。当$ n $是树的根时,$ v(h ^ \ Psi | x,\ omega,n)$是后悔的,以$(x,\ omega)$为条件的抵消树策略。

证明策略是通过感应绑定$ v(h ^ \ Psi | x,\ omega,n)\ leq \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)$。对于只有一片叶子(没有内部节点)的树,基本情况很容易满足,因为它的值为$ 0 \ leq 0 $。为了显示在特定内部节点$ n $上的递归,让$ \ lambda $和$ \ phi $为左子树($ n_ \ lambda $)和右子树($ n_ \ phi $)的预测。

情况1:$ \ Gamma(n_ \ lambda)\ setminus \ omega = \ emptyset $。在这种情况下,\ omega $中的$ \ lambda \和为假,因此选择了$ \ phi $。右子树中必须有一个最大化器,因为左子树中的所有值都是$-\ infty $。此外,对于$ m = n $和$ m \ in \ Lambda(n_ \ lambda)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v(h ^ \ Psi | x,\ omega,n)&=
\max_{k \in \Gamma (n)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\phi) \right] \\ &= \max_{k \in \Gamma (n_\phi)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\phi) \right] \\ &= v (h^\Psi | x, \omega, n_\phi) \\ &\leq \sum_{m \in \Lambda (n_\phi)} q_m (\Psi | x, \omega) \\ &= \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]
情况2:$ \ Gamma(n_ \ lambda)\ setminus \ omega \ neq \ emptyset $和$ \ Gamma(n_ \ phi)\ setminus \ omega = \ emptyset $。在这种情况下,\ omega $中的$ \ phi \和\\ omega $中的$ \ lambda \,而不是\ omega $中的$ \ phi $,因此选择了$ \ phi $充公和$ \ lambda $。左子树中必须有一个最大化器,因为右子树中的所有值都是$-\ infty $。此外,对于$ m = n $和$ m \ in \ Lambda(n_ \ phi)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v(h ^ \ Psi | x,\ omega,n)&=
\max_{k \in \Gamma (n)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\lambda) \right] \\ &= \max_{k \in \Gamma (n_\lambda)} E_{r \sim D_{r|\omega,x}} \left[ r (k) \right] - E_{r \sim D_{r|\omega,x}} \left[ r (\lambda) \right] \\ &= v (h^\Psi | x, \omega, n_\lambda) \\ &\leq \sum_{m \in \Lambda (n_\lambda)} q_m (\Psi | x, \omega) \\ &= \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]
情况3:$ \ Gamma(n_ \ lambda)\ setminus \ omega \ neq \ emptyset $和$ \ Gamma(n_ \ phi)\ setminus \ omega \ neq \ emptyset $。这是``正常''偏移树情况,其中$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $都没有,所以没收没收。以$(x,\ omega,r)$和$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $为条件的预期重要性权重为\ [\ begin {aligned} w _ {\ lambda | r}&= E_{a \sim p} \biggl[ 1_{a = \lambda} 1_{r (a) \geq \frac{1}{2}}\frac{p (\lambda | x, \omega) + p (\phi | x, \omega)}{p (\lambda | x, \omega)} \left(r (\lambda) - \frac{1}{2}\right) \\ &\quad \quad \quad \quad + 1_{a = \phi} 1_{r (a) <\ frac {1} {2}} \ frac {p(\ lambda | x,\ omega)+ p(\ phi | x,\ omega)} {p(\ phi | x,\ omega)} \ left(\ frac {1} {2}-r(\ phi)\ right)\ biggr] \ biggl / \\&\ quad \ quad E_ {a \ sim p} \ left [1_ {a = \ lambda} + 1_ {a = \ phi} \ right] \\&= \ left(r(\ lambda)-\ frac {1} {2} \ right)_ + + \ left(\ frac {1} {2}-r(\ phi )\ right)_ +,\\ w _ {\ phi | r}&= \ left(r(\ phi)-\ frac {1} {2} \ right)_ + + \ left(\ frac {1} { 2}-r(\ lambda)\ right)_ +,\\ \ end {aligned} \] 其中$ \ left(x \ right)_ + = \ max(x,0)$。因此\ [| w_ \ lambda-w_ \ phi | = \ left | E_ {r \ sim D_ {r | \ omega,x}} \ left [w _ {\ lambda | r}-w _ {\ phi | r} \ right] \ right | = \ left | E_ {r \ sim D_ {r | \ omega,x}} [r(\ lambda)-r(\ phi)] \ right |,\],即内部节点的重要性加权后悔等于策略对于输入到该节点的两个动作感到遗憾。

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

2010年9月4日,星期六

没收的过滤树

对于好消息和坏消息 过滤树 在存在约束的情况下,将成本敏感的多类分类(CSMC)简化为二进制分类。好消息是它可以应付 平均约束CSMC 稍加修改,通过无法选择的选择自动取消其锦标赛。坏消息是,没用的技巧不允许过滤树处理受minimax约束的CSMC,如以下所示。 反例 在下面。

对于平均约束的CSMC,此减少是针对重要性加权二进制分类的。这几乎与无约束的CSMC的过滤树减少相同,另外,不可行的选择会自动失去他们参加的任何锦标赛(如果两个参赛者都不可行,则可以任意选择一个)。由于该规则,仅调用底层的二进制分类器来区分可行的选择,而后悔分析本质上是相同的。
算法:没收过滤树火车
数据: 受约束的CSMC训练数据集$ S $。
输入: 重要性加权的二进制分类程序$ \ mbox {Learn} $。
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
结果: 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
  1. 从叶子到根的每个$ n \ in \ Lambda(T)$:
    1. $ S_n = \ emptyset $。
    2. 对于每个示例$(x,\ omega,c)\ in S $:
      1. 假设$ a $和$ b $是输入到$ n $的两个类(分别预测输入$(x,\ omega)$的左和右子树)。
      2. 如果$ a \ in \ omega $,为构造父节点的训练输入而预测$ b $(``$ a $ forfeits'');
      3. 否则,如果$ b \ in \ omega $中,则预测$ a $以便为父节点构建训练输入(``$ b $ forfeits'');
      4. 否则(当$ a \ not \ in \ omega $和$ b \ not \ in \ omega $时),$ S_n \ leftarrow S_n \ cup \ {(x,1_ {c_a<c_b},| c_a-c_b | )\} $;
    3. 令$ \ Psi_n = \ mbox {Learn}(S_n)$。
  2. 返回$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。

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

后悔分析

没收过滤器树的后悔分析与过滤器树的后悔分析非常相似,只是没收案件有其他理由。

平均约束CSMC问题的特征在于分布$ D = D_x \ times D _ {\ omega | x} \ times D_ {c | \ omega,x} $,其中$ c:K \ to \ mathbf {R} $扩展实数$ \ mathbf {R} = \ mathbb {R} \ cup \ {\ infty \} $中的值,以及特定实例的$ \ infty $值的$ c $组成部分将作为一部分显示通过$ \ omega \ in \ mathcal {P}(K)$确定问题实例(即$ \ omega $是$ K $的子集)。特定分类器$ h的遗憾:X \ times \ mathcal {P}(K)\ to K $由\ [r_ {av}(h)= E _ {(x,\ omega)\ sim D_x \ times给出D _ {\ omega | x}} \ left [E_ {c \ sim D_ {c | \ omega,x}} \ left [c(h(x,\ omega))-\ min_ {k \ in K} \ ,, E_ {c \ sim D_ {c | \ omega,x}} \ left [c(k)\ right] \ right] \ right]。 \] 令$ \ Psi =(T,\ {\ Psi_n | n \ in \ Lambda(T)\})$表示特定的没用过滤树(即,选择二叉树和一组特定的节点分类器) ,并让$ h ^ \ Psi $表示因没收过滤树而产生的分类器。

后悔分析利用三元组(x ^ \ prime,y,w)$上的诱导重要性加权二元分布$ D ^ \ prime(\ Psi)$,定义如下:
  1. 从$ D $绘制$(x,\ omega,c)$。
  2. 在二叉树的内部节点上绘制$ n $统一的。
  3. 设$ x ^ \ prime =(x,n)$。
  4. 假设$ a $和$ b $是输入到$ n $的两个类(分别预测输入$ x $的左和右子树)。
  5. 如果$ a在\ omega $中,则创建重要性加权的二进制示例$(x ^ \ prime,0,0)$;
  6. 否则,如果$ b \ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,1,0)$;
  7. 否则(当$ a \ not \ in \ omega $和$ b \ not \ in \ omega $时),创建重要性加权的二进制示例$(x ^ \ prime,1_ {c_a <c_b},| c_a-c_b |)$。
诱导分布$ D ^ \ prime(\ Psi)$取决于特定的没收过滤树,但是对于任何固定的没收过滤树都是很好定义的。现在,我想将受约束的CSMC后悔$ 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_ {n \ in \ Lambda(T)} E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [q_n(\ Psi | x,\ omega)\ right],\ end {aligned} \] 其中\ [q_n(\ Psi | x,\ omega)= \ begin {cases} 0&\ mbox {if} \ Gamma(n_l)\ setminus \ omega = \ emptyset \ mbox {或} \ Gamma(n_r)\ setminus \ omega = \ emptyset; \\ 0&\ mbox {if} \ Psi_n(x)= 1_ {E_ {c \ sim D_ {c | \ omega,x}}} [c_a]<E_ {c \ sim D_ {c | \ omega,x}} [c_b]}; \\ \左| E_ {c \ sim D_ {c | \ omega,x}} \ left [c_a-c_b \ right] \ right |&\ mbox {otherwise},\ end {cases} \] 和$ \ Gamma(n)$是指以$ n $为根的子树中的一组标签(叶),$ n_l $是$ n $的左子元素,而$ n_r $是$ n $的正确子代。

换句话说,如果$ n $的左子树或右子树完全由在该实例中不可行的标签组成,或者如果分类器做出了正确的决定,则在节点$ n $上没有重要性加权的遗憾。
定理:遗憾的结界
对于所有平均受限CSMC分布$ D $和所有没收的过滤树$ \ Psi $,\ [r_ {av}(h ^ \ Psi)\ leq(| K |-1)q(\ Psi),\]其中$ q(\ Psi)$是对引起的子问题的重要性加权二元遗憾。

证明: 看到 附录.
此界限与将未约束的CSMC降为重要性加权分类的过滤树还原基本相同,因此最终平均约束的CSMC不会比不受约束的CSMC困难(因为两者均缩减为具有相同后悔界限的二进制分类)。最终,这并不奇怪,因为平均约束CSMC本质上是不受约束的CSMC,其中增加了最高刑罚值($ \ infty $)和有关处罚地点的其他实例信息。但是,这很幸运,因为平均约束CSMC是将约束编码为约简的有用原语。

Minimax反例

为了显示没收技巧在minimax约束的CSMC上不起作用,请考虑具有3类和确定性成本向量$ c =(x,y,z)$和$ x的零特征空间问题< z <y $。进一步假设我们的二叉树首先玩1对2,然后玩(1对2的获胜者)对3。​​使用$ \ omega = \ emptyset $进行训练,没收的过滤树将学习从根和根获得两个左分支。选择1,导致CSMC遗憾为零。如果攻击者随后出现并在测试时设置$ \ omega = \ {1 \} $,则没收过滤器树将选择2造成遗憾,因为一旦1不可行,则3是最佳选择。

如果这听起来完全不公平,请记住,零后悔的回归降低可以在测试时处理任意施加的约束,而不会引起额外的后悔。这是因为回归不仅决定了最佳类别,而且实际上决定了所有类别的成本顺序。 (这并不意味着减少回归更好;实际上相反,它表明回归正在解决比通常需要的更困难的问题)。

这也表明与平均约束CSMC不同,minimax约束CSMC, 比不受约束的CSMC更难。

附录

这就是后悔的证明。考虑一个固定的$(x,\ omega)$。讨论在内部节点$ n $上平均受约束的CSMC后悔是有用的,\ [r_ {av}(h ^ \ Psi | x,\ omega,n)= E_ {c \ sim D_ {c | \ omega,x}} \ left [c(h_n ^ \ Psi(x,\ omega))\ right]-\ min_ {k \ in \ Gamma(n)} E_ {c \ sim D_ {c | \ omega,x }} \ left [c(k)\ right],\]其中$ h_n ^ \ Psi $是内部节点$ n $的预测。当$ n $是树的根时,$ r_ {av}(h ^ \ Psi | x,\ omega,n)$是在$(x,\ omega)$的条件下没收的过滤树平均约束CSMC后悔。证明策略是通过以下方式绑定$ r_ {av}(h ^ \ Psi | x,\ omega,n)\ leq \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)$感应。对于只有一片叶子(没有内部节点)的树,基本情况很容易满足,因为它的值为$ 0 \ leq 0 $。为了显示特定内部节点$ n $上的递归,令$ a $和$ b $为左子树($ n_l $)和右子树($ n_r $)的预测。

情况1:

$ \伽玛(n_l)\ setminus \ omega = \ emptyset $。在这种情况下,$ a \ in \ omega $并被没收,因此选择了$ b $。右子树中必须有一个最小化器,因为左子树中的所有值均为$ \ infty $。此外,对于$ m = n $和\ m在\ Lambda(n_l)$中,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} r_ {av}(h ^ \ Psi | x,\ omega,n)&= E_ {c \ sim D_ {c | \ omega,x}} \ left [c(b)\ right]-\ min_ {k \ in \ Gamma(n)} E_ {c \ sim D_ {c | \ omega ,x}} \ left [c(k)\ right] \\&= E_ {c \ sim D_ {c | \ omega,x}} \ left [c(b)\ right]-\ min_ {k \ in \ Gamma(n_r)} E_ {c \ sim D_ {c | \ omega ,x}} \ left [c(k)\ right] \\&= r_ {av}(h ^ \ Psi | x,\ omega,n_r)\\&\ leq \ sum_ {m \ in \ Lambda(n_r)} q_m(\ Psi | x,\ omega)\\&= \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]

情况2:

$ \ Gamma(n_l)\ setminus \ omega \ neq \ emptyset $和$ \ Gamma(n_r)\ setminus \ omega = \ emptyset $。在这种情况下,\ omega $中的$ b \和\ omega $中的$ a \不是\ omega $,因此选择了$ b $没收和$ a $。左子树中必须有一个最小化器,因为右子树中的所有值都是$ \ infty $。此外,对于$ m = n $和$ m \ in \ Lambda(n_r)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} r_ {av}(h ^ \ Psi | x,\ omega,n)&= E_ {c \ sim D_ {c | \ omega,x}} \ left [c(a)\ right]-\ min_ {k \ in \ Gamma(n)} E_ {c \ sim D_ {c | \ omega ,x}} \ left [c(k)\ right] \\&= E_ {c \ sim D_ {c | \ omega,x}} \ left [c(a)\ right]-\ min_ {k \ in \ Gamma(n_l)} E_ {c \ sim D_ {c | \ omega ,x}} \ left [c(k)\ right] \\&= r_ {av}(h ^ \ Psi | x,\ omega,n_1)\\&\ leq \ sum_ {m \ in \ Lambda(n_l)} q_m(\ Psi | x,\ omega)\\&= \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]

情况3:

$ \ Gamma(n_l)\ setminus \ omega \ neq \ emptyset $和$ \ Gamma(n_r)\ setminus \ omega \ neq \ emptyset $。这是``正常''的过滤树情况,其中$ a \ not \ in \ omega $和$ b \ not \ in \ omega $都没有,所以没收没收。不失一般性地假设分类器选择$ b $。如果最小化器来自正确的子树,则\ [\ begin {aligned} r_ {av}(h ^ \ Psi | x,\ omega,n)&= E_ {c \ sim D_ {c | \ omega,x}} \ left [c(b)\ right]-\ min_ {k \ in \ Gamma(n_r)} E_ {c \ sim D_ {c | \ omega ,x}} \ left [c(k)\ right] \\&= r_ {av}(h ^ \ Psi | x,\ omega,n_r)\\&\ leq \ sum_ {m \ in \ Lambda(n_r)} q_m(\ Psi | x,\ omega)\\&\ leq \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \] 如果最小化器来自左子树,则\ [\ begin {aligned} r_ {av}(h ^ \ Psi | x,\ omega,n)&= E_ {c \ sim D_ {c | \ omega,x}} \ left [c(b)\ right]-\ min_ {k \ in \ Gamma(n_l)} E_ {c \ sim D_ {c | \ omega ,x}} \ left [c(k)\ right] \\&= E_ {c \ sim D_ {c | \ omega,x}} \ left [c(b)-c(a)\ right] + r_ {av}(h ^ \ Psi | x,\ omega,n_1)\ \&= q_n(\ Psi | x,\ omega)+ r_ {av}(h ^ \ Psi | x,\ omega,n_l)\\&\ leq q_n(\ Psi | x,\ omega)+ \ sum_ {m \ in \ Lambda(n_l)} q_m(\ Psi | x,\ omega)\\&\ leq \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \] 在根处终止归纳会产生\ [r_ {av}(h ^ \ Psi | x,\ omega)\ leq \ sum_ {n \ in \ Lambda(T)} q_n(\ Psi | x,\ omega)= | \ Lambda(T)| q(\ Psi | x,\ omega)。 \] 考虑双方对$ D_x \ times D _ {\ omega | x} $的期望,并注意$ | \ Lambda(T)| =(| K |-1)$完成证明。

2010年9月1日,星期三

受约束的成本敏感:回归分析

在一个 以前的帖子 我介绍了两种版本的受约束的成本敏感型多类分类(CSMC):平均值,遗憾地\ \ left [E_ {c \ sim D_ {c | \ omega,x}} \ left [c(h(x,\ omega))-\ min_ {k \ in K} \; E_ {c \ sim D_ {c | \ omega,x}} \ left [c(k)\ right] \ right] \ right],\]和极小极大,遗憾的是\ [r_ {mm}(h)= E_ {x \ sim D_x} \ left [E _ {\ tilde c \ sim D _ {\ tilde c | x}} \ left [\ max _ {\ omega \ in \ mathcal {P}(K)} \ left \ {c( h(x,\ omega))-\ min_ {k \ in K} \; E _ {\\ t​​ilde c \ sim D _ {\\ t​​ilde c | x}} \ left [c(k(k)\ right] \ right \} \ right] \ right]。 \] 现在,我要说明两个结果,这并不奇怪。
结果:平均CSMC回归遗憾
对于所有平均受限CSMC分布$ D $,以及所有成本敏感的分类器$ h_g $都来自回归器$ g $,\ [r_ {av}(h_g)\ leq \ sqrt {2 | K | \ epsilon_ {L ^ 2}(g)},\]其中$ \ epsilon_ {L ^ 2}(g)$是基础回归问题的损失$ L ^ 2 $。

证明: 看到 平均分析 下面。
结果:Minimax 华润上华回归遗憾
对于所有受maxmax约束的CSMC分布$ D $,以及所有成本敏感的分类器$ h_g $都来自回归变量$ g $,\ [r_ {mm}(h_g)\ leq \ sqrt {2 | K | \ epsilon_ {L ^ 2}(g)},\]其中$ \ epsilon_ {L ^ 2}(g)$是基础回归问题的损失$ L ^ 2 $。

证明: 看到 极小极大分析 下面。
这些界限应该看起来很熟悉:它们与不受约束的CSMC情况相同。这些结果加在一起表明,回归减少对约束,甚至在应用程序时被强加的约束,实际上都是无所谓的。有趣的是,不受约束的CSMC的其他减少是否对于受约束的CSMC具有不同的属性。

平均分析

在这种情况下,存在分布$ D = D_x \ times D _ {\ omega | x} \ times D_ {c | \ omega,x} $,其中$ c:K \ to \ mathbf {R} $取值扩展的实数$ \ mathbf {R} = \ mathbb {R} \ cup \ {\ infty \} $,并且在特定实例中以$ \ infty $值对$ c $的组成部分进行了揭示。通过$ \ omega \ in \ mathcal {P}(K)$中的问题实例(即$ \ omega $是$ K $的子集)。特定分类器$ h的遗憾:X \ times \ mathcal {P}(K)\ to K $由\ [r_ {av}(h)= E _ {(x,\ omega)\ sim D_x \ times给出D _ {\ omega | x}} \ left [E_ {c \ sim D_ {c | \ omega,x}} \ left [c(h(x,\ omega))-\ min_ {k \ in K} \\; E_ {c \ sim D_ {c | \ omega,x}} \ left [c(k)\ right] \ right] \ right]。 \] 解决成本敏感型多类别分类器的argmax回归策略是函数$ g:X \ times \ mathcal {P}(K)\ times K \ to \ mathbf {R} $,它定义了相关的成本敏感型多分类器$ h_g:X \ times \ mathcal {P}(K)\ to K $根据\ [h_g(x,\ omega)= \ underset {k \ in K} {\ operatorname {arg \,min \;}} g(x,\ omega,k)。 \] 我想将$ r_ {av}(h_g)$约束在回归问题上的$ g $的遗憾上,\ [\ epsilon_ {L}(g)= q_ {L}(g)-\ min_g \; q_ {L}(g),\]其中$ q $是回归问题的误差\ [q_ {L}(g)= E _ {(x,\ omega,c)\ sim D} \ left [\ frac {1} {| K |} \ sum_ {k \ in K} L \ bigl(g(x,\ omega,k),c(k)\ bigr)\ right],\]和$ L $是损失回归问题的函数(在扩展实数上定义)。我将集中讨论通过扩展实数定义的回归变量通过$ L ^ 2(\ infty,\ infty)= 0 $,$ L ^ 2(\ infty,\ cdot)= \ infty $造成的$ L ^ 2 $损失,和$ L ^ 2(\ cdot,\ infty)= \ infty $。

考虑单个实例$(x,\ omega)$与相关的按实例成本向量分布$ D_ {c | \ omega,x} $,并假设我们的回归变量的成本估算值与最小误差回归变量的估算值$ c ^ *(x,\ omega,k)$ by $ \ delta(x,\ omega,k)$,\ [g(x,\ omega,k)= c ^ *(x,\ omega,k)+ \ delta(x,\ omega,k)。 \] 对于\ omega $中的$ k \ $,$ \ delta(x,\ omega,k)= 0 $,因为$ c ^ *(x,\ omega,k)$和我们的回归变量$ g(x,\ omega ,k)$将是$ \ infty $。关联的分类器$ h_g $为\ [h_g(x,\ omega)= \ underset {k \ in K} {\ operatorname {arg \,min \,}}} \ bigl(c ^ *(x,\ omega,k )+ \ delta(x,\ omega,k)\ bigr)。 \] 想象一个对手尝试在此实例上创建一定数量的CSMC后悔,同时将此实例上的回归遗憾的数量降至最低。该对手面临以下一系列问题,这些问题由$ k ^ {**} \ in K \ setminus \ omega $索引:\ [\ begin {aligned}&\min_{\delta}\;\ sum_ {k \ in K} \ delta(x,\ omega,k)^ 2 \\ \ mathrm {s.t。} \; \ forall k \ neq k ^ {**},\;& c^* (x, \omega, k^{**}) + \delta (x, \omega, k^{**}) \leq c^* (x, \omega, k) + \delta (x, \omega, k). \ end {aligned} \] This 是 the same as the unconstrained 华润上华 reduction to regression but with $k^{**}$ restricted to the set $K \setminus \omega$. When $|K \setminus \omega| \leq 1$, the 华润上华 regret 是 zero;否则,对手的策略将保持不变:干扰$ k ^ * $和$ k ^ {**} $的估算,而让其他人呆在那里。因此利用 先前的分析 产生\ [r_ {av}(h_g)\ leq \ sqrt {2 | K | \ epsilon_ {L ^ 2}(g)}。 \] 还应注意,在无约束的情况下,回归遗憾最多将是回归遗憾,因为$ \ omega $中包含的附加信息使回归者可以对$ k $的某些值进行完美估计。

极小极大分析

在这种情况下,分布为$ D = D_x \ times D _ {\\ t​​ilde c | x} $,其中$ \ tilde c:K \ to \ mathbb {R} $的取值以正实数$ \ mathbb {R } $。然后,一个对手进入,并通过将某些成分设置为$ \ infty $,在扩展实数$ \ mathbf {R} $中制造成本向量$ c $;在做出决定之前,这些选择会通过$ \ omega $显示出来。在这种情况下,特定分类器的遗憾由\ [r_ {mm}(h)= E_ {x \ sim D_x} \ left [E _ {\ tilde c \ sim D _ {\ tilde c | x}} \ left给出[\ max _ {\ omega \ in \ mathcal {P}(K)} \ left \ {c(h(x,\ omega))-\ min_ {k \ in K} \; E _ {\\ t​​ilde c \ sim D _ {\\ t​​ilde c | x}} \ left [c(k(k)\ right] \ right \} \ right] \ right]。 \] 考虑单个实例$ x $和相关的按实例成本向量分布$ D_ {c | x} $;此外,对手可以选择$ \ omega $来构建完整的问题实例$(x,\ omega)$。如上所述,回归器的成本估算与最小误差回归器的估算$ c ^ *(x,\ omega,k)$相差$ \ delta(x,\ omega,k)$,而当$ k \ in \ omega $估计是完美的,即$ \ delta(x,\ omega,k)= 0 $。

想象一个对手试图在这种情况下创建一定数量的CSMC后悔,同时将这种情况下的回归遗憾最小化。该对手面临着以下一系列问题,这些问题由$ \ omega $和$ k ^ {**} \ in K \ setminus \ omega $索引:\ [\ begin {aligned}&\min_{\delta}\;\ sum_ {k \ in K} \ delta(x,\ omega,k)^ 2 \\ \ mathrm {s.t。} \; \ forall k \ neq k ^ {**},\;& c^* (x, \omega, k^{**}) + \delta (x, \omega, k^{**}) \leq c^* (x, \omega, k) + \delta (x, \omega, k). \ end {aligned} \] Again when $|K \setminus \omega| \leq 1$, the 华润上华 regret 是 zero;否则,每个$ \ omega $的对手策略都是相同的,并且利用 先前的分析 产生\ [r_ {mm}(h_g)\ leq \ sqrt {2 | K | \ epsilon_ {L ^ 2}(h_g)}。 \]