使用矩阵运算的分解机器的有效实现？

Question

链接在此处：https://www.csie.ntu.edu.tw/~r01922136/slides/ffm.pdf (幻灯片5-6)

给定以下矩阵：

X : n * d 
W : d * k

是否有一种仅使用矩阵运算来计算n x 1矩阵的有效方法(例如，numpy、tensorflow)，其中第j个元素是：

​

​

编辑:当前的尝试是这样的，但显然它的空间效率不是很高，因为它需要存储n*d*d大小的矩阵：

n = 1000
d = 256
k = 32

x = np.random.normal(size=[n,d])
w = np.random.normal(size=[d,k])

xxt = np.matmul(x.reshape([n,d,1]),x.reshape([n,1,d]))
wwt = np.matmul(w.reshape([1,d,k]),w.reshape([1,k,d]))
output = xxt*wwt
output = np.sum(output,(1,2))

Answer 1

避免大型临时数组

并不是所有类型的算法都那么容易或明显地向量化。可以使用np.einsum重写np.sum(xxt*wwt)。这应该比您的解决方案更快，但有一些其他限制(例如，没有多线程)。

因此，我建议使用像Numba这样的编译器。

示例

import numpy as np
import numba as nb
import time

@nb.njit(fastmath=True,parallel=True)
def factorization_nb(w,x):
  n = x.shape[0]
  d = x.shape[1]
  k = w.shape[1]
  
  output=np.empty(n,dtype=w.dtype)
  wwt=np.dot(w.reshape((d,k)),w.reshape((k,d)))
  
  for i in nb.prange(n):
    sum=0.
    for j in range(d):
      for jj in range(d):
        sum+=x[i,j]*x[i,jj]*wwt[j,jj]
    output[i]=sum
  return output

def factorization_orig(w,x):
  n = x.shape[0]
  d = x.shape[1]
  k = w.shape[1]
  
  xxt = np.matmul(x.reshape([n,d,1]),x.reshape([n,1,d]))
  wwt = np.matmul(w.reshape([1,d,k]),w.reshape([1,k,d]))
  output = xxt*wwt
  output = np.sum(output,(1,2))
  
  return output

测量性能

n = 1000
d = 256
k = 32

x = np.random.normal(size=[n,d])
w = np.random.normal(size=[d,k])

#first call has some compilation overhead
res_1=factorization_nb(w,x)
t1=time.time()
for i in range(100):
  res_1=factorization_nb(w,x)
  #res_2=factorization_orig(w,x)

print(time.time()-t1)

计时

factorization_nb: 4.2 ms per iteration
factorization_orig: 460 ms per iteration (110x speedup)