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

Второй этап связывают с разработкой на базе отдельных эвристических методовраспознавания параметрических моделей и решением задач оптимизации моделей поиска наилучших алгоритмов в пределах фиксированных моделей /25/. Данный этапсвязан с естественным желанием исследователя в максимально возможном обобщении47метода распознавания, реализацией идеи параметрической подстройки метода под новыеданные. К тому же обилие алгоритмов распознавания создало проблему их сравнения иавтоматического выбора наилучшего из заданного множества.

Приведенные в разделах1.2, 1.3 основные подходы и представляют современные и достаточно хорошо изученныемодели.В дальнейшем, опыт решения практических задач выявил и слабые места приработе с фиксированной моделью. Выяснилось, что нахождение и использованиенаилучшего по точности алгоритма данной модели для заданной контрольной задачидалеко не всегда является лучшим способом использования имеющегося исходногомножестваалгоритмов.Стандартнойявляетсяситуация,когданайденнаборэвристических алгоритмов A1 , A2 , . .

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

Сначала для распознавания произвольных объектов независимоприменяются алгоритмы A1 , A2 , . . . , Ak . Далее результаты их применения специальнымобразом обрабатываются и формируется окончательное коллективное решение оботнесении объектов к одному из классов. С данным подходом связана надежда навзаимную компенсацию ошибок отдельных алгоритмов и получение в итоге болееточного решения заданной задачи распознавания.Данная идея склеивания алгоритмов и методы ее реализации лежат в основеалгебраическойтеориираспознавания.Былопоказано,чтовсемногообразиераспознающих алгоритмов может быть описано в стандартном единообразном виде.Каждый алгоритм может быть представлен как произведение (последовательноевыполнение) двух операторов - распознающего оператора и решающего правила.Распознающий оператор переводит совокупность q описаний объектов распознаваемойвыборки в числовую матрицу оценок gij , i  1,2, .

. . , q, j  1,2, . . . , l , характеризующих48меры близости объектов к каждому из классов. Решающее правило переводит числовуюматрицу оценок в информационную матрицу вычисленных значений предикатовP j ( S )  " S  K j ".множествамиПоказана определяющая рольраспознающихоператоровраспознающего оператора. Надопределеныалгебраическиеоперации,позволяющие строить корректные алгоритмы (безошибочно распознающие элементызаданной контрольной выборки), получены необходимые и достаточные условиясуществования корректных алгоритмов, разработаны схемы и численные методы ихнепосредственного построения в виде полиномов от отдельных алгоритмов одной илинескольких моделей /25-28/.1.4.2. Алгебраическая коррекция множеств распознающих алгоритмов.Предположим, что у нас имеется семейство { A} эвристических алгоритмовраспознавания, которые вообще говоря не являются корректными для некоторойконкретнойзадачи.Подкорректностьюраспознающегоалгоритмапонимаетсяправильность распознавания им объектов контрольной выборки.

Возникает вопрос овозможности построения корректного алгоритма с использованием уже имеющегосямножества алгоритмов { A}.Рассмотрим более общую постановку задачи распознавания с пересекающимисяклассами. Пусть имеется некоторое множество допустимых объектов {S} , являющеесяобъединением классов K1 ,..., Kl . Через Pi ( S ) обозначим заданный на множестведопустимых объектов {S} предикат " S  Ki " . Пусть задан конечный набор допустимыхобъектов S1 ,..., Sq .Определение 1. Матрица || ij ||q  l , где ij  Pj (Si ) называется информационнойматрицей набора S1 ,..., Sq по системе предикатов P1 ,..., Pl .

Строка ( ,..., ) называетсяi1ilинформационным вектором объекта Si .Задача распознавания состоит в том, чтобы по начальной информации I ,принадлежащей к множеству допустимых информаций {I } о классах K1 ,..., Kl , и~предъявленной для распознавания выборке S q  {S1 , S 2 ,..., S q } построить информационнуюматрицу|| ij ||q  l . Обозначим данную задачу для краткостикакзадачаZ ( I , S1,..., Sq , P1,..., Pl ) или просто Z. Примером начальной информации о классахявляетсятаблицапризнаковыхинформационная матрица.описанийэталонныхобъектовклассовиих49Предположим, что у нас имеется множество алгоритмов { A} , переводящих пару( I , S1,..., Sq ) , I  {I }, {S1,..., Sq }  {S} в матрицы ||  ij ||q  l , составленные изэлементовA(I , S1,..., Sq ) ||  ij ||q  l , где значения0,1, . ij интерпретируютсяобычным образом.

