rankncg_linear_train.m

RankNGG 算法实现. 含有dll文件。源码为matlab

function [w,time_taken]=RankNCG_linear_train(data,CG_tolerance,lambda,method,epsil,verbose,plot_enable)
% Trains a linear ranking function using nonlinear conjugate gradient.
%
% The exct version scales as $$O(N^2)$$.
%
% The approximate version scales as $$O(N)$$.
%
% CG_tolerance and lambda can be chosen by cross-validation.
%
%% Input
%
% * data ... structure containing the data regarding the ranking task at hand [See convert_data_to_ranking_format.m]
% * CG_tolerance ... tolerance for the conjugate gradient procedure [Set to 1e-3 to 1e-6]
% * lambda ... regularization parameter.
% * method ... if 'direct' uses the exact gradient, if 'approx' uses the approximate gradient 
% * epsil ... the accuracy parameter for the fast approximate computation of erfc functions  [Set to 1e-3 to 1e-6]
% * verbose ... if 1 comments are displayed. Set to 0 when timing the program
% * plot_enable ... if 1 plots the learning curve
%
%  Basic information---
%
% * data.N ... number of data points
% * data.d ... data dimensionality
% * data.S ... number of classes
% * data.m ... number of inputs in each class 
%
%  Actual data---
%
% * data.labels ... vector of class labels
% * data.X ... cell array where each cell contains the data belonging to one class
% * data.index ... index of the data belonging to one class
% * data.X_raw ... d x N original data matrix
% * data.y_raw ... 1 x N vector of the class labels
%
%  Preference graph---
% 
% * data.graph_type ... graph type
% * data.C ... number of edges in the preference graph
% * data.G ... data.C x 2 matrix encoding the preference relations. The class in the second column is preferred over that in the first column.
% * data.num_of_pairs ... total number of pairwise preference realtions
%
%% Ouput
%
% *  w ... d x 1 learnt weight vector
% *  time_taken ... in seconds
%
%% Signature
%
% Author: Vikas Chandrakant Raykar
% E-Mail: [e-mail]
% Date: September 27, 2006
%
%% See also
%
% convert_data_to_ranking_format,  non_linear_conjugate_gradient
%

to=clock;
 
%--------------------------------------------------------------------------
% Initialize the model parameters
%--------------------------------------------------------------------------

if verbose==1
    disp('Initializing the model parameters');
end

start_w=generate_uniform_vector(-1/sqrt(data.d),1/sqrt(data.d),data.d,1);

%--------------------------------------------------------------------------
% NCG parameters
%--------------------------------------------------------------------------


NCG_parameters.epsilon_CG=CG_tolerance;%---CG error tolerance
NCG_parameters.epsilon_secant=1e-3;%---secant method error tolerance
NCG_parameters.iter_max_CG=200;%---maximum number of CG iterations 
NCG_parameters.iter_max_secant=30;%---maximum number of secant method iterations
NCG_parameters.sigma_0=1e-12;%---secant method step parameter


%--------------------------------------------------------------------------
% Choose the gradient method
%--------------------------------------------------------------------------

if strcmp(method,'direct')==1
    if verbose==1
        fprintf(1,'Nonlinear Conjugate gradient Direct: lambda=%f CG_tolerance=%e\n',lambda,NCG_parameters.epsilon_CG);
    end
    data.lambda=lambda;
    gradient_function=@gradient_vector_linear_direct;
end

if strcmp(method,'approx')==1
    if verbose==1
        fprintf(1,'Nonlinear Conjugate gradient Approximate: lambda=%f CG_tolerance=%e epsilon=%e\n',lambda,NCG_parameters.epsilon_CG,epsil);
    end
    data.lambda=lambda;
    data.epsil=epsil;
    data.delta_1=precompute_delta_1(data);
    [data.rx,data.r,data.h,data.p,data.nn]=choose_parameters(epsil); %choose the parameters for the fast erfc summation
    gradient_function=@gradient_vector_linear_approx;
end

%--------------------------------------------------------------------------
% NCG routine
%--------------------------------------------------------------------------

[w,iter,time_taken_NCG]=nonlinear_conjugate_gradient(...
    start_w,...
    NCG_parameters,...
    gradient_function,...
    data,...
    verbose);

time_taken=etime(clock,to);

return

%--------------------------------------------------------------------------

function [delta_1]=precompute_delta_1(data)
% Precomputes the term $$\Delta_1$$ described in the paper.

for i=1:data.S
    mean_vector(:,i)=mean(data.X{i},2);
end

delta_1=zeros(data.d,1);
for g=1:data.C
    i=data.G(g,1);
    j=data.G(g,2);
    delta_1=delta_1+(data.m(i)*data.m(j)*(mean_vector(:,i)-mean_vector(:,j)));    
end

%--------------------------------------------------------------------------
function [x]=generate_uniform_vector(a,b,M,N)

% This function generates MxN matrix of uniformly distributed numbers
% between a and b.

m=(a+b)/2;
r=(b-a);
x=m-r*0.5+r*rand(M,N);

return

%--------------------------------------------------------------------------