Комитетные конструкции в многоклассовых задачах распознавания образов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ

ГЛАВА I. МОДЕЛИ КОММТЕТНЫХ КОНСТРУКЦИЙ И ТЕОРЕМЫ

СУЩЕСТВОВАНИЯ

§ I.I. Постановка задачи дискриминантного анализа распознавания образов

§ 1.2. Линейные алгоритмы распознавания

§ 1*3. Комитетные конструкции

§ 1.4. Теоремы существования комитета большинства, не делающего ошибок на обучающей информации

§ 1.5. Теорема существования комитета старшинства, правильно классифицирующего объекты обучающей информации

ГЛАВА 2. АЛГОРИТМЫ ПОСТРОЕНИЯ КОМИТЕТОВ

§ 2.1. Алгоритм построения комитета большинства

§ 2.2. Алгоритм построения комитета старшинства

ГЛАВА 3. ВОПРОСЫ ПРИМЕНЕНИЯ КОМИТЕТНЫХ КОНСТРУКЦИЙ

§ ЗЛ. Комитетные конструкции для двухклассовых задач дискриминантного анализа

§ 3.2. Задача разделения фигур в R , образованных гиперплоскостями

§ 3.3. Вычисление геометрических предикатов

ГЛАВА 4. ЗАДАЧА КОРРЕКЦИИ ПАРАМЕТРОВ ОБЪЕКТА В

РАСПОЗНАВАНИИ ОБРАЗОВ

§ 4.1. Решение задачи дискриминантного анализа

§ 4.2. Формулировка задачи коррекции параметров объекта и ее цреобразование

§ 4.3. Решение полученной задачи выцуклого программирования методом фейеровских отображений

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

4 . '|f *

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

Задача распознавания объектов в общем виде есть задача классификации объектов любой природы»

В предлагаемой работе рассматривается задача дискриминантно-го анализа распознавания образов в следующей общей постановке, предложенной Ю. И «Журавлевым [l8]«

Пусть заданы множества допустимых объектов { S } и описаний допустимых объектов

Предположим, что существует покрытие множества |S г подмно

С* жествами К , . К I ^ 1 > классов объектов, и задана I обучающая информация JD о классах К ,. ,К\

Требуется построить алгоритм, вычисляющий для произвольного допустимого объекта о значения предикатов P-CS) =

-.se^; л cs) б {on,л], j = v., i. с

Для решения поставленной задачи при различных ограничениях накладываемых на множество ^CS)J и покрытие множества {$} классами К 4 5 . . . 7 К , предложено большое число методов (см. [I, 10, 16, 20, 31, 40, 43, 54] и др.),

В большинстве случаев авторы рассматривают двухклассовые задачи с непересекающимися классами, когда множество описаний объектов содержится в R и заданы конечные подмножества А ^ и А описаний объектов из классов К и К .Из многоклассовых задач распознавания образов, как правило, рассматривают также задачи с непересекающийся классами и сводят их решение к решению двухклассовых задач, что не всегда эффективно» При этом отыскивается дискриминантная функция { над пространством R , разделяющая множества и А^ , т.е. удовлетворяющая соотношению

•• a G Ajn {4(a) : а € Аг] - 0.

Наиболее важным классом дискриминантных функций является класс линейных функций. В этом случае нахождение дискриминантной функции сводится к решению системы линейных неравенств иг, а) > о v GL в А , иг, а j < о V а 6 А^, у^ где , у ) - скалярное произведение векторов X , ij б К .

Применение линейных функций для решения поставленной задачи дискриминантного анализа в рамках проблемы распознавания образов впервые рассматривалось Ф.Розенблаттом [47], который сделал попытку технически реализовать физиологическую модель восприятия. Техническую модель Ф.Розенблатт назвал персептроном и предложил алгоритм его обучения (построения разделяющей гиперплоскости) методом поощрения и наказания. Интересным является тот факт, что теорема о сходимости процесса обучения персептрона и ее доказательство существовали в математическом смысле до появления персептрона в идее решения систем линейных неравенств релаксационным методом [59].

Для разделения двух линейно неразделимых множеств употребляют различные кусочно-линейные функции (см. [l0, 16, 18, 22, 40, 43] и др.)* С помощью кусочно-линейных функций можно разделить любые два конечных непересекающихся множества [40].

