Support Vector Machine

Você está aqui

Neste módulo, vamos apresentar uma das mais importantes ferramenta de aprendizado de máquina, o support vector machine . O algoritmo de SVM trata o desafio da complexidade da amostra através de um separador com "alta margem" ("large margin"). De forma intuítiva, um hiperplano separa o conjunto de dados de treinamento com "alta margem" se todos os exemplos estão do lado correto do hiperplano e o mais distantes possível dos dados. Restringir o algortimo para fornecer o hiperplano com maior margem diminui a complexidade mesmo com grandes volumes de dados e alta dimensão. 

Seja ${\bf o}_n = ((x_1 , y_1) , \cdots , (x_n , y_n) \in \mathbb{O}^n$ um conjunto de dados de treinamento, no qual $x_i \in \mathbb{R}^d$ e $y_i \in \{0,1\}$. Dizemos que este conjunto de dados é linearmente separável se existe um hiperplano $(f,b)$ tal que $y_i = 1\!\!1_{ \{ (2y_i -1) ( \langle f , x_i \rangle + b) > 0 \}}.$ Todo hiperplano que satisfaz esta condição minimiza o risco empírico (erro de classificação). Portanto, para qualquer conjunto de dados separável, temos muitos hiperplanos satisfazendo o princípio da minimização do risco empírico. Por exemplo, considere o conjunto de dados de treinamento descrito na Figura 1. 

Figura 1: Conjunto de dados de treinameno separável

 

Enquanto ambos hiperplanos (preto e verde) separam os quatro exemplos, nossa intuição provavelmente escolheria o hiperplano preto ao invés do hiperplano verde. Um forma de formalizarmos nossa intuição consiste no conceito de margem. A margem de um hiperplano com respeito ao conjunto de dados de treinamento é definido com a menor distância entre um ponto no conjunto de dados de treinamento e o hiperplano. Se o hiperplano tem alta margem, então deve separar os dados no conjunto de treinamento mesmo que os dados sejam perturbados em cada exemplo. Support Vector Machine (SVM) é um algoritmo que retorna uma hiperplano que satisfaz o princípio da MRE com maior margem possível. No módulo Método de Núcleo, deduzimos a seguinte equção de otimização ao problema de classificação binária com núcleo.

$$ \min_{ \{ (\alpha_1 , \cdots , \alpha_n) \in \mathbb{R}^n \}} \left\{ \frac{1}{n}  \sum_{i=1}^n \psi(-  (2y_i-1)  \sum_{j=1}^n \alpha_j \mathcal{K}(x_j , x_i)  ) + R \left( \sqrt{ \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j \mathcal{K} (x_i , x_j)}  \right) \right\} ~ ~ (\text{Equação 1}) .$$ 

 Uma vez que aprendemos os coeficientes $(\alpha_1^\star, \cdots , \alpha_n^\star)$ com a equação 1, podemos calcular a previsão de uma nova entrada por $$ h_{f^\star} (x) = 1\!\!1_{ \{ f^\star(x) \geq 0 \}} \quad \text{no qual} \quad f^\star (x) = \sum_{i=1}^n \alpha_i^\star \mathcal{K}(x_i , x) , \quad x \in \chi .$$ O SVM algoritmo consiste no estimador dos coeficientes na equação 1 com função custo $\psi(x) = \max \{0 , 1+x \}$ para todo $x \in \mathbb{R}$ e $R(f) = \lambda \parallel f \parallel^2$ para todo $f \in \mathcal{F}$. A função custo $\psi$ é denominada perda dobradiça ("Hinge Loss").  Denotamos por $[G]_{ij} = \mathcal{K}(x_i , x_j)$ os elementos  da matrix Gram $G$. Sabemos que a solução da equação 1 é dada por $f^\star (\cdot) = \sum_{i=1}^n \alpha^\star_i \mathcal{K}( \cdot , x_i)$ no qual $$\alpha^\star =  (\alpha^\star_1 , \cdots , \alpha^\star_n) = arg \min_{ \{ \alpha= (\alpha_1 , \cdots , \alpha_n) \in \mathbb{R}^n \}} \left\{ \frac{1}{n}  \sum_{i=1}^n \left( \max\{ 0, 1- (2y_i -1) [G\alpha]_{i}\} \right) + \lambda \alpha^T G \alpha \right\} ~ ~ (\text {Equação 2}).$$ Para tornar este problema de otimização suave, tomamos a seguinte variável $\xi_i =  \max\{ 0, 1- (2y_i -1) [G\alpha]_{i}\}$ e reescrevemos o problema de otimização na forma $$ (\alpha^\star , \xi^\star) = arg \min_{  \alpha , ~ \xi \in \mathbb{R}^n  ~ ~  \text{tal que} \\ \xi_i \geq  1- (2y_i -1) [G\alpha]_{i} \\ \xi \geq 0 } \left\{ \frac{1}{n}  \sum_{i=1}^n \xi_i + \lambda \alpha^T G \alpha \right\}.$$ Este problema de otimização é suave e convexo. Portanto satisfaz as condições de Karush-Khun-Tucker para o problema dual Lagrangeano no qual 

 

$$ (\alpha^\star , \xi^\star) = arg \min_{  \alpha , ~ \xi \in \mathbb{R}^n  ~ ~  \text{tal que} \\ \xi_i \geq  1- (2y_i -1) [G\alpha]_{i} \\ \xi \geq 0 } \left\{ \frac{1}{n}  \sum_{i=1}^n \xi_i + \lambda \alpha^T G \alpha - \sum_{i=1}^n  \left( \eta_i (\xi_i - 1- (2y_i -1) [G\alpha]_{i}) + \theta_i \xi_i \right) \right\}.$$  As condições neessárias para a solução do problema de minização são dadas por: 

  • Condições de primeira ordem: $ 2 \lambda [G \alpha^\star ]_j = \sum_{i=1}^n G_{ij} \eta_i (2y_i -1) $ e $\eta_i + \theta_i = \frac{1}{n}$;
  • Condições de Negligência (slackness conditions): $\min \{\eta_i , \xi^\star_i - 1 +(2y_i -1) [G \alpha^\star]_,\}  \}=0$ e $\min \{\theta_ i, \xi_i^\star\} =0$.

 

