[模式分类]贝叶斯决策论

本文对应《模式分类》的第 2 章。

最小错误率贝叶斯决策

设特征向量 \(\mathbf x\in\mathbb R^d\)，属于 \(c\) 个类别 \(\{\omega_1,\ldots,\omega_c\}\) 之一。假设下述概率分布都是已知的：

• 各类别先验概率：\(P(\omega_i),\,i=1,\ldots,c\)
• 类条件概率：\(p(\mathbf x\vert\omega_i),\,i=1,\ldots,c\)

那么，如果观测到样本 \(\mathbf x\)，应该将其分到哪一类，使得错误率最小呢？

首先，根据贝叶斯公式，我们可以计算后验概率： \[ P(\omega_i\vert\mathbf x)=\frac{p(\mathbf x\vert\omega_i)P(\omega_i)}{p(\mathbf x)},\quad i=1,\ldots,c \] 一个自然的决策是选取后验概率最大的那一类： \[ \mathbf x\in\omega=\mathop{\text{argmax }}_{i=1}^c P(\omega_i\vert\mathbf x)\tag{1}\label{1} \] 事实上，这也确实是使得错误率最小的决策。因为，所谓错误率（总错误率 / 平均错误率），就是： \[ P(\text{error})=\mathbb E_{\mathbf x}[P(\text{error}\vert\mathbf x)]=\int P(\text{error}\vert\mathbf x)p(\mathbf x)\mathrm d\mathbf x \] 那么要使得 \(P(\text{error})\) 最小，只需要对每一个 \(\mathbf x\) 让 \(P(\text{error}\vert\mathbf x)\) 最小： \[ P(\text{error}\vert\mathbf x)=1-P(\omega_i\vert\mathbf x)\quad\text{if we decide }\mathbf x\in\omega_i \] 显然，我们的决策应该是找最小的 \(1-P(\omega_i\vert\mathbf x)\)，整理一下也就是 \(\eqref{1}\) 式。

我们可以将这个过程形式化为以下模式：对每个 \(\mathbf x\)，计算判别函数 \(g_i(\mathbf x),\,i=1,\ldots,c\)，如果： \[ g_k(\mathbf x)=\max_{i=1}^c g_i(\mathbf x) \] 我们就将 \(\mathbf x\) 分类为 \(\omega_k\). 这就是一个分类器。

对于 \(\eqref{1}\) 式而言，其判别函数就是后验概率 \(g_i(\mathbf x)=P(\omega_i\vert\mathbf x)\). 然而，后验概率的分母部分（即归一化因子）\(p(\mathbf x)\) 是个积分/求和，一般难以计算。不过，注意到 \(p(\mathbf x)\) 其实与决策无关——不管哪个类都有这一项，所以完全可以丢掉。另外，判别函数的单增函数并不会改变判别结果，所以事实上，以下选择都是可行的判别函数： \[ \begin{align} &g_i(\mathbf x)=P(\omega_i\vert\mathbf x)\tag{2}\label{2}\\ &g_i(\mathbf x)=p(\mathbf x\vert\omega_i)P(\omega_i)\tag{3}\label{3}\\ &g_i(\mathbf x)=\ln p(\mathbf x\vert\omega_i)+\ln P(\omega_i)\tag{4}\label{4} \end{align} \] 实际应用中，哪种形式方便就用哪一种。

有了判别函数，任取两类 \(i,j\)，那么 \(g_i(\mathbf x)=g_j(\mathbf x)\) 就是决策面方程——决策面的两边分属 \(\omega_i\) 和 \(\omega_j\). 当判别函数是关于 \(\mathbf x\) 的线性函数时，决策面为一个超平面（反过来不成立，若决策面是超平面，判别函数并不一定是线性的，非线性的判别函数的交面也可以是超平面）。

特别地，在两类情形下，我们的判决规则就是【若 \(P(\omega_1\vert\mathbf x)>P(\omega_2\vert\mathbf x)\)，则 \(\mathbf x\in\omega_1\)；否则 \(\mathbf x\in\omega_2\)】。去掉分母并稍作移项，得：当 \[ l(\mathbf x)=\frac{p(\mathbf x\vert\omega_1)}{p(\mathbf x\vert\omega_2)}>\frac{P(\omega_2)}{P(\omega_1)} \] 时，判决 \(\mathbf x\in\omega_1\)；否则 \(\mathbf x\in\omega_2\). 这里 \(l(\mathbf x)\) 称作似然比。

