Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Факультатив от кафедры МОУ ФУПМ МФТИ и ПреМоЛаб МФТИ "Предсказания, обучение, сложность"

Факультатив от кафедры МОУ ФУПМ МФТИ и ПреМоЛаб МФТИ.

 
В весеннем семестре по субботам в рамках Стохастического анализа в задачах планируется проводить факультатив, темы занятий которого, как правило, будут выбираться из предложенного ниже списка. По вопросам, касающимся этого факультатива, просьба писать на gasnikov@list.ru (прежде всего, для включения в список рассылки этого факультатива)
 

Предсказания, обучение, сложность

А.В. Гасников, Е.А. Крымова, Е.О. Черноусова, Н.О. Бузун, Н.К. Животовский
 

Часть I. Элементы статистической теории обучения

1.       Задача классификации. Байесовский классификатор. Принцип множителей Лагранжа (как теорема об отделимости) в функциональных пространствах (лемма Неймана-Пирсона).

2.       Теория обобщения, эпсилон -сети и  VC -размерность, эпсилон -энтропия (дельта-емкость) компакта и энтропийное доказательство Колмогоровым теоремы Витушкина о не возможности представления функций одного класса суперпозициями функций другого класса.

3.    Классификация с помощью пороговых решающих правил. Пороговая размерность. Покрытия и упаковки. Вероятностный метод в комбинаторике. Теорема Хауслера и др .

4.  Эмпирические процессы, Колмогоровский чейнинг, энтропийное неравенство Дадли, неравенства о концентрации меры: Чернова, Хеффдинга, Бернштейна, Эфрона-Стайна, МакДиармида, Хана (информационное), Буске, Талаграна. Энтропийный метод. Подходы Мертона, Бобкова.

5.       Средние по Радемахеру и другие меры емкости класса функций.

6.       Примеры. Метод опорных векторов.

7.       Оракульные неравенства (разреженность), агрегирование оценок, локальная Радемахеровская сложность, PAC -байесовские неравенства.

8.    Геометрическое толкование результатов о концентрации (Мильман, Громов и др.). Пример шара (сферы). Лемма Пуанкаре. Подход Леви. Кривизна Риччи многообразия, задача Бюффона, вероятностная интерпретация формулы Гаусса-Бонне. Изопериметрическое неравенство. Вывод закона распределения скоростей молекул газа Максвелла (термодинамический предельный переход, метод Лапласа).

9.       Случайная проекция и теорема Джонсона-Линденштраусса. Теорема Кашина. Теорема Клартага.

10.    Метод  LASSO L 1-оптимизация, элементы теория сжатия измерений,  RIP -свойство и изометричность (Доноха, Кэндис-Тао).

11.    Концентрация меры на Хэмминговском кубе, на группе перестановок. Упоминание некоторых результатов А.М. Вершика и др. о предельных формах (для группы перестановок и простых чисел).

 

Часть I I . Энтропия и информация

12.    Игра в 10 вопросов. Игра Улама и ее обобщения. Поиск фальшивой монетки. Задача Патриция. Задача Тода Эберта о шляпах. Цена информации. Энтропия Шеннона. Условная энтропия. Расстояние Кульбака-Лейблера. Информация.

13.    Неравенства Фано, Макмиллана (лемма Крафта). Коды Шеннона-Фано, Хаффмана. Теоремы Шеннона. Теорема Шеннона об идеальном шифре и информационные неравенства.

14.    Элементы теории марковских процессов. Эргодическая теорема для марковских цепей, как принцип сжимающих отображений в метрике Биркгофа. Энтропия марковской цепи.

15.    Кодирование текстов с учетом частотных закономерностей. Кодирование с ошибками. Теорема Вольфа-Слепяна.

16.    Каналы с помехами. Пропускная способность каналов с помехами. Геометрическая интерпретация.

17.    Граница Хэмминга, граница Эдгара Гилберта. Случайное кодирование. Игра Лжеца и дерандомизация.

18.    Вероятностный метод в комбинаторике – информационный ракурс (информационное доказательство локальной леммы Ловаса).

19.    Линейные коды, коды Хэмминга, Рида-Соломона.

20.    Коммуникационная сложность, хэширование, интерактивные доказательства.

21.    Условие детального баланса. Закон действующих масс. Парадокс Эренфестов. Энтропия как функция Ляпунова кинетической динамики, возникающей при скейлинге марковской динамики, и как функция, описывающая концентрацию стационарной меры марковской динамики. Скорость сходимости и дискретная кривизна Риччи. Изопериметрические неравенства Пуанкаре и Чигера.

22.    Пример  PageRank  и  Markov chain Monte Carlo.

23.    Эволюционные (популяционные) игры. Дарвиновский отбор и равновесие Нэша. Элементы  Discrete   choice theory .

24.    Кинетика социального неравенства, закон Ципфа-Парето-Мандельброта. Связь с предельными формами.

 

 

Часть  III . Универсальное прогнозирование. Элементы теории Колмогоровской сложности

25.    Универсальные предсказания. Калибруемость прогнозов. Алгоритм вычисления калибруемых прогнозов.

26.    Расстояние Кульбака-Лейблера, мартингальность и игра с казино.

27.    Сложность, случайность, непредсказуемость. Колмогоровская сложность.

