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

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

(Различия между версиями)
Перейти к: навигация, поиск
(оформление)
(20 промежуточных версий не показаны.)
Строка 31: Строка 31:
=== Замечания для студентов ===
=== Замечания для студентов ===
-
* Видеолекции [http://shad.yandex.ru/lectures/machine_learning.xml ШАД Яндекс].
+
* Видеолекции [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)''
Строка 53: Строка 54:
== Метрические методы классификации и регрессии ==
== Метрические методы классификации и регрессии ==
-
Презентация: [[Media:Voron-ML-Metric-slides.pdf|(PDF, 3,0 МБ)]] {{важно|— обновление 18.02.2016}}.
+
Презентация: [[Media:Voron-ML-Metric-slides.pdf|(PDF, 3,0 МБ)]] {{важно|— обновление 21.02.2017}}.
* Гипотезы компактности и непрерывности.
* Гипотезы компактности и непрерывности.
Строка 73: Строка 74:
== Логические методы классификации ==
== Логические методы классификации ==
Текст лекций: [[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;МБ)]] {{важно| — обновление 25.02.2016}}.
+
Презентация: [[Media:Voron-ML-Logic-slides.pdf|(PDF,&nbsp;1.8&nbsp;МБ)]] {{важно| — обновление 21.02.2017}}.
* Понятие [[логическая закономерность|логической закономерности]].
* Понятие [[логическая закономерность|логической закономерности]].
Строка 94: Строка 95:
== Градиентные методы обучения ==
== Градиентные методы обучения ==
-
Презентация: [[Media:Voron-ML-Lin-SG.pdf|(PDF,&nbsp;1,3&nbsp;МБ)]] {{важно|— обновление 03.03.2016}}.
+
Презентация: [[Media:Voron-ML-Lin-SG.pdf|(PDF,&nbsp;0,9&nbsp;МБ)]] {{важно|— обновление 03.03.2017}}.
* [[Линейный классификатор]], модель МакКаллока-Питтса, непрерывные аппроксимации пороговой функции потерь.
* [[Линейный классификатор]], модель МакКаллока-Питтса, непрерывные аппроксимации пороговой функции потерь.
* [[Метод стохастического градиента]] SG.
* [[Метод стохастического градиента]] SG.
Строка 112: Строка 113:
== Метод опорных векторов ==
== Метод опорных векторов ==
-
Презентация: [[Media:Voron-ML-Lin-SVM.pdf|(PDF,&nbsp;1,2&nbsp;МБ)]] {{важно|— обновление 10.03.2016}}.
+
Презентация: [[Media:Voron-ML-Lin-SVM.pdf|(PDF,&nbsp;1,1&nbsp;МБ)]] {{важно|— обновление 07.03.2017}}.
* Оптимальная разделяющая гиперплоскость. Понятие [[зазор]]а между классами (margin).
* Оптимальная разделяющая гиперплоскость. Понятие [[зазор]]а между классами (margin).
* Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь.
* Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь.
Строка 128: Строка 129:
== Многомерная линейная регрессия ==
== Многомерная линейная регрессия ==
-
Презентация: [[Media:Voron-ML-regression-slides.pdf|(PDF,&nbsp;0,6&nbsp;MБ)]] {{важно|— обновление 22.03.2016}}.
+
Презентация: [[Media:Voron-ML-regression-slides.pdf|(PDF,&nbsp;0,7&nbsp;MБ)]] {{важно|— обновление 14.03.2017}}.
* Задача регрессии, [[многомерная линейная регрессия]].
* Задача регрессии, [[многомерная линейная регрессия]].
* [[Метод наименьших квадратов]], его вероятностный смысл и геометрический смысл.
* [[Метод наименьших квадратов]], его вероятностный смысл и геометрический смысл.
Строка 136: Строка 137:
* Методы отбора признаков: [[Лассо Тибширани]], [[Elastic Net]], сравнение с гребневой регрессией.
* Методы отбора признаков: [[Лассо Тибширани]], [[Elastic Net]], сравнение с гребневой регрессией.
* [[Метод главных компонент]] и [[декоррелирующее преобразование]] Карунена-Лоэва, его связь с сингулярным разложением.
* [[Метод главных компонент]] и [[декоррелирующее преобразование]] Карунена-Лоэва, его связь с сингулярным разложением.
 +
