این درس را مشترکا با دکتر علیشاهی ارائه می‌کنیم. قرار است در این درس ابتدا کمی بهینه‌سازی مقدماتی درس بدهیم، کمی برنامه‌ریزی خطی و کمی بهینه‌سازی محدب. که احتمالا حدود ۳ هفته این طول بکشد. بعد مقداری بهینه‌سازی برخط، بعد هم کمی یادگیری، بعد هم کمی یادگیری برخط و بعد هم کمی تلاش می‌کنیم چند مساله حل کنیم با این روش‌ها. دو سه کتاب نامزد کتاب درس شدن هستند.
- Introduction to Online Optimization که جزوه‌های درس آقای Bubeck است در سال ۲۰۱۱.
- Introduction to Online Convex Optimization کتاب آقای Hazan.
- Online Learning and Online Convex Optimization.
مباحث گفته شده در کتاب‌های بالا هستند. می‌توانید نگاه کنید و پیشاپیش از درس لذت ببرید. امیدوارم در ترم آینده بیشتر من این درس را درس بدهم و دکتر علیشاهی بیشتر شنونده باشند.
طبیعتا درس کمی طعم ریاضی خواهد داشت و کم‌تر طعم الگوریتمی. از درس بهینه‌سازی محدب کم‌تر و از درس‌های ارشدی که معمولا من درس می‌دهم بیشتر ریاضی‌گونه خواهد بود.
به عنوان پیش‌نیاز الگوریتم و ریاضی ۲ که لازم هستند. دانستن آمار موجب می‌شود مثال‌ها را خیلی بهتر متوجه شوید.
توصیف درس در قالب فایل پی‌دی‌اف در این فایل آمده است. به نظر می‌آید از کتاب آقای بوبک در این درس استفاده نکنیم.
برخی منابع مرتبط
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems S. Bubeck and N. Cesa-Bianchi
- The Multiplicative Weights Update Method: a Meta-Algorithm and Applications S. Arora, E. Hazan and S. Kale
- Statistical Learning and Sequential Prediction A. Rakhlin and K. Sridharan
- The convex optimization approach to regret minimization E. Hazan
- Bandit Algorithms Book
- Online and Adaptive Methods for Machine Learning
- The Multiplicative Weights Update Method: a Meta-Algorithm and Applications S. Arora, E. Hazan and S. Kale
- Statistical Learning and Sequential Prediction A. Rakhlin and K. Sridharan
- The convex optimization approach to regret minimization E. Hazan
- Introduction to Online Learning
- Machine Learning Theory
- Online Learning
- Prediction and Learning: It’s Only a Game
- Online Learning and Optimization
- The complexities of optimization
- کتاب‌چه‌ای برای درس Statistical Learning and Sequential Prediction
- مطالب یک درس Online Methods in Machine Learning
- شاید این از همه درس‌های قبلی بهتر باشد Online Prediction and Learning
- اما این منبع از همه بهتر است: Competitive analysis via convex optimization. اما ای‌کاش همه جزوه‌هایش موجود بود.
- مقاله‌ای جمع‌بندی در مورد کارهای انجام شده در یادگیری برخط Online Learning: A Comprehensive Survey
- درس مقدمه‌ای بر یادگیری برخط
- یک کتاب جدیدتر: Introduction to Multi-Armed Bandits
پس‌نوشت (۲۰ شهریور)
پس از مذاکرات طولانی با دکتر علیشاهی، قرار شد ایشان ابتدای درس را درس بدهند. احتمالا ابتدای درس را از روی کتاب آقای هیزن درس می‌دهند. هنوز نمی‌دانیم این قسمت چقدر طول می‌کشد. احتمالا خیلی طول نخواهد کشید، یک چیزی حدود یک و نیم ماه. بعدش هم احتمالا جنبه‌های یادگیری ماشین را بیشتر مطرح کنیم. مثلا یک مقاله هست به نام Online Learning: Beyond Regret که شاید از روی مقاله و مقاله‌های پیش از آن درس را ادامه بدهیم.
پروژه درس
درس آقای لوو چند نوع پروژه دارد. یکی از آن انواع را برای پروژه درس انتخاب کردیم. در این پروژه چند الگوریتم یادگیری برخط را برروی یک سری داده اجرا می‌کنیم. فعلا داده‌های انتخاب شده داده مربوط به سرطان روده بزرگ با مشخصات زیر است:
Source: [AU99a]
Preprocessing: Instance-wise normalization to mean zero and variance one. Then feature-wise normalization to mean zero and variance one. [SKS03a]
# of classes: 2
# of data: 62
# of features: 2,000
Files: colon-cancer.bz2
یک مجموعه داده: UCI و یک مجموعه داده دیگر.
در داده بالا، باید اولین عدد را که یک یا منهای یک است بر اساس ستون‌های دیگر پیش‌بینی کنید. عدد ابتدایی در مورد سرطانی بودن است و اعداد ستون‌های دیگر میزان بیان ژن را مشخص می‌کند.
شما باید فرض کنید که داده‌ها یکی یکی می‌آیند. برای هرکدام شما باید هزینه انتخاب خود را لحاظ کنید و پارامترهای الگوریتم را به‌روز کرده و منتظر داده بعدی باشید. در نهایت میزان حسرت الگوریتم شما خوبی الگوریتمتان را می رساند.
الگوریتم اول برای آزمایش، الگوریتم مشاوران است. در این الگوریتم فرض کنید هر کدام از مشاوران یک ژن را انتخاب می‌کنند و شما می‌خواهید با الگوریتم هدج روشی پیشه کنید که از بهترین مشاوران خیلی بدتر نباشید.
الگوریتم دوم، الگوریتم Squint است.
در الگوریتم‌های بالا سعی کنید حساسیت الگوریتم خود را به ترتیب ورودی‌ها محاسبه کنید. همچنین سعی کنید پارامترهای اولیه را تغییر دهید و کارآیی الگوریتم خود را با این روش محاسبه کنید.
آزمون‌ها
- آزمون پایان‌ترم
سوال ۶ از آزمون پایان‌ترم براساس قسمت ابتدایی از جلسه ۱۱ از درس آقای لوو طراحی شده. می‌توانید راه حل آن را اینجا بیابید.