Máquina de vetores de suporte, 30 linhas

Neste artigo, mostrarei como escrever sua máquina de vetores de suporte muito simples sem scikit-learn ou outras bibliotecas com uma implementação pronta em apenas 30 linhas em Python. Se você queria entender o algoritmo SMO, mas parecia muito complicado, este artigo pode ser útil para você.



É impossível explicar o que é a máquina de vetores de suporte Matrix ... Você tem que ver você mesmo.





Tendo aprendido que Habré tem a capacidade de inserir elementos de mídia, criei uma pequena demonstração (se de repente não funcionar, você ainda pode tentar a sorte com a versão no github [1] ). Coloque em um plano (espaço de dois recursos $$$X$ e $$$Y$ ) vários pontos vermelhos e azuis (este é o nosso conjunto de dados) e a máquina fará a classificação (cada ponto do fundo é pintado dependendo de onde a solicitação correspondente seria classificada). Mova os pontos, mude o kernel (eu aconselho você a tentar Funções de Base Radial) e a dureza da borda (constante $$$C$ ). Minhas desculpas pelo terrível código em JS - escrevi nele apenas algumas vezes na minha vida, para entender o algoritmo, use o código Python posteriormente neste artigo.

Contente

• , , , . , — . , — [2] [3], , , .
• « SMO» SMO , , . , , SMO, .
• , «» Python .
• « sklearn.svc.svm» — 2D confusion matrix MNIST.
• «» - .

Support Vector Machine é um método de aprendizado de máquina (aprendizado supervisionado) para resolver problemas de classificação, regressão, detecção de anomalias, etc. Vamos considerá-lo usando o exemplo de um problema de classificação binária. Nosso exemplo de treinamento é um conjunto de vetores de recursos $$$\boldsymbol{x}_i$ classificado em uma das duas classes $$$y_i = \pm 1$ ... Solicitação de classificação - vetor $$$\boldsymbol{x}$ para o qual devemos atribuir a classe $$$+1$ ou $$$-1$ ...



No caso mais simples, as classes da amostra de treinamento podem ser divididas desenhando apenas uma linha reta como na figura (para um número maior de recursos, seria um hiperplano). Agora, quando um pedido chega para classificar algum ponto $$$\boldsymbol{x}$ , é razoável colocá-lo na classe de que lado ficará.



Como escolher a melhor linha reta? Intuitivamente, quero que a linha reta passe no meio entre as classes. Para fazer isso, escreva a equação da linha reta como $$$\boldsymbol{x} \cdot \boldsymbol{w} + b = 0$ e dimensionar os parâmetros para que os pontos do conjunto de dados mais próximos da linha reta satisfaçam $$$\boldsymbol{x} \cdot \boldsymbol{w} + b = \pm 1$ (mais ou menos, dependendo da classe) - esses pontos são chamados de vetores de suporte .



Neste caso, a distância entre os pontos de fronteira das classes é $$$2/|\boldsymbol{w}|$ ... Obviamente, queremos maximizar esse valor para separar as classes da melhor forma possível. Este último é equivalente a minimizar $$$\frac{1}{2} |\boldsymbol{w}|^2$ , todo o problema de otimização está escrito

$$

$$\begin{aligned} &\min \frac{1}{2} |\boldsymbol{w}|^2 \\ \text{subject to: } &y_i \left(\boldsymbol{x}_i \cdot \boldsymbol{w} + b\right) - 1 \geq 0. \end{aligned}$$

Se você resolver, então a classificação a pedido $$$\boldsymbol{x}$ produzido assim

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}\left(\boldsymbol{x} \cdot \boldsymbol{w} + b\right).$$

Esta é a máquina de vetores de suporte mais simples.



E o que fazer no caso em que pontos de classes diferentes se penetram mutuamente como na figura?



Não podemos mais resolver o problema de otimização anterior - não há parâmetros que satisfaçam essas condições. Então, é possível permitir que os pontos violem o limite pelo valor $$$\xi_i \geq 0$ , mas também é desejável que tais violadores sejam o mínimo possível. Isso pode ser alcançado modificando a função objetivo com um termo adicional (regularização $$$L_1$ ):

$$

$$\begin{aligned} &\min\left( \frac{1}{2} |\boldsymbol{w}|^2 + C \sum_i \xi_i \right)\\ \text{subject to: }&\xi_i + y_i \left(\boldsymbol{x}_i \cdot \boldsymbol{w} + b\right) - 1 \geq 0,\\ &\xi_i \geq 0, \end{aligned}$$

