利用逆倾向分数 (IPS) 降低选择偏差

Recommendations as Treatments: Debiasing Learning and Evaluation

1 引言
2 相关工作
3 推荐的无偏性能估计
3.1 任务 1：估计评分预测的准确度
3.2 任务 2：估计推荐质量
3.3 倾向分数的性能估计量
3.4 估计量的实验示例
4 倾向分数的推荐学习
4.1 使用倾向的推荐 ERM
4.2 倾向分数矩阵分解
5 对于观测数据的倾向估计
5.1 倾向估计模型

1 引言

推荐系统中几乎所有数据都受选择偏差 (selection bias) 的限制。以想要优化的效果为条件进行观测会导致数据出现非随机缺失 Missing Not At Random (MNAR)。以因果推断的视角来看，在推荐系统中向一个用户推荐一个物品就是一次介入 (intervention)。

本文主要贡献：

使用因果推断等问题中常用的倾向加权 (propensity-weighting) 技术来估计推荐系统质量。特别是得到了许多性能指标（如 MSE, MAE, DCG）的无偏估计。
使用这些估计量提出了一个在选择偏差下学习推荐系统的经验风险最小化 Empirical Risk Minimization (ERM) 框架，并推导了泛化误差上界 (generalization error bound)。
使用 ERM 框架得到了一个可以解释选择偏差的矩阵分解 (matrix factorization) 方法。
探讨了在观测背景 observational settings（选择偏差是由于用户的自己选择）下估计倾向的方法，描述了框架对于错误指定的倾向的鲁棒性。

2 相关工作

过去处理推荐数据 MNAR 的方法是基于缺失值模型和评分模型的联合似然 (joint likelihood) 进行缺失值填充。

3 推荐的无偏性能估计

例子：

用户 $u\in\{1,\dots,U\}$ ，电影 $i\in\{1,\dots,I\}$

图 1 中真实评分矩阵 $Y\in\Re^{U\times I}$

二元矩阵 $O\in\{0,1\}^{U\times I}$ 表示用户提供了哪部电影的评分， $[O_{u,i}=1]\Leftrightarrow [\small观测到\normalsize\;Y_{u,i}].$

例子中喜欢电影和给电影评分强相关，矩阵 $P$ 描述边缘概率 $P_{u,i}=P(O_{u,i}=1)$ ，每个评分以该概率显现出来。

考虑如下两个任务：

3.1 任务 1：估计评分预测的准确度

该任务评价一个预测的评分矩阵 $\hat{Y}$ 能够多好地反映真实评分 $Y$ 。标准评价指标比如平均绝对值误差 Mean Absolute Error (MAE) 和均方误差 Mean Squared Error (MSE) 可以写成这样的形式：

$R(\hat{Y})=\frac{1}{U\cdot I}\sum_{u=1}^{U}\sum_{i=1}^{I}\delta_{u,i}(Y,\hat{Y}) \tag{1}$

其中 $\delta_{u,i}(Y,\hat{Y})$ 适当地选择。

$\begin{aligned} \text{MAE:}\quad \delta_{u,i}(Y,\hat{Y})&=|Y_{u,i}-\hat{Y}_{u,i}|,\\ \text{MSE:}\quad \delta_{u,i}(Y,\hat{Y})&=(Y_{u,i}-\hat{Y}_{u,i})^2,\\ \text{Accuracy:}\quad \delta_{u,i}(Y,\hat{Y})&=\mathbf{1}\{Y_{u,i}=\hat{Y}_{u,i}\}. \end{aligned}$

传统方法：由于 $Y$ 仅部分可知，只在观测到的项上取平均来估计 $R(\hat{Y})$

$\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}).\tag{5}$

该估计量称为朴素估计量。以图 1 中 $\hat{Y}_1$ 和 $\hat{Y}_2$ 为例， $\hat{R}_{naive}(\hat{Y})$ 会认为 $\hat{Y}_2$ 比 $\hat{Y}_1$ 有更好的 MAE。该错误就是由于选择偏差，由于 1 星的评分在观测到的数据中没有被充分表示， $\delta_{u,i}(Y,\hat{Y})$ 和 $Y_{u,i}$ 是相关的。 $\hat{R}_{naive}(\hat{Y})$ 不是真实性能 $R(\hat{Y})$ 的无偏估计：

