傍晚小街路面上沁出微雨后的湿润，和煦的细风吹来，抬头看看天边的晚霞，嗯，明天又是一个好夭气。走到水果摊旁，挑了个根蒂蜷缩、敲起来声音浊响的青绿西瓜，一边满心期待着皮薄肉厚瓢甜的爽落感，一边愉快地想着，这学期狠下了工夫，基础概念弄得清清楚楚，算法作业也是信手拈来，这门课成绩一定差不了!

绪论

基本概念

通过对经验的利用，对新情况做出决策

  • 模型：泛指从学习中获取的结果
  • 数据集：收集到的一组数据
  • 示例/样本：关于一个事件或对象的描述
  • 属性：事件或对象在某方面的表现或性质
  • 属性空间/样本空间/输入空间：属性张成的空间，是讨论的基础
  • 特征向量：属性值组成的在样本空间中的向量

数据集包含m个示例，每个示例由d个属性描述。则每个示例由xi⃗=(xi1,xi2,...,xid)\vec{x_i}=(x_{i1},x_{i2},...,x_{id})​是d维样本空间S中的一个向量。

  • 学习/训练：从数据中学得模型
  • 训练数据：训练过程中使用的数据
  • 训练样本：训练数据中的每个样本
  • 训练集：训练样本组成的集合
  • 假设：学的模型关于数据的某种潜在规律假设

训练完模型后，需要对模型进行测试：

  • 测试：对模型进行预期的过程
  • 测试样本：被预测的样本
  • 泛化：学得模型适用于新样本的能力

有监督学习

有监督学习指的是训练数据拥有标记信息。光有数据本身是无法做出预测的，还需要有关训练样本的结果信息

  • 样例：拥有了标记信息的示例。一般用(xi⃗,yi)(\vec{x_i},y_i)表示第i个样例
  • 标记空间/输出空间：所有标记的集合

预测结果通常也有离散和连续两种情况：

  • 分类：预测的是离散值
  • 回归：预测的是连续值

无监督学习

无监督学习指的是训练数据没有标记信息。

典型的例子是聚类：

  • 聚类：将训练集中的数据分为若干组
  • 簇：聚类分后得到的每个组

聚类中因为训练数据没有标记，所有分类的标准往往是预先不知道的，是由机器自信揭示的关于数据的规律

假设空间

  • 归纳：从特殊到一般的泛化
  • 假设：从一般到特殊的特发

从样例中学习是一个归纳的过程

  • 假设空间：在特定假设“可决策”的条件下，由输入空间到输出空间的映射的集合。

    该空间是一个函数空间，即由函数所构成的集合

    以好瓜分类为例：目的是得到是否为好瓜的分类，由三个属性描述，每个属性有3种可能的取值。故在好瓜可决策的条件下，总的样本空间数为4∗4∗4+1=654*4*4+1=65：4代表3种取值加上不重要为*的情况，+1为根本不存在好瓜的极端情况。

  • 版本空间：就是与训练集一致的所有假设（函数）所构成的集合，是假设空间的一个子集。

将学习过程看作一个在所有假设组成的空间中进行搜索的过程，学习到的模型对应了假设空间中的一个假设。

可能会得到多个与训练集一致的假设

归纳偏好

可能会得到多个与训练集一致的假设，怎么得到更好的一个，算法自身需要有一个归纳偏好。

归纳偏好：学习算法自身在假设空间中对假设进行自信选择的启发式或价值准则。

一般选取最简洁的假设。但是什么是更简洁的是难以定义的。

NFL定理：考虑到所有潜在问题，所有学习算法都一样好，有相同的期望性能。

模型评估与选择

基本概念

错误率和正确率针对分类结果：

  • 错误率：m个样品中有a个分类错误，错误率E=a/m
  • 精度：1-错误率
  • 误差：学习器的实际预测输出与样本的真实输出差异
    • 训练误差：训练集上的误差
    • 泛化误差：新样本上的误差
  • 过拟合：训练误差减小的同时，泛化性能下降

评估方法

使用一个测试集，来测试学习器对新样本的判别能力，然后以测试集上的测试误差作为泛化误差的估计

对于包含m个样例的数据集D=(x1⃗,y1),(x2⃗,y2),...(xm⃗,ym)D={(\vec{x_1},y_1),(\vec{x_2},y_2),...(\vec{x_m},y_m)}，如何分割出训练集和测试机：

  • 留出法
  • 交叉验证法
  • 自助法
  • 调参与自助模型

留出法

将数据集D划分为两个互斥的集合：训练集S和测试集T，即D=S∪T,S∩T=∅D=S\cup T,S\cap T=\varnothing​。

