花书笔记：第 05 章 机器学习基础
5.1 机器学习算法
机器学习算法定义：对于某类任务 TTT ，和性能度量 PPP ，一个计算机程序被认为可以从经验 EEE 中学习是指，通过经验 EEE 改进后，它在任务 TTT 由性能度量 PPP 衡量的性能有所提升。
5.1.1 任务TTT
机器学习的任务通常是一些人为设计和使用确定性程序很难解决的问题。通常有以下几类任务。
分类
学习算法返回一个函数 f：Rn→{1,⋅⋅⋅,k}\pmb{f：\mathbb{R}^n→ \{1,···,k\}}f：Rn→{1,⋅⋅⋅,k}f：Rn→{1,⋅⋅⋅,k}f：Rn→{1,⋅⋅⋅,k}。将向量 xxx 所代表的输入(待分类数据)，函数将会输出该数据相应的类别码 kkk；或该类别输入各个类别的概率分布。
输入缺失分类
即输入向量 xxx 会存在某些属性的数据缺失的情况，但必须对其进行分类(如医疗诊断)。
回归
通过学习数据的规律，算法根据给定的输入预测输出值，如未来股票、证券、房价的预测。
转录
将一些非结构化的表示数据，转化为离散的文本形式，如语音识别，OCR字符识别。
机器翻译
输入是一种语言类的符号序列，计算机程序必须将其转化为另一种语言的符号序列，如将英文译为中文。
结构化输出
结构化输出任务的输出是向量或者其他包含多个值的数据结构，且输出值中的各个部分具有一定的联系。如图像理解，即计算机程序中输入一幅图像，程序给出对这幅图像的描述。
异常检测
计算机程序在一组事件或对象中筛选，并标记不正常或非典型的个体。如工业零件的残品检测，找出与正常零件有差异的对象。
合成与采样
机器学习程序生成一些和训练数据相似的新样本。如语音合成，根据句子输出这个句子的音频波形，且每个输入并非只有一个正确的输出，即每次输出音频波形可能不同，但都包含句子信息。
缺失值填补
根据一些历史数据学习到的知识，对新样本 x∈Rnx \in \mathbb{R}^nx∈Rn 中的某些缺失值进行填补。
去噪
机器学习程序根据受到干扰的样本，预测初始的干净样本。
密度估计或概率质量函数估计
机器学习算法 pmodel(x)p_{model}(x)pmodel(x) 根据观测到的数据结构，隐式地捕捉概率分布的结构。可以应用于根据概率分布解决缺失值填补任务。
5.1.2 性能度量 P
设计性能度量是为了评估机器学习算法执行任务T\pmb TTTT 的能力。
准确率和错误率
准确率是指模型输出正确结果的样本数占总体样本数的比率。错误率与其含义相反。常用于分类、确实输入分类、转录任务的性能评估。
测试集
我们训练机器学习模型通常是希望得到其良好的泛化性能，即模型在没有见过的数据中仍然保持良好的性能。所以我们经常会使用模型在学习过程中没有见过的数据作为测试集来衡量模型的泛化性能。
5.1.3 经验 E
有监督学习
数据集包含输入x以及输出y，有监督学习算法的目标是学习x与y之间的关联，以达到能够从 x 预测 y 的目的。
无监督学习
无监督学习的数据集中只有包含输入x，主要目的是自主的学习数据集中有用的结构性质。
5.1.4 示例：线性回归(linear regression)
线性回归的目标
根据数据集，找到一个线性函数，使得该函数根据 x\pmb xxxx 预测出的 y^\pmb{\hat{y}}y^y^y^ 与实际值 y\pmb yyyy 的整体误差最小。
目标函数为：
y^=wTx\hat y=w^Tx y^=wTx
其最终目的是找到最优的参数 www。
定义误差函数
即定义性能度量 P。线性回归用均方误差（MSE）作为误差函数，并对其进行优化，使 MSE 能够达到最小，从而找到最优参数 www。
MSEtrain=1m∣∣y^(train)−y(train)∣∣22MSE_{train}=\frac{1}{m}||\hat y^{(train)}-y^{(train)}||_2^2 MSEtrain=m1∣∣y^(train)−y(train)∣∣22
求导
求 ▽wMSEtrain=0\triangledown_w MSE_{train}=0▽wMSEtrain=0 可以得到最优 www。
其结果为
w=(X(train)TX(train))−1X(train)Ty(train)w=(X^{(train)T}X^{(train)})^{-1}X^{(train)T}y^{(train)} w=(X(train)TX(train))−1X(train)Ty(train)
根据上式就可得到最优 www。
如何处理存在偏置的情况
大多数的线性回归的形式为：
y^=wTx+b\hat y=w^Tx + b y^=wTx+b
为了方便求解长将数据集 xxx矩阵中加入一列 1。在权重矩阵 www中再加入一列表示 b\pmb bbbb。以此来进行线性回归。
Y^=WTX\hat Y=W^TX Y^=WTX
其中，
W=(w,b);X=(x,1)W=(w,b);\quad X=(x,1) W=(w,b);X=(x,1)
5.2 容量、过拟合和欠拟合
容量：指拟合各种函数的能力。容量低的模型容易造成欠拟合，容量高的模型容易造成过拟合。可以理解为模型的复杂程度
欠拟合：指模型在训练集中不能达到足够低的误差，即模型在训练集上性能较差。
过拟合：训练误差与测试误差差距太大。即在训练集性能很好，测试集性能很差，这样可以理解为训练过了，模型记住了训练样本，只能预测训练集中的数据。
奥卡姆剃刀：即在选择模型时，在模型性能差异不太大的情况下，我们通常选择最简单的那个。
5.2.1 没有免费午餐定理
该定理表明，没有哪个机器学习算法总是比其他算法更好。在所有可能的数据分布中，他们具有相同的错误率。只能说在某些数据分布中哪个算法更适合。
5.2.2 正则化
指在代价函数(loss)中增加一个正则化项，改变权重偏好，从而达到防止过拟合，降低泛化误差的目的。
权重衰减
以线性回归为例，在线性回归的损失函数中加入惩罚项 λwTw\pmb{\lambda w^Tw}λwTwλwTwλwTw。组成新的代价函数。
J(w)=MSEtrain+λwTwJ(w)=MSE_{train}+\lambda w^Tw J(w)=MSEtrain+λwTw
其中 λ\lambdaλ 为选择的常数。
从上式中可以看出 wTww^TwwTw 越大，惩罚项 λwTw\lambda w^TwλwTw 增加程度越大，惩罚程度越大；wTww^TwwTw 很小的时候， λwTw\lambda w^TwλwTw 也很小，惩罚项几乎不起作用，所以惩罚项偏好于平方 L2L^2L2 范数较小的权重。惩罚项的具体作用见下图。
5.3 超参数和验证集
超参数：模型的超参数是人为设定的，不是由算法学习得到的，它用来控制算法的行为。例如多项式回归，多项式的次数。验证集：训练集主要用于算法学习；测试集用于衡量算法的泛化能力；验证集用于挑选最优超参数。数据集通常划分比例：万级以下(6 : 2 : 2)；万级以上(98 : 1 : 1)。5.3.1 交差验证
当数据集比较小时，划分的测试集就不能准确的估计泛化误差，k-折交叉验证是一种处理这种问题的方法。其主要思想是，将数据集等分为k份，将算法训练k次，每次选取不同份的数据作为测试集，其他作为训练集，最终返回k个测试误差来获取算法误差的平均估计。
5.4 估计、偏差和方差
5.4.1 点估计
点估计是对模型的单个参数或某些参数模型的一个向量参数提供最优预测。如线性回归中的 www 。参数的真实值用 θ\thetaθ 表示 (生成数据集的真实分布)；点估计用 θ^\hat\thetaθ^ 表示 (根据数据集进行分布的近似估计)。良好的估计量会接近真实的参数 θ\thetaθ。5.4.2 偏差
估计的偏差定义
bias(θ^m)=E(θ^)−θbias(\hat\theta_m)=\mathbb{E}(\hat\theta)-\theta bias(θ^m)=E(θ^)−θ
E(θ^)\mathbb{E}(\hat\theta)E(θ^) 表示所有数据集的期望；θ\thetaθ 表示参数的真实值。若 bias(θ^m)=0bias(\hat\theta_m)=0bias(θ^m)=0 则 θ^m\hat\theta_mθ^m 为无偏估计。若 limm→∞bias(θ^m)=0\lim_{m \rightarrow \infty}bias(\hat\theta_m)=0limm→∞bias(θ^m)=0 则 θ^m\hat\theta_mθ^m 为渐进无偏估计。
5.4.3 方差和标准差
估计量方差 Var(θ^)Var(\hat \theta)Var(θ^)；真实值方差 σ2\sigma^2σ2；估计量标准差 SE(θ^)SE(\hat \theta)SE(θ^)； 真实值标准差 σ\sigmaσ 。
均值标准差
SE(μ^m)=Var[1m∑i=1mx(i)]=σmSE(\hat \mu_m)=\sqrt{Var [\frac{1}{m} \sum_{i=1}^m x^{(i)}]}=\frac{\sigma}{\sqrt m} SE(μ^m)=Var[m1i=1∑mx(i)]=mσ
算法 A 比 算法 B 好，指 A 的误差的 95% 置信区间的上界小于 B 的误差的 95% 置信区间的下界。
95%置信区间：(μ^m−1.96E(μ^),μ^m+1.96E(μ^))95\% 置信区间：( \hat \mu _m-1.96 E(\hat \mu), \hat \mu _m+1.96 E(\hat \mu) ) 95%置信区间：(μ^m−1.96E(μ^),μ^m+1.96E(μ^))
5.4.4 权衡偏差和方差以最小化均方误差
根据偏差和方差综合衡量模型泛化误差时可以选择交叉验证或均方误差(MSE)。
均方误差
MSE=E[(θ^m−θ)2]=Bias(θ^m)2+Var(θ^m)MSE=\mathbb{E}[(\hat \theta_m- \theta )^2]=Bias(\hat \theta _m)^2 + Var(\hat\theta_m) MSE=E[(θ^m−θ)2]=Bias(θ^m)2+Var(θ^m)
使用 MSE 衡量泛化误差，增加容量会增加方差，降低偏差。
5.4.5 一致性
一致性准则
plimm→∞θ^m=θplim_{m\rightarrow\infty}\hat \theta_m=\theta plimm→∞θ^m=θ
即数据集无穷大时，θ^\hat\thetaθ^ 会收敛到 θ\thetaθ。
一致性保证了估计量的偏差会随数据样本数目的增多而减少。
5.5 最大似然估计
最大似然估计，是通过概率角度优化求解模型参数 θ^\hat\thetaθ^ 的方法
最大似然求解
1) 最大似然定义
由上式可以看出，我们期望能够找到最大似然θML\pmb{\theta_{ML}}θMLθMLθML ，使得模型接近真实值的概率最大，即 pmodel(X;θ)p_{model}(\mathbb{X};\theta)pmodel(X;θ) 最大。
由于 式 5.57 乘积形式，不容易求导，且容易造成下溢。所以进行取对数操作变成求和形式，不影响 θML\theta_{ML}θML ，见式 5.58 。
KL 散度
对 式5.58除以 m，可得到训练数据 p^data\hat p_{data}p^data 的期望分布。
式 5.60 代表KL散度，这就是模型训练优化的目标(loss)，最小化KL 散度只需要最小化 式5.61即可。
最小化 KL 散度就是在最小化分布之间的交叉熵。
5.5.1 条件对数似然和均方误差
5.5.2 最大似然的性质
最大似然估计具有一致性，但真实分布 pdatap_{data}pdata 需要满足以下几个条件：
1）pdatap_{data}pdata 需要在模型族 pmodel(⋅;θ)p_{model}(·;\theta)pmodel(⋅;θ) 中，否则，没有估计可以还原 pdatap_{data}pdata 。
2）pdatap_{data}pdata 必须刚好对应一个θ\thetaθ 值，否则，估计恢复出真实分布后不知道使用哪一个 θ\thetaθ 。
5.6 贝叶斯统计
当训练数据有限时，贝叶斯方法通常泛化的更好。但是当训练样本数目很大时，通常由很大的计算代价。5.7 监督学习算法
监督学习算法是根据包含 xxx 和 yyy 的数据集，学习如何关联输入和输出。5.7.1 概率监督学习
大部分的监督学习算法都是基于估计概率分布 p(y∣x)p(y|\pmb x)p(y∣xxx) 的.将线性回归和sigmoid 函数组合可构成逻辑回归(logistic regression) 用于分类问题。5.7.2 支持向量机(SVM)
支持向量机也是基于线性函数 wTx+b\pmb{w^Tx}+bwTxwTxwTx+b 的，与逻辑回归不同，支持向量机只输出类别，不输出概率。
主要思想
1)支持向量中的线性函数可重写为：
x(i)\pmb{x^{(i)}}x(i)x(i)x(i) 表示训练样本，α\pmb\alphaααα 是系数向量，αi\alpha_iαi 为常数，x\pmb xxxx 表示输入项，m 表示训练数据数量。
2)引入特征函数ϕ(x)\phi(\pmb x)ϕ(xxx)，对数据进行高维映射
f(x)=b+∑iαiϕ(x)⋅ϕ(x(i))f(\pmb x)=b+\sum_i \alpha_i \phi(\pmb x)·\phi(\pmb{x^{(i)}}) f(xxx)=b+i∑αiϕ(xxx)⋅ϕ(x(i)x(i)x(i))
3)核函数 k(x,x(i))k(\pmb x,\pmb x^{(i)})k(xxx,xxx(i))等价代换特征函数
f(x)=b+∑iαik(x,x(i))f(\pmb x)=b+\sum_i \alpha_i k(\pmb x,\pmb x^{(i)}) f(xxx)=b+i∑αik(xxx,xxx(i))
由于 ϕ(x)\phi(\pmb x)ϕ(xxx) 可以是无限维，很多时候计算是复杂的。而核函数完全等价于用 ϕ(x)⋅ϕ(x(i))\phi(\pmb x)·\phi(\pmb{x^{(i)}})ϕ(xxx)⋅ϕ(x(i)x(i)x(i)) 处理的所有输入，简化了计算代价。例如最小核：
ϕ(x)\phi(\pmb x)ϕ(xxx) 的返回结果是一个由 xxx 个 1 开头，之后是无限个 0 的向量。
最小核 k(x,x(i))=min(x,x(i))k(\pmb x,\pmb x^{(i)})=min(x,x^{(i)})k(xxx,xxx(i))=min(x,x(i)) 。
若 x=2x = 2x=2；x(i)=1x^{(i)}=1x(i)=1，则 ϕ(2)⋅ϕ(1)=k(2,1)=1\phi(2)·\phi(1)=k(2, 1)=1ϕ(2)⋅ϕ(1)=k(2,1)=1。
支持向量机之后会在新的转换空间学习线性模型。
其他性质
支持向量机中每个训练样本贡献一个 αik(x,x(i))\alpha_i k(\pmb x,\pmb x^{(i)})αik(xxx,xxx(i)) 项，因此决策函数 f(x)f(x)f(x)计算成本是线性的，支持向量机通过学习主要包含 0 的向量α\pmb \alphaααα 来，缓和这一缺点。这样只需要计算几个非零αi\alpha_iαi 项就可以决策。非零αi\alpha_iαi 对应得样本点则称为支持向量。
5.7.3 其他简单的监督学习算法
k-最近邻决策树5.8 无监督学习算法
无监督学习相关任务
1.学习从分布中采样
2.学习从分布中去噪
3.寻找数据分布的流形
4.将数据中相关的样本聚类
寻找数据最佳表示——无监督学习经典任务
1.低维表示
低维表示尝试将数据集 x\pmb xxxx 尽可能的压缩到一个较小的表示中。产生的表示具有更少的元素间依赖关系
2.稀疏表示
将数据集嵌入到输入项大多数为 0 的表示中，通常用于需要增加表示维数的情况。
3.独立表示
独立表示试图分开数据分布中的变化来源，使得表示的维度是统计独立的。
5.8.1 主成分分析
在花书笔记：第2章线性代数 2.8节中的 PCA 是通过求解 XTXX^TXXTX 的特征向量来确定线性变换W\pmb WWWW 的；本节将会讲述使用奇异值分解(SVD)求解变换的方法。
SVD 求解 PCA
1.设 X→Z 的变换
Z=WTXZ=\pmb{W^T}X Z=WTWTWTX
2.奇异值求解
XTX=(UΣWT)T(UΣWT)X^TX=(U \Sigma W^T)^T (U \Sigma W^T) XTX=(UΣWT)T(UΣWT)
W\pmb WWWW 即为所求变换。
性质
PCA将数据变换为元素之间彼此不相关的表示，消除了数据中未知变化因素。
5.8.2 k-均值聚类
5.9 随机梯度下降(SGD)
对于一般梯度下降求解梯度时需要计算所有数据样本的梯度，当样本数量 m 过大时，计算代价太高。随机梯度下降的核心是，梯度是期望。期望可使用小规模的样本近似估计。即，算法每一步在数据集中抽取一个小批量(batch)。批量数 m′m'm′ 相对较小，从一到几百。此时梯度的估计可表示为：
梯度下降
θ←θ−ϵg\pmb\theta \leftarrow \pmb\theta - \epsilon \pmb g θθθ←θθθ−ϵggg
ϵ\epsilonϵ 为学习率。
5.10 构建机器学习算法
深度学习算法的配方1.特定的数据集
2.代价函数 + 正则化(选)
3.优化过程
4.特定的模型(算法)
5.11 促使深度学习发展的挑战
许多机器学习在很多不同问题上表现良好，但在人工智能问题上泛化能力不足，如语音识别，目标识别。传统机器学习中实现泛化的机制不适合学习高维空间中的复杂函数。5.11.1 维数灾难
维数灾难是指，当数据维数很高时，许多机器学习问题将会变得非常困难。5.11.2 局部不变性核平滑正则化
平滑先验或局部不变性先验
这个先验表明要学习的函数(模型)不应在小区域内发生很大变化。例如梯度下降中 loss 曲线是缓慢递减的。
深度学习的核心思想是，假设数据由因素或特征组合产生，这些因素或特征可能来自一个层次结构的多个层级。这种深度的分布式表示有效的解决了维数灾难，以及平滑先验不足应对复杂任务的问题。
5.11.3 流形学习
流形指连接在一起的区域，是指一组点。且这些点每个点都有其邻域。
允许流形的维数从一个点到另一个点有所变化，这经常发生于自身相交的情况，例如数字8形状的流形的中心相交处有两维，其他为一维。
流形学习
背景
让机器学习算法去学习整个 Rn\mathbb {R}^nRn 上有趣变化的函数是不可能的。但流形学习可以解决这一问题。
解决策略
流形学习假设 Rn\mathbb {R}^nRn 中大部分区域都是无效的输入。有意义的输入只存在于少量数据点的子集构成的一组流形中。流形学习认为有意义的变化都沿着流形方向或仅发生在我们切换到另一流形时。
支持流形假设的两个观点
1.现实生活中的图像、文本、声音的概率分布都是高度集中的。如图像中的某一对象是集中在图像的某一区域的。
2.我们至少能够非正式的想象这些邻域和变换。
