自然语言处理期末考试复习

选择题，15道，30分
填空题，5道，10分
判断题，6道，12分
简答题，4道，20分
综合题，2道，18分
程序设计题，1道，10分

1. (单选题)以下哪个算法是无监督信息抽取算法？
   A. CRF
   B. SVM
   C. TextRank
   D. BM25
   正确答案: C

2. (单选题)可以用于计算文档与查询之间的相关性得分的是：
   A. CRF
   B. SVM
   C. TextRank
   D. BM25
   正确答案: D:BM25;

3. (单选题)属于信息提取的一种任务的是：
   A. 文本分类
   B. 机器翻译
   C. 命名实体识别
   D. 语言模型
   正确答案: C

4. (单选题)哪个算法可以用于从文本中自动抽取实体、关系或事件等信息？
   A. CRF
   B. SVM
   C. TextRank
   D. 无监督信息抽取算法
   正确答案: D

5. (单选题)属于一种基于规则的信息抽取方法的是：
   A. CRF
   B. SVM
   C. 基于模式匹配的方法
   D. 基于聚类的方法
   正确答案: C

6. (单选题)可以用于将文本中的实体和关系表示为图，从中抽取出实体之间的关系的是：
   A. CRF
   B. SVM
   C. TextRank
   D. 基于图模型的方法
   正确答案: D

7. 以下哪个选项不是分离超平面的一部分
   A. 特征向量
   B. 阈值
   С. 权重向量
   D. 偏置
   正确答案：A

8. 以下使用感知机的人名性别分类任务中，解释正确的是
   A. 感知机算法只能用于二分类问题。
   B. 人名性别分类问题是一个线性可分问题。
   C. 感知机算法的损失函数是平方损失函数。
   D. 感知机算法使用梯度下降来更新权重向量和偏置。
   正确答案：B

9. 假设我们给定输入样本x，将其分配给了ci, cj;中的一种，以下无关的是
   A.对输入样本×进行词性标注
   B.选择一个合适的分类算法
   C.分类器的训练数据集
   D.评估分类器的性能
   正确答案：A

10. 补全下面程序：
    A. return0 ifx<0 else1
    В. returnx
    C. return np.tanh(x)
    D. return1 ifx>0 else0
    正确答案：A

11. 下面关于线性分类模型不正确的是
    A. 如果激活函数不是线性的，那么决策边界也不会是线性的。
    B. 二维空间中，如果决策边界是直线，该决策边界的模型y( )= wx +wo才是线性模型，但不能被直接用于分类问题。
    C. 只有当y(x)=f(wx + wo)等于一个正数c时才能得到决策边界。
    D. 假设关于参数w是线性的，则称该模型是线性的。
    正确答案：C

TF-IDF

TF-IDF(词频-倒排文档频次) 是信息检索中衡量一个词语重要程度的统计指标。相较于词频，TF-IDF还综合考虑词语的稀有程度。在TF-IDF的计算方法中，一个词语的重要程度不光正比于它在文档中的频次，还反比于有多少文档包含它。包含该词语的文档越多，就越说明它宽泛，越不能体现文档特色。因为考虑整个语料库或文档集合，所以TF_IDF在关键词提取时属于多文档方法。

TF表示词频，指的是某个词在文本中出现的频率。如果一个词在文本中多次出现，那么它的词频较高。

IDF表示逆文档频率，用于衡量一个词的普遍重要性。在语料库中，如果一个词在多个文档中都出现，那么它的IDF较低。而如果一个词只在少数几个文档中出现，那么它的IDF较高。

TF-IDF的计算方法是将一个词的TF值与其IDF值相乘，以便得到一个词的综合重要性分数。公式如下：

$$\begin{array}{rl}TF-IDF(t,d)& =\frac{TF(t,d)}{DF(t)}\\ & =TF(t,d)\ast IDF(t)\end{array}$$

其中，t代表单词，d代表文档，TF(t,d)代表t在d中的出现频次，DF(t)代表有多少篇文档包含t。DF的倒数成为IDF。

切分算法

1. 自然语言处理中的切分算法是将一段文本切分成一个个词语的过程。常用的切分算法有完全切分、正向最长匹配、逆向最长匹配以及双向最长匹配。
2. 完全切分算法是将文本中所有可能的词语都列出来，但是这种方法会导致词语数量爆炸，因此不常用。
3. 正向最长匹配算法是从左到右扫描文本，每次取出最长的词语作为结果。
4. 逆向最长匹配算法是从右到左扫描文本，每次取出最长的词语作为结果。
5. 双向最长匹配算法是结合了正向和逆向两种方法，每次取两种方法中结果数量较少的那一种作为结果。