$\mathbb{E}_O[\hat{R}_{naive}(\hat{Y})]\ne R(\hat{Y}).$

3.2 任务 2：估计推荐质量

将 $\hat{Y}$ 重新定义为类似于 $O$ 的二元矩阵来编码推荐， $[\hat{Y}_{u,i}=1]\Leftrightarrow [i\;\small被推荐给\normalsize\;u]$ ，限制每个用户 $k$ 个推荐。图 1 中的 $\hat{Y}_3$ 为例子。一种合理的度量推荐质量的方法是用户从推荐的电影中获得的累积增益 Cumulative Gain (CG)，这里在例子中定义为被推荐的电影的平均评分。CG 可以写成公式 (1) 的形式：

$\text{CG:}\quad \delta_{u,i}(Y,\hat{Y})=(I/k)\hat{Y}_{u,i}\cdot Y_{u,i}.$

但除非用户看过了 $\hat{Y}$ 中的所有电影，否则是无法通过公式 (1) 直接计算出 CG 的。

反事实问题 (counterfactual question)：只有 $O_{u,i}=1$ 即用户 $u$ 提供了电影 $i$ 的评分才观测到 $Y_{u,i}$ 。那么如果用户不去看 $O$ 中显示的电影，而是去看我们的推荐 $\hat{Y}$ ，（用 CG 来表示）用户会感觉怎么样呢？

对于推荐的顺序和上面描述的基于集合的推荐类似，如折扣累积增益 Discounted Cumulative Gain (DCG), DCG@k, 前 k 准确度 Precision at k (PREC@k) 等指标也适用于这个背景。对于这些，将每行中 $\hat{Y}$ 的值定义为预测的排序，那么

$\begin{aligned} \text{DCG:}\quad \delta_{u,i}(Y,\hat{Y})&=(I/\log(\text{rank}(\hat{Y}_{u,i})))Y_{u,i},\\ \text{PREC@k:}\quad \delta_{u,i}(Y,\hat{Y})&=(I/k)Y_{u,i}\cdot\mathbf{1}\{\text{rank}(\hat{Y}_{u,i}\le k)\}. \end{aligned}$

一种方法是再次使用公式 (5) 的朴素估计量，但它是 $R(\hat{Y})$ 的有偏估计。

3.3 倾向分数的性能估计量

生成 $O$ 中观测模式的过程在因果推断中称为分配机制 (Assignment Mechanism)，在缺失值分析中称为缺失值机制 (Missing Data Mechanism)。区分出下面两种背景：

实验背景 (Experimental Setting)：分配机制受推荐系统控制，如广告放置系统控制给哪个用户展示什么广告。
观测背景 (Observational Setting)：用户是生成 $O$ 的分配机制的部分，如在线电影服务中用户自己选择想看的电影并评分。

假设分配机制是基于概率的，即观测到一项 $Y_{u,i}$ 的边缘概率 $P_{u,i}=P(O_{u,i}=1)$ 对于所有用户/物品对都是非零的。把 $P_{u,i}$ 称作观测到 $Y_{u,i}$ 的倾向 (propensity)。实验背景中已知所有倾向的矩阵 $P$ ，因为我们实现了分配机制。观测背景中需要从观测到的矩阵 $O$ 中估计 $P$ 。首先关注实验背景。

IPS 估计量 逆倾向分数 Inverse-Propensity-Scoring (IPS) 估计量定义为：

$\hat{R}_{IPS}(\hat{Y}|P)=\frac{1}{U\cdot I}\sum_{(u,i):O_{u,i}=1}\frac{\delta_{u,i}(Y,\hat{Y})}{P_{u,i}}.\tag{10}$

IPS 估计量对于任意基于概率的分配机制都是无偏的，无偏性不受 $O$ 内的依赖关系影响：

