Байесовские методы опорных векторов для обучения распознаванию образов с управляемой селективностью отбора признаков тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Татарчук, Александр Игоревич

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

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

Содержание

Введение

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

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

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

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

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

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

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

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

1.2.2.1 1 -norm SVM (Lasso SVM)

1.2.2.2 Doubly Regularized SVM (Elastic Net SVM)

1.2.2.3 Elastic SCAD SVM

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

Введение диссертации (часть автореферата) на тему «Байесовские методы опорных векторов для обучения распознаванию образов с управляемой селективностью отбора признаков»

ВВЕДЕНИЕ

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

Актуальность. В диссертации исследуется и развивается наиболее популярный в современной литературе линейный подход к обучению распознаванию двух классов объектов реального мира со е 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.

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

Положения, выносимые на защиту:

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 «Методы выбора уровня сложности модели в задачах восстановления зависимостей между разнородными объектами реального мира».

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

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

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

• 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 статей в изданиях, входящих в список ВАК (выделены шрифтом):

1. Середин О.С., Моттль В.В., Татарчук А.И., Разин Н.А. Выпуклые селективные критерии метода релевантных векторов в пространстве парных отношений объектов распознавания. Известия ТулГУ, Серия Естественные науки. Тула: Изд-во ТулГУ, 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 9784-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 Sci-

ence, Vol. 5997. Springer-Verlag, Berlin \ Heidelberg, 2010, ISBN 978-3-642-12127-2_17, pp. 165-174.

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

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

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. В.В. Моттль, А.И. Татарчук, А.П. Елисеев Экспериментальное исследование методов многомодального распознавания образов с регулируемой селективностью. Известия Тульского государственного уни-

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

10. Tatarchuk A., Mottl V., Eliseyev A., Windridge 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 MultiKernel 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. Сулимова, B.B. Моттль, А.И. Татарчук. Автоматический выбор наиболее информативных фрагментов в задачах распознавания сигналов разной длительности. // Труды конференции «Интеллектуализация^обработки информации»-2006, Алушта, стр. 152-154.

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

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

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

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

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

В диссертации исследуется и развивается линейный подход к обучению распознаванию двух классов объектов сое О, >>(<») = +1, которые воспринимаются компьютером через векторы их числовых признаков х(со) = (х1(со),...,х„(со))еМ". Основополагающим принципом машинного обучения является гипотеза компактности, которая, в самой общей формулировке для задач обучения распознаванию образов, означает, что объекты одного и того же класса имеют большее сходство между собой чем объекты, принадлежащие разным классам. Такая гипотеза, в том или ином виде, неизбежно инкорпорирована в любой метод обучения, а их многообразие определяется разными смыслами, вкладываемыми исследователями в понятие сходство объектов. Самым распространённым математическим инструментом измерения сходства между объектами реального мира П, погруженными числовыми признаками х(со) е М" в конечномерное евклидовое пространство, является евклидова метрика

р(со',со") = р(х(со'),х(со")) = Р(х',х") =|| х' - х" ||= ((*' - х'У (х' - х")//2. (1)

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

направляющего вектора а е М" и действительного числа Ь е К определяет некоторую разделяющую гиперплоскость

ft(a,6) = {zeIT:arz + 6 = 0}. (2)

Гиперплоскость (2) делит все признаковое пространство М" на три части. Во-первых, это само множество Н{а,Ь), и во-вторых, два множества точек, находящихся по разные от гиперплоскости стороны. Принадлежность объекта х(со) е R" к одному из трех множеств определяет оценку его класса j)(co), при этом множество 7i{a,b), как правило, для простоты объединяется с множеством точек одного из классов.

Помимо гиперплоскости (2) одним из ключевых понятий линейного подхода является решающая функция {decision score function)

d{x\a,b) =—j.—щ или d{x\a,b) = aTx + b при ||а||=1. (3)

(а а)'

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

1 а г, •х

у = 1 О

у = -1

d{x | а, Ь)

о

О Н{а,Ь) = {г^{х\а,Ь) = 0}

О

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

С другой стороны, итоговое суждение о классе ;р(со) объекта определяется знаком решающей функции (3)

Г 1, если с?(х|а,6)>0,

1-1, если d{x\a,b) <0. { }

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

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

{(х7,^),у = 1,...,Аг}, х;бГ, ^=±1. (5)

Степень несоответствия значения решающей функции ¿/(х|а,Ь) для объекта х(со) е М" значению его целевой характеристики Хсо) выражается в виде функции потерь. В частности, нас далее будет интересовать функция потерь специального вида:

6СМ|8>

о,

ус1 > 8,

1

1--уй, уй < 8,

8

(6)

где з^ = >'(со) - истинный класс объекта, с1 = с1(х\а,Ь) - значение решающей функции (3), а е > 0 - параметр, который далее будем интерпретировать как зазор разделения двух классов объектов.

Функция потерь такого вида была впервые предложена Вапником В.Н. и Червоненкисом А.Я. и привела к методу обобщенного портрета [8], а затем к известному методу опорных векторов [9].

