Минимаксный подход к построению оптимального классификатора методом SVM с одновременным выбором оптимального подпространства признаков тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

004603142

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

Гончаров Юрий Владимирович

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

01.01.09 — Дискретная математика и математическая кибернетика

Автореферат

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

- з июн 2010

Москва - 2010

004603142

Работа выполнена в Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН

Научный руководитель: доктор физико-математических наук,

профессор А. С. Антипин

Официальные оппоненты: доктор физико-математических наук

А. М. Райгородский

кандидат физико-математических наук А. Я. Червоненкис

Ведущая организация: Учреждение Российской академии наук

Институт проблем передачи информации им. А. А. Харкевича РАН

Защита состоится 2010 г. в -/-5 ■ (-'0 часов на заседании

диссертационного совета Д.002.17.02 при Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН по адресу: 119333, г.Москва, ул.Вавилова, 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

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

Ученый секретарь Ц^^Сс^Л доктор физико-математических наук, диссертационного совета профессор В. В. Рязанов

Общая характеристика работы

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

Актуальность темы. Определение множества информативных признаков рассматривалось в качестве одной из главных задач с самого начала изучения проблемы обучения классификации. Так, в одной из самых первых работ по распознаванию образов1 построение множества «полезных» признаков рассматривалось в качестве необходимой компоненты в алгоритмах обучения классификации. С прикладной точки зрения необходимость выбора признаков диктуется тем, что обучающие данные часто содержат избыточные или не имеющие отношения к изучаемым явлениям признаки, которые могут значительно снизить качество распознавания. Наряду с задачей выбора признаков также выделяют задачу извлечения признаков, в которой из существующих признаков могут конструироваться новые признаки. При постановке задачи обучения объекты распознавания представляются векторами пространства R", где п — количество признаков, характеризующих объект. Таким образом, при решении задачи выбора или извлечения признаков стремят-

1Бонгард М.М. Проблема узнавания. М.: Наука, 1967.

ся сократить размерность пространства. Предлагаемый в диссертации метод относится к группе «встроенных» методов, в которых признаки выбираются одновременно с процессом решения задачи обучения классификации. «Встроенные» методы представляют наибольший интерес в виду того, что эти методы позволяют учитывать особенности алгоритма обучения в процессе поиска подмножества информативных признаков. Среди огромного разнообразия современных подходов к распознаванию метод SVM на протяжении последних 15 лет общепризнан как один из самых совершенных. Следовательно, разработка «встроенных» методов выбора признаков на основе SVM представляется актуальной задачей. Поскольку в методе опорных векторов формулируется и точно решается оптимизационная задача в пространстве исходных признаков, то естественно попытаться найти обобщение имеющейся формулировки, которая бы обеспечивала поиск оптимального правила классификации при рассмотрении всех возможных подмножеств признаков. Существует несколько примеров таких обобщений задачи SVM. Так, в работе В.Н. Вапника и др.2 предложена постановка задачи выбора признаков, метод решения которой сводится к минимизации дифференцируемой невыпуклой функции при ограничениях. В другой работе рассматривается постановка в форме задачи многокритериальной оптимизации3, для которой предлагается приближенный алгоритм ее решения. В обеих постановках булевые переменные, которые отвечают за выбор подмножества признаков, заменяются на непрерывные переменные z; со значениями из отрезка [0,1].

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

2Weston, J., Mukherjee S., Chapelle О., PontU M., Poggio T.,Vapnik V. Feature Selection for SVMs // Advances in Neural bformation Processing Systems. 2000. V.13. P.668-674.

3Bi J. Multi-objective programming in SVMs // Proc. of 20th Intern.Conf. on Machine Learning. 2003. P.35-42.

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

В диссертации представлен подход к разрешению указанных проблемных ситуаций. Задача выбора признаков ставится на основе модификации оптимизационного критерия метода БУМ. В постановке используются непрерывные переменные € [0,1], которые отвечают за выбор признаков. Получаемая задача оптимизации имеет выпуклую целевую функцию. Анализируются свойства решений задачи оптимизации и описываются условия, при которых значения переменных г, принимают значения 0 или 1.

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

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

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

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

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

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

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

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

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

Научная новизна. В диссертации предложена оригинальная формулировка задачи выбора признаков, которая построена на модификации критерия метода опорных векторов. Математически задача выбора признаков поставлена в виде оптимизационной задачи, в которой булевой переменной % соответствует наличие или отсутствие в подмножестве информативных признаков г-го признака. Остальные переменные в задаче оптимизации отвечают за поиск решающей функции распознавания. Задача дискретной, по переменным Zi, оптимизации погружается в непрерывную невыпуклую задачу, в которой переменные Z{ принимают значения из интервала [0,1]. Показано, что невыпуклая задача может быть заменена на эквивалентную задачу на поиск минимакса выпукло-вогнутой функции. Доказана теорема о выпуклости по переменным Z{ минимизируемой функции. Главным научным результатом диссертации является теорема, характеризующая условия, при которых оптимальные значения переменных Zi в минимаксной задаче принимают значения 0 или 1. Показано, что среди множества решений минимаксной задачи существуют решения, являющиеся седловыми точками целевой функции минимаксной задачи. Для решения задачи на минимакс предложено использовать алгоритм поиска седловой точки выпукло-вогнутой функции. Для поиска седловой точки применен дискретный вариант экстраградиентного метода4, для которого доказана сходимость и проведена оценка параметра, задающего величину шага в алгоритме. В экстраградиентном методе для вы-

4Antipin A.S. From optima to equilibria // Proceedings of Institute for Systems Analysis. «Dynamics of non-homogeneous systems». V.3. Moscow. 2000. P.35-64.

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

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

Апробация работы. Основные результаты работы докладывались на 13-й Всероссийской конференции «Математические методы распознавания образов» в 2007г.

Публикации автора. Основные результаты диссертации опубликованы в работах [1-6]. См. в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы и трех приложений. Список литературы содержит 89 наименований. Диссертация изложена на 174 страницах, содержит 21 рисунок и восемь таблиц.

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

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

Задача обучения классификации состоит в поиске решающего правила, согласно которому любой вектор х £ R" относится к одному из двух классов. Правило может задаваться в виде решающей функции /. При f{x) — 1 вектор X относится к первому классу, при f(x) = —1 — ко второму. Задано множество допустимых решающих функций {fa(x), а 6 П}, где П — некоторое множество. Поиск оптимальной функции fa(x) ведется по обучающей выборке конечной длины (®i, г/i), (2:2,1/2), ••• (xi>yi)> где x¡ € Rn,yi £ {1;—1},г = 1,2,...,/. Элемент обучающей выборки состоит из вектора x¿ и у,- — признака принадлежности одному из двух классов.

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

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

Алгоритм метода опорных векторов для задачи классификации двух линейно-разделимых классов известен уже более 35 лет и назван в книге В.Н. Вапника и А.Я. Червоненкиса5 методом обобщенного портрета. Почти 20 лет спустя было предложено обобщение алгоритма метода опорных векторов для задачи классификации на случай линейно неразделимых классов6. В англоязычной литературе метод имеет название «SVM (support vector machine)». Изложение метода опорных векторов в диссертации следует книге В.Н. Вапника.7 «Емкость» множества решающих функций {fa(x), а е fi} характеризуется величиной VC-размерности, которую будем обозначать че-

'Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.: Наука, 1974.

"Cortes е., Vapnik V. Support Vector Networks // Machine Learning. 1995. V.20. №3. P.273-297.

7Vapnik V.N. The Nature of Statistical Learning Theory, Second Edition. New York: Springer, 2000.

рез h. По обучающей выборке вычисляется величина эмпирического риска функции fa(x):

Оценка сверху для вероятности ошибки распознавания решающим правилом fQ(x) имеет вид монотонно возрастающей функции g(h, Remp(a)) по Л. и Rempi®)- При поиске оптимального решающего правила /а(г) в методе опорных векторов стремятся минимизировать величину оценки g(h, Remp(a)). Для этого стараются минимизировать взаимно противоречивые VC-размерность и эмпирический риск.

Встречающиеся далее обозначения нормы вектора и матрицы подразумевают соответственно стандартную евклидову норму вектора и подчиненную ей матричную норму. Через (zi, Х2) обозначим скалярное произведение векторов Х\ и 12- Пусть дана гиперплоскость {w*, х) + Ъ* ~ 0, |Jw*J| = 1 и число Д > 0. Рассмотрим следующее правило:

В случае выполнения неравенств -Д < {1и*,Х{) 4- Ь* < Д считается, что решающее правило классифицирует элемент обучающей выборки Х{ с ошибкой.

В.Н. Вапником и А.Я. Червоненкисом получена верхняя оценка величины УС-размерности множества решающих правил (1):

где К — радиус шара, в котором лежат векторы х\ [а] — наименьшее целое число большее или равное а. Для минимизации величины Л предлагается минимизировать правую часть оценки (2).

Метод опорных векторов сводится к решению задачи квадратичного про-

m =

1 , если (w*,x) + b* > Д, -1 , если (tu*, х) + Ь* < -Д.

(1)

граммирования.

Уг{(ю,Х{)+Ь) > 1-6и 6(> 0, С>0, I — 1,2,. . .,1 .

Минимизация первого члена функционала (3) ведет к максимизации величины Д в оценке (2). Минимизация второго члена функционала (3) ведет к минимизации эмпирического риска Детр(а). В оценке (2) участвует величина размерности п, которую необходимо уменьшать для минимизации оценки УС-размерности. Однако, в функционале задачи опорных векторов (3) нет члена, который бы побуждал уменьшать величину размерности п. В диссертации предлагается критерий оптимизации, который штрафует также и величину размерности п.

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

Дискретная постановка задачи выбора признаков.

Пусть I = {1;2;...;п — 1;п} — множество координат вектора V е Я", С} С I — подмножество координат. Обозначим через V® вектор с множеством координат <5, = ы, г е Например, для I = {1;2;3;4; 5}, г» = (9; 8; 4; 7; 6)Г, <2 = {2; 3; 5}, вектор V<3 будет равен

(8;4;6)Г

Задача выбора признаков ставится в форме модификации задачи БУМ

<4>

¿«>0, » = 1,2,...,/, А > 0.

Первые два члена функционала в (4) отвечают за поиск оптимальной гиперплоскости в пространстве признаков, задаваемом С). Третий член — шраф на мощность подмножества признаков. Коэффициент А регулирует величину штрафа. Задача (4) имеет комбинаторный характер по <3. Различным подмножествам С} отвечают различные подпространства признаков. Однако, вид целевой функции позволяет погрузить задачи с различными <5 в исходное пространство признаков. Рассмотрим сначала следующую задачу:

^(¿«^¿^¿Л (5)

\ «=1 )

У{ ^¿С ^Л^/Щ + ^ > 1 - (6)

5г > 0, » = 1,2,...,/, Л> 0, зу £ {0; 1}, з = 1,2.......

здесь х\ — координата з вектора Хг, ш,- — координата ] вектора ги. Эта задача содержит булевые переменные г у Значение г^ — 1 означает, что признак с индексом ] выбран, значение г,- = 0 означает, что признак удален.

Следующее предложение утверждает, что задачи (4) и (5),(6) эквивалентны в том смысле, что из решения одной задачи получаем решение другой. Предложение 1 Пусть (д,ги®,Ь,6 — решение задачи (4), значения г, ги в задаче (5), (6) вычисляются по следующему правилу:

г^ — 1, = , если з е С X] = 0, т, = 0 , если j £ <3,

тогда г,т,Ь,6 — решение задачи (5),(6).

Пусть г,ги,Ь,6 — решение задачи (5),(6), значения вычисляются

по следующему правилу:

<2 = № = = 1,2,...,п>,= €

тогда (¿¡ь)®^^ — решение задачи (4).

Непрерывная постановка задачи выбора признаков. В задаче (5),(6) переменные могут принимать значения 0 или 1. Задача оптимизации с целочисленными переменными является трудной для решения с вычислительной точки зрения. Предлагается ослабить условие на целочисленность и разрешить переменным г^ принимать значения из отрезка [0,1]. Таким образом, приходим к непрерывному аналогу задачи (5),(6):

' ' ' \ 1=1 3=1 /

п

+ (8)

.7=1

й>0, г = 1,2,...,/, Л>0, %е[0,1], ; = 1,2,... ,тг.

Пусть г*,ю*,Ь*,5* — решение задачи (7),(8). Для классификации вектора х вычисляется следующая величина:

При Б > О вектор х относится к первому классу, в противном случае ко второму. Целевая функция задачи выбора признаков (7),(8) отличается от целевой функции БУМ наличием штрафа А г^ на подмножество выбранных признаков. Присутствие в ограничениях (8) операции взятия квадратного корня у/Щ необходимо для того, чтобы целевая фунция двойственной к (7),(8) задачи была линейной по г. Задача (7),(8) при фиксированном г фактически

является задачей БУМ, в которой элементы обучающей выборки предварительно шкалируются с помощью вектора 2 следующим способом:

х\ ► I — 1,2,... ,1, ] = 1,2,..., п.

Можно считать, что процедура решения задачи (7),(8) состоит из поиска оптимальной шкалы признаков и оптимальной разделяющей гиперплоскости в новом шкалированном пространстве. Алгоритм, который решает задачу (7),(8), будем называть алгоритмом выбора признаков. Задача (7),(8) имеет невыпуклые ограничения по совокупности всех переменных г, го, Ь, 5.

Выпуклая минимаксная постановка задачи выбора признаков.

Задача (7),(8) может быть преобразована в эквивалентную задачу последовательной минимизации с выпуклой структурой. Рассмотрим задачу:

юш^(г), (9)

где значение ф(г) получается в результате решения следующей задачи:

' ' \ г=1 ¿=1 /

■ф{г) = шш ( -И2 + С £ ** + А £ Ъ 1 > (10)

Уг У/% + ^ - 1 ~

6г> 0, г = 1,2,...,/, А > 0. Задача (10) может быть записана в двойственной форме

ф(г) = тах (V ^ - \ V V (у,ук X) ) + А ]£ гз ) > (п)

А \г=1 г 1 1 V ,=1 / /

I

]ГЛ^ = 0, О < Л, < С, г = 1 ,...,<.

