6.3 分类问题

分类问题的任务：

  • 输入：N个独立同分布（i.i.d）的训练样本(xi,yi)∈X×C(\mathbf{x}^i,y^i)\in X\times C，i=1,2,…,Ni=1,2,\dots,N

  • 目标函数：f∈Ff\in\mathcal{F}

  • 损失函数：L(f;x,y)=I{f(x≠y}L(f;x,y)=I_{\{f(\mathbf{x}\neq y\}}

  • 期望风险：∫I{f(x≠y}dP(x,y)=P(f(x)≠y)\int I_{\{f(\mathbf{x}\neq y\}}dP(\mathbf{x},y)=P(f(\mathbf{x})\neq y)

对于二分类问题，y仅有两个取值-1和1，则其目标为求解一个w\mathbf{w}用于预测y，例如

f(x,w)=sgn(wTx)={1wTx>0−1wTxf(\mathbf{x,w}) = \text{sgn}(\mathbf{w}^T\mathbf{x})=\begin{cases} 1 &\mathbf{w}^T\mathbf{x}>0 \\ -1 &\mathbf{w}^T\mathbf{x} \end{cases}

理论上，对于使用y=−1y=-1或y=1y=1的所有样本，都应该有：

wTxy>0\mathbf{w}^T\mathbf{x}y>0

因此，一些方法会试图最小化分错的样本，即最小化：

E^p(w)=−∑i∈TMwTxiyi\hat{E}_p(\mathbf{w}) = -\sum_{i\in T_M}\mathbf{w}^T\mathbf{x}^iy^i

其中，TMT_M为错分样本的集合

一些常见的分布

伯努利分布

单个二进制变量x∈{0,1}x\in \{0,1\}的分布由单个连续参数β∈[0,1]\beta\in[0,1]控制：

P(x∣β)=βx(1−β)1−xP(x\vert \beta) = \beta^x(1-\beta)^{1-x}

二项式分布

给出N个服从伯努利分布的样本中观察到mm次x=1x=1的概率：

P(m∣N,β)=(Nm)βm(1−β)N−mP(m\vert N,\beta) = \begin{pmatrix} N\\m \end{pmatrix} \beta^m(1-\beta)^{N-m}

多项式分布

多项式分布是二次分布的推广，变量可以取K个状态，第K个状态被观测到了mkm_k次的概率为：

P(m1,…,mk∣N,β)=(Nm1,…,mk)∏k=1KβkmkP(m_1,\dots,m_k\vert N,\beta) = \begin{pmatrix} N\\m_1,\dots,m_k \end{pmatrix} \prod_{k=1}^K\beta_k^{m_k}

多变量正态分布

对于x∼N(μ,Σ)x\sim N(\mu,\Sigma)，有

p(x)=1(2π)D∣Σ∣exp⁡(−12(x−μ)TΣ−1(x−μ))p(x) = \frac{1}{\sqrt{(2\pi)^D\vert\Sigma\vert}}\exp\left(-\frac 12(\mathbf x-\mathbf\mu)^T\Sigma^{-1}(\mathbf x-\mathbf\mu)\right)

其中，∣Σ∣\vert \Sigma\vert为协方差矩阵的行列式，此分布的图像如下图所示：

6.3.1 Logistic 回归

Logistic回归属于判别式模型

Logistic回归使用Logistic函数估计后验概率：

p(y=1∣x)=f(x,w)=g(wTx)=11+exp⁡(−wTx)\begin{align} p(y=1\vert\mathbf{x}) &= f(\mathbf{x,w}) \nonumber \\ &= g(\mathbf{w}^T\mathbf{x}) \\ &=\frac{1}{1+\exp(-\mathbf{w}^T\mathbf{x})} \end{align}

上式中的g(x)=11+e−zg(x)=\dfrac{1}{1+e^{-z}}即为Logistic函数，它是一个经典的Sigmoid函数

Logistic函数具有以下特性：

  • z→∞z \to \infin时，g(z)→1g(z)\to 1

  • z→−∞z \to -\infin时，g(z)→0g(z)\to 0

  • 取值在0到1之间

  • g′(z)=g(z)(1−g(z))g'(z) = g(z)(1-g(z))

一、使用最大似然估计求解Logistic回归

对于二分类问题，可以假设样本的输出服从伯努利分布（0-1分布），则对于y=0y=0和y=1y=1可以统一表达为：

P(y∣x,w)=(f(x,w))y(1−f(x,w))1−yP(y\vert \mathbf{x,w})=(f(\mathbf{x,w}))^y(1-f(\mathbf{x,w}))^{1-y}

则可以得到其似然函数和对数似然函数为：

L(w)=∏i=1NP(yi∣xi,w)=∏i=1N(f(xi,w))yi(1−f(xi,w))1−yil(w)=log⁡L(w)=∑i=1N(yilog⁡f(xi,w)+(1−yi)log⁡(1−f(xi,w)))L(\mathbf{w}) = \prod_{i=1}^NP(y^i\vert \mathbf{x}^i,\mathbf{w}) = \prod_{i=1}^N\left(f(\mathbf{x}^i,\mathbf{w})\right)^{y^i}\left(1-f(\mathbf{x}^i,\mathbf{w})\right)^{1-y^i} \\ l(\mathbf{w})=\log L(\mathbf{w}) = \sum_{i=1}^N\left(y^i\log f(\mathbf{x}^i,\mathbf{w})+(1-y^i)\log\left(1- f\left(\mathbf{x}^i,\mathbf{w}\right)\right)\right)

梯度为：

∂l(w)∂wj=(yi−f(xi,w))xji, ∀(xi,w)\frac{\partial l(\mathbf w)}{\partial w_j} = (y^i-f(\mathbf x^i,\mathbf w))x^i_j,\ \forall(\mathbf x^i,\mathbf w)

则可以使用梯度下降法更新参数：

wj=wj+α(yi−f(xi,w))xji\textcolor{red}{w_j = w_j + \alpha (y^i - f(\mathbf x^i,\mathbf w))x^i_j}

二、多类Logistic回归

思路是使用softmax函数取代logistic sigmoid：

P(Ck∣w,x)=exp⁡(wkTx)∑j=1Nexp⁡(wjTx)P(C_k\vert\mathbf{w,x}) = \frac{\exp(\mathbf w^T_k\mathbf x)}{\sum\limits_{j=1}^N\exp(\mathbf w_j^T\mathbf x)}

而对于y，使用一个K维的独热表示的向量来代替，它满足：

∑i=1KP(yi∣w,x)=1\sum_{i=1}^KP(y_i\vert\mathbf{w,x}) = 1

同样的，对于样本的概率分布，采用广义伯努利分布表示：

P(y∣μ)=∏i=1Kμiyiμi=P(yi=1∣w,x)\begin{align} &P(\mathbf{y|\mu}) = \prod_{i=1}^K\mathbf \mu_i^{y_i} \nonumber \\ &\mu_i = P(y_i=1\vert \mathbf{w,x}) \end{align}

这样就可以写出似然函数：

P(y1,y2,LyN∣w1,…,wK,x1,…,xN)=∏i=1N∏k=1KP(Ck∣wk,xi)=∏i=1N∏k=1KμikykiP(\mathbf y^1,\mathbf y^2,L\mathbf y^N\vert\mathbf w_1,\dots,\mathbf w_K,\mathbf x^1,\dots,\mathbf x^N) = \prod_{i=1}^N\prod_{k=1}^KP(C_k\vert\mathbf w_k, \mathbf x^i) = \prod_{i=1}^N\prod_{k=1}^K\mu_{ik}^{y_k^i}

其中，μik\mu_{ik}为softmax函数：

μik=exp⁡(wkTxi)∑j=1Kexp⁡(wjTxi)\mu_{ik} = \frac{\exp (\mathbf w_k^T\mathbf x^i)}{\sum\limits_{j=1}^K\exp(\mathbf w_j^T\mathbf x^i)}

那么，最优化问题就可以写成最小化对数似然函数：

min⁡E=min⁡−ln⁡P(y1,…,yN∣w1,…,wK,x1,…,xN)=min⁡−∑i=1N∑k=1Kykiln⁡μik\begin{align} \min{E} &=\min -\ln P(\mathbf y^1,\dots,\mathbf y^N\vert\mathbf w_1,\dots,\mathbf w_K,\mathbf x^1,\dots,\mathbf x^N) \nonumber \\ &= \min \color{red}{-\sum_{i=1}^N\sum_{k=1}^Ky_k^i\ln\mu_{ik}} \end{align}

上式中的EE即为交叉熵损失函数。

对于这个损失函数，采用梯度下降法更新，梯度为：

∂E∂wj=∑i=1N(μij−yji)xi\frac{\partial E}{\partial \mathbf w_j} = \sum_{i=1}^N(\mu_{ij}-y^i_j)\mathbf x^i

6.3.2 高斯判别分析（GDA）

GDA属于生成式模型

GDA使用多变量正态分布对p(x∣y)p(\mathbf x\vert y)进行建模：

y∼Bernoulli(β)(x∣y=0)∼N(μ0,Σ0)(x∣y=1)∼N(μ1,Σ1)\begin{align} y&\sim Bernoulli(\beta) \nonumber \\ (x\vert y = 0) &\sim N(\mathbf\mu_0,\mathbf\Sigma_0) \\ (x\vert y = 1) &\sim N(\mathbf\mu_1,\mathbf\Sigma_1) \end{align}

则对数似然函数为：

L(β,μ0,μ1,Σ)=log⁡∏i=1Np(xi,yi;β,μ0,μ1,Σ)=log⁡∏i=1Np(yi;β)p(xi∣yi;β,μ0,μ1,Σ)\begin{align} L(\beta,\mathbf \mu_0,\mathbf \mu_1,\mathbf \Sigma) &= \log\prod_{i=1}^Np(\mathbf x^i,\mathbf y^i;\beta,\mathbf \mu_0,\mathbf \mu_1,\mathbf \Sigma) \nonumber \\ &=\log\prod_{i=1}^Np(\mathbf y^i;\beta)p(\mathbf x^i\vert\mathbf y^i;\beta,\mathbf \mu_0,\mathbf \mu_1,\mathbf \Sigma) \end{align}

使用MLE，估计各参数为：

β=1N∑i=1NI{yi=1}μk=∑i=1NI{yi=k}xi∑i=1NI{yi=k}k={0,1}Σ=1N∑i=1N(xi−μyi)(xi−μyi)T\begin{align} \beta &=\frac1N\sum_{i=1}^NI_{\{y^i=1\}} \nonumber \\ \mu_k &= \frac{\sum\limits_{i=1}^NI_{\{y^i=k\}}x^i}{\sum\limits_{i=1}^NI_{\{y^i=k\}}} &k=\{0,1\} \\ \Sigma&= \frac1N\sum_{i=1}^N(\mathbf x^i - \mathbf\mu_{y^i})(\mathbf x^i - \mathbf\mu_{y^i})^T \end{align}

GDA与LR的区别

  • GDA有很强的模型假设：当假设是正确时，处理数据的效率更高

  • LR假设很弱：对偏离假设的情况更具鲁棒性

  • 实际中，LR更常用

  • 在GDA中，特征向量x中的元素是连续的实数

    • 若特征向量中元素是离散的：p(x1,…,xD∣y)p(x_1,\dots,x_D\vert y)

6.3.3 朴素贝叶斯（NB）

NB属于生成式模型

假设给定y时，特征分量xjx_j相互独立：

p(x1,…,xD∣y)=∏i=1Dp(xi∣y)p(x_1,\dots,x_D\vert y) = \prod_{i=1}^Dp(x_i\vert y)

那么对于给定的训练数据(xi,yi)(\mathbf x^i,y^i)，i=1,…,Ni=1,\dots,N，对数似然为：

L=∑i=1N∑j=1D[log⁡p(xji∣yi)+log⁡p(yi)]L = \sum_{i=1}^N\sum_{j=1}^D\left[\log p(\mathbf x_j^i\vert y^i) + \log p(y^i)\right]

使用MLE，估计各参数为：

p(xj=1∣y=1)=∑i=1NI{xji=1,yi=1}∑i=1NI{yi=1}p(xj=1∣y=0)=∑i=1NI{xji=1,yi=0}∑i=1NI{yi=0}p(y=1)=∑i=1NI{yi=1}N\begin{align} &p(x_j=1\vert y=1) = \frac{\sum\limits_{i=1}^NI_{\{x_j^i=1,y^i=1\}}}{\sum\limits_{i=1}^NI_{\{y^i=1\}}} \nonumber \\ &p(x_j=1\vert y=0) = \frac{\sum\limits_{i=1}^NI_{\{x_j^i=1,y^i=0\}}}{\sum\limits_{i=1}^NI_{\{y^i=0\}}} \\ &p(y=1) = \frac{\sum\limits_{i=1}^NI_{\{y^i=1\}}}{N} \end{align}

基于此，即可做出预测：

p(y=1∣x)=p(x∣y=1)p(y=1)p(x)=∏j=1Dp(xj∣y=1)p(y=1)∏j=1Dp(xj∣y=1)p(y=1)+∏j=1Dp(xj∣y=0)p(y=0)\begin{align} p(y=1\vert x) &=\frac{p(x\vert y=1)p(y=1)}{p(x)} \nonumber \\ &= \frac{\prod\limits_{j=1}^Dp(x_j\vert y=1)p(y=1)}{\prod\limits_{j=1}^Dp(x_j\vert y=1)p(y=1) + \prod\limits_{j=1}^Dp(x_j\vert y=0)p(y=0)} \end{align}

平滑

对于给定的训练集{x1,…,xN}\{x^1,\dots,x^N\}，利用最大似然估计可以估计变量xx取每个值的概率：

p(x=j)=∑i=1NI{xi=j}N, j=1,…,Kp(x=j)=\frac{\sum\limits_{i=1}^NI_{\{\mathbf x^i=j\}}}{N},\ j=1,\dots,K

然而，如果训练集中某个类别的数据没有涵盖xx的第mm个取值的话，就无法估计相应的条件概率，从而导致模型可能会在测试集上产生误差

对此，可以使用Laplace平滑，在各个估计中加入平滑项：

p(x=j)=∑i=1NI{xi=j}+1N+K, j=1,…,Kp(x=j)=\frac{\sum\limits_{i=1}^NI_{\{\mathbf x^i=j\}}+1}{N+K},\ j=1,\dots,K

NB与LR的区别

  • 渐进比较

    • 当模型假设正确：NB与LR产生相似的分类器

    • 当模型假设不正确

      • LR不假设条件具有独立性，偏差较小

      • LR的表现优于NB

  • 非渐进比较

    • 参数估计的收敛性

      • NB：O(log⁡N)O(\log N)

      • LR：O(N)O(N)

本节绘图代码

import numpy as np
import matplotlib.pyplot as plt

np.random.seed(0)

mean = np.array([0, 0])
cov = np.eye(2)
data = np.random.multivariate_normal(mean, cov, (2, 2))

x = np.linspace(-4, 4, 30)
y = np.linspace(-4, 4, 30)
X, Y = np.meshgrid(x, y)

Z = np.zeros_like(X)
for i in range(len(x)):
    for j in range(len(y)):
        point = np.array([x[i], y[j]])
        Z[j, i] = np.exp(-0.5 * np.dot(np.dot((point - mean), np.linalg.inv(cov)), (point - mean).T))

fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.plot_surface (X, Y, Z, cmap='viridis', shade=False)

plt.show()
上一页6.2 回归任务下一页附 第六章作业

最后更新于