仮説クラスのイプシロンカバーを用いたPAC学習

この動画は43:00になります、一般化エラー$
εに対してバインドされたPACのバージョン以前は見たことがなかった$が引用されています:

$$epsilon^2 < frac{log{|H_epsilon|} +
log{1/delta}}{2m}$$

ここで、$ m $は標本数、$ delta $は信頼パラメータ、$ H_ ε$は仮説クラスの “$ epsilon $
-cover”の基数であり、ここで$
ε同じサブセット内の2つの仮説が一致しない確率が$ε未満であるように、仮説クラスのサブセットの集合として$
-coverを生成する。

これが正式な陳述ではないという事実を別にすれば、私はこれを自分で証明できませんでした。誰でもこのバージョンのPACについて聞いたことがありますか?もしそうなら、彼らは私にそれを説明するリソースを指摘することができますか?

ベストアンサー

This follows from Massart’s finite class lemma. Let $F$ is a
binary function class restricted to some set ${X_1,ldots,X_n}$,
and let $P_n$ be the empirical (i.e., uniform) measure on this set.
Then, for any $epsilon>0$, the empirical Rademacher complexity
of $F$ is bounded by $$ R_n(F;X) le epsilon + sqrt{frac{2log
N_F(epsilon)}{n}},$$ where $N_F(epsilon)$ is the $ell_2$
$epsilon$-covering number of $F$ w.r.t. $P_n$. This is proved in
display (1) here: https://www.cs.bgu.ac.il/~asml162/wiki.files/dudley-pollard.pdf
— check out the course notes: https://www.cs.bgu.ac.il/~asml162/Class_Material

返信を残す

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