依存句法分析

1. 依存句法分析是指识别语句中词与词之间的依存关系，并揭示其句法结构。
2. 依存句法分析的结果可以用依存句法树来表示，其中每个节点表示一个词，每条边表示两个词之间的依存关系。
3. 常用的依存句法分析算法有基于转移的算法和基于图的算法。
4. 基于转移的算法是一种自底向上的算法，通过不断移动指针来构建依存树。
5. 基于图的算法是一种自顶向下的算法，通过不断合并节点来构建依存树。

线性分类模型与感知机算法

1. 线性分类模型是一种基于线性假设的分类算法，它将输入的特征和权重进行线性组合，然后使用一个阈值函数来判断分类结果。常见的线性分类模型包括逻辑回归和线性支持向量机（SVM）等。
2. 感知机算法是一种经典的线性二分类算法，它通过不断迭代优化权重参数来划分两个类别的数据点。感知机算法基于感知机模型，其中每个特征的权重与特征的线性组合决定了新样本的分类结果。感知机算法是基于梯度下降法的迭代优化算法。
3. 线性分类模型和感知机算法也有一些局限性，例如对非线性问题的处理能力有限。

基于双数组字典树的AC自动机

基于双数组字典树（Double-Array Trie）的AC自动机是一种用于多模式字符串匹配的高效算法，常用于自然语言处理中的文本分析和关键词匹配任务。

下面是基于双数组字典树的AC自动机的基本步骤：

1. 构建Trie树：将需要匹配的关键词构建成Trie树，每个节点表示一个字符，使用一个数组保存子节点的指针。
2. 计算Fail指针：对Trie树进行遍历，为每个节点计算Fail指针，表示在匹配失败时应跳转的下一个节点。这样可以在匹配过程中遇到不匹配的字符时快速跳转到下一个可能匹配的位置。
3. 构建双数组：将Trie树和Fail指针进行转化，得到双数组，用两个数组实现双向关联，可以在不增加额外空间的情况下高效地存储和查询。
4. 匹配过程：对于待匹配的文本，从头开始，依次匹配字符。根据当前字符和当前节点，根据转移条件找到下一个节点。如果找不到，根据Fail指针跳转到下一个可能匹配的节点。同时检查当前节点是否为一个关键词的结尾，如果是，则表示匹配到一个关键词。

基于双数组字典树的AC自动机具有高效的匹配速度和较小的内存占用，可以在大规模的关键词集合中进行快速匹配。它广泛应用于文本过滤、敏感词过滤、关键词提取等自然语言处理任务中。

以下是一个简单的基于双数组字典树的AC自动机的示例代码：

在示例代码中，首先创建了一个AC自动机对象并调用build_trie方法构建Trie树，然后调用compute_fail方法计算Fail指针。接下来，通过调用match方法可以对文本进行关键词匹配，并返回匹配结果。

Arc-Eager转移系统

Arc-Eager转移系统是自然语言处理中用于依存句法分析的一种常见转移系统。它是一种基于转移动作的句法分析方法，通过一系列转移操作来构建句子的依存树结构。

Arc-Eager转移系统的核心操作包括以下几种：

1. Shift：将当前分析的词移到栈顶，将输入中的下一个词移入缓冲区。
2. Reduce：从栈顶弹出一个词，表示该词已经完成分析。
3. Left-Arc：建立一条从栈顶词指向下一个词的依存弧，然后将下一个词移入栈顶。
4. Right-Arc：建立一条从下一个词指向栈顶词的依存弧，然后从栈顶弹出词。

Arc-Eager转移系统的基本思路是通过Shift、Reduce、Left-Arc和Right-Arc这些转移动作，逐步构建句子的依存结构。在依存分析开始时，句子中的词会依次进入缓冲区，并且栈初始为空。

通过不断执行转移动作，直到分析完成，即缓冲区和栈同时为空，或者达到某个终止条件。

Arc-Eager转移系统的优点之一是能够有效地处理左依存和右依存的关系，因此在实际应用中得到广泛应用。同时，基于转移的句法分析方法还可以与其他技术（如特征模板和学习算法）结合，进一步提升依存分析的性能。

TextRank 算法

TextRank算法是一种基于图的文本摘要和关键词提取算法，它通过分析文本中词语之间的关系来确定重要的句子或关键词。

