競争の後悔

意思決定理論において、競争的後悔とは、分布推定のプロセスにおいて、制限された、または無制限の力を持つオラクルと比較した 相対的な後悔のことです。

データに基づく離散集合上の離散確率分布を推定することを考えると、推定量 ^[1]の後悔は次のように定義される。 ${\displaystyle p}$${\displaystyle {\mathcal {X}}}$${\displaystyle X}$ ${\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))).}$

ここで、と の間のKullback–Leibler 距離です。 ${\displaystyle D(p||q)}$${\displaystyle p}$${\displaystyle q}$

オラクルは、パラメータ空間内のの位置をある分割まで知ることによって、真の分布の部分的な情報にアクセスするように制限されている。^[1]パラメータ空間の分割が与えられ、オラクルが真の が存在する部分集合を知っていると仮定する。オラクルは次のような後悔を持つ。 ${\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).}$

競争上の後悔は、

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

オラクルは を正確に知っているが、自然推定量の中から推定量を選択することしかできない。自然推定量は、サンプル内で同じ回数出現するシンボルに等しい確率を割り当てる。^[1]オラクルの後悔は ${\displaystyle p}$

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

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

ここで はk 次元単位単体面を表します。 分割は上の置換クラスを表します。ここで と は、が の置換である場合に限り、同じサブセットに分割されます。 ${\displaystyle \Delta _{k}}$${\displaystyle \mathbb {P} _{\sigma }}$${\displaystyle \Delta _{k}}$${\displaystyle p}$${\displaystyle p'}$${\displaystyle p'}$${\displaystyle p}$