libsvm è accurato?

Question

Con le correzioni di StompChicken (ho calcolato male un prodotto punto, ugh!) La risposta sembra essere sì. Da allora ho testato lo stesso problema usando un kernel precompilato con gli stessi risultati corretti. Se stai usando libsvm StompChickens chiaro, i calcoli organizzati sono un ottimo controllo.

Domanda originale: Sto per iniziare a utilizzare i kernel precomputed in libSVM. Avevo notato Vlad's answer a una domanda e ho pensato che sarebbe saggio confermare che libsvm ha dato risposte corrette. Ho iniziato con i kernel non precompilati, solo un semplice kernel lineare con 2 classi e tre punti dati nello spazio tridimensionale. Ho usato i dati

1 1:3 2:1 3:0 
2 1:3 2:3 3:1 
1 1:7 3:9 

Il file modello generato da una chiamata al svm-train -s 0 - t 0 contiene

svm_type c_svc 
kernel_type linear 
nr_class 2 
total_sv 3 
rho -1.53951 
label 1 2 
nr_sv 2 1 
SV 
0.4126650675419768 1:3 2:1 3:0 
0.03174528241667363 1:7 3:9 
-0.4444103499586504 1:3 2:3 3:1 

Tuttavia quando computo la soluzione a mano che non è quello che mi capita. Qualcuno sa se libsvm soffre di errori o qualcuno può confrontare le note e vedere se ottengono la stessa cosa che fa libsvm?

I coefficienti a1, a2, a3 restituiti da libsvm sono dovrebbero essere i valori che rendono

a1 + a2 + a3 - 5*a1*a1 + 12*a1*a2 - 21*a1*a3 - 19*a2*a2/2 + 21*a2*a3 - 65*a3*a3 

più grande possibile con le restrizioni che a1 + a3 = a2 e ciascuno di a1, a2, a3 è tenuto a si trovano tra 0 e 1 (il valore predefinito di C).

Il file modello di cui sopra dice che la risposta è

a1 = .412665... 
a2 = .444410... 
a3 = .031745... 

Ma uno deve solo sostituire a2 = a1 + a3 nella grande formula di cui sopra e confermare entrambe le derivate parziali sono pari a zero per vedere se questa soluzione è corretta (poiché nessuno di a1 , a2, a3 è 0 o 1) ma non sono zero.

Sto facendo qualcosa di sbagliato, o libsvm sta dando risultati cattivi? (Spero di fare qualcosa di sbagliato.)

Answer 1

LibSVM è una libreria molto diffusa e dubito fortemente che qualcosa sia drasticamente sbagliato nel codice. Detto questo, penso che sia fantastico che ci siano persone abbastanza paranoiche da controllarlo per correttezza - ben fatto!

La soluzione sembra corretta in base al funzionamento che riporto di seguito. Ciò che intendo è che soddisfa lo KKT conditions (15,29). È anche vero che i derivati ​​parziali del doppio svaniscono alla soluzione.

Ecco il mio lavoro ...

x1 = (3,1,0) x2 = (3,3,1) x3 = (7,0,9) 
y1 = -1  y2 = 1  y3 = -1 

K = [10 12 21] 
    [12 19 30] 
    [21 30 130] 

L_dual = a1 + a2 + a3 -5a1^2 + 12a1a2 - 21a1a3 - (19/2)a2^2 + 30a2a3 - 65a3^2) 

a1 = 0.412 a2 = 0.4444 a3 = 0.0317 

Checking KKT: 
y1.f(x1) = y1 * (y1*a1*K(x1,x1) + y2*a2*K(x1,x2) + y3*a3*k(x1,x3) - rho) 
     = rho + 10*a1 + 21*a3 - 12*a2 
     ~= 1 
(Similar for the x2 and x3) 

Substituting a2 = a1 + a3 into L_dual: 
L_dual = 2a1 + 2a3 - 2.5a1^2 + 2a1a3 - 44.5a3^2 
dL/da1 = 2 - 5a1 + 2a3 = 0 
dL/da3 = 2 + 2a1 - 89a3 = 0