Author: Pan

Date: 2020/7/13

1.机器学习的定义与其中牵扯到的问题

统计机器学习究竟是什么，根据《统计学习方法》 $^{[1]}$ 定义：统计机器学习是计算机基于数据建立概率统计模型，并用该模型对数据进行分析和预测的学科。

其中有几个耐人寻味的问题：

1. 怎么建立这样的模型？

2. 为什么这样的模型能进行分析和预测呢？

3. 有了模型，怎么实现这种分析和预测呢？

好了，现在我们有了定义，就像我们登上了山顶，而机器学习的个中内容就像你远眺时，眼里所见的城市建筑，而这些问题，就像道路，你虽不了解建筑内部，却知道有道路可以通向他。重要的不是定义，而是我们从中发现的道路。

而道路千万条，从机器学习的流程上看，机器学习的组件大多只有这几类，许多人有不同的定义组件的方式。例如，《统计学习方法》中，这些组件是：1.模型 2. 策略 3.算法。而在其他地方我还看到这样的：1.Matrix 2.Optimation 3.Algothrim 4.Statistics。诸如此类，本文以前者为模板来进行说明并非意味着后者没有可取之处，而是前者相对于后者更加清晰地回答了前面三个问题。而且事实上，这些说的都是一件事。

1.1 模型（Model）

模型是什么？这是一个问题，且是通往下一个细节的“道路”，我们下山探一探究竟。

在监督学习中，模型实际上是输入空间或者特征空间到输出空间的映射，它以参数空间的形式存在于假设空间。

小朋友你是否有很多问号？？？？？？？？？

那么问题来了

1. 这四个空间都是什么东西？

2. 输入空间和输出空间之间为什么有个或的关系，他们有啥区别

3. 我们为什么需要这些空间？

对于问题一，我们解释如下

首先，输入空间实际上就是我们数据的一个抽象，它不是你具体抽出的哪个样本，而是泛指全体可能作为输入的数据。比如你想预测下明天下不下雨，经过调查你觉得温度，湿度，大气层云层厚度，地表温度都是不错的指标，那么这个输入空间泛指所有可能的这四个指标的所有取值，他们以向量的形式存在于输入空间中。输入空间中的某个样本集T可按如下表达：

$T=\left\{ \vec{x_{1}},\vec{x_{2}},...,\vec{x_{N}}\right\};\vec{x_{i}}=(x^{(1)},x^{(2)},...x^{(p)})$

该T中有N个数据，p个指标特征，T是个N*p的矩阵。

那么什么是特征空间呢，就比如上面那个例子，温度和地表温度可能都能表达清楚这个模型需要的参数，他们相关性很强，且在这个问题上有近乎一样的权重，那么，真实所需要的特征可能就三个，因此特征空间是输入空间作用在特征维度上的映射结果。

那么你会问特征多了不好吗？我不想奥卡姆剃刀张嘴就来，那么我们来举个例子吧，我被妈妈告知去买酱油，她最为精确告诉我的方式是告诉我酱油的牌子，再具体一点盖子的颜色。假设她极其细致的描述了盖子的各种细节，颜色，拉环的形状，瓶盖凸起部分的弧度，然后告诉你酱油的牌子，为了满足妈妈说的所有要求，你是不是要耗费比前者多得多的精力去找这瓶满足了所有条件的酱油？（你会说你怎么可能这么傻，相信我，计算机就是这个水平的智商），最可怕的是，你会认为所有的酱油都长这样都得这么找（泛化能力差，后面会提到），于是当这个牌子出了一款新酱油，你居然认为它不是酱油,Awkward,right? 举个这样的例子是说明特征空间是对问题的特征指标本身更为有效的描述，事实上，模型都是定义在特征空间上的。这里回答了问题二。

而输出空间是你想得到的答案的集合，比如买酱油，1是买对了，0是买错了，那么这里的1和0就是输出空间里的一个具体值。输出空间可以按如下表示：

$Y=\left\{ y_{1},y_{2},...,y_{N} \right\}$

假如y_i是连续型变量，那么对应于回归问题，如果y是离散型变量，对应于分类问题，如果y_i是一个序列或者向量，那么对应于标注问题。

