原文地址:http://happykai.cn/2018/06/30/MIT-PatternRecognition3/，簡書沒有系統(tǒng)性的目錄之分，容易使知識變成一盤散沙，因此今后將逐步轉(zhuǎn)移至個人博客http://happykai.cn，在個人博客中系統(tǒng)地搭建知識體系。
手機版不支持mathjax，所以公式亂碼，如果您使用手機閱讀，請到個人博客。
簡介
通常來講，在解決一個分類問題時，我們的思維過程可以分為下面這三個部分：
Measurement Space ---> Feature Space ---> Decision Space
先思考如何測量衡量（可以理解為抽象這個問題并通過某種方式得到相應的數(shù)據(jù)），然后根據(jù)測量得到的結(jié)果提取特征，最后作出決策，有時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。
如果給出了下面兩個cases：
- 條件概率密度函數(shù)和先驗概率——measurement space & feature space
- 訓練所需的樣本點——where we get our decision space
那么就可以考慮使用貝葉斯方法做出分類決策。
貝葉斯決策理論（Bayesian decision theory）是一種根據(jù)概率進行決策的理論，在模式識別中，將分類當作決策進行預測。
貝葉斯決策規(guī)則（簡單版）
- M個類
- 給出（算出）類條件密度函數(shù)（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表示。
結(jié)合實例理解
理解公式
我們用一個分類兩種魚的例子來說明貝葉斯規(guī)則以及它的合理性。
假設有兩種魚sea bass和salmon，隨機取一條魚，我們會如何猜測呢？在什么都不知道的情況下，我們當然會隨機猜測，但是如果此時給你一份統(tǒng)計數(shù)據(jù)，告訴你這片海域60%是sea bass，40%是salmon，此時你會怎么猜測呢？當然猜sea bass了。其實這里的60%和40%就是先驗概率，用大寫字母P表示。在這種情況下，我們的決策規(guī)則是：if\ P(sea \ bass)>P(salmon),\ then\ sea\ bass, \ otherwise \ salmon
猜一條魚的時候，我們可以采用上面的方式猜，但是如果接下來的100條魚都讓你猜測，你還會用同樣的決策規(guī)則嗎？顯然不會。那么有沒有什么更聰明的方法呢？有。
我們可以探索更多的特征來輔助決策，增加我們決策的依據(jù)。
假如有人給我們提供了sea bass和salmon的光澤度密度函數(shù)，光澤度我們用x來表示，即給我們提供了p(x|sea\ bass)和p(x|salmon)。
現(xiàn)有一條魚，經(jīng)過測量，光澤度是5，那么我們怎么猜呢？我們要猜p(sea\ bass|x=5)和p(salmon|x=5)的概率，誰大就猜誰，這就是我們的決策策略（有同學會有疑問，怎么這個決策策略好像和第二部分寫的不太一樣？沒關系，一會兒解答）。
ok我們現(xiàn)在問題抽象的已經(jīng)很明確了——要計算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)的大小就可以對不對，這就是我們第二部分寫的貝葉斯決策規(guī)則的由來。
貝葉斯公式也可以用英文來描述：
posterior = \dfrac {likelihood*prior}{evidence}
所以貝葉斯公式將先驗概率轉(zhuǎn)換成了后驗概率，式子中的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}
在第二部分貝葉斯決策規(guī)則的最后一條寫道：最好的決策是最小化錯誤率，也就是說，我們要最小化平均錯誤率。
因為平均錯誤率由：
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)=min[P(\omega_1|x),P(\omega_2|x)]
貝葉斯理論——連續(xù)特征
上面到情況是假設每個錯誤的權重（這個權重是指，比如銀行猜測一個人是否是歹徒，有兩種錯誤，一種是其實是歹徒但是猜成了不是，另一種是其實不是歹徒但是猜成了是，這種情況下，我們寧可第二種錯誤發(fā)生，也不希望第一種錯誤發(fā)生，所以這就產(chǎn)生了每個錯誤的權重）一樣，現(xiàn)在我們從四個方面對貝葉斯決策理論進行泛化：
- 泛化到多個特征
- 泛化到多個類
- 泛化到除了對類進行決策外還能有其他行為，比如：拒絕決策
- 將錯誤率泛化到損失函數(shù)（代價函數(shù)）
前三個泛化不難理解，第四個泛化適用于第二部分的最后一條提到的“每個錯誤的權重（代價）不一樣”的情況。
我們用\omega_{1},\omega_{2},...,\omega_{c}表示c個類，用\alpha_{1}, \alpha_{2}, ...,\alpha_{a}表示可以采取的a個動作(其實這個動作就可以理解為猜測，比如\alpha_1代表猜這個東西的類為\omega_1)。當實際為\omega_{j}，行動為\alpha_{i}時(也就是猜成\omega_i)，損失函數(shù)為\lambda\left(\alpha_{i}|\omega_{j}\right)。特征向量\overrightarrow x表示一個d維的隨機向量，p(\overrightarrow x|\omega_{j})表示x的條件密度函數(shù)。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,則損失函數(shù)為\lambda(\alpha_i|\omega_j)。因為后驗概率為P(\omega_j|\overrightarrow x), 所以采取行動\alpha_i的損失為
R(\alpha_i|\overrightarrow x)=\sum^c_{j=1}\lambda(\alpha_i|\omega_j)P(\omega_j|\overrightarrow x)
在決策理論的術語中，可預期的損失叫做風險risk，R(\alpha_i|\overrightarrow x)叫做條件風險conditional\ risk。
我們現(xiàn)在根據(jù)整體的risk來優(yōu)化貝葉斯決策規(guī)則，也就是說，在所有錯誤的權重不相等的情況下， 我們采取使整體風險最小的行動。
為了得到好的結(jié)果，我們需要最小化整體風險，即對每個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^*表示。
二分類問題
我們現(xiàn)在考慮一個二分類問題。我們用\alpha_1表示猜測為\omega_1，\alpha_2表示猜測為\omega_2。為了符號簡潔，我們用\lambda_{ij}=\lambda(\alpha_i|\omega_j)表示實際是\omega_j卻猜成\alpha_i的損失。根據(jù)條件風險的公式我們可以得到
R(\alpha_1|\overrightarrow x) = \lambda_{11}P(\omega_1|\overrightarrow x) + \lambda_{12}P(\omega_2|\overrightarrow x)
以及
R(\alpha_2|\overrightarrow x) = \lambda_{21}P(\omega_1|\overrightarrow x) + \lambda_{22}P(\omega_2|\overrightarrow x)
我們的規(guī)則是，采取風險最小的行動，即猜做\omega_1如果R(\alpha_1|\overrightarrow x) < R(\alpha_2|\overrightarrow x)，否則\omega_2。
有很多方式可以表示這一規(guī)則，各有優(yōu)勢。
猜做\omega_1如果：
(\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，因此我們的決定就更依賴于后驗概率，根據(jù)貝葉斯公式，可以得到
(\lambda_{21}-\lambda_{11})p(\overrightarrow x|\omega_1)P(\omega_1)>(\lambda_{12}-\lambda_{22})p(\overrightarrow x|\omega_2)P(\omega_2)
變成這樣就和上面提到的貝葉斯決策理論（簡單版）一樣了。猜做\omega_1如果：
\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)}
此公式是另一個變換方式。這個公式側(cè)重x的概率密度，我們可以把p(\overrightarrow x|\omega_j)想象為\omega_j的函數(shù)（如，似然函數(shù)likelihood function），然后產(chǎn)生了似然比（likelihood radio）p(\overrightarrow x|\omega_1)/p(\overrightarrow x|\omega_2)。因此貝葉斯規(guī)則可以被解釋成如果似然比超過不依賴于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第三節(jié)