Особое место среди кусочно-линейных функций занимают коми-тетные функции [l6, 40, 43, 54, 58, 62, 63].

Понятие комитета решений для несовместной системы однородных строгих линейных неравенств над пространством R было введено в 1965 году Д.Ней лором и С.Эйблоу [58].

Комитетом системы линейных неравенств

Gj , V) > 0 , j ^ 1, па, (0.1) где Я- } if S R называется такое конечное множество V -~ ("\Г . яГ г С R » ЧТО каждому ее неравенству удовлетворя

С. \ У 4 % ' ) (if J ет более половины элементов множества V «

Комитет системы линейных неравенств является обобщением понятия решения системы линейных неравенств.

В работах Вл.Д.Мазурова, А.И.Кривоногова и др. теория метода комитетов получила широкое развитие, так, были доказаны необходимые и достаточные условия существования комитета для различных классов систем неравенств; введены другие комитетные конструкции: разделяющий комитет функционалов, комитет системы множеств, 2 -решение, р -комитет, коллективное решение; а также разработаны и обоснованы методы построения комитетных конструкций (см. [16, 26-30, 33, 36, 37, 40, 53] и др.).

Метод свертывания для систем линейных неравенств, разработайный С.Н.Черниковым [55, 5б], позволяет решать проблему нахождения минимального комитета [l6, 30, 40].

Среди алгоритмов построения комитета следует выделить, как наиболее эффективный, алгоритм, использующий понижение размерности, т.е. отображение векторов множества A^W ^ в R и построение минимального комитета системы линейных неравенств над пространством R [ 16, 26, 40, 52].

Н.Нильсон предложил [43] следующий алгоритм построения комитета системы линейных неравенств.

Пусть задано обучающее множество а h •= A V {-а : а € А,}, причем А - [v., а J , а^ (ftCl,.,Vi> 1

Составим из точек множества А обучающую последовательность а • i- 1 i ] ~ а а (Я а q

Пусть О ) , • • • , ^ (^ ) - произвольные векторы из R , > 1 - некоторое целое число. уже постро

Если \Г, (fc), - ■ • , & > 1 ены, то вычисляем

N = Z. iqn, (ir.(*J,afe), i I где

I, если X > 0 , 0 '-I, если X ^ 0

Если > 0 .то ir (b-i) - гг-CtJ, j = 1,.,

Если ^^ ^ , то вычисляем

-V \ , если -четное;

INlI -V- 1 I М I 1 , если -нечетное; и шбираем Q^ векторов из совокупности (&),. имеющих наименьшие величины I > ^ |) I » где

Л^) ^ 0 ? j, € 1,^ . Корректируем выбранные векторы относительно , т.е. полагаем для них r(i) +

Г <> оставляя остальные векторы без изменения*

Этот метод не всегда приводит к нахождению комитета ^43, 6о]< Некоторые условия, при которых алгоритм сходится, приведены в [26]. Неудобством его использования является и то, что нужное число ^ неизвестно,

В 1977 году М.Осборн [бй] вводит новый тип комитетов - комитеты старшинства, и предлагает алгоритм локальной коррекции их построения, рассчитанный на задачи с обучающим множеством, составленным из бинарных векторов.

Комитетом старшинства называется упорядоченная совокупность векторов ^ , . . • , ЯГ^ R , где калдаый вектор имеет ранг Г(тГ.) ^ и и тип "Ц^) 6 [l,l] , i е Vfy.

При классификации точки d вектор , и 'I , Оу » го типа голосует за 1-ый класс, если

К- , а.) > 0 . и воздерживается в противном случае, а вектор Г } j 2-го типа голосует за второй класс, если

Т-,<х) < О, и воздерживается в противном случае. Если все векторы воздержались, то комитет относит точку <Х ко второму классу; в противном случае решающее значение имеет голос вектора с наибольшим рангом.

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

Пусть &(TfJ, S(-o-) £ S - возраст вектора ТГ , где

- параметр алгоритма, $ R Коррекцией вектора ТГ в ответ на вектор обучающего множества Cl называется изменение

8 or J : = S(v)fi, JT

- llirlt ' где Jb - параметр алгоритма, Jb > 0 , п Г X, если (Г, cl) ^ 0 , з- (а) = ч -I, если (ТГ, а J > 0.

Вектор тГ называется корректоспособным в ответ на вектор Cl , если изменение его отклика на & изменяет отклик комитета на Cl.

Сопротивлением вектора 1Г на векторе CL называется число, равное

Serb g) , где ^ ^ - - параметр алгоритма»

