الگوریتم های تکراری و وردشی - نیم‌سال دوم 1400

هدف این درس آشنایی با مبانی نظری الگوریتم ­های تکراری و وردشی است که بر مبنای اصل وردشی گیبز و روش تکرار انتروپی نسبی حاصل می­شوند و در نهایت انواع الگوریتم­های از جنس Expectation-Maximization یا انواع الگوریتم­های از جنس Belief Propagation را نتیجه می­دهند. بخش اول درس به توضیح مفاهیم مرتبط با انتروپی نسبی و نقش آن در تمرکز اندازه و Large Deviation و دوگانی آن با تابع پارش لگاریتمی به همراه قضیه Donsker-Varadhan و تبیین دوگانی مسایل Maximum Entropy و Maximum Likelihood اختصاص دارد و استخراج الگوریتم BP از تقریب Bethe و همچنین قضیه اساسی Csiszar برای همگرایی روش تکرار روی انتروپی نسبی، و نظریه mean field از قسمت­های اصلی بخش اول است. بخش دوم درس به کاربردهای جدی این الگوریتم­ها اختصاص دارد که مدلهای مخلوط (Mixture) و HMM و از مثال­ های اصلی درس هستند و استاد با توجه به سلیقه و کلاس درس میتواند مباحث زیر را نیز مورد بحث قرار دهد: نمایش Loop Series و روش تقریب ناحیه­ای Bethe در قسمت نظری و فیلترهای کالمن، کاربردها در یادگیری تقویتی، کاربردها در دیکدینگ و کدهای LDPC، مدل­های Ising و بحث انتقال فاز.

The main objective of this course is to present the variational paradigm of algorithm design within the context of Gibbs variational principle. The main theme of the course is to present the necessary theoretical and practical background for the design and analysis of variational and iterative algorithms of maximum entropy or expectation-maximization type. The first part of the course is dedicated to the necessary background from geometric information theory, statistical physics, and Bayesian statistics. It is expected that the duality between maximum entropy and maximum likelihood using Legendre-Fenchel transform within the context of large-deviation and Donsker-Varadhan theory is discussed. The belief-propagation (i.e. cavity) iterative setup should be discussed in relation to Bethe approximation and different aspects of similar algorithms as max-sum or other variants. Also, the necessary theoretical background in relation to convergence properties of iterative expectation-maximization is presented along with an introduction to mean-field theory. The second part of the course is dedicated to some important examples and their analysis. Mixture and hidden Markov models as well as the Ising models and their variants are discussed in detail as the two most important setups. The concept of phase transition is also discussed in relation to these general examples. Selected applications in combinatorial optimization, coding theory, physics, or filtering may be considered based on the choice of the instructor.

[1] M. Mezard and A. Montanari, Information, Physics, and Computation, Oxford University Press 2009. 1

[2] C. L. Byrne, Iterative Optimization in Inverse Problems, CRC Press, Taylor & Francis Group, 2014. 2

[3] I. Csiszar and P. C. Shields, Information Theory and Statistics: a tutorial, Foundation and Trends in Communications and Information Theory, Vol 1, 2004. 3

[4] M. J. Wainwright and M. I. Jordan, Graphical Models, Exponential Families, and Variational Inference, Foundation and Trends in Machine Learning, Vol 1, 2008. 4

[5] C. M. Bishop, Pattern Recognition and Machine Learning, Springer 2006. 5

این درس به صورت آنلاین در اتاق مجازی https://vc.sharif.edu/ch/daneshgar تشکیل خواهد شد.

• حضور و مشارکت فعال در کلاس درس
• در طول نیمسال تحصیلی تمرین­هایی برای حل مشخص می­شوند که تحویل گرفته خواهند شد
• یک پروژه نهایی برای هر دانشجو تعیین می­شود که در پایان نیمسال تحویل گرفته خواهد شد
• آزمون میان ترم (تاثیر: حدود 40 درصد)
• آزمون پایان ترم (تاثیر: حدود 60 درصد)
• اصولا همه آزمون­های اصلی درس تجمعی هستند و محتوی آزمون از کل مطالبی که از ابتدای ترم تدریس شده باشند تا جایی که در اطلاعیه آزمون ذکر می­شود، خواهد بود.
• نمره نهایی دانشجو در این درس بر اساس تمامی فعالیت­های فوق­الذکر تعیین می­شود و همه میزان تاثیر­های اعلامی تخمینی و صرفا جهت اطلاع از کلیات روش ارزیابی است. به دانشجویان عزیز توصیه می­شود که از ابتدای شروع کلاس در فراگیری مطالب جدی باشند و تا انتهای نیمسال و آزمون نهایی از هر نوع تلاش برای جبران عقب ­افتادگی احتمالی فروگذاری نکنند.