метрика Вассерштейна

В математике расстояние Вассерштейна или метрика Канторовича – Рубинштейна – это функция расстояния, определённая между распределениями вероятностей на заданном метрическом пространстве . Она названа в честь Леонида Васерштейна . ${\displaystyle М}$

Интуитивно, если каждое распределение рассматривать как единицу количества земли (почвы), сложенной на , метрика представляет собой минимальную «стоимость» превращения одной кучи в другую, которая, как предполагается, равна количеству земли, которое необходимо переместить, умноженному на среднее расстояние, на которое ее необходимо переместить. Эта задача была впервые формализована Гаспаром Монжем в 1781 году. Из-за этой аналогии метрика известна в информатике как расстояние землекопа .${\displaystyle М}$

Название «расстояние Вассерштейна» было придумано Р. Л. Добрушиным в 1970 году после того, как он узнал о нем из работы Леонида Васерштейна о марковских процессах, описывающих большие системы автоматов ^[1] (русский, 1969). Однако впервые метрика была определена Леонидом Канторовичем в «Математическом методе планирования и организации производства» ^[2] (русский оригинал 1939) в контексте оптимального планирования перевозок товаров и материалов. Некоторые ученые поэтому поощряют использование терминов «метрика Канторовича» и «расстояние Канторовича». Большинство англоязычных публикаций используют немецкое написание «Wasserstein» (приписывается фамилии «Васерштейн» (русский: Васерштейн ), которая имеет идишское происхождение).

Пусть будет метрическим пространством , которое является польским пространством . Для , расстояние Вассерштейна между двумя вероятностными мерами и на с конечными - моментами равно , где - множество всех связей и ; определяется как и соответствует супремум-норме . Здесь связь - это совместная вероятностная мера на которой маргиналы и на первом и втором факторах соответственно. Это означает, что для всех измеримых она удовлетворяет и .${\displaystyle (М,д)}$${\displaystyle p\in [1,+\infty]}$${\displaystyle p}$ ${\displaystyle \мю}$${\displaystyle \nu}$${\displaystyle М}$${\displaystyle p}$${\displaystyle W_{p}(\mu,\nu)=\inf _{\gamma \in \Gamma (\mu,\nu)}\left(\mathbf {E} _{(x,y)\sim \гамма }d(x,y)^{p}\right)^{1/p},}$${\displaystyle \Gamma (\mu,\nu)}$${\displaystyle \мю}$${\displaystyle \nu}$${\displaystyle W_ {\infty }(\mu,\nu)}$${\displaystyle \lim _ {p\rightarrow +\infty }W_ {p}(\mu,\nu)}$${\displaystyle \гамма}$${\displaystyle М\times М}$${\displaystyle \мю}$${\displaystyle \nu}$${\displaystyle A\подмножество M}$${\displaystyle \gamma (A\times M)=\mu (A)}$${\displaystyle \gamma (M\times A)=\nu (A)}$

Один из способов понять приведенное выше определение — рассмотреть задачу оптимальной транспортировки . То есть, для распределения массы на пространстве мы хотим переместить массу таким образом, чтобы она трансформировалась в распределение на том же пространстве; преобразуя «кучу земли» в кучу . Эта задача имеет смысл только в том случае, если создаваемая куча имеет ту же массу, что и перемещаемая куча; поэтому без потери общности предположим, что и являются распределениями вероятностей, содержащими общую массу 1. Предположим также, что задана некоторая функция стоимости${\displaystyle \мю (х)}$${\displaystyle X}$${\displaystyle \nu (x)}$${\displaystyle \мю}$${\displaystyle \nu}$${\displaystyle \мю}$${\displaystyle \nu}$

$${\displaystyle c(x,y)\geq 0}$$

