Алгебраические методы обработки данных (курс лекций, Журавлёв Ю.И.)

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

Страница курса находится в стадии формирования

Содержание 1 Система выставления оценок по курсу 2 Экзамен 3 Программа курса 3.1 Повторение некоторых разделов дискретной математики 3.2 Алгоритмы, основанные на вычислении оценок (АВО) 3.3 Алгебраический подход к решению задач классификации 3.4 Дискретные (логические) процедуры распознавания 3.5 Логико-статистические модели в распознавании 4 Литература

Преподаватели: А.Г. Дьяконов, Е.В. Дюкова, А.И. Майсурадзе, О.В. Сенько.

Оценки по курсу находятся здесь.

Система выставления оценок по курсу

1. В рамках курса предполагается 5 контрольных работ и экзамен. Каждая контрольная работа по курсу оценивается из 5-ти баллов. Возможные оценки за экзамен - 0, 3, 4, 5.
2. При отсутствии положительного балла за хотя бы одну из контрольных работ максимальная возможная оценка за курс - «удовлетворительно».
3. Необходимым условием получения положительной оценки за курс является написание не менее трёх контрольных работ на положительный балл и сдача экзамена на положительную оценку.
4. Итоговая оценка вычисляется по формуле , где Exam — оценка за устный экзамен (0, 3, 4, 5), Tests — баллы, набранные за контрольные работы (см. таблицу выше), Mark — итоговая оценка по 5-балльной шкале. Нецелые значения округляются в сторону ближайшего целого, превосходящего дробное значение.

Экзамен

Экзамен состоится 18 января (понедельник) в ауд. 579, начало в 9-00.

Список вопросов

Программа курса

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

1. Булевы функции, их запись, изображения на булевом кубе
2. Дизъюнктивные нормальные формы (ДНФ): сокращённые, тупиковые, кратчайшие
3. Алгоритмы построения ДНФ: метод Нельсона, метод Блейка, критерий поглощения

Алгоритмы, основанные на вычислении оценок (АВО)

1. Тестовые алгоритмы
2. Алгоритмы с представительными наборами
3. Алгоритмы вычисления оценок (АВО), обобщения АВО, эффективные формулы для оценок

Алгебраический подход к решению задач классификации

1. Задача классификации на l классов
2. Алгебра над алгоритмами, линейное и алгебраическое замыкание
3. База в линейном замыкании АВО

Дискретные (логические) процедуры распознавания

1. Постановка задачи распознавания по прецедентам. Сущность дискретного (логического) подхода к задачам распознавания. Общие принципы построения дискретных (логических) процедур распознавания в случае целочисленных данных. Понятие корректного элементарного классификатора. Модели дискретных (логических) алгоритмов распознавания, основанные на построении корректных элементарных классификаторов.
2. Построение элементарных классификаторов в тестовых алгоритмах распознавания и алгоритмах голосования по представительным наборам на основе поиска покрытий булевых матриц. Построение элементарных классификаторов в алгоритмах голосования по представительным наборам на основе преобразования нормальных форм логических функций (на примере бинарных признаков). Задача дуализации. Основные подходы к оценке эффективности алгоритмов дуализации.
3. Алгебро-логический подход к построению корректных процедур распознавания на базе произвольных (не обязательно корректных) элементарных классификаторов. Понятие (монотонного) корректного набора элементарных классификаторов. Общая схема работы логического корректора. Подходы к снижению вычислительной сложности на этапе обучения логического корректора. Практические модели логических корректоров.
4. Методы повышения эффективности дискретных (логических) процедур распознавания. Оценка информативности признаков, значений признаков, выделение шумящих признаков и обучающих объектов, не являющихся типичными для своего класса.

Логико-статистические модели в распознавании

1. Трёхкомпонентное разложение ошибки. Bias-Variance дилемма. Разложение ошибки для выпуклых комбинаций предикторов. Несократимые комбинации. Разложение ошибки для компоненты сдвига и вариационной компоненты обобщённой ошибки.
2. Методы верификации закономерностей, основанные на перестановочных тестах. Метод оптимальных достоверных разбиений.
3. Метод континуального голосования в модели АВО.
4. Метод статистически взвешенных синдромов.

Литература

1. Дискретная математика и математические вопросы кибернетики / Под ред. С.В. Яблонского и О.Б. Лупанова. – М.: Наука, 1974. – 312с (глава про ДНФ)
2. Яблонский С.В. Введение в дискретную математику. 4-е издание, стереотипное — М.: Высшая школа, 2003. — 484 с (в конце книги - в приложение про ДНФ).
3. Дьяконов A.Г. Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab (практикум на ЭВМ кафедры математических методов прогнозирования). — МАКСПресс, 2010. (9 глава).
4. Дьяконов А.Г. Алгебраические замыкания модели АВО, операторы разметки и теория систем эквивалентностей. Москва, 2009. (параграфы 1.1-1.2)
5. Дюкова Е.В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели // Учебное пособие для студентов Математических факультетов педвузов. М: МПГУ 2003 г. 30 с.
6. Сенько О.В., Докукин А.А. Оптимальные выпуклые корректирующие процедуры в задачах высокой размерности. ЖВМиМФ, Т. 51, №9 с.1751-1760, 2011
7. Senko O.V., Dokukin A.A. Optimal forecasting based on convex correcting procedures. in New trends in classification and data mining, (2010), Sofia,Bulgaria:ITHEA
8. Senko O.V., Kuznetsova A.V. The Optimal Valid Partitioning Procedures // “InterStat”, Statistics in Inter- net. 2006.
9. Сенько О.В. Алгоритм голосования по множеству операторов вычисления оценок континуальной мощности. В сб. Вопросы кибернетики. Москва, 1989.
10. Senko O., Kuznetsova A. A recognition method based on collective decision making using systems of regularities of various types // Pattern Recognition and Image Analysis, MAIK Nauka/Interperiodica. Vol. 20, No. 2, 2010, pp. 152-162.