e o procedimento de classificação continuará como antes. Aqui o hiperparâmetro $$$C$ é responsável pela força de regularização, ou seja, determina o quão estritamente exigimos pontos para respeitar a fronteira: quanto mais $$$C$ - o mais $$$\xi_i$ irá desaparecer e menos pontos irão violar o limite. Os vetores de suporte, neste caso, são os pontos para os quais $$$\xi_i > 0$ ...



Mas e se o conjunto de treinamento se parecer com o logotipo do The Who e os pontos nunca puderem ser separados por uma linha reta?



Aqui, seremos ajudados por uma técnica engenhosa - o truque do kernel [4] . Porém, para aplicá-lo, deve-se passar ao chamado problema de Lagrange dual (ou dual ). Uma descrição detalhada pode ser encontrada na Wikipedia [5] ou na sexta aula do curso [3] . As variáveis ​​em que o novo problema é resolvido são chamadas de multiplicadores duais ou de Lagrange... O problema duplo é freqüentemente mais simples do que o original e tem boas propriedades adicionais, por exemplo, é côncavo mesmo se o problema original não for convexo. Embora sua solução nem sempre coincida com a solução do problema original (quebra de dualidade), há uma série de teoremas que, sob certas condições, garantem tal coincidência (dualidade forte). E este é apenas o nosso caso, então você pode ir com segurança ao problema duplo

$$

$$\begin{aligned} &\max_{\lambda} \sum_{i=1}^n \lambda_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j (\boldsymbol{x}_i \cdot \boldsymbol{x}_j) \lambda_i \lambda_j,\\ \text{subject to: } &0 \leq \lambda_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,\\ &\sum_{i=1}^n y_i \lambda_i = 0, \end{aligned}$$

Onde $$$\lambda_i$ - variáveis ​​duais. Depois de resolver o problema de maximização, também é necessário calcular o parâmetro $$$b$ , que não está incluído no problema duplo, mas é necessário para o classificador

$$

$$b = \mathbb{E}_{k,\xi_k \neq 0}\left[y_k - \sum_i \lambda_i y_i (\boldsymbol{x}_i \cdot \boldsymbol{x}_k)\right].$$

O classificador pode (e deve) ser reescrito em termos de variáveis ​​duais

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}(f(\boldsymbol{x})),\quad f(\boldsymbol{x}) = \sum_i \lambda_i y_i (\boldsymbol{x}_i \cdot \boldsymbol{x}) + b.$$

Qual é a vantagem dessa gravação? Observe que todos os vetores do conjunto de treinamento estão incluídos aqui exclusivamente na forma de produtos escalares $$$(\boldsymbol{x}_i \cdot \boldsymbol{x}_j)$ ... Você pode primeiro mapear pontos para uma superfície em um espaço de dimensão superior e só então calcular o produto escalar das imagens no novo espaço. Por que fazer isso pode ser visto na figura.



Se o mapeamento for bem-sucedido, as imagens dos pontos são separadas por um hiperplano! Na verdade, tudo é ainda melhor: não há necessidade de exibir, porque estamos apenas interessados ​​no produto escalar, e não nas coordenadas específicas dos pontos. Portanto, todo o procedimento pode ser emulado substituindo o produto escalar pela função $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j)$ , que é chamado de núcleo . Claro, nem toda função pode ser um kernel - pelo menos hipoteticamente, deve haver um mapeamento $$$\varphi$ de tal modo que $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j)=(\varphi(\boldsymbol{x}_i) \cdot \varphi(\boldsymbol{x}_j))$ ... As condições necessárias são determinadas pelo teorema de Mercer [6] . A implementação Python representará linear ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = \boldsymbol{x}_i^T \boldsymbol{x}_j$ ), polinomial ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = (\boldsymbol{x}_i^T \boldsymbol{x}_j)^d$ ) o kernel e o kernel das funções de base radial ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = e^{-\gamma |\boldsymbol{x}_i - \boldsymbol{x}_j|^2}$ ) Como você pode ver nos exemplos, os kernels podem introduzir seus hiperparâmetros específicos no algoritmo, o que também afetará sua operação.



Você pode ter visto um vídeo onde a ação da gravidade é explicada usando o exemplo de um filme de borracha esticado em forma de funil [7] . Isso funciona, uma vez que o movimento de um ponto em uma superfície curva em um espaço de alta dimensão é equivalente ao movimento de sua imagem em um espaço de dimensão inferior, se você fornecer a ele uma métrica não trivial. Na verdade, o núcleo dobra o espaço.

