// // Soft Maximal Margin Linear Classifier // // Copyright 2005, Konstantin Tretyakov // // // Function soft_maximal_margin_classifier //----------------------------------------------------------------- // Trains the soft maximal margin linear classifier. // Parameters: // X - the n x m data matrix containing training instances as its rows // 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: // w - The weight vector of the resulting classifier // b - Bias of the resulting classifier // // The linear classifier discriminant function is // f(x) = sign(w'*x + b) // function [w, b] = soft_maximal_margin_classifier(X, y, C) // Hessian of the dual Lagrangian H = (X*X').*(y*y'); // Minimize the dual Lagrangian Ld(a)=0.5*a'*H*a - j'*a // Subject to: y'*a = 0, C >= 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 w = X'*(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) - X(k, :)*w;