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

Question

Я работаю над машиной опорных векторов уже около 2 месяцев. Я сам кодировал SVM и для задачи оптимизации SVM я использовал Последовательную минимальную оптимизацию (SMO) доктора Джона Платта.

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

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

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

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

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

Пожалуйста, дайте мне информацию по этому вопросу.

Спасибо и ура.

Answer 1

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

Время обучения SVM против C - Из Sentelle и др. Быстрый пересмотренный симплекс-метод для обучения SVM .

альтернативный текст http://dmcer.net/StackOverflowImages/svm_scaling.png

Вероятно, у вас есть два простых способа и один не очень простой способ ускорить процесс.

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

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