$\begin{aligned} \mathbb{E}_O\Big[\hat{R}_{IPS}(\hat{Y}|P)\Big]&=\frac{1}{U\cdot I}\sum_u\sum_i\mathbb{E}_{O_{u,i}}\Bigg[\frac{\delta_{u,i}(Y,\hat{Y})}{P_{u,i}}O_{u,i}\Bigg]\\ &=\frac{1}{U\cdot I}\sum_u\sum_i\delta_{u,i}(Y,\hat{Y})=R(\hat{Y}). \end{aligned}$

为研究 IPS 估计量的变化性 (variability)，假设在给定 $P$ 的条件下观测是相互独立的，对应于一个多元伯努利模型，每个 $O_{u,i}$ 都有概率 $P_{u,i}$ 。下面的命题提供了一些关于当倾向变得更“不均匀”时 IPS 估计量的准确性如何变化的直觉知识。

命题 3.1（IPS 估计量的尾界）令 $P$ 为观测到每项的独立伯努利概率。对于给定的 $\hat{Y}$ 和 $Y$ ，IPS 估计量 $\hat{R}_{IPS}(\hat{Y}|P)$ 以 $1-\eta$ 的概率不会偏离真实的 $R(\hat{Y})$ 超过：

$\Big|\hat{R}_{IPS}(\hat{Y}|P)-R(\hat{Y})\Big|\le\frac{1}{U\cdot I}\sqrt{\frac{\log \frac{2}{\eta}}{2}\sum_{u,i}\rho_{u,i}^2},$

其中当 $P_{u,i}<1$ 时 $\rho_{u,i}=\frac{\delta_{u,i}(Y,\hat{Y})}{P_{u,i}}$ ，否则 $\rho_{u,i}=0$ 。

证明 霍夫丁不等式 (Hoeffding’s inequality) 说明对于相互独立的有界的随机变量 $Z_1,\dots,Z_n$ ，以概率 1 取值分别在大小为 $\rho_1,\dots,\rho_n$ 的区间，对于任意 $\epsilon >0$ ，

$P\bigg(\bigg|\sum_kZ_k-E\bigg[\sum_kZ_k\bigg]\bigg|\ge\epsilon\bigg)\le2\exp\Big(\frac{-2\epsilon^2}{\sum_k\rho_k^2}\Big).$

定义

$Z_k=\begin{cases} \frac{1}{U\cdot I}\cdot\frac{\delta_{u,i}(Y,\hat{Y})}{P_{u,i}},&\quad \text{w/ prob.}\ P_{u,i},\\ 0,&\quad\text{w/ prob.}\ 1-P_{u,i}. \end{cases}$

则

$\begin{aligned} \sum_kZ_k&=\sum_{(u,i)}\frac{1}{U\cdot I}\cdot\frac{\delta_{u,i}(Y,\hat{Y})}{P_{u,i}}\cdot O_{u,i}\\ &=\frac{1}{U\cdot I}\sum_{(u,i):O_{u,i}=1}\frac{\delta_{u,i}(Y,\hat{Y})}{P_{u,i}}\\ &=\hat{R}_{IPS}(\hat{Y}|P). \end{aligned}$

且

$E\bigg[\sum_kZ_k\bigg]=E\Big[\hat{R}_{IPS}(\hat{Y}|P)\Big]=R(\hat{Y}).$

而

$\rho_k=\begin{cases} \frac{1}{U\cdot I}\cdot\frac{\delta_{u,i}(Y,\hat{Y})}{P_{u,i}},&\text{if}\ P_{u,i}<1,\\ 0,&\text{otherwise}. \end{cases}$

那么令

$\rho_{u,i}=\begin{cases} \frac{\delta_{u,i}(Y,\hat{Y})}{P_{u,i}},&\text{if}\ P_{u,i}<1,\\ 0,&\text{otherwise}. \end{cases}$

则有 $\rho_k=\frac{\rho_{u,i}}{U\cdot I}$ ，带入霍夫丁不等式，得

