Learning From Data——Generative Learning Algorithm

Posted on Edited on In

之前我们介绍的分类算法，包括，logistic regression，PLA甚至加上linear regression，他们都是试图找到一条线然后来将两种类别分开。这种算法叫做Discriminative Learning Algorithm，他们的由来，都是直接去估计P(Y|X)P(Y|X),这样的话根据新样本的X，从而预测Y。

接下来我们想介绍的是另外一种思路来解决分类问题。我们不再直接估计P(Y|X)P(Y|X),而是估计P(X|Y)P(X|Y).也就是，我们希望从当前的样本中学到X的特征看上去应该是什么样子，从鸡的样本中学到鸡的样子，从狗的样本中学到狗的样子。这样的算法叫做Generative Learning Algorithm（生成学习算法）。当然，我们最后要知道的还是P(Y|X)P(Y|X),不过根据Bayes理论可以知道： P(Y|X)=P(X|Y)P(Y)P(X) P(Y|X) = \frac{P(X|Y)P(Y)}{P(X)}

我们知道：

argmaxyp(y|x)=argmaxyp(x|y)p(y)p(x)=argmaxyp(x|y)p(y)=WhatWePredictargmax_yp(y|x) = argmax_y \frac{p(x|y)p(y)}{p(x)} = argmax_y p(x|y)p(y) = WhatWePredict

所以我们真正需要解决的是P(x|y)P(y)P(x|y)P(y).

当然，如果想要求得P(X),可以通过全概率公式：P(X)=P(y=1)⋅P(X|y=1)+P(y=0)⋅P(X|y=0)P(X) = P(y=1)\cdot P(X|y=1) +P(y=0)\cdot P(X|y=0).

下面介绍两个最常见的生成学习算法：Gaussian Discriminant Analysis(高斯判别分析)与Naive Beyas(朴素贝叶斯模型)。

Gaussian Discriminate Analysis

高斯判别模型主要用于输入是连续的时候，也就是X的特征值是属于实数集的。首先来复习一下多维高斯分布模型，它是高斯判别模型的基础：

一般来说，多维高斯分布简写为：X N(,). * μ∈ℝn\mu \in \mathbb{R}^n 是平均向量。 * Σ∈ℝn×n\Sigma \in \mathbb{R}^{n \times n}是协方差矩阵。Σ\Sigma是对称的SPD（ symmetric and positive definite matrix）.

它的概率密度函数如下： p(x;μ,Σ)=1(2π)n2|Σ|12e−12(x−u)TΣ−1(x−u) p(x;\mu,\Sigma) = \frac{1}{(2\pi)^{\frac n 2}\vert \Sigma\vert ^{\frac 1 2} } e^{-\frac 1 2(x-u)^T\Sigma^{-1}(x-u)}

均值和协方差对分布有什么影响？利用一个二维的向量来说的话，有下面几张图可以看看：

这三张图分别对应着协方差矩阵为I，2I,12II，2I,\frac 1 2 I的情况。其中 I=[1001]I = \begin{bmatrix} 1&0\\ 0&1 \end{bmatrix}.

从上图又可以看出来，协方差矩阵非对角线的数字变化的时候，对它的图形似乎扭向一边了。实际上这代表了两个特征间的相关程度。

最后一个就是mumu的变化，很显而易见，图形的中心改变了。

现在假如有一个分类问题，其中X∈ℝnX \in \mathbb{R}^n,利用高斯判别模型的话，我们会有以下假设： $$ y\tilde{} Bernuolli(\Phi)\\ p(x|y=0)\tilde{}N(\mu_0,\Sigma)\\ p(x|y=1)\tilde{}N(\mu_1,\Sigma) $$ 从上面看出来，我们对于两个模型的生成采用的μ\mu不一样，但是Σ\Sigma一样，这样不光保证了两个模型的形状一样，简化了计算过程，最后可以用它们接触点的切线来当做分割线，从而实现与之前Discriminative学习算法的比较。

Note:现在n为向量的维度，而m为样本个数。

