斯坦福机器学习课程 第三周

(1) 分类

下面将介绍分类问题。我们将学习一种叫做逻辑回归(Logistic Regression)的算法,这也是目前最流行,使用最广泛的一种学习算法。
下面是几个使用分类算法的例子:

  • Email的垃圾邮件分类问题:区分邮件是否为垃圾邮件
  • 网上交易分类问题:是否为欺诈交易
  • 肿瘤分类问题:区分肿瘤是恶性还是良性 在所有的这些问题中,我们想要预测的变量是$y​$,我们可以认为它取两个值:0或者1
    $$
    y \in 0, 1
    $$

0:“负类”(例如:良性肿瘤)

1:“正类”(例如:恶性肿瘤)

现在研究的是只有两类(0和1)的分类问题,叫做二元分类问题。如果是更多类别的问题就是所谓的多类分类问题

二元分类

对于这类问题我们可以使用逻辑回归算法(Logistic Regression),这个算法的性质就是适用于$y$值为离散值的情况,并且它的输出值保证在0到1之间:
$$
0 \le h_\theta(x) \le 1
$$

值得注意的是,逻辑回归算法是一个分类算法,即使它的名字里有回归,但我们也把它当成分类算法来使用。这里只是因为历史原因,才被这样称呼。

假设函数表达式

逻辑回归假设函数:
$$
h_\theta(x) = g(\theta^Tx)
$$
其中$g​$函数的表达式为:
$$
g(z) = \frac{1}{1+e^{-z}}
$$
这个函数被称为S型函数(Sigmoid function),或者逻辑函数(Logistic function)

S型函数(Sigmoid function)的图形是这样的,顶部是随着$z$的增大而逐渐趋近于1,底部随着$z$的减小而逐渐趋近于0:

因此可以得到:
$$
\begin{eqnarray}
h_\theta(x) &=& g(\theta^Tx) \
& = & \frac{1}{1+e^{-\theta^Tx}}
\end{eqnarray}
$$
接下来我们要做的就是用参数$\theta$来拟合我们的数据。

对假设函数的进一步理解

假设函数的解释

$h_\theta(x)$是对于新注入样本$x$的满足$y=1$的概率估计。
$$
h_\theta(x) = P(y = 1 | x; \theta)
$$

这个式子代表着在给定的特征$x$的情况下,$y=1$的概率,其中参数为$\theta$。

由于我们知道$y$的取值不是0就是1,因此当我们得到了$y=1$的概率时,$y=0$的概率就很容易得出:
$$
P(y=0 | x;0) = 1 - P(y=1|x;\theta)
$$

决策边界(Decision Boundary)

逻辑回归假设函数:
$$
h_\theta(x) = g(\theta^Tx) \
g(z) = \frac{1}{1+e^{-z}}
$$
对应的函数图象为:

更进一步来理解:

  • 如果$h_\theta(x) \ge 0.5$ 我们认为$y=1$
  • 如果$h_\theta(x) \le 0.5$ 我们认为$y=0$

根据图像可以得出:

  • 当$z \ge 0$时,$h_\theta(x) \ge 0.5$,满足$y=1$;
  • 当$z \le 0$时,$h_\theta(x) \le 0.5$,满足$y=0$。

即:

  • 当$\theta^Tx \ge 0$时,$y=1$;
  • 当$\theta^Tx \le 0$时,$y=0$。

当取$h_\theta(x) = 0$时,这条线则被称为决策边界(decision boundary)

(2) Logistic回归模型

逻辑回归的代价函数

