Неравенство Пинскера

В теории информации неравенство Пинскера , названное в честь его изобретателя Марка Семеновича Пинскера , представляет собой неравенство , которое ограничивает общее вариационное расстояние (или статистическое расстояние) с точки зрения расхождения Кульбака-Лейблера . Неравенство строго ограничено постоянными факторами. ^{[ 1 ]}

Официальное заявление

Неравенство Пинскера гласит, что если $P$ и $Q$ - это два распределения вероятностей в измеримом пространстве. $(X,\Sigma )$ , затем

\delta (P,Q)\leq {\sqrt {{\frac {1}{2}}D_{\mathrm {KL} }(P\parallel Q)}},

где

\delta (P,Q)=\sup {\bigl \{}|P(A)-Q(A)|\mid \quad A\in \Sigma {\text{ is a measurable event}}{\bigr \}}

это общее расстояние вариации (или статистическое расстояние) между $P$ и $Q$ и

D_{\mathrm {KL} }(P\parallel Q)=\operatorname {E} _{P}\left(\log {\frac {\mathrm {d} P}{\mathrm {d} Q}}\right)=\int _{X}\left(\log {\frac {\mathrm {d} P}{\mathrm {d} Q}}\right)\,\mathrm {d} P

— расхождение Кульбака–Лейблера в nats . Когда пространство выборки $X$ является конечным множеством, расходимость Кульбака–Лейблера определяется выражением

D_{\mathrm {KL} }(P\parallel Q)=\sum _{i\in X}\left(\log {\frac {P(i)}{Q(i)}}\right)P(i)\!

Заметим, что в терминах полной вариационной нормы $\|P-Q\|$ подписанного мероприятия $P-Q$ , неравенство Пинскера отличается от приведенного выше в два раза:

\|P-Q\|\leq {\sqrt {2D_{\mathrm {KL} }(P\parallel Q)}}.

Доказательство неравенства Пинскера использует неравенство разделения для f -дивергенций .

Альтернативная версия

Заметим, что выражение неравенства Пинскера зависит от того, какой базис логарифмирования используется при определении КЛ-дивергенции. $D_{KL}$ определяется с помощью $\ln$ (логарифм по основанию $e$ ), тогда как $D$ обычно определяется с помощью $\log _{2}$ (логарифм по основанию 2). Затем,

D(P\parallel Q)={\frac {D_{KL}(P\parallel Q)}{\ln 2}}.

Учитывая приведенные выше комментарии, в некоторой литературе существует альтернативная формулировка неравенства Пинскера, которая связывает расхождение информации с вариационным расстоянием:

D(P\parallel Q)={\frac {D_{KL}(P\parallel Q)}{\ln 2}}\geq {\frac {1}{2\ln 2}}V^{2}(p,q),

то есть

{\sqrt {\frac {D_{KL}(P\parallel Q)}{2}}}\geq {\frac {V(p,q)}{2}},

в котором

V(p,q)=\sum _{x\in {\mathcal {X}}}|p(x)-q(x)|

это (ненормализованное) расстояние вариации между двумя функциями плотности вероятности $p$ и $q$ на том же алфавите ${\mathcal {X}}$ . ^{[ 2 ]}

Эта форма неравенства Пинскера показывает, что «сходимость по расхождению» является более сильным понятием, чем «сходимость по вариационному расстоянию».

Простое доказательство Джона Полларда можно получить, положив $r(x)=P(x)/Q(x)-1\geq -1$ :

