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, and then pairs $\{1, 3\}$. Suppose the classifier used 在 each tree node is $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年11月13日,星期六

关于零的不重要

在大多数广告网络上,广告的大多数展示都不会导致任何用户交互(例如,未点击)。同样,在在线婚介中,大多数介绍都不会引起人们的兴趣。因此,任何尽职尽责地记录每个行动和每个结果的系统都将包含历史数据,这些历史数据主要由零值奖励组成。在广告投放中,零与非零的比率很容易达到100:1或更高,因此,舍弃零就是舒适地放在笔记本电脑上的数据集与需要映射缩减的数据集之间的差。或者$ 100 EC2票据和$ 10,000 EC2票据之间的差额。

直观地,如果零示例是常见的,而非零示例很少,那么非零示例每个样本包含的信息要比零示例多得多。这表明对零奖励示例进行二次采样,例如合成大约1:1比例的数据集,在泛化方面可能并不那么昂贵。这里简要讨论一些可以完成的情况。

政策价值估算

假设我正在尝试根据根据已知策略生成的历史数据来估计与新颖的确定性策略相关的预期收益。当绘制示例IID时,可以使用离线策略估计器来评估静态策略。假设分布$ D = D_x \ times D_ {r | x} $,其中$ x $是与实例关联的特征向量,而$ r:A \ to [0,1] $是与每个动作关联的奖励。我有一个建议的策略$ \ pi:X \ to A $,我想估计$ D $,$ E _ {(x,r)\ sim D} \ left [r \ left(\ pi( x)\ right)\ right] $。进一步假设历史策略在给定实例$ p(a | x)$的情况下对操作使用已知的条件分布。历史策略定义了由定义的历史数据的分布$ S $
  1. 从$ D $中提取$(x,r)$。
  2. 从$ p(a | x)$中提取$ a $。
  3. 输出实例$ \ left(x,a,r(a),p(a | x)\ right)$。
很容易证明\ [
\ begin {aligned}
E _ {(x,a,r(a),p)\ sim S} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x )| x)} \ right]&= E _ {((x,r)\ sim D} \ left [r \ left(\ pi(x)\ right)\ right],
\ end {aligned}
\]在给定历史数据集$ H $的情况下使用经验策略估计量进行证明,\ [\ frac {1} {| H |} \ sum _ {(x,a,r(a),p)\ in H} r (\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x)| x)}。
\]这是经验政策估算器的有趣之处:任何观察到的历史奖励为零的实例都可以在不更改总和的情况下丢弃。为了正确地获得标准化常数,需要知道零示例的数量,但是关于零示例的任何其他详细信息对于计算策略估计器都是完全不必要的。这意味着数据集只需要一个常数因数,该常数要大于存储所有非零示例所需的空间。

有时,我遇到的系统具有已知的日志记录策略,该系统很早就对零个示例进行了子采样,而总的零奖励示例计数并未保留。定义了一个新的分布$ \ tilde S $通过
  1. 从$ D $中提取$(x,r)$。
  2. 从$ p(a | x)$中提取$ a $。
  3. 观察$ r(a)$。
  4. 如果$ r(a)= 0 $,则以概率$(1-1)$拒绝。
  5. 输出实例$ \ left(x,a,r(a),p(a | x),l \ right)$。
在这种情况下,$ S $和$ \ tilde S $由\ [
E _ {(x,a,r(a),p,l)\ sim S} \ left [f \ right] = \ frac {E _ {(x,a,r(a),p)\ sim \ tilde S } \ left [\ left(l ^ {-1} 1_ {r(\ pi(x))= 0} + 1_ {r(\ pi(x))\ neq 0} \ right)f \ right]} { E _ {(x,a,r(a),p)\ sim \ tilde S} \ left [\ left(l ^ {-1} 1_ {r(\ pi(x))= 0} + 1_ {r( \ pi(x))\ neq 0} \ right)\ right]},
\]建议使用给定的历史数据集$ \ tilde H $,\ [\ frac {1} {\ eta(\ tilde H)} \ sum _ {(x,a,r(a), p,l)\ in \ tilde H} r(\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x)| x)},\]其中$ \ eta(\ tilde H)$是有效的历史数据集大小,\ [
\ eta(\ tilde H)= \ sum _ {(x,a,r(a),p,l)\ in \ tilde H} \ left(l ^ {-1} 1_ {r(a)= 0} + 1_ {r(a)\ neq 0} \ right),
\],例如,零奖励示例会将有效集合大小增加$ 1 / l $。注意分子不受影响,因为零奖励示例不起作用。

当然,比率的期望值不是期望值的比率,因此后者的估计值可能有偏差,但希望并非如此(我应该对此有更好的理解)。

AUC

假设我正在尝试估计排名模型的AUC。我假设奖励是二进制值,具有条件要素实例分布$ D_ {x | 0} $和$ D_ {x | 1} $。为简单起见,我假设我的模型通过评分函数$ \ phi:X \ to \ mathbb {R} $引发线性排序。在这种情况下,AUC由\ [
\mbox{AUC} (\phi) = E_{(x_+, x_-) \sim D_{x|1} \times D_{x|0}} \left[ 1_{\phi (x_+) > \phi (x_-)} + \frac{1}{2} 1_{\phi (x_+) = \phi (x_-)} \right].
\]这是AUC的``正确成对比较的概率''形式,等同于``曲线下面积''公式。现在,我可以将$ D_ {x | 0} $替换为新的分布$ \ tilde D_ {x | 0} $,定义为
  1. 从$ D_ {x | 0} $中提取$ x $。
  2. 以恒定概率$ p $拒绝$ x $。
  3. 否则,发出$ x $。
希望明确的是,对于$ D_ {x | 0} $和$ \ tilde D_ {x | 0} $的期望是相同的。因此\ [
\mbox{AUC} (\phi) = E_{(x_+, x_-) \sim D_{x|1} \times \tilde D_{x|0}} \left[ 1_{\phi (x_+) > \phi (x_-)} + \frac{1}{2} 1_{\phi (x_+) = \phi (x_-)} \right],
\],即使用历史数据集(其中负面示例已被明显地二次抽样)不会带来偏差。

当然,我可以对肯定因素重复此论点,得出荒谬的结论,即仅用一个肯定的例子和一个否定的例子就可以构造一个很好的AUC估计量。好吧,这样的AUC估算器将是 无偏见的 (根据历史记录中可能的单例对的集合进行平均),但事实并非如此 。要理解这一点,如Agarwal等人所探讨的那样,有助于研究将经验AUC与实际AUC相关联的偏差范围。在 这篇报告。定理3是金钱,其中\
P_ {T \ sim D ^ N} \ left \ {\ left | \ mbox {AUC} _e(\ phi,T)-\ mbox {AUC}(\ phi)\ right | \ geq \ sqrt {\ frac {\ ln(\ frac {2} {\ delta})} {2 \ rho(T)(1-\ rho(T))N}} \ right \} \ leq \ delta,
\]其中$ \ mbox {AUC} _e $是训练数据集$ T $上的经验AUC,而$ \ rho(T)$衡量训练集标签中的不平衡量,\ [
\ rho(T)= \ frac {1} {N} \ sum _ {(x,y)\ in T} 1_ {y = 1}。
\]此处有两个条件驱动偏差范围。首先是评估经验AUC估计量时使用的示例数:越多越好。但是,第二个度量了所使用示例的不平衡程度。如果数据集中的正样本比负样本多得多,反之亦然,则偏差范围会降低。这正式化了这样的直觉,即结果很少的例子比一般的结果携带更多的信息。

这是一个有趣的问题:对于固定总数的示例$ N $,使偏差范围最小化的正例与负例之比是多少?答案是$ \ rho(T)= 1/2 $,即正例与负例的1:1比率,这表明如果评估$ \ phi $昂贵,或者您只有一定数量的硬盘空间或通过网络提取数据是一个瓶颈等,为实现奇偶校验而进行二次采样是评估AUC丢失的好策略。

到目前为止,讨论都是在评估方面进行的,但是在培训过程中,一些策略有效地归结为针对经验AUC进行优化(可能与其他术语一起使用以提高泛化性)。培训通常比评估贵,因此在这里固定数据预算的想法非常合理。上方的偏差自然建议对平衡数据集进行训练。这是根据经验探索的 一篇论文 由Weiss和Provost撰写,他们在使用C4.5作为学习算法的多个数据集中发现,``当使用ROC曲线下方的面积评估分类器性能时,显示出均衡的分布表现良好。''还提出了一种更复杂的技术,称为``预算敏感''渐进采样,以进一步提高分类器的性能。

当数据预算不成问题时,也有可能对少数类进行过度采样以形成平衡的数据集,并且可能会提高通用性。这个和其他想法在 一篇论文 由Batista等撰写。等

回归

假设我正在尝试维护回归器$ \ phi:X \ to \ mathbb {R} $,其目的是估计上下文的条件期望回报(为简单起见,假定此处没有任何操作;仅包含一系列上下文,其中包含相关的标量奖励)。在这种情况下,我有一个根据$ D = D_x \ times D_ {r | x} $绘制的IID数据,并且我正在尝试最小化平方损失\ [
E _ {((x,r)\ sim D} \ left [(r-\ phi(x))^ 2 \ right]。
\]我处于在线状态,恐怕我的回归器会被数据量淹没,所以我正在考虑对零奖励示例进行二次抽样。我正在有效地定义一个新的分布$ \ tilde D $
  1. 从$ D $中提取$(x,r)$。
  2. 如果$ r = 0 $,则以概率$(1-1)$拒绝。
  3. 输出实例$ \ left(x,r,l \ right)$。
这两个分布通过\ [
E _ {((x,r)\ sim D} \ left [f \ right] = \ frac {E _ {(x,r)\ sim \ tilde D} \ left [(l ^ {-1} 1_ {r = 0 } + 1_ {r \ neq 0})f \ right]} {E _ {(x,r)\ sim \ tilde D} \ left [(l ^ {-1} 1_ {r = 0} + 1_ {r \ neq 0})\ right]}。
\]如果回归变量实际上是重要性加权回归算法(例如GD),则使用重要性加权$ w(l,r)=(l ^ {-1} 1_ {r = 0} + 1_ {r \ neq 0})$在二次采样数据上导致\ [
E _ {((x,r)\ sim D} \ left [(r-\ phi(x))^ 2 \ right] = \ frac {E _ {(x,r)\ sim \ tilde D} \ left [w( l,r)(r-\ phi(x))^ 2 \ right]} {E _ {(x,r)\ sim \ tilde D} \ left [w(l,r)\ right]},
\],即原始分布中的平方损失与子采样分布中的重要性加权平方损失成正比。在实践中,如果子采样过于激进,则零奖励示例的重要性权重将太大而性能将很差,但这是将数据量降低10倍的明智方法。 (要真正扩大规模,需要采用大规模的并行学习策略,因此,我对 在NIPS 2010上学习集群 今年。)

在离线环境中,我发现校准通常可以改善估计量(也许也在在线环境中?我没有尝试过,但是我要描述的过程也可以在线实现)。表示确保估计器的输出接近奖励的条件期望值。最近,我通过获取校准样本$ \ {(x_i,r_i)\} \ sim D ^ * $来进行此操作,并使用未经校准的估算器对其进行处理,以获得原始估算$ \ {(x_i,\ phi(x_i ),r_i)\} $,并将其汇总到$ J $箱中,以使相等数量的样本落入每个范围$ b_ {j-1} \ leq \ phi(x_i) < b_j$, with $b_0$ and $b_J$ being the smallest and largest possible output of the uncalibrated estimator. I then define control points via \[
\ begin {aligned}
\ hat \ phi_j&= E _ {(x,r)\ sim D} \ left [\ phi(x)| b_ {j-1} \ leq \ phi(x) < b_j \right] \approx \frac{\sum_{\{ x_i, \phi (x_i), r_i \}} \phi (x_i) 1_{b_{j-1} \leq \phi (x_i) < b_j}}{\sum_{\{ x_i, \phi (x_i), r_i \}} 1_{b_{j-1} \leq \phi (x_i) < b_j}}, \\
\ hat r_j&= E _ {(x,r)\ sim D} \ left [r | b_ {j-1} \ leq \ phi(x) < b_j \right] \approx \frac{\sum_{\{ x_i, \phi (x_i), r_i \}} r_i 1_{b_{j-1} \leq \phi (x_i) < b_j}}{\sum_{\{ x_i, \phi (x_i), r_i \}} 1_{b_{j-1} \leq \phi (x_i) < b_j}}.
\ end {aligned}
\]集合$ \ {\ hat \ phi_j,\ hat r_j \} $,并增加了点$ \ {\ min \ phi,\ min r \} $和$ \ {\ max \ phi,\ max r \} $代表未校准估计器的最小和最大可能输出以及奖励的最小和最大可能估计,定义了线性样条线$ \ psi:[\ min \ phi,\ max \ phi] \ to [\ min r, \ max r] $可以用来对未校准估计器的输出进行后处理,以改善校准效果。

现在假设事实证明不是从$ D ^ * $提取校准样本,而是从零回报子采样$ \ tilde D ^ * $提取。与上面的经验值估算器类似,该调整包括在控制点的计算中将$ r_i = 0 $的任何示例等同于$ r_i \ neq 0 $的$ 1 / l $个示例。
\ begin {aligned}
\ hat \ phi_j&\ approx \ frac {\ sum _ {\ {x_i,\ phi(x_i),r_i \}} \ left(l ^ {-1} 1_ {r_i = 0} + 1_ {r_i \ neq 0} \ right)\ phi(x_i)1_ {b_ {j-1} \ leq \ phi(x_i)\ leq b_j}} {\ sum _ {\ {x_i,\ phi(x_i),r_i \}}} left(l ^ {-1} 1_ {r_i = 0} + 1_ {r_i \ neq 0} \ right)1_ {b_ {j-1} \ leq \ phi(x_i)\ leq b_j}},\\
\ hat r_j&\ approx \ frac {\ sum _ {\ {x_i,\ phi(x_i),r_i \}} \ left(l ^ {-1} 1_ {r_i = 0} + 1_ {r_i \ neq 0} \右)r_i 1_ {b_ {j-1} \ leq \ phi(x_i)\ leq b_j}} {\ sum _ {\ {x_i,\ phi(x_i),r_i \}} \ left(l ^ {-1} 1_ {r_i = 0} + 1_ {r_i \ neq 0} \ right)1_ {b_ {j-1} \ leq \ phi(x_i)\ leq b_j}},
\ end {aligned}
\],然后按照上述步骤进行操作。但是,这很酷:如果您要校准估计量,则训练数据是否为零奖励二次采样且未使用重要性加权似乎并不重要。估计量最终有偏差,但是校准可以对其进行校正,并且在实践中,与重要度加权回归相比,该校准过程对较大的零奖励子采样率不敏感。例如,通过重要性加权技巧尝试$ l = 1/100 $是很危险的,但实际上在上面的校准过程中效果很好。

2010年11月5日,星期五

编码技巧

我用 Vowpal兔子 eHarmony广泛使用,主要用于可伸缩性目的。尽管我们不是Google或Yahoo规模的公司,但我们确实做了一些我们想建模的数十亿次匹配(在一个主要的广告网络中,一到两天就有10亿次展示;因此,在数据方面小3个数量级)。 Vowpal通过在原始线性表示上实现梯度下降的简单性来实现高速,但这实际上意味着人们花时间尝试对原始数据进行非线性变换以提高模型性能。

这是一种广泛适用的编码方案,我已将其用于几个不同的问题,以提高性能。它与 分段回归 (针对统计预测人员)以及 类型2的特殊订单集 (适用于运筹学人员)。我们实际上在办公室将其称为``SOS2编码''。

在一个维度上,它的工作方式如下:为变量选择一组点,然后为任何输入值激活对应于包围该值的点的两个要素,权重对应于两个要素之间的线性插值。例如,对于在线约会,两个人之间的实际距离有助于预测很多兴趣。为了对两个人之间的距离进行编码以输入模型,我首先获取距离的$ \ log_2 $(即席直觉变换),然后使用积分点进行SOS2编码。因此,如果两个人的距离差为72英里,则两个要素输出将为
LOG2_DISTANCE_6:0.83 LOG2_DISTANCE_7:0.19
由于这种编码是稀疏的,因此最终可以与其他变量很好地交互(即,涉及SOS2编码特征的二次vowpal术语会产生有用的提升)。在一个二维问题中,我SOS2对每个维度进行了编码,然后二次成功地进行了交互。对于更高维度的问题,我从其他技术(例如, VQ)。