Demystifying Maths of SVM

Derivando o objetivo de otimização do Support Vector Machine para um conjunto de dados linearmente separável com um discurso detalhado em cada etapa

Krishna Kumar Mahto Blocked Desbloquear Seguir Seguindo 5 de janeiro

Então, três dias no SVM, eu estava 40% frustrado, 30% inquieto, 20% irritado e 100% ineficiente em termos de fazer meu trabalho. Eu estava preso com a parte de matemática do Support Vector Machine. Passei por vários vídeos do YouTube, vários documentos, PPTs e PDFs de anotações de aula, mas tudo parecia indistinto demais para mim. De todas essas, achei as palestras de Andrew Ng em Stanford as mais úteis. Embora ele caia um pouco na sua capacidade de transmitir tudo o que ele pretende, suas notas e derivações fluem muito suavemente. O que quer que eu vá discutir foi inspirado em 50% pelas palestras de Andrew Ng e suas notas, 20% por um dos cursos de ML que estou cursando e 29% por todo o resto e o resto de 1% vem do pouco trabalho que eu coloquei juntos para construir isso. No final, verifica-se que não é nada difícil entender como o SVM surgiu, já que tudo o que é necessário é a coordenada do ensino médio e a geometria vetorial. Na maior parte, encontrar os pontos certos para criar um mapa sensato foi o que achei difícil. Com este artigo, tentei estabelecer a derivação matemática que criei apor ideias de diferentes fontes, juntamente com o processo de pensamento.

Vamos começar …

