贝叶斯分类器

---

文章目录

• @[toc]
• 朴素贝叶斯
• 一个重要的前提
• 形式
• 估计
• 连续值属性
• 潜在问题
• 特点
• 贝叶斯信念网络
• 概念
• 训练
• 拓扑结构的学习
• 主观专家的编码
• 网络的推断
• $BBN$ 的特点

朴素贝叶斯

朴素贝叶斯分类器

一个重要的前提

属性之间的独立性假设

$P(a_1,...,a_n|v_j) = \Pi_iP(a_i|v_j)$P(a1​,...,an​∣vj​)=Πi​P(ai​∣vj​)

形式

$v_{NB} = arg \max_{v_j \in V}P(v_j)\Pi_iP(a_i|v_j)$vNB​=argvj​∈Vmax​P(vj​)Πi​P(ai​∣vj​)

从训练数据中估计 $P(a_i|v_j)$P(ai​∣vj​) 要比直接估计联合密度估计要容易得多。

估计

从训练样本中进行估计

• 对任意目标值 $v_j$vj​
  • 估计出 $\hat P(v_j)$P^(vj​)
  • 对任意一个 $a_j$aj​，估计出 $\hat P(a_i|v_j)$P^(ai​∣vj​)
• 模型形式为
  • $v_{NB} = arg \max\limits_{v_j \in V}\hat P(v_j)\Pi_{a_i \in x}\hat P(a_i|v_j)$vNB​=argvj​∈Vmax​P^(vj​)Πai​∈x​P^(ai​∣vj​)
• 计算出来的值再进行概率归一化即可

连续值属性

对于连续值属性的讨论

• 离散化
• 利用概率分布来进行估计
  • $P(x_j|C_j) = \frac{1}{\sqrt{2\pi}\sigma_{ij}}exp(-\frac{(x_j - \mu_{ij})^2}{2\sigma_{ij}^2})$P(xj​∣Cj​)=2π​σij​1​exp(−2σij2​(xj​−μij​)2​)
  • 其中 $\mu_{ij}$μij​ 和 $\sigma_{ij}$σij​ 分别为类 $C_i$Ci​ 中随机变量 $x_i$xi​ 的期望和标准差，利用对应的样本期望和标准差来进行估计

潜在问题

• 如果某一个属性的条件概率为 $0$0,那么整个类的后验概率也为 $0$0
• 训练样本不能覆盖那么多属性值时，不能分类某些测试记录

针对第一个问题，采用平滑技术

$\frac{n_c+mp}{n+m},p = \frac{1}{k}$n+mnc​+mp​,p=k1​
其中 $p$p 是按均匀概率的观念点出发，如果有 $k$k 个可能的属性值,则取值为 $\frac{1}{k}$k1​.
$m$m 被称为等效样本.
那么修正式相当于 $n$n 个实际观察加上 $m$m 个按 $p$p 分布的虚拟样本。

特点

• 对于孤立噪声点，朴素贝叶斯分类器是健壮的
• 可以处理属性值遗漏问题
• 可以处理无关属性
• 属性相关性高会降低朴素贝叶斯分类器的性能

---

贝叶斯信念网络

贝叶斯信念网络 $(Bayes\ belief\ network,BBN)$(Bayes belief network,BBN)

概念

• 描述的是一组变量所遵循的概率分布，通过一组条件概率来指定一组条件独立性假设
• 可以表述变量自己上的条件独立性假设。比朴素贝叶斯分类器的限制更少。
• 如果一个节点的父母节点已知，则它条件独立于它的所有非后代节点。

贝叶斯信念网络的表示

• 一个无环有向图来标识
• 一个概率表，即一组局部条件概率的集合

训练

• 如果网络结构已知，且变量可以从训练数据中完全取得，那么训练就比较简单

• 如果网络结构已知，但是只有部分变量能从训练数据中观察到，那么学习问题就困难多了。类似于神经网络的隐藏层的学习。

• 如果结构位置，那么需要学习结构。

  • 定义一个 评分函数
  • 基于信息论准则
  • 引入了归纳偏置

选择综合编码长度最短的贝叶斯网----最小长度描述准则

评分函数

$S(B|D) = f(\theta)|B| - LL(B|D)$S(B∣D)=f(θ)∣B∣−LL(B∣D)
其中 $|B|$∣B∣ 是贝叶斯网的参数个数； $f(\theta)$f(θ) 表示描述每个参数 $\theta$θ 所需的字节数

其中 $LL(B|D) = \sum_{i=1}^m\log P_B(x_i)$LL(B∣D)=i=1∑m​logPB​(xi​)
是贝叶斯网络的似然。

寻找一个贝叶斯网络 $B$B 使得评分函数 S(B|D)最小

• 如果 $f(\theta) = 1$f(θ)=1,则就是 $AIC$AIC 准则
  $AIC(B|D) = |B| - LL(B|D)$AIC(B∣D)=∣B∣−LL(B∣D)
• 如果 $f(\theta) = \frac{1}{2}\log m$f(θ)=21​logm，则就是 $BIC$BIC 准则
  $BIC(B|D) = \frac{\log m}{2}|B| - LL(B|D)$BIC(B∣D)=2logm​∣B∣−LL(B∣D)
• 如果 $f(\theta) = 0$f(θ)=0 ，即不考虑进行编码长度，函数退化为对数似然。
  $S(B|D) = - LL(B|D)$S(B∣D)=−LL(B∣D)
  参数 $\theta_{x_i|\pi_i} = \hat P_D(x_i|\pi_i)$θxi​∣πi​​=P^D​(xi​∣πi​)。其中 $\hat P_D(·)$P^D​(⋅) 是 $D$D 上的经验分布。所以只需要进行搜索得到最优参数。

拓扑结构的学习

主观专家的编码

• 设 $T = (X_1,...,X_d)$T=(X1​,...,Xd​)，表示变量的全序。
• 对于所有的 $T$T 中的元素
  • $X_{T(j)}$XT(j)​ 表示 $T$T 中第 $j$j 个次序最高的变量
  • $\pi(X_{T(j)}) = \{X_{T(1)},...,X_{T(j-1)}\}$π(XT(j)​)={XT(1)​,...,XT(j−1)​} 表示排在 $X_{T(j)}$XT(j)​ 前面的变量集合
  • 从 $\pi(X_{T(j)})$π(XT(j)​) 中去掉对 $X_j$Xj​ 没有影响的变量。这是由先验知识得到的
  • 在 $X_{T(j)}$XT(j)​ 和 $\pi(X_{T(j)})$π(XT(j)​) 中剩余的变量画弧。

这是一个如何通过主观专家来构建合理网络结构的过程。

梯度提升训练

• $w_{ijk}$wijk​ 代表概率表的一个表项，即在给定 $U_i$Ui​ 取值 $u_{ik}$uik​ 时，网络变量 $Y_i$Yi​ 值为 $y_{ij}$yij​ 的概率。

• 梯度的计算：
  $\frac{\partial \ln P(D|h)}{\partial w_{ijk}} = \sum_{d \in D}\frac{P(Y_i = y_{ij},U_i = u_{ik}|d)}{w_{ijk}}$∂wijk​∂lnP(D∣h)​=d∈D∑​wijk​P(Yi​=yij​,Ui​=uik​∣d)​

• 梯度的更新：
  $w_{ijk} \leftarrow w_{ijk} + \eta \sum_{d \in D}\frac{P_h(y_{ij},u_{ik}|d)}{w_{ijk}}$wijk​←wijk​+ηd∈D∑​wijk​Ph​(yij​,uik​∣d)​

• 权重的归一化：
  $w_{ijk} \leftarrow \frac{w_{ijk}}{\sum_{j}w_{ijk}}$wijk​←∑j​wijk​wijk​​

