Prova de convergência uniforme se a dimensão VC é finita

Question

No livro »Compreender a aprendizagem da máquina: da teoria dos algoritmos«, escrita por Ben-David e Shalev-Shwartz, há uma prova que eu não entendo. O contexto está provando que, se uma classe de hipótese $ \ mathcal {h} $ tem dimensão do VC finito, então goza da propriedade uniforme de convergência.

A prova desta implicação envolve o lema da Sauer (aulas de hipótese com a dimensão do VC finito têm »pequeno tamanho eficaz«) e um teorema afirmando que as aulas de hipóteses com »pequeno tamanho eficaz« desfrutar da propriedade uniforme da convergência. A prova da última sub-implicação envolve este teorema (Teorema 6.11 no livro):

.

Deixe $ \ mathcal {h} $ ser uma classe de hipethesis de classificadores binários em um domínio $ \ mathcal {x } $ e deixe $ \ tau _ {\ mathcal {h}} $ Seja sua função de crescimento (do Lema do Sauer). Em seguida, para todos $ m \ in \ mathbb {n} $ , para cada distribuição $ \ mathcal {d} $ < / span> sobre $ \ mathcal {x} \ vezes \ {0, 1 \} $ e cada $ \ Delta \ Em (0, 1) $ : $$ \ forall h \ in \ mathcal {h}: \ mathbb {p} _ {s \ sim \ mathcal {d} ^ m} \ esquerda [| L _ {\ mathcal {d}} (h) - l_s (h) | \ leq \ frac {4 + \ sqrt {\ log (\ tau _ {\ mathcal {h}} (2m))}}}} {\ delta \ sqrt {2m}} \ direita] \ geq 1 - \ delta $$

Na prova para este teorema é declarado, que segue imediatamente da desigualdade $$ \ mathbb {e} _ {s \ sim \ mathcal {d} ^ m} \ \ sup_ {h \ in \ mathcal {h}} | L _ {\ mathcal {d}} (h) - l_s (h) | \ Direita] \ LEQ \ FRAC {4 + \ sqrt {\ log (\ tau _ {\ mathcal {h}} (2m))}}} {\ sqrt {2m}}, $$ O fato de a variável aleatória $ \ theta:=sup_ {h \ in \ mathcal {h}} | L _ {\ mathcal {d}} (h) - l_s (h) | $ é a desigualdade não-negativa e de Markov.

---

.

No entanto, faço não ver como segue imediatamente desses fatos. O que estou perdendo?

Answer 1

Deixe $ x= | l_ \ mathcal {d} (h) - l_s (h) | $ .A declaração sobre a expectativa do supremo da $ x $ implica, em particular, que para alguma $ m $ , $$ \ mathbb {e} [x] \ leq m. $$ Desde a $ x \ geq 0 $ , a desigualdade de Markov implica que $$ \ Pr \ left [x \ geq \ frac {m} {\ delta} \ direito] \ leq \ delta. $$ Isso implica que $$ \ Pr \ left [x \ leq \ frac {m} {\ delta} \ direita] \ geq \ Pr \ left [x <\ frac {m} {\ delta} \ direita]= 1 - \ PR \ left [x \ geq \ frac {m} {\ delta} \ direito] \ geq 1 - \ delta. $$