Part1-分类问题(细)

这一部分学习自李宏毅老师的机器学习深度学习相关课程

对于分类这件事，我们需要找的是一个函数，输入为x，输出是这个输入x对应的属于哪个类别class n，即：

$x \rightarrow function \rightarrow Class\ n$

例：

对于宝可梦游戏而言，输入的是精灵的特征(如总的战斗力、生命值、攻击值、防御值、特殊攻击值、特征防御值、速度等)，输出的是精灵对应的属性类别，如$f(皮卡丘)=雷$

训练集：$(x^{(1)},\hat y^{(1)}),(x^{(2)},\hat y^{(2)}),\cdots,(x^{(m)},\hat y^{(m)})$ (为与吴恩达老师教学保持一致，将目标有所修改)

二分类

使用线性回归

对于训练数据：Class 1意味着目标值是1，Class 2意味着目标值是-1

预测时：采用线性回归方式，输出大于0，则类别接近于Class 1，输出小于0，则类别接近于Class 2

这样会出现如图所示的问题：

如图，蓝色表示Class 1,红色表示Class 2，则$b+w_1x_1+w_2x_2=0$是绿色线，表示两类的分界线，分界线上部表示回归输出小于0，下部表示输出大于0；但是可能会有这种情况：比如，Class 1的分布是右图的情况，这样的话，为了满足右下角的蓝色点在方程中的值接近1，则最终求出的分界线会是紫色这条线，这样分类结果就会有问题了。

此外，对于线性回归用于多分类问题而言，如果将Class 1对应于1，Class 2对应于2，Class 3对应于3等，则会存在以下问题：因为当这样做时，就默认是假设Class 3和Class 2是比较接近的，它们有某种关系，Class 2和Class 1是比较近的，它们有某种关系，但如果实际上这种关系不存在，这样将它作为一个线性回归问题来处理就没有办法得到一个好的结果。

理想做法

模型：

损失函数(Loss function)：$L(f)=\sum_m \delta(f(x^{(m)}\ne \hat y^{(m)}))$（预测结果错误的次数）

但是，这样的模型和损失函数，并不能微分，也就不能梯度下降，但可以使用感知机(Perceptron)或支持向量机(SVM)来解决，但这里不用。

概率模型

如图

则

一个蓝球，从$B_1$中抽出来的概率：$P(B_1|Blue)=\frac{P(Blue|B_1)P(B_1)}{P(Blue|B_1)P(B_1)+P(Blue|B_2)P(B_2)}$

对应的，如果将盒子换成类别则：

给定一个x，则它从对应类别抽出来的概率：

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

要计算$P(C_1|x)$，就必须知道$P(C_1)、P(x|C_1)、P(C_2)、P(x|C_2)$

这一整套想法，叫做生成模型(Generative Model)，因为根据这些，可以计算任一x产生的概率，$P(x)=P(x|C_1)P(C_1)+P(x|C_2)P(C_2)$

先验概率

以宝可梦为例，数据集中79只水系，61只一般系，则：

$P(C_1)=\frac{79}{79+61}=0.56$

$P(C_2)=\frac{61}{79+61}==0.44$

从类别中挑选出某一只的概率：

$P(x|C_1)=？$

假设只考虑防御力和特殊防御力两个特征，则79只水系的分布情况大概如图所示：

那么，对于一只没有在79只宝可梦中的水系新宝可梦，则对应求出的概率难道就是0？

所以，需要想办法从这些已经有的宝可梦估测，如果从所有水系宝可梦中选一个，则对应的是这个新宝可梦的概率。

解决：

可以想象为，这79只宝可梦，只是水系中的一小部分，即它们的防御力和特殊防御力是从一个高斯分布中抽样出来的，而从这个高斯分布中，抽取到新宝可梦对应防御力和特殊防御力对应点的概率并不为0。

高斯分布(正态分布)：

$f_{\mu,\Sigma}(x) = \frac{1}{(2\pi)^{D/2}}\frac{1}{|\Sigma|^{1/2}}exp\{-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\}$

高斯分布可以看作：一个输入为向量$x$，输出为$x$从这一分布中被抽取出来的概率(实际是概率密度)的函数，这个函数则是由均值(期望)$\mu$和方差$\Sigma$决定

接下来，我们需要做的就是根据上述79个样本，来估计出$\mu$和$\Sigma$

方法：极大似然估计(Maximum Likelihood)

可以想象成，这79个点，其实可以从任何一个高斯分布中被抽取出来，因为从一个高斯分布中可以抽取出空间上的任意一点，只是有的地方概率高，有的地方概率低。

但是，虽然说每个高斯分布都可以抽取出这79个样本，但它们抽取这79个样本的可能性并不一样。

对于一个高斯分布：

$Likelihood=从高斯分布中抽取到x^{(1)},x^{(2)},\cdots,x^{(79)}的概率$

即：$L(\mu,\Sigma)$（此处$L$表示Likelihood，而非Loss）

由于这79个点是独立从高斯分布中抽取出来的，所以：

$L(\mu,\Sigma)=f_{\mu,\Sigma}(x^{(1)})f_{\mu,\Sigma}(x^{(2)})\cdots f_(\mu,\Sigma)(x^{79})$

然后我们需要就是对应$L(\mu,\Sigma)$最大时的$\mu^*$和$\Sigma^*$，即：

$\mu^*,\Sigma^*=arg\ \max_{\mu,\Sigma}L(\mu,\Sigma)$

求解：

$\mu^*=\frac{1}{79}\sum_{n=1}^{79}x^{(n)}$

$\Sigma^*=\frac{1}{79}\sum_{n=1}^{79}(x^{(n)}-\mu^*)(x^{(n)}-\mu^*)^T$

代入到具体数值，可以计算出：

$\mu^1=\left[ \begin{matrix} 75.0 \\ 71.3 \end{matrix} \right] \ \Sigma^1=\left[ \begin{matrix} 874 & 327 \\ 327 & 929 \end{matrix} \right]$

同理，求出一般系对应的：

$\mu^2=\left[ \begin{matrix} 55.6 \\ 59.8 \end{matrix} \right] \ \Sigma^2=\left[ \begin{matrix} 847& 422 \\ 422& 685\end{matrix} \right]$

### 开始分类

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

将上述计算代入后，如果$P(C_1|x)>0.5$，则x属于Class 1

至此，就得到了一个模型来解决这个分类问题。

模型改良

上述得出：

$\mu^1=\left[ \begin{matrix} 75.0 \\ 71.3 \end{matrix} \right] \ \Sigma^1=\left[ \begin{matrix} 874 & 327 \\ 327 & 929 \end{matrix} \right]$

$\mu^2=\left[ \begin{matrix} 55.6 \\ 59.8 \end{matrix} \right] \ \Sigma^2=\left[ \begin{matrix} 847& 422 \\ 422& 685\end{matrix} \right]$

其实这在实际中是比较少见的，实际中，通常不会给第一个高斯分布都有自己的$\mu$和$\Sigma$，比较常见的做法是不同的类别可以共用同一个$$，这样就可以减少参数量，由此：

$L(\mu^1,\mu^2,\Sigma)=f_{\mu^1,\Sigma}(x^{(1)})f_{\mu^1,\Sigma}(x^{(2)})\cdots f_{\mu^1,\Sigma}(x^{(79)}) \times f_{\mu^2,\Sigma}(x^{(80)})f_{\mu^2,\Sigma}(x^{(81)})\cdots f_{\mu^2,\Sigma}(x^{(140)})$

$\Sigma = \frac{79}{140}\Sigma^1+\frac{61}{140}\Sigma^2$

如图，当$\Sigma$取一样时，分界线就是一条线性的：

总结：三步：

函数模型：

函数好坏：使用$\mu$和$\Sigma$进行极大似然估计

为什么使用高斯分布呢？

没有原因，也可以使用别的，只是高斯分布使用比较多而已。

另外一种常见的假设：

假设$P(x|C_1)$中的$x=\left[\begin{matrix} x_1 \\ x_2 \\ \cdots \\ x_k \\ \cdots \\ x_K \end{matrix} \right]$,其中$x_k$表示对应的第k个特征

假设每个维度从概率模型中产生出来的概率是独立的，则

$P(x|C_1)=P(x_1|C_1)P(x_2|C_1)\cdots P(x_k|C_1)\cdots$

可以说第一个概率$P(x_k|C_1)$分别都是一维的高斯分布(1-D Gaussian)，这样就可以更加减少参数量。

以上这种假设处理方法也叫做朴素贝叶斯(Naive Bayes Classifier)

后验概率分析

$\begin{split} 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+\frac{P(x|C_2)P(C_2)}{P(x|C_1)P(C_1)}}\end{split}$

假设：$z=\ln\frac{P(x|C_1)P(C_1)}{P(x|C_2)P(C_2)}$

则：

$P(C_1|x)=\frac{1}{1+exp(-z)}=\sigma(z)$

这个函数$\sigma(z)$就叫做激活函数，对应的曲线图如图：

具体计算z：(数学警告)

$\begin{split} z&=\ln\frac{P(x|C_1)P(C_1)}{P(x|C_2)P(C_2)}\\ &= \ln\frac{P(x|C_1)}{P(x|C_2)}+\ln\frac{P(C_1)}{P(C_2)}\end{split}$

使用$N_1$表示Class 1在训练数据中出现的次数，$N_2$表示Class 2在训练数据中出现的次数则

$\frac{P(C_1)}{P(C_2)}=\frac{\frac{N_1}{N_1+N_2}}{\frac{N_2}{N_1+N_2}}=\frac{N_1}{N_2}$

