关于周志华教师的《机器学习》这本书的学习笔记
记载学习进程
本博客记载Chapter7

1 贝叶斯决策论

假定有$N$种或许的类别符号，即Y={c1,c2,…,cN}Y=\{c_1,c_2,…,c_N\}Y={c1​,c2​,…,cN​}。ij\lambda_{ij}ij​是将一个实在符号为cjc_jcj​的样本误分类到cic_ici​的丢失。依据后验概率P(ci∣x)P(c_i|\bold x)P(ci​∣x)可取得将样本$\mathbf{x}$误分类到cic_ici​所发生的希望丢失（expected loss），即在样本$\mathbf{x}$上的“条件危险”（conditional risk）(P(cj∣x)P(c_j|\bold x)P(cj​∣x):表明样本$\mathbf{x}$是cjc_jcj​的概率):

咱们的使命是寻觅一个判别原则$h:\mapsto Y$以最小化整体危险：

明显，关于每一个样本$\mathbf{x}$，若$h$能最小化条件危险$R(h(\mathbf{x})|\mathbf{x})$，则整体危险$R(h)$就能最小化。这体现了贝叶斯断定原则（Bayes decision rule）：为最小化整体危险，只需求在每个样本上选择哪个能使条件危险$R(c|\mathbf{x})$最小的类别符号：

此刻，h∗h^*h∗被称为贝叶斯最优分类器（Bayes optimal classifier），与之对应的整体危险R(h∗)R(h^*)R(h∗)对应贝叶斯危险（Bayes risk）。1−R(h∗)1-R(h^*)1−R(h∗)反映了分类器所能到达的最好性能。

+++

若希望丢失ij\lambda_{ij}ij​符合：

此刻条件危险$R(c|\mathbf{x})=1-P(c|\mathbf{x})$

于是，最小化分类错误率的贝叶斯最优分类器：

即选择后验概率$P(c|\mathbf{x})$最大的类别符号。

+++

不难看出，欲运用贝叶斯断定原则来最小化决策危险，首先要取得后验概率$P(c|x)$。 但是，在实际使命中这一般难以直接取得。从这个角度来看，机器学习所要完成的是依据有限的练习样本集尽或许精确地估量出后验概率$P(c|x)$。大体来说，主要有两种战略：

• 给定$x$，可经过直接建模$P(c|x)$来猜测$c$，这样得到的是 “判别式模型”(discriminativemodels)
• 也可先对联合概率散布$P(x,c)$建模，然后再由此取得$P(c|x)$，这样得到的是 “生成式模型’(generative models)

明显，前面介绍的决策树、BP神经网络、支撑向量机等，都可归入判别式模型的范畴。对生成式模型来说，必然考虑

其间，$P(c)$是先验（prior）概率，$P(x|c)$是样本$x$关于类符号$c$的类条件概率，或称为似然（likelihood）；$P(x)$是用于归一化的依据因子（evidence）。关于给定样本，依据因子和类符号无关，因而估量$P(c|x)$的问题就转化为如何依据练习数据$D$估量先验$P(c)$和似然$P(x|c)$。 依据大数定理，$P(c)$能够用各类样本呈现的频率来进行估量；关于类条件概率$P(x|c)$来说，因为其触及关于$x$一切特点的联合概率，直接依据样本呈现频率来估量会遭到严峻困难。

2 极大似然估量

假定$P(x|c)$具有确定的办法而且被参数c\theta_cc​唯一确定，则咱们的使命便是运用练习集$D$估量参数c\theta_cc​。

事实上，概率模型练习进程便是参数估量（parameter estimation）。关于参数练习进程，有频率学主义学派和贝叶斯学派。前者认为参数尽管未知，但是是客观存在的固定值，能够优化似然函数来确定参数；后者认为参数是未观察到的随机变量，其本身能够有散布，因而能够假定参数遵守一个先验散布，然后依据观测到的数据来核算参数的后验散布。

这一节咱们选用频率主义学派的极大似然估量（MLE）办法：

此刻参数c\theta_cc​的极大似然估量为c\hat {\theta_c}c​​:

