Почему люди используют методы квадратичного программирования (например, SMO) при работе с SVM с ядром? Что не так с градиентным спуском? Это невозможно использовать с ядрами или просто слишком медленно (и почему?).
Здесь немного больше контекста: пытаясь немного лучше понять SVM, я использовал Gradient Descent для обучения линейного классификатора SVM, используя следующую функцию стоимости:
Я использую следующие обозначения:
- - это весовые характеристики модели, а- ее параметр смещения.
- я й - вектор элементов обучающего экземпляра.
- - целевой класс (-1 или 1) для экземпляра .
- - количество обучающих экземпляров.
- - гиперпараметр регуляризации.
Я вывел (суб) вектор градиента (относительно и ) из этого уравнения, и Gradient Descent работал просто отлично. б
Теперь я хотел бы заняться нелинейными задачами. Могу ли я просто заменить все точечные продукты на в функции стоимости, где - функция ядра (например, RBF Гаусса, ), затем используйте исчисление для вывода (суб) градиентный вектор и приступить к градиентному спуску? K( u , v )KK( u , v )= e - γ ‖ u - v ‖ 2
Если это слишком медленно, то почему? Функция стоимости не выпуклая? Или это потому, что градиент изменяется слишком быстро (он не является непрерывным по Липшицу), поэтому алгоритм продолжает перепрыгивать через долины во время спуска, поэтому он сходится очень медленно? Но даже тогда, как это может быть хуже, чем временная сложность квадратичного программирования, которая равна ? Если это вопрос локальных минимумов, не может ли стохастик GD с имитацией отжига преодолеть их?
источник
Если мы применим преобразование ко всем входным весовым векторам ( x ( i ) ), мы получим следующую функцию стоимости:ϕ x(i)
Трюк с ядром заменяет на K ( u , v ) . Так как весовой вектор W является не трансформировали, ядро трик не может быть применен к функции затрат выше .ϕ(u)t⋅ϕ(v) K(u,v) w
Вышеуказанная функция стоимости соответствует основной форме цели SVM:
Двойная форма является:
Таким образом, уловка ядра может быть использована только в двойственной форме задачи SVM (плюс некоторые другие алгоритмы, такие как логистическая регрессия).
Теперь вы можете использовать готовые библиотеки для квадратичного программирования, чтобы решить эту проблему, или использовать множители Лагранжа для получения неограниченной функции (функция двойной стоимости), а затем искать минимум с помощью градиентного спуска или любого другого метода оптимизации. Одним из наиболее эффективных подходов является алгоритм SMO, реализованный
libsvm
библиотекой (для SVM с ядром).источник
Я могу ошибаться, но я не понимаю, как мы можем заменить точечные продукты ядрами, не превращая это в двойственную проблему.
Кажется трудным оптимизировать вектор бесконечных измерений, используя градиентный спуск напрямую.
Обновленный
ответ Firebug дает возможность заменить точечные продукты ядрами в первичной формулировке.
источник