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

В диссертационной работе рассматривается проблема выбора признаков в задаче обучения классификации. Предлагается минимаксный подход к одновременному построению оптимального решающего правила и оптимального подпространства признаков для классификации. Подход применяется к стандартной задаче метода опорных векторов (support vector machine, SYM) и приводит к минимаксной задаче оптимизации модифицированного критерия задачи SVM. Устанавливаются математические свойства решений минимаксной задачи. Предлагаются алгоритмы решения минимаксной задачи. Описываются численные эксперименты, но тестированию предложенного подхода в задачах классификации. Демонстрируется применение предложенного минимаксного подхода к задаче одновременного построения SVM регрессии и оптимального подпространства признаков.

Актуальность исследования.

Проблема обучения классификации является одной из основных задач прикладной математики. В рамках этой проблемы существует задача выбора из исходного множества признаков подмножества «полезных» для обучения признаков. Определение множества информативных признаков рассматривалось в качестве одной из главных задач с самого начала изучения проблемы обучения классификации. Так, в одной из самых первых работ по распознаванию образов [9] М. М. Бонгард рассматривал построение множества «полезных» признаков в качестве необходимой компоненты в алгоритмах обучения классификации.

С прикладной точки зрения необходимость выбора признаков диктуется тем. что обрабатываемые алгоритмом обучения данные часто содержат избыточные или не имеющие отношения к изучаемым явлениям признаки, которые могут значительно снижать качество решающего правила распознавания. Например, вероятность ошибки распознавания решающего правила, построенного методом ЯУМ по данным с множеством информативных признаков может сильно возрасти при добавлении значений не информативных признаков в обучающие данные. Так, в работе [87] приводится пример, когда добавление к исходным данных нормально распределенных шумовых признаков увеличивает долю ошибочных классификаций с 3% до 50%.

Наряду с задачей выбора признаков также выделяют задачу извлечения признаков. В задаче извлечения признаков из существующих признаков могут конструироваться новые признаки. При этом обычно предполагается, что количество новых признаков не должно превышать количества исходных. При постановке задачи обучения объекты распознавания представляются векторами пространства К'1, где п — количество признаков, характеризующих объект. Таким образом, при решении задачи выбора или извлечения признаков стремятся сократить размерность исходного пространства. Задачей сокращения размерности будем называть как задачу выбора, так и задачу извлечения признаков. В диссертации содержится обзор классических методов извлечения признаков. Одним из представителей этих методов является метод главных компонент. Данный метод хорошо изучен и ему посвящена обширная литература. Основные усилия современных научных исследований задачи сокращения размерности сосредоточены на разработке новых методов решения задач выбора признаков.

Современные методы решения задач выбора признаков можно разделить на три группы: «фильтр», «интерфейсные» и «встроенные» методы, см. с. 44. Эти три группы характеризуются разной степенью связи между собственно процессом выбора признаков и алгоритмом обучения классификации. Методы двух первых групп не учитывают специфики конкретного алгоритма обучения. Третья группа состоит из «встроенных» методов, в которых алгоритм распознавания устроен таким образом, что он одновременно осуществляет выбор признаков и решает задачу обучения в пространстве этих признаков.

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

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

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

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

Предлагаемые в диссертации методы относятся именно к этой новой группе методов отбора полезных признаков в задаче обучения классификации. Автор ограничил рассмотрение проблемы рамками метода опорных векторов (БУМ) при построении линейных оптимальных решающих правил классификации на два класса.

Выбор метода опорных векторов диктовался следующими соображениями:

1) Среди огромного разнообразия современных подходов к распознаванию метод опорных векторов на протяжении последних 15 лет общепризнан как один из самых совершенных.

2) Он имеет простую математическую постановку задачи и наиболее глубокое теоретическое обоснование, позволяющее легко сформулировать, что значит оценка информативности подмножества признаков.

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

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

