f - дивергенция

В теории вероятностей $f$-дивергенция – это определенный тип функции $D_{f}(P\|Q)$ который измеряет разницу между двумя распределениями вероятностей $P$ и $Q$. Многие распространенные дивергенции, такие как КЛ-дивергенция , расстояние Хеллингера и полное вариационное расстояние , являются частными случаями $f$-расхождение.

История

Эти расхождения были введены Альфредом Реньи. в той же статье, где он ввел известную энтропию Реньи . Он доказал, что эти расходимости уменьшаются в марковских процессах . f -дивергенции были дополнительно изучены независимо Чисаром (1963) , Моримото (1963) и Али и Сильви (1966) , и иногда их называют Чисаром. $f$-расхождения, расходимости Чисара–Моримото или расстояния Али–Сильви.

Определение

Несингулярный случай

Позволять $P$ и $Q$ быть двумя распределениями вероятностей в пространстве $\Omega$, такой, что $P\ll Q$, то есть, $P$ непрерывен абсолютно относительно $Q$. Тогда для выпуклой функции $f:[0,+\infty )\to (-\infty ,+\infty ]$ такой, что $f(x)$ конечен для всех $x>0$, $f(1)=0$, и $f(0)=\lim _{t\to 0^{+}}f(t)$ (которое может быть бесконечным), $f$-расхождение $P$ от $Q$ определяется как

$D_{f}(P\parallel Q)\equiv \int _{\Omega }f\left({\frac {dP}{dQ}}\right)\,dQ.$

Мы звоним $f$ генератор $D_{f}$.

В конкретных приложениях обычно существует эталонное распределение. $\mu$ на $\Omega$ (например, когда $\Omega =\mathbb {R} ^{n}$, эталонное распределение является мерой Лебега ), такое что $P,Q\ll \mu$, то мы можем использовать теорему Радона–Никодима, чтобы взять их плотности вероятности $p$ и $q$, давая

$D_{f}(P\parallel Q)=\int _{\Omega }f\left({\frac {p(x)}{q(x)}}\right)q(x)\,d\mu (x).$

Когда такого эталонного распределения под рукой нет, мы можем просто определить $\mu =P+Q$, и действуйте, как указано выше. Это полезный метод в более абстрактных доказательствах.

Распространение на сингулярные меры

Приведенное выше определение можно распространить на случаи, когда $P\ll Q$ больше не удовлетворяется (Определение 7.1 ).

С $f$ является выпуклым, и $f(1)=0$ , функция ${\frac {f(x)}{x-1}}$ не должна уменьшаться, поэтому существует $f'(\infty ):=\lim _{x\to \infty }f(x)/x$, принимая значение в $(-\infty ,+\infty ]$.

Поскольку для любого $p(x)>0$, у нас есть $\lim _{q(x)\to 0}q(x)f\left({\frac {p(x)}{q(x)}}\right)=p(x)f'(\infty )$ , мы можем распространить f-дивергенцию на $P\not \ll Q$.

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

Основные соотношения между f-расхождениями

• Линейность: $D_{\sum _{i}a_{i}f_{i}}=\sum _{i}a_{i}D_{f_{i}}$ задана конечная последовательность неотрицательных действительных чисел $a_{i}$ и генераторы $f_{i}$.

• $D_{f}=D_{g}$ если только $f(x)=g(x)+c(x-1)$ для некоторых $c\in \mathbb {R}$.

Доказательство

Если $f(x)=g(x)+c(x-1)$, затем $D_{f}=D_{g}$ по определению.

И наоборот, если $D_{f}-D_{g}=0$, тогда пусть $h=f-g$. Для любых двух вероятностных мер $P,Q$ на съемочной площадке $\{0,1\}$, с $D_{f}(P\|Q)-D_{g}(P\|Q)=0$, мы получаем $h(P_{1}/Q_{1})=-{\frac {Q_{0}}{Q_{1}}}h(P_{0}/Q_{0})$

Поскольку каждая вероятностная мера $P,Q$ имеет одну степень свободы, мы можем решить ${\frac {P_{0}}{Q_{0}}}=a,{\frac {P_{1}}{Q_{1}}}=x$ на любой выбор $0<a<1<x$.

Линейная алгебра дает $Q_{0}={\frac {x-1}{x-a}},Q_{1}={\frac {1-a}{x-a}}$, что является допустимой вероятностной мерой. Тогда мы получаем $h(x)={\frac {h(a)}{a-1}}(x-1),h(a)={\frac {h(x)}{x-1}}(a-1)$.

Таким образом $h(x)={\begin{cases}c_{1}(x-1)\quad {\text{if }}x>1,\\c_{0}(x-1)\quad {\text{if }}0<x<1,\\\end{cases}}$ для некоторых констант $c_{0},c_{1}$. Подключаем формулу в $h(x)={\frac {h(a)}{a-1}}(x-1)$ урожайность $c_{0}=c_{1}$.

Основные свойства f-дивергенций

• Неотрицательность : ƒ -дивергенция всегда положительна; оно равно нулю, если меры P и Q совпадают. Это следует непосредственно из неравенства Йенсена :

  $D_{f}(P\!\parallel \!Q)=\int \!f{\bigg (}{\frac {dP}{dQ}}{\bigg )}dQ\geq f{\bigg (}\int {\frac {dP}{dQ}}dQ{\bigg )}=f(1)=0.$

• Неравенство обработки данных : если κ — произвольная вероятность перехода , которая преобразует меры P и Q в P _κ и Q _κ соответственно, то
  $D_{f}(P\!\parallel \!Q)\geq D_{f}(P_{\kappa }\!\parallel \!Q_{\kappa }).$
  Равенство здесь выполняется тогда и только тогда, когда переход индуцируется достаточной статистикой относительно { P , Q }.
• Совместная выпуклость : для любого 0 ≤ λ ≤ 1 ,

  $D_{f}{\Big (}\lambda P_{1}+(1-\lambda )P_{2}\parallel \lambda Q_{1}+(1-\lambda )Q_{2}{\Big )}\leq \lambda D_{f}(P_{1}\!\parallel \!Q_{1})+(1-\lambda )D_{f}(P_{2}\!\parallel \!Q_{2}).$

  Это следует из выпуклости отображения $(p,q)\mapsto qf(p/q)$ на $\mathbb {R} _{+}^{2}$.
• Обращение путем выпуклой инверсии : для любой функции. $f$, его выпуклая инверсия определяется как $g(t):=tf(1/t)$. Когда $f$ удовлетворяет определяющим характеристикам генератора f-дивергенции ( $f(x)$ конечен для всех $x>0$, $f(1)=0$, и $f(0)=\lim _{t\to 0^{+}}f(t)$), затем $g$ удовлетворяет тем же свойствам и, таким образом, определяет f-дивергенцию $D_{g}$. Это «обратная сторона» $D_{f}$, в том смысле, что $D_{g}(P\|Q)=D_{f}(Q\|P)$ для всех $P,Q$ которые абсолютно непрерывны друг относительно друга.Таким образом, каждая f-дивергенция $D_{f}$ можно сделать симметричным, $D_{{\frac {1}{2}}(f+g)}$. Например, выполнение этой симметризации превращает КЛ-дивергенцию в дивергенцию Дженсена-Шеннона.

В частности, из монотонности следует, что если марковский процесс имеет положительное равновесное распределение вероятностей $P^{*}$ затем $D_{f}(P(t)\parallel P^{*})$ — монотонная (невозрастающая) функция времени, где распределение вероятностей $P(t)$ является решением прямых уравнений Колмогорова (или Мастер-уравнения ), используемых для описания временной эволюции распределения вероятностей в марковском процессе. Это означает, что все f -расхождения $D_{f}(P(t)\parallel P^{*})$ – функции Ляпунова прямых уравнений Колмогорова. Верно и обратное утверждение: если $H(P)$ является функцией Ляпунова для всех цепей Маркова с положительным равновесием. $P^{*}$ и имеет форму следа( $H(P)=\sum _{i}f(P_{i},P_{i}^{*})$) затем $H(P)=D_{f}(P(t)\parallel P^{*})$, для некоторой выпуклой функции f . Например, расходимости Брегмана вообще не обладают таким свойством и могут возрастать в марковских процессах.

