前言

侦测人脸或物体即将快到尾声了，希望在12月底能完成相关的实作，也要给自己下一年新的目标，而我最困难的目标大概是英文。
这次要介绍机器学习的AdaBoost，AdaBoost原理其实很简单，使用多个线性组合起来去分类，这里最麻烦的地方应该是要推倒出分类器倍率的公式，但一步一步慢慢地去推导还是很容易理解的，接着就先介绍推倒公式。

推导公式

预测函数

每一次计算的加法模型。简单来说就是每个线性判断乘上倍率。

Markdown

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

损失函数

这里使用指数损失函数。预测结果和实际相乘。

Markdown

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

损失最小化函数(化简和对alpha求偏微分=0)

目标为将指数损失最小化，将每一层的损失相加，而每个加法模型为上一层的结果加上目前计算的权重乘上分类结果G(x)，这样做原因主要是将计算好的强分类器与目前的弱分类去做分离，方便后面计算alpha，将公式带入。

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)) $$

而第二个弱分类器函数要求的是alpha变化趋近0(偏微分)所以先化简公式。G(x)函数主要是判断分类分类正确或分类错误所以可将第二个函数拆开为分类正确函数加上分类错误，正确为1错误为-1带入结果为。

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} $$

接着化简公式，多加了两个合为0的sigma函数(2)，主要是能将其化简为较简单的函数(3)，最后将分类错误的函数转为1~N的sigma函数(4)。

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}$$

接着求出alpha，以下为推导公式详细过程。

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}$$

更新权重函数

而每个资料权重的公式，，会等于1，除了初始化和为一，还因为计算完后会将资料权重进行更新并且归一化。
由上述分开的公式一我们得知上一个分类器权重公式为，而下一层就是将m+1，将公式拆开两个式子(2)(上面有提到可将当下的权重拆开)，最后再变为最上面提到的加法模型(3)，以下推导简化公式。

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}$$

最后这里使用L1归一化，以下为公式。

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}$$

AdaBoost实作

几个月前刚碰AdaBoost找到程式码后就没仔细推导公式，这次参考[2]和[3]慢慢一步步的推导才理解，这里实作主要用上述介绍的公式实作。

类别

我主要将公式实现拆开分为这三类，AdaBoost主要是训练和预测，StrongClassfier和WeakClassfier则是储存资料和强预测和弱预测。

AdaBoost：训练资料和预测。StrongClassfier：储存弱分类器和预测强分类器。WeakClassfier：弱分类器资料和预设弱分类器。

WeakClassfier类别

由上述推倒公式纪录每一个弱分类器的资料，并且将每个分类器的权重alpha进行计算即可。而预测方面只需要使用维度索引与阀值依照分类比较符号进行比较即可。

资料成员

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);AdaBoostType::LABELS Predict(AdaBoostType::C_DATAS& data, C_UINT32& dimension) const;std::vector<double> WeightsPredict(AdaBoostType::C_DATAS& data) const;double WeightsPredict(AdaBoostType::C_DATA& data) const;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;}AdaBoostType::LABELS WeakClassifier::Predict(AdaBoostType::C_DATAS& data, C_UINT32& dimension) const{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;}std::vector<double> WeakClassifier::WeightsPredict(AdaBoostType::C_DATAS& data) const{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;}double WeakClassifier::WeightsPredict(AdaBoostType::C_DATA& data) const{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();void Add(const WeakClassifier& weakClassifier);AdaBoostType::LABELS Predict(AdaBoostType::C_DATAS& data) const;AdaBoostType::LABEL Predict(AdaBoostType::C_DATA& data) const;AdaBoostType::LABELS Sign(const std::vector<double>& predict) const;AdaBoostType::LABEL Sign(const double predict) const;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;}void StrongClassfier::Add(const WeakClassifier& weakClassifier){_weakClassifiers->push_back(weakClassifier);}AdaBoostType::LABELS StrongClassfier::Predict(AdaBoostType::C_DATAS& data) const{AdaBoostType::LABELS predict(data.size());for (UINT32 index = 0; index < data.size(); index++){predict[index] = Predict(data[index]);}return predict;}AdaBoostType::LABEL StrongClassfier::Predict(AdaBoostType::C_DATA& data) const{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);}AdaBoostType::LABELS StrongClassfier::Sign(const std::vector<double>& predict) const{AdaBoostType::LABELS labels(predict.size());for (UINT32 index = 0; index < predict.size(); index++){labels[index] = Sign(predict[index]);}return labels;}AdaBoostType::LABEL StrongClassfier::Sign(const double predict) const{return predict > 0 ? 1 : -1;}

