统计机器学习 COMP90051 课程笔记

统计机器学习 03：线性回归与优化

墨尔本大学 COMP90051 课程笔记

Posted by YEY on November 7, 2019

Lecture 3 线性回归与优化

主要内容

  • 线性回归
    • 简单模型（方便的数学运算，以牺牲灵活性为代价）
    • 通常需要较少的数据，“可解释性”，可以扩展到非线性
    • 所有统计学派都可以推得
      • 在本节中，我们将通过 “频率学派 + 决策理论” 推得
      • 在后面的学习中，我们将介绍贝叶斯方法
  • 机器学习优化
    • 解析求解方案
    • 梯度下降
    • 凸性

    在后面的学习中，我们将讨论拉格朗日对偶。

1. 基于决策理论的线性回归

例子：根据温度预测湿度

在回归中，我们的任务是根据特征（即预测变量或自变量）预测数值响应（即因变量）。 假设现在有这样一个线性关系：$H=a+bT$ 其中，$H$ 表示湿度，$T$ 表示温度，$a$ 和 $b$ 是参数。

问题陈述

  • 模型： $H=a+bT$
  • 拟合模型 = 基于当前数据寻找 $a$ 和 $b$ 的最佳值
  • 常见标准：最小化平方和误差（又称残差平方和 $SSR$）

最小化平方和误差

寻找 $a$ 和 $b$，使得平方损失函数 $L=\sum_{i=1}^{10}(H_i-(a+bT_i))^2$ 最小化。 令偏导数为零：

$\dfrac{\partial L}{\partial a}=-2\sum_{i=1}^{10}(H_i-a-bT_i)=0$

如果我们知道 $b$，那么 $\hat a=\dfrac{1}{10}\sum_{i=1}^{10}(H_i-bT_i)$

$\dfrac{\partial L}{\partial b}=-2\sum_{i=1}^{10}T_i(H_i-a-bT_i)=0$

如果我们知道 $a$，那么 $\hat b=\dfrac{1}{\sum_{i=1}^{10}T_i^2}\sum_{i=1}^{10}T_i(H_i-a)$

常规步骤：

  • 写出偏导数
  • 令偏导数等于零
  • 求解得到模型
  • 检查二阶导

解析求解方案

  • 我们有两个等式和两个未知参数 $a,b$
  • 重写为线性方程组的形式：
    $\begin{pmatrix}10 & \sum_{i=1}^{10}T_i \\ \sum_{i=1}^{10}T_i &\sum_{i=1}^{10}T_i^2\end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}=\begin{pmatrix}\sum_{i=1}^{10}H_i \\ \sum_{i=1}^{10}T_i H_i\end{pmatrix}$

  • 解析求解方案：$a=25.3,b=0.77$
  • 利用 numpy.linalg.solve 或者 SymPy 求解。

更通用的决策规则

  • 在响应 $y\in\Bbb R$ 和具有特征 $x_1,…,x_m\in\Bbb R$ 的实例之间建立一个线性关系：
    $\hat y=w_0+\sum_{i=1}^{m}x_i w_i$
    这里，$w_0,…,w_m$ 表示权重（即模型参数）。
  • 技巧：增加一个虚拟特征 $x_0=1$，采用向量表示
    $\hat y=\sum_{i=0}^{m}x_i w_i=\boldsymbol{x’w}$

2. 基于频率概率模型的线性回归

最大似然估计

数据是带有噪声的

例子：根据 知识技术（KT） 的分数预测 统计机器学习（SML） 的分数。

回归的概率模型

  • 假设一个概率模型：$Y=\boldsymbol{X’w}+\varepsilon$
    • 这里，$\boldsymbol{X},Y$ 和 $\varepsilon$ 都是随机变量
    • 变量 $\varepsilon$ 编码了噪声
  • 接下来，假设高斯噪声（独立于 $\boldsymbol{X}$）：$\varepsilon \sim N(0,\sigma^2)$
  • 回忆：$N(x;\mu,\sigma^2)\equiv \dfrac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\dfrac{(x-\mu)^2}{2\sigma^2}\right)$
  • 因此， $p_{\boldsymbol{w},\sigma^2}(y|\boldsymbol{x})=\dfrac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\dfrac{(y-\boldsymbol{x’w})^2}{2\sigma^2}\right)$

参数概率模型

  • 采用简化表示，判别式模型为： $p(y|\boldsymbol{x})=\dfrac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\dfrac{(y-\boldsymbol{x’w})^2}{2\sigma^2}\right)$
  • 未知参数：$\boldsymbol{w}$
  • 给定观测数据 ${(\boldsymbol X_1,Y_1),…,(\boldsymbol X_n,Y_n)}$，我们希望找到能够 “最好地” 解释这些数据的参数值。
  • 最大似然估计：选择使得观测数据的概率最大化的参数值。

最大似然估计

  • 假设数据点之间互相独立，观测数据的概率为： $p(y_1,…,y_n|\boldsymbol x_1,…,\boldsymbol x_n)=\prod_{i=1}^{n}p(y_i|\boldsymbol x_i)$
  • 其中，$p(y_i|\boldsymbol x_i)=\dfrac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\dfrac{(y_i-\boldsymbol x_i’ \boldsymbol w)^2}{2\sigma^2}\right)$
  • “Log 技巧”：相比直接求上式的最大值，我们选择求上式的对数的最大值：
    $\sum_{i=1}^{n}\log p(y_i|\boldsymbol x_i)=-\dfrac{1}{2\sigma^2}\sum_{i=1}^{n}(y_i-\boldsymbol x_i’ \boldsymbol w)^2+C$
    这里，$C$ 是一个常量，与 $\boldsymbol w$ 无关。
  • 在该模型下，最大化以 $\boldsymbol w$ 为变量的对数似然函数，等价于最小化平方和误差。

3. 非线性连续优化

对机器学习至关重要的一些基本优化方法的简要概述

3.1 机器学习中的优化公式

  • 训练 = 拟合 = 参数估计
  • 典型公式 $\hat{\boldsymbol\theta}\in\mathop{\operatorname{arg\,min}}\limits_{\boldsymbol\theta\in\boldsymbol\Theta} L(data,\boldsymbol\theta)$
    • $\mathop{\operatorname{arg\,min}}$ 是因为我们希望最小化而非最小值
      • 注意：$\mathop{\operatorname{arg\,min}}$ 可能返回一个集合（最小化并非总是唯一的）
    • $\boldsymbol\Theta$ 表示一个模型簇（包含约束）
    • $L$ 表示某个需要优化的目标函数
      • 例如：MLE 中的（条件）似然函数
      • 例如：决策理论中的（正则化）经验风险

3.2 两种求解方案

  • 解析解（又称闭合解）
    • 仅在少数情况下可以得到

    • 假设无约束、$L$ 可微的情况下，令参数的一阶偏导为零： $\dfrac{\partial L}{\partial \theta_1}=…=\dfrac{\partial L}{\partial \theta_p}=0$

      注意：为了检查是否为局部最小值，需要二阶偏导大于 $0$（或者 Hessian 矩阵是正定的），这是在假定不受约束的前提下（通常还需要检查边界），另外请参考后面的拉格朗日方法。

  • 通过迭代求近似解
    1. 初始化：选择参数的初始值 $\boldsymbol\theta^{(1)}$，设置 $i=1$
    2. 更新：$\boldsymbol\theta^{(i+1)}\leftarrow SomeRule[\boldsymbol\theta^{(i)}]$，设置 $i\leftarrow i+1$
    3. 终止：决定是否停止
    4. 回到第 2 步
    5. 停止：返回 $\hat{\boldsymbol\theta}\approx\boldsymbol\theta^{(i)}$

3.3 寻找最深的点

  • 在这个例子中，模型具有 2 个参数。
  • 每个位置对应于参数值的特定组合。
  • 深度表示该候选模型在数据上的目标值（例如：损失函数）。

3.4 坐标下降

  • 假设 $\boldsymbol\theta=[\theta_1,…,\theta_K]’$
    1. 选择 $\boldsymbol\theta^{(1)}$ 和某个 $T$
    2. 对 $i$ 从 $1$ 到 $T$（也可以采用其他终止条件）：
    1. $\boldsymbol\theta^{(i+1)}\leftarrow\boldsymbol\theta^{(i)}$
    2. 对 $j$ 从 $1$ 到 $K$：
      1. 固定 $\boldsymbol\theta^{(i+1)}$ 部分，除了第 $j$ 项
      2. 找到使 $L\left(\theta_j^{(i+1)}\right)$ 最小化的 $\hat\theta_j^{(i+1)}$
      3. 更新 $\boldsymbol\theta^{(i+1)}$ 的第 $j$ 项
      4. 返回 $\hat{\boldsymbol\theta}\approx\boldsymbol\theta^{(i)}$

3.5 回忆：梯度

  • $\boldsymbol\theta$ 处的梯度定义为 $\left[\dfrac{\partial L}{\partial\theta_1},…,\dfrac{\partial L}{\partial\theta_p}\right]’$ 在 $\boldsymbol\theta$ 处的值。
  • 梯度指向从 $\boldsymbol\theta$ 点出发，$L(\boldsymbol\theta)$ 变化最大的方向。
  • 速记表示：
    • 计算在 $\boldsymbol\theta$ 点处的 $\nabla L\overset{\text{def}}{=}\left[\dfrac{\partial L}{\partial\theta_1},…,\dfrac{\partial L}{\partial\theta_p}\right]’$
    • 这里，$\nabla$ 是 “竖琴” 符号

3.6 梯度下降

  • 假设 $L$ 是可微的
    1. 选择 $\boldsymbol\theta^{(1)}$ 和某个 $T$
    2. 对 $i$ 从 $1$ 到 $T$（也可以采用其他终止条件）： $\boldsymbol\theta^{(i+1)}\leftarrow\boldsymbol\theta^{(i)}-\eta\nabla L(\boldsymbol\theta^{(i)})$
    3. 返回 $\hat{\boldsymbol\theta}\approx\boldsymbol\theta^{(i)}$
  • 注意：$\eta$ 在每一步中是动态更新的
  • 变体：随机梯度下降 (SGD)、小批量梯度下降 (Mini-batch SGD)、动量法 (Momentum)、AdaGrad算法等

3.7 凸目标函数

  • “碗形” 函数
  • 直观上，函数图像任意两点之间的线段位于函数图像上方。

  • 定义：

    $f:D\rightarrow\Bbb R$ 是凸函数，

    如果 $\forall \boldsymbol{a,b}\in D,t\in [0,1]$，都有：

    $f(t\boldsymbol a+(1-t)\boldsymbol b)\le tf(\boldsymbol a)+(1-t)f(\boldsymbol b)$

    当不等号为严格 ( $<$ ) 时，$f$ 为严格凸函数。

    此外，等效地，我们可以看一下二阶导：

    对于按标量定义的 $f$，二阶导应为非负；

    对于多元 $f$，Hessian 矩阵应为正半定。

  • 在（严格）凸函数上使用梯度下降，可以确保找到（唯一）全局最小值。

3.8 $L_1$ 与 $L_2$ 范数

  • 在整个课程中，我们经常会遇到范数，它们是一类具有特定形式的函数：$\Bbb R^n\rightarrow\Bbb R$
    • 直观上，范数在某种意义上衡量了向量的长度
    • 通常作为机器学习优化中的目标函数或者停止条件的一部分

  • 具体来说，我们将经常使用 $L_2$ 范数（又称欧几里德距离）:

    $\|\boldsymbol a\|=\|\boldsymbol a\|_2\equiv\sqrt{a_1^2+…+a_n^2}$

  • 以及 $L_1$ 范数（也称为绝对范数或曼哈顿距离）:

    $\|\boldsymbol a\|_1\equiv |a_1|+…+|a_n|$

  • 例如，平方和误差就是一个平方范数：

    $L=\sum_{i=1}^{n}\left(y_i-\sum_{j=0}^{m}X_{ij}w_j\right)^2=\|\boldsymbol y-\boldsymbol{Xw}\|^2$

