Оптимальный транспорт и связанные с ним вопросы машинного обучения: (2) вычислительные методы

В последнее время многие друзья спрашивали меня о методе расчета, связанном с оптимальной транспортной теорией (Оптимальный транспорт).Так случилось, что я также недавно пишу свою дипломную работу.В качестве основной темы моей докторской дипломной работы я кратко представлю ее.Правильная поза для прыжка в ямуХорошо. Я считаю, что каждый может знать некоторые основные вещи, такие как его определение и возможные применения. В некотором смысле небольшая кульминация ОТ в области машинного обучения очень похожа на предыдущую разработку метода ядра в области машинного обучения.Некоторые красивые свойства можно вывести математически, а некоторые сценарии посадки можно найти на практике (инструмент орошения ).

Эта статья — вторая в этом цикле (планирую написать три-четыре, еще несколько, включая первую, будут выходить последовательно). В первой статье будет предварительное введение, рассказ о предыстории и слухах о проблеме, а заинтересованные студенты могут посмотреть мой предыдущий ответ Zhihu:Знание пользователя: Какая модель лучше для схожести (расстояния) распределения?Вторая и эта будут посвящены его текущим ведущим вычислительным методам, а третья и четвертая статьи могут рассказать о его применении в машинном обучении.

Вообще проблема вот в чем:

Как очень классическая задача линейного программирования, существующие алгоритмы линейного программирования позволяют относительно быстро решать небольшие задачи. Но если вы хотите использовать его в области машинного обучения, есть еще две основные вычислительные проблемы:

еслиНасколько оно большое? Вычислительный масштаб задачи решения ЛП составляет $O(m_1m_2(m_1+m_2)\log (\max\{m_1,m_2\}))$ [Orlin, 1993]
Что, если нужно решить не одну, а большое количество различных задач ОТ одновременно?

В настоящее время необходимы некоторые приближенные методы расчета, которые можно использовать в $O(n^2/\varepsilon^q)$ время вычислить $\varepsilon$ -гарантийное решение.

Entropic Regularization and Sinkhorn algorithm

Несомненно, одним из наиболее популярных методов является использование энтропийной регуляризации для превращения задачи в сильно выпуклую аппроксимацию и использование для ее решения алгоритма Синкхорна. Проще говоря, это решение следующих задач:

здесь H(Z) является функцией энтропии. [Cuturi, 2013] предложил использовать итерацию Синкхорна для решения вышеуказанной проблемы:

Если быть точным, у Синкхорна есть две стратегии реализации: одна — итерация в пространстве журнала (то есть, как показано на рисунке выше), другая — итерация напрямую. $u=\exp(\mathbf x),v=\exp(\mathbf y)$ . Вообще говоря, последняя реализация более эффективна в вычислительном отношении. Итак, какие теоретические гарантии есть у алгоритма Синкхорна? В недавней статье [Альтшулер и др., 2017] был получен хороший результат, если $A=\exp(\eta M)$ ,и $U_{r,c}=\Pi(\mathbf p, \mathbf q)$ , Синкхорн может быть $O((\varepsilon')^2)(\log n + \eta \|M\|_{\infty})$ количество итераций для получения приближенного решения $\hat Z$ сделать

$\langle \hat Z, M\rangle \le \min_{Z\in \Pi(\mathbf p, \mathbf q)}\langle Z, M\rangle + \frac{2 \log n}{\eta} + 4\varepsilon'\|M\|_{\infty},$

$\|r(\hat Z) -\mathbf p\|_1 +\|c(\hat Z) - \mathbf q\|_1<\varepsilon'.$

[Альтшулер и др., 2017] далее заявляют, что при любом произвольном $\varepsilon$ Просто выберите подходящий $\eta,\varepsilon'$ , мы можем $O(m_1m_2/\varepsilon^3)$ временная (почти линейная) генерация $\varepsilon$ -guarantee in objective, $\varepsilon^2$ Решение для -гарантии в ограничениях. Однако у синкхорна есть две основные проблемы, которые мешают добиться таких характеристик в реальности:

когда $\eta^{-1}$ Когда алгоритм очень мал, он может легко превысить точность вычислений с плавающей запятой после нескольких итераций (намного меньше, чем требует теоретическая граница).
существует $\eta^{-1}$ Когда количество итераций относительно велико, а количество итераций относительно мало, хотя решение Синкхорна линейно сходится к гладкой аппроксимации (уравнение (3.5)), влияние аппроксимации на исходную целевую функцию задачи (уравнение (3.1) ) очень плохо.

Эти два вопроса более подробно обсуждаются в моей статье TSP [Ye et al., 2017].

Связанная литература:

Cuturi, Marco. "Sinkhorn distances: Lightspeed computation of optimal transport." Advances in neural information processing systems. 2013.

Altschuler, Jason, Jonathan Weed, and Philippe Rigollet. "Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration." Advances in Neural Information Processing Systems. 2017.

Bregman ADMM

Существует также менее известный метод аппроксимации ОТ, который, насколько мне известно, был впервые предложен [Wang, Banerjee, 2014]. Однако, поскольку сама статья не является литературой, обслуживающей в основном ОТ, а теоретические результаты доказательства носят относительно общий (сложный) характер, она редко упоминается. Основная идея метода аналогична классическому ADMM, Во-первых, исходная задача записывается как эквивалентная задача следующим образом:

$\min_{\substack{r(Z_1)=\mathbf p\\ c(Z_2) = \mathbf q}} \langle Z_1, M\rangle \mbox{ s.t. } Z_1 = Z_2.$

Затем выполните метод множителя для последнего ограничения равенства:

$\begin{eqnarray*} Z_1&:=&\mbox{argmin}_{r(Z_1) = \mathbf p} \langle Z_1, M \rangle + \langle \Lambda, Z_1 \rangle + \underbrace{\rho \cdot \mbox{KL}(Z_1, Z_2)}_{\text{replace $|\cdot|^2$ with $B_{\Phi}(\cdot,\cdot)$}}\\ Z_2&:=&\mbox{argmin}_{c(Z_2)=\mathbf q} -\langle \Lambda, Z_2\rangle + \rho \cdot \mbox{KL}(Z_2, Z_1)\\ \Lambda &:= &\Lambda + \rho (Z_1 - Z_2) \end{eqnarray*}$

Итак, получаем следующий алгоритм:

Этот метод также является теоретически связанным, в частности, мы определяем $D(W^\ast ,W^t) = \mbox{KL}(Z^\ast, Z_2^t) + \dfrac{1}{\rho^2} \|\Lambda^\ast - \Lambda^t\|^2$ тогда у нас есть

$\langle \bar{Z}_1^T, M\rangle - \langle Z^\ast, M\rangle \le \frac{\rho \mbox{KL}(Z^\ast, Z_2^0)}{T},$

а также

$\|\bar{Z}_1^T - \bar{Z}_2^T\|_1 \le \sqrt{m_1m_2} \|\bar{Z}_1^T - \bar{Z}_2^T\|_2\le \sqrt{\dfrac{2D(W^\ast, W^0)m_1m_2}{T}}$

в $\bar{Z_j}^T=\frac{1}{T}\sum_{t=1}^T Z_j^t, j=1,2$ .

Связанная литература:

Wang, Huahua, and Arindam Banerjee. "Bregman alternating direction method of multipliers." Advances in Neural Information Processing Systems. 2014.

Сравнение двух методов

Можно видеть, что при одинаковом количестве итераций мы можем эффективно сравнивать скорость сходимости двух методов.

В следующей таблице кратко представлены результаты

Теоретически в $\sqrt{m_1m_2} \ll T$ В случае , просто выберите соответствующий $\rho$ Можно получить более быстрое сходящееся решение для аппроксимации исходной целевой функции (уравнение (1.3)), но это решение с меньшей вероятностью удовлетворяет ограничениям, чем решение Синкхорна . [Ye et al. 2017] подробно сравнивает два метода, и теоретические объяснения соответствуют экспериментальным результатам в этой статье. Стоит отметить, что в большинстве приложений машинного обучения нет необходимости строго удовлетворять двум предельным ограничениям, но необходимо иметь разумный метод для аппроксимации целевой функции. Следующий рисунок, который много раз публиковался в моих прошлых докладах, представляет собой игрушечный пример, который интуитивно сравнивает характеристики сходимости.

В дополнение к Sinkhorn и B-ADMM существуют и другие методы аппроксимации, например, в моей прошлогодней статье на ICML для аппроксимации решения OT использовался метод Sampling, с акцентом на ситуацию теплого старта в оптимизации OT. В этом году в заявке ICML также использовался метод проксимальной точки для решения OT.

Соответствующий код:

bobye/OT_demo

Связанная литература:

Ye, Jianbo, et al. "Fast discrete distribution clustering using Wasserstein barycenter with sparse support." IEEE Transactions on Signal Processing 65.9 (2017): 2317-2332.

Ye, Jianbo, James Z. Wang, and Jia Li. "A Simulated Annealing Based Inexact Oracle for Wasserstein Loss Minimization." International Conference on Machine Learning. 2017.

Xie, Yujia, et al. "A Fast Proximal Point Method for Wasserstein Distance." arXiv preprint arXiv:1802.04307(2018).

От ОТ до барицентра Вассерштейна

По сравнению с решением одной задачи OT, барицентр Вассерштейна (WBC) объединяет несколько задач OT вместе, что очень часто встречается в задачах машинного обучения, в которых расстояние Вассерштейна используется в качестве функции потерь. В задаче WBC просто задан набор распределений и найдены их центры:

$\min_{P} \frac{1}{N} \sum_{k=1}^{N} W^2 ( P,P^{( k )} )$

В рамках Sinkhorn или B-ADMM эта классическая задача может быть эффективно решена. В рамках Sinkhorn [Benamou et al., 2015] предложил итеративную проекцию Брегмана для решения WBC, а в рамках B-ADMM [Ye et al. 2017] предложил использовать метод WBC для решения аналогичных K-средних в пространстве Вассерштейна.

Соответствующий код:

bobye/WBC_Matlab

Связанная литература:

Ye, Jianbo, et al. "Fast discrete distribution clustering using Wasserstein barycenter with sparse support." IEEE Transactions on Signal Processing 65.9 (2017): 2317-2332.

Benamou, Jean-David, et al. "Iterative Bregman projections for regularized transportation problems." SIAM Journal on Scientific Computing 37.2 (2015): A1111-A1138.