统计学习方法概论：

1 监督学习

任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测

监督学习的目的是在于学习一个由输入到输出的映射，这一映射由模型来表示，学习的目的就在于找打最好的这样的模型，模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间，假设空间的确定就是以为这学习范围的确定

如果模型足够好，训练输出和模型输出 差距应该尽可能的小

2 统计学习三要素

统计学习由模型 算法 策略构成

如果一味提高对训练数据的预测能力，所选模型复杂度往往比真实模型更高，这种现象称为过拟合，过拟合是指学习时选择数据所选参数过多，以至于出现这一模型对已知数据预测的很好，但对未知数据预测的很差的情况。

3 正则化验证

模型选择的典型是正则化，正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项或罚项。

正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值越大，比如，正则化可以是模型参数向量的范数。

4 交叉验证

    如果给定的样本数据充足，进行模型选择的一种简单方法是将随机数据切成三部分，分别为训练集，验证集和测试集

    交叉验证的核心思想是重复的使用数据，把给定的数据进行切分，将切分的数据集组合为训练集和测试集，在此基础上反复进行训练，测试以及模型选择

简单交叉验证

随机将数据分为两部分，一部分是训练数据一部分是测试数据，在测试数据上评价各个模型的测试误差，选出测试误差最小的模型。

S折交叉验证

首先随机的将数据切分为S个互不相交的大小相同的子集，然后用s-1个数据训练模型，利用余下的子集测试模型；将这一过程对可能的S种选择重复进行；最后选出S次评测中平均测试误差最小的模型。

留一交叉验证

S交叉模型的特殊情况是 S = N，称为留一交叉验证，往往在数据缺乏的情况下使用，这里，N是给定数据集的容量

生成模型和判别模型

监督学习的任务就是学习一个模型，应用这一模型，对给定的模型预测相应的输出，这个模型的一般形式称为决策函数：

或者条件概率分布：

监督学习的方法又可以称为生成方法和判别方法，所学到的模型分别称为生成模型和判别模型。

生成方法由数据学习联合概率分布,然后求出条件概率分布作为预测模型，既生成模型：

这样的方法称为生成方法，是因为模型表示了给定输入X产生的输出Y的生成关系

典型的生成模型方法： 朴素贝叶斯法和隐马尔可夫模型；

判别方法关心的是对给定输入X，应该预测出什么样的输出Y，典型的判别模型包括：k近邻法、感知机、决策树、逻辑斯谛回归模型，最大熵模型，支持向量机，提升方法和随机场

生成方法的特点：生成方法可以还原出联合概率分布，而判别方法则不能；生成方法的学习收敛的速度更快，当样本容量增加时，学到的模型可以更快的收敛于真实模型；当存在隐变量时，仍可以用生成方法学习，此时的判别方法不能用。

判别方法：判别方法直接学习的是条件概率P或者决策函数，直接面对预测往往学习的准确率更高，由于直接学习可以对数据进行各种程度的抽象，可以简化学习问题。

分类问题

分类是监督学习的一个核心问题

分类问题包括学习和分类两个过程，在学习过程中，根据已知的训练集利用一个有效的学习方法学习一个分类器；在分类过程中，利用学习的分类器对新的输入实例进行分类

标注问题

标注问题是分类问题的一个推广

标注问题输入是一个观测数列，输出是一个标记序列或状态序列，标注问题的目的在于学习一个模型，使他能够对观测序列给出标记序列作为预测

第2章 感知机

感知机是二类分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值

敢直接算法具有简单而易于实现的优点，分为原始形式和对偶形式，感知机预测是学习得到的感知机模型对新的实例进行分类。

存在某个超平面S，能够将数据集正实例点和负实例点完全划分到超平面两侧，对所有的

的实例i，有 相反 y = -1 的时候 大于0 ；

则称数据集为线性可分数据集，否则称数据集线性不可分。

感知机学习策略

感知机学习的目标是找到一个能够将训练集正实例点和负实例点完全分开的超平面，为了找出这样的超平面，既确定感知机参数w,b  需要确定一个学习策略，定义一个损失函数，并将损失函数极小化

误分类点到S平面的距离是

总距离是：

损失函数：

显然损失函数是非负的，如果么有误分类点，损失函数是0，而且误分类点越少，误分类点离超平面越近，损失函数值越小。

一个特定的样本点的损失函数：在误分类时是参数W，b的线性函数，在正确分类时是0，因此在给定训练集的时候，损失函数是训练集的w,b的连续可导函数。

