贝叶斯分类器

作者: 抄书侠 | 来源:发表于2019-10-19 11:03 被阅读0次

总结

本节从贝叶斯公式出发，通过最小化错误分类概率得到贝叶斯决策理论。进一步定义决策面和决策函数，基于正态分布讨论了贝叶斯分类的样子，但实际情况下，不一定是正态分布的，此时就需要对概率密度函数进行估计。最经典的，如果数据点都来自同一个分布，就是使用最大似然估计，如果数据点不是来自同一个分布，我们引入混合模型，采用EM算法来非线性迭代优化求解。之前都是假设属于某个分布来计算参数，但我们如果在没有假设基于什么分布的情况下，一维我们用直方图统计，高维时用超立方体，但是这是个非连续的阶跃函数，进一步引入了有更好的数学性质的核。这叫做核密度估计，这个过程中，围绕点 $x$ 的volume时固定的，落在这个里面的点数时变化的，如果把这个过程反过来，就成了KNN密度估计，直观上来说是给定某个点，统计距它最近的k个点的类别，判断这个点为类别数最多的那个类。最后讨论了极端情况假设，各个特征分量相互独立，称为朴素的贝叶斯分类器，这个条件太苛刻，在实际情况下少见，所以引入贝叶斯网络，能够让我们能够在两个极端的任意位置停留。

贝叶斯决策理论

贝叶斯公式
先验概率 $P\left(\omega_{i}\right)$ ，类 $\omega_i$ 的概率密度函数 $p\left(\boldsymbol{x} | \omega_{\mathrm{i}}\right)$ 。给定贝叶斯公式 $P\left(\omega_{i} | \boldsymbol{x}\right)=\frac{p\left(\boldsymbol{x} | \omega_{i}\right) P\left(\omega_{i}\right)}{p(\boldsymbol{x})}$ ，其中 $p(\boldsymbol{x})=\sum_{i=1}^{i} p\left(\boldsymbol{x} | \omega_{i}\right) P\left(\omega_{i}\right)$ 那么根据贝叶斯分类法则，将 $x$ 分类到 $\omega^{*}=\arg \max _{\omega_{i}} P\left(\omega_{i} | \boldsymbol{x}\right)=\arg \max _{\omega_{i}} p\left(\boldsymbol{x} | \omega_{i}\right) P\left(\omega_{i}\right)$ 。

分类错误概率
分类器若把空间分为 $R_1,R_2$ 两部分，

示意图那么如果但判别为类,且则就算产生了错误分类。
那么总的错误概率为：

最小化错误分类概率
$x$ 被分类到 $\omega_i$ 是被错误分类的概率是 $1-P\left(\omega_{i} | \boldsymbol{x}\right)=\sum_{k \neq i} P\left(\omega_{k} | \boldsymbol{x}\right)$
那么按贝叶斯分类 $\omega^{*}=\arg \max _{\omega_{i}} P\left(\omega_{i} | \boldsymbol{x}\right)=\arg \max _{\omega_{i}} p\left(\boldsymbol{x} | \omega_{i}\right) P\left(\omega_{i}\right)$ 则变成了最小化错误分类 $\omega^{*}=\arg \min _{\omega_{i}} \sum_{k \neq i} P\left(\omega_{k} | \boldsymbol{x}\right)=\arg \min _{\omega_{i}} \sum_{k \neq i} p\left(\boldsymbol{x} | \omega_{k}\right) P\left(\omega_{k}\right)$

