فصل 2 هندسه پیشرفته vladlen

اپسیلون-نت و ابعاد VC

-اپسیلون نت

کاربرد در ساختارهای هندسی تصادفی

تابع X با احتمال m را در نظر بگیرید. اکثرا m یکنواخت است. یک مجموعه از زیرمجموعه X را F بنامید. (X,F) را یک سیستم مجموعه (set system) می نامند. (اگر X یک مجموعه متناهی باشد به آن ابرگراف هم می گویند.) یک اپسیلون-نت برای (X,F) مجموعه ای است که همه ی اعضای با m بیشتر از اپسیلون از مجموعه های F را شامل می شود.

مثال: یک set system متناهی (X,F) که در آن تعداد اعضای X برابر n است و تابع احتمال یکنواخت است (m(S) =|S|/n). یک 1/r-نت (برای r طبیعی مثبت) برای (X,F) زیرمجموعه N از X است که با همه ی اعضای F که حداقل n/r عضو دارند اشتراک ناتهی دارد.

اپسیلون-نت های کوچک برای ما جالب هستند. مخصوصا به ازای اپسیلون ثابت، می خواهیم یک اپسیلون-نت با اندازه ی ثابت پیدا کنیم! یعنی اندازه ی آن به اپسیلون وابسته باشد اما به set system وابسته نباشد. این همیشه ممکن نیست ولی معمولا ممکن است. برای توضیح کلاسی از ست سیستم ها نیاز به که اپسیلون-نت های کوچک دارند نیاز به تعریف VC-بعد داریم.

2.2. تعریف VC-بعد

VC-بعد یک پارامتر عددی برای ست سیستم است که نشان می دهد که سیستم چقدر خوش رفتار است. یک ست سیستم (X,F) و زیرمجموعه Y از X داده شده است محدود کردن F روی Y مجموعه ی F|y است که اشتراک مجموعه های F با مجموعه ی Y است.

تعریف: یک ست سیستم (X,F) و زیر مجموعه A از X  (تعریف بالا) را توسط F شکسته شده می نامیم اگر هر زیرمجموعه A اشتراک یک عضو F با A باشد؛ یعنی F|y = 2^A. بعد VC برای F بزرگترین زیرمجموعه از X است که با F شکسته می شود.

مثال: X را صفحه اقلیدسی (دو بعدی) و F1 را مجموعه همه ی چندضلعی های محدب در صفحه و F2 را مجموعه ی همه ی نیم صفحه ها فرض کنید. ست سیستم (X,F1) بعد VC بینهایت دارد. یک مجموعه A به دلخواه بزرگ از صفحه که محدب باشد در نظر بگیرید. هر عضو A' از A می تواند به صورت اشتراک A با یک چندضلعی محدب دیده شود.

اما ست سیستم (X,F2) تعداد بعد VC آن 3 است.

*تابع شکست

ماکسیمم تعداد اعضای F|y به ازای همه ی مجموعه های m عضوی از X را تابع شکست ست سیستم (X,F) به ازای m می نامند.

*اپسیلون نمونه

به ازای ست سیستم (X,F) ، یک زیرمجموعه N از X را اپسیلون نمونه برای (X,F) می نامیم اگر به ازای هر عضو F مثل S داشته باشیم: اختلاف نسبت اشتراک N و S به تعداد اعضای N و m(S) کمتر مساوی اپسیلون باشد.

*قضیه اپسیلون نمونه

به ازای ست سیستم (X,F) که dim(F) <= d که دی بزرگتر مساوی 2 و آر بزرگتر مساوی 2 که آر یک پارامتر است یک 1/r-نمونه برای (X,F) با اندازه ی حداکثر Cdr^2 ln r وجود دارد که C یک ثابت مطلق است.