Проблемы с конвергенцией последовательной минимальной оптимизации для SVM

Question

Я работаю над поддержкой Vector Machine около 2 месяцев. Я сам кодировал SVM и для оптимизации проблемы SVM, я использовал Sequential Minimal Optimization (SMO) доктором Джоном Платтом.

Сейчас я нахожусь в фазе, где я собираюсь искать сетку, чтобы найти оптимальное значение C для моего набора данных. (Подробности здесь можно найти здесь: SVM Classification - minimum number of input sets for each class)

Я успешно проверил выполненную мной техническую точность SVM для значений C от 2^0 до 2^6. Но теперь у меня есть некоторые проблемы, связанные с конвергенцией SMO для C> 128. Как я попытался найти альфа-значения для C = 128, и он занимает много времени, прежде чем он фактически сходится и успешно дает альфа-значения.

Время, затраченное на схождение SMO, составляет около 5 часов для C = 100. Этот огромный я думаю (потому что SMO должен быть быстрым.), Хотя я получаю хорошую точность? Я правильно ввернусь, потому что не могу проверить точность для более высоких значений C.

Я фактически показываю количество альфов, измененных в каждом проходе SMO, и получаю 10, 13, 8 ... альфа меняется непрерывно. Условия KKT гарантируют конвергенцию, так что здесь так странно происходит?

Обратите внимание, что моя реализация отлично работает для C < = 100 с хорошей точностью, хотя время выполнения длительное.

Просьба дать мне материалы по этой проблеме.

Спасибо и приветствуются.

Answer 1

Для большинства реализаций SVM время обучения может резко увеличиться при больших значениях C. Чтобы понять, как время тренировки в достаточно хорошей реализации шкал SMO с C, посмотрите на строку журнала для libSVM на графике ниже.

Время обучения СВМ против C - От Sentelle et al.'s A Fast Revised Simplex Method for SVM Training.

alt text http://dmcer.net/StackOverflowImages/svm_scaling.png

У вас, вероятно, есть два простых способа и один нелегкий способ сделать вещи быстрее.

Начнем с простого материала. Во-первых, вы можете попробовать ослабить критерии конвергенции. Строгие критерии, такие как epsilon = 0.001, будут занимать гораздо больше времени, чтобы тренироваться, в то время как типично приводят к модели, которая не лучше, чем более рыхлые критерии, такие как epsilon = 0.01. Во-вторых, попробуйте указать свой код, чтобы узнать, есть ли какие-либо очевидные узкие места.

Не так просто исправить, было бы переключиться на другой алгоритм оптимизации (например, SVM-RSQP из вышеприведенной работы Sentelle et al.). Но, если у вас есть рабочая реализация SMO, вы, вероятно, должны сделать это только в крайнем случае.