句法分析

自然语言的复杂性

1、乔姆斯基体系

• 非受限文法 –形成递归可枚举语言（可能不可识别）

  剩下三种生成的都是递归语言，句子可以被判定。

• I型文法–上下文有关法 （CSG）可生成：copy语言 NP完全问题

• II 型文法–上下文无关法（CFG）可生成：镜像语言 Polynomial 计算机能够高效计算

• III型文法–正规文法（RG）

自然语言不能用RG生成：存在镜像语言
自然语言不能用CFG生成：存在系列交叉依存现象

自然语言属于上下文有关文法，但接近CFG
需要有高效的上下文无关文法的技术

2、线图：保存森林。保留子串的利器，可以在线图中找到很多词法树。

句法分析经典算法

自底向上线图分析

符号：
dot（O）:表示左边的符号已经都分析完成，右边的还没有分析。
key：当前分析的成分。

1. 如果agenda数据结构为空，扫描当前句子，将扫描到的成分压进agenda
2. 从agenda中弹出成分，进行分析，成分中还有位置信息。
3. 匹配规则
4. 对成分C进行分析：
   • 没有到头的句子成分，分析下一个成分
   • 到头的句子陈分，将它压入agenda

自顶向下Earley线图分析

1. 先产生一定的预期，即从s出发

   

2. 句子来迎合预期，从而达到，通过自顶向下的预期与自底向上的迎合，减少误判以及不合法句子的可能。

3. 所有的非终结符都要往下不断的根据规则展开，直到不能再展开，即对词汇的预期。

对比来看第一张图也就是第二种算法，很多不必要的判断都没有了，提高了算法的效率。

转移网络语法

感觉实质就是自动机
这次自动机里的弧线可以有非终结符，但非终结符也会对应相应的很多自动机

特征系统与扩充语法

主要是处理语法规则问题(?)，例如 a men 这是不合法的句子，但是直接用上面的算法判定则是合法的。因而我们需要为词语添加特征，来生成合法的句子。feature暂时理解为，一个单词是一个节点，是由结构体构成，结构体中有很多属性可以代表单词的feature（这些都放在字典中）。句法分析的时候不仅要匹配基本句子结构，也要判断单词的feature检查。

扩充转移网络

ATN—寄存器

概率性上下无关文法

在有树库的基础上，添加已经计算得到的一些概率。可以求得一棵语法树的概率。沿着概率可以加快生成速度，也可提升准确率。概率+词的个性化 == 更快、更精确的结果。

其他问题

基于机器学习的自然语言处理方法，如果能导入句法分析规则，精确度预计可以提高很多。

nlp相关词汇中英对照

词法及语言模型

词表示

是翻译词中的符号成为机器可以理解的语义的过程。能让计算机理解每个词背后的meaning，实现对词的语义信息的表示。

应用：计算词之间的相似度，发现词之间的关系。

利用近义词和上位词表示的缺陷、利用词典进行词义表示的缺陷：依旧会丧失词义的细节信息；人工编撰的字典更新比较慢，对词汇新的词义很难捕捉到；也会包含一定的人的主观感受；大量的人力

one-hot representation

在计算机里给每一个词赋予一个独一无二的id，利用长度为整个词典的向量进行词表示，除了id位为1，其他位都为0。

最常用的是，对整篇文档进行表示，形成关于文档的高效表示，可以用来计算两个文档之间的相似度。—词袋模型

存在问题： 没有办法表示和衡量任意两个词之间的相似度。词的表示之间的都是正交的。没有办法保留相似度之间的信息，假设每个词都是独立的。

Represent Word by Context

You shell know the word by the company it keeps

词的表示和其所在的上下文有密切的关系。利用一个词的上下文的词来表示这个词。

Co-Occurrence Counts

还是用一个词典长度的vector来表示单词，这里用大量的文本中，出现在这个中心词周围的单词的次数（count-based)，上下文词的分布（distribution）作为表示这个中心词的向量。

window短：获得更多句法信息
window长：获得更多语义信息

