Условия корректности алгебраических замыканий эвристических алгоритмов распознавания Дюсембаев, Ануар Ермуканович

Введение к работе

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

Опишем характерный при таком подходе метод решения задачи распознавания.

Пусть множество объектов / покрывается двумя непересекающимися классами К₄ и 1<і и задано т объектов обучения %1 э ^xi >"' 9 Ж_т 5удем считать, что каждый объект ОС представляет собой вектор размерности П, т.е. X-(Q-4 fiif», &h ) _t координаты которого принимают вещественные значения. Для каждого из обучающих' объектов ЗС, , Х₂ ,,,, _? 0С_т известно, в какой из классов он входит. Распознающий алгоритм задается набором чисел -коэффициентов, определяющих гиперплоскость

/7

в евклидовом пространстве признаков. Классификация новых объектов происходит по следующему правилу: объект СС заносится в класс К, , если X лежит в "положительном" (т.е.^^^^"'^?//^ О) полупространстве и заносится в класс /Q , если ЭС лежит в "отрицательном" (т. е. ^ 4,+ft л і * '« + fa #л +fatf < О) полупространстве определенных гиперплоскостью л . Функционалом качества

здесь является отношение числа правильно классифицированных объектов обучения к числу всех объектов в обучении. Необходимо найти алгоритм (т.е. определить коэффициенты^ ,f/_z ,.>->J/n ttfn+i гиперплоскости д ), максимизирующий функционал качества. Для этого условия правильной классификации каждого из объектов обу-четт j-(*hf , Я/г,"' , _f/~f>ts<»jiTl запишем в виде системы линейных неравенств

* 0 ф

.* ' * » » » *

fr &mi +'"+">» + y»+l < О

Решение y_{f ;}Й ,,, >;У*і?У/}фі этой системы в случае ее совместности определяло бы алгоритм, точно классифицирующий объекты обучения. Но данная система в общем случае является несовместной. Выделив из этой системы максимальную совместную подсистему и решив ее, мы получим значения параметров экстремального алгоритма. В свою очередь, решение задачи о выделении максимальной совместной подсистемы в системе линейных неравенств потребовало разработки специальных методов [*32],[33].

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

Как известно, исходные семейства (множества) распознающих алгоритмов строятся на различных принципах, таких как: принцип разде-ления["б], [ІЗ], частичной прецедентности іб], потенциалов flj; на структурных 36(,(.39(, на статистических [*6,2J принципах и т.д. И выбор

5 того или иного алгоритма исходной совокупности эвристик для решения конкретной задачи осуществляется некоторой процедурой, требующей либо, в общем случае, значительных вычислительных усилий и не гарантирующей при этом высокую точность распознавания, либо существование сильных ограничений на обучающую информацию при удовлетворительной точности распознавания [ 2&) Однако, в ряде случаев известны условия, гарантирующие математическое обоснование применимости эвристических алгоритмов при решении конкретных задач і в J . На практике проверка этих условий затруднительна ввиду недостаточности априорной информации в задачах распознавания. Поэтому часто обоснованием применимости эвристических алгоритмов при решении новых прикладных задач является большое число решенных с их помощью и с приемлемой точностью задач распознавания в различных областях естествознания. Таким образом, важной задачей теории распознавания на втором этапе является задача создания численных методов для решения прикладных задач и их теоретическое или экспериментальное обоснование. Целью теоретического подхода является определение корректных множеств алгоритмов для задач распознавания, т.е. множеств алгоритмов,содержащих для каждой конкретной задачи точно её решающий алгоритм.

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

Основы такой общей алгебраической теории были заложены в ряде работ Журавлева Ю.И. [ 10,II,12,13,14,15] . Другим общим подходом к проблеме распознавания является подход, развитый в работах Гренандера У.

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

_{і L<4~ **<*»'}

суммарного риска₃ (L - число объектов в контроле / бJ . Таким
образом понятие корректного алгоритма подменялось понятием опти
мального алгоритма. Благодаря тому, что в алгебраической теории
для . синтеза корректных алгоритмов требуются чрезвычай-

но простые операции над матрицами, такие алгоритмы легко реализуются на ЭВМ, и, более того, аналитический вид корректных алгоритмов удобен для их естественного распараллеливания на современных многопроцессорных ЭВМ L38]

Приведем необходимые определения и утверждения из [ 10,11,12].

Пусть(р| - множество допустимых объектов, а X - множество описаний, соответствующее множеству Г р/ . Элементами множества /С являются И - мерные векторы, при этом множество /{ так-

же есть декартово произведение множеств Kf 1*-%),,#;Е* »где
t« - множество чисел, являющееся областью значений С - го приз
нака, р

ПустьX^ Q К: _; Kif ttij.nj/(^-классы.

Рассмотрим \4ri)W)4tf~ множество одноместных предика-

тов. Каждый предикат У\ определен на множестве X -

Информационной строкой оі( объекта ЭС{ _f Х( Є/ ^по системе предикатов Уг^,„, Р^\ является строка < ~(А«,<Л11,,,,^1^ ^4 = /7(0). Пусть далее X ^s №4>%1и"рХы)- множество допустимых объектов, для которых информационные строки по предикатам

'nJ'jL/tn/'t известны, тогда за начальную информацию некото-

рой задачи 2л возьмем множество Iq ~ 7#T^,,,_v#ta'^i/^t;'^mJ Множество таких начальных информации обозначим через Ц_а}_ф

Задача iu есть пара ^Хр, / > , где X zjZ*>Jfy.>*»;%$,}-

множество допустимых объектов, для которых информационные строки

по предикатам К . г« . ,,,, Y_t необходимо вычислить. Множества от ъ(Ь т *. t ^г s ч

J\ , X называются обучающей и контрольной выборками соответ
ственно. Обозначим через Условие
/ f\fl z: 0 считаем выполненным для каждой рассматриваемой
задачи.

Определение I. Матрица // dq Hcnrf называется информа-

ционной матрицей набора /^^,,,,/ ЭСл (задачи JBWJ^jf > )

по системе предикатов г_{л t}it^P^ і

Рассмотрим совокупность алгоритмов распознавания {АУ Определение 2. Алгоритм А из \п\ называется корректным для задачи Z » если А по задаче Z вычисляет информационную матрицу задачи

8 Алгоритм А , не являющийся корректным для задачи Z , называется некорректным.

Как правило, исходное множество алгоритмов і А) состоит, вообще говоря, из некорректных (эвристических) алгоритмов, которые обычно дают удовлетворительные по точности результаты при решении прикладных задач. Легко могут быть указаны примеры задач, при решении которых алгоритмы совершают ошибки. Поэтому, естественной является задача модификации множества алгоритмов і А; » при которой модифицированные алгоритмы имеют высокую точность решения прикладных задач и при этом теряют свою эвристичность ( алгоритмы становятся корректными). Для построения такой модернизации существует универсальный метод синтеза специальных расширений исходной совокупности алгоритмов, т.е. синтез их алгебраических замыканий.

В рамках алгебраической теории распознавания может быть поставлена и в ряде случаев решена следующая задача: для заданного множества задач \t*J распознавания выделить в алгебраическом замыкании > априори заданного подкласса алгоритмов і Л) , множество і A/J алгоритмов, среди которых находится алгоритм, точно решающий заданную задачу т)/л\. Более того, часто удается выделить конечное множество алгоритмов, среди которых находится корректный для задачи алгоритм, и указать его аналитический вид.

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

ранее в работах [г, 3, 4, 10, II, 12, 13, 14, 17, 18, 36, 28, 30 J была доказана корректность над задачами со стандартной

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

Представляет интерес также проблема построения корректных замыканий над задачами с бинарной обучающей информацией для алгоритмов типа "тестовых" и типа "Кора", широко используемых при решении прикладных задач, а также уточнения результатов для алгоритмов, основанных на принципе разделения. В Гі0,із7 предложен

виа алгоритма распознавания, в который укладываются все существующие типы алгоритмов, и была доказана теорема о каноническом представлении алгоритмов из множества inj.

Теорема I. Каждый алгоритм представим как

последовательное выполнение алгоритмов Р и С , где о алгоритмический оператор, С - решающее правило, причем

Bf Z) =1 Ц\1^,С(&№№^ЫЩ 1^,^Ш,

ft..- ВЄЩЄСТВЄННОЄ ЧИСЛО, t -IfMj р J J' ijtiij с .

Из теоремы I, следует, что множество 7 -л) порождает

множества fp j и f С) ,

Определение 3. Решающее правило С называется корректным на / , если для всякого конечного набора ^i,T_iptlfJ Та объектов из X существует хотя бы одна числовая матрица

" ^/ 'V^ ' ^такая ' ^что ^ (''^ч''ы^ "^y'Urf ^гД^е ||Яц'1|фг(- информационная матрица элементов OC_AiXi_f„,jX!n по системе предикатов rjf > 11 ;„, j /у . Корректное решающее правило будем обозначать через С

В множестве операторов j qj легко вводятся операции сложения, умножения и умножения на скаляр:

10 Пусть

^{г'і к > &', в"б ш, ШЦіі^тЦії^ті}

тогда

S^llik'ijtl^, (і)

B'tB"=llu'- -bdljll^ , (2)

6'-В"=ііа-_га^і^ _; (з)

Замыкание множества относительно операций (I), (2) является линейным замыканием и обозначается через LiOJ.

Замыкание множества операторов {В/ относительно операций (I) - (3) является алгебраическим замыканием множества операторов { Й/ и обозначается через

Нетрудно видеть, что алгебраическое замыкание И і 8} состоит из операторных многочленов, т.е. если о Є НІи/ то

Максимальное число сомножителей-операторов в слагаемом является степенью многочлена.

Пусть - совокупность операторных многочленов

степени не выше к . Ясно, что

Множество называется алгебраическим

замыканием степени k множества операторов у oj ( алгоритмов 7 А ) ).

Пусть - задача, обозначим через - множество

матриц таких, что

Определение 4. Если множество содержит базис в

пространстве матриц размерности CL^c » то задача Z называ
ется полной относительно (} ) б (^

Теорема 2. f" 10J Если множество \сл\ состоит только из задач, полных относительно О^Ц, , то линейное замыкание и {А) множества алгоритмов является корректным над / 2 /

Следствие іДДДуодь І A j - совокупность некорректных алго
ритмов, f oj- соответствующее множество операторов, С " ^КР"
рентное решающее правило. Тогда является

корректным относительно \сл\ » если 7 jj состоит из задач полных относительно \о\*

Следствие 2.Й(Я.Дуоть выполнены все условия следствия I, тогда

является корректным над JZ} » если iZJ состоит из задач, полных относительно ^tlЮ),

Определение 5. Алгебраическое замыкание >Ц, І of k>i называется квази-полным для множества задач j Zf , если для любой задачи Z из iZ\) ^в лл. І В) существуют операторы D(t,jJ _; 1^Г 4д1₀^) j~lj_ntJt такие, что для матрицы оператора

й ( hp (Z) "Л 17 (hi)\\q ?^{ерны сле}ДУ^юш.^ие соотношения

ffiu'j;}

Определение 6. Совокупность таких операторов hi

і> называется квази-базисом алгебраического

замыкания

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

Пусть J Z } - множество регулярных задач, іАЩ и}) -подкласс алгоритмов (операторов) вычисления оценок IlJ .

Алгебраическое замыкание ьС 1 и) является квази-полным для

