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

На правах рукописи

ТАТАРЧУК Александр Игоревич

БАЙЕСОВСКИЕ МЕТОДЫ ОПОРНЫХ ВЕКТОРОВ ДЛЯ ОБУЧЕНИЯ РАСПОЗНАВАНИЮ ОБРАЗОВ С УПРАВЛЯЕМОЙ СЕЛЕКТИВНОСТЬЮ ОТБОРА ПРИЗНАКОВ

Специальность 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва, 2014

г У МАП 2014

005549432

Работа выполнена в Федеральном государственном бюджетном учреждении науки «Вычислительный центр им. A.A. Дородницына Российской академии наук».

Научный руководитель:

доктор технических наук, профессор Вадим Вячеславович Моттль

Официальные оппоненты:

Выогин Владимир Вячеславович, доктор физико-математических наук, профессор (Институт проблем передачи информации им. А. А. Харкевича РАН, заведующий лабораторией №1 им. М. С. Пинскера «Теория передачи информации и управления»)

Червоненкис Алексей Яковлевич, кандидат физико-математических наук, старший научный сотрудник (Федеральное государственное бюджетное учреждение науки «Институт проблем управления имени В.А. Трапезникова Российской академии наук», ведущий научный сотрудник)

Ведущая организация: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский государственный университет им. М.В. Ломоносова».

Защита диссертации состоится «19» июня 2014 г. в 13 ч. на заседании диссертационного совета Д 002.017.02 в ВЦ РАН по адресу 119991 Москва, ГСП-1, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке и на официальном сайте (http://www.ccas.ru/) ВЦ РАН.

Автореферат разослан 2014 г.

Ученый секретарь

диссертационного совета Д 002.017.02 доктор физико-математических наук

/ Л

,/■ у

Рязанов В.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность. В диссертации исследуется и развивается наиболее популярный в современной литературе линейный подход к обучению распознаванию двух классов объектов реального мира coeQ, основанный на двух предположениях. По-первых, предполагается, что всякий объект воспринимается компьютером через вектор его числовых признаков как точка в линейном пространстве х(со) е R". размерность которого определяется числом признаков п. Во-вторых, предполагается, что для суждения о принадлежности объекта к одному из двух классов у = +1 достаточно вычислить значение линейной решающей функции (decision function) d(x \ a,b) = aTx + b: К" —> К, знак которой непосредственно укажет класс объекта aTx + b^0. Очевидно, что линейная функция d(x \ а,Ь) определяет дискриминантную гиперплоскость в R". а решение о классе объекта определяется тем, по какую сторону от нее окажется вектор признаков объекта х. Обучение линейного классификатора сводится к формированию значений параметров (а,Ь) на основе анализа конечной обучающей совокупности {(х,.^), j = \,...,N).

Наиболее популярным методом обучения линейного классификатора по обучающей совокупности является метод опорных векторов (Support l'ector Machine - Sl'M). разработанный Вапником B.H. и Червонснкисом А.Я.1. в основе которою лежит ими же ранее предложенный метод обобщенного портрета2. В основе метода лежит естественная идея выбирать ту гиперплоскость, которая в обучающей совокупности разделяет векторы признаков объектов разных классов с наибольшим зазором, дополнительно штрафуя возможные нарушения некоторыми объектами этого общего «идеального» требования. В данной диссертации исследуется и развивается именно метод опорных векторов.

Одно из основных преимуществ метода опорных векторов заключается в том. что как задача обучения, так и решающее правило классификации новых объектов определяются не самими векторами признаков отдельных объектов х(со)бМ". а только их попарными скалярными произведениями (х(и'))'х{и"):йхП->К, Из этого факта следует, что нет противоречия между традиционным признаковым способом погружения объектов распознавания в линейное пространство и беспризнаковым способом, предполагающим, что объекты со е могут быть представлены в компьютере только через некоторую числовую функцию парного отношения ^(ш',а>"). Правда, для того, чтобы идея поиска дискриминантной гиперплоскости в некотором линейном пространстве представления объектов реальною мира имела простую математическую реализацию, функция К(ы', co"):QxQ —>R должна обладать свойствами кернела (kernel function), т.е. быть симметричной и порождать неотрицательно определенные матрицы для всех конечных комбинаций объектов. Известно, что всякий кер-нел погружает множество объектов реального мира ы s Q в некоторое большее гильбертово пространство ПзО.в котором он играет роль скалярного произведения1,3.

Однако требование неотрицательной определенности для функции парного сравнения объектов является чрезвычайно ограничивающим. Альтернативный подход предложен Р. Дыоиным4 под названием реляционного дискршшнантного анализа (Relational Discriminant Analysis). Идея заключается в том, чтобы интерпретировать значения произвольной функции парного сравнения между всяким объектом со s fi и объектами из обучающей совокупное™ {ffl,,...,cov} как вектор вторичных признаков этого объекта х(га)=(хДм)=/С(со,.га).г=1,...,Л'), и

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

1 Vapnik V. Statistical Learning Theory. NY.: J. Wiley, 1998.

Вапник B.H., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). М.: Наука, 1974.

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

4 R. Duin. Е. Pekalska, D. Ridder. Relational discriminant analysis. Pattern Recognition Letters. Vol. 20. 1999. pp. I 175-1 181.

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

С учетом последнего замечания в данной диссертации рассматривается метод опорных векторов в его традиционном признаковом понимании.

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

Для разрешения этой проблемной ситуации в настоящей диссертации предлагается специальная байесовская постановка обучения распознаванию двух классов объектов в линейном признаковом пространстве, приводящая к обобщению метода опорных векторов и являющаяся теоретической основой для создания новых селективных методов обучения. Основная идея байесовской постановки заключается в построении системы вероятностных предположений о паре плотностей распределения объектов двух классов ф(х|><=±1,а,6), определяемой объективно существующей, но неизвестной гиперплоскостью (а,Ъ) в линейном пространстве признаков, при некотором априорном предположении о ее случайном выборе При этом именно структура первого семейства распределений определяет характерный принцип обучения по методу опорных векторов.

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

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

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

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

5 Середин О.С., Моттль В.В., Татарчук А.И., Разин Н.А. Выпуклые селективные критерии релевантных векторов для сокращения размерности описания объектов, представленных парными отношениями. Известия ТулГУ, Серия Естественные науки. Тула: Изд-во ТулГУ, 2013, Вып. 1, с. 165-176.

6 John С. Piatt. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods. Advances in large margine classifiers, 1999, pp. 61-74, MIT Press.

1 Peter Sollich. Probabilistic methods for Support Vector Machines. Advances in Neural Information Processing Systems 12, 2000, pp. 349-355, MIT Press.

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

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

На основе анализа мировой литературы в диссертации приняты четыре критерия для оценивания «качества» селективных свойств конкретного метода обучения:

а) эффективное подавление полностью шумовых попарно независимых признаков;

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

в) эффективное выделение группы информативных линейно независимых признаков:

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

По этим критериям в диссертации исследованы две наиболее популярных модификации метода опорных векторов, наделяющие его свойством отбора признаков - Lasso SVM (1-norm SVM) и Elastic Net SVM (Doubly Regularized SVM). Оба эти метода несколько разными средствами отбирают подмножество информативных признаков, число которых определяется структурными параметрами.

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

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

Один из новых методов, названный методом релевантных признаков (Relevance Feature Machine - RFM), не выделяя строгого подмножества информативных признаков, наделяет все признаки неотрицательными весами. Чем больше значение структурного параметра селективности, тем большее число весов приближаются к нулевым значениям, фактически исключая соответствующие признаки из принятия решения о классе объекта.

Другой предложенный метод, названный методом опорных признаков (Support Feature Machine - SFM), разбивает все множество признаков на три группы - полностью активные признаки, взвешенные признаки и полностью подавленные признаки. Можно считать, что метод SFM снабжает все признаки весами, но, в отличие от метода RFM, часть весов оказываются строгими единицами, часть принимает значения между единицей и нулем, а часть строго равны нулю.

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

