نمایش مبدأ برای پیش‌نویس:حداقل سازی ریسک تجربی

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

'''"این مقاله در حال ترجمه از ویکی انگلیسی است'''

'''لطفا حذف نشود."'''

== پیشینه ==
وضعیت زیر را در نظر بگیرید، که مجموعه ای کلی از بسیاری از مشکلات یادگیری تحت نظارت است.ما دو فضای از اشیاء  X و Y داریم و می خواهیم یک تابع را یاد بگیریم

h:X→Y که خروجی آن از X به Y است.برای انجام این کار، ما یک مجموعه آموزشی از n مثال در اختیار داریم<math>(x1,y1),...,(xn,yn)
</math>که در آن x عضو مجموعه X و y عضو مجموعه Y است.

به بیان رسمی تر، فرض می کنیم که یک توزیع احتمال مشترک وجود دارد<math>P(x,y)</math> برروی X و Y و اینکه مجموعه آموزشی از n نمونه تشکیل شده است <math>(x1,y1),...,(xn,yn)</math> بدست آمده از <math>P(x,y)</math> است.توجه داشته باشید که فرض توزیع احتمال مشترک به ما امکان می دهد تا عدم قطعیت در پیش بینی ها را مدل کنیم (مثلاً از نویز در داده ها) زیرا y تابع قطعی x نیست.بلکه یک متغیر تصادفی با توزیع شرطی P (y | x) P(y|x) برای x ثابت است.

همچنین فرض می‌کنیم که یک تابع ضرر واقعی غیر منفی <math>L(\hat{y},y)</math> به ما داده می‌شود که میزان تفاوت پیش‌بینی <math>\hat{y}</math> را اندازه می‌گیرد. یک فرضیه از نتیجه واقعی y است. y ریسک مرتبط با فرضیه h (x) سپس به عنوان انتظار تابع زیان تعریف می شود:

<math>R(h)={\mathbf {E}}[L(h(x),y)]=\int L(h(x),y)\,dP(x,y).</math>

یک تابع ضرر که معمولاً در تئوری استفاده می شود، تابع ضرر 0-1 است:<math>{\displaystyle L({\hat {y}},y)={\begin{cases}1&{\mbox{ if }}\quad {\hat {y}}\neq y\\0&{\mbox{ if }}\quad {\hat {y}}=y\end{cases}}}</math>

هدف نهایی یک الگوریتم یادگیری یافتن یک فرضیه *h در میان یک کلاس ثابت از توابع H  است که ریسک R (h)  برای آن حداقل است.

<math>{\displaystyle h^{*}={\underset {h\in {\mathcal {H}}}{\operatorname {arg\,min} }}\,{R(h)}.}</math>

برای مسائل طبقه بندی، طبقه بندی بیز به عنوان طبقه بندی کننده ای تعریف می شود که ریسک تعریف شده با تابع ضرر 0-1 را به حداقل می رساند.

== Empirical risk minimization ==
به طور کلی، ریسک R (h)  را نمی توان محاسبه کرد زیرا توزیع P (x، y)  برای الگوریتم یادگیری ناشناخته است (این وضعیت به عنوان یادگیری آگنوستیک شناخته می شود). با این حال، می‌توانیم یک تقریبی به نام ریسک تجربی را با میانگین‌گیری تابع ضرر در مجموعه آموزشی محاسبه کنیم. به طور رسمی تر، محاسبه انتظار با توجه به معیار تجربی:<math>{\displaystyle \!R_{\text{emp}}(h)={\frac {1}{n}}\sum _{i=1}^{n}L(h(x_{i}),y_{i}).}</math>اصل تجربی به حداقل رساندن ریسک[1] بیان می کند که الگوریتم یادگیری باید فرضیه <math>\hat{y}</math> را انتخاب کند که ریسک تجربی را به حداقل برساند:

<math>{\displaystyle {\hat {h}}={\underset {h\in {\mathcal {H}}}{\operatorname {arg\,min} }}\,R_{\text{emp}}(h).}</math>
بنابراین الگوریتم یادگیری تعریف شده توسط اصل ERM شامل حل مسئله بهینه سازی فوق است

== Computational complexity ==
به حداقل رساندن ریسک تجربی برای یک مسئله طبقه بندی با یک تابع ضرر 0-1 به عنوان یک مشکل NP-hard شناخته شده است، حتی برای یک دسته نسبتاً ساده از توابع مانند طبقه بندی کننده های خطی.[2] اگرچه، زمانی که حداقل ریسک تجربی صفر باشد، یعنی داده ها به صورت خطی قابل تفکیک هستند، می توان آن را به طور موثر حل کرد.
در عمل، الگوریتم‌های یادگیری ماشین یا با استفاده از یک تقریب محدب برای تابع ضرر 0-1 (مانند از دست دادن لولا برای SVM)، که بهینه‌سازی آسان‌تر است، یا با تحمیل فرضیات بر توزیع P (x, y) P با آن مقابله می‌کنند. (x,y) (و بنابراین دیگر الگوریتم های یادگیری آگنوستیکی نباشند که نتیجه فوق در مورد آنها اعمال می شود)

== منابع ==
V. Vapnik (1992). ''Principles of Risk Minimization for Learning Theory.''

V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu (2009).