无监督聚类分析

聚类指的是给定一组无标签样本，按照一定的准则将其划分为不同的样本簇，其中每个簇的样本都具有相似的属性和特征，而簇间的样本具有明显的差异

聚类≠\neq分类，分类是有监督的，给定标签和数据类别条件下的学习，而聚类是面向无监督学习的，是人工参与度极低的一种学习方法

聚类中样本距离的计算方法

设样本x\pmb{x}和y\pmb{y}之间的距离d(x,y)d(x,y)一般满足以下四项基本性质：

  1. 非负性：d(x,y)≥0d(x,y) \ge 0
  2. 自反性：d(x,y)=0d(x,y) = 0，当且仅当x=yx = y
  3. 对称性：d(x,y)=d(y,x)d(x,y) = d(y,x)
  4. 三角不等式：d(x,y)≤d(x,z)+d(z,y)d(x,y) \le d(x,z) + d(z,y)

下面有一些常用的计算距离的方法

曼哈顿距离

曼哈顿距离在二维空间表示为

d(x,y)=∣x1−y1∣+∣x2−y2∣d(x,y) = |x_1 - y_1| + |x_2 - y_2|

对于高维向量x=[x1,x2,⋯ ,xn]T\pmb{x} = {[x_1,x_2,\cdots,x_n]}^T和y=[y1,y2,⋯ ,yn]T\pmb y = {[y_1,y_2,\cdots,y_n]}^T，曼哈顿距离则表示为

d(x,y)=∑i=1n∣xi−yi∣d(x,y) = \sum^{n}_{i = 1}|x_i - y_i|

其中，曼哈顿距离越小，表示两个样本越相似

欧氏距离

对于二维空间给定的两个点(x1,x2)(x_1,x_2)和(y1,y2)(y_1,y_2)，它们之间的欧氏距离为

d(x,y)=(x1−y1)2+(x2−y2)2d(x,y) = \sqrt{ {(x_1 - y_1)}^2 + {(x_2 - y_2)}^2}

而对于高维样本的欧氏距离为

d(x,y)=∑i=1nxi−yi2d(x,y) = \sqrt{\sum^n_{i = 1}{x_i - y_i}^2}

其中，欧氏距离越小，表示两个样本越相似

注意：xx和yy的量纲应该相同，当用dd作为判断多个样本之间距离的时候，更应该拥有一致的量纲，这样才具有可比性

马氏距离

d(x,y)=(x−y)TΣ−1(x−y)d(x,y) = \sqrt{ {(x - y)}^T\Sigma^{-1}(x - y)}

马氏距离将协方差考虑进来， 排除了样本之间的相关性

当协方差矩阵为单位矩阵时， 马氏距离和欧氏距离相同

协方差矩阵刻画了向量中各分量的波动程度和样本分布方向

当欧式距离当中的某一项特别大时，会掩盖另一个较小项所起到的作用，这就是它的不足，而马氏距离可以修正这一点

马氏距离与原始数据的测量单位无关

闵可夫斯基距离

闵可夫斯基距离是曼哈顿距离和欧氏距离的扩展，定义为

d(x,y)=(∑i=1n∣xi−yi∣p)1pd(x,y) = {(\sum^n_{i = 1}{|x_i - y_i|}^p)}^{\frac{1}{p}}

其中pp是一个可变参数，当pp分别等于1和2时，闵可夫斯基距离就是曼哈顿距离和欧氏距离

下图展示了不同pp值下闵可夫斯基距离的单位等高线

pp取值比较小时， 明氏距离对于坐标轴对角线方向变化敏感（惩罚较大）

pp取值比较大时， 明氏距离对于坐标轴方向变化敏感（惩罚较大）

汉明距离

汉明距离一般用于度量离散字符串之间的相似程度，计算具有离散属性的样本之间的距离

给定两个长度相同的字符串，汉明距离则是两个字符串当中对应位置数值不同的字符串的个数，也就是两个字符串经过异或运算后1的个数

汉明距离越小，两个样本特征越相似

测地距离

在一个连通的空间当中，两个点至少存在一条路径将两点相连，其中最短的那条称为测地弧，测地弧的长度则是测地距离

对于空间当中的两个样本点xx和yy具有以下的性质

  1. 如果xx和yy所处的区域不连通，则测地距离不存在
  2. 两点之间欧氏距离小于等于测地距离
  3. 如果欧氏距离小于测地距离，则有
    1. 测地距离的路径至少经过边界上的一个点，如果边界区域为多边形，则至少经过一个顶点
    2. 在测地弧与xx和yy的连线所组成的区域内，只有xx和yy可以是凹点，其他的点必然是凸点
    3. 在单连通区域内测地距离和测地弧唯一，在多联通区域内测地距离唯一而测地弧不唯一

余弦相似度

我们可以通过测量高维样本向量之间的夹角来计算样本向量之间的相似度

对于二维向量，计算公式为

cos⁡(x,y)=x1y1+x2y2x12+x22y12+y22\cos(x,y) = \frac{x_1y_1 + x_2y_2}{\sqrt{x_1^2 + x_2^2}\sqrt{y_1^2 + y_2^2}}

对于高维向量，计算公式为

d(x,y)=cos⁡(x,y)=∑i=1nxiyi∑i=1nxi2∑i=1nyi2d(x,y) = \cos(x,y) = \frac{\sum^n_{i = 1}x_iy_i}{\sqrt{\sum^n_{i = 1}x_i^2}\sqrt{\sum^n_{i = 1}y_i^2}}

向量的形势为

d(x,y)=cos⁡(x,y)=⟨x,y⟩∣x∣∣y∣d(x,y) = \cos(x,y) = \frac{\langle x,y \rangle}{|x||y|}

与欧氏距离，汉明距离等不同，当两个样本余弦相似度越大，两个样本越相似

Tanimoto测度

S(x,y)=xTyxTx+yTy−xTy=x,y共有的特征数目x和y中占有的特征数目总和S(x,y) = \frac{x^Ty}{x^Tx + y^Ty - x^Ty} = \frac{x,y共有的特征数目}{x和y中占有的特征数目总和}

其中xx和yy的分量用二值来表示，0表示不具有某种特征，1表示具有某种特征

聚类性能评估

内部评估

内部评估有两个评估项：一个是类内聚合程度，通常由各个样本到类中心的距离表示；另一个是类间离散程度，通常由不同类的中心距离求取

根据类内和类间离散程度的不同结合，研究者提出了多种内部评估指标

  1. Davies-Bouldin指数

Davies-Bouldin指数（DBI）定义了类内聚合程度sis_i为：

si=(1ni∑k=1ni∣∣xk−x‾i∣∣p)1ps_i = {(\frac{1}{n_i}\sum^{n_i}_{k = 1}{||x_k - {\overline{x}}_i||}^p)}^{\frac{1}{p}}

其中xkx_k为第ii类的第kk个样本点，x‾i{\overline{x}_i}为第ii类的中心，nin_i为第ii类的样本数量，p≥1p \ge 1，sis_i的数值越小，说明第ii类的聚合程度越高

其次，类间离散程度mijm_{ij}定义为

mij=∣∣x‾i−x‾j∣∣m_{ij} = ||{\overline{x}_i} - {\overline{x}}_j||

mijm_{ij}的数值越大，说明第ii类和第jj类的离散程度越高

那么，两个类簇的聚类质量可以定义为

rij=si+sjmijr_{ij} = \frac{s_i + s_j}{m_{ij}}

因此，一个良好的聚类结果应该具有比较小的rijr_{ij}

令ri=max⁡i≠jrijr_i = \underset{i \neq j}{\max} r_{ij}，则DBIDBI可以定义为

DBI=1c∑i=1criDBI = \frac{1}{c}\sum^c_{i = 1}r_i

其中cc为聚类簇的数量，当DBIDBI越小时，聚类的质量就越好

  1. Dunn指数

Dunn指数（DVI）也是基于类内离散程度和类间离散程度的一个指标

最小类间距离ebe_b定义如下：

eb=min⁡1≤i≠j≤c{min∀x∈Ωi,∀y∈Ωj{∣∣x−y∣∣}}e_b = \underset{1\le i\neq j \le c}{\min}\{\underset{\forall x \in \Omega_i,\forall y \in \Omega_j}{min}\{||x - y||\}\}

  1. Silhouette系数

Silhouette系数对比的是类内元素的平均距离和这些元素与其他类元素的平均距离

具有高的Silhouette值表明类内元素聚集，类间元素分离，表示是很好的聚类，常用于确定K-均值聚类的最佳聚类数量

