Неравенство Бретаньоля – Хубера

В теории информации неравенство Бретаньоля – Хубера ограничивает общее расстояние вариации между двумя распределениями вероятностей. $P$ и $Q$ вогнутой и ограниченной функцией расходимости Кульбака–Лейблера $D_{\mathrm {KL} }(P\parallel Q)$ . Оценку можно рассматривать как альтернативу известному неравенству Пинскера : когда $D_{\mathrm {KL} }(P\parallel Q)$ большой (например, больше 2). ^{[ 1 ]}), неравенство Пинскера бессмысленно, а Бретаньолле – Хубера остается ограниченным и, следовательно, непустым. Он используется в статистике и машинном обучении для доказательства нижних границ теории информации на основе проверки гипотез. ^{[ 2 ]}　 ( Неравенство Бретаньолля – Хубера – Кэрола представляет собой вариант неравенства концентрации для полиномиально распределенных случайных величин, которое ограничивает общее расстояние вариации.)

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

Предварительные определения

Позволять $P$ и $Q$ быть двумя распределениями вероятностей в измеримом пространстве $({\mathcal {X}},{\mathcal {F}})$ . Напомним, что общая разница между $P$ и $Q$ определяется

d_{\mathrm {TV} }(P,Q)=\sup _{A\in {\mathcal {F}}}\{|P(A)-Q(A)|\}.

Расхождение Кульбака -Лейблера определяется следующим образом:

D_{\mathrm {KL} }(P\parallel Q)={\begin{cases}\int _{\mathcal {X}}\log {\bigl (}{\frac {dP}{dQ}}{\bigr )}\,dP&{\text{if }}P\ll Q,\\[1mm]+\infty &{\text{otherwise}}.\end{cases}}

Вышеупомянутые обозначения $P\ll Q$ означает абсолютную непрерывность $P$ относительно $Q$ , и ${\frac {dP}{dQ}}$ обозначает Радона–Никодима производную $P$ относительно $Q$ .

Общее заявление

Неравенство Бретаньоля – Хубера гласит:

d_{\mathrm {TV} }(P,Q)\leq {\sqrt {1-\exp(-D_{\mathrm {KL} }(P\parallel Q))}}\leq 1-{\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))

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

Следующая версия напрямую подразумевается из приведенной выше оценки, но некоторые авторы ^{[ 2 ]} предпочитаю говорить об этом так. Позволять $A\in {\mathcal {F}}$ быть любое событие. Затем

P(A)+Q({\bar {A}})\geq {\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))

где ${\bar {A}}=\Omega \smallsetminus A$ является дополнением $A$ .

Действительно, по определению полной вариации для любого $A\in {\mathcal {F}}$ ,

{\begin{aligned}Q(A)-P(A)\leq d_{\mathrm {TV} }(P,Q)&\leq 1-{\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))\\&=Q(A)+Q({\bar {A}})-{\frac {1}{2}}\exp(-D_{\mathrm {KL} }(P\parallel Q))\end{aligned}}

Переставляя, получаем заявленную нижнюю оценку $P(A)+Q({\bar {A}})$ .

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

Докажем основное утверждение, следуя идеям книги Цыбакова (лемма 2.6, стр. 89): ^{[ 3 ]} которые отличаются от оригинального доказательства ^{[ 4 ]} (см. примечание К.Канона ^{[ 1 ]} для модернизированной перезаписи их аргументов).

Доказательство состоит из двух шагов:

1. Докажите с помощью Коши–Шварца, что полная вариация связана с коэффициентом Бхаттачарьи (правая часть неравенства):

1-d_{\mathrm {TV} }(P,Q)^{2}\geq \left(\int {\sqrt {PQ}}\right)^{2}

2. Докажите, используя умное применение неравенства Йенсена, что

\left(\int {\sqrt {PQ}}\right)^{2}\geq \exp(-D_{\mathrm {KL} }(P\parallel Q))

Шаг 1:

Сначала заметьте, что

