统计学习方法_统计学习方法下载 - CSDN
统计学习方法 订阅
《统计学习方法》是2012年清华大学出版社出版的图书,作者是李航。本书全面系统地介绍了统计学习的主要方法,适用于高等院校文本数据挖掘、信息检索及自然语言处理等专业的大学生、研究生,也可供从事计算机应用相关专业的研发人员参考。 [1] 展开全文
《统计学习方法》是2012年清华大学出版社出版的图书,作者是李航。本书全面系统地介绍了统计学习的主要方法,适用于高等院校文本数据挖掘、信息检索及自然语言处理等专业的大学生、研究生,也可供从事计算机应用相关专业的研发人员参考。 [1]
信息
ISBN
9787302275954
页    数
235页
作    者
李航
书    名
统计学习方法
出版时间
2012 年3月
开    本
16开
出版社
清华大学出版社
统计学习方法内容简介
统计学习是计算机及其应用领域的一门重要的学科。本书全面系统地介绍了统计学习的主要方法,特别是监督学习方法,包括感知机、k近邻法、朴素贝叶斯法、决策树、逻辑斯谛回归与最大熵模型、支持向量机、提升方法、em算法、隐马尔可夫模型和条件随机场等。除第1章概论和最后一章总结外,每章介绍一种方法。叙述从具体问题或实例入手,由浅入深,阐明思路,给出必要的数学推导,便于读者掌握统计学习方法的实质,学会运用。为满足读者进一步学习的需要,书中还介绍了一些相关研究,给出了少量习题,列出了主要参考文献。《统计学习方法》是统计学习及相关课程的教学参考书,适用于高等院校文本数据挖掘、信息检索及自然语言处理等专业的大学生、研究生,也可供从事计算机应用相关专业的研发人员参考。
收起全文
精华内容
参与话题
  • 李航高清版,带书签和目前的统计学习方法。《统计学习方法》全面系统地介绍了统计学习的主要方法,特别是监督学习方法,包括感知机、k近邻法、朴素贝叶斯法、决策树、逻辑斯谛回归与最大熵模型、支持向量机、提升...
  • 李航作者写的统计学习方法,这本书非常经典。这是这本书配套的ppt,方便学习理解。PDF文件
  • 文章目录统计学习方法概论监督学习知识点 统计学习方法概论 统计学习方法三要素:模型、策略和算法 统计学习的目的: 统计学习用于对数据进行预测与分析,特别是对未知算机的某些性能得到所数据进行预测与分析....


    在这里插入图片描述

    统计学习方法概论

    统计学习方法三要素:模型、策略和算法
    统计学习的目的:
    统计学习用于对数据进行预测与分析,特别是对未知算机的某些性能得到数据进行预测与分析.对数据的预测可以使计算机更加智能化:对数据的分析可以让人们获取新的知识,给人们带来新的发现.
    对数据的预测与分析是通过构建概率统计模型实现的.统计学习总的目标是考虑学习什么样的模型和如何学习模型,以使模型能对数据进行准确的预测与分析,同时也要考虑尽可能地提高学习效率.
    统计学习的方法
    统计学习的方法是基于数据构建统计模型从而对数据进行预测与分析.统计学习由监督学习(supervised learning)、非监督学习( unsupervised learning)、半监督学习( semi-supervised learning)和强化学习( reinforcement learning)等组成

    监督学习

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

    监督学习从训练数据中学习模型,对测试数据进行预测
    输入变量与输出变量均为适续变量的预测题称为 回归问题,

    输出变量为有限个离散变量的预测问题为分类问题

    输变量和输出变量均为变量序列的预测问题称为标注问题.

    监督学习分为学习和预则的个过程由学习系统与预测系统完成

    知识点

    进程和线程:
    进程和线程都是一个时间段的描述,是CPU工作时间段的描述,不过是颗粒大小不同.
    进程就是包换上下文切换的程序执行时间总和 = CPU加载上下文+CPU执行+CPU保存上下文.

    线程是共享了进程的上下文环境的更为细小的CPU时间段。

    判别式模型和生成式模型:
    判别式模型直接学习决策函数f(X)或条件概率分布P(Y|X)作为预测的模型.往往准确率更高,
    并且可以简化学习问题.如k近邻法/感知机/决策树/最大熵模型/Logistic回归/线性判别分析(LDA)/支持向量机(SVM)/Boosting/条件随机场算法(CRF)/线性回归/神经网络

    生成式模型由数据学习联合概率分布P(X,Y),然后由P(Y|X)=P(X,Y)/P(X)求出条件概率分布作为预测的模型,即生成模型.当存在隐变量时只能用生成方法学习.,
    如混合高斯模型和其他混合模型/隐马尔可夫模型(HMM)/朴素贝叶斯/依赖贝叶斯(AODE)/LDA文档主题生成模型

    概率质量函数,概率密度函数,累积分布函数:
    概率质量函数 (probability mass function,PMF)是离散随机变量在各特定取值上的概率。

    概率密度函数(p robability density function,PDF )是对连续随机变量 定义的,本身不是概率,只有对连续随机变量的取值进行积分后才是概率。

    累积分布函数(cumulative distribution function,CDF) 能完整描述一个实数随机变量X的概率分布,是概率密度函数的积分。

    极大似然估计:
    已知某个参数能使这个样本出现的概率最大,我们当然不会再去选择其他小概率的样本,所以干脆就把这个参数作为估计的真实值

    最小二乘法:
    二乘的英文是least square,找一个(组)估计值,使得实际值与估计值之差的平方加总之后的值最小.在这里插入图片描述
    求解方式是对参数求偏导,令偏导为0即可.样本量小时速度快.
    梯度下降法:
    负梯度方向是函数值下降最快的方向,每次更新值都等于原值加学习率(步长)乘损失函数的梯度.每次都试一个步长看会不会下降一定的程度,如果没有的话就按比例减小步长.不断应用该公式直到收敛,可以得到局部最小值.
    初始值的不同组合可以得到不同局部最小值.在最优点时会有震荡.
    批量梯度下降(BGD):
    每次都使用所有的.m个样本来更新,容易找到全局最优解,但是m较大时速度较慢

    在这里插入图片描述
    随机梯度下降(SGD):
    每次只使用一个样本来更新,训练速度快,但是噪音较多,不容易找到全局最优解,以损失很小的一部分精确度和增加一定数量的迭代次数为代价,换取了总体的优化效率的提升.
    注意控制步长缩小,减少震荡.
    在这里插入图片描述
    小批量梯度下降(MBGD):
    每次使用一部分样本来更新.

    牛顿法:
    牛顿法是二次收敛,因此收敛速度快.从几何上看是每次用一个二次曲面来拟合当前所处位置的局部曲面而梯度下降法是用一个平面来拟合.
    牛顿法起始点不能离极小点太远,否则很可能不会拟合.
    在这里插入图片描述
    1、黑塞矩阵是由目标函数f(x)在点X处的二阶偏导数组成的n*n阶对称矩阵。
    2、牛顿法:将f(x)在x(k)附近进行二阶泰勒展开:
    在这里插入图片描述
    其中gk是f(x)的梯度向量在x(k)的值,H(x(k))是f(x)的黑塞矩阵在点x(k)的值.牛顿法利用极小点的必要条件f(x)处的梯度为0,每次迭代中从点x(k)开始,假设
    在这里插入图片描述
    对二阶泰勒展开求偏导有
    在这里插入图片描述

    在这里插入图片描述
    以此为迭代公式就是牛顿法.
    拟牛顿法:用一个n阶正定矩阵Gk=G(x(k))来
    近似代替
    黑塞矩阵的逆矩阵就是拟牛顿法的基本思想.在牛顿法中黑塞矩阵满足的条件如下
    在这里插入图片描述
    在这里插入图片描述,
    则有
    在这里插入图片描述
    称为拟牛顿条件.根据选择Gk方法的不同有多种具体实现方法.
    1、DFP算法:假设每一步
    在这里插入图片描述
    ,为使Gk+1满足拟牛顿条件,可使Pk和Qk满足
    在这里插入图片描述
    ,例如取
    在这里插入图片描述
    就得到迭代公式
    在这里插入图片描述
    2、 BFGS算法: 最流行的拟牛顿算法.考虑用Bk逼近黑塞矩阵,此时相应的拟牛顿条件是在这里插入图片描述
    在这里插入图片描述
    先验概率和后验概率:
    1、先验概率就是事情发生前的预测概率.
    2、后验概率是一种条件概率,它限定了事件为隐变量取值,而条件为观测结果。一般的条件概率,条件和事件可以是任意的.
    3、贝叶斯公式P(y|x) = ( P(x|y) * P(y) ) / P(x)中,P(y|x)是后验概率,P(x|y)是条件概率,P(y)是先验概率.

    偏差,方差,噪声:
    1、偏差:度量了学习算法的期望预测和真实结果偏离程度

    2、方差:度量了同样大小的训练集的变动所导致的学习性能的变化,即刻画了数据扰动所造成的影响
    3、噪声:可以认为是数据自身的波动性,表达了目前任何学习算法所能达到泛化误差的下限
    4、泛化误差可以分解为偏差、方差与噪声之和

    对偶原理:
    一个优化问题可以从主问题和对偶问题两个方面考虑.在推导对偶问题时,通过将拉格朗日函数对x求导并使导数为0来获得对偶函数.对偶函数给出了主问题最优解的下界,因此对偶问题一般是凸问题,那么只需求解对偶函数的最优解就可以了.

    KKT条件:
    通常我们要求解的最优化条件有如下三种:
    1、无约束优化问题:通常使用求导,使导数为零,求解候选最优值
    2、有等式约束的优化问题:通常使用拉格朗日乘子法,即把等式约束用拉格朗日乘子和优化问题合并为一个式子,通过对各个变量求导使其为零,求解候选最优值.拉格朗日乘数法其实是KKT条件在等式约束优化问题的简化版.
    3、有不等式约束的优化问题:通常使用KKT条件.即把不等式约束,等式约束和优化问题合并为一个式子.假设有多个等式约束h(x)和不等式约束g(x)
    在这里插入图片描述
    则不等式约束引入的KKT条件如下:
    在这里插入图片描述
    实质是最优解在g(x)<0区域内时,约束条件不起作用,等价于对μ置零然后对原函数的偏导数置零;当g(x)=0时与情况2相近.结合两种情况,那么只需要使L对x求导为零,使h(x)为零,使μg(x)为零三式即可求解候选最优值.
    性能度量:
    1、准确度,最常用,但在数据集不平衡的情况下不好

    2、Precision(精确度/查准率): P=TP/(TP+FP)
    3、Recall(召回率/查全率): R=TP/(TP+FN)


    4、Fβ度量:
    在这里插入图片描述
    当β=1时退化为F1度量,是精确率和召回率的调和均值.
    5、TPR(真正例率):TPR=TP/(TP+FN)
    6、FPR(假正例率):FPR=FP/(TN+FP)
    7、PR曲线:纵轴为Precision,横轴为Recall,一般使用平衡点(BEP,即Precsion=Recall的点)作为衡量标准.
    8、ROC(接受者操作特征)曲线:纵轴为TRP,横轴为FPR,在绘图时将分类阈值依次设为每个样例的预测值,再连接各点.ROC曲线围住的面积称为AOC,AOC越大则学习器性能越好.

    损失函数和风险函数:
    1、损失函数度量模型一次预测的好坏.常用的损失函数有:0-1损失函数,平方损失函数,绝对损失函数,对数似然损失函数.
    2、损失函数的期望是理论上模型关于联合分布P(X,Y)的平均意义下的损失,称为风险函数,也叫期望风险.但是联合分布是未知的,期望风险不能直接计算.
    3、当样本容量N趋于无穷时经验风险趋于期望风险,但现实中训练样本数目有限.

    经验风险最小化和结构风险最小化:
    1、模型关于训练数据集的平均损失称为经验风险.
    经验风险最小化的策略就是最小化经验风险.当样本数量足够大时学习效果较好.比如当模型是条件概率分布,损失函数是对数损失函数时,经验风险最小化就等价于极大似然估计.但是当样本容量很小时会出现过拟合.
    2、结构风险最小化等于正则化.结构风险在经验风险上加上表示模型复杂度的正则化项.
    比如当模型是条件概率分布,损失函数是对数损失函数,模型复杂度由模型的先验概率表示时,结构风险最小化就等价于最大后验概率估计.
    **过拟合是指学习时选择的模型所包含的参数过多,以致于对已知数据预测得很好,但对未知数据预测很差的现象.**模型选择旨在避免过拟合并提高模型的预测能力.
    正则化是模型选择的典型方法.正则化项一般是模型复杂度的单调递增函数,比如模型参数向量的范数.
    交叉验证是另一常用的模型选择方法,可分为简单交叉验证,K折交叉验证,留一交叉验证等.

    感知机

    感知机是二类分类的线性模型,属于判别模型.感知机学习旨在求出将**训练数据进行线性划分的分离超平面.**是神经网络和支持向量机的基础.
    模型:
    在这里插入图片描述
    w叫作权值向量,b叫做偏置,sign是符号函数.

    **感知机的几何解释:**wx+b对应于特征空间中的一个分离超平面S,其中w是S的法向量,b是S的截距.S将特征空间划分为两个部分,位于两个部分的点分别被分为正负两类.
    **策略:**假设训练数据集是线性可分的,感知机的损失函数是误分类点到超平面S的总距离.因为误分类点到超平面S的距离是在这里插入图片描述
    且对于误分类的数据来说,总有
    在这里插入图片描述
    因此不考虑1/||w||,就得到感知机的损失函数:在这里插入图片描述
    其中M是误分类点的集合.感知机学习的策略就是选取使损失函数最小的模型参数.

    算法:
    感知机的最优化方法采用随机梯度下降法.首先任意选取一个超平面w0,b0,然后不断地极小化目标函数.在极小化过程中一次随机选取一个误分类点更新w,b,直到损失函数为0
    在这里插入图片描述
    其中η表示步长.该算法的直观解释是:当一个点被误分类,就调整w,b使分离超平面向该误分类点接近.感知机的解可以不同.

    对偶形式:假设原始形式中的w0和b0均为0,设逐步修改w和b共n次,令a=nη,最后学习到的w,b可以表示为:
    在这里插入图片描述
    那么对偶算法就变为设初始a和b均为0,每次选取数据更新a和b直至没有误分类点为止.对偶形式的意义在于可以将训练集中实例间的内积计算出来,存在Gram矩阵中,可以大大加快训练速度.

    k近邻法

    k近邻法(KNN)根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测.k值的选择,距离度量及分类决策规则是k近邻法的三个基本要素.当k=1时称为最近邻算法.
    模型:当训练集,距离度量,k值以及分类决策规则确定后,特征空间已经根据这些要素被划分为一些子空间,且子空间里每个点所属的类也已被确定.

    **策略:**距离:特征空间中两个实例点的距离是相似程度的反映,k近邻算法一般使用欧氏距离,也可以使用更一般的Lp距离或Minkowski距离.

    k值:k值较小时,整体模型变得复杂,容易发生过拟合.k值较大时,整体模型变得简单.在应用中k一般取较小的值,通过交叉验证法选取最优的k.

    分类决策规则:k近邻中的分类决策规则往往是多数表决,多数表决规则等价于经验风险最小化.

    算法:根据给定的距离度量,在训练集中找出与x最邻近的k个点,根据分类规则决定x的类别y.

    kd树:

    1、kd树就是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构.kd树更适用于训练实例数远大于空间维数时的k近邻搜索.
    2、构造:可以通过如下递归实现:在超矩形区域上选择一个坐标轴和此坐标轴上的一个切分点,确定一个超平面,该超平面将当前超矩形区域切分为两个子区域.在子区域上重复切分直到子区域内没有实例时终止.通常依次选择坐标轴和选定坐标轴上的中位数点为切分点,这样可以得到平衡kd树.
    在这里插入图片描述

    **3、搜索:**从根节点出发,若目标点x当前维的坐标小于切分点的坐标则移动到左子结点,否则移动到右子结点,直到子结点为叶结点为止.以此叶结点为"当前最近点",递归地向上回退,在每个结点:(a)如果该结点比当前最近点距离目标点更近,则以该结点为"当前最近点"(b)"当前最近点"一定存在于该结点一个子结点对应的区域,检查该结点的另一子结点对应的区域是否与以目标点为球心,以目标点与"当前最近点"间的距离为半径的超球体相交.如果相交,移动到另一个子结点,如果不相交,向上回退.持续这个过程直到回退到根结点,最后的"当前最近点"即为
    最近点。

    朴素贝叶斯

    朴素贝叶斯是基于贝叶斯定理和特征条件独立假设的分类方法.首先学习输入/输出的联合概率分布,然后基于此模型,对给定的输入x,利用贝叶斯定理求出后验概率最大的输出y.属于生成模型.
    **模型:**首先学习先验概率分布在这里插入图片描述
    然后学习条件概率分布
    在这里插入图片描述
    如果估计实际,需要指数级的计算,所以朴素贝叶斯法对条件概率分布作了条件独立性的假设,上式变成

    在这里插入图片描述
    在分类时,通过学习到的模型计算后验概率分布,由贝叶斯定理得到
    在这里插入图片描述
    将条件独立性假设得到的等式代入,并且注意到分母都是相同的,所以得到朴素贝叶斯分类器:

    在这里插入图片描述
    朴素贝叶斯将实例分到后验概率最大的类中,这等价于期望风险最小化.
    ***算法:***使用极大似然估计法估计相应的先验概率
    在这里插入图片描述
    和条件概率
    在这里插入图片描述
    计算条件独立性假设下的实例各个取值的可能性
    在这里插入图片描述
    选取其中的最大值作为输出.
    用极大似然估计可能会出现所要估计的概率值为0的情况,在累乘后会影响后验概率的计算结果,使分类产生偏差.可以采用贝叶斯估计,在随机变量各个取值的频数上赋予一个正数.
    在这里插入图片描述
    Sj为j属性可能取值数量,当λ=0时就是极大似然估计.常取λ=1,称为拉普拉斯平滑.
    如果是连续值的情况,可以假设连续变量服从高斯分布,然后用训练数据估计参数.
    在这里插入图片描述

    决策树

    决策树是一种基本的分类与回归方法.它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布.主要优点是模型具有可读性,分类速度快.

    模型:分类决策树由结点和有向边组成.结点分为内部结点(表示一个特征或属性)和叶结点(表示一个类).决策树的路径具有互斥且完备的性质.

    策略:决策树学习本质上是从训练数据集中归纳出一组分类规则.我们需要的是一个与训练数据矛盾较小,同时具有很好的泛化能力的决策树.从所有可能的决策树中选取最优决策树是NP完全问题,所以现实中常采用启发式方法近似求解.

    算法:决策树学习算法包含特征选择,决策树的生成与决策树的剪枝过程.
    生成只考虑局部最优,剪枝则考虑全局最优.
    特征选择:如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的.扔掉这样的特征对决策树学习的精度影响不大.

    1、信息熵:熵是衡量随机变量不确定性的度量.熵越大,随机变量的不确定性就越大.信息熵是信息量的期望
    在这里插入图片描述
    条件熵表示在已知随机变量X的条件下随机变量Y的不确定性.

    在这里插入图片描述
    2、信息增益:表示得知特征X的信息而使得类Y的信息的不确定性减少的程度.定义为集合D的经验熵与特征A在给定条件下D的经验条件熵之差在这里插入图片描述
    也就是训练数据集中类与特征的互信息.

    3、信息增益算法:计算数据集D的经验熵
    在这里插入图片描述
    ,计算特征A对数据集D的经验条件熵

    在这里插入图片描述
    计算信息增益,选取信息增益最大的特征.

    4、信息增益比:信息增益值的大小是相对于训练数据集而言的,并无绝对意义.使用信息增益比可以对这一问题进行校正.
    在这里插入图片描述

    决策树的生成:

    **ID3算法:**核心是在决策树各个结点上应用信息增益准则选择信息增益最大且大于阈值的特征,递归地构建决策树.ID3相当于用极大似然法进行概率模型的选择.由于算法只有树的生成,所以容易产生过拟合.
    C4.5算法:C4.5算法与ID3算法相似,改用信息增益比来选择特征.

    决策树的剪枝:

    1、在学习时过多考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树,产生过拟合现象.解决方法是对已生成的决策树进行简化,称为剪枝.
    2、设树的叶结点个数为|T|,每个叶结点有Nt个样本点,其中k类样本点有Ntk个,剪枝往往通过极小化决策树整体的损失函数
    在这里插入图片描述
    来实现,其中经验熵
    在这里插入图片描述
    剪枝通过加入a|T|项来考虑模型复杂度,实际上就是用正则化的极大似然估计进行模型选择.
    3、剪枝算法:剪去某一子结点,如果生成的新的整体树的损失函数值小于原树,则进行剪枝,直到不能继续为止.具体可以由动态规划实现.

    CART算法:
    1、CART既可以用于分类也可以用于回归.它假设决策树是二叉树,内部结点特征的取值为"是"和"否".递归地构建二叉树,对回归树用平方误差最小化准则,对分类数用基尼指数最小化准则.
    2、回归树的生成:在训练数据集所在的输入空间中,递归地将每个区域划分为两个子区域.选择第j个变量和它取的值s作为切分变量和切分点,并定义两个区域
    在这里插入图片描述
    遍历变量j,对固定的j扫描切分点s,求解
    在这里插入图片描述
    用选定的对(j,s)划分区域并决定相应的输出值,直到满足停止条件.
    在这里插入图片描述

    3、基尼指数:假设有K个类,样本属于第k类的概率为pk,则概率分布的基尼指数为
    在这里插入图片描述
    表示不确定性.在特征A的条件下集合D的基尼指数定义为:
    在这里插入图片描述
    表示分割后集合D的不确定性.基尼指数越大,样本集合的不确定性也就越大.

    4、分类树的生成:从根结点开始,递归进行以下操作:设结点的训练数据集为D,对每个特征A和其可能取的每个值a,计算A=a时的基尼指数,选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点,生成两个子结点,直至满足停止条件.停止条件一般是结点中的样本个数小于阈值,或样本集的基尼指数小于阈值,或没有更多特征.

    5、CART剪枝:
    Tt表示以t为根结点的子树,|Tt|是Tt的叶结点个数.可以证明当
    在这里插入图片描述
    时,Tt与t有相同的损失函数值,且t的结点少,因此t比Tt更可取,对Tt进行剪枝.自下而上地对各内部结点t计算
    在这里插入图片描述
    并令a=min(g(t)),自上而下地访问内部节点t,如果有g(t)=a,进行剪枝,并对t以多数表决法决定其类,得到子树T,如此循环地生成一串子树序列,直到新生成的T是由根结点单独构成的树为止.利用交叉验证法在子树序列中选取最优子树.
    如果是连续值的情况,一般用二分法作为结点来划分.

    logistic回归和最大熵模型

    在这里插入图片描述
    在这里插入图片描述
    逻辑斯谛分布:分布函数f(x)以点(μ,1/2)为中心对称,γ的值越小,曲线在中心附近增长得越快.

    逻辑斯谛回归模型:对于给定的输入x,根据
    在这里插入图片描述
    在这里插入图片描述
    计算出两个条件概率值的大小,将x分到概率值较大的那一类.将偏置b加入到权值向量w中,并在x的最后添加常数项1,得到
    在这里插入图片描述
    在这里插入图片描述
    如果某事件发生的概率是p,则该事件发生的几率(此处几率指该事件发生概率与不发生概率之比)是p/1-p,对数几率是log(p/1-p),那么
    在这里插入图片描述
    也就是说在逻辑斯谛回归模型中,输出Y=1的对数几率是输入x的线性函数,线性函数值越接近正无穷,概率值就越接近1,反之则越接近0.

    似然估计:给定x的情况下参数θ是真实参数的可能性.
    模型参数估计:对于给定的二分类训练数据集,对数似然函数为
    在这里插入图片描述
    也就是损失函数.其中P(Y=1|x)=π(x),对L(w)求极大值,就可以得到w的估计值.问题变成了以对数似然函数为目标函数的最优化问题.
    多项逻辑斯谛回归: 当问题是多分类问题时,可以作如下推广:设Y有K类可能取值
    在这里插入图片描述
    实际上就是one-vs-all的思想,将其他所有类当作一个类,问题转换为二分类问题.

    最大熵原理:学习概率模型时,在所有可能的概率模型中,熵最大的模型是最好的模型.直观地,最大熵原理认为模型首先要满足已有的事实,即约束条件.在没有更多信息的情况下,那些不确定的部分都是"等可能的".

    最大熵模型:给定训练数据集,可以确定联合分布P(X,Y)的经验分布
    在这里插入图片描述
    和边缘分布P(X)的经验分布
    在这里插入图片描述
    其中v表示频数,N表示样本容量.用特征函数f(x,y)=1描述x与y满足某一事实,可以得到特征函数关于P(X,Y)的经验分布的期望值和关于模型P(Y|X)与P(X)的经验分布的期望值,假设两者相等,就得到了约束条件
    在这里插入图片描述
    定义在条件概率分布P(Y|X)上的条件熵为
    在这里插入图片描述
    则条件熵最大的模型称为最大熵模型.
    最大熵模型的学习就是求解最大熵模型的过程.等价于约束最优化问题
    在这里插入图片描述
    将求最大值问题改为等价的求最小值问题
    在这里插入图片描述
    引入拉格朗日乘子
    在这里插入图片描述
    将原始问题
    在这里插入图片描述
    转换为无约束最优化的对偶问题
    在这里插入图片描述
    首先求解内部的极小化问题,即求L(P,W)对P(y|x)的偏导数
    在这里插入图片描述
    并令偏导数等于0,解得
    在这里插入图片描述
    .可以证明对偶函数等价于对数似然函数,那么对偶函数极大化等价于最大熵模型的极大似然估计

    在这里插入图片描述
    之后可以用最优化算法求解得到w.

    最大熵模型与逻辑斯谛回归模型有类似的形式,它们又称为对数线性模型.模型学习就是在给定的训练数据条件下对模型进行极大似然估计或正则化的极大似然估计.

    算法:似然函数是光滑的凸函数,因此多种最优化方法都适用.
    改进的迭代尺度法(IIS):假设当前的参数向量是w,如果能找到一种方法w->w+δ使对数似然函数值变大,就可以重复使用这一方法,直到找到最大值.
    逻辑斯谛回归常应用梯度下降法,牛顿法或拟牛顿法.

    支持向量机

    **模型:**支持向量机(SVM)是一种二类分类模型.它的基本模型是定义在特征空间上的间隔最大的线性分类器.支持向量机还包括核技巧,使它成为实质上的非线性分类器.
    分离超平面
    分离超平面
    分类决策函数
    分类决策函数
    **策略:**间隔最大化,可形式化为一个求解凸二次规划的问题,也等价于正则化的合页损失函数的最小化问题.

    当训练数据线性可分时,通过硬间隔最大化,学习出线性可分支持向量机.当训练数据近似线性可分时,通过软间隔最大化,学习出线性支持向量机.当训练数据线性不可分时,通过使用核技巧及软间隔最大化,学习非线性支持向量机.

    核技巧:当输入空间为欧式空间或离散集合,特征空间为希尔伯特空间时,核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积.通过核函数学习非线性支持向量机等价于在高维的特征空间中学习线性支持向量机.这样的方法称为核技巧.

    考虑一个二类分类问题,假设输入空间与特征空间为两个不同的空间,输入空间为欧氏空间或离散集合,特征空间为欧氏空间或希尔伯特空间.支持向量机都将输入映射为特征向量,所以支持向量机的学习是在特征空间进行的.

    支持向量机的最优化问题一般通过对偶问题化为凸二次规划问题求解,具体步骤是将等式约束条件代入优化目标,通过求偏导求得优化目标在不等式约束条件下的极值.

    线性可分支持向量机:

    1、当训练数据集线性可分时,存在无穷个分离超平面可将两类数据正确分开.利用间隔最大化得到唯一最优分离超平面
    在这里插入图片描述
    和相应的分类决策函数
    在这里插入图片描述
    称为线性可分支持向量机

    2、函数间隔:一般来说,一个点距离分离超平面的远近可以表示分类预测的确信程度.在超平面确定的情况下,|wx+b|能够相对地表示点x距离超平面的远近,而wx+b与y的符号是否一致能够表示分类是否正确.所以可用来表示分类的正确性及确信度,这就是函数间隔.注意到即使超平面不变,函数间隔仍会受w和b的绝对大小影响.

    3、**几何间隔:**一般地,当样本点被超平面正确分类时,点x与超平面的距离是
    在这里插入图片描述
    其中||w||是w的l2范数.这就是几何间隔的定义.定义超平面关于训练数据集T的几何间隔为超平面关于T中所有样本点的几何间隔之最小值.
    在这里插入图片描述
    当||w||=1时几何间隔和函数间隔相等.

    硬间隔最大化:对线性可分的训练集而言,这里的间隔最大化又称为硬间隔最大化.直观解释是对训练集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类.求最大间隔分离超平面即约束最优化问题
    在这里插入图片描述
    将几何间隔用函数间隔表示
    在这里插入图片描述
    并且注意到函数间隔的取值并不影响最优化问题的解,不妨令函数间隔=1,并让最大化1/||w||等价为最小化||w||^2/2,问题变为凸二次规划问题
    在这里插入图片描述
    5、支持向量和间隔边界:与分离超平面距离最近的样本点的实例称为支持向量.支持向量是使最优化问题中的约束条件等号成立的点.因此对y=+1的正例点和y=-1的负例点,支持向量分别在超平面H1:wx+b=+1和H2:wx+b=-1.H1和H2平行,两者之间形成一条长带,长带的宽度
    在这里插入图片描述
    称为间隔,H1和H2称为间隔边界.在决定分离超平面时只有支持向量起作用,所以支持向量机是由很少的"重要的"训练样本确定的.由对偶问题同样可以得到支持向量一定在间隔边界上.
    在这里插入图片描述
    6、对偶算法: 引进拉格朗日乘子,定义拉格朗日函数
    在这里插入图片描述
    根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:
    在这里插入图片描述
    先求对w,b的极小值.将L(w,b,a)分别对w,b求偏导数并令其等于0,得
    在这里插入图片描述
    代入拉格朗日函数得
    在这里插入图片描述
    这就是极小值.接下来对极小值求对a的极大,即是对偶问题
    在这里插入图片描述
    将求极大转换为求极小
    在这里插入图片描述
    由KKT条件成立得
    在这里插入图片描述
    其中j为使aj*>0的下标之一.所以问题就变为求对偶问题的解a*,再求得原始问题的解w*,b*,从而得分离超平面及分类决策函数可以看出w和b都只依赖训练数据中ai*>0的样本点(xi,yi),这些实例点xi被称为支持向量.

    线性支持向量机:
    1、如果训练数据是线性不可分的,那么上述方法中的不等式约束并不能都成立,需要修改硬间隔最大化,使其成为软间隔最大化.

    2、线性不可分意味着某些特异点不能满足函数间隔大于等于1的约束条件,可以对每个样本点引进一个松弛变量,使函数间隔加上松弛变量大于等于1,约束条件变为
    在这里插入图片描述
    同时对每个松弛变量,支付一个代价,目标函数变为
    在这里插入图片描述
    其中C>0称为惩罚参数,C值越大对误分类的惩罚也越大.新目标函数包含了两层含义:使间隔尽量大,同时使误分类点的个数尽量小.

    **3、软间隔最大化:**学习问题变成如下凸二次规划问题:
    在这里插入图片描述
    可以证明w的解是唯一的,但b的解存在一个区间.线性支持向量机包含线性可分支持向量机,因此适用性更广.

    对偶算法: 原始问题的对偶问题是,构造拉格朗日函数
    在这里插入图片描述

    先求对w,b,ξ的极小值,分别求偏导并令导数为0,得
    在这里插入图片描述
    代入原函数,再对极小值求a的极大值,得到
    在这里插入图片描述
    利用后三条约束消去μ,再将求极大转换为求极小,得到对偶问题
    在这里插入图片描述
    由KKT条件成立可以得到

    在这里插入图片描述
    j是满足0<aj*<C的下标之一.问题就变为选择惩罚参数C>0,求得对偶问题(凸二次规划问题)的最优解a*,代入计算w和b,求得分离超平面和分类决策函数.因为b的解并不唯一,所以实际计算b*时可以取所有样本点上的平均值.

    支持向量:在线性不可分的情况下,将对应与ai*>0的样本点(xi,yi)的实例点xi称为支持向量.软间隔的支持向量或者在间隔边界上,或者在间隔边界与分类超平面之间,或者再分离超平面误分一侧
    在这里插入图片描述
    6、合页损失函数:可以认为是0-1损失函数的上界,而线性支持向量机可以认为是优化合页损失函数构成的目标函数
    在这里插入图片描述

    非线性支持向量机:

    1、如果分类问题是非线性的,就要使用非线性支持向量机.主要特点是使用核技巧.

    2、非线性分类问题:用线性分类方法求解非线性分类问题分为两步:首先使用一个变换将原空间的数据映射到新空间,然后在新空间里用线性分类学习方法从训练数据中学习分类模型.

    3、核函数:设X是输入空间(欧式空间的子集或离散集合),H为特征空间(希尔伯特空间),一般是高维甚至无穷维的.如果存在一个从X到H的映射
    在这里插入图片描述
    使得对所有x,z属于X,函数K(x,z)满足条件
    在这里插入图片描述
    点乘代表内积,则称K(x,z)为核函数.

    4、核技巧:基本思想是通过一个非线性变换将输入空间对应于一个特征空间,使得在输入空间中的超曲面模型对应于特征空间中的超平面模型(支持向量机).在学习和预测中只定义核函数K(x,z),而不显式地定义映射函数.对于给定的核K(x,z),特征空间和映射函数的取法并不唯一.注意到在线性支持向量机的对偶问题中,目标函数和决策函数都只涉及输入实例与实例之间的内积,xixj可以用核函数K(xi,xj)=Ф(xi)Ф(xj)来代替.当映射函数是非线性函数时,学习到的含有核函数的支持向量机是非线性分类模型.在实际应用中,往往依赖领域知识直接选择核函数.

    **5、正定核:**通常所说的核函数是指正定核函数.只要满足正定核的充要条件,那么给定的函数K(x,z)就是正定核函数.设K是定义在X*X上的对称函数,如果任意xi属于X,K(x,z)对应的Gram矩阵
    在这里插入图片描述
    是半正定矩阵,则称K(x,z)是正定核.这一定义在构造核函数时很有用,但要验证一个具体函数是否为正定核函数并不容易,所以在实际问题中往往应用已有的核函数.

    **6、算法:**选取适当的核函数K(x,z)和适当的参数C,将线性支持向量机对偶形式中的内积换成核函数,构造并求解最优化问题
    在这里插入图片描述
    选择最优解a的一个正分量0<aj<C计算
    在这里插入图片描述
    构造决策函数
    在这里插入图片描述

    常用核函数:
    1、多项式核函数(polynomial kernel function):
    在这里插入图片描述
    对应的支持向量机是一个p次多项式分类器,分类决策函数为
    在这里插入图片描述
    2、高斯核函数(Gaussian krenel function):
    在这里插入图片描述
    对应的支持向量机是高斯径向基函数(RBF)分类器.分类决策函数为
    在这里插入图片描述
    3、字符串核函数(string kernel function): 核函数不仅可以定义在欧氏空间上,还可以定义在离散数据的集合上.字符串核函数给出了字符串中长度等于n的所有子串组成的特征向量的余弦相似度.

    序列最小最优化(SMO)算法:
    在这里插入图片描述
    1、SMO是一种快速求解凸二次规划问题的算法.基本思路是:如果所有变量都满足此优化问题的KKT条件,那么解就得到了.否则,选择两个变量,固定其他变量,针对这两个变量构建一个二次规划问题.不断地将原问题分解为子问题并对子问题求解,就可以求解原问题.注意子问题两个变量中只有一个是自由变量,另一个由等式约束确定.

    2、两个变量二次规划的求解方法:假设选择的两个变量是a1,a2,其他变量是固定的,于是得到子问题
    在这里插入图片描述
    ε是常数,目标函数式省略了不含a1,a2的常数项.考虑不等式约束和等式约束,要求的是目标函数在一条平行于对角线的线段上的最优值
    在这里插入图片描述
    问题变为单变量的最优化问题.假设初始可行解为aold,最优解为anew,考虑沿着约束方向未经剪辑的最优解anew,unc(即未考虑不等式约束).对该问题求偏导数,并令导数为0,代入原式,令
    在这里插入图片描述
    得到
    在这里插入图片描述
    L与H是a2new所在的对角线段端点的界.并解得
    在这里插入图片描述
    **3、变量的选择方法:**在每个子问题中选择两个变量优化,其中至少一个变量是违反KKT条件的.第一个变量的选取标准是违反KKT条件最严重的样本点,第二个变量的选取标准是希望能使该变量有足够大的变化,一般可以选取使对应的|E1-E2|最大的点.在每次选取完点后,更新阈值b和差值Ei.

    提升方法

    提升(boosting)是一种常用的统计学习方法,是集成学习的一种.它通过改变训练样本的权重(概率分布),学习多个弱分类器(基本分类器),并将这些分类器线性组合来构成一个强分类器提高分类的性能.

    AdaBoost:

    1、AdaBoost提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值.然后采取加权多数表决的方法组合弱分类器.

    2、算法:首先假设训练数据集具有均匀的权值分布D1,使用具有权值分布Dm的训练数据集学习得到基本分类器Gm(x),计算分类误差率
    在这里插入图片描述
    和Gm(x)的系数
    在这里插入图片描述
    更新训练数据集的权值分布
    在这里插入图片描述
    其中
    在这里插入图片描述
    Zm是使Dm+1成为概率分布的规范化因子
    在这里插入图片描述
    重复上述操作M次后得到M个弱分类器,构建线性组合得到最终分类器
    在这里插入图片描述
    3、AdaBoost算法也可以理解成模型为加法模型,损失函数为指数函数,学习算法为前向分步算法的二类分类学习方法.
    前向分步算法:考虑加法模型
    在这里插入图片描述
    其中b(x,γm)为基函数,γm为基函数的参数,βm为基函数的系数.在给定损失函数L(y,f(x))的条件下,学习加法模型就是求解损失函数极小化问题
    在这里插入图片描述
    其中b(x,γm)为基函数,γm为基函数的参数,βm为基函数的系数.在给定损失函数L(y,f(x))的条件下,学习加法模型就是求解损失函数极小化问题
    在这里插入图片描述
    前向分步算法求解的想法是:从前往后,每一步只学习一个基函数及其系数,优化
    在这里插入图片描述
    得到参数βm和γm,更新
    在这里插入图片描述
    逐步逼近优化目标.最终得到加法模型.
    提升树:
    1、提升树是模型为加法模型,算法为前向分布算法,基函数为决策树的提升方法.第m步的模型是
    在这里插入图片描述
    通过经验风险极小化确定下一棵决策树的参数
    在这里插入图片描述
    不同问题的提升树学习算法主要区别在于使用的损失函数不同.

    2、二类分类问题:只需将AdaBoost算法中的基本分类器限制为二类分类数即可.

    3、回归问题:如果将输入空间划分为J个互不相交的区域,并且在每个区域上确定输出的常量Cj,那么树可表示为
    在这里插入图片描述
    其中
    在这里插入图片描述
    提升树采用前向分步算法:
    在这里插入图片描述
    当采用平方误差损失函数时,损失变为
    在这里插入图片描述
    其中r是当前模型拟合数据的残差.每一步都只需拟合残差学习一个回归树即可.

    4、梯度提升树(GBDT): 利用最速下降法的近似方法来实现每一步的优化,关键在于用损失函数的负梯度在当前模型的值
    在这里插入图片描述
    作为回归问题中提升树算法中的残差的近似值,每一步以此来估计回归树叶结点区域以拟合残差的近似值,并利用线性搜索估计叶结点区域的值使损失函数最小化,然后更新回归树即可.

    AdaBoost产生的基础学习器有好有坏,因此加入权重.提升树产生的基础学习器是一个不断减少残差的过程,并不是一个单独的分类器,因此一般不加权重.

    XGBoost:相比传统GBDT有以下优点:
    1、在优化时用到了二阶导数信息.
    2、在代价函数里加入了正则项.
    3、每次迭代后都将叶子结点的权重乘上一个系数,削弱每棵树的影响.
    4、列抽样.
    5、在训练前对数据进行排序,保存为block结构,并行地对各个特征进行增益计算.

    EM算法

    EM算法是一种迭代算法,用于含有隐变量的概率模型参数的极大似然估计.每次迭代由两步组成:E步,求期望(expectation),M步,求极大值(maximization),直至收敛为止.
    隐变量:不能被直接观察到,但是对系统的状态和能观察到的输出存在影响的一种东西.
    算法:
    1、选择参数的初始值θ(0),开始迭代.注意EM算法对初值是敏感的.
    2、E步:θ(i)为第i次迭代参数θ的估计值,在第i+1次迭代的E步,计算
    在这里插入图片描述
    P(Z|Y,θ(i))是在给定观测数据Y和当前参数估计θ(i)下隐变量数据Z的条件概率分布.
    3、M步:求使Q(θ,θ(i))极大化的θ,确定第i+1次迭代的参数的估计值
    在这里插入图片描述
    4、重复2和3直到收敛,一般是对较小的正数ε1和ε2满足
    在这里插入图片描述
    则停止迭代.
    EM算法是通过不断求解下界的极大化逼近求解对数似然函数极大化的算法.可以用于生成模型的非监督学习.生成模型由联合概率分布P(X,Y)表示.X为观测数据,Y为未观测数据.

    高斯混合模型(GMM):高斯混合模型是指具有如下形式的概率分布模型:
    在这里插入图片描述
    其中
    在这里插入图片描述
    在这里插入图片描述
    称为第k个分模型.
    高斯混合模型参数估计的EM算法:

    1、取参数的初始值开始迭代
    2、E步:计算分模型k对观测数据yj的响应度

    在这里插入图片描述
    3、在这里插入图片描述
    M步:计算新一轮迭代的模型参数
    在这里插入图片描述
    4、重复2和3直到对数似然函数收敛.
    在这里插入图片描述

    隐马尔可夫模型(HMM)

    隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态序列,再由各个状态生成一个观测而产生观测随机序列的过程.

    设Q是所有可能的状态的集合,V是所有可能的观测的集合
    在这里插入图片描述
    I是长度为T的状态序列,O是对应的观测序列
    在这里插入图片描述
    A是状态转移概率矩阵,aij表示在时刻t处于状态qi的条件下在时刻t+1转移到状态qj的概率.
    在这里插入图片描述
    B是观测概率矩阵,bij是在时刻t处于状态qj的条件下生成观测vk的概率.
    在这里插入图片描述
    π是初始状态概率向量πi,π=(πi)表示时刻t=1处于状态qi的概率.隐马尔可夫模型由初始状态概率向量π,状态转移概率矩阵A以及观测概率矩阵B确定.π和A决定即隐藏的马尔可夫链,生成不可观测的状态序列.B决定如何从状态生成观测,与状态序列综合确定了观测序列.因此,隐马尔可夫模型可以用三元符号表示.
    在这里插入图片描述
    隐马尔可夫模型作了两个基本假设:

    1、齐次马尔可夫性假设:假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前一时刻的状态.

    2、观测独立性假设:假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态.
    隐马尔可夫模型有三个基本问题,即概率计算问题,学习问题,预测问题.
    概率计算问题:给定模型
    在这里插入图片描述
    和观测序列,计算在模型λ下观测序列
    在这里插入图片描述
    出现的概率P(O|λ).
    1、直接计算法:最直接的方法是列举所有可能长度为T的状态序列,求各个状态序列I与观测序列O的联合概率,但计算量太大,实际操作不可行.
    2、前向算法:定义到时刻t部分观测序列为o1~ot且状态为qi的概率为前向概率,记作
    在这里插入图片描述在这里插入图片描述3、后向算法:定义在时刻t状态为qi的条件下,从t+1到T的部分观测序列为oi+1~oT的概率为后向概率,记作
    在这里插入图片描述
    在这里插入图片描述
    学习算法:已知观测序列
    在这里插入图片描述
    估计模型的参数
    在这里插入图片描述
    使得在该模型下观测序列概率P(O|λ)最大.根据训练数据是否包括观察序列对应的状态序列分别由监督学习与非监督学习实现.
    **1、监督学习:**估计转移概率
    在这里插入图片描述
    和观测概率
    在这里插入图片描述
    初始状态概率πi的估计为S个样本中初始状态为qi的频率.
    2、非监督学习(Baum-Welch算法):将观测序列数据看作观测数据O,状态序列数据看作不可观测的隐数据I.首先确定完全数据的对数似然函数.
    在这里插入图片描述
    求Q函数
    在这里插入图片描述
    用拉格朗日乘子法极大化Q函数求模型参数
    在这里插入图片描述预测问题:也称为解码问题.已知模型和观测序列求对给定观测序列条件概率P(I|O)最大的状态序列.

    1、近似算法: 在每个时刻t选择在该时刻最有可能出现的状态it*,从而得到一个状态序列作为预测的结果.优点是计算简单,缺点是不能保证状态序列整体是最有可能的状态序列.

    2、维特比算法:用动态规划求概率最大路径,这一条路径对应着一个状态序列.从t=1开始,递推地计算在时刻t状态为i的各条部分路径的最大概率,直至得到时刻t=T状态为i的各条路径的最大概率.时刻t=T的最大概率即为最优路径的概率P*,最优路径的终结点it*也同时得到,之后从终结点开始由后向前逐步求得结点,得到最优路径.

    统计学习方法总结

    在这里插入图片描述

    神经网络

    神经元(感知器)接收到来自n个其他神经元传递过来的输入信号,这些输入信号通过带权重的连接进行传递,神经元将接收到的总输入值与神经元的阈值进行比较,然后通过激活函数处理以产生神经元的输出.把许多个这样的神经元按一定的层次结构连接起来就得到了神经网络.一般使用反向传播(BP)算法来进行训练.

    反向传播(BP)算法:

    1、前向传播:将训练集数据输入,经过隐藏层,到达输出层并输出结果.

    2、计算估计值与实际值之间的误差,并将该误差从输出层向输入层反向传播.

    3、在反向传播的过程中,根据误差使用梯度下降与链式法则调整各种参数的值.

    4、不断迭代直至收敛.
    深度神经网络(DNN):可以理解为有很多隐藏层的神经网络.DNN内部分为输入层(第一层),隐藏层,输出层(最后一层).层与层之间是全连接的.

    卷积神经网络(CNN):一般用于图像识别.通过卷积核和感受野的乘积形成卷积后的输出.在每一个卷积层之后,通常会使用一个ReLU(修正线性单元)函数来把所有的负激活都变为零.在几个卷积层之后也许会用一个池化层(采样层)来输出过滤器卷积计算的每个子区域中的最大数字或平均值.

    循环神经网络(RNN):如果训练样本输入是连续序列,则DNN和CNN不好解决.RNN假设样本是基于序列的,对应的输入是样本序列中的x(t),而模型在序列索引号t位置的隐藏状态h(t)由x(t)和h(t-1)共同决定.在任意序列索引号t有对应的模型预测输出o(t).也就是说,RNN是包含循环的网络,允许信息的持久化.
    在这里插入图片描述**长短期记忆网络(LSTM)?*一种特殊的RNN,可以学习长期依赖信息.

    K-Means

    K-Means是无监督的聚类算法.思想是对于给定的样本集,按照样本之间的距离大小将样本集划分为K个簇,让簇内的点尽量紧密地连在一起,而让簇间的距离尽量的大.

    传统算法:

    1、用先验知识或交叉验证选择一个合适的k值.
    2、随机选择k个样本作为初始的质心.注意初始化质心的选择对最后的聚类结果和运行时间都有很大的影响.
    3、计算每个样本点和各个质心的距离,将样本点标记为距离最小的质心所对应的簇.
    4、重新计算每个簇的质心,取该簇中每个点位置的平均值.
    5、重复2,3,4步直到k个质心都没有发生变化为止.

    K-Means++

    用于优化随机初始化质心的方法
    1、从输入样本点中随机选择一个点作为第一个质心.
    2、计算每一个样本点到已选择的质心中最近质心的距离D(x).
    3、选择一个新的样本点作为新的质心,选择原则是D(x)越大的点被选中的概率越大.
    4、重复2和3直到选出k个质心.

    Elkan K-Means

    利用两边之和大于第三边以及两边之差小于第三边来减少距离的计算.不适用于特征稀疏的情况.

    Mini Batch K-Means

    样本量很大时,只用其中的一部分来做传统的K-Means.一般多用几次该算法,从不同的随即采样中选择最优的聚类簇.

    Bagging

    Bagging的弱学习器之间没有boosting那样的联系,它的特点在于**“随机采样”,也就是有放回采样.因此泛化能力**很强.一般会随机采集和训练集样本数一样个数的样本.假设有m个样本,且采集m次,当m趋向无穷大时不被采集到的数据占1/e,也就是36.8%,称为袋外数据,可以用来检测模型的泛化能力.Bagging对于弱学习器没有限制,一般采用决策树和神经网络.

    算法:

    1、对于t=1~T,对训练数据进行第t次随机采样,共采集m次,得到包含m个样本的采样集Dm.
    2、用采样集Dm训练第m个弱学习器Gm(x)
    3、如果是分类,则用简单投票法.如果是回归,则取T个弱学习器结果的平均值.
    **随机森林:**使用CART决策树作为弱学习器,然后每次不从n个样本特征中选择最优特征,而是从随机选择的nsub个样本特征中来选择.一般用交叉验证来获取合适的nsub值.

    Apriori

    Apriori是常用的挖掘出数据关联规则的算法,用于找出数据值中频繁出现的数据集合.一般使用支持度或者支持度与置信度的组合作为评估标准.
    支持度:几个关联的数据在数据集中出现的次数占总数据集的比重
    在这里插入图片描述
    置信度:一个数据出现后.另一个数据出现的概率
    在这里插入图片描述
    Apriori算法的目标是找到最大的K项频繁集.假设使用支持度来作为评估标准,首先搜索出候选1项集及对应的支持度,剪枝去掉低于支持度的1项集,得到频繁1项集.然后对剩下的频繁1项集进行连接,得到候选的频繁2项集…以此类推,不断迭代,直到无法找到频繁k+1项集为止,对应的频繁k项集的集合即为输出结果.

    降维方法

    主成分分析(PCA):降维,不断选择与已有坐标轴正交且方差最大的坐标轴.
    奇异值分解(SVD):矩阵分解,降维,推荐系统.
    线性判别分析(LDA)

    展开全文
  • 李航统计学习方法总结与整理

    千次阅读 2019-03-26 22:22:18
    感知机(perception):二类分类的线性模型,输入为实例的特征向量,输出为实例的类别,取+1,-1。 对应于输入空间中将样本实例分成正负两类的分离超平面,属于判别模型。 其损失函数为:所有误分类点到分类超平面...

    感知机(perception):二类分类的线性模型,输入为实例的特征向量,输出为实例的类别,取+1,-1。

    对应于输入空间中将样本实例分成正负两类的分离超平面,属于判别模型。

    其损失函数为:所有误分类点到分类超平面的距离总和。目的为最小化这个距离总和。

                                                       \small L(w,b) = -\sum_{x_{i} \in M}y_{i}(w\cdot x+b)

    其中,\small -y_{i}(w\cdot x+b) 为误分类点到分离超平面距离。L 是 w, b 的连续可导函数。

    其包括原始形式和对偶形式,采用随机梯度下降法进行求解。首先任意选择一个超平面w0,b0,然后使用梯度下降法不断的极小化目标函数,其过程不是一次使所有的M个点的梯度下降,而是随机选择一个误分类点使其梯度下降,这样以来随机梯度下降会存在震荡,但整体趋势是下降的,算法本身是收敛的。

                                               \small \begin{matrix} \bigtriangledown_{w}L(w,b) = -\sum_{x_{i}\in M}y_{i}x_{i}&\: \: \: \: \: w\leftarrow w+\eta y_{i}x_{i} \\ \bigtriangledown_{b}L(w,b) = -\sum_{x_{i}\in M}y_{i}&\: \: \: \: \: b\leftarrow w+\eta y_{i} \end{matrix}

    无法显示

     对偶形式的基本思想是将w和b表示为实例xi和标记yi的线性组合,通过求其解系求得w和b,本质是用\small \alpha代替w属于全局数据求解

    由感知机模型可以进一步推出支持向量机

    支持向量机(SVM):是一种二分类模型,定义在特征空间上的建个最大的线性分类器,这也是与感知机的区别:求间隔最大化。

    支持向量机的学习策略就是间隔最大化,可形式化为求解一个凸二次规划问题,也等价于正则化的合页损失函数最小化问题。

    线性可分支持向量机:硬间隔最大化

    \large \begin{matrix} {functional \, margin} : \hat{\gamma}_{i} = y_{i}(w \cdot x+b) \, \, \, \Rightarrow \hat{\gamma} = \min_{i=1,2,...,N} \hat{\gamma}_{i} \\ {geometic \, margin}:\gamma_{i} = y_{i}\left(\tfrac{w}{||w||} \cdot x_{i}+\tfrac{b}{||w||} \right) \Rightarrow \gamma = \min_{i=1,2,...,N} \gamma_{i} \end{matrix}

    则:

    \large \max_{w,b} \gamma\;\;\;\;s.t.\;\;\; y_{i}\left(\tfrac{w}{||w||} \cdot x_{i}+\tfrac{b}{||w||} \right)\geqslant \gamma, i=1,2,...,N\\ \Rightarrow \max_{w,b} \tfrac{\hat{\gamma}}{||w||}\;\;\;\;s.t.\;\;\; y_{i}\left(w \cdot x_{i}+b \right)\geqslant \hat{\gamma}, i=1,2,...,N\\ \xrightarrow{\hat{\gamma} =1,max\tfrac{1}{||w||}\Leftrightarrow min1/2||w||^{2}} \min_{w,b} \tfrac{1}{2}||w||^{2}\;\;\;\;s.t.\;\;\; y_{i}\left(w \cdot x_{i}+b \right)-1\geqslant 0

    线性支持向量机:软间隔最大化

    \large \min_{w,b,\xi} \tfrac{1}{2}\left \| w \right \|^{2}+C\sum_{i=1}^{N}\xi_{i}\\\\ s.t.\\ y_{i}\left(w \cdot x_{i}+b \right)\geqslant 1-\xi_{i},\;\;\;i=1,2,...,N\\ \xi_{i}\geqslant 0 \;\;\;i=1,2,...,NNOTE: w的解唯一,b的解不唯一,存在于一个区间中

     

    非线性支持向量机:核函数 + 软间隔最大化

    通过非线性变换将非线性问题转化为线性问题。

    这里引入了核函数将输入空间映射为特征空间,核函数:\large K(x,z) = \phi(x) \cdot \phi(z), 在学习与预测中只定义核函数,不显示定义函数 \large \phi 

    常用核函数

    多项式核函数:

                                                   \large K(x,z)=(x \cdot z +1)^{p}

    ,对应的支持向量机是一个p次多项式分类器,分类决策函数为:

                                          \large f(x) = sign\left( \sum_{i=1}^{N_{s}}\alpha_{i}^{*}y_{i}(x_{i} \cdot x+1)^{p} +b^{*} \right )

    高斯核函数:

                                                   \large K(x,z)=\exp\left(-\tfrac{\left\|x-z\right\|^{2}}{2\sigma^{2}} \right )

    对应的支持向量机为高斯径向基函数分类器,分类决策函数为:

                                         \large f(x) = sign\left( \sum_{i=1}^{N_{s}}\alpha_{i}^{*}y_{i}\exp\left(-\tfrac{\left\|x-z\right\|^{2}}{2\sigma^{2}} \right )+b^{*} \right )

    字符串核函数:

                                  \large k_{n}(s,t) = \sum_{u \in \Sigma^{n}}[\phi_{n}(s)]_{u} [\phi_{n}(t)]_{u} =\sum_{u \in \Sigma^{n}}\sum_{(i,j):s(i)=t(j)=u} \lambda^{l(i)}\lambda^{l(j)}


           

    原始问题:  对偶问题:
    \large \min_{x \in \mathbb{R}^{n}}f(x)\\ \\ s.t. \\c_{i}(x)\leqslant 0,\;\;\;i ={1,2,...,k}\\ h_{j}(x)=0,\;\;\;j=1,2,...,l  \large \max_{\alpha, \beta}\theta_{D}(\alpha, \beta) =\max_{\alpha, \beta}\min_{x}L(x, \alpha, \beta)\\ \\s.t.\;\;\; \alpha_{i}\geqslant 0,\;\;\;i=1,2,...,k

     

    KKT(Karush-Kuhn-Tucker)条件:

    对原始问题和对偶问题,如果函数 f(x) 和ci(x) 是凸函数,hj(x) 是仿射函数,并且不等式约束ci(x)是严格可行的,则\large x^{*},\alpha^{*},\beta^{*} 分别是原始问题和对偶问题的解的充分必要条件是\large x^{*},\alpha^{*},\beta^{*}满足以下条件:
                                                                          \large \center \triangledown _{x}L({x^{*},\alpha^{*},\beta^{*}}) = 0\\ \alpha_{i}^{*} c_{i}({x^{*})=0,\;\;\;i=1,2,...,k\\ c_{i}({x^{*})\leq 0,\;\;\;i=1,2,...,k\\ \alpha_{i}^{*}\geq 0,\;\;\;i=1,2,...,k\\ h_{j}({x^{*})=0,\;\;\;i=1,2,...,k

    且,\large \alpha_{i}\geq 0,\;\;\;i=1,2,...,k 是对偶互补条件,即:若 \large \alpha_{i}^{*}> 0,则 \large c_{i}({x^{*})=0


    最后给出求解svm的SMO算法:

    SMO算法假设如果所有的变量的解都满足KKT条件,则此问题的解就找到了。否则选择两个变量,固定其他变量,针对这两个变量构建一个二次规划问题,这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解,因为这会使得原始二次规划问题的目标函数值变得更小。重要的是,这时子问题可以通过解析方法求解从而加快整个算法的计算速度。子问题有两个变量,一个是违反KKT条件最严重的一个,另一个由约束条件自动确定。如此,SMO算法将原问题不断分解为子问题并对子问题求解,进而达到求解原问题的目的。

     

    展开全文
  • 最近开始阅读李航老师的经典著作《统计学习方法》,现将其中自认为较为重要的点写出来,一个是作为回忆复习,二一个是希望能够分享给更多人。第一次写博客,如有错误,希望多包涵。 第一章统计学习方法概论 个人...

        最近开始阅读李航老师的经典著作《统计学习方法》,现将其中自认为较为重要的点写出来,一个是作为回忆复习,二一个是希望能够分享给更多人。第一次写博客,如有错误,希望多包涵。

       第一章统计学习方法概论

        个人认为第一章主要介绍的是机器学习中一些最为基本的概念和重要的要素,比方说监督学习,假设空间,损失函数,风险函数(期望风险),经验风险,结构风险,正则化,过拟合,泛化误差这些概念。非常好理解,而且只用一些比较简单的数学表示,从字面上到数学公式可以构建一个比较直观的联系。

    下面给出学习之后我个人觉得很重要的三个推导

    一 由经验风险最小化推导极大似然估



    二 由结构风险最小化推导最大后验概率:



    三 证明二类分类问题的泛化误差上界:

    无限个函数的情况没有讨论。

    问题一:书上说当模型是条件概率分布,损失函数是对数损失函数,结构风险最小化就等价于MAP,但是上面给出了损失函数是平方损失函数,结果也是结构风险最小化。也就是似然概率服从高斯分布时的推导。

    问题二:推导泛化误差上界过程中那个N,是如何从分子跑到分母的,还有就是hoeffding不等式给的是随机变量之和,怎么带成期望风险和经验风险的?那个1/N那里去了?是不等式左边那个N吗?



    展开全文
  • 作者:Demon的黑与白  来源:CSDN  ...   统计学习方法资源汇总 历时近半年《统计学习方法》的学习,今天告一段落。也没什么好说的,在学习过程遇到的一些坑,和搜集到的...本书介绍了10种主要的统计学习方法:感知...

    作者:Demon的黑与白 
    来源:CSDN 
    原文:https://blog.csdn.net/u014688145/article/details/60758291 


     

    统计学习方法资源汇总
    历时近半年《统计学习方法》的学习,今天告一段落。也没什么好说的,在学习过程遇到的一些坑,和搜集到的一些资料都在此汇总下,方便自己复习查阅。

    统计学习方法总结
    本书介绍了10种主要的统计学习方法:感知机、k邻近法、朴素贝叶斯、决策树、逻辑斯蒂回归与最大熵模型、支持向量机、提升发方法、EM算法、隐马尔可夫模型和条件随机场。这10中统计学习方法的特点概括总结在下表中。 

    alt text
    建议学习顺序

    1. 1.k近邻法

    所有方法中,最简单的模型,本质上并不算任何学习算法。参考博文有:

    1. 2. 决策树

    决策树的核心在于对熵的理解,算法有ID3,C4.5,以及CART算法。参考的博文有:

    1. 3.感知机和支持向量机

    这两部分都属于对几何空间的划分,可以放在一块学,支持向量机是感知机的升级版,该系列对数学的要求较高,是块难啃的骨头。参考博文有:

    在总结之余,有一篇大神的博文高达56万的阅读量,可谓是SVM典型之作,强烈推荐。

    1. 4.朴素贝叶斯方法

    深刻的贝叶斯原理,它的哲学绝对不是一行简单的贝叶斯公式所能描述的。参考博文有:

    又发掘了一篇大神之作,现居美国研究心理学,从他口中叙述的贝叶斯令人印象深刻,强烈推荐。

    1. 5.逻辑斯蒂回归模型与最大熵模型

    对熵有了一定的概念之后,以及了解了概率模型的极大似然估计方法后,便可以开始上述两个模型的学习了。参考博文有:

    关于最大熵模型,可以参考吴军之作《数学之美》,深入浅出。

    1. 6. EM算法及隐马尔可夫模型

    EM算法是解决含隐变量问题的迭代算法,是隐马尔可夫模型中Baum-Welch算法的一般形式,所以必须先学习EM算法,才能理解隐马尔可夫模型的学习算法。而隐马尔可夫模型则可归结为三个大问题:概率计算,参数学习,模型预测。参考的博文有:

    关于EM算法的参考资料较多,可以直接参看上述博文的参考文献。

    大神之作总是需要单独拎出来,说一下,讲的实在是太棒了。

    1. 7. 条件随机场

    它是这本书的终极大boss,谁叫它放在了最后呢,它可谓是朴素贝叶斯、逻辑斯蒂回归、最大熵模型及隐马尔科夫模型的综合升级版。所以必须最后一个学,否则云里雾里。参考博文有:

    那么这里就有一篇关于应用【概率模型】进行多元分类和序列标注的introduction,参考链接如下:

    能帮助你理解书中所提到的【判别模型】和【生成模型】的区别。

    1. 8. 提升方法

    指数损失函数的经典应用,三个臭皮匠顶个诸葛亮。参考博文有:

    提升方法,引入了计算机学习理论PAC,发现了一位大牛,毕业于浙江大学,留美博士,链接如下:

    机器学习牛博推荐
    这一部分,推荐几位我认为在机器学习领域的大牛,呵呵,看着他们的博客长大,感觉自己差点变牛了,然而还差一大截,唉。

    码农场: http://www.hankcs.com/ 
    他总结了《统计学习方法》中的所有章节,基本上是抄书,但是每个章节都有相应的代码,我博文中的代码基本上全来源于该博文,是开源项目NLP的作者,牛!

    我爱自然语言处理 : http://www.52nlp.cn 
    里面有很多统计学中各种分布的知识,非常深刻有趣,大部分资源也可以从中找。

    阮一峰的网络日志 : http://www.ruanyifeng.com/blog/ 
    上海财大经济学博士,非常博学,出版《ECMAScript 6入门》、《黑客与画家》、《软件随想录》等等。

    CSDN July 大神:http://blog.csdn.net/v_july_v/article/details/7624837 
    七月在线的CEO,专注于机器学习的教学,看了他的SVM三重境界,变成了他的小粉。对算法也颇有研究,强烈推荐。

    Free Mind : http://blog.pluskid.org/?p=772 
    浙大本科硕士,留美深造,数学功底强至令人折服,不怕虐可以看看。

    刘未鹏 | Mind Hacks 思维改变生活 : http://mindhacks.cn/ 
    南大本科,现依旧在美国,所写文章深刻而哲学,喜欢研究认知心理学,但在机器学习领域也有深刻的认识,所谓知己知彼百战百胜,对如何学习有着自己独特的见解。

    优化算法专栏:http://blog.csdn.net/column/details/optimization-a.html 
    zouxy09的专栏:http://blog.csdn.net/zouxy09

    未完待续
    更新进行时…
    --------------------- 

     

    展开全文
  • 统计学习方法概论

    2020-10-20 09:57:47
    1、统计学习(statistical learning)也称为统计机器学习,是关于计算机基于数据构建概率统计模型并运用模型对数据进行分析预测的一门学科,主要特点有: 统计学习以计算机及网络为平台,建立在计算机及网络上; ...
  • ##《统计学习方法》各章节代码实现与课后习题参考解答 章节 代码 课后习题 第1章 统计学习方法概论(LeastSquaresMethod) 传送门 传送门 第2章 感知机(Perceptron) 传送门 传送门 ...
  • 【机器学习】李航 统计学习方法 知识点总结

    万次阅读 多人点赞 2020-01-17 16:48:41
    机器学习实战代码 阅读目录 知识点 感知机 k近邻法 朴素贝叶斯 决策树 logistic回归和最大熵...因为要准备面试,本文以李航的《统计学习方法》为主,结合西瓜书等其他资料对机器学习知识做一个整理. 知识点...
  • 统计学习方法》——李航 学习大纲

    万次阅读 多人点赞 2018-01-27 17:40:38
    最近在学习李航写的统计学习方法概论, 每一章都用xmind理清了思路,括号里是书里的公式,第一次写博文,敬请指教~~~~ 第一章 统计学习方法论 第二章 感知机 每个方法其实只需要着重掌握三要素和...
  • 1. 统计学习概述 2. 统计学习三要素 3. 模型的评估与选择 4. 分类问题、标注问题与回归问题   1. 统计学习概述 (1)概念:统计学习是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测分析的...
  • 第一章 统计学习方法概论 Blog 第二章 感知机 Blog 第三章 K近邻法 Blog 第四章 朴素贝叶斯法 Blog 第五章 决策树 Blog 第六章 逻辑斯蒂回归与最大熵模型 第七章 支持向量机 Blog 第八章 提升方法 ...
  • 李航 统计学习方法 课后习题答案

    万次阅读 多人点赞 2018-07-09 22:09:29
    第一章 https://blog.csdn.net/familyshizhouna/article/details/70160782 第二章 2.1-2.2 https://blog.csdn.net/cracker180/article/details/78778305 2.3 https://blog.csdn.net/xiaoxiao_wen/arti...
  • 李航—统计学习方法第四章课后答案

    万次阅读 多人点赞 2017-01-05 20:56:39
    4.1 用极大似然估计法推导朴素贝叶斯法中的先验概率估计公式和条件概率估计公式
  • 一转眼,从开始接触机器学习,到现在被琐事左右,不得不放下李航老师的《统计学习方法》,快五个月了。这五个月里,开头的一个月是我最快活的时候,全身心地享受统计学习方法带来的种种思维的乐趣,妙不可言。 ...
  • 2.3 题目:证明一下定理:样本集线性可分的充分必要条件是正实例点集和负实例点集所构成的凸壳互不相交。 这里给出比较精确的数学证明,主要参考凸优化相关理论
  • 统计学习基础(ESL)中文版

    万次阅读 多人点赞 2018-11-25 17:52:58
    ESL 指的是 The Elements of Statistical Learning。因为自己也是统计学专业,所以想研读这本书,同时实现书中的算法及其例子,并尝试解决习题。 说明 参考文献保留原书的写法,如 “Efron and Tibshirani (1993)”...
  • 统计学习笔记(1)——统计学习方法概论

    万次阅读 多人点赞 2014-04-17 11:37:42
    1.统计学习  统计学习是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科,也称统计机器学习。统计学习是数据驱动的学科。统计学习是一门概率论、统计学、信息论、计算理论、最优化...
  • 统计学习方法》勘误表

    千次阅读 2016-10-01 21:41:14
    去年刚接触机器学习时拜读过李航老师的统计学习方法,很有收获。 最近看到李航老师更新了新的勘误表,转载作为收藏 原文链接 http://blog.sina.com.cn/s/blog_7ad48fee01017dpi.html#cmt_3285959
  • 统计学习方法-李航(笔记整理)一

    千次阅读 2017-02-22 10:59:18
    1、特点 统计学习以数据为研究对象(数据驱动),以方法为中心,目的是为了对数据进行...统计学习方法三要素:模型,策略,算法 统计学习方法步骤: 得到一个有限训练数据集确定包含所有可能的模型假设空间,即学习
1 2 3 4 5 ... 20
收藏数 314,566
精华内容 125,826
关键字:

统计学习方法