数值计算

上溢和下溢

当接近0的数被四舍五入为0时发生下溢.
当大量级的数被近似为∞或-∞时发生上溢.

对上溢和下溢进行数值稳定的一个例子是softmax函数.

$Softmax(x)_ i=\frac{exp(x_i)}{\sum_{j=1}^nexp(x_j)}$

考虑一下当所有$x_i$都等于某个常数c时会发生什么.从理论上,我们发现所有的输出应该都是$\frac{1}{n}$.从数值计算上来说,当c很小的负数时,exp(c)会下溢.这就意味着softmax函数的分布会变为0,分子也为0，softmax的结果是未定义的.当c很大正数时,分子分母都是无穷大,其结果softmax同样是未定义的.
为解决上述问题,会用z_i=x_i-max_i x_i,然后对z进行softmax.这样就可以排除上溢和下溢的问题.

还有一个小问题,分子中的下溢仍可以导致整体表达式被计算为0.这意味着,如果我们在计算log softmax(x)时,先计算softmax再把结果传给log函数,会错误地得到-∞.相反,我们必须实现一个单独的函数,并以数值稳定的方式计算log softmax。我们可以使用相同的技巧来稳定log softmax函数.

病态条件

条件数指的是函数相对于输入的微小变化而变化的快慢程度.输入被轻微扰动而迅速改变的函数对于科学计算来说可能是有问题的,因为输入中的舍入误差可能导致输出的巨大变化。

考虑函数$f(x)=A^{-1}x$,当A∈$R^{n×n}$具有特征值分解时,其条件数为

$max_{i,j}|\frac{\lambda_i}{\lambda_j}|$

这是最大和最小特征值的模之比.该数很大时,矩阵求逆对输入的误差特别敏感.

这种敏感性是矩阵本身的固有特性,而不是矩阵求逆期间舍入误差的结果.即使我们乘以完全正确的矩阵逆,病态条件的矩阵也会放大预先存在的误差.

约束优化

有时候,在x的所有可能值下最大化或最小化一个函数f(x)不是我们所希望的.相反,我们可能希望在x的某些集合S中找f(x)的最大值或最小值.这称为约束优化.在约束优化术语中,集合S内的点x称为可行点.

KKT方法：是针对约束优化非常通用的解决方案.为介绍KKT方法,这里引入一个称为广义Lagrangian 的新函数

为了定义Lagrangian,我们先要通过等式和不等式的形式描述S.我们希望通过m个函数$g^{(i)}$和n个函数$h^{(j)}$描述S，那么S可以表示为$S=\{x|任意i,g^{(i)}(x)=0 and 任意j,h^{(j)}(x)≤0\}$,其中$g^{(i)}$等式称为等式约束,$h^{(j)}$的不等式为不等式约束.

为每个约束引入新的变量$\lambda_i$和$α_i$,这些新变量被称为KKT乘子.广义Lagrangian可以定义为:

$L(x,\lambda,α)=f(x)+\sum_i\lambda_ig^{(i)}(x)+\sum_jα_jh^{(j)}(x)$

现在可以通过优化无约束的广义Lagrangian解决约束最小化问题.只要存在至少一个可行点且f(x)不允许取∞,那么

$min_xmax_{\lambda}max_{α,α≥0}L(x,\lambda,α)$

与如下函数有相同的最优目标函数值和最优点集x

$min_{x∈S}f(x)$

这是因为当约束满足时,

$max_{\lambda}max_{α,α≥0}L(x,\lambda,α)=f(x)$

而违反任意约束时,

$max_{\lambda}max_{α,α≥0}L(x,\lambda,α)=∞$

这些性质保证不可行点不会是最佳的,并且可行点范围内的最优点不变.

约束优化问题有一些性质，被称为KKT条件:

广义Lagrangian的梯度为0
所有关于x和KKT乘子的约束都满足
不等式约束显示的”互补松弛性”：$α\odot h(x)=0$

这些是确定一个点是最优点的必要条件,但不一定是充分条件.

机器学习基础

机器学习本质上属于应用统计学，更多地关注于如何用计算机统计地估计复杂函数,不太关注为这些函数提供置信区间，因此会讨论两种统计学的主要方法：频率派估计和贝叶斯推断。

学习算法

所谓的”学习”是什么意思？
对于某类任务T和性能度量P,一个计算机程序被认为可以从经验E中学习是指,通过经验E改进后,它在任务T上由性能度量P衡量的性能有所提升.经验E、任务T和性能度量P的定义范围非常宽广。

任务T

从“任务”的相对正式的定义上来说,学习过程本身不能算是任务.学习是我们所谓的获取完成任务的能力
通常机器学习任务定义为机器学习系统应该如何处理样本。样本是指我们从某些希望机器学习系统处理的对象或事件中收集到的已经量化的特征的集合.
机器学习可以解决很多类型的任务.一些非常常见的机器学习任务列举如下：

分类
输入缺失分类:学习算法只需定义一个从输入向量映射到输出类别的函数.当一些输入可能丢失时,学习算法必须学习一组函数,而不是单个分类函数.每个函数对应着分类具有不同缺失输入子集的x.这种情况在医疗诊断中经常出现,因为很多类别类型的医学测试是昂贵的,对身体有害的.有效地定义这样一个大集合函数的方法是学习所有相关变量的概率分布,然后通过边缘化缺失变量来解决分类任务.使用n个输入变量,我们现在可以获得每个可能的缺失输入集合所需的所有$2^n$个不同的分类函数,但计算机程序仅需要学习一个描述联合概率分布的函数.
回归:在这类任务中,计算机程序需要对给定输入预测数值
转录:在这类任务中,机器学习系统观测一些相对非结构化表示的数据,并转录信息为离散的文本形式.
机器翻译：在这类任务中,输入是一种语言的符号序列,计算机程序必须将其转换成另一种语言的符号序列
结构化输出：结构化输出任务的输出是向量或者其他包含多个值的数据结构,并且构成输出的这些不同元素间具有重要关系.
异常检测:在这类任务中,计算机程序在一组事件或对象中筛选,并标记不正常或非常典型的个体.例如信用卡欺诈检测
合成和采样:在这类任务中,机器学习程序生成一些和训练数据相似的新样本
缺失值填补:在这类任务中,机器学习算法给定一个新样本x∈$R^n$,x中某些元素$x_i$缺失.算法必须填补这些缺失值
去噪:在这类任务中,机器学习算法的输入是:干净样本x∈$R^n$经过未知损坏过程后得到的损失样本$\hat{x}∈R^n$.算法根据损坏后的样本$\hat{x}$预测干净的样本x,或者更一般地预测条件概率分布$p(x|\hat{x})$
密度估计或概率质量函数估计:在密度估计问题中,机器学习算法函数$p_{model}$:$R^n->R$,其中$p_{model}(x)$可以解释成样本采样空间地概率密度函数(如果x是连续的)或者概率质量函数(如果x是离散的).要做好这样的任务(在讨论性能度量P时,我们会明确定义任务是什么),算法需要学习观测到的数据的结构.算法必须知道什么什么情况下样本聚集出现,什么情况下不太可能出现.以上描述的大多数任务都要学习算法至少能隐式地捕获概率分布的结构.密度估计可以让我们显式地捕获该分布。

性能度量P

为了评估机器学习算法地能力,我们必须设计其性能地定量度量.通常性能度量P是特定于系统执行地任务T而言的.
对于诸如分类、缺失输入分类和转录任务,我们通常度量模型的准确率
通常我们会更加关注机器学习算法在未观测数据上的性能如何,因为这将决定其在实际应用中的性能。因此，我们使用测试集数据来评估系统性能,将其与训练机器学习系统的训练集数据分开.

经验E

机器学习算法可以大致分类为无监督算法和监督算法.

无监督学习算法：训练含有很多特征的数据集,然后学习出这个数据集上有用的结构性质.在深度学习中,我们通常要学习生成数据集的整个概率分布,显式地,比如密度估计,或是隐式地,比如合成或去噪.还有一些其他类型地无监督学习任务,例如聚类,将数据集分成相似样本的集合
监督学习算法:训练含有很多特征的数据集,不过数据集中的样本都有一个标签(label)或目标(target)。