Такая функция потерь (рис. 2) имеет нулевой штраф 5(>>, с11 е) = 0 для объектов, удаленных от гиперплоскости на достаточное расстояние ус1> 8, и линейно растущий штраф Ь(у,с1\£) = \-ус1/г для объектов слишком близко приблизившихся к границе классов или попавших в область другого класса ус1 <г.

5СМ|е)

Рисунок 2. Вид функции потерь Ь(у,с! \ в).

В случае линейной разделимости обучающей выборки (5) естественно отдавать предпочтения такой решающей функции (3), для которой функция потерь (6) принимает нулевые значения для всех объектов обучающей выборки для как можно большего значения параметра е > 0. Другими словами, оптимальной гиперплоскостью является такая гиперплоскость, которая без ошибок разделяет обучающую выборку с наибольшим зазором е > О (рис. 3).

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

Такое требование эквивалентно невыпуклой оптимизационной задаче: 1/е2 шш(а, Ь, £), ага=1,

В случае линейно неразделимой обучающей выборки (5) ненулевые значения функции потерь (6) соответствуют объектам, нарушившим границу зазора, определяемой положением гиперплоскости (а, Ъ) и параметром функции потерь е > О (рис. 4).

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

В качестве критерия обучения естественно искать такую гиперплоскость, которая бы разделяла обучающую выборку на два класса, с одной стороны, с как можно большей величиной зазора е > 0, l/s2 —> min, а с другой, с как можно меньшей величиной суммарного штрафа для ошибочно классифицированных объектов обучающей выборки (5) = 1 - (l/s)^ (агх; +Ь),

^jj о/е)у (агх +i)<i^7 • Нетрудно убедиться, что баланс таких весьма эвристических

требований к процессу обучения выражается оптимизационным критерием 1 N

-7 + С У 8, —min(a,ö,5,s), ага=1,

е ^ 7 (8)

агх, +Ь) > 8(1-57), 5, >0, j = \,...,N, е > 0,

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

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

n

JSVM (a, b, б | С) = ara + 5у min(a еЕ", Ь еМ, 6 еRN ),

j=1 (9)

Этот простой и в то же время очень эффективный способ обучения распознаванию двух классов объектов путем решения задачи квадратичного программирования (минимизации квадратичной функции при линейных ограничениях) был предложен Вапником В.Н. [9] и получил за прошедшие годы огромную популярность как метод опорных векторов {Support Vector Machine). Его название объясняется тем, что, как показывает элементарное математическое исследование, направляющий вектор оптимальной

разделяющей гиперплоскости (а, 6,5) = arg min JSVM(b,b,b |С) согласно (9)

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

а = (10)

л

где X > 0, ] = 1,...,./У - решения двойственной задачи квадратичного программирования

n ^ n n

1 7=1 /=1

7=1

5>А=0' о < < С/2, у =

7=1

(11)

имеющих смысл множителей Лагранжа при ограничениях-неравенствах

^.(агх;+6)>1-5; в (9).

Согласно (10) направляющий вектор оптимальной разделяющей гиперплоскости и вся решающая функция

^Ед^о Ьу^х + Ь^О, (12)

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

Список литературы диссертационного исследования кандидат наук Татарчук, Александр Игоревич, 2014 год

ЛИТЕРАТУРА

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

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

3. R. Duin, Е. Pekalska, D. Ridder. Relational discriminant analysis. Pattern Recognition Letters, Vol. 20,1999, pp. 1175-1181.

4. M. Tomlinson, B. Love. When learning to classify by relations is easier than by features. Thinking & Reasonong, 2010, 16 (4), pp. 372-401.

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.

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

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

9. Vapnik V. Statistical Learning Theory. - NY.: J. Wiley, 1998. - 768 p.

10. John C. Piatt. Probabilistic Outputs for Support Vetor Mahines and Comparisons to Regularized Likelihood Methods. Advances in large margine classifiers, 1999, pp. 61-74, MIT Press.

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

12. Вапник В. H. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. —448 с.

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

14. Bradley P., Mangasarian O. Feature selection via concave minimization and support vector machines. In International Conference on Machine Learning. 1998.

15. Li Wang, Ji Zhu, Hui Zou. The doubly regularized support vector machine. Statistica Sinica, 01/2006; 16:589-615.

16. Zou, H., Hastie, Т.. Regularization and variable selection via the elastic net. J. Roy. Statist. Soc. Ser. В 67, 301-320, 2005.

17. Natalia Becker, Grischa Toedt, Peter Lichter, Axel Benner. Elastic SCAD as a novel penalization method for SVM classification tasks in high-dimensional data. BMC Bioinformatics, 2011.

18. Fan J, Li R: Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of American Statistical Association 2001, 96:13481360.

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

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

21. С.М. Bishop, М.Е. Tipping. Variational relevance vector machines. Proceedings of the 16th Conference on Uncertainty in Arti cial In-telligence. Morgan Kaufmann, 2000, pp. 46-53.

22. J.-B. Hiriart-Urruty, C. Lemarechal. Fundamentals of Convex Analysis. Springer, 2001.

23. Boyd S., Vandenberghe L. Convex Optimization. Cambridge University Press.

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