Рабочая программа учебной дисциплины «Теория обучения машин»

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

им. А.А. Дородницына

РОССИЙСКОЙ АКАДЕМИИ НАУК

УТВЕРЖДАЮ
Директор ВЦ РАН, академик РАН
Евтушенко Ю.Г.
«___» ____________ ______ г.
РАБОЧАЯ ПРОГРАММА
УЧЕБНОЙ ДИСЦИПЛИНЫ

«Теория обучения машин»

для подготовки аспирантов по специальности

05.13.17 — Теоретические основы информатики

Москва 2012

АННОТАЦИЯ

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

ЦЕЛИ И ЗАДАЧИ КУРСА

Целью дисциплины является изучение основ теории обучения машин, современных методов восстановления зависимостей по эмпирическим данным, включая дискриминантный, кластерный и регрессионный анализ, овладение навыками практического решения задач интеллектуального анализа данных.

Задачами данного курса являются: освоение аспирантами базовых знаний (понятий, концепций, методов и моделей), приобретение теоретических знаний и практических умений и навыков, проведение собственных теоретических исследований и консультирование студентов в области машинного обучения и интеллектуального анализа данных.

МЕСТО ДИСЦИПЛИНЫ С СТРУКТУРЕ ОПППО

Курс «Теория обучения машин» относится к обязательным дисциплинам учебного плана подготовки аспирантов по научной специальности 05.13.17 «Теоретические основы информатики». Для успешного изучения курса аспиранту необходимо знать математический анализ, линейную алгебру, численные методы оптимизации, теорию вероятностей, математическую статистику и основы программирования.

Получаемые в результате изучения курса знания могут быть востребованы при подготовке к кандидатскому экзамену по научной специальности 05.13.17 «Теоретические основы информатики», в научно-исследовательской работе и при подготовке диссертации на соискание ученой степени кандидата наук.

ТРЕБОВАНИЯ К РЕЗУЛЬТАТАМ ОСВОЕНИЯ КУРСА

В результате освоения дисциплины «Теория обучения машин» обучающийся должен:

Знать:

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

Уметь:

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

Владеть:

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

содержание И Структура КУРСА

В курсе рассматриваются основные классы задач и методов машинного обучения и интеллектуального анализа данных: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами. Все методы излагаются по единой схеме: исходные идеи и эвристики, их формализация и математическая теория, описание алгоритма в виде слабо формализованного псевдокода, анализ достоинств, недостатков и границ применимости, пути устранения недостатков, сравнение с другими методами.
4.1.СОДЕРЖАНИЕ РАЗДЕЛОВ КУРСА

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

Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
Типы задач: классификация, регрессия, прогнозирование, кластеризация. Примеры прикладных задач.
Основные понятия: модель алгоритмов, метод обучения, функция потерь и функционал качества, принцип минимизации эмпирического риска, обобщающая способность, скользящий контроль.
Методика экспериментального исследования и сравнения алгоритмов на модельных и реальных данных. Полигон алгоритмов классификации.
Вероятностная постановка задачи обучения по прецедентам, принцип максимума правдоподобия и его связь с принципом минимизации эмпирического риска. Разновидности функций потерь и их вероятностная интерпретация.

Байесовский классификатор. Непараметрическое оценивание плотности

Принцип максимума апостериорной вероятности.
Функционал среднего риска. Ошибки I и II рода.
Теорема об оптимальности байесовского классификатора.
Оценивание плотности распределения: три основных подхода.
Наивный байесовский классификатор.
Ядерная оценка плотности Парзена-Розенблатта. Одномерный и многомерный случаи.
Метод парзеновского окна.
Выбор функции ядра. Выбор ширины окна, переменная ширина окна.
Робастное оценивание плотности.
Непараметрический наивный байесовский классификатор.

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

Нормальный дискриминантный анализ. Многомерное нормальное распределение, геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения.
Матричное дифференцирование. Вывод оценок параметров многомерного нормального распределения.
Квадратичный дискриминант. Вид разделяющей поверхности. Подстановочный алгоритм, его недостатки и способы их устранения.
Линейный дискриминант Фишера.
Проблемы мультиколлинеарности и переобучения. Регуляризация ковариационной матрицы.
Робастное оценивание. Цензурирование выборки (отсев объектов-выбросов).
Параметрический наивный байесовский классификатор.
Метод редукции размерности Шурыгина.

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

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

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

