algorithm - 补全稀疏矩阵数据的机器学习算法

Question

我在这里看到了一些机器学习问题，所以我想我会发布一个相关问题:

假设我有一个数据集，其中运动员参加了 10 公里和 20 公里的丘陵跑道比赛，即每场比赛都有自己的难度。

对于每场比赛，用户的完成时间几乎呈正态分布。

可以将这个问题写成矩阵:

       Comp1 Comp2 Comp3
User1  20min  ??   10min

User2  25min 20min 12min

User3  30min 25min ??

User4  30min ??    ??

我想完成上面的矩阵，它的大小为 1000x20，稀疏度为 8% (!)。

应该有一种非常简单的方法来完成这个矩阵，因为我可以计算每个用户(能力)的参数和每个比赛的参数(mu，分布的 lambda)。而且比赛之间的相关性非常高。

我可以利用排名 User1 < User2 < User3 和 Item3 << Item2 < Item1

你能不能给我一些提示，我可以使用哪些方法？

Answer 1

你敏锐地观察到这是一个矩阵补全问题你大部分的解决方案。我会整理你的直觉用户能力与类(class)难度的结合得出比赛时间，然后给出各种算法。

型号

让向量 u 表示用户的速度，这样 u_i 就是用户 i 的速度。让向量 v 表示类(class)的难度v_j 是类(class) j 的难度。同样在可用时，让 t_ij 成为用户 i's time on路线j，定义y_ij = 1/t_ij，用户i在路线j上的速度。

既然你说时间是逆高斯分布的，一个明智的观察模型是

y_ij = u_i * v_j + e_ij,

其中 e_ij 是零均值高斯随机变量。

为了适应这个模型，我们搜索向量 u 和 v 来最小化观察到的速度之间的预测误差:

f(u,v) = sum_ij (u_i * v_j - y_ij)^2

算法1:缺失值奇异值分解

这是经典Hebbianalgorithm .它通过梯度下降最小化上述成本函数。的梯度f wrt to u 和 v 是

df/du_i = sum_j (u_i * v_j - y_ij) v_j
df/dv_j = sum_i (u_i * v_j - y_ij) u_i

将这些梯度插入共轭梯度求解器或 BFGS优化器，例如 MATLAB 的 fmin_unc 或 scipy 的 optimize.fmin_ncg 或优化.fmin_bfgs。除非你愿意实现一个非常好的线搜索算法，否则不要推出你自己的梯度下降。

算法 2:带迹范数惩罚的矩阵分解

最近，针对这个问题的简单凸松弛建议的。生成的算法编写起来同样简单，而且看起来工作得很好。 checkout ，例如 Collaborative Filtering in a Non-Uniform World:Learning with the Weighted Trace Norm .这些方法最小化 f(m) = sum_ij (m_ij - y_ij)^2 + ||m||_*,其中 ||.||_* 是矩阵 m 的所谓核范数。实现将再次计算关于 u 和 v 的梯度并依赖于非线性优化器。