生成式學習演算法（四）之-樸素貝葉斯分類器

生成式學習演算法（四）之—-樸素貝葉斯分類器

2019 年 10 月 3 日
筆記

樸素貝葉斯分類器（演算法）與樸素貝葉斯假設

在高斯判別分析模型（GDA）中，特徵向量$ x$ 是連續實值向量。現在我們來討論分量$ x_j$ 取離散值的貝葉斯樸素貝葉斯模型。
在文本分類問題中，有一個問題是分出一個郵件是（(y=1) ）或者不是（(y=1) ）垃圾郵件。我們的訓練數據集是一些標好是否是垃圾郵件的郵件。現在我們首先需要把每個郵件表示成特徵向量的形式。
假設我們有一個固定長度的詞表。這個詞表不包括一些在每個文檔中都出現的，高頻的對判別垃圾郵件沒有太大作用的停用詞。然後對於每一個郵件。可以用一個長度為詞表長度的0，1向量來表示。向量的分量$ x_j$ 就表示這個詞表中的第$ j$項所代表的單詞是否出現在這個郵件中，0表示沒有出現，1表示出現。

把每個郵件表示成0，1特徵向量$ x$ 後，現在我們要對條件概率(p(x | y)) 進行建模。肯定不能用多項分布來建模，因為參數量太大了。比如我們的詞表長度為5000，特徵向量的可能結果有$ 2^{5000}$ 種。用多項分布則需要確定$ 2^{5000}-1$ 個參數。因此，我們需要對模型做出一些簡化假設。
樸素貝葉斯假設就是其中一種簡化假設，在這個假設下得到的演算法叫樸素貝葉斯分類器（演算法）。雖然這個假設較強，但很多問題在這個假設下依然表現良好。樸素貝葉斯假設是指在給定(y) 的條件下，向量$ x$ 的各個分量$ x_j$ 取值是條件獨立的。具體的，給定C的情況下，A和B是條件獨立的是指$ p(A)=p(A|B,C)$ 。注意，這與A和B是獨立的不同。A與B獨立是指$ p(A)=p(A|B)$ 。在條件獨立假設下，我們可以簡化條件概率，將條件概率分解為如下形式，
[ begin{array}{l} {pleft(x_{1}, ldots, x_{n} | yright)} \ {quad=pleft(x_{1} | yright) pleft(x_{2} | y, x_{1}right) pleft(x_{3} | y, x_{1}, x_{2}right) cdots pleft(x_{n} | y, x_{1}, ldots, x_{n-1}right)} \ {quad=pleft(x_{1} | yright) pleft(x_{2} | yright) pleft(x_{3} | yright) cdots pleft(x_{n} | yright)} \ {quad=prod_{j=1}^{n} pleft(x_{j} | yright)} end{array} ]
從現在起，我們應該把特徵$x $ 看成是一個固定的東西。則模型的參數有垃圾郵件的先驗概率(phi_{y}=p(y=1)) ，以及每個特徵分量下的兩個參數(phi_{j | y=1}=pleft(x_{j}=1 | y=1right)) ，和 (phi_{j | y=0}=pleft(x_{j}=1 | y=0right))。比如 (phi_{j | y=1}=pleft(x_{j}=1 | y=1right)) 是垃圾郵件中這個特徵所代表的單詞出現的概率。