假设空间是从特征空间到输出空间的映射的集合，也就是说，假设空间包含了所有基于数据来预测的方式，可以是条件概率函数集 $F=\left\{ P|P_{\theta }(Y|X) ;\theta \in R^{n} \right\}$ 也可以是决策函数集 $F=\left\{ f|f_{\theta}(x);\theta \in R^{n} \right\}$ 。

对于问题三，这些空间的定义是服务于我们的模型选择和评估的，这关乎于策略。

1.2 策略(Strategy)

策略解决的是我们的机器要以怎么样的准则进行学习，在探讨这个问题之前，我们必须知道的是：有了假设空间，我们怎么知道哪个模型是我们想要的？我怎么知道我当前的模型有多接近这个我们都想要的模型？

好，首先来解决这个问题，什么样的模型是我们想要的模型。在这里，我们不得不先量化“我们想要的”这个定语，我们得明白计算机学习的是什么，计算机学习的是参数，假设空间实际就是所有参数存在的空间，其中可以有多如繁星的参数向量，我们想要什么模型，其实就是我们想要什么样的参数向量，那具体要什么样的参数向量呢？这显而易见：

1.参数向量的维数和潜在的真实参数向量维数接近。

2.参数向量的每个元素值与潜在的真实参数向量值接近。

那么，有了这样一个目标还不够，我们需要一把尺子去丈量这个“接近”。

怎么样才算接近？于是我们必须有个度量标准：风险

我们知道这个世界上永远找不到一把精确到无可挑剔的尺子，总是有误差存在的。但是我们期望的尺子长什么样我们心里都有数---丈量一切距离，微如原子，大若星辰，只要是距离我都能测。所以这个接近程度的测量也是有个理想状态的--期望风险(expected loss)。在谈到这个时，不得不提的是我们得定义一次测量的误差--损失函数 $L(Y,f(X))$ 。损失函数有很多，例如平方损失，0-1损失，绝对损失和对数损失等等,因此此处仅采用上述L记号。

所以，期望风险可以表达为损失函数的期望：

$R_{exp}(f)=E(L(Y,f_{}(X)))=\int_{X\times Y}^{}L(Y,f_{}(X))P(X,Y)dXdY$

而我们的希望的目标是找到使得期望损失最小的模型f：

$f=arg \space min_{[f]} \space (R_{exp}(f))$

但遗憾的是如此完美的尺子并不存在，为什么呢？因为我们穷尽一切想要得到的是 $P(Y|X)$ ,更显式的： $R_{exp}(P(Y|X))=E(L(Y,arg \space max_{[Y]}(P(Y|X))))=\int_{X\times Y}^{}L(Y,arg \space max_{[Y]}(P(Y|X)))P(Y|X)P(X)dXdY$

如果我们都知道了 $P(Y|X)$ ,最小化期望风险来找模型f的意义何在？这是个悖论。

你会说我说了半天等于没说，我不得不说，从实践的意义上你说的很对，这令人沮丧，但它具有指导意义。因为统计学，因为大数定律，我们可以找到相应的样本无偏估计量去接近这个期望损失。但在此之前我们得先从输入空间中随机实例化出(随机抽出)样本数量为N的样本：

$T=\left\{ \vec{x_{1}},\vec{x_{2}},...,\vec{x_{N}}\right\};\vec{x_{i}}=(x^{(1)},x^{(2)},...x^{(p)})$

于是，我们得出了经验风险(empirical loss)：

$R_{emp}(f)=\frac{1}{N}\cdot \sum_{i=1}^{N}L(y_{i},f(x_{i}))$

虽然我们找到了实践意义上的可行性，但这远远不够，因为很明显看出一些问题：

1. 现实中的小样本是否也可以采用这样的方法？如果不能是否意味着我们局限了它的使用范围？

2. 经验风险最小化是否真的是前文我们说到的“接近”潜在真实模型的唯一标准？

但无论如何，我们找到了“接近真相”的办法。阵对上述两个疑问，我们将以线性模型为例，在例子中多角度来看这个问题。

e.g.线性模型

首先，定义一个线性模型： $Y=X\cdot\vec{a};$ 其中，X是一个N*p的矩阵，而 $\vec{a}$ 是一个p*1的向量。

我们定义其经验风险如下：

$R_{emp}=\frac{1}{2}\cdot\sum_{i=1}^{N}(y_{i}-\vec{x}^{T}_{i}\cdot\vec{a})^{2}=\frac{1}{2}\cdot(Y-X\cdot\vec{a})^{T}(Y-X\cdot\vec{a})=\frac{1}{2}\cdot\vert\vert Y-X\cdot\vec{a} \vert\vert^{2}_{2}$

因为我们的目标是最小化经验损失，所以将这个优化问题表述如下：

$min_{[f]} \space R_{emp}$

具体化一下,另偏导数等于0，以求得经验风险最小化后的参数 $\vec{a}$ 的取值：

$\frac{\delta{R_{emp}}}{\delta{\vec a}}=-X^{T}\cdot(Y-X\cdot\vec{a})=0$

所以可以得出：

$X^{T}X\cdot\vec{a}=X^{T}Y$

有趣的事情来了，参数 $\vec{a}$ 能否求出，取决于 $X^{T}X$ 是否可逆，那么怎么算可逆呢？

我们知道 $X^{T}X$ 是实对称方阵，是半正定矩阵。因此要使得 $X^{T}X$ 可逆的条件是 $X$ 的列向量线性无关，即特征之间线性无关。这里的证明可参考这里：

要使得参数 $\vec{a}$ 可求，我们有两个选择：

1. 提前对X做降维，弱化特征之间的线性相关性。

2. 加入正则化项。

此时你一定一脸懵逼，怎么就加正则化项了？在哪加？我们先将这个看上去很厉害的名词放一下，

考虑一个问题：前面我们有说到 $X^{T}X$ 是半正定的矩阵，如果能让其成为正定矩阵，可逆这个事情是不是就解决了呢？

所谓半正定矩阵，其实是对任意向量 $\vec{C}$ ，有 $\vec{C}^{T}X^{T}X\vec{C}\geq 0$ ,为了使得其只大于零而不等于零，

我们可以另其加上一个未知常数倍的对角矩阵。

设 $\lambda >0$ ；则 $\vec{C}^{T}{(X^{T}X+\lambda \cdot diag(k_{1},k_{2},...,k_{p})_{p\times p})}\vec{C}>0;k_{1},k_{2},...,k_{p}>0$

但我们怎么能凭空多出个这样的项呢？答案是使用结构风险来替代经验风险。

结构风险给出如下：

$R_{cons}=R_{emp}+\lambda\cdot J(f)$

其中 $J(f)$ 是定义在假设空间上的泛函，和模型复杂度有关，模型越复杂， $J(f)$ 越大。

所以，结构风险最小化不仅使得经验风险最小化，还惩罚了模型复杂度。这也回答了问题2：经验风险最小化是否真的是前文我们说到的“接近”潜在真实模型的唯一标准？模型复杂度也是我们不得不考虑的一个指标，模型越是复杂，就越可能拟合噪声，如Fig1所示:

Fig.1 欠拟合(左)，正常(中)，过拟合(右)

当样本数量不足时，欠拟合可能会发生，但是这可用交叉验证来解决。

过拟合的解决方案可以是正则化，也可以是降维。过拟合一旦发生，模型在测试集的表现就会异常，测试集的准确率曲线将先增大后减小。过拟合其实本质上是模型过分追求在训练集上的准确率，导致模型泛化能力(后面会涉及)下降的一种异常。

接下来我们将更为细致的来看正则化的问题：

1.当 $J(f)=\vert \vert \vec{a} \vert \vert^{2}_{2}$ 时，此时正则化项为二范数，称为Ridge Regression, 即正则化项为 $\lambda\cdot \vec{a}^{T}\cdot\vec{a}$ 时：

$R_{cons}=\frac{1}{2}\cdot\sum_{i=1}^{N}(y_{i}-\vec{x}^{T}_{i}\cdot\vec{a})^{2}+\lambda\cdot \vec{a}^{T}\cdot\vec{a}=\frac{1}{2}\cdot(Y-X\cdot\vec{a})^{T}(Y-X\cdot\vec{a})+\lambda\cdot \vec{a}^{T}\cdot\vec{a}$

$\frac{\delta{R_{cons}}}{\delta{\vec a}}=-X^{T}\cdot(Y-X\cdot\vec{a})+\lambda\cdot\vec{a}=0$

$(X^{T}X+\lambda\cdot I_{p})\cdot\vec{a}=X^{T}Y$

由于单位矩阵 $I_{p}$ 为正定矩阵, $\lambda >0$ ,所以 $(X^{T}X+\lambda\cdot I_{p})$ 也为正定矩阵，正定矩阵可逆，所以：

$\vec{a}=(X^{T}X+\lambda\cdot I_{p})^{-1}\cdot X^{T}Y$

由此我们便求得了我们想要的参数向量 $\vec{a}$ ，当然我们会有疑问， $\lambda$ 是怎么来的。

其实它的值是根据验证集筛选出，在验证集中使得损失函数最小的那个 $\lambda$ 作为我们的参数。

2.当 $J(f)=\sum\vert \vert \vec{a} \vert \vert_{1}$ 时，此时正则化项为一范数，称为Lasso Regression, 由于一范数连续不可导，该正则化方式将导致稀疏，一定程度上相当于降维，几何解释上看，Lasso 在参数空间里是个对角线在坐标轴上的超方形，且最优值在顶点取到，Ridge 是个以原点为中心的超球体，最优值在边沿取到。如图Fig.2,图片摘自知乎从Lasso开始说起[2]

Fig.2 L1正则化与L2正则化在参数空间里的表现[2]

继续线性模型的例子，前面的损失函数都是回归损失，也就是输出空间中y是连续值时的损失。

那么假如现在我们要做的是个二分类问题呢？实际上，回归损失依旧可以用，只是不太好用，因为你不得不设置一个阈值来截断类别的连续值来进行类别的区分，但是这个阈值你要取多少合适呢？这貌似是个不好解决的问题。那为什么不直接输出概率来进行选择呢？这样可能使得二分类的做法拓展到多分类也适用。

概率(⊙o⊙)？

不知道为什么，突然觉得脑海里，雅各布 $\cdot$ 伯努利的肖像一阵狂喜。

Fig.3 Jakob Bernoulli‎,1654－1705

膜拜完大佬，开始讲正题：

可以想到，想要输出概率来判断类别，我们得涉及概率分布，我们训练样本当成带参数的N重伯努利试验,损失函数可由极大似然估计(Maximum Likelihood Estimate)给出：

$L=-\prod\nolimits_{i=1}^N (P^{y_{i}}\times (1-P)^{1-y_{i}})$

为了求导方便，我们采用对数似然估计（交叉熵损失函数）：

$lnL=-\sum_{i=1}^{N}(y_{i}\cdot ln(P)+(1-y_{i})\cdot ln(1-P))$

针对概率P，我们采用sigmoid函数将Y映射为区间在[0,1]之间的值，即概率，形式如下：

$P=sigmoid(Xa)=\frac{1}{1+e^{-X\cdot\vec{a}}}$

现在我们要进行说明的是，带正则化项的交叉熵损失函数的最小化，即：

$lnL=-\sum_{i=1}^{N}(y_{i}\cdot ln(P)+(1-y_{i})\cdot ln(1-P))+\lambda\cdot \vec{a}^{T}\cdot\vec{a}$

相当于最大后验估计。

我们令 $g(a)=-\sum_{i=1}^{N}(y_{i}\cdot ln(P)+(1-y_{i})\cdot ln(1-P))$

$R_{cons}=g(a)+\lambda\cdot \vert \vert \vec{a} \vert \vert^{2}_{2}$

所以 $e^{-R_{cons}}=e^{-g(a)}\cdot e^{-\lambda\cdot \vert \vert \vec{a} \vert \vert^{2}_{2} }=(\prod\nolimits_{i=1}^N (P^{y_{i}}\times (1-P)^{1-y_{i}}))\cdot e^{-\lambda\cdot \vert \vert \vec{a} \vert \vert^{2}_{2} }$

由于 $e^{-\lambda\cdot \vert \vert \vec{a} \vert \vert^{2}_{2} }$ 是服从于均值为0，方差为 $\frac{1}{2 \lambda }$ 的正态分布。

此时我们的后验为 $P(a|Y)$ ,而 $(\prod\nolimits_{i=1}^N (P^{y_{i}}\times (1-P)^{1-y_{i}}))$ 实际上表示的是 $P(Y|a)$ ;正态分布实际上是先验 $P(a;\lambda)$ ;根据贝叶斯可知：

$P(a|Y)=\frac{P(Y|a)\cdot P(a;\lambda)}{P(Y)}$

而 $P(Y)$ 是常数，在进行最优化时可省去。

由此可见正则化还有个惊天秘密，那就是对损失函数的正则化项与最大后验估计的先验概率有对偶关系。正则化貌似不仅仅惩罚个模型复杂度这么简单，它的背后还真有许多奇妙之处。

由上述，显而易见的是：对损失函数的最小化，其实等同于最大后验估计。

在策略这个模块下，还有个坑没填，这个坑不填，前面说得天花乱坠那也只是在痴人说梦。

这个坑就是前面一直提到的泛化误差。没有它，训练集就算精确度再高，应用不到现实数据里，那都没什么用。泛化误差的衡量标准是泛化误差上界

我们知道我们的期望风险是： $R_{exp}(f)=E(L(Y,f_{}(X)))$

我们的经验风险是： $R_{emp}(f)=\frac{1}{N}\cdot \sum_{i=1}^{N}L(y_{i},f(x_{i}))$

另，我们的假设空间 $F$ 中模型的个数设为 $d$ ;

根据霍夫丁不等式：详细证明过程请见证明原稿。

这里只给出霍夫丁的结果： $P(S_{n}-E(S_{n})\geq t)\leq e^{\frac{-2t^2}{\sum^{N}_{i=1}(b_{i}-a_{i})^2}};S_{n}=\sum_{i=1}^{N}Z_{i};Z_{i}\in [a_{i},b_{i}];$

所以：

$P(R_{exp}(f)-R_{emp}(f)\geq \varepsilon)\leq e^{-2N\varepsilon^{2}}$

$P(\exists f\in F;R_{exp}(f)-R_{emp}(f)\geq \varepsilon)=P(\bigcup_{f\in F}^{} R_{exp}(f)-R_{emp}(f)\geq \varepsilon)\leq \sum_{f\in F}P(R_{exp}(f)-R_{emp}(f)\geq \varepsilon)\leq de^{-2N\varepsilon ^{2}}$

所以上界 $\alpha =de^{-2N\varepsilon ^{2}}$ ， $\varepsilon =\sqrt{\frac{1}{2N}\cdot ln(\frac{d}{\alpha })}$

所以泛化误差上界为： $R_{exp}(f)\geq R_{emp}(f)+\sqrt{\frac{1}{2N}\cdot ln(\frac{d}{\alpha })}$

从中可以看出一些端倪，泛化误差取决于样本数量，假设空间大小。

【1】当样本数量增加，泛化误差越小，且越接近于经验风险；

【2】当样本数量太少，泛化误差越大，且将高于经验风险；

【3】当假设空间越大，模型越复杂，模型越难学，泛化误差变大；

【4】当假设空间越小，模型越简单，模型越易学，泛化误差变小。

1.3 算法

算法这里暂不讨论，随机梯度下降什么的会在以后涉及到。当前只需要明白，前面两个模块已经将问题转化为一个最优化问题，所以这里涉及最优化算法，如果没有显示解析解，将采用数值算法逼近。

2. 机器学习的分类

2.1 大类

1. 监督学习

[a] 分类

[b] 回归

[c] 标注

2. 无监督学习

[a] 降维

[b] 聚类

3. 半监督学习

传导学习(Transtactive Learning)等

4. 强化学习

Q-learning

State-Action-Reward-State-Action (SARSA)

Deep Q Network (DQN)等等

2.2 面向机制分类

1.生成模型：计算机学的是联合概率分布 $P(Y|X)$

2.判别模型：计算机直接学习条件概率分布 $P(Y|X)$ 以及决策函数 $f(X)$

2.3 面向参数分类

1.参数方法(Parametric Approach):参数有限个，如感知机等

2.非参数方法(NonParametric Approach):参数太多了，如knn,每个已知点都是参数以及其他等等

2.4 面向学派分类：

1.频率学派

2.贝叶斯学派

其实，前面的线性模型的交叉熵损失函数与后验概率之间的关系可以看出，两个学派是可以相互转化的。

3.参考文献

[1] 李航. 统计学习方法[M]. 清华大学出版社, 2012.

[2] https://zhuanlan.zhihu.com/p/46999826

（一）机器学习的基本概要