Einsum очень медленно вычисляет c расстояние - PullRequest
Новая
       30

Einsum очень медленно вычисляет c расстояние

0 голосов
/ 07 марта 2019

Я вычисляю расстояние махаланобиса через np.einsum: 

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

, где VI, обратная ковариационная матрица, равна 783 x 783, а дельта равна 6000 x 783.Эта строка занимает 10 секунд на моем Macbook Pro 2016 года, чтобы выполнить.Как я могу сделать это быстрее?

Я должен вычислить эту строку от 200 000 до 300 000 раз.Векторизация не может быть вариантом, потому что VI отличается для каждого класса.

1 Ответ

2 голосов
/ 07 марта 2019

Нет необходимости в 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 и delta, просто добавьте одинаковое количество элементов в начало VI и delta

# 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
...