最小风险贝叶斯决策

在一些实际问题中，分类错误导致的风险是不同的。自动驾驶汽车没能检测出障碍物的风险很大（车毁人亡），但误检出障碍物的风险就小很多（无非就是莫名其妙地刹车）。设 \(\{\alpha_1,\ldots,\alpha_a\}\) 表示 \(a\) 种行动，风险函数 \(\lambda(\alpha_i\vert\omega_j)\) 表示在类别为 \(\omega_j\) 时采取行动 \(\alpha_i\) 的风险，简记作 \(\lambda_{ij}\). 我们的目标从最小化错误率变成了最小化风险。事实上，如果定义行动 \(\alpha_i\) 表示判决类别为 \(\omega_i\)，那么最小化错误率可以看作是在最小化 0-1 风险： \[ \lambda(\alpha_i\vert\omega_j)=\begin{cases}0&i=j\\1&i\neq j\end{cases}\quad\quad i,j=1,\ldots,c \] 一般地，给定 \(\mathbf x\)，采取各个动作的条件风险为： \[ R(\alpha_i\vert\mathbf x)=\sum_{j=1}^c\lambda(\alpha_i\vert\omega_j)P(\omega_j\vert\mathbf x),\quad i=1,\ldots,a\tag{5}\label{5} \] 设对每个 \(\mathbf x\)，\(\alpha(\mathbf x)\) 为采取的行动，那么总风险 / 平均风险就是： \[ R=\mathbb E_\mathbf x[R(\alpha(\mathbf x)\vert\mathbf x)]=\int R(\alpha(\mathbf x)\vert\mathbf x)p(\mathbf x)\mathrm d\mathbf x \] 为了让 \(R\) 最小，只需要对每个 \(\mathbf x\) 让 \(R(\alpha(\mathbf x)\vert\mathbf x)\) 最小。显然，我们的决策是选取使得条件风险最小的那个动作： \[ \alpha(\mathbf x)=\mathop{\text{argmin }}_{i=1}^aR(\alpha_i\vert\mathbf x)\tag{6}\label{6} \]

特别地，考察两类情形，我们的判决规则就是【若 \(R(\alpha_1\vert\mathbf x)<R(\alpha_2\vert\mathbf x)\)，则 \(\alpha(\mathbf x)=\alpha_1\)；否则 \(\alpha(\mathbf x)=\alpha_2\)】。代入 \(\eqref{5}\) 式展开得： \[ R(\alpha_1\vert\mathbf x)<R(\alpha_2\vert\mathbf x)\implies\lambda_{11}P(\omega_1\vert\mathbf x)+\lambda_{12}P(\omega_2\vert\mathbf x)<\lambda_{21}P(\omega_1\vert\mathbf x)+\lambda_{22}P(\omega_2\vert\mathbf x) \] 由于一般而言分类错误的代价比正确的代价高，所以我们可以合理地假设 \(\lambda_{11}<\lambda_{21},\,\lambda_{22}<\lambda_{12}\)，那么上式最终可以化简为：当 \[ l(\mathbf x)=\frac{p(\mathbf x\vert\omega_1)}{p(\mathbf x\vert\omega_2)}>\frac{P(\omega_2)}{P(\omega_1)}\cdot\frac{\lambda_{12}-\lambda_{22}}{\lambda_{21}-\lambda_{11}} \] 时，取 \(\alpha(\mathbf x)=\alpha_1\)；否则 \(\alpha(\mathbf x)=\alpha_2\).

例子：正态分布

上面的讨论只假定 \(P(\omega_i)\) 和 \(p(\mathbf x\vert\omega_i)\) 是已知的，但没有给出具体的形式，所以这一节我们计算一下各类条件概率密度函数为多元正态分布的情形，即： \[ p(\mathbf x\vert\omega_i)=\mathcal N(\boldsymbol\mu_i,\Sigma_i) \] 那么在最小错误率决策框架下，根据 \(\eqref{4}\) 式，各判别函数为： \[ g_i(\mathbf x)=-\frac{1}{2}(\mathbf x-\boldsymbol\mu_i)^T\Sigma_i^{-1}(\mathbf x-\boldsymbol\mu_i)-\frac{d}{2}\ln(2\pi)-\frac{1}{2}\ln |\Sigma_i|+\ln P(\omega_i)\tag{7}\label{7} \] 我们下面继续分三种情形讨论。

情形一：\(\Sigma_i=\sigma^2\mathbf I\)

