Алгоритм Синкхорна

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
 
Строка 1: Строка 1:
{{well|Статья написана с использованием LLM '''DeepSeek''' и проверена участником [[Участник:Kirill Savitskii|Kirill Savitskii]] 18:01, 15 июля 2026 (MSD)}}
{{well|Статья написана с использованием LLM '''DeepSeek''' и проверена участником [[Участник:Kirill Savitskii|Kirill Savitskii]] 18:01, 15 июля 2026 (MSD)}}
-
'''Алгоритм Синкхорна''' (также известный как '''итерации Синкхорна–Кноппа''') — это [[итеративный метод]] масштабирования строк и столбцов [[Матрица (математика)|матрицы]], который позволяет эффективно решать задачу [[Оптимальный транспорт|оптимального транспорта]] с [[Энтропийная регуляризация|энтропийной регуляризацией]]. Он лежит в основе современных вычислительных инструментов для работы с [[Расстояние Вассерштейна|расстоянием Вассерштейна]] и его сглаженным вариантом — '''расстоянием Синкхорна'''. Благодаря высокой скорости, простоте реализации и полной дифференцируемости, алгоритм стал одним из ключевых строительных блоков в [[Машинное обучение|машинном обучении]], [[Компьютерное зрение|компьютерном зрении]] и [[Вычислительная биология|вычислительной биологии]].
+
'''Алгоритм Синкхорна''' (также известный как '''итерации Синкхорна–Кноппа''') — это [[итеративный метод]] масштабирования строк и столбцов матрицы, который позволяет эффективно решать задачу [[Оптимальный транспорт|оптимального транспорта]] с [[Энтропийная регуляризация|энтропийной регуляризацией]]. Он лежит в основе современных вычислительных инструментов для работы с [[Расстояние Вассерштейна|расстоянием Вассерштейна]] и его сглаженным вариантом — '''расстоянием Синкхорна'''. Благодаря высокой скорости, простоте реализации и полной дифференцируемости, алгоритм стал одним из ключевых строительных блоков в [[Машинное обучение|машинном обучении]], [[Компьютерное зрение|компьютерном зрении]] и вычислительной биологии.
== История ==
== История ==
-
Математический фундамент был заложен в работах Ричарда Синкхорна. В 1964 году он доказал, что любую квадратную матрицу со строго положительными элементами можно привести к [[Дважды стохастическая матрица|дважды стохастическому]] виду попеременным диагональным масштабированием <ref>Sinkhorn, R. (1964). "A relationship between arbitrary positive matrices and doubly stochastic matrices". ''Annals of Mathematical Statistics''. '''35''' (2): 876–879.</ref>. Позже, вместе с Полом Кноппом, он обобщил результат на неотрицательные матрицы и строго доказал сходимость итераций <ref>Sinkhorn, R., & Knopp, P. (1967). "Concerning nonnegative matrices and doubly stochastic matrices". ''Pacific Journal of Mathematics''. '''21''' (2): 343–348.</ref>.
+
Математический фундамент был заложен в работах Ричарда Синкхорна. В 1964 году он доказал, что любую квадратную матрицу со строго положительными элементами можно привести к дважды стохастическому виду попеременным диагональным масштабированием <ref>Sinkhorn, R. (1964). "A relationship between arbitrary positive matrices and doubly stochastic matrices". ''Annals of Mathematical Statistics''. '''35''' (2): 876–879.</ref>. Позже, вместе с Полом Кноппом, он обобщил результат на неотрицательные матрицы и строго доказал сходимость итераций <ref>Sinkhorn, R., & Knopp, P. (1967). "Concerning nonnegative matrices and doubly stochastic matrices". ''Pacific Journal of Mathematics''. '''21''' (2): 343–348.</ref>.
В современном контексте алгоритм обрёл второе рождение благодаря Марко Кутюри, который в 2013 году предложил использовать энтропийно-регуляризованный оптимальный транспорт для быстрого вычисления расстояния Вассерштейна и ввёл термин «Синкхорновы расстояния» <ref name="cuturi2013">Cuturi, M. (2013). "Sinkhorn distances: Lightspeed computation of optimal transport". ''Advances in Neural Information Processing Systems''. '''26''': 2292–2300.</ref>. Эта работа превратила красивую теорему в практический инструмент анализа данных.
В современном контексте алгоритм обрёл второе рождение благодаря Марко Кутюри, который в 2013 году предложил использовать энтропийно-регуляризованный оптимальный транспорт для быстрого вычисления расстояния Вассерштейна и ввёл термин «Синкхорновы расстояния» <ref name="cuturi2013">Cuturi, M. (2013). "Sinkhorn distances: Lightspeed computation of optimal transport". ''Advances in Neural Information Processing Systems''. '''26''': 2292–2300.</ref>. Эта работа превратила красивую теорему в практический инструмент анализа данных.
Строка 22: Строка 22:
= \min_{\mathbf{P} \in \Pi(\mathbf{a},\mathbf{b})} \langle \mathbf{P}, \mathbf{C} \rangle + \varepsilon \sum_{i,j} P_{ij} (\log P_{ij} - 1).</tex>
= \min_{\mathbf{P} \in \Pi(\mathbf{a},\mathbf{b})} \langle \mathbf{P}, \mathbf{C} \rangle + \varepsilon \sum_{i,j} P_{ij} (\log P_{ij} - 1).</tex>
-
Введение энтропийного члена делает задачу строго [[Выпуклое множество|выпуклой]] и гладкой. Ключевым теоретическим результатом, лежащим в основе её решения, является '''теорема Синкхорна'''.
+
Введение энтропийного члена делает задачу строго выпуклой и гладкой. Ключевым теоретическим результатом, лежащим в основе её решения, является '''теорема Синкхорна'''.
'''Теорема Синкхорна (Sinkhorn, 1964; Sinkhorn & Knopp, 1967).''' Пусть <tex>K \in \mathbb{R}^{n \times m}</tex> — матрица со строго положительными элементами, а <tex>\mathbf{a} \in \Delta^n</tex> и <tex>\mathbf{b} \in \Delta^m</tex> — вероятностные векторы. Тогда существуют единственные с точностью до взаимного масштабирования диагональные матрицы <tex>\mathbf{D}_u = \operatorname{diag}(\mathbf{u})</tex> и <tex>\mathbf{D}_v = \operatorname{diag}(\mathbf{v})</tex> с положительными диагоналями, такие что матрица <tex>\mathbf{D}_u K \mathbf{D}_v</tex> имеет маргинальные суммы <tex>\mathbf{a}</tex> и <tex>\mathbf{b}</tex>. В контексте регуляризованного оптимального транспорта это означает, что решение представляется в виде
'''Теорема Синкхорна (Sinkhorn, 1964; Sinkhorn & Knopp, 1967).''' Пусть <tex>K \in \mathbb{R}^{n \times m}</tex> — матрица со строго положительными элементами, а <tex>\mathbf{a} \in \Delta^n</tex> и <tex>\mathbf{b} \in \Delta^m</tex> — вероятностные векторы. Тогда существуют единственные с точностью до взаимного масштабирования диагональные матрицы <tex>\mathbf{D}_u = \operatorname{diag}(\mathbf{u})</tex> и <tex>\mathbf{D}_v = \operatorname{diag}(\mathbf{v})</tex> с положительными диагоналями, такие что матрица <tex>\mathbf{D}_u K \mathbf{D}_v</tex> имеет маргинальные суммы <tex>\mathbf{a}</tex> и <tex>\mathbf{b}</tex>. В контексте регуляризованного оптимального транспорта это означает, что решение представляется в виде
Строка 54: Строка 54:
=== Сходимость и остановка ===
=== Сходимость и остановка ===
-
Сходимость итераций к решению с точностью до машинного нуля гарантирована для любой положительной матрицы <tex>\mathbf{K}</tex> <ref>Sinkhorn & Knopp, 1967.</ref>. На практике число необходимых итераций зависит от параметра регуляризации <tex>\varepsilon</tex>: чем он меньше, тем медленнее сходимость. Типичный критерий остановки — [[Расхождение Кульбака — Лейблера|дивергенция Кульбака–Лейблера]] между текущими маргиналами и целевыми значениями, либо допустимая погрешность изменения двойственных потенциалов.
+
Сходимость итераций к решению с точностью до машинного нуля гарантирована для любой положительной матрицы <tex>\mathbf{K}</tex> <ref>Sinkhorn & Knopp, 1967.</ref>. На практике число необходимых итераций зависит от параметра регуляризации <tex>\varepsilon</tex>: чем он меньше, тем медленнее сходимость. Типичный критерий остановки — [[дивергенция Кульбака–Лейблера]] между текущими маргиналами и целевыми значениями, либо допустимая погрешность изменения двойственных потенциалов.
== Вычислительная сложность ==
== Вычислительная сложность ==
Строка 62: Строка 62:
* '''Экранирование''' (screening) на основе <tex>\varepsilon</tex>-разреженности плана позволяет не вычислять маловероятные элементы <tex>K_{ij}</tex>, снижая сложность до <tex>\mathcal{O}(N)</tex> для одномерных задач <ref>Altschuler, J., Weed, J., & Rigollet, P. (2017). "Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration". ''Advances in Neural Information Processing Systems''. '''30''': 1964–1974.</ref>.
* '''Экранирование''' (screening) на основе <tex>\varepsilon</tex>-разреженности плана позволяет не вычислять маловероятные элементы <tex>K_{ij}</tex>, снижая сложность до <tex>\mathcal{O}(N)</tex> для одномерных задач <ref>Altschuler, J., Weed, J., & Rigollet, P. (2017). "Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration". ''Advances in Neural Information Processing Systems''. '''30''': 1964–1974.</ref>.
* '''Многоуровневые методы''' (multiscale) агрегируют опоры распределений.
* '''Многоуровневые методы''' (multiscale) агрегируют опоры распределений.
-
* Использование [[Графический процессор|GPU]] позволяет эффективно векторизовать матричные умножения.
+
* Использование GPU позволяет эффективно векторизовать матричные умножения.
== Преимущества и ограничения ==
== Преимущества и ограничения ==
Строка 85: Строка 85:
: Выравнивание распределений признаков из исходного и целевого доменов путём минимизации расстояния Синкхорна между эмпирическими распределениями. Алгоритм используется в методах типа [[COOT]] и [[JDOT]].
: Выравнивание распределений признаков из исходного и целевого доменов путём минимизации расстояния Синкхорна между эмпирическими распределениями. Алгоритм используется в методах типа [[COOT]] и [[JDOT]].
-
; [[Генеративно-состязательная сеть|Генеративное моделирование]]
+
; [[Генеративная состязательная сеть|Генеративное моделирование]]
: В [[Wasserstein GAN|WGAN]] и его вариантах расстояние Синкхорна служит стабильным и информативным сигналом для обучения генератора. Sinkhorn Autoencoder напрямую минимизирует транспортные потери в [[Латентное пространство|латентном пространстве]].
: В [[Wasserstein GAN|WGAN]] и его вариантах расстояние Синкхорна служит стабильным и информативным сигналом для обучения генератора. Sinkhorn Autoencoder напрямую минимизирует транспортные потери в [[Латентное пространство|латентном пространстве]].
Строка 100: Строка 100:
* [[Оптимальный транспорт]]
* [[Оптимальный транспорт]]
* [[Расстояние Вассерштейна]]
* [[Расстояние Вассерштейна]]
-
* [[Земное расстояние (EMD)]]
 