训练器的误差会与划分方式密切相关，要尽可能维持数据分布的一致性。

通常采用分层抽样的方法，有时分层方式也是多样的，则会采取若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果。

若S太大，则T不能欢迎真实的泛化效果；若S太小，则训练效果又太差。通常将2/3~4/5的数据用于训练。

交叉验证法

将数据集D划分为k个大小相似的互斥子集：D=D1∪D2∪...Dk,Di∩Dj=∅,i≠jD=D_1 \cup D_2 \cup ...D_k,D_i\cap D_j=\varnothing,i \neq j，每个子集都尽可能保持数据分布的一致性。

每次使用k-1个子集进行训练，将剩余那个用于测试。

交叉验证法评估结果的稳定性和保真性很大程度上取决于k的选择，因而也被称为：k折交叉验证。

10折交叉验证

若k=数据集的样本数，则每次仅有一个样本不被用于训练，称之为留一法。因为只有一个，故被认为评估结果往往与直接使用D训练出的结果较为类似，比较准确。缺点是计算开销大。

自助法

想要减少训练样本规模变化造成的不同影响，同时比较高效地进行实验估计。

对包含m个样本的数据集D进行m次采样，每个样本始终不被采集到的概率是(1−1m)m−>1e(1-\frac{1}{m})^m->\frac{1}{e}，这样约有0.368的数据不被采样，用作测试集，被采样的数据用作训练集。

在样本数较小、难以划分时，自助法有较好的效果。

调参与自助模型

调参：设定学习模型的参数，相当于选择算法

  • 算法的参数：也叫做超参数，数目通常为10
  • 模型的参数：数目可能很多，通过学习来产生多个候选模型

训练多个模型后选择参数最好的那一个。

性能度量

性能：预测准确度。使用均方误差进行描述：E(f;D)=1m(f(xi)−yi)2E(f;D)=\frac{1}{m}(f(x_i)-y_i)^2

错误率和精度

错误率：分类错误的样本数占样本总数的比例

精度：分类正确的样本数占样本总数的比例

查准率和查全率

在有些时候，错误率和精度无法满足需求，还关注查询得到的结果中正确预测结果的占比，引入查准率P和查全率R

有TP+FP+TN+FN=样本总数

分类结果

查准率P=TPTP+FPP=\frac{TP}{TP+FP}，在预测为正例中预测准确的比例

查全率R=TPTP+FNR=\frac{TP}{TP+FN}，在所有正例中预测结果的比例

查准率和查全率往往是矛盾的，一个高了另一个往往就会低。会绘制一个模型的P-R曲线，来反映模型的预测性能。

定义平衡点BEP为查准率等于查全率的点，比较不同模型在其平衡点处查准率/查全率的值。

BEP有些简单了，定义F1F_1度量：F1=2∗P∗RP+R=2∗TP样例总数+TP−TNF_1=\frac{2*P*R}{P+R}=\frac{2*TP}{样例总数+TP-TN}

ROC和AUC

很多学习器为测试样本产生了一个实值或概率预测，与一定的阈值进行比较，大于阈值则为正类，小于则为反类。为了关注模型的在实际预测中的结果是否符合原有正类和反类。

真正例率TPR=TPTP+FNTPR=\frac{TP}{TP+FN}，在预测为正例中预测准确的比例

假正例率FPR=FPTN+FPFPR=\frac{FP}{TN+FP}​，在所有正例中预测结果的比例

利用TPR和FPR绘制ROC曲线，纵轴为真正例率，横轴为假正例率。ROC曲线的的y=xy=x描述了随机预测，而点(0,1)(0,1)反映了最佳预测的理想模型。

实际中用有限个训练来绘制ROC曲线，获得有限个坐标对，

为了反应不同ROC曲线的优劣，利用其包围的面积AUC来反应。

对于不连续的ROC曲线，定义AUC=12∑i=1m−1(xi+1−xi)∗(yi+1+yi)AUC=\frac{1}{2}\sum^{m-1}_{i=1}(x_{i+1}-x_i)*(y_{i+1}+y_i)​

定义损失值loss=1-AUC

代价敏感错误率与代价曲线

对于分类错误，会设置一定的代价矩阵，希望最小化总体代价。

引入代价后，原先的ROC曲线不能反映出学习器的期望总体代价，使用代价曲线进行描述。

正例概率代价为P(+)cost=p∗cost01p∗cost01+(1−p)∗cost10P(+)_{cost}=\frac{p*cost_{01}}{p*cost_{01}+(1-p)*cost_{10}}，其中p为样例为正例的概率。

比较检验

怎么比较模型的性能：进行假设检验：比较在一组样本上的分布

偏差和方差

记D为训练集，yDy_D为x在数据集上的标注，f(x;D)f(x;D)为模型f在x上的预测输出

学习算法的期望预测为f‾(x)=ED[f(x;D)]\overline{f}(x)=E_D[f(x;D)]​

方差为var(x)=ED[(f(x;D)−f‾(x))2]var(x)=E_D[(f(x;D)-\overline{f}(x))^2]

噪声为ϵ2=ED[(yD−y)2]\epsilon^2=E_D[(y_D-y)^2]

期望输出与真实输出的差别记为偏差bias2=(f‾(x)−y)2bias^2=(\overline{f}(x)-y)^2，反映了训练数据劳动造成的影响

泛化误差可以分解为偏差、方差、噪声之和

一般来说，偏差与方差是有冲突的，这称为偏差一方差窘境

  • 在训练不足时，学习器的拟合能力不够强，训练数据的扰动不足以便学习器产生显著变化，此时偏差主导了泛化错误率
  • 随着训练程度的加深，学习器的拟合能力逐渐增强，训练数据发生的扰动渐渐能被学习器学到，方差逐渐主导了泛化错误率
  • 在训练程度充足后，学习器的拟合能力已非常强，训练数据发生的轻微扰动都会导致学习器发生显著变化，若训练数据自身的、非全局的特性被学习器学到了，则将发生过拟合

线性模型

给定由d个属性值描述的示例x=(x1;x2;...;xd)x=(x_1;x_2;...;x_d)，线性模型试图学得一个属性的线性组合来进行预测的函数，即f(x)=w1x1+w2x2+...+wdxd+b=wTx+bf(x)=w_1x_1+w_2x_2+...+w_dx_d+b=w^Tx+b，可写作向量形式。

w反映了各个属性在预测中的重要性。

线性回归

可以利用最小二乘法进行基本的多元线性回归，对w和b进行估计。

线性回归是在输入空间到输出空间之间建立了一个线性映射关系，但是有时候映射关系没有那么好，可以建立非线性的映射关系，比如对数映射关系ln⁡y=wTx+b\ln y=w^Tx+b，对数起到了将预测结果和真实结果进行练习的作用。

更一般的，可以考虑使用单调可微函数g，有y=g−1(wTx+b)y=g^{-1}(w^Tx+b)，即g(y)=wTx+bg(y)=w^Tx+b，称为广义线性模型。将g称为联系函数，将线性回归模型产生的预测值与真实标记y联系起来。

对数几率回归

考虑一个二分类任务，利用z=wTx+bz=w^Tx+b中z的取值进行分类，最简单的分类标准为：

y={0,z<00.5,z=01,z>0y= \begin{cases} 0,z<0\\ 0.5,z=0\\ 1,z>0 \end{cases}

利用Sigmoid函数进行转化：

y=11+e−z=11+e−(wTx+b)ln⁡y1−y=wTx+by=\frac{1}{1+e^{-z}}=\frac{1}{1+e^{-(w^Tx+b)}} \\ \ln \frac{y}{1-y} = w^Tx+b

其中y为将样本x视为正例的可能性，1-y为其反例的可能性，故y1−y\frac{y}{1-y}可视为几率，反映了x作为正例的相对可能性。利用线性回归的模型的预测结果去毕竟真实标记的对数几率。

更严谨的数学表述为：

ln⁡P(y=1∣x)P(y=0∣x)=wTx+bP(y=1∣x)=ewTx+b1+ewTx+bP(y=0∣x)=11+ewTx+b\ln \frac{P(y=1|x)}{P(y=0|x)}=w^Tx+b \\ P(y=1|x) = \frac{e^{w^Tx+b}}{1+e^{w^Tx+b}} \\ P(y=0|x) = \frac{1}{1+e^{w^Tx+b}}

线性判别法LDA

LDA的想法是很朴素的：对于给定训练集，将样例投射到一条直线上，让同类样例投影的距离尽可能接近。在对新样本进行分类时，同样将其投影到直线上，根据距离进行分类。

LDA

多分类学习

往往是基于一些基本策略，利用二分类学习器来解决多分类问题。

假设有N个类别C1,C2,...,CnC_1,C_2,...,C_n，将问题拆分为若干个二分类问题进行求解，然后为每个问题训练一个分类器。

最经典的拆分方法有三种：

  • 一对一OvO
  • 一对其余OvR
  • 多对多MvM

OvO

对于给定数据集D={(x1,y1),(x2,y2),...,(xm,ym)},yi∈{C1,C2,...,CN}D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\},y_i \in\{C_1,C_2,...,C_N\}，OvO策略将N个类别两两配对，训练N(N−1)2\frac{N(N-1)}{2}个分类任务。

在测试时，新样本将同时提交给所有的分类器，根据这N(N−1)2\frac{N(N-1)}{2}分类投票结果进行确定。

OvR

每次将一个类的样例作为正例，其余作为反例，总共有N个分类任务。

根据分类结果投票进行确定。

image-20240506133813533

MvM

每次将若干个类作为正类，其余作为反类。OvO和OvR都是MvM的特例。

MvM的正反类构造必须有特殊的设计，不能随意选取。最常用的为纠错输出码ECOC：

  • 编码：对N个类别做M次划分，每次划分将一部分类别划为正类，一部分划为反类，从而形成一个二分类训练集。这样一共产生M个训练集，可训练出M个分类器.
  • 解码：M个分类器分别对测试样本进行预测，这些预测标记组成一个编码。将这个预测编码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果.

编码示意

称为“纠错输出码”：对分类器的错误有一定的容忍和修正能力。一般来说，对同一个学习任务，ECOC 编码越长，纠错能力越强。然而，编码越长，意味着所需训练的分类器越多，计算、存储开销都会增大。另一方面，对有限类别数，可能的组合数目是有限的，码长超过一定范围后就失去了意义。

类别不平衡问题

训练集中不同类别的训练数据数目差别很大。

决策树

决策树：不断进行二分类任务，形成树状的决策过程，每一层的决策范围都是在上次决策结果的限定范围之内。

一颗决策树一般包括：

  • 一个根节点：对应一个属性测试
  • 若干个内部节点：对应一个属性测试
  • 若干个叶节点：对应决策结果

每个节点把包含的样本集合根据属性测试的结果被划分到子节点中，根节点包含全部样本集合。

决策树的目的是产生处理未见示例能力强的决策树。

决策树的生成

决策树的生成是一个递归过程，在每一层选择最优的划分准则，直至划分完毕。

在决策树基本算法中，有三种情形会导致递归返回：

  1. 当前结点包含的样本全属于同一类别，无需划分

  2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分

    将当前节点标记为叶节点，并将节点的类别设置为该节点所包含样本最多的类别

  3. 当前结点包含的样本集合为空，不能划分

    将当前节点标记为叶节点，将其类别设置为其父节点包含样本最多的类别

决策树学习基本算法

划分选择

决策树的关键在于，如何选择最优划分属性。随着划分的不断进行，希望决策树的分支节点所包含的样本尽可能属于同一类别，即纯度越来越高。

信息增熵

信息熵是度量样本集合纯度的最常用指标。

假设当前样本集合D中的第k类样本所占比例为pk,k=1,2...,np_k,k=1,2...,n，n为标签的取值情况数量。则定义信息熵为Ent(D)=−∑k=1npklog⁡2pkEnt(D)=-\sum^{n}_{k=1}p_k \log_2p_k。信息熵的值越小，D的纯度越高。

假定离散属性a有V个可能的取值{a1,a2,...,aV}\{a^1,a^2,...,a^V\}。若采用a来对样本集D进行划分，则会产生V个分支节点，其中第i个分支节点包含了D中所有在属性a熵取值为aia^i的样本，即为DiD^i。

考虑不同分支节点包含的样本数的不同，给分支节点赋予权重∣Di∣∣D∣\frac{|D^i|}{|D|}，可以得到整体样本集D的信息增益为Gain(D,a)=Ent(D)−∑v=1V∣Di∣∣D∣Ent(Dv)Gain(D,a)=Ent(D)-\sum^{V}_{v=1} \frac{|D^i|}{|D|}Ent(D^v)。

  • 其中Ent(D)Ent(D)代表样本整体的信息熵。以最一般的二分决策为例，结果仅有正例和反例，则Ent(D)=−∑k=12正例/反例Ent(D)=-\sum^{2}_{k=1}正例/反例​
  • ∑v=1V∣Di∣∣D∣Ent(Dv)\sum^{V}_{v=1} \frac{|D^i|}{|D|}Ent(D^v)为按照属性的值进行计算，V为a总共有V种可能的取值

一般而言：信息增益越大，意味着使用属性a用来进行划分获得的纯度提升越大。利用信息增益作为划分决策树的属性选择。

增益率

信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，引入增益率作为划分属性。

增益率定义为Gain_ratio(D,a)=Gain(D,a)IV(a)Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}，其中固有值IV(a)IV(a)定义为IV(a)=−∑v=1V∣DV∣∣D∣log⁡2∣DV∣∣D∣IV(a)=-\sum^{V}_{v=1} \frac{|D^V|}{|D|} \log_2 \frac{|D^V|}{|D|}。属性a可能取值数目V越大，则固有值越大。

