پیچیدگی نمونه - ویکی‌پدیا، دانشنامهٔ آزاد

پیچیدگی نمونه یک الگوریتم یادگیری ماشین، برابر است با تعداد نمونه‌های یادگیری که برای موفقیت الگوریتم لازم است. به صورت دقیق‌تر، پیچیدگی نمونه برابر است با حداقل تعداد نمونه‌های لازم، تا تابع خروجی الگوریتم با احتمالی نزدیک به «یک» در فاصله‌ای نزدیک به «صفر» از تابع هدف قرار گیرد. پیچیدگی نمونه به دو صورت در نظر گرفته می‌شود:

نوع ضعیف؛ که در آن فرضی روی توزیع احتمال ورودی و خروجی در نظر گرفته می‌شود.
نوع قوی؛ که در آن فرضی روی توزیع احتمال ورودی و خروجی الگوریتم گذاشته نمی‌شود.

طبق قضیه از ناهار مجانی خبری نیست می‌دانیم که در حالت کلی، پیچیدگی نمونه نوع قوی بی‌نهایت است. به عبارت دیگر هیچ الگوریتم یادگیری‌ای وجود ندارد که بتواند با تعداد محدودی نمونه هر تابع هدفی را یاد بگیرد. به‌هرحال اگر خود را به توابع خاصی مانند توابع خطی یا توابع دودویی محدود کنیم؛ پیچیدگی نمونه محدود است و به بعد وی‌سی مربوط می‌شود.^[۱]

تعریف[ویرایش]

اگر $X$ را مجموعه ورودی‌های ممکن و $Y$ را مجموعه خروجی‌های ممکن در نظر بگیریم، $Z$ را به صورت ضرب دکارتی این دو مجموعه $X\times Y$ تعریف می‌کنیم. برای مثال برای مسئله دسته‌بندی دو‎کلاسه، $X$ یک فضای برداری متناهی و $Y$ برابر با مجموعه $\{0,1\}$ است.

${\mathcal {H}}$ را مجموعه‌ای از توابع $h$ که $h:X\rightarrow Y$ است در نظر می‌گیریم. یک الگوریتم یادگیری $A$ عبارت‌است از تابعی از $Z^{*}$ به ${\mathcal {H}}$ . به‌عبارت دیگر یک الگوریتم یادگیری تعداد محدودی از نمونه‌های یادگیری را دریافت می‌کند و یک تابع $h:X\rightarrow Y$ را به عنوان خروجی برمی‌گرداند. یک تابع هزینه $L:X\times Y\rightarrow R^{+}$ را در نظر می‌گیریم، برای مثال این تابع می‌تواند تابع هزینه خطای مربعات $L(y,y')=(y-y')^{2}$ باشد. برای یک توزیع احتمال $D$ داده‌شده روی $X\times Y$ متوسط خطای تابع $h$ ، که یکی از اعضای کلاس فرضیه ${\mathcal {H}}$ است، به صورت زیر تعریف می‌شود.

${\mathcal {E}}(h):=\mathbb {E} _{D}[Loss(h(x),y)]=\int _{X\times Y}Loss(h(x),y)\,dD(x,y)$

داده‌های آموزشی یک دنباله $m$ تایی از زوج مرتب‌های $(x,y)$ به صورت $S_{m}=((x_{1},y_{1}),...,(x_{m},y_{m}))\sim D^{m}$ تشکیل می‌دهند، که تمامی آن‌ها به صورت یکسان و مستقل از توزیع $D$ نمونه‌برداری شده‌اند. یک الگوریتم یادگیری $A$ به هر دنباله از داده‌های آموزشی $S_{m}$ یکی از اعضای کلاس فرضیه ${\mathcal {H}}$ را نسبت می‌دهد. کمینه خطای کلاس فرضیه ${\mathcal {H}}$ به صورت زیر تعریف می‌شود.

${\mathcal {E}}_{\mathcal {H}}^{*}={\underset {h\in {\mathcal {H}}}{\inf }}{\mathcal {E}}(h)$

$h_{m}=A(S_{m})$ را خروجی الگوریتم به‌ازای داده‎های آموزشی $S_{m}$ در نظر می‌گیریم( $h_{m}$ یک متغیر تصادفی است که به متغیر تصادفی $S_{m}$ که از توزیع $D^{m}$ نمونه‌برداری شده‌است بستگی دارد). به الگوریتم $A$ ، قاطع گفته می‌شود اگر ${\mathcal {E}}(h)$ به صورت احتمالی به ${\mathcal {E}}_{\mathcal {H}}^{*}$ میل کند. به‌عبارت دیگر به ازای هر $\epsilon >0$ و $\delta >0$ عدد صحیح و مثبتی مانند $M$ وجود داشته‌باشد که به‌ازای هر $m\geq M$ داشته‌باشیم

$\Pr _{D^{m}}[{\mathcal {E}}(h_{m})-{\mathcal {E}}_{\mathcal {H}}^{*}>\epsilon ]<\delta .$

