Nachweis der einheitlichen Konvergenz, wenn VC-Dimension endlich ist

Question

Im Buch »Machine verstehen Lernen: von Theorie bis Algorithmen«, geschrieben von Ben-David und Shalev-Shwartz, ein Beweis, den ich nicht verstehe. Der Kontext beweist, dass, wenn eine Hypotheseklasse $ \ Mathcal {h} $ eine endliche VC-Dimension hat, dann genießt es die einheitliche Konvergenzeigenschaft.

Der Nachweis dieser Implikation umfasst SAUERs Lemma (Hypothesenklassen mit Finite VC-Dimension haben »kleine effektive Größe« und ein Satz, der angibt, dass Hypotheseklassen mit »kleinen effektiven Größe« die einheitliche Konvergenzeigenschaft genießen. Der Nachweis der letztgenannten Sub-Implikation beinhaltet diesen Satz (theorem 6.11 im Buch):

let $ \ mathcal {h} $ Seien Sie eine Hypotheseklasse von Binärklassifizierern über eine Domäne $ \ Mathcal {x } $ und lassen Sie $ \ tau _ {\ matcal {h}} $ sein Wachstumsfunktion sein (von SAUERs Lemma). Dann für alle $ m \ in \ mathbb {n} $ , für jede Verteilung $ \ mathcal {d} $ < / span> über $ \ matcal {x} \ times \ {0, 1 \} $ und jeder $ \ delta \ in (0, 1) $ : $$ \ fürall h \ in \ matcal {h}: \ mathbb {p} _ {s \ sim \ matcal {d} ^ m} \ linke [| L _ {\ matcal {d}} (h) - l_s (h) | \ leq \ frac {4 + \ sqrt {\ \ \ \ tau _ {\ matcal {h}} (2m))}} {\ delta \ sqrt {2m}} \ Right] \ geq 1 - \ delta $$

Im Beweis für diesen Satz wird gesagt, dass es sofort von der Ungleichheit folgt $$ \ mathbb {e} _ {s \ sim \ matcal {d} ^ m} \ linke [\ sup_ {h \ in \ matcal {h}} | L _ {\ matcal {d}} (h) - l_s (h) | \ RECHTS] \ LEQ \ FRAC {4 + \ sqrt {\ \ \ log (\ tau _ {\ mathcal {h}} (2m))}} {\ sqrt {2m}}, $$ die Tatsache, dass die Zufallsvariable $ \ theta:=sup_ {h \ in \ matcal {h}} | L _ {\ matcal {d}} (h) - l_s (h) | $ ist nicht negative und markovs Ungleichheit.

---

Ich mache jedoch nicht , wie es sofort von diesen Tatsachen folgt. Was vermisse ich?

Answer 1

lass $ x= | l_ \ mathcal {d} (h) - l_s (h) | $ .Die Erklärung zur Erwartung des Supremums von $ x $ impliziert insbesondere, dass für einigen $ M $ $$ \ mathbb {e} [x] \ leq m. $$ Da $ x \ geq 0 $ , impliziert Markovs Ungleichung das $$ \ PR \ LINKEN [X \ GEQ \ FRAC {M} {\ Delta} \ RECHTS] \ LEQ \ DELTA. $$ Das impliziert das $$ \ PR \ LINKS [X \ LEQ \ FRAC {M} {\ Delta} \ RECHTS] \ GEQ \ Pr \ Links [x <\ frac {m} {\ delta} \ RECHTS]= 1 - \ PR \ LINKS [X \ GEQ \ FRAC {M} {\ Delta} \ RECHTS] \ GEQ 1 - \ DELTA. $$