第五讲：决策树+随机森林+AdaBoost（上）
主要内容
3 逻辑斯蒂回归（下）
3.5 逻辑斯谛回归和凸优化问题
3.5.1 什么是凸优化问题
3.5.2 为什么说逻辑斯谛回归是一个凸优化问题
3.6 多项逻辑斯谛回归
3.6.1 模型
3.6.2 策略
3.6.3 算法
3.6.4 正则化
3.7 对比感知机、SVM和逻辑斯谛回归
3.7.1 损失函数
3.7.2 分离超平面
3.7.3 算法性能
4 集成学习（上）
4.1 决策树
4.1.1 CRAT框架
4.1.2 模型
4.1.3 特征选择
3.5 逻辑斯谛回归和凸优化问题
3.5.1 什么是凸优化问题
在机器学习中，我们经常会遇到凸优化问题。那么什么叫凸优化问题，凸优化又有什么作用呢？
凸优化是指一种比较特殊的优化，是指求取最小值的目标函数为凸函数的一类优化问题。凸优化问题的形式是：，其中f(x)是凸函数，可行域S是凸集。此外还有个等价形式：
其中f(x)和所有的限制函数gi(x)都必须是凸函数。
那么什么是凸函数，什么是凸集呢？所谓的凸集指的是如果对于一个集合S中的任意两个点A和B，这两个点的连线AB也在S内，那么S就是一个凸集。换句话说，凸集不能有洞，不能有任何凹陷。
而凸函数是指同时满足以下条件的函数：
（1）它的定义域是凸集
（2）对于其定义域中的任意两点x1，x2，对任意0 ≤ α ≤ 1，f ( αx1 + (1−α) x2 ) ≤ α f( x1 ) + ( 1−α ) f ( x2 )，那么这个函数f就是凸函数。凸优化问题有个很好的性质，就是它的局部最优解一定是全局最优解。
3.5.2 为什么说逻辑斯谛回归是一个凸优化问题
根据上面的内容我们知道，一个凸优化问题要满足可行域是凸集并且目标函数为凸函数两个条件。对于逻辑斯谛回归，参数w可以取任意值，可行域是整个实数空间，很明显它是一个凸集。然后我们对损失函数进行二阶求导。
求一阶导：
求二阶导：
接下来我们令
我们可以得到：
因为B是一个n阶对角矩阵，很容易得到，因此
是半正定的，即L(w)的Hesse矩阵是半正定的，根据凸函数的性质，如果其Hesse矩阵（二阶偏导）是半正定的，那么该损失函数是一个凸函数。
逻辑斯谛回归的可行域是凸集，损失函数是凸函数，所以它是一个凸优化问题。
3.6 多项逻辑斯谛回归
3.6.1 模型
上一讲介绍的逻辑斯谛回归模型是二项类分类模型，用于二类分类。我们可以将其推广为多项逻辑斯谛回归模型，用于多分类。在多项逻辑斯谛回归中，我们解决的是多分类问题，因此离散型随机变量Y可以取值{1，2，…，K}，这样我们可以得到多项逻辑斯谛回归的模型：
因为它满足，所以我们也可以将它写成另外一种形式：
3.6.2 策略
为了使二分类的逻辑斯谛回归扩展到多分类问题，我们将sigmoid函数，换成softmax函数。
softmax(x)=（其中，ei代表第i类，K代表总共的类别数），应用到多项逻辑斯谛回归模型中是：
应用极大似然估计，然后取负对数变成极小化问题，因此我们可以得到多项逻辑斯谛回归的损失函数：
3.6.3 算法
和二分类的逻辑斯谛回归类似，我们也可以使用随机梯度下降的算法对其进行优化：
3.6.4 正则化
但是，softmax回归有一个不同寻常的特点，它有一个“冗余”的参数集。假设我们从参数向量wk中减去向量ψ，这时每一个wk都变成了wk – ψ(k=1，… ，K)。此时的假设函数变成了下面这个式子：
换句话说，从wk中减去ψ完全不影响假设函数的预测结果。这表明前面的 softmax 回归模型中存在冗余的参数。更正式一点来说，softmax模型被过度参数化了。对于任意一个用于拟合数据的假设函数，可以求出多组参数值，这些参数得到的是完全相同的假设函数hw。进一步而言，如果参数(w1，w2，… ，wk)是价函数J(w)的极小值点，那么(w1 - ψ，w2 - ψ，… ，wk - ψ)同样也是它的极小值点，其中ψ可以为任意向量。因此使J(w)最小化的解不是唯一的。由于J(w)仍然是一个凸函数，因此梯度下降时不会遇到局部最优解的问题。但是Hessian矩阵是奇异的（不可逆的），这会直接导致采用牛顿法优化就遇到数值计算的问题。
注意，当ψ= w1时，我们总是可以将w1替换为（即替换为全零向量），并且这种变换不会影响假设函数。因此我们可以去掉参数向量w1（或者其他wk中的任意一个）而不影响假设函数的表达能力。实际上，与其优化全部k(n+1)个参数(w1，w2，… ，wk)，我们可以令
，只优化剩余的(k-1)(n+1)个参数，这样算法依然能够正常工作。但在实际应用中，为了使算法实现更简单清楚，我们往往保留所有参数(w1，w2，… ，wn)，而不任意地将某一参数设置为0。但此时我们需要对代价函数做一个改动：加入权重衰减，权重衰减可以解决softmax回归的参数冗余所带来的数值问题。
我们通过添加一个权重衰减项来修改损失函数，这个衰减项会惩罚过大的参数值，现在我们的损失函数变为：
有了这个权重衰减项以后 (λ>0)，代价函数就变成了严格的凸函数，这样就可以保证得到唯一的解,此时的 Hessian矩阵变为可逆矩阵。并且因为J(θ)是凸函数，梯度下降法和 L-BFGS 等算法可以保证收敛到全局最优解。再通过最小化J(w)，我们就能实现一个可用的softmax回归模型。
3.7 对比感知机、SVM和逻辑斯谛回归
感知机、SVM和逻辑斯谛回归三者既有联系也有区别。联系在于这三者都是线性分类器，而且SVM和Logistic都是由感知器发展改善而来的。但是三者在损失函数，分离超平面和算法性能上都有所区别。
3.7.1 损失函数
感知机、SVM和逻辑斯谛回归三者的损失函数不同，后两者的损失函数的目的都是增加对分类影响较大的数据点的权重，SVM的处理方法是只考虑support vectors，也就是和分类最相关的少数点，去学习分类器。而逻辑回归通过非线性映射，大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重。
感知机的损失函数：
SVM的损失函数：
逻辑斯谛回归的损失函数：
下图中红色的曲线代表Logistic回归的损失函数，绿色的线代表SVM的损失函数。
3.7.2 分离超平面
感知机、SVM和逻辑斯谛回归同样都用到了分离超平面，但是如何利用这个分离超平面三者有所区别。
❖ 感知机模型将分离超平面对数据分割，寻找出所有错误的分类点，计算这些点到超平面的距离，使这一距离和最小化，也就是说感知机模型的最优化问题是使得错误分类点到超平面距离之和最小化。
❖支持向量机的最优化问题是最大化样本点到分离超平面的最小距离。
❖逻辑斯谛回归是将分离超平面作为sigmoid函数的自变量进行输入，获得了样本点被分为正例和反例的条件概率，然后用极大似然估计极大化这个后验概率分布，也就是说逻辑斯谛回归模型的最优化问题是极大似然估计样本的后验概率分布。
3.7.3 算法性能
感知机模型无法加入核方法映射到高维，而逻辑斯谛回归和支持向量机都能通过核方法对低维不可分高维可分的数据集进行分类。感知机模型和支持向量机模型可以通过二分类方法的扩展处理多分类问题，方法是对每一类都产生一个分离超平面区分该类和其他类的样本。支持向量机计算相对复杂，但因为其实凸优化问题，因此算法一定可以收敛。
逻辑斯谛回归相比感知机多了一层sigmoid函数的计算，计算仍然十分高效。其在线性可分的数据集中不能收敛但可以加入正则化来使算法收敛，在线性不可分的数据集中可以较好的收敛。逻辑斯谛回归进行多分类问题通过选择最后一个类为基准类，构造k-1个分离超平面（分类器）。k-1个分类器计算sigmoid函数值求和在加1作为投票法的分母，每个分类器计算的sigmoid函数值作为分子进行投票，选出最大的分配到该类别。
4 集成学习（上）
集成学习是指通过训练多个分类器，然后将这些分类器组合起来，来获得比单个分类器更优的性能（比最好的那个分类器还要好）。如果每个分类器都是同种类型的（比如都是决策树或者都是SVM等等），那么这些单个的分类器我们称为基学习器；如果集成中包含不同类型的分类器，这样的集成是异质的。需要注意的是，这些单个的分类器性能不一定要很好，只需要比随机猜测好就可以。在我们一般的经验中，如果把好的东西与坏的东西掺杂在一起，那么结果通常是比最坏的要好但比最好的要差一些，但是集成学习可以获得比最好的单一学习器更好的性能。
集成学习的发展历史我们可以从下图中简单了解。
4.1 决策树
4.1.1 CRAT框架
CART使用基尼指数来选择划分。基尼指数反映的是从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此基尼指数越少，数据集D包含的信息量越少。CART在候选特征集中选取一个特征，使得划分后基尼指数最小。
分类举例：
我们根据决策树，将下面的区域分成四块。分别是X2≤0.7,X1≤-1.4; X2≤0.7,X1＞-1.4; X2＞0.7,X1≤-0.6; X2＞0.7,X1＞-0.6。
回归举例：
4.1.2 模型
分类决策树模型是一种描述对实例进行分类的树形结构，决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。
我们可以将决策树看成一个if-then规则的集合，转换成if-then规则的过程：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。
4.1.3 特征选择
特征选择在于选取对训练数据具有分类能力的特征，通常特征选择的准则是信息增益或信息增益比。在学习信息增益之前，我们给出熵、联合熵和条件熵的定义。
设有随机变量(X,Y)，其联合概率分布为：
P(X=xi，Y=yi)=Pi，j，i=1，2，…，n；j=1，2，…，m
随机变量熵X的熵定义为：
所以联合熵的定义为：
熵H(p)随概率p变化的曲线如下图所示：
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。
reference:
[1] 李航 . 统计学习方法 . 清华大学出版社，北京(2012)
[2] 周志华 . 机器学习 . 清华大学出版社，北京(2016)