Автор: Лиховидов В.Н.
Теги: математика естественные науки физика математическая физика кибернетика издательство владивосток
Год: 1983
Текст
УДК 506 + 5X0
Печатается по решению
редазцаонно-издательского
совета ДВГУ
Рецензента:
доктор фивико-математическак паук
профессор В.Н.Фокин (.ЛГУ); навдида? фиэико-ма-
тена*ичесних наук доцент В.В.Ццин (ДВГУ)
Л55 Лиховидов В.Н. Практической курс распознавания образов.' ~
Владивосток. Издательство Дальневосточного университета,
1963. - 124 чг,
■ В учебном пособии рассматриваются ооновные вопросы теории
распознавания обраяов: сходимость алгоритмов,обучения и
самообучения, методы отбора признаков, оценки точности алгоритиюв и
метода моделирования процеосов раопознавання на ЭВМ. Изложенная
теория применяется к практическому изучении с пршененяем ЭВМ
девятнадцати конкретных алгоритмов распознавания и отбсра
признаков. Учебное пособие предназначено для студентов, обучапцихзя
во специальности "Прикладная мауематика" 0647.
Г7.2. » 35 ББК22Л2
160 - 83 бвз объяьлениг Л65
(Q) Издательство Дальневосточного J
университета, 1963
ВВЕДЕНИЕ
Теория распознавания образов- является одним из важнейших
разделов современной кибернетики как в теоретическом, так и в
прикладном ллане. В последние годы методы теории распознавания
образов успешно применялись в медицинской
диагностике,"геологоразведке, прогнозировании погоды, для построения читающих
автоматов, контроля качества изделий и т.д. Это делает их
полезнейшим инструментом в научных исследованиях и в ряде областей
практической деятельности. Владение методами распознавания образов
необходимо каждому специалисту по прикладной математике,
занимающемуся обработкой результатов экспериментов.
Сформулируем задачу раегсо^авания, (вторая иоследуется в
данном учебном пособии. Пусть имеется небколько классов объек-'
тов. Каждый объект характеризуется значениями нескольких его
параметров - признаков. В результате некоторого эксперимента
можно получить наборы (векторы) признаков для
последовательности объектов, при этом известно, из какого класса взят каждый
объект. Затем'появляется новый объект с его опиоанием, но
неизвестно, какому классу он принадлежит. Необходимо на ооноее
полученной ранее информации вынести решение о принадлежности
этого объекта.
Так как объекты изображаются векторами в многомерной
пространстве (пространстве признаков), то мы приходим-к
геометрической формулировке задачи распознавания: необходимо построить
поверхность, которая разделяет множества, соответствующие в
пространстве признаков различном классам объектов. "Если
множества в пространстве признаков, описывающие разные классы, не
пересекаются, то возможно точное разделение классов; если же
они пересекаются,., то любое решающее правило .неизбежно будет
ошибаться* поатому необходимо искать правило классификации,
доставляющее, минимум шибок*.. ^
Инфармация-г которой' обладает исоледователь до эксперимента" ,
- априорная; информация - служит для выбора конкретного типа ал- *
горитма gacnosHasaHKHv УЫ информация» которую получают в
результате укопвриаеназ& isemw$& признаков и указания о принадлезнос-
ти объектов-. 'шгагванХ яезавает-ся обучающей выборкой и служит
для построения? нашфчаеяа' правила классификации. Сам процесс
построения ззхшо правила^ т есть обучение распознающей системы.
Возможна и такая- ситуация,» когда указания о принадлежности
объектов обучающей, выборки-! отсутетвуйТг в этом случае мы инеем дело с
вадачей самообучения^
Учебное пособие написано на оемове лекций- и лабораторных
работ, проводимых на математическом и физической факультетах
Дальневосточного гооуниверситета. Основная цель, преследуемая в
этом курсе - обучить студентов грамотному решению задач
классификации, которое включает н-оебя выбор алгоритма распознавания,
наиболее подходящего для конкретной задачи, теоретическое*его
обоонование, написание и отладку программы для ЭВМ с змлиричес-
ким исследованием свойств алгоритма на модельном материале. В
соответствии с этим учебное пособие разделяется на две части -
теоретическую и практическую.
Теоретическая часть ^главк I, II я Приложение; содерйсит
формулировку основных понятие теории распознай»» о >а"ос и
обоснование методов построения алгоритмов класс! v .а ии ате-
матически задача распознавания формулируется its,/ по >ое.ние раэ-
делямце.; поверхнооти, доставляете:-: ызиЕ-'.ум некс^ *у /ь пио-
иалу среднего риска. Рассмотрены три типа задач *лс о fa a*, p
5
детерминированная и вероятностная задачи и самообучение.
Основное внимание уделяется построению рекуррентных алгоритмов обу- "
чения и самообучения. Здесь же изложены вопросы оценивания точ- "
ности алгоритмов обучения, досги;-£ймой на обучающих выборках
конечной длины, а также элементы иетода Монте-Карло, необходимые
для моделирования обучающих выборок при иоделировании
алгоритмов распознавания на ЭВМ. В приложении рассматриваются
некоторые вопросы метода стохастической алпрокоимации, лежащего в
основе рекуррентных алгоритмов обучения.
Вторую часть ооставляют главы III - У1, каждый параграф в
которых посвящен подробному исследованию -одного конкретного
алгоритма обучения, самообучения или отборагфризнаков. Фактичеони
отдельный параграф предотавляет собой лабораторную работу*
состоящую из1 пооледова'гельнооти заданий. Выполнение йтих заданий
оостазляет три стадии исследования; теоретическое обоснование
алгоритма, оос^тавление и отладь.у программы для ЭШ,
тестирование алгоритма на модельной материале. Предполагаетоя, что в
лабораторном практикуме используется какая-либо мини-SBM,
имеющая средства отображения информации и диалога, например, СМ-4,
"Мир-2" или "Наири-4П.
Учебное пособие может быть также попользовано в качестве
справочника по методам раопознавания. Все задания, касающиеся
конкретных алгоритмов, сформулированы так, что ответ оодержит-
ся в оамом вопросе., Для учащегося важно продемонстрировать
умение провести все доказательства. Читатель же, которого не
интересуют математичеокие тонкости, может легко с помощь»
приведенных формул составить программу, реализующую нугэнгй ему алгоритм,
ГЛАНД I. ОЯЮВШЕ ШИПИ И МШШ Я ' *
МОШЯИВШИ ОБРАЗОВ
1.1. Проотранотво призваков и априорная информив*» *'■-
Пусть имеется множество объектов fit , элементы Kortpo**-
го мы будем обозначать буквами А ,£,... (возможно о
индексами). Множеотво $- разбито наМ непереоекаэдихоя
подмножеств ft-i M
которые называются класоамя объектов. Над каждым объектом
Дбft.производится А/ измерений, результаты которых эск,(А\
... , 3£( (Д^ назнваютоя признакеми данного объекта.
Таким образом, каждый объект изображается вектором признаков
Эс(Д}- {XUW Х'"!(А)} в tf -мерном простраяот-
ве, которое называется пространством признаков.
Векторы в пространстве признаков ми будем записывать в
виде столбцов .
ос^ЧА}]
так что пространство признаков будет обйчным /V -мерным
проетранотвом R . На вход распознающей системы поступает
последовательность векторов признаков
Х|,...,зеЛ1...(Хк =ос(А^, (t.i.t)
ооответствуищх набору объектов At , ... . Д». . ••• из
(К • Последовательное ль ("l.i.i) называется обучлющеь
послед овательностью, или обучающей виборко;!.
Задача распознавания может бкть в обйеы аиле &№psym-
ровапа следующим образок: необходимо по вбучада»ей т$ар*&
7
-построить решвдее iipascac, то есть аравкдо/которое" душ
любого объекта AG ■&■ (возможно, ае оовцадавдего .ни о одним
из А*. * Л. ', А.*,) позволяло бк на оонове вектора "Х(А)
' 'указать, какому чз классов ft,.*, тллвдадлешт объект А ,
Конструктор распознающей системы может быть в различной
отецени оовздомлен о структуре клгйсйфЕЦируемо-й информагдаи,,
■■к-
Если для каадого объекта обучающей выборки известно, к кежо-
■ му иласеу он относится, то мн имеем задачу обучения '.$£.&-
поавазанию образов» при этом указания о прщаддзжностЕ
объектов обучещей выборки называя-гея указаниями учителя. Золи .
указания учителя отсутотвуют. то мы пряходчм к задаче оемо-
. р0учвн?я - система додьша -обучаться уздедиФь обвекты сема»
без нодокаэки со сторонн* Далее, зуотьХ<тН"1».--[М)есть
образ класоа 0Ц при отоораке1фи.;0С.(А),то"*и*^
Х = {хе I?: Зй*Х(А)# А« Cti },
■Вовможны два случая структура маояюотв {X*J, ощюдеявхвцйе
■//оноеоб решения задачи распознавания:
^а) множества ' Ai не пересекаются, б) множества &*, пере-
■еехаются.
Е первом случае возможно точное разделение множеств At*
а следовавлшо» и точное решегхе задача распознавания,
которая в stom случае называется детермшшрованной, Примеры
ситуаций б)г Еетрудяо~ж>отрой*ь ^ ^~р- Поскольку в этом случае
лмеиюд точки ОС , одновременно принадлежащие нескольким
множеотвам л£ „ то ясно,' что точное решение задачи р£су-.зА
; навашЕЯ вдесь невоамсияр, т-»в» для аекоторкк объектов на оа~-
'vHobs нх векторов признаков лрин!щшй&льяо невозможо одаоэчач-
яо установить хгринадлзжнооть к току или иному классу* Додоб-
»••***"' ""£&■ ■* "?"''
ные оитуации ш условились трактовать в вероятностном омнолв!
мы будем считать, что векторы признаков, соответствующие
объектам хлаооа &i , являются случайными величинами и
распределены в соответствии о некоторым распределением
вероятностей (своим для каждого класоа).Тогда случай Х;,ЛХц^0
еотеотвенно отмывается в терминах перекрываацкхся шютвоо-
тей распределений и задача раопознаваюш носит название ве-
роятжотяой.
Теперь мы еще более детализируем постановку задачи,
рассматривая отдельно три случая,
I.I.I. Детерминированная задача раолозыавания,
рш простоты будем пока предполагать,что имеется только
два класса &«.', Лг , и пусть Xi Л Хг = 0 .Тогда?
существует разделяющая функция,т.е. такая функция |* С^-) ,что
. *о даже)!,
•. *v для »е Хг
Для того чтобы обучать машину узнавании объектов клаВсов ft-i,
О-г нам в дапком ожучаэ достаточно построить фуягадо if Ок),
знак которой оозпадал бы оо знаком t^ia<ium |»Сзс):
f(uc)sO если f.fatjjo,
j(X.)<0 если |»(жНО,
или ;:наче можно эвжоать
$(ъ)1*Сх.)>0 Vx&XinX2.
Яриг.:гош оиотемн, решающей дьтер:,п:ы;ро^шую .3^чу распозна-
ваш'а,является персептроп Розенс'латто (с:.,. J 3.X.).
_.1.2. Бероятпостная оэдвча р;-1Снопнг.нашл.
:;усть вектор прпзп^оз.иоотретстЕ.уяни^ o&bwf}/ из деласг
са #..(, .является случайной .величиной в R" ",распределенной
о плотностью 1\ (*0 ( *■ аХ,2). Кроме того задана
вероятность Vi появления в обучающей шзборке объекта из класса
&v • Vl назнвается априорной вероятностью класоа <&i .
Плотности Vl C^w могут перекрыватьоя: на некотором
множестве Y с X1 " л 2 обе функции Vi fac) • V% (Эь) не равны
нулю (см. рис. i. 1 ). Е этом случае задача классификации может
быть сформулирована следующим образом: найти решагсще-л правило
вида
ДеСЦ; если £(;с(А))»!?,
AsOj) если J (X (А)) < О,
которое давало бы наименьшее1 число неправильных ответов,т.е.
чтобы вероятность неправильной классификации была минимальной,
Рис. 1.1
Как будет строго показано в- § 1.3, такое оптимальное
решающее правило задается функцией
/„О^р^х^-р^о) . (i.i.a)
и называется байесовским решающим правилом. Итак,задача
обучения распознающей системы сводится к оцениванию байесовского
решающего правила. С делано это модет бить разлЕгтшд ейособа-
пи.Ыанршзр, глокно по обучающей выборке и указавши* учителя
оценить априорные вероятности Р-С и плотности рсСэ^) л под-
1С
стлать ш. в формул/ С1Л.г). в математической статисдае
разработано больше '-гасло методов одещшашя раолредедэниИ эероййи^
стей; веко"орве та них будут подрооно рассмотрены в 5 4,1 -
i'.Sv Другак подходом является недоередствеыие вооемижлевЛе
оппмааькой байесовской решащей функции: необходимо яайти та-*
itjfo функ:ад) £ (х)» которая в наименьшей степени отклоняется от
4-~*(/Х-) , т.е. к примеру, доставляет мншшум функционалу}
Для .реюния" таких задач оудет развит ошпиальзия иетод в §4.3.
Здаетнм^что детерминированная 8адача распознавания явля-
%'рря частнви случаем вероятностной. Действительно, пуоть адот-
аоетя PiC^n РгСЭС} сосредоточены на непереоекаииихоя множэ-
•$твах-, Xi a X* к
ft, «*Х4,
Выборе» в качестве функционала (i.i.i) слодушщй:
Tift) - Е [ h№ - Щ» № У .=
* ЧЕЗ{М*-Ш*-)<0^ =4P€Cf), (i.i.l)
■эдцоь^ \ I ~.,воличеда?принш£аю1т;ак значение I, если вы-
иодияетвя уоловие.эазксшной в скобка?:, и О*в противнем случае;
*PtCf) -вэронтзооть ошибочнее клесглфшяюо!, еоответотьулнтдя
решающей <7уикп?т £ С*-) -Та.<шл образом,дето!иин£рдаанявя зада- ■
■«а текже ооетокт в мавишдаяий вероятности ошибки.iia спецяйн-
ж*. ваклЕчаёкуг в тоа, что -зук»сгаует точное решениеСРеХ!*-)» $у
4SQ зоэзводяарт использовать ,тда решения ияне метода,чем в ве-
jUpSC&IOCIHOt ''ПОСТШОВКЭ.
11
1.1,3. Самообучение' (автоматическая классификация)
Как можно клаесафщэфоваздь обучающую выборку, если
указания учителя отсузетвзгая?? Ответ на этот вопрос дают
следующие соображения* $$$>№ ллотности ftfx^l^x), описывающие
Рио.Ч.а
распределения векторов и признаков внутри классов.имеют Рис. 1.2"
зараженные максимумы в достаточно разнесенных точках ^i, M% *
Тогда большая часть выборочных точек будет лежать в
окрестности центров lit . 'М^и совсем мало точек попадет в район "до-
лини". Ояенивая плотности р«.ЗД или непосредственно отыскиээая
'!долину" как область малой плотности точек и проводя не ней
разделяющую границу, ш и получки решающее правило. Таким об-
разом, сама по себе обучающая выборка бег указаний учителя
гложет содержать информытию,достаточную для разделения классов.
Математически атот процесс также можно представить как
минимизацию некоторого ^вкционала от совместной плотности;
действительно, если записать функционал S1
f * Z SHoc-ail^Wdx, (i.t.F)
12
где Xi и Хг - Два непересекающихся множества, то
задача самообучения сформулируемся следующим образом: найти та-
кие множества X* . Х& и центры 411 , У.г , которые
минимизируют функционал (£. i. 5*) . На простых примерах
можно убедиться,, что -если сложности Pi-C^) сосредоточены на
"комшктннх"разнес©,}ще!: 'Множествах, то, минимизируя
функционал (i.i.ff), >мы сможем акделйть эти множества.
Следует отметить важную черту задачи распознавания: во
всех трех рассмотренных случаях она свелась к минимизации
некоторого /функционала от плотнооти распределения Р(э&) .
Такие функционалы'называются функционалами среднего риска и
главной нашей, целью в дальнейшем будет разработка методов
минимизации функционалов средвего рис&а. Построение обучаемой
распознающей системы мы будем рассматривать как создание
алгоритма минимизации определенного функционала среднего риска.
Цы увидим, что такая формулировка распознавания охватывает
очень большое число практически важных задач. До вполне
понятным причинам этот подход лазиваетсд геометрическим, или
статистическим направлением в распознавании обра-зов.
Таким образом, круг вопросов,изучаемый в 'данном учебном
пособии, характеризуется как статистический*подход к
распознаванию образов; обучение распознаваний понимается как
построение поверхности,-разделяющей классы в пространстве
признаков. При этом ореди всех возможных разделяющих поверхносте!
отыскивается оптимальная,' то -есть доставляющая минимум дедо-
т-орому функционалу среднего риска.
Разумеется,есть много задач распознавания, которые не
сводятся еотеотвенкым путем к разделении множеств в
пространстве признаков. Еольи-ое количество таких проблем обсужда-
13
ется в литературе: синтаксический подход-'к распознаванию
образов,анализ изображений сцен, сиотемы тактильного
восприятия для роботов и т.д. (см.например, Г"#Т> £.£Ч]).
I «2.*-Детерминированная задача распознавания
Как показано' а параграфе 1!. % ,. детерминирог-апная
задача распознавания образов приводив к' отысканию функции l-fa),
удовлетворяющей неравенству*.
Для того чтобн подучи»- штеыатйчеоки .точную постановку
задачи, необходимо-' определить тоткласс функций 10»),в котором
ищется" решение.Будем предполагать .что искомая разделяющая
Функция £fo&) имеет известное аналитичеокое выражение
£(ЭЬ*)к f ('Xrjtr)^ где Т -неизвестный векторный
параметр, *тг 6 R . Тогда задача оводитоя к нахождению
значения вектора Т .удовлетворяющего условию;
причем,значения функции 4*(х.) известны только на точках из
"■обучающе*: выборки.
Зводь обозначение
исрешниом (1.2. i):
^x;ii'i образам, задача распознавания в детерминированной пос-
*s*iOj3Ke приводит к решении оиотемы неравенств (1.2.3*)
и
' (таких неравенств в системе (i. £.3) столько же, сколько
элементов содержит множестве Ж « Xi U Х^ ).
Сдним иэ способов решения ,такой задачи являются
рекуррентные конечно-сходящиеся ажотпш.
Определение. Рекуррентный вазшаетея алгоритм вида;
в котором каждое оледуяцее приближение к рцевдшаемому
параметру строитоя как сйункция предыдущего- приближения и вновь
поступившего "измерения" X*v .
Такие алгоритмы наиболее удобны для реализации на ЭШ,
поскольку они не требуют запоминания всей обучающей выборки
Xt,... ,31ч,.Это имеет особенно важное значение при решении
задач распознавания на мини- и микро-ЭВМ, объем оперативной
памяти которых ограничен, В дальнейшем мы будем всегда
отрекаться к построению именно рекуррентных алгоритмов
распознавания.
В частноотн, для решения систем неравенотв (i.Z.i)
применяются рекуррентные алгоритмы следэпощего вида
т., i - т.. г А. й~ V* Ч" (*~,чг-), (i.a- -О
где
, _ ! I, если M'CX^.t-^iO,
"" (. О , еоли f (I», f«.) > 0,
ГЛ^У-некоторая неотрицательная чиоловая последовательность.
Алгоритм (1.2..Ц*) имеет естественный вид: ьектор'Vh.
сдвигается в направлении возраотшшя функции ^(*,'"*г)р если на и^м
шаге не выполняется неравенство (LiL-i-) ; в противной случае
Т"*. остается яа меоте.Последовательность (&«,^додяна быть
15
выбрела так, чтобы обеопечить сходимость'алгоритма (I.Z.4)
за конечное число шагов.
"^Драделение.АлгсшиГ^- Ь. Н) называете»
конечно-сходящимся,если для лвбой обучаицей выборки ^3tt,.,.,»»,, ._. \ ж лю-.
бото начального вектора Тг е К. найдется таков номер X ,
что ^(ос^.тяЧ > О для всех и- » fit .Очевидно,нечжьая с этого
вомера к. , вектор "Тк перестанет изменяться! ft, •= ^л **.
Покаяем.что в алгоритме (t.ff. Ч") при некоторых условиях
можно так выбрать последовательность ^&*.},что он будет" ко-*
вэчво-сходящичоя.
Теорема T.I.. Йуоть внтголяеян сладупцие уолсвия:
где 0-1, С j, не зависят от X ;
-2}сзтаэетнуют вектор тг» е. I* и число в» >0 такие, что
4>(-х.,тг»')>*».,' ос е X ',
3)справедливо неравенство.8
- Выберем числа 0.и,Е алгоритке (1.8.4) :
где А*.ё [О, £1, X» -число изменений- вектора. TV за И«
шатюв алгоритма,'Ci B i,
(ОС к.'. , если > (Ж .., О-.0 >0,
1*м*,аодя f(X^,tw)40.'
Тогг<а алгоритм (1.2.41 будет конечно-сходящимся.
"ГДоказательство: Лредполояим.что на И- -м шаге произошло
исправление вектора f*. .тогда соглг.спо (1.2..У) z (i.Z.s)
-Г
16
"i! Тк-т» 11г+ гг?ла„. (t*. - %, ^ f (х л>тг^) +
4 II т*-о; 11г+ 2-Л. аЛч^лг..) _ 4>(x».,tv)l ♦
+ iia.» llvc.'«f(otB.,'r».)ii!
a a силу условия 2) доказываемой теоремы/
flTW-TrJI'illtw-t.f-
- г Л й„ (*»=f (а^т.))<• 4 «; цуг f (хЛ, tw) Г.
Подставляя овда CL„. из (I.E. б) и rpjmmpya слагаете, по-
лучпи неравенство?
lllS,u-Tr»ll^ inr„--tvl|l- 2г1 |t +
Последнее слагаемое б правой ^нота мола;о отбросить, посколысу
ояо аецрложительно; то же самое справедливо и для третьего
"слдагеыэго (рая гролзошдо дещ явление,то *f Сх^/Х-УРЭ.Не-
ггрудар доказать,что в четверга, слагаемоз неположительно, и та-
/ик 'обрезом,
Вf«i --'с, «г * St-,-1-»f-g.t»„.-i^;
Оуилпр^д этл Ейрслелстяа .по 11. от. i до /Т ,находим;'
| 17
г. таким образом, 1|тгкм-Т^Пг6 1К*-тЛ*~ 2€* J^ 4" '
£ откуда я следует,ч^о Х.п не может стремиться к бесконечности
при Vb -* —>. Теорема доказана.
v ^та теорема позволяет обосновать большое число алгорит-
- мов распознавания в детерминированной постановке,Общая схзма
ноет:оеыия алгоритмов распознавания состоит при этом в
следующем. Пусть разделяющая поверхность ищется в_ классе функщй.
fOxrtr)*Обозначим через ©"„, указание учителя относительно Си*,,
т.е., QV = sicpi ^«(XivV
Тогда конечно-сходящиЭся алгоритмгполучаеШ2# из (±,2,ц*) ,
{i--Z 5") при замене ^(за*-,^»*.) на §~к.£(3(КЪ0 будет
алгоритмом обучения распознаванию образов:
MS:
если e^ffX^Tr^-) S 0,
если 'SW f (ЗС-л, TT„) > 0,
»' ,, Т^З. Вероятностная задача распознавания
-.' Дадим строгую математическую формулировку вероятностно:?
^ задачи распознавания.Пусть на вероятноотной пространстве XI.
задана случайная величина И .принимающая конечное число зне-
f чацвя, i_'eIi,,,,,M.\, М ^ ■£• Будил интерпретировать
> э^чеяие случайной величины Ъ как номер класса,которому дри-
Нщлежит объект.появинзийся на входе распознающей системы,
/ 5^"Да вероятность рк*р {*fs £\ есть априорная вероятность W*.
Пусть кроме того имеется векторная случайная величина \ ,
принимающая значения в пространстве признаков Rv ; значение
ОС случайной величины ^ есть вектор признаков
объекта,поступившего на вход распознающей системы. Предположим,что
существуют условные плотности распределений для каждого из классов,
то есть для множества 1ЬС Я *
Очевидно, распределение случайной величины ^ будет иметь
плотность i
м
(этот факт следует из формулы полной вероятности).
КашЕ. задача состоит в том, чтобы наилучжм образом
провести классификацию объекта, заданного лектором признаков,то есть
необходимо построить таков правило, которое по вектору
признаков указывало бы, к какому из классов&-iT - . jOL^a относится
соответствующий объект. Слов& "наилучааш образом" предполагают,
что у нас есть способ количественной оценки построенного
правила классификации,Поэтому прежде всего определим,что да будем
понимать под качеством классифицирующего провила. '
&дадии матрицу потерь С —{Cht >"k,£ ™ i-,-., -М }
элемент Сit*i, которой имеет смкол штрека [ни ei;b), связанного с-
относеыием объекта, принадлежащего К. - щ классу, в t -й ■
класс. Р£осмотрим разбиение [Xi\ (£*i, ■ ■ ■, М) пространства
У. на М. непересекагащихся подмножеств.Этому разбиению будет
соответствовать решающее правило £ :
o\3t)»i, Шла. х ^ Xi
v 19
(мы относим объект к классу (%,±геслк его вектор признаков
попадает в Xi ).Очевидно, ркРкСх) dx. есть вероятность
попадания вектора из К. -го класса в окрестность doc точки СС,
Средний риск (штраф) отнесения объектов к. -го класса в <--й
класс равен
где Ух, С"Х) -индикатор множества X с .Общий риск получится,
если это выражение просуммировать по всем г, к, X. :
_ м м
£ (?) = ) Z £ \ №)<vv р* p. № dx •, (1-3.2)
R* i=i K*i Av Г l
&(й)-средний риск соответствующий превилу классификации
о, является критерием качества* чем мейыпе к ( б J, тем
лучше правило $. С математической точки зрения Ё.(о) является
функционалом на множестве решающих правил (ок сопоставляет
численную оценку каадому решеюжему правилу о ^поэтому его
называют функционалом среднего риока.
Оптимальным мы будем Ьчнтать решающее правилоtимеющее
- наименьшее значение Ж$) .Вероятностные охемы.в которых
рассматриваются классы распределений о заданными на них
априорными вероятностями, называют в теории отатиетическях решений
байесовскими.
%■ Определение. Байесовским решающим правилон называется ре-
*L'' шающее правило минимизирующее средний риск.
С Итак, пуоть задана вероятностная схемами. ,{\(ос-) ,k»i ,
С" ... , ЬА и матрица потерь С= f^icLj • Какой вид имеет байе-
f "совское решающее правило? Для того, чтобн ответить на этот
:; допрос, преобразуем сначала &(ff) к более удобному виду. Вве-
-■ft 'i.
го
Тогда функционал среднего риска прилет следущий вид.
Ш) °& S„ \(*-) =UC3 P Wdx - (1.5.4)
Удобство такой зашей оостоит в том, чтоИ("£) здось явно
выражен как математическое ожидание некоторой ?унк1эди, а именно ;
Естественно ожадать, что $ушщдонал(1.$. й) достигает минимума
в том случае»' когда мн относимв класс X i те точки, для
которых cii (ос.) меньше любого dl*. (ос.), k* i. Для доказательства
оптимальности такого реиакщега нравмла нам понадобятся
утверждение, которое удойно офэрмэть з виде отдельной леммы, так
как око неоднократно будет использоваться в 'дальнейшем,
Леша 1.1» Йуоть разбиение |Xi , i«-i,...,Mp
определяется соотношениями;
Тогда дчя любого" другого рнзбиення j Xi, \ и Ot <£ £. справедливо
неравенство;
- Доказательство. Отметим, что s опгелолешш. (А.З.ь) никак
не учтены точки" " границу > для кото пых fy\, (сс.тг)» ^(х,^.
Поскольку мы предполагаем существо с tj ^ в i о i ости
р(сс), то границ имеет нулевую ве о mi jc и nit. и ада
в йутадаонал (1.3.iT) . Но для т го "т j г Xt
составляли в сумме вес пространств" и Р- о j J vu ть
Щ 21
Л в них и граничные точки. Условимоя для определенности считать,
что граничная точка принадлежит множеству с меньшим номером.
£, Поскольку множества ^ *^i\ не пересекаютоя и VXi e Е- ,
♦ то Z Ч%9 (ot) ^ i. V ос в £.* и аналогично £ \. С») * i
I- ¥ot e £/" f а -следовательно, при любом 1С
м
&■* Зафиксируем теперь точку X е Я * Так как она обязательно по-
^ падает в одно из множеотв \ X {[, то найдется такое к. , чаю
V* y„*(x-)»i. Добавляя левую чаоть (1.VS) к dCx^)t получим^
;_ поскольку Х«(ос-)*-0 при W К . Но в ойлу определения мно-
^ жеотва Х£ для X сХ^имеют песто нераванотва dtCot) 4сЦ(х-)
jT дрн всех tyk. Отсюда следует <АСх)&0t что в оиду произ-
~^Г вольности точки X и доказывает лемму.
">t - Теперь легко показать, что разбиение I Xi \ * определяе-
#£у*ыов соотношением (i.J.fc)i является оптимальным.
Теорема 1.2. Байесовское решающее правило 'определяется
^ ^"^ разбиением ;
Щ 41§йо|сазательство» Очевидно, разбиение (L.b.£) и (1,Ъ.9) эквива-
& "-йеатны, так как в облас™, гдерСс)=0, разделящие граннтц*
А- * а\
■^ ^ейшо проводить как угодно, при атом значение R(b; не язме-
нтся. Пусть |Xi j - произвольное разбиение, тогда согласно
Йедае i.. i I
Z2
где У» -решающее правило.соответетвунцев разбиению (1.4. $у
Теорема доказана.
Рассмотрим один очень важный чаотный случай построения
оптимального решающего правила. Пусть матрица потерь имеет
вид;
fi при К?**,
1 0 при i~ К
ft.4.10)
при I ~ К.
Тогда оптимальное. разбиение состоит иэ множеств:
= Л .{PupK^^Pipif»)},
что соответствует рекалиему правилу: 'X. относится к А*,е<ш(
ft Рг<*> ? PjcPJW даи"воех k + t fi.».u)
Дик матрица noTepbfi.i.U?) функционал к(?) есть вероятность
ошибки решающего правила.Особенно простое вид этот функционал
имеет для двух классов (М-1^):
£(8) = Pi S pi(=-W« + рД ptf3u)d« ,
Таким образом,ретагащее прашш>(±.3.и) г.пшжизирует вероятность
ошибочной классификации.
Пример .Классификация для гауссово rant распределений векторов
ПрНЗН&КОВ.
Пслболее часто лрииеняется в ш;те;^.т;:-чес::о.;: статистике
нормальное (гауссосское) расирзделокие. ^го ст^пио кар с осс-
з?
*
бой ролью,которую играет нормальное распределение в теории
вероятностей (см. центральную предельную теорему),так и с
простотой аналитических результатов.Наномним.что многомерное
нормальное распределение есть распределение е плотностью
?(х,л,к) =(^JLj^ exp [- i A'V-o-Ux-a)], <i.ws)
й- -средний вектор, А - ковариационная матрица:
К*
А= 5 (x-cO(»-ft.y,p(x.,,utA)dai.
я"
Рассмотрим случай двух кл&сеов, М *.Ш Байесовское
решающее правило удобно записать тогда лополёйуя отношение
правдоподобия р*.(Х)/Ра (эс) : X относится к классу GL± .если
*** Додотавляя сюда плотностн(Д-3.1&) .видам,что решайте правило
^ " определяется разделяющей поверхностью второго порядка:
Ра
-(A;(«--at),a^- аг)*2^г
?! '
Полезно проследить на конкретшх примерах (выбирая для N* £
достаточно простые матрицы Ai. ),какой характер имеют поверх-
, ности |(ж) = О .1Ш здесь остановимся на случае,когда обе мат-
**а5ицы Ai единичные. Разделяад&к поверхность тогда превращает-
^«я в г1шерплоскос'№:_
24
Pi
Еь-jtK априорные вероятности равны, PteP2 » *о гиперплоскость
|Гх)»0 проходи? перпендикулярно отрезку, соединяющему &£ и
*2.2, через его середину.
Итак, мы получили вид решающего правила, минимизирующего
функционал среднего риска.
Однако, при решении задачи распознавания мы не имеем
достаточно информации для использования этого правила, т.к.
могут быть неизвестны ии плотности p.(oc)^iA априорные
вероятности р. . Иначе говоря, мы долкны принимать решения, имея
неполную априорную информацию. Для преодоления ятой иеопределенг
дойти и олужит обучающая выборка. При этом возможны два пути
использования Ёмлирическнх данные: а)оценивание плотностей
распределений и б) непосредственное восстановление параметров
оптимального решаьа^еге правила. Рассмотрим в отдельности оба
этих пути.
Оценивание плотностей распределении представляет собой
классическую в&дачу, решаемую в математической статистике. А
именно, пусть имеется повторная выборка (то есть, посяедоэатель-
ность независимых одинаково рвсяределеннах случайных величин)
3Ci,...,0cWj... с плотностью распределения pfvc) . Необходимо
построить оценку функции р (*). Известно много методов решений
этой задачи, например, метод максимального правдоподобия,
байесовские методы оценивания, неп&ьамвтричес^яе оценки плотностей
Схема обучения распознаванию выглядит теперь следующим
образок. Обучазоцая выборка разбивается на подвыборки, соответст-
25
"*, вующие отдельным классам.Оцениваются плотности распределений
t дая каждого класса pi Ой и априорные вероятности классов Pi .
*- Получешше оценки подставляются в байесовское решающее пряви-
,i до (1.Ъ.11),которое и попользуется для классификации.Такой ме-
*j тод решения задачи распознавания рассмотрен в параграфах 4.1-
Ивогда предпочтительнее может быть другой путь:не оцеаи-
_/ вать плотности и, априорные вероятности,а непосредственно ис-
I?' яать параметры байесовского решающего цравила.Раесмотрим для
^ простоты разделение на два класса;введем функцию е!(эс) ,на-
-f ^зываемую степенью достоверности принадлежности точки эс. к
"V классу <Xi i
•-, Вта.фуввцня однозначно определяет байесовское решающее правя-
J?\ -X~ai, если dC-xi)?-^'
вехоторых случаях функцию dCx-) бывает восстановить проще,
>Jen оценивать в отдельности Pi,pi.PtfOtt^piCx}.
По оудеотву, dfx.) есть условная вероятность того, что
5EV
воявингойоя объект принадлежит первому классу,если его вектор
внаков равен х- (иначе говоря, d (х-) -апостериорная
вероятность принадлежности вектора Х- к классу ft. t' ).
Пусть ^и есть указание учителя,
10, если Я.».~ Я.в,
1, если •ОС». *-» 0U ,
2»1до имеем:
Z6
откуда
Доложим 5 к. ~ ^ ~*^(^i') 1 тогда мы имеем
функцию,наблюдаемую с помехой;
Предположим,чтое!{х.) можно представить в виде линейной
комбинации о, ливейно-незавиоимых фикций *?i (X) :
d №) - %;• «Pi {^)^> - (т., •? с=»,
. глв
fttt?
?(*•) =
Тогдр восстановление байесовского ре&еющег-о правила сводится
к оцениванию вектора коэф^циептов Т"» .что moj$qt быть
сделано, например,с помощью метода стоадстичес«ой'ая1фокс>ша,***к
(ом. § 4,4,).
1.4. Автоматическая классификация.
Для успешного решения задачи самообучения необходило,как
это вытекает из рассуждении пункта 3' § I.I, чтобы в
пространстве признаков 6з*ществозаяй четко выраженные "компактные"
груша»* *еочек .Математичеоки строгая формализация задачи само-
о6ученкя',с-'*вдовательно1да5*-ща опираться на понятие близости
I
-v
27
векторов признаков и расстояния между группами векторов. Мы
рассмотрим три таких формулировки,позволяющих единообразно
охватить большое число алгоритмов автоматической
классификация. "
I.4.I. Кластерный авЕлиз
Рассмотрим обучающую выборку конечной, длины oct,..,, эс.
Пусть{Xi^'mXi,...,)^!- раэбизние этой выборки на М
непересекающихся додмножеств.Введам некоторую функпию d(X,ty) ,
характеризующую степень различия {шш наоборот,схдпства)
объектов, описываемых векторами признаков Ой и <£■ .0 помощью
зтсй функции можно построить критерий .характеризующий
качество разбиения {XU .Тогда задача самообучения будет состоять
в отыскания разбиения обучающей выборки,которое обладает
наибольшим качеством.
В такой формулировке самообучение называется также
группировкой или кластерным анализом.Очевидно.результат
группировки оуадэственно зависит от выбора мери сходотва-различия -
■ векторов и критерия качества группировки.Рассмотрим
несколько ирщеров:
Евклидово расстояние —
ds(x, V - 8* - ^ .(Z (Ж-"*- f*f)v'
равномерная метрика —
меттжка.п*зост13анства ***
раостошше Надалонобиоа определяется гаадратичной формой
£де % -выборочная ковариационная матрица:
}1Ч,г\1Л
28
мера Ддефриса-.'^атуси'гы -
rw(x, «*)=< X(VtetMi- УП^)г)^
ко&ф^щент дивергенции
Все перечисленные функции являются мерами различия (tiCx,^)
тем больше,чем сильнее X отличается от Ч- ),хотя
расстояниями в строгом смысле являются только три первые из
них.Рассмотрим также два Примера мер сходства:
коэффициент корреляции —-
"потенциальная функция" —
Для построения критериев качества группировки введем
понятие рассеяния внутри множества Xi;
2
Ш$ -
ШОч-i) J; |r-***xt dCxJ •
( H4-число точек обучающей выборки,попавших в Х{ ) и
расстояния между множествами Xi , Xj :
!еличш мсйено построй;
•шщровкн, н'априме р J
мгрупповой разброс -
Хк.ех1 эсе'« -
С помощью этих величин мссшо построить разнообразные
критерии качества группировки,напримерJ
рредниЗ внутригрупповой разброс
_средняя удаленность групп -
Можно оргвнйзоветь также различные комбинации этих покаэате-
V
1ь Ч ,■ W
метим,что eMmd("X,^}-«epa различия,» 9i подлежит миними-
| задай (разбиение |Х1|тем лучше,чем меньше Ч4 ),а ^г -мак-
;■ Химизации, воли scedC^c,^.)-мера сходства,то наоборот. .
I. 4.2. Разделение смеси распределений
Ооратшся опять к статистической формулировке задачи
лоиу>икащщ.Предположим,что векторы признаков объектов
-го класса имеют плотность распределения p-i№, V ) ,где
j V -яеизвеояыи параметр; и пусть Р ' -вероятность появле-
: в обучаицей выборке объекта из «• -го класса (априорная
ятнооть i -го класса) .Тоста в целом обучающая выборка
Рудет реализацией последовательности случайных величин,име- '
. плотность распределения
ксящую от набора параметров,
f-{ptl\-'..,ptMW">.--->'",'V.
Задача оамообучеюш заключается здесь в оценивании век-
< параметров 't" по обучающей выборке.Распределение с
ргаостыо вида (i.«.*•)называется смесью распределений,отсюда
'" Название подхода - разделение смеси распределений.После
'р как параметры \р , $"*}оцененн, классификация объекта
с -зектороп признаков эс = ЗС-(А) может быть произведена,
пример, с логлощью байесовского решающего ирмталги (i 3.1 if . ^
30
Итак,необходимо оценить-неизввстний параметре
плотности распределения pps ГС") .В математической статистике
разработано несколько методов решения §той задачи.Наиболее
распространенным является метод максимального правдоподобия,в котором
за оценку тг принимается значение вектора т*
,максимизирующее функцию правдоподобия \Е1 ^рф^р^.Мы воспользуемся
рекуррентным вариантом метода максимального правдоподобия. -
Обозначим Т-^ истинное значение.неизвестного параметра
тг и покажем, что т^. доставляет максимум функции
.Согласно известному в теории вероятностей
неравенству Йенсена [12.1, для неотрицательной случайной
величины ^
Отсюда имеем,
= Е^рЛгт^ 4 -^ Б рсг^д -
что н требовалось.
Вели рСэс/ъ) дифференцируема по Тг ,тоТ* удовлетворяет
уразценщ) %
Непосредственно найти f отскща невозможно,так как в зто
уравнение входит неизвестная плотность распределения,Можно,
однако .воспользоваться методом стохастической аш/роксаатацпи.
Применяя для рев?еьия уравнения (£.^2) алгоритм Роббпнса-ЭДон-
ро.получаем рекуррентной алгоритм нахождения оцоики максималь-
hoi-o правдоподобия:
ТиМ - т* - у„ Vt'£H,p{au«.>lX).
Подставляя сюда конкретный вид плотности (1.4.£.) и параметра
Пг .получаем рекуррентный алгоритм самообучения;
РСК~,Т-~) (1ЛЧ-)
i - I fftV.
(здесь учтено условие 21рн+А~ i).
Условия сходимости алгоритма Роббинса-Монро (теоремаЩ)
г*м данном случае на выполняются. В частности,уравнение(1.М.г)
"дай функций pC3e.>*tr) вида (i.4. t) имеет не единственное
решение (действительно,если ^~ -решение уравнения(i.ЧЛ) ,
шо вектор, отличающийся'от Т- перенумерацией классов,так-
является решением).Тем не менее при некоторых ограниче-
; на функции pi(X, t?) можно доказать сходимость- этого
оритма в вероятностном смысле к локальному экстремуму
кцни Vi(X)^
Для оценивания вектора параметров rft .особенно в
одномерном случае (X* 10, применяется также метод моментов.Пусть
"^еоть к -й момент случайной величины \t имеющей плот-
Згйость распределения pC^c.f), m,fc = Е ^ . - Очевидно, СИ*
^ееть некоторая функция от параметров Т", Mx^*^ fir) .Заии-
В&м еиотаяу уравнений Ягie ft(***),..- i W"^»£^t)( ty -раз-
ерность вектора 1Г), Если эта система разрезшма
относительно Тг ,
32
то поставляя в(1.Ч.5") вместо моментович,.~ ,m», их оценки,
построенные по выборке,^"te^£■ X-v ; подучим оценку****,
вектора T- tПоскольку,согласно закону больших чисел, оценки
моментов сходятся при у^-+о* к истинным значениям моментов (ло
вероятности или с вероятностью X), то при определенных
условиях на гладкость функции Т последовательность
уТ^Лсходится к *"t^ в-том или ином вероятностном емыоле.
1.4.3, Вариационная формулировка задачи самообучения
Веди нет оснований предполагать,что плотности PiC>*i,^)
имеют заданный аналитический вид,то можно сформулировать иеиара-
метрический вариант задачи самообучения.В основе такого
-подхода лежит понятие функционал среднего риска[ъ1Д22]Д£5"]
в'связи с чем он называется вариационным подходом к задаче
самообучения.
Зададим набор функщйС^(Х/"^ц),имеющих смысл
"расстояния" вектора признаков *Х от некоего обобщение?о "центра"
Tw i -го ютсса.Пусть |Xi\= \Х*,. . ^ХрЛ-р&збиение ^прост-.
ранства признаков К. на М непересекающихся .подмножеств.
За' критерий,характеризующий качество этого разбиений,примем
функционал
м .
- i-i x; '
Еадача самообучения заключается в нахождении такого разбиения
Ли таких "центров" Тг(1\ которые мшшмиеируют функционал
И .Полученной оптимальное разбиение к позволит производить
автоматическую клр.ооификацию объектов.
I*
33
Функционал (1.Ц.&") естественном путем возникает на -ооно-
||_ ве байесовского среднего риска (1.1.4} .Поскольку в задаче
самообучения -у нас все равно нет информации о принадлежности
.^объектов обучающей выборки к классам,то нет-смысла-и
расписывать функции di(X) из (1ЛА) в виде (i-3.3) .Вместо этого
Щ, мы предполагаем априори,что функции d i Ox) имеют заданный
f аналитический вид сЦСХ-)= tyiCVbtnrO*) и приходим к
функционалу (1-Н.6).разумеется?при этом мы уже. не знаем,соответ-
-^2 ствует ли оптимальное разбиение,построенное на основе функци-
Щ, онала С i.M.6),истинной структуре классифицируемой информа-
щ ции.
Используя Лемму I.I, лет^о доказатъ^о при фиксирован-
"^'ных'С(''разбиеш1е, мшшшзвдкщее R-, »Шет вид;
■ {f'",
_(«>
1-
(1.ИЛ)
^Используя эти соотношения,мояно исключить IXi^H3 числа неза-
^вйсимых и тогда критерий качества в задаче самообучения
примет более простую форму:
м »
V.M = Т. Ъ а (Х/^>)р(аа)с1х. (1.ЧЛ)
Условия экстремума атого (функционала даются системой
|_уравЕенийЧ
Вывод этих услоиий в общзл видз довольно славен Сем Г221 ),
Поэтому • здесь fie приводится .Зис.оото этого мы рассмотрим жрос-
! частные случай.хорошо иллюотрирущиЕ суть дела.
34
Пример. Пусть М^й,^ 6 В. множество Xi имеет вид
Х("|х: Х>Й-| .тогда
Б.» Б(й-/Й = ^^(x^^Jpcodjdon +
А-
Приравнивая к нулю частные производные от R noa. at
„получим*
U»(<vt-(t))-(k(ftA-(1>Jp(e4*c>,
Предполагая,что p(ft,) yl 0 (s области,где f>foe) eO .ггашиау
можно проводить произвольно).убеждаемся,что условия Ъкстре-
мума состоит из равенства (1.4,4^) и уелови.ч^(Ж,'Ь'")с|^(г,"гя{)
на грейте множеств A,, Xt .Но яла (й'нкщоналв (i.4.%)
последнее требование опр&шддиво по определению.
Применение алгоритма Роббииса-Яонро для ршпонда уравнения
(.1.4.4) дает рекуррентный аймрнтм самообучения
Сйлраулируом утаерждони'е о.сходимости этого алгоритма
самообучения»
'Неровна 1.3. Пусть ввнолнеин следующие условия:
I) плотность р(*) отлична от нуля на огрмшченном йноадоюе
А .обучающая айорка*«,... ,9Си еоетсглейа из неайшсимкх
одинаково распрэделзннвд с плотностью р(эс) , векторои"!
Z) фикции «Щзс.^У даК-ерешаруем! so втором;- «ргуменгу и
Vytyiftc.ty) удавдзтвврии усетяда йикмща
выполнено.условие
Тогда с вероятностью X существует конечный предел
li^n- &(^) = Е.„и на некоторой цодноследоаателшости И-^
кэчания, I). В теореме не утверквается^оходимость самой
Едовательцости т„_; алгоритм (i. N. io) сходится в ошо-
I сходимости последовательности значений функционала. При
1(1.4 И) означает,что нрадел R к является етащонар-
: значенном функционала £(тг) (но не обязательно глшшмумом).
К Условие 3) .твореыы 1.3. может быть заменено на одно из
.*** XiCt-)
; -г- fe T йТ„бТ, Уи, 1Щ?и атом утверждение теоре™
а*еея справедливым.
Доказательство ^сремы 1.&, основано на методе стохас-
кой шщроиснмшда. Ввиду его громоздкости оно приведено
жжении 2»
36
Fadoia алгоритма (1. Ч. £ о) проходит следутлм обряяом.
Па П. -и и.гв м;! имеем оценки параметров Т., ,.. . , т£Г' в
иа вход алгоритма поступает, точка обучапаей выборки Ж» .
Вычисляются эпачения фрюиЯ<Ц(Ж»,Т,,1и>)1 и ос' относи-
оя х классу о номером^-Аг^»Ч«п-<}'1С*»Г'""^Парамотр Т^'
иеняетоя согласно формуле (i, ц. io) иа
величину,пропорциональную JV .остальные'^* (t^*) не изменяшоя.Лоиуотим^
что в точение нескольких последователышх шагов изменялся
параметр одного и того же класса. Так над У«, умевшается
на каддом шаге,то последующие изменения параметров других
классов будут малн.это замедлит сходжостъ алгоритма.Поэтому
обычно пользуются модификацией ачгоретма (14. Ю),в которой
If», свое для каждого клаеое: *
£ ^11' - t еоЕь число точек,попавших в класс i зв Л.
шагов алгоритма ).
Рекуррентные алгорит.\ш имеют преимущество в экономии
памяти ЭВМ и простоте реализации.Однако, теоретические оценки
и практика показывают,что такого типа стохастические
итеративные алгориплы сходятся довольно менлениоЛюатому при не
слитом больших объемах обучающих виборок млеет авдед
стремиться к повышению эффективности ол-ropjrar эч счет змнишю-
кия и более тцатеЛьноЙ обррбэгки всей (хЗучпюцеГ: выборы*«
Рассмотрим метод построения шрегу^рен'гнюс мгоштасг. в
роаках вг.риашонпой ^орм;глпрспш задсчи самообучения. Ййче-
. 3?
даиа функционал среднего риоиа (I. ЧЛ) его оценкой-,построенной
по обучающей шборке X $ ,.. .*, Xjv ;
Согласно эакену большая чксел.Ц* fr"5 ^^"liCc-) с вероятное
отью I» До этому, если Тч. -эиление, доставляющее минимум
функции £и(Тг) .то при больших н. оио должно бнтъ близко к
'г; г=Лга Vrvin. &Ct'). Подобчая зшеяа неаззеотгого
функционала его оценкой} носит название метода минимизации-
эмпирического риека и широко испольэуетса в теории сценивашш Е5"] .
Фактичеики истод максимального правдоподобия является ч-ютним г
случаем минимизации эмпирического риска 1(см"# раддзл 1,4,Я).
;хшс,иам необходимо ш-^^зйрошть^щецию Ц.ЧЛЧ); за-
/дача 3ia осложняется паличиак разрывных функции *3^ (t>)&4
р Для ее решения иеяолъэуется гак наливаемый метод динамгчеокой
г^утшароЕки,которые предлагает оледатощий зтеративннё алгоркамг
дусть T-g -приближение,получеешее за S итераций, гогда&41)-е
приближение ищется как решение акстремальаоЁ задачи;
tti: как здесь ранение {XitT'j^} зафиксировано,то роить .
■Ту задг<"у намного проще,чем жходнув.яе многих случаях для
'•едого достаточно решить систему*
Z \1Ч) (хо V> %i (»«. ,^(11) - о, i«f,.. .,M.(ti.i6)
?Докатвм су'одш.гасть алгоритма дикамичеокоЯ грунпировгг.
feopsBa, F,4. Если Т^тройтел как ревеяие.ясотремьльяой за-
BflSra<t,4.15) ,то пгедедоватблЬ1!ооть(Е.я('С1^}являето(» навоэрао-
38
IvOJETj» ! -решение CUCTStn (1,4.16) ,8 JjyuiuiM <{{(»,f'0)
удовлетзоряэт условиям
(т.е.являются внлуюи&ш), to iraate ощшвадлтео (1.4.1*)
Доказательство: Применяя Лемму 1.1 д.!ся
ползшем
Уч1Глшай,что 't'j* j, -рыкание экотр&мальиоа задачи (1.4. is) t
у&вд£.емся в справедливости неравенства (1.4, it) .
Если выполнено (i. Mil) и t^j -решите сйстегда (1.4. i&) »то
39
ч*о пош-одователыюсть R n (TTi) имеет предел (при
' g_-e ),поскольку она не возо«стает и ограничена снизу. А
{рак Kait множество всевозмсшшх раа'йявакв обучающей выборки
. .,х„конеч1ю,то эта последовательность на некотором ware
fj,-t>" стабилизируется.
ГЛАВА II. ЩШКИ ТОЧНОСТИ АЛГОВШЗ РАСПОЗНАВАНИЯ.
МОДЕЛИРОВАНИЕ НА ЭВМ
2Д. Оценки достаточной длины обучающей
последовательности
В главе I мы рассмотрели множество различных методов
построения решшщх правил. Выбрав подходящий алгоритм и имея в
своем раопоряжения обучающую выборку мы можем оценить решающе,
правило и тем оамым решить задачу распознавания,Но можно л*-)
гарантировать,что найденное решение будет действительно
оптимальным? Практически вое алгоритмы являются асшпто'глчес-
кими.тс есть лишь в пределе при неограниченно!^ возрастания-^
длины обучающей выборки они приводят к теоретически
оптимальным разделяющим поверхностям.В нашем же распоряжении всегда
имеется обучающая выборка конечной (и часто - небольшой)" длины
Итак,основной вопроо.на который надо ответить - сколь
точно можно аппроксимировать оптимальное решающее правило с
помощью решающего правил а, построенного по обучающей выборке
конечной длиныТ-Чтобы придать этому вопросу точный с.ю/ольо6;/1~
тимся к статистической формулировке задачи классификш^ш.Нам
задана векторная случайная величина ^ ,значение которое
есть вектор признаков объекта,поступившего на вход опознающей
системы.и случайная величина tf , значение которой есть номер
класса,которому принадлежит этот объект.Необходимо найти
решающее правило ££к-/Т") .минимизирующее функционал среднего
риска
R(f) = Elt[-l(^)]2 (a.i.i)
Это решающее правило и является оптималь^-йй
Для решения ?тп? зйд?чи у нас гс-теется обучею^я последо-
41
вагсльноотьXt,,..,Эй*,векторов признаков К 'объектов.для
каждого из которых известна его принадлежность |1(,,, f •? ^.
Рассмотрим оценку функционала (2.1.1) .построенную по обучаю-
%:
IBi. л принем за оценку оптимального значения параметра тч =
&--=ОЛА Trun-Hfrc) то значение,которое минимизирует, вмшри-
"чёский функционал ореднего pH0Ka(2.t.£):Tw=<W#mj.>i-£;"ftr').
.Hp'ifeK упошгаалооь ранее,такой подход называется методом
минимизации амцир.гчеекого риска.
Согласно закону больших чисел,выборочное среднее стрзмит-
: к математическому окиданир.то есть5.»(гс)-»Жтг)!1риИ,—»■» .
£>-Что справедливо при любом фиксированном f .Однако следует
„что т\ и *с будут такие близки при больших к?
;Bicjhok ЙЛ.показывает.что это вообще говоря не так,поскольку
КЙайроо функции £и(т)хотя в одной точке может привести к тому,
bfjifl 'С-. будет сильно отличаться от Т« .Это будет невозмож-
i
г £5
*!>'"*'
•^
4-V
—Л*.
■''F*'
'"П.
К.Стг)
Р.(тг1
. "*!■
Его. 2.1.
НО, если R „(f) при воех тт отличается ст'Я^тг)не более чем на
Ц$адую величину * . Действительно,предположим,что
suplfcCTl-W-rilH*,
адда ТЦтг„) - Ъу~(Ъ-) i% и йпСтт.^-ЦСт-.Н * ,а так
Т"» и т» -точки минимума функций Щт) и R»ft^oooTBeTcT-
42 -. ■;
'венно.то Я(тг») « И(т») , В.«(Т^ 4К.-(т-»,'!.Из этих
четырех неравенств непосредственно вытекает:
Таким образом,необходимо.чтобы вшшрнческий функционал
еходился it теоретическому равномерно по Т" »то" есть должно
они.
«^р{вир|ц.„(чг>-я(тг)и*> = 0. (a.i.»)
ft-* •# '■t J
функционал ореднвго риока гфодарционален. вероятности
неправильной классификации (см. (iЛ. А) ) .Эмпирический функционал тогда
щюпородонален. -частота неправильной классификации,вычисленной
по обучающей выборке .Следовательно, выяснение условий,при
которых имеет место(2,. 1.Ъ) .сводится к решению вопроса о
равномерной сходимости частот событий к ох вероятностям.
Пусть задано реаающее правило $(&,-?), Каждое значение
параметра ТГ определяет ообытие А(т) .заключавдееея в том,
что вектор \(и))непра&1ЛЬЕО классифицируется решающим правилом
i-C&fe). Когда Т* пробегает все множество ■значений,мы
ьодучаем семейство событий S = {A^t* )%*t*« Ц*г j. .Равномерная
по t* сходимость функционала UnCt*) 'эквивалентна
равномерной по семейству S сходимости частот событий V(A)к
вероятностям V(Pi) .Иначе говоря,нас интерооует сходимость к нули
максимального по классу S уклонения частота от вероятности:
PfttfOl **}.-*£, rae^r^SUg^CAbKA)}*
■й»(А) -частота появления события А на выборке длины "К .
Классичеокая теорема Бернулла [Zt\ утверждает,что для
любого фиксированного события А
однако не для всех беоконечанх семейств событий имеет место
равномерная сходимость (см. [5"1 ).Ъ простейшем случае,когда
S состоит из конечного числа событий^ равномерная сходимость
-вгда имеет место и можно дать оценку величины уклонения
Теорема 2.1.Для класса ообнтай S .ооотоящеи нз Л
Доказательство .Случайная величина j*(A) имеет биномиаль-
'^Ье звспределвние
тому <
P(li(Al-PCA)|>*} = £'^P"(A,)U-P(A^-,:
сумма берется по к ,для которых 1я - Р(АТ| * в.
i Sup 1$я,(А) - Р{АМ > ft } означает.что по крайней
для одного из событий А(,.,.,Алсправедливо неравенство
По тесреме о сложении вероятностей
f{nt(H.)t>*}*jtz'c^p,'a)H-p(A>r;"
В силу интегральной теоремы Муавра-Лапласа lZt\ правая
. этого неравенства может быть оценена сверху величиной
Sa»?(A)U~ Р(А)1 -диспероия случайной величины 1)»(А),
имальное. значение величины С равно g (при V(k) = jr)j
и
Ч1ри достаточно больиюс И. ( И>1 /йр"** )отоида
получается неравенство (2.1.4).
Рассмотрим бинарное пространство яриэиаков.Б котором
значения компонент векторов признаков равны либо О либо
I,как,например,для пероептрона Роэенблатта.Так как всего существует
' 2/* различных .М -мерных бинарных вендоров, то число их
разбиений на два множества нонечнэ.Б частности,чиоло разорений с
томощь» линейных правил К < 2, .Потребуем,чтобы вероятность
Р{8ир1^н.(Ак.)-Р(^«:)|>*} не превосходила заданноге
числа^ :
p{supli(AO-P<A«>l>*}<t-
Согласно(г.1,М),8То будет иметь место.еоли
Разрешая это,соотношение относительно & либо -С ,при~"
дем к еледуинему рез/льтату^сли из конечного множества /J
решЕлцюс правил шйкрадфся кр&вшло,которое на обучающей выбор
ке длина & 'имеет наименыау» частоту ошибочной клаооафйкащш
У ,то е вероятность» "i - *£ мсянд утвервдать^что "Ц
отличается от вероятности оидбкн сптаиального решающего правила
Ее более чем на велнчйяу
о другой стороны,для того.чтобн о вероятностью \~ £ частота
отличалась от'вероятности ошибки не более чем иа & ,обучак-
Яьй выборка должна иметь длину не менее
{ 4 еоть точность избранного рещаадэго правила, а £ -надеа-
воо:ь :
т£
.« Если число решакщах правил бесконечно,то получение оценок
ИпвСг.С^ораэдо сложнееГВместо К. в етом случае вводится
[вивальная характеристика - функция роота.Развитая в С У] те-
равиомерной оходамооти частот событий к вероятностям при-
т к вняопенгав необходимых я достаточных-условий равномер-
еходимостк.а также дает опенки точности приближения час- i
5 к вероятностяк.Полный вывод этих оценок и условия о.чода-
Ш довольно сложен.Зцесь мы его приводить не будем.ограни-
:ь рассмотренным простым частным случаем конечного ыао-
правил.хорошс илдвстрирувдим основные моменты,1
В качестве рецепта,которым можно пользоваться при выборе
обучаящей выборки и сценке точности алгоритмов распоз-
,прчведем слеяупцив резуаататдая линейных ретагарх
ш в пространстве R" длина обучаэде* выборки должна бить
if'roro,чтобы о вероятностью !-■>£_ частота ошибок эипнричес-
sro решающего правила отличалась от вероятности
оптимального решашего правил» не более чем на & .
: отсвка € через С (с пгчощь» неравенствами^ <j|:$,
i точность при заданной длине обучающей выборки:
Подробное наложение теории равномерней оходямооти и ее
$ний в раопознавания образов и теории етатиотического,
t можно найи в книге 15] .
46
2.2. Правило останова конечяосходяшихся
алгоритмовт обучения
Применение конечнс«чожящихс& алгоритмов в
детерминированной задаче обучения гарантирует отыскание разделяющей
поверхности за конечное число шагов алгоритма.Но каково именно это
число шагов - неизвеетно.Более того,далее если мы сможем
оценить число исправлений,которые претерпит вектор параметров Т",
мы не сможем сказать,когда же остановится процесс обучения,
поскольку это зависит от опоооба выбора обучавшей
последовательности.
Еоли наложить определенные ограничения на отатиетику
показа обучавдей выборки,то можно гарантировать с большой
вероятностью достаточное качество разделяющей поверхности.Мы
будем предполагать,что обучапдая выборка выбирается как последо -
вагельность независимых случайных векторов,распределенных о
пломостьв Р(х) на множестве X. Цуоть }*(х-) -разделяющая
поверхность,а f -вектор параметров.поотроенный о помощью ко-
нечносходящегося алгоритма.Качество ревевшего правила f(cc,nr)
определяется вероятностью ошибки:
Сформулируем следующее правило останова:алгоритм обучения
останавливается,если после некоторого к -го исправления в
течение Tn-'и) шагов исправления не происходит.Покажем,что при
С9ответотэувдем выборе ф/шштШ-С*-)можно е.большой иадеж-
ноотыг гарантировать высокое качество разделяющей поверхности.
Теорема 2.2.Дуоть в правиле останова
47
Зав 0<^*1, и, -любое целое число, И->1( ^(n.) s.Z pi —
: ^ункпЕЯ Вмана. Тогда справедливо неравенство;
P{£'(f)**} >i-l. (г.гл)
Доказательотво.Пуоть Тг*к -вектор.полученный. после К -го
ленкя.Вероятнооть тоге,что останов ироизойдег после к-го
ления(но до (К41)-го),равна Ц -^jtftv.)]"""Чумовная
ятнооть трго.что алгоритм остановится яри условии,что ка-'
Ьтво разделяющей поверхности ^tCtV) =• Ц-,равна
ложим.что случайная величина $ГСпО имеет юютнооть
расселения <},ty),тогда вероятность того.что алгоритм оставо-
йтся на векторе,для которого качество решающего ярааила боль-
^другой оторрнн.эта вероятность равнаl-p^fflr) 4 А} ,
f -вектор к* С*-2-^Выверен йгякянв Ж-(К) из условия
\m-CK)
|1; Л- подберем так, чтобы
Й-ен.ои.ен.^-^н^и) )Соглаоно(г.а.а) wtflQ-^flffigS
;|ть совпадает о выражением (гДЛ).При этем выполнено не-
|нство (а,2.2).Теорема доказана.
gS качестве примера эаиетим.что § * ^- при и>« 2 .
48
2.3. Моделирование процеосов распознавания
на ЭВМ
Для иооледования овойотв алгоритмов распознавания удобно
пользоваться специальными модельными масоивами информации. О
этой пелью на ЭШ генерируют данные, обладающие требуемыми
статистическими характериетикамиЛо результатам применения
алгоритмов распознавания к этим данным можно оценить эффективность
выбранного алгоритма,подобрать наилучший алгоритм для решения
определенного крута задач и т.д.
Методы получения числовых последовательностей о
требуемыми статистическими характеристиками и их использование для
решения различных задач составлявт предмет метода отатиотичее-
ких испытаний,или метода Монте-Карло {el, 191.мы рассмотрим
йдесь некоторый круг вопросов этого метода.которне будут но-
лезны-для моделирования процеосов распознавания на ЭВМ.
2.3,1. Генерация псевдослучайных последовательностей
Последовательности чисел,обладание статистическими
свойствами случайных величин,называют псевдослучайными последова-
тельностями.'Оказывается, задача построения последовательности
с заданной функцией распределения сводится к более простой -
к построению случайной последовательности о равномерным
распределением. ^
Теорема 2.3.Пусть задан набор чисел \ *0, 2И рк = i,!
и ^ -случайная величина,равномерно распределенная на
интервале [0,11 .Тогда для случайной величины \ .определенной
соотношениями
1=К .если £Pi«%*XPi. (a.S-t)
43
дливн равенства) P П * ^ { = P* , К » 1, ...,//,
Доказательство,Нескольку
H1S0C1"X. же№П, (г,.ъ.г)
= р{}*|М~р|1фф
Теорема 2.4.Шгсть ЩЩ-монотонно возрастающая йгнкцня
^деления, | равномерно распределена на [0, i~\ ."Тоща
ная величина *[ = G *( ^ ) имеет функции раопределения.
Доказательство. (Заметим,чго,функция U" , odj твая к &,
*твует и также является монотонно возраотающей.в силу ра-
(2 5.2)
P{^x} = p{r,-'(|)43e} = P{^G('K)bG^>i
й требовалось доказать.
Поскольку в математическом обеспечении довременных ЭВМ
стандартные программы генерации значений равномерно
военной случайной величии',то -задачу "построения-оду-
t последовательности о любым заданным распределением нок-
:ать практически решенной".
-*В .некоторых случаях обращение функции £ может быть
сложвым.тогда для построения случайной величины прибе-
'к специальным приемам,Рассмотрим, например, поотроение нор-
едучайвнх пооледовательностей^Есдй. £ „ равномерно рас-
,*енкяа[0,1] ,то
50
Согласно центральной предельной теореме,случайная величина
имеет при достаточно больших tt распределение,близкое к.
/\f(0,1^ ш достаточная точность лодучаетоя уже приК=10;слу-
, чайная величина ^ о раопрьделеняем''(й.О'2) получается из
стандартной нормальной величины V во правилу^ »W 4 + О, .
Набор -J = (^^.1, ^)незавиошшх стандартных норчальнвх олу-
чаВннх величии образует W нквтанй BeKTOji о нулевые средний в
единичной ковариационной матрицей.Вектор \ - В^'+ <*- имеет
нормальное распределение со средним вектором Л. и матрицей
ковариаднй ВЬ .
2.3.2. Интегрирование по кетодт Монте-Карло.
При оценивания эйектигнооет ретагашк правил приходится
вычислять вероятность неправильной классификаций,а это
приводит к заделе вычисления интегралов от бувкщя» многих перемея-
них по областям,кмепким иногда довольно сложный
вид.Аналитически ваять такие интегралы не удается и приходится прибегать
к приближенным метсдам.Одюш из методов численного иптегриро-
вавяя является использование поевдослучайгах последовательно-
отэй.
Пусть требуется вычислить интеграл по
области X ь R," Доли \ -случайная величина с-: влотностьи
распределения Pf») .отличной от нуля на «яокеотве X , то
Это соотношение указывает на способ приближенного внчислевия
интеграла,поохольку в силу закона больших чисел выборочная
51
■Ш опенка математического ожидания ояучайной величины f(f VP("5)
Ж сходится к •зш.
Теорема" 2.5.Пусть Xtl - -. , ^^-последовательность неза-
случайных величин о плотностью РСс), сосредоточенной
^^яа множестве X С Я .Положим
*^д^огда для любого О <. & t 1,
Щ'_ Ц1^-эши^£ }>i-S (г.э.а)
fr^ Докдоательетво.Теорема представляет собой просто
формулировку закола больших -чисел в форме Чебнцяда t&O^fa?] для кон-т
Цветного олучея.Упомянутцй а&^н утверждйет^что дхя неЕавися-
^<4?далс одинаково распределениях случайных величин ^ и, со средним
&. и дисперсией S"
-cM*VfiM-«.
как легко убедиться, Т> ш есть дисперсия случайной вели-
5*шшКх».)/КЛ.»).
уормула(г.1.3) дает возможность оценить длину последсва-
Ц тельнооти 3it,,.. . Хп,необходимую .для прийшжения интеграла
.■3(f) о требуемой точностью.Однако зта оценка является силь-.
'но эав«1тецкоЕ. Лучшую оценку можно получить с помощью цептр&ль-
|* ной предельной теоремы,согласно которой величина
/живет при больших п. распределение,близкое к нормальному о
Рунулезш средним л единичной дяояероией.
ГЛАВ* Я1. РАСПОЗНАВАНИЕ ТОЧНО РАЗДЫШМЛ КЛАССОВ
3.1. Иероептроп Розен&гатта
Дерсмгероном назван },Р{)зенбяатт построенное им всервдя-
но 50-х годов электронное устройотвсопооойное обучаться уз-
ьаванпл простых ой^вктов.Первоначально нерсептрэк возник as
■ стремления промоделировать некоторые $$нкпии мозга человека
(зрительное вобяривтйе.уэнавание.офчение^в прецесое
исследований,овязаянш с персептровов .офсцсншс! принципа
современно* теории раопознаввяачойразов.
Охеаа пероептрона Езойрввена'ва рис. 4-й. Основным эле-,
гантои героегарова является так вазнваемнй пороговая элемент!
Рао. 3.1 . Пороговый мемаът,
Зсроговнй вленант гмеет аюкояые входов и один внход «г
функционирует по правилу г - bg.n ( £ Х<, ~ Зй„^ ,
где 4»»)i ft'*»»'
-некоторая константа,
S
Рис. 3.4 . Переёптрон Роэенолатта,
W
тш?
53
Переёптрон состоит? из слоя фотоэлементов С S
-элементы ил* сетчатка) ,слоя пороговых элементов, назнваемах аооопи-
'атившаш ( А -элементы) (реагируэдэто до-рогового элшеята
( Ц, элемент) и вичисштельного устройства КГ.
Изображение объекта проецируется на сетчатку и о
фотоэлементов сигналя о наличии или отсутствии света в каадой точ~.
т сетчатки поступают на А -амемеитн,0»взя мевду S - и А "
,, элементами выбираются совершенно случало «.С выхода А -эле-
'мрнтов сигналы через усоагктслн 5 поступают на £ -элемент,
который-либо выдает выуодной сигнал либо '"шлчнт*'.Допустим,кы
. хотам обучить переёптрон узнавать буквы А и В.ТТотребуом,чтобы
при появлении яа входе пероептрона букв&0 сигнал на выходе^
пероептрона появлялся,а кяк %^©ы £ - ,от%тстьсшатг,Обучение
пероептрона реализуется с помощью вычислительного устройства
ВУ н переменных коэффициентов усиления усилителей.
11а вход ЗУ додается информация о том,какое имение кзеб-
ражение поступило на вход пероептрона.(указание учителя 7У);'
допустим,УУ=1,если на входе Д. н УУ-0,если на входа S. Тогда
если % - ТУ,то переёптрон правильнс ерзагировал на изобрадо-
ше.если же Тт^УУ.то произошла ошибка н тогда ЗУизменяет не-
которнн образом коэффациентн усиления.Правило' изменения весов
(алгоритм обучения пероептрона) должно битв построено таим
образом,чтобы после показа нескольких изображений переёптрон -
емог научиться правильному узнаванию.
Рассмстрин персептрон о 'точки зрения общей схеш
распознавания образов(сы.ьараграф. 1.1 ).Мы икеем два класса: #Ц -
букш Ае ^-г. -буквн В.Вектором. признаков X /еоответотвую-
вдщ данному изображению,будем считать набор вьцгодоь А
-элементов. Обозначая nrtv) коэффициента уаакеняа,похучаи правило
54
функдаонироваиия R -элемента (через t°i обозначено
количество А -элементов):
N
Задала обучения переептрона состоит в построено такого
ректора весов тт ,что
( >,о для, «tXi,
' <0 для, ХбХг,
где />i -множество в R.", соответстзущее объектам класса Ok-
I.Воспользовавшись теоремой 1.1.,доказать,что оледувдий
•иггоритм обеспечит оходимость процесоа обучения пероелтрона за
конечное число шагов:
о _ | i, если_е^(тг,,а1„)г,£^
1 " ~ 10, есля ev>(o-„, я;„1 >£>,
и»_эе.. г" №F «
е»"-1 для бута А в<5", •-! для Б, fl««t<\&l .
2,Дня данного конкретного вида разделяющей поверхности
можно обосновать конечною сходимость более простого алгоритма
обученгаЦсм. \.5] ).
а-в,1=ти + Лте„, (o.i.i)
Нашей уэлью является построение демойстращошю* модели
персептрона на ЭВМ,
З.Яла моделирования персептрона на ЭВМ пестрой» слелувш!
алгоритм выччоления признаков, В .пом. ЭреийВ введет ка^ор
линий,называемых зондами, и будем считать -X,
равным числу пересечение изоораямиш с i -м зоэдом,Напасать йро-
гранту.ре&шзущуй вычисление таких признаков.
* _ 4.Написать програину для ЭШ .моделируацув персептрок.
if Изображение буквы должно взводиться на экран вместе с зондами.
fri Ввод маооива;опиоываящего букву,осуществляется о.перфоленты,а
^указание учителя вводится о пишущей мапшшеа.Обучение нереедт-
рона осуществляется в соответствии с лрьЕилом ('i.i.i),
б.Лодготовить обучающую ьиборку и провести обучение пер-
К; ееатрона.Если однократного просмотра обучаадей выборки оказа-
&яооь недостаточно,поморить оОучение.Для оценивания
необходимой длины обучаэдеи выборки воспользоваться результатами па~
'^вагрЕфа 2.2,
6,По литературе изучить вопроса о возможностях переелтро-
_на и о тех задачах из области физиологии^Ьтсрне привели к ево
«созданию.
Литература: 13] Д5] ,[14] ,122] 126]..
3.2. Конечносходящиеея алгоритмы обучения
распоззавЕЛИю образов f
Цель данной работы - исследование алгоритмов обучения ,пс-
jfc строенных на 'основе,двух вовечносходящахея алгоритмов решения
оиотем неравенств:
(X, W-'j * V > О
а также
(X, м)-ЦМ8г>0.
I.Проверить выполнение условий теоремы I.I.B предаоложе-
вии.что существуй такие w»V». и й„?0 .чтоУхаХ
fi(tt.tV|*(*.•«.) + V» >■*», т-[" J, (З.г.1)
^(■X.-ul^Cx.'U»)- Щ^И*»"*».'
(гг.г>
56
2.Пуоть множестваXi, Xt в нроотраыгае нризнаетв.соот-
ве^ствугаще объектам двух кяасооБ,разде.шш гиперплоскостью.
Ярииенить ж этэй задаче конечноеходгаиеся аягорилш.волучае-
-ннв из общего алгоритма (Ц.(>) ,(1.2. ?i дай &yrataje(4Zi.),(V1.2).
В первом случае яолучавтея алгоритм)
-и».!. •««+«& «Мл. л„, (5.г.&)
Й„ -указание учители ( I дяиХ„бХ4и -I для ijc^-Xj ),
' * 1.0 иначе,
Т6»^чиоло изменений векмра йареметров за « шагов5,
алгоритма, ^ в fes]?
Алгоритм во втором случае:
ы„41 - м„ + а„1>вв^(<11.в-а«.),
Иосг-едоввть геометричеокую интерпретацию эвя алгоритмов
3.Нависает, проградаы.реалгзуетда оба алгоритма (взять
j3 = tCn4*B качестве параметра лрогрзммы). Снабдить алгоритм
обучения правилом останова (ои.параграф 2.2.).
4.Смоделвровать обучающую выборку,йзваеченнт» аз двух
классов, разделимых гиперплоскостью.Длина обучающей выборки
должна быть выбрана в соответствии с 2Л.,Я.£.Смоделировать
акзаменационну» выборку и провесгй эюадврйнеит по обучении и
оценке качества распознавали.urrejseiypa: 1221 .
67
3,3. Разделение нескольких класоов
Пуста в детерминированной задаче распознавания число
классов М. больше" двух'. ~*Ддя этого случая иогут бнть предложены
различные метода построения алгоритмов распозвавашя(см,напрн-
г- иер,[?1 ЛХ21 );Мн здесь рассмотрим путь,естественным обра-
'' зом возникавший из общей вариационной постановки задачи классу
* фккавии,сформулированной г параграфе 1.3.
Дидполояим.что распределение векторов прюияков.соответ-,
^ствуичих объектам 1-го класоа,оосредоточено' на множестве Хц .
" пеней иножеетва.соответотвуящив раяличввм классам.не первое- '
IiSDynrana достоверяоота прияадле»нооти(1.з.З)превраие1)т-
cs в этой случае в нвдкатори «шожеста X t;
jic»)-^if«j-{o:**-'
.а функционал среднего риска принимает вид i
(i.u.)
(9.3.2)
Првднологим.что для каждой пара «иоавств Xt , Х«
существует разделяющая функция
- аналщт^ески? вид функша,Рк,; (ТС, тг") предполагается извест-
ннм.Эадача»таким образом,состоит в чахо*дениг аеизвеотиогс
векторного параметра ^м ,
Выбрей функции Скл.<х.,тг^ в(г.Ъ.1)сяедущим образом;
вв
j-:|
to , k = -i.
2,Из(З.З.гУ(>.1.4)ораэу следует
геем* XiCXiCt.).
Рассмотрим градиентный алгоритм!
tj.t ~т-„ +tXtjr.<""4x.(«-1|t()iltB.0(oB,)7cfKi(=u«1t-.y,
*<*«
X?"*i. K*i; K,i-1,...,M; £c'l> 6 [<U] .
Теорема ЗЛ.Чуоть выполнены следующие уоловия:
-I) feHKiniBl1ftii(X,t)|vtl?rfiii(ai,'r)e ограничены равномерно во X
13 X ';
2) существует вектор т; и число fe ;>о, для которых выпол-
... вево(5ДЪ);
■ !з5для лвййпарн точек|*,т^б?. х R. справедливы веравенотва}
Тогда алгоритм С5.1.Ч) является конечносходяиемоя.'Го еочъ
для любого т^е R г произвольной попледовательносшХ,,...,^,
Х^бХ найдется такое дало Л^ {эавиоядее otXj.,. ,.
.,..,»«, ....,t\;,«o
Доказательство.ilj'C'b на W -и ааге^Сю^З^^рс.,]-!,
5S
нек.оторвх K.,t i .тогда в оилутретьег^у&аовия:
»t„„ - t„ «»* Нт. -т. Ц** (xl™? Й^С*»^-!»'+
4 Итя -тЛг* (rf)* U^-Pti(Xn„T^H^
Согласно определению множеств Xi (tr) (имееи для i * К,'
Поскольку К ф i р то ореде множеств,стоящих сод знаком
пересечения, имеется множество > {С^;. <. О \ Л Х^ ' (соответству-;
ющеэ ). * К. )и следовательно,
3.~С помощь» условий теоремн и соотношений (3:5.*|)
/ценно доказать снраввдшвость неравенства
1Кч -'Т, И*Г H'CW -Т. И* 6 f**, .
где рад нз неотрицательных величин й*. расходится.Отенда и ,
следует конечная оходимоси алгоритма,Эта 'чао*ь доказательства
почти вэтяостьв повторяет доказятельствз теоремы I.I.
4.Язвестно,что в случае двух классов алгоритм ойучегоо» с
поощрением является градиентным для функционала
'см. 1*1 ,стр.й5).5тот фужцконал мояго цргаэотТ к виду
(S.4.-1) , ec.m m!OrraTbC!i(^.^)-*fc^,(Ui(sl.'^~
ее
б.Еоли разделяющая функция Ц5аСХ»"С) зависит только
от "овоего" параметра tit , «f,^ (X,Tr) - f „x (х,а-<(->),
<Г=1-г'0 К>ч.дД»1,..,М},ю (J.3.4) распадается наМ(М-1)/2
равенств для каждого из T(tU.PaccMOTpeTb частный случай
алгоритма (&.э.ч) ни равдедящих функций вида (M.i).CpaB-
нить этот алгоритм при М=2 о алгоритмом (4.2.S) .
Е.Напиоать программу, реализущув полученный алгоритм.
7.Смоделировать обучащие выборка для нескольких значений
;' М .-применить *с ним алгоритм классификации,исследовать его
сходимость.При определении необходимой длины обучающей поеле-
, дозательности воспользоваться результатами глфзы II,
Литература: ЕП, [221,
3.4. Построение кусочно-линейной разделяющей
поверхнооти
-До сих пор мв предполагали,что классы в пространстве
признаков разделимы о пояощьь. функция простого вида,как правило,
линейной.Что делать,если множества Xi, X&. не разделяются гя-
пёргогаскостьвТ Иногда и в этой случае можно свести задачу к
линейной,например,если и?вестно,что разделяющая поверхность
ямеет вид Xt^A-i (X) ,где | ft. i„(3t)^-набор лзвеоишх
функций» Вели сделать замену леремешшх X — ^ , y.w • <Х,\. ре.),
4.* {,...,£}. (которую обычно называют переходом в опрямляющее
пространство),то разделявдея. поверхность будет в новом проот^
ранотве гиперплоскостью.
Чаще однако не" удается указать тжЛ набор |й,;&$]до-
статочно простых функций,а приходится иметь, дело с нелинейкой
разделимостью множеств Xi , Xj. .Мы рассмотрим здесь один
из методов решения этой задачи,связанный с построением так яа-
61
' знваемого комитета неравенствЗозмакны и другие 'подходы.как
* например,в методе "обобщенного портрета"(см. 1^1).
Пусть в простравотве признаков К задано К гшгергаюо-
.'коотей (И."» се.)**»" «О,- 1-4,...,К.
Определение.Рбшашее правило вида
называется комитетом неравенств,основанным на принципе болышя-
отва голосов (или "Комитетом-!").Число К, называемое поряд*
ком номитета.ддя "Комитета-1* предполагается
нечетным.Очевидно, "Комитете" относи? точку, "X. в множество X», если для v
бслынизотва гштерплоскостей она лежит в положительном пелунро-
стройстве.
Определение.Комитетом.основанным не пркшипе единогласия;
("Комитэтом-11")аазывается решающее правило вида
■х. а Х4 , если (tct£>,'*>.+ **' > О дои воех*"1,.-Л
"Комитет-11* откосит точку "X. а Хг.если хотя бв для одной
гиперплоскости точка X попадает в стриительное полупростран-
cTBOiBastEHM явдяето! вопрос о сущетвовании комитетов.,
1.Доказать,что если выпуклая оболочка множества Xi
отделена полонительннм раоетокнием от множества Х4 ,то
существует "Кошшет-П"конечного irapwn», разделяющий" зга кножества,
,Для "Комитета-I" вU21 доказано следующее утверждение!
еыы клааси Х« . Хг. 01тжшчш№ и рбзделены положительяым
уаостоянчеи.то сущеоетует разделяяаиЗ их "Комитзт-1" конечного ,
Порядка.
Алгоритмы построения комитетов конструируется по анало?»»
е чоиечносходя1,!ккся алгоритмом (й.й.З) (при At» i. комитет пре-
И*->
вращается в ^делянцу«кпшер]иоскость).Пусть ооучащая
выборка **!,'■.. , *-п, навлечена та двух яепереоекащяхоя множеств
X i, X л #Д?я когорта существует разделяиций комитет порядка
К., и пуста f {*•) -какая-дийс разделявшая {ункпия,
>0 для oceXi,
< О для ЗС в Хг ,
%рть к .КС -му шагу алгоритме построен наборов',$J',-t*i,...,к}.
.'Для "Комгаета-1* вIX21 предложен следующий алгоритм.
Чиж' ^(x„)^MJ»l(«li>.-*,w>+tfia'l>0.
so<^i»W. ^5"^. <.-1,...,1С, '
В противном случае' параметра гиперплоскостей переечятшмштся.
-Зредподожт.что *»2.U * i .введен числа
в упорядочим юс по величине.Пуоть Ч*' * 0, • ■ ■, '£Z) s О , -
a it"' >0, • •. ,- l"u* lV>0 (miL+i .).Тогда
«,a<j>, «& - W
i-i^.-.u,"1*!,---^!-*!;
,гй
«W-*1"1-^ -TTPS5»
|jvt- i»L+i,-
. Аючритм построения'"Кггатета-П'геОЯн
5(3
: .-.IP
*Q'-«»i
И1Ч1
,c'b
- *?•*■-£-. f?tr»
Льва
й1 = f 0, если («!?, л.) * Л" ^ wvfM.Kuf'.x.)* Vl%
Эта алгоритма носят вврястагаеонни хьрактер.доказательотво
тс сходимости отсутствует (теорека I.I. здесь
неприменима).Белое того.извеотин, прине!» ннмеотв Xi, Xt.когда сходдгооти
нет (си.[г21 ).Однако,вкспершенте ва ЭШ показывают,что в
вольявдаетве ситуаций алгоритмы работаю достаточно надегао.
г.Иооледовать геоиетричеожую интерпретацию алгоритмов -
<ом.1Ш>«
З.Нашсать программы,реализующие алгоритма построения
комитетов.
4.Получить овучьпше выборка для юкяеотв.раэделиинх с
лсиощье комитетов обоах типов.Применить к ним алгоритмы.ис-
оледовать их сходимость.
Литература: [51,[22].
СТША IУ. BEPfflTHOCmffi МЕГОШ ПОСТРОШЙЯ
ишпих пшад
4;1. Метод максимального, правдоподобия
Пусть имеется повторная выборка OCi,.,., Хк
-последовательность независимых одинаково распределению; случайное вели-
. чин.Цредпошжим.что задан аналитический вид п плотности
распределения РСх) ,то есть онг известна о точностью до
некоторого параметра Т"
Р(х) = р(х,т), тге Rp.
Необходимо построить-оценку неизвестного параметра т~
Одределение.Опеяков максимального правдоподобия, (о.м.п.)
называется значение т- доставляющее максимум зЕуякцш
правдоподобия ft РСХ^Т") ил»,что'.: то же самое, догари^шческой $унн
цки правдоподобия
Иввестно.что см.д. обладает рядом полезных cboSotb.b чаотн<*-
л р —^
ота,^ ^-».8 * ( 'с"* -истинное значение параметра) (см.U2U
-Рассмотрим подробно ввчисление о.м.п, для наиболее
интересного частного случая многомерного нормального распределения.
Пусть рСелЗ-плотность tf -мерного нормального распределения,
эадаваемая формулой (1.4-i.U); Tr=^fl.,Aj.
I.О.м.п, есть решение уравнения Ч^1*(х)-0 ,где
2.Это уравнение распадается на две оистемы:
V«.Ur)»0, (ЧД.1)
%. UM'О. ' „. (чл.г)
Йа(ч1.1\ легко одедует.'что S, - % » jj„t '
65
З.Еычислзщ ирокзведнув 7А "f(А) от скалярной фуякщн
матричного аргумента,где
?(AWA"4- (чд.а)
Еля фушбпш многих переменных f(A) оггразбдлпво разложение
Ч(А*Ъ) -f(A) -tf\[yK<f(A)'!a" }*оСШ),
^Справедливо матричное гождеёзжо*
(А^БГ'^А-'-А^вСА+ЬУ,1
5,Стоика для функции (1.1. J) следит 1»й$отз"о
tr |IVA (w^-'V)]** }.=■■ -tfbAjitf-w'A
(если .А -симметричная иатущ^).,
(э.Если для некоторых маагрнл С-.»*?5 и произвольной
.^ярицы Ъ , trCb^tft^b, то С «**& и.следоательЕО,
Vi* Лг*т * -А'Ьм*4 А'*. . (it.*»)
7.Иодолъзуя формулу для определителя 1А\* XL&in Д*.к
A.i.t --алгббраичеокое дополнение элемента &>_*,*. ),доказать,
. ' VAe«.!A\ = A-\ («-i-e)
в.'Подставляя(Ч.Ш) и(Ч-1.В)в уравнение (Ч.1.<!.\ находим,'
^чте cM.ir. ковариационной матрщы А есть
1 А = £ t(<xt-x)(xK-«>! (4.i.«)
i Э.Заеиет ждя априорны вероятностей классе? могут быть
£ получены яз следующих соображеяий.Луоть *£, г*д$чайнан велкчп- -
I ва,равная~~ числу точек обучающей выборки,припадлетаца
Macs'су номер I .Она имеет распределение Вернулди с параметром pi,
1дто
56
Оценка максимального правдоподобия параметра р, равна;
а 1чиело точек обучающей выборки,попавших в класс* |
"1:0»Наппса-1-ь программу»оцешыаяцую априорные вероятности,
средние векторы и ковариецяоняые матрищ P-i, 0Li , Aiклассов по
обучамцей выборке (с указаниями учителя-).1
XI.Смоделировать обучавдие выборки при различных
значениях параметров; оттенись по ним параметры ж построить решающее
правила.Сравнить вероятности ошбка втих правил с байесовским
риском.
Литзратура: 1*1, [51, m, tlZl, [1П, EiT-1, [2.?Л, СЯЭ1.
4,2- Парьеновскке сленга плотности
- !Йвтоды оценивания^ которш: не делается .предположений об
■ аналитическом виде неизвестной плотности,называется нзпаремея-
рячеокими.Мк расемеррим два таких метода - парземсвокие сценкА
н разложение плотности распределения з ряя по базисная фун:<ик-
ям (в парагр"афз 4.3).
- Пусть ЭСч.Л.^Хъ.-ийвторная выборка с плотность» рСзс) .
Нарзбйовския оценка плст-носта рфс) есть Функций
где Kty) -некоторая заданная tfc-нкцкя.называемая ядро*! сценки
(Ц.г,.1)Лп^1-неотрицательная числовая последовательность.
Т.Вйзли ядро КСу-) удовлетворяет ус^овплм
K.(^)*0WWd^ =
(4.2 2.)
(4.£.i} eoi-ь шютлость распределен;!
Докажем следующую теорема:
'Теорема 4.1. -Еусть знполнеаы уолташ на ад» % % ^
Д"&1КС*)Н'
(ч.г.У)
(4.2.J)
Если фунхпия р(Х1 непрерывна а точке 31, то
Доказательство. Рассмотрим величину;
Справедлива формула;
^ Разобьем здесь область интегрирования на" два множества:1(Ч11£в
и '! ^ 1!7а, о -произвольное положзтельное число.
3.Первое, слагаемое не превосходит величины
I til -• о/К
а второе не превосходит
4, Отсюда следу61*"1170
0 в." iv«»s/+i«
6.Устремляя П. к бесконечности,получаем в силу Уоляетй
(ч.ал)-С-г.^:
Л^ ^ 4 itfft £ р<* - ifl -р(*Л $я«*) j »,
а так как о может бать ьзятс глюкзЕрльно малым,то это и
означает охсдзмссть &v'""* ® .Теорема доказана.
Теорема ^.^.Нусть ЗС -точка непрерывности плотности pfae)
■ и выполнены условия теоремы 4.Х.Тсгдарп(ой-)-аошптотйческ^
яэсмбценная оценка величины р(э&) »?о есть
Ёолй кроме того
то Р*,^)-состоятельная, сценка,то ест£
Доказательство,Соотношение (Ч-JL б) непосредственно следует
кз теоремы 4,1.
б-Справедливо равенство
второе слагаемое в лравой части стремится к нулю при -П- ■■**• .
7. Введем о^озяачёчия*
тогда В-С*)-^^,
а так как £fcv, -незавгскмае одинаково распределенные
случайные величины,тс
tf»-»vA.lli-ii(j1,.-Eiu.)l*.^T(fi»-X^.
Б.Цри больших Vv -
Э.Тах хак фуящял К-Ч^-'j удовлетворяет условии» теоремы
4.I.',TO-6iwjrZ-K=?(a)^K,^JU'( .откуда олсдузт u.E.95.
Ю.Прк $f*l следующие фунхцик удо1итат^оояыг условр.ад(>(.2.г):
■^W1
-Ы
Ki.(«.) -1 г'", iufx} - J,- -,
'Шогомернне йдра могут быть получены из одномерных следужящм
образом! t£(X.)" Д Ki (X-li>) , X. -вектот) о компонентами;)!1?
УсловияМ.?.3),К. 2. Т) внпояиеш для последовагедьзоотвй вида
К-£, '**<#•
II,Написать программу построения чаргзеноьской оценки для
какого-либо тепа ядра,испытать ее на оценивании рдномарпой
нормальней плотности (результаты изобразить графически).
12.'Применить парзеяовскук оценку для классификации
выборок из многомерных нормальных распредалений.Сравнить ошибку
* классификации с байпеовским риском.
Литература: [tfj, f2»3].
4,3. Разложение плотности распределения
по базисным функциям
Лредшшшм.что неизвестная плотность может Зыть pasraore-
на к конечный ряд по эаданЕОЙ системе функций I4i (зь) \ ;
Повторная выборка тогда используется дот оценивания
коэффициентов разложения I &i\ -&ы зд&оь рассмотрим рекуррентный
алгоритм оценивания, основанный на методе стохастической атгрок-
оимедяи.
I. Сформулируем задачу нахождения козфбициентов Т^' кек _
задачу среднеквадратичного пркбляхешя} необходимо найти вектор
ПГ* yt *>.,. Лг**м,и:шЕМИзируи.аиЙ функцию;
■ И^г) можно записать в вида математического схцдинск
некоторой фТЬкцга.Если система j'ft.t ортонормнрована;
то ч. ^
iM 8." i-»
и следовательно,
2.Мингашэация фупяции(ч.'Ь-11') приводят р решению системы
уравнвндЛ; q,
Оту систему можно переписать тед:
к
Дня ее решения воспользуемся алгоритмом
тгп.1гтгя *р, [■Рфн)-т-.,1, (ч.%.б)
где *f(o.) -векторная пункция
Э.Прпменяв теорему Л. 1, .доказать сходимости алгорвтуа
(ч.м) -. *гп ^~Ь тг„. (ч.ээ)
4.Цус-ъ yftfM)} -ортоногмированная сястзма функций
скалярного аргумента u e R1. Организуем всеБоаеаккие кгапаве-
ления! «Рщ,... ijx) = Ч^,^.)'-П^«г). - Y;M (U„) ( (V-S-Ч
где каждый из ищекоов независимо ири'тимрвт вес значчгзга cvi?
до *** , СС -вектор кэ Е." ,ЭС ---(-и.-,,.. ,«,).Тогда лк'ир дзг
-3)уПКЦШ*&,1А. - in(W.) .ОТПГЧашрКЖЯ J.O,"] ЙЫ СД'?Иг' ИНДЕКСОМ,
ортогональны и все сяк нормировали ка. I.
б.Зкоерсм в качестве неходкого сд-адарйсм-о ^йзисй кссле—
П
,"овзТблъность щункимй Эсшта, которые опредеяяюмр формулой:
Н„(и) -поливая) эрача,
Первые шесть полиномов:
6.Налипать программ^реалинушую алгоритм (4.3.4ддя
разложена,! одномерной плотности по Фрмщьта,Дрмытй;Едягь 6 членов
а разложении.
7.Сжщелировать повторную Выборгу, соответствумцуо
плотности раснредэле"ния , .
l ft >0 ,) я Применить к ней алгоритм оценквРяая.Сревнагь
графитести найденную озепяу с истинной плотностью.
teepasfta: [blt [?.aj, [23]. [3«, [261.
4.4. Непосредственная влпроксЕмашя ОаВ^сов-
ского решающего правила
Кад указывалось в параграфе 1, Ъ. .можно непосредственно
«ШТокскмировать байесозскоо решапдее цравдто, оцендван фуяк-
аш достоверности прш!ЕДЕКккос1И(1.3.14|.
I .Пусть функция Jf"X.) раэлокима по система i ч\(х)[ J
<J(x) » (т* t *f fx)) .Для Рвхоадения параметра ТГ^ чройхо-
,viwo минимизировать функции
,что 1гриводит
к веаению снс^гел'М уоавнешй i
л.Зосголъзоватьея ал1"Оригм<ж ГойбяЕоа-Мочро- для решения
этой системы нельзя, так как эначенич функции Hfx} на точная
сбучаодеИ вкборки нам чеизвестны.Но можно счят=.ть,чт;о нам нй-
пестна величине- -Kpty с некоторой пошхой.Действнтелъно.пуоть
■у и - i .если Xh соответствует объекту из класса Gt4 ,
и у* * С .если тЯ-и**0^ CV" -указание учителя).фактически
о.,, есть зеалиэацля случаЙноЯ величины •»— номера 1гласса,но-
торому прикадлекет объект „оггисыгаекыи векторов признаков V .
Справедливо следущее соотношение:
Если ввести случайптв величину &, » Ц~ - <J (:£.) ^ мы гю-
лучим наблгщение фунхсш dfscl с чшзхоЗ: ^и = c'f&i.) + #к .
ггокчем, *
3.Запишем ялгорвта РойОияса-Чонро для системы (*j.ij.
^.заменив J Cx^J на у« :
4.Следущач теорема ноназывает.что а."горктгл(ч M.Z.J
сходится,несмотря на то,что функции входит е него с поксхой.
Йюгема 4.3.Воля фуькцкя d(rc) таялохима е пял по ортс-
нормированной системе vft.(x)}. dC^-l -fti,'Pi'^j), матрапг
A-.E'fCxWC3^ „еадмвденв и Е И ^С*)!** »* , то
tr„ "" ~» .
Локаэатзлъетво сводится к проверит услогсщ деорвии Я.!.
1ЗД.?акже [a.2J )-
Иногда бьвает удобнее рассмотреть предстзвлеи'тв Функции
73
в влдё fJj^C, *fip^ly\ ^ #тде j (") -навестила функцт:.
5.Кайти представление такого вида для случая двух
одномерных нормальных распрепаяениЗ.
ё.Аеп?1жтм оценивания здесь Судет име?ь кал.
ш 7.Кусть pjfotl и р2 (X) -плотности двумерных нормаль'цК
распределений Лфймэпить алгоритм(Ч.Ч.й):оргонорыированную
систему 4^-(№}\ построить в виде лроиэведеиий одномерных фунздий
(ш. параграф 4.3.).3а одномерные функции взять набор полиномов
1-го,Я-го порядков,ортогокальныт не отрезке 1-1,1"] :
Из зтиу одномерных функций построить двумерную ортонормпровы->
ную систему, содержащую компоненты вектора ос. в стелет ие
выше 2.
е.Примеаитъ рассматриваемый метод я распознаванию омеол
гвух двумерных нормальных распределениН.Исс-ледовать сходимость
алгоритма .«оделирун выборки разной длины.Срав1!итъ вероятное^
оаибки построенного правила с байесоЕсшм риском.
Лигарачура: [а1, [22], [Й6?
■1
ГЛАВА У^АЛГОГИЭИ АВТаМВГШЖЗ! КЙ1СС11ФИШ5М
5.1. Иетод Н.Шгосона разделения смеси
нору.^яъгск распределений
Впервые задачу разделения смеси дзух одномерных нормаль-
них распределении исследовал в 18й4г. К .Пирсон. Этот частый
случай самообучения в силу его нагладности и практической
важности заслуживает подробного исследования.
Пусть компоненты снеся (I Ч. I) являлтол норшльянмт! раса-
ределепияни.т.е.
К.Штроон предложил воспользоваться для оценки неизвестных
априорных вероятностей р* .средних d-i. и дисперсий ©Я методов
ыоыентоа .Дленная лабораторная работа и посвящена этомз подходу.
I. Ка теории вероятностей известна следующая связь м^вду
гюмвнтК1ШГмл=Ё ^"случайной величины > и ее характрристччег-
яоЁ фугкцдей fH) :
двсь J= »'а .;.дн нормального распределения;
'tm - ap(fa.t- ччуг.).
вывести стеша следящие выраиевдя для моментов
Нормального распределения с пло1.чэсть*) р* (3C-) :
' т-л = Л; -, та4 ■■ е^ * of
m5i . isms' ,ical&'±a.i
76
2. Нам неооходимо оценить пять ларвиетрокри.й*,^^^
(тяв код рь = 1 - р4 J. для итого нухнн пять уразчехий.свя-
енвапщих момент]} смеси
14 " Sx"p(x)d3t . pSxBp,(xW^ *(l-p) $x»ptec}<№
о параметрами р • йс, &г. 6"±16^ (индеко при р4 ык будем
опускать).Кокаэать.что эти уравнения имеют вид;
pat-* (i-p)Ost-mi,
p(ef * of- тг)+ (l-p)(cf* oj -то -с,
p (Sffi'fli ■> Oi-msV (J-p)(sra"Oi+ o£- m,) = o.
p (oe,"t baitfiOf-m,)*
••ft-p)(»«.'-> 40*6".* «О?-иг»). 0.
pCiSSVo.^iCr'ni-oS- mB).
3. Р-уедпожиаад.что'иг^ь О, т.е. поместим начало
координат Е центр Смэсп-Показчть.чю написанная внце система
уравнения сводится п уравнении девятого порядка относительно
величину 14 - ft» /О*:
♦ 0|*Чж,т*-1 JxJ)«"., (288mj -iC8m3?e,a',»s>SBj)K,«
♦ (-«mjsej -«n43e,)u,-eemjse,tt-e(nij-e, fsu)
где э&ч - мгч -* Элгг . ЭС5 - ^5 "^^г^четэертнк и пяты*;
шс"ор'о-1Ше еемикнваршнть.рцеякч 1,еЧ8вестЕЬ"х параметров еле-
дугчиа! ооо^зом вьржантся черев решение втого грашенчя;
a, j. , о» > -£ ,
a^-Oi»
.^pes R обозначена ееличгсщ;
Среди решений урашен1*я(£-£-0 должно быть выбрано вещественное
ifес^рицательное,поскольку рСч + (£- PJOi = C,
4.11ал!'сахь программзчреалиэужщуь данный подход.для реше--
яия уравнение (51М) воспользоваться одной из стандартных лрог-
рьмм.имекщихея в стандартном мааематичесиом обеспечения любой
ЭВМ. #
Ь.Выбрать некоторое фиксированное значение «екяора
параметров *С^ „Сысделироиать обучающую выборку дая,скаже11:,п=20
из ompcs. с ^акйм набором параиетров.С помощью программы из
пучкта 4 найти по втой выборке савнкя параметров смеси и
вычислить величину отклонения оценвд *с от истдшогс значения
§^=|1т—Т„ ll/ii^vd •Проделать тоже самое для значений
*v — 40,6C,8D,I0D,I2£i Еарисовать гредик зависимости веяи-
I чини о от длшш ебучавдаЗ внборки.
В.Завести на экран график сданяваекой плотности р(:с) =
I *»-р С*» r-c*»)»b Taitse графики построении* оценок втой илотис-
J сти pC'Jt,'^-).
jf 7.Рзезмот№тъ часгиьЕ случай 6"» " ^k , p= i/2. Пока-
вятгь.'гго тогда
II
77
Смоделировать несколько обучающих выборок ив смеси двух
нормальных распределения о единичными дисперсия™ и сравнить
метод 11ирсона с непосредственным вычислением оценок по
формулам.
Литература: £2l, ["Л, [237. [2«Г].
;».Й. Метод локальной опимизапии
Рассчотрии вадачу кластер-анализе: необходимо разбить
конечную оОучиацуы вниорку Х4 X», на М групп тис,
чтосы достигал мияиичума некоторый критерий качества *?.
Решение втой задачи всегда существует, так как воачюдно лишь
конечное число разбиений конечной последовательности. Сдаат-с
число способов разбиэкия И-' объектов на М групп при
большее И' икеет порядок М (см. t «П ), поетоиц- искать
оптимальное реиккие непосредственным перебором невоз^о^но. Вое
реачьно работаадие злгорпетщ группжровкв евляются "субоптс-
малъными", т.е. гарантируют отыскание локального, а не гяэ-
■балького гкетре^тума, го нато имеют преимущество в простого
вычислений. Один на таких алгоритмов рассматривается в
данной работе.
Обозначим 6"(сс, номер класса, к которому отнесена точка
ОС . Алгоритм локальней элтикизахш пвлдетоя итерационным и
состоит из следукышх шагов:
i-ar 1. ^(-Х.к)-~к для k = i. .,М; -ei-Jvl,
jiictJU *: = €+!,
где л'ЗСс ""XiJeoTj, значение критерия яачествг V , вы-
чксл-енное ;ic ;ь.е хлаоси'тдчроъгннго! точкам 3Ct p ,. f Хп в
76
предположении, что ССе. отнесена в класс At . Если С < и ,то
вдги па Шаг 2 иначе £ = = О , нити на Шаг Зг
НагЗ. е:=€+1,
вГссе-1: = &ла гЫп. {^иСэс*— Xi)l
* HUM ( J
Вола Ч *■ И, то идти на Шаг 3. иначе идти на Шаг 4f
Наг 4. Коли в результате выполнения Шага 3 хотя бы одна
точка OCt изменила свою классификацию, то С ; = О в вдте
на Шаг 3, иначе алгоритм заканчивает свою работу - стоп.
Очевидно, втот алгоритм остановятся после конечного
числа итераций к результатом его работы будет некоторое локально
оптимальное разбиение (т.к. на каздом ишге вЕачегше фушшио-
нала 3 не возрастает).
I. Нависать программу, реалвзуияую алгоритм локальной
одтнмязыши Для какого-либо критерия качества Э из
параграфа Т.Я.
£. Смоделировать несколько ооучаидкх выборок из смеси
двух и грех нормальных распределений.
3. Применить алгоритм самообучения к этим выборкам;
изобразить графически результаты классификации.
4. Ъапнсать програ»^ о тем же ({ункцвоиалоы 9, яи цри
другом выборе нерн расстояния ме^цу вегторами и выполнить
Пуню 3.
5. Исодедовать во81укпость решения задачи группировки
при нефиксированном числа кдоосов следущим образам: скоделя-
рокмгь обучаищв выборду ял смеси трех нормадьнкх раопре.це-де-
няЛ, пай-лг опвтаельгае разбиения с помшсьо напксадньк нрсг-
рмс: для М^2.3,Ч, JT, за оценку неизвестного чссла чгаеоов
прянять число М , для которого кашвиольва ввяи-ища X (М)
79
CWM) - вгачение функционала на оптимальном разбиения при
числе классов М ) {проделать то ке ошое для выборки из
смесь четырех нормальных распределения.
Литература: [23, Ш, [ 81, ЦС], [Щ , [25].
5.3. Рекуррентный алгоритм разделения сизой
многомерных нормальных раояределвнжи
Пусть компоненты сиеои распределения (1. 4.1) являютса
многомерными нормальными распределениями,т^ еояу функция. pjf%)
имеют вид;
где ОТ* - средний вектор, А" - ковариационная ыетряда(по-
дояямльвс опредёленнаясимметричная A v^* -матрица). ТТриме'ьим,"
дли разделения втои смеси регуррентныи алгоритм (1.Ч-^)-(1-Ч */).
1. В данном случае алгоритм будет состоять из \i.4-ij) и
ооотаэшевхЯ;
а?., - а'» - Г» -Р-^^Я V^,P(*-oP. A'*'),
2. Первое из них легко преобразуется с виду/
l&apoe получается е Еснользовакием Формул (4.1.4) ,(^-~-^) >
Иы несколько упростим алгорвтм,оторосив матрицы СА'к! ;»ояар во-
незать.что *то не керувает сходимости алгоритма.Итвж.реЕурревт-
hhS алгоритм разделена^ сноси прнмрт Bits"
ёо
я„.( - л. ♦ j„ рсхи.тЙГ
OS.- of* jr. -^'.р^-°'"--^"-)^. -«?);
сода еще надо добавить соотношение (Ш.ч).
5. Нависать программу, реаяизуоцул алгоритм,
смоделировать несколько обучаадо выборок из смэои нормальных
распределений с числом'классов, равным 2,3,4. Применить к »тим
выборкам алгоритм самообучения для нахождения оценок шрешют»
ров смеси.
6. Камаоать программу, реалиэущув байесоьсдар решавшее
правкло (ii.il/. С ноиоцью тех же обучающих выборов эдвни-ть
вероятность ошибки доя каждого ет решаших правил, шст^оев-
нет в соответствии о яаидаяяымя отаняеми параметров скэсв.
Проделав эту работу №*я обучающих выборок ра^лой длины, но-
-йтроп'Ь rpaj-raci аэвнсимостк вероятности оашбкп от числа
шагов влгорнтыа.
Всв работу проделать «ля двумерных псрмаяылк
распределений, чтобв не усложнять программ вытеснением обратим мат-
■рщ. Имвеоти на екрон несколько npioinpos обучающих выборок и
поотроенвшс раацелящга поверхностей.
Литература: [ 161, [Zbl. [25] , f 2€].
81
5" Ц , Речп>рентний алгсрьтм сачго9уче,1ия
с поиском цечтроь классов
Рассгштрш задачу самообучения з ^эрЕвдрюнноЬ
остановке, выбрав в качестве ^'нкцик^^^Е.тг'^кзадрйг расстояния от
точки X до венгра класса т w;
1огда функционал среднего ркска (1.^.2) примет вид;
& М
i-i Xifr) r ■ '
Исследуем более подробно сшет этого гТутгкцрошха и его
условий якстрещуаа.
I. Пусть число классов patKo двум. Показать, чга воиерх-
:-' ность, рызделяитая два класс-i, XaCt") tlV-iCr), имеет вод;
(X1t«»-Tft>)-(B-ir«II*- Лт*»в*)/г* J.
?. Согласно (i-Ч 9} экстремальны! набор гараметров
; уукгащонала (£4.1) удовлетворяет услэвнлм
Ci)_ Mi(f,l
f; -
Р* Гт
I Pi(t-)*J pftfc}doc (Г.Ч.г)
- вероятность миокветвь X;(lr), ь Mitt}- средний вектор,
вычислены»! го этог!у мшжесгву.
Mi Cti - $ «. pfrcjdx. (5:4.2;
Лсстремальгее зиачзчиз $<уёрц<юн8ля(!Г.Ч. 1) раьчо суиме даснер-
сил мнечейтв (X;. (■£-»)}-
й» Аспрктм оат.гасоучгиЕй:
а-.'.1!. - тг?. у? Эх. ст._)Сх„1 СХ.--1-;»); (г. ил)
ez
иоеие.говлгсяы.ость yj*) оггоеяе.'щется сле^удадм авралом:
(ЭСИ - число точек, копавших б л -Й класс за и. пэгоп
алгоритма), Кеобраэять г^арически изменение центров *"£",, ча
один шаг алгоритма.
4. 11а основе пунктов 2-3 модно сделать следующий вывод:
алгоритм приспособлен для разделений достаточно разнесеьнчх
црьОячэитслзпо сферических групп точек в срострелкл'ве признаков.
5. Проверить вшолнепве условий сходшвпсти яэ параграфа
1.4. для алгор;гша(5'.Ч ч) 1,при замене Jj"£* Fa <Г*П ).
6. Смоделировать обучагога» B':6op;oi раачичной дщпш из
сысси норцальнык распрсделегай три числе классов 2,3ьлриме-
нита к пии алгоритм, х^&яжзавакний г вгд& программы для odK:
ОЦСГИТЬ СКОРОСТЬ СХОЛЕМОСШ В СМНйЛС ЗВВИСИЫССТЕ рКСбМЯКИЯ
lltv,-T»| от длины осучащий выборки; нарЕОовать графики.
Эту работу проделать и& рябортах яа дзумерши кормвльяьу
распределений; вывеет* на экраа зесЕольжс примеров стучащих
выборок и разделяющих поверхностен, .йшариационные матрицы
брать еднялчгима.
7. Внполеить пункт 6 дан ом?си нотммьнах распределений
с нвединЕчн-ча неодияпковнки ковдряаиион11ы.лк waTjuntaw
{выборка разной длены при одних и тех же ж»р01№'1Тгйс смеси). '*<"-
елтезозать воэкожкостм члх-о^ тма no oeohupwhd цпрт<»тр. crscry
нормальных ррсцредеясхи с чм>тлч1!;гв-я.-к говьг "" ' "
ршада.
Литература: [Z1, U] , \М\ [2,21, \?Л.}, \2П
5.5, Рекуррентный алгоритм сагтоооучепня дгя
выделения сильно вытянутое дараллелышх
множеств
Предположим, что т, простракетее признаков is имеем
примерно следуйдую картину;
Неойходимо аппроксимировать э»и сальдД вытяьутые мня
жества с помощъя гипеишоскоотеЯ.т.е. достроить также
гиперплоскости, чтео'ы разброс точек к^вдого класса относительно
Овоей гиперплоскости был мииииаганшЛ'ля решения такоЕ
задачи естественно ээять функционал ервдлего ряска с
функцией <^(ог,*7Г ),имеющей смысл расстояния >т точки ОС дс
•I -й гиперплоскости.^ргсмотвш рекуррентный алгоритм
минимизации такпго функционала. Цуоть в пространстве К ведано
/"I гиперплоскостей:
(те, bflti}*tf0)^o, -i-iv...M.
1. Показать, что кзадрат расстояния oi точки ЗС до r:it-
лерплоокоотЕ с параметрами yU** jl^JpaaeF;
2. Т^ссчютрви функшюаал среднего рхсза;
Ь котором 1г - вектор параметров,T-^lu^ir*0, i=i Ml. а
разбиение {XiCf ) } определяется соотношением
xcS (т)<=> ((ж.г|'")»-1г",)у,||г1'а8г*((х,«'Ч-1^У||г<*|| *
Еолк направляющие векторы V"' гиперплоскостей считать нормаро-
вакными (/144. ' || - i) , то условия елетреьг/ма (i *J 9 J для
функционала (££1) имеют вчл:
^ {(Ух. 1^)+vlto)x - ((л, *л'>}■» ir(1') '■ -ыw} pcx)dx^,(5:5.a)
i ((X,t*(ij)* ^(1)р(эс)<)х = 0. (FE3)
3. Пусть AiCt}- коваргациощая матрица, вечислыш&к по
множеству Xi Ct"),V есть:
(ом. обоая8чеш1я(£:Ч.£).№.*1.5)); погасгегь. что Ркстретчъчне
вектор параметров -tr* = 11/ * , l7, J удоачзтворяег условиям
1Й° — М". MiM)/Pi(T-»), CS5.4)
Ai (t-.Ы" - (A. (-r.)ui", «I")«?-« (КГ5)
4. Соотношение С &. 5. Ч) означает, что оптимальная пшер-
плюкооть проходит через "центр тяессте" Mi ft*}/Pi ("С*)
множества Х\ (tv) :
(а«.-$^> v„<n = o.
а равенство (J.? 5) орнач^е-;, что 1/'„*' - собствен .ш! вектор
матр:щы A^Ctv). £сли А^ - еоотвеуствуэтес :i?o.rf n*>T-Tojy
собственное якьяеюз, то
М
85
Отсюда слецует, что £(1%) достигает минимума, когда 'U*''
соответствует наименьшему собственному знечешта матрицы.
A^(f«). Поскольку гидероЕоскость периевдикулярра своему
направляющему вектору, а кшпзидДвИрэ собственное рваад.ше
указывает данравяение наименьшего разброса точек, -го
оптимальная гиперплоскость проходит вдоль направления заиболыпего
разброса точек множества через его 1*едар тяжзсти. что и
объясняет название алгоритма и указывает область его применлю-зтн.
Ь. Изобразить jppa£E4eoKii изменение вектора параметров
при выполнении одного гоага алгоритма самообучения, который в
цаяном случае и**5* зид to учетом позировки напраелясаас
векторовJ:
« *i = «!? * Г. ^fc., (=,.)(.i'"x„ - w»p).
6. Построить обу*шшие выборки разной длены нэ смеси
двух двдмернда иор^ачызп распределения, вмевдис струк'ууу
тина рис.3. Написать программу, реалиэ>мцую алгоритм (2..5"-t) .
Нришжить алгоритм к обучащим выборкам для каяуздения оценок
ппрзиетроЕ оптимальных гиперплоскостей (в данном случае -
пргеых линяй), йайть или данной Си;еся хс-гутте вяачения олти-
кальнкх парииетгов. Пцределтеь стлионеш*1 оценок ЗЕрлиатров 05
истан'ок значений и юсбрази-зя. аазисилмсть втого отклонении от
■шеда катов алгоритм.'..
7. Оценить аналогичным образом скорость сходк,уст« алго-
If'
ритмч для различных cieceH, меняя расстс.ние мелду плось^отй-
ш и угод мевду налраышшш Викторами.
8. Оденпть работаспссоокость а-ггсритма при числе югаосов,
ЙО^ьпе, чем два.
5.6. Алгоримл самообучения "ИЗОЛЕНТА"
Рас&дотр™ честныЕ случай метода дия."*мкчвской
группировки для юттмиэации ялшричеокого Фулюшонрлй!
т * lt-t*,,...,ttM4,
возтисягац^о из ф/п-тиопат ащего вида f J.'i.bi} -pp -&-нкЕшиг.
потерь
^i(x.Tr) = ilx--r-c-:i||i
1, Исказить, что повериюсть, разделяющая множества
XlftiXjCt"), есть гиперплоскость, проходящая через середину
отрезка, соедиктоцего лентрн *г-(*1 . Tr(j), перпякдгао-лярш
ецу. Изобразить графически раздекя-нцие поверхности дав я-х
в дня 4-х клаооов в 2-мерном Еростригстье признаков.
2. Согласно метода дяндоичесгоЛ гручпировки (i 4 15")
(S4i)-{ приближение дчя эе*:тог„ f£t> отдоится по . .0!«.<уле;
где Hi(tt) - числе- тэтеп о^учч»-*; г^Сг^кч гс4 , ...
^И, ПОПРИЩЕ* В KPOJWCTDO Xi (*?"s) :
W-^;N(x,i
e?
ТГак как oooTFoinea'e(Lit.l8) превращается ji рассматриваемой
олучаэ в равенстве, то услоьис сходакэсти дамдаа динямичейко*)
группировки выполнена.
3. Работа атаорщгма дянеьЕ^эсдай грукллровкп есстогт
эвесь из следующих шагов.
iliar I, Рыорать ьачадьннз щяйяижезия $ся центров t~
например, салют Т^ = ^Ч, t-i,.. ,М. уцчсслзть значение
Ьйг 2. Нейти средние ивктерн множеств Xi(f), и положить
новые значений центрол t-1-1'равными stem среднем.
[цаК.Зд, Вычислить нояое зизэдние З.унютп» R. K it-). Ъ'зли
оно рапвс старощ', -jo С^оп, иначе эзпкл!^ &зе.чэ:;ие 1£к(т-1
и вдтл на bar 2f
Б латеро-sype но распознаванию оЗразоя втох «лгорьтм
обычно нарызалу/ йЗОДКЛа от адглтйя.ого сократи ;1И1Т Т50ВАТА
(Iterative Self Or^Gntyinq Dcrte An«£i&t(& flnd
TrtatmU'it). он является наиболее ^рЬот'л: к эф-юктыйшм
аягоритмом груплгровчи многомерных ннйшденлй.
4. йагамать протрачу, реализуадую алгоритм ШСЫМА.
При втом оргачьзовать аягориты тан, чтобы Iliar 2 иклоявйтоя
за один просмотр обучввдбй ввсЗорки.
Смсделироишл неоколыго сбучащах выборок па смцсе *-х
норм-шьы^в рпепревдяеняЯ п применять ь- иш алгоритм. Оцени-ь
екшериыенталыш скорость что сходшости. Сделать то же самое
для смеск из 3-х распределения.
5. Алгоритм ЯЗОДЕда ыесяо использовать дня гтуспировки,
если дэполт-йть ьго правилами изменегая чис-ic клпссой. Лосле
окончания гругшЕровкг подсщципа?м дисьероии в^тр/ груш и
ореднле расстояюаг :K3»jy rpjmaija. Если расстояз'^е ие.^су rpyi—
о?
нами лепит заданного порога Л , ю эти группы объединяются,
группировка прОРвводитоя заново. Еолв дшоерскя некоторого
ЕиассБ больше, чем ааданзщЗ порог ,/Ь , то этот ляасс
разбивается на два. Если кам>Е-та класс оказался
непредставительным (продал точек, гопавших в него, ыенздг. порога fl* ), тс
он лехвдифуптоя, число классов уменьшается iia единицу, кнас-
свЗшсация проиввсдатг-я вансво.
Смоделировать вчборки на смесей нормальных распределения
о числом классов 3,4,5. Варьируя параьйтри Л , ,£ , jf ,
добЕТйоя качественной группировки.
Литература: [Z\t [i]. Wi, l*'i ,Г«1, И91, ffiSl.
5.7. Эвртстичбсквй алгоритм гру'Ц^ровки
t)ce рассмотренные в прздыдуцкх. рабэтах аягорити^ возни-
ката в ринках математкчееках копулировок задачи ьэмообуче-
иия. Прттчем, все эти чюрнутаровкк прикуси: к эяетр^шзглда
того или инс-^о функционала, характеризующего качество
разбиения. Различие мекч? ьлкзритмаии заключается в выборе
функционала и сяосдйа его вкстрешэшрЕ.'. Существует, однако,
обширная группа методов кластеризации, которые не отшрютоя на
ту влг ияу» точную постанову вадачч классификации. Ьместо
итого дэла?тся попытка непосредственного использования
интуитивно очевидного понятия близости, сходства ^екторзв
признаков для выделения компактных групп. При чтои часто ядатп'ия-
ются различные ссосоок чь^лулно^о rp-Tnir-ecioro пч^д^-/ие;:'.-я
данных. Подобные метода гдтиар s 1чзьл к-с: эт !■:!';,■.iieci-.t-
юг; один из ык ка -1Х;йсг.ст;Л7.:. * яе«нои {лсюте.
В основа утсго iiropira.-; .тегвт ей<ыц(»д?е ст;о*сгк$
-Мерочной к^аарвипиовкоЕ frfwpjna»: ее собстьеп.*'^ acr-sop, сеотеет-
ству1Ми£ макси^тьроцу c«0^tk*«^ow^ знччвка/:. 4f/->ri;r
69
правление кзнбольвего разброса точек обучащей выборта. Само
ке вто собственное епачение равно дисперсия выборочных точек
в направззнии максимального раосаяния. Докажем его свойство.
J", Пусть А - выборочная ковариационная матрица, чост-
роевная со обучаадей последовательности CCi , ... , ЭС„ •
А-^Сж.-гхжк-эе)? (rid
"X - средний вектор.
Спроектируем обучаицув выборку на направление -. вадаваемое
единичным вектором *W,
среднее значение сдучайннх величин *^к равно 4 •>(!!,X}»
Выборочная диспероия втои лоследовататьнсстж равна;
Гюказать, что вкяремум этой ввличяш при услозии tlvlf *1
достигается, если V есть рвкение уравнения А^ » Хи , т.е.
1/ - собственный вектор выборо *ной коварващгоннс-Ё ад-гриля.
2. Будем предполагать, что ообственше значения патрицы
X упорядочены по величине X* > /л*...> Аии Hi,Ht>.. (WW -
со6>йетс'гву!одле км ортонормированию собствекнье б<-1 ' ,?л. Спро-
вкгируем o'jj^ixqyo вксорку за собственный вектор 1(< :
V ~ с?е^;'е^ ЕЕ^челие этих проекцаР., ^(1' "C^i»^-/.
Из определимо* матрицы А и ортонорлчюванн^етн системы
сой^гачаясг peiL^opOB непоср-и.ствекно следует равенство;
г.е. С1.рдимтз,*ая1!?:ч1 "; разбрдс ирююиП ачктиров 01». не вей-
90
тор U-i рав«ь соответотгутаче^г собственнощ- доачеют, что и
докяяшзает сформулированное выше утверждения.
Рий5.2 иллюстрирует возможность применения втого
свойства для автоиатичеокои ктсюсв^икаюш.
jflkflk
рио.аг.
рправа иаобраасева гистограмма, поотроенная дал исследователь-
ноотя ^| , ... , ^» ; ь точке ty* она илвет мкшэдм. Если
все векторы ЭСц, дчя которьос у* > *f» , отнести в одна югаоо,
а те, для которых у%} <у»~ в другой, то мы пвдедим две
достаточно компактные грущш, Постровытое тасиы образок рекагщсе
правило является тавейкьи а том смысле, что оно определяется
линейной раадаштапей поверхностью:
CWi.scJay» -=> за *Xt,
Равунеется» в о&йеы случае одгократное разделение эоуча-
цце£ ЗУборкн не прлвгд№ к наделению коквакгакх rpjim точек,
но тзгда имело отжбегзуть к поатедоватедькому дачеяию laaetofi
ввдучеыюр группы. Этот процесс ишзстркруе-гся ркеДЗ. ,ш яс-
fopo« пскезаде выделение групп ян омеск двумерны? нормальных
распределений с едкнаксшаи коварчшионники мат?;пздш;.
Ряс. Х,Ъ.
|0.вдг mai' илгсритма состоит, таким образом, в следующа'!.-
яыгодчя вдбо;)СЧяу» ясеаркапионаую ыатрЕцу гр^гаш, якчисляем
рй insciaiaEbMce соОственшэ значение и соответствувдиЗ соб-
1 стяеяныи вектор 1l i, 1троэктируем группу на вектор i( j и
строгал гистогршцу проекций, Ло этой гасзсгрявде (визуально или
р соствествик с некоторым заранее выбранным критерием) опре-
зяеявеи, н& столько дазгрулп делить данную групп;' и состав под-
груж. :imnv эта оверадия применяется к кацдон us подученных
грусч. Асгстжтм останавЛЕраяд, вдгяд грстеграюя дзя проекций
5сох ^rpyjin носят достаточно одночодалыагК дараиср, v.е. не
со. ;e,ii,'.«' яр<« да'-таиш киЕицуииэ.
j. Лгллсагь npor|4u1L..y для отрвоотги зтого #лг<',1т:т.**а ий
2-i:p->T!i-x ei'f.'Opjs-ut. Cr.JcTBQBbi.'-j значения -5 со^ствендае векто-
i-w с -№пит,;.чио|" иототстс-'/.ио счред<угекио11 :*аг>л:ци [{с. jb:j-
ч/слр~*гся во ^отаолаи; А*,г =ft+ ^ii,2.
При iiooTpoeium гистограшш очень важное значение имеет вмбор
юага квантования (интервал Д на рис. В". Я ) (.Поскольку ва-
ранее наилучшее зпачеяве & неизвестно,следует предусмотреть
в 1фограмие возможность варьировать величину ^ ) «
Написать програмиу,реелиэуиЕ(ун данный елгорпты грушшроз-
ки'.при произвольных размерностях пространства прнэнакдв.Для не~
хождэния собственных значения и собственных векторов вооюль-
звва'АЪСЯ одной из стандартных программ-Построить выборку из
смеся нескольких многомерных нормальных распределения и
применить в ней алгоритм.
to-ерагура; Ш, U1, Ш. И0).
ГЛАйД ^1. ШЕОР ПРИЖАКСВ И ОТОБШЕРИЕ ЮВОРШЦИИ
В СИСТЕМАХ РАСПОЗНАВШИ ОБРАЗОВ
6.1. Снижение размешостя-Метод главных
компонент
До сих гор мы рассматривали различные методы построения
ретащих правнл в пространстве признаков.При этом сам способ
jsufiapa признаков .характеризующих объекты, предполагался
заданны,» и фиксированным. О? того.яасколько удачно выбран набор прь-
анаков,существенно зависит успех в решении задачи Елассифтаа-
ция-Чем больше размерность пространства признаков,тем длиннее
долина быть обучащ&я выборкагчтобы обеспечнтыреСуемую иеро-
ктноать ошибки (см.результазы главы 11).Да и по чисто
техническим пркчивач обработка на EDM значительных массиво* BH<fiop-
ыации может потребовать слишком большого времечи.Еоэто-ду »яд:~
но как можно более 4kceove4Ho строить признаковое описений
объектов.
Раэумеется.укЕяать существенные для описания признака!
можно только на основе знелия т«х конкретных областей науки z
естествоэнания^'де'мылытаэмся применять методы распоэнягаякя.
Ко и для чисто статистических методов вдееь остается свое паче
деятельности,евчзанное с сокращением избыточности признакового
описания объектов,выбором способов оптимального кодирования
ЮфорОТ|ЦЙЙ.
Итак,пусть К — исходное множество значений векгорсв
признаков классифицируемых объектов (пространство признаков).
Необходимо построить оптимальное в некотором смысла огобрзке-
клеТГ: £ —"Я пространства V." в пространство кеаьией
размерности { Ni *• М ).Критерии оЕТшальвосТИ отобрехесир
Т бнвают раэ.пгчнют.п,'одно например потребовать .чтобы i-c-Hfii-
94
ту$ащя имеющейся обучающей выборки при этом отобраиенка •>'
кааклась в наименьшей степени или чтобы сохранилась ъеяоэт «с
агабочного распознавания классов а т.д.
Наиболее просто решается задача в том случае .когда 7'<-сть
линейное отображение,задаваемое некоторой Ui^N матрицей,
^. « Тх .Особый интерес средстэвляют
матрицу.проектирующие R б подпространство L мьныпей раамерноо'-ги.Выберем в
Е. ортонсрмарсваниый базис
тогда матррца
i * Nt t N, (6.1. a)
»^та оператор проеятировглия на подпространство L порозда-
емоо первыми /Vt векторами базиса C6.il. 1} .Именно такого ввда
отображовия ш будем рассматривать в втоц и следующем иервг--
ра&ах-
I.Пусть ВЧ
тогда .юякий вектор ЖбЬ можно представить в виде '.
Отокда следуе*. "Тх|! < ||Х||* и проектгрование ка
ясцдроотранство L геометрически означает пренебрэжегше
разбросом точек относительно L. Если ыи хотим потерять как
можно меныае информации при проектировании обучащей выборки,
гс несводимо строить L так,чтобы минимизировать в средней
этот.- разброс.
/ааг.сЛюрмулируэм задачу,котору» мы будем рбгэть в этоо
нарагрофв. ГЗусть t -чекторная случайная м^кчина.описывающая
[«.*■
растгределедье векторов признаков в К.. Необходимо найти
такой ортонормвроваышй баэяс б Е. .чтобы матрица if. 1.2}мвд-
епклэтрйвьла величину ЕПТ\«».
йлл простоты везде в этом параграфе ш будем преяпола-
гять,ч.то Е ^ = О •
Теорема 6.L Матрица Т ввда ft. 1.2) макоииизирует
величину Е ЙТ^Й* .если бааио [■£*] совпадает о и&бором
собственных векторов ковариационной патрицы ** * -* S ? * в
рлчеотвз ti, - . , €•*/« выбраны собственные векторы,состг.ет-
отвущке Hi наибольшим еобственн»! значениям.
Докаэательство.Яри доказательстве будем иснолъзоват?,
roJiKo условие яорнкрояяи: ,
lltil!1-!, i-4... .ft Ш.Ъ)
-л покаявк.чхо нужный оаяио автоматически будет и нормярсвак-
нда.
EflT^-E^et.^-J^Afc
при условии (^ 1.3) по метоцу Лагранжа.получаем необходимые
условия экогреыуиаг
А«< »>*£<., *-*,...,М (*-*•*)
НоСбЛ.'Д-УР^нения для собеттзечнах вехтороЕ ыатридк А »Йв-
вастио.что собственные иектсри сяммвтричкзй неотрицательно
определенной матрицы ортовормированн,1 аооетвеннне значения не-
лтригрчеллш, Рсполъэук (&.L1*) .получим
откуда и следует соследшее утверждение теоремы.
Т;лгки .ойразам.олтимапыкк! метркца Т даеет гвд
'U.1-
С6 1.В)
96
где Vi ,.. , Vn -собственные векторы ыатриш А, Разложение
рзктора X по собственным векторам ковариационной матрицы.
носит название разложения Карунена-Лоэва.
3. Коэффициенты разлояения Карунена-Лоэва являются
некоррелированными случайными величинами и ЕС^ * Ai
Это утверждений дает корпшае геометрическое обоснование
методу отйора признаков,основанному на ратлокении Карунена-
Аовва.Из него также становится ясным название
рассматриваемого здесь подхода: "метод главных компонентов качестве новых
признаков мы берем наибольшие (по величине) коэффицивнти в
разложении Карунека-ЛоБва,то есть учитываем только
те/^компонент вектора признаков (в новом беэисе),которне вносят нйи-
'Сольцую доле в рааброс выборочных точек.
Мч пришли к главным компонентам из чисто гесветрических
соображений "покажем теперь,что этот метод для гауосовсяих рас*-
пределеьиБ является оптимельним о точки зрения сохранения нч-
формадия.Пусть случайная величина ^ имеет ретпределанне с
■меткость» рСэс).
Оггоеделрцне. Количеством игфэрмкши.соотвотствушим
распределений р плотностью Р^х),называется величина
1=г $ ppe.)£«,pftc) doc.
Понятие информации имеет большое энэпенле в о&елттас.еьязаяшл
с кодированная н йередачзй данных.
4.В частив случае одномерного нормального реепределйнйя
J^->t*i,(l/(T).Стекло следует интерпретация величкш I; чек
йопык 1 (to есть ммь.3 среднеквадратичный геячрос С /утем
большее количество йр^^апли деот нам измерение вели-;ины % ,
ОТ
ii'jTtcTBei.'Ho позтоед строить такие np:isiu№i:,которые какей-тезк-
ровали бы знформациэ.
5.Если- f имеет нормальное распределение с
ковариационной матрицей А и нулеяш ербдьиу.то
Ооознятам ДТ) инфорнаыш.'.соотвстствуий';? случайному
вектору Ч - Т "$ ,гле Т олрзделено в (6 i.2).
6.Сектор и имеет /Vj Штернов ноомольпое ^асирец&лоаие
с матрицей Ё = Т А Т , и
Теорема 6.2. Т(Т) -достигает макекчального «лач^ниоtдотла
' (, t ?0,t -сойст&эниые «е-гтгг:- ■*.*!}.&& Д
соответствующие ее Л/4 максиманышм собственным значениям.
Доказательство .В;*ч1:слим производные фикции I (T) по
компонентам «актеров ti. Д$'етъ £j = [£i ,-..,£; ^тогда
согласно формуле (4.15"),
Булем максимизировать функцию TfTJ щи условиях (£.!.&)
.Составив функции .Иагранжа t-= I^g £ с£ (Н6$11г-4), получаем
условия экстремума* г
o'-TL/»e|4_ гр-*тд -гт).:г, r=j 0'-.^ ].
Ета система уравнений ькэдвалентна матричному уравнении
Л ТА кГТ или ТА= RPT • Гркравяивая обо части
равенства ноалемеатно, (ИИ;)* = S.CA'Ki/tftJjJi. ^/c .видим.что оно
удовлетворяется,еелр 'W*,..., "W*- — собственнее векторы иат-
рлцы А . иэ(Ы.Ч)вдшю,что матрица втерло- проязводнях
отрицательно определене, значит экстремум яьллется максчвдмом.
вз
7.Напасать программу,реглгзущуп мэто^ главных компонент;
емэото матрицы А попользуется выборочная ковариационная мат-
рица (5*.Ч-1| ЛГредусмотретъ в" программе вычленение собственных
пначьннй дул оценки рассеяния я потери информации,а такие вычке
ление количеств ннфорлаяки (начального и конечного) в предпо-
ложе1иу,1ТО распределение векторов признаков гауесезекое.
8,Провести несколько численннх еиспершентлв для раэлкч-
еых Еыборок.
. Литература: ГО, [21, [191, [2VJ.
6.2. Классификационные критерии выбора
признаков
Метод глазных кснлоиент ориентирован е основном на
построение экономичного описания ооъектов одного клясоа, Есги мы
инеем несколько клаосон,то сникенке размерности следует прокз-
яодить тея.чтобч со возможности нэ ухудаигь кс разделимость.
Пусть имеется два класса с плотностями распределенйир,Ск)
nPafx)n априорными вероятностями Pi, рг . Вероятность
ошибочной классификации остимшп-кого (байесовского) решающе™
правила равна;
х£ XI
паялучгаее правило выбора признаков дохлою било За выглядеть
следугаиим сбраасм:построить такоз ог&бракёнш, i':& —*R
( Ni < Ы ),при готором з-^ромиосг* *лмбки е новел пр1стран-
стве как i«-sho меньше превышала Ф Я» .Однако теяттим? К.
внтлеляетоя весьма сложно даде для распределений .простого вяла,
поэтому использовать ее в качестве критет>гч от<5е№! :га ''чт-сол
практически невозможно.Вместо этог" ""-«• <;сч"^,1Г'^ »' !сг-
5ь
рукцзп более простые.нс связанные о зелкчинс/й ошибки "R .
В теории проверю! гипэтаз известии несколько велнч/н.да-
ющих вергнвю оценку вероятности ошибочной яласспйккацли:
граница Черкова,К0Б<1фкцизнт Кхаттач'-.рия.диБергеяциЕ (смДЯЗ! ).
Зое они могут бять яепольяовэкк для гостроения нравила шбооа
признаков,мы подрогздо рассыотшм здесь коайрциент Вхаттача-
рил:
Смысл этой величинн становится понятнш,если учесть.что
.квадрат которых имеет конетнаР ннтег-
рал. Следовательно .их можно рассматривать как элементы
гильбертова пространства и tovjmi Jt всть cHcw^Soe произведение,
t£4Vpi,V|5).B силу веравейх-. ча 1'!варда %4l!l^(|*jv^ill'e i ,
Поскольку' под интегралом в Of. 2 1) стоит неотрицательная
']&ункндя,равенство /S » 0 возможно лишь в том одучае.ногдь
плотности р* и Рл ..в .?рекрыввются (р*Сх)вО apEj%(^>0
и ыпоборот).Но в втом случае возможна пешая разделимость
классов, К в О -С другой сторогш.если распределения
полысеть» совпадают. Pifx) =■ Рг(эг} ,то разделение невозможнее
этда случае ф * 4 , Эти рассуждения покаэывагт.что коэ№ога~
ент Бхаттьчария тесьо снязад с байесовским риском;в дейстьи-
тельнооти Д> является верхней оценкой дця ILm .
Теорема Б.,3.Пусть 9,* -баВеоовсяжЯ £жол,тогда для люОот;.*
Ofe А < 1 сараве^алво неравелстго ;
£ частаоотй,пр]( *t = т .шгеем R. *r ft
Доказательства rirteoon рнск иокет йить эашгсвя в виде;
1СП
Так как да? ллбых неотрицательных чисел Ctt, Ct* и дйото
О * Л- 4 1 сгразедушво неравенство 1">г*и/|*«,1чУь fl£ Q'^ ,то
отсюда coasy ncjjyvaei":
Ecjii вэнть Л- А ,то
ко Vp^fc t | maOipiii, О* К 4 -J
Иногда бывает удобно рассматривать величину Е>= - E>v ^>,
которся равна нулю для совпадающих распределений к & = •*"■.
если классы полносты- разделили.
й, ^'JbpjtaXRW ''■' - ес5,ь -^ -керннз кормадшне
распределения со средьими Oi и ковариационными матрицгга №; (см.
тгдре.лхв5 '-^- )»тогда
3.7сли отображение в пространство раявешоси» /Vi осущесг--
Блнетсп с номои(№ мат-рисы *Г . t - Т % ,то в ненок проотрсч-
i-тзе мы будем иметь две дормальчаз: распределения со оредиимп
Tfti к ковариагионными матрииаш ТАгТ* ,следовательно,
Ki^Bwpiei' г Ехаттачарая для этих раептеА-е-п^ниА ркмен;
B№-^P>i-Bi)kT*(TA,T'*TA,rV1TW.-o.
j, |ГТА.т%т*.т')/г1
ЕесОхэдичо hsJitii т-у^й wa" -:цу Т, * ивк кпзи ft*
f7 величину BfT) :
" .Таити выредакче г,-ш 3i ■>/■•-; vT В ( Г %ncrtv;b3j'fl
1С1
каксимнааты функции 6СТ)длл яаходдакы одтамалыюЗ мгтриш
Т (см,также 1сЬ1 ).
5.Ншшоатв ирогрзло ,реалкэ;/»цую данный едц^сркти.средусмои>-
рев я вей выэясленке величины & (до з после отоОраненин).
5.Смоделцровэтъ несколгло сбучащих ааоорок из аигся двух
нормальных рассределгсшй в применкъ к вил: программ выборе
признаков;при этом кеждай раз оценивать вяжчицу байесовского
риска по исходной выСорке й после отоорйсений.
Литература: fill, fie]. [19], 123]
6.3. Ettfop признаков на оснсче группировки
Дла снижения размерности гфооттнствапрязнаков можно
щиманитъ иетоды группировки,*! о показывает следщщио сообиа-
жнда. Предположим, что некоторые из цризкакос сильно коррели-
роваки маящу собой,тогда группу таких признаков мояно объедд-
'нить в один признак.При этом число признаков, описывэящпз. объект,
уменьшится с явэ^чмтелъной потерей гаформатЕИ.
для тэге,чтобы свести дало v привычной нам геометрической
картине .построим так называемое пространство объектов - нрэст-
ранетло размерности п ( П. _ддщш оо"у°ащей выборки),по
i; ^1 оси которого откладывэ.еч'ся аначеняе признака ка К -и
объекте.З этом пространстве кадщй kd Л' признаков изобрака-
етсн в виде И- -«ерного воктооа т. На рисунке
6.3-изображена внОорка;
— |-.'].«.-[*Л.*.-[!1,л-["Л.ь-[.|].
Волк имеется нечхолшо групп попарно силььо коррелярсран-
ищ ящзнаков, то в пэсстралсуве объектов Я. ЕОзнпк.,'ут
несколько комчактнкх маслеста ив блз'зло ледащих признаков (рис.5.4.).
Объединяя кажяу» гакуп гггрпд' в сч^'л прлзнагс,нацри^р,рэяв
,;оеднлй вектор какого .лноя?стаа,мн и примем к уменычеые:- раз-
«ерчоотг гространства призн-иков. .
с»1
!■• -«г t
, , , ^*~U
^—Т 1 *ш 7^ 2
*•» у\,
PiiO. 6.I. Пространство призраков к
проотоанство объектов
Из рис. 6 Д .хорошо ьидно,что для решения задачи груттьо.,-
ки признаков можно вос1юльэовать<"я охни* та алгоритмов самоо-
сучения.Ощшем ободо саему такого подхола.Пусть имеется ооучэ-
Поставим последовательность ччкюров в пространство объектны
и применим-к ней алгоритм самообученияJB результате вослечовг.-
те.иьность (t.^ ^разделится на заданное число Л/» грунт.Пусть
г -я группа .содержит -yj ве;;юрок11)4 +^г+.' * yw, « Л" ):
обозначим Ij множество номерол м'ктегоч.погаелтх: ъ % -w
группу, lj в \"ii *. . ., if 1 ) ь$ it, i N . Кавднй аа-
горитм самообучения лает гакок-ляйо хатлтерш А "центр" rpynr.i
■ рпример, средня-* те ктор, среднее чакрчи.' "нии s; т..4.Эти' цпщр,
^означим его rff ^ чклугся '£ вида1? 1-е,ртогч"'1,1-:о;иг|-!йх и
3 -Ю групцу. ,р- . ^ (jUi ^ ( ^ f .^ } ((_ ъ ъ)
итоСрР*енке шбоэтл (- 5 i) »■- irin^Tf,!^-/' мсавл*" " мир
чозти сттк.'лгс!ь теперь слеадмщвм о^изи*:в тчееэвз фд-. У«
гектара ^к Сер"г; ьстор Чь-=(ур^ ,4^'^'° чочь "не.(твмя г
IC3
■лдзеъ функции •Jjj onpcjejfflDTCH приведепццми вчле соотнеишнин-
Б качестве ыеры сходства двух признаков йеруу обычно кэ-
а№»диеаа' корреляции:
*Ч * «*. fj)/« hi Щ >J^^^ •
Поэтому вкберем S качестве функции потерь в фугааздояиле
среднего риска
й поса-рода соответствуй;^ алгоритм самооСучения.Использование
неречурредтного алгоритма предпочтительнее здесь в сяау того,
то длина обучающей аыборки (6.5 г) невелика и црииеня'"-ъ рекур-
рентнн!! алгоритм бессмысленно.
Построим по обучащеЧ ви£»р-зг^(,, ., {*/ аллкрическ;
■J^yBKuiiGjia)! с функцией потерь С6 Ъ.У) прк «шеле классов #»:
1 .Построить алгоритм динамической гщтширолки для даннсГ:
задачи (см.парагрг'i 4.4 ).Хараь,тер№ки центрами групп в нем
иаяяютсй среднее направления,
2.дягоритм снижения размерности ш основе втого алгоритиа
имеет- взд;
а&г Т.Кыбир-аРМ заданное число /Vt и члепкзл вектсрор *Р^
Шаг З.Вычисляем веиюрь Yi. - - -, ^лч " :
Шаг 4.Вола X II v; - *fc | > ё (^ -заданное малое число)
, ^4 < ^f
то ч« присвоить значения •?,■ .идти не :11аг 2,в противнем с^учэе-
на Шг 5.
Шаг 5.Образ ^'i,._ , Uh обучающей виберки в пространстве
R строится согласно формулам:
** ' % iTi, I! ^-ч1! ' ц . j a'
Конец.
4,Написать программу, реализующую ртот алгоритм,
Э.Оценить эффективность данного подход? .дая чогс омодели-
ровнть обучагацую вкборту из смеси двух # -мерных нсуьшышх
распределена? (о достаточно йольшим' А ) таких,ч.о признаки
образуй Й - 3 сильно коррелирсвачяых груши-. 1рнмзпия алгоритм
снижения рааяерности, построить в доном пространстве ба^есовечйз
решающее правило и сравьить его ошибку с ^алесозш риском а
исходном пространстве .Проделать несколько таких экспериментов.
Литература:" i *1. «141
€.4. Еизуальное отобратслне информации в
диалоговых системах кл£ссиййка>ш~а
Осноаньм требованием,которое предъявляется г лмэсда
алгоритму снижения размер»"сети,является оохрпречке; лол&игуршми
иохолнрй сбучавдей гыбсрки.Ето требование .латемагачеекк может
бить выражено разлгчяши способ&ик.ь эом ч«с.те в чисто геомет-
рически.Пуст1> имвегся обучастсая енсялш ^-i, , X ■, в р,)с<")
ранстве ft. ;необзсодимс. построить тьаув пустедозате^чостъ
V*»--- » tf« s ^-rf* ( "* ^^ M™^ язарлю-г
расположение точек \ У*1 KSit ac^in боте стктетс-гиогаЕл -.-гн'-тур.---
105
ции шборкк { Ж«},Клк численно оценить степень этого
соответствия? Пуоть 6 ij -расстояние меаду Яч, х^ , 8ij *HXi-a^(|,
acUj -расстояние меаду образами зтих точек, «Ау ■-=■ fityi -yj| .
Тогда можно считать опткмйльной такую кон^ягурацть точен {Ун\,
которая здиишизирует среднеквадратичную ошибку;
Возможны и другие критерии оптимальности отображения.и:шримег.;
Нзлбатее интересно представляется случай N* - £ .когле
1Л1 отобрежаем многдаернуя выборку на плоскость и можем
зрительно найгащеть результаты 1Ушосифичацяи.Дело в том,что рекение
задач;; классификации птхяюходат в условиях недостаточно парной
информации о структуре дакшх.е роторыми мы раЙотаем.КавдкЙ
алгоритм обучония или самообучения работоспособен при оиреде—
пенных ограгачениях.Применля его к реальным данным,мы не 8нае#,
аадедшены .ш в действительности зги огракичезия.Особенно
сильно это сказывается л задаче снмообучзния.гяе без допышителы-
кых исследований нетьзя знать.эда .ватен ли вибранныЯ фуккцио»
1'ал структуре rpyim.itaKOBO их количество,
У. здесь существенную помощь оказывает как раз воэшгность
ария&таюгэ гфедставления дзвьнх. Контролируя результаты решняя
закячи хазеенфвкедия,внося лоцравки в начальяые предпосчлки
1чзело классов.тип разделишрй поверхности),выбирая наиболее
и"одхоляадп( елгоритм.то есть,ссущестзляя диалог с ЭШ,ан можач
добиться бо.'/ее надежои результатов распознавания.
Г.Наакоать алгоритм дву?/ерного отображения на оогово ь:е-
■к>дг крнгчзДяюгс спуска мипплчзаи" о.цчой za д^тн^ий *f •
106
Предусмотреть возможность вывода на экран не только ебучашей
Шиорк2,но и разделящей поверхности.Это мокко сделать .екалеч,
еледущим оСразом.11а разделяющую поверхность в цроотркюмто
признаяовк наносится достаточное колячесазо точекsk,..., Й* „
IfccJie того как образ обучающей внссрки построй.производится
отображение точек {%Лна «лоскость ft , 2v —* £* так,чтоб«
расстояния между точками {^«]. (хк]в неибслъшзЭ степени сс-
ОТЕОтопгосапи расстояниям ыезду {ЭЬ»1. IУи\('1,(1 рсть 0!!Н£Ь
применяется критерии тшш 3 X
2.Огладить прогреМ1г/,рвшшэущую даяны£ метод.Применкть
ов для отображения -каких-либо простых трехмерных конфигураций
ра плоскость о целью проверки шботоопосойноотл.
S.Смоделировать несколько обучащкх выборок из смеси 2-х
й 3-х нсрмьлышх распределения для размерностеР,к£Ярииер,3,
5,1СОтобразить их яа плоскость вместе с байесовскими разделн-
шши п-овертаоС'.'ямн.Иаобрадять графически результаты шподше-
кия пунктов 2,3.
Литература: 1й1, [*] . (1С1. П«1, СИ« .
яяжжнше. метод стоисзической ашршсиущи
П.1. Алгоритм Роббинса-Ыоцро
Кетод стохастической аппроксимации исследует итернтйвнне
алгоритмы речения систем у^эаэнениИ и иахсощения вкотремумов
йдгоктдий при наличия случаРнях возмущений. Одни, из гякнеЬшиг
яынегея алгоритм РоЗбинса-Мгифо;раэбзрем вдею втсго слгсря-лла
на простейшем примере решении одного уравнения со скаляртлм f«*
известным.Ка рисунке П.1.и80бражена функция £(Ъ/и ее ьвпасреи-
нге с помехой значения.
Рис, ПЛ.
для нахождения корня уравнепия Д?1-)=>0 Robbing W.., в
.МОПГО S. в /Э51гйфвдложилл использовать алгоритм
t-*.* - t*я - у. Y(t-„), (n.i.i)
rneY^"")51 ffr")*- ^С^*) -намеренно:; в точке -с- эничеяие
функции J-Ct) с помехой, тТк j -«еотритатедьная чиелсьа*
гтппладпвгтельность.Еоли нчмеха шест чулевое математическое
отиллнии.то в среднем гправу от Т^ Аудет Yfr} *0> в слева
YCt") * О .Поэтому в среднем сыещечяе е алгоритме^.!,!) про--
игячцтгп в сторгеу корм tv ,чго и позгожет надея^ьск на
eadorecHnrViiocTb алгопвт*а.
Нсно,чтс сходиопсть сильно зааксст оз' выбор? згличик ■£,.
1рсда!1и«км.чя'о (яд из "^ схсдс-тсл, S 1^, ЕС<«,« лусгь
я-унагай /О*1} к нш-эуи %<f) огренгч&ы, lYVV) )* К .тогда
X Itv** ~ тл, I - -ton. X It;;,j - -^ I ^
Если начальное приЗлиюние *т^ иыбракс достаточно дааеьо os
tJt ,то последовательность т^, никогда не дооерется .not-^ .
Следовательно,необходчмое условие сходимости: К ^"« *= -~».
С другой стороны .последовательность {жЛ должна
достаточно быстро убавать.так как иначе помехе будет "раенаяивьть"
эцзяку тг„ и сходимости яе будег.Ьиие мы увгдлм.что
достаточную скорость*убнввния гарантирует условие Зи'У'п <«
подходящим выбором коатому является "f*. = 'fo/'n.'f-у < * * 4)-
Подробное изложение теорот п прилокени!" метода стохйсти-
чзской агафОЕсвмащи hiwho шЕте в работах fej,[f'3r[2&],[a^.
Ш здесь остановимся только па обосновании алгоритме. Взебянса-
Нонро,яа котором осков&нн многие алгоритмы нестроения решан>цвх
Еразял.Сформглир;ем иго не в вплеfГ1.1.)^,а в той форме,в какоР
он ойгшо используется в задачах распознавания образов.
Г!усть имеется Еекгоонозначная функция дау* переменим
ffx,^) XtС" t-eB*H векторная случайная величина £
со-8начешсии в К. .Необходимо решить систему уравнений;
Т^(\,^)'0, (П1.2)
при втом раепрзделекие релттчзшы i неизвестно,я пкеетая
повторная Euc'qptflXj.,..., ЭС„-последовательность яез&шоешх
решкзапвР. спуча£ной величины к .Алгорыта РобЛинса-Мояро р^>
авпя етей зздячя имеет вид
iOS
кяи необходдао миянкиаяровать фуннлаю Efi(>,i-j (й(х,тг)
заданная скалярная дифференцируемая ^щения), то, исходе аз
условия ее экстремума
EC*Q ($,-*)-о,
годучаем вллегитм
T«*i - Г. - ?„ ^ fl<33H,f«) . ( Ч« 4)
Ьленно этим объясняется выбор знака минус в правой части<Я1$1
обычно мы подря8ум9ъабм,что уравнение {П-1.г)воз'аЕсает из
задачи |ЯК1игаэят'й некоторого функционала среднего риска.Е едущее
'лакстщэгигк знак прчращеяил в(П.И)меняетсл на плюс.
Заметам,что алгоритм {П. £.3) легко сводится к(П.1 4),если по-
Дда доказательства сходимости алгорнтма(П.1.2рнам поначо--
сятся сЕойстьа условных математических окидавий,которое мь
чркнедзм здесь Cms доказательств (подробке №. в li^l, [2¥ji-
Цусть if е Ч -случайные величины^усдовгюе математическое
еддаияе i при условии ^ = У- лУ5еч обозначатьE(V 1 "'/)•
з условное матег.№..т]" ч: ожидание V стЕССИ'."ельно J чероэ
йсле i есть функция от *i , ^ i= /'7.) ,То
В;л-.т V _-гамЕ^ ья^стор-тя ояучдкн&я тгрлг^Лй£и|^гМ£(£^
гслц с ■?;__._ it V .тл
110
Матемятанеоков ожидание от условного математического
ожидания равно обычному математическому сашданлю:
Е(ЕЦ/1|) = ь^. (П.1Ь)
Если тЯ есть функщя случайной ввдещьы ^ ,V~ ИЧ) i
ЕЦЛ>ЬЕ ($/{,). (ni.e)
Докажем георему о сход-моста алгоритма^. 1.3).
Тогрсма ПДЛйготь выполнены следующие, условия: еущесрвуе-/
такой вектор Тг^.что EG,Q/£*•)=-С* ;ддя любого *t- «3. Р.*:
t Ct. Са -некоторые константы)рюследовдтельноетьnfhJудов-
ли1ъоррвт ограничения;/;
Тогда алгоритм(П.1_%)схо;ютда в ореднеквадрьтячлс*.! E'tV"
■C^'m- ElTv,-tvl*-flL rn.1.13)
ДОЕазательство.Согдьсяо алгоритму (П. 15),
-Zjr-(f.fK„,Tr„),'tt.-Tr-,)»j-„"||<i.te„,T-.)ii2
Возьмем уловное математ!гческое охгашкие отаосктелыюХ!, .5c_i
от ойегс чаате* нгого равекитва.Тах как т^, ьсть функции 0,г
Х^, .^Vi.TO eol'jLiCHO Cfl-i-ff)
Ь(!1Тг„ -f. II V^i, ■ -.^.-l)" ll'CV. -Т. 1!
рстлеткио везаыгсииоош ^С cTXi,..., ССк-^яэ сы*Ее1в(П-1.б)т
(Л 1.4-)uc«iriaei.ij
Е<?Ч"(-ж»л-„>,тг„-тг»)/;с1,...,х,,.0«
111
ECJ^(»«,t^')«Vbti,...,x».i)-El4,№,'Kj||?
С пометило вывевеншх оеотношениВ находим:
- й}"„. ( Е cj, («^•c-j,tt1._t») I- J"* E flij.et.'t-JII*
и eoMj(n.l.iC),(n.t.li).
Е(||тл„-т.Иг/я.1,..-..Жк-0« U-c-t-.ll1-
-гу„С1 II тя-тт. II2- j-.?c, (i+ iit-.n»),
Б правой части ааибшм1|'е-„1''',воспольэовсв:пись неравек-
ЦТ-.»» t *(!•&. -T.nsiiT-.il'), |
затем вовилем от обеих частей математическое ожидание и
применим сБоестБо(П.1.1).Тогда для последовательности
&.- ЕВт«.-т„1*
получим неравенство:
Жедел очэвидные переобозначения, запишем его в более
компактном виде
^,.4 £ (1-«.„♦■«.,) ft, *е*; (П.м^
ыпеледоватечьяоета {Р-ДД^и^ . {Си\ эдест. удовлетворяют уе-
дйм-й 2с*..= ~, sa2<<«, и*г.**~, хеп<*.
„1гачея,™то пооледогагыш'остъ £>„ сходится &. нулг.эч'С Е-
Судет означать справедливое г ь утверждения теоремы.
так как ряд sea Ок расходится,» ряд лв -6И схолдтое.то
и&чяяэл •; некоторого н-wepft tn, Лп i, £ О-у, f S > °) >
J12
а гак как кроме того, С —* С ,то начиная с некоторого
несера m- = J-rKfe),
Подставим ату оценку в (П.1ДЧ):
$„,i& (i -&a„)8h+C* для л,гт.[й).
Применяя последовательно данное яеравечство.ЕэхоАШ:
ft*, г ^ (1 - A«m.i) им + С™ i *
Отсюда нетрудно вивестн оощее соотношение:
гае fft (1-xoo, <4s.n»
I t-еч v "
/'si" 1 1. .. s""-.
[О, g > п..
далее.иэ раажетешн tu * I ■*■ «+<Кг/24 ••■ следует,
чго I + 1Л * &" .шкжаду 1ПИ достаточно оольтх П-
при ц, —* ««> ,Иэ определения величин /itM имеем
о lea клн f £ ^s*«,4 *-»T0 этот Р4* сходится абсолютно,и жж-
йи «шешть местами оуинпровггие и пределынй переход:
сгадоглвелык), ^* iwr^r ^ ,и теорема док-гзвча.
113
0.2. Доказательство сжщямоотя реедрертных
ЕШ-оритмоБ самообучения
«в^аедЕо&йддовательяост?. сдучайню: взлячкч^,..,,^
называемся полушртлнг&аш.бсли
Понятие иолтодартинпылов используется для обоснования
сходимости рекуррентных алгоритмов агаптацки и обучения (£],Г223,
при этом устаишдашаеаер с^оддюсть с вероятностью гдкнпцэ.Яо-
лумартангал является обобщением ионятия убывающей
последовательности на стохастетеошй случай. Ограниченная снизу убивающая
последовательность имеет аредел; оказывает^, вто свойство
сохраняется н для п&щиертштелов.
Трорема (Д*.Дуб). Если пелукартингал "V ^ ограничен сшяу,
и 8LfpEt\^.l<ee,T6 существув! случайная величинв i„ такая,
что £„£*- £. . El^|<-.
№ исиольвуау творец Дуба для jiDKasareabCTBa аходимосга
рекуррентного алгоритма самообучения общего
вцда(М^.Предварительно докажем рспомогагельвое утверждение.
Лемма Дт1.Пуогь последовательность Ееотрицательякх слу-
чайннх величин ( >,J удовлетворяет одному ез услоЕай:
Щ„, /\t $„)«?»-*> ("•*•*)
E(J„l/|«,....^)<M'-«->«'--.
(Л.П-, «и -неслучайные последовательности.
Тогда с "вероятностью I существует предел-
Дюказателъстио.Рассмстрим всьемоют 'льяую пос'еловгтяль-
НОСТЬ V V.f п
Со!№сео(П.£.0 и свойству (П. 14J .имел»:
E(^.„/^,,...te,)-E(/b«.i/J,,...,^5-
гак чго ^(Ьи1-полуийртш:гал.В силу с холима щ гида X й-.;
Е1/1»|«Е1^|-2е», sEl$,|*2gf,,<_
следсшательяо,»"ожно щжменить Teopatiy ДОр^сказатрдес-гво
да т-орого условия иолучкется ачалпгкчно.ес^и доказать.-я-о
"Ос-£еасвательность
яиляе-гся Еолумартшгалом.
Обратимся теперь к доказательству твэремы 1.3. о
сходимости рекуррентных алгоритмов caMooojnje-HiwiJlorta-wji и рычтем
лз ijaoHOCTaRCti't)-Прилагаемое
м
и сгругаируем в следующем порядке:
м _
«5
Лршеичд ко второму слы-ае.чому лчыыу д..1«дзя .Ai =■ Xi (t«»»),
Xi eXi(T^#i)(«Ji(x.)=l3.i_('X-,tv1t3[),y6esfl3e«cfl в гом.что оке
яожигомтсяъно и сладователья'1.
Целее,
_OB^:-1t-il-n'W!!-'rjf>),i)<l>tl В В ОМУ У0Л<ШИ,2 "
телим образе»],
*-** At Си)
Возьмем от обеих «астеЕ вютс неравенства условное
математическое ожидание относительно эо«.: .,0Сц-1.Учитывкя,чго'с^
воть функция от *!, . .^^.получаа в шщу своЙст1А(Л.1.Б);
Из независииоетв Di„ отзе*,... ,ou*-i и свойств условных
математических авдданиС ьиьодлм;
EfCi-'rf'A'v .*»-.>=-<ГЛ t4i irf'lpMdi,
E (11-г.Й -тг™ !1г/х4 к..,) *
= 3T« E(\cc..,(*»lRVc<li(*,.tJ»')llAt.1.,..fa^.
XifB.1
Подстановка выведенных соотношений в неревбнстзо(П.а.*)
дает;
E(Rfc».i)/b^....,-»,.i)* Е(т-1 -
Обозначим j^
V (T) = T. I! 5 It (Ji(syrK>>pte)<J zc |»
тоцда с учетом услоЕИЯиЗ ,
EfR(Ti,,iV3Ci х„ч)<
Отбрасывая отрицательное слагаемое в право? чмзта к ио-
яолъзуя ламму 1!.т.,доказываем,чго£(:"С'^) —^ Е* .йзяз от об->-
етс частей неравенства (П 2.Ч) магий-ч'.ич^сиг.е ao'Laimc- j»
проаудировав пз Н or i но Л* ,110.1/4*11.!;
ER(f„.) 4 Е(тг) ч-сьГу* CRfr-l -
Так как ER(*t>^—■* ЕР» ,а ряд 5Г Y* сходится,го переходя
к пределу У/—■"<« «уСеядаемся в сходимости ряда Х!я, EVfoi
Поскольку Z-yi,-**0 ,то отеща следует.чго на .чекотсрой под-
вделадоьатедьности E'VfT^)—*0 .а тстаа VC^) "'-^ С?
я следовательно,существует подцос-тедоватзл*нсст£ M-g >на
которой V сходится к нулю с вероятностью единица. Гаорема
доказана.
С помощью,8той общей «еррмн мохно обосновать сходимость
ГСлльйюго числа чаотшлс случаев алгоритмов семооЗуч!51ШГ.Неко-
торнв из них рэсшлтренн п vnee& У.
СОДЕРЖАНИЕ
Введение 3
Гаава I. Основные донятая к методы теории
распознавания образов
1.1. Пространство признаков и априорная информация 6
1.2. Детерминированная задача распознавания ... 13
1.3. Вероятностная задача распознавания .... IV
1.4. Автоматическая классификация 2Ь
Глава II. Оценки точности алгоритмов распознавания
Моделирование на ЭВМ
2.1. Оценки достаточно* длина обучающей
последовательности .... 40
2.2. Оравило останова кснечноясодявкся
алгоритмов обучения 46
2.3. моделирование процессов распознавания на ЭВМ '18
Гжава III.Распознавание точно разделимых классов
3.1. Цероелтрои Ф.Роэекблатта 52
3.2. Конечноеходяф.эся алгоритмы обучения распоз-
наванюз образов . 55
3.3. Разделение нескольких классов Ь7
3.4. Цостроение кусочяо-яинсйной разделяйте*
поверхности 60
ш
. Глава 1У. Вероятностные метода построения ]
правил
4.1. №тод максимального правдоподобия ...... 64
4.2. Яарзеновские оценки плотности . . . . * . . 66 -
4.3. Разложение плотности распределения по
базисным функциям ....... ^ ........ 69
' 4.4. Незосредствённая аппроксимация байесовского
решающего правила . . » , ■ . . .- . -71,
Глава У. Алгори-гмы автоматической яласйфнсации.
5.1.Метод К.ШфОсна разделения смеси нормальных
распределений .......... 74
5,2- ^етод локальной оптимизации ...... i ... 77
5.3. Рекуррентный алгоритм разделения смеои
многомерных нормальных распределений ....... 79
5.4. Рекуррентный алгоритм самообучения с поиском
центров.классов ......... „ ..... &Т
5.5. Рекуррентный алгоритм самообучения для
выделения сильно вытянутых параллельных множеств 93 '
5.6. Алгоритм самообучения "ЙЗОДЕЙХА" . i . . . &&
5.7. Эвристический алгоритм группировки , . . . • 88
Глава У1. Выбор признаков и отображение информации
в системах распознавания образов
6JI. Снижение размерности. Метод главных ко-тонент 93
6.2. Классйс^кацнонные. критераи'выбора признаков t 96
6.3. Выбор признаков за основе группировки , . . 101
- 6.4. Визуальное- Отображение информации в диалоговых
Системах классификации г-.г- ,..,.... 104
Ui
вртшивм, Иетад отохастичеошя еппрысоишциа
ЯД. Ахгоркти {ЪМано-Иокро Ю7
13*2. -4мааател>ст9о сходямооти рекуррентных
алгоритм» саяоэо/чеиш ю
Ахшикдуеяая лтрвтура Д8
Виктор Николаевич Лиховмдов
(РАКГИЧШКИЙ КУРС
РАСПОЗНАВАНИЯ ОБРАЗОВ
Учебное пособие
Редактор r.n.fyphdH
Технический редактор И.А.Гребек1жо&
Корректор Л.З.Аннпко
/
*