Método de Núcleo - SVM

Você está aqui

A classe de preditores lineares são atrativos tanto do ponto de vista de algoritmos quanto do ponto de vista teórico. Porém, o fato dos preditores serem lineares pode gerar alguma desconfiança quanto a representativade da classe. A técnica de núcleo tem como objetivo aliviar este problema. A ideia consiste em transportar os dados de entrada para um espaço de dimensão maior ou infinita denominado "feature space" e então, utilizar preditores lineares. Para ilustrar, considere o problema bidimensional tratado na Figura 1. 

Figura 1: 

Na Figura 1, as duas classes são organizadas no círculo e não são linearmente separáveis. Entretanto, se utilizarmos o círculo como fronteira, podemos separar perfeitamente os dados. Tal preditor é dado na forma $h(x) = sign (x_1^2 + x_2^2 - r^2 )$ e, pode ser descrito de forma linear se definirmos adequadamente o "feature space".  Em particular, tomamos a transformação $x \rightarrow \phi(x)$ no qual $\phi (x) = (x_1^2 , x_2^2, x_1  x_2 , x_1 , x_2 , 1)$. Assim, o classificador baseado no círculo $x_1^2 + x_2^2 - r^2$ pode ser descrito como o hiperplano definido pelo vetor $f = (1,1,0,0,0, -r^2) \in \mathbb{R}^6$. Este hiperplano no "feature space" é especificado por $\langle f , x \rangle = x_1^2 + x_2^2 - r^2 $ e classifica perfeitamente os dados. Assim, ao transportarmos os dados para um espaço de dimensão maior podemos utilizar classificadores lineares e aumentar expressivamente o poder da classe de preditores lineares. 

Tomamos $\phi: \chi \rightarrow D$ uma função Borel mensurável no qual $D$ é um espaço de Hilbert separável com produto interno $\langle \cdot , \cdot \rangle_D$. Assumimos que para todo $x \in \chi$, a norma $\parallel \phi(x) \parallel_D < M$ no qual $M$ é uma contante positiva.  A partir da "feature map" $\phi$, podemos definir uma função de similaridade $\mathcal{K} : \chi \times \chi \rightarrow \mathbb{R}$ satisfazendo $$\mathcal{K} (x , x^\prime) = \langle \phi(x) , \phi(x^\prime ) \rangle_D, \quad x , x^\prime \in \chi.$$ A função de similaridade $\mathcal{K}$ é denominado núcleo ("Kernel"). Por outro lado, dado um núcleo $\mathcal{K}$ obtemos a "feature map" na forma $\phi(x) = \mathcal{K}(\cdot , x)$ para todo $x \in \chi$. 

Como dissemos, a vantagem de utilizarmos núcleo como medida de similaridade é que podemos utilizar preditores lineares em espaços de Hilbert infinito dimensional. Como exemplo, considere o seguinte algoritmo. A ideia consite em calcularmos as médias das duas classes no "feature space" $D$, $$c^{+} = \frac{1}{n^+} \sum_{\{ i: y_i=1 \}} \phi(x_i) \quad \text{e} \quad c^{n} = \frac{1}{n^-} \sum_{\{ i: y_i=0 \}} \phi(x_i),$$ no qual $n^+$ é o total de dados com rótulos positivos e $n^-$ é o total de dados com rótulos negativos. Para um novo ponto $x \in \chi$, escolhemos o rótulo cuja média está "mais próxima" de $\phi(x)$, o que nos leva ao preditor $$y = h^\star(x) = 1\!\!1_{ \{ \left( \langle \phi(x) , c^+ \rangle_D - \langle \phi(x) , c^- \rangle_D + b \right) \geq 0\}} ,$$ no qual $b = \frac{1}{2} \left( \parallel c^- \parallel_D -  \parallel c^+ \parallel_D \right)$ . Ao subtituirmos $c^+$ e $c^-$, obtemos que

\begin{eqnarray*} y = h^\star(x)  &=& 1\!\!1_{ \left\{   \left( \frac{1}{n^+} \sum_{\{i:y_i=1 \}} \langle \phi(x) , \phi(x_i) \rangle_D - \frac{1}{n^-} \sum_{\{i:y_i=0 \}} \langle \phi(x) , \phi(x_i) \rangle_D + b\right) \geq 0 \right\}} \\ \\&=& 1\!\!1_{ \left\{  \left( \frac{1}{n^+} \sum_{\{i:y_i=1 \}} \mathcal{K}(x , x_i) - \frac{1}{n^-} \sum_{\{i:y_i=0 \}}  \mathcal{K}(x , x_i)  + b \right) \geq 0 \right\}} , \end{eqnarray*} no qual

\begin{eqnarray*} b &=& \frac{1}{2} \left(\frac{1}{(n^-)^2} \sum_{\{i:y_i=0 \}} \langle \phi(x) , \phi(x_i) \rangle_D -  \frac{1}{(n^+)^2} \sum_{\{i:y_i=1 \}} \langle \phi(x) , \phi(x_i) \rangle_D \right) \\ &=& \frac{1}{2} \left(\frac{1}{(n^-)^2} \sum_{\{i:y_i=0 \}}  \mathcal{K}(x , x_i) -  \frac{1}{(n^+)^2} \sum_{\{i:y_i=1 \}}  \mathcal{K}(x , x_i) \right) . \end{eqnarray*} Este preditor está relacionado com a máquina de suporte vetorial (support vector machine).  Observe que o preditor acima corresponde a função indicadora $1\!\!1$ composta com um funcional linear limitado sobre o espaço de Hilbert $D$.  

Na sequência, vamos utilizar o processo de contrução do RKHS apresentado no módulo Construção do RKHS. Considere uma função núcleo $\mathcal{K} : \chi \times \chi \rightarrow \mathbb{R}$, isto é, uma função simétrica satisfazendo \[ \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j \mathcal{K} (x_i , x_j) \geq 0 , \] para qualquer escolha de $n \geq 1$, $\alpha_1 , \cdots \alpha_n \in \mathbb{R}$ e $x_1, \cdots , x_n \in \chi$. A função de similaridade $\mathcal{K}$ naturalmente nos fornece um espaço de funções na forma

\[ \mathcal{F} = \left\{ f(\cdot) = \sum_{i=1}^n  \alpha_i \mathcal{K} (x_i , \cdot): ~ \sum_{i=1}^n  \sum_{j=1}^n \alpha_i \alpha_j \mathcal{K} (x_i , x_j) \leq M^2, ~ n \in \mathbb{N}, ~ \alpha_i \in \mathbb{R}, ~ x_i \in \chi \right\}. \] De forma simples, definimos o seguinte produto interno sobre a classe de funções lineares $\mathcal{F}$, $$ \langle \sum_{i=1}^n  \alpha_i \mathcal{K} (x_i , \cdot) , \sum_{j=1}^m  \beta_j \mathcal{K} (x_j , \cdot) \rangle =   \sum_{i=1}^n  \alpha_i \beta_j  \mathcal{K} (x_i , x_j) .$$ A partir do produto interno $\langle  \cdot , \cdot \rangle$ podemos completar $\mathcal{F}$ para obtermos um espaço de Hilbert $\bar{\mathcal{F}}$, que é denominado Reproducing Kernel Hilbert Space (RKHS). Uma propriedade importante do RKHS é que para toda função $f \in \bar{\mathcal{F}}$ temos que $$f(x) = \langle f , \mathcal{K} (\cdot , x) \rangle_{\bar{\mathcal{F}}}, \quad x \in \chi .$$

Conforme apresentado no módulo Algoritmos baseados em função custo, seja $\psi : \mathbb{R} \rightarrow [0 , \infty)$ uma função Borel mensurável satisfazendo $\psi(x) \geq 1\!\!1_{\{ x > 0\}}$.  Típicas escolhas para $\psi$ incluem $\psi(x)=e^x$, $\psi(x) = \log_2 (1+ e^x)$   e $\psi(x) = \max \{1+x , 0\}$, entre outras. A partir da propriedade reprodutiva, a função custo e sua versão empírica são dadas por $$C(f, \mathbb{P}) = \mathbb{E}_{\mathbb{P}} \psi(-f(X) (2Y-1)) = \mathbb{E}_{\mathbb{P}} \psi(- \langle f , \mathcal{K} (\cdot , X) \rangle (2Y-1)) $$ e  $$C_E ({\bf o}_n , f) =  \frac{1}{n}  \sum_{i=1}^n \psi(-f(x_i) (2y_i-1)) = \frac{1}{n}  \sum_{i=1}^n \psi(-  \langle f , \mathcal{K} (\cdot , x_i) \rangle (2y_i-1)), $$ para todo conjunto de dados ${\bf o}_n = ((x_1,y_1), \cdots , (x_n,y_n)) \in \mathbb{O}^n$. Com esta notação, deduzimos a seguinte desigualdade relacionada com a complexidade de Rademacher $$L(\mathbb{P} , h_f) \leq C_E({\bf o}_n , f  ) + 2L_{\psi} \mathbb{E}_{\mu^n} \sup_{f \in \bar{\mathcal{F}}} \frac{1}{n}  \sum_{i=1}^n \sigma_if(x_i) +   3 B \sqrt{\frac{\ln(2/\delta)}{2n} }, \quad {\bf o}_n \in \hat{G},$$ no qual $\mathbb{P}(\hat{G}) > 1 - \delta$ com $0 < \delta < 1/2$ e $h_f = 1\!\!1_{ \{ f \geq 0 \}}$ com $f \in \bar{\mathcal{F}}$. A partir desta desigualdade, vamos nos concentrar em minimizar a função de custo empírica $C_E$. 

Uma questão importante nos algoritmos relacionados com núcleo é a introdução de uma função que mede a complexidade da função $f \in \bar{\mathcal{F}}$. De forma geral, regularizar a norma de $f$ é útil para contornarmos problemas computacionais. Neste sentido, introduzimos o seguinte problema de otimização $$ \min_{f \in \bar{\mathcal{F}}} \left\{ C_E({\bf o}_n , f  ) + R(\parallel f \parallel) \right\}  ~ ~ ( \text{Equação 1}),$$ no qual $R: [0, \infty) \rightarrow \mathbb{R}$ é uma função não decrescente. Típica escolha para $R$ é dada por $R(a) = \lambda a^2$ com $\lambda$ uma constante positiva. O teorema seguinte nos garante que a solução ao problema de Minimização acima (Equação 1) pertence ao span do conjunto $\{\mathcal{K}(\cdot , x_1) , \cdots , \mathcal{K}( \cdot , x_n)  \}$. 

Teorema 1: Teorema da Representação

Suponha que existe solução ao problema de minimização apresentado na equação 1. Então, existe um vetor $(\alpha_1^\star, \cdots , \alpha_n^\star) \in \mathbb{R}^n$ tal que $$f^\star (\cdot)  = \sum_{i=1}^n \alpha_i^\star \mathcal{K}(\cdot , x_i) $$ é uma solução ótima ao problema de minimização apresentado na Equação 1.

Prova:  Seja $g^\star$ uma soluçao ao problema de minimização dado na equação 1. Como $g^\star$ pertence ao espaço de Hilbert  $\bar{\mathcal{F}}$, podemos escrever $g^\star$ na forma $$g^\star (\cdot)=  \sum_{i=1}^n \alpha_i^\star \mathcal{K}(\cdot , x_i)  + g (\cdot),$$ no qual $\langle g , \mathcal{K}(\cdot , x_i) \rangle = 0$ para todo $i=1, \cdots , n$. Seja $f^\star=g^\star - g$.  Obviamente, temos que $\parallel g^\star \parallel^2 = \parallel g \parallel^2 + \parallel f^\star \parallel^2$. Portanto, concluímos que $\parallel f^\star \parallel \leq \parallel g^\star \parallel $. Desde que $R$ é uma função não decrescente, obtemos que $R(\parallel f^\star \parallel) \leq R (\parallel g^\star \parallel)$. Além disso, para todo $i=1, \cdots , n$, temos que $$ \langle f^\star , \mathcal{K}(\cdot , x_i) \rangle  =   \langle g^\star - g , \mathcal{K}(\cdot , x_i) \rangle = \langle g^\star  , \mathcal{K}(\cdot , x_i) \rangle .$$ Desta forma, concluímos que $$C_E ({\bf o}_n , f^\star) = \frac{1}{n}  \sum_{i=1}^n \psi(-  \langle f^\star , \mathcal{K} (\cdot , x_i) \rangle (2y_i-1)) = \frac{1}{n}  \sum_{i=1}^n \psi(-  \langle g^\star , \mathcal{K} (\cdot , x_i) \rangle (2y_i-1)) = C_E ({\bf o}_n , g^\star) .$$ Com isso, concluímos que a função objetivo da equação 1 no ponto $f^\star$ não pode ser maior que a função objetivo no ponto $g^\star$ e portanto $f^\star$ também é uma solução ótima. Segue o teorema da representação.

A partir do teorema da representação, sabemos que $$\inf_{f \in \bar{\mathcal{F}}} \left\{ C_E({\bf o}_n , f  ) + R(\parallel f \parallel) \right\} = \inf_{f \in \mathcal{F}} \left\{ C_E({\bf o}_n , f  ) + R(\parallel f \parallel) \right\} .$$ Assim, podemos nos concentrar na classe $\mathcal{F}$ de funcionais lineares, nos quais $$L(\mathbb{P} , h_f) \leq C_E({\bf o}_n , f  ) + 2L_{\psi} \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{i=1}^n \sigma_if(x_i) +   3 B \sqrt{\frac{\ln(2/\delta)}{2n} }, \quad {\bf o}_n \in \hat{G},$$ no qual $\mathbb{P}(\hat{G}) > 1 - \delta$ com $0 < \delta < 1/2$ e $h_f = 1\!\!1_{ \{ f \geq 0 \}}$ com $f \in \mathcal{F}$. A partir da propriedade reprodutiva, aplicamos os mesmos argumentos do módulo Classe de preditores lineares para obtermos

$$ \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{i=1}^n \sigma_if(x_i) = \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{i=1}^n \sigma_i \langle f , \mathcal{K}(\cdot , x_i) \rangle  \leq \frac{M}{n} \mathbb{E}_{\mu^n}  \parallel   \sum_{i=1}^n \sigma_i  \mathcal{K}(\cdot , x_i) \parallel  =$$  $$  \frac{M}{n} \mathbb{E}_{\mu^n}  \left(  \langle   \sum_{i=1}^n \sigma_i  \mathcal{K}(\cdot , x_i) , \sum_{j=1}^n \sigma_j  \mathcal{K}(\cdot , x_j)  \rangle \right)^{1/2} =  \frac{M}{n} \sqrt{ \sum_{i=1}^n     \mathcal{K}(x_i , x_i) } , $$ no qual $\parallel \cdot \parallel$ denota a norma relacionada com o produto interno. $\langle \cdot , \cdot \rangle$. Como consequência da desigualdade de Kahane-Khinchine temos que $$ \frac{M}{\sqrt{2}n} \sqrt{ \sum_{i=1}^n     \mathcal{K}(x_i , x_i) } \leq \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{i=1}^n \sigma_if(x_i) \leq   \frac{M}{n} \sqrt{ \sum_{i=1}^n     \mathcal{K}(x_i , x_i) }.$$ Estas desigualdades são interessantes pois podem ser facilmente calculadas a partir dos dados. Considere $f_C : \mathbb{O}^n \rightarrow \mathcal{F} $ uma função obtida através da minimização da função custo $$ f_C \in arg \min_{f \in \mathcal{F}}  \left\{ C_E({\bf o}_n , f  ) + R(\parallel f \parallel) \right\}, ~ ~ (\text{Equação 2}), $$ e $A_C : \mathbb{O}^n \rightarrow \mathcal{H}_{\mathcal{F}}$ o correspondente algoritmo no qual $\mathcal{H}_{\mathcal{F}} = \{ h_f = 1\!\!1_{\{ f \geq 0 \}} : f \in \mathcal{F} \}$ .  A seguir, enunciamos o seguinte teorema. 

Teorema 2: 

Temos que  $$L(\mathbb{P} , A_C ({\bf o}_n)) \leq C_E({\bf o}_n , f_C ({\bf o}_n  ) + 2L_{\psi}  \frac{M}{n} \sqrt{ \sum_{i=1}^n     \mathcal{K}(x_i , x_i) } +   3 B \sqrt{\frac{\ln(2/\delta)}{2n} }, \quad {\bf o}_n \in \hat{G},$$ no qual $\mathbb{P}(\hat{G}) > 1 - \delta$ com $0 < \delta < 1/2$.

O problema de minimização proposto na equação 2 pode ser escrito na seguinte forma $$ \min_{ \{ (\alpha_1 , \cdots , \alpha_n) \in \mathbb{R}^n \}} \left\{ \frac{1}{n}  \sum_{i=1}^n \psi(-  \langle \sum_{j=1}^n \alpha_j \mathcal{K}(x_j , \cdot) , \mathcal{K} (\cdot , x_i) \rangle (2y_i-1)) + R \left( \sqrt{ \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j \mathcal{K} (x_i , x_j)}  \right) \right\} =$$ 

$$ \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 3}) .$$ 

Para resolver o problema de minimização proposto na equação 3, não precisamos acessar diretamente os elementos no "Feature Space". A única coisa que precisamos calcular são os produtos internos no Feature space, o que pode ser calculado através da função núcleo. Assim, para resolver a equação 3 precisamos conhecer a matrix Gram $G$ nos quais os elementos são dados por $G(i,j) = \mathcal{K} (x_i , x_j)$. Uma vez que aprendemos os coeficientes $(\alpha_1^\star, \cdots , \alpha_n^\star)$ com a equação 3, podemos calcular a previsão de uma nova entrada por $$ f^\star (x) = \sum_{i=1}^n \alpha_i^\star \mathcal{K}(x_i , x) \quad \text{e} \quad h_{f^\star} (x) = 1\!\!1_{ \{ f^\star(x) \geq 0 \}}, \quad x \in \chi .$$ 

Exemplo 1: Núcleo Polinomial

O núcleo polinomial de ordem $k$ é dado por  $$ \mathcal{K}(x  , x^\prime) := \left( 1 + \langle x , x^\prime \rangle \right)^k .$$  A seguir, vamos checar que $\mathcal{K}$ é realmente um núcleo. Para isto, vamos  mostrar que existe ma função $\phi$ no espaço domínio tal que $\mathcal{K}(x  , x^\prime) = \langle \phi(x) , \phi(x^\prime) \rangle$. Por simplicidade, denotamos $x_0 = x^\prime_0 =1$. Então, temos que $$\mathcal{K} (x , x^\prime) =  \left( 1 + \langle x , x^\prime \rangle \right) \cdots \left( 1 + \langle x , x^\prime \rangle \right) = \left( \sum_{j=0}^n x_j x_j^\prime \right) \cdots \left( \sum_{j=0}^n x_j x_j^\prime \right) =$$ $$ \sum_{J \in \{0,1,2 \cdots \}^k} \prod_{i=1}^k x_{J_i}  x_{J_i}^\prime = \sum_{J \in \{0,1,2 \cdots \}^k} \prod_{i=1}^k x_{J_i}  \prod_{i=1}^k x_{J_i}^\prime .$$ Com isso, definimos uma função $\phi: \mathbb{R} \rightarrow \mathbb{R}^{(n+1)^k}$ tal que para todo $J \in \{0,1, 2, \cdots n\}^k$ existe um elemento de $\phi(x)$ que é igual a $\prod_{i=1}^k x_{J_i}$. Desta forma, obtemos que $$  \mathcal{K}(x  , x^\prime) = \left( 1 + \langle x , x^\prime \rangle \right)^k = \langle \phi(x) , \phi(x^\prime) \rangle .$$

Exemplo 2: Núcleo Gaussiano

Inicialmente, suponha que o espaço domínio seja dado pela reta $\mathbb{R}$. Considere a função $$\phi(x) := \frac{x^n}{\sqrt{n !}} e^{- \frac{x^2}{2} } , \quad x \in \mathbb{R}. $$ Desta forma, tomamos $$\langle \phi(x) , \phi(x^\prime) \rangle = \sum_{n=1}^\infty  \frac{x^n}{\sqrt{n !}} e^{- \frac{x^2}{2} } \frac{(x^\prime)^n}{\sqrt{n !}} e^{- \frac{(x^\prime)^2}{2} } = e^{\frac{x^2 + (x^\prime)^2}{2}} \sum_{n=1}^\infty \left( \frac{(x x^\prime)^n}{n!} \right) = e^{-\frac{\parallel x - x^\prime \parallel }{2}} .$$  Aqui, o feature space tem dimensão infinita, enquanto que calcular o núcleo é bem simples. De forma geral, dado um escalar $\sigma > 0$, o núcleo Gaussiano é definido por $$ \mathcal{K}(x  , x^\prime) := e^{-\frac{\parallel x - x^\prime \parallel }{2 \sigma}}, \quad x , x^\prime \in \mathbb{R}^d.$$

 

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]