SVM – Entendendo Sua Matemática – Parte 3 – O Hiperplano ótimo

On 13 de janeiro de 2016 by Ricardo Câmara

Esta é a terceira parte da série de post sobre a matemática por trás do SVM. Se você não leu os artigos anteriores, você pode querer lê-los antes:

SVM – Entendendo Sua Matemática

SVM – Entendendo Sua Matemática – Parte 1 – A Margem

SVM – Entendendo Sua Matemática – Parte 2 – O Hiperplano

SVM – Entendendo Sua Matemática – Parte 3 – O Hiperplano ótimo

Sobre o que este artigo se trata?

O objetivo principal deste artigo é mostrar para você o raciocínio que nos permite encontrar o hiperplano ótimo no SVM.

Aqui está resumidamene o que você verá:

– Como podemos encontrar hiperplano ótimo?
– Como nós calculamos a distância entre dois hiperplanos?
– Qual é o problema de otimização do SVM?

Como podemos encontrar hiperplano ótimo no SVM?

No final da segunda parte nós computamos a distância \left|\left| p \right| \right| entre o ponto A e o hiperplano a. Nós computamos a margem a qual é igual a 2\left|\left| p \right| \right|.

Entretanto, mesmo ocorrendo a separação dos dados está não era a separação com hiperplano ótimo.

Figura 1: A margem calculada na parte 2 mostra como M1

Figura 1: A margem calculada na parte 2 mostra como M1

Como foi visto na primeira parte o hiperplano máximo e aquele que maximiza a margem em relação aos dados do conjunto de treinamento.

Na figura 1, podemos ver que a margem, delimitada pelas duas linhas azuis, não é a maior margem que separa os dados perfeitamente. A maior margem é a {M}_{2} mostrada na Figura 2, abaixo:

Figura 2: Hiperplano ótimo, é o hiperplano mostrado na parte 2 aumentado para a esquerda.

Figura 2: Hiperplano ótimo, é o hiperplano mostrado na parte 2 aumentado para a esquerda.

Você pode também ver o hiperplano ótimo na Figura 2. O qual é o hiperplano inicial sutilmente estendido para a esquerda. Como eu o encontrei? Eu simplesmente tracei uma linha cruzando o meio de {M}_{2}.

Agora você deve estar pensando que hiperplanos e margens estão bem relacionados. E você está certo.

Se eu tiver um hiperplano eu posso calcular a sua margem em relação a alguns pontos da base de dados. Se eu tiver uma margem delimitada por dois hiperplanos (as linhas azuis escuras da Figura 2), eu posso encontrar ou hiperplano passando exatamente no meio da margem.

Encontrar a maior margem é o mesmo que encontrar o maior hiperplano no SVM.

Como podemos encontrar a maior margem?

É bem simples:

1. Você tem um conjunto de dados
2. seleciona dois hiperplanos os quais separa os dados sem pontos entre eles
3. maximiza a distancia (a margem).

Esta região que contém os dois hiperplanos será a região de maior margem.

Se é tão simples por que todo mundo tem tanta dificuldade em entender o SVM.
É por que como sempre a simplicidade sempre requer alguma abstração e o entendimento de alguma terminologia matemática para se entendida.

Então nós vamos passar por esta fórmula passo a passo:

Passo 1: Se você tem um conjunto de dados D e quer classificá-lo

Na maioria das vezes seus dados serão compostos de n vetores {x}_{i}.

Onde {x}_{i} também é associado com o valor {y}_{i} indicando se o elemento pertence a classe (+1) ou não(-1).

Note que {y}_{i} pode ter somente doi valores +1 e -1.

Além disso, na maioria das vezes, por exemplo quando é classificação de texto, o vetor {x}_{i} acaba tendo várias dimensões. Podemos dizer que {x}_{i} é p-dimensional se ele tiver p dimensões.

Então sua base de dados D é um conjunto de n elementos \left({x}_{i},{y}_{i})

A definição formal da base de dados inicial é:

D = {\{({x}_{i},{y}_{i}) \mid {X}_{i} \in {\mathbb{R}}^{p}, {Y}_{i} \in \{-1,1\} \}}_{i=1}^{n}