Algoritmo SMO

Então, estamos no objetivo, resta resolver o problema duplo colocado na seção anterior

$$

$$\def\M{{\color{red}M}} \def\L{{\color{blue}L}} \begin{aligned} &\max_{\lambda} \sum_{i=1}^n \lambda_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j K(\boldsymbol{x}_i; \boldsymbol{x}_j) \lambda_i \lambda_j,\\ \text{subject to: } &0 \leq \lambda_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,\\ &\sum_{i=1}^n y_i \lambda_i = 0, \end{aligned}$$

então encontre o parâmetro

$$

$$b = \mathbb{E}_{k,\xi_k \neq 0}[y_k - \sum_i \lambda_i y_i K(\boldsymbol{x}_i; \boldsymbol{x}_k)], \tag{1}$$

e o classificador terá a seguinte forma

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}(f(\boldsymbol{x})),\quad f(\boldsymbol{x}) = \sum_i \lambda_i y_i K(\boldsymbol{x}_i; \boldsymbol{x}) + b. \tag{2}$$

O algoritmo SMO (Sequential minimal optimization, [8] ) para resolver o problema dual é o seguinte. No loop, usando uma heurística complexa ( [9] ), um par de variáveis ​​duais é selecionado $$$\lambda_\M$ e $$$\lambda_\L$ , e então a função objetivo é minimizada sobre eles, com a condição da constância da soma $$$y_\M\lambda_\M + y_\L\lambda_\L$ e restrições $$$0 \leq \lambda_\M \leq C$ , $$$0 \leq \lambda_\L \leq C$ (definindo a dureza da borda). A condição de soma armazena a soma de todos $$$y_i\lambda_i$ inalterado (afinal, não tocamos no resto dos lambdas). O algoritmo pára quando detecta uma observância suficientemente boa das chamadas condições KKT (Karush-Kuna-Tucker [10] ).



Vou fazer algumas simplificações.

• Vou descartar a heurística complexa de seleção de índice (isso é feito no curso da Universidade de Stanford [11] ) e iterarei sobre um índice e selecionarei o outro aleatoriamente.
• Recusarei verificar o CCP e executarei um número predeterminado de iterações com antecedência.
• No próprio procedimento de otimização, em contraste com o trabalho clássico [9] ou a abordagem de Stanford [11] , usarei a equação vetorial de uma linha reta. Isso simplificará muito os cálculos (compare o volume de [12] e [13] ).

Agora, para os detalhes. As informações da amostra de treinamento podem ser escritas na forma de uma matriz

$$

$$\boldsymbol{K} = \begin{pmatrix} y_1 y_1 K(\boldsymbol{x}_1; \boldsymbol{x}_1) & y_1 y_2 K(\boldsymbol{x}_1; \boldsymbol{x}_2) & \dots & y_1 y_N K(\boldsymbol{x}_1; \boldsymbol{x}_N) \\ y_2 y_1 K(\boldsymbol{x}_2; \boldsymbol{x}_1) & y_2 y_2 K(\boldsymbol{x}_2; \boldsymbol{x}_2) & \dots & y_2 y_N K(\boldsymbol{x}_2; \boldsymbol{x}_N) \\ \cdots & \cdots & \cdots & \cdots \\ y_N y_1 K(\boldsymbol{x}_N; \boldsymbol{x}_1) & y_N y_2 K(\boldsymbol{x}_N; \boldsymbol{x}_2) & \dots & y_N y_N K(\boldsymbol{x}_N; \boldsymbol{x}_N) \\ \end{pmatrix}. \tag{3}$$

A seguir, usarei a notação com dois índices ( $$$\boldsymbol{K}_{i,j}$ ) para se referir a um elemento da matriz e com um índice ( $$$\boldsymbol{K}_{k}$ ) para denotar o vetor coluna da matriz. Colete as variáveis ​​duais em um vetor de coluna $$$\boldsymbol{\lambda}$ ... Nós estamos interessados ​​em

$$

$$\max_{\boldsymbol{\lambda}} \underbrace{ \sum_{i=1}^n \lambda_i - \frac12 \boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda} }_{\mathscr{L}}.$$

Suponha que, na iteração atual, queiramos maximizar a função objetivo por índices $$$\L$ e $$$\M$ ... Tomaremos derivados, por isso é conveniente selecionar os termos que contêm os índices $$$\L$ e $$$\M$ ... É fácil fazer na parte com a quantidade $$$\lambda_i$ , mas a forma quadrática exigirá várias transformações.



