یادگیری افزایشی(incremental learning)

یک الگوریتم یادگیری افزایشی یک توالی از مدل‌ها h1, h2, ..., ht که از داده‌های آموزشی s1, s2, , ...., stتولید می‌کند. به طوری که مدل hi به مدل hi-1 و همچنین p نمونه آخر s یعنی (si-p,si-p+1, ..., si) وابسته است.

یادگیری افزایشی که اخیراً بسیار مورد توجه قرار گرفته به خصوص در کلان داده‌ها و یادگیری جریان (data stream) با فرضیات سنتی یعنی در دسترس بودن کل داده آموزشی در تناقض است. روش‌های یادگیری ماشین، تمام داده جمع آوری شده را استفاده می‌کنند تا اطلاعات مرتبط را از مدل استخراج کنند و یا با استفاده از این مدل بتوانند پیش بینی انجام دهند. اما رویکردهای یادگیری ماشین دسته‌ای (batch) کلاسیک قادر نیستند تا حجم معینی از داده را که در زمانی خاص در دسترس قرار می‌گیرند را پردازش کنند بنابراین حجمی از داده‌های پردازش نشده در دسترس خواهند بود و باید مدل مرتباً از نو ساخته شود. بنابراین این یک روند زمانبری خواهد بود و باعث می‌شود که مدل از رده خارج شود.

زمانی تمام داده‌ها در دسترس قرار نمی‌گیرند که یا داده‌ها آنلاین تولید می‌شوند (یادگیری آنلاین) مانند پیش بینی داده‌های بورس، و یا حجم بسیار زیادی از داده در اختیار داریم و نمی‌توانیم در حافظه اصلی (RAM) سیستم قرار دهیم مانند آنچه که مربوط به کلان داده‌هاست (big data). بنابراین در هر برهه‌ای از زمان داده‌های متفاوتی در دست داریم.

برای غلبه بر این موضوع یادگیری افزایشی مطرح شد که توالی‌ای از داده‌ها در چارچوب جریانی از داده مورد نیاز است (یادگیری جریان). بدین صورت نه تنها اطلاعات جدید به منظور به روز کردن مدل‌ها در هر زمان استفاده می‌شود که هزینه‌های ذخیره و نگهداری داده‌ها نیز کاهش می‌یابد.

یادگیری افزایشی با چندین چالش روبروست:

1- مدل به تدریج تطبیق یابد. یعنی آنکه hi قابلیت این را داشته باشد که از hi-1 ساخته شود.

2- دانش کسب شده قبلی باید ذخیره شود بدون آنکه فراموشی حاد منجر شود. یعنی آنکه اطلاعات استخراج شده از داده های قبل از si-p یعنی اطلاعات موجود در (s0, s1, ..., si-p-1) که در مدل hi-1 موجود هستند از بین نروند.

3- تنها یک تعداد محدودی از نمونه‌ها (p) قابل دسترسی است.

همچنین این را هم باید در نظر گرفت که هر زمان که داده جدیدی وارد می‌شود ممکن است کلاس جدیدی را هم تشکیل دهد.

به منظور ارزیابی مدل افزایشی دو رویکرد می‌توان در نظر گرفت:

1- چارچوب برون خطی (off-line)

2- چارچوب برخط (on-line)

به طور کلی در یک رویکردآفلاین مدل h بسته به مجموعه آموزشی Dtrain تولید می‌شود. و در فاز آزمایش نیز بر اساس مجموعه دیگری Dtest مدل ارزیابی می‌شود . این روش در شکل یک قابل مشاهده است.

اما در الگوریتم افزایشی این چارچوب، به جای آنکه همه داده در یک زمان برای آموزش در نظر گرفته شود، آن با یک ترتیب از پیش تعیین شده‌ای پردازش می‌شود و بنابراین جفت توالی‌های(x2,y2),(x1,y1),...,(xj,yj) توالی‌ای از مدل‌ها h1,h2, ..., hj می‌سازد (شکل 2). پس مدل hi برابر است با :

