Вычисление коэффициентов Лагранжа для SVM в Python

Я пытаюсь написать полную реализацию SVM на Python, и у меня есть несколько проблем с вычислением коэффициентов Лагранжа.

Сначала позвольте мне перефразировать то, что я понимаю из алгоритма, чтобы убедиться, что я на правильном пути.

Если $x_1, x_2, ..., x_n$ - это набор данных, а $y_i \in \{-1, 1\}$ - метка класса $x_i$ , тогда

$$\forall i, y_i(w^Tx_i + b) \geq 1$$

Так что нам просто нужно решить проблему оптимизации, чтобы

$\|w\|^2$

при условии$y_i(w^Tx_i + b) \geq 1$

В терминах коэффициентов Лагранжа это приводит к нахождению минимизации , и и :б α = ( & alpha ; 1 , & alpha ; 2 , . . . α п ) ≠ 0 ≥ 0 L ( α , ш , б ) = $w$$b$$\alpha=(\alpha_1, \alpha_2, ... \alpha_n) \neq0$$\geq0$

$$L(\alpha, w, b) = \frac12 \|w\|^2 - \sum \alpha_i(y_i(w^Tx + b)-1)$$

Теперь, поскольку и мы можем переписать его как L (\ alpha, w, b) = Q (\ alpha) = \ sum \ alpha_i - \ frac12 \ sum \ sum \ alpha_i \ alpha_j y_i y_j x_i ^ T x_j с ограничениями \ alpha_i \ geq 0 \ \ text {and} \ \ sum \ alpha_i y_i = 0∂

$$\frac{\partial L}{\partial w}=0 \implies w=\sum \alpha_i y_i x_i$$ л ( & alpha ; , ш , б ) = Q ( & alpha ; ) = Е & alpha ; я - $$\frac{\partial L}{\partial b}=0 \implies \sum y_i \alpha_i = 0$$ $$L(\alpha, w, b) = Q(\alpha)=\sum \alpha_i - \frac12\sum \sum \alpha_i \alpha_j y_i y_j x_i^T x_j$$ $$\alpha_i \geq 0 \ \text{and} \ \sum \alpha_i y_i = 0$$

Поэтому я пытаюсь решить проблему оптимизации с помощью Python, и единственный бесплатный пакет, который я могу найти, называется cvxopt .

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

Обратите внимание, что в какой-то момент я захочу решить ее, используя Ядра но я не уверен, каковы последствия решения этого в коде.

$$L(\alpha, w, b) = Q(\alpha)=\sum \alpha_i - \frac12\sum \sum \alpha_i \alpha_j y_i y_j K(x_i,x_j)$$

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

Я использовал cvxopt для реализации SVM раньше, однако в Matlab не Python. Это определенно будет служить вашей цели, будет ли его эффективность будет зависеть от того, для чего вы его используете. Наиболее эффективные SVM не используют пакет решения QP, они используют преимущества некоторых оптимизаций, уникальных для SVM. Многие используют алгоритм стиля SMO для его решения.

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

SVMLight - это еще один пакет, в котором используется другой алгоритм (см. Ссылки на их сайте). Это также с открытым исходным кодом и имеет интерфейс Python.

Общая форма вашей задачи оптимизации - это квадратичная программа , независимо от того, используете ли вы ядро или линейное ядро. Похоже, cvxoptэтого будет достаточно для того, что вы пытаетесь сделать, но и другим питонавтам здесь повезло и с OpenOpt .