• 第一步通过 Inter Split 选择 top N 个备选特征分裂点；
• 第二步通过 Intra Split 从 N 个备选中选择一个最终的特征分裂点 。

资源分配并行算法
解决了用户弹性的预估问题之后 ， 在智能营销领域输出营销决策时 ， 我们经常需要去回答 ， 在有限的资源约束下如何去实现最优分配 。 为此 ， 该研究把智能营销中的资源分配问题建模成了有约束的整数规划数学模型 ， 如图 3 。 但是 ， 快手亿级别的用户量导致决策变量数目巨大 ， 很多目前开源的求解器不能满足性能的需求 ， 会存在内存溢出等问题 。

文章图片

图 3 整数规划数学模型
为此 ， 该研究设计了可并行的 Dual Gradient Bisection(DGB)算法 ， 如图 4 。 该算法在不损失解质量的情况下 ， 实现了亿级用户量的分钟级求解 。 限于篇幅 ， 这里简单描述下求解思路 ， 详细的可以参阅论文和附录 code 。

• 第一步 ， 利用线性松弛技术 ， 把图 3 的整数规划数学模型简化成易于求解的线性规划问题 ， 可以证明松弛后的线性规划问题的解集至多只在预算临界处有一个非整数解 。
• 第二步 ， 通过拉格朗日乘子把有约束问题转化为无约束问题 。
• 第三步 ，由于该问题满足强对偶条件 ， 研究者对该问题进行对偶转化 ， 由此得到了一个关于拉格朗日乘子的单变量分段函数 ， 并且可以证明该分段函数为闭区间上的凸函数 。
• 第四步 ， 通过图 4 的 DGB 算法 ， 研究者可以在并行系统上高效求出 。
• 第五步 ， 代回对偶问题 ， 便可依次求解出所有决策变量的值 。

文章图片

图 4 可并行的 DGB 算法
多元因果模型评估
因为无法观测到因果模型的反事实结果(Counterfactual Outcome) ， 因此 ， 如何评估因果模型的线下效果成了业界亟待解决的问题 ， 常用的评估方法有 AUUC/Qini Curve 等 ， 但这些更适合评估二元因果模型；对于多元因果模型的预估结果 ， 也只能是先把多元结果拆解成许多二元结果 ， 之后再进行分别评估 。
本文利用随机控制实验 (RCT) 数据 ， 基于 Treatment Matching 的思想 ， 提供了整体收益对比的方法 。 核心方法是：在 RCT 数据中找出 Policy Treatment 和 RCT Treatment 匹配的那些样本 ， 需要指出的是 ， 对于这些匹配样本 ， 我们是可以观测到其真实结果的 。 其次 ， 可以证明这些匹配样本的均值是其各列期望的好的估计 。 最后 ， 利用各列的期望值 ， 我们可以计算出多元因果模型的整体收益 ， 收益越高 ， 模型越好 。
效果展示
为了公平的对比算法效果 ， 首先 ， 该研究利用 Ye Tu 等人在 WWW 2021 公开的仿真数据集【2】 ， 与业界主流的以树为基础的因果模型进行了线下对比 ， 如图 5 ， 横轴是数据集噪声的强弱 ， 纵轴是研究者关注的核心指标的收益 ， 可以看出 ， LBCF 效果最好 ， CT.ST 和 CF.DT 次之 。

文章图片

图 5 线下仿真实验
进一步 ， 该研究在快手的真实智能营销场景下部署了 LBCF 算法 ， 进行了两周的 A/B 实验 ， 如图 6 ， 结果也证明了该算法的有效性 ， 与 CT.ST 和 CF.DT 算法相比 ， 收益分别提高了 0.92 和 2.48 个百分点 。