НИС Машинное обучение и приложения — различия между версиями

Текущая версия на 22:26, 16 июня 2016

Таблица с расписание семинаров здесь

Таблица со списком следующих тем здесь

Таблица с итогами здесь

Контакты:

• Ветров Дмитрий Петрович DVetrov@hse.ru
• Лобачева Екатерина Максимовна elobacheva@hse.ru
• Бартунов Сергей Олегович sbos.net@gmail.com

Просьба к теме письма добавлять тег [НИС ФКН].

Краткое описание

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

Результаты

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

О_результ = 0.6 * О_сем + 0.4 * О_доклад + 0.3 * О_итог.контроль

• O_сем складывается на 50% из участия в хакатоне и на 50% из доли посещенных семинаров.
• О_доклад равняется 10 (успешный доклад), 5 (серьезные замечания к докладчику), 0 (незасчитанный доклад или человек с докладом не выступал)
• О_итог.контроль определяется результатом собеседования, которое состоится 22 июня (среда) в 13:00 в 622 аудитории. На собеседование выносятся все темы, начиная с семинара 4.

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

Темы семинаров

Семинар 1. Машинное обучение и история его развития.

Семинар 2. Научный метод.

Основные моменты: Что такое научный метод? Его основные особенности. Эмпирическое и теоретический научный метод. Принципы верификации и фальсификации. Бритва Оккама. Научный и ненаучный метод. Псевдонаука.

Полезные ссылки: 1, 2, 3 + глава 22 из Гарри Поттера и методов рацмышления

Семинар 3.1. Как сделать качественную презентацию.

Полезные ссылки: 1, 2, 3, 4, 5, 6, 7

Семинар 3.2. Как не нужно работать с данными.

Полезные ссылки: 1, 2, 3, 4, 5, 6, 7

Семинар 4. Линейная регрессия.

В докладе следует осветить следующие основные моменты:

1. Общую постановка задачи обучения с учителем, а также регрессии как ее частный случай
2. Привести несколько примеров из жизни, где подобная задача возникает
3. Рассмотреть линейную модель регресии, а также привести пример любой нелинейной модели
4. Записать задачу оптимизации, которая возникает при использовании квадратичной функции потерь.
5. Вывести разложение квадратичной ошибки в виде суммы bias и variance, обсудить значение этого разложения
6. Показать хотя бы два метода для решения данной задачи - метод градиентного спуска и псевдо-решение СЛАУ, обсудить, какие преимущества и недостатки есть у каждого метода.
7. Рассмотреть пример переобучения и использования L2-регуляризации как метода борьбы с ним. Связь L2-регуляризации с нормальным псевдо-решением.
8. Обсудить другие функции потерь, например, L1.

Полезные ссылки: 1, 2 (главы 2 и 3), 3, 4, 5, 6, 7, 8

Семинар 5. Метод опорных векторов. Линейно-разделимый случай

План доклада:

1. Ликбез. Теорема Куна-Такера и как ее использовать для задач оптимизации с ограничениями.
2. Общая постановка задачи обучения с учителем, а также классификации, как ее частный случай.
3. Привести несколько примеров из жизни, где подобная задача возникает
4. Рассмотреть линейный классификатор, как выглядит его решающее правило, его геометрический смысл (разделяющая гиперплоскость).
5. Неоднозначность выбора разделяющей гиперплоскости при использовании бинарной функции потерь.
6. Принцип максимального зазора (или иначе заступа, англ. max margin), как некоторый разумный способ выбора разделяющей гиперплоскости. Показать его устойчивость при добавлении небольшого шума к обучающей выборке.
7. Вывод величины зазора через вектор нормали гиперплоскости
8. Задача оптимизации, возникающая при обучении метода опорных векторов в случае линейно-разделимой выборки.
9. Решение выпуклой задачи условной оптимизации с использованием метода множителей Лагранжа.
10. Двойственная функция, возникающая при обучении SVM.
11. Решение данной задачи оптимизации, его зависимость от опорных векторов. Смысл множителей лагранжа, условий дополняющей нежесткости.

Полезные ссылки: 1, 2, 3, 4, 5, 6, 7, 8.

Семинар 6. Метод опорных векторов. Линейно-неразделимый случай, ядровой переход

План доклада:

1. Краткое напоминание основных результатов предыдущего семинара:
   1. постановка задачи бинарной классификации
   2. вид решающего правила и его геометрический смысл
   3. принцип максимизации зазора
   4. прямая и двойственная задачи оптимизации
2. Ослабление предположения о линейной разделимости выборки
   1. изменение задачи оптимизаци
   2. решение двойственной задачи оптимизации
   3. вывод функции потерь SVM (hinge loss)
3. Ядровой переход
   1. формальная замена скалярного произведения на функцию ядра
   2. свойства скалярного произведения
   3. примеры ядер с объяснением их свойств и параметров
   4. способы определения новых ядер

См. список материалов к предыдущему семинару.

