贝叶斯决策理论（理论部分）

此Markdown不支持mathjax，所以公式乱码，请到个人博客:http://happykai.cn/2018/06/30/MIT-PatternRecognition3/，进行阅读

简介

通常来讲，在解决一个分类问题时，我们的思维过程可以分为下面这三个部分：

Measurement Space ---> Feature Space ---> Decision Space

先思考如何测量衡量（可以理解为抽象这个问题并通过某种方式得到相应的数据），然后根据测量得到的结果提取特征，最后作出决策，有时Measurement Space和Feature Space是和在一起的。比如识别“B”和“8”，可能立刻马上想到的最简单的方法是：把“B”和“8”放入一个长方形，观察可以得到，“B”的左边竖线是平行于长方形的左边框的，而“8”不是，所以选取长方形左边框上一系列点，过这些做垂线段，找到与B/8的左边的交点，测量这一些列垂线段的长度（This is Measurement Space），如果长度几乎一样（This is Feature Space），则为B（This is Decision Space），否则为8。

<!-- more -->

如果给出了下面两个cases：

1. 条件概率密度函数和先验概率——measurement space & feature space
2. 训练所需的样本点——where we get our decision space

那么就可以考虑使用贝叶斯方法做出分类决策。

贝叶斯决策理论（Bayesian decision theory）是一种根据概率进行决策的理论，在模式识别中，将分类当作决策进行预测。

贝叶斯决策规则（简单版）

• M个类
• 给出（算出）类条件密度函数（class conditional density function） $$p(x|\omega_1), p(x|\omega_2), \dots , p(x|\omega_M), x \in R^n$$
• 给出（算出）先验概率$P(\omega_1), P(\omega_2), \dots, P(\omega_M)$

$$0 < P(\omega_i) < 1, \forall i = 1,2, \dots, M$$

$$\sum_{i=1}^MP(\omega_i)=1$$

• 如果$p(x|\omega_i)P(\omega_i)\geq p(x|\omega_j)P(\omega_j), \forall j \neq i$， 则认为$x$是$\omega_i$类，为什么呢？后面解释
• 最好的决策是：最小化错分类的概率，前提是所有错误的权重（代价）相等，否则此条不适用。

NOTE:

条件概率用小写p表示，先验概率用大写P表示。

结合实例理解

理解公式

我们用一个分类两种鱼的例子来说明贝叶斯规则以及它的合理性。

假设有两种鱼sea bass和salmon，随机取一条鱼，我们会如何猜测呢？在什么都不知道的情况下，我们当然会随机猜测，但是如果此时给你一份统计数据，告诉你这片海域60%是sea bass，40%是salmon，此时你会怎么猜测呢？当然猜sea bass了。其实这里的60%和40%就是先验概率，用大写字母P表示。在这种情况下，我们的决策规则是：$$if\ P(sea \ bass)>P(salmon),\ then\ sea\ bass, \ otherwise \ salmon$$

猜一条鱼的时候，我们可以采用上面的方式猜，但是如果接下来的100条鱼都让你猜测，你还会用同样的决策规则吗？显然不会。那么有没有什么更聪明的方法呢？有。

我们可以探索更多的特征来辅助决策，增加我们决策的依据。

假如有人给我们提供了sea bass和salmon的光泽度密度函数，光泽度我们用$x$来表示，即给我们提供了$p(x|sea\ bass)$和$p(x|salmon)$。

现有一条鱼，经过测量，光泽度是5，那么我们怎么猜呢？我们要猜$p(sea\ bass|x=5)$和$p(salmon|x=5)$的概率，谁大就猜谁，这就是我们的决策策略（有同学会有疑问，怎么这个决策策略好像和第二部分写的不太一样？没关系，一会儿解答）。

ok我们现在问题抽象的已经很明确了——要计算$p(sea\ bass|x=5)$和$p(salmon|x=5)$的概率。想想我们已知的有哪些？首先我们知道先验概率：$P(sea\ bass)$和$P(salmon)$, 其次我们知道每种鱼的光泽度分布：$p(x|sea\ bass)$和$p(x|salmon)$。

ok，以计算$p(sea bass|x)$为例：

