Дивергенция Синкхорна

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

(Различия между версиями)

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

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

Дивергенция Синкхорна — мера различия между вероятностными распределениями, основанная на энтропийно-регуляризованном оптимальном транспорте. Предложена в 2018 году как симметричная и неотрицательная поправка к синкхорновому расстоянию, которая устраняет энтропийное смещение и восстанавливает аксиому тождества. За счёт гладкости и эффективной вычислимости на графических процессорах дивергенция Синкхорна стала популярным инструментом в задачах генеративного моделирования, переноса стиля и сравнения эмпирических распределений.

Содержание

1 Интуитивная мотивация
2 Энтропийно-регуляризованный оптимальный транспорт
3 Формула дивергенции Синкхорна
4 Основные свойства
5 Алгоритм Синкхорна
6 Преимущества и ограничения
7 Применения в машинном обучении
8 Сравнение с расстоянием Васерштейна
9 См. также
10 Примечания

Интуитивная мотивация

Сравнение двух вероятностных распределений $\mu$ и $\nu$ часто сводится к вычислению расстояния Васерштейна — минимальной стоимости перемещения массы из $\mu$ в $\nu$ при заданной функции затрат $c(x,y)$ . В дискретном случае, когда распределения представлены гистограммами с весами $a \in \mathbb{R}^n_+$ и $b \in \mathbb{R}^m_+$ , задача оптимального транспорта формулируется как линейное программирование:

$\mathrm{OT}(\mu,\nu) = \min_{P \in \Pi(a,b)} \langle C, P \rangle,$

где $C_{ij} = c(x_i,y_j)$ , $\Pi(a,b) = \{ P \in \mathbb{R}^{n \times m}_+ : P \mathbf{1}_m = a,\; P^\top \mathbf{1}_n = b \}$ — множество транспортных планов. Точное решение обладает кубической сложностью и не является дифференцируемым по входным данным, что ограничивает его применение в глубоком обучении.

В 2013 году М. Кутури предложил добавить энтропийную регуляризацию и решать получившуюся задачу быстрым алгоритмом Синкхорна — итеративным масштабированием строк и столбцов матрицы Гиббса $K = \exp(-C/\varepsilon)$ . Полученная величина $\mathrm{OT}_\varepsilon(\mu,\nu)$ (синкхорново расстояние) вычислительно эффективна и дифференцируема, однако она не равна нулю при $\mu = \nu$ из-за энтропийного смещения. Чтобы получить полноценную дивергенцию, из неё вычитают симметризующие члены — так возникает дивергенция Синкхорна.

Энтропийно-регуляризованный оптимальный транспорт

Для дискретных мер $\mu = \sum_{i=1}^n a_i \delta_{x_i}$ , $\nu = \sum_{j=1}^m b_j \delta_{y_j}$ с векторами весов $a \in \Delta_n$ , $b \in \Delta_m$ (где $\Delta_k$ — вероятностный симплекс) энтропийно-регуляризованная стоимость транспортировки с параметром $\varepsilon > 0$ определяется как

$\mathrm{OT}_\varepsilon(\mu,\nu) = \min_{P \in \Pi(a,b)} \langle C, P \rangle + \varepsilon\, \mathrm{KL}(P \| a b^\top),$

где $\mathrm{KL}(P \| Q) = \sum_{i,j} P_{ij} \log \frac{P_{ij}}{Q_{ij}} - P_{ij} + Q_{ij}$ — дивергенция Кульбака-Лейблера, а $a b^\top$ — независимое произведение мер. Добавка энтропийного штрафа делает задачу строго выпуклой и разрешает явное решение в виде

$P^\star_{ij} = u_i K_{ij} v_j, \quad K_{ij} = e^{-C_{ij}/\varepsilon},$

где неотрицательные векторы $u \in \mathbb{R}^n_+$ , $v \in \mathbb{R}^m_+$ однозначно находятся из условий на маргиналы $P^\star \mathbf{1}_m = a$ , $(P^\star)^\top \mathbf{1}_n = b$ .