Ao calcular $$$\boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda}$ a soma é realizada em dois índices, vamos $$$i$ e $$$j$ ... Realce pares de índices contendo $$$\L$ ou $$$\M$ ...





Vamos reescrever o problema combinando tudo o que não contém $$$\lambda_\L$ ou $$$\lambda_\M$ ... Para tornar mais fácil acompanhar os índices, preste atenção a $$$\boldsymbol{K}$ na imagem.

$$

$$\begin{aligned} \mathscr{L} &= \lambda_\M + \lambda_\L - \sum_{j} \lambda_\M \lambda_j K_{\M,j} - \sum_{i} \lambda_\L \lambda_i K_{\L,i} + \text{const} + \\ {\text{}\atop\text{ }} \rightarrow\qquad &+ \frac{1}{2}\lambda_\M^2 K_{\M,\M} + \lambda_\M \lambda_\L K_{\M,\L} + \frac{1}{2}\lambda_\L^2 K_{\L,\L} = \\ &= \lambda_\M \left(1-\sum_{j} \lambda_j K_{\M,j}\right) + \lambda_\L \left(1-\sum_{i} \lambda_i K_{\L,i}\right)+\\ &+\frac{1}{2}\left(\lambda_\M^2 K_{\M,\M} + 2 \lambda_\M \lambda_\L K_{\M,\L}+\lambda_\L^2 K_{\L,\L} \right) + \text{const} = \\ &=\boldsymbol{k}^T_0 \boldsymbol{v}_0 + \frac{1}{2}\boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const}, \end{aligned}$$

Onde $$$\text{const}$ denota termos independentes de $$$\lambda_\L$ ou $$$\lambda_\M$ ... Na última linha, usei a notação

$$

$$\begin{align} \boldsymbol{v}_0 &= (\lambda_\M, \lambda_\L)^T, \tag{4a}\\ \boldsymbol{k}_0 &= \left(1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\M}, 1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\L}\right)^T, \tag{4b}\\ \boldsymbol{Q} &= \begin{pmatrix} K_{\M,\M} & K_{\M,\L} \\ K_{\L,\M} & K_{\L,\L} \\ \end{pmatrix},\tag{4c}\\ \boldsymbol{u} &= (-y_\L, y_\M)^T. \tag{4d} \end{align}$$

Observe que $$$\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0$ não depende de $$$\lambda_\L$ nem de $$$\lambda_\M$

$$

$$\boldsymbol{k}_0 = \begin{pmatrix} 1 - \lambda_\M K_{\M,\M} - \lambda_\L K_{\M,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \lambda_\M K_{\L,\M} - \lambda_\L K_{\L,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} = \begin{pmatrix} 1 - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} - \boldsymbol{Q} \boldsymbol{v}_0.$$

O kernel é simétrico, portanto $$$\boldsymbol{Q}^T = \boldsymbol{Q}$ e você pode escrever

$$

$$\mathscr{L} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0 - \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}_0 + \frac{1}{2}\boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}_0 - \frac{1}{2} \boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const}$$

Queremos realizar a maximização para que $$$y_\L\lambda_\L + y_\M\lambda_\M$ permaneceu constante. Para isso, os novos valores devem estar em linha reta

$$

$$(\lambda_\M^\text{new}, \lambda_\L^\text{new})^T = \boldsymbol{v}(t) = \boldsymbol{v}_0 + t \boldsymbol{u}.$$

É fácil ter certeza de que para qualquer $$$t$

$$

$$y_\M\lambda_\M^\text{new} + y_\L\lambda_\L^\text{new} = y_\M \lambda_\M + y_\L \lambda_\L + t (-y_\M y_\L + y_\L y_\M) = y_\M\lambda_\M + y_\L\lambda_\L.$$

Neste caso, devemos maximizar

$$

$$\mathscr{L}(t) = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}(t) - \frac12 \boldsymbol{v}^{\,T}(t) \, \boldsymbol{Q} \, \boldsymbol{v}(t) + \text{const},$$

o que é fácil de fazer tomando a derivada

$$