外部评估

  1. 纯度

计算公式为

purity(C)=1n∑kmax⁡m∣Wk∩Cm∣\mathcal{purity(C)} = \frac{1}{n}\sum_k\underset{m}{\max}|W_k \cap \mathcal{C}_m|

其中WkW_k代表聚类结果中第kk个类样本集合，Cm\mathcal C_m代表人工标签中第mm个类集合，C\mathcal C代表所有类的集合，∣Wk∩Cm∣|W_k \cap \mathcal C_m|表示两个集合交集的元素数量，max⁡\max表示当前类别中来自某一个类别的元素数量的最大值，即最多的元素类别

由此可得出纯度即表示聚类结果当中每一个类的最大相似元素的数量与整体样本数量的比值

纯度存在两个缺陷

  1. 当聚类的类别比较多的时候，内部的一致性也会相应增加，因此纯度往往更高
  2. 当不同类样本数量不平衡时，纯度也往往较大，难以准确刻画聚类的性能
  1. Rand指数

Rand指数(RI)可以通过以下公式求解

RI=TP+TNTP+FP+FN+TNRI = \frac{TP + TN}{TP + FP + FN + TN}

其中TPTP是聚类结果当中属于该类的正确的样本数量，TNTN是不属于该类的正确的样本数量，FPFP指的是聚类结果中错误的正样本数量，FNFN指的是聚类结果当中错误的负样本的数量

其中TPTP是同时在预测部分和Ground Truth部分聚类簇中点对的数量，FPFP是在预测部分但是不在Ground Truth当中的点对

如果数据集大小是nn，则有

TP+TN+FP+FN=(n2)TP + TN + FP + FN = \bigl( \begin{matrix} n\\2 \end{matrix} \bigr)

Rand指数存在一个问题：错误的正样本和错误的负样本二者的权重相等，对于某些聚类应用并不适合

对于正负样本的通俗解释：

训练集中每个样本对应1个标签（label），举个例子，标签表示该样本是否为猫，我们用yy来表示

标签为1，表示该样本是猫；标签为0，表示该样本不是猫

如果样本对应的标签为1，则该样本为正样本（positive sample）

如果样本对应的标签为0，则该样本为负样本（negative sample）

  1. F-度量

F-度量可以通过加权召回率β≥0\beta \ge 0来平衡错误负样本带来的影响，若PP表示准确率，RR表示召回率，则有以下公式

P=TPTP+FPP = \frac{TP}{TP + FP}

R=TPTP+FNR = \frac{TP}{TP + FN}

Fβ=(β2+1)⋅P⋅Rβ2⋅P+RF_\beta = \frac{(\beta^2 + 1)\cdot P\cdot R}{\beta^2\cdot P + R}

不难得出，当β=0\beta = 0时，召回对于F-度量没有影响，增加β\beta会在最终的F-度量当中分配一个不断增加的权重

对于之前提到的TNTN，则并不在考虑范围之中，可以在0到任意值当中变换

  1. Jaccard指数

Jaccard指数通过两个数据集合的并集与交集的比例刻画两个数据集合之间的相似性，定义为

J(A,B)=∣A∩B∣∣A∪B∣=TPTP+FP+FNJ(A,B) = \frac{|A\cap B|}{|A\cup B|} = \frac{TP}{TP + FP + FN}

两个数据集中共有元素的数量除以两个数据集集中所有元素数量总和

不难得出Jaccard指数的数值介于0和1之间，1代表两个数据集完全相同，0代表两个数据集没有交集

  1. Dice指数

Dice指数(DSC)和Jaccard指数差不多，只是增加了TpTp的权重

DSC=2TP2TP+FP+FNDSC = \frac{2TP}{2TP + FP + FN}

  1. Fowlkes-Mallows指数

Fowlkes-Mallows指数用于计算聚类结果和人工标签之间的相似性，计算公式为

FM=TPTP+FP⋅TPTP+FNFM = \sqrt{\frac{TP}{TP + FP}\cdot\frac{TP}{TP + FN}}

FM指数是准确度PP和召回率RR之间的几何平均值，FM指数的值越大，聚类簇和基准分类就越相似

  1. 互信息

互信息是一种信息论度量，用于度量两个随机变量之间的依赖程度，可以用于衡量聚类和真实值之间共享多少信息

归一化互信息是一个修正的结果，减少因为簇数增长导致的偏差

层次聚类算法

算法介绍

层次聚类算法是一种基于距离搜索的经典算法，通过计算不同样本点之间的相似度来构建具有多个层级关系的树状图

其中每个样本可以看作树的叶子节点，相似的样本可以聚集成一个类别作为中间节点，而相似的类别可以进一步地聚集在一起形成范围更大的聚类，以作为更高级的中间节点

所有样本的集合是最终树的根节点

层次聚类又可以分为合并型和分裂型两种聚类方式

相似性度量和停止条件

在分级聚类的时候，我们经常需要考虑两个问题

  1. 如何计算聚类之间的聚类
  2. 如何确定停止条件以停止合并聚类

我们有三种聚类距离的公式

  1. 最近邻距离

即为两个类当中任意两个样本点之间的最小距离

dmin⁡(Ci,Cj)=min⁡x∈Ci,y∈Cjd(x,y)d_{\min(\mathcal C_i,\mathcal C_j)} = \underset{x\in\mathcal C_i,y\in\mathcal C_j} {\min}d(\pmb x,\pmb y)

  1. 最远邻距离

两个聚类当中任意两个样本之间距离的最大值

dmax⁡(Ci,Cj)=max⁡x∈Ci,y∈Cjd(x,y)d_{\max(\mathcal C_i,\mathcal C_j)} = \underset{x\in\mathcal C_i,y\in\mathcal C_j} {\max}d(\pmb x,\pmb y)

这两类聚类距离对于噪声比较敏感

  1. 平均邻域距离

两个聚类中任意的样本对之间的距离的平均值

dαvg(Ci,Cj)=1ninj∑x∈Ci∑y∈Cjd(x,y)d_{\alpha vg}(\mathcal C_i,\mathcal C_j) = \frac{1}{n_in_j}\sum_{x\in\mathcal C_i}\sum_{y\in\mathcal C_j}d(\pmb x,\pmb y)

平均邻域距离的优点是对噪声不敏感，缺点是计算复杂度高

对于停止条件，一般根据实际情况进行设计，例如

  1. 当相似度达到一定阈值
  2. 当聚类数目达到某一个数量
  3. 某一层后，类内的距离突然增加

层次算法的优点：

  1. 可以聚类任意形状的样本簇
  2. 不需要指定聚类的数目
  3. 可以通过给定不同的参数来得到不同的结果

缺点：

  1. 对停止条件比较敏感
  2. 计算复杂度较高

主要算法

  1. BIRCH算法
  2. CURE算法
  3. Chameleon算法

K-均值聚类算法

K-均值算法遵循的准则是聚类簇中每一个样本点到该类聚类中心的均方误差和最小，即

J=∑i=1C∑x∈Xi∣∣x−mi∣∣22J = \sum^C_{i = 1}\sum_{x\in X_i}{||\pmb x - \pmb m_i||}^2_2

其中XiX_i假定为第ii个簇的样本集合，x\pmb x是XiX_i当中的样本，mi\pmb m_i是对应的第ii个簇的所有样本的中心，JJ是样本到它聚类中心的欧氏距离的求和

不难得知，当JJ值越小，表明聚类效果越好

需要注意的是，公式当中存在两个变量：mi\pmb m_i和XiX_i，需要同时进行优化，使得JJ趋于最小

K-均值算法的优点：

  1. 方法简单
  2. 数据可分性好
  3. 聚类结果较优

缺点：

  1. 对噪声样本比较敏感
  2. 实际当中聚类数量kk难以确定
  3. 得出来的结果是局部最优解，不一定是全局最优解
  4. 对初始的中心比较敏感

我们可以通过多次运行K-均值算法得到多个聚类结果，并合并产生更加鲁棒的聚类结果

算法变体

  1. K-medoids算法

之前提到的K-均值算法有一个缺点：容易受到噪声干扰

而K-medoids算法是在原算法上的改进，即不再选取簇内样本的均值作为聚类中心，而是选取簇内处于最中心的样本作为聚类中心，其他的算法过程基本不变

  1. K-modes算法

对于计算具有离散属性的样本，K-均值算法求得的聚类中心就可能是小数，就不具有实际意义了，所以之前运用到的计算样本均值以及样本均方误差的方法就不再适合了

