uplift Tree
和causal tree一样，uplift tree[8]作为一种以分类任务为主的，同样是将因果效应apply到节点分割的标准中。区别是：causal tree：1）使用honest的方法；2) 从effect 的偏差和方差的角度切入指导树的构建，把分类问题转化为回归问题去做。3）逻辑上只支持两个treatment
而uplift tree则更直接一些：直接看节点分裂前后，增量uplfit的gain, 两种treatment下通用形式化框架为：
\(D\) 表示一种评估方式，第一项表示分裂后的metric值，第二项表示分裂前的metric值，A表示某种分裂方式。\(P^T\) 表示T组的概率分布，\(P^C\) 表示C组的概率分布。
同时，只要稍作修改，uplift tree就能支持多treatment的情况：
对于分裂前：
其中，\(\alpha\) 和 \(\gamma\) 是两个超参， 其中\(\gamma，\lambda\) 用来控制treatment的重要性。\(\alpha\) 控制TvsC 和 TvsT的balance。比如我们需要设定treatment单调性的时候
\[ \begin{aligned} & D(P^{T_1}(Y),...,P^{T_k}(Y):P^{C}(Y)|A) \\ &=\sum_{a}\frac{N(a)}{N}D(P^{T_i}(Y|a),...,P^{T_k}(Y|a):P^{C}(Y|a)) \\ \end{aligned} \]i.e. 深补的effect>浅补的effect
通常来说，如果设置 \(\lambda=\frac{1}{k},\gamma_{ij}=\frac{1}{k^2}\) , 相当于等价看不同的T组。
对于分裂后：
几种不同的分裂方式
uplift tree的一个优点是可以很自由的去修改split criteria。我们以两种treatment为例，事实上多两种treatment只是多种的特例。
DDP \(\Delta \Delta P\)
对于一种分裂方式\(A\), DDP定义为：
\[\Delta \Delta P(A)=|(P^{T}(y_0|a_0)-P^{C}(y_0|a_0))-(P^{T}(y_1|a_1)-P^{C}(y_1|a_1))| \]很直观，字面意思就是：左右子节点各计算一次uplift得到第一层\(\Delta\) ,然后两个叶子节点再计算一次\(\Delta\)。达到了最大化两个叶子节点的divergence的目的，节点内部和节点间异质最大化。
IDDP
IDDP[9] 对DDP做了一些改进，motivation是DDP存在一些缺陷：
- DDP得到的gain总是正的=>有正就会导致tree 一直分裂，得到一棵很深的树。树深了就很容易导致over-fitting。
- 依然继承第1个问题，不断分裂的特点是：容易导致叶子节点上的样本很少，进而导致叶子方差很高，又进一步有加剧了过拟合。
- 没有考虑叶子节点node的数量和T|C组的样本占比，这就会导致不置信或者不平。
因此，作者引入了invariant version DDP:
其中，\(H\) 表示熵：\(H(p,q)=(-p*log_2(p)) + (-q*log_2(q))\) , \(\phi\) 表示当前node可用的特征空间，\(\phi_l\) 就是左节点的特征空间，\(\phi_r\) 是右节点的特征空间。\(n_c(\phi)\) 表示当前节点c组的样本，\(n_t(\phi)\) 表示当前节点T组的样本，\(n(\phi)\) 就是节点总样本。
加入整项公式后，类似于一种对于当前分割结果的惩罚项，基本上solve了前面3个问题，特别是节点样本数量、T|C组样本量的问题。
KL divergence KL散度
如果把T组和C组理解成两个分布，那么我们需要分割的时候，能尽量的拉大两个分布间的距离，
同时，因为T|C的样本量可能不一致，这个时候，分布度量函数需要考虑到不对称性，熟悉交叉熵的话，就会想起 KL散度就是一个不错的选择
其中，\(p_k\)是T组在节点\(k\)的概率分布，\(q_k\) 是C组在节点\(k\) 的概率分布。这个分布其实就是各组的正样本占比。当然，两个分布在这里都是float型。对于多个treatment，则分别和C组算一下KL，然后sum起来
具体的计算为：
@cython.cfunc
def kl_divergence(pk: cython.float, qk: cython.float) -> cython.float:
'''
Calculate KL Divergence for binary classification.
sum(np.array(pk) * np.log(np.array(pk) / np.array(qk)))
Args
----
pk : float
The probability of 1 in one distribution.
qk : float
The probability of 1 in the other distribution.
Returns
-------
S : float
The KL divergence.
'''
eps: cython.float = 1e-6
S: cython.float
if qk == 0.:
return 0.
qk = min(max(qk, eps), 1 - eps)
if pk == 0.:
S = -log(1 - qk)
elif pk == 1.:
S = -log(qk)
else:
S = pk * log(pk / qk) + (1 - pk) * log((1 - pk) / (1 - qk))
return S
欧式距离(Euclidean Distance, ED)
距离度量方式当然还有欧式距离：
\[ED(P : Q) = \sum_{k=left, right}(p_k - q_k)^2 \]坦率说，我其实没理解ED会有什么用。
卡方距离Chi
\[\chi^2(P : Q) = \sum_{k=left, right}\frac{(p_k - q_k)^2}{q_k} \]有了KL散度的理解，Chi内部的计算逻辑就不 系嗦 了:)
Interaction Tee (IT)
Causal Inference Tree (CIT)
Contextual Treatment Selection (CTS)
Uplift Forest
和 tree转forest一样，直接apply，简单粗暴，秒变森林。分布式下会复杂一些
self.uplift_forest = [
UpliftTreeClassifier(
max_features=self.max_features, max_depth=self.max_depth,
min_samples_leaf=self.min_samples_leaf,
min_samples_treatment=self.min_samples_treatment,
n_reg=self.n_reg,
evaluationFunction=self.evaluationFunction,
control_name=self.control_name,
normalization=self.normalization,
honesty=self.honesty,
random_state=random_state.randint(MAX_INT))
for _ in range(self.n_estimators)
]
refs
- https://hwcoder.top/Uplift-1
- 工具: scikit-uplift
- Meta-learners for Estimating Heterogeneous Treatment Effects using Machine Learning
- Athey, Susan, and Guido Imbens. "Recursive partitioning for heterogeneous causal effects." Proceedings of the National Academy of Sciences 113.27 (2016): 7353-7360.
- https://zhuanlan.zhihu.com/p/115223013
- Athey, Susan, Julie Tibshirani, and Stefan Wager. "Generalized random forests." (2019): 1148-1178.
- Wager, Stefan, and Susan Athey. "Estimation and inference of heterogeneous treatment effects using random forests." Journal of the American Statistical Association 113.523 (2018): 1228-1242.
- Rzepakowski, P., & Jaroszewicz, S. (2012). Decision trees for uplift modeling with single and multiple treatments. Knowledge and Information Systems, 32, 303-327.
- annik Rößler, Richard Guse, and Detlef Schoder. The best of two worlds: using recent advances from uplift modeling and heterogeneous treatment effects to optimize targeting policies. International Conference on Information Systems, 2022.