$$
Cost(h_\theta(x),y) =\left{\begin{array}{r}
-log(h_\theta(x)) ~~ \text{ if } y = 1 \
-log(1-h_\theta(x)) ~~\text{ if } y = 0
\end{array}
\right.
$$

$y=1$时 $y=0$时

现在这种形式的代价函数有很多有趣的性质:

  • 在$y=1$的情况下:
    • 如果$h_\theta(x)=1$,那么代价函数为0
    • 如果$h_\theta(x) \rightarrow \infty$,那么代价函数趋近于$\infty$
  • 在$y=0$的情况下:
    • 如果$h_\theta(x) \rightarrow 1$,那么代价函数趋近于$\infty$
    • 如果$h_\theta(x) = 0$,那么代价函数等于0

这就是我们所期望的效果:当假设函数和期望值越接近时,代价函数值越小,反之越大。

简化代价函数以及梯度下降

简化单个样本的代价函数

对于单个样本的代价函数,我们可以把$y=0$和$y=1$的两种情况合二为一,写成一个统一的式子:
$$
Cost(h_\theta(x),y) = -ylog(h_\theta(x)) - (1-y)log(1-h_\theta(x))
$$

拟合逻辑回归的参数$\theta$

问题的核心在于求解最小代价函数:

上图就是逻辑回归问题中最小化代价函数的方法,是通过梯度下降算法来实现。

对上图中的偏导数项展开后就是下面的形式:

如果你把上面的式子放到线性回归问题中进行对比的话,你会发现这个式子正是用来做线性回归梯度下降的。

高级优化

利用一些技巧,可以使通过梯度下降进行逻辑回归的速度大大提高,这也将使得算法更加适合解决大型的机器学习问题。

优化算法概念引入

梯度下降并不是我们可以使用的唯一算法,下面是几种常用的算法:

  • 梯度下降算法(Gradient descent)
  • 共轭梯度法(Conjugate gradient)
  • 变尺度法(BFGS)
  • 限制变尺度法(L-BFGS)

优缺点

优点

  • 不需要手动选择学习率$\alpha$
    • 所以对这些算法的一种思路是给出计算导数项和代价函数$J(θ)$的方法,可以认为是算法有一个智能的内部循环,这种智能的内部循环被称为线性搜索(line search)算法,它可以自动尝试不同的学习速率$\alpha$,并自动选择一个好的学习速率$\alpha$。因此它甚至可以在每次迭代时都选择不同的学习速率,那么你就不需要自己选择$\alpha$了。
  • 通常情况下收敛速度比梯度下降算法更快
    • 这些算法实际上在做更复杂的事情,而不仅仅是选择一个好的学习速率$\alpha$,所以他们往往最终收敛的远远快于梯度下降。

缺点

  • 比梯度下降法复杂多了
    • 如果你不是数值计算方面的专家,不建议你亲自去写共轭梯度法、BFGS和L-BFGS,而是去使用一些现成的库。实际上Octave和Matlab都有很理想的库来实现这些先进的优化算法。值得一提的是,这些算法在不同语言上的实现,是有差别的,有的语言上的库可能会表现的不太好。所以建议对比选择合适的实现。

使用实例

现在举例说明如何使用这些算法。假设你有一个包含两个参数的问题:

对于上图中的代价函数,我们可以求得当$\theta_1 = 5$, $\theta_2 = 5$时,$J(\theta)$的值最小。

下面是使用Octave程序来计算$\theta_1$和$\theta_2$。

1
2
3
4
5
function [jVal, gradient] = costFunction(theta)
jVal = (theta(1)-5)^2 + (theta(2)-5)^2;
gradient = zeros(2,1);
gradient(1) = 2*(theta(1)-5);
gradient(2) = 2*(theta(2)-5);

上面这段代码定义了一个函数costFunction(theta),参数是一个theta向量,包含$\theta_1$和$θ_2$,返回值是jValgradient。通过函数的定义,我们可以看出来jVal表示的是代价函数$J(θ)=(\theta_1 - 5)^2 + (\theta_2 - 5)^2$。gradient是一个列量,其中两个值分别代表对$\theta_2$和$\theta_2$的偏导。

接下来,调用高级优化函数fminunc

1
2
3
options = optimset('GradObj', 'on', 'MaxIter', '100');
initialTheta = zeros(2,1);
[optTheta, functionVal, exitFlag] = fminunc(@costFunction, initialTheta, options);

fminunc表示Octave里无约束最小化函数,调用这个函数时,需要传入一个存有配置信息的变量options。上面的代码中,我们的设置项中'GradObj', 'on',代表设置梯度目标参数为打开状态(on),这也意味着你现在确实要给这个算法提供一个梯度。'MaxIter', '100'代表设置最大迭代次数为100次。initialTheta代表我们给出的一个$θ$的猜测初始值。

然后我们调用fminunc这个函数,传入三个参数,其中第一个参数@costFunction这里的@符号代表指向之前我们定义的costFunction函数的指针。后面两个参数分别是我们定义的$\theta$初始值和配置信息options

当我们调用这个fminunc函数时,它会自动的从众多高级优化算法中挑选一个来使用(你也可以把它当做一个可以自动选择合适的学习速率$\alpha$的梯度下降算法)。

最终我们会得到三个返回值,分别是满足最小化代价函数$J(θ)$的$θ$值optThetacostFunction中定义的jVal的值functionVal,以及标记是否已经收敛的状态值exitFlag,如果已收敛,标记为1,否则为0

在逻辑回归中使用优化算法

上面的例子是一个简单的二次函数中使用优化算法的例子,下面介绍一些在逻辑回归中使用这些算法:

上图就是逻辑回归问题的代价函数的求解代码。可以看到大体流程和之前的例子是一致的,只需要把相应的计算jVal以及各个gradient的代码,按照逻辑回归的规则填写完整即可。

使用了这些复杂的优化算法之后,虽然它将使得调试变得更为困难,但是这些算法的速度远远大于普通的梯度下降算法的速度,因此可以用来处理很大的机器学习问题的时候,可以使用这些高级算法,而不是梯度下降算法。

(3) 多类别分类问题:一对多

一对多(one-vs-all)分类问题

先看这样一些例子:

  • 邮件分类器自动将邮件按照以下标签分类:工作,朋友,家庭,兴趣
  • 医学根据病人的得病类型分类:没有病,感冒,流感
  • 天气预报根据天气类型分类:晴天,多云,雨天,雪天

我们可以分别对这些类别打上数值标签,比如天气分类中:晴天代表y=1,多云代表y=2,雨天代表y=3,雪天代表y=4

以上这些例子都属于多类别分类问题。

对于多分类问题,我们可以把它看作是多个二分类问题,这样我们就得到了多个分类器,通过这些分类器来估算给出$x$和$\theta$时,$y=i$的概率:
$$
h_\theta^{(i)}=P(y=i | x; \theta) ~~~ (i = 1,2,3)
$$
总之,现在我要做的就是训练这个逻辑回归分类器$h_\theta^{(i)}(x)$,其中$i$对应每一个可能的$y=i$。

最后,为了做出预测,我们给定一个新的输入值$x$,用来做预测,我们要做的就是在我们的多个分类器里输入$x$,然后我们选择一个让$h_θ^{(i)}(x)$最大的$i$,这就是预测出的类别。

(4) 正则化:解决过拟合问题

机器学习模型需要拥有很好地泛化能力来适应训练集中没有出现过的新样本。正则化是一个有助于预防过拟合的有效办法。

解决过拟合问题

到现在为止我已经学习了几种不同的学习算法,包括线性回归和逻辑回归,它们能够有效地解决许多问题,但是当应用到某些特定的及其学习应用时,会遇到过度拟合(over-fitting)的问题,可能导致效果很差。

接下来我将谈论一种称为正则化(regularization)的技术,它可以改善或者减少过度拟合问题,以使学习算法更好实现。

梯度下降中的过拟合问题

让我们继续使用那个线性回归来预测房价的例子。

欠拟合

我们通过建立以住房面积为自变量的函数来预测房价,我们可以对该数据做线性回归:

但这不是一个很好的模型,因为随着房子面积增大,住房价格的变化趋势趋于稳定,或者往右越平缓。所以这个算法没有很好地拟合训练数据。

我们把这个问题称为欠拟合(under fitting),这个问题的另一个术语叫做高偏差(High bias)

刚好合适

当我们加入一个二次项,在这组数据中,我们用二次函数来拟合它:

事实证明这个拟合效果很好。

过拟合

另一个极端情况是,如果我们拟合一个四次多项式,因此在这里我们用五个参数来拟合这五个训练样本,你可以得到看上去像这样的一条曲线:

一方面似乎对训练数据做了一个很好的拟合,因为这条曲线通过了所有的训练实例。但是,这仍然是一条扭曲的曲线。它不停上下波动,因此事实上,我们并不认为它是一个预测房价的好模型。

这个问题我们把他叫做过度拟合(over fitting),另一个描述该问题的术语是高方差(variance)

介于高偏差高方差这两者之间的情况叫做“刚好合适”

概括地说,过拟合的问题将会在变量过多的时候发生,这种时候训练出的方程总能很好的拟合训练数据,所以你的代价函数实际上可能非常接近于0,甚至就是0。但是这会导致这种模型无法泛化到新的数据样本中,以至于无法预测新样本价格。

在这里术语“泛化(generalize)”指的是一个假设模型能够应用到新样本的能力。

逻辑回归中的过拟合问题

类似的方法同样可以应用到逻辑回归

解决过拟合问题

当我们有过多变量,同时只有非常少的训练数据时,就会出现过度拟合的问题。

为了解决过度拟合问题,有两种方法:

  1. 要尽量减少选取的变量的数量。
    • 具体而言我们可以人工检测变量的条目,保留重要的特征,舍弃无用的特征
    • 模型选择算法(后面的课程会提到)
  2. 正则化
    • 保留所有的特征变量,但是通过减少参数$θ_j$的数量级或值的大小。

正则化相关的知识点将在接下来的内容中介绍。

代价函数

正则化的思路就是,如果我们的参数值对应一个较小的值,那么往往会得到一个形式更简单的假设函数,就能够减少代价函数的均方误差。通常情况下来讲,参数值减少的越多,函数越光滑,就不易发生过拟合的问题。

正则化优化的目标

我们正则化之后的代价函数如下:
$$
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$我们称为正规化参数

$\lambda$要做的就是控制在两个不同的目标中的一个平衡关系:

  • 第一个目标就是:我们想要训练使假设函数更好的拟合训练数据。
  • 第二个目标就是:我们想要保持参数值较小。

参数$\lambda$就是用来控制这两者之间的平衡,目标就是平衡拟合训练的目的和保持参数值较小的目的。(即欠拟合和过拟合的平衡)

正规化线性回归中,如果正规化参数值被设定为非常大,那么假设函数将会变为:
$$
h_\theta(x) = \theta_0
$$
对于数据来说这就是欠拟合(under-fitting)。因此为了使正则化运作的良好,我们应该去选择一个不错的正则化参数$\lambda$,并且当我们讲到多重选择时,我们将会介绍一种方法来自动选择正则化参数$\lambda$。这就是高度正则化的思路。

正则化线性回归

对于线性回归的求解,我们之前推导了两种学习算法:一种基于梯度下降、一种基于正规方程。接下来我们会把它们推广到正则化线性回归中去。

基于梯度下降

Repeat{
$$
\begin{array}{l}
\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_0^{(i)} +\frac{\lambda}{m}\theta_j ] ~~~ (j = 1, 2, 3, …, n)
\end{array}
$$
}

