// // Support-Vector-Machine. // // Copyright 2005, Konstantin Tretyakov // // // Function svm //----------------------------------------------------------------- // Trains the svm classifier // Parameters: // K - the n x n kernel matrix // y - the vector of classifications of training instances (of size n x 1) // y(i) = 1 if instance i is positive, and // y(i) = -1 otherwise // C - regularization constant // // Return value: // alpha - The dual representation of the trained classifier. // b - Bias of the resulting classifier // // The linear classifier discriminant function is // f(x) = sign(sum(alpha K(x_i, x)) + b) // function [alpha, b] = svm(K, y, C) // Hessian of the dual Lagrangian H = K.*(y*y'); // Minimize the dual Lagrangian Ld(a)=0.5*a'*H*a - j'*a // Subject to: y'*a = 0, a >= 0 // First, fix the Hessian (because it may be ill-conditioned) Q = H + diag(rand(y)/100); // Now we'll call the "quapro" function that will do the optimization for us // We only need to prepare the parameters p = -ones(y); // Linear constrains on a are given as y'*a = [0] // Lower bounds for a are all 0 // Solve printf("Training classifier, please wait...\n"); [a, lagr, f] = quapro(Q, p, y', [0], zeros(y), C*ones(y), 1); printf("Done\n"); // Optimal weight vector alpha = (a.*y); // Optimal bias // We need to find a support vector x(k) (i.e. k, for which a(k) <> 0) // we'll find all the support vectors now sv = find(abs(a) > 0.001); nonsv = find(abs(a) <= 0.001); // k is the index of the first support vector k = sv(1); // Calculate bias b = 1/y(k) - K(k,:)*alpha;