Machine Learning Introduction: Supervised Learning, Model Evaluation, and Bayesian Methods

机器学习概述

机器学习是什么

在传统的研究中我们主要采用模式识别的方法（正则表达式就属于一种模式识别）作为机器类人处理问题的方法；事实上模式识别方法存在各种各样的问题，依靠人主观的提取特征再交由机器判断确实正确性并不理想并且对比较复杂的问题束手无策；

因此我们自发的想到了让机器自己改善自己的效果，机器学习正是这样一门学科，它致力于研究如何通过计算的手段，利用经验来改善系统自身的性能；

在这个领域发展阶段，以规则学习为代表的符号主义学习是最早开始研究的机器学习技术，但是由于性能问题，目前规则学习技术已经基本被统计学习技术取代，或者作为融合形式发展

基本术语

因此，机器学习所研究的主要内容，是关于在计算机上从数据中产生“模型”（model）的算法，即“学习算法”（Learning algorithm）.

有了学习算法，我们把经验数据提供给它，它就能基于这些数据产生模型；在面对新的情况时，模型会给我们提供相应的判断，如果说计算机科学是研究关于“算法”的学问，那么类似的，可以说机器学习是研究关于“学习算法”的学问.

从数据中学得模型的过程称为 “学习” （learning）或“训练”（training），这个过程通过执行某个学习算法来完成.训练过程中使用的数据称为“训练数据” （training data），其中每个样本称为一个“训练样本” （training sample），训练样本组成的集合称为“训练集”（training set）.

学得模型后，使用其进行预测的过程称为“测试”（testing）

根据训练数据是否拥有标记信息，学习任务可大致划分为两大类：“监督学习”（supervised learning）和“无监督学习”（unsupervised learning），分类和回归是前者的代表，而聚类和降维则是后者的代表

需注意的是，机器学习的目标是使学得的模型能很好地适用于“新样本”，而不是仅仅在训练样本上工作得很好；也就是“泛化”（generalization）能力

发展历程

推理阶段：也就是模式识别阶段人工的归纳特点机器进行逻辑推理

归纳学习阶段：让机器进行自我学习的最主要方法，我们希望机器拥有自己的学习能力，从样本中归纳共性，再进行推理

目前整个机器学习领域都属于归纳学习阶段，后面都是它自身的发展

符号学习阶段决策树是其重要代表

连接主义阶段以神经网络算法（BP）为核心连接主义和符号学习最大的不同就在于是否为黑箱它缺少理论支持

统计学习阶段支持向量机算法是重要的代表

深度学习阶段随着算力爆发增长连接主义再次登场多层神经网络学习（深度学习）技术成为了机器学习领域新宠延续了连接主义的低可解释性要求大量训练数据与极高算力我们在机器学习中不过多介绍深度学习内容

后记

在目前的机器学习过程中我们有两个比较重要的研究阶段转变：

从符号主义到统计学习阶段
从统计学习到纯粹的工业界领导的深度学习LLM阶段

其中在理论上有重大突破的只有第一次转变；机器学习领域引入了统计学方法；

继续吸收数学中的各种思想会是机器学习领域下一次理论突破的核心

机器学习问题的分类

机器学习本质上是让机器自发的去寻找我们的决策函数的问题，根据决策函数的不同，我们可以对机器学习问题进行分类。

假设要找的函数的输出是一个数值，一个标量，这种机器学习的任务称为回归。

除了回归以外，另一个常见的任务是分类。分类任务要让机器做选择题。人类先准备好一些选项，这些选项称为类别（class），现在要找的函数的输出就是从设定好的选项里面选择一个当作输出，该任务称为分类。

在机器学习领域里面，除了回归跟分类以外，还有结构化学习（structured learning）。机器不只是要做选择题或输出一个数字，而是产生一个有结构的物体，比如让机器画一张图，写一篇文章。这种叫机器产生有结构的东西的问题称为结构化学习。