Аналитические свойства

F-расхождения можно выразить с помощью ряда Тейлора и переписать, используя взвешенную сумму расстояний типа хи ( Nielsen & Nock (2013) ).

Наивное вариационное представление

Позволять $f^{*}$ быть сопряжением выпуклым $f$. Позволять $\mathrm {effdom} (f^{*})$ быть эффективной областью $f^{*}$, то есть, $\mathrm {effdom} (f^{*})=\{y:f^{*}(y)<\infty \}$. Тогда мы имеем два вариационных представления $D_{f}$, о котором мы опишем ниже.

Основное вариационное представление

При вышеуказанной настройке

Теорема — $D_{f}(P;Q)=\sup _{g:\Omega \to \mathrm {effdom} (f^{*})}E_{P}[g]-E_{Q}[f^{*}\circ g]$.

Это теорема 7.24.

Примеры приложений

Используя эту теорему об общем вариационном расстоянии с генератором $f(x)={\frac {1}{2}}|x-1|,$ его выпуклое сопряжение $f^{*}(x^{*})={\begin{cases}x^{*}{\text{ on }}[-1/2,1/2],\\+\infty {\text{ else.}}\end{cases}}$, и мы получаем $$TV(P\|Q)=\sup _{|g|\leq 1/2}E_{P}[g(X)]-E_{Q}[g(X)].$$Для дивергенции хи-квадрат, определяемой формулой $f(x)=(x-1)^{2},f^{*}(y)=y^{2}/4+y$, мы получаем $$\chi ^{2}(P;Q)=\sup _{g}E_{P}[g(X)]-E_{Q}[g(X)^{2}/4+g(X)].$$Поскольку вариационный член не является аффинно-инвариантным в $g$, хотя домен, в котором $g$ варьируется аффинно -инвариантно, мы можем использовать аффинную инвариантность, чтобы получить более компактное выражение.

Замена $g$ к $ag+b$ и берём максимум $a,b\in \mathbb {R}$, мы получаем $$\chi ^{2}(P;Q)=\sup _{g}{\frac {(E_{P}[g(X)]-E_{Q}[g(X)])^{2}}{Var_{Q}[g(X)]}},$$что находится всего в нескольких шагах от границы Хаммерсли–Чепмена–Роббинса и границы Крамера–Рао (теорема 29.1 и ее следствие в ).

Для $\alpha$-расхождение с $\alpha \in (-\infty ,0)\cup (0,1)$, у нас есть $f_{\alpha }(x)={\frac {x^{\alpha }-\alpha x-(1-\alpha )}{\alpha (\alpha -1)}}$, с диапазоном $x\in [0,\infty )$. Его выпуклое сопряжение $f_{\alpha }^{*}(y)={\frac {1}{\alpha }}(x(y)^{\alpha }-1)$ с диапазоном $y\in (-\infty ,(1-\alpha )^{-1})$, где $x(y)=((\alpha -1)y+1)^{\frac {1}{\alpha -1}}$.

Применение этой теоремы дает после замены на $h=((\alpha -1)g+1)^{\frac {1}{\alpha -1}}$, $$D_{\alpha }(P\|Q)={\frac {1}{\alpha (1-\alpha )}}-\inf _{h:\Omega \to (0,\infty )}\left(E_{Q}\left[{\frac {h^{\alpha }}{\alpha }}\right]+E_{P}\left[{\frac {h^{\alpha -1}}{1-\alpha }}\right]\right),$$или, сняв ограничение на $h$, $$D_{\alpha }(P\|Q)={\frac {1}{\alpha (1-\alpha )}}-\inf _{h:\Omega \to \mathbb {R} }\left(E_{Q}\left[{\frac {|h|^{\alpha }}{\alpha }}\right]+E_{P}\left[{\frac {|h|^{\alpha -1}}{1-\alpha }}\right]\right).$$Параметр $\alpha =-1$ дает вариационное представление $\chi ^{2}$-дивергенция, полученная выше.

Домен, над которым $h$ варьируется, вообще говоря, не является аффинно-инвариантным, в отличие от $\chi ^{2}$- случай расхождения. $\chi ^{2}$-дивергенция является особенной, так как в этом случае мы можем удалить $|\cdot |$ от $|h|$.

Для общего $\alpha \in (-\infty ,0)\cup (0,1)$, домен, над которым $h$ варьируется, является просто масштабным инвариантом. Как и выше, мы можем заменить $h$ к $ah$, и возьмем минимум больше $a>0$ чтобы получить $$D_{\alpha }(P\|Q)=\sup _{h>0}\left[{\frac {1}{\alpha (1-\alpha )}}\left(1-{\frac {E_{P}[h^{\alpha -1}]^{\alpha }}{E_{Q}[h^{\alpha }]^{\alpha -1}}}\right)\right].$$Параметр $\alpha ={\frac {1}{2}}$, и выполнив еще одну замену с помощью $g={\sqrt {h}}$, дает два вариационных представления квадрата расстояния Хеллингера: $$H^{2}(P\|Q)={\frac {1}{2}}D_{1/2}(P\|Q)=2-\inf _{h>0}\left(E_{Q}\left[h(X)\right]+E_{P}\left[h(X)^{-1}\right]\right),$$$$H^{2}(P\|Q)=2\sup _{h>0}\left(1-{\sqrt {E_{P}[h^{-1}]E_{Q}[h]}}\right).$$Применяя эту теорему к KL-дивергенции, определяемой формулой $f(x)=x\ln x,f^{*}(y)=e^{y-1}$, дает $$D_{KL}(P;Q)=\sup _{g}E_{P}[g(X)]-e^{-1}E_{Q}[e^{g(X)}].$$Это строго менее эффективно, чем представление Донскера – Варадана. $$D_{KL}(P;Q)=\sup _{g}E_{P}[g(X)]-\ln E_{Q}[e^{g(X)}].$$Этот недостаток устраняется следующей теоремой.

Улучшенное вариационное представление

Предположим, что используется настройка, описанная в начале этого раздела («Вариационные представления»).

Теорема — Если $f(x)=+\infty$ на $x<0$ (переопределить $f$ если необходимо), то

$D_{f}(P\|Q)=f^{\prime }(\infty )P\left[S^{c}\right]+\sup _{g}\mathbb {E} _{P}\left[g1_{S}\right]-\Psi _{Q,P}^{*}(g)$,

где $\Psi _{Q,P}^{*}(g):=\inf _{a\in \mathbb {R} }\mathbb {E} _{Q}\left[f^{*}(g(X)-a)\right]+aP[S]$и $S:=\{q>0\}$, где $q$ — функция плотности вероятности $Q$ относительно некоторой базовой меры.

В частном случае $f^{\prime }(\infty )=+\infty$, у нас есть

$D_{f}(P\|Q)=\sup _{g}\mathbb {E} _{P}[g]-\Psi _{Q}^{*}(g),\quad \Psi _{Q}^{*}(g):=\inf _{a\in \mathbb {R} }\mathbb {E} _{Q}\left[f^{*}(g(X)-a)\right]+a$.

Это теорема 7.25.

Примеры приложений

Применение этой теоремы к KL-дивергенции дает представление Донскера–Варадана.

Попытка применить эту теорему к общему $\alpha$-расхождение с $\alpha \in (-\infty ,0)\cup (0,1)$ не дает решения в замкнутом виде.

Типичные примеры f -дивергенций

В следующей таблице перечислены многие распространенные расхождения между распределениями вероятностей и возможными производящими функциями, которым они соответствуют. Примечательно, что, за исключением общего вариационного расстояния, все остальные являются частными случаями $\alpha$-дивергенция, или линейные суммы $\alpha$-расхождения.

Для каждой f-дивергенции $D_{f}$, его производящая функция определена не однозначно, а только с точностью до $c\cdot (t-1)$, где $c$ любая реальная константа. То есть для любого $f$ порождающее f-дивергенцию, мы имеем $D_{f(t)}=D_{f(t)+c\cdot (t-1)}$. Эта свобода не только удобна, но и действительно необходима.

Дивергенция	Соответствующая f(t)	Дискретная форма
$\chi ^{\alpha }$-расхождение, $\alpha \geq 1\,$	${\frac {1}{2}}|t-1|^{\alpha }\,$	${\frac {1}{2}}\sum _{i}\left|{\frac {p_{i}-q_{i}}{q_{i}}}\right|^{\alpha }q_{i}\,$
Общее расстояние вариации ( $\alpha =1\,$)	${\frac {1}{2}}|t-1|\,$	${\frac {1}{2}}\sum _{i}|p_{i}-q_{i}|\,$
α-дивергенция	${\begin{cases}{\frac {t^{\alpha }-\alpha t-\left(1-\alpha \right)}{\alpha \left(\alpha -1\right)}}&{\text{if}}\ \alpha \neq 0,\,\alpha \neq 1,\\t\ln t-t+1,&{\text{if}}\ \alpha =1,\\-\ln t+t-1,&{\text{if}}\ \alpha =0\end{cases}}$
KL-дивергенция ( $\alpha =1$)	$t\ln t$	$\sum _{i}p_{i}\ln {\frac {p_{i}}{q_{i}}}$
обратная КЛ-дивергенция ( $\alpha =0$)	$-\ln t$	$\sum _{i}q_{i}\ln {\frac {q_{i}}{p_{i}}}$
Расхождение Дженсена-Шеннона	${\frac {1}{2}}\left(t\ln t-(t+1)\ln \left({\frac {t+1}{2}}\right)\right)$	${\frac {1}{2}}\sum _{i}\left(p_{i}\ln {\frac {p_{i}}{(p_{i}+q_{i})/2}}+q_{i}\ln {\frac {q_{i}}{(p_{i}+q_{i})/2}}\right)$
Дивергенция Джеффри (КЛ + обратный КЛ)	$(t-1)\ln(t)$	$\sum _{i}(p_{i}-q_{i})\ln {\frac {p_{i}}{q_{i}}}$
квадрат расстояния Хеллингера ( $\alpha ={\frac {1}{2}}$)	${\frac {1}{2}}({\sqrt {t}}-1)^{2},\,1-{\sqrt {t}}$	${\frac {1}{2}}\sum _{i}({\sqrt {p_{i}}}-{\sqrt {q_{i}}})^{2};\;1-\sum _{i}{\sqrt {p_{i}q_{i}}}$
Пирсон $\chi ^{2}$-дивергенция (изменение масштаба $\alpha =2$)	$(t-1)^{2},\,t^{2}-1,\,t^{2}-t$	$\sum _{i}{\frac {(p_{i}-q_{i})^{2}}{q_{i}}}$
Нейман $\chi ^{2}$-дивергенция (обратная Пирсона) (изменение масштаба $\alpha =-1$)	${\frac {1}{t}}-1,\,{\frac {1}{t}}-t$	$2+\sum _{i}{\frac {(p_{i}-q_{i})^{2}}{p_{i}}}$

Сравнение генераторов альфа-расхождений, поскольку альфа изменяется от -1 до 2.

Позволять $f_{\alpha }$ быть генератором $\alpha$-расхождение, то $f_{\alpha }$ и $f_{1-\alpha }$ являются выпуклыми инверсиями друг друга, поэтому $D_{\alpha }(P\|Q)=D_{1-\alpha }(Q\|P)$. В частности, это показывает, что квадрат расстояния Хеллингера и расходимость Дженсена-Шеннона симметричны.

В литературе, $\alpha$-расхождения иногда параметризуются как

