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

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

(Различия между версиями)

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

Текущая версия

Содержание

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

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

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

Аннотация

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

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

Категории

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

Морфизмы

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

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

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

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

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

Базы

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

Г-Полнота

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

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

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

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

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

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

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

Литература

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

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

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

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

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

Литература

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

Источник — «http://www.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»

Категории: Учебные курсы | МГУ

@@ Строка 8: / Строка 8: @@
 == Аннотация ==
-Основу данного курса составляют теория категорий и теория универсальных и локальных ограничений для задач классификации и распознавания. В курс входит построение теории категорий, изучение понятий категорий, подкатегорий, морфиз-фов (мономорфизм, эпиморфизм, биморфизм). Рассмотрена задача синтеза алгорит-мов, изучены понятия допустимых и корректных алгоритмов, понятие разрешимо-сти. Так же введены понятия полноты семейства алгоритмов и категорий, базы категорий. Изучен критерий регулярности задач классификации. Рассмотрены понятия функциональной сигнатуры и универсальных ограничений.
+Основу данного курса составляют теория категорий и теория универсальных и локальных ограничений для задач классификации и распознавания. В курс входит построение теории категорий, изучение понятий категорий, подкатегорий, морфизфов (мономорфизм, эпиморфизм, биморфизм). Рассмотрена задача синтеза алгоритмов, изучены понятия допустимых и корректных алгоритмов, понятие разрешимости. Так же введены понятия полноты семейства алгоритмов и категорий, базы категорий. Изучен критерий регулярности задач классификации. Рассмотрены понятия функциональной сигнатуры и универсальных ограничений.
 == Содержание курса ==
@@ Строка 15: / Строка 15: @@
 === Морфизмы ===
-Мономорфизмы. Теорема о композиции мономорфизмов. Мономор-физмы в категории отображений. Эпиморфизмы. Теорема о композиции эпиморфиз-мов. Эпиморфизмы в категории отображений. Изоморфизмы и биморфизмы. Пример неэквивалентности.
+Мономорфизмы. Теорема о композиции мономорфизмов. Мономорфизмы в категории отображений. Эпиморфизмы. Теорема о композиции эпиморфизмов. Эпиморфизмы в категории отображений. Изоморфизмы и биморфизмы. Пример неэквивалентности.
 === Элементы теории множеств ===
-Декартово произведение произвольной индексиро-ванной системы множеств. Аксиома выбора. Парадокс Рассела. Отношение эквива-лентности множеств и теорема Кантора-Бернштейна. Парадокс Кантора. Разложение произвольного отображения в суперпозицию отображений определенного вида. Бу-левы функции. Неявные булевы функции.
+Декартово произведение произвольной индексированной системы множеств. Аксиома выбора. Парадокс Рассела. Отношение эквивалентности множеств и теорема Кантора-Бернштейна. Парадокс Кантора. Разложение произвольного отображения в суперпозицию отображений определенного вида. Булевы функции. Неявные булевы функции.
 === Алгебраический подход ===
-Общий вид алгоритмов, синтезируемых методами ал-гебраического подхода. Лемма о достаточности условий допустимости. Регулярность задач распознавания. Обоснование необходимости условия полноты. Определения баз категорий. Лемма об эквивалентности определений баз для полных допустимых категорий.
+Общий вид алгоритмов, синтезируемых методами алгебраического подхода. Лемма о достаточности условий допустимости. Регулярность задач распознавания. Обоснование необходимости условия полноты. Определения баз категорий. Лемма об эквивалентности определений баз для полных допустимых категорий.
 === Базы ===
-Общая схема перехода от пространства матриц информации к пространст-ву информационных матриц. Лемма о необходимости для, вообще говоря, неодноэлементных баз. Лемма о достаточности для одноэлементных баз.
+Общая схема перехода от пространства матриц информации к пространству информационных матриц. Лемма о необходимости для, вообще говоря, неодноэлементных баз. Лемма о достаточности для одноэлементных баз.
 === Г-Полнота ===
