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

Содержание 1 Содержание курса 1.1 Тема 1. Основы статистического распознавания и машинного обучения 1.2 Тема 2. Задачи статистического распознавания и машинного обучения с целевыми признаками: классификация, восстановление регрессии 1.3 Тема 3. Задачи статистического распознавания и машинного обучения без целевых признаков: кластеризация, сокращение размерности 1.4 Тема 4. Основные информационные модели и методы их обучения по прецедентам 2 Оценивание 2.1 Примеры контрольных заданий 2.2 Примеры тем для работы над рефератами 2.3 Список вопросов для индивидуального собеседования 3 Литература

Успех и сама возможность проведения многих современных индустриальных и научных проектов в самых разных предметных областях всё чаще зависит от корректного анализа накопленной информации. Поэтому в наши дни практически каждый специалист должен иметь представление о возможностях и ограничениях, которые возникают при использовании существующего арсенала методов и средств интеллектуального анализа данных (Data Mining). Цель предлагаемого курса как раз и состоит в том, чтобы создать у слушателя представление об аналитической деятельности и соответствующей математической теории. Рассматриваются основные классы задач машинного обучения и методов их решения. Закрепляются навыки решения таких задач с использованием распространенных статистических пакетов.

Дисциплина входит в обязательную часть магистерской образовательной программы «Распределенные системы и компьютерные сети», изучается в 1-м семестре.

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

Содержание курса

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

• Цели и задачи анализа данных в разных видах деятельности. Связь анализа данных с фундаментальной и прикладной математикой.
• Трехуровневая классификация аналитических задач и технологий. Уровень сбора и хранения информации. Уровень запросов к данным, описания данных и проверки гипотез. Уровень генерации новых гипотез и выявления закономерностей.
• Понятие об инструментах прикладной статистики и фундаментальных задачах интеллектуального анализа данных.
• Основные модели в анализе данных. Понятие модели данных. Понятие информационной модели.
• Классификация инструментов статистики и фундаментальных задач интеллектуального анализа данных: по наличию целевых признаков, по типу признаков, по существованию распределения, по модели исходных данных.
• Основные этапы работы распознающей системы. Основные этапы создания и обучения распознающей системы.

Тема 2. Задачи статистического распознавания и машинного обучения с целевыми признаками: классификация, восстановление регрессии

• Фишеровская задача распознавания, нулевая гипотеза, функция правдоподобия, p-значение, ошибки первого рода и специфичность, уровень значимости.
• Неймановская задача распознавания, альтернативная гипотеза, отношение правдоподобия, ошибки второго рода и чувствительность, мощность критерия. Минимаксная задача распознавания, равный уровень ошибок.
• Совместное распределение, априорная вероятность, апостериорная вероятность. Функция потерь, средний риск, байесовская задача распознавания.
• Основные показатели качества в задачах классификации и восстановления регрессии, парадоксы их использования (проблема группирования, проблема редких событий), проблемы теории рационального выбора. Важнейшие функции потерь, соответствующие байесовские стратегии.
• Эмпирический риск, обобщающая способность стратегии. Явления недообучения и переобучения. Роль обучающей, валидационной и контрольной выборок при обучении по прецедентам. Кросс-валидация. Регуляризация, роль валидации при регуляризации. Валидация как критерий останова при итерационной оптимизации эмпирического риска.
• Восстановление плотности распределения. Параметрические и непараметрические методы. Ядровое сглаживание.
• Разложение среднего риска на части, теоретическое обоснование ансамблей классификаторов.

Тема 3. Задачи статистического распознавания и машинного обучения без целевых признаков: кластеризация, сокращение размерности

• Сокращение описания объекта как сжатие данных.
• Отбор и генерация признаков на основе операционных характеристик признаков (информативности). Линейный метод главных компонент. Многомерное шкалирование. Нелинейный метод t-SNE.
• Отбор и генерация признаков на основе операционных характеристик (качества) стратегий. Автокодировщики.
• Задача кластеризации, сопоставление с операцией группирования и задачей классификации. Различные постановки задачи кластеризации: разбиение, стохастическая, нечёткая, иерархическая, упорядочивание, однокластерная (последовательная).
• Задача разделения смеси распределений. EM-алгоритм.

Тема 4. Основные информационные модели и методы их обучения по прецедентам