* [[Энтропийная регуляризация]]
* [[Энтропийная регуляризация]]
-
* [[Дважды стохастическая матрица]]
 
* [[Метод масштабирования матриц]]
* [[Метод масштабирования матриц]]
* [[Алгоритм Брэгмана]]
* [[Алгоритм Брэгмана]]

Текущая версия

Статья написана с использованием LLM DeepSeek и проверена участником Kirill Savitskii 18:01, 15 июля 2026 (MSD)


Алгоритм Синкхорна (также известный как итерации Синкхорна–Кноппа) — это итеративный метод масштабирования строк и столбцов матрицы, который позволяет эффективно решать задачу оптимального транспорта с энтропийной регуляризацией. Он лежит в основе современных вычислительных инструментов для работы с расстоянием Вассерштейна и его сглаженным вариантом — расстоянием Синкхорна. Благодаря высокой скорости, простоте реализации и полной дифференцируемости, алгоритм стал одним из ключевых строительных блоков в машинном обучении, компьютерном зрении и вычислительной биологии.

Содержание

История

Математический фундамент был заложен в работах Ричарда Синкхорна. В 1964 году он доказал, что любую квадратную матрицу со строго положительными элементами можно привести к дважды стохастическому виду попеременным диагональным масштабированием [1]. Позже, вместе с Полом Кноппом, он обобщил результат на неотрицательные матрицы и строго доказал сходимость итераций [1].

В современном контексте алгоритм обрёл второе рождение благодаря Марко Кутюри, который в 2013 году предложил использовать энтропийно-регуляризованный оптимальный транспорт для быстрого вычисления расстояния Вассерштейна и ввёл термин «Синкхорновы расстояния» [1]. Эта работа превратила красивую теорему в практический инструмент анализа данных.

Математические основы

Задача оптимального транспорта

В дискретной постановке Канторовича заданы два распределения \mathbf{a} \in \Delta^n и \mathbf{b} \in \Delta^m (вероятностные симплексы), а также матрица стоимостей \mathbf{C} \in \mathbb{R}_{+}^{n \times m}, где C_{ij} — стоимость транспортировки единицы массы из опоры i в опору j. Требуется найти транспортный план \mathbf{P} \in \mathbb{R}_{+}^{n \times m}, минимизирующий суммарные затраты:

\min_{\mathbf{P} \in \Pi(\mathbf{a},\mathbf{b})} \langle \mathbf{P}, \mathbf{C} \rangle = \min_{\mathbf{P} \in \Pi(\mathbf{a},\mathbf{b})} \sum_{i=1}^{n} \sum_{j=1}^{m} P_{ij} C_{ij},

где допустимое множество \Pi(\mathbf{a},\mathbf{b}) = \{ \mathbf{P} \in \mathbb{R}_{+}^{n \times m} \mid \mathbf{P} \mathbf{1}_m = \mathbf{a}, \mathbf{P}^\mathsf{T} \mathbf{1}_n = \mathbf{b} \} — множество всех матриц с заданными маргинальными суммами. Эта задача является задачей линейного программирования и для больших n,m требует значительных вычислительных затрат.

Энтропийная регуляризация и расстояние Синкхорна

Кютюри (2013) предложил добавить к целевой функции отрицательную энтропию Шеннона транспортного плана с весовым коэффициентом \varepsilon > 0 [1]:

\min_{\mathbf{P} \in \Pi(\mathbf{a},\mathbf{b})} \langle \mathbf{P}, \mathbf{C} \rangle - \varepsilon H(\mathbf{P}) = \min_{\mathbf{P} \in \Pi(\mathbf{a},\mathbf{b})} \langle \mathbf{P}, \mathbf{C} \rangle + \varepsilon \sum_{i,j} P_{ij} (\log P_{ij} - 1).

Введение энтропийного члена делает задачу строго выпуклой и гладкой. Ключевым теоретическим результатом, лежащим в основе её решения, является теорема Синкхорна.

Теорема Синкхорна (Sinkhorn, 1964; Sinkhorn & Knopp, 1967). Пусть K \in \mathbb{R}^{n \times m} — матрица со строго положительными элементами, а \mathbf{a} \in \Delta^n и \mathbf{b} \in \Delta^m — вероятностные векторы. Тогда существуют единственные с точностью до взаимного масштабирования диагональные матрицы \mathbf{D}_u = \operatorname{diag}(\mathbf{u}) и \mathbf{D}_v = \operatorname{diag}(\mathbf{v}) с положительными диагоналями, такие что матрица \mathbf{D}_u K \mathbf{D}_v имеет маргинальные суммы \mathbf{a} и \mathbf{b}. В контексте регуляризованного оптимального транспорта это означает, что решение представляется в виде

P_{ij}^\varepsilon = u_i K_{ij} v_j,