该算法可能找到的是局部最优解。

网络的推断

• 推断出的结果一把都是一个概率分布。
• 利用贝叶斯公式来进行概率的而计算

例如：

• 如果没有任何先验信息判断一个人是否会患心脏病：
  • 计算过程
    $P(HD = Yes) = \sum_\alpha\sum_\beta P(HD = Yes|E = \alpha,D = \beta)P(E = \alpha,D = \beta)$P(HD=Yes)=α∑​β∑​P(HD=Yes∣E=α,D=β)P(E=α,D=β)
    $= \sum_\alpha\sum_\beta P(HD = Yes|E = \alpha,D = \beta)P(E = \alpha)P(D = \beta)$=α∑​β∑​P(HD=Yes∣E=α,D=β)P(E=α)P(D=β)
    $= 0.25*0.7*0.25+0.45*0.7*0.75+ 0.55*0.3*0.25+0.75*0.3*0.75 = 0.49$=0.25∗0.7∗0.25+0.45∗0.7∗0.75+0.55∗0.3∗0.25+0.75∗0.3∗0.75=0.49
    $\Rightarrow P(HD = No) = 1-P(HD = Yes) = 0.51$⇒P(HD=No)=1−P(HD=Yes)=0.51
• 已知该人有高血压
  • 计算过程
    $P(BP = 高) = \sum P(BP = 高|HD = \gamma)P(HD = \gamma)$P(BP=高)=∑P(BP=高∣HD=γ)P(HD=γ)
    $= 0.85*0.49+0.2*0.51 = 0.5185$=0.85∗0.49+0.2∗0.51=0.5185
    所以患心脏病的后验概率是：
    $P(HD = Yes|BP = 高) = \frac{P(BP = 高|HD = Yes)P(HD = Yes)}{P(BP = 高)}$P(HD=Yes∣BP=高)=P(BP=高)P(BP=高∣HD=Yes)P(HD=Yes)​
    $= \frac{0.85*0.49}{0.5185} = 0.8033$=0.51850.85∗0.49​=0.8033
    $P(HD = No|BP = 高) = 0.1967$P(HD=No∣BP=高)=0.1967
• 经常锻炼且饮食健康
  • 计算方式
    $P(HD = Yes|BP = 高，D = 健康，E = Yes)$P(HD=Yes∣BP=高，D=健康，E=Yes)
    $= [\frac{P(HD = Yes|BP = 高，D = 健康，E = Yes)}{P(BP = 高|D = 健康，E = Yes)}] * P(HD = Yes|D = 健康，E = Yes)$=[P(BP=高∣D=健康，E=Yes)P(HD=Yes∣BP=高，D=健康，E=Yes)​]∗P(HD=Yes∣D=健康，E=Yes)
    $= \frac{P(BP = 高|HD = Yes)P(HD = Yes|D = 健康,E = Yes)}{\sum_\gamma P(BP = 高| HD = \gamma)P(HD = \gamma|D = 健康,E = Yes)}$=∑γ​P(BP=高∣HD=γ)P(HD=γ∣D=健康,E=Yes)P(BP=高∣HD=Yes)P(HD=Yes∣D=健康,E=Yes)​
    $= \frac{0.85*0.25}{0.85*0.25+0.2*0.75} = 0.5862$=0.85∗0.25+0.2∗0.750.85∗0.25​=0.5862
    则$P(HD = No|BP = 高，D = 健康，E = Yes) = 0.4138$P(HD=No∣BP=高，D=健康，E=Yes)=0.4138

$BBN$BBN 的特点

• 提供了一种图模型来捕获先验知识，还可以对变量之间的因果关系进行编码
• 构建网络结构的过程虽然费时费力，但是结构确定了，容易添加新的变量
• 贝叶斯网络很适合处理不完全数据
• 数据和先验信息以概率方式结合，所以可以避免过拟合问题。