Por que se preocupar com o problema duplo ao instalar o SVM?

50

Dado os pontos de dados e etiquetas y 1 , ... , y n{ - 1 , 1 } , a margem de difícil problema SVM primal éx1,,xnRdy1,,yn{1,1}

s.t.

minimizew,w012wTw
s.t.i:yi(wTxi+w0)1

que é um programa quadrático com variáveis a serem otimizadas para ei restrições. O duplod+1i

s.t.

maximizeαi=1nαi12i=1nj=1nyiyjαiαjxiTxj
é um programa quadrático com n + 1 variáveis ​​a serem otimizadasen en desigualdade e n restrições de igualdade.
s.t.i:αi0i=1nyiαi=0
n+1nn

Ao implementar um SVM de margem rígida, por que eu resolveria o problema duplo em vez do problema principal? O problema principal parece mais "intuitivo" para mim, e não preciso me preocupar com a diferença de dualidade, a condição de Kuhn-Tucker etc.

Não faria sentido para mim para resolver o duplo problema se , mas eu suspeito que há melhores razões. É esse o caso?dn

blubb
fonte
26
Resposta curta é kernels. A resposta longa é keeerneeels (-;
A coisa mais importante do problema duplo é introduzir o truque do kernel, com o objetivo de mapear os dados originais no espaço com maior dimensão.
precisa saber é o seguinte

Respostas:

40

Com base nas notas de aula mencionadas na resposta de @ user765195 (obrigado!), Os motivos mais aparentes parecem ser:

wαixwTxd

αiαi=0x

wTx+w0=(i=1nαiyixi)Tx+w0=i=1nαiyixi,x+w0

Este termo é calculado com muita eficiência se houver apenas alguns vetores de suporte. Além disso, como agora temos um produto escalar que envolve apenas vetores de dados , podemos aplicar o truque do kernel .

blubb
fonte
6
Espera espera. Digamos que você tenha dois vetores de suporte x1 e x2. Você não pode ter menos de dois, certo? Você está dizendo que a computação <x1, x> e <x2, x> é mais rápida que <w, x>?
27312 Leo
11
@ Leo: Note que eu uso <x1, x>e wTx. O primeiro é usado como um símbolo para uma avaliação do kernel K (x1, x), que projeta x1 e x em um espaço dimensional muito alto e calcula implicitamente o produto escalar dos valores projetados. O último é o produto escalar o normal, assim we xtêm de ser projectada de forma explícita, e, em seguida, o produto escalar é calculada explicitamente. Dependendo da escolha do kernel, um único cálculo explícito pode exigir muito mais computação do que muitas avaliações do kernel.
Blubb
11
ααα
2
"Além disso, como agora temos um produto escalar que envolve apenas vetores de dados, podemos aplicar o truque do kernel". - Isso também é verdade na formulação primária.
Firebug
2
Se as pessoas quiserem mais detalhes sobre o comentário de @Firebug ... confira as equações 10-12 de lib.kobe-u.ac.jp/repository/90001050.pdf (que é uma versão irrestrita do primal).
MrDrFenner
13

Leia o segundo parágrafo na página 13 e a discussão que se segue nestas notas:

http://cs229.stanford.edu/notes/cs229-notes3.pdf

user765195
fonte
17
Essa é uma ótima referência e responde claramente à pergunta. Acho que sua resposta será melhor apreciada se você puder resumir a resposta aqui: isso faz com que esse tópico se mantenha por si só.
whuber
3

Aqui está uma razão pela qual a formulação dupla é atraente do ponto de vista da otimização numérica. Você pode encontrar os detalhes no seguinte documento :

Hsieh, C.-J., Chang, K.-W., Lin, C.-J., Keerthi, SS, e Sundararajan, S., “Um método de descida de coordenadas duplas para SVM linear em larga escala”, Proceedings of the 25ª Conferência Internacional sobre Aprendizado de Máquina, Helsinque, 2008.

A formulação dupla envolve uma única restrição de igualdade afim e n restrições vinculadas.

1. A restrição de igualdade afim pode ser "eliminada" da formulação dupla.

Isso pode ser feito simplesmente observando seus dados em R ^ (d + 1) através da incorporação de R ^ d em R ^ (d + 1), resultando na adição de uma única coordenada "1" a cada ponto de dados, ou seja, R ^ D ----> R ^ (d + 1): (a1, ..., ad) | ---> (a1, ..., ad, 1).

Fazer isso para todos os pontos do conjunto de treinamento redefine o problema de separabilidade linear em R ^ (d + 1) e elimina o termo constante w0 do seu classificador, o que, por sua vez, elimina a restrição de igualdade afim do dual.

2. No ponto 1, o dual pode ser facilmente convertido como um problema de otimização quadrática convexa cujas restrições são apenas restrições vinculadas.

3. O problema duplo agora pode ser resolvido com eficiência, ou seja, por meio de um algoritmo de descida de coordenadas duplas que produz uma solução ótima em epsilon em O (log (1 / epsilon)).

Isso é feito observando que a fixação de todos os alfas, exceto um, gera uma solução de forma fechada. Você pode então percorrer todos os alfas um por um (por exemplo, escolhendo um aleatoriamente, corrigindo todos os outros alfas, calculando a solução de formulário fechado). Pode-se mostrar que você obterá uma solução quase ideal "rapidamente" (consulte o Teorema 1 no documento acima mencionado).

Existem muitas outras razões pelas quais o problema duplo é atraente do ponto de vista da otimização, alguns dos quais exploram o fato de que ele tem apenas uma restrição de igualdade afim (as restrições restantes são todas restrições vinculadas) enquanto outros exploram a observação de que na solução do problema duplo "geralmente a maioria dos alfas" é zero (alfas diferentes de zero correspondentes aos vetores de suporte).

Você pode obter uma boa visão geral das considerações de otimização numérica para SVMs na apresentação de Stephen Wright no Computational Learning Workshop (2009).

PS: Eu sou novo aqui. Desculpas por não ser bom em usar notação matemática neste site.

aTn
fonte
11
As informações sobre como usar a digitação matemática estão aqui: math.meta.stackexchange.com/questions/5020/…
Reinstala Monica
-5

Na minha opinião, nas notas da aula de Andrew ng, foi claramente mencionado que o problema principal de 1 / || w || é um problema não convexo. O dual é um problema convexo e é sempre fácil encontrar o melhor de uma função convexa.

Avni Kant Rai
fonte
11
O SVM primário, como indicado acima, é convexo.
Dougal