5.1 Learning Algorithms

  • Learn 的定义: Task( $T$ ) + Experince( $E$ ) + Performance( $P$ ) 。

5.1.1 The Task, $T$

  • 分类:有函数 $f$ ,一般可以分为两种

    • $f$ 将 $x\in \mathbb{R}^n$ 映射为一个表示种类的数 $y\in \{1,\dots,k\}$ 。
    • $f$ 将 $x\in \mathbb{R}^n$ 映射为一个表示落入各个种类的概率 $\pmb{y}_i \in [0,1]$ 。
  • 输入缺失的分类:对于输入有缺失的分类,如果有 $n$ 个输入变量,需要对于可能的缺失定义 $2^n$ 个不同的分类函数。一般是直接学习联合概率分布,通过边缘化获得需要的函数。
  • 回归:有函数 $f: \mathbb{R}^n \to \mathbb{R}$ ,即对于输入相应地输出一个连续的值。
  • 转录:将非结构化的数据转换为离散的文本表示,例如图片中的文字识别、演讲文字提取等。
  • 机器翻译:将输入的语言转换为输出的语言,例如英法转换。
  • 结构化输出:输出相互间有关系的数据,例如语法分析后输出语法树、对于一张图片输出描述文字等。
  • 异常检测:可用于信用卡消费记录检测,一旦有异常则冻结。
  • 合成和采样:机器学习程序生成一些和训练数据相似的新样本,以避免大量重复的工作。例如,游戏背景的生成、根据文字生成方差较大的语音等。
  • 缺失值填补:填补 $\pmb{x}\in \mathbb{R}$ 中缺失的 $x_i$ 。
  • 去噪:根据被污染的 $\widetilde{\pmb{x}}$ 预测 $\pmb{x}$ ,或者更一般地根据 $\widetilde{\pmb{x}}$ 得出 $p(\pmb{x}|\widetilde{\pmb{x}})$ 。
  • 密度估计或概率质量函数估计:有函数 $p_{\mathrm{model}}:\mathbb{R}^n \to \mathbb{R}$ ,其中 $p_{\mathrm{model}}$ 是样本采样空间的概率密度函数或概率质量函数。

5.1.2 The Performance Measure, $P$

  • 对于分类、转录任务,一般度量准确率或错误率。
  • 对于密度估计任务,要使输出对于每个样本都输出一个连续数值的得分,常用方法是输出模型在一些样本上概率对数的平均值。
  • 有时很难确定应该度量什么,有时很难度量指定的值。

5.1.3 The Experience, $E$

  • 无监督学习:预测 $p(\mathrm{\pmb{x}})$ 。

    • 学习数据集的概率分布:显式(密度函数)或隐式(合成和去噪)。
    • 其他任务,例如聚类。
    • 利用链式法则 $p(\pmb{\mathrm{x}})=\prod\limits_{i=1}^n p(\mathrm{x}_i|\mathrm{x}_1,\dots,\mathrm(x)_{i-1})$ ,可以将无监督学习拆分为 $n$yuah 个监督学习。
  • 监督学习:数据集包括标签,预测 $p(\mathrm{\pmb{y}}|\mathrm{\pmb{x}})$ 。

    • 利用 $p(y|\pmb{\mathrm{x}})=\frac{p(\pmb{\mathrm{x}},y)}{\sum_{y'}p(\pmb{\mathrm{x}},y')}$ 可以利用无监督学习进行监督学习。
  • 数据集采用设计矩阵表示,其中每行表示一个样本,每列表示一个特征。

