Содержание к диссертации
1. ПРОБЛЕМА РАСПОЗНАВАНИЯ ОБРАЗОВ ПРИ ОТСУТСТВИИ ЯВНО
ВЫРАЖЕННОГО ВЕКТОРА ПРИЗНАКОВ ОБЪЕКТОВ 13
Принцип ортогональности главным осям выборки и принцип гладкости для регуляризации построения линейного решающего правила в пространстве проекционных признаков 52
2. ОБУЧЕНИЕ РАСПОЗНАВАНИЮ ОБРАЗОВ В ГИЛЬБЕРТОВОМ
ПРОСТРАНСТВЕ ОБЪЕКТОВ 55
Метод опорных элементов для обучения распознаванию образов в гильбертовом пространстве 63
Метод скользящего контроля для оценивания же грагю.ляционных свойств решающего правила по обучающей выборке 78
Загрузка и редактирование данных 91
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 119 ЛИТЕРАТУРА 121 ПРИЛОЖЕНИЕ 1 130 ПРИЛОЖЕНИЕ 2 138 ПРИЛОЖЕНИЕ 3 141
Изучение способностей к распознаванию, которыми обладают человеческие существа и другие живые организмы, так называемый феномен восприятия.
Развитие теории и методов построения устройств, предназначенных для решения отдельных задач распознавания образов в определенных прикладных областях.
на III международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (Нижний Новгород. 1997 г.),
на IV международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (Новосибирск, 1998 г.),
на IX Всероссийской конференции «Математические методы распознавания образов» (ВЦ РАН, Москва, 1999 г.),
на V международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (Самара. 2000 г.).
на международной научной конференции «Интеллектуализация обработки информации ИОИ - 2000» (Алушта. Крым. 2000 г.),
DIMACS Working Group Meeting on Informatics of Protein Classification (университет RUTGERS, США, 2000 г.),
1APR International Workshop on Machine Learning and Data Mining m Pattern Recognition (Institut fur Bildverarbeitung und angewandte Informatik, Лейпциг, Германия, 2001 ),
на ежегодных научно-практических конференция профессорско- преподавательского состава ТулГУ (Тула, 1998-2000 г.),
на семинаре отдела Вычислительных методов распознавания ВЦ РАН (Москва. 2001 г.).
Введение к работе
Последние достижения в области науки и техники, в частности, стремительный прорыв в сфере компьютерных технологий и, как следствие, увеличение доли применения вычислительных средств, вплотную подвели человечество к переходу из общества техногенного к обществу информационному. С развитием сетевых технологий появилась возможность говорить о едином информационном поле. Человечество вступило в эпоху, когда созданные им информационные системы окажутся в состоянии решать много более сложные, чем когда бы то ни было, задачи. Одной из важнейших проблем, возникающих в связи с созданием современных полностью автоматизированных информационных систем, является автоматизация процесса распознавания образов - область, изучением которой занято большое количество исследовательских групп. Исследования в области распознавания настолько масштабны. что, пожалуй, невозможно перечислить все направления науки, в которых они ведутся - от появившегося достаточно давно распознавания печатных и рукописных символов, медицинских, метеорологических и других данных до распознавания сейсмических сигналов, позволяющего отличать ядерные взрывы от землетрясений.
Проблема распознавания образов сохраняет свою актуальность уже без малого полвека. Несмотря на относительную новизну проблемы, ей посвящено огромное число научных статей и монографий. На начальных папах своего развития теория распознавания имела мощнейший источник, подталкивающий ученых к все более глубокому изучению и осмыслению задач узнавания в их применении к техническим системам. Таким источником была идея создания искусственного интеллекта. Крайне популярен был вопрос о том. сможет ли какое либо устройство самостоятельно войти в контакт с окружающим миром, осмыслить этот мир, приспособиться к нему, а затем и управлять им.
Распознавание образов - одна из главных функций всех живых организмов. Поэтому достаточно полные сведения о механизме распознавания образов можно получить при исследовании поведения живых систем. Первыми проблемой обучения распознаванию образов заинтересовались биологи и психологи, а за ними - уже математики и инженеры, так как они хорошо понимали, что любой интеллект, в том числе и искусственный, начинается с восприятия внешнего мира. Нельзя всерьез рассчитывать на создание искусственного интеллекта, не позаботившись о том, как этот интеллект будет снабжаться информацией, как он будет разбираться в океане разрозненных сведений об окружающем его мире, как он будет ориентироваться во всевозможных ситуациях в процессе принятия решений.
Недаром, один из первых подходов к проблеме обучения распознаванию образов основывается на моделировании гипотетического механизма человеческого мозга. Основоположником такого подхода считается Ф. Розенблат [36]. а системы, основанные на таком подходе, называются перцептронными Как оказалось, другие системы не сильно отличаются от перцептронов. Более того, системы перцептронного типа могут практически выполнять почти все. что доступно и более широкому классу распознающих систем.
Следует отметить, что на современном этапе специалисты делают достаточно скептические прогнозы по поводу построения полноценных систем искусственного интеллекта. Пришло понимание того, что построение универсального, всепонимающего робота мечты 60-х годов - и нецелесообразно. Гораздо важнее умение применять и адаптировать уже созданные наработанные процедуры к специальным задачам. Не так уж плох простой и ясный подход: конкретная задача (класс задач) - конкретный алгоритм решения.
Итак, в задачах распознавания можно выделить два основных направления:
Процесс распознавания состоит в том, что система распознавания, сопоставляя апостериорную информацию относительно каждого поступившего на вход системы объекта или явления с априорным описанием классов, принимает решение о принадлежности этого объекта (явления) к одному из классов. Правило, которое каждому объекту ставит в соответствие определенное наименование класса, называют решающим правилом распознавания литературе, посвященной распознаванию образов, утвердилось мнение, что суть проблемы распознавания заключается в определении решающих правил, то есть в нахождении в признаковом пространстве таких границ, придерживаясь которых признаковые пространства некоторым оптимальным образом, например, с точки зрения минимизации числа ошибок распознавания, разделяются на области, соответствующие классам. Проблема распознавания как- раз и заключается в отыскании таких решающих правил. Различают задачи обучения распознаванию образов с учителем и без учителя. Задача обучения с учителем предполагает, что каждый объект в обучающей совокупности представлен идентификатором своего класса и образом в пространстве наблюдений. Такую задачу называют также задачей обучения по классифицированной обучающей совокупности, или обучения по прецедентам. В случае обучения без учителя в обучающей совокупности отсутствуют данные о принадлежности объектов к классам, и обучающая совокупность представляеч собой просто конечное множество объектов в пространстве наблюдении
Существует множество методов решения задач распознавания, среди которых выделяют такие как геометрический и структурный подходы, перцеп- троны, потенциальные функции (М.А. Айзерман, Э.М. Браверман. Л И. Розоноэр). статистические методы (В.Н Вапник. А.Я. Червоненкис), допустимые преобразования, вычисление оценок (Ю.И. Журавлев), математическая лингвистика (Э.М. Браверман, И.Б. Мучник), логико-комбинаторные алгоритмы (А.Е. Янковская), комитетные конструкции (В.Д. Мазуров), метод опорных векторов (В.Н. Вапник).
Тем не менее, в такой уже ставшей классической области кибернетической науки, как теория обучения распознаванию образов, еще остается множество нерешенных проблем, одна из которых и являются предметом рассмотрения данной работы.
Как отмечалось выше, теория распознавания образов разрабатывает методы построения формальных решающих правил в предположении, что на анализируемом объекте уже измерены значения так называемых полезных признаков, или, как принято говорить, он представлен в виде точки в признаковом пространстве. Формирование решающих правил распознавания в процессе обучения основано на так называемой гипотезе компактности, согласно которой объекты, отобразившиеся в близкие точки в пространстве признаков, скорее всего принадлежат к одному и тому же классу.
Следует заметить, что выбор признаков, образующих удобное для распознавания пространство, представляет собой отдельную весьма сложную проблему (В.И. Васильев, Н.Г. Загоруйко, Г.С. Лбов). В то же время существует широкий класс прикладных задач распознавания образов, в которых легко удается непосредственно вычислить степень «похожести» или «непохожести» любых двух объектов, но трудно указать набор осмысленных характеристик объектов, которые могли бы служить координатными осями пространства признаков.
Специфика именно таких задач обучения распознаванию образов изучается в настоящей работе. Предлагается два подхода. Первый: мы рассматриваем неотрицательное число, характеризующее похожесть пары объектов как скалярное произведение некоторого гипотетического набора признаков в воображаемом гильбертовом пространстве. Как и в классическом подходе к проблеме обучения, мы опираемся на гипотезу компактности, которая здесь трактуется непосредственно, а не через промежуточное понятие линейного пространства признаков. Второй подход, вместо линейного векторного пространства признаков, в которое объекты распознавания отображаются лишь условно, мы рассматриваем в качестве характеристик объектов отсчеты проекционного пространства, опирающегося на проекционные признаки, роль которых играют похожести на некоторые заранее заданных (пространствооб- разующих) объектов.
Тем не менее, мы используем здесь принцип формирования решающего правила распознавания [52, 105] созданный, именно для обучения в линейных пространствах и получивший название метода опорных векторов. В начале 90-х годов, работая уже в США, в AT&T Labs, В.Н. Вапник переработал метод обобщенного портрета, созданный им и А.Я. Червоненкисом [12] в период их совместной деятельности в Институте проблем управления АН СССР, и предложил красивейший оптимизационный критерий построения решающего правила обучения [52]. Сущность предложенного критерия имела настолько глубокий смысл, адекватный природе большинства прикладных задач распознавания образов, что он сразу завладел умами специалистов в области анализа данных. Появился целый поток публикаций 51,52,91. 104, 105, 106, 107], интерпретирующих, дополняющих, развивающих предложенный подход. В диссертационной работе показано, что основная идея этого метода опирается, в сущности, не на наличие в пространстве признаков линейных операций, а на возможность вычисления взаимного сходства объектов, для непосредственной реализации которого достаточно рассматривать скалярные произведения из гипотетического гильбертова пространства. В силу такой замены мы будем использовать термин «опорные элементы» вместо термина «опорные векторы», имеющего смысл лишь в линейных пространствах.
Эксперименты, проводимые в ходе исследований, показали недостаточную статистическую устойчивость решающих правил, построенных в гильбертовом пространстве объектов с нефиксированной размерностью, что объясняется проблемой «проклятия малой выборки», характерной для задач распознавания образов в случае, когда число признаков близко к числу объектов обучающей выборки или превосходит его. Для повышения статистической стабильности процесса обучения, или, как принято говорить для его регуляризации (Ш.Ю. Раудис, [35]), потребовалось привлечение дополнительной априорной информации, отражающей природу конкретной прикладной задачи В диссертации разработаны методы учета такой информации.
Кроме того, достаточно детально рассмотрена процедура оценивания экс- траполяционных свойств полученного решающего правила, называемая скользящим контролем. Предложен метод ускорения этой процедуры с точки зрения вычислительной эффективности за счет учета специфики критерия обучения по методу опорных векторов. Предложена концепция дообучения с использованием результатов скользящего контроля.
Научная новизна работы. В работе впервые предложена концепция погружения множества реально существующих объектов беспризнакового распознавания образов в гипотетическое линейное пространство со скалярным произведением (гильбертово пространство). Предложен класс линейных решающих правил и критериев обучения беспризнаковому распознаванию образов в гильбертовом пространстве объектов. Предложен способ регуляризации обучения беспризнаковому распознаванию образов с целью повышения статистической стабильности получаемого решающего правила.
Степень обоснованности результатов. Научные положения, результаты и выводы, сформулированные в диссертационной работе, обоснованы теоретически и обсуждены на семинарах и конференциях. Обоснованность предложенных моделей и алгоритмов подтверждается результатами обработки реальных данных
Практическая значимость. Разработанные концепции и алгоритмы существенно расширяют круг прикладных задач, к которым применимы существующие методы обучения распознавания образов.
Связь с плановыми научными исследованиями. Работа выполнена в рамках договора о сотрудничестве между кафедрой автоматики и телемеханики Тульского государственного университета и Department of Computer Science государственного университета RUTGERS штата Нью-Джерси (США), и при поддержке Государственной научно-технической программы РФ «Перспективные информационные технологии», гранта Российского фонда фундаментальных исследований, гранта Министерства образования РФ.
Прикладные результаты работы и их реализация. Разработанные алгоритмы реализованы в виде программно-алгоритмического комплекса обучения распознаванию образов в беспризнаковых пространствах. Апробация работы. Результаты диссертации докладывались:
Публикации. По теме диссертации опубликовано девять статей. Структура работы. Текст диссертации состоит из шести глав. В первой главе рассматриваются современные проблемы теории распознавания, в частности, метод опорных векторов, особенности обучения в условиях малого относительного размера обучающей выборки по сравнению с размерностью признакового пространства. Показаны примеры прикладных задач, приводящих к необходимости обучения в отсутствии явно выраженного вектора признаков объектов. Формулируются основные задачи исследования. Во второй главе рассматривается структура решающих правил распознавания в беспризнаковых пространствах. Предлагается критерии и алгоритмы обучения в беспризнаковых пространствах, а так же методы регуляризации полученных критериев. В третьей главе рассмотрена процедура оценивания экстраполя- ционных свойств решающего правила. Предложены методы повышения эффективности обучения путем смещения порога принятия решения в польз}' того или иного класса. В четвертой главе приводится описание программного комплекса обучения распознаванию образов, реализующего алгоритмы, предложенные в основной части работы. Результаты экспериментального исследования алгоритмов приводятся в пятой главе. В завершающем шестом разделе перечисляются основные теоретические результаты, достигнутые в работе.
1. Проблема распознавания образов при отсутствии явно выраженного вектора признаков объектов
1.1. Прикладные задачи беспризнакового распознавания образов по критерию сходства объектов
1.1.1. Распознавание рукописных символов
Наглядным примером задачи распознавания образов при отсутствии явно выраженного вектора признаков объектов является задача распознавания рукописных символов, например, букв, при их вводе в ЭВМ непосредственно в процессе написания с помощью специального пера. При таком способе ввода каждый символ первоначально оказывается представленным сигналом, состоящим из двух компонент, а именно, текущих координат пера по вертикали и горизонтали, однако, может оказаться целесообразным использовать и дополнительные локальные характеристики процесса написания, например, угловой азимут мгновенного направления движения пера, его скорость, силу прижатия к бумаге, временные отрывы от нее, наклон и т.п. В качестве аргумента сигнала может выступать либо время, либо длина пути, пройденного пером отточки первого касания бумаги. На рис. 1.1.1 представлены трехком- понентные сигналы в виде функций координат и азимута движения пера от пройденного пути вдоль его траектории, полученные при написании рукописных букв «6/» и «б/».
В этой задаче трудно указать заранее фиксированное число признаков сигнала, которые могли бы сформировать пространство, удовлетворяющее гипотезе компактности. Нельзя использовать в качестве признаков и отсчеты сигнала, взятые с некоторым тагом вдоль оси аргумента, поскольку сигналы, полученные от разных написаний даже одного и того же символа неизбежно будут иметь разную длину, и, следовательно, не существует единого линей-
мою пространства, в котором могли бы быть представлены написания распознаваемых символов [77].
Заметим, что разные варианты написания одного и того же символа естественно представить как результат некоторого нелинейного преобразования оси аргумента, приводящего к ее сжатию либо растяжению. Эти различия между разными написаниями, несущественные с точки зрения распознавания символов, легко компенсировать с помощью процедуры так называемого парного выравнивания (рис. 1.1.1), тогда остающееся несовпадение сигналов будет нести информацию об «истинной» непохожести сигналов, которую естественно принять в качестве рабочей метрики при построении процедуры обучения распознаванию символов.
1 -'1' I.
V-/
Рис. 1.1.1. Два сигнала в виде функций координат и азимута движения пера от пройденного пути вдоль его траектории, полученные при вводе рукописных символов в компьютер непосредственно в процессе написания Совмещение произведено по значениям азимута
1.1.2. Распознавание классов пространственной структуры белков
Другим примером задачи распознавания образов, в которой трудно указать явно выраженный набор разумных признаков, является задача классификации пространственной структуры полимерных молекул белков, опираясь на знание лишь их первичной структуры в виде последовательности ами
нокислот, которых в природе существует ровно двадцать, и которые принято обозначать буквами латинского алфавита.
Информация о пространственной организации белка (его пространственной структуре) является очень важной для понимания механизмов работы макромолекул и их функций. Пространственную структуру макромолекул определяют экспериментальными методами (рентгеноструктурный анализ, ядерный магнитный резонанс). Эти методы являются чрезвычайно трудоемкими и требуют больших затрат времени, но позволяют получить достоверные сведения о пространственной организации молекул. Характерно, что для больших групп эволюционно родственных белков, подчас значительно отличающихся по первичной структуре и, значит, по распределению всех атомов в пространстве, способ укладки полипептидной цепи остается в главных чертах неизменным. С другой стороны, при всем разнообразии пространственных структур белков удается выделить относительно небольшое число типов укладки полипептидной цепи. Налицо задача классификации - выделение групп достаточно близких друг к другу белков.
1СС5 Cytochrome c5 {Azotolnicter vinelandii)
GGGARSGDDV VAKYCNACHG TGLLNAPKVG DSAAWKTRAD AKGGLDGLLA QSLSGLHAMP PKGTCADCSD DELKAAIGKM SGL 1 CDS CDS [Human (Homo sapiens))
SQFRVSPLDR TWNLGETVEL KCQVLLSKPT SGCSV7LFQPR GAAASPTFLL YLSQ1JKPKAA EGLDTQRFSG KRLGDTFVLT LSDFRRENEG YYFCSALSNS IMYFSHFVPV FLPA
Класс Four-helical bundle
Класс Periplastic binding protein
1DBQA Purine repressor (PurR), C-tenninal domain {Escherichia coli)
KSIGLLATSS EAAYFAEIIE AVEKNCFQKG YTLILGMAWN
NLEKQRAYLS MMAQKRVDGL LVMCSEYPEP LLAMLEEYRH
IPMWMDWGE AKADFTDAVI DNAFEGGYMA GRYLIERGHR
TAFNMLLDRI VHKREEPQSI EVHPRLIERR SVADGPFRDY RR
2MHR Myohemerythin Sipiinculan worm (Themiste zostericola))
GWEIPEPYVW DESFRVFYEQ LDEEHKKIFK GIFDCIRDNS APNLATLVKV TTNHFTHEEA MMDAAKYSEV VPHKKMHKDF LEKIGGLSAP VDAK1IVDYCK EWLVKHIKGT DFKYKGKL
Рис. 1.1.2. Представители четырех классов пространственной структуры rio классификации д-ра Сан-Хо Кима из Lawrence Berkley National Laboratory (США).
Один из фундаментальных принципов молекулярной биологии говорит о том, что последовательность аминокислотных остатков полипептидной цепи белка несет в себе всю информацию, необходимую и достаточную для формирования однозначной пространственной структуры [37]. Учитывая это положение, в настоящее время большие усилия прилагаются для разработки методов предсказания третичной структуры молекул на основе известной первичной структуры. Разумеется, абсолютно томно произвести таком прогноз невозможно, остается надежда на то, чтобы правильно «угадать» групп) к которой относится исследуемый белок.
На сегодняшний день биологи выделяют определенные типы (семейства, фолды) известных пространственных структур [82]. В качестве примера, на рис. 1.1.2 представлено схематичное трехмерное изображение белков четырех различных класов и их первичная структура. Положительным результатом процедуры распознавания считается достоверное отнесение белка к одному из таких классов. Налицо задача распознавания образов.
Имея в наличии информацию только о первичной структуре белков, входящих в изучаемые данные, первым шагом представляется попытка получить некоторые количественные характеристики, которые отражали бы существо пространственной классификации. В настоящее время открыто более четырехсот признаков аминокислот, таких как гидрофобность, степень поляризации. размер молекулы и др., однако, прямое использование этих признаков затруднено тем, что различные протеины имеют разную длину, и, следовательно, непосредственное представление первичных структур как векторных «сигналов» их свойств, потребует учета специфики работы с задачами такою типа. Другой простейший подход получения количественных признаков и аминокислотной последовательности заключается в подсчете относительного числа остатков каждой из аминокислот к общей длине последовательности [54]. В таком случае каждый протеин будет представлен точкой в двадцатимерном пространстве. Однако наиболее разумной представляется схема, использующая знания о взаимной близости аминокислотных последовательностей. Существуют априорные объективные данные о близости в химико- биологическом смысле всех 210 пар аминокислот, включая их близости «самих с собой», которые обычно выражаются в виде матрицы соответствия 20x20. Для двух аминокислотных последовательностей пытаются найти такое их взаимное соответствие, чтобы величина «невязки» близостей аминокислот была по возможности минимальной. При этом, для белков различной длины более короткий приходится искусственно «вытягивать» за счет введения в определенные позиции вставок, т.е. разрывать исходную первичную структуру. Результат такой процедуры обычно выражается величиной близости выравниваемых последовательностей в процентах.
Используя какую либо процедуру выравнивания последовательностей, например, Раз1аЗ [83,84] (), можно построить матрицу всех взаимных близостей первичных структур предъявленных белков. Если предположить, что для белков справедлива гипотеза компактности, т.е. что белки, близкие по первичной структуре, имеют, как правило, и сходную пространственную структур}', то представляется естественным использовать для распознавания классов пространственной структуры белков значения их близости к некоторым фиксированным белкам, пространственная структура которых известна.
1.2. Современные методы обучения распознаванию образов в векторных пространствах как теоретическая база беспризнакового распознавания
1.2.1 Общая постановка задачи обучения распознаванию образов
Классические постановки задачи распознавания образов [2,6, II, 13, 17, 24, 41, 43, 44, 76] оперируют с неделимыми объектами, каждый из которых
предполагается целиком принадлежащим к одному из конечного множества классов. Задачей наблюдателя является определить скрытую принадлежность объекта к тому или иному классу, анализируя вектор значений некоторых его признаков, число которых обычно принимается конечным Информацию о связи между значениями признаков объекта и его принадлежностью к определенному классу наблюдатель должен извлечь из обучающей совокупности объектов, для которых известны как значения их признаков, так и классы, либо только значения признаков. В первом случае задача называется задачей обучению распознаванию образов с учителем, а во втором - без учи теля.
Центральными понятиями формальной постановки задачи обучения распознаванию образов являются [12. 43]:
-гипотетическое множество (генеральная совокупность) объектов распознавания (!) е О ;
-индикаторная функция #(со): П ->.//, М - {1,...,/??|, объективно разбивающая множество на т непересекающихся классов и неизвестная наблюдателю;
- пространство наблюдений 9С, в пределах которого некоторая функция х(ы): О —», также неизвестная наблюдателю, ставит в соответствие каждому объекту йеП его образ х(со)е^ \ непосредственно воспринимаемый наблюдателем.
Конечной целью наблюдателя является построение решающего правила (х): СХ- —>. // . которое позволило бы распознавать класс #(со) скрытого
объекта сое О, опираясь на его образ х(со) в пространстве наблюдений Я . и «не слишком часто» ошибаться. При этом доступная наблюдателю информация о функциях и \(оз). составляющих вместе с множествами О. . // и .Я первичную модель источника данных, ограничивается результатами измерений над конечным числом объектов со / = 1,...,Л', составляющих обу- мающую совокупность. В зависимости от того, какие измерения могут быть произведены на объектах обучающей совокупности, различают задачи обучения распознаванию образов с учителем, без учителя, а также промежуточный вариант.
Задача обучения с учителем предполагает, что каждый объект со, в обучающей совокупности представлен номером своего класса =^((0,) и образом в пространстве наблюдений х , = х(со,), то есть обучающая совокупность в целом есть конечное множество пар / = 1,...,Л'' . Такую задачу на
зывают также задачей обучения по классифицированной обучающей совокупности или обучения по прецедентам.
В случае задачи обучения без учителя [22] в обучающей совокупности отсутствуют данные о принадлежности объектов к классам, а обучающая совокупность в целом представляет собой просто конечное множество образов объектов в пространстве наблюдений х;, у = 1,...,Л'. При таком понимании
задачи обучения говорят об обучении по неклассифицированной обучающей совокупности.
Если в обучающей совокупности принадлежность объектов к классам известна для части объектов и неизвестна для остальных, то обучающую совокупность называют частично классифицированной.
В принципе, пространство наблюдений С может иметь любую природу, по. как правило, под наблюдением \(со) понимают вектор с некоторым фиксированным числом компонент \ = (.\",. \\) . котрые называются признаками объекта. Обычно полагаю!, что признаки принимают действительные .г еК либо дискретные значения, в последнем случае обычно х1 е {0,1}. Мы остановимся на первом варианте, полагая в дальнейшем, что пространство наблюдений У является /г-мерным евклидовым пространством ГЧ , или пространством признаков, или признаковым пространством.
Качество решающего правила распознавания содержательно интерпретируется в простейшем случае как «частота» правильных решений о классе объекта, обычно формализуют, наделяя множество объектов О. некоторой а-алгеброй подмножеств и вероятностной мерой, т.е. рассматривая его как вероятностное пространство. Тогда решающее правило следует выбирать из условия минимума вероятности ошибки /;([х(со)]^ #(со)), где о) понимаемся как случайная переменная, принимающая значения из Г2. В более сложном случае качество решающего правила оценивается средним риском ошибки распознавания, под которым понимается математическое ожидание потерь от несовпадения оценки и истинного класса объекта
/[Д(-)]=Я{^[х(со)],я(со)) , (1.2.1)
где - некоторая функция потерь.
Вместе с функциями ,г(оо) и х(со) вероятностная мера на множестве П определяет двухкомпонентный случайный вектор принимающий зна
чения из множества „//хН". Источник данных полностью характеризуется априорными вероятностями появления объекта каждого класса в очередном испытании
к =!
и условными распределениями вероятностей в пространстве признаков для каждого класса объектов. Если предположить, что эти распределения непрерывны в К", го они полностью определяются соответствующими условными плотн остям и ра с п редел е н и я
А)) ,
ф (.V) = Н111 - --— —-. ф (с)с/с = I. к = 1 ш - (1 2..Ч
и»)
где р(/\.(с)) -- мера Лебега с-окрестности Л.(с,) точки х е Р".
Другой исчерпывающей характеристикой источника данных является полное распределение вероятностей в пространстве признаков /(с) вместе с
апостериорными вероятностями классов относительно фиксированных предположений о значениях вектора признаков
" () = /<(со)= Л|х(со) = (I ][/() = 1, к = 1,...,/77. (1.2.4)
Функции яА(,), 4 е часто называют функциями степени достоверности. Такое название отражает интерпретацию значения л:'1 (с), ^еР". как достоверности суждения, что объект с вектором признаков х принадлежит к классу к .
Далее везде будем обозначать аргумент с плотности распределения в признаковом пространстве так же, как и вектор признаков х .
Средний риск ошибки распознавания ./[()], как функционал на множестве решающих правил (х), полностью определяется парой /(х), яА(х) ли
парой с\к, фА (х), к = 1,...,/7?, х е К'1
(1х. (1.2.5
/'(XV* = 1
к=1
Эти выражения, вообще говоря, эквивалентны, так как оба представления вероятностной модели данных могут быть пересчитаны друг в друга:
2.6)
(1.2.7)
(1.2.8)
./(*) = !> УОО, п'(х) =
/ = 1
и наоборот
,/ = |*Чх)/(х>/х, фЧх)=я*(х)./(х)А/
(Г
В то же время, первое из этих выражений более удобно в том смысле, что непосредственно указывает на структуру оптимального (байесовского) решающего правила
<((х)=агоп11пХ?.(<<>,/фА(х).
« к = I
Тем не менее, наблюдателю неизвестны вероятностные характеристики источника данных. Он располагает лишь обучающей совокупностью (^х ), у = 1....,Л; в случае обучения с учителем или х;, / = К...,Л при обучении без учителя, которую в обоих случаях естественно рассматривать как- случайную выборку, состоящую из N независимых реализаций соответствующих случайных векторов, определяемых исходной вероятностной мерой на множестве объектов О. Общая постановка задачи обучения распознаванию образов требует, опираясь на обучающую выборку, найти решающее правило #(х), которое позволило бы в дальнейших экспериментах определять класс вновь предъявляемых объектов с минимальным или, по крайней мере, приемлемым средним риском ошибки ./[/К')]-
В тех случаях, когда невозможно принять какие-либо достаточно простые априорные предположения об аналитической форме условных плотностей
распределения срЛ (х) и, следовательно, функциях достоверности тгА(х), то нет оснований надеяться, что оптимальное решающее правило, минимизирующее средний риск (1.2.1), можно будет представить в конструктивном виде. Тогда обычно ограничивают класс решающих правил (х) некоторым простым параметрическим семейством (х;а). Для случая двух классов, к которому последовательной дихотомией можно свести задачу распознавания при любом числе классов, такие решающие правила удобно строить на основе некоторой дискриминантной функции с/(х;а) в пространстве признаков
<^Л-П2, б/(х;а)< 0, (1-;)
например, линейной с/(х;а)=а 1\ + а{) или полиномиальной с/(х;а) = а' у(х ). где а еК'', у бК'' принадлежат новому (спрямляющему) признаковом) пространству, х е К" по-прежнему принадлежит исходному признаковому пространству
После выбора параметрического класса решающих правил, задача обучения формулируется как задача поиска на основе анализа обучающей выборки вектора параметров а, который обеспечил бы наименьший средний риск ошибки распознавания (1.2.1) в новых экспериментах.
Оптимальное решающее правило (1.2.8) непосредственно опирается на
функции степени достоверности л:А(х), к - 1,...,ш (1.2.4), а не на плотности
распределения фА(х). Как функции образа объекта в пространстве признаков они, как правило, много проще исходных плотностей распределения классов. Это объясняется тем, что согласно (1.2.6) функция степени достоверности
определенного класса лЛ(х) несет информацию о различии плотности срА (х) и плотностей других классов в основном лишь в относительно небольшой "спорной" области признакового пространства, где существенно оыичны от
нуля одновременно фЛ(х) и по крайней мере еще одна из плотностей ф'(х),
I ^ В большей же части пространства признаков значения яд(х) близки к О или 1. В этом случае говорят, что в пространстве признаков выполняется гипотеза «компактности» [13, 14,25]. Так как эта гипотеза представляет собой одно из фундаментальных понятий теории распознавания образов, остановимся на ней несколько подробнее.
Если предположить, что в процессе обучения пространство признаков формируется исходя из задуманной классификации, то можно надеяться, что, задавая пространства признаков, тем самым и задается то свойство, пол. действием которого образы в этом пространстве легко разделяются [16|. Именно эти надежды, по мере развития работ в области распознавания образов, стимулировали появление гипотезы компактности [4], которая гласит: образам соответствую! компактные множества в пространстве признаков Под компактным множеством в простейшем случае принято понимать некие «сгустки» точек в пространстве изображений, предполагая, что между ними сгустками существуют разделяющие их разряжения [25, 26].
Однако эту гипотезу не всегда удавалось подтвердить экспериментально, но, что самое главное, те задачи, в рамках которых гипотеза компактности хорошо выполнялась (рис. 1.2.1, а), все без исключения находили простое решение. И, наоборот, те задачи, для которых гипотеза не подтверждалась (рис. 1.2.1. о), либо совсем не решались, либо решались с большим трудом с привлечением дополнительных приемов. На рис 1.2.1. а компактные образы свободно разделяются прямой линией, а на рис. 1.2.1.6 гипотеза компактности не выполняется, и поэтому приходится строить замысловатую кривую, которая хотя и разделяет образы в обучающей совокупности, но не дает достаточной гарантии успеха на новых точках.
Х| X
а 6
Рис. 1.2.1. Компактные (а) и перемешанные (б) множества.
Существует огромное количество различных методов обучения распознаванию образов. В частности, один из них, простейший и широко известный (линейный дискриминатор Фишера (ЛДФ)) [42, 61] предполагает, что выборки пары классы представлены нормальными распределениями с одинаковыми ковариационными матрицами.
8~'( х"' — х,2)) (1.2.10)
" + х(;
х -
х =
в которой 8 представляет собой оценку максимума правдоподобия ковариационной матрицы размером пхп, х еЯ" представляет собой п-мерный вектор. который необходимо классифицировать, х1" е!Ч" - вектор среднего по
выборке /-го класса. Очевидно, что линейная дискриминантная функция Фишера имеет вид
/,(х) = с/(х;а,а0) = а?х+^0, (1.2.1 Г)
где а = 8"'(х(1) -х<2)), а, = (х(1) + х(2))г 8"'(х(1) - х(2)), и принимает положительные значения для объектов первого класса и отрицательные для второго.
Существенную особенность в постановку задачи обучения вносит предположение, что условны.е плотности распределений фА (х), к = целиком сосредоточены в некоторых областях в признаковом пространстве, таких, что эти области и их выпуклые оболочки не пересекаются между собой. Тогда для каждой пары классов заведомо существует линейная дискриминантная функция, позволяющая безошибочно классифицировать объекты этих двух классов, что. в свою очередь, позволяет на основе последовательной дихотомии построить безошибочное решающее правило распознавания для любого числа классов. Такая дискриминантная функция определяется лишь формой непересекающихся областей признакового пространства с тех сторон, которыми эти области «обращены друг к другу», и не зависит от конкретного вида заполняющих их распределений вероятностей. Именно решающие правила такого вида будут использоваться в работе. Два следующих раздела дают обзор метода построения так называемой оптимальной разделяющей гиперплоскости.
1.2.2. Концепция оптимальной разделяющей гиперплоскости
По своей идее решающее правило распознавания в виде оптимальной разделяющей гиперплоскости призвано как можно лучше отделять друг от друга объекты пары классов в признаковом пространстве. Пусть обучающая совокупность содержит N объектов двух классов, представленных векторами их
действительнозначных признаков х( еР" и индексами классов
/ = . Поскольку, единственное, что известно о границах областей клас
сов в пространстве признаков, полностью содержится в обучающей выборке, то представляется естественным выбрать вектор а е К" и скаляр Ь так, чтобы
Такая пара (а, Ь) существует, если подвыборки первого и второго классов в обучающей совокупности линейно разделимы, т.е. их выпуклые оболочки не пересекаются, причем в этом случае существует множество таких пар. Оптимальной принято называть ту, которая определяет гиперплоскость наиболее удаленную от краев подвыборок.
В случае пересекающихся (линейно неразделимых) подвыборок первого и второго классов оптимальная разделяющая гиперплоскость будет определяться такой парой (а, Ь), которая обеспечит наименьшее «наложение» проекций выборок на вектор а .
Рис. 1.2.2. Возможные разделяющие гиперплоскости, оптимальной считается гиперплоскость 3
1.2.3. Обучение на основе понятия опорных векторов
В этом разделе будет дан обзор чрезвычайно популярного последние несколько лет метода обучения на основе построения линейного решающего
правила распознавания в конечномерном пространстве признаков, названного его создателем (В.Н. Вапник) методом опорных векторов. Важнейшей особенностью метода является достаточность для построения линейного решающего правила знания лишь скалярных произведений векторов признаков объектов. Фактически метод не нуждается в признаках, измеренных на объектах, и именно эта его особенность будет использована в дальнейшем в основной части работы для построения беспризнаковых алгоритмов обучения и распознавания.
Первая форма задачи построения оптимальной разделяющей гиперплоскости (общая для разделимых и неразделимых подвыборок двух классов объектов). Предположим, что объекты классов 1 и -1 линейно разделимы. Тогда существует гиперплоскость а7 х + h = , такая, что
а7 х у + />>+, при gj = 1, а7 х j + b < при = -1, (1.2.10)
./ = !,..„Л/,
где ^ > 0 .
Оптимальной называется такая гиперплоскость, для которой зазор с, является наибольшим среди всех гиперплоскостей с направляющими векторами единичной нормы:
t —> max при ограничениях (1.2.10) и а' а = I или, в более конструктивном виде,
J (а) = min а' х . - max а' х , —» шах при ограничении а7а = 1. (1.2.1 Г)
Предположим теперь, что объекты классов 1 и -I линейно неразделимы. В этом случае для любой гиперплоскости а' х + h - 0 существуют точки класса 1. в которых а' х . + b < 0, и точки класса -1, в которых а' х + b > 0 . так что
не существует гиперплоскости, удовлетворяющей условиям (1.2.10) с каким бы то ни было положительным зазором Какую бы гиперплоскость мы ни
выбрали, условия (1.2.10) будут выполняться лишь для некоторой величины
Естественно оптимальной называть такую гиперплоскость, которая обеспечивает выполнение таких неравенств с наименьшим по абсолютной величине «обратным» зазором, т.е. с наибольшим значением только это наибольшее значение уже не сможет стать положительным. Таким образом, задача поиска оптимальной разделяющей гиперплоскости по-прежнему формально выражается условием (1.2.1 Г).
Задача (1.2.11) представляет собой задачу минимизации кусочно- линейной функции ./(а) на сфере а'а=1. Хотя; сама целевая функция выпукла, область поиска выпуклой не является, поэтому задача неудобна для численного решения.
Вторая форма задачи построения оптимальной разделяющей гиперплоскости (разная для разделимых и неразделимых объектов двух классов). Пусть объекты классов 1 и -1 линейно разделимы. Очевидно, что изменением масштаба оси а всегда можно сделать правые части неравенств (1.2.10) равными, соответственно, 1 и -1. Для этого достаточно разделить оба неравенства на с;
1 У 1 , , 7 1 ,
-ах +-Ь> 1. -ах +~Ь<-1
' I ' 7
После деления на новый вектор а будет в Е, раз короче прежнего, норма которого была равна I. Чем больше С, т.е. чем лучше была прежняя гиперплоскость, тем меньше будет норма нового вектора а. Таким образом, задача построения оптимальной разделяющей гиперплоскости для линейно разделимых объектов классов 1 и -1 принимает следующий вид:
а'а —» шп при ограничениях (а' х + />) > I. / = 1.....Л' (1.2.14)
Это задача минимизации квадратичной функции при линейных ограничениях типа неравенств, т.е. классическая задача квадратичного программирования. Минимальное значение 1 с;2 = а7а указывает максимальное возможную величину зазора между гиперплоскостью и векторами первого и второго классов, безошибочно разделяемыми этой гиперплоскостью, если вернуться к исходным параметрам а = а и Ь = ^Ь, удовлетворяющим условию
а7 а = 1.
При неразделимых совокупностях объектов классов 1 и -1 множество, определяемое ограничениями (1.2.13), будет пустым, т.е. задача (1.2.14) не будет иметь решения. В этом случае неравенства (1.2.10) могут быть выполнены, как мы уже говорили, только при отрицательном значении Если по- прежнему считать положительной величиной, то их надо заменить неравенствами
а' х; + Ь > -Е, при = 1 и а' х, + Ь < при = -1, у = 1,...Л'. (1.2.15)
Гиперплоскость ' гем лучше, чем меньше значение с. Разделив оба неравенства на и изменив тем самым масштаб оси а. всегда можно сделать правые части неравенств (1.2.1 5) равными, соответственно. 1 и I
1 7 / , 1 / 1 , ,
-а х; + -Л >-1. -а х,+-/)<1,
С ' с, с с,
а х + Ь > - \ при ^, = 1 и а' х + Ь < 1 при ^ Эти два неравенства эквивалентны одному неравенству
(1.2 16)
а <-> 1
g/a'x,+/>)>-!, ./=!,..., Л'.
Чем меньше значение и, соответственно, больше значение а. тем лучше гиперплоскость, поэтому задача построения оптимальной разделяющей гиперплоскости для линейно неразделимых объектов классов -1 и 1 может быть записана в виде:
а а —> max при ограничениях х (а' х .+/?)> - I, у = 1 Д'
Максимальное значение 1 Д = а а дает минимальную величин)' ocraiоч-
ного дефекта Д с которым гиперплоскость с исходными параметрами а = са и /? = ./), удовлетворяющими условию а а = 1. разделяет векторы первого и второго классов, не разделимые никакой гиперплоскостью без ошибки.
(1.2.19)
при ограничениях
Третья форма задачи построения оптимальной разделяющей гиперплоскости (разная для разделимых и неразделимых объектов двух классов). Пусть объекты двух классов линейно разделимы. Задача (1.2.14) есть задача минимизации квадратичной функции при линейных ограничениях типа неравенств, т е классическая задача квадратичного программирования. Ей соответствуем функция Лагранжа
(1.2.18)
где для удобства дальнейших выкладок принят коэффициент 1 2 перед целевой функцией. X >0, у = 1,...,Д/ - неотрицательные множители Лагранжа. Решением задачи является седловая точка функции Лагранжа.
/ДаДД,,...Д,- ) —» min по а Д,
/лаД / . / s > max по л ..../.
X, >0, / -= 1 V.
Первое из этих условий (1.2.19) дает
= 0. —
I- !а 4 - 1
= 0.
V а а -
дЬ 2 4? 1 ' ;
откуда получим
(1.2.22)
(1.2.23)
Хл.х. =0
Подстановка (1.2.22) во второе условие (1.2.20) превращает его в целевую функцию, вообще говоря, относительно множителей Лагранжа Я,,...,/и порога Ь
2 /-'1 к-Л I ] к ] ^ , 1 ) , 1
-I Л.:
однако в силу равенства (1.2.23) активными аргументами являются только множители Лагранжа. Таким образом, мы приходим к следующей формулировке задачи построения оптимальной разделяющей гиперплоскости в виде задачи квадратичного программирования, называемой в литературе двойственной по Вульфу [62] или по Лагранжу [5] по отношению к задаче (1.2.14):
(1.2.24
2>
./V
0-,/
^ = о, л
И/(А.),...,лу) - двойственная функция Лагранжа - является вогнутой, следовательно, всякий ее локальный максимум является и глобальным [5].
После того, как множители Лагранжа найдены, направляющий вектор оптимальной разделяющей гиперплоскости определяется по формуле (1.2.22) как линейная комбинация векторов обучающей совокупности. Те векторы, для которых А.,^0, т.е. /.,>() с учетом ограничения (1.2.21), называются
опорными векторами оптимальной разделяющей гиперплоскости.
Для определения значения порога Ь используем тот факт, что в оптимальной точке из совокупности ограничений ^ (а7х; + Ь) > 1 (1.2.14) активными, т.е. превращающимися в равенства #.(а'х; + /)) = 1, являются те. для которых множители Лагранжа положительны \,>0. Для этих ограничений имеем
)^,(а7 х . + Ь) = АДа? \ / + Ь) = (1.2.25 )
Но эти же равенства выполняются и для всех остальных / в силу того, что для них А,, = 0. Сложив все эти равенства, получим
л 4 л ( д \
^ГАДа'х = =0,т.е. Ь- 0, откуда следует
1=1 ,=I /=1 у.,=1
ХА'а'х /
/.) — . (1.2.26)
Х\
/-1
Заметим, что мы по-прежнему решаем задачу (1.2.14), и значение 1 ,2 = аа для направляющего вектора (1.2.22), вычисленного при оптимальных значениях весов, дает максимальную величину остаточного зазора, с которым гиперплоскость разделяет точки первого и второго классов. С учетом (1.2.23) эта величина выражается непосредственно через значения весов
!/- У х х )>. А .
К тому же, аналогично (1.2.25), л.^Да'х +Ь) = Х/, что при суммировании по всем / дает
( \
-] =1 =1 у ;=1
<г , Л
откуда с учетом (1.2.22) и ограничения в виде равенства в (1.2.24) получим
, = 1 /=1 V А" =! / ; = 1 к=\
Таким образом, шах Ж(л,,...Дч) = 1 2ц2 , и при любых других значениях
'ч '-л
весов выполняется неравенство ИЭл,,...Ду) < .
Пусть в > 0 - некоторое достаточно малое число, такое, что множества точек первого и второго класса можно считать линейно неразделимыми, если никакая гиперплоскость не может обеспечить величину остаточного зазора, большую с. Если в процессе решения задачи квадратичного программирования (1.2.24) наступит ситуация 14/(Х],...,Хх)> 1 2с2 , то точки первого и'второго класса линейно неразделимы, и процесс должен быть остановлен.
Рассмотрим теперь третью постановку задачи для случая линейной неразделимости объектов классов 1 и -1. Следует отметить тот факт, что для задачи (1.2.17) система ограничений образует замкнутую область в пространстве варьируемых параметров, а критерий представляет собой максимизацию выпуклой квадратичной целевой функции. Это приводит к наличию нескольких локальных экстремумов, и как следствие - трудности в построении эффективной процедуры направляющего вектора оптимальной разделяющей гиперплоскости. Этот факт наглядно демонстрируется на примере, приведенном на рис. 1.2.3.
Это обстоятельство делает запись задачи (1.2.17) в виде, эквивалентном задаче (1.2.18), неудобной в вычислительном отношении. В работе [52] была предложена отличная схема, суть которой заключается в следующем.
О-О О О —ОСЮ-#—О
чию нескольких локальных экстремумов.
Вернемся к второй форме задачи построения оптимальной разделяющей гиперплоскости. Как очевидно то, что для случая линейно разделимых классов изменением масштаба оси а, всегда можно сделать правые части неравенств (1.2.10) равными соответственно 1 и -1, так очевидно и то. что смещением объектов 1-го класса в положительном направлении вектора а и -1- го класса в отрицательном направлении удастся линейно неразделимые классы представить как разделимые. Предлагается применить такое «центробежное» преобразование по-разному для различных объектов выборки, а именно, для объектов, попавших в область чужого класса, необходимо ощутимо отодвинуть их в «свою» сторону, в то время как объекты из задних областей вообще не нуждаются в подобном смещении. Понятно преимущество такого подхода (рис. 1.2.4, 6') по сравнению с добавлением одинаковой константы ко всем объектам выборки (рис. 1.2.4. б).
у''
\ V.
Рис. 1.2.4. Линейно неразделимая выборка (а). Смещение всех объектов выборки (б). Смещение объектов, мешающих линейной разделимости выборки («).
Он позволяет оценить число ошибок в обучающей выборке
/V', + АС,
где /7, и - минимальное число объектов в классах 1 и -1, соответственно, сместив которые, удастся добиться линейной разделимости классов.
Таким образом, для неразделимого случая перепишем неравенства (1.2.12) в виде
а' х ,+/;>+1 - 8, при g/ = 1 при ^ = -1,
где 5 > 0, / = 1,...,А/ - неотрицательные константы, на которые необходимо
сместить объекты обучающей выборки, чтобы добиться линейной разделимости. В более компактной форме это может быть записано следующим образом
-/(а7х/+/>)>+1-^. (1.2.27)
Тогда ошибка распознавания на обучающей выборке может быть представлена в следующем виде
и. «„,*>«
/О о о <-4,0 0-0
о С) , \Го0 о
о" :;о о о
а б
1* = -^ , где в($) = \
N 0, сс:ш 6 = О
Задача заключается в выборе 6,, / = 1,...,Л; таким образом, чтобы >гшп. В таком случае В.Н. Вапник предлагает представить общий критерий поиска в одном из следующих видов:
(1.2.28а)
(1.2.28Ы
—(а7а + ) -» гшп ,
— |а'а + С]Г(6.)2] —> тт
2.28с)
|У а + ('(^5. )А ] -> тт , к > 1,
где С>0 - положительная константа - параметр пользователя, при ограничениях
(а7 х / + /;) > +1 - 5 8 >0. / = 1....,Л'.
Таким образом, получена задача минимизации квадратичной функции при линейных ограничениях типа неравенств. Осталось получить двойственную формулировку этой задачи.
Ограничимся рассмотрением задачи обучения в виде (1.2.28а). Функция Лагранжа, соответствующая такой задаче, имеет вид
1 С л
/.(а,/)Д|,...Дл ,51,...,8л.,р|,...,р,) = -а/а+ ^ ]Г8. -
(1.2.29)
где X >0, > 0, / = 1,...,Л' - неотрицательные множители Лагранжа.
Решением задачи является седловая точка функции Лагранжа:
,51,...,8)-> шит по а, Л, 8,,...,8, , (1.2.30)
/Д а,/),л,,...,/., .8,,...,8, д!,,...,^. ) шах по А.,,..А,., р,,...,|л, . (1.2.3 I ) при ограничениях
Первое из этих условий дает
V,/Да.ЛЛ,.. .Л, ,8,,...,5Л.,ц,,...,ц..) = 0
сУДа./)Д,,...,А, ,8,,...,8, .п.... ,п ) дЬ
dL{а,/.>.А,,... Дл,,5,....А ...и )
= 0. j = \,...,N
откуда получим
(1.2.32)
\ = У X у- х , ./=1
( 1.2.33
A,+f.i,=-, ./ = 1,..„Л/.
Отметим что. так как А >0,н >0 и X + и =—, то 0
с:
./ / ./ г / т
Подстановка (1.2.32) в условие (1.2.31) превращает его в целевую функ
И^Л >v,A. А-М, Я Л;
- / I /. 1
V / .V Л v
/ 1 А- 1 VJ ./'=' -/ 1 " '
однако в силу равенств (1.2.33) и (1.2.34) активными аргументами являются
только множители Лагранжа Xt >0, / = 1,...,Д/ .
Таким образом, мы приходим к следующей формулировке задачи построения оптимальной разделяющей гиперплоскости в виде задачи квадрат и ч н о го п р о гр а м м и ро в а н и я
(1.2.34)
1 v -v
ИДли...Д,) = JA --ХХА.-АхА-Л, -> max,
,35а)
V/. -о. о-.,. -о. / 1 V.
По-прежнему значения А. > 0 указывают опорные элементы обучающей
выоорки, определяющие параметры оптимальной разделяющей гиперплоско
сти, вычисляемые в данном случае по формуле (1.2.32). Максимальное значение критерия (1.2.35а) шах И/(л1,...,лу) =-1/2,2 укажет минимальную ве-
>-. Аллицину дефицита, с которым точки первого и второго классов могут быть разделены гиперплоскостью, а направляющий вектор разделяющей гиперп-
лоскости определяется как а = ,х. , то есть так же как и для случая ли
нейно разделимых выборок. Константа же Ь в этом случае будет другой. Определим ее
Смещения б, равны нулю тогда и только тогда, кода соответствующие им суть множителей Лагранжа ц,>0, то есть, когда X <С/2, у = 1,...,Л/Г. В
других терминах: 8; > О тогда и только тогда, когда Х1 .
Для положительных А, выполняется условие ;(ау х; + 6) = 1 - 8;.. Если
О < А ( < ~ О', то 8у=0, и, следовательно, g(а хJ + Ь) = \ . Учитывая, тот
факт что х2 = 1, перепишем последнее уравнение в виде АДа'х, + Ь) = Х.^ . откуда следует ЕлДа' х, +|/;)= Выразив отсюда Ь получим:
I 1 .
/.()
'2 '2
/=1
Для задачи (1.2.285) аналогичным образом можно получить соответствующую ей двойственную задачу вида
Л'
тах,
(1.2.35Ь)
V/. и =0, Д >0,7 = 1,...,Л'.
7 = 1
Или введя новые обозначения О = {(ЯД^х ,хА.)], 1 = (1---1)' и А — (а, )
виде
|/(Л) 1 Л -л' (О + - 1)Л тах,
^А.» =0: А > 0, / = 1,...,А/.
Направляющий вектор разделяющей гиперплоскости будет определяться
следующим ооразом:
/=|
л а х +
7 / / . ,=1 ^ ;=1
Ь =
V .V , ] .V
/=1 к=1
I»-, 2Х
/=1 7=1
Для задачи выпуклого программирования (1.2.28с) получим двойствен
ную задачу
к к-1
тах.
, ----1
У>. х Л). 0< А; <(/,7 = А- 1.
/ = 1
С к
а 8
где произведена замен
. В частности, при к = 2 ,
.ТОССКЙ?" ' "
Л- Л
—» шах.
,(1.2.35с)
Направляющий вектор разделяющей гиперплоскости, определяемый таким набором опорных векторов, будет иметь вид
ЕХ 2 X ,
X А а х - с! X Хдх 4 х (1 X
/: 0
2>,
у:0
у: 0
1.2.4. Проблема малой обучающей выборки
/=1 ^
./:а, =
Очень часто при решении задач распознавания образов приходится сталкиваться с проблемой так называемых коротких выборок. Речь идет о случаях, когда число признаков выбранных для описания выборки сравнимо или даже больше числа объектов в выборке. Обычно, в таких задачах без труда удается найти решающее правило, хорошо разделяющее обучающую выборку, но экстраполяционные свойства такого решения бывают неудовлетворительными. Зачастую специалистам, впервые применяющим методы теории распознавания, непонятна сама проблема. Ведь с точки зрения теории информации лишних признаков быть не может. Дело в том, что решающее правило, например линейное, фактически представляет собой некоторую гиперповерхность в многомерном пространстве, положение которой полностью определяется объектами (точками) обучающей выборки в этом пространстве. Чем больше размерность вектора признаков, тем больше «разряжено» это пространство, тем больше свободы у разделяющей гиперповерхности. Удаление хотя бы одной точки из обучающей выборки, может привести к суще
ственному изменению разделяющей границы. Если уместна такая аналогия, то при удалении одной точки, остальные не смогут «поддержать» «проваливающуюся» гиперплоскость - они ведь как бы растянуты по другим «фронтам» (признакам).
Эксперименты, проводимые в ходе верификации предлагаемых в работе методов, показали наличие именно этой проблемы. Поэтому ниже приведен обзор методов распознавания в пространствах высокой размерности []. 19. 27. 35, 55, 63, 64, 65, 66, 68. 69, 71, 74, 86, 87, 89, 94, 95, 96, 100, 101, 108].
Фактически сложилось два направления - это сокращение размерности пространства признаков и наложение специальных ограничений на решающее правило, призванных уменьшить его вариабельность.
1.2.5. Селекция признаков (сокращение признакового пространства)
Методом улучшения экстраполирующих свойств является метод сокращения признакового пространства. Эта задача является не только проблемой теории распознавания образов, но и вообще проблемой обработки данных. Следует отметить тот факт, что интерес к этой процедуре сохраняется и в последнее время, так как появление нового поколения быстродействующих ЭВМ, и, как следствие, относительная независимость исследователей от вычислительной сложности не явилась эволюционным решением этой проблемы. Дело в том, что помимо (а) сокращения объема вычислений, отбор признаков, в большей или меньшей степени направлен и на (б) улучшение классификации, (в) сокращение стоимости сбора данных, (г) сжатие объема данных (д) возможность визуализации многомерных данных [I, 15]. Приложения, требующие применения методов отбора признаков, встречаются в следующих задачах:
(1) Приложения, в которых объединены данные от большого числа датчиков
Объединение многомерных моделей, когда все параметры различных моделей могут быть использованы для классификации.
Приложения, основанные на получении (извлечении) данных, где целью является определение скрытых зависимостей между признаками.
Таким образом, очевидно, что выбор признаков играет в распознавании важную роль. Выбор адекватного множества признаков, учитывающий трудности, которые связаны с реализацией процессов выделения или выбора признаков и обеспечивающий в то же время необходимое качество классификации, представляет собой одну из наиболее трудных задач построения распознающих систем. Для того чтобы облегчить анализ этой задачи в [41] предлагается разделить признаки на три категории: (1) «физические», (2) структурные и (3) математические.
Физические и структурные признаки обычно используются людьми при распознавании образов, поскольку такие признаки легко обнаружить на ощупь, визуально, с помощью других органов чувств. Поскольку органы чувств обучены распознаванию физических и структурных признаков, человек, естественно, пользуется в основном такими признаками при классификации и распознавании. В случае же построения вычислительной системы распознавания образов эффективность таких признаков с точки зрения организации процесса распознавания может существенно снижаться, так как, вообще говоря, в большинстве практических ситуаций довольно сложно имитировать возможности органов чувств человека. С другой стороны, можно создать систему, обеспечивающую выделение математических признаков образов, что может оказаться затруднительным для человека при отсутствии «механической» помощи. Примерами признаков этого типа являются статистические средние, коэффициенты корреляций, характеристические числа и собственные векторы ковариационных матриц, и прочие инвариан тные свойства объектов.
Предварительная обработка образов обычно включает решение двух основных задач - преобразование кластеризации и выбор наиболее информативных признаков.
Как было сказано ранее, основной задачей распознавания образов является построение решающих функций, представляющих некоторые классы. Эти функции должны обеспечивать разделение пространства признаков на области. каждая из которых содержит, по возможности, точки, представляющие образы только одного из рассматриваемых классов. Данное положение приводит к идее преобразований кластеризации [26, 38, 41, 46], реализуемого в пространстве измерений, для того чтобы обеспечить группировку точек, представляющих выборочные образы одного класса. В результате такого преобразования максимизируется расстояние между множествами и минимизируются внутримножественные расстояния.
Выбор наиболее эффективных признаков, либо получение таких признаков каким либо преобразованием (например, Карунена-Лоэва, Сэммона) [41, 65, 74] позволяет снизить размерность вектора измерений. Выбор признаков можно осуществлять вне связи с качеством схемы классификации. Оптимальный выбор признаков при этом определяется максимизацией или минимизацией некоторого критерия. Такой подход принято считать выбором признаков без учета ограничений. Другой подход связывает выбор признаков с качеством классификации, причем обычно эта связь выражается в терминах вероятности правильного распознавания.
1.2.6. Регуляризация классификаторов
Другой способ надежного обучения в условиях малых выборок заключается в наложении специальных ограничений на решающее правило с целью повышения его экстраполирующих свойств. Так. например, в случае разделимых выборок первого и второго классов, всевозможные направления вектора-нормали разделяющей гиперплоскости описывают в пространстве при
знаков конус. Процедура обучения заключается в выборе некоторого оптимального направления, обусловленного обучающей выборкой и критерием обучения. Учет априорной информации о характере прикладной задачи, т е о природе данных, позволяет существенно сузить конус возможных направляющих векторов. Может оказаться полезным большее предпочтение на этапе обучения отдавать именно априорной информации, нежели информации, содержащейся в обучающей выборке.
Стандартные классические статистические методы испопользуют ковариационную матриц)'. Например, обратную ковариационную матрицу содержит линейная дискриминангная функция Фишера (1.2.10)
Учет априорной информации о характере связи между признаками достигается выбором той или иной модели ковариационной матрицы. В [35] рассмотрено больше десяти вариантов структуризации ковариационной матрицы. Иногда подобные методы стабилизации не только не помогают, но и более того, даже увеличивают ошибку классификации. Это четко связано со стабильностью классификаторов на специфических данных.
Прямое вычисление обратной ковариационной матрицы на этапе обучения невозможно в случае, когда число признаков п превышает число объектов N [85]. В пространстве большой размерности п при уменьшении А' ожидаемая вероятность ошибок классификаций сильно возрастает [88]. Для преодоления этих проблем существует несколько различных методов.
Одной из простейших модификаций процедуры ЛДФ является классификатор ближайших средних, получающийся из (1.2.10) присвоением 8 - I. где I - единичная матрица
(х<1)-х12)
х —- (х + х ) 1
^.лДх,
Следовательно, классификатор ближайших средних есть гиперплоскость между средними по классам, и, таким образом, строит оптимальный линейный классификатор для классов с одинаковыми нормальными сферическими
распределениями. Преимущество этого классификатора заключается в относительной нечувствительности к размеру выборки. Однако такой классификатор не учитывает разницы между дисперсиями и ковариациями.
Хорошо известный метод обращения вырожденной ковариационной матрицы, использованный при построении стандартного ЛДФ (1.3.1), заключается в добавлении некоторых постоянных значений к диагональным элементам, оцениваемой ковариационной матрицы
СЛ=С + Х1, (1.3.2)
и I - есть единичная матрица размером пхп, и А. - параметр регуляризации.
Новая оценка: Си называется ридж-оценкой ковариационной матрицы, термин, который был заимствован из регрессионного анализа. Этот подход называется регуляризованным дискриминантным анализом. Модификация (1.2.10) дает ридж или регуляризованную дискриминантную функцию (РЛДФ)
а,,.(х)-[д--{(х(|)-х(2)Ж8 + ЛГ,(х(,)-х(2') (1.3.3)
Очевидно, что при А.-»со, теряются значения дисперсий. Одновременно обобщенная ошибка может быть существенным образом уменьшена. Малые значения параметра регуляризации А. могут быть полезны для стабилизации решения. Очень малые значения А. могут быть не достаточно эффективны
Другая модификация линейной дискриминантной функции Фишера (1.2.10) позволяет преодолеть обращение вырожденной ковариационной матрицы для выборок малого размера N<4. Это так называемый псевдолинейный дискриминатор Фишера (ПЛДФ) [55]. С использованием расширенного вектора, непосредственное решение для (1.2.11) получается в виде
^/,(х) = (а,б/ц)/(х,1) = (х,1)(Х,1Г1, (1.3.4)
где (х, 1) - расширенный вектор, который необходимо классифицировать и (Х,1) - расширенная матрица данных. Процедура обращения матрицы (\,1)~' представляет собой псевдообращение Мура-Пенроуза [44], которое
дает минимальное нормированное решение. Перед обращением данные необходимо сдвинуть таким образом, чтобы средние значения по признакам были равны нулю.
Для значений Л' >п ПЛДФ, максимизируя расстояния между выборками разных классов, идентичен ЛДФ (1.3.1). Однако для значений N <п ПЛДФ находит линейное подпространство, где располагаются все данные, и в этом подпространстве оцениваются средние значения и ковариационные матрицы и строит линейное разделяющее правило, которое ортогонально этому подпространству во всех других направлениях, в которых нет заданных объектов.
Другим методом стабилизации является бэггинг [50], основанный на бут- стрэпе [60]. Предлагается строить бэггинг-классификатор посредством усреднения параметров линейного классификатора, построенного на нескольких повторениях процедуры бутстрэпа. Усреднение этих версий как раз и дает бэггинг-классификатор. В работе [50] показано, что бэггинг может уменьшить ошибку линейной регрессии и классификации. Отмечается, что такой метод полезен только для нестабильных процедур. Для стабильных методов он может даже ухудшить результат работы классификатора.
Обычно для выбора приемлемого параметра регуляризации используется два метода: скользящий контроль и бутстрэп [60, 75].
1.3. Принципы организации обучения беспризнаковому распознаванию образов в гильбертовом пространстве объектов
1.3.1. Гильбертово пространство объектов распознавания и параметрическое семейство линейных решающих правил
Центральная идея беспризнакового подхода к распознаванию образов, развиваемого в дальнейшем в данной диссертации, целиком опирается на тот
факт, что в методе опорных векторов В Н. Вапника, разработанном первоначально для обучения в пространстве конечного числа признаков и изложенном выше в разделах 1.2.2 и 1 2.3, при решении задач обучения и распознавания используются лишь скалярные произведения векторов признаков объектов, но не сами векторы. Поиск параметров а е R" и b eR оптимального линейного правила распознавания с/(\: я.h) = а7 х +h есгь задача квадратичного программирования, решение которой сводится к поиску множителей Лагранжа при элементах обучающей выборки A., >0,...,AV >0 как решения двойственной задачи (1.2.35а) и вычислению искомых параметров по простым формулам (1.2.32) и (1.2.36а). При этом во всех выражениях фигурируют лишь скалярные попарные произведения векторов обучающей выборки х^., j\k = ],...,N , а не сами векторы. Далее, с учетом (1.2.32) полученное решающее правило распознавания имеет вид
б/(х; a,h) = а' \ + h = JA \ +/>,
в который опять же входят только скалярные произведения вектора признаков вновь предъявляемого объекта х е R" с векторами обучающей совокупности.
Таким образом, метод опорных векторов не использует конечномерности векторов признаков объектов. Существенно лишь то, что объекты распознавания представлены в некотором линейном пространстве, в котором определена операция вычисления скалярного произведения для любых двух объектов. Основная идея данного исследования заключается в том. что в силу этого обстоятельства вообще нет нужды вводить понятия признаков объектов, достаточно лишь предположить, что объекты распознавания могут рассматриваться как элементы некоторого линейного пространства, размерность которого не играет роли, причем для всех пар объектов определена числовая характеристика их сходства, обладающая свойствами скалярного произведения в этом линейном пространстве.
Линейные пространства, наделенные операцией скалярного произведения, принято называть гильбертовыми пространствами, поэтому в дальнейшем мы будем называть предлагаемую концепцию распознавания образов беспризнаковым распознаванием в гильбертовом пространстве.
Будем рассматривать всякий объект со как элемент линейного пространства Г2 с определенной на нем операцией скалярного произведения (со'.со"), т.е. как элемент гильбертова пространства. Соответственно, квадратный корень из скалярного произведения элемента на самого себя является его нормой || аз||= (со,со)1/2. Весь формализм введения такого пространства будет рассмотрен в основной части работы.
Пусть гильбертово пространство П объективно разбито на два класса С2, 1Ю_, = 2, = 0- Задача распознавания сводится к поиску такой
не слишком сложной дискриминантной функции /(со), которая принимала бы, по возможности, положительные значения на объектах первого класса и отрицательные значения на объектах второго класса. Поскольку гильбертово пространство является линейным, в нем определено понятие линейной функции, поэтому вполне уместно искать дискриминантную функцию в семействе линейных функций с/(со; 9,/;) = (9,со) + Ь, каждая из которых определяется двумя параметрами - элементом гильбертова пространства играющим
роль направляющего элемента соответствующей разделяющей гиперплоскости, и числом Ь еИ, определяющим ее смещение.
Мы не предполагаем, что все элементы гильбертова О пространства реально существуют как потенциальные объекты распознавания. Мы сбудем полагать. что реально существующие объекты образуют подмножество 2 точек в 2, быть может, изолированных, в то время как остальные элементы представляют собой ни что иное, как продукт нашего воображения. Именно такое расширение множества П до О. позволяет нам говорить о «суммах» реально существующих объектов и их «произведениях» с действительными коэффициентами.
Пусть задана классифицированная обучающая выборка со., / = N состоящая из N объектов, каждый из которых отнесен к одному из двух классов. Будем полагать, что индекс класса принимает значения =1 и
=-1, на объектах, соответственно, первого и второго классов. Тогда задачу обучения распознаванию образов будем понимать как задачу поиска такого элемента & из гильбертова пространства О. и скаляра Ь. чтобы по возможности выполнялись неравенства (Э,со; ) + /:>> 0 для \ п (Э,со )+ 6 < О
для # =-1 . Перенося в гильбертово пространство концепцию оптимальной
