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

В математике , то Вассерстины расстояние или метрика Канторович-Рубинштейн является функцией расстояния , определенной между вероятностными распределениями на заданном метрическом пространстве .${\ displaystyle M}$

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

Название «расстояние Вассерштейна» было придумано Р.Л. Добрушиным в 1970 году в честь русского математика Леонида Васерштейна, который представил это понятие в 1969 году. В большинстве англоязычных публикаций используется немецкое написание «Wasserstein» (приписывается немецкому названию «Vaseršteĭn»). источник).

Определение [ править ]

Позвольте быть метрическим пространством, для которого каждая вероятностная мера на является мерой Радона (так называемое пространство Радона ). Для , пусть обозначает совокупность всех вероятностных мер на с конечным моментом . Тогда существует некоторые в таких , что:${\ displaystyle (M, d)}$${\ displaystyle M}$${\ displaystyle p \ geq 1}$${\ Displaystyle P_ {p} (М)}$${\ displaystyle \ mu}$${\ displaystyle M}$${\ displaystyle p ^ {\ text {th}}}$ ${\ displaystyle x_ {0}}$${\ displaystyle M}$

${\ displaystyle \ int _ {M} d (x, x_ {0}) ^ {p} \, \ mathrm {d} \ mu (x) <\ infty.}$

Расстояние Вассерштейна между двумя вероятностными мерами и in определяется как${\ displaystyle p ^ {\ text {th}}}$${\ displaystyle \ mu}$${\ displaystyle \ nu}$${\ Displaystyle P_ {p} (М)}$

${\ displaystyle W_ {p} (\ mu, \ nu): = \ left (\ inf _ {\ gamma \ in \ Gamma (\ mu, \ nu)} \ int _ {M \ times M} d (x, y) ^ {p} \, \ mathrm {d} \ gamma (x, y) \ right) ^ {1 / p},}$

где обозначает совокупность всех мер по с маргинальными и на первые и вторые факторах соответственно. (Множество также называется множество всех соединений из и .)${\ Displaystyle \ Гамма (\ му, \ ню)}$${\ displaystyle M \ times M}$ ${\ displaystyle \ mu}$${\ displaystyle \ nu}$${\ Displaystyle \ Гамма (\ му, \ ню)}$${\ displaystyle \ mu}$${\ displaystyle \ nu}$

Вышеуказанное расстояние обычно обозначается (обычно среди авторов, предпочитающих написание «Вассерштейн») или (как правило, среди авторов, предпочитающих написание «Васерштейн»). В оставшейся части статьи будут использоваться обозначения.${\ Displaystyle W_ {p} (\ mu, \ nu)}$${\ displaystyle \ ell _ {p} (\ mu, \ nu)}$${\ displaystyle W_ {p}}$

Метрика Вассерштейна может быть эквивалентно определена следующим образом:

${\displaystyle W_{p}(\mu ,\nu )=\left(\inf \operatorname {E} {\big [}d(X,Y)^{p}{\big ]}\right)^{1/p},}$

где обозначает ожидаемую величину в виде случайной величины , а нижняя грань берется по всем совместным распределениям случайных величин и с маргинальными и соответственно.${\displaystyle \mathbf {E} [Z]}$ ${\displaystyle Z}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle \mu }$${\displaystyle \nu }$

Интуиция и подключение к оптимальному транспорту [ править ]

Два одномерных распределения и , нанесенные на оси x и y, и одно возможное совместное распределение, которое определяет транспортный план между ними. Совместный план распределения / транспортировки не уникален${\displaystyle \mu }$${\displaystyle \nu }$

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

${\displaystyle c(x,y)\mapsto [0,\infty )}$

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

${\displaystyle {\begin{aligned}\int \gamma (x,y)\,\mathrm {d} y=\mu (x)&\qquad {\text{(the amount of earth moved out of point }}x{\text{ needs to equal the amount that was there to begin with)}}\\\int \gamma (x,y)\,\mathrm {d} x=\nu (y)&\qquad {\text{(the amount of earth moved into point }}y{\text{ needs to equal the depth of the hole that was there at the beginning)}}\end{aligned}}}$

То есть общая масса, перемещенная из бесконечно малой области вокруг, должна быть равна, а общая масса, перемещенная в область вокруг, должна быть равна . Это эквивалентно требованию, представлять собой совместное распределение вероятностей с маргинальными и . Таким образом, бесконечно малая масса транспортируется из в это , а стоимость перемещения является , после определения функции затрат. Таким образом, общая стоимость транспортного плана составляет${\displaystyle x}$${\displaystyle \mu (x)\mathrm {d} x}$${\displaystyle y}$${\displaystyle \nu (y)\mathrm {d} y}$${\displaystyle \gamma }$${\displaystyle \mu }$${\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 \gamma }$

${\displaystyle \iint c(x,y)\gamma (x,y)\,\mathrm {d} x\,\mathrm {d} y=\int c(x,y)\,\mathrm {d} \gamma (x,y)}$

План не уникален; Оптимальный транспортный план - это план с минимальной стоимостью из всех возможных транспортных планов. Как уже упоминалось, требование плана действительным является то , что это совместное распределение с маргинальными и ; позволяя обозначать множество всех таких мер , как и в первой части, стоимость плана оптимальной является${\displaystyle \gamma }$${\displaystyle \mu }$${\displaystyle \nu }$${\displaystyle \Gamma }$

${\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 a_{1}}$${\displaystyle a_{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 a_{1}}$${\displaystyle a_{2}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle W_{p}(\mu _{1},\mu _{2})=\|a_{1}-a_{2}\|_{p}.}$

Нормальные распределения [ править ]

Позвольте и быть двумя невырожденными гауссовскими мерами (т.е. нормальными распределениями ) на , с соответствующими ожидаемыми значениями и и симметричными положительными полуопределенными ковариационными матрицами и . Тогда ^[1] относительно обычной евклидовой нормы на 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 {trace} } {\bigl (}C_{1}+C_{2}-2{\bigl (}C_{2}^{1/2}C_{1}C_{2}^{1/2}{\bigr )}^{1/2}{\bigr )}.}$

Этот результат обобщает предыдущий пример расстояния Вассерштейна между двумя точечными массами (по крайней мере, в данном случае ), поскольку точечную массу можно рассматривать как нормальное распределение с ковариационной матрицей, равной нулю, и в этом случае следовой член исчезает, и только термин, включающий евклидово расстояние между средствами, остается.${\displaystyle p=2}$

Приложения [ править ]

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

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

В своей статье «Вассерштейн ГАН» Арджовский и др. ^[2] используют метрику Вассерштейна-1 как способ улучшить исходную структуру Generative Adversarial Networks (GAN), чтобы уменьшить исчезающий градиент и проблемы коллапса режима.

Метрика Вассерштейна имеет формальную связь с анализом Прокруста в применении к мерам хиральности ^[3] и анализу формы. ^[4]

Свойства [ править ]

Метрическая структура [ править ]

Можно показать , что W _р удовлетворяет все аксиомы матрицы А метрики на Р _р ( М ). Более того, сходимость по W _p эквивалентна обычной слабой сходимости мер плюс сходимость первых p -х моментов. ^[5]

Двойное представление W ₁ [ править ]

- Следующее двойственное представление 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 .

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

${\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 ограничена некоторой константой C , то

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

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

Эквивалентность W ₂ и соболевской норме отрицательного порядка [ править ]

При подходящих предположениях расстояние Вассерштейна второго порядка липшицево эквивалентно однородной соболевской норме отрицательного порядка . ^[6] Более точно, если мы возьмем , чтобы быть подключен римановом многообразия оснащен положительной мерой , то мы можем определить для полунормя${\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}(\mu )}.}$

В другом направлении, если и каждый имеет плотности по отношению к стандартной мере объема на , которые оба ограничены выше некоторого , и имеют неотрицательную кривизну Риччи , то${\displaystyle \mu }$${\displaystyle \nu }$${\displaystyle M}$${\displaystyle 0<C<\infty }$${\displaystyle M}$

${\displaystyle \|\mu -\nu \|_{{\dot {H}}^{-1}(\mu )}\leq {\sqrt {C}}W_{2}(\mu ,\nu ).}$

Разделимость и полнота [ править ]

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

См. Также [ править ]

• Метрика Леви
• Метрика Леви – Прохорова
• Общее расстояние вариации вероятностных мер
• Теория транспорта
• Дистанция движителя земли

Эта статья включает в себя список общих ссылок , но он остается в основном непроверенным, поскольку в нем отсутствуют соответствующие встроенные ссылки . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Июль 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Ссылки [ править ]

• Виллани, Седрик (2008). Оптимальный транспорт, старый и новый . Springer. ISBN 978-3-540-71050-9.
• Амбросио, Л., Джильи, Н. и Саваре, Г. (2005). Градиентные потоки в метрических пространствах и в пространстве вероятностных мер . Базель: ETH Zürich, Birkhäuser Verlag. ISBN 3-7643-2428-7.CS1 maint: multiple names: authors list (link)
• Джордан, Ричард; Киндерлерер, Дэвид; Отто, Феликс (1998). «Вариационная формулировка уравнения Фоккера – Планка». SIAM J. Math. Анальный . 29 (1): 1–17 (в электронном виде). CiteSeerX  10.1.1.6.8815 . DOI : 10.1137 / S0036141096303359 . ISSN  0036-1410 . Руководство по ремонту  1617171 .
• Рюшендорф, Л. (2001) [1994], "Метрика Вассерштейна" , Энциклопедия математики , EMS Press

Внешние ссылки [ править ]

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