что дает стоимость транспортировки единицы массы из точки в точку . План транспортировки для перемещения в можно описать функцией , которая дает количество массы для перемещения из в . Вы можете представить себе задачу как необходимость переместить кучу земли формы в яму в земле формы таким образом, чтобы в конце и куча земли, и яма в земле полностью исчезли. Для того чтобы этот план был осмысленным, он должен удовлетворять следующим свойствам:${\displaystyle x}$${\displaystyle y}$${\displaystyle \мю}$${\displaystyle \nu}$${\displaystyle \гамма (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle \мю}$${\displaystyle \nu}$

1. количество земли, перемещенной из точки, должно быть равно количеству, которое там было изначально; то есть, и${\displaystyle x}$$${\displaystyle \int \gamma (x,y)\,\mathrm {d} y=\mu (x),}$$
2. количество земли, перемещенной в точку, должно быть равно глубине ямы, которая была там в начале; то есть,${\displaystyle y}$$${\displaystyle \int \gamma (x,y)\,\mathrm {d} x=\nu (y).}$$

То есть, общая масса, перемещенная из бесконечно малой области вокруг, должна быть равна , а общая масса, перемещенная в область вокруг, должна быть . Это эквивалентно требованию, чтобы было совместным распределением вероятностей с маргиналами и . Таким образом, бесконечно малая масса, перемещенная из в , равна , а стоимость перемещения равна , следуя определению функции стоимости. Таким образом, общая стоимость плана транспортировки равна${\displaystyle x}$${\displaystyle \mu (x)\mathrm {d} x}$${\displaystyle y}$${\displaystyle \nu (y)\mathrm {d} y}$${\displaystyle \гамма}$${\displaystyle \мю}$${\displaystyle \nu}$${\displaystyle x}$${\displaystyle y}$${\displaystyle \gamma (x,y)\,\mathrm {d} x\,\mathrm {d} y}$${\displaystyle c(x,y)\gamma (x,y)\,\mathrm {d} x\,\mathrm {d} y}$${\displaystyle \гамма}$$${\displaystyle \iint c(x,y)\gamma (x,y)\,\mathrm {d} x\,\mathrm {d} y = \int c(x,y)\,\mathrm {d} \гамма (x,y).}$$

План не является уникальным; оптимальный транспортный план — это план с минимальной стоимостью из всех возможных транспортных планов. Как уже упоминалось, требование к плану, чтобы быть действительным, заключается в том, чтобы он был совместным распределением с маргиналами и ; обозначим набор всех таких мер, как в первом разделе, стоимость оптимального плана равна Если стоимость перемещения — это просто расстояние между двумя точками, то оптимальная стоимость идентична определению расстояния .${\displaystyle \гамма}$${\displaystyle \мю}$${\displaystyle \nu}$${\displaystyle \Гамма}$$${\displaystyle C=\inf _ {\gamma \in \Gamma (\mu,\nu)}\int c(x,y)\,\mathrm {d} \gamma (x,y).}$$${\displaystyle W_{1}}$

Пусть и будут двумя вырожденными распределениями (т.е. дельта-распределениями Дирака ), расположенными в точках и в . Существует только одна возможная связь этих двух мер, а именно точечная масса, расположенная в . Таким образом, используя обычную функцию абсолютного значения в качестве функции расстояния на , для любого расстояние -Вассерштейна между и равно По аналогичным рассуждениям, если и являются точечными массами, расположенными в точках и в , и мы используем обычную евклидову норму на в качестве функции расстояния, то${\displaystyle \mu _{1}=\delta _{a_{1}}}$${\displaystyle \mu _{2}=\delta _{a_{2}}}$${\displaystyle а_{1}}$${\displaystyle а_{2}}$${\displaystyle \mathbb {R} }$${\displaystyle \delta _{(a_{1},a_{2})}}$${\displaystyle (a_{1},a_{2})\in \mathbb {R} ^{2}}$${\displaystyle \mathbb {R} }$${\displaystyle p\geq 1}$${\displaystyle p}$${\displaystyle \mu _{1}}$${\displaystyle \mu _{2}}$$${\displaystyle W_{p}(\mu _{1},\mu _{2})=|a_{1}-a_{2}|.}$$${\displaystyle \mu _{1}=\delta _{a_{1}}}$${\displaystyle \mu _{2}=\delta _{a_{2}}}$${\displaystyle а_{1}}$${\displaystyle а_{2}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle \mathbb {R} ^{n}}$$${\displaystyle W_{p}(\mu _{1},\mu _{2})=\|a_{1}-a_{2}\|_{2}.}$$

Если — эмпирическая мера с выборками и — эмпирическая мера с выборками , то расстояние является простой функцией порядковой статистики :${\displaystyle P}$${\displaystyle X_{1},\ldots ,X_{n}}$${\displaystyle Q}$${\displaystyle Y_{1},\ldots ,Y_{n}}$$${\displaystyle W_{p}(P,Q)=\left({\frac {1}{n}}\sum _{i=1}^{n}\|X_{(i)}-Y_{(i)}\|^{p}\right)^{1/p}.}$$

Если и являются эмпирическими распределениями, каждое из которых основано на наблюдениях, то${\displaystyle P}$${\displaystyle Q}$${\displaystyle n}$

$${\displaystyle W_{p}(P,Q)=\inf _{\pi }\left({\frac {1}{n}}\sum _{i=1}^{n}\|X_{i}-Y_{\pi (i)}\|^{p}\right)^{1/p},}$$

где инфимум берется по всем перестановкам элементов . Это линейная задача о назначениях , и ее можно решить венгерским алгоритмом за кубическое время .${\displaystyle \пи}$${\displaystyle n}$

Пусть и будут двумя невырожденными гауссовыми мерами (т.е. нормальными распределениями ) на , с соответствующими ожидаемыми значениями и и симметричными положительно полуопределенными ковариационными матрицами и . Тогда, ^[3] относительно обычной евклидовой нормы на , расстояние Вассерштейна 2 между и равно , где обозначает главный квадратный корень из . Обратите внимание, что второй член (включающий след) является в точности (ненормализованной) метрикой Буреса между и . Этот результат обобщает более ранний пример расстояния Вассерштейна между двумя точечными массами (по крайней мере, в случае ), поскольку точечную массу можно рассматривать как нормальное распределение с ковариационной матрицей, равной нулю, в этом случае член следа исчезает и остается только член, включающий евклидово расстояние между средними.${\displaystyle \mu _{1}={\mathcal {N}}(m_{1},C_{1})}$${\displaystyle \mu _{2}={\mathcal {N}}(m_{2},C_{2})}$${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle m_{1}}$${\displaystyle m_{2}\in \mathbb {R} ^{n}}$ ${\displaystyle C_{1}}$${\displaystyle C_{2}\in \mathbb {R} ^{n\times n}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle \mu _{1}}$${\displaystyle \mu _{2}}$$${\displaystyle W_{2}(\mu _{1},\mu _{2})^{2}=\|m_{1}-m_{2}\|_{2}^{2}+\mathop {\mathrm {след} } {\bigl (}C_{1}+C_{2}-2{\bigl (}C_{2}^{1/2}C_{1}C_{2}^{1/2}{\bigr )}^{1/2}{\bigr )}.}$$${\displaystyle C^{1/2}}$${\displaystyle C}$${\displaystyle C_{1}}$${\displaystyle C_{2}}$${\displaystyle p=2}$

Пусть будут вероятностными мерами на , и обозначим их кумулятивные функции распределения через и . Тогда транспортная задача имеет аналитическое решение: Оптимальный транспорт сохраняет порядок элементов массы вероятности, поэтому масса в квантиле перемещается в квантиль . Таким образом, расстояние -Вассерштейна между и равно , где и являются функциями квантиля (обратными CDF). В случае замена переменных приводит к формуле${\displaystyle \mu _{1},\mu _{2}\in P_{p}(\mathbb {R} )}$${\displaystyle \mathbb {R} }$${\displaystyle F_{1}(x)}$${\displaystyle F_{2}(x)}$${\displaystyle q}$${\displaystyle \mu _{1}}$${\displaystyle q}$${\displaystyle \mu _{2}}$${\displaystyle p}$${\displaystyle \mu _{1}}$${\displaystyle \mu _{2}}$$${\displaystyle W_{p}(\mu _{1},\mu _{2})=\left(\int _{0}^{1}\left|F_{1}^{-1}(q)-F_{2}^{-1}(q)\right|^{p}\,\mathrm {d} q\right)^{1/p},}$$${\displaystyle F_{1}^{-1}}$${\displaystyle F_{2}^{-1}}$${\displaystyle p=1}$$${\displaystyle W_{1}(\mu _{1},\mu _{2})=\int _{\mathbb {R} }\left|F_{1}(x)-F_{2}(x)\right|\,\mathrm {d} x.}$$

Метрика Вассерштейна — это естественный способ сравнения распределений вероятностей двух переменных X и Y , где одна переменная выводится из другой посредством небольших неравномерных возмущений (случайных или детерминированных).

В информатике, например, метрика W ₁ широко используется для сравнения дискретных распределений, например, цветовых гистограмм двух цифровых изображений ; более подробную информацию см. в разделе «Расстояние землеройной машины» .

В своей статье « Вассерштейн GAN » Арджовски и др. ^[4] используют метрику Вассерштейна-1 как способ улучшения исходной структуры генеративно-состязательных сетей (GAN), чтобы смягчить проблемы исчезающего градиента и коллапса мод. Частный случай нормальных распределений используется в начальной дистанции Фреше .

Метрика Вассерштейна формально связана с анализом Прокруста , с применением к мерам хиральности ^[5] и к анализу формы ^{[6] .}

В вычислительной биологии метрика Вассерштейна может использоваться для сравнения диаграмм устойчивости наборов данных цитометрии. ^[7]

Метрика Вассерштейна также использовалась в обратных задачах геофизики. ^[8]

Метрика Вассерштейна используется в теории интегрированной информации для вычисления разницы между концепциями и концептуальными структурами. ^[9]

Метрика Вассерштейна и связанные с ней формулировки также использовались для создания единой теории для анализа наблюдаемой формы в наборах данных физики высоких энергий и коллайдеров. ^{[10] [11]}

Можно показать, что W _p удовлетворяет всем аксиомам метрики на пространстве Вассерштейна P _p ( M ) , состоящем из всех борелевских вероятностных мер на M, имеющих конечный p -й момент. Более того, сходимость относительно W _p эквивалентна обычной слабой сходимости мер плюс сходимость первых p -х моментов. ^[12]

Следующее дуальное представление W ₁ является частным случаем теоремы двойственности Канторовича и Рубинштейна (1958): когда μ и ν имеют ограниченный носитель ,

$${\displaystyle W_{1}(\mu ,\nu )=\sup \left\{\left.\int _{M}f(x)\,\mathrm {d} (\mu -\nu )(x)\,\right|{\text{ continuous }}f:M\to \mathbb {R} ,\operatorname {Lip} (f)\leq 1\right\},}$$

где Lip( f ) обозначает минимальную константу Липшица для f . Эта форма показывает, что W ₁ является интегральной вероятностной метрикой .

Сравните это с определением метрики Радона :

$${\displaystyle \rho (\mu ,\nu ):=\sup \left\{\left.\int _{M}f(x)\,\mathrm {d} (\mu -\nu )(x)\,\right|{\text{ continuous }}f:M\to [-1,1]\right\}.}$$

Если метрика d метрического пространства ( M , d ) ограничена некоторой константой C , то

$${\displaystyle 2W_{1}(\mu ,\nu )\leq C\rho (\mu ,\nu ),}$$

и поэтому сходимость в метрике Радона (идентичная сходимости по полной вариации, когда M — польское пространство ) подразумевает сходимость в метрике Вассерштейна, но не наоборот.

Ниже приведено интуитивное доказательство, которое пропускает технические моменты. Полностью строгое доказательство находится в ^{[13] .}

Дискретный случай : Когда дискретно, решение для 1-расстояния Вассерштейна является задачей линейного программирования: где — общая «функция стоимости».${\displaystyle M}$$${\displaystyle {\begin{cases}\min _{\gamma }\sum _{x,y}c(x,y)\gamma (x,y)\\\sum _{y}\gamma (x,y)=\mu (x)\\\sum _{x}\gamma (x,y)=\nu (y)\\\gamma \geq 0\end{cases}}}$$${\displaystyle c:M\times M\to [0,\infty )}$

Тщательно записывая приведенные выше уравнения как матричные уравнения, мы получаем ее двойственную задачу : ^[14] и по теореме двойственности линейного программирования , поскольку первичная задача является допустимой и ограниченной, то двойственная задача также является допустимой, и минимум в первой задаче равен максимуму во второй задаче. То есть, пара задач демонстрирует сильную двойственность .$${\displaystyle {\begin{cases}\max _{f,g}\sum _{x}\mu (x)f(x)+\sum _{y}\nu (y)g(y)\\f(x)+g(y)\leq c(x,y)\end{cases}}}$$

Для общего случая двойственная задача находится путем преобразования сумм в интегралы: и сильная двойственность все еще сохраняется. Это теорема двойственности Канторовича . Седрик Виллани приводит следующую интерпретацию Луиса Каффарелли : ^[15]$${\displaystyle {\begin{cases}\sup _{f,g}\mathbb {E} _{x\sim \mu }[f(x)]+\mathbb {E} _{y\sim \nu }[g(y)]\\f(x)+g(y)\leq c(x,y)\end{cases}}}$$

Предположим, вы хотите отправить уголь из шахт, распределенных как , на заводы, распределенные как . Функция стоимости транспортировки равна . Теперь приходит грузоотправитель и предлагает выполнить транспортировку для вас. Вы бы заплатили ему за уголь за погрузку угля в , и заплатили бы ему за уголь за разгрузку угля в . ${\displaystyle \mu }$${\displaystyle \nu }$${\displaystyle c}$${\displaystyle f(x)}$${\displaystyle x}$${\displaystyle g(y)}$${\displaystyle y}$

Чтобы вы приняли сделку, ценовой график должен удовлетворять . Двойственность Канторовича гласит, что грузоотправитель может составить ценовой график, который заставит вас заплатить почти столько же, сколько вы бы отправили сами.${\displaystyle f(x)+g(y)\leq c(x,y)}$

Этот результат можно преобразовать далее, чтобы получить:

Два нижних шага свертки визуально понятны, когда вероятностное пространство равно . ${\displaystyle \mathbb {R} }$

Для удобства записи обозначим операцию инфимальной свертки. ${\displaystyle \square }$

Для первого шага, где мы использовали , постройте кривую , затем в каждой точке нарисуйте конус с наклоном 1 и возьмите нижнюю огибающую конусов как , как показано на диаграмме, затем не может увеличиваться с наклоном больше 1. Таким образом, все его секущие имеют наклон . ${\displaystyle f={\text{cone}}\mathbin {\square } (-g)}$${\displaystyle -g}$${\displaystyle f}$${\displaystyle f}$${\displaystyle {\bigg |}{\frac {f(x)-f(y)}{x-y}}{\bigg |}\leq 1}$

Для второго шага представьте себе инфимальную свертку , тогда, если все секущие имеют наклон не более 1, то нижняя огибающая — это просто сами вершины конуса, таким образом . ${\displaystyle {\text{cone}}\mathbin {\square } (-f)}$${\displaystyle f}$${\displaystyle {\text{cone}}\mathbin {\square } (-f)}$${\displaystyle {\text{cone}}\mathbin {\square } (-f)=-f}$

Пример 1D . Когда оба являются распределениями на , то интегрирование по частям дает таким образом${\displaystyle \mu ,\nu }$${\displaystyle \mathbb {R} }$$${\displaystyle \mathbb {E} _{x\sim \mu }[f(x)]-\mathbb {E} _{y\sim \nu }[f(y)]=\int f'(x)(F_{\nu }(x)-F_{\mu }(x))\,\mathrm {d} x,}$$$${\displaystyle f(x)=K\cdot \operatorname {sign} (F_{\nu }(x)-F_{\mu }(x)).}$$

Бенаму и Брениер нашли двойственное представление с помощью механики жидкости , которое допускает эффективное решение с помощью выпуклой оптимизации . ^{[16] [17]}${\displaystyle W_{2}}$

Даны две плотности вероятности на , где пробегает поля скорости, управляющие уравнением непрерывности с граничными условиями в поле плотности жидкости: То есть масса должна сохраняться, а поле скорости должно переносить распределение вероятностей в течение интервала времени .${\displaystyle p,q}$${\displaystyle \mathbb {R} ^{n}}$$${\displaystyle W_{2}^{2}(p,q)=\min _{\mathbf {v}}\int _{0}^{1}\int _{\mathbb {R} ^{n}}\|{\mathbf {v}}({\mathbf {x}},t)\|^{2}\rho ({\mathbf {x}},t)\,d{\mathbf {x}}\,dt}$$${\displaystyle {\mathbf {v}}}$$${\displaystyle {\dot {\rho }}+\nabla \cdot (\rho {\mathbf {v}})=0\quad \rho (\cdot ,0)=p,\;\rho (\cdot ,1)=q}$$${\displaystyle p}$${\displaystyle q}$${\displaystyle [0,1]}$

При подходящих предположениях расстояние Вассерштейна порядка два эквивалентно Липшицу однородной норме Соболева отрицательного порядка . Точнее, если мы возьмем связное риманово многообразие , снабженное положительной мерой , то мы можем определить для полунормы и для знаковой меры на дуальной норме Тогда любые две вероятностные меры и на удовлетворяют верхней границе ^[18] В другом направлении, если и каждая имеет плотности относительно стандартной меры объема на , которые обе ограничены сверху некоторым , и имеет неотрицательную кривизну Риччи , то ^{[19] [20]}${\displaystyle W_{2}}$${\displaystyle M}$ ${\displaystyle \pi }$${\displaystyle f\colon M\to \mathbb {R} }$$${\displaystyle \|f\|_{{\dot {H}}^{1}(\pi )}^{2}=\int _{M}\|\nabla f(x)\|^{2}\,\pi (\mathrm {d} x)}$$ ${\displaystyle \mu }$${\displaystyle M}$$${\displaystyle \|\mu \|_{{\dot {H}}^{-1}(\pi )}=\sup {\bigg \{}|\langle f,\mu \rangle |\,{\bigg |}\,\|f\|_{{\dot {H}}^{1}(\pi )}\leq 1{\bigg \}}.}$$${\displaystyle \mu }$${\displaystyle \nu }$${\displaystyle M}$$${\displaystyle W_{2}(\mu ,\nu )\leq 2\,\|\mu -\nu \|_{{\dot {H}}^{-1}(\pi )}.}$$${\displaystyle \mu }$${\displaystyle \nu }$${\displaystyle M}$${\displaystyle 0<C<\infty }$${\displaystyle M}$ $${\displaystyle \|\mu -\nu \|_{{\dot {H}}^{-1}(\pi )}\leq {\sqrt {C}}\,W_{2}(\mu ,\nu ).}$$

Для любого p ≥ 1 метрическое пространство ( P _p ( M ), W _p ) является сепарабельным и полным , если ( M , d ) является сепарабельным и полным. ^[21]

Также можно рассмотреть метрику Вассерштейна для . В этом случае определяющая формула становится: где обозначает существенный супремум относительно меры . Метрическое пространство ( P _∞ ( M ), W _∞ ) является полным, если ( M ,  d ) является сепарабельным и полным. Здесь P _∞ — пространство всех вероятностных мер с ограниченным носителем. ^[22]${\displaystyle p=\infty }$$${\displaystyle W_{\infty }(\mu ,\nu )=\lim _{p\rightarrow +\infty }W_{p}(\mu ,\nu )=\inf _{\gamma \in \Gamma (\mu ,\nu )}\gamma \operatorname {-essup} d(x,y),}$$${\displaystyle \gamma \operatorname {-essup} d(x,y)}$${\displaystyle d(x,y)}$${\displaystyle \gamma }$

• «В чем преимущества метрики Вассерштейна по сравнению с дивергенцией Кульбака–Лейблера?». Stack Exchange . 1 августа 2017 г.