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

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

(Различия между версиями)
Перейти к: навигация, поиск
(викификация)
(ссылки, ссылки, ссылки, ссылки, ссылки)
Строка 22: Строка 22:
== Первый семестр ==
== Первый семестр ==
-
=== Вводная лекция ===
+
=== Лекция 1. Вводная лекция ===
-
Постановка задач обучения по прецедентам, типы задач. Понятия модели алгоритмов и метода обучения. Функционалы качества и принцип минимизации эмпирического риска. Понятие обобщающей способности. Скользящий контроль. Вероятностная постановка задачи и принцип максимума правдоподобия. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные. Примеры прикладных задач распознавания, классификации, кластеризации, прогнозирования.
+
* Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
 +
* Типы задач: [[классификация]], [[распознавание]], [[кластеризация]], [[прогнозирование]]. Примеры прикладных задач.
 +
* Основные понятия: [[модель алгоритмов]], [[метод обучения]], [[функция потерь]] и функционал качества, [[принцип минимизации эмпирического риска]], [[обобщающая способность]], [[скользящий контроль]].
 +
* Вероятностная постановка задачи и [[принцип максимума правдоподобия]].
-
=== Байесовские алгоритмы классификации ===
+
=== Лекция 2. Байесовские алгоритмы классификации ===
-
'''Оптимальный байесовский классификатор'''.
+
* Оптимальный [[байесовский классификатор]].
-
Функционал среднего риска. Ошибки I и II рода. Теорема об оптимальности байесовского решающего правила. Задача восстановления плотности распределения. «Наивный» байесовский классификатор.
+
* Функционал среднего риска. Ошибки I и II рода.
 +
* Теорема об оптимальности байесовского решающего правила.
 +
* [[Оценивание плотности распределения]]: три основных подхода.
 +
* [[Наивный байесовский классификатор]].
 +
* Непараметрическое оценивание плотности распределения по Парзену-Розенблатту. Выбор функции ядра. Выбор ширины окна, переменная ширина окна. Робастное оценивание плотности. [[Метод парзеновского окна]].
-
'''Непараметрическое оценивание плотности''' распределения по Парзену-Розенблатту. Выбор функции ядра. Выбор ширины окна, переменная ширина окна. Робастное оценивание плотности.
+
=== Лекция 3. Параметрическое оценивание плотности ===
 +
* [[Нормальный дискриминантный анализ]]. [[Многомерное нормальное распределение]], геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения.
 +
* [[Квадратичный дискриминант]]. Вид разделяющей поверхности. [[Подстановочный алгоритм]], его недостатки и способы их устранения.
 +
* [[Линейный дискриминант Фишера]].
 +
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]]. [[Регуляризация]] ковариационной матрицы. [[Метод редукции размерности]] Шурыгина. Робастное оценивание.
 +
* Факультатив/семинар: матричное дифференцирование.
-
'''Параметрическое оценивание плотности'''.
+
=== Лекция 4. Разделение смеси распределений ===
-
Нормальный дискриминантный анализ. Матричное дифференцирование и оценки параметров нормального распределения. Геометрическая интерпретация. Линейные и квадратичные разделяющие поверхности. Подстановочный алгоритм, его недостатки и способы их устранения.
+
* [[Смесь распределений]].
 +
* [[EM-алгоритм]]: основная идея, понятие скрытых переменных. «Вывод» алгоритма без обоснования сходимости. Псевдокод EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси.
 +
* Стохастический EM-алгоритм.
 +
* Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки.
-
'''Линейный дискриминант Фишера'''.
+
=== Лекция 5. Метрические алгоритмы классификации ===
-
Проблемы мультиколлинеарности и переобучения. Регуляризация ковариационной матрицы. Метод редукции размерности Шурыгина. Робастное оценивание.
+
* [[Метод ближайших соседей]] (''k''NN) и его обобщения.
 +
* Подбор числа ''k'' по критерию скользящего контроля.
 +
* Обобщённый [[метрический классификатор]].
 +
* [[Метод потенциальных функций]], градиентный алгоритм.
 +