然後我們在這些參數下可以寫出數據的似然函數，
[ mathcal{L}left(phi_{y}, phi_{j | y=0}, phi_{j | y=1}right)=prod_{i=1}^{m} pleft(x^{(i)}, y^{(i)}right) ]
關於每組參數最大化，可以得到各個參數的如下估計，
[ begin{equation} begin{aligned} phi_{j | y=1} &=frac{sum_{i=1}^{m} 1left{x_{j}^{(i)}=1 wedge y^{(i)}=1right}}{sum_{i=1}^{m} 1left{y^{(i)}=1right}} \ phi_{j | y=0} &=frac{sum_{i=1}^{m} 1left{x_{j}^{(i)}=1 wedge y^{(i)}=0right}}{sum_{i=1}^{m} 1left{y^{(i)}=0right}} \ phi_{y} &=frac{sum_{i=1}^{m} 1left{y^{(i)}=1right}}{m} end{aligned} end{equation} ]
不難理解上面等式的意義（其中1表示計數向量，尖號表示邏輯與）。比如參數(phi_{j | y=1}=pleft(x_{j}=1 | y=1right)) 的估計（不嚴格地，上面我們還用同一個符號來表示）其實就是垃圾郵件中這個特徵所代表的單詞出現的頻率，在一個郵件中每個詞最多計數一次。
估計出這些參數，來了一個新郵件，我們就可以做出如下預測，
[ begin{aligned} p(y=1 | x) &=frac{p(x | y=1) p(y=1)}{p(x)} \ &=frac{left(prod_{j=1}^{n} pleft(x_{j} | y=1right)right) p(y=1)}{left(prod_{j=1}^{n} pleft(x_{j} | y=1right)right) p(y=1)+left(prod_{j=1}^{n} pleft(x_{j} | y=0right)right) p(y=0)} end{aligned} ]
不要害怕第二個分母里一坨東西，它只是計算了$ x$ 和$ y$ 的不同取值的聯合概率，然後歸一化。
之前我們說特徵向量$ x$ 是0，1向量。可以自然推廣到特徵向量取$k $ 個值的情況。對於連續的變數不是太服從多元正態分布時，可以將其離散化為$k $ 值離散特徵向量，然後利用這個模型，也往往能取得比高斯判別分析模型更好的結果。

拉普拉斯平滑

2019年9月21日19:03:05
上面演算法的一個最大問題就是對於在詞表中出現過，但訓練集中未出現過的單詞，計算出後驗概率0：0，無法判斷是垃圾郵件，還是非垃圾郵件。採用拉普拉斯平滑可以大大改善這個演算法。
更廣泛一點來說，對於訓練集中沒有見到的事件，我們就估計它出現的概率為零，不是一個好的做法。對於一個取k個值的多項分布。把最大似然估計有，
[ phi_{j}=frac{sum_{i=1}^{m} 1left{z^{(i)}=jright}}{m} ]
拉普拉斯平滑機制則在此基礎上在分母加$k $，分子加一，即，
[ phi_{j}=frac{sum_{i=1}^{m} 1left{z^{(i)}=jright}+1}{m+k} ]
回到樸素貝葉斯參數估計上，再給定標籤$y $ 的情況下，表示詞出現與否的每個特徵分量 $x_{j} $ 是一個二項分布，因此就有如下拉普拉斯平滑估計，
[ begin{aligned} phi_{j | y=1} &=frac{sum_{i=1}^{m}{ 1left{x_{j}^{(i)}=1 wedge y^{(i)}=1right}}+1}{sum_{i=1}^{m}{ 1left{y^{(i)}=1right}}+2} \ phi_{j | y=0} &=frac{sum_{i=1}^{m} 1left{x_{j}^{(i)}=1 wedge y^{(i)}=0right}+1}{sum_{i=1}^{m} 1left{y^{(i)}=0right}+2} end{aligned} ]
注意，我們這裡是對特徵分量進行拉普拉斯平滑。標籤本身也是個二項分布，但一般不需要拉普拉斯平滑。

文本分類事件模型

雖然樸素貝葉斯演算法在分類中一般表現較好，有一類演算法在文本分類中可以表現得更好。

