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

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

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

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

Определение

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

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

В ${displaystyle p^{ ext{th}}}$ Расстояние Вассерштейна между двумя вероятностными мерами ${displaystyle mu }$ и ${displaystyle u }$ в ${displaystyle P_{p}(M)}$ определяется как

${displaystyle W_{p}(mu ,u ):=left(inf _{gamma in Gamma (mu ,u )}int _{M imes M}d(x,y)^{p},mathrm {d} gamma (x,y)ight)^{1/p},}$

куда ${displaystyle Gamma (mu ,u )}$ обозначает совокупность всех мер на ${displaystyle M imes M}$ с маргиналы ${displaystyle mu }$ и ${displaystyle u }$ по первому и второму факторам соответственно. (Набор ${displaystyle Gamma (mu ,u )}$ также называется набором всех муфты из ${displaystyle mu }$ и ${displaystyle u }$.)

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

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

${displaystyle W_{p}(mu ,u )=left(inf operatorname {E} {ig [}d(X,Y)^{p}{ig ]}ight)^{1/p},}$

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

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

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

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

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

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

${displaystyle {egin{aligned}int gamma (x,y),mathrm {d} y=mu (x)&qquad { ext{(the amount of earth moved out of point }}x{ ext{ need to equal the amount that was there to begin with)}}int gamma (x,y),mathrm {d} x=u (y)&qquad { ext{(the amount of earth moved into point }}y{ ext{ need 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 u (y)mathrm {d} y}$. Это эквивалентно требованию, чтобы ${displaystyle gamma }$ быть совместное распределение вероятностей с маргиналами ${displaystyle mu }$ и ${displaystyle u }$. Таким образом, бесконечно малая масса, переносимая из ${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 u }$; позволяя ${displaystyle Gamma }$ обозначим набор всех таких мер, как в первом разделе, стоимость оптимального плана равна

${displaystyle C=inf _{gamma in Gamma (mu ,u )}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 pgeq 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}|_{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 imes n}}$. Потом,^[1] относительно обычной евклидовой нормы на ${displaystyle mathbb {R} ^{n}}$, расстояние 2-Вассерштейна между ${displaystyle mu _{1}}$ и ${displaystyle mu _{2}}$ является

${displaystyle W_{2}(mu _{1},mu _{2})^{2}=|m_{1}-m_{2}|_{2}^{2}+mathop {mathrm {trace} } {igl (}C_{1}+C_{2}-2{igl (}C_{2}^{1/2}C_{1}C_{2}^{1/2}{igr )}^{1/2}{igr )}.}$

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

Приложения

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

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

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

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

Характеристики

Метрическая структура

Можно показать, что W_п удовлетворяет все аксиомы из метрика на п_п(M). Кроме того, сходимость по W_п эквивалентно обычному слабая сходимость мер плюс схождение первых пые моменты.^[5]

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

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

${displaystyle W_{1}(mu ,u )=sup left{left.int _{M}f(x),mathrm {d} (mu -u )(x)ight|{ ext{continuous }}f:M o mathbb {R} ,operatorname {Lip} (f)leq 1ight},}$

где Lip (ж) обозначает минимальную Постоянная Липшица за ж.

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

${displaystyle ho (mu ,u ):=sup left{left.int _{M}f(x),mathrm {d} (mu -u )(x)ight|{ ext{continuous }}f:M o [-1,1]ight}.}$

Если метрика d ограничено некоторой константой C, тогда

${displaystyle 2W_{1}(mu ,u )leq Cho (mu ,u ),}$

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

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

При подходящих предположениях расстояние Вассерштейна ${displaystyle W_{2}}$ второго порядка липшицево эквивалентно однородному отрицательному порядку. Соболева норма.^[6] Точнее, если взять ${displaystyle M}$ быть связаны Риманово многообразие оснащен положительной мерой ${displaystyle pi }$, то мы можем определить для ${displaystyle fcolon M o mathbb {R} }$ полунорма

${displaystyle |f|_{{dot {H}}^{1}(pi )}^{2}=int _{M}|abla f(x)|^{2},pi (mathrm {d} x)}$

и для подписанная мера ${displaystyle mu }$ на ${displaystyle M}$ двойственная норма

${displaystyle |mu |_{{dot {H}}^{-1}(pi )}=sup {igg {}|langle f,mu angle |,{igg |},|f|_{{dot {H}}^{1}(pi )}leq 1{igg }}.}$

Тогда любые две вероятностные меры ${displaystyle mu }$ и ${displaystyle u }$ на ${displaystyle M}$ удовлетворяют верхней границе

${displaystyle W_{2}(mu ,u )leq 2|mu -u |_{{dot {H}}^{-1}(mu )}.}$

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

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

Разделимость и полнота

Для любого п ≥ 1 метрическое пространство (п_п(M), W_п) является отделяемый, и является полный если (M, d) отделимо и полно.^[7]

Смотрите также

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

Рекомендации

1. Олкин И. и Пукельсхайм Ф. (1982). «Расстояние между двумя случайными векторами с заданными дисперсионными матрицами». Приложение линейной алгебры. 48: 257–263. Дои:10.1016/0024-3795(82)90112-4. ISSN  0024-3795.
2. Арджовски (2017). "Генеративные состязательные сети Вассерштейна". ICML.
3. Петижан, М. (2002). «Хиральные смеси» (PDF). Журнал математической физики. 43 (8): 4147–4157. Дои:10.1063/1.1484559.
4. Петижан, М. (2004). «От подобия форм к дополнительности форм: к теории стыковки». Журнал математической химии. 35 (3): 147–158. Дои:10.1023 / B: JOMC.0000033252.59423.6b. S2CID  121320315.
5. Климент, Филипп; Деш, Вольфганг (2008). «Элементарное доказательство неравенства треугольника для метрики Вассерштейна». Труды Американского математического общества. 136 (1): 333–339. Дои:10.1090 / S0002-9939-07-09020-X.
6. Пейр, Реми (2018). "Сравнение между W₂ расстояние и ЧАС⁻¹ норма, и локализация расстояния Вассерштейна ». ESAIM Control Optim. Расчет. Вар. 24 (4): 1489–1501. Дои:10.1051 / cocv / 2017050. ISSN  1292-8119. (См. Теоремы 2.1 и 2.5.)
7. Богачев В.И.; Колесников, А. (2012). «Проблема Монжа – Канторовича: достижения, связи, перспективы». Русская математика. Обзоры. 67 (5): 785–890. Дои:10.1070 / RM2012v067n05ABEH004808.

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

внешняя ссылка

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