西瓜书阅读

西瓜书阅读记录(2.0)

2018年1月19日提交1.0
2018年3月1日重新持续更新2.0
2018年3月15日完成1-11章的阅读,下面开始阅读<统计学习方法>

=============================================

第一章绪论

1.归纳偏好

奥卡姆剃刀:若有多个假设与观察一致,则选择最简单的那个.

2.NEL定理(No Free Lunch):脱离具体问题,空泛的谈论”什么学习算法更好”毫无意义.

第二章.模型评估与选择

1.过拟合:当学习器把训练样本学得”太好了”的时候,很可能已经把训练样本本身的一些特点当作了所有潜在样本都会具有的一般性质.

2.欠拟合:学习能力低下造成的,解决办法:在决策树学习中扩展分支/在神经网络学习中增加训练轮数等.

3.评估方法:

3.1 测试集应该尽可能与训练集互斥,即测试样本尽量不再训练集中出现,未在训练过程中使用过.

3.2 划分训练集和测试集的方法: a)留出法,直接将数据集划分为互斥的两个集合;b)交叉验证法(k-fold validation),先将数据集D划分为k个大小相似的互斥子集,每个子集都尽可能保持数据分布的一致性.然后,每次用k-1个子集的并集作为训练集,余下的那个子集作为测试集,进行k次训练和测试,最终返回这k个测试结果的均值.(k的通常取值为10,并且通常对k-fold validation做多次,一般为10次10折交叉验证法).c)自助法(bootstrapping),给定包含m个样本的数据集D,对它进行采样产生数据集D’:每次随即从D中挑选一个样本,将其拷贝放入D’,然后再将该样本放回初始数据集D中,使得该样本在下次采样时仍有可能被采到;这个过程重复执行m次后,我们就得到了包含m个样本的数据集D’.

3.3 调参参数类型:算法参数(超参)和模型参数.

模型参数是学习得到的,作为模型的一部分保存
算法参数是算法中的参数,是模型外部的配置,如:神经网络中的学习速率,支持向量机中的C和sigma参数.

4.性能度量:

4.1 回归任务最常用的性能度量是”均方误差”:

$E(f;D)=\frac{1}{m}\sum\_{i=1}^{m}(f(x\_i)-y\_i)^2$$. 4.2 评价标准: 错误率与精度,查全率和查准率.错误率和精度指多少样本被判错,多少样本被判错;查全率和查准率指模型判断为正例中有多少比例是真正的正例,模型判断为反例中有多少为真正的反例.(两种评价标准对应的需求不一样) | 真实情况 | 预测结果正例 | 预测结果反例 | | :--: | :--: | :--: | | 正例 | TP(真正例) | FN(反正例) | | 反例 | FP(假正例) | TN(真正例) | $$P(查准率) = TP / (TP + FP)$ $R(查全率) = TP / (TP + FN)$

4.3 P-R图:以查准率为纵坐标,以查全率为横坐标.在进行比较时,若一个学习器的P-R曲线被另一个学习器的曲线完全”包住”,则可断言后者的性能优于前者. “平衡点”(BEP):当查准率 = 查全率时的取值,即为平衡点.当两个曲线有交点时,可通过比较平衡点的取值.

4.4 F1-measure:

$F1 = 2 * TP / (样例总数 + TP - TN)$

(补充): $F_\beta = \frac{1+\beta^2\times{P}\times{R}}{\beta^2\times{P}+R}$ ,当$\beta=1$时,退化为标准的F1;$\beta>1$时查全率有更大影响;$\beta$&lt1时查准率有更大影响.

4.5 查准率和查全率的应用目的区别:例如在商品推荐系统中,为了尽可能少打扰用户,更希望推荐内容的确是用户感兴趣的,此时查准率更重要;而在逃犯信息检索系统中,更希望尽可能少漏掉逃犯,此时查全率更重要.

4.6 对于多分类考察查准率和查全率,基于两种方式:a)先在各个混淆矩阵上计算(P₁,R₁),(P₂,R₂),…,(P_n,R_n),然后再计算平均值得到”宏查准率”和”宏查全率”.b)先将各混淆矩阵上的对应元素计算平均,再基于这些平均值计算出”微查准率”和”微查全率”.

4.7 ROC和AUC: ROC体现了综合考虑学习器在不同任务下的”期望泛化性能”的好坏,或者说,”一般情况下”泛化性能的好坏.ROC曲线的纵轴是”真正例率(TPR)”,横轴是”假正例率(FPR)”,两者分别定义为TPR=TP / (TP + FN), FPR=FP / (TN + FP). 和P-R图相似,若一个学习器的ROC曲线被另一个学习器的曲线完全”包住”,则可断言后者性能优于前者.若两个学习器的ROC曲线发生交叉,则难以一般性地断言两者孰优孰劣,此时如果一定要进行比较,则较为合理的判据是比较ROC曲线下的面积,即AUC.

$AUC = \frac{1}{2}\sum\_{i=1}^{m-1}(x\_{i+1} - x\_i) \cdot(y\_i + y\_{i+1})$$. **5.比较检验(待丰富)**:假设检验/交叉验证t检验/McNemar检验/Friedman检验与Nemenyi后续检验 **6.偏差与方差**: 6.1 泛化误差可分为偏差/方差与噪声之和.**偏差**度量了学习算法的期望预测与真实结果的偏离程度,即刻画了学习算法本身的拟合能力;**方差**度量了同样大小的训练集的变动所导致的学习性能的变化,即刻画了数据扰动所造成的影响;**噪声**则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界,即刻画了学习问题本身的难度. **(2.0补充)** 7.训练误差(经验误差):学习器在训练集上的误差 8.泛化误差:学习器在新样本上的误差 *** ### 第三章.线性模型 1.线性模型:给定由d个属性描述的示例X=(x1;x2;...;xd),其中xi是X在第i个属性上的取值,线性模型试图**学得一个通过属性的线性组合来进行预测的函数**,即 $$f(\textbf{x})=w\_1x\_1+w\_2x\_2+...+w\_dx\_d+b$

