统计学习方法

读书笔记 数据挖掘 机器学习

---

第一章、统计学习方法概论

1.1、统计学习

　　统计学习的对象是数据，从数据出发，提取数据的特征，抽象出数据的模型，发现数据中的知识，由回到对数据的分析与预测当中
　　实现统计学习方法的步骤如下：

• 得到一个有限的训练数据集合
• 确定模型选择的准则，即学习的策略
• 实现求解最右模型的算法，即学习的算法
• 通过学习方法选择最右模型
• 利用最优模型对新的数据进行预测或者分析

1.3、策略

　　监督学习问题是在假设空间中选择模型f作为决策函数，对于给定的输入$X$，由$f(x)$给出相应的输出$\hat{y}$，这个$\hat{y}$与真实的$y$可能不一致，用一个损失函数（loss function）或者代价函数（cost function）来度量预测错误的程度
　　学习的目标就是选择期望风险最小的模型。

1.5、交叉验证

　　如果给定的样本数据充足，进行模型选择的一种简单的方法就是随机将数据分为三部分，分别为训练集、验证集和测试集。训练集用来训练模型，验证机用于模型的选择，而测试集用于最终对学习方法的评估。在训练好的不同的模型中，选择对验证机由最小预测误差的模型。（有些模型需要设计超参数，如LDA、pLSA等需要设计主题个数这个超参数），验证集就是用来选哪一个适合的超参数。
1.10、回归问题
　　回归是监督学习的另一个重要问题。回归用于预测输入变量与输出变量之间的关系，特别是当输入变量的值发生变化时，输出变量的值随之发生的变化。回归模型正式表示从输入变量到输出变量之间映射的函数。回归问题的学习等价于函数拟合，选择一条函数曲线使其很好地拟合已知数据且很好预测未知数据。

第二章、感知机

　　感知机是二元分类的线性分类模型，其输入为实力的特征向量（feature vector），输出为实力的label，+1，-1.感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。为了求出分离超平面，感知机利用梯度下降最小化损失函数（误分类点到超平面S的总距离）进而求得模型参数。
　　感知机函数：$f(x) = sign(wx+b)$，$w$，$b$为感知机模型参数。
　　感知机适用于线性可分的数据，对于非线性可分的效果就不好了。

第三章、k 近邻法

　　k 近邻属于一个lazy学习方法，对于每一个新实例，通过新实例的最近的k个训练样本进行表决判断新实例的类别，它不具有显式的学习过程，没有生成模型。k 近邻法实际上是利用训练样本对特征向量空间进行划分，并作为分类的规则。
　　k 近邻法的三个基本要素：

1. k值的选择（经验值或者通过小样本集测试）
2. 距离度量，马氏距离、欧氏距离
3. 分类决策规则（小数服从多数）

kd树：利用样本各个特征的中位数进行二分

优点：

1. 思想简单，理论成熟，既可以用来做分类也可以用来做回归；
2. 可用于非线性分类
3. 训练时间复杂度为O(n)；
4. 准确度高，对数据没有假设，对outlier不敏感；

缺点：

1. 计算量大；
2. 样本不平衡问题（即有些类别的样本数量很多，而其它类别样本的数量很少）
3. 需要大量的内存；

第四章、朴素贝叶斯法

　　朴素贝叶斯法是基于贝叶斯定理以及特征条件独立假设（条件独立于分类标签）的分类方法，给定输入$x$利用贝叶斯定理求出后验概率最大的输出$y$
　　参数估计：
　　极大似然估计，其实就是统计每一个分类标签$P(Y=c_k)$,$P(X^{(j)}=x^{(j)}|Y=c_k)$的频率
　　拉普拉斯平滑：譬如分子加上1，分母加上$K$，$K$是分类标签个数
　　
　　优点：对小规模的数据表现很好，适合多分类任务，适合增量式训练。
　　缺点：对输入数据的表达形式很敏感。（连续变量就不好办了，需要离散化）

第五章、决策树

5.2.2信息增益

　　为了便于说明，先给出熵与条件熵的定义
　　熵（entropy）是表示随机变量不确定性的度量，$X$是一个取有限个值的离散随机变量，其概率分布为：
　　　　　　　$P(X=x_{i})=p_{i},i=1,2,,...,n$
　　则随机变量$X$的熵定义为
　　　　　　　$H(X)=-\sum_{i=1}^{n}p_{i}logp_{i}$
　　熵只依赖于分布，与$X$的取值无关，所以也可将$H(X)$记为$H(p)$
　　 　　　　　$0\leqslant H(p)\leqslant logn$
　　条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性。
　　　　　　　$H(Y|X)=\sum_{i=1}^{n}p_{i}H(Y|X=x_{i}),p_{i}=P(X=x_{i})$
　　信息增益（information gain）表示得知特征$X$的信息而使得$Y$的信息的不确定性减少的程度
　　(1)、计算数据集D的经验熵$H(D)$
　　　　　　　$H(D)=-\sum_{k=1}^{K}\frac{|C_{k}|}{|D|}log_{2}\frac{|C_{k}|}{|D|}$
　　(2)、计算特征A对数据集D的经验条件熵$H(D|A)$
　　　　　　　$H(D|A)=\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}H(D_{i}),n是特征值A将D划分为n个子集D_{i},i=1,..n$
　　(3)、计算信息增益
　　　　　　　$g(D,A)=H(D)-H(D|A)$
　　以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比（information gain ratio）可以对这一问题进行校正。这是特征选择的另一准则。
　　信息增益比定义$g_{R}(D,A)$：
　　　　　　　$g_{R}(D,A)=\frac{g(D,A)}{H_{A}(D)}$
其中，$H_{A}(D)=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}log_{2}\frac{|D_{i}|}{|D|}$