Алгоритм. Пусть S > 0 , р > О и ^ ^ ~ о - параметры алгоритма.

Начальное приближение комитета старшинства состоит из члена 1ГЛ - (О, . . , 0, -1) типа KlTj-l.

Пусть построено приближение ЧГ^ , . ., ТГ^ , ^ ^ 1.

Формируем обучающую последовательность из обучающего множества А : а- \ и и, каждый раз, когда вектор <Х из обучающей последовательности классифицируется неверно, корректируем вектор, корректоепособный в ответ на & , с наименьшим сопротивлением, или вводим в приближение новый вектор и корректируем его. Новый вектор вводится, если вектор, корректоспособный в ответ на Oi , с наименьшим сопротивлением, имеет сопротивление на векторе (X, большее, чем ^ + У • Вводится новый вектор 1-го типа - (0,. .,

0,-1) , если (X. G АЛ , и второго типа •• >0, 1 ^ если (Я А

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

Р.Такияма [бз] предложил использовать вместо дискриминантной функции, задаваемой произвольным комитетом dCxJ - >) i-1 где V,, . . . , \)G , 4 G R » дискриминантную функцию следующе

1 1 у + 1 го вида о(,(х, W) = W Т (х, W) х , где W = (1АГ, .,vT ) € R", N = X = (х,.,

X) € S>\ X €

I -цсх.й-^Е* о . о \

Т (х, W) - . Г h - единичная матрица порядка ^ ,

I, если (1аГ. , х) > 0 и с((х) > О, и или (ЯлГ , х) 4 о И 4 О,

О-в противном случае. Пусть обучающее множество А равно

А-- ^{-и: гб AJ.

Задача обучения комитета состоит в определении вектора

W € R t.fx тлГ) =

1 V N ot [а,\Д/; > о V а € А.

Предлагается следующий алгоритм обучения. Выбираем в качестве начального приближения произвольный N -мерный вектор W (1) .

Составим из точек обучающего множества А обучающую последовательность •

Пусть построено приближение \Д/ (t) и предъявляется точка (л^ обучающей последовательности. Тогда

Я если d^a W(i)) > О,

Xa^wfl)) at , если W(%o если ■ R- ' К

Этот алгоритм, как и алгоритм Н.Нильсона, требует установлена в начале процесса обучения числа векторов ^ • Здесь необходимо также выбирать начальное приближение W(1J , т,к. приближение W (1) - 9 - (0,. т 0) не подходит ввиду того, что в результате работы алгоритма всегда получаются одинаковые векторы \А/J, . ? » т.е. д/(4) - - W (I) V А > 1.

М.Минский и С.Пейперт [42] подробно исследовали ряд вопросов, связанных с потенциальными возможностями персептронов, как практических устройств для распознавания образов и обучения. Была выявлена принципиальная возможность (или невозможность) вычисления конкретных свойств объектов с помощью персептронов, проведены оценки требуемого объема персептрона и диапазона значений коэффициентов персептрона.

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

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

Рассмотрена также задача коррекции параметров объекта в распознавании образов и указан путь ее решения. Задача сведена к серии задач выцуклого программирования, в их решении используется разработанный и исследованный И «И .Ереминым метод фейеровских отображений [l3, 1б].

Остановимся на содержании диссертационной работы более подробно.

Работа состоит из четырех глав.

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

Пусть заданы множества допустимых объектов S } и описаний , допустимых объектов {tt.CS)} С R , Я ^ 1 , существует покрытие множества {. S } классами К,-., К } i Z i

S} - yj к*.

Задана стандартная обучающая информация Jp , состоящая из описаний ft-CSJ, . . ? ^^ ) и информационных векторов us,),., dcsj

W^UCS,);.; aCSJ,iCSm)}, где о(S-) - значение предиката P-CS.) - S. £ ^ ,

0 i 1 1

I € 1,m. ; j €

Требуется построить алгоритм L , вычисляющий для & [cxCS)} информационные векторы

CCyD,a(SJ) = olCSj.

Вводится следующее понятие линейного алгоритма распознавания ♦

Пусть тг£ Ra, тГ^е R, 16 1,1.

Определение 0.1. Алгоритм С , вычисляющий для описания информационный вектор по правилу