-Общий критерий регулярности. Условие 1-Г-полноты. Условие сла-бой 1-Г-пол-ноты. Корректность. Условие Г-полноты. Условие слабой Г-полноты. Теорема о полноте алгебраических расширений.
+Общий критерий регулярности. Условие 1-Г-полноты. Условие слабой 1-Г-пол-ноты. Корректность. Условие Г-полноты. Условие слабой Г-полноты. Теорема о полноте алгебраических расширений.
 === Симметрические универсальные ограничения ===
-Определение. Лемма о доста-точности использования подгрупп. Лемма о допустимости симметрических катего-рий. Лемма о полноте симметрических категорий. Лемма о базах.
+Определение. Лемма о достаточности использования подгрупп. Лемма о допустимости симметрических категорий. Лемма о полноте симметрических категорий. Лемма о базах.
 === Функциональные сигнатуры и универсальные ограничения ===
@@ Строка 39: / Строка 39: @@
 == Литература ==
+# {{П:Рудаков 1992 Алгебраическая теория}}
 # Букур И., Деляну А. Ведение в теорию категорий и функторов.  М.: Мир. 1972.
 # Журавлев Ю.И. Избранные научные труды. М.: Магистр. 1999.
@@ Строка 45: / Строка 46: @@
 # Ленг С. Алгебра.  М.: Мир. 1968.
 # Мальцев А.И. Алгебраические системы.  М.: Наука. 1970.
-# Матросов В.Л. Корректные алгебры ограниченной емкости над множествами не-корректных алгоритмов // ДАН СССР. 1980. Т. 253.  № 1. С. 25-30.
+# Матросов В.Л. Корректные алгебры ограниченной емкости над множествами некорректных алгоритмов // ДАН СССР. 1980. Т. 253.  № 1. С. 25-30.
-# Рудаков К.В. Универсальные и локальные ограничения в проблеме коррекции эв-ристических алгоритмов классификации // Кибернетика. 1987.  № 2. С. 30-34.
+# Рудаков К.В. Универсальные и локальные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. 1987.  № 2. С. 30-34.
-# Рудаков К.В. Полнота и универсальные ограничения в проблеме коррекции эври-стических алгоритмов классификации // Кибернетика. 1987.  № 3. С. 106-109.
+# Рудаков К.В. Полнота и универсальные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. 1987.  № 3. С. 106-109.
-# Рудаков К.В. Симметрические и функциональные ограничения в проблеме кор-рекции эвристических алгоритмов классификации // Кибернетика. 1987. № 4. С. 35-40.
+# Рудаков К.В. Симметрические и функциональные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. 1987. № 4. С. 35-40.
 # Рудаков К.В. О применимости универсальных ограничений при исследовании алгоритмов классификации // Кибернетика. 1987. № 5. С. 32-38.
-# Рудаков К.В. Об алгебраической теории универсальных и локальных ограниче-ний для задач классификации // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 1. М.: Наука. 1989.  С. 176-200.
+# Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 1. М.: Наука. 1989.  С. 176-200.
 # Фейс С. Алгебра: кольца, модули и категории: В 2-х т. М.: Мир. 1979.
@@ Строка 61: / Строка 62: @@
 == Аннотация ==
-Данный курс составляет часть алгебраического подхода к проблеме синтеза алго-ритмов распознавания. В курс входит построение теории категорий, изучение свойств функциональных и симметрических  категорий, баз и полноты категорий, соотношений категорий (функциональные подкатегории симметрических категорий и симметрические подкатегории функциональных категорий). Так же в данном курсе изложены основные принципы построения R и Г моделей, классы решаемых задач, их регулярность, полнота и семейства подмоделей. Рассмотрены семейства корректирующих операций, изучены понятия полноты и суперполноты моделей.
+Данный курс составляет часть алгебраического подхода к проблеме синтеза алгоритмов распознавания. В курс входит построение теории категорий, изучение свойств функциональных и симметрических  категорий, баз и полноты категорий, соотношений категорий (функциональные подкатегории симметрических категорий и симметрические подкатегории функциональных категорий). Так же в данном курсе изложены основные принципы построения R и Г моделей, классы решаемых задач, их регулярность, полнота и семейства подмоделей. Рассмотрены семейства корректирующих операций, изучены понятия полноты и суперполноты моделей.
 == Содержание курса ==