Метод ближайших соседей (kNN) и его обобщения.
Подбор числа k по критерию скользящего контроля.
Обобщённый метрический классификатор, понятие отступа.
Метод потенциальных функций, градиентный алгоритм.
Отбор эталонных объектов. Псевдокод: алгоритм СТОЛП.
Функция конкурентного сходства, алгоритм FRiS-СТОЛП.
Функционал полного скользящего контроля, формула быстрого вычисления для метода 1NN. Профиль компактности.

Линейные методы классификации

Линейный классификатор, непрерывные аппроксимации пороговой функции потерь. Связь с методом максимума правдоподобия.
Квадратичная функция потерь, метод наименьших квадратов, связь с линейным дискриминантом Фишера.
Метод стохастического градиента и частные случаи: адаптивный линейный элемент ADALINE, перcептрон Розенблатта, правило Хэбба.
Теорема Новикова о сходимости. Доказательство теоремы Новикова
Эвристики: инициализация весов, порядок предъявления объектов, выбор величины градиентного шага, «выбивание» из локальных минимумов.
Проблема переобучения, редукция весов (weight decay).
Байесовская регуляризация. Принцип максимума совместного правдоподобия данных и модели. Квадратичный (гауссовский) и лапласовский регуляризаторы.

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

Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
Логистическая регрессия. Принцип максимума правдоподобия и логарифмическая функция потерь. Снова метод стохастического градиента, сглаженное правило Хэбба.
Пример прикладной задачи: кредитный скоринг. Бинаризация признаков. Скоринговые карты и оценивание вероятности дефолта. Риск кредитного портфеля банка.
Настройка порога решающего правила по критерию числа ошибок I и II рода. Кривая ошибок (ROC curve). Алгоритм эффективного построения ROC-кривой. Градиентный метод максимизации площади под ROC-кривой.

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

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

Непараметрические методы восстановления регрессии

Сглаживание. Локально взвешенный метод наименьших квадратов и оценка Надарая-Ватсона.
Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна.
Проблема выбросов и робастная непараметрическая регрессия. Алгоритм LOWESS.

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

Задача регрессии, многомерная линейная регрессия.
Метод наименьших квадратов и его геометрический смысл.
Сингулярное разложение.
Проблемы мультиколлинеарности и переобучения.
Регуляризация. Гребневая регрессия. Лассо Тибширани, сравнение с гребневой регрессией.
Линейные преобразования признакового пространства, задача сокращения размерности. Метод главных компонент и декоррелирующее преобразование Карунена-Лоэва, его связь с сингулярным разложением.

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

Метод Ньютона-Рафсона, метод Ньютона-Гаусса.
Обобщённая линейная модель (GLM).
Логистическая регрессия как частный случай GLM, метод наименьших квадратов с итеративным пересчётом весов (IRLS).
Одномерные нелинейные преобразования признаков: метод настройки с возвращениями (backfitting) Хасти-Тибширани.
Неквадратичные функци потерь. Робастная регрессия, функция Мешалкина. Несимметричные функции потерь, пример прикладной задачи: прогнозирование потребительского спроса.

Многослойные нейронные сети

Биологический нейрон, модель МакКаллока-Питтса как линейный классификатор. Функции активации.
Проблема полноты. Задача исключающего или. Полнота двухслойных сетей в пространстве булевых функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).
Алгоритм обратного распространения ошибок.
Эвристики: формирование начального приближения, ускорение сходимости, диагональный метод Левенберга-Марквардта. Проблема «паралича» сети.
Метод послойной настройки сети.
Подбор структуры сети: методы постепенного усложнения сети, оптимальное прореживание нейронных сетей (optimal brain damage).

Сети Кохонена

