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

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

(Различия между версиями)
Перейти к: навигация, поиск
(ссылки, ссылки, ссылки, ссылки, ссылки)
(→Второй семестр)
(282 промежуточные версии не показаны)
Строка 1: Строка 1:
{{TOCright}}
{{TOCright}}
-
'''Машинное обучение''' возникло на стыке [[Прикладная статистика|прикладной статистики]], [[Методы оптимизации|оптимизации]], [[Дискретный анализ|дискретного анализа]], и за последние 30 лет оформилось в самостоятельную математическую дисциплину. Методы [[Машинное обучение|машинного обучения]] составляют основу ещё более молодой дисциплины — ''[[Интеллектуальный анализ данных|интеллектуального анализа данных]]'' (data mining).
+
'''Теория обучения машин''' (machine learning, машинное обучение) находится на стыке [[Прикладная статистика|прикладной статистики]], [[Методы оптимизации|численных методов оптимизации]], [[Дискретный анализ|дискретного анализа]], и за последние 50 лет оформилась в самостоятельную математическую дисциплину. Методы [[Машинное обучение|машинного обучения]] составляют основу ещё более молодой дисциплины — ''[[Интеллектуальный анализ данных|интеллектуального анализа данных]]'' (data mining).
В курсе рассматриваются основные задачи обучения по прецедентам: [[классификация]], [[кластеризация]], [[регрессия]], [[понижение размерности]]. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.
В курсе рассматриваются основные задачи обучения по прецедентам: [[классификация]], [[кластеризация]], [[регрессия]], [[понижение размерности]]. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.
Строка 10: Строка 10:
* анализ достоинств, недостатков и границ применимости;
* анализ достоинств, недостатков и границ применимости;
* пути устранения недостатков;
* пути устранения недостатков;
-
* сравнение с другими методами;
+
* сравнение с другими методами.
* примеры прикладных задач.
* примеры прикладных задач.
-
Данный курс существенно расширяет и углубляет набор тем, рекомендованный международным стандартом '''ACM/IEEE Computing Curricula 2001''' по дисциплине «Машинное обучение и нейронные сети» (machine learning and neural networks) в разделе «Интеллектуальные системы» (intelligent systems).
+
Данный курс расширяет и углубляет набор тем, рекомендованный международным стандартом '''ACM/IEEE Computing Curricula 2001''' по дисциплине «Машинное обучение и нейронные сети» (machine learning and neural networks) в разделе «Интеллектуальные системы» (intelligent systems).
-
Курс читается студентам 3 курса кафедры [[Интеллектуальные системы (кафедра МФТИ)|«Интеллектуальные системы / интеллектуальный анализ данных» ФУПМ МФТИ]] с 2004 года и студентам 3 курса кафедры [[Математические методы прогнозирования (кафедра ВМиК МГУ)|«Математические методы прогнозирования» ВМиК МГУ]] с 2007 года.
+
Курс читается
-
На материал данного курса существенно опираются последующие курсы, читаемые студентам на этих кафедрах.
+
* студентам 3 курса кафедры [[Интеллектуальные системы (кафедра МФТИ)|«Интеллектуальные системы / интеллектуальный анализ данных» ФУПМ МФТИ]] с 2004 года;
 +
* студентам 3 курса кафедры [[Математические методы прогнозирования (кафедра ВМиК МГУ)|«Математические методы прогнозирования» ВМиК МГУ]] с 2007 года;
 +
* студентам [[Школа анализа данных Яндекса|Школы анализа данных Яндекса]] с 2009 года.
 +
 
 +
На материал данного курса опираются последующие кафедральные курсы.
 +
<!---На&nbsp;кафедре ММП ВМиК МГУ параллельно с данным курсом и в&nbsp;дополнение к&nbsp;нему читается спецкурс [[Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)|Теория надёжности обучения по прецедентам]], посвящённый проблемам [[Переобучение|переобучения]] и оценивания [[Обобщающая способность|обобщающей способности]].--->
От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание [[Математическая статистика|математической статистики]], [[Методы оптимизации|методов оптимизации]] и какого-либо языка программирования желательно, но не обязательно.
От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание [[Математическая статистика|математической статистики]], [[Методы оптимизации|методов оптимизации]] и какого-либо языка программирования желательно, но не обязательно.
-
== Первый семестр ==
+
Ниже представлена расширенная программа — в полном объёме она занимает больше, чем могут вместить в себя два семестра.
 +
Каждый параграф приблизительно соответствует одной лекции.
 +
