统计学习方法读记（中）
统计学习方法读记（中）
5、决策树
1、决策与学习：一种基本的分类与回归方法，可以认为是if-then的组合，决策树学习包含3步骤：特征选择、决策树的生成和修剪。决策树的思想来源于Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，一起后来的CART算法。既然叫决策树就是一种对实例进行分类的树形结构，从根节点开始，对实例的某一特征进行测试，根据结果将实例分配到其子节点，这时每一个子节点对应着该特征的一个取值，最种分类从哪个分支处，要看学习准则，如此递归的对实例进行测试分配直到叶节点的类别。决策树可以看成是一个if-then规则的集合，转化成if-then规则的过程是：由决策树的根结点到叶结点的每一条路径构建一条规则，路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树还可以看成是定义在特征空间的划分，根据划分的单元确定类的划分路径（书中给的例子看一简单的用多个if-else判读最终得出结果来理解）。在决策树的分支划分中得到的决策树可能有多个，需要一个与训练数据矛盾较小的决策树，同时有很好的泛化能力，决策树学习的损失函数通常是正则化的极大似然函数，学习策略是以损失函数为目标函数的最小化。
决策树的本质上是从训练数据集中归纳出一组分类准则，学习算法通常是一个递归选择最优特征，并根据该特征对训练数据进行分割，使得对各子集有一个最好的分类过程。（特征空间划分，开始时所有数据都放在根节点，选择一个最优特征，按照这一特征划分子集，使得各子集在有一个在当前条件下最好的分类。如果当前子集已经能确定分类，那就狗仔叶节点否则对子集进行最优特征选择继续分割。影响分支决策的特征当然是好的选择，决定是不是一个好的特征选择通常用信息增益和信息增益比。关于信息相关介绍基本在我的（机器学习（周志华）读书笔记-（四）决策树里做了介绍。再次不再多写,搬运工也累且决策树说难不难说易不易，本人能力有限，只是个人读书笔记。
6、逻辑斯蒂回归与最大熵模型
1、LR回归，是回归算法，但其实际上是一个分类算法。LR回归是在线性回归模型的基础上使用sigmoid函数，将线性模型 wTx 的结果压缩到[0,1]之间，使其拥有概率意义。其本质仍然是一个线性模型，实现相对简单。LR回归属于概率性判别式模型，LR模型是有概率意义且LR回归并没有对数据的分布进行建模，即LR模型并不知道数据的具体分布，而是直接将判别函数或者是分类超平面求解了出来。首先，需要对 logistic distribution （逻辑斯蒂分布）这个分布的密度函数和分布函数如下：
μ是位置参数，而s 是形状参数。逻辑回归分布密度函数与分布函数如下：
逻辑斯蒂分布的概率分布函数自中心附近增长速度较快，而在两端的增长速度相对较慢。当μ=0,s=1时，逻辑斯蒂分布的概率分布函数就是我们常说的sigmoid函数。分类算法都是求解p(Ck|x)而逻辑斯蒂回归模型就是用当μ=0,s=1时的逻辑斯蒂分布的概率分布函数：sigmoid函数，对p(Ck|x)进行建模所得到的模型对于二分类的逻辑斯蒂回归模型有：
一个事件的几率是指该事件发生的概率与不发生的比值，即在逻辑斯蒂回归模型中输出Y=1的对数几率是输入x的线性函数。逻辑斯蒂回归模型的定义式P(Y=1|x)中可以将线性函数w⋅x转换为概率，这时线性函数的值越接近正无穷，概率值就越接近1；线性函数的值越接近负无穷，概率值就接近0。应用极大似然法进行参数估计获得逻辑斯蒂回归模型。（极大似然估计：极大似然估计提供了一种给定观察数据来评估模型参数的方法以别人博客中例子解释：假如有一个罐子，里面有黑白两种颜色数量未知的球，想知道罐中白球和黑球的比例，但不能把罐中的球全部拿出来数。现在可以每次任意从已经摇匀的罐中拿一个球出来，记录球的颜色，然后把拿出来的球再放回罐中。这个过程可以重复，通过记录的球的颜色来估计罐中黑白球的比例。假如在前面的一百次重复记录中，有七十次是白球，请问罐中白球所占的比例最有可能是多少？很多人马上就有答案了：70%。而其后的理论支撑是什么呢？假设罐中白球的比例是p，那么黑球的比例就是1-p。因为每抽一个球出来，在记录颜色之后把抽出的球放回了罐中并摇匀，所以每次抽出来的球的颜 色服从同一独立分布。这里我们把一次抽出来球的颜色称为一次抽样。题目中在一百次抽样中，七十次是白球的,三十次为黑球事件的概率是P(样本结果|Model)。如果第一次抽象的结果记为x1,第二次抽样的结果记为x2....那么样本结果为(x1,x2.....,x100)。这样，我们可以得到如下表达式：P(样本结果|Model)=P(x1,x2,…,x100|Model)= P(x1|Mel)P(x2|M)…P(x100|M)=p^70(1-p)^30.我们已经有了观察样本结果出现的概率表达式了。那么我们要求的模型的参数，也就是求的式中的p。那么我们怎么来求这个p呢？不同的p，直接导致P（样本结果|Model）的不同。好的，我们的p实际上是有无数多种分布的。极大似然估计应该按照什么原则去选取这个分布呢？答：采取的方法是让这个样本结果出现的可能性最大，也就是使得p^70(1-p)^30值最大，那么我们就可以看成是p的方程，求导即可！那么既然事情已经发生了，为什么不让这个出现的结果的可能性最大呢？这也就是最大似然估计的核心。我们想办法让观察样本出现的概率最大，转换为数学问题就是使得：p^70(1-p)^30最大，这太简单了，未知数只有一个p，我们令其导数为0，即可求出p为70%，与我们一开始认为的70%是一致的。其中蕴含着我们的数学思想在里面）
2、最大熵模型：熵的本质是一个系统“内在的混乱程度”。最大熵原理是概率模型学习的一个准则，在所有的概率模型分布中熵最大的模型就是最好的模型，通常用概率调价决定概率模型的集合，最大熵原理认为要选择概率模型必须首先选择满足约束条件在没有更多信息的情况下，那些不确定的部分都是等可能的。逻辑斯蒂回归模型、最大熵模型学习归结为以似然函数为目标的最优化问题，通常通过迭代算法求解，为了保证全局最优常用的改进算法迭代尺度、梯度下降、牛顿法或拟牛顿法。
7、支持向量机
1、SVM一种二类分类模型，基本模型是定义在特征空间上的间隔最大化的线性分类器。间隔最大化使他有别于感知机，有着核技术使得他实质上是非线性分类器，SVM的学习算法是求解凸二次规划的最优化算法。线性可分的二分类的例子：一个二维平面(一个超平面，在二维空间中的例子就是一条直线)，如下图所示平面上有两种不同的点代表不同的两类，红颜色的线表示一个可分的超平面将两个类别分开。
分类决策函数y(w.x+b)=0,分类决策函数f(x)=sign（wx+b）。感知机用误差分类最小的策略得到无穷多个分类离超平面，SVM用利用间隔最大化求最优分类平面解只有一个。
2、函数间隔和几何间隔：一个点（类）到分类超平面的距离表示分类的确信程度，函数间隔的定义，超平面（w，b）关于样本点（x，y）函数间隔v=y（w×x+b），函数距离只是便面数值上的距离，假如我们让w和b等比例变为2w和2b，计算距离值变大，但实际超平面并没有改变，函数距离变为原来的两倍，因此就会对函数间距加以约束如规范化||w||=1，使得间距确定即变成几何间距。一般当样本点被超平面正确分类时点到平面的几何距离计算为：
关于训练集的正确划分类别的超平面使得几何间距最大化的超平面就是我们想要求得的，在线性可分的情况下这个最大化的平面是唯一的，通过等式变形变为求解凸二次规划的问题即约束最优化问题。
3、支持向量和边界间隔：在线性可分的情况下，训练集的样本点中与分离超平面距离最近的实例称为支持向量，对于类别（H1）y=+1的正例点支持向量在超平面w*x+b=1上，同理使之等于-1的点负实例点在H2超平面上，这些点都是支持向量。
两个超平面平行，并且没有超平面落在他们之间，我们找的超平面在两个平面之间位于*，两条长带的宽度称为间隔间隔依赖于超平面的法向量w等于2/||w||，H1与H2称为间隔边界。在决定分离超平面的时候只有支持向量起作用其他点不起作用，正因此将这种分类模型称为支持向量机，支持向量的个数一般很少，所以支持向量机由很少的”重要的“训练样本确定。拉格朗日算子对偶算法等参考https://www.cnblogs.com/little-YTMM/p/5547642.html
支持向量机扩展到非线性可分的数据时，要解决的问题其实就是解决掉一些数据奇异点其他的都是线性可分的，反映在数学函数上就是不满足于函数间隔大于等于1的约束条件。所以引进了一个松弛变量使之加上松弛变量后大于等于1，核函数的使用将非线性可分的数据通过映射变化到一个可线性的空间在划分（拉格朗日算子，对偶法，核函数具体计算不是甚清楚，清晰了回头再增加个人笔记）
8、提升方法
提升方法是一种综合策略，书里重点讲了AdaBoost算法，文中先从概念的弱学习算法等价于强学习算的理论，然后讲到怎样从一系列的弱学习算法模型中进行组合构成强学习分类器。一般的方法是改变训练数据的概率分布（训练数据的权值分布），得到一系列的弱分类器模型。那么就会涉及到如何改变训练数据权值分布和如何组合弱分类器。改变训练数据的权值一般是提升那些被前一轮分类错误的样本权值，降低相应正确样本的权值，关于组合弱分类器的方法AdaBoost一般采用加权多数表决的方法。加大分类误差率小的分类器权值是在表决中占有一定地位。算法过程-输入：训练数集T其中xi∈Rn,yi∈{−1,+1};某个弱学习算法g(x)。输出：最终的分类器G(x)：步骤如下：
1、初始化训练数据的权值D1={w11,...,w1i,...w1N}，w1i=1/N 。2、a)使用具有权值分布Dm的训练数据集学习，得到基本分类器gm(x)，b)计算分类误差率，em=P(gm(xi)≠yi)=∑Ni=1wmiI (gm(xi)≠yi)，c)计算gm(x)的系数， d)更新训练数据的权值分布，w(m+1)i=wmi / Zmexp(−α yi gm (xi ) )),其中Zm是规范化因子目的是使得Dm+1成为一个概率分布；（当分类错误时，−αyigm(xi)=α;当分类争正确时，−αyigm(xi)=−α，故错误的分类样本权值将增大，正确分类样本的权值将减小）。3、通过分类器的线性组合获得最终的分类器G(x)=sign(∑Ni=1αmGm(x)).
Adaboost算法还有另一种解释，即：可以认为Adaboost算法是“模型为加法模型、损失函数为指数函数、学习算法为前向分布算法”时的二类分类学习方法，对于加法模型，在给定训练数据及损失函数L(y, f(x))的条件下，学习加法模型f(x)就成为经验风险极小化损失函数极小化问题，加法模型如下：其中，b(x; r)为基函数，r是基函数的参数，βm为基函数的系数
提升树：提升树是以决策树为弱分类器的提升方法，通常使用CART树，提升方法实际采用加法模型（基函数的线性组合）和前向分步算法，以决策树为基函数的提升方法称为提升树。
9、EM算法
先说一下极大似然和最大似然：极大似然的思想：某位同学与一位猎人一起外出打猎，一只野兔从前方窜过。一声枪响野兔倒下，如果要你推测这一发命中的子弹是谁打的？你会自然觉得只发一枪便打中由于猎人命中的概率一般大于这位同学命中的概率，看来这一枪是猎人射中的。因此极大似然估计只是一种概率论在统计学中的应用，它是参数估计的方法之一。说的是已知某个随机样本满足某种概率分布，但是其中具体的参数不清楚，参数估计就是通过若干次实验，观察其结果，利用结果推出参数的大概值。最大似然估计是建立在这样的思想上：已知某个参数能使这个样本出现的概率值最大，我们当然不会再去选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值。最大似然估计你可以把它看作是一个反推。多数情况下我们是根据已知条件来推算结果，而最大似然估计是已经知道了结果，然后寻求使该结果出现的可能性最大的条件，以此作为估计值。比如，如果其他条件一定的话，抽烟者发生肺癌的危险时不抽烟者的5倍，那么如果现在我已经知道有个人是肺癌，我想问你这个人抽烟还是不抽烟。你怎么判断？我相信你更有可能会说，这个人抽烟。为什么？这就是“最大可能”因为你只知道抽烟者发生肺癌的危险时不抽烟者的5倍，只能说他“最有可能”是抽烟的，“他是抽烟的”这一估计值才是“最有可能”得到“肺癌”这样的结果。这就是最大似然估计。
求最大似然函数估计值的一般步骤：（1）写出似然函数；（2）对似然函数取对数，并整理；（3）求导数，令导数为0，得到似然方程；（4）解似然方程，得到的参数即为所求
假设我们有一个样本集{x(1),…,x(m)}，包含m个独立的样本。但每个样本i对应的类别z(i)是未知的（相当于聚类），也即隐含变量。故我们需要估计概率模型p(x,z)的参数θ，但是由于里面包含隐含变量z，所以很难用最大似然求解，但如果z知道了，那我们就很容易求解了。 对于参数估计，我们本质上还是想获得一个使似然函数最大化的那个参数θ，现在与最大似然不同的只是似然函数式中多了一个未知的变量z，见下式（1）。也就是说我们的目标是找到适合的θ和z让L(θ)最大。那我们也许会想，你就是多了一个未知的变量而已啊，我也可以分别对未知的θ和z分别求偏导，再令其等于0，求解出来不也一样吗？
本质上我们是需要最大化（1）式（对（1）式，我们回忆下联合概率密度下某个变量的边缘概率密度函数的求解，注意这里z也是随机变量。对每一个样本i的所有可能类别z求等式右边的联合概率密度函数和，也就得到等式左边为随机变量x的边缘概率密度），也就是似然函数，但是可以看到里面有“和的对数”，求导后形式会非常复杂（自己可以想象下log(f1(x)+ f2(x)+ f3(x)+…)复合函数的求导），所以很难求解得到未知参数z和θ。那OK，我们可否对（1）式做一些改变呢？我们看（2）式，（2）式只是分子分母同乘以一个相等的函数，还是有“和的对数”啊，还是求解不了，那为什么要这么做呢？咱们先不管，看（3）式，发现（3）式变成了“对数的和”，那这样求导就容易了。我们注意点，还发现等号变成了不等号，为什么能这么变呢？这就是Jensen不等式的大显神威的地方参考点击打开链接