矩阵补全、协变量与信息性缺失(Matrix Completion with Covariate Information and Informative Missingness)

这篇文章最重要的价值，是把信息性缺失 (informative missingness)、协变量 (covariates)、高维 (high-dimensional) 和低秩 (low-rank) 矩阵补全 (matrix completion) 放进了一个统一框架，而且不需要显式指定缺失机制 (missingness mechanism) 的参数模型。

论文信息

• 题目：Matrix Completion with Covariate Information and Informative Missingness
• 作者：Huaqing Jin, Yanyuan Ma, Fei Jiang
• 期刊：Journal of Machine Learning Research
• 年份：2022

1. 解决了什么问题，已有工作到哪里

• 作者研究的是这样一个问题：矩阵条目的缺失不是随机的，而是依赖于条目真实取值本身，也就是缺失非随机 (missing not at random, MNAR)。这时，如果还像传统矩阵补全那样只对观测到的条目建模，会出现明显的选择偏差 (selection bias)。
• 同时，作者还希望利用每个单元的协变量 (covariates) $X_{ij}$。所以目标不是单纯补全矩阵，而是同时完成两件事：一是恢复缺失响应，二是估计协变量效应 (covariate effect)。
• 早期的矩阵补全工作主要关注无噪声 (noiseless) 或理想采样情形，例如 Candès and Recht (2009), Recht (2011)。
• 把噪声 (noise) 加进去以后，代表性工作有 Candès and Plan (2010), Koltchinskii, Lounici and Tsybakov (2011), Rohde and Tsybakov (2011), Negahban and Wainwright (2012)。这些工作重点还是低秩恢复，不处理协变量，也基本不处理响应依赖缺失。
• 非均匀采样 (nonuniform sampling) 或更复杂缺失分布开始被讨论，例如 Srebro and Salakhutdinov (2010), Klopp (2014), Cai and Zhou (2016), Cai, Cai and Zhang (2016), Bi et al. (2016), Mao, Chen and Wong (2019)。
• 协变量被纳入矩阵补全后，相关工作包括 Abernethy et al. (2009), Xu, Jin and Zhou (2013), Chiang, Hsieh and Dhillon (2015), Mao, Wong and Chen (2018), Zhu, Shen and Ye (2016), Robin et al. (2018)。
• 一般统计中的非可忽略缺失 (nonignorable missingness) 也有方法基础，例如 Zhao and Shao (2015), Miao and Tchetgen Tchetgen (2016)。
• 协同过滤 (collaborative filtering) 里也有人讨论 MNAR，例如 Marlin and Zemel (2009), Hernandez-Lobato, Houlsby and Ghahramani (2014), Liang et al. (2016), Hu, Koren and Volinsky (2008), Pan et al. (2008), Steck (2010)。
• 这篇文章的核心定位是：作者认为，最接近的已有工作里，Mao et al. (2019) 仍然需要对缺失机制建模，而 Robin et al. (2018) 虽然能处理高维协变量，但还是在缺失随机 (MAR) 框架里。本文试图同时处理“响应依赖缺失”和“超高维协变量”。

2. 作者提出的模型是什么，参数各代表什么

• 数据对象：
• $Y_{ij}$：第 $i$ 个用户对第 $j$ 个对象的响应或评分。
• $R_{ij}$：$Y_{ij}$ 是否被观测到的缺失指示 (missingness indicator)。
• $X_{ij} \in \mathbb{R}^p$：与单元 $(i,j)$ 对应的协变量向量。
• 作者先用广义线性模型 (generalized linear model, GLM) 写响应分布：

$$Y_{ij} \mid X_{ij} \sim f\bigl(Y_{ij}; \Theta_{0,ij} + \beta_0^\top X_{ij}\bigr).$$

• $\Theta_0$：低秩基线矩阵 (low-rank baseline matrix)，也可以理解成用户和对象之间无法被协变量解释的潜在结构 (latent structure)。它的秩 (rank) 是 $r$。
• $\beta_0$：稀疏系数 (sparse coefficient) 向量，表示协变量如何影响响应。它的稀疏度 (sparsity) 是 $s$。
• $g(X)$：协变量的边缘分布 (marginal distribution)。作者不要求把它写成一个严格的参数模型。
• 关键假设是