对于上面式子中第二项可以改写成这种形式:

当我们使用正则化线性回归时,我们实际上做的就是在每一个被正则化的参数$θ_j$上乘以了一个比1小一点点的数字,然后执行跟以前一样的更新。

基于正规方程

取$J$关于各个参数的偏导数,并令他们等于0,然后通过一些数学推导可以得到这样的式子:
$$
\theta = (X^TX + \lambda\left[
\begin{array}{c}
0 & 0 & … & 0 \
0 & 1 \
… & … & … & \
0 & 0 & … & 1
\end{array}
\right])^{-1} X^T y
$$
其中正则化矩阵左上角的元素是0,其余对角线元素都是1,剩下的元素也都是0。矩阵的维度是$(n + 1) \times (n + 1)$。

不可逆问题(*选学)

在正规方程中,考虑$m$(即样本总数)小于等于特征数量$n$:
$$
m \le n
$$
如果样本数量比特征数量小的话,那么这个矩阵$X^TX$将是不可逆的或奇异(singular)的。

幸运的是,正规化也为我们解决了这个问题,具体地说,只要正则参数是严格大于0的:
$$
\lambda > 0
$$
实际上是可以证明
$$
X^TX + \lambda\left[
\begin{array}{c}
0 & 0 & … & 0 \
0 & 1 \
… & … & … & \
0 & 0 & … & 1
\end{array}
\right]
$$
这个矩阵是可逆的。

因此,使用正则化还可以解决一些$X^TX$不可逆的问题。