直接抬升建模:以KL散度和欧几里得距离为分裂准则的抬升决策树

2019年的10月28日
乔治·菲在一堵砖墙前摆姿势

乔治·范

介绍

提升模型预测治疗对个体结果的递增效应。换句话说,他们回答了一个因果问题,即如果我们给他/她一个特定的治疗,他/她的行为将如何改变。在Wayfair,我们建立了提升模型,以告知我们的目标客户以及我们在展示再营销中使用的展示广告的出价。要了解更多关于这个特定业务用例的信息,请查看Wayfair Data Science经理Jen Wang的博客。许多不同的研究人员开发了模拟上升的方法;经过大量的探索,我们的团队已经确定,到目前为止,在大多数回测和现场A/B测试中,“提升决策树”是获胜者。在这篇博客文章中,我们将对提升决策树方法进行深入的描述,它可以直接优化提升。

概述不同的隆升建模技术

提升模型包含了因果推断,因为它让我们知道如果我们对一个人进行治疗,他/她的行为会发生多大的改变。这种预测本质上是反事实的。因果推理问题,我们面临的挑战,没有一个明确的响应变量进行训练,因为我们只能观察的结果,一个特定的治疗,或缺乏,对个人来说,如我们不能同时显示,而不是给客户展示广告和测量电梯。

为了解决上述问题,隆升模型严重依赖随机实验来估计条件平均处理效果。即给定一个人的特征,结果变化的期望值。研究人员提出了两种常用的提升建模方法:元学习方法和直接提升估计方法。

元学习方法本质上是将提升问题重新定义为另一种问题或一组问题,并使用现有的机器学习模型来解决这些“翻译”问题。188金宝慱亚洲体育是赌博的嘛两种最广泛使用的元学习方法是双模型方法和结果转化方法。双模型方法建立两个独立的预测模型,一个用于建模P(|治疗的结果),另一个用于建模P(|不治疗的结果)。为了得到个体的提升,我们使用两个模型分别预测两个概率并取其差值。这种方法很容易实现,但它通常无法捕捉到较弱的上升信号,因为建立两个模型会增加预测的噪声(Radcliffe & Surry, 2011)。转化结果法,正如其名称所示,从最初的治疗标签和结果标签中构建一个新的目标变量(Athey和Imbens, 2016)。然后,可以使用任何传统的机器学习模型(如XG188金宝慱亚洲体育是赌博的嘛Boost)来预测转换后的结果。可以证明转换结果的期望值等于真实的隆升,学习的模型应该能够预测隆升。有关此方法的更多细节,可以参考此Wayfair博客Robert Yi和Will Frost在他们的pylift包中实现了这个方法。当上升信号较强时,该方法的回溯测试性能一般与下面讨论的直接上升估计方法相当。

直接提升估计方法对现有的机器学习算法进行了改进,使之直接优化提升。188金宝慱亚洲体育是赌博的嘛它是用于升降随机森林的方法,顾名思义,它是一个升降决策树的集合。我们将在下一节中更详细地讨论提升决策树方法。

深入探究提升决策树背后的理论

提升决策树算法有多种,每一种算法都有不同的分裂判据;在这里,我们将讨论使用Piotr Rzepakowski和Szymon Jaroszewicz在2012年的“直销提升模型”中提出的信息理论分裂标准的人。

在单个处理提升决策树的情况下,每个节点将包含两个单独的结果类分布,一个用于处理组,一个用于对照组。等价于最大的提升,我们想让这两个分布尽可能的远离彼此当我们沿着树走的时候。Kullback-Leibler散度和平方欧氏距离是信息论中用于分布之间散度的两个度量(Eq. 1),下标i表示每个结果类别,p_i和q_i分别是处理组和对照组中该结果类别i的概率。

方程1:两个分布之间的Kullback-Leibler散度(顶部)。两个分布之间的欧式距离的平方(下图)。

对于要分割的树中的一个给定节点,我们可以使用上面两个散度度量之一来计算该节点中结果分布的散度。通过a检验,将一个树节点分割成子节点,我们同样可以测量以a检验为条件的结果类分布的条件发散性(Eq. 2)。式中,“a”表示每个子节点;“N”表示父节点中的实例总数;“N(a)”表示子节点“a”中的实例数;D是散度的度量。“P^T(Y)”和“P^C(Y)”是结果类分布,它们的“|a”变体是子节点a的结果类分布。

方程2:给定测试的条件发散

对于最佳分割,我们想要最大限度地扩大治疗和控制之间的结果类别分布的差异。换句话说,我们想最大化Eq. 3。第一项是上面提到的条件发散,第二项是父节点的结果类分布发散。

方程3:给定检验的类分布的增益散度

太多的方程?别担心。下面我们举一个例子使其更加具体。

一个玩具的例子来帮助解释这个理论

更好地说明提升决策树分裂节点通过最大化收益的治疗和抵抗类分布之间的分歧,我们提出以下示例(见图1)。想象我们一共有8数据点在一个给定的树节点,与治疗组和4 4实例实例在抵抗。治疗组4名顾客中有3名转换,拒绝治疗组4名顾客中有2名转换。我们想找到一种方法来分割这个节点,使Eq. 3的增益最大化。

图1。通过最大化子节点的分布发散来分割决策树节点的示例。绿色圆圈表示已转换的客户,红色圆圈表示未进行转换。标签为T的盒子里的顾客属于治疗组,标签为C的盒子里的顾客属于对照组。

从理论上讲,提升决策树的剖分准则与多路剖分是兼容的。但是在实际实现中,二进制分割(拆分只产生两个子节点)更为常见,如本例所示。我们声明图1所示的分割是我们正在寻找的最优分割。为了证明它,我们来做一下数学运算。为了简化计算,我们选择平方欧几里得距离作为散度测量。

首先,我们计算类分布在父节点上的散度:

这只是处理组和坚持组之间转化率的欧式距离的平方((0.75 - -0.5)2)加上两类之间的非转化率差的平方欧几里得距离((0.25 - -0.5)2)。类似地,我们可以计算两个子节点的类分布发散。对于左结点(1 - 0)2+ (0 - 1)2= 2。对于右边的节点(0 - 1)2+ (1 - 0)2= 2

为了标准化两个子节点对分裂后散度改善的相对影响,我们计算条件散度如公式2所示:

因此,根据公式3,类分布散度的增益为2-0.125=1.875;这是增益可以取的最大值,因为当两个类分布的散度最大时,两个子代的欧氏距离的平方最大(都等于2)。用更具体的语言来说,左边的子节点现在只包含可劝说的内容,因为治疗中的每个人都转换了,而坚持者中的每个人都没有转换。正确的子节点正好相反,在它里面包含不会打扰(或“沉睡的狗”),当他们接受治疗时产生负价值。

在模型训练过程中,通过在不同的可用特征值下对不同的分割进行迭代,计算每个场景的增益,选择增益最大的分割,来找到最优分割。

解决潜在的次优分割

这并不难理解,对吧?嗯,还有更多的故事。我们需要解决上面提出的分割方案可能产生的两个潜在问题:首先,不均匀的处理/控制分割;第二,算法倾向于选择子节点数量较多的split。当算法将大部分的处理实例(如果不是全部的话)放在一个子树中,而该子树中几乎没有控制类时,就会发生不均匀的处理/控制分割。这意味着用于分割的特征与处理标签高度相关,从而违背了对提升建模至关重要的不混淆假设。此外,这样的分割将使进一步分割更加困难,因为每个叶节点必须包含足够的处理和控制实例。第二个问题是选择具有大量子节点的split,这可能是一个问题,因为这种split在应用于训练数据时往往具有更高的增益,但对测试数据的外推效果很差,导致过拟合。

下面所示的归一化因子旨在纠正上述偏差。在这个例子中,与两个分裂准则变量一样,我们有两种类型的归一化值,一种用于KL散度,另一种用于欧氏距离。

方程4:基于KL散度分裂的归一化值

方程5:基于欧氏距离拆分的归一化值