当然，无监督的聚类和降维也是重要的机器学习技巧，经常和监督学习配合使用

模型评估与选择

现在我们已经了解了基本术语知道了机器学习在研究什么非常自然的我们希望知道如何评估现有的模型无论是对原始数据上的拟合能力还是泛化能力它将是后面整个学习阶段的基础

决策树

基本定义

决策树(decision tree )是一类常见的机器学习方法（属于监督学习范畴），顾名思义，决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制我们通过一系列判断最后给出我们的决策结果

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点;叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集.从根结点到每个叶结点的路径对应了一个判定测试序列；

决策树学习的目的是为了产生一棵泛化能力强的决策树；

决策树的生成是一个递归过程；我们对目前所拥有的样本进行判断如果它为空或者全部属于一个类别那么它应该就是叶节点了；如果不是我们需要再选出最优划分属性然后划分后继续生成新的节点

划分选择

非常自然的整个决策树学习过程中最核心的最优划分属性的选择我们希望随着划分的不断进行决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高.

信息增益

“信息熵 “(information entropy)是度量样本集合纯度最常用的一种指标

假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k$ 那么可以定义他的信息熵为

\operatorname{Ent}(D)=-\sum\limits_{k=1}^{|\mathcal{Y}|}p_k\log_2p_k.

信息熵越小对应的纯度越高

假定我们有一个用于划分的属性 $a$ 他对应了 $V$ 个可能的取值那么使用它进行划分就可以得到 $V$ 个分支节点；我们就可以计算出每个分支节点的信息熵然后根据分支节点的样本数不同赋予权重（样本越多权重越大）然后就可以计算这个属性划分对样本划分得到的信息增益

\mathrm{Gain}(D,a)=\mathrm{Ent}(D)-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}\mathrm{Ent}(D^{v}).

越大的信息增益就意味着越好的纯度提升效果我们可以使用信息增益为准则选择划分属性

增益率

信息增益准则不是没有缺点的如果我们把每个样本都单独划分一类那么信息增益就是最大的；事实上信息增益准则对可能取值较多的属性有偏好为了减少这个偏好带来的不利影响我们引入了增益率

\operatorname{Gain}\text{ratio}(D,a)=\frac{\operatorname{Gain}(D,a)}{\operatorname{IV}(a)}

其中

\mathrm{IV}(a)=-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}\log_{2}\frac{|D^{v}|}{|D|}\quad.

增益率可以压制信息增益带来的偏好遗憾的是增益率对较少的分类数量有偏好我们最好权重前面的两种的方法

基尼指数

我们引入另一种衡量数据纯度的方法定义基尼指为

\begin{aligned} \operatorname{Gini}(D)& =\sum_{k=1}^{|J|}\sum_{k^{\prime}\neq k}p_{k}p_{k^{\prime}} \\ &=1-\sum_{k=1}^{|\mathcal{Y}|}p_{k}^{2}. \end{aligned}

因此属性a划分带来的纯度提升可以用基尼指数来衡量

\mathrm{Gini}\_\mathrm{index}(D,a)=\sum_{v=1}^{V}\frac{|D^{v}|}{|D|.}\mathrm{Gini}(D^{v}).

具体的方法不变

剪枝

剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段.在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得“太好” 了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合.因此，可通过主动去掉一些分支来降低过拟合的风险

决策树剪枝的基本策略有“预剪枝”(prepruning)和 “后剪枝 “ (post- pruning)

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；

后剪枝则是先从训练集生成一棵完整的决策树, 然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点.

至于如何判断泛化性能提升了可以考虑前面介绍的性能评估本文的性能度量部分

连续与缺失值

连续值处理

由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的取值来对结点进行划分.止匕时，连续属性离散化技术可派上用场；

我们只需要把连续属性设定一定的步长在范围内设定一些小区间作为连续属性的分类方法就可以了

与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性.

在大部分的决策树算法中，连续属性在每一次决策中只会自动生成两个分支，根据某种指标自动选择最优划分点，而不是使用我们介绍的划分step的方法

缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失；有时候我们可以舍弃有缺失的样本但是有的时候这样会导致剩余样本过少我们必须考虑使用有缺失的样本进行训练

我们需解决两个问题：

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

对于第一个问题我们在训练模型的时候只使用那些在这个属性上没有缺失的样本子集来训练此时我们需要对信息熵计算中的比例问题进行修正保证计算用的比例和为1

对于第二个问题我们将x 同时划入所有子结点但是要根据子节点的权重调整它的权重也就是让它以不同的概率进入每一个子节点

多变量决策树

在学习任务的真实分类边界比较复杂时，前面介绍的决策树算法必须使用很多段划分才能获得较好的近似；此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大

多变量决策树的思想是，非叶结点不再是仅对某个属性,而是对属性的线性组合进行测试; 也就是说每一个非叶的节点都是一个线性分类器（这种分类器的设计我们在分类算法中会学到）每一次非叶节点的确定都是一次建立合适的线性分类器；这种方法可以有效的降低决策树的复杂程度

多变量决策树的思想其实是一个很大的改进思路在决策树上嵌入各种不同的算法结合他们的优势实现分类

支持向量机SVM

间隔与支持向量

支持向量机又是一种监督学习方法它的目标是处理分类问题；他的思想非常简单基于训练数据集 $D$ 在样本空间中找到一个超平面把不同类别的样本分开；那么就此产生的问题有两个；如何寻找超平面把样本分开如何在寻找到的多个超平面中找到最为合适的那一个让他有着最好的泛化性能；

在样本空间中划分超平面可以用下面线性方程描述

w^\mathrm{T}x+b=0

整个划分超平面被法向量 $w$ 和位移 $b$ 决定

因此样本空间中任何点到超平面的距离可以写为

r=\frac{|\boldsymbol{w^\mathrm{T}}\boldsymbol{x}+b|}{||\boldsymbol{w}||}.

如果超平面可以把训练样本正确分类假设我们分别让分类用的 $y_i$ 取为正负1 则有

\left.\left\{\begin{array}{ll}w^\mathrm{T}x_i+b\geqslant+1,&y_i=+1;\\w^\mathrm{T}x_i+b\leqslant-1,&y_i=-1.\end{array}\right.\right.

我们知道距离超平面最近的这几个训练样本一定可以让前式中的等号成立他们被称为支持向量(support vector) 两个异类支持向量到超平面的距离为

\gamma=\frac{2}{||\boldsymbol{w}||}

我们称为间隔(margin)

想要找到最大间隔的划分超平面是最优化问题的范畴只需要进行下面的最优化

\begin{aligned}\min_{\boldsymbol{w},b}&\frac{1}{2}\|\boldsymbol{w}\|^2\\\mathrm{s.t.}&y_i(\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_i+b)\geqslant1,i=1,2,\ldots,\boldsymbol{m}.\end{aligned}

这就是支持向量机(Support Vector Machine,简称SVM ) 的基本型.

约束条件的意思是，类别 $y_i$ 和平面计算值的积大于1 也就是所有样本都被正确的分类

核函数与核方法

在前面的讨论中，我们假设训练样本是线性可分的，即存在一个划分超平面能将训练样本正确分类.然而在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面也就是原始样本空间线性不可分

如果线性可分，就意味着可以使用简单的线性分类方法来分类，如logit回归和svm

如果线性不可分，要么使用复杂的非线性分类方法，要么使用kernel方法映射到高维空间上

对这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分；幸运的是，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分.

映射到高维空间后我们的最优化问题变化为

\begin{aligned}\min_{\boldsymbol{w},b}&\frac{1}{2}\|\boldsymbol{w}\|^2\\\text{s.t.}&y_i(\boldsymbol{w}^\mathrm{T}\phi(\boldsymbol{x}_i)+b)\geqslant1,\quad i=1,2,\ldots,m.\end{aligned}

其中 $\phi(x)$ 是映射后的特征向量

此时的求解涉及计算 $\phi(\boldsymbol{x}_{i})^{\mathrm{T}}\phi(\boldsymbol{x}_{j})$ 由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算通常是困难的.为了避开这个障碍，可以设想

\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\langle\phi(\boldsymbol{x}_i),\phi(\boldsymbol{x}_j)\rangle=\phi(\boldsymbol{x}_i)^\mathrm{T}\phi(\boldsymbol{x}_j)

也就是特征空间的内积等于它们在原始样本空间中通过函数 $\kappa$ 计算的结果这样我们就可以规避前面的内积计算原始的最优化问题转变为

\begin{aligned}\max_{\boldsymbol{\alpha}}&\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)\\\text{s.t.}&\sum_{i=1}^m\alpha_iy_i=0,\\&\alpha_i\geqslant0,\quad i=1,2,\ldots,m.\end{aligned}

如果我们知道非线性映射的形式就可以给出核函数的形式遗憾的是我们不可能知道非线性映射的形式因此我们需要自行选择核函数这也是SVM算法中最大的变数 若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳

我们给出定理：只要一个对称函数所对应的核矩阵半正定,.它就能作为核函数使用其中核矩阵定义为

\mathbf{K}=\begin{bmatrix}\kappa(\boldsymbol{x}_1,\boldsymbol{x}_1)&\cdots&\kappa(\boldsymbol{x}_1,\boldsymbol{x}_j)&\cdots&\kappa(\boldsymbol{x}_1,\boldsymbol{x}_m)\\\vdots&\ddots&\vdots&\ddots&\vdots\\\kappa(\boldsymbol{x}_i,\boldsymbol{x}_1)&\cdots&\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)&\cdots&\kappa(\boldsymbol{x}_i,\boldsymbol{x}_m)\\\vdots&\ddots&\vdots&\ddots&\vdots\\\kappa(\boldsymbol{x}_m,\boldsymbol{x}_1)&\cdots&\kappa(\boldsymbol{x}_m,\boldsymbol{x}_j)&\cdots&\kappa(\boldsymbol{x}_m,\boldsymbol{x}_m)\end{bmatrix}.

几种常用的核函数

名称	表达式
线性核	$\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\boldsymbol{x}_i^\mathrm{T}\boldsymbol{x}_j$
多项式核	$\kappa(\boldsymbol{x_{i}},\boldsymbol{x_{j}})=(\boldsymbol{x_{i}^{\mathrm{T}}x_{j}})^{d}$
高斯核	$\kappa(\boldsymbol{x}_{i},\boldsymbol{x}_{j})=\exp\big(-\frac{\\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\\|^{2}}{2\sigma^{2}}\big)$
拉普拉斯核	$\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\exp\left(-\frac{\\|\boldsymbol{x}_i-\boldsymbol{x}_j\\|}{\sigma}\right)$
Sigmoid 核	$\kappa(\boldsymbol{x}_{i},\boldsymbol{x}_{j})=\tanh(\beta\boldsymbol{x}_{i}^{\mathrm{T}}\boldsymbol{x}_{j}+\theta)$

原始核函数的一些组合方式也是核函数如

\gamma_{1}\kappa_{1}+\gamma_{2}\kappa_{2}

\kappa_1\otimes\kappa_2(x,z)=\kappa_1(x,z)\kappa_2(x,z)

\kappa(x,z)=g(x)\kappa_1(x,z)g(z)

软间隔与正则化

在前面的讨论中，我们一直假定训练样本在样本空间或特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全划分开；

在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分；退一步说, 即便恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的.

缓解该问题的一个办法是允许支持向量机在一些样本上出也就是引入软间隔(soft margin)

前面介绍的支持向量机要求所有样本均能满足我们的约束这称为 “硬间隔”(hard margin ) 软间隔就是允许某些样本不满足约束

y_{i}(\boldsymbol{w^{\mathrm{T}}x_{i}}+b)\geqslant1.

当然我们也有尽量减少不满足约束的样本也就是引入损失为把最优化问题变为

\min_{\boldsymbol{w},b}\frac{1}{2}\|\boldsymbol{w}\|^{2}+C\sum_{i=1}^{m}\ell_{0/1}\left(y_{i}\left(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_{i}+b\right)-1\right)

其中损失函数的选取比较自由我们在这里只进行简单的介绍最基础的01损失为

\ell_{0/1}(z)=\begin{cases}1,&\text{if}z<0;\\0,&\text{otherwise}.\end{cases}

由于01损失不容易进行最优化因此我们有替代方法为

hinge 损失 $:\ell_{hinge}(z)=\max(0,1-z)\:;$
指数损失(exponential loss): $\ell_{exp}(z)=\exp(-\dot{z})\:;$
对率损失(logistic loss $) {: }\ell_{log}( z) = \log ( 1+ \exp ( - z) ) .$

本质上我们可以通过替换最优化目标的方法来得到其他学习模型；正如我们在线性回归中引入正则化一样在基础的最小化间隔上引入其他惩罚得到我们的目标

支持向量回归

现在我们来考虑回归问题训练的因变量变为了一个实数我们希望学习到一个回归模型让 $f(x)$ 和 $y$ 之间尽可能的接近

传统回归模型通常直接基于模型输出与真实输出之间的差别来计算损失只有他们的差别完全为0的时候损失才为0 与此不同的是支持向量回归(Support Vector Regression,简称 SVR)假设我们能容忍他们之间有 $\epsilon$ 的偏差只有偏差大于这个它的时候我们才计算损失

因此 SVR可以写成

\min_{\boldsymbol{w},b}\frac{1}{2}\|\boldsymbol{w}\|^{2}+C\sum_{i=1}^{m}\ell_{\epsilon}\left(f(\boldsymbol{x}_{i})-y_{i}\right),

其中 $C$ 是正则化常数损失函数的形式应该为

\left.\ell_\epsilon(z)=\left\{\begin{array}{ll}0,&\text{if}|z|\leqslant\epsilon;\\|z|-\epsilon,&\text{otherwise}.\end{array}\right.\right.

我们可以把它看作一个线性回归的变形允许偏差并且惩罚了系数复杂程度

核方法

核方法介绍

前面我们研究了SVM和SVR 他们最终学习到的模型都可以表示为核函数的线性组合事实上它是一个一般性的结论

(表示定理) 令 $H$ 为核函数 $\kappa$ 对应的再生核希尔伯特空间， $\|h\|_{\mathrm{H}}$ 表示 $H$ 空间中关于 $h$ 的范数，对于任意单调递增函数 $\Omega:[0,\infty]\mapsto\mathbb{R}$ 和任意非负损失函数 $\ell:\mathbb{R}^m\mapsto[0,\infty]$ , 优化问题

\min\limits_{h\in\mathbb{H}}F(h)=\Omega(\|h\|_{\mathbb{H}})+\ell\big(h(\boldsymbol{x}_1),h(\boldsymbol{x}_2),\ldots,h(\boldsymbol{x}_m)\big)

的解总可以写作

h^*(\boldsymbol{x})=\sum_{i=1}^m\alpha_i\kappa(\boldsymbol{x},\boldsymbol{x}_i).

也就是对损失函数毫无限制对正则化项要求单独递增优化问题解总可以写成核函数的线性组合

这体现了核函数的巨大威力因此我们开发出了大量的基于核函数的学习方法统称为 “核方法”(kernel methods)

粗略地说，在任何一种含有点积运算的算法中，用核函数来代替点积就可以称作是核方法，不仅仅可以用于SVM

核方法可以让我们享受高维空间的好处但是于此同时不需要承受其弊端，最大的好处就是低维的非线性问题在高维中非常容易使用线性方法求解，也就是将模型非线性化

核线性判别分析KLDA

我们简单的介绍“核线性判别分析”(Kernelized Linear Discriminant Analysis,简称 KLDA). 它引入核函数把线性学习器拓展为了非线性学习器 如下

我们假设通过某种映射把样本映射到了一个特征空间 $F$ 在 $F$ 中进行线性判别分析计算（学习器的形式）

h(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}}\phi(\boldsymbol{x}).

