机器学习-分类问题（Classification）

分类问题概述

分类问题是我们日常生活中最常遇到的一类问题，比如垃圾邮件的分类，识别我们所看到的是汽车还是火车抑或是别的物体，再或者去医院医生诊断病人身体里的肿瘤是否是恶性的，这些问题全部都属于分类问题的范畴。那么我们在机器学习中遇到此类问题该怎么做呢？

我们可能首先会想，为什么不能用之前线性回归的方法来处理分类问题呢？答案其实是可以，不过我们在计算损失函数时需要对预测值远远偏离真实值的对象进行打击。理由也很简单，因为这些过大的偏差会使我们的回归结果向减小这类偏差的方向移动，造成下图所示的结果。

很显然，这种做法并不是分类问题的最优解决方案，接下来我们研究一种可靠的分类问题的解法。

二元分类问题（Binary Classification）

首先，我们从二元分类问题开始入手。何谓二元分类问题？通俗讲就是只有两个类别的分类问题，如是不是垃圾邮件，是不是恶性肿瘤这类非黑即白的问题，我们就称之为二元分类问题。

概率解法

如果有两个类别$C_1,C_2$，里面分别包含了$N_1,N_2$个元素。现从两个类别中随机挑出一个元素x，该元素x来自$C_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)}$

在这个公式中，$P(C_1),P(C_2)$的值显而易见：

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

接着，我们假设元素x是从多维高斯分布（GaussianDistribution）中选取出来的，则有：

$P(x|C_1)=f_{\mu_1,\Sigma_1}(x)=\frac{1}{(2\pi)^{D/2}}\frac{1}{|\Sigma_1|^{1/2}}e^{-\frac{1}{2}(x-\mu_1)^T\Sigma_1^{-1}(x-\mu_1)}$

在这个表达式包含两个参数：均值$\mu$，协方差$\Sigma$，如果假设选取样本$x^{(i)}$相互独立，那么所有样本来自该集合概率为：

$L(\mu,\Sigma)=\Pi_{i=1}^{m}f_{\mu,\Sigma}(x^{(i)})$

由于样本$x^{(i)}$本来就是存在于集合中的，所以应该最大化这个概率，根据对数似然估计可得：

$\mu^*,\Sigma^*=arg\ max_{\mu,\Sigma}\ L(\mu,\Sigma)$ $\frac{\partial lnf}{\partial\mu}=0,\ \mu^*=\frac{1}{m}\sum_{i=1}^{m}x^{(i)}$ $\frac{\partial{lnf}}{\partial{\Sigma}}=0,\ \Sigma^*=\frac{1}{m}\sum_{i=1}^{m}(x^{(i)}-\mu^*)^T(x^{(i)}-\mu^*)$

通过对数似然估计我们可以求得$\mu,\Sigma$，进而计算出$P(x|C_1)$。同理我们用相同的方法亦可求得$P(x|C_2)$，最终得到$P(C_1|x)，P(C_2|x)$。

逻辑回归（Logestic Regression）

我们将概率解法中的贝叶斯公式稍作变形可得：

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

这里的$\sigma(z)$是sigmoid函数，其中自变量z为：

$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{N_1}{N_2}$

对于不同的特征$x_i$，选择不同的$\Sigma_i$可能引入过多变量导致过拟合现象，因此我们对于所有特征选择相同的$\Sigma$和不同的$\mu_i$计算$P(x|C_i)$，则有:

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

如果我们把x前的系数$(\mu_1-\mu_2)^T\Sigma^{-1}$看作参数向量$[\theta_1,\theta_2 \dots \theta_n]$，x后其他项看作常数$\theta_0$：

$z=\theta^Tx+\theta_0$

将上述公式整理后，即可得预测函数：

$h_\theta(X)=\frac{1}{1+e^{-\theta^TX}}\in[0,1]$ $\begin{equation} y = \begin{cases} 0, & h_\theta(X)<0.5 \\ 1, & h_\theta(X)\geq 0.5 \end{cases} \end{equation}$

损失函数（Cost Function）

在分类问题中，我们采用交叉熵作为损失函数，表达式为：

$\begin{equation} Cost(h_{\theta}(x),\hat{y})=\begin{cases} -log(1-h_{\theta}(x)), & \hat{y}=0 \\ -log(h_{\theta}(x)), & \hat{y}=1 \end{cases} \end{equation}$

从函数图像中，我们更能直观理解交叉熵函数是怎样运作的

$\hat{y}=0，\begin{cases} Cost(h,x)\rightarrow0, & h_\theta(x)\rightarrow0 \\ Cost(h,x)\rightarrow\infty, & h_\theta(x)\rightarrow1 \end{cases}$ $\hat{y}=1，\begin{cases} Cost(h,x)\rightarrow\infty, & h_\theta(x)\rightarrow0 \\ Cost(h,x)\rightarrow0, & h_\theta(x)\rightarrow1 \end{cases}$

