python - 如何在 NumPy 计算中避免 Kronecker 积

Question

背景

生成随机权重列表后:

sizes = [784,30,10]
weights = [np.random.randn(y, x) for x, y in zip(sizes[:-1],sizes[1:])]

利用 Numpy 的 Kronecker 产品创建 foo (形状 (900, 23520)):

foo = np.kron(np.identity(30),weights[0])

然后，矩阵乘法 foo来自 data 的切片，即

bar = np.dot(foo,data[0])

由此 data[0].shape是 (23520,)和 data[0].dtype是 float32 .

问题
foo比较浪费。怎么可以 weights[0] ，其形状为 (30,784) , 用于与 data[0] 的乘法以更足智多谋的方式？

更一般地说， data[0]是来自形状为 (1666,23520) 的数组的切片，因此乘法过程将需要执行 1666 次。此外，数据数组接近稀疏，只有不到 20% 的条目为非零。

这是我尝试过的循环:

for i in range(len(data)):
    foo = np.kron(np.identity(30),weights[0])
    bar = np.dot(foo,data[i])

Answer 1

诀窍是 reshape data进入 3D张量然后使用 np.tensordot 反对 weights[0]从而绕过 foo创造，就像这样——

k = 30 # kernel size
data3D = data.reshape(data.shape[0],k,-1)
out = np.tensordot(data3D, weights[0], axes=(2,1)).reshape(-1,k**2)

在引擎盖下， tensordot使用转置轴， reshape 然后 np.dot .因此，使用所有手工劳动来避免对 tensordot 的函数调用，我们会有一个，就像这样——

out = data.reshape(-1,data.shape[1]//k).dot(weights[0].T).reshape(-1,k**2)

Related post to understand tensordot .

sample 运行

让我们使用一个玩具示例来向可能不了解问题的人解释发生了什么:

In [68]: # Toy setup and code run with original codes
    ...: k = 3 # kernel size, which is 30 in the original case
    ...: 
    ...: data = np.random.rand(4,6)
    ...: w0 = np.random.rand(3,2) # this is weights[0]
    ...: foo = np.kron(np.identity(k), w0)
    ...: output_first_row = foo.dot(data[0])

所以，问题是摆脱 foo创建步骤并到达 output_first_row并对 data 的所有行执行此操作.

建议的解决方案是:

...: data3D = data.reshape(data.shape[0],k,-1)
...: vectorized_out = np.tensordot(data3D, w0, axes=(2,1)).reshape(-1,k**2)

让我们验证结果:

In [69]: output_first_row
Out[69]: array([ 0.11,  0.13,  0.34,  0.67,  0.53,  1.51,  0.17,  0.16,  0.44])

In [70]: vectorized_out
Out[70]: 
array([[ 0.11,  0.13,  0.34,  0.67,  0.53,  1.51,  0.17,  0.16,  0.44],
       [ 0.43,  0.23,  0.73,  0.43,  0.38,  1.05,  0.64,  0.49,  1.41],
       [ 0.57,  0.45,  1.3 ,  0.68,  0.51,  1.48,  0.45,  0.28,  0.85],
       [ 0.41,  0.35,  0.98,  0.4 ,  0.24,  0.75,  0.22,  0.28,  0.71]])

所有建议方法的运行时测试 -

In [30]: import numpy as np

In [31]: sizes = [784,30,10]

In [32]: weights = [np.random.rand(y, x) for x, y in zip(sizes[:-1],sizes[1:])]

In [33]: data = np.random.rand(1666,23520)

In [37]: k = 30 # kernel size

# @Paul Panzer's soln
In [38]: %timeit (weights[0] @ data.reshape(-1, 30, 784).swapaxes(1, 2)).swapaxes(1, 2)
1 loops, best of 3: 707 ms per loop

In [39]: %timeit np.tensordot(data.reshape(data.shape[0],k,-1), weights[0], axes=(2,1)).reshape(-1,k**2)
10 loops, best of 3: 114 ms per loop

In [40]: %timeit data.reshape(-1,data.shape[1]//k).dot(weights[0].T).reshape(-1,k**2)
10 loops, best of 3: 118 ms per loop

This Q&A 以及下面的评论，可能有助于理解 tensordot使用 tensors 效果更好.