d_{\mathrm {TV} }(P,Q)=1-\int \min(P,Q)=\int \max(P,Q)-1

Чтобы увидеть это, обозначим

A^{*}=\arg \max _{A\in \Omega }|P(A)-Q(A)|

и без ограничения общности предположим, что

P(A^{*})>Q(A^{*})

такой, что

d_{\mathrm {TV} }(P,Q)=P(A^{*})-Q(A^{*})

. Тогда мы сможем переписать

d_{\mathrm {TV} }(P,Q)=\int _{A^{*}}\max(P,Q)-\int _{A^{*}}\min(P,Q)

А затем добавление и удаление

\int _{\bar {A^{*}}}\max(P,Q){\text{ or }}\int _{\bar {A^{*}}}\min(P,Q)

мы получаем оба тождества.

Затем

{\begin{aligned}1-d_{\mathrm {TV} }(P,Q)^{2}&=(1-d_{\mathrm {TV} }(P,Q))(1+d_{\mathrm {TV} }(P,Q))\\&=\int \min(P,Q)\int \max(P,Q)\\&\geq \left(\int {\sqrt {\min(P,Q)\max(P,Q)}}\right)^{2}\\&=\left(\int {\sqrt {PQ}}\right)^{2}\end{aligned}}

потому что

PQ=\min(P,Q)\max(P,Q).

Шаг 2:

Мы пишем

(\cdot )^{2}=\exp(2\log(\cdot ))

и применим неравенство Йенсена :

{\begin{aligned}\left(\int {\sqrt {PQ}}\right)^{2}&=\exp \left(2\log \left(\int {\sqrt {PQ}}\right)\right)\\&=\exp \left(2\log \left(\int P{\sqrt {\frac {Q}{P}}}\right)\right)\\&=\exp \left(2\log \left(\operatorname {E} _{P}\left[\left({\sqrt {\frac {P}{Q}}}\right)^{-1}\,\right]\right)\right)\\&\geq \exp \left(\operatorname {E} _{P}\left[-\log \left({\frac {P}{Q}}\right)\right]\right)=\exp(-D_{KL}(P,Q))\end{aligned}}

Объединение результатов шагов 1 и 2 приводит к заявленной границе общей вариации.

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

Пример сложности необъективного подбрасывания монеты

Источник: ^{[ 1 ]}

Вопрос в том Сколько подбрасываний монеты мне нужно, чтобы отличить честную монету от необъективной?

Предположим, у вас есть 2 монеты, честная монета ( бернулли распределена со средним $p_{1}=1/2$ ) и $\varepsilon$ -предвзятая монета ( $p_{2}=1/2+\varepsilon$ ). Тогда, чтобы идентифицировать смещенную монету с вероятностью не менее $1-\delta$ (для некоторых $\delta >0$ ), по меньшей мере

n\geq {\frac {1}{2\varepsilon ^{2}}}\log \left({\frac {1}{2\delta }}\right).

Чтобы получить эту нижнюю оценку, мы предполагаем, что общее расстояние вариации между двумя последовательностями $n$ образцы как минимум $1-2\delta$ . Это связано с тем, что верхняя граница общего отклонения ограничивает вероятность недооценки или переоценки средних значений монет. Обозначим $P_{1}^{n}$ и $P_{2}^{n}$ соответствующие совместные распределения $n$ подбрасывание монеты для каждой монеты, затем

У нас есть

{\begin{aligned}(1-2\delta )^{2}&\leq d_{\mathrm {TV} }\left(P_{1}^{n},P_{2}^{n}\right)^{2}\\[4pt]&\leq 1-e^{-D_{\mathrm {KL} }(P_{1}^{n}\parallel P_{2}^{n})}\\[4pt]&=1-e^{-nD_{\mathrm {KL} }(P_{1}\parallel P_{2})}\\[4pt]&=1-e^{-n{\frac {\log(1/(1-4\varepsilon ^{2}))}{2}}}\end{aligned}}

Результат получается перестановкой слагаемых.

