python - 在python numpy中是否有更快的方法来有效地执行此伪代码？

Question

我有三个名为 RowIndex 的数组, ColIndex和 Entry在 NumPy 。本质上，这是矩阵中条目的子集，分别具有这三个变量中该条目的行索引、列索引和值。我有两个 numpy 二维数组(矩阵)U和 M .让 alpha和 beta是两个给定的常数。我需要遍历矩阵的条目子集，如果我遍历 RowIndex，这是可能的。 , ColIndex和 Value .说，

i=RowIndex[0], j=ColIndex[0], value = Entry[0] 

那么我需要更新 i '第行和j '第 U 列和 M分别根据某个方程。然后，我使

i=RowIndex[1], j=ColIndex[1], value = Entry[1]

等等。详情如下。

for iter in np.arange(length(RowIndex)):
    i = RowIndex[iter]
    j = ColIndex[iter]
    value = Entry[iter]
    e = value - np.dot(U[i,:],M[:,j])
    OldUi = U[i,:]
    OldMj = M[:,j]
    U[i,:] = OldUi + beta * (e*OldMj - alpha*OldUi)
    M[:,j] = OldMj + beta * (e*OldUi - alpha*OldMj)

问题是代码非常慢。是否有任何代码部分可以加快速度？

PS:对于好奇的人，这是著名的 NetFlix 百万奖金问题的有奖解决方案的变体。 RowIndex 对应于用户，ColIndex 对应于电影，值对应于他们的评分。大部分评分都不见了。已知的评级被堆积在 RowIndex、ColIndex 和 Entry 中。现在您尝试找到矩阵 U 和 M，使得 i 的评级'第 j 的用户'th 电影由 np.dot(U[i,:],M[:,j]) 提供.现在，基于可用的评级，您尝试使用如上代码所示的更新方程来查找矩阵 U 和 M(或它们的行和列)。

Answer 1

我想如果我没有理解错，你的代码可以被向量化如下:

import numpy as np

U, M = # two 2D matrices
rows_idx = # list of indexes
cols_idx = # list of indexes
values   = # np.array() of values

e = values - np.dot(U[rows_idx, :], M[:, cols_idx]).diagonal()
Uo = U.copy()
Mo = M.copy()
U[rows_idx, :] += beta * ((e * Mo[:, cols_idx]).T - alpha * Uo[rows_idx, :])
M[:, cols_idx] += beta * ((e * Uo[rows_idx, :].T) - alpha * Mo[:, cols_idx])

这里，

e = values - np.dot(U[rows_idx, :], M[:, cols_idx]).diagonal()

计算你的

e = value - np.dot(U[i,:],M[:,j])

请注意，您想要的结果位于矩阵之间点积的对角线上。

这不会处理顺序更新(因为没有可用的矢量化)，但它允许您以矢量化和更快的方式执行一批独立更新。

如上所述，我向您提出的代码不能处理顺序更新，因为根据定义，顺序更新方案不能矢量化。任何形式

A(t) = A(t-1) +/* something

哪里t定义时间，不能并行更新。

所以，我提出的是 的矢量化更新独立 更新。

假设您有 M和 U与 10x10每行，并且您有以下行和列索引:

rows_idx = [1, 1, 3, 4, 5, 0]
cols_idx = [7, 1, 7, 5, 6, 5]

您可以从中识别出两个独立的集合(考虑到索引是有序的):

rows_idx = [1, 4, 5], [1, 3, 0]
cols_idx = [7, 5, 6], [1, 7, 5]

请注意，独立集由唯一的行和列中的索引构成。使用该定义，您可以将所需的循环数从 6(在本例中)减少到 2:

for i in len(rows_idx):
    ridx = rows_idx[i]
    cidx = cols_idx[i]
    # Use the vectorized scheme proposed above the edit
    e = values - np.dot(U[ridx, :], M[:, cidx]).diagonal()
    Uo = U.copy()
    Mo = M.copy()
    U[ridx, :] += beta * ((e * Mo[:, cidx]).T - alpha * Uo[ridx, :])
    M[:, cidx] += beta * ((e * Uo[ridx, :].T) - alpha * Mo[:, cidx])

因此，如果您有一种手动(或轻松)提取独立更新的方法，或者您通过使用搜索算法计算列表，则上述代码会将 向量化。独立更新 .

为了以防万一，在上面的例子中:

rows_idx = [1, 1, 3, 4, 5, 0]
cols_idx = [7, 1, 7, 5, 6, 5]

第二行无法并行，因为 1之前出现过，由于相同的原因(使用 7 和 5 )，第三列和最后一列无法并行化。因此，由于行和列都需要是唯一的，我们最终得到 2 组元组:

rows_idx = [1, 4, 5], [1, 3, 0]
cols_idx = [7, 5, 6], [1, 7, 5]

从这里开始，要走的路将取决于您的数据。寻找独立集的问题可能非常昂贵，特别是如果它们中的大多数都依赖于某些先前的更新。

如果您有办法从您的数据中(假设您按时记录数据)提取独立集，那么批量更新将对您有所帮助。另一方面，如果您将所有数据放在一起(这是常见的)，它将取决于一个因素:

如果可以保证独立集的长度N远远大于独立集的数量M (这或多或少意味着，如果您的 M = {2,3,4} 行/列索引最终会得到几个 N = 100000, with N >> M 独立集)，那么可能值得寻找独立集。

换句话说，如果您要以 10000 种不同的组合更新 30 个作者和 30 部电影，那么您的数据很可能依赖于以前的更新，但是，如果您要以 30 种组合更新 100000 个作者和 100000 部电影，那么你的数据很可能是独立的。

一些用于查找独立集的伪代码，如果您没有办法在没有信息的情况下提取它们，将是这样的:

independent_sets = [] # list with sets

for row, col in zip(rows_idx, cols_idx):
    for iset in independent_sets:
        if row and col DONT exist in iset:
            insert row and col
            break
    if nothing inserted:
        add new set to independent set
        add current (row, col) to the new set

如您所见，为了找到独立的集合，您已经需要遍历整个行/列索引列表。上面的伪代码不是最有效的，我很确定会有特定的算法。但是，如果您的更新可能依赖于先前的更新，则查找独立集的成本可能高于执行所有顺序更新。

完成:在整个帖子之后，它完全取决于您的数据。

如果您可以事先从获取要更新的行/列的方式提取独立集，那么您可以轻松地将它们更新为矢量化。

如果您可以确保您的大部分更新都是独立的(例如，990 中的 10000 将是)，那么尝试查找 990 可能是值得的。放。近似集合的一种方法是使用 np.unique :

# Just get the index of the unique rows and columns
_, idx_rows = np.unique(rows_idx, return_index=True) 
_, idx_cols = np.unique(cols_idx, return_index=True)

# Get the index where both rows and columns are unique
idx = np.intersection1d(idx_rows, idx_cols)

现在 idx包含rows_idx 和cols_idx 的位置unique ，希望这可以大大减少您的计算成本。您可以使用我的批量更新来快速更新与这些索引对应的行和列。然后，您可以使用最初的方法来更新在非唯一索引上重复迭代的少数条目。

如果您对相同的 Actor 或电影有多个更新，那么...保持您的顺序更新方案，因为找到独立集将比迭代更新更难。