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

8

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(xi,xj)=exp(||xixj||22σ2)
w=iSVhiyixi
b=1|SV|iSV(yij=1N(hjyjxjTxi))
xyyi{1,1}h são os coeficientes lagrangianos e é um conjunto de vetores de suporte. Depois disso, posso usar e sozinho para classificar facilmente: .SVwbcx=sign(wTx+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)=ϕ(x)ϕ(y)

Jan Hadáček
fonte
Não é uma resposta completa, mas eu tinha esses slides em uni: patterns.enm.bris.ac.uk/files/lecture10-2010.pdf
tristan

Respostas:

19

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 Φ : XF X F X F F X x i Φ ( x i ) x T y Φ ( x ) , Φ ( y ) F w *XΦ:XFXFXFFXxiΦ(xi)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,xTyΦ(x),Φ(y)Fw

w=iSVhiyiΦ(xi)

e, portanto,

w,Φ(x)=iSVhiyiΦ(xi),Φ(x)

Da mesma forma,

b=1|SV|iSV(yij=1N(hjyjΦ(xj),Φ(xi)))

e sua regra de classificação se parece com: .cx=sign(w,Φ(x)+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 ) kk:X×XRk(xi,xj)=Φ(xi),Φ(xj)k(xi,xj)k

Portanto, e parecem, b *w * , Φ ( x ) = Σ i S V H i y i k ( x i , x ) b * = 1wb

w,Φ(x)=iSVhiyik(xi,x)
b=1|SV|iSV(yij=1N(hjyjk(xj,xi)))

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 wwxw

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 )hiFXΦkΦ

maxihii,jyiyjhihjk(xi,xj)subject to : iyihi=0,hi0
TenaliRaman
fonte
@ JanHadáček De nada! É bom saber que a minha resposta é compreensível, eu estava preocupado que poderia ser muito condensado :-)
TenaliRaman
Explicação muito boa
London guy