• (1): $p(sea\ bass|x) = p(sea\ bass, x) / p(x)$
• (2): $p(x|sea\ bass) = p(x,sea\ bass) / P(sea\ bass)$
• (3): 由(2)得：$$p(sea\ bass\ ,\ x) = p(x|sea\ bass) * P(sea\ bass)$$
• (4): 把(3)带入(1)得：$$p(sea\ bass|x) = p(x|sea\ bass) * P(sea\ bass) / p(x)$$

使用上述方法就可以计算出p(sea bass|x)的概率，p(sea bass|x)同理，如此就可以给出x=5时候的猜测。

上述计算公式(4)就是贝叶斯公式，通用写法为：

$$P\left(\omega{j} | x \right) = \frac{p\left(x|\omega{j}\right)P\left(\omega_{j}\right)}{p\left(x\right)}$$

其中$\omega$代表某个类，$x$代表某个特征，在这个二分类问题中：

$$p(x)=\sum_{j=1}^2p(x|\omega_j)P(\omega_j)$$

看这个公式，所有类里，$p(x)$是一样的，所以我们只要比较$p(x|\omega_j)P(\omega_j)$的大小就可以对不对，这就是我们第二部分写的贝叶斯决策规则的由来。

贝叶斯公式也可以用英文来描述：

$$

posterior = \dfrac {likelihood*prior}{evidence}

$$

所以贝叶斯公式将先验概率转换成了后验概率，式子中的evidence可以当作一个比例因子（scale factor），来确保posterior的和为1.

理解错误（代价）

依然是上例，如果我们猜是sea bass，可想而知，我们的错误率是$p(salmon|x)$,否则错误率是$p(sea \ bass|x)$。用公式表达为

$$

P(error | x)=

\begin{cases}

P(salmon|x), &\text{if we decide sea bass} &\

P(sea \ bass|x), &\text{if we decide salmon}

\end{cases}

$$

在第二部分贝叶斯决策规则的最后一条写道：最好的决策是最小化错误率，也就是说，我们要最小化平均错误率。

因为平均错误率由：

$$

P(error)=\int{-\infty}^{+\infty}P(error,x)dx=\int{-\infty}^{+\infty}P(error|x)p(x)dx

$$

得出，所以我们只要对每个x，尽可能最小化$P(error|x)$，这样积分就会变小。因此，错误率公式可以写作$P(error | x)=minP(\omega_1|x),P(\omega_2|x)$

贝叶斯理论——连续特征

上面到情况是假设每个错误的权重（这个权重是指，比如银行猜测一个人是否是歹徒，有两种错误，一种是其实是歹徒但是猜成了不是，另一种是其实不是歹徒但是猜成了是，这种情况下，我们宁可第二种错误发生，也不希望第一种错误发生，所以这就产生了每个错误的权重）一样，现在我们从四个方面对贝叶斯决策理论进行泛化：

• 泛化到多个特征
• 泛化到多个类
• 泛化到除了对类进行决策外还能有其他行为，比如：拒绝决策
• 将错误率泛化到损失函数（代价函数）

前三个泛化不难理解，第四个泛化适用于第二部分的最后一条提到的“每个错误的权重（代价）不一样”的情况。

我们用$\omega{1},\omega{2},...,\omega{c}$表示$c$个类，用$\alpha{1}, \alpha{2}, ...,\alpha{a}$表示可以采取的a个动作(其实这个动作就可以理解为猜测，比如$\alpha1$代表猜这个东西的类为$\omega_1$)。当实际为$\omega{j}$，行动为$\alpha{i}$时(也就是猜成$\omega_i$)，损失函数为$\lambda\left(\alpha{i}|\omega{j}\right)$。特征向量$\overrightarrow x$表示一个$d$维的随机向量，$p(\overrightarrow x|\omega{j})$表示$x$的条件密度函数。$P(\omega{j})$表示$\omega{j}$的先验概率。则后验概率可以用贝叶斯公式计算出来：

$$P\left(\omega{j} | \overrightarrow x \right) = \frac{p\left(\overrightarrow x|\omega{j}\right)P\left(\omega_{j}\right)}{p\left(\overrightarrow x\right)}$$

其中，$p(\overrightarrow x)$为：

$$

p(\overrightarrow x)=\sum^c_{j=1}p(\overrightarrow x|\omega_j)P(\omega_j)

$$

假设我们针对一个具体的特征向量$\overrightarrow x$,采取行动$\alpha_i$(即猜类别为$\omega_i$),而实际类别是$\omega_j$,则损失函数为$\lambda(\alpha_i|\omega_j)$。因为后验概率为$P(\omega_j|\overrightarrow x)$, 所以采取行动$\alpha_i$的损失为

