机器学习I - 综述与线性回归(Linear Regression)

机器学习是一门开发算法和统计模型的科学，计算机系统使用这些算法和模型，在没有明确指令的情况下，依靠既有模式和推理来执行任务。计算机系统使用机器学习算法来处理大量历史数据，并识别数据模式。这可让计算机系统根据给出的输入数据集更准确地预测结果。

1. 入门与一元线性回归

1.1 简介

机器学习模型主要有以下几种分类：

Supervised Machine Learning(监督学习)
Unsupervised Machine Learning(无监督学习)
Semi-supervised Machine Learning(半监督学习)
Reinforcement(强化学习)

主要先介绍监督学习与无监督学习

Supervised Machine Learning(监督学习)

在监督学习中，数据的训练集（输入数据）包括了标签，该标签可能是离散的或者连续的。例如分类模型，数据的训练集中都标注了该图片是狗或者是非狗，或者是某种狗的类型。
二元分类模型：狗
多元分类模型：狗
在回归模型中，需要预测的值为一个连续值，所以需要通过一些评判标准来进行预测。例如线性回归，是将每个点到预测线的误差值得集合最小化，来获得预测线。
线性回归模型：冰激凌价格vs温度

Unsupervised Machine Learning(无监督学习)

在现实生活中，带有标签的数据获得成本实际很高，所以催生了无监督学习的发展。与监督学习相对应的为无监督学习，即训练集中无现有标签。
常见的为Culstering Example(聚类模型)，根据准则（例如K-means和KNN）来将模型分类n类。

1.2 模型与代价函数 (Model and Cost Function)

1.2.1 模型

$x^{(i)}$ 输入变量 (input variables)

$y^{(i)}$ 输出变量 (output variables)

$(x^{(i)}, y^{(i)})$ 训练样本 (training example)

$(x^{(i)}, y^{(i)}); i = 1, …, m$ 训练集 (traing set)

$X, Y$ 输入特征和输出特征的空间(space)，例如$X \in \mathbb{R}, y \in \mathbb{R}$

一个有监督模型的过程，正式来讲，是根据训练集去学习一个假设(hypothesis)$h:X \to Y$，这样$h(x^{(i)})$便可以用来预测实际的$y^{(i)}$。例如下图：

graph TD
A(训练集 - Training Set):::box
--> B(算法 - Learning Algorithm):::box
--> C(h):::box
--> y:::box
x:::box --> C
classDef box fill:#ebf2ff, stroke:#000000

假设可以简单理解为是一种我们推测出的一种，事物间的关系。从数据的角度，关系即为一个函数。

衡量函数$h$的性能，我们一般使用代价函数(Cost Function)。

1.2.2 代价函数 (Cost Function)

以线性回归为例，$h_\theta(x) = \theta_0 + \theta_1x$，则线性回归的代价函数$J$则为平均预测值$h(x)$和实际值$y$之间的差，如：

$J(\theta_0,\theta_1) = \frac{1}{2m}(\hat{y}_i - y_i)^2 = \frac{1}{2m}\sum_{i=1}^m(h_\theta(x) - y_i)^2$

其中： $\theta$ 函数的参数，$m$ 训练集样本量

线性回归的代价函数一般也称之为MSE(均方误差 Mean Sqaure Error)，或者方差损失函数(Squared Error Function)。

乘以$\frac{1}{2}$是为了在使用梯度下降时计算的便利性，并无实际意义

1.3 梯度下降 (Gradient Descent)

目前我们拥有了假设函数$h_\theta$，以及测量假设函数的准确性的方法$J(\theta_0,\theta_1)$，我们便需要一个方法可以将代价函数最小化，从而最大限度的提升假设函数的准确性，这个方法便是梯度下降。

想象我们绘制一个三维曲面图，将假设函数$h_\theta$的参数$\theta_0,\theta_1$作为图的$x, y$轴，将$J(\theta_0,\theta_1)$作为$z$轴，梯度下降的概念是，我们随机选择一个点，然后环顾一周选择下降最快的一个方向，往下走一步，之后在不断重复，直到在最低点。

梯度下降的详细步骤如下：

$\begin{aligned} &重复直到收敛\ \{ \\ \ \ \ \ \ &\theta_j := \theta_j - \alpha \frac{\partial}{\partial\theta_j} J(\theta_0,\theta_1) \ \ (for\ j = 0\ and\ j = 1) \\ &\} \end{aligned}$

$:=$ 表示复制；$\alpha$代表学习率(Learning Rate)，也就是每次梯度下降的步长

1.3.1 学习率

