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

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

اسلاید 1: ارزیابی فرضیه هاInstructor : Saeed Shiry

اسلاید 2: مقدمهیک الگوریتم یادگیری با استفاده از داده های آموزشی فرضیه ای را بوجود میآورد . قبل از استفاده از این فرضیه ممکن است که لازم شود تا دقت این فرضیه مورد ارزیابی قرار گیرد.اینکار از دو جهت اهمیت دارد:دقت فرضیه را برای مثالهای نادیده حدس بزنیم.گاهی اوقات ارزیابی فرضیه جزئی از الگوریتم یادگیری است: مثل حرس کردن درخت تصمیم.Data Learning Hypothesis AlgorithmPerformance Assessment

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

اسلاید 4: کمی داده های آموزشیوقتی که داده آموزشی محدود باشد این امکان وجود دارد که این مثالها نشان دهنده توزیع کلی داده ها نباشند

اسلاید 5: مشکل کمی دادهوقتی که یادگیری با استفاده از داده های محدودی انجام میشود دو مشکل ممکن است رخ دهند:Bias in the estimateدقت یک فرضیه بر روی مثالهای آموزشی تخمین مناسبی برای دقت آن برای مثالهای نادیده نیست. زیرا فرضیه یاد گرفته شده بر اساس این داده ها برای مثالهای آتی بصورت optimistic عمل خواهد نمود. برای رهائی از این امر میتوان از مجموعه داده ها ی تست استفاده کرد.Variance in the estimateحتی با وجود استفاده از مجموعه تست این امکان وجود دارد که خطای اندازه گیری شده با خطای واقعی اختلاف داشته باشد

اسلاید 6: Bias and Variance in the Estimatesample sizeaccuracyEstimated AccuracyTrue accuracyVarianceBias

اسلاید 7: در یک مثال یادگیری میتوان برای فضای مثالهای ورودی یک تابع توزیع احتمال نامعلوم D در نظر گرفت که احتمال رخداد هر نمونه x را با p(x) مشخص مینماید. در اینصورت با دو سوال زیر مواجه هستیم:اگر فرضیه h و تعداد n نمونه داشته باشیم که بصورت تصادفی از مثالهائی با توزیع D انتخاب شده باشند، بهترین تخمین برای دقت h برای مثالهائی با همان توزیع چیست؟خطای احتمالی در این تخمین دقت چقدر است؟تخمین دقت فرضیهInput Space Xp(X)