$P\Big(\Big|\hat{R}_{IPS}(\hat{Y}|P)-R(\hat{Y})\Big|\ge\epsilon\Big)\le2\exp\Big(\frac{-2\epsilon^2U^2\cdot I^2}{\sum_{u,i}\rho_{u,i}^2}\Big).$

解出 $\epsilon$ 即证。

考虑均匀的倾向 $P_{u,i}=p$ ，这意味着期望意义下有 $n=pUI$ 个 $Y$ 中的元素显示出来。这样，这个界就是 $O(1/(p\sqrt{UI}))$ 。如果 $P_{u,i}$ 是非均匀的，即便期望的显示的元素数量 $\sum P_{u,i}$ 是 $n$ ，这个界也会大得多。这里是用了很大的变化性 (variability) 来保证无偏性。

SNIPS 估计量 一种降低变化性的方法是利用控制变量 (control variants)。在 IPS 估计量上应用，有 $\mathbb{E}_o\Big[\sum_{(u,i):O_{u,i}=1}\frac{1}{P_{u,i}}\Big]=U\cdot I$ 。可以得到自归一化逆倾向分数 Self-Normalized Inverse Propensity Scoring (SNIPS) 估计量：

$\hat{R}_{SNIPS}(\hat{Y}|P)=\frac{\sum_{(u,i):O_{u,i}=1}\frac{\delta_{u,i}(Y,\hat{Y})}{P_{u,i}}}{\sum_{(u,i):O_{u,i}=1}\frac{1}{P_{u,i}}}.$

SNIPS 估计量通常会有比 IPS 估计量更低的方差，但偏差也更小。

3.4 估计量的实验示例

使用了半人造的 ML100K 数据集（见 6.2 节），其中 $Y$ 完全已知，因而可以使用公式 (1) 计算真实性能。选择观测到评分 $Y_{u,i}$ 的概率 $P_{u,i}$ 来模仿原始的 ML100K 数据集中观测的边缘评分分布，平均 5% 的 $Y$ 矩阵被显示出来了。

表 1 是下面五种预测矩阵 $\hat{Y}_i$ 使用 MAE 估计评分预测的准确度和使用 DCG@50 估计推荐质量的结果。

REC_ONES：预测矩阵 $\hat{Y}$ 和真实评分矩阵 $Y$ 相同，除了将 $|\{(u,i):Y_{u,i}=5\}|$ 个随机选择的真实评分为 1 翻转为 5。这意味着一半预测的 5 是真实的 5，一半是真实的 1。
REC_FOURS：与 REC_ONES 相同，但翻转的是 4 星的评分。
ROTATE：当 $Y_{u,i}\ge 2$ 时每个预测评分 $\hat{Y}_{u,i}=Y_{u,i}-1$ ，当 $Y_{u,i}=1$ 时 $\hat{Y}_{u,i}=1$ 。
SKEWED：预测的 $\hat{Y}_{u,i}$ 是从 $\mathcal{N}(\hat{Y}_{u,i}^{raw}|\mu=Y_{u,i},\sigma=\frac{6-Y_{u,i}}{2})$ 并裁剪到区间 $[0,6]$ 。
COARSENED：如果真实评分 $Y_{u,i}\le3$ ，那么 $\hat{Y}_{u,i}=3$ 。否则 $\hat{Y}_{u,i} = 4$ 。

DCG@50 使用的排名是对于每个用户用物品相应的 $\hat{Y}_i$ 排序得到的。

结论：对于 MAE 和 DCG，IPS 和 SNIPS 的偏差都很小，朴素估计量严重有偏，估计的 MAE 把预测矩阵 $\hat{Y}_i$ 得到的排序甚至是错的（它认为 REC_ONES 的性能比 REC_FOURS 更好）。IPS 和 SNIPS 的标准差远小于朴素估计量的偏差。此外，对于 MAE，SNIPS 能够降低 IPS 的标准差，但对于 DCG 不能。

4 倾向分数的推荐学习

