SVM – Entendendo sua Matemática – Parte 2 – O hiperplano

On 24 de setembro de 2015 by Ricardo Câmara

SVM: Na primeira parte deste tutorial da matemática por tras do svm nós vimos o objetivo do SVM. Seu objetivo é encontrar um hiperplano que maximize a margem.

Mas como calculamos esta margem no SVM?

SVM = Support VECTOR Machine (Máquina de Vetores de Suporte)

Em SVM há a palavra vetor. Isso quer dizer que é importante entender bem vetor e saber como usá-lo.

coverAqui está um pequeno resumo do que mostraremos hoje:

– O que é um vetor?
– É uma normal.
– É uma direção.

– Como adicionar e subtrair vetores?

– O que é produto escalar?

– Como projetar um vetor em outro?

Quando tivermos todas esses conhecimentos em mente nós veremos:

– Qual é a quação de um hiperplano?

– Como calcular a margem?

O que é um vetor?

Se definimos um ponto A(3,4) em ℝ2 nós podemos ilustra-lo assim.

Figura 1: um ponto

Figura 1: um ponto

Definição: Qualquer ponto x = (x_1,x_2), x \neq 0 em \mathbb{R}^2 especifica um vetor no plano, isto é, o vetor começa na origem e acaba em x .

Essa definição significa que há um vetor entre a origem e A .

Figura 2: Um vetor

Figura 2: Um vetor

Se nós dissermos que o ponto da origem é o ponto O(0,0) então o vetor acima é é o vetor \underset{OA}{\rightarrow}. Nós podemos também dar um nome arbitrário como u.

Obs.: Você pode notar que nós também escrevemos o vetor com uma seta em cima, ou em negrito, no resto deste post eu usarei a seta quando houver duas letras como \underset{OA}{\rightarrow} e a notação em negrito quando não houver.

Ok, então agora nós sabemos quando temos um vetor mas, continuamos não sabendo o que de fato é um vetor.
Definição: Um vetor é um objeto que possui uma direção e uma magnitude.

Agora nós veremos estes conceitos.

1) A magnetude de um vetor no SVM

A magnetude ou tamanho de um vetor x é escrita \left \| x \right \| e é chamada normal.

Para o nosso vetor \underset{OA}{\rightarrow}, \left \| OA \right \| é o comprimento do segmento de reta OA.

Figura 3

Figura 3

Pela figura 3 podemos facilmente calcular a distância do seguimento OA usando o teorema de pitágoras:

OA^2 = OB^2 + AB^2

OA^2 = 3^2 + 4^2

OA^2 = 25

OA = \sqrt{25}

\|OA\| =OA=5

2) A direção de um vetor no SVM

A direção é o segundo componente de um vetor.

Definição: A direção de um vetor u(u_1,u_2) é o vetor:

w(\frac{u_1}{\left \| u \right \|},\frac{u_2}{\left \| u \right \|})

De onde a coordenada w vem?

Entendendo a definição

Para encontrar a direção de um vetor, nós precisamos usar seus ângulos.

Figura 4 - Direção de um vetor

Figura 4 – Direção de um vetor

Podemos dizer que:

Definição simples 1: A direção de um vetor u é definida pelo ângulo \theta em relação ao eixo horizontal, e com o ângulo \alpha em relação ao eixo vertical.

Isso é chato. Ao contrário disso nós usaremos o cosseno dos ângulos.

Em um triângulo retângulo, o cosseno de \beta é definido por:

cos(\beta ) = \frac{cat. adjacente}{hipotenusa}

Na figura 4 vemos que podemos formar dois triângulos retângulo, e em ambos casos o cateto adjacente será um dos eixos. O que quer dizer que a definição de coseno contém implicitamente um eixo relacionado ao triângulo. Nós podemos reformular nossa definição simples para:

Definição simples 2: A direção de um vetor u é definida pelo coseno de um ângulo \theta e o cosseno de um ângulo \alpha.

Agora se olharmos para os seus valores:

cos(\theta ) = \frac{u_1}{\left \| u \right \|}

cos(\alpha ) = \frac{u_2}{\left \| u \right \|}

Consequentemente é a definição original de um vetor W. Por isso que suas coordenadas também são chamadas de direção do cosseno.

Calculando a direção do vector

Nós iremos agora calcular a direção do vetor u da figura 4:

