Difference between revisions of "BSc: MathematicalFoundationsOfAI"

From IU
Jump to navigation Jump to search
 
(12 intermediate revisions by the same user not shown)
Line 16: Line 16:
 
: '''Целью освоения дисциплины''' является обучение студентов с соответствующей математикой, что впоследствии должно помочь им в изучении специализированных разделов анализа данных (машинного обучения, статистики, обучения с подкреплением, численных методов оптимизации, моделирования больших сетей и т.д.).
 
: '''Целью освоения дисциплины''' является обучение студентов с соответствующей математикой, что впоследствии должно помочь им в изучении специализированных разделов анализа данных (машинного обучения, статистики, обучения с подкреплением, численных методов оптимизации, моделирования больших сетей и т.д.).
   
  +
: '''Задачами дисциплины''' являются знакомство с математическими основами искусственного интеллекта. Формирование у студентов теоретических знаний и практических навыков применения математического аппарата для решения актуальных задач в области искусственного интеллекта.
: '''Задачами дисциплины''' являются ...
 
   
 
=== Общая характеристика результата обучения по дисциплине ===
 
=== Общая характеристика результата обучения по дисциплине ===
: '''Знания: ''' после прохождения курса у студентов должны быть сформированы .
+
: '''Знания: ''' после прохождения курса у студентов должны быть сформированы следующие знания:
  +
- принципы математической оптимизации и численные методы для решения задач машинного обучения, <br>
  +
- основные концепции вероятности и статистики, применяемые в области искусственного интеллекта,<br>
  +
- навыки работы с многомерными данными и их математическим анализом.
   
: '''Умения:''' сформированы умения .
+
: '''Умения:''' сформированы умения:
  +
- умение применять математические методы для анализа и решения задач в области искусственного интеллекта, <br>
  +
- способность использовать различные алгоритмы оптимизации для обучения и тестирования моделей машинного обучения, <br>
  +
- навык проведения статистического анализа данных и извлечения информации из них, <br>
  +
- умение интерпретировать и визуализировать результаты математического анализа для принятия обоснованных решений.
   
: '''Навыки (владения):''' в результате прохождения курса формируются навыки .
+
: '''Навыки (владения):''' в результате прохождения курса формируются навыки:
  +
- навык применения математического аппарата для проектирования и разработки алгоритмов и моделей искусственного интеллекта,<br>
  +
- навык использования программных средств для работы с математическими моделями и алгоритмами,<br>
  +
- навык адаптации математических подходов и решений к различным задачам в области искусственного интеллекта.
   
 
== 3. Структура и содержание дисциплины ==
 
== 3. Структура и содержание дисциплины ==
Line 164: Line 174:
 
== 4. Методические и оценочные материалы ==
 
== 4. Методические и оценочные материалы ==
 
'''Задания для практических занятий:</b>'''
 
