Почему в scikit-learn truncatedSVD по умолчанию используется "рандомизированный" алгоритм?

Question

Я использовал truncatedSVD с размером матрицы 30000 на 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-й крупнейших компонентов. Рандомизированный алгоритм также легче эффективно распараллелить и делает меньше проходов по данным.

В таблице 7.1 статьи (на странице 45) показана производительность нескольких алгоритмов в зависимости от размера матрицы и количества компонентов, а рандомизированный алгоритм часто на порядок быстрее.

Точность вывода также считается довольно хорошей (рис. 7.5), хотя есть некоторые модификации и константы, которые могут повлиять на нее, и я не изучал код sklearn, чтобы увидеть, что они сделали / не сделали.