Python 中的高效逐元素函数计算

Question

我有以下优化问题。给定两个 np.arrays X,Y 和一个函数 K 我想尽快计算矩阵关联 gram_matrix 其中 (i,j)-th元素计算为 K(X[i],Y[j])。

这里有一个使用嵌套 for 循环的实现，它被认为是解决这类问题最慢的。

def proxy_kernel(X,Y,K):
    gram_matrix = np.zeros((X.shape[0], Y.shape[0]))
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            gram_matrix[i, j] = K(x, y)
    return gram_matrix

非常感谢您的帮助。

Answer 1

您至少可以对内部循环进行矢量化：

def proxy_kernel_vect(X, Y, K):
    K_vect = np.vectorize(K)
    gram_matrix = np.zeros((X.shape[0], Y.shape[0]))
    for i, x in enumerate(X):
        gram_matrix[i] = K_vect(x, Y)
    return gram_matrix

这对相对较长的数组产生了很好的改进：

In [15]: a = np.array(range(1000))
    ...: b = np.array(range(1000))
    ...: 

In [16]: %timeit proxy_kernel(a, b, k)
1 loops, best of 3: 665 ms per loop

In [17]: %timeit proxy_kernel_vect(a, b, k)
1 loops, best of 3: 266 ms per loop

其中 k 只是 lambda x, y: x+y.

Answer 2

np.vectorize 确实在速度上做了一些改进 - 大约 2 倍（这里我使用 math.atan2 作为一个带有 2 个标量参数的黑盒函数）。

In [486]: X=np.linspace(0,1,100)
In [487]: K_vect=np.vectorize(math.atan2)

In [488]: timeit proxy_kernel(X,X,math.atan2)
100 loops, best of 3: 7.84 ms per loop

In [489]: timeit K_vect(X[:,None],X)
100 loops, best of 3: 3.49 ms per loop

In [502]: timeit np.arctan2(X[:,None],X)  # numpy compiled loop
1000 loops, best of 3: 871 µs per loop

哪里

def proxy_kernel(X,Y,K):
    gram_matrix = np.zeros((X.shape[0], Y.shape[0]))
    for i, x in enumerate(X):
            for j, y in enumerate(Y):
                    gram_matrix[i, j] = K(x, y)
    return gram_matrix

只要 K 是黑盒子，您就会受到调用 K 和 X.shape[0]*Y.shape[0] 次所需时间的限制。您可以尝试最小化迭代时间，但您仍然受到所有这些函数调用的限制。

通过利用 np.linalg.norm 函数的 axis 参数加速高斯核的计算。

Answer 3

您也可以尝试 numba 模块中的 vectorize 装饰器。

使用 vectorize 和 numpy broadcasting:

可以轻松解决您的特定问题

from numba import vectorize

@vectorize(['float64(float64, float64)'])
def K(x,y):
    return x + y

a = np.arange(1000)
b = np.arange(1000)

gram_array = K(a[None,:], b[:, None])

Python 中的高效逐元素函数计算

Efficient element-wise function computation in Python

python

numpy

vectorization

scikit-learn