«БАЙЕСОВСКИЕ МЕТОДЫ ОПОРНЫХ ВЕКТОРОВ ДЛЯ ОБУЧЕНИЯ РАСПОЗНАВАНИЮ ОБРАЗОВ С УПРАВЛЯЕМОЙ СЕЛЕКТИВНОСТЬЮ ОТБОРА ПРИЗНАКОВ ...»

8. A. Tatarchuk, V. Mottl, A. Eliseyev, D. Windridge. A Bayesian approach to multimodal pattern recognition with supervised selectivity of modalities. Proceedings of 9th International Conference on Pattern Recognition and Image Analysis: New Information Technologies, Nizhni Novgorod, September 14-20, 2008, vol. 2, p. 204.

В.В. Моттль, А.И. Татарчук, А.П. Елисеев Экспериментальное исследование методов многомодального распознавания образов с регулируемой селективностью. Известия Тульского государственного университета. Технические науки, вып.3. – Тула: Изд-во ТулГУ, 2008.

10. Tatarchuk A., Mottl V., Eliseyev A., Windridge D. Selectivity supervision in combining pattern-recognition modalities by feature- and kernelselective Support Vector Machines. Proceedings of the 19th International Conference on Pattern Recognition, Vol 1-6, IEEE, ISBN 978-1-4244-2174-9, 2008, pp. 2336-2339.

Моттль В.В., Татарчук А. И., Елисеев А. П. Регулируемая селективность в многомодальном распознавании образов. Таврический вестник информатики и математики, 2008, том. 2, с. 89.

Моттль В.В., Татарчук А. И., Елисеев А. П. Многомодальное распознавание образов с регулируемой селективностью. Тезисы докладов международной научной конференции «Интеллектуализации обработки информации», Симферополь, 2008, с. 172.

Моттль В.В., Татарчук А. И., Елисеев А. П. Исследование методов комбинирования классификаторов и потенциальных функций в многомодальном распознавании образов. Тезисы докладов международной научной конференции «Интеллектуализации обработки информации», Симферополь, 2008, с. 176.

14. Mottl V., Tatarchuk A., Krasotkina O., Seredin O., Sulimova V.

Combining pattern recognition modalities at the sensor level via kernel fusion.

In: Multiple Classifier Systems. Lecture Notes In Computer Science, Vol.

4472. Springer-Verlag, Berlin \ Heidelberg. ISBN 978-3-540-72481-0, 2007, pp. 1-12.

Моттль В.В., Татарчук А. И., Красоткина О.В., Сулимова В.В. Комбинирование потенциальных функций в многомодальном распознавании образов. Математические методы распознавания образов. 13-я Всероссийская конференция: Сборник докладов. М.: МАКС Пресс, 2007.

16. Valentina Sulimova, Vadim Mottl, Alexander Tatarchuk MultiKernel approach to on-line signature verification. // Proceedings of the Eighth IASTED International Conference on Signal and Image Processing, ACTA PRESS ANAHEIM, ISBN 978-0-88986-583-9, 2006, pp. 448-453.

В.В. Сулимова, В.В. Моттль, А.И. Татарчук. Автоматический выбор наиболее информативных фрагментов в задачах распознавания сигналов разной длительности. // Труды конференции «Интеллектуализация обработки информации»-2006, Алушта, стр. 152-154.

В.В. Сулимова, В.В. Моттль, А.И. Татарчук. Автоматический выбор наиболее информативных фрагментов в задачах распознавания сигналов разной длительности. // Таврический вестник математики и информатики – № 1, 2006, стр. 109-115.

Структура работы. Диссертация состоит из введения, четырех глав, заключения, приложения и списка литературы. Материал изложен на 125 страницах, содержит 2 леммы, 15 теорем, 15 рисунков, 8 таблиц и список литературы из 21 наименования.

ПРОБЛЕМА СЕЛЕКТИВНОГО КОМБИНИРОВАНИЯ

ПРИЗНАКОВ В ЛИНЕЙНЫХ МЕТОДАХ ОБУЧЕНИЯ

РАСПОЗНАВАНИЮ ОБРАЗОВ

Помимо гиперплоскости (2) одним из ключевых понятий линейного подхода является решающая функция (decision score function) Важность этого понятия определяется, с одной стороны тем, что решающая его проекции x () на гиперплоскость (2) с учетом знака в смысле метриn ки (1) (рис. 1).

Рисунок 1. Расстояние от объекта до разделяющей гиперплоскости.

С другой стороны, итоговое суждение о классе y() объекта определяется знаком решающей функции (3) Концепция оптимальной разделяющей гиперплоскости для 1.1. обучающей совокупности: Метод опорных векторов Пусть задана обучающая совокупность объектов с указанием индексов классов, к которым они принадлежат:

Степень несоответствия значения решающей функции d (x | a, b) для виде функции потерь. В частности, нас далее будет интересовать функция потерь специального вида:

где y y() - истинный класс объекта, d d (x | a, b) - значение решающей функции (3), а 0 - параметр, который далее будем интерпретировать как зазор разделения двух классов объектов.

Функция потерь такого вида была впервые предложена Вапником В.Н. и Червоненкисом А.Я. и привела к методу обобщенного портрета [2], а затем к известному методу опорных векторов [1].

Такая функция потерь (рис. 2) имеет нулевой штраф ( y, d | ) 0 для объектов, удаленных от гиперплоскости на достаточное расстояние yd, и линейно растущий штраф ( y, d | ) 1 yd для объектов слишком близко приблизившихся к границе классов или попавших в область другого класса yd.

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

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

Такое требование эквивалентно невыпуклой оптимизационной задаче:

В случае линейно неразделимой обучающей выборки (5) ненулевые значения функции потерь (6) соответствуют объектам, нарушившим границу зазора, определяемой положением гиперплоскости (a, b) и параметром функции потерь 0 (рис. 4).

Рисунок 4. Ненулевое значение функции потерь для объекта обучающей совокупности, нарушившего границу зазора.

В качестве критерия обучения естественно искать такую гиперплоскость, которая бы разделяла обучающую выборку на два класса, с одной стороны, с как можно большей величиной зазора 0, 1 2 min, а с другой, с как можно меньшей величиной суммарного штрафа для ошибочно классифицированj 1 (1 ) y j (aT x j b), требований к процессу обучения выражается оптимизационным критерием где C - структурный параметр, определяющий соотношение требований максимизации зазора и минимизации величины эмпирического риска. Это и есть исходный критерий обучения, получивший название метода опорных векторов.

Правда, критерий (8) не очень удобен, поскольку имеет вид задачи множество. Классический критерий получается из (8) простой заменой Этот простой и в то же время очень эффективный способ обучения распознаванию двух классов объектов путем решения задачи квадратичного программирования (минимизации квадратичной функции при линейных ограничениях) был предложен Вапником В.Н. [1] и получил за прошедшие годы огромную популярность как метод опорных векторов (Support Vector Machine). Его название объясняется тем, что, как показывает элементарное разделяющей гиперплоскости (a, b, ) arg min J SVM (a, b, | C ) согласно (9) есть линейная комбинация векторов признаков объектов обучающей совокупности где j 0, j 1,..., N – решения двойственной задачи квадратичного программирования имеющих смысл множителей Лагранжа при ограничениях-неравенствах гиперплоскости и вся решающая функция опорных векторов определило его практическую популярность, поскольку после обучения для распознания распознавания класса нового объекта достаточно вычислить скалярное произведение xT x (12) лишь для опорных объектов обуj чающей совокупности (рис. 5).