* Спектральный подход к решению задачи наименьших квадратов.
 +
* Задачи и методы низкоранговых матричных разложений.
<!---
<!---
=== Шаговая регрессия ===
=== Шаговая регрессия ===
Строка 144: Строка 147:
== Нелинейная регрессия ==
== Нелинейная регрессия ==
-
Презентация: [[Media:Voron-ML-regress-non-slides.pdf|(PDF,&nbsp;0,7&nbsp;MБ)]] {{важно|— обновление 29.03.2016}}.
+
Презентация: [[Media:Voron-ML-regress-non-slides.pdf|(PDF,&nbsp;0,7&nbsp;MБ)]] {{важно|— обновление 28.03.2017}}.
* [[Метод Ньютона-Рафсона]], [[метод Ньютона-Гаусса]].
* [[Метод Ньютона-Рафсона]], [[метод Ньютона-Гаусса]].
* Обобщённая аддитивная модель (GAM): [[метод настройки с возвращениями]] (backfitting) Хасти-Тибширани.
* Обобщённая аддитивная модель (GAM): [[метод настройки с возвращениями]] (backfitting) Хасти-Тибширани.
Строка 158: Строка 161:
Текст лекций: [[Media:Voron-ML-Modeling.pdf|(PDF,&nbsp;330&nbsp;КБ)]].<br/>
Текст лекций: [[Media:Voron-ML-Modeling.pdf|(PDF,&nbsp;330&nbsp;КБ)]].<br/>
Презентация: [[Media:Voron-ML-Modeling-slides.pdf|(PDF,&nbsp;1,0&nbsp;МБ)]] {{важно|— обновление 05.03.2015}}.<br/>
Презентация: [[Media:Voron-ML-Modeling-slides.pdf|(PDF,&nbsp;1,0&nbsp;МБ)]] {{важно|— обновление 05.03.2015}}.<br/>
-
Презентация: [[Media:Voron-ML-Quality-slides.pdf|(PDF,&nbsp;1,3&nbsp;МБ)]] {{важно|— обновление 05.04.2016}}.
+
Презентация: [[Media:Voron-ML-Quality-slides.pdf|(PDF,&nbsp;1,3&nbsp;МБ)]] {{важно|— обновление 28.03.2017}}.
* Критерии качества классификации: чувствительность и специфичность, ROC-кривая и AUC, точность и полнота, AUC-PR.
* Критерии качества классификации: чувствительность и специфичность, ROC-кривая и AUC, точность и полнота, AUC-PR.
Строка 181: Строка 184:
== Прогнозирование временных рядов ==
== Прогнозирование временных рядов ==
-
Презентация: [[Media:Voron-ML-forecasting-slides.pdf|(PDF,&nbsp;0,9&nbsp;MБ)]] {{важно|— обновление 12.04.2016}}.
+
Презентация: [[Media:Voron-ML-forecasting-slides.pdf|(PDF,&nbsp;0,9&nbsp;MБ)]] {{важно|— обновление 27.04.2017}}.
* Задача прогнозирования временных рядов. Примеры приложений.
* Задача прогнозирования временных рядов. Примеры приложений.
* [[Экспоненциальное сглаживание|Экспоненциальное скользящее среднее]]. [[Модель Хольта]]. [[Модель Тейла-Вейджа]]. [[Модель Хольта-Уинтерса]].
* [[Экспоненциальное сглаживание|Экспоненциальное скользящее среднее]]. [[Модель Хольта]]. [[Модель Тейла-Вейджа]]. [[Модель Хольта-Уинтерса]].
Строка 190: Строка 193:
== Байесовская теория классификации ==
== Байесовская теория классификации ==
-
Презентация: [[Media:Voron-ML-Bayes1-slides.pdf|(PDF,&nbsp;1,1&nbsp;МБ)]] {{важно|— обновление 14.04.2016}}.
+
Презентация: [[Media:Voron-ML-Bayes1-slides.pdf|(PDF,&nbsp;1,1&nbsp;МБ)]] {{важно|— обновление 27.04.2017}}.
* Принцип максимума апостериорной вероятности. Теорема об оптимальности байесовского классификатора.
* Принцип максимума апостериорной вероятности. Теорема об оптимальности байесовского классификатора.
Строка 208: Строка 211:
== Разделение смеси распределений ==
== Разделение смеси распределений ==
-
Презентация: [[Media:Voron-ML-Bayes2-slides.pdf|(PDF,&nbsp;1,7&nbsp;МБ)]] {{важно|— обновление 26.04.2016}}.
+
Презентация: [[Media:Voron-ML-Bayes2-slides.pdf|(PDF,&nbsp;1,7&nbsp;МБ)]] {{важно|— обновление 27.04.2017}}.
* [[Смесь распределений]].
* [[Смесь распределений]].
Строка 217: Строка 220:
* Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки.
* Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки.
* Сопоставление RBF-сети и SVM с гауссовским ядром.
* Сопоставление RBF-сети и SVM с гауссовским ядром.
 +
