线性分类

综述：线性分类包括什么？

对于分类任务，线性回归模型就无能为力了，但是我们可以在线性模型的函数进行后再加入一层激活函数

下面我们依次介绍几种线性分类模型

硬输出：感知机

我们要解决的问题是：二分类N个样本点(x_i, y_i)，其中x_i ∈ R^p
引入： $$sign(a)=\left\{\begin{matrix}+1,a\geq0\\-1,a<0\end{matrix}\right.$$

感知机的思路是把线性回归的结果填充到激活函数中：
f(x) = sign(w^Tx)

这样f(x)即为预测结果。
此时，问题变为如何求解w。我们使用梯度下降的策略，那么自然的需要引入loss函数。为了引入合适的loss函数，做一些必要的讨论

我们考虑一个被正确分类的点(x_i, y_i)，若 w^Tx_i > 0，则 y_i = +1,若w^Tx_i < 0，则 y_i = −1,因此对于正确分类的点(x_i, y_i)，总有y_iw^Tx_i > 0

综上所述，我们引入形如下式的loss函数 L(w) = ∑_{xi ∈ 𝒟wrong} − y_iw^Tx_i

应用梯度下降法可得

$$\frac\partial{\partial w}L(w)=\sum_{x_i\in\mathcal{D}_{wrong}}-y_ix_i$$

w^t + 1 ← w^t + λy_ix_i

硬输出：线性判别

在 LDA 中，我们的基本想法是选定一个方向，将试验样本顺着这个方向投影，投影后的数据需要满足两个条件，从而可以更好地分类：

1. 相同类内部的试验样本距离接近。
2. 不同类别之间的距离较大。

引入x顺着w方向的投影(有正有负的标量)

z = w^T ⋅ x( = |w|⋅|x|cos θ)

假设属于两类C₁, C₂的样本点数量是N₁, N₂,我们采用方差矩阵来表征两个类内的总体分布

$$\begin{aligned} &C_1:Var_z[C_1] =\frac1{N_1}\sum_{i=1}^{N_1}(z_i-\overline{z_{c1}})(z_i-\overline{z_{c1}})^T \\ &=\frac1{N_1}\sum_{i=1}^{N_1}(w^Tx_i-\frac1{N_1}\sum_{j=1}^{N_1}w^Tx_j)(w^Tx_i-\frac1{N_1}\sum_{j=1}^{N_1}w^Tx_j)^T \\ &=w^T\frac1{N_1}\sum_{i=1}^{N_1}(x_i-\overline{x_{c1}})(x_i-\overline{x_{c1}})^Tw \\ &=w^TS_1w \\ &C_2:Var_z[C_2] =\frac1{N_2}\sum_{i=1}^{N_2}(z_i-\overline{z_{c2}})(z_i-\overline{z_{c2}})^T \\ &=w^TS_2w \end{aligned}$$

其中S₁, S₂就定义为两个类的方差矩阵，我们想让类内距离小，必然希望两个类的类内距离都是小的，为此定义类内距离函数为 Var_z[C₁] + Var_z[C₂] = w^T(S₁ + S₂)w

同时定义类间距离为

$$\begin{aligned} (\overline{z_{c1}}-\overline{z_{c2}})^2& =(\frac1{N_1}\sum_{i=1}^{N_1}w^Tx_i-\frac1{N_2}\sum_{i=1}^{N_2}w^Tx_i)^2 \\ &=(w^T(\overline{x_{c1}}-\overline{x_{c2}}))^2 \\ &=w^T(\overline{x_{c1}}-\overline{x_{c2}})(\overline{x_{c1}}-\overline{x_{c2}})^Tw \end{aligned}$$

用两个值相除作为损失函数，我们要求的w就是

$$\begin{aligned} \hat{w}=argmax J(w)& =argmax\frac{(\overline{z_{c1}}-\overline{z_{c2}})^2}{Var_z[C_1]+Var_z[C_2]} \\ &=argmax\frac{w^T(\overline{x_{c1}}-\overline{x_{c2}})(\overline{x_{c1}}-\overline{x_{c2}})^Tw}{w^T(S_1+S_2)w} \\ &=\underset{w}{\operatorname*{argmax}}\frac{w^TS_bw}{w^TS_ww} \end{aligned}$$

显然，我们并不需要知道w的具体大小，我们只需要知道w的方向即可，对损失函数求导

$$\frac\partial{\partial w}J(w)=0$$

$$\begin{aligned}&\Longrightarrow S_bw(w^TS_ww)=(w^TS_bw)S_ww\\&\Longrightarrow w\propto S_w^{-1}S_bw=S_w^{-1}(\overline{x_{c1}}-\overline{x_{c2}})(\overline{x_{c1}}-\overline{x_{c2}})^Tw\propto S_w^{-1}(\overline{x_{c1}}-\overline{x_{c2}})\end{aligned}$$

$S_w^{-1}(\overline{x_{c1}}-\overline{x_{c2}})$就是w的方向，再进行归一化即可。 w^Tx = 0就是我们的决策边界

软输出：逻辑回归

对于一次观测，获得分类y的概率为(假定C₁ = 1, C₂ = 0 ): p(y|x) = p₁^yp₀^1 − y 那么对于N次独立全同的观测 MLE为： $$\hat{w}=argmax_wJ(w)=argmax_w\sum_{i=1}^N(y_i\log p_1+(1-y_i)\log p_0)$$

接着使用梯度下降推导即可，我们相当于在这里直接导出了交叉熵函数

软输出：高斯判别:关注数据本身特征

假设数据分布满足这样的形式

$\begin{aligned}&1.\quad y\sim Bernoulli(\phi)\\&2.\quad x|y=1\sim\mathcal{N}(\mu_1,\Sigma)\\&3.\quad x|y=0\sim\mathcal{N}(\mu_0,\Sigma)\end{aligned}$

$$argmax_{\phi,\mu_0,\mu_1,\Sigma}\log p(X|Y)p(Y)=argmax_{\phi,\mu_0,\mu_1,\Sigma}\sum_{i=1}^N(\log p(x_i|y_i)+\log p(y_i))$$

利用交叉熵形式技巧把上面的概率式子展开

$$=argmax_{\phi,\mu_0,\mu_1,\Sigma}\sum_{i=1}^N((1-y_i)\log\mathcal{N}(\mu_0,\Sigma)+y_i\log\mathcal{N}(\mu_1,\Sigma)+y_i\log\phi+(1-y_i)\log(1-\phi))$$

求解ϕ,对ϕ求偏导数令其等于零即可 $$\begin{aligned}\sum_{i=1}^N\frac{y_i}\phi+\frac{y_i-1}{1-\phi}=0\\\sum_{i=1}^Ny_i\\\Longrightarrow\phi=\frac{\sum_{i=1}^Ny_i}N=\frac{N_1}N\end{aligned}$$

求解μ₁,对μ₁求偏导

$$\begin{aligned} \hat{\mu}_{1}& =argmax_{\mu_1}\sum_{i=1}^Ny_i\log\mathcal{N}(\mu_1,\Sigma) \\ &=argmin_{\mu_1}\sum_{i=1}^Ny_i(x_i-\mu_1)^T\Sigma^{-1}(x_i-\mu_1) \end{aligned}$$

$$\mu_1=\frac{\sum_{i=1}^Ny_ix_i}{\sum_{i=1}^Ny_i}=\frac{\sum_{i=1}^Ny_ix_i}{N_1}$$

根据对称性， $$\mu_0=\frac{\sum_{i=1}^N(1-y_i)x_i}{N_0}$$

求解方差，需要一些技巧，这里直接给出结果

$$\Sigma=\frac{N_1S_1+N_2S_2}N$$

软输出:朴素贝叶斯分类器

链接

$$\begin{aligned} &T=\{(x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{N},y_{N})\} \\ &x_i=(x^1,\ldots,x^n) \\ &y_{i}=c_{k}, \text{其中}k=1\ldots K \\ &&y\neq argmax_{c_k}P(y=c_k)\prod_jP(x^j|y=c_k) \end{aligned}$$

我们选择概率最大的作为分类结果