$P(x|C_1)= \frac{1}{(2\pi)^{D/2}}\frac{1}{|\Sigma^1|^{1/2}}exp\{-\frac{1}{2}(x-\mu^1)^T(\Sigma^1)^{-1}(x-\mu^1)$

$P(x|C_2)= \frac{1}{(2\pi)^{D/2}}\frac{1}{|\Sigma^2|^{1/2}}exp\{-\frac{1}{2}(x-\mu^2)^T(\Sigma^2)^{-1}(x-\mu^2)$

$\begin{split} \ln\frac{P(x|C_1)}{P(x|C_2)} &=\ln\frac{\frac{1}{(2\pi)^{D/2}}\frac{1}{|\Sigma^1|^{1/2}}exp\{-\frac{1}{2}(x-\mu^1)^T(\Sigma^1)^{-1}(x-\mu^1)}{\frac{1}{(2\pi)^{D/2}}\frac{1}{|\Sigma^2|^{1/2}}exp\{-\frac{1}{2}(x-\mu^2)^T(\Sigma^2)^{-1}(x-\mu^2)} \\ &=\ln\frac{|\Sigma^2|^{1/2}}{|\Sigma^1|^{1/2}}exp\{-\frac{1}{2}[(x-\mu^1)^T(\Sigma^1)^{-1}(x-\mu^1) \\ &-(x-\mu^2)^T(\Sigma^2)^{-1}(x-\mu^2)] \} \\ &=\ln\frac{|\Sigma^2|^{1/2}}{|\Sigma^1|^{1/2}}-\frac{1}{2}[(x-\mu^1)^T(\Sigma^1)^{-1}(x-\mu^1) \\ &-(x-\mu^2)^T(\Sigma^2)^{-1}(x-\mu^2)] \end{split}$

$\begin{split} &(x-\mu^1)^T(\Sigma^1)^{-1}(x-\mu^1) \\ &=x^T(\Sigma^1)^{-1}x - x^T(\Sigma^1)^{-1}\mu^1-(\mu^1)^T(\Sigma^1)^{-1}x+(\mu^1)^T(\Sigma^1)^{-1}\mu^1 \\ &= x^T(\Sigma^1)^{-1}x - 2(\mu^1)^T(\Sigma^1)^{-1}x+(\mu^1)^T(\Sigma^1)^{-1}\mu^1 \end{split}$

$\begin{split} &(x-\mu^2)^T(\Sigma^2)^{-1}(x-\mu^2) \\ &=x^T(\Sigma^2)^{-1}x - x^T(\Sigma^2)^{-1}\mu^2-(\mu^2)^T(\Sigma^2)^{-1}x+(\mu^2)^T(\Sigma^2)^{-1}\mu^2 \\ &= x^T(\Sigma^2)^{-1}x - 2(\mu^2)^T(\Sigma^2)^{-1}x+(\mu^2)^T(\Sigma^2)^{-1}\mu^2 \end{split}$

$\Rightarrow \begin{split} z &=\ln\frac{|\Sigma^2|^{1/2}}{|\Sigma^1|^{1/2}} - \frac{1}{2}x^T(\Sigma^1)^{-1}x+(\mu^1)^T(\Sigma^1)^{-1}x-\frac{1}{2}(\mu^1)^T(\Sigma^1)^{-1}\mu^1 \\ &+\frac{1}{2}x^T(\Sigma^2)^{-1}x-(\mu^2)^T(\Sigma^2)^{-1}x+\frac{1}{2}(\mu^2)^T(\Sigma^2)^{-1}\mu^2+\ln\frac{N_1}{N_2} \end{split}$

因为$\Sigma$共用的，所以$\Sigma_1=\Sigma_2=\Sigma$，所以简化后：

$z = (\mu^1-\mu^2)^T\Sigma^{-1}x-\frac{1}{2}(\mu^1)^T(\Sigma^1)^{-1}\mu^1+\frac{1}{2}(\mu^2)^T(\Sigma^2)^{-1}\mu^2+\ln\frac{N_1}{N_2}$

假设：$w^T=(\mu^1-\mu^2)^T\Sigma^{-1}$ ；$b=-\frac{1}{2}(\mu^1)^T(\Sigma^1)^{-1}\mu^1+\frac{1}{2}(\mu^2)^T(\Sigma^2)^{-1}\mu^2+\ln\frac{N_1}{N_2}$

则$z=w^Tx+b$

$P(C_1|x)=\sigma(wx+b)$

这也就是为什么，我们前面将$\Sigma_1$和$\Sigma_2$共用时，分界线成为了一条线性的

逻辑回归

函数：$f_{w,b}(x)=P_{w,b}(C_1|x)$

$P_{w,b}(C_1|x)=\sigma(z) \\ z=wx+b=\sum_iw_ix_i+b$

如果使用图像的方式来表示，就是如图所示：

损失函数

训练数据：

$\begin{matrix} x^{(1)} & x^{(2)} & x^{(3)} & \cdots & x^{(m)} \\ C_1 & C_1 & C_2 & \cdots & C_1 \\ \hat y^{(1)}=1 & y^{(2)}=1 & y^{(3)}=0 & \cdots & y^{(m)}=1\end{matrix}$

$L(w,b)=f_{w,b}(x^{(1)})f_{w,b}(x^{(2)})(1-f_{w,b}(x^{(3)}))\cdots f_{w,b}(x^{(m)})$

最好的$w^*,b^*$就是当$L(w,b)$最大时对应的$w,b$，即：

$w^*,b^*=\arg \max_{(w,b)} L(w,b) \Leftrightarrow w^*,b^*=\arg \min_{(w,b)}-\ln L(w,b)$

$-\ln L(w,b)=-\ln f_{w,b}(x^{(1)})-\ln f_{w,b}(x^{(2)})-\ln (1-f_{w,b}(x^{(3)})) \cdots$

而$-\ln f_{w,b}(x^{(i)})=-[\hat y^{(i)}\ln f(x^{(i)})+(1-\hat y^{(i)})\ln (1-f(x^{(i)}))]$

所以：

$-\ln L(w,b)=\sum_i -[\hat y^{(i)}\ln f(x^{(i)})+(1-\hat y^{(i)})\ln (1-f(x^{(i)}))]$

$-[\hat y^{(i)}\ln f(x^{(i)})+(1-\hat y^{(i)})\ln (1-f(x^{(i)}))]$:两个伯努利分布之间的交叉熵

交叉熵：

对于分布p：$p(x=1)=\hat y^{(m)};p(x=0)=1-\hat y^{(m)}$

q：$q(x=1)=f(x^{(m)});q(x=0)=1-f(x^{(m)})$

二者的交叉熵：$H(p,q)=-\sum_xp(x)\ln(q(x))$

为什么使用交叉熵，而不使用线性回归中的均方误差？

如果使用均方误差，则在计算$\frac{\part L}{\part w_i}时$：

对于真实值 $\hat y^{(m)}=1$时

如果$f_{w,b}(x^{(m)})=1$（接近真实值），则$\frac{\part L}{\part w_i}=0$;

如果$f_{w,b}(x^{(m)})=0$（远离真实值），则$\frac{\part L}{\part w_i}=0$;

对于真实值$\hat{y}^{(m)}=0$时，同理

对于交叉熵而言，距离目标越远，则对应下降越快，距离目标越近，则下降越慢

而对于均方误差，距离目标远时，下降也很慢

梯度下降

$\frac{\part \ln f_{w,b}(x)}{\part w_i}=\frac{\part \ln f_{w,b}(x)}{\part z}\frac{\part z}{\part w_i}$

$f_{w,b}(x)=\sigma(z)=\frac{1}{1+exp(-z)} \; z=wx+b=\sum_i w_ix_i + b$

$\Rightarrow$

$\frac{\part\ln f_{w,b}(x)}{\part z}=\frac{\part\ln \sigma(z)}{\part z}=\frac{1}{\sigma(z)}\frac{\part \sigma(z)}{\part z} = \frac{1}{\sigma(z)}\sigma(z)(1-\sigma(z))=1-\sigma(z)$；$\frac{\part z}{\part w_i}=x_i$

同理：

$\frac{\part \ln (1-f_{w,b}(x))}{\part w_i}=\frac{\part \ln (1-f_{w,b}(x))}{\part z}\frac{\part z}{\part w_i}$

$\frac{\part \ln (1-f_{w,b}(x))}{\part z}=-\frac{1}{1-\sigma(z)}\frac{\part\sigma(z)}{\part z}=-\frac{1}{1-\sigma(z)}\sigma(z)(1-\sigma(z))=\sigma(z)$

所以：

$\frac{-\part \ln L(w,b)}{\part w_i} = \sum_m-[\hat y^{(m)}\frac{\part \ln f_{w,b}(x^{(m)})}{\part w_i}+(1-\hat y^{(m)})\frac{\ln (1-f_{w,b}(x^{(m)}))}{\part w_i} \\ = \sum_m -[\hat y^{(m)}(1-f_{w,b}(x^{(m)}))x_i^{(m)}-(1-\hat y^{(m)})f_{w,b}(x^{(m)})x_i^{(m)}] \\ =\sum_m-[\hat y^{(m)}-\hat y^{(m)}f_{w,b}(x^{(m)})-f_{w,b}(x^{(m)})+\hat y^{(m)}f_{w,b}(x^{(m)})]x_i^{(m)} \]\\ =\sum_m-(\hat y^{(m)}-f_{w,b}(x^{(m)}))x_i^{(m)}$

$w_i \leftarrow w_i - \eta \Sigma_n -(\hat y^{(m)}-f_{w,b}(x^{(m)}))x_i^{(m)}$

逻辑回归 VS. 线性回归：

Logistic Regression	Linear Regression
$f_{w,b}(x)=\sigma(\sum_iw_ix_i+b)$ 输出：[0,1]	$f_{w,b}(x)=\sum_iw_ix_i+b$ 输出：任意值
$L(f)=\sum_mC(f(x^{(m)}),\hat y^{(m)})$ $\hat y^{(m)}:类别1:1；类别2:0$	$L(f)=\frac{1}{2}\sum_m(f(x^{(m)})-\hat y^{(m)})^2$ $y^{(m)}：一个真实值 $
$w_i \leftarrow w_i - \eta \Sigma_n -(\hat y^{(m)}-f_{w,b}(x^{(m)}))x_i^{(m)}$	$w_i \leftarrow w_i - \eta \Sigma_n -(\hat y^{(m)}-f_{w,b}(x^{(m)}))x_i^{(m)}$

交叉熵：$C(f(x^{(m)}),\hat y^{(m)}) =-[\hat y^{(m)}\ln f(x^{(m)})+(1-\hat y^{(m)})\ln (1-f(x^{(m)}))]$

判别模型 VS. 生成模型

对于函数$P(C_1|x)=\sigma(wx+b)$

在判别模型中，我们直接求得$w,b$

在生成模型中，我们求出$\mu^1,\mu^2,\Sigma^{-1}$，然后$w^T=(\mu^1-\mu^2)^T\Sigma^{-1}；b=-\frac{1}{2}(\mu^1)^T(\Sigma^1)^{-1}\mu^1+\frac{1}{2}(\mu^2)^T(\Sigma^2)^{-1}\mu^2+\ln \frac{N_1}{N_2}$

问：两种模型中求得的$w$和$b$是一样的吗？

答：不是，因为分布不同，前者对于分布没有进行假设，而后者是假设的高斯分布，并且最终得到的结果中，判别模型的结果相对更好一些。

例：训练数据如图：

那么，如图的测试数据是属于哪一类呢？

我们可能都会认为是取自Class 1，而如果使用朴素贝叶斯方法去求呢？

首先，使用朴素贝叶斯则需要假设所有的特征产生的概率互相独立，即$P(x|C_i)=P(x_1|C_i)P(x_2|C_i)$

则：

$P(C_1)=\frac{1}{13}$ $P(x_1=1|C_1)=1$ $P(x_2=1|C_1)=1$

$P(C_2)=\frac{12}{13}$ $P(x_1=1|C_2)=\frac{1}{3}$ $P(x_2=1|C_2)=\frac{1}{3}$

给定上述测试数据后，则可计算其来自Class 1的概率

$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\times 1 \times \frac{1}{13}}{1 \times 1 \times \frac{1}{13}+\frac{1}{3}\times \frac{1}{3}\times \frac{12}{13}} \approx 0.43 < 0.5$

所以，计算结果是该数据来自Class 2

这就是因为，生成模型在计算时，进行了一些假设，这个假设中，可能就有一些与测试数据一样的数据取自Class 1

生成模型的优点：

由于对数据分布进行了假设，因此只需要更少的数据量

由于对数据分布进行了假设，因此其对噪音时有更好的鲁棒性

先验概率和类条件概率分布可以由不同的源来进行估计

多分类

$C_1:w^1,b_1 \ \ z_1=w^1x+b_1$

$C_2:w^2,b_2 \ \ z_2=w^2x+b_2$

$C_2:w^2,b_2 \ \ z_2=w^2x+b_2$

$1>y_i>0$

$\sum_i y_i=1$

$y_i=P(C_i|x)$

逻辑回归的限制

例：

对于如图所示的输入：

则

使用一条直接，无论怎么画，都无法实现正确的分类

这也就是线性模型无法解决异或问题

解决方法：

特征变换

如图，对于原始数据，通过改变数据的值为对应的点到原点的距离，来实现特征的变换

然而，这样同样有一个问题，找到这样一种特征变换方式并不总是这么容易

由此，我们可以采用将多个逻辑回归模型级联的方法解决问题

这样，也就引出了神经网络

Logistic Regression	Linear Regression
\(f_{w,b}(x)=\sigma(\sum_iw_ix_i+b)\) 输出：[0,1]	\(f_{w,b}(x)=\sum_iw_ix_i+b\) 输出：任意值
\(L(f)=\sum_mC(f(x^{(m)}),\hat y^{(m)})\) \(\hat y^{(m)}:类别1:1；类别2:0\)	\(L(f)=\frac{1}{2}\sum_m(f(x^{(m)})-\hat y^{(m)})^2\) $y^{(m)}：一个真实值 $
\(w_i \leftarrow w_i - \eta \Sigma_n -(\hat y^{(m)}-f_{w,b}(x^{(m)}))x_i^{(m)}\)	\(w_i \leftarrow w_i - \eta \Sigma_n -(\hat y^{(m)}-f_{w,b}(x^{(m)}))x_i^{(m)}\)