_{, Ш1 В)}

iZU ІВ<іф$'Л - квази-базио &І&}.

Ю«И.Журавлевым в Г12] найден аналитический вид корректных

алгоритмов для этого случая и доказана

Теорема 3« Корректный алгоритм /\ для задачи % из /2 /

можно представить в виде .

f '

где II «iu Нл/f - информационная матрица задачи Z* » С -корректное решающее правило с параметрами ^.С^. Сц Са₉

»*№ *С₂е ) " 'V⁽''^{матрица оператора} 6 < ^<р>

К имеет место формула

іля вычисления V имеет место формула ' ' ^J

_-М.

В каждом конкретном случае формула для вычисления К зависит от способа построения операторов u(hj)j 1~^/т/$г_; J-4faij,

Как было показано в последующих публикациях [*17, 18, 19, 27? корректный алгоритм, представленный в виде (I) обладает рядом полезных свойств, тем самым стало ясно, что приведенное выше

ІЗ представление корректного алгоритма удобно для теоретических исследований. Ввиду многократного использования программ, реализующих корректные алгоритмы, естественной является также задача синтеза простых корректных алгоритмов ~1?» 18, 28*], В данной работе упрощение корректных алгоритмов производится за счет дальнейшей параметризации исходной совокупности эвристических алгоритмов. Однако, при этом остается открытым вопрос о емкости алгебраических замыканий параметризованной совокупности эвристических алгоритмов f 27 3,

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

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

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