Формула дивергенции Синкхорна

Дивергенция Синкхорна $S_\varepsilon$ между мерами $\mu$ и $\nu$ вводится как симметризованная версия $\mathrm{OT}_\varepsilon$ :

$S_\varepsilon(\mu,\nu) = \mathrm{OT}_\varepsilon(\mu,\nu) - \frac{1}{2}\mathrm{OT}_\varepsilon(\mu,\mu) - \frac{1}{2}\mathrm{OT}_\varepsilon(\nu,\nu).$

Такая конструкция аналогична поправке на смещение, используемой в максимальном среднем расхождении (MMD), и гарантирует выполнение свойства $S_\varepsilon(\mu,\mu) = 0$ . Более того, дивергенция симметрична и неотрицательна:

$S_\varepsilon(\mu,\nu) \ge 0, \qquad S_\varepsilon(\mu,\nu) = 0 \iff \mu = \nu.$

Через двойственную задачу $\mathrm{OT}_\varepsilon$ можно выразить дивергенцию в виде, напоминающем MMD, но с оптимально подобранными потенциалами:

$S_\varepsilon(\mu,\nu) = \sup_{f,g \in \mathcal{C}} \langle f, \mu \rangle + \langle g, \nu \rangle - \varepsilon\!\int\! e^{(f(x)+g(y)-c(x,y))/\varepsilon} d\mu(x)d\nu(y) - \frac{1}{2}(\dots),$

где поправки на $\mu,\mu$ и $\nu,\nu$ выписаны аналогично.

Основные свойства

Неотрицательность и аксиома тождества — вытекают из построения.
Симметричность — $S_\varepsilon(\mu,\nu) = S_\varepsilon(\nu,\mu)$ .
Интерполяция между расстоянием Васерштейна и энергетическим расстоянием:

   — расстояние Васерштейна с функцией затрат ;
   — энергетическое расстояние, совпадающее с  для условно-отрицательно определённого ядра .

Гладкость — при $\varepsilon > 0$ функция $S_\varepsilon$ бесконечно дифференцируема по параметрам распределений; градиенты выражаются через потенциалы Синкхорна и допускают эффективное вычисление обратным распространением через итерации алгоритма.
Выборочная сложность — оценка дивергенции по $n$ независимым наблюдениям сходится со скоростью $O(n^{-1/2})$ независимо от размерности пространства, в отличие от экспоненциальной деградации для точного расстояния Васерштейна.
Связь с задачей Шрёдингера — оптимальный план $P^\star$ является решением статической формулировки задачи Шрёдингера с эталонной мерой $K_{ij}$ .

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

Вычисление $\mathrm{OT}_\varepsilon$ и, как следствие, $S_\varepsilon$ выполняется алгоритмом Синкхорна — итеративным масштабированием строк и столбцов матрицы $K$ . Исходя из условий $u \odot (K v) = a$ и $v \odot (K^\top u) = b$ , вектор $v$ инициализируют единицами и повторяют:

$u^{(t+1)} = \frac{a}{K v^{(t)}}, \qquad v^{(t+1)} = \frac{b}{K^\top u^{(t+1)}},$

где деление поэлементное. При использовании логарифмического суммирования (log-sum-exp) метод устойчив даже для малых $\varepsilon$ . После сходимости (обычно за $L \sim 100{-}1000$ итераций) план восстанавливается как $P = \operatorname{diag}(u) K \operatorname{diag}(v)$ , а регуляризованная стоимость —

$\mathrm{OT}_\varepsilon = \langle a, \log u \rangle + \langle b, \log v \rangle + \varepsilon\bigl(\sum a_i \log a_i + \sum b_j \log b_j - 1\bigr) + \text{const}.$

