向量化径向基函数的多维特征欧氏距离计算

Question

我怀疑可能有一个 SO post 已经回答了这个问题，但我还没有找到它，所以如果这是一个重复的问题，我提前道歉。

出于我自己的学习目的，我正在尝试使用 Numpy 从头开始实现径向基函数内核。对于一维输入，计算非常简单：

def kernel(x, y):
    return * np.exp( -0.5 * np.subtract.outer(x, y)**2)

以上来自blog post on Gaussian Processes.

但我正在尝试将其扩展到多个维度。我有一个在下面运行良好的实现：

x = np.array([[4,3,5], [1,3,9], [0,1,0], [4,3,5]])
distances = []
γ = -.5
for i in x:
    for j in x:
        distances.append(np.exp(γ * np.linalg.norm(i - j) ** 2))
np.array(distances).reshape(len(x),len(x))

[[1.00000000e+00 3.72665317e-06 1.69189792e-10 1.00000000e+00]
 [3.72665317e-06 1.00000000e+00 2.11513104e-19 3.72665317e-06]
 [1.69189792e-10 2.11513104e-19 1.00000000e+00 1.69189792e-10]
 [1.00000000e+00 3.72665317e-06 1.69189792e-10 1.00000000e+00]]

我正在使用 sklearn.pairwise.rbf_kernel

检查

from sklearn.metrics.pairwise import rbf_kernel
print(rbf_kernel(x, gamma= .5))

[[1.00000000e+00 3.72665317e-06 1.69189792e-10 1.00000000e+00]
 [3.72665317e-06 1.00000000e+00 2.11513104e-19 3.72665317e-06]
 [1.69189792e-10 2.11513104e-19 1.00000000e+00 1.69189792e-10]
 [1.00000000e+00 3.72665317e-06 1.69189792e-10 1.00000000e+00]]

但很明显，双 for 循环并不是迭代此方法的最有效方法。向量化此操作的最佳方法是什么？

此提供了一种计算距离的有效方法，但没有提供我需要的矢量化。

Answer 1

我们可以使用 SciPy's cdist 然后用指数值缩放它们 -

from scipy.spatial.distance import cdist

lam = -.5
out = np.exp(lam* cdist(x,x,'sqeuclidean'))

我们也可以-

def sqcdist_own(x):
    row_sum = (x**2).sum(1) # or np.einsum('ij,ij->i',x,x)
    sqeucdist = row_sum - 2*x.dot(x.T)
    sqeucdist += row_sum[:,None]
    return sqeucdist

out = np.exp(lam* cdist(x,x,'sqeuclidean'))

要在 2D 和 1D 情况下使用这些方法，将 x 重塑为 2D 作为预处理步骤：X = x.reshape(len(x),-1) 然后使用 X 作为这些解决方案的输入。

Answer 2

您可以利用以下观察来解决问题：

||a - b|| ** 2 = ||a|| ** 2 + ||b|| ** 2 - 2 * <a, b>

在代码中，它将如下所示：

x_norm = np.linalg.norm(x, axis=1) ** 2
output = np.exp(- 0.5 * (x_norm.reshape(-1, 1) + x_norm.reshape(1, -1) - 2 * np.dot(x, x.T)))

向量化径向基函数的多维特征欧氏距离计算

Vectorizing radial basis function's euclidean distance calculation for multidimensional features

python

numpy

linear-algebra

scikit-learn