ارزیابی فرضیه ها

صفحه 1:
ارزیابی فرضیه ها ۱ Ghiqv 

صفحه 2:
یک الگوریتم یادگیری با استفاده از داده های آموزشی فرضیه ای را بوجود میآورد . قبل از استفاده از این فرضیه ممکن است که لازم شود تا دقت این فرضیه مورد ارزیابی قرار گیرد. Data Learning ———~ Hypothesis Algorithm Performance Assessment اينكار از دو جهت أهميت دارد: 

صفحه 3:
اروشهای آماری در اين فصل سعی میشود تا روشهای آماری مناسب برای حدس زدن دقت فرضیه ها معرفی گردند. مبنای کار در جهت پاسخگوئی به سه سوال زیر است: اگر دقت یک فرضیه برای داده های محدودی معلوم باشد دقت آن برای سایر مثالها چه قدر خواهد بود؟ اگر یک فرضیه برای داده های محدودی بهتر از فرضیه دیگری عمل کند احتمال اینکه این وضعیت در حالت کلی نیز صادق باشد چقدر است؟ وقتی که داده آموزشی اندکی موجود باشد بهترین راه برای اينکه هم فرضیه را یاد بگیریم و هم دقت آنرا اندازه گیری کنیم چیست؟ 

صفحه 4:
اکمی داده های آموزشی ‎٩‏ وقتی که داده آموزشی محدود باشد این امکان وجود دارد که این مثالها نشان دهنده توزیع کلی داده ها نباشند ‎ ‎ ‎ ‎ 

صفحه 5:
مشکل کمی داده *_ وقتی که یادگیری با استفاده از داده های محدودی انجام میشود دو مشکل ممکن است رخ دهند: Oius ia the eptvocte © دقت یک فرضیه بر روی مثالهای آموزشی تخمین مناسبی برای دقت آن برای مثالهای نادیده نیست. زیرا فرضیه یاد گرفته شده بر اساس اين داده ها برای مثالهای آتی بصورت همم عمل خواهد نمود. برای رهائی از این امر میتوان از مجموعه داده ها ی تست استفاده کرد. © وه عا دز نون حنی با وجود استفاده از مجموعه تست این امکان وجود دارد که خطای اندازه گیری شده با خطای واقعی اختلاف داشته باشد 