* Задача кластеризации. [[EM-алгоритм]] и [[Алгоритм k средних]] (k-means).
 +
* Задача частичного обучения.
-
== Кластеризация ==
+
== Кластеризация и частичное обучение ==
-
Презентация: [[Media:Voron-ML-Clustering-slides.pdf|(PDF,&nbsp;1,7&nbsp;МБ)]] {{важно|— обновление 27.04.2015}}.
+
Презентация: [[Media:Voron-ML-Clustering-slides.pdf|(PDF,&nbsp;1,7&nbsp;МБ)]] {{важно|— обновление 25.05.2017}}.
 +
<!--Презентация: [[Media:Voron-ML-SSL.pdf|(PDF,&nbsp;1.0&nbsp;МБ)]] {{важно| — обновление 28.10.2015}}.-->
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач. Типы кластерных структур.
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач. Типы кластерных структур.
 +
* Постановка задачи Semisupervised Learning, примеры приложений.
 +
* Оптимизационные постановки задач кластеризации и частичного обучения.
* [[Графовые алгоритмы кластеризации]]. Выделение связных компонент. [[Кратчайший незамкнутый путь]].
* [[Графовые алгоритмы кластеризации]]. Выделение связных компонент. [[Кратчайший незамкнутый путь]].
* [[Алгоритм ФОРЭЛ]].
* [[Алгоритм ФОРЭЛ]].
-
* Функционалы качества кластеризации.
 
-
* Статистические алгоритмы кластеризации: [[EM-алгоритм]] и [[Алгоритм k средних]] (k-means). Задача частичного обучения.
 
-
* [[Нейронная сеть Кохонена]]. [[Конкурентное обучение]], стратегии WTA и WTM.
 
-
* [[Самоорганизующаяся карта Кохонена]]. Применение для визуального анализа данных. Искусство интерпретации карт Кохонена.
 
* [[Агломеративная кластеризация]], [[Алгоритм Ланса-Вильямса]] и его частные случаи.
* [[Агломеративная кластеризация]], [[Алгоритм Ланса-Вильямса]] и его частные случаи.
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров.
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров.
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
 +
* Простые эвристические методы частичного обучения: self-training, co-training, co-learning.
 +
* Трансдуктивный метод опорных векторов TSVM.
 +
