2

# 推導公式

### 預測函數

Markdown

$$F(x)=\sum_{m=0}^M=\alpha_mG_m(x)$$


### 損失函數

Markdown

$$L(y,F(x))=exp(-yf(x))$$


### 損失最小化函數(化簡和對alpha求偏微分=0)

Markdown

$$(\alpha_m,G_m(x)) = min\sum_{i=1}^N exp(-y_i(f_{m-1}(x_i) + \alpha G(x_i)))$$


Markdown

$$w_{mi} = exp(-y_i f_{m-1}(x_i))$$


Markdown

$$(\alpha_m,G_m(x)) = min\sum_{i=1}^N w_{mi} exp(-y_i \alpha G(x_i))$$


Markdown

$$g(\alpha) = exp(-\alpha_m)\sum_{y=G_{m(x_i)}}^{}w_{mi} + exp(\alpha_m)\sum_{y\neq G_{m(x_i)}}^{}w_{mi}$$


Markdown

\begin{align} g(\alpha) &= exp(-\alpha_m)\sum_{y=G_m(x_i)}^{}w_{mi} + exp(\alpha_m)\sum_{y\neq G_m(x_i)}^{}w_{mi}\\ &= exp(-\alpha_m)\sum_{y=G_m(x_i)}^{}w_{mi} + exp(-\alpha_m)\sum_{y\neq G_m(x_i)}^{}w_{mi} - exp(-\alpha_m)\sum_{y\neq G_m(x_i)}^{}w_{mi} + exp(\alpha_m)\sum_{y\neq G_m(x_i)}^{}w_{mi}\\ &= exp(-\alpha_m)\sum_{i=1}^{N}w_{mi} + (exp(\alpha_m) - exp(-\alpha_m))\sum_{y\neq G_m(x_i)}^{}w_{mi}\\ &= exp(-\alpha_m)\sum_{i=1}^{N}w_{mi} + (exp(\alpha_m) - exp(-\alpha_m))\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i)) \end{align}


alpha求偏微分(變化) = 0，因為alpha都提出來且都在自然指數，所以依照公式其他地方可以忽略直接針對exp帶入偏微分(3)，最後偏微分結果為(4)。

Markdown

\begin{align} &\frac{\delta G(\alpha)}{\delta\alpha} = 0\\ &exp(-\alpha_m)\sum_{i=1}^{N}w_{mi} + (exp(\alpha_m) - exp(-\alpha_m))\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))=\\ &-1(exp(-\alpha_m))\sum_{i=1}^{N}w_{mi}) + (1(exp(\alpha_m))-(-1(exp(-\alpha_m)))\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))=\\ &-exp(-\alpha_m)\sum_{i=1}^{N}w_{mi}) + (exp(\alpha_m)+exp(-\alpha_m))\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i)) = 0 \end{align}


Markdown(em代替)

\begin{align} &-exp(-\alpha_m)\sum_{i=1}^{N}w_{mi} + (exp(\alpha_m)+exp(-\alpha_m))\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i)) = 0\\ &(exp(\alpha_m)+exp(-\alpha_m))\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i)) = exp(-\alpha_m)\sum_{i=1}^{N}w_{mi}\\ &(exp(\alpha_m)+exp(-\alpha_m))\frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}} = exp(-\alpha_m)\\ &\frac{(exp(\alpha_m)+exp(-\alpha_m))}{exp(-\alpha_m)}e_m = 1\\ &(exp(2\alpha_m)+1)e_m = 1 \\ &exp(2\alpha_m)e_m+e_m = 1\\ &exp(2\alpha_m)e_m = 1 - e_m\\ &exp(2\alpha_m) = \frac{1 - e_m}{e_m}\\ &2\alpha_m = ln(\frac{1 - e_m}{e_m})\\ &\alpha_m = \frac{1}{2}ln(\frac{1 - e_m}{e_m}) \end{align}


Markdown(無代替)