* Настройка весов объектов. Отбор эталонных объектов. Псевдокод: [[алгоритм СТОЛП]].
 +
* [[Проклятие размерности]]. Настройка весов признаков.
 +
* Концепция [[CBR]].
-
'''Разделение смеси распределений'''.
+
=== Лекция 6. Кластеризация ===
-
EM-алгоритм. Теорема о смеси многомерных нормальных распределений. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси. Стохастический EM-алгоритм. Сети радиальных базисных функций (RBF) и их настройка с помощью EM-алгоритма.
+
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач.
 +
* [[Графовые алгоритмы кластеризации]]. Алгоритм связных компонент.
 +
* Псевдокод алгоритма: [[кратчайший незамкнутый путь]].
 +
* Псевдокод алгоритма: [[ФОРЭЛ]].
 +
* Функционалы качества кластеризации.
 +
* Статистические алгоритмы: [[EM-алгоритм]]. Псевдокод алгоритма [[k-means]].
-
=== Метрические алгоритмы классификации ===
+
=== Лекция 7. Иерерхическая кластеризация и многомерное шкалирование ===
-
Метод k ближайших соседей (kNN) и его обобщения. Подбор числа k по критерию скользящего контроля. Обобщённый метрический классификатор. Метод потенциальных функций, градиентный алгоритм. Настройка весов объектов. Отбор эталонных объектов.
+
* Псевдокод алгоритма: [[агломеративная кластеризация]]. [[Формула Ланса-Вильямса]].
 +
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров.
 +
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
 +
Потоковые (субквадратичные) алгоритмы кластеризации.
 +
* [[Многомерное шкалирование]]. Размещение одной точки методом Ньютона-Рафсона. Субквадратичный алгоритм.
 +
* Визуализация: [[карта сходства]], [[диаграмма Шепарда]].
 +
* Совмещение многомерного шкалирования и иерархической кластеризации.
 +
* Примеры прикладных задач.
-
=== Кластеризация и многомерное шкалирование ===
+
=== Лекция 8. Непараметрическая регрессия ===
-
'''Методы кластеризации'''.
+
* Локально взвешенный [[метод наименьших квадратов]] и [[оценка Надарая-Ватсона]].
-
Примеры прикладных задач. Графовые алгоритмы: связные компоненты, кратчайший незамкнутый путь, Форель. Функционалы качества кластеризации. Статистические алгоритмы: EM и k-means. Агломеративные (иерархические) алгоритмы. Формула Ланса-Вильямса. Алгоритм построения дендрограммы. Свойства сжатия/растяжения, монотонности и редуктивности. Определение числа кластеров. Потоковые (субквадратичные) алгоритмы кластеризации.
+
* [[Сглаживание]].
 +
* Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна.
 +
* Проблема выбросов и робастная непараметрическая регрессия. Псевдокод: [[алгоритм LOWESS]].
 +
* Проблема «проклятия размерности» и проблема выбора метрики.
-
'''Многомерное шкалирование'''.
+
=== Лекция 9. Многомерная линейная регрессия ===
-
Размещение одной точки методом Ньютона-Рафсона. Субквадратичный алгоритм. Визуализация: карты сходства и диаграммы Шепарда. Совмещение многомерного шкалирования и иерархической кластеризации. Примеры прикладных задач.
+
* Задача регрессии, [[многомерная линейная регрессия]].
 +
* [[Метод наименьших квадратов]]. [[Сингулярное разложение]].
 +
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]].
 +
* [[Регуляризация]]. [[Гребневая регрессия]]. [[Лассо Тибширани]]. Линейная монотонная регрессия (симплекс-метод).
 +
* Линейные преобразования признакового пространства. [[Метод главных компонент]] и [[декоррелирующее преобразование]] Карунена-Лоэва.
 +
* [[Робастная регрессия]].
-
=== Алгоритмы восстановления регрессии ===
+
=== Лекция 10. Шаговая регрессия ===
-
'''Непараметрическая регрессия'''.
+
* [[Модифицированная ортогонализация Грама-Шмидта]], достоинства и недостатки.
-
Локально взвешенный метод наименьших квадратов и оценка Надарая-Ватсона. Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна. Проблема «выбросов» и робастная непараметрическая регрессия. Проблема «проклятия размерности» и проблема выбора метрики.
+
* [[Отбор признаков]] в процессе ортогонализации, критерии выбора и останова.
 +