有些机器学习算法并不是训练于一个固定的数据集上，例如,强化学习算法会和环境进行交互,所以学习系统和它的训练过程会有反馈回路.

容量、过拟合和欠拟合

机器学习的主要挑战是我们算法必须能够在先前未观察到的新输入上表现良好,而不只是在训练集上表现良好.在先前未观测到的输入上表现良好的能力称为泛化.
通常情况下,训练机器学习模型时,我们可以使用某个训练集,在训练集上计算一些被称为训练误差的度量误差,目标是降低训练误差.机器学习和优化不同的地方在于,我们希望泛化误差(也称为测试误差)很低.泛化误差被定义为新输入的误差期望.

训练集和测试集数据通过数据集上被称为数据生成过程的概率分布生成.通常,会做一系列被统称为独立同分布假设.该假设是说,每个数据集中的样本都是彼此相互独立的,并且训练集和测试集是同分布的,采样自相同的分布.这个假设使我们能够在单个样本的概率分布描述数据生成过程.然后相同的分布可以用来生成每一个训练样本和每一个测试样本.我们将这个共享的潜在分布称为数据生成分布,记作$p_{data}$.这个概率框架和独立同分布假设允许我们从数学上研究训练误差和测试误差之间的关系.

在使用机器学习算法时,我们不会提前固定参数,然后采用得到两个数据集.我们采样得到训练集,然后挑选参数去降低训练集误差,然后采样得到测试集.在这个过程中,测试误差期望会大于或等于训练误差期望。以下是决定机器学习算法效果是否好的因素:
(1)降低训练误差
(2)缩小训练误差和测试误差的距离
这两个因素对应于机器学习的两个主要挑战:欠拟合和过拟合。欠拟合是指模型不能在训练集上获得足够低的误差,而过拟合是指训练误差和测试误差之间的差距太大

通过调整模型的容量(capacity),我们可以控制模型是否偏向于过拟合或欠拟合。通俗来讲,模型的容量是指其拟合各种函数的能力.

模型规定了调整参数降低训练目标时,学习算法可以从某些函数簇中选择函数.这被称为模型的表示容量.实际上,学习算法不会真的找到最优函数,而仅是找到一个可以大大降低训练误差的函数.额外的限制因素,比如优化算法的不完美,意味着学习算法的有效容量可能小于模型簇的表示容量.

奥卡姆剃刀:在同样能够解释已知观测现象的假设中,我们应该挑选”最简单”的那一个
没有免费午餐定理:在所有可能的数据生成分布上平均之后,每一个分类算法在未事先观测的点上都有相同的错误率。换言之,在某种意义上,没有一个机器学习算法总比其他的要好.

正则化

我们建立一组学习算法的偏好来达到这个要求.当这些偏好和我们希望算法解决的学习问题相吻合时,性能会更好.例如,可以加入权重衰减来修改线性回归的训练标准.更一般地,正则化一个学习函数$f(x;\theta)$的模型,我们可以给代价函数添加被称为正则化项的惩罚.

正则化是指修改学习算法,使其降低泛化误差而非训练误差.

超参数和验证集

大多数机器学习算法都有超参数,可以设置来控制算法行为.超参数不是通过学习算法本身学习出来的.我们需要一个训练算法观测不到的验证集样本.测试样本不能以任何形式参与到模型的选择中,包括设定超参数.基于这个原因,测试集中的样本不能用于验证集.因此,我们总是从训练数据中构建验证集.特别地,我们将训练数据分成两个不相交的子集.其中一个用于学习参数。另一个作为验证集,用于估计训练中或训练后的泛化误差,更新超参数.用于学习参数的数据子集通常仍被称为训练集,尽管这会和整个训练过程用到的更大的数据集相混。用于挑选超参数的数据子集被称为验证集.通常，80%训练数据用于训练,20%用于验证.

估计、偏差和方差

统计领域为我们提供了很多工具来实现机器学习目标，不仅可以解决训练集上的任务,还可以泛化.基本的概念,例如参数估计、偏差和方差,对于正式地刻画泛化、欠拟合和过拟合都非常有帮助.