* Алгоритм Expectation-Regularization на основе многоклассовой регуляризированной логистической регрессии.
<!--* ''Потоковые (субквадратичные) алгоритмы кластеризации.''
<!--* ''Потоковые (субквадратичные) алгоритмы кластеризации.''
* [[Многомерное шкалирование]], примеры прикладных задач.
* [[Многомерное шкалирование]], примеры прикладных задач.
Строка 236: Строка 243:
* Совмещение многомерного шкалирования и иерархической кластеризации.
* Совмещение многомерного шкалирования и иерархической кластеризации.
-->
-->
 +
 +
== Поиск ассоциативных правил ==
 +
Презентация: [[Media:Voron-ML-AssocRules-slides.pdf|(PDF,&nbsp;1.1&nbsp;МБ)]] {{важно| — обновление 20.10.2015}}.
 +
* Понятие [[Ассоциативное правило|ассоциативного правила]] и его связь с понятием логической закономерности.
 +
* Примеры прикладных задач: [[анализ рыночных корзин]], выделение терминов и тематики текстов.
 +
* [[Алгоритм APriori]]. Два этапа: поиск частых наборов и рекурсивное порождение ассоциативных правил. Недостатки и пути усовершенствования алгоритма APriori.
 +
* [[Алгоритм FP-growth]]. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов.
 +
* Общее представление о динамических и иерархических методах поиска ассоциативных правил.
= Второй семестр =
= Второй семестр =
Строка 248: Строка 263:
* Метод послойной настройки сети.
* Метод послойной настройки сети.
* Подбор структуры сети: методы постепенного усложнения сети, [[оптимальное прореживание нейронных сетей]] (optimal brain damage).
* Подбор структуры сети: методы постепенного усложнения сети, [[оптимальное прореживание нейронных сетей]] (optimal brain damage).
 +
* [[Нейронная сеть Кохонена]]. [[Конкурентное обучение]], стратегии WTA и WTM.
 +
* [[Самоорганизующаяся карта Кохонена]]. Применение для визуального анализа данных. Искусство интерпретации карт Кохонена.
<!--* [[Сети встречного распространения]], их применение для кусочно-постоянной и гладкой аппроксимации функций.
<!--* [[Сети встречного распространения]], их применение для кусочно-постоянной и гладкой аппроксимации функций.
-->
-->
 +
 +
== Нейронные сети глубокого обучения ==
 +
Презентация: [[Media:Voron-ML-DeepLearning-slides.pdf|(PDF,&nbsp;3,4&nbsp;МБ)]] {{важно|— обновление 1.11.2017}}.
 +
* Быстрые методы стохастического градиента: Поляка, Нестерова, AdaGrad, RMSProp, AdaDelta, Adam, Nadam.
 +
* Проблема взрыва градиента и эвристика gradient clipping
 +
* Метод случайных отключений нейронов (Dropout). Интерпретации Dropout. Обратный Dropout и L2-регуляризация.
 +
* Функции активации ReLU и PReLU.
 +
* Свёрточные нейронные сети (CNN). Свёрточный нейрон. Pooling нейрон. Выборка размеченных изображений ImageNet.
 +
* Идея обобщения CNN на любые структурированные данные.
 +
* Рекуррентные нейронные сети (RNN). Обучение рекуррентных сетей: Backpropagation Through Time (BPTT).
 +