где K_{ij} = \exp(-C_{ij} / \varepsilon) — матрица ядра Гиббса, а векторы \mathbf{u} \in \mathbb{R}^n_+ и \mathbf{v} \in \mathbb{R}^m_+ гарантированно существуют и единственны с точностью до постоянного множителя.

Расстояние Синкхорна между распределениями \mathbf{a} и \mathbf{b} определяется как величина регуляризованной транспортной стоимости d_{\varepsilon}(\mathbf{a},\mathbf{b}) = \langle \mathbf{P}^\varepsilon, \mathbf{C} \rangle. При \varepsilon \to 0 оно сходится к точному расстоянию Вассерштейна, а при \varepsilon \to \infty вырождается в тривиальную независимую модель P_{ij} = a_i b_j.

Двойственная задача

Энтропийно-регуляризованная задача эквивалентна поиску двойственных потенциалов \mathbf{f} \in \mathbb{R}^n, \mathbf{g} \in \mathbb{R}^m, доставляющих максимум двойственному функционалу:

\max_{\mathbf{f},\mathbf{g}} \; \mathbf{f}^\mathsf{T}\mathbf{a} + \mathbf{g}^\mathsf{T}\mathbf{b} - \varepsilon \sum_{i,j} \exp\left(\frac{f_i + g_j - C_{ij}}{\varepsilon}\right).

Связь с прямыми переменными выражается как u_i = \exp(f_i / \varepsilon) и v_j = \exp(g_j / \varepsilon). Итерации алгоритма Синкхорна непосредственно решают эту двойственную задачу, попеременно пересчитывая потенциалы так, чтобы удовлетворить маргинальным ограничениям.

Алгоритм Синкхорна

Итеративная схема

Алгоритм нацелен на поиск векторов \mathbf{u} и \mathbf{v}. Из условия на маргиналы \mathbf{P} \mathbf{1}_m = \mathbf{a} и \mathbf{P}^\mathsf{T} \mathbf{1}_n = \mathbf{b} вытекает система уравнений:

\mathbf{u} \odot (\mathbf{K} \mathbf{v}) = \mathbf{a}, \quad \mathbf{v} \odot (\mathbf{K}^\mathsf{T} \mathbf{u}) = \mathbf{b},

где \odot — поэлементное умножение. Отсюда получается итеративная процедура чередующегося обновления:

\mathbf{u}^{(t+1)} = \frac{\mathbf{a}}{\mathbf{K} \mathbf{v}^{(t)}}, \qquad \mathbf{v}^{(t+1)} = \frac{\mathbf{b}}{\mathbf{K}^\mathsf{T} \mathbf{u}^{(t+1)}}.

Деление выполняется поэлементно. Начальное приближение обычно выбирают как \mathbf{v}^{(0)} = \mathbf{1}_m. Каждый шаг соответствует масштабированию строк, а затем столбцов матрицы \mathbf{K} так, чтобы они давали требуемые суммы. Итоговый план восстанавливается как \mathbf{P}^\varepsilon = \operatorname{diag}(\mathbf{u})\, \mathbf{K}\, \operatorname{diag}(\mathbf{v}).

Сходимость и остановка

Сходимость итераций к решению с точностью до машинного нуля гарантирована для любой положительной матрицы \mathbf{K} [1]. На практике число необходимых итераций зависит от параметра регуляризации \varepsilon: чем он меньше, тем медленнее сходимость. Типичный критерий остановки — дивергенция Кульбака–Лейблера между текущими маргиналами и целевыми значениями, либо допустимая погрешность изменения двойственных потенциалов.

Вычислительная сложность

Каждая итерация включает два умножения матрицы \mathbf{K} (порождённой из \mathbf{C}) на вектор, что требует \mathcal{O}(n m) операций в плотном случае. Для квадратных матриц размера N сложность одной итерации составляет \mathcal{O}(N^2).

