目录
概
由于一些未观测数据的存在, 一般的损失估计会存在 bias, 导致经此训练后的模型的表现不是很好. 本文提出用一种无偏的估计 (IPS) 来替代.
符号说明
- /(u /in /{1, 2, /cdots, U/}/), user;
- /(i /in /{1, 2, /cdots, I/}/), item;
- /(Y /in /mathbb{R}^{U /times I}/), true ratings;
- /(O /in /{0, 1/}^{U /times I}/), /(O_{u,i} = 1/) 表示 /(Y_{u, i}/) 是观测到的数据;
- /(P_{u, i} := P(O_{u, i} = 1)/);
MNAR 带来的 bias
通常, 我们希望最小化如下的损失来优化预测 /(/hat{Y}/):
/[/tag{1}
R(/hat{Y}) = /frac{1}{UI} /sum_{u=1}^U /sum_{i=1}^I /delta_{u, i} (Y, /hat{Y}),
/]
这里 /(/delta_{u, i}/) 可以是
/[/begin{array}{rl}
/text{MAE:} & /delta_{u, i}(Y, /hat{Y}) = |Y_{u, i} – /hat{Y}_{u, i}|, //
/text{MSE:} & /delta_{u, i}(Y, /hat{Y}) = (Y_{u, i} – /hat{Y}_{u, i})^2, //
/text{Accuracy:} & /delta_{u, i}(Y, /hat{Y}) = /mathbb{I} (Y_{u, i} = /hat{Y}_{u, i}). //
/end{array}
/]
但是, 因为部分数据 /(Y_{u, i}/) 的缺失, 我们通常用如下的损失替代:
/[/tag{5}
/hat{R}_{naive}(/hat{Y}) = /frac{1}{|/{(u, i): O_{u, i} = 1/}|} /sum_{(u, i): O_{u, i} = 1} /delta_{u, i} (Y, /hat{Y}).
/]
但是 (5) 通常只有在 MCAR (Missing Completely At Random) /(P_{u,i} /equiv p/) 的 uniform 的情况 (且互相独立) 下才是 (1) 的无偏估计:
/[/begin{array}{ll}
/mathbb{E}_{O} [/hat{R}_{naive}(/hat{Y})]
&=/mathbb{E}_{O}[/frac{1}{|/{(u, i): O_{u, i} = 1/}|} /sum_{(u, i): O_{u, i} = 1} /delta_{u, i} (Y, /hat{Y})] //
&=/sum_{(u, i)} /delta_{u, i} (Y, /hat{Y}) /mathbb{E}_{O_{u, i}}[/frac{1}{/sum_{u, i} O_{u, i}} O_{u, i}] //
&= /mathbb{E}_{O}[/frac{O}{/sum_{u, i} O_{u, i}}] /: /sum_{(u, i)} /delta_{u, i} (Y, /hat{Y}) /: /leftarrow /text{ [MCAR] } O_{u,i} /perp /!/!/! /perp O_{u’, i’} + P_{u,i} /equiv p //
&= /frac{1}{UI} /: /sum_{(u, i)} /delta_{u, i} (Y, /hat{Y}) /: /leftarrow /sum_{u, i} /mathbb{E}_{O_{u,i}} [/frac{O_{u, i}}{/sum_{u’, i’} O_{u’, i’}}] = 1,
/mathbb{E}_{O_{u,i}} [/frac{O_{u, i}}{/sum_{u’, i’} O_{u’, i’}}]=
/mathbb{E}_{O_{/tilde{u},/tilde{i}}} [/frac{O_{/tilde{u}, /tilde{i}}}{/sum_{u’, i’} O_{u’, i’}}] .
/end{array}
/]
而通常的 MNAR (Missing Not At Random) 情况, 上述的无偏性就失效了, 即
/[/mathbb{E}_O [/hat{R}_{naive}(/hat{Y})] /not= R(/hat{Y}).
/]
IPS Estimator
我们可以用如下的 Inverse-Propensity-Scoring (IPS) estimator 来替代 (5):
/[/tag{10}
/hat{R}_{IPS}(/hat{Y}|P) = /frac{1}{UI} /sum_{(u, i): O_{u,i} =1} /frac{/delta_{u, i} (Y, /hat{Y})}{P_{u, i}},
/]
其中 /(|P/) 表示各 /(P_{u,i}/) 都是已知的, 当然这是比较理想的情况, 后面会给出更切实际的替代.
容易发现:
/[/begin{array}{ll}
/mathbb{E}_{O} [/hat{R}_{IPS}(/hat{Y}|P)]
&=/frac{1}{UI} /sum_{(u, i)} /mathbb{E}_{O_{u,i}} [/frac{/delta_{u, i} (Y, /hat{Y})}{P_{u, i}} O_{u,i}] //
&=/frac{1}{UI} /sum_{(u, i)} /frac{/delta_{u, i} (Y, /hat{Y})}{P_{u, i}} /mathbb{E}_{O_{u,i}} [O_{u,i}] //
&=/frac{1}{UI} /sum_{(u, i)} /delta_{u, i} (Y, /hat{Y})//
&= R(/hat{Y}).
/end{array}
/]
故 (10) 是一个无偏统计量.
IPS Estimator 的变化性
Proposition 3.1 (Tail Bound for IPS Estimator): 倘若 /(O_{u,i}/) 相互独立. 则给定任意的 /(/hat{Y}, Y/), 至少有 /(1 – /eta/) 的概率保证
/[|/hat{R}_{IPS}(/hat{Y}|P) – R(/hat{Y})| /le /frac{1}{UI} /sqrt{/frac{/log /frac{2}{/eta}}{2} /sum_{u, i} /rho_{u,i}^2},
/]
其中 /(/rho_{u,i} = /frac{/delta_{u, i} (Y, /hat{Y})}{P_{u, i}}/) 如果 /(P_{u,i}/) 否则 /(/rho_{u,i} = 0/).
proof:
令 /(Z_{u,i} := /rho_{u,i} O_{u,i}/), 则
/[/begin{array}{ll}
P(|/hat{R}_{IPS}(/hat{Y}|P) – R(/hat{Y})| /ge /epsilon)
&=P(|/sum_{u,i} (Z_{u,i} – /mathbb{E}[Z_{u,i}])| /ge UI /epsilon) //
&/le 2 /exp(-/frac{2(UI/epsilon)^2}{/sum_{u, i}/rho_{u, i}^2}) /: /leftarrow /text{Hoeffding’s inequality}.
/end{array}
/]
只需令等式右端等于 /(/eta/), 然后求解出 /(/epsilon/) 即可.
当 /(P_{u,i} /equiv p/) 的时候, 上界大概是 /(O(1 / p/sqrt{UI})/) 级别的, 当 /(P_{u,i}/) 的分布严重不 uniform 的时候, 上界可能变得很大 (比如某个 /(P_{u,i}/) 特别小, 那么由于 /(P_{u,i}/) 作为分母, 会导致某个 /(/rho_{u, i} /rightarrow /infty/)). 所以, 可以说 IPS 用变化性交易了无偏性.
例子
- ML100K数据集, 其上的 /(Y/) 是全部可知的;
- 通过指定 /(P_{u, i}/) 使得观测到的量在 /(5/%/) 左右;
- 构造不同的 /(/hat{Y}/):
- REC_ONES: /(/hat{Y}_{u, i} = Y_{u,i}/) 除了在 /(/{(u, i):Y_{u,i}=1/}/) 上, 随机将这些元素的打分设置为 /(/hat{Y}_{u, i} = 5/);
- REC_FOURS: 和上面的类似, 作用于 /(4/) 上;
- ROTATE: /(/hat{Y}_{u, i} = Y_{u, i} – 1, /text{ if } Y_{u, i} /ge 2/), /(/hat{Y}_{u, i} = 5, /text{ if } Y_{u, i} = 1/);
- SKEWED: /(/hat{Y}_{u, i}/) 从 /(/mathcal{N}(/cdot|/mu = Y_{u,i}, /sigma=/frac{6 – Y_{u,i}}{2})/) 中采样, 然后截断至 /([0, 6]/);
- COARSENED: /(/hat{Y}_{u, i} = 3, /text{ if } Y_{u,i} /le 3/), 否则 /(/hat{Y}_{u, i} = 4/);
- 在这几种不同的情况下, 我们估计 MAE 所上图所示, 可以发现, IPS 比 Naive 要准确的多 (但是并不那么稳定).
注: 其它指标回看论文.
利用 IPS estimator 进行训练
令
/[/tag{12}
/hat{Y}^{ERM} = /mathop{/text{argmin}} /limits_{/hat{Y} /in /mathcal{H}} /{/hat{R}_{IPS} (/hat{Y}|P)/}
/]
为在空间 /(/mathcal{H}/) 中的一个最优解.
泛化界
Theorem 4.2 (Propensity-Scored ERM Generalization Err Bound): 假设空间 /(/mathcal{H} = /{/hat{Y}_1, /ldots, /hat{Y}_{|/mathcal{H}|}/}/) 是有限的, 且 /(0 /le /delta_{u, i}(Y, /hat{Y}) /le /Delta/), /(P_{u,i}/) 是互相独立的. 此时至少有概率 /(1-/eta/) 能够保证
/[R(/hat{Y}^{ERM}) /le /hat{R}_{IPS} (/hat{Y}^{ERM}|P) + /frac{/Delta}{UI} /sqrt{/frac{/log (2|/mathcal{H} / /eta|)}{2}} /sqrt{/sum_{u, i} /frac{1}{P^2_{u, i}}}.
/]
proof:
/[/begin{array}{ll}
P(|R(/hat{Y}^{ERM}) – /hat{R}_{IPS} (/hat{Y}^{ERM}|P) | /le /epsilon)
&/ge P(/max_{/hat{Y}_i} |R(/hat{Y}_i) – /hat{R}_{IPS} (/hat{Y}_i|P) | /le /epsilon) //
&= P(/bigvee_{/hat{Y}_i} |R(/hat{Y}_i) – /hat{R}_{IPS} (/hat{Y}_i|P) | /le /epsilon) //
&= 1 – P(/bigwedge_{/hat{Y}_i} |R(/hat{Y}_i) – /hat{R}_{IPS} (/hat{Y}_i|P) | /ge /epsilon) //
&/ge 1 – /sum_{i=1}^{/mathcal{H}} P(|R(/hat{Y}_i) – /hat{R}_{IPS} (/hat{Y}_i|P) | /ge /epsilon) //
&/ge 1 – |/mathcal{H}| /cdot 2 /exp(/frac{-2/epsilon^2 U^2 I^2}{/sum_{u, i} /frac{/Delta^2}{P_{u,i}^2}}) /: /leftarrow /text{ Proposition 3.1}. //
/end{array}
/]
令最后的部分等于 /(1-/eta/) 然后求解出 /(/epsilon/) 即可.
这意味着, 优化 (12) 实际上是在优化原先的一个上界.
例子
以 matrix factorization
/[/hat{Y}_{u, i} = v_u^T w_i + a_{ui}
/]
为例, 此时需要优化
/[/mathop{/text{argmin}} /limits_{V, W, A} /Big[
/sum_{O_{u, i} = 1} /frac{/delta_{u, i}(Y, V^TW + A)}{P_{u,i}} + /lambda (/|V/|_F^2 + /|W/|_F^2)
/Big].
/]
估计 Propensity Score
然而在实际中, /(P_{u, i}/) 通常是未知的, 此时我们需要估计 /(/hat{P}_{u, i}/). 容易发现
/[/text{bias}(/hat{R}_{IPS}(/hat{Y}|/hat{P})) :=
/hat{R}(/hat{Y}) – /mathbb{E}_O[/hat{R}_{IPS}(/hat{Y}|/hat{P})] = /sum_{u, i} /frac{/delta_{u,i} (Y, /hat{Y})}{UI} /Big[ 1 – /frac{P_{u, i}}{/hat{P}_{u, i}} /Big]
/]
即, 此时无偏性以及失去了.
泛化界
利用 /(/hat{R}_{IPS}(/hat{Y}|/hat{P})/) 的泛化界为:
Theorem 5.2 (Propensity-Scored ERM Generalization Error Bound under Inaccurate Propensities): 假设空间 /(/mathcal{H} = /{/hat{Y}_1, /ldots, /hat{Y}_{|/mathcal{H}|}/}/) 是有限的, 且 /(0 /le /delta_{u, i}(Y, /hat{Y}) /le /Delta/), /(P_{u,i}/) 是互相独立的. 此时至少有概率 /(1-/eta/) 能够保证
/[R(/hat{Y}^{ERM}) /le /hat{R}_{IPS} (/hat{Y}^{ERM}|/hat{P}) + /frac{/Delta}{UI} /sum_{u,i}|1 – /frac{P_{u, i}}{/hat{P}_{u, i}}| + /frac{/Delta}{UI} /sqrt{/frac{/log (2|/mathcal{H} / /eta|)}{2}} /sqrt{/sum_{u, i} /frac{1}{/hat{P}^2_{u, i}}}.
/]
proof:
只需注意到:
/[/begin{array}{rl}
& |R(/hat{Y}^{ERM}) – /hat{R}_{IPS} (/hat{Y}^{ERM}|/hat{P}) | //
=& |R(/hat{Y}^{ERM}) – /mathbb{E}_{O}[R(/hat{Y}^{ERM}|/hat{P}) ] + /mathbb{E}_{O}[R(/hat{Y}^{ERM}|/hat{P}) ] – /hat{R}_{IPS} (/hat{Y}^{ERM}|/hat{P}) | //
/le& |R(/hat{Y}^{ERM}) – /mathbb{E}_{O}[R(/hat{Y}^{ERM}|/hat{P}) ]| + |/mathbb{E}_{O}[R(/hat{Y}^{ERM}|/hat{P}) ] – /hat{R}_{IPS} (/hat{Y}^{ERM}|/hat{P}) | //
/le& /frac{/Delta}{UI} /sum_{u,i} |1 – /frac{P_{u,i}}{P_{u,i}}| + |/mathbb{E}_{O}[R(/hat{Y}^{ERM}|/hat{P}) ] – /hat{R}_{IPS} (/hat{Y}^{ERM}|/hat{P}) | //
/end{array}
/]
而后者通过和定理 4.2 无二的证明方式即可.
上面的结论给出一个泛化界, 至于具体的估计方法, 作者给出了 Naive Bayes 和 Logistic Regression 两种方法.
疑问
需要注意的是, 一般的 Propensity Score /(e(X)/) 需要满足:
/[X /perp /!/!/! /perp Z | e(X),
/]
其中
/[e(X) := P(Z|X).
/]
在这里, 我们可以理解为
/[e(U, V) = P(O|U, V),
/]
是一种实例级别的划分. 在实际情况中, 通常应该是
/[e(X) = P(O|X(U, V)),
/]
即满足相同性质 /(X/) 的 /(U, V/) 服从相同的缺失率. 可以说文章中的两个估计方法就是依此准则来估计的, 而并非实例级别的估计.
代码
[official]
原创文章，作者：wure，如若转载，请注明出处：https://blog.ytso.com/274832.html