автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Построение корректных моделей алгоритмов ограниченной емкости

РГБ им

^ I) М1?

На правах рукописи

МАМАЕВ Владислав Владимирович

ПОСТРОЕНИЕ КОРРЕКТНЫХ МОДЕЛЕЙ АЛГОРИТМОВ ОГРАНИЧЕННОЙ ЕМКОСТИ

Специальность 05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1998

Работа выполнена в Московском педагогическом государственном университете на кафедре информатики и дискретной математики

НАУЧНЫЙ РУКОВОДИТЕЛЬ: действительный член РАО, доктор физико-математических наук, профессор Матросов В.Л.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

доктор физико-математических наук,

профессор ДюковаЕ.В. кандидат физико-математических наук, доцент Гуров С.И.

Ведущая организация — Центральный научно-исследовательский институт экономики, информатики и систем управления.

Защита состоится ..^^^г.... 1998 г. в ./Xчасов на

заседании Диссертационного совета К 053.01.16 в Московском педагогическом государственном университете по адресу: 107140, Москва, Краснопрудная ул., д. 14, математический факультет МПГУ ауд.301.

С диссертацией можно ознакомиться в библиотеке МПГУ по адресу: 119435, Москва, ул. Малая Пироговская, д. 1.

Автореферат разослан ...... 1998 г.

Ученый секретарь .

диссертационного совета -- Чиканцева Н.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Широкий класс среди вышеупомянутых задач представляют задачи распознавания образов, являющиеся в частном случае дискретным аналогом проблемы поиска оптимальных решений. На практике это задачи из таких областей, как геология, медицина, социология, химия — не позволяющие строить формальные модели. Это обстоятельство определило тот факт, что на первом этапе развития теории и практики распознавания образов возникло большое число различных методов и алгоритмов, применявшихся без какого - либо серьезного обоснования для решения практических задач. Такие методы, как это принято во всех экспериментальных науках, обосновывались экспериментальной проверкой — успехом решения реальных задач. Однако очевидна необходимость изучения с помощью строгих математических методов самого множества таких процедур.

Кроме обилия прикладных вопросов, исследование которых сводится к задачам этого типа, следует отметить весьма важный для математиков факт, что решение таких задач ввело в обиход большое число некорректных (эвристических) алгоритмов. Очевидно, появление каждого из таких алгоритмов можно рассматривать как эксперимент, а со всем множеством таких экспериментов и их результатов — работать, как с новым для математики множеством объектов. В результате возникают теоретические проблемы, решение которых имеет большое практическое значение. Это такие проблемы, как оценка емкости важных моделей алгоритмов, исследование корректирующих операций, синтез корректных алгоритмов минимальной сложности, решение вопросов об их устойчивости. В настоящее время перспективной представляется идея построения корректных алгоритмов методом покры-ТИЙ1'2'3.

1 Журавлев Ю.И., Исаев И.В. Построение алгоритмов распознавания, корректных для заданной контрольной выборки. — ЖВМ и МФ, 1979. Т. 19. № 3, — С. 726 — 738.

2 Матросов В.Л. Оптимальные алгоритмы в алгебраических замыканиях операторов вычисления оценок. // ДАН СССР, 1982. Т. 262. № 4. — С. 818 — 822.

* Исаев И.В. Задача синтеза корректного алгоритма распознавания, как задача построения минимального покрытия // ЖВМ и МФ, 1983. Т. 23. № 2. — С. 467 — 476.

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

Методы исследования. При получении результатов были использованы метод £ — сечений 4 и метод минимальных покрытий, позволяющий эффективно выделять в модели ABO максимальные операторы5. Использовались средства вычислительной техники для апробации полученных теоретических результатов.

Научная новизна. Все основные результаты диссертации являются новыми.

Основные результаты диссертации:

1. Получены оценки верхней и нижней границ емкости модели

ABO.

2. Для алгебр вычислимых операций произвольного типа над классом всех ABO и классом ABO с опорным множеством {7iv,Á-}c{l,2,...,/¡} получены верхние оценки емкости исследуемых моделей алгоритмов, инвариантные относительно выбора главных операций, при условии ограничения на их размерность.