Textrank算法将文本中的词语看作图中的节点，将它们之间的关联看作边，通过PageRank算法进行迭代计算，得到每个节点的权重。 Text rank 算法 考虑了文本中单词之间的关联性，因此能更准确地评估单词的重要程度。

具体来说，TextRank算法包括以下步骤：

1. 分词和词性标注：对文本进行分词，并标注每个词语的词性。
2. 构建图模型：根据分词结果，构建一个无向图，其中每个节点代表一个句子或一个词语，边的权重表示节点之间的关系。通常可以使用共现关系、语义关系等来确定边的权重。
3. 迭代计算节点重要性：通过迭代计算，按照一定的更新规则，更新每个节点的重要性分数。更新规则可以基于PageRank算法进行定义，即节点的重要性由其相邻节点的重要性确定。
4. 根据节点重要性排序：根据节点的重要性分数，对句子或词语进行排序，从而确定重要的句子或关键词。

需要注意的是，TextRank算法是一种无监督学习方法，对文本的预处理和参数的设置都会对算法的效果产生一定影响，因此在实际应用中需要根据具体任务和数据集的特点进行调整和优化。

维特比算法（不用纠结计算问题)

基本思想是利用动态规划，从左到右递推地计算每个时刻最优路径的概率和对应的前驱状态，然后从右到左回溯地找出最优路径。Viterbi算法的具体步骤如下：

1. 初始化：计算时刻1各个隐藏状态的最优路径概率和前驱状态
2. 递推：对于时刻t=2,3,…,T，计算时刻t各个隐藏状态的最优路径概率和前驱状态
3. 终止：计算最优路径的终点和概率
4. 回溯：根据终点和前驱状态，从右到左找出最优路径

齐夫定律

齐夫定律用于描述自然语言中词频与排名的关系。

齐夫定律指出，对于自然语言中的词汇表，词频和词的排名（按照频率从高到低进行排序）之间存在着一种反比关系。具体来说，如果将词频从大到小排列，并将其对应的排名从1开始标注，那么排名为n的词的出现频次约等于1/n，或者说频次和排名之间大致满足一个指数函数关系。

齐夫定律在自然语言处理中有广泛应用。例如，在文本处理任务中，可以根据齐夫定律对词频进行统计和分析，识别出高频词、低频词以及词频分布的稀疏性等特征。这对于词汇表的特征选择、文本分类、信息检索等任务都具有一定的指导意义。

需要注意的是，齐夫定律是一种经验规律，并不适用于所有的自然语言文本。在某些特殊情况下，词频与排名之间可能存在一定的偏离。因此，在具体应用中，需要根据具体问题和数据集的特点进行分析和调整。

Word2vec主要包含两个浅层的神经网络模型，分别是？

CBOW模型和Skip-gram模型。

最常见的句法分析任务？

最常见的句法分析任务是依存句法分析。依存句法分析旨在分析句子的语法结构，并表示单词之间的依存关系。它通过构建一个依存关系树来形式化句子的结构，其中每个单词作为一个节点，而依存关系则由边连接起来，表示单词之间的依存关系。

在依存句法分析中，通常需要确定每个单词的依存头（head）以及头与子节点之间的依存关系标签。依存头指的是某个单词在句法分析中依赖的单词，而依存关系标签则描述了头与子节点之间的语法关系，如主谓关系、定中关系、状语关系等。

依存句法分析在自然语言处理中有广泛的应用，包括句法解析、语法错误检测、机器翻译、问答系统等。通过深入理解句子的语法结构，依存句法分析有助于提取句子中的信息，更准确地理解和处理自然语言文本。

AC自动机

AC自动机（Aho-Corasick Automaton）是一种高效的多模式串匹配算法，在自然语言处理中常用于快速查找文本中的多个关键词或模式串。

AC自动机的主要思想是将需要匹配的模式串构建成一个有限状态自动机。该自动机由多个状态和状态之间的转移边组成，其中每个状态代表当前已匹配的模式串的前缀。构建AC自动机的过程涉及两个主要步骤：

1. 构建Trie树：根据模式串集合构建一个Trie树（字典树），其中每个节点代表一个字符，路径代表字符之间的连接。Trie树的结构允许在文本中进行高效的模式匹配。
2. 添加转移边：根据Trie树的结构，为每个节点添加转移边。转移边指示了在当前状态下，如果匹配下一个字符，则应转移到哪个状态。

在匹配过程中，AC自动机根据输入文本逐个字符进行状态转移。当达到某个状态时，表示已匹配到一个模式串的前缀。同时，可以通过在每个状态上存储额外的信息，如模式串的编号、出现的位置等。