¿=1

Теорема 1 Функция ф(г) в задаче (11) является выпуклой.

Используя двойственное представление (11) для задачу (9), (10) можно представить в форме минимаксной задачи (9), (11) и записать в следующем виде:

min max Liz, Л), (12)

zez лел v . v '

i 1 1 1 f n \ n a) = xi - о Л (yiVk£z^xk XiXk+АЛzi> ■ i=1 ¿=1 k=l \ j=1 / j=1

Z = {z\0<zj<l,j = l,2,...,n} , i

Л = {A| Aiift = 0,0 < A< < C, * = 1,2,..., i} .

¿=i

Полученный результат о выпуклости функции ip(z) в задаче (11) позволяет построить алгоритм решения задачи (9),(11) одним из методов выпуклой недифференцируемой оптимизации. В приложении В диссертации описан алгоритм решения задачи (9),(11) на основе метода проекции субградиента Б.Т. Поляка.

Седловая постановка задачи выбора признаков. Заметим, что L(z, Л) выпукло-вогнутая функция, т.е. выпуклая по z при фиксированном значении Л и вогнутая по Л при фиксированном г.

Рассмотрим задачу поиска седловой точки (z*,X*) G Z х А:

L(z*, А) < L(z*, X♦) < L{z, X*) 4z G Z, VA € A. (13)

Для седловой точки справедливо следующее равенство:

minmaxL(z, А) = max min ¿(г, А) = L(z*, А*). (14)

zeZ Дел лел zez

Опираясь на это равенство, мы можем заменить задачу поиска минимакса на задачу поиска седловой точки. Множество седловых точек является подмножеством минимаксных решений.

Основным научным результатом диссертации служит следующая теорема «целочисленности», которая утверждает существование седловой точки у функции L(z, А) и показывает условия, при которых координаты оптимального z имеют целочисленные значения 0 или 1.

Теорема 2 1. Существует седловая точка (z*,A*) в задаче (13) и справедливы следующие равенства:

z* — arg min max L(z, А), A* — arg max min Liz, A). zez АеЛ 4 " 0 Дел zeZ v ' '