Для дивергенции Синкхорна дополнительно вычисляют $\mathrm{OT}_\varepsilon(\mu,\mu)$ и $\mathrm{OT}_\varepsilon(\nu,\nu)$ , запуская алгоритм Синкхорна для пары распределений с самим собой. Сложность одного вычисления составляет $O(L n^2)$ , где $n = \max(|\mu|, |\nu|)$ . На графических процессорах матричные умножения выполняются параллельно, что делает метод применимым к выборкам среднего размера ( $10^4{-}10^5$ точек) в градиентном обучении.

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

Преимущества	Ограничения
Дифференцируемость и совместимость с автоматическим дифференцированием	Не является метрикой: отсутствует неравенство треугольника
Эффективное вычисление на GPU, масштабируемость	Введение энтропийного размытия, сглаживающего мелкие детали распределений
Статистическая сходимость со скоростью $O(1/\sqrt{n})$ без «проклятия размерности»	Необходимость выбора параметра $\varepsilon$ , компромисс между точностью и скоростью
Устранение энтропийного смещения синкхорнова расстояния	Квадратичная память $O(n^2)$ ограничивает применение на миллионах точек
Хорошая геометрия ландшафта потерь в генеративных моделях	При слишком малом $\varepsilon$ итерации Синкхорна могут сходиться медленно

Применения в машинном обучении

Генеративные модели — Sinkhorn GAN и Sinkhorn Autoencoder используют дивергенцию Синкхорна в качестве гладкой и устойчивой функции потерь для обучения порождающих сетей.
Перенос стиля и цвета — регуляризованный транспорт позволяет передавать цветовые распределения между изображениями с сохранением структуры.
Одноклеточная геномика — сравнение профилей экспрессии генов, вычисление барицентров популяций клеток.
Сопоставление представлений — оценка близости между эмбеддингами слов, предложений или графовых представлений.
Градиентные потоки и барицентры — построение интерполирующих распределений и решение вариационных задач на пространстве мер.

Сравнение с расстоянием Васерштейна

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

Метрические свойства: расстояние Васерштейна является метрикой (удовлетворяет неравенству треугольника), тогда как дивергенция Синкхорна — нет.
Гладкость: $S_\varepsilon$ всюду дифференцируема по параметрам распределений, что позволяет использовать её как дифференцируемый критерий качества; точное расстояние Васерштейна недифференцируемо и требует субградиентных методов.
Вычислительная сложность: точное расстояние Васерштейна для дискретных распределений решается венгерским алгоритмом или симплекс-методом с трудоёмкостью $O(n^3 \log n)$ ; дивергенция Синкхорна вычисляется за $O(L n^2)$ и легко параллелизуется.
Сходимость эмпирических оценок: эмпирическое расстояние Васерштейна сходится к истинному со скоростью $O(n^{-1/d})$ , где $d$ — размерность пространства (проклятие размерности); для дивергенции Синкхорна скорость $O(n^{-1/2})$ не зависит от размерности.
Энтропийное смещение: синкхорново расстояние $\mathrm{OT}_\varepsilon$ даёт смещённую оценку, $S_\varepsilon$ поправляет это смещение, сохраняя вычислительные преимущества, тогда как расстояние Васерштейна не содержит систематической ошибки, но лишено гладкости.

Благодаря этим качествам дивергенция Синкхорна особенно удобна в задачах, где требуется быстрый и дифференцируемый сигнал сходимости, например при обучении глубоких генеративных сетей, в то время как точное расстояние Васерштейна остаётся предпочтительным, когда первостепенны строгие метрические свойства и отсутствие размытия.

См. также

Примечания

Cuturi M. Sinkhorn Distances: Lightspeed Computation of Optimal Transport // Advances in Neural Information Processing Systems. — 2013. — Т. 26. — С. 2292–2300. Genevay A., Peyré G., Cuturi M. Learning Generative Models with Sinkhorn Divergences // Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS). — 2018. — Т. 84. — С. 1608–1617. Genevay A., Chizat L., Bach F., Cuturi M., Peyré G. Sample Complexity of Sinkhorn Divergences // Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS). — 2019. — Т. 89. — С. 1574–1583. Peyré G., Cuturi M. Computational Optimal Transport. — Now Publishers, 2019.

Источник — «http://recognition.su/wiki/index.php?title=%D0%94%D0%B8%D0%B2%D0%B5%D1%80%D0%B3%D0%B5%D0%BD%D1%86%D0%B8%D1%8F_%D0%A1%D0%B8%D0%BD%D0%BA%D1%85%D0%BE%D1%80%D0%BD%D0%B0»

Категории: Машинное обучение | Теория вероятностей | Оптимальный транспорт | Дивергенции (статистика)

@@ Строка 2: / Строка 2: @@
-'''Дивергенция Синкхорна''' — мера различия между вероятностными распределениями, основанная на энтропийно-регуляризованном [[оптимальный транспорт|оптимальном транспорте]]. Предложена в 2018 году как симметричная и неотрицательная поправка к синкхорновому расстоянию, которая устраняет энтропийное смещение и восстанавливает аксиому тождества. За счёт гладкости и эффективной вычислимости на [[Графический процессор|графических процессорах]] дивергенция Синкхорна стала популярным инструментом в задачах [[Генеративная модель|генеративного моделирования]], переноса стиля и сравнения эмпирических распределений.
+'''Дивергенция Синкхорна''' — мера различия между вероятностными распределениями, основанная на энтропийно-регуляризованном [[оптимальный транспорт|оптимальном транспорте]]. Предложена в 2018 году как симметричная и неотрицательная поправка к синкхорновому расстоянию, которая устраняет энтропийное смещение и восстанавливает аксиому тождества. За счёт гладкости и эффективной вычислимости на графических процессорах дивергенция Синкхорна стала популярным инструментом в задачах [[Генеративная модель|генеративного моделирования]], переноса стиля и сравнения эмпирических распределений.
 == Интуитивная мотивация ==
-Сравнение двух [[вероятностное распределение|вероятностных распределений]] <tex>\mu</tex> и <tex>\nu</tex> часто сводится к вычислению [[расстояние Васерштейна|расстояния Васерштейна]] — минимальной стоимости перемещения массы из <tex>\mu</tex> в <tex>\nu</tex> при заданной функции затрат <tex>c(x,y)</tex>. В дискретном случае, когда распределения представлены [[гистограмма|гистограммами]] с весами <tex>a \in \mathbb{R}^n_+</tex> и <tex>b \in \mathbb{R}^m_+</tex>, задача оптимального транспорта формулируется как [[линейное программирование]]:
+Сравнение двух [[вероятностное распределение|вероятностных распределений]] <tex>\mu</tex> и <tex>\nu</tex> часто сводится к вычислению [[расстояние Васерштейна|расстояния Васерштейна]] — минимальной стоимости перемещения массы из <tex>\mu</tex> в <tex>\nu</tex> при заданной функции затрат <tex>c(x,y)</tex>. В дискретном случае, когда распределения представлены гистограммами с весами <tex>a \in \mathbb{R}^n_+</tex> и <tex>b \in \mathbb{R}^m_+</tex>, задача оптимального транспорта формулируется как [[линейное программирование]]:
 <tex>\mathrm{OT}(\mu,\nu) = \min_{P \in \Pi(a,b)} \langle C, P \rangle,</tex>
@@ Строка 18: / Строка 18: @@
 <tex>\mathrm{OT}_\varepsilon(\mu,\nu) = \min_{P \in \Pi(a,b)} \langle C, P \rangle + \varepsilon\, \mathrm{KL}(P \| a b^\top),</tex>
