3.3Алгоритм обучения с заданной селективностью отбора признаков

Критерий обучения по методу опорных векторов с релевантными компонентами несложно алгоритмически реализовать, разделив все множество варьируемых переменных на два подмножества и с применением метода итерационного попеременного спуска (метода Гаусса-Зайделя). Итерационный процесс естественно начать, например, с исходных единичных значений .

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

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

, .

Приравнивание производной по дает условие

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

.

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

При правило вычисления значений дисперсий на очередной итерации принимает вид

.

В этом случае алгоритм подавляет почти все признаки, оставляя один, редко два из них.

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

4Отбор подмножества информативных признаков в процессе обучения распознаванию двух классов объектов по методу опорных векторов: Метод опорных признаков

4.1Независимые идентичные комбинированные распределения элементов направляющего вектора

Априорные нормальные распределения :

.

Априорные распределения Лапласа:

.

Априорные комбинированные распределения (Е.О. Черноусова):

где – функция Лапласа (интеграл вероятности, дополнительная функция ошибок).

Тогда обобщенная задача SVM :

Этот критерий известен в литературе как Doubly Regularized SVM или Elastic Net SVM [⁴].

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

Критерий обучения не является квадратичным, но остается выпуклым. Негладкие задачи оптимизации, Наум Зуселевич Шор (1937-2006), академик НАН Украины.

При критерий превращается в известный критерий Lasso SVM [⁵]:

4.2Двойственная задача обучения

Функция Лагранжа:

Здесь . Минимизация функции Лагранжа по сводится к минимизации по каждой из функций

.

Ограничимся рассмотрением случая .

Точка минимума недифференцируемой в нуле функции зависит от значения по отношению к интервалу .

Если , то и определяется условием

т.е. .

Если , то .

Если , то , и определяется условием

, т.е. .

Сведем вместе все три варианта:

Результат минимизации по согласно и :

.

Заметим, что в первом случае и , а в последнем случае и , поэтому

.

Отсюда следует эквивалентная запись результата минимизации по :

.

Минимизация функции Лагранжа по остальным целевым переменным и не отличается от случая классического критерия SVM , и , и приводит к равенствам

,

, т.е. , .

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

После того, как двойственная задача обучения решена, и найдены значения множителей Лагранжа , значения компонент направляющего вектора оптимальной разделяющей гиперплоскости определяются равенствами . Если обозначить через все множество признаков объектов , т.е. множество компонент направляющего вектора , то решение двойственная задачи согласно разбивает это множество на три подмножества , , , :

где

Селективность обучения заключается в том, что часть признаков объявляются неактивными в решающем правиле распознавания, применимом к произвольным объектам , в том числе к тем, которые не участвовали в обучении:

.

Смещение гиперплоскости определяется теми же соображениями -, что и для классического критерия обучения SVM:

Целевая функция двойственной задачи является вогнутой кусочно-квадратичной функцией, подлежащей максимизации в выпуклой области. Численное решение двойственной задачи может быть получено подходящим стандартным итерационным методом выпуклого (вогнутого) программирования, например, методом внутренней точки [⁶]. Однако специфика эадачи позволяет построить более простой итерационный алгоритм ее численного решения, опирающийся на любой метод решения более простой задачи квадратичного программирования, предполагающей, что целевая функция является квадратичной вместо более общего случая вогнутой функции.