Рисунок 5. Опорные объекты обучающей выборки.

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

Первый подход [7] основан на калибровке по обучающей выборке монотонного преобразования значений решающей функции (12) в единичный интервал [0,1]. Такой способ хорошо зарекомендовал себя на практике, однако не смог удовлетворить потребности научного сообщества изложить метод опорных векторов с вероятностных позиций. Второй подход [8] заключается в переосмыслении самой задачи обучения метода опорных векторов (9) через вероятностные суждения о модели порождения данных. Ключевая идея сводится к интерпретации критерия оптимизации метода опорных векторов (9) в виде задачи максимизации логарифмированной апостериорной плотности распределения (Maximum A Posterior estimation, MAP) параметров неизвестной гиперплоскости Первое слагаемое D(a, b) exp(0.5aT a 0.5b2 B2 ) в целевой функции критерия (13) отвечает за априорное суждение об искомых параметрах, которое выражается в предположении, что параметры гиперплоскости (a, b) попарно независимы и априори имеют нормальное распределение с единичными дисперсиями, и нулевыми математическими ожиданиями.

Второе слагаемое в (13) является логарифмированной функцией правдоподобия реализации обучающей выборки, выраженной непосредственно через функцию апостериорной вероятности Q( y | x, a, b) принадлежности объекта обучающей выборки x к его классу y {1,1} Однако такой крайне прямолинейный способ интерпретации второго слагаемого критерия обучения (9) обладает явным недостатком, заключающийся в том, что значения функции Q( y | x, a, b) строго говоря нельзя называть вероятностями, поскольку они не удовлетворяют естественному требованию Q( y 1| x, a, b) Q( y 1| x, a, b) 1. Действительно исключая ситуации | aT x b | 1, что вынудило авторов предпринимать дополнительные меры по нормализации вероятностной модели.

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

1.2 Проблема переобучения при обучении в признаковом пространстве большой размерности Природа переобучения в линейном пространстве признаков 1.2. Метод опорных векторов в своей классической постановке (9) изначально наделен простым, но очень мощным регуляризационным механизмом, ограничивающим свободу выбора решающего правила и, который, по сути, и определил высокую эффективность, и большую популярность метода. Этот механизм заложен в само определение функции потерь (6) и принципы обучения (7), (8) и (9), который предполагает выбирать предпочтительно те гиперплоскости, которые обеспечивают разделение выборки с наибольшим зазором 0. Влияние такой регуляризации на обобщающую способность обучения имеет фундаментальное теоретическое обоснование в статистической теории обучения, разработанной В.Н. Вапником и А.Я. Червоненкисом [1,9,10]. Ключевым понятием этой теории является размерность ВапикаЧервоненкиса (VC-dimension), которая численно характеризует разнообразие выбранного семейства решающих функций, в нашем случае семейства гиперплоскостей, в котором при обучении по заданной обучающей совокупности производится поиск оптимального решения. Фактически под размерностью Вапика-Червоненкиса понимается максимальное количество объектов l, которое возможно разделить на два класса всеми возможными 2l способами с помощью решающей функций из выбранного семейства. Нетрудно показать, что для семейства гиперплоскостей (разделяющих выборку с нулевым размерность Вапика-Червоненкиса равна n 1. В частности, в зазором) в n двумерном пространстве любые 3 точки еще можно разделить прямыми линиями на два класса всеми восьмью способами, а уже 4 точки - нельзя. Это означает, что при достаточно большой размерности признакового пространства для любой обучающей выборки фиксированного размера всегда можно найти подходящую гиперплоскость, которая разделить ее на два класса без единой ошибки. Именно поэтому в подобных ситуациях прямая минимизация эмпирического риска становится мало продуктивной и для решения задачи исследователь вынужден прибегать к дополнительным механизмам регуляризации обучения или, другими словами, к поиску способов ограничения свободы выбора итоговой решающей функции.

Развиваемая в диссертации вероятностная методология обеспечения селективности обучения опирается на тот факт [10], что для оптимальной гиперплоскости, разделяющей без ошибок заданную обучающую совокупность размера N на два класса с зазором 0, справедлива следующая оценка математического ожидания вероятности ошибки на генеральной совокупности (в среднем по всем обучающим совокупностям заданного размера):

где m - количество опорных векторов (объектов выборки), R - радиус минимальной сферы, содержащей все данные наблюдения, и n - размерность признакового пространства, в котором производится поиск оптимальной разделяющей гиперплоскости.

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

Во-первых, представление оптимальной гиперплоскости относительно небольшим количеством m опорных векторов (объектов выборки), вовторых, разделение выборки с наибольшим зазором между объектами разных классов и, в-третьих, обучение в признаковом пространстве небольшой размерности n.

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

Существующие способы отбора признаков в методе опорных 1.2. 1.2.2.1 1-norm SVM (Lasso SVM) Одной из первых и наиболее известных модификаций критерия метода опорных векторов (9), наделившая этот метод свойством селекции признаков непосредственно в процессе обучения, стал метод 1-norm SVM [11], имеющий критерий обучения:

Такой оптимизационный критерий представляет собой частный случай целевой функции общего вида от классического метода опорных векторов (9) исключительно видом первого слагаемого Такую функцию принято называть штрафом Lasso, а квадратичный штраф a метода опорных векторов (9) - штрафом Ridge.

Критерий (15) имеет склонность в точке минимума (a, b, ) присваивать строго нулевые значения большинству компонент направляющего вектора ai 0, реализуя при этом на практике разумный выбор подмножества полезных для распознавания признаков. С момента своего появления, метод обучения 1-norm SVM (15) неоднократно демонстрировал свое преимущество по сравнению с классическим методом опорных векторов (9) при решении практических задач, содержащих большое количество мало полезных для распознавания признаков при относительно небольшой по размеру обучающей выборке.

1.2.2.2 Doubly Regularized SVM (Elastic Net SVM) Несмотря на свою эффективность, метод 1-norm SVM имеет два существенных недостатка [12]. Во-первых, если исходное множество признаков содержит группу сильно линейно зависимых признаков (имеющих высокую попарную корреляцию), то такой способ обучения (15) старается в итоговом решении оставить только один из этих признаков, подавляя все остальные.

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

Дальнейшее развитие селективных свойств метода опорных векторов получило в работе [12], в которой авторы вместо функции штрафа Lasso применили функцию штрафа Elastic Net, предложенную ранее для регуляризации задачи восстановления числовой зависимости [13]. Штраф Elastic Net представляет собой линейную комбинацию квадратичного штрафа Ridge где 1 и 2 - неотрицательные параметры.

Критерий обучения с функцией штрафа Elastic Net получил название Doubly Regularized SVM (DrSVM) и учитывая (17) имеет вид:

