如何在计算核函数时使用 numpy einsum 和 numexpr 来提高性能？

Question

我正在尝试为 sklearn 库中的 svm.SVR 方法定义一些著名的内核，如 RBF、双曲正切、傅里叶等。我开始研究 rbf（我知道 rbf 的 svm 中有一个默认内核，但我需要定义一个以便以后能够对其进行自定义），并在 here 中找到了一些有用的 link并选择了这个：

def my_kernel(X,Y):
    K = np.zeros((X.shape[0],Y.shape[0]))
    for i,x in enumerate(X):
        for j,y in enumerate(Y):
            K[i,j] = np.exp(-1*np.linalg.norm(x-y)**2)
    return K

clf=SVR(kernel=my_kernel)

我使用这个是因为我可以将它用于我的火车（形状为 [3850,4]）和测试数据（形状为 [1200,4]），它们具有不同的形状。但问题是太慢了，要等这么久才能出结果。我什至在 cython 中使用了 static-typing 和 memoryviews，但它的性能不如默认的 svm rbf 内核。我还发现 link 也有同样的问题，但使用 numpy.einsum 和 numexpr.evaluate 对我来说有点混乱。事实证明，就速度性能而言，这是最好的代码：

从 scipy.linalg.blas 导入 sgemm

def app2(X, gamma, var):
    X_norm = -gamma*np.einsum('ij,ij->i',X,X)
    return ne.evaluate('v * exp(A + B + C)', {\
        'A' : X_norm[:,None],\
        'B' : X_norm[None,:],\
        'C' : sgemm(alpha=2.0*gamma, a=X, b=X, trans_b=True),\
        'g' : gamma,\
        'v' : var\
    })

此代码仅适用于一个输入 (X)，我找不到针对我的情况修改它的方法（两个具有两种不同大小的输入 - 内核函数获取形状为 (m,n) 的矩阵，并且(l,n) 并根据 svm docs 输出 (m,l)）。我想我只需要替换第二个代码中第一个代码中的 K[i,j] = np.exp(-1*np.linalg.norm(x-y)**2) 即可加快速度。任何帮助将不胜感激。

Answer 1

三种可能的变体

变体 1 和 3 使用

(a-b)^2 = a^2 + b^2 - 2ab

如所述 or 。但对于像小二维变体 2 这样的特殊情况也可以。

import numpy as np
import numba as nb
import numexpr as ne
from scipy.linalg.blas import sgemm

def vers_1(X,Y, gamma, var):
    X_norm = -gamma*np.einsum('ij,ij->i',X,X)
    Y_norm = -gamma*np.einsum('ij,ij->i',Y,Y)
    return ne.evaluate('v * exp(A + B + C)', {\
        'A' : X_norm[:,None],\
        'B' : Y_norm[None,:],\
        'C' : sgemm(alpha=2.0*gamma, a=X, b=Y, trans_b=True),\
        'g' : gamma,\
        'v' : var\
    })

#Maybe easier to read but slow, if X.shape[1] gets bigger
@nb.njit(fastmath=True,parallel=True)
def vers_2(X,Y):
    K = np.empty((X.shape[0],Y.shape[0]),dtype=X.dtype)
    for i in nb.prange(X.shape[0]):
        for j in range(Y.shape[0]):
            sum=0.
            for k in range(X.shape[1]):
                sum+=(X[i,k]-Y[j,k])**2
            K[i,j] = np.exp(-1*sum)
    return K

@nb.njit(fastmath=True,parallel=True)
def vers_3(A,B):
    dist=np.dot(A,B.T)

    TMP_A=np.empty(A.shape[0],dtype=A.dtype)
    for i in nb.prange(A.shape[0]):
        sum=0.
        for j in range(A.shape[1]):
            sum+=A[i,j]**2
        TMP_A[i]=sum

    TMP_B=np.empty(B.shape[0],dtype=A.dtype)
    for i in nb.prange(B.shape[0]):
        sum=0.
        for j in range(B.shape[1]):
            sum+=B[i,j]**2
        TMP_B[i]=sum

    for i in nb.prange(A.shape[0]):
        for j in range(B.shape[0]):
            dist[i,j]=np.exp((-2.*dist[i,j]+TMP_A[i]+TMP_B[j])*-1)
    return dist

时间

gamma = 1.
var = 1.
X=np.random.rand(3850,4)
Y=np.random.rand(1200,4)

res_1=vers_1(X,Y, gamma, var)
res_2=vers_2(X,Y)
res_3=vers_3(X,Y)
np.allclose(res_1,res_2)
np.allclose(res_1,res_3)


%timeit res_1=vers_1(X,Y, gamma, var)
19.8 ms ± 615 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit res_2=vers_2(X,Y)
16.1 ms ± 938 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit res_3=vers_3(X,Y)
13.5 ms ± 162 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Answer 2

您可以直接通过 pythran

管道传输您的原始内核

kernel.py:

import numpy as np

#pythran export my_kernel(float64[:,:], float64[:,:])
def my_kernel(X,Y):
    K = np.zeros((X.shape[0],Y.shape[0]))
    for i,x in enumerate(X):
        for j,y in enumerate(Y):
            K[i,j] = np.exp(-1*np.linalg.norm(x-y)**2)
    return K

编译步骤：

> pythran kernel.py

没有重写步骤（尽管您需要将内核放在一个单独的文件中）并且加速非常显着：使用

在我的笔记本电脑上速度提高了 19 倍

> python -m timeit -s 'from numpy.random import random; x = random((100,100)); y = random((100,100)); from svr_kernel import my_kernel as k' 'k(x,y)'

收集时间。

如何在计算核函数时使用 numpy einsum 和 numexpr 来提高性能？

How can I speed up the performance by using numpy einsum and numexpr in calculating kernel functions?

python

performance

numexpr

numpy-einsum

三种可能的变体