Машинное обучение (курс лекций, К.В.Воронцов)
Материал из MachineLearning.
(→Критерии выбора моделей и методы отбора признаков) |
(→Второй семестр) |
||
(208 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
{{TOCright}} | {{TOCright}} | ||
- | '''Теория обучения машин''' (machine learning, машинное обучение) | + | '''Теория обучения машин''' (machine learning, машинное обучение) находится на стыке [[Прикладная статистика|прикладной статистики]], [[Методы оптимизации|численных методов оптимизации]], [[Дискретный анализ|дискретного анализа]], и за последние 50 лет оформилась в самостоятельную математическую дисциплину. Методы [[Машинное обучение|машинного обучения]] составляют основу ещё более молодой дисциплины — ''[[Интеллектуальный анализ данных|интеллектуального анализа данных]]'' (data mining). |
В курсе рассматриваются основные задачи обучения по прецедентам: [[классификация]], [[кластеризация]], [[регрессия]], [[понижение размерности]]. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами. | В курсе рассматриваются основные задачи обучения по прецедентам: [[классификация]], [[кластеризация]], [[регрессия]], [[понижение размерности]]. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами. | ||
Строка 10: | Строка 10: | ||
* анализ достоинств, недостатков и границ применимости; | * анализ достоинств, недостатков и границ применимости; | ||
* пути устранения недостатков; | * пути устранения недостатков; | ||
- | * сравнение с другими методами | + | * сравнение с другими методами. |
* примеры прикладных задач. | * примеры прикладных задач. | ||
Строка 21: | Строка 21: | ||
На материал данного курса опираются последующие кафедральные курсы. | На материал данного курса опираются последующие кафедральные курсы. | ||
- | На кафедре ММП ВМиК МГУ параллельно с данным курсом и в дополнение к нему читается спецкурс [[Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)|Теория надёжности обучения по прецедентам]], посвящённый проблемам [[Переобучение|переобучения]] и оценивания [[Обобщающая способность|обобщающей способности]]. | + | <!---На кафедре ММП ВМиК МГУ параллельно с данным курсом и в дополнение к нему читается спецкурс [[Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)|Теория надёжности обучения по прецедентам]], посвящённый проблемам [[Переобучение|переобучения]] и оценивания [[Обобщающая способность|обобщающей способности]].---> |
От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание [[Математическая статистика|математической статистики]], [[Методы оптимизации|методов оптимизации]] и какого-либо языка программирования желательно, но не обязательно. | От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание [[Математическая статистика|математической статистики]], [[Методы оптимизации|методов оптимизации]] и какого-либо языка программирования желательно, но не обязательно. | ||
Строка 31: | Строка 31: | ||
=== Замечания для студентов === | === Замечания для студентов === | ||
- | * | + | * Видеолекции [https://yandexdataschool.ru/edu-process/courses/machine-learning ШАД Яндекс]. |
+ | * [https://www.coursera.org/learn/vvedenie-mashinnoe-obuchenie «Введение в машинное обучение» на Курсэре] содержит примерно втрое меньше материала, чем в годовом курсе, представленном на этой странице. Там очень многое упрощено, спрятано, пропущено. Действительно введение. | ||
* На подстранице имеется перечень [[Машинное обучение (курс лекций, К.В.Воронцов)/Вопросы|вопросов к устному экзамену]]. Очень помогает при подготовке к устному экзамену! | * На подстранице имеется перечень [[Машинное обучение (курс лекций, К.В.Воронцов)/Вопросы|вопросов к устному экзамену]]. Очень помогает при подготовке к устному экзамену! | ||
* О найденных ошибках и опечатках [[Служебная:EmailUser/Vokov|сообщайте мне]]. — ''[[Участник:Vokov|К.В.Воронцов]] 18:24, 19 января 2009 (MSK)'' | * О найденных ошибках и опечатках [[Служебная:EmailUser/Vokov|сообщайте мне]]. — ''[[Участник:Vokov|К.В.Воронцов]] 18:24, 19 января 2009 (MSK)'' | ||
+ | * Материал, который есть в pdf-тексте, но не рассказывался на лекциях, обычно не входит в программу экзамена. | ||
+ | * Короткая ссылка на эту страницу: [https://bit.ly/1bCmE3Z https://bit.ly/1bCmE3Z]. | ||
= Первый семестр = | = Первый семестр = | ||
- | + | '''Текст лекций:''' [[Media:Voron-ML-1.pdf|(PDF, 3 МБ)]] {{важно|— обновление 4.10.2011}}. | |
- | Текст лекций: [[Media:Voron-ML-1.pdf|(PDF, 3 МБ)]] | + | |
- | + | ||
- | + | == Основные понятия и примеры прикладных задач == | |
+ | Презентация: [[Media:Voron-ML-Intro-slides.pdf|(PDF, 1,4 МБ)]] {{важно|— обновление 14.12.2019}}. | ||
* Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные. | * Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные. | ||
- | * Типы задач: [[классификация]], [[регрессия]], [[прогнозирование]], [[ | + | * Типы задач: [[классификация]], [[регрессия]], [[прогнозирование]], [[ранжирование]]. |
* Основные понятия: [[модель алгоритмов]], [[метод обучения]], [[функция потерь]] и функционал качества, [[принцип минимизации эмпирического риска]], [[обобщающая способность]], [[скользящий контроль]]. | * Основные понятия: [[модель алгоритмов]], [[метод обучения]], [[функция потерь]] и функционал качества, [[принцип минимизации эмпирического риска]], [[обобщающая способность]], [[скользящий контроль]]. | ||
- | * Методика экспериментального исследования и сравнения алгоритмов на модельных и реальных данных. [[Полигон алгоритмов классификации]]. | + | * Линейные модели регрессии и классификации. Метод наименьших квадратов. Полиномиальная регрессия. |
- | * | + | * Примеры прикладных задач. |
+ | * Методика экспериментального исследования и сравнения алгоритмов на модельных и реальных данных. | ||
+ | * Конкурсы по анализу данных [http://kaggle.com kaggle.com]. [[Полигон алгоритмов классификации]]. | ||
+ | * [[CRISP-DM]] — межотраслевой стандарт ведения проектов [[Data Mining | интеллектуального анализа данных]]. | ||
- | == | + | == Линейный классификатор и стохастический градиент == |
- | + | ||
- | + | Презентация: [[Media:Voron-ML-Lin-SG.pdf|(PDF, 1,1 МБ)]] {{важно|— обновление 14.12.2019}}. | |
- | + | * [[Линейный классификатор]], модель МакКаллока-Питтса, непрерывные аппроксимации пороговой функции потерь. | |
- | + | * [[Метод стохастического градиента]] SG. | |
- | + | * [[Метод стохастического среднего градиента]] SAG. | |
- | + | <!-- | |
- | * [[ | + | * Частные случаи: [[адаптивный линейный элемент]] ADALINE, [[перcептрон Розенблатта]], [[правило Хэбба]]. |
- | + | * [[Теорема Новикова]] о сходимости. Доказательство теоремы Новикова | |
- | + | --> | |
- | * [[ | + | * Эвристики: инициализация весов, порядок предъявления объектов, выбор величины градиентного шага, «выбивание» из локальных минимумов. |
- | * [[Метод | + | * Проблема мультиколлинеарности и переобучения, регуляризация или [[редукция весов]] (weight decay). |
- | + | * Вероятностная постановка задачи классификации. Принцип максимума правдоподобия. | |
- | + | * Вероятностная интерпретация регуляризации, совместное правдоподобие данных и модели. Принцип максимума апостериорной вероятности. | |
- | + | * Гауссовский и лапласовский регуляризаторы. | |
- | + | * [[Логистическая регрессия]]. Принцип максимума правдоподобия и логарифмическая функция потерь. [[Метод стохастического градиента]] для логарифмической функции потерь. Многоклассовая логистическая регрессия. Регуляризованная логистическая регрессия. [[Калибровка Платта]]. | |
- | + | <!-- | |
- | * [[ | + | * Функции потерь, зависящие от цены ошибок. [[Кривая ошибок]] (ROC curve). Алгоритм эффективного построения ROC-кривой. |
- | + | * Градиентный метод максимизации AUC. | |
- | + | --> | |
- | * | + | |
- | * | + | |
- | * | + | |
- | * | + | |
- | * | + | |
- | + | ||
- | + | ||
- | * [[ | + | |
- | + | ||
- | + | ||
- | * | + | |
- | + | ||
- | + | ||
- | + | ||
- | == | + | == Метрические методы классификации и регрессии == |
- | + | Презентация: [[Media:Voron-ML-Metric-slides.pdf|(PDF, 3,2 МБ)]] {{важно|— обновление 14.12.2019}}. | |
- | + | ||
- | + | ||
- | + | ||
- | + | * Гипотезы компактности и непрерывности. | |
- | * | + | * Обобщённый [[метрический классификатор]]. |
- | * [[Функция конкурентного сходства]], [[алгоритм FRiS-СТОЛП]]. | + | * [[Метод ближайших соседей]] ''k''NN и его обобщения. Подбор числа ''k'' по критерию скользящего контроля. |
- | * [[Функционал полного скользящего контроля]], формула быстрого вычисления для метода 1NN. [[Профиль компактности]]. | + | * [[Метод окна Парзена]] с постоянной и переменной шириной окна. |
- | + | * [[Метод потенциальных функций]] и его связь с линейной моделью классификации. | |
+ | * Непараметрическая регрессия. Локально взвешенный [[метод наименьших квадратов]]. [[Ядерное сглаживание]]. | ||
+ | * [[Оценка Надарая-Ватсона]] с постоянной и переменной шириной окна. Выбор функции ядра. | ||
+ | * Задача отсева выбросов. Робастная непараметрическая регрессия. [[Алгоритм LOWESS]]. | ||
+ | * Задача отбора эталонов. Понятие [[отступ]]а. [[Алгоритм СТОЛП]]. | ||
+ | * Задача отбора признаков. Жадный алгоритм построения метрики. | ||
+ | <!-- | ||
+ | * ''[[Функция конкурентного сходства]], [[алгоритм FRiS-СТОЛП]]''. | ||
+ | * ''[[Функционал полного скользящего контроля]], формула быстрого вычисления для метода 1NN. [[Профиль компактности]]. Функция вклада объекта. Отбор эталонных объектов на основе минимизации функционала полного скользящего контроля. Эффективные структуры данных для быстрого поиска ближайших объектов в прямых и обратных окрестностях — [[метрические деревья]].'' | ||
* ''Концепция вывода на основе прецедентов ([[CBR]]).'' | * ''Концепция вывода на основе прецедентов ([[CBR]]).'' | ||
+ | --> | ||
- | == | + | == Метод опорных векторов == |
- | Презентация: [[Media:Voron-ML-Lin- | + | Презентация: [[Media:Voron-ML-Lin-SVM.pdf|(PDF, 1,1 МБ)]] {{важно|— обновление 14.12.2019}}. |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
* Оптимальная разделяющая гиперплоскость. Понятие [[зазор]]а между классами (margin). | * Оптимальная разделяющая гиперплоскость. Понятие [[зазор]]а между классами (margin). | ||
* Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь. | * Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь. | ||
Строка 123: | Строка 102: | ||
* [[Функция ядра]] (kernel functions), [[спрямляющее пространство]], [[теорема Мерсера]]. | * [[Функция ядра]] (kernel functions), [[спрямляющее пространство]], [[теорема Мерсера]]. | ||
* Способы конструктивного построения ядер. Примеры ядер. | * Способы конструктивного построения ядер. Примеры ядер. | ||
- | * | + | * SVM-регрессия. |
+ | * Регуляризации для отбора признаков: [[LASSO SVM]], [[Elastic Net SVM]], [[SFM]], [[RFM]]. | ||
+ | * Метод релевантных векторов [[RVM]] | ||
+ | <!--- | ||
* ''Обучение SVM методом активных ограничений. [[Алгоритм INCAS]]. [[Алгоритм SMO]].'' | * ''Обучение SVM методом активных ограничений. [[Алгоритм INCAS]]. [[Алгоритм SMO]].'' | ||
* ''ню-SVM.'' | * ''ню-SVM.'' | ||
- | + | ---> | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | == | + | == Многомерная линейная регрессия == |
- | + | Презентация: [[Media:Voron-ML-regression-slides.pdf|(PDF, 0,7 MБ)]] {{важно|— обновление 14.12.2019}}. | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
* Задача регрессии, [[многомерная линейная регрессия]]. | * Задача регрессии, [[многомерная линейная регрессия]]. | ||
- | * [[Метод наименьших квадратов]] | + | * [[Метод наименьших квадратов]], его вероятностный смысл и геометрический смысл. |
* [[Сингулярное разложение]]. | * [[Сингулярное разложение]]. | ||
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]]. | * Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]]. | ||
- | * [[Регуляризация]]. [[Гребневая регрессия]]. [[Лассо Тибширани]], сравнение с гребневой регрессией. | + | * [[Регуляризация]]. [[Гребневая регрессия]] через сингулярное разложение. |
- | * | + | * Методы отбора признаков: [[Лассо Тибширани]], [[Elastic Net]], сравнение с гребневой регрессией. |
- | + | * [[Метод главных компонент]] и [[декоррелирующее преобразование]] Карунена-Лоэва, его связь с сингулярным разложением. | |
+ | * Спектральный подход к решению задачи наименьших квадратов. | ||
+ | * Задачи и методы низкоранговых матричных разложений. | ||
<!--- | <!--- | ||
=== Шаговая регрессия === | === Шаговая регрессия === | ||
Строка 153: | Строка 127: | ||
* [[Метод наименьших углов]] (LARS), его связь с лассо и шаговой регрессией. | * [[Метод наименьших углов]] (LARS), его связь с лассо и шаговой регрессией. | ||
--> | --> | ||
- | + | ||
+ | == Нелинейная регрессия == | ||
+ | Презентация: [[Media:Voron-ML-regress-non-slides.pdf|(PDF, 0,7 MБ)]] {{важно|— обновление 14.12.2019}}. | ||
* [[Метод Ньютона-Рафсона]], [[метод Ньютона-Гаусса]]. | * [[Метод Ньютона-Рафсона]], [[метод Ньютона-Гаусса]]. | ||
- | * | + | * Обобщённая аддитивная модель (GAM): [[метод настройки с возвращениями]] (backfitting) Хасти-Тибширани. |
- | * [[Логистическая регрессия]] | + | * [[Логистическая регрессия]]. [[Метод наименьших квадратов с итеративным пересчётом весов]] (IRLS). Пример прикладной задачи: кредитный скоринг. Бинаризация признаков. Скоринговые карты и оценивание вероятности дефолта. ''Риск кредитного портфеля банка.'' |
- | * | + | * [[Обобщённая линейная модель]] (GLM). Экспоненциальное семейство распределений. |
- | * | + | * Неквадратичные функции потерь. Метод наименьших модулей. Квантильная регрессия. Пример прикладной задачи: прогнозирование потребительского спроса. |
+ | * Робастная регрессия, функции потерь с горизонтальными асимптотами. | ||
+ | <!--- | ||
+ | * [[Логистическая регрессия]]. Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации. | ||
+ | ---> | ||
- | == | + | == Прогнозирование временных рядов == |
- | Презентация: [[Media:Voron-ML- | + | Презентация: [[Media:Voron-ML-forecasting-slides.pdf|(PDF, 0,9 MБ)]] {{важно|— обновление 14.12.2019}}. |
+ | * Задача прогнозирования временных рядов. Примеры приложений. | ||
+ | * [[Экспоненциальное сглаживание|Экспоненциальное скользящее среднее]]. [[Модель Хольта]]. [[Модель Тейла-Вейджа]]. [[Модель Хольта-Уинтерса]]. | ||
+ | * Адаптивная авторегрессионная модель. | ||
+ | * [[Следящий контрольный сигнал]]. [[Модель Тригга-Лича]]. | ||
+ | * Адаптивная селективная модель. Адаптивная композиция моделей. | ||
+ | * Локальная адаптация весов с регуляризацией. | ||
- | == | + | == Критерии выбора моделей и методы отбора признаков == |
- | + | Текст лекций: [[Media:Voron-ML-Modeling.pdf|(PDF, 330 КБ)]].<br/> | |
- | + | Презентация: [[Media:Voron-ML-Quality-slides.pdf|(PDF, 1,5 МБ)]] {{важно|— обновление 14.12.2019}}. | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | == | + | * Критерии качества классификации: чувствительность и специфичность, ROC-кривая и AUC, точность и полнота, AUC-PR. |
- | Презентация: [[Media:Voron-ML- | + | * Внутренние и [[внешние критерии]]. Эмпирические и аналитические критерии. |
+ | * [[Скользящий контроль]], разновидности эмпирических оценок скользящего контроля. [[Критерий непротиворечивости]]. | ||
+ | * Разновидности аналитических оценок. [[Регуляризация]]. [[Критерий Акаике]] (AIC). [[Байесовский информационный критерий]] (BIC). Оценка Вапника-Червоненкиса. | ||
+ | * Сложность задачи [[отбор признаков|отбора признаков]]. [[Полный перебор]]. | ||
+ | * [[Метод добавления и удаления]], шаговая регрессия. | ||
+ | * [[Поиск в глубину]], метод ветвей и границ. | ||
+ | * Усечённый [[поиск в ширину]], [[многорядный итерационный алгоритм МГУА]]. | ||
+ | * [[Генетический алгоритм]], его сходство с МГУА. | ||
+ | * [[Случайный поиск]] и [[Случайный поиск с адаптацией]] (СПА). | ||
+ | <!--- | ||
+ | * ''Агрегированные и многоступенчатые критерии''. | ||
+ | * ''Статистические критерии: [[коэффициент детерминации]], [[критерий Фишера]], [[анализ регрессионных остатков]].'' | ||
+ | == Теория обобщающей способности == | ||
+ | * [[Теория Вапника-Червоненкиса]]. Функционал равномерного отклонения частот ошибок. [[Функция роста]], [[ёмкость]] семейства алгоритмов. [[Структурная минимизация риска]]. | ||
+ | * ''Оценка «бритвы Оккама»''. | ||
+ | * ''[[Радемахеровская сложность]] семейства алгоритмов.'' | ||
+ | * [[Комбинаторная теория переобучения (виртуальный семинар)|Комбинаторная теория переобучения]]. Функционал вероятности переобучения. Граф расслоения-связности. Оценки расслоения-связности. | ||
+ | ---> | ||
+ | |||
+ | == Логические методы классификации == | ||
+ | Текст лекций: [[Media:Voron-ML-Logic.pdf|(PDF, 625 КБ)]].<br/> | ||
+ | Презентация: [[Media:Voron-ML-Logic-slides.pdf|(PDF, 1.8 МБ)]] {{важно| — обновление 14.12.2019}}. | ||
+ | |||
+ | * Понятие [[логическая закономерность|логической закономерности]]. | ||
+ | * Параметрические семейства закономерностей: конъюнкции пороговых правил, синдромные правила, шары, гиперплоскости. | ||
+ | * Переборные алгоритмы синтеза конъюнкций: [[стохастический локальный поиск]], [[стабилизация]], [[редукция]]. | ||
+ | * Двухкритериальный отбор информативных закономерностей, парето-оптимальный фронт в (p,n)-пространстве. | ||
+ | * [[Решающее дерево]]. Жадная нисходящая стратегия «разделяй и властвуй». [[Алгоритм ID3]]. Недостатки жадной стратегии и способы их устранения. Проблема переобучения. | ||
+ | * Вывод критериев ветвления. Мера нечистоты (impurity) распределения. Энтропийный критерий, критерий Джини. | ||
+ | * [[Редукция решающих деревьев]]: [[предредукция]] и [[постредукция]]. [[Алгоритм C4.5]]. | ||
+ | * Деревья регрессии. [[Алгоритм CART]]. | ||
+ | * [[Небрежные решающие деревья]] (oblivious decision tree). | ||
+ | * Решающий лес. [[Случайный лес]] (Random Forest). | ||
+ | |||
+ | '''Факультатив''' | ||
+ | * Статистический критерий информативности, [[точный тест Фишера]]. Сравнение областей эвристических и статистических закономерностей. Асимптотическая эквивалентность статистического и энтропийного критерия информативности. Разнообразие критериев информативности в (p,n)-пространстве. | ||
+ | * Решающий пень. [[Бинаризация признаков]]. Алгоритм разбиения области значений признака на информативные зоны. | ||
+ | * [[Решающий список]]. Жадный алгоритм синтеза списка. | ||
+ | * Преобразование решающего дерева в решающий список. | ||
+ | |||
+ | == Поиск ассоциативных правил == | ||
+ | Презентация: [[Media:Voron-ML-AssocRules-slides.pdf|(PDF, 1.1 МБ)]] {{важно| — обновление 14.12.2019}}. | ||
+ | * Понятие [[Ассоциативное правило|ассоциативного правила]] и его связь с понятием логической закономерности. | ||
+ | * Примеры прикладных задач: [[анализ рыночных корзин]], выделение терминов и тематики текстов. | ||
+ | * [[Алгоритм APriori]]. Два этапа: поиск частых наборов и рекурсивное порождение ассоциативных правил. Недостатки и пути усовершенствования алгоритма APriori. | ||
+ | * [[Алгоритм FP-growth]]. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов. | ||
+ | * Общее представление о динамических и иерархических методах поиска ассоциативных правил. | ||
+ | |||
+ | == Байесовская классификация и оценивание плотности == | ||
+ | Презентация: [[Media:Voron-ML-BTC-EM-slides.pdf|(PDF, 1,6 МБ)]] {{важно|— обновление 14.12.2019}}. | ||
+ | |||
+ | * Принцип максимума апостериорной вероятности. Теорема об оптимальности байесовского классификатора. | ||
+ | * [[Оценивание плотности распределения]]: три основных подхода. | ||
+ | * [[Наивный байесовский классификатор]]. | ||
+ | * Непараметрическое оценивание плотности. [[Ядерная оценка плотности Парзена-Розенблатта]]. Одномерный и многомерный случаи. | ||
+ | * [[Метод парзеновского окна]]. Выбор функции ядра. Выбор ширины окна, переменная ширина окна. | ||
+ | * Параметрическое оценивание плотности. [[Нормальный дискриминантный анализ]]. | ||
+ | * [[Многомерное нормальное распределение]], геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения. | ||
+ | * [[Квадратичный дискриминант]]. Вид разделяющей поверхности. [[Подстановочный алгоритм]], его недостатки и способы их устранения. | ||
+ | * [[Линейный дискриминант Фишера]]. | ||
+ | * Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]]. [[Регуляризация]] ковариационной матрицы. | ||
+ | * Параметрический наивный байесовский классификатор. | ||
+ | * [[Смесь распределений]]. | ||
+ | * [[EM-алгоритм]] как метод простых итераций для решения системы нелинейных уравнений. | ||
+ | * Выбор числа компонентов смеси. Пошаговая стратегия. Априорное распределение Дирихле. | ||
+ | * Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки. | ||
+ | * Сравнение RBF-сети и SVM с гауссовским ядром. | ||
+ | <!--- | ||
+ | * ''Связь линейного дискриминанта Фишера с [[метод наименьших квадратов|методом наименьших квадратов]].'' | ||
+ | * ''Матричное дифференцирование. Вывод оценок параметров многомерного нормального распределения.'' | ||
+ | * Жадное добавление признаков в линейном дискриминанте, ''[[метод редукции размерности]] Шурыгина.'' | ||
+ | * ''Робастное оценивание. Цензурирование выборки (отсев объектов-выбросов).'' | ||
+ | == Разделение смеси распределений == | ||
+ | Презентация: [[Media:Voron-ML-Bayes2-slides.pdf|(PDF, 1,7 МБ)]] {{важно|— обновление 27.04.2017}}. | ||
+ | * Детали реализации EM-алгоритма. Критерий останова. Выбор начального приближения. | ||
+ | * Обобщённый EM-алгоритм. Стохастический EM-алгоритм. Иерархический EM-алгоритм. | ||
+ | * Задача кластеризации. [[EM-алгоритм]] и [[Алгоритм k средних]] (k-means). | ||
+ | * Задача частичного обучения. | ||
+ | ---> | ||
- | + | == Кластеризация и частичное обучение == | |
+ | Презентация: [[Media:Voron-ML-Clustering-SSL-slides.pdf|(PDF, 1,8 МБ)]] {{важно|— обновление 14.12.2019}}. | ||
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач. Типы кластерных структур. | * Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач. Типы кластерных структур. | ||
+ | * Постановка задачи Semisupervised Learning, примеры приложений. | ||
+ | * Оптимизационные постановки задач кластеризации и частичного обучения. | ||
+ | * [[Алгоритм k-средних]] и [[ЕМ-алгоритм]] для разделения гауссовской смеси. | ||
* [[Графовые алгоритмы кластеризации]]. Выделение связных компонент. [[Кратчайший незамкнутый путь]]. | * [[Графовые алгоритмы кластеризации]]. Выделение связных компонент. [[Кратчайший незамкнутый путь]]. | ||
* [[Алгоритм ФОРЭЛ]]. | * [[Алгоритм ФОРЭЛ]]. | ||
- | * | + | * [[Алгоритм DBSCAN]]. |
- | + | ||
- | + | ||
- | + | ||
* [[Агломеративная кластеризация]], [[Алгоритм Ланса-Вильямса]] и его частные случаи. | * [[Агломеративная кластеризация]], [[Алгоритм Ланса-Вильямса]] и его частные случаи. | ||
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров. | * Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров. | ||
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма. | * Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма. | ||
+ | * Простые эвристические методы частичного обучения: self-training, co-training, co-learning. | ||
+ | * Трансдуктивный метод опорных векторов TSVM. | ||
+ | * Алгоритм Expectation-Regularization на основе многоклассовой регуляризированной логистической регрессии. | ||
+ | <!-- | ||
* ''Потоковые (субквадратичные) алгоритмы кластеризации.'' | * ''Потоковые (субквадратичные) алгоритмы кластеризации.'' | ||
- | + | * [[Многомерное шкалирование]], примеры прикладных задач. | |
- | + | * Субквадратичный алгоритм, псевдокод. Минимизация функционала стресса методом Ньютона-Рафсона. | |
- | * [[ | + | * Визуализация: [[карта сходства]], [[диаграмма Шепарда]]. |
- | * | + | * Совмещение многомерного шкалирования и иерархической кластеризации. |
- | * [[ | + | * [[Алгоритм t-SNE]] |
- | + | --> | |
- | + | ||
- | + | ||
- | * [[ | + | |
= Второй семестр = | = Второй семестр = | ||
- | == | + | == Нейронные сети: градиентные методы оптимизации == |
- | + | Презентация: [[Media:Voron-ML-NeuralNets1-2018-slides.pdf|(PDF, 1,4 МБ)]] {{важно|— обновление 23.09.2019}}. | |
- | + | * Биологический нейрон, [[модель МакКаллока-Питтса]] как [[линейный классификатор]]. Функции активации. | |
+ | * Проблема полноты. [[Задача исключающего или]]. Полнота двухслойных сетей в пространстве булевых функций. | ||
+ | <!--* ''Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).''--> | ||
+ | * [[Алгоритм обратного распространения ошибок]]. | ||
+ | * Быстрые методы стохастического градиента: Поляка, Нестерова, AdaGrad, RMSProp, AdaDelta, Adam, Nadam, [[диагональный метод Левенберга-Марквардта]]. | ||
+ | * Проблема взрыва градиента и эвристика gradient clipping. | ||
+ | * Метод случайных отключений нейронов (Dropout). Интерпретации Dropout. Обратный Dropout и L2-регуляризация. | ||
+ | * Функции активации ReLU и PReLU. Проблема [[паралич сети|«паралича» сети]]. | ||
+ | * Эвристики для формирования начального приближения. Метод послойной настройки сети. | ||
+ | * Подбор структуры сети: методы постепенного усложнения сети, [[оптимальное прореживание нейронных сетей]] (optimal brain damage). | ||
+ | <!--* [[Нейронная сеть Кохонена]]. [[Конкурентное обучение]], стратегии WTA и WTM. | ||
+ | * [[Самоорганизующаяся карта Кохонена]]. Применение для визуального анализа данных. Искусство интерпретации карт Кохонена.* [[Сети встречного распространения]], их применение для кусочно-постоянной и гладкой аппроксимации функций. | ||
+ | --> | ||
- | == | + | == Нейронные сети глубокого обучения == |
- | + | Презентация: [[Media:Voron-ML-DeepLearning-slides.pdf|(PDF, 3,4 МБ)]] {{важно|— обновление 14.12.2019}}. | |
- | * | + | * Свёрточные нейронные сети (CNN) для изображений. Свёрточный нейрон. Pooling нейрон. Выборка размеченных изображений ImageNet. |
- | * | + | * Свёрточные сети для сигналов, текстов, графов, игр. |
- | * | + | * Рекуррентные нейронные сети (RNN). Обучение рекуррентных сетей: Backpropagation Through Time (BPTT). |
- | * | + | * Сети долгой кратковременной памяти (Long short-term memory, LSTM). |
+ | * Рекуррентная сеть Gated Recurrent Unit (GRU). | ||
+ | * Автокодировщики. Векторные представления дискретных данных. | ||
+ | * Перенос обучения (transfer learning). | ||
+ | * Самообучение (self-supervised learning). | ||
+ | * Генеративные состязательные сети (GAN, generative adversarial net). | ||
- | == | + | == Линейные композиции, бустинг == |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
Текст лекций: [[Media:Voron-ML-Compositions.pdf|(PDF, 1 MБ)]].<br/> | Текст лекций: [[Media:Voron-ML-Compositions.pdf|(PDF, 1 MБ)]].<br/> | ||
- | Презентация: [[Media:Voron-ML-Compositions-slides.pdf|(PDF, | + | Презентация: [[Media:Voron-ML-Compositions-slides.pdf|(PDF, 0.9 МБ)]] {{важно|— обновление 14.12.2019}}. |
- | + | ||
- | + | ||
* Основные понятия: [[базовый алгоритм]] ([[алгоритмический оператор]]), [[корректирующая операция]]. | * Основные понятия: [[базовый алгоритм]] ([[алгоритмический оператор]]), [[корректирующая операция]]. | ||
* [[Взвешенное голосование]]. | * [[Взвешенное голосование]]. | ||
* [[Алгоритм AdaBoost]]. Экспоненциальная аппроксимация пороговой функции потерь. Процесс последовательного обучения базовых алгоритмов. Теорема о сходимости [[бустинг]]а. | * [[Алгоритм AdaBoost]]. Экспоненциальная аппроксимация пороговой функции потерь. Процесс последовательного обучения базовых алгоритмов. Теорема о сходимости [[бустинг]]а. | ||
+ | * Обобщающая способность бустинга. | ||
+ | * Базовые алгоритмы в бустинге. Решающие пни. | ||
* ''Варианты бустинга: [[GentleBoost]], [[LogitBoost]], [[BrownBoost]], и другие.'' | * ''Варианты бустинга: [[GentleBoost]], [[LogitBoost]], [[BrownBoost]], и другие.'' | ||
- | * | + | * [[Градиентный бустинг]]. Стохастический градиентный бустинг. |
+ | * [[Алгоритм AnyBoost]]. | ||
+ | * [[Алгоритм XGBoost]]. | ||
- | + | == Эвристические, стохастические, нелинейные композиции == | |
- | + | Презентация: [[Media:Voron-ML-Compositions-slides2.pdf|(PDF, 0.9 МБ)]] {{важно|— обновление 14.12.2019}}. | |
- | + | ||
* Стохастические методы: [[бэггинг]] и [[метод случайных подпространств]]. | * Стохастические методы: [[бэггинг]] и [[метод случайных подпространств]]. | ||
- | + | * [[Простое голосование]] (комитет большинства). Алгоритм ComBoost. Идентификация нетипичных объектов (выбросов). | |
+ | * Преобразование простого голосования во взвешенное. | ||
+ | * Обобщение на большое число классов. | ||
+ | * Случайный лес. | ||
+ | * Анализ смещения и вариации для простого голосования. | ||
+ | * [[Смесь алгоритмов]] (квазилинейная композиция), [[область компетентности]], примеры функций компетентности. | ||
+ | * Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический. | ||
+ | * Построение смеси алгоритмов с помощью EM-подобного алгоритма. | ||
<!--- | <!--- | ||
+ | * ''[[Решающий список]] (комитет старшинства). Алгоритм обучения. Стратегия выбора классов для базовых алгоритмов.'' | ||
+ | * ''Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии. Задача монотонизации выборки, изотонная регрессия.'' | ||
=== Метод комитетов === | === Метод комитетов === | ||
* Общее понятие: [[комитет]] системы ограничений. Комитеты большинства, простое и взвешенное голосование (''z,p''-комитеты). | * Общее понятие: [[комитет]] системы ограничений. Комитеты большинства, простое и взвешенное голосование (''z,p''-комитеты). | ||
Строка 246: | Строка 321: | ||
* [[Максимальная совместная подсистема]], [[минимальный комитет]]. Теоремы об ''NP''-полноте задачи поиска минимального комитета. | * [[Максимальная совместная подсистема]], [[минимальный комитет]]. Теоремы об ''NP''-полноте задачи поиска минимального комитета. | ||
* Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета. | * Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета. | ||
- | |||
=== Бустинг алгоритмов ранжирования === | === Бустинг алгоритмов ранжирования === | ||
* Задача ранжирования. Примеры: ранжирование результатов текстового поиска, задача [[Netflix]]. | * Задача ранжирования. Примеры: ранжирование результатов текстового поиска, задача [[Netflix]]. | ||
Строка 252: | Строка 326: | ||
* Бустинг алгоритмов ранжирования — аналоги AdaBoost и AnyBoost. | * Бустинг алгоритмов ранжирования — аналоги AdaBoost и AnyBoost. | ||
* Двудольная задача. Сведение попарного функционала качества к поточечному. | * Двудольная задача. Сведение попарного функционала качества к поточечному. | ||
- | + | === Взвешенное голосование логических закономерностей === | |
- | === | + | * Применение алгоритма бустинга [[AdaBoost]] к закономерностям. Критерий информативности в бустинге. |
- | * | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
* [[Решающий лес]] и бустинг над решающими деревьями. ''[[Алгоритм TreeNet]].'' | * [[Решающий лес]] и бустинг над решающими деревьями. ''[[Алгоритм TreeNet]].'' | ||
- | + | * ''Методы синтеза конъюнктивных закономерностей. Псевдокод: [[алгоритм КОРА]], [[алгоритм ТЭМП]].'' | |
- | + | * Эвристики, обеспечивающие различность и полезность закономерностей. Построение Парето-оптимальных закономерностей. Выравнивание распределения отступов. | |
- | * Методы синтеза конъюнктивных закономерностей. Псевдокод: [[алгоритм КОРА]], [[алгоритм ТЭМП]]. | + | * ''[[Чередующиеся решающие деревья]] (alternating decision tree).'' |
- | * | + | |
* Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов. | * Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов. | ||
- | |||
=== Алгоритмы вычисления оценок === | === Алгоритмы вычисления оценок === | ||
* [[Принцип частичной прецедентности]]. Структура [[Алгоритмы вычисления оценок|Алгоритмов вычисления оценок]]. | * [[Принцип частичной прецедентности]]. Структура [[Алгоритмы вычисления оценок|Алгоритмов вычисления оценок]]. | ||
Строка 289: | Строка 339: | ||
* Проблема оптимизации АВО. АВО как композиция метрических закономерностей. | * Проблема оптимизации АВО. АВО как композиция метрических закономерностей. | ||
* Применение бустинга, ТЭМП и СПА для оптимизации АВО. | * Применение бустинга, ТЭМП и СПА для оптимизации АВО. | ||
+ | ---> | ||
- | == | + | == Ранжирование == |
- | + | Презентация: [[Media:Voron-ML-Ranking-slides.pdf|(PDF, 0,5 МБ)]] {{важно|— обновление 14.12.2019}}. | |
- | * | + | * Постановка задачи [[Обучение ранжированию|обучения ранжированию]]. Примеры. |
- | * | + | * Признаки в задаче ранжирования поисковой выдачи: текстовые, ссылочные, кликовые. [[TF-IDF]]. [[PageRank]]. |
+ | * Критерии качества ранжирования: Precision, MAP, AUC, DCG, NDCG, pFound. | ||
+ | * Ранговая классификация, OC-SVM. | ||
+ | * Попарный подход: RankingSVM, RankNet, LambdaRank. | ||
- | == | + | == Рекомендательные системы == |
- | * | + | Презентация: [[Media:Voron-ML-CF.pdf|(PDF, 0.8 МБ)]] {{важно| — обновление 14.12.2019}}. |
- | * | + | * Задачи [[коллаборативная фильтрация|коллаборативной фильтрации]], [[транзакционные данные]] и матрица субъекты—объекты. |
- | * | + | * Корреляционные методы user-based, item-based. Задача восстановления пропущенных значений. Меры сходства субъектов и объектов. |
- | * | + | * ''Латентные методы на основе [[би-кластеризация|би-кластеризации]]. [[Алгоритм Брегмана]].'' |
- | * | + | * Латентные методы на основе матричных разложений. [[Метод главных компонент]] для разреженных данных (LFM, Latent Factor Model). [[Метод стохастического градиента]]. |
+ | * Неотрицательные матричные разложения. Метод чередующихся наименьших квадратов ALS. | ||
+ | * Модель с учётом неявной информации (implicit feedback). | ||
+ | * Рекомендации с учётом дополнительных признаковых данных. Линейная и квадратичная регрессионные модели, [[libFM]]. | ||
+ | * Измерение качества рекомендаций. Меры разнообразия (diversity), новизны (novelty), покрытия (coverage), догадливости (serendipity). | ||
+ | == Тематическое моделирование == | ||
+ | Текст лекций: [[Media:Voron-ML-TopicModels.pdf|(PDF, 830 КБ)]].<br/> | ||
<!--- | <!--- | ||
- | + | Презентация 1: [[Media:Voron-ML-TopicModels-slides.pdf|(PDF, 2.8 МБ)]] {{важно| — обновление 16.11.2015}}. | |
- | + | Презентация 2: [[Media:Voron-ML-TopicModels-slides-2.pdf|(PDF, 6.1 МБ)]] {{важно| — обновление 16.11.2015}}. | |
- | + | ||
- | + | ||
- | + | ||
---> | ---> | ||
+ | Презентация: [[Media:Voron-ML-TopicModeling-slides.pdf|(PDF, 1.6 МБ)]] {{важно| — обновление 14.12.2019}}. | ||
+ | * Задача [[тематическое моделирование|тематического моделирования]] коллекции текстовых документов. | ||
+ | * [[Вероятностный латентный семантический анализ]] PLSA. [[Метод максимума правдоподобия]]. [[ЕМ-алгоритм]]. Элементарная интерпретация EM-алгоритма. | ||
+ | * [[Латентное размещение Дирихле]] LDA. [[Метод максимума апостериорной вероятности]]. Сглаженная частотная оценка условной вероятности. | ||
+ | * Небайесовская интерпретация LDA и её преимущества. Регуляризаторы разреживания, сглаживания, частичного обучения. | ||
+ | * Аддитивная регуляризация тематических моделей. Регуляризованный EM-алгоритм, теорема о стационарной точке (применение условий Каруша–Куна–Таккера). | ||
+ | * Рациональный EM-алгоритм. Онлайновый EM-алгоритм и его распараллеливание. | ||
+ | * Мультимодальная тематическая модель. | ||
+ | * Регуляризаторы классификации и регрессии. | ||
+ | * Регуляризаторы декоррелирования и отбора тем. | ||
+ | * Внутренние и внешние критерии качества тематических моделей. | ||
+ | |||
+ | == Обучение с подкреплением == | ||
+ | Презентация: [[Media:Voron-ML-RL-slides.pdf|(PDF, 1.0 МБ)]] {{важно| — обновление 14.12.2019}}. | ||
+ | * Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound). Стратегия Softmax. | ||
+ | * Среда для экспериментов. | ||
+ | * Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования. | ||
+ | * Постановка задачи в случае, когда агент влияет на среду. Ценность состояния среды. Ценность действия. | ||
+ | * Жадные стратегии максимизации ценности. Уравнения оптимальности Беллмана. | ||
+ | * Метод временных разностей TD. Метод Q-обучения. | ||
+ | <!---* Многошаговое TD-прогнозирование. Обобщения методов временных разностей, SARSA, Q-обучения. ---> | ||
+ | * Градиентная оптимизация стратегии (policy gradient). Связь с максимизацией log-правдоподобия. | ||
+ | * Постановка задачи при наличии информации о среде в случае выбора действия. Контекстный многорукий бандит. | ||
+ | * Линейная регрессионная модель с верхней доверительной оценкой LinUCB. | ||
+ | * Оценивание новой стратегии по большим историческим данным. | ||
+ | <!---* Адаптивный полужадный метод VDBE.---> | ||
+ | |||
+ | == Активное обучение == | ||
+ | Презентация: [[Media:Voron-ML-AL-slides.pdf|(PDF, 1.2 МБ)]] {{важно| — обновление 14.12.2019}}. | ||
+ | * Постановка задачи машинного обучения. Основные стратегии: отбор объектов из выборки и из потока, синтез объектов. | ||
+ | * Сэмплирование по неуверенности. Почему активное обучение быстрее пассивного. | ||
+ | * Сэмплирование по несогласию в комитете. Сокращение пространства решений. | ||
+ | * Сэмплирование по ожидаемому изменению модели. | ||
+ | * Сэмплирование по ожидаемому сокращению ошибки. | ||
+ | * Синтез объектов по критерию сокращения дисперсии. | ||
+ | * Взвешивание по плотности. | ||
+ | * Оценивание качества активного обучения. | ||
+ | * Введение изучающих действий в стратегию активного обучении. Алгоритмы ε-active и EG-active. | ||
+ | * Применение обучения с подкреплением для активного обучения. Активное томпсоновское сэмплирование. | ||
+ | |||
+ | == Заключительная лекция == | ||
+ | Презентация: [[Media:Voron-ML-final.pdf|(PDF, 2.0 МБ)]] {{важно| — обновление 14.12.2019}}. | ||
+ | |||
+ | Обзор курса. Оптимизационные задачи машинного обучения. | ||
+ | |||
+ | = См. также = | ||
+ | * [https://www.coursera.org/learn/vvedenie-mashinnoe-obuchenie Курс «Введение в машинное обучение», К.В.Воронцов (ВШЭ и Яндекс)].[https://habrahabr.ru/company/yandex/blog/269175 Хабр об этом курсе]. | ||
+ | * [https://www.coursera.org/specializations/machine-learning-data-analysis Специализация «Машинное обучение и анализ данных» (МФТИ и Яндекс)]. [https://habrahabr.ru/company/yandex/blog/277427 Хабр об этом курсе]. | ||
+ | * [https://drive.google.com/open?id=0B-3LhgkjkY_OSDJncFdxTkFaOG8 Машинное обучение (семинары,ФУПМ МФТИ)] | ||
+ | * [[Машинное обучение (семинары, ВМК МГУ)]] | ||
+ | * [[Машинное обучение (курс лекций, Н.Ю.Золотых)]] | ||
+ | * [[Машинное обучение (курс лекций, СГАУ, С.Лисицын)]] | ||
+ | |||
+ | = Литература = | ||
+ | # ''Hastie T., Tibshirani R., Friedman J.'' The Elements of Statistical Learning. Springer, 2014. — 739 p. | ||
+ | # ''Bishop C. M.'' Pattern Recognition and Machine Learning. — Springer, 2006. — 738 p. | ||
+ | # ''Мерков А. Б.'' Распознавание образов. Введение в методы статистического обучения. 2011. 256 с. | ||
+ | # ''Мерков А. Б.'' Распознавание образов. Построение и обучение вероятностных моделей. 2014. 238 с. | ||
+ | # ''Коэльо Л.П., Ричарт В.'' Построение систем машинного обучения на языке Python. 2016. 302 с. | ||
- | + | = Список подстраниц = | |
{{Служебная:Prefixindex/Машинное обучение (курс лекций, К.В.Воронцов)/}} | {{Служебная:Prefixindex/Машинное обучение (курс лекций, К.В.Воронцов)/}} | ||
[[Категория:Учебные курсы]] | [[Категория:Учебные курсы]] |
Версия 19:54, 14 декабря 2019
Теория обучения машин (machine learning, машинное обучение) находится на стыке прикладной статистики, численных методов оптимизации, дискретного анализа, и за последние 50 лет оформилась в самостоятельную математическую дисциплину. Методы машинного обучения составляют основу ещё более молодой дисциплины — интеллектуального анализа данных (data mining).
В курсе рассматриваются основные задачи обучения по прецедентам: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.
Все методы излагаются по единой схеме:
- исходные идеи и эвристики;
- их формализация и математическая теория;
- описание алгоритма в виде слабо формализованного псевдокода;
- анализ достоинств, недостатков и границ применимости;
- пути устранения недостатков;
- сравнение с другими методами.
- примеры прикладных задач.
Данный курс расширяет и углубляет набор тем, рекомендованный международным стандартом ACM/IEEE Computing Curricula 2001 по дисциплине «Машинное обучение и нейронные сети» (machine learning and neural networks) в разделе «Интеллектуальные системы» (intelligent systems).
Курс читается
- студентам 3 курса кафедры «Интеллектуальные системы / интеллектуальный анализ данных» ФУПМ МФТИ с 2004 года;
- студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года;
- студентам Школы анализа данных Яндекса с 2009 года.
На материал данного курса опираются последующие кафедральные курсы.
От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание математической статистики, методов оптимизации и какого-либо языка программирования желательно, но не обязательно.
Ниже представлена расширенная программа — в полном объёме она занимает больше, чем могут вместить в себя два семестра. Каждый параграф приблизительно соответствует одной лекции. Курсивом выделен дополнительный материал, который может разбираться на семинарах.
Замечания для студентов
- Видеолекции ШАД Яндекс.
- «Введение в машинное обучение» на Курсэре содержит примерно втрое меньше материала, чем в годовом курсе, представленном на этой странице. Там очень многое упрощено, спрятано, пропущено. Действительно введение.
- На подстранице имеется перечень вопросов к устному экзамену. Очень помогает при подготовке к устному экзамену!
- О найденных ошибках и опечатках сообщайте мне. — К.В.Воронцов 18:24, 19 января 2009 (MSK)
- Материал, который есть в pdf-тексте, но не рассказывался на лекциях, обычно не входит в программу экзамена.
- Короткая ссылка на эту страницу: https://bit.ly/1bCmE3Z.
Первый семестр
Текст лекций: (PDF, 3 МБ) — обновление 4.10.2011.
Основные понятия и примеры прикладных задач
Презентация: (PDF, 1,4 МБ) — обновление 14.12.2019.
- Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
- Типы задач: классификация, регрессия, прогнозирование, ранжирование.
- Основные понятия: модель алгоритмов, метод обучения, функция потерь и функционал качества, принцип минимизации эмпирического риска, обобщающая способность, скользящий контроль.
- Линейные модели регрессии и классификации. Метод наименьших квадратов. Полиномиальная регрессия.
- Примеры прикладных задач.
- Методика экспериментального исследования и сравнения алгоритмов на модельных и реальных данных.
- Конкурсы по анализу данных kaggle.com. Полигон алгоритмов классификации.
- CRISP-DM — межотраслевой стандарт ведения проектов интеллектуального анализа данных.
Линейный классификатор и стохастический градиент
Презентация: (PDF, 1,1 МБ) — обновление 14.12.2019.
- Линейный классификатор, модель МакКаллока-Питтса, непрерывные аппроксимации пороговой функции потерь.
- Метод стохастического градиента SG.
- Метод стохастического среднего градиента SAG.
- Эвристики: инициализация весов, порядок предъявления объектов, выбор величины градиентного шага, «выбивание» из локальных минимумов.
- Проблема мультиколлинеарности и переобучения, регуляризация или редукция весов (weight decay).
- Вероятностная постановка задачи классификации. Принцип максимума правдоподобия.
- Вероятностная интерпретация регуляризации, совместное правдоподобие данных и модели. Принцип максимума апостериорной вероятности.
- Гауссовский и лапласовский регуляризаторы.
- Логистическая регрессия. Принцип максимума правдоподобия и логарифмическая функция потерь. Метод стохастического градиента для логарифмической функции потерь. Многоклассовая логистическая регрессия. Регуляризованная логистическая регрессия. Калибровка Платта.
Метрические методы классификации и регрессии
Презентация: (PDF, 3,2 МБ) — обновление 14.12.2019.
- Гипотезы компактности и непрерывности.
- Обобщённый метрический классификатор.
- Метод ближайших соседей kNN и его обобщения. Подбор числа k по критерию скользящего контроля.
- Метод окна Парзена с постоянной и переменной шириной окна.
- Метод потенциальных функций и его связь с линейной моделью классификации.
- Непараметрическая регрессия. Локально взвешенный метод наименьших квадратов. Ядерное сглаживание.
- Оценка Надарая-Ватсона с постоянной и переменной шириной окна. Выбор функции ядра.
- Задача отсева выбросов. Робастная непараметрическая регрессия. Алгоритм LOWESS.
- Задача отбора эталонов. Понятие отступа. Алгоритм СТОЛП.
- Задача отбора признаков. Жадный алгоритм построения метрики.
Метод опорных векторов
Презентация: (PDF, 1,1 МБ) — обновление 14.12.2019.
- Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin).
- Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь.
- Задача квадратичного программирования и двойственная задача. Понятие опорных векторов.
- Рекомендации по выбору константы C.
- Функция ядра (kernel functions), спрямляющее пространство, теорема Мерсера.
- Способы конструктивного построения ядер. Примеры ядер.
- SVM-регрессия.
- Регуляризации для отбора признаков: LASSO SVM, Elastic Net SVM, SFM, RFM.
- Метод релевантных векторов RVM
Многомерная линейная регрессия
Презентация: (PDF, 0,7 MБ) — обновление 14.12.2019.
- Задача регрессии, многомерная линейная регрессия.
- Метод наименьших квадратов, его вероятностный смысл и геометрический смысл.
- Сингулярное разложение.
- Проблемы мультиколлинеарности и переобучения.
- Регуляризация. Гребневая регрессия через сингулярное разложение.
- Методы отбора признаков: Лассо Тибширани, Elastic Net, сравнение с гребневой регрессией.
- Метод главных компонент и декоррелирующее преобразование Карунена-Лоэва, его связь с сингулярным разложением.
- Спектральный подход к решению задачи наименьших квадратов.
- Задачи и методы низкоранговых матричных разложений.
Нелинейная регрессия
Презентация: (PDF, 0,7 MБ) — обновление 14.12.2019.
- Метод Ньютона-Рафсона, метод Ньютона-Гаусса.
- Обобщённая аддитивная модель (GAM): метод настройки с возвращениями (backfitting) Хасти-Тибширани.
- Логистическая регрессия. Метод наименьших квадратов с итеративным пересчётом весов (IRLS). Пример прикладной задачи: кредитный скоринг. Бинаризация признаков. Скоринговые карты и оценивание вероятности дефолта. Риск кредитного портфеля банка.
- Обобщённая линейная модель (GLM). Экспоненциальное семейство распределений.
- Неквадратичные функции потерь. Метод наименьших модулей. Квантильная регрессия. Пример прикладной задачи: прогнозирование потребительского спроса.
- Робастная регрессия, функции потерь с горизонтальными асимптотами.
Прогнозирование временных рядов
Презентация: (PDF, 0,9 MБ) — обновление 14.12.2019.
- Задача прогнозирования временных рядов. Примеры приложений.
- Экспоненциальное скользящее среднее. Модель Хольта. Модель Тейла-Вейджа. Модель Хольта-Уинтерса.
- Адаптивная авторегрессионная модель.
- Следящий контрольный сигнал. Модель Тригга-Лича.
- Адаптивная селективная модель. Адаптивная композиция моделей.
- Локальная адаптация весов с регуляризацией.
Критерии выбора моделей и методы отбора признаков
Текст лекций: (PDF, 330 КБ).
Презентация: (PDF, 1,5 МБ) — обновление 14.12.2019.
- Критерии качества классификации: чувствительность и специфичность, ROC-кривая и AUC, точность и полнота, AUC-PR.
- Внутренние и внешние критерии. Эмпирические и аналитические критерии.
- Скользящий контроль, разновидности эмпирических оценок скользящего контроля. Критерий непротиворечивости.
- Разновидности аналитических оценок. Регуляризация. Критерий Акаике (AIC). Байесовский информационный критерий (BIC). Оценка Вапника-Червоненкиса.
- Сложность задачи отбора признаков. Полный перебор.
- Метод добавления и удаления, шаговая регрессия.
- Поиск в глубину, метод ветвей и границ.
- Усечённый поиск в ширину, многорядный итерационный алгоритм МГУА.
- Генетический алгоритм, его сходство с МГУА.
- Случайный поиск и Случайный поиск с адаптацией (СПА).
Логические методы классификации
Текст лекций: (PDF, 625 КБ).
Презентация: (PDF, 1.8 МБ) — обновление 14.12.2019.
- Понятие логической закономерности.
- Параметрические семейства закономерностей: конъюнкции пороговых правил, синдромные правила, шары, гиперплоскости.
- Переборные алгоритмы синтеза конъюнкций: стохастический локальный поиск, стабилизация, редукция.
- Двухкритериальный отбор информативных закономерностей, парето-оптимальный фронт в (p,n)-пространстве.
- Решающее дерево. Жадная нисходящая стратегия «разделяй и властвуй». Алгоритм ID3. Недостатки жадной стратегии и способы их устранения. Проблема переобучения.
- Вывод критериев ветвления. Мера нечистоты (impurity) распределения. Энтропийный критерий, критерий Джини.
- Редукция решающих деревьев: предредукция и постредукция. Алгоритм C4.5.
- Деревья регрессии. Алгоритм CART.
- Небрежные решающие деревья (oblivious decision tree).
- Решающий лес. Случайный лес (Random Forest).
Факультатив
- Статистический критерий информативности, точный тест Фишера. Сравнение областей эвристических и статистических закономерностей. Асимптотическая эквивалентность статистического и энтропийного критерия информативности. Разнообразие критериев информативности в (p,n)-пространстве.
- Решающий пень. Бинаризация признаков. Алгоритм разбиения области значений признака на информативные зоны.
- Решающий список. Жадный алгоритм синтеза списка.
- Преобразование решающего дерева в решающий список.
Поиск ассоциативных правил
Презентация: (PDF, 1.1 МБ) — обновление 14.12.2019.
- Понятие ассоциативного правила и его связь с понятием логической закономерности.
- Примеры прикладных задач: анализ рыночных корзин, выделение терминов и тематики текстов.
- Алгоритм APriori. Два этапа: поиск частых наборов и рекурсивное порождение ассоциативных правил. Недостатки и пути усовершенствования алгоритма APriori.
- Алгоритм FP-growth. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов.
- Общее представление о динамических и иерархических методах поиска ассоциативных правил.
Байесовская классификация и оценивание плотности
Презентация: (PDF, 1,6 МБ) — обновление 14.12.2019.
- Принцип максимума апостериорной вероятности. Теорема об оптимальности байесовского классификатора.
- Оценивание плотности распределения: три основных подхода.
- Наивный байесовский классификатор.
- Непараметрическое оценивание плотности. Ядерная оценка плотности Парзена-Розенблатта. Одномерный и многомерный случаи.
- Метод парзеновского окна. Выбор функции ядра. Выбор ширины окна, переменная ширина окна.
- Параметрическое оценивание плотности. Нормальный дискриминантный анализ.
- Многомерное нормальное распределение, геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения.
- Квадратичный дискриминант. Вид разделяющей поверхности. Подстановочный алгоритм, его недостатки и способы их устранения.
- Линейный дискриминант Фишера.
- Проблемы мультиколлинеарности и переобучения. Регуляризация ковариационной матрицы.
- Параметрический наивный байесовский классификатор.
- Смесь распределений.
- EM-алгоритм как метод простых итераций для решения системы нелинейных уравнений.
- Выбор числа компонентов смеси. Пошаговая стратегия. Априорное распределение Дирихле.
- Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.
- Сравнение RBF-сети и SVM с гауссовским ядром.
Кластеризация и частичное обучение
Презентация: (PDF, 1,8 МБ) — обновление 14.12.2019.
- Постановка задачи кластеризации. Примеры прикладных задач. Типы кластерных структур.
- Постановка задачи Semisupervised Learning, примеры приложений.
- Оптимизационные постановки задач кластеризации и частичного обучения.
- Алгоритм k-средних и ЕМ-алгоритм для разделения гауссовской смеси.
- Графовые алгоритмы кластеризации. Выделение связных компонент. Кратчайший незамкнутый путь.
- Алгоритм ФОРЭЛ.
- Алгоритм DBSCAN.
- Агломеративная кластеризация, Алгоритм Ланса-Вильямса и его частные случаи.
- Алгоритм построения дендрограммы. Определение числа кластеров.
- Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
- Простые эвристические методы частичного обучения: self-training, co-training, co-learning.
- Трансдуктивный метод опорных векторов TSVM.
- Алгоритм Expectation-Regularization на основе многоклассовой регуляризированной логистической регрессии.
Второй семестр
Нейронные сети: градиентные методы оптимизации
Презентация: (PDF, 1,4 МБ) — обновление 23.09.2019.
- Биологический нейрон, модель МакКаллока-Питтса как линейный классификатор. Функции активации.
- Проблема полноты. Задача исключающего или. Полнота двухслойных сетей в пространстве булевых функций.
- Алгоритм обратного распространения ошибок.
- Быстрые методы стохастического градиента: Поляка, Нестерова, AdaGrad, RMSProp, AdaDelta, Adam, Nadam, диагональный метод Левенберга-Марквардта.
- Проблема взрыва градиента и эвристика gradient clipping.
- Метод случайных отключений нейронов (Dropout). Интерпретации Dropout. Обратный Dropout и L2-регуляризация.
- Функции активации ReLU и PReLU. Проблема «паралича» сети.
- Эвристики для формирования начального приближения. Метод послойной настройки сети.
- Подбор структуры сети: методы постепенного усложнения сети, оптимальное прореживание нейронных сетей (optimal brain damage).
Нейронные сети глубокого обучения
Презентация: (PDF, 3,4 МБ) — обновление 14.12.2019.
- Свёрточные нейронные сети (CNN) для изображений. Свёрточный нейрон. Pooling нейрон. Выборка размеченных изображений ImageNet.
- Свёрточные сети для сигналов, текстов, графов, игр.
- Рекуррентные нейронные сети (RNN). Обучение рекуррентных сетей: Backpropagation Through Time (BPTT).
- Сети долгой кратковременной памяти (Long short-term memory, LSTM).
- Рекуррентная сеть Gated Recurrent Unit (GRU).
- Автокодировщики. Векторные представления дискретных данных.
- Перенос обучения (transfer learning).
- Самообучение (self-supervised learning).
- Генеративные состязательные сети (GAN, generative adversarial net).
Линейные композиции, бустинг
Текст лекций: (PDF, 1 MБ).
Презентация: (PDF, 0.9 МБ) — обновление 14.12.2019.
- Основные понятия: базовый алгоритм (алгоритмический оператор), корректирующая операция.
- Взвешенное голосование.
- Алгоритм AdaBoost. Экспоненциальная аппроксимация пороговой функции потерь. Процесс последовательного обучения базовых алгоритмов. Теорема о сходимости бустинга.
- Обобщающая способность бустинга.
- Базовые алгоритмы в бустинге. Решающие пни.
- Варианты бустинга: GentleBoost, LogitBoost, BrownBoost, и другие.
- Градиентный бустинг. Стохастический градиентный бустинг.
- Алгоритм AnyBoost.
- Алгоритм XGBoost.
Эвристические, стохастические, нелинейные композиции
Презентация: (PDF, 0.9 МБ) — обновление 14.12.2019.
- Стохастические методы: бэггинг и метод случайных подпространств.
- Простое голосование (комитет большинства). Алгоритм ComBoost. Идентификация нетипичных объектов (выбросов).
- Преобразование простого голосования во взвешенное.
- Обобщение на большое число классов.
- Случайный лес.
- Анализ смещения и вариации для простого голосования.
- Смесь алгоритмов (квазилинейная композиция), область компетентности, примеры функций компетентности.
- Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
- Построение смеси алгоритмов с помощью EM-подобного алгоритма.
Ранжирование
Презентация: (PDF, 0,5 МБ) — обновление 14.12.2019.
- Постановка задачи обучения ранжированию. Примеры.
- Признаки в задаче ранжирования поисковой выдачи: текстовые, ссылочные, кликовые. TF-IDF. PageRank.
- Критерии качества ранжирования: Precision, MAP, AUC, DCG, NDCG, pFound.
- Ранговая классификация, OC-SVM.
- Попарный подход: RankingSVM, RankNet, LambdaRank.
Рекомендательные системы
Презентация: (PDF, 0.8 МБ) — обновление 14.12.2019.
- Задачи коллаборативной фильтрации, транзакционные данные и матрица субъекты—объекты.
- Корреляционные методы user-based, item-based. Задача восстановления пропущенных значений. Меры сходства субъектов и объектов.
- Латентные методы на основе би-кластеризации. Алгоритм Брегмана.
- Латентные методы на основе матричных разложений. Метод главных компонент для разреженных данных (LFM, Latent Factor Model). Метод стохастического градиента.
- Неотрицательные матричные разложения. Метод чередующихся наименьших квадратов ALS.
- Модель с учётом неявной информации (implicit feedback).
- Рекомендации с учётом дополнительных признаковых данных. Линейная и квадратичная регрессионные модели, libFM.
- Измерение качества рекомендаций. Меры разнообразия (diversity), новизны (novelty), покрытия (coverage), догадливости (serendipity).
Тематическое моделирование
Текст лекций: (PDF, 830 КБ).
Презентация: (PDF, 1.6 МБ) — обновление 14.12.2019.
- Задача тематического моделирования коллекции текстовых документов.
- Вероятностный латентный семантический анализ PLSA. Метод максимума правдоподобия. ЕМ-алгоритм. Элементарная интерпретация EM-алгоритма.
- Латентное размещение Дирихле LDA. Метод максимума апостериорной вероятности. Сглаженная частотная оценка условной вероятности.
- Небайесовская интерпретация LDA и её преимущества. Регуляризаторы разреживания, сглаживания, частичного обучения.
- Аддитивная регуляризация тематических моделей. Регуляризованный EM-алгоритм, теорема о стационарной точке (применение условий Каруша–Куна–Таккера).
- Рациональный EM-алгоритм. Онлайновый EM-алгоритм и его распараллеливание.
- Мультимодальная тематическая модель.
- Регуляризаторы классификации и регрессии.
- Регуляризаторы декоррелирования и отбора тем.
- Внутренние и внешние критерии качества тематических моделей.
Обучение с подкреплением
Презентация: (PDF, 1.0 МБ) — обновление 14.12.2019.
- Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound). Стратегия Softmax.
- Среда для экспериментов.
- Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования.
- Постановка задачи в случае, когда агент влияет на среду. Ценность состояния среды. Ценность действия.
- Жадные стратегии максимизации ценности. Уравнения оптимальности Беллмана.
- Метод временных разностей TD. Метод Q-обучения.
- Градиентная оптимизация стратегии (policy gradient). Связь с максимизацией log-правдоподобия.
- Постановка задачи при наличии информации о среде в случае выбора действия. Контекстный многорукий бандит.
- Линейная регрессионная модель с верхней доверительной оценкой LinUCB.
- Оценивание новой стратегии по большим историческим данным.
Активное обучение
Презентация: (PDF, 1.2 МБ) — обновление 14.12.2019.
- Постановка задачи машинного обучения. Основные стратегии: отбор объектов из выборки и из потока, синтез объектов.
- Сэмплирование по неуверенности. Почему активное обучение быстрее пассивного.
- Сэмплирование по несогласию в комитете. Сокращение пространства решений.
- Сэмплирование по ожидаемому изменению модели.
- Сэмплирование по ожидаемому сокращению ошибки.
- Синтез объектов по критерию сокращения дисперсии.
- Взвешивание по плотности.
- Оценивание качества активного обучения.
- Введение изучающих действий в стратегию активного обучении. Алгоритмы ε-active и EG-active.
- Применение обучения с подкреплением для активного обучения. Активное томпсоновское сэмплирование.
Заключительная лекция
Презентация: (PDF, 2.0 МБ) — обновление 14.12.2019.
Обзор курса. Оптимизационные задачи машинного обучения.
См. также
- Курс «Введение в машинное обучение», К.В.Воронцов (ВШЭ и Яндекс).Хабр об этом курсе.
- Специализация «Машинное обучение и анализ данных» (МФТИ и Яндекс). Хабр об этом курсе.
- Машинное обучение (семинары,ФУПМ МФТИ)
- Машинное обучение (семинары, ВМК МГУ)
- Машинное обучение (курс лекций, Н.Ю.Золотых)
- Машинное обучение (курс лекций, СГАУ, С.Лисицын)
Литература
- Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Springer, 2014. — 739 p.
- Bishop C. M. Pattern Recognition and Machine Learning. — Springer, 2006. — 738 p.
- Мерков А. Б. Распознавание образов. Введение в методы статистического обучения. 2011. 256 с.
- Мерков А. Б. Распознавание образов. Построение и обучение вероятностных моделей. 2014. 238 с.
- Коэльо Л.П., Ричарт В. Построение систем машинного обучения на языке Python. 2016. 302 с.
Список подстраниц
Машинное обучение (курс лекций, К.В.Воронцов)/2009 | Машинное обучение (курс лекций, К.В.Воронцов)/ToDo | Машинное обучение (курс лекций, К.В.Воронцов)/Вопросы |
Машинное обучение (курс лекций, К.В.Воронцов)/Семестровый курс | Машинное обучение (курс лекций, К.В.Воронцов)/Форма отчета |