2010年8月27日,星期五

从n个候选人中选择m个广告

好吧,我有一些 随机最短路径的乐趣 (SSP)最近没有资源,这很奇怪,因为我现在实际上没有适合SSP的任何问题:它更像是一个成本敏感的多类分类(CSMC)与更复杂的离散优化问题之间的有趣的转折点,我希望扩大我的理解。

我之前处理过的一个问题看起来与SSP相似,即从$ n $个候选广告中挑选$ m $个广告的问题。忽略位置效应和广告间的外部性,其特征在于后悔函数\ [r_ {ad}(h)= E _ {(x,f)\ sim D} \ left [\ sum_ {k = 1} ^ mf( h_k(x))\ right]-\ min_ {h \ in X \ to S_m} E _ {(x,f)\ sim D} \ left [\ sum_ {k = 1} ^ mf(h_k(x))\ right],\]其中$ S_m = \ {a \ in A ^ m | \ i \ neq j \ Rightarrow a_i \ neq a_j \} $是可行结果向量的集合,$ A $是广告的集合,并且$ h:X \ to S_m $是结果向量选择函数,$ x $是与问题实例相关的功能,$ f $是与问题实例相关的每个广告的(负)费用,$ D = D_x \ D_ {f | x} $是问题实例的分布。将此称为广告选择问题(ASP)。

减少回归 回到我最初遇到此问题时(超过10年前),减少回归似乎是解决此问题的自然方法(唯一?)。 ASP的回归归约是函数$ g:X \ times A \ to \ mathbb {R} $,它定义了关联的结果向量,选择函数$ h_g:X \ to S_m $通过\ [h_g(x)= \ underset { h \ in S_m} {\ operatorname {arg \,min \,}} \ sum_ {k = 1} ^ mg(x,h_k)。 \]换句话说,估算值,然后选择成本最低$ m $的广告(任意打破联系)。我想对潜在的回归问题\ [\ epsilon_ {L}(g)= \ nu_ {L}(g)-\ min_g \;表示遗憾,以此来限制$ r_ {ad} $ \ nu_ {L}(g),\]是根据基本回归问题的误差定义的\ [\ nu_L(g)= E _ {(x,f)\ sim D} \ left [\ frac {1} { | A |} \ sum_ {a \ in A} L(g(a),f(a))\ right]。 \]使用类似于用来分析 无需回归即可减少SSP,我可以显示以下内容。
定理:ASP回归遗憾
对于所有ASP分布$ D $和回归变量$ g $,\ [r_ {ad}(h_g)\ leq \ sqrt {2 \ min \ {m,| A | -m \}} \ sqrt {| A |} \ sqrt {\ epsilon_ {L ^ 2}(g)}。 \] 证明: 看到 附录.
熟悉的平方根对回归后悔的依赖再次出现。如果您需要选择几乎所有广告,则可以决定选择“空洞”,从而导致$ \ min \ {m,| A |。 -m \} $项。

减少到CSMC 尽管ASP的回归减少分析与没有资源的SSP非常相似,但随后将ASP降低为CSMC的一致减少与没有资源的CSP的减少没有太大相似之处。

正是唯一性约束使一系列CSMC子问题的构建受挫,因此,我将使用$ A ^ m $而不是使用$ S_m $进行操作,但我将指出同一广告的重复出现次数为零值。对于结果向量选择器$ \ tilde h:X \到A ^ m $,我们将重复敏感的后悔关联到\ [\ begin {aligned} \ tilde r_ {ad}(\ tilde h)&= E_{(x, f) \sim D} \left[ \sum_{k=1}^m f (h_k (x)) \prod_{j<k} 1_ {h_k(x)\ neq h_j(x)} \ right] \\&\quad - \min_{h \in X \to A^m} E_{(x, f) \sim D} \left[ \sum_{k=1}^m f (h_k (x)) \prod_{j<k} 1_ {h_k(x)\ neq h_j(x)} \ right]。 \ end {aligned} \]假设所有费用严格都是非正数的(即,每个广告都具有非负值显示),则最小化器中将不会有重复项,因此$ r_ {ad}(h)= \ tilde r_ {ad}(h)$,表示范围为$ S_m $的任何$ h $。因此,该策略将通过CSMC减少来约束$ \ tilde r_ {ad} $,然后强制所获知识的$ h $仅接受$ S_m $的值。

培训收益从1轮到$ m $;在每一轮中,一个对成本敏感的分类器正在学习选择仍然可用的最佳广告。允许选择已经选择的广告,但提供零增量值。在测试时,每个回合的分类器都会要求选择一个广告;遇到的任何重复项都将被丢弃,并替换为随机的唯一广告。此重复数据删除过程可确保$ r_ {ad}(h ^ \ Psi)\ leq \ tilde r_ {ad}(\ tilde h ^ \ Psi)$,其中$ \ tilde h ^ \ Psi:X \ to A ^ m $是可能重复生成的学习结果生成器,而$ h ^ \ Psi:X \ to S_m $是学习结果生成器的重复数据删除版本。通常,只要成本有上限,此技巧就会起作用。

