在第三周的课程里，介绍了Logistic Regression - 逻辑斯谛回归问题，主要应用在Classification - 分类上。还有Regularization - 正则化，如何用来解决Overfitting - 过拟合问题。

Logistic Regression - 逻辑斯谛回归

Classification - 分类问题

分类在日常中用在很多地方，比如邮件是否垃圾邮件，肿瘤是否良性。通过给定的特征与对应的类别，我们可以训练出一个能够进行分类的算法。相应的，垃圾邮件的特征可以是某些关键词，比如推销类的；而肿瘤的特征可以是肿瘤大小或者别的什么（不懂就不胡说了）。
这时我们的结果$y$就是离散化的数字。

如果是Binary Classification - 二分类问题，$y$可以离散化为$y = 0 or 1$，对应是/否，大/小等抽象的结果。
如果是Multiple Classification - 多分类问题，$y$可以离散化为元素个数为类别个数的向量。比如我们需要对某组数据进行分类，训练样本中一共有$n$类，当前训练样本的$y$是属于第$i$类的，则令$y = [0_{1},0_{2},\cdots,1_{i},\cdots,0_{n}]^{T}$ ，其中下标位置为对应类别。

这里我们先讨论Binary Classification - 二分类问题。同样先来个例子。

假如我们有一组肿瘤大小与其对应性质（良性/恶性）的数据，特征只有一个，就是肿瘤大小，$y=1$和红色X点代表恶性。如下图：

我们看到，假如我们用单纯的线性方程来拟合这组数据，按照图示定义，当$h_{\theta} = \theta^{T}x >0.5$ 时预测为恶性，则会与原数据误差较大。显然单纯的线性方程很难做到精准的分类。

我们尝试换一种思路。可以看到，两种类型的数据在某一$x$值上会有明显的区分。在$x$左边是良性的，在$x$右边是恶性的。于是我们做如下分析：

令分界点$x = \frac{-\theta_{0}}{\theta_{1}}$ ，则当$x > \frac{-\theta_{0}}{\theta_{1}}$ 即$\theta^{T}x = \theta_{0}+\theta_{1}x > 0$时，预测$y=1$，当$x < \frac{-\theta_{0}}{\theta_{1}}$ 即$\theta^{T}x = \theta_{0}+\theta_{1}x < 0$时，预测$y=0$。这样就能得到很好的分类效果。

同样的，多特征时也可以如此这般。比如两个特征时的情况：

因此我们只要一个函数$g(\theta^{T}x)$

当$\theta^{T}x > 0$ 时，$g(\theta^{T}x) > 0.5$
当$\theta^{T}x < 0$ 时，$g(\theta^{T}x) < 0.5$

最后令$h_{\theta}(x) = g(\theta^{T}x)$ ，就ok了。

Hypothesis Representation - 假设函数的表示

接着上面的问题。我们给出这样一个函数

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

它的图像如下

它满足下述性质

当$z > 0$ 时，$g(z) > 0.5$
当$z < 0$ 时，$g(z) < 0.5$

因此，我们只需令$\theta^{T}x = z$ ，即

$g(\theta^{T}x) = \frac{1}{1+e^{-\theta^{T}x}}$

则可得我们的假设函数

$h_{\theta}(x) = g(\theta^{T}x) = \frac{1}{1+e^{-\theta^{T}x}}$

这里$h_{\theta}(x)$ 实际上可以理解为如下

$h_{\theta}(x) = p(y = 1|x;\theta)$

即输入$x$ 的情况下，预测结果为$1$ 的概率为$h_{\theta}(x)$ 。
比如说这是一个良性/恶性肿瘤的分类问题，我们训练出了$h_{\theta}(x)$ 。现在有一个肿瘤的各项特征为$x$ ，我们要判断它是良性$(y=1)$ 还是恶性$(y=0)$ ，把$x$ 丢进$h_{\theta}(x)$ 里，结果为$0.8$ ，那么我们就可以说这个肿瘤有$80\%$ 的概率是良性的。假如我们设置了一个阈值为$0.7$ ，计算结果超过这个阈值就可以声明预测为真，那么在上面的情况中，我们就可以直接对病人说你的肿瘤是良性的，不用担心。

