python - 在 python 中计算 RBF 内核的最快方法是什么？

Question

我想为具有 n 行和 d 列的数据矩阵 X 计算 RBF 或“高斯”内核。得到的方核矩阵由下式给出:

K[i,j] = var * exp(-gamma * ||X[i] - X[j]||^2)

var 和 gamma 是标量。

在 python 中执行此操作的最快方法是什么？

Answer 1

我将介绍四种不同的方法来计算这种内核，然后比较它们的运行时间。

使用纯 numpy

在这里，我使用了 ||x-y||^2 = ||x||^2 + ||y||^2 - 2 * x^T * y 这一事实。

import numpy as np

X_norm = np.sum(X ** 2, axis = -1)
K = var * np.exp(-gamma * (X_norm[:,None] + X_norm[None,:] - 2 * np.dot(X, X.T)))

使用数字表达式

numexpr是一个 python 包，允许对 numpy 数组进行高效和并行的数组操作。我们可以按如下方式使用它来执行与上面相同的计算:

import numpy as np
import numexpr as ne

X_norm = np.sum(X ** 2, axis = -1)
K = ne.evaluate('v * exp(-g * (A + B - 2 * C))', {
        'A' : X_norm[:,None],
        'B' : X_norm[None,:],
        'C' : np.dot(X, X.T),
        'g' : gamma,
        'v' : var
})

使用scipy.spatial.distance.pdist

我们也可以使用 scipy.spatial.distance.pdist要计算成对平方欧氏距离的非冗余数组，请计算该数组上的内核，然后将其转换为方矩阵:

import numpy as np
from scipy.spatial.distance import pdist, squareform

K = squareform(var * np.exp(-gamma * pdist(X, 'sqeuclidean')))
K[np.arange(K.shape[0]), np.arange(K.shape[1])] = var

使用sklearn.metrics.pairwise.rbf_kernel

sklearn 提供了一个 built-in method直接计算 RBF 内核:

import numpy as np
from sklearn.metrics.pairwise import rbf_kernel

K = var * rbf_kernel(X, gamma = gamma)

运行时比较

我使用 25,000 个 512 维的随机样本进行测试，并在 Intel Core i7-7700HQ(4 核 @ 2.8 GHz)上进行实验。更准确地说:

X = np.random.randn(25000, 512)
gamma = 0.01
var = 5.0

每种方法运行 7 次，并报告每次执行时间的平均值和标准差。

|               Method                |       Time        |
|-------------------------------------|-------------------|
| numpy                               | 24.2 s ± 1.06 s   |
| numexpr                             | 8.89 s ± 314 ms   |
| scipy.spatial.distance.pdist        | 2min 59s ± 312 ms |
| sklearn.metrics.pairwise.rbf_kernel | 13.9 s ± 757 ms   |

首先，scipy.spatial.distance.pdist 出奇地慢。

numexpr 几乎比纯 numpy 方法快 3 倍，但这个加速因子会随着可用 CPU 的数量而变化。

sklearn.metrics.pairwise.rbf_kernel 不是最快的方法，但只比 numexpr 慢一点。