用于完成稀疏矩阵数据的机器学习算法

Question

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

假设我有一个数据集,运动员参加10公里和20公里的丘陵比赛的比赛,即每场比赛都有自己的困难.

用户的完成时间几乎与每次比赛的正常分布相反.

可以将此问题写为矩阵:

       Comp1 Comp2 Comp3
User1  20min  ??   10min

User2  25min 20min 12min

User3  30min 25min ??

User4  30min ??    ??

我想完成上面的矩阵,其大小为1000x20,稀疏度为8%(!).

应该有一种非常简单的方法来完成这个矩阵,因为我可以计算每个用户(能力)的参数和每个竞争的参数(mu,lambda of distribution).此外,比赛之间的相关性非常高.

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

你能不能给我一个暗示我可以使用的方法？

Answer 1

您精确地观察到这是一个矩阵完成问题,可以让您获得解决方案的大部分内容.我将把你的直觉编成一个直觉,即用户的能力和课程难度的结合会产生比赛的时间,然后呈现各种算法.

模型

让向量u表示用户的速度,以便u_i是用户i的速度.让向量v表示课程的难度,以便v_j是课程j的难度.同样可用时,让t_ij成为用户i在课程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:缺失值奇异值分解

这是经典的Hebbian算法.它通过梯度下降最小化上述成本函数.f wrt到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

将这些渐变插入Conjugate Gradient解算器或BFGS优化器,如MATLAB fmin_unc或scipy optimize.fmin_ncg或 optimize.fmin_bfgs.除非您愿意实施非常好的线搜索算法,否则不要滚动自己的梯度下降.

算法2:具有跟踪范数惩罚的矩阵分解

最近,已经提出了针对该问题的简单凸松弛.生成的算法就像编码一样简单,似乎工作得很好.退房,例如非统一世界中的协作过滤:使用加权跟踪规范学习.这些方法最小化f(m)= sum_ij(m_ij - y_ij)^ 2 + || m || _*,其中||.||_*是矩阵m的所谓核范数.实现将最终再次计算关于u和v的梯度并依赖于非线性优化器.