Содержание к диссертации
Введение
ГЛАВА I. Модели комитетшх конструкций и теореш существования 25
1.1« Постановка задачи дискриминантного анализа распознавания образов 25
1.2. Линейные алгоритмы распознавания 27
1.3. Комитетные конструкции 28
1.4. Теоремы существования комитета большинства, не делающего ошибок на обучающей информации 32
1.5. Теорема существования комитета старшинства, правильно классифицирующего объекты обучающей информации 41
ГЛАВА 2. Алгоритм построения комитетов 45
2.1. Алгоритм построения комитета большинства 45
2.2. Алгоритм построения комитета старшинства 62
ГЛАВА 3. Вопросы применения комитетшх конструкций 75
3.1. Комитетные конструкции для двухклассовых задач дискриминантного анализа 75
3.2. Задача разделения фигур в к , образованных гиперплоскостями 83
3.3. Вычисление геометрических предикатов 97
ГЛАВА 4. Задача коррекции параметров объекта в распознавании образов 106
4.1. Решение задачи дискриминантного анализа 107
4.2. Формулировка задачи коррекции параметров объекта и ее преобразование 109
4.3. Решение полученной задачи выпуклого программирования методом фейеровских отобра жений
Список литературы
- Линейные алгоритмы распознавания
- Алгоритм построения комитета старшинства
- Задача разделения фигур в к , образованных гиперплоскостями
- Формулировка задачи коррекции параметров объекта и ее преобразование
Введение к работе
Диссертация посвящена исследованию новых комитетных конструкций, позволяющих решать многоклассовые задачи дискриминантно-го анализа распознавания образов, разработке и обоснованию алгоритмов для их построения. В ней проводится сравнение разделяющих возможностей комитетных конструкций, а также решается задача управления параметрами объекта в распознавании образов.
Распознавание образов является одним из центральных разделов кибернетики. Задачи распознавания образов возникают в различных областях науки и техники, распознавание образов является одной из основных логических операций во многих задачах. Особое значение имеет применение методов распознавания образов для управления сложными неформализованными системами, которые характеризуются лишь некоторой эмпирической информацией.
Задача распознавания объектов в общем виде есть задача классификации объектов любой природы»
В предлагаемой работе рассматривается задача дискриминантно-го анализа распознавания образов в следующей общей постановке, предложенной Ю.ИДуравлевым [l8]«
Пусть заданы множества допустимых объектов \ Ь j и описаний допустимых объектов ^&(.Ь)(.
Предположим, что существует покрытие множества \_5 г подмно-жествами К,..., К , t ^ 1 классов объектов, и задана обучающая информация L о классах К , ... , К .
Требуется построить алгоритм, вычисляющий для произвольного допустимого объекта Ь значения предикатов
-,Se К*) .US) б {0,1, М- i = i,...,1.
Для решения поставленной задачи при различных ограничениях
5 накладываемых на множество \Q-v»S)j и покрытие множества l->j классами К , ...,К , предложено большое число методов (см. [I, 10, 16, 20, ЗІ, 40, 43, 54] и др.),
В большинстве случаев авторы рассматривают двухклассовые задачи с непересекающимися классами, когда множество описаний объектов содержится в К, и заданы конечные подмножества А и А описаний объектов из классов К и К .Из многоклассовых задач распознавания образов, как правило, рассматривают также задачи с непересекающимися классами и сводят их решение к решению двухклассовых задач, что не всегда эффективно» При этом отыскивается дискриминантная функция { над пространством К , разделяющая множества Ад и А^ , т.е. удовлетворяющая соотношению
Наиболее важным классом дискриминантных функций является класс линейных функций. В этом случае нахождение дискриминантной функции сводится к решению системы линейных неравенств
Г(иг а) > 0 V О. Є А ,
(иг, а) < о V а Є А^,
где (^ , Ч ) - скалярное произведение векторов X , U б R. . Применение линейных функций для решения поставленной задачи дискриминантного анализа в рамках проблемы распознавания образов впервые рассматривалось Ф.Розенблаттом [47J, который сделал попытку технически реализовать физиологическую модель восприятия. Техническую модель Ф.Розенблатт назвал персептроном и предложил алгоритм его обучения (построения разделяющей гиперплоскости) методом поощрения и наказания. Интересным является тот факт, что
теорема о сходимости процесса обучения персептрона и ее доказательство существовали в математическом смысле до появления персептрона в идее решения систем линейных неравенств релаксационным методом [59J.
Для разделения двух линейно неразделимых множеств употребляют различные кусочно-линейные функции (см. [l0, 16, 18, 22, 40, 43J и др.)« С помощью кусочно-линейных функций можно разделить любые два конечных непересекающихся множества [40].
Особое место среди кусочно-линейных функций занимают коми-тетные функции [16, 40, 43, 54, 58, 62, 63].
Понятие комитета решений для несовместной системы однородных строгих линейных неравенств над пространством К было введено в 1965 году Д.Кейлором и С.Эйблоу [58].
Комитетом системы линейных неравенств
(Oj, "О > 0 , j - 1, ...,m.f (O.i)
где Я- іГ Є гч «взывается такое конечное множество V -~ W< ... t С R что каждому ее неравенству удовлетворя-ет более половины элементов множества V «
Комитет системы линейных неравенств является обобщением понятия решения системы линейных неравенств.
В работах Вл.Д.Мазурова, А.И.Кривоногова и др» теория метода комитетов получила широкое развитие, так, были доказаны необходимые и достаточные условия существования комитета для различных классов систем неравенств; введены другие комитетные конструкции: разделяющий комитет функционалов, комитет системы множеств, 2 -решение, р -комитет, коллективное решение; а также разработаны и обоснованы методы построения комитетных конструкций (см. [іб, 26-30, 33, 36, 37, 40, 53] и др.).
Метод свертывания для систем линейных неравенств, разрабо-
тайный С.Н.Черниковым [55, 56J, позволяет решать проблему нахождения минимального комитета [іб, 30, 40J,
Среди алгоритмов построения комитета следует выделить, как наиболее эффективный, алгоритм, использующий понижение размерности, т.е* отображение векторов множества \^ \ в ^ и по~ строение минимального комитета системы линейных неравенств над пространством к [16, 26, 40, 52J
Н.Нильсон предложил [43 J следующий алгоритм построения комитета системы линейных неравенств*
Пусть задано обучающее множество
Ь - А V {-а-- а А^},
причем А^ К,...,^] , av= (^,...,^.,, О.
Составим из точек множества '"\ обучающую последователь-
ность
fa-i-11 1-а а (Я a q
Пусть ^0),---, ^q П ) - произвольные векторы из rs , 0L > 1 - некоторое целое число.
Если \Г; (t), . . . , in С 6.) , & > 1 .уже построены, то вычисляем
-\
. I, если X > 0 7
0 (-1, если X ^ 0 .
Если Nn > 0 .то
Если M я < 0 , то вычисляем
если I ^c і - четное;
если iN»i -нечетное;
Я. *
и выбираем Q« векторов из совокупности TXJ (к),. .., ^,(1), имеющих наименьшие величины K^-(t), ftt)| .їда ((4), &о) ^ 0 ? і 1,^ . Корректируем выбранные векторы относительно (Хо , т.е. полагаем для них
г(Ьі) = т. (і) + ай,
оставляя остальные векторы без изменения*
Этот метод не всегда приводит к нахождению комитета [43, 60J Некоторые условия, при которых алгоритм сходится, приведены в [26J. Неудобством его использования является и то, что нужное число Q, неизвестно,
В 1977 году М.Осборн [62J вводит новый тип комитетов - комитеты старшинства, и предлагает алгоритм локальной коррекции их построения, рассчитанный на задачи с обучающим множеством, составленным из бинарных векторов.
Комитетом старшинства называется упорядоченная совокупность векторов ^, . - , Т^о, r R , где каждый вектор "^ имеет ранг Р (тП ) = и и тип t(TTt) {1,1} , і Є l.cj,.
При классификации точки d вектор "17"- , ^ 6 ІЯ » I-го типа голосует за 1-ий класс, если
(.^, а) > о.
и воздерживается в противном случае, а вектор Г. } \ 1,0,, 2-го типа голосует за второй класс, если
[Т-, <х) < 0,
и воздерживается в противном случае. Если все векторы воздержались, то комитет относит точку <Х ко второму классу; в противном случае решающее значение имеет голос вектора с наибольшим рангом.
Алгоритм обучения комитета старшинства для обучающей информации, составленной из бинарных векторов, предлагаемый в [б2], описывается следующим образом.
Вводится терминология.
Пусть S (тг} , S (тГ/ ^ оо - возраст вектора IT , где о - параметр алгоритма, и <Е R .
Коррекцией вектора ТГ в ответ на вектор обучающего множества G- называется изменение
8 (у) = S (тг) + 1,
_ jr
т'' - ІІТГЦ' где Р> - параметр алгоритма, Ь > 0 ,
г Г I, если (т, а) ^ о ,
(з- (а) = ч
I -1, если
Вектор тГ называется корректоспособным в ответ на вектор <Х , если изменение его отклика на & изменяет отклик комитета на Ci.
Сопротивлением вектора 1Г на векторе CL называется число, равное
где У ^ - 0 - параметр алгоритма»
Алгоритм. Пусть S > О Ь > 0 и X ^ ~ о " параметры алгоритма.
Начальное приближение комитета старшинства состоит из члена 1Гп-= (0,...,0,-1) типа 1(^)-1.
Пусть построено приближение IT .. ., TL , Ч, ^ 1.
Формируем обучающую последовательность из обучающего множества А :
a- \v ^г,
и, каждый раз, когда вектор (л. из обучающей последовательности классифицируется неверно, корректируем вектор, корректоспособный в ответ на & , с наименьшим сопротивлением, или вводим в приближение новый вектор и корректируем его. Новый вектор вводится, если вектор, корректоспособный в ответ на Cl , с наименьшим сопротивлением, имеет сопротивление на векторе G, большее, чем ^ + У * Вводится новый вектор 1-го типа "^+1 - (0,.. ., 0,-1) , если (X. Є А , и второго типа "С = (0У... , 0,1)} если (Я Є А
Следовательно, стратегия строящегося комитета старшинства такова: векторы с малым рангом классифицируют большинство объектов, а векторы с высоким рангом классифицируют (отсекают) особые, изолированные точки, на которых члены с меньшим рангом делают ошибки*
Р.Такияма [63J предложил использовать вместо дискриминантной функции, задаваемой произвольным комитетом
где V,, . . . , vG ,. G R. , дискриминантную функцию следующе-го вида
о(,(х, W)= W T(x,W) X , где W = (таг, ..., «г j RN, N = ^, X = (х,...,
/-ЦСх.ідґ^Е* 0...0
T(-x,W) -
\ о... о ty^E"'
E - единичная матрица порядка ^ ,
і, если (іаГ. ,х)> 0 и с((х)> О,
t.(x,-uT) =
Г таг. , х) 4 о и ctfxj^ О,
О-в противном случае. Пусть обучающее множество Л равно
А- /\, W {-а : а AJ.
Задача обучения комитета состоит в определении вектора
W Є R
о(Да,\л/; > о V а А.
Предлагается следующий алгоритм обучения. Выбираем в качестве начального приближения произвольный N -мерный вектор W (1 J .
12 Составим из точек обучающего множества А обучающую последовательность
Пусть построено приближение \Д/ (v.) и предъявляется точка (ло обучающей последовательности. Тогда
О, если
Этот алгоритм, как и алгоритм Н*Нильсона, требует установлена в начале процесса обучения числа векторов fy- Здесь необходимо также выбирать начальное приближение W(1) , т.к. приближение W (1) - 0 - (0, -.. 7 0) не подходит ввиду того, что в результате работы алгоритма всегда получаются одинаковые векторы V\/(1J, ... 7 \ЛД(1] , т.е.
\A/(tj -... - W (і) V 4 > 1.
М.Минский и С.Пейперт [42J подробно исследовали ряд вопросов, связанных с потенциальными возможностями персептронов, как практических устройств для распознавания образов и обучения. Была выявлена принципиальная возможность (или невозможность) вычисления конкретных свойств объектов с помощью персептронов, проведены оценки требуемого объема персептрона и диапазона значений коэффициентов персептрона.
В предлагаемой работе рассматривается применение комитетных конструкций для многоклассовых задач дискриминантного анализа с пересекающимися классами, строятся и обосновываются алгоритмы построения комитетов большинства и старшинства для решения этих
задач»
В работе проведено сравнение разделяющих возможностей комитетов с различными логиками при решении задачи дискриминантного анализа над пространством «ч. и исследуется вопрос применения комитетов большинства для вычисления геометрических предикатов.
Рассмотрена также задача коррекции параметров объекта в распознавании образов и указан путь ее решения. Задача сведена к серии задач выцуклого программирования, в их решении используется разработанный и исследованный И«И.Ереминым метод фейеровских отображений [іЗ, 16j.
Остановимся на содержании диссертационной работы более подробно.
Работа состоит из четырех глав,
В главе I строятся модели комитетных конструкций для задач дискриминантного анализа распознавания образов в нижеследующей общей постановке, и доказываются теоремы существования комитетов большинства и старшинства, не делающих ошибок на обучающей информации*
Пусть заданы множества допустимых объектов \_ S j и описаний ,
допустимых объектов Н. ^> 1 * существует
покрытие множества {_ S} классами К,-.., К , v ^ 2,
і {S} - и к*, hi
Задана стандартная обучающая информация J , состоящая из описаний & CSt), .. . ? Gl CS ) и информационных векторов
KS,)...., oicsj
J.4^S1),A(S1);...;aCSJ,iCSm)},
где Ы- (S^j - значение предиката r-CS.) - UJ. ^ тч. ,
Требуется построить алгоритм С , вычисляющий для Q.KJ6 информационные векторы
CCj,,a(SJ) = oiCSj .
Вводится следующее понятие линейного алгоритма распознава-
ния*
п.
Пусть тгЄ R , тГиЄ R, 16 1,1.
Определение 0.1. Алгоритм С , вычисляющий для описания
<3-(SJ информационный вектор по правилу
Г і.если №a(S))+lN> О,
\, (^ 0 - в противном случае,
d (S) = Ь V j*u . j ей,
называется линейным алгоритмом распознавания типа "t^CJ - і с весовым вектором
Из совокупности С . .. , Сд , \/ ^> 1 , линейных алгоритмов строятся различные комитетные конструкции: комитеты единогласия, большинства, р -комитеты и комитеты старшинства»
Так, определения комитетов болыпинства и старшинства следующие*
Выделим из множества |_ С , . .. , ^ о } алгоритмы типа I,
Пусть алгоритм С ІА Є 1,0, , вычисляет для объекта S информационный вектор
dCS,Cj= (=l,CS,Cj,...,Jt(S,Cj).
Определение 0«2« Комитетом большинства, составленным из линейных алгоритмов С ... ,4 назовем алгоритм, вычисляющий для объекта Ь информационный вектор
«ВД - (c/,cs),...,eitcsj;
по правилу
I, если JL o^(S,C) > ^ —
cUSM - сєси
^ (_ 0 - в противном случае,
і= 1, ...,,
где V^- J - целая часть числа "X : к, "X -^" v ? \ X | -мощность (количество элементов) множества X
Предположим, что каждому алгоритму С } U Є 1,^L, поставлено в соответствие число f v ^ u) , называемое рангом алгоритма:
г(С.) s г>(С.) V j > і. ; Ч 1^,
если КС.) - г(С.) , то tCC) t(C.) ; u,i 1^.
1 і L- (І V
Пусть
Г (S) = mvti(r(C ) : ol (S, С J = 1, U q, і ЄЙ
I+(S)-{j Є1.Є = ^S,C)-Sr(CJ-riS),«e щ}.
Определение 0*3, Комитетом старшинства, составленным из алгоритмов С1 , . . . , Cq , назовем алгоритм, вычисляющий сі (5) по правилу
^(s;= (, іб it(s),
J-(S) = о, j vt \ it(S).
Для задачи дискриминантного анализа с обучающей информацией J0 , удовлетворяющей условиям
a^J^aCS.) V ^2 ; 4 *>> (0.2) ^CSp Є {0,1}, Lfel,t; І V^,
справедлива следующая теорема существования комитетов большинства и старшинства.
Теорема 0,1« Для задачи с обучающей информацией, удовлетворяющей условиям (0.2), существуют комитет большинства и комитет старшинства, безошибочно вычисляющие информационные векторы для объектов из обучающей информации.
Отдельно рассматривается теорема существования комитета большинства для обучающей информации, описания объектов которой имеют расположение общего типа.
Алгоритмы построения комитетов большинства и старшинства рассмотрены в главе 2. В главе проводится их обоснование; показано, что, при выполнении некоторых ограничений на количество линейных алгоритмов в комитете, предлагаемые алгоритмы строят комитеты, правильно классифицирующие обучающую информацию.
Решение задачи дискриминантного анализа при произвольной
обучающей информации ] с помощью комитетов большинства сведено к решению t задач с двумя непересекающимися классами объектов.
Для их решения предложен следующий алгоритм, использующий идеи алгоритмов Н.Нильсона построения комитета большинства и М. Осборна построения комитета старшинства.
Вводится дополнительная терминология.
Вектор W называется корректируемым в ответ на вектор
О , если сопротивление ТАГ на о меньше некоторого параметра
алгоритма і ^ О . мадс
Коррекцией вектора 1С относительно Ь будем называть из-
менение
В
Определим обучающее множество , получаемое из двух не
пересекающихся множеств , которые необходимо раз-
делить:
В - В, U {-Ь і Є В J , |В| - гп.
В качестве начального приближения решения задачи возьмем вектор
Допустим, что построено приближение комитета большинства \Д/ - { W уТ \ , Я, ^ 1 , и предъявляется точка Ь. V <> 1 , обучающей последовательности, составленной из точек множества О . Вводятся обозначения:
m\) - к w : о/г,\) > о, ^ є ц,},
Если
— V t U
то приближение не изменяется, если к > 0 , то изменяем приближение следующим образом,
из W(.) выделяем подмножество W (6.) векторов,
корректируемых в ответ на О- Если
ибираем из W №) \х+Ч векторов с минимальными сопро-
ТО B1
тивлениями на о. , и корректируем их относительно о. . Если
1^(«:)| < U-lb
'-л*-
то корректируем относительно 6 все векторы W_ (о.) и вводим И= І- ^|W,(&-)| +1 векторов 1^,..., УУ в приближение:
и корректируем их относительно 6- .
Процесс построения комитета большинства при данном ^глах заканчиваем, если после предъявления подряд ^ точек обучающей последовательности приближение не изменилось. При этом может быть построен комитет, делающий ошибки при классификации объектов обу-
чающей информации С"грубый" комитет).
Содержание пункта 2,1*3 состоит в доказательстве того факта, что в случае линейно разделимых множеств о и О , при определенном выборе параметров алгоритма о , р , У и 3 ал-горитм сходится, т,е, находит разделяющую гиперплоскость.
Для иллюстрации алгоритма приведен пример его работы*
Предлагаемый алгоритм выгодно отличается от алгоритма линейной коррекции Н*Нильсона тем обстоятельством, что не требует задания числа CL ; легко проверить, что он не зацикливается в случае, приведенном в [43J. Он также не имеет недостатков алгоритма Р.Такиямы.
Для решения задачи дискриминантного анализа с помощью комитетов старшинства предложен следующий алгоритм, использующий идеи алгоритма М,0сборна*
Снова введем изменения в терминологию»
Коррекцией линейного алгоритма С с весовым вектором ) относительно вектора & называется изменение
S(w(C)):= s^wcc;) + \t
где G(C,«.) Є {-1,1 }. Пусть
\<*&1); О, si'{s1,...,sm}, і^ія,
А^{а^А : cl^Sp-f.^l^i-U.e.
20 Составим из точек множества А обучающую последователь-
ность \<Х. ' І - 1,2,,...}.
В качестве начального приближения возьмем линейные алгоритмы С1 , ... , С^ :
Допустим, что построено приближение Ц , .. . > С„ t а> і , и предъявляется точка (Х- L ^ 1 , обучающей последовательно-сти.
Пусть
L.
Если S- классифицируется приближением верно, то приближе-d ниє не изменяется.
Если S. классифицируется неверно, то возможны следующие
о случаи,
I, В приближении имеется набор D из t алгоритмов одинакового ранга Г С D) , голосующих за & , если тип алгоритма
о содержится в множестве
или голосующих против <Я , если тип алгоритма не из 1 (i/ » или
корректируемых в ответ на О,- , а все алгоритмы с меньшим
с рангом, голосующие за <Х- , корректируемы в ответ на &
В этом случае корректируем приближение.
Корректируем относительно &j при алго-
ритмы набора Т) типов из I (j) , голосующие против (Х- * Корректируем относительно О, при (г (С , 3-) - -1 алго-
ритмы Ъ типов, не содержащихся в ^ (>) * голосующие за ft. .
Корректируем относительно ft; при G(C,q) "= -1 ал-
горитмы приближения ранга меньшего Г \ и ) , голосующие за О.. .
о 2, Приближение не содержит набора D , удовлетворяющего
условиям из 1-го случая, и все алгоритмы приближения, голосующие
за ft: , корректируемы в ответ на ftг .
В этом случае корректируем относительно ft- при & (С ^.)-- - І все алгоритмы, голосующие за ft-
Если ft- имеет максимальную норму из всех точек обучающе-
го множества, для которых объекты, им соответствующие, классифи
цируются приближением неверно, и для которых также выполняются
условия этого случая, то вводим в приближение алгоритмы С ,
.... Ctt: ^
где Г - максимальный ранг алгоритмов С1 , . .. , Ц, .
Корректируем относительно ft- при &- (С , <Я|) - t алгоритмы из набора Сд ,,..., (-<, « типов из I (i) .
3« В третьем случае приближение не содержит набора "D ,
удовлетворяющего условиям из случая I, и не все алгоритмы из
приближения, голосующие за ft- , корректируемы в ответ на ft-
о о
В этом случае приближение не изменяется.
Условие конца процесса обучения такое же, как и в алгоритме построения комитета большинства. В результате также может быть получен "грубый комитет*1.
Показывается, что при определенном выборе параметров алгоритма всегда может быть построен комитет старшинства, правильно классифицирующий объекты обучающей информации, но число членов О, в нем равно
<\-~ Z. I AM.
И завершает главу 2 пример работы алгоритма построения комитета старшинства,
В главе 3 находятся необходимые и достаточные условия для существования решения задачи дискриминантного анализа над R в классах комитетов с различными логиками и исследуется вопрос вычислимости геометрических предикатов с помощью комитетов*
Во введении главы 3 приводятся определения комитетов с различными логиками для двухклассовых задач дискриминантного анализа с непересекающимися классами и выписываются дискриминантные функции, задаваемые этими комитетами.
В первой части главы 3 проводится сравнение разделяющих возможностей комитетов при решении следующей задачи дискриминантного анализа.
Пусть в R. заданы гиперплоскости 1р...,^, л ^ л} проходящие через точку Ф - (0, 0) Є R, и выделяющие в R 2 А конусов Q1 , . . . , Q -і .
Определение 0.4« Фигурой F в R , образованной гиперплоскостями Г, . . . . , Г\ , называется объединение Yc\, , Па ОДХ , конусов Q. Q- :
Дополнением фигуры F называется фигура г :
Ставится задача отделения фигуры F от F с помощью ди-скриминантных функций, задаваемых комитетами с различными логиками. Находятся необходимые и достаточные условия для отделимости фигуры от дополнения для каждого класса комитетов, и приводится сравнение их разделяющих возможностей.
Оказывается, что при решении задач дискриминантного анализа такого рода разделяющая способность комитета с произвольной логикой не выше разделяющей способности комитетов большинства.
Во второй части главы 3 рассматривается задача вычисления с помощью комитетов большинства геометрических предикатов над следующим множеством фигур А на плоскости.
Пусть |< разбито на квадраты, Н - множество квадратов, I HI - іг < + <=^
Фигуре А г , нарисованной на плоскости, поставим в соответствие подмножество А С , состоящее из квадратов, в которых содержатся точки из А о .
Показано, что для любого геометрического предиката существует дискриминантная функция, задаваемая комитетом большинства, вычисляющая этот предикат, но количество линейных алгоритмов в комитете может достигать числа X - 1 .
Отдельно рассматривается случай предиката
ф -
четность
г д \ __ J I, если I А | - нечетное число, -I - в противном случае.
^.
В этом случае предикат вычисляется с помощью комитета большинства из К- линейных алгоритмов.
Задача коррекции параметров объекта в распознавании образов рассмотрена в главе 4, доказана теорема о возможности ее решения с помощью предлагаемого метода.
Предположим, что задача дискриминантного анализа решена
методом комитетов старшинства.
Задан объект о и указано, принадлежность к какому классу из к , . .. , К желательна для него. На множестве описаний объектов |ct(S)] задана метрика. Требуется так минимально изменить описание Cl(S> ), чтобы построенный алгоритм комитета старшинства относил объект с измененным описанием к нужному классу.
Эта задача сводится, в общем случае, к нескольким задачам выпуклого программирования, для решения которых применяется метод фейеровских отображений [13, 16].
Результаты, содержащиеся в работе, являются новыми. Эти результаты докладывались на Региональных конференциях "Методы математического программирования и их программное обеспечение" (г. Свердловск, 1981 и 1984 г.г.) [4, б], на Всесоюзной конференции "Математические метода распознавания образов" (г.Москва, 1983г.), на Республиканском семинаре "Распознающие и информационно-распознающие системы" (г.Киев, 1983 г.), а также на семинарах отделов математического программирования и исследования операций Института математики и механики УНЦ АН СССР,
Результаты исследований опубликованы в работах , 32, 34, 41J. Эти результаты были использованы при разработке пакета прикладных программ по прогнозированию на базе стандартных методов распознавания образов "Квазар-ЕС", созданного в отделе исследования операций Института математики и механики УНЦ АН СССР по заказу Госкомитета по науке и технике. Пакет "Квазар-ЕС" сдан в Государственный фонд алгоритмов и программ и используется в ряде организаций Москвы, Перми, Ташкента, Челябинска, Свердловска и других городов страны. С помощью описываемых комитетных конструкций автором были решены задачи Института биофизики МЗ СССР дифференциальной диагностики по биохимическим данным болезней печени, легких и желудка (см. приложение I).
Линейные алгоритмы распознавания
Построим алгоритм распознавания, относящий объект о к классу К , І : 1, t , если большинство алгоритмов типа I относят объект S к классу К Определение 1«3. Комитетом большинства, составленным из линейных алгоритмов С . . . , Со , назовем алгоритм, вычисляющий для объекта $ информационный вектор I, если . « S,W L" I 0 - в противном случае, X (S,c) { по правилу ГЛп г _ . ,„ „ і . J С I где І_х} - целая часть числа х Є К , ГС О Пусть р Є [О, 1] . Построим алгоритм распознавания, относящий объект S к классу К , и б: 1, t , если более чем Р -ая часть алгоритмов типа I относят объект S к классу К.1 . Определение 1.4. р -комитетом, р Є І Иі t составленным из линейных алгоритмов С , . . . , Со , назовем алгоритм, вычисляющий для объекта S информационный вектор по правилу Очевидно, что при р X Р комитет является комитетом большинства, при К- 1 7 - : D t - коми ІС1 тетом единогласия.
Предположим, что алгоритмы С{ , . . . , Со, упорядочены, и каждому алгоритму L , U. 6 И, поставлено в соответствие число Г" CC J , называемое рангом линейного алгоритма, такое, что выполняются следующие условия:
Построим алгоритм распознавания, относящий объект S к классу К , I Е 1, t , если найдется алгоритм наименьшего ранга, голосующий за вектор & \.Ь) , типа I » Пусть гЦ$) = (г(СJ : J-CS.CJ = 1, и. Є 14; j Uj. Если, например, для приведенной выше совокупности линейных алгоритмов « CS.CJ = (о,л), oiCS.cj = (л,о), «ACS, С) = (д,о, HS С ) - (1,ь), то г- . CS) = I, huh.
Тогда алгоритм распознавания, составленный из линейных алгоритмов С , С , - э ц вычисляет для объекта S информационный вектор
Так как гиперплоскость не может содержаться в объединении конечного числа гиперплоскостей, с ней не совпадающих, то получено противоречие. Пусть вытекает, что Из условия выбора векторов Q , , 9 О Возьмем некоторый вектор (Я- , і Є l,r l Ему соответству-ет вектор = СЛ , h.h )t Пусть а- Ь /л , и Є 1, t . Вектору (л.: поставим в соответствие два линейных алгоритма мУ и С (о.-) типа і с весовыми векторами Покажем, что алгоритмы СДЗ-) и С ((Я:J разделяют (в I I смысле [48J) множества 1] и А \ {_ яЛ Вычислим скалярные произведения весовых векторов алгоритмов на вектор Х т.е. оба скалярные произведения положительны.
Для произвольного вектора & х 6 1, \ (і} скалярные произведения и С (С :)), 0--. X ввиду условия выбора (1.5), имеют разные знаки. Совокупность Лр линейных алгоритмов распознавания С = {С; (а), С; (а) : а Є А\ І Є ЇД } будет задавать комитет большинства, правильно классифицирующий объекты обучающей информации.
Действительно, возьмем произвольный объект о- \ Є 1,1 . с Рассмотрим, как будет вычисляться информационный вектор для объекта Ь: комитетом большинства, составленным из совокупности с Зафиксируем .
Если и два алгорит l L о і — ма С. (Q.) и С ( Я) типа Ь из совокупности С дают 1 і . в . , с значения I -ой координаты информационного вектора L с , Сu (_СЯ.- jJ , ( ) (Q; )J равные І, а для любой пары алго-ритмов типа I значения о(. (S- С )) и o(,(S- С (&Л рав 37 нн I и 0.
Следовательно, более половины алгоритмов типа I из совокупности С относят объект S- к классу К , т.е. комитет большинства относит о- к классу к . Если oL (. 9 .) - 0 , то (Я Є А , и для любой пары 1 о С алгоритмов С,ЧсО, cj ), а 6 К типа I значения -( ; , 1 -а)) и ; (S; , C CoJ) равны I и 0, Следовательно, среди множества [\{ Х) с 6 С, t(Cj- і.} число единиц равно числу нулей, т.е. комитет большинства не относит о- к классу Ю (Г Таким образом, доказана следующая теорема о существовании V комитета большинства, не делающего ошибок на обучающей информации.
Алгоритм построения комитета старшинства
Пусть задана обучающая информация причем a(St) a(Sj) V і J ; i.j Є viv, at(S.) {0,1}, i4,...,t; j -1,...,пг.
Требуется построить комитет старшинства, правильно классифицирующий объекты обучающей информации» Из теоремы 1,3 следует, что такой комитет существует.
Упорядочим точки обучающего множества А по убыванию их норм, т,е. Из результатов пункта 1.5 следует, что в этом случае каждая точка совокупности Л . .., & отделяется гиперплоскостью в к проходящей через начало координат, от всех следующих за ней точек, т.е» Составим из точек множества А обучающую последовательность
Алгоритм построения комитета старшинства заключается в последовательном предъявлении приближению комитета точек обучающей последовательности и изменении его в случае, когда объект, соответствующий точке, классифицируется приближением неправильно.
При описании алгоритма будем пользоваться терминологией пункта 2.1.2 с незначительными изменениями.
Так, коррекцией линейного алгоритма С с весовым вектором W \С) относительно вектора обучающего множества Ct будем называть изменение
В качестве начального приближения возьмем линейные алгоритмы С, , ... , Ct : ur(C)= (aCS i-llaCS, )!!1), г CC) - \,
Допустим, что построено приближение комитета, составленное из линейных алгоритмов С1 , . . . , С д , .fy 4 » и предъявляется точка & v \ , обучающей последовательности. Пусть Если объект S. , соответствующий точке &; , класси-фицируется приближением верно, то предъявляем следующую точку обучающей последовательности
Если S- классифицируется приближением неверно, то воз-можны следующие случаи. I. Приближение содержит набор "D из v линейных алгоритмов с одинаковым рангом У (ТЗ ) , голосующих за & , если тип алгоритма содержится в множестве іф - [мр, и е ал или голосующих против CL- , если тип алгоритма не содержится в множестве ГО") » или корректируемых в ответ на &; , а все линейные алгоритмы с меньшим рангом, голосующие за Q. , коррек 0 тируемы в ответ на &. .
В этом случае корректируем приближение относительно О. о следующим образом. Корректируем относительно Q.: при G-(C,Q.) = 1 алго ритмы из набора Ъ типов из множества І (І) , голосующие про тив (Х- . Корректируем относительно (X при Ь- (С , Q.) -1 алгори тмы из "D типов, не содержащихся в Ці) » голосующие за Я- , Корректируем относительно CL при 0- ( С , Q..) - - 1 алгори тмы приближения ранга Г(С ) : r(C) r(D) , голосующие за d .
Замечание I. Если таких наборов из V алгоритмов несколько, то выбираем в качестве набора "D набор линейных алгоритмов с весовыми векторами, имеющими минимальное наибольшее сопротивление на (Х 2. Приближение не содержит набора "D линейных алгоритмов одинакового ранга, удовлетворяющего условиям из 1-го случая, и все алгоритмы приближения, голосующие за (X , корректируе-мы в ответ на СХ.: В этом случае корректируем относительно CL- при \т[\.fi) , о d - -л все линейные алгоритмы, голосующие за U.. .
Если 0L. имеет максимальную норму из всех точек обучающе го множества, для которых объекты, им соответствующие, классифицируются приближением неправильно, и для которых также выполняются условия этого случая, то вводим в приближение алгоритмы с с і -- , л, где - максимальный ранг алгоритмов
Корректируем относительно Х- при \r(CiQ-)- \ алгоритмы из набора Сс +1 , - - , C-n tj типов из множества Г (і). 3 Приближение не содержит набора "D алгоритмов ранга Ґ (Ь) , удовлетворяющего условиям из 1-го случая, и не все алгоритмы из приближения, голосующие за & , корректируемы _ с в ответ на CI- . о В этом случае приближение не изменяется. Во всех трех случаях дальше переходим к следующей точке
Если после предъявления подряд YTi. точек обучающей последовательности приближение не изменилось, то заканчиваем процесс построения комитета старшинства при данном Ь . При этом в результате может быть получен комитет старшинства, делающий ошибки при распознавании объектов обучающей информации.
Замечание 2. Если каждый объект обучающей информации содержится только в одном классе (решается задача дискриминантного анализа с непересекающимися классами объектов), т.е.
Задача разделения фигур в к , образованных гиперплоскостями
Так как функция d (х) задает в гч два полупространст ва, на одном из которых она положительна, а на другом отрицатель на, то фигура будет отделяться от дополнения только в том случае, если ее замыкание в R является полупространством, т.е. би нарный вектор , соответствующий фигуре, содержит Л еди ниц и они расположены подряд (считаем, что за компонентой векто ра і идет L ), т.е., например, вектор (1,0,0,1) содержит две единицы подряд.
Так как количество -А -мерных бинарных векторов, содержащих X единиц, и которые расположены подряд, равно \\ , то количество М- фигур, отделимых от дополнения с помощью линейного алгоритма, равно
Разделение с помощью комитета единогласия Предположим, что разделяющая функция имеет вид d (х) = ZL іук (-\г, х) ± 1 - . Функция л (х) положительна только в том случае, если положительны все функции (яГ х) j . .. , C "q,j -)
Так как множество точек в R , на котором функция (X (рс) положительна, является замыканием пересечения полупространств, то фигура будет отделяться от дополнения только в том случае, если в бинарном векторе, соответствующем фигуре, единицы расположены подряд. Сосчитаем количество таких векторов. Пусть - количество бинарных Z, Л -мерных векторов, содержащих I единиц подряд, і - 0 , . .. } Ik . Так как вектор такого типа однозначно определяется номером левого конца единичных компонент (например, в векторе 0 » И) у расположенных подряд двух единиц номер левого конца равен 4) и количеством единиц в нем, то справедливы соотношения = П , і = 1,... , ZA-1, Тогда общее число векторов равно ЯД 2L У\ = 1 + (2Х-1) IX + 1 - АЪ-2.Х + 1. 1-0 Следовательно, количество и, фигур, отделимых от дополнения с помощью комитета единогласия равно Справедливо следующее утверждение.
Замечание« Если фигура в R , образованная Л гиперплоскостями, отделима от дополнения с помощью комитета единогласия, составленного из Q/ , CL 1 , линейных алгоритмов, то она отделима с помощью комитета единогласия, составленного из двух алгоритмов. Легко показать, что если рассматривать фигуры в is , К 2, , образованные гиперплоскостями, то это утверждение не имеет места, Комитет старшинства Предположим, что разделяющая функция C J задается комитетом старшинства, т.е. имеет вид где коэффициенты V , . . . , vQ удовлетворяют условиям (3.1)«
Найдем необходимое и достаточное условие отделимости фигуры в R от дополнения с помощью комитета старшинства. Доказывается, справедливо следующее утверждение. Лемма 3.2. Фигура F в R. отделима от дополнения с помощью комитета старшинства, составленного из линейных однородных алгоритмов, тогда и только тогда, когда существует полупространство, являющееся замыканием конусов, входящих только в г или только в F
Доказательство. Необходимость. Пусть существует комитет старшинства, составленный из линейных однородных алгоритмов С1 , . . . , Со , отделяющий F от F.
Тогда алгоритм \ с минимальным рангом отсекает полупространство Г = 1; иКСДх) о], и относит все конусы, в него входящие, либо к г , либо к F ; т.е. существует полупространство, содержащее конусы только из г или только из F ,
Достаточность. Пусть существует полупространство Г , содержащее конусы только из г или только из V , Покажем, что можно построить комитет старшинства, отделяющий F от V . Построим алгоритм С с весовым вектором ЯАГ СЦ) , отсекающий полупространство Г" . Пусть полупространство Г_- [х R : (vr(C,), ос) 0 ] содержит конусы H ,...,Q-, , і 1, X -М . Из геометрических соображений ясно, что конус Q . X j - 0 , . . . , Х-1 , можно отсечь от расположенных за ним конусов Q , .. . , Q- с помощью гиперплоскости (линейного однородного алгоритма), т.е», при любом распределении конусов Q. , _. , У. +л-1 между фигурами Г и F , су-ществует комитет старшинства, составленный из алгоритмов
Формулировка задачи коррекции параметров объекта и ее преобразование
Пусть заданы множества допустимых объектов \_S j , описаний допустимых объектов и обучающая информация jo={aCS1J) S1);...;a(SJ,d(SJ) где (S.) (d(S.),..., о1 ( .))} olj(S-) -значение предиката n S- Є Кй , j - 1 , - . ., I \ і - 1, ... , hi.
Предположим, что решена задача дискриминантного анализа и построен алгоритм распознавания С , вычисляющий для произвольного допустимого объекта О информационный вектор С CJ0}SJ. Пусть на множестве описаний \Q» \.о) j задана метрика JKO-CSJ, G-CSjj » r e Л \ {$} , т.е. оп ределенная на декартовом произведении функция с неотрицательными действительными значениями.
Пусть задан объект S и вектор B (S) = ( (S),-- , . )), где компоненты &-(Ь) Є І И] имеют следующий смысл: Ь- (S) - 1 , если желательна принадлежность объекта S к классу объектов К; b. (S) — 0 в противном случае, 1= ,... Д
Например, если рассматривается задача диагностики в медицине с двумя классами объектов: \ - здоровые, К - больные, то вектор b(S) для любого объекта Ь имеет вид все; = (1,о).
Ставится задача минимального изменения описания & (S) , т.е нахождения описания (S) , ближайшего в смысле метрики на множестве описаний, для которого алгоритм С вычисляет информационный вектор C(,g(S)j= S).
Задача такого рода решалась в работе [45], где рассматривался вопрос рационального использования остаточной трудоспособности лиц пенсионного возраста.
В данной главе эта задача рассматривается для случая, когда множество описаний \.&(S) } d R , классы объектов не пересекаются и алгоритмом распознавания, решающим задачу дискри-минантного анализа, является алгоритм комитета старшинства. Она сводится к решению ряда задач выпуклого программирования.
Предположим, что множество описаний объектов является W -мерным параллелепипедом П. С R П = Га , а J х . . . х Га , а 1 тїи. max где Ct. и Ct. - минимальное и максимальное значение I -ой характеристики объекта, t = 1 ,..., It-. Обычно, при решении задач распознавания образов у каждой характеристики объекта имеется свой интервал (шкала) принимаемых им значений, поэтому необходимо преобразовать множество описаний таким образом, чтобы зависимость от шкал не влияла на вычисляемое расстояние между описаниями объектов.. Желательно также, чтобы преобразование множества описаний учитывало знание информатив 108 ностей характеристик, т.е. предположим, что нам известны веса р1 , . . . , р характеристик, где pt 0 , і, - 1,..., кі, и вес характеристики тем больше, чем больше ее информативность. Эти два обстоятельства приводят к следующему преобразованию описаний объектов: a.(sj - a. a.(S) = р,-— l— , і-= І, ..., п. і l max mih. a. - a п с Следовательно, множеством описаний объектов будет являться параллелепипед П- [о.р,1 X. . .х [o,pJ. Рассматривается следующая задача дискриминантного анализа с непересекающимися классами. Заданы множества допустимых объектов \ S j , описаний объ ектов и обучающая информация : причем
Из теоремы 1,3 следует, что существует комитет старшинства, правильно классифицирующий объекты обучающей информации. Предположим, что задача дискриминантного анализа решена, и построен алгоритм С комитета старшинства, составленный из линейных алгоритмов С,,..., С п . КС.) - I UCL)
Алгоритм С классифицирует произвольный объект S по его описанию a(S) следующим образом: объект относим к классу К , если t ( С і ) - L , где і ,- тіл. Кеіл ; (vr cj, a:cs)j оі, здесь CL С S ) "= ( ОЛ S ) ; 1 ) К. , если множество (і 1Л " (ч С ), Х (Sj) О V пустое, то алгоритм С не относит объект S ни к одному из классов К
