VC寸法が有限の場合、均一な収束の証明

Question

本の中で»機械学習の理解：理論からアルゴリズムまで«は、ベン - ダビデとShalev-Shwartzによって書かれています。理解できない証明があります。背景は、仮説クラス $ \ mathcal {h} $ が有限VCディメンションを持っている場合、それは統一された収束プロパティを楽しんでいることを証明しています。

この意味の証明には、Sauerの補題（有限のVC寸法を持つ仮説クラスがあります。»小さな有効な大きさ«を持つ仮説クラスと、仮説クラスが述べた»有効な大きさ«統一された収束性をお楽しみください。後者のサブ含意の証明には、この定理（本の定理6.11）が含まれます。

$ \ mathcal {h} $ ドメイン上のバイナリ分類器のハイメーシシシスクラスである $ \ mathcal {x $ と $ \ tau _ {\ mathcal {h}} $ } $ （Sauer's Lemmaから）。次に、すべての $ m \ in \ mathbb {n} $ の場合、 $ \ mathcal {d} $ < / SPAN> OVER $ \ mathcal {x} \ hids {0,1 \} $ 、およびすべての $ \ delta \ （0,1）$ ： $$ \ forall h \ \ mathcal {h}：\ mathbb {p} _ {s \ sim \ mathcal {d} ^ m} \左[| l_ {\ mathcal {d}}（h） - L_S（h）| \ leq \ frac {4 + \ sqrt {\ log（\ tau _ {\ mathcal {h}}（2m））}}}}} \ right \ right \ geq 1 - \ delta $$

この定理の証明には、不平等からすぐに続くことが記載されています $$ \ mathbb {e} _ {s \ sim \ mathcal {d} ^ m} \ left [\ sup_ {h \ in \ mathcal {h}} | l_ {\ mathcal {d}}（h） - L_S（h）| \ rique \ frac {4 + \ sqrt {\ log（\ tau _ {\ mathcal {h}}（2m））}}} {\ sqrt {2m}} $$ random変数 $ \ theta：=sup_ {h}} | l_ {\ mathcal {d}}（h） - l_s（h）| $ は、非負の不平等です。

---

しかし、私はではありませんそれらの事実からすぐにどのように続くかを見てください。私は何が足りないのですか？

Answer 1

$ x= | l_ \ mathcal {d}（h） - l_s（h）| $ 。 $ x $ のSupremumの期待に関するステートメントは、特に、いくつかの $ m $ 、 $$ \ mathbb {e} [x] \ LEQ M. $$ $ x \ geq 0 $ 以来、マルコフの不等式はそれを意味します $$ \ pr \ left [x \ geq \ frac {m} {\ delta} \ right] \ leq \ delta。 $$ これはそれを意味します $$ \ pr \ left [x \ leq \ frac {m} {\ delta} \ right] \ geq \ pr \左[x <\ frac {m} {\ delta} \ right]= 1 - \ PR \ Left [X \ GEQ \ frac {m} {\ delta} \ right] \ GEQ 1 - \ Delta。 $$