$$X_{ij} \perp R_{ij} \mid Y_{ij}.$$

• 原本如果想直接对观测到的响应写似然，那么目标应该是

$$\Pr(Y_{ij}=y_{ij}\mid X_{ij}=x_{ij},R_{ij}=r_{ij}).$$

• 但由贝叶斯公式 (Bayes rule)

$$\Pr(y_{ij}\mid x_{ij},r_{ij}) = \frac{\Pr(r_{ij}\mid y_{ij},x_{ij})\Pr(y_{ij}\mid x_{ij})}{\Pr(r_{ij}\mid x_{ij})} = \frac{\Pr(r_{ij}\mid y_{ij})\Pr(y_{ij}\mid x_{ij})}{\Pr(r_{ij}\mid x_{ij})},$$

• 所以即使加上独立假设，它仍然依赖未知的缺失机制 $\Pr(r_{ij}\mid y_{ij})$，不能直接拿来做最大似然 (maximum likelihood)。

• 于是作者改看反向条件分布 (reverse conditional distribution)

$$\Pr(X_{ij}=x_{ij}\mid Y_{ij}=y_{ij},R_{ij}=r_{ij}).$$

• 同样由贝叶斯公式，

$$\Pr(x_{ij}\mid y_{ij},r_{ij}) = \frac{\Pr(r_{ij}\mid x_{ij},y_{ij})\Pr(x_{ij}\mid y_{ij})}{\Pr(r_{ij}\mid y_{ij})} = \Pr(x_{ij}\mid y_{ij}),$$

• 最后一等号正是由 $X_{ij} \perp R_{ij}\mid Y_{ij}$ 得到的。于是作者把原问题改写成 $X_{ij}\mid Y_{ij}$ 的伪似然 (pseudo-likelihood)：

$$\Pr(X_{ij}=x_{ij}\mid Y_{ij}=y_{ij};\Theta,\beta) = \frac{ f\bigl(y_{ij};\Theta_{ij}+\beta^\top x_{ij}\bigr)g(x_{ij}) }{ \int f\bigl(y_{ij};\Theta_{ij}+\beta^\top x\bigr)g(x)\,dx },$$

从而

$$\ell_{ij}(\Theta,\beta) = R_{ij}\left[ \log f\bigl(y_{ij};\Theta_{ij}+\beta^\top x_{ij}\bigr) - \log \int f\bigl(y_{ij};\Theta_{ij}+\beta^\top x\bigr)g(x)\,dx \right],$$

其中与参数无关的 $\log g(x_{ij})$ 被省略。

Remark
核心不是把似然函数写得更复杂，而是换了方向：$\Pr(Y_{ij}\mid X_{ij},R_{ij})$ 里仍然带着未知缺失机制，所以不能直接做；而 $\Pr(X_{ij}\mid Y_{ij},R_{ij})$ 在条件独立假设下正好化成 $\Pr(X_{ij}\mid Y_{ij})$，于是得到可优化的伪似然。

• 有了上面的负伪似然 (negative pseudo-likelihood) $L(\Theta,\beta)$，作者再加入低秩和稀疏的结构约束，最终得到下面这个带双重正则化 (double regularization) 的优化问题：

$$(\hat\Theta,\hat\beta) = \arg\min_{\|\Theta\|_{\max}\le a,\ \|\beta\|_1\le a} \Bigl\{ L(\Theta,\beta) + \lambda_\Theta \|\Theta\|_* + \lambda \|\beta\|_1 \Bigr\}.$$

• 这里：

• $L(\Theta,\beta)$ 是负伪似然 (negative pseudo-likelihood)。

• $\|\Theta\|_*$ 是核范数 (nuclear norm)，用来逼迫 $\Theta$ 低秩。

• $\|\beta\|_1$ 是 $L_1$ 惩罚 (lasso penalty)，用来逼迫 $\beta$ 稀疏。

• 约束 $\|\Theta\|_{\max}\le a$ 和 $\|\beta\|_1\le a$ 用来控制参数不发散。

• 如果只想抓住一句话，那我会把这篇文章的建模总结成：

