Machine Learning

1 .概述

机器学习基于数据产生进行预测的模型，对需要预测的离散值和连续值进行分类(classification)和回归(regression)
在这个过程中，学的模型适用于新样本的能力成为泛化（generalization）
学习器在在训练集的误差称为训练误差，在新样本上的误差称为泛化误差，我们能做的是使训练误差尽可能小
我们的目的是为了尽可能学出适用于所有潜在样本的普遍规律
当训练误差较小时，很可能把训练样本本身的一些特点当做了普遍特点，反而使得泛化性能下降
这种现象称为过拟合（overfitting），相对应的是欠拟合（underfitting）

泛化误差评估方法

• 留出法(hold-out)：直接将数据集划分成两个互斥的集合，一个用于训练，一个用于测试
• 交叉验证法(cross validation)：分成k个互斥子集，每次选k-1个用于训练，1个用于测试，从而可进行k次训练和测试
• 自助法（bootstrapping):每次从m个样本的数据集中随机挑一个样本，执行m次，得到训练集，没有被选到的用作测试集

性能度量

• 回归任务：均方误差（mean squared error）
• 分类任务：精度（accuracy）
  查准率（precision）：挑选出的好瓜占总挑选的比例
  查全率（recall）：挑选出的好瓜占总好瓜的比例
  F1：查准率和查全率的调和平均

2.线性模型

线性模型试图学得一个通过属性的线性组合来进行预测的函数
其向量形式写成 $$f(x)=w^T\vec{x}+b$$

线性回归(回归)

我们试图让均方误差最小化，基于均方误差最小化的方法叫最小二乘法(least square method)
最小二乘法实际上就是寻找一条直线，使样本到直线距离之和最小
对于多元线性回归，同样是寻找一个超平面，使得样本到超平面距离之和最小
这里参数我们可以通过求导计算，也可通过线性代数列空间性质计算，得出最优解

线性回归的思想是是预测值逼近真实标记，同样可以令预测值逼近真实标记的衍生物
比如lny=w^Tx+b ，形式上仍是线性回归，但实质是求取输入空间到输出空间的非线性函数映射
同样可以拓展到其它函数，这样的模型成为广义线性模型

对数几率回归(分类)

其实只要找到一个单调可微函数，将线性回归预测值跟真实分类标记联系起来即可
由于单位阶跃函数不连续，所以我们使用近似的对数几率函数(sigmoid)

\[y=\frac{1}{1+e^{-z}} \]

然后用极大似然法估计参数w和b，最后通过梯度下降法和牛顿法求其最优解

线判别分析(分类)

LDA对于给定训练集，设法将样例投影到直线上，使得同类尽可能近，异类尽可能远
对于新样本分类时，同样将其投影到该直线上，根据其位置来确定类别
欲使得LDA最优化，即使得广义瑞利商最大

3. 决策树

决策树进行分类的关键在于如何选择最优划分属性，同时随着划分过程不断进行
决策树分支节点所包含样本纯度越来越高

信息增益

信息熵是度量纯度的一种常用指标，信息熵的值越小，纯度越高
假定第k类样本所占比例为p_k

\[Ent(D)=-\sum_{k=1}^{|y|}{p_klog_2p_k} \]

尝试对当前节点使用不同属性进行划分，当前信息熵减去划分后的信息熵即为信息增益
我们每次选择信息增益最大的属性进行划分来提升其纯度，若不能提升，则选择不划分
信息增益准则会对取值数目较多的属性有所偏好，将信息增益除以属性固有值，来补偿属性数量的影响，
最后我们可以使用一个启发式的方式，在信息增益高于平均的属性中选取增益率最高的属性

基尼指数

基尼指数反映了从数据集中随机抽取两个样本，其类别不一致的概率，Gini越小，纯度越高

\[Gini(D) = 1 - \sum_{k=1}^{|y|}p_k^2 \]

剪枝处理

剪枝主要是为了防止过拟合，在训练过程中，决策树为了使纯度更高，会尽可能多划分属性
从而导致把样本的特点当成了一般特点，所以可以主动去掉一些分支降低过拟合风险
通过测试集来判断泛化性是否得到提升

• 预剪枝
  在每个节点划分前进行估计，若划分不能带来决策树泛化性能的提升，则停止划分
• 后剪枝
  后剪枝是先生成一颗完整的决策树，再自下而上的考察，若取消划分后能带来泛化性提升，则进行替换

连续值离散化

最简单的策略是采用二分法对连续属性进行处理
遍历所有可取点，选取可以使得信息增益最大，则该点作为最终划分点