所有类都服从各向同性、方差相同的正态分布，判别函数 \(\eqref{7}\) 式可以简化为： \[ g_i(\mathbf x)=-\frac{\Vert\mathbf x-\boldsymbol\mu_i\Vert_2^2}{2\sigma^2}+\ln P(\omega_i)\tag{8}\label{8} \] 这看起来是 \(\mathbf x\) 的二次型，但是二次项 \(\mathbf x^T\mathbf x\) 对各类其实是相同的，对决策并没有作用，因此可以丢掉，于是 \(\eqref{8}\) 式简化为了一个线性判别函数： \[ \begin{align} &g_i(\mathbf x)=\mathbf w_i^T\mathbf x+w_{i0}\\ \text{where}\quad &\mathbf w_i=\frac{1}{\sigma^2}\boldsymbol\mu_i\\ &w_{i0}=-\frac{1}{2\sigma^2}\boldsymbol\mu_i^T\boldsymbol\mu_i+\ln P(\omega_i) \end{align}\tag{9}\label{9} \] 那么决策面方程 \(g_i(\mathbf x)=g_j(\mathbf x)\) 为： \[ \begin{align} &\mathbf w^T(\mathbf x-\mathbf x_0)=0\\ \text{where}\quad &\mathbf w=\boldsymbol\mu_i-\boldsymbol\mu_j\\ &\mathbf x_0=\frac{1}{2}(\boldsymbol\mu_i+\boldsymbol\mu_j)-\frac{\sigma^2}{\Vert\boldsymbol\mu_i-\boldsymbol\mu_j\Vert^2_2}\ln\frac{P(\omega_i)}{P(\omega_j)}(\boldsymbol\mu_i-\boldsymbol\mu_j) \end{align} \] 这是一个超平面，法向量为 \(\mathbf w\)，即中心点的连线。若先验概率是相等的，\(P(\omega_i)=P(\omega_j)\)，超平面过连线中点；否则，超平面会朝一侧偏移。

情形二： \(\Sigma_i=\Sigma\)

所有类的协方差矩阵相同，判别函数 \(\eqref{7}\) 式可以简化为： \[ g_i(\mathbf x)=-\frac{1}{2}(\mathbf x-\boldsymbol\mu_i)^T\Sigma^{-1}(\mathbf x-\boldsymbol\mu_i)+\ln P(\omega_i)\tag{10}\label{10} \] 同理二次项 \(\mathbf x^T\Sigma^{-1}\mathbf x\) 可以丢掉，因此 \(\eqref{10}\) 式依旧简化为了一个线性判别函数： \[ \begin{align} &g_i(\mathbf x)=\mathbf w_i^T\mathbf x+w_{i0}\\ \text{where}\quad &\mathbf w_i=\Sigma^{-1}\boldsymbol\mu_i\\ &w_{i0}=-\frac{1}{2}\boldsymbol\mu_i^T\Sigma^{-1}\boldsymbol\mu_i+\ln P(\omega_i) \end{align}\tag{11}\label{11} \] 那么决策面方程 \(g_i(\mathbf x)=g_j(\mathbf x)\) 为： \[ \begin{align} &\mathbf w^T(\mathbf x-\mathbf x_0)=0\\ \text{where}\quad&\mathbf w=\Sigma^{-1}(\boldsymbol\mu_i-\boldsymbol\mu_j)\\ &\mathbf x_0=\frac{1}{2}(\boldsymbol\mu_i+\boldsymbol\mu_j)-\frac{1}{(\boldsymbol\mu_i-\boldsymbol\mu_j)^T\Sigma^{-1}(\boldsymbol\mu_i-\boldsymbol\mu_j)}\ln\frac{P(\omega_i)}{P(\omega_j)}(\boldsymbol\mu_i-\boldsymbol\mu_j) \end{align} \] 这也是一个超平面，但与上一种情形不同的是，其法向量 \(\mathbf w\) 不再朝着 \(\boldsymbol\mu_i-\boldsymbol\mu_j\) 方向，而是有一定的旋转（\(\Sigma^{-1}\) 的作用）。不过，当先验概率相等时，超平面依旧过中心点连线的中点；否则，超平面朝一侧偏移。

情形三：\(\Sigma_i\) 任意

