function B = vpc(A, W)
%VPC Voted perceptron classifier
%
%   W = VPC(A)
%   W = VPC(A, N)
%
% INPUT 
%   A   Dataset
%   N   Number of sweeps
%
% OUTPUT 
%   W   Voted perceptron classifier
%
% DESCRIPTION 
% The classifier trains an ensemble of perceptrons on dataset A. The
% training procedure performs N full sweeps through the training data. If N
% is not specified, 10 sweeps are performed. The total number of
% perceptrons in the ensemble is equal to N x GETSIZE(A, 1).
%
% The classification of new objects is performed by allowing the ensemble  
% of perceptrons to vote on the label of each test point.
%
% REFERENCE
% Y. Freund and R.E. Schapire. Large Margin Classification Using the 
% Perceptron Algorithm. Machine Learning 37(3):277-296, 1999.
%
% SEE ALSO (<a href="http://37steps.com/prtools">PRTools Guide</a>)
% DATASETS, MAPPINGS, PERLC, ADABOOSTC

% (C) Laurens van der Maaten, 2010
% University of California, San Diego

    name = 'Voted perceptron';

    % Handle untrained calls like W = vpc([]);
    if nargin == 0 || isempty(A)
        B = prmapping(mfilename); 
        B = setname(B, name); 
        return;
        
    % Handle training on dataset A (use A * vpc, A * vpc([]), and vpc(A))
    elseif (nargin == 1 && isa(A, 'prdataset')) || (isa(A, 'prdataset') && isa(W, 'double'))
        if nargin == 1
            W = 10;
        end
        islabtype(A, 'crisp');
        isvaldfile(A, 1, 2);
        A = testdatasize(A, 'features');
        A = setprior(A, getprior(A)); 
        [m, k, c] = getsize(A);
        [data.v, data.c] = train_voted_perceptron(+A, getnlab(A), W);
        B = prmapping(mfilename, 'trained', data, getlablist(A), k, c);
        B = setname(B, name);
        
    % Handle evaluation of a trained voted perceptron W for a dataset A 
    elseif (isa(A, 'prdataset') || isdouble(A)) && isa(W, 'prmapping')        
        test_post = predict_voted_perceptron(+A, W.data.v, W.data.c);
        A = prdataset(A); 
        B = setdata(A, test_post, getlabels(W));
    
    % This should not happen
    else
        error('Illegal call');
    end
end

function [v, c] = train_voted_perceptron(train_X, train_labels, max_iter)
%TRAIN_VOTED_PERCEPTRON Trains a voted perceptron on the specified data set
%
%   [v, c] = train_voted_perceptron(train_X, train_labels, max_iter)
%
% The function trains a voted perceptron on the data specified by train_X
% and train_labels. For a problem with K classes, the functions trains K
% voted perceptrons in a one-vs-all manner. The cell-array v contains the
% perceptrons for each class, whereas the cell-array c contains the
% corresponding weights of the perceptrons.
%
%
% (C) Laurens van der Maaten, 2010
% University of California, San Diego

    % Add the bias term to the data
    train_X = [train_X ones(size(train_X, 1), 1)];

    % Initialize some variables
    [n, d] = size(train_X);
    lablist = unique(train_labels);
    no_labels = length(lablist);
    
    % Shuffle the data
    ind = randperm(n);
    train_X = train_X(ind,:);
    train_labels = train_labels(ind);
    
    % Initialize voted perceptron cell arrays
    c = cell(no_labels, 1);
    v = cell(no_labels, 1);
    
    % Loop over all classes
    for k=1:no_labels
        
        % Initialize voted perceptron
        v{k} = zeros(d, ceil(n * max_iter / 4));          % perceptrons
        c{k} = zeros(1, ceil(n * max_iter / 4));          % survival times
        index = 1;
        
        % Construct appropriate labelling
        labels = train_labels;
        labels(labels ~= k) = -1;
        labels(labels == k) =  1;

        % Perform learning iterations
        for iter=1:max_iter 

            % Loop over all data points
            for i=1:n

                % Perform prediction
                y = +sign(train_X(i,:) * v{k}(:,index));

                % Train new perceptron if misclassified, or increase weight
                if y == labels(i)
                    c{k}(index) = c{k}(index) + 1;
                else
                    v{k}(:,index + 1) = v{k}(:,index) + labels(i) .* train_X(i,:)';
                    c{k}(  index + 1) = 1;
                    index = index + 1;
                end
            end
        end
        
        % Make sure we do not have 'empty' perceptrons left
        v{k} = v{k}(:,1:index);
        c{k} = c{k}(  1:index);
    end
end

function test_post = predict_voted_perceptron(test_X, v, c)
%PREDICT_VOTED_PERCEPTRON Classify test data using a voted perceptron
%
%   test_post = predict_voted_perceptron(test_X, v, c, lablist)
%
% The function classifies the data points in test_X using the voted
% perceptron specified by v and c. The voted perceptron can be trained
% using the TRAIN_VOTED_PERCEPTRON function.
%
%
% (C) Laurens van der Maaten, 2010
% University of California, San Diego

    
    % Add the bias term to the data
    test_X = [test_X ones(size(test_X, 1), 1)];

    % Prediction is maximum over all voted perceptrons
    test_post = zeros(size(test_X, 1), length(v));
    for k=1:length(v)
        test_post(:,k) = sum(bsxfun(@times, c{k}, +sign(test_X * v{k})), 2);
    end
    
    % Estimate posterior if requested
    for k=1:length(c)
        test_post(:,k) = test_post(:,k) + sum(c{k});
    end
    test_post = bsxfun(@rdivide, test_post, sum(test_post, 2));
end