А (S) = Г 1,если №a(s))+ ^ i I 0 - в противном случае, d (S) = Ь V , j 6U о

5 » называется линейным алгоритмом распознавания типа "t(C) - i с весовым вектором ЩС) - (тГ; Г ) е

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

Так, определения комитетов большинства и старшинства следующие.

Выделим из множества £ С ^ , . . , С ^ "]• алгоритмы типа I,

I a • teg

Пусть алгоритм С^ , (Л £ , вычисляет для объекта

S информационный вектор

Определение 0,2. Комитетом большинства, составленным из линейных алгоритмов Ct , . . . 5 С^ назовем алгоритм, вычисляющий для объекта S информационный вектор

KS) - 4 ft)) по правилу

- мо

I, если > cUSM - cecu 0 — в противном случае, где {j*1} - целая часть числа X t ^ ^ I X щность (количество элементов) множества X •

Предположим, что каждому алгоритму С } U в поставлено в соответствие число f С С ) , называемое рангом алгоритма: r(C.) s r(C.) V ;> i ;

Г." J если Г(С.) = Г (с.), то tec.) * -tec ) ; u,j 6 Ц-.

Пусть г ):d (S,C ) = ei.i}, mivv 1 u </ ^ "

J U. > u ^

Определение 0*3, Комитетом старшинства, составленным из алгоритмов С1 , . . . , С , назовем алгоритм, вычисляющий «л (5) по правилу

SJ = (, i € ItCS), oJ-QS) = 0, j e 1Л \ ItCs)

Для задачи дис1фиминантного анализа с обучающей информацией J0 , удовлетворяющей условиям

G {0,1}, 1£ U ; j € V^, справедлива следующая теорема существования комитетов большинства и старшинства.

Теорема 0,1. Для задачи с обучающей информацией, удовлетворяющей условиям (0.2), существуют комитет большинства и комитет старшинства, безошибочно вычисляющие информационные векторы для объектов из обучающей информации.

Отдельно рассматривается теорема существования комитета большинства для обучающей информации, описания объектов которой имеют расположение общего типа.

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

Решение задачи дискриминантного анализа при произвольной обучающей информации JQ с помощью комитетов большинства сведено к решению L задач с двумя непересекающимися классами объектов.

Для их решения предложен следующий алгоритм, использующий идеи алгоритмов Н.Нильсона построения комитета большинства и М. Осборна построения комитета старшинства.

Вводится дополнительная терминология.

Вектор W называется корректируемым в ответ на вектор 6 , если сопротивление таГ на 6 меньше некоторого параметра алгоритма i ^ О . о

Коррекцией вектора 1С относительно ь будем называть изменение Ь

1лГ •• -иг * 6, Scur)

S(vt) ■ = £(уг) -v 1 .

Определим обучающее множество В , получаемое из двух непересекающихся множеств В> и В , которые необходимо разделить:

В - В1 U {-Ь : i 6 В J , IBI - гп.

В качестве начального приближения решения задачи возьмем вектор

Ч = © , SCWJ = ? .

Допустим, что построено приближение комитета большинства \Д/ - ^ял^ тлГ^ } , ^ ^ 1 , и предъявляется точка

-6. U 1 , обучающей последовательности, составленной из точек множества В .

Вводятся обозначения:

V/Д) - {tf G W : >0,^4,}, W \

Если ft - |W(«.)l \ |W Сбл| < 0 , т U то приближение не изменяется, если fe. > 0 , то изменяем приближение следующим образом.

Из W ) выделяем подмножество векторов, корректируемых в ответ на о- • и

Если то выбираем из W ) \Х+Ч векторов с минимальными сопротивлениями на ^ » и корректируем их относительно . Если {Ь1 ь то корректируем относительно все векторы и вводим

И = & - Z\W+1 векторов VT , в приближение: иг - б bfvJ:.)=S j - 1.и г -=9 S(ur .) = & 1 - 1, и корректируем их относительно

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

Содержание пункта 2,1,3 состоит в доказательстве того факта, что в случае линейно разделимых множеств В1 и В^ , при определенном выборе параметров алгоритма & , f> , X и 3 ал

0 J V mqx горитм сходится, т.е. находит разделяющую гиперплоскость. Для иллюстрации алгоритма приведен пример его работы. Предлагаемый алгоритм выгодно отличается от алгоритма линейной коррекции Н.Нильсона тем обстоятельством, что не требует задания числа ; легко проверить, что он не зацикливается в случае, приведенном в [43]. Он также не имеет недостатков алгоритма Р,Такиямы.