使用前面的无偏估计量在经验风险最小化 Empirical Risk Minimization (ERM) 框架下学习，证明泛化误差上界 (generalization error bound)，并得到一个用于评分预测的矩阵分解 (matrix factorization) 方法。

4.1 使用倾向的推荐 ERM

通过体现出公式 (1) 对应于数据生成过程 $P(O|P)$ 上的期望损失（即风险），调整 ERM 适应于当前背景。给定一个来自于 $P(O|P)$ 的样本，可以把公式 (10) 的 IPS 估计量视为对任意 $\hat{Y}$ 估计 $R(\hat{Y})$ 的经验风险 (Empirical Risk) $\hat{R}(\hat{Y})$ 。

定义 4.1（倾向分数的推荐 ERM）给定以边缘倾向 $P$ 从 $Y$ 中得到的训练观测 $O$ ，一个预测 $\hat{Y}$ 的假设空间 $\mathcal{H}$ ，以及一个损失函数 $\delta_{u,i}(Y,\hat{Y})$ ，ERM 选择 $\hat{Y}\in\mathcal{H}$ 最优化：

$\hat{Y}^{ERM}=\argmin_{\hat{Y}\in\mathcal{H}}\Big\{\hat{R}_{IPS}(\hat{Y}|P)\Big\}.$

为说明倾向分数 ERM 方法的有效性，下面说明泛化误差上界，为简便只考虑有限 $\mathcal{H}$ 。

定理 4.2（倾向分数 ERM 的泛化误差上界）对于任意的有限的预测假设空间 $\mathcal{H}=\{\hat{Y}_1,\dots,\hat{Y}_{|\mathcal{H}|}\}$ 和损失 $0\le\delta_{u,i}(Y,\hat{Y})\le\Delta$ ，给定以相互独立的伯努利倾向 $P$ 从 $Y$ 中得到的训练观测 $O$ ，使用 IPS 估计量从 $\mathcal{H}$ 中得到的经验风险最小的 $\hat{Y}^{ERM}$ 的真实风险 $R(\hat{Y})$ 以 $1-\eta$ 的概率上界为：

$R(\hat{Y}^{ERM})\le \hat{R}_{IPS}(\hat{Y}^{ERM}|P)+\frac{\Delta}{U\cdot I}\sqrt{\frac{\log(2|\mathcal{H}|/\eta)}{2}}\sqrt{\sum_{u,i}\frac{1}{P_{u,i}^2}}.$

证明

Union bound：

$P\bigg(\bigcup_iA_i\bigg)\le\sum_iP(A_i)$

$\begin{aligned} &P\Big(\Big|\hat{R}_{IPS}(\hat{Y}|P)-R(\hat{Y})\Big|\le\epsilon\Big)\ge1-\eta\\ \Leftarrow \;&P\Big(\max_{\hat{Y}_i}\Big|R(\hat{Y}_i)-\hat{R}_{IPS}(\hat{Y}_i|P)\Big|\le\epsilon\Big)\ge1-\eta\\ \Leftrightarrow\;&P\Bigg(\bigvee_{\hat{Y}_i}\Big|R(\hat{Y}_i)-\hat{R}_{IPS}(\hat{Y}_i|P)\Big|\ge\epsilon\Bigg)<\eta\\ \Leftarrow\;&\sum_{i=1}^{|\mathcal{H}|}P\Big(\Big|R(\hat{Y}_i)-\hat{R}_{IPS}(\hat{Y}_i|P)\Big|\ge\epsilon\Big)<\eta\\ \Leftarrow\;& |\mathcal{H}|\cdot2\exp\Bigg(\frac{-2\epsilon^2}{\frac{\Delta^2}{U^2\cdot I^2}\sum_{u,i}\frac{1}{P_{u,i}^2}}\Bigg)<\eta \end{aligned}$

解出 $\epsilon$ 即证。

4.2 倾向分数矩阵分解

假设一个标准的 $d$ 阶限制且 $L_2$ 正则化的有用户、物品和全局偏置的矩阵分解模型 $\hat{Y}_{u,i}=v_u^Tw_i+a_u+b_i+c$ 作为假设空间 $\mathcal{H}$ 。倾向分数 ERM 得到下面的训练目标：