Passo 2: Você precisa selecionar dois hiperplanos que separa os dados sem ponto sentre eles

Encontrar dois hiperplanos que separam os dados é fácil quando você tem um lápis e um papel. Mas quando você tem dados p-dimensionais é mais difícil já que não da para desenhar.

Entretanto, mesmo se seus dados são bi-dimensionais pode ser que não seja possível encontrar um hiperplano de separação.

Você só pode fazer se seus dados são separáveis de forma linear.

Figura 3: Dado da esquerda são separáveis de forma linear, dados a esquerda não são

Figura 3: Dado da esquerda são separáveis de forma linear, dados a esquerda não são

Vamos assumir que nosso conjunto de dados D é separável de forma linear. Nós queremos encontrar dois hiperplanos sem pontos entre eles, mas não temos como visualizar o conjunto de dados.

O que sabemos sobre hiperplanos que pode nós ajudar?

Olhando novamente para a equação do hiperplano do SVM

Vimos anteriormente que a equação do hiperplano pode ser descrita em:

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

De qualquer foram, No artigo sobre SVM da wikipedia diz que:

Qualquer hiperplano pode ser escrito como o conjuto de pontos que satisfazem \mathbf{w} \cdot \mathbf{x} {-} b = 0.

Primeiro, nós conhecemos outra notação para o produto escalar, o artigo usa \mathbf{w} \cdot \mathbf{x} ao contrário de {\mathbf{w}}^{T} \mathbf{x}.

Você pode pensar… De onde vem o -b? Nossa definição anterior está incorreta?

Não muito. De novo é uma questão de notação. Na nossa definição os vetores w e x são tridimensionais, enquanto na definição da Wikipedia eles têem duas dimensões:

Dado dois vetores de 3 dimensões \mathbf{w}(-b,-a,1) e \mathbf{x}(1,x,y)

\mathbf{w}\cdot\mathbf{x} = -b\times (1) + (-a)\times x + 1 \times y

\mathbf{w}\cdot\mathbf{x} = y {-} ax {-} b

Dados dois vetores de 2 dimensões \mathbf{w^\prime}(-a,1) e \mathbf{x^\prime}(x,y).

\mathbf{w^\prime}\cdot\mathbf{x^\prime} = (-a)\times x + 1 \times y

\mathbf{w^\prime}\cdot\mathbf{x^\prime} = y {-} ax

Agora se nós subtraímos b dos dois lados da segunda equação nós temos:

\mathbf{w^\prime}\cdot\mathbf{x^\prime} -b = y – ax -b

\mathbf{w^\prime}\cdot\mathbf{x^\prime}-b = \mathbf{w}\cdot\mathbf{x}

No resto deste post nós iremos usar um vetore de 2 dimensões, como na segunda equação.

Dado um hiperplano H_0 separando a base de dados e satisfazendo:

\mathbf{w}\cdot\mathbf{x} {-} b = 0

Nós podemos selecionar dois outros hiperplanos H_1 e H_2 o qual também separa os dados e também têem as seguintes equações:

\mathbf{w}\cdot\mathbf{x} {-} b=1

e

\mathbf{w}\cdot\mathbf{x} {-} b=-1

E nós escolhemos +1 e -1 por que são os únicos valores que a classe podem ter.

Agora nós queremos ter certeza de que não há pontos entre eles.

Nós não selecionaremos nenhum hiperplano que não satisfacação as seguintes restrições:

Para cada vetor \mathbf{x_i}:

\mathbf{w}\cdot\mathbf{x_i} {-} b \geq 1\;\text{para }\;\mathbf{x_i}\;\text{sendo da classe 1}\;

ou

\mathbf{w}\cdot\mathbf{x_i} {-} b \leq -1\;\text{para }\;\mathbf{x_i}\;\text{sendo da classe {-}1}\;

Entendendo as restrições

Nas figuras a seguir, todos pontos vermelhors são da classe 1 e todos os pontos azuis são da classe -1.