cos\left ( \theta \right ) = \frac{u_1}{\left \| u \right \|} = \frac{3}{5} = 0.6

e

cos\left ( \alpha \right ) = \frac{u_2}{\left \| u \right \|} = \frac{5}{5} = 0.8

A direçãode u(3,4) é o vetor W(0.6,0.8).

Se desenharmos este vetor nos teremos a figura 5:

Figura 5: a direção de u

Figura 5: a direção de u

Nós podemos ver que w possui de fato a mesma aparência de u só que é menor. Algo interessante sobre a direção de vetores como w é que suas normais são iguais a 1. É por isso que são chamados de vetores unitários.

A soma de dois vetores

Figura 6: Dois vetores, u e v

Figura 6: Dois vetores, u e v

Dados dois vetores u(u_1,u_2) e v(v_1,v_2) então:

u+v = (u_1+u_2,v_1+v_2)

O que quer dizer que somando dois vetores nos teremos um terceiro vetor o qual as coodenadas são as somas das coordenadas dos vetores originais.

Você pode se convencer com o exemplo abaixo:

Figura 7: a soma de dois vetoes

Figura 7: a soma de dois vetoes

Subtração de dois vetores

A subtração de dois vetores funciona da mesma maneira:

u – v = (u1-v1,u2-v2)

Figura 8: subtração de dois vetores

Figura 8: subtração de dois vetores

Já que a subração não é comutativa, nós podemos considerar o outro caso:

v – u = (v1-u1,v2-u2)

Figura 9: subtração v-u

Figura 9: subtração v-u

As duas últimas imagens descrevem de fato dos vetores gerados pela diferença dos vetores u e v .

Como um vetor tem magnetude e direção, nós consideramos que a translação paralela de um dado vetor (vetores com a mesma direção e magnetude mas com origens diferentes) são os mesmos vetores, só que desenhado em um diferente lugar no espaço.

Então não se surpreenda se encontrar como ilustrado abaixo:

Figura 10: outra maneira de visualisar v-u

Figura 10: outra maneira de visualisar v-u

e

Figura 11: outra maneira de visualisar u-v

Figura 11: outra maneira de visualisar u-v

Se você fizer os cálculos, parece errado, por que o final do vetor u – v não está no ponto direito más, essa é a maneira conveniete de pensar sober vetores os quais você encontrará frequentemente.

O produto por escalar

Uma notação importante para entender o SVM é o produto escalar.

Definição: Geometricamente este é o produto das magnetudes euclidianas dos dois vetores e o cosseno dos ângulo entre eles.

O que quer dizer que se nós temos dois vetores x e y e há um ângulo \theta entre eles, o produto escalar é:

x . y = |x||y|cos(\theta)

Por quê?

Para enteder vamos olhar para o problema de forma geométrica.

Figura 12

Figura 12

Na definição, eles falam sobre cos(\theta), vamos ver o que é isso.

Por definição nós sabemos que em um triângulo equilátero:

cos(\theta) = \frac {cat. adjacente}{hipotenusa}

No nosso exemplo nós não temos um triângulo retângulo.

De qualquer forma se olharmos de outra maneira para a Figura 12 nós podemos encontrar dois triângulos retângulos formados por cada vetor com o eixo horizontal.

Figura 13

Figura 13

e

Figura 14

Figura 14

Agora nós podemos ver nosso esquema orignial assim:

Figura 15

Figura 15

Nós podemos ver que:

\theta = \beta -\alpha

Então computar o cos(\theta) é o mesmo que computar cos(\beta -\alpha ).

Há uma fórmula especial chamada a diferença de identidade do cosseno que diz que:

cos(\beta -\alpha) = cos(\beta)cos(\alpha)-sen(\beta)sen(\alpha)

(Se quiser ver a demonstração aqui.)

Vamos usar esta fórmula!

cos(\beta) = \frac{cat. adjacente}{hipotenusa} = \frac{x_1}{\left \| x \right \|}

sen(\beta) = \frac{cat. oposto}{hipotenusa} = \frac{x_2}{\left \| x \right \|}

cos(\alpha) = \frac{cat. adjacente}{hipotenusa} = \frac{y_1}{\left \| y \right \|}

sen(\alpha) = \frac{cat. oposto}{hipotenusa} = \frac{y_2}{\left \| y \right \|}

Então se substituirmos cada termo:

cos(\theta) = cos(\beta -\alpha ) = cos(\beta )cos(\alpha ) + sen(\beta )sen(\alpha )

cos(\theta) = \frac{x_1}{\left \| x \right \|} \frac{y_1}{\left \| y \right \|} + \frac{x_2}{\left \| x \right \|} \frac{y_2}{\left \| y \right \|}

cos(\theta) = \frac{x_1y_1 + x_2y_2}{\left \| x \right \| \left \| y \right \|}

Se nós multiplicarmos ambos lados por \left \| x \right \| \left \| y \right \| nós temos:

\left \| x \right \| \left \| y \right \|cos(\theta)= x_1y_1 + x_2y_2

O que é o mesmo que:

\left \| x \right \| \left \| y \right \|cos(\theta)= x \cdot y

Nós acabamos de encontrar a definição geométrica de produto escalar!

Das duas últimas equações podemos ver que:

x \cdot y = x_1y_1 + x_2y_2 = \sum_{i = 1}^{2}(x_iy_i)

Esta é a definição algébrica de produto escalar!

Um pouco sobre notação

O produto escalar, em inglês “dot product” recebe esse nome pois na notação é escrita com um ponto entre os vetores.

Falar sobre produto escalar x \cdot y é o mesmo que falar sobre:

– O produto interno \left \langle x,y \right \rangle (na algebra linear)
– Produto escalar por que nós tiramos o produto de dois vetores e retornamos um escalar, ou seja um número real.

A projeção ortogonal de um vetor

Dado dois vetores x e y, podemos querer encontrar a projeção ortogonal de x em y.

Figura 16

Figura 16

Essa projeção de vetores de x em y

Figura 17

Figura 17

isso nos dá o vetor z

Figura 18: z é a projeção de x em y

Figura 18: z é a projeção de x em y

Por definição:

cos(\theta ) = \frac{\left \| z \right \|}{\left \| x \right \|}

\left \| z \right \| = \left \| x \right \| cos(\theta )

Vimos na seção sobre o produto escalar que:

cos\left ( \theta \right ) = \frac{x \cdot y}{\left \| x \right \| \left \| y \right \|}

Então nós substituimos cos(\theta) na nossa equação

\left \| z \right \| = \left \| x \right \|\tfrac{x\cdot y}{\left \| x \right \|\left \| y \right \|}

\left \| z \right \| =\frac{x \cdot y}{\left \| y \right \|}

Se nós definirmos o vetor u como a direção de y então

u = \frac{y}{\left \| y \right \|}

e

\left \| z \right \| = u \cdot x

Agora nós temos uma maneira simples de computar a normal do vetor z .

Desde de que este vetor esteja na mesma direção que y ele possuirá a mesma direção de u .

u = \frac{z}{\left \| z \right \|}

z = \left \| z \right \| u

E podemos dizer:

O vector z = (u \cdot x)u é a projeção ortogonal de x em y.

Por quê estamos interessados na projeção ortogonal? No nosso exemplo, o qual nos permite computar a distância entre x e a linha a qual vai até y.

Figura 19

Figura 19

Vimos que essa distância é \left \| x-z \right \|.

\left \| x-z \right \| = \sqrt{(3-4)^{2}+(5-1)^{2}} = \sqrt{17}

O hiperplano SVM

Entendendo a equação do hiperplano SVM

Você provavelmente que a equação da linha é: y = ax + b. De qualquer forma quando lemos sobre hiperplano SVM, você frequentemente irá ver que a equação de um hiperplano é definida por:

\boldsymbol{w}^{T}\boldsymbol{x} = 0

Como essas duas formas de relacionam?

Na equação do hiperplano você pode ver que o nome das variavéis estão em negrito. O que quer dizer que elas são vetores! Além disso, \boldsymbol{w}^{T}\boldsymbol{x} = 0 é como computamos o produtor interno de dois vetores, e se você se recorda, o produto interno é só outro nome para produto escalar!

Note que

y = ax + b

é a mesma coisa que

y -ax -b = 0

Dado dois vetores \boldsymbol{w}(-b,-a,1) e \boldsymbol{x}(1,x,y)

\boldsymbol{w}^{T}\boldsymbol{x} = -b \times (-1) + (-a)\times x + 1 \times y

\boldsymbol{w}^{T}\boldsymbol{x} = y-ax-b

As duas equações só são maneiras deiferentes de expressar a mesma coia.

É interessante notar que w_0 é -b, o que significa que o valor determina a interseção das linhas com o eixo vertical.