3. Для произвольной регулярной задачи разработан метод синтеза корректного алгоритма основанный на построении минимального операторного покрытия, предложенного B.JI. Матросовым2, дана оценка радиуса устойчивости синтезированного алгоритма.

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

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

4 Матросов В.Л. Емкость алгебраических расширений модели алгоритмов вычисления оценок. // ЖВМ и МФ, 1984. Т. 24, № 11. — С. 1719 — 1730.

5 Матросов В.Л. Оптимальные алгоритмы в алгебраических замыканиях операторов вычисления оценок. // ДАН СССР, 1982. Т. 262. № 4. — С. 818 — 822.

Результаты и методы диссертации могут быть использованы в дальнейших исследованиях как в рамках алгебраического подхода, так и при решении других проблем теории распознавания в МПГУ, ВЦ РАН и других университетах и пединститутах.

Апробация работы. Результаты диссертации докладывались на семинарах кафедры информатики и дикретной математики МПГУ.

Публикации. Основные результаты диссертации представлены в пяти работах (см. ниже).

Структура работы. Диссертация состоит из введения, трех глав, списка литературы, содержащего 81 источник и приложения. Всего 111 страниц, 7 рисунков.

СОДЕРЖАНИЕ РАБОТЫ

Введем следующие обозначения: -§т = ^,..., — обучающая выборка; = (51,..., —- контрольная выборка; = (ад,...,а;„); 5' = (Ьп,..., Ь1п); ] = 1,2,...,/и; / = 1,2,...,?.

Рассмотрим множество М допустимых объектов. Пусть заданы множества М1,..., Мп — области значений признаков 1,2,,..,л соответственно. ,

В каждом М1 определена неотрицательная функция р,(х, у) — полуметрика со свойствами х) = 0, у)>0 при хФу,

х,у*Мп 1=1,2,...п. М= {5} = {(о1,...,ав)}) где СЦеМ,,

г = 1,2,... п.

Рассмотрим множество {/„} начальных информации. Пусть — произвольная конечная совокупность объектов из М, причем для каждого 5г задан информационный вектор а(5;), 1 = 1,2,...т. по системе предикатов РД5) — "5е К]",] = 1,2.....1.

I

М = и К}, а элементы {/„} определяются:

/=1

1а ={51,...,в„,а(в1).....а(вт)}.

Каждый алгоритм А вычисления оценок6 определяется в виде А = А(г, с, р, у, С), где г, в, р, у, — набор параметров, А = Н ° г(С), /?(е, е, р, у) —распознающий оператор, он применяется к начальной информации 10 и контрольной выборке ¡5я. Его результатом является

'Журавлев Ю.И. Корректные алгебры над множеством некорректных (эвристических) алгоритмов. I. II Кибернетика, 1977. № 4. — С. 14 — 21.

матрица оценок Гц принадлежности объектов классам К1 (/=7,

я; }=1.....Г):

г(С) — фиксированное пороговое решающее правило, результатом его действия на матрицу оценок ; является информационная матри-

ВДЩ.Г = Р. ^ {0,1, Л},

С = (с15 с2) — определяется набором констант с15 с2, сг > 0, с2 > сг. Оно задается следующими условиями: если Гц < сх , то = 0, если Гц > с2 , то ру = 1; если < Гу < с2 , то [3 у = А.

Пусть {О} -— совокупность всех непустых подмножеств множества {1, 2, . ... п}. Алгоритму А сопоставляется совокупность {Пд} с: {Г}}. Элементы {Ол} называются опорными множествами алгоритма А.

Систему опорных множеств {С1А} определим следующими способами:

A. Совокупность опорных множеств {П^} состоит из одного множества £1Л = {г1,...,£Л}.

B. Совокупность {Г2Д} состоит из всех одноэлементных подмножеств множества {1,2,...,«}.

Любому С1А = взаимнооднозначно соответствует бу-

левский вектор ш со„) такой, что = ... = <а,4 = 1 , и