{\begin{aligned}D_{KL}(P\parallel Q)&=E_{Q}[(1+r(x))\log(1+r(x))-r(x)]\\&\geq {\frac {1}{2}}E_{Q}\left[{\frac {r(x)^{2}}{1+r(x)/3}}\right]\\&\geq {\frac {1}{2}}{\frac {E_{Q}[|r(x)|]^{2}}{E_{Q}[1+r(x)/3]}}&{\text{(from Titu's lemma)}}\\&={\frac {1}{2}}E_{Q}[|r(x)|]^{2}&{\text{(As }}E_{Q}[1+r(x)/3]=1{\text{ )}}\\&={\frac {1}{2}}V(p,q)^{2}.\end{aligned}}

Здесь лемма Титу известна также как неравенство Седракяна .

Обратите внимание, что нижняя оценка неравенства Пинскера бессмысленна для любых распределений, где $D_{\mathrm {KL} }(P\parallel Q)>2$ , поскольку полное вариационное расстояние не более $1$ . Для таких распределений можно использовать альтернативную оценку, предложенную Бретаньоллем и Хубером. ^{[ 3 ]} (см. также Цыбаков ^{[ 4 ]}):

\delta (P,Q)\leq {\sqrt {1-e^{-D_{\mathrm {KL} }(P\parallel Q)}}}.

История

Пинскер первым доказал неравенство с большей константой. Неравенство в приведенной выше форме было независимо доказано Кульбаком , Чисаром и Кемперманом . ^{[ 5 ]}

Обратная задача

Точное обратное неравенству не может иметь места: для любого $\varepsilon >0$ , есть распределения $P_{\varepsilon },Q$ с $\delta (P_{\varepsilon },Q)\leq \varepsilon$ но $D_{\mathrm {KL} }(P_{\varepsilon }\parallel Q)=\infty$ . Простой пример — двухточечное пространство. $\{0,1\}$ с $Q(0)=0,Q(1)=1$ и $P_{\varepsilon }(0)=\varepsilon ,P_{\varepsilon }(1)=1-\varepsilon$ . ^{[ 6 ]}

Однако на конечных пространствах справедливо обратное неравенство $X$ с постоянной, зависящей от $Q$ . ^{[ 7 ]} Более конкретно, можно показать, что при определении $\alpha _{Q}:=\min _{x\in X:Q(x)>0}Q(x)$ у нас есть для любой меры $P$ который абсолютно непрерывен $Q$

{\frac {1}{2}}D_{\mathrm {KL} }(P\parallel Q)\leq {\frac {1}{\alpha _{Q}}}\delta (P,Q)^{2}.

Как следствие, если $Q$ имеет полную поддержку (т. $Q(x)>0$ для всех $x\in X$ ), затем

\delta (P,Q)^{2}\leq {\frac {1}{2}}D(P\parallel Q)\leq {\frac {1}{\alpha _{Q}}}\delta (P,Q)^{2}.

Ссылки

^ Чисар, Имре; Кернер, Янош (2011). Теория информации: теоремы кодирования для дискретных систем без памяти . Издательство Кембриджского университета. п. 44. ИСБН 9781139499989 .
^ Раймонд В., Юнг (2008). Теория информации и сетевое кодирование . Гонконг: Спрингер. п. 26. ISBN 978-0-387-79233-0 .
^ Бретаньолле, Дж.; Хубер, К., Оценка плотностей: минимаксный риск , Семинар по вероятностям, XII (Страсбургский университет, Страсбург, 1976/1977), стр. 342–363, Конспекты лекций по математике, 649, Springer, Берлин, 1978, Лемма 2.1 (на французском языке).
^ Цыбаков, Александр Б., Введение в непараметрическую оценку , переработанное и дополненное издание французского оригинала 2004 года. Перевод Владимира Зайца. Серия Спрингера по статистике. Спрингер, Нью-Йорк, 2009. xii+214 стр. ISBN 978-0-387-79051-0 , уравнение 2.25.
^ Цыбаков, Александр (2009). Введение в непараметрическую оценку . Спрингер. п. 132 . ISBN 9780387790527 .
^ Расхождение становится бесконечным, когда одно из двух распределений присваивает событию нулевую вероятность, а другое присваивает ему ненулевую вероятность (независимо от того, насколько она мала); см., например Басу, Митра; Хо, Тин Кам (2006). Сложность данных в распознавании образов . Спрингер. п. 161. ИСБН 9781846281723 . .
^ см. лемму 4.1 в Гетце, Фридрих; Самбале, Хольгер; Синулис, Артур (2019). «Концентрация высшего порядка для функций слабозависимых случайных величин». Электронный журнал вероятностей . 24 . arXiv : 1801.06348 . дои : 10.1214/19-EJP338 . S2CID 52200238 .

Дальнейшее чтение

Томас М. Кавер и Джой А. Томас: Элементы теории информации , 2-е издание, Willey-Interscience, 2006 г.
Николо Чеза-Бьянки и Габор Лугоши: предсказание, обучение и игры , Cambridge University Press, 2006 г.

[1] Чисар, Имре; Кернер, Янош (2011). Теория информации: теоремы кодирования для дискретных систем без памяти . Издательство Кембриджского университета. п. 44. ИСБН 9781139499989 .

[2] Раймонд В., Юнг (2008). Теория информации и сетевое кодирование . Гонконг: Спрингер. п. 26. ISBN 978-0-387-79233-0 .

[3] Бретаньолле, Дж.; Хубер, К., Оценка плотностей: минимаксный риск , Семинар по вероятностям, XII (Страсбургский университет, Страсбург, 1976/1977), стр. 342–363, Конспекты лекций по математике, 649, Springer, Берлин, 1978, Лемма 2.1 (на французском языке).

[4] Цыбаков, Александр Б., Введение в непараметрическую оценку , переработанное и дополненное издание французского оригинала 2004 года. Перевод Владимира Зайца. Серия Спрингера по статистике. Спрингер, Нью-Йорк, 2009. xii+214 стр. ISBN 978-0-387-79051-0 , уравнение 2.25.

[5] Цыбаков, Александр (2009). Введение в непараметрическую оценку . Спрингер. п. 132 . ISBN 9780387790527 .

[6] Расхождение становится бесконечным, когда одно из двух распределений присваивает событию нулевую вероятность, а другое присваивает ему ненулевую вероятность (независимо от того, насколько она мала); см., например Басу, Митра; Хо, Тин Кам (2006). Сложность данных в распознавании образов . Спрингер. п. 161. ИСБН 9781846281723 . .

[7] см. лемму 4.1 в Гетце, Фридрих; Самбале, Хольгер; Синулис, Артур (2019). «Концентрация высшего порядка для функций слабозависимых случайных величин». Электронный журнал вероятностей . 24 . arXiv : 1801.06348 . дои : 10.1214/19-EJP338 . S2CID 52200238 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]