\begin{align} &-exp(-\alpha_m)\sum_{i=1}^{N}w_{mi} + (exp(\alpha_m)+exp(-\alpha_m))\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i)) = 0\\ &(exp(\alpha_m)+exp(-\alpha_m))\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i)) = exp(-\alpha_m)\sum_{i=1}^{N}w_{mi}\\ &(exp(\alpha_m)+exp(-\alpha_m))\frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}} = exp(-\alpha_m)\\ &\frac{(exp(\alpha_m)+exp(-\alpha_m))}{exp(-\alpha_m)}\frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}} = 1\\ &(exp(2\alpha_m)+1)\frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}} = 1 \\ &exp(2\alpha_m)\frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}}+\frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}} = 1\\ &exp(2\alpha_m)\frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}} = 1 - \frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}}\\ &exp(2\alpha_m) = \frac{1 - \frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}}}{\frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}}}\\ &2\alpha_m = ln(\frac{1 - \frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}}}{\frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}}})\\ &\alpha_m = \frac{1}{2}ln(\frac{1 - \frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}}}{\frac{\sum_{i=1}^{N}w_{mi}I(y_i\neq G_m(x_i))}{\sum_{i=1}^{N}w_{mi}}}) \end{align}


### 更新權重函數

Markdown