Для решения задачи дискриминантного анализа с помощью комитетов старшинства предложен следующий алгоритм, использующий идеи алгоритма М,0сборна.

Снова введем изменения в терминологию,

Коррекцией линейного алгоритма L с весовым вектором ллГСС) относительно вектора Cl называется изменение

ЩС) : = W-(C) + &(С,а) а ,

S(W(C)):= S(taTCC)) нгде Q (С, О.) G {-1,1 }. Пусть

А -{*„■■ > ИМ V | > i, ; i. j е (ръ,

А1 = (a.€A :

Составим из точек множества А обучающую последовательность • ь ~ 1, ^, - - • ] . мы

В качестве начального приближения возьмем линейные алгоритс с • s > • - • > ч •

VT(C.)< (^HK^f), tcc.)N> гЧС.)= 1, S(iat(C.J) - , j - 1,., t.

Доцустим, что построено приближение Ct, . . t C^ s ^ > \ } и предъявляется точка , L ^ 1 , обучающей последовательноo " сти.

Пусть

А^ф^а;*-!,.,*.; 4.61Л

Если S- классифицируется приближением верно, то приближе0 ние не изменяется.

Если S.' классифицируется неверно, то возможны следующие Q случаи,

I. В приближении имеется набор D из I алгоритмов одинакового ранга rCD) , голосующих за , если тип алгоритма о содержится в множестве или голосующих против , если тип алгоритма не из I (j) ; или корректируемых в ответ на Ct- , а все алгоритмы с меньшим с рангом, голосующие за <х- , корректируемы в ответ на cld ® В этом случае корректируем приближение.

Корректируем относительно (Х- при алгоритмы набора Т) типов из I (j) , голосующие против (Х^ *

Корректируем относительно О, • при С (С , ) - w1 алгоt * ритмы Ъ типов, не содержащихся в 1 С j) , голосующие за CL .

Корректируем относительно цри ссс , Q •) ~ -1 алг т\ \ ® горитмы приближения ранга меньшего Г и ) , голосующие за . о

2, Приближение не содержит набора D , удовлетворяющего условиям из 1-го случая, и все алгоритмы приближения, голосующие за , корректируемы в ответ на С^ .

В этом случае корректируем относительно (Я - при С (С 5<Я-) -. с d

- - I все алгоритмы, голосующие за ft. л о

Если и.- имеет максимальную норму из всех точек обучающе-о то множества, для которых объекты, им соответствующие, классифицируются приближением неверно, и для которых также выполняются условия этого случая, то вводим в приближение алгоритмы С , с ■ ^ w'V1" ^(Sp.-ll^)!!1), t(C^J = U., 1, sCiatCC. )) = s, ne,

4 rncax 5 V 0' * где - максимальный ранг алгоритмов С1 , . . , ^ •

Корректируем относительно при Q (С , ci) - \ алгоритмы из набора 1 ,. . . , ^ + t типов из I ) •

3. В третьем случае приближение не содержит набора "D , удовлетворяющего условиям из случая I, и не все алгоритмы из приближения, голосующие за , корректируемы в ответ на (Хс о

В этом случае приближение не изменяется.

Условие конца процесса обучения такое же, как и в алгоритме построения комитета большинства. В результате также может быть получен "грубый комитет".

Показывается, что при определенном выборе параметров алгоритма всегда может быть построен комитет старшинства, правильно классифицирующий объекты обучающей информации, но число членов Cj, в нем равно I

Z. I A1

И завершает главу 2 пример работы алгоритма построения комитета старшинства,

В главе 3 находятся необходимые и достаточные условия для существования решения задачи дискриминантного анализа над R в классах комитетов с различными логиками и исследуется вопрос вычислимости геометрических предикатов с помощью комитетов*

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

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

Пусть в R. заданы гиперплоскости Г1 ,. , Г^ 9 X > 1, проходящие через точку G - (0,0) G R , и выделяющие в R 1Л конусов Q1 , . . . , Q^x

Определение 0,4. Фигурой F в R1 , образованной гипероскостями г., .г, , называется объединение Irrv, , Л m € ОдХ , конусов Q. . Q.

L v.

1 l-Yb mo.

F = U Qi is

Дополнением фигуры F называется фигура F :

F -tQ,,-.,^ XF

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

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

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

Пусть разбито на квадраты, Н - множество квадратов, I Н | - «г < + ^

Фигуре А ^г , нарисованной на плоскости, поставим в соответствие подмножество А С 2 , состоящее из квадратов, в которых содержатся точки из А ^ .

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

Отдельно рассматривается случай предиката ф (Д) f I» если I АI - нечетное число, четность )

-I - в противном случае•

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

Задача коррекции параметров объекта в распознавании образов рассмотрена в главе 4, доказана теорема о возможности ее решения с помощью предлагаемого метода.

Предположим, что задача дискриминантного анализа решена методом комитетов старшинства.

Задан объект^ Sq и указано, принадлежность к какому классу из К , . . , К желательна для него. На множестве описаний объектов (cl(S)} задана метрика. Требуется так минимально изменить описание )» чтобы построенный алгоритм комитета старшинства относил объект с измененным описанием к нужному классу.

Эта задача сводится, в общем случае, к нескольким задачам выпуклого программирования, для решения которых применяется метод фейеровских отображений [l3, 1б].

Результаты, содержащиеся в работе, являются новыми. Эти результаты докладывались на Региональных конференциях "Методы математического программирования и их программное обеспечение" (г. Свердловск, 1981 и 1984 г,г,) [4, б], на Всесоюзной конференции "Математические метода распознавания образов" (г.Москва, 1983г.), на Республиканском семинаре "Распознающие и информационно-распознающие системы" (г,Киев, 1983 г.), а также на семинарах отделов математического программирования и исследования операций Института математики и механики УНЦ АН СССР,

Результаты исследований опубликованы в работах ^3-8, 32, 34, 4l]. Эти результаты были использованы цри разработке пакета прикладных программ по прогнозированию на базе стандартных методов распознавания образов "Квазар-ЕС", созданного в отделе исследования операций Института математики и механики УНЦ АН СССР по заказу Госкомитета по науке и технике. Пакет "Квазар-ЕС" сдан в Государственный фоцд алгоритмов и программ и используется в ряде организаций Москвы, Перми, Ташкента, Челябинска, Свердловска и других городов страны. С помощью описываемых комитетных конструкций автором были решены задачи Института биофизики МЗ СССР дифференциальной диагностики по биохимическим данным болезней печени, легких и желудка (см. приложение I),

1. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. - М.: Наука, 1970. -384 с.

2. Белецкий Н.Г. Об одном методе оптимизации, использующем распознавание образов. В кн.: Динамическое управление: Всесоюз. конф. г.Свердловск, 30 мая - I июня 1979 г. Тез.докл. Свердловск: УНЦ АН СССР, 1979, с.33-35.

3. Белецкий Н.Г. 0 коррекции параметров объекта в распознавании образов. В кн.: Применение математических методов в решении медицинских задач, Свердловск, ИММ УНЦ АН СССР, 1983, с. 49-50.

4. Белецкий Н.Г, Об алгоритме построения комитета системы линейных неравенств. В кн.: Метода математического программирования и их программное обеспечение: Per.конф, г.Свердловск, 1618 мая 1984 г. Тез. докл. Свердловск, 1984, с.25-26.

5. Белецкий Н.Г. Об одном итерационном методе кусочно-линейной дискриминации. В кн.: Классификация и оптимизация в задачах управления. Сверцловск: УНЦ АН СССР, 1981, с.64-66.

6. Белецкий Н.Г. Применение комитетов для многоклассовой классификации, В кн.: Методы мат.программирования и их програм. обеспечение: Per,конф. г.Свердловск, 14-16 апреля 1981 г. Тез. докл, Свердловск, 1981, с.18-19.

7. Белецкий Н.Г. Применение комитетов для многоклассовой классификации. В кн.: Численный анализ решения задач линейного и выпуклого программирования. Свердловск: УНЦ АН СССР, 1983,с.156-162.

8. Белецкий Н.Г. Разделяющие возможности комитетов с различными логиками. Свердловск: АН СССР УНЦ ИММ, 1984. - 23 с.Рукопись деп. в ВИНИТИ 30.07.84, № 5507-84.

9. Бонгард М.М. Проблема узнавания. М.: Наука, 1967. -320 с.

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

11. Данилов В.И. Модели группового выбора: Обзор. Изв. АН СССР. Техн. кибернетика, № I, 1983, с.143-164.

12. Дуда Р., Харт П. Распознавание образов и анализ сцен.-М.: Мир, 1976. 512 с.

13. Еремин И .И. 0 фейеровских процессах применительно к задачам выпуклого программирования. В кн.: Метода выпуклого программирования и приложения. Свердловск: УНЦ АН СССР, 1973, с.47-52.

14. Еремин И.И., Мазуров Вл.Д. Вопросы оптимизации и распознавания образов: Метод.пособие. Свердловск: ИММ УНЦ АН СССР, 1979. - 64 с.

15. Еремин И,И., Мазуров Вл.Д. Итерационный метод обучения дискриминации бесконечных множеств. Кибернетика, 1977, № 5,с.108-110.

16. Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979. - 288 с.

17. Журавлев Ю.И. Непараметрические задачи распознавания образов. Кибернетика, 1976, № 6, с.93-103.

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

19. Журавлев Ю.И., Дмитриев А.Н., Кренделев Ф.П. О математических принципах классификации предметов и явлений. В кн.: Дискретный анализ. Новосибирск: ИМ СО АН СССР, 1966, № 7, с.3-17.

20. Журавлев Ю.И., Камилов М.М., Туляганов Ш.Е. Алгоритмывычисления оценок и их применение. Ташкент: ФАН, 1974. - 119 с.

21. Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок. Кибернетика, 1971, № 3, с. 1-Й,

22. Кашкевич С,И., Краснопрошин В.В. Двухуровневый автоматизированный распознающий комплекс. Журн. вычисл.математики и мат.физики, 1979, т.19, № б, с.1577-1587.

23. Краснопрошин В.В. Об оптимальном корректоре совокупности алгоритмов распознавания* Журн. вычисл. математики и мат. физики, 1979, т.19, № I, с.204-215.

24. Кривоногов А.И. Некоторые модификации комитетных алгоритмов в распознавании образов. В кн.: Метода мат.программирования и приложения. Свердловск: ИММ УНЦ АН СССР, 1979, вып.27, с.49-55.

25. Кривоногов А.И, Условия существования комитета неоднородной системы неравенств и приложения. Мат.зап./УрГУ им.A.M. Горького, 1979, вып. 5, с, 89-94.

26. Кривоногов А.И, Исключение неизвестных в методе комитетов. В кн.: Метода мат,программирования и их црограм. обеспечение, Рег.конф. г.Свердловск, 14-16 апреля 1981 г. Тез.докл. Свердловск, 1981, с.78,

27. Кривоногов А.И. Некоторые вопросы обоснования комитетных алгоритмов. В кн.: Классификация и оптимизация в задачахуправления. Свердловск: УНЦ АН СССР, 1981, с.39-51.

28. Кривоногов А.И, Об использовании метода свертывания для построения комитета системы линейных неравенств. Свердловск:АН СССР УНЦ ИМ, 1982. 70 с. - Рукопись деп. в ВИНИТИ 17.01.82, № 268-83.

29. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. Новосибирск: Наука, Сиб.отделение, 1981. - 160 с.

30. Мазуров Вл.Д., Кривоногов А.И,, Казанцев B.C., Сачков Н.О,, Белецкий Н.Г. Комитеты в принятии решений. Кибернетика, 1984, № I, с.90-96.

31. Мазуров Вл.Д. О построении комитета системы выпуклых неравенств. Кибернетика, 1967, № 2, с,56-59.

32. Мазуров Вл.Д., Казанцев B.C., Белецкий Н.Г. Пакет КВАЗАР как средство решения задач классификации. В кн.: Структура и организация пакетов прикладных программ. Свердловск: ИММ УНЦ АН СССР, 1983, с.33-52.

33. Мазуров Вл.Д. Распознавание образов как средство автоматического выбора проще,цуры в вычислительных методах. Журн. вычисл. математики и мат.физики, 1970, т.Ю, № 6, с.1520-1525.

34. Мазуров Вл.Д. Комитеты систем неравенств и задача распознавания. Кибернетика, 197I, № 3, с.140-146.

35. Мазуров Вл.Д. Теория и приложения комитетных конструкций. В кн.: Методы для нестационарных задач мат.программирования. Свердловск: ИММ УНЦ АН СССР, 1979, вып. 29, с.31-63.