Если  ij  {01, }, то  ij - значение предиката Pj на допустимомобъекте Si , вычисленное алгоритмом A . Если алгоритм A не вычислил значениепредиката Pj ( Si ) , то принимается  ij = Определение 2. Алгоритм A называется корректным для задачи Z , если выполненоравенство A( I , S1,..., Sq , P1,..., Pl ) || ij ||q  l .Алгоритм не являющийся корректным для задачи Z называется некорректным. Вкачестве { A} в дальнейшем рассматривается совокупность алгоритмов, составленнаявообще говоря из некорректных алгоритмов.Основной целью является:А)- введение алгебраических операций над алгоритмами из { A} , позволяющихстроить алгебраические замыкания [{ A}] множеств { A} ;B)- выяснение ограничений для {I }, {S} , { A} , при выполнении которых для любойзадачи Z в [{ A}] существует алгоритм, корректный для Z .

В этом случае замыкание[{ A}] называется корректным относительно {Z}.Теорема 1. Каждый алгоритм A  {A} представим как последовательное выполнениеалгоритмовBиC , где B( I , S1,..., Sq ) || aij ||q  l , aij -действительные числаC(|| aij ||q  l ) ||  ij ||q  l ,  ij  {01, , }, B  B( A) , C  C( A) .Из теоремы 1 следует, что множество { A} порождает множества {B} и {C} . Элементы из{B} будем в дальнейшем называть распознающими операторами, или просто операторами,элементы из {C} - решающими правилами. Числовые матрицы B( I , S1,..., Sq ) || aij ||q  lназывают матрицами оценок объектов за классы, или просто матрицами оценок.Iaij~SqqlПрименениеоператора B ijqlПрименениеоператора CРис.

14. Каждый алгоритм распознавания представим в виде произведения распознающего оператора ирешающего правила50Определение 3. Решающее правило C называется корректным на {S} , если для всякогоконечного набора S1,..., Sq из {S} существует хотя бы одна числовая матрица ||aij ||q  lтакая, что C(||aij ||q  l ) || ij ||q  l . Здесь || ij ||q  l - информационная матрица элементовS1,..., Sq по системе предикатов P1 ,..., Pl .В множестве операторов {B} вводятся следующие операции сложения, умноженияи умножения на скаляр.Пусть B , B   {B} , B ( I , S1 ,..., Sq ) || aij ||q  l , B ( I , S1 ,..., Sq ) || aij ||q  l , b -скаляр.Определим операторы b  B (произведение на скаляр), B   B  (сумма операторов),B   B  (произведение операторов) следующим образом:b   B ( I , S1,..., Sq ) || b   aij ||ql(1.21)( B   B )( I , S1 ,..., Sq ) || aij  aij||q  l(1.22)( B   B )( I , S1,..., Sq ) ||aij  aij||q  l(1.23)Очевидно, что линейное замыкание L{B} множества относительно операций (1.21), (1.22)является векторным пространством.Замыкание U {B} множества {B} относительно операций (1.21) - (1.23) являетсяассоциативной линейной алгеброй с коммутативным умножением.Нетрудно увидеть, что операторы из U {B} могут быть представлены в видемногочленов от операторов из {B}.

Если B   U {B}, то B   b Bi1 ...  Bik . Какiобычно,степеньюоператорногомногочленаназываетсямаксимальноечислосомножителей в слагаемых . Bi1...Bik .Определение 4. Множества L{ A}и U {B} алгоритмов A  B  C* таких, что B  L{B}( B  U {B}), называются линейным (алгебраическим) замыканием { A}.~~Зафиксируем информацию I  {I } и выборку S q  {S1,..., Sq }, S q  {S} . Будем~рассматривать задачи ( I , S q ) , обладающие следующим свойством относительно~множества B распознающих операторов.~Определение 5. Если множество матриц {B (I , S q )} (операторы B пробегают множество~B ) содержит базис в пространстве числовых матриц размерности q  l , то задача~Z ( I , S1,..., Sq , P1,..., Pl ) называется полной относительно B .51~Теорема 2.

Если множество {Z} состоит лишь из задач, полных относительно B , то~линейное замыкание L{B  C*} , где C* - произвольное фиксированное корректноерешающее правило, является корректным относительно {Z}.Следствие1.Пусть{ A}-совокупностьнекорректныхалгоритмов,{B}-соответствующее множество операторов, C*-фиксированное корректное решающееправило. Тогда L{ A}  {L{B}  C*} является корректным относительно {Z} , если {Z}состоит из задач, полных относительно {B} .Следствие 2. Пусть выполнены все условия следствия 1 и, кроме того, [{B}] естьзамыкание {B} относительно операций (1.21) - (1.23).