Рандомизированный метод Качмажа: алгебра стохастического градиентного спуска
Когда дата-сайентисты обучают гигантские нейронные сети или решают переопределенные системы уравнений на терабайтах данных, они не могут загрузить всю матрицу в оперативную память. Решением стала разработка алгоритмов, которые считывают данные по одной строке (одному примеру) за раз. Исторически первым таким алгоритмом стал алгоритм польского математика Стефана Качмажа, опубликованный в 1937 году. В 2009 году Томас Стромер и Роман Вершинин доказали, что если выбирать строки матрицы не по порядку, а случайным образом с определенными вероятностями, метод Качмажа обретает фантастическую, экспоненциальную скорость сходимости. Так родилась строгая алгебраическая теория рандомизированного метода Качмажа (RK), ставшая фундаментом для понимания современного стохастического градиентного спуска (SGD).
Геометрия проекций на гиперплоскости
Рассмотрим переопределенную систему линейных уравнений A*x = b. Каждое отдельное уравнение (строка матрицы A) геометрически задает гиперплоскость в n-мерном пространстве. Решение системы (если оно существует) — это единственная точка, в которой пересекаются все эти гиперплоскости. Классический метод Качмажа работает предельно наглядно: мы берем случайную начальную точку x_0. Затем мы берем первое уравнение и ортогонально проецируем нашу точку на гиперплоскость этого уравнения. Полученную точку x_1 мы проецируем на гиперплоскость второго уравнения, и так далее по кругу. Геометрия гарантирует, что точка будет двигаться зигзагами, но неуклонно приближаться к истинной точке пересечения. Формула проекции элементарна и требует лишь вычисления скалярного произведения вектора строки на текущее приближение.
Проблема циклического порядка и рандомизация
Главный недостаток оригинального алгоритма Качмажа заключается в том, что при циклическом (последовательном) переборе строк алгоритм может застрять. Если гиперплоскости расположены под очень острыми углами друг к другу, точка будет бесконечно долго метаться между ними, продвигаясь к цели микроскопическими шагами. Стромер и Вершинин решили эту проблему, предложив Рандомизированный метод Качмажа. В их версии на каждом шаге строка матрицы выбирается абсолютно случайно, но не равновероятно! Вероятность выбора i-й строки должна быть строго пропорциональна квадрату ее евклидовой нормы (квадрату длины вектора-строки). То есть «длинные» строки (несущие больше геометрической информации) выбираются чаще, чем «короткие».
Теорема об экспоненциальной сходимости
Введение вероятностного выбора сотворило алгебраическое чудо. Стромер и Вершинин строго математически доказали, что математическое ожидание квадрата ошибки (расстояния от текущей точки x_k до точного решения) убывает с экспоненциальной скоростью на каждом шаге. Фактор уменьшения ошибки жестко зависит от так называемого числа обусловленности Качмажа (отношения квадрата нормы Фробениуса всей матрицы к ее минимальному сингулярному числу). Поразительность этого результата в том, что скорость сходимости абсолютно не зависит от количества уравнений в системе (количества строк матрицы m)! Это означает, что метод RK решает систему из миллиарда уравнений так же быстро, как систему из тысячи уравнений, считывая лишь крошечную случайную долю данных.
Связь с SGD и компьютерной томографией
В мире машинного обучения метод Качмажа в точности эквивалентен алгоритму Стохастического Градиентного Спуска (Stochastic Gradient Descent, SGD), применяемому для квадратичной функции потерь (MSE). В машинном обучении гиперплоскости — это данные обучающей выборки. RK доказывает, почему SGD так феноменально успешен в обучении нейросетей: случайный выбор примеров (mini-batches) прорезает «острые углы» функции потерь и стремительно падает в глобальный минимум. Но исторически самым первым практическим применением метода Качмажа стал алгоритм ART (Algebraic Reconstruction Technique), разработанный в 1970-х годах Ричардом Гордоном для медицинских компьютерных томографов. Он позволил восстанавливать 3D-изображения внутренних органов человека по сотням плоских рентгеновских снимков, последовательно проецируя плотности пикселей на уравнения рентгеновских лучей.
