机器学习导论总结
on Courses
机器学习导论期末复习总结，建议复习再多看看细节的概念
机器学习期末复习总结
第二章 基本术语和模型评估
任务
分类任务：标记为离散值
回归任务：标记为连续纸
聚类任务：标记为空值
预测任务：根据标记的完整情况
监督学习：所有示例有标记，分类、回归
无监督学习：所有实例没有标记，聚类
半监督学习：少量有标记，大量没有标记。
噪音标记学习：有标记，但不完全准确
概念学习
假设空间：所有可能属性的组合
版本空间：与训练集一致的“假设集合”
归纳偏好：学习过程中对某种类型假设的偏好称作归纳偏好
No Free Lunch：总误差与学习算法无关
模型评估与选择
学习器在训练集上的误差称为训练误差或经验误差，在新样本上的误差称为测试误差或泛化误差。
评估方法：
留出法：将数据集划分为两个互斥的集合
交叉验证法：将数据集划分为k个互斥子集，每次用k-1个子集的并作为训练集，余下的作为测试集，k常取10
自助法：从数据集有放回的随机采样m次、
自助法：数据集小，难以划分训练、测试集很有用；产生多个训练集，对集成学习有用
数据量足够，一般采用留出法和交叉验证
性能度量
均方误差（MSE），错误率、精度，P，R，ROC(AUC)，$F_\beta$度量，代价敏感错误率。
ROC：
P：(Precision)查准率$\dfrac{TP}{TP+FP}$，预测结果正例中真实情况为正例占的比例
R：(Recall)查全率$\dfrac{TP}{TP+FN}$，真实情况正例中预测结果为正例占的比例
P-R曲线：P=R，平衡点，可用来度量P-R曲线有交叉的分类器性能的高低
$F_{\beta}=\dfrac{(1+\beta^2)\times P\times R}{(\beta^2\times P)+R}$,$F_\beta$度量，$\beta=1$，标准$F_1$度量。
比较检验（比较评价两个模型）：假设检验：二项检验、T-检验
偏差与方差
泛化误差可分解为方差、偏差与噪声之和
第三章 线性模型
回归任务（掌握）
最小二乘法原理和推导
二分类任务
对数几率回归、线性判别分析的建模原理
线性判别分析
多分类任务
一对一
一对其余
多对多
类别不平衡任务
欠采样、过采样、阈值移动
第四章 决策树
决策树基本流程
掌握决策树基本流程和原理
基本流程
递归过程，当以下条件停止：
（1）当前节点包含的样本全部属于同一类别
（2）当前属性集为空，或所有样本在所有树性上取值相同
（3）当前节点包含的样本集合为空
决策树算法的关键：划分选择
熟悉三种划分准则
划分选择-信息增益
信息熵：样本集合D中第k类样本所占的比例为$p_k,(k=1,2,…,|y|)$.
$
Ent(D)=-\sum\limits_{k=1}^{|y|}p_k\log_2{p_k}
$
$Ent(D)$表示集合的纯度 越小越纯
信息增益
离散属性$a$，可能取值有$V$类，产生V个分支节点，第$v$个分支节点包含了D中所有在属性$a$上取值为$a^v$的样本，记为$D^v$。计算用属性a
$
Gain(D,a)=Ent(D)-\sum\limits_{v=1}^V\dfrac{|D^v|}{|D|}Ent(D^v)
$
选择$Gain(D,a)$最大的属性$a$来进行划分。
不足：若编号作为一个属性，信息增益一般远大于其他属性。信息增益指标偏好取值数目较多的属性
基尼指数——CART决策树
C4.5：使用增益率，用属性的取值范围对信息增益做一个规范化。
基尼指数：$Gini(D)=1-\sum\limits_{k=1}^{|y|}p_k^2$.越小越纯
$Gini_index(D,a)=\sum\limits_{v=1}^V\dfrac{|D^v|}{|D|}Gini(D^v)$.选择使得$Gini_index(D,a)$最小的属性
克服过拟合的问题：剪枝处理
预剪枝 vs 后剪枝
原因：决策树容易过拟合
预剪枝：决策树生成过程中，对每个结点在划分前先进⾏估计，若当前结点的划分不能带来决策树泛化性能提升，则停⽌划分并将当前结点记为叶结点，其类别标记为训练样例数最多的类别。（边建树，边剪枝）（留出法，用一部分进行验证）
优点：降低过拟合风险，减少时间开销。缺点：欠拟合风险。
后剪枝：先建树，后剪枝
优点：欠拟合风险小 缺点：时间开销大
处理多种类型数据：连续与缺失值
了解基本原理
连续：连续属性离散化
缺失：Q1 划分 考虑一个属性时，仅使用当前属性无缺失样本学习
Q2：划分后样本的处理：将样本划分到每一个分支，赋予不同的权重
决策树的变体：多变量决策树
了解基本原理
每一个非叶节点是一个线性分类器
第五章 神经网络
神经元模型：熟悉
输入：来自其他n个神经云传递过来的输入信号。
处理：输入信号通过带权重的连接进行传递，神经元接收到总输入值将与神经元的阈值进行比较。
输出：通过激活函数的处理以得到输出。
感知机与多层网络：熟悉
感知机
两层神经元组成，只能处理线性可分问题。
多层前馈神经网络
定义：每层神经元与下一层神经元全互联, 神经元 之间不存在同层连接也不存在跨层连接。
前馈：输入层接受外界输入, 隐含层与输出层神经 元对信号进行加工, 最终结果由输出层神经元输出。
多层前馈网络表示能力
只需要一个包含足够多神经元的隐含层，多层前馈神经网络就能以任意精度逼近任意复杂度的连续函数。
多层前馈网络局限
容易过拟合
如何设置隐层神经元的个数仍然是个未决问题
缓解过拟合策略
早停：在训练中，若训练误差降低，但验证误差升高，则停止训练。
正则化：在误差目标函数中增加一项描述网络复杂程度的部分，例如连接权重与阈值的平方和。($E=\lambda\dfrac{1}{m}\sum\limits_{k=1}^mE_k+(1-\lambda)\sum\limits_iw_i^2$)
误差逆传播算法：熟悉
BP算法
推导注意链式法则，计算输入层的变化时要对所有的$\beta_j$分别链式法则求和。
标准BP算法
每次针对单个训练样例更新权值与阈值。
参数更新频繁，不同样例可能抵消们需要多次迭代。
累计BP算法
优点：其优化的目标是最小化整个训练集上的累计误差$E=\dfrac{1}{m}\sum\limits_{k=1}^mE_k$.
缺点：读取整个训练集一遍才对参数进行更新，参数更新频率较低。
实际应用
但在很多任务中，累计误差下降到一定程度后，进一步下降会非常缓慢，这时标准BP算法往往会获得较好的解，尤其当训练集非常大时效果更明显。
全局最⼩与局部最⼩：了解
跳出局部最小的策略
多组不同的初始参数优化
模拟退火技术
随机梯度下降
遗传算法
其他常见神经网络：了解
RBF网络：是哟个径向基函数$\rho(x,c_i)=e^{-\beta_i||x-c_i||^2}$作为激活函数
ART:竞争学习，无监督学习
SOM网络：竞争型无监督学习
级联相关网络：将网络结构也作为学习目标
Elman网络:递归神经网络,有反馈.
深度学习：了解
深层神经网络最为典型
训练方法:预训练+微调. 预训练:每次训练一层,微调:对整个网络进行微调训练
权共享 (CNN)
理解深度学习:特征工程 VS 特征学习或表示学习
特征工程:手工设计特征
特征学习:通过深度学习自动产生分类的特征
第六章 支持向量机 SVM
间隔与支持向量
寻找超平面将样本划分，找最中间的超平面。
$
\mathop{\arg\max}_{w,b} \dfrac{2}{||w||}\
s.t.\quad y_i(w^Tx_i+b)\geq 1,i=1,2.,…,m\
\Leftrightarrow\
\mathop{\arg\min}_{w,b} \dfrac{||w||^2}{2}\
s.t.\quad y_i(w^Tx_i+b)\geq 1,i=1,2.,…,m
$
对偶问题
拉格朗日乘子法
$
L(w,b,\alpha)=\dfrac{1}{2}||w||^2-\sum\limits_{i=1}^{m}\alpha_i(y_i(w^Tx_i+b)-1)
$
令$L$对$w,b$的偏导为0可得
$
w=\sum\limits_{i=1}^m\alpha_iy_ix_i,\sum\limits_{i=1}^m\alpha_iy_i=0
$
回代
$
\min_\alpha\quad \dfrac{1}{2}\sum\limits_{i=1}^m\sum\limits_{j=1}^m\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum\limits_{i=1}^m\alpha_i\
s.t.\quad \sum\limits_{i=1}^m\alpha_iy_i=0\
\alpha_i\geq 0,i=1,2,…,m.
$
最终模型
$
f(x)=w^Tx+b=\sum\limits_{i=1}^m\alpha_iy_ix_i^Tx+b
$
KKT条件
$
\alpha_i\geq 0\
y_if(x_i)\geq 1\
\alpha_i(y_if(x_i)-1)=0
$
求解SMO
基本思路：不断执行如下
选取一对需要更新的变量$\alpha_{i},\alpha_j$.
固定$\alpha_i,\alpha_j$以外的参数，求解对偶问题更新$\alpha_i,\alpha_j$.注意仅考虑两个变量，约束也视为两个变量的约束，其他视为常数，显然有闭式解。
b通过支持向量来计算。（对任意支持向量$x_s$，$y_s(\sum\limits_{i=1}^m\alpha_iy_ix_i^Tx_s+b)=1$）
支持向量机解的稀疏性：训练后，模型仅与支持向量有关，及$\alpha_i$不等于0的对应的向量有关。
核函数
当空间不线性可分时，将样本从低维映射到一个更高维的特征空间。
样本$x$映射后$\phi(x)$，超平面$f(x)=w^T\phi(x)+b$。在模型中仅以内积的形式出现。
Mercer定理(充分非必要)：只要一个对称函数所对应的核矩阵半正定, 则它就能作为核函数来使用.
$
k(x_i,x_j)=\phi(x_i)^T\phi(x_j)
$
常用的核函数
软间隔与正则化
软间隔
现实中, 很难确定合适的核函数使得训练样本在特征空间中线性可分; 同时一个线性可分的结果也很难断定是否是有过拟合造成的.
引入”软间隔”的概念, 允许支持向量机在一些样本上不满足约束.
基本想法：最大化间隔的同时, 让不满足约束的样本应尽可能少
$
\min_{w,b}\quad \dfrac{1}{2}||w||^2+C\sum\limits_{i=1}^ml_{0/1}(y_i(w^T\phi(x_i)+b)-1)
$
$l_{0/1}$是损失函数
$
l_{0/1}(z)=1, z < 0
\
l_{0/1}(z)=0,otherwise
$
替代函数（因为0-1函数不连续）
$
l_{hinge(z)}=\max(0,1-z)
$
模型
原始问题
$
\mathop{\arg\min}{w,b} \dfrac{||w||^2}{2}+C\sum\limits{i=1}^m\max(0,1-y_i(w^T\phi(x_i)+b))\
s.t.\quad y_i(w^Tx_i+b)\geq 1,i=1,2.,…,m
$
对偶问题
$
\min_\alpha\quad \dfrac{1}{2}\sum\limits_{i=1}^m\sum\limits_{j=1}^m\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum\limits_{i=1}^m\alpha_i\
s.t.\quad \sum\limits_{i=1}^m\alpha_iy_i=0\
C\geq \alpha_i\geq 0,i=1,2,…,m.
$
正则化
$
\min_f\quad \Omega(f)+C\sum\limits_{i=1}^ml(f(x_i),y_i)
$
第一项是结构风险（描述模型的某些性质），第二项是经验风险（描述模型与训练数据的契合程度）
支持向量回归
特点: 允许模型输出和实际输出间存在$2\epsilon$的偏差
损失函数
核方法
推广：核LDA（线性模型中提到），核PCA
第七章 贝叶斯分类器
掌握贝叶斯决策论
给定N个类别，令$\lambda_{ij}$代表将第$j$类样本误分类为第$i$类所产生的损失，
将样本$x$分到第$i$类的条件风险为：
$
R(c_i|\mathbf{x})=\sum\limits_{j=1}^N\lambda_{ij}P(c_j|\mathbf{x})
$
贝叶斯判定准则
$
h^*(\mathbf{x})=\mathop{\arg\min}_{c\in Y}R(c|\mathbf{x})
$
$h^*$成为被贝叶斯最优分类器，总风险成为贝叶斯风险，反应学习性能的理论上限。
判别式 vs 生成式
判别式
直接对$P(c|\mathbf{x})$建模如决策树，BP神经网络，SVM
生成式
先对$P(\mathbf{x},c)$建模，再由次获得$P(c|\mathbf{x})$.
$
P(c|\mathbf{x})=\dfrac{P(\mathbf{x},c)}{P(\mathbf{x})}=\dfrac{P(c)P(\mathbf{x}|c)}{P(\mathbf{x})}
$
代表：贝叶斯分类器，（贝叶斯分类器$\neq$贝叶斯学习）
熟悉极大似然估计
先假设某种概率分布形式，再基于训练样例对参数进行估计
设$P(x|c)$具有某种概率分布，参数$\theta_c$.
$\theta_c$对训练集D中第c类样本组成的集合$D_c$的似然为
$
P(D_c|\theta_c)=\prod_{x\in D_c}P(x|\theta_c)
$
连乘容易下溢，故通常使用对数似然LL
$LL(\theta_c)=\log{P(D_c|\theta_c)}=\sum_{x\in D_c}\log{P(x|\theta_c)}$
$\hat{\theta}_c=\arg\max_{\theta_c}{LL(\theta)}$
熟悉朴素贝叶斯（拉普拉斯修正）
主要障碍：所有属性上的联合概率难以从有限训练样本估计获得
组合爆炸；样本稀疏
基本思路：假定属性独立
$
P(c|x)=\dfrac{P(c)P(x|c)}{P(x)}=\dfrac{P(c)}{P(x)}\prod_{i=1}^dP(x_i|c)
$
估计
$P(c)=\dfrac{|D_c|}{|D|}$.
$P(x|c)$:
对离散属性，$D_{c,x_i}$表示$D_c$在第i个属性上取值为$x_i$的样本组成的集合，则$P(x_i|c)=\dfrac{|D_{c,x_i}|}{|D_c|}$.
对连续属性，考虑概率密度函数，假定$P(x_i|c)\sim N(\mu_{c,i},\sigma^2_{c,i})$.
拉普拉斯修正
若某个属性值在训练集中没有与某个类同时出现过，则直接计算会出现 问题，因为概率连乘将“抹去”其他属性提供的信息。
$P(c)=\dfrac{|D_c|+1}{|D|+N}$.$P(x_i|c)=\dfrac{|D_{c,x_i}|+1}{|D_c|+N_i}$.
朴素贝叶斯分类器的使用
若对预测速度要求高：预计算所有概率估值，使用时“查表”
若数据更替频繁：不进行任何训练，收到预测请求时再估值 (懒惰学习, lazy learning)
若数据不断增加：基于现有估值，对新样本涉及的概率估值进行修正 (增量学习, incremental learning)
掌握半朴素贝叶斯
基本思路：适当考虑一部分属性间的相互依赖信息
最常用策略：独依赖估计 (One-Dependent Estimator, ODE)
假设每个属性在类别之外最多仅依赖一个其他属性
$
P(c|x)\propto P(c)\prod_{i=1}^d P(x_i|c,pa_i)
$
SPODE
假设所有属性都依赖于同一属性，称为“超父” (Super-Parent)， 然后通过交叉验证等模型选择方法来确定超父属性
TAN
以属性间的条件”互信息”(mutual information)为边的权重，构建完全图，再利用最大带权生成树算法，仅保留强相关属性间的依赖性
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)\
\hat{P}(c,x_i)=\dfrac{|D_{c,x_i}|+1}{|D|+N_i}\
\hat{P}(x_j|c,x_i)=\dfrac{|D_{c,x_i,x_j}|+1}{|D_{c,x_i}|+N_j}
$
高阶依赖
需要充分的样本
掌握贝叶斯网
了解EM算法
第八章 集成学习
个体与集成：知道个体分类器的定义和集成学习的定义
集成学习通过构建并结合多个学习器来提升性能
Boosting：知道Boosting的思想和adaboost的实现
Boosting
个体学习器存在强依赖关系，串行生成，每次调整训练数据样本分布
AdaBoost
($Z_t$是规范化因子，保证权重之和是1)
基学习器的线性组合
$
H(x)=\sum_{t=1}^T\alpha_th_t(x)
$
最小化指数损失函数
$
l_{exp}(H|D)=E_{x\sim D}[e^{-f(x)H(x)}]
$
注意事项
数据分布的学习：重赋权法，重采样法
重启动，避免训练过程过早停止，（8.5处，如果学习的分类器不佳）
Bagging与随机森林：知道思想和实现的方式
个体学习器不存在强依赖关系
并行化生成
自助采样法
Bagging算法
($D_{bs}$是自助采样产生的样本分布)
时间复杂度低 :
假定基学习器的计算复杂度为O(m)，采样与投票/平均过程的复杂度 为O(s)，则bagging的复杂度大致为T(O(m)+O(s))
由于O(s)很小且T是一个不大的常数
因此训练一个bagging集成与直接使用基学习器的复杂度同阶
可使用包外估计
包外估计
可以计算泛化误差等
随机森林
采样的随机性，属性的随机性
结合策略：知道集中常用策略以及stacking的优缺点
平均法：如加权平均法
投票法：绝对多数投票法和相对多数投票法
学习法：Stacking 先从初始数据集训练出初级学习器，然后”生成”一个新数据集用于训练次级学习器.
在训练阶段，次级训练集是利用初级学习器产生的，若直接用初级学习器 的训练集来产生次级训练集，则过拟合风险会比较大;因此一般是通过使用交叉验证或留一法这样的方式，用训练初级学习器未使用的样本来产生次级学习器的训练样本.
多样性：知道多样性扰动的几种办法
误差-分歧分解
$
E=\bar{E}-\bar{A}
$
($\bar{E}$表示个体学习器泛化误差的加权评分，$\bar{A}$表示个体学习器的加权分歧值。)
个体学习器精确性越高、多样性越大，则集成效果越好
多样性增强方法
数据样本扰动：
- 采样
输入属性扰动：
- 随机子空间算法
输出表示扰动：
翻转法：随机改变输入样本的标记
输出调剂法：分类输出改为回归输出得到分类器
ECOC法：多类任务分解为一系列两类任务来求解
算法参数扰动：
负相关法：强制要求个体神经网络采用不同的参数
不同的多样性增强机制同时使用