增益率弥补了部分对取值数目较多的属性的偏好，但也可能会偏好取值小的。常用的做法是先选出信息增益高于平均水平的属性，再从中选取增益率最高的。

基尼指数

数据集D的基尼值定义为Gini(D)=∑k=1n∑k′≠kpkpk′=1−∑k=1npk2Gini(D)=\sum^{n}_{k=1} \sum_{k'\neq k} p_k p_k' = 1-\sum^{n}_{k=1} p_k^2。基尼值反映了从数据集D中随机选择两个样本，其类别标记不一致的概率。基尼值越小，则数据集D的纯度越高。

基尼指数定义为Gini_index(D,a)=∑v=1V∣Dv∣∣D∣Gini(Dv)Gini\_index(D,a) = \sum^{V}_{v=1} \frac{|D^v|}{|D|} Gini(D^v)

选取划分后使基尼指数最小的属性作为最优属性。

剪枝处理

剪枝是为了处理过拟合的主要应对手段：如果决策树分支过多，以至于把训练集自身的一些特点当作了所有数据都具有的一般性质。可以通过主动减少一些分支来降低过拟合的风险。

剪枝的策略有预剪枝和后剪枝两种。

  • 预剪枝：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点
  • 后剪枝：先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点

判断泛化性能提升的方式：在将训练集部分划分为验证集后，验证模型的性能。详情可见第二章。

预剪枝

预剪枝是在每一个节点进行考虑：在当前节点按照信息增益准则选取划分属性后，验证集精度时候上升；如果结论为后，则不进行划分，此节点不会继续递归地向下进行划分。

如果决策树只有一层划分，称之为决策树桩。

于预页剪枝使得决策树的很多分支都没有展开，降低了过拟合分享和时间开销。

但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降。但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于"贪心"的本质禁止了这些分支展开，给预剪枝决策树带来了欠拟合的风险。

后剪枝

后剪枝是对未剪枝完全决策树自底向上的重新合并。对于非叶节点，如果不在此进行划分，比较验证集精度是否上升，如果上升则说明剪枝是没必要的，将节点转换为叶节点。

一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。

但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

连续与缺失值

样本中的数据不是理想离散数据的情况。

连续属性决策树

决策树的属性可能不是离散而是连续的，如何根据连续值构建决策树：采用对连续值进行离散化。

最简单的策略是用二分法对连续属性进行处理。

给定样本集D和连续属性a，假设a在D上出现了n个不同的取值（D中的样本数是有限的），将这n个值从小到大排列为{a1,a2,...,an}\{a^1,a^2,...,a^n\}。

基于划分点t可以将D分为子集Dt−D^{-}_{t}和Dt+D^{+}_{t}。其中Dt−D^{-}_{t}中包含在属性a上取值不大于t的样本，Dt+D^{+}_{t}中包含在属性a上取值大于t的样本。

对于相邻的属性取值aia^i和ai+1a^{i+1}，t在区间[ai,ai+1)[a^i,a^{i+1})产生的划分结果相同。因而对于连续属性a，考察包含n-1个元素的候选划分点集合Ta={ai+ai+12∣1<=i<=n−1}T_a=\{ \frac {a^i+a^{i+1}} {2} | 1<=i<=n-1 \}，把取值的中位点作为候选划分点，后续可以向考察离散划分点一样考察这些候选划分点。

缺失值处理

对于不完整样本中的缺失值，如何更好构建决策树。

如果放弃部分缺失的样本，那么可能无样本可用，必须考虑利用有缺失属性值的训练样例来进行训练。

两个基本问题：

  1. 如何在属性值缺失的情况下进行属性选择
  2. 给定划分属性，若样本在该属性上的值缺失，如何对该样本进行划分

对于给定训练集D和属性a，用D~\widetilde{D}表示D在属性a上无缺失（在别的属性上依然可以缺失）的样本子集。

假设a有V个可能取值{a1,a2,...,aV}\{a^1,a^2,...,a^V\}，令D~v\widetilde{D}^v表示D~\widetilde{D}在属性a上取值为ava^v的样本子集。

D~k\widetilde{D}_k表示D~\widetilde{D}中属于第k类（k=1,2…n，n为标签可能取值的数量）的样本子集。

有：

D~=∪k=1nD~kD~=∪v=1VD~vρ=∑x∈D~wx∑x∈Dwxp~k=∑x∈D~kwx∑x∈D~wx,1<=k<=nr~v=∑x∈D~vwx∑x∈Dwx,1<=v<=V\widetilde{D} = \cup_{k=1}^n \widetilde{D}_k \\ \widetilde{D} = \cup_{v=1}^V \widetilde{D}^v \\ \rho = \frac{\sum_{x\in \widetilde{D}} w_x} {\sum_{x\in D} w_x} \\ \widetilde{p}_k = \frac{\sum_{x\in \widetilde{D}_k} w_x} {\sum_{x\in \widetilde{D}} w_x} , 1<=k<=n \\ \widetilde{r}_v = \frac{\sum_{x\in \widetilde{D}^v} w_x} {\sum_{x\in D} w_x} , 1<=v<=V \\

直观的，对于属性a：

  • ρ\rho表示无缺失值样本所占的比例
  • p~k\widetilde{p}_k表示无缺失值样本中第k类所占的比例
  • r~v\widetilde{r}^v表示无缺失值样本中在属性a上取值为ava^v的样本所占的比例

推广信息增益的计算公式为：

Gain(D,a)=ρ∗Gain(D~,a)=ρ∗(Ent(D~)−∑v=1Vr~vEnt(D~v))Ent(D~)=−∑k=1np~klog⁡2p~kGain(D,a) = \rho * Gain(\widetilde{D},a) \\ =\rho * (Ent(\widetilde{D})-\sum^{V}_{v=1} \widetilde{r}^v Ent(\widetilde{D}^v)) \\ Ent(\widetilde{D}) = -\sum_{k=1}^n \widetilde{p}_k \log_2 \widetilde{p}_k

对问题2：

  • 若样本x在划分属性a上的取值己知，则将x划入与其取值对应的子结点，且样本权值在于结点中保持为wxw_x
  • 若样本x在划分属性a上的取值未知，则将x同时划入所有子结点。且样本权值在与属性值ava^v对应的子结点中调整为r~v\widetilde{r}^v。直观地看，这就是让同一个样本以不同的概率划入到不同的子结点中去

多变量决策树

若我们把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。

决策树所形成的分类边界有一个明显的特点：轴平行(axis-parallel) ，即它的分类边界由若干个与坐标轴平行的分段组成。让模型具有了较好的解释性。

神经网络

TODO

贝叶斯分类器

贝叶斯决策论

贝叶斯决策论(Bayesian decision theory)是概率框架下实施决策的基本方法。对分类任务来说，在所有相关概率都己知的理想情形下，贝叶斯决策论考虑：如何基于这些概率和误判损失来选择最优的类别标记。

基本原理

朴素贝叶斯通过训练数据集学习联合概率分布P(X,Y)P(X,Y)，再对于给定的输入计算后验概率分布，其后验概率最大的类作为输出：

  • 假设输出空间，即标记组成的集合Y={c1,c2,...cK}Y=\{c_1,c_2,...c_K\}

  • 学习先验概率分布P(Y=ck),k=1,2,...KP(Y=c_k),k=1,2,...K​

  • 学习条件概率分布P(X=x∣Y=ck)=P(X(1)=x(1),X(2)=x(2),...X(n)=x(n)∣Y=ck)P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)}, X^{(2)}=x^{(2)},...X^{(n)}=x^{(n)} | Y=c_k)

    • 为了降低为了降低复杂度，做了条件独立性的假设，认为输入的每一个维度之间是独立的
    • P(X=x∣Y=ck)=∏P(X(j)=x(j)∣Y=ck)P(X=x|Y=c_k)=\prod P(X^{(j)} = x^{(j)}|Y=c_k)

  • 训练后，在分类钟，对于输入向量x，可以得到输出y的概率

    • P(Y=ck∣X=x)=P(Y=ck,X=x)P(X=x)=P(X=x∣Y=cK)∗P(Y=ck)P(X=x)=P(Y=ck)∗∏P(X(j)=x(j)∣Y=ck)∑P(X∣Y=ci)∗P(Y=ci)P(Y=c_k | X=x) = \frac{P(Y=c_k,X=x)} {P(X=x)} \\ =\frac{P(X=x|Y=c_K) * P(Y=c_k)} {P(X=x)} \\ = \frac{P(Y=c_k) * \prod P(X^{(j)}=x^{(j)} |Y=c_k)} {\sum P(X|Y=c_i) * P(Y=c_i)}

    • 其中P(Y=ci),P(X∣Y=ci),P(X(j)=x(j)∣Y=ck)P(Y=c_i),P(X|Y=c_i),P(X^{(j)}=x^{(j)} |Y=c_k)均为测试数据集中的先验概率

  • 输出对应概率最大的y