28.    Сложность (случайность) и динамические системы с перемешиванием. Динамические системы с шумом. Хаотичность и устойчивость. Чувствительность к внешним возмущениям. Пример Бореля. Уравнение Лиувилля. Подход статистических ансамблей (слабой сходимости) Гиббса-Пуанкаре-Козлова-Веденяпина к обоснованию статистической механики. Скольжение по ансамблю В.И. Опойцева.

29.    Эргодическая теорема в теории динамических систем и в теории случайных процессов. Мера Синая-Боуэна-Рюэля. Примеры Вейля, Гаусса-Гильдена-Вимана-Кузьмина.

30.    Автоморфизмы Маркова, конструкция Улама, сдвиг Бернулли.

31.    Энтропия динамической системы, как инвариант. Теорема Орнстейна.

32.    Фракталы, метод ренорм-группы.

33.    Алгоритмические вопросы теории вероятностей.

 

 

Часть  IV . Онлайн оптимизация. Взвешивание экспертов. Предсказания и игры

34.    Discrete   choice   theory , алгоритмы следования за лидером (за возмущенным лидером). Мотивация метода зеркального спуска (МЗС) Немировского-Юдина. Метод двойственных усреднений Нестерова и его связь с МЗС. Функция зазора и прямо-двойственные методы.

35.    Онлайн оптимизация. Основные свойства МЗС (стохастическая онлайн постановка).

36.    МЗС и взвешивание экспертов (линейные потери, выпуклые потери, невыпуклые потери).

37.    МЗС и безградиентные методы. Задача ранжирования  web -страниц и безградиентный МЗС. Случайный покомпонентный спуск Нестерова в форме МЗС и его обобщения (Рихтарик и др.).

38.    МЗС и многорукие бандиты. Контекстуальные и марковские бандиты.

39.    Нижние информационные оценки для многоруких бандитов и для взвешивания экспертов. Вероятностный метод доказательства.

40.    МЗС и оракульные неравенства. Рассмотрение сильно выпуклого случая. Неравенства о концентрации без условий типа Крамера.

41.    МЗС и  Huge - scale   оптимизация. Пример  PageRank  (разреженный случай) .

42. Онлайн игры, состоятельность по Ханнану. Онлайн интерпретация равновесия Нэша. Повторяющиеся игры. Теорема Блекуэлла. Калибруемые предсказания.

43.    Агрегирующий алгоритм Вовка. Многомерная онлайн регрессия.

44.    Бустинг. Стохастический градиентный бустинг и задача ранжирования  web -страниц.

45.    Теоретико-игровая интерпретация теории вероятностей (продолжение).

 

 

Литература

1.       Lugosi G., Cesa-Bianchi N. Prediction, learning and games. New York: Cambridge University Press, 2006.

2.       Вьюгин В.В. Математические основы теории машинного обучения и прогнозирования. М.: МЦНМО, 2013.

3.       Алон   Н .,  Спенсер   Дж Вероятностный метод в комбинаторике. М.: Бином, 2007.

4.       Boucheron S., Lugoshi G., Massart P. Concentration inequalities: A nonasymptotic theory of independence. Oxford University   Press,  2013.

5.       Верещагин Н.К., Успенский В.А., Шень А. Колмогоровская сложность и алгоритмическая случайность. М.: МЦНМО, 2013.

6.       Верещагин Н.К., Щепин Е.В. Информация, кодирование и предсказание. М.: МЦНМО, 2012.

7.       Вьюгин В.В. Колмогоровская сложность и алгоритмическая случайность. М. МФТИ, 2012.

8.       Зорич В.А. Математический анализ задач естествознания. М.: МЦНМО, 2008.

9.       Ромащенко А., Румянцев А., Шень А. Заметки по теории кодирования. М.: МЦНМО, 2011.

10.    Бланк М.Л. Устойчивость и локализация в хаотической динамики. М.: МЦНМО, 2001.

11.    Тао Т.  Структура и случайность. М.: МЦНМО, 2013.

12.    Motwani R., Raghavan P. Randomized algorithms. Cambridge Univ. Press, 1995.

13.    Dubhashi D.P., Panconesi A. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.

14.    Ledoux M. Concentration of measure phenomenon. Providence, RI, Amer. Math. Soc., 2001 (Math. Surveys Monogr. V. 89).

15.    Bubeck S.,   Cesa-Bianchi N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems // Foundation and Trends in Machine Learning. 2012. V. 5. № 1. P. 1 122.

16.    Гасников А.В., Дмитриев Д.Ю. Об эффективных рандомизированных алгоритмах поиска вектора PageRank // Автоматика и телемеханика. 2014.

17.    Гасников А.В., Гасникова Е.В. Об энтропийно-подобных функционалах … // Математические заметки. 2013 . Т. 94. № 6. С. 816–824.

18.    Гасников А. В., Нестеров Ю.Е., Спокойный В.Г. Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн оптимизации // Автоматика и телемеханика. 2014.

19.    Andersen S. P., de Palma A., Thisse J.-F. Discrete choice theory of product differentiation. MIT   Press Camb ., 1992.

20.    Sandholm W. Population games and Evolutionary dynamics. Economic Learning and Social Evolution. MIT Press; Cambridge, 2010.

 

См. также на  mathnet.ru   выступления в рамках научных семинаров Математический кружок и Стохастический анализ в задачах: В.В. Вьюгина, Г.К. Голубева, Г.А. Кабатянского, А.В. Назина, Ю.Е. Нестерова, М.Л. Бланка, А. Шеня, А.В. Гасникова и др.

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика