Математические методы классификации (курс лекций, К.В. Рудаков)

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

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

Содержание

МАТЕМАТИЧЕСКИЕ МЕТОДЫ КЛАССИФИКАЦИИ (часть 1)

  • Обязательный курс для студентов 4 курса каф. ММП, читается в 7 семестре
  • Лекции – 36 часов
  • Форма контроля - экзамен
  • Автор программы: д.ф.-м.н. Рудаков К.В.
  • Лектор: д.ф.-м.н. Рудаков К.В.

Аннотация

Основу данного курса составляют теория категорий и теория универсальных и локальных ограничений для задач классификации и распознавания. В курс входит построение теории категорий, изучение понятий категорий, подкатегорий, морфиз-фов (мономорфизм, эпиморфизм, биморфизм). Рассмотрена задача синтеза алгорит-мов, изучены понятия допустимых и корректных алгоритмов, понятие разрешимо-сти. Так же введены понятия полноты семейства алгоритмов и категорий, базы категорий. Изучен критерий регулярности задач классификации. Рассмотрены понятия функциональной сигнатуры и универсальных ограничений.

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

Категории

Определение понятия категории. Двойственность. Подкатегории. Традиционное определение полной подкатегории.

Морфизмы

Мономорфизмы. Теорема о композиции мономорфизмов. Мономор-физмы в категории отображений. Эпиморфизмы. Теорема о композиции эпиморфиз-мов. Эпиморфизмы в категории отображений. Изоморфизмы и биморфизмы. Пример неэквивалентности.

Элементы теории множеств

Декартово произведение произвольной индексиро-ванной системы множеств. Аксиома выбора. Парадокс Рассела. Отношение эквива-лентности множеств и теорема Кантора-Бернштейна. Парадокс Кантора. Разложение произвольного отображения в суперпозицию отображений определенного вида. Бу-левы функции. Неявные булевы функции.

Алгебраический подход

Общий вид алгоритмов, синтезируемых методами ал-гебраического подхода. Лемма о достаточности условий допустимости. Регулярность задач распознавания. Обоснование необходимости условия полноты. Определения баз категорий. Лемма об эквивалентности определений баз для полных допустимых категорий.

Базы

Общая схема перехода от пространства матриц информации к пространст-ву информационных матриц. Лемма о необходимости для, вообще говоря, неодноэлементных баз. Лемма о достаточности для одноэлементных баз.

Г-Полнота

Общий критерий регулярности. Условие 1-Г-полноты. Условие сла-бой 1-Г-пол-ноты. Корректность. Условие Г-полноты. Условие слабой Г-полноты. Теорема о полноте алгебраических расширений.

Симметрические универсальные ограничения

Определение. Лемма о доста-точности использования подгрупп. Лемма о допустимости симметрических катего-рий. Лемма о полноте симметрических категорий. Лемма о базах.

Функциональные сигнатуры и универсальные ограничения

Категории Ф0, Фi, Фj. Допустимые функциональные сигнатуры. Лемма об условиях существования единичного морфизма. Лемма об условиях существования единичного морфизма. Лемма об условиях замкнутости относительно суперпозиций. Лемма об условиях замкнутости относительно суперпозиций.

Функциональные категории

Лемма о полноте функциональных категорий. Лемма о допустимости функциональных категорий. Лемма о базах.

Литература

  1. Букур И., Деляну А. Ведение в теорию категорий и функторов. М.: Мир. 1972.
  2. Журавлев Ю.И. Избранные научные труды. М.: Магистр. 1999.
  3. Журавлев Ю.И., Исаев И.В. Построение алгоритмов распознавания, корректных для данной выборки // ЖВМ и МФ. 1979. Том 19. № 3. С. 728 738.
  4. Журавлев Ю.И., Рудаков К.В. Об алгебраической коррекции процедур обработки (преобразования) информации // Прикладная математика и информатика. М.: Наука. 1987. С. 240-251.
  5. Ленг С. Алгебра. М.: Мир. 1968.
  6. Мальцев А.И. Алгебраические системы. М.: Наука. 1970.
  7. Матросов В.Л. Корректные алгебры ограниченной емкости над множествами не-корректных алгоритмов // ДАН СССР. 1980. Т. 253. № 1. С. 25-30.
  8. Рудаков К.В. Универсальные и локальные ограничения в проблеме коррекции эв-ристических алгоритмов классификации // Кибернетика. 1987. № 2. С. 30-34.
  9. Рудаков К.В. Полнота и универсальные ограничения в проблеме коррекции эври-стических алгоритмов классификации // Кибернетика. 1987. № 3. С. 106-109.
  10. Рудаков К.В. Симметрические и функциональные ограничения в проблеме кор-рекции эвристических алгоритмов классификации // Кибернетика. 1987. № 4. С. 35-40.
  11. Рудаков К.В. О применимости универсальных ограничений при исследовании алгоритмов классификации // Кибернетика. 1987. № 5. С. 32-38.
  12. Рудаков К.В. Об алгебраической теории универсальных и локальных ограниче-ний для задач классификации // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 1. М.: Наука. 1989. С. 176-200.
  13. Фейс С. Алгебра: кольца, модули и категории: В 2-х т. М.: Мир. 1979.

