قدرت یادگیری ضعیف
۱. مقدمه
من تصمیم گرفتم مجموعه پست‌های بعدی خود را در مورد الگوریتم‌های تقویتی[1] شامل AdaBoost (تقویت تطبیقی) | افزایش گرادیان | XGBoost (تقویت گرادیان فوق العاده) داشته باشم. نیازی به ذکر نیست که چندین وبلاگ عالی، ویدیوهای یوتیوب و کتاب‌های درسی در این زمینه وجود دارد. با این حال، این یادداشت‌ها برای تقویت درک من در مورد خانواده الگوریتم‌های تقویت‌کننده هستند - بسیار خوشحالم اگر این محتوا برای دیگر علاقه‌مندان به علم داده در سراسر جهان مفید باشد.
بگذارید از ریشه شروع کنیم!
۲. تقویت - زمینه و فلسفه
یادگیرندگان قوی در مقابل یادگیرندگان ضعیف[2]
مسائل پیچیده در حوزه‌های هوش‌مصنوعی (AI) ممکن است با استفاده از «یادگیرندگان قوی» به عنوان مدل‌های شبکه عصبی حل شوند. با این حال، مدل‌هایی مانند DNNها به (الف) پارامترهای یادگیری بیشتری نیاز دارند - بسته به اندازه شبکه (ب) داده‌های بیشتری برای یادگیری خوب به منظور پیش‌بینی تعمیمی‌تر نیاز دارند (ج) نیاز سخت‌افزاری بالا دارند. بدون شک حل چنین مسائلی مسیری است که ما به ویژه در حوزه تحقیقات یادگیری عمیق در حال حرکت هستیم – با این حال، موارد متعددی وجود دارد که در آنها با محدودیت‌هایی مواجه می‌شویم – محدودیت‌هایی از نظر داده‌های موجود برای آموزش. یک مدل، محدودیت‌ها از نظر سخت‌افزار موجود و غیره. در چنین مواردی است که "یادگیرندگان ضعیف" به نجات ما می‌آیند!
اجازه دهید اکنون چکیده و مقدمه مقاله رابرت ای شاپیر با عنوان «قدرت یادگیری ضعیف» را مرور کنیم - تاریخ این مقاله به سال 1990 برمی‌گردد (!) اما نکته اولیه مقاله حتی امروز بسیار مرتبط است.
A concept class is learnable (or, strongly learnable) if given access to a source of examples of the unknown concept, the learner with high probability is able to output a hypothesis that is correct but on all but on an arbitrary small fraction of the instances. A concept/class is weakly learnable if the learner can produce a hypothesis that performs only slightly better than random guessing
رابرت ای شاپیر در این مقاله بیان می‌کند: «یک کلاس مفهومی قابل یادگیری است (یا به شدت قابل یادگیری است) اگر به منبعی از مثال‌های مفهوم مجهول دسترسی پیدا کند، یادگیرنده با احتمال بالا می‌تواند فرضیه‌ای را ارائه دهد که درست است اما در همه موارد به جز در همه موارد. کسری دلخواه کوچک از نمونه‌ها. اگر یادگیرنده بتواند فرضیه‌ای ارائه دهد که فقط کمی بهتر از حدس زدن تصادفی باشد، یک مفهوم/کلاس ضعیف قابل یادگیری است.
فرضیه ~ معادله با وزن / پارامترهای آن
برداشت مقاله:
در این مقاله نشان داده شده است که 2 مفهوم یادگیری پذیری معادل هستند. به عبارت دیگر، اگر یک یادگیرنده قوی بتواند مسئله‌ای را حل کند، یادگیرنده یک هفته نیز باید آن را حل کند. مفهوم یادگیری پذیری ضعیف توسط کرنز و والیانت (1988، 1989) مطرح شد که این سؤال را باز گذاشتند که آیا مفاهیم یادگیری قوی و ضعیف معادل هستند. این سوال به عنوان "مکانیسم تقویت فرضیه[3]" نامیده شد زیرا نشان دادن مفاهیم معادل نیاز به روشی برای افزایش دقت پایین یک فرضیه یادگیری ضعیف دارد.
در "مکانیسم تقویت فرضیه" به جای ساخت یک فرضیه، بیش از یک فرضیه می‌سازیم و همه آنها را پیش‌بینی می‌کنیم و سپس با اکثریت آرا پیش می‌روند. بنابراین، ترکیب این فرضیه منجر به پیش‌بینی قوی‌تر شد که به بهبود دقت کمک کرد و در نتیجه مفهوم «یادگیری ضعیف» معادل یادگیری قوی شد.
۳. الگوریتم های مبتنی بر مفهوم تقویت فرضیه
۳.۱ جنگل‌های تصادفی
در مطالب بالا، من در مورد مفهوم یادگیری قوی و ضعیف و اینکه چگونه این مفاهیم الهام بخش کشف "مکانیسم تقویت فرضیه" هستند که اساساً به معنای ترکیب بیش از یک فرضیه برای افزایش دقت یک فرضیه ضعیف برای حل یک مسئله یادگیری است.
اجازه دهید اکنون و در بخش‌های بعدی به برخی از این الگوریتم‌ها با جزئیات نگاه کنیم: جنگل‌های تصادفی، تقویت تطبیقی (AdaBoost)، تقویت گرادیان و تقویت XG (تقویت گرادیان فوق‌العاده).
درختان تصمیم و جنگل‌های تصادفی:
درختان تصمیم بلوک‌های ساختمان جنگل‌های تصادفی هستند – یک منبع خوب برای جزئیات مربوط به درختان تصمیم، سخنرانی MIT توسط تامارا برودریک (https://youtu.be/ZOiBe-nrmc4) است.
از آنجایی که درخت‌های تصمیم به داده‌ها حساس هستند، الگوریتم جنگل‌های تصادفی به‌طور تصادفی از مجموعه داده‌ها نمونه‌برداری می‌کند و از هر یک از نمونه‌ها (هر نمونه معمولاً با اندازه N یکسان است) برای آموزش هر درخت تصمیم استفاده می‌کند.
یکی دیگر از موارد بسیار مهم برای برجسته کردن تفاوت بین جنگل‌های تصادفی و درخت‌های تصمیم این است که - در یک الگوریتم درخت تصمیم منظم، ترتیب ویژگی‌های انتخاب شده در طول هر تقسیم درخت بر اساس حداقل آنتروپی است (اصطلاح "آنتروپی" نشان دهنده اندازه‌گیری تصادفی بودن در پیش‌بینی است) یعنی: ابتدا آن ویژگی‌هایی را انتخاب می‌کنیم که منجر به حداکثر "درآمد اطلاعات[4]" می‌شود. برخلاف این، در جنگل‌های تصادفی، ویژگی‌های هر درخت را به‌طور تصادفی انتخاب می‌کنیم.
بنابراین، در جنگل‌های تصادفی، درختان بر روی نمونه‌های تصادفی مجموعه داده‌ها و همچنین با استفاده از توزیع تصادفی ویژگی‌ها در بین درختان آموزش داده می‌شوند و سپس کلاسی که اکثریت رای در بین همه درختان دارد برای پیش‌بینی استفاده می‌شود.
چرا تصادفی بودن در جنگل‌های تصادفی کمک می‌کند؟
توزیع تصادفی نمونه‌ها از مجموعه داده‌ها در میان درختان و همچنین توزیع تصادفی ویژگی‌ها در به دست آوردن دقت خوب قدرتمند است - هر چه تصادفی بودن بیشتر باشد، یعنی درختان بیشتر، اطمینان بیشتری در پیش‌بینی دارند.
این را می‌توان مشابه با تحلیل مونت کارلو در نظر گرفت. با در نظر گرفتن یک مثال، ما از یک تولید کننده اعداد تصادفی برای تولید یک عدد بین 0 تا 100 و شرط‌بندی روی عدد 0 تا 60 استفاده می‌کنیم. تعداد دفعاتی که بازی را انجام می‌دهید، امکان برنده شدن و انجام یک مونت بیشتر خواهد بود. -شبیه‌سازی کارلو در چنین سناریویی این را پیش‌بینی می‌کند - تعداد دفعاتی که با استفاده از مولد اعداد تصادفی برای تولید یک عدد بازی می‌کنید - بیشتر عدد خواهد بود. از بردها این وضعیت با تصادفی بودن در جنگل‌های تصادفی است - بیشتر درختان، توزیع تصادفی ویژگی‌ها و نمونه‌های مجموعه داده‌ها بیشتر خواهد بود و بنابراین اطمینان در پیش‌بینی بالاتر خواهد بود.
۳.۲ تقویت تطبیقی
از مطالب فوق به طور کلی می‌توان گفت که یادگیرندگان ضعیف را می‌توان برای پیش‌بینی قوی ترکیب کرد. اکنون به الگوریتم دیگری نگاه می کنیم - "تقویت تطبیقی" که همچنین مبتنی بر مفهوم ترکیب یادگیرندگان ضعیف است تا آنها معادل "یادگیرنده قوی" شوند.
در مورد جنگل‌های تصادفی، یادگیرنده ضعیف یک درخت تصمیم با اندازه کامل بود، و در بخش 3.1 در بالا ذکر شد که مجموعه داده‌ها را به‌طور تصادفی و ویژگی‌ها (به‌طور تصادفی) در بین درختان نمونه‌برداری می‌کنیم. هر درخت تصمیم‌گیری در تصمیم‌گیری نهایی حرف یکسانی دارد.
در تقویت تطبیقی ما این فرآیند را کارآمدتر می‌کنیم. در تقویت تطبیقی، مدل کلی به N درخت تصمیم تقسیم می‌شود (دقیقاً N مدل ضعیف - اجازه دهید در نظر بگیریم که یادگیرنده ضعیف درخت تصمیم است) - هر درخت تصمیم یک مهر تصمیم (شکل زیر را ببینید) با یک تقسیم است - N در اینجا به تعداد ویژگی‌ها اشاره می‌کند. بنابراین، ما برای هر ویژگی یک خرده تصمیم ایجاد می‌کنیم و اولین مهر تصمیمی خواهد بود که کمترین میزان تصادفی را دارد (Entropy / Gini Index).
به تمام نمونه‌های داده‌ها وزن داده می‌شود و برای شروع همه نمونه‌های داده به طور مساوی وزن می‌شوند. هنگامی که ما بر روی این نمونه‌های داده آموزش دیده‌ایم، سپس وزن‌های بالاتری را به نمونه‌هایی که به اشتباه دسته‌بندی شده‌اند اختصاص می‌دهیم. اکنون مهر تصمیم دوم (یا مدل ضعیف) بیشتر بر روی نمونه‌هایی تمرکز می‌کند که به اشتباه دسته‌بندی شده‌اند. وزن یا اهمیت فرضیه در هر نمونه از تمرین به روز می‌شود و دسته‌بندی نهایی برای تصمیم‌گیری قوی‌تر استفاده می‌شود.
همانطور که می‌توان تفسیر کرد (از پاراگراف‌های بالا و بخش جنگل‌های تصادفی)، در جنگل‌های تصادفی، می‌توان کارها را در یک ماشین چند پردازنده موازی کرد، زیرا هر درخت تصمیم مستقل از دیگری ساخته می‌شود - در Adapboost از موارد بالا واضح است. توضیح اینکه ترتیب مُهرها مهم است. خطایی که درخت اول (مُهر تصمیم‌گیری) ایجاد می‌کند بر وزن نمونه‌های تمرینی در مُهر دوم تأثیر می‌گذارد زیرا هر مُهر با در نظر گرفتن اشتباهات مُهر قبلی ایجاد می‌شود.
شکل: Decision Stump (منبع: Wikipedia)
۳.۳ افزایش گرادیان
در بخش‌های فوق بر مفهوم یادگیرندگان قوی و ضعیف تاکید شد و سپس الگوریتم‌هایی شامل مجموعه‌ای از یادگیرندگان ضعیف مانند جنگل‌های تصادفی مورد بحث قرار گرفت.
در واقع، تقویت تطبیقی مورد بحث در بخش ۳.۲ در بالا ممکن است به عنوان یک مورد خاص از "تقویت گرادیان" در نظر گرفته شود. در تقویت تطبیقی، وزن دادن به نقاط داده توسط یک منحنی نمایی انجام می‌شود، به این معنی که اگر یک نمونه آموزشی توسط یک یادگیرنده ضعیف دسته‌بندی شود، ما واقعاً آن را وزن می‌کنیم تا یادگیرنده ضعیف بعدی روی درست کردن آن تمرکز کند. وزن نقاط داده در AdaBoost در معادله ریاضی زیر نشان داده شده است:
خطای کل مجموع تمام وزن نمونه نقاط داده دسته‌بندی اشتباه است.
برخلاف موارد فوق (رویکرد محاسبه وزن نمونه‌های دسته‌بندی اشتباه) در Gradient Boosting، مدل وزن‌ها را از طریق گرادیان یاد می‌گیرد. گرادیان برای به حداقل رساندن تابع ضرر و "یادگیری" وزن‌ها استفاده می‌شود. در هر دور آموزش خطا (پیش‌بینی در مقابل حقیقت) محاسبه می‌شود و گرادیان با مشتق جزئی تابع ضرر محاسبه می‌شود. از آنجایی که در تقویت گرادیان، پیش‌بینی چندین مدل را با هم ترکیب می‌کنیم، گرادیان‌ها افزودنی هستند و از طریق فرآیند آموزش هر درخت به‌روزرسانی می‌شوند.
داشتن وزن‌های آموخته‌شده از طریق، انعطاف‌پذیری بسیار بیشتری نسبت به به‌روزرسانی وزن‌ها به‌طور تصاعدی مانند تقویت تطبیقی می‌دهد.
یکی از نکاتی که در افزایش گرادیان وجود دارد این است که فرآیند آموزش به دلیل محاسبه گرادیان کندتر می‌شود، به خصوص زمانی که داده‌های آموزشی بسیار زیاد است، و این بخش در XGBoost مراقبت می‌شود.
XGBoost: افزایش گرادیان فوق العاده
XGBoost تقویت کننده گرادیان است اما با برخی بهبود عملکردهاست. XGBoost داده‌های آموزشی را در قالب ستون پراکنده فشرده[5] (csc) ذخیره می‌کند و از گرادیان مرتبه دوم برای محاسبه تابع ضرر استفاده می‌کند و از Regularization L، L2 برای جلوگیری از برازش بیش از حد و تعمیم بهتر استفاده می‌کند. آموزش می‌تواند موازی/توزیع[6] در میان خوشه‌ها باشد.
به این ترتیب، XGBoost سنگ بنای یادگیری ماشین رقابتی بوده است، تکنیکی است که برای برنده شدن استفاده می‌شود و توسط برندگان توصیه می‌شود. به عنوان مثال، در اینجا چیزی است که برخی از برندگان مسابقه Kaggle گفته‌اند:
"به عنوان برنده تعداد فزاینده‌ای از مسابقات Kaggle، XGBoost دوباره به ما نشان داد که یک الگوریتم همه جانبه عالی است که ارزش داشتن در جعبه ابزار شما را دارد."
- مصاحبه برندگان داتو
"در صورت شک، از xgboost استفاده کنید."
- مصاحبه برندگان Avito
درباره فرمت csc: https://scipy-lectures.org/advanced/scipy_sparse/csc_matrix.html
