逻辑回归

与之前的回归问题不同，在分类问题中我们要预测的$y$是离散的值，来尝试区分预测结果的类别。例如判断一封邮件是否是垃圾邮件，或者判断一次金融交易是否涉嫌欺诈。我们先从简单的二元分类问题开始：

二元分类

二元分类是指预测结果分为两类，被称为负向类（negative class）和正向类（positive class）则因变量$y\in {0,1}$，其中$0$表示负向类，$1$表示正向类。

我们不能运用线性回归的方法来解决分类问题，因为分类问题中的$y$取值不会大于$1$或者小于$0$，即$0\leq h_\theta(x) \leq 1$，这是线性回归算法很难保证的。

因此我们利用逻辑回归模型来解决分类问题，该模型的输出变量范围始终在$0$和$1$之间。逻辑回归模型的假设是： $h\theta(x)=g(\theta^Tx)$。其中：$\theta$代表特征向量，$g(z)$代表逻辑函数（logistic function）。逻辑函数可以让$h\theta(x)$落在$[0,1]$区间内部，Sigmoid函数是一个常用的逻辑函数，公式为：

$$g(z) =\frac{1}{1+e^{-z}}$$

函数图像为：

因为$h\theta(x)$的值落在$[0,1]$区间内部，那么可以将$h\theta(x)$理解为：对于给定的输入变量$x$，根据选择的参数$\theta$计算输出变量为$1$的可能性（estimated probability）即:

$$h_\theta(x) = P(y = 1|x;\theta)$$

例如，如果对于给定的$x$，通过已经确定的参数计算得出$h_\theta(x) = 0.7$，则表示有70%的几率$y$为正向类，相应地，$y$为负向类的几率为1-0.7=0.3。

决策边界

在逻辑回归中，当$h\theta(x)\geq0.5$时，我们预测$y =1 $；相应地，当$h\theta(x)\leq0.5$时，我们预测$y = 0$。根据上面的图象可以得知当$z\geq0$时，$g(z)\geq0.5$；当$z\leq0$时，$g(z)\leq0.5$；当$z=0$时，$g(z)=0.5$。

例如下面这个模型：

假设我们已经运用了一些算法求得$\theta^T = \begin{bmatrix}-3&1&1\end{bmatrix}^T$，则当$z = \theta^Tx=-3+x1+x_2\geq0$时，$h\theta(x)\geq0.5$，模型预测$y =1 $；反之，当$z = \theta^Tx=-3+x1+x_2\leq0$时，$h\theta(x)\leq0.5$，模型预测$y =0 $。我们称$-3+x_1+x_2=0$为这个模型的决策边界(decision boundary)，这条线便是我们模型的分界线，将预测为$1$的区域和预测为$0$的区域分隔开。

代价函数

有了新的预测函数$h\theta(x) = \frac{1}{1+e^{-\theta^Tx}}$，我们的代价函数$J(\theta)$也会做出相应的改变，变得不再是一个便于梯度下降找到全局最优解的凸函数（convex function），而将是一个非凸函数（non-convex function）。为了解决这个问题，我们需要重新定义逻辑回归的代价函数$J(\theta) = \frac{1}{m}\sum{i=1}^m Cost(h(x^{(i)})-y^{(i)})^2$:

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

我们还可以将代价函数简化写成：

$$Cost(h_\theta(x),y)=-y\times log(h_\theta(x))-(1-y)\times log(1-h_\theta(x))$$

这样构建的$Cost(h\theta(x),y)$函数的特点是：当实际的$y=1$且$h\theta(x)$也为 1 时误差为 0，当 $y=1$但$h\theta(x)$不为1时误差随着变小而变大；当实际的 $y=0$ 且$h\theta(x)$也为 0 时代价为 0，当$y=0$ 但$h_\theta(x)$不为 0时误差随着 的变大而变大。

这里的$\log(x)$就是高等数学里面的$\ln(x)$。

梯度下降

在得到代价函数以后，我们便可以用梯度下降算法来求得能使代价函数最小的参数了。算法为：

$$\theta_j :=\theta_j-\alpha\frac{\partial}{\partial\theta_j}J(\theta)~~~~~(simultaneously~update)$$

求导后得到：

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

虽然得到的梯度下降算法公式表面上看上去与线性回归的梯度下降算法一样，但是这里的$h_\theta(x) = \frac{1}{1+e^{-\theta^Tx}}$与线性回归中不同，所以实际上是不一样的。另外，在运行梯度下降算法之前，进行特征缩放依旧是非常必要的。

下面是梯度下降法的推导过程：