Теоретико-информационная нижняя оценка для k -вооруженными бандитами игр с

В многоруком бандите нижняя граница минимаксного сожаления любого бандитского алгоритма может быть доказана с использованием Бретаньоля – Хубера и его последствий при проверке гипотез (см. главу 15 « Бандитских алгоритмов»). ^{[ 2 ]}).

История

Этот результат был впервые доказан в 1979 году Жаном Бретаньоллем и Катрин Юбер и опубликован в материалах Страсбургского семинара по теории вероятностей. ^{[ 4 ]} Книга Александра Цыбакова. ^{[ 3 ]} представляет собой раннюю переиздание неравенства и его приписывание Бретаньолю и Юберу, которое представлено как ранняя и менее общая версия леммы Ассуада (см. примечания 2.8). Постоянное улучшение Бретаньолле-Хубера было доказано в 2014 году как следствие расширения неравенства Фано . ^{[ 5 ]}

См. также

Общая вариация для списка верхних границ
Неравенство Бретаньоля – Хубера – Кэрола в неравенстве концентрации

Ссылки

^ Jump up to: ^а ^б ^с Канонн, Клеман (2022). «Краткая заметка о неравенстве между КЛ и ТВ». arXiv : 2202.07198 [ мат.PR ].
^ Jump up to: ^а ^б ^с Латтимор, Тор; Сепешвари, Чаба (2020). Бандитские алгоритмы (PDF) . Издательство Кембриджского университета . Проверено 18 августа 2022 г.
^ Jump up to: ^а ^б Цыбаков, Александр Б. (2010). Введение в непараметрическое оценивание . Серия Спрингера по статистике. Спрингер. дои : 10.1007/b13794 . ISBN 978-1-4419-2709-5 . OCLC 757859245 . S2CID 42933599 .
^ Jump up to: ^а ^б Бретаньолле, Ж.; Хубер, К. (1978), «Оценка плотностей: минимаксный риск» , Семинар по вероятностям XII , Конспекты лекций по математике, том. 649, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 342–363, номер домена : 10.1007/bfb0064610 , ISBN. 978-3-540-08761-8 , S2CID 122597694 , получено 20 августа 2022 г.
^ Герчиновиц, Себастьян; Менар, Пьер; Штольц, Жиль (01 мая 2020 г.). «Неравенство Фано для случайных величин» . Статистическая наука . 35 (2). arXiv : 1702.05985 . дои : 10.1214/19-стс716 . ISSN 0883-4237 . S2CID 15808752 .

[canonne-1] Jump up to: ^а ^б ^с Канонн, Клеман (2022). «Краткая заметка о неравенстве между КЛ и ТВ». arXiv : 2202.07198 [ мат.PR ].

[bandit_algs-2] Jump up to: ^а ^б ^с Латтимор, Тор; Сепешвари, Чаба (2020). Бандитские алгоритмы (PDF) . Издательство Кембриджского университета . Проверено 18 августа 2022 г.

[:0-3] Jump up to: ^а ^б Цыбаков, Александр Б. (2010). Введение в непараметрическое оценивание . Серия Спрингера по статистике. Спрингер. дои : 10.1007/b13794 . ISBN 978-1-4419-2709-5 . OCLC 757859245 . S2CID 42933599 .

[:1-4] Jump up to: ^а ^б Бретаньолле, Ж.; Хубер, К. (1978), «Оценка плотностей: минимаксный риск» , Семинар по вероятностям XII , Конспекты лекций по математике, том. 649, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 342–363, номер домена : 10.1007/bfb0064610 , ISBN. 978-3-540-08761-8 , S2CID 122597694 , получено 20 августа 2022 г.

[5] Герчиновиц, Себастьян; Менар, Пьер; Штольц, Жиль (01 мая 2020 г.). «Неравенство Фано для случайных величин» . Статистическая наука . 35 (2). arXiv : 1702.05985 . дои : 10.1214/19-стс716 . ISSN 0883-4237 . S2CID 15808752 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]