Машинное обучение (курс лекций, К.В.Воронцов)
Материал из MachineLearning.
(Различия между версиями)
(→Параметрическое оценивание плотности) |
(Программа 1-го семестра приведена в соотвествие с прочитанными лекциями (ВМК, осень 2008)) |
||
| Строка 15: | Строка 15: | ||
Данный курс существенно расширяет и углубляет набор тем, рекомендованный международным стандартом '''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 курса кафедры [[Интеллектуальные системы (кафедра МФТИ)|«Интеллектуальные системы / интеллектуальный анализ данных» ФУПМ МФТИ]] с 2004 года; | ||
| + | студентам 3 курса кафедры [[Математические методы прогнозирования (кафедра ВМиК МГУ)|«Математические методы прогнозирования» ВМиК МГУ]] с 2007 года; | ||
| + | студентам [[Школа анализа данных Яндекс|Школы анализа данных Яндекс]] с 2009 года. | ||
| + | |||
На материал данного курса существенно опираются последующие кафедральные курсы. | На материал данного курса существенно опираются последующие кафедральные курсы. | ||
На кафедре ММП ВМиК МГУ параллельно с данным курсом и в дополнение к нему читается спецкурс [[Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)|Теория надёжности обучения по прецедентам]], посвящённый проблемам [[Переобучение|переобучения]] и оценивания [[Обобщающая способность|обобщающей способности]]. | На кафедре ММП ВМиК МГУ параллельно с данным курсом и в дополнение к нему читается спецкурс [[Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)|Теория надёжности обучения по прецедентам]], посвящённый проблемам [[Переобучение|переобучения]] и оценивания [[Обобщающая способность|обобщающей способности]]. | ||
| Строка 60: | Строка 64: | ||
* [[Метод потенциальных функций]], градиентный алгоритм. | * [[Метод потенциальных функций]], градиентный алгоритм. | ||
* Отбор эталонных объектов. Псевдокод: [[алгоритм СТОЛП]]. | * Отбор эталонных объектов. Псевдокод: [[алгоритм СТОЛП]]. | ||
| + | <!-- | ||
* Настройка весов объектов. | * Настройка весов объектов. | ||
* [[Проклятие размерности]]. Настройка весов признаков. | * [[Проклятие размерности]]. Настройка весов признаков. | ||
* Вывод на основе прецедентов ([[CBR]]). | * Вывод на основе прецедентов ([[CBR]]). | ||
| + | --> | ||
=== Линейные алгоритмы классификации === | === Линейные алгоритмы классификации === | ||
| - | * | + | * Биологический нейрон, [[модель МакКаллока-Питтса]]. |
| - | * [[Линейный классификатор]], непрерывные аппроксимации | + | * [[Линейный классификатор]], функции активации, непрерывные аппроксимации пороговой функции потерь. |
* Квадратичная функция потерь, [[метод наименьших квадратов]], связь с линейным дискриминантом Фишера. | * Квадратичная функция потерь, [[метод наименьших квадратов]], связь с линейным дискриминантом Фишера. | ||
* [[Метод стохастического градиента]] и частные случаи: [[адаптивный линейный элемент]] ADALINE, [[перцептрон Розенблатта]], [[правило Хэбба]]. | * [[Метод стохастического градиента]] и частные случаи: [[адаптивный линейный элемент]] ADALINE, [[перцептрон Розенблатта]], [[правило Хэбба]]. | ||
| Строка 75: | Строка 81: | ||
* Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации. | * Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации. | ||
* [[Логистическая регрессия]]. Принцип максимума правдоподобия и логарифмическая функция потерь. Снова метод стохастического градиента, аналогия с правилом Хэбба. | * [[Логистическая регрессия]]. Принцип максимума правдоподобия и логарифмическая функция потерь. Снова метод стохастического градиента, аналогия с правилом Хэбба. | ||
| - | |||
| - | |||
=== Нейронные сети === | === Нейронные сети === | ||
* Проблема полноты. [[Задача исключающего или]]. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства). | * Проблема полноты. [[Задача исключающего или]]. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства). | ||
| - | * [[Алгоритм обратного распространения ошибок]]. Недостатки алгоритма, способы их устранения. | + | * [[Алгоритм обратного распространения ошибок]]. Способы формирования начального приближения. Недостатки алгоритма, способы их устранения. |
* Подбор структуры сети: методы постепенного усложнения сети, [[оптимальное прореживание нейронных сетей]] (optimal brain damage). | * Подбор структуры сети: методы постепенного усложнения сети, [[оптимальное прореживание нейронных сетей]] (optimal brain damage). | ||
=== Метод опорных векторов === | === Метод опорных векторов === | ||
* Оптимальная разделяющая гиперплоскость. Понятие [[зазор]]а между классами (margin). | * Оптимальная разделяющая гиперплоскость. Понятие [[зазор]]а между классами (margin). | ||
| - | * Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией эмпирического риска | + | * Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь. |
* Задача квадратичного программирования и двойственная задача. Понятие [[Опорный вектор|опорных векторов]]. | * Задача квадратичного программирования и двойственная задача. Понятие [[Опорный вектор|опорных векторов]]. | ||
* Рекомендации по выбору константы ''C''. | * Рекомендации по выбору константы ''C''. | ||
* [[Функция ядра]] (kernel functions), [[спрямляющее пространство]], [[теорема Мерсера]]. | * [[Функция ядра]] (kernel functions), [[спрямляющее пространство]], [[теорема Мерсера]]. | ||
| - | * Способы построения ядер. Примеры ядер. | + | * Способы конструктивного построения ядер. Примеры ядер. |
| - | * Сопоставление SVM и RBF-сети. | + | * Сопоставление SVM с гауссовским ядром и RBF-сети. |
| + | * Обучение SVM методом активных ограничений. Псевдокод: [[алгоритм INCAS]]. | ||
| + | <!-- | ||
=== Методы оптимизации SVM === | === Методы оптимизации SVM === | ||
* Обучение SVM методом последовательной минимизации. Псевдокод: [[алгоритм SMO]]. | * Обучение SVM методом последовательной минимизации. Псевдокод: [[алгоритм SMO]]. | ||
| - | |||
* SVM-регрессия. | * SVM-регрессия. | ||
| + | --> | ||
| + | |||
| + | === Обобщённый линейный классификатор === | ||
| + | * Задача максимизации совместного правдоподобия данных и модели. | ||
| + | * Возможные типы априорных предположений о вероятностном распределении в пространстве параметров и их связь с регуляризацией. | ||
| + | * Некоторые разновидности регуляризаторов, применяемые на практике. | ||
| + | * Настройка порога решающего правила по критерию числа ошибок I и II рода. [[Кривая ошибок]] (ROC curve). | ||
| + | <!-- | ||
| + | * Пример прикладной задачи: кредитный скоринг и скоринговые карты. | ||
| + | --> | ||
=== Непараметрическая регрессия === | === Непараметрическая регрессия === | ||
* [[Сглаживание]]. Локально взвешенный [[метод наименьших квадратов]] и [[оценка Надарая-Ватсона]]. | * [[Сглаживание]]. Локально взвешенный [[метод наименьших квадратов]] и [[оценка Надарая-Ватсона]]. | ||
* Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна. | * Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна. | ||
| - | |||
* Проблема выбросов и робастная непараметрическая регрессия. Псевдокод: [[алгоритм LOWESS]]. | * Проблема выбросов и робастная непараметрическая регрессия. Псевдокод: [[алгоритм LOWESS]]. | ||
| + | <!-- | ||
| + | * Доверительный интервал значения регрессии в точке. | ||
* Проблема «проклятия размерности» и выбор метрики. | * Проблема «проклятия размерности» и выбор метрики. | ||
| + | --> | ||
=== Многомерная линейная регрессия === | === Многомерная линейная регрессия === | ||
| Строка 108: | Строка 125: | ||
* [[Метод наименьших квадратов]]. [[Сингулярное разложение]]. | * [[Метод наименьших квадратов]]. [[Сингулярное разложение]]. | ||
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]]. | * Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]]. | ||
| - | * [[Регуляризация]]. [[Гребневая регрессия]]. [[Лассо Тибширани]]. | + | * [[Регуляризация]]. [[Гребневая регрессия]]. [[Лассо Тибширани]]. |
* Линейные преобразования признакового пространства, задача сокращения размерности. [[Метод главных компонент]] и [[декоррелирующее преобразование]] Карунена-Лоэва. | * Линейные преобразования признакового пространства, задача сокращения размерности. [[Метод главных компонент]] и [[декоррелирующее преобразование]] Карунена-Лоэва. | ||
| - | |||
| + | <!-- | ||
=== Шаговая регрессия === | === Шаговая регрессия === | ||
* [[Модифицированная ортогонализация Грама-Шмидта]], достоинства и недостатки. | * [[Модифицированная ортогонализация Грама-Шмидта]], достоинства и недостатки. | ||
* [[Отбор признаков]] в процессе ортогонализации, критерии выбора и останова. | * [[Отбор признаков]] в процессе ортогонализации, критерии выбора и останова. | ||
* [[Метод наименьших углов]] (LARS), его связь с лассо и шаговой регрессией. | * [[Метод наименьших углов]] (LARS), его связь с лассо и шаговой регрессией. | ||
| + | --> | ||
=== Нелинейная параметрическая регрессия === | === Нелинейная параметрическая регрессия === | ||
| Строка 123: | Строка 141: | ||
* [[Логистическая регрессия]] как частный случай GLM, [[метод наименьших квадратов с итеративным пересчётом весов]] (IRLS). | * [[Логистическая регрессия]] как частный случай GLM, [[метод наименьших квадратов с итеративным пересчётом весов]] (IRLS). | ||
| + | <!-- | ||
=== Прогнозирование временных рядов === | === Прогнозирование временных рядов === | ||
* Аддитивная модель временного ряда: тренд, сезонность, цикличность. Модель Бокса-Дженкинса. Модель ARIMA — авторегрессии и интегрированного скользящего среднего. | * Аддитивная модель временного ряда: тренд, сезонность, цикличность. Модель Бокса-Дженкинса. Модель ARIMA — авторегрессии и интегрированного скользящего среднего. | ||
* Адаптивные модели. Примеры экономических приложений. | * Адаптивные модели. Примеры экономических приложений. | ||
* Неквадратичные функции потерь, примеры прикладных задач. | * Неквадратичные функции потерь, примеры прикладных задач. | ||
| + | --> | ||
== Второй семестр == | == Второй семестр == | ||
Версия 01:09, 14 января 2009
Машинное обучение возникло на стыке прикладной статистики, оптимизации, дискретного анализа, и за последние 30 лет оформилось в самостоятельную математическую дисциплину. Методы машинного обучения составляют основу ещё более молодой дисциплины — интеллектуального анализа данных (data mining).
В курсе рассматриваются основные задачи обучения по прецедентам: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.
Все методы излагаются по единой схеме:
- исходные идеи и эвристики;
- их формализация и математическая теория;
- описание алгоритма в виде слабо формализованного псевдокода;
- анализ достоинств, недостатков и границ применимости;
- пути устранения недостатков;
- сравнение с другими методами;
- примеры прикладных задач.
Данный курс существенно расширяет и углубляет набор тем, рекомендованный международным стандартом ACM/IEEE Computing Curricula 2001 по дисциплине «Машинное обучение и нейронные сети» (machine learning and neural networks) в разделе «Интеллектуальные системы» (intelligent systems).
Курс читается студентам 3 курса кафедры «Интеллектуальные системы / интеллектуальный анализ данных» ФУПМ МФТИ с 2004 года; студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года; студентам Школы анализа данных Яндекс с 2009 года.
На материал данного курса существенно опираются последующие кафедральные курсы. На кафедре ММП ВМиК МГУ параллельно с данным курсом и в дополнение к нему читается спецкурс Теория надёжности обучения по прецедентам, посвящённый проблемам переобучения и оценивания обобщающей способности.
От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание математической статистики, методов оптимизации и какого-либо языка программирования желательно, но не обязательно.
Первый семестр
Вводная лекция
- Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
- Типы задач: классификация, регрессия, прогнозирование, кластеризация. Примеры прикладных задач.
- Основные понятия: модель алгоритмов, метод обучения, функция потерь и функционал качества, принцип минимизации эмпирического риска, обобщающая способность, скользящий контроль.
- Вероятностная постановка задачи, принцип максимума правдоподобия и его связь с принципом минимизации эмпирического риска.
Байесовские алгоритмы классификации
- Оптимальный байесовский классификатор.
- Функционал среднего риска. Ошибки I и II рода.
- Теорема об оптимальности байесовского решающего правила.
- Оценивание плотности распределения: три основных подхода.
- Наивный байесовский классификатор.
- Непараметрическое оценивание плотности распределения по Парзену-Розенблатту. Выбор функции ядра. Выбор ширины окна, переменная ширина окна. Робастное оценивание плотности. Метод парзеновского окна.
Параметрическое оценивание плотности
- Нормальный дискриминантный анализ. Многомерное нормальное распределение, геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения.
- Квадратичный дискриминант. Вид разделяющей поверхности. Подстановочный алгоритм, его недостатки и способы их устранения.
- Линейный дискриминант Фишера.
- Проблемы мультиколлинеарности и переобучения. Регуляризация ковариационной матрицы.
- Робастное оценивание. Цензурирование выборки (отсев объектов-выбросов).
Разделение смеси распределений
- Смесь распределений.
- EM-алгоритм: основная идея, понятие скрытых переменных. «Вывод» алгоритма без обоснования сходимости. Псевдокод EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси.
- Стохастический EM-алгоритм.
- Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.
Метрические алгоритмы классификации
- Метод ближайших соседей (kNN) и его обобщения.
- Подбор числа k по критерию скользящего контроля.
- Обобщённый метрический классификатор, понятие отступа.
- Метод потенциальных функций, градиентный алгоритм.
- Отбор эталонных объектов. Псевдокод: алгоритм СТОЛП.
Линейные алгоритмы классификации
- Биологический нейрон, модель МакКаллока-Питтса.
- Линейный классификатор, функции активации, непрерывные аппроксимации пороговой функции потерь.
- Квадратичная функция потерь, метод наименьших квадратов, связь с линейным дискриминантом Фишера.
- Метод стохастического градиента и частные случаи: адаптивный линейный элемент ADALINE, перцептрон Розенблатта, правило Хэбба.
- Теорема Новикова о сходимости.
- Недостатки метода стохастического градиента и способы их устранения. Проблема «паралича» сети. Ускорение сходимости, «выбивание» из локальных минимумов. Проблема переобучения, редукция весов (weight decay).
Логистическая регрессия
- Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
- Логистическая регрессия. Принцип максимума правдоподобия и логарифмическая функция потерь. Снова метод стохастического градиента, аналогия с правилом Хэбба.
Нейронные сети
- Проблема полноты. Задача исключающего или. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).
- Алгоритм обратного распространения ошибок. Способы формирования начального приближения. Недостатки алгоритма, способы их устранения.
- Подбор структуры сети: методы постепенного усложнения сети, оптимальное прореживание нейронных сетей (optimal brain damage).
Метод опорных векторов
- Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin).
- Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь.
- Задача квадратичного программирования и двойственная задача. Понятие опорных векторов.
- Рекомендации по выбору константы C.
- Функция ядра (kernel functions), спрямляющее пространство, теорема Мерсера.
- Способы конструктивного построения ядер. Примеры ядер.
- Сопоставление SVM с гауссовским ядром и RBF-сети.
- Обучение SVM методом активных ограничений. Псевдокод: алгоритм INCAS.
Обобщённый линейный классификатор
- Задача максимизации совместного правдоподобия данных и модели.
- Возможные типы априорных предположений о вероятностном распределении в пространстве параметров и их связь с регуляризацией.
- Некоторые разновидности регуляризаторов, применяемые на практике.
- Настройка порога решающего правила по критерию числа ошибок I и II рода. Кривая ошибок (ROC curve).
Непараметрическая регрессия
- Сглаживание. Локально взвешенный метод наименьших квадратов и оценка Надарая-Ватсона.
- Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна.
- Проблема выбросов и робастная непараметрическая регрессия. Псевдокод: алгоритм LOWESS.
Многомерная линейная регрессия
- Задача регрессии, многомерная линейная регрессия.
- Метод наименьших квадратов. Сингулярное разложение.
- Проблемы мультиколлинеарности и переобучения.
- Регуляризация. Гребневая регрессия. Лассо Тибширани.
- Линейные преобразования признакового пространства, задача сокращения размерности. Метод главных компонент и декоррелирующее преобразование Карунена-Лоэва.
Нелинейная параметрическая регрессия
- Метод Ньютона-Рафсона, метод Ньютона-Гаусса.
- Одномерные нелинейные преобразования признаков: метод обратной настройки (backfitting) Хасти-Тибширани.
- Обобщённая линейная модель (GLM).
- Логистическая регрессия как частный случай GLM, метод наименьших квадратов с итеративным пересчётом весов (IRLS).
Второй семестр
Кластеризация
- Постановка задачи кластеризации. Примеры прикладных задач.
- Графовые алгоритмы кластеризации. Алгоритм связных компонент.
- Псевдокод алгоритма: кратчайший незамкнутый путь.
- Псевдокод алгоритма: ФОРЭЛ.
- Функционалы качества кластеризации.
- Статистические алгоритмы: EM-алгоритм и k-means, псевдокод.
Таксономия и многомерное шкалирование
- Агломеративная кластеризация: псевдокод алгоритма, формула Ланса-Вильямса и её частные случаи.
- Алгоритм построения дендрограммы. Определение числа кластеров.
- Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
- Потоковые (субквадратичные) алгоритмы кластеризации.
- Многомерное шкалирование, примеры прикладных задач.
- Субквадратичный алгоритм, псевдокод. Размещение одной точки методом Ньютона-Рафсона.
- Визуализация: карта сходства, диаграмма Шепарда.
- Совмещение многомерного шкалирования и иерархической кластеризации.
Сети Кохонена
- Сеть Кохонена. Конкурентное обучение, стратегии WTA и WTM, обучающееся векторное квантование.
- Самоорганизующаяся карта Кохонена. Применение для визуального анализа данных.
- Сети встречного распространения, их применение для кусочно-постоянной и гладкой аппроксимации функций.
Алгоритмические композиции
- Основные понятия: базовый алгоритм (алгоритмический оператор), корректирующая операция.
- Линейные (выпуклые) алгоритмические композиции.
- Процесс последовательного обучения базовых алгоритмов.
- Простое голосование (комитет большинства). Эвристический алгоритм.
- Решающий список (комитет старшинства). Эвристический алгоритм.
Бустинг, бэггинг и аналоги
- Взвешенное голосование.
- Экспоненциальная аппроксимация пороговой функции потерь. Теорема о сходимости бустинга.
- Псевдокод: алгоритм AdaBoost.
- Варианты бустинга: GentleBoost, LogitBoost, BrownBoost, и другие.
- Стохастические методы: бэггинг и метод случайных подпространств.
Метод комитетов
- Общее понятие: комитет системы ограничений. Комитеты большинства, простое и взвешенное голосование (z,p-комитеты).
- Теоремы о существовании комитетного решения.
- Сопоставление комитета линейных неравенств с нейронной сетью.
- Максимальная совместная подсистема, минимальный комитет. Теоремы об NP-полноте задачи поиска минимального комитета.
- Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.
Нелинейные алгоритмические композиции
- Смесь экспертов, область компетентности алгоритма.
- Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
- Построение смесей экспертов с помощью EM-алгоритма.
- Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии.
Оценивание и выбор моделей
- Внутренние и внешние критерии.
- Скользящий контроль.
- Критерий непротиворечивости.
- Регуляризация.
- Критерии, основанные на оценках обобщающей способности: Вапника-Червоненкиса, критерий Акаике (AIC), байесовский информационный критерий (BIC).
- Статистические критерии: коэффициент детерминации, критерий Фишера, анализ остатков.
Методы отбора признаков
- Сложность задачи отбора признаков. Полный перебор.
- Метод добавления и удаления (шаговая регрессия).
- Поиск в глубину (метод ветвей и границ).
- Усечённый поиск в ширину (многорядный итерационный алгоритм МГУА).
- Генетический алгоритм, его сходство с МГУА.
- Случайный поиск с адаптацией (СПА).
Логические алгоритмы классификации
- Понятие логической закономерности. Эвристическое, статистическое, энтропийное определение информативности. Асимптотическая эквивалентность статистического и энтропийного определения. Принципиальные отличия эвристического и статистического определения.
- Разновидности закономерностей: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции).
- Бинаризация признаков, алгоритм выделения информативных зон.
- «Градиентный» алгоритм синтеза конъюнкций, частные случаи: жадный алгоритм, стохастический локальный поиск, стабилизация, редукция.
Решающие списки и деревья
- Решающий список. Жадный алгоритм синтеза списка.
- Решающее дерево. Псевдокод: жадный алгоритм ID3. Недостатки алгоритма и способы их устранения. Проблема переобучения.
- Редукция решающих деревьев: предредукция и постредукция.
- Преобразование решающего дерева в решающий список.
- Решающий лес и бустинг над решающими деревьями.
- Переключающиеся решающие деревья (alternating decision tree).
Взвешенное голосование закономерностей
- Принцип голосования. Проблема различности (диверсификации) закономерностей.
- Методы синтеза конъюнктивных закономерностей. Псевдокод: алгоритм КОРА, алгоритм ТЭМП.
- Алгоритм бустинга. Теорема сходимости.
- Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
Алгоритмы вычисления оценок
- Принцип частичной прецедентности. Структура АВО.
- Тупиковые тесты.
- Тупиковые представительные наборы.
- Проблема оптимизации АВО. АВО как композиция метрических закономерностей.
- Применение бустинга, ТЭМП и СПА для оптимизации АВО.
Поиск ассоциативных правил
- Пример прикладной задачи: анализ рыночных корзин.
- Понятие ассоциативного правила и его связь с понятием логической закономерности.
- Псевдокод: алгоритм APriori, его недостатки и пути усовершенствования.