AdaBoost类别

构想

1.输入N笔训练资料和N笔标籤。
2.预设资料的分类权重=1/N笔。
3.训练并给予训练次数T。
4.找出目前分类权重错误率最小的阀值，并更新弱分类器。
5.更新分类权重，重複直到次数T。
6.输入资料，预测结果。

资料成员

data:训练资料。label:标籤。strongClassfier:强分类器。dataWeights:训练资料目前权重。dimensionSize:维度大小。dataSize:资料数量。

主要函数

Predict:预测结果。Train:训练资料。ProcessError:找寻当下目前错误率最小的弱分类器。走访每个资料、维度和比较符号并使用弱分类器预测结果。CalcError:计算弱分类器预测与实际标籤的错误权重。UpdateWeights:更新权重。依照找寻到错误率最小的弱分类器和结果依照公式更新下一轮的权重。

程式码

AdaBoost.h

#pragma once#ifndef ADABOOST_H#define ADABOOST_H#include "general.h"#include "StrongClassfier.h"#include "WeakClassifier.h"class AdaBoost{public:AdaBoost(AdaBoostType::C_DATAS& data, AdaBoostType::C_LABELS label) :_data(data), _label(label){ Init(); };~AdaBoost();void Train(C_UINT32 weakSize);AdaBoostType::LABELS Predict(AdaBoostType::C_DATAS& data) const;AdaBoostType::LABEL Predict(AdaBoostType::C_DATA& data) const;private:void Init();void ProcessError(WeakClassifier& weakClassifier, AdaBoostType::LABELS& pridect);double CalcError(AdaBoostType::C_LABELS& pridect);void UpdateWeights(const WeakClassifier& weakClassifier, AdaBoostType::C_LABELS& pridect);AdaBoostType::C_DATAS _data;AdaBoostType::C_LABELS _label;StrongClassfier* _strongClassfier;std::vector<double>* _dataWeights;UINT32 _dimensionSize;UINT32 _dataSize;};#endif // !ADABOOST_H

AdaBoost.cpp

#include "stdafx.h"#include "AdaBoost.h"AdaBoost::~AdaBoost(){delete _dataWeights;_dataWeights = nullptr;delete _strongClassfier;_strongClassfier = nullptr;}void AdaBoost::Init(){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();}void AdaBoost::Train(C_UINT32 weakSize){for (UINT32 index = 0; index < weakSize; index++){WeakClassifier weakClassifier;AdaBoostType::LABELS pridect;ProcessError(weakClassifier, pridect);UpdateWeights(weakClassifier, pridect);_strongClassfier->Add(weakClassifier);}}void AdaBoost::ProcessError(WeakClassifier& minWeakClassifier, AdaBoostType::LABELS& minPridect){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);}double AdaBoost::CalcError(AdaBoostType::C_LABELS& pridect){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;}void AdaBoost::UpdateWeights(const WeakClassifier& weakClassifier, AdaBoostType::C_LABELS& pridect){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;}}AdaBoostType::LABELS AdaBoost::Predict(AdaBoostType::C_DATAS& data) const{return _strongClassfier->Predict(data);}AdaBoostType::LABEL AdaBoost::Predict(AdaBoostType::C_DATA& data) const{return _strongClassfier->Predict(data);}

结果

使用[4]的资料测试结果，比对后误差不大。

// AdaBoostAPI.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include "AdaBoost.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 };AdaBoost adaBoost(data, label);adaBoost.Train(5);AdaBoostType::LABELS labels = adaBoost.Predict(data);for (UINT32 index = 0; index < labels.size(); index++){std::cout << labels[index] << " ";}system("pause");return 0;}

---

AdaBoostAPI

结语

这礼拜跳过"Selective Search for Object Recognition"主要原因是想把论文看完，所以这礼拜先介绍AdaBoost，若有问题或错误欢迎提问。

参考文献

[1]https://upmath.me/
[2]liuwu265@126.com(2015) AdaBoost 算法原理及推导 https://www.cnblogs.com/liuwu265/p/4692347.html(2018.12.05)
[3]SIGAI(2018). 理解AdaBoost算法 form:https://zhuanlan.zhihu.com/p/43443518(2018.12.05)
[4]v_JULY_v(2014) Adaboost 算法的原理与推导 form:https://blog.csdn.net/v_JULY_v/article/details/40718799(2018.12.08)