Konkurrensmässig ånger

I beslutsteorin är konkurrens ånger den relativa ångern jämfört med ett orakel med begränsad eller obegränsad makt i processen för distributionsuppskattning .

Konkurrenskraftig ånger till oraklet med full kraft

Överväg att uppskatta en diskret sannolikhetsfördelning $p$ på en diskret uppsättning ${\mathcal {X}}$ baserat på data $X$ , beklagaren av en estimator $q$ är definierad som

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

där ${\mathcal {P}}$ är mängden av all möjlig sannolikhetsfördelning, och

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

där $D(p||q)$ är Kullback–Leibler-divergensen mellan $p$ och $q$ .

Konkurrenskraftig ånger till oraklet med begränsad kraft

Oracle med partiell information

Oraklet är begränsat till att ha tillgång till partiell information om den sanna distributionen $p$ genom att känna till platsen för $p$ i parameterutrymmet upp till en partition. Givet en partition $\mathbb {P}$ av parameterutrymmet, och anta att oraklet känner till delmängden $P$ där den sanna $p\in P$ . Oraklet kommer att ångra sig som

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

Den konkurrensmässiga ångern till oraklet kommer att vara

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

Oracle med partiell information

Oraklet vet exakt $p$ , men kan bara välja estimatorn bland naturliga estimatorer. En naturlig estimator tilldelar lika sannolikhet till symbolerna som visas lika många gånger i urvalet. Oraklets ånger är

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

och konkurrensen ånger är

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

Exempel

För estimatorn $q$ som föreslås i Acharya et al.(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}})).$

Här betecknar ${\displaystyle \Delta _{k}} den k-dimensionella enhetens simplexyta.$ Partitionen $\mathbb {P} _{\sigma }$ anger permutationsklassen på $\Delta _{k}$ , där $p$ och $p '$ är partitionerade i samma delmängd om och endast om $p'$ är en permutation av $p$ .