'''Задания для практических занятий:</b>'''
{| class="wikitable" style="width:70%;"
+
{| class="wikitable" style="width:80%;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
| style="width:10%" | №<br>п/п
 
| style="width:10%" | №<br>п/п
Line 170: Line 180:
 
| style="width:60%" | Перечень рассматриваемых тем (вопросов)<br>
 
| style="width:60%" | Перечень рассматриваемых тем (вопросов)<br>
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
| style="text-align:center;" | 1. || Элементы теории аппроксимации. ||
+
| style="text-align:center;" | Проект 1. || Reinforcement Learning / AMDP (теоретический). ||
  +
В современном обучении с подкреплением в плане теории уже довольно много сделано. Однако для average-reward (AMDP) постановок в теории есть зазор между нижними и верхними оценками. Предлагается в целом изучить RL сквозь призму современной стох. оптимизации (см. в этой связи презентацию, прикрепленную у описанию и цитированную литературу) и сконцентрироваться именно на AMDP. Итогом здесь должно быть написание некоторого небольшого (7-10 страниц) текста-отчета (лучше всего, сделанного в оверлифе), в котором описывается state-of-the-art результаты (теоретические) по AMDP постановкам. Отмечу, что в презентации содержатся не все нужные ссылки (например, нет вот [https://arxiv.org/pdf/1906.05110.pdf этой]), и отчасти работа заключается в поиске таких теоретических работ, в которых есть интересные продвижения.
#Построить алгоритм для приближения рациональным числом корня полинома указанной степени с целыми коэффициентами.<br>
 
#Рассмотреть интерполяцию заданной функции на равномерной сетке и вычислить интеграл квадрата разности значения интерполяционного полинома и интерполируемой функции.<br>
 
#Вычислить максимальное отклонение интерполируемой функции и построенного интерполяционного полинома. Проиллюстрировать явление Рунге.<br>
 
#Построить набор узлов Чебышева для заданной функции построить интерполяционный полином. Вычистить интеграл от квадрата разности интерполяционного полинома Чебышева и интерполируемой функции.<br>
 
#Построить частичную сумму Фурье для заданной разрывной функции и проиллюстрировать численно феномен Гиббса.<br>
 
#Построить сплайн для аппроксимации заданной табличной функции с заданным дефектом.<br>
 
#Построить Паде аппроксимацию заданного порядка для экспоненты.<br>
 
#Построить Паде аппроксимацию заданного порядка для функции синус. <br>
 
   
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
| style="text-align:center;" | 2. || Расходящиеся ряды.||
+
| style="text-align:center;" | Проект 2. || Поиск вектора Page Rank.||
  +
Изучите статьи [https://arxiv.org/ftp/arxiv/papers/1701/1701.02595.pdf Вокруг степенного закона распределения компонент вектора PageRank], [https://arxiv.org/pdf/1508.07607.pdf Efficient Numerical Methods to Solve Sparse Linear Equations with Application to PageRank (тут есть пример, откуда можно брать данные)]. Попробуйте реализовать метод MCMC и еще парочку приглянувшихся методов для задачи поиска вектора PageRank. Определите, какой метод и в каком смысле лучше работает. Итогом здесь должен быть colab ноутбук с кодом и хорошими комментариями, поясняющими полученные результаты.<br>
#Методом интегрирования по частям получить частичную сумму асимптотического при больших значениях аргумента ряда для интеграла Френеля.<br>
 
  +
[https://github.com/HCL-271/Page_rank,%20https://colab.research.google.com/drive/1XZPBAG0CrPeNP5TdIMXr0vtigS2L3JDU?usp=sharing Примеры сделанного проекта]
#Оценить величину остатка ряда в зависимости от количества членов ряда и от аргумента функции Френеля.<br>
 
#Основываясь на интегральном представлении Гамма-функции получить частичную сумму асимптотического ряда при больших значениях аргумента Гамма-функции. Исследовать относительную погрешность формулы Муавра-Стирлинга.<br>
 
#Просуммировать по Чезаро расходящийся знакопеременный ряд.<br>
 
#Найти сумму по Борелю для расходящегося ряда.<br>
 
#Показать, что суммирование по Чезаро и по Борелю дают одинаковые результаты, если эти сумму существуют.<br>
 
#Указать калибровочную последовательность для функции Эйри при построении асимптотики вблизи бесконечно удаленной точки.<br>
 
   
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
| style="text-align:center;" | 3. ||Анализ на многообразиях нецелой размерности.||
+
| style="text-align:center;" | Проект 3. ||Градиентный клиппинг.||
  +
Посмотрите вот это [https://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=35797. видео]. В различных моделях обучения возникают задачи стохастической оптимизации, в которых у градиентов имеются тяжелые хвосты. Для лучшей практической работы стандартных методов типа SGD и их моментных вариантов используется клиппирование (пробатченного) стохастического градиента. Такой проект мы делали летом 2022 года со школьниками в Сириусе. В результате было сделано следующее (стоит делать поправку, что это делали школьники 8-10 классов): <br>
#Вычислить фрактальную размерность жирного множества Кантора.<br>
 
  +
::[https://bigchallenges.ru/clipping Лендинг]<br>
#Вычислить фрактальную размерность салфетки Серпинского.<br>
 
  +
::[https://github.com/EugGolovanov/TorchClippedOptimizers GitHub]<br>
#Построить алгоритм для вычисления фрактальной размерности множества Мандельброта.<br>
 
  +
::[https://pypi.org/project/torch-clip/ PyPi]<br>
#Построить алгоритм для вычисления фрактальной размерности множества Жулиа.<br>
 
  +
::Флайер <br>
#Найти численное приближение.<br>
 
  +
Оказывается, для выпуклых задач есть довольно симпатичная математика, стоящая за всем этим: [https://arxiv.org/pdf/2106.05958.pdf Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise], [https://arxiv.org/pdf/2206.01095.pdf Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise] (совсем идейно это описано в самом начале презентации, прикрепленной к описанию). <br>
|}
 
  +
Проект практический и заключается в подборе новых примеров (классов) задач обучения (в том числе состязательного обучения), на которых клиппированные методы работают лучше неклипированных. На самом деле, чтобы не заниматься перебором, как раз важно понять, какой эффект дает клипирование и в каких ситуациях это все может себя проявить. Естественно, на практике размер клипа и батча, возможно, придется подбирать не совсем так как в теории, но в целом, некоторые общие закономерности теоретические результаты дают, по-видимому, правильные, и разумно это использовать, чтобы сократить перебор в подборе этих параметров.
'''Текущий контроль успеваемости обучающихся по дисциплине:'''
 
   
{| class="wikitable" style="width:70%;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
| style="width:5%" | №<br>п/п
 
| style="width:20%" | Наименование раздела<br>дисциплины
 
| style="width:25%" | Форма текущего контроля<br><br>
 
| style="width:50%" | Материалы текущего контроля<br><br>
 
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
| style="text-align:center;" | 1.
+
| style="text-align:center;" | Проект 4. ||Градиентный клиппинг.||
  +
В цикле статей Вершика-Синая-Арнольда исследуются различные предельные формы (например, диаграмм Юнга, выпуклых ломаных и т.п.). Вообще, все это очень красиво, и в своей основе имеет целый ряд фундаментальных законов природы, проявляющихся и в целом ряде других областей. Например, в статистической физике. Для погружения в данную проблематику можно рекомендовать [https://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=231 мини-курс А.М. Вершка из трех лекций]. Некоторые такие примеры разобраны в [https://arxiv.org/pdf/1508.03461.pdf книге] (см. также цитированную там литературу). Искать можно как раз по фамилиям (Вершик, Синай). Целью данного проекта является разбор того, почему имеет место наблюдение, описанное в скрине. В результате работы над проектом должен появиться текст, обосновывающий результат со скрина.<br>
| Элементы теории аппроксимации.
 
  +
[[File:q1.png]]
| style="text-align:center;" | Разработка кода для иллюстрации теоретических положений раздела.
 
| Выбрать одну из задач для практических заданий и написать программу для решений такой задачи.<br>
 
   
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
| style="text-align:center;" | 2.
+
| style="text-align:center;" | Проект 5. ||Как зародилась жизнь? Генетические алгоритмы, Мир РНК.||
  +
Вопрос «как зародилась жизнь?» давно привлекает к себе внимание ученых из разных областей. Текущее понимание этого вопроса изложено в замечательной книге А.А. Маркова «Рождение сложности». Хотя до сих пор нет одной какой-то общепринятой точки зрения, но все же наиболее популярна гипотеза о том, что жизнь могла зародиться из самокопирующихся молекул РНК (гипотеза РНК мира). Обоснование гипотезы требует проработки разных (в том числе чисто математических) вопросов. Замечательно здесь и то, что можно пойти и в обратном направлении (а именно, эволюция/естественный отбор может подсказать способ решения той или иной сложной задачи оптимизации, функционал которой интерпретируется как приспособленность). Собственно, это и предлагается сделать. Решите задачу [https://arxiv.org/pdf/1508.03461.pdf 16 на стр. 175-176]. Требуется математически строго обосновать решение и подкрепить теорию результатами численных экспериментов.
| Расходящиеся ряды.
 
| style="text-align:center;" | Разработка кода для иллюстрации теоретических положений раздела.
 
| Выбрать одну из задач для практических заданий и написать программу для решений такой задачи.<br>
 
   
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | Проект 6. ||Вокруг методов Монте-Карло, в том числе с приложениями к финансовой математике.||
| style="text-align:center;" | 3.
 
  +
Посмотрите [https://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=6060 часть 1] и [https://www.mathnet.ru/php/seminars.phtml?presentid=6774&option_lang=rus часть 2] видео «В окрестностях Монте-Карло» и попробуйте на базе прослушанного предложить какие-то свои вариации классических методов. Проект очень неопределенный. Это сделано специально, чтобы дать больше свободы творчества. Также было бы здорово обратить внимание, что для целого ряда вещей совсем не нужна первозданно случайная последовательность. В частности, на практике эффективными оказываются так называемы квази Монте-Карловские методы, под которые есть [https://web.archive.org/web/20210508093913/https://blogs.princeton.edu/imabandit/2014/12/22/guest-post-by-sasho-nikolov-beating-monte-carlo/ хорошая теория].<br>
| Анализ на многообразиях нецелой размерности.
 
| style="text-align:center;" | Разработка кода для иллюстрации теоретических положений раздела.
 
| Выбрать одну из задач для практических заданий и написать программу для решений такой задачи.<br>
 
   
  +
Цель данного проекта — знакомство с современными приложениями методов Монте-Карло. В частности, для тех, кто хочет посмотреть в сторону финансовой математике можно рекомендовать в качестве проекта выбрать Multi-level Monte Carlo. А именно, проект заключается в том, чтобы аккуратно обосновать (с нужной теорией и желательно демонстрацией на практике) то, что написано в условиях [https://arxiv.org/pdf/1508.03461.pdf задачи 22 на стр. 204-205]. Для погружения в финансовую математику есть [https://zlibrary.org/book/1131868/99d503 очень доступный курс].
|}
 
   
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
'''Контрольные вопросы для подготовки к промежуточной аттестации:'''
 
  +
| style="text-align:center;" | Проект 7. ||Ранняя остановка или регуляризация.||
Для ознакомления доступна [https://disk.yandex.ru/i/2TopPVGCg6kQ0w контрольная работа] <br>
 
  +
Одной из главных проблем машинного обучения является переобучение. Это давно и хорошо известно, и много чего в этой связи было сделано. Если совсем кратко резюмировать, то для задач обучения с выпуклым целевым функционалом (логистическая регрессия, SVM, LASSO, …) основные способы борьбы с переобучением — это регуляризация или ранняя остановка процедур типа SGD. На базе первой главы книги по Алгоритмической стох. оптимизации (ссылка здесь дублируется - имеется в прикрепленном сообщении) попробуйте сделать обзор описанных двух подходов и продемонстрируйте как все это работает на практике. В чем преимущества и недостатки этих двух подходов друг перед другом? Итогом работы по проекту должен стать текст + эксперименты. То есть в этом проекте важны обе составляющие (практическая и теоретическая).
   
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | Проект 8. ||Модели распространения эпидемий, в частности, ковид как модель стохастической химической кинетики.||
  +
Изучите [https://arxiv.org/pdf/1508.03461.pdf. главу 6]. В частности, модель Эренфестов, модель хищник-жертва и ее распределенные варианты. Попробуйте на базе похожего формализма получить систему дифференциальных уравнений [https://en.wikipedia.org/wiki/Compartmental_models_in_epidemiology SIR-типа моделей] и предложите свои обобщения. Для дополнительной мотивации можно посмотреть [https://www.youtube.com/watch?v=gxAaO2rsdIs&t=1s&ab_channel=3Blue1Brown мультфильм].<br>
  +
Результатом работы по проекту может быть описание микроскопической динамики, которая в макромасштабе описывается чем-то типа SIR-моделей или их обобщений. При этом обоснование должно быть как теоретическое, так и практическое.
   
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
| style="text-align:center;" | 3. || Анализ на многообразиях нецелой размерности.||
+
| style="text-align:center;" | Проект 9. ||Почему зависимости частот катастроф от их масштабов имеют степенной закон?||
  +
Изучите задачу Д. Кьялво [https://arxiv.org/pdf/1508.03461.pdf (задача 12 на стр. 170-171)]. Попробуйте не только экспериментально проверить то о чем написано в задаче (естественно, в большем масштабе, чем было в эксперименте, который делал Д. Кьялво над своими студентами), но и обосновать это теоретически. Проект также включает в себя текст, с теоретической проработкой, и эксперименты.
#Дать определение фрактальной размерности. Привести примеры многообразий нецелой размерности.<br>
 
#Привести примеры отображений, генерирующих многообразия фрактальной размерности.<br>
 
#Определение интеграла Дробного порядка и производной дробного порядка.<br>
 
   
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
|}
 
  +
| style="text-align:center;" | Проект 10. ||Почему большинство крупных мегаполисов живут в режиме пробок, фазовый переход в сетях массового обслуживания.||
  +
Этот проект совершенно реален (то есть идею этого проекта воплотили в жизнь при планировании развития сети общественного транспорта в г. Москве за последние 10-15 лет). Вот [https://elementy.ru/nauchno-populyarnaya_biblioteka/431798/Kak_borotsya_s_probkami краткое описание проблематики] (ключевой тут рис. 1). Немного есть про это вот в этом [https://vk.com/video-135454514_456242213 видео] (в концовке как раз об этом, впрочем, начало тоже интересное, но не об этом). Речь идет о том, что большинство крупных мегаполисов живут в режимах, когда есть и много пробок. Почему это так? Математическое объяснение есть в [http://www.mou.mipt.ru/gasnikov1129.pdf книге] (см. приложение Малышева-Замятина). Собственно, эта тема дальше развивается в Исследовательской задаче (такой раздел есть в книге) «Задача о критическом числе автомобилей для заданного города». Предложите свой вариант такого типа задачи и получите практическое подтверждение наличия фазового перехода. Проект практический.
   
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
'''Вопросы/Задания к промежуточной аттестации в устной/письменной форме:'''
 
  +
| style="text-align:center;" | Проект 11. ||Четыре рукопожатия и как это посчитать?||
  +
В замечательной [https://zlibrary.org/book/3389327/273068 книге Райгородского-Литвак] совсем по-простому рассказано о том, как современные социальные сети решают различные задачи подсчета (см. сюжет из Главы 7 Счетчики с короткой памятью и в частности Четыре виртуальных рукопожатия). Попробуйте разобрать пример из статьи Себастьяна Виньи на более продвинутом уровне чем в популярной книге Райгородского-Литвак. В частности, помочь может вот эта [https://www.cs.cornell.edu/jeh/book%20no%20so;utions%20March%202019.pdf. книга]. Цель проекта продемонстрировать математику, которая есть вокруг этого сюжета (в частности, хеширование). Проект теоретический, но чтобы получить по нему хорошую оценку нужно либо довольно тонко освоить теорию, либо провести достаточно понятные эксперименты, подтверждающие теорию...
   
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
#Blum A., Hopcroft J., Kannan R. Foundations of data science. – Cambridge University Press, 2020.<br>
 
  +
| style="text-align:center;" | Проект 12. ||Межгрупповая вражда способствует внутригрупповому сотрудничеству.||
#Bach F. Learning Theory from First Principles. – 2021.<br>
 
  +
В другой интересной книге [https://readingbook.ru/humanities/1055-evolyuciya-cheloveka-v-2-knigah-kniga-2-obezyany-neyrony-i-dusha.html А.А. Маркова] в главе 5 есть параграф, который называется так как этот проект. Прочитайте параграф, постарайтесь понять о чем идет речь. В параграфе описывается некоторое равновесие макросистемы. Попробуйте придумать каку-то разумную динамику, которая бы приводила к такому равновесию (соответствующие заготовки могут быть почерпнуты из 6 главы [https://arxiv.org/pdf/1508.03461.pdf книги]). Нужно не только придумать, подтвердить экспериментально, но и попробовать математически обосновать, что предложенная динамика, действительно, выходит на нужное равновесие…<br>
#Тыртышников Е. Е. Методы численного анализа. – 2007.<br>
 
  +
#Зорич В. Математический анализ задач естествознания. – Litres, 2018.<br>
 
  +
P.S. В целом, очень рекомендую эту книгу Маркова, если есть желание получше разобраться как устроены люди. Кажется, в этой книге есть и много других интересных сюжетов (например, парадокс Симпсона, теория Гамильтона — родственного отбора, и многое другое), которые, по-видимому, качественно улавливают какие-то закономерности, управляющие поведением людей.<br>
  +
  +
По итогам этого проекта появилась [https://nauka.tass.ru/nauka/16928303?utm_source=tass.ru&utm_medium=referral&utm_campaign=tass.ru&utm_referrer=tass.ru статья].<br>
  +
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | Проект 13. ||Кинетика социального неравенства.||
  +
Решите [https://arxiv.org/pdf/1508.03461.pdf задачу 4 на стр. 154-162]. Решение требуется привести математическое. Это один вариант сдачи проекта. Второй вариант — предложить свои вариации модели обмена монетками, которые приводят к более интересным асимптотикам. В этом случае обоснование формы предельных кривых может быть схематичным, но желательно тогда подтверждение численными экспериментами.
  +
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | Проект 14. ||Двойной спуск, сложный проект!||
  +
В последние годы в задачах обучения наблюдается довольно интересный эффект, что если модель сильно переобучена, то U-образная кривая снова начинает убывать. Математика этого эффекта еще далека от своего окончательного объяснения, но все же попытки это объяснить имеются. В том числе [https://www.di.ens.fr/~fbach/ltfp_book.pdf довольно компактные]. Более того, все эти вопросы оказываются завязанными на так называемое [https://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=32683. условие Поляка-Лоясиевича] (градиентного доминирования). К сожалению, на данный момент неизвестны нижние оценки для гладких задач оптимизации в условиях Поляка-Лоясиевича. При том, что много интересных результатов о сходимости градиентного типа методов (в том числе и их стохастических вариантов) есть. Проект, по-видимому, достаточно сложный. Целью проекта является продвинуться в понимание, какие нижние оценки имеют место для методов типа градиентного спуска в условиях Поляка-Лоясиевича. Гипотеза, что имеющиеся верхние оценки оптимальны. То есть ускорения в условиях Поляка-Лоясиевича нет. Проблема тут с использованием стандартной техники получения нижних оценок [https://opt.mipt.ru/posobie.pdf упражнения 1.3 и 2.1.] Нужно найти подобную плохую функцию, удовлетворяющую условию Поляка-Лоясиевича. Ну или как-то еще посмотреть на эту задачу.
  +
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | Проект 15. ||Гамильтоновы пути и концентрация меры.||
  +
Хорошо известно, что задача поиска гамильтонова пути — NP-трудна. А именно, трудной является задача почтальона: в каком порядке надо обойти дома на своем участке и вернуться в отделение почты (откуда и стартует маршрут), чтобы суммарная длина пути была бы минимальна? Конечно, метрический коммивояжер уже немного попроще (веса ребер графа отвечают некоторой топологии реальной дорожной сети, скажем на плоскости), чем общая задача. Все равно эта задача остается сложной и улучшается у нее только различные аппроксимационные характеристики. Представим себе, что теперь у нас город — это квадрат со стороной 1. В городе n домов. Все дома случайно и независимо построены (дом - это точка в квадрате, обе координаты которой выбираются независимо и из равномерного распределения). Обозначим длину кратчайшего (гамильтонового) пути в таком графе через TSP(n). Это будет случайная величина. Покажите, что TSP(n) экспоненциально концентрируется около своего математического ожидания, пропорционального \sqrt{n}. Указание: Используйте [https://zlibrary.org/book/703189/6d862b книгу].
  +
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | Проект 16. ||Устойчивые системы большой размерности.||
  +
Попробуйте решить задачу<br>
  +
[[File:q2.png]]
  +
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | Проект 17. ||О типично худшем накоплении ошибки в линейных итерационных методах.||
  +
Попробуйте решить задачу<br>
  +
[[File:q3.png]]<br>
  +
[https://colab.research.google.com/drive/1P_ZYfSt4zA-kXoo1fuoWRU_annABgN2I?usp=sharing Пример сделанного проекта]
  +
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | Проект 17 от Максима Рахубы. ||Использование тензорных сетей для сжатия и восстановления изображений.||
  +
В этом проекте предлагается познакомиться с тензорными сетями (обобщение матричных факторизаций на многомерный случай и их приложением для задач восстановления изображения по значениям в небольшом числе пикселей (tensor completion), а также для сжатия изображений. Для конкретики можно рассмотреть тензорные сети PEPS, тензорное кольцо и/или тензорный поезд. Для решения задач минимизации можете использовать несколько методов оптимизации на свой выбор, а также реализовать метод попеременных наименьших квадратов (ALS) (только для задачи сжатия). Для более детального ознакомления с постановкой задачи и одним из возможных алгоритмов прочитайте [https://arxiv.org/abs/2008.05437 статью] и ознакомьтесь с [https://tensornetwork.org/ сайтом]. В качестве фреймворка для написания проекта можно воспользоваться [https://github.com/google/TensorNetwork пакетом] или альтернативными вариантами. Результатом работы по проекту должна стать jupyter тетрадка (можно ссылкой в colab), с кодом, кратким описанием используемых алгоритмов, а также графиками ошибки и значений PSNR от числа параметров в тензорных сетях для нескольких изображений. <br>
  +
По поводу вопросов пишите в ТГ @mrakhuba.
  +
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | Проект 18 от Максима Рахубы.||Методы римановой оптимизации и их приложение для рекомендательных систем.||
  +
Известно, что множество матриц фиксированного ранга является римановым многообразием. Эту информацию можно использовать для построения эффективных методов поиска малоранговых приближений матриц. В этом проекте предлагается познакомиться с методами римановой оптимизации, реализовать [https://arxiv.org/pdf/1209.3834.pdf риманов метод сопряженных градиентов], а также воспользоваться им для минимизации l1 нормы ошибки. В качестве приложения предлагается построить рекомендательную систему. Результатом работы по проекту должна стать jupyter тетрадка (можно ссылкой в colab), с кодом, кратким описанием используемых алгоритмов, а также графиками зависимости RMSE и одной из релевантных для рекомендательных систем метрик в зависимости от ранга. <br>
  +
  +
По поводу вопросов пишите в ТГ @mrakhuba.
  +
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | Проект 19 от Алексея Фролова.|| Граница случайного кодирования для задачи сжатия измерений массового некоординированного множественного доступа.||
  +
В работе [1] введена теоретико-информационная модель массового некоординированного множественного доступа и получена граница случайного кодирования, которую можно применять как в асимптотическом, так и неасимптотическом режимах. Улучшение для асимптотического режима предложено в работе [2] с использованием леммы Гордона (Gordon’s lemma) о минимуме гауссовского процесса. Задача данного проекта заключается в получении неасимптотической версии границы из [2]. Также разрешается применять любые другие методы уточнения аддитивной границы из [1], например, предложенную на лекции локальную лемму Ловаша.<br>
  +
1. Y. Polyanskiy, “A perspective on massive random-access,” IEEE Information Theory (ISIT), 2017.<br>
  +
2. I. Zadik, Y. Polyanskiy, and C. Thrampoulidis, “Improved bounds on Gaussian MAC and sparse regression via Gaussian inequalities,” IEEE International Symposium on Information Theory (ISIT), 2019<br>
  +
  +
|}
  +
  +
'''Контрольные вопросы для подготовки к промежуточной аттестации:'''<br><br>
  +
Для ознакомления доступна [https://disk.yandex.ru/i/2TopPVGCg6kQ0w контрольная работа] <br>
   
 
=== Перечень учебно-методического обеспечения дисциплины ===
 
=== Перечень учебно-методического обеспечения дисциплины ===
 
Список основной литературы:<br>
 
Список основной литературы:<br>
  +
1. Blum A., Hopcroft J., Kannan R. Foundations of data science. – Cambridge University Press, 2020.<br>
  +
2. Bach F. Learning Theory from First Principles. – 2021.<br>
  +
3. Тыртышников Е. Е. Методы численного анализа. – 2007.<br>
  +
4. Зорич В. Математический анализ задач естествознания. – Litres, 2018.<br>
  +
  +
Список дополнительной литературы:<br>
 
1. Гyдфеллоy Я., Бенджио И., Кyрвилль А. Глyбокое обyчение. 2-е изд., исправл. М.: ДМК-Пресс, 2018.<br>
 
1. Гyдфеллоy Я., Бенджио И., Кyрвилль А. Глyбокое обyчение. 2-е изд., исправл. М.: ДМК-Пресс, 2018.<br>
 
2. Shapiro A., Dentcheva D., Ruszczyński A. Lectures on stochastic programming: modeling and theory. – Society for Industrial and Applied Mathematics, 2014.<br>
 
2. Shapiro A., Dentcheva D., Ruszczyński A. Lectures on stochastic programming: modeling and theory. – Society for Industrial and Applied Mathematics, 2014.<br>
Line 257: Line 305:
 
9. Shen A., Romashchenko A., Rumyantsev A. Y. Заметки по теории кодирования. – 2017.<br>
 
9. Shen A., Romashchenko A., Rumyantsev A. Y. Заметки по теории кодирования. – 2017.<br>
 
10. Vershynin R. High-dimensional probability: An introduction with applications in data science. – Cambridge university press, 2018. – Т. 47.<br>
 
10. Vershynin R. High-dimensional probability: An introduction with applications in data science. – Cambridge university press, 2018. – Т. 47.<br>
 
Список дополнительной литературы:<br>
 
#Glebov S.G., Kiselev O.M., Tarkhanov N., Nonlinear equations with small parameter. Volume I: Oscillations and resonances De Gruyter Series in Nonlinear Analysis and Applications. 2017, v. 23/1, pp.340.<br>
 
#Лутц М., Изучаем Python: Т. 1, 2, Издательство Диалектика, 2023, ISBN 9785521805532<br>
 
#Beazley D., Jones B.K. Python Cookbook, 3rd Edition by 2013 Publisher(s): O'Reilly Media, Inc. ISBN: 9781449357351<br>
 
   
 
=== Методические указания для обучающихся по освоению дисциплины ===
 
=== Методические указания для обучающихся по освоению дисциплины ===
Line 271: Line 314:
 
| style="vertical-align:middle; text-align:center;" | Лекция
 
| style="vertical-align:middle; text-align:center;" | Лекция
 
| style="vertical-align:middle; text-align:left;" | Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
 
| style="vertical-align:middle; text-align:left;" | Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
|-
 
| style="vertical-align:middle; text-align:center;" | Практическое (семинарское) занятие
 
| style="vertical-align:middle; text-align:left;" | При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его.<br>Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
 
|-
 
| style="vertical-align:middle; text-align:center;" | Устный/письменный опрос
 
| style="vertical-align:middle; text-align:left;" | Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
 
|-
 
| style="vertical-align:middle; text-align:center;" | Реферат
 
| style="vertical-align:middle; text-align:left;" | Поиск источников и литературы, составление библиографии. При написании реферата рекомендуется использовать разнообразные источники, монографии и статьи из научных журналов, позволяющие глубже разобраться в различных точках зрения на заданную тему. Изучение литературы следует начинать с наиболее общих трудов, затем следует переходить к освоению специализированных исследований по выбранной теме. Могут быть использованы ресурсы сети «Интернет» с соответствующими ссылками на использованные сайты.<br>Если тема содержит проблемный вопрос, следует сформулировать разные точки зрения на него. Рекомендуется в выводах указать свое собственное аргументированное мнение по данной проблеме. Подготовить презентацию для защиты реферата.
 
|-
 
| style="vertical-align:middle; text-align:center;" | Эссе
 
| style="vertical-align:middle; text-align:left;" | Написание прозаического сочинения небольшого объема и свободной композиции, выражающего индивидуальные впечатления и соображения по конкретному поводу или вопросу и заведомо не претендующего на определяющую или исчерпывающую трактовку предмета. При работе над эссе следует четко и грамотно формулировать мысли, структурировать информацию, использовать основные понятия, выделять причинно-следственные связи. Как правило эссе имеет следующую структуру: вступление, тезис и аргументация его, заключение. В качестве аргументов могут выступать исторические факты, явления общественной жизни, события, жизненные ситуации и жизненный опыт, научные доказательства, ссылки на мнение ученых и др.
 
 
|-
 
|-
 
| style="vertical-align:middle; text-align:center;" | Подготовка к промежуточной аттестации
 
| style="vertical-align:middle; text-align:center;" | Подготовка к промежуточной аттестации
 
| style="vertical-align:middle; text-align:left;" | При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей.<br>Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
 
| style="vertical-align:middle; text-align:left;" | При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей.<br>Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
|-
 
| style="vertical-align:middle; text-align:center;" | Практические (лабораторные) занятия
 
| style="vertical-align:middle; text-align:left;" | Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
 
|-
 
| style="vertical-align:middle; text-align:center;" | Самостоятельная работа
 
| style="vertical-align:middle; text-align:left;" | Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
 
|-
 
| style="vertical-align:middle; text-align:center;" | Видеопрезентация
 
| style="vertical-align:middle; text-align:left;" | Подготовка видеопрезентаций по курсу. Видеопрезентации могут быть сделаны на любую тему, затронутую в ходе курса. Темы должны быть заранее согласованы с преподавателем. Видеопрезентации продолжительностью около 5 минут (300 секунд) должны быть подготовлены в группах, определяемых преподавателем. Несмотря на то, что это групповая работа, должен явно присутствовать вклад каждого члена группы.
 
|-
 
| style="vertical-align:middle; text-align:center;" | Доклад
 
| style="vertical-align:middle; text-align:left;" | Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
 
|-
 
| style="vertical-align:middle; text-align:center;" | Дискуссия
 
| style="vertical-align:middle; text-align:left;" | Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
 
 
|-
 
|-
 
| style="vertical-align:middle; text-align:center;" | Контрольная работа
 
| style="vertical-align:middle; text-align:center;" | Контрольная работа
 
| style="vertical-align:middle; text-align:left;" | При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
 
| style="vertical-align:middle; text-align:left;" | При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
|-
 
| style="vertical-align:middle; text-align:center;" | Тестирование (устное/письменное)
 
| style="vertical-align:middle; text-align:left;" | При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.
 
|-
 
| style="vertical-align:middle; text-align:center;" | Индивидуальная работа
 
| style="vertical-align:middle; text-align:left;" | При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
 
|-
 
| style="vertical-align:middle; text-align:center;" | Разработка отдельных частей кода
 
| style="vertical-align:middle; text-align:left;" | Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
 
 
|-
 
|-
 
| style="vertical-align:middle; text-align:center;" | Выполнение домашних заданий и групповых проектов
 
| style="vertical-align:middle; text-align:center;" | Выполнение домашних заданий и групповых проектов
Line 322: Line 329:
 
| Методы и технологии обучения, способствующие формированию компетенции
 
| Методы и технологии обучения, способствующие формированию компетенции
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
| В курсе планируется использовать несколько технологий обучения. Таких как: <u> интерактивные лекции </u>, поощряющие участие студентов посредством сессий вопросов и ответов, живых демонстраций концепций квантовых вычислений или групповых дискуссий.
+
| В курсе планируется использовать несколько технологий обучения. Таких как: <u> интерактивные лекции </u>, поощряющие участие студентов посредством сессий вопросов и ответов или групповых дискуссий.
   
<u> Проблемно-ориентированное обучение </u> – мероприятия по решению проблем, которые побуждают студентов применять концепции квантовых вычислений в практических ситуациях. Этот метод может улучшить навыки критического мышления и закрепления знаний.
+
<u> Проблемно-ориентированное обучение </u> – мероприятия по решению проблем, которые побуждают студентов применять концепции курса в практических ситуациях. Этот метод может улучшить навыки критического мышления и закрепления знаний.
   
Будут применяться <u> программные библиотеки для аналитических и численных методов: SymPy, NumPy, и SciPy </u>, что позволит использовать компьютер как инструмент для изучения свойств аналитических функции, изучать теорию аппроксимаций и получить опыт использования компьютерных вычислений в задачах математического анализа.
 
   
Планируется предложить <u> совместные проекты </u>, которые требуют применения концепций квантовых вычислений в реальных сценариях или создания новых квантовых алгоритмов. Такой подход может способствовать командной работе, навыкам общения и креативности, одновременно углубляя понимание студентами концепций квантовых вычислений.
+
Планируется предложить <u> совместные проекты </u>, которые требуют применения концепций курса в реальных сценариях. Такой подход может способствовать командной работе, навыкам общения и креативности, одновременно углубляя понимание студентами концепций курса.
   
Важный элемент курса – <u> смешанное обучение </u>: сочетание традиционного очного обучения с онлайн-учебными ресурсами, такими как видео, симуляторы или интерактивные викторины. Такой подход может учитывать различные стили обучения и предпочтения, одновременно улучшая понимание учащимися концепций квантовых вычислений.
+
Важный элемент курса – <u> смешанное обучение </u>: сочетание традиционного очного обучения с онлайн-учебными ресурсами, такими как видео, симуляторы или интерактивные викторины. Такой подход может учитывать различные стили обучения и предпочтения, одновременно улучшая понимание учащимися концепций курса.
 
&nbsp;
 
&nbsp;
 
|}
 
|}

Latest revision as of 06:53, 23 April 2024

Математические основы искуственного интеллекта

Квалификация выпускника: бакалавр
Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”
Направленность (профиль) образовательной программы: Математические основы ИИ
Программу разработал(а):

1. Краткая характеристика дисциплины

Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в следующих областях знаний:
Явление концентрации меры. Начиная с классических результатов Гаусса, Максвелла, Пуанкаре, Леви, Мильмана, планируется постепенно перейти к современным результатам и приложениям, в том числе, возникающим в разнообразных задачах анализа данных.

Численные методы решения задач (выпуклой) стохастической оптимизации в пространствах больших размеров. Такие задачи часто возникают в разнообразных приложениях, в том числе в анализе данных — принцип максимального правдоподобия в статистике, минимизация риска в машинном обучении.

Классическая теорема о SVD-разложении и ее различные обобщения будут продемонстрированы в приложениях к данным, хранящимся в многомерных массивах.

2. Перечень планируемых результатов обучения

Целью освоения дисциплины является обучение студентов с соответствующей математикой, что впоследствии должно помочь им в изучении специализированных разделов анализа данных (машинного обучения, статистики, обучения с подкреплением, численных методов оптимизации, моделирования больших сетей и т.д.).
Задачами дисциплины являются знакомство с математическими основами искусственного интеллекта. Формирование у студентов теоретических знаний и практических навыков применения математического аппарата для решения актуальных задач в области искусственного интеллекта.

Общая характеристика результата обучения по дисциплине

Знания: после прохождения курса у студентов должны быть сформированы следующие знания:

- принципы математической оптимизации и численные методы для решения задач машинного обучения,
- основные концепции вероятности и статистики, применяемые в области искусственного интеллекта,
- навыки работы с многомерными данными и их математическим анализом.

Умения: сформированы умения:

- умение применять математические методы для анализа и решения задач в области искусственного интеллекта,
- способность использовать различные алгоритмы оптимизации для обучения и тестирования моделей машинного обучения,
- навык проведения статистического анализа данных и извлечения информации из них,
- умение интерпретировать и визуализировать результаты математического анализа для принятия обоснованных решений.

Навыки (владения): в результате прохождения курса формируются навыки:

- навык применения математического аппарата для проектирования и разработки алгоритмов и моделей искусственного интеллекта,
- навык использования программных средств для работы с математическими моделями и алгоритмами,
- навык адаптации математических подходов и решений к различным задачам в области искусственного интеллекта.

3. Структура и содержание дисциплины


п/п
Наименование раздела
дисциплины
Содержание дисциплины по темам
1. Вокруг задач поиска вектора PageRank.

1 часть (Google problem) изложена в учебном пособии (Б. Вектор PageRank и Google Problem)
2 часть (Методы Монте-Карло с цепями Маркова)
изложена в публикации Также по ходу лекции будут упоминаться классические результаты из теории случайных процессов, с которыми можно ознакомиться в учебнике из п. 1.
C относительно простым изложением приниципа максимума правдоподобия можно ознакомиться в книге.
В целом, про вычислительные аспекты задачи поиска вектора PageRank можно прочесть в публикации.
Подробнее о макросистемах, стохастической химической кинетике и т.п. можно прочесть в учебном пособии Особенно рекомендуется пример «Кинетики социального неравенства».

2. Элементы теории случайных процессов.

1. Классические вопросы, связанные с методом Монте-Карло (вычисление площади, интеграла, Hit and run алгоритм).

Соболь И.М. Численные методы Монте-Карло
Статья Lovasz-Vempala

2. Введение в эргодические динамические системы и эргодические случайные процессы (поворот окружности, сдвиг Бернулли, цепные дроби, восстановления с помощью эргодической теоремы параметра сноса по достаточно длинной траектории геометрического броуновского движения - процесса Башелье-Самуэльсона).

Случайные процессы. под ред. А.В. Гасникова
Учебник Коралова-Синая

3. Основные классы случайных процессов (Мартингалы и безарбитражный рынок ценных бумаг, процессы Леви (Винеровский процесс как диффузионный предел случайных блужданий, Пуассоновский, сложный Пуассоновский), безгранично-делимые распределения).

Случайные процессы. под ред. А.В. Гасникова
Стохастический анализ в задачах. под ред. А.В. Гасникова
Булинский А.В. Случайные процессы. МФТИ
3. Вокруг Центральной предельной теоремы.

1. Центральная предельная теорема для схемы i.i.d. и ее доказательство с помощью аппарата характеристических функций. Схема рассуждений была взята из книги Розанов Ю.А. Лекции по теории вероятностей. Изд. 3, 2008. 136 с.
2. Два классических неравенства концентрации меры (Хефдинга и Бернштейна). Неравенства взяты из статьи-обзора Габора Лугоши Conentration-of-measure inequalities. Упоминается также неравенство для субгауссовско-экспоненциальной концентрации (то есть такой же, как и для предыдущих двух неравенств) квадрата нормы стандартного гауссовского вектора, детали и обобщения можно посмотреть в статье В.Г. Спокойного.
3. Центральная предельная теорема для случайных величин с тяжелыми хвостами имеется в книге Боровков А.А.
Асимптотический анализ случайных блужданий. Т.1. Медленно убывающие распределения скачков. М.: Физматлит, 2008. - 650 с. Также упоминается неравенство Берри-Эссена, оно есть в многих книжках, например, Сенатов В.В. Центральная предельная теорема: Точность аппроксимации и асимптотические разложения Изд. стереотип. URSS. 2018. 350 с.
4. Геометрическое броуновское движение и стохастическое дифференциальное уравнение для него. Изложение близко к книге Булинский А.В. Случайные процессы. МФТИ, 2010.
5. Simulated annealing был рассказан по книге Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума. 1991. 248 с.

4. Стохастические дифференциальные уравнения и методы Монте-Карло, Стохастический градиентный спуск.

1. Условное математическое ожидание. Гильбертово пространство квадратично-интегрируемых случайных величин. Получение характеристической функции сложного Пуассоновского процесса с помощью формулы полного математического ожидания. Случайные процессы. под ред. А.В. Гасникова.
2. Продолжение изучения Simulated annealing (Имитация отжига). В частности, рассматривается уравнение Колмогорова-Фоккера-Планка, его вывод на основе формулы Дынкина. Также затрагиваются случайные блуждания и решения краевых задач. Во многом изложение ведется по книге Б. Оксендаля Стохастические дифференциальные уравнения.
3. Случай d = 1 (одномерный), квази-монтекарловские методы.
4. Стохастическая оптимизация, негладкий случай.

5. Вокруг стохастического градиентного спуска.

1. Неравенство Азума-Хефдинга
2. Зеркальный спуск, пример единичного симплекса и онлайн оптимизация (взвешивание экспертных решений, приложение к теории игр)

Introduction to Online Convex Optimization
Prediction, Learning, and Games
Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн оптимизации
A Modern Introduction to Online Learning

3. Клиппирование, использование неравенства Бернштейна-Фридмана.
4. Сходимость стохастического градиентного спуска в гладком сильно выпуклом случае, в условиях перепараметризации.

6. Концентрация меры.

1. Метод Лапласа (исследование асимптотики интеграла по параметру), обоснование формулы Стирлинга.

М.В. Федорюк, Метод перевала. — 1977. — С. 366.

2. Концентрация меры на сфере.

Blum A., Hopcroft J., Kannan R. Foundations of data science. – Cambridge University Press, 2020.
В.А. Зорич, Математический анализ задач естествознания. М.: МЦНМО, 2018.
V.D. Milman. The heritage of P. Lévy in geometrical functional analysis

3. Случайные перестановки и их свойства
4. Концентрация TSP в задаче метрического коммивояжера на квадрате. (без доказательств)

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

5. Неравенство Талаграна (просто упоминание)

Алон Н., Спенсер Д. Вероятностный метод. – Бином, 2007.

6. Теорема Джонсона-Линденштраусса.

Blum A., Hopcroft J., Kannan R. Foundations of data science. – Cambridge University Press, 2020.

7. Вероятностная проверка тождеств.

Н.Н Кузюрин, С.А. Фомин, Эффективные алгоритмы и сложность вычислений. М. МФТИ, 2019
7. Большие системы (макросистемы).

1. Теорема Клартага (только формулировка)

Klartag B. A central limit theorem for convex sets //Inventiones mathematicae. – 2007. – V. 168. – №. 1. – P. 91-131.

2. Предельные формы (диаграммы Юнга, Ричардсона, выпуклые ломаные)

Выступление А.М. Вершика в ЛШСМ 2008
Коралов Л. Б., Синай Я. Г. Теория вероятностей и случайные процессы. М.: МЦНМО. – 2013.

3. Модели роста сетей (типа интернета) на принципе предпочтительного присоединения

Blum A., Hopcroft J., Kannan R. Foundations of data science. – Cambridge University Press, 2020.

4. Эволюция РНК и генетические алгоритмы

Редько В. Г., Цой Ю. Р. Оценка эффективности эволюционных алгоритмов //Доклады Академии наук. – 2005. – Т. 404. – №. 3. – С. 312-315.

5. Время достижения ускоренного консенсуса снизу оценивается диаметром графа и квадрат этого времени отвечает времени выхода сопряженной марковской цепи на стационарное (инвариантное) распределение

Gorbunov E. et al. Recent theoretical advances in decentralized distributed convex optimization //High-Dimensional Optimization and Probability. – Springer, Cham, 2022. – P. 253-325.
Decentralized Convex Optimization over Time-Varying Graphs: a Survey

6. Распределение ошибок при решении систем линейных уравнений

Красносельский М. А., Крейн С. Г. Замечание о распределении ошибок при решении системы линейных уравнений при помощи итерационного процесса //Успехи математических наук. – 1952. – Т. 7. – №. 4 (50. – С. 157-161.

7. Равновесия макросистем, как аттракторы в моделях стохастической химической кинетики. Пример «Кинетика социального неравенства»

Стохастический анализ в задачах. под ред. А.В. Гасникова

8. Метод перевала. Элементы ТФКП. Формула Коши. Получение оценок больших уклонений (теорема Крамера) с помощью метода перевала.

А.Н. Соболевский Конкретная теория вероятностей МЦНМО

9. Игрушечная модель эволюции Д. Кьялво - степенной закон распределения частоты лавин от длительности (связь с временем первого возвращения случайного блуждания)

Пер Бак. Как работает Природа: Теория самоорганизованной критичности. Пер. с англ. №66. Изд. 2 Как работает природа: Теория самоорганизованной критичности. Пер. с англ. URSS. 2022. 288 с.
8. Машинное обучение с точки зрения стохастической оптимизации.

1. Multilevel Monte Carlo
2. HyperLogLog счетчик
3. Машинное обучение с точки зрения стохастической оптимизации

Shalev-Shwartz S., Ben-David S. Understanding machine learning: From theory to algorithms. – Cambridge university press, 2014.
9. Распределенная оптимизация.

1. Методы распределенной оптимизации, использующие сжатие
2. Методы распределенной оптимизации, учитывающие data similarity

10. Математика больших данных в теории информации.

1. Основные определения теории информации: энтропия и взаимная информация
2. Неравенство обработки данных и неравенство Фано
3. Типичные последовательности, их роль в задачах кодирования источника и передачи информации
4. Метод случайного кодирования (вероятностный метод) и его применение в задаче сжатия измерений (англ. compressed sensing)

Y. Polyanskiy, “A perspective on massive random-access,” IEEE Information Theory (ISIT), 2017.
I. Zadik, Y. Polyanskiy, and C. Thrampoulidis, “Improved bounds on Gaussian MAC and sparse regression via Gaussian inequalities,” IEEE International Symposium on Information Theory (ISIT), 2019
11. Малоранговая аппроксимация матриц.

1.Скелетное и сингулярное разложения матриц.
2.Псевдоскелетная (CUR) аппроксимация.
3.Оптимизационные методы (ALS, риманова оптимизация).

12. Малоранговая аппроксимация тензоров.

1.Каноническое разложение.
2.Разложение Таккера.
3.Тензорные сети.

13. Математика обучения с подкреплением.

1. Базовые понятия: марковский процесс принятия решений, уравнения Беллмана, онлайн обучение с подкреплением и регрет. Похожее изложение
2. Exploration-Exploitation дилемма. Алгоритм UCRL
3. Более эффективное исследование: Алгоритм UCBVI

4. Методические и оценочные материалы

Задания для практических занятий:


п/п
Наименование раздела
дисциплины (модуля)
Перечень рассматриваемых тем (вопросов)
Проект 1. Reinforcement Learning / AMDP (теоретический).

В современном обучении с подкреплением в плане теории уже довольно много сделано. Однако для average-reward (AMDP) постановок в теории есть зазор между нижними и верхними оценками. Предлагается в целом изучить RL сквозь призму современной стох. оптимизации (см. в этой связи презентацию, прикрепленную у описанию и цитированную литературу) и сконцентрироваться именно на AMDP. Итогом здесь должно быть написание некоторого небольшого (7-10 страниц) текста-отчета (лучше всего, сделанного в оверлифе), в котором описывается state-of-the-art результаты (теоретические) по AMDP постановкам. Отмечу, что в презентации содержатся не все нужные ссылки (например, нет вот этой), и отчасти работа заключается в поиске таких теоретических работ, в которых есть интересные продвижения.

Проект 2. Поиск вектора Page Rank.

Изучите статьи Вокруг степенного закона распределения компонент вектора PageRank, Efficient Numerical Methods to Solve Sparse Linear Equations with Application to PageRank (тут есть пример, откуда можно брать данные). Попробуйте реализовать метод MCMC и еще парочку приглянувшихся методов для задачи поиска вектора PageRank. Определите, какой метод и в каком смысле лучше работает. Итогом здесь должен быть colab ноутбук с кодом и хорошими комментариями, поясняющими полученные результаты.
Примеры сделанного проекта

Проект 3. Градиентный клиппинг.

Посмотрите вот это видео. В различных моделях обучения возникают задачи стохастической оптимизации, в которых у градиентов имеются тяжелые хвосты. Для лучшей практической работы стандартных методов типа SGD и их моментных вариантов используется клиппирование (пробатченного) стохастического градиента. Такой проект мы делали летом 2022 года со школьниками в Сириусе. В результате было сделано следующее (стоит делать поправку, что это делали школьники 8-10 классов):

Лендинг
GitHub
PyPi
Флайер

Оказывается, для выпуклых задач есть довольно симпатичная математика, стоящая за всем этим: Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise, Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise (совсем идейно это описано в самом начале презентации, прикрепленной к описанию).
Проект практический и заключается в подборе новых примеров (классов) задач обучения (в том числе состязательного обучения), на которых клиппированные методы работают лучше неклипированных. На самом деле, чтобы не заниматься перебором, как раз важно понять, какой эффект дает клипирование и в каких ситуациях это все может себя проявить. Естественно, на практике размер клипа и батча, возможно, придется подбирать не совсем так как в теории, но в целом, некоторые общие закономерности теоретические результаты дают, по-видимому, правильные, и разумно это использовать, чтобы сократить перебор в подборе этих параметров.

Проект 4. Градиентный клиппинг.

В цикле статей Вершика-Синая-Арнольда исследуются различные предельные формы (например, диаграмм Юнга, выпуклых ломаных и т.п.). Вообще, все это очень красиво, и в своей основе имеет целый ряд фундаментальных законов природы, проявляющихся и в целом ряде других областей. Например, в статистической физике. Для погружения в данную проблематику можно рекомендовать мини-курс А.М. Вершка из трех лекций. Некоторые такие примеры разобраны в книге (см. также цитированную там литературу). Искать можно как раз по фамилиям (Вершик, Синай). Целью данного проекта является разбор того, почему имеет место наблюдение, описанное в скрине. В результате работы над проектом должен появиться текст, обосновывающий результат со скрина.
Q1.png

Проект 5. Как зародилась жизнь? Генетические алгоритмы, Мир РНК.

Вопрос «как зародилась жизнь?» давно привлекает к себе внимание ученых из разных областей. Текущее понимание этого вопроса изложено в замечательной книге А.А. Маркова «Рождение сложности». Хотя до сих пор нет одной какой-то общепринятой точки зрения, но все же наиболее популярна гипотеза о том, что жизнь могла зародиться из самокопирующихся молекул РНК (гипотеза РНК мира). Обоснование гипотезы требует проработки разных (в том числе чисто математических) вопросов. Замечательно здесь и то, что можно пойти и в обратном направлении (а именно, эволюция/естественный отбор может подсказать способ решения той или иной сложной задачи оптимизации, функционал которой интерпретируется как приспособленность). Собственно, это и предлагается сделать. Решите задачу 16 на стр. 175-176. Требуется математически строго обосновать решение и подкрепить теорию результатами численных экспериментов.

Проект 6. Вокруг методов Монте-Карло, в том числе с приложениями к финансовой математике.

Посмотрите часть 1 и часть 2 видео «В окрестностях Монте-Карло» и попробуйте на базе прослушанного предложить какие-то свои вариации классических методов. Проект очень неопределенный. Это сделано специально, чтобы дать больше свободы творчества. Также было бы здорово обратить внимание, что для целого ряда вещей совсем не нужна первозданно случайная последовательность. В частности, на практике эффективными оказываются так называемы квази Монте-Карловские методы, под которые есть хорошая теория.

Цель данного проекта — знакомство с современными приложениями методов Монте-Карло. В частности, для тех, кто хочет посмотреть в сторону финансовой математике можно рекомендовать в качестве проекта выбрать Multi-level Monte Carlo. А именно, проект заключается в том, чтобы аккуратно обосновать (с нужной теорией и желательно демонстрацией на практике) то, что написано в условиях задачи 22 на стр. 204-205. Для погружения в финансовую математику есть очень доступный курс.

Проект 7. Ранняя остановка или регуляризация.

Одной из главных проблем машинного обучения является переобучение. Это давно и хорошо известно, и много чего в этой связи было сделано. Если совсем кратко резюмировать, то для задач обучения с выпуклым целевым функционалом (логистическая регрессия, SVM, LASSO, …) основные способы борьбы с переобучением — это регуляризация или ранняя остановка процедур типа SGD. На базе первой главы книги по Алгоритмической стох. оптимизации (ссылка здесь дублируется - имеется в прикрепленном сообщении) попробуйте сделать обзор описанных двух подходов и продемонстрируйте как все это работает на практике. В чем преимущества и недостатки этих двух подходов друг перед другом? Итогом работы по проекту должен стать текст + эксперименты. То есть в этом проекте важны обе составляющие (практическая и теоретическая).

Проект 8. Модели распространения эпидемий, в частности, ковид как модель стохастической химической кинетики.

Изучите главу 6. В частности, модель Эренфестов, модель хищник-жертва и ее распределенные варианты. Попробуйте на базе похожего формализма получить систему дифференциальных уравнений SIR-типа моделей и предложите свои обобщения. Для дополнительной мотивации можно посмотреть мультфильм.
Результатом работы по проекту может быть описание микроскопической динамики, которая в макромасштабе описывается чем-то типа SIR-моделей или их обобщений. При этом обоснование должно быть как теоретическое, так и практическое.

Проект 9. Почему зависимости частот катастроф от их масштабов имеют степенной закон?

Изучите задачу Д. Кьялво (задача 12 на стр. 170-171). Попробуйте не только экспериментально проверить то о чем написано в задаче (естественно, в большем масштабе, чем было в эксперименте, который делал Д. Кьялво над своими студентами), но и обосновать это теоретически. Проект также включает в себя текст, с теоретической проработкой, и эксперименты.

Проект 10. Почему большинство крупных мегаполисов живут в режиме пробок, фазовый переход в сетях массового обслуживания.

Этот проект совершенно реален (то есть идею этого проекта воплотили в жизнь при планировании развития сети общественного транспорта в г. Москве за последние 10-15 лет). Вот краткое описание проблематики (ключевой тут рис. 1). Немного есть про это вот в этом видео (в концовке как раз об этом, впрочем, начало тоже интересное, но не об этом). Речь идет о том, что большинство крупных мегаполисов живут в режимах, когда есть и много пробок. Почему это так? Математическое объяснение есть в книге (см. приложение Малышева-Замятина). Собственно, эта тема дальше развивается в Исследовательской задаче (такой раздел есть в книге) «Задача о критическом числе автомобилей для заданного города». Предложите свой вариант такого типа задачи и получите практическое подтверждение наличия фазового перехода. Проект практический.

Проект 11. Четыре рукопожатия и как это посчитать?

В замечательной книге Райгородского-Литвак совсем по-простому рассказано о том, как современные социальные сети решают различные задачи подсчета (см. сюжет из Главы 7 Счетчики с короткой памятью и в частности Четыре виртуальных рукопожатия). Попробуйте разобрать пример из статьи Себастьяна Виньи на более продвинутом уровне чем в популярной книге Райгородского-Литвак. В частности, помочь может вот эта книга. Цель проекта продемонстрировать математику, которая есть вокруг этого сюжета (в частности, хеширование). Проект теоретический, но чтобы получить по нему хорошую оценку нужно либо довольно тонко освоить теорию, либо провести достаточно понятные эксперименты, подтверждающие теорию...

Проект 12. Межгрупповая вражда способствует внутригрупповому сотрудничеству.

В другой интересной книге А.А. Маркова в главе 5 есть параграф, который называется так как этот проект. Прочитайте параграф, постарайтесь понять о чем идет речь. В параграфе описывается некоторое равновесие макросистемы. Попробуйте придумать каку-то разумную динамику, которая бы приводила к такому равновесию (соответствующие заготовки могут быть почерпнуты из 6 главы книги). Нужно не только придумать, подтвердить экспериментально, но и попробовать математически обосновать, что предложенная динамика, действительно, выходит на нужное равновесие…

P.S. В целом, очень рекомендую эту книгу Маркова, если есть желание получше разобраться как устроены люди. Кажется, в этой книге есть и много других интересных сюжетов (например, парадокс Симпсона, теория Гамильтона — родственного отбора, и многое другое), которые, по-видимому, качественно улавливают какие-то закономерности, управляющие поведением людей.

По итогам этого проекта появилась статья.

Проект 13. Кинетика социального неравенства.

Решите задачу 4 на стр. 154-162. Решение требуется привести математическое. Это один вариант сдачи проекта. Второй вариант — предложить свои вариации модели обмена монетками, которые приводят к более интересным асимптотикам. В этом случае обоснование формы предельных кривых может быть схематичным, но желательно тогда подтверждение численными экспериментами.

Проект 14. Двойной спуск, сложный проект!

В последние годы в задачах обучения наблюдается довольно интересный эффект, что если модель сильно переобучена, то U-образная кривая снова начинает убывать. Математика этого эффекта еще далека от своего окончательного объяснения, но все же попытки это объяснить имеются. В том числе довольно компактные. Более того, все эти вопросы оказываются завязанными на так называемое условие Поляка-Лоясиевича (градиентного доминирования). К сожалению, на данный момент неизвестны нижние оценки для гладких задач оптимизации в условиях Поляка-Лоясиевича. При том, что много интересных результатов о сходимости градиентного типа методов (в том числе и их стохастических вариантов) есть. Проект, по-видимому, достаточно сложный. Целью проекта является продвинуться в понимание, какие нижние оценки имеют место для методов типа градиентного спуска в условиях Поляка-Лоясиевича. Гипотеза, что имеющиеся верхние оценки оптимальны. То есть ускорения в условиях Поляка-Лоясиевича нет. Проблема тут с использованием стандартной техники получения нижних оценок упражнения 1.3 и 2.1. Нужно найти подобную плохую функцию, удовлетворяющую условию Поляка-Лоясиевича. Ну или как-то еще посмотреть на эту задачу.

Проект 15. Гамильтоновы пути и концентрация меры.

Хорошо известно, что задача поиска гамильтонова пути — NP-трудна. А именно, трудной является задача почтальона: в каком порядке надо обойти дома на своем участке и вернуться в отделение почты (откуда и стартует маршрут), чтобы суммарная длина пути была бы минимальна? Конечно, метрический коммивояжер уже немного попроще (веса ребер графа отвечают некоторой топологии реальной дорожной сети, скажем на плоскости), чем общая задача. Все равно эта задача остается сложной и улучшается у нее только различные аппроксимационные характеристики. Представим себе, что теперь у нас город — это квадрат со стороной 1. В городе n домов. Все дома случайно и независимо построены (дом - это точка в квадрате, обе координаты которой выбираются независимо и из равномерного распределения). Обозначим длину кратчайшего (гамильтонового) пути в таком графе через TSP(n). Это будет случайная величина. Покажите, что TSP(n) экспоненциально концентрируется около своего математического ожидания, пропорционального \sqrt{n}. Указание: Используйте книгу.

Проект 16. Устойчивые системы большой размерности.

Попробуйте решить задачу
Q2.png

Проект 17. О типично худшем накоплении ошибки в линейных итерационных методах.

Попробуйте решить задачу
Q3.png
Пример сделанного проекта

Проект 17 от Максима Рахубы. Использование тензорных сетей для сжатия и восстановления изображений.

В этом проекте предлагается познакомиться с тензорными сетями (обобщение матричных факторизаций на многомерный случай и их приложением для задач восстановления изображения по значениям в небольшом числе пикселей (tensor completion), а также для сжатия изображений. Для конкретики можно рассмотреть тензорные сети PEPS, тензорное кольцо и/или тензорный поезд. Для решения задач минимизации можете использовать несколько методов оптимизации на свой выбор, а также реализовать метод попеременных наименьших квадратов (ALS) (только для задачи сжатия). Для более детального ознакомления с постановкой задачи и одним из возможных алгоритмов прочитайте статью и ознакомьтесь с сайтом. В качестве фреймворка для написания проекта можно воспользоваться пакетом или альтернативными вариантами. Результатом работы по проекту должна стать jupyter тетрадка (можно ссылкой в colab), с кодом, кратким описанием используемых алгоритмов, а также графиками ошибки и значений PSNR от числа параметров в тензорных сетях для нескольких изображений.
По поводу вопросов пишите в ТГ @mrakhuba.

Проект 18 от Максима Рахубы. Методы римановой оптимизации и их приложение для рекомендательных систем.

Известно, что множество матриц фиксированного ранга является римановым многообразием. Эту информацию можно использовать для построения эффективных методов поиска малоранговых приближений матриц. В этом проекте предлагается познакомиться с методами римановой оптимизации, реализовать риманов метод сопряженных градиентов, а также воспользоваться им для минимизации l1 нормы ошибки. В качестве приложения предлагается построить рекомендательную систему. Результатом работы по проекту должна стать jupyter тетрадка (можно ссылкой в colab), с кодом, кратким описанием используемых алгоритмов, а также графиками зависимости RMSE и одной из релевантных для рекомендательных систем метрик в зависимости от ранга.

По поводу вопросов пишите в ТГ @mrakhuba.

Проект 19 от Алексея Фролова. Граница случайного кодирования для задачи сжатия измерений массового некоординированного множественного доступа.

В работе [1] введена теоретико-информационная модель массового некоординированного множественного доступа и получена граница случайного кодирования, которую можно применять как в асимптотическом, так и неасимптотическом режимах. Улучшение для асимптотического режима предложено в работе [2] с использованием леммы Гордона (Gordon’s lemma) о минимуме гауссовского процесса. Задача данного проекта заключается в получении неасимптотической версии границы из [2]. Также разрешается применять любые другие методы уточнения аддитивной границы из [1], например, предложенную на лекции локальную лемму Ловаша.
1. Y. Polyanskiy, “A perspective on massive random-access,” IEEE Information Theory (ISIT), 2017.
2. I. Zadik, Y. Polyanskiy, and C. Thrampoulidis, “Improved bounds on Gaussian MAC and sparse regression via Gaussian inequalities,” IEEE International Symposium on Information Theory (ISIT), 2019

Контрольные вопросы для подготовки к промежуточной аттестации:

Для ознакомления доступна контрольная работа

Перечень учебно-методического обеспечения дисциплины

Список основной литературы:
1. Blum A., Hopcroft J., Kannan R. Foundations of data science. – Cambridge University Press, 2020.
2. Bach F. Learning Theory from First Principles. – 2021.
3. Тыртышников Е. Е. Методы численного анализа. – 2007.
4. Зорич В. Математический анализ задач естествознания. – Litres, 2018.

Список дополнительной литературы:
1. Гyдфеллоy Я., Бенджио И., Кyрвилль А. Глyбокое обyчение. 2-е изд., исправл. М.: ДМК-Пресс, 2018.
2. Shapiro A., Dentcheva D., Ruszczyński A. Lectures on stochastic programming: modeling and theory. – Society for Industrial and Applied Mathematics, 2014.
3. Shalev-Shwartz S., Ben-David S. Understanding machine learning: From theory to algorithms. – Cambridge university press, 2014.
4. Bubeck S. Convex optimization: Algorithms and complexity // Foundations and Trends® in Machine Learning Volume 8 Issue 3-411 pp 231–357. – 2015.
5. Duchi J. C. Introductory lectures on stochastic optimization // The mathematics of data. – 2018. – V. 25. – P. 99-185.
6. Hazan E. Lecture notes: Optimization for machine learning // arXiv preprint arXiv:1909.03550. – 2019.
7. Lan G. First-order and Stochastic Optimization Methods for Machine Learning. – Springer Nature, 2020.
8. Milman V. D. The heritage of P. Lévy in geometrical functional analysis //Astérisque. – 1988. – Т. 157. – №. 158. – С. 273-301.
9. Shen A., Romashchenko A., Rumyantsev A. Y. Заметки по теории кодирования. – 2017.
10. Vershynin R. High-dimensional probability: An introduction with applications in data science. – Cambridge university press, 2018. – Т. 47.

Методические указания для обучающихся по освоению дисциплины

Вид учебных
занятий/деятельности
Деятельность обучающегося
Лекция Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Подготовка к промежуточной аттестации При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей.
Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
Контрольная работа При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
Выполнение домашних заданий и групповых проектов Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.

Методы и технологии обучения, способствующие формированию компетенции

Методы и технологии обучения, способствующие формированию компетенции
В курсе планируется использовать несколько технологий обучения. Таких как: интерактивные лекции , поощряющие участие студентов посредством сессий вопросов и ответов или групповых дискуссий.

Проблемно-ориентированное обучение – мероприятия по решению проблем, которые побуждают студентов применять концепции курса в практических ситуациях. Этот метод может улучшить навыки критического мышления и закрепления знаний.


Планируется предложить совместные проекты , которые требуют применения концепций курса в реальных сценариях. Такой подход может способствовать командной работе, навыкам общения и креативности, одновременно углубляя понимание студентами концепций курса.

Важный элемент курса – смешанное обучение : сочетание традиционного очного обучения с онлайн-учебными ресурсами, такими как видео, симуляторы или интерактивные викторины. Такой подход может учитывать различные стили обучения и предпочтения, одновременно улучшая понимание учащимися концепций курса.