• ROC-анализ описаний объектов, индекс Джини. ROC-анализ классификаторов, AUC и его свойства.
• Линейная модель. Метод наименьших квадратов, его связь с методом максимального правдоподобия. Регуляризация при настройке линейных моделей регрессии: ridge, lasso, elastic net. Линейная машина. Регуляризация при настройке линейных моделей классификации: SVM.
• Обобщенные линейные модели. Логистическая регрессия.
• Переход от линейных моделей к нелинейным при помощи ядровой функции.
• Метрические модели. Парзеновские окна. Метод k ближайших соседей.
• Нейронные сети. Перцептрон и теорема Новикова. Обратное распространение ошибки. Дискриминационные возможности сети в зависимости от её глубины.
• Решающие деревья.
• Комбинаторно логические методы. Тестовый алгоритм. Алгоритмы типа КОРА. Основы АВО.
• Алгоритмы, основанные на голосования по наборам закономерностей. Метод логических закономерностей. Метод статистически взвешенных синдромов.
• Ансамбли классификаторов. Основные этапы работы типичного базового классификатора, возможность коррекции на разных этапах. Выпуклые комбинации предикторов. Бэггинг и случайные подпространства. Бустинг. Случайный лес как композиция основных подходов к построению ансамбля.
• Анализ выживаемости как задача на цензурированных данных. Основы модели Кокса.

Оценивание

Оценка результатов обучения формируется из оценок решения 3 контрольных заданий, которые выполняются учащимися в процессе обучения на протяжении курса, реферата и итогового собеседования. Каждое из заданий и реферат оценивается максимум 15 баллами. На итоговом собеседовании можно набрать максимум 40 баллов. Таким образом, учащийся может суммарно набрать до 100 баллов. Итоговая сумма более или равно 80 соответствует оценке «отлично», от 60 до 79 – оценке «хорошо», от 40 до 59 – оценке «удовлетворительно», меньшая 40 – оценке «неудовлетворительно».

Примеры контрольных заданий

• Показатель X в классах К1 и K2 распределён нормально с параметрами: в К1 математическое ожидание 2, стандартное отклонение 4; в К2 математическое ожидание 3, стандартное отклонение 1. Выделить на числовой оси значений показателя X области отнесения байесовским классификатором к классам К1 и K2. Априорные вероятности классов К1 и K2 равны 0.6 и 0.4 соответственно.
• Каждый год варан подрастает на А% от своего веса в начале года. А – случайная величина с известными матожиданием 5 и дисперсией 1 (одна и та же для всех варанов во все годы). В начале жизни каждый варан имеет вес 1. Построить байесовский классификатор для определения возраста варана (полных лет) по его весу, минимизирующий частоту ошибки. Предположить, что распознаваться будут «достаточно» взрослые вараны.
• Рассматривается задача классификации на два класса: положительный и отрицательный. В ходе тестирования классификатора получены следующие результаты: полнота составляет 75%, общая точность составляет 80%. Какие значения может принимать точность?
• Магазин собрал сведения о покупках (транзакции в файле). Были построены ассоциативные правила. Какое правило, содержащее в условии 2 элемента, имеет наибольшую поддержку?
• Государственная избирательная комиссия зафиксировала результаты выборов по партиям и по регионам (таблица в файле). Требуется кластеризовать регионы по правилу k-средних для числа кластеров K от 1 до 12. Для каждого числа кластеров K найти максимальный радиус кластера. Построить график этой величины от K. На основании графика предположить, сколько групп регионов разумно выделить по итогам выборов.
• В алгоритме вычисления оценок написать формулу для числа голосов, если система опорных множеств состоит из всех непустых подмножеств, а функция близости определяется только порогами e1, …, en.
• Обоснуйте способ построения всех тупиковых тестов через приведение системы тестовых уравнений к неупрощаемой ДНФ.

Примеры тем для работы над рефератами

• Распознавание рукописных цифр, написанных разными людьми.
• Выделение на изображении сегментов кожи.
• Периоды покоя и извержения гейзеров.
• Анализ зависимости времени вылета рейса от пункта назначения.
• Анализ результатов ЕГЭ по регионам.
• Связь стоимости просмотра фильма с его характеристиками.
• Связь стоимости монитора с его характеристиками.

Список вопросов для индивидуального собеседования

1. Место и роль ИАД в современной структуре человеческой деятельности. Место ИАД в передаче научного знания. Уровни технологий анализа данных, их назначение, место ИАД в технологиях АД. Понятие о моделировании реального мира в науке. Физическая модель. Модель “решателя”. Информационная модель. Эвристическая модель. Основная особенность ИАД (обучение и эксплуатация эвристической информационной модели). Понятие о машинном обучении.
2. Основные модели данных (dataframe, multidimensional, similarity tensor, transactional). Их назначение научное, технологическое. Гомогенные и гетерогенные модели.
3. Фундаментальные задачи ИАД и основные инструменты статистики. Прикладная жизнь ИАД: декомпозиция содержательных задач предметной области. Научная жизнь ИАД: сведение к задачам фундаментальной математики. Обучение и эксплуатация в фундаментальных задачах. Основания таксономии (способы группирования) фундаментальных задач. Таксономия по наличию в исходных данных целевого признака. Таксономия по моделям данных: в разрезе исходных данных, в разрезе результатов.
4. Модель данных «признаковое описание объектов». Понятие о шкалах значений атрибутов. Представление реляционными технологиями. Схемы «звезда» и «снежинка».
5. Многомерная модель данных. Группирование объектов как переход к многомерной модели данных. Аналитические пространства. Измерения и категории. Показатели. Детализация. Функции агрегирования, типы показателей по агрегированию.
6. Транзакционная модель данных. Связанные с ней задачи.
7. Общая задача классификации. Понятие об обучении и использовании. Объект, модель, алгоритм-классификатор. Универсальные ограничения.
8. Локальные ограничения. Оптимизационный подход. Функционалы качества на размеченной выборке. Частотные функционалы качества. Случай бинарной классификации. Стоимостные функционалы качества. Несоответствие частотных и стоимостных функционалов качества человеческому поведению.
9. Подходы к многокритериальной оптимизации.
10. Понятие байесовского классификатора как оптимального алгоритма распознавания. Классификаторы, основанные на использовании формулы Байеса. Линейный дискриминант Фишера. Логистическая регрессия. Метод q-ближайших соседей.
11. Форматы представления информации. Текстовые файлы, их атрибуты, проблема определения атрибутов.
12. Текстовые форматы представления таблиц: separated values, delimited text. Экранирование символов.
13. Форматы представления транзакционных данных.
14. Диаграммы для наборов точек из конечномерных евклидовыхпространств.
15. Диаграммы для многомерной модели данных. Системы отчётности.
16. Задача восстановления регрессии: аппроксимационный подход, статистический подход. Простая регрессия. Множественная регрессия. Поиск коэффициентов по МНК. Недостатки МНК. Трёхкомпонентное разложение ошибки регрессионных моделей. Регуляризация по Тихонову. Гребневая регрессия, лассо, эластичные сети.
17. Модель данных «метрические тензоры», гомогенные и гетерогенные многомерные матрицы сходства. Группирование объектов как кластеризация по метрическим описаниям. Гомогенная кластеризация, бикластеризация, мультикластеризация. Основные типы результатов кластеризации (плоская, последовательная плоская, иерархическая, нечёткая, стохастическая, ранговая).
18. Плоская кластеризация. Задача и метод k-means.
19. Последовательная плоская кластеризация. Метод ФОРЕЛЬ.
20. Иерархическая кластеризация. Дивизивная. Агломеративная, функционалы связи (linkage).
21. ROC анализ.
22. Линейная модель. Линейная машина как метод обучения линейной модели.
23. Линейная модель. Метод опорных векторов.
24. Модель перцептрона Розенблатта. Метод его обучения. Теорема Новикова. Переход от сдвига к фиктивному признаку.
25. Многослойные перцептроны. Метод обратного распространения ошибки. Функции активации, удобные для распространения ошибки.
26. Многослойные перцептроны. Возможность разделения множеств для перцептронов разной глубины.
27. Решающие деревья.
28. Комбинаторно логические методы. Тестовый алгоритм.
29. Алгоритмы типа КОРА. Основы АВО. Быстрое вычисление оценок.
30. Алгоритмы, основанные на голосования по наборам закономерностей.
31. Метод логических закономерностей. Метод статистически взвешенных синдромов.
32. Bagging. Boosting. Решающие леса (random forest).
33. Коллективные методы. Ошибка и выпуклые комбинации предикторов. Основы алгебраической коррекции.
34. Анализ выживаемости как задача. Основы модели Кокса.

Литература

Основная учебно-методическая литература

1. Флах П. Машинное обучение. Наука и искусство построения алгоритмов, которые извлекают знания из данных. – М: ДМК Пресс. – 2015. – 400 с. ISBN 978-5-97060-273-7 (Flach P. Machine learning: the art and science of algorithms that make sense of data. – Cambridge University Press, 2012)
2. Bishop C. M. Pattern recognition and machine learning. – Springer, 2006.

Дополнительная учебно-методическая литература

1. Коэльо Л. П., Ричарт В. Построение систем машинного обучения на языке Python. – М: ДМК Пресс. – 2016. (Coelho L. P., Richert W. Building machine learning systems with Python. — 2nd ed. — Packt Publishing Ltd, 2015.)
2. Max Kuhn, Kjell Johnson. Applied Predictive Modeling. — Springer, 2013.
3. Hastie, T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed. — Springer-Verlag, 2009. — 746 p. — ISBN 978-0-387-84857-0.
4. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.