Войти
Логин:
Пароль:
Забыли пароль?
научная деятельность
структура институтаобразовательные проектыпериодические изданиясотрудники институтапресс-центрконтакты
русский | english

Билеты по курсу «Математические основы  машинного обучения», Вьюгин ВВ, Семестр 2, 2017г.

Билеты по по курсу "Онлайн методы машинного обучения" Семестр 2 (2019г.) 

Билеты по курсу "Колмогоровская сложность и ее приложения", 2018, Семестр 1

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

Билеты  и задачи к дифф. зачету по курсу «Математические основы  машинного обучения», Вьюгин ВВ, 2019г.

1.    Байесовский классификатор. Персептрон, алгоритм Розенблатта, оценка числа итераций. Постановка задачи восстановления зависимости в теории машинного обучения. Равномерое уклонение ошибки от среднего. PAC-форма неравенств больших уклонений. Задача классификации, постановка задачи, ошибка классификации, эмпирическая ошибка.

2.    Задача классификации, постановка, основные проблемы. Теоремы об оценке предсказательной способности алгоритмов классификации (формулировки). Схема доказательства. Доказательство леммы 1 о симметризации для случая разделения без ошибок.

3.    Теорема об оценке предсказательной способности алгоритмов классификации через функцию роста. Схема доказательства. Доказательство второй леммы.

4.    Определение функции роста класса индикаторных функций и VC-размерности. Лемма Зауэра с доказательством. Примеры классов функций классификации и их VC-размерность.

5.    VC-размерность классов всех линейных и однородных функций в n-мерном эвклидовом пространстве (с доказательствами).

6.    Определение нейронной сети. VC-размерность класса всех нейронных сетей (доказательство леммы о декартовом произведении и композиции, применение к вычислению оценки для нейронных сетей).

7.    Оптимальная разделяющая гиперплоскость, ее существование, единственность и свойства. Разделение без ошибок: постановки задачи, граничные гиперплоскости.

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

9.    Переход к разделению с помощью ядер. Соответствующая оптимизационная задача. Примеры ядер. Ядра и отображения. Их примеры.

10.    Положительно определенные ядра. Гильбертово пространство, порожденное воспроизводящим ядром. Построение канонического гильбертова пространства по положительно определенному ядру. Теорема о представителе.

11.    Задача построения оптимальной разделяющей гиперплоскости для случая неразделимой выборки. Случаи квадратичной и линейной нормы. Свойства опорных векторов для обоих случаев.

12.    Средние по Радемахеру. Основная теорема о равномерной оценке разности между выборочным средним и математическим ожиданием. Ее следствия.

13.    Среднее по Радемахеру и функция роста: неравенство между ними.

14.    Неравенство Хефдинга. Основная форма неравенства с доказательством. Вывод неравенства Чернова.

15.    Определение мартингал-разности. Неравенство Адзумы – Хефдинга с доказательством. Мартингальный закон больших чисел.

16.    Неравенство Мак-Диармонда с доказательством. Его следствия для равномерной оценке разности между выборочным средним и математическим ожиданием.

17.    Среднее по Радемахеру и оценка ошибки обобщения для классификаторов из RKHS в общем случае разделения с ошибками.

18.    Постановка задачи предсказания с использованием экспертных стратегий. Алгоритм взвешенного большинства. Оценка числа ошибок. Постановка   задачи предсказания с использованием экспертных стратегий. Алгоритм WMA, оценка числа его ошибок. Алгоритм Hedge оптимального распределения потерь. Оценки его регрета.

19.    Алгоритм AdaBoost. Схема применения алгоритма. Оценка его ошибки.

20.   Теория алгоритмов экспоненциального смешивания. Mixloss, связь кумулятивного mixloss-а и потерь алгоритма Hedge. Алгоритм Hedge с переменным параметром обучения.

Лабораторная работа

Провести обучение и классификацию массива данных из базы UCI repository http://archive.ics.uci.edu/ml/

Использовать какую-нибудь стандартную программу SVM. Представить отчет этой программы о числе ошибок на обучающей и тестовой выборках.

Задачи (сдать большую часть в тетради).

Привести примеры ядер и соответствующих RKHS и отображений.

Вычислить VC-размерность класса всех характеристических функций множеств {A: |A|<=k}, A – подмножества некоторого фиксированного бесконечного множества (см. книгу раздел 1.6).

Вычислить VC-размерность класса функций {sign(sin(tx)):t\in R} (см. книгу раздел 1.6).

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

Почему при построении оптимальной разделяющей гиперплоскости с ошибками в линейной норме хотя бы один опорный вектор лежит на граничной гиперплоскостях и для него коэффициент Лагранжа больше 0.

Привести примеры ядер и соответствующих RKHS и отображений.

Доказать, что экспонента K(x,y)=exp(-xy) и гауссова функция K(x,y)=exp(-|x-y|^2).являются положительно определенными (т.е. ядром). (см. задачу 6 из книги). Как устроено соответствующее каноническое RKHS. (см. книгу раздел 1.6).

Литература

1.    Вьюгин В.В.. Математические основы машинного обучения и прогнозирования. – М.: МЦНМО, 2013. (имеется также расширенная онлайн версия, http://iitp.ru/upload/publications/7241/vyugin1.pdf)

 

Билеты 2019г. Семестр 2. 

«Онлайн методы машинного обучения» Семестр 2 (2019г.)

Исторические алгоритмы

Алгоритм WMA взвешенного большинства (экспертов). Оценка числа ошибок.

Постановки задачи предсказания с использованием экспертных стратегий: 1) для потерь общего вида; 2) для функции потерь. Понятие регрета.

Алгоритм Hedge Фройнда и Шапире оптимального распределения потерь в режиме онлайн. Оценка его регрета.

Усиление слабых классификаторов: Бустинг (на основе алгоритма Hedge). Алгоритм AdaBoost и его свойства.

Онлайн выпуклая оптимизация

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

Регуляризация. Алгоритм следования за регуляризованным лидером. Применение к линейной оптимизации. Алгоритм онлайн градиентного спуска. Оценка его регрета.

Линеаризация выпуклых функций. Алгоритм градинтного спуска с переменным параметром обучения (Алгоритм Зинкевича)..

Строго выпуклые функции и строго выпуклая оптимизиция. Примеры регуляризаторов: эвклидов регуляризатор, энтропийный регуляризатор.

Оценки регрета алгоритма следования за регуляризованным лидером для строго выпуклого регуляризатора. Оценки для случая эвклидова регуляризатора и энтропийного регуляризатора.

Онлайн зеркальный спуск в упрощенном виде. Алгоритм и оценка его регрета. Частные случаи: онлайн градиентный спуск и алгоритм экспоненциального смешивания.

Расстояние Брэгмана и его свойства. Преобразование Лежандра - Фенхеля. Алгоритм зеркального спуска. Оценка его регрета. Частные случаи: градиентный спуск, экспоненциальное взвешивание.

Логарифмическая оценка регрета для строго выпуклой функции потерь.

Предсказания с использованием экспертных стратегий (Prediction with Expert Advice). Алгоритмы экспоненциального смешивания.

Постановки задачи предсказания с использованием экспертных стратегий: 1) для потерь общего вида; 2) для функции потерь. Понятие регрета. Алгоритм экспоненциального взвешивания экспертных решений. Mixloss и его связь с оценкой потерь и регрета.

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

Состоятельность по Ханнану.

Схемы смешивания апостериорных распределений экспертов Буске и Вармута. Оценка регрета. Алгоритм Fixed Share и оценка его регрета. Связь алгоритма Sixed Shsre и алгоритма Hedge.

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

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

Агрегирующий алгоритм Вовка для континуума экспертов. Универсальный портфель Ковера. Алгоритм вычисления портфеля. Гарантийная оценка выигрыша данного портфеля.

Предсказания с экспертами в условиях ограниченной информации (Задача о многоруком бандите). Вероятностный подход: алгоритм USB и оценка регретаПредсказания с экспертами в условиях ограниченной информации (Задача о многоруком бандите). Минимаксный случай: алгоритм Exp3 и оценка его регрета.

Прогнозирование индивидуальных последовательностей.

Задача универсального предсказания в режиме онлайн. Тестирование предсказаний (Пример: предсказатель погоды). Калибруемость предсказаний по Дэйвиду. Случайное округление. Вероятностный алгоритм построения калибруемых предсказаний для произвольной последовательности исходов. Калибруемость с ядром.

Бесконечно повторяющиеся игры

Элементы теории игр. Антагонистическая игра двух лиц с нулевой суммой.Верхняя и нижняя цена игры. Седловая точка. Достаточное условие существования седловой точки.

Достаточное условие существования решения антогонистической игры (доказательство на основе алгоритма экспоненциального смешивания). Смешанное расширение игры. Минимаксная теорема Дж. Фон Неймана. Чистые стратегии и минимаксная теорема. Решение игр типа (2xM). 

Бесконечно повторяющиеся игры. Состоятельные по Ханнану стратегии. Построение такой стратегии для игры двух лиц с нулевой суммой на основе методов предсказания с экспертами.

Бесконечно повторяющиеся игры. Теоремы 1 и 2 Блекуэлла о достижимости. Применения для построения состоятельной по Ханнану онлайн стратегии.

 

Литература

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

 

Shai Shalev-Shwartz Online Learning and Online Convex Optimization. Foundations and Trends in Machine Learning Vol. 4, No. 2 (2011) 107–194 DOI: 10.1561/2200000018

 

Sґebastien Bubeck and Nicol`o Cesa-Bianchi. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Foundations and Trends in Machine Learning Vol. 5, No. 1 (2012) 1–122. DOI: 10.1561/2200000024

 

Cesa-Bianchi, Lugosi Prediction, Learning and Games, Cambridge university press, 2006

 

Cover, T., Thomas, J. Elements of information theory, Wiley

 


Контроль: Зачет с оценкой

Студенты с высокой оценкой самостоятельной работы (список объявлен на прошлых занятиях) сдают только теорию по билетам.

Остальные студенты, которые сдавали самостоятельные работы, но не вошли в список, получают дополнительно задачи.

Все  остальные для получения допуска к зачету предварительно сдают задачи (в письменном виде) из файла (см. ниже). Надо представить решения для не менее 75% задач.

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

Сроки  сдачи -- г. г.Долгопрудный,  в 9-45

Задачи http://www.iitp.ru/upload/userpage/143/problem.pdf  представить в тетради к зачету..

Идеи решения задач периодически разбираются на практических занятиях.

-------------------------------------------------------

Дополнительный зачет (по договоренности) по адресу г.Москва Б.Каретный 19, ИППИ РАН, к.413 (4 этаж) 

 

 

  © Федеральное государственное бюджетное учреждение науки
Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, 2019
Об институте  |  Контакты  |  Старая версия сайта