排行榜哪个网站最好,抖音代刷网站推广快速,九江建企业网站,综合性门户网站列举论文#xff1a;A large Budget-Constrained Causal Forest Algorithm
论文#xff1a;http://export.arxiv.org/pdf/2201.12585v2.pdf
目录
0 摘要
1 介绍 2 问题的制定
3策略评价
4 方法
4.1现有方法的局限性。
4.2提出的LBCF算法
5验证
5.1合成数据
5.2离线生…论文A large Budget-Constrained Causal Forest Algorithm
论文http://export.arxiv.org/pdf/2201.12585v2.pdf
目录
0 摘要
1 介绍 2 问题的制定
3策略评价
4 方法
4.1现有方法的局限性。
4.2提出的LBCF算法
5验证
5.1合成数据
5.2离线生成TestRCT数据。
5.3在线AB测试设置
6预算受限的治疗选择
7结论
8阅读理解
Readme 0 摘要
向用户提供奖励(例如亚马逊的优惠券优步的折扣和抖音的视频奖金)是在线平台用来提高用户粘性和平台收入的常用策略。尽管这些营销激励已被证明是有效的但如果使用不当会产生不可避免的成本并可能导致低ROI(投资回报)。另一方面不同的用户对这些激励措施的反应不同例如有些用户从未在没有优惠券的情况下购买某些产品而另一些用户则无论如何都会购买。因此如何在预算限制下为每个用户选择合适的激励(即待遇)是一个具有重大现实意义的重要研究问题。在本文中我们称这种问题为预算约束的治疗选择问题。挑战是如何有效地解决大规模数据集上的BTS问题并获得比现有技术更好的结果。本文提出了一种预算约束下基于树的治疗选择算法称为大规模预算约束因果森林(large BudgetConstrained Causal Forest, LBCF)算法该算法也是一种适用于现代分布式计算系统的有效治疗选择算法。本文还提出了一种新的离线评估方法以克服在随机对照试验(RCT)数据中评估BTS问题解决方案性能的内在挑战。我们将我们的方法部署在一个大型视频平台的现实场景中该平台为了增加用户的活动参与时间而赠送奖金。仿真分析、离线和在线实验都表明我们的方法优于各种基于树的最先进的基线1。该提议的方法目前正在为平台上的数亿用户提供服务并在这几个月里实现了最大的改进之一。
KEYWORDSPersonalization, Heterogeneous causal effects, Constraint optimization, Treatment Selection, Distributed Computing
关键词个性化异质因果效应约束优化处理选择分布式计算
1 介绍
通过赠送奖励来开展营销活动是提高用户粘性和平台收入的一种流行而有效的方式例如共享出行中的折扣[13](优步[31]滴滴)和电子商务中的优惠券[29](阿里巴巴[29]Booking.com[6,14])。
在工业环境中这些营销活动受到有限的预算限制因此有效地分配有限的激励至关重要。其中最具挑战性的任务是识别具有异质性的目标用户即不同用户对不同级别的优惠券(如9折8折等)的反应不同。换句话说一些用户在没有优惠券的情况下从不购买某些产品而另一些用户则会购买。因此研究如何将有限的激励预算分配给具有异质性的用户以最大化整体回报(如用户粘性、平台收益等)是一个重要的研究问题。最近的研究开始使用因果分析框架来解决这一问题将激励和回报分别视为“治疗”和“结果”。在本文中我们将这类问题视为预算约束的治疗选择问题(BTS)。 方法现有的许多技术都可以解决BTS问题。挑战是如何有效地解决大规模数据集上的BTS问题并获得比现有技术更好的结果。本文主要研究基于树的技术因为它在工业上具有良好的性能。这些技术可以分为两类。
第一类是带贪婪处理选择的隆起随机森林。在得到所有处理的异质处理效果(本文中处理效果和隆升是可交换的)估计后这些解如隆升随机森林在上下文治疗选择(Contextual Treatment Selection, CTS)[30]上只需为每个用户选择治疗效果最大的治疗[7,17]。我们称这种治疗选择策略为贪婪治疗选择策略。在4.1.1节中通过一个简单的例子我们证明了这种贪婪的处理选择策略对于BTS问题是次优的。
第二类是Tu等人最近提出的最优治疗选择算法[26]。该算法有两个局限性特别是对于大规模的BTS问题。首先在大规模数据集上由于缺乏大规模线性规划优化求解器作者建议采用队列级优化代替成员级优化。其次为了利用二元因果森林(见Athey et al. [2]) (BCF)实现多处理效果估计Tu et al.[26]提出分别训练多个二元因果森林(MBCF)每个BCF对应一个处理。尽管如此在这种分治方法中用户可能属于每个二进制模型中的不同叶节点(见图2a)。因此在估计不同处理的处理效果或提升时我们正在观察不同的特征空间(见图1a)。因此所获得的治疗效果在不同治疗之间没有严格的可比性。此外如果我们有多个模型同时服务它是计算消耗和难以维护。
在本文中我们提出了一种大规模预算约束因果森林(LBCF)算法来克服上述限制。LBCF由两部分组成:成员级治疗效果估计和预算约束优化。对于第一个组件我们设计了一个新的分割标准允许来自多个治疗组的类似用户驻留在同一个节点上。提出的分割准则允许我们用统一的模型处理多个处理(图2b)这样就可以在相同的特征空间内估计不同激励水平下的处理效果(图1b)。 为此除了节点间的异质性我们提出的方法还鼓励节点内处理效果的异质性以促进下游预算受限的优化任务。对于另一个组成部分在获得用户对不同激励水平的处理效果后我们可以将预算约束优化任务制定为多选择背包问题(MCKP)[10,15,22]。尽管MCKP已经被研究了几十年(例如经典的线性时间近似算法Dyer-Zemel算法[4])但现有的优化方法并不是为现代基础设施设计的特别是分布式计算框架如Tensorflow[1]和Spark。因此这些方法无法扩展到今天的大规模在线平台。在这项工作中我们利用MCKP的拉格朗日对偶的凸性设计了一种高效的可并行平分搜索算法称为对偶梯度平分(DGB)。与其他最先进的近似优化方法相比DGB可以更容易地部署在分布式计算系统中。(?)时间复杂度和不需要额外的超参数调优作为其基于梯度下降的替代方案。
政策评估。对防弹少年团的离线评价也是一个难题。现有的BTS问题评价方法存在诸多局限性。其中一种方法如AUUC[8,21,23]、Qini-curve[16]和AUCC[3]在多治疗情况下根据评分对所有用户进行排序评分是所有可能的治疗分配中预测治疗效果最大的。然而待评估策略并不一定选择最大的治疗。另一种方法是Zhao等人提出的预期结果度量。在这个指标中被评估的用户并不是全部的RCT用户这导致消费预算随着不同的治疗选择策略而变化。为了克服这些现有评估方法的局限性我们提出了一种新的评估指标称为百分比平均增益(PMG)用于BTS问题。我们的指标能够对治疗选择政策进行更全面的评估。
数据集和测试。为了充分验证我们的LBCF算法的性能我们进行了三种测试:模拟测试、在实词数据集上的离线测试和在线AB测试。在模拟测试中我们使用与Tu et al.[26]相同的方法生成合成的RCT数据集。为了得出令人信服的结果我们还使用Tu et al.[26]中定义的相同测量指标:个性化治疗效果的归一化平均值(ITE)。我们将提出的LBCF算法与五种基于树的基线方法进行比较:基于欧几里得距离(ED)的抬升随机森林[7,17]卡方(Chi)和上下文处理选择(CTS)这些方法都来自CausalML包;随机优化因果树(CT.ST)和确定性优化因果森林(CF.DT)是Tu et al.[26].推荐的两种方法。仿真结果表明LBCF算法在不同噪声水平下具有良好的性能。
在离线测试中我们首先从视频流媒体平台收集了一个网络规模的RCT数据集。数据集记录了用户在七个随机登记的激励组中的活动参与时间(即“结果”)每个组提供不同级别的奖金(即“多重待遇”)。有了我们发布的完整数据集和提议的评估协议PMG我们社区的更多研究人员可以潜在地参与相关研究。我们进一步在平台上部署了建议的方法。在线A/B实验表明在活动参与持续时间方面在相同的预算下我们的算法可以显著优于基线方法至少0.9%这是这几个月的巨大进步。在线实验也证明了LBCF算法的可扩展性。目前LBCF算法为数亿用户提供服务。
综上所述本文的贡献可以概括为以下几点:
我们提出了一种预算约束下基于树的处理选择技术称为大规模预算约束因果森林(LBCF)算法。所提出的方法已经部署在一个服务于数亿用户的真实大型平台上。我们提出了一种新的用于预算约束治疗选择(BTS)问题的离线评估方法称为百分比平均增益(PMG)该方法解决了使用随机对照试验(RCT)收集的离线数据集评估BTS问题解决方案的内在局限性。我们进行了一系列广泛的实验包括在公共合成数据集上的模拟测试在收集的真实数据集上的离线测试以及在大型视频平台上的在线AB测试。结果证明了该方法的有效性并证明了其在大规模工业应用场景下的可扩展性。2 问题的制定
在这项工作中我们专注于最大化总体回报同时决定如何提供激励以遵守全球预算约束。我们采用潜在结果框架[20,24]来表达激励对回报的治疗效果其中激励和回报分别被视为“治疗”和“结果”。我们用大写字母表示随机变量用小写字母表示它们的实现。我们用粗体表示向量用普通字体表示标量。
假设我们有一个大小的数据集?包含(X? ?)收集自随机对照试验。我们使用上标?为了索引样本(xi ?吗?,吗??),吗? 1…,吗? 吗?∈{0,1…,吗?}。我们假设潜在结果的存在?吗?(?吗? ?)然后呢?吗?(?吗? 0)与我们在治疗分配中观察到的结果相对应?吗? ?还是?吗? 0并尝试估计条件平均处理效果(CATE)函数假设它们具有相同的特征值xi:
吗?吗? 另外我们考虑随机变量?代表与治疗相关的费用。我们假设没有成本如果? 0成本呢?吗?吗?如何应用每种治疗方法?给每个用户?是事先知道的。让吗?表示总预算。然后给出(X, ?,吗? ?)手动设定预算呢?我们的目标是最大化 3策略评价
BTSbudget-constrained treatment selection问题的第一个挑战是如何评估解决方案这是一个困难的任务因为缺少反事实的结果例如如果我们选择治疗我们无法观察到客户潜在的结果变化(即治疗效果)?(例如九折优惠券)而不是治疗?(例如没有优惠券)。在本节中我们提出了一种新的BTS问题的评价方法。
现有方法的局限性。最近研究了两种评价方法。
第一种方法是利用从随机对照试验(RCT)中收集的用户数据使用隆起曲线下的度量面积(AUUC)[21]来评估治疗效果[11,12,25,28]。在多重治疗的情况下这种方法要求将所有用户按评分降序排列评分是所有可能的治疗分配中预测的最大治疗效果。但是待评价策略并不一定选择最大处理因为最大处理不一定是最优处理。
第二个是[30]提出的预期结果度量。它通过汇总RCT和政策处理匹配的用户的加权结果来估计预期结果(图3)。对于我们的BTS问题这个指标的主要局限性是被评估的用户不是整个RCT用户。因此预期结果并不是整个RCT使用者的平均结果这就导致了不同治疗选择政策的消费预算的变化。两个具有不同消费预算的政策是不具有可比性的。
考虑到上述两种方法的局限性我们针对BTS问题提出了一种新的策略评估指标称为百分比平均增益(PMG)。 4 方法
我们比较了几种常见的基于树的方法来解决BTS问题并介绍了一种称为大规模预算约束因果森林(LBCF)算法的新方法。
4.1现有方法的局限性。
4.1.1隆升随机森林。
在处理方法的选择上大多数隆升随机林方法只是简单地选择处理效果最大的处理。我们称这种治疗选择策略为贪婪治疗选择策略。在下面通过一个简单的例子我们表明在给定的预算下这种贪婪的治疗选择策略是次优的。 理解贪心不考虑后续不是全局最优。
4.1.2最优处理选择算法。
Tu等人最近提出的最优处理选择算法[26]可以用来解决BTS问题不需要做太多修改。然而该算法有两个局限性特别是对于大规模的BTS问题。首先在大规模数据集上由于缺乏大规模线性规划优化求解器作者提出用群体级优化代替成员级优化。然而正如Tu等人[26]测试的那样在低噪声级别的数据集上成员级优化可以生成更个性化的估计。
因此我们希望开发一种并行算法来解决大规模数据集上BST问题的成员级优化。其次为了实现多处理效果估计Tu等。[26]简单地分别训练多个二元因果森林[27](MBCF)即一个因果森林生成一个治疗组与对照组的治疗效果估计。然而MBCF有两个局限性 •训练和维护许多二元因果森林(BCF)在计算上很麻烦。
•对于一个用户来说一个BCF产生的治疗效果估计可能与其他BCF产生的治疗效果估计属于不同的特征空间这与CATE的定义相矛盾(Eq. 1)。例如(图2a)特征{年龄 30收入 55?}将分别属于BCF1的Leaf11和BCF3的Leaf31但Leaf11和Leaf31对应不同的特征值。
4.2提出的LBCF算法
我们将BTS问题分解为两个步骤:(i)估计CATE ?吗?吗?在成员级别上只使用一个模型。(ii)通过求解约束优化问题得到最佳处理方案z *。 4.2.1统一判别因果林。
为了克服MBCF(第4.1.2节)的局限性并在多个处理之间区分处理效果估计通过修改BCF我们设计了一个新的多处理因果林模型该模型具有以下两个特性:
•统一-该模型只构建一个因果林所有处理被分割在一起并遵循相同的分割规则。
•可区分性——该模型可以区分节点间异构性和节点内异构性。 为了总结上面的两个分割规则并平衡效率和有效性特别是在大规模数据集上我们提出了一个新的因果森林称为统一判别因果森林(UDCF图2b)具有两步分割标准:
(i)让?相对于所有可能分裂的总数来说是一个很小的数字。挑顶?根据公式3计算的结果通过Inter分割规则将候选人从所有可能的分割中分割出来。(ii)从?根据式4计算的结果用Intra splitrule拆分候选。 Termination Rule and Treatment Effect Estimation. Termination rule for tree split is just the same as BCF. After UDCF is constructed, treatment effect estimation (xi) can be obtained by fitting T and Y in a weighted least square regression, where theweight is the similarity between xi and all other samples. We omit the details of this part (see [2]). 4.2.2预算约束优化。
基于?在第4.2.1节中我们可以在给定预算的情况下制定我们的优化问题? 我们希望通过求解以下问题得到最优的z *。 4.2.3大规模系统与并行化。
对于BTS问题来说“大规模”一词有两层含义:数十万用户和大量各种各样的处理这都给这些技术应用于大规模系统带来了障碍。在处理效果估计方面所提出的UDCF本质上是一个可以在现代分布式系统上并行运行的随机森林。而UDCF本质上是一个单一模型哪个可以训练呢?治疗组的数据放在一起不管有多大?是多少。对于预算受限的优化计算梯度?‘(?*)(见算法2中的第12行)可以分解为|U| ?独立的子问题也可以由分布式系统并行解决。总而言之即使在大规模系统中LBCF算法仍能表现良好高效运行。 4.2.4总体算法。
在UDCF和DGB的基础上我们在算法3中总结了我们的方法。
算法3 LBCF算法
1:从在线测试或合成数据集中获取RCT样本。
2:通过UDCF对不同治疗的结果进行成员级别的治疗效果估计(章节4.2.1)。
3:利用所提出的DGB(章节4.2.2)解决成员级预算约束优化问题。
5验证
为了完全符合我们的LBCF算法的性能我们进行了三种测试:在公共合成数据集上的模拟分析在真实字数据集上的离线测试和在线AB测试。
5.1合成数据
我们使用与Tu et al.[26]相同的方法来生成合成数据集。在这个模拟中我们假设有8万个样本每个样本有三个处理。我们在最大限度地提高治疗效果的同时将成本控制在预算之内? 此外我们还像Tu等人一样通过引入不确定性权重超参数来衡量不同方法在数据中不同噪声水平下的性能。[26]。测量指标。为了得到一个令人信服的结果我们也使用了Tu等人的测量方法。 5.2离线生成TestRCT数据。
在一个视频应用程序上我们将0.1%的在线流量分配给RCT, RCT运行两周以收集足够的样本数据这些数据被用作5.1节中比较的所有方法的训练实例。在RCT中活动运营商对不同实验组的应用用户提供不同的积分而对对照组的应用用户不提供积分。一般来说奖励点数越多活动参与时间越长。最后RCT数据集包含超过10万个应用访问实例。每个实例都被赋予了相关特征(如应用访问行为、区域、历史统计数据等)、结果(活动参与时长)和治疗(加分)(如果适用的话)(详见补充材料)。
结果。通过利用Eq. 2中描述的评估指标PMG我们进行了与第5.1节相同的比较但在不同的条件下总预算限制。如图5所示本文提出的LBCF方法在任何预算配置下都能获得最大的用户活动参与持续时间PMG这与仿真分析的结果一致(见章节5.1)。 图5:在不同预算下将提出的算法与其他基线方法进行比较的离线测试结果其中x轴代表预算y轴代表真实RCT数据集上活动参与持续时间的百分比平均增益(PMG)。 5.3在线AB测试设置
在线AB实验在5.2节提到的大型视频应用上进行了15天以上。该实验的目标是评估实验组和对照组(即无激励组)之间活动参与持续时间的增加百分比。实验组都在相同的预算约束下?对照组没有奖金。基于上述模拟测试和离线测试的结果在本次在线实验中我们仅将LBCF与以下两种方法进行比较:CT。ST和CF.DT因为实现管道和启动在线A/B测试的成本很高。CF.DT的线性规划求解器不能处理大规模数据集因此我们使用我们提出的DGB代替。因此在本试验中CF.DT也等价于MBCF。DGB (CF实际上是MBCF模型)。•实验组:CT。Tu et al.[26]的ST -基线法•实验组:Tu et al. CF.DT (MBCF.DGB)。•实验组:LBCF (UDCF.DGB) -建议方法结果如图6所示。在最初几天后建议的LBCF (UDCF.DGB)始终提供较高的百分比收益(最后一天为7.79%)。一个基线CF.DT (MBCF. dgb)是各组中最差的(最后一天为5.31%)因为MBCF比UDCF差如我们在第4节中所述。另一个基线CT。ST处于中间(最后一天为6.87%)这与我们5.2节的离线测试结果基本一致。
6预算受限的治疗选择
对于BTS问题我们主要关注基于树的技术。现有的方法有欧氏距离(ED)、卡方(Chi)和环境处理选择[30](CTS)等;随机优化的因果树(CT.ST)和确定性优化的因果森林(CF.DT)两者都是前两个Tu等人推荐的方法。[26]。这些方法的局限性是在估计隆起时不能保证相同的特征空间经常需要训练多个模型或者在预算限制下简单地采用次优贪婪处理选择策略。此外预算约束优化MCKP[22]是一个著名的np难问题。在过去的几十年里精确算法和启发式算法都被研究过包括分支和定界[5]禁忌搜索[9]贪婪算法[22]等。不幸的是这些传统算法并不是为现代分布式计算而设计的。因此他们无法在一个非常大规模的数据集(例如数十亿个决策变量)上求解MCKP。
评价指标。对于BTS问题目前流行的评价方法有两种。一些方法如AUUC[8,21,23]、Qini-curve[16]、AUCC[3]等要求相似评分组表现出相似的特征这并不一定能满足要求。另一种方法是[30]提出的预期结果度量。该指标的主要局限性是被评估的用户不是整个RCT用户这导致不同治疗选择策略的消费预算发生变化。不同消费预算下的两种政策不具有可比性。
7结论
假设强调两点:第一点是每个单元的独立性。在我们的案例中我们确实承认SUTVA假设并不严格地适用于第一点。例如两个应用程序用户可能经常相互分享激励信息(即待遇)。最近已经开展了一些工作来处理数据中的这种依赖性。第二点是每种治疗只存在一个级别。在我们的工作中我们考虑离散的处理我们保证每个处理都有相同数量的激励。因此SUTVA假设可以hold住第二点。此外我们还希望在约束优化任务中加入更多约束(如用户体验)并提出即使在大型系统中也能有效解决这类任务的解决方案。
8阅读理解
UDCF分裂没考虑cost没单调性约束。Readme
代码
LBCF:一种大规模预算约束因果森林算法 本回购包含了论文“LBCF: A large Budget-Constrained Causal Forest Algorithm”补充资料中提到的所有数据、代码文件和图片。 第五节仿真分析 重现结果的步骤:
1. 在generateSimulationData中将你的工作目录添加到“homePath”中。R在Code/Data_generation文件夹下。 2. generateSimulationData.R运行。 3.按照每个模型文件夹下的说明进行训练和预测;为每个模型运行budget_allocation.py。 4. 在代码/评估文件夹下运行Simulation_analysis.py。 5.2离线测试 注意:由于这个真实世界的离线测试数据集的版权受到保护目前我们无法在发布之前公开此测试中使用的完整数据但读者可以使用提供的代码在其他数据集上运行此算法。但是数据文件夹中提供了一小部分(约2000个样本)的完整数据仅用于测试代码而不是重现5.2节中的结果并且所有2000个样本都已加密。
运行代码的步骤:
1. 按照每个模型文件夹下的说明进行训练和预测。 2. 为每个模型运行budget_allocation-RCT.py。 3.在代码/评估文件夹下运行Offline_test.py。 实现细节 提出的CATE估计方法UDCF(统一判别因果森林)是通过直接修改GRF(广义随机森林)的c源代码采用新的分裂准则来实现的。因此UDCF需要一个像GRF一样的c运行环境。环境配置的详细信息请参考GRF Github页面。 提出的MCKP分布式算法DGB (Dual Gradient Bisection)是用Python编写的并在Pytorch上运行。 基线方法:ED (Euclidean Distance)、Chi (Chi- square)和CTS (Contextual Treatment Selection)上的随机森林都是从CausalML包Github Pages直接导入的。 基线方法:CT。Tu et al.[1]提出的ST (Causal Tree with Stochastic Optimization随机优化因果树)和CF.DT (Causal Forest with Deterministic Optimization确定性优化因果林)采用论文[1]中列出的算法实现。需要R包。 参考 [1]。Ye Tu, Kinjal Basu, Cyrus DiCiccio, roil Bansal, Preetam Nandy, Padmini Jaikumar和Shaunak Chatterjee, 2021。使用因果异质性的个性化治疗选择。在2021年网络会议论文集中。1574 - 1585。