这时候需要进行改进，也就是通过汉明距离对样本进行聚类

基于密度的聚类算法

K-均值聚类算法虽然算法简单，但是也存在两个局限性：

  1. 只适用于理想的球形分布的数据
  2. 难以确定初始聚类中心的数量

所以提出了一种基于密度的聚类算法，这里的密度就是指某一个样本点其周围样本点的聚集程度

算法的基本思路就是按照样本点的密度进行迭代聚类，如果已经标记的样本点的密度大于预设的阈值，则将该标记样本点临近区域内的样本点添加到相应的样本簇当中

该算法不能保证所有点都能被聚类，可能会出现无聚类点（离所有聚类的中心都比较远）

其聚类中心是局部密度最大点

基于密度的聚类算法的优点是：

  1. 对非球形分布的样本具有很好的鲁棒性
  2. 不需要聚类的数目
  3. 只需要遍历一次就可以完成聚类，且聚类结果和遍历顺序无关

缺点：

  1. 比较依赖给定的参数，比如密度的判定阈值
  2. 当样本点比较多时，计算复杂度会较高

主要算法

  1. DBSCAN算法
  2. DPCA算法
  3. OPTICS算法

谱聚类算法

算法介绍

谱聚类算法采用加权无向图刻画样本之间的关系，其中图的每一个节点vi\pmb v_i代表一个样本xi\pmb x_i，边eije_{ij}则刻画了两个样本之间的相似关系，其权重wijw_{ij}代表了样本的相似程度

一般而言，距离越远，权重越低；反之则越高

基本概念

  1. 带权无向图及其邻接矩阵A\pmb A（详见数据结构）
  2. 度矩阵

对于顶点vi\pmb v_i，定义该点的度did_i为与它相连接的所有边的权重之和，可表示为

di=∑j=1nwijd_i = \sum^n_{j = 1}w_{ij}

因此可以得到一个以did_i为对角元的对角矩阵D∈Rn×n\pmb D \in \mathbb{R}^{n\times n}，称之为度矩阵

  1. 拉普拉斯矩阵

对于之前的邻接矩阵A\pmb A和度矩阵D\pmb D，可以得到拉普拉斯矩阵的计算公式

L=D−A\pmb L = \pmb D - \pmb A

拉普拉斯矩阵具有以下性质

  1. 拉普拉斯矩阵为对称矩阵，且特征值为实数
  2. 对于nn维向量v=(v1,v2,⋯ ,vn)\pmb v = (v_1,v_2,\cdots,v_n)，且v1,v2,⋯ ,vn∈Rv_1,v_2,\cdots,v_n\in\mathbb{R}，可以得到

vTLv=12∑i,j=1nwij(vi−vj)2\pmb v^T\pmb L\pmb v = \frac{1}{2}\sum^{n}_{i,j = 1}w_{ij}{(v_i - v_j)}^2

  1. 拉普拉斯矩阵满足半正定矩阵，存在nn个特征值满足∀k∈n,λk≥0\forall k\in n,\lambda_k \ge 0且λ1,λ2,⋯ ,λn∈R\lambda_1,\lambda_2,\cdots,\lambda_n\in\mathbb{R}
  2. 拉普拉斯矩阵中特征值等于0的数量与其对应的图ϱ(V,E)\varrho(V,E)中包含的最大连通子图的个数相同

算法特点

谱聚类算法的优点有：

  1. 谱聚类对于分布不规则的样本或者分布稀疏的样本有很好的鲁棒性
  2. 谱聚类处理类别比较少的样本数据会有很好的聚类效果
  3. 谱聚类更容易得到全局最优解
  4. 对于高维数据更有效

缺点有：

  1. 对相似度矩阵比较敏感，选择不同的相似度矩阵计算方法会得到不同的聚类结果
  2. 如果不同聚类簇当中的样本点的个数相差较大，则使用谱聚类不能得到很好的聚类效果

有监督统计学习模型

贝叶斯分类器

贝叶斯定理

即概率论当中的贝叶斯公式

P(Ci∣x)=P(Ci)P(x∣Ci)∑i=1nP(x∣Ci)P(Ci)P(\mathcal C_i|x) = \frac{P(\mathcal C_i)P(x|\mathcal C_i)}{\sum^n_{i = 1}P(x|\mathcal C_i)P(\mathcal C_i)}

其中，P(Ci)P(\mathcal C_i)表示全体样本当中Ci\mathcal C_i类出现的可能性，即先验概率；P(x∣Ci)P(x|\mathcal C_i)表示Ci\mathcal C_i类的样本中出现x\pmb x的可能性，称为似然概率；P(Ci∣x)P(\mathcal C_i|x)表示特征为xx的样本中出现Ci\mathcal C_i类的可能性，称为后验概率

最小错误率判别准则

最小错误率贝叶斯决策的目标是令分类结果的后验概率最大化

以典型的二分类问题为例，给定任一个样本特征xx，当其关于不同类别的后验概率P(C1∣x)P(\mathcal C_1|x)和P(C2∣x)P(\mathcal C_2|x)已知时，对应的最小错误率贝叶斯决策判别规则可表示为

(1)当P(C1∣x)>P(C2∣x)时，x∈C1(1)当P(\mathcal C_1|x) > P(\mathcal C_2|x)时，x \in \mathcal C_1

(2)当P(C1∣x)<P(C2∣x)时，x∈C2(2)当P(\mathcal C_1|x) < P(\mathcal C_2|x)时，x\in\mathcal C_2

然而在实际应用当中，后验概率往往难以直接获得，此时可以通过贝叶斯定理获得以下等价的最小错误率决策准则

(1)若P(Ci∣x)=max⁡j=1,2P(Cj∣x),则x∈Ci(1)若P(\mathcal C_i|x) = \underset{j = 1,2}{\max}P(\mathcal C_j|x),则x\in\mathcal C_i

(2)若P(x∣Ci)P(Ci)=max⁡j=1,2P(x∣Ci)P(Ci)，则x∈Ci(2)若P(x|\mathcal C_i)P(\mathcal C_i) = \underset{j = 1,2}{\max}P(x|\mathcal C_i)P(\mathcal C_i)，则x\in\mathcal C_i

(3)若l(x)=P(x∣C1)P(x∣C2)>P(C2)p(C1)=τ，则x∈C1，反之亦然(3)若l(x) = \frac{P(x|\mathcal C_1)}{P(x|\mathcal C_2)} > \frac{P(\mathcal C_2)}{p(\mathcal C_1)} = \tau，则x\in\mathcal C_1，反之亦然

(4)设h(x)=−ln⁡l(x)=−ln⁡P(x∣C1)+ln⁡P(x∣C2)，若h(x)<ln⁡P(C1)P(C2)，则x∈C1;若h(x)>ln⁡P(C1)P(C2)，则x∈C2(4)设h(x) = -\ln l(x) = -\ln P(x|\mathcal C_1) + \ln P(x|\mathcal C_2)，若h(x) < \ln\frac{P(\mathcal C_1)}{P(\mathcal C_2)}，则x\in\mathcal C_1;若h(x) > \ln\frac{P(\mathcal C_1)}{P(\mathcal C_2)}，则x\in\mathcal C_2

其中，l(x)l(x)称为似然函数比，τ\tau被称为阈值或似然比，h(x)h(x)为似然函数比的对数形式

我们可以将误判事件ee表示为

e=defy≠Cie \overset{def}{=}y \neq \mathcal C_i

其中，yy表示样本xx真实的类别，Ci\mathcal C_i表示基于最小错误率判别准则推断的类别，然后误判事件ee的全概率可表示为

P(e)=∫−∞∞p(e,x)dx=∫−∞∞p(e∣x)p(x)dxP(e) = \int^\infty_{-\infty}p(e,x)dx = \int^\infty_{-\infty}p(e|x)p(x)dx

其中，p(e∣x)p(e|x)为样本特征xx已知条件下的条件错误率，p(e∣x)p(e|x)和p(x)p(x)均为xx的函数，P(e)P(e)即为p(e∣x)p(e|x)的数学期望

综上，在二分类问题当中，xx的条件错误概率可以表示为

p(e∣x)={p(C1∣x)当p(C2∣x)>p(C1∣x)时p(C2∣x)当p(C1∣x)>p(C2∣x)时p(e|x) = \begin{cases}p(\mathcal C_1|x)&\text{当$p(\mathcal C_2|x) > p(\mathcal C_1|x)$时}\\\\p(\mathcal C_2|x)&\text{当$p(\mathcal C_1|x) > p(\mathcal C_2|x)$时}\end{cases}

我们令τ\tau表示最小错误率判别准则的决策界面，且有p(C1∣x)=p(C2∣x)p(\mathcal C_1|x) = p(\mathcal C_2|x)

此时，我们可以将P(e)P(e)作如下展开

P(e)=P(C2)∫−∞τp(x∣C2)dx+P(C1)∫τ∞p(x∣C1)dx=p(C2)P2(e)+P(C1)P1(e)P(e) = P(\mathcal C_2)\int^\tau_{-\infty}p(x|\mathcal C_2)dx + P(\mathcal C_1)\int^\infty_\tau p(x|\mathcal C_1)dx = p(\mathcal C_2)P_2(e) + P(\mathcal C_1)P_1(e)

朴素贝叶斯判别器

在实际应用当中，我们一般使用多重观测变量构成的高维向量进行判别，而朴素贝叶斯分类器对不同维度的观测变量采用了条件独立性假设，从而将多维观测变量下的贝叶斯定理简化成以下形式

P(y∣x1,⋯ ,xd)=P(y)P(x1,⋯ ,xd∣y)P(x1,⋯ ,xn)P(y|x_1,\cdots,x_d) = \frac{P(y)P(x_1,\cdots,x_d|y)}{P(x_1,\cdots,x_n)}

使用朴素的条件独立性假设则有

P(xi∣y,x1,⋯ ,xi−1,xi+1,⋯ ,xd)=P(xi∣y)P(x_i|y,x_1,\cdots,x_{i - 1},x_{i + 1},\cdots,x_d) = P(x_i|y)

对于所有的ii，这种关系就可以简化为

P(y∣x1,⋯ ,xd)=P(y)∏i=1dP(xi∣y)P(x1,⋯ ,xd)P(y|x_1,\cdots,x_d) = \frac{P(y)\prod^d_{i = 1}P(x_i|y)}{P(x_1,\cdots,x_d)}

如果xix_i取值过多，就会出现某一个值从未被取过的情况，即概率为0，就会导致∏i=1nP(xi∣y)=0\prod^n_{i = 1}P(x_i|y) = 0

通常情况下，可以引入平滑项来有效避免上述情况，方法如下

x+αn+αd\frac{x + \alpha}{n + \alpha d}

其中dd表示特征维度，α(>0)\alpha(>0)是平滑参数

当0<α<10 < \alpha < 1时，平滑度低，称为Lidstone平滑

当α≥1\alpha\ge1时，平滑度高，称为Laplace平滑

概率图模型

  1. 有向图模型——贝叶斯网络

  2. 无向图模型——马尔可夫网

概率密度估计

最大似然函数

略

最大后验估计

最大后验估计就是将待估计的参数也当成随机变量，根据观测数据来对这个参数的分布进行估计

非参数的概率密度估计

  1. 直方图估计法
  2. Parzen窗函数估计法
  3. K近邻估计法

采样方法

  1. 蒙特卡洛方法

蒙特卡洛方法的核心思想是，用采样得到的样本点的均值来近似估计分布的数学期望，即

Ep(x)(f(x))=∫abf(x)p(x)dx\mathbb E_{p(x)}(f(x)) = \int^b_af(x)p(x)dx

Ep(x)[f(x)]≈1n⋅∑i=1nf(xi)\mathbb E_{p(x)}[f(x)] \approx \frac{1}{n}\cdot\sum^n_{i = 1}f(x_i)

说白了就是概率论里面的矩估计法，使用样本矩代替总体矩

  1. 马尔可夫链

假设我们的序列状态是⋯ ,Xt−2,Xt−1,Xt,Xt+1,⋯\cdots,X_{t - 2},X_{t - 1},X_t,X_{t + 1},\cdots，那么时刻XtX_t的状态会决定Xt+1X_{t + 1}的状态的条件概率，即：

对于一个随机变量序列X={Xt:t>0}X = \{X_t:t>0\}，则tt时刻的条件概率为P(Xt∣Xt−1,⋯ ,X1)P(X_t|X_{t - 1},\cdots,X_1)，当序列XX满足马尔可夫性质时，条件概率可以简化成

P(Xt∣Xt−1,⋯ ,X1)=P(Xt∣Xt−1)P(X_t|X_{t - 1},\cdots,X_1) = P(X_t|X_{t - 1})

马尔可夫链蒙特卡洛采样（MCMC）

马尔科夫链蒙特卡洛采样就是通过采样来生成满足分布p(x)p(x)的样本，进而完成后验概率估计等任务，同时采样的方式满足马尔科夫链

其中有两个关键的超参数：转移矩阵QQ和接受率α\alpha

Metropolis-Hastings采样

该算法将MCMC算法当中的接受率改成以下形式

α(i,j)=min⁡{p(zj)Q(j,i)p(zi)Q(i,j),1}\alpha(i,j) = \min\left\{\frac{p(z_j)Q(j,i)}{p(z_i)Q(i,j)},1\right\}

此时采样过程就有了更大的接受率，提升了收敛速度

缺点是计算量比较庞大，难以处理高维数据

吉布斯采样

给定高维随机变量的情况，吉布斯采样从维度分解的角度简化样本的生成，也就是每次只考虑一个维度进行采样，并固定其他维度，之后依次迭代处理不同的维度，生成采样结果

优点：适合高维数据的采样

有监督判别学习模型

线性判别函数

令x=(x1,x2,⋯ ,xd)\pmb x = (x_1,x_2,\cdots,x_d)表示维度为dd的样本特征向量，其中xix_i为x\pmb x第ii个维度上的特征取值

设w=[w1,w2,⋯ ,wd]T\pmb w = {[w_1,w_2,\cdots,w_d]}^T为x\pmb x在各个维度上线性加权的权重，bb为偏差项，f(x)f(\pmb x)为输出，对应于类别，此处w\pmb w和bb都是待学习的未知参数

f(x)=∑i=0dwixi+bf(\pmb x) = \sum^d_{i = 0}w_ix_i + b

f(x)=wTx+bf(\pmb x) = \pmb w^T\pmb x + b

当将判别函数的输出置为0即可得到dd维特征空间的一个d−1d - 1维的决策平面g(x)=0g(\pmb x) = 0

权向量w\pmb w与决策面垂直，决定决策面的方向，偏差项bb确定了决策面在特征空间的偏移，所以确定了w\pmb w和bb就可以唯一的确定一个决策面

我们很容易知道，决策面会将特征空间分为两个部分，分别对应两个类别

我们可以通过样本和决策面的相对位置来推断其类别，即

{f(x)>0x∈C1f(x)<0x∈C2f(x)=0无法判别\begin{cases}f(\pmb x) > 0&\text{$x\in\mathcal C_1$}\\\\f(\pmb x) < 0&\text{$x\in\mathcal C_2$}\\\\f(\pmb x) = 0&\text{无法判别}\end{cases}

对于多类问题的判别，我们常常可以通过分成多个两类进行判别

  1. 一对多策略：对某类和非某类进行二分类问题的分析
  2. 一对一策略：对任意两类构建二分类问题，并进行集成分析（对于kk个类别有k(k−1)2\displaystyle\frac{k(k - 1)}{2}个判别平面）
  3. 一对一策略特例：对任意两类采用两类判别，且每一类都有自己的判别函数，使得不确定区域最小

一对一策略的特例是每个类别都有一个判别函数，把x\pmb x代入到判别函数当中，判别函数最大的那个就是所属的类别

线性判别分析

线性判别函数存在两个方面的问题：

  1. 线性判别函数的复杂度会随着特征维度的不断升高而不断增加
  2. 高维特征空间内训练样本相对稀疏，过拟合的风险会增加

所以出现了Fisher线性判别方法，即将高维的数据直接投影到一维进行分析，使得同类聚集，不同类分开

所有的样本特征都投影到一条直线上，决策面退化成决策点

令X=[x1,x2,⋯ ,xn]\pmb X = [\pmb x_1,\pmb x_2,\cdots,\pmb x_n]为所有训练样本的特征向量组成的矩阵，其中共有nn个样本，每一个样本是一个列向量

其线性投影之后的特征Y\pmb Y可表示为

Y=θTX\pmb Y = \pmb \theta^T\pmb X

其中θ\pmb\theta表示投影矩阵，代表投影方向

设NkN_k表示属于Ck\mathcal C_k的样本数量，则在初始的空间里面，两个类别的均值向量是

uk=1Nk∑xi∈Ckxi,k=1,2\pmb u_k = \frac{1}{N_k}\sum_{\pmb x_i\in\mathcal C_k}\pmb x_i,k = 1,2

在投影空间内，则均值为一标量

u^k=1Nk∑yi∈Ckyi=θTuk\hat u_k = \frac{1}{N_k}\sum_{y_i\in\mathcal C_k}y_i = \pmb\theta^T\pmb u_k

定义两个类别均值在投影空间内的投影距离为两个类别均值之间的分离程度，计算公式如下

u^2−u^1=θT(u2−u1)\hat u_2 - \hat u_1 = \pmb\theta^T(\pmb u_2 - \pmb u_1)

在类内聚集方面，定义任意一类别Ck\mathcal C_k的类内离散度为样本和中心的距离之和，即

sk^2=∑yi∈Ck(yi−u^k)2,k=1,2\hat{s_k}^2 = \sum_{y_i\in\mathcal C_k}{(y_i - \hat u_k)}^2,k = 1,2

我们可以定义目标函数如下

J(θ)=(u^2−u^1)2s1^2+s2^2J(\pmb\theta) = \frac{ {(\hat u_2 - \hat u_1)}^2}{\hat{s_1}^2 + \hat{s_2}^2}

J(θ)J(\pmb\theta)越大，表示类内越聚集，类间越分离

我们可以定义在原始高维空间内的第kk类的离散度为

Sk=∑xi∈Ck(xi−uk)(xi−uk)T\pmb S_k = \sum_{\pmb x_i\in\mathcal C_k}(\pmb x_i - \pmb u_k){(\pmb x_i - \pmb u_k)}^T

类内的离散度矩阵为

Sw=S1+S2\pmb S_w = \pmb S_1 + \pmb S_2

类间离散度矩阵为

Sb=(u2−u1)(u2−u1)T\pmb S_b = (\pmb u_2 - \pmb u_1){(\pmb u_2 - \pmb u_1)}^T

则可推断得最佳的投影方向θ∗\pmb\theta^*为

θ∗∝Sw−1(u2−u1)\pmb\theta^*\varpropto \pmb S_w^{-1}(\pmb u_2 - \pmb u_1)

上述优化方式的前提是Sw−1\pmb S_w^{-1}存在，如果不存在时，应该考虑其他的优化方法

支持向量机

支持向量机解决的问题是如何在多个可行的二分类界面中选择最优分类界面，基本思想是寻找使得两类样本间隔最大的分界线作为两类的分类界面，也就是将线性分类界面的学习问题转换成间隔最大的优化问题

模型构建与优化

后续暂略

深度学习基础

基本知识

  1. 数据

深度学习过程中所运用到的学习资料，一般有以下三种
1. 训练数据
2. 验证数据
3. 测试数据

  1. 损失函数

测量预测标签和真实标签之间的差异或损失的函数，用于评估当前网络参数输出与真实结果的差异

在大多数情况下，损失函数是有界的

  1. 过拟合

过拟合表示的就是模型在训练集上表现优秀，但是因为模型复杂度过高，在验证数据集和测试数据集当中表现不佳

这也是泛化能力差的最直观的表现

  1. 欠拟合

欠拟合指的是模型在训练集上表现的也不好，通常是由训练样本数据不足或者训练数据分布不理想导致的

  1. 优化

优化应用于神经网络的训练过程中，获取使得损失函数最小化的网络参数

但是由于训练网络的损失函数可能是一个非凸函数，优化可能比较困难，常采用近似优化算法，寻找性能足够好的局部最小值，如梯度下降法

  1. 感受野

神经元的感受野是指卷积神经网络操作的范围在原始图像上映射区域的大小

感受野越大，所刻画的上下文信息越充分

神经网络基本结构

单个神经元建模

设x1,x2,⋯ ,xnx_1,x_2,\cdots,x_n表示来自神经元的多个输入信号，w1,w2,⋯ ,wnw_1,w_2,\cdots,w_n为权重，阈值为τ\tau，u(x)u(x)为单位阶跃函数，则模型的输出yy可以表示为

y=u(∑i=1nwixi−τ)y = u\left(\sum^n_{i = 1}w_ix_i - \tau\right)

常见的激活函数还有：Sigmoid, ReLU, Softmax等等

多层神经网络

对于复杂的任务，单个神经元难以完成，就需要更多的神经元进行预测

一个典型的神经网络通常由一个输入层，多个隐藏层和一个输出层构成，相邻层的神经元之间是全连接关系

前向传播

前向传播指的是传播过程中，输入信息沿着单一方向从网络的隐藏层传递到输出层，然后生成输出结果

其中每一个神经元都是由上一层的神经元输入以及对应的权重所决定的

反向传播

反向传播是通过链式求导法则和梯度下降法，从损失函数L\mathcal L，最后一层到第一层进行数据传播，逐渐实现神经网络参数的训练

在反向传播过程中，梯度消失和梯度爆炸是两类常见的问题

损失函数

分类损失函数

对于最简单的二分类问题，最基本的损失是0-1损失，即

L(y^,y)={0y^=y1y^≠y\mathcal L(\hat{\pmb y},\pmb y) = \begin{cases}0&\text{$\hat{\pmb y} = \pmb y$}\\\\1&\text{$\hat{\pmb y} \neq \pmb y$}\end{cases}

输出与真实值相同则输出为0，反之则为1

但是由于0-1损失函数是一个不连续的分段函数，不利于优化，所以在实际情况下常常构造其代理损失使其便于优化

  1. 交叉熵损失函数

当两类的类别标签分别定义为0和1时，常常使用交叉熵损失

L=−(ylog⁡(y^))+(1−y)log⁡(1−y^)\mathcal L = -(\pmb y\log(\hat{\pmb y})) + (1 - \pmb y)\log(1 - \hat{\pmb y})

当真实类别y=0\pmb y = 0时，欲使交叉熵损失越小，则希望y^\hat{\pmb y}趋于0，反之则希望y^\hat{\pmb y}趋于1

当扩展到多分类损失时，常用交叉熵损失

L=−1n∑i=0n−1∑j=0n−1yijlog⁡pij\mathcal L = -\frac{1}{n}\sum^{n - 1}_{i = 0}\sum^{n - 1}_{j = 0}y_{ij}\log p_{ij}

其中pijp_{ij}表示第ii个样本预测为第jj个标签值的预测概率，yijy_{ij}则代表第ii个样本预测为第jj个标签值的真实概率，非0即1

这个损失函数的本质是当样本ii的真实类别是jj时，样本ii属于类别jj的概率越大，交叉熵损失越小，反之 则越大

  1. 铰链损失函数

我们定义二分类的类别标签分别为-1和1时，铰链损失函数为

L(y^,y)=max⁡(0,1−y^y)\mathcal L(\hat y,y) = \max(0,1 - \hat yy)

当预测值和真实标签比较接近的时候，损失L(y^,y)L(\hat y,y)趋于0，而预测与真实结果相反的时候，损失趋近于2

所以尽可能使损失函数最小来达到最好效果

  1. 指数损失函数

L(y^,y)=exp⁡(−y^y)\mathcal L(\hat y,y) = \exp(-\hat yy)

当预测值和真实标签比较接近的时候，损失L(y^,y)L(\hat y,y)趋于最小，而预测与真实结果相反的时候，损失输出较大

同样的，我们应该最小化损失函数以实现更好的预测效果

  1. KL散度损失函数

除了交叉熵损失之外，相对熵也常用来衡量概率分布的结果，称为KL散度

KL(P∣∣Q)=def∫−∞∞p(x)log⁡p(x)q(x)dxKL(P||Q) \overset{def}{=}\int^\infty_{-\infty}p(x)\log\frac{p(x)}{q(x)}dx

其中PP和QQ是两个概率分布，p(x)p(x)和q(x)q(x)分别是它们的概率密度函数

当PP和QQ的分布差别不大时，KL散度特别低；反之则特别大

KL散度可以用于衡量网络预测的分布和真实分布的一致程度

  1. JS散度

从KL散度的公式易知KL散度不具有对称性，所以推出了JS散度

JS(P∣∣Q)=12KL(P(x)∣∣P(x)+Q(x)2)+12KL(Q(x)∣∣P(x)+Q(x)2)JS(P||Q) = \frac{1}{2}KL(P(x)||\frac{P(x) + Q(x)}{2}) + \frac{1}{2}KL(Q(x)||\frac{P(x) + Q(x)}{2})

回归损失函数

在回归问题的损失函数选择上，通常采用L2L_2损失、L1L_1损失和平滑L1L_1损失

  1. L2L_2损失（最小方差损失）

L2(y,y^)=∑i=1n(yi−y^i)2\mathcal L_2(y,\hat y) = \sum^n_{i = 1}{(y_i - \hat y_i)}^2

其中nn为样本数量

  1. L1L_1损失（最小绝对误差损失）

L1(yi,y^i)=∑i=0n−1∣yi−y^i∣\mathcal L_1(y_i,\hat y_i) = \sum^{n - 1}_{i = 0}|y_i - \hat y_i|

L1L_1损失和L2L_2损失本质上相同，但是求导时不同

  1. 平滑L1L_1损失

Smooth=∑i=0n−1{0.5(yi−y^i)2if∣yi−y^i∣<1∣yi−y^i∣−0.5otherwiseSmooth = \sum^{n - 1}_{i = 0}\begin{cases}0.5{(y_i - \hat y_i)}^2&\text{if$|y_i - \hat y_i| < 1$}\\\\|y_i - \hat y_i| - 0.5&\text{otherwise}\end{cases}

卷积神经网络基本层

卷积层

卷积层是卷积神经网络的核心组成模块，作用是将原始输入数据映射为多通道空间特征，通过卷积方式实现输入特征的提取和变换映射，进而获得数据的特征表示

卷积操作是对于输入的局部区域进行加权处理，是一个局部连接，这个区域称为卷积的感受野

可以理解为将图像在空间域分割成若干小块，并将它们与特定的一组权重进行卷积

假设给定输入的二维数据大小为n×nn\times n，卷积核维度为k×kk\times k，Padding操作参数为pp，步长为ss，则输出的数据大小是o×oo\times o，其中

o=n−k+2ps+1o = \frac{n - k + 2p}{s} + 1

通常卷积层会使用多个滤波器实现特征的提取，每一个滤波器输出一个二维矩阵数据

将这些滤波器级联起来，卷积层的输出就可以看成是三维矩阵

当输入也是三维的时候，让卷积核也是三维的，卷积之后的结果仍然是二维的

卷积输出和卷积核的大小也有关，为了让输入和输出的结果大小保持一致，会进行Padding操作，即对于原输入进行补零扩展

增加了pp圈0，则称参数为pp的Padding操作

卷积的变体
  1. 反卷积（转置卷积）

反卷积不能恢复原始卷积输入的每个元素值

反卷积是一种特殊的卷积，通常只能够还原到与前一层同一维度大小数据

  1. 空洞卷积

空洞卷积指的是在卷积谱当中引入空洞，实现感受野的增加

和一般的卷积相比，空洞卷积引入了一个新参数“扩张率”来表示卷积核进行空洞卷积时数据选择的距离

空洞卷积的扩张即在标准卷积核中加入间隔以增大感受野，同时保有原有卷积核的大小

随着扩张率的增加，感受野将会以指数扩展

  1. 可分离卷积

可分离卷积是将卷积分成多个卷积进行计算，从而降低卷积的计算复杂度

一般可分为以下两种：

  • 空间可分离卷积
  • 深度可分离卷积

对于空间可分离卷积而言，不是所有的卷积核都可以进行拆分

深度可分离卷积可以用于无法被拆分的卷积核

对于图像而言，一般有RGB三个通道，深度可分离卷积则是针对每一个通道都设置不同的卷积核，保持输出的深度与原图一致，最终采用1x1卷积核进行点卷积操作

  1. 组卷积

组卷积是将输入特征分为多类并送入多个GPU进行计算，随后将不同GPU的结果进行融合

组卷积的优点是：

  1. 降低参数量为标准卷积的1g\displaystyle\frac{1}{g}，也等价于在同等参数量下生成gg倍的特征（gg为组的数量，当g=1g = 1时，退化成标准卷积）
  2. 可以提升性能

缺点为：组间信息无法有效传递

  1. 动态卷积

动态卷积会将卷积层的参数与输入数据进行关联，即自适应调整，极大的增强了网络的灵活性

池化层

池化层一般加在卷积层之后，充当减小特征谱分辨率的角色，以获取更大的感受野

池化层的操作大概可以概括为在感受野的邻域内归纳具有代表性的信息，并输出作为该区域的主导响应

最大池化

最大池化就是对一个数据块取最大值来代表这个数据块

平均池化

平均池化就是对一个数据块取平均值来代表这个数据块

在池化操作当中，假设输入的二维数据大小是n×nn\times n。池化核维度是k×kk\times k，Padding操作参数是pp，步长为ss，则输出数据的大小为

o=n−k−2ps+1o = \frac{n - k - 2p}{s} + 1

池化操作的本质思想就是一方面保留较大的响应区域，使得特征对于平移和其他变换的敏感度降低，增强特征的鲁棒性；另一方面是要降低特征尺度，从而避免大尺度所带来的高计算负担，改善网络输出，防止过拟合

组合池化

组合池化是前两种池化方式的拓展，通常有两种：

  • 级联

级联的组合池化是将最大值池化和均值池化的结果直接级联

  • 相加

相加的组合池化是将最大值池化和均值池化的结果求均值

空间金字塔池化

空间金字塔池化是采取空间多级操作的方式进行特征提取，在提高对任意大小的目标的识别精度方面有显著的表现

空间金字塔池化可以通过多尺度特征提取出固定大小的特征向量，从而解决了不同大小的特征谱输出不一致的问题

非线性激活函数

非线性激活函数常用于对卷积层的输出进行处理，增加非线性拟合能力

卷积神经网络当中，通常需要对卷积层和全连接层的输出使用激活函数进行处理，提升CNN的性能

常用的激活函数有Sigmoid函数，Tanh函数，ReLU函数，LeakyReLU函数，PReLU函数和ELU函数

sigmoid(x)=11+e−xsigmoid(x) = \frac{1}{1 + e^{-x}}

tanh(x)=ex−e−xex+e−xtanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}

ReLU(x)=max⁡(0,x)ReLU(x) = \max(0,x)

LeakyReLU(x)={xiif xi>0xiaiif xi≤0,其中ai>1LeakyReLU(x) = \begin{cases}x_i&\text{if\ $x_i> 0 $}\\\\\frac{x_i}{a_i}&\text{if\ $x_i \le 0,其中a_i>1$}\end{cases}

PReLU(x)={xx>0axx≤0PReLU(x) = \begin{cases}x&\text{$x>0$}\\\\ax&\text{$x \le 0$}\end{cases}

ELU(x)={xx>0a(ex−1)x≤0ELU(x) = \begin{cases}x&\text{$x>0$}\\\\a(e^x - 1)&\text{$x\le0$}\end{cases}

对于Sigmoid和Tanh函数而言，它们都存在严重的梯度消失的问题，即在较大和较小的数值时，梯度接近于0，不利于反向传播，所以ReLU取代了它们

但是ReLU也存在一些问题：

一个是失活问题：在反向传播的过程中，如果某一个很大的梯度流经ReLU，就会使前面权重的偏置更新为很小的负数，使得后续训练当中该单元的输出是负数，权重不再更新，ReLU失活

另一个是漂移效应：ReLU没有负区域，数据分布的均值为正，非饱和区域（x>0x>0）的一阶导数为1，没有对梯度和输出进行限制，所以在训练过程中会增大网络各层神经元数据分布的方差，从而使训练变得困难

而LeakyReLU和PReLU对ReLU进行了一定的改进

LeakyReLU牺牲了ReLUctant的稀疏激活特性，但是获得了较强的鲁棒性，且其负区域存在一个微小梯度，所以避免了ReLUctant的失活问题，也在一定程度上削弱了漂移效应

PReLU用一个线性函数代替了ReLU的左饱和区域，且该线性函数的斜率是自适应的，在误差反向传播过程中更新，由于PReLU没有饱和区域，所以能够有效抑制ReLU失活的问题

ELU负区域采用指数型函数，超参数α\alpha由网络自适应学习，负输入区域存在一部分非饱和区域，可以对ReLUctant的失活问题起到一定的抑制作用，具有噪声鲁棒性和低复杂度的优点

全连接层

定义

全连接层指的是相邻的两层任意节点之间都存在连接。实现输入特征的整合和映射

它的输出y\pmb y能被表示为一个输入x\pmb x与滤波器W\pmb W的矩阵乘法，再加上偏差b\pmb b

y=WTx+b\pmb y = \pmb W^T\pmb x + \pmb b

通常情况下，全连接层加在卷积层之后，使得最终的输出维度和目标维度一致，进而实现结果预测

运算步骤如下：

  1. 将卷积层的输入转换成向量
  2. 将向量的每一个维度看成是全连接层的一个节点
  3. 与全连接层进行连接
  4. 通过调整最后一层全连接层的点的数量来改变输出的维度

例如，当分类问题输出为C\mathcal C个类别，仅需要将最后一层设置为C\mathcal C个点，每一个点对应于一个类别，从而实现卷积神经网络在C\mathcal C个类别的预测

将全连接层转化为卷积层

全连接层和卷积层本质上都可以理解为矩阵乘法，唯一的不同就是卷积层使用了局部连接，且卷积中神经元共享参数

所以可以将全连接层转化为卷积层，且这种转化不受图像大小的限制，减少了计算量，前向传播更加高效

注意力机制

注意力机制可以赋予模型动态地给与输入的某些部分更多的关注能力，也就是创造输入信息的不对称性

硬注意力机制

如果注意力数值采用离散的数值，则把该种注意力机制称为硬注意力机制

每个输入部分的权重只有两个可能的取值：0和1

由于硬注意力的不连续性，所以硬注意力是不可微的

软注意力机制

将特征输入软注意力网络，就可以得到一系列加权系数，将该加权系数用于原始特征就可以得到加权之后的特征

在训练过程中的梯度的反向传播中与网络的其他部分共同被优化

根据加权对象的不同，软注意力机制可以分为不同的种类

  1. 基于空间域的注意力机制

基于空间域的注意力机制会在特征谱X∈RH×W×C\pmb X\in R^{H\times W\times C}的空间维度刻画上下文关系

  1. 基于通道域的注意力机制

通道注意力的目的是强化图像表征能力更高的特征平面，抑制表征能力更弱的特征平面或者背景信息较为丰富的特征平面

  1. 基于时间域的注意力机制

当不同时间节点上的特征有不同的重要度的时候，就需要使用基于时间域的注意力机制

  1. 基于混合域的注意力机制

有时候注意力机制不单单作用于一个域，而是多个域共同作用，我们把这种注意力机制称为混合域的注意力机制

循环神经网络

卷积神经网络的结构当中，层与层之间是相互连接的，但是层内是无连接的，很难处理有序的数据

而循环神经网络（RNN）可以通过构建层内节点的连接实现对前面信息的记忆，从而输出与当前时刻之前数据相关的输出结果

图神经网络

图神经网络（GNN）是用于处理复杂而不规则的图数据结构的

在数学图论当中，一个图GG由顶点VV和连接这些顶点的边EE组成，是用来表示和建模节点和节点之间的依赖关系的数据结构，可记为

G=(V,E)G = (V,E)

边既可以是有向边，也可以是无向边，有向边代表的是信息传输的方向

参数的计算

模型的计算复杂度直接决定了卷积神经网络的训练/预测时间

我们可以通过一些方法来缩减网络复杂度和模型大小

  1. 网络剪枝
  2. 模型量化
  3. 知识蒸馏

网络优化和经典的卷积神经网络

网络优化算法

深度神经网络的学习需要解决如下两个关键问题

  1. 参数的优化问题：如何稳定快速的求解出使损失函数最小化的网络参数
  2. 模型的泛化能力：如何在网络参数学习过程中避免对数据的过拟合

基于梯度下降的参数优化算法

  1. 朴素梯度下降

我们令J(w)J(\pmb w)为深度神经网络的损失函数，其中w\pmb w为该网络的参数

朴素梯度下降的目标是在参数空间内构建连续的参数序列w1,w2,⋯\pmb w_1,\pmb w_2,\cdots，从而使损失函数满足单调下降J(wt+1)<J(wt)J(\pmb w_{t + 1}) < J(\pmb w_t)，其中tt代表迭代次数，通过迭代更新参数wt\pmb w_t，我们可以获得损失函数的极小值

由于损失函数在梯度方向的增长速率最快，因此我们沿着梯度反方向更新参数，便能够以最快的速度逼近极小值

令gt\pmb g_t表示损失函数在第tt步迭代对参数w\pmb w的梯度，即

gt=∇Jw(wt)\pmb g_t = \nabla J_w(\pmb w_t)

则参数wt+1\pmb w_{t + 1}的迭代更新公式如下

wt+1=wt−ηgt\pmb w_{t + 1} = \pmb w_t - \eta \pmb g_t

其中η≥0\eta \ge 0代表学习率，用以控制参数沿梯度反方向更新的幅度

当η\eta较小的时候，收敛速度会过慢

当η\eta较大的时候，容易导致收敛过程中剧烈震荡，难以收敛

参数更新的停止条件通常采用以下两种

  1. 损失函数的收敛性∣J(wt)−J(wt+1)∣<α|J(\pmb w_t) - J(\pmb w_{t + 1})| < \alpha
  2. 最大迭代步数t>Tt>T

损失函数的计算需要考虑样本的选择方式

假设全部训练样本数目为nn，我们将其中mm个训练样本的平均损失表示如下

J(w)=1m∑i=0mL(y^i,yi)J(\pmb w) = \frac{1}{m}\sum^m_{i = 0}\mathcal L(\hat y_i,y_i)

其中y^i\hat y_i表示预测值，yiy_i表示真实值，L\mathcal L表示两个变量之间的距离测度

当m=nm = n时，称为批量梯度下降（BGD）

当1<m<n1<m<n时，称为小批量梯度下降（MBGD）

当m=1m = 1时，称为随机梯度下降（SGD）

优点：BGD算法的收敛稳定性高；SGD算法的计算速度快；MBGD算法的能够在计算效率和收敛稳定性方面取得较好的均衡

缺点：BGD算法的计算效率低，收敛速度慢，容易陷入局部最小值；SGD算法的损失与训练样本的全局平均损失可能差异较大，导致收敛性较差，可能导致全体训练样本平均损失的上下震荡

  1. 动量法

朴素梯度下降法参数的迭代更新仅考虑了当前的梯度方向，在处理类似峡谷状的曲面时损失函数震荡极易加剧

而动量法是模拟运动物体的动量定理，并要求梯度下降保有原运动方向的趋势，从而加速收敛

vt+1=βvt−ηgt\pmb v_{t + 1} = \beta v_t - \eta\pmb g_t

wt+1=wt+vt+1\pmb w_{t + 1} = \pmb w_t + \pmb v_{t + 1}

其中vt+1\pmb v_{t + 1}为本次参数更新的累计速度，且v0=0\pmb v_0 = 0，−ηgt-\eta\pmb g_t则为朴素梯度下降的更新步长，β\beta为调节历史速度累积的权重，通常取0.9

将上式进行化简可得

wt+1=wt−η∑i=1tβt−igi\pmb w_{t + 1} = \pmb w_t - \eta\sum^t_{i = 1}\beta^{t - i}\pmb g_i

优点：能够在梯度下降的时候抑制震荡，加速收敛

缺点：历史梯度的累计放大了学习率的影响，为学习率的有效设置带来了更大的困难

  1. 自适应矩估计法（ADAM）

朴素梯度下降和动量法无法满足高维向量的不同的更新速率的要求

自适应矩估计法在继承了动量法的优势同时，利用参数向量各元素历史梯度的二阶矩估计其变化速率

其中，二阶矩越大表示该元素更新越频繁，应降低更新步长，反之则增加

优点：计算高效，占用内存少，能够有效处理稀疏的高维梯度向量，参数更新更加平稳

缺点：ADAM算法的更新速率可能在不同迭代过程中剧烈震荡，导致无法收敛或者错过全局最优解

常见的参数初始化方法

  1. 随机初始化

随机初始化通常假设最优参数满足某种特定分布，最为广泛采用的最优分布假设为高斯分布和均匀分布

通过手工设定高斯分布的均值、方差或均匀分布的最小值、最大值，算法就会用指定分布当中随机抽取的数值来初始化网络参数

由于其稳定性差，对于手工设置高度敏感，所以常用于浅层神经网络的初始化

  1. Xavier初始化

对于深度神经网络，由于多层参数累乘的放大效应，太小的初始化参数容易导致神经元或梯度消失，反之则容易造成梯度爆炸

Xavier方法则是约束了网络层在前向传播和反向传播的过程中，输入项和输出项的方差要求一致

满足该限制的数值可以从如下分布当中随机采样获得

U(−6cin+cout,6cin+cout)U\left(-\sqrt{\frac{6}{c_{in} + c_{out} } } , \sqrt{\frac{6}{c_{in} + c_{out} } }\right)

其中cinc_{in}和coutc_{out}分别表示当前层所连接的输入与输出神经元的数目

Xavier初始化方法推导假设网络采用线性激活函数，且神经元响应值基于0对称，故该方法常常和Tanh激活函数联合使用，对ReLUctant与Sigmoid激活函数构建的网络表现欠佳

  1. Kaiming初始化

针对ReLU激活函数造成的负值响应抑制，Kaiming初始化方法假设ReLU的输入以及网络参数满足以0为均值的对称分布，则ReLU输入的二阶矩可表示为前层输出方差的12\displaystyle\frac{1}{2}

满足上述限制的数值可以从如下分布当中随机采样获得

U(−6cin,6cin)U\left(-\sqrt{\frac{6}{c_{in} } },\sqrt{\frac{6}{c_{in} } }\right)

其中cinc_{in}表示当前层与输入连接的神经元数目

  1. 基于预训练的初始化

我们可以构建通用的骨干网络，并在现有的大规模数据集上进行预训练

待模型收敛之后，我们便可以将其参数用于后续新任务的初始化

优点：具有较好的泛化性能，收敛速度快

常见的变量归一化算法

归一化是指通过算法将不同来源的数据统一在指定的区间范围内，能够有效的避免奇异样本数据（即相比于其他的数据过大或者过小）和网络优化过程中带来的梯度消失等问题，进一步提高网络模型的收敛速度以及精度

目前最常见的数据预处理的归一化方法是最小最大值归一化和ZZ值归一化

最小最大值归一化就是把所有的参数都映射到[0,1]之间

另外，在训练深度神经网络时，随着前一层参数的变化，各层内部输入的分布也会随之发生变化，可能降低网络的收敛速度，并使得模型训练变得十分困难，这种现象叫内部协变量漂移

为了有效缓解这种现象，研究者在神经网络当中引入了归一化层，从而使得网络获得更平滑的梯度，更快的收敛速度以及更好的泛化精度

归一化层通常放在卷积层和激活函数之间

  1. 批量归一化

批量归一化就是对输入的每一批数据进行归一化，使其的分布变成标准正态分布

缺点：容易受每个批量样本数据大小的影响

  1. 层归一化

层归一化是对每个样本，依据所有层单独进行归一化

层归一化弥补了批量归一化的缺点，通常被应用于循环神经网络当中

  1. 实例归一化

实例归一化指的是对每个样本特征的单个通道归一化，可以表示为单个通道加单个样本

实例归一化不会受样本数目和通道数目的影响，所以应用范围更广

  1. 分组归一化

分组归一化是指将每个样本特征的通道数分为GG组，对每组的通道之间的神经元归一化，介于层归一化和实例归一化之间

常见的正则化算法

现在主要通过正则化方法来避免网络过拟合，减少测试误差，保证模型的泛化能力

  1. 数据增广法

数据增广法是对原始数据的变换来扩充原始的数据集

  1. L1L_1和L2L_2正则化

依据奥卡姆剃刀原理，它们通过在代价函数当中加入参数惩罚项Ω(w)\Omega(\pmb w)来约束和限制参数过大，避免过拟合

J‾(w,b)=J(w,b)+λΩ(w)\overline J(\pmb w,\pmb b) = J(\pmb w,\pmb b) + \lambda\Omega(\pmb w)

其中J(w,b)J(\pmb w,\pmb b)为原始的代价函数，w\pmb w和b\pmb b对应于神经网络当中的参数权重和偏置，λ\lambda表示正则化系数

这里由于偏置b\pmb b对于网络的影响不大，所以不做约束

通过改变惩罚项Ω(w)\Omega(\pmb w)为L1L_1和L2L_2范数来分别表示L1L_1和L2L_2正则化

L1正则项:Ω(w)=∣∣w∣∣1=∑i∣wi∣L_1正则项:\Omega(\pmb w) = {||\pmb w||}_1 = \sum_i|w_i|

L2正则项:Ω(w)=∣∣w∣∣22=∑iwi2L_2正则项:\Omega(\pmb w) = {||\pmb w||_2^2} = \sum_i\pmb w_i^2

L1L_1和L2L_2正则化会趋向于产生少量的特征，增加网络参数的稀疏性，可以达到特征选择的功能，通常用在压缩模型任务当中

在实践中，除了压缩模型外，其他情况优先选择L2L_2正则化

也可以同时加入L1L_1和L2L_2正则化，即弹性网络正则化

  1. 提前停止法

提前停止法是指在训练集收敛之前就提前停止训练

  1. Dropout法

Dropout法指的是在全连接层之后引入"dropout"，它会以pp的概率随机激活或者设置隐藏层当中的神经元的输出为0

以这种方式设置为0的神经元既不参与网络的前馈，也不参与反向传播

这种技术会迫使神经网络学习更加鲁棒的特征，从而提高模型的泛化能力

  1. 集成学习法

集成学习法指的是结合多个模型降低泛化误差，如Adaboost算法和随机森林

Adaboost算法属于Boosting技术，即集成多个模型来提升网络的容量，增强分类能力

随机森林属于Bagging技术，即在原始数据集有放回的随机抽样出nn个不同的数据集，利用这些数据集分别去训练nn个神经网络模型，最后采用加权法或者投票法对这些模型的输出进行表决，并最终输出结果

通常集成的模型数量大约为5~10个，不能设置太多

经典骨干网络模型

AlexNet

AlexNet是深度卷积网络兴起时较早的代表性网络模型

VGGNet

VGGNet相较于其他网络的创新之处是第一个卷积层使用更小的卷积核，验证表明了一个3 x 3的小卷积核比一个大卷积核更好

VGGNet的不足之处是它的计算消耗比较大，参数过多，对内存有较高要求

GoogLeNet

相比于VGGNet，GoogLeNet提出了Inception模块，将包含不同大小的卷积核的子分支并行的组合在一起，不仅增加了网络的深度，也考虑了网络的宽度，同时减少了网络的参数

在Inception v1的基础上，受VGGNet的启发，研究人员提出了Inception v2，使用两个3 x 3的小卷积核替代5 x 5的大卷积核，从而在不改变感受野的大小的同时减少了参数量

Inception v3的一个重要改进则是利用小型非对称卷积核（1 x k，k x 1）替代大型卷积核（k x k），同时增加了网络的深度，提高了非线性表达力，此外还引入了BN层以及标签平滑技术来防止网络过拟合

Inception v4则将Inception模块和残差模块相结合，提升了网络的收敛速度

ResNet

当网络层数从20层到56层时，模型在训练集和测试集的错误率不仅没有降低，反而有所提高，这一现象被称为网络的”退化“

造成该现象的原因是随着网络层数加深，SGD优化中的误差很难传到浅层，导致优化困难

而残差块由两个分支组成，一个是直接的映射分支，称为残差映射，另一个分支则在原始输入和输出之间增加了一个恒等映射，直接跳过了许多层

这不仅不会增加网络的参数量，而且还能保存原始的输入信息，大大增加了网络的收敛速度，提高了网络的性能

LSTM

长短期记忆网络是一个经典的循环神经网络，该网络一般用于处理长序列数据，可以将先前的信息保留传递到当前的时刻，因此适合处理音频，视频等具有时序性的数据

LSTM容易引入较多的中间信息，使得训练过程中的参数增加，难度加大

目前人们通常采用与LSTM效果相似，但是参数更少的GRU网络来替代LSTM

GRU

GRU网络是LSTM网络的一种变体，它的贡献在于将LSTM当中的三个中间门控换成了两个门控（即重置门控和更新门控），并且其内部只存在隐藏层状态的输入和输出，最终得到了比LSTM网络更加简单的网络结构

Transformer

Transformer网络是由编码器和解码器组成，采用了多个自注意力子模块组合成的多头注意力模块用于捕捉单词间多种维度上的相关性

此外，Transformer的自注意力机制使得模型可以并行化训练，而时序结构的RNN并不具有这种优点

由于Transformer的并行化训练并不能利用原有的词的位置信息，所以需要在输入中额外添加位置编码

GPT-4就是Transformer模型

GAN

GAN即生成式对抗网络，将网络划分为判别器和生成器两部分，通过博弈对抗的思想迭代地训练两个网络，最终实现利用生成器网络生成逼真的伪样本数据

  1. 判别器

对于输入的样本，判别器的任务是对样本的真实性进行判别并打分

当输入为真实样本时，打分为1；当输入为生成器生成的伪样本时，打分为0

  1. 生成器

生成器的任务是不断模拟真实样本的数据分布，尽量生成更加逼真的样本，来“欺骗”判别器