נושאים מתקדמים בתורת האינפורמציה – למידה וחיזוי אוניברסליים  

מרצה: פרופ מאיר פדר

 נקודות זכות: 2

דרישות קדם: תורת האינפורמציה1 . מומלץ (לא חובה) – תהליכים  אקראיים.

סילבוס:
חיזוי אוניברסלי של סדרות. המקרה הסטוכסטי. המקרה האידיוידואלי. קשר בין דחיסה לחיזוי. קידוד לפלס, קריצ'בסקי-טרופימוב, למפל-זיו, אלגוריתם Context Tree Weighting (CTW) , אלגוריתמי ה    Prediction by Partial Matching (PPM). חיזוי/החלטה סדרתית עם פונקציות מחיר כלליות – קשר לתורת המשחקים, איך ל"נצח את המומחה". עקרון ה Minimum Description Length (MDL), התער של Occam, סיבוכיות קולמוגורוב. חיזוי נתונים פיננסי ובעיית הפורטפוליו. חיזוי וקידוד סדרות מעל אלפבית גדול/לא ידוע. סינון אוניברסלי ובעיית ה De-Noising האוניברסלית. הכללה ללמידה סדרתית. תוצאות בלמידה אוניברסלית. תיאור חזית המחקר הנוכחית בנושאי חיזוי ולמידה.

Course title: Advanced Topics in Information Theory: Universal Prediction and Coding

Syllabus:

Universal prediction of sequences – the stochastic setting and the individual setting. Relation between source coding and prediction. Laplace and Kriechevski-Trofimov’s approach, Lempel-Ziv, Context Tree Weighting (CTW), Prediction by Partial Matching (PPM) algorithms. Prediction/sequential decision with general loss functions. Relation to game theory. “How to use expert advice”? The Minimum Description Length (MDL) principle, Occam’s Razor and Kolmogorov’s complexity. Financial prediction and the portfolio problem. Prediction and Coding with large/unknown alphabet. Universal filtering and universal “de-noising”. Extension to sequential learning problems. Results in universal learning. Open current problems.

References:

1. Research Papers. In particular – Merhav & Feder “Universal Prediction”, IEEE Transactions on Information Theory, October 2008.
2. Prediction, Learning, and Games, N. Cesa-Bianchi and G. Lugosi, Cambridge University Press, 2006.
3. Statistical Learning Theory and Sequential Prediction, A. Rakhlin and K. Sridharan, Lecture Notes University of Pennsylvania, 2013.

אופן קביעת הציון הסופי:

הציון הסופי יקבע על סמך עבודת גמר וסמינר בהתבסס על הנושאים הנלמדים בקורס.