1

背景：

我正在实现一个顺序向后选择算法来从数据集中选择特征。有问题的数据集是 MNIST。我有 60000 个长度为 784 的向量。

fi该算法要求我从总共 784个特征中遗漏一个特征，并选择剩余的 783 个特征，selection在下面的代码中调用。然后我必须计算每个向量的 Mahalanobis 到它的尊重类的平均值。一旦这个迭代完成，我会遗漏两个特征，然后是三个，依此类推。这些迭代中的每一个都需要 3 分钟。

我必须选择 500 个特征，因此上述内容重复 500 次，因此总共计算了马氏距离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)

问题

我怎样才能加快这个计算？从我过去一周所做的测试来看，这个计算中最慢的部分似乎是 line pseudoInverse = pinv(covariance(class_rows))。

4

1 回答 1

0

现在，您的代码本质上是：

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)

值得注意的是，此函数和您的函数都不能正确处理复杂值。

于 2019-03-11T04:12:18.597 回答