$$\begin{align} \frac{d \mathscr{L}(t)}{d t} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \frac{d \boldsymbol{v}}{dt} &- \frac12 \left(\frac{d(\boldsymbol{v}^{\,T} \, \boldsymbol{Q} \, \boldsymbol{v})}{d \boldsymbol{v}}\right)^T \frac{d\boldsymbol{v}}{d t} =\\ &= \boldsymbol{k}_0^T \boldsymbol{u} + \underbrace{\boldsymbol{v}_0^T \boldsymbol{Q}^T \boldsymbol{u} - \boldsymbol{v}^T \boldsymbol{Q}^T \boldsymbol{u}}_{(\boldsymbol{v}_0^T - \boldsymbol{v}^T)\boldsymbol{Q} \boldsymbol{u}} = \boldsymbol{k}_0^T \boldsymbol{u} - t \boldsymbol{u}^T \boldsymbol{Q} \boldsymbol{u}. \end{align}$$

Equacionando a derivada a zero, obtemos

$$

$$t_* = \frac{\boldsymbol{k}^T_0 \boldsymbol{u}}{\boldsymbol{u}^{\,T} \boldsymbol{Q} \boldsymbol{u}}. \tag{5}$$

E mais uma coisa: talvez subamos mais do que o necessário e nos encontremos fora da praça como na foto. Então você precisa dar um passo para trás e retornar à sua fronteira

$$

$$(\lambda_\M^\text{new}, \lambda_\L^\text{new}) = \boldsymbol{v}_0 + t_*^{\text{restr}} \boldsymbol{u}.$$

Isso completa a iteração e seleciona novos índices.

Implementação

O diagrama esquemático de treinamento de uma máquina de vetores de suporte simplificado pode ser escrito como







Vamos dar uma olhada no código em uma linguagem de programação real. Se você não gosta do código dos artigos, pode estudá-lo no github [14] .







Ao criar um objeto da classe SVM, você pode especificar hiperparâmetros. O treinamento é feito chamando a função de ajuste, as classes devem ser especificadas como $$$0$ e $$$1$ (convertido internamente para $$$-1$ e $$$+1$ , feito para maior compatibilidade com sklearn), a dimensão do vetor de recursos é permitida arbitrariamente. A função de previsão é usada para classificação.

Comparação com sklearn.svm.SVC

Não que essa comparação faça muito sentido, pois estamos falando de um algoritmo extremamente simplificado, desenvolvido exclusivamente para fins de ensino aos alunos, mas ainda assim. Para testar (e ver como usar tudo), você pode fazer o seguinte (este código também está disponível no github [14] ).





Após o lançamento, as imagens serão geradas, mas como o algoritmo é aleatório, elas serão ligeiramente diferentes a cada lançamento. Aqui está um exemplo de como o algoritmo simplificado funciona (da esquerda para a direita: kernels linear, polinomial e rbf)



E este é o resultado da versão industrial da máquina de vetores de suporte.



Se a dimensão $$$2$ parece muito pequeno, você ainda pode testar no MNIST





Para MNIST, tentei vários pares aleatórios de classes (o algoritmo simplificado só suporta classificação binária), mas não encontrei nenhuma diferença no trabalho do algoritmo simplificado e do sklearn. A seguinte matriz de confusão dá uma ideia da qualidade.

Conclusão

Obrigado a todos que leram até o fim. Neste artigo, vimos uma implementação simplificada de tutorial de uma máquina de vetores de suporte. Claro, ele não pode competir com um design industrial, mas devido à extrema simplicidade e código compacto em Python, bem como o fato de que todas as idéias básicas de SMO foram preservadas, esta versão de SVM pode muito bem tomar seu lugar no Sala de aula. Deve-se notar que o algoritmo é mais simples não apenas do que um algoritmo muito complicado [9] , mas até mesmo sua versão simplificada da Universidade de Stanford [11] . Afinal, uma máquina de vetores de suporte em 30 linhas é linda.

Lista de referências

1. https://fbeilstein.github.io/simplest_smo_ever/
2. página em http://www.machinelearning.ru
3. "Beginnings of Machine Learning", KAU
4. https://en.wikipedia.org/wiki/Kernel_method
5. https://en.wikipedia.org/wiki/Duality_(optimization)
6. http://www.machinelearning.ru
7. https://www.youtube.com/watch?v=MTY1Kje0yLg
8. https://en.wikipedia.org/wiki/Sequential_minimal_optimization
9. Platt, John. Fast Training of Support Vector Machines using Sequential Minimal Optimization, in Advances in Kernel Methods – Support Vector Learning, B. Scholkopf, C. Burges, A. Smola, eds., MIT Press (1998).
10. https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
11. http://cs229.stanford.edu/materials/smo.pdf
12. https://www.researchgate.net/publication/344460740_Yet_more_simple_SMO_algorithm
13. http://fourier.eng.hmc.edu/e176/lectures/ch9/node9.html
14. https://github.com/fbeilstein/simplest_smo_ever