如果学习率过小，梯度下降会很慢
如果学习率过大，梯度下降会略过收敛点，导致结果无法收敛

1.3.2 局部最优与全局最优

梯度下降会到局部最优，如果损失函数是凹函数，则不会有问题。

1.3.3 偏微分项

偏微分项$\frac{\partial}{\partial\theta_j} J(\theta_0,\theta_1)$是为了让每次的步长，越下降越小，以防止略过收敛点。

1.4 线性回归梯度下降 (Gradient Descent)

线性回归的梯度下降过程如下：

$\begin{aligned} &重复直到收敛\ \{ \\ \ \ \ \ \ &\theta_0 := \theta_0 - \alpha \frac{1}{m}(h_\theta(x^{(i)}) - y^{(i)})\\ \ \ \ \ \ &\theta_1 := \theta_1 - \alpha \frac{1}{m}(h_\theta(x^{(i)}) - y^{(i)})*x^{(i)}\\ &\} \end{aligned}$

其中：

$\begin{align} \frac{\partial}{\partial\theta_j} J(\theta) &= \frac{\partial}{\partial\theta_j} \frac{1}{2}(h_\theta(x)-y)^2 \\ &= 2 * \frac{1}{2}(h_\theta(x)-y)*\frac{\partial}{\partial\theta_j}(h_\theta(x)-y) \\ &= (h_\theta(x)-y) * \frac{\partial}{\partial\theta_j}(\sum_{i=0}^n \theta_ix_i - y) \\ &= (h_\theta(x) - y)x_j \end{align}$

线性回归的代价函数为凹函数，所以local minimum即为overall minimum。

2. 多元线性回归(Multivariate Linear Regression)

多元线性回归是在一元线性回归的基础上，有多个$x$

$x_j^{(i)}$ 输入特征$j$中，第$i$个的值

$m$ 训练样本量

$n$ 特征量

假设函数如下：

$h(\theta) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + ... + \theta_n x_n$

或矩阵形式：

$h(\theta) = \begin{bmatrix} \theta_0 & \theta_1 & ... & \theta_n \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ ... \\ x_n \end{bmatrix} = \theta^Tx$

2.1 多元线性回归的梯度下降

与一元线性回归类似

$\begin{aligned} &重复直到收敛\ \{\\ &\theta_j := \theta_j - \alpha \frac{1}{m}(h_\theta(x^{(i)}) - y^{(i)})*x_j^{(i)}\\ &\} \end{aligned}$

2.1.1 特征缩放(Feature Scaling)与标准化(Normalization)

不同的特征数值范围是不同的，比如$x_1$是从0-10，$x_2$是从0-1000，这样进行梯度下降时会过于慢，如下图：

调整方法有以下两种

特征缩放：每个特征值，除以该特征的取值范围(Range)，例如$x_1/10$ ，$x_2/1000$
标准化：$(x_i - \mu_i)/ s_i

2.1.2 多项式回归(Polynomial Regression)

在某些特定的输入特征，我们需要对其加工，例如合并多个特征变为一个，比如新增$x_2 = x_1 * x_1$，这样我们的假设函数就会变为

$h(\theta) = \theta_0 + \theta_1 x_1 + \theta_2 x_1^2$

经过乘方之后，$x$的取值范围会大大扩大，所以特征缩放就会变得极其重要

2.2 多元线性回归的正规方程(Normal Equation)

正规方程为另外一种最小化代价函数的方法。与梯度下降不同的是，正规方程不是使用多次迭代，不断寻找最小值的方法，而是可以直接计算出代价函数最小时，各$\theta$的值。推导过程如下：

多元线性回归的假设函数为

$h(\theta) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + ... + \theta_n x_n$

矩阵形式则为

$h(\theta) = \begin{bmatrix} \theta_0 & \theta_1 & ... & \theta_n \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ ... \\ x_n \end{bmatrix} = \theta^Tx$

多元线性回归的代价函数为

$J(\theta_{0...n}) = \frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})^2$

带入矩阵形式

$\begin{align} J(\theta) &= \frac{1}{2m}(X\theta-Y)^T(X\theta - Y) \\ J(\theta) &= \frac{1}{2m}((X\theta)^T - Y^T)(X\theta - Y) \\ J(\theta) &= \frac{1}{2m}((X\theta)^T(X\theta) - (X\theta)^TY -Y^T(X\theta) + Y^TY) \\ J(\theta) &= \frac{1}{2m}(X^T\theta^T(X\theta) - 2X^T\theta^TY + Y^TY) \\ \end{align}$

因为我们需要取代价函数的最小值，则对$J(\theta)$取偏导

$\begin{align} \frac{\partial J(\theta)}{\partial \theta} &= \frac{\partial \frac{1}{2m}(X^T\theta^TX\theta - 2X^T\theta^TY + Y^TY)}{\partial \theta} \\ \frac{\partial J(\theta)}{\partial \theta} &= \frac{1}{2m}*2*X^TX\theta - \frac{1}{2m}*2X^TY \\ \frac{\partial J(\theta)}{\partial \theta} &= \frac{1}{m}(X^TX\theta - X^TY) \end{align}$

最小化$J(\theta)$时，其的导数等于0

$\begin{align} 0 &= \frac{1}{m}(X^TX\theta - X^TY) \\ 0 &= X^TX\theta - X^TY \\ X^TX\theta &= X^TY \end{align}$

假设$X^TX$是可逆的，则

$\theta = (X^TX)^{-1}X^TY$

$X^TX$有时会是不可逆的，通常原因为：

有些特征是冗余的，或者说一些特征相互线性相关(Linearly Dependent)

样本量少于特征数量，也就是$ m<n $，这样我们需要对特征进行正则(Regularization)，来删除特征，后续会介绍这部分。

2.3 对比梯度下降与正规方程

梯度下降：

需要选择学习率$\alpha$
需要$k$次迭代
时间复杂度$O(kn^2)$
在特征数量$n$较大时，仍然适用

正规方程：

不需要选择学习率，不需要迭代
时间复杂度$O(n^3)$
在特征数量比较大时，速度较慢

3. 分类模型(Classification)与逻辑回归(Logistic Regression)

逻辑回归的假设函数为

$h_\theta(x) = g(\theta^Tx) = g(X\theta)$

其中

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

$g(z)$函数将实数域映射到$[0,1]$，之间从而满足分类的要求。例如，$g(z) = 0.7 $则代表分类为1的概率为70%。

故

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

3. 优化目标

3.1 代价函数

回想线性回归的代价函数为

$J(\theta_0,\theta_1) = \frac{1}{2m}\sum_{i=1}^m(h_\theta(x) - y_i)^2$

套用到逻辑回归中，其中

$h_\theta(x) = \frac{1}{1+e^{-\theta^Tx}}, \ y = 0 \ or \ 1$

这样我们的代价函数将不会是一个凹函数，梯度下降时，会陷入局部最小值，从而无法应用梯度下降。所以我们使用以下代价函数：

$J(\theta) = \frac{1}{m}\sum^m_{i=1}Cost(h_\theta(x^{(i)}),y^{(i)})$

其中

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

因为$y = 0 \ or \ 1$，所以可以简写为

$\begin{aligned} Cost(h_\theta(x),y) &= y(-log(h_\theta(x))) + (1-y)(-log(1-h_\theta(x))) \\ J(\theta) &= -\frac{1}{m}[\sum^m_{i=1} y^{(i)}log(h_\theta(x^{(i)})) + (1-y^{(i)})log(1-h_\theta(x^{(i)}))] \\ &= \frac{1}{m}(-y^Tlog(h)-(1-y)^Tlog(1-h)) \ \ \ \ \ and \ \ h=g(X\theta) \end{aligned}$

3.2 梯度下降

进行梯度下降，我们需要$min_\theta J(\theta)$

$\begin{aligned} &重复直到收敛 \{ \\ &\theta_j := \theta_j - \alpha \frac{\partial}{\partial\theta_j}J(\theta) \\ &\} \end{aligned}$

其中，

$\begin{aligned} \frac{\partial}{\partial\theta_j}J(\theta) &= \frac{\partial}{\partial\theta_j}[-\frac{1}{m}[\sum^m_{i=1} y^{(i)}log(h_\theta(x^{(i)})) + (1-y^{(i)})log(1-h_\theta(x^{(i)}))]] \\ &= \theta_j - \frac{\alpha}{m}\sum^m_{i=1}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} \\ &= \theta - \frac{\alpha}{m}X^T(g(X\theta)-Y) \end{aligned}$

有更复杂的优化方法，例如”Conjugate gradient”, “BFGS”, 和”L-BFGS”，可以在包中供我们使用

3.3 多分类问题(Multiclass Classification)

我们可以建立多个假设函数，每个假设函数将多个分类拆分为其中一个分类与全部其他分类，例如：

$y\in\{0,1,...,n\} \\ h_\theta^{(0)}=P(y=0|x;\theta) \\ h_\theta^{(1)}=P(y=1|x;\theta) \\ ... \\ h_\theta^{(n)}=P(y=n|x;\theta) \\$

reference
机器学习 by 周志华

本文使用 Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 许可协议，转载请注明出处。