5.1.4 Example: Linear Regression

  • $\hat{y}=\pmb{w}^T\pmb{x}$ ,其中 $\pmb{x} \in \mathbb{R}^n,\hat{y} \in \mathbb{R},\pmb{w} \in \mathbb{R}^n$ , $\hat{y}$ 是对于 $y$ 的预测值。

    • 损失函数 $\mathrm{MSE_{test}}=\frac{1}{m}\sum\limits_i (\hat{\pmb{y}}^{(test)}-\pmb{y}^{(test)})^2_i=\frac{1}{m}||\hat{\pmb{y}}^{(test)}-\pmb{y}^{(test)}||^2_2$
    • 推导过程
  • $\hat{y}=\pmb{w}^T\pmb{x}+b$ ,其中 $\pmb{x} \in \mathbb{R}^n,\hat{y} \in \mathbb{R},\pmb{w} \in \mathbb{R}^n,b \in \mathbb{R}$ , $\hat{y}$ 是对于 $y$ 的预测值。

    • 过原点的仿射函数是线性函数。
    • 可以在 $\pmb{x}$ 中添加一项 $1$ ,在 $\pmb{w}$ 中添加一项 $b$ 。

5.2 Capacity, Overfitting and Underfitting

  • 泛化(generalization):在未训练的数据上表现良好的能力。
  • 训练误差泛化误差
  • 独立同分布假设:假设数据集中的每个样本彼此相互独立,并且训练集和测试集同分布。可以用此分布 $p_{\mathrm{data}}$ 来生成每一个训练样本和测试样本。
  • 从理论上来讲,对于固定的 $\pmb{w}$ 和分布 $p(\pmb{x},y)$ ,训练集和数据集会有相同的误差期望。但实际操作中,我们是先生成数据集,然后根据训练集训练出最合适的 $\pmb{w}$ 。我们需要同时降低训练误差降低泛化误差和训练误差的差距,由此引发两个问题:

    • 欠拟合:训练误差不够小。
    • 过拟合:泛化误差和训练误差差距太大。
  • 容量:模型拟合函数的能力。容量小可能会欠拟合,容量大可能会过拟合。

    • 可以通过增加输入特征的数目,和同时增加对应的参数来改变模型的容量。
    • 表示容量:算法可以选择的函数族,有效容量一般小于表示容量。
    • Occam's razor:在同样能够解释已观测现象的假设中,选择最简单的一个。
    • VC维度:分类器能够分类的训练样本的最大数目。
  • 训练误差和泛化误差的差异的上界随着模型容量增长而增长,随着训练样本增多而下降,只能提供理论验证,但很难运用于实际。
  • 非参数模型

    • 有时是不能实际实现的抽象理论,例如搜索所有可能概率分布的算法。
    • 也可以让复杂度与训练集大小相关,例如最近邻回归。

      • 对于测试点 $\pmb{x}$ ,求 $\hat{y}=y_i$ ,其中 $i=\mathop{\arg\min}||\pmb{X}_{i,:}-\pmb{x}||^2_2$ 。
      • 也可以拓展为其他的距离度量,例如学成距离度量。
    • 可以在参数学习算法外面嵌套另一个增加参数数目的算法。
  • 贝叶斯误差:假设能够预先知道数据的真实概率分布,由于噪声出现的误差。

5.2.1 The No Free Lunch theorem

  • 没有免费午餐定理:在所有可能的分布上平均之后,每一个分类算法在未事先观测的点上都有相同的错误率。
  • 机器学习算法是针对某一分布的。

5.2.2 Regularization

  • 权重衰减:例如,$J(\pmb{w})=\mathrm{MSE_{train}}+\lambda\pmb{w}^\mathrm{T}\pmb{w}$ ,其偏好于平方 $L^2$ 范数较小的权重。
  • 更一般地,对于 $f(\pmb{x};\pmb{\theta})$ ,可以给代价函数添加正则化项的惩罚。

5.3 Hyperparameters and Validation Sets

  • 超参数:用于控制算法,一般不被算法优化。例如:线性回归的次数、正则化项的权重等。

    • 一种情况是,超参数很难被算法优化。
    • 另一种情况是,在训练集上优化超参数不合适。例如,线性回归会永远选择较高的次数趋近于零的正则化权重
  • 验证集:从训练集中划分一部分出来,用于估计泛化误差,以优化超参数。

5.3.1 Cross-Validation

  • 当数据集比较小的时候,会有较大的统计不确定性。
  • $k$ 折交叉验证过程:将数据集轮流 $k$ 次分为互不交叉的训练集和测试集,最终得到泛化误差 $\pmb{e}$ 向量。

