نظرية فابنيك-تشيرفونينكيس

يترك${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$أن يكون حيزًا قابلاً للقياس . لأي قياس${\displaystyle Q}$على${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$وأي وظائف قابلة للقياس${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$، يُعرِّف

${\displaystyle Qf=\int fdQ}$

سيتم تجاهل مسائل قابلية القياس هنا، وللحصول على مزيد من التفاصيل التقنية، انظر [ ^{1 ] .}${\displaystyle {\mathcal {F}}}$لتكن فئة من الدوال القابلة للقياس${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$وحدد:

${\displaystyle \|Q\|_{\mathcal {F}}=\sup\{\vert Qf\vert \$ :\ f\in {\mathcal {F}}\}.}

يترك${\displaystyle X_{1},\ldots ,X_{n}}$أن تكون عناصر عشوائية مستقلة وموزعة توزيعًا متطابقًا من${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$ثم حدد المقياس التجريبي

${\displaystyle \mathbb {P} _{n}=n^{-1}\sum _{i=1}^{n}\delta _{X_{i}},}$

حيث يرمز δ هنا إلى مقياس ديراك . وينتج عن المقياس التجريبي دالة${\displaystyle {\mathcal {F}}\to \mathbf {R} }$مقدم من:

${\displaystyle f\mapsto \mathbb {P} _{n}f={\frac {1}{n}}(f(X_{1})+...+f(X_{n}))}$

لنفترض الآن أن P هو التوزيع الحقيقي الأساسي للبيانات، وهو غير معروف. تهدف نظرية العمليات التجريبية إلى تحديد الفئات.${\displaystyle {\mathcal {F}}}$والتي تنطبق عليها عبارات مثل ما يلي:

• قانون الأعداد الكبيرة المنتظم :

  ${\displaystyle \|\mathbb {P} _{n}-P\|_{\mathcal {F}}{\underset {n}{\to }}0,}$

أي، كما${\displaystyle n\to \infty }$،

${\displaystyle \left|{\frac {1}{n}}(f(X_{1})+...+f(X_{n}))-\int fdP\right|\to 0}$

بشكل موحد للجميع${\displaystyle f\in {\mathcal {F}}}$.

• نظرية النهاية المركزية الموحدة :

${\displaystyle \mathbb {G} _{n}={\sqrt {n}}(\mathbb {P} _{n}-P)\rightsquigarrow \mathbb {G} ,\quad {\text{in }}\ell ^{\infty }({\mathcal {F}})}$

في الحالة الأولى${\displaystyle {\mathcal {F}}}$يُطلق عليها فئة جليفنكو-كانتيلي ، وفي الحالة الأخيرة (بافتراض${\displaystyle \forall x,\sup \nolimits _{f\in {\mathcal {F}}}\vert f(x)-Pf\vert <\infty }$) الفصل${\displaystyle {\mathcal {F}}}$يُطلق عليه اسم دونسكر أو P- دونسكر. وتُعتبر فئة دونسكر فئة جليفنكو-كانتيلي في الاحتمالات بتطبيق نظرية سلوتسكي .

هذه العبارات صحيحة بالنسبة لحالة واحدة${\displaystyle f}$وفقًا لحجج نظرية الحد المركزي القياسية ، في ظل شروط الانتظام، تكمن الصعوبة في العمليات التجريبية في أنه يتم تقديم عبارات مشتركة لجميع${\displaystyle f\in {\mathcal {F}}}$وبالتالي، وبشكل بديهي، فإن المجموعة${\displaystyle {\mathcal {F}}}$لا يمكن أن تكون كبيرة جدًا، وكما اتضح فإن هندسة${\displaystyle {\mathcal {F}}}$يلعب دوراً بالغ الأهمية.

إحدى طرق قياس حجم مجموعة الدوال${\displaystyle {\mathcal {F}}}$يتمثل ذلك في استخدام ما يسمى بأرقام التغطية . رقم التغطية

${\displaystyle N(\varepsilon ,{\mathcal {F}},\|\cdot \|)}$

هو الحد الأدنى لعدد الكرات${\displaystyle \{g:\|g-f\|<\varepsilon \}}$مطلوب لتغطية المجموعة${\displaystyle {\mathcal {F}}}$(من الواضح هنا أنه يُفترض وجود معيار ضمني بشأن${\displaystyle {\mathcal {F}}}$). الإنتروبيا هي لوغاريتم عدد التغطية.

يُقدَّم أدناه شرطان كافيان، يمكن بموجبهما إثبات أن المجموعة${\displaystyle {\mathcal {F}}}$هو جليفنكو-كانتيلي أو دونسكر.

فصل دراسي${\displaystyle {\mathcal {F}}}$تكون P -Glivenko–Cantelli إذا كانت قابلة للقياس P- مع غلاف F بحيث${\displaystyle P^{\ast }F<\infty }$ويلبي:

${\displaystyle \forall \varepsilon >0\quad \sup \nolimits _{Q}N(\varepsilon \|F\|_{Q},{\mathcal {F}},L_{1}(Q))<\infty .}$

الشرط التالي هو صيغة من مبرهنة دادلي . إذا${\displaystyle {\mathcal {F}}}$هي فئة من الدوال بحيث

${\displaystyle \int _{0}^{\infty }\sup \nolimits _{Q}{\sqrt {\log N\left(\varepsilon \|F\|_{Q,2},{\mathcal {F}},L_{2}(Q)\right)}}d\varepsilon <\infty }$

ثم${\displaystyle {\mathcal {F}}}$هل P -Donsker لكل مقياس احتمالي P بحيث${\displaystyle P^{\ast }F^{2}<\infty }$في التكامل الأخير، تعني الرموز

${\displaystyle \|f\|_{Q,2}=\left(\int |f|^{2}dQ\right)^{\frac {1}{2}}}$.

تعتمد معظم الحجج المتعلقة بكيفية تحديد حدود العملية التجريبية على التناظر، ومتباينات الحد الأقصى والتركيز، والتسلسل. يُعد التناظر عادةً الخطوة الأولى في البراهين، ويُستخدم في العديد من براهين التعلم الآلي لتحديد حدود دوال الخسارة التجريبية (بما في ذلك برهان متباينة VC الذي سيتم مناقشته في القسم التالي). يُعرض هنا:

لننظر في العملية التجريبية:

${\displaystyle f\mapsto (\mathbb {P} _{n}-P)f={\dfrac {1}{n}}\sum _{i=1}^{n}(f(X_{i})-Pf)}$

اتضح أن هناك صلة بين العملية التجريبية والعملية المتناظرة التالية:

${\displaystyle f\mapsto \mathbb {P} _{n}^{0}f={\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(X_{i})}$

العملية المتناظرة هي عملية رادماخر ، بشرط البيانات${\displaystyle X_{i}}$لذلك، فهي عملية شبه غاوسية وفقًا لمتباينة هوفدينغ .

اللمة (التناظر). لكل دالة غير متناقصة ومحدبة Φ: R → R وفئة من الدوال القابلة للقياس${\displaystyle {\mathcal {F}}}$،

${\displaystyle \mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} \Phi \left(2\left\|\mathbb {P} _{n}^{0}\right\|_{\mathcal {F}}\right)}$

يعتمد برهان مبرهنة التناظر على إدخال نسخ مستقلة من المتغيرات الأصلية${\displaystyle X_{i}}$(يُشار إليها أحيانًا باسم العينة الوهمية ) واستبدال القيمة المتوقعة الداخلية للطرف الأيسر بهذه النسخ. بعد تطبيق متباينة جنسن، يمكن إدخال إشارات مختلفة (ومن هنا جاء اسم التناظر) دون تغيير القيمة المتوقعة. يمكن الاطلاع على البرهان أدناه نظرًا لطبيعته التوضيحية. يمكن استخدام طريقة البرهان نفسها لإثبات نظرية جليفنكو-كانتيلي . ^{[ 3 ]}

تتمثل إحدى الطرق النموذجية لإثبات نظريات النهاية المركزية التجريبية في استخدام التناظر أولاً لتمرير العملية التجريبية إلى${\displaystyle \mathbb {P} _{n}^{0}}$ثم استند في حجتك إلى البيانات، مستخدماً حقيقة أن عمليات رادماخر هي عمليات بسيطة ذات خصائص جيدة.

اتضح أن هناك صلة رائعة بين بعض الخصائص التوافقية للمجموعة${\displaystyle {\mathcal {F}}}$وأرقام الإنتروبيا. يمكن التحكم في أرقام التغطية المنتظمة من خلال مفهوم فئات فابنيك-تشيرفونينكيس للمجموعات - أو باختصار مجموعات VC .

لنفترض مجموعة ${\displaystyle {\mathcal {C}}}$من مجموعات جزئية من فضاء العينة${\displaystyle {\mathcal {X}}}$.${\displaystyle {\mathcal {C}}}$يقال إنه يختار مجموعة فرعية معينة${\displaystyle W}$من المجموعة المنتهية${\displaystyle S=\{x_{1},\ldots ,x_{n}\}\subset {\mathcal {X}}}$لو${\displaystyle W=S\cap C}$بالنسبة للبعض${\displaystyle C\in {\mathcal {C}}}$.${\displaystyle {\mathcal {C}}}$يُقال إنها تُحطّم المجموعة S إذا اختارت كل مجموعة فرعية من مجموعاتها الفرعية البالغ عددها 2 ^{^n} . مؤشر VC (مشابه لبُعد VC + 1 لمجموعة مصنفات مختارة بشكل مناسب).${\displaystyle V({\mathcal {C}})}$ل${\displaystyle {\mathcal {C}}}$هو أصغر عدد صحيح n لا يمكن عنده تفتيت أي مجموعة بحجم n بواسطة${\displaystyle {\mathcal {C}}}$.

ثم تنص ليمّة ساور على أن العدد${\displaystyle \Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})}$من المجموعات الفرعية التي تم اختيارها بواسطة فئة VC${\displaystyle {\mathcal {C}}}$يرضي:

${\displaystyle \max _{x_{1},\ldots ,x_{n}}\Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})\leq \sum _{j=0}^{V({\mathcal {C}})-1}{n \choose j}\leq \left({\frac {ne}{V({\mathcal {C}})-1}}\right)^{V({\mathcal {C}})-1}}$

وهو عدد كثير الحدود${\displaystyle O(n^{V({\mathcal {C}})-1})}$من المجموعات الجزئية بدلاً من عدد أُسّي. وهذا يعني بديهياً أن مؤشر VC المحدود يستلزم أن${\displaystyle {\mathcal {C}}}$يتميز ببنية بسيطة ظاهرياً.

يمكن إثبات حد مماثل (بثابت مختلف، وبنفس المعدل) لما يسمى بفئات الرسم البياني الفرعي VC . بالنسبة لدالة${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$الرسم البياني الفرعي هو مجموعة فرعية من${\displaystyle {\mathcal {X}}\times \mathbf {R} }$بحيث:${\displaystyle \{(x,t):t<f(x)\}}$مجموعة من${\displaystyle {\mathcal {F}}}$يُطلق عليه اسم فئة الرسم البياني الفرعي VC إذا كانت جميع الرسوم البيانية الفرعية تشكل فئة VC.

لنفترض مجموعة من دوال المؤشر${\displaystyle {\mathcal {I}}_{\mathcal {C}}=\{1_{C}:C\in {\mathcal {C}}\}}$في${\displaystyle L_{1}(Q)}$بالنسبة للنوع التجريبي المنفصل للمقياس Q (أو ما يعادله لأي مقياس احتمالي Q ). يمكن بعد ذلك إثبات أنه من المثير للدهشة، بالنسبة لـ${\displaystyle r\geq 1}$:

${\displaystyle N(\varepsilon ,{\mathcal {I}}_{\mathcal {C}},L_{r}(Q))\leq KV({\mathcal {C}})(4e)^{V({\mathcal {C}})}\varepsilon ^{-r(V({\mathcal {C}})-1)}}$

علاوة على ذلك، ضع في اعتبارك الغلاف المحدب المتناظر لمجموعة${\displaystyle {\mathcal {F}}}$:${\displaystyle \operatorname {sconv} {\mathcal {F}}}$كونها مجموعة من الدوال من الشكل${\displaystyle \sum _{i=1}^{m}\alpha _{i}f_{i}}$مع${\displaystyle \sum _{i=1}^{m}|\alpha _{i}|\leq 1}$ثم إذا

${\displaystyle N\left(\varepsilon \|F\|_{Q,2},{\mathcal {F}},L_{2}(Q)\right)\leq C\varepsilon ^{-V}}$

ينطبق ما يلي على الغلاف المحدب لـ${\displaystyle {\mathcal {F}}}$:

${\displaystyle \log N\left(\varepsilon \|F\|_{Q,2},\operatorname {sconv} {\mathcal {F}},L_{2}(Q)\right)\leq K\varepsilon ^{-{\frac {2V}{V+2}}}}$

النتيجة المهمة لهذه الحقيقة هي أن

${\displaystyle {\frac {2V}{V+2}}<2,}$

وهذا يكفي تمامًا لكي يتقارب تكامل الإنتروبيا، وبالتالي الفئة${\displaystyle \operatorname {sconv} {\mathcal {F}}}$سيكون P -Donsker.

وأخيرًا، يتم النظر في مثال لفئة الرسم البياني الفرعي VC. أي فضاء متجهي محدود الأبعاد${\displaystyle {\mathcal {F}}}$من الوظائف القابلة للقياس${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$هل الرسم البياني الفرعي VC ذو فهرس أصغر من أو يساوي${\displaystyle \dim({\mathcal {F}})+2}$.

الدليل: خذ${\displaystyle n=\dim({\mathcal {F}})+2}$نقاط${\displaystyle (x_{1},t_{1}),\ldots ,(x_{n},t_{n})}$المتجهات:

${\displaystyle (f(x_{1}),\ldots ,f(x_{n}))-(t_{1},\ldots ,t_{n})}$

تقع هذه العناصر في فضاء جزئي ذي بُعد n − 1 من R ⁿ . خذ متجهًا a ≠ 0 ، وهو متجه متعامد مع هذا الفضاء الجزئي. بالتالي:

${\displaystyle \sum _{a_{i}>0}a_{i}(f(x_{i})-t_{i})=\sum _{a_{i}<0}(-a_{i})(f(x_{i})-t_{i}),\quad \forall f\in {\mathcal {F}}}$

ضع في اعتبارك المجموعة${\displaystyle S=\{(x_{i},t_{i}):a_{i}>0\}}$لا يمكن اختيار هذه المجموعة لأنه إذا كان هناك بعض${\displaystyle f}$بحيث${\displaystyle S=\{(x_{i},t_{i}):f(x_{i})>t_{i}\}}$وهذا يعني أن الطرف الأيسر موجب تمامًا بينما الطرف الأيمن غير موجب.

توجد تعميمات لمفهوم فئة الرسم البياني الفرعي VC، على سبيل المثال يوجد مفهوم البعد الزائف. ^{[ 4 ]}

بالنسبة للتصنيف الثنائي ودالة الخسارة 0/1، لدينا حدود التعميم التالية:

${\displaystyle {\begin{aligned}P\left(\sup _{f\in {\mathcal {F}}}\left|{\hat {R}}_{n}(f)-R(f)\right|>\varepsilon \right)&\leq 8S({\mathcal {F}},n)e^{-n\varepsilon ^{2}/32}\\\mathbb {E} \left[\sup _{f\in {\mathcal {F}}}\left|{\hat {R}}_{n}(f)-R(f)\right|\right]&\leq 2{\sqrt {\dfrac {\log S({\mathcal {F}},n)+\log 2}{n}}}\end{aligned}}}$

بعبارة أخرى، تنص متباينة VC على أنه مع زيادة حجم العينة، بشرط أن${\displaystyle {\mathcal {F}}}$نظرًا لأن بُعد VC محدود، يصبح خطر 0/1 التجريبي مؤشرًا جيدًا لخطر 0/1 المتوقع. لاحظ أن كلا طرفي المتباينتين سيتقاربان إلى 0، بشرط أن${\displaystyle S({\mathcal {F}},n)}$ينمو بشكل متعدد الحدود في n .

إن الصلة بين هذا الإطار وإطار العملية التجريبية واضحة. هنا نتعامل مع عملية تجريبية معدلة.

${\displaystyle \left|{\hat {R}}_{n}-R\right|_{\mathcal {F}}}$

لكن ليس من المستغرب أن تكون الأفكار متطابقة. يعتمد برهان (الجزء الأول من) متباينة VC على التناظر، ثم يستند إلى متباينات التركيز (وخاصة متباينة هوفدينغ ) بناءً على البيانات. يمكن للقارئ المهتم مراجعة الكتاب ^{[ 5 ]،} النظريتين 12.4 و12.5.