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

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

Версия от 16:33, 11 января 2016; Kropotov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Страница курса находится в стадии формирования


Содержание

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

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

  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.