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

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

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

 

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

 

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

Билеты. к экзамену по курсу «Математические основы  машинного обучения», Вьюгин ВВ, 2017г.
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. Последовательные вероятностные предсказания для логарифмической функции потерь. Смешивающий предсказатель. Оптимальный минимаксный предсказатель и его свойства. Префиксно - корректные коды, построение универсального метода сжатия, оценка его избыточности. Эксперты не зависящие от истории. Оценка ошибки для случая двух экспертов.. Игра Келли,  оптимальная стратегия, оценка ошибки. Правило Лапласа  (для бесконечного числа экспертов), оценка ошибки.

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

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

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

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

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

24.    Агрегирующий алгоритм Вовка. Схема алгоритма. Псевдоалгоритм. Вычисление предсказаний. Основная лемма про псевдоалгоритм.

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

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

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

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

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

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

Задачи (сдать большую часть в тетради).
Привести примеры ядер и соответствующих RKHS и отображений.
Доказать, что экспонента K(x,y)=exp(-|x-y|^2).является положительно определенной функцией (т.е. ядром). (см. задачу 6 из книги). Как устроено соответствующее каноническое RKHS. (см. книгу раздел 1.6).
Вычислить VC-размерность класса всех характеристических функций множеств {A: |A|<=k}, A – подмножества некоторого фиксированного бесконечного множества (см. книгу раздел 1.6).
Вычислить VC-размерность класса функций {sign(sin(tx)):t\in R} (см. книгу раздел 1.6).
Почему при построении  оптимальной разделяющей гиперплоскости с ошибками в квадратичной норме ни один опорный вектор не лежит на граничных гиперплоскостях.
Почему при построении оптимальной разделяющей гиперплоскости с ошибками в линейной норме хотя бы один опорный вектор лежит на граничной гиперплоскостях и для него коэффициент Лагранжа больше 0.
Привести примеры ядер и соответствующих RKHS и отображений.
Доказать, что экспонента 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% задач.

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

Сроки  сдачи --13,, 20  декабря 2018г. г.Долгопрудный,  в 9-45, ауд.432 ГК

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

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

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

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

 

 

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