需注意的是,这种参数化的办法虽能使类条件概率估量变得相对简略，但估量结果的精确性严峻依靠于所假定的概率散布办法是否符合潜在的实在数据散布。在实际应用中，欲做出能较好地挨近潜在实在散布的假定，往往需在必定程度上运用关于应用使命本身的经历知识，否则若仅凭“猜想”来假定概率散布办法，很或许发生误导性的结果。

3 朴素贝叶斯分类器

朴素贝叶斯分类器（naive Bayes classifier）选用了 “特点条件独立性假定”，即假定对已知的类别，一切的特点彼此独立。因而，后验概率能够写为：

其间，$d$为特点数目，即$x$的维数。

因为关于一切类别，$P(x)$相同，因而贝叶斯断定原则为：

朴素贝叶斯的练习进程便是依据练习集$D$来估量类先验概率$P(c)$，并为每个特点估量条件概率P(xi∣c)P(x_i|c)P(xi​∣c)。其间

对接连特点能够考虑概率密度函数，假定P(xi∣c)∼N(c,i,c,i2)P(x_i|c)\thicksim N(\mu_{c,i},\sigma_{c,i}^2)P(xi​∣c)∼N(c,i​,c,i2​)，其间c,i\mu_{c,i}c,i​和c,i2\sigma_{c,i}^2c,i2​分别是第$c$类样本在第$i$个特点上取值的均值和方差，有：

为了避免其他特点带着的信息被练习会集未呈现的特点值“抹去”，在估量概率值的时分一般要进行滑润，咱们选用拉普拉斯修正。即令$N$表明练习集$D$种或许呈现的类别数；令NiN_iNi​表明第$i$个特点或许的取值数，则：

在实际使命中朴素贝叶斯分类器有多种运用办法。例如：

• 若使命对猜测速度要求较高，则对给定练习集，可将朴素贝叶斯分类器触及的一切概率估值事。先核算好存储起来，这样在进行猜测时只需“查表”即可进行判别
• 若使命数据更替频繁，则可选用“懒惰学习”(lazy learning) 办法，先不进行任何练习，待收到猜测请求时再依据当时数据集进行概率估值
• 若数据不断增加，则可在现有估值基础上，仅对新增样本的特点值所触及的概率估值进行计数修正即可完成增量学习

4 半朴素贝叶斯分类器

朴素贝叶斯采纳的特点条件独立性假定往往在实际中很难建立，因而人们尝试对特点条件独立性假定进行必定程度的放松，选用“半朴素贝叶斯分类器”。

半朴素贝叶斯分类器的基本思想：适当考虑一部分特点间的彼此依靠信息，然后既不需求进行彻底联合概率核算，又不至于疏忽比较强的特点依靠联系。“独依靠估量”（ODE）：是半朴素贝叶斯分类器最常用的战略，即假定每个特点在类别之外最多仅依靠于一个其他特点。

几种常见的办法：

• SPOED办法（super-parent ODE）：一切特点都依靠于同一个特点，称为“超父”

• TAN办法（Tree Augmented naive Bayes）：在最大带权生成树的基础上，经过核算任意两个特点之间的互信息，构建最大带权生成树。

  互信息核算公式：

  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)}I(xi​,xj​∣y)=xi​,xj​;c∈Y∑​P(xi​,xj​∣c)logP(xi​∣c)P(xj​∣c)P(xi​,xj​∣c)​

• ADOE(Averaged One-Dependent Estimator)：依据集成学习机制，更为强壮的独依靠分类器。ADOE尝试将每个特点作为超父来构建SPODE，将具有满足练习数据支撑的SPODE集成起来作为最终结果。

5 贝叶斯网

贝叶斯网称为“信念网”（belief network），凭借有向无环图（Directed Acyclic Graph，DAG）来描写特点之间的依靠联系，并运用条件概率表（Contional Probability Table,CPT）来描绘特点的联合概率散布。

一个贝叶斯网络由结构$G$和参数\theta两部分构成。（$B=<G,>$）。 $G$是一个有向无环图，每个结点对应一个特点，若两个特点有直接依靠联系，则由一条边连接起来。\theta定量描绘依靠联系，假定特点xix_ixi​在$G$中的父节点集为i\pi_ii​，则\theta包含了每个特点的条件概率表xi∣i=P(xi∣i)\theta_{x_i|\pi_i}=P(x_i|\pi_i)xi​∣i​​=P(xi​∣i​)。