$$\begin{align} J(\theta) =& -\frac{1}{m}\sum_{i=1}^{m}\bigl [y^{(i)}log(h_\theta(x))+(1-y^{(i)})log(1-h_\theta(x))\bigl]\\ =&-\frac{1}{m}\sum_{i=1}^{m}\bigl [y^{(i)}log(\frac{1}{1+e^{-\theta^Tx}})+(1-y^{(i)})log(1-\frac{1}{1+e^{-\theta^Tx}})\bigl]\\ =&\frac{1}{m}\sum_{i=1}^{m}\bigl [y^{(i)}log({1+e^{-\theta^Tx}})+(1-y^{(i)})log({1+e^{\theta^Tx}})\bigl]\\ \end{align}$$

求偏导得：

$$\begin{align} \frac{\partial}{\partial\theta_j} J(\theta) =& \frac{\partial}{\partial\theta_j} \Bigl[\frac{1}{m}\sum_{i=1}^{m}\bigl [y^{(i)}log({1+e^{-\theta^Tx}})+(1-y^{(i)})log({1+e^{\theta^Tx}})\bigl]\Bigr]\\ =&\frac{1}{m}\sum_{i=1}^{m}\bigl [y^{(i)}(\frac{-x_j^{(i)}e^{-\theta^Tx^{(i)}}}{1+e^{-\theta^Tx^{(i)}}})+(1-y^{(i)})(\frac{x_j^{(i)}e^{\theta^Tx^{(i)}}}{1+e^{\theta^Tx^{(i)}}})\bigl]\\ =&\frac{1}{m}\sum_{i=1}^{m}\bigl [y^{(i)}(\frac{-x_j^{(i)}}{1+e^{\theta^Tx^{(i)}}})+(1-y^{(i)})(\frac{x_j^{(i)}e^{\theta^Tx^{(i)}}}{1+e^{\theta^Tx^{(i)}}})\bigl]\\ =&\frac{1}{m}\sum_{i=1}^{m}\frac{-y^{(i)}x_j^{(i)}+x_j^{(i)}e^{\theta^Tx^{(i)}}-y^{(i)}x_j^{(i)}e^{\theta^Tx^{(i)}}}{1+e^{\theta^Tx^{(i)}}}\\ =&\frac{1}{m}\sum_{i=1}^{m}\bigl[ \frac{e^{\theta^Tx^{(i)}} - y^{(i)}(1+e^{\theta^Tx^{(i)}})}{1+e^{\theta^Tx^{(i)}}} \bigl]x_j^{(i)}\\ =&\frac{1}{m}\sum_{i=1}^{m}\bigl[ \frac{e^{\theta^Tx^{(i)}}}{1+e^{\theta^Tx^{(i)}}}-y^{(i)} \bigl]x_j^{(i)}\\ =&\frac{1}{m}\sum_{i=1}^{m}\bigl[ h_\theta(x^{(i)})-y^{(i)} \bigl]x_j^{(i)} \end{align}$$

除了梯度下降算法以外，还有一些常被用来令代价函数最小的算法，这些算法更加复杂和优越，而且通常不需要人工选择学习率，通常比梯度下降算法要更加快速。这些算法有：共轭梯度（Conjugate Gradient），局部优化法(Broyden fletcher goldfarb shann,BFGS)和有限内存局部优化法(LBFGS)

多类别分类：一对多 (One vs All)

多类别问题是指分类的问题不只是只有两种预测结果，而是由多种预测结果问题。例如现在需要一个学习算法能自动地将邮件归类到不同的文件夹里，或者说可以自动地加上标签。那么，你也许需要一些不同的文件夹，或者不同的标签来完成这件事，来区分开来自工作的邮件、来自朋友的邮件、来自家人的邮件或者是有关兴趣爱好的邮件，于是我们就有了这样一个分类问题：其类别有四个，分别用$y = 1$、$y = 2$、$y = 3$、$y = 4$来代表。

对于一个多类分类问题，我们的数据集或许看起来像这样：

我们现在已经知道使用逻辑回归来进行二元分类，可以通过确定决策边界将数据集一分为二为正类和负类。我们可以用一对多的分类思想来解决多类分类问题。

现在我们有一个训练集，好比上图表示的有3个类别，我们用三角形表示 $y = 1$，方框表示$y = 2$ ，叉叉表示$y = 3$ 。我们下面要做的就是创建“新”的训练集，将其分成3个二元分类问题。

比如先从用三角形代表的类别1开始，创建一个类型2和类型3定为负类，类型1设定为正类的训练集，并且根据这个二元问题，拟合出一个合适的分类器$h\theta^{(1)}(x)$。这个分类器表示$P(y=1|x;\theta)$。同理，我们还可以计算出其他的两个分类器$h\theta^{(2)}(x)$、$h_\theta^{(3)}(x)$。

最后我们得到一系列的模型简记为：

$$h_\theta^{(i)}(x)=P(y=i|x;\theta)~~~~~~~~for~~i = 1,2,3\dots k$$

之后要做的就是在我们三个分类器里面输入$h_\theta^{(i)}(x)$，然后我们选择一个概率$P(y=i|x;\theta)$最大的，即

$$\max_i\{h_\theta^{(i)}(x)\}$$