5.4 Estimators, Bias and Variance

5.4.1 Point Estimation

  • 点估计

    • 借助总体 $X$ 的一个样本估计总体未知参数。
    • 令 $\{\pmb{x}^{(1)},\dots,\pmb{x}^{(m)}\}$ 是 $m$ 个独立同分布的数据点,点估计是这些数据的任意函数 $\hat{\pmb{\theta}_m}=g(\pmb{x}^{(1)},\dots,\pmb{x}^{(m)})$ 。
  • 函数估计:输入和目标变量之间关系的估计。

5.4.2 Bias

  • 点估计的偏移: $\mathrm{bias}(\hat{\pmb{\theta}}_m)-\pmb{\theta}$ 。
  • 无偏的: $\mathrm{bias}(\hat{\pmb{\theta}}_m)=\pmb{0}$ 。
  • 渐近无偏的: $\mathrm{lim}_{m \to \infty}\mathrm{bias}(\hat{\pmb{\theta}}_m)=\pmb{0}$ 。
  • 例子

    • 伯努利分布 $\theta$
    • 高斯分布 $\mu$
    • 高斯分布 $\sigma ^2$ 有偏估计
    • 高斯分布 $\sigma ^2$ 无偏估计

5.4.3 Variance and Standard Error

  • 估计量的方差: $\mathrm{Var}(\hat{\theta})$
  • 估计量的标准差: $\mathrm{SE}(\hat{\theta})$
  • 样本方差的平方根和方差无偏估计的平方根都不是标准差的无偏估计。
  • 均值的标准差

    • $\mathrm{SE}(\hat{\mu}_m)=\frac{\sigma}{\sqrt{m}}$
    • 在机器学习领域很重要,因为通常用测试集样本的均值来估计泛化误差。

5.4.4 Trading off Bias and Variance to Minimize Mean Squared Error

  • 一种方法是交叉验证
  • 另一种方法是比较均方误差

    • $\mathrm{MSE}=\mathbb{E}[(\hat{\theta}_m-\theta)^2]=\mathrm{Bias}(\hat{\theta}_m)^2+\mathrm{Var}(\hat{\theta}_m)$

5.4.5 Consistency

  • 一致性(弱一致性): $\mathrm{plim}_{m\to \infty}\hat{\theta}_m=\theta$ ,也就是说当数据集中点的数量增加时,点估计会收敛到对应的真实值。
  • 几乎必然收敛(强一致性):当 $p(\mathrm{lim}_{m\to \infty} \mathrm{\pmb{x}}^{(m)}=\pmb{x})=1$ 时,随机变量序列 $\mathrm{x}^{(1)},\mathrm{x}^{(2)},\dots$ 收敛到 $x$ 。
  • 一致性保证了估计量的偏差会随着样本数量的增多而减少,反之不正确。