В отличие от метода 1-norm SVM (15) такой способ обучения обладает эффектом группировки (grouping effect), который выражается в стремлении либо удалять из решения, либо оставлять в решении сразу все признаки, имеющие высокую линейную попарную корреляцию. Кроме того, количество активных в решении признаков не ограничено размером обучающей выборки. Как следствие, такой способ обучения (18) продемонстрировал лучшую, в сравнении с 1-norm SVM, обобщающую способность на модельных и практических задачах [12].

В дальнейшем изложении результатов диссертации будет использоваться эквивалентная запись критерия обучения (18) 1.2.2.3 Elastic SCAD SVM Другим примером попытки усовершенствовать метод опорных векторов (9) наделением его селективными свойствами за счет выбора особого вида функции штрафа на компоненты направляющего вектора является работа [14]. Авторами предложена функция штрафа, которая является комбинацией квадратичного штрафа Ridge метода опорных векторов (9) и невыпуклого штрафа SCAD [15]:

где 1, 2 и 3 - неотрицательные структурные параметры, scad (ai | 2, 3 ) функция штрафа SCAD Однако авторами метода не приводится какого-либо теоретического обоснования такого выбора штрафа и его преимуществ по сравнению с уже зарекомендовавшими себя штрафами Lasso и Elastic Net. Экспериментальное исследование, проведенное авторами, к сожалению, также не продемонстрировало какого-либо заметного превосходства предлагаемого подхода. В связи с этим, в диссертации не будет подробно рассматриваться функция штрафа Elastic SCAD и основанный на нем метод обучения Elastic SCAD SVM.

Свойства методов отбора признаков и недостаточность 1.2. существующих подходов Механизм селективности отбора признаков 1.2.3. Модификации метода опорных векторов, исследуемых в диссертации, отличаются друг от друга только видом штрафа на компоненты направляющего вектора в целевой функции соответствующих критериев (9), (15) и (19).

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

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

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

Известные формулировки критериев обучения SVM (9), Lasso SVM (15) и Elastic Net SVM (19) в том виде, в котором они были предложены авторами, предполагают поиск такого направляющего вектора a, для которого будет наименьшей. Однако здесь важно отметить, что величина эмпиричеN висит и от его нормы (aT a)1 2, непосредственно определяющей величину зазора 2 2(aT a)1 2, с которым разделяется обучающая выборка. Для анализа селективных свойств критерия обучения необходимо в первую очередь разделить механизмы селекции направлений и максимизации зазора. Такое разделение (8) уже было сделано в этой главе для классического метода опорных векторов (9). Действительно, в критерии (8) величина зазора входит в критерий как отдельная переменная оптимизации, а область поиска направляющего вектора ограничена сферой aT a 1 единичного радиуса. При такой эквивалентной записи (8) известного критерия (9) выбор направляющего вектора определяет исключительно ориентацию разделяющей гиперплоскости и в силу фиксированной нормы aT a 1 не несет в себе информацию о величине зазора, с которым разделяется обучающая выборка.

Выпишем критерий (8) еще раз, поделив целевую функцию на значение структурного параметра C 0 :

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

Формализуем этот подход. Для этого запишем критерий обучения (20) с функцией штрафа в самом общем виде где V (a, | C ) - штраф, отвечающий за максимизацию зазора и селекцию направлений a, причем в (20) этот штраф не зависит от a, C - структурный параметр обучения.

обучения штрафуются сильнее всего с точки зрения выбранной функции штрафа V (a, | C ), будем называть «наихудшими» направлениями а направления, которые слабее всего – «наилучшими» направлениями В качестве количественной оценки способности функции штрафа различать «наихудшие» и «наилучшие» направления между собой естественно оценивать уровень селективности (selectivity level – SL ), рассчитываемый как разность максимального и минимального значений штрафа для «наихудших» и «наилучших» направлений соответственно:

Тогда для критерия метода опорных векторов (20) получим и очевидно, что справедливы следующие утверждения:

вень селективности SL (23) для штрафа (24), учитывая (25) и (26), будет наименьшим из возможных, т.е. равным нулю что показывает полное отсутствие селективности у классического метода опорных векторов.

Нетрудно проверить, выполнив простейшую замену переменных a a, b b и домножив целевую функцию (15) на величину параметра C 0, что оптимизационная задача эквивалентна критерию обучения метода 1-norm SVM с функцией штрафа Lasso.

Однако теперь, в отличие от критерия метода опорных векторов (20), каждое направление штрафуется слагаемым C 11 i1| ai |, и это слагаемое для фиксированных и C принимает разные значения для разных направлеa :|| a || 1}, причем это различие не зависит от выборки, предъний n явленной для обучения. Кроме того, именно в такой постановке становится понятным другое свойство метода 1-norm SVM, которое неочевидно при классической записи критерия (15). Заметим, что чем больше зазор, тем меньший вклад в значение целевой функции делает первое слагаемое C 11 i 1| ai |, и, следовательно, тем меньше выражено предпочтение одних направлений перед другими.

Действительно, для метода 1-norm SVM имеем и нетрудно проверить, что справедливы следующие утверждения:

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

ние в решающую функцию сразу всех признаков с одинаковыми по модулю весами | a1 |... | an | n1 2 (компонентами направляющего вектора). Эти множества не зависят ни от величины зазора, с которым разделяется выборка, ни от значения структурного параметра обучения C, являясь фундаментальным свойством механизма селективности функции штрафа Lasso, а, следовательно, и критерия обучения метода 1-norm SVM.

Уровень селективности SL (23) для штрафа Lasso (28), учитывая (29) и (30), будет равен Кроме того, из (31) нетрудно увидеть, что величина «различимости направлений» (уровень селективности) уменьшается с ростом величины зазора, что характеризует способ балансировки двух разных механизмов регуляризации (отбора признаков и максимизации зазора) в методе Lasso SVM. На рисунке 6 графически проиллюстрирована зависимость уровня селективности (31) от величины зазора для n 2 и трех различных значений структурного параметра C.

Рисунок 6. Зависимость уровня селективности штрафа Lasso от величины зазора и параметра разделимости выборки C.

Аналогичным образом можно показать, что критерий обучения DrSVM (18), основанный на штрафе Elastic Net, эквивалентен оптимизационной задаче где Нетрудно проверить справедливость следующих утверждений:

Тогда уровень селективности согласно (23) определяется выражением Таким образом, для методов 1-norm SVM, и DrSVM множества «наилучших»

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

Использование штрафов Lasso и Elastic Net фактически означает принятие специальной априорной гипотезы о модели порождения данных, которая сводится к предположению, что объекты «скорее всего» не будут представлены близкими по полезности для распознавания признаками. Следовательно, в ситуациях, когда в исходных данных есть такие признаки, обучение методами 1-norm SVM и DrSVM может приводить к снижению обобщающей способности полученных решающих функций.

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

Эффект группировки признаков 1.2.3. В работе [12] в качестве основного недостатка метода 1-norm SVM (15) указывается тот факт, что метод полностью игнорирует при отборе признаков их взаимную линейную зависимость (попарную корреляцию), оставляя в решении только лишь небольшое (не больше количества объектов в обучающей выборке) подмножество признаков, полностью подавляя все остальные.

