Алгебраические замыкания обобщённой модели алгоритмов распознавания, основанных на вычислении оценок

• Автор: Дьяконов, Александр Геннадьевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 292 с. : ил.

- 2 -ОГЛАВЛЕНИЕ

Введение

§0. Обозначения

Глава 1. Описание алгебраических замыканий обобщённой модели

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

§1.1. Модель алгоритмов вычисления оценок (АВО)

§ 1.2. Алгебра над алгоритмами

§ 1.3. Системы эквивалентностей

§1.4. Операции внешнего и покоординатного произведений

§ 1.5. Матрицы оценок операторов из алгебраических замыканий

Глава 2. Критерии корректности и разрешимости

§2.1. Характеристические матрицы систем эквивалентностей
§2.2. Метрики систем эквивалентностей
§2.3. Обобщённые характеристические матрицы и метрики систем
эквивалентностей
§2.4. Описание корректных полиномов
§2.5. Характеристические матрицы в задачах распознавания с двумя
классами
Глава 3. Оценки степени корректного алгебраического замыкания
§3.1. Модель АВО с общей функцией близости
§3.2. Неулучшаемая оценка степени корректного алгебраического
замыкания
§3.3. Задачи распознавания с непересекающимися классами
§3.4. Модель АВО с системой одноэлементных опорных множеств
§3.5. Исследование некоторых подмоделей
Глава 4. Алгебра над алгоритмами, пополненная операциями
нормировки и деления
§4.1. Основные определения. Замыкания относительно операций
§4.2. Нормировка по сумме

§4.3. Нормировка по максимуму
§4.4. Нормировка по отрезку
§4.5. Сравнение различных видов нормировок. Деление матриц
(распознающих операторов)
Глава 5. Корректность относительно множества решающих правил 180 §5.1. Решающие правила
§5.2. Общие критерии получения классификации
§5.3. Критерии корректности относительно семейств построчно и
постолбцово монотонных решающих правил
§5.4. Корректность в задаче распознавания с непересекающимися
классами
§5.5. Сведение задач распознавания
Глава 6. Критерии вырожденности матрицы попарных -расстояний
и их обобщения
§6.1. к -сингулярные системы точек
§6.2. Описание А:-сингулярных систем точек
§6.3. Приложение результатов о А;-сингулярных системах
к распознаванию
Заключение
Список литературы
Приложения
Приложение I. Список обозначений
Приложение II. Выбор системы опорных множеств для эффективной
реализации алгоритмов вычисления оценок
Приложение III. Прикладные задачи, решённые в 2005 - 2008 годах

ВВЕДЕНИЕ
В начале 1970х годов Ю.И. Журавлёвым была описана модель алгоритмов вычисления оценок (АВО) для решения- задач распознавания1 [ЖН71], [ЖКТ74]. Каждый алгоритм модели представлялся в виде
суперпозиции распознающего оператора и решающего правила. Распознающий оператор строил матрицу оценок принадлежности контрольных объектов (которые алгоритм должен классифицировать) классам, анализируя схожести подописаний контрольных и эталонных объектов (классификация которых уже известна). Решающее правило на основе этой матрицы оценок классифицировало контрольные объекты. В АВО'были отражены многие эвристические методы, которые применялись тогда при решении прикладных задач, и модель стала своеобразным универсальным языком описания алгоритмов распознавания [Ж98]. Например, представителями модели были тестовые алгоритмы [ДЖК66], [Яд71 ] и алгоритмы «Кора» [Бн67], [Вн73], успешно зарекомендовавшие себя на практике.
В конце 1970х годов Ю.И. Журавлёвым был предложен алгебраический, подход к решению задач распознавания: корректный- алгоритм (который не делает ошибок на контрольный выборке) было предложено искать в виде алгебраического выражения над некорректными (эвристическими) алгоритмами [Ж77а], [Ж776], [Ж77в]. Над распознающими операторами были введены операции сложения, умножения на константу и умножения как операции над их матрицами оценок (умножение проводилось поэлементно). При фиксированном решающем правиле эти операции индуцировали операции над алгоритмами распознавания. Множество алгоритмов, состоящее из всех полиномов степени не выше к над алгоритмами некоторой* модели, было-названо алгебраическим замыканием к-й степени-этой модели. Множество всех полиномов - алгебраическим замыканием (если ясно из контекста, то
1 Задачу распознавания образов по традиции российской научной литературы последних лет называем задачей распознавания (изначально термин «образ» был не совсем корректен РКГ89]).

ВІЬ - множество операторов {ВПАаА?}Пі а Ж, Д* - множество операторов {5П( аЬ?}П/ а6~.
Нами получено равенство Ь(2?*) = ЦД,), из которого, в силу свойства (1.2.1), следует равенство
иЧ5‘) = (Доопределение. Оператор Пп,а~, который получает ненулевую матрицу оценок Г[£>п ?Л ~]:
называется оператором разметки.
Замечание. Для каждой подмодели модели АВО термин «оператор разметки» будет уточняться. Неформально: это «самый простой оператор в этой подмодели», у -й элемент его матрицы оценок будет иметь вид
важно, чтобы для множества операторов разметки был верен аналог теоремы 1.2.1. Требование ненулевой матрицы оценок накладывается только для удобства формулировок результатов. Заметим, что множество
(допустимые) значения, совпадает с множеством, в котором они пробегают лишь те значения, которые обеспечивают ненулевые матрицы оценок операторов. Поэтому в формулах будем опускать множества значений, которые пробегают параметры.
даъ,а,е] = 1[а) = а] /[рп(б"д.) - е],
(і,/) є 01, где
ЦЩэ,1,а,е}пг,а,е)> в котором параметры С2,(,а,е пробегают всевозможные