7

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

假设我有一个数据集，其中运动员参加 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

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

4

4 回答 4

7

您对这是一个矩阵完成问题的敏锐观察使您获得了解决方案的大部分方法。我将你的直觉编码为用户的能力和课程难度的组合产生了比赛的时间，然后介绍了各种算法。

模型

让向量 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

算法一：缺失值奇异值分解

这是经典的赫布算法。它通过梯度下降最小化上述成本函数。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

将这些梯度插入共轭梯度求解器或 BFGS 优化器，如 MATLABfmin_unc或 scipyoptimize.fmin_ncg或 optimize.fmin_bfgs. 除非您愿意实现一个非常好的线搜索算法，否则不要滚动您自己的梯度下降。

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

最近，针对这个问题提出了简单的凸松弛。由此产生的算法编码起来也很简单，而且看起来效果很好。例如，查看非均匀世界中的协作过滤：使用加权跟踪范数学习。这些方法最小化 f(m) = sum_ij (m_ij - y_ij)^2 + ||m||_*，这里||.||_*是矩阵 m 的所谓核范数。实现最终将再次计算关于 u 和 v 的梯度并依赖于非线性优化器。

于 2012-11-25T00:00:22.377 回答
4

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

（像往常一样，作为预处理步骤，尽可能将您的数据标准化为具有 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 算法逐步调整它们。

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

如果您对这个架构很清楚，或者您需要进一步阐述，请告诉我。

于 2012-11-21T19:58:24.650 回答
2

我认为这是丢失数据恢复的经典任务。存在一些不同的方法。我可以建议的其中之一是基于自组织特征图（Kohonen's Map）。

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

基本上，您应该将数据分为两组：第一组 - 具有完全定义的模式，第二组 - 具有部分丢失特征的模式。我认为这是符合条件的，因为稀疏度为 8%，也就是说，您有足够的数据 (92%) 来训练未损坏记录的网络。

然后，您将第一个集合提供给 SOM 并在此数据上对其进行训练。在此过程中，将使用所有功能。我不会在这里复制算法，因为它可以在许多公共资源中找到，甚至一些实现是可用的。

训练网络后，您可以将第二组中的模式输入网络。对于每个模式，网络应仅基于当前模式中存在的那些特征计算最佳匹配单元(BMU)。然后你可以从 BMU 中获取它的权重，对应于缺失的特征。

作为替代方案，您不能将整个数据分成两组，而是在所有模式上训练网络，包括缺少特征的模式。但是对于这样的模式，学习过程应该以类似的方式改变，即 BMU 应该只根据每个模式中的现有特征来计算。

于 2012-11-21T19:24:57.630 回答
1

我想你可以看看最近的低秩矩阵完成方法。假设与矩阵维度相比，您的矩阵的秩较低。

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

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

这个问题的优化有一个宽松的版本，就是：

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

rank(M) 放松到它的凸包 ||M||_* 然后你通过控制参数 lambda 来权衡这两个项。

于 2012-11-25T05:32:36.843 回答