$\argmin_{V,W,A}\Bigg[\sum_{O_{u,i}=1}\frac{\delta_{u,i}(Y,V^TW+A)}{P_{u,i}}+\lambda(\|V\|_F^2+\|W\|_F^2)\Bigg]\tag{14}$

其中 $A$ 编码了偏置项， $\hat{Y}^{ERM}=V^TW+A$ 。可以很容易地利用现有的可以有效地、可扩展地解决训练问题的优化算法，本文的实验中使用的是存储受限的BFGS (Limited-memory BFGS)。

传统的不完整的矩阵分解是公式 (14) 对于完全随机缺失 MCAR (Missing Completely At Random) 数据的一种特例，即所有的倾向 $P_{u,i}$ 都相等。

5 对于观测数据的倾向估计

现在考虑观测背景 (Observational Setting)，这时需要估计倾向。估计的倾向只需比朴素的均匀显示观测的假设（即对于所有用户和物品 $P=|\{(u,i):O_{u,i}=1\}|/(U\cdot I)$ ）“更好”就行了。下面描述了就偏差 (bias) 和对学习过程的变化性 (variability) 的影响而言“更好”的倾向。

引理 5.1（IPS 估计量在不准确的倾向下的偏差）令 $P$ 是观测到评分矩阵 $Y$ 中项的边缘概率，且 $\hat{P}$ 为估计的倾向，满足对所有的 $u,i$ ， $\hat{P}_{u,i}>0$ 。使用 $\hat{P}$ 的公式 (10) IPS 估计量的偏差为：

$\text{bias}\Big(\hat{R}_{IPS}(\hat{Y}|\hat{P})\Big)=\sum_{u,i}\frac{\delta_{u,i}(Y,\hat{Y})}{U\cdot I}\bigg[1-\frac{P_{u,i}}{\hat{P}_{u,i}}\bigg].$

证明偏差定义为

$\text{bias}\Big(\hat{R}_{IPS}(\hat{Y}|\hat{P})\Big)=R(\hat{Y})-\mathbb{E}_O\Big[\hat{R}_{IPS}(\hat{Y}|\hat{P})\Big],$

其中 $R(\hat{Y})$ 是 $\hat{Y}$ 在完整评分矩阵上的真实风险。展开两项得到

$\begin{aligned} R(\hat{Y})&=\frac{1}{U\cdot I}\sum_{u,i}\delta_{u,i}(Y,\hat{Y})\\ \mathbb{E}_O\Big[\hat{R}_{IPS}(\hat{Y}|\hat{P})\Big]&=\mathbb{E}_O\Big[\frac{1}{U\cdot I}\sum_{(u,i):O_{u,i}=1}\frac{\delta_{u,i}(Y,\hat{Y})}{\hat{P}_{u,i}}\Big]\\ &=\frac{1}{U\cdot I}\sum_{u,i}\mathbb{E}_{O_{u,i}}\Big[\frac{\delta_{u,i}(Y,\hat{Y})}{\hat{P}_{u,i}}O_{u,i}\Big]\\ &=\frac{1}{U\cdot I}\sum_{u,i}\frac{P_{u,i}}{\hat{P}_{u,i}}\delta_{u,i}(Y,\hat{Y}). \end{aligned}$

两式相减即得。

下面的泛化误差上界描绘了估计的倾向对学习过程的总体影响。

定理 5.2（倾向分数 ERM 在不准确的倾向下的泛化误差上界）对于任意有限的预测假设空间 $\mathcal{H}=\{\hat{Y}_1,\dots,\hat{Y}_{|\mathcal{H}|}\}$ ，使用估计倾向 $\hat{P}$ ( $\hat{P}_{u,i}>0$ ) 的 IPS 估计量，并给定以相互独立的伯努利倾向 $P$ 从 $Y$ 中得到的训练观测 $O$ ，经验风险最小的 $\hat{Y}^{ERM}$ 的转导 (transductive) 预测误差上界为：