相比于传统串匹配算法，AC自动机的优势在于避免了大量的重复比较和回溯操作，从而提高了匹配的效率。在自然语言处理中，AC自动机可以应用于分词、实体识别、敏感词过滤等任务中，实现对大规模模式串的高效匹配。

K-means 算法

K-means算法是一种常用的聚类算法，用于将数据点划分成K个不同的簇群。在自然语言处理中，K-means算法可以用于文本聚类、文本分类等任务。

K-means算法的基本思想是通过迭代优化的方式，将数据点划分到K个簇中，使得同一簇内的数据点相似度较高，不同簇之间的数据点相似度较低。算法的步骤如下：

1. 随机选择K个初始簇中心（可以是随机选取或根据启发式方法选择）。
2. 对每个数据点，计算其到各个簇中心的距离，并将数据点分配给距离最近的簇。
3. 根据当前分配的簇，更新每个簇的中心点，将簇中所有数据点的均值作为新的中心点。
4. 重复步骤2和步骤3，直到达到停止条件（如达到最大迭代次数或中心点的变化小于设定阈值）。

对于自然语言处理中的文本数据，通常需要进行向量表示，如使用词向量（Word Embedding）表示文本，然后基于这些向量进行K-means聚类。通过K-means算法，可以将相似的文本划分为同一簇，从而实现文本的自动聚类和分类。

需要注意的是，K-means算法对初始中心点的选择较为敏感，不同的初始点可能导致不同的聚类结果。同时，K-means算法也有一些限制，如对离群点敏感，对簇形状的约束较强等。因此，在使用K-means算法时，需要综合考虑数据特点和实际任务需求，选择合适的K值和初始点，适当调整算法参数，以获得较好的聚类效果。

隐马尔可夫模型存在哪些问题，以及算法流程

以下是HMM存在的问题：

1. 信息损失：HMM假设当前状态只依赖于前一个状态，而忽略了其他相关信息。这可能导致对序列中的某些重要特征的丢失。
2. 长期依赖：HMM不能很好地处理长期依赖，即序列中当前状态与较远的过去状态相关联的情况。
3. 参数估计：在HMM中，参数的估计有时很困难。尤其是当模型中的状态和观测空间较大时，参数估计变得更加复杂。
4. 模型选择：选择适当的状态数和观测空间大小也是HMM的一个挑战。选择大小不当可能导致模型不准确或过于复杂。

下面是HMM的算法流程：

前向算法：用于计算给定模型参数和观测序列，观测序列出现的概率。前向算法的基本思想是利用动态规划，从左到右递推地计算每个时刻的前向概率，即在时刻t观测到ot并且处于状态si的概率。前向算法的具体步骤如下：

1. 初始化：计算时刻1各个隐藏状态的前向概率
2. 递推：对于时刻t=2,3,…,T，计算时刻t+1各个隐藏状态的前向概率
3. 终止：计算观测序列出现的概率

后向算法：用于计算给定模型参数和观测序列，在时刻t处于状态si的条件下，从时刻t+1到T的部分观测序列出现的概率。后向算法的基本思想也是利用动态规划，从右到左递推地计算每个时刻的后向概率，即在时刻t处于状态si的条件下，从时刻t+1到T的部分观测序列出现的概率。后向算法的具体步骤如下:

1. 初始化：计算时刻T各个隐藏状态的后向概率。
2. 递推：对于时刻t=T-1,T-2,…,1，计算时刻t各个隐藏状态的后向概率。
3. 终止：计算观测序列出现的概率。

维特比算法：上文有，略。

词向量

1. 词向量是连接传统机器学习与深度学习的桥梁；词向量的目标是使得具有相似含义的单词在向量空间中的距离更近。这样，我们可以通过计算向量之间的距离或相似度来判断单词之间的关系和相似程度。Word2Vec利用神经网络的训练过程，将单词映射到连续向量空间，并且在向量空间中保留了一定的语义信息。
2. Word2Vec：Word2Vec是一种通过训练神经网络模型来生成词向量的方法。它有两种主要的实现方式：CBOW和Skip-gram。
   • CBOW模型根据周围的上下文单词预测目标单词。
   • Skip-gram模型则根据目标单词来预测周围的上下文单词。

互信息的计算问题

详情见书本 P273

$$I(x,y)={\log }_2\frac{p(x,y)}{p(x)p(y)}$$

二元语法模型下的概率计算

详情见书本 P95

p(商品 和 服务) = p(商品｜BOS) * p(和｜商品) * p(服务｜和) * p(EOS ｜ 服务)