算法:设置选择火车
数据: 候选人设置了$ A $,即填充$ m $的职位数。
数据: 训练数据集$ S $。
输入: 成本敏感的分类例程$ \ mbox {Learn} $。
结果: 经过训练的分类器$ \ {\ Psi_k | k \ in [1,m] \} $。
  1. 定义$ \ gamma_0(\ cdot)= \ emptyset $。
  2. 对于每个头寸$ k $从1到$ m $:
    1. $ S_k = \ emptyset $。
    2. 对于每个示例$(x,f)\ in S $:
      1. 令$ \ gamma_ {k-1}(x)$为前一次迭代的最佳预测集。
      2. 对于每个广告$ a $,令$ c_a(x,k)= 1_ {a \ not \ in \ gamma_ {k-1}(x)} f(a)$。
      3. $ S_k \ leftarrow S_k \ cup \ left \ {\ bigl(x,c(x,k)\ bigr)\ right \} $。
    3. 令$ \ Psi_k = \ mbox {Learn}(S_k)$。
    4. 令$ \ gamma_k(x)= \ Psi_k(x)\ cup \ gamma_ {k-1}(x)$。
  3. 返回$ \ {\ Psi_k | k \ in [1,m] \} $。
评论: 如果$ S_k $的输入为$(x,\ gamma_ {k-1}(x))$,即在明确告知分类器已经选择了哪些广告的情况下,这样做可能会更好。

算法:设置选择测试
数据: 候选人设置了$ A $,即填充$ m $的职位数。
数据: 实例功能实现$ x $。
数据: 经过训练的分类器$ \ {\ Psi_k | k \ in [1,m] \} $。
结果: 将$ h ^ \ Psi:X \设置为S_m $。
  1. $ \ tilde h_k ^ \ Psi(x)= \ Psi_k(x)$。
  2. $ h ^ \ Psi(x)= \ mbox {Dedup}(\ tilde h ^ \ Psi(x))$
    1. 例如,随机地将重复的广告替换为唯一的广告。
我的目标是限制重复敏感的遗憾\ [\ begin {aligned} \ tilde r_ {ad}(\ tilde h)&= E_{(x, f) \sim D} \left[ \sum_{k=1}^m f (\tilde h_k (x)) \prod_{j<k} 1 _ {\\ t​​ilde h_k(x)\ neq \ tilde h_j(x)} \ right] \\&\quad - \min_{\tilde h \in X \to A^m} E_{(x, f) \sim D} \left[ \sum_{k=1}^m f (\tilde h_k (x)) \prod_{j<就引起子问题的成本敏感遗憾而言,k} 1 _ {\\ t​​ilde h_k(x)\ neq \ tilde h_j(x)} \ right] \ end {aligned} \]。我将再次利用过滤器树派生的技巧,通过定义归纳分布将多个子问题折叠为一个子问题。设$ D = D_x \ times D_ {f | x} $为$(x,f)$的分布。定义$ \ Psi((x,k))= \ Psi_k(x)$,并定义成本敏感示例$ {x ^ \ prime,c)的诱导分布$ D ^ \ prime({\ Psi})$ $如下:
  1. 从$ D $中提取$(x,f)$。
  2. 在$ [1,m] $上绘制$ k $制服。
  3. 设$ x ^ \ prime =(x,k)$。
  4. 令$ c(a)= 1_ {a \ not \ in \ gamma_ {k-1}(x)} f(a)$为$ a \ in A $。
  5. 创建成本敏感的示例$(x ^ \ prime,c)$。