A partir das condições de primeira ordem nos dizem que $\alpha^\star_i = \eta_i (2y_i-1) / (2 \lambda)$. Desde que $f^\star (x_i) = [G \alpha^\star]_i$, a primeira condição de negligência nos reforça que $\alpha_i^\star = 0$ se $(2y_i-1) f^\star(x_i) > 1$. A segunda condição de negligência com a segunda condição de primeira ordem nos dizem que $\alpha^\star_i = (2y_i -1) / (2 \lambda n)$ se $\xi^\star_i > 0$ e $0 \leq (2y_i -1) \alpha_i^\star \leq 1 / (2 \lambda n) $ caso contrário. Desta forma, temos que se $\xi^\star > 0$ então $\alpha^\star_i$ e $\eta_i$ são diferentes de zero e, protanto, concluímos que $(2y_i-1) f^\star(x_i) = 1- \xi^\star_i < 1$ de acorodo com a condição de negligência. Com isso, chegamos ao seguinte teorema. 

Teorema 1: Support Vector Machine

A solução da equação 2 é dada na forma $f^\star (x) = \sum_{i=1}^n \alpha^\star_i \mathcal{K}(x_i , x) $ para $x \in \mathbb{R}^d$, nos quais 

  • $\alpha_i^\star = 0$ se $(2y_i -1) f^\star (x_i) > 1$;
  • $\alpha_i^\star = (2y_i-1) / (2 \lambda n) $ se $(2y_i -1) f^\star (x_i) < 1$;
  • $0 \leq (2y_i - 1) \alpha^\star_i  \leq 1/(2 \lambda n)$ se $(2y_i -1) f^\star (x_i) < 1$.

Os vetores de dados $x_i \in \mathbb{R}^d$ com índice $i$ tal que $\alpha^\star_i \neq 0$ são denominados vetores de suporte.

A seguir, vamos apresentar uma interpretação geométrica para o algoritmo SVM. Inicialmente, tomamos a função núcleo $\mathcal{K}(x , x^\prime) = \langle x , x^\prime \rangle$ para todo $x , x^\prime \in \mathbb{R}^d$. O RKHS relacionado é dado pelo espaço das formas lineares  $\mathcal{F} = \{ \langle x , \cdot \rangle: x \in \mathbb{R}^d \}$. Neste caso, temos que $$f^\star (x) = \sum_{i=1}^n \alpha_i^\star \langle x_i , x \rangle = \langle \omega^\star , x \rangle \quad \text{com} \quad   \omega^\star = \sum_{i=1}^n \alpha_i^\star x_i .$$ Desta forma o preditor ótimo é dado por $h^\star (x) = 1\!\!1_{ \{ f^\star(x) \geq 0 \}}$. Assim, o vetor normal (perpendicular) ao hiperplano $\omega^\star$ é uma combinação linear dos vetores de suporte, que corresponde aos pontos $x_i$ nos quais  $(2y_i -1) \langle \omega^\star , x_i \rangle \leq 1$.

Figura 2: Classificação Binária com SVM linear.

Na figura 2, o hiperplano que separa pontos  $\{x \in \mathbb{R}^d: \langle \omega^\star , x \rangle=0  \}$ é representado pela linha preta. Por outro lado os hiperplanos margem $\{x \in \mathbb{R}^d: \langle \omega^\star , x \rangle=1  \}$ e $\{x \in \mathbb{R}^d: \langle \omega^\star , x \rangle=-1  \}$ são representados pelas linhas tracejadas em azul e vermelho, respectivamente. Além disso, os vetores de suporte são representados por quadrados. Com isso, deduzimos a seguinte propriedade do algoritmo SVM. Se adicionarmos um ponto $x_{n+1}$ ao conjunto de dados de treinamento para o qual $(2y_{n+1} -1) \langle \omega^\star , x \rangle> 1$, o vetor $\omega^\star$ e o preditor $h^\star$ não se alteram. Em outras palavras, somente dados que são classificados errados ou classificados com baixa margem (isto é, $(2y_{n+1} -1) \langle \omega^\star , x \rangle \geq  1$) influenciam o hiperplano separador $\{x \in \mathbb{R}^d: \langle \omega^\star , x \rangle=0  \}$.

Sobre o Portal Action

O Portal Action é mantido pela Estatcamp - Consultoria Estatística e Qualidade, com o objetivo de disponibilizar uma ferramenta estatística em conjunto com uma fonte de informação útil aos profissionais interessados.

Facebook

CONTATO

  •  Maestro Joao Seppe, 900, São Carlos - SP | CEP 13561-180
  • Telefone: (16) 3376-2047
  • E-Mail: [email protected]