\begin{align} w_{m + 1,i} &= exp(-y_if_m(x_i))\\ &= exp(-y_i(f_{m-1}(x)+\alpha_mG(x))\\ &= exp(-y_i\alpha_mG(x_i)) \end{align}


Markdown

\begin{align} Z_m &=\sum_{i=1}^Nexp(-y_i\alpha_mG(x_i)) \\ w_{m+1,i} &= \frac{w_{m,i}}{Z_m}exp(-y_i\alpha_mG(x_i)) \end{align}


## 類別

• StrongClassfier：儲存弱分類器和預測強分類器。
• WeakClassfier：弱分類器資料和預設弱分類器。

## WeakClassfier類別

### 資料成員

• error:錯誤權重總和。
• dimension:維度索引。
• alpha:弱分類器權重。
• sign:分類的比較符號。
• threshold:分類闊值。

### 主要函數

• Predict:無權重的預測結果(1　or　-1)。
• WeightsPredict:有權重的預測結果(alpha　or　-alpha)。

### 程式碼

WeakClassfier.h

#pragma once
#ifndef WEAKCLASSIFIER_H
#define WEAKCLASSIFIER_H
#include "general.h"

/**********************************************************
* pridect formula: alpha * compare(DATAS[dimension], threshold)
***********************************************************/
class WeakClassifier
{
public:
enum SignType
{
BIG, SMALL
};

WeakClassifier();
~WeakClassifier();

WeakClassifier& operator=(const WeakClassifier& weakClassifier);

void Dimension(C_UINT32 dimension);
UINT32 Dimension() const;

void Threshold(C_DOUBLE threshold);
double Threshold() const;

double Alpha() const;

void Error(C_DOUBLE sign);
double Error() const;

void Sign(const SignType sign);
SignType Sign() const;

void SetWeakParams(C_UINT32 dimension, C_DOUBLE threshold, C_DOUBLE alpha, const SignType sign);

void SetWeakParams(C_UINT32 dimension, C_DOUBLE threshold, C_DOUBLE alpha);

private:
typedef bool (*CMP_FM)(C_DOUBLE, C_DOUBLE);

CMP_FM GetCompareFormula() const;

UINT32 _dimension;
double _threshold;
double _alpha;
double _error;
SignType _sign;
};

#endif // !WEAKCLASSIFIER_H


WeakClassfier.cpp

#include "stdafx.h"
#include "WeakClassifier.h"

WeakClassifier::WeakClassifier()
{

}

WeakClassifier::~WeakClassifier()
{

}

WeakClassifier& WeakClassifier::operator=(const WeakClassifier& weakClassifier)
{
_dimension = weakClassifier.Dimension();
_threshold = weakClassifier.Threshold();
_alpha = weakClassifier.Alpha();
_sign = weakClassifier.Sign();

return *this;
}

{
C_UINT32 size = data.size();

std::vector<__int32> predict(size);
WeakClassifier::CMP_FM compare = GetCompareFormula();

for (UINT32 index = 0; index < size; index++)
{
if (compare(data[index][dimension], _threshold))
{
predict[index] = 1;
}
else
{
predict[index] = -1;
}
}
return predict;
}

{
C_UINT32 size = data.size();

std::vector<double> predict(size);
WeakClassifier::CMP_FM compare = GetCompareFormula();

for (UINT32 index = 0; index < size; index++)
{
if (compare(data[index][_dimension], _threshold))
{
predict[index] =  _alpha;
}
else
{
predict[index]= -_alpha;
}
}
return predict;
}

{
WeakClassifier::CMP_FM compare = GetCompareFormula();

if (compare(data[_dimension], _threshold))
{
return _alpha;
}
else
{
return -_alpha;
}
}

WeakClassifier::CMP_FM WeakClassifier::GetCompareFormula() const
{
switch (_sign)
{
case SignType::SMALL:
return [](C_DOUBLE value, C_DOUBLE threshold) {return value <= threshold; };
case SignType::BIG:
return [](C_DOUBLE value, C_DOUBLE threshold) {return value > threshold; };
default:
return [](C_DOUBLE value, C_DOUBLE threshold) {return value <= threshold; };
}
}

void WeakClassifier::Dimension(C_UINT32 dimension)
{
_dimension = dimension;
}

UINT32 WeakClassifier::Dimension() const
{
return _dimension;
}

void  WeakClassifier::Threshold(C_DOUBLE threshold)
{
_threshold = threshold;
}

double  WeakClassifier::Threshold() const
{
return _threshold;
}

void WeakClassifier::Error(C_DOUBLE error)
{
_error = error;
_alpha = 0.5 * log((1.0 - error) / std::max(error, 0.0000000000001)) / log(exp(1));
}

double WeakClassifier::Error() const
{
return _error;
}

double WeakClassifier::Alpha() const
{
return _alpha;
}

void WeakClassifier::Sign(const SignType sign)
{
_sign = sign;
}

WeakClassifier::SignType WeakClassifier::Sign() const
{
return _sign;
}

void WeakClassifier::SetWeakParams(C_UINT32 dimension, C_DOUBLE threshold, C_DOUBLE error, const SignType sign)
{
Dimension(dimension);
Threshold(threshold);
Error(error);
Sign(sign);
}

void WeakClassifier::SetWeakParams(C_UINT32 dimension, C_DOUBLE threshold, C_DOUBLE error)
{
Dimension(dimension);
Threshold(threshold);
Error(error);
}


## StrongClassfier類別

### 資料成員

• weakClassifiers:所有的弱分類器。

### 主要函數

• Predict:預測結果(1　or　-1)。

### 程式碼

StrongClassfier.h

#pragma once
#ifndef STRONGCLASSFIER_H
#define STRONGCLASSFIER_H
#include "general.h"
#include "WeakClassifier.h"

/**********************************************************
* pridect formula: sign(sum(weakClassfier.weightsPredict()))
***********************************************************/
class StrongClassfier
{
public:
StrongClassfier();
~StrongClassfier();

private:
std::vector<WeakClassifier>* _weakClassifiers;

};

#endif


StrongClassfier.cpp

#include "stdafx.h"
#include "StrongClassfier.h"

StrongClassfier::StrongClassfier()
{
_weakClassifiers = new std::vector<WeakClassifier>();
}

StrongClassfier::~StrongClassfier()
{
delete _weakClassifiers;
_weakClassifiers = nullptr;
}

{
_weakClassifiers->push_back(weakClassifier);
}

{

for (UINT32 index = 0; index < data.size(); index++)
{
predict[index] = Predict(data[index]);
}

return predict;
}

{
double predict = 0;
for (UINT32 index = 0; index < _weakClassifiers->size(); index++)
{
const double weakPredict = _weakClassifiers->at(index).WeightsPredict(data);

for (UINT32 predIndex = 0; predIndex < data.size(); predIndex++)
{
predict += weakPredict;
}
}
return Sign(predict);
}

{

for (UINT32 index = 0; index < predict.size(); index++)
{
labels[index] = Sign(predict[index]);
}
return labels;
}

{
return predict > 0 ? 1 : -1;
}


### 構想

1.輸入N筆訓練資料和N筆標籤。
2.預設資料的分類權重=1/N筆。
3.訓練並給予訓練次數T。
4.找出目前分類權重錯誤率最小的閥值，並更新弱分類器。
5.更新分類權重，重複直到次數T。
6.輸入資料，預測結果。

### 資料成員

• data:訓練資料。
• label:標籤。
• strongClassfier:強分類器。
• dataWeights:訓練資料目前權重。
• dimensionSize:維度大小。
• dataSize:資料數量。

### 主要函數

• Predict:預測結果。
• Train:訓練資料。
• ProcessError:找尋當下目前錯誤率最小的弱分類器。走訪每個資料、維度和比較符號並使用弱分類器預測結果。
• CalcError:計算弱分類器預測與實際標籤的錯誤權重。
• UpdateWeights:更新權重。依照找尋到錯誤率最小的弱分類器和結果依照公式更新下一輪的權重。

### 程式碼

#pragma once
#include "general.h"
#include "StrongClassfier.h"
#include "WeakClassifier.h"

{

public:

void Train(C_UINT32 weakSize);
private:
void Init();
void UpdateWeights(const WeakClassifier& weakClassifier, AdaBoostType::C_LABELS& pridect);

StrongClassfier* _strongClassfier;
std::vector<double>* _dataWeights;
UINT32 _dimensionSize;
UINT32 _dataSize;

};



#include "stdafx.h"

{
delete _dataWeights;
_dataWeights = nullptr;

delete _strongClassfier;
_strongClassfier = nullptr;
}

{
assert(_data.size() > 0 && _data[0].size() > 0);

_dataSize = _data.size();
_dimensionSize = _data[0].size();
_dataWeights = new std::vector<double>(_dataSize, 1.0 / _dataSize);
_strongClassfier = new StrongClassfier();
}

{
for (UINT32 index = 0; index < weakSize; index++)
{
WeakClassifier weakClassifier;

ProcessError(weakClassifier, pridect);

UpdateWeights(weakClassifier, pridect);

}
}

{
WeakClassifier weakClassifier;

double minError = 100000;

for (UINT32 dimension = 0; dimension < _dimensionSize; dimension++)
{
weakClassifier.Dimension(dimension);

for (UINT32 index = 0; index < _dataSize; index++)
{
weakClassifier.Threshold(_data[index][dimension]);

const WeakClassifier::SignType signs[] = { WeakClassifier::SignType::BIG
, WeakClassifier::SignType::SMALL };

for (UINT32 signIndex = 0; signIndex < sizeof(signs) / sizeof(WeakClassifier::SignType); signIndex++)
{
weakClassifier.Sign(signs[signIndex]);

const std::vector<__int32> pridect = weakClassifier.Predict(_data, dimension);
C_DOUBLE error = CalcError(pridect);

if (error < minError)
{
minWeakClassifier = weakClassifier;
minPridect = pridect;
minError = error;
}
}

}
}
minWeakClassifier.Error(minError);
}

{
assert(pridect.size() == _label.size());

double error = 0.0;

for (UINT32 index = 0; index < _dataSize; index++)
{
if (pridect[index] != _label[index])
{
error += _dataWeights->at(index);
}
}

return error;
}

{
double sum = 0;

for (UINT32 index = 0; index < _dataSize; index++)
{
_dataWeights->at(index) *= exp(-weakClassifier.Alpha() * pridect[index] * _label[index]);
sum += _dataWeights->at(index);
}

for (UINT32 index = 0; index < _dataSize; index++)
{
_dataWeights->at(index) /= sum;
}

}

{
return _strongClassfier->Predict(data);
}

{
return _strongClassfier->Predict(data);
}


# 結果

// AdaBoostAPI.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "general.h"
#include <iostream>
int main()
{
AdaBoostType::DATAS data = { {0}, {1},{ 2 },{ 3 },{ 4 },{ 5 },{ 6 },{ 7 },{ 8 },{ 9 } };

AdaBoostType::LABELS label = { 1, 1, 1, -1, -1, -1, 1, 1, 1, -1 };

for (UINT32 index = 0; index < labels.size(); index++)
{
std::cout << labels[index] << " ";
}

system("pause");
return 0;
}


# 參考文獻

[1]https://upmath.me/