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

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

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

Содержание

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

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

Аннотация

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

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

Категории

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

Морфизмы

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

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

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

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

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

Базы

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

Г-Полнота

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

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

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

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

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

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

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

Литература

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

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

Полнота семейств

Теорема о полноте семейства A^{ql-1}. Теорема о полноте семейства LM^{](ql-1)/2[}. Теорема о 0-1 полноте модели M(\gamma_m,\varepsilon). Теорема о 0-1 полноте семейства A^{[\log_2ql]}. Теорема о 0-1 полноте семейства LM^1.

Категории \Phi_0 и \Sigma_0

Критерий разрешимости для категорий \Phi_0 и \Sigma_0. Теорема о суперполноте для категории \Phi_0. Теорема о суперполноте для категории \Sigma_0.

Замыкания модели M(R_j,\gamma_m,x)

Прямая теорема о полноте линейного замыкания модели M(R_j,\gamma_m,x). Прямая теорема о полноте полиномиального замыкания модели M(R_j,\gamma_m,x).

Глобальный и локальный базисы для задач распознавания

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

Монотонные корректирующие операции

Дефект алгоритмического оператора. Дефект набора алгоритмических операторов. Построение локального базиса для случая монотонных корректирующих операций. Теорема о сходимости итерационного процесса построения проблемно-ориентированного базиса за конечное число шагов в случае монотонных корректирующих операций.

Проблемно-ориентированные теории

Задачи синтеза алгоритмов выделения трендов. Формализация задач синтеза алгоритмов выделения трендов. Разрешимость и регулярность. Проблемы локальности.

Литература

  1. Рудаков, К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр АН СССР, 1992. — 274 с.  (подробнее)
  2. Букур И., Деляну А. Введение в теорию категорий и функторов. М.: Мир. 1972.
  3. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. Вып. 33. М.: Наука. 1978. С. 5-69.
  4. Ленг С. Алгебра. М.: Мир. 1968.
  5. Мальцев А.И. Алгебраические системы. М.: Наука.1970.
  6. Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 1. М.: Наука. 1989. С. 176-200.
  7. Фейс С. Алгебра: кольца, модули и категории: В 2-х т. М.: Мир. 1979.
  8. Рудаков К.В., Воронцов К.В. О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания // Доклады РАН. 1999. Т. 367. № 3. С. 314-317.
Источник — «http://machinelearning.ru/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»