感知机学习策略是在假设空间中选取致使损失函数最小模型参数w,b

2.3感知机学习算法

感知机学习问题转化为求解损失函数的最优化问题

当训练数据线性可分的时候，感知机学习算法存在无穷个解，其解由于有不同的初值或迭代顺序而可能有所不同。

K近邻法

k近邻法不具有显式学习过程，k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的模型，

k值的选择  

距离的度量

分类决策规则 是k近邻法的三个基本要素

3.1k近邻法

k近邻法：给定一个训练数据集，对新的输入实例，在训练集中找到与该实例最接近的k个实例，这k个实例多数属于某个类

3.2k近邻法模型

k近邻法中，当训练集，距离度量，k值及分类决策规则确定后，对于任何一个新的输入实例，他所属类唯一确定。

在特征空间中，对每个训练实例x，距离该点比其他点更近的所有点组成的一个区域，叫做单元，每个实例点拥有一个单元，所有的训练实例点的单元构成对特征空间的一个划分，最近邻法将实例x的类y作为其单元中所有点的类标记，这样每个单元的类别是确定的

3.2.2 距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映，k近邻模型的特征空间一般是n维实数向量空间R。

3.2.3k值选择

k值的选择会对k近邻法的结果产生重大影响。

如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，学习的近似误差会减小，缺点是学习的估计误差会变大，预测的结果会对近邻的实例点非常敏感，容易发生过拟合现象。

如果选择较大的K值，相当于用较大的邻域对实例进行预测，其优点是减少学习的估计误差，但缺点是学习的近似误差会加大。使预测发生错误，K值的增大意味着整体的模型变的简单。

在应用中，k一般选取一个较小的数值，通常采用交叉验证法来选取最优k值。

3.2.4分类决策规则

k近邻法中的分类决策规则往往是多数表决，即由输入实例的K个邻近训练实例中的多数类决定输入实例的类。

3.3 k近邻法的实现

实现k近邻法时，主要考虑的问题是如何对训练数据进行快速的K近邻搜索，这点在特征空间的维数以及训练容量大时候很有必要。

k近邻法最简单的方法是线性扫描，这时要计算输入实例与每个实例的距离，当样本比较大的时候，计算非常耗时，不可行。

为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数，具体方法很多。

构造Kd树

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形结构。

kd树是二叉树，表示对k维空间的一个划分，构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域，kd树的每个节点对应一个k维超矩形区域。

构造kd树的方法：构造根节点，使根节点对应于k维空间中包含所有实例点的超矩形区域，通过下面的递归方法对k维空间进行切分，生成子节点，在超矩形区域上选择一个坐标轴和在此坐标轴的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直与选定的坐标轴，将当前超矩形切分为左右两个子区域，这时，实例被分到两个区域，这个过程直到子区域没有实例时终止（终止时的结点为叶结点），在此过程中，将实例保存在相应的结点上。

kd树可以省去对大部分数据点的搜索，减少搜索计算量

4 朴素贝叶斯法

朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法，对于给定的数据集，首先基于特征条件独立假设学习输入/输出的联合概率分布；然后基于此模型，对给定的输入x，求出后验概率的最大输出y

4.1朴素贝叶斯法的学习与分类

朴素贝叶斯法通过训练数据集学习联合概率分布P(X,Y)，具体的学习先验概率分布以及条件概率分布。

条件概率分布P(X=x|Y=)有指数级数量的参数，其估计实际是不可行的，需要指数级的运算，所以朴素贝叶斯对条件概率分布做了条件独立性的假设

条件独立假设等于是用于分类的特征在类的确定的条件下都是条件独立的，这一假设使朴素贝叶斯变的简单，有时候会牺牲一定的准确率。

在分类时通过学习到的模型计算后验概率分布，由贝叶斯定理得到

将条件独立性的等式带入，并且注意到分母都是相同的，所以得到贝叶斯分类器

4.2朴素贝叶斯法的参数估计

4.2.1极大似然估计

  先验概率的极大似然估计：

条件概率：

学习与分类算法

计算先验概率以及条件概率

朴素贝叶斯法的基本假设是条件独立性，这是一个较强的假设，由于这个假设，模型包含的条件概率的数量大为减少，朴素贝叶斯法的学习与预测大为简化，因而朴素贝叶斯法也变的较为高效，且易于实现，缺点是分类性能不一定很高。

朴素贝叶斯法用到的贝叶斯定理与学到的联合概率模型进行分类预测。

将输入的x分到后验概率最大的类y。

后验概率的最大等价于0-1损失函数是期望风险最小化。