点估计

点估计试图为一些感兴趣的量提供单个”最优”预测.一般地,感兴趣的量可以是单个参数,或是某些参数模型中的一个向量参数.为了区分参数估计和真实值,习惯将参数$\theta$的点估计表示为$\hat{\theta}$

令$\{x^{(1)},….,x^{(m)}\}$是m个独立同分布(i.i.d.)的数据点.点估计或统计量是这些数据的任意函数:

$\hat{\theta}=g(x^{(1)},...,x^{(m)})$

这个定义不要求g返回一个接近真实$\theta$的值,或者g的值域恰好是$\theta$的允许取值范围.点估计的定义非常宽泛,给了估计量的设计者极大的灵活性.虽然几乎所有的函数都可以称为估计量,但是一个良好的估计量的输出会接近生成训练数据的真实参数$\theta$

采取频率派在统计上的观点,假设真实参数$\theta$是固定但未知的,而点估计$\hat{\theta}$是数据的函数.由于数据是随机过程采样出来的,数据的任何函数都是随机地,因此$\hat{\theta}$是一个随机变量

点估计也可以是指输入和目标变量之间关系的估计,我们将这种类型的点估计称为函数估计。函数估计就是从输入向量x预测变量y。假设有一个函数f(x)表示y和x之间的近似关系。例如,可能假设$y=f(x)+\epsilon$,其中$\epsilon$是y中未能从x预测的一部分.在函数估计中,感兴趣的是用模型估计去近似f,或者估计$\hat{f}$.函数估计和估计参数$\theta$是一样的,函数估计$\hat{f}$是函数空间中的一个点估计.

偏差

估计的偏差被定义为

$bias(\hat{\theta}_m)=E(\hat{\theta}_m)-\theta$

其中期望作用在所有数据(看作随机变量采样的到的)上,$\theta$是用于定义数据生成分布的$\theta$的真实值.如果$bias(\theta_m)=0$那么估计量$\hat{\theta}_m$被称为是无偏的,这意味着$E(\hat{\theta}_m)=\theta$.如果$lim_{m—>∞}bias(\hat{\theta}_m)=0$,那么估计量$\hat{\theta}_m$被称为渐进无偏,这意味着$lim_{m->∞}E(\hat{\theta}_m)=\theta$

方差和标准差

有时会考虑估计量的另一个性质是它作为数据样本的函数,期望的变化程度是多少.之前提到可以计算估计量的期望来决定它的偏差,也可以计算它的方差.估计量的方差就是一个方差:

$Var(\hat{\theta})$

其中随机变量是训练集.另外,方差的平方根被称为标准差，记作$SE(\hat{\theta})$

估计量的方差或标准差告诉我们,当独立地从潜在的数据生成过程中重采样数据集时,如何期望估计的变化.正如我们希望估计的偏差小,我们也希望其方差较小.

均值的标准差被记作

$SE(\hat{\mu}_m)=\sqrt{Var[\frac{1}{m}\sum_{i=1}^m x^{(i)}]}=\frac{\sigma}{\sqrt{m}}$

权衡偏差和方差以最小化均方误差

偏差和方差度量着估计量的两个不同误差来源.偏差度量着偏离真是函数或参数的误差期望,而方差度量着数据上任意特定采样可能导致的估计期望的偏差

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

要注意偏差和方差的关系与机器学习容量、欠拟合和过拟合的概念紧密相连.(记住那个U形图)

最大似然估计

我们希望有些准则可以让我们从不同模型中得到特定函数作为好的估计,而不是猜测某些函数可能是好的估计,然后分析其偏差和方差。最常用的准则是最大似然估计.
令$p_{model}(x;\theta)$是一族由$\theta$确定在相同空间上的概率分布.换言之,$p_{model}(x;\theta)$将任意输入x映射到实数来估计真实概率$p_{data}(x)$
对$\theta$的最大似然估计被定义为:

$\theta_{ML}=argmax_{\theta}p_{model}(X;\theta)=argmax_{\theta}\prod_{i=1}^mp_{model}(x^{(i)};\theta)$

多个概率的乘积会因很多原因不便于计算，常常会对其进行log处理

一种解释最大似然估计的观点是将它看作最小化训练集上的经验分布$\hat{p}_{data}$和模型分布之间的差异,两者之间的差异程度可以通过KL散度度量。KL散度被定义为:

$D_{KL}(\hat{p}_{data}||p_{model})=E_{x～\hat{p}_{data}}[log\hat{p}_{data}(x)-logp_{model}(x)]$

左边一项仅涉及数据生成过程,和模型无关.这意味着当训练模型最小化KL散度时,我们只需要最小化

$-E_{x～\hat{p}_{data}}[logp_{model}(x)]$

显然这和最大似然的式子相同.
最小化KL散度其实就是在最小化分布之间的交叉熵.

最大似然的性质：
在合适的条件下,最大似然估计具有一致性,意味着训练样本数目趋向于无穷大时,参数的最大似然估计会收敛到参数的真实值.
那么什么是合适的条件?
(1)真实分布$p_{model}$必须在模型族$p_{model}(·;\theta)$中.否则,没有估计可以还原$p_{data}$.
(2)真实分布$p_{data}$必须刚好对应一个$\theta$值.否则,最大似然估计恢复出真实分布$p_{data}$后,也不能决定数据生成过程使用那个$\theta$

贝叶斯统计

之前讨论的都是频率派估计方法和基于估计单一值$\theta$的方法,然后基于该估计作所有的预测.下面要讲的是贝叶斯统计,即在做预测时会考虑所有可能的$\theta$.
贝叶斯统计的视角完全不同.贝叶斯统计用概率反映知识状态的确定性程序.数据集能够被直接观测到,因此不是随机的.另一方面,真实参数$\theta$是未知或不确定的,因此可以表示成随机变量.

在观测到数据前,将$\theta$的已知知识表示成先验概率分布,$p(\theta)$(有时称为先验).一般而言,机器学习实践者会选择一个相当宽泛的先验分布(高熵的),以反映在观测到任何数据前参数$\theta$的高度不确定性.
现在假设我们有一组数据样本${x^{(1)},…,x^{(m)}}$,通过贝叶斯规则结合数据似然$p(x^{(1)},…,x^{(m)}|\theta)$和先验,可以恢复数据对我们关于$\theta$信念的影响

$p(\theta|x^{(1)},....,x^{(m)})=\frac{p(x^{(1)},...,x^{(m)}|\theta)p(\theta)}{p(x^{(1)},...,x^{(m)})}$

在贝叶斯估计常用的情景下,先验开始是相对均匀的分布或高熵的高斯分布，观测数据通常会使后验的熵降下来,并集中在参数的几个可能性很高的值.

相对于最大似然估计,贝叶斯估计有两个重要区别:(1)不像最大似然方法预测时使用$\theta$的点估计,贝叶斯方法使用$\theta$的全分布。(2)贝叶斯估计中的先验能够影响概率质量密度朝参数空间中偏好先验的区域偏移.对贝叶斯方法的批判认为,先验是认为主观判断影响预测的来源.

最大后验(MAP)估计

原则上,我们应该使用参数$\theta$的完整贝叶斯后验分布进行预测,但单点估计常常也是需要的.希望使用点估计的一个常见原因是,对于大多数有意义的模型而言,大多数涉及贝叶斯后验的计算是非常棘手的,点估计提供了一个可行的近似解.仍然可以先验影响点估计的选择来利用贝叶斯方法的优点,而不是简单地回到最大似然估计。一种能够做到这一点的合理方式是选择最大后验点估计.

正如全贝叶斯推断,MAP贝叶斯推断的优势是能够利用来自先验的信息.这些信息无法从训练数据中获得。该附加信息有助于减少最大后验点估计的方差(相当于ML估计)。然而,这个优点的代价是增加了偏差。
许多正规化估计方法，例如权重衰减正则化的最大似然学习,可以被解释为贝叶斯推断的MAP近似.并非所有正则化惩罚都对应着MAP贝叶斯推断.