Стандартная процедура оценки качества решающего правила классификации, основанная на вычислении ошибок классификации на специальном тестовом множестве, позволяет строго статистически оценивать правила, построенные на разных подмножествах признаков. Поэтому быстрые методы, основанные на построении опорных векторов, позволяют прямым перебором решать задачу выбора признаков при малой (порядка 5−10) размерности пространства классификации. Для случая большой размерности предложены эвристические процедуры существенно использующие специфику классификаторов, конструируемых на базе вычисления опорных векторов [60]. И вместе с тем, поскольку в методе опорных векторов формулируется и точно решается оптимизационная задача в пространстве исходных признаков, то естественно попытаться найти обобщение имеющейся формулировки, которая бы обеспечивала поиск оптимального правила классификации при рассмотрении всех возможных подмножеств признаков. Примеры таких обобщений задачи БУМ можно найти в работах [37, 87]. Изучение этих работ привело нас к повой формулировке, которая является не только более эффективной с вычислительной точки зрения, но и дает более глубокое теоретическое понимание проблемы и, как следствие, новые возможности интерпретации результатов на практике.

Цели и задачи исследования.

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

1. Анализ современного состояния проблемы выбора признаков.

2. Разработка новой формулировки задачи выбора признаков в рамках метода опорных векторов.

3. Анализ свойств решений поставленной задачи выбора признаков.

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

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

6. Реализация алгоритма решения задачи выбора признаков па ЭВМ, проведение и анализ результатов экспериментов.

Объект и предмет исследования.

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

Методологическая и теоретическая основа исследования.

Теоретическую основу диссертации составили работы отечественных и зарубежных авторов в теории выпуклого анализа, оптимизации, прикладной статистики и распознавания образов. В диссертации использовались методы квадратичной оптимизации, недифференцируемой оптимизации. Необходимо привести имена советских и российских ученых, которые внесли значительный вклад в развитие методологической и теоретической базы исследования, выполненного в диссертации. В области прикладной статистики и теории распознавания образов — Айвазян С. А., Айзерман М. А., Браверман Э. М., Вапник В. Н., Журавлев Ю. И. Моттль В. В, Мучник И. Б. Розоноэр Л.И. Червоненкис А. Я. В области теории выпуклого анализа и методов оптимизации — Антипин А. С, Васильев JI. B, Гольштейн Е. Г., Демьянов В. Ф., Евтушенко Ю. Г., Еремин И. И., Корпелевич Г. М., Малозсмов В. Н., Поляк Б. Т., Шор Н.З.

Информационная база исследования.

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

1. Научные источники в виде книг, статей из журналов, научных отчетов, материалов конференций и семинаров.

2. Научные материалы расположенные в сети Интернет.

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

Научная новизна исследования.

В диссертации предложена оригинальная формулировка задачи выбора признаков, которая построена на модификации стандартного критерия метода опорных векторов. Математически задача выбора признаков поставлена в виде дискретной оптимизационной задачи, в которой булевой переменной zi соответствует наличие или отсутствие в подмножестве информативных признаков ¿—того признака. Задача дискретной оптимизации погружается в непрерывную невыпуклую задачу оптимизации, в которой переменная Zi принимает значения из интервала [0- 1]. Показано, что невыпуклая задача может быть заменена на эквивалентную задачу на поиск минимакса выпукло-вогнутой функции.

Главный научный результат диссертации, состои т в том, что доказана теорема о свойстве «целочисленности» оптимальных значений переменных в минимаксной задаче. Также, доказано существование подмножества седло-вых решений среди множества решений минимаксной задачи.

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

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

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

Практическая значимость работы.

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

Аппробация результатов работы.

Основные результаты работы докладывались на 13-й Всероссийской конференции «Математические методы распознавания образов» в 2007 г. и содержатся в публикациях [17, 18, 19, 53, 54, 55].

Структура диссертации.

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

ЗАКЛЮЧЕНИЕ

.

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

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

Исследованы свойства решений непрерывной минимаксной задачи оптимизации и доказано свойство «целочисленности» решений.

Предложено два различных подхода к оптимизации целевой функции: алгоритм недифференцируемой выпуклой оптимизации и метод поиска седло-вой точки выпукло-вогнутой функции.

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

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

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

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