Такое свойство метода обучения является неприемлемым для ряда прикладных задач, в частности, при анализе экспрессии генов с использованием микрочипов (microarray analysis), поскольку уровни экспрессии генов, которые отвечают за один и тот же биологический механизм, как правило, сильно линейно зависимы, и все такие гены вносят свой вклад в биологический процесс. Поэтому в работе [12] идеальным назван такой метод, который бы эффективно подавлял незначимые для распознавания гены и автоматически включал бы в итоговое решение все взаимосвязанные. Предлагаемый в работе [12] метод DrSVM (19), в отличие от 1-norm SVM, отчасти обладает желаемым свойством, которое выражено в виде утверждения, что чем больше корреляция jl между признаками с индексами j и l, тем меньше будут отличаться в итоговом решении соответствующие коэффициенты a j и al направляющего вектора:

Здесь N – размер обучающей выборки, 2 - структурный параметр регуляризации критерия обучения (18) при квадратичном штрафе. Такое свойство метода было названо эффектом группировки или grouping effect, как в оригинальной публикации.

Заметим, что свойство группировки одинаково работает как для полезных генов или, в общем случае, признаков, так и для признаков, которые не несут никакой информации для решения задачи, но тоже участвуют в процессе обучения. Т.е. метод DrSVM будет «стараться» либо удалять все такие «шумовые признаки», либо наоборот оставлять такую группу целиком. Последний случай, очевидно, не может способствовать увеличению обобщающей способности распознавания и интерпретации итогового решения с точки зрения содержания прикладной задачи. Другими словами, и метод DrSVM, и Lasso SVM являются представителями крайних подходов к обучению, которые либо наделяют процесс обучение эффектом группировки, либо полностью от него избавляют.

Одной из задач данной диссертации является дальнейшее развитие идеи группировки попарно зависимых признаков. Один из предлагаемых в работе методов обучения, а именно, метод опорных признаков (раздел 3.3), разрабатывается именно для того, чтобы обеспечить эффект избирательной группировки признаков (раздел 3.4.2). Избирательность предлагаемого метода выражается в стремлении сохранять в итоговом решении только попарно зависимые признаки, обладающие достаточной значимостью для распознавания, аналогично DrSVM, и в максимальном подавлении всех остальных малозначимых признаков, независимо от их попарной зависимости, аналогично Lasso SVM.

1.3 Предлагаемая концепция: Байесовский подход к одновременному построению разделяющей гиперплоскости и выбору подмножества релевантных признаков В диссертации предлагается специальная байесовская постановка обучения распознаванию двух классов объектов в линейном признаковом пространстве, приводящая к обобщению метода опорных векторов и являющаяся теоретической основой для создания новых селективных методов обучения. Основная идея байесовской постановки заключается в построении простейшей системы вероятностных предположений о паре плотностей распределения объектов двух классов, определяемой объективно существующей, но неизвестной гиперплоскостью в линейном пространстве признаков, при некотором априорном предположении о ее случайном выборе. В диссертации предлагаются и детально рассматриваются две частные априорные модели случайного направляющего вектора разделяющей гиперплоскости, позволяющие в процессе обучения количественно различать его компоненты, а, следовательно, и исходные признаки, по степени их полезности для распознавания двух заданных классов объектов, управляя при этом степенью селективности такого различия. Эти две модели приведут к двум разным методам обучения с отбором полезных признаков, один из которых назван методом релевантных признаков с управляемой селективностью (метод RFM), а второй – методом опорных признаков с управляемой селективностью (метод SKM).

1.4 Основные задачи

исследования Для реализации изложенной концепции в данной диссертации сформулированы и решены следующие задачи:

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

Разработка математической постановки общей вероятностной задачи обучения двухклассовому распознаванию объектов двух классов в линейном пространстве признаков.

Разработка частных априорных вероятностных моделей генеральной совокупности в терминах совместного априорного распределения компонент направляющего вектора разделяющей гиперплоскости, отражающих две принятые в мировой литературе стратегии отбора признаков – взвешивания всех исходно заданных признаков (feature weighting) и жесткого выбора их подмножества (feature subset selection).

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

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

БАЙЕСОВСКИЙ ПОДХОД К ПОИСКУ ОПТИМАЛЬНОЙ

РАЗДЕЛЯЮЩЕЙ ГИПЕРПЛОСКОСТИ

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

2.1 Параметрическое семейство пары плотностей распределения, определяемое гиперплоскостью Свяжем с этой гиперплоскостью пару параметрических семейств условных плотностей распределения вероятностей вектора признаков случайного фиксированного индекса его класса y {1,1}, определяемых параметрами a, b, c. Эти два семейства призваны выражать предположение, что случайные векторы признаков объектов двух классов распределены главным образом в «своих» полупространствах aT x b 0 и aT x b 0, однако могут попадать и в «чужие» полупространства, причем степенью возможности несобственные плотности, не образующие единичных интегралов по всему Некорректность несобственной пары плотностей (34) не приводит далее к математическим противоречиям, поскольку они участвуют только в формуле Байеса [16].

Кроме того, несобственность плотностей может легко быть устранена формулированием семейства (34), например, в виде:

где d, h 0 - параметры внешних границ распределения.

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

Пара плотностей распределения (34), сконцентрированных в основном «равномерно» по разные стороны заданной гиперплоскости, выражает предположение, что единственное знание о двух классах объектов заключается в их расположении преимущественно по разные стороны заданной гиперплоскости. Наглядное представление о такой паре плотностей распределения дает рисунок 7.

Рисунок 7. Графическое представление параметрического семейства плотностей распределения (34) двух классов объектов в двумерном пространстве.

Общий действительный параметр обеих плотностей c 0, определяющий степень возможности попадания вектора признаков объекта определенного класса в «чужое» полупространство (рис. 8), является структурным параметром, имеющим известное заданное значение.

Рисунок 8. Графическое представление параметрического семейства плотностей распределения двух классов объектов в проекции на направляющий вектор разделяющей гиперплоскости.

Будем далее предполагать, что получена обучающая совокупность образованная векторами признаков x j ( xij, i 1,..., n) с известными индексами классов y j. Тогда совместное условное распределение обучающей совокупности ( X | Y ) представимо в виде произведения плотностей (34):

2.2 Априорное распределение параметров гиперплоскости Другим ключевым предположением в предлагаемой вероятностной модели является суждение об априорном совместном распределении (a, b) параметров (a, b) разделяющей гиперплоскости aT x b 0. Будем считать, что отсутствуют какие-либо априорные предпочтения величин порога разделяющей гиперплоскости b, тогда:

2.3 Общий байесовский критерий обучения для параметрического семейства пары плотностей распределения Апостериорная плотность распределения P(a, b| X,Y, ) параметров (a, b) относительно обучающей совокупности ( X,Y ) определяется формулой Байеса:

Понимание обучения как задачи максимизации этой апостериорной плотности распределения в пространстве параметров модели (a, b) приводит к очевидному критерию:

распределения наблюдений (34)-(36) является основным теоретическим предложением данной диссертации. Следующая теорема, доказанная в диссертации, показывает, что этот критерий представляет собой обобщение классического метода опорных векторов.

