显示带有标签的帖子 机器学习减少. 显示所有帖子
显示带有标签的帖子 机器学习减少. 显示所有帖子

2012年11月27日,星期二

解开您的乙状结肠

我和Nikos找出了如何将神经网络实现为 威杜布 减少。基本思想是为隐藏单元创建虚假示例,以使核心计算的损失函数的梯度与反向传播相对应。结果非常类似于神经网络学习的迭代加权最小二乘法 华纳和米斯拉。一个区别是,Warner和Misra专注于特定的二阶学习方案,而我们没有指定学习算法,我们只是将vee-dub核心视为GLM求解器,并在线构建增强设计矩阵。这使我们能够利用vee-dub中的不同学习算法,即SGD变体和L-BFGS。在单盒设置中,SGD通常比L-BFGS快,尤其是在vee-dub中实现的增强中。因此,使用L-BFGS娱乐的主要原因是分布式学习。

一些注意事项:
  1. 没有多余的装饰。一个隐藏层,激活功能为tanh,唯一的配置是隐藏单元数。
  2. 具有其他减少量的组合应该可以工作,但未经广泛测试。孤立地,归约进行二进制分类和回归。
  3. 它不是一个完整的狗,但是也不能尽可能快:可以进行更多优化。但是,如果您的问题是高维且稀疏的,则vee-dub的基本基础结构(即解析,哈希等)应在假设密集特征向量的神经网络实现方面取得重大胜利。
  4. 它应该与任何可用的损失函数和所有可用的学习算法变体一起工作。
  5. 二次方和ngram起作用,并应用于输入到隐藏层。

那些乐于解决玩具问题的人会很高兴知道vee-dub现在可以用两个隐藏单元解决3-parity。
pmineiro@pmineirovb-931% ./make-parity 3
-1 |f  1:1 2:-1 3:-1
-1 |f  1:-1 2:1 3:-1
1 |f  1:1 2:1 3:-1
-1 |f  1:-1 2:-1 3:1
1 |f  1:1 2:-1 3:1
1 |f  1:-1 2:1 3:1
-1 |f  1:1 2:1 3:1
1 |f  1:-1 2:-1 3:-1
pmineiro@pmineirovb-932% ./make-parity 3 | ../vowpalwabbit/vw --nn 2 --passes 2000 -k -c --cache_file cache -f model -l 10 --invariant                          final_regressor = model
Num weight bits = 18
learning rate = 10
initial_t = 1
power_t = 0.5
decay_learning_rate = 1
randomly initializing neural network output weights 和 hidden bias
creating cache_file = cache
Warning: you tried to make two write caches.  Only the first one will be made.
Reading from
num sources = 1
average    since         example     example  current  current  current
loss       last          counter      weight    label  predict features
1.550870   1.550870            3         3.0   1.0000  -1.0000        4
1.919601   2.288332            6         6.0   1.0000   0.7762        4
2.011137   2.120980           11        11.0   1.0000  -1.0000        4
2.154878   2.298620           22        22.0   1.0000   0.3713        4
2.354256   2.553635           44        44.0  -1.0000   1.0000        4
2.286332   2.216827           87        87.0  -1.0000   1.0000        4
2.222494   2.158657          174       174.0   1.0000   0.8935        4
1.716414   1.210335          348       348.0  -1.0000  -0.9598        4
1.368982   1.021549          696       696.0   1.0000   0.9744        4
1.151838   0.934694         1392      1392.0   1.0000   1.0000        4
0.976327   0.800816         2784      2784.0   1.0000   1.0000        4
0.756642   0.536958         5568      5568.0   1.0000   1.0000        4
0.378355   0.000000        11135     11135.0  -1.0000  -1.0000        4

finished run
number of examples = 16000
weighted example sum = 1.6e+04
weighted label sum = 0
average loss = 0.2633
best constant = -6.25e-05
total feature number = 64000
pmineiro@pmineirovb-933% ./make-parity 3 | ../vowpalwabbit/vw -i model -t -p /dev/stdout --quiet
-1.000000
-1.000000
1.000000
-1.000000
1.000000
1.000000
-1.000000
1.000000
-q ff,我可以对2个隐藏单位进行4个奇偶校验。哇

更加现实,我尝试 mnist。任务是对手写数字进行多类分类,因此我将“一无所有”归约法与神经网络归约法一起使用。原始像素值是不错的功能,因为数字已尺寸标准化并居中。示例行看起来像
pmineiro@pmineirovb-658% zcat test.data.gz | head -1
 |p 202:0.328125 203:0.72265625 204:0.62109375 205:0.58984375 206:0.234375 207:0.140625 230:0.8671875 231:0.9921875 232:0.9921875 233:0.9921875 234:0.9921875 235:0.94140625 236:0.7734375 237:0.7734375 238:0.7734375 239:0.7734375 240:0.7734375 241:0.7734375 242:0.7734375 243:0.7734375 244:0.6640625 245:0.203125 258:0.26171875 259:0.4453125 260:0.28125 261:0.4453125 262:0.63671875 263:0.88671875 264:0.9921875 265:0.87890625 266:0.9921875 267:0.9921875 268:0.9921875 269:0.9765625 270:0.89453125 271:0.9921875 272:0.9921875 273:0.546875 291:0.06640625 292:0.2578125 293:0.0546875 294:0.26171875 295:0.26171875 296:0.26171875 297:0.23046875 298:0.08203125 299:0.921875 300:0.9921875 301:0.4140625 326:0.32421875 327:0.98828125 328:0.81640625 329:0.0703125 353:0.0859375 354:0.91015625 355:0.99609375 356:0.32421875 381:0.50390625 382:0.9921875 383:0.9296875 384:0.171875 408:0.23046875 409:0.97265625 410:0.9921875 411:0.2421875 436:0.51953125 437:0.9921875 438:0.73046875 439:0.01953125 463:0.03515625 464:0.80078125 465:0.96875 466:0.2265625 491:0.4921875 492:0.9921875 493:0.7109375 518:0.29296875 519:0.98046875 520:0.9375 521:0.22265625 545:0.07421875 546:0.86328125 547:0.9921875 548:0.6484375 572:0.01171875 573:0.79296875 574:0.9921875 575:0.85546875 576:0.13671875 600:0.1484375 601:0.9921875 602:0.9921875 603:0.30078125 627:0.12109375 628:0.875 629:0.9921875 630:0.44921875 631:0.00390625 655:0.51953125 656:0.9921875 657:0.9921875 658:0.203125 682:0.23828125 683:0.9453125 684:0.9921875 685:0.9921875 686:0.203125 710:0.47265625 711:0.9921875 712:0.9921875 713:0.85546875 714:0.15625 738:0.47265625 739:0.9921875 740:0.80859375 741:0.0703125
这是一些结果。 \ [
\ begin {array} {c | c | c}
\ mbox {模型}&\ mbox {测试错误}&\ mbox {注意} \\ \ hline
\ mbox {线性}&\ mbox {848}&\\
\ mbox {Ngram}&\ mbox {436}&\ verb!--ngram 2-跳过1! \\
\ mbox {二次}&\ mbox {301}和\ verb!-q pp! \\
\ mbox {NN}&\ mbox {273}&\ verb!-nn 40!
\ end {array}
\] 二次方可提供良好的结果,但训练起来却是s-l-o-w(每个示例都有>10000个功能)。 NGram增强了二次方的功能,并且相当活泼(由于编码,它们是水平n元语法;垂直n元语法也可能会有所帮助)。 40个隐藏单元神经网络的性能优于二次方,并且训练速度也更快。命令行调用如下所示:
pmineiro@pmineirovb-74% ./vw --oaa 10 -l 0.5 --loss_function logistic --passes 10 --hash all -b 22 --adaptive --invariant --random_weights 1 --random_seed 14 --nn 40 -k -c --cache_file nncache train.data.gz -f nnmodel

2012年6月26日,星期二

关于链接预测的思考

我正在读Richard等的论文。等来自 ICML 2012论文清单同时稀疏和低秩矩阵的估计。我不确定为什么直到现在我仍将这两个想法混为一谈,但回想起来,它们显然是不同的,并且可能要针对这两个进行优化。自从 潜在特征日志线性 Mennon和Elkan(LFLL)模型本质上是一种低阶矩阵分解算法,我想知道如何在其中同时执行稀疏性;我认为在潜在功能上使用$ L_1 $正则化函数可能值得尝试。

但是,这篇论文也让我思考了链接预测。这是这篇论文的引文:
链接预测 -矩阵$ A $是部分观测图的邻接矩阵;不存在和未发现的链接的条目均为0。搜索空间像以前一样不受限制,矩阵$ S $包含链接预测的分数;理想损耗函数是每个系数的零一损耗的经验平均值\ [
l_ {E}(S,A)= \ frac {1} {| E |} \ sum _ {(i,j)\ in E} 1 _ {(A_ {ij}-1/2)\ cdot S_ {ij} \ leq 0}。
\]
所以我读为,``这是一个 P-U问题 我们正在简化为逐点分类。'' 首选方法 对于P-U问题,是降低到排名(AUC损失)。链接预测会是什么样?
  1. 实例是边(即,成对的顶点加上二进位的特定信息)。
  2. 减少AUC是成对分类,即成对的边或成对的顶点。
  3. 邻接图中的每个正(观察)边都将与未标记(未观察或未开发)边配对,后者可能从所有可能的边上均匀地绘制;或可能从给定一个顶点的所有可能边缘开始(``每个顶点AUC'')。
  4. 最终的分类模型可以是纯粹的潜伏模型(例如,纯LFLL),也可以是纯粹由特征驱动的模型(例如,使用 大众)或组合(例如带有辅助信息的LFLL)。
    1. 根据我的经验,与纯粹的LLFL不同,带有辅助信息的LLFL很难训练。

下次我遇到链接预测问题时,我将稍作讨论。

2012年1月6日,星期五

成本敏感型二进制分类和主动学习

现在,出现了多种针对二进制分类的主动学习算法,现在是时候问什么 机器学习减少 可以说关于其他类型学习问题的主动学习。现在,我将重点介绍对成本敏感的二进制分类,其目标是与\ [
h ^ * = \ mathop {\ operatorname {arg \,min \;}} _ {h \ in H} E _ {(X,Y,\ Upsilon)\ sim D} [\ Upsilon 1_ {h(X)\ neq Y}],
\] 其中$ X $是要素,$ Y \ in \ {0,1 \} $是标签,$ \ Upsilon \ in [0,c_ {max}] $是成本,$ D $是未知的分布。

成本可见

首先,我假设我们可以在未标记的数据中看到费用,即无需查询标签。这在实践中并不常见,因为成本通常取决于标签(例如,误报要比误报要贵)。但是,这将为可能的情况提供一些直觉。

