Slide 1

Report
‫دسته بندی نیمه نظارتی‬
‫زهره کریمی‬
Introduction to semi-supervised Learning, Xiaojin Zhu and Andrew B. Goldberg,
University of Wisconsin, Madison, 2009.
1
‫فهرست مطالب‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫روش های یادگیری نیمه نظارتی‬
‫مدل های ‪ Mixture‬و روش ‪EM‬‬
‫روش ‪Co-Training‬‬
‫روش های مبتنی بر گراف‬
‫روش های مبتنی بر ‪SVM‬‬
‫یادگیری نیمه نظارتی انسان‬
‫تئوری‬
‫‪2‬‬
‫انواع روش های یادگیری‬
‫‪ ‬یادگیری بدون ناظر‬
‫‪ ‬خوشه بندی‬
‫‪ ‬کاهش ابعاد‬
‫‪ ‬کشف ‪outlier‬‬
‫‪ ‬یادگیری نظارتی‬
‫‪ ‬دسته بندی‬
‫‪ ‬رگرسیون‬
‫‪ ‬یادگیری نیمه نظارتی‬
‫‪3‬‬
‫یادگیری نیمه نظارتی‬
‫انواع روش های نیمه نظارتی‬
‫‪ ‬دسته بندی نیمه نظارتی‬
‫‪ ‬خوشه بندی نیمه نظارتی‬
‫‪ ‬مثال‪ :‬دو نمونه خاص در یک دسته قرار می گیرند‪.‬‬
‫‪ ‬رگرسیون با استفاده از داده های برچسب دار و بدون برچسب‬
‫‪ ‬کاهش بعد با استفاده از داده های برچسب دار و بدون برچسب‬
‫‪4‬‬
‫انگیزه استفاده از یادگیری نیمه نظارتی‬
‫‪ ‬دالیل عملی‬
‫‪ ‬داده بدون برچسب به تعداد زیاد و با هزینه کم در دسترس است‬
‫‪ Natural Language Processing‬‬
‫‪ protein 3D structure prediction‬‬
‫‪ Spam filtering‬‬
‫‪ ‬دالیل تئوری‬
‫‪ ‬رسیدن به سطح یکسان کارایی با تعداد داده های بدون برچسب کمتر‬
‫‪ ‬به وجود آوردن مدل محاسباتی شبیه یادگیری انسان‬
‫‪5‬‬
‫یادگیری نیمه نظارتی‬
‫‪6‬‬
‫انواع روش های یادگیری نیمه نظارتی‬
‫‪ ‬روش های ‪Inductive‬‬
‫‪ ‬پیشگویی برچسب نمونه هایی که تاکنون مشاهده نشده اند؛‬
‫‪ ‬امتحان کالس ی‬
‫‪ ‬روش های ‪Transductive‬‬
‫‪ ‬پیشگویی بر چسب نمونه هایی که در مجموعه آموزش بکار رفته اند؛‬
‫‪ ‬امتحان ‪take-home‬‬
‫‪7‬‬
‫نکته مهم‬
‫‪ ‬در نظرگرفتن فرضیاتی در مورد ارتباط توزیع حاشیه ای )‪ P(x‬و توزیع شرطی‬
‫)‪P(y|x‬‬
‫‪ ‬ارتباط مستقیم کارایی به صحت فرض در نظرگرفته شده‬
‫‪8‬‬
9
Self-training
 self-teaching or bootstrapping
‫ از پیشگویی های خود برای آموزش خود استفاده می کند‬
10
‫)‪Self-training models (2‬‬
‫‪ ‬مزایا‬
‫‪ ‬سادگی‬
‫‪ ‬عدم وابستگی به مدل دسته بندی‬
‫‪ ‬اشکال‬
‫‪ ‬تقویت اشتباه در مراحل یادگیری‬
‫‪ ‬حساس به ‪Outlier‬‬
‫‪ ‬فرض‪ :‬پیشگویی دسته بندی کننده با اطمینان باالیی صحیح است‪.‬‬
‫‪ ‬در هنگامی که دسته ها در خوشه های جداگانه ای باشند ممکن است‬
‫‪11‬‬
Self-training models (3)
12
Self-training models (4)
13
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫روش های یادگیری نیمه نظارتی‬
‫مدل های ‪ Mixture‬و روش ‪EM‬‬
‫روش ‪Co-Training‬‬
‫روش های مبتنی بر گراف‬
‫روش های مبتنی بر ‪SVM‬‬
‫یادگیری نیمه نظارتی انسان‬
‫تئوری‬
‫‪14‬‬
‫‪Mixture Model‬‬
‫‪ ‬جمع وزن دار چند تابع چگالی احتمال‬
‫‪15‬‬
‫‪Mixture models‬‬
‫‪ ‬داده بدون برچسب حاوی اطالعاتی در مورد نحوه ترکیب داده های دسته های‬
‫گوناگون است‪.‬‬
‫‪ ‬با دانستن نحوه توزیع داده های هر دسته‪ ،‬می توان آن ها را از یکدیگر جدا‬
‫کرد‪.‬‬
‫‪16‬‬
‫‪Generative Models‬‬
‫‪ ‬محاسبه )‪ p(y|x‬با استفاده از روش های ‪Generative‬‬
‫‪ ‬روش هایی که به صورت صریح یا ضمنی توزیع احتمال توام ورودی و‬
‫خروجی را مشخص می کنند‬
‫‪ ‬با نمونه برداری از آن ها می توان داده هایی را در فضای نمونه تولید‬
‫کرد‬
‫‪ ‬نمونه ها‪:‬‬
‫‪Gaussian Mixture Model, Multinomial Mixture Model,‬‬
‫‪Hidden Markov Model‬‬
‫‪17‬‬
‫‪Generative Models‬‬
‫‪ ‬مجهوالت‬
‫‪ ‬پارامترهای مدل (مثال میانگین و کوواریانس در توزیع گوس ی)‬
‫‪ ‬احتمال هر دسته‬
‫)‪Maximum likelihood estimate (MLE‬‬
‫‪18‬‬
‫‪ Mixture models‬در یادگیری بانظارت‬
‫اغلب راه حل تحلیلی برای حل این مسئله وجود دارد‬
‫‪19‬‬
‫‪ Mixture models‬در دسته بندی نیمه نظارتی‬
‫‪Marginal probability‬‬
‫راه حل تحلیلی برای حل ‪ MLE‬در دسته بندی نیمه نظارتی وجود ندارد‬
‫‪20‬‬
‫بهینه سازی با استفاده از الگوریتم ‪EM‬‬
‫‪21‬‬
‫الگوریتم ‪EM‬‬
‫‪ ‬گام ‪:E‬‬
‫‪22‬‬
‫الگوریتم ‪EM‬‬
‫‪ ‬گام ‪:M‬‬
‫‪23‬‬
‫الگوریتم ‪EM‬‬
‫‪ ‬روش ی برای یافتن بهینه محلی‬
‫‪ ‬حساس به مقدار اولیه‬
‫‪ ‬ایده آن شبیه الگوریتم ‪K-means‬‬
‫‪24‬‬
‫نمونه ای از ‪EM‬‬
‫‪25‬‬
‫فرضیات مدل های ‪Mixture‬‬
‫داده واقعا بر اساس ‪ mixture model‬است یعنی تعداد‬
‫مولفه ها و )‪ p(x|y‬صحیح است‪.‬‬
‫‪26‬‬
‫فرضیات مدل های ‪Mixture‬‬
‫‪27‬‬
‫فرضیات مدل های ‪Mixture‬‬
‫فرضیات مدل های ‪Mixture‬‬
‫فرضیات مدل های ‪Mixture‬‬
‫‪ ‬راه های بهبود‬
‫‪ ‬استفاده از دانش دامنه‬
‫‪ ‬اهمیت کمتر به داده های بدون برچسب‬
‫‪30‬‬
‫مدل های ‪Generative‬‬
‫‪ ‬قابل شناسایی (‪)Identifiable‬‬
‫‪GMM ‬‬
‫‪ ‬بهینه محلی‬
‫‪ ‬شروع تصادفی‬
‫‪31‬‬
‫قابل شناسایی بودن مدل‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫)‪ P(x|y‬یکنواخت‬
‫)‪ P(x‬یکنواخت در ]‪[0,1‬‬
‫داده های برچسب دار‬
‫برچسب ‪x=0.5‬؟‬
‫‪32‬‬
‫روش ‪Cluster-then-label‬‬
‫دسته بندی نیمه نظارتی با استفاده از روش های خوشه بندی بدون نظارت‬
‫‪33‬‬
Cluster-then-label ‫روش‬
34
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫روش های یادگیری نیمه نظارتی‬
‫مدل های ‪ Mixture‬و روش ‪EM‬‬
‫روش ‪Co-Training‬‬
‫روش های مبتنی بر گراف‬
‫روش های مبتنی بر ‪SVM‬‬
‫یادگیری نیمه نظارتی انسان‬
‫تئوری‬
‫‪35‬‬
‫دو دید از یک کاربرد‬
 Named Entity Recogniton
 Web Page Classification
‫ کلماتی در خود صفحه‬
‫ ارجاع دهنده به صفحه‬hyperlink ‫ کلماتی در‬
36
Co-Training
 Named entity Classification
Location
37
Co-Training
 Named entity Classification
Location
Location
38
Co-Training
 Named entity Classification
Location
Location
39
‫‪Co-Training‬‬
‫‪ ‬دو دسته بندی کننده را یاد می گیرد‪ :‬هر دسته بندی کننده روی یک دید‬
‫‪ ‬نمونه هایی را که در یک مدل دسته بندی با اطمینان باال دسته بندی شده اند به‬
‫داده های آموزش مدل دسته بندی دیگر اضافه می کند‪.‬‬
‫‪40‬‬
‫‪Co-Training‬‬
‫‪ ‬فرضیات‬
‫‪ ‬هر ‪ view‬به تنهایی برای دسته بندی کافی باشد‬
‫‪ ‬دو ‪ view‬به صورت شرطی با توجه به برچسب داده شده مستقل از هم باشند‬
‫‪41‬‬
‫کاربردها‬
‫‪ Web-page classification‬‬
‫‪ ‬متن صفحه‪ :‬کلمات رخ داده در صفحه‬
‫‪ ‬متن ‪ :hyperlink‬کلمات رخ داده در ‪ hyperlink‬ها به صفحه مورد نظر‬
‫‪ Classify Speech phonemes‬‬
‫‪ ‬سیگنال ‪Audio‬‬
‫‪ ‬سیگنال ‪ video‬نمایش دهنده حرکت لب ها‬
‫‪42‬‬
‫‪Co-training‬‬
‫‪ ‬ایده ‪Cotraining‬‬
‫‪ ‬دو دسته بندی کننده در مورد داده های بدون برچسب با یکدیگر توافق دارند‪.‬‬
‫‪ ‬تعداد زیادی توابع در فضای فرضیه نیستند که در مورد داده های بدون برچسب‬
‫با یکدیگر سازگار باشند لذا فضای فرضیه مورد نظر کوچک خواهد بود‪.‬‬
‫‪ ‬این تعداد از توابع اگر داده های بدون برچسب را به خوبی برازش دهند منجر به‬
‫‪ overfit‬نخواهد شد‪.‬‬
‫‪43‬‬
Regularized Risk Minimization Framework (1)
•The squared loss
c(x, y, f (x)) = (y − f (x))2
•0/1 loss
c(x, y, f (x)) = 0 if y = f (x), and 1 otherwise
• c(x, y = healthy, f (x) = diseased) = 1 and
c(x, y = diseased, f (x) = healthy) = 100
44
Regularized Risk Minimization Framework (2)
45
Multiview Learning
 MULTIVIEW LEARNING
‫ دید است‬k ‫ مدل بر اساس‬k ‫هدف تولید‬
Individual Regularized Risk
Semi-Supervised regularizer
 The semi-supervised regularizer:
‫ مدل را روی داده های بدون برچسب اندازه گیری می کند‬k ‫میزان عدم توافق‬
46
‫فرض در الگوریتم ‪Multiview learning‬‬
‫مجموعه فرضیه ها با یکدیگر موافق باشند و عالوه بر آن‬
‫‪ emprical risk‬آن ها کوچک باشد‬
‫‪47‬‬

similar documents