Prova di convergenza uniforme se la dimensione VC è finita

Question

Nel libro »Comprensione dell'apprendimento della macchina: dalla teoria agli algoritmi«, scritto da Ben-David e Shalev-Shwartz, c'è una prova che non capisco. Il contesto si sta dimostrando che se una classe di ipotesi $ \ mathcal {h} $ ha una dimensione VC finita, quindi gode della proprietà di convergenza uniforme.

La prova di questa implicazione implica il lemma di Sauer (lezioni di ipotesi con dimensione Finite VC hanno »piccole dimensioni efficaci«) e un teorema affermando che lezioni di ipotesi con »piccole dimensioni efficaci« Godetevi la proprietà di convergenza uniforme. La prova di quest'ultima sotto-implicazione coinvolge questo teorema (teorema 6.11 nel libro):

.

Let $ \ mathcal {h} $ essere una classe di hypethesis di classificatori binari su un dominio $ \ mathcal {x } $ e let $ \ tau _ {\ mathcal {h}} $ Sii la sua funzione di crescita (dal Lemma di Sauer). Quindi, per tutti $ M \ in \ mathbb {n} $ , per ogni distribuzione $ \ mathcal {d} $ < / span> sopra $ \ mathcal {x} \ volte \ {0, 1 \} $ e ogni $ \ delta \ in (0, 1) $ : $$ \ forall h \ in \ mathcal {h}: \ mathbb {p} _ {s \ sim \ mathcal {d} ^ m} \ Sinistra [| L _ {\ Mathcal {d}} (h) - l_s (h) | \ leq \ frac {4 + \ sqrt {\ log (\ tau _ {\ mathcal {h}} (2m))}} {\ delta \ sqrt {2m}} \ destra] \ geq 1 - \ delta $$

Nella prova per questo teorema è affermato, che segue immediatamente dalla disuguaglianza $$ \ mathbb {e} _ _ \ SIM \ Mathcal {d} ^ m} \ Sinistra [\ sup_ {h \ in \ mathcal {h}} | L _ {\ Mathcal {d}} (h) - l_s (h) | \ destra] \ leq \ frac {4 + \ sqrt {\ log (\ tau _ {\ mathcal {h}} (2m))}} {\ sqrt {2m}}, $$ Il fatto che la variabile casuale $ \ theta:=sup_ {h \ in \ mathcal {h}} | L _ {\ Mathcal {d}} (h) - l_s (h) | $ è la disuguaglianza non negativa e di Markov.

---

.

Tuttavia, faccio non vedere come segue immediatamente da tali fatti. Cosa mi manca?

Answer 1

Let $ x= | l_ \ mathcal {d} (h) - l_s (h) | $ .La dichiarazione sull'attesa del supremum di $ x $ implica, in particolare, che per alcuni $ m $ $$ \ MathBB {E} [X] \ Leq M. $$ Dal momento che $ x \ GeQ 0 $ , la disuguaglianza di Markov implica quella $$ \ PR \ sinistra [x \ geq \ frac {m} {\ delta} \ destra] \ leq \ delta. $$ Questo implica che $$ \ PR \ sinistra [x \ leq \ frac {m} {\ delta} \ destra] \ geq \ PR \ sinistra [x <\ frac {m} {\ delta} \ destra]= 1 - \ PR \ sinistra [x \ geq \ frac {m} {\ delta} \ destra] \ geq 1 - \ delta. $$