Dado um conjunto de pontos no espaço bidimensional, como uma decisão de projeto pode funcionar para o SVM?

Existem pelo menos duas maneiras de motivar os SVMs, mas seguirei a rota mais simples aqui.

Agora, esqueça tudo o que sabe sobre o SVM no momento e concentre-se apenas no problema em questão. Você recebe um conjunto de pontos junto com alguns rótulos ( ) que são de . Agora, estamos tentando encontrar uma linha em 2D tal que todos os pontos com etiqueta queda de um lado da linha e todos os pontos com etiqueta queda do outro lado. $\mathcal{D} = \{(x^i_1, x^i_2, y_i)\}$ $y_i$ $\{1, -1\}$ $1$ $-1$

Antes de tudo, perceba que é uma linha em 2D e representa "um lado" da linha e representa o "outro lado" da linha. $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$

Do exposto, podemos concluir que queremos um vetor tal que, para todos os pontos com e $[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$ para todos os pontos com [1]. $x^i$ $y_i = -1$

Vamos supor que essa linha realmente exista, então eu posso definir um classificador da seguinte maneira,

min | w_{0} | + | w_{1} | + | w_{2} | subject to : w_{0} + w_{1} x_{1}^{i} + w_{2} x_{2}^{i} \geq 0, \forall x^{i} with y_{i} = 1 w_{0} + w_{1} x_{1}^{i} + w_{2} x_{2}^{i} < 0, \forall x^{i} with 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 \\$

Eu usei uma função objetivo arbitrária acima, na verdade não nos importamos no momento em que função objetivo seja usada. Nós apenas queremos um que satisfaça nossas restrições. Como assumimos que existe uma linha de forma que possamos separar as duas classes com essa linha, encontraremos uma solução para o problema de otimização acima. $w$

O acima não é SVM, mas fornecerá um classificador :-). No entanto, esse classificador pode não ser muito bom. Mas como você define um bom classificador? Um bom classificador é geralmente aquele que se sai bem no conjunto de testes. Idealmente, você examinaria todos os possíveis que separam seus dados de treinamento e veria qual deles se saiu bem nos dados de teste. No entanto, existem infinitos , então isso é totalmente inútil. Em vez disso, consideraremos algumas heurísticas para definir um bom classificador. Uma heurística é que a linha que separa os dados estará suficientemente longe de todos os pontos (ou seja, sempre há espaço ou margem entre os pontos e a linha). O melhor classificador dentre esses é o de margem máxima. É isso que é usado nos SVMs. $w$ $w$

Em vez de insistir que para todos os pontos com e para todos os pontos com , se insistimos que para todos os pontos com e para todos os pontos com , então estamos realmente insistindo para que os pontos estejam longe da linha. A margem geométrica correspondente a esse requisito é . $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}$

Portanto, obtemos o seguinte problema de otimização, Uma forma ligeiramente sucinta de escrever é: Essa é basicamente a formulação básica do SVM. Eu pulei muita discussão por questões de brevidade. Espero que ainda tenha conseguido a maior parte da idéia.

max \frac{1}{‖ w ‖_{2}} subject to : w_{0} + w_{1} x_{1}^{i} + w_{2} x_{2}^{i} \geq 1, \forall x^{i} with y_{i} = 1 w_{0} + w_{1} x_{1}^{i} + w_{2} x_{2}^{i} \leq - 1, \forall x^{i} with y_{i} = - 1

$\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} subject to : y_{i} (w_{0} + w_{1} x_{1}^{i} + w_{2} x_{2}^{i}) \geq 1, \forall i

$\min \|w\|_2 \\ \text{subject to} : y_i(w_0 + w_1x^i_1 + w_2x^i_2) \geq 1, \forall i$

Script CVX para resolver o problema de exemplo:

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

Adenda - Margem Geométrica

Acima, já solicitamos que modo que ou geralmente . O LHS aqui que você vê é chamado de margem funcional; portanto, o que solicitamos aqui é que a margem funcional seja . Agora, tentaremos calcular a margem geométrica, considerando esse requisito de margem funcional. $w$ $y_i(w_0 + w_1x_1 + w_2x_2) \geq 1$ $y_i(w_0 + w^Tx) \geq 1$ $\geq 1$

O que é margem geométrica? Margem geométrica é a menor distância entre pontos nos exemplos positivos e pontos nos exemplos negativos. Agora, os pontos que possuem a menor distância, conforme exigido acima, podem ter uma margem funcional maior que igual a 1. No entanto, vamos considerar o caso extremo, quando estiverem mais próximos do hiperplano, a margem funcional para os pontos mais curtos é exatamente igual para 1. Seja o ponto no exemplo positivo, seja um ponto tal que e seja o ponto no exemplo negativo, seja um ponto tal que . Agora, a distância entre e será a mais curta quando $x_+$ $w^Tx_+ + w_0 = 1$ $x_-$ $w^Tx_- + w_0 = -1$ $x_+$ $x_-$ $x_+ - x_-$ é perpendicular ao hiperplano.

Agora, com todas as informações acima, tentaremos encontrar que é a margem geométrica. $\|x_+ - x_-\|_2$

w^{T} x_{+} + w_{0} = 1

$w^Tx_+ + w_0 = 1$

w^{T} x_{-} + w_{0} = - 1

$w^Tx_- + w_0 = -1$

w^{T} (x_{+} - x_{-}) = 2

$w^T(x_+ - x_-) = 2$

| w^{T} (x_{+} - x_{-}) | = 2

$|w^T(x_+ - x_-)| = 2$

‖ w ‖_{2} ‖ x_{+} - x_{-} ‖_{2} = 2

$\|w\|_2\|x_+ - x_-\|_2 = 2$

‖ x_{+} - x_{-} ‖_{2} = \frac{2}{‖ w ‖_{2}}

$\|x_+ - x_-\|_2 = \frac{2}{\|w\|_2}$

[1] Não importa qual lado você escolhe para e . Você só precisa permanecer consistente com o que escolher. $1$ $-1$

TenaliRaman
fonte

@ Naresh Yeap, resolver isso é em CVX me deu exatamente a mesma solução que você tem .

w = [0, - 2, 3]

$w = [0, -2, 3]$

TenaliRaman

@entropy obrigado Corrigi o erro de digitação. Vou adicionar a explicação da margem geométrica.

TenaliRaman

@entropy Atualizei a resposta com a explicação da margem geométrica.

TenaliRaman

@entropy é um hiperplano passando pela origem. Para cobrir o espaço de todas as equações lineares, você precisa do termo de viés. Pense nos pontos que residem em 2D e digamos que você está tentando encontrar uma linha que os separa. No entanto, todos esses pontos estão no primeiro quadrante. Agora, é possível organizar esses pontos de modo que sejam separáveis, mas não por qualquer linha que passe pela origem. No entanto, uma linha com um viés adequado pode fazê-lo.

w^{T} x

$w^{T}x$

TenaliRaman

@entropy Dito o exposto acima, você já deve ter percebido que, se você girar e mudar os pontos adequadamente, mesmo uma linha que passa pela origem deve separar as classes. No entanto, geralmente não é fácil encontrar essa rotação e mudança certas, comparado a apenas aprender o termo de viés.

TenaliRaman

Dado um conjunto de pontos no espaço bidimensional, como uma decisão de projeto pode funcionar para o SVM?

Respostas: