خطای تعمیم

در کاربردهای یادگیری نظارت شده در یادگیری ماشینی، خطای تعمیم (به انگلیسی: Generalization error) معیاری برای ارزیابی میزان دقت یک الگوریتم در پیش‌بینی داده‌های از پیش دیده نشده‌ است. به دلیل این که الگوریتم‌های یادگیری توسط نمونه‌های محدودی ارزیابی می‌شوند، ارزیابی این الگوریتم‌ها به خطای نمونه‌گیری حساس است. در نتیجه، معیارهای پیش‌بینی با توجه به داده‌های کنونی ممکن است اطلاعات جدیدی در مورد توانایی پیش‌بینی در داده‌های جدید ارائه نکند. با اجتناب از بیش‌برازش می‌توان خطای تعمیم را کاهش داد. عملکرد یک الگوریتم یادگیری ماشین با تجسم نمودارهایی به نام منحنی فراگیری انجام می‌پذیرد که خطای تعمیم را در فرایند یادگیری تخمین می‌زنند.

تعریف

هدف در یک مسئلهٔ یادگیری، یافتن تابع $f_{n}({\vec {x}})$ است که با توجه به دادهٔ ورودی ${\vec {x}}$، خروجی $y$ را پیش‌بینی می‌کند. زیرنویس $n$ نشان می‌دهد که تابع $f_{n}$ براساس مجموعه‌ای شامل $n$ داده ساخته شده‌است. خطای تعمیم، $I[f]$ برای تابع $f$، روی تمام مقادیر ${\vec {x}}$ و $y$ برابر است با:

$I[f]=\int _{X\times Y}V(f({\vec {x}}),y)\rho ({\vec {x}},y)d{\vec {x}}dy,$

که در آن $V$، تابع هزینه و $\rho ({\vec {x}},y)$، توزیع احتمال توأم برای ${\vec {x}}$ و $y$ است.

بدون دانستن توزیع احتمال توأم، $\rho$ محاسبهٔ مقدار $I[f]$ غیرممکن است. در عوض، می‌توانیم خطا را روی داده‌های نمونه محاسبه کنیم که به آن خطای تجربی می‌گویند. خطای تجربی با دانستن $n$ داده برابر است با:

$I_{n}[f]={\frac {1}{n}}\sum _{i=1}^{n}V(f({\vec {x}}_{i}),y_{i})$

و یک الگوریتم تعمیم‌پذیر خواهد بود اگر:

$\lim _{n\rightarrow \infty }I[f]-I_{n}[f]=0$

خطای تعمیم $I[f_{n}]$، برای یک تابع وابسته به دادهٔ $f_{n}$ که توسط یک الگوریتم یادگیری بر اساس نمونه محاسبه شده‌است، از اهمیت زیادی برخوردار است. با توجه به این که محاسبهٔ مستقیم $I[f_{n}]$ نیازمند دانستن توزیع احتمال است که ناشناخته است، هدف بسیاری از مسائل در نظریه یادگیری آماری محدود کردن یا مشخص کردن تفاوت خطای تعمیم و خطای تجربی است:

$P_{G}=P(I[f_{n}]-I_{n}[f_{n}]\leq \epsilon )\geq 1-\delta _{n}$

در نتیجه، هدف مشخص کردن احتمال $1-\delta _{n}$ است که بتوانیم خطای تعمیم را، با جمع خطای تجربی و یک کران خطا $\epsilon$ (در حالت کلی وابسته به $\delta$ و $n$) محدود کنیم. در بسیاری از الگوریتم‌ها، نشان داده شده‌است که یک الگوریتم، در صورتی که معیارهای ثبات خاصی را برآورده کند، دارای مرزهای تعمیم است. به‌طور خاص، اگر الگوریتمی متقارن باشد (ترتیب ورودی‌ها بر نتیجه تأثیری نگذارد)، تابع هزینهٔ محدودی داشته باشد و دو شرط پایداری را برآورده کند، تعمیم می‌یابد. این شرایط را می‌توان به صورت زیر بیان کرد:

پایداری اعتبارسنجی متقابل یک‌طرفه (به انگلیسی: Leave-one-out cross-validation)

الگوریتم $L$ این ثبات را خواهد داشت اگر به ازای هر $n$، وجود داشته باشد $\beta _{CV}^{(n)}$ و $\delta _{CV}^{(n)}$ که:

