Ускорение расчета расстояния Махаланобис

Question

Фон:

Я реализую алгоритм последовательного обратного выбора для выбора объектов из набора данных.Этот набор данных - MNIST.У меня 60000 векторов длиной 784.

Алгоритм требует, чтобы я исключил одну функцию, fi из общего числа 784, и выбрал оставшиеся 783 функции, которые в приведенном ниже коде называются selection.Затем я должен вычислить махаланобис каждого вектора в соответствии с его классом уважения.Как только эта итерация завершена, я оставляю две функции, а затем три и так далее.Каждая из этих итераций занимает 3 минуты.

Мне нужно выбрать 500 объектов, чтобы описанное выше повторялось 500 раз, поэтому общее расстояние Махаланобиса вычисляется 500 x 784 = 392,000 раз.Это требует от меня вычисления обратной матрицы ковариации.Инверсия этой ковариационной матрицы не существует, так как она является единственной, поэтому я использую псевдообратную numpy.

Задача

Как вы можете себе представить, описанное выше очень медленно,Вычисление псевдообратного процесса - самый медленный процесс.Я подумал, что смогу уйти с предварительным вычислением псевдообращения, а затем удалить соответствующие столбцы и строки, связанные с fi.Однако, как оказалось, эта псевдообратная матрица не равна псевдообратной матрице, вычисленной непосредственно из векторов, где я уже удаляю fi.

То, что я пробовал

Я пытался в значительной степени векторизовать это и обрабатывать стеки массивов только для того, чтобы выяснить, что факторизованный подход был медленнее.Я пробовал np.einsum, cdist и даже Numberxpr.Ничто действительно не помогает.

Это заставляет меня поверить, что лучший шанс для ускорения этого процесса - это как-то вывести ковариацию и псевдообратное вычисление из этого цикла.Это мой текущий код:

def mahalanobis(self, data, lbls, selection):
    subset data[:,tuple(selection)]

    for n in range(10):
        class_rows = subset[np.where(y == n)]
        mean = np.mean(class_rows, axis = )
        pseudoInverse = pinv(covariance(class_rows))
        delta = C - u
        d[n] = np.mean(np.sum(((delta @ pseudoInverse) * delta), axis = -1))
    return np.mean(d)

Вопрос

Как я могу ускорить это вычисление?Из тестов, которые я провел на прошлой неделе, кажется, что самая медленная часть этого вычисления - строка pseudoInverse = pinv(covariance(class_rows)).

Answer 1

Прямо сейчас, ваш код по сути:

def mahalanobis(delta, cov):
    ci = np.linalg.pinv(cov)
    return np.sum(((delta @ ci) * delta), axis=-1)

Вы можете немного ускорить это:

• Использование svd напрямую вместо pinv и устранение спряжений, которые вы не используете.
• Использование eigh вместо svd, которое использует симметрию ковариационной матрицы

def mahalanobis_eigh(delta, cov):
    s, u = np.linalg.eigh(cov)
    # note: missing filtering of small s, which you might want to consider adding - pinv already does this for you
    ic = u @ (1/s[...,None] * u.T)
    return np.sum(((delta @ ci) * delta), axis=-1)

Стоит отметить, что ни эта функция, ни ваша функция не работают корректно для комплексных значений.