Нейронная сеть Кохонена. Конкурентное обучение, стратегии WTA и WTM.
Самоорганизующаяся карта Кохонена. Применение для визуального анализа данных. Искусство интерпретации карт Кохонена.
Сети встречного распространения, их применение для кусочно-постоянной и гладкой аппроксимации функций.

Методы кластеризации

Постановка задачи кластеризации. Примеры прикладных задач. Типы кластерных структур.
Графовые алгоритмы кластеризации. Выделение связных компонент. Кратчайший незамкнутый путь.
Алгоритм ФОРЭЛ.
Функционалы качества кластеризации.
Статистические алгоритмы: EM-алгоритм и Алгоритм k средних (k-means).
Агломеративная кластеризация, Алгоритм Ланса-Вильямса и его частные случаи.
Алгоритм построения дендрограммы. Определение числа кластеров.
Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.

Критерии выбора моделей

Внутренние и внешние критерии.
Эмпирические и аналитические оценки функционала полного скользящего контроля.
Скользящий контроль, разновидности эмпирических оценок скользящего контроля.
Критерий непротиворечивости.
Регуляризация. Критерий Акаике (AIC). Байесовский информационный критерий (BIC).
Агрегированные и многоступенчатые критерии.

Теория обобщающей способности

Теория Вапника-Червоненкиса. Функционал равномерного отклоненеия частот ошибок. Функция роста, ёмкость семейства алгоритмов. Структурная минимизация риска.
Оценка «бритвы Оккама».
Радемахеровская сложность семейства алгоритмов.
Комбинаторная теория переобучения. Функционал вероятности переобучения. Граф расслоения-связности. Оценки расслоения-связности.

Методы отбора признаков

Сложность задачи отбора признаков. Полный перебор.
Метод добавления и удаления, шаговая регрессия.
Поиск в глубину, метод ветвей и границ.
Усечённый поиск в ширину, многорядный итерационный алгоритм МГУА.
Генетический алгоритм, его сходство с МГУА.
Случайный поиск и Случайный поиск с адаптацией (СПА).

Композиции классификаторов, бустинг

Основные понятия: базовый алгоритм (алгоритмический оператор), корректирующая операция.
Взвешенное голосование.
Алгоритм AdaBoost. Экспоненциальная аппроксимация пороговой функции потерь. Процесс последовательного обучения базовых алгоритмов. Теорема о сходимости бустинга.
Обобщение бустинга как процесса градиентного спуска. Теорема сходимости. Алгоритм AnyBoost.
Простое голосование (комитет большинства). Эвристический алгоритм ComBoost. Идентификация нетипичных объектов (выбросов). Обобщение на большое число классов.
Решающий список (комитет старшинства). Эвристический алгоритм. Стратегия выбора классов для базовых алгоритмов.
Стохастические методы: бэггинг и метод случайных подпространств.
Нелинейные алгоритмические композиции. Смесь экспертов, область компетентности алгоритма. Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический. Построение смесей экспертов с помощью EM-алгоритма.

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

Понятие логической закономерности. Эвристическое, статистическое, энтропийное определение информативности. Асимптотическая эквивалентность статистического и энтропийного определения. Сравнение областей эвристических и статистических закономерностей.
Разновидности закономерностей: конъюнкции пороговых предикатов (гиперпараллелепипеды), синдромные правила, шары, гиперплоскости.
«Градиентный» алгоритм синтеза конъюнкций, частные случаи: жадный алгоритм, стохастический локальный поиск, стабилизация, редукция.
Бинаризация признаков. Алгоритм разбиения области значений признака на информативные зоны.
Решающий список. Жадный алгоритм синтеза списка.
Решающее дерево. Псевдокод: жадный алгоритм ID3. Недостатки алгоритма и способы их устранения. Проблема переобучения.
Редукция решающих деревьев: предредукция и постредукция.
Преобразование решающего дерева в решающий список.
Чередующиеся решающие деревья (alternating decision tree).
Невнимательные решающие деревья (oblivious decision tree).
Решающий лес и бустинг над решающими деревьями.
Взвешенное голосование закономерностей. Методы синтеза конъюнктивных закономерностей. Алгоритмы КОРА и ТЭМП.
Эвристики, обеспечивающие различность и полезность закономерностей. Построение Парето-оптимального фронта закономерностей. Выравнивание распределения отступов.
Применение алгоритма бустинга AdaBoostк закономерностям. Критерий информативности в бустинге.
Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.

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

Принцип частичной прецедентности. Структура Алгоритмов вычисления оценок.
Тупиковые тесты.
Тупиковые представительные наборы.
Проблема оптимизации АВО. АВО как композиция метрических закономерностей.
Применение бустинга, ТЭМП и СПА для оптимизации АВО.

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

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

Задачи с частичным обучением

Постановка задачи Semisupervised Learning, примеры приложений.
Простые эвристические методы: self-training, co-training, co-learning.
Адаптация алгоритмов кластеризации для решения задач с частичным обучением. Кратчайшиё незамкнутый путь. Алгоритм Ланса-Уильямса. Алгоритм k-средних.
Трансдуктивный метод опорных векторов TSVM.
Алгоритм Expectation-Regularization на основе многоклассовой регуляризированной логистической регрессии.

Коллаборативная фильтрация

Задачи коллаборативной фильтрации, транзакционные данные и матрица субъекты—объекты.
Корреляционные методы user-based, item-based.
Латентные методы на основе би-кластеризации. Алгоритм Брегмана.
Латентные методы на основе матричных разложений. Метод главных компонент для разреженных данных. Метод стохастического градиента.
Неотрицательные матричные разложения. Вероятностный латентный семантический анализ PLSA. ЕМ-алгоритм для PLSA.
Эксперименты на данных конкурса «Интернет-математика» 2005.

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

Задачи тематического моделирования, коллекции текстовых документов и матрица документы—слова. Перплексия как мера качества тематической модели. Задача тематического поиска.
Униграммная модель документа. Метод максимума правдоподобия и метод максимума апостериорной вероятности. Применение метода множителей Лагранжа.
Вероятностный латентный семантический анализ PLSA. ЕМ-алгоритм. Инкрементное добавление новых документов (folding-in). Задача с частичным обучением.
Латентное размещение Дирихле. Сглаженная частотная оценка вероятности. Сэмплирование Гиббса. Оптимизация гиперпараметров.
Робастная тематическая модель с фоновой и шумовой компонентой. Эксперименты по сравнению робастных и регуляризованных моделей.

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

Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Среда для экспериментов. Метод сравнения с подкреплением. Метод преследования.
Адаптивные стратегии на основе скользящих средних.
Уравнения Беллмана. Оптимальные стратегии. Динамическое программирование. Метод итераций по ценностям и по стратегиям.
Методы временных разностей: TD, SARSA, Q-метод. Многошаговое TD-прогнозирование. Адаптивный полужадный метод VDBE.

4.2. СТРУКТУРА КУРСА

Общая трудоемкость курса составляет 4 зачетные единицы (144 часов).

Вид работы	Трудоемкость, часов
Общая трудоемкость	144
Аудиторная работа:	72
Лекции	72
Практические занятия	-
Лабораторные занятия	-
Самостоятельная работа:	72
Самостоятельное изучение разделов	-
Самоподготовка (проработка и изучение лекционного материала и материала учебников и учебных пособий, выполнение практических заданий)	72
Вид итогового контроля (зачет, экзамен)	Кандидатский экзамен

4.3. ТРУДОЕМКОСТЬ ОТДЕЛЬНЫХ РАЗДЕЛАХ КУРСА

№	Наименование раздела	Всего часов	Аудиторная работа (лекции)	Внеаудиторная самостоятельная работа
	Основные понятия и примеры прикладных задач		2	2
	Непараметрический байесовский классификатор		2	2
	Параметрический байесовский классификатор		2	4
	Разделение смеси распределений		2	2
	Метрические методы классификации		2	2
	Линейные методы классификации		2	2
	Логистическая регрессия		2	2
	Метод опорных векторов		4	4
	Непараметрическая регрессия		2	2
	Многомерная линейная регрессия		4	4
	Нелинейная параметрическая регрессия		2	2
	Многослойные нейронные сети		4	4
	Сети Кохонена		2	2
	Методы кластеризации		4	2
	Критерии выбора моделей		2	2
	Теория обобщающей способности		4	6
	Методы отбора признаков		4	2
	Композиции классификаторов, бустинг		6	6
	Логические методы классификации		6	6
	Алгоритмы вычисления оценок		2	2
	Поиск ассоциативных правил		2	2
	Задачи с частичным обучением		2	2
	Коллаборативная фильтрация		2	2
	Тематическое моделирование		4	4
	Обучение с подкреплением		2	2
	Всего:	144	72	72

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

Форма контроля знаний:

Кандидатский экзамен по специальности

Контрольно-измерительные материалы

На кандидатском экзамене аспирант должен продемонстрировать знания в объеме основной программы кандидатского экзамена по научной специальности 05.13.17 «Теоретические основы информатики» в которую могут входить вопросы, рассматриваемые в данном курсе.

Контрольные вопросы для программы
Байесовские методы классификации

Записать общую формулу байесовского классификатора (надо помнить формулу).
Какие вы знаете три подхода к восстановлению плотности распределения по выборке?
Что такое наивный байесовский классификатор?
Что такое оценка плотности Парзена-Розенблатта (надо помнить формулу). Выписать формулу алгоритма классификации в методе парзеновского окна.
На что влияет ширина окна, а на что вид ядра в методе парзеновского окна?
Многомерное нормальное распределение (надо помнить формулу). Вывести формулу квадратичного дискриминанта. При каком условии он становится линейным?
На каких предположениях основан линейный дискриминант Фишера?
Что такое «проблема мультиколлинеарности», в каких задачах и при использовании каких алгоритмов она возникает? Какие есть подходы к её решению?
Что такое «смесь распределений» (надо помнить формулу)?
Что такое ЕМ-алгоритм, какова его основная идея? Какая задача решается на Е-шаге, на М-шаге? Каков вероятностный смысл скрытых переменных?
Последовательное добавление компонент в ЕМ-алгоритме, основная идея алгоритма.
Что такое стохастический ЕМ-алгоритм, какова основная идея? В чём его преимущество (какой недостаток стандартного ЕМ-алгоритма он устраняет)?
Что такое сеть радиальных базисных функций?
Что такое «выбросы»? Как осуществляется фильтрация выбросов?

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

Что такое обобщённый алгоритм классификации (надо помнить формулу)? Какие вы знаете частные случаи?
Как определяется понятие отступа в метрических алгоритмах классификации?
Что такое окно переменной ширины, в каких случаях его стоит использовать?
Что такое метод потенциальных функций? Идея алгоритма настройки. Сравните с методом радиальных базисных функций.
Зачем нужен отбор опорных объектов в метрических алгоритмах классификации?
Основная идея алгоритма СТОЛП.
Что такое функция конкурентного сходства? Основная идея алгоритма FRiS-СТОЛП.
Приведите пример метрического алгоритма классификации, который одновременно является байесовским классификатором.
Приведите пример метрического алгоритма классификации, который одновременно является линейным классификатором.

Линейные методы классификации

Что такое модель МакКаллока-Питтса (надо помнить формулу)?
Метод стохастического градиента. Расписать градиентный шаг для квадратичной функции потерь и сигмоидной функции активации.
Недостатки метода SG и как они устраняются?
Что такое линейный адаптивный элемент ADALINE?
Что такое правило Хэбба?
Что такое «сокращение весов»?
Обоснование логистической регрессии (основная теорема), основные посылки (3) и следствия (2). Как выражается апостериорная вероятность классов (надо помнить формулу).
Как выражается функция потерь в логистической регрессии (надо помнить формулу).
Две мотивации и постановка задачи метода опорных векторов. Уметь вывести постановку задачи SVM (рекомендуется помнить формулу постановки задачи).
Какая функция потерь используется в SVM? В логистической регрессии? Какие ещё функции потерь Вы знаете?
Что такое ядро в SVM? Зачем вводятся ядра? Любая ли функция может быть ядром?
Какое ядро порождает полимиальные разделяющие поверхности?
Что такое ROC-кривая, как она определяется?
Как эффективно вычислить ROC-кривую?
В каких алгоритмах классификации можно узнать не только классовую принадлежность классифицируемого объекта, но и вероятность того, что данный объект принадлежит каждому из классов?
Каков вероятностный смысл регуляризации? Какие типы регуляризаторов Вы знаете?
Что такое принцип максимума совместного правдоподобия данных и модели (надо помнить формулу)?

Методы восстановления регрессионных зависимостей

Что такое ядерное сглаживание?
Что есть общего между ядром в непараметрической регрессии и ядром SVM?
На что влияет ширина окна, а на что вид ядра в непараметрической регрессии?
Что такое окна переменной ширины, и зачем они нужны?
Что такое «выбросы»? Как осуществляется фильтрация выбросов в непараметрической регрессии?
Постановка задачи многомерной линейной регрессии. Матричная запись.
Что такое сингулярное разложение? Как оно используется для решения задачи наименьших квадратов?
Что такое «проблема мультиколлинеарности» в задачах многомерной линейной регрессии? Какие есть три подхода к её устранению?
Сравнить гребневую регрессию и лассо. В каких задачах предпочтительнее использовать лассо?
Какую проблему решает метод главных компонент в многомерной линейной регрессии? Записать матричную постановку задачи для метода главных компонент.
Как свести задачу многомерной нелинейной регрессии к последовательности линейных задач?
Метод настройки с возвращениями (backfitting): постановка задачи и основная идея метода.
Какие методы построения логиcтической регрессии Вы знаете?
Приведите примеры неквадратичных функций потерь в регрессионных задачах. С какой целью они вводятся?

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

Приведите пример выборки, которую невозможно классифицировать без ошибок с помощью линейного алгоритма классификации. Какова минимальная длина выборки, обладающая данным свойством? Какие существуют способы модифицировать линейный алгоритм так, чтобы данная выборка стала линейно разделимой?
Почему любая булева функция представима в виде нейронной сети? Сколько в ней слоёв?
Метод обратного распространения ошибок. Основная идея. Основные недостатки и способы их устранения.
Как можно выбирать начальное приближение в градиентных методах настройки нейронных сетей?
Как можно ускорить сходимость в градиентных методах настройки нейронных сетей?
Что такое диагональный метод Левенберга-Марквардта?
Что такое «паралич» сети, и как его избежать?
Как выбирать число слоёв в градиентных методах настройки нейронных сетей?
Как выбирать число нейронов скрытого слоя в градиентных методах настройки нейронных сетей?
В чём заключается метод оптимального прореживания нейронной сети? Какие недостатки стандартного алгоритма обратного распространения ошибок позволяет устранить метод ODB?

Композиции алгоритмов классификации

Дать определение алгоритмической композиции (помнить формулу). Какие типы корректирующих операций вы знаете?
Какие типы голосования вы знаете? Какой из них наиболее общий? (помнить формулу)
Как обнаружить объекты-выбросы при построении композиции классификаторов для голосования по большинству?
Как обеспечивается различность базовых алгоритмов при голосовании по большинству?
Как обеспечивается различность базовых алгоритмов при голосовании по старшинству?
Какие возможны стратегии выбора классов базовых алгоритмов при голосовании по старшинству?
Какие две эвристики лежат в основе алгоритма AdaBoost?
Как обнаружить объекты-выбросы в алгоритме AdaBoost?
Достоинства и недостатки алгоритма AdaBoost.
Основная идея алгоритма AnyBoost.
Основная идея метода bagging.
Основная идея метода случайных подпространств.
Что такое смесь экспертов (помнить формулу)?
Приведите примеры выпуклых функций потерь. Почему свойство выпуклости помогает строить смеси экспертов?

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

В чём отличия внутренних и внешних критериев?
Разновидности внешних критериев.
Разновидности критерия скользящего контроля.
Что такое критерий непротиворечивости? В чём его недостатки?
Что такое многоступенчатый выбор модели по совокупности критериев?
Основная идея отбора признаков методом полного перебора. Действительно ли это полный перебор?
Основная идея отбора признаков методом добавлений и исключнений.
Что такое шаговая регрессия? Можно ли её использовать для классификации, в каком методе?
Основная идея отбора признаков методом поиска в глубину.
Основная идея отбора признаков методом поиска в ширину.
Что такое МГУА?
Основная идея отбора признаков с помощью генетического алгоритма.
Основная идея отбора признаков с помощью случайного поиска.
В чём отличия случайного поиска от случайного поиска с адаптацией?

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

Что такое логическая закономерность? Приведите примеры закономерностей в задаче распознавания спама.
Часто используемые типы логических закономерностей.
Дайте определение эпсилон-дельта-логической закономерности (помнить формулы).
Дайте определение статистической закономерности (помнить формулы).
Сравните области статистических и логических закономерностей в (p,n)-плоскости.
С какой целью делается бинаризация?
В чём заключается процедура бинаризации признака?
Как происходит перебор в жадном алгоритме синтеза информативных конъюнкций?
Какие критерии информативности используются в жадном алгоритме синтеза информативных конъюнкций и почему?
Как приспособить жадный алгоритм синтеза конъюнкций для синтеза информативных шаров?
Что такое стохастический локальный поиск?
В чём отличия редукции и стабилизации? В чём их достоинства и недостатки?
Что такое решающий список?
Какие критерии информативности используются при синтезе решающего списка и почему?
Достоинства и недостатки решающих списков.
Что такое решающее дерево?
Какие критерии информативности используются при синтезе решающего дерева и почему?
Достоинства и недостатки решающих деревьев.
Зачем делается редукция решающих деревьев?
Какие есть два основных типа редукции решающих деревьев?
Как преобразовать решающее дерево в решающий список, и зачем это делается?
Что такое ADT (alternating decision tree)? Как происходит построение ADT?
Основная идея алгоритма КОРА.
Почему возникает проблема предпочтения признаков с меньшими номерами в алгоритме КОРА? Как она решается?
Основная идея алгоритма ТЭМП.
Какие критерии информативности используются в алгоритме ТЭМП и почему?
Почему возникает проблема дублирования закономерностей в алгоритме ТЭМП? Как она решается?
Достоинства и недостатки алгоритма ТЭМП.
Как использовать алгоритм AdaBoost для построения взвешенного голосования закономерностей?
Какой критерий информативности используется в алгоритме AdaBoost?
Структура алгоритма вычисления оценок (АВО).
Что такое ассоциативное правило? Приведите пример ассоциативного правила в задаче анализа потребительских корзин.
Основная идея алгоритма поиска ассоциативных правил APriory.

Методы кластеризации и таксономии

Каковы основные цели кластеризации?
Основные типы кластерных структур. Приведите для каждой из этих структур пример алгоритма кластеризации, который для неё НЕ подходит.
В чём заключается алгоритм кратчайшего незамкнутого пути? Как его использовать для кластеризации? Как с его помощью определить число кластеров? Всегда ли это возможно?
Основная идея алгоритма ФорЭл.
Как вычисляются центры кластеров в алгоритме ФорЭл, если объекты — элементы метрического (не обязательно линейного векторного) пространства?
Какие существуют функционалы качества кластеризации и для чего они применяются?
Основные отличия алгоритма k-средних и EM-алгоритма. Кто из них лучше и почему?
Основная идея иерархического алгоритма Ланса-Вильямса.
Какие основные типы расстояний между кластерами применяются в алгоритме Ланса-Вильямса?
Какие расстояния между кластерами, применяемые в алгоритме Ланса-Вильямса, лучше и почему?
Что такое дендрограмма? Всегда ли её можно построить?
Какой функционал качества оптимизируется сетью Кохонена? (помнить формулу)
В чем отличия правил мягкой и жёсткой конкуренции? В чём преимущества мягкой конкуренции?
Как устроена самооганизующаяся карта Кохоненеа?
Как интерпретируются карты Кохонена?
Почему задачи с частичным обучением выделены в отдельный класс? Приведите примеры, когда методы классификации и кластеризации дают неадекватное решение задачи с частичным обучением.
Как приспособить графовые алгоритмы кластеризации для решения задачи с частичным обучением?
Как приспособить EM-алгоритм для решения задачи с частичным обучением?
Какие способы решения задачи с частичным обучением Вы знаете?

СПИСОК ЛИТЕРАТУРЫ

Основная литература

Воронцов К. В. Математические методы обучения по прецедентам. 2012. http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций,_К.В.Воронцов).
Мерков А. Б. Распознавание образов. Введение в методы статистического обучения. Едиториал УРСС. 2011. 256 стр.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Springer: Data Mining, Inference, and Prediction. — 2nd ed. — Springer-Verlag. 2009. — 746 p.
C. M. Bishop. Pattern Recognition and Machine Learning. — Springer, Series: Information Science and Statistics. 2006. — 738 p.

Дополнительная литература

Айвазян С. А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Классификация и снижение размерности. — М. Финансы и статистика. 1989.
Айвазян С. А., Енюков И.С., Мешалкин Л.Д. Исследование зависимостей. — М. Финансы и статистика. 1985.
Айвазян С. А., Мхитарян В. С. Прикладная статистика и основы эконометрики. — М.: Юнити, 1998.
Вагин В. Н., Головина Е. Ю., Загорянская А. А, Фомина М. В. Достоверный и правдоподобный вывод в интеллектуальных системах. — М.: Физматлит. 2004.
Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука. 1979.
Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики. http://www.ccas.ru/voron.
Головко. В. А. Нейронные сети: обучение, организация и применение. — М.: ИПРЖР. 2001.
Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999.
Загоруйко Н. Г., Ёлкина В. Н., Лбов Г. С. Алгоритмы обнаружения эмпирических закономерностей. — Новосибирск: Наука, 1985.
Ивахненко А. Г., Юрачковский Ю. П. Моделирование сложных систем по экспериментальным данным. — М.: Радио и связь, 1987.
Журавлёв Ю.И. Рязанов В.В. Сенько О.В. РАСПОЗНАВАНИЕ. Математические методы. Программная система. Применения. — Москва: Фазис, 2006.
Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. — 1978. — Т. 33. — С. 5–68.
Казанцев В. С. Задачи классификации и их программное обеспечение. — М. Наука. 1990.
Лоусон Ч, Хенсон Р. Численное решение задач метода наименьших квадратов. —М. Наука. 1986.
Магнус Я. Р., Катышев П. К., Пересецкий А. А. Эконометрика: начальный курс. М.: Дело. 2004.
Саттон Р.С., Барто Э.Г. Обучение с подкреплением. — БИНОМ, 2011.
Хардле В. Прикладная непараметрическая регрессия. — М.: Мир. 1993.
Шурыгин А. М. Прикладная стохастика: робастность, оценивание, прогноз. — М. Финансы и статистика. 2000.
Burges C. J. C. A tutorial on support vector machines for pattern recognition // Data Mining and Knowledge Discovery. — 1998. — Vol. 2, no. 2. — Pp. 121–167.
http://citeseer.ist.psu.edu/burges98tutorial.html.
Martin J. K. An exact probability metric for decision tree splitting and stopping // Machine Learning. — 1997. — Vol. 28, no. 2-3. — Pp. 257–291.
http://citeseer.ist.psu.edu/martin97exact.html.
Marchand M., Shawe-Taylor J. Learning with the set covering machine // Proc. 18th International Conf. on Machine Learning. — Morgan Kaufmann, San Francisco, CA, 2001. — Pp. 345–352. http://citeseer.ist.psu.edu/452556.html.
Schapire R. The boosting approach to machine learning: An overview // MSRI Workshop on Nonlinear Estimation and Classification, Berkeley, CA. — 2001. http://citeseer.ist.psu.edu/schapire02boosting.html.

Материально-техническое обеспечение дисциплины

Необходимое оборудование для лекций и практических занятий:

компьютер и мультимедийное оборудование (проектор, звуковая система)

Программу составил д.ф.-м.н., с.н.с. ВЦ РАН Воронцов К.В.
Программа принята на заседании Ученого Совета ВЦ РАН,

Протокол № ___________ от «_____»________________2012 г.