Arrepentimiento competitivo

Concepto en la teoría de la decisión

En la teoría de decisiones , el arrepentimiento competitivo es el arrepentimiento relativo comparado con un oráculo con poder limitado o ilimitado en el proceso de estimación de distribución.

Arrepentimiento competitivo ante el oráculo con pleno poder

Considere estimar una distribución de probabilidad discreta en un conjunto discreto basado en datos , el arrepentimiento de un estimador ^[1] se define como ${\displaystyle p}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle X}$ ${\displaystyle q}$

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

donde es el conjunto de todas las distribuciones de probabilidad posibles, y ${\displaystyle {\mathcal {P}}}$

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

¿Dónde está la divergencia de Kullback-Leibler entre y ? ${\displaystyle D(p||q)}$ ${\displaystyle p}$ ${\displaystyle q}$

Arrepentimiento competitivo ante el oráculo con poder limitado

Oráculo con información parcial

El oráculo está restringido a tener acceso a información parcial de la distribución verdadera al conocer la ubicación de en el espacio de parámetros hasta una partición. ^[1] Dada una partición del espacio de parámetros, y supongamos que el oráculo conoce el subconjunto donde se encuentra la distribución verdadera . El oráculo se arrepentirá como ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \mathbb {P} }$ ${\displaystyle P}$ ${\displaystyle p\in P}$

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

El arrepentimiento competitivo ante el oráculo será

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

Oráculo con información parcial

El oráculo sabe exactamente , pero sólo puede elegir el estimador entre los estimadores naturales. Un estimador natural asigna la misma probabilidad a los símbolos que aparecen el mismo número de veces en la muestra. ^[1] El arrepentimiento del oráculo es ${\displaystyle p}$

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

y el arrepentimiento competitivo es

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

Ejemplo

Para el estimador propuesto en Acharya et al.(2013), ^[2] ${\displaystyle q}$

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

Aquí se denota la superficie símplex unitaria de dimensión k. La partición denota la clase de permutación en , donde y se dividen en el mismo subconjunto si y solo si es una permutación de . ${\displaystyle \Delta _{k}}$ ${\displaystyle \mathbb {P} _{\sigma }}$ ${\displaystyle \Delta _{k}}$ ${\displaystyle p}$ ${\displaystyle p'}$ ${\displaystyle p'}$ ${\displaystyle p}$

Referencias

1. Orlitsky, Alon; Suresh, Ananda Theertha. (2015), Estimación de distribución competitiva , arXiv : 1503.07940 , Bibcode :2015arXiv150307940O
2. Acharya, Jayadev; Jafarpour, Ashkan; Orlitsky, Alon; Suresh, Ananda Theertha (2013), "Estimación de probabilidad óptima con aplicaciones a la predicción y clasificación", Actas de la 26.ª Conferencia Anual sobre Teoría del Aprendizaje (COLT)