https://www.nituchao.com/category/algorithm-ml/ https://www.nituchao.com/algorithm-ml/ml-stats-em.html 2019-10-29T20:56:00+08:00 EM算法是一种迭代算法，1977年由Dempster等人总结提出，用于含有隐变量(hidden variable)的概率模型参数的极大似然估计，或极大后验概率估计。EM算法的每次迭代由两步组成：E步：求期望(expectation)；M步：求极大(maximization)；所以这一算法称为期望极大算法(expectation maximization algorithm)，简称EM算法。EM算法概率模型有时即含有观测变量(observable variable)，又含有隐变量或潜在变量(latent variable)。如果概率模型的变量都是观测变量，那么给定数据，可以直接用极大似然估计法，或贝叶斯估计法估计模型参数。但是，当模型含有隐变量时，就不能简单地使用这些估计方法。EM算法就是含有隐变量的概率模型参数的极大似然估计法，或极大后验概率估计法。首先介绍一个使用EM算法的例子 ---- 三硬币模型假设有3枚硬币，分别记作A，B，C。这些硬币正面出现的概率分别是$\pi, p$和$q$。进行如下抛硬币实验：先抛硬币A，根据其结果选出硬币B或硬币C，正面选硬币B，反面选硬币C；然后抛选出的硬币，抛硬币的结果，出现正面记作1，出现反面记作0；独立地重复n次实验(这里，n=10)，观测结果如下：$$1,1,0,1,0,0,1,0,1,1$$假设只能观测到抛硬币的结果，不能观测到抛硬币的过程。问如何估计三硬币正面出现的概率，即三硬币模型的参数：解 三硬币偶像可以写作：$$P(y|\theta)=\sum_zP(y,z|\theta)=\sum_zP(z|\theta)P(y|z,\theta) \\ = \pi p^y(1-p)^(1-y) + (1-\pi)q^y(1-q)^)(1-y)$$ https://www.nituchao.com/algorithm-ml/boosting_adaboost.html 2019-10-28T20:51:00+08:00 提升方法提升(boosting)方法是一种常用的统计学习方法，应用广泛且有效。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。提升方法的基本思路提升方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。实际上，就是"三个臭皮匠顶个诸葛亮"的道理。历史上，Kearns和Valiant首先提出了"强可学习(strongly learnable)"和"弱可学习(weakly learnable)"的概念。指出：在概率近似正确(probably approximately correct, PAC)学习的框架中，一个概念（一个类），如果存在一个多项式学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测好，那么就称这个概念是弱可学习的。Schapire后来证明强可学习与弱可学习是等价的。也就是说，在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。由于，发现弱学习算法通常要比发现强学习算法容易得多。通过将已经发现的"弱学习算法"提升(boost)为"强学习算法"，就是我们所说的提升方法。对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称为基分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据集的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。这样，对提升方法来说，有两个问题需要回答：一是在每一轮如何改变训练数据的权值或概率分布；二是如何将弱分类器组合成一个强分类器。关于第1个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器"分而治之"。至于第2个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减少分类误差率大的弱分类器的权值，使其在表决中起较小的作用。AdaBoost算法假设给定一个二分类的训练数据集：$$T=\{(x_1, y_1),(x_2, y_2),...,(x_N,y_N)\}$$其中，每个样本点由实例与标记组成。实例$x_i \in X \subset R^n$，标记$y_i \in Y = \{-1,1\}$ ,$X$是实例空间，$Y$是标记集合。AdaBoost利用以下算法，从训练数据中学习一系列弱分类器或基分类器，并将这些弱分类器线性组合成为一个强分类器。输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ,其中$x_i \in X \subset R^n, y_i \in Y={-1,+1}$;弱学习算法。输出：最终分类器$G(x)$(1) 初始化训练数据的权值分布$$D_1 = \{w_{11},...,w_{1i},...w_{1N}\}, w_{1i}=\frac{1}{N}, i=1,2,...,N$$(2) 对m=1,2,...,M​ (a) 使用具有权值分布$D_m$的训练数据集学习，得到基本分类器：$$G_m(x): X -> {-1,+1}$$(b) 计算$G_m(x)$在训练数据集上的分类误差率：$$e_m = P(G_m(x_i) \neq y_i) = \sum_{i=1}^{N}w_{mi}I(G_m(x_i) \neq y_i)$$(c) 计算$G_m(x)$的系数$$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$$这里的对数是自然对数。(d) 更新训练数据集的权值分布$$D_{m+1}=(w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N})$$$$w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)), i=1,2,...,N$$这里，$Z_m$是规范化因子：$$Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))$$它使$D_m+1$成为一个概率分布。(3) 构建基本分类器的线性组合：$$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$得到最终分类器：$$G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_m(x))$$对AdaBoost算法作如下说明：步骤(1) 假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设保证第1步能够在原始数据上学习基本分类器$G_1(x)$。步骤(2) AdaBoost反复学习基本分类器，在每一轮$m=1,2,...,M$顺次地执行下列操作：(a) 使用当前分布$D_m$加权的训练数据集，学习基本分类器$G_m(x)$。(b) 计算基本分类器$G_m(x)$在加权训练数据集上的分类误差率：$$e_m=P(G_m(x_i) \neq y_i)=\sum_{G_m(x_i) \neq y_i}w_{mi}$$这里，$w_mi$表示第m轮中第i个实例的权值，$\sum_{i=1}^Nw_{mi}=1$。这表明，$G_m(x)$在加权的训练数据集上的分类误差率是被$G_m(x)$误分类样本的权值之和，由此可以看出数据权值分布$D_m$与基本分类器$G_m(x)$的分类误差率的关系。(c) 计算基本分类器$G_m(x)$的系数$\alpha_m·\alpha_m$表示$G_m(x)$在最终分类器中的重要性。由式$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$可知，当$e_m \leq \frac{1}{2}$时，$\alpha_m \geq 0$，并且$\alpha_m$随着$e_m$的减小而增大 ，所以分类误差率越小的基本分类器在最终的分类器中的作用越大。(d) 更新训练数据的权值分布作为下一轮作准备。$$w_{m_1,i} = \begin{cases} \frac{w_{mi}}{Z_m}e^{-\alpha_m}& G_m(x_i)=y_i\\ \frac{w_{mi}}{Z_m}e^{\alpha_m}& G_m(x_i) \neq y_i \end{cases}$$由此可知，被基本分类器$G_m(x)$误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小。两相比较，误分类样本的权值被放大$e^{2\alpha_m} = \frac{e_m}{1-e_m}$倍。因此，误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是AdaBoost的一个特点。步骤(3) 线性组合$f(x)$实现M个基本分类器的加权表决。系数$\alpha_m$表示了基本分类器$G_m(x)$的重要性，这里，所有$\alpha_m$之和并不为1。$f(x)$的符号决定实例x的类，$f(x)$的绝对值表示分类的确信度。利用基本分类器b的线性组合构建最终分类器是AdaBoost的另一特点。AdaBoost实例给定如下表所示训练数据。假设弱分类器由$x<v$或$x>v$产生，其阈值v使该分类器在训练数据集上分类误差率最低。试用AdaBoost算法学习一个强分类器。$$AdaBoost实例 训练数据表$$序号12345678910x0123456789y111-1-1-1111-1解 初始化数据权值分布：$$D_1 = (w_{11},w_{12},...,w_{110})$$$$w_{1i}=0.1, i=1,2,...,10$$对$m=1$(a) 在权值分布为$D_1$的训练数据上，阈值v取2.5时分类误差率最低，故基本分类器为:$$G_1(x) = \begin{cases} 1,& x<2.5\\ -1,& x>2.5 \end{cases}$$(b) $G_1(x)$在训练数据集上的误差率$e_1=P(G_1(x_i) \neq y_i) = 0.3$(c) 计算$G_1(x)$的系数：$\alpha_1=\frac{1}{2}log\frac{1-e_1}{e_1}=0.4236$(d) 更新训练数据的权值分布：$$D_2=(w_{21},...,w_{2i},...,w_{210})$$$$w_{2i}=\frac{w_{1i}}{Z_1}exp(-\alpha_1y_iG_1(x_i)), i=1,2,...10$$$$D_2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715)$$$$f_1(x)=0.4236G_1(x)$$分类器$sign[f_1(x)]$在训练数据集上有3个误分类点。对$m=2$，(a) 在权值分布为$D_2$的训练数据集上，阈值v是8.5时分类误差率最低，基本分类器为:$$G_1(x) = \begin{cases} 1,& x<8.5\\ -1,& x>8.5 \end{cases}$$(b) $G_2(x)$在训练数据集上的误差率$e_2=0.2143$。(c) 计算$\alpha_2=0.6496$。(d) 更新训练数据权值分布:$$D_3=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)$$$$f_2(x)=0.4236G_1(x) + 0.6496G_2(x)$$分类器$sign[f_2(x)]$在训练数据集上有3个误分类点。对m=3，(a) 在权值分布为$D_3$的训练数据上，阈值v是5.5时分类误差率最低，基本分类器为：$$G_1(x) = \begin{cases} 1,& x>5.5\\ -1,& x<5.5 \end{cases}$$(b) $G_3(x)$在训练样本集上的误差率$e_3=0.1820$。(c) 计算$\alpha_3=0.7514$。(d) 更新训练数据的权值分布:$$D_4=(0.125,0.125,0.125,0.102,0.102,0.065,0.065,0.065,0.125)$$于是得到：$$f_3(x)=0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)$$AdaBoost算法的训练误差分析AdaBoost最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率。关于这个问题有下面的定理：AdaBoost的训练误差界 AdaBoost算法最终分类器的训练误差界为：$$\frac{1}{N}\sum_{i=1}^NI(G(x_i) \neq y_i) \leq \frac{1}{N}\sum_iexp(-y_if(x_i))=\prod_mZ_m$$$$G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_m(x))$$$$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$$$Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))$$证明 当$G(x_i) \neq y_i$时，$y_if(x_i) < 0$，因而$exp(-y_if(x_i)) \geq 1$。由此直接推导出前半部分。后半部分的推导要用到$Z_m$的定义式及变形：$$w_{mi}exp(-\alpha_my_iG_m(x_i))=Z_mw_{m+1,i}$$现推导如下：$$\frac{1}{N}\sum_iexp(-y_if(x_i)) \\ = \frac{1}{N}\sum_iexp(-\sum_{m=1}^M)\alpha_my_iG_m(x_i) \\ = \sum_iw_{1i}\prod_{m=1}^Mexp(-\alpha_my_iG_m(x_i)) \\ = Z_1\sum_iw_{2i}\prod_{m=2}^Mexp(-\alpha_my_iG_m(x_i)) \\ = Z_1Z_2\sum_iw_{3i}\prod_{m=3}^Mexp(-\alpha_my_iG_m(x_i)) \\ = ... \\ = Z_1Z_2...Z_{M-1}\sum_iw_{Mi}exp(-\alpha_My_iG_M(x_i)) \\ = \prod_{m=1}^MZ_m$$这一定理说明，可以在每一轮选取适当的$G_m$使得$Z_m$最小，从而使训练误差下降最快。对二分类问题，有如下结果：二分类问题 AdaBoost的训练误差界$$\prod_{m=1}^MZ_m = \prod_{m=1}^M[2\sqrt{e_m(1-e_m)}] = \prod_{m=1}^M\sqrt{1-4\gamma_m^2} \leq exp(-2\sum_{m=1}^M\gamma_m^2)$$这里，$\gamma_m = \frac{1}{2} - e_m$。证明 由Z_m的定义式得：$$Z_m = \sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i)) \\ = \sum_{yi=G_m(x_i)}w_{mi}e^{-\alpha_m} + \sum_{y_i \neq G_m(x_i)}w_{mi}e^{\alpha_m} \\ = (1-e_m)e^{-\alpha_m} + e_me^{\alpha_m} \\ = 2\sqrt{e_m(1-e_m)} = \sqrt{1-4\gamma_m^2}$$至于不等式：$$\prod_{m=1}^M\sqrt{1-4\gamma_m^2} \leq exp(-2\sum_{m=1}^M\gamma_m^2)$$则可先由$e^x$和$\sqrt{1-x}$在点x=0的泰勒展开式推出不等式$\sqrt{1-4\gamma_m^2} \leq exp(-2\gamma_m^2)$，进而得到。推论 如果存在$\gamma > 0$，对所有m有$\gamma_m \geq \gamma$，则：$$\frac{1}{N}\sum_{i=1}{N}I(G(x_i) \neq y_i) \leq exp(-2M\gamma^2)$$这表明在此条件下AdaBoost的训练误差是以指数速率下降的。这一性质当然是很有吸引力的。注意，AdaBoost算法不需要知道下界$\gamma$。这正是Freund与Schapire设计AdaBoost时所考虑的。与一些早期的提升方法不同，AdaBoost具有适应性，即它能适应弱分类器各自的训练误差率。这也是它的名称(适应的提升)的由来，Ada是Adaptive的简写。AdaBoost算法的解释AdaBoost算法还有另一个解释，即可以认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法时的二分类学习方法。前向分布算法考虑加法模型(additive model)：$$f(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m)$$其中，$b(x;\gamma_m)$为基函数，$\gamma_m$为基函数的参数，$\beta_m$为基函数的系数。在给定训练数据及损失函数$L(x,f(x))$的条件下，学习加法模型$f(x)$成为经验风险最小化即损失函数极小化问题：$$min_{\beta_m,\gamma_m}\sum_{i=1}^NL(y_i,\sum_{m=1}^M\beta_mb(x_i;\gamma_m))$$通常这是一个复杂的优化问题。前向分布算法(forward stagewise algorithm)求解这一优化问题的想法是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数：$$min_{\beta,\gamma}\sum_{i=1}^NL(y_i,\beta b(x_i;\gamma))$$给定训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}, x_i \in X \subset R^n, y_i \in Y = \{-1,+1\}$。损失函数L(y, f(x))和基函数的集合$\{b(x;\gamma\}$，学习加法模型f(x)的前向分布算法如下：前向分布算法输入：训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$；损失函数$L(y,f(x))$;基函数集$\{b(x;\gamma)\}$;输出：加法模型$f(x)$。(1) 初始化$f_0(x)=0$(2) 对$m=1,2,...,M$(a) 极小化损失函数$$(\beta_m,\gamma_m)=argmin_{\beta,\gamma}\sum_{i=1}^NL(y_i,f_{m-1}(x_i) + \beta b(x_i;\gamma))$$得到参数$\beta_m,\gamma_m$(b) 更新$$f_m(x)=f_{m-1}(x) + \beta_mb(x;\gamma_m)$$(3) 得到加法模型$$f(x)=f_M(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m)$$这样，前向分布算法将同时求解从m=1到M所有参数$\beta_m,\gamma_m$的优化问题简化为逐次求解各个$\beta_m,\gamma_m$的优化问题。前向分布算法与AdaBoost由前向分布算法可以推导出AdaBoost，用定理叙述这一关系。定理 AdaBoost算法是前向分布加法算法的特例，当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器：$$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$由基本分类器$G_m(x)$及其系数$\alpha_m$组成，$m=1,2,...,M$。前向分布算法逐一学习基函数，这一过程与AdaBoost算法逐一学习基本分类器的过程一致。下面证明前向分布算法的损失函数是指数损失函数(exponential loss function)$$L(y, f(x))=exp[-yf(x)]$$时，其学习的具体操作等价于AdaBoost算法学习的具体操作。假设经过m-1轮迭代前向分布算法已经得到$f_{m-1}(x)$：$$f_{m-1}(x) = f_{m-2}(x)+\alpha_{m-1}G_{m-1}(x) \\ = \alpha_1G_1(x) + ... + \alpha_{m-1}G_{m-1}(x)$$在第m轮迭代得到$\alpha_m, G_m(x)$和$f_m(x)$。$$f_m(x)=f_{m-1}(x) + \alpha_mG_m(x)$$目标是使前向分布算法得到的$\alpha_m$和$G_m(x)$使$f_m(x)$在训练数据集T上的指数损失最小，即：$$(\alpha_m,G_m(x))=argmin_{\alpha,G}\sum_{i=1}^Nexp[-y_i(f_{m-1}(x_i) + \alpha G(x_i))]$$也即：$$目标式：(\alpha_m,G_m(x))=argmin_{\alpha,G}\sum_{i=1}^Nw_{mi}exp[-y_i\alpha G(x_i)]$$其中，$w_{mi}=exp[-y_if_{m-1}(x_i)]$。因为$w_{mi}$既不依赖$\alpha$也不依赖$G$，所以与最小化无关。但$w_{mi}$依赖于$f_{m-1}(x)$，随着每一轮迭代而发生改变。现证使上式达到最小的$\alpha_m^*$和$G_m^*(x)$就是AdaBoost算法所得到的的$\alpha_m$和$G_m(x)$。求解可分为两步：首先，求$G_m^*(x)$。对任意$\alpha > 0$，使目标式最小的G(x)由下式得到：$$G_m^*(x)=argmin_G\sum_{i=1}^Nw_{mi}I(y_i \neq G(x_i))$$其中，$w_{mi}=exp[-y_if_{m-1}(x_i)]$。此分类器$G_m^*(x)$即为AdaBoost算法的基本分类器$G_m(x)$，因为它是使第m轮加权训练数据分类误差率最小的基本分类器。之后，求$\alpha_m^*$。目标式中：$$\sum_{i=1}^Nw_{mi}exp[-y_i\alpha G(x_i)] \\ = \sum_{y_i=G_m(x_i)}w_{mi}e^{-\alpha} + \sum_{y_i \neq G_m(x_i)}w_{mi}e^{\alpha} \\ = (e^{\alpha} - e^{-\alpha})\sum_{i=1}^Nw_{mi}I(y_i \neq G(x_i)) + e^{-\alpha}\sum_{i=1}^Nw_{mi}$$将以求得的$G_m^*(x)$带入上式，对$\alpha$求导并使导数为0，即得到使目标式最小的$\alpha$。$$\alpha_m^*=\frac{1}{2}log\frac{1-e_m}{e_m}$$其中，$e_m$是分类误差率：$$e_m=\frac{\sum_{i=1}^Nw_{mi}I(y_i \neq G_m(x_i))}{\sum_{i=1}^Nw_{mi}}=\sum_{i=1}^Nw_{miI(y_i \neq G_m(x_i))}$$这里的$\alpha_m^*$与AdaBoost算法第2(c)步的$\alpha_m$完全一致。最后看来每一轮样本权值的更新。由$$f_m(x)=f_{m-1}(x) + \alpha_mG_m(x)$$以及$w_{mi}=exp[-y_if_{m-1}(x_i)]$，可得$$w_{m+1,i}=w_{m,i}exp[-y_i\alpha_mG_m(x)]$$这与AdaBoost算法第2(d)步的样本权值的更新，只相差规范化因子，因而等价。 https://www.nituchao.com/algorithm-ml/ml-gbdt.html 2019-09-30T09:41:00+08:00 提升树是以分类树或回归树为基础分类器的提升方法，提升树被认为是统计学习中性能最好的方法之一。当损失函数是平方损失和指数损失函数时是普通提升树，当利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树时称为梯度提升决策树(GBDT)。提升树模型提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树（boosting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。如果我们取一个基本分类器if (x > 30) 1 else 0，这可以看做是由一个根节点直接连接两个叶结点的简单决策树，即所谓的决策树桩(decision stump)。提升树模型可以表示为决策树的加法模型。$$ f_M(x) = \sum_{m=0}^{M}{\alpha}_{m}G_{m}(x) $$其中，$T(x;{\theta}_m)$表示决策树；${\theta}_m$为决策树的参数；M为树的个数。提升树算法提升树算法采用前向分布算法。首先确定初始提升树$f_0(x) = 0$，第m步的模型是$$ f_m(x) = f_{m-1}(x) + T(x;{\theta}_m) $$其中，f_{m-1}(x)为当前模型，通过经验风险极小化确定下一棵决策树的参数 $ {\theta}_m$，$$ {\theta}_m = argmin_{{\theta}_m}\sum_{i=1}^{N}L(y_i, f_{m-1}(x_i) + T(x_i;{\theta}_m)) $由于树的线性组合可以很好的拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。当提升树使用平方误差损失函数时可解决回归问题，当使用指数损失函数时可解决分类问题。回归问题的提升树算法输入：训练数据集$ T={(x_1, y_1), (x_2, y_2), ... (x_N, y_N)}, x_i \in X \subset R^n, y_i \in y \subset R; $输出：提升树$ f_M(x) $(1) 初始化 $ f_0(x) = 0$(2) 对m=1,2,...,M(a) 按式$r=y-f_{m-1}(x)$计算残差$$ r_{mi} = y_i - f_{m-1}(x_i), i = 1,2,...,N $$(b) 拟合残差$ r_{mi} $学习一个回归树，得到$T(x;{\theta}_m)$(c) 更新$ f_m(x) = f_{m-1}(x) + T(x;{\theta}_m) $(3) 得到回归问题提升树$$ f_M(x) = \sum_{m=1}^{M}T(x;{\theta}_m) $$提升树实例已知如表8.2所示的训练数据，x的取值范围为区间[0.5, 10.5]，y的取值范围为区间[5.0, 10.0]，学习这个回归问题的提升树模型，考虑只用树桩作为基函数。$$ 提升树实例，训练数据表 $$$x_i$12345678910$y_i$5.565.705.916.406.807.058.908.709.009.05解 按照提升树算法，第1步求$f_i(x)$ 即回归树$T_i(x)$。首先通过以下优化问题：$$ min_s [min_{c_1}\sum_{x_i \in R_i } (y_i - c_i)^2 + min_{c_2} \sum_{x_i \in R_2}(y_i - c_2)^2] $$求解训练数据的切分点s:$$ R_1 = {x|x<= s}, R_2 = {x|x>s} $$容易求得在$ R_1, R_2 $内部使平方损失误差达到最小值的$c_1,c_2$为$$ c_1 = \frac{1}{N} \sum_{x_i \in R_i}y_i, c_2 = \frac{1}{N} \sum_{x_i \in R_2}y_i $$这里$N_1, N_2$是$R_1, R_2$的样本点数。求训练数据的切分点。根据所给数据，考虑如下切分点：$$ 1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5 $$对各切分点，不难求出相应的$R_1, R_2, c_1, c_2$及$$ m(s) = min_{c_1} \sum_{x_i \in R_1}(y_i - c_1)^2 + min_{c_2} \sum_{x_i \in R_2}(y_i - c_2)^2 $$例如，当s=1.5时，$$R_1 = {1}, R_2 = {2, 3, ...10}, c_1 = 5.56, c_2 = 7.50$$$$m(s) = min_{c_1} \sum_{x_i \in R_1}(y_i - c_1)^2 + min_{c_2} \sum_{x_i \in R_2}(y_i - c_2)^2 = 0 + 15.72 = 15.72 $$现将s及m(s)的计算结果列表如下：$$提升树算法，计算数据表$$s1.52.53.54.55.56.57.58.59.5$m(s)$15.7212.078.365.783.911.938.0111.7315.74由上表可知，当s=6.5时m(s)达到最小值，此时$R_1={1,2,...,6}, R_2={7,8,9,10}, c_1=6.24, c_2 = 8.91,$所以回归树$T_1(x)$为：$$T_1(x) = \begin{cases} 6.24& \text{x<6.5}\\ 8.91& \text{x >= 6.5} \end{cases}$$$$f_i(x)=T_i(x)$$用$f_i(x)$拟合训练数据的残差见下表，表中$r_2i=y_i - f_i(x_i), i=1,2,...,10.$$$提升树算法，残差表$$$x_i$12345678910$r_{2i}$-0.68-0.54-0.330.160.560.81-0.01-0.210.090.14用$f_1(x)$拟合训练数据的平方损失差：$$L(y, f_i(x)) = \sum_{i=1}^{10}(y_i - f_1(x_i))^2 = 1.93 $$第2步求$T_2(x)$。方法与求$T_1(x)$一样，只是拟合的数据是上表的残差。可以得到：$$T_1(x) = \begin{cases} -0.52,& \text{x<3.5}\\ 0.22& \text{x <= 3.5} \end{cases}$$$$f_2(x) = f_1(x) + T_2(x) = \begin{cases} 0.57,& \text{x<3.5}\\ 6.46,& \text{3.5 <= x <= 6.5}\\ 9.13,& \text{x >= 6.5} \end{cases}$$用$f_2(x)$拟合训练数据的平方损失误差是：$$L(y,f_2(x)) = \sum_{i=1}^{10}(y_i - f_2(x_i))^2 = 0.79$$继续求得：$$T_3(x) = \begin{cases} 0.15,& \text{x<6.5}\\ -0.22& \text{x >= 6.5} \end{cases} L(y,f_3(x))=0.47,$$$$T_4(x) = \begin{cases} -0.16,& \text{x<4.5}\\ 0.11& \text{x >= 4.5} \end{cases} L(y,f_4(x))=0.30,$$$$T_5(x) = \begin{cases} 0.07,& \text{x<6.5}\\ -0.11& \text{x >= 6.5} \end{cases} L(y,f_5(x))=0.23,$$$$T_6(x) = \begin{cases} -0.15,& \text{x<2.5}\\ 0.04& \text{x >= 2.5} \end{cases} $$$$f_6(x) = f_5(x) + T_6(x) = T_1(x) + ... + T_5(x) + T_6(x) \\ = \begin{cases} 5.63,& \text{x<2.5}\\ 5.82,& \text{2.5 >= x < 3.5} \\ 6.56,& \text{3.5 >= x < 4.5} \\ 6.83,& \text{4.5 >= x < 6.5} \\ 8.95,& \text{x >= 6.5} \end{cases} $$用$f_6(x)$拟合训练数据的平方损失误差是：$$L(y,f_6(x)) = \sum_{i=1}^{10}(y_i - f_6(x_i))^2=0.17$$假设此时已满足误差要求，那么$f(x) = f_6(x)$即为所求提升树。梯度提升算法提升树利用加法模型与前向分步算法实现学习的优化过程，当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不是那么容易。针对这一问题，Freidman提出了梯度提升(gradient boosting)算法。这是利用最速下降法的近似方法，器其关键是利用损失函数的负梯度在当前模型的值：$$ -\left[ \partial{L(y, f(x_i))} / \partial{f(x_i)} \right] $$作为回归问题提升树算法中的残差的近似值，拟合一个回归树。梯度提升算法:输入：训练数据集$ T={(x_1, y_1), (x_2, y_2),... (x_N, y_N)}, x_i \in X \subset R^n, y_i \in y \subset R; $ 损失函数L(y, f(x));输出：回归树f(x).(1) 初始化$$ f_0(x) = argmin_c{\sum_{i=1}^NL(y_i, c)} $$(2) 对m=1,2,...,M(a) 对i=1,2,...,N,计算$$ r_{mi} = -\left[ \partial{L(y, f(x_i))} / \partial{f(x_i)} \right] $$(b) 对$ r_{mi} $拟合一个回归树，得到第m棵树的叶节点区域$R_{mj}, j=1,2,...,J$(c) 对$ j=1,2,...J, $计算$$ c_{mj} = argmin_c {\sum_{x_i \in R_{mj}}L(y_i, f_{m-1}(x_i) + c)} $$(d) 更新 $ f_m(x) = f_{m-1}(x) + \sum_{j=1}^{J}c_{mj}I(x \in $_{mj}) $(3) 得到回归树$$ \hat{f(x)} = f_M(x) = \sum_{m=1}^{M}\sum_{j=1}^Jc_{mj}I(x \in R_{mj}) $$算法第1步初始化，估计使损失函数极小化的常数值，它只是一个根结点的树。第2(a)步计算损失函数的负梯度在当前模型的值，将它作为残差的估计。对于平方损失函数，它就是通常所说的残差；对于一般损失函数，它就是残差的近似值。第2(b)步估计回归树叶结点区域，以拟合残差的近似值。第2(c)步利用线性搜索估计叶结点区域的值，使损失函数极小化。第2(d)步更新回归树。第2步得到输出的最终模型$ \hat{f(x)} $ https://www.nituchao.com/algorithm-ml/ml-algorithm-logistic.html 2018-05-17T18:08:00+08:00 逻辑回归，即Logistic Regression，简写为LR。逻辑回归就是这样的一个过程：面对一个回归或者分类问题，选择合适的目标函数（即预测函数，模型），建立代价函数（即损失函数，策略），然后通过优化方法求解出最优的模型参数（算法），然后测试验证我们这个求解模型的好坏。逻辑回归虽然名字里带了"回归"，但是它实际上是一种分类方法，主要用于二分类（即输出只有两种0或1，分别代表两个类别）。算法标签：回归，二类分类，多类分类。模型特点：特征条件下类别的条件概率分布，对数线性模型。模型类型：判别模型。学习模型：逻辑斯蒂函数。学习策略：逻辑斯蒂损失（即交叉熵），从极大似然估计或正则化的极大似然估计推导出。学习算法：梯度下降1 用途在金融领域，逻辑回归由于可以直接输出原始特征的权重，可以认为是一种可解释的白盒模型，常被用来结合WOE转换，做信用评分卡。在医学领域，逻辑回归用于预测在不同的自变量情况下，发生某病或某种情况的概率有多大。2 优缺点优点缺点速度快，适合二分类问题。对数据和场景的适应能力有局限，不如决策树算法适应性那么强。能容易地更新模型，吸收新的数据。 简单易于理解，直接看到各个特证的权重。 3 基本原理根据李航在《统计学习方法》里提出的机器学习过程框架：机器学习=模型 + 策略 + 算法，我们可以将逻辑回归表述为下面的过程：寻找一个合适的预测函数（模型），一般表示为h函数，该函数就是我们需要找的分类函数，它用来拟合特征变量和目标变量。这个过程是非常关键的，需要对数据有一定的分析和探索，知道或者猜测预测函数的"大概"形式，比如是线性函数还是非线性函数。构造一个合适的损失函数（即Cost函数，代价函数，策略），该函数表示预测的输出（h）与目标变量(y)之间的偏差，可以是二者之间的差(h - y)或者其他的形式。综合考虑所有训练数据的"损失"，将Cost求和或者求平均，记为损失函数----J(θ)函数，表示所有训练数据预测值与实际类别的偏差。根据"没有免费的午餐"理论，对于同一个问题而言，所有的模型都是等价的，损失函数实际上表达了人们对于模型的偏好和策略，希望能找到最满意的模型。选择一个合适的算法，计算出可以让损失函数J(θ)函数最小（根据业务需要，也可能是最大）的参数(θ)集合。机器学习处于数学理论和实际问题的交叉点，很多实际问题翻译成数学方程式之后，通常无法直接严格求解。因此，在处理面向实际问题的数学过程时，往往采用近似拟合的方式。选择合适的算法，类似于在数学理论和实际问题之间寻找一个桥梁，而逻辑回归采用的是梯度下降法(Gradient Descent)。4 具体过程4.1 预测函数预测函数使用Logistic函数，原因在于，若要直接通过回归的方法预测二分类问题，y到底是0类还是1类，最好的函数是单位越阶函数。然而单位越阶函数不连续（GLM的必要条件），而Logistic函数在形式上恰好接近于单位越阶函数，而且单调可微。Logistic函数（即Sigmoid函数），函数形式为：$$ g(z) = \frac{1}{1 + e^{-z}} $$对应的函数图形是一个取值在0和1之间的S型曲线：接下来需要确定数据划分的边界类型，对于图2和图3中的两种数据分布，显然图2需要一个线性的边界，而图3需要一个非线性的边界。在逻辑回归算法领域，我们只讨论线性边界的情况。对于线性边界的情况，边界形式如下：$$ \theta_{0} + \theta_{1}x_{1} + ... + \theta_{n}x_{n} = \sum_{i=0}^{n}\theta_{i}x_{i} = \theta^{T}x $$构造预测函数为：$$ h_{\theta}(x) = g(\theta^{T}x) = \frac{1}{1 + e^{-\theta^{T}x}} $$$h_{\theta}(x)$函数的值有特殊的含义，它标示结果取1的概率（究竟为什么其可以表示概率，在后文我们会进一步探讨），因此对于输入x分类结果为类别1和类别0的概率分别为：$$ p(y=1|x;\theta) = h_{\theta}(x) $$$$ p(y=0|x;\theta) = 1 - h_{\theta}(x) $$综合上面的两种情况，我们得到下面的推导：$$ p(y|x;\theta) = (h_{\theta}(x))^{y}(1 - h{\theta}(x))^{1-y} $$4.2 损失函数在逻辑回归模型中，损失函数通过最大似然估计(MLE)来推导，要正确理解最大似然估计，首先要能从本质上区分概率与统计这两个概念，最大似然估计是个统计工具，其目的是用来估计，某个已经发生的事件，背后需要的模型参数。比如，我们拿着硬币抛了10次，得到的数据($x_{0}$)是：反正正反正反正正正反。我们想求的正面概率$\theta$是模型参数，抛硬币模型我们可以假设是二项分布，此过程是统计过程。而在概率过程中，正面概率是0.5，不是未知参数，是已知的常识。从这个角度想，概率与统计恰好是相反的两个过程，关于这个问题，我们后文会进一步讨论。1，我们假设在二类分类中:结果取类1的概率表示为：$$ p(y=1|x;\theta) = h_{\theta}(x) = \frac{1}{1 + e^{-\theta^{T}x}} $$结果取类0的概率表示为：$$ p(y=0|x;\theta) = 1- h_{\theta}(x) = \frac{1}{1+e^{\theta^{T}x}} $$在上面两个公式中，x和概率p（可以理解为标签y）都是观测结果，是已知的事实数据，未知数为参数$\theta$，这个问题便转化成统计问题，使用最大似然估计来处理。2，构建最大似然估计为了求取使得观察结果(x和y)出现的模型参数$\theta$，我们首先构建似然函数:$$ \begin{split} L(\theta) &= \prod_{i=1}^{m}P(y_{i}|x_{i};\theta) \\ &= \prod_{i=1}^{m}(h_{\theta}(x))^{y_{i}}(1-h_{\theta}(x))^{1-y_{i}} \end{split} $$对数似然函数：$$ \begin{split} l(\theta) &= logL(\theta) \\ &= \sum_{i=1}^{m}(y_{i}logh_{\theta}(x_{i}) + (1 - y_{i})log(1 - h_{\theta}(x_{i})) \end{split} $$在对数似然函数$l(\theta)$中，$y_{i}$和$x_{i}$作为观察值，都是已知的，因此$l(\theta)$是$\theta$的函数。到此为止，我们可以用$l(\theta)$作为损失函数，即：$$ \begin{split} J(\theta) &= l(\theta) \\ &= \sum_{i=1}^{m}(y_{i}logh_{\theta}(x_{i}) + (1 - y_{i})log(1 - h_{\theta}(x_{i})) \end{split} $$最大似然估计就是求$J(\theta)$取最大值时的$\theta$，其实这里可以使用梯度上升法求解，求得的$\theta$就是要求的最佳参数。在Andrew Ng的课程中将$J(\theta)$取为下式：，即$$ \begin{split} J(\theta) &= - \frac{1}{m}l(\theta) \\ &= - \frac{1}{m}\sum_{i=1}^{m}(y_{i}logh_{\theta}(x_{i}) + (1 - y_{i})log(1 - h_{\theta}(x_{i})) \end{split} $$此时，要使用梯度下降法求解，其中m表示样本个数，$x_{i}$表示第i个样本的内容，$y_{i}$表示i个样本的标签(取值为0和1)。4.3 学习算法在逻辑回归模型中，我们使用梯度下降法求解损失函数$J(\theta)$的最小值。$\theta$更新过程：$$ \theta_{j} := \theta_{j} - \alpha\frac{\delta}{\delta_{\theta}}J(\theta) $$其中，$\frac{\delta}{\delta_{\theta}}J(\theta)$的推导如下：$$ \begin{split} \frac{\delta}{\delta_{\theta}}J(\theta) &= -\frac{1}{m}\sum_{i=1}^{m}(y_{i}\frac{1}{h_{\theta}(x_{i})}\frac{\delta}{\delta_{\theta}}h_{\theta}(x_{i})-(1-y_{i})\frac{1}{1-h_{\theta}(x_{i})}\frac{\delta}{\delta_{\theta}}h_{\theta}(x_{i})) \\ &= -\frac{1}{m}\sum_{i=1}^{m}(y_{i}\frac{1}{h_{\theta}(x_{i})}-(1-y_{i})\frac{1}{1-h_{\theta}(x_{i})})\frac{\delta}{\delta_{\theta}}h_{\theta}(x_{i}) \\ &= -\frac{1}{m}\sum_{i=1}^{m}(y_{i}\frac{1}{h_{\theta}(x_{i})}-(1-y_{i})\frac{1}{1-h_{\theta}(x_{i}))})h_{\theta}(x_{i})(1-h_{\theta}(x_{i}))\frac{\delta}{\delta_{\theta}}\theta^{T}x_{i} \\ &= -\frac{1}{m}\sum_{i=1}^{m}(y_{i}(1-h_{\theta}(x_{i}) - (1-y_{i})h_{\theta}(x_{i}))x_{i} \\ &= -\frac{1}{m}\sum_{i=1}^{m}(y_{i} - h_{\theta}(x_{i})x_{i} \\ &= \frac{1}{m}\sum_{i=1}^{m}(h_{\theta}(x_{i}) - y_{i})x_{i} \end{split} $$最终，$\theta$更新过程可以写成:$$ \theta_{j} := \theta_{j} - \alpha\frac{1}{m}\sum_{i=1}^{m}(h_{\theta}(x_{i}) - y_{i})x_{i}^{j} $$注意：1) $\alpha$: 代表学习率，用于控制梯度下降的步长。2) m: 代表样本数量。3) j: 代表第j轮梯度下降。4) $\sum_{i=1}^{m}$: 代表在每一轮梯度下降，都要将训练集中所有样本参与计算。4.4 向量化向量化(vectorization)是使用矩阵计算来代替for循环，以简化计算过程，提高效率。向量化过程：约定训练数据的矩阵形式如下，x的每一行为一条训练样本，而每一列为不同的特征取值：$$ x = \left[ \begin{matrix} x_{1} \\ ... \\ x_{m} \end{matrix} \right] = \left[ \begin{matrix} x_{11} & \cdots & x_{1n} \\ \cdots & \ddots & \cdots\\ x_{m1} & \cdots & x_{mn} \end{matrix} \right],y = \left[ \begin{matrix} y_{1} \\ \cdots \\ y_{m} \end{matrix} \right],\theta=\left[ \begin{matrix} \theta_{1} \\ \cdots \\ \theta_{m} \end{matrix} \right] $$$$ A = x·\theta=\left[ \begin{matrix} x_{11} & \cdots & x_{1n} \\ \cdots & \ddots & \cdots\\ x_{m1} & \cdots & x_{mn} \end{matrix} \right]·\left[ \begin{matrix} \theta_{1} \\ \cdots \\ \theta_{m} \end{matrix} \right]=\left[ \begin{matrix} \theta_{1}x_{11} + \theta_{1}x_{11} + ... + \theta_{n}x_{1n} \\ \cdots \\ \theta_{1}x_{m1} + \theta_{1}x_{m1} + ... + \theta_{n}x_{mn} \end{matrix} \right] $$$$ E = h_{\theta}(x) = \left[ \begin{matrix} g(A_{1} - y_{1}) \\ \cdots \\ g(A_{m} - y_{m}) \end{matrix} \right] = \left[ \begin{matrix} e_{1} \\ \cdots \\ e_{m} \end{matrix} \right] = g(A) - y $$g(A)的参数A为一列向量，所以实现g函数时要支持列向量作为参数，并返回列向量。$\theta$更新过程可以改为：$$ \theta := \theta - \alpha\frac{1}{m}\sum_{i=1}{m}(h_{\theta}(x^{i})-y^{i})x^{i}, (j=1...n) $$综上所述，向量化更新后的步骤如下：1, 求A = x·$\theta$2, 求E = g(A) - y3, 求$\theta := \theta - \alpha x^{T}E$4.5 正则化4.5.1 过拟合问题过拟合即是过分拟合了训练数据，使得模型的复杂度提高，泛化能力较差（对未知数据的预测能力），下面左图即为欠拟合，中图为合适的拟合，右图为过拟合。4.5.2 过拟合原因过拟合问题往往源于过多特征。解决方法：1) 减少特征数量（减少特征会失去一些信息，即使特征选取的很好）。可用人工选择要保留的特征。模型选择算法。2) 正则化（特征比较多时比较有效）保留所有特征，但减小$\theta$的大小4.5.3 正则化方法正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项或惩罚项。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化项就越大。正则化项可以取不同形式，在回归问题中取平方损失，就是参数的L2范数，也可以取L1范数。取平方损失时，模型的损失函数变为：$$ J(\theta) = \frac{1}{2m}\sum_{i=1}^m(h_{\theta}(x_{i}-y_{i})^{2}) + \lambda\sum_{j=1}^{n}\theta_{j}^{2} $$lambda是正则化项系数：如果它的值很大，说明对模型的复杂度惩罚大，对拟合数据的损失惩罚小，这样它就不会过分拟合数据，在训练数据上的偏差较大，在未知数据上的方差较小，但是可能出现欠拟合的现象。如果它的值很小，说明比较注重对训练数据的拟合，在训练数据上的偏差会小，但是可能会导致过拟合。正则化后的梯度下降算法$\theta$的更新变为：$$ \theta_{j} := \theta_{j} - \frac{\alpha}{m}\sum_{i=1}^{m}(h_{\theta}(x_{i}) - y_{i})x_{i}^{j} - \frac{\lambda}{m}\theta_{j} $$5 决策本质5.1 为什么是逻辑回归？都说线性回归用来做回归预测，逻辑回归用于做二分类，一个是解决回归问题，一个用于解决分类问题。但很多人问起逻辑回归和线性回归的区别，很多人只知道，逻辑回归就是对线性回归做了一个压缩，将y的阈值从y∈(-∞,+∞)压缩到(0,1)。那么问题来了，问为什么仅仅做了一个简单的压缩，就将回归问题变成了分类问题？这里面蕴涵了什么样的本质？首先要从数据说起，线性回归的样本的输出，都是连续值，y属于(-∞,+∞)，而逻辑回归中y∈{0, 1}，只能取0和1。对于拟合函数也有本质上的差别：线性回归：$f(x) = \theta^{T}x = \theta_{1}x_{1} + \theta_{2}x_{2} + ... + \theta_{n}x_{n}$逻辑回归：$f(x) = p(y = 1|x;\theta) = g(\theta^{T}x)，\text{其中，}g(z) = \frac{1}{1 + e^{-z}}$可以看出，线性回归的拟合函数，的确是对f(x)的输出变量y的拟合，而逻辑回归的拟合函数是对为1类的样本的概率的拟合。5.2 为什么要以1类样本的概率进行拟合呢？首先，要从logistic函数的本质说起。若要直接通过回归的方法去预测二分类问题，y到底是0类还是1类，最好的函数是单位越阶函数。然而单位越阶函数不连续（GLM的必要条件），而Logistic函数恰好接近于单位越阶函数，而且单调可微。于是希望通过该复合函数去拟合分类问题：$$ y = \frac{1}{1 + e^{-\theta^{T}x}} $$于是有：$$ ln\frac{y}{1-y} = \theta^{T}x $$发现，如果我们假设$y=P(y=1|x;\theta)$作为我们的拟合函数，等号左边的表达式的数学意义就是1类和0类的对数几率(log odds)。这个表达式的意思就是：用线性模型的预测结果取逼近1类和0类的几率比。于是，$\theta^Tx = 0$就相当于是1类和0类的决策边界：当$\theta^{T}x > 0$，则有y > 0.5；若$\theta^{T}x -> +∞$，则y -> 1，即y为1类。当$\theta^{T}x < 0$，则有y < 0.5；若$\theta^{T}x -> -∞$，则y -> 0，即y为0类。这个时候就能看出区别来了：在线性回归中$\theta^{T}$为预测值的拟合函数。在逻辑回归中$\theta^{T} = 0$为决策边界。参考https://blog.csdn.net/u010692239/article/details/52345754https://blog.csdn.net/u010976453/article/details/78488279