Shapley - 原理与 C++ 实现

写在前面——我发现我的四肢都各有各的想法，腿想跷二郎腿，肩膀不自觉往上怂，手指像刷手机，眼睛想闭起来，头皮想被扣，嘴巴想吃东西，需要学习的季节总是这么难熬。

原理部分

首先是对公式的理解，其次是用 C++ 来实现公式。公式本身基于排列组合和概率论：

\phi_i = \sum_{S \subseteq N \setminus \{i\}} \frac{\vert{}S\vert{}!(\vert{}N\vert{} - \vert{}S\vert{} - 1)!}{\vert{}N\vert{}!} \big(v(S \cup \{i\}) - v(S)\big)

假设特征数为 $N$ ， $S$ 代表不包含特征 $i$ 的一个特征子集。 $v(S)$ 代表只给定特征子集 $S$ 时的模型预测结果。

好比说对于一个评估牛马工作效率状态的项目来说，通过分析牛马的睡眠，咖啡因摄入量，运动，环境（比如图书馆或者在家）对每天的productivity的影响，这里的特征数为 $N = 4$ ， $S$ 作为 $N$ 子集，共有 $2^N$ 个，在子集的表示上用2进制来表达当前子集中包含哪些特征，0101 从右往左看，包含了第1和第3个特征。

在上述公式中，边际贡献 $\big(v(S \cup \{i\}) - v(S)\big)$ 表示对于特征子集（好比说对于子集 $S$ 0101， $S \cup \{i\}$ 即为0111 或 1101）， $v(S)$ 代表对特征子集 $S$ 时的模型预测结果，计算 $v(S)$ 时处理那些不在 $S$ 中的特征时可以选择用整体平均值代替或者基于预先设定的值。

\text{Weight} = \frac{\vert{}S\vert{}!(\vert{}N\vert{} - \vert{}S\vert{} - 1)!}{\vert{}N\vert{}!}

权重的计算基于概率论，

分母 $\vert{}N\vert{}!$ ：代表了所有 $\vert{}N\vert{}$ 个特征排队的总排列方式（比如 4 个特征就有 $4 \times 3 \times 2 \times 1 = 24$ 种不同的出场顺序）。
分子 $\vert{}S\vert{}!(\vert{}N\vert{} - \vert{}S\vert{} - 1)!$ ：代表在所有的排队方式中，刚好是子集 $S$ 先出场，然后特征 $i$ 紧跟着出场的情况总数。

具体实现

在用 C++ 实现过程中核心思想是用位运算（Bitwise operations）遍历并组合特征。

实现 v 函数

int fact(int n); // 算阶乘
std::array<double, 4> current_instance{}; // 待解释的样本 x
std::array<double, 4> baseline_instance{}; // 参照值
// 实例model
double model(const Vec& x) {
	return 2.0 * x[0] + 1.5 * x[1] + 0.5 * x[2] * x[3];
} 
double evaluate_model(int mask){
	int N = 4;
	std::array<double, 4> hybrid_instance;
	for(int k = 0;k < N; k++){
		if(mask & (1<<k)){
		hybrid_instance[k] = current_instance[k];
		}
		else{
		hybrid_instance[k] = baseline_instance[k];
		}
	}
	return model(hybrid);
}

主循环

double fact(int n) { //求阶乘
	double r = 1.0;
	for (int i = 2; i <= n; ++i) r *= i;
	return r;
}
int main(){
	int N = 4;
	int n = 1<< N ; // 通过位移得到 2^N 
	double sum {0};
	std::array<double, 4> shapley_values{0.0}; // 初始化
	for(int i=0;i<N;i++){ //基于特征的主循环
		for(int mask=0;mask<n;mask++){ // 遍历所有
			if((mask & (1<<i))==0){ // 确保特征 i 不在 S 中
				int S_size = __builtin_popcount(mask); //｜S｜
				double weight = (fact(S_size) * fact(N - S_size - 1)) / (double)fact(N);
				double marginal_contribution = evaluate_model(mask | (1 << i)) - evaluate_model(mask);
				shapley_values[i]+=weight * marginal_contribution;
			}
		}
	}
}

Page Views: 10

原理部分

具体实现

实现 v 函数

主循环

评论