پیچیدگی نمونه

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

## تعریف
اگر 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] 

به‌ازای هر الگوریتم یادگیری 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 قابل یادگیری است.

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

300px|بندانگشتی|چپ|فضای فرضیه، فرضیه‌های سازگار، فرضیه‌های سازگار با خطای بالا
پیچیدگی نمونه نشان‌دهنده میزان قاطعیت یک الگوریتم است، یعنی به ازای میزان دقت داده‌شده \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  و 0  اگر الگوریتم 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] \le \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} 

\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}]

## منابع

رده:آمار
رده:نظریه یادگیری محاسباتی
رده:هوش مصنوعی
رده:یادگیری
رده:یادگیری ماشین