Decision Boundary - 判定边界

在逻辑斯谛回归中，我们一般

当$h_{\theta}(x) > 0.5$ ，即当$\theta^{T}x > 0$ 时，预测$y=1$
当$h_{\theta}(x) < 0.5$ ，即当$\theta^{T}x < 0$ 时，预测$y=0$

如下图（见上节）

此时阈值为$0.5$

对于一般的问题，$0.5$ 的阈值足以胜任。可是假如是一些精确度要求很高的问题，就比如刚刚的判断肿瘤是否良性，或者判断是否得癌症等，那么就应该把阈值设置得高点，预测结果更准确。毕竟是人命关天的事嘛:)

假如我们的样本分布不能线性划分，如下图所示

我们可以用一个非线性的边界（高次多项式）来划分。

Cost function - 代价函数

对于前面的回归问题，我们的代价函数是所有误差的平方和取均值（实际上就是方差）

$J(\theta)=\frac{1}{2m}\sum_{i=1}^{m}\left(h_{\theta}(x^{(i)})-y^{( i)}\right)^{2}$

如果我们沿用这个计算方法，将逻辑斯谛回归的$h_{\theta}(x) = g(\theta^{T}x) = \frac{1}{1+e^{-\theta^{T}x}}$ 代入进上式的话，我们的函数图像会呈现出下面一种状况

这是一个非凸函数，它有许多的局部最小值，不利于用梯度下降法寻找全局最小值。
所以我们要对逻辑回归重新定义一个代价函数。

根据我们$h_{\theta}(x)$的性质

当$\theta^{T}x > 0$ 时，$h_{\theta}(x) > 0.5$
当$\theta^{T}x < 0$ 时，$h_{\theta}(x) < 0.5$
$h_{\theta}(x) \in (0, 1)$

我们对代价函数作出如下定义

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

它的函数图像和意义如下所示

当$y = 1$时

它所反映的就是当样本结果$y = 1$ 时，如果我们$h_{\theta}(x)$ 输出也$\rightarrow 1$ 的话，我们的误差就$\rightarrow 0$ ；反之，如果我们$h_{\theta}(x)$ 输出$\rightarrow 0$ 的话，我们的误差就$\rightarrow \infty$

当$y = 0$时

它所反映的就是当样本结果$y = 0$ 时，如果我们$h_{\theta}(x)$ 输出也$\rightarrow 0$ 的话，我们的误差就$\rightarrow 0$ ；反之，如果我们$h_{\theta}(x)$ 输出$\rightarrow 1$ 的话，我们的误差就$\rightarrow \infty$

没毛病:)

Simplified cost function and gradient descent - 化简代价函数与梯度下降

对于$Cost\left( h_{\theta}\left( x \right), y \right)$ ，我们可以化简成

$Cost\left( h_{\theta}\left( x \right), y \right) = -ylog\left( h_{\theta}\left( x \right) \right) - \left( 1-y \right)log\left( 1-h_{\theta}\left( x \right) \right)$

对于$J(\theta)$ 我们作如下定义

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

将$Cost\left( h_{\theta}\left( x \right), y \right)$ 代入上式，则可得

$J(\theta) = - \frac{1}{m} \sum_{i=1}^{m} \left[ y^{\left( i \right)}log\left( h_{\theta}\left( x^{\left( i \right)} \right) \right) + \left( 1-y^{\left( i \right)} \right)log\left( 1-h_{\theta}\left( x^{\left( i \right)} \right) \right) \right]$

这时我们就可以用梯度下降来求$min_{\theta}J(\theta)$ 。

与回归一样，我们要做的就是不断更新$\theta$