最优实现

从风险的角度：定义λij\lambda _{ij}是将真实标记为cjc_j的样本分类为cic_i的损失，则定义条件风险为R(ci∣x)=∑j=1NλijP(cj∣x)R(c_i|x)=\sum^N_{j=1} \lambda_{ij}P(c_j|x)，即在输入x的情况下将真实标记为cic_i的样本分类为cjc_j的风险的和。

寻找一种判定准则实现从输入空间到输出空间的映射h，以最小化总体风险：R(h)=Ex[R(h(x)∣x)]R(h)=E_x [R(h(x)|x)]。整体的最小化与每个x的最小化一致。

贝叶斯判定准则：为最小化总体风险，只需在每个样本上选择那个能使条件风险R(c∣x)R(c|x)最小的类别标记。

对应的贝叶斯最优分类器即为h∗(x)=arg⁡min⁡R(c∣x)h^{*}(x)=\arg \min R(c|x)。称R(h∗)R(h^*)为贝叶斯风险，1−R(h∗)1-R(h^*)为分类器所能达到的最好性能，即模型精度理论上限。

对于最小化分类错误率，定义损失函数在分类正确时为0，其余均为1，则条件风险R(c∣x)=1−P(c∣x)R(c|x)=1-P(c|x)，此时的贝叶斯最优分类器为h∗(x)=arg⁡max⁡P(c∣x)h^*(x)=\arg\max P(c|x)