${\begin{cases}{\frac {4}{1-\alpha ^{2}}}{\big (}1-t^{(1+\alpha )/2}{\big )},&{\text{if}}\ \alpha \neq \pm 1,\\t\ln t,&{\text{if}}\ \alpha =1,\\-\ln t,&{\text{if}}\ \alpha =-1\end{cases}}$

что эквивалентно параметризации на этой странице путем замены $\alpha \leftarrow {\frac {\alpha +1}{2}}$.

Связь с другими статистическими расхождениями

Здесь мы сравниваем f -расхождения с другими статистическими расхождениями .

Расхождение Реньи

— Расходимости Реньи это семейство расходимостей, определяемое формулой

$R_{\alpha }(P\|Q)={\frac {1}{\alpha -1}}\log {\Bigg (}E_{Q}\left[\left({\frac {dP}{dQ}}\right)^{\alpha }\right]{\Bigg )}\,$

когда $\alpha \in (0,1)\cup (1,+\infty )$. Оно распространяется на случаи $\alpha =0,1,+\infty$ взяв предел.

Простая алгебра показывает, что $R_{\alpha }(P\|Q)={\frac {1}{\alpha -1}}\ln(1+\alpha (\alpha -1)D_{\alpha }(P\|Q))$, где $D_{\alpha }$ это $\alpha$-дивергенция, определенная выше.

Дивергенция Брегмана

Единственная f-дивергенция, которая также является дивергенцией Брегмана, — это КЛ-дивергенция.

Интегральные вероятностные метрики

Единственная f-дивергенция, которая также является интегральной вероятностной метрикой, — это полная вариация.

Финансовая интерпретация

Пару распределений вероятностей можно рассматривать как азартную игру, в которой одно из распределений определяет официальные шансы, а другое содержит фактические вероятности. Знание реальных вероятностей позволяет игроку получить прибыль от игры. Для большого класса рациональных игроков ожидаемая норма прибыли имеет ту же общую форму, что и ƒ -дивергенция.

См. также

• Расхождение Кульбака – Лейблера
• Дивергенция Брегмана

Ссылки

• Чисар, И. (1963). «Теоретико-информационное неравенство и его применение к доказательству эргодичности цепей Маркова». Мадьяр. Туд. Академический мат. Козл . 8 :85-108.
• Моримото, Т. (1963). «Марковские процессы и H-теорема». Дж. Физ. Соц. Япония . 18 (3): 328–331. Бибкод : 1963JPSJ...18..328M . дои : 10.1143/JPSJ.18.328 .
• Али, С.М.; Сильви, SD (1966). «Общий класс коэффициентов отклонения одного распределения от другого». Журнал Королевского статистического общества, серия B. 28 (1): 131–142. JSTOR   2984279 . МР   0196777 .
• Чисар, И. (1967). «Информационные меры различия вероятностных распределений и косвенного наблюдения». Studia Scientiarum Mathematicarum Hungarica . 2 : 229–318.
• Чисар, И. ; Шилдс, П. (2004). «Теория информации и статистика: Учебное пособие» (PDF) . Основы и тенденции в теории связи и информации . 1 (4): 417–528. дои : 10.1561/0100000004 . Проверено 8 апреля 2009 г.
• Лизе, Ф.; Вайда, И. (2006). «О расхождениях и информации в статистике и теории информации». Транзакции IEEE по теории информации . 52 (10): 4394–4412. дои : 10.1109/TIT.2006.881731 . S2CID   2720215 .
• Нильсен, Ф.; Нок, Р. (2013). «О Хи-квадрате и расстояниях Хи высшего порядка для аппроксимации f-расходимостей». Письма об обработке сигналов IEEE . 21 (1): 10–13. arXiv : 1309.3029 . Бибкод : 2014ISPL...21...10N . дои : 10.1109/ЛСП.2013.2288355 . S2CID   4152365 .
• Кёржолли, Ж.Ф.; Друйе, Р. (2006). «Нормализованные информационные расхождения». arXiv : math/0604246 .