容易给出我们的学习目标为

\max_{\boldsymbol{w}}J(\boldsymbol{w})=\frac{\boldsymbol{w}^{\mathrm{T}}\mathbf{S}_{b}^{\phi}\boldsymbol{w}}{\boldsymbol{w}^{\mathrm{T}}\mathbf{S}_{w}^{\phi}\boldsymbol{w}},

其中 $S$ 是散度矩阵只是是映射后的再 $F$ 上的散度矩阵

选取核函数给出损失函数取 $\Omega = 0$ 根据表示定理给出

h(\boldsymbol{x})_{\cdot}=\sum_{i=1}^{m}\alpha_{i}\kappa(\boldsymbol{x},\boldsymbol{x}_{i}),

据此可以计算 $w$ 和 $\alpha$ 最后给出我们的 $h(x)$

核方法应用广泛

核方法的基本思想只涉及向高维空间映射，增加后续算法的非线性划分能力。因此非常多的算法都可以增加核化部分，如

核化PCA，非线性降维
核化LDA，非线性分类
核化SVM，分类聚类
核化K means 聚类

贝叶斯分类器

贝叶斯决策理论与我们的目标

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

损失函数对后验分布的期望称为后验风险函数让后验风险最小化的决策就是我们应该选取的方案

损失函数是比较好给出的我们根据我们的目标不同就可以选定合适的损失函数但是后验概率是一个比较麻烦的问题在贝叶斯统计中我们是使用理论计算出的但是在机器学习中这并不现实因此 机器学习所要实现的是基于有限的训练样本集尽可能准确地估计出后验概率

大体来说，主要有两种策略：

判别式模型 (discriminative models ) 根据 $x$ 直接给出 $P(c|x)$
生成式模型 (generative models ) 根据贝叶斯定理分别估计先验和样本分布计算出后验分布前面介绍的决策树、BP 神经网络、支持向量机等，都可归入判别式模型的范畴而后面介绍的贝叶斯分类器都属于生成式模型

朴素贝叶斯分类器

首先我们限定到这次的贝叶斯决策用于分类问题其中的有多个自变量一个分类的因变量，其中自变量有的是定类变量有的是定量的具有某种分布的自变量其参数用极大似然估计确定

选取损失函数为