МАТЕМАТИЧЕСКИЕ МЕТОДЫ КЛАССИФИКАЦИИ (часть 2)

  • Обязательный курс для студентов 4 курса каф. ММП, читается в 8 семестре
  • Лекции – 32 часа
  • Форма контроля - экзамен
  • Автор программы: д.ф.-м.н. Рудаков К.В.
  • Лектор: д.ф.-м.н. Рудаков К.В.

Аннотация

Данный курс составляет часть алгебраического подхода к проблеме синтеза алго-ритмов распознавания. В курс входит построение теории категорий, изучение свойств функциональных и симметрических категорий, баз и полноты категорий, соотношений категорий (функциональные подкатегории симметрических категорий и симметрические подкатегории функциональных категорий). Так же в данном курсе изложены основные принципы построения R и Г моделей, классы решаемых задач, их регулярность, полнота и семейства подмоделей. Рассмотрены семейства корректирующих операций, изучены понятия полноты и суперполноты моделей.

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

Модель M(R_j,\gamma_m)

Иерархия подмоделей модели M(R_j,\gamma_m). Теорема о полноте модели M(L,\gamma_m). Теорема о полноте модели M(R). Теорема о неполноте моделей M(L) и M(L_j).

Модель M(\gamma_m,p,\varepsilon,x)

Иерархия подмоделей модели M(\gamma_m,p,\varepsilon,x). Теорема о полноте модели M(\gamma_m,\varepsilon). Теорема о неполноте моделей M(\gamma_m,p,x) и M(p,\varepsilon,x).

Одноэлементная база категории \Phi_0

Лемма о существовании одноэлементной базы категории в линейной оболочке базы. 

    Полнота семейств. Теорема о полноте семейства   . Теорема о полноте семей-ства   . Теорема о 0-1 полноте модели   . Теорема о 0-1 полноте се-мейства   . Теорема о 0-1 полноте семейства   .
    Категории    и   . Критерий разрешимости для категорий    и   . Теорема о суперполноте для категории   . Теорема о суперполноте для категории   .
    Замыкания модели  . Прямая теорема о полноте линейного замыка-ния модели  . Прямая теорема о полноте полиномиального замыкания мо-дели  .
    Глобальный и локальный базисы для задач распознавания. Общий итераци-онный процесс построения локальных базисов задач распознавания. Построение ло-кального базиса в комитете большинства. Построение локального базиса в комитете старшинства. Построение локального базиса в алгоритме бустинга  AdaBoost.
    Монотонные корректирующие операции. Дефект алгоритмического оператора. Дефект набора алгоритмических операторов. Построение локального базиса для слу-чая монотонных корректирующих операций. Теорема о сходимости итерационного процесса построения проблемно-ориентированного базиса за конечное число шагов в случае монотонных корректирующих операций.
    Проблемно-ориентированные теории. Задачи синтеза алгоритмов выделения трендов. Формализация задач синтеза алгоритмов выделения трендов. Разрешимость и регулярность. Проблемы локальности.

Литература

  1. Букур И., Деляну А. Введение в теорию категорий и функторов. М.: Мир. 1972.
  2. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. Вып. 33. М.: Наука. 1978. С. 5-69.
  3. Ленг С. Алгебра. М.: Мир. 1968.
  4. Мальцев А.И. Алгебраические системы. М.: Наука.1970.
  5. Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 1. М.: Наука. 1989. С. 176-200.
  6. Фейс С. Алгебра: кольца, модули и категории: В 2-х т. М.: Мир. 1979.
  7. Рудаков К.В., Воронцов К.В. О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания // Доклады РАН. 1999. Т. 367. № 3. С. 314-317.
Источник — «http://recognition.su/wiki/index.php?title=%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%86%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%9A.%D0%92._%D0%A0%D1%83%D0%B4%D0%B0%D0%BA%D0%BE%D0%B2%29»
Личные инструменты