作者先用“低秩矩阵 + 稀疏协变量”的 GLM 描述 $Y_{ij}$，再加上 $X_{ij} \perp R_{ij} \mid Y_{ij}$ 这个假设，把原来不能直接用的似然函数改写成伪似然函数，再在这个伪似然上做低秩和稀疏正则化估计。

3. 作者通过什么算法进行求解

• 作者把整体算法叫作 Soft-Impute Proximal Gradient (SIPG)。
• 对 $\beta$ 的更新，用近端梯度 (proximal gradient)：

$$\beta_t = \mathcal{S}_{\eta\lambda} \Bigl( \beta_{t-1} - \eta \nabla_\beta L(\Theta_{t-1}, \beta_{t-1}) \Bigr),$$

其中 $\mathcal{S}$ 是逐坐标软阈值 (soft-thresholding) 算子。

• 对 $\Theta$ 的更新，用 Soft-Impute，也就是奇异值软阈值化 (singular value soft-thresholding)。如果

$$\Theta_{t-1} - \eta_1 \nabla_\Theta L(\Theta_{t-1}, \beta_t) = U D V^\top,$$

那么

$$\Theta_t = U \, \mathrm{Soft}_{\eta_1\lambda_\Theta}(D) \, V^\top.$$

• 所以算法结构非常清楚：$\beta$ 这一块按高维稀疏回归的套路做，$\Theta$ 这一块按低秩矩阵恢复的套路做。
• 伪似然里有积分项 (integration term)。作者建议把积分看成对 $X$ 分布的均值，再用样本平均 (sample average) 或 Monte Carlo 近似。
• 在 Yelp 实验里，作者就是用经验分布 (empirical distribution) 来近似 $X$ 的分布，并在迭代过程中重估 $\beta^\top X$ 的经验分布。

4. 作者有哪些理论结果

• 这篇文章的理论主线是有限样本误差界 (finite-sample error bound) 和一致性 (consistency)，不是渐近正态性 (asymptotic normality)。
• Theorem 1 给出 $\hat\beta$ 的误差上界，也就是 $\|\hat\beta-\beta_0\|_2$ 的上界。
• 文中明确说明：如果 $s$ 和与缺失相关的关键量保持可控，同时 $\log p = o(mn)$，并且若干技术量如 $d_W, d_{EX}$ 的增长速度慢于 $mn$，那么 Theorem 1 的上界会趋于 0，因此 $\hat\beta$ 是一致的。
• Theorem 2 给出 $\hat\Theta$ 的误差上界，也就是 $\|\hat\Theta-\Theta_0\|_F$ 的上界。
• 作者进一步指出：当 $\Theta_0$ 的秩有限，而且 $d \log d /(mn) \to 0$ 时，$\|\hat\Theta-\Theta_0\|_F$ 的上界是

$$O_p\Bigl(\bigl(d \log d /(mn)\bigr)^{1/4}\Bigr),$$

所以 $\hat\Theta$ 也是一致的。

• 理论上最关键的技术点，是在稀疏集 (sparse set) 和低秩集 (low-rank set) 上建立受限特征值条件 (restricted eigenvalue condition)。文中对应的关键引理是 Lemmas A.10 和 A.19。
• Theorem 3 处理的是算法收敛 (algorithmic convergence)，说明 SIPG 在满足文中凸性和光滑性条件时，会以高概率收敛到原优化问题的 $\epsilon$-最优解 ($\epsilon$-optimal solution)。
• 更具体地说，Theorem 3 给出：当迭代次数足够大时，$F(\Theta_T,\beta_T)-F(\hat\Theta,\hat\beta)\le \epsilon$，且概率至少为 $1-6(mn+p)^{-1}$。
• 附录里的 Theorem A.1 还单独证明了一个有限维 (finite-dimensional) 伪似然估计量的一致性，算是给主方法提供了额外直觉基础。
• 结论非常明确：这篇文章主打的是一致性和优化收敛，没有给出渐近正态性，也没有做置信区间 (confidence interval) 或显著性检验 (inference)。

5. 用在什么 real data 上，结果如何

Yelp 数据

