Hi all,
I am glad that I found prtools. I am trying to develop an AdaBoost-based model which instead of using a single weak classifier, it’ll use different weak classifier and weights them to get the final output.
First, I want to implement the existing AdaBoost to check how it works:
-----------------------------
A = gendatm(2000);
[B,C] = gendat(A,0.3);
V1=B*qdc;
testc(C,V1);
[W2,V2,alf] = adaboostc(B,qdc,20,votec);
testc(C,V2);
-----------------------------
V1 is an individual classifier (qdc) which its error is : 0.121
V2 is an ensemble of 20 qdc classifier; but surprisingly its error is too high: 0.863

Where is the problem. My understanding is that AdaBoost error should not be more than individual classifiers used in it.

By the way, do you have any suggestion how to use different weak classifiers rather than one learning algorithms?

Thanks,
Hossein

Some remarks:

1. gendatm generates a 8-class problem. This is not a typical problem for adaboost.
2. qdc is not a weak classifier as it will easily overtrain, as happened a number of times when I ran this example.
3. V2 is just the set of base classifiers. Some are overtrained. If adaboost didn’t crash these classifiers may have weights 0, but are selected frequently by the default combiner maxc. Use W2 instead.
4. In this example testc may run into a recent bug. Attached is a debugged version.

Bob Duin

Dear Bob
Thanks for your quick reply.

1- I know that the original AdaBoost is a binary approach. But the AdaBoost function in PRTools refer to Multi-class AdaBoost by Zhu et al. So, my understanding is that the existing AdaBoost function available in PRTools is able for Multi-classification problem.
2- I check it with “stumpc”, the error decrease from 0.736 (individual stumpc error) to 0.395 (AdaBoost stumpc). But it is not still a strong classifier.
3&4;-Thanks,

My understanding is that AdaBoost which improves the accuracy of weak learners, can of course improve the accuracy of strong learners by ensemble of them. Is this wrong? Is this related to over-training? If yes, what is the alternative suggestion of combining strong classifiers to build a more strong classifier?

Thanks so much,
Hossein

Yes, the implementation allows for multi-class problems. It remains however tricky as in the sampling stage some classes may receive no samples at all. May be the implementation has to be improved for that. You may observe that PRTools generates warnings about the use of the pseudo-inverse. This is needed as some classes are undersampled. Moreover, some base classifiers have weight 0, which also indicates that their performance is bad.

I don’t agree with your statement that as adaboost improves the accuracy of weak learners it will also increase the accuracy of strong learners. The entire strategy is based on a slow and careful approach to tackle the problem. All small steps together constitute a solution that is sensitive to details that might be missed if you run like a giant.

PRTools is designed such that almost any set of classifiers can be combined. There is a lot of research done in this direction, e.g. on the use of fixed and trained combiners and the proper normalisation of classifier outputs, such that they all contribute to the combination. There is no guarantee that a combination of classifiers will improve over the best possible one. In your example, for instance, it is almost impossible to beat knnc, parzenc or parzendc significantly.

Bob Duin

Thanks,
I edited AdaBoost to be able to get more than one learner and combine them. The goal is to compare it with fixed combiners like meanc, etc. One character of adaboost is to highlight the miss-classified points by giving them higher weights to be consider in the next step with more attention. I am trying to use this characteristic as well as combining different classifiers. But in the data set that I used this policy does not work. i.e. that the available fixed combinators work better that this kind of extension.

To solve the problem of under-sampling I tried to modify the weights such that:
sum_weight(correctly classified)=0.5
sum_weight(wrongly classified)=0.5
but it does not work too.

I look forward to hearing from you.
Thanks,

THIS IS MY EXTENSION:

function [W,V,alf] = adaboost(a,clasf,rule,verbose)
% clasf is a vector of classifiers
prtrace(mfilename);

%%INITIALISATION
if nargin < 4, verbose = 0; end
if nargin < 3, rule = []; end
if nargin < 2 || isempty(clasf), clasf = nmc; end
if nargin < 1 || isempty(a)
W = mapping(mfilename,{clasf,n,rule,verbose});
W = setname(W,’Adaboost’);
return
end
n = size(clasf,2);
[m,k,c] = getsize(a);
V = [];
laba = getlab(a);
%lablist = getlablist(a);
%laba = getnlab(a);
%p = getprior(a);
%a = dataset(a,laba); % use numeric labels for speed
%a = setprior(a,p);
u = ones(m,1)/m; % initialise object weights
alf = zeros(1,n); % space for classifier weights
if verbose > 0 && k == 2
figure(verbose);
scatterd(a);
end

%% generate n classifiers
for i = 1:n
b = gendatw(a,u,m); % sample training set
b = setprior(b,getprior(a)); % use original priors

w = b*stacked(clasf(i)); % train weak classifier
ra = a*w; % test weak classifier

if verbose && k == 2
plotc(w,1); drawnow
end

labc = labeld(ra);
diff = sum(labc~=laba,2)~=0; % objects erroneously classified
erra = sum((diff).*u); % weighted error on original dataset

if (erra < (1-1/c)) % if classifier better then random guessing…
alf(i) = 0.5*(log((1-erra)/erra) + log(c-1));
correct = find(diff==0); % find correctly classified objects
wrong = find(diff==1); % find incorrectly classified objects
u(correct) = u(correct)*exp(-alf(i)); % give them the ...
u(wrong) = u(wrong)*exp(alf(i)); % proper weights

u(correct) = 0.5* u(correct)./sum(u(correct)); % normalize weights
u(wrong) = 0.5* u(wrong)./sum(u(wrong)); % normalize weights

u = u./sum(u); % normalize weights
else
alf(i) = 0;
end

%w = setlabels(w,lablist); % restore original labels
if verbose
disp([erra alf(i) sum(alf)])
end
V = [V w]; % store all classifiers

end

%% combine and return
if isempty(rule)
W = wvotec(V,alf); % default is weighted combiner
else
W = traincc(a,V,rule); % otherwise, use user supplied combiner
end

if verbose > 0 && k == 2
plotc(W,’r’,3)
ee = a*W*testc;
title([’Error: ‘, num2str(ee)]);
end

return

This is open for research. Anybody who likes to comment may do so.

Bob Duin