写成向量形式:

$f(\textbf{x})=\textbf{w}^T+b$

其中,w=(w₁;w₂;…;w_d).w和b学得之后,模型就得以确定.

2.线性回归

2.1 概念:线性回归试图学得一个线性模型以尽可能准确地预测实值输出标记.

2.2 均方误差是回归任务中最常用的性能度量.基于均方误差来求解模型的方法成为最小二乘法.

2.3 对于多元线性回归,可以利用最小二乘法来对w和b进行估计.

2.4 对数线性回归: 认为示例所对应的输出标记是在指数尺度上变化.

$lny=\textbf{w}^T+b$

实际上是试图让 $e^{w^Tx}+b$ 逼近y.

2.5 广义线性模型: $y=g^{-1}(\textbf{w}^T+b)$ (将输入空间上的真实值到输出空间上预测值的非线性函数映射)

3.对数几率回归

3.1 对数几率回归是一种”Sigmoid函数”.进而将回归问题转化为分类问题.

(补充):优化方法:极大似然估计;先构造极大似然函数,再利用梯度下降或牛顿法进行优化函数.

4.线性判别分析(待温故)

4.1 线性判别分析(Linear Discriminant Analysis),简称LDA,是一种经典的线性学习方法.LDA:给定训练样例集,设法将样例集投影到一条直线上,使得同类样例的投影点尽可能近/异类样例的投影点尽可能远;在对新样本进行分类时,将其投影到同样的这条直线上,再根据投影点的位置来确定新样本的类别.即,欲使同类样例的投影点尽可能接近,可以让同类样例投影点的协方差尽可能小;而欲使异类样例的投影点尽可能远离,可以让类中心之间的距离尽可能大.

4.2 奇异值: 特征值分解是提取矩阵特针很不错的方法,但是它只是针对方针而言的,对于非方阵矩阵,使用奇异值分解能适用于任何形式的矩阵.分解形式为:

$A\_{m\*n}=U\_{m\*m}\Sigma\_{m\*n}{V\_{n\*n}}^T(\Sigma\_{m\*n}为对角矩阵)$

5.多分类学习

5.1 多分类学习的基本思路是”拆解法”,即将多分类任务拆分为若干个二分类任务求解.最经典的拆分策略有三种:”一对一(One vs. One OvO)”,”一对其余(One vs. Rest,OvR)”和”多对多(Many vs. Many,简称MvM)”.

(补充)
5.2 类别不平衡问题:指的是分类任务中不同类别的训练样例数目差别很大的情况.
基本策略:

$\frac{y^{'}}{1-y^{'}}=\frac{y}{1-y}\times\frac{m^{-}}{m^{+}}$

解决方案:

1.直接对训练集里的反例样例进行”欠采样”(下采样),即去除一些反例使得正/反例数目接近,然后进行学习
2.对训练集里的正类样例进行”过采样”(上采样),即增加一些正例使得正/反例数目接近,然后再进行学习
3.直接基于原始训练集进行学习,但在用训练好的分类器进行预测时,将基本策略公式嵌入到决策过程中,称为”阈值移动”

第四章决策树

4.1 信息熵是度量样本集合纯度最常用的一种指标.假定当前样本集合D中第k类样本所占的比例为p_k(k=1,2,…,|Y|),则D的信息熵为

$Ent(D)=-\sum\_{k=1}^{|Y|}p\_klog\_2p\_k$

Ent(D)的值越小,则D的纯度越高.

4.2 假定离散属性a有V个可能的取值{a¹,a²,…,a^V},若使用a对样本集D进行划分,则会产生V个分支结点,其中第v个分支结点包含了D中所有在属性a上取值为a^v,记为D^v.于是可以计算出用属性a对样本集D进行划分所获得的信息增益

$Gain(D,a)=Ent(D)-\sum\_{v=1}^{V}\frac{|D|^v}{|D|}Ent(D^v)$$. 一般而言,信息增益越大,则意味着使用属性a来进行划分所获得的"纯度提升"越大.因此,可利用信息增益来进行决策树的划分属性选择. 4.3 **ID3**决策树学习算法就是以**信息增益**为准则来选择划分属性.(信息增益准则对可取值数目较多的属性有所偏好) 4.4 **C4.5**决策树算法不直接使用信息增益,而是使用"**增益率**"来选择最优划分属性.增益率定义为: $$GainRatio(D,a)=\frac{Gain(D,a)}{IV(a)}$$,其中, $$IV(a)=-\sum\_{v=1}^{V}\frac{|D|^v}{|D|}log\_2\frac{|D|^v}{|D|}$$,IV(a)称为属性a的"固有值".增益率对属性数目偏少的属性有所偏好. (**补充**):C4.5算法并不是直接选择增益率最大的候选划分属性,而是使用了启发式算法:**先从候选划分属性中找出信息增益高于平均水平的属性,然后再从中选择增益率最高的.** 4.5 **CART决策树**使用"基尼指数"来选择划分属性. **4.6 剪枝处理** 4.6.1 剪枝是决策树学习算法对付"过拟合"的一个重要手段. 4.6.2 剪枝策略包括:**预剪枝**和**后剪枝**. 4.6.3 **预剪枝**是在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能的提升,则停止划分并将当前结点标记为叶结点;**后剪枝**则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点. 4.6.3 后剪枝决策树通常比预剪枝决策树保留了更多的分支.一般情形下,后剪枝决策树的欠拟合风险很小,泛化性能往往优于预剪枝决策树.但其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多. **(如何判断决策树泛化性能能否提升?)**:采用留出法,即预留一部分数据用作"验证集"以进行性能评估. **4.7 连续与缺失值** 4.7.1 连续值处理: 二分法.(也是基于信息增益来选择划分点).二分法切分出n-1个划分点,然后从这些划分点中选择信息增益最大的划分点. 4.7.2 缺失值处理: 简单来讲,通过样本中无缺失值样本来估计同一个有属性值缺失的样本被划入不同子结点的概率. **(补充)**:解决两个问题: * 1)如何在属性值缺失的情况下进行划分属性选择? * 2)给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分? 对于第一个问题,还是沿用信息增益来进行划分,借助无缺失值的样本. $$Gain(D,a)=\rho\*Gain(\tilde{D},a)=\rho\*(Ent(\tilde{D}-\sum\_{v=1}^{V}\tilde{r\_{v}}Ent(\tilde{D}^v)))$

其中, $Ent(\tilde{D})=-\sum\_{k=1}^{|Y|}\tilde{p}\_{k}log\_2\tilde{p}\_k$ .(参考西瓜书Page86)

对于第二个问题,若样本x在划分属性a上的取值已知,则将x划入与其取值对应的子结点,且样本权值在子结点中保持为$W_x$.若样本x在划分属性a上的取值未知,则将x同时划入所有子结点,且样本权值在与属性值$a^v$对应的子结点调整为$\tilde{r_v}\cdot{w_x}$.

4.8 多变量决策树: 实现斜划分甚至更复杂的决策树.在多变量决策树的学习过程中,不是为每个非叶结点寻找一个最优划分属性,而是试图建立一个合适线性分类器.

第五章神经网络

1 神经网络的学习过程就是根据训练数据来调整神经元之间的连接权以及每个功能神经元的阈值.

2 感知机: 由两层神经元组成,输入层接受外界输入信号后传递给输出层,输出层是M-P神经元,亦称”阈值逻辑单元”. 对于非线性问题,需要考虑使用多层功能神经元.

3 误逆差传播算法(亦称反向传播算法,BP算法):BP算法是基于梯度下降策略,以目标的负梯度方向对参数进行调整.

4 累积BP算法的目标是最小化训练集D上的累积误差 $E=\frac{1}{m}\sum\_{k=1}^{m}E\_k$ .标准BP算法每次更新只针对单个样例,参数更新得非常频繁,而对不同样例进行更新的效果可能出现”抵消”现象.因此为了达到同样的累积误差极小点,标准BP算法往往需要进行更多次数的迭代.累积BP算法直接针对累积误差最小化,它在读取整个训练集D一遍后才对参数进行更新,其参数更新的频率低得多,但在很多任务中,累积误差下降到一定程度后,进一步下降会非常缓慢,这时标准BP往往会更快获得较好的解,尤其是在训练集D非常大时更明显.

5 BP神经网络经常遭遇过拟合,两种策略解决: a)早停,将数据分成训练集和验证集,训练集用来计算梯度/更新连接权和阈值,验证集用来估计误差,若训练集误差降低但验证集误差升高,则停止训练,同时返回具有最小验证集误差的连接权和阈值. b)正则化,其基本思想是在误差目标函数中增加一个用于描述网络负责度的部分.

6 神经网络采用一下策略”跳出”局部极小:

以多组不同参数值初始化多个神经网络,按标准方法训练后,取其中误差最小的解作为最终参数.
使用”模拟退火“,即以一定概率接受比当前解更差的结果.
使用随机梯度下降.与标准梯度下降精确计算梯度不同,随即梯度下降法在计算梯度时加入了随即因素,于是,即使陷入局部极小点,它计算出的梯度仍可能不为0,这样有机会跳出局部极小点继续搜索.

(补充):梯度下降:

1)批量梯度下降:每次使用全量的训练集样本来更新模型参数
2)随机梯度下降:每次从训练集中随机选择一个样本来进行学习
3)小批量梯度下降:每次更新速度与更新次数中间取得一个平衡，其每次更新从训练集中随机选择 m (m小于n) 个样本进行学习

7 其他常见神经网络

RBF网络(使用径向基函数作为隐层神经元激活函数,而输出层是对隐层神经元输出的线性组合.)
ART网络(竞争型学习是神经网络中一种常用的无监督学习策略,在使用该策略时,网络的输出神经元相互竞争,每一时刻仅有一个竞争获胜的神经元被激活,其他的神经元的状态被抑制.ART网络有比较层/识别层/识别阈值和重置模块构成.比较层负责接收输入样本,并将其传递给识别层神经元.识别层每个神经元对应一个模式类,神经元数目可在训练过程中动态增长以增加新的模式类)
SOM网络(一种竞争学习型的无监督神经网络,它能将高维输入数据映射到低维空间,同时保持输入数据在高维空间的拓扑结构.)
级联相关网络
Elman网络
Boltzmann机

8 深度学习:一般地，CNN的基本结构包括两层，其一为特征提取层，每个神经元的输入与前一层的局部接受域相连，并提取该局部的特征。一旦该局部特征被提取后，它与其它特征间的位置关系也随之确定下来；其二是特征映射层，网络的每个计算层由多个特征映射组成，每个特征映射是一个平面，平面上所有神经元的权值相等。特征映射结构采用影响函数核小的sigmoid函数作为卷积网络的激活函数，使得特征映射具有位移不变性。此外，由于一个映射面上的神经元共享权值，因而减少了网络自由参数的个数。卷积神经网络中的每一个卷积层都紧跟着一个用来求局部平均与二次提取的计算层，这种特有的两次特征提取结构减小了特征分辨率。CNN主要用来识别位移、缩放及其他形式扭曲不变性的二维图形.

8.1 卷积: 说白了,卷积操作就是一种加权求和.在卷积层中,通常包含若干个特征平面,每个特征平面由一些矩形排列的神经元组成,同一特征平面的神经共享单元共享权值,共享的权值就是卷积核.卷积核带来的直接好处减少网络各层之间的连接,同时降低了过拟合的风险.

8.2 池化: 也叫子采样,降维处理,减少了模型的参数.

(补充):神经网络的误差反向传播算法的推导需要重新看.

第六章支持向量机

第六章西瓜书

1.划分超平面:在样本空间中,划分超平面可通过如下线性方程来描述:

$w^Tx+b=0$$, 其中,$$w=(w\_1;w\_2;...;w\_d)$$为法向量;b为位移项,决定了超平面与原点之间的距离.将超平面记为(**w**,b),样本空间中任意点x到超平面(**w**,b)的距离为$$r=\frac{|w^T+b|}{||w||}$$. 2.**支持向量**:假设超平面(**w**,b)能将训练样本正确分类,即对于$$(x\_i,y\_i)\in{D}$$,若yi=+1,则有$$w^T+b>0$$;若yi=-1,则有$w^T+b<0$.令$w^T+b\geq{+1},y\_i=1$;$w^T+b\leq{+1},y\_i=-1$.距离超平面最近的这几个训练样本点使上述等号成立,它们被称为"支持向量".两个异类支持向量到超平面的距离之和为$$\gamma=\frac{2}{||w||}$$.它们被称为"间隔". 3.**支持向量机**:$min\_{w,b}\frac{1}{2}||w||^2,s.t. y\_i(w^Tx\_i+b)\geq{1},i=1,2,3,...,m.$. **(补充:)**SMO算法: * 选取一对需要更新的变量$\alpha\_{i}$和$\alpha\_{j}$ * 固定$\alpha\_{i}$和$\alpha\_{j}$以外的参数,求解拉格朗日函数后更新$\alpha\_{i}$和$\alpha\_{j}$ SMO算法先选取违背KKT条件程度最大的变量,第二个变量本应选择一个使目标函数值减小最快的变量,但由于比较各变量所对应的目标函数值减幅的复杂度过高,**因此SMO采用了一个启发式:使选取的两变量所对应样本之间的间隔最大.** 4.正定矩阵:实对称矩阵 5.二次规划问题:给定一个目标函数,找到n维的向量x,使得 $$minimize \frac{1}{2}x^TQx+c^Tx,subject to Ax\leq{b}$$.如果Q为半正定矩阵,那么该问题就是**凸二次规划问题**.凸二次规划问题,如果至少一个向量满足约束并且在可行域有下界,则凸二次规划问题就有一个全局最小值.如果Q是正定的,则这类二次规划为严格的凸二次规划问题,那么全局最小值就是唯一的. 6.对于凸二次规划问题解法:拉格朗日方法/Lemke方法,内点法,有效集法,椭球法等. 7.对偶问题:任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应,反之亦然.如果我们把其中一个叫原问题,则另一个就叫做它的对偶问题,并称这一对互相联系的两个问题为一对**对偶问题**. 8.核函数:当样本在原始样本空间中线性不可分时,可以将样本映射到更高维的特征空间中,使得样本在这个特征空间内线性可分.如果原始空间是有限维,那么一定存在一个高维特征空间使样本可分.即xi与xj在特征空间的内积等于它们在原始样本空间中通过函数*k(.,.)*计算的结果,这里的*k(.,.)*就是**核函数**.有了这样的函数,就不必计算高维甚至无穷维特征空间中的内积. 9.核函数类型: * 线性核 * 多项式核 * 高斯核(RBF核) * 拉普拉斯核 * Sigmoid核 **(补充)**:核函数的组合形式($k\_1(x)$为核函数): * 1.核函数的线性组合还是核函数 * 2.核函数的直积还是核函数$k\_1\times{k\_2}(x,z)=k\_1(x,z)k\_2(z)$仍是核函数 * 3.对任意函数$g(x)$,$k(x,z)=g(x)k\_1(x,z)g(z)$仍是核函数 **10.软间隔和正则化** 10.1 软间隔:在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分;退一步说,即便恰好找到了某个核函数使训练集在特征空间中可分,也很难判定这个"线性可分"是不是由过拟合造成的.缓解该问题的一个方法是允许支持向量机在一些样本上出错.支持向量机形式要求所有样本均满足约束,即所有样本都必须划分正确,这称为**"硬间隔"**.而**软间隔**允许某些样本不满足约束. **补充**:软间隔线性支持向量机优化目标为: 1.$$min\_{w,b}\frac{1}{2}{||w||}^2+C\sum\_{i=1}^{m}l\_{0/1}(y\_i(w^T+b)-1)$

2.C为惩罚参数,当C无穷大时,则迫使所有样本都满足约束.当C取有限值时,则允许有一些样本不满足约束.
3.$l_{0/1}$为0/1损失函数.
4.硬间隔和软间隔区别在于:前者是$0\leq{\alpha_i}\leq{C}$,后者是$0\leq{\alpha_i}$.
5.支持向量机模型都由两项构成:结构风险和经验风险.结构风险用于描述模型的某些性质,经验风险用于描述模型与训练数据的契合程度.为了降低模型复杂度和防止过拟合,通过$L_p$范数来正则化结构风险.

11.损失函数:

hinge损失
指数损失
对率损失

补充:SVR-支持向量回归

1)容忍$f(x)$与真实输出$y$之间有$\epsilon$的误差,通过这种方式来最大限度的包容尽可能多的点在内
2)目标函数的优化,依然用拉格朗日乘子法.

第六章统计学习方法

1.支持向量机学习方法包含构建由简至繁的模型:线性可分支持向量机,线性支持向量机及非线性支持向量机.当训练数据线性可分时,通过硬间隔最大化学习一个线性的分类器,即线性可分支持向量机,又称为硬间隔支持向量机;当训练数据近似线性可分时,通过软间隔最大化,也学习一个线性的分类器,即线性支持向量机,又称为软间隔支持向量机;当训练数据线性不可分时,通过核技巧及软间隔最大化,学习非线性支持向量机.

2.空间概念

2.1 线性空间(向量空间)

线性空间又称作向量空间,对于一个线性空间,知道”基”(相当于三维空间中的坐标系)便可确定空间中元素的坐标(即位置).线性空间之定义了加法和数乘元算.

2.2 赋范线性空间

定义了范数的线性空间(为了了解向量的长度)

2.3 内积空间

定义了内积的线性空间(为了了解向量的夹角)

2.4 欧式空间

定义了内积的实线性空间V为实内积空间或欧几里德空间.

2.5 Banach空间

完备的赋范线性空间

2.6 希尔伯特空间

