numpy - Einsum 计算 c 距离的速度非常慢

Question

我正在通过 np.einsum 计算马氏距离：

np.einsum('nj,jk,nk->n', delta, VI, delta)

其中，协方差矩阵的逆矩阵 VI 是 ，783 x 783而 delta 是6000 x 783。这条线在我的 2016 Macbook Pro 上执行需要 10 秒。我怎样才能让它更快？

我必须将这条线计算 200k 到 300k 次。矢量化可能不是一个选项，因为每个类的 VI 都不同。

Answer 1

不需要 Einsum，您可以使用点积和元素积，以及总和：

VI = np.random.rand(783, 783)
delta = np.random.rand(6000, 783)

%timeit np.einsum('nj,jk,nk->n', delta, VI, delta)
# 7.05 s ± 89.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit np.sum((delta @ VI) * delta, axis=-1)
# 90 ms ± 4.72 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

out_1 = np.einsum('nj,jk,nk->n', delta, VI, delta)
out_2 = np.sum((delta @ VI) * delta, axis=-1)
np.allclose(out_1, out_2)
# True

我是怎么做到的？

nj,jk->nk是一个点积：

tmp_1 = np.einsum('nj,jk->nk', delta, VI)
tmp_2 = delta @ VI
np.allclose(tmp_1, tmp_2)  # True

nk,nk->nk是元素乘积：

tmp_3 = np.einsum('nk,nk->nk', tmp_1, delta)
tmp_4 = tmp_2 * delta
np.allclose(tmp_3, tmp_4)  # True

并且nk->n是最后一个轴的总和：

tmp_5 = np.einsum('nk->n', tmp_3)
tmp_6 = np.sum(tmp_4, axis=-1)
np.allclose(tmp_5, tmp_6)  # True

矢量化VI

您会注意到VI沿第一个轴进行矢量化只会起作用：

# Vectorized `VI`
nd_VI = np.random.rand(3, 783, 783)
# Unvectorized `VI`, for comparison
VI = nd_VI[0, :]
delta = np.random.rand(6000, 783)

out = np.sum((delta @ VI) * delta, axis=-1)
out.shape
# (6000,)

nd_out = np.sum((delta @ nd_VI) * delta, axis=-1)
nd_out.shape
# (3, 6000)

# Result of vectorized and unvectorized `IV` are the same
np.allclose(out, nd_out[0, :])
# True

矢量化VI和delta元素化

与向量化VI和相同，只需在anddelta的开头添加相同数量的元素VIdelta

# Vectorized `VI`
nd_VI = np.random.rand(3, 783, 783)
# Unvectorized `VI`, for comparison
VI = nd_VI[0, ...]
# Vectorized `delta`
nd_delta = np.random.rand(3, 6000, 783)
# Unvectorized `delta`, for comparison
delta = nd_delta[0, ...]

out = np.sum((delta @ VI) * delta, axis=-1)
out.shape
# (6000,)

nd_out = np.sum((nd_delta @ nd_VI) * nd_delta, axis=-1)
nd_out.shape
# (3, 6000)

# Result of vectorized and unvectorized `IV` are the same
np.allclose(out, nd_out[0, ...])
# True

向量化VI和delta独立

或者，如果您想计算 中的每个元素与 中VI的每个可能元素的马氏距离delta，您可以使用广播：

# Vectorized `VI`, note the extra empty dimension (where `delta` has 3)
nd_VI = np.random.rand(4, 1, 783, 783)
# Unvectorized `VI`, for comparison
VI = nd_VI[0, 0, ...]
# Vectorized `delta`, note the extra empty dimension (where `VI` has 4)
nd_delta = np.random.rand(1, 3, 6000, 783)
# Unvectorized `delta`, for comparison
delta = nd_delta[0, 0, ...]

out = np.sum((delta @ VI) * delta, axis=-1)
out.shape
# (6000,)

nd_out = np.sum((nd_delta @ nd_VI) * nd_delta, axis=-1)
nd_out.shape
# (4, 3, 6000)

# Result of vectorized and unvectorized `IV` are the same
np.allclose(out, nd_out[0, 0, ...])
# True