樸素貝葉斯用的是多元伯努利事件模型（multi-variate Bernoulli event model）。郵件發送者先一定概率決定發送垃圾郵件和非垃圾郵件，然後在給定條件概率下。獨立的以相應概率發送詞表中的每個單詞。
現在我們來看一下多項事件模型（multinomial event model）。他對每個郵件的特徵表示與之前不同。他將第j個特徵分量表示郵件中的第j個單詞（之前的是詞表中第j個單詞出現與否0，1變數）。這個特徵分量取值於({1, ldots,|V|})，(|V|) 為詞表的大小。然後一個郵件由不固定長度的(n) 個片語成。
在多項事件模型中，每個郵件是否是垃圾郵件產生方法和之前相同。在決定了郵件是否是垃圾郵件後，再根據相應的條件概率產生第一個單詞，注意是從多項分布中產生一個單詞，然後再獨立的產生第二個單詞，一直產生n個單詞。這裡分布是多項分布，和之前的伯努利分布是不一樣的。

這個模型的參數同樣有垃圾郵件的先驗概率(phi_{y}=p(y=1)) ，(phi_{k | y=0}=pleft(x_{j}=k | y=0right)) 和(phi_{k | y=1}=pleft(x_{j}=k | y=1right)) 。注意，我們這裡假設不管哪一個位置j，產生此位置單詞的多項分布的參數都是一樣的（比較之前(phi_{j | y=0}=pleft(x_{j}=1 | y=0right)) ）。

給定訓練集(left{left(x^{(i)}, y^{(i)}right) ; i=1, ldots, mright}) ，其中(x^{(i)}=left(x_{1}^{(i)}, x_{2}^{(i)}, dots, x_{n_{i}}^{(i)}right))，這裡$n_{(i)} $ 是第${i} $ 個郵件的單詞個數。然後我們在這些參數下可以寫出數據的似然函數，
[ begin{aligned} mathcal{L}left(phi_{y}, phi_{k | y=0}, phi_{k | y=1}right) &=prod_{i=1}^{m} pleft(x^{(i)}, y^{(i)}right) \ &=prod_{i=1}^{m}left(prod_{j=1}^{n_{i}} pleft(x_{j}^{(i)} | y ; phi_{k | y=0}, phi_{k | y=1}right)right) pleft(y^{(i)} ; phi_{y}right) end{aligned} ]
關於每組參數最大化，可以得到各個參數的如下估計，
[ begin{aligned} phi_{k | y=1} &=frac{sum_{i=1}^{m} sum_{j=1}^{n_{i}} 1left{x_{j}^{(i)}=k wedge y^{(i)}=1right}}{sum_{i=1}^{m} 1left{y^{(i)}=1right} n_{i}} \ phi_{k | y=0} &=frac{sum_{i=1}^{m} sum_{j=1}^{n_{i}} 1left{x_{j}^{(i)}=k wedge y^{(i)}=0right}}{sum_{i=1}^{m} 1left{y^{(i)}=0right} n_{i}} end{aligned} ]
我們耐心從一個郵件開始分析，慢慢理順就不難理解上面等式的意義（其中1表示計數向量，尖號表示邏輯與）。比如 (phi_{k | y=1}) 是垃圾郵件中第(k) 個單詞出現的頻率，在一個郵件中每個詞可能多次計數（注意比較與前面不同）。

如果我們用拉普拉斯平滑，標籤$y $ 的情況下，表示第 $j $ 個位置哪個詞出現的特徵分量 $x_{j} $ 是一個多項分布（取值個數 (|V|) ），因此就有如下拉普拉斯平滑估計，
[ begin{aligned} phi_{k | y=1} &=frac{sum_{i=1}^{m} sum_{j=1}^{n_{i}} 1left{x_{j}^{(i)}=k wedge y^{(i)}=1right}+1}{sum_{i=1}^{m} 1left{y^{(i)}=1right} n_{i}+|V|} \ phi_{k | y=0} &=frac{sum_{i=1}^{m} sum_{j=1}^{n_{i}} 1left{x_{j}^{(i)}=k wedge y^{(i)}=0right}+1}{sum_{i=1}^{m} 1left{y^{(i)}=0right} n_{i}+|V|} end{aligned} ]
儘管樸素貝葉斯演算法可能不是最好的，但它通常都有不俗的表現。由於這個演算法實現起來簡單明了。絕對是首先值得一試的演算法。