36. Мазуров Вл.Д. Метод допустимых коррекций. В кн.: Несобственные задачи оптимизации. Свердловск: УНЦ АН СССР, 1982, с. 11-22.

37. МакухiH О.Г. Про лшшну розд1льн1сть реакцШ систем л'ш1йних нер1вностей. Доп. АН УРСР, сер. А, 1968, № 5,с.406-411.

38. Метод комитетов в распознавании образов: Сб.науч.тр. /АН СССР, УЩ. Ин-т математики и механики. Свердловск, 1974, -вып.6, - 165 с.

39. Минский M., Пейперт С. Персептроны, M.: Мир, 1971. -261 с.

40. Нильсон Н. Обучающиеся машины. М.: Мир, 1967. - 180 с.

41. Пакет КВАЗАР прикладных программ распознавания образов (версия 2): (Информ.материалы по мат.обеспечению ЭВМ) /Вл.Д.Мазуров, В.С.Казанцев, Н.Г.Белецкий, С.В.Мезенцев, Н.О.Сачков. -Свердловск: шм УНЦ АН СССР, 1979. 121 с.

42. Ползик Е.В., Белецкий Н.Г. 0 комплексе мер, направленных на продление трудовой деятельности горнорабочих медных рудников. Здравоохранение РШСР, 1980, № 3, с.27-29.

43. Растригин JI.A., Эренштейн Р.Х. Метод коллективного распознавания. М.: Энергоиздат, 1981, - 80 с.

44. Розенблатт Ф. Принципы нейродинамики. М.: Мир, 1965.480 с.

45. Рудаков К.В. 0 числе гиперплоскостей, разделяющих конечные множества в евклидовом пространстве. Докл. АН СССР, 1976, т.231, № 6, с.1296-1299.

46. Сачков Н.0. Решение смешанных систем неравенств. В кн.: Методы оптимизации и распознавания образов в задачах планирования. Свердловск: УНЦ АН СССР, 1980, с.99-105.

47. Ту Дж., Гонсалес Р. Принципы распознавания образов.М.: Мир, 1978. 412 с.

48. Тягунов Л,И. Программа построения комитета для задачи распознавания образов. В кн.: Программы оптимизации, Свердловск: ИЫМ УНЦ АН СССР, 1969, вып.1, с.84-101.

49. Тягунов Л.И. Алгоритмы комитетного распознавания и их применение для решения практических задач классификации: Автореф. дисс. . канд.техн.наук. 05.13.01. Свердловск: УПИ им.С.М.Кирова, 1973. - 24 с.

50. Тягунов Л.И., Карапетян Э.Г., Мирзоев Р.Г. Управление качеством промышленных изделий. Л.: Изд-во Ленингр. ун-та,1977. 120 с.

51. Фомин В.Н. Математическая теория обучаемых опознающих систем» Л.: ЛГУ, 1976. - 236 с.

52. Черников С.Н. Линейные неравенства. М.:Наука, 1968. -488 с.

53. Черников С.Н. Свертывание конечных систем линейных неравенств. Доповзд! АН УРСР, сер. А, 1969, № I, с.32-35.

54. Шилов Г.Е. Математический анализ (конечномерные линейные пространства). М.: Наука, 1969. - 432 с,

55. Ablow С.М., Kaylor D.J. Inconsistent homogeneous linear inequalities.- Bull. Amer. Math. Soc., 1965, vol.71, no.5, p.724.

56. Agmon S. The relaxation method for linear inequalities.- Canad. J. Math., 1954, vol.6, no.3, p.382-392.

57. Blaha S. The convergence of a committee solution of the Pattern Recognition Problem.- Kybernetika (Praha), 1969, vol.6, no.5, p.474-483.

58. Camba A., Cambertini L., Palmieri G., Sanna R. Further experiments with PAPA.- Nuovo Cimento Suppl., 1961, vol.20,no.2, p.112-115.

59. Osborne M.L. The seniority Logic a Logic for a committee machine.- IEEE Trans. Comput., 1977, vol.C-26, no.12, p.1302-1306.

60. Takiyama R. A general method for training the com-mitee machine.- Pattern Recogn., 1978, vol.10, no.4> p.255-259.УТВЕВДАЮЗаведующий филиалом № I ордена Ленина института Биофизики МЗ СССР канц.мед.науквХлжерг "14 " II. 1983 г.