• Term-term matrix：词和词之间同线的矩阵

  如下图，生成的矩阵行和列都是单词的长度，eg： i和like在这三句话（语料信息）中同现两次（出现在同一篇文章中），所以组成的矩阵中，matrix[i][like] = 2 （m = 2？）

  

• Term-Document Matrix：词和文章形成的矩阵

  行和列分别是单词和特定文章，每一列可以用该列生成vector表示当前文章。

  

相似度计算方法：（1）计算点积（相同维度相乘再相加） （2）余弦相似度：相当于做了一个归一化，点积除以向量的长度。

问题：（1）向量的size随着词汇量的变大而变大。存储等都是问题（2）低频的词汇，向量很稀疏，计算的精确度下降。

分布式词表示

1、语言模型

做什么：

• 计算一个文字序列，组成语言的概率有多少。
• 知道序列的前半部分，能够预测出下一个字符是什么的概率。

假设：w_n出现的概率，仅有w₁……w_n-1决定。

N-gram Model

因为如果将一个词前面出现的词全部计算来计算其概率，算法复杂度太大。为了解决这一缺陷，会选择限制选择前面词的数量（比如只利用前2-3个词来计算当前位置的词出现的概率）。即某个词条件概率只依赖于其前面有限个词的概率。

问题：（1）因为是近似，所以会存在着不准确性。（2）不能够很好的捕捉词之间的相似性。

Neural Language Model

过程：

1. 每个词用one hot表示组成一个矩阵
2. 通过输入的句子序列，将在一起的两个词vector取出，拼接到一起。
3. 通过一个激发函数
4. 通过一个映射函数(机器学习得到参数矩阵)
5. 通过softmax函数，将值归一化，这样得到的向量里，每一个维度代表着这一维的词是接在后面的可能性的大小。
6. 

loss function:交叉熵

总结：

缺陷：（1）太多的参数 （2）太多的计算

Word2Vec

CBOW: input：上下文 output：w₀预测中心词

Skip-Ggram: input: W₀中心词 output：上下文的词汇

CBOW

用上下文的词来预测中心词

问题： 过于依靠上下文来表示词义，如果两个词上下文相同，就会得到很相似的词向量表示，但可能这两个词并没有那么高的相似度。

skip-gram

中心词预测每一个上下文的词，分别预测其可能的上下文

整体

1. 最复杂的步骤是计算softmax来形成概率向量
2. loss-function也是利用交叉熵，也利用各种优化器来反向传播

问题： softmax的计算非常复杂，每个词都要算

两个改进方法：

• Negative sampling 负例取样

  不是将每个词都计算，而是针对某一个中心词，只取一定量的负例（也就是不正确的其他词）来进行计算，只要保证负例与正例之间的距离足够大就可以。

  

• Hierarchical softmax

  根据单词的频度，组装成哈夫曼树。计算softmax不需要再计算全部，沿着树的路径来算即可，也可以提高效率

第一讲 绪论

1、什么是自然语言处理？

让计算机能够处理并理解自然语言。

2、语言

语言是人与人之间最方便、最自然、最有效的交流通讯工具

语言是知识的载体，语言和人类智能关系密切。

3、经典应用

ACL,EMNLP,CO

Pytorch构建深度学习模型

经典项目

1、图像分类：github.com/floydhub/imagent

2、github.com/amdegroot/ssd.pytorch

3、github.com/ruotianluo/ImageCaptioning.pytorch

4、github.com/allenai/document-qa

5、

……

构建简单的两层网络

词向量

论文：distribution representations of words and phrases and their compositionality

• 词编码需要保证词的相似性

分布式表示：用一个词附近的其他词来表示该词

Word2Vec：skip-gram模型

中心词预测中文词。词向量能够预测周围单词的信息。

Negative sampling 负例采样：因为计算所有的单词关系太困难，所以采用采样的方式，然后我们所希望的是中心词周围正确的单词的分数越高越好，不正确的周围的单词分数越低越好。这是我们的一个训练任务。