Рандомизированная линейная алгебра (RandNLA): вычисления через вероятности

Традиционные алгоритмы вычислительной линейной алгебры (такие как сингулярное разложение или QR-факторизация) требуют кубического времени выполнения, что делает их абсолютно неприменимыми для обработки современных массивов данных петабайтного масштаба. В ответ на этот вызов математики создали совершенно новую парадигму — Рандомизированную вычислительную линейную алгебру (RandNLA). Вместо точных, детерминированных, но бесконечно долгих вычислений, этот подход использует законы теории вероятностей для нахождения потрясающе точных аппроксимаций за долю секунды. RandNLA лежит в основе алгоритмов машинного обучения корпоративного уровня, позволяя мгновенно сжимать матрицы, находить главные компоненты и решать переопределенные системы огромной размерности.

Лемма Джонсона-Линденштрауса и случайные проекции

Фундаментом всей рандомизированной алгебры является геометрическая лемма, доказанная в 1984 году Уильямом Джонсоном и Йорамом Линденштраусом. Лемма утверждает поразительный факт: любой набор из N точек в евклидовом пространстве невероятно высокой размерности может быть спроецирован (сплющен) в пространство логарифмически малой размерности (порядка O(log N / epsilon^2)), при этом все попарные расстояния между точками исказятся не более чем на малую величину epsilon. Самое потрясающее — эта проекция осуществляется не сложным алгоритмом оптимизации, а простым умножением данных на матрицу, элементы которой заполнены случайными числами (например, из стандартного нормального распределения). Это позволяет кардинально сжать данные перед их анализом, не потеряв их внутреннюю геометрическую структуру.

Рандомизированное сингулярное разложение (rSVD)

Классическое усеченное SVD для поиска k главных компонент матрицы A размера m на n требует времени O(m * n * k). Рандомизированный алгоритм rSVD решает эту задачу иначе. Сначала генерируется «эскиз» (sketch) исходной матрицы. Для этого матрица A умножается на случайную гауссовскую матрицу Omega размера n на (k+p), где p — небольшая добавка (oversampling parameter). Результатом является компактная матрица Y = A * Omega. Далее с помощью QR-разложения находится ортонормированный базис матрицы Y (матрица Q). Наконец, исходная матрица A проецируется на этот компактный случайный базис: B = Q^T * A. Классическое SVD выполняется уже не для гигантской A, а для крошечной матрицы B. Результаты перемножаются, давая идеальное приближение спектра оригинальной матрицы при затратах, близких к линейным.

Метод Нюстрёма для ядерных матриц

В машинном обучении (например, в методе опорных векторов) возникают ядровые матрицы (Kernel matrices) размера N на N, где N — количество объектов. При миллионах объектов хранение такой плотной матрицы требует терабайтов оперативной памяти. Метод аппроксимации Нюстрёма позволяет обойти это препятствие. Вместо вычисления всей матрицы алгоритм случайным образом выбирает крошечную подвыборку из m столбцов (где m гораздо меньше N). Используя только эти столбцы и подматрицу их взаимных пересечений, линейная алгебра метода Нюстрёма восстанавливает (аппроксимирует) всю исходную гигантскую матрицу, опираясь на предположение о ее низком ранге. Это снижает сложность вычислений с кубической до линейной, делая возможным глубокое обучение на огромных датасетах.

Оценка следа: метод Хатчинсона

Вычисление следа обратной матрицы (Tr(A^(-1))) или логарифма определителя гигантских матриц необходимо в байесовской статистике и машинном обучении, однако прямое обращение матрицы невозможно. В 1989 году Хатчинсон предложил элегантный вероятностный трюк. Оказывается, след любой матрицы A равен математическому ожиданию квадратичной формы v^T * A * v, где v — вектор, элементы которого являются независимыми случайными величинами со средним нулем и дисперсией единица (например, случайный вектор, состоящий из +1 и -1). Для оценки следа достаточно сгенерировать несколько таких случайных векторов, умножить их на матрицу (или решить систему уравнений A*x = v итерационным методом, не находя обратную матрицу явно) и усреднить результаты. Дисперсия такой оценки стремительно падает с ростом числа тестовых векторов.

Оценить