协同过滤
传统推荐系统采用内容过滤，即使用产品和用户已有的信息做推荐，需要维护两方的档案（profile）。例如，产品侧需要维护电影信息、价格信息、产品描述等等。用户侧需要维护画像、问卷信息等。这些信息可能难以采集
协同过滤的思想是，使用用户之前的输入/行为来对未来进行推荐，这里不使用用户的先验信息。其核心是使用相同用户的评分来预测某一个用户的评分，而不需要知道被打分的是什么、谁打的分、打了多少分。一种典型的协同过滤方法是给予邻居的方法，即定义一种评估用户相似性的方法，然后根据用户之间相似性的分数，让其它用户替某个具体用户做选择。两种过滤方法并非对立，可以相辅相成
矩阵分解
假设评分矩阵\(M\)是一个\(N_1 \times N_2\)的矩阵，其中\(N_1\)是用户数量，\(N_2\)是物品数量，\(M_{ij}\)是用户\(i\)对物品\(j\)的评分。可以预见到\(M\)必然是一个极稀疏的矩阵，因为大部分用户都只能对很小一部分物品打分。推荐系统的目的就是要将其它缺失值预测出来。使用的方法是奇异值分解，即每个矩阵\(M\)都可以分解为\(M=USV^\mathsf{T}\)，其中\(U^\mathsf{T}U=I\)，\(V^\mathsf{T}V=I\)，\(S\)是对角矩阵，所有\(S_{ii} \ge 0\)。如果\(M\)是\(n \times d\)矩阵，则\(U\)为\(n\times r\)的，\(V^\mathsf{T}\)为\(r \times d\)的。其中\(r = {\rm rank}(M)\)
从另一个角度看，如果\(N_1 \times N_2\)矩阵\(M\)可以分解成\(N_1 \times d\)矩阵\(U\)与\(d \times N_2\)矩阵\(V\)的乘积，\(U\)中的每一行可以看做是用户\(u_i\)的\(d\)个特征，\(V\)中的每一列也可以看作是物品\(v_j\)的\(d\)个特征，两者内积就是原始矩阵中\(M_{ij}\)的值。
令集合\(\Omega\)包含了所有有观测值的行列对\((i,j)\)，也就是 \[ \Omega = \{(i,j): M_{ij} {\rm\ is\ measured}\} \] 即如果用户\(i\)给物品\(j\)打过分，那么\((i,j) \in \Omega\)。令\(\Omega_{u_i}\)是用户\(i\)打过分的物品，\(\Omega_{v_j}\)是给物品\(j\)打过分的用户
假设用户的location满足\(u_i \sim N(0, \lambda^{-1}I)\)，物品的location满足\(v_j \sim N(0, \lambda^{-1}I)\)，则整个数据的分布满足\(M_{ij} \sim N(u_i^\mathsf{T}v_j, \sigma^2)\)。注意由于\(M_{ij}\)是评分，每个值都基本是个离散值，因此其实不适合使用正态分布建模。但是如果采用这个假设，算法会比较容易实现而且最终模型也很可用
令\(M_o\)是\(M\)中观测到的部分，\(M_m\)是缺失的部分，则 \[ p(M_o | U,V) = \int p(M_o, M_m|U,V)dM_m \] 又 \[ p(M_o, U, V) = {\left[\prod_{(i,j)\in \Omega} p(M_{ij}|u_i, v_j)\right]} \times \left[\prod_{i=1}^{N_1} p(u_i)\right]\left[\prod_{j=1}^{N_2} p(v_j)\right] \] 因此有 \[ U_{\rm MAP}, V_{\rm MAP} = {\rm arg}\max_{U,V} \sum_{(i,j)\in \Omega} \ln p(M_{ij}|u_i, v_j) + \sum_{i=1}^{N_1} \ln p(u_i) + \sum_{j=1}^{N_2} \ln p(v_j) \]
所以MAP目标函数为 \[ \mathcal{L} = -\sum_{(i,j) \in \Omega} \frac{1}{2\sigma^2}|\!|M_{ij} - u_i^\mathsf{T}v_j|\!|^2 - \sum_{i=1}^{N_1}\frac{\lambda}{2}|\!|u_i|\!|^2 - \sum_{j=1}^{N_2}\frac{\lambda}{2}|\!|v_j|\!|^2 + C \] 求导得 \[ \begin{align*} \nabla_{u_i}\mathcal{L} &= \sum_{j \in \Omega_{u_i}} \frac{1}{\sigma^2} (M_{ij} - u_i^\mathsf{T}v_j)v_j - \lambda u_i = 0 \\ \nabla_{v_j}\mathcal{L} &= \sum_{i \in \Omega_{v_j}} \frac{1}{\sigma^2} (M_{ij} - v_j^\mathsf{T}u_i)u_i - \lambda v_i = 0 \end{align*} \] 可以解得 \[ \begin{align*} u_i &= \left(\lambda \sigma^2 I + \sum_{j \in \Omega_{u_i}} v_jv_j^\mathsf{T} \right)^{-1}\left(\sum_{j \in \Omega_{u_i}} M_{ij}v_j \right) \\ v_j &= \left(\lambda \sigma^2 I + \sum_{i \in \Omega_{v_j}} u_iu_i^\mathsf{T} \right)^{-1}\left(\sum_{i \in \Omega_{v_j}} M_{ij}u_i \right) \end{align*} \]
这里也不能对所有\(u_i\)和\(v_j\)同时求解，所以可以使用类似Kmean或者GMM的方法来做坐标下降
概率矩阵分解算法 输入：一个不完全的评分矩阵\(M\)，其中在\(\Omega\)中的下标有值，以及秩\(d\) 输出：\(N_1\)个用户location \(u_i \in \mathbb{R}^d\)，\(N_2\)个物品location \(v_j \in \mathbb{R}^d\) 初始化每个\(v_j\)，对每个迭代， - 对\(i\)从1到\(N_1\)，更新user location \[ u_i = \left(\lambda \sigma^2 I + \sum_{j \in \Omega_{u_i}} v_jv_j^\mathsf{T} \right)^{-1}\left(\sum_{j \in \Omega_{u_i}} M_{ij}v_j \right) \] - 对\(j\)从1到\(N_2\)，更新object location \[ v_j = \left(\lambda \sigma^2 I + \sum_{i \in \Omega_{v_j}} u_iu_i^\mathsf{T} \right)^{-1}\left(\sum_{i \in \Omega_{v_j}} M_{ij}u_i \right) \] 预测方法：用户\(i\)对物品\(j\)的打分是\(u_i^\mathsf{T}v_j\)的四舍五入
单独把每个\(v_j\)拿出来，对所有user location构成的矩阵\(U\)，实际上是最小化带有惩罚项\(\lambda |\!|v_j|\!|^2\)的均方误差\(\frac{1}{\sigma^2}(M_{ij} - u_i^\mathsf{T}v_j)^2\)，可以看做是对\(v_j\)做岭回归。整个问题也是\(N_1+N_2\)个岭回归问题交织起来的问题。如果去掉\(u_i\)和\(v_j\)的先验分布，问题退化成最小二乘问题，但是要求解\(\left(\sum_{i\in \Omega_{v_j}}u_iu_i^\mathsf{T}\right)^{-1}\)需要保证每个用户都对至少d个物品打分，每个物品至少有d个用户打过分，那个矩阵才有逆。但是这种假设在实际中很难成立，因此先验概率是必要的
