Est-ce que libsvm est précis?

Question

Avec les corrections de StompChicken (j'ai mal calculé le produit d'un point, pouah!) La réponse semble être oui. J'ai depuis testé le même problème en utilisant un noyau précalculé avec les mêmes résultats corrects. Si vous utilisez libsvm StompChickens, les calculs organisés sont très agréables.

Question d'origine: Je suis sur le point de commencer à utiliser des noyaux précalculés dans libSVM. J'avais remarqué Vlad's answer à une question et j'ai pensé qu'il serait sage de confirmer que libsvm a donné des réponses correctes. J'ai commencé avec des noyaux non pré-calculés, juste un noyau linéaire simple avec 2 classes et trois points de données dans un espace à 3 dimensions. J'ai utilisé les données

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

Le fichier modèle généré par un appel à svm-train -s 0 - t 0 contient

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 

Cependant, lorsque je calcule la solution à la main qui n'est pas ce que je reçois. Est-ce que quelqu'un sait si libsvm souffre d'erreurs ou est-ce que quelqu'un peut comparer les notes et voir si elles obtiennent la même chose que libsvm?

Les coefficients a1, a2, a3 retournés par libsvm sont devraient être les valeurs qui font

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

aussi grande que possible avec les restrictions qui a1 + a3 = a2 et chacun des a1, a2, a3 est nécessaire pour se situe entre 0 et 1 (la valeur par défaut de C).

Le fichier modèle ci-dessus indique la réponse est

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

Mais un juste doit remplacer a2 = a1 + a3 dans la grande formule ci-dessus et confirmer les deux dérivées partielles sont nuls pour voir si cette solution est correcte (car aucun de a1 , a2, a3 est 0 ou 1) mais ils ne sont pas nuls.

Est-ce que je fais quelque chose de mal, ou est-ce que libsvm donne de mauvais résultats? (J'espère que je vais faire quelque chose de mal.)

Answer 1

LibSVM est une bibliothèque très largement utilisée et je doute fortement que quelque chose soit radicalement faux avec le code. Cela dit, je pense que c'est génial qu'il y ait des gens assez paranoïaques pour vérifier la justesse - c'est bien!

La solution semble correcte selon le fonctionnement que je donne ci-dessous. Ce que je veux dire par là, c'est qu'il satisfait les KKT conditions (15.29). Il est également vrai que les dérivées partielles du dual disparaissent à la solution.

Voici mon travail ...

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