Семинар 7. Деревья решений и ансамбли решающих правил

План доклада:

1. Общие представления о деревьях решений для классификации и регрессии, примеры, геометрия решающего правила.
2. Алгоритм обучения ID3. Проблемы алгоритма ID3: невозможность обработки вещественных признаков, а также пропущенных значений в данных.
3. Решение этих проблем в алгоритме C4.5, принцип максимизации информационной выгоды (information gain).
4. Проблема переобучения, регуляризация при обучении деревьев решений: ограничение максимальной глубины дерева, обрезание дерева (tree pruning).
5. Ансамбли решающих правил. Примеры, геометрия решающего правила. Общая идея бустинга.
6. Схема алгоритма AdaBoost.
7. Верхняя оценка ошибки на обучающей выборке алгоритма AdaBoost.

Полезные ссылки: 1, 2, 3, 4.

Практическое задание. Классификация изображений. Описание.

Семинар 9. Конференции и современные результаты в машинном обучении

Семинар 10. Методы кластеризации

План доклада:

1. Задача кластеризации. Отличия от задачи классификации. Неоднозначность/возможность разных постановок задачи.
2. Функция близости/расстояния, ее свойства, подробно рассмотреть неравенство треугольника и проблемы, к которым оно может приводить. В качестве примера можно рассмотреть тройку объектов: человек, лошадь и кентавр. Привести примеры функций близости/расстояния кроме евклидового для различных типов объектов.
3. Иерархические алгоритмы кластеризации. Построение иерархии снизу вверх и сверху вниз, преимущества и недостатки обоих подходов.
4. Алгоритм k-средних. Оптимизируемая функция потерь, алгоритмическая сложность глобальной минимизации данной функции. Алгоритм k-средних как метод локальной покоординатной оптимизации, доказательство сходимости, зависимость от инициализации. Подбор числа кластеров.
5. EM-алгоритм для смеси гауссиан. Многомерное нормальное распределение, его параметры и их смысл. Описания кластера с помощью нормального распределения, связь правдоподобия нормального распределения и евклидового расстояния. Оптимизируемая функция потерь/качества (логарифм неполного правдоподобия или обоснованность модели). Сложность оптимизации подобной функции в явном виде. EM-алгоритм как строгое обобщения алгоритма k-means.

Полезные ссылки: 1, 2, 3, 4.

Семинар 11. Матричные разложения и их приложения в рекомендательных системах и анализе текста

План доклада:

1. Введение. Матрицы как естественное представление данных в рекомендательных системах (оценки пользователей) и анализе текста (количество слов в каждом документе).
2. Предположение о существовании базиса в скрытом пространстве низкой размерности, хорошо описывающем данные в виде общих характеристик/жанров/тематик/etc. Формула для выражения элемента матрицы через скалярное произведение векторов в скрытом пространстве. Аналогичная запись в матричной форме.
3. Функции потерь. Обработка отсутствующих данных.
4. Стохастические алгоритмы оптимизации в задаче матричного разложения.
5. Улучшения предсказаний, вычитание средних значений.
6. Предсказания для новых данных, интерпретация объектов разложения в скрытом пространстве, извлечение признаков.
7. Тензорные разложения (разложение Таккера, СP-разложение)

Полезные ссылки: 1, 2, 3, 4.

Семинар 12. Оптимизация: градиентный спуск и стохастический градиент

План доклада:

1. Задачи машинного обучения и соответствующие им задачи оптимизации: линейная регрессия, логистическая регрессия, двойственная задача в SVM.
2. Понятия функции многих переменных, выпуклости множества и функции, свойства выпуклых функций. Примеры выпуклых и невыпуклых функций.
3. Определение производной (для одномерного случая) и градиента (для функции многих переменных), понятие непрерывной, дифференцируемой и гладкой функции (примеры и антипримеры).
4. Свойства градиента, правила дифференцирования, дифференцирование сложной функции.
5. Алгоритм градиентного спуска (GD)
   • Общая схема алгоритма
   • Выбор шага градиента
   • Условия и скорость сходимости (пояснить смысл данного понятия)
   • Пример пошаговой оптимизации для двумерной линейной регрессии
6. Стохастическая оценка градиента, сходимость градиентного спуска со стохастической оценкой градиента (теорема Роббинса-Монро).
7. Алгоритм стохастического градиентного спуска (SGD)
   • Общая схема алгоритма
   • Выбор шага градиента
   • Условия и скорость сходимости
   • Пример пошаговой оптимизации для двумерной линейной регрессии

Замечание: Нужно реализовать GD и SGD и применить их к задаче двумерной линейной регрессии. Следует привести графики зависимости значения минимизируемого функционала от номера итерации, а также показать как меняется положение искомой прямой в пространстве в ходе оптимизации.

Полезные ссылки: 1, 2, 3, 4, 5.

Семинар 13. Введение в нейросети

План доклада:

1. Основные тезисы коннекционизма. Сложная модель на основе сети из простых связанных элементов. Биологическая модель нейрона. Модель искусственного нейрона.
2. Функции активации нейронов (сигмоидальная, гиперболический тангенс, кусочно-линейная). Многослойный перцептрон. Выходной слой для различных задач: регрессия над произвольными и неотрицательными числами, классификация.
3. Теорема о многослойном перцептроне как универсальном аппроксиматоре. Примеры.
4. Обзор библиотеки theano или tensorflow (на выбор), основные возможности, типы данных, принципы построения эффективных программ. Типичные проблемы производительности и способы их решения. Методы отладки.
5. Подробный пример собственной реализации двуслойного перцептрона для классификации изображений из коллекции MNIST.
6. Основные управляющие параметры модели: число слоев, размеры слоев, функции активации, регуляризация, инициализация параметров, алгоритм оптимизации и его параметры. Влияние данных параметров на скорость / качество обучения (обязательно с конкретными цифрами / графиками).

Полезные ссылки: 1, 2, 3, 4, 5.

Семинар 14. Сокращение размерности, автокодировщики

План доклада:

1. Важность признакового описания в задачах машинного обучения. Примеры удачных и неудачных признаковых описаний.
2. Недостатки использования “сырого” представления данных (пример: пиксели изображения), избыточность и низкая информативность
3. Задача понижения размерности, связь с извлечением признаков. Метод главных компонент.
   • Ликбез: ковариационная матрица и ее свойства, SVD-разложение положительно определенной матрицы
   • Различные постановки задачи и их эквивалентность: поиск ортогонального базиса с наибольшей дисперсией, декорреляция признаков, оптимальное (с точки зрения квадратичной ошибки) линейное уменьшение размерности. Обязательно рассмотреть хотя бы две из формулировок, можно рассмотреть больше.
   • Итеративный алгоритм поиска главных компонент.
   • Матрица прямого и обратного преобразования.
4. Пример приложения МГК - система eigenfaces.
5. Автокодировщик как нейросетевая архитектура понижения размерности и извлечения признаков. Нелинейные и иерархические преобразования данных.

Полезные ссылки: 1, 2, 3, 4, 5, 6, 7, 8.

Семинар 15. Сверточные нейронные сети в компьютерном зрении

План доклада:

1. Полносвязные нейронные сети и их приложения к задачам компьютерного зрения. Преимущества (например, устойчивость к перестановке пикселей) и недостатки (например, большое число настраиваемых параметров).
2. Сверточные сети. Операция свертки с примерами. Мотивация: меньшее число настраиваемых параметров, инвариантнось к небольшим смещениям и поворотам, меньшая зависимость от размера входа.
3. Обзор типичной архитектуры сверточной сети (LeNet) для классификации изображений. Назначение и устройство различных типов слоев (сверточные, пулинг, полносвязные). Обработка RGB-входа.
4. Интерпретация фильтров сверточных слоев. Использование активаций обученных сетей для извлечения признаков и других задач (перенос стиля, моментальное обучение и пр.)
5. Примеры использования сверточных сетей для различных задач. Стоит поискать интересные примеры в интеренете + для многих из них можно скачать готовые модели и позапускать их на семинаре.

Полезные ссылки: 1, 2, 3, 4, 5, 6, 7, 8, 9.

Семинар 16. Спектральный анализ графов

План доклада:

1. Ликбез: собственные числа и собственные векторы матрицы.
2. Ненаправленный простой граф. Матрица смежности. Расчет существования путей длины k с помощью матрицы смежности.
3. Случайные блуждания на графе. Вероятность перехода в вершину за k шагов. Стационарное распределение случайного блуждания, достаточные условия его существования, алгоритмы вычисления.
4. Лапласиан графа. Вложения вершин графа с помощью лапласиана, связь с собственными векторами. Приложения: извлечение признаков, спектральная кластеризация.
5. Расчет близостей между вершинами в графе, среднее время пути (average commute time distance) и связанные меры близости/расстояния. Эффективный алгоритм вычисления. Приложения.
6. Бонус: спектральные свойства графов, число компонент связности, диаметр и т.д.

Полезные ссылки: 1, 2, 3, 4, 5, 6, 7, 8.

Семинар 17. Обучение с подкреплением

План доклада:

1. Постановка задачи обучения с подкреплением. Понятия наблюдаемых данных, состояния, действий, награды и стратегии. Марковский процесс приятия решений и его не полностью наблюдаемый аналог. Примеры задач обучения с подкреплением.
2. Понятие ожидаемого дохода (англ. return), средний и дисконтированный доход. Функции ценности состояния (англ. value function) и ценности действия-состояния (англ. action-state function). Уравнение Беллмана.
3. Принцип обучения функции ценности (Q-learning) для марковского процесса принятия решений, аппроксимация функции ценности.
4. Градиентное обучение стратегий, алгоритм REINFORCE.
5. Приложения: алгоритм Deep Q-network для Atari игр.

Полезные ссылки: 1, 2, 3, 4, 5, 6, 7.