Конкурентное сожаление

В теории принятия решений конкурентное сожаление — это относительное сожаление по сравнению с оракулом с ограниченной или неограниченной властью в процессе оценки распределения.

Соревновательное сожаление оракулу в полную силу

Рассмотрим оценку дискретного распределения вероятностей $p$ на дискретном множестве ${\mathcal {X}}$ на основе данных $X$, сожаление оценщика $q$ определяется как

$\max _{p\in {\mathcal {P}}}r_{n}(q,p).$

где ${\mathcal {P}}$ - набор всех возможных распределений вероятностей, и

$r_{n}(q,p)=\mathbb {E} (D(p||q(X))).$

где $D(p||q)$ – это расхождение Кульбака – Лейблера между $p$ и $q$.

Соревновательное сожаление оракулу с ограниченной властью

Oracle с частичной информацией

Оракул ограничен в доступе к частичной информации об истинном распределении. $p$ зная местонахождение $p$ в пространстве параметров до раздела. Учитывая раздел $\mathbb {P}$ пространства параметров и предположим, что оракул знает подмножество $P$ где правда $p\in P$. Оракул пожалеет, что

$r_{n}(P)=\min _{q}\max _{p\in P}r_{n}(q,p).$

Конкурентное сожаление оракулу будет

$r_{n}^{\mathbb {P} }(q,{\mathcal {P}})=\max _{P\in \mathbb {P} }(r_{n}(q,P)-r_{n}(P)).$

Oracle с частичной информацией

Оракул точно знает $p$, но может выбирать оценку только среди натуральных оценок. Естественная оценка присваивает равную вероятность символам, которые появляются в выборке одинаковое количество раз. Сожаление оракула

$r_{n}^{nat}(p)=\min _{q\in {\mathcal {Q}}_{nat}}r_{n}(q,p),$

и соревновательное сожаление

$\max _{p\in {\mathcal {P}}}(r_{n}(q,p)-r_{n}^{nat}(p)).$

Пример

Для оценщика $q$ предложено Ачарья и др. (2013),

$r_{n}^{\mathbb {P} _{\sigma }}(q,\Delta _{k})\leq r_{n}^{nat}(q,\Delta _{k})\leq {\tilde {\mathcal {O}}}(\min({\frac {1}{\sqrt {n}}},{\frac {k}{n}})).$

Здесь $\Delta _{k}$ обозначает k-мерную единичную симплексную поверхность. Раздел $\mathbb {P} _{\sigma }$ обозначает класс перестановок на $\Delta _{k}$, где $p$ и $p'$ разделены на одно и то же подмножество тогда и только тогда, когда $p'$ представляет собой перестановку $p$.