和往常一样，我们求它的log极大似然估计： l(Φ,μ0,μ1,Σ)=log⁡∏i=1mp(Xi,yi;Φ,μ0,μ1,Σ)=log⁡∏i=1mp(Xi|yi;μ0,μ1,Σ)p(yi;Φ) \begin{align} l(\Phi,\mu_0,\mu_1,\Sigma)&= \log \prod_ {i=1}^{m}p(X_i,y_i;\Phi,\mu_0,\mu_1,\Sigma)\\ &= \log \prod_ {i=1}^m p(X_i|y_i;\mu_0,\mu_1,\Sigma)p(y_i;\Phi) \end{align}

上述的式子中的参数取值如下： $$ \Phi = \frac 1 m \sum_ {i=1}^m \mathbf{1}\{ y_i = 1\}\\ \mu_b = \frac{\sum_ {i=1}^m \mathbf{1}\{y_i=b\}X_i}{\sum_ {i=1}^m \mathbf{1}\{y_i=b\} },b=0,1\\ \Sigma = \frac 1 m \sum_ {i=1}^m(X_i - \mu_ {y_i})(X_i - \mu_ {y_i})^T $$

我们希望生成的模型如下：

如果画等高线图：

我们会发现找到一条线，它属于0或者1的概率是相等的。因此我们就找到了这条线。

GDA与Logistic Regression

在上面的推导过程中我们发现： P(y=1|X;Φ,μ0,μ1,Σ)=p(X|y=1)p(y=1)p(X|y=1)p(y=1)+p(X|y=0)p(y=0)=11+e−θTX \begin{align} P(y=1|X;\Phi,\mu_0,\mu_1,\Sigma) &= \frac{p(X|y=1)p(y=1)}{p(X|y=1)p(y=1)+p(X|y=0)p(y=0)}\\ &=\frac {1}{1+e^{-\theta ^TX} } \end{align} 上式中：θ=[log⁡1−ΦΦ−12(μ0TΣ−1μ0−μ1TΣ−1μ1)Σ−1(μ0−μ1)]\theta = \begin{bmatrix} \log \frac{1-\Phi}{\Phi} - \frac 1 2(\mu_0^T\Sigma^{-1}\mu_0 - \mu_1^T \Sigma^{-1}\mu_1) \\ \Sigma ^{-1}(\mu_0 - \mu_1)\end{bmatrix}.

如果还记得上次讲过的exponential family，我们应该知道对于伯奴利分布(y|x̃B(ψ))(y|x \tilde{} B(\psi))的canonical link funtion是 log⁡ψ1−ψ\log \frac{\psi}{1-\psi}.

因此θX=log⁡ψ1−psi=log⁡p(y=1|X)p(y=0|X)=log⁡p(X|y=1)p(y=1)p(X|y=0)p(y=0)\theta ^X = \log \frac{\psi}{1-psi} = \log \frac{p(y=1|X)}{p(y=0|X)} = \log \frac {p(X|y=1)p(y=1)}{p(X|y=0)p(y=0)}

这意味着：如果p(x|y)̃N(μ,Σ)p(x|y)\tilde{}N(\mu,\Sigma),则p(y|x)p(y|x)是logistic function.但是从logistic regression是无法推出来GDA的。

如果我们的假设正确，GDA模型更高效，效果也更好，但是logistic regression因为比较简单，对于即使假设错误了依然有很好的鲁棒性。GDA最大化联合分布，而LR最大化的是概率分布。

所以我们发现，GDA并不像普通的学习算法那样需要去进行cost funtion的优化。这得益于我们假设整个正样本的X服从一个高斯分布。而之前的学习方法，每个样本因为X不同各个样本之间服从分布的参数都会不一致，也就是每个样本在给定y的时候有一个自己的分布（如逻辑回归，每个样本都有不同的概率，而它预测的是伯奴利分布，也就是每个样本服从不同的伯奴利分布；又如线性回归，每个样本有不一样的μ\mu）。

Naive Beyas

下面介绍朴素贝叶斯模型。它用来处理输入为离散数据时候的情况。假如有这么一个例子：垃圾邮件分类。如何定义邮件的特征？当然定义的是其中的单词了。但是这个世界上单词有很多很多，而垃圾邮件很可能更包含了很多无意义的字符组合，这样特征就更多了。

假设给一个大小为n的字典（这个n可能很大，50000或者100000），而一个邮件的特征值会像下面的样子： [10...1...]aaadjsa...b... \begin{bmatrix} 1\\ 0\\ .\\ .\\ .\\ 1\\ .\\ .\\ . \end{bmatrix} \begin{matrix} a\\ aadjsa\\ .\\ .\\ .\\ b\\ .\\ .\\ . \end{matrix}