صفحه 6:
Ores ud Ourtcure tn the Csivate 5 Estimated Variance ‏سس(‎ Accuracy seis ~—~True accuracy sample size 

صفحه 7:
:؟ اتخمين دقت فرط * در یک مثال یادگیری میتوان برای فضای مثالهای ورودى يك تابع توزیع احتمال نامعلوم () در نظر گرفت که احتمال رخداد هر نمونه »«را ‎p(x) b‏ مشخص مینماید. NTS Input Space X p(X) © در اینصورت با دو سوال زیر مواجه هستیم: خطای احتد تخت 

صفحه 8:
#: خطای نمونه و خطای واقعی خطای نمونه عبارت است از خطای فرضیه روی مجموعه مثالهای موجود ) آموزشی و یا تست( خطای نمونه فرضیه :1 نسبت به تابع هدف ۶ و داده نمونه ‏ بصورت زیر بیان میشود: ((( )2۵ 40 -() ,سس كه در ان تعداد مثالهای « ومقدار ((مم,(م))۵ برابر با ۵ است اكر ()>ا + ()*و در غير اینصورت برابر با ) است. 

صفحه 9:
#: اخطای نمونه و خطای واقعی ‎٩‏ خطای واقعی © عبارت است از خطای فرضیه روی مجموعه تمام مثالهای با توزیع نامعلوم 0) و برابر است با احتمال اينکه یک نمونه تصادفی به غلط دسته بندی شود. خطای واقعی فرضیه | نسبت به تابع هدف. ۶ و داده با توزیع 0) بصورت زیر بیان میشود: ‎ ۳([‏ (آم۳۳) -()مس< ‎Se a ee‏ را سا ‏ات وا نع شع در بج بو رتراك ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 10:
* یک مجموعه داده0 تائی با توزیع احتمال زیر وجود دارد: 060 - 0. 06 - 0 00(۶ ۵۸ 0۵ 0.4 = 0۵ 0.6 - رمعم فرضیه :| برای مجموعه نمونه [26۳ ,2 ,66 ,060میتواند 6 ,6 ,0 را بدرستی دسته بندی کند ولی قادربه دسته بندی صحیح 66 نیست. دراین صورت خطای نمونه برابر است با: 14 )0 +0 + 0 + 0( 2 1 2 0.66 اگر این فرضیه برای 26 صحیح و برای 0(نادرست باشد در اینصورت خطای واقعی برابر است با: 0:0۰ + ۵.۵0 + ۵:0 + ۵:0 + )0.0 + 060 

صفحه 11:
فاصله اطمینان برای فرضیه های با مقادیر گسته اگرشرایط زیر برقرار باشند: * نمونه 6 دارای ب مثال باشد که مستقل از یکدیگر و مستفل از برپایه توزیع احتمال () انتخاب شده باشند و 96 < ب باشد و #فرضيه +| منجر به , خطا برروئ اين مثالها گردد رن سر تحت اين شرايط میتوان بر پایه قضایای آماری ادعا نمود که _ اگر اطلاعات بیشتری موجود نباشد. محتملترین مقدار برای (4),جسجج برابر با (ج/),سسمر خواهد ae ‏وف د رم تررق‎ SEO” error” ‏ج. با احتمال ©©96 خطاى واقعى بين فاصله زير قرار دارد‎ 2 

صفحه 12:
© فرض كنيد كه < دارای 0ب مثال بوده و فرضیه | منجر به 08 خطا بر روی اين داده شود. در اینصورت: * خطای نمونه برابر است با 0,-0//-() ,سس #اگر اين آزمایش را بارها و بارها برای 620 نمونه جدید تکرار کنیم متوجه خواهیم شد كه در 9696 مواقع خطای محاسبه شده در فاصله زیر قرار خواهد داشت: 0.30+(1.96x.07 =0.30+.14 

صفحه 13:
© عبارت فوق را میتوان بجای فاصله اطمینان 9۵90 برای هر فاصله دیگری نظیر ‎%D‏ نیز ذکر نمود: errofi+ 2 ‏قزم جع‎ 2 errof# ۰ مقدار ثابت 0 برای درصدهای مختلف را میتوان از جدول زیر بدست آورد: 68% 80% 90% 95% 98% 99% 7 1.00 1.28 1.64 1.96 2.58 © اين تقريب زمانى بهترا را دارد که: © < (لا) سد - 0)ل/) مده 

صفحه 14:
555 امقدمه ای بر تتوری نمونه برداری # مروری بر بحثهای زیر « میانگین ۶ واریانس © توزیع دوجمله ای ۶ توزیع نرمال ‎٩‏ فواصل یک طرفه و دو طرفه 

صفحه 15:
0 خطا © سوال: تاثير اندازه داده هاى نمونه بر اختلاف بين خطاى نمونه و خطاى واقعى جيست؟ * در واقع ياسخ اين سوال را متخصصين آمار داده اند! © ميتوان اندازه كيرى خطاى نمونه را به آزمايشى با نتيجه تصادفى تشبيه كرد. اكر به دفعات » نمونه با توزيع احتمال 0) بصورت تصادفى انتخاب و خطاى نمونه براى هر كدام اندازه كيرى شودء بعلت متفاوت بودن نمونه ها مقدار خطا نيز متفاوت خواهد بود. نتيجه حاصل از هر آزمايش يك متغير تصادفى خواهد بود. © جنين آزمايشى را ميتوان با استفاده از توزيع دو جمله اى توصيف نمود. 

صفحه 16:
توزیع دو جمله ای برای آزمایشاتی استفاده میشود که دارای خواص زير باشند: آزمایش به تعداد ب دفعه تکرار شود ب مقداری ثابت و ازقبل دانسته است. هر آزمایش دارای دو نتیجه درست و یا غلط باشد. آزمایشات مستقل از همدیگر باشند» به نحویکه نتیجه یک آزمایش تاثیری بر سایر آزمایشات نداشته باشد. احتمال وقوع نتیجه درست برای تمام آزمایشات ثابت باشد. 

صفحه 17:
:: امثال در پرتاب یک سکه به تعداد 60 دفعه: u=O ۶ © آزمايش داراى دو نتيجه شير يا خط است © نتيجه هر يرتاب سكه مستقل از يرتاب هاى قبلى است © احتمال آمدن شير براى هر يرتاب 1/2)-م است 

صفحه 18:
:: احتمال دوجمله ای ‎٩‏ احتمال وقوع ‏ موفقیت در () بار تکرار یک آزمایش از رابطه زیر محاسبه میشود: ‎An= ae aa )1 37* ‏9 که در آن م احتمال وقوع موفقیت در هر بار تکرار آزمایش ‎ ‏توزیع دوجمله ای برای عم ,0و ‎10 20 30 40 

صفحه 19:
© احتمال آمدن 0 خط در 0 بار پرتاب یک سکه چقدر است؟ p=5 =a a 2)1- 5-0 