$\theta := \theta - \alpha \frac{\partial J}{\partial \theta}$

接下来我们来推导一下$\frac{\partial J}{\partial \theta}$ 。

首先，我们有

$X_{m \times (n+1)}\begin{bmatrix}x_{0}^{(1)} & x_{1}^{(1)} & \cdots & x_{n}^{(1)}\\ \vdots & \vdots & \ddots & \vdots\\ x_{0}^{(m)} & x_{1}^{(m)} & \cdots & x_{n}^{(m)}\end{bmatrix} = \begin{bmatrix}1 & x_{1}^{(1)} & \cdots & x_{n}^{(1)}\\ \vdots & \vdots & \ddots & \vdots\\ 1 & x_{1}^{(m)} & \cdots & x_{n}^{(m)}\end{bmatrix}$
$Y_{m\times 1} = \begin{bmatrix} y^{(1)} & \cdots & y^{(m)}\end{bmatrix}^{T}$
$\theta = \begin{bmatrix}\theta_{0} & \theta_{1} & \cdots & \theta_{n} \end{bmatrix}^{T}$
$\frac{\partial J}{\partial \theta} = - \frac{1}{m} \sum_{i=1}^{m} \left[ y^{(i)}\frac{\partial log(h_{\theta}(x^{(i)}))}{\partial \theta} + ( 1-y^{(i)})\frac{\partial log(1-h_{\theta}( x^{(i)} ))}{\partial \theta} \right]$
$h_{\theta}(x^{(i)}) = g(\theta^{T}x^{(i)}) = \frac{1}{1+e^{-\theta^{T}x^{(i)}}}$

因为

$y^{(i)} \frac{\partial log(h_{\theta}(x^{(i)}))}{\partial \theta} = \frac{y^{(i)}}{h_{\theta}(x^{(i)})} \cdot \frac{x^{(i)}e^{-\theta^{T}x^{(i)}}}{(1+e^{-\theta^{T}x^{(i)}})^{2}}$

$= y^{(i)}(1+e^{-\theta^{T}x^{(i)}}) \cdot \frac{x^{(i)}e^{-\theta^{T}x^{(i)}}}{(1+e^{-\theta^{T}x^{(i)}})^{2}}$

$= y^{(i)} \frac{x^{(i)}e^{-\theta^{T}x^{(i)}}}{1+e^{-\theta^{T}x^{(i)}}}$

$= y^{(i)} h_{\theta}(x^{(i)})x^{(i)}e^{-\theta^{T}x^{(i)}}$

又因为

$(1-y^{(i)}) \frac{\partial log(1-h_{\theta}( x^{(i)} ))}{\partial \theta} = - (1-y^{(i)}) \frac{1}{1-h_{\theta}(x^{(i)})} \cdot \frac{x^{(i)}e^{-\theta^{T}x^{(i)}}}{(1+e^{-\theta^{T}x^{(i)}})^{2}}$

$= - (1-y^{(i)}) \frac{1+e^{-\theta^{T}x^{(i)}}}{e^{-\theta^{T}x^{(i)}}} \cdot \frac{x^{(i)}e^{-\theta^{T}x^{(i)}}}{(1+e^{-\theta^{T}x^{(i)}})^{2}}$

$= - (1-y^{(i)}) \frac{x^{(i)}}{1+e^{-\theta^{T}x^{(i)}}}$

$= - (1-y^{(i)})x^{(i)}h_{\theta}(x^{(i)})$

将上面两式相加，提出$h_{\theta}(x^{(i)})x^{(i)}$ ，得

$h_{\theta}(x^{(i)})x^{(i)} \left[y^{(i)}(1+e^{-\theta^{T}x^{(i)}}) - 1\right]$

$= x^{(i)}y^{(i)} - x^{(i)}h_{\theta}(x^{(i)})$

$= x^{(i)} (y^{(i)} - h_{\theta}(x^{(i)}))$

将上式代入$\frac{\partial J}{\partial \theta}$ ，则

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