$R(\hat{Y}^{ERM})\le\hat{R}_{IPS}(\hat{Y}^{ERM}|\hat{P})+\frac{\Delta}{U\cdot I}\sum_{u,i}\Bigg|1-\frac{P_{u,i}}{\hat{P}_{u,i}}\Bigg|+\frac{\Delta}{U\cdot I}\sqrt{\frac{\log(2|\mathcal{H}|/\eta)}{2}}\sqrt{\sum_{u,i}\frac{1}{\hat{P}_{u,i}^2}}.$

证明首先，注意到由引理 5.1 可得

$\begin{aligned} R(\hat{Y}^{ERM})&=R(\hat{Y}^{ERM})-\mathbb{E}_O\Big[\hat{R}_{IPS}(\hat{Y}^{ERM}|P)\Big]+\mathbb{E}_O\Big[\hat{R}_{IPS}(\hat{Y}^{ERM}|P)\Big]\\ &=\text{bias}\Big(\hat{R}_{IPS}(\hat{Y}^{ERM}|\hat{P})\Big)+\mathbb{E}_O\Big[\hat{R}_{IPS}(\hat{Y}^{ERM}|P)\Big]\\ &\le\frac{\Delta}{U\cdot I}\sum_{u,i}\Bigg|1-\frac{P_{u,i}}{\hat{P}_{u,i}}\Bigg|+\mathbb{E}_O\Big[\hat{R}_{IPS}(\hat{Y}^{ERM}|P)\Big] \end{aligned}$

再找出下面的界

$\begin{aligned} &P\Big(\Big|\hat{R}_{IPS}(\hat{Y}^{ERM}|\hat{P})-\mathbb{E}_O\Big[\hat{R}_{IPS}(\hat{Y}^{ERM}|\hat{P})\Big]\Big|\le\epsilon\Big)\ge1-\eta\\ \Leftarrow\;&|\mathcal{H}|\cdot2\exp\Bigg(\frac{-2\epsilon^2}{\frac{\Delta^2}{U^2\cdot I^2}\sum_{u,i}\frac{1}{\hat{P}_{u,i}^2}}\Bigg)<\eta. \end{aligned}$

中间过程与定理 4.2 的证明过程类似。调整各项的位置再加上偏差 (bias) 即证。

这个界体现了传统 ERM 中没有的偏差-方差权衡 (bias-variance trade-off)。特别是，如果过高估计较小的倾向降低的变化性 (variability) 要比增加的偏差多的话，这样做是有益的。

5.1 倾向估计模型

一般来说，倾向

$P_{u,i}=P(O_{u,i}=1|X,X^{hid},Y)\tag{17}$

依赖一些可观测到的特征 $X$ （如显示给用户的预测评分），不可观测到的特征 $X^{hid}$ （如是否这个物品是被朋友推荐的），以及评分 $Y$ 。一旦考虑到可观测到的特征，合理假设 $O_{u,i}$ 与新预测 $\hat{Y}$ 相互独立（从而与 $\delta_{u,i}(Y,\hat{Y})$ 相互独立）。

使用朴素贝叶斯的倾向估计 假设协变量 $X$ , $X^{hid}$ 和其他评分之间的依赖关系很小，公式 (17) 可以简化为 $P(O_{u,i}|Y_{u,i})$ 。将 $Y_{u,i}$ 视为已观测到的，由于我们只需要已观测到的项的倾向来计算 IPS 和 SNIPS。因此有朴素贝叶斯 (Naive Bayes) 倾向估计量：

$P(O_{u,i}=1|Y_{u,i}=r)=\frac{P(Y=r|O=1)P(O=1)}{P(Y=r)}.$

可以从 MNAR 数据中已观测到的评分得出 $P(Y=r|O=1)$ 和 $P(O=1)$ 的最大似然估计。然而，要估计 $P(Y=r)$ ，需要 MCAR 数据的小样本。

