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
1. Introdução
A aplicação e desenvolvimento de métodos de aprendizado estatístico de máquina é um importante tópico de pesquisa na comunidade acadêmica e industrial. As técnicas de aprendizado de máquina foram aplicadas em inúmeras tarefas de classificação, desde diagnóstico e previsão de câncer (Sato et al. 2019), reconhecimento de fala (Mokgonyane et al. 2019), classificação de texto (Kim, Howland, e Park 2005; Burdisso, Errecalde, e Montes-y-Gómez 2019) e detecção de fraude financeira (Dighe, Patil, e Kokate 2018). A variedade de métodos que têm sido utilizados na área é enorme, e a natureza não paramétrica do aprendizado de máquina pode nos permitir renunciar a muitas suposições paramétricas e permitir que a forma do modelo venha a emergir dos dados (Kunce e Chatterjee 2017).
Os Modelos de Vetores de Suporte são um tipo popular de algoritmos de aprendizado de máquina que podem ser utilizados para tarefas de classificação e regressão que, com frequência, apresenta desempenho preditivo superior ao das redes neurais clássicas (Vladimir Vapnik 1999a; V. N. Vapnik 1999; Campbell e Ying 2011), bem como são conhecidos por sua capacidade de lidar com conjuntos de dados complexos.
A origem destes modelos está relacionada ao desenvolvimento da teoria do aprendizado estatístico (Vladimir Vapnik 1999b) e da teoria da complexidade computacional. A teoria do aprendizado estatístico é uma área que estuda a capacidade de generalização de algoritmos de aprendizado a partir de dados de treinamento limitados. Vladimir Vapnik, junto com Alexey Chervonenkis, desenvolveu a teoria da capacidade de VC (Vapnik-Chervonenkis) para analisar a capacidade de generalização de algoritmos de aprendizado (VN Vapnik e Chervonenkis 1971).
Particularmente para o contexto de classificação, a Máquina de Vetores de Suporte (SVM - Support Vector Machine) (Cortes e Vapnik 1995) desempenha um papel importante entre os possíveis métodos de aprendizado e sua metodologia assume conhecimentos matemáticos básicos da geometria vetorial, do cálculo e dos multiplicadores de Lagrange para estimação dos parâmetros. Além disso, pode ser considerado o método mais jovem, bem estabelecido e bem-sucedido entre os métodos tradicionais de aprendizagem de máquina.
A ideia principal consiste em mapear o espaço de entrada (em geral, o espaço gerado pelas covariáveis) para um espaço de características de alta dimensão (geralmente um espaço de Hilbert o qual é uma generalização do espaço euclidiano que não precisa estar restrita a um número finito de dimensões) por meio de transformação não linear para produzir hiperplanos de separação ideais que separam casos de rótulos de classes diferentes.
A principal característica das SVMs é que o algoritmo procura o hiperplano de separação que maximiza a margem entre as classes. A margem é a menor distância entre o hiperplano e os pontos de dados mais próximos de cada classe. A intuição por trás dessa abordagem é que, ao maximizar a distância entre as margens, estamos construindo um classificador com uma boa capacidade de generalização.
Sua popularidade cresceu devido ao sucesso em diversas aplicações somo:
Reconhecimento de padrões: O SVM é amplamente utilizado no reconhecimento de padrões em imagens e sinais. Por exemplo, pode ser aplicado na classificação de imagens médicas para identificar diferentes tipos de lesões ou na classificação de objetos em imagens de satélite.
Classificação de imagens e visão computacional: O SVM tem sido aplicado com sucesso na classificação de imagens em diversas áreas, como reconhecimento facial, detecção de objetos, segmentação de imagens e categorização de imagens em geral. Ele pode aprender a distinguir entre diferentes classes de objetos com base nas características extraídas das imagens.
Bioinformática e genômica: O SVM é utilizado para a análise de dados biológicos, como sequências de DNA, proteínas e expressão gênica. Ele pode ser aplicado na classificação de sequências de DNA para identificar regiões codificadoras de genes ou na previsão de estruturas de proteínas com base em seus padrões estruturais.
Análise de texto e processamento de linguagem natural: O SVM é aplicado em tarefas de análise de texto, como classificação de sentimentos, detecção de spam, categorização de documentos e extração de informações. Ele pode aprender a distinguir entre diferentes categorias de texto com base em características linguísticas extraídas, como palavras-chave, frequência de termos ou estruturas gramaticais.
Detecção de fraudes: O SVM é usado para a detecção de fraudes em várias áreas, incluindo detecção de fraudes financeiras, identificação de atividades fraudulentas em sistemas de segurança e detecção de comportamentos anômalos em redes de computadores.
Ciências sociais e comportamentais: O SVM pode ser aplicado na análise de dados sociais e comportamentais, como prever o sucesso acadêmico dos alunos com base em dados demográficos e desempenho anterior, analisar padrões de preferência do consumidor ou prever tendências de mercado com base em dados de comportamento do usuário.
Os SVMs são agora um campo importante e ativo de toda a pesquisa em aprendizado estatístico de máquina e são considerados como um caso particular de ’métodos de kernel’ (Evgeniou et al. 2002; Sánchez A 2003; Vermet 2018; Zhang, Liu, e Yang 2021).
Os métodos baseados em Kernel dependem da estrutura hilbertiana do chamado RKHS (reproducing kernel Hilbert space), o espaço de função natural associado ao RKHS. Esses métodos funcionam apenas com produtos internos entre mapas de características das observações no RKHS associado ao kernel; em muitas situações, esses produtos internos podem ser calculados diretamente sem a necessidade de calcular explicitamente o mapa de características de alta dimensão, uma operação frequentemente chamada de “truque do kernel”. Portanto, os métodos baseados em kernel podem ser aplicados a qualquer tipo de dados, desde dados registrados no espaço euclidiano padrão a dados que consistem em histogramas, cadeias, árvores ou gráficos, entre outros.
Figura 1. O mapeamento por \(\phi\) do espaço de entrada para o espaço de características é ativado por uma função de kernel \(K\). Fonte: Adaptado de Jenssen (2013)
Smola et al. (2000) apresentou algumas ótimas propriedades deste algoritmo de aprendizado, incluindo boa capacidade de generalização, alta eficiência em tarefas de predição e, a convexidade da função objetivo que garante um mínimo global. Segundo Shivaswamy, Chu, e Jansche (2007) o sucesso dos modelos de vetores de suporte deve-se principalmente aos seguintes fatores:
Classificação de dados complexos: O SVM tem um bom desempenho na classificação de conjuntos de dados complexos, especialmente aqueles que não são linearmente separáveis. Ele pode lidar com dados de alta dimensionalidade e encontrar hiperplanos de separação ótimos, permitindo a separação eficaz entre diferentes classes.
Eficiência em conjuntos de dados de médio a grande porte: O SVM tem sido eficiente em aplicações que envolvem conjuntos de dados de médio a grande porte. Sua formulação matemática e técnicas de otimização permitem que ele lide com grandes volumes de dados de forma eficiente e escalável.
Capacidade de lidar com diferentes tipos de dados: O SVM pode lidar com diferentes tipos de dados, incluindo dados numéricos e categóricos. Além disso, o uso de kernels permite que o SVM trabalhe com dados não linearmente separáveis, realizando transformações para espaços de maior dimensão.
Regularização e controle de overfitting: O SVM incorpora a regularização em sua formulação, o que ajuda a controlar o overfitting (sobreajuste) dos modelos. Isso é especialmente benéfico quando há ruído ou dados de treinamento limitados.
Interpretabilidade e visualização: Os vetores de suporte, que são os pontos de dados mais relevantes para a construção do hiperplano de separação, fornecem informações interpretáveis e permitem visualizar a separação entre as classes. Isso ajuda na compreensão do modelo e nas análises dos resultados. Neste caso, a interpretação é focada nos dados, diferente da interpretação tradicional focada nos parâmetros estimados do modelo.
Implementações eficientes e disponibilidade de bibliotecas: O SVM possui implementações eficientes em várias linguagens de programação, como R (exemplo, as bibliotecas kernlab e e1071), Python (por exemplo, a biblioteca scikit-learn) e MATLAB. Essas bibliotecas fornecem funcionalidades completas do SVM e facilitam a sua utilização em diversas aplicações.
Alguns trabalhos apresentam a superioridade do SVM quando comparado com outras técnicas de benchmarking de aprendizado supervisionado, destacando resultados de precisão favoráveis (Cueto-López et al. 2019), (Thanh Noi e Kappas 2018) e (Shah e Issac 2018).
Em suma, a Máquina de Vetores de Suporte é um classificador discriminativo que é formalmente projetado por um hiperplano de separação. É uma representação das observações no espaço que são mapeados de forma que diferentes categorias sejam separadas por um espaçamento mais amplo possível. Sua popularidade cresceu devido ao seu sucesso no reconhecimento de dígitos manuscritos, sendo o artigo de Cortes e Vapnik (1995) contendo hoje mais de 60 mil citações.
1.1 Função de Classificação
Para iniciar o entendimento dos modelos de vetores de suporte, considere um problema de classificação binária onde as observações de interesse da variável resposta são denotadas como \(+1\) e \(-1\), isto é, \(y \in \{-1,+1\}\). Ao mesmo tempo, todas as variáveis de entrada variam em \(\mathcal{R}^{p}\), ou seja, podemos visualizar cada observação no universo de dados como um vetor de posição no espaço \(p\)-dimensional \(\mathcal{R}^{p}\), onde \(p\) é o números de variáveis de entrada, \(\mathbf{x} \in \mathcal{R}^{p}\).
Assim, o problema de classificação binária, portanto pode ser escrito na forma:
Seja \(\mathcal{R}^{p}\) o espaço de dados com vetores \(\textbf{x} \in \mathcal{R}^{p}\) como observações das variávies de entrada.
Seja \(S\) um conjunto de amostras tal que \(S \subset \mathcal{R}^{p}\).
Seja \(f: \mathcal{R}^{p} \rightarrow \{+1, -1\}\) a função alvo.
Seja \(D = \{(\textbf{x}, y) \vert ~\textbf{x} \in S \text{ e } y = f (\textbf{x})\}\) o conjunto de treinamento.
Encontre uma função \(\widehat{f}:\mathcal{R}^{p} \rightarrow \{ +1,-1 \}\) usando \(D\) temos que:
\[\widehat{f}(\textbf{x}) \simeq f(\textbf{x})\]
sendo \(\textbf{x} \in \mathcal{R}^{p}\) e \(\widehat{f}(\textbf{x}) \simeq f(\textbf{x})\), em que se quer dizer que \(\widehat{f}(\textbf{x})\) é semelhante ou uma boa estimativa para \(f(\textbf{x})\). Observe que, para este caso, será utilizado a codificação de rótulos da variável resposta como \(\{ +1 , -1 \}\), no sentido de ajustar um modelo \(\widehat{f}\) que se aproxime de \(f\). Outras metodologias podem utilizar outras codificações como verdadeiro e falso ou zero e um. Desta forma, uma linha, plano ou hiperplano, deverá ser construída para separar as classes \(+1\) e \(-1\) o melhor possível, de modo que ela será a superfície de decisão estimada para \(f\).
Neste caso, há a introdução de um viés de linguagem aos problemas de aprendizado de máquina: se um conjunto de treinamento não pode ser separado por uma linha, plano ou hiperplano, então esse conjunto é dito linearmente não separável. Ou seja, não é possível construir uma função de decisão linear para este tipo de problema de aprendizagem de máquina. Quando o conjunto de dados é linearmente separável, fato raro na prática, a tarefa de classificação é solucionada de forma simples por diversos tipos de metodologias.
1.2 Ideias iniciais
Os SVMs são baseados na construção de hiperplanos ótimos para classificar categorias – geralmente em duas classes distintas – bem como fazem o uso do truque do kernel para aumentar a flexibilidade do modelo. Desta forma, estas duas ideias iniciais são brevemente introduzidas nesta seção. O aprofundamento em ambas será realizado mais adiante no texto para, então, a formalização do SVM ser apresentada.
De uma forma geral, os modelos de vetores de suporte consideram as observações de um conjunto de dados como vetores. Para o caso de classificação binária, \(\textbf{x}_i\) refere-se a localização da i-ésima observação em \(\mathcal{R}^p\), espaço vetorial de ordem \(p\), sendo \(\textbf{x}_i=(x_{1_i},x_{2_i},\ldots, x_{p_i})\), bem como \(y_i\) refere-se a categoria da i-ésima observação. A Figura 1 representa 14 observações como vetores a partir da origem em um espaço \(\mathcal{R}^2\).
Figura 2. Na teoria de SVM as observações são consideradas como vetores, sendo o vetor binário \(y=\{\)⚪,🟢\(\}\).
1.2.1 Visão geral de um hiperplano
Em aprendizado de máquina, um hiperplano de separação é uma representação geométrica utilizada para separar dois conjuntos de dados distintos em um espaço dimensional superior.
No caso das Máquinas de Vetores de Suporte (SVM), o objetivo é encontrar um hiperplano ótimo que maximize a distância entre as margens de separação entre as classes.
Considere um problema de classificação binária, sendo o conjunto de dados de treinamento composto por pares de características \((\textbf{x}_i)\) e rótulos de classe correspondentes \(y_i \in \{-1,+1\}\), com \(i=1,...,n\), sendo \(n\) o tamanho da amostra de treinamento.
Se as classes são linearmente separáveis, isso significa que existe um hiperplano que pode separar perfeitamente os pontos de uma classe dos pontos da outra classe.
Em um espaço bidimensional, um hiperplano é uma linha reta que divide os pontos em dois grupos. No entanto, as SVMs podem lidar com espaços de dimensionalidade superior, onde um hiperplano é um subespaço de dimensão um a menos do que o espaço original. Em um espaço tridimensional, um hiperplano é um plano, e assim por diante.
A representação matemática geral de um hiperplano de separação é dada por:
\[f(\textbf{x}) = \textbf{w} \cdot \textbf{x} + b = 0 \] em que
\(\textbf{w}\) é um vetor de pesos que define a orientação do hiperplano.
\(\textbf{x}\) é um vetor de características das observações dos dados de entrada.
\(b\) é um termo de polarização (viés ou bias).
Aqui, \(\textbf{w}\) e \(\textbf{x}\) são vetores. O operador \(\cdot\) representa o produto interno entre \(\textbf{w}\) e \(\textbf{x}\) o qual é representado por \(\textbf{w} \cdot \textbf{x}\) e pode ser entendido como uma medida da ponderação do vetor de características \(\textbf{x}\) na direção do vetor de pesos \(\textbf{w}\). O termo \(b\) controla o deslocamento do hiperplano ao longo do eixo perpendicular a \(\textbf{w}\).
No caso, do problema de classificação binária, a decisão de classificação é baseada no sinal do valor resultante \(\textbf{w} \cdot \textbf{x} + b\). Se o valor for positivo, o ponto de dados será classificado em uma classe (\(y = +1\)), e se for negativo, será classificado na outra classe (\(y = -1\)).
Ou seja, considerando o hiperplano a função de classificação é dada por
\[y=\text{sgn}\left( \textbf{w} \cdot \textbf{x} + b \right)\] com \(\text{sgn}\) a função sinal.
De uma forma geral, infinitos hiperplanos poderiam separar de forma eficiente dados linearmente separáveis para o contexto de classificação binária. A Figura 3 exibe quatro possíveis exemplos de retas separadoras para o conjunto de dados apresentado na Figura 2.
Figura 3. Exemplos de hiperplanos separadados em \(\mathcal{R}^2\).
Intuitivamente, entre as Figuras 3a e 3d, a última reta parece ser mais eficiente na separação de ambas as nuvens de dados, pois está bem ao centro de onde termina uma classe e começa outra. Essa ideia é formalizada pela Figura 4, que indica o hiperplano ótimo para este caso. Ele é construído maximizando a distância entre as margens, a distância entre superior e margem inferior. Desta forma, apenas algumas observações caracterizaram o hiperplano ótimo, estas observações são chamadas de vetores de suporte.
Figura 4. Hiperplano separador ótimo, suas margens e os vetores de suporte, sendo \(y=\{\)⚪,🟢\(\}\).
Além disso, nem sempre é possível encontrar um hiperplano de separação perfeito que separe linearmente os dados. Nesses casos, as SVMs utilizam uma abordagem conhecida como margens suaves (veremos isso mais adiante), que permite erros de classificação e maior generalização no sentido de evitar overfitting. A ideia é permitir que alguns pontos de dados fiquem dentro da margem ou até mesmo do lado errado do hiperplano, a fim de obter uma classificação geral melhor. Isso é controlado pelo parâmetro de regularização \(C\), que equilibra a maximização da margem com a minimização dos erros de classificação.
1.2.2 O truque do kernel
Até o momento, a construção de um hiperplano separador é útil apenas para problema muito simples, com dados linearmente separáveis. Porém, essa não é a realidade da maioria dos conjuntos de dados. Desta forma, a estratégia utilizada no SVM é aumentar virtualmente o espaço de entrada através de um artifício conhecimento como truque do kernel.
Basicamente, se emprega uma função de mapeamento \(\phi (\cdot)\) que é capaz de projetar os dados em dimensões superiores, ou seja,
\[ \phi :\mathcal{R}^p \rightarrow \mathcal{R}^q, ~~~~\text{ com } p < q. \]
Assim, uma vez com o espaço de características aumentado para dimensões superiores é possível buscar um hiperplano que separe as categorias neste novo espaço.
A Figura 5 ilustra essa ideia considerando apenas uma variável explicativa, sendo \(\phi :\mathcal{R} \rightarrow \mathcal{R}^2\), e o hiperplano estimado em \(\mathcal{R}^2\).
Figura 5. Exemplificação da aplicação da função de mapeamento que envolve o truque do kernel, sendo \(y=\{\)⚪,🟢\(\}\).
Através do aumento do espaço de variáveis de entrada e a aplicação do hiperplano separador é possível resolver problemas de classificação para dados linearmente não separáveis, como visto na Figura 5. Existem diferentes tipos de função de mapeamento, mas, de fato, não será necessário defini-las, sendo estas associadas implicitamente aos kernels e ao truque do kernel.
Um kernel \(K\) é uma função que mapeia pares de vetores de características \((\textbf{x}_i, \textbf{x}_j)\) em um produto escalar, ou seja, \[K(\textbf{x}_i, \textbf{x}_j) = \phi(\textbf{x}_i) \cdot \phi(\textbf{x}_j),\] onde \(\phi\) representa a transformação do espaço de características de entrada para o espaço de características com maior dimensão.
Desta forma, o truque do kernel é uma técnica baseada nas funções \(K\) que permite contornar a necessidade de calcular explicitamente o mapeamento para espaços de características de alta dimensão, enquanto ainda se beneficia da capacidade de lidar com dados não linearmente separáveis. Isso é alcançado através da utilização de funções kernel, que são funções capazes de medir a semelhança ou proximidade entre pares de vetores de características no espaço transformado em maior dimensão. A Figura 6 exibe uma visão esquemática da incorporção do kernel.
Figura 6. Uma visão esquemática da incorporação do kernel. Fonte: Adaptado de Harchaoui et al. (2013)
O uso do truque do kernel permite que a SVM opere diretamente no espaço original, sem a necessidade de conhecer explicitamente \(\phi\) ou calcular os vetores transformados \(\phi(\textbf{x}_i)\) e \(\phi(\textbf{x}_j)\). Em vez disso, o produto interno entre os vetores de características transformados é substituído pelo cálculo do kernel, ou seja, \(K(\textbf{x}_i, \textbf{x}_j)\). Existem diferentes tipos de funções kernels e maiores detalhes serão dados mais adiante.
Formalmente, o truque do kernel se baseia na observação de que a maioria das operações dentro do SVM envolve apenas o produto interno dos vetores de características. Em vez de realizar a transformação dos dados para o espaço de alta dimensão, o truque do kernel permite que se calcule implicitamente o produto interno no espaço original, usando uma função kernel.
Ao utilizar o truque do kernel, a SVM pode encontrar hiperplanos de separação ótimos no espaço de características de alta dimensão, mesmo sem precisar conhecer ou calcular explicitamente os vetores transformados. Isso proporciona uma vantagem computacional significativa, pois evita a necessidade de manipular dados em espaços de dimensões muito grandes.
O truque do kernel é essencial para o sucesso das SVMs em lidar com problemas não linearmente separáveis em várias áreas, como reconhecimento de padrões, visão computacional, processamento de linguagem natural, entre outras. Ele oferece uma abordagem flexível e eficiente para lidar com a complexidade dos dados, permitindo que a SVM capture relações complexas e tome decisões de classificação mais precisas.
A próxima seção tem foco na fundamentação teórica dos modelos de máquina de vetores de suporte que, essencialmente, baseia-se em operações com vetores, conceitos de hiperplanos e otimização lagrangeana. Caso seja necessário, uma breve revisão sobre esses tópicos é exibida no Apêndice. Maiores detalhes podem ser encontrados em Winterle e Steinbruch (2000) e Hamel (2011).