عضو شوید
عضویت سریع
تبادل لینک هوشمند 
آمار مطالب
آمار بازدیدPlease enter banners and links.
روشهای یادگیری جمعی، گروهی از مدل های ضعیف را تولید می‌کنند که با تلفیق مناسب و هوشمندانه خروجی آنها می توان به یک دسته‌بندی‌کننده قوی دست یافت. این روش‌ها زمانی که از الگوریتمهای تقویتی در ساختار سریال بهره می‌برند، کارایی به مراتب بالاتری از خود نشان می‌دهند.استفاده از شیوه تقسیم-و-تسخیر یا همان separate-and-conquer در زمان آموزش هر لایه از ساختار سریال، دلیل قدرت یادگیر‌های جمعی سریال می‌باشد؛ علاوه بر آن، تعیین مرزهای تصمیم موارد جزیی در دورهای نخست ساختار سریال انجام میشود و در دورهای آتی این مرز پالایش شده و موارد سخت‌تر را در بر خواهد گرفت. عملکرد مدل کلاسیک ساختار سريال، در مواجهه با مسائل دوکلاسه، به این صورت است که نمونه‌های غیر هدف که در لایه‌های اولیه یاد گرفته میشوند از سیستم حذف شده و با نمونه‌های سخت‌تر جایگزین میشوند؛ که میتوان از این استراتژی با نام bootstrapping یاد کرد. با این روند، یادگیری بهینه کلان-به-جزیی یا همان learning coarse-to-fine حاصل میشود.
در این مطالعه، یک مدل نوین برای آموزش طبقه‌بندی‌کننده‌های سريال ارایه شده است که از روش وارسی اعتبار در ساختار آن استفاده شده است. در روش پیشنهادی، درصدی از دادههای درست دسته‌بندی‌شده در لایه نخست ساختار به منظور حفظ عمومیت سیستم، برای آموزش به لایه بعدی فرستاده میشود و این روند برای لایه‌های بعدی ادامه خواهد یافت. بدین ترتیب، مدل ارائه شده در مقابل دادههای نویزی بسیار مقاوم بوده و انحراف معیار نرخ خطای آزمایش آن، از روشهای رقیب کمتر میشود.
واژههای کلیدی: یادگیری ماشین، الگوریتمهای یادگیری جمعی، coarse-to-fine learning، یادگیر‌های جمعی سريال، separate-and-conquer
فهرست مطالب
عنوان صفحه
TOC \h \z \t “A-Title 1,1,A-Title 2,2,A-Title 3,3,A-Chap Num,1,A-Chap Title,1,A-Title 4,4,لیست سطح 1,1,A-Title 5,5,A-Title 6,6,A-Title 0,1” فصل اولمقدمه1. مقدمه………………………………………………………………………………………………………………………………… PAGEREF _Toc380062188 \h 11-1. مقدمه PAGEREF _Toc380062189 \h 11-2. یادگیری ماشین PAGEREF _Toc380062190 \h 11-3. الگوریتمهای یادگیری جمعی PAGEREF _Toc380062191 \h 31-4. دسته بندی کننده های سریال PAGEREF _Toc380062192 \h 41-5. ایده اصلی تحقیق PAGEREF _Toc380062193 \h 51-6. نگاهی کلی به فصول رساله PAGEREF _Toc380062194 \h 6فصل دومپیشینه تحقیق2. پیشینه تحقیق………………………………………………………………………………………………………………….. PAGEREF _Toc380062197 \h 82-1. مقدمه PAGEREF _Toc380062198 \h 82-2. اهمیت مسائل چندکلاسه PAGEREF _Toc380062199 \h 82-3. روشهای BOOSTING PAGEREF _Toc380062200 \h 112-3-1. مسائل دوکلاسه PAGEREF _Toc380062201 \h 132-3-2. مسائل چندکلاسه PAGEREF _Toc380062202 \h 14تکنیک های تجزیه کلاسی PAGEREF _Toc380062203 \h 15یکی-در مقابل-همه(OAA) PAGEREF _Toc380062204 \h 15یکی-در مقابل-یکی(OAO) PAGEREF _Toc380062205 \h 16روش P در مقابل Q PAGEREF _Toc380062206 \h 17روشهای Boosting چندکلاسه PAGEREF _Toc380062207 \h 18روش AdaBoost.M2 PAGEREF _Toc380062208 \h 18روش AdaBoost.OC PAGEREF _Toc380062209 \h 21روش AdaBoost.ECC PAGEREF _Toc380062210 \h 222-4. روشهای جمعی سريال PAGEREF _Toc380062211 \h 232-4-1. دسته‌بندی‌‌‌کننده‌ی سريال PAGEREF _Toc380062212 \h 24دسته‌بندی‌کننده‌های سريال همزمان PAGEREF _Toc380062213 \h 28ساختارهای سريال درختی PAGEREF _Toc380062214 \h 302-5. خلاصه PAGEREF _Toc380062215 \h 31فصل سومراهکارهای پیشنهادی3. راهکارهای پیشنهادی PAGEREF _Toc380062218 \h 333-1. مقدمه PAGEREF _Toc380062219 \h 333-2. روش LogitBoost سريال تودرتو PAGEREF _Toc380062220 \h 34کلیات روش PAGEREF _Toc380062221 \h 34جزییات روش PAGEREF _Toc380062222 \h 343-3. ساختار سریال پایش دادهها به کمک الگوریتم -kنزدیک‌ترین‌همسایه PAGEREF _Toc380062223 \h 393-4. خلاصه PAGEREF _Toc380062224 \h 41فصل چهارمروال آزمایشها4. روال آزمایشها……………………………………………………………………………………………………………….. PAGEREF _Toc380062227 \h 434-1. مقدمه PAGEREF _Toc380062228 \h 434-2. دسته‌بندی‌کننده‌های مورد استفاده برای مقایسه PAGEREF _Toc380062229 \h 434-2-1. دلایل انتخاب روشهای رقیب PAGEREF _Toc380062230 \h 434-2-2. جزییات پیادهسازی روشهای رقیب PAGEREF _Toc380062231 \h 444-3. معیارهای ارزیابی PAGEREF _Toc380062232 \h 464-4. مجموعه دادههای به‌کار رفته در آزمایشها PAGEREF _Toc380062233 \h 48مجموعه دادههای مربوط به مسائل چندکلاسه PAGEREF _Toc380062234 \h 48مجموعه دادههای مربوط به مسائل دوکلاسه PAGEREF _Toc380062235 \h 494-5. تست آماری فریدمن PAGEREF _Toc380062236 \h 504-6. خلاصه PAGEREF _Toc380062237 \h 52فصل پنجمنتایج5. نتایج………………………………………………………………………………………………………………………………. PAGEREF _Toc380062240 \h 545-1. مقدمه PAGEREF _Toc380062241 \h 545-2. نتایج حاصل از آزمایش هفت ترکیب مختلف از پارامترها برای روش پیشنهادی اول PAGEREF _Toc380062242 \h 545-2-1. تحلیل نتایج حاصل از آزمایش هفت ترکیب مختلف از پارامترها برای روش پیشنهادی اول PAGEREF _Toc380062243 \h 565-3. نتایج حاصل از آزمایش روش پیشنهادی اول و روشهای رقیب PAGEREF _Toc380062244 \h 585-4. نتایج حاصل از آزمایش روش پیشنهادی دوم PAGEREF _Toc380062245 \h 615-5. خلاصه PAGEREF _Toc380062246 \h 63فصل ششمنتیجه‌گیری و کارهای آینده6. نتیجهگیری و کارهای آینده PAGEREF _Toc380062249 \h 656-1. نتیجهگیری PAGEREF _Toc380062250 \h 656-2. کارهای آینده PAGEREF _Toc380062251 \h 66اختصارات………….. PAGEREF _Toc380062252 \h 67واژه نامه فارسی به انگلیسی PAGEREF _Toc380062253 \h 68واژه نامه انگلیسی به فارسی PAGEREF _Toc380062254 \h 72فهرست منابع……. PAGEREF _Toc380062255 \h 76
فهرست جداول
عنوان صفحه TOC \h \z \t “A-Table,1”
جدول 2-1.مثال از یک ماتریس کد گذاری به روش ECOC برای یک مساله چهار کلاسه PAGEREF _Toc380188609 \h 17جدول 3-1.ترکیب پارامتری استفاده شده در راستای تحلیل تاثیر پارامترهای موجود در الگوریتم پیشنهادی اول…….. PAGEREF _Toc380188611 \h 39جدول 4-1. جزییات مجموعه دادههای چندکلاسه PAGEREF _Toc380188613 \h 49جدول 4-2. جزییات مجموعه دادههای دوکلاسه PAGEREF _Toc380188614 \h 50جدول 5-1. مشخصات مجموعه دادههای استفاده شده برای بررسی تاثیر پارامترها در روش پیشنهادی اول……. PAGEREF _Toc380188616 \h 55جدول 5-2.مقادیر آزمایشی ترکیبات مختلف پارامترها برای روش پیشنهادی اول PAGEREF _Toc380188617 \h 55جدول 5-3.نرخ خطا و انحراف معیار به‌دست آمده از ترکیبات مختلف پارامترها برای روش پیشنهادی اول…………………………………………………………………………………………. PAGEREF _Toc380188618 \h 55جدول 5-4.میانگین رتبه بندی برای 7 ترکیب پارامتری مقایسه شده بر 11 مجموعه داده چندکلاسه………. PAGEREF _Toc380188619 \h 58جدول 5-5.تست فریدمن و تست تعقیبی Bonferroni-Dunn. برای 7 ترکیب پارامتری ، اختلافات معنادار با فونت توپر نمایش داده شده است. PAGEREF _Toc380188620 \h 58جدول 5-6.نتایج حاصل از اعمال روش پیشنهادی اول و روشهای رقیب، در قالب نرخ خطای آزمایش و انحراف معیار PAGEREF _Toc380188621 \h 59جدول 5-7.میانگین رتبه بندی برای 5 روش مقایسه شده بر 11 مجموعه داده چندکلاسه PAGEREF _Toc380188622 \h 60جدول 5-8.نتایج تست فریدمن و تست تعقیبی Bonferroni-Dunn. برای روش پیشنهادی اول، اختلافات معنادار با فونت توپر نمایش داده شده است. PAGEREF _Toc380188623 \h 60جدول 5-9. نتایج اعمال روش پیشنهادی دوم و روشKNN به ازای مقادیر مختلف k، در قالب نرخ خطای آزمایش و انحراف معیار PAGEREF _Toc380188624 \h 61جدول 5-10.میانگین رتبه بندی برای 4 روش بر روی 12 مجموعه داده دوکلاسه PAGEREF _Toc380188625 \h 62جدول 5-11.نتایج تست فریدمن و تست تعقیبی Bonferroni-Dunn. برای روش پیشنهادی دوم، اختلافات معنادار با فونت توپر نمایش داده شده است. PAGEREF _Toc380188626 \h 62
فهرست الگوریتم‌ها
عنوان صفحه
TOC \h \z \t “A-Algorithm,1” الگوریتم 1.شبه کد مربوط به روش AdaBoost PAGEREF _Toc380061795 \h 14الگوریتم 2.شبه کد مربوط به روش AdaBoost.M2 PAGEREF _Toc380061796 \h 19الگوریتم 3.شبه کد مربوط به روش AdaBoost.OC PAGEREF _Toc380061797 \h 21الگوریتم 4.شبه کد مربوط به روش AdaBoost.ECC PAGEREF _Toc380061798 \h 23الگوریتم 5.ساختار سريال Viola-Jones PAGEREF _Toc380061799 \h 25الگوریتم 6.شبه کد مربوط به فاز آموزش ساختار سریال پیشنهادی اول PAGEREF _Toc380061800 \h 38الگوریتم 7.شبه‌کد مربوط به الگوریتم LogitBoost برای مسائل چندکلاسه PAGEREF _Toc380061801 \h 46
فهرست شکل ها
عنوان صفحه TOC \h \z \t “A-Figure,1”
شکل 2-1.ساختار سريال Viola-Jones [42] PAGEREF _Toc380062485 \h 26شکل 2-2.ساختار دسته‌بندی‌کننده سريال همزمان PAGEREF _Toc380062486 \h 29شکل 2-3.ساختار درختی ارائه شده توسط لینهارت PAGEREF _Toc380062488 \h 31شکل 3-1.ساختار کلی روش دستهبندی سريال پیشنهادی اول PAGEREF _Toc380062490 \h 35شکل 3-2.مکانیزم انتقال داده از یک لایه به لایه بعدی در روش پیشنهادی اول PAGEREF _Toc380062491 \h 37شکل 3-3.ساختار سريال پیشنهادی دوم PAGEREF _Toc380062492 \h 40
فصل اولمقدمه
مقدمهمقدمه
امروزه شاهد رشد عظیمی در تولید داده هستیم. فعالیت‌ها و تعامل‌های روزانه انسان‌ها، حجم چشمگیری از دادهها و اطلاعات را به وجود می‌آورد؛ به عنوان مثال در ارتباطات از راه دور، تراکنش های‌مالی و بانکی، شبکه‌های اجتماعی، فعالیت‌های اینترنتی عام، امور مربوط به بهداشت و درمان، پایش اطلاعات امنیتی، اطلاعات و دادههای آماری مانند سرشماری نفوس و بسیاری موارد دیگرCITATION JHa \m IoH \l 1033 [1,2]. با پیشرفت چشمگیر تجهیزات سخت افزاری، هزینه ذخیره داده کم شده است؛ این در حالی است که آنالیز صحیح و استخراج اطلاعات مفید از این حجم از داده به یک دغدغه تبدیل شده است. هوش مصنوعی و به ویژه حوزه یادگیری ماشین، به دنبال یافتن روش‌ها و ابزار‌های موثر جهت رفع این مشکل می باشد.
یادگیری ماشین
اصلی‌ترین زمینه تحقیقاتی در حوزه یادگیری ماشین، شناسایی الگو است؛ یعنی استخراج اطلاعات و الگو‌های تکرار شونده از داده ورودی، که این اطلاعات برای انجام تصمیم‌گیری در مورد دادههای نادیده کاربرد دارد.
بر اساس نوع پیش بینی دادههای نادیده، انواع روشهای شناسایی الگو را می توان به دو گروه کلی روشهای مبتنی بر دستهبندی و روشهای مبتنی بر رگرسیون تقسیم‌بندی کرد. سیستم‌های مبتنی بر دستهبندی، سعی در ساختن مدلی دارند که خروجی آن گسسته می‌باشد و این خروجی در واقع برچسب کلاسی است که سیستم برای یک نمونه خاص پیشنهاد می‌دهد؛ در مقابل، سیستم‌های مبتنی بر رگرسیون، تابعی پیوسته را مدل می‌کنند و خروجی آنها به صورت عددی می‌باشد.
یادگیری ماشین را میتوان به چهار دسته کلی یادگیری با نظارت و یادگیری بدون نظارت، یادگیری نیمه نظارتی و یادگیری فعال تقسیم‌بندی کرد. در یادگیری با نظارت، سیستم با دادههای آموزشی که دارای برچسب‌های کلاس معین هستند آموزش داده میشود. این گروه از الگوریتم‌ها که بسیار رایج نیز می‌باشند، سعی در ساخت مدلی دارند که به بهترین نحو دادههای آموزشی را به برچسب کلاس داده شده‌ی آنها مرتبط سازند. مدل ساخته شده بر این اساس، در مرحله آزمایش سعی در پیش بینی برچسب کلاس دادههای آزمایشی خواهد کرد. در مقابل این گروه از الگوریتم ها، الگوریتم های مبتنی بر یادگیری بدون نظارت، بدون دریافت برچسب کلاس دادههای آموزشی، سعی در دستهبندی دادههای آموزشی می‌کنند؛ به این نوع از یادگیری، خوشه‌بندی نیز گفته میشود. گاهی تنها بخشی از برچسب کلاس دادههای آموزشی در دسترس است بنابر این دسته سوم از الگوریتم‌ها، یعنی الگوریتمهای نیمه‌نظارتی، عملکردی مابین الگوریتمهای نظارتی و الگوریتمهای بدون نظارت دارند. در یادگیری فعال، سیستم در مرحله آموزش، با انسان تعامل دارد؛ به این صورت که انسان برچسب‌های مناسب را به دادههای ورودی نسبت می‌دهد و سیستم با توجه به برچسب‌های اختصاص داده شده، به پایش اطلاعات خود و مدل آموزشی می‌پردازد.
این رساله منحصرا بر روشهای دستهبندی مبتنی بر یادگیری نظارتی تمرکز دارد. به بیان رسمی‌تر، الگوریتم‌هایی که از یک مجموعه آموزشی مانند D، شامل n داده نمونه ورودی به فرم {(x1,y1),…, (xn,yn)} که هر نمونه متشکل از یک بردار خصیصه xi=(x1,…, xd)∈R با بعد d و یک برچسب کلاس yi∈Y که Y∈{0,…,k} برای مسائل K کلاسه، آموزش میبینند و خروجی این آموزش، یک دسته‌بندی‌کننده یا فرضیه است که در حالت ایده آل یک مرزبندی تصمیم دقیق برای جداسازی کلاسها در کل فضای R انجام خواهد داد.
الگوریتمهای یادگیری جمعیالقای دسته‌بندی‌کننده ها هنگامی که تعداد دادههای آموزشی به طرز چشمگیری زیاد باشد با مشکل رو‌به‌رو خواهد شد. این پدیده باعث به وجود آمدن مرزهای کلاس پیچیده میشود؛ یادگیری دقیق این مرز‌ها، برای دسته‌بندی‌کننده‌هایی که سعی در تولید یک قانون برای توصیف داده دارند، به چالشی عظیم تبدیل می شود. پیچیدگی این وضعیت زمانی به اوج خود می رسد که بردار خصیصه دادهها، دارای ابعاد بالا باشد.
رواج خانواده خاصی از الگوریتمهای یادگیری ماشین، تحت عنوان الگوریتمهای یادگیری جمعی که سعی در مواجهه و برطرف نمودن چالش‌های موجود دارند، طی سال‌های اخیر بسیار چشمگیر بوده است. این دسته از الگوریتم‌ها، موفقیت خود را مرهون عملکرد محافظه‌کارانه خود می‌باشند. در حالی که اکثر الگوریتمهای یادگیری از القای یک دسته‌بندی‌کننده برای توصیف داده استفاده می‌کنند، الگوریتمهای یادگیری جمعی از تعداد زیادی یادگیر‌های ضعیف، که قدرت پیش بینی آنها اندکی بهتر از حدس تصادفی است، بهره می برند. به بیان دیگر، ایده اصلی الگوریتمهای یادگیری جمعی، به‌کارگیری چندین یادگیر و ترکیب نتیجه پیشبینی آنها به عنوان یک گروه از دستهبندیکنندهها و بالا بردن دقت کلی یادگیری است. به هر یک از اعضای موجود در این گروه از یادگیرها، یادگیر پایه گفته میشود. در مسائل دستهبندی، الگوریتم یادگیری جمعی به عنوان سیستم دستهبندی چندگانه، ائتلاف دسته‌بندی‌کننده ها، کمیتهای از دستهبندیکنندهها و یا ترکیب دستهبندیکنندهها نیز خوانده میشود. پیشبینی هر یک از اعضا ممکن است به صورت یک عدد حقیقی، برچسب کلاس، احتمال پسین و یا هر چیز دیگری باشد. چگونگی ترکیب رأی اعضای الگوریتم، در نتیجهگیری نهایی بسیار مهم است که شامل میانگین‌گیری، رأی به اکثریت و روشهای احتمالی میشود.
دسته بندی کننده های سریال
ویولا و جونزCITATION Jon \l 1033 [3] در سال 2001 برای اولین بار قوانین روشهای مبتنی بر یادگیری جمعی را به کمک مفهوم یادگیری کلان-به-جزیی توسعه دادند. با این گام عظیم، آنها روشی را ابداع کردند که انجام دستهبندی دقیق و سریع بر روی مجموعه دادههای تشخیص چهره، که شامل صدها هزار داده بودند، را امکان پذیر می ساخت. روش ابداعی آنها به صورت یک ساختار سريال بود که دسته‌بندی‌کننده‌های جمعی را در لایه‌های متوالی به صورتی کنار هم قرار می‌داد که لایه‌های اولیه شامل تعداد کمی از دستهبندیکنندهها بود و این تعداد در لایه‌های بعدی به مرور افزایش می‌یافت. این روش تاثیر بسزایی در تولید دسته‌بندی‌کننده های پیمانه‌بندی‌شده و دقیق داشت که به طبع، نه تنها در زمینه تشخیص چهره، بلکه در زمینه‌های مختلف کاربرد داشت. با این حال آموزش دسته‌بندی‌کننده‌های موثر با استفاده از روش ویولا و جونز، به علت زمانبر بودن بیش از حد مرحله آموزش، تقریبا مقرون‌به‌صرفه نبود.
در تلاشی برای کاهش زمان آموزش دسته‌بندی‌کننده‌های سريال در مواجهه با مجموعه دادههای بسیار بزرگ، بارکزاک و همکارانCITATION AoL \l 1033 [4] یک روش سریال تودرتو ارایه کردند. آنها نام روش خود را PSL نهادند که بیانگر دسته‌بندی‌کننده‌های تودرتوی سريال متشکل از دسته‌بندی‌کننده‌های قوی موازی در هر لایه است.
ایده اصلی تحقیقساختار سريال کلاسیک ارایه شده توسط ویولا و جونز برای مسائل دوکلاسه تعریف شده است و الگوریتم آنها برای حل مسائلی که دادههای مربوط به کلاس مثبت در مقایسه با دادههای متعلق به کلاس منفی به شدت کم‌پیشامد هستند، کارایی دارد. همچنین مدل‌ها و الگوریتمهای توسعه یافته بر اساس ساختار پیشنهادی ویولا و جونز نیز بیشتر متمرکز بر حل مسائل با دادههای نامتوازن هستند. بنابراین یکی از اصلی‌ترین اهداف این مطالعه، طراحی مدلی از دسته‌بندی‌کننده‌های سريال است که برای مسائل چندکلاسه و نه لزوما نامتوازن، مناسب باشند. به طور کلی تمرکز این مطالعه بر ارایه مدلی نوین از ساختارهای سریال تودرتو با هدف افزایش دقت دسته‌بندی‌کننده‌های سريال است.
مشارکت این تحقیق نه تنها بر حل نامتوازن و کم‌پیشامد، بلکه بر حل مسائلی با توزیع دادهای متوازن است؛ همچنین در این مطالعه، برآنیم که از ساختارهای سریال به عنوان ابزاری برای رفع نیاز به پیدا کردن kی بهینه در روش KNN، استفاده کنیم. به صورت فهرست‌وار، اهداف اصلی این تحقیق عبارتند از:
حل مسائل چندکلاسه با توزیع دادهای متوازن و نامتوازن به کمک ساختاری نوین از دسته‌بندی‌کننده‌های سريال
بالا بردن دقت دستهبندی در زمینه حل مسائل چندکلاسه، با استفاده از ساختار سريال دستهبندیکنندهها
استفاده از ساختار سريال برای رفع نیاز به پیدا کردن بهترین k در روش k-نزدیک‌ترین همسایه
نگاهی کلی به فصول رسالهاین رساله به شش فصل تقسیم شده است. در ادامه‌ی مقدمه که در فصل اول آمده است، فصل دوم به بررسی روش‌ها و الگوریتمهای مرسوم برای حل مسائل دوکلاسه و چندکلاسه و معرفی روشهای دستهبندی سريال و بیان نقاط ضعف و قوت آنها می‌پردازد. در فصل سوم، جزییات روشهای پیشنهادی به تفصیل ارائه میشود. فصل چهارم بر معرفی معیارهای ارزیابی روش‌ها، معرفی مجموعه دادههای استفاده شده در تحقیق و معرفی تست آماری مورد استفاده برای مقایسه نتایج الگوریتمهای پیشنهادی با سایر روش‌ها تمرکز دارد. در فصل پنجم، نتایج حاصل از بررسی و مقایسه الگوریتمهای پیشنهادی با سایر روش‌ها گزارش شده است. و در نهایت، فصل ششم به نتیجهگیری و بیان کارهای آینده می‌پردازد.
فصل دومپیشینه تحقیق
پیشینه تحقیقمقدمهاین فصل به معرفی و بررسی تحقیقات پیشین در زمینه حل مسائل دوکلاسه و چندکلاسه توسط روشهای یادگیری جمعی موفق و به خصوص راهکارهای سريال جمعی می‌پردازد و نقاط ضعف و قدرت هر یک را برمی‌شمرد. در ابتدای این فصل ابتدا از آنجایی که شراکت اصلی این تحقیق در بهبود حل مسائل چندکلاسه است، به لزوم تمرکز بر حل مسائل چندکلاسه خواهیم پرداخت و کارهای پیشین انجام شده در این حیطه را معرفی خواهیم کرد. سپس به بررسی انواع روشهای یادگیری جمعی خواهیم پرداخت. روشهای کلاسه‌بندی سريال در رقابت تنگاتنگی با روشهای یادگیری جمعی تقویتی هستند؛ لذا، قبل از پرداختن به ساختارهای سريال موجود، روشهای یادگیری جمعی مورد بررسی قرار خواهند گرفت؛ از طرفی اکثر قریب به اتفاق روشهای سريال، متمرکز بر دادههای نامتوازن مانند زمینه تشخیص چهره هستند، بنابراین به علت تکیه این مطالعه بر به کار بستن ساختار جدیدی از دسته‌بندی‌کننده‌های سريال برای حل مسائل دوکلاسه و چند‌کلاسه‌ای که لزوما نامتوازن نیستند، لزوم مرور روشهای موفق جمعی تقویتی کاملا آشکار است.
اهمیت مسائل چندکلاسهاکثر تحقیقات در زمینه یادگیری ماشین متمرکز بر مسائل دوکلاسه هستند. شماری از تکنیک‌های موفق و معروف یادگیری ماشین، نظیر طبقه‌بندی‌کننده‌های تقویتی، بردارهای پشتیبانCITATION CoC \l 1033 [5] و روش RIPPERCITATION WWC1 \l 1033 [6] در اصل برای مسائل دوکلاسه طراحی شده‌اندCITATION ACL \l 1033 [7]. البته لازم به ذکر است که روش RIPPER با هدف حل مسائل چندکلاسه تعریف شد اما این روش در واقع حاصل ترکیب دو روشREP CITATION CAB \l 1033 [8] وIREP CITATION JFu94 \l 1033 [9] می‌باشد که هر دوی این روش‌ها در حوزه‌ی مسائل دوکلاسه تعریف شده‌اند. اما واقعیت این است که بسیاری از مسائل طبقه‌بندی در دنیای واقعی ابدا دوکلاسه نیستند بلکه متعلق به مسائل چندکلاسه می‌باشند. احتمال طبقه‌بندی نادرست در مسائل چندکلاسه بسیار بالاست و این احتمال با بالا رفتن تعداد کلاسها، به سرعت افزایش می‌یابد CITATION ACL \l 1065 [7]. بنابراین واضح است که رسیدن به دقت بالا، در مسائل چندکلاسه، بسیار مشکل‌تر از مسائل دوکلاسه است.
تاکنون روشهای موثر متفاوتی برای حل مسائل چندکلاسه ارائه شده است. این روش‌ها را می توان به دو دسته کلی تقسیم کرد:
روشهای مبتنی بر تقسیم-و-تسخیر
روشهای مبتنی بر تفکیک-و-تسخیر
دسته روشهای تقسیم-و-تسخیر بر مبنای ایجاد درخت تصمیم‌گیری بر روی دادههای آموزشی استوار هستند. به این صورت که نقاط تصمیم‌گیری در هر لایه از درخت تصمیم‌گیری، بر اساس آزمایش بر انواع ویژگی‌های داده، محاسبه میشود و دادهها بر اساس این آزمایش، طبقه‌بندی میشوند. این روند به صورت بازگشتی آنقدر انجام میشود تا زمانی که دقت مورد نظر کسب شود. از جمله الگوریتمهای متعلق به این دسته، میتوان بهCART CITATION LBr \l 1033 [10]،ID3 CITATION JRQ86 \l 1033 [11]، C4.5 CITATION WWC1 \l 1065 [6] و توسعه یافته آن C5.0 اشاره کرد که پیچیده‌ترین روشهای القای درختی در دو دهه اخیر هستند CITATION SCS11 \l 1033 [12].
در روشهای مبتنی بر تفکیک-و-تسخیر، الگوریتم در هر زمان فقط بر یک کلاس تمرکز می‌کند. به بیان دیگر الگوریتمهای این دسته سعی دارند که در هر زمان، قوانینی را تولید کنند که بیشترین تعداد داده متعلق به کلاس جاری را به درستی پیدا کرده و تا حد ممکن دادههای غیر از آن کلاس را نادیده بگیرند. پس از هر دور تولید قانون به روش مذکور، داده‌هایی که درست دستهبندی شده‌اند از دادههای آموزشی حذف شده، سپس مابقی دادهها در دورهای آینده به صورت تکرار شونده، با روالی مشابه، مورد آموزش قرار می‌گیرند. الگوریتم‌هایی نظیرPRISM CITATION Cen87 \l 1033 [13]، IREP CITATION JFu94 \l 1065 [9] و RIPPER CITATION WWC1 \l 1065 [6] از معروف‌ترین و موثرترین الگوریتمهای این دسته می‌باشند.
به طور کلی روشهای مبتنی بر تقسیم-و-تسخیر، بیشتر بر بالا بردن دقت تمرکز دارند؛ در حالی که روش های مبتنی بر تفکیک-و-تسخیر از سادگی و سرعت بالاتر، در ازای کاهش نسبی دقت، بهره می‌برند.
فرنک و ویتن در سال 1998 سعی کردند که دو روش تقسیم-و-تسخیر و تفکیک-و-تسخیر را از طریق استفاده از روش القای جزئی درخت تصمیم‌گیری، ترکیب کنندCITATION EFr \l 1033 [14]. روش آنها در واقع یک روش مبتنی بر تفکیک-و-تسخیر بود که تفاوت اصلی آن با سایر روشهای این دسته در چگونگی تولید قوانین در هر دور از اجرای الگوریتم بود. الگوریتم آنها بر ساختن درخت تصمیم‌گیری هرس شده در هر دور بر دادههای موجود و برگزیدن برگ با بیشترین پوشش، استوار بود. این روش ترکیبی، بیش‌هرس‌شدگی را تخفیف می‌دهد اما نیاز به بهینه‌سازی سراسری دارد CITATION IoH \l 1065 [2].
سایر روشهای اتخاذ شده در راستای حل مسائل چندکلاسه، از روشهای موفق در زمینه مسائل دوکلاسه بهره می‌جویند؛ به این صورت که سعی دارند این روش‌ها را بر مسائل چندکلاسه به گونه‌ای تطبیق دهند. این در حالی است که به کار گرفتن این استراتژی ساده نیست و در بسیاری از مواقع کاملا غیر عملی استCITATION APa \l 1033 [15]. اچ اس یو و لینCITATION CWH \l 1033 [16] طی تحقیقی نشان دادند که استفاده از بردارهای پشتیبان در این شرایط موجب بالا رفتن هزینه آموزش به طرز قابل توجهی میشود. بنابر دلایل ذکر شده، یکی از روشهای متداول، به جای تطبیق دادن الگوریتمهای حوزه دوکلاسه برای شرایط چندکلاسه، شکستن مساله چندکلاسه به تعدادی مساله دوکلاسه می‌باشدCITATION LiL \l 1033 [17]. مزیت استفاده از این روش این است که پیچیدگی برای القای یک طبقه‌بندی‌کننده در این شرایط کاهش می‌یابد. همچنین وقتی که دو برچسب کلاس در هر مقطع زمانی با هم مقایسه میشوند امکان جداسازی خطی آنها بسیار بالاست؛ این در حالیست که چنین امکانی در زمانی که همه برچسب‌های کلاسها با هم در نظر گرفته شوند، وجود ندارد.
بنابر تحقیقات و مطالعات اخیر متخصصان در حوزه طبقه‌بندی مسائل چندکلاسه، استفاده از طبقه‌بندی‌کننده‌های سریال برای مواجهه با چالش‌های موجود، هنوز به صورت یک مساله حل نشده و باز پابرجاستCITATION CZh \l 1033 [18]. از جمله روشهای متداول ارائه شده در زمینه طبقه‌بندی‌کننده‌های سریال برای حل مسائل چندکلاسه، می توان به ساخت طبقه‌بندی‌کننده‌های سریال برای هر کلاس و استفاده جداگانه و موازی هر یک از این طبقه‌بندی‌کننده‌های سريال و همچنین ساختن درخت‌های ردیاب سريال اشاره کرد.
روشهای BOOSTINGBoosting CITATION RES90 \l 1033 [19] یک روش کلی برای بهبود دقت یادگیر‌های ضعیف، توسط یک پروسه تکرار‌شونده است. شپیر در سال 1990 اثبات کرد که یادگیر‌های ضعیف، که عملکرد آنها اندکی بهتر از حدس تصادفی است، می توانند طوری با هم ترکیب شوند که یک یادگیر قوی و دقیق را تشکیل دهند.
روش Boosting همانند Bagging از باز‌نمونه‌گیری دادهها و تلفیق خروجی یادگیرها با استفاده از رای به اکثریت، بهره می‌برد. اما Boosting، عملیات باز‌نمونه‌گیری را طوری انجام می‌دهد که تمرکز یادگیری بیشتر به سمت نمونه‌های سخت‌تر معطوف شود.
الگوریتم اصلی و ابتدایی Boosting، سه دسته‌بندی‌کننده ضعیف را به وجود می‌آورد. اولین دسته‌بندی‌کننده ضعیف با نام c1، توسط زیر مجموعه دادهای تصادفی S1 آموزش داده میشود. دسته‌بندی‌کننده بعدی با نام c2 با زیر مجموعه دادهای S2، که نیمی از آن متشکل از نمونه‌های درست دستهبندی شده توسط c1 و نیمی دیگر از نمونه‌های غلط دستهبندی شده توسط c1 است، آموزش داده میشود. در نهایت دسته‌بندی‌کننده c3 توسط S3 آموزش داده میشود که S3 شامل نمونه‌هایی است که c1 و c2 در مورد آنها اتفاق نظر ندارند.
با فرض خطای tε برای بهترین دسته‌بندی‌کننده t عضو یک یادگیر جمعی و اینکه هر کدام از دستهبندیکنندهها دارای خطای کمتر از 5/0 باشند، یعنی fε<0.5 ، شپیر نشان داد CITATION RES90 \l 1065 [19] که خطای الگوریتم boosting جمعی دارای کرانه بالای زیر می‌باشد:
fεt=3εt-2εt3
این بدان معنی است که یادگیر جمعی تقویتی همیشه بهتر از هر یک از یادگیر‌های پایه‌اش عمل می‌کند. به علت وجود این نکته جالب، boosting توجه بسیاری از محققین را به خود جلب کرد. قابل ذکرترین محصول از روشهای boosting را میتوان الگوریتم AdaBoost دانست که در ابتدا برای حل مسائل دوکلاسه پیشنهاد شد. کارایی تضمین شده‌ی این الگوریتم باعث شده که به یکی از موثرترین روش ها در زمینه هوش محاسباتی بدل شود CITATION RPo06 \l 1033 [20]. موفقیت این الگوریتم باعث به وجود آمدن گونه‌های بسیاری از آن و همچنین بسط‌هایی برای حل مسائل چندکلاسه شد که در ادامه این فصل برخی از آنها معرفی خواهند شد.مسائل دوکلاسهالگوریتم AdaBoost (الگوریتم 1.) روش اصلی و ابتدایی boosting را با معرفی یک پروسه تکرار‌شونده بهبود بخشید. بنیادی‌ترین تفاوت بین آنها این است که AdaBoost از توزیع غیر یکنواخت D از دادهها برای جایگزینی باز‌نمونه‌گیری استفاده می‌کند؛ علاوه بر آن به جای استفاده از روش رای به اکثریت برای تلفیق نتایج یادگیرها، از ترکیبی وزن‌دار از رای یادگیرها بهره می‌جوید.
الگوریتم AdaBoost ابتدا کار خود را با توزیع یکنواخت وزن برای همه نمونه‌ها آغاز می‌کند. برای هر توزیع Dt ، یک دسته‌بندی‌کننده ضعیف ht القا و به سیستم افزوده میشود. سپس خطای وزن‌دار tε بر توزیع Dt محاسبه میشود و بررسی میشود که شرط 12 > tε برقرار باشد. وزن رای ht برابر است با 1εt . سپس Dt+1 به روز رسانی می شود به طوری که وزن نمونه‌هایی که اشتباه دستهبندی شده‌اند به تناسب دقت ht افزایش می‌یابد. در این مرحله، وزن‌ها نرمال میشوند و وزن داده‌هایی که درست دستهبندی شده‌اند کاهش می‌یابد. با این مکانیزم، یادگیری برای هر توزیع t+1، بیشتر به سمت دادههای سخت‌تر متمایل میشود. این الگوریتم، خطا و واریانس دادههای آموزشی را کاهش داده امّا بسیار به نویز موجود در داده حساس است CITATION EBa99 \l 1033 [21].
Input: A set of training examples (x1 ,y1 ), …, (xn ,yn ) where xi is a feature ∈X and yi is a class ∈-1,+1 , n is the number of elements and with T as the number of boosting rounds.
Output: A linear combination of weak classifiers ht(xi ), each a factor αt.
1 D1(xi ) = 1n , i=1, …, n2 for t=1 to T do
3 ht= WeakLearner( Dt)
4 εt = in( Dt(xi ) ht(xi ) yi)5 αt= 12 ln((1- εt ) εt ) 6 for i=1 to n do
7 Dt+1(xi ) = Dtxi exp(-αt yt htxi )
8 end
9 Dt+1xi = Dt+1(xi ) in Dt+1(xi ) 10 end
11 return Hx =Sign(tTαt htx)شبه کد مربوط به روش AdaBoostمسائل چند‌کلاسهدر دو دهه اخیر شاهد ازدیاد ارایه گونه‌های مختلف از الگوریتم AdaBoost هستیم که تعدادی از آنها عبارتند از: الگوریتمRealBoost CITATION YFr \l 1033 [22] که خروجی یادگیرها را بر اساس درجه اطمینان آنها بسط می‌دهد، GentelAdaBoost CITATION JFr \l 1033 [23] که در مقابل دادههای پرت مقاوم‌تر است، CITATION SZL02 \l 1033 [24]FloatBoost که با هدف کم کردن افزونگی در دستهبندیکنندهها از طریق هرس ارایه شد، CITATION CXZ08 \l 1033 [25]Local boosting که با استفاده از روش تقویت به وسیله باز‌نمونه‌گیری به دقت و مقاومت بیشتر در مقابل دادههای نویزی دست یافت، Asymmetric AdaBoost CITATION Jon \l 1065 [3] که قالب به روز رسانی وزن دادهها را به صورت افزایش وزن دادههای دلخواه کلاس مثبت تغییر داد، بوهولمن و هوتورن CITATION PBu10 \l 1033 [26]روش Twin Boost را پیشنهاد کردند و گزارش کردند که این روش از یک متد پیشرفته انتخاب خصیصه استفاده می‌کند که منجر به تشکیل یادگیر‌های جمعی ساده‌تر و دقیق‌تر میشود.
دستهبندی مسائل چندکلاسه در مقایسه با مسائل دوکلاسه با چالش‌های مهمتری مواجه است به علت اینکه احتمال بروز خطا در این دسته از مسائل به مراتب بالاتر است. یکی از روشهای متداول برای حل مسائل چندکلاسه، شکستن آنها به تعدادی مسائل دوکلاسه به جای اعمال مستقیم الگوریتمهای حل مسائل چندکلاسه است CITATION ACL \l 1065 [7]. در ادامه به روشهای مختلف موجود در راستای شکستن مسائل چندکلاسه خواهیم پرداخت.
تکنیک های تجزیه کلاسیرایج‌ترین تکنیک‌های تجزیه کلاسی، روشهای یکی-در مقابل-یکی (OAO) و یکی-در مقابل-همه (OAA) است CITATION All01 \l 1033 \m LLi06 [27,28].
یکی-در مقابل-همه(OAA)روش یکی-در مقابل-همه، k دسته بندی کننده را برای یک مساله k-کلاسه می‌سازد. هر دسته‌بندی‌کننده برای شناختن یک کلاس در مقابل سایر کلاسها آموزش داده میشود. در زمان بازیابی، خروجی ایده آل آن است که همه دستهبندیکنندهها به یک کلاس رای دهند؛ از آنجایی که اغلب موارد شرایط به این خوبی پیش نمی‌رود، تساوی رای‌ها به صورت دلخواه و مستبدانه شکسته میشود CITATION VGu99 \l 1033 [29]یا یک ارزش اضافی برای میزان اعتبار هر دسته‌بندی‌کننده طوری تعریف شود که از به وجود آمدن شرایط نامطلوب جلوگیری کند CITATION Kre99 \l 1033 [30]. یکی از معایب این روش این است که در مواجهه با دادههای آموزشی نامتوازن قادر به ساختن مرز تصمیم‌گیری دقیق نیستCITATION Rok10 \l 1033 \m RJi07 \m HHe09 [31,32,33].
یکی-در مقابل-یکی(OAO)روش یکی-در مقابل-یکی که به دستهبندی دورهای نیز معروف است، به این صورت عمل می‌کند که مجموعه دادههای یک کلاس در مقابل نمونه‌های سایر کلاسها آموزش داده میشود؛ به گفته دیگر اگر k کلاس داشته باشیم آنگاه kk-12 دسته‌بندی‌کننده دوکلاسه خواهیم داشت. با وجود اینکه پیچیدگی زمانی تولید این تعداد دسته‌بندی‌کننده از مرتبه k2 است اما در مقابل آموزش این دستهبندیکنندهها ، به علت دوکلاسه بودن، بسیار سریع انجام میشود. از طرف دیگر با این روش مرز تصمیم‌گیری با آزادی بیشتری نسبت به حالتی که کل کلاسها با هم در نظر گرفته میشوند، تخمین زده میشودCITATION JFu97 \l 1033 [34]. ساده‌ترین و رایج‌ترین راه ترکیب نتیجه دستهبندیکنندهها، گرفتن رأی به اکثریت است CITATION Kre99 \l 1065 [30]. بزرگترین مشکل استفاده از روش رای به اکثریت در اینجا این است که تعداد زیادی رای توسط دستهبندیکنندهها تولید میشود که برخی رای‌ها، به علت بی‌ربط بودن کلاسها به تعدادی از دستهبندیکنندهها، از درجه اعتبار کمی برخوردار هستند. یکی از نقاط قوت این الگوریتم این است که باعث ایجاد عدم توازن در توزیع کلاسی نمیشود و میتوان آن را به شیوه‌ی یادگیری افزایشی نیز پیادهسازی کرد. زمانی که کلاس جدیدی از داده، به دادههای قبلی افزوده میشود، میتوان k دسته‌بندی‌کننده جدید دیگر آموزش داد و بدون تأثیر روی سایر دستهبندیکنندهها، به مجموعه افزود.
روش P در مقابل Qدر این روش P عدد از مجموعه k کلاس در مقابل Q عدد دیگر از آنها آموزش میبینند و پروسه آموزش چندین بار تکرار میشود. P کلاس مختلف از داده هر بار انتخاب میشوند. در این روش انتخاب کدام P کلاسها، بر مبنای یک کدواژه با بیتهای صفر و یک انتخاب میشود. روشهای مختلفی برای ساخت این کدواژه وجود دارد که معروف‌ترین آنهاECOC است CITATION Die94 \l 1033 [35]. روش ECOC یک ماتریس کد گذاری می‌سازد که یک نمونه از آن را در جدول2-1. مشاهده می‌کنید. این ماتریس نحوه‌ی آموزش دستهبندیکنندهها را نشان می‌دهد. k تعداد سطر‌های ماتریس و برابر با تعداد کلاسها و i تعداد ستون‌های آن و برابر با تعداد دستهبندیکنندهها است؛ همچنین k > 2 و i > k می باشد. مقادیر دودویی هر یک از ستون‌ها به گونه‌ای انتخاب میشود که مقدار هر سطر یکتا باشد. هنگامی که داده‌ی نادیده‌ای مانند x، وارد سیستم می شود، هر کدام از دسته‌بندی‌کننده‌های fix∈0,1 در مورد داده نظر می‌دهند؛ تلفیق نظرات همه دستهبندیکنندهها، یک کدواژه تولید می‌کند که فاصله همینگ آن از هر کدام از سطر‌های ماتریس محاسبه و کوچکترین آنها انتخاب میشود. کلاس پیش‌بینی‌شده آن داده، برچسب نظیر سطر انتخاب شده خواهد بود.
مثال از یک ماتریس کد گذاری به روش ECOC برای یک مساله چهار کلاسهClassifiersf6f5f4f3f2f1class111111c1110000c2001100c3101010c4f6(x)f5(x)f4(x)f3(x)f2(x)f1(x)output
یکی از مهم‌ترین معایب این روش آن است که کارایی آن به نوع کلاسهبند و نوع کدواژه بسیار وابسته است CITATION RJi07 \l 1065 [32].روشهای Boosting چند‌کلاسهاولین الگوریتم تعمیم یافته AdaBoost برای حل مسائل چندکلاسه، الگوریتمAdaBoost.M1 CITATION Fre96 \l 1033 [36] است. نیاز به تولید خطای وزن‌دار بهتر از 12 در هر دور از اجرای الگوریتم AdaBoost ، اولین مانعی بود که در راستای تعمیم AdaBoost برای حل مسائل چندکلاسه وجود داشت. برای اکثر مسائل چندکلاسه k > 2 ، برقراری این شرایط بسیار سخت‌تر از موارد حدس تصادفی 1k است؛ بنابراین بایستی از دسته‌بندی‌کننده‌های قوی‌تری مانند C4.5 استفاده کرد که این دستهبندیکنندهها باعث بالا رفتن زمان آموزش میشود. اخیرا آیبیل و فایفرCITATION Eib05 \l 1033 [37] و زو و همکارانCITATION JZh06 \l 1033 [38] به ترتیب روشهای AdaBoost.MW و SAMME را پیشنهاد کردند. تغییراتی که آنها در AdaBoost ایجاد کردند، باعث شد که دسته‌بندی‌کننده‌های ضعیفی تولید شود که خطای آنها اندکی بهتر از حدس تصادفی 1k باشد.
روش AdaBoost.M2روییند و شپیر CITATION YFr \l 1065 [22] نیز یک روش قوی به نام AdaBoost.M2 ارایه کردند که قدرت آن در این نکته است که نه‌تنها نمونه‌های سخت را یاد می‌گیرد، بلکه برچسب کلاس‌های نادرست را هم یاد می‌گیرد؛ به این صورت که یک توزیع برای نمونه‌های اشتباه تعریف میشود تا روند آموزش و تقویت با هم تلفیق شوند. این امر توسط تعریف مجموعه محتمل μ که μ ϵ Yو Y کل مجموعه برچسب کلاسها است انجام میشود؛ سپس فرضیه ضعیف، یک پیشبینی دوگانه برای نمونه x انجام می‌دهد که این پیشبینی صرفا مشخص می‌کند که نمونه، عضو مجموعه محتمل است یا نه. خروجی فرضیه ضعیف، به صورت شبه-زیان است. فرضیه‌ای که کمترین شبه-زیان را روی همه مجموعه‌های محتمل ممکن کسب کند به عنوان فرضیه برگزیده در دور t انتخاب میشود. با این شیوه، AdaBoost.M2 تضمین می‌کند که بهترین فرضیه ممیزی را در هر دور ارایه کند. الگوریتم 2. شبه کد AdaBoost.M2 را نشان می‌دهد.
Given: x1,y1, …, (xm,ym) where xi ∈X, yi ∈Y to make uniform over all
incorrect labels
Output: Hypothesis Hfinalx=argmaxl∈Yt=iTαtl ϵ ht(x)
1 Initialize D1i,l= l ≠ yimk-12 for t=1 to T do
3 Train weak learner using pseudoloss defined by Dt4 Get weak hypothesis ht :X → 2Y5 Let ϵt= 12 i=1ml∈YDti,l . (yi ∉ htxi+ l ϵ ht(xi))
6 Let αt= 12 ln(1-ϵtϵt)7 Update Dt+1i,l= 1Zt . Dti,l exp(αt(yi ∉ htxi+ l ϵ ht(xi)))
where Zt is the normalization factor so that Dt+1 will sum to 1.
8 end
شبه کد مربوط به روش AdaBoost.M2همان‌طور که در الگوریتم 2 مشاهده می‌کنید، در هر دور از اجرای الگوریتم، برای هر جایگشت از مجموعه محتمل μt∈2Y، یک فرضیه ضعیف تولید میشود. هدف یادگیر، کمینه کردن شبه-زیان است که به این صورت تعریف میشود:
ϵt= 12 i=1ml∈YDti,l . (yi ∉ htxi+ l ϵ ht(xi))که معیار زیان، در دو صورت فرضیه را جریمه می‌کند؛ اول به خاطر شامل نشدن برچسب صحیح yi مربوط به نمونه xi که عضو مجموعه محتمل است یعنی زمانی که yi ∉ htxi، دوم برای هر برچسب اشتباه l≠yi که عضو مجموعه محتمل است یعنیl ϵhtxi . در این الگوریتم، مقدار αt مشابه AdaBoost محاسبه میشود. فرضیه نهایی، یک نمونه را بر اساس برچسبی که دارای بیشترین تعداد تکرار در مجموعه محتمل انتخاب شده توسط فرضیه های ضعیف است، دستهبندی می‌کند. با وجود اینکه AdaBoost.M2 نشان داده که از عملکرد بسیاری خوبی برخوردار است CITATION VGu99 \l 1065 \m Fre96 [29,36]، این الگوریتم معایبی نیز دارد. اولین مورد، زمان آموزش آن است. از خط 2 در الگوریتم 2، این نکته به راحتی قابل استنباط است که تعداد مجموعه‌های محتمل با افزایش تعداد برچسب‌های کلاس نمونه‌های آموزشی، به صورت نمایی افزایش می‌یابد. به گفته دیگر، جستجوی همه مجموعه‌های محتمل در حالتی که تعداد برچسب‌های کلاس موجود در دادههای آموزشی بیش از ده باشد (k > 10)، غیر ممکن است. مورد دوم، مشکل شدن پیادهسازی الگوریتم است که به علت لزوم تغییر در یادگیر‌های ضعیف و تعریف شبه-زیان به‌وجود می‌آید.
ایراد رایجی که به روشهای تفکیک نظیر OAO، OAA و ECOC، که ابتدا دستهبندیکنندهها را دو‌به‌دو جدا می‌کنند و سپس رای آنها را تلفیق می‌کنند، وارد میشود این است که چنین روش‌هایی بدون در نظر گرفتن ماهیت و ویژگی‌های داده این روال را اجرا می‌کنند CITATION Jon \l 1065 \m All01 \m RJi07 [3,27,32]. به علاوه، آلوین و همکاران CITATION All01 \l 1065 [27] و جین و زنگ CITATION RJi07 \l 1065 [32] به این نکته اشاره کردند که در روش ECOC، به علت به وجود آمدن مرزهای تصمیم چند وجهی، ممکن است یادگیری زیر مساله‌های دودویی مصنوعی ، سخت باشد شود. پیدا کردن ماتریس کدگذاری بهینه برای روش ECOC، یک مساله NP-hard است CITATION KCa02 \l 1033 [39]؛ البته روش‌هایی برای برطرف کردن این مشکل پیشنهاد شده است. از معروف‌ترین این روش‌ها، AdaBoost.OC CITATION Fre96 \l 1065 [36] و AdaBoost.ECC CITATION VGu99 \l 1065 [29] است که به خوبی روش ECOC را با یادگیری تقویتی تلفیق کرده‌اند CITATION Rok10 \l 1065 [31]. به علت رواج استفاده از این روش‌ها و تحقیقات متعددی که بر این روش‌ها جریان دارد CITATION YSu07 \l 1033 \m RJi07 \m Rok10 \m LiL[40,32,31,17]، این روش‌ها به عنوان روشهای پایه برای مقایسه در این پایان‌نامه مورد استفاده قرار گرفته‌اند.
روش AdaBoost.OCالگوریتمهای AdaBoost.OC و AdaBoost.ECC، قوانین روش ECOC را با یادگیری جمعی تقویتی ادغام کرده و به کمک این استراتژی، توانسته‌اند بر معایت روش AdaBoost.M2 فائق آیند. روشهای یادگیری تقویتی مبتنی بر ECOC، به طور تکرار شونده، ستون‌های ماتریس کدگذاری را تولید می‌کنند به طوری که اغتشاش میان کلاسها در هر دور اجرای الگوریتم تقویتی، کاهش یابد. الگوریتم 3. جزییات روش AdaBoost.OC را نشان می‌دهد. اثبات قمست‌های تئوری این روش را میتوان در CITATION Fre96 \l 1065 [36] یافت.
Given: x1,y1, …, (xm,ym) where xi ∈X, yi ∈Y to make uniform over
all incorrect labels
Output: Hypothesis Hfinalx=argmaxl∈Yt=iTαthtx= μtl1 Initialize D1i,l= l ≠ yimk-12 for t=1 to T do
3 Compute colouring μ :Y →{0,1}4 Let Ut= i=1ml∈YDti,l μtyi ≠ μtl
5 Let Di= 1Ut . l∈YDti,l μtyi ≠ μtl6 Train weak learner on examples x1,μ1y1, …, (xm,μtym) weighted according to Dt7 Get weak hypothesis ht :X →{0,1}8 Let htx={l ϵ Y : htx= μtl}9 Let ϵt= 12 i=1ml∈YDti,l . (yi ∉ htxi+ l ϵ ht(xi))10 Let αt= 12 ln(1-ϵtϵt)11 Update Dt+1i,l= 1Zt . Dti,l exp(αt(yi ∉ htxi+ l ϵ ht(xi)))
where Zt is the normalization factor so that Dt+1 will sum to 1.
12 end
شبه کد مربوط به روش AdaBoost.OCالگوریتم AdaBoost.OC، کار خود را با تولید یک تابع کد گذاری، که ارایه دهندگان روش به آن تابع رنگ‌آمیزی μ می گویند، آغاز می‌کند. تابع رنگ‌آمیزی، ستون‌های ماتریس کدگذاری را تولید و تمام برچسب کلاس‌های Y →{0,1} را نگاشت می‌کند. همانند AdaBoost.M2، این روش نیز توزیع اضافی D را در هر دور t به‌روز رسانی کرده و نگه می‌دارد. با اعمال تابع رنگ‌آمیزی μt بر توزیع D، Ut تولید میشود که میزان توانایی اصلاح خطای ماتریس ستونی μt را نشان می‌دهد. سپس μt، Ut وDt جهت محاسبه وزن توزیعDt ، با هم ترکیب میشوند. بعد از آن، دسته‌بندی‌کننده دوکلاسه ht بر توزیع جدیدDt آموزش داده میشود؛ این قسمت از الگوریتم، با روش AdaBoost.M2 که بر Dt آموزش داده میشود متفاوت است. در این مرحله، شبه خطای ϵt مشابه الگوریتم AdaBoost، برای محاسبه αt، تولید میشود. در آخر، توزیع D ، مشابه روش AdaBoost.M2، توسطαt به‌روز رسانی میشود. برچسب پیشنهادی فرضیه نهایی H برای نمونه x، همان برچسب ارایه شده توسط htx است که دارای بیشترین رای وزن دار می‌باشد.
روش AdaBoost.ECCالگوریتم AdaBoost.ECC، از بسیاری جهات شبیه AdaBoost.OC است. تفاوت اصلی این دو الگوریتم این است که، AdaBoost.ECC ارزشαt را بر اساس شبه خطا در هر دور از اجرای الگوریتم، محاسبه نمی‌کند؛ بلکه αt و βt را که به ترتیب نشان‌دهنده رای‌های مثبت و منفی فرضیه X →{1,-1} در مساله دوکلاسه است را در هر دور محاسبه می‌کند. بر اساس گفته ارایه دهندگان این روش CITATION VGu99 \l 1065 [29]، با این استراتژی، به طور ساده‌تری میتوان مساله چندکلاسه را به فرم دوکلاسه شکست. شبه کد این روش را الگوریتم4. مشاهده می‌کنید. در زمان دستهبندی، تابع gtx.μtl ارزش رای مربوط به برچسب کلاس l را به‌دست می‌دهد. خروجی فرضیه نهاییHx، برچسب کلاس y می‌باشد که بیشترین مقدار را از فرضیه gtx کسب کرده است. ارایه دهندگان AdaBoost.ECC ادعا می‌کنند که این روش پیچیدگی محاسباتی کمتری نسبت به AdaBoost.OC دارد و نتایج دقیق‌تری نیز به دست می‌آورد.
Given: x1,y1, …, (xm,ym) where xi ∈X, yi ∈Y to make uniform over
all incorrect labels
Output: Hypothesis Hfinalx=argmaxl∈Yt=iTgt(x)μtl1 Initialize D1i,l= l ≠ yimk-12 for t=1 to T do
3 Compute colouring μ :Y →{-1,1}4 Let Ut= i=1ml∈YDti,l μtyi ≠ μtl
5 Let Di= 1Ut . l∈YDti,l μtyi ≠ μtl6 Train weak learner on examples x1,μ1y1, …, (xm,μtym) weighted according to Dt7 Get weak hypothesis ht :X →{-1,1}8 Compute the weight of positive and negative votes αt and βtrespectively
9 Define: gtx=αt if htx=1 βt if htx=-110 Update Dt+1i,l= 1Zt . Dti,lexp(gtxiμtl – gtxiμtyi. 12}
where Zt is the normalization factor so that Dt+1 will sum to 1.
11 end
شبه کد مربوط به روش AdaBoost.ECCروشهای جمعی سريالیک دسته‌بندی‌کننده جمعی غیر سريال مانند H، شامل T دسته‌بندی‌کننده ضعیف hi,…,T است. در فاز آموزش، اگر از روش تقویتی برای ایجاد گوناگونی استفاده شود، هر دسته‌بندی‌کننده ضعیف همه دادههای آموزشی را می‌بیند. در زمان دستهبندی، دسته‌بندی‌کننده‌های ضعیف به صورت خطی با هم ترکیب میشوند و خروجی هر hi(x) برای محاسبه‌ی مرز تصمیم‌گیری Hx ضروری است؛ به این گروه از دسته‌بندی‌کننده‌های جمعی، دسته‌بندی‌کننده‌های تک‌لایه یا یکپارچه گفته می شود.
دسته‌بندی‌‌‌کننده‌ی سريالبر خلاف دسته‌بندی‌کننده‌های تک‌لایه، دسته‌بندی‌کننده‌های سريال، دارای بیشتر از یک لایه هستند و شامل Hi,…,L میشوند. هر لایه Hi، دارای T دسته‌بندی‌کننده ضعیف hi,j,…,T است. در فاز آموزش، دسته‌بندی‌کننده‌های hi,j نمونه‌های آموزشی یکسانی را نمی‌بینند. کل مجموعه دادههای منفی N متصور است؛ دسته‌بندی‌کننده‌های هر لایه i فقط بر روی زیرمجموعه‌ای از مجموعه N آموزش می‌بیند که Ni∈N؛ این در حالی است که مجموعه دادههای مثبت P بدون تغییر باقی می ماند. در ابتدا، Ni به صورت تصادفی انتخاب می شود؛ سپس دسته‌بندی‌کننده Hi نمونه‌هایی از Ni که درست دستهبندی شوند را با نمونه‌هایی از N، که اشتباه دستهبندی شده‌اند جایگزین می‌کند. در نتیجه، هر لایه i یاد می‌گیرد که نمونه‌های سخت‌تر را تمیز دهد، همچنین مرز تصمیم‌گیری از حالت کلان به درجات جزئی و دقیق‌تر پالایش می‌یابد.
همچنین، هر لایه i نماینده یک دور از دستهبندی تقویتی مستقل است؛ به این دلیل که در هر لایه، توزیع وزن دادههای آموزشی از اول مقدار‌دهی میشود. خطاهای آموزشی هدف برای هر لایه به گونه‌ای تعیین میشود که تنها 50% از دادههای منفی موجود در Ni یادگیری شوند. اما معمولا، اهداف مربوط به نرخ موفقیت بسیار نزدیک به 100% انتخاب میشود.
دستیابی به نرخ موفقیت هدف، در لایه‌های آخر که دادهها سخت‌تر میشوند، به یک معضل تبدیل میشود. برای حل این مشکل، یک آستانه مصنوعی یا بایاس θi برای هر لایه تعریف و تنظیم میشود. این آستانه، حاشیه اعتبار را کاهش می‌دهد که این امر باعث میشود، تعداد بیشتری از نمونه‌های مثبت مورد پذیرش قرار گیرند و دستیابی به هدف میسر شود. مشکلی که استفاده از این روش به وجود می‌آورد این است که تعداد بیشتری نمونه مثبت غلط نیز به وجود می‌آیند؛ بنابر این، پس از آموزش هر hi,j، بایستی آستانه با یک روش غیر عمومی دستکاری شود تا نرخ مثبت غلط مورد نظر نیز حاصل شود.
نرخ مثبت غلط و نرخ مثبت درست نهایی حاصل از کل دسته‌بندی‌کننده، بر پایه نرخ های تولید شده توسط هر لایه Hi خواهد بود CITATION RVe08 \l 1033 [41]. الگوریتم 5. جزییات روش سريال ویولا و جونز را بیان می‌کند و شکل(2-1) نیز به صورت شماتیک این ساختار را نشان می‌دهد.
Given: P, N, Ni denote sets of positive and two negative datasets respectively,
where Ni is the negative set used on layer i and Ni ⊂ N .
≺fi, di≻ denote the pair of false positive and hit rates respectively
for a given layer i Output: Cascade classifier H() comprised of Hi,…,L layers, each consisting of hi,j,…,T
weak classifiers and a layer threshold θi.
1 H= InitializeCascadeClassifier()
2 for each layer i to L do
3 Ni= Bootstap(N, H)
4 ≺P, Ni≻ = InitializeWeights()
5 j=0
6 repeat
7 hi,j = WeakLearn(P, Ni)
8 ≺P, Ni≻ = ReweightSamples(hi,j)
9 θi = FindBestThreshold()
10 ≺fi, di≻ = Validate(P, Ni)
11 j=j+112 until j >T or LayerTargetSatisfied(fi, di) ;
13 Hi= ≺hi, θi≻14 end
ساختار سريال Viola-Jones
Layer 1
Layer 2
Layer 3
Layer 4
