vchilka.in.ua 1

СРАВНЕНИЕ НЕКОТОРЫХ ПОДХОДОВ К РЕШЕНИЮ ЗАДАЧ КЛАССИФИКАЦИИ


Ю.И.Журавлев, Ю.П.Лаптин, А.П.Виноградов, Н.Г.Журбенко, А.П.Лиховид


Математические модели задач построения линейных и нелинейных классификаторов и методы построения классификаторов, основанные на этих моделях, рассматривались во многих работах (см., например, [1-4]). Сравнению различных подходов к решению задач построения классификаторов посвящены работы [4-6]. Наиболее широко в настоящее время используется метод опорных векторов (SVM).

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

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

Приводятся результаты вычислительных экспериментов на специальных тестовых задачах большой размерности [см. также 10]. Эти результаты показывают, что для рассмотренных задач с увеличением обучающей выборки трудоемкость методов негладкой оптимизации растет медленнее по сравнению с методом опорных векторов (LIBSVM).

1. Краткое описание задач построения классификаторов


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

, , . (1)

При приведенное соотношение может быть упрощено, линейные классификаторы описываются одной линейной функцией , и представляются в виде

(2)

Функции обычно называются дискриминантными функциями.

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


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

Говорят, что классификатор правильно разделяет точки из , если , для всех . Положим – номер множества , которому принадлежит точка , . При величина



(3)

называется зазором классификатора в точке , .


В случае зазором классификатора в точке является величина

(4)

Величина называется зазором классификатора на совокупности множеств . Классификатор правильно разделяет точки из множеств , если .

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

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


Будем рассматривать задачу построения оптимального классификатора (определения значений параметров ) для множеств, разделимых в классе линейных классификаторов, имеющую вид: найти

. (5)

Для случая может использоваться норма , для .

Задача (5) может быть записана в эквивалентных формах

, (6)

. (7)

Здесь эквивалентность понимается в следующем смысле – если оптимальное решение задачи (5), то для оптимального решения задачи (6) или (7) имеет место [11] , . Заметим, что для множеств, разделимых в классе линейных классификаторов.

2. Последовательные линейные классификаторы

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




Рисунок. Пример множеств, неразделимых в классе линейных классификаторов

В [11,12] формулируются некоторые достаточные условия разделимости в классе линейных классификаторов для произвольного числа множеств. Более углубленный геометрический анализ таких условий приведен в [13].

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


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

Необходимо отметить, что рассмотренные последовательные классификаторы близки по конструкции к DAGSVM-алгоритмам, введенным в [6].

3. Минимизация эмпирического риска


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

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

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


. (8)

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

, (9)

при ограничениях

, (10)

, (11)

, (12)

, (13)

. (14)

Переменная определяет, учитывается ли точка при формулировке задачи. Если , то точка исключается из обучающей выборки. Ограничения (12) определяют условие того, что, по крайней мере, одна точка из каждого множества должна быть включена в задачу.

Задача (9)-(14) – -полная. В связи с этим для практического использования должны разрабатываться приближенные алгоритмы решения такой задачи. При небольших значениях размерности задачи могут применяться существующие программные средства оптимизации общего назначения (возможности такого использования будут рассматриваться в разделе 6).


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

Пусть , , ,. Рассмотрим задачу

, (15)

, (16)


. (17)

Лемма 1. Имеет место равенство

. (18)

Доказательство. Обозначим , – множество всех , удовлетворяющих ограничениям (12), (14), – множество всех векторов , удовлетворяющих ограничениям (10), (11) при заданном значении вектора . Пусть вектор такой, что . Положим

.

Очевидно, что . Пусть , , . Обозначим . Нетрудно видеть, что для любого такого, что , выполняется , т.е. . Откуда , и учитывая, что получаем утверждение леммы. ■.


Пусть . Рассмотрим более подробно задачу (15)–(17). Учитывая (4), перепишем эту задачу в виде

, (19)

, (20)

, (21)

. (22)

Если система ограничения (20) – (22) несовместна, то . Это имеет место, если . В силу (8) всегда существует пара , такая что.

Легко видеть, что в оптимальном решении задачи (19)–(22) ограничения (20), (22) обязательно выполняются как равенства, а ограничение (21) может быть как активным, так и неактивным. Рассмотрим случай, когда ограничение (21) неактивно в оптимальном решении. Используя правило множителей Лагранжа, получаем для оптимального решения

, , .

При этом для полученного вектора должно выполняться ограничение (21). Если это ограничение не выполняется, то оптимальное решение должно строиться с учетом того, что ограничение (21) активно.


Полученные соотношения позволяют сравнительно просто определять значения .

Рассмотрим задачу (9)-(13) – непрерывную релаксацию задачи минимизации эмпирического риска. Положим и зафиксируем некоторые значения переменных . Нетрудно видеть, что если при этих значениях существует решение задачи (9)-(13), то . Откуда получаем задачу минимизации по переменным : найти

(23)

при ограничениях

, (24)

, (25)

, (26)

Величина есть оценка снизу для минимального значения эмпирического риска , а вектор , полученный в результате решения задачи (23)–(26), определяет приближенное решение задачи (9)–(14). Функции – выпуклые кусочно-линейные. Для решения задачи (23)-(26) целесообразно применять эффективные методы негладкой оптимизации [9]. Особенности такого применения будут рассмотрены в разделе 5.

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


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

, (27)

, (28)

, (29)

. (30)

Метод опорных векторов (SVM) используется для построения оптимального классификатора как для линейно разделимых классов, так и для линейно неразделимых классов.

Заметим, что ограничения (28), (29) соответствуют ограничению . В случае линейно разделимых классов из теорем о негладких штрафах [см., например, 9] следует, что при достаточно большом коэффициенте задачи (7) и (27)–(30) имеют одинаковые решения. В случае линейно неразделимых классов задача (27)–(30) интерпретируется [14] как некоторая регуляризация задачи минимизации эмпирического риска.

Покажем, что между задачей (27)–(30) и непрерывной релаксацией (9)–(13) задачи минимизации эмпирического риска существуют определенные взаимосвязи.

Ослабим ограничения (10), положив , и исключим ограничения (12). Задача примет вид

, (31)

при ограничениях

, (32)


, (33)

, (34)

. (35)

Здесь ограничение (11) заменено парой эквивалентных ограничений (32), (33). Понятно, что . Сделаем замену переменных , . Задача примимает вид

(36)

при ограничениях

, (37)

, (38)

, (39)

. (40)

Пусть – двойственная переменная для ограничения (39). Рассмотрим функцию Лагранжа и Лагранжевую релаксацию задачи (36)–(40): найти

(41)

при ограничениях (37), (38), (40).

Поскольку – оптимальное значение Лагранжевой релаксации задачи (36)–(40), то при любом [см., например, 9]. Пусть задан штрафной коэффициент в задаче (27)-(30). Выбирая из условия , получаем


,

т.е. задача (41), (37), (38), (40) эквивалентна задаче (27)-(30) с точностью до аддитивной константы и фиксированного множителя в целевой функции при указанном выборе значения двойственной переменной.

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

5. Решение задач оптимизации с ограничениями


Используемая схема решения оптимизационных задач с ограничениями заключается в построении эквивалентной задачи безусловной оптимизации и в последующем ее решении эффективными субградиентными алгоритмами (r-алгоритмом Н.З.Шора [9]). Для построения такой задачи безусловной оптимизации будет использоваться метод точных штрафных функций [см., например, 9]. Возможно также использование другого эффективного подхода [16, 17].

Задача выпуклого программирования с ограничениями имеет вид: найти

, (42)

где , – выпуклые функции.

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

, , (43)

где , , и задачу: найти


. (44)

Штрафная функция точная при заданном значении штрафного коэффициента , если и решения задач (42) и (44) совпадают.

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

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

Обозначим:

– решение задачи безусловной оптимизации (44),


– производная функции в точке по направлению при фиксированном значении ,

,

– точка пересечения отрезка с границей если ,

.

Теорема 1 [15]. Пусть заданы числа , и для каждого , , выполняется

. (45)

тогда является решением задачи (42), т.е. – точная штрафная функция.


Теорема 2 [15]. Пусть , где . Тогда существует такое, что при любом , существует , для которых выполняются условия теоремы 1.

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

В случае, когда неравенство (45) на некоторой итерации алгоритма нарушается, будем увеличивать (на этой итерации) штрафной коэффициент так, чтобы неравенство (45) выполнилось. При этом увеличение штрафного коэффициента производится на величину не менее , где – заданный параметр. В силу теоремы 2 количество таких увеличений штрафного коэффициента по ходу работы оптимизационного алгоритма будет конечно.


Если начальная точка , такая что , неизвестна, то процесс решения задачи распадается на два этапа – на первом необходимо найти точку , на втором собственно решается исходная задача.

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


Приведем особенности задач (5) и (23)-(26), полезные при использовании описанных подходов:

  1. Точка является внутренней точкой допустимого множества.

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

  3. Одномерный поиск точки на границе допустимого множества реализуется просто: пусть – квадрат нормы точки , , тогда точка является искомой точкой на границе допустимого множества..

  4. Функции обладают свойством – .

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


Задача (27)-(30) приводится к виду

, (46)

и для ее решения также использовался -алгоритма Н.З.Шора.

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

размерность признакового пространства – от 5 до 100;

число точек в обучающей выборке – от 40 до 50 000.

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

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

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

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


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

Разработанные программные средства сравнивались с существующим программным обеспечением (LIBSVM – http://www.csie.ntu.edu.tw/