专栏首页绿巨人专栏机器学习实战 - 读书笔记(07) - 利用AdaBoost元算法提高分类性能

机器学习实战 - 读书笔记(07) - 利用AdaBoost元算法提高分类性能

前言

最近在看Peter Harrington写的“机器学习实战”,这是我的学习笔记,这次是第7章 - 利用AdaBoost元算法提高分类性能。

核心思想

在使用某个特定的算法是,有时会发现生成的算法f(x)的错误率比较高,只使用这个算法达不到要求。 这时f(x)就是一个弱算法。 在以前学习算法的过程中,我们认识到算法的参数很重要,所以把公式改写成这样: f(x,arguments) \\ where \\ \qquad x \text{ : calculated data} \\ \qquad arguments \text{ : function arguments} 一个思路是通过多个弱算法组合形成一个强算法来满足需求。 训练多个弱算法的思路如下:

  • 根据样本数据,求出f(x,arguments_1)
  • 调整样本数据:将满足匹配f(x,arguments_1)的样本数据的权重调低,将不满足匹配f(x,arguments_1)的样本数据的权重调高。
  • 重复以上步骤,训练出多个弱算法算法f(x,arguments_1), ..., f(x,arguments_n),直到这些弱算法组合的错误率等于0,或者小于指定值为止。

这个思路称之为Adaboost算法,是对其它算法组合的一种方式。 我们可以看出弱算法是同类的算法,也就是说,它们是基于相同的算法,只不过参数不同。这样元算法在训练算法的步骤中就好容易控制。 注:也有其它的的元算法,可以针对不同算法的。

基本概念

  • 元算法(meta-algorithm),是对其它算法组合的一种方式。也称为集成方法(ensemble method)。
  • 弱算法:准确度较低的算法。元算法通过组合多个弱算法来提高准确率。
  • 强算法:可以认为是组合后的算法。
  • boosting : 是一种元算法,将多个弱算法变成强算法的算法族。除了AdsBoost,还有LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost, and others.
  • Adaboost : Adaptive Boosting的简称。一个具体的boosting算法。本章就是介绍这个算法。

详解Adaboost

说明:书中弱算法是一个单层决策树算法,返回的是一个二类分类结果(-1, 1)。所以书中Adaboost也是一个二类分类算法。

Adaboost训练算法

  • 输入
    • 样本数据
    • 弱算法的数量
  • 输出
    • 一个弱算法数组(弱算法参数,弱算法权重\(\alpha_i\))
  • 逻辑 在一个迭代中(弱算法数量) 计算当前算法的参数 计算当前算法的错误率 计算当前算法的权重 计算下次样本数据的权重 计算当前的样本数据错误数,如果是0,退出。
  • 核心数学公式
    • 训练算法 - 计算弱算法f_i(x)的权重\alpha_i: \alpha_i = \begin{cases} \frac{1}{2}ln \left (\frac{1 - \epsilon_i}{\epsilon_i} \right), & \text{if} \epsilon_i > C \\ \frac{1}{2}ln \left (\frac{1 - \epsilon_i}{C} \right), & \text{if} \epsilon_i \leqslant C \end{cases} \\ where \\ \qquad \epsilon_i = \frac{count(\text{wrong classified samples})}{count(\text{all samples})} \text{ : error rate of function i} \\ \qquad C \text{ : constant }\ e^{-16} 解释:为什要用自然对数? 个人认为在权重方面,自然对数和log_2,log_{10}性质上是一样的,它们的结果是等比例的。 数学家倾向于使用自然对数。 求对数是可以将数据关系线性化。比如log_{10}1000 = 3, log_{10}100 = 2, log_{10}10 = 1.
    • 训练算法 - 调整样本数据:每条样本数据的权重D_1 D_i^{'(t)} = \begin{cases} D_i^{(t)}e^{-\alpha}, & \text{if the sample is classified correctly} \\ D_i^{(t)}e^{\alpha}, & \text{if the sample is not classified correctly} \end{cases} \\ D_i^{(t+1)} = \frac{D_i^{'(t)}}{\textstyle \sum_{j=1}^n D_j^{'(t)}} \\ where \\ \qquad \alpha \text{ : weight of current weak function} \\ \qquad D \text{ : is a vector, the length is the length of samples data} \\ \qquad D_i \text{ : is weight value of sample data i} \\ \qquad D_i^{(t)} \text{ : is weight value of sample i for this function} \\ \qquad D_i^{(t+1)} \text{ : is weight value of sample i for next week function} 解释: 假如有1000个sample,有100个sample被分错类,则: \begin{array}{lcl} \epsilon & =\frac{100}{1000} \\ \alpha & = \frac{1}{2}ln \left(\frac{1 - \frac{100}{1000}}{\frac{100}{1000}} \right) \\ & = \frac{1}{2}ln(9) \\ D_{correct}^{'} & = 1 * e^{-\frac{1}{2}ln(9)} \\ & = \frac{1}{e^{\frac{1}{2}} * 9} \\ D_{incorrect}^{'} & = 1 * e^{\frac{1}{2}ln(9)} \\ & = e^{\frac{1}{2}} * 9 \\ \frac{D_{incorrect}^{'}}{D_{correct}^{'}} & = e * 9 ^ 2 \end{array} 可以看出错误的sample占的比例越小,下次的权重是二次方级数增大。

Adaboost分类算法

  • 输入
    • 分类数据
    • 弱算法数组
  • 输出
    • 分类结果
  • 逻辑 在一个迭代中(弱算法数量) 用当前弱算法计算分类结果$classified_i$ 计算强分类结果(使用下面的公式) 返回分类结果
  • AdaBoost分类器中计算公式 \textstyle \sum_{i=1}^n \alpha_if_i(x) \\ where \\ \qquad \alpha_i \text{ : weight of weak function i} \\ \qquad f_i(x) \text{ : weak function i}

参考

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 强化学习读书笔记 - 02 - 多臂老O虎O机问题

    绿巨人
  • 强化学习总结

    绿巨人
  • Scala on Visual Studio Code

    绿巨人
  • 11位机器学习大牛最爱算法全解

    【新智元导读】“你最喜欢的机器学习算法是什么?”这个问题有些像“你最喜欢的颜色是什么?”说不重要吧,细究起来,颇有深意。本文摘选一些机器学习大牛在 Quora ...

    新智元
  • 【干货】机器学习常用 35 大算法盘点(附思维导图)

    【新智元导读】本文将带你遍历机器学习领域最受欢迎的算法。系统地了解这些算法有助于进一步掌握机器学习。当然,本文收录的算法并不完全,分类的方式也不唯一。不过,看完...

    新智元
  • 【榜单】计算机科学中最重要的32个算法

    【新智元导读】 奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph...

    新智元
  • 数据挖掘18大算法实现以及其他相关经典DM算法

    算法使用方法在每个算法中给出了3大类型,主算法程序,调用程序,输入数据,调用方法如下: 将需要数据的测试数据转化成与给定的输入格式相同,然后以Client类...

    机器学习AI算法工程
  • 算法概论

    打好牢固的基础,是成就高楼万丈的基石头。在学习算法之前,我们先了解算法是什么?如何设计算法?什么才是“好”算法?如何优化算法?

    PayneWu
  • 2.1 C语言程序的灵魂

    广义地说:为解决一个问题而采取的方法和步骤,就称为“算法”。计算机算法可以分为两大类:数值运算算法和非数值运算算法

    C语言入门到精通
  • 发现 | 基于深度学习的自动上色程序,以及其实际应用

    来自伯克利大学和麻省理工学院的三名研究者Richard Zhang、Phillip Isola、Alexei A. Efros日前给出了深度学习在另一个特定领域...

    AI科技评论

扫码关注云+社区

领取腾讯云代金券