Задачи исследования. Для достижения поставленной цели в диссертации сформулированы и решены следующие задачи:

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

2. Разработка вероятностной модели наблюдения объектов в пространстве векторов признаков относительно фиксированной разделяющей гиперплоскости, отражающей идею метода опорных векторов.

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

тегии отбора признаков - взвешивания всех исходно заданных признаков (feature weighting) и жесткого выбора их подмножества (feature subset selection).

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

5. Количественное экспериментальное исследование разработанных методов и алгоритмов па модельных данных и в ходе решения прикладных задач.

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

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

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

2. Вероятностная модель наблюдения объектов в пространстве векторов признаков относительно фиксированной разделяющей гиперплоскости.

3. Два семейства априорных вероятностных моделей направляющего вектора разделяющей гиперплоскости, отражающих стратегии отбора признаков на основе взвешивания всех исходно заданных признаков (feature weighting) и на основе жесткого выбора их подмножества (feature subset selection).

4. Комплекс байесовских методов и алгоритмов оценивания разделяющей гиперплоскости, реализующих принцип обучения с заданной селективностью отбора признаков объектов.

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

Связь с плановыми научными исследованиями. Работа выполнена в рамках гранта ИНТАС № 04-77-7347 «Принципы беспризнакового распознавания сигналов, символьных последовательностей и изображений» (2005-2006), грантов Российского фонда фундаментальных исследований № 05-01-00679-а «Линейные методы восстановления зависимостей в массивах данных произвольной природы», № 06-01-08042-офи «Теоретические основы, методы, инструментальные средства и новая открытая информационная технология построения систем идентификации личности по свободно пополняемому множеству биометрических характеристик», № 08-01-00695-а «Линейные методы комбинирования разнородной информации для решения задач анализа массивов данных произвольной природы», № 11-07-00409 «Методы выбора уровня сложности модели в задачах восстановления зависимостей между разнородными объектами реального мира».

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

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

Теоретические результаты диссертационной работы вошли в состав курса «Статистические методы анализа сигналов», читаемого профессором В.В. Моттлем студентам 5-го курса на кафедре «Интеллектуальные системы» ФУПМ МФТИ, и курсов «Теория обучения машин» и «Машинное обучение», читаемых профессором К.В. Воронцовым на ФУПМ МФТИ и в Школе анализа данных Яндекс, соответственно.

Апробация работы. Основные положения и результаты диссертации докладывались автором на конференциях:

• XIII всероссийская конференция «Математические методы распознавания образов», Зе-леногорск, 2007 г.;

• The 7th International Workshop on Multiple Classifier Systems, Prague, Czech Republic, 2007 г.;

• The 6th International Conference on Machine Learning and Cybernetics, Китай, Гонконг, 2007 г.;

• Международная конференция «International Conference of Pattern Recognition», США, Тампа, 2008 г.;

• Международная конференция «Интеллектуализации обработки информации». Украина, Симферополь, 2008 г.;

• 14-ая Всероссийская конференция «Математические методы распознавания образов», Суздаль, 2009 г.;

• The 9th International Workshop, MCS 2010, Cairo, Egypt, 2010 г.;

• Международная конференция «International Conference of Pattern Recognition», Япония, Токио, 2012 г.

Кроме того, основные результаты работы докладывались на семинаре отдела Интеллектуальных систем (Москва, ВЦ РАН, 2009 г., 2014 г.).

Публикации. По тематике исследований опубликовано 18 статей, в том числе 8 статей в изданиях, входящих в список ВАК.

Структура работы. Диссертация состоит из введения, четырех глав, заключения, приложения и списка литературы. Материал изложен на 125 страницах, содержит 2 леммы, 15 теорем, 15 рисунков, 8 таблиц и список литературы из 21 наименования.

Благодарность. Автор глубоко признателен своему научному руководителю, учителю и наставнику профессору, д.т.н. Вадиму Вячеславовичу Мотглю за неоценимый вклад в научное мировоззрение автора. Автор также благодарен сотрудникам отдела «Интеллектуальные системы» ВЦ РАН и сотрудникам кафедры ATM ТулГУ за внимание, помощь и поддержку в годы работы автора над диссертацией.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе дана краткая характеристика линейного подхода к обучению распознаванию двух классов объектов в некотором множестве объектов реального мира ueQ, j(co) = ±l, которые воспринимаются компьютером через векторы их числовых признаков х(со) = (л'1(ю),...,л',1(со)) е R". Основополагающим принципом машинного обучения является гипотеза компактности, которая, в самой общей формулировке для задач обучения распознаванию образов, означает, что объекты одного и того же класса имеют большее сходство между собой чем объекты, принадлежащие разным классам. Самым распространённым математическим инструментом измерения несходства между объектами реального