2. Если в седловой точке выполнено неравенство i I

Y1 >2А , то z* = 1.

t=l k=1

Если в седловой точке выполнено неравенство i I

ЕЕутФЛК <2А , то Zj = 0. ¿=1 fc=i

Если 0 < Zj < 1, то имеет место равенство

i I

¿=1 k=l

Может показаться, что в случае равенства i i

i=i *=i

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

Справедлива аналогичная теорема о «целочисленности» решений минимаксной задачи (12).

Теорема 3 Пусть (г°,А°) — решение минимаксной задачи (12), (г*, А*) — седловая точка задачи (13), тогда справедливы следующие импликации. i I

¡=1 k=1

!=1 Ь=1

I I

о < < 1 ^ =•

1=1 Л=1

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

равенство = 0.

Предложение 2 Пусть величина А в задаче (12) вычислена по формуле

где е — произвольное положительное число и (20, Л°) — решение задачи (12). Тогда выполняется равенство г® = 0.

С другой стороны, в диссертации приведен пример, в котором уменьшение параметра А в задаче (12) не приводит к решению с положительным значением ,7-той координаты вектора г.

Алгоритм поиска седловой точки. В этом разделе диссертации описывается алгоритм поиска седловой точки для выпукло-вогнутой фунции, которая удовлетворяет некоторым условиям на функцию Ь(г,Х). Затем показывается, что функция Л) в задаче (13) удовлетворяет этим условиям.