و همچنین به منظور ارزیابی، دقت برابر است با:

یک چارچوب آنلاین دیگر در شکل 3 نمایش داده شده است. یک جفت از توالی‌ها یکی پس از دیگری می‌رسند و در هر زمان t، هدف آن است که برچسب yt به ازای ورودی xt مطابقت کند. پیش بینی y_hat در زمان t بر اساس مدل یادگرفته شده قبلی یعنی ht-1 انجام می‌گیرد و بعد از آن تابع هزینه محاسبه می‌گردد. دقت آنلاین با رابطه زیر به دست می‌آید:

برای مقایسه مدل‌های آنلاین ، اگر هر دو مدل دقت آفلاین برابری داشته باشند، مدلی که دقت آنلاین بزرگتری داشته باشد، به طور متوسط زودتر از مدل دیگر همگرا می‌شود.

برای به روز رسانی مدل‌ها در حالت افزایشی لازم است hyper-parameter را با مدل تطبیق دهیم. برای مثال در روش‌های بردارهای پشتیبان، تابع کرنل، واریانس تابع RBF و در روش گرادیان نزولی تابع هزینه و نرخ آموزش به عنوان hyper-parameter توصیف می‌شود. اما چالش‌هایی که مطرح است این است که

1- در هر مرحله به روز رسانی چه مقدار تطبیق لازم است؟

2- چه مقدار داده از قبل و الان برای به روز رسانی لازم است؟

3- آیا این روش به روز رسانی در برابر اغتشاش موجود در برچسب گذاری مقاوم است؟

بنابراین پیچیدگی مدل‌ها به میزان و نوع همین پارامترها بستگی دارد. برای مثال یک انتخاب نامناسب از واریانس می‌تواند تعداد بردارهای پشتیبان را در روش ماشین بردار پشتیبان افزایش دهد. علاوه بر دقت و پیچیدگی، سرعت همگرایی نیز از عوامل موثر در انتخاب پارامتر مدل است. برای مثال تعداد درختان در روش ORF در سرعت همگرایی تأثیر می‌گذارد.

الگوریتم‌های افزایشی و آنلاین زیادی تا به حال انتشار یافته‌اند. مدل‌های بیزی، الگوریتم‌های بردارهای پشتیبان افزایشی، کاهش شیب تصادفی (sgd) افزایشی، مدل‌های مبتنی بر نمونه مانند جنگل تصادفی آنلاین، و یا الگوریتم‌های دیپ لرنینگ افزایشی که در بسیاری از مقاله‌ها به آن‌ها پرداخته شده است. اما در این مجال الگوریتم‌ بردارهای پشتیبان را مرور می‌کنیم.

ماشین‌های بردار پشتیبان تابع هزینه زیر را در فضای ویژگی کمینه می‌سازند:

با اضافه شدن نمونه جدید، مرز تصمیم نیز لازم است تا به روز شود. از آنجایی که نمونه‌ها در یادگیری افزایشی یکی پس از دیگری وارد می‌شوند یک راه حل آن است که مرز تصمیم بزرگ انتخاب شود. اما بزرگ بودن مرز تصمیم باعث می‌شود که به تعداد بردارهای پشتیبان افزوده شود و این مطلوب نیست. اما یک راه حل (LASVM) آن است که در هر تکرار یک مرحله حذف بردارهای پشتیبان منسوخ شده را نیز داشته باشیم.

یک راه حل دیگر که در SVMها بیشتر استفاده می‌شود، ماشین بردار پشتیبان افزایشی (ISVM) است و این الگوریتم بدین صورت استفاده می‌شود که داده‌ها به چندین بخش تقسیم می‌شود و در هر مرحله داده آموزشی جدید با بردارهای پشتیبان قبلی مجموعه داده جاری را می‌سازد و بعد از الگوریتم بردار پشتیبان بر روی آن اعمال می‌شود.