决策树学习包括3个步骤：

1. 特征选择，ID3信息增益，C4.5信息增益比，选择对样本有分类能力的特征，CART对回归树采用平方误差最小化准则，对分类树用基尼指数最小化准则。
2. 决策树生成
3. 决策树修剪，防止过度拟合

以信息增益作为划分训练样本的特征，存在偏向于选择取值较多的特征的问题，因为取值较多，所以分割后的子结点的纯度就越高。所以采用信息增益比来矫正这一个问题

优点：计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征；
缺点：容易过拟合（后续出现了随机森林，减小了过拟合现象）；

第六章、logistic regression 与最大熵模型

　　Logistic回归目的是从特征学习出一个0/1分类模型，而这个模型是将特征的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此，使用logistic函数（或称作sigmoid函数）将自变量映射到(0,1)上，映射后的值被认为是属于y=1的概率。
LR模型：
$P(Y=1|x)=\frac{exp(w·x+b)}{exp(w·x+b)+1}$
$P(Y=0|x)=\frac{1}{exp(w·x+b)+1}$

参数估计：
使用极大似然估计法：训练得到$w$
优点：
1. 实现简单；
2. 分类时计算量非常小，速度很快，存储资源低；
缺点：
1. 容易欠拟合，一般准确度不太高；
2. . 只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分；
　　最大熵原理认为要选择的概率模型首先必须满足已有的事实，即约束条件。在没有更多信息的情况下，哪些不确定的部分都是“等可能的”

第七章、支持向量机

　　支持向量机是一个二类分类模型，它的基本模型定义在特征空间上的间隔最大的线性分类器。学习策略就是间隔最大化（间隔最大化使SVM有别于感知机），可形式化转化为一个求解凸二次规划的问题。
　　支持向量机包括：线性可分支持向量机、线性支持向量机与非线性支持向量机
线性向量机目的是找出一个分离超平面$w·x+b=0$
　　一般来说，一个点距离分离超平面的距离可以作为分类预测的确信程度，可用量$y_i(w·x_i+b)$来表示分类的正确性以及确信度，这就是函数间隔的概念。
样本集的函数间隔是所有点的函数间隔最小值，而学习目标就是最大化这个样本集的最小值，使得所有点都离超平面都远。
由于函数间隔与$w，b$成正比例，对法向量$w$加以规划化模长$|w|=1$，使得间隔是可以唯一确定的，这时候函数间隔称为几何间隔
　　间隔最大化就是最小化${|w|}^2$，转化为凸二次规划了。

　　优点：
1. 可用于线性/非线性分类，也可以用于回归；
2. 低泛化误差；
3. 容易解释；
4. 计算复杂度较低；
　　缺点：
1. 对参数和核函数的选择比较敏感；
2. 原始的SVM只比较擅长处理二分类问题；

第八章、提升方法

8.1、提升方法AdaBoost算法

　　基本思想就是三个臭皮匠顶一个诸葛亮，训练多个弱分类器称为一个强分类器
　　对于提升算法，需要解决两个问题：
1. 在每一个如何改变训练样本的权重或者概率分布
2. 如何将弱分类器合成一个强分类器
关于第一个问题，AdaBoost的做法是，提高那些被前一轮的弱分类器误分的权重，而降低那些被正确分类的权重（在计算损失函数时使用这个权重）。
关于第二个问题，AdaBoost采用加权多数表决的方法，方法是误差小的投票权重大，误差大的投票权重小
　　本章概要：
提升方法是将若学习算法提升为强学习算法的统计学习方法，在分类学习中，提升方法反复修改训练样本的权重分布，构建一系列基本分类器，并将这些基本分类器线性组合构成一个强分类器，代表的方法有AdaBoost
　　优点：
1. 低泛化误差；
2. 容易实现，分类准确率较高，没有太多参数可以调；
　　缺点：
1. 对outlier比较敏感；

第九章、EM算法及其推广

　　EM算法是一种迭代算法，用于含有隐含变量的概念模型参数的极大似然估计或者暨大厚后验概率估计，每一次迭代有两步：E步骤求期望，M步骤求极大值
　　EM算法的推导关键一步是用了Jensen不等式求得下面，然后极大化似然函数的下界，不断迭代得到收敛解
　　$Q$函数：$Q(\theta,\theta^{(i)})=E_Z[logP(Y,Z|\theta);Y,\theta^{(i)}]$，每一次就是最大化得到新的$\theta^{(i+1)}$

第十章、隐马尔科夫模型(HMM)

　　隐马尔科夫模型由初始状态概率向量$\pi$、状态转移矩阵$A$与观测概率矩阵$B$，$\pi$和$A$决定了状态序列，$B$决定观测序列，就是如何从状态生成观测
　　隐马尔科夫模型作了两个基本假设：
1. 齐次马尔科夫性假设，隐藏的马尔科夫链在任何时刻t的状态只依赖前一刻的状态，与其他时刻的状态及观测无关，也与时间t无关
2. 观测独立性假设，即任何时刻的观测只依赖与该时刻的马尔科夫链的状态，与其他观测状态无关。