注意$ D ^ \ prime(\ Psi)$通过重复惩罚取决于分类器,但是对于任何固定的分类器来说,定义都很好。最终,我想将重复敏感的遗憾$ \ tilde r_ {ad}(\ tilde h ^ \ Psi)$与诱导的成本敏感的遗憾\ [\ begin {aligned} q(\ Psi)相关联&= E_{x^\prime \sim D^\prime_x (\Psi) } \left[ E_{c \sim D^\prime_{c|x} (\Psi)} \left[ c (\Psi (x^\prime)) \right] - \min_{a \in A}\;E_ {c \ sim D ^ \ prime_ {c | x}(\ Psi)} \ left [c(a)\ right] \ right] \\&= \frac{1}{m} \sum_{k=1}^m q_k (\Psi), \end{aligned} \] where \[ \begin{aligned} q_k (\Psi) &= E_{x \sim D_x} [ q_k (\Psi | x) ], \\ q_k (\Psi | x) &= E_{f \sim D_{f|x}} \left[ 1_{\Psi_k (x) \not \in \gamma_{k-1} (x)} f (\Psi_k (x)) \right] - \min_{a \in A}\;E_ {f \ sim D_ {f | x}} \ left [1_ {a \ not \ in \ gamma_ {k-1}(x)} f(a)\ right]。 \ end {aligned} \]
定理:ASP CSMC后悔绑定
对于所有ASP分布$ D $,其中$ f \ leq 0 $ a.s.,对于所有成本敏感的分类器$ \ Psi $,\ [r_ {ad}(h ^ \ Psi)\ leq m \,q(\ Psi)。 \]证明: 考虑一个固定的$ x $。讨论$ \ tilde r_k(\ tilde h ^ \ Psi | x)$,对于大小为$ k $的结果,重复敏感的遗憾,\ [\ begin {aligned} \ tilde r_k(\ tilde h ^ \ Psi | x)&= E_{f \sim D_{f|x}} \left[ \sum_{n=1}^k f (\Psi_n (x)) \prod_{j <n} 1 _ {\ Psi_n(x)\ neq \ Psi_j(x)} \ right] \\&\quad - \min_{h \in A^k}\;E_ {f \ sim D_ {f | x}} \ left [\ sum_ {n = 1} ^ k f(h_n)\ prod_ {j<n} 1_ {h_n \ neq h_j} \ right]。 \ end {aligned} \]令\ [h ^ *(k,x)= \ underset {h \ in A ^ k} {\ operatorname {arg \,min \,}} E_ {f \ sim D_ {f | x}} \ left [\ sum_ {n = 1} ^ kf(h_n)\ prod_ {j<n} 1_ {h_n \ neq h_j} \ right] \]是第二项的最小化项(在排列和联系上是唯一的);请注意,相对于有条件的预期费用,任何$ h ^ *(k,x)$都会选择最小的$ k $广告。然后\ [\ begin {aligned} \ tilde r_k(\ tilde h ^ \ Psi | x)-\ tilde r_ {k-1}(\ Psi | x)&= E_{f \sim D_{f|x}} \left[ f (\Psi_k (x)) \prod_{j <k} 1 _ {\ Psi_k(x)\ neq \ Psi_j(x)} \ right] \\&\quad - \min_{a \in A}\;E_ {f \ sim D_ {f | x}} \ left [f(a)\ prod_ {j<k} 1_ {a \ neq h ^ * _ j(k-1,x)} \ right] \\&\leq E_{f \sim D_{f|x}} \left[ f (\Psi_k (x)) \prod_{j <k} 1 _ {\ Psi_k(x)\ neq \ Psi_j(x)} \ right] \\&\quad - \min_{a \in A}\;E_ {f \ sim D_ {f | x}} \ left [f(a)\ prod_ {j<k} 1_ {a \ neq \ Psi_j(k)} \ right] \\&= q_k(\ Psi | x),\ end {aligned} \]其中不等式源自$ h ^ *的最优性(k- 1,x)$。由于$ \ tilde r_1(\ tilde h ^ \ Psi | x)= q_1(\ Psi | x)$,因此我们有\ [\ tilde r_ {ad}(\ tilde h ^ \ Psi | x)= \ tilde r_m( \ tilde h ^ \ Psi | x)\ leq \ sum_ {k = 1} ^ m q_k(\ Psi | x)= m \,q(\ Psi | x)。 \]期望$ D $,并注意$ f \ leq 0 $a.s。表示$ r_ {ad}(h ^ \ Psi)\ leq \ tilde r_ {ad}(\ tilde h ^ \ Psi)$完成了证明。
我怀疑存在对孔进行归约的版本,因此实际的超前项是$ \ min \ {m,| A | -m \} $。

减少是一致的,但效率低下。这是因为通过CSMC简化为回归会导致$ m \ sqrt {| A |} \ sqrt {\ epsilon_ {L ^ 2}} $界,而简化为回归会导致$ \ sqrt {m} \ sqrt {| A |} \ sqrt {\ epsilon_ {L ^ 2}} $的边界,比$ \ sqrt {m} $更好。

每当$ f $是a.s时,此技术也将起作用。由于可以从所有成本中减去该常数,从而在A.s. $ f \ leq 0 $。有效地需要一种机制来惩罚约束违例(创建重复项),并保证其成本为可能的最坏的成本。这样,就可以保证对约束违反的任何更正都可以改善针对原始遗憾的解决方案。 (更新资料:重新阅读此内容后,我感觉条件较弱$ E_ {f \ sim D_ {f | x}} [f(a)] \ leq 0 $对于所有$ a $和a.s。 $ x $就足够了)。

