Преобразование двойной для L oop в Numpy линейную алгебру для двойной формы SVM

Question

Я пытаюсь создать SVM Dual Form, и сейчас он работает очень медленно, но правильно. В настоящее время у меня есть это для целевой функции (которая является узким местом) ...

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 имеют одинаковую длину. а и у содержат все числа с плавающей точкой. 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() и сравнил его с 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() примерно в 220 раз быстрее, чем original_way().

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