句法分析

自然语言的复杂性

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

Sequence Labeling Problem

以下都是以POS问题（词性标注问题）为例

HMM（隐马尔科夫模型）

假设：
产生句子分为两个步骤：

• 产生一个POS的序列，基于大脑中的语法。
• 根据POS序列的tag，找到对应词性的单词，对应方式是基于词典
• ->形成一句话

概况

Step 1: 根据马尔科夫链，计算产生相应POS的几率
step 2：基于相应的pos序列，在指定位置上配上某一单词的几率，将整句话组成的序列相乘，也就得到了在该pos序列条件下，生成这句话的几率。

基于以上两个步骤，利用条件概率公式，可以计算出X：句子序列，Y：词性序列，两者相匹配的几率。下图是一个例子：

更一般化的描述：

其中的各种几率根据training data可以统计得到

计算方式
已知x，想要求的Y，实际上就是通过穷举所有的Y，找到让P(x,y)最大的Y的过程。
直接通过暴力枚举的话算法的复杂的非常大，借助viterbi algorithm可以将复杂度大幅度降低，提高效率(一般复杂度为O(L|S|²),L为序列长度，S为词性元素)

Summary

根据结构化学习的方式，HMM解决了对应的三个问题。

存在的问题

HMM“脑补”问题：

由于HMM假设了Transition probability 和 Emission probability之间是相互独立的，得到的计算公式P(x,y)体现了这一点，两个可能性单独通过训练集进行训练。所以可能会出现HMM根据公式自主创造新序列的可能性。

这个问题有好有坏：

• 不好的地方：正确的序列的P(x,y)值可能反而小于错误的P(x,y)值
• 好的地方：当数据集数据很少的时候，通过脑补反而会有比较好的表现

CRF 条件随机场

• P(x,y)是与一个 exp(W*feature(x,y))正相关的
• HMM与CRF的本质是一样的

HMM到CRF的转换

• 将p(x,y)取log值，化乘为加
  

• 所有形如下图左边的求和表达式条件概率，都可以表示成右边的形式
  

• HMM的P(x,y)表达式取log值后，可以划分为四个部分：

  • 词性Y1作为句子开头的概率的log值
  • 词性yi+1在yi后面出现的概率的log值（由1-（L-1)求和)
  • 词性yL在句子末尾的概率的log值
  • 实际单词xi对应词性yi的概率的log值（由1-L求和）
    

• 最后的结果，可以表示成两个向量做内积，其中紫色部分为w,红色部分为feature(x,y)。
  

• w中的每一维是可以和相应的概率进行对应，但是由于不能保证W最后结果的每一维都小于1，而概率不能大于1，所以以正相关描述两者关系。

Feature vector的组成

• part1：tags和words之间的关系
  类似于一个邻接矩阵，矩阵形成所有的（tag，word）对，记录的值是该对在句子中出现的次数。
• part2：tag与tag之间的关系（tag：词性+start+end组成的集合）
  同样类似于邻接矩阵，所有的（tag，tag）对一一配对，形成矩阵。（tag1，tag2）指的是tag2出现在tag1之后的情况。还是记录次数。
• 其实feature(x,y)可以自己定义。

Training

如图所示
正如一般的结构化学习，在训练CRF的时候，我们希望可以定义一个函数，这里是O(w)，找到的W，是可以在数据是正确的(x,y)对时，另这个O(w)最大化的函数。
在这里，我们用条件概率p(y|x)用来组成O(w)。

而组成的O(w)根据统计学公式，我们又可以写成相减的两部分。第一部分对我们而言是可见的（橙色的），我们需要最大化的；第二部分对我们而言是不可见的（蓝色的），我们需要最小化。

因为这里是最大化，使用的方法不再是梯度下降，而是梯度增加。

(具体计算有些困难，暂时没有理解)

最后的梯度上升的公式

• 绿色的部分是正确的对出现的次数，意味着s，t可以被正确匹配的时候，我们应该增大W。因而是正相关。
• 黄色的部分是其余任意的对出现的概率，意味着当s,t匹配错误的时候，我们应该减小W。因而是负相关。

summary

CRF vs HMM

本质区别：CRF会通过调整参数，尽可能降低错误对的机率，而HMM不具备这个功能

在计算中，HMM依据的是准确的P的值，而CRF只是根据训练集数据一直在训练调整参数，fit data。使得正确的对机率上升，错误对机率下降。

Structured support vector machine

Separable(应用范围较窄)

使用structured Perceptron 结构化感知机

问题：
这个算法什么时候才能够收敛，可能成功的找到需要的W吗？
结论：
算法花费最多的次数是（R/margin）的平方次

Non-separable case

我们大多数时候可能找不到可以让正确的(x,y)对的值最大的W向量，但是我们依旧可以评价不同的W向量的好坏。

为了评价W向量的好坏–>定义Cost Function，用来评估W有多差，然后我们选择的W是使得Cost Function minimize的。

Cost Function可以根据不同的问题自己定义。

Cost Function的最小值的求解可以通过梯度下降的方法。

特别地，当learning rate = 1的时候，这个就变成了结构化感知机。

Considering error

不同的错误之间有差别，这个也应该考虑到Training中来。

如图所示，右边对应的W就比左边对应的W要好很多。

所谓考虑错误的差别，即我们希望找到的W对应的评测函数F，当虽然是错误但是和正确答案比较接近的时候，两者的评测值也是接近的。但是当错误很离谱的时候，评测值和正确的评测值之间的差距则相对大了很多。

做法：定义Error Function，这个函数也是自己根据不同的问题自主定义。

有了Error Function，对应的Cost Function也需要作出相应修改，表示错误的差别被考虑进了training当中。

(存疑？为什么最大值是要加上Error Function)

计算Cost Function同样使用梯度下降

注意：此时出现了一个问题，最大值的求解对象是改变了的，原本只是求W*Feature的最大值，这个是我们假定已经能解决出来的，现在需要求出来的是原来的值加上Error Function的值。这点提示我们Error Function要合理定义，便于计算，不然会给整个计算增添很多问题。

算是一种理解方式？当式子满足下面两个的时候，上面的不等式是成立的，上面的不等式成立了，我们才能通过不断地减小真实y值和使F值最大的y值之间的最大差距来减小实际差距。

Regularization

Structured SVM

Structured Learning 结构化学习

对应视频BV13x411v7US P32

Unsupervised Learning 无监督学习

对应视频BV13x411v7US P24

• 化繁为简
  输入比较复杂的input，得到比较简单的output
  拥有的训练data，只有input，不知道output
• 无中生有
  训练某种function，训练集里只有function的output

Clustering 聚类

化繁为简的好方法

• K-means（K均值）：将X集合里的元素聚类为K个类别。

• HAC(hierarchical Agglomerative Clustering)凝聚层次聚类：
  利用树的结构表示Data
  在树的不同层次划分，可以得到不同数量的class。

Dimension Reduction 降维

从比较高维的空间变为比较低维的空间。
实质是输入一个x，经过某一function，得到输出z，z的维度小于x的维度。

方法：

• Feature selection 特征选择
• Principle component analysis(PCA) 主成分分析

（未完待续）

Semi-supervised Learning 半监督学习

对应视频BV13x411v7US P23

基本介绍

• 半监督学习的特点是，训练数据中存在一部分没有标记的数据，且数据量一般比标记后的数据要大。
• 为什么使用半监督学习？因为我们更多的数据是没有标记的，如果能有效地利用这些未标记数据可以将模型训练的更好，但是这方面，精确的“假设”起很重要的作用。