%DLPC LP-classifier on dissimilarity (proximity) data % % [W1,W2,W3] = DLPC(D,BIAS,TYPE,PARAM) % % INPUT % D Dissimilarity (proximity) dataset % BIAS YES or NO (optional; default: 1 (YES)) % TYPE Type of a classifier % 'SIMPLE' - the most simple formulation; no sparse solution; PARAM = []; % 'STANDARD' - minimization of the training misclassification errors; % no sparse solution; PARAM = []; % 'C-SPARSE' - sparse solution; a formulation similar to the LP_1 SVM; % PARAM is a tradeoff parameter, similar as in the traditional % SVM; (optional; DEFAULT: 1). % 'MU-SPARSE' - sparse solution; a formulation similar to the LP_1 SVM, % based on the paper of Graepel, Herbrich, Smola etc % 'Classification on proximity data with LP-machines'. % PARAM is a tradeoff parameter, usually PARAM = 0.05 or 0.1. % It is an upper bound on the misclassfied training objects. % So, for well separable problems, PARAM = 0.01 or PARAM = 0.02. % (optional; DEFAULT: the LOO 1-NN error * 1.3). % PARAM Parameter connected to the TYPE, as above % % OUTPUT % W1 LP-Classifier in the complete dissimilarity space % W2 LP-Classifier in a reduced dissimilarity space % W3 Object selection mapping; the indices of support objects are in +W3. % % DEFAULTS % BIAS = 1 % TYPE = 'STANDARD' % PARAM = [] % % DESCRIPTION % Classification problem on a N x M dissimilarity dataset D with LP-machines. % D should be described by both label and feature lists. If D is a square, % symmetric matrix, then the feature list should be the same as the label list. % % Assume a 2-class problem. Let DLPC select J support objects. Then: % W1 is an M x 2 classifier in the original dissimilarity space, W2 is an J x 2 % classifier in the dissimilarity space defined by the J support objects % and W3 is an M x R feature selection such that W1 = W3 * W2. % Note that the indices of the support objects can be retrieved by +W3. % % A linear classifier is built on D: % % f(D(x,*)) = diag(Y) * D(x,*) * W + W0, % % where Y are labels (+/- 1) and W are the weights. If BIAS is 1, then W0 is also % sought, otherwise it equals 0, hence the hyperplane is forced to go through the origin. % % For C-class problems, C classifiers are trained, one against all others. % In such a case, only W1 is returned and W3 in now NOT a feature selection, % but directly the indices of the support objects. % % Let [n,k] = size(D). Assume a two-class problem. % Any multi-class problem is converted one-against-all to two-class problems. % Y are the labels (converted +/-1) % D_Y = diag(Y_r) * D * diag(Y_c), % where Y_r are the labels for rows of D and % Y_c are the labels for columns. % alpha is the sought solution. % % Internal - the optimization schema (A,b,f) refer to the constraints in % the standard Matlab LINPROG procedure. % % 'simple': % min 0^T * alpha(1:k) (= 0) % s.t. [D_Y Y] * [alpha(1:k) alpha_0)] >= 1 % % A = [D_Y Y] is n x (k+1) % b = 1(n,1) % f = 0(k+1,1) % % % 'standard': % min p^T * beta(1:n), p = 1/n_i for the class_i % s.t. [D_Y Y] * [alpha(1:k) alpha_0] + beta(1:n) >= 1, % beta >= 0 % % A = [D_Y Y eye(n)] % b = 1(n,1) % f = [0(k+1,1) p]^T % % % 'c-sparse': % min sum(alpha(1:k)) + sum (alpha2(1:k)) + C*sum(ksi) % s.t. [D_Y Y] * [alpha(1:k)-alpha2(1:k) alpha_0] + ksi(1:n) >= 1, % ksi >= 0 % alpha, alpha2 >= 0 % % A = [D_Y -D_Y Y eye(n,n)] % b = 1(n,1) % f = [0(k+1,1)]^T % % % 'mu-sparse': % min sum(ksi)/n - mu*g % s.t. [D_Y -D_Y Y] * [alpha(1:k)-alpha2(1:k) alpha_0] + ksi(1:n) >= g, % sum(alpha) + sum(alpha2) = 1 % alpha, alpha2 >= 0 % ksi >= 0 % % A = [D_Y -D_Y Y eye(n,n)] % b = 1(n,1) % f = [0(2k+1,1)] % % Elzbieta Pekalska, Robert P.W. Duin, e.pekalska@tudelft.nl % Faculty of Electrical Engineering, Mathematics and Computer Science, % Delft University of Technology, The Netherlands. function [W1,W2,W3] = dlpc (d,is_w0,type,par,usematlab,prec) if nargin < 6, prec = 1e-7; end if nargin < 5, usematlab = 0; end if nargin < 3 | isempty(type), type = 'standard'; end if nargin < 4 par = []; end if nargin < 2 | isempty(is_w0), is_w0 = 1; end if nargin < 1 | isempty(d) W1 = mapping(mfilename,{is_w0,type,par,usematlab}); W1 = setname(W1,'DLPC'); W2 = []; W3 = []; return end if ~isdataset(d), error('The first parameter should be a dataset.') end if ~isnumeric(is_w0) | (is_w0 ~= 0 & is_w0 ~= 1), error('The second parameter should be 0 or 1.'); end if isempty(par), switch upper(type) case 'MU-SPARSE', par = max(0.01,1.3*testkd(d,1,'loo')); % upperbound error: 1.3 * loo 1-nn error case 'C-SPARSE', par = 1; case {'SIMPLE','STANDARD'}, par = []; otherwise error('Wrong type.') end end lab = getnlab(d); lablist = getlablist(d); featlab = getfeatlab(d); [m,k,C] = getsize(d); [nl, fe, fl] = renumlab(lablist,featlab); if max(fe) > size(lablist,1) error('Feature labels of the dataset do not match with class labels.') end z = (is_w0 > 0); % is bias used or not? % This is the status of the optimization procedure. % For GLPK, this is the exit code; see GLPKMEX for details. % For Matlab LINPROG, if negative then no solution is found. status = 1; % If more than 2 classes, do one against all others. if C > 2, % W1 = mclassc(d,mapping(mfilename,{is_w0,type,par,usematlab})); W1 = []; W2 = []; W3 = []; N = []; for i=1:C mlab = 2 - (lab == i); mfe = 2 - (fe == i); dd = setlabels(d,mlab); dd = setfeatlab(dd,mfe); if ~isempty(d.prior) dd = setprior(dd,[d.prior(i),1-d.prior(i)]'); end [v1,v2,v3]= dlpc(dd,is_w0,type,par,usematlab); j = +v3; if isempty(v1), W1 = []; W2 = []; W3 = []; prwarning(1,'No solution found.'); return; end W1 = [W1,setlabels(v1(:,1),lablist(i,:))]; W2 = [W2;setlabels(v2(:,1),lablist(i,:))]; W3(j) = ones(length(j),1); N = [N j]; end [N1,N2,N3] = unique(N); W3 = featsel(k,N1); %disp(size(W3,2)) W2 = featsel(length(N1),N3)*W2; return else Y1 = 3 - 2 * lab; % labels +/-1 Y = 3 - 2 * fe; % featlabels +/-1 alpha(1:k+1,1) = 0; switch type case 'simple', f = zeros(k+z,1); b = -ones(m,1); if is_w0, A = -[(Y1*Y').* +d Y1]; else A = -[(Y1*Y').* +d]; end % if (exist('glpkmex')>0) & (usematlab==0) % smin = 1; % solve minimum % ctype = char(ones(m,1)*abs('U')); % Sign of inequalities % vartype = char(ones(k+z,1)*abs('C')); % Continous variables % lpsolver = 2; % Interior Point Method % lpsolver = 1; % Revised Simlex Method % params.msglev = 0; % no outputs % [al,fval,status] = glpkmex(smin,f,A,b,ctype,[],[],vartype,params,lpsolver); % else % [al,fval,status] = linprog(f,A,b); % end [al,fval,status] = linprog(f,A,b); alpha(1:k+z) = al; case 'standard', L = ones(k,1); I = find(Y==1); if ~isempty(I) L(I) = L(I)/length(I); end J = find(Y==-1); if ~isempty(J) L(J) = L(J)/length(J); end f = [zeros(k+z,1); L]; lb = [-Inf .*ones(k+z,1); zeros(k,1)]; ub = Inf .* ones(2*k+z,1); b = -ones(m,1); if is_w0, A = -[(Y1*Y').* +d Y1 eye(m,k)]; else A = -[(Y1*Y').* +d eye(m,k)]; end % if (exist('glpkmex')>0) & (usematlab==0) % smin = 1; % solve minimum % ctype = char(ones(m,1)*abs('U')); % Sign of inequalities % vartype = char(ones(2*k+z,1)*abs('C')); % Continous variables %% lpsolver = 2; % Interior Point Method % lpsolver = 1; % Revised Simlex Method % params.msglev = 0; % no outputs % [sss,hostname] = unix('hostname'); % hostname = hostname(1:end-1); % if strcmp(hostname,'saturnus') | strcmp(hostname,'polaris') | strcmp(hostname,'neptunus') % [al,fval,status] = glpkmex_redhat(smin,f,A,b,ctype,lb,ub,vartype,params,lpsolver); % else % [al,fval,status] = glpkmex(smin,f,A,b,ctype,lb,ub,vartype,params,lpsolver); % end % else % [al,fval,ststus] = linprog(f,A,b,[],[],lb,ub); % end [al,fval,ststus] = linprog(f,A,b,[],[],lb,ub); alpha(1:k+z) = al(1:k+z); case 'c-sparse', L = ones(k,1); ub = Inf .* ones(3*k+z,1); lb = [zeros(2*k,1); -Inf.*ones(z,1); zeros(k,1)]; b = -ones(m,1); dd = (Y1*Y').* +d; if is_w0, f = [ones(2*k,1); 0; par*L]; A = -[dd -dd Y1 eye(m,k)]; else f = [ones(2*k,1); par*L]; A = -[dd -dd eye(m,k)]; end if (exist('glpkmex')>0) & (usematlab==0) smin = 1; % solve minimum ctype = char([ones(m,1)*abs('U')]); % Sign of inequalities vartype = char(ones(3*k+z,1)*abs('C')) ; % Continuous variables % lpsolver = 1; % Revised Simlex Method lpsolver = 2; % Interior Point Method params.msglev = 0; % no outputs params.itlim = 400; % iteration limit [sss,hostname] = unix('hostname'); hostname = hostname(1:end-1); if strcmp(hostname,'saturnus') | strcmp(hostname,'polaris') | strcmp(hostname,'neptunus') [al,fval,status] = glpkmex_redhat(smin,f,A,b,ctype,lb,ub,vartype,params,lpsolver); else [al,fval,status] = glpkmex(smin,f,A,b,ctype,lb,ub,vartype,params,lpsolver); end else [al,fval,status] = linprog (f,A,b,[],[],lb,ub); end alpha(1:k) = al(1:k) - al(k+1:2*k); if is_w0, alpha(k+1) = al(2*k+1); end case 'mu-sparse', L = ones(k,1)/k; f = [zeros(2*k+z,1); L; -par]; ub = Inf .* ones(3*k+1+z,1); lb = [zeros(2*k,1); -Inf.*ones(z,1); zeros(k+1,1)]; Aeq = [ones(2*k,1); zeros(k+1+z,1)]'; beq = 1; b = zeros(m,1); dd = (Y1*Y').* +d; if is_w0, A = -[dd -dd Y1 eye(m,k) -ones(m,1)]; else A = -[dd -dd eye(m,k) -ones(m,1)]; end if (exist('glpkmex')>0) & (usematlab==0) smin = 1; % solve minimum ctype = char([ones(m,1)*abs('U'); 'S']); % Sign of inequalities vartype = char(ones(3*k+1+z,1)*abs('C')); % Continous variables % lpsolver = 1; % Revised Simlex Method lpsolver = 2; % Interior Point Method params.msglev = 0; % no outputs, but doesn't seem to work params.itlim = 400; % iteration limit [sss,hostname] = unix('hostname'); hostname = hostname(1:end-1); if strcmp(hostname,'saturnus') | strcmp(hostname,'polaris') | strcmp(hostname,'neptunus') [al,fval,status] = glpkmex_redhat(smin,f,[A; Aeq],[b; beq],ctype,lb,ub,vartype,params,lpsolver); else [al,fval,status] = glpkmex(smin,f,[A; Aeq],[b; beq],ctype,lb,ub,vartype,params,lpsolver); end else [al,fval,status] = linprog(f,A,b,Aeq,beq,lb,ub); end alpha(1:k) = al(1:k) - al(k+1:2*k); if is_w0, alpha(k+1) = al(2*k+1); end otherwise error ('Wrong type.'); end end if (status <= 0) | (status > 181 | status == 150), prwarning(1,'Fisher classifier is trained.'); W1 = fisherc(d); W2 = W1; W3 = featsel(k,[1:k]); return; end % Choose support objects ss = sum(abs(alpha(1:k))); J = find(abs(alpha(1:k)) > ss*prec); if ~isempty(J), W3 = featsel(k,J); w = [Y; 1] .* alpha(1:k+1); W2 = affine(w(J),w(k+1),d(:,J),lablist,k,2); W2 = cnormc(W2,d(:,J)); W1 = W3*W2; W1 = setname(W1,'DLPC'); W2 = setname(W2,'DLPC'); else prwarning(1,'No support objects found. Fisher classifier is trained.'); W1 = fisherc(d); W2 = W1; W3 = featsel(k,[1:k]); return; end % disp(size(W3,2)) return;