Então vamos olhar para a Figura 4 abaixo e considerar o ponto A. É vermelho então é da classe 1 precisamos verificar não é violada a restrição \mathbf{w}\cdot\mathbf{x_i} {-} b \geq 1.

Quando \mathbf{x_i} = A vemos que o ponto está no hiperplano então \mathbf{w}\cdot\mathbf{x_i} {-} b =1 então a restrição é respeitada o mesmo é aplicado para B.

Quando \mathbf{x_i} = C vemos que o ponto está abaixo do hiperplano então \mathbf{w}\cdot\mathbf{x_i} {-} b > 1 então a restrição é respeitada o mesmo é aplicado para D,E,F e G.

Com um raciocínio análogo você pode ver que a segunda restrição é respeitada para a classe -1.

Figura 4: Dois hiperplanos satisfazendo as restrições

Figura 4: Dois hiperplanos satisfazendo as restrições

Na figura 5 nós vemos mais dois hiperplanos satisfazendo as restrições:

Figura 5: Dois hiperplanos que também satisfazem as restrições.

Figura 5: Dois hiperplanos que também satisfazem as restrições.

E agora olharemos casos onde as restrições não são respeitadas.

Figura 6: O hiperplano da direita não satisfaz a primeira restrição

Figura 6: O hiperplano da direita não satisfaz a primeira restrição

Figura 7: O hiperplano da esquerda não a satisfaz a segunda restrição.

Figura 7: O hiperplano da esquerda não a satisfaz a segunda restrição.

Figura 8: Ambas constantes não são satisfeitas.

Figura 8: Ambas constantes não são satisfeitas.

O que quer dizer quando uma restrição não é respeitada? Isso quer dizer que não podemos selecionar esses dois hiperplanos. Você pode ver que todas as vezes que as restrições não são satisfeitas (Figuras 6,7 e 8) existem pontos entre os hiperplanos.

Pela definição dessas restrições, nós encontramos uma maneira de alcançar nossa itenção inicial de seleção de dois hiperplanos sem pontos entre eles. E funciona não somente para nossos exemplos mas também em p dimensões!

Combinando ambas restrições

Na matemática as pessoas gostam que as coisas sejam expressas concisamente.

As equações:

\mathbf{w}\cdot\mathbf{x_i} {-} b \geq 1\;\text{para }\;\mathbf{x_i}\;\text{sendo da classe 1}\;

e

\mathbf{w}\cdot\mathbf{x_i} {-} b \leq -1\;\text{para }\;\mathbf{x_i}\;\text{sendo da classe {-}1}\;

podem ser combinadas em uma só restrição:

nós começamos com a segunda equação

para x_i sendo da classe {-}1
\mathbf{w}\cdot\mathbf{x_i} {-} b \leq -1\;

E multiplica os dois lados por y_i (o qual é sempre -1 nesta equação)

y_i(\mathbf{w}\cdot\mathbf{x_i} {-} b) \geq y_i({-}1)

o que quer dizer que essa equação pode ser escrita também nesta forma:

y_i(\mathbf{w}\cdot\mathbf{x_i} {-} b) \geq 1\ para\ x_i\ sendo\ da\ classe\ {-}1

Na equação \mathbf{w}\cdot\mathbf{x_i} {-} b \geq 1\;\text{para }\;\mathbf{x_i}\;\text{sendo da classe 1}\;, como y_i = 1 não muda os sinais da inequação.

y_i(\mathbf{w}\cdot\mathbf{x_i} {-} b) \geq 1\ para\ x_i\ sendo\ da\ classe\ 1

nós combinamos essas duas equações e:

y_i(\mathbf{w}\cdot\mathbf{x_i} {-} b) \geq 1\ para\ todo\ 1 \leq i \leq n

Agora nśo temos uma única restrição (y_i(\mathbf{w}\cdot\mathbf{x_i} {-} b) \geq 1\ para\ todo\ 1 \leq i \leq n) ao contrário das duas anteriores, mas são matematicamente equivalentes. Então os efeitos são os mesmos (não haverá pontos entre os hiperplanos).

Passo 3: Maximize a distância entre os dois planos

Esta é provavelmente a parte mais difícil do problema. Mas não se preocupe, nós explicaremos tudo.

