机器学习笔记复习整理（更新中）
本文主要整理，之前在学习吴恩达机器学习和李航的统计学习方法时的部分笔记。
统计学习方法书，主要讨论监督学习问题。
一、统计学习方法概论
统计学习方法是由模型、策略和算法构成的。
统计学习方法是由模型、策略和算法构成的。
模型：表示输入到输出的映射，可以是条件概率分布或者决策函数。所有可能的模型的集合称为假设空间。
策略：通过确定学习策略，进而确定按怎样的准则学习或选择最优的模型，即从假设空间中选择最优的模型。首先确定损失函数来度量模型预测错误的程度，再希望损失最小。也可以加入正则项。
算法：策略将统计学习问题归结为数学上的最优化问题，统计学习的算法则是求解最优化问题的算法。同时，因为往往问题显式的解析解（有严格公式，确定的解）不存在，就需要用数值计算的方法求取近似解。
期望损失（风险函数）与经验损失（经验风险）：
期望损失：理论上模型关于联合分布的平均意义下的损失。
经验损失：关于训练数据集的平均损失。
期望损失所代表的更为广义，经验损失是针对训练集而言。当样本容量N趋于无穷时，经验风险趋于期望风险。
经验风险最小化与结构风险最小化：
经验风险最小化的策略认为，经验风险最小的模型是最优的模型。
当样本容量足够大时，经验风险最小化能保证有很好的学习效果。
结构风险最小化，则是为了防止过拟合才提出来的。
结构风险最小化等价于正则化，定义如下：
结构风险最小化的策略认为，结构风险最小的模型是最优的模型。
结构风险小，需要经验风险和模型复杂度同时小。
结构风险小的模型，往往对训练数据以及未知的测试数据都有较好的预测。（防止过拟合，泛化效果好）
在学习时，要防止过拟合，进行最优的模型选择，即选择复杂度适当的模型，以达到使测试误差最小的学习目的。
下面介绍两种常用的模型选择方法：正则化和交叉验证。
正则化：
L1：
L2：
正则化的作用是选择经验风险与模型复杂度同时较小的模型。
交叉验证：
当数据充足时，可以将数据集分成训练集、验证集、测试集三个部分。
其中，验证集用来选择模型，选择对验证集有最小预测误差的模型。
而当数据量不足时，则需采用交叉验证法。
交叉验证的基本思想是重复地使用数据，把给定的数据进行切分，切分的数据集组合为训练集和测试集。
都是选测试集的误差最低的模型，只不过测试误差的求法不同。
1、简单交叉验证（留出法）：
数据分成两部分，一部分作为训练集，一部分作为测试集。
2、S折交叉验证：
将数据分为S个互不相交的大小相同的子集，然后利用S-1个子集的数据训练模型，余下的做测试。取S次的测试误差平均值。
3、留一交叉验证：
S折的特殊情况，S=N。
生成模型与判别模型：
生成方法学习得到生成模型。
生成方法由数据学习联合概率分布，然后求出条件概率分布作为预测的模型。
之所以称为生成模型，是因为模型表示了，给定输入x产生输出y的生成关系。
判别方法学习得到判别模型。
判别方法由数据直接学习决策函数或者条件概率分布作为预测的模型。
分类问题：
TP：实际为正类，预测为正类。
TP：实际为正类，预测为正类。
FP：实际为负类，预测为正类。
TN：实际为负类，预测为负类。
FN：实际为正类，预测为负类。
（预测为什么看最后一个字母）
精确率（查准率）：
精确率（查准率）：
预测出的正例有多少是正确的。
召回率（查全率）：
有多少正例被正确预测出来。（对正例的覆盖能力）
F1值：
是精确率和召回率的调和均值
准确率：（不再是指针某一个类，描述整个预测）
回归问题：回归问题的学等价于函数拟合：选择一条函数曲线使其很好地拟合已知数据且很好地预测未知数据。
标注问题：略。
二、感知机模型（超平面）
感知机模型可理解为没有隐层的，最简单的神经网络。
感知机模型可理解为没有隐层的，最简单的神经网络。
模型：
损失函数：
算法：
算法的对偶形式：
Gram矩阵：
三、KNN（分类与回归）
KNN是监督学习，K-means不是。
k近领的三个基本要素： k值的选择，距离度量，分类决策规则。
k近领使用的模型，实际上对特征空间的划分。
k近领没有显示的学习过程。
对于新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数实例属于哪个类，就把该输入实例分为哪个类。
k值的选择：
选择较小k值，近似误差小，只有与输入实例相近的训练实例才会起作用。
但估计误差大，预测结果会对临近的点非常敏感，一旦出现噪声，则预测错误。
选择较大k值，估计误差小，增加鲁棒。但缺点是近似误差大，此时与实例较远的不相近的点也会起作用。
距离度量：
不同的距离度量，所确定的最近邻点是不同的。
k近邻法的搜索，最简单的实现是线性扫描。这时要计算输入实例与每一个训练实例的距离。
当训练集很大时，计算非常耗时，这种方法是不可行的。
为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。
比如kd树：
构建平衡kd树，搜索kd树：先递归向下确定第一个叶结点，再递归向上确定最近邻点。
具体是，在每往上一级的对应的另一子节点区域，搜寻是否有相交，有的话则进行最近邻搜索，否则退回。
当退回到根节点时，搜索结束。最后的“当前最近点”即为x的最近邻点。
因为有相交才搜寻，搜也只搜相交部分，所以减少了搜索的计算量。
四、Kmeans
对于监督学习，其训练样本带有标记信息。而非监督学习，训练样本的标记信息则是未知的。
Kmeans聚类算法属于非监督学习。
kmeans算法又名k均值算法。其算法思想大致为：先从样本集中随机选取k个样本作为簇中心，并计算所有样本与这 k个“簇中心”的距离，对于每一个样本，将其划分到与其距离最近的“簇中心”所在的簇中，对于新的簇计算各个簇的新的“簇中心”。
根据以上描述，我们大致可以猜测到实现kmeans算法的主要三点：
（1）簇个数 k的选择
（2）各个样本点到“簇中心”的距离：类似KNN算法。
（3）根据新划分的簇，更新“簇中心”
根据以上描述，我们大致可以猜测到实现kmeans算法的主要三点：
（1）簇个数 k的选择
（2）各个样本点到“簇中心”的距离：类似KNN算法。
（3）根据新划分的簇，更新“簇中心”
算法分为两个步骤，第一个for循环是赋值步骤，即：对于每一个样例，计算其应该属于的类。第二个for循环是聚类中心的移动，即：对于每一个类K，重新计算该类的质心。
k值的选择：
簇的数量的选择，通常有两种方法，均要求 
：
人工选择：根据需求或者已知的知识，进行人工选择簇的数量。
肘部法则：如下图所示（图源：吴恩达机器学习），尝试不同的 
，选择变化率明显变缓的“肘部点。
簇中心初始化：
在运行K-均值算法的之前，我们首先要随机初始化所有的聚类中心点，下面介绍怎样做：
1.我们应该选择K<m，即聚类中心点的个数要小于所有训练集实例的数量
2.随机选择K个训练实例，然后令K个聚类中心分别与这K个训练实例相等
K-均值的一个问题在于，它有可能会停留在一个局部最小值处，而这取决于初始化的情况。
在运行K-均值算法的之前，我们首先要随机初始化所有的聚类中心点，下面介绍怎样做：
1.我们应该选择K<m，即聚类中心点的个数要小于所有训练集实例的数量
2.随机选择K个训练实例，然后令K个聚类中心分别与这K个训练实例相等
K-均值的一个问题在于，它有可能会停留在一个局部最小值处，而这取决于初始化的情况。
策略：
回顾刚才给出的: K-均值迭代算法，我们知道，第一个循环是用于减小
引起的代价，而第二个循环则是用于减小
引起的代价。
引起的代价，而第二个循环则是用于减小引起的代价。 迭代的过程一定会是每一次迭代都在减小代价函数，不然便是出现了错误。
五、朴素贝叶斯
贝叶斯定理：
先验概率：是指根据以往经验和分析得到事情发生的概率。
后验概率：事情已经发生，要求这件事情发生的原因是由某个因素引起的可能性的大小。由果推因。 
朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。
朴素贝叶斯通过训练数据集学习先验概率分布及条件概率分布，进而学习联合概率分布。
因此，朴素贝叶斯实际上学习到生成数据的机制，所以属于生成模型。
1、特征条件独立假设：
用于分类的特征在类确定的条件下都是条件独立的。
2、通过贝叶斯公式和学习的模型，计算后验概率分布，将后验概率最大的类作为x的类输出。
参数估计：
1、极大似然估计（MLE）
极大似然估计，通俗理解来说，就是利用已知的样本结果信息，反推最具有可能（最大概率）导致这些样本结果出现的模型参数值！
换句话说，极大似然估计提供了一种给定观察数据来评估模型参数的方法，即：“模型已定，参数未知”。
具体体现在题目，或者说训练模型中，就是用小样本的分布，来似然估计出模型的参数，并以此来模拟大样本的分布。
2、贝叶斯估计
六、决策树（分类与回归）
分类决策树模型是一种描述对实例进行分类的树形结构。
决策树由结点和有向边组成。
结点有两种类型：内部节点和叶结点。
内部结点表示一个特征或者属性。
叶结点表示一个类。
模型：
决策树学习本质上是从训练数据集中归纳出一组分类规则。
而从另一个角度看，决策树学习则是由训练数据集估计条件概率模型。
决策树学习的本质，是从训练数据集上，归纳出一组分类规则。
或者是由训练数据集估计条件概率模型。
且无论树或者是概率模型，都希望不仅对训练数据有很好的拟合，且对未知数据有很好的预测泛化能力。
策略：
决策树的损失函数通常是正则化的极大似然函数。
决策树学习的策略是以损失函数为目标函数的最小化。
算法：决策树学习的算法包括特征选择、决策树的生成与决策树的剪枝过程。
决策树的学习的算法有ID3、C4.5、CART。
具体的：
1、特征选择：
通常是递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类。（分割、分类）
如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去。
如果还要子节点不能被分类，那么就对这些子集选择新的最优特征，继续对其进行分类构建相应的结点。
如此递归下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。
最后每个数据集子集都被分到叶结点上，即都有了明确的类，这就生成了一棵决策树。
这一过程对应这对特征空间的划分，也对应着决策树的构建。
特征选择在于选取对训练数据具有分类能力的特征。通常特征选择的准则是信息增益或信息增益比。
信息增益&信息增益比：
条件熵表示在已知随机变量X的条件下，随机变量Y的不确定性，定义如下：
当熵和条件熵中的概率由数据估计得到时，就分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。
信息增益(information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少程度。定义如下：
在这里，信息增益表示了由于特征A而使得对数据集D的分类的不确定性减少的程度。
具体如何根据信息增益选择特征呢？用这个方法：对训练数据集(或子集)D，计算其每个特征的信息增益，比较它们的大小，选择信息增益最大的特征。
具体计算公式：
信息增益比是信息增益关于特征的值的熵之比，具体如下：
2、决策树生成：
3、剪枝：
对未知数据没有很好的分类能力，即可能发生过拟合现象。
需要自下向上进行剪枝，将树变得简单，从而使它具有更好的泛化能力。
具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。
七、逻辑回归与最大熵模型
1、逻辑斯谛回归
首先，逻辑回归不是回归，而是分类问题。
其和单层感知机类似，都没有隐层， 单单一个神经元。但感知机的激活函数是f(x)=sign(wx+b)。
公式：（以下公式是，逻辑回归输出的，当前样本属于正样本的概率）
损失函数：
logit仅仅是最大化似然函数，没有最小、最大化后验概率。
算法：
通常采用的方法是梯度下降法与拟牛顿法。
2、最大熵模型
八、SVM
可分为三类： 线性可分支持向量机、线性支持向量机、非线性支持向量机
将输入从输入空间，映射成特征空间中的特征向量。
支持向量机的学习是在特征空间中进行的。
模型：二分类模型，是定义在特征空间上的间隔最大的线性分类器。
策略：间隔最大化。
算法：求解凸二次规划的最优化算法。
函数间隔：
一方面，根据点到直线距离公式：
，可知
可以表示点x距离超平面的远近。
另一方面，wx+b的符号与类标记y的符号是否一致，能够表示分类是否正确。
所以 )
可以用来表示分类的正确性及确信度，这就是函数间隔。
超平面与所有样本点的函数间隔的最小值，即为超平面与整个数据集的函数间隔。
几何间隔：
几何间隔是对函数间隔进行归一化的结果。
并且，当正确分类，即数值为正时。几何间隔即为点到超平面的距离。
对于样本点的几何间隔，与对于数据集的几何间隔的定于，与函数间隔类似，都是取最小值。
两者关系：
当||w||等于1的时候，函数间隔就和几何间隔一样。
间隔最大化的直观解释：
对训练数据集找到几何间隔（本已是所有几何间隔最小）最大的超平面，意味着以充分大的确信度对训练数据进行分类。
也就是说，不仅仅是将数据分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将他们分开。
线性可分支持向量机：
也叫硬间隔支持向量机。当训练数据线性可分时，通过硬间隔最大化策略，求解最优分离超平面，解是唯一的。
而感知机通过误分类最小的策略进行学习，解有无穷多个。
模型： %3Dsign(w%5E%7B*%7Dx%2Bb%5E%7B*%7D))
策略：间隔最大化
算法：最优化算法
支持向量：
在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。（即对于数据集的几何间隔）
间隔边界：
最大间隔法的对偶算法：
线性支持向量机：
策略：
合页损失函数：
图中有0-1损失、感知机损失（虚线）、合页损失三种。
1）0-1损失
当样本被正确分类时，损失为0；当样本被错误分类时，损失为1。
2）感知机损失函数
当样本被正确分类时，损失为0；当样本被错误分类时，损失为-y(wx+b)。
3）合页损失函数
当样本被正确分类且函数间隔大于1时，合页损失才是0，否则损失是1-y(wx+b)。
当样本被正确分类时，损失为0；当样本被错误分类时，损失为1。
2）感知机损失函数
当样本被正确分类时，损失为0；当样本被错误分类时，损失为-y(wx+b)。
3）合页损失函数
当样本被正确分类且函数间隔大于1时，合页损失才是0，否则损失是1-y(wx+b)。
相比之下，合页损失函数不仅要正确分类，而且确信度足够高时损失才是0。也就是说，合页损失函数对学习有更高的要求。
非线性支持向量机：
常用核函数：
补：
SVM目标是结构风险最小化：SVM的目标是找到使得训练数据尽可能分开且分类间隔最大的超平面，应该属于结构风险最小化。
SVM可以有效避免模型过拟合：SVM可以通过正则化系数控制模型的复杂度，避免过拟合。
投递Optiver等公司10个岗位 >
