scikit-learn - 为什么 scikit-learn truncatedSVD 默认使用“随机”算法？

Question

我使用 truncatedSVD 和 30000 x 40000 大小的术语文档矩阵来将维度减少到 3000 维度，当使用“随机化”时，方差比约为 0.5（n_iter=10），当使用“arpack”时，方差比约为 0.9

“随机”算法的方差比低于“arpack”之一。

那么为什么 scikit-learn truncatedSVD 默认使用“随机”算法呢？

Answer 1

速度！

根据文档，sklearn.decomposition.TruncatedSVD由于Halko、Martinson 和 Tropp (2009)，可以使用随机算法。这篇论文声称他们的算法要快得多。

对于密集矩阵，它在 O(m*n*log(k)) 时间内运行，而经典算法需要 O(m*n*k) 时间，其中 m 和 n 是您想要的矩阵的维度第 k 个最大的组件。随机算法也更容易有效地并行化，并且对数据的传递次数更少。

论文（第 45 页）的表 7.1 显示了一些算法的性能作为矩阵大小和组件数量的函数，随机算法通常快一个数量级。

输出的准确性也声称非常好（图 7.5），尽管有一些修改和常量可能会影响它，而且我还没有查看 sklearn 代码来查看它们做了什么/没做什么。