Classificação SVM não linear com kernel RBF

Estou implementando um classificador SVM não linear com o kernel RBF. Disseram-me que a única diferença em relação a um SVM normal era que eu tinha que simplesmente substituir o produto do ponto por uma função do kernel: Sei como funciona um SVM linear normal, ou seja, depois de resolver o problema de otimização quadrática (tarefa dupla), calculo o hiperplano de divisão ideal como e o deslocamento do hiperplano respectivamente, onde é uma lista dos meus vetores de treinamento, y são seus respectivos rótulos ( y_i \ in \ {- 1,1 \} ),

$$K(x_i,x_j)=\exp\left(-\frac{||x_i-x_j||^2}{2\sigma^2}\right)$$ $$w^*=\sum_{i \in SV} h_i y_i x_i$$ $$b^*=\frac{1}{|SV|}\sum_{i \in SV}\left(y_i - \sum_{j=1}^N\left(h_j y_j x_j^T x_i\right)\right)$$ $x$$y$$y_i \in \{-1,1\}$$h$ são os coeficientes lagrangianos e é um conjunto de vetores de suporte. Depois disso, posso usar e sozinho para classificar facilmente: .$SV$$w^*$$b^*$$c_x=\text{sign}(w^Tx+b)$

No entanto, acho que não posso fazer uma coisa dessas com um kernel RBF. Encontrei alguns materiais sugerindo que . Isso facilitaria as coisas. No entanto, acho que essa decomposição não existe para esse kernel e não é mencionada em nenhum lugar. A situação é necessária para que todos os vetores de suporte sejam necessários para a classificação? Em caso afirmativo, como classifico nesse caso?$K(x,y)=\phi(x)\phi(y)$

Deixe que represente seu espaço de entrada, ou seja, o espaço onde seus pontos de dados residem. Considere uma função , de forma que ela aponte um ponto do espaço de entrada e mapeie-a para um ponto em . Agora, digamos que mapeamos todos os seus pontos de dados de para este novo espaço . Agora, se você tentar resolver o svm linear normal neste novo espaço vez de , você notará que todos os trabalhos anteriores simplesmente parecem iguais, exceto que todos os pontos são representados como Φ : X → F X F X F F X x i Φ ( x i ) x T y ⟨ Φ ( x ) , Φ ( y ) ⟩ F w $\mathcal{X}$$\Phi:\mathcal{X} \rightarrow \mathcal{F}$$\mathcal{X}$$\mathcal{F}$$\mathcal{X}$$\mathcal{F}$$\mathcal{F}$$\mathcal{X}$$x_i$$\Phi(x_i)$e, em vez de usar (produto em pontos), que é o produto interno natural para o espaço euclidiano, substituímos por que representa o produto interno natural no novo espaço . Então, no final, seu ficaria assim,$x^Ty$$\langle \Phi(x), \Phi(y) \rangle$$\mathcal{F}$$w^*$

$$w^*=\sum_{i \in SV} h_i y_i \Phi(x_i)$$

e, portanto,

$$\langle w^*, \Phi(x) \rangle = \sum_{i \in SV} h_i y_i \langle \Phi(x_i), \Phi(x) \rangle$$

Da mesma forma,

$$b^*=\frac{1}{|SV|}\sum_{i \in SV}\left(y_i - \sum_{j=1}^N\left(h_j y_j \langle \Phi(x_j), \Phi(x_i)\rangle\right)\right)$$

e sua regra de classificação se parece com: .$c_x=\text{sign}(\langle w, \Phi(x) \rangle+b)$

Até aí tudo bem, não há nada de novo, pois simplesmente aplicamos o SVM linear normal a apenas um espaço diferente. No entanto, a parte mágica é esta -

Digamos que exista uma função tal que . Em seguida, podemos substituir todos os produtos de pontos acima por . Tal é chamado de função do kernel. k ( x i , x j ) = ⟨ Φ ( x i ) , Φ ( x j ) ⟩ k ( x i , x j ) $k:\mathcal{X}\times\mathcal{X}\rightarrow \mathbb{R}$$k(x_i, x_j) = \langle \Phi(x_i), \Phi(x_j) \rangle$$k(x_i, x_j)$$k$

Portanto, e parecem, b * ⟨ w * , Φ ( x ) ⟩ = Σ i ∈ S V H i y i k ( x i , x ) b * = $w^*$$b^*$

$$\langle w^*, \Phi(x) \rangle = \sum_{i \in SV} h_i y_i k(x_i, x)$$ $$b^*=\frac{1}{|SV|}\sum_{i \in SV}\left(y_i - \sum_{j=1}^N\left(h_j y_j k(x_j, x_i)\right)\right)$$

Para quais funções do kernel a substituição acima é válida? Bem, essa é uma pergunta um pouco envolvente e você pode querer usar material de leitura adequado para entender essas implicações. No entanto, apenas acrescentarei que o acima é válido para o RBF Kernel.

Para responder sua pergunta: "A situação é necessária para que todos os vetores de suporte sejam necessários para a classificação?" Sim. Como você pode notar acima, calculamos o produto interno de com vez de calcular explicitamente. Isso exige que retenhamos todos os vetores de suporte para classificação.x $w$$x$$w$

Nota: Os na seção final aqui são solução para o dual do SVM no espaço e não . Isso significa que precisamos conhecer a função explicitamente? Felizmente não. Se você observar o objetivo duplo, ele consiste apenas em produto interno e, como temos que permite calcular diretamente o produto interno, não precisamos conhecer explicitamente. O objetivo duplo simplesmente se parece com: F X Φ k Φ max ∑ i h i - ∑ i , j y i y j h i h j k ( x i , x j$h_i$$\mathcal{F}$$\mathcal{X}$$\Phi$$k$$\Phi$

$$\max \sum_i h_i - \sum_{i,j} y_i y_j h_i h_j k(x_i, x_j) \\ \text{subject to : } \sum_i y_i h_i = 0, h_i \geq 0$$