第四章 Linear Models for Classification

PRML 机器学习

---

章节细讲

---

重点讲了解决分类问题的三种不同方法，最简单的是判别函数， 它直接将 inference 和 decision 两个阶段合在一起，建立判别函数，判别函数就是输入x然后输出就是类的编号。剩下的两种分类方法都是将 inference 和 decision 分开，不同的是生成模型不直接对$p(C_k|x)$建模，而是通过对$p(x|C_k)$和$p(C_k)$建模，然后使用贝叶斯公式获得$p(C_k|x)$。而对应的判别模型，则直接对$p(C_k|x)$建模，相比生成模型，判别模型的参数通常更少。
当在线性模型外面套一个激活函数（通常是非线性函数）就称为广义线性模型，广义线性模型的分割面是超平面。

4.1. Discriminant Functions
4.1.3 Least squares for classification
如同regression中的 sum-of-squares error方法，有解析解，但是由于least squares是假设似然函数的条件概率是服从高斯分布，而这和分类问题的目标相差甚远，所以效果很差，一般不会使用。
4.1.4 Fisher’s linear discriminant
Fisher一般是作为有监督的降维使用。输入数据 x 是一个D维向量，但是$y=w^Tx$却是一个只有一维的scalar，这个过程可以看作是D维的一个向量投影到1维空间上。Fisher判别的思想是，把分类看作选择一个1维空间，并把原D维数据投影到该空间的过程；选择1维空间的准则是Fisher criterion，包含两方面的要求：一方面要求投影到1维空间后，不同类的数据是分开的（投影后各个类的均值之差大$\frac{1}{N_1}\sum_{n\in C_1}w^Tx_n-\frac{1}{N_2}\sum_{n\in C_2}w^Tx_n$）；而另一方面要求同一类的数据能够尽可能聚集在一块（投影后方差小$s_k^2=\sum_{n\in C_k}(w^Tx_n-m_k)^2$）。Fisher criterion是这两方面要求的量化（两者相除）。求解Fisher criterion最大化后，得到参数w，即确定了decision hyperplane的（法）方向；剩下只需要再在1维上确定一个阈值$y_0$，表明该超平面的位置即可。
4.1.7 The perceptron algorithm
感知机也是Generalized Linear Model$\ y=f(w^Tx+w_0)$，其中激活函数是阶跃函数，而损失函数是perceptron criterion。首先修改一下类的标号方式：把第1类记$t_{C_1}$为+1，第2类记$t_{C_2}$为-1。对于一个数据$x_n$如果属于第1类，则有$w^Tx_n>0$；如果属于第2类，则有$w^Tx_n< 0$；因此正确分类的数据$x_n$总是有$w^Tx_nt_n>0$。而对于每个误分类的数据$x_n$，$w^Tx_nt_n< 0$，我们的目标是最小化误分类的$-w^Tx_nt_n$。perceptron criterion，就是把所有误分类的这个目标相加，得到$E_p(w)=\sum_{n\in M}-w^Tx_nt_n$，其中$M$是全部误分类数据点的集合。最小化这个目标函数没有closed解，可以用stochastic gradient descent算法解。

$$w^{(\tau+1)}=w^{(\tau)}+\eta\phi_nt_n$$

4.2. Probabilistic Generative Models
需要建模input的分布，即得到class-conditional distribution，用贝叶斯定理转化成后验概率后，就是和Discriminant model一样进行决策了

$$\begin{align} p(C_1|x)&=\frac{p(x|C_1)p(C_1)}{p(x|C_1)p(C_1)+p(x|C_2)p(C_2)}\\ &= \frac{1}{1+exp(-a)}=\sigma(a) \tag 1 \end{align}$$
其中
$$a=ln\frac{p(x|C_1)p(C_1)}{p(x|C_2)p(C_2)}\tag 2$$
对于指数族分布，$a$是关于x的线性函数。
4.2.1 Continuous inputs
假设input的class-conditional distribution的分布形式为Gaussian，而且进一步假设每个类别的class-conditional distribution具有相同的covariance matrix $\Sigma$，不同的仅仅是各自的均值向量$\mu$。
$$p(x|C_k)=\frac{1}{(2\pi)^{D/2}}\frac{1}{|\Sigma|^{1/2}}exp\{-\frac{1}{2}(x-\mu_k)^T\Sigma^{-1}(x-\mu_k)\}$$
则通过(1)式和(2)式可以得到
$$p(C_1|x)=\sigma(ln\frac{p(x|C_1)p(C_1)}{p(x|C_2)p(C_2)})=\sigma(w^Tx+w_0)\tag 3$$
其中：
$$\begin{align} &w=\Sigma^{-1}(\mu_1-\mu_2)\\ &w_0=-\frac{1}{2}\mu_1^T\Sigma^{-1}\mu_1+\frac{1}{2}\mu_2^T\Sigma^{-1}\mu_2+ln\frac{p(C_1)}{p(C_2)} \end{align}$$
可以看出$a$是关于x的线性函数，得到的后验概率刚好是一个GLM模型（Logistic）。

