SVM – Entendendo sua Matemática – Parte 2 – O hiperplano
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.
Aqui 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.
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 .
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.
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.
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:
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
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:
Subtração de dois vetores
A subtração de dois vetores funciona da mesma maneira:
u – v = (u1-v1,u2-v2)
Já que a subração não é comutativa, nós podemos considerar o outro caso:
v – u = (v1-u1,v2-u2)
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:
e
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.
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.
e
Agora nós podemos ver nosso esquema orignial assim:
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.
Essa projeção de vetores de x em y
isso nos dá o vetor z
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.
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.
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.
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}.
Nós pegamos o vetor \boldsymbol{p}.
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:





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