Теорема 1. Критерий обучения (39) для семейства распределений (34)и априорного распределения параметров (37) эквивалентен оптимизационной задаче минимизации целевой функции J (a, b1 N | c) на выпуклом множестве, заданном набором линейных ограничений-неравенств для объектов обучающей совокупности:

Доказательство теоремы приведено в приложении на с. 96.

По своей структуре оптимизационный критерий (40) отличается от классического критерия опорных векторов (9) только слагаемым ln (a) вместо квадрата нормы направляющего вектора искомой разделяющей гиперплоскости aT a i 1 ai2. Параметр c 0 семейств распределений (34), отвечающий за способность объектов генеральной совокупности нарушать границу своих классов, регламентирует приоритет между качеством разделения обучающей совокупности и априорными предпочтениями по выбору направляющего вектора.

J (a, b1 N | c) в (40) строго выпукла. Поскольку система ограничений в (40) (a, b, 1,..., N ) предлагаемый в диссертации обобщенный критерий обучения по методу опорных векторов в общем виде представляет собой единственный набор оптимальных параметров (a, b), удовлетворяющий всем ограничениям задачи (40) и доставляющий минимум целевой функции J (a, b1 N | c).

Результатом обучения по обучающей совокупности (35) является решающее правило классификации d (x) aT x b 0 (4), применимое к 2.4 Апостериорные вероятности классов объектов формулировки задачи обучения является тот факт, что вероятностное предположение об условном распределении векторов признаков случайных объектов (34), выражающее основную специфику метода опорных векторов, позволяет интерпретировать полученное решающее правило не только как суждение о классе нового объекта, но и наделить это суждение естественной оценкой его «уверенности».

Действительно, примем дополнительное предположение, что случайно появившийся новый объект, не содержащийся в обучающей совокупности, объективно принадлежит тому или иному классу с некоторыми априорными вероятностями Тогда, для параметров разделяющей гиперплоскости (a, b), найденных как решение задачи обучения (40), апостериорная вероятность принадлежности объекта x к классу y 1 определяется формулой Байеса через плотности расn пределения двух классов (x a, b, y; c) :

Для простоты дальнейших рассуждений примем, в частности, равными априорные вероятности двух классов q1 q1 1 2 1. Тогда Выбор различных априорных вероятностей классов q1 q1 1 отражает другое предположение об их свойстве в сравнении с выбором различных значений параметра пересечения классов c 0, характеризуя их разнонаполненность. В данной работе роль априорных вероятностей классов (q1, q1 ) как параметров вероятностной модели детально не исследуется.

Теорема 2. Для условных плотностей распределения (34) и для случая равных априорных вероятностей q1 q1 1 2 апостериорные вероятности классов (42) будут иметь вид сигмоидоподобной функции Доказательство теоремы приведено в приложении на с. 97.

сигмоидоподобного обобщения (43) ступенчатой решающей функции Соответствующая зависимость апостериорной вероятности (43) от значения решающей функции d (x | a, b) aT x b показана на рисунке 9.

1 exp(c)exp c(a x b) Рисунок 9. Апостериорные вероятности классов для вновь поступившего объекта в вероятностной интерпретации метода опорных векторов.

2.5 Частные априорные модели разделяющей гиперплоскости Классический метод опорных векторов: Частный случай 2.5. нормальных априорных распределений компонент направляющего вектора с одинаковыми дисперсиями случайный направляющий вектор образован независимыми компонентами a (a1,..., an ) с нормальными плотностями распределения, имеющими нулевое математическое ожидание и одинаковые дисперсии r1... rn r. Тогда и задача обучения (40) примет вид классического критерия обучения по методу опорных векторов (9), в котором коэффициент C 2rc.

Заметим, что в диссертации автором впервые предложена формальная интерпретация структурного параметра C в методе опорных векторов как относительной степени пересечения классов по сравнению с общей априорной дисперсией компонент направляющего вектора C 2cr. В такой интерпретации нет смысла рассматривать иные значения априорной дисперсии, нежели r 1 2, тогда C c определяется степенью «пересечения»

областей концентрации распределений объектов двух классов (34).

Известные методы 1-norm SVM (Lasso SVM) и Doubly Regularized 2.5. Более общий метод Elastic Net SVM получается из задачи обучения (40) при предположении, что случайный направляющий вектор образован которых определяются одинаковыми значениями параметров (, ). Здесь нормирующая константа определяется обоими параметрами2:

где (u ) exp dz – функция Лапласа.

В этом случае совместная априорная плотность распределения направляющего вектора определяется выражением и предлагаемая в диссертации задача обучения (40) примет вид, эквивалентный методу Doubly Regularized SVM (19):

В еще более частном случае, когда 0, получается метод обучения 1-norm SVM (Lasso SVM):

Этот критерий эквивалентен (15) при интерпретации независимых компонент случайного направляющего вектора a (a1,..., an ) как распределенных по закону Лапласа (ai | r ) (2r )1 2 exp (r 2)1 2 | ai |.

оптимизации, они детально исследованы в работах [11,12,17]. Заметим лишь, что в силу специфики принятых априорных распределений критерии (45) и (46) обладают чрезвычайно важным свойством беспереборного отбора признаков непосредственно в ходе обучения. Это свойство является Это утверждение доказано Е.О. Черноусовой.

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

Исследование и дальнейшее развитие методологии отбора признаков в предложенных выше вероятностных терминах является одной из задач данной диссертации. Заметим, что целевые функции критериев селективного обучения J DrSVM (a, b, 1 N| c,, ) (45) и J1nSVM (a, b, 1 N| c, r ) (46), как и J SVM (a, b, 1,..., N | C ) (9), представляют собой взвешенные суммы эмпиричеN торов (SVM), и той или иной функции регуляризующего штрафа, интерпретируемого в предложенной обобщенной постановке задачи SVM (40) как логарифм априорного распределения направляющего вектора дискриминантной гиперплоскости ln (a).

БАЙЕСОВСКИЙ ПРИНЦИП УПРАВЛЕНИЯ СЕЛЕКТИВНОСТЬЮ

КОМБИНИРОВАНИЯ ПРИЗНАКОВ

3.1 Обобщение метода опорных векторов: Частный случай нормальных априорных распределений компонент направляющего вектора с разными известными дисперсиями В диссертации предлагается естественное обобщение классического метода опорных векторов за счет введения в его вероятностную постановку дополнительного предположения о том, что независимые компоненты направляющего вектора a (a1,..., an ) распределены по нормальному закону с разными известными дисперсиями ri 0, i 1,..., n и, как и прежде, с нулевыми математическими ожиданиями.

Совместная априорная плотность распределения направляющего вектора определяется выражением В этом случае и задача обучения (40) примет вид где C 2c.

Предложенный в диссертации оптимизационный критерий (50), являясь частным случаем критерия (40), представляет собой, тем не менее, обобщение метода опорных векторов (9) в случае взвешенных компонент лее показано, что такая постановка задачи обучения позволяет управлять «степенью участия» отдельных признаков ( x1,..., xn ) в решающем правиле распознавания вплоть до почти полного подавления некоторых из них - чем меньше априорная дисперсия ri 0, тем меньше участие i -го признака. Этот факт выражается следующей теоремой о решении задачи (50).

Теорема 3. В точке минимума критерия (50) значения компонент направляющего вектора a (a1,..., an ) где j 0 - множители Лагранжа при ограничениях-неравенствах, определяемые решением двойственной задачи квадратичного программирования Оптимальное значение порога определяется выражением Доказательство теоремы приведено в приложении на с. 98.

Из утверждения (51) этой теоремы хорошо видно, что «масштаб» i -й компоненты направляющего вектора напрямую определяется значением соответствующей априорной дисперсии ri. Соответственно, решающее правило распознавания, полученное в результате обучения и применимое к новому объекту с вектором признаков x ( x1,..., xn ), будет зависеть главным образом от признаков с большими значениями ri и почти игнорировать остальные признаки:

Структура решающего правила (54), полученного по методу опорных векторов со взвешенными компонентами направляющего вектора (50), дает инструмент управления участием признаков x ( x1,..., xn ) в процессе обучения. Чем больше принятое значение априорной дисперсии ri некоторой компоненты направляющего вектора относительно дисперсий других компонент, тем большее влияние i -й признак оказывает на решение о классе объекта.

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

3.2 Метод релевантных признаков с регулируемой селективностью Параметрическое семейство априорных нормальных-гамма 3.2. распределений компонент направляющего вектора со случайными дисперсиями Предлагаемый в диссертации метод основан на предположении, что дисперсии (r1,..., rn ) компонент направляющего вектора a (a1,..., an ) (47) являются независимыми случайными величинами, характеризующимися некоторым априорным распределением и подлежащими оцениванию в процессе обучения по байесовскому принципу вместе с параметрами разделяющей гиперплоскости (a, b). В литературе подобные дополнительные априорные предположения о параметрах, участвующих в некотором ранее принятом априорном предположении, принято называть Hyper Prior Assumptions.

Удобнее оперировать не дисперсиями ri, а обратными к ним величинами 1 ri, называемыми мерами точности (precision measures) соответствующих случайных величин [16], предполагая, что обратные дисперсии имеют одно и то же априорное гамма-распределение:

здесь 0 и 0 – параметры гамма-распределения, вопрос о выборе которых будет рассмотрен ниже в параграфе 3.2.3.

По-прежнему будем рассматривать параметрическое семейство нормальных совместных условных распределений параметров гиперплоскости относительно заданных дисперсий элементов направляющего вектора r (r1,..., rn )T (48):

Тогда, вместе с априорным распределением независимых дисперсий априорное распределение совокупности параметров (a, b, r) является произведением нормальных-гамма распределений [16]:

Как и прежде, будем исходить из условной плотности совместного распределения случайной обучающей совокупности относительно скрытых параметров (a, b) (36) где параметр априорной разделимости классов c в (34) полагается заданным.

Тогда по формуле Байеса, аналогично (38), апостериорное совместное распределение подлежащих оцениванию параметров модели (a, b, r) относительно обучающей совокупности примет вид:

Отождествляя обучение, как и прежде, с вычислением максимума апостериорной плотности параметров, мы придем к следующему критерию являющийся обобщением критерия обучения (39).

3.2. Теорема 4. Оптимизационная задача обучения (59) для (34), (49) и (57) эквивалентная критерию Доказательство теоремы приведено в приложении на с. 100.

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

Остальные признаки с бльшими весами ri предполагаются наиболее информативными (relevance features) для данной обучающей совокупности.

Параметры гамма распределения: Управление селективностью 3.2. Прежде чем говорить об алгоритме решения задачи оптимизации (60), исследуем вопрос, как значения параметров и влияют на вид априорного гамма-распределения обратных дисперсий компонент направляющего вектора (1 ri |, ) (1 ri )1 exp (1 ri ) (55).

Если m |, 0, априорные гамма распределения всех дисперсий ri сконцентрированы возле общего математического ожидания / (рис. 10-а).

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

При таких значениях параметров критерий (60) эквивалентен классическому критерию опорных векторов (9), использующему все признаки объектов.

Если же m |, 1, то априорные распределения становятся практически равномерными (рис. 10-б). При ri 0 соответствующее слагаемое целевой функции в (60) неограниченно уменьшается ln ri, и критерию выгодно уменьшать все дисперсии. Однако в этом случае невозможно чрезмерной селективности отбора признаков, подавляя большинство из них, даже полезные.

Рисунок 10. Вид гамма-распределения при малом (а) и большом (б) Управлять степенью селективности отбора признаков можно, варьируя значения параметров и в априорном распределении дисперсий. Будем выбирать значения двух параметров априорного гамма распределения и, задавая один общий параметр 0 :

В этом случае параметрическое семейство гамма распределений (55) будет иметь вид Нетрудно убедиться, что а также При увеличении от нуля до достаточно больших значений вид гаммараспределения плавно изменяется от сконцентрированного в окрестности 1 ri 1 до почти «равномерного» на неотрицательной полуоси (рис. 11).

0, Рисунок 11. Зависимость априорного гамма-распределения дисперсий компонент направляющего вектора от параметра.

плотность распределения обратных дисперсий:

Тогда совместная априорная плотность распределения параметров разделяющей гиперплоскости (48) и обратных дисперсий компонент направляющего вектора (63) запишется как Соответственно, совместное апостериорное распределение всех переменных модели относительно обучающей совокупности, аналогично (58), пропорционально произведению Отождествляя обучение, как и прежде, с вычислением байесовской оценки неизвестных параметров, мы придем к следующему критерию представляющему собой обобщение критерия (39).

Теорема 5. Оптимизационная задача обучения (64) для (48), (62) и (63) эквивалентна критерию где C 2c.

Доказательство теоремы приведено в приложении на с. 101.

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

При нулевом значении параметра 0 и, соответственно, 1, штрафы (1 ) (1 ri ) ln ri настолько велики, что все оценки дисперсий равны единицы r1... rn 1 в точке минимума критерия (65), который становится эквивалентным критерию классического метода опорных векторов, вообще не обладающего свойством селективности.

При неограниченном увеличении параметра априорное гамма распределение обратной дисперсии каждой компоненты направляющего вектора 1 ri (62) и их совместное априорное распределение (63) становятся практически «равномерными», соответственно, на положительной полуоси пределе приводит к исчезновению слагаемого ln G(r | ) в критерии (64) и штрафующего отклонение ri от единицы, и критерий становится чрезмерно селективным.

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

В связи с этим обстоятельством данный метод обучения назван методом релевантных признаков с регулируемой селективностью, или, полностью характеризуя метод, Selective Relevance Feature Support Vector Machine (RFM).

Эквивалентный критерий обучения 3.2. Критерий обучения метода релевантных признаков (65) может быть записан в эквивалентной форме, который не содержит параметров оптимизации (r1,..., rn ). Такая запись критерия будет удобна для последующего анализа свойств метода. Справедлива следующая теорема.

Теорема 6. Критерий обучения метода релевантных признаков (65) имеет эквивалентную формулировку где структурный параметр C 0 связан с аналогичным параметром критерия (65) выражением Доказательство теоремы приведено в приложении на с. 102.

