Лектор: Михаил Викторович Чертков (LANL)
Аннотация:
За последние 10-15 лет статистическая теория информации и теория вычислений, призванные решить такие проблемы, как построение эффективных схем декодирования в коммуникационных системах повыщенной емкости или анализ конфигураций в большой системе дискретных переменных с запретами, претерпели революцию, связанную с внедрением новых идей из теории вычислительной сложности (complexity theory), а также вследствие разработки новых статистических алгоритмов. Статистическая физика, задачей которой является установление закономерностей в поведение систем с большим количеством компонент (частиц), сыграла определяющую роль в этом развитии.
Мини-курс, состоящий из пяти лекций, задуман как введение в эту новую дисциплину, которую можно назвать "физика и алгоритмы". Курс предполагает обсуждение следующих тем (в основном базирующихся на оригинальных работах лектора).
Программа:
Лекция 1. Статистическая реконструкция (Statistical Inference, Data Restoration), комбинаторная оптимизация (Combinatorial Optimization), подсчет конфигураций (Counting/Enumeration). Вычислительно-легкие задачи (наикрайчайщий путь, динамическое программирование, иерархические вычисления на "деревьях") и вычислительно-сложные задачи (K-SAT, спиновые стекла, декодирование графических кодов коррекций ошибок).
Лекция 2. Графовые модели. Основное состояние и статистические суммы. Приближение Бете-Пайерлса, Belief Propagation (BP), теория среднего поля, свободная энергия Бете.
Лекция 3. BP и петлевые вычисления (Loop Calculus). Бинарные модели. Графовые и вариационные формулировки. Само-избегаюшие (self-avoiding) деревья (Weitz method). Петлевые Башни (Loop Tower) = Петлевые разложениы для моделей с q-ичным алфавитом.
Лекция 4. Восстановление основного состояния и задача подсчета количества конфигураций на планарных графах. Модель Изинга. Модель димеров. Метод Фишера-Кастеляна-Бараоны (Fisher, Kastelyan, Barahona). Петлевые разложения на графах, вложенных в плоскость (планарных) и в двумерные поверхности. Пфаффиан и грассмановы интегралы (интегралы Березина).
Лекция 5. Гауссовы модели. Петлевые разложения для определителей и перманентов. Пример синтеза: практическое использование BP для отслеживания частиц в турбулентных течениях.
Продолжительность лекций два академических часа (около 1 ч. 30 м.) каждая.
Время и место:
Лекции 1, 2: среда 23 ноября, 10:30-13:30.
Лекция 3: четверг 24 ноября, 15:00-16:30.
Лекции 4, 5: четверг 1 декабря, 10:30-13:30.
Ул. Льва Толстого, 16 (метро Парк культуры-радиальная).
Просьба приходить не менее чем за 15 мин до начала лекций!
Литература:
1. Loop Calculus in Statistical Physics and Information Science, Phys. Rev. E 73 (2006) 065102®; cond-mat/0601487, co-author: Vladimir Chernyak.
2. Loop series for discrete statistical models on graphs, cond-mat/0603189, JSTAT/2006/P06009, co-author: Vladimir Chernyak.
3. Loop Calculus and Belief Propagation for q-ary Alphabet: Loop Tower, Proceedings of ISIT 2007, June 2007, Nice, cs.IT/0701086, co-author: Vladimir Chernyak.
4. Exactness of Belief Propagation for Some Graphical Models with Loops, submitted to JSTAT, http://arxiv.org/abs/0801.0341
5. Belief Propagation and Loop Series on Planar Graphs, JSTAT/2008/P05003, http://arxiv.org/abs/0802.3950, co-authors: V. Chernyak, R. Teodorescu.
6. Belief Propagation and Beyond for Particle Tracking, submitted to Proceeding of NIPS 2008, arXiv: 0806.1199, co-authors: L. Kroc, M. Vergassola
7. Fermions and Loops on Graphs. I. Loop Calculus for Determinant, preprint Aug 2008, http://arxiv.org/abs/0809.3479, co-author: V. Chernyak.
8. Fermions and Loops on Graphs. II. Monomer-Dimer Model as Series of Determinants, preprint Aug 2008, http://arxiv.org/abs/0809.3481, co-author: V. Chernyak.