5.1 结构

贝叶斯网结构有效地表达了特点间的条件独立性。给定父结点集，贝叶斯网络假定每个特点与它的非后嗣特点独立，于是$B=<G;>$将特点x1,x2,…,xdx_1,x_2,…,x_dx1​,x2​,…,xd​的联合概率散布界说为：

贝叶斯网络中由三种典型依靠联系：

• 同父联系：给定父结点x1x_1x1​的取值，x3x_3x3​和x4x_4x4​就条件独立
• 顺序结构：给定$x$的值，$y$和$z$就条件独立
• V型结构：也叫冲撞结构，给定x4x_4x4​的取值，x1x_1x1​和x2x_2x2​必定不独立；但x4x_4x4​的值假如彻底位置，则x1x_1x1​和x2x_2x2​是彼此独立的。这种独立性称为“边际独立性”。

为了分析图中变量之间的条件独立性，能够运用“有向别离”：

• 找到一切V型结构，在V型结构的两个父结点之间加上一条无向边
• 将一切有向边改为无向边

由此发生的图叫品德图（moral graph），将父结点相连的进程称为“品德化”。（孩子的爸爸妈妈之间应该有牢靠的联系，否则是不品德的）

依据品德图能直观、迅速地找到变量间的条件独立性。假定品德图中有变量$x,y$和变量集合$z=z$，若变量$x$和$y$能在图上被$z$分开，即从品德图中将变量集合$z$去除后，$x$和$y$分属两个连通分支，则称变量$x$和$y$被$z$有向别离。

5.2 学习

贝叶斯学习网中的首要使命便是依据练习数据集找出结构最“恰当”的贝叶斯网。

选用评分函数，评价贝叶斯网和练习数据的符合程度，然后依据这个评分函数寻觅结构最优的贝叶斯网是一种常用的办法。常用评分函数一般依据信息论原则，此类原则将学习问题看作一个数据压缩使命，学习的方针是找到一个能以最短编码长度描绘练习数据的模型，此刻编码的长度包含了描绘模型本身所需的字节长度和运用该模型描绘数据所需的字节长度。对贝叶斯网学习而言，模型便是贝叶斯网，每个贝叶斯网描绘了一个在练习数据上的概率散布，自有一套编码机制能使那些经常呈现的样本有更短的编码。于是，咱们应选择那个综合编码长度(包含描绘网络和编码数据)最短的贝叶斯网，这便是 “最小描绘长度”(Minimal Description Length，简称MDL)原则。

评分函数能够写为如下（其间，|B|是贝叶斯网的参数个数，$f()$表明描绘每个参数\theta​所需求的编码位数），第一项是核算编码贝叶斯网的编码位数，第二项是描绘概率散布PBP_BPB​对数据集$D$的拟合程度。

若$f()$为1，则对应AIC评分函数；若f()=12log⁡mf(\theta)=\frac{1}{2}\log mf()=21​logm为，则对应BIC评分函数；若\theta为0，则对应极大似然估量。

不幸的是,从一切或许的网络结构空间搜索最优贝叶斯网结构是一个NP难问题，难以快速求解。有两种常用的战略能在有限时间内求得近似解：第一种是贪心法，例如从某个网络结构动身，每次调整一条边(增加、 删去或调整方向)，直到评分函数值不再降低为止；第二种是经过给网络结构施加束缚来削减搜索空间，例如将网络结构限定为树形结构等。

5.3 揣度

贝叶斯网络练习好之后能用来回答“查询”，即经过一些特点变量的观测值来估测其他特点变量的取值。经过已知变量来估测待查询变量的进程称为“揣度”（inference），已知变量观测值称为“依据”（evidence）。

依据贝叶斯网界说的联合概率散布来精确核算后验概率是NP难的问题，需求凭借“近似揣度”，降低精度要求，在有限时间内求得近似解。咱们常选用吉布斯采样（Gibbs sampling）：