判别函数 \(\eqref{7}\) 式只能丢掉常数项，依旧是一个二次型： \[ \begin{align} &g_i(\mathbf x)=\mathbf x^T W_i\mathbf x+\mathbf w_i^T\mathbf x+w_{i0}\\ \text{where}\quad &W_i=-\frac{1}{2}\Sigma_i^{-1}\\ &\mathbf w_i=\Sigma_i^{-1}\boldsymbol\mu_i\\ &w_{i0}=-\frac{1}{2}\boldsymbol\mu_i^T\Sigma_i^{-1}\boldsymbol\mu_i-\frac{1}{2}\ln|\Sigma_i|+\ln P(\omega_i) \end{align}\tag{12}\label{12} \] 此时的决策面方程将是超二次曲面——超平面、超平面对、超球体、超椭球体、超抛物面、超双曲面等。

丢失特征和噪声特征

设 \(\mathbf x=[\mathbf x_g,\mathbf x_b]\)，其中 \(\mathbf x_g\) 表示已知或完好的特征，\(\mathbf x_b\) 表示未知或丢失的特征，那么根据已知的特征表示后验概率为： \[ \begin{align} P(\omega_i\vert\mathbf x_g)&=\frac{p(\omega_i,\mathbf x_g)}{p(\mathbf x_g)}=\frac{\int p(\omega_i,\mathbf x_g,\mathbf x_b)\mathrm d\mathbf x_b}{\int p(\mathbf x_g,\mathbf x_b)\mathrm d\mathbf x_b}\\ &=\frac{\int P(\omega_i\vert\mathbf x_g,\mathbf x_b)p(\mathbf x_g,\mathbf x_b)\mathrm d\mathbf x_b}{\int p(\mathbf x_g,\mathbf x_b)\mathrm d\mathbf x_b}\\ &=\frac{\int g_i(\mathbf x)p(\mathbf x)\mathrm d\mathbf x_b}{\int p(\mathbf x)\mathrm d\mathbf x_b} \end{align}\tag{13}\label{13} \] 分子分母都相当于在变量 \(\mathbf x_b\) 上进行“边缘化”。

进一步地，如果 \(\mathbf x_b\) 表示的是受到噪声干扰的特征，其真实值为 \(\mathbf x_t\)，噪声模型记作 \(p(\mathbf x_b\vert\mathbf x_t)\). 注意当真实特征值 \(\mathbf x_t\) 已知时 \(\mathbf x_b\) 与 \(\omega_i\) 和 \(\mathbf x_g\) 无关。那么，后验分布为： \[ \begin{align} P(\omega_i\vert\mathbf x_g,\mathbf x_b)&=\frac{p(\omega_i,\mathbf x_g,\mathbf x_b)}{p(\mathbf x_g,\mathbf x_b)}=\frac{\int p(\omega_i,\mathbf x_g,\mathbf x_b,\mathbf x_t)\mathrm d\mathbf x_t}{\int p(\mathbf x_g,\mathbf x_b,\mathbf x_t)\mathrm d\mathbf x_t}\\ &=\frac{\int P(\omega_i\vert\mathbf x_g,\mathbf x_b,\mathbf x_t)p(\mathbf x_b\vert\mathbf x_g,\mathbf x_t)p(\mathbf x_g,\mathbf x_t)\mathrm d\mathbf x_t}{\int p(\mathbf x_b\vert\mathbf x_g,\mathbf x_t)p(\mathbf x_g,\mathbf x_t)\mathrm d\mathbf x_t}\\ &=\frac{\int P(\mathbf \omega_i\vert\mathbf x_g,\mathbf x_t)p(\mathbf x_b\vert\mathbf x_t)p(\mathbf x_g,\mathbf x_t)\mathrm d\mathbf x_t}{\int p(\mathbf x_b\vert\mathbf x_t)p(\mathbf x_g,\mathbf x_t)\mathrm d\mathbf x_t}\\ &=\frac{\int g_i(\mathbf x)p(\mathbf x)p(\mathbf x_b\vert\mathbf x_t)\mathrm d\mathbf x_t}{\int p(\mathbf x)p(\mathbf x_b\vert\mathbf x_t)\mathrm d\mathbf x_t} \end{align}\tag{14}\label{14} \] 对比 \(\eqref{13}\) 式，\(\eqref{14}\) 式对被积函数按噪声模型进行了加权。在极端情况下，\(p(\mathbf x_b\vert\mathbf x_t)\) 在整个空间为 \(1\)，即 \(\mathbf x_b\) 不包含任何关于 \(\mathbf x_t\) 的信息，那么这个特征相当于丢失了，\(\eqref{14}\) 式也就退化到了 \(\eqref{13}\) 式。