我可以使用拒绝采样来 将对成本敏感的分类降低为二进制分类 然后应用主动学习二进制分类器。具体来说,我可以以接受概率$ \ Upsilon_k / c_ {max} $拒绝输入流的样本,如果样本被接受,它将丢弃成本并使用二进制分类。这是后悔变换,其将所引起的二进制后悔按比例缩放$ E [$]。因此,如果我们很有可能后悔在给定$ n $个示例的情况下将$ r_b(n)$绑定到基础活动二进制分类器中,则大概替换$ n \ rightarrow(E [\ Upsilon] / c_ {max})n + O( \ frac {1} {n} \ log \ frac {1} {\ delta})$并按$ E [\ Upsilon] $缩放会给我们带来很大的可能性$ r_c(n)$问题,\ [
r_c(n)= E [\ Upsilon] r_b \ left(\ frac {E [\ Upsilon]} {c_ {max}} n + O(\ frac {1} {n} \ log \ frac {1} {\ delta})\ right)。
\]
同时,在拒绝的情况下,我们绝对不会查询标签$ Y_k $。在不拒绝的情况下,我们可以查询标签$ Y_k $,具体取决于在诱导的主动二进制分类器中使用标签的可能性。如果在给定$ n $实例的情况下,在诱导二进制分类器$ l_b(n)$的标签复杂度上具有较高的概率界限,则大概替换$ n \ rightarrow(E [\ Upsilon / c_ {max})n + O (\ frac {1} {n} \ log \ frac {1} {\ delta})$将给标签复杂度$ l_c(n)$带来高的概率边界,该复杂度是原始成本敏感问题\ [
l_c(n)= l_b \ left(\ frac {E [\ Upsilon]} {c_ {max}} n + O(\ frac {1} {n} \ log \ frac {1} {\ delta})\ right )。
\] 这是一种用于主动学习的元算法,具有成本敏感的二进制分类和可见的成本。
算法:可见成本案例
具有可见成本和主动学习二进制oracle $ \ mathcal {O} $的主动成本敏感型二进制分类的拒绝采样。
  1. 以成本$ \ Upsilon_k $获得未标记的数据点$ X_k $。
  2. 用$ \ mathrm {Pr}(\ mathrm {heads))=(\ Upsilon_k / c_ {max})$掷一个偏向硬币。
    1. 如果是正面,请将未标记的特征$ X_k $传递给$ \ mathcal {O} $。
    2. 如果有尾巴,则丢弃未标记的数据点。

如果二进制oracle使用 不受约束的不可知主动学习,这种推理暗示了类似\ [
\ mathrm {err} _c(h_n)\ leq \ mathrm {err} _c(h ^ *)+ O \ left(\ sqrt {c_ {max} E [\ Upsilon] \ frac {\ log n} {n}} \对)
\] 是可能的,其中\ [
\ mathrm {err} _c(h)= E _ {(X,Y,\ Upsilon)\ sim D} [\ Upsilon 1_ {h(X)\ neq Y}],
\] 和诸如[[
\ mbox {要求标签} \ leq 1 + \ theta \ cdot \ frac {2} {c_ {max}} \ mathrm {err} _c(h ^ *)n + O \ left(\ theta \ sqrt {\ frac { E [\ Upsilon]} {c_ {max}} n \ log n} \ right)
\] 是可能的。这里的$ \ theta $是引起的二进制子问题的分歧系数。

费用不可见

现在,我假设仅在查询标签时才可以使用成本。假设我们决定通过首先根据底层主动学习算法接受或拒绝,然后再查询标签并观察到成本$ \ Upsilon_k $,然后掷出另一枚硬币并以概率$(\ Upsilon_k接受,来实施上述拒绝抽样程序/ c_ {max})$。这将与无形成本约束相一致,但在结果方面相同。如果成本可见,这将是愚蠢的,但如果成本不可见,这是可行的策略。后悔的界限仍然是相同的,但是不幸的是,现在引起的二元问题的标签复杂度通过未经修改的$ l_c(n)= l_b(n)$。当然,标签的复杂性 游戏中的主动学习,否则我们将查询每个标签并获得金标准的被动学习后悔。因此,对于一个特定的后悔界限,具有更差的标签复杂性是非常不希望的。

算法:无形成本案
具有不可见成本和主动学习二进制oracle $ \ mathcal {O} $的主动成本敏感型二进制分类的拒绝采样。
  1. 获取未标记的数据点$ X_k $。
  2. 将未标记的数据点$ X_k $传递到$ \ mathcal {O} $,并拦截\ {0,1 \} $中的决策$ Q_k \ in查询标签。
    1. 如果$ Q_k = 0 $,则不执行任何操作。
    2. 如果$ Q_k = 1 $,
      1. 查询标签并观察$ \ Upsilon_k $和$ Y_k $。
      2. 用$ \ mathrm {Pr}(\ mathrm {heads))=(\ Upsilon_k / c_ {max})$掷一个偏向硬币。
        1. 如果是正面,将标签$ Y_k $传递给$ \ mathcal {O} $,这在$ Q_k = 1 $时可以预期。
        2. 如果有尾巴,则丢弃标签并将$ X_k $的表示``撤消''到$ \ mathcal {O} $。

特别是对于使用不受约束的不可知主动学习的基础学习者,这种推理建议何时看不到成本,\ [
\ mbox {要求标签} \ leq 1 + \ theta \ cdot \ frac {2} {E [\ Upsilon]} \ mathrm {err} _c(h ^ *)n + O \ left(\ theta \ sqrt {n \ log n} \ right)。
\] 两种标签复杂度的比较表明,在“智能”成本敏感型主动学习算法和“智能”成本不可实现的情况下,我们可能会获得$(E [\ Upsilon] / c_ {max})$的改进。这里勾勒出的``哑巴''。

2011年6月23日,星期四

减少AUC到逐点回归

查尔斯·埃尔坎洛杉矶机器学习聚会昨天。在演讲之前,我们正在讨论AUC损失的排名问题。众所周知 归结为成对分类 导致AUC后悔界限为$ 2 r $,其中$ r $是对归类分类问题的遗憾。查尔斯说,在实践中,他通过简化为逐点逻辑回归获得了很好的结果,即估计``相关概率''并使用归纳排名。他推测后勤损失实际上是在某种程度上限制了AUC损失,这是因为它给数据点提供了有效的重要性权重(高表示``令人惊讶'',低表示``不令人惊讶'');有趣的是,它比平方损失要好得多;铰链丢失根本不起作用。关于铰链损耗的观察是有道理的,因为已知减少逐点分类并不可靠。但是平方或逻辑损失呢?

因此,在考虑减少量时,存在一个一致性问题:对引起的子问题零后悔会导致对原始问题的零后悔吗?由于平方和逻辑损失是 正确的评分规则,一致性在直觉上是可能的。但是,对于嘈杂的问题,还存在效率问题。换句话说,对引发问题的后悔如何限制对原始问题的后悔?

物流损失是棘手的,但是平方损失我取得了一些进展。假设从$ S = X \ times Y $中抽取示例对,其中$ Y = \ {0,1 \} $根据分布$ D_ {S \ times} = D_x \ times D_ {y | x} \ times D_x \ times D_ {y | x} $。如果您熟悉排名问题,那么您可能正在调整,因为在实践中很少有明确的逐点相关性二进制概念。但是,由于我正在谈论归结为点回归的减少,因此我将假设它可以取得进展。

我现在要修复$ x_1 $和$ x_2 $,最后我会期望$ D_ {x | 0} \ times D_ {x | 1} $。给定分类器$ h:S \ to \ mathbb {R} $,条件AUC损失由\ [
\ mathrm {AUC}(h | x_1,x_2)= E _ {(y_1,y_2)\ sim D _ {(y_1,y_2)| (x_1,x_2)}} \ left [\ left(1_ {y_1> y_2} 1_{h (x_1) < h (x_2)} + 1_{y_1 < y_2} 1_{h (x_1) >h(x_2)} \ right)\ right]。
\] 同时平方损失由\ [
L_2(h | x_1,x_2)= E _ {(y_1,y_2)\ sim D _ {(y_1,y_2)| (x_1,x_2)}} \ left [\ sum_k y_k(1-h(x_k))^ 2 +(1-y_k)h(x_k)^ 2 \ right]。
\]
不失一般性地假定$ h(x_1)<h(x_2)$。然后有条件的AUC损失变为\ [
\ mathrm {AUC}(h_1,h_2,p_1,p_2)= p_1(1-p_2),
\] 其中$ h_k = h(x_k)$和$ p_k = p(y_k = 1 | x_k)$。最佳AUC损失由\ [
\ mathrm {AUC}(h_1,h_2,p_1,p_2)= \ begin {cases}
p_1(1-p_2)和\ mbox {if} p_1 \ leq p_2,\\
(1-p_1)p_2& \mbox{if } p_1 > p_2.
\ end {cases}
\] ,因此AUC后悔由\ [
r_ \ mathrm {AUC} = \ max \ left(p_1-p_2,0 \ right)。
\] 同时对分类器的平方损失遗憾是\ [
\ begin {aligned}
r_2(h; x_1,x_2)&= \sum_k r_2 (h_k;x_k)= \ sum_k(p_k-h_k)^ 2。
\ end {aligned}
\] 作为对手,我的目标是针对给定的平方损失后悔最大化AUC后悔。要解决的程序是\ [\ max_ {p_1,p_2,h_1,h_2}(p_1-p_2)\]受\ [
\ begin {aligned}
p_2-p_1&\ leq 0,\\
h_1-h_2&\ leq 0,\\
\ sum_k(p_k-h_k)^ 2&= r_2 (h; x_1, x_2).
\ end {aligned}
\] 通过 KKT条件 (感谢Mathematica!)产生解\ [
\ begin {aligned}
h_1&= h_2,\\
h_2&= \ frac {p_1 + p_2} {2},\\
p_1-p_2&= \sqrt{2 r_2 (h; x_1, x_2)}.
\ end {aligned}
\] 这就是说,对手的最佳选择是将$ h_1 $和$ h_2 $放置在$ p_1 $和$ p_2 $的均值之上和之下的$ \ epsilon $;这让人联想到 中位数选民定理。在这种情况下,AUC的遗憾是\ [
r _ {\ mathrm {AUC}}(h; x_1,x_2)\ leq \ sqrt {2 r_2(h | x_1,x_2)}。
\] 现在我可以对两边的$ D_ {x | 0} \ times D_ {x | 1} $做出期望,\ [
\ begin {aligned}
r _ {\ mathrm {AUC}}(h)&\leq E_{(x_1, x_2) \sim D_{x|0} \times D_{x|1}} \left[ \sqrt{2 r_2 (h;x_1,x_2)} \ right] \\
&\leq \sqrt{ 2 E_{(x_1, x_2) \sim D_{x|0} \times D_{x|1}} \left[ r_2(h; x_1,x_2)\right] } \\
&= \sqrt{2 \left( E_{x \sim D_{x|0}} \left[ r (h;x)\ right] + E_ {x \ sim D_ {x | 1}} \ left [r(h; x)\ right)\ right)} \\
&= 2 \sqrt{E_{x \sim \tilde D_x} \left[ r (h; x) \right]} \\
&= 2 \ sqrt {\ tilde r_2(h)}
\ end {aligned}
\] 这里$ D_ {x | y} $是给定标签$ y $的$ x $的条件分布,$ \ tilde D_x = \ frac {D_ {x | 0} + D_ {x | 1}} {2 } $是$ x $的类平衡分布,而$ \ tilde r_2(h)$是基础分类器相对于$ \ tilde D_x $的平方误差后悔。那么这是什么意思?
  • 如果针对类平衡的数据集(即相同数目的正负数)计算平方损失后悔,则此分析仅保证减少平方损失的一致性。这可以通过例如重要性加权或拒绝采样来实现。不平衡的数据集可能会出现问题,例如,当使用几乎完全是负样本的数据集和一个正样本的数据集时,基础数据集的平均每样本均方差损失后悔与AUC后悔规模之间的界限为数据集(因为在一个积极的例子上的重要性越来越大,但被忽略了)。
  • 后悔界限对潜在遗憾具有平方根依赖性,这比成对归类到分类时对潜在遗憾的线性依赖性更差。

您可能会想到,后勤损失不适合该技术。但是,我开始欣赏查尔斯发表评论的直觉。想象一下一个在线学习场景,一个物流学习者在不考虑他们的班级标签的情况下就被不断地输入示例。如果数据集非常不平衡,例如学习者大多是负面的,他们将很快收敛于一个高度负面的常数。这将有效降低负面示例的学习率,而正面示例将保持较高的学习率。这模仿了对数据加权以进行类平衡的重要性操作。如何将这种直觉转化为正式声明?

2011年5月10日,星期二

成本敏感的多标签:观察

我遇到了一个成本敏感的多标签分类(CSML)问题,即有一组标签$ K $,我要将其中的任何一个或全部分配给实例(在我的情况下是文本文档) 。一种方法是将其视为标签$ \ mathcal {P}(K)$的幂集上的成本敏感的多类分类(CSMC)问题。到那时,我可以使用过滤树简化为二进制分类。这具有一些优点,例如一致性(对子问题引起的零后悔意味着对原始问题的零后悔)。它还具有实质性的缺点,既有理论上的(遗憾的常量是缩放为$ O(2 ^ {| K |})$),也有实践上的(最一般的实现方式是时间复杂度缩放为$ O(2 ^ { | K |})$)。

另一种流行的方法是在测试时学习$ | K | $独立的二进制分类器,在测试时独立查询它们,并输出并集。它具有很好的实用属性(时间复杂度缩放为$ O(| K |)$)。但是将问题分解为一组 独立 子问题通常是造成不一致减少的公式,因此我对这种方法感到怀疑。

因此,这是一个有趣的观察:在以下条件下,学习一组独立的二进制分类器等效于CSMC问题上的过滤树方法。
  1. 过滤树是 评分过滤树,即每个节点的分类符为\ [
    \ Phi(x)= 1_ {f(x; \ lambda)> f (x; \phi)}.
    \]
  2. 得分函数进一步分解为一组加权的指标函数,\ [
    f(x; \ lambda)= \ sum_ {k \ in K} 1_ {k \ in \ lambda} f_k(x)
    \]
  3. 华润上华问题的损失函数为 汉明损失.
  4. 构造该树使得在$ k $级别,每个节点的两个输入仅在$ K $的$ k ^ {\ mathrm {th}} $元素存在或不存在时有所不同。考虑到$ \ mathcal {P}(K)$的元素为位字符串,级别为$ k $的比赛正在决定二进制扩展中的$ k ^ {\ mathrm {th}} $位。

在这种情况下,将发生以下情况。在$ k ^ \ mathrm {th} $级别上,锦标赛全部在各组之间进行,只是其$ k ^ \ mathrm {th} $有效位不同。此级别上每个节点的分类器的格式为\ [
\ Phi(x)= 1_ {f_k(x)> 0}
\] ,并且此级别上所有子问题的所有重要性权重都相同(因为使用了汉明损失)。因此,树的整个$ k ^ \ mathrm {th} $级相当于一个二元分类器,该分类器独立地学习是否将$ K $的$ k ^ \ mathrm {th} $元素包括到最终结果中。

因此,好消息是:这意味着如果汉明损失是CSML问题的损失函数,则学习独立的二进制分类器是一致的。当然,后悔界限中的常数很大,并且分类器的结构假设很重要,因此在实践中性能可能会很差。

那其他损失函数呢?如果保留了分类器的结构假设,则仍可以使用单个二进制分类器来总结过滤树的每个级别。但是,馈送到此分类器的示例的重要性权重取决于先前级别的分类器的输出。

例如,考虑整个标签集的0-1损失。在树的最低层,唯一具有非零重要性权重(成本差异)的锦标赛是考虑是否在所有其他标签正确的情况下包括第一个标签的锦标赛。在树的第二层,唯一可能具有非零重要性权重的锦标赛是考虑是否在所有其他标签正确的条件下包括第二标签的锦标赛。但是,如果第一个分类器出错,则此条件将不会过滤树,所有重要权重将为零。通常,一旦分类器之一出错,训练就会停止。因此,培训过程可以大致概括为:
  1. 给定训练数据$(x,Y)\ X \ times \ mathcal {P}(K)$,
  2. 对于每个$ k = 1 \ ldots | K | $
    1. 令$ \ hat y_k $为标签$ k $是否在目标集中的分类器$ k $的预测。
    2. 将$(x,1_ {k \ in Y})$添加到分类器$ k $的训练集中。请注意,所有非零重要性权重均为1,因此这只是二进制分类。
    3. 如果$ \ hat y_k \ neq 1_ {k \ in Y} $,则停止对此训练基准重复$ k $。
如果分类器经常犯错误,则最终将数据抽取到无用的地步。抛开这个问题,此过程在直观上令人愉悦,因为它不会在链中的后续阶段浪费分类器资源,而这些决策根据整个集合的0-1损失无关紧要。

2011年3月30日,星期三

减少过滤树:Perl实现

最近我一直在用以下方法解决多分类问题 誓言 用一个 机器学习减少。理想情况下,我将使用vowpal提供的减少API在C中对此进行编程。在实践中,vowpal不断变化。因此,为了隔离自己,我一直将vowpal视为我通过IPC与之通信的黑匣子。这种方法有一个缺点:如果我在vowpal内实施减少(基于top的输出),我估计我的总吞吐量至少会大4倍。希望John和他们的工作人员将在不久的将来提供稳定的vowpal减少API。

同时,尽管有点麻烦,但我在这里提出的减少仍然是切实可行的。另外,有时只是看到某种实现可以使这些概念具体化,所以我想在此介绍一下简化的概念。

策略

起点是 过滤树减少 成本敏感的多类分类对重要性加权二元分类的解释。在这种减少中,类别标签被安排为三月疯狂的锦标赛,获胜者扮演获胜者,直到一个类别标签获胜:这就是最终的预测。当两个类别标签``相互竞争''时,真正发生的是重要性加权分类器根据关联实例特征$ x $决定谁获胜。

实际上,我使用的是一种特殊的过滤树 评分过滤树。在这里,重要性加权分类器被限制为\ [
\ Psi _ {\ nu}(x)= 1_ {f(x; \ lambda)> f (x; \phi)}.
\] 这里的$ \ lambda $和$ \ phi $是两个“互相比赛”的标签,以查看谁在锦标赛中晋级。该方程式表示的是:
  1. 有一个函数$ f $,它告诉每个类标签实例具有$ x $的性能。
  2. 更好的类别标签总是胜过其他类别标签。
这意味着根据$ f $,比赛的获胜者是最好的球队。这使得$ f $看起来像是一个得分函数(就像从argmax回归中获得的一样),并且基本上可以在测试时忽略锦标赛的结构。在火车上使用比赛是至关重要的,但是对于在嘈杂的问题(即低后悔)上获得良好的表现至关重要。

实施

我假设我们正在尝试在$ | K | $标签之间进行分类,这些标签由整数$ \ {1,\ ldots,| K | \} $表示。我还将假设输入格式与vowpal的本机输入格式非常相似,但是使用的是成本向量而不是标签。 \ [
c_1,\ ldots,c_ {| K |} \; \ textrm {importance} \; \ textrm {tag} | \ textrm {namespace} \; \ textrm {功能} \ ldots
\] 因此,例如3类问题输入行可能看起来像\ [
0.7,0.2,1.3 \; 0.6 \; \ textrm {idiocracy} | \ textrm {items} \; \ textrm {hotlatte} \; | \ textrm {desires} \; \ textrm {i} \; \ textrm {like} \; \ textrm {money}
\] 最好的选择(最低的费用)是2。

测试时间
应用模型比训练模型更容易理解,所以我将从这里开始。在perl中,我将其转换为一组vowpal输入行,其中每行对应于特定的类标签$ n $,\ [
\; \ textrm {tag} | \ textrm {namespace} n \; \ textrm {功能} \ ldots
\] 本质上,成本向量和重要性权重被去除(因为现在没有学习发生),标记被去除(我将单独处理),并且每个命名空间都附加了类标签。由于vowpal使用第一个字母来标识名称空间,因此对名称空间进行操作的选项(例如-q,-ignore)将继续按预期运行。因此,例如继续上面的示例,我们将生成三行\ [
| \ textrm {items} 1 \; \ textrm {hotlatte} \; | \ textrm {desires} 1 \; \ textrm {i} \; \ textrm {like} \; \ textrm {money} \; | \ _1 \; ķ
\] \ [
| \ textrm {items} 2 \; \ textrm {hotlatte} \; | \ textrm {desires} 2 \ ;; \ textrm {i} \; \ textrm {like} \; \ textrm {money} \; | \ _2 \; ķ
\] \ [
| \ textrm {items} 3 \; \ textrm {hotlatte} \; | \ textrm {desires} 3 \; \ textrm {i} \; \ textrm {like} \; \ textrm {money} \; | \ _3 \; ķ
\] 这些行中的每行都输入到vowpal,并且具有最低vowpal输出的类别标签被选为比赛的获胜者。命名空间_中的最后一个功能$ k $提供了常量功能的类标签本地化版本,vowpal在每个示例中默默提供了该功能。

火车时间
在火车上,我基本上是参加比赛的:但是由于我知道实际的花费,所以我根据谁``应该赢了''来更新分类器。更新的重要性权重由刚刚参加比赛的两个团队之间的成本绝对差值确定。因此,对于两个类别标签$ i $和$ j $,将有一个训练输入馈入形式为\ [
1 \; \ omega \; \ textrm {tag} | \ textrm {namespace $ i $:1} \; \ textrm {功能} \ ldots | \ textrm {namespace $ j $:-1} \; \ textrm {功能} \ ldots | \ textrm {\ _ $ i $:-1} \; k \; | \ textrm {\ _ $ j $:-1} \; ķ
\] 其中$ \ omega = \ textrm {重要性} * \ mbox {abs}(c_i-c_j)$,即,原始重要性权重由实际成本中的绝对差来衡量。在这里,我利用了在名称空间上提供权重的功能,该权重乘以名称空间中所有功能的权重。 (vowpal始终提供的那种讨厌的常量功能呢?它仍然存在并且实际上不应该。正确的处理方法是修补vowpal以接受不提供常量功能的选项。但是我想呈现一些适用于未修补的vowpal的内容,因此我改为输入另一项训练输入,并将所有取反,以使恒定特征保持接近零。)

当一支球队赢了一场比赛,他们本不应该赢,他们仍然在锦标赛中前进。直观地,分类器需要从比赛中先前犯的错误中恢复过来,所以这是正确的做法。

少了什么东西
以下是我要改进的一些内容:
  1. 在vowpal内部实现,而不是通过IPC在外部实现。
  2. 在实现中,我根据特定的班级手动设计比赛。自动构建锦标赛会更好。
  3. 有一种简洁的方法来指定稀疏成本向量会很好。例如,当所有错误同样严重时,所需要做的就是正确标签的标识。
  4. 上述策略不适用于铰链损耗,我也不知道为什么(它似乎适用于平方损耗和逻辑损耗)。可能是我在某个地方犯了一个错误。买者自负!

编码

有两部分:
  • 誓言.pm:这封装了与vowpal的通信。您将需要它来使其正常工作,但主要是无聊的Unix IPC东西。
    • 检测底层vw未能成功启动不是很好(例如,由于尝试加载不存在的模型)。但是,由于挂起,您会注意到这一点。
  • 过滤树:归约实现实际存在的perl脚本。您可以调用它来开始。通常,它与vw本身采用相同的参数,只是将它们传递出去,但有一些例外:
    1. 您必须从标准输入读取数据。我可以截取--data参数并模拟它们,但是我不知道。
    2. 由于前面的语句,您不能使用--passes参数。
    3. 我确实截取了-p参数(用于输出预测),并在归约级别上对此进行了仿真。

您从过滤树看到的输出看起来像来自大众的输出,但事实并非如此。它实际上来自perl脚本,并且被设计为类似于针对多类情况进行适当修改的vw输出。

这是一个示例调用:
% zcat traindata.gz | head -1000 | ./filter-tree --adaptive -l 1 -b 22 --loss_function logistic -f model.users.b22  
average    since       example  example    current  current  current
loss       last        counter   weight      label  predict features
1.000000   1.000000          1      1.0     1.0000   0.0000       16
0.500000   0.000000          2      2.0     1.0000   1.0000       15
0.500000   0.500000          4      4.0     2.0000   1.0000       20
0.375000   0.250000          8      8.0     2.0000   2.0000       19
0.562500   0.750000         16     16.0     5.0000   2.0000       23
0.437500   0.312500         32     32.0     0.0000   1.0000       14
0.281250   0.125000         64     64.0     1.0000   1.0000       16
0.312500   0.343750        128    128.0     0.0000   1.0000       16
0.347656   0.382812        256    256.0     1.0000   1.0000       13
0.322266   0.296875        512    512.0     1.0000   1.0000       20

finished run
number of examples = 1000
weighted examples sum = 1000
average cost-sensitive loss = 0.287
average classification loss = 0.287
best constant for cost-sensitive = 1
best constant cost-sensitive loss = 0.542
best constant for classification = 1
best constant classification loss = 0.542
minimum possible loss = 0.000
confusion matrix
15      1       0       1       0       1       0
77      416     53      23      5       0       1
14      41      281     56      8       3       2
0       0       0       1       0       1       0
0       0       0       0       0       0       0
0       0       0       0       0       0       0
0       0       0       0       0       0       0
-p参数输出制表符分隔的一组列。第一列是预测的类标签,接下来的$ | K | $列是每个类标签的评分函数值,最后一列是实例标签。

通常,源代码(最好)是最好的文档。

过滤树

#! /usr/bin/env perl

use warnings;
use strict;

use 誓言;

$SIG{INT} = sub { die "caught SIGINT"; };

# if this looks stupid it 是: these used to be actual class names,
# but i didn't want to release code with the actual class labels that i'm using
use constant {
  ZERO => 0,
  ONE => 1,
  TWO => 2,
  THREE => 3,
  FOUR => 4,
  FIVE => 5,
  SIX => 6, 
};

sub argmin (@)
{
  my (@list) = @_;
  my $argmin = 0;

  foreach my $x (1 .. $#list)
    {
      if ($list[$x] < $list[$argmin])
        {
          $argmin = $x;
        }
    }

  return $argmin;
}

sub tweak_line ($$)
{
  my ($suffix, $rest) = @_;

  $rest =~ s/\|(\S*)/\|${1}${suffix}/g;

  return $rest;
}

sub train_node ($$$$$$$$$)
{
  my ($m, $la, $lb, $pa, $pb, $ca, $cb, $i, $rest) = @_;

  my $argmin = ($ca < $cb) ? -1 : 1;
  my $absdiff = abs ($ca - $cb);

  if ($absdiff > 0)
    {
      chomp $rest;
      my $w = $i * $absdiff;

      my $plusone = 1;
      my $minusone = -1;
      my $chirp = (rand () < 0.5) ? 1 : -1;

      $argmin *= $chirp;
      $plusone *= $chirp;
      $minusone *= $chirp;

      $m->send ("$argmin $w",
                tweak_line ("${la}:$plusone", " |$rest |_ k"),
                tweak_line ("${lb}:$minusone", " |$rest |_ k\n"))->recv ()
      or die "vowpal failed to respond";

      $argmin *= -1;
      $plusone *= -1;
      $minusone *= -1;

      $m->send ("$argmin $w",
                tweak_line ("${la}:$plusone", " |$rest |_ k"),
                tweak_line ("${lb}:$minusone", " |$rest |_ k\n"))->recv ()
      or die "vowpal failed to respond";
   }

  return $pa - $pb;
}

sub print_update ($$$$$$$$)
{
  my ($total_loss, $since_last, $delta_weight, $example_counter, 
      $example_weight, $current_label, $current_predict, 
      $current_features) = @_;

  printf STDERR "%-10.6f %-10.6f %8lld %8.1f   %s %8.4f %8lu\n",
         $example_weight > 0 ? $total_loss / $example_weight : -1,
         $delta_weight > 0 ? $since_last / $delta_weight : -1,
         $example_counter,
         $example_weight,
         defined ($current_label) ? sprintf ("%8.4f", $current_label) 
                                  : " unknown",
         $current_predict,
         $current_features;
}

#---------------------------------------------------------------------
#                                main                                 
#---------------------------------------------------------------------

srand 69;

my @my_argv;
my $pred_fh;

while (@ARGV)
  {
    my $arg = shift @ARGV;
    last if $arg eq '--';

    if ($arg eq "-p")
      {
        my $pred_file = shift @ARGV or die "-p argument missing";
        $pred_fh = new IO::File $pred_file, "w" or die "$pred_file: $!";
      }
    else
      {
        push @my_argv, $arg;
      }
  }

my $model = new 誓言 join " ", @my_argv;

print STDERR <<EOD;
average    since       example  example    current  current  current
loss       last        counter   weight      label  predict features
EOD

my $total_loss = 0;
my $since_last = 0;
my $example_counter = 0;
my $example_weight = 0;
my $delta_weight = 0;
my $dump_interval = 1;
my @best_constant_loss = map { 0 } (ZERO .. SIX);
my @best_constant_classification_loss = map { 0 } (ZERO .. SIX);
my $minimum_possible_loss = 0;
my $classification_loss = 0;
my $mismatch = 0;
my %confusion;

while (defined ($_ = <>))
  {
    my ($preline, $rest) = split /\|/, $_, 2;

    die "bad preline $preline" 
      unless $preline =~ /^([\d\.]+)?\s+([\d\.]+\s+)?(\S+)?$/;

    my $label = $1;
    my $importance = $2 ? $2 : 1;
    my $tag = $3;

    my ($actual_tag, @costs) = split /,/, $tag;

    die "bad tag $tag" unless @costs == 0 || @costs == 8;

    my @scores = 
      map { my $s = $model->send (tweak_line ($_, " |$rest |_ k"))->recv ();
            chomp $s;
            $s
          } (ZERO .. SIX);
    my $current_prediction = argmin @scores;

    if (@costs == 8)
      {
        # it turned out better for my problem to combine classes 6 和 7.
        # costs are already inverted 和 subtracted from 1, so, 
        # have to subtract 1 when doing this
        
        my $class_seven = pop @costs;
        $costs[SIX] += $class_seven - 1;

        # zero level

        my $zero_one = train_node ($model,
                                   ZERO,
                                   ONE,
                                   $scores[ZERO],
                                   $scores[ONE],
                                   $costs[ZERO],
                                   $costs[ONE],
                                   $importance,
                                   $rest) <= 0
                       ? ZERO : ONE;

        my $two_three = train_node ($model,
                                    TWO,
                                    THREE,
                                    $scores[TWO],
                                    $scores[THREE],
                                    $costs[TWO],
                                    $costs[THREE],
                                    $importance,
                                    $rest) <= 0
                        ? TWO : THREE;

        my $four_five = train_node ($model,
                                    FOUR,
                                    FIVE,
                                    $scores[FOUR],
                                    $scores[FIVE],
                                    $costs[FOUR],
                                    $costs[FIVE],
                                    $importance,
                                    $rest) <= 0
                        ? FOUR : FIVE;

        # SIX gets a pass

        # first level: (zero_one vs. two_three), (four_five vs. SIX)

        my $fleft = train_node ($model,
                                $zero_one,
                                $two_three,
                                $scores[$zero_one],
                                $scores[$two_three],
                                $costs[$zero_one],
                                $costs[$two_three],
                                $importance,
                                $rest) <= 0
                    ? $zero_one : $two_three;

        my $fright = train_node ($model,
                                 $four_five,
                                 SIX,
                                 $scores[$four_five],
                                 $scores[SIX],
                                 $costs[$four_five],
                                 $costs[SIX],
                                 $importance,
                                 $rest) <= 0
                     ? $four_five : SIX;

        # second level: fleft vs. fright

        my $root = train_node ($model,
                               $fleft,
                               $fright,
                               $scores[$fleft],
                               $scores[$fright],
                               $costs[$fleft],
                               $costs[$fright],
                               $importance,
                               $rest) <= 0
                   ? $fleft : $fright;

        $total_loss += $importance * $costs[$root];
        $since_last += $importance * $costs[$root];
        $example_weight += $importance;
        $delta_weight += $importance;

        my $best_prediction = argmin @costs;

        foreach my $c (ZERO .. SIX)
          {
            $best_constant_loss[$c] += $importance * $costs[$c];
            if ($c != $best_prediction)
              {
                $best_constant_classification_loss[$c] += $importance;
              }
          }

        $minimum_possible_loss += $importance * $costs[$best_prediction];
        $classification_loss += ($current_prediction == $best_prediction) ? 0 : 1;
        ++$confusion{"$current_prediction:$best_prediction"};

        ++$mismatch if $root ne $current_prediction;
      }

    print $pred_fh (join "\t", $current_prediction, @scores, $actual_tag), "\n"
      if defined $pred_fh;

    ++$example_counter;
    if ($example_counter >= $dump_interval)
      {
        my @features = split /\s+/, $rest;         # TODO: not really

        print_update ($total_loss, 
                      $since_last,
                      $delta_weight,
                      $example_counter,
                      $example_weight,
                      (@costs) ? (argmin @costs) : undef,
                      $current_prediction,
                      scalar @features);

        $dump_interval *= 2;
        $since_last = 0;
        $delta_weight = 0;
      }
  }

my $average_loss = sprintf "%.3f", $example_weight > 0 ? $total_loss / $example_weight : -1;

my $best_constant = argmin @best_constant_loss;
my $best_constant_average_loss = sprintf "%.3f", $example_weight > 0 ? $best_constant_loss[$best_constant] / $example_weight : -1;

my $best_constant_classification = argmin @best_constant_classification_loss;
my $best_constant_classification_average_loss = sprintf "%.3f", $example_weight > 0 ? $best_constant_classification_loss[$best_constant_classification] / $example_weight : -1;

my $minimum_possible_average_loss = sprintf "%.3f", $example_weight > 0 ? $minimum_possible_loss / $example_weight : -1;

my $classification_average_loss = sprintf "%.3f", $example_weight > 0 ? $classification_loss / $example_weight : -1;

print <<EOD;

finished run
number of examples = $example_counter
weighted examples sum = $example_weight
average cost-sensitive loss = $average_loss
average classification loss = $classification_average_loss
best constant for cost-sensitive = $best_constant
best constant cost-sensitive loss = $best_constant_average_loss
best constant for classification = $best_constant_classification
best constant classification loss = $best_constant_classification_average_loss
minimum possible loss = $minimum_possible_average_loss
confusion matrix
EOD
#train/test mismatch = $mismatch

foreach my $pred (ZERO .. SIX)
  {
    print join "\t", map { $confusion{"$pred:$_"} || 0 } (ZERO .. SIX);
    print "\n";
  }

誓言.pm

# 誓言.pm

package 誓言;

use warnings;
use strict;

use POSIX qw (tmpnam mkfifo);
use IO::File;
use IO::Pipe;
use IO::Poll;

sub new ($$)
{
  my $class = shift;
  my $args = shift;

  my $pred_pipename = tmpnam () or die $!;
  my $pred_pipe = mkfifo ($pred_pipename, 0700) or die $!;
  my $pred_fd = POSIX::open ($pred_pipename, 
                             &POSIX::O_RDONLY | 
                             &POSIX::O_NONBLOCK | 
                             &POSIX::O_NOCTTY) or die $!;
  my $pred_fh = new IO::Handle;
  $pred_fh->fdopen ($pred_fd, "r") or die $!;
  POSIX::fcntl ($pred_fh, 
                &POSIX::F_SETFL, 
                POSIX::fcntl ($pred_fh, &POSIX::F_GETFL, 0) & ~&POSIX::O_NONBLOCK);

  my $data_fh = new IO::Pipe or die $!;
  open my $oldout, ">&STDOUT" or die "Can't dup STDOUT: $!";
  eval
    {
      open STDOUT, ">", "/dev/null" or die "Can't redirect STDOUT: $!";
      eval
        {
          open my $olderr, ">&STDERR" or die "Can't dup STDERR: $!";
          eval
            {
              open STDERR, ">", "/dev/null" or die "Can't redirect STDERR: $!";
              $data_fh->writer ("vw $args -p $pred_pipename --quiet") or die $!;
              $data_fh->autoflush (1);
            };
          open STDERR, ">&", $olderr or die "Can't restore STDERR: $!";
          die $@ if $@;
        };
      open STDOUT, ">&", $oldout or die "Can't restore STDOUT: $!";
      die $@ if $@;
    };
  die $@ if $@;

  my $poll = new IO::Poll;
  $poll->mask ($data_fh => POLLOUT);
  $poll->poll ();
  $poll->remove ($data_fh);
  $poll->mask ($pred_fh => POLLIN);

  my $self = { data_fh => $data_fh,
               pred_fh => $pred_fh,
               pred_file => $pred_pipename,
               poll => $poll,
               args => $args };

  bless $self, $class;
  return $self;
}

sub send ($@)
{
  my $self = shift;

  $self->{'data_fh'}->print (@_);

  return $self;
}

sub recv ($)
{
  my $self = shift;

  $self->{'poll'}->poll ();
  return $self->{'pred_fh'}->getline ();
}

sub DESTROY
{
  my $self = shift;

  $self->{'data_fh'}->close ();
  $self->{'pred_fh'}->close ();
  unlink $self->{'pred_file'};
}

1;

2010年12月5日,星期日

成本敏感的最佳M的SFF树

约翰·兰福德 最近向我发送了一个有用的建议。
另一种方法是引入代表性的hack。假设我们将成对分类器定义为:$ w_ {left} x_ {left}-w_ {right} x_ {right} $。然后,过滤树的输出为$ \ underset {a} {\ operatorname {arg \,max \,}} w_a x_a $,其形式与回归相同。但是,我们以不同的方式训练事物,以实现较低的后悔$ \ ldots $
与该建议相关的探索方向很多。这是我的一些曲折。

SFF树:定义

我将此建议称为计分没收过滤器(SFF)树。类比是当使用评分功能定义线性排序以减少对分类的排名时。这是一个更精确的定义。
定义:SFF树
SFF树是 没收过滤树 $\Psi$ where 在 each internal node $\nu$ the importance-weighted classifier 是 of the form \[ \Psi_\nu (x) = 1_{f (x; \lambda) > f (x; \phi)}
\] 其中$ \ lambda $和$ \ phi $是输入到$ \ nu $的两个类(分别是左和右子树的预测)。函数$ f $称为计分函数,并且在每个内部节点处都相同(但对于每个操作而言都不同)。

John的建议的妙处在于,可以在测试时通过$ h ^ \ Psi(x,\ omega)= \ underset {k \ in K \ setminus \ omega} {\ operatorname {arg \,max \,}} f(x; k)$看起来就像如何计算输出以进行回归归约。但是后悔的界限更好,因为训练的过程是不同的。

SFF树 平均约束CSMC

由于SFF树是没用的过滤树,因此 后悔 上的“没收过滤器”树 平均约束CSMC 问题成立,即\ [r_ {av}(h ^ \ Psi)\ leq(| K |-1)q(\ Psi),\]其中$ q(\ Psi)$是重要性加权二元遗憾引起的子问题。这与 回归遗憾,\ [r_ {av}(h_g)\ leq \ sqrt {2 | K | \ epsilon_ {L ^ 2}(g)},\]其中$ \ epsilon_ {L ^ 2}(g)$是基础回归问题的损失$ L ^ 2 $。

因此,一开始这似乎很神奇(即,可以将其视为获得更好的回归指标的一种方法),但是我将其理解为训练过程,将子问题预言集中在重要的问题上(例如,区分best和$ 2 ^ \ mathrm { nd} $每个实例的最佳操作),而忽略不存在的问题(例如,准确估计$(n-1)^ \ mathrm {th} $和$ n ^ \ mathrm {th} $最差的选择的值)。

在实践中,强制SFF树中的分类器基于评分函数可能会导致难以学习对诱导子问题的低遗憾解决方案。评分函数在所有内部节点上共享的事实是简化输出计算的关键,但与普通的没收树不同。在原始情况下,很容易设想通过$ \ log_2(| K |)$顺序遍历以从下到上的方式训练树,每次遍历定义内部节点的下一级别的训练数据,并且每次遍历在特定深度训练一组内部节点。但是,现在不同级别的分类器是交织在一起的。

我实际上不确定如何处理这个问题,并且直到尝试尝试时我才知道。凭直觉,如果我要在线上逐步更新热模型,我会尝试忽略依赖关系,而仅应用更新。动机是我每次更新都会进行微小的更改,所以我忽略的是``高阶微小''。当然,决策边界处的大量非线性有点令人不安(并且不是很小)。从冷开始但仍使用在线学习算法(针对脱机数据),我尝试从下到上的方式通过$ \ log_2(| K |)$,在一定深度前热启动整个树在下一个更高的深度训练任何内部节点。与普通情况不同,每次通过都会训练所有内部节点达到一定深度,而不仅仅是训练特定深度的内部节点。希望能奏效,但如果失败了,我会考虑使用softmax风格的方法来减轻决策边界的非线性,例如$ p(\ Psi_ \ nu = 1 | x)= 1 /(1 + e ^ {-\ beta(f(x; \ lambda)-f(x; \ psi))})$并将$ \ beta $退火为$ \ infty $。

SFF树 平均约束CSBM

平均约束CSBM 是在给定实例的情况下选择前$ m $个操作的问题。通过构造分类器列表$ \ {\ Psi_n | |,可以将其减少到受约束的平均CSMC。 n \ in [1,m] \} $每个都经过训练,以选择最佳动作,下一个最佳动作等。

所以这是一个有趣的事情:如果我们在分类器列表中设置$ \ Psi_n = \ Psi $,并且如果我们的平均约束CSMC分类器是SFF树,那么我们可以通过\ [h ^ \ Psi(x, \ omega)= \ underset {k \ in K \ setminus \ omega} {\ operatorname {arg \,max \,^ m}} f(x; k),\]在这里我用符号$ \ operatorname {arg \,max \,^ m} $代表选择前$ m $个元素。同样,这正是在测试时将采用基于回归约简的方法的方式。但是遗憾的界限还是不同的。当将平均约束CSBM减小为平均约束CSMC时, 后悔 是\ [r_ {csbm}(h ^ \ Psi)\ leq m \,q(\ Psi,m),\]其中$ q(\ Psi,m)$是对$ m $的平均成本敏感后悔平均约束CSMC子问题(这些问题又可以简化为重要性加权分类,从而保持对后悔的线性依赖)。相反,当简化为回归 后悔 是\ [r_ {csbm}(h_g)\ leq \ sqrt {2 \ min \ {m,| K | -m \}} \ sqrt {| K |} \ sqrt {\ epsilon_ {L ^ 2}(g)},\]其中$ \ epsilon_ {L ^ 2}(g)$是$ L ^ 2 $的损失关于潜在的回归问题。

因此,我们再次保证可以采用不同的训练程序来获得更好的回归值,但是子问题之间的依存关系也存在类似的问题,使训练画面复杂化。在将CSBM简化为CSMC的典型情况下,每个分类器将按顺序进行训练,并为下一个分类器定义训练输入分布。现在所有分类器都相同,因此需要一些技巧。

再说一次,我实际上不确定如何处理这个问题,直到尝试了一些事情,我才知道。凭直觉,我将再次尝试在线上逐步更新热模型,而忽略依赖关系。对于将离线模型应用于在线模型的冷启动,我将首先针对top-1问题,然后针对top-2问题进行培训,直到达到top- $ m $。有趣的是,如何看待我的两个直观过程的组成如何进行完整的冷启动:
  1. 对于$ n $ in $ [1,m] $
    1. 为$ l $ in $ [\ log_2(| K |),1] $
      1. 更新$ l ^ \ mathrm {th} $和更低级别的内部节点,以解决同时选择顶部$ n $动作的问题
      2. 更新$ l ^ \ mathrm {th} + 1 $和更高级别的内部节点,以解决选择前$(n-1)$个操作的问题。
总共$ m \ log_2(| K |)$通过了数据,这很合理。外循环用于减轻由$ \ Psi_n = \ Psi $创建的依赖关系,而内循环用于减轻在所有内部节点之间共享$ f $所创建的依赖关系。

现在,我想我应该在一些实际数据上尝试一下。

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)$, 和 suppose the tree first pairs $\{1, 2\}$ while giving 3 a pass, 和 then 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年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)$完成证明。