• 原始 Yelp 数据非常大，包含 8,635,403 条评论和 160,585 家商户。
• 作者实际分析时选了 Las Vegas 里评分数最多的 500 家餐厅，再选了对这 500 家餐厅评分最多的 1000 个用户。
• 最终矩阵规模是 $1000 \times 500$，缺失率 (missing rate) 为 90.9%。
• 每个单元有 $p=22$ 个协变量，包括餐厅星级、开业日期、用户评论数等。
• 作者把响应二值化 (dichotomize)：评分大于 3.5 记为 1，否则记为 0。
• 评估时，作者额外人为制造一层 MNAR 缺失，再比较 20 次重复实验中的 AUC。
• 比较对象包括：
• MNAR：本文方法。
• MAR：把缺失当作缺失随机来做。
• EM：用期望最大化 (EM) 方式迭代填补。
• MIMI：Robin et al. (2020) 的方法。
• 结果：MNAR 在所有设置下都拿到最高 AUC，明显优于 MAR、EM 和 MIMI。

MovieLens 1M 数据

• 数据包含约 100 万条评分，6040 个用户，3952 部电影。
• 作者把用户年龄组 (age group) 和电影类型 (genre) 组合成协变量，维度是 $p=7\times 302=2114$。
• 整体缺失率超过 95.7%。
• 这里作者主要和加权协同过滤 (weighted collaborative filtering, WCF) 比较，具体是 Hu, Koren and Volinsky (2008) 的方法。
• 评价指标不是 AUC，而是期望百分位排序 (expected percentile ranking)。这个指标越小越好。
• 结果：MNAR 的期望百分位排序显著小于 WCF，说明排序效果更好。
• 另外，WCF 对因子数 (number of factors) 很敏感；在 MovieLens 上，作者报告的最优因子数是 16。

Yelp 上再和 WCF 比较

• 作者还把 WCF 放到 Yelp 子样本上比较。
• 结果仍然是 MNAR 的期望百分位排序更小，表现更好。
• 在这个 Yelp 子样本上，WCF 的最优因子数是 4。

我会怎么记这篇文章

• 最有启发的一点，是作者没有去硬建模 $R_{ij} \mid Y_{ij}, X_{ij}$，而是转去建模 $X_{ij} \mid Y_{ij}$，用伪似然把 MNAR 带来的偏差问题绕开了。
• 第二个要点是参数分解 (decomposition) 很自然：低秩矩阵 $\Theta$ 管潜在交互，稀疏向量 $\beta$ 管可解释协变量。
• 第三个要点是理论目标很克制：作者要的是高维一致性和算法收敛，不做渐近正态推断。
• 局限也很明显：条件独立假设 $X_{ij} \perp R_{ij}\mid Y_{ij}$ 不一定总成立，而且文中的可识别性也比较依赖协变量矩阵本身足够稀疏。

重点参考文献

• Candès, E. J., and Recht, B. (2009). Exact Matrix Completion via Convex Optimization. 低秩矩阵补全的经典起点。
• Candès, E. J., and Plan, Y. (2010). Matrix Completion with Noise. 把噪声引入矩阵补全分析。
• Negahban, S., and Wainwright, M. J. (2012). Restricted Strong Convexity and Weighted Matrix Completion. 受限强凸性 (restricted strong convexity) 和加权矩阵补全的重要参考。
• Mao, X., Chen, S. X., and Wong, R. K. W. (2019). Matrix Completion with Covariate Information. 与本文最接近，但仍需要更明确的缺失机制处理。
• Robin, G., Wai, H.-T., Josse, J., Klopp, O., and Moulines, E. (2018). Low-rank Interaction with Sparse Additive Effects Model for Large Data Frames. 高维协变量加低秩结构的重要背景文献。
• Zhao, J., and Shao, J. (2015). Semiparametric Pseudo-likelihoods in Generalized Linear Models with Nonignorable Missing Data. 本文伪似然思路的重要统计背景。
• Hu, Y., Koren, Y., and Volinsky, C. (2008). Collaborative Filtering for Implicit Feedback Datasets. 文中 real data 比较的 WCF 基准方法。
• Marlin, B. M., and Zemel, R. S. (2009). Collaborative Prediction and Ranking with Non-random Missing Data. 协同过滤里处理非随机缺失的代表工作。