我们惊奇地发现，$\frac{\partial J}{\partial \theta}$ 的表达式居然跟回归是一样的！这就是数学的魅力！
因此，参考week1的推导，可得

$\frac{\partial J}{\partial \theta} = \frac{1}{m} X^{T}(X\theta - Y)$

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

Multi-class classification: One-vs-all - 多分类问题：一对多

在实际分类问题中，我们遇到的大多是需要分多个类的问题，比如联系人的分类有家人，朋友，同事，同学等等。在可视化图像中，它们可能会呈现出如下的分布

一对多的做法就是我们分别对这三个类训练$h_{\theta}^{(i)}(x)$ ，其中$i$ 为类别序号。如下图所示

训练完所有的$h_{\theta}^{(i)}(x)$ 后，当我们给一组输入特征$x$ 时，取最大的$h_{\theta}^{(i)}(x)$ 作为我们的预测结果。

Regularization - 正则化

The problem of overfitting - 过拟合问题

假如我们样本有非常多的特征，我们也许能训练出一个在样本集上表现得很好的假设函数$h_{\theta}(x)$ ，但是对于新的输入，我们可能不能很好地进行拟合（预测）。这类问题，我们称之为过拟合。

对于过拟合问题我们一般有下面一些解决方法

减少特征数量

手动剔除一些不必要的特征，或者用一些降维算法（PCA）来自动减少特征数

正则化

保留所有的特征，同时减小参数$\theta$ 的大小

Cost function - 代价函数

首先看下面这两种预测函数在样本集上的结果

我们能看到，左边是比较合适的预测函数，而右边则明显过拟合了。

这时我们用一个小小的技巧，在我们的误差函数$J(\theta)$ 后面对$\theta_{3}$ 和$\theta_{4}$ 加一个惩罚系数（或者说补偿反馈），使之变为

$J(\theta)=\frac{1}{2m}\sum_{i=1}^{m}\left(h_{\theta}(x^{(i)})-y^{(i)}\right)^{2} + 1000\theta_{3} + 1000\theta_{4}$

由上可知，我们要求最优的$\theta$ ，使得$J(\theta)$ 取得最小值，那么我们在优化过程中（比如梯度下降）$\theta_{3}$ 和$\theta_{4}$ 一定$\rightarrow 0$ ，因为他们占比很大。这样$\theta_{3}$ 和$\theta_{4}$ 对$h_{\theta}(x)$ 的贡献就非常小，$x^{3}$ 和$x^{4}$ 这些高次项在$h_{\theta}(x)$ 所占的权重就小很多，有效地防止了过拟合。

假如我们有非常多的特征，不知道要对哪些对应的参数$\theta$ 作惩罚，那么最好的办法就是对所有的$\theta$ 作惩罚，然后让程序自己迭代优化。所以我们的代价函数$J(\theta)$ 就变成下面这种形式

$J(\theta) = \frac{1}{2m} \left[ \sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})^{2} + \lambda \sum_{j=1}^{n} \theta_{j}^{2} \right]$

其中$\lambda$ 称为正则化参数。一般我们不对$\theta_{0}$ 进行惩罚。

正则化后的假设函数如下图所示

其中蓝色曲线是过拟合的情况，紫色曲线是正则化后的假设函数曲线，而橙色直线则是 正则化参数过大 导致的 欠拟合。为什么会这样呢？因为正则化参数过大，会对$(\theta_{1} \cdots \theta_{n})$ 惩罚过重，以至于$(\theta_{1} \cdots \theta_{n}) \rightarrow 0$ ，使得$h_{\theta}(x) \approx \theta_{0}$。

因此对于正则化，我们要选一个合适的值，才有好的效果。

Regularized linear regression - 正则化后的线性回归

正则化后我们的代价函数变成

$J(\theta) = \frac{1}{2m} \left\{ \left[\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})^{2} \right] + \lambda \sum_{j=1}^{n} \theta_{j}^{2} \right\}$

如果我们用梯度下降来求最优$\theta$ ，我们更新$\theta$ 就要分别更新$\theta_{0}$ 和$\theta_{1} \cdots \theta_{n}$

$$\begin{cases} \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 \left\{ \frac{1}{m} \left[\sum_{i=1}^{m}( h_{\theta}(x^{(i)})-y^{(i)} )x_{j}^{(i)} \right]+\frac{\lambda}{m}\theta_{j}\right\} & j=1,2, \cdots ,n \end{cases}$$

其中$\theta_{j}$ 可以化简成

$\theta_{j}(1-\alpha\frac{\lambda}{m}) - \alpha\frac{1}{m}\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)}$

我们看到，$(1-\alpha\frac{\lambda}{m}) < 1$ ，所以正则化后的梯度下降实际上就是让$\theta_{j}$ 减少一定的比例后再进行原来的梯度下降。

我们知道，梯度$\frac{\partial J}{\partial \theta}$ 为$0$ 时，$J(\theta)$ 取得极小值，所以我们令

$$\begin{cases} \sum_{i=1}^{m}( h_{\theta}(x^{(i)})-y^{(i)} )x_{0}^{(i)} = 0\\ \sum_{i=1}^{m}( h_{\theta}(x^{(i)})-y^{(i)} )x_{j}^{(i)} + \lambda\theta_{j} = 0 & j=1,2, \cdots ,n \end{cases}$$

即

$\frac{\partial J}{\partial \theta} =\begin{bmatrix}x_{0}^{(1)} & x_{0}^{(2)} &\cdots & x_{0}^{(m)}\\ x_{1}^{(1)} & x_{1}^{(2)} & \cdots & x_{1}^{(m)}\\ \vdots & \vdots & \ddots & \vdots \\ x_{n}^{(1)} & x_{n}^{(2)} & \cdots & x_{n}^{(m)}\end{bmatrix} \begin{bmatrix}h_{\theta}(x^{(1)})-y^{(1)}\\h_{\theta}(x^{(2)})-y^{(2)}\\ \vdots\\h_{\theta}(x^{(m)})-y^{(m)}\end{bmatrix} + \lambda \begin{bmatrix}0\\ \theta_{1}\\ \vdots \\ \theta_{n}\end{bmatrix} = 0$

也即

$X^{T}(X\theta - Y) + \lambda \begin{bmatrix}0 & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1\end{bmatrix}_{(n+1)^{2}} \theta = 0$

去掉括号，并提出$\theta$ ，整理等式

$(X^{T}X + \lambda\begin{bmatrix}0 & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1\end{bmatrix}_{(n+1)^{2}}) \theta = X^{T}Y$

最后我们可得

$\theta = (X^{T}X + \lambda\begin{bmatrix}0 & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1\end{bmatrix}_{(n+1)^{2}})^{-1} X^{T}Y$

上式就是正则化后的 Normal equation - 正规方程，其中$(X^{T}X + \lambda\begin{bmatrix}0 & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1\end{bmatrix}_{(n+1)^{2}})$ 一定是可逆的。这个就不在此作证明了。

Regularized logistic regression - 正则化后的逻辑斯谛回归

与线性回归一样，我们在原来的代价函数$J(\theta)$ 后面加上一个惩罚项，则$J(\theta)$ 变成

$J(\theta) = - \left\{ \frac{1}{m} \sum_{i=1}^{m} \left[ y^{\left( i \right)}log\left( h_{\theta}\left( x^{\left( i \right)} \right) \right) + \left( 1-y^{\left( i \right)} \right)log\left( 1-h_{\theta}\left( x^{\left( i \right)} \right) \right) \right] \right\} + \frac{\lambda}{2m} \sum_{j=1}^{2} \theta_{j}^{2}$

因为其$\frac{\partial J(\theta)}{\partial \theta}$ 的形式与上面线性回归一样，所以梯度下降的过程同上。

课程资料