Por quê nós usamos a equação do hiperplano \boldsymbol{w}^{T} ao contrário de y = ax + b?

Por duas razões:
– É mas fácil trabalhar com mais de dois vetores nesta anotação.
– O vetor \boldsymbol{w} sempre será a normal deste hiperplano.

E esta última propriedade que virá a calhar para computar a distância entre o ponto e o hiperplano.

Compute a distância de um ponto para o hiperplano

Na figura 20 nós temos um hiperplano, o qual separará os dados em dois grupos.

Figura 20

Figura 20

Como vocês pode ver na figura 20, a equação do hiperplano é:

x_2 = -2x_1

O qual é equivalente a:

\boldsymbol{w}^{T}\boldsymbol{x} = 0

com \boldsymbol{w}(2,1) e \boldsymbol{x}(x_1,x_2).

Note que o vetor \boldsymbol{w} é mostrado na figura 20. (w não é ponto de algum dado)

Nós gostariamos de computar a distância entre o ponto \boldsymbol{A}(3,4) e o hiperplano.

Esta é a distância entre \boldsymbol{A} e a sua projeção no hiperplano.

Figura 21

Figura 21

Nós podemos ver o ponto \boldsymbol{A} como um vetor de origem até \boldsymbol{A}.
Se nós projetarmos este vetor no vetor normal \boldsymbol{w}.

Figura 22: Projeção de a em w

Figura 22: Projeção de a em w

Nós pegamos o vetor \boldsymbol{p}.

Figura 23: p é a projeção de a em w

Figura 23: p é a projeção de a em w

Nossa intenção é encontrar a distância entre o ponto \boldsymbol{A}(3,4) e o hiperplano.
Podemos ver na Figura 23 que a distância é a mesma coisa que \left \| p \right \|.
Vamos calcular este valor.

Nós começamos com dois vetores, \boldsymbol{w} = (2,1) o qual é a normal ao hiperplano, e \boldsymbol{a} = (3,4) o qual é o vetor entre a origem e \boldsymbol{A}.

\left \| w \right \| = \sqrt{2^{2} +1^{2}} = \sqrt{5}

Deixe o vetor \boldsymbol{u} seja a direção de \boldsymbol{w}.

u = (\frac{2}{\sqrt{5}},\frac{1}{\sqrt{5}})

\boldsymbol{p} é a projeção ortogonal de \boldsymbol{a} em \boldsymbol{w} então:

\boldsymbol{p} = (\boldsymbol{u}\cdot \boldsymbol{a})\boldsymbol{u}

\boldsymbol{p} = (3\times \frac{2}{\sqrt{5}} + 4 \times \frac{1}{\sqrt{5}})\boldsymbol{u}

\boldsymbol{p} = (\frac{6}{\sqrt{5}} + \frac{4}{\sqrt{5}})\boldsymbol{u}

\boldsymbol{p} = \frac{10}{\sqrt{5}}\boldsymbol{u}

\boldsymbol{p} = (\frac{10}{\sqrt{5}}\times \frac{2}{\sqrt{5}} , \frac{10}{\sqrt{5}} \times \frac{1}{\sqrt{5}})

\boldsymbol{p} = (\frac{20}{5} , \frac{10}{5})

\boldsymbol{p} = (4,2)

\left \| p \right \| = \sqrt{4^{2} +2^{2}} = 2\sqrt{5}

Calcular a margem do hiperplano

Agora que temos a distância \left \| p \right \| entre \boldsymbol{A} e o hiperplano, a margem é definida por:

margem = 2 \left \| p \right \| = 4 \sqrt{5}

Conseguimos! Calculamos a margem do hiperplano!

Conclusão

Aqui termina a segunda parte do nosso tutorial da matemática por trás do SVM.
Teve muita matemática, mas espero que você tenha sido capaz de entender o post sem problemas. Se você tiver alguma pergunta, sinta-se a vontade para perguntar nos comentários.

Referência:

svm-tutorial

Summary
Review Date
Reviewed Item
SVM
Author Rating
51star1star1star1star1star

4 Responses to “SVM – Entendendo sua Matemática – Parte 2 – O hiperplano”

  • Existe um erro na fórmula de soma de vetores. Você colocou: u + v = (u1+u2, v1+v2). O correto é (u1 + v1, u2 + v2)

Trackbacks & Pings

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *