% adaboost.M1 revise 2, set some of the highest weight to be zero after some iterations
function [trerr, tserr, w] = adaboostM1_revise1(type, fea_tr, lab_tr, fea_ts, lab_ts, M, cn)
% perform adaboost algorithm 
% type:                 the based classifier
% fea_tr, lab_tr:       training feature and label
% fea_ts, lab_ts:       testing feature and label
% M:                    iteration num
% cn:                   class num
% 
% trerr                 training error (combined)
% tserr                 testing error
% w                     weight distribution

if nargin < 6
    disp('adaboostM1(type, fea_tr, lab_tr, fea_ts, lab_ts, M, [cn])');
    return;
elseif nargin == 6
    cn = 2;
end

if nargout < 3
    w = [];
end

c = 5;
c1 = 10;

% first get parameters
vsize = size(fea_tr, 1);
trnum = size(fea_tr, 2);
tsnum = size(fea_ts, 2);

if (vsize ~= size(fea_ts, 1))
    disp('training feature and testing feature donnot have same size\n');
    return;
end

if (trnum ~= size(lab_tr, 2))
    disp('training set has different feature and label size\n');
    return;
end

if (tsnum ~= size(lab_ts, 2))
    disp('testing set has different feature and label size\n');
    return;
end

% deal with different base classifiers
switch lower(type)
    
case 'nearest'                      % nearest neighbour
    % parameters
    weight = ones(1, trnum) / trnum;
    alpha_M = zeros(1, M);
    hypo_tr_M = zeros(1, trnum, M);
    I_tr_M = zeros(1, trnum, M);
    hypo_ts_M = zeros(1, tsnum, M);
    I_ts_M = zeros(1, tsnum, M);
    m = 1; err = -1;
    
    while m<=M & err<0.5 & err~=0
        % resample data
        [fea_w, lab_w, idx_w] = resample(fea_tr, lab_tr, weight);
        
        % train base classifier and run base classifier on ORIGINAL trainning data, I==1 means wrongly classified
        % for KNN, it requires only one step
        [I_tr, hypo_tr] = knn(fea_w, lab_w, fea_tr, lab_tr);        % train on training set
        [I_ts, hypo_ts] = knn(fea_w, lab_w, fea_ts, lab_ts);        % train on testing set
        
        % calculate err
        err = sum(weight .* I_tr, 2) / sum(weight, 2);
        
        % calculate alpha
        alpha_M(m) = 0.5*log((1-err)/err);
        
        % update weight
        weight = weight .* exp(2*alpha_M(m)*I_tr);
        mean_weight = mean(weight);
        % trim weights
        if mod(m,c) == 0
            weight(find(weight == max(weight))) = mean_weight;
        end

        weight = weight ./ sum(weight,2);
           
        % store parameters for round m
        hypo_tr_M(:, :, m) = hypo_tr;
        hypo_ts_M(:, :, m) = hypo_ts;
        I_tr_M(:, :, m) = I_tr;
        I_ts_M(:, :, m) = I_ts;
        
        % update m
        m = m + 1;
        
    end

    % show debug information
    disp(m);
    disp(alpha_M);
    
    % combine all weak learners and output trainning error
    tr_res = zeros(1, trnum);
    for i = 1:trnum
        v = zeros(1, cn);
        for t = 1:m-1
            if I_tr_M(:, i, t) == 0
                v(hypo_tr_M(:, i, t)) = v(hypo_tr_M(:, i, t)) + alpha_M(t);
            end
        end
        [c,argmax] = max(v);
        tr_res(:, i) = argmax; 
    end
    
    tr_err = (tr_res ~= lab_tr);
    trerr = sum(tr_err)/trnum;
    fprintf(1, 'training err of 1NN is %f\n', trerr);
    
    
    % combine all weak learners and output testing error
    ts_res = zeros(1, tsnum);
    for i = 1:tsnum
        v = zeros(1, cn);
        for t = 1:m-1
            if I_ts_M(:, i, t) == 0
                v(hypo_ts_M(:, i, t)) = v(hypo_ts_M(:, i, t)) + alpha_M(t);
            end
        end
        [c,argmax] = max(v);
        ts_res(:, i) = argmax; 
    end
    
    ts_err = (ts_res ~= lab_ts);
    tserr = sum(ts_err)/tsnum;
    fprintf(1, 'testing err of 1NN is %f\n', tserr);
    
    % output weight
    w = weight;
        
case 'lda'
    % parameters
    weight = ones(1, trnum) / trnum;
    alpha_M = zeros(1, M);
    hypo_tr_M = zeros(1, trnum, M);
    hypo_ts_M = zeros(1, tsnum, M);
    I_tr_M = zeros(1, trnum, M);
    I_ts_M = zeros(1, tsnum, M);
    m = 1; err = -1;
    
    while m<=M & err<0.5 & err~=0
        % resample data
        [fea_w, lab_w, idx_w] = resample(fea_tr, lab_tr, weight);
        
        % train lda and get hypo
        [w, w0] = lda_tr(fea_w, lab_w, cn);
        [I_tr, hypo_tr] = lda_ts(fea_tr, lab_tr, w, w0, cn);
        [I_ts, hypo_ts] = lda_ts(fea_ts, lab_ts, w, w0, cn);
        
        % calculate err
        err = sum(weight .* I_tr, 2) / sum(weight, 2);
        
        % calculate alpha
        alpha_M(m) = 0.5*log((1-err)/err);
        
        % update weight
        weight = weight .* exp(2*alpha_M(m)*I_tr);
        weight = weight ./ sum(weight,2);
        
        % store parameters for round m
        hypo_tr_M(:, :, m) = hypo_tr;
        hypo_ts_M(:, :, m) = hypo_ts;
        I_tr_M(:, :, m) = I_tr;
        I_ts_M(:, :, m) = I_ts;
        
        % update m
        m = m + 1;
    end

    % show debug info
    disp(m);
    disp(alpha_M);
    
    % combine all weak learners and output trainning error
    tr_res = zeros(1, trnum);
    for i = 1:trnum
        v = zeros(1, cn);
        for t = 1:m-1
            if I_tr_M(:, i, t) == 0
                v(hypo_tr_M(:, i, t)) = v(hypo_tr_M(:, i, t)) + alpha_M(t);
            end
        end
        [c,argmax] = max(v);
        tr_res(:, i) = argmax; 
    end
    
    tr_err = (tr_res ~= lab_tr);
    trerr = sum(tr_err)/trnum;
    fprintf(1, 'training err of 1NN is %f\n', trerr);
    
    
    % combine all weak learners and output testing error
    ts_res = zeros(1, tsnum);
    for i = 1:tsnum
        v = zeros(1, cn);
        for t = 1:m-1
            if I_ts_M(:, i, t) == 0
                v(hypo_ts_M(:, i, t)) = v(hypo_ts_M(:, i, t)) + alpha_M(t);
            end
        end
        [c,argmax] = max(v);
        ts_res(:, i) = argmax; 
    end
    
    ts_err = (ts_res ~= lab_ts);
    tserr = sum(ts_err)/tsnum;
    fprintf(1, 'testing err of 1NN is %f\n', tserr);
    
case 'naivebayes'
    % parameters
    weight = ones(1, trnum) / trnum;
    alpha_M = zeros(1, M);
    hypo_tr_M = zeros(1, trnum, M);
    hypo_ts_M = zeros(1, tsnum, M);
    I_tr_M = zeros(1, trnum, M);
    I_ts_M = zeros(1, tsnum, M);
    m = 1; err = -1;
    
    while m<=M & err<0.5 & err~=0
        % resample data
        [fea_w, lab_w, idx_w] = resample(fea_tr, lab_tr, weight);
        
        % train naive bayes and get hypo
        [mean, var, pri] = nb_tr(fea_w, lab_w, cn);
        [I_tr, hypo_tr] = nb_ts(fea_tr, lab_tr, mean, var, pri, cn);
        [I_ts, hypo_ts] = nb_ts(fea_ts, lab_ts, mean, var, pri, cn);        
        
        % calculate err
        err = sum(weight .* I_tr, 2) / sum(weight, 2);
        
        % calculate alpha
        alpha_M(m) = 0.5*log((1-err)/err);
        
        % update weight
        weight = weight .* exp(2*alpha_M(m)*I_tr);
        weight = weight ./ sum(weight,2);
        
        % store parameters for round m
        hypo_tr_M(:, :, m) = hypo_tr;
        hypo_ts_M(:, :, m) = hypo_ts;
        I_tr_M(:, :, m) = I_tr;
        I_ts_M(:, :, m) = I_ts;
        
        % update m
        m = m + 1;
        
    end

    % show debug information
    disp(m);
    disp(alpha_M);
    
    % combine all weak learners and output trainning error
    tr_res = zeros(1, trnum);
    for i = 1:trnum
        v = zeros(1, cn);
        for t = 1:m-1
            if I_tr_M(:, i, t) == 0
                v(hypo_tr_M(:, i, t)) = v(hypo_tr_M(:, i, t)) + alpha_M(t);
            end
        end
        [c,argmax] = max(v);
        tr_res(:, i) = argmax; 
    end
    
    tr_err = (tr_res ~= lab_tr);
    trerr = sum(tr_err)/trnum;
    fprintf(1, 'training err of 1NN is %f\n', trerr);
    
    
    % combine all weak learners and output testing error
    ts_res = zeros(1, tsnum);
    for i = 1:tsnum
        v = zeros(1, cn);
        for t = 1:m-1
            if I_ts_M(:, i, t) == 0
                v(hypo_ts_M(:, i, t)) = v(hypo_ts_M(:, i, t)) + alpha_M(t);
            end
        end
        [c,argmax] = max(v);
        ts_res(:, i) = argmax; 
    end
    
    ts_err = (ts_res ~= lab_ts);
    tserr = sum(ts_err)/tsnum;
    fprintf(1, 'testing err of 1NN is %f\n', tserr);

otherwise
    disp('unknow method');
        
end