5.5 Maximum Likelihood Estimation

  • 假设 $m$ 个样本 $\mathbb{X}=\{\pmb{x}^{(1)},\dots,\pmb{x}^{(m)}\}$ 独立且服从同一分布 $p_{\mathrm{data}}(\mathrm{\pmb{x}})$ ,该分布是未知的数据生成分布。我们要用 $p_{\mathrm{model}}(\pmb{x},\pmb{\theta})$ 来近似未知分布 $p_{\mathrm{data}}(\mathrm{\pmb{x}})$ ,其中 $\theta$ 是一组参数。
  • 所以我们定义 $\pmb{\theta}_{\mathrm{ML}}=\mathop{\arg\max}\limits_{\pmb{\theta}} p_{\mathrm{model}}(\mathbb{X}; \pmb{\theta})$ ,也就是让服从未知分布的样本在新的分布中拥有大概率出现。因为是独立的样本,所以转化为 $\pmb{\theta}_{\mathrm{ML}}=\mathop{\arg\max}\limits_{\pmb{\theta}} \prod\limits_{i=1}^m p_{\mathrm{model}}(\pmb{x}^{(i)}; \pmb{\theta})$ 。
  • 由于乘积计算困难且可能造成下溢,取 $\mathrm{log}$ ,得 $\pmb{\theta}_{\mathrm{ML}}=\mathop{\arg\max}\limits_{\pmb{\theta}} \sum\limits_{i=1}^m \mathrm{log} p_{\mathrm{model}}(\pmb{x}^{(i)}; \pmb{\theta})$ 。
  • 对于式子除以 $m$ ,不影响结果,得 $\pmb{\theta}_{\mathrm{ML}}=\mathop{\arg\max}\limits_{\pmb{\theta}} \mathbb{E}_{\mathrm{\pmb{x}}\sim \hat{p}_{\mathrm{data}}} \mathrm{log} p_{\mathrm{model}}(\pmb{x}; \pmb{\theta})$ 。
  • 最大化似然估计和最小化 KL 散度是等价的, KL 散度定义为 $D_{\mathrm{KL}}(\hat{p}_{\mathrm{data}}||p_{\mathrm{model}})=\mathbb{E}_{\mathrm{\pmb{x}}\sim \hat{p}_{\mathrm{data}}}[\mathrm{log} \hat{p}_{\mathrm{data}}(\pmb{x})-\mathrm{log} p_{\mathrm{model}}(\pmb{x})]$ 。由于第一部分与模型无关,因此在训练时只需最小化 $-\mathbb{E}_{\mathrm{\pmb{x}} \sim \hat{p}_{\mathrm{data}}}[\mathrm{log}p_{\mathrm{model}}(\pmb{x})]$ ,这就是交叉熵,在之前也提到过。
  • 二者是等价的,但一般会选择最小化 KL 散度的方法,因为已知 KL 散度是非负的。

5.5.1 Conditional Log-Likelihood and Mean Squared Error

  • 对于监督学习的最大似然函数: $\pmb{\theta}_{\mathrm{ML}}=\mathop{\arg\max}\limits_{\pmb{\theta}}\sum\limits_{i=1}^m\mathrm{log}P(\pmb{y}^{(i)}|\pmb{x}^{(i)};\theta)$ 。
  • 线性回归

    • 不只预测 $\hat{y}$ ,而是最大似然 $p{y|\pmb{x}}$ 。
    • 定义 $p{y|\pmb{x}}=\mathcal{N}(y;\hat{y}(\pmb{x};\pmb{w}),\sigma^2)$ 。
    • 可以看出最小化 $\sum\limits_{i=1}^m\mathrm{log}P(y^{(i)}|\pmb{x}^{(i)};\theta)=-m\mathrm{log}\sigma-m/2\mathrm{log}(2\pi)-\sum\limits_{i=1}^m\frac{||\hat{y}^{(i)}-y^{(i)}||^2}{2\sigma^2}$ ,这和最大化 $\mathrm{MSE}_{\mathrm{train}}=\frac{1}{m}\sum\limits_{i=1}^m||\hat{y}^{(i)}-y^{(i)}||^2$ 是等价的,所以 MSE 不是没有道理的。
    • 注意这里的参数就是 $\pmb{w}$ ,只是这本书里统一都用 $\pmb{\theta}$ 表示了 。

5.5.2 Properties of Maximum Likelihood

  • 不存在均方误差低于最大似然估计的一致估计.
  • 在满足一定的条件时,训练样本数目趋向于无穷大,参数的最大似然估计会收敛到参数的真实值。这些条件是:

    • 真实分布 $p_{\mathrm{data}}$ 必须在模型族 $p_{\mathrm{model}}(\cdot;\pmb{\theta})$ 中。
    • 真实分布 $p_{\mathrm{data}}$ 必须正好对应一个 $\theta$ 。