a) O que é a distância entre os dois hiperplanos?

Antes de tentar maximizar a distância entre dois hiperplanos, nós primeiramente nos perguntaremos: Como computar isso?

Deixe que:

H_0 seja o hiperplano seja a equação \mathbf{w}\cdot\mathbf{x_i} {-} b = -1\;

H_1 seja o hiperplano seja a equação \mathbf{w}\cdot\mathbf{x_i} {-} b = 1\;

x_0 seja um hiperplano H_0.

Nós podemos chamar m a distância perpendicular entre x_0 ao hiperplano H_1. Pela definição, m é o que chamamos de margem.

Como x_0 está em H_0, m é a distância entre os hiperplanos H_0 e H_1.

Agora nós tentaremos encontrar o valor de m.

Figura 9: m é a distância entre dois hiperplanos

Figura 9: m é a distância entre dois hiperplanos

Você pode estar pensando que se nós adicionarmos m para x_0 nós teremos um outro ponto, e este ponto estará e outro hiperplano!

Mas isso não funcionará, por que m é escalar, e x_0 é um vetor e adicionar escalar a vetor não é possível. Contudo, sabemos que adicionar dois vetores é possível, então se nós transformarmos m nós poderemos fazer a adição.

Podemos encontrar o conjunto de todos os pontos que estão na distância m de x_0. Isso pode ser representado como um círculo:

Figura 10: Todos ponto no círuclo estão na distância m de X0

Figura 10: Todos ponto no círuclo estão na distância m de X0

Olhando a figura, a necessidade do vetor se torna clara. E somente com o comprimento m nós não temos uma informação crucial: a direção. (lembre da parte 2 que vetor tem magnetude e direção).

Nós não podemos adicionar um escalar a um vetor, mas nós sabemos que se multiplicarmos um escalar com um vetor nós teremos outro vetor.

De nossa informação inicial, nós queremos que um vetor:

1. tenha a magnetude m
2. tenha que ser perpendicular ao hiperplano H_1

Felizmente, nós já conhecemos um vetor perpendicular a H_1, que é w (por que H_1 = \mathbf{w} \cdot \mathbf{x} {-} b = 1)

Figura 11: W é perpendicular a H1

Figura 11: W é perpendicular a H1

Vamos definir \mathbf{u} = \frac{\mathbf{w}}{\left \| \mathbf{w} \right \|} o vetor unitário de \mathbf{w}. Como é um vetor unitário {\left \| \mathbf{u} \right \|} = 1 e tem a mesma direção que \mathbf{w} então é perpendicular ao hiperplano.

Figura 12: u é também perpendicular a H1

Figura 12: u é também perpendicular a H1

Se multiplicarmos \mathbf{u} por m nós temos o vetor \mathbf{k} = \mathit{m}\mathbf{u} e:

1. \left \| \mathbf{k} \right \| = \mathit{m}
2. \mathbf{k} é perpendicular a H_1(por que tem a mesma direção que \mathbf{u})

Dessas propriedades podemos ver que \mathbf{k} é o vetor que estamos procurando.

Figura 13: k é o vetor que tamanho m perpendicular a H1

Figura 13: k é o vetor que tamanho m perpendicular a H1

\mathbf{k} = \mathit{m}\mathbf{u} = \mathit{m} \frac{\mathbf{w}}{\left \| \mathbf{w} \right \|}

Pronto! TRansformamos nosso escalar \mathit{m} em um vetor \mathbf{k} o qual pode ser usado para fazermos uma adiçãocom o vetor \mathbf{x}_0.

Se começarmos do ponto \mathbf{x}_0 e adicionarmor k nós encontraremos o ponto \mathbf{z}_0 = \mathbf{x}_0 + \mathbf{k} está no hiperplano H_1 como mostrado na Figura 14.

Figura 14: z0 é um ponto em H1

Figura 14: z0 é um ponto em H1

O fato de que \mathbf{z}_0 está em H_1 significa que

\mathbf{w} \cdot \mathbf{z}_0 {-} b = 1

Podemos substituir \mathbf{z}_0 por \mathbf{x}_0 + \mathbf{k} por que é assim a construiremos.

