Логический анализ данных в распознавании (курс лекций, Е.В. Дюкова)

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

Перейти к: навигация, поиск

Содержание

Аннотация

Излагаются принципы, лежащие в основе логических методов анализа информации в задачах распознавания, классификации и прогнозирования. Рассматриваются подходы к конструированию процедур распознавания по прецедентам на основе использования аппарата логических функций и методов построения покрытий булевых и целочисленных матриц. Изучаются основные модели и рассматриваются вопросы, связанные с исследованием сложности их реализации и качества решения прикладных задач распознавания, а также вопросы применения логического подхода для задач кластерного анализа. Продолжительность курса 64 часа. Курс рассчитан на студентов 2-5 курсов.

Автор курса: доц. каф. ММП д.ф.-м.н. Дюкова Елена Всеволодна

Лектор с 2023 года: к.ф.-м.н. Прокофьев Пётр Александрович

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

Постановка задачи распознавания. Сущность дискретного подхода к задачам распознавания. Общие принципы построения дискретных (логических) процедур распознавания. Понятие элементарного классификатора. Основные модели дискретных (логических) процедур распознавания и используемые в них семейства элементарных классификаторов.

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

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

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

Сложность реализации дискретных (логических) процедур распознавания. Метрические свойства множества покрытий целочисленной матрицы.

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

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

Проблема построения корректных процедур распознавания. Алгебро-логический синтез корректных процедур распознавания на базе элементарных классификаторов. Задача классификации (таксономии, кластерного анализа). Процедуры классификации, основанные на построении покрытий классов.

Лекции

  • Лекция 1. Сущность дискретного подхода к задаче классификации (распознавания) по прецедентам (Презентация, PDF) (версия Прокофьева П.А.: Презентация, PDF)
  • Лекция 2. Принципы конструирования классических логических процедур распознавания и основные модели (Презентация, PDF)
  • Лекция 3. Общая схема конструирования дискретных (логических) процедур распознавания с использованием понятия элементарного классификатора. Модели алгоритмов голосования по антипредставительным наборам и по покрытиям класса (Презентация, PDF)
  • Лекция 4. Основные понятия теории дизъюнктивных нормальных форм (Презентация, PDF)
  • Лекция 5. Построение сокращенной ДНФ булевой функции, заданной КНФ. Построение сокращенной ДНФ для не всюду определенной булевой функции (Презентация, PDF)
  • Лекция 6. Использование аппарата логических функций для конструирования дискретных процедур распознавания в случае целочисленной информации (Презентация, PDF)
  • Лекция 7. Поиск элементарных классификаторов на основе построения покрытий булевой и целочисленной матриц. Связь задач построения покрытий булевой матрицы и преобразования нормальных форм булевой функции (Презентация, PDF)
  • Лекция 8. О сложности монотонной дуализации. Асимптотически оптимальные алгоритмы монотонной дуализации (Презентация, PDF)
  • Лекция 9. Об алгебро-логической коррекции элементарных классификаторов (Презентация, PDF) (версия Прокофьева П.А.: Презентация, PDF)
  • Лекция 10. Алгоритмы классификации на основе решающих деревьев (Презентация, PDF)
  • Лекция 11. Методы повышения эффективности дискретных процедур распознавания (Презентация, PDF)

Литература

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

  1. Дискретная математика и математические вопросы кибернетики / Под ред. С.Б. Яблонского, О.Б. Лупанова. М.: Наука. 1974.
  2. Дюкова Е.В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели. Учебное пособие для студентов математических факультетов педвузов. М: МПГУ. 2003. Пособие (PDF), Приложение к пособию (PDF).
  3. Дюкова Е.В. Алгоритмы распознавания типа Кора: сложность реализации и метрические свойства / Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука. 1989. Вып. 2. С. 99-125.
  4. Дюкова Е.В. О числе тупиковых покрытий целочисленной матицы // Ж. вычисл. матем. и матем. физ. 2005. Т. 27, № 1. С. 114-127.
  5. Дюкова Е.В., Журавлёв Ю.И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // Ж. вычисл. матем. и матем. физ. 2000. Т. 40, №8. С. 1264-1278.
  6. Дюкова Е.В., Журавлев Ю.М., Рудаков К.В. Об алгебро-логическом синтезе корректных процедур распознавания на базе элементарных алгоритмов // Ж. вычисл. матем. и матем. физ. 1996. Т. 36, № 8. С. 217-225.
  7. Дюкова Е.В., Инякин А.С. О процедурах классификации, основанных на построении покрытий классов // Ж. вычисл. матем. и матем. физ. 2003. Т. 43, № 12. С. 1910-1921.
  8. Дюкова Е.В., Песков Н.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // Ж. вычисл. матем. и ма-тем. физ. 2002. Том 42, № 5. С. 741-753.

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

  1. Баскакова Л.В., Журавлёв Ю.И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств // Ж. вычисл. матем. и матем. физ. 1981. Т. 21, №5. С. 1264-1275.
  2. Вайнцвайг М.Н. Алгоритм обучения распознаванию образов «Кора» / Ал-горитмы обучения распознаванию образов. М.: Сов. Радио. 1973. С. 82-91.
  3. Дмитриев А.И., Журавлев Ю.И., Кренделев Ф.П. О математических принципах классификации предметов или явлений / Дискретный анализ. Новоси-бирск: ИМ СО АН СССР. 1966. Вып. 7. С. 3-17.
  4. Донской В.И. Алгоритмы обучения, основанные на построении решающих деревьев // ЖВМиМФ. 1982. Т. 22, № 4. С. 963-974.
  5. Дюкова Е.В. Об асимптотически оптимальном алгоритме построения тупиковых тестов // ДАН СССР. 1977. 233, № 4. С. 527-530.
  6. Дюкова Е.В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания / Пробл. кибернетики. М.: Наука. 1982. Вып. 39. С. 165-199.
  7. Дюкова Е.В. О сложности реализации некоторых процедур распознавания // Ж. вычисл. матем. и матем. физ. 1987. Т. 27, №1. С.114-127.
  8. Дюкова Е.В. Асимптотические оценки некоторых характеристик множества представительных наборов и задача об устойчивости //Ж. вычисл. матем. и матем. физ. 1995. Т. 35, № 1. С. 122-134.
  9. Дюкова Е.В. О сложности реализации дискретных (логических) процедур распознавания // Ж. вычисл. матем. и матем. физ. 2004. Т. 44, № 3. С. 550-572.
  10. Журавлев Ю.И. Избранные научные труды. М.: Изд. Магистр. 1998. 416 с.
  11. Кузнецов В.Е. Об одном стохастическом алгоритме вычисления информативных характеристик таблиц по методу тестов / Дискретный анализ. Новоси-бирск: ИМ СО АН СССР. 1973. Вып. 23. С. 8-23.
  12. Рязанов В.В. О построении оптимальных алгоритмов распознавания и таксономии (классификации) при решении прикладных задач / Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука. 1988. Вып. 1. С. 229-279.
  13. Чегис И.А., Яблонский С.В. Логические способы контроля электрических схем // Тр. МИАН СССР. М.: 1958.
  14. Яблонский С.В. Введение в дискретную математику. М.: Наука. 1986.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9B%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%B2_%D1%80%D0%B0%D1%81%D0%BF%D0%BE%D0%B7%D0%BD%D0%B0%D0%B2%D0%B0%D0%BD%D0%B8%D0%B8_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%95.%D0%92._%D0%94%D1%8E%D0%BA%D0%BE%D0%B2%D0%B0%29»
Личные инструменты