将二重For循环转换为对偶SVM的Numpy线性代数

Question

我正在尝试创建一个Dual Form SVM，它运行速度很慢，但现在运行正确。我目前有这个目标函数(这是瓶颈(。。。

ij = 0
for i in range(len(x)):
for j in range(len(x)):
ij += y[i]*y[j]*a[i]*a[j]*np.dot(x[i].T, x[j])
ij /= 2

这跑得很慢。我需要以某种方式将其转换为线性代数，以使用NumPy来加快速度，但我倾向于在这方面遇到困难。

仅供参考：a、y和x都是相同的长度。a和y包含所有浮点值。x是浮点的二维向量。

Answer 1

我认为有一种更好/更干净的方法，但在这里我做到了最好。

def np_way():
# Compute 1st part: y[i]*y[j]*a[i]*a[j]
ay = a*y
ya = np.outer(ay, ay)
# print(ya)
# Compute 2nd part: np.dot(x[i].T, x[j])
_dot = np.outer(x, x)
dot = _dot[::2, ::2] + _dot[1::2, 1::2]
# print(dot)
return (ya * dot).sum()/2

您可以取消注释以调试它。

我已经把你的代码放在original_way()函数中，并将ir与np_way()进行了比较，这样我就可以使用timeit:

%timeit original_way()
%timeit np_way()
1 loop, best of 3: 708 ms per loop
100 loops, best of 3: 3.21 ms per loop

结果表明，长度为500，np_way()比original_way()快220倍左右。

Answer 2

y[i]*y[j]*a[i]*a[j]*np.dot(x[i].T, x[j])

我认为ij和可以写成广播的外积，然后是平坦和

temp = y[:,None]*y*a[:,None]*a*(x.T@x)
temp = temp.sum()

我写这篇文章没有经过测试，所以可能会有错误。

或

ya = y*a
temp = np.outer(ya,ya)
temp *= x.T@x