При заданном наборе точек в двухмерном пространстве, как может функционировать одно решение по проектированию для SVM?

Может кто-нибудь объяснить мне, как можно разработать функцию решения SVM? Или укажите мне на ресурс, который обсуждает конкретный пример.

РЕДАКТИРОВАТЬ

Для приведенного ниже примера я вижу, что уравнение $X_2 = 1.5$ разделяет классы с максимальным запасом. Но как мне отрегулировать веса и написать уравнения для гиперплоскостей в следующем виде.

$$\begin{array}{ll} H_1 : w_0+w_1x_1+w_2x_2 \ge 1 & \text{for}\; Y_i = +1 \\ H_2 : w_0+w_1x_1+w_2x_2 \le -1 & \text{for}\; Y_i = -1.\end{array}$$

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

Я разработал решение для этого Кто-то может подтвердить, если это правильно?

весовой вектор равен (0, -2), а W_0 равен 3

$$\begin{array}{ll} H_1 : 3+0x_1-2x_2 \ge 1 & \text{for}\; Y_i = +1 \\ H_2 : 3+0x_1 -2x_2 \le -1 & \text{for}\; Y_i = -1.\end{array}$$

Есть как минимум два способа мотивации SVM, но я выберу более простой путь.

$\mathcal{D} = \{(x^i_1, x^i_2, y_i)\}$$y_i$$\{1, -1\}$$1$$-1$

$w_0 + w_1x_1 + w_2x_2 = 0$$w_0 + w_1x_1 + w_2x_2 > 0$$w_0 + w_1x_1 + w_2x_2 < 0$

$[w_0, w_1, w_2]$$w_0 + w_1x^i_1 + w_2x^i_2 \geq 0$$x^i$$y_i = 1$$w_0 + w_1x^i_1 + w_2x^i_2 < 0$$x^i$$y_i = -1$

Давайте предположим, что такая строка действительно существует, тогда я могу определить классификатор следующим образом,

$$\min |w_0| + |w_1| + |w_2| \\ \text{subject to} : w_0 + w_1x^i_1 + w_2x^i_2 \geq 0, \forall x^i\text{ with }y_i = 1 \\ w_0 + w_1x^i_1 + w_2x^i_2 < 0, \forall x^i\text{ with }y_i = -1 \\ $$

Я использовал произвольную целевую функцию выше, в настоящий момент нам все равно, какая целевая функция используется. Мы просто хотим который удовлетворяет нашим ограничениям. Поскольку мы предположили, что линия существует так, что мы можем разделить два класса этой строкой, мы найдем решение вышеупомянутой задачи оптимизации.$w$

Выше не SVM, но он даст вам классификатор :-). Однако этот классификатор может быть не очень хорошим. Но как вы определяете хороший классификатор? Хорошим классификатором обычно является тот, который хорошо работает на тестовом наборе. В идеале, вы бы перебрать все возможные «S, разделяющие ваши обучающие данные и посмотреть , какие из них действительно хорошо на тестовых данных. Тем не менее, существует бесконечное количество , так что это совершенно безнадежно. Вместо этого мы рассмотрим некоторые эвристики, чтобы определить хороший классификатор. Одна эвристика заключается в том, что линия, разделяющая данные, будет достаточно далеко от всех точек (т. Е. Между точками и линией всегда есть разрыв или запас). Лучшим среди них является классификатор с максимальным запасом. Это то, что используется в SVM.$w$$w$

Вместо того чтобы настаивать на том, что для всех точек с и для всех точек с , если мы настаиваем на том, что для всех точек с и для всех точек с , то мы фактически настаиваем на том, чтобы точки находились далеко от линии. Геометрическое поле, соответствующее этому требованию, оказывается .$w_0 + w_1x^i_1 + w_2x^i_2 \geq 0$$x^i$$y_i = 1$$w_0 + w_1x^i_1 + w_2x^i_2 < 0$$x^i$$y_i = -1$$w_0 + w_1x^i_1 + w_2x^i_2 \geq 1$$x^i$$y_i = 1$$w_0 + w_1x^i_1 + w_2x^i_2 \leq -1$$x^i$$y_i = -1$$\frac{1}{\|w\|_2}$

Итак, мы получаем следующую задачу оптимизации: Немного сжатая форма написания: Это в основном базовая формулировка SVM. Я пропустил довольно много дискуссий для краткости. Надеюсь, я все еще получил большую часть идеи.

$$\max \frac{1}{\|w\|_2} \\ \text{subject to} : w_0 + w_1x^i_1 + w_2x^i_2 \geq 1, \forall x^i\text{ with }y_i = 1 \\ w_0 + w_1x^i_1 + w_2x^i_2 \leq -1, \forall x^i\text{ with }y_i = -1 \\ $$ $$\min \|w\|_2 \\ \text{subject to} : y_i(w_0 + w_1x^i_1 + w_2x^i_2) \geq 1, \forall i$$

---

Сценарий CVX для решения проблемы примера:

A = [1 2 1; 3 2 1; 2 3 1; 3 3 1; 1 1 1; 2 0 1; 2 1 1; 3 1 1];
b = ones(8, 1);
y = [-1; -1; -1; -1; 1; 1; 1; 1];
Y = repmat(y, 1, 3);
cvx_begin
variable w(3)
minimize norm(w)
subject to
(Y.*A)*w >= b
cvx_end

---

Приложение - Геометрическая маржа

Выше мы уже просили, чтобы мы искали таким образом, чтобы или вообще . LHS здесь, который вы видите, называется функциональным запасом, поэтому мы попросили, чтобы функциональный запас был . Теперь мы попытаемся вычислить геометрическую маржу с учетом этого требования функциональной маржи.$w$$y_i(w_0 + w_1x_1 + w_2x_2) \geq 1$$y_i(w_0 + w^Tx) \geq 1$$\geq 1$

Что такое геометрический запас? Геометрический запас - это кратчайшее расстояние между точками в положительных примерах и точками в отрицательных примерах. Теперь точки с самым коротким расстоянием, как требуется выше, могут иметь функциональный запас больше, чем равный 1. Однако, давайте рассмотрим крайний случай, когда они находятся ближе всего к гиперплоскости, то есть функциональный край для самых коротких точек точно равен 1. Пусть - точка в положительном примере - точка, такая, что а - точка в отрицательном примере, точка, такая, что , Теперь расстояние между и будет самым коротким, когда$x_+$$w^Tx_+ + w_0 = 1$$x_-$$w^Tx_- + w_0 = -1$$x_+$$x_-$$x_+ - x_-$ перпендикулярно гиперплоскости.

Теперь, со всей вышеуказанной информацией, мы попытаемся найти который является геометрическим полем. $\|x_+ - x_-\|_2$

$$w^Tx_+ + w_0 = 1$$ $$w^Tx_- + w_0 = -1$$ $$w^T(x_+ - x_-) = 2$$ $$|w^T(x_+ - x_-)| = 2$$ $$\|w\|_2\|x_+ - x_-\|_2 = 2$$ $$\|x_+ - x_-\|_2 = \frac{2}{\|w\|_2}$$

---

[1] На самом деле не имеет значения, какую сторону вы выберете для и . Вы просто должны оставаться в соответствии с тем, что вы выбираете.$1$$-1$