* Сети долгой кратковременной памяти (Long short-term memory, LSTM)
== Линейные композиции, бустинг ==
== Линейные композиции, бустинг ==
Строка 310: Строка 338:
* Попарный подход: RankingSVM, RankNet, LambdaRank.
* Попарный подход: RankingSVM, RankNet, LambdaRank.
-
== Поиск ассоциативных правил ==
+
== Рекомендательные системы ==
-
Презентация: [[Media:Voron-ML-AssocRules-slides.pdf|(PDF,&nbsp;1.1&nbsp;МБ)]] {{важно| — обновление 20.10.2015}}.
+
Презентация: [[Media:Voron-ML-CF.pdf|(PDF,&nbsp;0.8&nbsp;МБ)]] {{важно| — обновление 13.11.2016}}.
-
* Понятие [[Ассоциативное правило|ассоциативного правила]] и его связь с понятием логической закономерности.
+
-
* Примеры прикладных задач: [[анализ рыночных корзин]], выделение терминов и тематики текстов.
+
-
* [[Алгоритм APriori]]. Два этапа: поиск частых наборов и рекурсивное порождение ассоциативных правил. Недостатки и пути усовершенствования алгоритма APriori.
+
-
* [[Алгоритм FP-growth]]. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов.
+
-
* Общее представление о динамических и иерархических методах поиска ассоциативных правил.
+
-
 
+
-
== Задачи с частичным обучением ==
+
-
Презентация: [[Media:Voron-ML-SSL.pdf|(PDF,&nbsp;1.0&nbsp;МБ)]] {{важно| — обновление 28.10.2015}}.
+
-
* Постановка задачи Semisupervised Learning, примеры приложений.
+
-
* Простые эвристические методы: self-training, co-training, co-learning.
+
-
* Адаптация алгоритмов кластеризации для решения задач с частичным обучением. Кратчайшиё незамкнутый путь. Алгоритм Ланса-Уильямса. Алгоритм k-средних.
+
-
* Трансдуктивный метод опорных векторов TSVM.
+
-
* Алгоритм Expectation-Regularization на основе многоклассовой регуляризированной логистической регрессии.
+
-
 
+
-
== Коллаборативная фильтрация ==
+
-
Презентация: [[Media:Voron-ML-CF.pdf|(PDF,&nbsp;1.5&nbsp;МБ)]] {{важно| — обновление 13.04.2014}}.
+
* Задачи [[коллаборативная фильтрация|коллаборативной фильтрации]], [[транзакционные данные]] и матрица субъекты—объекты.
* Задачи [[коллаборативная фильтрация|коллаборативной фильтрации]], [[транзакционные данные]] и матрица субъекты—объекты.
-
* Корреляционные методы user-based, item-based. Меры сходства субъектов и объектов.
+
* Корреляционные методы user-based, item-based. Задача восстановления пропущенных значений. Меры сходства субъектов и объектов.
* ''Латентные методы на основе [[би-кластеризация|би-кластеризации]]. [[Алгоритм Брегмана]].''
* ''Латентные методы на основе [[би-кластеризация|би-кластеризации]]. [[Алгоритм Брегмана]].''
-
* Латентные методы на основе матричных разложений. [[Метод главных компонент]] для разреженных данных. [[Метод стохастического градиента]].
+
* Латентные методы на основе матричных разложений. [[Метод главных компонент]] для разреженных данных (LFM, Latent Factor Model). [[Метод стохастического градиента]].
-
* Неотрицательные матричные разложения. Разреженный SVD. Метод чередующихся наименьших квадратов ALS.
+
* Неотрицательные матричные разложения. Метод чередующихся наименьших квадратов ALS.
 +
* Модель с учётом неявной информации (implicit feedback).
 +
* Рекомендации с учётом дополнительных признаковых данных. Линейная и квадратичная регрессионные модели, [[libFM]].
 +