實現細節

2019年9月25日12:15:38
程式碼源於這裡，精簡濃縮了sklearn實現，精華，推薦。

類定義，

class BernoulliNB():      def __init__(self, alpha=1.0):          self.alpha = alpha #平滑參數，事實上可以設為任意大於零值

下面都是類函數，

_xxx 表示protected類型變數。只允許這個類本身與它的子類進行訪問。不能用 from module import * 引入名字。

__xxx 表示私有類型變數。只允許這個類本身進行訪問，子類不可以訪問。

總結，python 裡面的單下劃線與雙下劃線的區別是前者保護和後者私有

#這裡的X都是訓練數據  def _encode(self, y):      classes = np.unique(y)      y_train = np.zeros((y.shape[0], len(classes)))      for i, c in enumerate(classes):          y_train[y == c, i] = 1 #每一行是 y 的one-hot表示      return classes, y_train    def fit(self, X, y):      self.classes_, y_train = self._encode(y)      self.feature_count_ = np.dot(y_train.T, X)   # C類*n詞 一行代表是不是某一類，X一j列代表出現了沒第j個詞，中間m個文檔正好累和消去      self.class_count_ = y_train.sum(axis=0)      smoothed_fc = self.feature_count_ + self.alpha #給定類別下，避免各個詞頻為零出現，最小      smoothed_cc = self.class_count_ + 2 * self.alpha #某類別下特徵出現與否概率，與類別個數無關，與特徵個數無關，只與出現與否有關，因此加2，使得出現和不出現加起來概率為1      self.feature_log_prob_ = (np.log(smoothed_fc) -                                np.log(smoothed_cc.reshape(-1, 1)))    #reshape(-1, 1)升維變成C*1的2維數組，可參考之前numpy廣播部落格      self.class_log_prior_ = np.log(self.class_count_) - np.log(self.class_count_.sum())      return self

輸入 y 是$ m$ 個整數標籤，由函數 _encode 知道， self.classes_ 是一個長為$ C$ 的表示類別一維數組， y_train 為$ mtimes C$ 二維數組，每一行表示每個樣本的獨熱編碼。因此， self.class_count_ = y_train.sum(axis=0) 表示每個類的文檔個數。注意求和後self.class_count_ 遭到降維打擊變成一位數組。

$ X$ 表示由$ m$ 個樣本，$ n$ 個特徵組成的$ mtimes n$ 數據矩陣。裡面表示詞表中詞出現與否的0,1特徵向量意義在之前講過。

self.feature_count_= np.dot(y_train.T, X) 是一個 $ Ctimes n$ 的矩陣，$ (i,j)$ 元素表示第$ i$ 個類別下第$ j$ 個特徵詞出現的文檔個數（自己理一理，向量化程式碼學習一下）。

#這裡的X都是新來的數據  def _joint_log_likelihood(self, X): #第二坨是計算未出現詞項的概率，第一項出現詞項概率，向量大法好，簡潔又明了（可能不太明了？）      return (np.dot(X, self.feature_log_prob_.T) +              np.dot(1 - X, np.log(1 - np.exp(self.feature_log_prob_)).T) +              self.class_log_prior_)    def predict(self, X):#如前所述，預測不需要歸一化      joint_log_likelihood = self._joint_log_likelihood(X)      return self.classes_[np.argmax(joint_log_likelihood, axis=1)]    def predict_proba(self, X):#歸一化概率      joint_log_likelihood = self._joint_log_likelihood(X)      log_prob = joint_log_likelihood - logsumexp(joint_log_likelihood, axis=1)[:, np.newaxis] #[:, np.newaxis]升維變成m*1的2維數組，可參考之前numpy廣播部落格      return np.exp(log_prob)