4. 神经网络

神经网络最基本的成分是神经元模型，在M-P神经元模型中，神经元接收到来自n个其他神经元传递过来的输入信号，
这些输入信号通过带权重的连接进行传递，神经元接受的总输入值与预设的阈值进行比较，通过激活函数得到输出
通常使用sigmoid函数作为激活函数，整个过程抽象成如下的数学形式

\[y_j = f(\sum_iw_ix_i-θ_j) \]

要解决非线性可分问题，需要用到多层神经网络，在输入层和输出层间的被称为隐含层
隐含层和输出层都是拥有激活函数的神经元
每一层神经元与下层全连接，不存在同层连接和跨层连接，这样的神经网络结构称为多层前馈神经网络

误差逆传播算法（error BackPropagation）

BP算法的目标是要最小化训练集D上的累积误差
其基于梯度下降的策略，根据均方误差，以目标的负梯度方向对参数进行调整
学习率η∈(0,1)控制算法的每一轮迭代更新步长，太大容易震荡，太小收敛速度过慢
采用梯度下降的时候容易陷入局部最优，这时我们可以采用以下策略

• 多组不同参数初始化
• 使用模拟退火跳出局部极小
• 使用随机梯度下降

深度学习

典型的深度学习模型就是很深层的神经网络，但多隐层在误差逆传播的时候往往不能收敛到稳定状态
在卷积神经网络(CNN)中，就是采用了神经元权共享的方式节省训练开销
CNN复合多个卷积层和采样层(池化层)对输入信号加工，卷积层包含多个特征映射，通过卷积滤波器提取特征
使得用于训练数据大幅减少，同时保留我们需要的特征信息

5. 支持向量机(SVM)

6. 贝叶斯分类器

7. 集成学习(ensemble learning)

集成学习大致可分为两类

• 个体学习器键存在强依赖、必须串行生成的序列化方法：Boosting
• 个体学习器间不存在强依赖关系、可同时生成的并行化方法：Bagging和随机森林

Boosting

Boosting从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整
使得先前基学习器做错的训练样本在后续得到更多关注，基于调整后的样本来训练下一个基学习器，如此重复进行
调整样本的方式可以采用重赋权法和重采样法来实现
比较典型的算法是Adaboost

Bagging

该算法直接基于前面泛化误差的评估方法中的自助法，即bootstrap
给定包含m个样本的数据集，先随机取出一个样本放入采样集中，再把该样本放回去，使得下次采样仍可能选中
这样经过m次随机采样，我们得到含m个样本的采样集，照这样采样出T个含m个样本的采样集
基于每个采样集训练出一个基学习器，再将基学习器结合，这就是Bagging的基本流程
Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法

随机森林(Random Forest)

RF在以决策树作为基学习器构件Bagging集成的基础上，进一步在决策树的训练过程中引入随机属性的选择
前面提到到，传统决策树在划分属性时，会以尽可能提升纯度为目标选择最优属性
而在RF中，会先随机选取一个属性子集，然后再在这个子集中选取最优属性，这样就引入了随机性
随机森林的训练过程中，不仅存在样本扰动，也存在属性扰动
使具有一定差异性的基学习器集成后的泛化性能大大提升

8. 聚类

聚类是一种典型的无监督学习算法
聚类将样本集D划分为若干个互不相交的子集，我们希望同一簇的样本尽可能彼此相似
不同簇的样本尽可能不同，也就是簇内相似度尽可能高且簇间相似度尽可能低
这其实与LDA算法的思想用于分类任务时有着异曲同工之妙

k均值算法

k均值算法针对针对聚类所得簇最小化平方误差，即每个值和均值差的平方和
最小化并不容易，找到最优解需要考察样本所有可能的簇划分
因此k均值算法采用贪心策略，通过迭代优化来求近似解
其具体过程是先预设需要划分簇的个数和初始均值，再根据数据到均值的距离将数据分到不同的簇中
接着求出簇的均值，把这些均值作为新的一轮初始值取计算，从而形成一个完整的迭代流程

• 学习向量量化
• 高速混合聚类
• 密度聚类
• 层次聚类

k邻近学习

其工作机制非常简单，给定测试样本，基于某种距离度量找出训练集中与其最近的k个训练样本
然后根据k个邻居的信息来进行预测，通常使用投票法和平均法
k邻近学习仅仅是把样本保存起来，训练开销为0，只有在需要预测的时候进行处理，是一种典型的懒惰学习