AdaBoost
This is just a small practice as I find Adaboost hard to understand and I need to do some improvement of this algorithm.
1. Generating the sample data is a kind of trick because I pretend that
the event happens with the probability of each "classifier" which I
later need to find out.
2. The algorithm is based on this wonderful handout. It says it is better to do calculation "iteratively" and I still have no idea what it means.
3. Based on the trick of generating samples of "1" above, the result of
"combined-classifier" only achieves about 90% hit rate. I don't know if
it is all right, meaning whether this
is typical statistical error when generating sample by probability or
this is the limit of AdaBoost. In other words, can AdaBoost perfectly
"restore" the true "weight" of each classifier?
4. My
next experiment would be to create some "fake classifier" which simply
randomly vote when generating samples. Obviously they are like "noise"
and see if AdaBoost can find out.
And
more interesting experiment in plan is to create some "group
classifier" which means that some classifier are useless as they are
sort of "depending" other more reliable classifier. In other words,
these are "sleeping congressman" who never know what to vote except
just vote when the party leader wants them to vote. Obviously they
should not play as much weight as the "leader of the group" as the
"representative" can vote for them. Let's see if AdaBoost can find out
this.
#include <ctime>
#include <iostream>
#include <bitset>
#include <map>
#include <set>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MaxMember = 10;
struct SampleStruct
{
double committeeVote;
double sampleWeight;
};
// assume the last bit is the true result of event, or y[i], all other bits are vote of members
typedef bitset<MaxMember+1> MyBitSet;
typedef vector<pair<MyBitSet, SampleStruct> > MyBitSetWeightVector;
typedef vector<MyBitSet> MyBitSetVector;
typedef vector<float> FloatVector;
typedef vector<int> IntVector;
class AdaBoost
{
public:
int selectMember(int num)
{
if (num >= MaxMember)
{
num = MaxMember;
}
for (int member = 0; member < num; member ++)
{
int index = selectNextMember();
cout <<
index << " is new member selected with probability=" <<
probability[index] << endl;
if (index < MaxMember)
{
updateNewMember(index);
}
}
}
bool testSample(const MyBitSet& sample)
{
double result = 0.0;
for (int i = 0; i < MaxMember; i ++)
{
if (selectedMember.test(i))
{
result += (sample.test(i) ? 1.0 : -1.0) *
committeeVote[i];
}
}
double event = (sample.test(MaxMember) ? 1.0 : -1.0);
cout << " the Event is "
<< event << " and vote is " << result << endl;
return result*event > 0.0;
}
void testPerformance(int num)
{
MyBitSetVector testData;
int i;
for (i = 0; i < num; i ++)
{
MyBitSet myBitset;
generateBitset(myBitset);
testData.push_back(myBitset);
}
int counter = 0;
for (i = 0; i < testData.size(); i ++)
{
if (testSample(testData[i]))
{
counter ++;
}
}
cout << "hit rate is " << (double)counter /(double) num << endl;
}
void testPerformance()
{
int i;
int counter = 0;
for (i = 0; i < sampleData.size(); i ++)
{
const MyBitSet& myBitset = sampleData[i].first;
if (testSample(myBitset))
{
counter ++;
}
}
cout << "hit rate is "
<< (double)counter /(double) sampleData.size() << endl;
}
void init(int num)
{
initialize(num);
}
private:
void updateNewMember(int index)
{
double alpha = 0.5 * log((totalWeight - currentTotalError)/currentTotalError);
selectedMember.set(index);
committeeVote[index] = alpha;
double alphaValue = exp(alpha);
for (int i = 0; i < sampleData.size(); i ++)
{
const MyBitSet& mySet = sampleData[i].first;
bool event = mySet.test(mySet.size()-1);
bool vote = mySet.test(index);
SampleStruct& sample = sampleData[i].second;
// reset
totalWeight -= sample.sampleWeight;
if (event && !vote || !event && vote)
{
// calculate new value
sample.sampleWeight *= alphaValue;
}
else
{
// calculate new value
sample.sampleWeight /= alphaValue;
}
// plus new value
totalWeight += sample.sampleWeight;
// update vote value
sample.committeeVote += (vote?1.0:-1.0)*alpha;
}
}
int selectNextMember()
{
int i, index;
// find the first available and initialize
for (i = 0; i < MaxMember; i ++)
{
if (!selectedMember.test(i))
{
currentTotalError = calculateTotalError(i);
index = i;
break;
}
}
for (i = index + 1; i < MaxMember; i ++)
{
if (!selectedMember.test(i))
{
double totalError = calculateTotalError(i);
if (totalError < currentTotalError)
{
index = i;
currentTotalError = totalError;
}
}
}
return index;
}
double calculateTotalError(int index)
{
double totalError = 0.0;
for (int i = 0; i < sampleData.size(); i ++)
{
const MyBitSet& mySet = sampleData[i].first;
bool event = mySet.test(MaxMember);
bool vote = mySet.test(index);
if (event && !vote || !event && vote)
{
totalError +=
exp(-1*(event?1.0:-1.0)*sampleData[i].second.committeeVote);
}
}
return totalError;
}
void generateBitset(MyBitSet& myBitset)
{
int event = 0;
bool bHappen;
// the event is random...
event = rand() % 1000;
if (event > 800)
{
myBitset.set(MaxMember);
bHappen = true;
}
else
{
myBitset.reset(MaxMember);
bHappen = false;
}
int num = rand() % 1000;
for (int i = 0; i < MaxMember; i ++)
{
if ( num < probability[i])
{
myBitset.set(i, bHappen);
}
else
{
myBitset.set(i, !bHappen);
}
}
}
void generateSample(int num)
{
for (int i = 0; i < num; i ++)
{
MyBitSet myBitset;
generateBitset(myBitset);
SampleStruct sample;
sample.committeeVote = 0.0;
sample.sampleWeight = 1.0;
sampleData.push_back(make_pair(myBitset, sample));
}
}
void initialize(int num)
{
probability.clear();
memset(committeeVote, 0, sizeof(committeeVote));
for (int i = 0; i < MaxMember; i ++)
{
probability.push_back(rand()%1000);
}
sampleData.clear();
generateSample(num);
totalWeight = num;
currentTotalError = 0.0;
selectedMember.reset();
}
double totalWeight;
double currentTotalError;
MyBitSet selectedMember;
IntVector probability;
MyBitSetWeightVector sampleData;
double committeeVote[MaxMember];
};
int main()
{
srand(time(NULL));
AdaBoost ada;
ada.init(10000);
ada.selectMember(MaxMember);
//ada.selectMember(2);
ada.testPerformance();
return 0;
}
///////////////////////////////////////////////////////////////////////////////
running result:(5000 samples)
1 is new member selected with probability=933
6 is new member selected with probability=908
3 is new member selected with probability=732
7 is new member selected with probability=589
5 is new member selected with probability=393
9 is new member selected with probability=340
4 is new member selected with probability=321
2 is new member selected with probability=229
0 is new member selected with probability=56
8 is new member selected with probability=29
the Event is -1 and vote is -4.13416
the Event is -1 and vote is -4.13416
the Event is -1 and vote is 0.323252
the Event is -1 and vote is -3.74175
the Event is 1 and vote is 1.51351
the Event is -1 and vote is -1.51351
the Event is -1 and vote is -4.13416
the Event is -1 and vote is -3.74175
the Event is -1 and vote is -3.33565
the Event is 1 and vote is 3.33565
the Event is 1 and vote is 2.22078
...
...
the Event is -1 and vote is -3.74175
the Event is -1 and vote is -1.63758
the Event is -1 and vote is -4.19125
the Event is -1 and vote is -1.63758
the Event is -1 and vote is -3.33565
the Event is -1 and vote is -2.6208
the Event is -1 and vote is -1.63758
the Event is -1 and vote is -1.63758
the Event is -1 and vote is -3.74175
hit rate is 0.9449
/*
struct MyBitSetComp
{
bool operator()(const MyBitSet& left, const MyBitSet& right)const
{
return left.to_string().compare(right.to_string()) < 0;
}
};
typedef map<MyBitSet, int, MyBitSetComp> BitsetMap;
typedef map<MyBitSet, float, MyBitSetComp> BitsetWeightMap;
int probability[MaxMember] =
{100, 800, 900, 400, 780, 560, 230, 550, 340, 199};
void generate(int count, BitsetMap& myBitsetMap)
{
typedef pair<BitsetMap::iterator, bool> BitsetMapResult;
for (int i = 0; i < count; i ++)
{
MyBitSet myBitset;
generateBitset(myBitset);
BitsetMap::iterator it = myBitsetMap.find(myBitset);
if (it != myBitsetMap.end())
{
it->second ++;
}
else
{
myBitsetMap.insert(make_pair(myBitset, 1));
}
}
}
void display(const BitsetMap& myBitsetMap)
{
for (BitsetMap::const_iterator it = myBitsetMap.begin(); it != myBitsetMap.end(); ++ it)
{
cout <<"[" <<
it->first.to_string() << "]" << it->second<<
endl;
}
cout << "total:" << myBitsetMap.size() << endl;
}
void analysis(const BitsetMap& myBitsetMap)
{
int total = 0;
int counter[MaxMember] ={0};
for (BitsetMap::const_iterator it = myBitsetMap.begin(); it != myBitsetMap.end(); ++ it)
{
total += it->second;
for (int i = 0; i < it->first.size(); i ++)
{
if (it->first.test(i))
{
counter[i] += it->second;
}
}
}
for (int i = 0; i < MaxMember; i ++)
{
cout << "[" << counter[i] << "]" << endl;
}
cout << "total:" << total << endl;
}
void test1()
{
srand(time(NULL));
BitsetMap myBitsetMap;
generate(1000, myBitsetMap);
display(myBitsetMap);
analysis(myBitsetMap);
}
*/