上图说明当条件分布共享$\Sigma$时（绿色和红色），生成模型的决策面是超平面。
4.2.3 Discrete features
假设input的class-conditional distribution的分布形式为二项分布，而且进一步假设每个特征是条件独立的。
$$p(x|C_k)=\prod _{i=1}^D\mu_{ki}^{x_i}(1-\mu_{ki})^{1-x_i}$$
则通过(1)式和(2)式可以得到
$$p(C_1|x)=\sigma(ln\frac{p(x|C_1)p(C_1)}{p(x|C_2)p(C_2)})=\sigma(w^Tx+w_0)\tag 4$$
其中：
$$a_k(x)=\sum_{i=1}^D{x_iln\mu_{ki}+(1-x_i)ln(1-\mu_{ki})}+lnp(C_k)$$
可以看出$a$是关于x的线性函数。
4.2.4 Exponential family
通过(3)式和(4)式可以看出，对于高斯分布和二项分布来说，后验概率都可以看成激活函数是sigmod函数的广义线性模型，即$p(C_k|x)=\sigma(w^Tx+w_0)$，。其实，这是指数族分布的特性，即当条件概率是指数族分布时候（有少许限制，例如高斯分布有共同的$\Sigma$），后验概率都可以看成激活函数是sigmod函数的广义线性模型。

4.3. Probabilistic Discriminative Models
对于二分类问题来说，我们从4.2.4看到对于很多的条件概率来说，后验概率都是$\sigma(w^Tx+w_0)$。对于生成模型我们需要对$p(x|C_k)$和$p(C_k)$建模，然后再使用贝叶斯公式求出后验概率，即隐式确定$\sigma(w^Tx+w_0)$中$w、w_0$的值。因此，我们可以跳过条件概率和先验而直接对后验概率建模求出$w、w_0$的值，即判别模型。相比于生成模型的参数是维度的平方级，而判别模型的参数则仅仅是维度的线性函数。
4.3.3 Iterative reweighted least squares
logstic回归的后验概率：

$$p(C_x|x)=\sigma(w^Tx)$$
则似然函数是：
$$p(D|w)=\prod_{n=1}^N\sigma^{t_n}(1-\sigma)^{1-tn}$$
损失函数是求出最小化cross-entropy error function：
$$E(w)=-ln\ p(t|w)=-\sum_{n=1}^N\{t_nln\sigma+(1-t_n)ln(1-\sigma)\}$$
另外，如果激活函数是probit function，那么就得到probit regression。probit function就是标准正态分布的累计函数。

最小化E(w)应求出其梯度，并令梯度为0，注意到方程$\nabla E(w)=0$不存在closed-form solution，因为这个方程含有多个非线性的logistic function的求和。
IRLS其实就是牛顿迭代法，用于解如下方程：

$$\nabla E(w)=0$$
因此会涉及到Hessian矩阵，求解该方程的迭代公式为：
$$w^{(new)}=w^{(old)}-H^{-1}\nabla E(w)$$
4.3.6 Canonical link functions
对于指数族分布的对数似然函数对参数$w$求导，都得到$(y_n-t_n)\phi_n$的形式：
$$\nabla E(w)=\frac{1}{s}\sum_{n=1}^N\{y_n-t_n\}\phi_n$$

4.4. The Laplace Approximation
Laplace Approximation即找一个高斯分布q(z)，来近似一个复杂的分布$p(z)=\frac{1}{Z}f(z)$，其中$Z$是一个对$f(z)$的归一化因子。
找q(z)的方法是：首先找到$f(z)$的一个驻点$x_0$，然后在这点处将$ln\ f(z)$泰勒展开：

$$ln\ f(z)\simeq ln\ f(z_0)-\frac{1}{2}A(z-z_0)^2$$
其中，$A=-\frac{d^2}{dz^2}ln\ f(z)|_{z=z_0}$，因此：
$$f(z)\simeq f(z_0)exp\{-\frac{1}{2}A(z-z_0)^2\}$$
因为指数部分是$z$的平方函数，所以可以使用高斯分布近似：
$$q(z)\simeq {(\frac{A}{2\pi})}^{\frac{1}{2}}exp\{-\frac{1}{2}(z-z_0)^TA(z-z_0)\}=N(z_0,A^{-1})$$
因此，得到用来近似原复杂分布p(z)的高斯分布$q(z)$。

左图中黄色区域是目标分布，红色曲线是近似高斯分布。右图可以看出可以看出两个分布都在同一点取得众数。
4.4.1 Model comparison and BIC
通过对$f(z)$做Laplace Approximation我们可以得：
$$\begin{align} Z&=\int f(z)dz\\ &\simeq f(z_0)\int exp\{-\frac{1}{2}(z-z_0)^TA(z-z_0)\}dz\\ &=f(z_0)\frac{(2\pi)^{M/2}}{|A|^{1/2}} \end{align}$$
考虑模型的model evidence：
$$p(D|M_i)=\int p(D|M_i,\theta)p(\theta|M_i)d\theta$$
假设$f(\theta)=p(D|M_i,\theta)p(\theta|M_i)$，因此$Z=p(D|M_i)$，得：
$$lnp(D|M_i)\simeq lnp(D|M_i,\theta_{MAP})+lnp(\theta_{MAP})+\frac{M}{2}ln(2\pi)-\frac{1}{2}|A|$$

4.5. Bayesian Logistic Regression
以2类的情况考虑。对于一个新的feature vector ，现在要计算它的predictive distribution，也就是：$p(C_1|\phi,t)=\int p(C_1|\phi,w)p(w|t)dw=\int \sigma(w^Tx)p(w|t)dw$，涉及到Bayesian方法的典型问题，即marginalize over parameter space；以及在logistic变换下变得很复杂的后验概率p(w|t)。

现在首先要为复杂的$p(w|t)$找一个Laplace approximation近似的 q(w)。按照Laplace approximation的方法，得先找到p(w|t)的：stationary point，即$m_{MAP}$，以及lnp(w|t)的Hessian matrix。如果假设了先验概率$p(w)=N(w|m_0,S_0)$，那么对最大化$lnp(w|t)$可以求得参数$m_{MAP}$，两次求导得到Hessian matrix $S_N$，从而近似的高斯分布是$q(w)=N(w|m_{MAP},S_N)$。用$q(w)$替换$p(w|t)$，完成剩下的marginalization的工作，这里就是计算logistic函数与Gaussian分布的卷积。计算出最终的predictive distribution。

全章概况

---

本章依旧分为频率派和贝叶斯派两个视角对各个知识点进行对比。首先作者介绍了广义线性模型和多分类的情况，然后介绍了分类问题的三种解决方法，判别函数、生成模型、判别模型。其中生成模型和判别模型都是分为 inference 和 decision 两个阶段，而判别函数将两个阶段合并在一起，给定特征直接输出类标号。让生产模型的条件概率是指数族分布时，后验概率其实就是logstic函数。因此避开对先验概率和条件概率建模，直接显式求后验概率的参数就是判别模型。当然除了将后验概率定义为logstic函数以外，还可以假设后验概率的分布是probit函数，即标准正态分布的累计函数，形状类似于logstic函数。最后作者介绍了贝叶斯方法中常用的近似手段，Laplace Approximation。因为分类问题中，参数的后验概率$p(w|x)$和预测分布$p(t|w,x)$都不再是高斯分布，因此做marginal时就不再有解析解，因此作者提到需要对后验概率$p(w|x)$做高斯近似，然后再计算logistic函数与Gaussian分布的卷积，值得一提的是，最后用probit近似了logstic函数，而求出最终的预测分布。

参考资料

---

1. PRML, chapter 4
2. Notes on Pattern Recognition and Machine Learning (Jian Xiao)
3. Pattern Recognition And Machine Learning 读书会, chapter 4