1或者0代表了在这个邮件中是否出现了。

现在希望对P(X|Y)P(X|Y)建模。对于一封垃圾邮件： p(x1,x2,...,xn|y)=p(x1|y)p(x2|y,x1),...,p(xn|y,x1,...,xn−1) p(x_1,x_2,...,x_n|y) = p(x_1|y)p(x_2|y,x_1),...,p(x_n|y,x_1,...,x_ {n-1}) 使用了概率论中的链式法则。这个规则我也不了解，概率论还需要学习

这样的计算是非常复杂的。因此朴素贝叶斯模型中有一个假设：xix_i在给定y之后是条件独立的。这意味着：p(xn|y,x1,...,xn−1)=p(xn|y)p(x_n|y,x_1,...,x_ {n-1}) = p(x_n|y).

所以p(x1,x2,...,xn|y)=∏i=1np(xi|y)p(x_1,x_2,...,x_n|y) = \prod _ {i=1}^np(x_i|y).

多变量伯奴利事件模型

p(x,y)=p(y)p(x|y)=p(y)∏i=1np(xi|y)p(x,y) = p(y)p(x|y) = p(y) \prod _ {i=1}^n p(x_i|y).

这个模型假设了每封邮件是以Φy\Phi_y随机生成的。如果给定y，每个单词是独立的包含在信息里的，而这个概率为p(xi=1|y)=Φi|yp(x_i=1|y) = \Phi_ {i|y}.

这个模型参数如下：

  • Φy=p(y=1)\Phi_y = p(y=1)
  • Φi|y=0=p(x=1|y=0)\Phi_ {i|y=0} = p(x=1|y=0)
  • Φi|y=1=p(x=1|y=1)\Phi_ {i|y=1} = p(x=1|y=1)

同样的，接下来要做的依然是求log极大似然估计：

L(ΦyΦi|y=1,Φi|y=0)=log⁡∏i=1mp(Xi,yi)=log⁡∏i=1mp(Xi|yi)p(yi)=log⁡∏i=1m∏j=1np(xj|yi) \begin{align} L(\Phi_y \Phi_ {i|y=1},\Phi_ {i|y=0}) &=\log \prod_ {i=1}^m p(X_i,y_i)\\ &= \log \prod_ {i=1}^m p(X_i|y_i)p(y_i)\\ &= \log \prod_ {i=1}^m \prod_ {j=1}^np(x_j|y_i) \end{align}

不难想象，各个参数的取值如下： $$ y = p(y=1) = m {i=1}^m {y_i=1}\

_ {j|y=b} = ,b=0,1 $$

当给了一个新的样本的时候，我们计算p(y=1|x)p(y=1|x):

p(y=1|X)=p(X|y=1)p(y=1)p(X)=p(y=1)∏i=1np(xi|y=1)p(X|y=1)+p(X|y=0)=p(y=1)∏i=1np(xi|y=1)p(y=0)∏i=1np(xi|y=0)+p(y=1)∏i=1np(xi|y=1) \begin{align} p(y=1|X) &= \frac{p(X|y=1)p(y=1)}{p(X)}\\ &= \frac{p(y=1)\prod _ {i=1}^n p(x_i|y=1)}{p(X|y=1)+p(X|y=0)}\\ &=\frac{p(y=1)\prod _ {i=1}^n p(x_i|y=1)}{p(y=0)\prod _ {i=1}^n p(x_i|y=0)+ p(y=1)\prod _ {i=1}^n p(x_i|y=1)} \end{align}

然后根据概率是否大于0.5来进行预测。

Laplace Smoothing

这个模型是有一个缺点的：如果新的样本的单词从来没有在训练集合里出现过，那么：

Φj|y=b=∑i=1m𝟏{yi=b}⋅𝟏{xi,j=1}∑i=1m𝟏{yi=b}=0,b=0,1 \Phi_ {j|y=b} = \frac {\sum_ {i=1}^m \mathbf{1}\{y_i = b\} \cdot \mathbf{1}\{ x_ {i,j}=1\} }{\sum_ {i=1}^m \mathbf{1}\{y_i = b\} } = 0,b=0,1