остальные координаты <5 равны 0.

Всякому оператору Я поставим в соответствие функцию близости ВЦ&З^ёБ;), где е = (е1,...,сд), ег > 0, г=1,2,...,л, в — целое

число, е> 0, сой' = 655^ =

Напишем систему неравенств рг(Ь(г,а1г) < £г, г = (2)

если число невыполненных неравенств В^((Ь5', 55.) = < в системе (2) не больше е;

Р'

10,

(3)

в противном случае. Оценка Гj(S) по классу Ку. Пусть каждому Пл е {Г1Д} сопоставлен числовой параметр = р{5> А}; каждому из 10 — числовой параметр у(£()- у¡,1= 1,2,...,т.

Pj(S) = I £ y(S,) • ^(й) • в/(й5г, <5S),

где jBs£ = 1- Bs£, Qx, Q2 — нормирующие множители.

ГД5) - x, ■ rJ(S) + x0 ■ Tj(S), -r0, = 0, 1.

Под моделью алгоритмов будем понимать некоторую совокупность алгоритмов распознавания, имеющих общую область действия. Для задания модели необходимо: описать используемую систему опорных множеств, задать способ вычисления функции близости, определить формулы вычисления оценок и указать используемое решающее правило. Фиксация параметров (s,e,p,y, С) в модели позволяет задать конкретный алгоритм.

Диссертация состоит из трех глав, каждая из которых является логически завершенной сама по себе. Однако их объединяет общая идея — построение, исследование и практическая реализация корректного алгоритма.

В первой главе выполнены построения, на основании которых получены оценки емкости некоторых важных классов алгоритмов. Параграф 1 включает в себя основные понятия, определения и теоремы. Приведенные в нем факты являются, по сути дела, классическими, поскольку практически любая работа, выполненная в рамках алгебраического подхода, использует их в качестве исходных. В параграфе 2 проведены рассуждения, на основании которых сделан вывод о емкости описанной модели ABO, получен количественный результат в виде оценки верхней границы емкости модели ABO. Определены введенные автором понятия вектора близости и элементарной функции близости.

Изложим результаты § 2 более подробно. Опишем исследуемый класс алгоритмов. Систему опорных множеств {Оя} определим следующим образом: Í1R = {i1,...,ir},me {¿!.....ir) с {1,2,...,п).

Функция близости определена формулой (3). Оценка Fj (S) по

классу Kj: Г AS) = -J-- £ £ (А» • -+Prk )B¡(&S, <5 S,),

где fi(Wj) — число элементов в W), Wj = ^ П {S,,...,Sm}, N — нормирующий множитель.

C = (cltc2) — фиксированное пороговое решающее правило с порогами с1г с2.

Описанный выше класс алгоритмов будем называть моделью

е, е, р, у, С) или просто 5Ш .

Пусть Л = Л(5Ш) — пространство параметров, задающих алгоритм модели ОТ. CZ^[A] — классификация выборки S9 в пространстве допустимых объектов М, реализуемая алгоритмом А.

Любой алгоритм А е ЗЯ будем рассматривать в виде А = A(S,a), где а е Л, S е М.

Модель 5Ш порождает систему событий

Г(Л) = {Tjp. е Л}, ro = TJ5TO] = {(5, J)|A(S, а) = J, Ael}.

Определение. Индексом системы событий Т(А) называется число элементов множества классификации С А):

Доказаны теоремы:

Теорема 1.2.1. Индекс системы событий Т(А) по любой выборке допустимых объектов S' длины ^ ограничен сверху:

Ind^(S")<(qm)n.

Здесь и далее, — число объектов в обучающей выборке, п — размерность признакового пространства.

Определение. Функцией роста класса {A(S, а)} называется

m,(q) = max Iitd^(Sg)

(s1.....s«)

Теорема 1.2.3. Функция роста модели 3J? не превосходит (mq)n: mT(q)<(mqr.

Теорема7. Функция роста mz{q) либо тождественно равна 2f, либо мажорируется степенной функцией 1 ,bqn~l / (п -1)!, где п — минимальное число q, при котором тат(г/) ф. 2ч .

По теореме, число п -1 служит мерой разнообразия класса

{¿(5, а)}-

Определение. Число п -1, такое что mx (q) < l^"-1 / (п-1)1, где п — минимальное число q, при котором m^(q)*2q, будем называть емкостью класса {A(S,a)} и обозначать Лл (S,a).

7 Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.: Наука, 1974. — 418 с.

Основная теорема:

Теорема 1.2.4. Емкость модели 5Ш ограничена сверху: AA(S,á) < inm.

Параграф 3 посвящен дальнейшему исследованию модели алгоритмов, описанной в параграфе 2. Полученная нижняя оценка границы емкости модели ABO представлена в теореме.

Теорема 1.3.1. Емкость модели алгоритмов Ш ограничена снизу: Aa(S,cl) > тп.

В параграфе 4 дана оценка верхних границ емкости алгебраических расширений моделей 5Ш0 и полученные оценки инвариантны относительно выбора главных операций, при условии ограничения на их размерность. Проведенные в нем построения во многом опираются на идеи В.Л.Матросова89.

Перейдем к более подробному изложению результатов § 4. Рассматриваемые модели и TOg представляют собой модель всех алгоритмов вычисления оценок и ее подмодель с опорным множеством c{l,2,...,n] соответственно, над упорядоченным полем

G = {(£;*,Ф,®). Порядок на множестве <5 задается бинарным отношением >- и является частичным. Области истинности и ложности отношения >- являются непустыми. *,Ф,® — вычислимые операции. Vx, у: х,у&&, {х<у) = {у>-х).

к к X *Xt = Х{*. . *Хк , = • "

1=1 i=l

М = Aíj х ... х Мп — пространство признаков. Через R(n) обозначим пространство признаков М = М1х ... х Мп, где M¡ = (R,p¡),

R - множество действительных чисел, pt(x, у) = \х - у\, i = 1,2.....п.

Упорядоченный набор алгоритмов А. — (А^,... t А^) назовем вектор-алгоритмом, At е Ш? а, i = l,2.....L.

Пусть IL = (&;fj —алгебра, где //"' — произвольные rt — местные операции на Q, i = l,2,...,k, rt = 1,2,... . Tr"(U) — множе-

L

ство всех v -местных термов алгебры U, Tr(U, L) = ^JT"(U).

и=1

' Матросов В.Л. Емкость алгебраических расширений модели алгоритмов вычисления оценок.//ЖВМ и МФ, 1984. Т. 24, № 11. — С. 1719— 1730. 9 Матросов В.Л. Корректные алгебры ограниченной емкости над множеством алгоритмов вычисления оценок. //ЖВМ и МФ, 1981. Т. 21, N3 5, — С. 1276— 1291.

Каждому терму tr е Тг(31,1/) соответствует операция Г на (£, — множество всех таких операций. 7(Ь) — некоторое подмножество множества Ти (Ь). Введем обозначения:

Основные теоремы.

Теорема 1.4.3. Емкость модели ограничена сверху

д«[(®о)г] < 8М тп, щ1/2 + 2)2тп,

"Я (л)

где Е-^п, т,Ь) и т, Ь) — функции от натуральных аргументов: g1(Jl,m,L) = l + {У2 + 2У2™1 [п+Ь 3+1л к£2(2от(% + 2)2™' + то) +1) -1],

о \—/ 0 \2

Ь та 1 г ,, „ т , ,„ ( //от

дг(п,т, Ь) = 1+ —J [п + 1Лог2 3 + + от) + 1)-1].

Теорема 1.4.4. Емкость модели ограничена сверху

Двд[(®с)г] < />> т, ШтЬУ,

с)т] < Ш, т, Ц(Ь +1 Г", где ^(га, от, £) и /2(п>т> £) — функции от натуральных аргументов:

т,Ь) = 1 + ЩтпЬУ 1<яа( £ Скп(Щт(2тЬУ + от +1) +1) I- {2тЬ)'п,

4=1 У

/а(п, ш, Ц = 1 + ДЬ +1)-™ 1о&2( I; С*(3(2т(Ь +1)"" + от +1) +1)] - (£ +1)-™.

Во второй главе рассматривается проблема синтеза корректного алгоритма. В основе идеи построения корректного алгоритма лежит минимальное покрытие, предложенное В.Л.Матросовым2, а также тот факт, что для любой регулярной задачи г существует конечное множество операторов из бесконечного класса такое, что замыкание этого множества относительно некоторых простых операций обладает такими же разделяющими возможностями по отношению к задаче 2 , что и сам бесконечный класс операторов8. В параграфе 1 описывается

принцип построения минимального покрытия множества допустимых объектов Sq классами объектов из этого множества.

Определим последовательность классов допустимых объектов из §я, такую что объекты S'1, S'2 е S9 попадают в один класс, если р(k, i, = p(k, i,t2). В результате для любых i = 1,2,..., т ; к = 1,2,..., п данная последовательность имеет вид:

и1,...,и[„(Ш,1<ра,к)<д (4).

Множество допустимых объектов Lrv{i, k) = |J ,

v<J<r

где ülk взяты из (4), a (v,r) — произвольная пара натуральных чисел 1 < v < г < p(i,k), назовем (I, k) —интервалом.

Определение. Покрытием множества S а Sq будем называть всякую последовательность (i, h) — интервалов

L\(i,k).....Ljji,v,hiv) - такую, что S с ( [j 1% Щ, kj)), и

l<j<W

обозначать 7t(W, S).

Ck{W, S) — { У LrJ (ij,kj))\S — избыточное множество t</<w '

покрытия n(W, S).

Пусть S№ = {S"|u € SR(J)}, где W(J) = {i>|aUi/ = 1}, gajj^ -

информационная матрица задачи Z.

Пусть я1(Т^,5СН)),я2(Жа,5(5Я))>...,я1(ЖЕ>5(Я)), —

последовательность всех покрытий множества S(5i). Каждому се элементу соответствует конечная последовательность

покрытий избыточного множества Ckj = СпДТ^.Й^)): «ijOV^Otj), n2j(W2j,Cn

Множество допустимых объектов j, S(9i)) определим

следующим образом: x¥(x,j,S(^)) = S{yi)f]nxj(Wxj,Cnj),

Построим функцию Е(х, /) = W} + Wx/ + , достигающую минимума в некоторой точке (х0,}0): E(x0,j0) = minf£(^,/)|х = 1,2, ...,(5,

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

Рассмотрим § 2 подробнее.

uJ

Осуществляется построение оператора Rj'k, z = 1, 2, ..., /л ; к = 1, 2,..п\ J = l,2,...,l, следующим образом:

jrl jr2ijt jyi

Rja = Rj " - Rj *, где " оператор с системой опорных множеств

1

£1 = {{1},{2}, ...,{я}}> параметры: xi=l, л:о=1; Yi=l> =

i' = 1, 2,т, i' * i, N > 2mn \ pk = /Г1, k = 1, 2, n. zh выбирается следующим образом: Случай 1. S, е JC,: если Р^.*7/*) >

V / = 1, 2.....p{i,k), f Ф j, то tk - +оо, иначе eh выбирается так,

чтобы выполнялось неравенство U\k) < ск < pk(Si\,U'ik), где U}h

такое, что рк = min pA(Z7/fe) i//^). Остальные гк. = -1,

fe* = 1, 2, п, Ы ф к.

Случай 2. St е CK у. если pA(SP tf/*) < Pk(St,U{k)

V j' = 1, 2,..., p(i,k), j' *■ j, то eÄ = -1, иначе eä выбирается так, чтобы выполнялось неравенство pk(St, U'lk) < zk < pk(Sit Ulk), где i7/Ä такое, что p* = min рк(11(к,иЦ). Остальные ek, =+qo,

# = 1, 2, n,k Оператор Rj ".

Система опорных множеств £2 = {{1},{2},...,{тг}}; параметры:

jci=1, jco=1; Yj = 1 Yv = i' = 1, 2.....пг, i' * i, N>2mn; =

k = 1, 2, 71 .

выбирается следующим образом: Случай 1. Кj: если рk(St,Ulk) < p^EZ/J

V /' = 1, 2, ..., p(i,k), j' = j, то ск = -1, иначе £fe выбирается так, чтобы выполнялось неравенство p^OS^l//*) < Е* < Где Utk такое, что pfc = min pk(Ujk, 1}{к). Остальные £k, = -1

К = 1, 2, n, К * k.

Случай 2. SteCKj: если p*(S„ C//Ä) > pk(S,,U£)

V /' = 1, 2, p(i,k), у ф j, то £j = -к», иначе eÄ выбирается так, чтобы выполнялось неравенство PkiSpU^) < ск < pk(St,Ujh), где ¡7^

такое, что pÄ = min pk{U[k, U(k). Остальные еА = -ко, vui-.u'^ui

к = 1,2, n,k!

Вводится понятие изоморфизма объектов Sv ~ Sw. Определение. Задачи Z = (S1.....Sm,a(Sj),...,а(Sm), S1.....S1}

называют регулярными, если они удовлетворяют условиям:

1) Ки * К0, и = 1,2,.. .,1; v = 1,2,...,и - 1,и +1,...,

2) Sv ^Sw,v*u>,v,we{l,2,...,q};

3) {S1,...,Sm}n{S1,...,Si} = 0.

Совокупность всех регулярных задач будем обозначать {Z}. Доказывается теорема.

Теорема 2.2.2. Для всякой регулярной задачи Z(IQ, Sq) оценки,

U* 2 U^

вычисленные оператором R/k - Rj •* - Rj *, удовлетворяют неравенству 1 > I tJ Vi' е Ufk, teU'k.

Здесь Ги и — оценки, вычисленные оператором Rj'k. В параграфе 3 проведен синтез отделимо-корректных алгоритмов. Доказаны теоремы.

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

для задачи Z = Z(I0,Sq), если столбец информационной матрицы

A(Z) = (Зу| совпадает с J-ым столбцом истинной информационной

матрицы задачи Z.

Рассмотрим функцию Е(х, j) = Wf + Wxj + в некоторой точке

(■*•<)> /о) • Пусть Е(х, /') достигает минимума в этой точке Е(х0, /0) = min{£(*, ;)| х = 1,2, ...,©, j = 1,2,..., £} и = 0, тогда верна следующая теорема.

Теорема 2.3.1. Для всякой регулярной задачи Z{I0, Sq) существуют фиксированные пороги а и а такие, что алгоритм вида Aj = Rj °C(cltc2),

Rj= • (5)

Ч -4**10 Wto • svmc^io lw*0J0 'C*io) где S(J) = {S'jn Kj, является корректным по классу К3.

Определение. Класс алгоритмов 5Л называется отделимо-корректным над множеством задач Z, если для всякой задачи Z е Z и

любого 1=1, 2, .... I существует алгоритм Aj е Ш, корректный по классу isTj для Z.

Пусть /? — множество действительных чисел, |*у|| —

информационная матрица задачи Z. Тогда величину V(Z) = max|9í(J)|,

1<J<Í '

9í(J) = {i>| avJ ~ 1} назовем весом задачи Z.

Через Zq(I0,5) обозначим класс регулярных задач Z(I0, Sq), вес которых ограничен V(Z) < S , 0 < 5 < q.

Теорема 2.3.2. В алгебраическом замыкании операторов U }* степени 8 существуют операторы Rj вида (5) такие, что класс алгоритмов {А}, где А - Rj ° C(clt с2), является отделимо-корректным над Z4(I0,b).

Теорема 2.3.1 сформулирована для случая, когда функция Е(х, j) = W¡ + WXJ + %s¡ в точке Ow'u) имеет %x¡¡¡r¡ = 0. Сформулируем аналог теоремы 2.3.1 для случая %X<¡J{¡ 0.

Теорема 2.3.3. Для всякой регулярной задачи Z(IQ,Sq) алгоритм Aj = Rj ОС(с!,С2), 1

Rj =

uLvl>c*iB(W¡aMJ))\C*ro,0lWxo¡a,Cxj0)

на выборке S" по классу Kj имеет частоту ошибок v(Aj) < .

В параграфе 4 для произвольной регулярной задачи Z осуществляется построение корректного алгоритма. Рассмотрим оператор

l j=i

где Rj — оператор, определенный в (5).

Доказывается основная теорема. Пусть Z — произвольная регулярная задача Теорема 2.4.1. Алгоритм

A - R о , с2),

где C(Cj, с2) — фиксированное пороговое решающее правило: п(т -1) +1 2

с, = 1, с„ — —------; является корректным для задачи

п(т -1) N

Z(S\I0).

Здесь п — размерность признакового пространства; т — длина обучающей выборки; N—нормирующий множитель.

В параграфе 5 исследуется вопрос об устойчивости синтезированного корректного алгоритма. Показано, что синтезированный алгоритм является устойчивым, оценка радиуса устойчивости дана в теореме 2.5.1.

Более подробно о § 5. Рассмотрим множество задач Z(I0,Sq) такое, что начальная информация

h = (№.....¿U.WS:).....«(£„)});

a(St) = (ai.....aí): a^ = P(S,) =Г' f¡ 1'K¿ , J = 1,2,

[0, S, e Kj

и длина выборки q в нем являются фиксированнными.

Пусть Z(/0,«S7) — фиксированная задача из множества Z(Iü,Sq), А(£, р,у, k,x,Q.,C) —алгоритм, корректный для задачи Z(I0,Sq).

Для всякого допустимого объекта S'Q е

{So»• • ■> S¡} в

пространстве признаков М = Мх х ... х Мп будем называть е-окрестностью этого объекта открытый гипершар в признаковом пространствеМс центром S'0 - (als...,an) и радиусом г.

Определение 2.5.1. е-окрестность допустимого объекта S'a будем называть компактной, если для всякого входящего в нее допустимого объекта S информационные векторы

(a1(5¿),...,a{(5¿)) и (a1(S),...,a,(S)), построенные алгоритмом А(ё, р, у, к, х, Q, С), совпадают.

Определение 2.5.2. £-окрестность допустимого объекта S'0 будем называть оптимально-компактной, если она компактная и на ее границе найдется допустимый объект S такой, что информационные векторы (ci1(Sq),...,ci1(S¿)) и (a1(S),...,a¡(S)), построенные алгоритмом A(s, р, у, k, 5с, Q, С), не совпадают.

Пусть для каждого допустимого объекта , t = 1,2,..., q из выборки S¡¡ и алгоритма А(е, р, у, к, х, fi, С) существует оптимально-компактная s-окрестность ненулевого радиуса rt = г( .

Рассмотрим множество всевозможных выборок {S"}* длины q таких, что каждый допустимый объект S' из любой выборки S9 с {S4}* принадлежит оптимально-компактной Е-окрестносги допустимого объекта S'Q. Каждая такая выборка S'1 с: {£'}* однозначно определяет задачу Z(I0,Sq) во множестве задач

£*(/„, <§?). Из определений 2.5.1 и 2.5.2 следует, что для любой задачи из множества задач определяемого

множеством выборок допустимых объектов {й9}*, алгоритмом А(£, р, у, к, х, С1, С) будет построена информационная матрица

Ца^Ц^0'5 1, совпадающая с информационной матрицей Ца^Ц^""5"'

задачи

Определение 2.5.3. Корректный алгоритм А будем называть устойчивым, если множество задач Z*(I0, §<7)\Е(10,§д) —непустое.

Определение 2,5.4. Радиусом устойчивости корректного алгоритма А будем считать величину шпе, , I = 1,2,...,д и

обозначать г(/0,59).

Основная теорема.

Теорема 2.5.1. Для произвольной регулярной задачи 2(/0,<£г) радиус устойчивости корректного алгоритма А = В. ° С(с1, с2):

В третьей главе осуществлена практическая реализация решения задачи распознавания. Исходя из соображений, что в значительном числе работ в рамках теории распознавания образов решались практические задачи, связанные непосредственно с распознаванием (текста, речи, изображений), в данной работе рассматривается задача несколько иного характера. Известно, что при определенных условиях большинство задач, связанных с принятием решений, может быть сведено к задачам распознавания10 . Среди задач принятия решений особо выделяются задачи удерживания объекта (процесса) в устойчивом или максимально близком к устойчивому состоянии. Характерным для таких задач является следующее абстрактное описание. Объект (процесс) в момент времени I находится в состоянии («!,...,!„)• Существует оптимальное состояние (в",..., 8°)' объекта (процесса) в котором он стабилен, то есть при отсутствии вмешательства извне (например управления) за фиксированный промежуток времени Лí его состояние (в1,..., яп) либо не изменяется, либо изменяется минимально. В любом состоянии, отличном от

10 Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. // В кн.: Проблемы кибернетики. Вып. 33. — М.: Наука, 1978. — С. 5 — 68.

..., s°), на объект (процесс) действует сила или совокупность сил диссипативного характера. В пространстве состояний {(s1(sn)} предполагается возможным разбиение на классы. Задача заключается в распознавании наблюдаемого состояния, то есть его классификации, и принятии решения о выборе необходимого управляющего воздействия, результатом которого будет устойчивое (s°,s°) или максимально близкое к устойчивому состояние. Информация об управлющих воздействиях, адекватных наблюдаемым ситуациям, может быть в виде ранее накопленного опыта или в виде знаний, умений или навыков отдельно взятого человека. Эта информация может быть использована в качестве информации о классах состояний, каждому из которых соответствует уникальное управляющее воздействие.

В компьютерной модели обучающая информация включает в себя информацию о 1000 допустимых объектах и 20 классах. Допустимые объекты рассматриваются в трехмерном признаковом пространстве. Каждому классу допустимых объектов, описанному в информации о классах, соответствует уникальное решение, которое принимается в случае, если распознан допустимый объект, принадлежащий к данному классу. Под принятым решением подразумевается выбранный способ управления системой, математическая модель которой реализована в программе. Объекты из выборки допустимых объектов, предъявляемой к распознаванию, являются набором состояний системы в различные фиксированные моменты времени. На множестве состояний определено подмножество, называемое стабильным. Система находится под действием сил диссипативного характера, результатом действия которых может быть выведение системы из стабильного состояния. Цель управления — удержание системы в стабильном состоянии.

Математическая интерпретация выше описанной задачи, а также компьютерная модель корректного алгоритма решающего эту задачу, формальное описание которого дано во второй главе, выполнены на персональном компьютере типа IBM PC 486DX2 — 80MHz/RAM 8MB/HDD 1GB. В качестве языка программирования использован язык Turbo С++ 1.0.

Компьютерное моделирование показало, что синтезированный корректный алгоритм проводит эффективное распознавание, на основании которого принимаются правильные решения об управлении системой.

Публикации по теме диссертации

1. Мамаев В.В. Верхняя и нижняя границы емкости модели алгоритмов вычисления оценок. Депонир. в ВИНИТИ, № 216-В97, 27.01.1997г. - 5 с.

2. Мамаев В.В. Верхние границы емкости алгебраических расширений моделей Шс и Депонир. в ВИНИТИ, № 215-В97,27.01.1997г. - 5 с

3. Мамаев В.В. О емкости одной модели алгоритмов. //Вестник Вятского пед. ун-та. Матем., инф., физ. Выл. 3. — 1997. —С.37-38.

4. Жданов A.A. Мамаев В.В. Беляев Б.Б. Использование принципа автономного адаптивного управления в системе угловой стабилизации космического аппарата "Спектр РГ" // Сб. науч. тр. Информационная бионика и моделирование. — М.:ИФТП,.1995. — С. 87 — 114.

5. Мамаев В.В. Матросов В.Л. Иванова Е.А. О компьютерной реализации распознающего алгоритма. // Тез. докладов VIII Всероссийской конференции "Математические методы распознавания образов" М.: 1997.— С. 188.