以及更多

  • 如果存在约束怎么办？
  • 收敛速度如何？
  • 有没有比梯度下降更快的方法（有，但是可能会很昂贵）
  • 目标函数是否真的需要可微？（并不是）
  • 还有更多的技巧吗？（是的）

稍后我们将看到拉格朗日对偶。

我们已经见过的一个技巧：Log 技巧

  • 尝试用更方便的 $\log L(\theta)$ 代替优化 $L(\theta)$
  • 为什么我们可以这样做？
  • 严格单调（递增）函数：$a>b \Rightarrow f(a)>f(b)$
    • 例子：log 函数
  • 引理：考虑任意目标函数 $L(\theta)$ 和任意严格单调函数 $f$，$\theta^*$ 是 $L(\theta)$ 的一个最优解，当且仅当它是 $f(L(\theta))$ 的一个最优解。

4. 线性回归优化

对于 MLE / 决策理论的推导

4.1 最小二乘法

  • 训练数据：${(\boldsymbol x_1,y_1),…,(\boldsymbol x_n,y_n)}$ （注意：这里 $\boldsymbol x_i$ 是粗体，表示向量）
  • 为了方便，行代表实例（所以，列代表属性），用一个 $n\times(m+1)$ 的矩阵 $\boldsymbol X$ 和一个 $n$ 维向量 $\boldsymbol y$ 代表训练数据
  • 概率模型 / 决策规则假设：$\boldsymbol y\approx\boldsymbol{Xw}$

  • 为了找到 $\boldsymbol w$，最小化平方和误差：

    $L=\sum_{i=1}^{n}\left(y_i-\sum_{j=0}^{m}X_{ij}w_j\right)^2$

  • 令偏导数为零，对 $\boldsymbol w$ 求解：

    $\hat{\boldsymbol w}=(\boldsymbol{X’X})^{-1}\boldsymbol{X’y}$

    • 该方程组称为正规方程
    • 只有当矩阵的逆存在时，该方程组才是良定义的

（本教程中，粗体大写字母表示矩阵，$\boldsymbol{X’}$ 表示转置，$\boldsymbol{X}^{-1}$ 表示逆）

4.2 贝叶斯推导

  • 在后面的学习中，我们还会回头讨论线性回归
  • 完全贝叶斯，后验：
    • 贝叶斯线性回归
  • 权重向量的贝叶斯（MAP）点估计：
    • 对平方和损失函数增加一个惩罚项
    • 相当于我们即将学习的 $L_2$ “正则化”
    • 称为：岭回归

总结

  • 线性回归
    • 基于频率的概率推导
    • 基于频率的决策理论推导

    后期学习中，我们还会涉及贝叶斯方法

  • 机器学习优化

下节内容：Logistic 回归-用于分类的线性概率模型；非线性基扩展

知识共享许可协议本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。 欢迎转载，并请注明来自：YEY 的博客 同时保持文章内容的完整和以上声明信息！
CATALOG
    FEATURED TAGS
    随笔 课程笔记 统计机器学习 COMP90051 学习笔记 自然语言处理 COMP90042 PyTorch 人工智能伦理 COMP90087 数据科学多元统计学 MAST90138 AI 自动规划 COMP90054 数据分析 计算统计学与数据科学 MAST90083 高级数据库系统 COMP90050 统计建模 MAST90139 读书 📚 MySQL 学习索引 Hive 技术问题 Jekyll Workshop
    FRIENDS