3.2. Критерий обучения (65) несложно алгоритмически реализовать, применив метод Гаусса-Зайделя с поочередной оптимизацией по двум группам переменных (a1,..., an, b, 1,,..., N ) и (r1,..., rn ). При фиксированных (r1 rn ), оптимизация критерия (65) только по (a1 an b, 1 N ), что эквивалентно критерию (50), сводится к решению двойственной задачи квадратичного (ri0 1 i 1,, n), что соответствует стандартному методу опорных векторов.

После того, как на очередном шаге итерационного процесса k 0,1,2,...

найдено решение (1,..., k ) двойственной задачи для текущего приближения (r1k,..., rnk ), новые значения дисперсий (r1k 1,..., rnk 1 ) на следующем шаге определяются следующей теоремой.

Теорема 7. Новые значения дисперсий (r1k 1,..., rnk 1 ) определяются решением (1,..., k ) двойственной задачи (52) для текущего приближения (r1k,..., rnk ) согласно выражению Доказательство теоремы приведено в приложении на с. 104.

Итерационная процедура обучения обычно сходится за 10-15 шагов, а сам алгоритм демонстрирует способность подавлять неинформативные признаки за счет очень маленьких весов ri в решающем правиле (54). Оптимальное значение порога b k определяется, как и прежде, выражением (53).

В частности, из формулы (67) хорошо видно, что при нулевой селективности 0 оценки всех дисперсий тождественно равны единице ri k 11, и критерий (65) вырождается в обычный критерий опорных векторов, сохраняющий все признаки. При алгоритм подавляет все признаки ri k 1 0.

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

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

3.3 Метод опорных признаков с регулируемой селективностью Параметрическое семейство составных априорных распределений 3.3. для компонент направляющего вектора В разделе 3.2.1 в качестве априорного суждения о предпочитаемых значениях направляющего вектора a (a1,..., an ) было принято, что компоненты направляющего вектора независимы и нормально распределены с некоторым дополнительным суждением о параметрах такого распределения. В этом разделе будет рассматриваться другое предположение об априорном распределении (a) независимых компонент направляющего вектора a n Вид априорной плотности (a) представляет собой комбинацию распределения Лапласа при значениях нормы компонент, не превышающих заданного порога | ai |, и нормального распределения при бльших значениях | ai | (рис. 12):

где 0 - неотрицательный параметр.

В этом случае совместное априорное распределение направляющего вектора a (a1,..., an ) определяется выражением Запишем совместное априорное распределение в эквивалентном виде Рисунок 12. Зависимость функции q(ai | ) априорного распределения компонент направляющего вектора (ai | ) от параметра.

Логарифм такого распределения имеет вид 3.3. Вид совместного априорного распределения (70) и обобщенный критерий обучения метода опорных векторов (40) полностью определяют вид оптимизационной задачи обучения Для логарифма априорного распределения (71) критерий (40) примет эквивалентный вид Величина порога 0 плотности (68) выполняет роль параметра селективности обучения и при 0 q(ai ) ai2 оптимизационный критерий (72) эквивалентен критерию метода опорных векторов с минимальной способностью к отбору признаков, а при достаточно больших значениях селективности 0 q(ai ) | ai | - критерию (46) методу 1-norm SVM, с увеличивающейся селективностью обучения по мере увеличения относительно параметра C до полного подавления всех признаков.

Двойственная задача обучения 3.3. Для произвольной обучающей выборки {( xij, i I ), y j, j 1,..., N}, где I {1,..., n} - множество индексов признаков объектов, задача (72) является выпуклый многогранник.

Обозначим через j 0 и j 0 множители Лагранжа при ограничениях задачи (72), соответственно, y j (aT x j b) 1 j и j 0. Можно показать, что задача (72) является регулярной [19], и, как следствие, она эквивалентна задаче поиска седловой точки соответствующей функции Лагранжа (74), то ее левая часть (ai, i I, b, j, j 1,..., N ) является решением задачи (72) и наоборот.

Запишем функцию Лагранжа (74) в эквивалентном виде, как сумму функций, зависящих только от своих переменных Ведем обозначение Функция Лагранжа примет вид Для того чтобы сформулировать двойственную задачу необходимо определить, как минимальное значение Li (ai, | ) по переменной ai зависит от множителей Лагранжа j для каждого i I. Поскольку эти функции содержат недифференцируемые (выпуклые) функции q(ai | ), то это приводит к необходимости воспользоваться понятиями суградиент и субдифференциал вместо обычного градиента для того, чтобы определить условия минимума выпуклой функции [19].

функции f :

выполнено для любой точки a.

ной точке.

из:

если 0 | ai |.

если ai 0.

Доказательство леммы приведено на с. 105.

Лемма 2. Минимум каждой функции Li (ai, | ) по переменной ai достигается в точках В каждой такой точке Доказательство леммы приведено на с. 105.

Справедлива следующая теорема о двойственной задаче.

Теорема 8. Оптимизационная задача квадратичного программирования является двойственной для задачи (72).

Задача (80) может быть записана в эквивалентном виде Доказательство теоремы приведено на с. 106.

Задача (81) относится к более широкому классу задач, который в литературе принято называть задачами квадратичного программирования с квадратичными ограничениями (QCQP) [20]. Для решения задач, подобных двойственной задаче (80), существует множество стандартных алгоритмов и программных решений, способных эффективно находить численное решение.

Подобные алгоритмы в диссертации рассматриваться не будут.

Итоговое решающее правило и опорные признаки 3.3. Предположим, что оптимизационная задача (80) или (81) решена. Для 1 0,..., N 0, значения вспомогательных множителей 1 0,..., N 0 можно опустить. В соответствии с (78) найденное решение разделяет все множество признаков на три непересекающихся множества I I I 0 I или в эквивалентной форме Учитывая (78) получим Таким образом, решение двойственной задачи полностью определяет значения компонент направляющего вектора ai, попадающих в множества I и I. Что же касается компонент, попадающих в множество I 0, то для них не определены пока коэффициенты i в (83). Кроме того, не определено значение сдвига разделяющей гиперплоскости.

Теорема 9. Итоговое оптимальное решающее правило, определяемое решением задачи (72), имеет вид дополнительной задачей линейного программирования Доказательство. Для доказательства утверждения (84) и (85) достаточai xi b 0 и в исходную задачу (72) оптимальные значения ai (78).

Теорема доказана.

После того, как найдены решения двойственной задачи (81) и дополнительной задачи (85), исходная задача обучения (72) решена полностью, т.е.

найдены коэффициенты 1 0,..., N 0 и 0 i 0, i I 0, определяющие компоненты направляющего вектора оптимальной разделяющей гиперплоскости ai согласно (83), и ее параметр сдвига b.

В решающее правило (84) не вошли признаки i I, поскольку соответствующие компоненты оптимальной разделяющей гиперплоскости оказались нулевыми. Заведомо входят в него признаки i I, что же касается признаков из множества i I 0, то в решающем правиле остаются только те из них, для которых значения коэффициентов 0 i 0, найденные при решении задачи (85), оказались ненулевыми.

Признаки или компоненты направляющего вектора, определяющие оптимальное решающее правило естественно назвать опорными признаками. То обстоятельство, что изложенный метод обучения жестко выделяет некоторое подмножество признаков, полностью устраняя остальные, позволил назвать его методом опорных признаков с управляемой селективностью или Selective Support Feature Support Vector Machine (SFM) в отличие от метода релевантных признаков, предложенного в предыдущей главе, который лишь снабжал признаки неотрицательными весами в соответствии с их оцененной степенью информативности.