صفحه 20:
£5 اخطای نمونه برداری این خطا را میتوان با پرتاب سکه مقایسه نمود: # پرتاب سکه و دیدن یک خط> انتخاب یک نمونه از ۱ 3 * احتمال اينکه در یک پرتاب واحد یک خط داشته باشیم» احتمال اینکه ایک نمونه غلط ارزیابی شود ۶ دیدن تعداد « خط در () بار پرتاب سکه > تعداد ارزیابی های غلط از بین () نمونه انتخاب شده 0 و تعیین اينکه آیا ب آنرا غلط ارزیابی میکند یا نه 

صفحه 21:
32° امیانگین ‎٩‏ مقدارمیانگین ) و یا (صاه() لصعم<) یک متغیر تصادفی ۷ که ممکن است مقادیر بم...,0, را داشته باشد عبارت است انه ‎Of] = Ev, PY) ‏* برای یک متغیر تصادفی با توزیع دوجمله ای اين مقدار برابر ‏است با: ‏ص - 6۳۷ 

صفحه 22:
واریانس ‎٩‏ واریانس گستردگی توزیع احتمال و فاصله متغیر تصادفی از مقدار میانگین را مشخص میکند. واریانس یک متغیر تصادفی ‎YY‏ عبارت است از: ‎OofY] = Ef(r-E[r]F] ‏© ريشه دوم واريانس انحراف معیار نامیده میشود. ‏© برای یک متغیر تصادفی با توزیع دوجمله ای اين مقادیر برابراند با: ‏۵ -<رن (ر -ر ۲۵2/11 

صفحه 23:
۹ © اگر ‏ تعداد خطا ی فرضیه برای نمونه ای با اندازه ب باشد در اینصورت: ‎=rfowd error (kh) =7‏ ()ن بر ‎p a8 ©‏ احتمال دسته بندی غلط یک نمونه انتخاب شده از 0) است ‎٩‏ متخصصین آمار ()یسسم را یک تخمین زننده ‏اختلاف بین مقدار تخمین زده شده و مقدار واقعی بایاس تخمین نامیده میشود م - [7]) © اگر مقدار بایاس صفر باشد» تخمین زننده بدون بایاس نامیده ميشود. 

صفحه 24:
أ اندراف معیار خطای نمونه 9 اگر در یک نمونه » عضوی تعداد « خطا داشته باشیم. انحراف معیار خطای نمونه برابر است با | _ 0 _ ‎Cerro” n\n‏ * اين مقدار را میتوان بصورت زیر تقریب زد: ~(errox)t- errox)) O errof n 

صفحه 25:
23 افاصله اطمینان * برای یک توزیع دوجمله ای مقدار میانگین برابر با (؟ا).م مج و مقدارانحراف معیار برابر است با errox)0- errox)) O error ~ 7 *۶ از اینرو برای بدست آوردن فاصله اطمینان 9۵6 میبایست فاصله ای حول میانگین پیدا کینم که 7۵0 احتمال را در بر داشته باشد. © از آنجانیکه برای توزیع دوجمله ای محاسبه اين مقدار مشکل بوده و از طرفی از آنجائیکه برای نمونه های زیاد توزیع دوجمله ای به توزیع نرمال نزدیک میشود. میتوان برای محاسبه فاصله اطمینان از توزیع نرمال بهره گرفت 

صفحه 26:
برای توزیع نرمال با میانگین و واریانس » فاصله اطمینان ‎٩660‏ بصورت زیر است: از اینرو تقریب ما بصورت زیر خواهد بود: زره و ررو| 2۳ مره برای بدست آوردن اين رابطه دو تقریب زده شده است: * در محاسبه انحراف معيار بجاى (جإ) مسجب از (ا) دم استفاده شده است توزيع دوجمله اى با توزيع نرمال تقريب زده شده است. 

صفحه 27:
‎Ape) Ss‏ يكطرفه 43 دوطرفه ‎٩‏ فاصله بدست آمده در مثال فوق یک فاصله دوطرفه است. گاهی لازم میشود که اين فاصله بصورت یکطرفه بیان شود: احتمال اینکه (0),«سه حداکثر () باشد چقدر است؟ © با توجه به اينکه توزیع نرمال حول میانگین متقارن است؛ میتوان یک فاصله اطمینان دوطرفه را به فاصله اطمینان یک طرفه معادلی با دو برابر اطمینان تبدیل نمود. [(هلم100)6 .. امه ‏[0 ۲ )9۵۵۵ (طلم)۵0 — ]% 

صفحه 28:
* اختلاف خطای فرضیه ها # حالتی را در نظر بگیرید که دو فرضیه ۲۵ ,۷ موجود باشند: 9 بر رویمجموعه 20 که شاملب عضو لستتستشدم و بر روومجموعه ‎oO‏ که شامل» عضو بوده و دارلی‌همان‌توزيم. لستقستگردیدم لستب © میخواهیم بدانیم اختلاف خطای واقعی اين دوفرضیه چیست؟ هروس - 1 لزم رمع 

صفحه 29:
© اتخمین زننده * برای تخمین مقدار 4 از یک تخمین زننده استفاده میکنیم: d=errod li)- errog( ۸ © نشاد داده میشود که [م تخمینی بایاس نشده از لرا بدست میدهد Hd =a 0 

صفحه 30:
انحراف معيار * از آنجائيكه براى مقادير بزرك نمونه توزيع احتمال (۳6) یس و (۳) ,رسمه نقریبا نرمال است ‏ لذا توزيع احتمال ب را نیزمیتوان بصورت نرمال در نظر گرفت: ‎_erro#\W- erro Md) 8 errop2\l- erropli2))‏ ۳ ‎d 11 12‏ © به همین ترتیب فاصله اطمینان این تقریب بصورت زیر خواهد بود. a oe | erroxAM- erro, erropUb- errog| 

صفحه 31:
مقایسه الگوریتم های یادگیری © چگونه میتوان عملکرد دو الگوریتم یادگیری مختلف ) مثل شبکه عصبی و درخت تصمیم ( را مقایسه کرد؟ 

صفحه 32:
$2 امقایسه الگوریتم های یادگیری * روشهای مختلفی برای اینکار معرفی شده ولی هنوز روشی که بتواند اتفاق آرا را کسب کند ارائه نگردیده است! # یک روش عبارت است از مقایسه میانگین عملکرد دو الگوریتم بر روی تمامی مجموعه های آموزشی با اندازه » که بصورت تصادفی از نمونه با توزیع 0 انتخاب میشوند. © بعبارت دیگر میخواهیم مقدار اختلاف مورد انتظار درخطای آندو را تخمین بزنیم. Cow fer o(lo(G))-errorolbo(G )([ 

صفحه 33:
9 در عمل فقط تعدا کمی داده نمونه برای مقایسه دو الگوریتم وجود دارد. در چنین حالتی داده موجود به دو مجموعه داده آموزشی (90) ومجموعه داده تست ‎DD)‏ تقسیم میشود.از داده آموزشی برای آموزش هر دو الگوریتم استفاده شده و داده تست نیز برای ارزیابی هر دو الگوریتم استفاده میشود. 9 در اینصورت مقدار زیر برای مقایسه دو الگوریتم بکار میرود. ((و) مامح( )ماو مد * ایراد این کاراینجاست که بجای استفاده از تمامی مجموعه های موجود در () فقط خطای موجود در مجموعه آموزشی مورد استفاده قرار میگیرد. 

صفحه 34:
‎Cross-Ouidation 33‏ لا ‏»يك راه حل استفاده از الكوريتم زیر است: ‎onto the avalible data 0000 ‏رت 6 ,20 له تم ۲ حادا‎ Al Tho equ size, where this size is ot lest OD or tProw (to k, do CO Gt< {DO -T} ‎k® <-L@(Gi) ‎k® <-L@(Gi) ‎Ot <= error THK®)-error THB) QRetura he vo wf), where : 2 wr (5) = Os Zag, ۷ 

صفحه 35:
‎s2‏ افاصله اطمینان ‎٩‏ مقدار تقریبی فاصله اطمینان ‎٩00‏ برای تخمین ‏[(()م)م سس ())ن امین عبارت است از: ‎a(S) Fy 7 an(d)‏ ۱ که در آن ببمامقداری شبیه به ,را بوده و مقادیر آن از جدول 0-0 بدست میاید» رم,,<تخمینی از انحراف معیار مربوط به توزيع (6)عره ميباشد: ‏7( م رت 

صفحه 36:
بو لعف ‎٩‏ اگر تست دو فرضیه یادگیری با استفاده ازمجموعه مثالهای یکسانی انجام شود ‎pte ode paired test‏ ‏© نتیجه چنین آزمایشاتی معمولا منجر به فواصل اطمینان بسته تری میگردد زیرا اختلاف مشاهده شده در خطا مربوط به اختلاف بین فرضیه هاست در حالیکه وقتی فرضیه ها با استفاده از مجموعه داده های متفاوتی تست میشوند امکان تاثیر گذاری اختلاف بين دو مجموعه داده زياد ميشود. ‎ 

ارزیابی فرضیه ها Instructor : Saeed Shiry مقدمه یک الگوریتم یادگیری با استفاده از داده های آموزشی فرضیه ای را بوجود میآورد .قبل از استفاده از این فرضیه ممکن است که الزم شود تا دقت این فرضیه مورد ارزیابی قرار گیرد. ‏ ‏Hypothesis ‏ ‏Learning ‏Algorithm ‏Data ‏Performance Assessment اینکار از دو جه8ت اهمیت دارد: ‏ ‏ دقت فرضیه را برای مثاله8ای نادیده 8حدس بزنیم. گاه8ی اوقات ارزیابی فرضیه جزئی از الگوریتم یادگیری است :م8ثل 8حرس کردن درخت تصمیم. روشهای آماری ‏ ‏ ‏ ‏ در این فصل سعی میشود تا روشهای آماری مناسب برای حدس زدن دقت فرضیه ها معرفی گردند .م8بنای کار در جهت پاسخگوئی به سه سوال زیر است: اگر دقت یک فرضیه برای داده های محدودی مع8لوم باشد دقت آن برای سایر مثالها چه قدر خواهد بود؟ اگر یک فرضیه برای داده های م8حدودی بهتر از فرضیه دیگری عمل کند احتمال اینکه این وضعیت در حالت ک8لی نیز صادق باشد چقدر است؟ وقتی که داده آموزشی اندکی موجود باشد به8ترین راه برای اینکه هم فرضیه را یاد بگیریم و هم دقت آنرا اندازه گ8یری ک8نیم چیست؟ کمی داده های آموزشی وقتی که داده آموزشی محدود باشد این امکان وجود دارد که این مثالها نشان دهنده توزیع کلی داده ها نباشند مشکل کمی داده وقتی ک8ه یادگیری با استفاده از داده های محدودی انجام م8یشود دو مشکل ممکن است رخ دهند: ‏Bias in the estimate  دقت یک فرضیه بر روی م8ثاله8ای آموزشی تخمین مناسبی برای دقت آن برای مثالهای نادیده نیست .زیرا فرضیه یاد گرفته شده بر اساس این داده ها برای مثالهای آتی بصورت optimisticعمل خواهد نمود .برای رهائی از این امر میتوان از مجموعه داده ها ی تست استفاده کرد. ‏Variance in the estimate  حتی با وجود استفاده از مجم8وعه تست این امکان وجود دارد که خطای اندازه گ8یری شده با خطای واقع8ی اختالف داشته باشد Bias and Variance in the Estimate Variance accuracy Estimated Accuracy True accuracy Bias sample size تخمین دقت فرضیه ‏ در یک مثال یادگیری میتوان برای فضای مثالهای ورودی یک تابع توزیع احتمال نامعلوم Dدر نظر گرفت که احتمال رخداد هر نمونه xرا با ) p(xمشخص مینماید. )p(X ‏Input Space X ‏ در اینصورت با دو سوال زیر مواجه هستیم: ‏ ‏ اگر فرضیه hو تعداد nنمونه داشته باشیم که بصورت تصادفی از مثالهائی با توزیع Dانتخاب شده باشند ،بهترین تخمین برای دقت hبرای مثالهائی با همان توزیع چیست؟ خطای احتمالی در این تخمین دقت چقدر است؟ خطای نمونه و خطای واقعی خطای نمونه عبارت است از خطای فرضیه روی مجموعه مثالهای موجود ) آموزشی و یا تست( خطای نمونه فرضیه hنسبت به تابع هدف fو داده نمونه s بصورت زیر بیان میشود: ))errors(h)= 1/n xS(f(x),h(x که در ان nتعداد مثالهای sومقدار )) (f(x),h(xبرابر با 1است اگر )f(x)  h(xو در غیر اینصورت برابر با 0است. خطای نمونه و خطای واقعی خطای واقعی عبار8ت است از خطای فرضیه روی مجموعه تمام مثالهای با توز8یع نامعلوم Dو بر8ابر است با احتمال اینکه یک نمونه تصادفی به غلط دسته بندی شود. خطای واقعی فرضیه hنسبت به تابع هدف f 8و داده با توزیع Dبصورت زیر بیان میشود: ])errorD(h)= PrxD[f(x)  h(x است. واقعیاست. خطایواقعی هستیمخطای دنبالآنآنهستیم آنچهکهکهبهبهدنبال حالیکهآنچه استدردرحالیکه نمونهاست خطای نمونه داریمخطای دستداریم آنچهکهکهدردردست آنچه برای خوبی تخمین میتواند ی حد چه تا نمونه خطای که دهیم پاسخ سوال این به باید اینصورت دردراینصورت باید به این سوال پاسخ دهیم که خطای نمونه تا چه حد ی میتواند تخمین خوبی برای باشد؟ واقعیباشد؟ خطایواقعی خطای مثال یک مجموعه داده 6تائی با توزیع احتمال زیر وجود دارد: ‏P(X1) = 0.2 P(X4) = 0.1 ‏P(X2) = 0.1 P(X5) = 0.2 ‏P(X3) = 0.3 P(X6) = 0.1 فرضیه hبرای مجموعه نمونه {}X1, X2, X3, X4میتواند X1, X2, X3را بدرستی دسته بندی کند ولی قادربه دسته بندی صحیح X4نیست .دراین صورت خطای نمونه برابر است با: ¼ (0 + 0 + 0 + 1) = ¼ = 0.25 اگر این فرضیه برای X6صحیح و برای X5نادرست باشد در اینصورت خطای واقعی برابر است با: 0.2(0) + 0.1(0) + 0.3(0) + 0.1(1) + 0.2(1) + 0.1(0) = 0.3 فاصله اطمینان برای فرضیه های با مقادیر گسسته اگرشرایط زیر برقرار باشند: نمونه Sدارای nمثال باشد ک8ه مستقل از یکدیگر و مستقل از hبرپایه توزیع احتمال Dانتخاب شده باشند و n  5 ب888اشد و فرضیه hمنجر به rخطا برروی 8این مثالها گردد ‏errorS(h)=r/n تحت این شرایط میتوان بر پایه قضایای آماری ادعا نمود که .1 .2 اگر اطالعات بیشتری موجود نباشد ،محتملترین مقدار برای ) errorD(hبرابر با ) errorS(hخواهد بود ‏ ‏ ‏ ‏ ‏h ‏ 1 ‏ ‏h ‏ با احتمال %95خطای واقعی بین فاصله زیر قرار داردerrors : ‏errors  h 1.96 errors ‏n مثال فرض کنید که sدارای n=40مثال بوده و فرضیه hمنجر به r=12خطا بر روی این داده شود .در اینصورت: خطای نمونه برابر است با errorS(h)=12/40=.30 اگر این آزمایش را بارها و بارها برای 40نمونه جدید تکرار کنیم متوجه خواهیم شد که در %95مواقع خطای محاسبه شده در فاصله زیر قرار خواهد داشت: 0.301.96.07 0.30.14 فاصله اطمینان برای فرضیه های با مقادیر گسسته ‏ عبارت فوق را میتوان بجای فاصله اطمینان %95برای هر فاصله دیگری نظیر %Nنیز ذکر نمود: ‏ h1 error h  ‏error ‏ ‏ ‏h ‏ ‏error Z ‏n ‏ مقدار ثابت ZNبرای درصدهای مختلف را میتوان از جدول زیر بدست آورد: ‏ این تقریب زمانی بهترین نتیجه را دارد که: ‏n errorS(h)(1 - errorS(h))  5 ‏s ‏s ‏N ‏s مقدمه ای بر تئوری نمونه برداری مروری بر بحثهای زیر میانگین واریانس توزیع دوجمله ای توزیع نرمال فواصل یک طرفه و دو طرفه تخمین خطا ‏ ‏ ‏ ‏ سوال :تاثیر اندازه داده های نمونه بر اختالف بین خطای نم8ونه و خطای واقعی چیست؟ در واقع پاسخ این سوال را متخصصین آمار داده اند! م8یتوان اندازه گ8یری خطای نمونه را به آزمایشی با نتیجه تصادفی تشبیه ک8رد .اگر به دفع8ات nنمونه با توزیع احتمال Dبصورت تصادفی انتخاب و خطای نمونه برای هر کدام اندازه گیری شود ،بعلت متفاوت بودن نمونه ها مقدار خطا نیز متفاوت خواهد بود .نتیجه حاصل از هر آزمایش یک متغ8یر تصادفی خواهد بود. چنین آزمایشی را میتوان با استفاده از توزیع دو جمله ای توصیف نمود. توزیع دوجمله ای ‏ ‏ ‏ ‏ ‏ توزیع دو جمله ای برای آزمایشاتی استفاده میشود که دارای خواص زیر باشند: آزمایش به تعداد nدفعه تکرار شود n ،مقداری ثابت و ازقبل دانسته است. هر آزمایش دارای 8دو نتیجه درست و یا غلط باشد. آزمایشات مستقل از همدیگر باشند ،به نحویکه نتیجه یک آزمایش تاثیری بر سایر آزمایشات نداشته باشد. احتمال وقوع نتیجه درست برای تمام آزمایشات ثابت باشد. مثال در پرتاب یک سکه به تعداد 8دفعه: ‏n=8  آزمایش دارای دو نتیجه شیر یا خط است نتیجه هر پرتاب سکه مستقل از پرتاب های قبلی است احتمال آمدن شیر برای هر پرتاب p=1/2است احتمال دوجمله ای احتمال وقوع rموفقیت در Nبار تکرار یک آزمایش از رابطه زیر محاسبه میشود: ‏N r ‏1 p ‏r !N ‏P r  ‏p !r! N  r که در آن pاحتمال وقوع موفقیت در هر بار تکرار آزمایش است. توزیع دوجمله ای برای ‏n=40, p=.3 40 30 20 10 0 مثال احتمال آمدن 6خط در 8بار پرتاب یک سکه چقدر است؟ ‏p .5 8 6 !8 6 ‏P 6  ‏.055 1 ‏ . 5 . 5 !6! 8 6 ‏ ‏ خطای نمونه برداری این خطا را میتوان با پرتاب سکه مقایسه نمود: پرتاب سکه و دیدن یک خط انتخاب یک نمونه از Dو تعیین اینکه آیا hآنرا غلط ارزیابی میکند یا نه احتمال اینکه در یک پرتاب واحد یک خط داشته باشیم احتمال اینکه یک نمونه غلط ارزیابی شود دیدن تعداد rخط در Nبار پرتاب سکه  تعداد ارزیابی های غلط از بین Nنمونه انتخاب شده میانگین مقدارمیانگین ) و یا ( Expected Valueیک متغیر تصادفی Yکه ممکن است مقادیر y1,...,ynرا داشته باشد عبارت است از: )E[Y] = i=1n yi Pr(Y=yi برای یک متغیر تصادفی با توزیع دوجمله ای این مقدار برابر است با: ‏E[Y] = np واریانس واریانس گستردگی توزیع احتمال و فاصله متغیر تصادفی از مقدار میانگین را مشخص میکند .واریانس یک متغیر تصادفی Yعبارت است از: ]Var[Y] = E[(Y-E[Y])2 ریشه دوم واریانس انحراف معیار نامیده میشود. برای یک متغیر تصادفی با توزیع دوجمله ای این مقادیر برابراند با: ) np(1 p ‏Y ‏ )Var[Y] np(1 p بایاس تخمین ‏ اگر rتعداد خطا ی فرضیه برای نمونه ای با اندازه nباشد در اینصورت: ‏errorS(h) = r/n and errorD(h) = p که pاحتمال دسته بندی غلط یک نمونه انتخاب شده از Dاست متخصصین آمار ) errorS(hرا یک تخمین زننده ()estimatorمینامند. اختالف بین مقدار تخمین زده شده و مقدار واقعی بایاس تخمین نامیده میشود E[Y] – p اگر مقدار بایاس صفر باشد ،تخمین زننده بدون بایاس نام8یده میشود. انحراف معیار خطای نمونه اگر در یک نمونه nعضوی تعداد rخطا داشته باشیم، انحراف معیار خطای نمونه برابر است با )p(1 p ‏ ‏n ‏n ‏r ‏ ‏ error )(h ‏s این مقدار را میتوان بصورت زیر تقریب زد: ))error(h)(1 error(h ‏S ‏S ‏n ‏ errors(h)  فاصله اطمینان برای یک توزیع دوجمله ای مقدار میانگین برابر با ) errorD(hو مقدارانحراف معیار برابر است با ))error(h)(1 error(h ‏S ‏S ‏n ‏ errors(h)  از اینرو برای بدست آوردن فاصله اطمینان %95میبایست فاصله ای حول میانگین پیدا کینم که %95احتمال را در بر داشته باشد. از آنجائیکه برای توزیع دوجمله ای محاسبه این مقدار مشکل بوده و از طرفی از آنجائیکه برای نمونه های زیاد توزیع دوجمله ای به توزیع نرمال نزدیک میشود ،میتوان برای محاسبه فاصله اطمینان از توزیع نرمال بهره گرفت. تقریب با توزیع نرمال ‏ برای توزیع نرمال با میانگین و واریانس فاصله اطمینان %Nبصورت زیر است: ‏ از اینرو تقریب ما بصورت زیر خواهد بود: ‏ zN ‏ h1 error ‏ h  ‏error ‏s ‏s ‏ ‏ ‏h ‏ ‏errors ZN ‏n ‏ برای بدست آوردن این رابطه دو تقریب زده شده است: ‏ در محاسبه انحراف معیار بجای ) errorD(hاز ) errors(hاستفاده شده است ‏ توزیع دوجمله ای با توزیع نرمال 8تقریب زده شده است. حدود یکطرفه و دوطرفه فاصله بدست آمده در مثال فوق یک فاصله دوطرفه است. گاهی الزم میشود که این فاصله بصورت یکطرفه بیان شود: احتمال اینکه ) errorD(hحداکثر Uباشد چقدر است؟ با توجه به اینکه توزیع نرمال حول میانگین متقارن است، میتوان یک فاصله اطمینان دوطرفه را به فاصله اطمینان یک طرفه معادلی با دو برابر اطمینان تبدیل نمود. [ )100(1-a/2 %L )100(1-a/2 ]%U [U ]L )%100(1-a اختالف خطای فرضیه ها حالتی را در نظر بگیرید که دو فرضیه h1, h2موجود باشند: ‏h1 ب888ر رویمجم8وعه s1 8ک888ه 8ش88امل n1عضو ا8ستت888ستش88ده8 و h2ب888ر رویمجموعه s2 8ک888ه 8ش88امل n2عضو ب888وده 8و 8ست دارا8یهمانت888وزیع 8ا8ستت888ستگ888ردیده 8ا . میخواهیم بدانیم اختالف خطای واقعی این دوفرضیه چیست؟ ‏derrorD h1  errorD h2 تخمین زننده برای تخمین مقدار dاز یک تخمین زننده استفاده میکنیم: ‏ ‏derrors1 h1  errors2 h2 ‏ نشاد داده میشود که dتخمینی بایاس نشده از dرا بدست میدهد یعنی ‏ ‏  ‏E d d ‏  انحراف معیار از آنجائیکه برای مقادیر بزرگ نمونه توزیع احتمال ) errors2(h2و ) errors1(h1تقریبا نرمال است ،لذا توزیع ‏ احتمال dرا نیزمیتوان بصورت نرمال در نظر گرفت: ‏s1 h11 error ‏s1 h1  error ‏s2 h21 error ‏s2 h2  2 error ‏ ‏ ‏n2 ‏n1 ‏ ‏d به همین ترتیب فاصله اطمینان این تقریب بصورت زیر خواهد بود. ‏ ‏errors1 h11 errors1 h1   errors2 h21 errors2 h2  ‏ ‏n2 ‏n1 ‏d zN مقایسه الگوریتم های یادگیری چگونه میتوان عملکرد دو الگوریتم یادگیری مختلف ) مثل شبکه عصبی و درخت تصمیم ( را مقایسه کرد؟ ‏LA ‏LB ‏Type B ‏Type A مقایسه الگوریتم های یادگیری روشهای مختلفی برای اینکار معرفی شده ولی هنوز روشی که بتواند اتفاق آرا را کسب کند ارائه نگردیده است! یک روش عبارت است از مقایسه میانگین عملکرد دو الگوریتم بر روی تمامی مجموعه های آموزشی با اندازه nکه بصورت تصادفی از نمونه با توزیع Dانتخاب میشوند. بعبارت دیگر میخواهیم مقدار اختالف مورد انتظار درخطای آندو را تخمین بزنیم. ]))ESD [errorD(LA(S))-errorD(LB(S مشکل کمی داده در عمل فقط تعدا کمی داده نمونه برای مقایسه دو الگوریتم وجود دارد .در چنین حالتی داده موجود به دو مجموعه داده آموزشی S0ومجموعه داده تست T0تقسیم میشود.از داده آموزشی برای آموزش هر دو الگوریتم استفاده شده و داده تست نیز برای ارزیابی هر دو الگوریتم استفاده میشود. در اینصورت مقدار زیر برای مقایسه دو الگوریتم بکار میرود. ))errorT0(LA(S0))-errorT0(LB(S0 ایراد این کاراینجاست که بجای استفاده از تمامی مجموعه های موجود در Dفقط خطای موجود در مجموعه آموزشی مورد استفاده قرار میگیرد. k-Fold Cross-Validation : یک راه حل استفاده از الگوریتم زیر است Partition the available data D0 into k disjoint subsets T1, T2, …, .1 .Tk of equal size, where this size is at least 30 For i from 1 to k, do .2 use Ti for the test set, and the remaining data for training set Si • Si <- {D0 - Ti} • hA <- LA(Si) • hB <- LB(Si) • i <- errorTi(hA)-errorTi(hB) Return the value avg(), where . .3 avg() = 1/k i=1k i فاصله اطمینان مقدار تقریبی فاصله اطمینان %Nبرای تخمین ])) ESD0[errorD(LA(S))-errorD(LB(Sعبارت است از: )avg()tN,k-1savg( ‏که در آن tN,k-1مقداری شبیه به ZNبوده و مقادیر آن از جدول 6-5بدست میآید savg() ،تخمینی از انحراف معیار مربوط به توزیع ) avg(میباشد: ‏savg())=1/k(k-1) i=1k (i -avg())2 Paired Test اگر تست دو فرضیه یادگیری با استفاده ازمجموعه مثالهای یکسانی انجام شود paired testنامیده میشود. نتیجه چنین آزمایشاتی معموال منجر به فواصل اطمینان بسته تری میگردد زیرا اختالف مشاهده شده در خطا مربوط به اختالف بین فرضیه هاست در حالیکه وقتی فرضیه ها با استفاده از مجموعه داده های متفاوتی تست میشوند امکان تاثیر گذاری اختالف بین دو مجموعه داده زیاد میشود.