* [[Метод наименьших углов]], его связь с лассо и шаговой регрессией.
-
'''Многомерная линейная регрессия'''.
+
=== Лекция 11. Нелинейная параметрическая регрессия ===
-
Принцип наименьших квадратов. Сингулярное разложение. Проблемы мультиколлинеарности и переобучения. Гребневая регрессия. Лассо Тибширани. Линейная монотонная регрессия (симплекс-метод). Линейные преобразования признакового пространства. Метод главных компонент и декоррелирующее преобразование Карунена-Лоэва. Робастная регрессия.
+
* [[Метод Ньютона-Рафсона]], [[метод Ньютона-Гаусса]].
 +
* Одномерные нелинейные преобразования признаков: [[метод обратной настройки]] (backfitting) Хасти-Тибширани.
 +
* [[Обобщённая линейная модель]] (GLM).
 +
* Неквадратичные функции потерь, примеры прикладных задач.
-
'''Шаговая регрессия'''.
+
=== Лекция 12. Логистическая регрессия ===
-
Алгоритм модифицированной ортогонализации Грама-Шмидта, достоинства и недостатки. Отбор признаков в процессе ортогонализации, критерии выбора и останова. Метод наименьших углов, его связь с лассо и шаговой регрессией.
+
* [[Линейный классификатор]]. «Наивное» сведение задачи классификации к задаче регрессии, его недостатки.
 +
* Гладкие аппроксимации пороговой функции потерь.
 +
* Обоснование [[Логистическая регрессия|логистической регрессии]]: теорема об экспонентных плотностях.
 +
* [[Метод наименьших квадратов с итеративным пересчетом весов]] (IRLS).
 +
* Настройка порога решающего правила по критерию числа ошибок I и II рода, [[кривая ошибок]] (lift curve), отказы от классификации.
 +
* Пример прикладной задачи: кредитный скоринг и скоринговые карты.
-
'''Нелинейная параметрическая регрессия'''.
+
=== Лекция 13. Элементы теории обобщающей способности ===
-
Методы Ньютона-Рафсона и Ньютона-Гаусса. Одномерные нелинейные преобразования признаков: метод обратной настройки (backfitting) Хасти-Тибширани. Обобщённые линейные модели. Неквадратичные функции потерь, примеры прикладных задач.
+
* [[Принцип равномерной сходимости]]. [[Скользящий контроль]]. [[Теория Вапника-Червоненкиса]].
 +
* [[Функция роста]] и [[ёмкость]].
 +
* Ёмкость некоторых семейств алгоритмов.
 +
* [[Метод структурной минимизации риска]].
 +
* [[Принцип минимума длины описания]].
 +
* Достаточная длина обучающей выборки.
 +
* Причины завышенности оценок Вапника-Червоненкиса.
 +
* Эффекты локализации (расслоения) семейства алгоритмов и различности алгоритмов.
 +
* Оценки, зависящие от данных. Оценки, зависящие от отступов. Принцип самоограничения сложности. Понятие стабильности обучения.
 +
* Эмпирическое оценивание обобщающей способности. Анализ вариации и смещения.
-
'''Логистическая регрессия'''.
+
=== Лекция 14. Оценивание и выбор моделей ===
-
Линейный пороговый классификатор. «Наивное» сведение задачи классификации к задаче регрессии, его недостатки. Гладкие аппроксимации пороговой функции потерь. Обоснование логистической регрессии: теорема об экспонентных плотностях. Метод наименьших квадратов с итеративным пересчетом весов. Настройка порога решающего правила по критерию числа ошибок I и II рода, кривая ошибок (lift curve), отказы от классификации. Пример прикладной задачи: кредитный скоринг и скоринговые карты.
+
* Внутренние и [[внешние критерии]].
 +
* [[Скользящий контроль]].
 +
* [[Критерий непротиворечивости]].
 +
* [[Регуляризация]].
 +
