加快Mahalanobis距离计算

Question

背景：

我正在实现一个顺序的向后选择算法，以从数据集中选择功能。所讨论的数据集是MNIST。我有60000个长度为784的向量。

该算法要求我从总计784中删除一项功能，fi，并在以下代码中选择剩余的783个功能，称为selection。然后，我必须计算每个向量的Mahalanobis，以达到其阶段的平均值。迭代完成后，我遗漏了两个功能，然后删除了三个功能，依此类推。这些迭代中的每一个都需要3分钟。

我必须选择500个功能，因此上述重复500次，因此总共计算了Mahalanobis距离500 x 784 = 392,000次。这要求我计算协方差矩阵的倒数。该协方差矩阵的倒数不存在，因为它是奇异的，所以我使用了numpy的伪内。

问题

您可以想象以上非常慢。计算伪内的过程是最慢的过程。我以为我可以通过预先计算伪内，然后删除与fi相关的相应列和行。但是，事实证明，该伪内矩阵不等于直接从我已经删除fi的向量计算的伪内矩阵。

我尝试了

我尝试在很大程度上对其进行介绍，并处理一堆阵列，只是发现分解方法较慢。我尝试了NP.Einsum，CDIST甚至Numexpr。没有任何帮助。

这使我相信，加速此速度的最佳机会是以某种方式将协方差和伪内计算从这个循环中移出。这是我当前的代码：

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
    ci = u @ (1/s[...,None] * u.T)
    return np.sum(((delta @ ci) * delta), axis=-1)

值得注意的是，此功能和您的功能都无法正常工作。