Машинное обучение (курс лекций, К.В.Воронцов)

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

(Различия между версиями)
Перейти к: навигация, поиск
м (Нейронные сети с обучением без учителя)
м (Ранжирование)
(21 промежуточная версия не показана)
Строка 126: Строка 126:
== Многомерная линейная регрессия ==
== Многомерная линейная регрессия ==
-
Презентация: [[Media:Voron-ML-regression-slides.pdf|(PDF, 0,7 MБ)]] {{важно|— обновление 14.12.2019}}.
+
Презентация: [[Media:Voron-ML-regression-slides.pdf|(PDF, 1,2 MБ)]] {{важно|— обновление 10.10.2020}}.
* Задача регрессии, [[многомерная линейная регрессия]].
* Задача регрессии, [[многомерная линейная регрессия]].
* [[Метод наименьших квадратов]], его вероятностный смысл и геометрический смысл.
* [[Метод наименьших квадратов]], его вероятностный смысл и геометрический смысл.
Строка 144: Строка 144:
== Нелинейная регрессия ==
== Нелинейная регрессия ==
-
Презентация: [[Media:Voron-ML-regress-non-slides.pdf|(PDF, 0,7 MБ)]] {{важно|— обновление 14.12.2019}}.
+
Презентация: [[Media:Voron-ML-regress-non-slides.pdf|(PDF, 0,7 MБ)]] {{важно|— обновление 17.10.2020}}.
* [[Метод Ньютона-Рафсона]], [[метод Ньютона-Гаусса]].
* [[Метод Ньютона-Рафсона]], [[метод Ньютона-Гаусса]].
* Обобщённая аддитивная модель (GAM): [[метод настройки с возвращениями]] (backfitting) Хасти-Тибширани.
* Обобщённая аддитивная модель (GAM): [[метод настройки с возвращениями]] (backfitting) Хасти-Тибширани.
Строка 157: Строка 157:
== Критерии выбора моделей и методы отбора признаков ==
== Критерии выбора моделей и методы отбора признаков ==
Текст лекций: [[Media:Voron-ML-Modeling.pdf|(PDF,&nbsp;330&nbsp;КБ)]].<br/>
Текст лекций: [[Media:Voron-ML-Modeling.pdf|(PDF,&nbsp;330&nbsp;КБ)]].<br/>
-
Презентация: [[Media:Voron-ML-Quality-slides.pdf|(PDF,&nbsp;1,5&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
+
Презентация: [[Media:Voron-ML-Quality-slides.pdf|(PDF,&nbsp;1,5&nbsp;МБ)]] {{важно|— обновление 25.10.2020}}.
* Критерии качества классификации: чувствительность и специфичность, ROC-кривая и AUC, точность и полнота, AUC-PR.
* Критерии качества классификации: чувствительность и специфичность, ROC-кривая и AUC, точность и полнота, AUC-PR.
Строка 181: Строка 181:
== Логические методы классификации ==
== Логические методы классификации ==
Текст лекций: [[Media:Voron-ML-Logic.pdf|(PDF,&nbsp;625&nbsp;КБ)]].<br/>
Текст лекций: [[Media:Voron-ML-Logic.pdf|(PDF,&nbsp;625&nbsp;КБ)]].<br/>
-
Презентация: [[Media:Voron-ML-Logic-slides.pdf|(PDF,&nbsp;1.8&nbsp;МБ)]] {{важно| — обновление 05.03.2030}}.
+
Презентация: [[Media:Voron-ML-Logic-slides.pdf|(PDF,&nbsp;1.8&nbsp;МБ)]] {{важно| — обновление 20.10.2020}}.
* Понятие [[логическая закономерность|логической закономерности]].
* Понятие [[логическая закономерность|логической закономерности]].
Строка 187: Строка 187:
* Переборные алгоритмы синтеза конъюнкций: [[стохастический локальный поиск]], [[стабилизация]], [[редукция]].
* Переборные алгоритмы синтеза конъюнкций: [[стохастический локальный поиск]], [[стабилизация]], [[редукция]].
* Двухкритериальный отбор информативных закономерностей, парето-оптимальный фронт в (p,n)-пространстве.
* Двухкритериальный отбор информативных закономерностей, парето-оптимальный фронт в (p,n)-пространстве.
 +
* Статистический критерий информативности, [[точный тест Фишера]]. Сравнение областей эвристических и статистических закономерностей. Разнообразие критериев информативности в (p,n)-пространстве.
* [[Решающее дерево]]. Жадная нисходящая стратегия «разделяй и властвуй». [[Алгоритм ID3]]. Недостатки жадной стратегии и способы их устранения. Проблема переобучения.
* [[Решающее дерево]]. Жадная нисходящая стратегия «разделяй и властвуй». [[Алгоритм ID3]]. Недостатки жадной стратегии и способы их устранения. Проблема переобучения.
* Вывод критериев ветвления. Мера нечистоты (impurity) распределения. Энтропийный критерий, критерий Джини.
* Вывод критериев ветвления. Мера нечистоты (impurity) распределения. Энтропийный критерий, критерий Джини.
Строка 193: Строка 194:
* [[Небрежные решающие деревья]] (oblivious decision tree).
* [[Небрежные решающие деревья]] (oblivious decision tree).
* Решающий лес. [[Случайный лес]] (Random Forest).
* Решающий лес. [[Случайный лес]] (Random Forest).
 +
* Решающий пень. [[Бинаризация признаков]]. Алгоритм разбиения области значений признака на информативные зоны.
 +
* [[Решающий список]]. Жадный алгоритм синтеза списка. Преобразование решающего дерева в решающий список.
'''Факультатив'''
'''Факультатив'''
-
* Статистический критерий информативности, [[точный тест Фишера]]. Сравнение областей эвристических и статистических закономерностей. Асимптотическая эквивалентность статистического и энтропийного критерия информативности. Разнообразие критериев информативности в (p,n)-пространстве.
+
* Асимптотическая эквивалентность статистического и энтропийного критерия информативности.
-
* Решающий пень. [[Бинаризация признаков]]. Алгоритм разбиения области значений признака на информативные зоны.
+
-
* [[Решающий список]]. Жадный алгоритм синтеза списка.
+
-
* Преобразование решающего дерева в решающий список.
+
-
== Линейные композиции, бустинг ==
+
== Поиск ассоциативных правил ==
 +
Презентация: [[Media:Voron-ML-AssocRules-slides.pdf|(PDF,&nbsp;1.3&nbsp;МБ)]] {{важно| — обновление 7.11.2020}}.
 +
 
 +
* Понятие [[Ассоциативное правило|ассоциативного правила]] и его связь с понятием логической закономерности.
 +
* Примеры прикладных задач: [[анализ рыночных корзин]], выделение терминов и тематики текстов.
 +
* [[Алгоритм APriori]]. Два этапа: поиск частых наборов и рекурсивное порождение ассоциативных правил. Недостатки и пути усовершенствования алгоритма APriori.
 +
* [[Алгоритм FP-growth]]. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов.
 +
* Общее представление о динамических и иерархических методах поиска ассоциативных правил.
 +
 
 +
== Линейные ансамбли ==
Текст лекций: [[Media:Voron-ML-Compositions.pdf|(PDF,&nbsp;1&nbsp;MБ)]].<br/>
Текст лекций: [[Media:Voron-ML-Compositions.pdf|(PDF,&nbsp;1&nbsp;MБ)]].<br/>
-
Презентация: [[Media:Voron-ML-Compositions-slides.pdf|(PDF,&nbsp;0.9&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
+
Презентация: [[Media:Voron-ML-Compositions1-slides.pdf|(PDF,&nbsp;1.0&nbsp;МБ)]] {{важно|— обновление 14.11.2020}}.
-
* Основные понятия: [[базовый алгоритм]] ([[алгоритмический оператор]]), [[корректирующая операция]].
+
 
-
* [[Взвешенное голосование]].
+
* Основные понятия: [[базовый алгоритм]], [[корректирующая операция]].
-
* [[Алгоритм AdaBoost]]. Экспоненциальная аппроксимация пороговой функции потерь. Процесс последовательного обучения базовых алгоритмов. Теорема о сходимости [[бустинг]]а.
+
* [[Простое голосование]] (комитет большинства).
-
* Обобщающая способность бустинга.
+
* Стохастические методы: [[бэггинг]] и [[метод случайных подпространств]].
 +
* [[Случайный лес]] (Random Forest).
 +
* [[Взвешенное голосование]]. Преобразование простого голосования во взвешенное.
 +
* [[Алгоритм AdaBoost]]. Экспоненциальная аппроксимация пороговой функции потерь. Процесс последовательного обучения базовых алгоритмов. Теорема о сходимости [[бустинг]]а. Идентификация нетипичных объектов (выбросов).
 +
* Теоретические обоснования. Обобщающая способность бустинга.
* Базовые алгоритмы в бустинге. Решающие пни.
* Базовые алгоритмы в бустинге. Решающие пни.
-
* ''Варианты бустинга: [[GentleBoost]], [[LogitBoost]], [[BrownBoost]], и другие.''
+
* Сравнение бэггинга и бустинга.
 +
* [[Алгоритм ComBoost]]. Обобщение на большое число классов.
 +
 
 +
== Продвинутые методы ансамблирования ==
 +
Презентация: [[Media:Voron-ML-Compositions-slides2.pdf|(PDF,&nbsp;1.2&nbsp;МБ)]] {{важно|— обновление 22.11.2020}}.
 +
 
 +
* Виды ансамблей. Теоретические обоснования. Анализ смещения и разброса для простого голосования.
* [[Градиентный бустинг]]. Стохастический градиентный бустинг.
* [[Градиентный бустинг]]. Стохастический градиентный бустинг.
-
* [[Алгоритм AnyBoost]].
+
* Варианты бустинга: регрессия, [[Алгоритм AnyBoost]], [[GentleBoost]], [[LogitBoost]], [[BrownBoost]], и другие.
-
* [[Алгоритм XGBoost]].
+
* [[Алгоритм XGBoost]].
 +
* [[Алгоритм CatBoost]]. Обработка категориальных признаков.
 +
* [[Стэкинг]]. Линейный стэкинг, взвешенный по признакам.
 +
* [[Смесь алгоритмов]] (квазилинейная композиция), [[область компетентности]], примеры функций компетентности.
 +
* Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
 +
* Построение смеси алгоритмов с помощью EM-подобного алгоритма.
 +
<!---
 +
* ''[[Решающий список]] (комитет старшинства). Алгоритм обучения. Стратегия выбора классов для базовых алгоритмов.''
 +
* ''Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии. Задача монотонизации выборки, изотонная регрессия.''
 +
=== Метод комитетов ===
 +
* Общее понятие: [[комитет]] системы ограничений. Комитеты большинства, простое и взвешенное голосование (''z,p''-комитеты).
 +
* Теоремы о существовании комитетного решения.
 +
* Сопоставление комитета линейных неравенств с нейронной сетью.
 +
* [[Максимальная совместная подсистема]], [[минимальный комитет]]. Теоремы об ''NP''-полноте задачи поиска минимального комитета.
 +
* Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.
 +
=== Бустинг алгоритмов ранжирования ===
 +
* Задача ранжирования. Примеры: ранжирование результатов текстового поиска, задача [[Netflix]].
 +
* Функционал качества — число дефектных пар.
 +
* Бустинг алгоритмов ранжирования — аналоги AdaBoost и AnyBoost.
 +
* Двудольная задача. Сведение попарного функционала качества к поточечному.
 +
=== Взвешенное голосование логических закономерностей ===
 +
* Применение алгоритма бустинга [[AdaBoost]] к закономерностям. Критерий информативности в бустинге.
 +
* [[Решающий лес]] и бустинг над решающими деревьями. ''[[Алгоритм TreeNet]].''
 +
* ''Методы синтеза конъюнктивных закономерностей. Псевдокод: [[алгоритм КОРА]], [[алгоритм ТЭМП]].''
 +
* Эвристики, обеспечивающие различность и полезность закономерностей. Построение Парето-оптимальных закономерностей. Выравнивание распределения отступов.
 +
* ''[[Чередующиеся решающие деревья]] (alternating decision tree).''
 +
* Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
 +
=== Алгоритмы вычисления оценок ===
 +
* [[Принцип частичной прецедентности]]. Структура [[Алгоритмы вычисления оценок|Алгоритмов вычисления оценок]].
 +
* [[Тупиковые тесты]].
 +
* [[Тупиковые представительные наборы]].
 +
* Проблема оптимизации АВО. АВО как композиция метрических закономерностей.
 +
* Применение бустинга, ТЭМП и СПА для оптимизации АВО.
 +
--->
== Байесовская классификация и оценивание плотности ==
== Байесовская классификация и оценивание плотности ==
Строка 247: Строка 299:
== Кластеризация и частичное обучение ==
== Кластеризация и частичное обучение ==
Презентация: [[Media:Voron-ML-Clustering-SSL-slides.pdf|(PDF,&nbsp;1,8&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
Презентация: [[Media:Voron-ML-Clustering-SSL-slides.pdf|(PDF,&nbsp;1,8&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
 +
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач. Типы кластерных структур.
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач. Типы кластерных структур.
* Постановка задачи Semisupervised Learning, примеры приложений.
* Постановка задачи Semisupervised Learning, примеры приложений.
Строка 271: Строка 324:
= Семестр 2. Прикладные модели машинного обучения =
= Семестр 2. Прикладные модели машинного обучения =
-
== Прогнозирование временных рядов ==
+
== Нейронные сети глубокого обучения ==
-
Презентация: [[Media:Voron-ML-forecasting-slides.pdf|(PDF,&nbsp;0,9&nbsp;MБ)]] {{важно|— обновление 14.12.2019}}.
+
Презентация: [[Media:Voron-ML-DeepLearning-slides.pdf|(PDF,&nbsp;1,6&nbsp;МБ)]] {{важно|— обновление 15.11.2020}}.
-
* Задача прогнозирования временных рядов. Примеры приложений.
+
-
* [[Экспоненциальное сглаживание|Экспоненциальное скользящее среднее]]. [[Модель Хольта]]. [[Модель Тейла-Вейджа]]. [[Модель Хольта-Уинтерса]].
+
-
* Адаптивная авторегрессионная модель.
+
-
* [[Следящий контрольный сигнал]]. [[Модель Тригга-Лича]].
+
-
* Адаптивная селективная модель. Адаптивная композиция моделей.
+
-
* Локальная адаптация весов с регуляризацией.
+
-
 
+
-
== Поиск ассоциативных правил ==
+
-
Презентация: [[Media:Voron-ML-AssocRules-slides.pdf|(PDF,&nbsp;1.1&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
+
-
* Понятие [[Ассоциативное правило|ассоциативного правила]] и его связь с понятием логической закономерности.
+
-
* Примеры прикладных задач: [[анализ рыночных корзин]], выделение терминов и тематики текстов.
+
-
* [[Алгоритм APriori]]. Два этапа: поиск частых наборов и рекурсивное порождение ассоциативных правил. Недостатки и пути усовершенствования алгоритма APriori.
+
-
* [[Алгоритм FP-growth]]. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов.
+
-
* Общее представление о динамических и иерархических методах поиска ассоциативных правил.
+
-
== Нейронные сети глубокого обучения ==
 
-
Презентация: [[Media:Voron-ML-DeepLearning-slides.pdf|(PDF,&nbsp;3,4&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
 
* Свёрточные нейронные сети (CNN) для изображений. Свёрточный нейрон. Pooling нейрон. Выборка размеченных изображений ImageNet.
* Свёрточные нейронные сети (CNN) для изображений. Свёрточный нейрон. Pooling нейрон. Выборка размеченных изображений ImageNet.
* Свёрточные сети для сигналов, текстов, графов, игр.
* Свёрточные сети для сигналов, текстов, графов, игр.
Строка 302: Строка 339:
== Нейронные сети с обучением без учителя ==
== Нейронные сети с обучением без учителя ==
Презентация: [[Media:Voron-ML-ANN-Unsupervised-slides.pdf|(PDF,&nbsp;2,3&nbsp;МБ)]] {{важно|— обновление 03.10.2020}}.
Презентация: [[Media:Voron-ML-ANN-Unsupervised-slides.pdf|(PDF,&nbsp;2,3&nbsp;МБ)]] {{важно|— обновление 03.10.2020}}.
 +
* [[Нейронная сеть Кохонена]]. [[Конкурентное обучение]], стратегии WTA и WTM.
* [[Нейронная сеть Кохонена]]. [[Конкурентное обучение]], стратегии WTA и WTM.
* [[Самоорганизующаяся карта Кохонена]]. Применение для визуального анализа данных. Искусство интерпретации карт Кохонена.
* [[Самоорганизующаяся карта Кохонена]]. Применение для визуального анализа данных. Искусство интерпретации карт Кохонена.
Строка 313: Строка 351:
* Генеративные состязательные сети (GAN).
* Генеративные состязательные сети (GAN).
-
== Эвристические, стохастические, нелинейные композиции ==
+
== Векторные представления текстов и графов ==
-
Презентация: [[Media:Voron-ML-Compositions-slides2.pdf|(PDF,&nbsp;0.9&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
+
Презентация: [[Media:Voron-ML-Embeddings-slides.pdf|(PDF,&nbsp;1,3&nbsp;МБ)]] {{важно|— обновление 14.10.2020}}.
-
* Стохастические методы: [[бэггинг]] и [[метод случайных подпространств]].
+
 
-
* [[Простое голосование]] (комитет большинства). Алгоритм ComBoost. Идентификация нетипичных объектов (выбросов).
+
* Векторные представления текста. Гипотеза дистрибутивной семантики.
-
* Преобразование простого голосования во взвешенное.
+
* Модели [[word2vec]], [[FastText]].
-
* Обобщение на большое число классов.
+
* Векторные представления графов.
-
* Случайный лес.
+
* [[Многомерное шкалирование]].
-
* Анализ смещения и вариации для простого голосования.
+
* Модели случайных блужданий [[DeepWalk]], [[node2vec]].
-
* [[Смесь алгоритмов]] (квазилинейная композиция), [[область компетентности]], примеры функций компетентности.
+
* Обобщённый автокодировщик на графах [[GraphEDM]].
-
* Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
+
* Векторные представления гиперграфов.
-
* Построение смеси алгоритмов с помощью EM-подобного алгоритма.
+
* Тематические модели транзакционных данных. EM-алгоритм для тематической модели гиперграфа.
 +
* Примеры транзакционных моделей на гиперграфах.
 +
 
 +
== Модели внимания и трансформеры ==
 +
Презентация: [[Media:Voron-ML-Attention-slides.pdf|(PDF,&nbsp;1,1&nbsp;МБ)]] {{важно|— обновление 7.11.2020}}.
 +
* Задачи обработки последовательностей.
 +
* Рекуррентная сеть с моделью внимания. Разновидности моделей внимания.
 +
* Критерии обучения и оценивание качества (предобучение).
 +
* Прикладные задачи: машинный перевод, аннотирование изображений (эквивалентность MHSA и CNN).
 +
* Модели внимания на графах.
 +
* Трансформеры для текстов, изображений, графов.
 +
 
 +
== Тематическое моделирование ==
<!---
<!---
-
* ''[[Решающий список]] (комитет старшинства). Алгоритм обучения. Стратегия выбора классов для базовых алгоритмов.''
+
Текст лекций: [[Media:Voron-ML-TopicModels.pdf|(PDF,&nbsp;830&nbsp;КБ)]].<br/>
-
* ''Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии. Задача монотонизации выборки, изотонная регрессия.''
+
Презентация 1: [[Media:Voron-ML-TopicModels-slides.pdf|(PDF,&nbsp;2.8&nbsp;МБ)]] {{важно| обновление 16.11.2015}}.
-
=== Метод комитетов ===
+
Презентация 2: [[Media:Voron-ML-TopicModels-slides-2.pdf|(PDF,&nbsp;6.1&nbsp;МБ)]] {{важно| — обновление 16.11.2015}}.
-
* Общее понятие: [[комитет]] системы ограничений. Комитеты большинства, простое и взвешенное голосование (''z,p''-комитеты).
+
-
* Теоремы о существовании комитетного решения.
+
-
* Сопоставление комитета линейных неравенств с нейронной сетью.
+
-
* [[Максимальная совместная подсистема]], [[минимальный комитет]]. Теоремы об ''NP''-полноте задачи поиска минимального комитета.
+
-
* Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.
+
-
=== Бустинг алгоритмов ранжирования ===
+
-
* Задача ранжирования. Примеры: ранжирование результатов текстового поиска, задача [[Netflix]].
+
-
* Функционал качества число дефектных пар.
+
-
* Бустинг алгоритмов ранжирования — аналоги AdaBoost и AnyBoost.
+
-
* Двудольная задача. Сведение попарного функционала качества к поточечному.
+
-
=== Взвешенное голосование логических закономерностей ===
+
-
* Применение алгоритма бустинга [[AdaBoost]] к закономерностям. Критерий информативности в бустинге.
+
-
* [[Решающий лес]] и бустинг над решающими деревьями. ''[[Алгоритм TreeNet]].''
+
-
* ''Методы синтеза конъюнктивных закономерностей. Псевдокод: [[алгоритм КОРА]], [[алгоритм ТЭМП]].''
+
-
* Эвристики, обеспечивающие различность и полезность закономерностей. Построение Парето-оптимальных закономерностей. Выравнивание распределения отступов.
+
-
* ''[[Чередующиеся решающие деревья]] (alternating decision tree).''
+
-
* Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
+
-
=== Алгоритмы вычисления оценок ===
+
-
* [[Принцип частичной прецедентности]]. Структура [[Алгоритмы вычисления оценок|Алгоритмов вычисления оценок]].
+
-
* [[Тупиковые тесты]].
+
-
* [[Тупиковые представительные наборы]].
+
-
* Проблема оптимизации АВО. АВО как композиция метрических закономерностей.
+
-
* Применение бустинга, ТЭМП и СПА для оптимизации АВО.
+
--->
--->
 +
Презентация: [[Media:Voron-ML-TopicModeling-slides.pdf|(PDF,&nbsp;7.1&nbsp;МБ)]], Семинар: [[Media:Voron-ML-TopicModeling-seminar-slides.pdf|(PDF,&nbsp;3.8&nbsp;МБ)]] {{важно| — обновление 15.11.2020}}.
 +
* Задача [[тематическое моделирование|тематического моделирования]] коллекции текстовых документов. [[Метод максимума правдоподобия]].
 +
* Лемма о максимизации гладкой функции на симплексах (применение условий Каруша–Куна–Таккера).
 +
* [[Аддитивная регуляризация тематических моделей]]. Регуляризованный EM-алгоритм, теорема о стационарной точке. Элементарная интерпретация EM-алгоритма.
 +
* [[Вероятностный латентный семантический анализ]] PLSA. [[ЕМ-алгоритм]].
 +
* [[Латентное размещение Дирихле]] LDA. [[Метод максимума апостериорной вероятности]]. Сглаженная частотная оценка условной вероятности. Небайесовская интерпретация LDA.
 +
* Регуляризаторы разреживания, сглаживания, частичного обучения, декоррелирования.
 +
* Мультимодальная тематическая модель. Мультиязычная тематическая модель.
 +
* Регуляризаторы классификации и регрессии.
 +
* Модель битермов WNTM. Модель связанных документов. Иерархическая тематическая модель.
 +
* Внутренние и внешние критерии качества тематических моделей.
-
== Ранжирование ==
+
== Обучение ранжированию ==
-
Презентация: [[Media:Voron-ML-Ranking-slides.pdf|(PDF,&nbsp;0,5&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
+
Презентация: [[Media:Voron-ML-Ranking-slides.pdf|(PDF,&nbsp;0,8&nbsp;МБ)]] {{важно|— обновление 3.11.2020}}.
* Постановка задачи [[Обучение ранжированию|обучения ранжированию]]. Примеры.
* Постановка задачи [[Обучение ранжированию|обучения ранжированию]]. Примеры.
-
* Признаки в задаче ранжирования поисковой выдачи: текстовые, ссылочные, кликовые. [[TF-IDF]]. [[PageRank]].
+
* Поточечные методы Ранговая регрессия. Ранговая классификация, OC-SVM.
 +
* Попарные методы: RankingSVM, RankNet, LambdaRank.
 +
* Списочные методы.
 +
* Признаки в задаче ранжирования поисковой выдачи: текстовые, ссылочные, кликовые. [[TF-IDF]], [[Okapi BM25]], [[PageRank]].
* Критерии качества ранжирования: Precision, MAP, AUC, DCG, NDCG, pFound.
* Критерии качества ранжирования: Precision, MAP, AUC, DCG, NDCG, pFound.
-
* Ранговая классификация, OC-SVM.
+
* Глубокая структурированная семантическая модель [[DSSM]] (Deep Structured Semantic Model).
-
* Попарный подход: RankingSVM, RankNet, LambdaRank.
+
== Рекомендательные системы ==
== Рекомендательные системы ==
-
Презентация: [[Media:Voron-ML-CF.pdf|(PDF,&nbsp;0.8&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
+
Презентация: [[Media:Voron-ML-CF.pdf|(PDF,&nbsp;0.8&nbsp;МБ)]] {{важно| — обновление 11.11.2020}}.
-
* Задачи [[коллаборативная фильтрация|коллаборативной фильтрации]], [[транзакционные данные]] и матрица субъекты—объекты.
+
* Задачи [[коллаборативная фильтрация|коллаборативной фильтрации]], [[транзакционные данные]].
-
* Корреляционные методы user-based, item-based. Задача восстановления пропущенных значений. Меры сходства субъектов и объектов.
+
* Корреляционные методы user-based, item-based. Задача восстановления пропущенных значений. Меры сходства.
-
* ''Латентные методы на основе [[би-кластеризация|би-кластеризации]]. [[Алгоритм Брегмана]].''
+
* Разреженная линейная модель (Sparse LInear Method, SLIM).
* Латентные методы на основе матричных разложений. [[Метод главных компонент]] для разреженных данных (LFM, Latent Factor Model). [[Метод стохастического градиента]].
* Латентные методы на основе матричных разложений. [[Метод главных компонент]] для разреженных данных (LFM, Latent Factor Model). [[Метод стохастического градиента]].
-
* Неотрицательные матричные разложения. Метод чередующихся наименьших квадратов ALS.
+
* Неотрицательные матричные разложения NNMF. Метод чередующихся наименьших квадратов ALS. [[Вероятностный латентный семантический анализ]] PLSA.
* Модель с учётом неявной информации (implicit feedback).
* Модель с учётом неявной информации (implicit feedback).
-
* Рекомендации с учётом дополнительных признаковых данных. Линейная и квадратичная регрессионные модели, [[libFM]].
+
* Автокодировщики для коллаборативной фильтрации.
 +
* Учёт дополнительных признаковых данных в матричных разложениях и автокодировщиках.
 +
* Линейная и квадратичная регрессионные модели, [[libFM]].
 +
* Гиперграфовая транзакционная тематическая модель для учёта дополнительных данных.
* Измерение качества рекомендаций. Меры разнообразия (diversity), новизны (novelty), покрытия (coverage), догадливости (serendipity).
* Измерение качества рекомендаций. Меры разнообразия (diversity), новизны (novelty), покрытия (coverage), догадливости (serendipity).
-
== Тематическое моделирование ==
+
== Прогнозирование временных рядов ==
-
Текст лекций: [[Media:Voron-ML-TopicModels.pdf|(PDF,&nbsp;830&nbsp;КБ)]].<br/>
+
Презентация: [[Media:Voron-ML-forecasting-slides.pdf|(PDF,&nbsp;0,9&nbsp;)]] {{важно|— обновление 14.12.2019}}.
-
<!---
+
* Задача прогнозирования временных рядов. Примеры приложений.
-
Презентация 1: [[Media:Voron-ML-TopicModels-slides.pdf|(PDF,&nbsp;2.8&nbsp;МБ)]] {{важно| — обновление 16.11.2015}}.
+
* [[Экспоненциальное сглаживание|Экспоненциальное скользящее среднее]]. [[Модель Хольта]]. [[Модель Тейла-Вейджа]]. [[Модель Хольта-Уинтерса]].
-
Презентация 2: [[Media:Voron-ML-TopicModels-slides-2.pdf|(PDF,&nbsp;6.1&nbsp;МБ)]] {{важно| — обновление 16.11.2015}}.
+
* Адаптивная авторегрессионная модель.
-
--->
+
* [[Следящий контрольный сигнал]]. [[Модель Тригга-Лича]].
-
Презентация: [[Media:Voron-ML-TopicModeling-slides.pdf|(PDF,&nbsp;1.6&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
+
* Адаптивная селективная модель. Адаптивная композиция моделей.
-
* Задача [[тематическое моделирование|тематического моделирования]] коллекции текстовых документов.
+
* Локальная адаптация весов с регуляризацией.
-
* [[Вероятностный латентный семантический анализ]] PLSA. [[Метод максимума правдоподобия]]. [[ЕМ-алгоритм]]. Элементарная интерпретация EM-алгоритма.
+
 
-
* [[Латентное размещение Дирихле]] LDA. [[Метод максимума апостериорной вероятности]]. Сглаженная частотная оценка условной вероятности.
+
== Инкрементное и онлайновое обучение ==
-
* Небайесовская интерпретация LDA и её преимущества. Регуляризаторы разреживания, сглаживания, частичного обучения.
+
(в разработке...)
-
* Аддитивная регуляризация тематических моделей. Регуляризованный EM-алгоритм, теорема о стационарной точке (применение условий Каруша–Куна–Таккера).
+
* Отличия инкрементного и онлайнового обучения.
-
* Рациональный EM-алгоритм. Онлайновый EM-алгоритм и его распараллеливание.
+
* Добавление новых объектов. Ленивое обучение: kNN, парзеновские методы. Метод наименьших квадратов для линейной регрессии. Решающие деревья и леса.
-
* Мультимодальная тематическая модель.
+
* Добавление новых признаков. Матричные разложения.
-
* Регуляризаторы классификации и регрессии.
+
* Добавление новых классов.
-
* Регуляризаторы декоррелирования и отбора тем.
+
* Оценивание инкрементного обучения. Кривые обучения.
-
* Внутренние и внешние критерии качества тематических моделей.
+
== Обучение с подкреплением ==
== Обучение с подкреплением ==
-
Презентация: [[Media:Voron-ML-RL-slides.pdf|(PDF,&nbsp;1.0&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
+
Презентация: [[Media:Voron-ML-RL-slides.pdf|(PDF,&nbsp;1.9&nbsp;МБ)]] {{важно| — обновление 18.11.2020}}.
-
* Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound). Стратегия Softmax.
+
* Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound).
-
* Среда для экспериментов.
+
* Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования.
-
* Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования.
+
* Постановка задачи в случае, когда агент влияет на среду. Ценность состояния среды. Ценность действия.
* Постановка задачи в случае, когда агент влияет на среду. Ценность состояния среды. Ценность действия.
* Жадные стратегии максимизации ценности. Уравнения оптимальности Беллмана.
* Жадные стратегии максимизации ценности. Уравнения оптимальности Беллмана.
-
* Метод временных разностей TD. Метод Q-обучения.
+
* Метод SARSA. Метод Q-обучения. Типизация методов на on-policy и off-policy.
-
<!---* Многошаговое TD-прогнозирование. Обобщения методов временных разностей, SARSA, Q-обучения. --->
+
* Глубокое Q-обучение нейронной сети DQN на примере обучения играм Atari.
 +
<!---* Метод временных разностей TD. Многошаговое TD-прогнозирование. Обобщения методов временных разностей, SARSA, Q-обучения. --->
 +
<!---* Модели актор-критик. Модели с непрерывным управлением. --->
* Градиентная оптимизация стратегии (policy gradient). Связь с максимизацией log-правдоподобия.
* Градиентная оптимизация стратегии (policy gradient). Связь с максимизацией log-правдоподобия.
-
* Постановка задачи при наличии информации о среде в случае выбора действия. Контекстный многорукий бандит.
+
* Постановка задачи при моделировании среды. Типизация методов на model-free и model-based.
-
* Линейная регрессионная модель с верхней доверительной оценкой LinUCB.
+
* Контекстный многорукий бандит. Линейная регрессионная модель с верхней доверительной оценкой LinUCB.
-
* Оценивание новой стратегии по большим историческим данным.
+
* Оценивание новой стратегии по большим историческим данным, сформированным при старых стратегиях.
-
<!---* Адаптивный полужадный метод VDBE.--->
+
== Активное обучение ==
== Активное обучение ==
-
Презентация: [[Media:Voron-ML-AL-slides.pdf|(PDF,&nbsp;1.2&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
+
Презентация: [[Media:Voron-ML-AL-slides.pdf|(PDF,&nbsp;1.2&nbsp;МБ)]] {{важно| — обновление 24.11.2020}}.
-
* Постановка задачи машинного обучения. Основные стратегии: отбор объектов из выборки и из потока, синтез объектов.
+
* Постановка задачи машинного обучения. Основные стратегии: отбор объектов из выборки и из потока, синтез объектов. Приложения активного обучения.
-
* Сэмплирование по неуверенности. Почему активное обучение быстрее пассивного.
+
* Почему активное обучение быстрее пассивного. Оценивание качества активного обучения. Кривые обучения.
 +
* Сэмплирование по неуверенности.
* Сэмплирование по несогласию в комитете. Сокращение пространства решений.
* Сэмплирование по несогласию в комитете. Сокращение пространства решений.
* Сэмплирование по ожидаемому изменению модели.
* Сэмплирование по ожидаемому изменению модели.
* Сэмплирование по ожидаемому сокращению ошибки.
* Сэмплирование по ожидаемому сокращению ошибки.
 +
* Синтез объектов методами безградиентной оптимизации. [[Метод Нелдера-Мида]].
* Синтез объектов по критерию сокращения дисперсии.
* Синтез объектов по критерию сокращения дисперсии.
* Взвешивание по плотности.
* Взвешивание по плотности.
-
* Оценивание качества активного обучения.
 
* Введение изучающих действий в стратегию активного обучении. Алгоритмы ε-active и EG-active.
* Введение изучающих действий в стратегию активного обучении. Алгоритмы ε-active и EG-active.
-
* Применение обучения с подкреплением для активного обучения. Активное томпсоновское сэмплирование.
+
* Использование активного обучения в краудсорсинге. Согласование оценок аннотаторов. Назначение заданий аннотаторам.
 +
<!---* Применение обучения с подкреплением для активного обучения. Активное томпсоновское сэмплирование.--->
== Заключительная лекция ==
== Заключительная лекция ==

Версия 20:52, 24 ноября 2020

Содержание

Теория обучения машин (machine learning, машинное обучение) находится на стыке прикладной статистики, численных методов оптимизации, дискретного анализа, и за последние 60 лет оформилась в самостоятельную математическую дисциплину. Методы машинного обучения составляют основу ещё более молодой дисциплины — интеллектуального анализа данных (data mining).

В курсе рассматриваются основные задачи обучения по прецедентам: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Теоремы в основном приводятся без доказательств.

Все методы излагаются по единой схеме:

  • исходные идеи и эвристики;
  • их формализация и математическая теория;
  • описание алгоритма в виде слабо формализованного псевдокода;
  • анализ достоинств, недостатков и границ применимости;
  • пути устранения недостатков;
  • сравнение и взаимосвязи с другими методами.
  • примеры прикладных задач.

Данный курс расширяет и углубляет набор тем, рекомендованный международным стандартом ACM/IEEE Computing Curricula 2001 по дисциплине «Машинное обучение и нейронные сети» (machine learning and neural networks) в разделе «Интеллектуальные системы» (intelligent systems).

Курс читается

От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание математической статистики, методов оптимизации и языка программирования Python желательно, но не обязательно.

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

Замечания для студентов

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

Текст лекций: (PDF, 3 МБ) — обновление 4.10.2011.

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

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

Линейный классификатор и стохастический градиент

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

Нейронные сети: градиентные методы оптимизации

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

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

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

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

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

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

Многомерная линейная регрессия

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

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

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

Критерии выбора моделей и методы отбора признаков

Текст лекций: (PDF, 330 КБ).
Презентация: (PDF, 1,5 МБ) — обновление 25.10.2020.

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

Текст лекций: (PDF, 625 КБ).
Презентация: (PDF, 1.8 МБ) — обновление 20.10.2020.

Факультатив

  • Асимптотическая эквивалентность статистического и энтропийного критерия информативности.

Поиск ассоциативных правил

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

  • Понятие ассоциативного правила и его связь с понятием логической закономерности.
  • Примеры прикладных задач: анализ рыночных корзин, выделение терминов и тематики текстов.
  • Алгоритм APriori. Два этапа: поиск частых наборов и рекурсивное порождение ассоциативных правил. Недостатки и пути усовершенствования алгоритма APriori.
  • Алгоритм FP-growth. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов.
  • Общее представление о динамических и иерархических методах поиска ассоциативных правил.

Линейные ансамбли

Текст лекций: (PDF, 1 MБ).
Презентация: (PDF, 1.0 МБ) — обновление 14.11.2020.

Продвинутые методы ансамблирования

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

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

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

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

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

Семестр 2. Прикладные модели машинного обучения

Нейронные сети глубокого обучения

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

  • Свёрточные нейронные сети (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, 2,3 МБ) — обновление 03.10.2020.

Векторные представления текстов и графов

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

  • Векторные представления текста. Гипотеза дистрибутивной семантики.
  • Модели word2vec, FastText.
  • Векторные представления графов.
  • Многомерное шкалирование.
  • Модели случайных блужданий DeepWalk, node2vec.
  • Обобщённый автокодировщик на графах GraphEDM.
  • Векторные представления гиперграфов.
  • Тематические модели транзакционных данных. EM-алгоритм для тематической модели гиперграфа.
  • Примеры транзакционных моделей на гиперграфах.

Модели внимания и трансформеры

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

  • Задачи обработки последовательностей.
  • Рекуррентная сеть с моделью внимания. Разновидности моделей внимания.
  • Критерии обучения и оценивание качества (предобучение).
  • Прикладные задачи: машинный перевод, аннотирование изображений (эквивалентность MHSA и CNN).
  • Модели внимания на графах.
  • Трансформеры для текстов, изображений, графов.

Тематическое моделирование

Презентация: (PDF, 7.1 МБ), Семинар: (PDF, 3.8 МБ) — обновление 15.11.2020.

Обучение ранжированию

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

  • Постановка задачи обучения ранжированию. Примеры.
  • Поточечные методы Ранговая регрессия. Ранговая классификация, OC-SVM.
  • Попарные методы: RankingSVM, RankNet, LambdaRank.
  • Списочные методы.
  • Признаки в задаче ранжирования поисковой выдачи: текстовые, ссылочные, кликовые. TF-IDF, Okapi BM25, PageRank.
  • Критерии качества ранжирования: Precision, MAP, AUC, DCG, NDCG, pFound.
  • Глубокая структурированная семантическая модель DSSM (Deep Structured Semantic Model).

Рекомендательные системы

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

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

Прогнозирование временных рядов

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

Инкрементное и онлайновое обучение

(в разработке...)

  • Отличия инкрементного и онлайнового обучения.
  • Добавление новых объектов. Ленивое обучение: kNN, парзеновские методы. Метод наименьших квадратов для линейной регрессии. Решающие деревья и леса.
  • Добавление новых признаков. Матричные разложения.
  • Добавление новых классов.
  • Оценивание инкрементного обучения. Кривые обучения.

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

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

  • Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound).
  • Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования.
  • Постановка задачи в случае, когда агент влияет на среду. Ценность состояния среды. Ценность действия.
  • Жадные стратегии максимизации ценности. Уравнения оптимальности Беллмана.
  • Метод SARSA. Метод Q-обучения. Типизация методов на on-policy и off-policy.
  • Глубокое Q-обучение нейронной сети DQN на примере обучения играм Atari.
  • Градиентная оптимизация стратегии (policy gradient). Связь с максимизацией log-правдоподобия.
  • Постановка задачи при моделировании среды. Типизация методов на model-free и model-based.
  • Контекстный многорукий бандит. Линейная регрессионная модель с верхней доверительной оценкой LinUCB.
  • Оценивание новой стратегии по большим историческим данным, сформированным при старых стратегиях.

Активное обучение

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

  • Постановка задачи машинного обучения. Основные стратегии: отбор объектов из выборки и из потока, синтез объектов. Приложения активного обучения.
  • Почему активное обучение быстрее пассивного. Оценивание качества активного обучения. Кривые обучения.
  • Сэмплирование по неуверенности.
  • Сэмплирование по несогласию в комитете. Сокращение пространства решений.
  • Сэмплирование по ожидаемому изменению модели.
  • Сэмплирование по ожидаемому сокращению ошибки.
  • Синтез объектов методами безградиентной оптимизации. Метод Нелдера-Мида.
  • Синтез объектов по критерию сокращения дисперсии.
  • Взвешивание по плотности.
  • Введение изучающих действий в стратегию активного обучении. Алгоритмы ε-active и EG-active.
  • Использование активного обучения в краудсорсинге. Согласование оценок аннотаторов. Назначение заданий аннотаторам.

Заключительная лекция

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

Обзор курса. Оптимизационные задачи машинного обучения.

См. также

Литература

  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 с.

Список подстраниц

Машинное обучение (курс лекций, К.В.Воронцов)/2009Машинное обучение (курс лекций, К.В.Воронцов)/ToDoМашинное обучение (курс лекций, К.В.Воронцов)/Вопросы
Машинное обучение (курс лекций, К.В.Воронцов)/Семестровый курсМашинное обучение (курс лекций, К.В.Воронцов)/Форма отчета
Личные инструменты