* Критерии, основанные на оценках обобщающей способности: Вапника-Червоненкиса, [[критерий Акаике]] (AIC), [[байесовский информационный критерий]] (BIC).
 +
* Статистические критерии: [[коэффициент детерминации]], [[критерий Фишера]], [[анализ остатков]].
-
=== Элементы теории обобщающей способности ===
+
=== Лекция 15. Методы отбора признаков ===
-
Функционалы скользящего контроля. Теорема Вапника-Червоненкиса. Функция роста и ёмкость. Емкость некоторых семейств алгоритмов. Метод структурной минимизации риска. Принцип минимума длины описания. Достаточная длина обучающей выборки. Причины завышенности оценок Вапника-Червоненкиса. Эффект локализации семейства алгоритмов. Оценки, зависящие от данных. Принцип самоограничения сложности. Декомпозиция ошибки на шум, смещение и вариацию. Понятие стабильности обучения. Методы эмпирического оценивания обобщающей способности.
+
* Сложность задачи [[отбор признаков|отбора признаков]]. [[Полный перебор]].
 +
* [[Метод добавления и удаления]] (шаговая регрессия).
 +
* [[Поиск в глубину]] (метод ветвей и границ).
 +
* Усечённый [[поиск в ширину]] ([[многорядный итерационный алгоритм МГУА]]).
 +
* [[Генетический алгоритм]], его сходство с МГУА.
 +
* [[Случайный поиск с адаптацией]] (СПА).
-
=== Оценивание и выбор моделей ===
+
== Второй семестр ==
-
'''Критерии качества модели'''.
+
-
Внутренние и внешние критерии. Скользящий контроль, критерии непротиворечивости и регуляризации. Критерии, основанные на оценках обобщающей способности: Вапника-Червоненкиса, Акаике (AIC), байесовский (BIC). Статистические критерии: коэффициент детерминации, критерий Фишера, анализ остатков.
+
-
'''Методы отбора признаков'''.
+
=== Лекция 1. Однослойный персептрон ===
-
Полный перебор, методы добавлений и удалений (шаговая регрессия), поиск в глубину (метод ветвей и границ), усечённый поиск в ширину (многорядный итерационный алгоритм МГУА), генетический алгоритм, случайный поиск с адаптацией.
+
* Естественный нейрон, [[модель МакКаллока-Питтса]].
 +
* [[Персептрон Розенблатта]].
 +
* [[Метод стохастического градиента]]. [[Теорема Новикова]] о сходимости.
 +
* Связь однослойного персептрона с логистической регрессией и обоснование сигмоидной функции потерь.
 +
* [[Проблема исключающего или]]. Проблема полноты. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).
-
== Второй семестр ==
+
=== Лекция 2. Многослойные нейронные сети ===
 +
* [[Алгоритм обратного распространения ошибок]]. Недостатки алгоритма, способы их устранения.
 +
* Проблема переобучения.
 +
* Проблема [[паралич сети|«паралича» сети]].
 +
* [[Редукция весов]] (weight decay).
 +
* Подбор структуры сети.
 +
* [[Метод оптимального прореживания сети]] (optimal brain damage).
-
=== Нейронные сети ===
+
=== Лекция 3. Обучающееся векторное квантование (сети Кохонена) ===
-
'''Персептроны'''.
+
* [[Сеть Кохонена]]. [[Конкурентное обучение]], стратегии WTA и WTM.
-
Естественный нейрон и его математическая модель. Персептрон Розенблатта. Метод стохастического градиента. Теорема сходимости (Новикова). Связь однослойного персептрона с логистической регрессией и обоснование сигмоидной функции потерь. Проблема «исключающего или». Проблема полноты. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).
+
* [[Самоорганизующаяся карта Кохонена]]. Применение для визуального анализа данных.
 +
* [[Сети встречного распространения]], их применение для кусочно-постоянной и гладкой аппроксимации функций.
-
'''Многослойные нейронные сети'''.
+
=== Лекция 4. Метод опорных векторов ===
-
Алгоритм обратного распространения ошибок. Недостатки алгоритма, способы их устранения. Проблема переобучения. Проблема «паралича» сети. Редукция весов. Подбор структуры сети. Метод оптимальной редукции сети (optimal brain damage).
+
* Оптимальная разделяющая гиперплоскость. Понятие [[зазор]]а между классами (margin).
 +