最小化风险
假设 $\lambda_{ij}$ 是本属于第 $i$ 类的样本错分到第 $j$ 类的风险。
那么原有的最小化分类错误概率 $P_{e}=P\left(\boldsymbol{x} \in R_{2}, \omega_{1}\right)+P\left(\boldsymbol{x} \in R_{1}, \omega_{2}\right)$
变成最小化平均风险 $P_{e}=\lambda_{12} P\left(\boldsymbol{x} \in R_{2}, \omega_{1}\right)+\lambda_{21} P\left(\boldsymbol{x} \in R_{1}, \omega_{2}\right)$
$P_{e}=\lambda_{12} P\left(\boldsymbol{x} \in R_{2} | \omega_{1}\right) P\left(\omega_{1}\right)+\lambda_{21} P\left(\boldsymbol{x} \in R_{1} | \omega_{2}\right) P\left(\omega_{2}\right)$
$P_{e}=\lambda_{12} P\left(\omega_{1}\right) \int_{R_{2}} p\left(\boldsymbol{x} | \omega_{1}\right) d \boldsymbol{x}+\lambda_{21} P\left(\omega_{2}\right) \int_{R_{1}} p\left(\boldsymbol{x} | \omega_{2}\right) d \boldsymbol{x}$

总共 $N$ 个样本，第 $k$ 类 $NP(\omega_k)$ 个样本，第 $k$ 类错误分到第 $i$ 类的样本数 $N P\left(\omega_{\mathrm{k}}\right) \int_{R_{i}} p\left(\boldsymbol{x} | \omega_{\mathrm{k}}\right) d \boldsymbol{x}$
带来的惩罚 $N P\left(\omega_{\mathrm{k}}\right) \lambda_{\mathrm{ki}} \int_{R_{i}} p\left(\boldsymbol{x} | \omega_{\mathrm{k}}\right) d \boldsymbol{x}$
错误分类的总惩罚为 $\sum_{k=1}^{M} \sum_{i=1}^{M} N P\left(\omega_{\mathrm{k}}\right) \lambda_{\mathrm{ki}} \int_{R_{i}} p\left(\boldsymbol{x} | \omega_{\mathrm{k}}\right) d \boldsymbol{x}=N \sum_{i=1}^{M} \int_{R_{i}}\left(\sum_{k=1}^{M} \lambda_{\mathrm{ki}} p\left(\boldsymbol{x} | \omega_{\mathrm{k}}\right) P\left(\omega_{k}\right)\right) d \boldsymbol{x}$
平均惩罚是 $r=\sum_{i=1}^{M} \int_{R_{i}}\left(\sum_{k=1}^{M} \lambda_{\mathrm{ki}} p\left(\boldsymbol{x} | \omega_{\mathrm{k}}\right) P\left(\omega_{k}\right)\right) d \boldsymbol{x}$