Пусть выпукло-вогнутая функция Ь(г, А) определена на декартовом произведении выпуклых замкнутых множеств 2 х Л и для некоторых констант Мг > 0, Мг > 0, Мз > 0 удовлетворяет следующим неравенствам:

получить решение (г°, А0), в котором для произвольного у будет выполнено

Л б Л , е > 0,

1

L(z + h,X)-L(z,X)-(^(z,X),h

(16)

+ (17)

Пусть 7Г2,7Гл ~ операторы проекции на множества Я и Л, т.е. 7Гг(г) — это проекция точки г на множество £ и, аналогично, 7Гд(Л) — проекция точки А на множество А.

Рассмотрим следующий алгоритм, каждая итерация которого состоит из следующих 3 шагов:

z' = „(¿-ag^A*)),

\Ш = nA(xk + a^(zk,X

(18)

Jfc+1

7TZ Z

■ а

дь

dz

(zk,Xk+1

В диссертации доказывается теорема о сходимости алгоритма (18). Теорема 4 Пусть L{z, А) — выпукло-вогнутая функция на Z х А, множества Z и А - выпуклые, замкнутые, L{z, А) удовлетворяет неравенствам (15) —(17), выполнены неравенства 0 < а < min ^щ, ■

Тогда для любой начальной точки z° € Z, А0 6 Л последовательность

— 1,2,..., вычисляемая по формулам (18), сходится к (z*,A*) — седловой точке функции L(z, А).

Теорема 4 может быть распространена на случай, когда неравенство (16) выполняется при Мг = 0. В этом случае в качестве константы Липшица в неравенстве (16) можно также взять М% = е, где е > 0 — произвольно малая величина. Для достаточно малой величины е условие на величину параметра шага а в теореме 4 принимает вид 0 < а < ■ Будем пользовать-

ся последним условием на величину а при Мг = 0.

Пусть определены матрицы

С = {дц = уМ|» = 1,2,..., I,з = 1,2,..., га}, (19)

& = № = Л = 1,2, • • •, 1},3 = 1,2,..., п, (20)

тогда константы Мх, М2 и М3 в (15)—(17) для Ь(г, X) из (13) вычисляются по следующим формулам:

п

М1 = т2, м2 = о, м3 = сг^1|^||.

Быстрое вычисление проекций. В алгоритме (18) требуется вычислять проекции точек на множества ЯиЛ. Обычно, если вычисляется проекция точки £о на множество 5, задаваемое системой линейных неравенств, то решается задача квадратичного программирования:

ттЦх - гсоЦ2,^ € 5.

(21)

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

грг = пг{г), Ъ = {0 < г} < 1,3 = 1,2,... ,тг} ,г € Я" и вычисляется по формуле

л* _

0, % < 0,

0 < % < 1, = 1,2, ...,п,

1, ц > 1.

(22)

Проекция точки Л на множество Л имеет вид

= 7ГЛ (А), Л= 0<А^<С,; = 1,2,А £

Af:

и вычисляется приближенно в результате последовательных проекций на куб {О < Xj < С,] — 1,...,/} и на подпространство, задаваемое равенством

Проекция точки А на куб {0 < А^- < С, з = 1,2,..., /} вычисляется по формуле

г

О, % < О,

А;, О <А; < С, ¿ = 1,2.....1, (23)

С, А, > С.

<

Проекция точки Хо 6 IIм на гиперплоскость стх — 0, с € ДЛ/ вычисляется по следующей формуле:

х£ = х0 -^с. (24)

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

Пусть А, В — выпуклые замкнутые подмножества пространства Я' и гбЕ'. Пусть для к > 1 определены последовательности

Ьо = х, Ро = 1о = О,

а* = тгл(Ь*-1+Р*-1). рк = Ьк-1 +Рк-\ - а*, (25)

Ьк = пв(а>к + Чк-1), Як = ак + Як-1 ~

Последовательности ак, Ьк сходятся к ~паг\в{%) — проекции точки х на пересечение множеств АпВ.8 В том случае, когда множество А является аффинным подпространством (сдвигом подпространства на вектор), то в формулах (25)

8Bauschke H.H., Borwein J.M. Dykstra'a Alternating Projection Algorithm for Two Sets // J. Approximat. Theory. 1994. V.79. №3. P.418-443.

можно положить рк = 0 для всех к.9 Таким образом, алгоритм нахождения проекции точки х на множество Л = {]T)j=i Xjyj = 0,0 < Xj < C,j — 1,..., /} имеет следующий вид:

bo =х, q0 = О,

ак = nA(h-\), (26)

Ък = пв(ак + qk-i), Як = ак + Чк~i ~ fo,

где множества А и В задаются в виде А — ^jVj = 0}>

В = {0 < Aj < С, j = 1,..., 1} и проекции на множества А я В вычисляются по формулам (24) и (23).

В пятой главе диссертации описаны результаты численных экспериментов с разработанным алгоритмом выбора признаков. Эксперименты проводились на искусственных данных, данных для распознавания гласных звуков английского языка и медицинских данных для диагностики болезни. Результаты экспериментов показывают, что алгоритм способен одновременно удалять признаки и улучшать качество распознавания по сравнению с качеством распознавания SVM. В некоторых экспериментах алгоритм позволяет удалять признаки ценой незначительного ухудшения качества распознавания по сравнению с SVM. Проведены эксперименты по анализу вычислительной эффективности алгоритма вычисления проекции Дейкстры по сравнению с алгоритмом квадратичного программирования для использования в алгоритме выбора признаков. Общее время работы алгоритма выбора признаков уменьшается в 1.2 — 2.2 раза за счет использования алгоритма Дейкстры.

В приложении А дается доказательство предложения 1 (см. с. 11) об эквивалентности двух постановок задачи выбора признаков.

В приложении В описан алгоритм решения минимаксной задачи (12) методом недифференцируемой оптимизации субградиентного типа.

В приложении С демонстрируется применение разработанного подхода

'Gafflce N., Matbar R. A cyclic projection algorithm via duality // Metrika. 1989. V.36. №1. P.29-54.

к выбору признаков в задаче построения SVM регрессии. Описываются постановка и математические свойства задачи, алгоритм решения и результат численного эксперимента с данными анализа ингибиторных свойств производных триазина от параметров замещения молекулы триазина.10 Результаты эксперимента показывают, что возможно удалить 46 из 60 -ти исходных независимых переменных регрессии без потери качества предсказания.

В заключение автор выражает глубокую благодарность своему научному руководителю А. С. Антипину, учителю и научному консультанту диссертации И.Б. Мучнику, другу и коллеге по научной работе J1.B. Шварцеру за постоянное внимание и помощь в работе.

Список публикаций по теме диссертации

1. Гончаров Ю.В., Мучник И.Б., Шварцер JI.B. Алгоритм выбора признаков в задаче обучения классификации методом опорных векторов -Докл. 13-й всероссийской конф. Математические методы распознавания образов (ММРО-13). -М: ООО «МАКС Пресс». - 2007. - 700 с.

2. Гончаров Ю.В., Мучник И.Б., Шварцер JI.B. Алгоритм выбора признаков в задаче обучения классификации методом опорных векторов // Ж. вычисл. матем. и матем. физ. -2008. - Т.48. №.7. - С.1318-1336.

3. Гончаров Ю.В. Минимаксная задача выбора признаков для построения классификатора методом опорных векторов // Ж. вычисл. матем. и матем. физ. -2010. - Т.50. №.5. - С.967-976.

4. Goncharov Y., Muchnik I., Shvartser L. Simultaneous feature selection and margin maximization using saddle point approach // DIMACS Technical Report 2004. - №2004-08. - P.54.

5. Goncharov Y., Muchnik I., Shvartser L. Saddle point feature selection in SVM regression // DIMACS Technical Report 2007. - №2007-08. - P.15.

6. Goncharov Y., Muchnik I., Shvartser L. Saddle point feature selection in SVM classification // DIMACS Technical Report 2007. - №2007-16. - P.23.

10King R., Hirst J,, Sternberg M. Comparison of artificial intelligence methods for modeling pharmaceutical QSARS // Applied Artificial Intelligence: An International Journal. 1995. V.9. Issue 2. P.213-233.

Отпечатано в ООО «Компания Спутник+» ПД № 1-00007 от 25.09.2000 г. Подписано в печать 23.04.2010 Тираж 100 экз. Усл. п.л. 1,31 Печать авторефератов (495)730-47-74,778-45-60

Введение

ГЛАВА 1. Проблема сокращения размерности в задаче обучения классификации

1.1 Постановка задачи обучения классификации.

1.2 Задача сокращения размерности.

1.3 Методы извлечения признаков.

1.3.1 Метод главных компонент

1.3.2 Метод центроидных компонент.

1.3.3 Методы экстремальной группировки параметров

ГЛАВА 2. Современное состояние проблемы выбора признаков в задачах классификации

2.1 Основные постановки задачи выбора признаков.

2.1.1 Виды оценок качества подмножества признаков.

2.2 Методы оценки вероятности ошибки распознавания.

2.2.1 Resubstitution метод.

2.2.2 Holdout метод

2.2.3 Cross-validation метод.

2.2.4 Jackknife метод.

2.2.5 Bootstrap метод

2.3 Вычислительная сложность задачи выбора признаков.

2.4 Обзор алгоритмов выбора признаков

2.4.1 Организация пространства поиска.

2.4.2 Способ движения в пространстве поиска.

2.4.3 Описание основных алгоритмов выбора признаков.

ГЛАВА 3. Алгоритмы выбора признаков на основе метода опорных векторов

3.1 Метод опорных векторов.

3.2 Алгоритмы выбора признаков на основе 8УМ

3.2.1 Градиентный алгоритм Вапника и др.

3.2.2 Алгоритм выбора признаков для задачи БУМ в многокритериальной постановке.

ГЛАВА 4. Минимаксный подход к построению оп тимального классификатора методом БУМ с одновременным выбором оптимального подпространства признаков.

4.1 Дискретная постановка задачи выбора признаков.

4.2 Непрерывная постановка задачи выбора признаков.

4.3 Выпуклая минимаксная постановка задачи выбора признаков

4.4 Седловая постановка задачи выбора признаков.

4.5 Алгоритм поиска седловой точки.

4.5.1 Вычисление параметра шага алгоритма а

4.5.2 Быстрое вычисление проекций.

4.6 Псевдокод седлового алгоритма выбора признаков.

ГЛАВА 5. Экспериментальные результаты

5.1 Схема тестирования алгоритма выбора признаков.

5.2 Распознавание искусственных данных.

5.3 Распознавание звуков английского языка.

5.4 Диагностика заболевания раком женской груди

5.5 Эффективность вычисления проекций методом Дейкстры.

5.6 Анализ результатов и направление дальнейшей работы.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

1. Айвазян С.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Исследование зависимостей: Справ.изд. - М.: Финансы и статистика, 1985. - 488 с.

2. Айвазян С.А., Бухштабер В.М., Енюков И.С. Метналкин Л.Д. Прикладная статистика: Классификация и снижение размерности: Справ.изд. -М.: Финансы и статистика, 1989. 608 с.

3. Айвазян С.А., Мхитарян B.C. Прикладная статистика и основы эконометрики. М.: ЮНИТИ, 1998. - 1022 с.

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

5. Антипин A.C. Управляемые проксимальные дифференциальные системы для решения седловьтх задач // Дифференциальные уравнения. -1992. Т.28. №11. - С.1846-1861.

6. Антипин A.C. Метод градиентного типа для отыскания седловой точки модифицированной функции Лаграижа // Экономика и матем. методы. 1977. -Т.13. - С.560-565.

7. Аркадьев А.Г.,Браверман Э.М. Обучение машины классификации объектов. М.: Наука, 1971. - 192 с.

8. Афифи А., Эйзен С. Статистический анализ. Подход с использованием ЭВМ. М.: Мир , 1982. - 488 с.

9. Бонгард М.М. Проблема узнавания. М.: Наука, 1967. - 320 с.

10. Браверман Э.М. Методы экстремальной группировки параметров и задача выделения существенных факторов // АиТ. 1970. - №1. - С.123-132.

11. Браверман Э.М., Мучник И.Б. Структурные методы обработки эмпирических данных. М. : Наука, 1983. - 464 с.

12. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.: Наука, 1974. - 416 с.

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

14. Воронцов К.В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О. Б. Лу-панова. М.: Физматлит, 2004. - Т. 13. - С. 5-36.

15. Гельфанд И.М. Лекции по линейной алгебре. М.: МЦНМО, 1998. -320 с.

16. Голынтейп Е.Г., Третьяков Н.В. Модифицированные функции Лагран-жа. М.: Наука, 1989. - 400 с.

17. Гончаров Ю.В., Мучник И.Б., Шварцер Л.В. Алгоритм выбора признаков в задаче обучения классификации методом опорных векторов Докл. 13-й всероссийской конф. Математические методы распознавания образов (ММРО-13). -М: ООО «МАКС Пресс». - 2007. - 700 с.

18. Гончаров Ю.В., Мучник И.Б., Шварцер Л.В. Алгоритм выбора признаков в задаче обучения классификации методом опорных векторов / / Ж. вычисл. матем. и матем. физ. -2008. Т.48. №.7. - С.1318-1336.

19. Гончаров Ю.В. Минимаксная задача выбора признаков для построения классификатора методом опорных векторов // Ж. вычисл. матем. и матем. физ. -2010. Т.50. №.5. - С.967-976.

20. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999. -548 с.

21. Загоруйко O.A., Кутпенко И.А., Борисова Н.Г. Выбор информативного подпространства признаков (Алгоритм GRAD). Докл. 12-й всероссийской конф. Математические методы распознавания образов (ММРО-12). -М: ООО «МАКС Пресс». - 2005. - 499 с.

22. Измайлов А.Ф., Солодов М.Ф. Численные методы оптимизации. М.: Физматлит, 2005.

23. Корпелевич Г.М. Экстраградиентный метод для отыскания седловых точек и других задач // Экономика и матем. методы. 1976. - Т.12. -С.747-756.

24. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. - 384 с.

25. Раудис Ш. Ограниченность выборки в задачах классификации // Статистические проблемы управления. Вильнюс. - 1976. - №8. - С.6-185.

26. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973. - 471 с.

27. Ту Дж., Гонсалсс Р. Принципы распознавания образов. М.: Мир, 1978.- 416 с.

28. Харман Г. Современный факторный анализ. М.: Статистика, 1972. -486 с.

29. Эрроу К.Дж., Гурвиц JL, Удзава X. Исследование по линейному и нелинейному программированию. М.: ИЛ, 1962. - 334 с.

30. Abe N., Kudo М., Toyama J., Shimbo M. Classifier-independent feature selection on the basis of divergence criterion // Pattern Anal. Applic., -2006. Ж9. - P. 127-137.

31. Anghelescu A.V., Muchnik I.B. Optimization of SVM in a Space of Two Parameters: Weak Margin and Intercept. // DIMACS Working Group on Monitoring Message Streams. May 2003.

32. Antipin A.S. From optima to equilibria // Proceedings of Institute for Systems Analysis. «Dynamics of non-homogeneous systems». V.3. Moscow.- 2000. P.35-64.

33. Bauschke H.H., Borwein J.M. Dykstra's Alternating Projection Algorithm for Two Sets // J. Approx. Theory. 1994. - V.79. №3. - P.418-443.

34. Bennett K.P.,Campbell C. Support Vector Machines:Hype or Hallelujah? // SIGKDD Explorations 2000. V.2. №2. P.l-13.

35. Bennett K. P., Mangasarian O. L. Robust linear programming discrimination of two linearly inseparable sets // Optimization Methods and Software 1, -1992. P.23-34.

36. Bi J., Vapnik V. Learning with Rigorous Support Vector Machines // Proceedings of COLT. 2003. - P.243-257.

37. Bi J. Multi-objective programming in SVMs // Proc. of 20th Intern.Conf. on Machine Learning (ICML-2003). 2003.

38. Burges C. J.C. A tutorial on Support Vector Machines for pattern Recognition // Knowledge Discovery and Data Mining. 1998. -V.2. №4. - P. 121-167.

39. Burges C.J.C.,Crisp D.J. Uniqueness of the SVM Solution // NIPS 12. -2000. P.223-229.

40. Censor Y. Computational Acceleration of Projection Algorithms for the Linear Best Approximation Problem. // Technical report. Department of Mathematics, University of Haifa. Israel. - May, 2005.

41. Chapelle O., Vapnik V., Bousquet O., Mukherjee S. Choosing Multiple Parameters for Support Vector Machines // Machine Learning. 2002. -V.46. №1. - P.131-159.

42. Chernick M. Bootstrap Methods: A Practitioner's Guide (Wiley Series in Probability and Statistics). Wiley-Interscience, 1999. - 369 P.

43. Cortes C., Vapnik V. Support Vector Networks // Machine Learning. 1995. - V.20. №3. - P.273-297.

44. Combettes P., Luo J. An Adaptive Level Set Method for Nondifferentiable Constrained Image Recovery // IEEE Trans. Image Processing. 2002. -V.ll. - P. 1295-1304.

45. Cover T. M., Van Campenhout J. M. On the possible orderings in the measurement selection problem // IEEE Transactions on Systems, Man, and Cybernetics. 1977. - V.SMC-7. №.9. - P.657-661.

46. Devroye L., Gyorfi L., Lugosi G. A Probabilistic Theory of Pattern Recognition. Springer, 1996. - 636 P.

47. Duda R., Hart P., Stork D. Pattern Classification (Second Edition). Wiley-Interscience Publication, 2000. - 654 P.

48. Dreo J., Petrowski A., Siarry P., Taillard E. Metaheuristics for Hard Optimization. Springer: - 2006. - 369 P.

49. Efron B. Estimating the error rate of a prediction rule: improvement on cross-validation // J. of the American Statistical Association. 1983. - V.78. P.316-330.

50. Efron B., Gong G. A Leisurely Look at the Bootstrap, the Jackknife, and Cross-Validation // The American Statistician. 1983. - V.37. №.1. - P.3648.

51. Efron B., Tibshirani R. An Introduction to the Bootstrap. Chapman & Hall/CRC, 1994. - 436 P.

52. Gaffke N., Mathar R. A cyclic projection algorithm via duality // Metrika.- 1989. V.36. №. P.29-54.

53. Goncharov Y., Muchnik I., Shvartser L. Simultaneous Feature Selection and Margin Maximization Using Saddle Point Approach // DIMACS Technical 'Report 2004. №2004-08. - P.54.

54. Goncharov Y., Muchnik I., Shvartser L. Saddle Point Feature Selection In SVM Regression // DIMACS Technical Report 2007. №2007-08. - P.15.

55. Goncharov Y., Muchnik I., Shvartser L. Saddle Point Feature Selection In SVM Classification // DIMACS Technical Report 2004. №2007-16. - P.23.

56. Foley D. Considerations of sample and feature size // IEEE Transactions on Information Theory. 1972. - V.18. .№.5. - P.618-626.

