目录

• 概
• 符号说明
• MNAR 带来的 bias
• IPS Estimator
  • IPS Estimator 的变化性
  • 例子
• 利用 IPS estimator 进行训练
  • 泛化界
  • 例子
• 估计 Propensity Score
  • 泛化界
• 疑问
• 代码

Schnabel T., Swaminathan A., Singh A., Chandak N., Joachims T. Recommendations as treatments: debiasing learning and evaluation. In International Conference on Machine Learning (ICML), 2016

概

由于一些未观测数据的存在, 一般的损失估计会存在 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 用变化性交易了无偏性.

例子

1. ML100K数据集, 其上的 \(Y\) 是全部可知的;
2. 通过指定 \(P_{u, i}\) 使得观测到的量在 \(5\%\) 左右;
3. 构造不同的 \(\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\);
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) 实际上是在优化原先的一个上界.

例子

以 ma￾trix 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]