{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "AdaBoost算法：  \n",
    "输入：训练数据集$T = \\left\\{ \\left( x_{1}, y_{1} \\right), \\left( x_{2}, y_{2} \\right), \\cdots, \\left( x_{N}, y_{N} \\right) \\right\\}$，其中$x_{i} \\in \\mathcal{X} \\subseteq R^{n}, y_{i} \\in \\mathcal{Y} = \\left\\{ +1, -1 \\right\\}, i = 1, 2, \\cdots, N$；弱学习算法  \n",
    "输出：分类器$G\\left(x\\right)$  \n",
    "1. 初始化训练数据的权值分布\n",
    "\\begin{align*}  \\\\ & D_{1}=\\left(w_{11},w_{12},\\cdots,w_{1N}\\right), \\quad w_{1i} = \\dfrac{1}{N}, \\quad i=1,2,\\cdots,N\\end{align*}     \n",
    "2. 对$m=1,2,\\cdots,M$  \n",
    "2.1 使用具有权值分布$D_{m}$的训练数据集学习，得到基本分类器\n",
    "\\begin{align*}  \\\\ & G_{m}\\left(x\\right): \\mathcal{X} \\to \\left\\{ -1, +1\\right\\} \\end{align*}   \n",
    "2.2 计算$G_{m}\\left(x\\right)$在训练数据集上的分类误差率  \n",
    "\\begin{align*} \\\\& e_{m} = P\\left(G_{m}\\left(x_{i}\\right) \\neq y_{i}\\right)\n",
    "\\\\ & = \\sum_{i=1}^{N} w_{mi} I \\left(G_{m}\\left(x_{i}\\right) \\neq y_{i} \\right) \\end{align*}   \n",
    "2.3 计算$G_{m} \\left(x\\right)$的系数 \n",
    "\\begin{align*}  \\\\ & \\alpha_{m} = \\dfrac{1}{2} \\log \\dfrac{1-e_{m}}{e_{m}} \\end{align*}\n",
    "2.4 更新训练数据集的权值分布\n",
    "\\begin{align*}  \\\\ &  D_{m+1}=\\left(w_{m+1,1},\\cdots,w_{m+1,i},\\cdots,w_{m+1,N}\\right)\n",
    "\\\\ & w_{m+1,i} = \\dfrac{w_{mi}}{Z_{m}} \\exp \\left(- \\alpha_{m} y_{i} G_{m}\\left(x_{i}\\right)\\right), \n",
    "\\\\ & \\quad \\quad = \\left\\{\n",
    "\\begin{aligned} \n",
    "\\ &  \\dfrac{w_{mi}}{Z_{m}} \\exp \\left(- \\alpha_{m} \\right), G_{m}\\left(x_{i}\\right) = y_{i}\n",
    "\\\\ & \\dfrac{w_{mi}}{Z_{m}} \\exp \\left( \\alpha_{m} \\right), G_{m}\\left(x_{i}\\right) \\neq y_{i}\n",
    "\\end{aligned}\n",
    "\\right. \\quad i=1,2,\\cdots,N \\end{align*}\n",
    "其中，$Z_{m}$是规范化因子\n",
    "\\begin{align*}  \\\\ & Z_{m}＝ \\sum_{i=1}^{N} w_{mi} \\exp \\left(- \\alpha_{m} y_{i}, G_{m}\\left(x_{i}\\right)\\right)\\end{align*}    \n",
    "3. 构建基本分类器的线性组合\n",
    "\\begin{align*}  \\\\ & f \\left( x \\right) = \\sum_{m=1}^{M} \\alpha_{m} G_{m} \\left( x \\right) \\end{align*}   \n",
    "得到最终分类器\n",
    "\\begin{align*}  \\\\ & G\\left(x\\right) = sign\\left(f\\left(x\\right)\\right)=sign\\left(\\sum_{m=1}^{M} \\alpha_{m} G_{m} \\left( x \\right)\\right) \\end{align*}   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "加法模型\n",
    "\\begin{align*}  \\\\ & f \\left( x \\right) = \\sum_{m=1}^{M} \\beta_{m} b\\left(x;\\gamma_{m}\\right) \\end{align*} \n",
    "其中，$b\\left(x;\\gamma_{m}\\right)$为基函数，$\\beta_{m}$为基函数系数，$\\gamma_{m}$为基函数参数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在给定训练数据及损失函数$L\\left(y,f\\left(x\\right)\\right)$的条件下，学习加法模型$f\\left(x\\right)$成为经验风险极小化问题\n",
    "\\begin{align*}  \\\\ & \\min_{\\beta_{m},\\gamma_{m}} \\sum_{i=1}^{N} L \\left( y_{i}, \\sum_{m=1}^{M} \\beta_{m} b\\left(x_{i};\\gamma_{m}\\right)  \\right) \\end{align*} "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "学习加法模型，从前向后每一步只学习一个基函数及其系数，即每步只优化\n",
    "\\begin{align*}  \\\\ & \\min_{\\beta,\\gamma} \\sum_{i=1}^{N} L \\left( y_{i}, \\beta b\\left(x_{i};\\gamma\\right)  \\right) \\end{align*} "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "前向分布算法：  \n",
    "输入：训练数据集$T = \\left\\{ \\left( x_{1}, y_{1} \\right), \\left( x_{2}, y_{2} \\right), \\cdots, \\left( x_{N}, y_{N} \\right) \\right\\}$，损失函数$L\\left(y,f\\left(x\\right)\\right)$；基函数集$\\left\\{b\\left(x;\\gamma\\right)\\right\\}$  \n",
    "输出：加法模型$f\\left(x\\right)$  \n",
    "1. 初始化$f_{0}\\left(x\\right)=0$     \n",
    "2. 对$m=1,2,\\cdots,M$  \n",
    "2.1 极小化损失函数\n",
    "\\begin{align*}  \\\\ & \\left(\\beta_{m},\\gamma_{m}\\right) = \\arg \\min_{\\beta,\\gamma} \\sum_{i=1}^{N} L \\left( y_{i},f_{m-1} \\left(x_{i}\\right) + \\beta b\\left(x_{i};\\gamma \\right)\\right) \\end{align*} \n",
    "得到参数$\\beta_{m},\\gamma_{m}$  \n",
    "2.2 更新  \n",
    "\\begin{align*} \\\\& f_{m} \\left(x\\right) = f_{m-1} \\left(x\\right) + \\beta_{m} b\\left(x;\\gamma_{m}\\right) \\end{align*}   \n",
    "3. 得到加法模型\n",
    "\\begin{align*}  \\\\ & f \\left( x \\right) = f_{M} \\left( x \\right) = \\sum_{m=1}^{M} \\beta_{m} b \\left( x; \\gamma_{m} \\right) \\end{align*}    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "训练数据集\n",
    "\\begin{align*} \\\\& T = \\left\\{ \\left( x_{1}, y_{1} \\right), \\left( x_{2}, y_{2} \\right), \\cdots, \\left( x_{N}, y_{N} \\right) \\right\\} \\end{align*}   \n",
    "其中，$x_{i} \\in \\mathcal{X} \\subseteq R^{n}, y_{i} \\in \\mathcal{Y} \\subseteq R, i = 1, 2, \\cdots, N$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将输入空间$\\mathcal{X}$划分为$J$个互不相交的区域$R_{1},R_{2},\\cdots,R_{J}$，且在每个区域上确定输出的常量$c_{j}$，则回归树\n",
    "\\begin{align*} \\\\& T \\left(x; \\varTheta\\right) =  \\sum_{j=1}^{J} c_{j} I \\left(x \\in R_{j}\\right) \\end{align*} \n",
    "其中，参数$\\varTheta = \\left\\{ \\left(R_{1}, c_{1}\\right),\\left(R_{2}, c_{2}\\right),\\cdots,\\left(R_{J}, c_{J}\\right) \\right\\}$表示树的区域划分和各区域上的常数。$J$是回归树的负责度即叶结点个数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "回归提升树使用前向分布算法\n",
    "\\begin{align*} \\\\& f_{0}=0\n",
    "\\\\ & f_{m}\\left(x\\right) = f_{m-1}\\left(x\\right) + T \\left(x; \\varTheta_{m}\\right) \n",
    "\\\\ & f_{M} = \\sum_{m=1}^{M} T \\left(x; \\varTheta_{m}\\right) \\end{align*} "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在前向分布算法的第$m$步给定当前模型$f_{m-1}\\left(x\\right)$，模型参数\n",
    "\\begin{align*} \\\\& \\hat \\varTheta_{m} = \\arg \\min_{\\varTheta_{m}} \\sum_{i=1}^{N} L \\left( y_{i}, f_{m-1}\\left(x_{i}\\right) + T \\left( x_{i}; \\varTheta_{m} \\right) \\right) \\end{align*} \n",
    "得到第$m$棵树的参数$\\hat \\varTheta_{m}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当采用平方误差损失函数\n",
    "\\begin{align*} \\\\& L \\left( y, f_{m-1}\\left(x\\right)+T\\left(x;\\varTheta_{m}\\right)\\right) \n",
    "\\\\ & = \\left[y-f_{m-1}\\left(x\\right)-T\\left(x;\\varTheta_{m}\\right)\\right]^{2} \n",
    "\\\\ & = \\left[r-T\\left(x;\\varTheta_{m}\\right)\\right]^{2}\\end{align*} \n",
    "其中，$r=y-f_{m-1}\\left(x\\right)$是当前模型拟合数据的残差。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "回归提升树算法：  \n",
    "输入：训练数据集$T = \\left\\{ \\left( x_{1}, y_{1} \\right), \\left( x_{2}, y_{2} \\right), \\cdots, \\left( x_{N}, y_{N} \\right) \\right\\},x_{i} \\in \\mathcal{X} \\subseteq R^{n}, y_{i} \\in \\mathcal{Y} \\subseteq R, i = 1, 2, \\cdots, N$  \n",
    "输出：回归提升树$f_{M}\\left(x\\right)$  \n",
    "1. 初始化$f_{0}\\left(x\\right)=0$     \n",
    "2. 对$m=1,2,\\cdots,M$  \n",
    "2.1 计算残差\n",
    "\\begin{align*}  \\\\ & r_{mi}=y_{i}-f_{m-1}\\left(x_{i}\\right),\\quad i=1,2,\\cdots,N \\end{align*}  \n",
    "2.2 拟合残差$r_{mi}$学习一个回归树，得到$T\\left(x;\\varTheta_{m}\\right)$  \n",
    "2.3 更新$f_{m}=f_{m-1}\\left(x\\right)+T\\left(x;\\varTheta_{m}\\right)$   \n",
    "3. 得到回归提升树\n",
    "\\begin{align*}  \\\\ &  f_{M} \\left( x \\right) = \\sum_{m=1}^{M} T \\left(x;\\varTheta_{m}\\right) \\end{align*}    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "梯度提升算法：  \n",
    "输入：训练数据集$T = \\left\\{ \\left( x_{1}, y_{1} \\right), \\left( x_{2}, y_{2} \\right), \\cdots, \\left( x_{N}, y_{N} \\right) \\right\\},x_{i} \\in \\mathcal{X} \\subseteq R^{n}, y_{i} \\in \\mathcal{Y} \\subseteq R, i = 1, 2, \\cdots, N$，损失函数$L\\left(y,f\\left(x\\right)\\right)$  \n",
    "输出：回归树$\\hat f\\left(x\\right)$  \n",
    "1. 初始化\n",
    "\\begin{align*}  \\\\ & f_{0}\\left(x\\right) = \\arg \\min_{c} \\sum_{i=1}^{N} L \\left(y_{i},c\\right) \\end{align*}      \n",
    "2. 对$m=1,2,\\cdots,M$  \n",
    "2.1 对$i=1,2,\\cdots,N$计算\n",
    "\\begin{align*}  \\\\ & r_{mi}=- \\left[ \\dfrac {\\partial L \\left(y_{i},f\\left(x_{i}\\right) \\right)}{\\partial f \\left(x_{i} \\right)}\\right]_{f\\left(x\\right)=f_{m-1}\\left(x\\right)} \\end{align*}  \n",
    "2.2 对$r_{mi}$拟合回归树，得到第$m$棵树的叶结点区域$R_{mj},j=1,2,\\cdots,J$  \n",
    "2.3 对$j=1,2,\\cdots,J$计算\n",
    "\\begin{align*}  \\\\ &  c_{mj}=\\arg \\min_{c} \\sum_{x_{i} \\in R_{mj}} L \\left( y_{i},f_{m-1} \\left(x_{i}\\right)+c \\right) \\end{align*} \n",
    "2.4 更新$f_{m}\\left(x\\right)= f_{m-1}\\left(x\\right) + \\sum_{j=1}^{J} c_{mj} I \\left(x \\in R_{mj} \\right)$\n",
    "3. 得到回归树\n",
    "\\begin{align*}  \\\\ &  \\hat f \\left( x \\right) = f_{M} \\left( x \\right) = \\sum_{m=1}^{M} \\sum_{j=1}^{J} c_{mj} I \\left( x \\in R_{mj} \\right) \\end{align*}    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}