$$

R(\alphai|\overrightarrow x)=\sum^c{j=1}\lambda(\alpha_i|\omega_j)P(\omega_j|\overrightarrow x)

$$

在决策理论的术语中，可预期的损失叫做风险$risk$，$R(\alpha_i|\overrightarrow x)$叫做条件风险$conditional\ risk$。

我们现在根据整体的risk来优化贝叶斯决策规则，也就是说，在所有错误的权重不相等的情况下， 我们采取使整体风险最小的行动。

为了得到好的结果，我们需要最小化整体风险，即对每个x都采取条件风险最小的$action$，用$\alpha(x)$表示，最终使整体风险：

$$

R=\int R(\alpha(\overrightarrow x)|\overrightarrow x)p(\overrightarrow x)\ d\overrightarrow x

$$

最小化。

可想而知，如果对每个$\overrightarrow x$，$R(\alpha(\overrightarrow x)|\overrightarrow x)$都尽可能小，那么整体风险就会最小，也就是说，计算：

$$

R(\alpha(\overrightarrow x)|\overrightarrow x)=\sum_{j=1}^c\lambda(\alpha_i|\omega_i)P(\omega_j|\overrightarrow x), \forall i=1,2, ..., a

$$

采取使其最小的行动$\alpha_i$。

最小化的整体风险被称为贝叶斯风险$Bayes\ risk$，用$R^* $表示。



二分类问题

我们现在考虑一个二分类问题。我们用$\alpha1$表示猜测为$\omega_1$，$\alpha_2$表示猜测为$\omega_2$。为了符号简洁，我们用$\lambda{ij}=\lambda(\alpha_i|\omega_j)$表示实际是$\omega_j$却猜成$\alpha_i$的损失。根据条件风险的公式我们可以得到

$$

R(\alpha1|\overrightarrow x) = \lambda{11}P(\omega1|\overrightarrow x) + \lambda{12}P(\omega_2|\overrightarrow x)

$$

以及

$$

R(\alpha2|\overrightarrow x) = \lambda{21}P(\omega1|\overrightarrow x) + \lambda{22}P(\omega_2|\overrightarrow x)

$$

我们的规则是，采取风险最小的行动，即猜做$\omega_1$如果$R(\alpha_1|\overrightarrow x) < R(\alpha_2|\overrightarrow x)$，否则$\omega_2$。

有很多方式可以表示这一规则，各有优势。

1. 猜做$\omega1$如果： $$ (\lambda{21}-\lambda{11})P(\omega_1|\overrightarrow x)>(\lambda{12}-\lambda{22})P(\omega_2|\overrightarrow x) $$ 一般来讲，猜错的损失要大于猜对的损失，所以$(\lambda{21}-\lambda{11})$和$(\lambda{12}-\lambda{22})$都大于0，因此我们的决定就更依赖于后验概率，根据贝叶斯公式，可以得到 $$ (\lambda{21}-\lambda{11})p(\overrightarrow x|\omega_1)P(\omega_1)>(\lambda{12}-\lambda_{22})p(\overrightarrow x|\omega_2)P(\omega_2) $$ 变成这样就和上面提到的贝叶斯决策理论（简单版）一样了。
2. 猜做$\omega1$如果： $$ \dfrac{p(\overrightarrow x|\omega_1)}{p(\overrightarrow x|\omega_2)}>\dfrac{\lambda{12}-\lambda{22}}{\lambda{21}-\lambda_{11}}\dfrac{P(\omega_2)}{P(\omega_1)} $$ 此公式是另一个变换方式。这个公式侧重x的概率密度，我们可以把$p(\overrightarrow x|\omega_j)$想象为$\omega_j$的函数（如，似然函数likelihood function），然后产生了似然比（likelihood radio）$p(\overrightarrow x|\omega_1)/p(\overrightarrow x|\omega_2)$。因此贝叶斯规则可以被解释成如果似然比超过不依赖于x的某阈值，则猜做$\omega_1$。

参考文献

• MIT课程指定的Reading：Duda, Richard O., Peter E. Hart, and David G. Stork. Pattern Classification. New York, NY: John Wiley & Sons, 2000. ISBN: 9780471056690.
• 印度的讲的贼好的MOOC第三节