也就是垃圾邮件和非垃圾邮件里出现它的概率都为0.那么最后预测结果为00\frac 0 0,这就没法计算了。

所以我们需要进行Laplace平滑。对于没有出现过的词，我们给他赋一个较小值，而不是让他为0： Φj=∑i=1m𝟏{zi=j}+1m+k \Phi_j = \frac{\sum_ {i=1}^m \mathbf{1}\{z_i = j\}+1}{m+k}

为了最后使得Φj\Phi_j的和为0,所以k为类比的个数，即∑i=1kΦi=1\sum_ {i=1}^k\Phi_i = 1。

所以最后的估计就成了下面的样子： Φj|y=b=∑i=1m𝟏{yi=b}⋅𝟏{xi,j=1}+1∑i=1m𝟏{yi=b}+2,b=0,1 \Phi_ {j|y=b} = \frac {\sum_ {i=1}^m \mathbf{1}\{y_i = b\} \cdot \mathbf{1}\{ x_ {i,j} = 1\} +1}{\sum_ {i=1}^m \mathbf{1}\{y_i = b\} +2},b=0,1

除此之外其他地方是一样的。

Naive Bayes and Multinomial Event Model

现在有一个新的方法，就是多项式模型。

现在xi∈1,...,|V|x_i \in {1,...,\vert V \vert},其中|V|为字典的长度。而n为信息的长度，也就是现在每个样本的特征数已经不一样了，因为我们没法保证每封信长度一样。

对字典中每个词都进行编号：

dictionary id 1 2 … 1300 … 2400 …
word a aa … free … gift …

多项式模型中有下面几个假设： * 信息随机地被以概率p(y)p(y)生成 * x1,x2,...,xnx_1,x_2,...,x_n独立同分布 * p(x1,x2,...,xn,y)=p(y)∏i=1np(xi|y)p(x_1,x_2,...,x_n,y) = p(y)\prod _ {i=1}^n p(x_i|y)

假设p(xi=k|y)p(x_i=k|y)对所有的kk来说都相等。 则该模型参数如下： * Φy=p(y)\Phi_y = p(y) * Φk|y=1=p(xj=k|y=1)\Phi_ {k|y=1} = p(x_j = k|y=1) for any j∈{1,...,n}j \in \{1,...,n\} * Φk|y=1=p(xj=k|y=0)\Phi_ {k|y=1} = p(x_j = k|y=0) for any j∈{1,...,n}j \in \{1,...,n\}

则出现训练样本的概率为: L(Φy,Φk|y=0,Φk|y=1)=∏i=1mp(xi,yi)=∏i=1mp(yi)p(xi|yi)=∏i=1mp(yi)∏j=1nip(xi,j|yi;Φy,Φk|y=1,Φk|y=0) \begin{align} L(\Phi_y,\Phi_ {k|y=0},\Phi_ {k|y=1}) &= \prod_ {i=1}^m p(x_i,y_i)\\ &= \prod_ {i=1}^m p(y_i)p(x_i|y_i)\\ &=\prod_ {i=1}^m p(y_i) \prod_ {j=1}^{n_i} p(x_ {i,j}|y_i;\Phi_y,\Phi_ {k|y=1},\Phi_ {k|y=0}) \end{align}

各个参数取值如下： $$ \Phi_y = \frac 1 m \sum_ {i=1}^m \mathbf{1}\{y_i=1\}\\ \Phi_ {k|y=1} = \frac{\sum_ {i=1}^m \mathbf{1}\{y_i=1\}\cdot (\sum_ {j=1}^{n_i}\mathbf{1}\{x_i=k\}) +1}{\sum_ {i=1}^m \mathbf{1}\{y_i=1\}+|V|}\\ \Phi_ {k|y=0} = \frac{\sum_ {i=1}^m \mathbf{1}\{y_i=0\}\cdot (\sum_ {j=1}^{n_i}\mathbf{1}\{x_i=k\}) +1}{\sum_ {i=1}^m \mathbf{1}\{y_i=0\}+|V|} $$

最后，预测值为：p(y=1|x)=p(x|y=1)p(y)p(x|y=1)+p(x|y=0)p(y=1|x) = \frac{p(x|y=1)p(y)} {p(x|y=1)+p(x|y=0)}