به‌ازای هر الگوریتم یادگیری $A$ و $\epsilon ,\delta ,D$ داده شده، پیچیدگی نمونه، $M_{A}(\epsilon ,\delta ,D)$ را کمترین مقدار $M$ تعریف می‌کنیم که رابطه بالا به‌ازای آن درست باشد. اگر الگوریتم $A$ قاطع نباشد، آن‌گاه $M_{A}(\epsilon ,\delta ,D)=\infty$ ، هم‌چنین اگر الگوریتمی مانند $A$ وجود داشته باشد که $M_{A}(\epsilon ,\delta ,D)$ عددی محدود باشد، می‌گوییم کلاس فرضیه ${\mathcal {H}}$ قابل یادگیری است.^[۲]

یادگیری احتمالاً تقریباً صحیح و پیچیدگی نمونه[ویرایش]

پیچیدگی نمونه نشان‌دهنده میزان قاطعیت یک الگوریتم است، یعنی به ازای میزان دقت داده‌شده $\epsilon$ و میزان اطمینان داده‌شده $\delta$ الگوریتم به حداقل $M(\epsilon ,\delta ,D)$ نمونه آموزشی نیاز دارد تا بتواند با احتمال حداقل $1-\delta$ ، خروجی‌ای با خطایی کمتر از $\epsilon$ تولید کند. در مدل یادگیری احتمالاً تقریباً صحیح پیچیدگی نمونه باید تابعی چند جمله‌ای از ${\frac {1}{\epsilon }}$ و ${\frac {1}{\delta }}$ باشد. به عبارت دیگر باید داشته باشیم:^[۳]

$M(\epsilon ,\delta )\in O(Poly({\frac {1}{\delta }},{\frac {1}{\epsilon }})).$

کرانی برای پیچیدگی نمونه فضای فرضیه متناهی[ویرایش]

اگر ${\mathcal {H}}$ یک مجموعه متناهی از فرضیه‌ها باشد و مجموعه آموزشی $S_{m}=((x_{1},y_{1}),...,(x_{m},y_{m}))$ به صورت یکسان و مستقل از توزیع $D$ نمونه برداری شده باشد آنگاه به‌ازای هر $0<\epsilon <{\frac {1}{2}}$ و $0<\delta <{\frac {1}{2}}$ اگر الگوریتم $A$ یکی از فرضیه‌های سازگار $h\in {\mathcal {H}}$ را به عنوان خروجی تولید کند(فرضیه‌ای سازگار است که روی تمام نمونه‌های آموزشی با تابع هدف یکسان باشد) آنگاه

$M_{A}(\epsilon ,\delta ,D)\leq {\frac {1}{\epsilon }}(\ln |{\mathcal {H}}|+\ln {\frac {1}{\delta }}).$

اثبات[ویرایش]

$R(h)=\Pr _{x,y\sim D}[y\neq h(x)]$

${\hat {R}}(h)={\frac {1}{m}}\sum _{i=1}^{n}\mathbb {I} (h(x_{i})\neq y_{i})$

می‌دانیم که فرضیه $A(S_{m})$ سازگار است بنابراین ${\hat {R}}(A(S_{m}))=0$

$\Pr[R(A(S_{m}))>\epsilon ]=\Pr[\exists h\in {\mathcal {H}}|{\hat {R}}(h)=0\wedge R(h)>\epsilon$

$=\Pr {\biggl [}\bigcup _{h\in {\mathcal {H}}}{\hat {R}}(h)=0\wedge R(h)>\epsilon {\biggr ]}$

با توجه به نابرابری بول می‌دانیم که:

$\Pr {\biggl [}\bigcup _{i}A_{i}{\biggr ]}\leq \sum _{i}\Pr(A_{i}).$

بنابراین:

$\Pr[R(A(S_{m}))>\epsilon ]\leq \sum _{h\in {\mathcal {H}}}\Pr[{\hat {R}}(h)=0\wedge R(h)>\epsilon ]\leq \sum _{h\in {\mathcal {H}}}\Pr[{\hat {R}}(h)=0|R(h)>\epsilon ]$

$\sum _{h\in {\mathcal {H}}}(1-\epsilon )^{m}=|{\mathcal {H}}|(1-\epsilon )^{m}\leq |{\mathcal {H}}|e^{-m\epsilon }<\delta$

$\Rightarrow m\geq {\frac {1}{\epsilon }}[\ln |{\mathcal {H}}|+\ln {\frac {1}{\delta }}]\Rightarrow M_{A}(\epsilon ,\delta ,D)\leq {\frac {1}{\epsilon }}[\ln |{\mathcal {H}}|+\ln {\frac {1}{\delta }}]$

^[۴]

منابع[ویرایش]

↑ Vapnik, Vladimir (1998), Statistical Learning Theory, New York: Wiley.
↑ Rosasco, Lorenzo (2014), Consistency, Learnability, and Regularization, Lecture Notes for MIT Course 9.520.
↑ M.Mitchell, Tom (1997). Machine Learning. p. 206.
↑ M.Mitchell, Tom (1997). Machine Learning. p. 209.

[:0-1] Vapnik, Vladimir (1998), Statistical Learning Theory, New York: Wiley.

[Rosasco-2] Rosasco, Lorenzo (2014), Consistency, Learnability, and Regularization, Lecture Notes for MIT Course 9.520.

[Mitchell-3] M.Mitchell, Tom (1997). Machine Learning. p. 206.

[Mitchell2-4] M.Mitchell, Tom (1997). Machine Learning. p. 209.

[۱]

[۲]

[۳]

[۴]