мира , погруженными числовыми признаками х(со) е R" в конечномерное евклидовое пространство, является спклидопа метрика p(ra',ro") = p(x',x") = || х'-х"||=[(х'-х")Г(х'-х")]1''2.

Суть линейного подхода заключается в поиске такой гиперплоскости, которая обеспечивала бы в некотором смысле «хорошее» разделение объектов первого _к(оэ) = +1 и второго

г(со) = -1 классов. При чтом всякий выбор направляющего вектора а е IR" и действительного числа ¿еК определяет некоторую разделяющую гиперплоскость 7-¿(a,6) = {zet°:a'z + 6 = 0} cr IR". Ключевым понятием линейного подхода является решающая функция (decision score function), понимаемая как расстояние от объекта х(ш) е R" до его проекции хн(и) е К" на гиперплоскость ~Н{л,Ь) с учетом знака в смысле евклидовой метрики:

= или с?(х|а,6) = агх + 6^0 при ||а||=1. (1)

(а а)' [<0=>>' = -1,

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

{(x,.>'j). j - Xj б Н", yj=±l. (2)

Степень несоответствия значения решающей функции d(x\a,b) для объекта x(w)eR" значению его целевой характеристики у(ш) выражается в виде функции потерь. В частности. нас далее будет интересовать функция потерь специального вида (рис. 1) íf). vil >

SOv/IsH, .iv¿ (3)

z

где v=v(ra) - истинный класс объекта, d = d(x\a,b) -

значение решающей функции (1), а е>0 - параметр, ко- ~Т

торый далее будем интерпретировать как зазор разделе- , ,.

ПИЯ двух классов объектов. Рис- 1 • Функция потерь 50-, d | £).

Функция потерь такого вида была впервые предложена Вапником В.Н. и Червоненки-сом А.Я. и привела к методу обобщенного портрета8, а затем к известному методу опорных векторов . Такая функция noicpb имеет нулевой штраф 6(у,с/|е) = 0 для объектов, удаленных от гиперплоскости на «достаточное» расстояние yd>e, и линейно растущий штраф 5(_у, ¿У | е) = l-yd/г для объектов, слишком близко приблизившихся к границе классов или попавших в область другого класса yd < е.

В качестве критерия обучения естественно искать такую гиперплоскость, которая разделяла бы обучающую выборку на два класса, с одной стороны, с как можно большей величиной зазора £ > 0. l/s2 —> min, а с другой, с как можно меньшей величиной суммарного штрафа для ошибочно классифицированных объектов обучающей выборки (2) 8; = 1 -(l/cl.v/a' x, +h). ^ ( ,„-,5, ■ Баланс таких требований к процессу обучения

выражается оптимизационным критерием

|е~:+C'VA .5, —>min(a,6,ö,E), а'а=1,

¿-¡j=\ ./ (4)

у,(а7 х j +Ь) > 5(1-5,), 5у >0, j = 1,...,N, е > 0.

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

liaiimiK ВН. McpiioiiuiKitL Л.Я Uupmt )\кпп шлмш:я обрашв ((Магнетические проблемы обучения). М.: Нау ка, 1974. Vapnik V. Statistical Learning Theory. NY.: J. Wiley, 1998.

Правда, критерий (4) не очень удобен, поскольку имеет вид задачи оптимизации на сфере ага=1, представляющей собой невыпуклое множество. Классический критерий получается из (4) простой заменой переменных а = sa, Ь = гЬ, ara=l/е2 :

|j5r,w(a,6,5|C) = a7'a + cXj1S/ ->min(a,6,5), (5)

[уj(aTXj +b)>l-6j, 5j>0, y' = l,...,7V.

Это задача квадратичного программирования - минимизации квадратичной функции

при линейных ограничениях типа неравенств. Название метода опорных векторов (Support

Vector Machine) объясняется тем, что направляющий вектор оптимальной разделяющей

гиперплоскости (a,6,6) = argmin7sriM(a,6,5|C) согласно (5) есть линейная комбинация

векторов признаков лишь небольшого числа объектов обучающей совокупности

a = V • V-X.-X-еМ", а именно только тех объектов, для которых в точке минимума ¿—ijXt>0^J J J

критерия (5) ограничения Vj(aTXj + b)>l-bj являются активными, т.е. множители Лагран-

жа при них (кj >0, j = \,...,N) строго положительны А.у >0. Значения множителей Ла-гранжа дает двойственная задача квадратичного программирования9, решение которой эквивалентно решению исходной задачи (5). Вся решающая функция

X X, X У/Х^х/+(С/2) £ >',

д>0й=——-у-

т

:0<л,<С/2 V

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

положительны Xj > 0.

В первой главе сформулирована основная идея селективного обучения, опирающаяся на тот факт10, что для оптимальной гиперплоскости, разделяющей без ошибок заданную обучающую совокупность размера N на два класса с зазором е > 0, справедлива следующая оценка математического ожидания вероятности ошибки на генеральной совокупности (в среднем по всем обучающим совокупностям заданного размера)

m [/?У2] п

(1)

N N N

Ч ■>

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

- представление гиперплоскости небольшим количеством m опорных векторов;

- разделение выборки с наибольшим зазором е между объектами разных классов;

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

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

В первой главе диссертации выполнен обзор и анализ существующих селективных модификаций метода опорных векторов, указана их недостаточность и сформулированы идеи двух вероятностных модификаций метода опорных векторов, а именно метода релевантных признаков с регулируемой селективностью (Relevance Feature Machine) и метода опорных признаков с регулируемой селективностью (Support Feature Machine), которые являются представителями, соответственно, непрерывных и дискретных встроенных

Vapnik V. N. The Nature of Statistical Learning Theory. Springer, 1995.

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

Во второй главе излагается общая вероятностная байесовская постановка задачи обучения двухклассовому распознаванию образов в линейном пространстве хеМ" на основе метода опорных векторов, сформулированного в его классическом виде9 в сугубо детерминистских терминах. Основная идея предлагаемой байесовской постановки заключается в построении специальной системы вероятностных предположений о паре плотностей распределения векторов признаков объектов двух классов ф(х|у = 1) и ср(х| v = -l), определяемой объективно существующей, но неизвестной гиперплоскостью в линейном пространстве признаков, при некотором априорном предположении о ее случайном выборе.

Пусть arx + bs;0 - некоторая гиперплоскость с направляющим вектором аеМ" и параметром сдвига be R. Свяжем с этой гиперплоскостью пару параметрических семейств условных плотностей распределения вероятностей вектора признаков случайного объекта

Íl,>'(arx + 6)>1,

<p(x|a ,b,y\c) = const { г / т N-1 т (8)

v ' exp -c(l-v(a \ + b)j \,у(а х + Ь)<1.

Эти два семейства призваны выражать предположение, что случайные векторы признаков объектов двух классов распределены главным образом в «своих» полупространствах а7х + 6>0 и a7x + ¿<0, однако могут попадать и в «чужие» полупространства, причем степенью возможности «ошибочных» значений управляет параметр с>0. Некорректность равномерного распределения в бесконечной области в верхней строке (8) не приводит далее к математическим противоречиям, поскольку оно участвует только в формуле Байеса11.

Будем предполагать, что получена обучающая совокупность (2), образованная векторами признаков объектов х). = (xiJti = \,—,п) с известными индексами классов vy. Тогда условное распределение обучающей совокупности в целом (А" | Y) представимо в виде произведения плотностей (8):

Ф(Л-|Г,а,6;С) = Щ,Ф(х/ I(9)

Другим ключевым предположением в предлагаемой вероятностной модели является суждение об априорном совместном распределении Ч^б) параметров (а, Ь) разделяющей гиперплоскости а'х + />^0. Будем считать, что отсутствуют какие-либо априорные предпочтения величин порога разделяющей гиперплоскости b е К, тогда

^(а^осЧ^а). (10)

Апостериорная плотность распределения P(a,b\X,Y;c) параметров (а,Ь) относительно обучающей совокупности (X,Y) определяется формулой Байеса:

const

Понимание обучения как задачи максимизации этой апостериорной плотности распределения в пространстве параметров модели (а, Ь) приводит к очевидному критерию:

(á,¿|X,K:c) = arg max Ч'(а,Л)Ф(А'| K,a,6;c) = argniax(ln4'(a, 6) + \n<$>(X\Y,a,b,cj). (12)

Байесовский критерий обучения (12) со структурой условного распределения наблюдений (8)-(9) является основным теоретическим предложением данной диссертации.

ДеГроот М. Оптимальные статистические решения. М.:, Мир, 1974.

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

Теорема 1. Критерий обучения (12) для семейства распределений (8) и априорного распределения параметров (10) эквивалентен оптимизаг/ионной задаче минимизации целевой функции J(a,b,b\c) на выпуклом множестве, заданном набором линейных ограничений-неравенств для объектов обучающей совокупности:

|Да, Ъ, б | с) = - 1п ¥(а) + 5, -> min(a, b, 5), \yJ{aTxJ +b)> 1-5,,S; >0, j = 1,...,jV.

По своей структуре этот критерий отличается от классического критерия опорных векторов (5) только слагаемым -ln^ía) вместо квадрата нормы направляющего вектора искомой разделяющей гиперплоскости ага. Параметр с > 0 семейств распределений (8), отвечающий за априорную способность объектов генеральной совокупности нарушать границу своих классов, регламентирует приоритет между качеством разделения обучающей совокупности и априорными предпочтениями по выбору направляющего вектора.

Если функция 1пЧ/(а) строго вогнута, то целевая функция У(а,/?,й|с) в (13) строго выпукла. Поскольку система ограничений в (13) образует выпуклый многогранник в линейном пространстве (a,¿,6) еЕ" хМи| предлагаемый в диссертации обобщенный критерий обучения по методу опорных векторов в общем виде представляет собой задачу выпуклого программирования. Это значит, что существует единственный набор оптимальных параметров (á,¿), удовлетворяющий всем ограничениям задачи (13) и доставляющий минимум целевой функции У(а,6,8| с).

Результатом обучения по обучающей совокупности (2) является решающее правило классификации í/(x|á,¿) = árx + ¿^0, применимое к любому новому объекту с вектором признаков xeR".

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

Действительно, примем предположение, что случайно появившийся новый объект, не содержащийся в обучающей совокупности, объективно принадлежит том)' или иному классу с некоторыми априорными вероятностями =Р(у = -1), q¡ =Р(у = 1), q_¡ + qt =1. Для простоты дальнейших рассуждений примем, в частности, равными априорные вероятности двух классов q_t=ql=l/212. Тогда, для параметров разделяющей гиперплоскости

(а,6), найденных как решение задачи обучения (13), апостериорная вероятность принадлежности объекта х е R" к классу у = 1 определяется формулой Байеса через плотности распределения двух классов <р(х| á,¿, у;с):

р(у = \\х;й,Ь,с) = \-р(у = -\\ъ*,Ь,с) =-Ф(х|у = 1;аЛС) _ _ (14)

Ф(х|>> = 1; а,6,с) + ф(х|>' = -1; а, 6, с)

12 Выбор разных априорных вероятностей классов q^ * цЛ отражает другое предположение об их свойстве в сравнении с выбором значения параметра пересечения классов с >0 , характеризуя их разнонаполненность. В данной работе роль априорных вероятностен классов (с/,,^ ,) как параметров вероятностной модели детально не исследуется.

Теорема 2. Для условных плотностей распределения (8) и для случая равных априорных вероятностей =1/2 апостериорные вероятности классов (14) будут иметь вид сигмоидоподобной функции

|1 +ехр(с)ехр[-с(агх +6)]| ,агх+Ь <-1,

р{у = Цх,-лМс) = \-р(у = -\\х,я,кс) = - |1+ехр[-2с(агх + 6)]| ',-1<агх + 6<1, (15)

|1+ехр(-с) ехр[-с(агх + 6)]} , агх + Ь > 1.

Заметим, что параметр с > 0 условных распределений (8), определяющий степень пересечения классов, управляет крутизной сигмоидоподобного обобщения (15) ступенчатой

решающей функции а'х + б^О. Соответствующая зависимость апостериорной вероятности (15) от значения решающей функции ¿/(х! а,6) = а'х + 6 показана на рис. 2.

'•р(у = 11 х; а, Л, с) = I -р(у = 11 х; а. Л, с)

11 + ехр(с) exp[-c(â'х + ¿)]|

: 1/2

11 + ехр(-с) ехр[-с( â' х + 6)]} -d(x\â,b) = âTx + b

|l + exp[-2c(ârx + è)]}"' Рис. 2. Апостериорные вероятности классов для вновь поступившего объекта в вероятностной интерпретации метода опорных векторов.

Классический метод опорных векторов: Частный случай нормальных априорных распределений компонент направляющего вектора asR" с одинаковыми дисперсиями. Рассмотрим задачу обучения (13), приняв предположение, что случайный направляющий вектор образован независимыми компонентами а = (а,,...,а„) с нормальными плотностями распределения, имеющими нулевое математическое ожидание и одинаковые дисперсии г, =... = /; =г. Тогда xP(a|/-) = [l/(/-"/2(2n)")]exp(-(l/2/-)^'_|a,2и задача обучения (13)

примет вид классического критерия обучения по методу опорных векторов (5), где С = 1er.

Заметим, что в диссертации впервые предложена формальная интерпретация структурного параметра С в методе опорных векторов как относительной степени пересечения классов по сравнению с общей априорной дисперсией компонент направляющего вектора С = 2сг. В такой интерпретации нет смысла рассматривать иные значения априорной дисперсии, нежели г = 1/2, тогда С = с.

Известные методы автоматического сокращения размерности признакового описания объектов в рамках метода опорных векторов, а именно, 1-norm SVM (Lasso SVM)" и Doubly Regularized SVM (Elastic Net SVM) получаются из обобщенного критерия (13) специальным выбором априорной плотности распределения направляющего вектора Ч'(а). Метод Elastic Net SVM, как более общий из них, получается из (13) при предположении, что случайный направляющий вектор образован независимыми компонентами а=(а|(...,а„) с одинаковыми плотностями распределения »|/(aJp,p)=Dexpf-((3a2+p|a(|)], которые определяются одинаковыми значениями параметров (Р,ц). Здесь нормирующая константа определяется обоими параметрами:

11 Bradley P.. Mangasarian O. Feature selection via concave minimization and support vector machines. In International Conference on Machine Learning. 199S.

IJ Li Wang. ,ti /lui hIni /.mi The doubly regularized support vector machine. Statistica Sinica, 01/2006; 16:589-615.

D =

2/—expf — |ф[-^= , где Ф(г<) = -jl=fexp

V/3 yjiß,

2N

z

dz - функция Лапласа15.

В этом случае совместная априорная плотность распределения направляющего вектора определяется выражением

IP,и) = D" ехр (Ро2+ ЦI а, |)], In Y(a | Р, ц) = const ~ (p^l, I ■я« l) >

и (13) примет вид, эквивалентный методу Elastic Net SVM:

В еще более частном случае, когда р = 0, получается метод обучения Lasso SVM: Ц„51,,(а,М|с,г) = а, | +c(r/2)VÎX*.18y->min(a,é,ô),

{л +b) * i-Sy. s^o,; = i ,...,N. (17)

Этот критерий эквивалентен (13) при интерпретации независимых компонент случайного направляющего вектора а = (at,...,an) как распределенных по закону Лапласа \|*(а,|г) =

(2r)-wexp(-(r/2)-V2|e(|).

В диссертации не обсуждаются соответствующие алгоритмы оптимизации, они детально исследованы в работах13,14,16. Заметим лишь, что в силу специфики принятых априорных распределений критерии (16) и (17) чрезвычайно важным свойством беспереборного отбора признаков непосредственно в ходе обучения. Это свойство является результатом склонности этих критериев в точке минимума присваивать нулевые значения большинству компонент направляющего вектора а, = 0, реализуя при этом, вообще говоря, разумный отбор подмножества «полезных» признаков.

В диссертации теоретически исследована способность регуляризующих функций ^ ( af ,

а2 + М-У."_|I а, | и соответственно, в классическом критерии SVM (5), Elastic

Net SVM (16) и Lasso SVM (17), отбирать подмножество информативных признаков с точки зрения требований к селективности обучения, сформулированных на с. 4-5 автореферата. Исследование основано на сформулированном в диссертации понятии множеств наиболее и наименее предпочтительных ориентаций направляющего вектора разделяющей гиперплоскости в пространстве R", определяющих «стиль» выбора подмножества полезных признаков.

Суждение о классическом SVM тривиально - все направления одинаковы по предпочтительности, и свойство селективности полностью отсутствует. Что же касается методов Elastic Net SVM и Lasso SVM, то оказалось, что они идентичны по ориентации предпочтительных направлений - наилучшим является направление, оставляющее единственный признак, а роль наихудшего играет направление, оценивающее все признаки как равнозначные. Это означает, что соответствующие априорные распределения направляющего вектора выражают предположение, что среди признаков есть только один признак, полезный для распознавания класса объекта. Следовательно, в ситуациях, когда в исходных данных таких признаков более одного, обучение методами Elastic Net SVM и Lasso SVM может приводить к снижению обобщающей способности полученных решающих функций.

15 Это утверждение доказано Е.О. Черноусовой.

16 Разин H.A. Выпуклые критерии и параллелизуемые алгоритмы селективного комбинирования разнородных представлений объектов в задачах восстановления зависимостей по эмпирическим данным. Днсс. к.ф.-м.н. ВЦ РАН, 2013.

Известно также14, что Lasso SVM в группе линейно зависимых признаков полностью игнорирует факт их зависимости - отбирает лишь один такой признак, отбрасывая остальные. В то же время, Elastic Net SVM стремится оставлять всю линейно зависимую группу целиком, даже если она малоинформативна. В диссертации показано, что последнее свойство Elastic Net SVM также ведет к снижению обобщающей способности обучения.

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

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

Метод релевантных признаков с регулируемой селективностью использует естественное обобщение классического метода опорных векторов за счет введения в его вероятностную постановку дополнительного предположения о том, что независимые компоненты направляющего вектора а = (ах,...,ап) распределены, как и прежде, по нормальному закону с нулевыми математическими ожиданиями, но с разными неизвестными случайными дисперсиями /- >0,/ = 1,...,и, характеризующимися некоторым априорным распределением, и подлежащими оцениванию в процессе обучения по байесовскому принципу вместе с параметрами разделяющей гиперплоскости (а,Ь). В литературе подобные дополнительные априорные предположения о параметрах, участвующих в некотором ранее принятом априорном предположении, принято называть Hyper Prior Assumptions.

В этом случае совместная априорная плотность распределения направляющего вектора определяется выражением

У(а | г) = | >-„...,/;) = __i__exp(-<l/2)^;=i(l/,-)a,2), (18)

Удобно оперировать обратными дисперсиями 1//; , называемыми мерами точности соответствующих случайных величин", полагая, что обратные дисперсии имеют одно и то же априорное гамма распределение у((1 //-)|a,р)ce(1 ехр(-Р(1 //;)), ; = 1,...,/г. Будем выбирать значения двух параметров априорного гамма распределения аир, задавая один общий параметр 0 < ц < да :

а = (1 + ц)-/2ц, Р = 1/2ц. В этом случае параметрическое семейство гамма распределений будет иметь вид

у(1/г, I ц) ОС (l/,-)(,V>/2Mехр[-(1/2ц)(1/^)], / = 1 ,...,„. (19)

Нетрудно убедиться, что при увеличении параметра ц от 0 до œ вид априорного гамма распределения изменяется от сконцентрированного вокруг значения 1//• =а/Р = 1 до почти «равномерного» на интервале 0<1//- <со (рис.3.). 10 7.5 5 2.5 0

j |Д = 0.001

1 (а)

Рис. 3. Зависимость априорного гамма распределения дисперсий компонент направляющего вектора от параметра р.. Обозначим через С(г | |л) = | априорную совместную плотность распреде-

ления обратных дисперсий:

G(r| ц) = G(r1,...,r„ | ц) = ПмГ((1/';)1м)0С (П'ЛГ<)°П' ^ "Ф(-Qf2rtT."jl/ri))- (20)

Тогда совместная априорная плотность распределения параметров разделяющей гиперплоскости (18) и обратных дисперсий компонент направляющего вектора (20) запишется как

Ф(а, Ь, г | ц) ос Ч^(а | r)G(r | и). Соответственно, совместное апостериорное распределение всех переменных модели относительно обучающей совокупности, аналогично (11), пропорционально произведению

Р(а, Ь, г\Х, Г; с, р) ос Ч^а | r)G(r | ц)Ф(Х | Г, а, b, с). Верхняя черта в обозначениях плотностей H^a.b.rln) и Р(а, b, г | X, К; с, |л) отражает тот факт, что это совместные распределения (априорное и апостериорное) параметров гиперплоскости (а,6) и вектора дисперсий г в отличие от маргинальных распределений параметров гиперплоскости ЧЧа,^) (10) и Р(я,Ь\ X, К; с) (11).

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

(а,6,г|Л\У;р,с)= arg шах Р(а,й,г| А", У, ц,с) =

a£R»,A£R,r£K" (2])

argmax In *F(a|r) + lnG(r | (.i) + 2_, ..In ф(ху \y ¡ \ &,b,c) ,

представляющему собой обобщение критерия (12).

Теорема 3. Оптимизационная задача обучения (21) для (18), (19) и (20) эквивалентна критерию

[Уяга/ (а,й,г,6[С, [С/';)(а,2+(1/ц)) + ((1/ц) + 1 + ц)1п л;. ^min(a,ö, г, б),

При нулевом значении параметра р.-»О и, соответственно, 1/ц—>оо, штрафы (1/ц)[(1/т;) + 1п?;.] настолько велики, что все оценки дисперсий равны единицы г{ =... = г(> =1 в точке минимума критерия (22), который становится эквивалентным критерию классического метода опорных векторов, вообще не обладающему свойством селективности.

При неограниченном увеличении параметра ц—»со априорное гамма распределение обратной дисперсии каждой компоненты направляющего вектора 1/т; (19) и их совместное априорное распределение (20) становятся практически «равномерными», соответственно, на положительной полуоси 0<1/г, <со (рис. 3-г) и в положительном квадранте пространства К". Это в пределе приводит к исчезновению слагаемого lnG(r||_t) в критерии (21) и слагаемого (1/ц)[(1//;) + 1п/;.] в целевой функции критерия (22), штрафующего отклонение от единицы, и критерий становится чрезмерно селективным.

В диссертации предложен алгоритм численного решения оптимизационной задачи (22), использующий метод Гаусса-Зайделя с поочередной оптимизацией по двум группам переменных (я1,...,ая)6,51,...,8д.) и (/*,,■■■,!"„). При фиксированных (rt,...,rn), оптимизация по (al,...,a/l,b,5,,...,5K) критерия (22) сводится к решению двойственной задачи квадратичного программирования

1Е>А = 0,0<МС/2,У = 1,...,7У.

Естественно принять начальные значения (r° = 1, i = 1,...,«), что соответствует стандартному методу опорных векторов (5). После того, как на очередном шаге итерационного процесса к = 0,1,2,... найдено решение (>^,...,A.*V) двойственной задачи (23) для текущего приближения (rf,...,/;*), новые значения дисперсий на следующем шаге опре-

деляются следующей теоремой.

Теорема 4. Новые значения дисперсий (г|*+1,...,7-*+1) определяются региением (А.*,...Д*„) двойственной задачи (23) для текущего приближения (г,\...,г*) согласно выражению

¿.JX^Za.xj^l I * J i ^ n (24)

' ц+1+1/ц

Итерационная процедура обучения обычно сходится за 10-15 шагов, а сам алгоритм демонстрирует способность подавлять неинформативные признаки за счет выбора очень маленьких весов г., в решающем правиле

d(x I ix г) =£ д^УЛЕ!, W+6^0, где оптимальное значение порога b определяется выражением

Z,o<i,<, ЛЬ.^Л!!, w HC/2-iZj^yj

Х,о<>,<глЛ

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

В связи с этим обстоятельством предложенный в диссертации метод обучения (22) назван методом релевантных признаков с регулируемой селективностью, или, полностью характеризуя метод, Selective Relevance Feature Support Vector Machine.

Метод опорных признаков с регулируемой селективностью базируется на другом предположении об априорном распределении lF(a) независимых компонент направляющего вектора а = (а,,...,а„). Вид априорной плотности Ч'(а) представляет собой комбинацию распределения Лапласа при значениях нормы компонент, не превышающих заданного порога | а, |< ц, и нормального распределения при больших значениях ||> (я (рис. 4):

17 C.M. Bishop, M.E. Tipping. Variational relevance vector machines. Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann, 2000, pp. 46-53.

(1 = 4

линей- Ишалра-

пая тичная

II

; квалра

: тичная

линейная ! (■?>;

(27)

Рис. 4. Зависимость функции q(at |р) комбинированного априорного распределения компонент направляющего вектора от параметра р. В этом случае совместное априорное распределение направляющего вектора а = (а,,...,а(|) определяется выражением

Ч»(а) = ЧЧа,,...,а„) ос expq(a, |р)). (26)

Априорное предположение (26) и обобщенный критерий обучения метода опорных векторов (13) определяют вид оптимизационной задачи обучения

Vy +ô)<l-Sy, 5> >0,

Задача (27) является задачей выпуклого программирования в пространстве R"xRv", поскольку каждое слагаемое целевой функций выпукло в К, а система ограничений для заданной обучающей выборки образует выпуклый многогранник.

Величина порога 0<р<оэ плотности (25) выполняет роль параметра селективности обучения и при р = 0 => q(al | р) = а,2 оптимизационный критерий (27) эквивалентен критерию метода опорных векторов (5) с минимальной способностью к отбору признаков, а при достаточно больших значениях селективности р з> 0 => g(al | р) = 2р | а, \ - критерию Lasso SVM (17) с увеличивающейся селективностью обучения по мере увеличения р относительно параметра с до полного подавления всех признаков.

Теорема 5. Решение задачи (27) определяется решением (£,,>0,/ е I = {1,...,и}, XJ>0,j=l,...,N) двойственной задачи

ЦХ„...,Х„|С,р) = :£>У-I^ILfl/î)^,->тах(Х„...Д„),

Z>A=0, 0<Ху<С/2,у = 1,...,М и выражается следующим образом

â, =0, (e/" = |ie/:Z^,X/l^W^Â

■ â<'6/"={/s/-n2=oj,

Теорема 6. Итоговое решение о классе нового объекта имеет вид

(28)

(29)

(30)

где коэффициенты г\, определяются дополнительной задачей линейного программирования

' S,гТш-ZZIУ,У!хМ» (3')

5у>0, _/=1...../V, 0<г|,<1, / 6

Оптимальные ненулевые значения компонент л(.еК, ;'е/°и/+ направляющего вектора (29), как и в классическом методе опорных векторов, выражаются в виде линейной комбинации опорных объектов обучающей выборки (2), но, в отличие от SVM, решение задачи (29) явным образом указывает множество /е/" строго нулевых компонент а, =0, а, следовательно, множество неактивных или неопорных признаков, т.е. признаков, не участвующих в принятии решения (30) о классе нового объекта. По этой причине, по аналогии с методом опорных векторов, предложенный метод назван в диссертации методом опорных признаков с регулируемой селективностью или Selective Support Feature Support Vector Machine.

Параметр селективности ц>0, как и параметр С>0, является структурным параметром критериев обучения (22) и (27), и определяет последовательность вложенных классов моделей распознавания, «размерность» которых уменьшается с ростом ц. Для выбора оптимальных значений параметров в данной работе используется метод скользящего контроля, зарекомендовавший себя, как наиболее универсальный и один из самых эффективных способов оценивания обобщающей способности методов обучения по обучающей выборке.

Преимущества предложенных двух критериев селективного обучения метода релевантных признаков (22) и метода опорных признаков (27) по сравнению с известными критериями Elastic Net SVM (16) и Lasso SVM (17) исследуются в диссертации с теоретической точки зрения в конце главы 3 и экспериментально в главе 4.

В частности, теоретическое исследование регуляризующей способности метода опорных признаков (27) показало, что множество наименее предпочтительных ориентаций направляющего вектора состоит не из одного направления, оценивающего все признаки как равнозначные (методы Elastic Net SVM и Lasso SVM), a составляет конус направлений

{а е R" : ^"^of =1, |0;12:ец, i=\,...,n} , предполагающих включение в решающую функцию яТх + Ь^0 сразу всех признаков с разными достаточно большими весами | а,-1 >ец, г=1,...,и.

Это условие означает «неразличимость» для обучения таких направляющих векторов между собой с точки зрения их априорной предпочтительности. Следовательно, в ситуациях, когда в исходных данных есть несколько значимых признаков, выбор весов, с которыми они будут входить в решение, определяется исключительно качеством разделения выборки, а не априорным стремлением выделить только один из признаков, подобно методам Elastic Net SVM и Lasso SVM.

С другой стороны, предложенный метод опорных признаков (27) характеризуется избирательным «стилем» учета линейной зависимости признаковых описаний объектов при их отборе. Избирательность предложенного метода выражается в стремлении сохранять в итоговом решении только попарно зависимые признаки, обладающие достаточной значимостью для распознавания. Для сравнения метод Elastic Net SVM сохраняет все линейно зависимые признаки. Малозначимые признаки при этом максимально подавляются в процессе обучения независимо от их попарной линейной зависимости, аналогично Lasso SVM.

В четвертой главе приводятся результаты экспериментального исследования предложенных в диссертации методов обучения с регулируемой селективностью, а именно, метода релевантных признаков (22) и метода опорных признаков (27). Основной целью экспериментального исследования является анализ предложенных методов в сравнении с существующими методами SVM (5), Lasso SVM (17) и Elastic Net SVM (16) по их способности сокращать признаковое описание объектов распознавания и, в конечном итоге, повышать

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

Экспериментальное исследование имеет общепринятую структуру, включающую в себя серию модельных экспериментов и пример решения прикладной задачи. Модельные эксперименты диссертации основаны, по своей структуре, на исследовании, проведенном авторами метода Elastic Net SVM14 для иллюстрации преимущества модулыю-квадратичной функции штрафа Elastic Net по сравнению с традиционным модульным Lasso. Прикладной задачей является задача распознавания рака легких из репозитория UCI18.

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

Именно этот аспект организации экспериментального исследования заслуживает особого внимания. Структура четырех модельных задач настоящей диссертации соответствует четырем простым требованиям к селективному обучению, приведенным на с. 5 автореферата. Результаты модельных экспериментов, изложенные в диссертации, наглядно иллюстрируют весьма важный факт, что ни один из существующих методов селективного обучения, включая предлагаемые, не удовлетворяет сразу всем этим весьма неизощренным требованиям. Предложенный метод опорных признаков (27) хорошо справился с подавлением шумовых признаков (а,б) при линейно независимых информативных признаках (в), существенно улучшив и без того неплохой результат существующего метода Elastic Net SVM. Однако метод релевантных признаков (22) в этих условиях оказался далеко не так эффективен. Требование выделять группу информативных признаков, которые только вместе обеспечивают достаточную точность распознавания (г), оказалось весьма проблематичным, как для существующего Elastic Net SVM, так и для предложенного метода опорных признаков, селективность которых обеспечивается за счет использования в целевых функциях критериев обучения штрафа модуля. Вместе с тем требование (г) не доставило никаких сложностей для второго предложенного метода релевантных признаков, селективность которого имеет отличную от привычного модуля природу.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. Сформулирована общая математическая постановка задачи обучения двухклассовому распознаванию образов в линейном пространстве признаков на основе количественного измерения расстояния между вектором признаков объекта и разделяющей гиперплоскостью.

2. Сформулирована байесовская постановка задачи обучения двухклассовому распознаванию образов в линейном пространстве признаков, дающая вероятностное обоснование метода опорных векторов.

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

18 http://archive.ics.uci.edu/ml/datasets/Lung+Cancer - UCI Machine Learning Repository: Lung Cancer Data Set.

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

5. Теоретически исследованы преимущества предложенных двух критериев селективного обучения метода релевантных признаков и метода опорных признаков по сравнению с известными критериями Elastic Net SVM и Lasso SVM.

6. Экспериментально получены количественные оценки эффективности предложенных методов обучения на модельных данных и данных задачи распознавания рака легких.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Середин O.C., Моттль В.В., Татарчук А.И., Разин Н.А. Выпуклые селективные критерии метода релевантных векторов в пространстве парных отношений объектов распознавания. Известия ТулГУ, Серия Естественные науки. Тула: Изд-во ТулГУ, 2013, Вып. 1, с. 165-176.

2. О. Seredin, V. Mottl, A. Tatarchuk, N. Razin, D. Windridge. Convex Support and Relevance Vector Machines for selective multimodal pattern recognition. Proceedings of the 21th International Conference on Pattern Recognition, Tsukuba, Japan, November 11-15, 2012. IAPR, 2012, ISSN 978-4-9906441-1-6, 2012, pp. 1647-1650.

3. A. Tatarchuk, E. Urlov, V. Mottl, D. Windridge. A support kernel machine for supervised selective combining of diverse pattern-recognition modalities. In: Multiple Classifier Systems. Lecture Notes In Computer Science, Vol. 5997. Springer-Verlag, Berlin \ Heidelberg, 2010, ISBN 978-3-642-12127-2_l7, pp. 165-174.

4. Татарчук А.И., Урлов E.H., Моттль B.B. Метод опорных потенциальных функций в задаче селективного комбинирования разнородной информации при обучении распознаванию образов. Доклады 14-й Всероссийской конференции «Математические методы распознавания образов», Суздаль, 21-26 сентября 2009 г., с. 192-195.

5. Татарчук А.И., Урлов Е.Н., Ляшко А.С., Моттль В.В. Экспериментальное исследование обобщающей способности методов селективного комбинирования потенциальных функций в задаче двухклассового распознавания образов. Доклады 14-й Всероссийской конференции «Математические методы распознавания образов», Суздаль, 21-26 сентября 2009 г., с. 196-199.

6. Татарчук А.И., Сулимова В.В., Моттль В.В., Уиндридж Д. Метод релевантных потенциальных функций для селективного комбинирования разнородной информации при обучении распознаванию образов на основе байесовского подхода. Доклады 14-й Всероссийской конференции «Математические методы распознавания образов», Суздаль, 21-26 сентября 2009 г., с. 188-191.

7. A. Tatarchuk, V. Sulimova, D. Windridge, V. Mottl, M. Lange. Supervised selective combining pattern recognition modalities and its application to signature verification by fusing on-line and off-line kernels. In: Multiple Classifier Systems. Lecture Notes In Computer Science, Vol. 5519. Springer-Verlag, Berlin \ Heidelberg. ISBN 978-3-642-02325-5, 2009, pp. 324-334.

8. A. Tatarchuk, V. Mottl, A. Eliseyev, D. Windridge. A Bayesian approach to multimodal pattern recognition with supervised selectivity of modalities. Proceedings of 9th International Conference on Pattern Recognition and Image Analysis: New Information Technologies, Nizhni Novgorod, September 14-20, 2008, vol. 2, p. 204.

9. B.B. Моттль, А.И. Татарчук, А.П. Елисеев Экспериментальное исследование методов многомодального распознавания образов с регулируемой селективностью.

Известия Тульского государственного университета. Технические науки, вып.З. - Тула: Изд-во ТулГУ, 2008.

10. Tatarchuk A., Mottl V., Eliseyev A., YVindridge D. Selectivity supervision in combining pattern-recognition modalities by feature- and kernel-selective Support Vector Machines. Proceedings of the 19th International Conference on Pattern Recognition, Vol 1-6, IEEE, ISBN 978-1-4244-2174-9, 2008, pp. 2336-2339.

11. Моттль В.В.. Татарчук А. И., Елисеев А. П. Регулируемая селективность в многомодальном распознавании образов. Таврический вестник информатики и математики, 2008, том. 2, с. 89.

12. Моттль В.В., Татарчук А. И., Елисеев А. П. Многомодальное распознавание образов с регулируемой селективностью. Тезисы докладов международной научной конференции «Интеллектуализации обработки информации», Симферополь, 2008, с. 172.

13. Моттль В.В., Татарчук А. И., Елисеев А. П. Исследование методов комбинирования классификаторов и потенциальных функций в многомодальном распознавании образов. Тезисы докладов международной научной конференции «Интеллектуализации обработки информации», Симферополь, 2008, с. 176.

14. Mottl V., Tatarchuk A., Krasotkina О., Seredin О., Sulimova V. Combining pattern recognition modalities at the sensor level via kernel fusion. In: Multiple Classifier Systems. Lecture Notes In Computer Science, Vol. 4472. Springer-Verlag, Berlin \ Heidelberg. ISBN 978-3-540-72481-0, 2007, pp. 1-12.

15. Моттль B.B., Татарчук А. И., Красоткина О.В., Сулимова В.В. Комбинирование потенциальных функций в многомодальном распознавании образов. Математические методы распознавания образов. 13-я Всероссийская конференция: Сборник докладов. М.: МАКС Пресс, 2007.

16. Valentina Sulimova, Vadim Mottl, Alexander Tatarchuk Multi-Kernel approach to on-line signature verification. // Proceedings of the Eighth IASTED International Conference on Signal and Image Processing, ACTA PRESS ANAHEIM, ISBN 978-0-88986-583-9, 2006, pp. 448-453.

17. В.В. Сулимова, B.B. Моттль, А.И. Татарчук. Автоматический выбор наиболее информативных фрагментов в задачах распознавания сигналов разной длительности. // Труды конференции «Интеллектуализация обработки информации»-2006, Алушта, стр. 152-154.

18. В.В. Сулимова, В.В. Моттль, А.И. Татарчук. Автоматический выбор наиболее информативных фрагментов в задачах распознавания сигналов разной длительности. // Таврический вестник математики и информатики - № 1, 2006, стр. 109-115.

Жирным шрифтом выделены статьи в изданиях, рекомендованные ВАК.

Личный вклад соискателя в работах с соавторами заключается в следующем:

[1,2] Предложен выпуклый селективный критерий релевантных векторов и исследованы свойства двойственной задачи обучения.

[3,4] Предложен критерий метода опорных признаков и опорных потенциальных функций, исследованы свойства двойственной задачи обучения, разработан алгоритм решения выпуклой задачи обучения.

[5,9,13] Разработана структура экспериментального исследования методов релевантных признаков и опорных признаков.

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

[7,8] Разработана вероятностная методология селективного комбинирования разнородных модальностей представления объектов распознавания.

[10,11] Разработан механизм регулирования селективности отбора признаков при обучении распознаванию образов по методу опорных векторов.

[14,15] Разработаны принципы комбинирования разнородных представлений объектов на уровне сенсоров.

[16] Разработана математическая идея применения методов отбора признаков для задачи распознавания рукописных подписей, представленных динамическими характеристиками.

[17,18] Разработана математическая идея применения методов отбора признаков для выделения информативных фрагментов сигналов.

Подписано в печать: 28.04.14

Объем: 3 п.л. Тираж: 100 экз. Заказ № 170 Отпечатано в типографии «Реглет» г. Москва, Ленинский проспект, д.2 (495) 978-66-63, www.reglet.ru

Вычислительный центр им. А.А. Дородницына Российской академии наук

Н^гравах рукописи

04201459096

Татарчук Александр Игоревич

БАЙЕСОВСКИЕ МЕТОДЫ ОПОРНЫХ ВЕКТОРОВ ДЛЯ ОБУЧЕНИЯ РАСПОЗНАВАНИЮ ОБРАЗОВ С УПРАВЛЯЕМОЙ СЕЛЕКТИВНОСТЬЮ ОТБОРА ПРИЗНАКОВ

05.13.17 - Теоретические основы информатики

диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель д.т.н., профессор В.В. Моттль

Москва, 2014

Содержание

Введение...........................................................................................................5

1 Проблема селективного комбинирования признаков в линейных методах обучения распознаванию образов...........................................16

1.1 Линейный подход к обучению распознаванию двух классов объектов..............................................................................................16

1.1.1 Разделяющая гиперплоскость в линейном пространстве признаков.........16

1.1.2 Концепция оптимальной разделяющей гиперплоскости для обучающей совокупности: Метод опорных векторов...................................................18

1.1.3 Вероятностная интерпретация метода опорных векторов........................22

1.2 Проблема переобучения при обучении в признаковом пространстве большой размерности..................................................23

1.2.1 Природа переобучения в линейном пространстве признаков объектов... 23

1.2.2 Существующие способы отбора признаков в методе опорных векторов 25

1.2.2.1 1 -norm SVM (Lasso SVM)...................................................................25

1.2.2.2 Doubly Regularized SVM (Elastic Net SVM).......................................26

1.2.2.3 Elastic SCAD SVM..............................................................................28

1.2.3 Свойства методов отбора признаков и недостаточность существующих подходов......................................................................................................29

1.2.3.1 Механизм селективности отбора признаков.....................................29

1.2.3.2 Эффект группировки признаков........................................................35

1.3 Предлагаемая концепция: Байесовский подход к одновременному построению разделяющей гиперплоскости и выбору подмножества релевантных признаков.............................................36

1.4 Основные задачи исследования.........................................................37

2 Байесовский подход к поиску оптимальной разделяющей гиперплоскости.........................................................................................38

2.1 Параметрическое семейство пары плотностей распределения, определяемое гиперплоскостью........................................................38

2.2 Априорное распределение параметров гиперплоскости..................41

2.3 Общий байесовский критерий обучения для параметрического семейства пары плотностей распределения......................................41

2.4 Апостериорные вероятности классов объектов................................43

2.5 Частные априорные модели разделяющей гиперплоскости............45

2.5.1 Классический метод опорных векторов: Частный случай нормальных априорных распределений компонент направляющего вектора с одинаковыми дисперсиями........................................................................45

2.5.2 Известные методы 1-norm SVM (Lasso SVM) и Doubly Regularized SVM (Elastic Net SVM)........................................................................................45

Байесовский принцип управления селективностью комбинирования признаков...................................................................................................48

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

3.2 Метод релевантных признаков с регулируемой селективностью....51

3.2.1 Параметрическое семейство априорных нормальных-гамма распределений компонент направляющего вектора со случайными дисперсиями..........51

3.2.2 Критерий обучения.....................................................................................53

3.2.3 Параметры гамма распределения: Управление селективностью..............53

3.2.4 Эквивалентный критерий обучения...........................................................58

3.2.5 Алгоритм обучения.....................................................................................58

3.3 Метод опорных признаков с регулируемой селективностью..........60

3.3.1 Параметрическое семейство составных априорных распределений для компонент направляющего вектора...........................................................60

3.3.2 Критерий обучения.....................................................................................61

3.3.3 Двойственная задача обучения..................................................................62

3.3.4 Итоговое решающее правило и опорные признаки...................................65

3.3.5 Зависимость множества опорных признаков от параметра селективности критерия обучения......................................................................................67

3.4 Теоретическое исследование механизма селективности и эффекта группировки методов релевантных и опорных признаков...............68

3.4.1 Механизм селективности отбора признаков.............................................68

3.4.2 Эффект группировки признаков................................................................72

3.5 Выбор оптимального уровня селективности: Метод скользящего контроля..............................................................................................75

Экспериментальное исследование методов релевантных и опорных признаков с управляемой селективностью..........................................76

4.1 Экспериментальное исследование на модельных данных...............76

4.1.1 Эксперимент А: Структура модельных данных и результаты..................76

4.1.2 Эксперимент В: Структура модельных данных и результаты..................84

4.1.3 Эксперимент С: Структура модельных данных и результаты..................86

4.1.4 Эксперимент D: Структура модельных данных и результаты..................88

4.2 Экспериментальное исследование на данных прикладной задачи.. 90

4.3 Обсуждение результатов экспериментов..........................................92

Заключение......................................................................................................95

Приложение: доказательства теорем..........................................................96

Теоремы главы 2.........................................................................................96

Доказательство теоремы 1.....................................................................................96

Доказательство теоремы 2.....................................................................................97

Теоремы главы 3.........................................................................................98

Доказательство теоремы 3.....................................................................................98

Доказательство теоремы 4.....................................................................................100

Доказательство теоремы 5.....................................................................................101

Доказательство теоремы 6.....................................................................................102

Доказательство теоремы 7.....................................................................................104

Доказательство леммы 1........................................................................................105

Доказательство леммы 2........................................................................................105

Доказательство теоремы 8.....................................................................................106

Доказательство теоремы 10...................................................................................107

Доказательство теоремы 11...................................................................................110

Доказательство теоремы 12...................................................................................113

Доказательство теоремы 13...................................................................................115

Доказательство теоремы 14...................................................................................116

Доказательство теоремы 15...................................................................................122

Литература......................................................................................................124

ВВЕДЕНИЕ

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

Актуальность. В диссертации исследуется и развивается наиболее популярный в современной литературе линейный подход к обучению распознаванию двух классов объектов реального мира со е Q, основанный на двух предположениях. Во-первых, предполагается, что всякий объект воспринимается компьютером через вектор его числовых признаков как точка в линейном пространстве х(со)еМ", размерность которого определяется числом признаков п. Во-вторых, предполагается, что для суждения о принадлежности объекта к одному из двух классов у - ±1 достаточно вычислить значение линейной решающей функции (decision function) d(x | a,b) = ат\ + b: R" —» E, знак которой непосредственно укажет класс объекта ятх + Ь^0. Очевидно, что линейная функция б/(х|а,6) определяет

дискриминантную гиперплоскость в R", а решение о классе объекта определяется тем, по какую сторону от нее окажется вектор признаков объекта х. Обучение линейного классификатора сводится к формированию значений параметров (а,Ь) на основе анализа конечной обучающей совокупности {(х^,^), j = l,...,N}.

Наиболее популярным методом обучения линейного классификатора по обучающей совокупности является метод опорных векторов {Support Vector Machine - SVM), разработанный Вапником В.Н. и Червоненкисом А.Я. [1], в основе которого лежит ими же ранее предложенный метод обобщенного портрета [2]. В основе метода лежит естественная идея выбирать ту гиперплоскость, которая в обучающей совокупности разделяет векторы признаков объектов разных классов с наибольшим зазором, дополнительно штрафуя возможные нарушения некоторыми объектами этого общего

«идеального» требования. В данной диссертации исследуется и развивается именно метод опорных векторов.

Следует заметить, что нет противоречия между традиционным признаковым способом погружения объектов распознавания в линейное пространство и беспризнаковым способом, предполагающим, что объекты реального мира со е Q могут быть представлены в компьютере только через некоторую числовую функцию парного отношения 5((о',со"). Такой подход предложен Р. Дьюиным [3] под названием реляционного дискриминантного анализа {Relational Discriminant Analysis) [4]. Идея заключается в том, чтобы интерпретировать значения этой функции между произвольным объектом соgQ и объектами из обучающей совокупности {с0,,...,с0д,} как вектор его вторичных признаков х(со) = (х,(со) = S(<d,,co),/ = 1,...,tV), и применить затем

обычный метод опорных векторов в М". Однако за такое использование функций парного сравнения объектов приходится платить большой размерностью пространства вторичных признаков, определяемой числом объектов в обучающей совокупности. Эта размерность многократно увеличится, если использовать несколько альтернативных функций парного сравнения [5].

Первая проблемная ситуация, определившая выбор темы данного диссертационного исследования, заключается в том, что при всей эффективности метод опорных векторов остается эвристическим по своей конструкции. С момента его создания в мировой литературе был предпринят ряд попыток снабдить его некоторой вероятностной интерпретацией [6,7]. Однако эти интерпретации оставались неполными, не позволяющими в полной мере использовать вероятностный аппарат для наделения чрезвычайно популярного метода опорных векторов принципиально новыми свойствами.

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

двух классов объектов в линейном признаковом пространстве, приводящая к обобщению метода опорных векторов и являющаяся теоретической основой для создания новых селективных методов обучения. Основная идея байесовской постановки заключается в построении системы вероятностных предположений о паре плотностей распределения объектов двух классов ф(х|_у=±1, а, 6), определяемой объективно существующей, но неизвестной гиперплоскостью (а, Ь) в линейном пространстве признаков, при некотором априорном предположении о ее случайном выборе При этом именно

структура первого семейства распределений определяет характерный принцип обучения по методу опорных векторов.

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

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

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

ограничимся рассмотрением именно методов отбора признаков объектов распознавания, независимо от того, каким способом эти признаки были получены.

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

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

На основе анализа мировой литературы в диссертации приняты четыре критерия для оценивания «качества» селективных свойств конкретного метода обучения:

а) эффективное подавление полностью шумовых попарно независимых признаков;

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

в) эффективное выделение группы информативных линейно независимых признаков;

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

По этим критериям в диссертации исследованы две наиболее популярных модификации метода опорных векторов, наделяющие его свойством отбора признаков - Lasso SVM (1-norm SVM) и Elastic Net SVM {Doubly Regularized SVM). Оба эти метода несколько разными средствами отбирают подмножество информативных признаков, число которых определяется структурными параметрами.

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

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

Один из новых методов, названный методом релевантных признаков {Relevance Feature Machine - RFM), не выделяя строгого подмножества информативных признаков, наделяет все признаки неотрицательными весами. Чем больше значение структурного параметра селективности, тем большее число весов приближаются к нулевым значениям, фактически исключая соответствующие признаки из принятия решения о классе объекта.

Другой предложенный метод, названный методом опорных признаков {Support Feature Machine - SFM), разбивает все множество признаков на три группы - полностью активные признаки, взвешенные признаки и полностью подавленные признаки. Можно считать, что метод SFM снабжает все признаки весами, но, в отличие от метода RFM, часть весов оказываются строгими единицами, часть принимает значения между единицей и нулем, а часть строго равны нулю.

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

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

пуклой оптимизации и основах байесовской теории принятия решений. Экспериментальное исследование проводилось с использованием программно-алгоритмического комплекса, разработанного автором в среде Matlab.

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