Зависимость множества опорных признаков от параметра 3.3. селективности критерия обучения Структура подмножеств признаков (82) и вид решающего правила (84) явно указывают механизм зависимости состава множества опорных признаков (компонент) от параметра 0 в критерии обучения (72).

Если 0, то множество заведомо опорных признаков I I {1,..., n} совпадает со всем множеством I. В этом частном случае функция (69) квадратична q(ai | ) ai2 при всех ai и критерий обучения (72) не отличается от обычного критерия метода опорных векторов, не обладающего свойством селективности, так что все исходные признаки входят в получаемое решающее правило распознавания, являясь опорными.

Увеличение значения параметра приводит к тому, что все большее число признаков попадает в множество I заведомо неопорных (82), соответственно уменьшается множество опорных признаков (86).

При неограниченном росте параметра селективности в конце концов все признаки оказываются в множестве I, и опорных компонент вообще не остается I supp.

3.4 Теоретическое исследование механизма селективности и эффекта группировки методов релевантных и опорных Механизм селективности отбора признаков 3.4. Для анализа свойств механизма селективности метода опорных признаков запишем критерий обучения (73), предложенный ранее в разделе 3.3, в эквивалентном виде, разделяющем принцип максимизации зазора между классами в обучающей выборке и механизм селекции направлений a искомой гиперплоскости:

Эквивалентность оптимизационных задач нетрудно проверить, выполнив замену переменных a a, b b и домножив целевую функцию на величину параметра C.

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

«Наилучшие» направления (22) критерия обучения (87), а, следовательно, и исходного критерия (73), определяются следующей теоремой.

Теорема 10. Функция штрафа (88) для фиксированного 0 принимает векторов Доказательство теоремы приведено на с. 107.

Как и у методов 1-norm SVM и DrSVM, селективность обучения по методу опорных признаков (73) определяется априорным предпочтением функции штрафа (88) минимально штрафовать такие направляющие вектора (89), у которых только один компонент отличен от нуля (90), что соответствует включению в решающее правило только одного признака.

«Наихудшие» направления (21) критерия обучения (87), а, следовательно, и исходного критерия (73), определяются следующей теоремой.

Теорема 11. Функция штрафа (88) для фиксированного 0 принимает щих векторов Если n0.5, то Если n0.5, то Доказательство теоремы приведено на с. 110.

Нетрудно теперь вычислить уровень селективности (23), который определяется разностью значений штрафа для «наихудших» и «наилучших»

направлений:

Теорема 11 показывает важное отличие метода опорных признаков (73) от методов 1-norm SVM и DrSVM, которое заключается в том, что при направляющего вектора состоит не из одного направления, оценивающего все признаки как равнозначные (методы 1-norm SVM и DrSVM), а составляет включение в решающую функцию aT x b 0 сразу всех признаков с разными достаточно большими весами | ai |, i 1,..., n. Это условие означает «неразличимость» для обучения таких направляющих векторов Следовательно, в ситуациях, когда в исходных данных есть несколько значимых признаков, выбор весов, с которыми они будут входить в решение, определяется исключительно качеством разделения выборки, а не априорным стремлением выделить только один из признаков, подобно методам 1-norm SVM и DrSVM.

Аналогичным образом проанализируем метод релевантных признаков с управляемой селективностью и запишем критерий обучения (66) в эквивалентном виде Эквивалентность критериев нетрудно проверить, выполнив замену переменных a a, b b и домножив целевую функцию на величину параметра C 0.

Выпишем отдельно штраф на направление и зазор (первое слагаемое целевой функции) «Наилучшие» направления такого штрафа определены в следующей теореме.

Теорема 12. Функция штрафа (92) для фиксированного 0 принимает векторов Доказательство теоремы приведено на с. 113.

«Наихудшие» направления критерия обучения (91) определены в следующей теореме.

Теорема 13. Функция штрафа (92) для фиксированного 0 принимает щих векторов Доказательство теоремы приведено на с. 115.

Уровень селективности (23) определяется разностью величин штрафов для «наихудших» и «наилучших» направлений:

Не трудно видеть, что с точки зрения состава множеств наиболее (96) и наименее (96) предпочтительных направлений метод релевантных признаков (66) эквивалентен методам 1-norm SVM и DrSVM.

Эффект группировки признаков 3.4. Предложенный в диссертации метод опорных признаков (73), в отличие от методов 1-norm SVM и DrSVM, обладает эффектом избирательной группировки признаков. Избирательность группировки признаков определяется следующей теоремой.

Теорема 14. Пусть обучающая выборка предварительно центрирована и нормирована таким образом, что Пусть a (a1,..., an )T, b, (1,..., N )T есть решение оптимизационной задачи метода опорных признаков с управляемой селективностью (73) для обучающей выборки (97) с учетом нормировки (98). Тогда для любой пары компонент с индексами (q, k ) направляющего вектора a (a1,..., an )T справедливы следующие неравенства.

где - есть выборочная корреляция признаков с индексами (q, k ), вычисленная по выборке (97) с учетом нормировки (98).

Если | aq |, | ak | и компоненты aq, ak одного знака, то их значения дополнительно не ограничены.

Если | aq |, | ak | и компоненты aq, ak разного знака, то Доказательство теоремы приведено на с. 116.

Для иллюстрации утверждений теоремы рассмотрим пару признаков с индексами (q, k ), корреляция которых равна единице 1. Соответствующие компоненты оптимального направляющего вектора aq, ak удовлетворяют следующим условиям:

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

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

Следующая теорема показывает, что метод релевантных признаков (66) также обладает эффектом группировки признаков.

Теорема 15. Пусть обучающая выборка предварительно центрирована и нормирована таким образом, что Пусть a (a1,..., an )T, b, (1,..., N )T есть решение оптимизационной задачи метода релевантных признаков (66) для обучающей выборки (101) с учетом нормировки (98).

Для любой пары индексом (q, k ), для которых выполняются условия 0 1 - выборочная корреляция признаков с индексами (q, k ), вычисленная по обучающей выборке (101) с учетом нормировки (102).

Доказательство теоремы приведено на с. 122.

3.5 Выбор оптимального уровня селективности: Метод скользящего контроля Параметр селективности 0, как и параметр C 0, является структурным параметром критериев обучения (65), (72), определяет последовательность вложенных классов моделей распознавания, чья размерность уменьшается с ростом. При этом уменьшение размерности происходит неявно для случая метода релевантных признаков (RFM) и абсолютно явно для метода опорных признаков (SFM). Однако для обоих методов нельзя указать, как количественно зависит размерность и величина параметра селективности, а также гарантировать, что эта зависимость монотонна.

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

ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МЕТОДОВ

РЕЛЕВАНТНЫХ И ОПОРНЫХ ПРИЗНАКОВ С УПРАВЛЯЕМОЙ

СЕЛЕКТИВНОСТЬЮ

За основу экспериментов принята и расширена структура модельных данных, предложенная авторами метода Doubly Regularized SVM (Elastic Net SVM) [12].