使用逻辑回归的倾向估计 逻辑回归常用于因果推断，无需 MCAR 数据的样本。对于公式 (17)，目标是找到模型参数 $\phi$ 使得 $O$ 与未观测到的 $X^{hid}$ 和 $Y$ 相互独立，即 $P(O_{u,i}|X,X^{hid},Y)=P(O_{u,i}|X,\phi)$ 。主要的模型假设是存在 $\phi=(w,\beta,\gamma)$ 使得 $P_{u,i}=\sigma(w^TX_{u,i}+\beta_i+\gamma_u)$ ，其中 $X_{u,i}$ 是一个编码了所有关于一个用户-物品对的可观测到的信息（如用户统计信息，物品是否促销等等）的向量， $\sigma(\cdot)$ 是 sigmoid 函数， $\beta_i$ 和 $\gamma_u$ 是各物品和各用户的偏置。

相比于其他的判别式模型，逻辑回归对于倾向预测有一些有吸引力的性质。对于逻辑倾向模型，观察到在 MLE 估计最优时，有下面两个等式成立：

$\begin{aligned} \forall i:&\sum_uO_{u,i}=\sum_uP_{u,i}\\ \forall u:&\sum_iO_{u,i}=\sum_iP_{u,i}. \end{aligned}$

也就是说，逻辑倾向模型能够学习到校准良好 (well-calibrated) 的边缘概率。

证明

sigmoid 函数： $\sigma(x)=\frac{1}{1+e^{-x}}=\frac{e^x}{e^x+1}$

$P_{u,i}=\frac{e^{w^TX_{u,i}+\beta_i+\gamma_u}}{1+e^{w^TX_{u,i}+\beta_i+\gamma_u}}$

即 $O$ 的分布律为

$P(O_{u,i}=k)=\bigg(\frac{e^{w^TX_{u,i}+\beta_i+\gamma_u}}{1+e^{w^TX_{u,i}+\beta_i+\gamma_u}}\bigg)^{k}\bigg(\frac{1}{1+e^{w^TX_{u,i}+\beta_i+\gamma_u}}\bigg)^{1-k},\quad k=0,1.$

故似然函数为

$\begin{aligned} L(\phi)&=\prod_{u,i}\Bigg[\bigg(\frac{e^{w^TX_{u,i}+\beta_i+\gamma_u}}{1+e^{w^TX_{u,i}+\beta_i+\gamma_u}}\bigg)^{k_{u,i}}\bigg(\frac{1}{1+e^{w^TX_{u,i}+\beta_i+\gamma_u}}\bigg)^{1-k_{u,i}}\Bigg]\\ \log L(\phi)&=\sum_{u,i}\bigg[k_{u,i}\Big(w^TX_{u,i}+\beta_i+\gamma_u\Big)-k_{u,i}\log\Big(1+e^{w^TX_{u,i}+\beta_i+\gamma_u}\Big)+(k_{u,i}-1)\log\Big(1+e^{w^TX_{u,i}+\beta_i+\gamma_u}\Big)\bigg]\\ &=\sum_{u,i}\bigg[k_{u,i}\Big(w^TX_{u,i}+\beta_i+\gamma_u\Big)-\log\Big(1+e^{w^TX_{u,i}+\beta_i+\gamma_u}\Big)\bigg]\\ &=\sum_{(u,i):O_{u,i}=1}\Big(w^TX_{u,i}+\beta_i+\gamma_u\Big)-\sum_{u,i}\log\Big(1+e^{w^TX_{u,i}+\beta_i+\gamma_u}\Big) \end{aligned}$

简化后的整个模型的 log 似然函数为：

$\ell(O|X,\phi)=\sum_{(i,u):O_{u,i}=1}[w^TX_{u,i}+\beta_i+\gamma_u]-\sum_{i,u}\log\Big[1+e^{w^TX_{u,i}+\beta_i+\gamma_u}\Big].$

对于任意物品 $i$ 对偏置项 $\beta_i$ 的梯度（ $\gamma_u$ 与之类似）：

$\frac{\partial\ell}{\partial\beta_i}=\sum_uO_{u,i}-\sum_uP_{u,i.}$

令梯度为 0 可解得结论。