极大似然估计

学习就意味着需要估计P(Y=ci),P(X(j)=x(j)∣Y=ck)P(Y=c_i),P(X^{(j)}=x^{(j)} |Y=c_k)，估计意味着参数，如何正确的估计参数？

事实上，模型训练的过程就是参数估计的过程。

极大似然估计认为，参数是未被观测到的随机变量，本身也具有一定的分布，可以假设一个先验分布，使用观测到的数据来计算参数的后验分布。

朴素贝叶斯分类器

朴素在于：假设所有属性相互独立，每个属性独立地对分类结果发生影响。

对于离散变量视频率为概率。

对于连续变量，考虑概率密度函数，假定p(xi∣c)∼N(μci,σci2)p(x_i|c)\sim N(\mu_{ci},\sigma^2_{ci})，为第c类样本在第i个属性上取值的均值和方差。

需注意，若某个属性值在训练集中没有与某个类同时出现过，对应概率为0，会直接使条件概率公式为0，抹去了其他属性携带的信息。需要对公式进行拉普拉斯修正：

P(c)=∣Dc∣+1∣D∣+NP(xi∣c)=∣Dc,xi∣+1Dc+NiP(c)=\frac{|D_c|+1}{|D|+N} \\ P(x_i|c) = \frac{|D_{c,x_i}|+1}{D_c+N_i}

其中D为训练集，DcD_c为第c类样本组成的集合，N为D考虑的类别数，NiN_i为x的第i个属性可能的取值数。

拉普拉斯修正避免了因训练集样本不充分而导致概率估值为零的问题，并且在训练集变大时，修正过程所引入的先验(prior)的影响也会逐渐变得可忽略，使得估值渐趋向于实际概率值.

半朴素贝叶斯分类器

显然，朴素贝叶斯分类器要求的各属性独立是难以做到的。对各属性的独立性进行一定的放松，即半朴素。

半朴素贝叶斯分类器的基本想法是适当考虑一部分属性问的相互依赖信息，从而既不需进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系。

“独依赖估计” (One-Dependent Estimator，简称ODE)是半朴素贝叶斯分类器最常用的一种策略。顾名思议，所谓"独依赖"就是假设每个属性在类别之外最多仅依赖于一个其他属性，即P(c∣x)∝P(c)∏i=1dP(xi∣c,pai)P(c|x) \propto P(c) \prod_{i=1}^d P(x_i | c,pa_i)。

其中paipa_i为属性xix_i依赖的属性，称为父属性。问题的关键就在于问题的关键，转化为了如何确定每个属性的唯一父属性，不同的做法产生了不变通的独依赖分类器。