5.6 Bayesian Statistics

  • 关于贝叶斯的资料:贝叶斯方法理解(1)— 从先验到后验 的一系列。
  • 频率派与贝叶斯统计

    • 频率派的观点:采样而得的数据本身服从的分布是确定的,其中参数 $\theta$ 是未知的,但是一个定值,所以我们用采样法去估计未知参数。
    • 贝叶斯统计的观点:采样得到的数据是确定的,但是其服从的分布是未知的,也就是参数 $\theta$ 是未知的不确定的。
  • 贝叶斯公式: $p(\pmb{\theta}|x^{(1)},\dots,x^{(m)})=\frac{p(x^{(1)},\dots,x^{(m)}|\pmb{\theta})p(\pmb{\theta})}{p(x^{(1)},\dots,x^{(m)})}$ ,其中 $p(\pmb{\theta})$ 是先验概率分布,一般选择高熵的作为初始。
  • 在观测完 $m$ 个样本后,下一个数据样本 $x^{(m+1)}$ 的预测分布为: $p(x^{(m+1)}|x^{(1)},\dots,x^{(m)})=\int p(x^{(m+1)}|\pmb{\theta})p(\pmb{\theta}|x^{(1)},\dots,x^{(m)})d\theta$
  • 贝叶斯线性回归

    • $p(\pmb{y}|\pmb{X},\pmb{w})=\mathcal{N}(\pmb{y};\pmb{Xw},\pmb{I})$
    • $p(\pmb{w})=\mathcal{N}(\pmb{w};\pmb{\mu}_0,\pmb{\Lambda})$
    • $p(\pmb{w}|\pmb{X},\pmb{y})=p(\pmb{y}|\pmb{X},\pmb{w})p(\pmb{w})$
    • 令 $\pmb{\Lambda}_m=(\pmb{X}^\mathrm{T}\pmb{X}+\pmb{\Lambda}_0^{-1})^{-1}, \pmb{\mu}_m=\pmb{\Lambda}_m(\pmb{X}^{\mathrm{T}}y+\pmb{\Lambda}_0^{-1}\mu_0)$ ,去掉与 $\pmb{w}$ 无关项可得 $p(\pmb{w}|\pmb{X},\pmb{y})\propto \mathrm{exp}(-\frac{1}{2}(\pmb{w}-\pmb{\mu}_m)^{\mathrm{T}}\pmb{\Lambda}_m^{-1}(\pmb{w}-\pmb{\mu}_m))$ 。

5.6.1 Maximum a Posteriori (MAP) Estimation

  • $\pmb{\theta}_{\mathrm{MAP}}=\mathop{\arg\max}\limits_{\pmb{\theta}}=\mathop{\arg\max}\limits_{\pmb{\theta}}\mathrm{log}p(\pmb{x}|\pmb{\theta})+\mathrm{log}p(\pmb{\theta})$
  • 当先验概率服从 $\mathcal{N}(\pmb{w};\pmb{0},\frac{1}{\lambda}\pmb{I}^2)$ 时,对数先验项正比于权重衰减惩罚 $\lambda \pmb{w}^\mathrm{T} \pmb{w}$ 。

5.7 Supervised Learning Algorithms

5.7.1 Probabilistic Supervised Learning

  • 逻辑回归:解决二分类问题。

    • $p(y=1|\pmb{x};\pmb{\theta})=\sigma(\pmb{\theta}^\mathrm{T}\pmb{x})$
    • 由于没有闭式解,无法直接求解,一般采用梯度下降法优化。
  • 监督学习问题:确定输入输出变量上的条件概率分布。

5.7.2 Support Vector Machines

  • 支持向量机不输出概率,只根据 $\pmb{w}^\mathrm{T}\pmb{x}+b$ 的正负输出分类。
  • 支持向量机全讲解:SVM系列-从基础到掌握
  • 核函数: $k(\pmb{x},\pmb{x}^{(i)})=\phi(\pmb{x})\cdot \phi(\pmb{x}^{(i)})$ 。

    • 核函数等价于用 $\phi(\pmb{x})$ 预处理所有输入,在新空间学习线性模型。
    • 核函数的实现方法通常比 $\phi(\pmb{x})$ 算点积高效。
    • 高斯核: $k(\pmb{u},\pmb{v})=\mathcal{N}(\pmb{u}-\pmb{v};\pmb{0},\sigma^2\pmb{I})$ 。

      • radial basis function(RBF),值沿着 $\pmb{v}$ 中从 $\pmb{u}$ 向外辐射的方向减小。
      • 模板匹配
  • 支持向量:$\pmb{\alpha}_i$ 非零。