Figura 1. Representação diagramática do SVM para dataset linearmente separável (Fonte: https://www.researchgate.net/figure/Classification-of-data-by-support-vector-machine-SVM_fig8_304611323 )

O diagrama não parece ser muito preocupante se você conhece SVM em um alto nível conceitual (o material de Classificador de Margem Ótimo). Embora os casos de conjuntos de dados linearmente separáveis não sejam vistos na vida real, a discussão ao longo deste artigo sobre SVM será apenas para esse contexto. Eu poderia fazer um post separado para uma versão mais geral do SVM.

Hipótese de SVM

Hipótese, através de um modelo de aprendizado de máquina, é o próprio modelo, que não é mais do que nosso classificador (que é uma função).

g (z) = 1 se z ? 0, -1 caso contrário

Rótulos de classe

Os rótulos de classe são indicados como -1 para a classe negativa e +1 para a classe positiva no SVM.

O problema de otimização final que teremos derivado no final deste artigo e o que o SVM resolve para ajustar os melhores parâmetros é:

Problema de otimização que o algoritmo SVM resolve

Este é um problema de otimização convexa , com uma função objetiva de otimização convexa e um conjunto de restrições que definem um conjunto convexo como a região viável. As funções convexas parecem com uma tigela colocada do lado direito para cima. Conjunto convexo é um conjunto de pontos nos quais uma linha que une dois pontos fica inteiramente dentro do conjunto. Eu adoraria falar sobre isso com mais detalhes, mas seria mais conveniente apenas ler os termos em itálico.

Antes de nos aprofundarmos na parte real, devemos estar familiarizados com dois termos – margem funcional e margem geométrica .

Margem funcional e margem geométrica

A seguir, vamos anotar o hiperplano que separa os exemplos positivos e negativos ao longo deste artigo:

Equação de separação do hiperplano; w é o normal para o hiperplano

Cada exemplo de treinamento é indicado como x, e sobrescrito (i) denota i th exemplo de treinamento. Na secção seguinte, y sobrescrito com (i) representa etiqueta correspondente ao i º exemplo formação.

Margem funcional de um hiperplano wrt i th tenção exemplo é definida como:

Margem funcional de um hiperplano com exemplo (denotando como gama-alto sobrescrito com (i))

Margem funcional de um hiperplano o conjunto de dados inteiro é definido como:

Margem funcional de um hiperplano sobre todo o conjunto de dados

Margem geométrico de um wrt hiperplana i th exemplo de formação é definido como margem funcional normalizado pela norma (w):

Margem geométrica com exemplo de treinamento (denotado como gama sobrescrita com (i)).

Margem geométrica para um hiperplano wrt todo o conjunto de dados é definido como:

Margem geométrica de hiperplano sobre todo o conjunto de dados

Nota : Na discussão a seguir, se não for especificado se a margem funcional / geométrica de um hiperplano é mencionada no conjunto de dados inteiro ou em algum exemplo, deve-se presumir que ele esteja em referência a todo o conjunto de dados e não a um único exemplo .

Resumo sobre como o algoritmo SVM funciona, o que ele quer alcançar (interpretando o SVM conceitualmente)

Apenas para ter certeza de que estamos na mesma página, vamos discutir como o SVM funciona. Eu me deparei com duas interpretações do SVM (ou, mais precisamente, o objetivo que o SVM almeja alcançar). Ambas as interpretações citadas abaixo são apenas maneiras diferentes de transmitir a mesma coisa que veremos quando derivamos o objetivo da otimização.

Primeiro,

O SVM maximiza a margem (conforme desenhado na figura 1) aprendendo um limite de decisão / superfície de decisão / separação de hiperplanos adequados.

Segundo,

O SVM maximiza a margem geométrica (como já definido e mostrado abaixo na figura 2) aprendendo um limite de decisão / superfície de decisão / separação / hiperplano adequados.

Fig. 2. A é um exemplo de treinamento, AB é a margem geométrica do hiperplano wrt A

A maneira que eu obtive o objetivo de otimização começa com o uso dos conceitos de margem funcional e geométrica; e depois de estabelecer que as duas interpretações de SVM coexistem entre si, o objetivo de otimização final é derivado.

A derivação

Como dito, começaremos com interpretação de margem funcional e geométrica, e então estabeleceremos a coexistência das duas interpretações de SVM.

Poderíamos ter feito o contrário?

Eu tentei fazer isso, mas acabou não sendo o melhor caminho para começar com a primeira interpretação. Discutiremos por que isso não funcionaria tão bem assim que derivássemos a formulação do objetivo de otimização.

Como já discutido, o SVM visa maximizar a margem geométrica e retorna o hiperplano correspondente. O que isso significa é que, de todos os possíveis hiperplanos (cada hiperplano tem uma margem geométrica no ponto mais próximo a ele, que é a menor de todas as outras margens geométricas definidas em todos os outros pontos), SVM escolhe aquele hiperplano que tem a margem geométrica máxima. Na fig. 3, o hiperplano vermelho é o melhor hiperplano de separação.

Fig. 3. Qual hiperplano é o melhor? – o de vermelho

Isso pode ser matematicamente escrito como,

Problema de otimização inicial

Aparentemente, a função objetivo é a margem geométrica do hiperplano ( w , b) . As restrições representam o fato de que a função objetivo é o mínimo do conjunto de margens geométricas do hiperplano ( w , b) para todos os exemplos de treinamento.

Podemos observar que a formulação da margem geométrica garante que para cada hiperplano, o valor da menor de todas as margens geométricas (computadas para todos os exemplos) seja compartilhado por pelo menos um par de exemplos (um par da classe + ve e outro classe ve) f. Tais pontos são chamados de vetores de suporte (fig. 1).

Portanto, o problema de otimização, conforme definido acima, é equivalente ao problema de maximizar o valor da margem (não valores de margem geométrica / funcional). Margem é definida como a distância entre dois hiperplanos, cada um dos quais é paralelo ao hiperplano separador e passa por vetores de suporte de cada classe (por exemplo, um hiperplano passa por vetores de suporte da classe + ve, enquanto o outro hiperplano passa por vetores de suporte de classe -ve, e ambos são paralelos aos hyperplanes de separação).

Neste ponto, portanto, podemos estabelecer que ambas as interpretações da SVM realmente coexistem, embora tenhamos começado com a segunda interpretação para chegar a essa conclusão. No final, discutirei que, indo no sentido inverso, temos alguma redundância em nossa formulação e, portanto, começamos com uma ideia menos clara do problema.

Vamos denotar os respectivos hiperplanos como:

Hiperplano passando por vetores de suporte positivoHiparque passando por vetores de suporte negativo

Portanto, o problema de otimização pode ser reformulado com a seguinte função objetiva:

Objetivo de otimização reformulado (i) Objetivo de otimização reformulada (ii)

A simplificação até agora foi feita apenas em termos de escrever notações menores e expressões menores. Nós não reduzimos nada em termos dos cálculos a serem feitos em comparação com o que havíamos iniciado (na verdade, seria bom verificar isso por conta própria).

A ideia que será executada como o próximo passo no desenvolvimento da forma final do problema de otimização do SVM, não parece ser tão simples de idealizar.

Temos feito geometria vetorial desde o começo deste artigo. Acontece que o SVM é na verdade um algoritmo de motivação geométrica em seu núcleo. O que é feito para simplificar ainda mais a função objetivo não é difícil de aplicar ou entender, mas a partir de muitas operações que você poderia fazer em uma expressão, zerar a idéia seguinte parece não-trivial.

Aqui está …

Uma das coisas sobre a equação de um hiperplano é que o escalonamento não altera o hiperplano. Dá uma nova equação ( w ' , b') , onde w ' = k. w e b '= k. b ( k é o fator de escala), mas o hiperplano permanece o mesmo no espaço e a margem geométrica, portanto, também não muda (mas a margem funcional muda). Aproveitando esse fator, o que podemos fazer é dimensionar w e b em nossa função objetivo de otimização , de forma que a margem funcional se torne 1.

Isso faz com que nosso problema de otimização seja:

w e b foram dimensionados de tal forma que a margem funcional tornou-se 1

Isso, no verdadeiro sentido, reduziu o problema de otimização, reduzindo o número de cálculos a serem realizados!

Nós passamos por quase toda a derivação, com a última parte que acabamos de ver sendo a mais crucial.

No entanto, existe um problema com esta formulação. A função objetivo é uma função não convexa, que é preferível evitar (fig. 4).

Figura 4. Margem geométrica do hiperplano w = (w1, w2), b = 1; x (i) = (1, 1) (plotadora usada: https://www.geogebra.org/ )

Como aplicamos gradiente descendente para otimizar a função, funções não convexas podem fazer com que o algoritmo fique preso no mínimo local. Mas verifica-se que a quadratura da norma ( w ) no inverso multiplicativo da função objetivo fornece uma função convexa e diferenciável (o inverso da função objetivo também é convexo, mas não é diferenciável em w = 0 , você pode verificar isso usando uma ferramenta de plotagem online). Podemos usar isso como nossa função objetivo, com o problema de otimização sendo modificado agora:

Tornar a função objetivo convexa; este também é o problema de otimização final do SVM

De fato, esta é a função objetiva final que é perfeitamente convexa também (fig. 5)! Nós amamos problemas de otimização convexa.

Fig. 5. A função objetivo final é perfeitamente convexa (Plotter usado: https://www.geogebra.org )

Note que maximizar uma função f é o mesmo que minimizar uma função g = 1 / f . É por isso que o problema de otimização é agora um problema de minimização que se opõe a ser um problema de maximização como antes.

O resultado final é satisfatório.

Mais alguns pontos para concluir:

  1. Começamos com o problema de otimizar a margem geométrica e não a margem funcional. Isso ocorre porque a margem funcional pode ser facilmente aumentada (ou diminuída) simplesmente escalando w e b . Lembre-se de que isso não altera o hiperplano. Então, isso não convergiria para um hiperplano de separação ideal ou haveria muitas iterações que, essencialmente, seriam inúteis. Pode-se argumentar que restringir a magnitude de w pode ajudar a questão. Mas isso não é de todo uma boa ideia, já que || w || = c ( c é alguma constante) é uma restrição não-convexa (como o conjunto viável é a superfície de uma hiperesfera), tornando o problema de otimização não-convexo. Sempre queremos evitar problemas de otimização não convexos.
  2. Começamos com a segunda interpretação e, em seguida, estabelecemos que ambas as interpretações coexistem. Mas inferimos a primeira interpretação do segundo. Acontece que começar com a primeira interpretação pode não ser tão conveniente porque, então, estaríamos começando com dois hiperplanos paralelos, inicialmente separados por alguns | b1-b2 | / || w || onde b1 e b2 são constantes iniciais de suas respectivas equações. Não é difícil ver que a distância entre os dois hiperplanos não pode mudar em nada, mesmo se seu w for alterado (girando os hiperplanos pelo mesmo ângulo). Restringir a região de viabilidade seria importante também para este caso, porque o aprendizado de hiperplanes a distância máxima pode significar simplesmente aprender aqueles hiperplanares que estão o mais longe possível. Isso não serve ao propósito. O problema de otimização restrita seria, portanto, algo como: “maximizar a distância em todos os pontos estão em um lado do hiperplano, e todos os pontos positivos estão em um lado do hiperplano + ve”. Nós poderíamos usar margem funcional para isso, mas então podemos observar que todos os pontos positivos estão no mesmo lado de ambos os vértices, bem como os vésperos, o mesmo vale para os vértices. Então, usar dois hiperplanos é um pouco redundante. Além disso, sem a definição de margem funcional e geométrica (que são definidas em referência a um hiperplano de separação), não seria tão fácil, se não impossível, derivar os resultados que acabamos de fazer.

Notas de rodapé

Espero ter escrito algo sensato com as Matemáticas corretas. Eu usei as anotações de aula de Andrew Ng e sua série de palestras disponíveis no YouTube (tanto de notas de aula off-line de Stanford, não Coursera), algumas ideias de um curso pago que estou fazendo e várias visitas a stackoverflow.com, e então compilei todas elas nisso. Espero que você tenha gostado.

Além disso, gentilmente perdoe a minha caligrafia. Se o que está escrito nessas imagens não estiver claro, deixe-me saber. Vou substituí-los por novas fotos.

Obrigado por ler.