机器学习之壹：回归与分类问题

Posted on 繁/简： set

计算机科学祛魅之路之 Machine Learning 篇。有一种莫名的激动，这个熟悉又陌生的名词终于从书本上，手机屏幕里，转瞬即逝的对话中以实体的形式向我走来。Let's see where it takes us.

从大名鼎鼎的吴恩达 Machine Learning 课程开始！Coursera 上申请了助学金，又省了 200 多块。(自动扣费我造密码)


  This article is a self-administered course note.

  It will NOT cover any exam or assignment related content.


Machine Learning: Overview

Field of study that gives computers the ability to learn without being explicitly programmed.

— Arthur Samuel (1959)

机器学习算法大概可分为四类：

  • Supervised Learning (监督学习)
  • Unsupervised Learning (无监督学习)
  • Recommender Systems (推荐系统)
  • Reinforcement Learning (强化学习)

监督学习与无监督学习的最主要区别在于机器是否被给予了参考数据集。

  • Supervised Learning: machine learns from data labeled with the right answers.
  • Unsupervised Learning: machine finds something potentially interesting in unlabeled data.


Supervised Learning

监督学习的两个主要问题：

  • Regression (回归): Predict a number - infinitely many possible outputs.
  • Classification (归类): Predict categories - small number of possible outputs.

这两种问题都要求机器从给定的 训练集 (training set) 中进行学习，通过 学习算法 (learning algorithm) 建立预测 模型 (model)，并能够做出较为准确的 预测 (prediction or estimation)。

回归问题中预测的结果是 continuous 的；而分类问题中的结果是 discrete 的。

介绍一些训练集中的 jargon：

  • \(x\): input variable in the training set, or features.
  • \(y\): output variable in the training set, or target.
  • \(\hat{y}\): a prediction of \(y\), or estimated \(y\).
  • \(n\): # of features.
  • \(m\): # of training examples.
  • \(x_i \ (i\leq n)\): the \(i\)-th feature. subscript \(i\).
  • \((x^{(i)}, y^{(i)}) \ (i\leq m)\): the \(i\)-th training example. superscript \(i\).


Univariate Linear Regression

之前一直很疑惑：regression 到底是什么意思？到底要回到哪里去呢。现在才知道这是一个很形象的说法，指回归曲线根据训练集不断朝最小化 cost 的方向「回归」的过程。

先来看最简单的情况：Univariate (one-variable) linear regression. 即 \(n=1\) 的线性回归问题。

线性回归的预测模型为 \(f_{w,b}(x)=wx+b\)。现在给出训练集，我们要求设计一个学习算法，使得机器能够根据该训练集找到能够产生准确预测的 \(w,b\)。

Square Error Cost

Cost Function \(J(w,b)\) 描述了 prediction model 与训练集数据间的误差。linear regression 采用的 cost function 是 square error cost function，即每个数据点与模型间误差的平方之和的平均值除以 2。 \[ J(w,b)=\frac{1}{2m}\sum_{i=1}^m (f_{w,b}(x^{(i)})-y^{(i)})^2 \] 其中 \(f_{w,b}(x^{(i)})=wx^{(i)}+b\).

(除了多除以一个 2 [stay tuned]，这就是最小二乘法)

问题转化为：设计 learning algorithm 找到 \(w,b\) 使得 cost function \(J(w,b)\) 最小化。


Gradient Descent

超级优美的算法。它是工程上被广泛采用的一种算法，能够求出使得 \(J(w,b)\) 最小的 \(w,b\)。

  • Start with some \(w,b\). (Set \(w=0,b=0\))
  • Keep changing \(w,b\) by gradient [stay tuned] to reduce \(J(w,b)\).
  • Until we settle at or near a minimum.

一开始很疑惑，求使得 \(J(w,b)\) 最小的 \(w,b\)，我们直接对 \(J\) 求导再令 \(J'=0\) 不就完事了嘛！

对于 square error function，这当然是可行的，因为我们能保证它是一个二次函数，具有 bowl shape；但大多数 cost function 的形式要比这复杂得多，甚至使得求导都是一个不可能的任务。

Outline

Set \(w=0,b=0\). Repeat the process simultaneously { \[ \begin{aligned} w&=w-\alpha \frac{\partial}{\partial w}J(w,b) \\ b&=b-\alpha\frac{\partial}{\partial b} J(w,b) \end{aligned} \] } until convergence.

其中 \(\alpha\) 是 learning rate，它是一个 positive number。偏导 \(\frac{\partial}{\partial w}J\) 与 \(\frac{\partial}{\partial b}J\) 为对应参数的梯度 (gradient)。

这个算法非常的 intuitive，它能够保证函数 \(J(w,b)\) 一定朝着某个最小值下降。想象在山地里，某人站在特定的起始位置 (\(w=0,b=0\))，一步一步地朝着山谷走去；他每走一步就环视一下周围，并朝着最陡 (下降最厉害) 的方向接着移动一步。他的步长是由 learning rate \(\alpha\) 所决定的。

在谷底时，此人不会再向其他地方移动 (convergence: 不断原地踏步)。

Learning Rate

步长 \(\alpha\) 过大：

  • overshoot, never reach minimum.
  • fail to converge but diverge.

步长 \(\alpha\) 过小：

  • gradient descent may be slow.

合适的 learning rate \(\alpha\) 能在保证梯度下降 (cost function 单调下降) 的前提下使得下降的幅度尽量大。

Gradient

梯度 \(\frac{\partial}{\partial w}J\) 与 \(\frac{\partial}{\partial b}J\) 的计算： \[ \begin{aligned} \frac{\partial}{\partial w}J(w,b)&=\frac{1}{2m}\frac{\partial}{\partial w}\sum_{i=1}^m(f(x^{(i)})-y^{(i)})^2= \frac{1}{m}\sum_{i=1}^m(f(x^{(i)})-y^{(i)})x^{(i)}\\ \frac{\partial}{\partial b}J(w,b)&=\frac{1}{2m}\frac{\partial}{\partial b}\sum_{i=1}^m(f(x^{(i)})-y^{(i)})^2= \frac{1}{m}\sum_{i=1}^m(f(x^{(i)})-y^{(i)}) \end{aligned} \] 其中 \(f(x^{(i)})=wx^{(i)}+b\).

之所以 cost function 的定义要比最小二乘法多除以一个 2，就是为了这里与导数产生的 2 抵消。

梯度的大小与偏导成正比：因此越靠近最小值 (local minimum)，导数越小，梯度也越小，cost function 的下降幅度也越小。就这样，cost function 不断向最小值收敛。


Multiple Linear Regression

\(n>1\) 的情况：训练集有多个 features。将 \(w\cdot x\) 标量乘换成 \(\vec{w}\cdot \vec{x}\) 点乘即可。 \[ \begin{aligned} f_{\vec{w},b}(\vec{x})&=\vec{w}\cdot\vec{x}+b=(\sum_{i=1}^n w_ix_i)+b \\ J(\vec{w},b)&=\frac{1}{2m}\sum_{i=1}^m(f_{\vec{w},b}(\vec{x}^{(i)})-y^{(i)})\\ \frac{\partial}{\partial w_n}J(\vec{w}, b)&=\frac{1}{m}\sum_{i=1}^m(f_{\vec{w},b}(\vec{x}^{(i)})-y^{(i)})x^{(i)}_n \end{aligned} \] 具体实现中，使用 Numpy 库中的 np.dot() 等 vectorization 函数来加速运算。


Feature Manipulation

一些有用的小 tricks：对训练集的 features 作适当调整提升 gradient descent 的效率与准确率。

Feature Scaling

当特征的尺度不同时，代价函数的形状可能会拉长，从而导致收敛速度减慢。feature scaling 对特征进行归一化处理，从而使代价函数更加圆滑，gradient descent 也能更快地收敛。

  • mean normalization: for \(1\leq i\leq n\), \(x_i=\frac{x_i-\mu_i}{\mathrm{max-min}}\).
  • Z-score normalization: for \(1\leq i\leq n\), \(x_i=\frac{x_i-\mu_i}{\sigma_i}\).

想象一个双变量 linear regression 的 contour plot，其中一个变量的尺度远大于另一个。

在进行 feature scaling 之前，contour plot 是椭圆形的，gradient descent 的过程很曲折，cost 在图中艰难的向椭圆中心 (最小值) 前进；进行 scaling 之后，contour plot 近似一个圆形，gradient descent 的过程很顺利，cost 沿着半径向圆心行进。

在进行 feature scaling 找到对应的参数 \(w,b\) 后，需要作出预测的 input variable 也应进行同样的 scaling。

Feature Engineering

Feature engineering 是从原始特征中选择，提取，转换和组合最相关的特征，以提高机器学习模型性能的过程。什么是最相关的特征？举个简单的例子：

  • feature \(x_1\) - depth.
  • feature \(x_2\) - frontage.
  • feature \(x_3\) - distance to downtown.
  • target \(y\) - price.

我们根据地产的 \(x_1,x_2,x_3\) 这三个特征预测其价格 \(y\)。一个明显更优秀的模型是利用 feature engineering 的思想组合 \(x_1,x_2\) 这两个特征创造出 \(x_3=x_1x_2\)，即地产的面积这一新的，与房价更相关的特征。


Polynomial Regression

与 feature engineering 的思想有相同之处。通过添加 \(\sqrt{x}, x^2,x^3, x^4...\) 等 polynomial features 使得回归曲线呈现 polynomial 的形态。

如果有多个 features 如 \(x_1,x_2\)，则添加它们之间各种 degree 的组合如 \(x_1^2,x_2^2,x_1x_2\)。(这里 degree 为 2)

很明显，\(\sqrt{x},x,x^2...\) 这一系列的 polynomial 的尺度是非常不同的，最好进行 feature scaling。


Logistic Regression

Logistic regression 的中文译名是逻辑回归，这一定程度上能说明其并不是 regression 问题的模型，而是 classification 问题的模型。

我们说 regression 问题要求 predict numbers with infinite outputs，而 classification 问题要求 predict categories with finite outputs.

Logistic regression (逻辑回归) 解决的是 binary classification 问题，即预测的结果是 \(0\) (假) 或 \(1\) (真) 这两个逻辑类型中的一个。

Why not linear regression?

categories 同样也属于 numbers，我们当然可以使用 linear regression 来解决 binary classification 问题。这里以 \(n=1\) 的情况为例：

  • 使用 linear regression 模型求出回归曲线 (这里应该是直线) \(y=wx+b\).
  • 设定 threshold (例 \(0.5\))，求出 \(y=0.5\) 对应的 \(x=x_t\)。
  • 对于所有 \(x>x_t\) 的输入，我们预测 \(1\)；反之预测 \(0\)。

对于较为简单的训练集，这种方法是可行的；但只要添加一个 outlier example，回归曲线就会受到很大的影响，从而大大降低预测的准确性。

对于 binary classification 问题，我们需要一种新的模型：它能在存在 outliers 的情况下作出准确的预测。这就是 logistic regression。

Sigmoid Function

Logistic regression 引入了 Sigmoid function 建立预测模型。

Sigmoid function 是一个 S 型函数，向 \(+\infty\) 逼近 \(1\)，向 \(-\infty\) 逼近 \(0\)。拜该结构所赐，linear regression 中的 outliers 被 sigmoid function 所消解。 \[ g(z)=\frac{1}{1+e^{-z}}, \ \ 0<g(z)<1 \] Logistic function: \[ f_{\vec{w},b}(x)=g(\vec{w}\vec{x}+b)=\frac{1}{1+e^{-(\vec{w}\vec{x}+b)}} \] 我们赋予 \(f_{\vec{w},b}(\vec{x})\) 意义：\(f_{\vec{w},b}(\vec{x})\) is the "probability" that class is \(1\). 例如，对某个输入 \(x_p\)，若 \(f_{\vec{w},b}(\vec{x_p})=0.7\)，我们说预测结果为 \(1\) 的可信度是 \(70\%\)。

Logistic regression 模型已经建立起来了。对于输入 \(\vec{x_p}\)：

  • \(f_{\vec{w},b}(\vec{x_p})\geq 0.5\)，预测结果为 \(1\)。
  • \(f_{\vec{w},b}(\vec{x_p})<0.5\)，预测结果为 \(0\)。

问题再次来到 cost function 的设计：如何找到最优的 \(\vec{w},b\)，使得对应的 logistic regression 模型能作出最准确的预测？

Decision Boundary

在 logistic regression 中，\(z=\vec{w}\vec{x}+b\)，而 \(f_{\vec{w},b}(\vec{x})=g(z)\)。

我们把 \(z=0\) 称为 decision boundary。这是因为在 \(z=0\) 时，\(f_{\vec{w},b}(\vec{x})=0.5\)；decision boundary 将预测空间分为两部分，一侧预测的结果为 \(1\)，另一侧预测的结果为 \(0\)。

有时我们能看到 non-linear decision boundary：这是因为对于更复杂的 classification 问题，\(z\) 不一定是线性的。例：\(z=x_1^2+x_2^2-1\)，此时的 decision boundary 是以原点为圆心，半径为 \(1\) 的圆。


Logistic Loss Function

若仍采用 square error function 计算 cost，cost function \(J_{w,b}\) 将呈现 non-convex 形态，这意味着它将具有多个 local minimum；这很不利于我们进行 gradient descent。

对于某个 logistic regression \(f_{\vec{w}, b}\)，数据集中的第 \(i\) 个 example \((\vec{x}^{(i)}, y^{(i)})\) 的损失 Loss function 是： \[ L(f_{\vec{w}, b}(\vec{x}^{(i)}), y^{(i)})= \begin{cases} -\log(f_{\vec{x},b}(\vec{x}^{(i)})), \ \ \ \ \ \ \ \ \ \mathrm{if} \ y^{(i)}=1 \\ -\log(1-f_{\vec{x},b}(x^{(i)})), \ \ \mathrm{if} \ y^{(i)}=0 \end{cases} \] 这个函数设计的很巧妙。分析一下：注意 \(f_{\vec{x},b}(x^{(i)})\) 是拟合值，\(y^{(i)}\) 是实际值。

  • 实际值为 \(0\)：
    • 预测值为 \(0\)：预测为 \(1\) 的可能性为 \(0\) (预测成功的可能性是 \(100\%\)) 损失 \(L=-\log(1)=0\)。
    • 预测值为 \(1\)：预测为 \(1\) 的可能性为 \(1\) (预测成功的可能性为 \(0\))，损失 \(L=-\log(0)=+\infty\)。
    • 在这之间：预测成功的可能性由高到低，损失从 \(0\) 急剧提升至 \(+\infty\)。
  • 实际值为 \(1\)：
    • (同上，略)

Intuitively，这个 loss 函数的设计刻意加大了预测成功与预测失败间的代价，这样就消除了多个 local minumum 同时存在的可能性。

Loss function 的简化形式如下： \[ L(f_{\vec{w},b}(x^{(i)}), y^{(i)})=-y^{(i)}\log(f_{\vec{x},b}(\vec{x}^{(i)}))-(1-y^{(i)})\log(1-f_{\vec{x},b}(\vec{x}^{(i)})) \] Logistic regression 的 cost function \(J(\vec{w},b)\) 即为各 examples loss 的平均值： \[ \begin{aligned} J(\vec{w},b)&=\frac{1}{m}\sum_{i=1}^m L(f_{\vec{w},b}(\vec{x}^{(i)}), y^{(i)})\\&=-\frac{1}{m}\sum_{i=1}^m[y^{(i)}\log(f_{\vec{x},b}(\vec{x}^{(i)}))+(1-y^{(i)})\log(1-f_{\vec{x},b}(\vec{x}^{(i)}))] \end{aligned} \] 可以证明这样设计的 cost function 是 convex-shaped 的，只存在一个 global minimum；除此之外，其对应的 gradient 形式与 linear regression 完全一致！

Repeat { \[ \begin{aligned} w_j&=w_j-\alpha[\frac{1}{m}\sum_{i=1}^m(f_{\vec{w},b}(\vec{x}^{(i)})-y^{(i)})x_j^{(i)}]\\ b_j&=b_j-\alpha[\frac{1}{m}\sum_{i=1}^m (f_{\vec{w},b}(\vec{x}^{(i)})-y^{(i)})] \end{aligned} \] } until convergence.

其中 \(f_{\vec{w},b}(\vec{x})=\frac{1}{1+e^{-\vec{w}\cdot \vec{x}}+b}\) (与 linear regression 唯一的区别)。


Overfitting

不理想的模型通常是：

  • underfit. 即使是 cost function 的最小值也显得过大，与数据拟合程度低。
  • overfit. 通常发生在 features 过多 (尤其是 polynomial features) 时，回归曲线不惜斗折蛇行都要与训练集中的所有数据拟合。拟合程度过高导致预测值准确率低。

对于 underfit，通常我们需要设计一个表现更优秀的模型；但 overfit 还“有救”。我们通过这三种方式解决模型的 overfitting 现象：

  • Collect more training data (也适用于 underfit).
  • Feature Selection: select features to be included/excluded.
  • Regularization.

我们将着重介绍 Regularization 这一 technique。


Regularization

首先我们需要认识一个规律：越复杂的模型越容易发生 overfit。很容易理解，复杂的模型才可能产生出复杂的曲线，从而以一种不自然的形式产生了过拟合。

因此，一种解决 overfit 的方案是移除部分 features，对模型进行简化；但采用这种方法损失了一部分信息。

移除 features \(x_i\) 的本质其实是将其对应的参数 \(w_i\) 设为 \(0\)。按照这个思路，我们提出了 regularization 这一方案：我们使得 features \(x_i\) 对应的参数尽量小，不就能够在不损失信息的情况下简化模型了吗？

Regularization 要求我们重新设计 cost function，使得 gradient descent 能够实现以下两种目的：

  • 最小化 cost function。
  • 尽量最小化参数 \(w_i\)。

我们重定义 cost function \(J(w,b)\) 为： \[ J(w,b)=\frac{1}{2m}\sum_{i=1}^{m}L(f_{\vec{w},b}(\vec{x}^{(i)}),y^{(i)})+ \frac{\lambda}{2m}\sum_{i=1}^nw_j^2 \] \(\lambda\) 是 regularization parameter: it balances both goals。gradient descent 算法使得 \(J(w,b)\) 尽量小，也就是使得 total loss 与 regularization term 尽量小。如果：

  • \(\lambda\) 过大，即 regularization term 对 \(J_{\vec{w},b}\) 的贡献较大；梯度下降将优先最小化 regularization term。模型向 underfit 方向移动。
  • \(\lambda\) 过小，即 total loss 对 \(J_{\vec{w},b}\) 的贡献较大；梯度下降将优先最小化 total loss。模型向 overfit 方向移动。

\(L\) 是 loss function。

  • linear regression 中 \(L(f_{\vec{w},b}(\vec{x}^{(i)}),y^{(i)})=(f_{\vec{w},b}(\vec{x}^{(i)})-y^{(i)})^2\)，其中 \(f_{\vec{w},b}(\vec{x}^{(i)})=\vec{w}\cdot\vec{x}+b\).
  • logistic regression 中 \(L(f_{\vec{w},b}(x^{(i)}), y^{(i)})=-y^{(i)}\log(f_{\vec{x},b}(\vec{x}^{(i)}))-(1-y^{(i)})\log(1-f_{\vec{x},b}(\vec{x}^{(i)}))\)，其中 \(f_{\vec{w},b}(\vec{x}^{(i)})=\mathrm{sigmoid}(\vec{w}\cdot\vec{x}+b)\).

接下来是 regularized gradient descent：linear regression 与 logistic regression 的形式完全一致，仅仅在对 \(f\) 的定义上有差别。

repeat { \[ \begin{aligned} w_j&=w_j-\alpha[\frac{1}{m}\sum_{i=1}^m(f_{\vec{w},b}(\vec{x}^{(i)})-y^{(i)})x_j^{(i)}]+\frac{\lambda}{m}w_j\\ b_j&=b_j-\alpha[\frac{1}{m}\sum_{i=1}^m (f_{\vec{w},b}(\vec{x}^{(i)})-y^{(i)})] \end{aligned} \] } until convergence.


Reference

  This article is a self-administered course note.

  References in the article are from corresponding course materials if not specified.

Course info: Machine Learning Specialization, Stanford & DeepLearning.AI.

  • Supervised Machine Learning - Regression and Classification.
  • Advanced Learning Algorithms.
  • Unsupervised Learning, Recommenders, Reinforcement Learning.

Lecturer: Professor Andrew Ng.

-----------------------------------そして、次の曲が始まるのです。-----------------------------------