编译原理 什么是语义分析

在编译原理中，语法规则和词法规则不同之处在于：规则主要识别单词,而语法主要识别多个单词组成的句子。词法分析和词法分析程序：词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。语法分析（Syntax analysis或Parsing）和语法分析程序（Parser） 语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等语法分析程序判断源程序在结构上是否正确源程序的结构由上下文无关文法描述语义分析（Syntax analysis） 语义分析是编译过程的一个逻辑阶段 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配

潜在语义分析（Latent Semantic Analysis,LSA）是一种无监督学习方法，主要用于分本的话题分析，其特点是 通过矩阵分解发现文本与单词之间的基于话题的语义关系。

文本信息处理的一个核心问题是 对文本的语义内容进行表示，并进行文本之间的语义相似度计算。 最简单的方法是利用向量空间模型（Vector Space Model,VSM）。向量空间模型的基本想法是，给定一个文本，用一个向量表示该文本的“语义”，向量的每一维对应一个单词，其数值为该单词在该文本中出现的频数或权值。 这里的基本假设是文本中所有单词的出现情况表示了文本的语义内容。 向量空间的度量，如内积或标准化内积表示文本之间的“语义相似度”。

严格定义如下：给出一个含有 个文本的集合 以及在所有文本中出现的 个单词的集合 。将单词在文本中出现的数据用一个 单词-文本矩阵 表示，记作 ：

表示单词 在文本 中出现的频数或权值。这是一个稀疏矩阵。

权值常用 单词频率-逆文本频率（term frequency-inverse document frequency,TF-IDF） 表示，其定义是：

其中 是单词 出现在文本 中的频数， 是文本 中出现的所有单词的频数之和， 是含有单词 的文本数， 是文本集合 的全部文本数。

这个概念的解释我在读吴军先生的《数学之美》时见过，至今记忆犹新。举例来说，很多单词在所有文本中出现频率都很高（比如I，is，are，and）但它们并不能代表文本的语义，因为这些单词在所有文本中都出现，因此它们并不能代表文本的特点。这就是不能直接使用单词频率的原因。为了度量一个单词能多大程度地反映文本的特点，可以使用逆文本频率，即 一个单词在整个文本集合中出现的文本越少，这个单词越能表示其所在文本的特点，重要度越高。 这就是逆文本频率的含义。综合逆文本频率（度量单词多大程度反映文本特点）以及单词频率（度量单词对文本的重要性）就得到了 TF-IDF 。

两个单词向量的内积或标准化内积（余弦）表示对应文本之间的语义相似度，文本 与 之间的相似度为：

VSM的优点是模型简单，计算效率高，因此单词向量通常是稀疏的，两个向量的内积计算只需要在同不为零的维度上进行即可。但VSM也有一定局限性，那就是有时内积相似度未必能准确表达两个文本的语义相似度，因为单词具有一词多义性（polysemy）和多词一义性（synonymy），所以基于单词向量的相似度计算存在不精确的问题。

所谓话题（topic），并没有严格定义，就是指文本讨论的内容和主题。一个文本一般含有若干话题。

单词-文本矩阵 定义同上，记为 。

另外我们定义 单词-话题矩阵 ，记作 ：

矩阵 也可以写作 （ 为所有文本的话题数）。

其中 表示单词 在话题 的权值， ，权值越大，该单词在该话题中重要度越高。这 个话题向量 张成一个话题向量空间，维数为 。

接下来我们定义 话题-文本矩阵 ：

矩阵 也可以写作 。

其中 表示话题 在文本 的权值， ，权值越大，该话题在该文本中重要度越高。

这样一来， 在单词向量空间的文本向量 可以通过它在话题空间中的向量 近似表示，具体地由 个话题向量以 为系数的线性组合近似表示：

表示单词在文本 的权值， 表示话题 在文本 的权值， 表示单词在话题 的权值。即：

这就是潜在语义分析。

进行潜在语义分析，需要同时决定两部分内容——单词-话题矩阵 和话题-文本矩阵 ，使两者乘积是原始矩阵数据的近似。这一结果完全从单词-文本矩阵 中获得。

潜在语义分析的思路是对单词-文本 矩阵进行奇异值分解，将其左矩阵作为单词-话题矩阵 ，将其对角矩阵和右矩阵的乘积作为话题-文本矩阵 。

具体来说，潜在语义分析根据固定的话题个数 对单词-文本矩阵 进行截断奇异值分解：

是 矩阵，它的列由 的前 个互相正交的左奇异向量组成， 是 阶对角阵，对角元素为前 个最大奇异值， 是 矩阵，它的列由 的前 个互相正交的右奇异向量组成。

从而 为单词-话题矩阵 （话题空间）， 为话题-文本矩阵 （文本在话题空间的表示）。

若一个矩阵所有元素非负，则称该矩阵为非负矩阵，若矩阵 非负，记为 。

给定非负矩阵 ，找到两个非负矩阵 和 ：

称为矩阵 的非负矩阵分解。

假设非负矩阵 是一个 矩阵，非负矩阵 和 分别为 矩阵和 矩阵。假设 ，即 和 小于原矩阵 ，所以非负矩阵分解是对原数据的压缩。

非负矩阵分解可形式化为最优化问题来求解。首先定义损失函数。

第一种是平方损失，两非负矩阵 和 的平方损失函数为：

第二种是散度，两非负矩阵 和 的散度损失函数为：

接着定义最优化问题：

或者：

使用梯度下降法求解得到的 可分别作为话题矩阵和文本表示矩阵。

---