很显然，这也是符合我们预期的，当预测值和真实值相近时损失函数较小，当预测值和真实值相差接近1时损失函数值很大。于是，我们将上述两式合并起来写如一个表达式中，即得二元分类下的交叉熵损失函数（Cross Entropy Error）：

$J(\theta)=\frac{1}{m}\sum_{i=1}^{m}Cost(h_{\theta}(x^{(i)}),\hat{y^{(i)}})$ $Cost(h_{\theta}(x^{(i)}),\hat{y^{(i)}})=-\hat{y^{(i)}}log(-h_{\theta}(x^{(i)}))-(1-\hat{y^{(i)}})log(1-h_{\theta}(x^{(i)}))$

写做矩阵形式为：

$J(\theta)=-\frac{1}{m}[y^Tlog(h_\theta(X))+(1-y)^Tlog(h_\theta(X))]$

为什么不用平方代价函数了呢？从函数图像中可以很清楚的得知原因。平方代价函数的梯度在接近目标值时趋近于零，但在离目标值很远的时候梯度仍然趋近于零，这就有可能导致我们无法用梯度下降的方法来优化参数向靠近目标值的方向移动。然而交叉熵代价函数在远离目标值时会提供一个很大的梯度值，越靠近目标值相应梯度越小直至趋近于零，这显然是符合梯度下降步长要求的。

梯度下降（Gradient Descent）

我们仍然采用梯度下降的方法来最优化参数向量$\theta$，求偏导后我们得到更新公式为：

$\theta_j:=\theta_j-\alpha\frac{\partial J(\theta)}{\partial \theta_j}=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$

写作矩阵形式为：

$\theta:=\theta-\alpha\frac{1}{m}X^T(h_\theta(X)-y)$

除了梯度下降外，还有些更加复杂的优化算法，但实现起来比较困难。不过在octave中内置了最小化无约束多变量函数fminunc可以帮助我们快速实现求解函数最小值的功能。

# 构建一个函数返回损失函数值和梯度
function [jVal, gradient] = costFunction(theta)
  jVal = [...code to compute J(theta)...];
  gradient = [...code to compute derivative of J(theta)...];
end

#使用fminunc计算最小值functionVal和最小值对应的参数向量optTheta
options = optimset('GradObj', 'on', 'MaxIter', 100);
initialTheta = zeros(2,1);
[optTheta, functionVal, exitFlag] = fminunc(@costFunction, initialTheta, options);

正则化（Regularization）

关于正则化已经在上一篇博文中详细介绍过，概括来说通过正则化的方法可以简化我们的预测函数，降低在梯度下降过程中发生过拟合现象的风险，正则化后的逻辑回归表达式为：

$J(\theta)=-\frac{1}{m}\sum_{i=1}^{m}(\hat{y^{(i)}}log(-h_{\theta}(x^{(i)}))+(1-\hat{y^{(i)}})log(1-h_{\theta}(x^{(i)})))+\frac{\lambda}{2m}\sum_{j=1}^{n}\theta_j^2$ $\theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}$ $\theta_j:=\theta_j-\alpha\frac{1}{m}[\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}]+\frac{\lambda}{m}\theta_j$

需要特别注意的是——只需要将$\theta_1,\theta_2,\dots,\theta_n$进行正规化，而$\theta_0$不需要正规化！

多元分类问题（Muti-Classification）

了解了二元分类问题，我们接着简单分析一下多元分类问题。对于多分类问题通常有两种解法：

将多分类问题划分成n个二分类问题
softmax函数替代sigmoid函数作为预测函数

转化为二元分类问题

这种做法的思路很简单，即单独取出一类，并把其他n-1类共同划分为一类应用二元分类问题求出属于该类的概率；同理再将剩下n-1类用同样的方法算出概率，选择概率最大的一类作为预测结果即可。

softmax函数

第二种方法则用到了在神经网络中经常用于处理输出层的softmax函数，这里只做简要介绍。

softmax是指数归一化函数，表达式为：

$Softmax(x_i)=\frac{e^{x_i}}{\sum_{j=1}^{n}e^{x_j}}$

在多元分类问题中常用softmax + crossEntropy的组合去处理分类问题，写成矩阵形式为：

$J(\theta) = -y^Tlog\ Softmax(X\theta)$

对向量$\theta$求导可以得到：

$\frac{\partial J}{\partial \theta}=X^T(Softmax(X\theta)-y)$

接着使用梯度下降或者其他高级优化算法迭代求解即可。

Logestic Regression存在的问题

就目前而言，逻辑回归还是存在一些情况没有办法处理，就拿逻辑运算异或（XOR）来说，如果将它表示在平面坐标内（如下图一），可以看出无论用直线怎么分割都不可能将y=1和y=0的两部分恰好划分在直线两侧。
解决这个问题的方法是对原本的输入特征$x_1,x_2$进行特征变换，用$x_1’$表示原特征点到[0,0]的距离，$x_2’$表示原特征点到[1,1]的距离，经过这样的变换后特征点的分布变为下图二，这样我们就很容易可以找到一条直线将y=1，y=0区分开。