5.7.3 Other Simple Supervised Learning Algorithms

  • $k$ -近邻
  • 决策树

5.8 Unsupervised Learning Algorithm

  • 无监督学习一般指不需要人为劳动标注数据,即可从某一分布中提取信息的方法。
  • 一般简化表示分为三种:

    • 低维表示
    • 稀疏表示:特征中尽量多位是 $0$ 。
    • 独立表示

5.8.1 Principal Components Analysis

  • PCA 学习低维表示独立表示,它学习一种线性投影,使方差最大的方向和新的坐标轴对齐。

    • 特征维度减小,在2.12部分已经讲过。
    • 特征之间将没有线性关系为此处要讨论的内容,但有可能还有非线性关系。
  • 假设有一个 $m \times n$ 的设计矩阵 $X$ 。

    • 其均值为零,即 $\mathbb{E}[\pmb{x}]=0$ ,如果不满足则同减。
    • 其无偏样本协方差矩阵为 $\mathrm{Var}[\pmb{x}]=\frac{1}{m-1} \pmb{X}^{\mathrm{T}} \pmb{X}$ 。
    • 将 $X$ 进行奇异值分解可得 $\pmb{X}=\pmb{U \pmb{sum} \W}^{\mathrm{T}}$ 。
  • PCA 对 $X$ 进行线性变换,假设 $\pmb{z}=\pmb{W}^{\mathrm{T}}\pmb{x}$ 。

    • 可推导得 $\mathrm{Var}[\pmb{z}]=\frac{1}{m-1}\pmb{sum}^2$ 。
    • 由于 $\pmb{sum}$ 是对角矩阵,所以 $\pmb{z}$ 中的元素是彼此线性无关的。

5.8.2 $k$-means Clustering

  • $k$-means 输出 one-hot 编码,实质上是一种稀疏表示
  • 过程:双层迭代。

    • 每个训练样本被分类至最近的簇。
    • 更新每个簇的中心点。
  • 没有标准去度量分类效果的好坏。

5.9 Stochastic Gradient Descent(SGD)

  • 如果训练集有 $m$ 个样本,梯度下降法的时间复杂度是 $O(m)$ 的,这在数据集很大时会非常慢。
  • 由于梯度下降法本质上是在求期望 $\mathbb{E}_{\mathrm{pmb{x}},\mathrm{y}\sim \hat{p}_{\mathrm{data}}}$ 的梯度,所以可以选取一小批量样本来近似估计梯度。

5.10 Building a Machine Learning Alogorithm

  • 深度学习算法:数据集、损失函数、优化过程、模型。
  • 常见损失函数:负对数似然,最小化损失函数等价于最大似然估计。
  • 当模型是线性的,可以直接求损失函数极值的闭式解,否则需要用梯度下降法。

5.11 Challenges Motivating Deep Learning

  • 传统机器学习泛化能力不足。

5.11.1 The Curse of Dimensionality

  • 高维空间中,样本数远远小于参数配置数目,而许多传统机器学习算法需要在泛化点附近找到最接近的训练点。

5.11.2 Local Constancy and Smoothness Regularization

  • 平滑先验:尽量满足 $f^*(\pmb{x})\approx f^*(\pmb{x}+\epsilon$)$ ,如果依赖于此很难在人工智能领域泛化,例如 $k$ -近邻、决策树。

5.11.3 Manifold Learning

  • 流形指连接在一起的区域,就是一组有邻域的点,每个邻域的定义暗示着存在变换能从一个位置走到邻域位置。
  • 让机器学习学习整个 $\mathbb{R}^n$ 上的函数很难,但是可以根据流形学习舍弃大部分无效的输入。
  • 生活中图像、文本、声音的概率分布都是高度集中的,否则会得到随机的噪声图像,例如马赛克。
最后修改:2020 年 11 月 26 日 02 : 54 PM
如果觉得我的文章对你有用,请随意赞赏