> For the complete documentation index, see [llms.txt](https://aye10032.gitbook.io/prml-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aye10032.gitbook.io/prml-note/di-liu-zhang-you-jian-du-xue-xi/6.3-fen-lei-wen-ti.md).

# 6.3 分类问题

分类问题的任务：

* **输入**：N个<mark style="color:orange;">**独立同分布（i.i.d）**</mark>的训练样本$$(\mathbf{x}^i,y^i)\in X\times C$$，$$i=1,2,\dots,N$$
* **目标函数**：$$f\in\mathcal{F}$$
* **损失函数**：$$L(f;x,y)=I\_{{f(\mathbf{x}\neq y}}$$
* **期望风险**：$$\int I\_{{f(\mathbf{x}\neq y}}dP(\mathbf{x},y)=P(f(\mathbf{x})\neq y)$$

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

$$
f(\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=-1$$或$$y=1$$的所有样本，都应该有：

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

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

$$
\hat{E}*p(\mathbf{w}) = -\sum*{i\in T\_M}\mathbf{w}^T\mathbf{x}^iy^i
$$

其中，$$T\_M$$为错分样本的集合

### 一些常见的分布

#### 伯努利分布

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

$$
P(x\vert \beta) = \beta^x(1-\beta)^{1-x}
$$

#### 二项式分布

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

$$
P(m\vert N,\beta) = \begin{pmatrix} N\m \end{pmatrix} \beta^m(1-\beta)^{N-m}
$$

#### 多项式分布

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

$$
P(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\sim N(\mu,\Sigma)$$，有

$$
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$$为协方差矩阵的行列式，此分布的图像如下图所示：

![](/files/c21PFhzEWaFrjnuqTeeh)

## 6.3.1 Logistic 回归

{% hint style="warning" %}
Logistic回归属于判别式模型
{% endhint %}

Logistic回归使用<mark style="color:purple;">**Logistic函数**</mark>估计后验概率：

$$
\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}
$$

{% hint style="success" %}
上式中的$$g(x)=\dfrac{1}{1+e^{-z}}$$即为<mark style="color:purple;">**Logistic函数**</mark>，它是一个经典的<mark style="color:purple;">**Sigmoid函数**</mark>

其图像为：![](/files/rvjbrWp1hLM0hKBuFZXy)

Logistic函数具有以下特性：

* $$z \to \infin$$时，$$g(z)\to 1$$
* $$z \to -\infin$$时，$$g(z)\to 0$$
* 取值在0到1之间
* $$g'(z) = g(z)(1-g(z))$$
  {% endhint %}

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

对于二分类问题，可以假设样本的输出服从<mark style="color:purple;">**伯努利分布**</mark>（0-1分布），则对于$$y=0$$和$$y=1$$可以统一表达为：

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

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

$$
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)
$$

梯度为：

$$
\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)
$$

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

$$
\textcolor{red}{w\_j = w\_j + \alpha (y^i - f(\mathbf x^i,\mathbf w))x^i\_j}
$$

### 二、多类Logistic回归

思路是使用<mark style="color:purple;">**softmax函数**</mark>取代logistic sigmoid：

$$
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维的<mark style="color:orange;">**独热表示**</mark>的向量来代替，它满足：

$$
\sum\_{i=1}^KP(y\_i\vert\mathbf{w,x}) = 1
$$

同样的，对于样本的概率分布，采用<mark style="color:purple;">**广义伯努利分布**</mark>表示：

$$
\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(\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}
$$

其中，$$\mu\_{ik}$$为softmax函数：

$$
\mu\_{ik} = \frac{\exp (\mathbf w\_k^T\mathbf x^i)}{\sum\limits\_{j=1}^K\exp(\mathbf w\_j^T\mathbf x^i)}
$$

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

$$
\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}
$$

上式中的$$E$$即为<mark style="color:purple;">**交叉熵损失函数**</mark>。

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

$$
\frac{\partial E}{\partial \mathbf w\_j} = \sum\_{i=1}^N(\mu\_{ij}-y^i\_j)\mathbf x^i
$$

## 6.3.2 高斯判别分析（GDA）

{% hint style="warning" %}
GDA属于生成式模型
{% endhint %}

GDA使用<mark style="color:purple;">**多变量正态分布**</mark>对$$p(\mathbf x\vert y)$$进行建模：

$$
\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}
$$

则对数似然函数为：

$$
\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，估计各参数为：

$$
\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有<mark style="color:orange;">**很强的模型假设**</mark>：当假设是正确时，处理数据的效率更高
* LR<mark style="color:orange;">**假设很弱**</mark>：对偏离假设的情况更具鲁棒性
* 实际中，LR更常用
* 在GDA中，特征向量x中的元素是连续的实数
  * 若特征向量中元素是离散的：$$p(x\_1,\dots,x\_D\vert y)$$

## 6.3.3 朴素贝叶斯（NB）

{% hint style="warning" %}
NB属于生成式模型
{% endhint %}

假设给定y时，特征分量$$x\_j$$<mark style="color:orange;">**相互独立**</mark>：

$$
p(x\_1,\dots,x\_D\vert y) = \prod\_{i=1}^Dp(x\_i\vert y)
$$

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

$$
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，估计各参数为：

$$
\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}
$$

基于此，即可做出预测：

$$
\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}
$$

### 平滑

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

$$
p(x=j)=\frac{\sum\limits\_{i=1}^NI\_{{\mathbf x^i=j}}}{N},\ j=1,\dots,K
$$

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

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

$$
p(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)$$
    * LR：$$O(N)$$

## 本节绘图代码

```python
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()
```