無知な学習のためのタイトなVC

次の結果はおそらく知られている。しかし、私が見いだすことができる証明は、余分な対数因子でより弱い結果を証明します。タイトバインドの証拠はどこにありますか?

Theorem. Let $mathcal{H}$ be a class of
functions $h : mathcal{X} to {-1,+1}$ with VC dimension $d<infty$. Let
$mathcal{D}$ be a distribution on $mathcal{X} times {-1,1}$
and let $(X_1,Y_1), cdots, (X_n,Y_n)$ be independent samples from
$mathcal{D}$. Let $varepsilon,delta>0$.

If $n geq
Oleft(frac{d+log(1/delta)}{varepsilon^2}right)$, then
$$mathbb{P}left[forall h in mathcal{H} ~~left|frac{1}{n}
sum_{i=1}^n h(X_i) cdot Y_i – underset{(X_*,Y_*) leftarrow
mathcal{D}}{mathbb{E}}[h(X_*) cdot
Y_*]right|levarepsilonright] ge 1-delta.$$


不可知論的学習への(よく知られた)つながりは、以下の通りです。 $ mathcal {H} $は “仮説”のクラスであり、$
mathcal {D} $は属性$ X in mathcal {X} $とラベル$ Y in { – 1 、+ 1
} $である。あなたは、$ mathcal {D} $からの$ n $サンプルを見て、サンプルによくラベルを付ける仮説(つまり$
frac {1} {n} sum_ {i = 1} ^ nh(X_i) cdot Y_i
$が大きい)は、地上の真理値をもうまくラベル付けする(つまり、$ underset {(X_ *、Y_ *) leftath
mathcal {D}} { mathbb {E}} [h(X_ *) cdot Y_ *] $も大きい)。上記の定理は、$ n
geqO left( frac { mathsf {VCdim}( mathcal {H})+ log(1/
delta)} { vε2} right)$ならば確率$ ge 1- delta
$で、すべての仮説について、サンプル上の誤差と分布上の誤差は$ varepsilon $の範囲内にあります。

VCの次元を統一収束に関連付けることができる証拠には、すべて余分な対数係数が含まれています。つまり、 frac {
mathsf {VCdim}( mathcal {H}) cdot log( mathsf {VCdim}(
mathcal {H})/ varepsilon)+ log(1/ delta)} { varepsilon ^ 2}
right)$です。これは、 Perles-Sauer-Shelah補題と巧妙な組合境界。 $ mathsf
{VCdim}( mathcal {H})= log | mathcal {H} |
$の単純な場合、これはちょうどHoeffdingの不等式と連合境界に従います。

残念ながら、私は数時間を探していたにもかかわらず、きつく一般的な結果の証拠を見つけることができませんでした。確かに誰かが私を正しい情報源に向けることができます!

ベストアンサー

これは、

M。 Talagrand。
ガウス的プロセスと経験的プロセスのより鋭い境界確率の実体、28-76ページ、1994年。

これは、例えば、 この記事(1.1.2節)を参考にしてください。風景。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です