$\forall i\in \{1,...,n\},\mathbb {P} _{S}\{|V(f_{S^{i}},z_{i})-V(f_{S},z_{i})|\leq \beta _{CV}^{(n)}\}\geq 1-\delta _{CV}^{(n)}$

و $\beta _{CV}^{(n)}$ و $\delta _{CV}^{(n)}$ زمانی که $n\rightarrow \infty$ به صفر میل کنند.

پایداری امیدریاضی اعتبارسنجی یک‌طرفه (به انگلیسی: Expected-leave-one-out error Stability)

الگوریتم $L$ این ثبات را خواهد داشت اگر به ازای هر $n$، وجود داشته باشد $\beta _{EL}^{m}$ و $\delta _{EL}^{m}$ که:

$\forall i\in \{1,...,n\},\mathbb {P} _{S}\left\{\left|I[f_{S}]-{\frac {1}{n}}\sum _{i=1}^{N}V\left(f_{S^{i}},z_{i}\right)\right|\leq \beta _{EL}^{(n)}\right\}\geq 1-\delta _{EL}^{(n)}$

و $\beta _{EL}^{(n)}$ و $\delta _{EL}^{(n)}$ زمانی که $n\rightarrow \infty$ به صفر میل کنند.

الگوریتم‌های پایدار اثبات‌شده (به انگلیسی: Algorithms with proven stability)

ثابت شده‌است که تعدادی از الگوریتم‌ها پایدار هستند، و در نتیجه خطای تعمیم آن‌ها محدود است. فهرستی از این الگوریتم‌ها و مقالاتی که پایداری آن‌ها را ثابت کرده‌اند، اینجا موجود است.

ارتباط با بیش‌برازش

مقالهٔ اصلی: بیش‌برازش

این شکل، رابطه بین بیش‌برازش و خطای تعمیم را نشان می‌دهد I[f_n] - I_S[f_n]. نقاط داده از رابطه y = x با نویز سفید اضافه شده به مقادیر y تولید شده‌اند.

مفاهیم خطای تعمیم و بیش‌برازش به هم مرتبط هستند. بیش‌برازش زمانی اتفاق می‌افتد که تابع $f_{S}$ به نویز داخل نمونه‌ها حساس شود. در نتیجه، این تابع روی مجموعهٔ آموزشی به خوبی عمل می‌کند، اما روی داده‌های دیگر که از توزیع احتمال مشترک $x$ و $y$ هستند، به خوبی عمل نمی‌کند؛ بنابراین، هرچه بیش‌برازش بیشتر باشد، خطای تعمیم هم بزرگتر خواهد بود.

میزان بیش‌برازش را می‌توان با استفاده از روش اعتبارسنجی متقابل محاسبه کرد، که نمونه‌ها را به نمونه‌های آموزشی و نمونه‌های آزمایشی تقسیم می‌کند. سپس مدل بر روی نمونه‌های آموزشی، آموزش داده می‌شود و بر روی نمونه‌های آزمایشی، ارزیابی می‌شود. نمونه‌های آزمایشی قبلاً توسط الگوریتم دیده نشده‌اند، بنابراین یک مجموعه نمونهٔ تصادفی از توزیع احتمال مشترک $x$ و $y$ خواهد بود. این مجموعه از نمونه‌های آزمایشی، به ما اجازه می‌دهد تا خطای مورد انتظار را تقریب بزنیم و تخمین خوبی از خطای تعمیم داشته باشیم.

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

یافتن تابعی که بیش‌برازش نداشته باشد، در تضاد با هدف یافتن تابعی است که به اندازه کافی پیچیده باشد تا ویژگی‌های داده‌ها را به تصویر بکشد. این به عنوان مبادله بایاس و واریانس معروف است. ساده نگه داشتن یک تابع برای جلوگیری از بیش‌برازش ممکن است باعث ایجاد بایاس در پیش‌بینی‌های به‌دست‌آمده شود، در حالی که پیچیده‌تر بودن آن منجر به بیش‌برازش و واریانس بیشتر خواهد شد و به حداقل رساندن هر دو به‌طور همزمان، غیرممکن است.

جستارهای وابسته

• یادگیری ماشینی
• یادگیری نظارت‌شده
• بیش‌برازش