@@ Строка 71: / Строка 72: @@
 === Одноэлементная база категории <tex>\Phi_0</tex> ===
-Лемма о существовании одноэлементной базы категории    в линейной оболочке базы.
+Лемма о существовании одноэлементной базы категории <tex>\Phi_0</tex> в линейной оболочке базы.
-     Полнота семейств. Теорема о полноте семейства   . Теорема о полноте семей-ства   . Теорема о 0-1 полноте модели   . Теорема о 0-1 полноте се-мейства   . Теорема о 0-1 полноте семейства   .
-     Категории    и   . Критерий разрешимости для категорий    и   . Теорема о суперполноте для категории   . Теорема о суперполноте для категории   .
+=== Полнота семейств ===
-     Замыкания модели  . Прямая теорема о полноте линейного замыка-ния модели  . Прямая теорема о полноте полиномиального замыкания мо-дели  .
+Теорема о полноте семейства <tex>A^{ql-1}</tex>. Теорема о полноте семейства <tex>LM^{](ql-1)/2[}</tex>. Теорема о 0-1 полноте модели    <tex>M(\gamma_m,\varepsilon)</tex>. Теорема о 0-1 полноте семейства <tex>A^{[\log_2ql]}</tex>. Теорема о 0-1 полноте семейства <tex>LM^1</tex>.
-     Глобальный и локальный базисы для задач распознавания. Общий итераци-онный процесс построения локальных базисов задач распознавания. Построение ло-кального базиса в комитете большинства. Построение локального базиса в комитете старшинства. Построение локального базиса в алгоритме бустинга  AdaBoost.
-     Монотонные корректирующие операции. Дефект алгоритмического оператора. Дефект набора алгоритмических операторов. Построение локального базиса для слу-чая монотонных корректирующих операций. Теорема о сходимости итерационного процесса построения проблемно-ориентированного базиса за конечное число шагов в случае монотонных корректирующих операций.
+=== Категории <tex>\Phi_0</tex> и <tex>\Sigma_0</tex> ===
-     Проблемно-ориентированные теории. Задачи синтеза алгоритмов выделения трендов. Формализация задач синтеза алгоритмов выделения трендов. Разрешимость и регулярность. Проблемы локальности.
+Критерий разрешимости для категорий <tex>\Phi_0</tex> и <tex>\Sigma_0</tex>. Теорема о суперполноте для категории <tex>\Phi_0</tex>. Теорема о суперполноте для категории <tex>\Sigma_0</tex>.
+=== Замыкания модели <tex>M(R_j,\gamma_m,x)</tex> ===
+Прямая теорема о полноте линейного замыкания модели <tex>M(R_j,\gamma_m,x)</tex>. Прямая теорема о полноте полиномиального замыкания модели <tex>M(R_j,\gamma_m,x)</tex>.
+=== Глобальный и локальный базисы для задач распознавания ===
+Общий итерационный процесс построения локальных базисов задач распознавания. Построение локального базиса в комитете большинства. Построение локального базиса в комитете старшинства. Построение локального базиса в алгоритме бустинга  AdaBoost.
+=== Монотонные корректирующие операции ===
+Дефект алгоритмического оператора. Дефект набора алгоритмических операторов. Построение локального базиса для случая монотонных корректирующих операций. Теорема о сходимости итерационного процесса построения проблемно-ориентированного базиса за конечное число шагов в случае монотонных корректирующих операций.
+=== Проблемно-ориентированные теории ===
+Задачи синтеза алгоритмов выделения трендов. Формализация задач синтеза алгоритмов выделения трендов. Разрешимость и регулярность. Проблемы локальности.
 == Литература ==
+# {{П:Рудаков 1992 Алгебраическая теория}}
 # Букур И., Деляну А. Введение в теорию категорий и функторов.  М.: Мир. 1972.
 # Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. Вып. 33. М.: Наука. 1978. С. 5-69.

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

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

Текущая версия

Содержание

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

Аннотация

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

Категории

Морфизмы

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

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

Базы

Г-Полнота

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

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

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

Литература

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

Аннотация

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

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

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

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

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

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

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

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

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

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

Литература

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты