Содержание к диссертации
Введение
ГЛАВА 1. Проблема сокращения размерности в задаче обучения класси фикации 14
1.1 Постановка задачи обучения классификации 14
1.2 Задача сокращения размерности 16
1.3 Методы извлечения признаков 19
1.3.1 Метод главных компонент 19
1.3.2 Метод центроидиых компонент 23
1.3.3 Методы экстремальной группировки параметров 24
ГЛАВА 2. Современное состояние проблемы выбора признаков в задачах классификации 28
2.1 Основные постановки задачи выбора признаков 28
2.1.1 Виды оценок качества подмножества признаков 29
2.2 Методы оценки вероятности ошибки распознавания 33
2.2.1 Resubstitution метод 36
2.2.2 Holdout метод 37
2.2.3 Cross-validation метод 38
2.2.4 Jackknife метод 40
2.2.5 Bootstrap метод 41
2.3 Вычислительная сложность задачи выбора признаков 42
2.4 Обзор алгоритмов выбора признаков 44
2.4.1 Организация пространства поиска 46
2.4.2 Способ движения в пространстве поиска 48
2.4.3 Описание основных алгоритмов выбора признаков 50
ГЛАВА 3. Алгоритмы выбора признаков на основе метода опорных век торов 55
3.1 Метод опорных векторов 55
3.2 Алгоритмы выбора признаков на основе SVM 66
3.2.1 Градиентный алгоритм Вапника и др 66
3.2.2 Алгоритм выбора признаков для задачи SVM в многокритериальной постановке 70
ГЛАВА 4. Минимаксный подход к построению оптимального классификатора методом SVM с одновременным выбором оптимального под пространства признаков . 81
4.1 Дискретная постановка задачи выбора признаков 83
4.2 Непрерывная постановка задачи выбора признаков 88
4.3 Выпуклая минимаксная постановка задачи выбора признаков . 90
4.4 Седловая постановка задачи выбора признаков 93
4.5 Алгоритм поиска седловой точки 100
4.5.1 Вычисление параметра шага алгоритма а 113
4.5.2 Быстрое вычисление проекций 115
4.6 Псевдокод седлового алгоритма выбора признаков 120
ГЛАВА 5. Экспериментальные результаты 123
5.1 Схема тестирования алгоритма выбора признаков 123
5.2 Распознавание искусственных данных 126
5.3 Распознавание звуков английского языка 129
5.4 Диагностика заболевания раком женской груди 133
5.5 Эффективность вычисления проекций методом Дейкстры 138
5.6 Анализ результатов и направление дальнейшей работы 140
Заключение 143
- Методы извлечения признаков
- Resubstitution метод
- Способ движения в пространстве поиска
- Алгоритм выбора признаков для задачи SVM в многокритериальной постановке
Введение к работе
В диссертационной работе рассматривается проблема выбора признаков в задаче обучения классификации. Предлагается минимаксный подход к одновременному построению оптимального решающего правила и оптимального подпространства признаков для классификации. Подход применяется к задаче метода опорных векторов (support vector machine, SVM) и приводит к минимаксной задаче оптимизации модифицированного критерия задачи SVM. Устанавливаются математические свойства решений минимаксной задачи. Предлагаются алгоритмы решения минимаксной задачи. Описываются численные эксперименты по тестированию предложенного подхода в задачах классификации. Демонстрируется применение предложенного минимаксного подхода к задаче одновременного построения SVM регрессии и оптимального подпространства признаков.
Актуальность темы. Определение множества информативных признаков рассматривалось в качестве одной из главных задач с самого начала изучения проблемы обучения классификации. Так, в одной из самых первых работ по распознаванию образов1 построение множества «полезных» признаков рассматривалось в качестве необходимой компоненты в алгоритмах обучения классификации. С прикладной точки зрения необходимость выбора признаков диктуется тем, что обучающие данные часто содержат избыточные или не имеющие отношения к изучаемым явлениям признаки, которые могут значительно снизить качество распознавания. Наряду с задачей выбора признаков также выделяют задачу извлечения признаков, в которой из существующих признаков могут конструироваться новые признаки. При постановке задачи обучения объекты распознавания представляются векторами пространства Rn, где п — количество признаков, характеризующих объект. Таким образом, при решении задачи выбора или извлечения признаков стремят-
^онгард М.М. Проблема узнавания. М.: Наука, 1967.
ся сократить размерность пространства. Предлагаемый в диссертации метод относится к группе «встроенных» методов, в которых признаки выбираются одновременно с процессом решения задачи обучения классификации. «Встроенные» методы представляют наибольший интерес в виду того, что эти методы позволяют учитывать особенности алгоритма обучения в процессе поиска подмножества информативных признаков. Среди огромного разнообразия современных подходов к распознаванию метод SVM на протяжении последних 15 лет общепризнан как один из самых совершенных. Следовательно, разработка «встроенных» методов выбора признаков на основе SVM представляется актуальной задачей. Поскольку в методе опорных векторов формулируется и точно решается оптимизационная задача в пространстве исходных признаков, то естественно попытаться найти обобщение имеющейся формулировки, которая бы обеспечивала поиск оптимального правила классификации при рассмотрении всех возможных подмножеств признаков. Существует несколько примеров таких обобщений задачи SVM. Так, в работе В.Н. Вапника и др.2 предложена постановка задачи выбора признаков, метод решения которой сводится к минимизации дифференцируемой невыпуклой функции при ограничениях. В другой работе рассматривается постановка в форме задачи многокритериальной оптимизации3, для которой предлагается приближенный алгоритм ее решения. В обеих постановках булевые переменные, которые отвечают за выбор подмножества признаков, заменяются на непрерывные переменные Z{ со значениями из отрезка [0,1].
Проблемная ситуация заключается в том, что задачи оптимизации, возникающие в указанных постановках, решаются приближенными методами и не гарантируют нахождения даже локальных минимумов экстремизи-руемых функционалов.
2Weston, J., Mukherjee S., Chapelle О., Pontil M., Poggio T.,Vapnik V. Feature Selection for SVMs // Advances in Neural Information 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.
Другая проблемная ситуация состоит в том, что значения переменных Z{: отличных от нуля и единицы в решении задач оптимизации, затрудняют их интерпретацию в качестве удаленных или выбранных признаков. В обеих постановках трудно судить об условиях, при которых переменные Z{ в решении принимают целые значения.
В диссертации представлен подход к разрешению указанных проблемных ситуаций. Задача выбора признаков ставится на основе модификации оптимизационного критерия метода SVM. В постановке используются непрерывные переменные Z{ Є [0,1], которые отвечают за выбор признаков. Получаемая задача оптимизации имеет выпуклую целевую функцию. Анализируются свойства решений задачи оптимизации и описываются условия, при которых значения переменных Z{ принимают значения 0 или 1.
Цель работы. Целью диссертационной работы является разработка и экспериментальная проверка нового подхода к задаче выбора признаков на основе метода SVM при построении линейных оптимальных решающих правил классификации.
Задачи исследования. Для достижения цели работы поставлены следующие задачи:
Анализ современного состояния проблемы выбора признаков.
Разработка новой формулировки задачи выбора признаков в рамках метода опорных векторов.
Анализ свойств решений поставленной задачи выбора признаков.
Разработка алгоритма решения возникающих задач оптимизации и анализ сходимости алгоритма.
Разработка схемы для экспериментального тестирования разработанного алгоритма.
Реализация алгоритма решения задачи выбора признаков на ЭВМ, проведение и анализ результатов экспериментов.
Методологическая и теоретическая основа исследований. Теоретическую основу диссертации составили работы отечественных и зарубежных авторов в теории выпуклого анализа, оптимизации, прикладной статистики и распознавания образов. В диссертации использовались методы квадратичного программирования, вычисления седловых точек выпукло-вогнутых функций и методы недифференцируемой оптимизации субградиентного типа.
Научная новизна. В диссертации предложена оригинальная формулировка задачи выбора признаков, которая построена на модификации критерия метода опорных векторов. Математически задача выбора признаков поставлена в виде оптимизационной задачи, в которой булевой переменной Z{ соответствует наличие или отсутствие в подмножестве информативных признаков г-го признака. Остальные переменные в задаче оптимизации отвечают за поиск решающей функции распознавания. Задача дискретной, по переменным Z{: оптимизации погружается в непрерывную невыпуклую задачу, в которой переменные Z{ принимают значения из интервала [0,1]. Показано, что невыпуклая задача может быть заменена на эквивалентную задачу на поиск минимакса выпукло-вогнутой функции. Доказана теорема о выпуклости по переменным Z{ минимизируемой функции. Главным научным результатом диссертации является теорема, характеризующая условия, при которых оптимальные значения переменных Z{ в минимаксной задаче принимают значения 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.
числения проекции вместо решения задачи квадратичного программирования предложено использовать алгоритм чередующихся проекций Дейкстры, что значительно ускоряет работу метода.
Теоретическая и практическая значимость. Предложенный минимаксный подход к выбору признаков в задаче классификации может быть применен к другим задачам обработки данных. В приложении С диссертации показано применение минимаксного подхода при выборе признаков в задаче построения SVM регрессии. Разработано математическое обеспечение, позволяющее решать задачи выбора признаков при обучении классификации и построении регрессии методом опорных векторов. Математическое обеспечение решения задач выбора признаков реализовано в виде независимых модулей и может быть использовано независимыми разработчиками.
Апробация работы. Основные результаты работы докладывались на 13-й Всероссийской конференции «Математические методы распознавания образов» в 2007г.
Публикации автора. Основные результаты диссертации опубликованы в работах [1-6]. См. в конце автореферата.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы и трех приложений. Список литературы содержит 89 наименований. Диссертация изложена на 174 страницах, содержит 21 рисунок и восемь таблиц.
Методы извлечения признаков
Подробное описание метода главных компонент содержится в [2, [8], [11], [28]. Опишем постановку задачи и метод ее решения. Пусть х (х1, х2, . .. ,хп) Є Rn является n-мерной случайной величиной с известными вектором средних /і = (/І1,//2, ...,// ) и ковариационной матрицей Е: где соо{хг,хі) — коэффициент ковариации между хг и жЛ Будем рассматривать центрированные данные: Таким образом, будем считать, что вектор х имеет нулевой вектор средних. В том случае, когда вектор средних и матрица ковариации являются неизвестными, то используются их выборочные оценки. Будем искать нормированную линейную комбинацию исходных признаков х1 такую, что полученная случайная величина имеет наибольшую дисперсию. Формально задача ставится следующим образом: Обозначим через вектор а\ = (йц, а о,.. ., о-ыУ решение задачи (1.3). Величина дисперсии z выражается через ковариационную матрицу вектора х следующим образом: В векторном виде равенство (1.4) запишется следующим образом: Таким образом, из (1.5) видно, что в задаче (1.3) ищется максимальное значение неотрицательно определенной квадратичной формы на сфере единичного радиуса. Пусть собственные значения матрицы Е упорядочены по убыванию следующим образом: Из линейной алгебры известно, см.напр.[15], что максимум неотрицательно определенной квадратичной формы на сфере единичного радиуса достигается на собственном векторе матрицы квадратичной формы с максимальным собственным значением. Таким образом, оптимальное значение в задаче (1-3) равно Лі и это оптимальное значение достигается на а,\ — собственном векторе матрицы Е с собственным значением Лі. Первая главная компонента будет равна:
Дисперсия первой главной компоненты равна Лі. Вторая главная компонента ищется в множестве нормированных линейных комбинаций исходных признаков хг, которые имеют нулевое значение коэффициента ковариации с первой главной компонентой z\. Критерием выбора служит максимум дисперсии второії компоненты. Таким образом, решается следующая задача: где а\ — собственный вектор матрицы Е с собственным значением Лі. Обозначим через а2 = (йгъ 22 , Й2п) — решение (1.8). Аналогично решению задачи (1.3), решением задачи (1.8) будет собственный вектор матрицы с вторым по величине собственным значением Л2 Оптимальное значение в задаче (1.8) равно Л2. Вторая главная компонента равна : Дисперсия второй главной компоненты равна Л2. Продолжая таким образом, А -я главная компонента ищется в множестве нормированных линейных комбинаций исходных признаков х3 , которые имеют нулевое значение коэффициента ковариации с (к-1) предыдущими главными компонентами, к-я главная компонента имеет максимальную дисперсию среди элементов этого множества. k-я главная компонента равна : собственным вектором матрицы Е с собственным значением Xk Дисперсия к-й главной компоненты равна А&. Таким образом можно найти все п главные компоненты и записать общее решение в следующем виде: где А-я строка матрицы А состоит из координат собственного вектора (с единичной нормой) матрицы Е с собственным значением Л/,.. Свойства главных компонент 1. Математическое ожидание вектора главных компонент равно нулю: 2.
Матрица ковариаций вектора главных компонент является диагональ ной: \ / 3. Сумма дисперсий исходных признаков вектора х равна сумме дисперсий главных компонент: Из равенства (1.9) можно предложить следующий критерий информативности первых А главных компонент: Данный критерий позволяет вычислить относительную долю дисперсии, приходящуюся на первые К главных компонент, и принять решение о количестве главных компонент при сокращении размерности. Модель главных компонент имеет несколько эквивалентных формулировок. Например, можно сформулировать задачу поиска главных компонент в рамках более общей модели факторного анализа, см. [10]. В рамках модели факторного анализа можно показать, что в методе главных компонент при поиске К главных компонент решается следующая задача:
Resubstitution метод
Пусть имеется обучающая выборка S = {.Ті, #2, , хі} объема I. Пусть алгоритм обучения построил решающее правило f(x) по обучающей выборке S. Применяя решающее правило f(x) к обучающей выборке S, можно получить оценку вероятности ошибки распознавания. Правило /(.т) применяется к элементу Х\. Элемент xi классифицируется правильно или ошибочно. В случае правильной классификации е\ = 0, а в случае ошибочной классификации Є\ = 1. Аналогично вычисляются результаты классификации Є2,...,е/ для остальных элементов выборки. Оценкой вероятности ошибки будет служить доля ошибочных классифп 1 г=1 Известно, что обычно оценка (2.6) занижена по сравнению с истинной и является излишне «оптимистичной». Например, в [83] доказано, что для байесовского классификатора эта оценка будет оценкой снизу для условной вероятности ошибочной классификации P(S,l). В работе [56] на примере двух классов, представленных двумя нормальными распределениями, анализируется поведение оценки (2.6) для P(S, І) в зависимости от объема выборки I и размерности пространства п. Утверждается, что при сооотношении - 3 оценка является сильно смещенной. Стандартное отклонение оценки ограничено величиной . В том случае, когда имеется достаточно большая выборка, то возможно разделить выборку на две части. Первая часть выборки используется для обучения и построения решающего правила, вторая часть для оценки построенного правила. Первая часть выборки называется обучающей, вторая часть — тестирующей. Пусть в результате работы алгоритма построено правило f(x), которое классифицирует элементы генеральной совокупности с вероятностью ошибки Р. Пусть в тестирующей выборке находится N элементов. Пусть количество ошибок классификации по правилу f(x) на тестирующей выборке равно к. Используя биномиальную модель, получаем по методу максимального правдоподобия оценку Р = j величины Р.
На основе оценки Р можно получить доверительный интервал для величины Р. Пример из [47] показывает, что при размере тестирующей выборки N — и безошибочной классификации (к — 0) с 95% уровнем значимости истинное значение Р находится между 0 и 8%. Для получения доверительного интервала [0, 2%] при безошибочной классификации нужно было бы взять тестирующую выборку размера 250. В [59] приводится пример, когда при истинном значении ошибки Р = 1% необходимо брать выборку размера 10000 для получения Р близкой к истинной Р. В книге С.А. Айвазяна и др. [2] cross-validation называется методом скользящего экзамена. В просгепшем варианте этот метод сводится к следующему. Пусть имеется выборка S = {.v\, Х2, - ., х{\ объема /. Процедура оценки состоит из / однотипных шагов. На каждом шаге из выборки S удаляется один элемент. По оставшимся данным строится решающее правило классификации. Затем правило применяется к удаленному элементу. Результат классификации запоминается. Элемент возвращается в выборку и производится переход к следующему элементу выборки S. Опишем процедуру оценки более подробно. На первом шаге из S = {хь Х2, , %i} удаляется элемент х\. Полученная выборка #2, ггз, , / используется в качестве обучающей для алгоритма обучения. Полученное решающее правило f\(x) применяется к элементу х\. Элемент Х\ классифицируется правильно или ошибочно. В случае правильной классификации е\ = 0, а в случае ошибочной классификации Є\ = 1. На г-том шаге из S — {х\, x i,..., хі} удаляется элемент Х{. Выборка Жі,Х2, , г-1, Xi+i,... ,xi используется в качестве обучающей .
Решающее правило fiix) применяется к элементу хг и вычисляется Є;. Оценкой вероятности ошибки будет служить доля ошибочных классификаций: В англоязычной литературе этот вариант метода «cross-validation» носит па-звание «leave-one-out». Обобщением «leave-one-out» является процедура «n-fold cross-validation». Выборка случайным образом разбивается па п непересекающихся подмножеств: Обычно стремятся, чтобы мощности подмножеств Si, / = 1. 2,. . ., п были одинаковыми. Процедура состоит из п однотипных шагов. На j-том шаге из выборки S удаляется множество Sj. Обучение производится на оставшихся элементах выборки S/S}. Подсчитываются результаты распознавания ег- для всех .гІ Є Sj. После выполнения всех п шагов вычисляется оценка по формуле (2.7). Данную процедуру можно повторить для нескольких случайных разбиений (2.8), а вычисленные оценки (2.7) усреднить для получения окончательной оценки. Метод «n-fold cross-validation» со значением п равного объему выборки / превращается в «leave-one-out» метод. Метод «complete cross-validation» требует, чтобы обучение и подсчет ошибок были проведены на всех возможных разбиениях выборки S на обучающую часть мотцности (I — к) и тестирующую часть мощности к. Таким образом, для каждого из Cf подмножеств S С S мощности к, \S\ — к проводится обучение на S/S и подсчет ошибок на S.
Способ движения в пространстве поиска
Способ движения указывает возможности по переходу из текущего состояния в следующее состояние в пространстве поиска. Пусть функция I{Z) — целевая функция, которая оценивает конкретный выбор признаков, т.е точку Z в пространстве поиска. Пусть I(Z) максимизируется. Определяются 5 основных способов движения. 1. Шаг Вперед (Forward). Начиная с пустого множества Z = 0 добавляется признак, который дает максимальное значение функционала I(Z): 2. Шаг Назад (Backward). Начиная с множества Z — X удаляется признак, который дает максимальное значение функционала I(Z): 3. Шаги Вперед-Назад (Compound). Пусть А и В положительные целые числа. Делается А движений «Шаг Вперед» , затем В движений «Шаг Назад». В работе [21] описывается следующая часто встречающаяся ситуация. Пусть, начиная с пустого подмножества признаков, мы добавляем на каждом шаге алгоритма по одному наиболее информативному признаку. Существуют пары признаков, которые взятые вместе значительно увеличивают экстремизируемый функционал. В то время, как взятые по отдельности, они не дают значимого прироста функционала. Поэтому на первых шагах алгоритма эти признаки будут удалены из рассмотрения. Требуется возможность добавлять сразу пары признаков. Для работы с функционалами такого типа и предназначено движение типа «Шаги Вперед-Назад». В процессе работы алгоритма «размеры» шагов А могут изменяться. Стоит заметить, что описанная выше ситуация с добавлением пары признаков была бы невозможна, если бы поиск начинался с множества всех признаков X и признаки удалялись по одному. В этом случае пара признаков осталась бы в оптимальном подмножестве признаков. 4. Весовые координаты (Weighting).
При этом способе движения в пространстве поиска происходит изменение весов признаков согласно некоторому алгоритму. Отметим, что наш оригинальный алгоритм, который описан в диссертации использует данный способ движения в пространстве поиска. 5. Случайный шаг (Random). При таком способе движения возможен переход из одного состояния в любое другое, находящееся в пространстве поиска. Практически во всех обзорах алгоритмов выбора признаков высказывается мысль, что на разных задачах различные алгоритмы показывают отличающиеся результаты. Следовательно, лучшей стратегией было бы применение целого ряда алгоритмов, оценка полученных результатов и выбор наилучшего решения. Существенным ограничением многих алгоритмов является требование монотонности оценки подмножества признаков. В этом случае невозможно использовать наиболее адекватную оценку «вероятность ошибки классификатора». Такая оценка является монотонной в случае «байесовского классификатора». В работе [57] предложена модификация алгоритма на случай «.малого» нарушения монотонности оценки. Опишем наиболее распространенные алгоритмы. Алгоритмы в пространстве «Экспоненциальный поиск» Основным алгоритмом в пространстве «Экспоненциальный поиск» является алгоритм ветвей и границ [76], а также его различные модификации.
В процессе поиска подмножества фиксированной мощности к происходит обход дерева и вычисление значений оценки I(Z) в вершинах дерева. Каждая вершина дерева представляет некоторое подмножество признаков. В работе [89] описано как сократить количество вычислений I(Z) в том случае, когда в процессе обхода дерева происходит движение из вершины А, \А\ к в вершину В, \В\ = к. Если из вершины А в вершину В ведет единственный путь. то нет необходимости вычислять значения оценки I(Z) в промежуточных вершинах дерева. Вместо этого следует сразу вычислить значение в вершине В. Проиллюстрируем эту идею на следующем примере. На рис.2.2 изображено дерево обхода для задачи, в которой среди пяти исходных признаков ищется оптимальное подмножество состоящее из двух признаков. Признаки пронумерованы и всякое подмножество признаков задается списком номеров признаков. Каждой вершине дерева соответствует подмножество признаков и вершина помечена соответствующим списком. Корень дерева представляет все множество признаков (1, 2, 3,4, 5). Листья дерева представляют собой подмножества с 2 признаками. Пусть в процессе обхода дерева алгоритм попадает в вершину А — (1,2,4,5). Нет необходимости вычислять значения функционала 1(A) в этой вершине. Алгоритм переходит сразу в вершину В = (1,2) и вычисляет 1(B). Таким образом, экономится два вычисления значения функционала I(Z). В работе [82] описывается «быстрый» метод ветвей и границ, в котором стремятся к сокращению количества вычислений значений оценки I(Z) в вершинах дерева. Для этого в процессе обхода дерева собирается информация о каждом признаке, чтобы делать прогноз значения функции I(Z) реально не вычисляя его значения. Вычисляется насколько в среднем удаление признака изменяет величину функции I(Z). Т.е. усредняется по Z величина I(Z) — I(Z \ г), если значения I(Z) и I(Z \ г) вычислялись в процессе обхода дерева. Пусть эта средняя величина равна А{. Пусть в процессе обхода мы находимся в вершине А и следующая вершина обхода А \ г.
Алгоритм выбора признаков для задачи SVM в многокритериальной постановке
Вторая работа [37], которая привлекла внимание автора, рассматривает задачу SVM как многокритериальную задачу оптимизации. Многокритериальная задача записывается в следующем виде: Ограничения задачи задают допустимое множество: Нужно определить — что понимать под оптимальным решением задачи (3.29). Говорят, что решение Х\ Є F доминирует решение х2 Є F, если выполнены условия: Решение Х\ не хуже, чем Х2 . Obj ) Obh(x2), Obj2(Xl) Obj2{x2) . Решение X\ строго лучше, чем х2 хотя бы по одному критерию: Зг{1; 2}, ObjtM Obji(x2) . Решение х называется Парето-оптимальным, если не существует решения у, которое бы доминировало х. Парето-оптимальные решения составляют Парето-оптимальное множество. Существуют различные методы нахождения Парето-оптимальных решений. Метод взвешенной суммы сводит многокритериальную задачу к од-нокритериалыгай задаче. Каждому критерию приписывается вес и формируется следующая задача: Любое решение задачи (3.30) является Парето-оптимальным решением задачи (3.29). В том случае, когда в (3.29) функции Obji(x). ObJ2(x), д(х) выпуклые, а функция d{x) линейная, любое Парето-оптимальное решение многокритериальной задачи (3.29) является решением однокритериальной задачи при некоторых значениях констант с\ и с%. В общем случае существуют Парето-оптимальные решения, которые не являются решением однокритериальной задачи (3.30) при любых значениях констант С[ п со. Для невыпуклых задач рассматривается задача, в которой минимизируется один критерий, а на остальные критерии налагаются ограничения сверху: При задании необходимого значения 5 в ограничении задачи (3.31) возможно получить любое
Парето-оптимальное решение задачи (3.29). Метод решения задачи (3.29) путем сведения к задаче (3.31) называется методом ограничений решения многокритериальной задачи оптимизации. Теперь опишем постановку задачи распознавания в многокритериальной форме. Верхняя оценка для вероятности оплібки распознавания решающим правилом / может быть записана в следующем виде где Т — допустимое множество решающих функций, Remp(f) величина эмпирического риска решающей функции /, h J7) — VC-размерность множества Т,1 — размер обучающей выборки, а функция Ф — монотонная. Для минимизации оценки (3.32) ставится задача минимизации эмпирического риска и VC-размерности. Причем, при вычислении значения оцеп ки (3.32), используются не точные значения эмпирического риска и VC-размерности, а их приближенные значения. Задачи минимизации эмпирического риска и VC-размерности являются конфликтующими. При уменьшении VC-размерности эмпирический риск может возрасти, так как множество Т становится «бедным» и не содержит функций, хорошо приближающих данные обучающей выборки. Эти конфликтующие задачи можно сформулировать в многокритериально it форме: В зависимости от выбора множества Т , способа вычисления эмпирического риска и способа вычисления оценки VC-размерности, возможно получать из (3.33) различные постановки задачи обучения SVM в форме задачи многокритериальной оптимизации.
В описываемом подходе к задаче выбора признаков, поиск оптимального подмножества признаков сводится к поиску оптимальной kernel-функцпп. Поэтому кратко опишем использование kernel-функций в SVM. Можно привести пример, когда в исходном пространстве элементы обучающей выборки не являются линейно разделимыми. Т.е. не существует гиперплоскости, разделяющей исходное пространство на две части таким образом, чтобы элементы разных классов лежали в разных частях. В этом случае применяется отображение точек исходного пространства в новое пространство, где образы элементов обучающей выборки являются линейно разделимыми. Пусть функция Ф(х) осуществляет такое преобразование в новое пространство. Это новое пространство называют спрямляющим пространством. Оказывается, что алгоритм обучения по методу опорных векторов устроен таким образом, что достаточно уметь вычислять скалярное произведение об разов: (Ф(х),Ф(у)) в спрямляющем пространстве. Нет необходимости уметь вычислять значение Ф(х). Функция К(х,у) = (Ф(;г), Ф{у)) называется kernel-функцией. Рассмотрим пример, который иллюстрирует использование kernel-функции. Пример 2 На рис.3.7 изображены элементы линейно неразделимых классов в исходном 2-мерном пространстве. При соответствующем выборе