• 令Q={Q1,Q2,…,Qn}Q=\{Q_1,Q_2,…,Q_n \}Q={Q1​,Q2​,…,Qn​}表明待查询变量，E={E1,E2,…,Ek}E=\{E_1,E_2,…,E_k\}E={E1​,E2​,…,Ek​}为依据变量，已知取值为e={e1,e2,…,ek}e=\{e_1,e_2,…,e_k\}e={e1​,e2​,…,ek​}。方针是核算后验概率$P(Q=q|E=e)$。

• 吉布斯采样先随机发生一个与依据$E=e$共同的样本q0q^0q0作为初始点，然后每步从当时样本动身发生下一个样本。在第$t$次采样，咱们先假定qt=qt−1q^t=q^{t-1}qt=qt−1，然后对非依据变量逐一进行采样改变其取值，采样概率依据贝叶斯网B和其他变量的当时取值核算取得。假定经过$T$次采样得到的与$q$共同的样本共有nqn_qnq​个，近似估算出后验概率：

  P(Q=q∣E=e)=nqTP(Q=q|E=e)=\frac{n_q}{T}P(Q=q∣E=e)=Tnq​​

实质上，吉布斯采样是在贝叶斯网一切变量的联合状态空间与依据$E=e$共同的子空间中进行 “随机散步”(random wallk)。每一步仅依靠于前一步的状态，这是一个“马尔可夫链”(Markov chain)。在必定条件下，无论从什么初始状态开端，马尔可夫链第t步的状态散布在$t\to \infty$时必收敛于一个平稳散布(stationary distribution)； 关于吉布斯采样来说，这个散布恰好是$P(Q|E=e)$。因而，在$T$很大时，吉布斯采样相当于依据$P(Q|E=e)$采样，然后确保了式(17)收敛于$P(Q=q|E=e)$。

6 EM算法

实际生活中，咱们往往会遇到样本“不完整”的状况。未观测的变量的学名是“隐变量”，令$X$表明已观测变量集，$Z$表明隐变量集，\theta表明模型参数，若对\theta做极大似然估量，则要最大化对数似然：

因为Z是隐变量，因而无法直接求解，这时咱们能够经过对$Z$核算希望，来最大化已观测数据的对数“边际似然”：

EM算法是常用的估量参数隐变量的利器。其基本思想：**若\theta已知，则可依据练习数据揣度出最优隐变量的值（E步）；反之，若$Z$的值已知，则可方便地对\theta做极大似然估量。**过程如下：

• 以初始值0\theta^00为起点，对式(19)，能够迭代执行以下过程直到收敛：
  • 依据t\theta^tt揣度隐变量$Z$的希望，记ZtZ_tZt​
  • 依据已观测变量$X$和$Z$对参数\theta做极大似然估量，记为t+1\theta^{t+1}t+1

进一步，若咱们不是取Z的希望，而是依据t^tt核算隐变量$Z$的概率散布P(Z∣X,t)P(Z| X, \theta^t)P(Z∣X,t)，则EM算法的两个过程是:

• E步(Expectation)：以当时参数t^tt揣度隐变量散布P(Z∣X,t)P(Z | X,\theta^t)P(Z∣X,t),并核算对数似然$LL(|X,Z)$关于$Z$的希望

  Q(∣t)=EZ∣X,tLL(∣X,Z)Q(\theta|\theta^t)=E_{Z|X,\theta^t}LL(\theta|X,Z)Q(∣t)=EZ∣X,t​LL(∣X,Z)

• M步(Maximization):寻觅参数最大化希望似然，即

  t+1=arg⁡max⁡Q∣t\theta_{t+1}=\mathop{\arg\max}_{\theta}\space Q{\theta|\theta^t}t+1​=argmax​Q∣t

简要来说, EM算法运用两个过程交替核算：第一步是希望(E)步，运用当时估量的参数值来核算对数似然的希望值；第二步是最大化(M)步，寻觅能使E步发生的似然希望最大化的参数值，然后，新得到的参数值从头被用于E步，直至收敛到局部最优解。 事实上，隐变量估量问题也可经过梯度下降等优化算法求解，但因为求和的项数将随着隐变量的数目以指数级上升，会给梯度核算带来费事；而EM算法则可看作一种非梯度优化办法。