希尔伯特空间是欧几里德空间的一个推广,其不再局限于有限维的情形.与欧几里德空间相仿,希尔伯特空间也是内积空间,其上有距离和角的概念,此外,希尔伯特空间还是一个完备的空间,其上所有的柯西序列等价于收敛序列,从而微积分中的大部分概念都可以无障碍地推广到希尔伯特空间中.

第七章提升方法(boosting)

提升方法是一种常用的统计学习方法,在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提升分类的性能.\
提升树是以分类树或回归树为基本分类器的提升方法. 以决策树为基函数的提升方法称为提升树,对分类问题决策树是二叉分类树,对回归问题决策树是二叉回归树.
提升树算法采用前向分步算法.
提升树利用加法模型与前向分步算法实现学习的优化过程,当损失函数是平方损失和指数损失函数时,每一步的优化是简单的.但对一般的损失函数而言,往往每一步优化并不容易,这里可以使用梯度提升算法. 其关键是利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值,拟合一个回归树.

第八章贝叶斯分类器

对分类任务来说,在所有相关概率都已知的理想情形下,贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记.
贝叶斯判定准则: 为了最小化总体风险,只需在每个样本上选择那个是条件风险最小的类别标记.(条件风险=期望损失).
极大似然估算后验概率,两种策略: 1) 给定样本x,可通过直接建模P(c|x)来预测c(从为x的类别标记),这样得到的是”判别式模型”; 2) 也可以先对联合概率分布P(x,c)建模,然后由此获得P(c|x),这样得到的是”生成式模型”;

4.求解贝叶斯分类器:朴素贝叶斯分类器.基于一个假设:所有属性之间相互独立

对于离散性属性:$P(x_i|c)=\frac{D_{c,x_i}}{D_c}$
对于连续性属性:$p(x_i|c)=\frac{1}{\sqrt{2\pi}\sigma_{c,i}}exp(-\frac{({x_i-\mu_{c,i}})^2}{2{\sigma_{c,i}}^2})$

5.为了避免其他属性携带的信息被训练集中未出现的属性值”抹去”,在估计概率值时通常要进行”平滑”,常用”拉普拉斯修正”.令N表示训练集D中可能的类别数,$N_i$表示第i个属性可能的取值数,则修正为:

$P(c)=\frac{|D_c|+1}{|D|+N}$
$P(x_i|c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i}$

6.如果任务对预测速度要求较高,则针对训练集将朴素贝叶斯分类器涉及的所有概率估值事先计算好存储起来.如果任务数据更替频繁,则可事先不进行任何训练,待收到预测请求时再根据当前数据集进行概率估值.如果数据不断增加,则可在现有估值的基础上,仅对新增样本的属性值所涉及的概率估值进行计数修正即可实现增量学习.

判别式模型常见的主要有：
Logistic Regression
SVM
Traditional Neural Networks
Nearest Neighbor
CRF
Linear Discriminant Analysis
Boosting
Linear Regression

产生式模型常见的主要有：
Gaussians
Naive Bayes
Mixtures of Multinomials
Mixtures of Gaussians
Mixtures of Experts
HMMs
Sigmoidal Belief Networks, Bayesian Networks
Markov Random Fields
Latent Dirichlet Allocation

(判别式模型和生成式模型:http://www.cnblogs.com/fanyabo/p/4067295.html)

补充::
1.贝叶斯最优分类器为:$h^*=argmax_{c\in{y}}P(c|x)$.要用贝叶斯判定准则来最小化决策风险,首先要获得后验概率$P(c|x)$,而这在现实生活中是难以直接获得的,机器学习所要实现的是基于有限的训练样本集尽可能准确地估计出后验概率.有两种策略:判别式模型和生成式模型.

2.判别式模型和生成式模型比较:
定义单个测试数据为$(c_0,x_0)$,$c_0$为测试数据的label,$x_0$为测试数据的feature

判别式模型(注重条件概率):它是训练完毕后,输入测试数据,判别模型直接给出的是$P(c|x_0)$.实际上是我们看了训练过的数据之后,学习到了对数据分步的后验知识,然后根据这个认识和测试样本的feature来决策.判别模型求解的思路是：条件分布———>模型参数后验概率最大———->（似然函数\cdot 参数先验）最大———->最大似然
生成式模型(注重联合分布概率):给定输入$x_0$,生成式模型可以给出输入和输出的联合分布$P(x_0,c_0)$.生成模型的求解思路是：联合分布———->求解类别先验概率和类别条件概率

3.半朴素贝叶斯分类器
3.1 目的:为了降低贝叶斯公式中的后验概率$P(c|x)$的困难,朴素贝叶斯分类器采用了属性条件独立的假设,但在现实任务中这个假设很难成立.
3.2 做法:适当考虑一部分属性间的相互依赖信息
3.3 策略:独依赖估计(One-Dependent Estimator)-ODE,就是假设每个属性在类别之外最多依赖于一个其他属性.$P(c|x)\propto{P(c)\prod_{i=1}^{d}P(x_i|c,pa_i))}$.相比朴素贝叶斯分类器,$x_i$多了一个依赖.$pa_i$为属性$x_i$所依赖的属性.
3.4 问题的关键就在于:如何确定每个属性的父属性,也就是所依赖的属性.
方案:

1.SPODE-所有的属性都依赖于同一个属性,称为”超父”,然后通过交叉验证等模型选择方法来确定超父属性
2.TAN-在最大带权生成树算法的基础上,将属性间依赖关系约简到一种树形结构.
- 1.计算任意两个结点的互信息$I(x_i,x_j|y)=\sum_{x_i,x_j;c\in{y}}P(x_i,x_j|c)log\frac{P(x_i,x_j|c)}{P(x_i|c)P(x_j|c)}$
- 2.以属性为结点构建完全图,任意两个结点之间边的权重设为$I(x_i,x_j|y)$
- 3.构建此完全图的最大带权生成树,挑选根变量,将边置为有向
- 4.加入类别结点y,增加从y到每个属性的有向边
3.AODE-一种基于集成学习机制,更为强大的独依赖分类器.AODE尝试将每个属性作为超父来构建SPODE,然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果.即$P(c|x)\propto{\sum_{i=1,|D_{x_i}|\geq{m^{‘}}}^{d}P(c,x_i)\prod_{j=1}^{d}P(x_j|c,x_i))}$