Диссертация состоит из трех глав, введения и списка литературы. Объем работы страниц.

Доказательства приведенных в работе утверждений в ряде случаев опираются на результаты из С 10, II, izl .

По теме диссертации опубликованы две работы. Основные результаты работы докладывались на I Всесоюзном совещании по статистическому и дискретному анализу нечисловой информации, экспертным оценкам и дискретной оптимизации ( Алма-Ата, 1981), на семинаре лаборатории проблем распознавания ВЦ АН СССР, на семинаре по теории автоматов механико-математического факультета МГУ (ІУ конференция молодых ученых механико-математического факультета, М.,

1982).

В первой главе диссертации рассматриваются подклассы алгоритмов вычисления оценок и множества задач с бинарной обучающей информацией.

Ранее дщ доказательства корректности алгебраичеоких замыканий алгоритмов вычисления оценок над задачами со стандартной обучающей информацией использовались системы опорных множеств

совместно с Возникал естественный вопрос: можно ли строить корректные алгоритмы в алгебраическом замыкании алгоритмов вычисления оценок с использованием произвольной системы опорных множеств. В частности, когда система опорных множеств состоит из тупиковых тестов матрицы обучения, подмножеств множества признаков одинаковой мощности к , представительных наборов [ 5J и т.д.

Кроме того возникает вопрос: влияет ли выбор системы опорных множеств для исходного множества алгоритмов на множество задач, для которых строятся корректные алгоритмы.

15 В диссертации рассматриваются системы опорных множеств удов-летворяющие следующему специальному условию: если СО - элемент системы опорных множеств XL % то СО Ф (/ (л) СО & SL.

Систему опорных множеств ^t- , удовлетворяющую этому условию, будем называть базой множества признаков ^4^ 2^»*»^ /^ /_#

Доказана корректность алгебраических замыканий подклассов

над множествами XL, - нормальных, невырожденных задач соответственно. Следствием изложенных результатов являются аналогичные результаты для тестовых алгоритмов.

Указан аналитический вид алгоритма, корректного для рассматриваемой задачи i-i *

Во второй главе диссертации рассматриваются подклассы

алгоритмов типа "Кора" и множества задач с бинарной обучающей информацией. Алгоритмы подобного типа используются при решении прикладных задач L ⁷ J

Каждому алгоритму из рассматриваемых подклассов также соответствует база множества бинарных признаков )4.)2 _ttlt, ft/ , являющаяся совокупностью опорных множеств для данного алгоритма. В частности, в качестве бызы могут быть использованы: некоторое множество тупиковых тестов матрицы обучения itirnd \ -*) , некоторые подмножестаАдлинн 3 множества І І ) 2,,„jh J,

Доказано, что алгебраическое замыкание подкласса алгоритмов ]MJli^)P )lf ,Cf /і); является корректным над множеством J/ -регулярных задач. Алгебраическое замыкание подкласса алгоритмов

іве диссертации рассматриваются подклассы рас

корректно над множеством задач, объемлющем множество _J/^ - регулярных задач. Указан также явный вид корректного алгоритма для решения рассматриваемых задач.

В третьей главе диссертации рассматриваются подклассы распознающих алгоритмов

порождаемых кусочно-линейными поверхностями и параметрами, причем

іА'ІсіА"},

Для операторов (алгоритмов) из множества \in (К )0 > ^/^)уоценка объекта ОС за класс К І вычисляется

следующим образом Г пі

Ж "М 00

если

_$(Х)>0

если J? (ОС) < О

- ,еоли R(Xi)<0

^!](*)=

НО + I 04

Г⁴ + Г⁴ +1 * Для операторов (алгоритмов) из множества

^{№(*,??/*)}(№(*,??/*,?< А)})}

оценка объекта СС( за класс л/ вычисляется так:

М^Х0ГЖ+&№№ , «ели /ВД>0

pOCiJ-

(2)

(3)

К - кусочно-линейная поверхность, раделяющая два непересекающихся конечных множества объектов в /( ,' fa _} fa ,,, Кт~ "веса" объектов из обучения,ytf(Х-і)Є {P,1}j oljB^jO^} І~1Дґ,

Эти алгоритмы (операторы) подробно описаны в ГіО,І4,І5І . В 1-3 главы 3 приводятся доказательства теорем о корректности линейных и алгебраических замыканий данных подклассов над множествами задач со стандартной обучающей информацией. Таким образом результаты главы 3-ей дополняют результаты, изложенные в ҐЮ,І4,І5І .

Рассмотрим множество задач \ Z} f 10] таких, что каждая

задача Z из iZ)

удовлетворяет следующим условиям:

Задачи, удовлетворяющие условия I будем называть невырожденными.

Пусть Z — ^ j-QjA } - невырожденная задача. Класс Kj flO, 14J называется изолированным в Z , если существуют классы li^ ) &t у Hv ₁1 * fjt_}V С такие, что

і. 1 с й_г.

Рассмотрим множество задач лСц) LlO, I4J таких,что каждая задача Z из і ц \ является невырожденной и кроме того классы <м > «2 ,,ц % J\p ^{не ЯВЛяются} изолированными ъ Z *

Пусть << —>JL_P. задача. Пара классов /> ц,» Ку называется изолированной в Zx , если

1. Ни, Uky^ X

2. Йи П K_v -//.

Невырожденная задача Z =J tl_oiX Ї называется детерминированной, если начальная информация l_v задачи Z не содержит изолированных пар клаосов.

Множество детермированных задач обозначим через і Zcj,
Очевидно, .о М_вісШс&Ь

В работе flO, I4J доказаны следующие теоремы: Теорема 4-. L ЮJ Линейное замыкание

класса алгоритмов с произвольным корректным решающим правилом С и операторами|В К определенными соотношением (3), является корректным над множеством задач {Zi^\_%

Теорема 5* 103 Совокупность алгоритмов

корректна над множеством невырожденных задач )2j* В I главы 3 доказана

Теорема I.I. Множество задач \ Сл ) является полным относи
тельно линейного замыкания , тогда и только тог
да, когда множество \1л\ состоит лишь из детерминированных задач

Следствием из теоремы 1*1 является ^

Теорема Линейное замыкание является корректным над множеством детерминированных задач jZpj,

В г доказана р _/ *ти~

Теорема 1.2. Алгебраическое замыкание

корректно над множеством невырожденных задач І с»).

В 3 доказана

Теорема 1.3. Линейное замыканиеL{n [К, jf ,Л,C_fлС_г)} корректно над множеством невырожденных задач \%)_щ

Автор искренне признателен Ю.йДуравлеву за постановку задач и внимание к работе.

Здесь алгоритмы из [A J обобщают алгоритмы из множества (А использованные в ҐЮ , 14 J .

Похожие диссертации на Условия корректности алгебраических замыканий эвристических алгоритмов распознавания

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

Разработка методов определения состояния объектов на основе синтеза алгоритмов распознавания и прогнозированияАкназарова, Раушан Булатовна

Корректные алгоритмы распознавания в задачах с дискретной обучающей информацией Ицков Александр Григорьевич

Алгоритм распознавания выполнимости формул логики ветвящегося времени и его применениеХелемендик Роман Викторович

Рекуррентные алгоритмы обучения и самообучения в теории распознавания образовИзмакова Ольга Анатольевна

Построение базиса на множестве алгоритмов, основанных на гиперплоскостях, для произвольной задачи распознаванияЛысёнок, Евгений Игоревич

Эффективные алгоритмы, основанные на вычислении оценок, с прямоугольными опорными множествами, для задач распознавания изображенийНефёдов Алексей Валентинович

Алгоритмы вычисления оценок со сложными системами опорных множеств и их замыкания Исраилов Илхом Мирхаликович

Полиномиальные алгоритмы распознавания изоморфизма в некоторых классах графов Расин Олег Вениаминович

Алгоритмы распознавания движущихся целей в просветной радиофизической системеПолозова, Оксана Викторовна