Материал из MachineLearning.

Содержание 1 Основные понятия и примеры прикладных задач 2 Метрические методы классификации и регрессии 3 Логические методы классификации 4 Градиентные методы обучения 5 Метод опорных векторов 6 Линейная и нелинейная регрессия 7 Байесовская теория классификации 8 Кластеризация и частичное обучение 9 Нейронные сети 10 Линейные композиции, бустинг 11 Понижение размерности 12 Ранжирование и информационный поиск 13 Обучение с подкреплением и активное обучение 14 Литература

Сокращённая версия курса машинного обучения для студентов 4 курса ФУПМ МФТИ.

Дополнительные материалы:

• Специализация «Машинное обучение и анализ данных» (МФТИ и Яндекс).
• Видеолекции ШАД Яндекс.
• «Введение в машинное обучение» на Курсэре содержит примерно втрое меньше материала, чем в годовом курсе, действительно введение.

Основные понятия и примеры прикладных задач

Презентация: (PDF, 1,4 МБ) — обновление 09.02.2018.

• Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
• Типы задач: классификация, регрессия, прогнозирование, ранжирование.
• Основные понятия: модель алгоритмов, метод обучения, функция потерь и функционал качества, принцип минимизации эмпирического риска, обобщающая способность, скользящий контроль.
• Линейные модели регрессии и классификации. Метод наименьших квадратов. Полиномиальная регрессия.
• Примеры прикладных задач.
• Методика экспериментального исследования и сравнения алгоритмов на модельных и реальных данных.
• Конкурсы по анализу данных kaggle.com. Полигон алгоритмов классификации.
• CRISP-DM — межотраслевой стандарт ведения проектов интеллектуального анализа данных.

Метрические методы классификации и регрессии

Презентация: (PDF, 3,2 МБ) — обновление 13.03.2018.

• Гипотезы компактности и непрерывности.
• Обобщённый метрический классификатор.
• Метод ближайших соседей kNN и его обобщения. Подбор числа k по критерию скользящего контроля.
• Метод окна Парзена с постоянной и переменной шириной окна.
• Метод потенциальных функций и его связь с линейной моделью классификации.
• Непараметрическая регрессия. Локально взвешенный метод наименьших квадратов. Ядерное сглаживание.
• Оценка Надарая-Ватсона с постоянной и переменной шириной окна. Выбор функции ядра.
• Задача отсева выбросов. Робастная непараметрическая регрессия. Алгоритм LOWESS.

Логические методы классификации

Презентация: (PDF, 1.8 МБ) — обновление 13.03.2018.

• Понятие логической закономерности.
• Параметрические семейства закономерностей: конъюнкции пороговых правил, синдромные правила, шары, гиперплоскости.
• Статистический критерий информативности, точный тест Фишера.
• Переборные алгоритмы синтеза конъюнкций: стохастический локальный поиск, стабилизация, редукция.
• Двухкритериальный отбор информативных закономерностей, парето-оптимальный фронт в (p,n)-пространстве.
• Решающее дерево. Жадная нисходящая стратегия «разделяй и властвуй». Алгоритм ID3. Недостатки жадной стратегии и способы их устранения. Проблема переобучения.
• Вывод критериев ветвления. Мера нечистоты (impurity) распределения. Энтропийный критерий, критерий Джини.
• Редукция решающих деревьев: предредукция и постредукция. Алгоритм C4.5.
• Деревья регрессии. Алгоритм CART.
• Решающий список (Decision List). Жадный алгоритм синтеза списка. Преобразование решающего дерева в решающий список.
• Решающие таблицы или Небрежные решающие деревья (oblivious decision tree).
• Решающий лес. Случайный лес (Random Forest).
• Алгоритм разбиения области значений признака на информативные зоны.

Градиентные методы обучения

Презентация: (PDF, 1,1 МБ) — обновление 13.03.2018.

• Линейный классификатор, модель МакКаллока-Питтса, непрерывные аппроксимации пороговой функции потерь.
• Метод стохастического градиента SG.
• Метод стохастического среднего градиента SAG.
• Частные случаи: адаптивный линейный элемент ADALINE, перcептрон Розенблатта, правило Хэбба.
• Теорема Новикова о сходимости. Доказательство теоремы Новикова
• Эвристики: инициализация весов, порядок предъявления объектов, выбор величины градиентного шага, «выбивание» из локальных минимумов.
• Проблема мультиколлинеарности и переобучения, регуляризация или редукция весов (weight decay).
• Вероятностная постановка задачи классификации. Принцип максимума правдоподобия.
• Вероятностная интерпретация регуляризации, совместное правдоподобие данных и модели. Принцип максимума апостериорной вероятности.
• Гауссовский и лапласовский регуляризаторы.
• Логистическая регрессия. Принцип максимума правдоподобия и логарифмическая функция потерь. Метод стохастического градиента для логарифмической функции потерь. Сглаженное правило Хэбба.
• Многоклассовая логистическая регрессия. Регуляризованная логистическая регрессия. Калибровка Платта.
• Пример прикладной задачи: кредитный скоринг. Бинаризация признаков. Скоринговые карты и оценивание вероятности дефолта. Риск кредитного портфеля банка.

Метод опорных векторов

Презентация: (PDF, 1,1 МБ) — обновление 07.03.2017.

• Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin).
• Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь.
• Задача квадратичного программирования и двойственная задача. Понятие опорных векторов.
• Рекомендации по выбору константы C.
• Функция ядра (kernel functions), спрямляющее пространство, теорема Мерсера.
• Способы конструктивного построения ядер. Примеры ядер.
• SVM-регрессия.
• Регуляризации для отбора признаков: LASSO SVM, Elastic Net SVM, SFM, RFM.
• Метод релевантных векторов RVM

Линейная и нелинейная регрессия

Презентация: (PDF, 0,8 MБ) — обновление 18.03.2018.

• Задача регрессии, многомерная линейная регрессия.
• Метод наименьших квадратов, его вероятностный смысл и геометрический смысл.
• Сингулярное разложение.
• Гребневая регрессия через сингулярное разложение.
• Нелинейная регрессия. Метод Ньютона-Рафсона, метод Ньютона-Гаусса.
• Обобщённая аддитивная модель (GAM): метод настройки с возвращениями (backfitting) Хасти-Тибширани.
• Неквадратичные функции потерь. Робастная регрессия. Метод наименьших модулей. Квантильная регрессия.
• Обобщённая линейная модель (GLM). Экспоненциальное семейство распределений. Метод наименьших квадратов с итеративным пересчётом весов (IRLS). Логистическая регрессия.

Байесовская теория классификации

Презентация: (PDF, 1,7 МБ) — обновление 13.04.2018.

• Принцип максимума апостериорной вероятности. Оптимальный байесовский классификатор.
• Наивный байесовский классификатор.
• Непараметрическое оценивание плотности. Ядерная оценка плотности Парзена-Розенблатта. Одномерный и многомерный случаи.
• Метод парзеновского окна. Выбор функции ядра. Выбор ширины окна, переменная ширина окна.
• Параметрическое оценивание плотности. Нормальный дискриминантный анализ.
• Многомерное нормальное распределение, геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения.
• Квадратичный дискриминант. Линейный дискриминант Фишера, робастное оценивание ковариационной матрицы.
• Робастное оценивание. Цензурирование выборки (отсев объектов-выбросов).
• Разделение смеси распределений.
• EM-алгоритм: основная идея, понятие скрытых переменных. ЕМ алгоритм как метод простых итераций для решения системы нелинейных уравнений.
• Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.
• Сопоставление RBF-сети и SVM с гауссовским ядром.

Кластеризация и частичное обучение

Презентация: (PDF, 2,1 МБ) — обновление 04.04.2018.

• Постановка задачи кластеризации. Примеры прикладных задач. Типы кластерных структур.
• Постановка задачи Semisupervised Learning, примеры приложений.
• Оптимизационные постановки задач кластеризации и частичного обучения.
• Алгоритм k-средних и ЕМ-алгоритм для разделения гауссовской смеси.
• Сеть Кохонена, конкурентное обучение, стратегии WTA и WTM. Самоорганизующаяся карта Кохонена.
• Графовые алгоритмы кластеризации. Выделение связных компонент. Кратчайший незамкнутый путь.
• Алгоритм ФОРЭЛ.
• Алгоритм DBSCAN.
• Агломеративная кластеризация, Алгоритм Ланса-Вильямса и его частные случаи.
• Алгоритм построения дендрограммы. Определение числа кластеров.
• Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
• Простые эвристические методы частичного обучения: self-training, co-training, co-learning.
• Трансдуктивный метод опорных векторов TSVM.
• Алгоритм Expectation-Regularization на основе многоклассовой регуляризированной логистической регрессии.

Нейронные сети

Презентация: (PDF, 3,8 МБ) — обновление 04.04.2018.

• Функциональная полнота нейронных сетей.
• Многослойная нейронная сеть. Алгоритм обратного распространения ошибок.
• Эвристики: формирование начального приближения, ускорение сходимости, диагональный метод Левенберга-Марквардта. Проблема «паралича» сети.
• Подбор структуры сети: методы постепенного усложнения сети, оптимальное прореживание нейронных сетей (optimal brain damage).
• Нейронные сети глубокого обучения.
• Быстрые методы стохастического градиента: Поляка, Нестерова, RMSProp, AdaDelta, Adam, Nadam.
• Проблема взрыва градиента и эвристика gradient clipping
• Метод случайных отключений нейронов (Dropout). Интерпретации Dropout. Обратный Dropout и L2-регуляризация.
• Функции активации ReLU и PReLU.
• Свёрточные нейронные сети (CNN). Свёрточный нейрон. Pooling нейрон. Выборка размеченных изображений ImageNet.
• Идея обобщения CNN на любые структурированные данные.
• Рекуррентные нейронные сети (RNN). Обучение рекуррентных сетей: Backpropagation Through Time (BPTT).
• Сети долгой кратковременной памяти. Long short-term memory (LSTM). Gated Recurrent Unit (GRU).

Линейные композиции, бустинг

Презентация: (PDF, 1.2 МБ) — обновление 16.04.2018.

• Основные понятия: базовый алгоритм (алгоритмический оператор), корректирующая операция.
• Взвешенное голосование.
• Алгоритм AdaBoost. Экспоненциальная аппроксимация пороговой функции потерь. Процесс последовательного обучения базовых алгоритмов. Теорема о сходимости бустинга.
• Обобщающая способность бустинга.
• Базовые алгоритмы в бустинге. Решающие пни.
• Варианты бустинга: GentleBoost, LogitBoost, BrownBoost, и другие.
• Алгоритм AnyBoost.
• Градиентный бустинг. Стохастический градиентный бустинг.
• Простое голосование (комитет большинства). Алгоритм ComBoost. Идентификация нетипичных объектов (выбросов).
• Преобразование простого голосования во взвешенное.
• Обобщение на большое число классов.
• Стохастические методы: бэггинг и метод случайных подпространств. Случайный лес.
• Смесь алгоритмов (квазилинейная композиция), область компетентности, примеры функций компетентности.
• Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
• Построение смеси алгоритмов с помощью EM-подобного алгоритма.

Понижение размерности

Презентация: (PDF, 1.4 МБ) — обновление 23.04.2018.

• Задача отбора признаков. Внутренние и внешние критерии.
• Алгоритмы комбинаторной оптимизации для отбора признаков. Полный перебор.
• Жадные алгоритмы: метод добавления и удаления, поиск в глубину, метод ветвей и границ.
• Усечённый поиск в ширину, многорядный итерационный алгоритм МГУА.
• Генетический алгоритм, его сходство с МГУА.
• Случайный поиск и Случайный поиск с адаптацией (СПА).
• Задачи матричного разложения.
• Метод главных компонент и декоррелирующее преобразование Карунена-Лоэва, его связь с сингулярным разложением.
• Спектральный подход к решению задачи наименьших квадратов.
• Рекомендательные системы и коллаборативная фильтрация.
• Метод главных компонент для разреженных данных (LFM, Latent Factor Model).
• Неотрицательные матричные разложения. Метод чередующихся наименьших квадратов ALS.
• Модель с учётом неявной информации (implicit feedback).
• Рекомендации с учётом дополнительных признаковых данных. Линейная и квадратичная регрессионные модели, libFM.
• Измерение качества рекомендаций: разнообразие (diversity), новизна (novelty), покрытие (coverage), догадливость (serendipity).

Ранжирование и информационный поиск

Презентация: (PDF, 2,2 МБ) — обновление 30.04.2018.

• Постановка задачи обучения ранжированию. Примеры.
• Признаки в задаче ранжирования поисковой выдачи: текстовые, ссылочные, кликовые. TF-IDF. Okapi BM25.
• PageRank, эффективные способы его вычисления.
• Критерии качества ранжирования: Precision, MAP, AUC, DCG, NDCG, pFound.
• Ранговая классификация, OC-SVM.
• Попарный подход: RankingSVM, RankNet, LambdaRank. Градиентный метод оптимизации AUC.
• Семантический поиск.
• Задача тематического моделирования коллекции текстовых документов.
• Вероятностный латентный семантический анализ PLSA. Метод максимума правдоподобия. ЕМ-алгоритм.
• Аддитивная регуляризация тематических моделей. Регуляризованный EM-алгоритм, теорема о стационарной точке (применение условий Каруша–Куна–Таккера).
• Примеры регуляризаторов. Латентное размещение Дирихле LDA. Разреживание, сглаживание, частичное обучение, мультимодальность.
• Регуляризаторы классификации и регрессии.
• Регуляризаторы декоррелирования и отбора тем.
• Критерии качества тематических моделей.

Обучение с подкреплением и активное обучение

Презентация: (PDF, 1.0 МБ) — обновление 1.11.2017.

• Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound). Стратегия Softmax.
• Среда для экспериментов.
• Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования.
• Постановка задачи в случае, когда агент влияет на среду. Ценность состояния среды. Ценность действия.
• Жадные стратегии максимизации ценности. Уравнения оптимальности Беллмана.
• Метод временных разностей TD. Метод Q-обучения.
• Градиентная оптимизация стратегии (policy gradient). Связь с максимизацией log-правдоподобия.
• Постановка задачи при наличии информации о среде. Контекстный многорукий бандит.
• Активное обучение.
• Сэмплирование по неуверенности. Почему активное обучение быстрее пассивного.
• Сэмплирование по ожидаемому сокращению ошибки.
• Взвешивание по плотности.
• Оценивание качества активного обучения.
• Введение изучающих действий в стратегию активного обучении. Алгоритмы ε-active и EG-active.

Литература

1. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Springer, 2014. — 739 p.
2. Bishop C. M. Pattern Recognition and Machine Learning. — Springer, 2006. — 738 p.
3. Мерков А. Б. Распознавание образов. Введение в методы статистического обучения. 2011. 256 с.
4. Мерков А. Б. Распознавание образов. Построение и обучение вероятностных моделей. 2014. 238 с.
5. Коэльо Л.П., Ричарт В. Построение систем машинного обучения на языке Python. 2016. 302 с.