语法分析

通过 ANTLR4 生成语法分析器

此处我们研究一个名为 Cymbol 的语言，是 C 语言的子集（代码附后）：

这样的文法有几个问题：

• 二义性：一段程序可以有多种解释方法。

  1 2 3 4

  stat: 'if' expr 'then' stat | 'if' expr 'then' stat 'else' stat | expr ;

  假设此时有这样的程序：if a then if b then c else d，会出现二义性：

  • if a then if b then c else d；
  • if a then if b then c else d。

  这种语法歧义被称为“悬空的 else”。

  如何修改这样有二义性的文法？

  我们将文法修改为：

  1 2 3 4 5 6 7 8 9

  stat: matched_stat | open stat ; matched_stat: 'if' expr 'then' matched_stat 'else' matched_stat | expr ; open_stat: 'if' expr 'then' stat | 'if' expr 'then' matched_stat 'else' open_stat ;

  改造后的文法实现了第一种解释。

  为什么？

  • 证明改造前后接受的语句集合是相同的；
  • 证明改造后的文法无二义性。

  证明留做习题（

  但是注意到，通过 ANTLR4 测试改造前的文法，发现同样实现的是第一种解释，并无二义性。原因是 ANTLR4 会按照从上向下的顺序分配优先级，越往上的优先级越高，所以这种实现也是正确的。

• 运算符的结合性带来的二义性：

  1 2 3 4

  expr: expr '*' expr | expr '-' expr | DIGIT ;

  对于此文法，1-2-3 会被解释为 (1-2)-3 或 1-(2-3)：

  

  在 ANTLR4 中，如果未明确运算符是左结合还是右结合，默认左结合，即上述表达式被解释为 (1-2)-3。

  如果想指定右结合，可以在语句前加入 <assoc = right>，如：

  1 2 3 4

  expr: '!' expr | <assoc = right> expr '^' expr | DIGIT ;

  考虑前缀运算符，这东西不带来歧义，只有一种解析方式，即右结合；后缀运算符只能左结合。

• 运算符的优先级带来的二义性：

  1 2 3 4

  expr: expr '*' expr | expr '-' expr | DIGIT ;

  当一个运算符优先级更高时，在解析树中的深度会更深。在 ANTLR4 中这样写已经可以处理优先级的问题，因为写在前面的优先级更高。

  如果不得已非要处理这种情况，可以通过两种方法：

  • 改为左递归（左结合）：

    1 2 3 4 5 6 7 8 9

    expr: expr '-' term | term ; term: term '*' factor | factor ; factor: DIGIT;

    如此，对于一个语法单元 expr，只会被左侧的 expr 调用递归，这被称为左递归文法，这样限制了文法只能被左结合的方式进行解释。

    由于乘号优先级更高，所以要把乘号放在右侧，等待 expr 被解释完成后再进行解释。

    左递归文法：e -> e - t -> e - t - t -> ...

  • 改为右递归：

    1 2 3 4 5 6 7

    expr: term expr_prime; expr_prime: '-' term expr_prime; term: factor term_prime; term_prime: '*' factor term_prime; factor: DIGIT;

    expr 表示的内容依然为 term-term-term-...，不同的是，通过引入新的语法单元 prime，expr 生成的方式为先生成一个 term，再不断生成 -term 序列，这样就是右递归文法了。

    右递归文法：e -> tEP -> t - tEP -> t - t - tEP -> ...

生成函数调用图

函数调用图表示的是函数之间的调用关系。

获取函数名有两个时机：

• 在进入 functionDecl 时，可以获得当前进入的函数名；
• 在遇到 functionCall 时，即找到一个 expr 表示的是 ID '(' exprList? ')' 时，我们就可以得到被调用函数的函数名（即 ID）。

只要在图中将这两个函数名连边即可。

词法分析

我们令 id 表示以字母开头的包含字母、数字的字符串，id 定义了一个集合，称之为语言（Language）。

id 中使用了字母、数字等符号集合，称之为字母表（Alphabet）。

语言中的每个元素（标识符）称为串（String）。

字母表 $\Sigma$ 是一个有限的符号集合。

字母表 $\Sigma$ 上的串（$s$）是由 $\Sigma$ 中的符号组成的一个有穷序列。$\epsilon$ 表示空串，其长度 $|\epsilon| = 0$。

在两个串 $x$ 和 $y$ 上可以做连接运算 $xy$，例如：$x=\text{dog}, y = \text{house} \rightarrow xy=\text{doghouse}$。特殊的，$s\epsilon = \epsilon s = s$。

由连接运算可以定义指数运算 $s^i$：

$$\begin{aligned} s^0 &\triangleq \epsilon \\ s^i &\triangleq ss^{i-1}, i>0 \end{aligned}$$

意为自连接 $i$ 次。

语言是给定字母表 $\Sigma$ 上一个任意的可数的串集合。当集合中没有串时，称为空语言 $\varnothing$。

基础图论

基本定义

约定

约定 $G = (V, E)$ 表示点集为 $V$，边集为 $E$ 的图，若无特殊说明，则 $|V| = n$，$|E| = m$。

若干基本定义：

• 边导出子图：选出若干条边，以及这些边所连接的所有顶点组成的图称为边导出子图；
• 点导出子图：选出若干个点，以及两端都在该点集的所有边组成的图称为点导出子图；
• 闭合子图：点集 $V$ 导出的闭合子图是所有 $V$ 可达的点的点导出子图，即：若 $x$ 在子图内，则 $x$ 的所有出边和出点均在子图内的原图子图；等价于每个点能到的所有点都在子图中；
• $k$ 正则图：若一个无向图每个点的度数均为 $k$，则称其为 $k$ 正则图。

DFS 树

当 dfs 一个图时，按照 dfs 的顺序可以构造出一个树结构，被称为 DFS 树。

有向图的 dfs 树主要有四种边：

• 树边：每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
• 反祖边：也叫回边，即指向祖先结点的边。
• 横叉边：在 dfs 树中从一个子树中的结点指向另一个子树中的结点的边，即除了其余三种边的边，表示遇到了一个已经访问过的结点，但这个结点并不是它的祖先。
• 前向边：在 dfs 树中从一个深度小的结点指向一个深度大的结点的边，不包括树边，表示遇到了子树中的结点。

SVM

在线性分类器中，我们知道，线性分类器的任务就是在样本空间中寻找一个超平面，将不同类别的样本分开。但是，对于特定的样本空间，我们可能能够找到很多的超平面都满足条件，那么哪个超平面是最好的呢？

直觉上，我们认为“正中间”的是最好的，它离两类样本都比较远，拥有较好的鲁棒性和泛化能力。

我们已经知道，超平面的方程为 $\boldsymbol{w}^\mathrm T\boldsymbol{x}+b=0$，为了找到“正中间”的超平面，我们要找出两类样本中距离超平面最近的那一个，计算出二者的距离，再将超平面放在中间。

两类样本中距离超平面最近的那个样本直接定义了这个超平面，我们把这几个样本称为“支持向量”：

则两个支持向量之间的距离被称做“间隔”，为

$$\gamma = \dfrac 2{\|\boldsymbol{w}\|}$$

卷积神经网络

卷积神经网络（CNN）是一个专门用于图像处理的神经网络。

从图像分类说起

下面的讨论都是基于假设所有图像的尺寸是固定的，不会突然出现大小不一致的图片。

图像识别模型的输入是一张图片，输出是一个独热（one-hot）的向量 $\hat y$，只有模型认为最有可能的类别为 1，其余都为 0。这个向量的长度表示着当前模型能识别出的种类数目。模型在输出独热向量之前，会先通过 Softmax 输出一个向量 $y'$，我们希望 $y'$ 和 $\hat y$ 的交叉熵尽可能地小。

对于输入，人眼看到的是一张三维的图像，计算机看到的是什么呢？计算机看到的是一个三维的张量（粗略的认为是维度大于 2 的矩阵），一维代表图片的宽，一维代表图片的高，另一维代表这张图片通道的个数，当给定一张彩色图片时，图片通道数为 3，分别表示 R、G 和 B。

当我们把一张图片“拉直”成一个向量之后，就可以放到神经网络中让它进行识别分类了。

目前为止，我们只学到了全连接神经网络，如果输入是一个 $100\times100\times3$ 的向量，第二层的神经元有 1000 个，那么将会有 $3 \times 10^7$ 个权重，这是一个非常巨大的数，计算过程会非常缓慢，同时过拟合的风险也会增加。

考虑图像识别的特性，我们并不需要每一个神经元和输入的每一维都有一个权重，即全连接是不必要的。

Softmax Regression

简介

Softmax 回归模型属于有监督学习，是逻辑回归模型在多分类问题上的推广，其类标签 $y$ 可以取两个以上的值。

由于我们要解决的是多分类问题，类标签 $y$ 可以取 $k$ 个不同的值，因此对于训练集 $\left\{(x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \dots, (x^{(m)}, y^{(m)})\right\}$，我们有 $y^{(i)} \in \left\{1, 2, \dots, k\right\}$。

对于给定的测试输入 $x$，我们希望用假设函数针对每一个类别 $j$ 都估算出一个概率值 $p(y = j \mid x)$，表示 $x$ 数据第 $j$ 类的概率。因此，我们的假设函数将要输出一个 $k$ 维的向量（向量元素的和为 1）来表示这 $k$ 个估计的概率值。

假设函数 $h_\theta(x)$ 形式如下：

$$h_\theta\left(x^{(i)}\right) = \begin{bmatrix} p(y^{(i)}=1 \mid x^{(i)};\theta \\ p(y^{(i)}=2 \mid x^{(i)};\theta \\ \vdots \\ p(y^{(i)}=k \mid x^{(i)};\theta) \end{bmatrix} = \dfrac{1}{\sum_{j=1}^k e^{\theta_j^\mathrm Tx^{(i)}}} \begin{bmatrix} e^{\theta_1^\mathrm Tx^{(i)}} \\ e^{\theta_2^\mathrm Tx^{(i)}} \\ \vdots \\ e^{\theta_k^\mathrm Tx^{(i)}} \end{bmatrix}$$

其中 $\theta_1, \theta_2, \cdots, \theta_k \in \mathbb{R}^{n+1}$ 是模型的参数，$\dfrac{1}{\sum_{j=1}^k e^{\theta_j^\mathrm Tx^{(i)}}}$ 是为了将所有的概率分布进行归一化，使所有概率之和为 1。

为了方便起见，我们令

$$\boldsymbol{\theta} = \begin{bmatrix} \theta_1^\mathrm T \\ \theta_2^\mathrm T \\ \vdots \\ \theta_k^\mathrm T \end{bmatrix}_{k \times (n + 1)}$$

稀疏自编码器

自编码器

传统反向传播神经网络缺点：

• 梯度越来越稀疏（梯度弥散）：从顶层越往下，误差校正信号越来越小；
• 容易收敛到局部最小值，尤其是从远离最优区域开始的时候（将参数初始化为随机值会导致这种情况发生）；
• 只能进行有监督训练，但大部分的数据是没有标签的，而人类的大脑可以从没有标签的数据中学习。

1986 年，Rumelhart 提出了自动编码器的概念，并将其用于高维复杂数据的处理，促进了神经网络的发展。自编码神经网络是一种无监督（自监督）学习算法，它使用了反向传播算法，并让目标值等于输入值，即自编码神经网络尝试学习一个 $h_{W, b}(x) \approx x$ 的函数。

自编码器分类：

• 浅层自编码（Autoencoder）
• 稀疏自编码（Sparse Autoencoder）
• 栈式自编码（Stacked Autoencoder）
• 去噪自编码（Denoising Autoencoder）
• 变分自编码（Variational Autoencoder）

自编码器的共同点：学习一个与输入相同的输出，并尽可能的让其具有较强的泛化能力。

自编码器的构成：

降维和特征选择

KNN

KNN 是一种常用的监督学习方法。其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的 $k$ 个训练样本，基于这 $k$ 个邻居的信息进行预测。

通常，在分类任务中可以使用“投票法”，即选择这 $k$ 个样本中出现次数最多的类别标记为预测结果（朴素方法直接寻找出现次数最多，值域过大可以考虑离散化，可以考虑摩尔投票法）；在回归任务中可使用“平均法”，即将这 $k$ 个样本的实值输出标记的平均值作为预测结果；还可以基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

KNN 算法的学习有一个与其他算法明显不同之处：它没有显式的学习过程，这被称为懒惰学习。此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。

与之相对的是急切学习，此类学习技术在训练阶段就对样本进行学习处理。

KNN 分类器中的超参数 $k$ 是一个重要参数，当 $k$ 取不同值时，分类结果会有显著不同。

另一方面，若采用不同的距离计算方式，则找出的“近邻”可能有显著差别，从而也会导致分类结果有显著不同。

下面对最近邻分类器（1NN，即 $k=1$）在二分类问题上的性能做一个简单的讨论。

聚类分析

介绍

在无监督学习中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。此类学习任务中研究最多、应用最广的是“聚类”（clustering）。

常见的无监督学习任务还有密度估计、异常检测等。

聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称作一个“簇”。

形式化地，假定样本集 $D = \left\{\boldsymbol{x}_1,\boldsymbol{x}_2, \dots,\boldsymbol{x}_m\right\}$ 包含 $m$ 个无标记样本，每个样本 $\boldsymbol{x}_i = \left(x_{i1};x_{i2};\dots;x_{in}\right)$ 是一个 $n$ 维特征向量，则聚类算法将样本集 $D$ 划分为若干个不相交的簇 $\left\{C_l \mid l = 1, 2, \dots, k\right\}$，其中 $C_{l'} \bigcap_{l' \neq l} C_l = \varnothing$ 且 $D = \bigcup_{l=1}^{k}{C_l}$。

令 $\lambda_j \in \left\{1, 2,\dots, k\right\}$ 表示样本 $\mathbf{x}_j$ 的簇标记，即 $\mathbf{x}_j \in \lambda_j$，则聚类的结果可用包含 $m$ 个元素的簇标记向量 $\vec\lambda = \left(\lambda_1; \lambda_2;\dots;\lambda_k\right)$ 表示。

对于聚类的结果，我们希望“簇内相似度”高，而“簇间相似度”低。下面是一些常用的聚类性能度量的内部指标：

• DB 指数：

支持向量机

支持向量机（support vector machines）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，它在学习复杂的非线性方程时能提供一种更加清晰和强大的方法。

在 Logistic 回归中，如果要令 $y = 1$，则有 $h_\theta(x) = \dfrac{1}{1+e^{-\theta^Tx}} \approx 1$，即 $\theta^Tx \gg 0$；当 $y=0$ 时有 $h_\theta(x)\approx 0$，即 $\theta^Tx\ll 0$。

对于 Logistic 回归，其代价函数为

$$-(y\log h_\theta(x) + (1 - y) \log (1 - h_\theta(x)))$$

将 $h_\theta(x)$ 代入上述函数得

$$-y\log\dfrac 1{1+e^{-\theta^Tx}} - (1-y) \log (1 - \dfrac 1{1+e^{-\theta^Tx}})$$

当 $y = 1$ 时，代价函数变为 $-\log \dfrac1{1+e^{-z}}$，此时令 $z \to +\infty$，代价函数将会趋近于 0，这也是为什么在看见 $y = 1$ 这样的样本时，会将 $z$ 赋值为一个极大值；类似地，当看见 $y = 0$ 这样的样本时，会将 $z$ 赋值为一个极小值。

在 Logistic 回归中，我们的代价函数 $J(\theta)$ 为

$$J(\theta) = \min_{\theta}\dfrac 1m\left[\sum\limits_{i = 1}^my^{(i)}\left(-\log h_{\theta}(x^{(i)})\right) + (1 - y^{(i)})\left(-\log (1 - h_\theta(x^{(i)}))\right)\right] + \dfrac{\lambda}{2m}\sum\limits_{j = 1}^n \theta_j^2$$