''Курсивом'' выделен дополнительный материал, который может разбираться на семинарах.
-
=== Лекция 1. Вводная лекция ===
+
=== Замечания для студентов ===
-
* Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
+
-
* Типы задач: [[классификация]], [[распознавание]], [[кластеризация]], [[прогнозирование]]. Примеры прикладных задач.
+
-
* Основные понятия: [[модель алгоритмов]], [[метод обучения]], [[функция потерь]] и функционал качества, [[принцип минимизации эмпирического риска]], [[обобщающая способность]], [[скользящий контроль]].
+
-
* Вероятностная постановка задачи и [[принцип максимума правдоподобия]].
+
-
=== Лекция 2. Байесовские алгоритмы классификации ===
+
* Видеолекции [https://yandexdataschool.ru/edu-process/courses/machine-learning ШАД Яндекс].
-
* Оптимальный [[байесовский классификатор]].
+
* [https://www.coursera.org/learn/vvedenie-mashinnoe-obuchenie «Введение в машинное обучение» на Курсэре] содержит примерно втрое меньше материала, чем в годовом курсе, представленном на этой странице. Там очень многое упрощено, спрятано, пропущено. Действительно введение.
-
* Функционал среднего риска. Ошибки I и II рода.
+
* На подстранице имеется перечень [[Машинное обучение (курс лекций, К.В.Воронцов)/Вопросы|вопросов к устному экзамену]]. Очень помогает при подготовке к устному экзамену!
-
* Теорема об оптимальности байесовского решающего правила.
+
* О найденных ошибках и опечатках [[Служебная:EmailUser/Vokov|сообщайте мне]]. —&nbsp;''[[Участник:Vokov|К.В.Воронцов]] 18:24, 19 января 2009 (MSK)''
-
* [[Оценивание плотности распределения]]: три основных подхода.
+
* Материал, который есть в pdf-тексте, но не рассказывался на лекциях, обычно не входит в программу экзамена.
-
* [[Наивный байесовский классификатор]].
+
* Короткая ссылка на эту страницу: [https://bit.ly/1bCmE3Z https://bit.ly/1bCmE3Z].
-
* Непараметрическое оценивание плотности распределения по Парзену-Розенблатту. Выбор функции ядра. Выбор ширины окна, переменная ширина окна. Робастное оценивание плотности. [[Метод парзеновского окна]].
+
-
=== Лекция 3. Параметрическое оценивание плотности ===
+
= Первый семестр =
-
* [[Нормальный дискриминантный анализ]]. [[Многомерное нормальное распределение]], геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения.
+
-
* [[Квадратичный дискриминант]]. Вид разделяющей поверхности. [[Подстановочный алгоритм]], его недостатки и способы их устранения.
+
-
* [[Линейный дискриминант Фишера]].
+
-
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]]. [[Регуляризация]] ковариационной матрицы. [[Метод редукции размерности]] Шурыгина. Робастное оценивание.
+
-
* Факультатив/семинар: матричное дифференцирование.
+
-
=== Лекция 4. Разделение смеси распределений ===
+
'''Текст лекций:''' [[Media:Voron-ML-1.pdf|(PDF,&nbsp;3&nbsp;МБ)]] {{важно|— обновление 4.10.2011}}.
-
* [[Смесь распределений]].
+
-
* [[EM-алгоритм]]: основная идея, понятие скрытых переменных. «Вывод» алгоритма без обоснования сходимости. Псевдокод EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси.
+
-
* Стохастический EM-алгоритм.
+
-
* Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки.
+
-
=== Лекция 5. Метрические алгоритмы классификации ===
+
== Основные понятия и примеры прикладных задач ==
-
* [[Метод ближайших соседей]] (''k''NN) и его обобщения.
+
Презентация: [[Media:Voron-ML-Intro-slides.pdf|(PDF,&nbsp;1,4&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
-
* Подбор числа ''k'' по критерию скользящего контроля.
+
-
* Обобщённый [[метрический классификатор]].
+
-
* [[Метод потенциальных функций]], градиентный алгоритм.
+
-
* Настройка весов объектов. Отбор эталонных объектов. Псевдокод: [[алгоритм СТОЛП]].
+
-
* [[Проклятие размерности]]. Настройка весов признаков.
+
-
* Концепция [[CBR]].
+
-
=== Лекция 6. Кластеризация ===
+
* Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
-
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач.
+
* Типы задач: [[классификация]], [[регрессия]], [[прогнозирование]], [[ранжирование]].
-
* [[Графовые алгоритмы кластеризации]]. Алгоритм связных компонент.
+
* Основные понятия: [[модель алгоритмов]], [[метод обучения]], [[функция потерь]] и функционал качества, [[принцип минимизации эмпирического риска]], [[обобщающая способность]], [[скользящий контроль]].
-
* Псевдокод алгоритма: [[кратчайший незамкнутый путь]].
+
* Линейные модели регрессии и классификации. Метод наименьших квадратов. Полиномиальная регрессия.
-
* Псевдокод алгоритма: [[ФОРЭЛ]].
+
* Примеры прикладных задач.
-
* Функционалы качества кластеризации.
+
* Методика экспериментального исследования и сравнения алгоритмов на модельных и реальных данных.
-
* Статистические алгоритмы: [[EM-алгоритм]]. Псевдокод алгоритма [[k-means]].
+
* Конкурсы по анализу данных [http://kaggle.com kaggle.com]. [[Полигон алгоритмов классификации]].
 +
* [[CRISP-DM]] — межотраслевой стандарт ведения проектов [[Data Mining | интеллектуального анализа данных]].
-
=== Лекция 7. Иерерхическая кластеризация и многомерное шкалирование ===
+
== Линейный классификатор и стохастический градиент ==
-
* Псевдокод алгоритма: [[агломеративная кластеризация]]. [[Формула Ланса-Вильямса]].
+
-
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров.
+
-
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
+
-
Потоковые (субквадратичные) алгоритмы кластеризации.
+
-
* [[Многомерное шкалирование]]. Размещение одной точки методом Ньютона-Рафсона. Субквадратичный алгоритм.
+
-
* Визуализация: [[карта сходства]], [[диаграмма Шепарда]].
+
-
* Совмещение многомерного шкалирования и иерархической кластеризации.
+
-
* Примеры прикладных задач.
+
-
=== Лекция 8. Непараметрическая регрессия ===
+
Презентация: [[Media:Voron-ML-Lin-SG.pdf|(PDF,&nbsp;1,1&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
-
* Локально взвешенный [[метод наименьших квадратов]] и [[оценка Надарая-Ватсона]].
+
* [[Линейный классификатор]], модель МакКаллока-Питтса, непрерывные аппроксимации пороговой функции потерь.
-
* [[Сглаживание]].
+
* [[Метод стохастического градиента]] SG.
-
* Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна.
+
* [[Метод стохастического среднего градиента]] SAG.
-
* Проблема выбросов и робастная непараметрическая регрессия. Псевдокод: [[алгоритм LOWESS]].
+
<!--
-
* Проблема «проклятия размерности» и проблема выбора метрики.
+
* Частные случаи: [[адаптивный линейный элемент]] ADALINE, [[перcептрон Розенблатта]], [[правило Хэбба]].
 +
* [[Теорема Новикова]] о сходимости. Доказательство теоремы Новикова
 +
-->
 +
* Эвристики: инициализация весов, порядок предъявления объектов, выбор величины градиентного шага, «выбивание» из локальных минимумов.
 +
* Проблема мультиколлинеарности и переобучения, регуляризация или [[редукция весов]] (weight decay).
 +
* Вероятностная постановка задачи классификации. Принцип максимума правдоподобия.
 +
* Вероятностная интерпретация регуляризации, совместное правдоподобие данных и модели. Принцип максимума апостериорной вероятности.
 +
* Гауссовский и лапласовский регуляризаторы.
 +
* [[Логистическая регрессия]]. Принцип максимума правдоподобия и логарифмическая функция потерь. [[Метод стохастического градиента]] для логарифмической функции потерь. Многоклассовая логистическая регрессия. Регуляризованная логистическая регрессия. [[Калибровка Платта]].
 +
<!--
 +
* Функции потерь, зависящие от цены ошибок. [[Кривая ошибок]] (ROC curve). Алгоритм эффективного построения ROC-кривой.
 +
* Градиентный метод максимизации AUC.
 +
-->
-
=== Лекция 9. Многомерная линейная регрессия ===
+
== Метрические методы классификации и регрессии ==
 +
Презентация: [[Media:Voron-ML-Metric-slides.pdf|(PDF,&nbsp;3,2&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
 +
 
 +
* Гипотезы компактности и непрерывности.
 +
* Обобщённый [[метрический классификатор]].
 +
* [[Метод ближайших соседей]] ''k''NN и его обобщения. Подбор числа ''k'' по критерию скользящего контроля.
 +
* [[Метод окна Парзена]] с постоянной и переменной шириной окна.
 +
* [[Метод потенциальных функций]] и его связь с линейной моделью классификации.
 +
* Непараметрическая регрессия. Локально взвешенный [[метод наименьших квадратов]]. [[Ядерное сглаживание]].
 +
* [[Оценка Надарая-Ватсона]] с постоянной и переменной шириной окна. Выбор функции ядра.
 +
* Задача отсева выбросов. Робастная непараметрическая регрессия. [[Алгоритм LOWESS]].
 +
* Задача отбора эталонов. Понятие [[отступ]]а. [[Алгоритм СТОЛП]].
 +
* Задача отбора признаков. Жадный алгоритм построения метрики.
 +
<!--
 +
* ''[[Функция конкурентного сходства]], [[алгоритм FRiS-СТОЛП]]''.
 +
* ''[[Функционал полного скользящего контроля]], формула быстрого вычисления для метода 1NN. [[Профиль компактности]]. Функция вклада объекта. Отбор эталонных объектов на основе минимизации функционала полного скользящего контроля. Эффективные структуры данных для быстрого поиска ближайших объектов в прямых и обратных окрестностях — [[метрические деревья]].''
 +
* ''Концепция вывода на основе прецедентов ([[CBR]]).''
 +
-->
 +
 
 +
== Метод опорных векторов ==
 +
Презентация: [[Media:Voron-ML-Lin-SVM.pdf|(PDF,&nbsp;1,1&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
 +
* Оптимальная разделяющая гиперплоскость. Понятие [[зазор]]а между классами (margin).
 +
* Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь.
 +
* Задача квадратичного программирования и двойственная задача. Понятие [[Опорный вектор|опорных векторов]].
 +
* Рекомендации по выбору константы&nbsp;''C''.
 +
* [[Функция ядра]] (kernel functions), [[спрямляющее пространство]], [[теорема Мерсера]].
 +
* Способы конструктивного построения ядер. Примеры ядер.
 +
* SVM-регрессия.
 +
* Регуляризации для отбора признаков: [[LASSO SVM]], [[Elastic Net SVM]], [[SFM]], [[RFM]].
 +
* Метод релевантных векторов [[RVM]]
 +
<!---
 +
* ''Обучение SVM методом активных ограничений. [[Алгоритм INCAS]]. [[Алгоритм SMO]].''
 +
* ''ню-SVM.''
 +
--->
 +
 
 +
== Многомерная линейная регрессия ==
 +
Презентация: [[Media:Voron-ML-regression-slides.pdf|(PDF,&nbsp;0,7&nbsp;MБ)]] {{важно|— обновление 14.12.2019}}.
* Задача регрессии, [[многомерная линейная регрессия]].
* Задача регрессии, [[многомерная линейная регрессия]].
-
* [[Метод наименьших квадратов]]. [[Сингулярное разложение]].
+
* [[Метод наименьших квадратов]], его вероятностный смысл и геометрический смысл.
 +
* [[Сингулярное разложение]].
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]].
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]].
-
* [[Регуляризация]]. [[Гребневая регрессия]]. [[Лассо Тибширани]]. Линейная монотонная регрессия (симплекс-метод).
+
* [[Регуляризация]]. [[Гребневая регрессия]] через сингулярное разложение.
-
* Линейные преобразования признакового пространства. [[Метод главных компонент]] и [[декоррелирующее преобразование]] Карунена-Лоэва.
+
* Методы отбора признаков: [[Лассо Тибширани]], [[Elastic Net]], сравнение с гребневой регрессией.
-
* [[Робастная регрессия]].
+
* [[Метод главных компонент]] и [[декоррелирующее преобразование]] Карунена-Лоэва, его связь с сингулярным разложением.
-
 
+
* Спектральный подход к решению задачи наименьших квадратов.
-
=== Лекция 10. Шаговая регрессия ===
+
* Задачи и методы низкоранговых матричных разложений.
 +
<!---
 +
=== Шаговая регрессия ===
* [[Модифицированная ортогонализация Грама-Шмидта]], достоинства и недостатки.
* [[Модифицированная ортогонализация Грама-Шмидта]], достоинства и недостатки.
* [[Отбор признаков]] в процессе ортогонализации, критерии выбора и останова.
* [[Отбор признаков]] в процессе ортогонализации, критерии выбора и останова.
-
* [[Метод наименьших углов]], его связь с лассо и шаговой регрессией.
+
* [[Метод наименьших углов]] (LARS), его связь с лассо и шаговой регрессией.
 +
-->
-
=== Лекция 11. Нелинейная параметрическая регрессия ===
+
== Нелинейная регрессия ==
 +
Презентация: [[Media:Voron-ML-regress-non-slides.pdf|(PDF,&nbsp;0,7&nbsp;MБ)]] {{важно|— обновление 14.12.2019}}.
* [[Метод Ньютона-Рафсона]], [[метод Ньютона-Гаусса]].
* [[Метод Ньютона-Рафсона]], [[метод Ньютона-Гаусса]].
-
* Одномерные нелинейные преобразования признаков: [[метод обратной настройки]] (backfitting) Хасти-Тибширани.
+
* Обобщённая аддитивная модель (GAM): [[метод настройки с возвращениями]] (backfitting) Хасти-Тибширани.
-
* [[Обобщённая линейная модель]] (GLM).
+
* [[Логистическая регрессия]]. [[Метод наименьших квадратов с итеративным пересчётом весов]] (IRLS). Пример прикладной задачи: кредитный скоринг. Бинаризация признаков. Скоринговые карты и оценивание вероятности дефолта. ''Риск кредитного портфеля банка.''
-
* Неквадратичные функции потерь, примеры прикладных задач.
+
* [[Обобщённая линейная модель]] (GLM). Экспоненциальное семейство распределений.
 +
* Неквадратичные функции потерь. Метод наименьших модулей. Квантильная регрессия. Пример прикладной задачи: прогнозирование потребительского спроса.
 +
* Робастная регрессия, функции потерь с горизонтальными асимптотами.
 +
<!---
 +
* [[Логистическая регрессия]]. Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
 +
--->
-
=== Лекция 12. Логистическая регрессия ===
+
== Прогнозирование временных рядов ==
-
* [[Линейный классификатор]]. «Наивное» сведение задачи классификации к задаче регрессии, его недостатки.
+
Презентация: [[Media:Voron-ML-forecasting-slides.pdf|(PDF,&nbsp;0,9&nbsp;MБ)]] {{важно|— обновление 14.12.2019}}.
-
* Гладкие аппроксимации пороговой функции потерь.
+
* Задача прогнозирования временных рядов. Примеры приложений.
-
* Обоснование [[Логистическая регрессия|логистической регрессии]]: теорема об экспонентных плотностях.
+
* [[Экспоненциальное сглаживание|Экспоненциальное скользящее среднее]]. [[Модель Хольта]]. [[Модель Тейла-Вейджа]]. [[Модель Хольта-Уинтерса]].
-
* [[Метод наименьших квадратов с итеративным пересчетом весов]] (IRLS).
+
* Адаптивная авторегрессионная модель.
-
* Настройка порога решающего правила по критерию числа ошибок I и II рода, [[кривая ошибок]] (lift curve), отказы от классификации.
+
* [[Следящий контрольный сигнал]]. [[Модель Тригга-Лича]].
-
* Пример прикладной задачи: кредитный скоринг и скоринговые карты.
+
* Адаптивная селективная модель. Адаптивная композиция моделей.
 +
* Локальная адаптация весов с регуляризацией.
-
=== Лекция 13. Элементы теории обобщающей способности ===
+
== Критерии выбора моделей и методы отбора признаков ==
-
* [[Принцип равномерной сходимости]]. [[Скользящий контроль]]. [[Теория Вапника-Червоненкиса]].
+
Текст лекций: [[Media:Voron-ML-Modeling.pdf|(PDF,&nbsp;330&nbsp;КБ)]].<br/>
-
* [[Функция роста]] и [[ёмкость]].
+
Презентация: [[Media:Voron-ML-Quality-slides.pdf|(PDF,&nbsp;1,5&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
-
* Ёмкость некоторых семейств алгоритмов.
+
-
* [[Метод структурной минимизации риска]].
+
-
* [[Принцип минимума длины описания]].
+
-
* Достаточная длина обучающей выборки.
+
-
* Причины завышенности оценок Вапника-Червоненкиса.
+
-
* Эффекты локализации (расслоения) семейства алгоритмов и различности алгоритмов.
+
-
* Оценки, зависящие от данных. Оценки, зависящие от отступов. Принцип самоограничения сложности. Понятие стабильности обучения.
+
-
* Эмпирическое оценивание обобщающей способности. Анализ вариации и смещения.
+
-
=== Лекция 14. Оценивание и выбор моделей ===
+
* Критерии качества классификации: чувствительность и специфичность, ROC-кривая и AUC, точность и полнота, AUC-PR.
-
* Внутренние и [[внешние критерии]].
+
* Внутренние и [[внешние критерии]]. Эмпирические и аналитические критерии.
-
* [[Скользящий контроль]].
+
* [[Скользящий контроль]], разновидности эмпирических оценок скользящего контроля. [[Критерий непротиворечивости]].
-
* [[Критерий непротиворечивости]].
+
* Разновидности аналитических оценок. [[Регуляризация]]. [[Критерий Акаике]] (AIC). [[Байесовский информационный критерий]] (BIC). Оценка Вапника-Червоненкиса.
-
* [[Регуляризация]].
+
-
* Критерии, основанные на оценках обобщающей способности: Вапника-Червоненкиса, [[критерий Акаике]] (AIC), [[байесовский информационный критерий]] (BIC).
+
-
* Статистические критерии: [[коэффициент детерминации]], [[критерий Фишера]], [[анализ остатков]].
+
-
 
+
-
=== Лекция 15. Методы отбора признаков ===
+
* Сложность задачи [[отбор признаков|отбора признаков]]. [[Полный перебор]].
* Сложность задачи [[отбор признаков|отбора признаков]]. [[Полный перебор]].
-
* [[Метод добавления и удаления]] (шаговая регрессия).
+
* [[Метод добавления и удаления]], шаговая регрессия.
-
* [[Поиск в глубину]] (метод ветвей и границ).
+
* [[Поиск в глубину]], метод ветвей и границ.
-
* Усечённый [[поиск в ширину]] ([[многорядный итерационный алгоритм МГУА]]).
+
* Усечённый [[поиск в ширину]], [[многорядный итерационный алгоритм МГУА]].
* [[Генетический алгоритм]], его сходство с МГУА.
* [[Генетический алгоритм]], его сходство с МГУА.
-
* [[Случайный поиск с адаптацией]] (СПА).
+
* [[Случайный поиск]] и [[Случайный поиск с адаптацией]] (СПА).
 +
<!---
 +
* ''Агрегированные и многоступенчатые критерии''.
 +
* ''Статистические критерии: [[коэффициент детерминации]], [[критерий Фишера]], [[анализ регрессионных остатков]].''
 +
== Теория обобщающей способности ==
 +
* [[Теория Вапника-Червоненкиса]]. Функционал равномерного отклонения частот ошибок. [[Функция роста]], [[ёмкость]] семейства алгоритмов. [[Структурная минимизация риска]].
 +
* ''Оценка «бритвы Оккама»''.
 +
* ''[[Радемахеровская сложность]] семейства алгоритмов.''
 +
* [[Комбинаторная теория переобучения (виртуальный семинар)|Комбинаторная теория переобучения]]. Функционал вероятности переобучения. Граф расслоения-связности. Оценки расслоения-связности.
 +
--->
-
== Второй семестр ==
+
== Логические методы классификации ==
 +
Текст лекций: [[Media:Voron-ML-Logic.pdf|(PDF,&nbsp;625&nbsp;КБ)]].<br/>
 +
Презентация: [[Media:Voron-ML-Logic-slides.pdf|(PDF,&nbsp;1.8&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
-
=== Лекция 1. Однослойный персептрон ===
+
* Понятие [[логическая закономерность|логической закономерности]].
-
* Естественный нейрон, [[модель МакКаллока-Питтса]].
+
* Параметрические семейства закономерностей: конъюнкции пороговых правил, синдромные правила, шары, гиперплоскости.
-
* [[Персептрон Розенблатта]].
+
* Переборные алгоритмы синтеза конъюнкций: [[стохастический локальный поиск]], [[стабилизация]], [[редукция]].
-
* [[Метод стохастического градиента]]. [[Теорема Новикова]] о сходимости.
+
* Двухкритериальный отбор информативных закономерностей, парето-оптимальный фронт в (p,n)-пространстве.
-
* Связь однослойного персептрона с логистической регрессией и обоснование сигмоидной функции потерь.
+
* [[Решающее дерево]]. Жадная нисходящая стратегия «разделяй и властвуй». [[Алгоритм ID3]]. Недостатки жадной стратегии и способы их устранения. Проблема переобучения.
-
* [[Проблема исключающего или]]. Проблема полноты. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).
+
* Вывод критериев ветвления. Мера нечистоты (impurity) распределения. Энтропийный критерий, критерий Джини.
 +
* [[Редукция решающих деревьев]]: [[предредукция]] и [[постредукция]]. [[Алгоритм C4.5]].
 +
* Деревья регрессии. [[Алгоритм CART]].
 +
* [[Небрежные решающие деревья]] (oblivious decision tree).
 +
* Решающий лес. [[Случайный лес]] (Random Forest).
-
=== Лекция 2. Многослойные нейронные сети ===
+
'''Факультатив'''
-
* [[Алгоритм обратного распространения ошибок]]. Недостатки алгоритма, способы их устранения.
+
* Статистический критерий информативности, [[точный тест Фишера]]. Сравнение областей эвристических и статистических закономерностей. Асимптотическая эквивалентность статистического и энтропийного критерия информативности. Разнообразие критериев информативности в (p,n)-пространстве.
-
* Проблема переобучения.
+
* Решающий пень. [[Бинаризация признаков]]. Алгоритм разбиения области значений признака на информативные зоны.
-
* Проблема [[паралич сети|«паралича» сети]].
+
* [[Решающий список]]. Жадный алгоритм синтеза списка.
-
* [[Редукция весов]] (weight decay).
+
* Преобразование решающего дерева в решающий список.
-
* Подбор структуры сети.
+
-
* [[Метод оптимального прореживания сети]] (optimal brain damage).
+
-
=== Лекция 3. Обучающееся векторное квантование (сети Кохонена) ===
+
== Поиск ассоциативных правил ==
-
* [[Сеть Кохонена]]. [[Конкурентное обучение]], стратегии WTA и WTM.
+
Презентация: [[Media:Voron-ML-AssocRules-slides.pdf|(PDF,&nbsp;1.1&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
-
* [[Самоорганизующаяся карта Кохонена]]. Применение для визуального анализа данных.
+
* Понятие [[Ассоциативное правило|ассоциативного правила]] и его связь с понятием логической закономерности.
-
* [[Сети встречного распространения]], их применение для кусочно-постоянной и гладкой аппроксимации функций.
+
* Примеры прикладных задач: [[анализ рыночных корзин]], выделение терминов и тематики текстов.
 +
* [[Алгоритм APriori]]. Два этапа: поиск частых наборов и рекурсивное порождение ассоциативных правил. Недостатки и пути усовершенствования алгоритма APriori.
 +
* [[Алгоритм FP-growth]]. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов.
 +
* Общее представление о динамических и иерархических методах поиска ассоциативных правил.
-
=== Лекция 4. Метод опорных векторов ===
+
== Байесовская классификация и оценивание плотности ==
-
* Оптимальная разделяющая гиперплоскость. Понятие [[зазор]]а между классами (margin).
+
Презентация: [[Media:Voron-ML-BTC-EM-slides.pdf|(PDF,&nbsp;1,6&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
-
* Случай линейной разделимости. Задача квадратичного программирования и двойственная задача. Понятие [[Опорный вектор|опорных векторов]].
+
-
* Случай отсутствия линейной разделимости. Двойственная задача. Отличие от предыдущего случая. Выбор константы&nbsp;''C''.
+
-
* [[Функция ядра]] (kernel functions), [[спрямляющее пространство]], [[теорема Мерсера]].
+
-
* Способы построения ядер. Примеры ядер.
+
-
* Сопоставление SVM и RBF-сети.
+
-
=== Лекция 5. Оптимизационные техники решения задачи SVM ===
+
* Принцип максимума апостериорной вероятности. Теорема об оптимальности байесовского классификатора.
-
* Обучение SVM методом последовательной оптимизации минимумов. Псевдокод: [[алгоритм SMO]].
+
* [[Оценивание плотности распределения]]: три основных подхода.
-
* Обучение SVM методом активных ограничений. Псевдокод: [[алгоритм INCAS]].
+
* [[Наивный байесовский классификатор]].
-
* SVM-регрессия.
+
* Непараметрическое оценивание плотности. [[Ядерная оценка плотности Парзена-Розенблатта]]. Одномерный и многомерный случаи.
 +
* [[Метод парзеновского окна]]. Выбор функции ядра. Выбор ширины окна, переменная ширина окна.
 +
* Параметрическое оценивание плотности. [[Нормальный дискриминантный анализ]].
 +
* [[Многомерное нормальное распределение]], геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения.
 +
* [[Квадратичный дискриминант]]. Вид разделяющей поверхности. [[Подстановочный алгоритм]], его недостатки и способы их устранения.
 +
* [[Линейный дискриминант Фишера]].
 +
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]]. [[Регуляризация]] ковариационной матрицы.
 +
* Параметрический наивный байесовский классификатор.
 +
* [[Смесь распределений]].
 +
* [[EM-алгоритм]] как метод простых итераций для решения системы нелинейных уравнений.
 +
* Выбор числа компонентов смеси. Пошаговая стратегия. Априорное распределение Дирихле.
 +
* Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки.
 +
* Сравнение RBF-сети и SVM с гауссовским ядром.
 +
<!---
 +
* ''Связь линейного дискриминанта Фишера с [[метод наименьших квадратов|методом наименьших квадратов]].''
 +
* ''Матричное дифференцирование. Вывод оценок параметров многомерного нормального распределения.''
 +
* Жадное добавление признаков в линейном дискриминанте, ''[[метод редукции размерности]] Шурыгина.''
 +
* ''Робастное оценивание. Цензурирование выборки (отсев объектов-выбросов).''
 +
== Разделение смеси распределений ==
 +
Презентация: [[Media:Voron-ML-Bayes2-slides.pdf|(PDF,&nbsp;1,7&nbsp;МБ)]] {{важно|— обновление 27.04.2017}}.
 +
* Детали реализации EM-алгоритма. Критерий останова. Выбор начального приближения.
 +
* Обобщённый EM-алгоритм. Стохастический EM-алгоритм. Иерархический EM-алгоритм.
 +
* Задача кластеризации. [[EM-алгоритм]] и [[Алгоритм k средних]] (k-means).
 +
* Задача частичного обучения.
 +
--->
-
=== Лекция 6. Алгоритмические композиции ===
+
== Кластеризация и частичное обучение ==
-
* Основные понятия: [[базовый алгоритм]] ([[алгоритмический оператор]]), [[корректирующая операция]].
+
Презентация: [[Media:Voron-ML-Clustering-SSL-slides.pdf|(PDF,&nbsp;1,8&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
-
* Линейные (выпуклые) алгоритмические композиции.
+
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач. Типы кластерных структур.
-
* Процесс последовательного обучения базовых алгоритмов.
+
* Постановка задачи Semisupervised Learning, примеры приложений.
-
* [[Простое голосование]] (комитет большинства). Эвристический алгоритм.
+
* Оптимизационные постановки задач кластеризации и частичного обучения.
-
* [[Решающий список]] (комитет старшинства). Эвристический алгоритм.
+
* [[Алгоритм k-средних]] и [[ЕМ-алгоритм]] для разделения гауссовской смеси.
 +
* [[Графовые алгоритмы кластеризации]]. Выделение связных компонент. [[Кратчайший незамкнутый путь]].
 +
* [[Алгоритм ФОРЭЛ]].
 +
* [[Алгоритм DBSCAN]].
 +
* [[Агломеративная кластеризация]], [[Алгоритм Ланса-Вильямса]] и его частные случаи.
 +
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров.
 +
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
 +
* Простые эвристические методы частичного обучения: self-training, co-training, co-learning.
 +
* Трансдуктивный метод опорных векторов TSVM.
 +
* Алгоритм Expectation-Regularization на основе многоклассовой регуляризированной логистической регрессии.
 +
<!--
 +
* ''Потоковые (субквадратичные) алгоритмы кластеризации.''
 +
* [[Многомерное шкалирование]], примеры прикладных задач.
 +
* Субквадратичный алгоритм, псевдокод. Минимизация функционала стресса методом Ньютона-Рафсона.
 +
* Визуализация: [[карта сходства]], [[диаграмма Шепарда]].
 +
* Совмещение многомерного шкалирования и иерархической кластеризации.
 +
* [[Алгоритм t-SNE]]
 +
-->
-
=== Лекция 7. Бустинг, бэггинг и аналоги ===
+
= Второй семестр =
 +
 
 +
== Нейронные сети: градиентные методы оптимизации ==
 +
Презентация: [[Media:Voron-ML-NeuralNets1-2018-slides.pdf|(PDF,&nbsp;1,4&nbsp;МБ)]] {{важно|— обновление 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,&nbsp;3,4&nbsp;МБ)]] {{важно|— обновление 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,&nbsp;1&nbsp;MБ)]].<br/>
 +
Презентация: [[Media:Voron-ML-Compositions-slides.pdf|(PDF,&nbsp;0.9&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
 +
* Основные понятия: [[базовый алгоритм]] ([[алгоритмический оператор]]), [[корректирующая операция]].
* [[Взвешенное голосование]].
* [[Взвешенное голосование]].
-
* Экспоненциальная аппроксимация пороговой функции потерь. Теорема о сходимости [[бустинг]]а.
+
* [[Алгоритм AdaBoost]]. Экспоненциальная аппроксимация пороговой функции потерь. Процесс последовательного обучения базовых алгоритмов. Теорема о сходимости [[бустинг]]а.
-
* Псевдокод: [[алгоритм AdaBoost]].
+
* Обобщающая способность бустинга.
-
* Варианты бустинга: GentleBoost, LogitBoost, BrownBoost, и другие.
+
* Базовые алгоритмы в бустинге. Решающие пни.
-
* Стохастические методы: [[бэггинг]] и [[метод случайных подпространств]].
+
* ''Варианты бустинга: [[GentleBoost]], [[LogitBoost]], [[BrownBoost]], и другие.''
 +
* [[Градиентный бустинг]]. Стохастический градиентный бустинг.
 +
* [[Алгоритм AnyBoost]].
 +
* [[Алгоритм XGBoost]].
-
=== Лекция 8. Метод комитетов ===
+
== Эвристические, стохастические, нелинейные композиции ==
 +
Презентация: [[Media:Voron-ML-Compositions-slides2.pdf|(PDF,&nbsp;0.9&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
 +
* Стохастические методы: [[бэггинг]] и [[метод случайных подпространств]].
 +
* [[Простое голосование]] (комитет большинства). Алгоритм ComBoost. Идентификация нетипичных объектов (выбросов).
 +
* Преобразование простого голосования во взвешенное.
 +
* Обобщение на большое число классов.
 +
* Случайный лес.
 +
* Анализ смещения и вариации для простого голосования.
 +
* [[Смесь алгоритмов]] (квазилинейная композиция), [[область компетентности]], примеры функций компетентности.
 +
* Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
 +
* Построение смеси алгоритмов с помощью EM-подобного алгоритма.
 +
<!---
 +
* ''[[Решающий список]] (комитет старшинства). Алгоритм обучения. Стратегия выбора классов для базовых алгоритмов.''
 +
* ''Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии. Задача монотонизации выборки, изотонная регрессия.''
 +
=== Метод комитетов ===
* Общее понятие: [[комитет]] системы ограничений. Комитеты большинства, простое и взвешенное голосование (''z,p''-комитеты).
* Общее понятие: [[комитет]] системы ограничений. Комитеты большинства, простое и взвешенное голосование (''z,p''-комитеты).
* Теоремы о существовании комитетного решения.
* Теоремы о существовании комитетного решения.
Строка 193: Строка 321:
* [[Максимальная совместная подсистема]], [[минимальный комитет]]. Теоремы об ''NP''-полноте задачи поиска минимального комитета.
* [[Максимальная совместная подсистема]], [[минимальный комитет]]. Теоремы об ''NP''-полноте задачи поиска минимального комитета.
* Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.
* Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.
 +
=== Бустинг алгоритмов ранжирования ===
 +
* Задача ранжирования. Примеры: ранжирование результатов текстового поиска, задача [[Netflix]].
 +
* Функционал качества — число дефектных пар.
 +
* Бустинг алгоритмов ранжирования — аналоги AdaBoost и AnyBoost.
 +
* Двудольная задача. Сведение попарного функционала качества к поточечному.
 +
=== Взвешенное голосование логических закономерностей ===
 +
* Применение алгоритма бустинга [[AdaBoost]] к закономерностям. Критерий информативности в бустинге.
 +
* [[Решающий лес]] и бустинг над решающими деревьями. ''[[Алгоритм TreeNet]].''
 +
* ''Методы синтеза конъюнктивных закономерностей. Псевдокод: [[алгоритм КОРА]], [[алгоритм ТЭМП]].''
 +
* Эвристики, обеспечивающие различность и полезность закономерностей. Построение Парето-оптимальных закономерностей. Выравнивание распределения отступов.
 +
* ''[[Чередующиеся решающие деревья]] (alternating decision tree).''
 +
* Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
 +
=== Алгоритмы вычисления оценок ===
 +
* [[Принцип частичной прецедентности]]. Структура [[Алгоритмы вычисления оценок|Алгоритмов вычисления оценок]].
 +
* [[Тупиковые тесты]].
 +
* [[Тупиковые представительные наборы]].
 +
* Проблема оптимизации АВО. АВО как композиция метрических закономерностей.
 +
* Применение бустинга, ТЭМП и СПА для оптимизации АВО.
 +
--->
-
=== Лекция 9. Нелинейные алгоритмические композиции ===
+
== Ранжирование ==
-
* [[Смесь экспертов]], [[область компетентности]] алгоритма.
+
Презентация: [[Media:Voron-ML-Ranking-slides.pdf|(PDF,&nbsp;0,5&nbsp;МБ)]] {{важно|— обновление 14.12.2019}}.
-
* Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
+
* Постановка задачи [[Обучение ранжированию|обучения ранжированию]]. Примеры.
-
* Построение смесей экспертов с помощью EM-алгоритма.
+
* Признаки в задаче ранжирования поисковой выдачи: текстовые, ссылочные, кликовые. [[TF-IDF]]. [[PageRank]].
-
* Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии.
+
* Критерии качества ранжирования: Precision, MAP, AUC, DCG, NDCG, pFound.
 +
* Ранговая классификация, OC-SVM.
 +
* Попарный подход: RankingSVM, RankNet, LambdaRank.
-
=== Лекция 10. Логические алгоритмы классификации ===
+
== Рекомендательные системы ==
-
* Понятие [[логическая закономерность|логической закономерности]]. Эвристическое, статичтическое, энтропийное определение [[информативность|информативности]]. Асимптотическая эквивалентность статичтического и энтропийного определения. Принципиальные отличия эвристического и статичтического определения.
+
Презентация: [[Media:Voron-ML-CF.pdf|(PDF,&nbsp;0.8&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
-
* Разновидности закономерностей: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции).
+
* Задачи [[коллаборативная фильтрация|коллаборативной фильтрации]], [[транзакционные данные]] и матрица субъекты—объекты.
-
* [[Бинаризация признаков]], алгоритм выделения информативных зон.
+
* Корреляционные методы user-based, item-based. Задача восстановления пропущенных значений. Меры сходства субъектов и объектов.
-
* «Градиентный» алгоритм синтеза конъюнкций, частные случаи: жадный алгоритм, [[стохастический локальный поиск]], [[стабилизация]], [[редукция]].
+
* ''Латентные методы на основе [[би-кластеризация|би-кластеризации]]. [[Алгоритм Брегмана]].''
 +
* Латентные методы на основе матричных разложений. [[Метод главных компонент]] для разреженных данных (LFM, Latent Factor Model). [[Метод стохастического градиента]].
 +
* Неотрицательные матричные разложения. Метод чередующихся наименьших квадратов ALS.
 +
* Модель с учётом неявной информации (implicit feedback).
 +
* Рекомендации с учётом дополнительных признаковых данных. Линейная и квадратичная регрессионные модели, [[libFM]].
 +
* Измерение качества рекомендаций. Меры разнообразия (diversity), новизны (novelty), покрытия (coverage), догадливости (serendipity).
-
=== Лекция 11. Решающие списки и деревья ===
+
== Тематическое моделирование ==
-
* [[Решающий список]]. Жадный алгоритм синтеза списка.
+
Текст лекций: [[Media:Voron-ML-TopicModels.pdf|(PDF,&nbsp;830&nbsp;КБ)]].<br/>
-
* [[Решающее дерево]]. Псевдокод: жадный [[алгоритм ID3]]. Недостатки алгоритма и способы их устранения. Проблема переобучения.
+
<!---
-
* [[Редукция решающих деревьев]]: [[предредукция]] и [[постредукция]].
+
Презентация 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}}.
-
* [[Решающий лес]] и бустинг над решающими деревьями.
+
--->
-
* [[Переключающиеся решающие деревья]] (alternating decision tree).
+
Презентация: [[Media:Voron-ML-TopicModeling-slides.pdf|(PDF,&nbsp;1.6&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
 +
* Задача [[тематическое моделирование|тематического моделирования]] коллекции текстовых документов.
 +
* [[Вероятностный латентный семантический анализ]] PLSA. [[Метод максимума правдоподобия]]. [[ЕМ-алгоритм]]. Элементарная интерпретация EM-алгоритма.
 +
* [[Латентное размещение Дирихле]] LDA. [[Метод максимума апостериорной вероятности]]. Сглаженная частотная оценка условной вероятности.
 +
* Небайесовская интерпретация LDA и её преимущества. Регуляризаторы разреживания, сглаживания, частичного обучения.
 +
* Аддитивная регуляризация тематических моделей. Регуляризованный EM-алгоритм, теорема о стационарной точке (применение условий Каруша–Куна–Таккера).
 +
* Рациональный EM-алгоритм. Онлайновый EM-алгоритм и его распараллеливание.
 +
* Мультимодальная тематическая модель.
 +
* Регуляризаторы классификации и регрессии.
 +
* Регуляризаторы декоррелирования и отбора тем.
 +
* Внутренние и внешние критерии качества тематических моделей.
-
=== Лекция 12. Взвешенное голосование логических закономерностей ===
+
== Обучение с подкреплением ==
-
* Принцип голосования. Проблема различности (диверсификации) закономерностей.
+
Презентация: [[Media:Voron-ML-RL-slides.pdf|(PDF,&nbsp;1.0&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
-
* Методы синтеза конъюнктивных закономерностей. Псевдокод: [[алгоритм КОРА]], [[алгоритм ТЭМП]].
+
* Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound). Стратегия Softmax.
-
* Алгоритм бустинга. Теорема сходимости.
+
* Среда для экспериментов.
-
* Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
+
* Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования.
 +
* Постановка задачи в случае, когда агент влияет на среду. Ценность состояния среды. Ценность действия.
 +
* Жадные стратегии максимизации ценности. Уравнения оптимальности Беллмана.
 +
* Метод временных разностей TD. Метод Q-обучения.
 +
<!---* Многошаговое TD-прогнозирование. Обобщения методов временных разностей, SARSA, Q-обучения. --->
 +
* Градиентная оптимизация стратегии (policy gradient). Связь с максимизацией log-правдоподобия.
 +
* Постановка задачи при наличии информации о среде в случае выбора действия. Контекстный многорукий бандит.
 +
* Линейная регрессионная модель с верхней доверительной оценкой LinUCB.
 +
* Оценивание новой стратегии по большим историческим данным.
 +
<!---* Адаптивный полужадный метод VDBE.--->
-
=== Лекция 13. Алгоритмы вычисления оценок ===
+
== Активное обучение ==
-
* [[Принцип частичной прецедентности]]. Структура [[АВО]].
+
Презентация: [[Media:Voron-ML-AL-slides.pdf|(PDF,&nbsp;1.2&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
-
* [[Тупиковые тесты]].
+
* Постановка задачи машинного обучения. Основные стратегии: отбор объектов из выборки и из потока, синтез объектов.
-
* [[Тупиковые представительные наборы]].
+
* Сэмплирование по неуверенности. Почему активное обучение быстрее пассивного.
-
* Проблема оптимизации АВО. АВО как композиция метрических закономерностей.
+
* Сэмплирование по несогласию в комитете. Сокращение пространства решений.
-
* Применение бустинга, ТЭМП и СПА для оптимизации АВО.
+
* Сэмплирование по ожидаемому изменению модели.
 +
* Сэмплирование по ожидаемому сокращению ошибки.
 +
* Синтез объектов по критерию сокращения дисперсии.
 +
* Взвешивание по плотности.
 +
* Оценивание качества активного обучения.
 +
* Введение изучающих действий в стратегию активного обучении. Алгоритмы ε-active и EG-active.
 +
* Применение обучения с подкреплением для активного обучения. Активное томпсоновское сэмплирование.
-
=== Лекция 14. Поиск ассоциативных правил ===
+
== Заключительная лекция ==
-
* Пример прикладной задачи: [[анализ рыночных корзин]].
+
Презентация: [[Media:Voron-ML-final.pdf|(PDF,&nbsp;2.0&nbsp;МБ)]] {{важно| — обновление 14.12.2019}}.
-
* Понятие [[Ассоциативное правило|ассоциативного правила]] и его связь с понятием логической закономерности.
+
 
-
* Псевдокод: [[алгоритм APriori]], его недостатки и пути усовершенствования.
+
Обзор курса. Оптимизационные задачи машинного обучения.
-
== Файлы ==
+
= См. также =
 +
* [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/Машинное обучение (курс лекций, К.В.Воронцов)/}}
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]

Версия 19:54, 14 декабря 2019

Содержание

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

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

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

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

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

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

На материал данного курса опираются последующие кафедральные курсы.

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

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

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

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

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

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

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

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

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

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

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

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

Презентация: (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.

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

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

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

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

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

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

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

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

Факультатив

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

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

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

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

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

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

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

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

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

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

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

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

Презентация: (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.

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

Презентация: (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.

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

Презентация: (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.

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

См. также

Литература

  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Машинное обучение (курс лекций, К.В.Воронцов)/Вопросы
Машинное обучение (курс лекций, К.В.Воронцов)/Семестровый курсМашинное обучение (курс лекций, К.В.Воронцов)/Форма отчета
Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%9A.%D0%92.%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D1%86%D0%BE%D0%B2%29»
Личные инструменты