-где <tex>\mathrm{KL}(P \| Q) = \sum_{i,j} P_{ij} \log \frac{P_{ij}}{Q_{ij}} - P_{ij} + Q_{ij}</tex> — [[расстояние Кульбака — Лейблера|дивергенция Кульбака — Лейблера]], а <tex>a b^\top</tex> — независимое произведение мер. Добавка энтропийного штрафа делает задачу строго выпуклой и разрешает явное решение в виде
+где <tex>\mathrm{KL}(P \| Q) = \sum_{i,j} P_{ij} \log \frac{P_{ij}}{Q_{ij}} - P_{ij} + Q_{ij}</tex> — [[дивергенция Кульбака-Лейблера]], а <tex>a b^\top</tex> — независимое произведение мер. Добавка энтропийного штрафа делает задачу строго выпуклой и разрешает явное решение в виде
 <tex>P^\star_{ij} = u_i K_{ij} v_j, \quad K_{ij} = e^{-C_{ij}/\varepsilon},</tex>
@@ Строка 43: / Строка 43: @@
 * '''Симметричность''' — <tex>S_\varepsilon(\mu,\nu) = S_\varepsilon(\nu,\mu)</tex>.
 * '''Интерполяция между расстоянием Васерштейна и энергетическим расстоянием''':
-  : <tex>\lim_{\varepsilon \to 0} S_\varepsilon(\mu,\nu) = W_c(\mu,\nu)</tex> — [[расстояние Васерштейна]] с функцией затрат <tex>c</tex>;
+   <tex>\lim_{\varepsilon \to 0} S_\varepsilon(\mu,\nu) = W_c(\mu,\nu)</tex> — [[расстояние Васерштейна]] с функцией затрат <tex>c</tex>;
-  : <tex>\lim_{\varepsilon \to \infty} S_\varepsilon(\mu,\nu) = \mathbb{E}_{X,Y}[c(X,Y)] - \tfrac{1}{2}\mathbb{E}[c(X,X')] - \tfrac{1}{2}\mathbb{E}[c(Y,Y')]</tex> — [[энергетическое расстояние]], совпадающее с <tex>\tfrac{1}{2}\mathrm{MMD}^2_{-c}(\mu,\nu)</tex> для условно-отрицательно определённого ядра <tex>-c</tex>.
+   <tex>\lim_{\varepsilon \to \infty} S_\varepsilon(\mu,\nu) = \mathbb{E}_{X,Y}[c(X,Y)] - \tfrac{1}{2}\mathbb{E}[c(X,X')] - \tfrac{1}{2}\mathbb{E}[c(Y,Y')]</tex> — [[энергетическое расстояние]], совпадающее с <tex>\tfrac{1}{2}\mathrm{MMD}^2_{-c}(\mu,\nu)</tex> для условно-отрицательно определённого ядра <tex>-c</tex>.
 * '''Гладкость''' — при <tex>\varepsilon > 0</tex> функция <tex>S_\varepsilon</tex> бесконечно дифференцируема по параметрам распределений; градиенты выражаются через потенциалы Синкхорна и допускают эффективное вычисление [[обратное распространение ошибки|обратным распространением]] через итерации алгоритма.
 * '''Выборочная сложность''' — оценка дивергенции по <tex>n</tex> независимым наблюдениям сходится со скоростью <tex>O(n^{-1/2})</tex> независимо от размерности пространства, в отличие от экспоненциальной деградации для точного расстояния Васерштейна.
-* '''Связь с задачей Шрёдингера''' — оптимальный план <tex>P^\star</tex> является решением статической формулировки [[уравнение Шрёдингера (статистическая физика)|задачи Шрёдингера]] с эталонной мерой <tex>K_{ij}</tex>.
+* '''Связь с задачей Шрёдингера''' — оптимальный план <tex>P^\star</tex> является решением статической формулировки задачи Шрёдингера с эталонной мерой <tex>K_{ij}</tex>.
 == Алгоритм Синкхорна ==
@@ Строка 98: / Строка 98: @@
 * [[Метод максимального среднего расхождения]]
 * [[Алгоритм Синкхорна]]
-* [[Ядерные методы]]
-* [[Уравнение Шрёдингера (статистическая физика)]]
 == Примечания ==