57. Foroutan I., J. Sklansky J. Feature selection for automatic classification of non-Gaussian data // IEEE Transactions on Systems, Man and Cybernetics.- 1987. -V.17. №.2. P. 187- 198.

58. Guyon I., Elisseeff A. An Introduction to Variable and Feature Selection // Journal of Machine Learning Research. 2003. - V. 3. №.3. - P.1157-1182.

59. Guyon I., Makhoul J., Schwartz R., Vapnik V. What Size Test Set Gives Good Error Rate Estimates? // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1998. -V.20. №.1. - P.52-64.

60. Guyori I., Weston I., Barnhill S., Vapnik V. Gene selection for cancer classification using support vector machines // Machine Learning. 2002. -V.46. №.1-3. - P.389-422.

61. Hall M.A. Correlation-based feature selection for machine learning // Ph.D. thesis. Department of Computer Science, University of Waikato, Hamilton, New Zealand. - 1999.

62. Joachims T. Optimizing Search Engines using Clickthrough Data // ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD). -2002. P.133-142.

63. Joachims T. Estimating the Generalization Performance of an SVM Efficiently // Proceedings of ICML-00, 17th International Conference on Machine Learning. 2000. - P.431-438.

64. King R., Hirst J., Sternberg M. Comparison of artificial intelligence methods for modeling pharmaceutical QSARS // Applied Artificial Intelligence: An International Journal. 1995. -V.9. Issue 2. - P.213-233.

65. Kearns M., Ron D. Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation // Neural Comp. 1999. - V.ll. .№.6. - P.1427-1453.

66. Kohavi R., John G. Wrappers for Feature Subset Selection // Artificial Intelligence. 1997. -V. 97. №.1-2. - P.273-324.

67. Kohavi R. A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection // International Joint Conference on Artificial Intelligence (IJCAI). 1995. - P. 1137-1145.

68. Kudo M., Sklansky J. Comparison of algorithms that select features for pattern classifiers // Pattern Recognition. 2000. - V.33. №.1. - P.25-41.

69. Liu H, Motoda H. Computational Methods of Feature Selection // Data Mining and Knowledge Discovery Series. Chapman & Hall/CRC, 2007. -419 P.

70. Liu H., Setiono R„ A probabilistic approach to feature selection A filter solution // 13th International Conference on Machine Learning. — 1996. -P.319-327.

71. Mangasarian O. L., Wolberg W. H. Cancer diagnosis via linear programming // SIAM News. V. 23. №. 5. - 1990. - P.l-18.

72. McLachlan G. Discriminant Analysis and Statistical Pattern Recognition. -Wiley, 1992. 732 P.

73. Meiri R., Zahavi J. Using simulated annealing to optimize the feature selection problem in marketing applications // Europ. J. of Oper. Res. -2006. V.1-71. №.3. - P.842-858.

74. Molina L., Belanche L., Nebot A. Feature Selection Algorithms: A Survey and Experimental Evaluation // Proc. IEEE Int. Conf. Data Mining. 2002. - P.306-313.

75. Narendra P., Fukunaga K. A branch and bound algorithm for feature subset selection // IEEE Trans, on Computers. 1977. - V. 26. №.9. - P.917-922.

76. Pudil P., Novovicova J., Somol P. Feature selection toolbox software package // Pattern Recognition Letters. 2002. - V.23. № 4. - P.487-492.

77. Raudys S., Jain A. Small sample size effects in statistical pattern recognition: recommendations for practitioners // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1991. -V.13. №.3. -P.252-264.

78. Sebban M., Nock R. A hybrid filter/wrapper approach of feature selection using information theory // Pattern Recognition. 2002. - V.35. №.4. -P.835-846.

79. Skalak D. Prototype and feature selection by sampling and random mutation hill climbing //In Machine Learning, Proc. of the Eleventh Intern. Conf. -1994. P.293-301.

80. Somol P., Novovicova J., Pudil P. Notes on the evolution of feature selection methodology // Kybernetika. 2007. - V. 43. № 5. - P.713-730.

81. Somol P., Pudil P., Kittler J. Fast branch k bound algorithms for optimal feature selection // IEEE Trans. Pattern Anal. Macli. Intell. 2004. -V.26. №. - P.900-912.

82. Theodoridis S., Koutroumbas K. Pattern Recognition, Second Edition. -Elsevier Academic Press, 2003. 689 P.

83. Vapnik V.N. Statistical Learning Theory. New York: Wiley,1998. - 732 P.

84. Vapnik V.N. The Nature of Statistical Learning Theory. Second Edition. -New York: Springer, 2000. 314 P.

85. Webb A. Statistical Pattern Recognition, Second Edition. John Wiley & Sons, 2002. - 496 P.

86. Weston, J., Mukherjee S., Chapelle O., Pontil M., Poggio T. and Vapnik V., Feature Selection for SVMs // Advances in Neural Information Processing Systems. 2000. - 13.

87. Wolberg W. H., Mangasarian O.L. Multisurface method of pattern separation for medical diagnosis applied to breast cytology / Proc. of the National Academy of Sciences, U.S.A. V. 87. - December 1990. - P.9193-9196.

88. Yu B., Yuan, B.1993. A more efficient branch and bound algorithm for feature selection // Pattern Recognition. 1993. - V.26. - P.883-889.