Введение
Задача оптимального транспорта (Optimal Transport Problem) — это математическая задача, которая задает вопрос, «как переместить материал с минимальными усилиями» при перемещении вещества (например, кучи песка) из одного места в другое (например, в яму).
Она была поставлена французским математиком Гаспаром Монжем в 18 веке, а современная формулировка была предложена Леонидом Канторовичем в 20 веке. Сегодня она широко применяется в областях от распределения ресурсов в экономике до машинного обучения.
Формулировка задачи Монжа
То, что рассматривал Монж, было очень интуитивной задачей. Представьте, что в одном месте есть куча песка, а в другом — яма такого же объема. Думая о задаче по перемещению песка для заполнения ямы, мы хотим минимизировать «стоимость» транспортировки песка.
Стоимость обычно представляется как произведение «количества перемещенного песка» на «пройденное расстояние».
flowchart LR
A["Куча песка (Предложение)"] -->|"Транспортировка"| B["Яма (Спрос)"]
C["Место x"] -->|"Расстояние d(x, y)"| D["Место y"]
С точки зрения математики, пусть распределение исходной кучи песка будет вероятностной мерой \(\mu\) на \(X\), а распределение ямы — вероятностной мерой \(\nu\) на \(Y\). Пусть \(T: X \to Y\) будет отображением (функцией), которое определяет пункт назначения для каждого места \(x \in X\) в \(y \in Y\). Это \(T\) должно перемещать (передвигать) \(\mu\) в \(\nu\). То есть \(T_{\#}\mu = \nu\).
Предполагая, что функция стоимости, связанная с перемещением, равна \(c(x, y)\), задача оптимального транспорта Монжа состоит в том, чтобы найти такое отображение \(T\), которое минимизирует следующую общую стоимость.
\[ \inf_{T_{\#}\mu = \nu} \int_X c(x, T(x)) d\mu(x) \]Однако с этой формулировкой была проблема. Например, ситуация, когда песок в одной точке кучи песка разделяется и перевозится в несколько ям, не могла быть выражена с помощью отображения \(T\).
Ослабление Канторовича
Именно Канторович решил эту проблему. Он рассмотрел транспортный план (Transport Plan), который представляет собой «какое количество выделить» из каждого места \(x\) в \(y\).
Пусть транспортный план будет совместной вероятностной мерой \(\pi\) на \(X \times Y\). Здесь мы налагаем условие, что маргинальные распределения \(\pi\) равны \(\mu\) и \(\nu\) соответственно. Это множество обозначается как \(\Pi(\mu, \nu)\).
flowchart TD
subgraph "Сторона Предложения"
X1["Место x_1"]
X2["Место x_2"]
end
subgraph "Сторона Спроса"
Y1["Место y_1"]
Y2["Место y_2"]
end
X1 -->|"Объем транспортировки π(x_1, y_1)"| Y1
X1 -->|"Объем транспортировки π(x_1, y_2)"| Y2
X2 -->|"Объем транспортировки π(x_2, y_1)"| Y1
X2 -->|"Объем транспортировки π(x_2, y_2)"| Y2
Задача оптимального транспорта Канторовича состоит в том, чтобы найти совместное распределение \(\pi\), которое минимизирует следующую общую стоимость.
\[ \inf_{\pi \in \Pi(\mu, \nu)} \int_{X \times Y} c(x, y) d\pi(x, y) \]С такой формулировкой разделение и транспортировка песка были разрешены, и математическая обработка стала намного проще. Кроме того, поскольку эта задача может быть сформулирована как задача линейного программирования, стал возможным мощный анализ с использованием двойственности.
Расстояние Вассерштейна
Когда в качестве функции стоимости \(c(x, y)\) выбирается \(p\)-я степень расстояния в метрическом пространстве, а именно \(d(x, y)^p\), \(1/p\)-я степень оптимальной стоимости транспорта становится индексом для измерения расстояния между распределениями вероятностей. Это называется расстоянием Вассерштейна (Wasserstein Distance).
\[ W_p(\mu, \nu) = \left( \inf_{\pi \in \Pi(\mu, \nu)} \int_{X \times Y} d(x, y)^p d\pi(x, y) \right)^{1/p} \]В частности, когда \(p=1\), оно также называется Earth Mover’s Distance (EMD) и широко используется как интуитивно понятное расстояние между распределениями в областях обработки изображений и машинного обучения.
Преимущества расстояния Вассерштейна
По сравнению с другими метриками между распределениями, такими как дивергенция Кульбака-Лейблера (KL дивергенция), расстояние Вассерштейна имеет большое преимущество.
А именно, «даже если распределения вообще не перекрываются, их расстояние можно измерить как значимое значение». Например, когда два набора точек находятся далеко друг от друга в пространстве, дивергенция KL стремится к бесконечности, в то время как расстояние Вассерштейна напрямую отражает геометрическое расстояние между наборами точек.
Применение в машинном обучении
В последние годы теория оптимального транспорта привлекла большое внимание в области машинного обучения, особенно в генеративных моделях. Ярким примером является Wasserstein GAN (WGAN).
За счет минимизации расстояния Вассерштейна между распределением данных, созданным генератором, и фактическим распределением данных стало возможным более стабильное обучение, а качество генерируемых изображений резко улучшилось.
Задача оптимального транспорта началась с чистых математических исследований и теперь стала мощным инструментом поддержки науки о данных. Эта интуитивно понятная идея измерения «разницы» между распределениями, вероятно, будет продолжать применяться в различных областях и в будущем.