* Измерение качества рекомендаций. Меры разнообразия (diversity), новизны (novelty), покрытия (coverage), догадливости (serendipity).
== Тематическое моделирование ==
== Тематическое моделирование ==
Строка 340: Строка 355:
Презентация 2: [[Media:Voron-ML-TopicModels-slides-2.pdf|(PDF,&nbsp;6.1&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;2.3&nbsp;МБ)]] {{важно| — обновление 18.09.2016}}.
+
Презентация: [[Media:Voron-ML-TopicModeling-slides.pdf|(PDF,&nbsp;1.6&nbsp;МБ)]] {{важно| — обновление 1.11.2017}}.
* Задача [[тематическое моделирование|тематического моделирования]] коллекции текстовых документов.
* Задача [[тематическое моделирование|тематического моделирования]] коллекции текстовых документов.
* [[Вероятностный латентный семантический анализ]] PLSA. [[Метод максимума правдоподобия]]. [[ЕМ-алгоритм]]. Элементарная интерпретация EM-алгоритма.
* [[Вероятностный латентный семантический анализ]] PLSA. [[Метод максимума правдоподобия]]. [[ЕМ-алгоритм]]. Элементарная интерпретация EM-алгоритма.
Строка 353: Строка 368:
== Обучение с подкреплением ==
== Обучение с подкреплением ==
-
Презентация: [[Media:Voron-ML-RL-slides.pdf|(PDF,&nbsp;0.9&nbsp;МБ)]] {{важно| — обновление 16.11.2015}}.
+
Презентация: [[Media:Voron-ML-RL-slides.pdf|(PDF,&nbsp;1.0&nbsp;МБ)]] {{важно| — обновление 1.11.2017}}.
* Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound). Стратегия Softmax.
* Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound). Стратегия Softmax.
* Среда для экспериментов.
* Среда для экспериментов.
* Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования.
* Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования.
 +
* Постановка задачи в случае, когда агент влияет на среду. Ценность состояния среды. Ценность действия.
 +
* Жадные стратегии максимизации ценности. Уравнения оптимальности Беллмана.
 +
* Метод временных разностей TD. Метод Q-обучения.
 +
<!---* Многошаговое TD-прогнозирование. Обобщения методов временных разностей, SARSA, Q-обучения. --->
 +
* Градиентная оптимизация стратегии (policy gradient). Связь с максимизацией log-правдоподобия.
* Постановка задачи при наличии информации о среде в случае выбора действия. Контекстный многорукий бандит.
* Постановка задачи при наличии информации о среде в случае выбора действия. Контекстный многорукий бандит.
* Линейная регрессионная модель с верхней доверительной оценкой LinUCB.
* Линейная регрессионная модель с верхней доверительной оценкой LinUCB.
* Оценивание новой стратегии по большим историческим данным.
* Оценивание новой стратегии по большим историческим данным.
-
* Постановка задачи в случае, когда агент влияет на среду. Ценность состояния среды. Ценность действия.
 
-
* Жадные стратегии максимизации ценности. Уравнения оптимальности Беллмана.
 
-
* Метод временных разностей TD(0). Метод SARSA. Метод Q-обучения.
 
-
* Многошаговое TD-прогнозирование. Обобщения методов временных разностей, SARSA, Q-обучения.
 
<!---* Адаптивный полужадный метод VDBE.--->
<!---* Адаптивный полужадный метод VDBE.--->
 +
 +
== Активное обучение ==
 +
Презентация: [[Media:Voron-ML-AL-slides.pdf|(PDF,&nbsp;1.2&nbsp;МБ)]] {{важно| — обновление 1.11.2017}}.
 +
* Постановка задачи машинного обучения. Основные стратегии: отбор объектов из выборки и из потока, синтез объектов.
 +
* Сэмплирование по неуверенности. Почему активное обучение быстрее пассивного.
 +
* Сэмплирование по несогласию в комитете. Сокращение пространства решений.
 +
* Сэмплирование по ожидаемому изменению модели.
 +
* Сэмплирование по ожидаемому сокращению ошибки.
 +
* Синтез объектов по критерию сокращения дисперсии.
 +
* Взвешивание по плотности.
 +
* Оценивание качества активного обучения.
 +
* Введение изучающих действий в стратегию активного обучении. Алгоритмы ε-active и EG-active.
 +
* Применение обучения с подкреплением для активного обучения. Активное томпсоновское сэмплирование.
= См. также =
= См. также =
 +
