БИОФИЗИКА, 2015, том 60, вып. 1, с. 18-31
МОЛЕКУЛЯР НАЯ БИОФИЗИКА =
УДК 577.3
СРАВНИТЕЛЬНАЯ ЭФФЕКТИВНОСТЬ АЛГОРИТМОВ ПОСТРОЕНИЯ МАШИН ОПОРНЫХ ВЕКТОРОВ ДЛЯ ЗАДАЧИ БИНАР НОЙ КЛАССИФИКАЦИИ
© 2015 г. Н.О. Кадырова, Л.В. Павлова
Институт прикладной математики и мех аники Санкт-Петербургского государственного политех нического университета, 195251, Санкт-Петербург, ул. Политехническая, 29 E-mail: па1аИа.кайутоуа@^таП.сот Поступила в p едакцию 09.06.14 г.
Методы построения машин опоpныx вектоpов не тpебуют дополнительной апpиоpной ин-фоpмации и позволяют обpабатывать большие объемы данный большой pазмеpноcти, что особенно важно для многиx проблем вычиcлительной биологии. Пpедcтавлены основные алгоpитмы поcтpоения машин опоpныx вектоpов для задачи бинаpной клаccификации. Рас-cмотpен вопpоc качества алгоpитмов обучения. Пpиведено опиcание пpедcтавленныx алго-pитмов, доcтаточное для их пpактичеcкой pеализации. И ccледована cpавнительная эффектив-ноcть pяда SV-клаccификатоpов.
Ключевые слова: бинарная классификация, машины опорных векторов, ядерные машины, SVM-алгоритмы, сравнительная эффективность SV-классификаторов.
Оеновные пpинципы и идеи cовpеменного подxода к задачам бинарной классификации и восстановления р егрессии, о снованного на машинах опорных вектор ов, рассмотрены нами в работе [1]. SVM-методы относятся к технологии, названной интеллектуальным анализом данных, и замечательны тем, что пр актически не требуют дополнительной априор ной информации и позволяют обрабатывать большие объемы данных большой р азмерности.
Новый индукционный принцип обучения по конечным выборкам - структурная минимизация риска - приводит к задаче минимизации регу-ляризованного риска [2]. Ряд SVM-алгоритмов непосредственно решает эту задачу, используя ядерные машины, например, алгоритм Naive Online Risk Minimization Algorithm (NORMА).
Стандартная постановка задачи бинарной классификации позволяет свести исходную задачу минимизации верхней границы ожидаемого риска к задаче квадратичного программирования с ограничениями типа равенств относительно двойственных переменных, полностью определяющих искомое решающее правило [2]. Непоср едственное решение двойственной задачи квадратичного программирования обычно невозможно из-за ее громадной размерности. Основные подходы к построению непрямого решения этой задачи опираются на свойство разреженно сти, пр исущее SV-машинам. Ряд SVM-алгоритмов основан на декомпозиции, т.е.
разбиении исходной задачи квадратичного про -граммирования на серию подзадач существенно меньшей размерности, например, алгоритмы SVM_Light и Sequential minimal optimization (SMO).
В настоящей работе рассмотрены о сновные алгор итмы построения машин опорных векторов для задачи бинарной классификации и исследована их сравнительная эффективность.
КАЧЕСТВО АЛГОРИТМОВ ОБУЧЕНИЯ
Оценивание характеристики обобщения (generalization performance) различных алгор итмов, использующих некоторое выборочное множество, является существенным моментом SVM-подхода. При заданной тренировочной последовательности важно опр еделить, насколько хо -рошо конкретный алгоритм обучения будет работать на новых данных, т.е. какова его способность к обобщению. Располагая подобной информацией, можно решать вопрос о выборе алгоритма, модели, значений параметров обучения.
На практике обычно используют методы оценивания ошибки обобщения, основанные на процедуре k-кратной перекрестной проверки (k -fold CToss-validation (CV)). Однако теоретические аспекты этого подхода мало изучены. Наиболее популярной разновидностью CV-ошибки является так называемая leave-one-out (loo)
ошибка (скользящий контр оль), полученная после пр именения /-кратной перекрестной проверки, где 1 - объем тренировочной последовательности. 1оо-Ошибка как оценка ошибки обобщения является важной статистической оценкой качества алгоритмов обучения. В работе [3] приведены результаты, позволяющие обосновать использование 1оо-ошибки при обучении машин.
Пусть X - пространство входных объектов х с фиксированным неизвестным распределением вероятностей Р (х); У - пр остранство выходных объектов у с фиксированным неизвестным распределением вероятностей Р(у/х). О - тренировочная последовательность объема 1, т.е. выборка независимых, одинаково распределенных согласно закону Р(х,у) = Р(х) х Р(у/х) наблюдений (х1, у 1), ... , (х1, у). Б' - трениро-вочная последовательность объема 1-1, полученная из О путем удаления г-го образца (х, у). До : X ^ Я - решение, полученное с использованием данного алгоритма обучения на основе выборки О. Пусть функция потерь Ь : Я х У ^ Я, Ь = ЬД(х),у) = ЬД,(х,у)), штрафует отклонение оценок Дх) от наблюдаемых у.
В качестве ошибки обобщения данного алгоритма обучения относительно функции потерь Ь рассматривают ожидаемый риск
Я [О = \ь Дв,(х,у))йР(х,у).
X х У
В качестве эмпирической ошибки данного алгор итма обучения относительно функции потерь Ь можно использовать как эмпирический риск
1
Я етр[До] = }ЕЬ До^ ^
' = 1
так и 1еауе-оие-ои1-ошибку
1
Я 1ооДо] = \ ТЬ (До',(х,у)).
г = 1
Заметим, что в последнем случае образец (х , у ) не используется в процессе обучения, на нем тестируется решение, полученное на основе выборки О' объема 1-1.
В отличие от эмпирического риска 1оо-ошибка почти не смещена в следующем смысле: 1оо-ошибка, основанная на выборках объема 1, дает несмещенную оценку ошибки обобщения после обучения по 1-1 образцу.
Вычисление loo-ошибки требует больших временных затрат, поэтому многие исследователи пытались получить для нее простые (в отношении вычислений) границы.
ОЦЕНКА КАЧЕСТВА SVM-КЛАССИФИКАЦИИ
Одним из показателей качества алгоритма классификации является его способность правильно классифицировать новые образцы. При этом требуется, чтобы характер истика этой способности была эффективной и не требовала большого количества вычислений.
Для оценивания характеристики обобщения обычно используется процедура перекрестной проверки, в частности loo-оценка. Из тр ениро -вочной последовательности удаляется один образец. На оставшихся (1-1)-парах производится обучение, результат которого проверяется на удаленном образце. Число полученных ошибок, деленное на число членов тренировочной последовательности, и является в данном случае loo -оценкой ошибки обобщения.
Верхние границы для loo-ошибки классификации, предполагающие построение только одной машины опорных векторов на основе исходной тренировочной последовательности объема l, приведены в работах [3,4].
В работе [4] предложена верхняя граница leave-one-out-оценки ошибки обобщения для стандартного SV-классификатора:
d
J_errl = - где d = |{i:(paR| + ') > 1}|. (1)
Здесь: р - параметр, равный двум; a¡ -множитель Лагранжа; ' - ослабляющая переменная, соответствующая i-му образцу; R\ -
верхняя граница разности K(x,x)-K(x,x') для всех допустимых входных векторов x, x', где K - ядерная функция (в случае линейного и гауссовского ядра R\ = 1). Доказано, что в
среднем оценка (1) больше, чем истинная доля ошибок классификации [4].
В работе [3] показано, что для задачи би-нар ной классификации с использованием функции потерь Хевисайда S(-y-f(x)) loo-оценка ядерной машины, которая минимизирует регуляри-зованный риск на основе тренировочной последовательности D, ограничена сверху:
Rf - 71 s( - yDx)) <
i = i
< 1 X8(jai!^(x,xi) - yfD(x)).
i = 1
ROC-анализ (Receiver Operator Characteristic) пр едставляет собой графический метод для представления результатов бинарной классификации пр и машинном обучении, отр ажаю-щий качество данного классификатора или сравнительную эффективность нескольких классификаторов. ROC-кривые весьма полезны в случае асимметричного распределения входных векторов и неодинаковой цены ошибок классификации. Эти показатели становятся особенно важными при несбалансированных классах.
Чтобы определять качество классификации отдельно для каждого класса (один класс -класс с положительными образцами, второй -с отрицательными обр азцами), используют показатели чувствительности и специфичности или показатели recall и precision, причем recall - то же самое, что чувствительность.
Чувствительность отражает эффективность работы бинарного классификатора и определяет долю истинно положительных наблюдений относительно количества фактически положительных. Классификатор, обладающий высокой чувствительностью, обеспечивает большую вероятность правильного распознавания положительных образцов.
Cпецифичноcть отражает точность р аботы бинарного классификатора и определяется как отношение истинно отрицательных наблюдений к числу фактически отрицательных. Модель, обладающая высокой специфичностью, обеспечивает большую вероятность правильного распознавания отрицательных образцов.
Показатель precision определяет долю истинно положительных наблюдений относительно количества наблюдений, классифицированных моделью как положительные.
Например, при классификации пациентов на больных (положительные образцы) и здоровых (отрицательные образцы) чувствительный классификатор максимально предотвращает пропуск больных, а специфичный классификатор диагностирует только настоящих больных.
П рактическое руководство по корректному использованию ROC-кривых и основных показателей качества классификации можно найти в работе [5]. Взаимосвязанность ROC-кривых
и ргес18юп-геса11-кривых рассмотрены в работе [6].
ОПИСАНИЕ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ БИНАРНОЙ КЛАССИФИКАЦИИ
Ра ссмотрим формулир овку двойственной задачи БУМ-обучения для бинарной классификации:
найти minW (а) = - /а + 2;/aiajyjyjK(xi,Xj)
(2)
а,- + 2"/ а,-<
i = 1 i, j = 1
при ограничениях 0 < ai < С, /ayi = 0.
i=1
Здесь (х^), ... , (х, у) е Я1 х {-1;+1} -тренировочная последовательность объема I; а > 0 - множители Лагранжа; С > 0 - параметр регуляризации, контролирующий ширину полосы; К(хх') - ядерная функция, удовлетворяющая условию Мерсера [2].
Оптимальная решающая функция представляет собой линейную комбинацию значений ядра на тренировочных векторах:
f(x) = /ауК(х.,х) + b.
Пусть Q - симметричная положительно определенная I х I матрица с элементами Q¡j
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.