示意

  • SPODE即super parent ODE，假设所有的属性值都依赖于同一个属性，即超父

  • TAN是在最大带权生成树算法的基础上构建的，选取强相关属性之间的依赖性选择父属性

    1. 计算两个属性之间的条件互信息I(xi,xj∣y)=∑xi,xj;c∈YP(xi,xj∣c)log⁡p(xi,xj∣c)P(xi∣c)∗P(xj∣c)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(xi,xj∣y)I(x_i,x_j|y)

    3. 构建此完全图的最大带权生成树，挑选根变量，将边置为有向

      在此生成了属性的父属性依赖关系图

    4. 加入类别节点y，增加从y到每个属性的有向边

  • AODE是一种基于集成学习机制的ODE，尝试使用每个属性作为超父来构建SPODE，让后让有足够训练数据支撑的SPODE集成起来作为结果

    P(c∣x)∝∑i=1,∣Dxi∣>=m′dP(c,xi)∏i=1dP(xi∣c,pai)P(c,xi)=∣Dc,xi∣+1∣D∣+N∗NiP(xj∣c,xi)=∣Dc,xi,xj∣+1∣Dc,xi∣+NjP(c|x) \propto \sum^d_{i=1,|D_{x_i}|>=m'} P(c,x_i) \prod_{i=1}^d P(x_i | c,pa_i) \\ P(c,x_i)=\frac{|D_{c,x_i}|+1}{|D|+N*N_i} \\ P(x_j|c,x_i) = \frac{|D_{c,x_i,x_j}|+1}{|D_{c,x_i}|+N_j}

    其中DxiD_{x_i}为在第i个属性上取值为xix_i的样本的集合，m′m'为 阈值常数

贝叶斯网

贝叶斯网(Bayesian network)亦称"信念网" (belief network) ，它借助有向无环图(Directed Acyclic Graph，简称DAG)来刻画属性之间的依赖关系，并使用条件概率表(Conditional Probability Table，简称CPT)来描述属性的联合概率分布。

一个贝叶斯网由结构G和参数Θ\Theta两部分组成，即B=<G,Θ>B=<G,\Theta>

  • 网结构G是一个有向无环图，每个节点对应于一个属性。
    • 若两个属性有直接依赖关系，则由一条边连起来
  • 参数Θ\Theta描述了属性之间具体的依赖关系
    • 若属性xix_i在G中的父节点集为πi\pi_i，则Θ\Theta包含了属性对应父属性的条件概率表θxi∣πi=PB(xi∣πi)\theta_{x_i|\pi_i}=P_B(x_i|\pi_i)

结构

贝叶斯网有效地描述了属性之间的独立性，对于贝叶斯图B=<G,Θ>B=<G,\Theta>，联合概率分布为：PB(x1,x2,...,xd)=∏i=1dPB(xi∣πi)=∏i=1dθxi∣πiP_B(x_1,x_2,...,x_d)=\prod^d_{i=1} P_B(x_i|\pi_i)=\prod^d_{i=1}\theta_{x_i|\pi_i}

三个变量之间的典型的依赖关系为：

三个变量之间典型的依赖关系

学习

贝叶斯网学习的首要任务就是根据训练数据集来找出结构最"恰当"的贝叶斯网，确定贝叶斯图的结构。

"评分搜索"是求解这一问题的常用办法：

  1. 先定义一个评分函数(score function) ，以此来评估贝叶斯网与训练数据的契合程度
  2. 基于这个评分函数来寻找结构最优的贝叶斯网

显然，评分函数引入了希望获得什么样的贝叶斯网的归纳偏好

推论

贝叶斯网训练好之后就能用来回答"查询" ，即通过一些属性变量的观测值来推测其他属性变量的取值。

  • 推断：通过已知变量来推测待查询变量的过程
  • 证据：已知变量的观测值称

最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，不幸的是，这样的"精确推断"己被证明是NP难的。当网络结点较多、连接稠密时，难以进行精确推断，此时需借助"近似推断"，通过降低精度要求，在有限时间内求得近似解。

在现实应用中，贝叶斯网的近似推断常使用吉布斯采样，这是一种随机采样方法。

  1. 令Q={Q1,Q2,...,Qn}Q=\{Q_1,Q_2,...,Q_n\}表示待查询变量；E={E1,E2,...,En}E=\{E_1,E_2,...,E_n\}为证据变量，其取值为e={e1,e2,...,en}e=\{e_1,e_2,...,e_n\}。目标为计算P=P(Q=q∣E=e)P=P(Q=q|E=e)。

  2. 先随机产生一个与证据变量E=eE=e一致的样本q0q^0作为起始点，然后从当前样本出发产生下一个样本

  3. 这是一个马尔可夫过程，在贝叶斯网的所有变量的联合状态空间与证据E=eE=e一致的子空间进行随机漫步

    1. 在第t次采样中，先让qt=qt−1q^t=q^{t-1}，再对非证据变量逐个进行采样改变其取值
    2. 最终得到收敛的概率结果
    吉布斯采样算法

EM算法

对于不完整的训练样本，需要怎么做？

未观测的变量称为隐变量。

集成学习

TODO