\mathbf{w} \cdot (\mathbf{x}_0 + \mathbf{k}) {-} b = 1

Nós podemos agora substituir \mathbf{k} usando a equação \mathbf{k} = \mathit{m}\mathbf{u} = \mathit{m} \frac{\mathbf{w}}{\left \| \mathbf{w} \right \|}

\mathbf{w} \cdot (\mathbf{x}_0 + \mathit{m}\frac{\mathbf{w}}{\left \| \mathbf{w} \right \|}) {-} b = 1

Agora nós a expandimos:

\mathbf{w} \cdot \mathbf{x}_0 + \mathit{m}\frac{\mathbf{w} \cdot \mathbf{w}}{\left \| \mathbf{w} \right \|} {-} b = 1

O produto escalar de um vetor com ele mesmo é o quadrado da sua normal então:

\mathbf{w} \cdot \mathbf{x}_0 + \mathit{m}\frac{\left \| \mathbf{w} \right \|^{2}}{\left \| \mathbf{w} \right \|} {-} b = 1

\mathbf{w} \cdot \mathbf{x}_0 + \mathit{m}\left \| \mathbf{w} \right \| {-} b = 1

\mathbf{w} \cdot \mathbf{x}_0 {-} b = 1 {-} \mathit{m}\left \| \mathbf{w} \right \|

Como \mathbf{x}_0 está em H_0 então \mathbf{x} \cdot \mathbf{x}_0 {-} b = {-}1

{-}1 = 1 {-} \mathit{m}\left \| \mathbf{w} \right \|
\mathit{m}\left \| \mathbf{w} \right \| = 2
\mathit{m} = \frac{2}{\left \| \mathbf{w} \right \|}

É isto! Encontramos uma maneira de computar m.

b)Como maximizar a distância entre nossos dois hiperplanos

Agora nós temos a formula para computar a margem:

\textit{m} = \frac{2}{\left \| \mathbf{w} \right \|}

A única variável que podemos mudar nesta fórmula é a normal de \mathbf{w}.

Vamos tentar atribuir a normal diferentes valores:

Se \left \| \mathbf{w} \right \| = 1 então \textit{m} = 2 .

Se \left \| \mathbf{w} \right \| = 2 então \textit{m} = 1 .

Se \left \| \mathbf{w} \right \| = 4 então \textit{m} = \frac{1}{2} .

Podemos ver facilmente que quanto maior a normal, menor será a margem.

Maximizando a margem é o mesmo que minimizar a normal de w

Nossa intenção é maximizar a margem. Entre todos hiperplanos que satifaz as restrições, nós vamos escolher o hiperplano com o menor \left \| \mathbf{w} \right \| por que é o qual terá a maior margem.

Isso nos dá o seguinte problema de otimização:

Minimize em (\left \| \mathbf{w} \right \|,b),

\left \| \mathbf{w} \right \|

sujeito a \mathit{y}_i(\mathbf{w \cdot x_i}{-}b)\geq 1

para cada (\textit{i} = 1,…,\textit{n})

Resolvendo este problema é igual resolver uma equação. Uma vez que tivermos o resolvido, teremos encontrado a tupla (\mathbf{w},b) para cada \left \| \mathbf{w} \right \| menor possível e as restrições são satisfeitas. O qual significa que nós temos a equação do hiperplano ótimo.

Conclusão

Nós descobrimos que encontrando o hiperplano ótimo requer que nós resolvemos um problema de otimização. Problemas de otimização são por si mesmos complicados. E nós preciamos de informações específicas para resolve-los. Por isso que resolver o problema de otimizaçãoserá tratado na Parte 4 dessa série de tutoriais. Obrigado por ler.

Lembrando: Esta será de tutorias foi baseada na série de tutorias do site: http://www.svm-tutorial.com/

Summary
SVM - Hiperplan optimal
Article Name
SVM - Hiperplan optimal
Description
SVM – Entendendo Sua Matemática – Parte 3 – O Hiperplano ótimo
Author
Publisher Name
iMobilis
Publisher Logo

Deixe um comentário

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