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

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

Билеты к зачету  по курсу "Игры с предсказаниями экспертов и повторяющиеся игры", 2016г. Семестр 2.

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

Билеты. к экзамену по курсу «Математические основы   машинного обучения», Вьюгин ВВ, 2016г.
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.    Постановка задачи предсказания с использованием экспертных стратегий. Алгоритм WMA, оценка числа его ошибок.
20.    Алгоритм Hedge оптимального распределения потерь. Оценки его регрета.
21.    Алгоритм AdaBoost. Схема применения алгоритма. Оценка его ошибки.
22.    Постановка задачи нахождения оптимального решения с использованием экспертных стратегий при наличии функции потерь. Алгоритм экспоненциального взвешивания экспертных решений для выпуклой функции потерь. Оценка его регрета.
23.    Агрегирующий алгоритм Вовка. Схема алгоритма. Псевдоалгоритм. Вычисление предсказаний. Основная лемма про псевдоалгоритм.
24.    Виды функций потерь: абсолютная, квадратичная, логарифмическая. Множества предсказаний и псевдопредсказаний в основном и экспоненциальном пространстве. Смешиваемые функции потерь. Построение предсказания агрегирующего алгоритма для квадратичной и логарифмической функции потерь. Доказательство смешиваемости для этих функций.
25.    Агрегирующий алгоритм для бесконечного множества экспертов (с доказательствами). Смешиваемость. Постановка задачи построения портфеля. Построение универсального портфеля (финансового инструментов) Ковера. Доказательство оценок его эффективности.

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

Провести обучение и классификацию массива данных из базы 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)
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Билеты 2016г. Семестр 2. Игры с предсказаниями экспертов и повторяющиеся игры
1.    .Алгоритм WMA взвешенного большинства (экспертов). Оценка числа ошибок. Постановки задачи предсказания с использованием экспертных стратегий: 1) для потерь общего вида; 2) для функции потерь. Понятие регрета.
2.    Постановки задачи предсказания с использованием экспертных стратегий: 1) для потерь общего вида; 2) для случая, когда потери задаются в виде функции потерь. Понятие регрета алгоритма. Алгоритм Hedge оптимального распределения потерь в режиме онлайн. Оценка его регрета.
3.    Усиление слабых классификаторов: Бустинг. Алгоритм AdaBoost и его свойства.
4.    Постановки задачи предсказания с использованием экспертных стратегий: 1) для потерь общего вида; 2) для функции потерь. Понятие регрета. Алгоритм экспоненциального взвешивания  экспертных решений. Mixloss и его связь с оценкой потерь и регрета.
5.    Агрегирующий алгоритм Вовка: конечное множество экспертов. Смешиваемые функции потерь.
 логарифмическая, квадратичная, вычисление предсказаний алгоритма для них.
6.    Агрегирующий алгоритм Вовка для континуума экспертов. Универсальный портфель акций Ковера.  Алгоритм вычисления портфеля. Оценка выигрыша данного портфеля.
7.    Линейная онлайн  регрессия с помощью агрегирующего алгоритма. Основные формулы и оценки потерь.
8.    Последовательные вероятностные предсказания для логарифмической функции потерь. Смешивающий предсказатель. Оптимальный минимаксный предсказатель и его свойства. Префиксно - корректные коды, построение универсального метода сжатия, оценка его избыточности. Эксперты не зависящие от истории. Оценка ошибки для случая двух экспертов.. Игра Келли,  оптимальная стратегия, оценка ошибки. Правило Лапласа  (для бесконечного числа экспертов), оценка ошибки.
9.    Задача универсального предсказания в режиме онлайн. Тестирование предсказаний (Пример: предсказатель погоды). Калибруемость предсказаний по Дэйвиду. Случайное округление. Вероятностный алгоритм построения калибруемых предсказаний для произвольной последовательности исходов. Калибруемость с ядром.
10.    Выпуклая онлайн оптимизация: постановка задачи. Алгоритм градиентного спуска с переменным параметром обучения. Оценка его регрета.
11.    Онлайн зеркальный спуск. Постановка задачи. Расстояние Брегмана и его свойства. Преобразование Лежандра. Алгоритм зеркального спуска. Оценка его регрета. Частные случаи: градиентный спуск, экспоненциальное взвешивание.
12.    Предсказания с экспертами в условиях ограниченной информации (Задача о многоруком бандите). Вероятностный алгоритм Exp3 и оценка его регрета.
13.    Элементы теории игр. Антагонистическая игра двух лиц с нулевой суммой. Верхняя и нижняя цена игры. Седловая точка. Достаточное условие существования седловой точки. Смешанное расширение игры. Минимаксная теорема Дж. Фон Неймана (доказательство на основе теории предсказаний с экспертами). Чистые стратегии и минимаксная теорема. Решение игр типа (2xM).
14.    Бесконечно повторяющиеся игры. Состоятельные по Ханнану стратегии. Построение такой стратегии для игры двух лиц с нулевой суммой на основе методов предсказания с экспертами.
15.    Бесконечно повторяющиеся игры. Теоремы 1 и 2 Блекуэлла о достижимости. Применения для построения состоятельной по Ханнану онлайн стратегии.
16.    Применение теоремы Блекуэлла для построения  калибруемых предсказаний в случае конечного числа исходов. Игра с конечным числом игроков, платежные функции, виды стратегий игроков. Равновесие Нэша, коррелированное равновесие Аумана.  Построение онлайн стратегии для повторяющейся игры, при которой частотное распределение ходов игроков сходится к коррелированному равновесию.
17.    Теоретико - игровая формулировка теории вероятностей, доказательство усиленного закона больших чисел.  Теоретико-игровая вероятность. Игра Бернулли.
Литература
1.    Вьюгин В.В.. Математические основы машинного обучения и прогнозирования. – М.: МЦНМО, 2013. (имеется также расширенная онлайн версия, http://iitp.ru/upload/publications/7241/vyugin1.pdf)
2.    Cesa-Bianchi, Lugosi Prediction, Learning and Games, Cambridge university press, 2006
3.    Cover, T., Thomas, J. Elements of information theory, Wiley

 

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

Билеты к экзамену по курсу"Колмогоровская сложность и ее приложения", Вьюгин ВВ г.

I. Определение колмогоровской сложности и ее свойства.

1. Алфавиты, конструктивные объекты, кодирование натуральных чисел, пар, троек строк. Понятие алгоритма, вычислимые функции, Формализация понятия алгоритма: вычислимые функции, машины Тьюринга и др. Идея построения универсальной машины Тьюринга. Универсальная функция. Перечислимые и разрешимые множества. Пример перечислимого и неразрешимого множества. Проблема остановки.

2. Простая колмогоровская сложность. Теорема инвариантности (теорема существования). Простейшие свойства колмогоровской сложности. Невычислимость сложности. Верхние оценки сложности. Теорема о неполноте.

3. Сложность пары конечных объектов. Условная сложность. Теорема Колмогорова -- Левина о сложности пары.

4. Количество информации. Свойство симметричности функции информации. Энтропия Шеннона. Связь сложности и энтропии Шеннона. Простейший закон больших чисел.

II. Случайные последовательности

6. Конструктивный анализ теории вероятностей. Пространство бесконечных двоичных последовательностей, задание мер на нем. Вычислимые меры. Эффективно нулевые множества. Существование максимального по включению эффективно-нулевого множества. Случайность по Мартин-Лефу. Примеры эффективно нулевых множеств..

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

8. Безпрефиксные методы кодирования. Префиксная сложность, ее существование и свойства. Обобщенное  неравенство Крафта.

9. Перечислимые множества и предельно вычислимые функции. Априорная полумера на конечных последовательностях и ее связь с префиксной сложностью. Префиксные машины Тьюринга (машины с самоограниченным входом). Соотношение между префиксной и простой колмогоровской сложностью.  Различные верхние и нижние оценки для префиксной сложности.

10. Условная префиксная сложность. Представление префиксной сложности пары. Количество информации и префиксная сложность. Симметричность функции информации.

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

12. Эквивалентные определения случайной по Мартин-Лефу последовательности с помощью префиксной и монотонной сложности (теорема Левина -- Шнорра).

13. Вычислимые меры. Определение последовательности случайной по Мартин-Лефу относительно произвольной вычислимой меры. Теорема Левина-Шнорра для последовательностей, случайных относительно произвольных вычислимых мер. 

14. Априорная перечислимая полумера на дереве двоичных последовательностей, ее построение и свойства. Связь с монотонной сложностью. Определение случайной последовательности с помощью априорной полумеры. Перечислимые снизу супермартингалы, их интерпретация. Связь с полумерами. Определение случайной последовательности с помощью супермартингала..

15. Универсальный предиктор Соломонова: определение и доказательство его асимптотической состоятельности.

III. Алгоритмические вопросы теории вероятностей - в 2013г. не входит в курс.

16. Сложностное доказательства закона закона повторного логарифма.

17. Основные понятия эргодической теории. Теорема Пуанкаре о возвращении для случайных последовательностей.

18. Эргодическая теорема Биркгофа: отсутствие вычислимой оценки скорости сходимости по вероятности.

19. Интегральные тесты случайности. Определение случайности по Мартин-Лефу с помощью интегральных тестов.

20. Эргодическая теорема Биркгофа для случайных по Мартин-Лефу последовательностей (формулировка и доказательство).

 

Список литературы

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

http://www.iitp.ru/upload/publications/6027/vyugin_kolm.pdf 

2. В.А.Успенский, Н.К.Верещагин, А.Шень Колмогоровская сложность и алгоритмическая случайность М.: МЦНМО, 2010, 556с. . Доступно онлайн:   http://www.lif.univ-mrs.fr/~ashen/nafit/kolmbook.pdf

 

4. Li M., Vitanyi P. An Introduction to Kolmogorov Complexity and Its Applications, 2nd ed. New  York: Springer--Verlag, 1997.

5. V"yugin V.V. Algorithmic complexity and  stochastic properties of finite binary sequences.     The Computer Journal, 1999, v.42, N4, p.294--317. Доступно онлайн:   http://www.iitp.ru/upload/publications/1629/surv3.pdf

6. Колмогоров А.Н. Три подхода к определению  понятия <<количество нформации>>.  Проблемы передачи  информации, 1965, т.1, N1, с.3--11.

 

Контроль: Зачет и Экзамен

Для получения зачета и допуска к зачету необходимо сдать задачи (в письменном виде) из файла (см. ниже).

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

Сроки  сдачи 23 и 25 декабря 2013г. г.Долгопрудный,  в 9-45, сбор у ауд.123  

Задачи http://www.iitp.ru/upload/userpage/143/problem.pdf  до 1 ноября 2013г.

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

Консультация 12 и 19 декабря 2013г. в 9-45

 

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

 

 

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