اسلاید 8: خطای نمونهعبارت است از خطای فرضیه روی مجموعه مثالهای موجود ) آموزشی و یا تست( خطای نمونه فرضیه 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 است.خطای نمونه و خطای واقعی

اسلاید 9: خطای نمونه و خطای واقعیخطای واقعیعبارت است از خطای فرضیه روی مجموعه تمام مثالهای با توزیع نامعلوم D و برابر است با احتمال اینکه یک نمونه تصادفی به غلط دسته بندی شود.خطای واقعی فرضیه h نسبت به تابع هدف f و داده با توزیع D بصورت زیر بیان میشود:errorD(h)= PrxD[f(x)  h(x)]آنچه که در دست داریم خطای نمونه است در حالیکه آنچه که به دنبال آن هستیم خطای واقعی است. در اینصورت باید به این سوال پاسخ دهیم که خطای نمونه تا چه حد ی میتواند تخمین خوبی برای خطای واقعی باشد؟

اسلاید 10: مثالیک مجموعه داده6 تائی با توزیع احتمال زیر وجود دارد:P(X1) = 0.2 P(X4) = 0.1P(X2) = 0.1 P(X5) = 0.2P(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

اسلاید 11: اگرشرایط زیر برقرار باشند:نمونه S دارای n مثال باشد که مستقل از یکدیگر و مستقل از h برپایه توزیع احتمال D انتخاب شده باشند وn  5 باشد وفرضیه h منجر به r خطا برروی این مثالها گردد errorS(h)=r/nتحت این شرایط میتوان بر پایه قضایای آماری ادعا نمود کهفاصله اطمینان برای فرضیه های با مقادیر گسستهاگر اطلاعات بیشتری موجود نباشد، محتملترین مقدار برای errorD(h) برابر با errorS(h) خواهد بودبا احتمال 95% خطای واقعی بین فاصله زیر قرار دارد:

اسلاید 12: مثالفرض کنید که s دارای n=40 مثال بوده و فرضیه h منجر به r=12 خطا بر روی این داده شود. در اینصورت:خطای نمونه برابر است با errorS(h)=12/40=.30 اگر این آزمایش را بارها و بارها برای 40 نمونه جدید تکرار کنیم متوجه خواهیم شد که در 95% مواقع خطای محاسبه شده در فاصله زیر قرار خواهد داشت:

اسلاید 13: فاصله اطمینان برای فرضیه های با مقادیر گسستهعبارت فوق را میتوان بجای فاصله اطمینان 95% برای هر فاصله دیگری نظیر N% نیز ذکر نمود:مقدار ثابت ZN برای درصدهای مختلف را میتوان از جدول زیر بدست آورد:این تقریب زمانی بهترین نتیجه را دارد که:n errorS(h)(1 - errorS(h))  5

اسلاید 14: مقدمه ای بر تئوری نمونه برداریمروری بر بحثهای زیرمیانگینواریانستوزیع دوجمله ایتوزیع نرمالفواصل یک طرفه و دو طرفه

اسلاید 15: تخمین خطاسوال: تاثیر اندازه داده های نمونه بر اختلاف بین خطای نمونه و خطای واقعی چیست؟در واقع پاسخ این سوال را متخصصین آمار داده اند!میتوان اندازه گیری خطای نمونه را به آزمایشی با نتیجه تصادفی تشبیه کرد. اگر به دفعات n نمونه با توزیع احتمال D بصورت تصادفی انتخاب و خطای نمونه برای هر کدام اندازه گیری شود، بعلت متفاوت بودن نمونه ها مقدار خطا نیز متفاوت خواهد بود. نتیجه حاصل از هر آزمایش یک متغیر تصادفی خواهد بود.چنین آزمایشی را میتوان با استفاده از توزیع دو جمله ای توصیف نمود.

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

اسلاید 17: مثالدر پرتاب یک سکه به تعداد 8 دفعه:n=8آزمایش دارای دو نتیجه شیر یا خط استنتیجه هر پرتاب سکه مستقل از پرتاب های قبلی استاحتمال آمدن شیر برای هر پرتاب p=1/2 است

اسلاید 18: احتمال دوجمله ایاحتمال وقوع r موفقیت در N بار تکرار یک آزمایش از رابطه زیر محاسبه میشود:که در آن p احتمال وقوع موفقیت در هر بار تکرار آزمایش است. 0 10 20 30 40توزیع دوجمله ای برایn=40, p=.3

اسلاید 19: مثالاحتمال آمدن 6 خط در 8 بار پرتاب یک سکه چقدر است؟

اسلاید 20: خطای نمونه برداریاین خطا را میتوان با پرتاب سکه مقایسه نمود:پرتاب سکه و دیدن یک خط انتخاب یک نمونه از D و تعیین اینکه آیا h آنرا غلط ارزیابی میکند یا نهاحتمال اینکه در یک پرتاب واحد یک خط داشته باشیم احتمال اینکه یک نمونه غلط ارزیابی شوددیدن تعداد r خط در N بار پرتاب سکه  تعداد ارزیابی های غلط از بین N نمونه انتخاب شده

اسلاید 21: میانگینمقدارمیانگین ) و یا (Expected Value یک متغیر تصادفی Y که ممکن است مقادیر y1,...,yn را داشته باشد عبارت است از:E[Y] = i=1n yi Pr(Y=yi) برای یک متغیر تصادفی با توزیع دوجمله ای این مقدار برابر است با:E[Y] = np

اسلاید 22: واریانسواریانس گستردگی توزیع احتمال و فاصله متغیر تصادفی از مقدار میانگین را مشخص میکند. واریانس یک متغیر تصادفی Y عبارت است از:Var[Y] = E[(Y-E[Y])2] ریشه دوم واریانس انحراف معیار نامیده میشود.برای یک متغیر تصادفی با توزیع دوجمله ای این مقادیر برابراند با:

اسلاید 23: بایاس تخمیناگر r تعداد خطا ی فرضیه برای نمونه ای با اندازه n باشد در اینصورت:errorS(h) = r/n and errorD(h) = p که p احتمال دسته بندی غلط یک نمونه انتخاب شده از D استمتخصصین آمار errorS(h) را یک تخمین زننده (estimator)مینامند.اختلاف بین مقدار تخمین زده شده و مقدار واقعی بایاس تخمین نامیده میشود E[Y] – p اگر مقدار بایاس صفر باشد، تخمین زننده بدون بایاس نامیده میشود.

اسلاید 24: انحراف معیار خطای نمونهاگر در یک نمونه n عضوی تعداد r خطا داشته باشیم، انحراف معیار خطای نمونه برابر است بااین مقدار را میتوان بصورت زیر تقریب زد:

اسلاید 25: فاصله اطمینانبرای یک توزیع دوجمله ای مقدار میانگین برابر با errorD(h) و مقدارانحراف معیار برابر است با از اینرو برای بدست آوردن فاصله اطمینان 95% میبایست فاصله ای حول میانگین پیدا کینم که 95% احتمال را در بر داشته باشد.از آنجائیکه برای توزیع دوجمله ای محاسبه این مقدار مشکل بوده و از طرفی از آنجائیکه برای نمونه های زیاد توزیع دوجمله ای به توزیع نرمال نزدیک میشود، میتوان برای محاسبه فاصله اطمینان از توزیع نرمال بهره گرفت.

اسلاید 26: تقریب با توزیع نرمالبرای توزیع نرمال با میانگین m و واریانس s فاصله اطمینان N% بصورت زیر است:از اینرو تقریب ما بصورت زیر خواهد بود:برای بدست آوردن این رابطه دو تقریب زده شده است:در محاسبه انحراف معیار بجای errorD(h) از errors(h) استفاده شده استتوزیع دوجمله ای با توزیع نرمال تقریب زده شده است.

اسلاید 27: حدود یکطرفه و دوطرفهفاصله بدست آمده در مثال فوق یک فاصله دوطرفه است. گاهی لازم میشود که این فاصله بصورت یکطرفه بیان شود:احتمال اینکه errorD(h) حداکثر U باشد چقدر است؟با توجه به اینکه توزیع نرمال حول میانگین متقارن است، میتوان یک فاصله اطمینان دوطرفه را به فاصله اطمینان یک طرفه معادلی با دو برابر اطمینان تبدیل نمود.[ L U] 100(1-a)%[ L 100(1-a/2)%U] 100(1-a/2)%

اسلاید 28: اختلاف خطای فرضیه هاحالتی را در نظر بگیرید که دو فرضیه h1, h2 موجود باشند:h1بر روی مجموعه s1 که شامل n1 عضو است تست شده و h2بر روی مجموعه s2 که شامل n2 عضو بوده و دارای همان توزیع است تست گردیده است. میخواهیم بدانیم اختلاف خطای واقعی این دوفرضیه چیست؟

اسلاید 29: تخمین زنندهبرای تخمین مقدار d از یک تخمین زننده استفاده میکنیم:نشاد داده میشود که تخمینی بایاس نشده از dرا بدست میدهد یعنی

اسلاید 30: انحراف معیاراز آنجائیکه برای مقادیر بزرگ نمونه توزیع احتمال errors2(h2) و errors1(h1) تقریبا نرمال است ، لذا توزیع احتمال را نیزمیتوان بصورت نرمال در نظر گرفت:به همین ترتیب فاصله اطمینان این تقریب بصورت زیر خواهد بود.

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

اسلاید 32: مقایسه الگوریتم های یادگیریروشهای مختلفی برای اینکار معرفی شده ولی هنوز روشی که بتواند اتفاق آرا را کسب کند ارائه نگردیده است!یک روش عبارت است از مقایسه میانگین عملکرد دو الگوریتم بر روی تمامی مجموعه های آموزشی با اندازه n که بصورت تصادفی از نمونه با توزیع D انتخاب میشوند.بعبارت دیگر میخواهیم مقدار اختلاف مورد انتظار درخطای آندو را تخمین بزنیم.ESD [errorD(LA(S))-errorD(LB(S))]

اسلاید 33: مشکل کمی دادهدر عمل فقط تعدا کمی داده نمونه برای مقایسه دو الگوریتم وجود دارد. در چنین حالتی داده موجود به دو مجموعه داده آموزشی S0 ومجموعه داده تست T0 تقسیم میشود.از داده آموزشی برای آموزش هر دو الگوریتم استفاده شده و داده تست نیز برای ارزیابی هر دو الگوریتم استفاده میشود.در اینصورت مقدار زیر برای مقایسه دو الگوریتم بکار میرود.errorT0(LA(S0))-errorT0(LB(S0)) ایراد این کاراینجاست که بجای استفاده از تمامی مجموعه های موجود در D فقط خطای موجود در مجموعه آموزشی مورد استفاده قرار میگیرد.

اسلاید 34: k-Fold Cross-Validationیک راه حل استفاده از الگوریتم زیر است:1. Partition the available data D0 into k disjoint subsets T1, T2, …, Tk of equal size, where this size is at least 30.2. For i from 1 to k, douse 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)3. Return the value avg(), where . avg() = 1/k i=1k i

اسلاید 35: فاصله اطمینانمقدار تقریبی فاصله اطمینان N% برای تخمین ESD0[errorD(LA(S))-errorD(LB(S))] عبارت است از:avg()tN,k-1savg() که در آن tN,k-1مقداری شبیه به ZN بوده و مقادیر آن از جدول 5-6 بدست میآید، savg() تخمینی از انحراف معیار مربوط به توزیع avg() میباشد:savg())=1/k(k-1) i=1k (i -avg())2

اسلاید 36: Paired Testاگر تست دو فرضیه یادگیری با استفاده ازمجموعه مثالهای یکسانی انجام شود paired test نامیده میشود.نتیجه چنین آزمایشاتی معمولا منجر به فواصل اطمینان بسته تری میگردد زیرا اختلاف مشاهده شده در خطا مربوط به اختلاف بین فرضیه هاست در حالیکه وقتی فرضیه ها با استفاده از مجموعه داده های متفاوتی تست میشوند امکان تاثیر گذاری اختلاف بین دو مجموعه داده زیاد میشود.