上述减少量假设i.i.d.从$ D $中删除是不现实的,因为在实践中,我们仅看到与所显示广告相关的值。因此,真正酷的是将这种减少与 偏移树 得到解决热启动问题的方法。

另一个不切实际的注意事项:在实际的广告投放设置中,候选广告集的波动性很大,例如,由于预算用尽或每位用户的频次上限。回归回归非常自然地解决了这一问题(通过限制argmax的范围)。在CSMC中处理此问题较为尴尬,但如果过滤率适中,则学习200万美元的分类器就足够了(这也可以允许使用更好的简化策略)。减少回归也可以很好地解决将新广告引入系统的问题(假设特征空间使回归器合理地推广到新颖广告),而且我对如何使CSMC减少能够处理这一点没有很好的想法。


附录: 这是回归减少分析。

考虑具有关联值分布$ D_ {f |的实例$ x $。 x} $,并假设我们的回归变量与最小误差回归变量的估计$ f ^ *(a)$相差$ \ delta(a)$,则所有$ a \ in A $,\ [g(a)= f ^ * (a)+ \ delta(a)。 \]想象一个对手尝试在此实例上创建一定量的ASP后悔,同时将此实例上的回归后悔量最小化。具体来说,对于$ L ^ 2 $的损失,对手面临以下由$ h ^ {**} $,\ [\ begin {aligned} &\min_{\delta}\;\ sum_ {a \ in A} \ delta(a)^ 2 \\ \ mathrm {s.t。} \; \ forall h \ neq h ^ {**},\; &\ sum_ {a \ in h ^ {**}} f ^ *(a)+ \ delta(a)\ leq \ sum_ {a \ in h} f ^ *(a)+ \ delta(a),\ end {aligned} \]其中$ h ^ {**} $对应于$ h_g $做出的决定。这种简化利用了$ L ^ 2 $损失的特殊性质,即后悔最小化估计量是条件均值,$ f ^ *(a)= E_ {f \ sim D_ {f | x}} [f(a)] $ 。

KKT平稳性条件表示\ [2 \ delta(a)+ \ sum_ {h \ neq h ^ {**}}(1_ {a \ in h ^ {**}}-1_ {a \ in h})\ mu_h =0。\]补充松弛表示$ \ mu_h = 0 $除非$ h $的约束处于活动状态。设$ h ^ * = \ operatorname {arg \,min \,} _ {h \ in S_m} E_ {f \ sim D_ {f | x}} [\ sum_ {a \ in h} f(a)] $是真正的最佳路径选择,在这种情况下,只需要$ \ mu_ {h ^ *} $为非零即可。平稳性条件简化为\ [\ delta(a)= \ begin {cases} \ mu_ {h ^ *} / 2& \mbox{if } e \in h^* \mbox{ and } e \not \in h^{**} ; \\ -\mu_{h^*} / 2 & \mbox{if } e \not \in h^* \mbox{ and } e \in h^{**} ;\\ 0&\ mbox {否则。} \ end {cases} \]直观地讲,由于错误是凸状惩罚的,所以对手最好的方法是将等错误和相反错误集中在$ h ^ {** $或$ h ^ * $。令$ \ kappa(h ^ *,h ^ {**})= | h ^ * | + | h ^ {**} | -2 | h ^ * \ cap h ^ {**} | $。代入不等式约束产生\ [\ begin {aligned} \ sum_ {a \ in h ^ {**}} f ^ *(a)-\ sum_ {a \ in h ^ *} f ^ *(a)& \ leq \ sum_ {a \ in h ^ *} \ delta(a)-\ sumq {a \ in h ^ {**}} \ delta(a)\\&= \ kappa(h ^ *,h ^ { **})\ sqrt {\ frac {| A |} {\ kappa(h ^ *,h ^ {**})}} \ frac {1} {| A |} \ sum_ {a \ in A} \ delta (a)^ 2} \\&\ leq \ sqrt {2 \ min \ {m,| A | -m \}} \ sqrt {| A |} \ sqrt {\ frac {1} {| A |} \ sum_ {a \ in A} \ delta(a)^ 2},\ end {aligned} \]其中最后一步利用$ \ kappa(h ^ *,h ^ {**})\ leq 2 \ min \ {m,| A | -m \} $。对$ D_x $取期望会得出结果\ [\ begin {aligned} r_ {ad}(h_g)&\ leq \ sqrt {2 \ min \ {m,| A | -m \}} \ sqrt {| A |} \ E_ {x \ sim D_x} \ left [\ sqrt {\ frac {1} {| A |} \ sum_ {a \ in A} \ delta(a)^ 2} \ right] \\&\ leq \ sqrt {2 \ min \ {m,| A | -m \}} \ sqrt {| A |} \ sqrt {\ epsilon_ {L ^ 2}(g)},\ end {aligned} \],最后一步是由于詹森的不等式。

没意见:

发表评论