* Случай линейной разделимости. Задача квадратичного программирования и двойственная задача. Понятие [[Опорный вектор|опорных векторов]].
 +
* Случай отсутствия линейной разделимости. Двойственная задача. Отличие от предыдущего случая. Выбор константы ''C''.
 +
* [[Функция ядра]] (kernel functions), [[спрямляющее пространство]], [[теорема Мерсера]].
 +
* Способы построения ядер. Примеры ядер.
 +
* Сопоставление SVM и RBF-сети.
-
'''Обучающееся векторное квантование (сети Кохонена)'''.
+
=== Лекция 5. Оптимизационные техники решения задачи SVM ===
-
Структура сети Кохонена. Конкурентное обучение, стратегии WTA и WTM. Самоорганизующиеся карты Кохонена. Применение для визуального анализа данных. Сети встречного распространения, их применение для кусочно-постоянной и гладкой аппроксимации функций.
+
* Обучение SVM методом последовательной оптимизации минимумов. Псевдокод: [[алгоритм SMO]].
 +
* Обучение SVM методом активных ограничений. Псевдокод: [[алгоритм INCAS]].
 +
* SVM-регрессия.
-
=== Машины опорных векторов ===
+
=== Лекция 6. Алгоритмические композиции ===
-
Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin). Случай линейной разделимости. Задача квадратичного программирования. Опорные векторы. Случай отсутствия линейной разделимости. Функции ядра (kernel functions), спрямляющее пространство, теорема Мерсера. Способы построения ядер. Примеры ядер. Сопоставление SVM и нейронной RBF-сети. Обучение SVM методом активных ограничений. SVM-регрессия.
+
* Основные понятия: [[базовый алгоритм]] ([[алгоритмический оператор]]), [[корректирующая операция]].
 +
* Линейные (выпуклые) алгоритмические композиции.
 +
* Процесс последовательного обучения базовых алгоритмов.
 +
* [[Простое голосование]] (комитет большинства). Эвристический алгоритм.
 +
* [[Решающий список]] (комитет старшинства). Эвристический алгоритм.
-
=== Алгоритмические композиции ===
+
=== Лекция 7. Бустинг, бэггинг и аналоги ===
-
'''Линейные алгоритмические композиции'''.
+
* [[Взвешенное голосование]].
-
Понятия базового алгоритма и корректирующей операции. Процесс последовательного обучения базовых алгоритмов. Простое голосование (комитет большинства). Решающий список (комитет старшинства). Взвешенное голосование. Бустинг: алгоритм AdaBoost, теорема сходимости. Стохастические методы: бэггинг и метод случайных подпространств.
+
* Экспоненциальная аппроксимация пороговой функции потерь. Теорема о сходимости [[бустинг]]а.
 +
* Псевдокод: [[алгоритм AdaBoost]].
 +
* Варианты бустинга: GentleBoost, LogitBoost, BrownBoost, и другие.
 +
* Стохастические методы: [[бэггинг]] и [[метод случайных подпространств]].
-
'''Метод комитетов'''.
+
=== Лекция 8. Метод комитетов ===
-
Комитеты большинства, простое и взвешенное голосование. Сопоставление с нейронной сетью. Понятия максимальной совместной подсистемы и минимального комитета. Алгоритм построения комитета большинства. Верхняя оценка числа членов комитета.
+
* Общее понятие: [[комитет]] системы ограничений. Комитеты большинства, простое и взвешенное голосование (''z,p''-комитеты).
 +
* Теоремы о существовании комитетного решения.
 +
* Сопоставление комитета линейных неравенств с нейронной сетью.
 +
* [[Максимальная совместная подсистема]], [[минимальный комитет]]. Теоремы об ''NP''-полноте задачи поиска минимального комитета.
 +
* Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.
-
'''Нелинейные алгоритмические композиции'''.
+
=== Лекция 9. Нелинейные алгоритмические композиции ===
-
Смеси экспертов, понятие области компетентности алгоритма. Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический. Построение смесей экспертов с помощью EM-алгоритма. Нелинейная монотонная коррекция.
+
* [[Смесь экспертов]], [[область компетентности]] алгоритма.
 +
* Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
 +
* Построение смесей экспертов с помощью EM-алгоритма.
 +
* Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии.
-
=== Логические алгоритмы классификации ===
+
=== Лекция 10. Логические алгоритмы классификации ===
-
'''Понятие логической закономерности'''. Энтропийное и комбинаторное определения информативности, их асимптотическая эквивалентность. Разновидности закономерностей: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции). Бинаризация признаков, алгоритм выделения информативных зон. «Градиентный» алгоритм синтеза конъюнкций, частные случаи: жадный алгоритм, стохастический локальный поиск, стабилизация, редукция.
+
* Понятие [[логическая закономерность|логической закономерности]]. Эвристическое, статичтическое, энтропийное определение [[информативность|информативности]]. Асимптотическая эквивалентность статичтического и энтропийного определения. Принципиальные отличия эвристического и статичтического определения.
 +
* Разновидности закономерностей: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции).
 +
* [[Бинаризация признаков]], алгоритм выделения информативных зон.
 +
* «Градиентный» алгоритм синтеза конъюнкций, частные случаи: жадный алгоритм, [[стохастический локальный поиск]], [[стабилизация]], [[редукция]].
-
'''Решающие списки'''. Жадный алгоритм синтеза списка. Разновидности решающих правил в списках: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции).
+
=== Лекция 11. Решающие списки и деревья ===
 +
* [[Решающий список]]. Жадный алгоритм синтеза списка.
 +
* [[Решающее дерево]]. Псевдокод: жадный [[алгоритм ID3]]. Недостатки алгоритма и способы их устранения. Проблема переобучения.
 +
* [[Редукция решающих деревьев]]: [[предредукция]] и [[постредукция]].
 +
* Преобразование решающего дерева в решающий список.
 +
* [[Решающий лес]] и бустинг над решающими деревьями.
 +
* [[Переключающиеся решающие деревья]] (alternating decision tree).
-
'''Решающие деревья'''. Алгоритм синтеза дерева ID3. Недостатки алгоритма и способы их устранения. Проблема переобучения. Редукция решающих деревьев: предредукция и постредукция. Преобразование решающего дерева в решающий список. Решающий лес и бустинг над решающими деревьями.
+
=== Лекция 12. Взвешенное голосование логических закономерностей ===
 +
* Принцип голосования. Проблема различности (диверсификации) закономерностей.
 +
* Методы синтеза конъюнктивных закономерностей. Псевдокод: [[алгоритм КОРА]], [[алгоритм ТЭМП]].
 +
* Алгоритм бустинга. Теорема сходимости.
 +
* Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
-
'''Взвешенное голосование логических закономерностей'''.
+
=== Лекция 13. Алгоритмы вычисления оценок ===
-
Принцип голосования. Проблема различности (диверсификации) закономерностей. Алгоритмы синтеза конъюнктивных закономерностей КОРА и ТЭМП. Применение ТЭМП для синтеза решающего списка. Алгоритм бустинга. Теорема сходимости. Взвешенные решающие деревья (alternating decision tree). Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
+
* [[Принцип частичной прецедентности]]. Структура [[АВО]].
 +
* [[Тупиковые тесты]].
 +
* [[Тупиковые представительные наборы]].
 +
* Проблема оптимизации АВО. АВО как композиция метрических закономерностей.
 +
* Применение бустинга, ТЭМП и СПА для оптимизации АВО.
-
'''Алгоритмы вычисления оценок'''.
+
=== Лекция 14. Поиск ассоциативных правил ===
-
Принцип частичной прецедентности. Структура АВО. Тупиковые тесты и тупиковые представительные наборы. Проблема оптимизации АВО. АВО как композиция метрических закономерностей. Применение бустинга для оптимизации АВО.
+
* Пример прикладной задачи: [[анализ рыночных корзин]].
-
 
