Реализация линейного двоичного SVM (машины поддержки векторов)

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

Проблема в том, что большинство руководств подходят к уравнению, которое можно решить как "квадратичную задачу", но они никогда не показывают реального алгоритма! Можете ли вы указать мне либо на очень простую реализацию, которую я мог бы изучить, либо (лучше) на учебник, который полностью соответствует деталям реализации?

Спасибо большое!

Ответы

Ответ 1

Некоторые псевдокоды для метода последовательной минимальной оптимизации (SMO) можно найти в этой статье Джона К. Платта: Быстрая подготовка векторных машин поддержки с использованием последовательного Минимальная оптимизация. Существует также реализация Java алгоритма SMO, который разработан для исследовательских и образовательных целей (SVM-JAVA).

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

  • ограниченные сопряженные градиенты
  • методы внутренней точки.
  • активные методы набора

Но помните, что для понимания этого необходимы некоторые математические знания (множители Лагранжа, условия Каруша-Куна-Таккера и т.д.).

Ответ 2

Вы заинтересованы в использовании ядер или нет? Без ядер лучший способ решить эти проблемы оптимизации - это различные формы стохастического градиентного спуска. Хорошая версия описана в http://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdf и имеет явный алгоритм.

Явный алгоритм не работает с ядрами, но может быть изменен; однако это было бы более сложным, как с точки зрения сложности кода, так и со временем выполнения.

Ответ 3

Посмотрите на liblinear и для нелинейного SVM в libsvm

Ответ 4

В следующей статье "Pegasos: Primal Estimated sub-GrAdient SOlver для SVM" вверху страницы 11 описан алгоритм Pegasos также для ядер. Его можно загрузить из http://ttic.uchicago.edu/~nati/Publications/PegasosMPB.pdf

Это, по-видимому, гибрид спуска и субградиентного спуска координат. Кроме того, строка 6 алгоритма неверна. В предикате второе появление y_i_t следует заменить вместо y_j.