由于两个惩罚项非常相似,这里我们只讨论欧几里得距离的情况。第一个术语防止了不平衡的处理/控制分裂。第一项的第一部分是类在父节点中所占比例的Gini杂质;当存在较大的处理/控制不平衡时,它将接近于零。这是因为如果父节点中已经存在较大的处理/控制不平衡,那么进一步惩罚子节点的不平衡是不公平的。第一项的第二部分是所有子节点中处理比例与坚持比例之间的欧氏距离的平方。只有当这两个比例在所有子节点中相等时,这个值才会最小化。

接下来的两个学期将惩罚具有大量子节点的测试,类似于经典决策树算法处理相同问题的方式。当裂后儿童结节数增加时,基尼杂质增加。例如,当它是一个偶数二分分割,我们有1 - 0。520。52= 0.5,当它是一个偶数四分,然后我们有1 - 4 * 0.252= 0.75。最后的横断项是为了防止倾向于在隆升方面有小增益但通过除以一个小的标准化因子而膨胀的劈裂。

未来的发展方向

虽然提升随机森林实现我们使用(由PauliusŠarka)产生了异常导致生活活动目标,我们相信我们可以做出进一步的贡献和改善方案,我们努力使我们的建模技术不断进步在Wayfair通过快速迭代。下面是我们已经确定的机会领域的列表,它们可以提高当前实现的性能,或者扩展我们模型的用例。

  • 多路分:虽然在构建树时,理论公式适应了多路分割,但我们目前使用的实现只支持二进制分割。由于任何多路分割都可以通过一系列二进制分割来实现,因此从模型性能的角度来看,实现这个特性几乎没有什么好处。但是,如果我们有大量的标称特征,多路分割可以显著降低树的深度,提高模型的可解释性。
  • Multi-treatment隆起模型:尽管我们只讨论了单一治疗在这篇博客,提升决策树算法的作者分别设计了一个升级版本的算法,可以处理multi-treatment隆起,在模型预测多种治疗的最佳治疗对于一个给定的个人(Rzepakowski Jaroszewicz, 2012)。通过将这个修改后的算法整合到代码中,我们将能够回答一些重要的问题,比如:哪个广告创意对我们的客户来说最相关、最有帮助?或者,哪种营销渠道最适合接触到客户?
  • 语境处理选择算法:这是Zhao等人发明的另一种提升决策树算法。它直接优化了一种称为预期反应的评估指标,这是对结果的一种无偏见的衡量。我们遵循该模型产生的治疗策略(赵、方和Simchi-Levi, 2017)。本文认为,该方法的回溯测试结果明显优于隆升随机森林的结果。我们计划将他们新的评估标准和分割标准合并到我们使用的包中。这一举措将使我们能够获得多处理提升模型的回溯测试性能的无偏估计,并有可能提高我们的模型性能。

总结

在这篇博客文章中,我们展示了不同类别的提升模型,并详细讨论了提升决策树方法。我们还讨论了许多改进,我们目前正在确定范围。如果你和我们一样对这个话题感兴趣,请回头看看我们关于隆升模型的最新进展。

参考文献

Athey, S., & Imbens, G. W.(2015)。188金宝慱亚洲体育是赌博的嘛估计异质因果效应的机器学习方法。统计,1050(5)。

新泽西州拉德克利夫,萨里警察局基于显著性的真实隆起模型。白皮书TR-2011-1,英国爱丁堡:随机解决方案,2011。

Piotr & Jaroszewicz, Szymon。(2012)。单处理和多处理的隆升建模决策树。知识和信息系统- KAIS。32.10.1007 / s10115 - 011 - 0434 - 0。

Piotr & Jaroszewicz, Szymon。(2012)。直接营销中的提升模型。《电信与信息技术杂志》2012。43-50。

赵,燕,方,肖,辛奇-李维,大卫。(2017)。多处理和一般响应类型的隆升建模。10.1137/1.9781611974973.66。

提交评论

注意:您的电子邮件地址是必须添加评论,但不会公布。