+
* Понятие [[Ассоциативное правило|ассоциативного правила]] и его связь с понятием логической закономерности.
-
'''Поиск ассоциативных правил'''.
+
* Псевдокод: [[алгоритм APriori]], его недостатки и пути усовершенствования.
-
Пример прикладной задачи: анализ рыночных корзин. Понятие ассоциативного правила и его связь с понятием логической закономерности. Алгоритм APriori, его недостатки и пути усовершенствования.
+
== Файлы ==
== Файлы ==
-
 
-
Программа курса
 
Экзаменационные билеты
Экзаменационные билеты

Версия 18:50, 23 июля 2008

Содержание

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

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

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

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

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

Курс читается студентам 3 курса кафедры «Интеллектуальные системы / интеллектуальный анализ данных» ФУПМ МФТИ с 2004 года и студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года. На материал данного курса существенно опираются последующие курсы, читаемые студентам на этих кафедрах.

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

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

Лекция 1. Вводная лекция

Лекция 2. Байесовские алгоритмы классификации

Лекция 3. Параметрическое оценивание плотности

Лекция 4. Разделение смеси распределений

  • Смесь распределений.
  • EM-алгоритм: основная идея, понятие скрытых переменных. «Вывод» алгоритма без обоснования сходимости. Псевдокод EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси.
  • Стохастический EM-алгоритм.
  • Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.

Лекция 5. Метрические алгоритмы классификации

Лекция 6. Кластеризация

Лекция 7. Иерерхическая кластеризация и многомерное шкалирование

Потоковые (субквадратичные) алгоритмы кластеризации.

Лекция 8. Непараметрическая регрессия

Лекция 9. Многомерная линейная регрессия

Лекция 10. Шаговая регрессия

Лекция 11. Нелинейная параметрическая регрессия

Лекция 12. Логистическая регрессия

Лекция 13. Элементы теории обобщающей способности

Лекция 14. Оценивание и выбор моделей

Лекция 15. Методы отбора признаков

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

Лекция 1. Однослойный персептрон

Лекция 2. Многослойные нейронные сети

Лекция 3. Обучающееся векторное квантование (сети Кохонена)

Лекция 4. Метод опорных векторов

  • Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin).
  • Случай линейной разделимости. Задача квадратичного программирования и двойственная задача. Понятие опорных векторов.
  • Случай отсутствия линейной разделимости. Двойственная задача. Отличие от предыдущего случая. Выбор константы C.
  • Функция ядра (kernel functions), спрямляющее пространство, теорема Мерсера.
  • Способы построения ядер. Примеры ядер.
  • Сопоставление SVM и RBF-сети.

Лекция 5. Оптимизационные техники решения задачи SVM

  • Обучение SVM методом последовательной оптимизации минимумов. Псевдокод: алгоритм SMO.
  • Обучение SVM методом активных ограничений. Псевдокод: алгоритм INCAS.
  • SVM-регрессия.

Лекция 6. Алгоритмические композиции

Лекция 7. Бустинг, бэггинг и аналоги

Лекция 8. Метод комитетов

  • Общее понятие: комитет системы ограничений. Комитеты большинства, простое и взвешенное голосование (z,p-комитеты).
  • Теоремы о существовании комитетного решения.
  • Сопоставление комитета линейных неравенств с нейронной сетью.
  • Максимальная совместная подсистема, минимальный комитет. Теоремы об NP-полноте задачи поиска минимального комитета.
  • Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.

Лекция 9. Нелинейные алгоритмические композиции

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

Лекция 10. Логические алгоритмы классификации

Лекция 11. Решающие списки и деревья

Лекция 12. Взвешенное голосование логических закономерностей

  • Принцип голосования. Проблема различности (диверсификации) закономерностей.
  • Методы синтеза конъюнктивных закономерностей. Псевдокод: алгоритм КОРА, алгоритм ТЭМП.
  • Алгоритм бустинга. Теорема сходимости.
  • Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.

Лекция 13. Алгоритмы вычисления оценок

Лекция 14. Поиск ассоциативных правил

Файлы

Экзаменационные билеты

Практикум

Личные инструменты