\left.\lambda_{ij}=\left\{\begin{array}{ll}0,&\text{if}i=j;\\1,&\text{otherwise},\end{array}\right.\right.

此时我们可以给出分类器为

h^*(\boldsymbol{x})=\arg\max_{c\in\mathcal{Y}}P(c\mid\boldsymbol{x}),

也就是对每一个样本 $x$ 选取后验概率最大的标记

我们现在对于贝叶斯分类器的最大一个处理问题在于自变量有很多种他们有着不同的分布导致后验概率求解困难为了规避这样的障碍 朴素贝叶斯分类器(naive Bayes classifier)采用了“属性条件独立性假设 “ (attribute conditional independence assumption): 对已知类别，假设所有属性相互独立.换言之,假设每个属性独立地对分类结果发生影响

那么我们可以把后验概率修正为

P(c\mid\boldsymbol{x})=\frac{P(c)P(\boldsymbol{x}\mid\boldsymbol{c})}{P(\boldsymbol{x})}=\frac{P(\boldsymbol{c})}{P(\boldsymbol{x})}\prod_{i=1}^dP(x_i\mid c)

其中后面的累积是不同自变量的概率积因此朴素贝叶斯分类器的贝叶斯判定准则为

h_{nb}(\boldsymbol{x})=\arg\max_{c\in\mathcal{Y}}P(c)\prod_{i=1}^{d}P(x_{i}\mid c)

现在我们就可以根据训练数据集估计类先验概率

P(c)=\frac{|D_c|}{|D|}

对于离散属性可以估计出条件概率为

P(x_i\mid c)=\frac{|D_{c,x_i}|}{|D_c|}

对连续属性可考虑概率密度函数一般假定其符合正态分布在类上使用MLE估计均值和方差然后有

p(x_{i}\mid c)=\frac{1}{\sqrt{2\pi}\sigma_{c,i}}\exp\left(-\frac{(x_{i}-\mu_{c,i})^{2}}{2\sigma_{c,i}^{2}}\right)

有了以上的基础就可以使用朴素贝叶斯分类器估计新样本的分类了训练过程就是刚才的概率计算过程对于新的样本；根据前面给出的判定准则分别计算概率看看什么情况下实现极大化给出分类结论

半朴素贝叶斯分类器

朴素贝叶斯分类器采用了属性条件独立性假设，但在现实任务中这个假设往往很难成立.于是，人们尝试对属性条件独立性假设进行一定程度的放松，由此产生了一类称为 “半朴素贝叶斯分类器“(semi-naive Bayes classifiers)的学习方法.

半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息，从而既不需进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系最常用的思想是假设每个属性在类别之外最多仅依赖于一个其他属性（One-Dependent Estimator）也就是

P(c\mid\boldsymbol{x})\propto P(c)\prod_{i=1}^{d}P(x_{i}\mid c,pa_{i}),

其中属性 $pa_i$ 称为 $x_i$ 父属性在这个情况下，我们可以对 $\prod_{i=1}^{d}P(x_{i}\mid c,pa_{i})$ 进行估计量

半朴素贝叶斯分类器的核心就在于怎么设置父属性不同的做法产生不同的分类器

最直接的做法是假设所有属性都依赖于同一个属性，称为 “超父” 然后通过交叉验证等模型选择方法来确定超父属性称为 SPODE (Super-Parent ODE)

当然我们还有很多其他方法来确定父属性比如 TAN (Tree Augmented naive Bayes) 效果是保留强相关属性的依赖性，AODE(Averaged One-Dependent Estimator) 是一种基于集成学习的超父方法，考虑了所有属性都作为超父的情况，结构如下图所示

非常自然的，将属性条件独立性假设放松能换取泛化性能提升，那么可以继续放松吗？这里就回到了我们最初的问题上了，引入属性条件独立假设是为了解决高阶联合概率导致的训练样本不足的问题，继续放松会再次坠入这个问题。

贝叶斯网

贝叶斯网的引入

贝叶斯网(Bayesian network)亦称 “信念网”(belief network),它借助有向无环图(Directed Acyclic Graph,简称DAG) 来刻画属性之间的依赖关系，并使用条件概率表(Conditional Probability Table,CPT)来描述属性的联合概率分布（我们的举例将用分类自变量描述，实际上不受限制）

贝叶斯网是一种经典的概率图模型机器学习进阶与无监督学习：概率图模型

具体来说，一个贝叶斯网 $B$ 由结构 $G$ 和参数 $\Theta$ 两部分构成。网络结构 $G$ 是一个有向无环图，其每个结点对应于一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来。参数 $\Theta$ 定量描述了这种依赖关系，如果属性 $x_i$ 的父节点为 $\pi_i$ 则参数 $\Theta$ 包含了所有的 $P(x_i|\pi_i)$

一个简单的例子为

贝叶斯网的结构

贝叶斯网修正了我们在朴素贝叶斯介绍的ODE思想，但是也可以说是一种广义的朴素贝叶斯。他的结构有效地表达了属性间的条件独立性，给定父结点集，贝叶斯网假设每个属性与它的非后裔属性独立 这里我们要理解这一句与 有向无环图 的联系

也就是定义联合概率分布为

P_B(x_1,x_2,\dots,x_d)=\prod\limits_{i=1}^dP_B(x_i\mid\pi_i)=\prod\limits_{i=1}^d\theta_{x_i|\pi_i}.

对我们前面举的习惯的例子，他的联合概率为

P(x_1,x_2,x_3,x_4,x_5)=P(x_1)P(x_2)P(x_3\mid x_1)P(x_4\mid x_1,x_2)P(x_5\mid x_2)

事实上，贝叶斯网有三种基本的依赖结构，如下

在V型结构中我们能发现一个问题，是否已知 $x_4$ 影响了他的父节点是否独立，当子节点未知的时候，两个父节点独立，反之则不独立

这里介绍独立问题仅仅是一个简单的偏题，我们理解贝叶斯网结构本身就足够了

贝叶斯网的学习

若网络结构已知，即属性间的依赖关系已知，则贝叶斯网的学习过程相对简单，只需通过对训练样本“计数”，估计出每个结点的条件概率表即可.和朴素贝叶斯也没有什么两样

实际上，现实应用中我们往往并不知晓网络结构，正如半朴素贝叶斯ODE中不知道谁是父节点的情况一样。贝叶斯网学习的首要任务就是根据训练数据集来找出结构最“恰当”的贝叶斯网.

“评分搜索”是求解这一问题的常用办法.具体来说，我们先定义一个评分函数(score function),以此来评估贝叶斯网与训练数据的契合程度，然后基于这个评分函数来寻找结构最优的贝叶斯网。选取什么样的评分函数影响了我们最后贝叶斯网的结果

常用评分函数通常基于信息论准则，一般我们选取编码长度(包括描述网络和编码数据)最短的贝叶斯网，，这就是“最小描述长度”(Minimal Description Length,简称MDL)准则. AIC准则 BIC准则都是可行的

不幸的是，从所有可能的网络结构空间搜索最优贝叶斯网结构是一个NP 难问题，难以快速求解.有两种常用的策略能在有限时间内求得近似解：第一种是贪心法，另一种则是限定结构方法，比如限制网络结构为树形的

推断

贝叶斯网训练好之后就能用来回答“查询”(query),即通过一些属性变量的观测值来推测其他属性变量的取值。这样通过已知变量观测值来推测待查询变量的过程称为“推断 “ (inference)

最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，遗憾的是，当网络结点较多、连接稠密时,难以进行精确推断。此时我们需要考虑一些近似的方法，我们目前一般使用吉布斯采样(Gibbs sampling)来完成

令 $\mathbf{Q}=\{Q_1,Q_2,\ldots,Q_n\}$ 表示待查询变量， $\mathbf{E}=\{E_1,E_2,\ldots,E_k\}$ 为证据变量，已知其取值为 $\mathbf{e}=\{e_1,e_2,\ldots,e_k\}.$ 目标是计算后验 $P(\mathbf{Q}=\mathbf{q}\mid\mathbf{E}=\mathbf{e})$ , 其中 $\mathbf{q}=\{q_1,q_2,\ldots,q_n\}$ 是待查询变量的一组取值

吉布斯采样算法先随机产生一个与证据 $\mathbf{E}=\mathbf{e}$ 一致的样本 $\mathbf{q}^{0}$ 作为初始点，然后每步从当前样本出发产生下一个样本.具体来说，在第 $t$ 次采样中，算法先假设 $\mathbf{q}^t=\mathbf{q}^{t-1}$ ,然后对非证据变量逐个进行采样改变其取值，采样概率根据贝叶斯网 $B$ 和其他变量的当前取值(即 $\mathbf{Z}=\mathbf{z})$ 计算获得.假定经过 $T$ 次采样得到的与 $\mathbf{q}$ 一致的样本共有 $n_q$ 个，则可近似估算出后验概率

P(\mathbf{Q}=\mathbf{q}\mid\mathbf{E}=\mathbf{e})\simeq\frac{n_q}{T}.

事实上，这就是贝叶斯统计中的马尔可夫链蒙特卡洛（MCMC）方法思想变形，我们不断的变换就是一个马尔可夫链