* [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 Машинное обучение (семинары,ФУПМ МФТИ)]
* [https://drive.google.com/open?id=0B-3LhgkjkY_OSDJncFdxTkFaOG8 Машинное обучение (семинары,ФУПМ МФТИ)]
* [[Машинное обучение (семинары, ВМК МГУ)]]
* [[Машинное обучение (семинары, ВМК МГУ)]]

Версия 11:38, 1 ноября 2017

Содержание

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

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

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

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

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

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

На материал данного курса опираются последующие кафедральные курсы. На кафедре ММП ВМиК МГУ параллельно с данным курсом и в дополнение к нему читается спецкурс Теория надёжности обучения по прецедентам, посвящённый проблемам переобучения и оценивания обобщающей способности.

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

Ниже представлена расширенная программа — в полном объёме она занимает больше, чем могут вместить в себя два семестра. Каждый параграф приблизительно соответствует одной лекции. Курсивом выделен дополнительный материал, который может разбираться на семинарах.

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

  • Видеолекции ШАД Яндекс.
  • «Введение в машинное обучение» на Курсэре содержит примерно втрое меньше материала, чем в годовом курсе, представленном на этой странице. Там очень многое упрощено, спрятано, пропущено. Действительно введение.
  • На подстранице имеется перечень вопросов к устному экзамену. Очень помогает при подготовке к устному экзамену!
  • О найденных ошибках и опечатках сообщайте мне. — К.В.Воронцов 18:24, 19 января 2009 (MSK)
  • Материал, который есть в pdf-тексте, но не рассказывался на лекциях, обычно не входит в программу экзамена.

Первый семестр

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

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

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

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

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

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

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

Факультатив

  • Статистический критерий информативности, точный тест Фишера. Сравнение областей эвристических и статистических закономерностей. Асимптотическая эквивалентность статистического и энтропийного критерия информативности. Разнообразие критериев информативности в (p,n)-пространстве.
  • Решающий пень. Бинаризация признаков. Алгоритм разбиения области значений признака на информативные зоны.
  • Решающий список. Жадный алгоритм синтеза списка.
  • Преобразование решающего дерева в решающий список.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разделение смеси распределений

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

  • Смесь распределений.
  • EM-алгоритм: основная идея, понятие скрытых переменных. ЕМ алгоритм как метод простых итераций для решения системы нелинейных уравнений.
  • Детали реализации EM-алгоритма. Критерий останова. Выбор начального приближения.
  • Выбор числа компонентов смеси. Пошаговая стратегия. Априорное распределение Дирихле.
  • Обобщённый EM-алгоритм. Стохастический EM-алгоритм. Иерархический EM-алгоритм.
  • Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.
  • Сопоставление RBF-сети и SVM с гауссовским ядром.
  • Задача кластеризации. EM-алгоритм и Алгоритм k средних (k-means).
  • Задача частичного обучения.

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

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

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

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

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

Второй семестр

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

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

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

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

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

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

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

Эвристические, стохастические, нелинейные композиции

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

  • Стохастические методы: бэггинг и метод случайных подпространств.
  • Случайный лес. Анализ смещения и вариации для простого голосования.
  • Смесь алгоритмов (квазилинейная композиция), область компетентности, примеры функций компетентности.
  • Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
  • Построение смеси алгоритмов с помощью EM-подобного алгоритма.
  • Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии. Задача монотонизации выборки, изотонная регрессия.

Ранжирование

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

  • Постановка задачи обучения ранжированию. Примеры.
  • Признаки в задаче ранжирования поисковой выдачи: текстовые, ссылочные, кликовые. TF-IDF. PageRank.
  • Критерии качества ранжирования: Precision, MAP, AUC, DCG, NDCG, pFound.
  • Ранговая классификация, OC-SVM.
  • Попарный подход: RankingSVM, RankNet, LambdaRank.

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

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

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

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

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

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

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

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

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

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

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

См. также

Литература

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

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

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