4.贝叶斯网
4.1 概念:借助有向无环图来刻画属性之间的依赖关系,并使用条件概率表来描述属性的联合概率分布.一个贝叶斯网B由结构G和参数$\theta$两部分构成,$\theta$定量描述变量的依赖关系.
4.2 结构:给定父结点集,贝叶斯网假设每个属性与它的非后裔属性独立,于是$B=<G,\theta>$将属性$x_1,x_2,…,x_d$的联合概率分布定义为$P_B(x_1,x_2,…,x_d)=\prod_{i=1}^{d}P_B(x_i|\pi_i)=\prod_{i=1}^{d}\theta_{x_i|\pi_i}$

第九章集成学习(提升方法)

1.概念介绍

1 集成学习方法大致分为两类: 1) 个体学习器之间存在强依赖关系,必须串行化生成的序列化方法; 2) 个体学习器间不存在强依赖关系,可同时生成的并行化方法. 1)的代表是Boosting;2)的代表是Bagging和”随机森林”;

1.2 Bagging是并行集成学习方法最著名的代表,训练基于自助采样法.

1.3 Bagging通常对分类任务使用简单投票法,对回归任务使用简单平均法.

1.4 随机森林(Random Forest)是Bagging的一个扩展变体,RF在以决策树为基学习器构建Bagging集成的基础上,进一步在决策树的训练过程中引入了随机属性选择.

补充:
1.5 集成中只包含同种类型的个体学习器称为”同质的”.同质集成中的学习器亦称”基学习器”,相应的学习算法称为”基学习算法”.集成也可包含不同类型的个体学习器,这样的集成是”异质的”.相应的个体学习器一般不称为基学习器,常成为组件学习器.

1.6 Important:要获得好的集成,个体学习器应“好而不同”,即个体学习器要有一定的”准确性”,即学习器不能太坏,并且要有”多样性”,即学习器间具有差异.

1.7 Boosting:

1.7.1 概念:Boosting是一族可将弱学习器提升为强学习器的算法.

1.7.1 工作机制:先从初始训练集训练出一个基学习器,再根据基学习器的表现对训练样本分布进行调整,使得先前基学习器做错的训练样本在后续受到更多关注,然后基于调整后的样本分布来训练下一个基学习器;如此重复,直至基学习器数目达到事先指定的值T,最终将这T个基学习器进行加权结合.

1.7.2 代表算法AdaBoost

推导:基于”加性模型”,即学习器的线性组合,$H(x)=\sum_{t=1}^{T}\alpha_th_t(x)$.训练T个基分类器,对上一轮分类错误的样本分配更多的权重.

1.8 Bagging和随机森林

1.8.1 概念:Bagging是并行式集成学习方法最著名的代表.直接基于自主采样法(bootstrap sampling),有放回的采样.

1.8.2 操作:Bagging对分类任务使用简单投票法,对回归任务使用简单平均法.

1.8.3 随机森林:是Bagging的一个扩展变体.RF在以决策树构建Bagging集成的基础上,进一步再决策树的训练过程中引入了随机属性选择.具体来说,传统决策树在选择划分属性时是在当前结点的属性集合中选择一个属性;而在RF中,对基决策树的每个结点,先从该结点的属性集合中随机选择一个包含k个属性的子集,然后再从这个子集中选择一个最优属性用于划分.

2.组合策略

2.1 平均法
包括简单平均法和加权平均法.加权平均法的权重一般是从训练数据中学习而得,但是加权平均法未必一定优于简单平均法.一般而言,在个体学习器性能相差较大时宜使用加权平均法,而在个体学习器性能相近是宜使用简单平均法.

2.2 投票法
包括绝对多数投票法,相对多数投票法及加权投票法.

2.3 学习法
当训练数据很多时,一种更为强大的结合策略是使用”学习法”,即通过另一个学习器来进行结合.Stacking是学习法的典型代表.Stacking先从初始数据集训练出初级学习器,然后”生成”一个新数据集用于训练次级学习器.在这个新数据集中,初级学习器的输出被当做样例输入特征,而初始样本的标记仍被当作样例标记.

第十章聚类

1.性能度量

1.1 聚类性能的度量有两类: 一类是将聚类结果与某个”参考模型”进行比较,称为”外部指标”.另一类是直接考察聚类结果而不利用任何参考模型,称为”内部指标”.

1.1 外部指标

1.2 a = |SS|,b=|SD|,c=|DS|,d=|DD|(关于SS,SD,DS和DD的解释参考书Page198),常用的三种性能度量:

Jaccard系数: $JC=\frac{a}{a+b+c}$
FM指数: $FMI=\sqrt{\frac{a}{a+b}\frac{a}{a+c}}$
$RI=\frac{2(a+d)}{m(m-1)}$
上述性能度量的结果均在[0,1]区间,值越大越好.

1.2内部指标
补充:通过考虑聚类结果的簇之间的距离
DBI指数和DI指数(DBI值越小越好,而DI值越大越好.)

2.聚类算法
2.1 原型聚类:k-means聚类,学习向量量化(LVQ)-有标记聚类,高斯混合聚类
2.2 密度聚类:DBSACN:1.找到所有的核心对象;2.从核心对象出发将密度可达点加入生成聚类簇
2.3 层次聚类:Hierarchical clustering:先将数据集中的每个样本看作一个初始聚类簇,然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并,不断重复,直到达到预设的聚类簇个数.

补充:3距离计算
3.1 距离度量函数满足以下性质:

非负性
同一性
对称性
直递性

3.2 常用的距离度量函数

Minkowski distance(闵可夫斯基距离)$dist_{mk}(x_i,x_j)=(\sum_{n}^{u=1}|x_{iu}-x_{ju}|^p)^\frac{1}{p}$
Euclidean distance(欧式距离) 当闵可夫斯基距离中的p=2时,即为欧式距离
Manhattan distance(曼哈顿距离) 当闵可夫斯基距离中的p=1时,即为曼哈顿距离

3.3 无序属性的处理

对无序属性可采用VDM(Value Difference Metric).令$m_{u,a}$表示在属性u上取值为a的样本数,$m_{u,a,i}$表示在第i个样本簇中的属性u上取值为a的样本数,k为样本簇数,则属性u上两个离散值a和b之间的VDM距离为$VDM_p(a,b)=\sum_{i=1}^{k}|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}|^p$.
将闵可夫斯基距离和VDM结合即可处理混合属性.假定有$n_c$个有序属性,$n-n_c$个无序属性,则$MinkovDM_p(x_i,x_j)=(\sum_{u=1}^{n_c}|x_{iu}-x_{ju}|^p+\sum_{u=n_c+1}^{n}VDM_p(x_{iu},x_{ju}))^\frac{1}{p}$

第十一章降维与度量学习

1.降维(维数约简)
1.1 为什么要降维?因为在高维情形下出现的数据样本稀疏,距离计算困难等问题,是所有机器学习方法共同面临的严重障碍.

1.2 为什么能进行降维?因为在很多时候,人们观测或收集到的数据样本虽然是高维的,但与学习任务密切相关的也许仅仅是某个低维分布,即高维空间中的一个低维”嵌入”.

1.3 降维方法:

多维缩放MDS(最优化问题解法:计算内积矩阵)
补充:
- 原样本为$R^{m\times{m}}$,降维后为$R^{d’\times{m}}$,使得任意两个样本在$d’$维空间中的欧式距离等于原始空间中的距离,即$||z_i-z_j||=dist_{ij}$.
- 令$B=Z^TZ$,B为降维后的内积矩阵,$b_{ij}=z_i^Tz_j$,$dist_{ij}^2=||z_i||^2+||z_j||^2-2z_i^Tz_j=b_{ij}+b_{jj}-2b_{ij}$,对Z进行中心化,然后推导求出B;求出B后利用特征值分解,求得Z矩阵
主成分分析PCA(Principal Component Analysis)(最优化问题解法:计算协方差矩阵),用一个超平面对所有样本进行恰当表达.
- 最近重构性:样本点到这个超平面的距离都足够近
- 最大可分性:样本点在这个超平面上的投影点能尽可能分开
- 思路:将所有的样本投影到超平面上,然后求投影变换后的新坐标系,正交基向量
核化线性降维(KPCA)
流形学习(Manifold Learning)
- 等度量映射(Isometric Mapping)(将多维空间中的测地线距离作为MDS算法的原始空间距离矩阵的输入,其中任意两点之间的最短路径可以用Dijkstra或者Floyd算法求)
- 局部线性嵌入(Locally Linear Embeeding)
度量学习(Metric Learning)(通过学习的方式,学到一种转换维度的距离度量的方式)

第十二章特征选择与稀疏学习

1.概念和意义
1.1 特征选择：从给定的特征集合中选择出相关特征子集的过程，成为”特征选择”;

1.2 特征选择的原因:

在现实任务中经常会遇到维数灾难的问题,这是由于属性过多造成的，如果能从中选择出重要的特征，使得后续的学习过程仅需在一部分特征上构建模型,则维数灾难问题会大为减轻。
去除不相关特征往往会降低学习任务的难度。

2.如何特征选择
分为两步:

“子集搜索”:前向搜索，每次向特征集合中添加，直到结果不再优为止;或者后向搜索，从完整的特征候选集合中减少特征（类似于贪心算法）。
“子集评价”:基于信息增益计算属性特征的贡献。对于属性子集A,假定根据其取值将D分成了V个子集{$D^1$,$D^2$,…,$D^V$},每个子集中的样本在A上取值相同,于是我们可计算属性子集A的信息增益.信息增益越大,意味着特征子集A包含的有助于分类的信息越多.基于每个属性子集的信息增益作为评价准则.

3.特征选择的方法
3.1 过滤式
过滤式选择不考虑后续学习器。

Relief是一种著名的过滤式特征选择方法，该方法设计了一个”相关统计量”来度量特征的重要性。（是为二分类问题设计的。扩展变体Relief-F能处理多分类的问题。）可以设定相关统计量的阈值或者设定选择特征的个数K.

3.2 包裹式
与过滤式选择不考虑后续学习器不同，包裹式选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。In other words，包裹式选择的目的就是为给定学习器选择最有利于其性能的特征子集。包裹式选择方法直接针对给定学习器进行优化。

LWW(Las Vegas Wrapper)是一个典型的包裹式特征选择方法，它在拉斯维加斯方法框架下使用随机策略来进行子集搜索，并以最终分类器的误差为特征子集评价准则。-交叉验证

3.3 嵌入式
嵌入式选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。
具体做法：将过拟合中的正则项中的L2范数替换为L1范数，L1范数和L2范数都有助于降低过拟合的风险，但L1范数还会带来一个额外的好处，它比后者更易于获得”稀疏”解。

4.稀疏表示与字典学习
4.1 将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，通常称为”字典学习”，亦称”稀疏编码”。

5.压缩感知
压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。通常认为，压缩感知分为”感知测量”和”重构恢复”这两个阶段。”感知测量”关注如何对原始信号进行处理以获得稀疏样本表示;”重构恢复”关注的使如何基于洗属性从少量观测中恢复原信号，这是压缩感知的精髓。

第十三章半监督学习

1.概念
在只有少量的标注样本,而有大量的未标注样本,让学习器不依赖外界交互,自动地利用未标记样本来提升学习性能,就是半监督学习.

2.方法
2.1 假设

聚类假设:假设数据存在簇结构,同一个簇的样本属于同一个类别.
流形假设:假设数据分布在同一个流形结构上,邻近的样本拥有相似的输出值.”邻近”程度常用”相似”程度来刻画,因此,流形假设可看作聚类假设的推广,但流形假设对输出值没有限制,因此比聚类假设的使用范围更广.
其实,这两个假设本质都是“相似的样本拥有相似的输出”.

2.2 分类
半监督学习可分为纯半监督学习和直推学习.

纯半监督学习:假定训练数据中的未标记样本并非待预测的数据.
直推学习:假定学习过程中所考虑的未标记样本恰是待预测数据.

2.3 具体方法

生成式方法
半监督SVM
图半监督学习
基于分歧的方法(与上述三个不同的是,基于分歧的方法使用多学习器,而学习器之间的”分歧”对未标记数据的利用至关重要.)
半监督聚类

第十四章概率图模型

1.隐马尔可夫模型
1.假定所关心的变量集合为Y,可观测变量集合为O,其他变量的集合为R,”生成式”模型考虑联合分布P(Y,R,O),”判别式”模型考虑条件分布P(Y,R|O).给定一组观测变量值,推断就是要由P(Y,R,O)或P(Y,R|O)得到条件概率分布P(Y|O).

2.概率图模型是一类用图来表达变量相关关系的概率模型.它以图为表示工具,最常见的是用一个结点表示一个或一组随即变量,结点之间的边表示变量间的概率相关关系,即”变量关系图”.

3.概率图模型大致分为两类:

使用有向无环图表示变量之间的依赖关系,称为有向图模型或贝叶斯网.
使用无向图表示变量间的相关关系,称为无向图模型或马尔可夫网.

4.隐马尔可夫模型是结构最简单的动态贝叶斯网.(主要用于时序数据建模,在语音识别/自然语言处理等领域有广泛应用.)

5.确定一个隐马尔可夫模型需要以下三组参数:

状态转移概率(状态转移矩阵)
输出观测概率(输出观测矩阵)
初始状态概率

2.马尔可夫随机场(MRF)
2.1 全局马尔可夫性:给定两个变量子集的分离集,则这两个变量子集条件独立.

2.2 由全局马尔可夫性得到两个有用的推论:

局部马尔可夫性:给定某变量的邻接变量,则该变量条件独立于其他变量.
成对马尔可夫性:给定所有其他变量,两个非邻接变量条件独立.

2.3 指数函数常被用于定义势函数.

3.条件随机场
3.1 条件随机场是一种判别式无向图模型.

3.2 生成式模型是直接对联合分布进行建模,而判别式模型则是对条件分布进行建模.(隐马尔可夫模型和马尔可夫随机场都是生成式模型,条件随机场是判别式模型.)

第十五章规则学习

1.基本概念
1.1 规则分为两类: “命题规则”和“一阶规则”,前者由是”原子命题”和逻辑连接词”与,或,非”和”蕴含”构成的简单陈述句.后者的基本成分是能描述事物的属性或关系的”原子公式”.

2.方法
2.1 序贯覆盖

2.2 剪枝优化(预剪枝和后剪枝)

2.3 一阶规则学习
受限于命题逻辑表达能力,命题规则学习难以处理对象之间的”关系”,而关系信息在很多任务中非常重要.例如,我们在现实世界挑选西瓜时,通常很难把水果摊上所有西瓜的特征用属性值描述出来,因为我们很难判断:色泽看起来多深才叫”色泽青绿”?敲起来声音多低才叫”敲声沉闷”?比较现实的做法是将西瓜进行相互比较,例如,”瓜1的颜色比瓜2更深,并且瓜1的根蒂比瓜2更蜷”,因此”瓜1比瓜2更好”.

第十六章强化学习

1.基本概念
1)强化学习任务通常用马尔可夫决策过程(MDP-Markov Decision Process)来描述:机器处于环境E中,状态空间为X,其中每个状态x是机器感知到的环境的描述.机器能采取的动作构成了动作空间A.若某个动作a作用在当前状态x上,则潜在的转移函数P将使得环境从当前状态按某种概率转移到另一个状态.在转移到另一个状态的同时,环境会根据潜在的“奖赏”函数R反馈给机器一个奖赏.

2)强化学习任务对应了四元组E=,其中P:X*A*X->R指定了状态转移概率,R:X*A*X->R指定了奖赏;在有的应用中,奖赏函数可能仅与状态转移有关,即R:X*X->R;

3)机器要做的是通过在环境中不断尝试而学得一个“策略”Pi,根据这个策略,在状态x下,就能得知要执行的动作a=Pi(x).

策略有两种方法:

一种是将策略表示为函数Pi:X->A,确定性策略常用这种表示.
另一种是概率表示Pi:X*A->R,随机性策略常用这种表示,Pi(x,a)为状态x下选择动作a的概率,动作概率之和为1.

总结:在强化学习任务中,学习的目的就是要找到能使长期累积奖赏最大化的策略.

T步累积奖赏
r折扣累积奖赏

4)强化学习和监督学习的差别和联系

强化学习	监督学习
状态(x)	示例(x)
动作(a)	标记(y)
策略(Pi)	分类器或回归器

与一般监督学习不同,强化学习任务的最终奖赏是在多步动作之后才能观察到的.

2.应用
2.1 K-摇臂赌博机

若仅为获知每个摇臂的期望奖赏,则可采用”仅探索”法,将所有尝试机会平均分配给每个摇臂,最后以每个摇臂各自的平均吐币概率作为其奖赏期望的近似估计.
若仅为执行奖赏最大的动作下,则可采用”仅利用”法,,按下目前最优的(即到目前为止平均奖赏最大的)摇臂.

总结:”探索”和”利用”两者是矛盾的,因为尝试次数有限,加强了一方则会自然削弱另一方.这就是强化学习所面临的”探索-利用窘境”.显然,欲累积奖赏最大,则必须在探索和利用之间达成较好的折中.

策略:

epsilon-贪心:基于一个概率来对探索和利用进行折中,每次尝试时,以epsilon的概率进行探索,以均匀概率选取一个摇臂,以1-epsilon的概率进行利用,即选择当前平均奖赏最高的摇臂.
Softmax:基于当前已知的摇臂平均奖赏来对探索和利用进行折中.若各摇臂的平均奖赏相当,则选取各摇臂的概率也相当;若某些摇臂的平均奖赏明显高于其他摇臂,则它们被选取的概率也明显更高.