_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (1185318), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

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

В 1976-1978 годах Журавлевым был разработан подобный алгебраический формализм. Было предложено решать задачи распознавания не одним, а множеством алгоритмов в два этапа. Сначала для распознавания произвольных объектов независимо применяются алгоритмы . Далее результаты их применения специальным образом обрабатываются и формируется окончательное коллективное решение об отнесении объектов к одному из классов. С данным подходом связана надежда на взаимную компенсацию ошибок отдельных алгоритмов и получение в итоге более точного решения заданной задачи распознавания.

Данная идея склеивания алгоритмов и методы ее реализации лежат в основе алгебраической теории распознавания. Было показано, что все многообразие распознающих алгоритмов может быть описано в стандартном единообразном виде. Каждый алгоритм может быть представлен как произведение (последовательное выполнение) двух операторов - распознающего оператора и решающего правила. Распознающий оператор переводит совокупность описаний объектов распознаваемой выборки в числовую матрицу оценок характеризующих меры близости объектов к каждому из классов. Решающее правило переводит числовую матрицу оценок в информационную матрицу вычисленных значений предикатов . Показана определяющая роль распознающего оператора. Над множествами распознающих операторов определены алгебраические операции, позволяющие строить корректные алгоритмы (безошибочно распознающие элементы заданной контрольной выборки), получены необходимые и достаточные условия существования корректных алгоритмов, разработаны схемы и численные методы их непосредственного построения в виде полиномов от отдельных алгоритмов одной или нескольких моделей /25-28/.

1.4.2. Алгебраическая коррекция множеств распознающих алгоритмов.

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

Рассмотрим более общую постановку задачи распознавания с пересекающимися классами. Пусть имеется некоторое множество допустимых объектов , являющееся объединением классов . Через обозначим заданный на множестве допустимых объектов предикат . Пусть задан конечный набор допустимых объектов .

Определение 1. Матрица , где называется информационной матрицей набора по системе предикатов . Строка называется информационным вектором объекта .

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

Предположим, что у нас имеется множество алгоритмов , переводящих пару , , в матрицы , составленные из элементов , где значения интерпретируются обычным образом. Если , то - значение предиката на допустимом объекте , вычисленное алгоритмом . Если алгоритм не вычислил значение предиката , то принимается = .

Определение 2. Алгоритм называется корректным для задачи , если выполнено равенство .

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

Основной целью является:

А)- введение алгебраических операций над алгоритмами из , позволяющих строить алгебраические замыкания множеств ;

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

Теорема 1. Каждый алгоритм представим как последовательное выполнение алгоритмов и , где , -действительные числа , , , .

Из теоремы 1 следует, что множество порождает множества и . Элементы из будем в дальнейшем называть распознающими операторами, или просто операторами, элементы из - решающими правилами. Числовые матрицы называют матрицами оценок объектов за классы, или просто матрицами оценок.

Рис. 14. Каждый алгоритм распознавания представим в виде произведения распознающего оператора и решающего правила

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

В множестве операторов вводятся следующие операции сложения, умножения и умножения на скаляр.

Пусть , , , -скаляр. Определим операторы (произведение на скаляр), (сумма операторов), (произведение операторов) следующим образом:

(1.21)

(1.22)

(1.23)

Очевидно, что линейное замыкание множества относительно операций (1.21), (1.22) является векторным пространством.

Замыкание множества относительно операций (1.21) - (1.23) является ассоциативной линейной алгеброй с коммутативным умножением.

Нетрудно увидеть, что операторы из могут быть представлены в виде многочленов от операторов из . Если , то . Как обычно, степенью операторного многочлена называется максимальное число сомножителей в слагаемых .

Определение 4. Множества и алгоритмов таких, что ( ), называются линейным (алгебраическим) замыканием .

Зафиксируем информацию и выборку , . Будем рассматривать задачи , обладающие следующим свойством относительно множества распознающих операторов.

Определение 5. Если множество матриц (операторы пробегают множество ) содержит базис в пространстве числовых матриц размерности , то задача называется полной относительно .

Теорема 2. Если множество состоит лишь из задач, полных относительно , то линейное замыкание , где - произвольное фиксированное корректное решающее правило, является корректным относительно .

Следствие 1. Пусть - совокупность некорректных алгоритмов, - соответствующее множество операторов, -фиксированное корректное решающее правило. Тогда является корректным относительно , если состоит из задач, полных относительно .

Следствие 2. Пусть выполнены все условия следствия 1 и, кроме того, есть замыкание относительно операций (1.21) - (1.23). Тогда является корректным относительно , если состоит из задач, полных относительно .

Рис.15. Алгебраическая коррекция эвристических алгоритмов

1.4.3. Логическая коррекция множеств распознающих алгоритмов.

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

Рассмотрим для простоты случай отсутствия отказов при классификации. Пусть задан коллектив из n распознающих алгоритмов , , Пусть матрица является информационной матрицей набора по системе предикатов . Множества матриц определяют l не всюду определенных булевых функций . При этом , и функция не определена на остальных наборах. Основная задача состоит в таком доопределении функции на весь дискретный единичный куб , при котором будут максимально выполнены дополнительные «содержательно обоснованные» условия, обеспечивающие некоторый однозначный и оптимальный выбор такой функции. Данные функции будем называть логическими корректорами. Если подобные функции построены, то процесс распознавания произвольной новой выборки объектов алгоритмами с последующей логической коррекцией может быть представлен схематически на рис. 16.

Рис.16. Логическая коррекция алгоритмов распознавания

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

Характеристики

Список файлов книги