Some notes about Machine Learning [including Ch 1-8] taught by OUC, using the textbook written by Zhihua Zhou, along with parts of Statistical Learning Method, Li Hang.
Ch 01 概论
统计学习
统计学习,简言之,一个系统基于统计数据执行某个过程,来改进其性能。其基本假设为:同类数据(独立同分布)具有一定的统计规律性。
三要素
- 模型:提出假设空间,即,假设要学习的模型属于某个函数的集合;
- 策略:应用评价准则($\mathcal{L}$),从空间中选取”最优”模型,使其对训练集、测试集在该准则下有最优的预测;
- 算法:选取最优模型,设定某种算法来得到参数最优的模型;
一般过程
得到有限数据集 -> 建立三要素 -> 得到最优模型 -> 预测新数据。
分类
-
监督学习:学习从输入到输出映射的统计规律。
-
基本假设:输入输出对 $(x,y)$ 满足联合概率分布 $P(x,y)$ 独立同分布产生;
- 分类:
- 回归问题:输入、输出变量均为连续变量;
- 分类问题:输入变量为有限个离散变量;
- 标注问题(e.g. 语句中的词性标注):输入、输出均为变量序列;
- 产生的模型形式为 $\hat{y}=f(x), \hat{y}=\arg\max\limits_y \hat{p}(y\mid x)$ 等,由此也可观,监督学习的主要优化算法是最大化似然函数。
-
-
无监督学习:学习无标注数据中的统计规律或潜在结构。
- 不同情境具体分析,其模型常与 $z=\hat{g}(x), \hat{p}(z\mid x), \hat{z}(x\mid z)$ 有关。
- 主要学习模型是聚类、降维等;
-
强化学习:通过系统和环境的一系列连续互动的数据,学习最优的序贯决策。
-
半监督学习和主动学习:
-
半监督学习:少量样本有标签,大量样本无标签:
假设
平滑假设
如果两个样本 $x_1, x_2$ 相似,相应输出 $y_1, y_2$ 也应相似。
聚类假设
给定的决策边界位于低密度地区,这意味着不同簇对应且仅对应不同类。(鲁棒性强,受扰动程度小)
流形假设
多个低维流形组成输入空间,同一流形上的数据点具有相同标签。
一些方法
一致性回归
假设细微的扰动不会对数据的分类造成影响。
伪标签
基于已标记的训练集,用启发式方法标注未标记数据集,生成额外训练用例。
比如说,正常训练监督模型,用其预测数据集并选取高置信度样本,协同有标签数据训练新模型,迭代替换原模型,以求精度不断提升。
-
主动学习:机器给出样本让教师标注,然后进行学习:
采用主动策略(提取待标注数据,人工标注)构建小训练集(以减少标记成本),这个小训练集中的样本比较”重要”,故期望训练效果好。
基础场景
- Pool-based Scenario (most): 提供未标记的数据池,策略在数据池中选取样本标记;
- 比如,选置信度最低的(min(max(prob)))
- 边缘采样,容易判定为两类的(min(prob_max_1 - prob_max_2))
- 熵最大的(不确定性最大)
- KL散度
- 方差减少最多
- 考虑稠密的、难以区分的等
- Stream-based Scenario: 提供未标记的数据流,策略选择对当前数据进行标记或进行预测;
- Query synthesis scenario: 提供未标记的数据池,但策略是自行生成新样本查询;
- Pool-based Scenario (most): 提供未标记的数据池,策略在数据池中选取样本标记;
-
Ch 02 模型评估与选择
误差
误差
样本真实输出与预测输出之间的差异。
- 训练误差/经验误差:训练集上的误差
- 测试误差:测试集上的误差
- 泛化误差:除训练集外,所有样本上的误差
过拟合
学习到的特征过于贴近训练集,而训练集却不能代表所有数据的分布情况,甚至可能被学习到”仅属于该训练集的特征/扰动”,导致泛化性能下降。
- Solutions/Problems:
- 增加训练资料,e.g. data augmentation,期望使学习的特征更泛化、鲁棒;
- 给出函数限制,(基于领域知识/对机器学习的经验)降低模型复杂度,以期泛化:
- 限制参数数量(e.g. 使用正则项):猜测外生量、内生量间关系较简单,或言,更囊括整个变量域的分布,于是限制模型复杂性;
- 输入较少特征:基于专家知识做特征工程,减少效用较低的特征输入/变换后输入;
- Early stopping、Dropout:增强泛化性;
欠拟合
连训练样本的一般特征都没学好。
- Solutions/Problems:
- 增大模型复杂性,e.g. 对决策树,拓展分支;对 NN,增加训练轮数/深度;
- 优化策略较差,e.g. 在非平滑的目标函数上,SGD 容易陷入 local minimum;
评估方法
留出法
直接将数据集划分为两个数据分布一致的互斥集合,随机划分进行重复实验,取平均值。
- 训练/测试比例常为 2:1~4:1
交叉验证法
讲数据集分层采样划分为 k 个大小相似的互斥子集,每次用一个子集作测试集,其余的作训练集,最终返回 k 次测试结果的均值。
-
k 的常用取值为 10
-
常随机采用不同划分重复多次,最终取平均值;但当 $k=m$,则得到留一法,好处在于不受随机划分方式的影响,结果准确,缺点在于计算开销大;
自助法(Bootstrap)
简言之,就是以自主采样法为基础,对数据集有放回采样 $m$ 次得到训练集,余下作测试集。
- 在数据集小,难以有效划分训练/测试集时有用;且从数据集中采样多个不同的训练集,有助于集成学习
性能度量
-
对回归任务,常用 MSE 均方误差度量:$\sum (f(x_i)-y_i)^2$
-
对分类任务,常用分类错误率 $E(f;D)={1\over m} \sum\limits^m_i \mathbb{I}(f(x_i)\ne y_i)$、精度 $1-E(f;D)$ 度量;
P-R
但分类中更多常用 Precision、Recall Rate 进行衡量:
- 查全率 Precision:$P={TP\over {TP+FP} }$,指真正例占所有预测正例的比例(预测正确的比例);
- 查准率 Recall:$R={TP\over TP+FN}$,指真正例占所有真实正例的比例(找回正确的比例);
- 根据 $TP,FP,TN,FN$ 可绘制混淆矩阵(confusion matrix);
- F1 score:$F_1=2\times \frac{P\times R}{P+R}$,即其调和平均数;
- $F_\beta=\frac{(1+\beta^2)\times P \times R}{(\beta^2\times P)+R}$,对 P、R 有所偏重;
- P-R 曲线:依次增加 threshold values,以改变真假正负例的比例,画出 P-R 曲线;
ROC 曲线(考)
全称”受试者工作特征”,x-y 表示 FP-TP,同样按预测概率排序样例得到 $m^+$ 个 TP 与 $m^-$ 个 FP,画出依次减小阈值,若当前点为真实正例,则标记 $(x,y+\frac{1}{m^+})$,否则标记 $(x+\frac{1}{m^{-} },y)$。
说这么多,其实就是,横轴为假正例占所有真实反例的比例,纵轴为真正例占所有真实正例的比例(该阈值下的查准率 Recall)。
-
AUC:
t 检验
假设做交叉验证后,得到了 $k$ 个测试错误率 ${\hat\epsilon_k}$,假设 $\epsilon=\epsilon_0$。采x用 t 检验,对显著度 $\alpha$,若 $[t_{-\alpha/2},t_{\alpha/2}]$ 位于临界范围 $\mid \mu-\epsilon_0\mid$ 内,则接受假设,认为泛化误差率 $\epsilon=\epsilon_0$,置信度为 $1-\alpha$;
交叉验证 t 检验
一般地,对不同学习器性能进行比较时,比如对 A, B 学习器,得到 ${\hat\epsilon_k^A}, {\hat\epsilon_k^B}$,可用 k 折交叉验证”成对 t 检验”进行比较检验。
如,对每对结果求差,$\Delta_i=\epsilon_i^A-\epsilon_i^B$,若性能相同,则差值为 0,继而用 ${\Delta_k}$ 进行 t 检验。
-
问题:样本有限,交叉验证导致训练集重叠,测试错误率不独立,从而过高估计假设成立概率。
-
解决方法:5*2 交叉验证法:
-
Friedman 检验
用于对多个算法进行比较。
根据性能好坏排序,若性能相同,则平分序值,得到平均序值 $r_i$:
Nemenyi 后续检验
当假设”所有算法性能相同”被拒绝,可用 Nemenyi 后续检验进一步区分算法:
\[CD=q_\alpha \sqrt{\frac{k(k+1)}{6N} }\]若两算法平均序值之差超过阈值 $CD$,则以相应置信度拒绝以上假设。
偏差与方差 (bias & variance)
- 偏差:$bias^2(x)=\mathbb{E}_D[(\bar{f}(x)-y)^2]$,期望预测值与真实值之间的差异;
- 方差:$\sigma^2=\mathbb{E}_D[(f(x;D)-\bar{f}(x))^2]$,不同训练集产生的预测值和期望预测值之间的差异;
- 噪声:$\epsilon^2=\mathbb{E}_D[(y_D-y)^2]$,表数据集中标记值和真实值的差异,是数据集本身携带的;
- 泛化误差:假设 $\epsilon=\mathbb{E}_D[y_D-y]=0$,则泛化误差 $E(f;D)=bias^2+\sigma^2+\epsilon^2$
其中,偏差刻画的是学习算法本身的拟合能力,方差刻画训练数据扰动对学习性能的影响,噪声表示的是学习问题本身的难度(若认为标记的正确率表征难度)。
规范化方法
- Min-Max Normalization:$ x’=x’{min}+\frac{x-x{min} }{x_{max}-x_{min} }\times (x’{max}-x’{min}) $
- 优点:方法简单,有利于在线更新(仅当新元素大于阈值时才重新规范所有数据);
- 缺点:易受极端数据影响;
- z-score Normalization:$x’=\frac{x-\bar{x} }{\sigma_x}$
- 优点:对极端数据不敏感,且元素分布在 0 周围;
- 缺点:在线计算复杂度高;
损失函数相关
- 0-1 损失函数:$\mathcal{L}(Y,f(X))=(\mathbb{I}(Y=f(X)))$,非凸函数;
- 平方损失函数(MSE):$\mathcal{L}(Y,f(X)) = (Y-f(X))^2$
- 绝对损失函数(MAE):$\mathcal{L}(Y,f(X))=\mid Y-f(X) \mid$
- 对数(似然)损失函数:$\mathcal{L}(Y,P(Y\mid X)) = -\log P(Y\mid X)$,鲁棒性差,但适合表征概率分布的场景;
- 因为多分类时通常使用 one-hot encoding,故此时对数损失函数与交叉熵等价;
损失函数的期望:
- 风险函数/期望损失:$R_{exp}(f)$;
- 经验风险:$R_{emp}(f)$,是关于训练集的平均损失;
在给定策略下,学习的目标是希望找到 $\arg \min\limits_f R_{exp}(f)$,而期望损失常用经验风险来代替,故问题转化为最小化 $R_{emp}(f)$:
- 经验风险最小化:求解 $f$ 满足 $\min\limits_{f\in \mathcal{F} } \frac{1}{N}\sum\limits_{i=1}^N \mathcal{L}(y_i, f(x_i))$。
- 特点:数据量大时效果较好,数据量小时容易过拟合;
- 结构风险最小化/正则化:为了减少过拟合,提出了 $R_{srm}(f)=\frac{1}{N}\sum\limits_{i=1}^N \mathcal{L}(y_i, f(x_i)) + \lambda \mathcal{J}(f)$,其中 $\lambda$ 为一系数,而 $\mathcal{J}(f)$ 用以衡量模型复杂度,比如可以用模型参数向量的范数来表示模型复杂度;
凸函数
为什么凸函数这么重要呢为什么呢为什么呢?
凸函数:函数曲线上的任意两点连线在这部分函数曲线之上,也即:$\lambda x_1 + (1-\lambda)f(x_2) \ge f(\lambda x_1 + (1-\lambda) x_2),\lambda \in [0, 1]$。
对于凸函数有,导数为零处(二阶导大于零)一定为极小值点,局部最优就是全局最优。
对偶问题
**待补充 **
Ch 03 线性模型
基本形式
\[f(x)=w_1x_1+w_2x_2+...+w_dx_d+b\\ i.e.\ f()=w^Tx+b\]优点
-
形式简单,易于建模
-
可解释性好
-
是非线性模型的基础
策略
-
最小二乘法 $ (w^,b^)=\arg\limits_{(w,b)} \min\sum\limits_{i=1}^m(f(x_i)-y_i)^2 $,也即最小化 MSE。则分别对两变量求导,得到闭式解。
-
对多元线性回归,也即,$ x_i=(x_{i1};x_{i2};…;x_{id}) $,同样有最小二乘法,优化目标变为: \(\hat{w}^*=(y-\hat{w}X)^T(y-\hat{w}X),\hat{w}=(w;b)\) 对其求导即可。
广义线性模型
\[y=g^{-1}(w^Tx+b)\]- 联系函数:单调可微函数 $g(·)$ 称为联系函数
- 作用:从线性回归函数出发,拟合目标 $y$ 的衍生物,从而达成非线性映射的目的。
对数线性回归
令 $g(·)=ln(·)$,则目标函数为 $lny=w^Tx+b$
对二分类任务 $z=w^Tx+b, y\in {0, 1}$ 而言,最理想的情况是使用单位阶跃函数: \(y=\left\{ \begin{aligned} 0, & z<0 \\ 0.5, & z=0 \\ 1, & z>0 \\ \end{aligned} \right.\) 但容易发现,单位阶跃函数的缺点是不连续,不便于更新。
于是提出了更加平滑的替代函数:
对数几率函数/逻辑斯蒂函数 Logistic Function
- 几率:$\frac{y}{1-y}$,即目标发生与不发生的比率;
- 对数几率:$ln\frac{p(y=1\mid x)}{p(y=0\mid x)}=ln\frac{y}{1-y}$。
则可令线性回归逼近对数几率,即 $g(y) = ln\frac{y}{1-y}$,变换得到: \(y=\frac{1}{1+e^{-(w^Tx+b)} }\) 立刻得: \(p(y=1\mid x) = \frac{e^{w^Tx+b} }{1+e^{w^Tx+b} }\\ p(y=0\mid x) = \frac{1 }{1+e^{w^Tx+b} }\)
优点
- 无需事先假设数据分布;
-
引入了非线性特质,可得到”类别”的近似概率预测;
- 单调可微,任意阶可导,可直接应用现有数值优化算法求最优解;
优化方法
最大化样本分布似然 $\mathcal{l}(w,b)=\sum\limits_{i=1}^m \ln p(y_i\mid x_i;w_i;b)=\sum ln (y_ip_1(\bar{x}_i;\pmb{\beta})+(1-y_i)p_0(\bar{x}_i;\pmb{\beta}))$
等价化为最小化负对数似然函数求解(优化方法:牛顿法、梯度下降法)。
缺点
当该函数的特例,sigmoid function $y=\frac{1}{1+e^{-x} }$ ,在深度网络中的隐藏层中作为激活函数传播时,由于其在远离零点处梯度极小,且值域上最大值为 0.25,故容易出现计算缓慢、梯度消失等问题。
于是提出了 $ReLU=max(0, x)$,求导便捷。但它也有缺点:零点附近不可微、容易出现 dead ReLU 问题,也即反向传播中易使一些 NN 的导数永远为 0 而不再进行更新;
为了解决这个问题,又提出了 $LeakyReLU=max(ax, x)$,其中 $a$ 是一个极小的系数,它也有缺点,下回再讲。
注意:在二分类的输出层中,激活函数仍常选择 sigmoid function。
线性判别分析(LDA, Linear Discriminant Analysis)
参考 https://www.cnblogs.com/pinard/p/6244265.html、https://zhuanlan.zhihu.com/p/264578345
一种监督降维技术。优化方法:为最大化广义瑞利商;目标:投影(e.g. $\bf{R}^d\rightarrow \bf{R}$)后,使投影点类间散度最大化、类内散度最小化。
二分类 LDA
将数据点 $x$ 投影到向量 $w$ 上,计算 $x$ 离原点的距离 $w^Tx$(此处投影点 $p=(\frac{w^Tx}{w^Tw}w)$,分母全程相同,则略去)。
我们定义:$X_i, \mu_i, \Sigma_i$ 为第 $i$ 类样本的集合、均值向量、协方差矩阵,则有: \(\mu_i=\frac{1}{N_i}\sum\limits_{x\in X_i} x\\ \Sigma_i=\sum\limits_{x\in X_i} (x-\mu_i)(x-\mu_i)^T\) LDA 目标的具体体现即为:使各类别数据尽可能集中,不同类别数据的中心($w^T\mu_i$)尽可能远离。
-
各类数据尽可能集中(使用样本与类别中心投影距离的平方和衡量):
-
$s^2i = \sum\limits{x\in X_i}(w^Tx - w^T\mu_i)^2=(w^T\sum\limits_{x\in X_i}(x-\mu_i))(\sum\limits_{x\in X_i}(x-\mu_i)w)=w^T\Sigma_iw$
此处定义 $S_w = \sum \Sigma_i$ 为类内散度矩阵;
-
-
不同类别中心尽可能远离(使用不同类别中心投影距离的平方衡量):
-
定义 $S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T$ 为类间散度矩阵,则:
$(w^T\mu_0 - w^T\mu_1)^2 = w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw=w^TS_bw$
-
则有优化目标(fisher LDA): \(\arg\limits_w \max J(w)=\frac{(w^T\mu_0 - w^T\mu_1)^2}{s_0^2+s_1^2}=\frac{w^TS_bw}{w^TS_ww}\) 上面的式子有个名字,叫广义瑞利商,待补充。
利用其性质,或求导得:当 $S_w$ 为可逆矩阵,$(S_w^{-1}S_b)w=J(w)w$,也即:矩阵 $S^{-1}B$ 对应的最大特征值即为 $J(w)$,而相应的特征向量即为投影方向 $w$。
对于二分类问题,有 $S_bw$ 和 $\mu_0-\mu_1$ 方向平行。忽略投影向量大小时,有 $w=S_w^{-1}(\mu_0-\mu_1)$。
多类 LDA
对多类 LDA,$J(W)$ 的计算有以下不同点:
- $W$ 为一$d$ 维的投影超平面,其为一形状 $(n,d)$ 的矩阵;
- $S_b = \sum\limits_{i=1}^{K} N_i(\mu_i-\mu)(\mu_i-\mu)^T$,(使用不同类别中心到样本中心投影距离的平方和衡量,感觉有点奇怪,)其中,$K$ 为类别总数,$n_i$ 为第 $i$ 类样本数目,$\mu$ 为所有样本的均值向量;
- (换成 $S_b = \sum (\mu_i - \mu’)(\mu_i - \mu’)^T$,$\mu’=\frac{1}{K}\sum \mu_i$ 会不会更好?)
最终,得到 $W$ 即矩阵 $S_w^{-1}S_b$ 的前 $d$ 大特征值对应的特征向量张成的矩阵。
- $d\le K-1$:因为 $r(S_w^{-1}S_b)\le r(S_b)$,而 $S_b$ 中,$N\mu=\sum\limits_i N_i\mu_i$,故有 $r(S_b)\le K-1$,其最多有 $K-1$ 个非零特征值。
步骤
- 输入:数据集 $X$,类别数量 $K$,待降维维数 $d$;
- 输出:投影空间 $W$;
- 计算各类别 $\mu_i, \Sigma_i$,从而算出类内散度矩阵 $S_w = \sum \Sigma_j$;
- 计算类间散度矩阵 $S_b = \sum\limits_{i=1}^{K} N_i(\mu_i-\mu)(\mu_i-\mu)^T$;
- 计算 $S_w^{-1}S_b$ 的特征向量(按特征值大小排序),取出前 $d$ 个作为投影空间 $W$;
- 对数据进行投影 $Y=WX$ 即可。
多分类学习
-
二分类学习方法推广到多类
-
利用二分类学习器解决多分类问题
-
拆分问题,为拆分出的每个任务训练一个分类器;
-
拆分策略:一对一、一对其余、多对多
-
一对一:两两配对,$\frac{N(N-1)}{2}$ 个二类任务,投票产生最终分类结果;
-
一对其余:N 个二类任务,比较各个预测置信度,最大类作为最终结果;
-
多对多:
-
-
-
对每个分类器的预测结果进行集成,得到最终的多分类结果
-
类别不平衡
解决方法
- 类别平衡正例预测:$\frac{y}{1-y}>1 \rightarrow \frac{y}{1-y}>\frac{m^+}{m^-}$,$m^+<m^-$,存疑
- 再缩放:
- 调整预测置信度阈值
- 去除/增加相应多出/缺少的反/正例
感知机
感知机是一种线性模型,用于二分类任务,其基本形式如 $f(x)=sgn(w·x+b)$。其中,输入空间 $\mathcal{X}\subseteq R^n$,表示特征向量,对应特征空间中的点;而输出空间 $Y={+1,-1}$,表示特征的类别。
- 线性可分:(是否)存在超平面 $\mathcal{S}:w·x+b=0$,对于给定数据集中的数据能够区分 $wx_i+b><0,y_i=\pm 1$。
对于线性可分数据集,确定这个超平面 $\mathcal{S}$ 的参数 $w,b$。而为了方便可导优化,有:
知错误分类点到超平面 $\mathcal{S}$ 的总距离:$-\frac{1}{\Arrowvert w\Arrowvert }\sum\limits_{x_i\in \mathcal{M}} y_i(w·x_i+b)$,故有:
损失函数
$\mathcal{L}(w,b)=-\sum\limits_{x_i\in \mathcal{M}} y_i(w·x_i+b)$。
优化算法 (e.g. SGD, Stochastic Gradient Descent)
随机选取误分类集合 $\mathcal{M}$ 中一个误分类点下降,更新直至 $\mathcal{M}$ 为空;
-
原始形式:$f(x)=sgn(w·x+b)$
$\left{ \begin{aligned} \nabla_w \mathcal{L}(w,b)=-\sum\limits_{x_i\in \mathcal{M} }x_iy_i \ \nabla_b \mathcal{L}(w,b)=-\sum\limits_{x_i\in \mathcal{M} }y_i \end{aligned} \right. \rightarrow \left{ \begin{aligned} w & \leftarrow w+\eta x_iy_i\ b & \leftarrow b + \eta y_i \end{aligned} \right.,\eta\in (0, 1]$
-
对偶形式:$f(x)=sgn(\sum\limits_{j=1}^N \alpha_jy_jx_j·x+b),\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T$。
也即,将 $w={w_j}$ 看作是 ${x_jy_j}$ 的线性组合,而 $\alpha$ 是系数向量。每次更新将 $\alpha_i \leftarrow \alpha_i + \eta$ 即可。其优点在于更新方便,且可预处理 Gram Matrix $G=[x_i·x_j]_{N\times N}$,降低在线计算复杂度。
-
注意:
- 采用不同初始参数、不同误分类点次序更新,都可能得到不同的超平面 $\mathcal{S}$;
- 根据 Novikoff 定理当;训练集线性可分,则以上感知机算法(原始形式)的误分类次数是有界的,具体界此处不表;当训练集线性不可分,迭代结果会发生震荡。
Ch 04 决策树
决策树,根据树结构来进行预测。
- 可以被视为 if-then 操作的集合,树上路径互斥且完备
学习过程
- 特征选择
- (贪心地)生成决策树
- (剪枝、全局优化)修剪决策树
- 在所有可能的决策树中取最优决策树是 NPC 的,故常常采用启发式优化
特征选择
在从根向叶结点分类的过程中,选择更泛化的分类特征很重要。
- 原则:选择减少不确定性更大的特征;
- 指标:信息增益、信息增益比(增益率)、基尼指数。
-
熵:度量随机变量的不确定性,熵越大,不确定性越高:
$H(X)=-\sum\limits_{i=1}^n p_i\log p_i, p_i=P(X=x_i)$,显然有 $0\le H(X)\le \log n$。(约定 $p=0, \log p=0$)
- 经验熵:其式中概率由数据估计而得到的熵;
-
条件熵:已知随机变量 $X$ 分布的条件下,$Y$ 的不确定性:
$H(Y\mid X) = \sum\limits_{i=1}^n p_iH(Y\mid X=x_i),p_i=P(X=x_i)$,表示 $X$ 给定的条件下,$Y$ 的条件概率分布对 $X$ 的期望。
信息增益
设训练集为 $D$,特征为 $A$,则信息增益 $g(D,A)=H(D)-H(D\mid A)$,其含义为:得知某个特征,而使训练集类信息的不确定性减少的程度;越大越好。
设 $D$ 中有 $K$ 个类 ${C_k}$,$A$ 有 $n$ 个不同的特征取值 ${D_n}$,则按经验熵计算,得到 $g(D,A)=(-\sum\limits_{k=1}^K \frac{\arrowvert C_k\arrowvert }{\arrowvert D\arrowvert}\log \frac{\arrowvert C_k\arrowvert }{\arrowvert D\arrowvert})-(\sum\limits_{i=1}^n \frac{\arrowvert D_i\arrowvert }{\arrowvert D\arrowvert}H(D_i)) $
- 应用:ID3 决策树学习算法。
信息增益比
用以校正信息增益存在的问题:偏向于选择取值较多的特征。
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$,其中 $H_A(D)=-\sum\limits_{i=1}^n \frac{\arrowvert D_i\arrowvert }{\arrowvert D\arrowvert}\log \frac{\arrowvert D_i\arrowvert }{\arrowvert D\arrowvert}$,意即该特征 $A$ 本身取不同结果的可能性度量。
- 这次的问题是偏向取值较少的特征。
- 应用:C4.5 采用的启发式方法:先从候选特征中找出信息增益高于平均水平的特征,再从中选取增益比最高的。
基尼指数
- 基尼值:$Gini(D)=\sum\limits_{k=1}^K\sum\limits_{k’\ne k}p_{k}p_{k’}=1-\sum\limits_{k=1}^K p_k^2$,反映从 $D$ 中随机抽取两个样本,其类别标记不一致的概率;基尼值越小,数据集 $D$ 纯度越高。
$G_i(D,A)=\sum\limits_{i=1}^n \frac{\arrowvert D_i\arrowvert }{\arrowvert D\arrowvert} Gini(D_i)$,选取基尼指数最小的特征作为最优划分特征。
- 应用:CART。
生成决策树
-
以 ID3 算法为例:以经验熵估计,递归地选择 $g(D,A_g)$ 最大的特征 $A_g$ 进行构造,直到 $g(D,A_g)$ 小于阈值 $\epsilon$,否则置其为单节点并以其中最大实例数 $C_i$ 为该结点的类标记。
-
CART 算法(分类与回归树):
-
分类树:这里提一下当特征为连续性特征时,C4.5, CART 算法均将其离散化后根据某个指标(信息增益比、基尼系数)来确定最优切分点(二分):对 $A_j$ 在 $D$ 上出现的 $n$ 个不同取值 $a_i$,排序后得到候选划分点集合 $T_{A_j}{\frac{a^i+a^{i+1} }{2}\mid 1\le i \le n-1}$,此处根据基尼系数来确定最优切分点 $s$。
-
回归树:递归地划分子区域:选择最优切分维度 $j$ 与切分点 $s$。设 $R_{1,2}(j,s)={x\mid x^{(j)}\le,> s}$ 表示切分后得到的两子区域,则有:
其中,$\hat{c_m}=\frac{1}{N_m}\sum\limits_{x_i\in R_m(j,s)}y_i,m\in {1,2}$。
使用以上公式来衡量、确定最优切分点与最优切分维度(特征)。
-
修剪决策树
- 预剪枝:划分前估计该特征能否带来泛化性能提升(实践上,能否提高验证集精度),来确定是否划分;
- 训练、测试时间开销小;
- 欠拟合:局部贪心。
-
后剪枝:生成完整决策树后,自底向上地对非叶结点进行考察:
设该树叶节点数量 $\arrowvert \mathcal{T}\arrowvert $,对叶结点 $t$,有 $N_t$ 个样本点,则: \(C_\alpha(\mathcal{T})=\sum\limits_{t=1}^{\arrowvert \mathcal{T}\arrowvert} N_tH_t(\mathcal{T})+\alpha\arrowvert \mathcal{T}\arrowvert\) 其中 $H_t(\mathcal{T})$ 表结点 $t$ 的熵值,其整体表示该树 $\mathcal{T}$ 的拟合程度、复杂度度量。
剪枝过程则为:若一组叶结点回缩至其父结点前后,对应的 $C_\alpha(\mathcal{T})$ 减小,则剪枝。
Ch 05 神经网络
建议看我前一篇博客。
Ch 06 支持向量机
这章没写充分,待补充
SVM 支持向量机用于二分类,生成一个超平面,将数据集根据标签划分为两类。
可以感性理解为感知机的进阶形式。
显然,将样本集划分为两类的超平面有很多,我们常用”间隔最大化”来选取正负支持向量正中间的,”最优”的超平面。
函数间隔
定义:超平面 $w^Tx+b=0$ 关于样本点 $(x_i, y_i)$ 的函数间隔为:$\hat{\gamma_i} = y_i(w·x_i+b),y_i=\pm 1$(分母一致,略去)
定义超平面 $w^Tx+b=0$ 关于训练集的函数间隔为:$\hat{\gamma} = \min\limits_{i=1,2,…,n}\hat{\gamma_i}$。
- 几何间隔:为了更规范地确定间隔,我们归一化 $\Arrowvert w\Arrowvert = 1$,也即:$w\leftarrow \frac{w}{\Arrowvert w\Arrowvert}, b\leftarrow \frac{b}{\Arrowvert w\Arrowvert}, $。则样本点的间隔可表示为 $\gamma_i = y_i(w^Tx + b)$。(其实就等价于点到平面的真实距离)
支持向量
数据集线性可分时,与超平面距离最近/间隔最小的样本。
我们将支持向量到超平面的距离设为 $\pm 1$,之所以这样做方便推导与优化,是因为最小间隔和超平面系数成比例关系,设定为 1 不会对目标函数优化产生任何影响。
故有优化目标:最大化正负支持向量间的间隔 $\max \frac{2}$,选取其正中间的,”最优”的超平面。
为了方便起见,转换一下得优化问题:
基本形式
\[\arg\limits_{w,b}\min \frac{1}{2}{\Arrowvert w\Arrowvert}^2\\ s.t. y_i(w^Tx_i+b)\ge 1\]对偶问题
- 引入拉格朗日乘子 $\alpha_i \ge 0$:$\mathcal{L}(w,b,\alpha) = \frac{1}{2} \Arrowvert w\Arrowvert ^2 - \sum\limits_{i=1}^m \alpha_i(y_i(w^Tx_i+b)-1)$;
- 求导并代入得到:$\arg\limits_{\alpha}\min \frac{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. \ \sum\limits_{i=1}^m \alpha_iy_i=0$
- 最终模型为 $f(x)=w^Tx+b=\sum\limits_{i=1}^m \alpha_iy_ix_i^Tx+b$
对于以上形式的优化问题,常用 SMO (Sequential Minimal Optimization) 序列最小优化算法优化,也即每次固定住其余参数,只优化选取的某个参数。
在 SVM 对偶问题中最简单的情况是:每次选取一对 $(\alpha_i, \alpha_j)$ 进行优化,此时原约束变为 $\alpha_iy_i+\alpha_jy_j=-\sum\limits_{k\ne i,j}\alpha_ky_k, \alpha_i\ge 0, \alpha_j \ge 0$,则可回代方程式得到单变量二次规划问题,可求出闭式解: \(\left\{ \begin{aligned} \alpha_i=-\alpha_jy_j/y_i-(\sum\limits_{k\ne i,j}\alpha_ky_k)/y_i\\ \arg\limits_{\alpha_i}\min \frac{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 \end{aligned} \right.\)
不断如此更新,直至收敛,得到最优参数 $\alpha^*$。
确定后,$b=-\frac{\max_{j,y_j=-1}\sum\limits_{i=1}^m \alpha_iy_ix_i^Tx_j+\min_{j,y_j=1}\sum\limits_{i=1}^m \alpha_iy_ix_i^Tx_j}{2}$,即通过支持向量求解。
最终,SVM 的解具有稀疏性,其确定仅与支持向量有关。(可以丢掉其他训练数据)
好处:
-
- 转换问题约束;
- 方便核函数的引入;
- 改变问题复杂度:原始问题下,求解 $w$ 与样本维度有关,而对偶问题中 $\alpha$ 与样本数量有关。
核技巧
问题
数据集并不线性可分。
解决方案
将样本从原始空间映射到高维特征空间,从而将超曲面模型对应到超平面模型上。
核映射
$\mathcal{X}$ 为输入的原始空间,$\mathcal{H}$ 为特征空间,若存在映射 $\phi(x):\mathcal{X}\rightarrow \mathcal{H},\forall x,z\in \mathcal{X},\mathcal{K}(x,z)=\phi(x)·\phi(z)$,则:
称 $\mathcal{K}(·,·)$ 为核函数,$\phi(·)$ 为映射函数。
- 一般不显式设计核映射,而是设计核函数。
正定核函数
设 $\mathcal{K}:\mathcal{X}\times\mathcal{X}\rightarrow{R}$ 是对称函数,$\forall x,\ \mathcal{K}(x,z)$ 对应的 Gram Matrix $K=[\mathcal{K}(x_i,x_j)]_{m\times m}, \forall x_i\in \mathcal{X},i=1,2,…,m$ 为半正定矩阵,则 $K(x,z)$ 为正定核函数。
核支持向量机
加入核函数,则 SVM 对偶形式变为: \(\arg\limits_\alpha \min \frac{1}{2}\sum\limits_{i=1}^m\sum\limits_{j=1}^m \alpha_i \alpha_j y_iy_j \phi(x_i)^T\phi(x_j) - \sum\limits_{i=1}^m \alpha_i\\s.t. \sum\limits_{i=1}^m \alpha_iy_i = 0\) 预测函数变为:$f(x)=w^T\phi(x)+b=\sum\limits_{i=1}^m \alpha_i y_i \phi(x_i)^T\phi(x) + b$
映射函数只以内积形式出现,故一般只定义核函数本身即可。
常用核函数
软间隔与正则化
问题
合适的核函数很难确定,最终结果虽线性可分,是否源于过拟合的产物也不清晰。
解决方案
引入”软间隔”进行正则化,允许个别样本点出现于间隔带中。具体地,引入松弛变量 $\xi_i\ge 0$,约束条件变为 $y_i(w^Tx_i+b)\ge 1-\xi_i$。
则优化目标变为: \(\arg\limits_{w,b}\min \frac{1}{2}{\Arrowvert w\Arrowvert}^2 + C\sum\limits_{i=1}^m \xi_i \\ s.t. y_i(w^Tx_i+b)\ge 1-\xi_i, \xi_i \ge 0\) 其中,惩罚程度 C>0,当其无穷大表示引入软间隔,否则退化为原始 SVM。
也有其他形式如: \(\arg\limits_{w,b}\min \frac{1}{2}{\Arrowvert w\Arrowvert}^2 + C\sum\limits_{i=1}^m l_{0/1}(y_i(w^T\phi(x_i)+b)-1)\) 此处 $l_{0/1}$ 即 0-1 损失函数,当内容物小于 0 返回 1,否则返回 0。由于不易优化,常采用 hinge 损失函数等替代。
也即,使用不满足硬间隔的样本约束参数限制,但无强制性的松弛变量 $\xi_i$。
支持向量回归(SVR)
待补充。
核方法
表示定理:对任意单调增函数 $\Omega$(结构风险)与任意非负损失函数 $l$(经验风险),优化问题: \(\arg\limits_{h\in \mathbb{H} } \min F(h) = \Omega (\Arrowvert h \Arrowvert_{\mathbb{H} }) + l(h(x_1), ..., h(x_m))\) 的解总可以写为 $h^*=\sum\limits_{i=1}^m \alpha_i \mathcal{K}(·,x_i)$。
与感知机的区别
- 感知机基于误分类损失梯度下降,满足约束的超平面个数也不唯一。而 SVM 求解的是几何间隔最大的超平面(有且仅有一个)。
Ch 07 贝叶斯估计
贝叶斯决策论
对于分类问题,已知所有相关概率,考虑如何基于这些概率和误判损失选择最优的分类标签。
- 条件风险:$R(c_i\mid \mathrm{x})=\sum\limits_{j=1}^N\lambda_{ij}P(c_j\mid \rm{x}))$,表示样本 $\rm{x}$ 应分类为某个 $c_j$,却误分类为 $c_i$ 的期望损失。其中 $\lambda_{ij}$ 表示将类别 $j$ 错分为 $i$ 造成的损失。
- 贝叶斯判定准则:最小化总体风险 $R(h)=\mathrm{E}_x[R(h(\rm{x})\mid \rm{x})]$,也即,对于每个样本,选择能使其条件风险最小的类别即可,此时 $h^{}$ 被称为贝叶斯最优分类器,$R(h^{})$ 被称为贝叶斯风险。
- 若 $\lambda_{ij}=1\ if\ i\ne j\ else\ 0$,则 $R(c\mid \rm{x})=1-P(c\mid \rm{x})$,$h^{*}(x)=\arg\limits_{c\in y} \max P(c\mid \rm{x})$。
极大似然估计
要得到上述所示后验概率 $P(c\mid \rm{x})$,则可以引入一种生成式模型,对联合概率分布 $P(c,\rm{x})$ 建模,再获得后验概率——贝叶斯定理: \(P(c\mid\rm{x})=\frac{P(c,\rm{x})}{P(\rm{x})}=\frac{P(c)P(\rm{x}\mid c)}{P(\rm{x})}\) 其中,$P(c)$ 为先验,$P(\rm{x} \mid c)$ 为似然,也即:后验正比于先验与似然。
而要估计这样的似然,假设这个概率被某个参数唯一确定,那么任务也就变成了通过训练集估计参数。
常见的两大参数估计过程学派有:贝叶斯学派(参数本身服从先验分布,基于此计算参数的后验分布)和频率主义学派(参数虽然未知,但存在客观值)。这里要讲述的 MLE 就来自于后者。
一般地,假设某类样本独立同分布,则假设其满足某种概率分布,其参数 $\theta_c$ 对数据集 $D_c$ 的似然为 $P(D_c\mid \theta_c)=\prod\limits_{\rm{x}\in D_c}P(\rm{x}\mid \theta_c)$,通常为了防止下溢,采用对数似然 $LL(\theta_c)=\log P(D_c\mid \theta_c )$,此时其极大似然估计 $\hat{\theta_c}$ 为 $\hat{\theta_c}=\arg\limits_{\theta_c}\max LL(\theta_c)$。
朴素贝叶斯分类器
属性条件独立性假设:每个属性独立地对分类结果发生影响。
基于此,上式可重写为:$P(c\mid\rm{x})=\frac{P(c,\rm{x})}{P(\rm{x})}=\frac{P(c)}{P(\rm{x})}\prod\limits_{i=1}^d P(x_i\mid c)$,其中 $d$ 为属性数目,$x_i$ 为第 $i$ 个属性的取值。
去掉 $P(x)$,求 MLE,即为朴素贝叶斯分类器。
一般地,先验概率 $P(c)=\frac{\arrowvert D_c\arrowvert}{\arrowvert D\arrowvert}$,似然 $P(x_i\mid c)=\frac{\arrowvert D_{c,x_i}\arrowvert}{\arrowvert D_c\arrowvert}$(离散)。
拉普拉斯平滑
存在这样的情况:训练集样本不包含某些类别/属性取值,但测试集中含有。
故需要对概率估计值进行平滑,具体地,$N$ 表示所有可能的类别数量,$N_i$ 表示第 $i$ 个属性可能的取值数,则修正有:$\hat{P}(c)=\frac{\arrowvert D_c\arrowvert+1}{\arrowvert D\arrowvert+N}$、$\hat{P}(x_i\mid c)=\frac{\arrowvert D_{c,x_i}\arrowvert+1}{\arrowvert D_c\arrowvert+N_i}$。
Ch 08 集成学习
通过构建并结合多个好而不同的个体学习器提升性能。
结合策略
- 等权平均、加权平均法
- 投票法:(如取 max)
- 学习法等
Boosting
- 特点:个体(弱)学习器相关性强,故串行调整训练数据分布进行集成学习,降低偏差。
以 Adaboost 为例:初始化训练集权重后,每轮选择一个学习器池中损失最小的弱学习器(若准确率低于随机选择,二分类下即 0.5,则终止),并根据其对训练集的误差计算该轮学习器的权重值(分类误差小,权重更大),并根据这个权重调整训练集的权重,然后重复 T 轮,最终将这些弱学习器的预测结果进行加权得到最终的预测结果。
Bagging
- 特点:个体学习器相关性弱,故并行化自助采样、投票进行集成学习,降低方差。
随机森林
对决策树进行类似于 bagging 的变种集成学习。
- 引入样本采样、特征选择的随机性