Prueba de convergencia uniforme si la dimensión VC es finita

Question

En el libro »Entendiendo el aprendizaje de la máquina: de la teoría a los algoritmos«, escrito por Ben-David y Shalev-Shwartz, hay una prueba que no entiendo. El contexto está demostrando que si una clase de hipótesis $ \ mathcal {h} $ tiene una dimensión de VC finita, luego disfruta de la propiedad de convergencia uniforme.

La prueba de esta implicación involucra el LEMMA de Sauer (las clases de hipótesis con la dimensión de VC finITO tienen »tamaño pequeño y eficaz«) y un teorema que indica que las clases de hipótesis con »Pequeño tamaño efectivo« Disfrute de la propiedad de convergencia uniforme. La prueba de la última sub-implicación implica este teorema (Theorem 6.11 en el libro):

Let $ \ mathcal {h} $ Be una clase de hipéstesis de clasificadores binarios sobre un dominio $ \ mathcal {x } $ y deje que $ \ tau _ {\ mathcal {h}} $ be su función de crecimiento (de Sauer Lemma). Luego, para todos $ m \ in \ mathbb {n} $ , para cada distribución $ \ mathcal {d} $ < / span> sobre $ \ mathcal {x} \ veces \ {0, 1 \} $ y cada $ \ delta \ en (0, 1) $ : $$ \ forall h \ in \ mathcal {h}: \ mathbb {p} _ {s \ sim \ mathcal {d} ^ m} \ izquierda [| L _ {\ mathcal {d}} (H) - l_s (h) | \ leq \ frac {4 + \ sqrt {\ log (\ tau _ {\ mathcal {h}} (2m))}} {\ delta \ sqrt {2m}} \ derecha] \ geq 1 - \ delta $$

En la prueba para este teorema se afirma, que sigue inmediatamente de la desigualdad. $$ \ mathbb {e} _ {s \ sim \ mathcal {d} ^ m} \ izquierda [\ sup_ {h \ in \ mathcal {h}} | L _ {\ mathcal {d}} (H) - l_s (h) | \ derecha] \ leq \ frac {4 + \ sqrt {\ log (\ tau _ {\ mathcal {h}} (2m))}} {\ sqrt {2m}}, $$ El hecho de que la variable aleatoria $ \ theTa:=sup_ {h \ in \ mathcal {h}} | L _ {\ mathcal {d}} (h) - l_s (h) | $ es la desigualdad no negativa y de Markov.

---

Sin embargo, lo hago no Vea cómo se desprende inmediatamente de esos hechos. ¿Qué estoy perdiendo?

Answer 1

Let $ x= | l_ \ mathcal {d} (h) - l_s (h) | $ .La declaración sobre la expectativa del supremo de $ x $ implica, en particular, que para algunos $ m $ , $$ \ mathbb {e} [x] \ leq M. $$ Desde $ x \ geq 0 $ , la desigualdad de Markov implica que $$ \ Pr \ izquierda [x \ geq \ frac {m} {\ delta} \ derecha] \ leq \ delta. $$ Esto implica que $$ \ Pr \ izquierda [x \ leq \ frac {m} {\ delta} \ derecha] \ geq \ Pr \ izquierda [x <\ frac {m} {\ delta} \ derecha]= 1 - \ pr \ izquierda [x \ geq \ frac {m} {\ delta} \ derecha] \ geq 1 - \ delta. $$