Благодаря геометрической сходимости общее количество итераций до достижения фиксированной точности слабо (логарифмически) зависит от точности, но обратно пропорционально \varepsilon. Существуют ускоренные версии:

  • Экранирование (screening) на основе \varepsilon-разреженности плана позволяет не вычислять маловероятные элементы K_{ij}, снижая сложность до \mathcal{O}(N) для одномерных задач [1].
  • Многоуровневые методы (multiscale) агрегируют опоры распределений.
  • Использование GPU позволяет эффективно векторизовать матричные умножения.

Преимущества и ограничения

Преимущества

  • Вычислительная эффективность: На много порядков быстрее точных решателей на основе симплекс-метода или методов внутренней точки.
  • Дифференцируемость: Явная зависимость выходного плана от входных распределений и матрицы стоимостей позволяет использовать алгоритм в качестве слоя нейронной сети и вычислять градиенты с помощью обратного распространения.
  • Теоретическая гарантия сходимости: Безусловная сходимость для любой положительной \mathbf{K}.
  • Разреженная структура: Энтропийная регуляризация размывает план, но одновременно позволяет аппроксимировать его разреженным, что даёт дополнительные возможности для ускорения.

Ограничения

  • Смещение оценки: Результатом является расстояние Синкхорна, а не точное расстояние Вассерштейна. Размывание (\varepsilon > 0) недопустимо в задачах, где требуется точное сопоставление.
  • Выбор \varepsilon: Малые \varepsilon замедляют сходимость и приводят к численной нестабильности; большие — к излишнему сглаживанию геометрической структуры.
  • Квадратичная сложность по памяти: Хранение матрицы \mathbf{K} требует \mathcal{O}(N^2) памяти. Для миллионов точек прямое применение невозможно без использования аппроксимаций или потоковых схем.

Современные применения в машинном обучении

Алгоритм Синкхорна стал центральным вычислительным примитивом во многих разделах ML.

Барицентры Вассерштейна
Усреднение распределений (гистограмм, изображений, графов) в смысле минимальной транспортной стоимости. Барицентр вычисляется итеративно с вложенным алгоритмом Синкхорна [1].
Перенос обучения (Domain Adaptation)
Выравнивание распределений признаков из исходного и целевого доменов путём минимизации расстояния Синкхорна между эмпирическими распределениями. Алгоритм используется в методах типа COOT и JDOT.
Генеративное моделирование
В WGAN и его вариантах расстояние Синкхорна служит стабильным и информативным сигналом для обучения генератора. Sinkhorn Autoencoder напрямую минимизирует транспортные потери в латентном пространстве.
NLP и Выравнивание текстов
Выравнивание распределений векторных представлений слов для машинного перевода без учителя, а также сравнение тематических моделей документов.
Анализ одиночных клеток и проточная цитометрия
Сравнение гистограмм маркеров клеточных популяций, траекторный анализ и выравнивание батчей данных.
Компьютерное зрение
Точное сопоставление гистограмм цвета для передачи стиля, регистрация 3D-облаков точек и нейронное отслеживание объектов.

См. также

Примечания


Литература

  • Sinkhorn, R. A relationship between arbitrary positive matrices and doubly stochastic matrices // Annals of Mathematical Statistics. — 1964. — Т. 35. — № 2. — С. 876–879.
  • Sinkhorn, R., Knopp, P. Concerning nonnegative matrices and doubly stochastic matrices // Pacific Journal of Mathematics. — 1967. — Т. 21. — № 2. — С. 343–348.
  • Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport // Advances in Neural Information Processing Systems. — 2013. — Т. 26. — С. 2292–2300.
  • Peyré, G., Cuturi, M. Computational Optimal Transport: With Applications to Data Science. — Now Publishers, 2019. — T. 11. — (Foundations and Trends in Machine Learning).
  • Altschuler, J., Weed, J., Rigollet, P. Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration // Advances in Neural Information Processing Systems. — 2017. — Т. 30. — С. 1964–1974.
  • Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L., Peyré, G. Iterative Bregman projections for regularized transportation problems // SIAM Journal on Scientific Computing. — 2015. — Т. 37. — № 2. — С. A1111–A1138.
Источник — «http://recognition.su/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A1%D0%B8%D0%BD%D0%BA%D1%85%D0%BE%D1%80%D0%BD%D0%B0»
Личные инструменты