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

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

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

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

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

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

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

куда ${\displaystyle D(p||q)}$ это Дивергенция Кульбака – Лейблера между ${\displaystyle p}$ и ${\displaystyle q}$.

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

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

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

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

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

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

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

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

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

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

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

Пример

Для оценщика ${\displaystyle q}$ предложено в Acharya et al. (2013),^[2]

${\displaystyle 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}})).}$

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

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

1. Орлицкий, Алон; Суреш, Ананда Тиртха. (2015), Оценка конкурентного распределения, arXiv:1503.07940, Bibcode:2015arXiv150307940O
2. Ачарья, Джаядев; Джафарпур, Ашкан; Орлицкий, Алон; Суреш, Ананда Тирта (2013), «Оптимальная оценка вероятности с приложениями к прогнозированию и классификации», Материалы 26-й ежегодной конференции по теории обучения (COLT)