Modelos de Vetores de Suporte
Uma Introdução ao Aprendizado Estatístico de Máquina
Anderson Ara, Raydonal Ospina e Mateus Maia
67ª RBras e 20º SEAGRO, Londrina-PR
24 a 28 de
Julho de 2023
CC BY NC ND
SUMÁRIO
🗒️ Resumo
🗒️ 3. Primeiros passos Hands-on
🗒️ 5. Outros tipos de Modelos de Vetores de Suporte
🗒️ Apêndice
2. Fundamentação teórica
2.1 SVM margens rígidas
Assumindo um conjunto de dados linearmente separável, pode-se reescalar \(\textbf{w}\) e \(b\) de forma que os pontos mais próximos do hiperplano separador satisfaçam \(|\textbf{w} \cdot \textbf{x} + b = k|\), obtendo assim uma a representação canônica do hiperplano adotada para facilitar as considerações subsequentes realizadas na determinação do hiperplano ótimo.
Segundo este sistema, SVM com margens rígidas é aquele em que não há pontos entre \(\textbf{w} \cdot \textbf{x} + b = 0\) e \(\textbf{w} \cdot x + b = \pm k\), partir do sistema:
\[ \begin{cases} \textbf{w} \cdot \textbf{x} + b \geq +k \\ \textbf{w} \cdot \textbf{x} + b \leq -k \end{cases} \tag{1} \label{hip:ot00} \]
Sejam \(\textbf{x}_{1}\) um ponto sobre \(\textbf{w} \cdot \textbf{x}_{1} + b = -k\) e \(\textbf{x}_{2}\) um ponto sobre \(\textbf{w} \cdot \textbf{x}_{1} + b = +k\), fornecendo assim o sistema:
\[\begin{equation} \tag{2}\label{hip:ot1} \begin{cases} \textbf{w} \cdot \textbf{x}_{1} + b = -k \\ \textbf{w} \cdot \textbf{x}_{2} + b = +k \end{cases} \end{equation}\]
Resolvendo o sistema \(\eqref{hip:ot1}\), tem-se:
\[ \textbf{w} \cdot (\textbf{x}_{2} - \textbf{x}_{1}) = 2k \]
Como \(\textbf{w}\) e \(\textbf{x}_{2} - \textbf{x}_{1}\) são ortogonais ao hiperplano separador, esses vetores são paralelos entre si, então:
\[\begin{equation} \label{hip:ot2} \textbf{w} \cdot (\textbf{x}_{2} - \textbf{x}_{1}) = \parallel \textbf{w} \parallel \times \parallel \textbf{x}_{2} - \textbf{x}_{1} \parallel \end{equation}\]
onde \(\parallel \cdot \parallel\) corresponde a norma euclidiana do vetor.
Assim,
\[ \textbf{w} \cdot (\textbf{x}_{2} - \textbf{x}_{1}) = \parallel \textbf{w} \parallel \times \parallel \textbf{x}_{2} - \textbf{x}_{1} \parallel = 2k \]
Tem-se,
\[\begin{equation} \tag{3}\label{hip:ot3} \parallel \textbf{x}_{2} - \textbf{x}_{1} \parallel =\frac{2k}{\parallel \textbf{w} \parallel} \end{equation}\]
A norma \(\parallel \textbf{x}_{2} - \textbf{x}_{1} \parallel\) mede a distância entre os hiperplanos \(\textbf{w} \cdot \textbf{x} = +k\) e \(\textbf{w} \cdot \textbf{x} \geq -k\). Logo, por \(\eqref{hip:ot3}\) pode-se afirmar que a distância entre os mesmos é dada por \(\frac{2k}{\parallel \textbf{w} \parallel}\). Como foi suposto que a margem é sempre maior que esta distância, a minimização de \(\parallel \textbf{w} \parallel=\textbf{w}\cdot \textbf{w}\) ou \(\parallel \textbf{w} \parallel=\frac{1}{2} \textbf{w}\cdot \textbf{w}\) leva a uma maximização de \(\frac{2k}{\parallel \textbf{w} \parallel}\). Portanto, o hiperplano ótimo é definido para os valores de \(\textbf{w}\) e \(b\) que satisfazem as inequações \(\eqref{hip:ot00}\) e para os quais a norma \(\parallel \textbf{w} \parallel\) é mínima.
Figura 1. SVM com margens rígidas. Fonte: Adaptado de Haltuf (2014).
Para o caso particular em que \(k = 1\), as inequações apresentadas em na expressão \(\eqref{hip:ot00}\), resultando na seguinte da forma (Lorena e Carvalho 2003):
\[\begin{equation} \label{hip:ot0} \begin{cases} \textbf{w} \cdot \textbf{x} + b \geq +1 \\ \textbf{w} \cdot \textbf{x} + b \leq -1 \end{cases} \end{equation}\]
A Figura 1, ilustra um SVM com margens rígidas.
Assumindo um conjunto linearmente separável da forma:
\[\begin{equation*} D = \lbrace (\textbf{x}_{1} , y_{1} ), (\textbf{x}_{2} , y_{2} ), \ldots, (\textbf{x}_{n} , y_{n} )\rbrace \subseteq \mathcal{R}^{n} \times \lbrace +1, -1 \rbrace \end{equation*}\]
Então, devemos obter uma função para ser otimizada, que descreveremos por:
\[\begin{equation*} \min_{\textbf{w},b}f(\textbf{w},b) = \min_{\textbf{w},b}f(\textbf{w},b) - \frac{1}{2} (\textbf{w} \cdot \textbf{w}). \end{equation*}\]
sujeito às restrições:
\[\begin{equation*} g_{i}(\textbf{w},b)= y_{i}(\textbf{w} \cdot \textbf{x} - b) - 1 \geq 0, \end{equation*}\] para \(i = 1, \ldots, n\). O Lagrangiano resulta na seguinte forma:
\[\begin{eqnarray} L(\boldsymbol{\alpha},\textbf{w},b) &=& f(\textbf{w},b) - \sum^{n}_{i=1} \alpha_{i}g_{i}(\textbf{w},b) \nonumber \\ &=& \frac{1}{2}\textbf{w} \cdot \textbf{w} - \sum^{n}_{i=1} \alpha_{i}(y_{i}(\textbf{w} \cdot \textbf{x}_{i} - b)-1) \nonumber \\ &=& \frac{1}{2}\textbf{w} \cdot \textbf{w} - \sum^{n}_{i=1} \alpha_{i} y_{i} \textbf{w} \cdot \textbf{x}_i + b \sum^{n}_{i=1}\alpha_{i} y_{i} + \sum^{n}_{i=1}\alpha_{i} \tag{4}\label{eqdual} \end{eqnarray}\]
Isso nos fornece o problema de otimização de Lagrange para classificadores com margem máxima.
\[ \max_{\textbf{a}} \min_{\textbf{w},b}L(\boldsymbol{\alpha},\textbf{w},b) , \] sendo \(\alpha \geq 0\), para \(i = 1, \ldots, n\).
Sejam \(\boldsymbol{\alpha}^{\ast},\textbf{w}^{\ast}\) e \(b\) uma solução para o problema de otimização Lagrangiano, de modo que:
\[ \max_{\textbf{a}} \min_{\textbf{w},b}L(\boldsymbol{\alpha},\textbf{w},b)=L(\boldsymbol{\alpha}^{\ast},\textbf{w}^{\ast},b^{\ast}) \]
Então, uma vez que \(f\) é convexa e as restrições \(g_i\) são lineares, a solução \(\boldsymbol{\alpha}^{\ast}, \textbf{w}^{\ast}\) e \(b^{\ast}\) irá satisfazer as seguintes condições KKT:
\[\begin{eqnarray} \frac{\partial L}{\partial \textbf{w}}(\boldsymbol{\alpha}^{\ast}, \textbf{w}^{\ast} , b^{\ast} )&=& \boldsymbol{0}, \tag{5}\label{kkt:1} \\ \frac{\partial L}{\partial b}(\boldsymbol{\alpha}^{\ast}, \textbf{w}^{\ast} , b^{\ast} ) &=& 0, \tag{6}\label{kkt:2} \\ \alpha^{\ast}_{i} (y_{i}(\textbf{w}^{\ast} \cdot \textbf{x}^{\ast}_{1}-b )-1 ) & = & 0, \tag{7}\label{kkt:3} \\ y_{i}(\textbf{w}^{\ast} \cdot \textbf{x}^{\ast}_{1}-b )-1 & \geq & 0, \tag{8}\label{kkt:4} \\ \alpha^{\ast} & \geq & 0. \tag{9}\label{kkt:5} \end{eqnarray}\]
para \(i = 1, \ldots , n\).
As Equações \(\eqref{kkt:1}\) e \(\eqref{kkt:2}\) asseguram que \(\textbf{w}^{\ast} \cdot b^{\ast}\) são pontos de sela do Lagrangiano. A condição de complementaridade da Equação \(\eqref{kkt:3}\) implica que \(\textbf{w}^{\ast}\) e \(b^{\ast}\) também são soluções para o problema de otimização sugerido.
\[ \max_{\textbf{a}} \min_{\textbf{w},b}L(\boldsymbol{\alpha},\textbf{w},b)=L(\boldsymbol{\alpha}^{\ast},\textbf{w}^{\ast},b^{\ast}) = f(\textbf{w}^{\ast},b^{\ast}) \]
Assim pode-se usar a otimização Lagrangiana para calcular a margem máxima. Finalmente, as Equações \(\eqref{kkt:3}\), \(\eqref{kkt:4}\) e \(\eqref{kkt:5}\) asseguram que a solução se enquadre nas regiões aceitáveis.
Para resolver a otimização Lagrangiana, será construído o Lagrangiano dual, como primeiro passo encontra-se os pontos \(\textbf{w}^{\ast}\) e \(b^{\ast}\). Sabe-se também que estes pontos têm que estar no ponto de sela do Lagrangiano.
Aplicando a primeira condição KKT \(\eqref{kkt:1}\), encontra-se a derivada parcial do Lagrangiano \(L\) em relação à \(\textbf{w}\)
\[ \frac{\partial L}{\partial \textbf{w}}(\textbf{w}^{\ast},b)=\textbf{w}^{\ast} - \sum^{n}_{i=1} \alpha_{i}y_{i}\textbf{x}_{i}= \boldsymbol{0} \]
onde
\[ \tag{10}\label{w_asterisco_exp} \textbf{w}^{\ast} = \sum^{n}_{i=1} \alpha_{i}y_{i}\textbf{x}_{i} \]
Utilizando a segunda expressão do KKT \(\eqref{kkt:2}\), encontra-se a derivada de \(L\) em relação a \(\textbf{b}\):
\[ \tag{11}\label{b_astestisco} \frac{\partial L}{\partial b}(\textbf{w},b^{\ast})= \sum^{n}_{i=1} \alpha_{i}y_{i} = 0 \]
A derivada parcial de \(L\) em relação a \(b\) não produz uma expressão para \(b^{\ast}\) mas em vez disso, nos fornece a restrição de que no ponto de sela \(b^{\ast}\) expressão \(\sum^{n}_{i=1} \alpha_{i}y_{i} = 0\). No entanto, pode-se recuperar um valor para \(b^{\ast}\) da estrutura dos dados de treinamento \(D\) e do fato de que a rotação ideal \(\textbf{w}^{\ast}\) da superfície de decisão. Considere que, num classificador de margem máxima, o hiperplano para a classe \(+1\) tem que passar por algum ponto \(\textbf{x}_{p}\), mais próximo da classe \(+1\). Isso nos permite calcular o deslocamento de \(b^{+}\) do hiperplano para a classe \(+1\) como:
Para o rótulo \(+1\) obtém-se:
\[ b^{+}=\min \{ \textbf{w}^{\ast} \cdot \textbf{x}|(\textbf{x},y) \in D \text{ com } y = +1 \} \]
E no caso da classe ser \(-1\) tem-se:
\[ b^{-}=\min \{ \textbf{w}^{\ast} \cdot \textbf{x}|(\textbf{x},y) \in D \text{ com } y = -1 \} \]
Assim os classificadores de margem máxima, tem a superfície de decisão está localizada entre os dois hiperplanos de apoio. Essa percepção permite calcular \(b^{\ast}\) como:
\[\begin{equation} \tag{12}\label{b_asterisco2} b^{\ast}=\frac{b^{+}+b^{-}}{2} \end{equation}\]
Vale ressaltar que tanto \(\textbf{w}^{\ast}\) como \(b^{\ast}\) podem ser expressos em termos de \(\boldsymbol{\alpha}\) pelo uso repetido da Equação \(\eqref{w_asterisco_exp}\). Isso significa que a superfície de decisão ideal \(\textbf{w}^{\ast} \cdot \textbf{x} = \textbf{b}^{\ast}\) é completamente determinada pelo valor de \(\alpha\), e encontrar uma solução \(\boldsymbol{\alpha}^{\ast}\) mostra a superfície de decisão. Encontrando a solução \(\boldsymbol{\alpha}^{\ast}\) resolve-se o Lagrangiano dual. Substituindo \(\eqref{w_asterisco_exp}\) em \(\eqref{eqdual}\) tem-se:
\[ \phi( \alpha) = f(\textbf{w}^{\ast},b^{\ast}) = L(\boldsymbol{\alpha}^{\ast},\textbf{w}^{\ast},b^{\ast}) = \sum^{n}_{i=1} \alpha_{i} - \frac{1}{2} \sum^{n}_{i=1} \sum^{n}_{j=1} \alpha_{i}\alpha_{j} y_{i} y_{j} \textbf{x}_{i} \cdot \textbf{x}_{j} \]
Isto dá origem à dupla otimização Lagrangiana para classificadores de margem máxima indicado na seguinte proposição.
O Lagrangiano Duplo para Margens Máximas, é encontrado a partir do valor máximo da função:
\[ \max_{\alpha} \phi(\alpha) = \max_{\alpha} \Bigg( \sum^{n}_{i=1} \alpha_{i} - \frac{1}{2} \sum^{n}_{i=1} \sum^{n}_{j=1} \alpha_{i}\alpha_{j} y_{i} y_{j} \textbf{x}_{i} \cdot \textbf{x}_{j} \Bigg), \]
com restrições em
\[\begin{eqnarray} \sum^{n}_{i=1} \alpha_{i}y_{i} = 0, \nonumber \\ \alpha_{i} \geq 0 \nonumber \end{eqnarray}\]
com \(i = 1, \cdots, n\).
Dada uma solução \(\boldsymbol{\alpha}^{\ast}\) para a otimização Lagrangiana dupla, é interessante observar a condição de complementaridade de KKT \(\eqref{kkt:3}\) em mais detalhes. Essa equação pode ser satisfeita para cada \(i = 1, \dots, l\), somente se \(\alpha^{\ast}_{i} = 0\) ou \(y_{i} (\textbf{w}^{\ast} \cdot x_{i} - b^{\ast}) - 1 = 0\).
Considere o caso em que \(\alpha_{j} > 0\) para algum ponto \((\textbf{x}_{j}, \textbf{y}_{j}) \in D\). Isso significa que para satisfazer a condição de complementaridade, tem-se \(y_{j} (\textbf{w}^{\ast}_{j} \cdot \textbf{x}_{j} - b^{\ast}) - 1 = 0\) em que:
\[\begin{eqnarray} \textbf{w}^{\ast}_{j} \cdot \textbf{x}_{j} = b^{\ast} + 1 \text{ se } y_{i}=+1 \tag{13}\label{lagrot_eq1} \\ \textbf{w}^{\ast}_{j} \cdot \textbf{x}_{j} = b^{\ast} - 1 \text{ se } y_{i}=-1 \nonumber \end{eqnarray}\]
Isso significa que a configuração do ponto de treinamento \((x_{j}, y_{j})\) com um multiplicador Lagrangiano \(\alpha^{\ast}_{j} > 0\) está em um dos dois hiperplanos de suporte, dependendo de seu rótulo \(y_{j}\). Este ponto representa uma restrição na margem em que os hiperplanos de suporte não podem ser movidos além dele. Tais pontos são chamados pontos com vetores de suporte de multiplicadores Lagrangianos diferentes de zero, e uma inspeção detalhada das Equações \(\eqref{w_asterisco_exp}\) e \(\eqref{b_asterisco2}\) revela que apenas vetores de suporte contribuem para a solução da otimização da margem máxima dupla. Agora com \(\alpha^{\ast}_{j} = 0\) para algum ponto \((\textbf{x}_{j}, y_{j}) \in D\). Ou seja, o ponto \(\textbf{x}_{j}\) é um ponto que não está na vizinhança do limite da classe porque temos \(y_{j} (\textbf{w}^{\ast}_{j} \cdot \textbf{x}_{j} - b^{\ast}) - 1 > 0\), em que:
\[\begin{eqnarray*} \textbf{w}^{\ast}_{j} \cdot \textbf{x}_{j} > b^{\ast} + 1 \text{ se } y_{i}=+1 \\ \textbf{w}^{\ast}_{j} \cdot \textbf{x}_{j} < b^{\ast} - 1 \text{ se } y_{i}=-1 \end{eqnarray*}\]
Isto implica que os multiplicadores Lagrangianos de valor zero não restringem a tamanho da margem, relacionando isso ao algoritmo inicial de margem máxima. Desta forma, o problema de otimização primal de margem máxima encontra os respectivos hiperplanos de suporte que estão mais afastados, isto é, criam a margem máxima entre eles.
A percepção de que apenas os vetores de suporte contribuem para a solução dual, conforme apresentado, nos permite expressar o valor de \(b^{\ast}\) de maneira mais elegante. Em vez de ajustar os pontos de cada classe que se encontram mais próximos da superfície, consideramos apenas os pontos do conjunto de treinamento que definem a direção nos hiperplanos de suporte. Se escolhido um vetor de suporte do conjunto de treinamento, digamos \((\textbf{x}_{sv+}, \textbf{y}_{sv+})\), então de acordo com \(\eqref{lagrot_eq1}\) pode-se calcular \(b^{\ast}\) como: \[\begin{equation} \tag{14}\label{lagrot:eq2} b^{\ast}= \textbf{w}^{\ast} \cdot \textbf{x}_{sv+}-1= \sum^{n}_{i=1} \alpha_{i}y_{i}\textbf{x}_{i} \cdot \textbf{x}_{sv+} -1 \end{equation}\]
Lembrando que as funções de decisão em classificadores lineares são baseadas em superfícies de decisão lineares, e a própria função de decisão retorna um rótulo \(+ 1\) para um ponto que fica acima da decisão superfície e um rótulo \(-1\) para um ponto que fica abaixo da superfície de decisão. Com \(\boldsymbol{\alpha}^{\ast}\), \(\textbf{w}^{\ast}\) e \(b^{\ast}\) sendo o resultado da otimização Lagrangiana, então a superfície de decisão ideal é definida como:
\[\begin{equation*} \textbf{w}^{\ast} \cdot \textbf{x}^{\ast} = b^{\ast} \end{equation*}\]
Isso resulta a seguinte função de decisão de margem máxima: \[\begin{equation*} \widehat{f}(\textbf{x}) = sgn(\textbf{w}^{\ast} \cdot \textbf{x}^{\ast} - b^{\ast} ) \end{equation*}\]
Utilizando os resultados de \(\textbf{w}^{\ast}\), e de \(b^{\ast}\), das \(\eqref{w_asterisco_exp}\) e \(\eqref{lagrot:eq2}\), encontra-se:
\[\begin{equation} \tag{15}\label{fun:eqot} \widehat{f}(\textbf{x}) = sgn \Bigg( \sum^{n}_{i=1} \alpha^{\ast}_{i}y_{i}\textbf{x}_{i} \cdot \textbf{x} - \sum^{n}_{i=1} \alpha^{\ast}_{i}y_{i}\textbf{x}_{i} \cdot \textbf{x}_{sv+} + 1 \Bigg) \end{equation}\]
Dessa forma, classificador de margem máxima dual é completamente determinado pelos vetores de suporte, ou seja, pelos pontos em que as restrições nos hiperplanos de margem de apoio são satisfeitas. Por causa dessa característica, o classificador de margem máxima de um SVM também pode-se chamar de função de decisão dual. Além disso, todo este processo é considerado um SVM linear, uma vez que é baseada em uma superfície de decisão linear.
2.2 SVM margens suaves
O SVM com margens suaves é uma extensão do SVM com margens rígidas apresentado na seção anterior, onde se acrescenta variáveis de folga \(\xi_{i}\) , para todo \(i = 1, \ldots , n\) para a construção das superfícies de decisão. Essas variáveis aliviam as restrições impostas ao problema de otimização, que é formulado da seguinte maneira para este caso:
\[\begin{equation} \tag{16}\label{eqmargensuav1} y_{i} (\textbf{w} \cdot \textbf{x}_{i} + b) \geq 1 - \xi_{i} \end{equation}\] sendo \(\xi_{i} \geq 0\) , para todo \(i = 1, \ldots , n\)
A aplicação desse procedimento suaviza as margens do classificador linear, permitindo que alguns dados se situem entre os hiperplanos formados pelas margens e também que a ocorram alguns erros de classificação. Isso explica o nome “SVM com margens suaves”.
Uma forma de minimizar \(\xi_{i}\) é utilizando: \[\begin{equation} \tag{17}\label{minisarepsilon} \min_{\textbf{w},b,\boldsymbol{\xi} } = \frac{1}{2} \textbf{w} \cdot \textbf{w} + C \Bigg( \sum^{n}_{i=1} \xi_{i} \Bigg) \end{equation}\] sendo \(C\) a constante de regularização que impõe um peso à minimização dos erros (\(\xi\)) no conjunto de treinamento no que se refere à minimização do modelo.
O termo \(\sum^{n}_{i=1} \xi_{i}\) pode ser entendido como a minimização dos erros marginais, pois um \(\xi \in (0,1]\), indica uma observação entre as margens. Utilizando o método de otimização Lagrangiana, tem-se a seguinte expressão:
\[\begin{equation} \max_{\alpha} \Bigg( \sum^{n}_{i=1} \alpha_{i} - \frac{1}{2} \sum^{n}_{i=1} \sum^{n}_{j=1} \alpha_{i}\alpha_{j} y_{i} y_{j} \textbf{x}_{i} \cdot \textbf{x}_{j} \Bigg) \end{equation}\]
\[ \text{ Sujeito as restrições } = \begin{cases} 0 \leq \alpha_{i} \leq C, & \quad \forall \ 1, \ldots,n , \\ \sum^{n}_{i=1} \alpha_{i} y_{i} =0 & \quad \end{cases} \]
Pode-se observar que essa formulação é igual à apresentada para as SVMs de margens rígidas, a não ser pela restrição nos \(\alpha_{i}\) que, agora, são limitados pelo valor de \(C\).
A variável \(b^{\ast}\) provém novamente de \(\boldsymbol{\alpha}^{\ast}\) e das condições de Kühn-Tucker (Karush et al. 1959) que neste caso são:
\[\begin{eqnarray} \alpha^{\ast}_{i}(y_{i}(\textbf{w}^{\ast} \cdot \textbf{x} - b^{\ast}) - 1 + \xi_{i}) = 0 \tag{18}\label{eqmargensuav2} \\ (C - \alpha^{\ast}_{i}) \xi_{i} = 0 \tag{19}\label{eqmargensuav3} \end{eqnarray}\]
Se \(\alpha^{\ast}_{i} < C\), pela Equação \(\eqref{eqmargensuav3}\), então pela Equação \(\eqref{eqmargensuav2}\), estes vetores de suporte encontram-se sobre as margens e também são denominados livres. Os vetores de suporte para os quais \(\alpha^{\ast}_{i} = C\) podem representar três casos: erros, se \(\xi_{i} > 1\); pontos corretamente classificados, entre as margens, se \(0<\xi_{i} < 1\) ; ou sobre as margens, se \(\xi_{i} = 1\). O último caso ocorre raramente e vetores de suporte anteriores são denominados limitados (Pontil e Verri 1998).
A Figura 2 ilustra uma separação por margens suaves:
Figura 2. SVM com margens suaves.
2.3 SVM não linear
As SVMs lineares são eficazes na classificação de conjuntos de dados linearmente separáveis ou que possuam um comportamento aproximadamente linear, sendo que a versão de margens suaves tolera a presença de alguns outliers. Porém, há muitos casos em que não é possível dividir satisfatoriamente os dados de treinamento por um hiperplano.
As SVMs lidam com problemas não lineares mapeando o conjunto de treinamento de seu espaço original, referenciado como entradas, para um novo espaço de maior dimensão, denominado espaço de características.
A Figura 3 ilustra a ideia da separação de classes por um SVM não linear
Figura 3. SVM não linear.
Seja \(\boldsymbol{\phi} : \mathcal{R}^{p} \rightarrow \mathcal{F}\) um mapeamento, em que \(\textbf{x}\) é o espaço de entradas e \(\mathcal{F}\) denota o espaço de características. A escolha apropriada da função de mapeamento \(\boldsymbol{\phi}\) faz com que o conjunto de treinamento mapeado em \(\mathcal{F}\) possa ser separado por uma SVM linear.
O uso desse procedimento é motivado pelo teorema de Cover visto em Haykin e Network (2004). Dado um conjunto de dados não linear no espaço de entradas \(\textbf{x}\), esse teorema afirma que \(\textbf{x}\) pode ser transformado por um espaço de características \(\mathcal{F}\) em que, com alta chance, os dados são linearmente separáveis. Para isso, duas condições devem ser satisfeitas. A primeira é que a transformação seja não linear, enquanto a segunda é que a dimensão do espaço de características seja suficientemente alta.
Logo, mapeia-se de início os dados para um espaço de maior dimensão e aplica-se a SVM linear sobre este espaço. Essa dimensão encontra o hiperplano com maior margem de separação, garantindo assim uma boa generalização, sendo portanto a versão de SVM não linear com margens suaves bem mais generalizável.
Para realizar o mapeamento, aplica-se aos exemplos presentes no problema de otimização Lagrangiana conforme ilustrado a seguir:
\[ \tag{20}\label{eqmargensuav4} \max_{\alpha} \Bigg( \sum^{n}_{i=1} \alpha_{i} - \frac{1}{2} \sum^{n}_{i=1} \sum^{n}_{j=1} \alpha_{i}\alpha_{j} y_{i} y_{j} \boldsymbol{\phi}(\textbf{x}_{i}) \cdot \boldsymbol{\phi}(\textbf{x}_{j}) \Bigg), \]
O classificador extraído se torna:
\[ \tag{21}\label{eqmargensuav5} g(x) = sgn \Bigg(\sum^{n}_{x_i \in sv } \alpha_{i}y_{i} \boldsymbol{\phi}(\textbf{x}) \cdot \boldsymbol{\phi}(\textbf{x}) + b^{\ast} \Bigg) \]
Como \(\mathcal{F}\) pode ter dimensão muito alta (até mesmo infinita), a computação de \(\boldsymbol{\phi}\) pode ser extremamente custosa ou inviável. Porém, percebe-se pelas Equações \(\eqref{eqmargensuav4}\) e \(\eqref{eqmargensuav5}\) que a única informação necessária sobre o mapeamento é de como realizar o cálculo de produtos escalares entre as observações no espaço de características, pois tem-se sempre \(\boldsymbol{\phi}(\textbf{x}_{i})\) e \(\boldsymbol{\phi}(\textbf{x}_{j})\), para duas observações \(\textbf{x}_{i}\) e \(\textbf{x}_{j}\) , em conjunto. Isso é obtido com o uso de funções denominadas kernels.
Um kernel é uma função que recebe dois vetores \(\textbf{x}_{i}\) e \(\textbf{x}_{j}\) do espaço de entradas e computa o produto escalar desses dados no espaço de características, que é escrito da seguinte forma:
\[ K(\textbf{x}_{i},\textbf{x}_{j}) = \boldsymbol{\phi}(\textbf{x}_{i}) \cdot \boldsymbol{\phi}(\textbf{x}_{j}) \] Os tipos de função acima são definidos como as funções de kernel semidefinidas (Courant e Hilbert 1953) e vários tipos de funções de kernel podem ser usados em exemplos distintos. A escolha de funções específicas do kernel fornece mapeamentos não lineares exclusivos e o desempenho do SVM resultante geralmente depende da escolha apropriada do kernel (Jebara 2004).
É comum empregar a função kernel sem conhecer a função de mapeamento \(\phi\), que é gerado implicitamente. A utilidade dos kernels está, portanto, em sua capacidade de representar espaços abstratos. Vale ressaltar que os kernels para construção dos suportes de vetores é necessário que satisfaçam as condições de Mercer Campbell, Sturim, e Reynolds (2006).
Os kernels utilizados nesta material estão expostos na Tabela abaixo e possuem hiperparâmetros \(\gamma\), \(d\) e \(q\) sendo \(\gamma >0\), \(d \in \mathcal{R}\) e \(q \in \mathcal{N}\).
As funções kernel mais utilizados estão expostos na Tabela a seguir.
| Tipo de Kernel | \(K(\textbf{x}_{i},\textbf{x}_{j})\) | Parâmetros |
|---|---|---|
| Linear | \(\sigma(\textbf{x}_{i} \cdot \textbf{x}_{j})+d\) | \(\sigma,d\) |
| Polinomial | \((\sigma(\textbf{x}_{i} \cdot \textbf{x}_{j})+d)^{q}\) | \(\sigma,d, q\) |
| Gaussiano | \(\exp(\frac{-\parallel \textbf{x}_{i} - \textbf{x}_{j}\parallel ^2}{2\sigma^2})\) | \(\sigma\) |
| Laplaciano | \(\exp(-\sigma \parallel \textbf{x}_{i} - \textbf{x}_{j} \parallel )\) | \(\sigma\) |
| Cauchy | \(\frac{1}{1+\frac{\parallel\textbf{x}_{i}-\textbf{x}_{j}\parallel^2}{\sigma^2}}\) | \(\sigma\) |
Sendo \(d, \sigma > 0\) e \(q \in \mathcal{N}\).
Exemplificando a forma como o kernel \(K(\textbf{x}_{i},\textbf{x}_{j})\) mapea os dados através do kernel para uma dimensão maior, podemos pensar no seguinte, exemplo. Seja \(\phi : \mathcal{R}^{2} \rightarrow \mathcal{R}^{3}\) e suponhamos que o kernel é polinomial com \(\sigma =1\), \(d = 0\), \(q = 2\), onde \(\phi(\textbf{x}_{i})=\big(x_{1i}^{2},x_{2i}^{2},\sqrt{2}x_{1i}x_{2i}\big)\), então:
\[K(\textbf{x}_{1},\textbf{x}_{2}) = \phi(\textbf{x}_{1}) \cdot \phi(\textbf{x}_{2}) = (\textbf{x}_{1} \cdot \textbf{x}_{2})^{2}\].
é uma superficie em \(\mathcal{R}^{3}.\)
A Figura 4 mostra três conjuntos de dados e suas projeções no espaço de característica via o uso do kernel. Os pontos de dados vermelhos e azuis pertencem a classes diferentes e, evidentemente, é impossível separá-los por uma linha reta no espaço de dados original. No entanto, após uma transformação de kernel em um espaço dimensional mais alto, agora é possível separá-los usando um plano linear (contorno branco), que se traduz em um limite não linear no espaço original. Nesses exemplos, foi usado um kernel Gaussiano com diferentes valores de \(\sigma\).
Figura 4. Ilustração do mapeamento dos dados através do kernel Gaussiano. Fonte: Adaptado de Pilario et al. (2019)