机器学习算法用于补全稀疏矩阵数据

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的优势。

您是否可以给我一些提示我可以使用哪些方法？

- user1141785

---

在这个例子中，每个人都参加了一次比赛。这种情况总是发生吗？ - Patricia Shanahan

请使用合理的问题标题！ - Has QUIT--Anony-Mousse

你能澄清一下你的说法吗？完成时间是反向正态分布吗？你的意思是1/时间服从高斯分布吗？ - moos

我尝试使用MATLAB将我的数据拟合到几个分布中。我发现逆高斯分布的拟合效果最佳：http://en.wikipedia.org/wiki/Inverse_Gaussian_distribution - user1141785

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相对于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或optimize.fmin_bfgs。除非你愿意实现一个非常好的线搜索算法，否则不要自己编写梯度下降算法。

算法2：矩阵分解与迹范数惩罚

最近，对这个问题提出了简单的凸松弛方法。由此得到的算法编码同样简单，似乎效果非常好。例如，请查看非均匀世界中的协作过滤：学习加权迹范数。这些方法最小化 f(m) = sum_ij (m_ij - y_ij)^2 + ||m||_*， 其中||.||_*是矩阵m的所谓核范数。实现最终会再次计算相对于u和v的梯度，并依赖于非线性优化器。

- moos

Answer 2

有几种方法可以实现这一点，也许首先尝试的最佳架构如下：

（通常情况下，作为预处理步骤，将数据归一化为具有0均值和1标准偏差的统一函数。您可以通过将函数拟合于所有比赛结果的分布并应用其逆来实现这一点，然后减去平均值并除以标准偏差。）

选择一个超参数N（您可以像往常一样使用交叉验证集进行调整）。

对于每个参与者和每场比赛，创建一个N维特征向量，初始随机。因此，如果有R场比赛和P个参与者，则一共有R+P个特征向量，总共有N(R+P)个参数。

给定参与者和给定比赛的预测是两个相应特征向量的函数（作为第一次尝试，使用这两个向量的数量积）。

在逐步改进参与者特征向量和比赛特征向量之间交替。

要改进特征向量，请在已知数据元素上使用梯度下降（或某些更复杂的优化方法）（即已知有结果的参与者/比赛对）。

这就是您的损失函数：

total_error = 0

forall i,j
    if (Participant i participated in Race j)
        actual = ActualRaceResult(i,j)
        predicted = ScalarProduct(ParticipantFeatures_i, RaceFeatures_j)
        total_error += (actual - predicted)^2

因此，计算这个函数相对于特征向量的偏导数，并根据通常的ML算法逐步调整它们。

（您还应该在损失函数上包括正则化项，例如特征向量长度的平方）

如果您需要进一步解释，请告诉我，否则请确认是否清楚了这种架构。

- Andrew Tomazos

---

谢谢。我明白了。还有一个问题：我已经尝试了乘法模型（如您所说的标量积）作为第一次尝试。它确实效果很好。 那么，如何构建/寻找比标量积更复杂和更好的模型呢？ - user1141785

我猜这种方法对于K>1来说完全是过拟合的。当K=1时，您保留了用户相关性非常高的属性。原因：如果用户1的参数= 1.03 * 用户2，则用户2在每次比赛中都会比用户1好3％（仅适用于K=1）。缺点：模型的复杂性和学习能力太低。 - user1141785

你说的K是指N吗？你在使用正则化吗？ - Andrew Tomazos

你是否对数据进行了归一化？如果K等于N，那么当N=1时，单一的赛事特征将成为总体赛事难度，而单一的参与者特征将成为总体参与者能力。然后将它们相乘以得出预测结果，这是有意义的。你是如何确定N=2会过拟合的呢？ - Andrew Tomazos

现在我想想，1000x20和8%的意思是20行平均有1.8个正确的条目，对吗？如果是这样的话，可能没有足够的数据来适应更复杂的模型。尽管如此，我仍然期望N=2在正则化方面比N=1表现更好。 - Andrew Tomazos

1. 对不起，我在尝试N>1的方法时没有对数据进行标准化。我会尝试一下。
2. 你说得对，平均每个人有1.8条目。我认为仍然可能有一种方法可以奏效，因为我有100个用户几乎拥有相同的能力 - 可能有一种方法可以将所有具有相同能力的用户的信息“合并”起来。

- user1141785

Answer 3

我认为这是一个经典的缺失数据恢复任务。有一些不同的方法。其中我可以建议的一个方法是基于自组织特征映射（Kohonen的映射）。

下面假设每个运动员记录是一个“模式”，每个比赛数据是一个“特征”。

基本上，你应该将你的数据分成两组：第一组是完全定义的模式，第二组是部分丢失特征的模式。我认为这是合适的，因为稀疏度为8%，也就是说你有足够的数据（92%）来训练网络在未受损的记录上。

然后，将第一组输入到SOM中，并在此数据上进行训练。在此过程中，所有特征都被使用。我不会在这里复制算法，因为它可以在许多公共来源中找到，甚至有一些实现可用。

训练完成后，你可以将第二组模式输入到网络中。对于每个模式，网络应该根据当前模式中存在的特征计算出最佳匹配单元（BMU）。然后，你可以从BMU中取出相应缺失特征的权重。

作为替代方案，您可以不将整个数据分成两组，而是对包括具有缺失特征的模式在内的所有模式进行网络训练。但是，对于这样的模式，学习过程应该以类似的方式进行修改，即在每个模式中仅计算存在的特征上的BMU。

- Stan

Answer 4

我认为你可以考虑最近的低秩矩阵完成方法。 假设是您的矩阵与矩阵维数相比是低秩的。

min rank(M)
s.t. ||P(M-M')||_F=0

M是最终结果，而M'是您当前拥有的未完成矩阵。 该算法将最小化矩阵M的秩。约束中的P是一个运算符，它将矩阵M'中已知的项，并将这些项约束为与M中相同。

此问题的优化有一个放松版本，即：

min ||M||_* + \lambda*||P(M-M')||_F

rank(M)被放松到其凸包||M||_*。然后通过控制参数lambda来权衡这两个术语。

- Min Lin