考虑拒绝分类
$\lambda_{k l}=\left\{\begin{array}{ll}{0} & {\text { if } l=k \text { (correct) }} \\ {1} & {\text { if } l \neq k, l \neq \mathcal{D}(\text { wrong })} \\ {d} & {\text { if } l \neq k, l=\mathcal{D}(\text { in doubt } / \text { reject })}\end{array}\right.$
拒绝分类的一般惩罚矩阵： $\omega^{*}=\left\{\begin{array}{cc}{\arg \min _{\omega} \sum_{k} \lambda_{k i} P\left(\omega_{k} | \mathbf{x}\right)} & {\text { if the min is less than } d} \\ {\mathcal{D}} & {\text { otherwise }}\end{array}\right.$

决策面和决策函数

决策面
对于 $M$ 类问题，最小化错误概率会将特征空间分为 $M$ 个区域， $R_1,R_2,\ldots$ ，若恰巧 $R_i,R_j$ 是临近的，那么把它们划分开，使错误概率最小化的决策面是 $P\left(\omega_{i} | \boldsymbol{x}\right)-P\left(\omega_{j} | \boldsymbol{x}\right)=0$
判别函数
有时不直接使用概率，而是从数学角度直接等价使用概率的函数

正态分布下的贝叶斯分类器

多元高斯分布x $l$ 维空间的多元高斯概率密度函数是 $p(\boldsymbol{x})=\frac{1}{\sqrt{|2 \pi \Sigma|}} \exp \left(-\frac{1}{2}(\boldsymbol{x}-\boldsymbol{\mu})^{T} \Sigma^{-1}(\boldsymbol{x}-\boldsymbol{\mu})\right)$
其中 $\mu$ 是 $x$ 的均值， $\Sigma$ 是 $x$ 的协方差矩阵 $\Sigma=E\left[(\boldsymbol{x}-\boldsymbol{\mu})(\boldsymbol{x}-\boldsymbol{\mu})^{T}\right]$ 。
两个例子：
例1. $\Sigma=\left[\begin{array}{cc}{15} & {0} \\ {0} & {3}\end{array}\right]$

image.png
例2.

image.png

高斯分布下的判别函数
使用判别函数 $g_{i}(\boldsymbol{x})=\ln \left(p\left(\boldsymbol{x} | \omega_{i}\right) P\left(\omega_{i}\right)\right)=\ln p\left(\boldsymbol{x} | \omega_{i}\right)+\ln P\left(\omega_{i}\right)$
在高斯分布下变为了 $g_{i}(\boldsymbol{x})=-\frac{1}{2}\left(\boldsymbol{x}-\boldsymbol{\mu}_{i}\right)^{T} \Sigma_{i}^{-1}\left(\boldsymbol{x}-\boldsymbol{\mu}_{i}\right)+\ln P\left(\omega_{i}\right)+c_{i}$
$g_{i}(\boldsymbol{x})=-\frac{1}{2} \boldsymbol{x}^{T} \Sigma_{i}^{-1} \boldsymbol{x}+\frac{1}{2} \boldsymbol{x}^{T} \Sigma_{i}^{-1} \boldsymbol{\mu}_{i}+\frac{1}{2} \boldsymbol{\mu}_{i}^{T} \Sigma_{i}^{-1} \boldsymbol{x}-\frac{1}{2} \boldsymbol{\mu}_{i}^{T} \Sigma_{i}^{-1} \boldsymbol{\mu}_{i}+\ln P\left(\omega_{i}\right)+c_{i}$ 其中 $c_i$ 为常数 $c_{i}=-(l / 2) \ln 2 \pi-(1 / 2) \ln \left|\Sigma_{i}\right|$
在 $l=2$ 的情况下，对应的决策曲线是二次曲线，此时贝叶斯分类器是二次分类器。特别的，协方差矩阵相同时，决策面 $g_i(x)-g_j(x)=0$ 变成一个超平面。

然而，概率密度函数通常是未知的，可能并非正态分布，此时就需要估计。

概率密度函数的估计

最大似然估计

$\theta_i$ 关于 $x$ 的似然函数 $p\left(\boldsymbol{x} | \omega_{i} ; \boldsymbol{\theta}_{i}\right)$ ，任务为通过一组已知特征向量来估计未知的参数 $\theta_i$ 。
最大似然估计，使似然函数取最大值 $\boldsymbol{\theta}_{M L}=\arg \max _{\boldsymbol{\theta}} \prod_{k=1}^{N} p\left(\boldsymbol{x}_{k} ; \boldsymbol{\theta}\right)$ ，为了使似然函数最大化， $\frac{\partial \prod_{k=1}^{N} p\left(\boldsymbol{x}_{k} ; \boldsymbol{\theta}\right)}{\partial \boldsymbol{\theta}}=0$ 。进一步，使用对数似然函数 $L(\boldsymbol{\theta}) \equiv \ln \prod_{k=1}^{N} p\left(\boldsymbol{x}_{k} ; \boldsymbol{\theta}\right)=\sum_{k=1}^{N} \ln p\left(\boldsymbol{x}_{k} ; \boldsymbol{\theta}\right)$ ，它关于 $\theta$ 的导数为0， $\frac{\partial L(\boldsymbol{\theta})}{\partial \boldsymbol{\theta}}=\sum_{k=1}^{N} \frac{\partial \ln p\left(\boldsymbol{x}_{k} ; \boldsymbol{\theta}\right)}{\partial \boldsymbol{\theta}}=\sum_{k=1}^{N} \frac{\mathbb{1}}{p\left(\boldsymbol{x}_{k} ; \boldsymbol{\theta}\right)} \frac{\partial p\left(\boldsymbol{x}_{k} ; \boldsymbol{\theta}\right)}{\partial \boldsymbol{\theta}}=0$ 。

混合模型

假设 $x$ 是以 $P_{j}, j=1,2, \ldots, J$ 的概率分别从 $J$ 个分布中抽取出来的。
那么未知的 $p(x)$ 可以写成多个密度函数的线性组合 $p(\boldsymbol{x})=\sum_{j=1}^{J} p(\boldsymbol{x} | j) P_{j}$ ，其中 $\sum_{j=1}^{J} P_{j}=1, \quad \int_{x} p(\boldsymbol{x} | j) d \boldsymbol{x}=1$ 。
首先要选择参数形式合适的密度函数 $p(\boldsymbol{x} | j ; \boldsymbol{\theta})$ ，然后基于一组训练样本 $x_k$ 计算未知参数 $\theta$ 和 $P_{j^{\prime}},j=1,2, \ldots, J$
然后根据参数 $\theta$ 和 $P_j$ 最大化似然函数 $\prod_{k} p\left(\boldsymbol{x}_{k} ; \boldsymbol{\theta}, P_{1}, P_{2}, \ldots, P_{J}\right)$ 。
未知参数以非线性方式进入最大化任务中，因此需要采用非线性优化迭代技术。

存在问题：

训练样本的哪个样本属于 $J$ 个分布的哪一个分布是未知的。
如果是已知的，那么最大化任务就可以分解为 $J$ 个最大似然估计任务。
这种未知使得现在的问题变成一个不完整数据集问题。一个完整的数据样本是 $y_k=(x_k,j_k)$ , $j_k$ 表示 $x_k$ 是属于第 $j_k$ 个分布的，但 $j_k$ 是未知的。

EM算法

E-step：在第(t+1)轮迭代中， $\Theta(t)$ 是已知的，这一步计算期望值 $Q(\mathbf{\Theta} ; \mathbf{\Theta}(t))=E_{j_{1}, \ldots, j_{N} | X ; \mathbf{\Theta}(t)}[L(\mathbf{E})]$
$=E_{j_{1}, \ldots, j_{N} | X, \mathbf{e}(t)}\left[\sum_{k=1}^{N} \ln \left(p\left(\boldsymbol{x}_{k} | j_{k} ; \boldsymbol{\theta}\right) P_{j_{k}}\right)\right]$
$=\sum_{k=1}^{N} E_{j_{k} | x_{k}, \mathbf{\Theta}(t)}\left[\ln \left(p\left(\boldsymbol{x}_{k} | j_{k} ; \boldsymbol{\theta}\right) P_{j_{k}}\right)\right]$
$=\sum_{k=1}^{N} \sum_{j_{k}=1}^{J} P\left(j_{k} | \boldsymbol{x}_{k} ; \boldsymbol{\Theta}(t)\right) \ln \left(p\left(\boldsymbol{x}_{k} | j_{k} ; \boldsymbol{\theta}\right) P_{j_{k}}\right)$
把 $j_k$ 换成 $j$ ， $Q(\mathbf{\Theta} ; \mathbf{\Theta}(t))=\sum_{k=1}^{N} \sum_{j=1}^{J} P\left(j | \boldsymbol{x}_{k} ; \mathbf{\Theta}(t)\right) \ln \left(p\left(\boldsymbol{x}_{k} | j ; \boldsymbol{\theta}\right) P_{j}\right)$
M-step：通过最大化期望值计算第(t+1)轮迭代的 $\Theta$ 值，即 $\Theta(t+1): \frac{\partial Q(\Theta ; \Theta(t))}{\partial \Theta}=0$ 。
求使得期望最大化的 $\Theta(t+1)^T$ ，即 $\left[\boldsymbol{\theta}(t+1)^{T}, \boldsymbol{P}(t+1)^{T}\right]^{T}$ 。
考虑约束 $P_{1}+P_{2}+\ldots+P_{J}=1$ ，利用拉格朗日乘数法可以求出 $P_{j}(t+1)=\frac{1}{N} \sum_{k=1}^{N} P\left(j | \boldsymbol{x}_{k} ; \mathbf{\Theta}(t)\right)$ 。而 $\Theta(t+1)$ 的计算依赖于具体分布。
初始估计 $\Theta(0)$ 开始迭代，直到参数稳定。

假设分布为正态分布 $p\left(\boldsymbol{x} | j ; \boldsymbol{\mu}_{j}, \Sigma_{j}\right)=\frac{1}{\sqrt{|2 \pi \Sigma|}} \exp \left(-\frac{1}{2}\left(\boldsymbol{x}-\boldsymbol{\mu}_{j}\right)^{T} \Sigma_{j}^{-1}(\boldsymbol{x}-\boldsymbol{\mu})\right)$ 。

由 $\partial Q / \partial \boldsymbol{\mu}_{j}=0 \quad \partial Q / \partial \Sigma_{j}=0$ 得 $\boldsymbol{\mu}_{j}(t+1)=\frac{\sum_{k=1}^{N} P\left(j | \boldsymbol{x}_{k} ; \mathbf{\Theta}(t)\right) \boldsymbol{x}_{k}}{\sum_{k=1}^{N} P\left(j | \boldsymbol{x}_{k} ; \mathbf{\Theta}(t)\right)}$ ， $\Sigma_{j}(t+1)=\frac{\sum_{k=1}^{N} P\left(j | \boldsymbol{x}_{k} ; \mathbf{\Theta}(t)\right)\left(\boldsymbol{x}_{k}-\boldsymbol{\mu}_{j}(t+1)\right)\left(\boldsymbol{x}_{k}-\boldsymbol{\mu}_{j}(t+1)\right)^{T}}{\sum_{k=1}^{N} P\left(j | \boldsymbol{x}_{k} ; \mathbf{\Theta}(t)\right)}$ 为进行迭代，需要计算 $P\left(j | \boldsymbol{x}_{k} ; \mathbf{\Theta}(t)\right)=\frac{p\left(\boldsymbol{x}_{k} | j ; \mathbf{\Theta}(t)\right) P_{j}(t)}{p\left(\boldsymbol{x}_{k} ; \mathbf{\Theta}(t)\right)}$
$p\left(\boldsymbol{x}_{k} ; \mathbf{\Theta}(t)\right)=\sum_{j=1}^{J} p\left(\boldsymbol{x}_{k} | j ; \mathbf{\Theta}(t)\right) P_{j}(t)$ 。

直方图

一维情况，将x轴划分为长度为 $b$ 的 $bins$ ，假设总的样本数为 $N$ ，有 $k_N$ 落在某个 $bin$ 里，那么对应的概率近似为 $P \approx K_{N} / N$ 。
若 $x'$ 为这个 $bin$ 的中心点，在这个 $bin$ 里的概率密度值近似为 $p(x) \equiv p\left(x^{\prime}\right) \approx \frac{1}{b} \frac{k_{N}}{N}, \quad\left|x-x^{\prime}\right| \leq \frac{b}{2}$ 。

核密度估计(parzen窗)

因高维不能取大小为 $b$ 的bin，把 $l$ 维空间划分为边长为 $b$ ，容积为 $b^l$ 的超立方体，令 $x_{i}, i=1,2, \ldots, N$ 为可用的特征向量。定义函数 $\phi(\boldsymbol{x})=\left\{\begin{array}{cc}{1} & {\text { for }\left|x_{j}\right| \leq 1 / 2} \\ {0} & {\text { otherwise }}\end{array}\right.$ ， $\int_{x} \phi(x) d x=1$ 。
换句话说，在以原点为中心的单位超立方体内部，这个函数等于1，在外部等于0.
那么 $x$ 处的概率密度变为 $p(x)=\frac{1}{b^{l}} \frac{1}{N} \sum_{i}^{N} \phi\left(\frac{x_{i}-x}{b}\right)$ ，即取一个以 $x$ 为中心的边长为 $b$ 的超立方体，看看有多少 $x_i$ 在这个超立方体里面。
原来的 $\phi(x)$ 是非连续的阶跃函数，现在考虑将 $\phi(\cdot)$ 改成平滑函数，它满足 $\phi(\boldsymbol{x}) \geq 0 \quad \int_{x} \phi(\boldsymbol{x}) d \boldsymbol{x}=1$ 。
高斯核 $N(0,I)$ 是一个典型的核，此时概率密度的展开为 $p(\boldsymbol{x})=\frac{1}{N} \sum_{i}^{N} \frac{1}{(2 \pi)^{\frac{l}{2}} b^{l}} \exp \left(-\frac{\left(\boldsymbol{x}_{i}-\boldsymbol{x}\right)^{T}\left(\boldsymbol{x}_{i}-\boldsymbol{x}\right)}{2 b^{2}}\right)$ ，也就是说， $p(x)$ 的估计是 $N$ 个高斯的均值，每个高斯以训练集的不同样本为中心。

在核密度估计中，围绕点 $x$ 的 $volume$ 是固定的，而落在这个 $volume$ 里的特征点数量 $k_N$ 在不同点之间是变化的。现在反过来，固定 $k_N=k$ ，而每次调节围绕 $x$ 的 $volume$ 的大小使它包含 $k$ 个点。

KNN密度估计

调节围绕 $x$ 的 $volume$ 使它包含 $k$ 个点，假设这个 $volume$ 的大小为 $V(x)$ ，概率密度的估计值可以写为 $p(\boldsymbol{x})=\frac{k}{N V(\boldsymbol{x})}$ 。
概率密度最大，即使 $V(x)$ 最小。

KNN估计变体及KNN分类器

在N个训练向量中，找出最近的k个，不管其类标注
在k个样本中，识别出属于 $\omega_i$ 的样本数 $k_i,i=1,2,\ldots,M$ 。很明显， $\Sigma_i k_i=k$ 。
假设包含这k个样本的volume大小为V，则 $\mathrm{p}\left(\mathrm{x} | \omega_{i}\right)=\mathrm{k}_{\mathrm{i}} /\left(\mathrm{N}_{\mathrm{i}} \mathrm{V}\right)$ 。
KNN分类器：
$k_i$ 是最大的，那么 $x$ 就属于 $\omega_i$ .

朴素的贝叶斯分类器

为了得到好的对概率密度函数 $p\left(\boldsymbol{x} | \omega_{\mathrm{i}}\right),i=1,\ldots,M$ 的估计结果，就要求训练集的样本数足够多。
如果一维空间里需要 $N$ 个样本，才能确保得到准确的估计，那么 $l$ 维空间就至少需要 $N^l$ 个样本。需要的样本数随着维数增大呈指数量级上升。
假设各特征分量相互独立，那么 $p\left(\boldsymbol{x} | \omega_{i}\right)=\prod_{j=1}^{l} p\left(x_{j} | \omega_{i}\right)$ 。
如果这样的话，我们只需要为每个类估计l个一维概率密度函数，为了得到好的估计， $Nl$ 个点就够了，这种独立性假设得到的分类器就是朴素贝叶斯分类器。

朴素贝叶斯分类器让我们从一个极端走向另一个极端，完全相互依赖的特征到相互独立。而贝叶斯网络让我们停留在两个极端之间的某个位置。

贝叶斯网络

贝叶斯网络：通过表示变量之间的依赖关系来表示完全联合概率分布。
概率链式规则 $p\left(x_{l}, \ldots, x_{2}, x_{1}\right)=p\left(x_{l} | x_{l-1}, \ldots, x_{1}\right) p\left(x_{l-1} | x_{l-2}, \ldots, x_{1}\right) \ldots p\left(x_{2} | x_{1}\right) p\left(x_{1}\right)$
$p(\boldsymbol{x})=p\left(x_{1}\right) \prod_{i=2}^{l} p\left(x_{i} | A_{i}\right)$
$A_{i} \subseteq\left\{x_{i-1}, x_{i-2}, \dots, x_{1}\right\}$

image.png

贝叶斯分类器

贝叶斯决策理论

决策面和决策函数

正态分布下的贝叶斯分类器

概率密度函数的估计

最大似然估计

混合模型

直方图

核密度估计(parzen窗)

KNN密度估计

KNN估计变体及KNN分类器

朴素的贝叶斯分类器

贝叶斯网络

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读