语言最主要的表达形式就是文字和语音，自然语言处理就是利用计算机自动或半自动地处理大量的文本信息，从中挖掘出有用的信息。自然语言处理研究的一些方面主要包括信息抽取、信息过滤、文档分类、情感分类等方面。自然语言处理中存在的一些基本的问题和困难包括语义歧义问题，比如对于句子

$$张老师和李老师的朋友过来了。$$

可以理解为

$$张老师/和/李老师的朋友/过来了。\\张老师和李老师/的/朋友过来了。$$

这样的例子还有很多，包括比如“关于鲁迅的文章”。对于句子歧义的组合种类，英语句子歧义有一个开塔兰数

$$Catalan_n = \frac{C_{2n}^n}{n+1}$$

自然语言处理中一般的研究方法包括基于规则的方法、基于数据驱动的方法以及基于统计的方法。其中最基本的原理来源于信息论，熵是信息论中重要的一个概念，其描述了随机变量的不确定性，熵的单位一般为bits，对于概率为P的随机变量X其熵为

$$H(X) = -\sum{p(x)}log_2p(x)$$

比如对于随机变量X其概率分布为，

$$P(X=1)=\frac{1}{2}, P(X=2)=\frac{1}{4}, P(X=3)=\frac{1}{4}$$

则其熵为

$$H(X) = -[\frac{1}{2}log(\frac{1}{2}) + 2*\frac{1}{4}log(\frac{1}{4})] = \frac{3}{2} bits$$

形式语言与自动机

形式语言是用来描述语言机器结构的方法，形式语法是一个四元组\(G=(N,\sum,P,S)\)，其中N表示非终结符的有限集合，\(\sum\)表示终结符有限集合，P是重写规则的有限集合，S为句子符或初始符。形式语言包括4中文法类型，分别为3-2-1-0型文法，对应正则文法、上下文无关文法、上下文有关文法以及无约束文法。根据文法规则中的每一步推导是改写最左边还是最右边的非终结符可以分为最左推导和最右推导。

3-型. 正则文法。 正则文法要求产生式的左侧只能包含一个非终结符号，右侧只能是空串、终结符或非终结符后随非终结符。正则文法产生的语言可以被有限状态自动机直接接受

若\(G=(V_N,V_T,P,S)\)是一个正则文法，则存在一个有限自动机FA \(M=(\sum,Q,\delta,q_0,F)\)使得\(T(M)=L(G) 其中T(M)\)为FA能接受的语言，其中Q是状态的有限集合，\(\sum\)是输入符号的有限集合，\(\delta\)是输入符号到状态的映射，\(q_0\)表示开始状态，F表示终止状态集合

$$T(M) = \{x|\delta(q_0,x)\in F\}$$

例 给定正则文法 \(G=V_N,V_T,P,S\)，其中

$$V_N = {S,A}, V_T = {0,1} \\P: S->0 A,A->1 S,A->0$$

则其对应的有限状态自动机M为

$$开始-->S--0-->A-->T \\S<-1-A$$

2型. 上下文无关文法CFG。 上下文无关文法也就是2-型文法相对于3-型文法正则文法少了右侧格式的限制，规则右端的格式没有约束，规则左部的非终结符可以被改写成任何形式。可以被非确定下推自动机接受。

1型. 上下文有关文法CSG。 相对于CFG继续放宽限制，规则左部不一定仅为一个非终结符，可以有上下文限制。这种语言可以被线性有界非确定图灵机接受。

0型. 无约束文法。 包括所有的文法，能产生所有可被图灵机识别的语言，即能使得图灵机停机的字符串，即递归可枚举语言。

形式语言与自动机在自然语言处理中可应用于单词拼写检查、单词形态分析以及词性消歧等，对于单词拼写检查需要计算字符串之间的编辑距离，对于字符串acomnad与command，其编辑距离就是使用添加删除或交换操作使得一个字符串能变成另一个的最小的次数，这里只需要将acomnad的第一个a删除，然后在m后面添加一个m，最后将后面的n和a进行交换，所以编辑距离为3。

语言模型

NLP语言模型包括文法语言模型和统计语言模型，随着统计的方法在自然语言处理中的应用，现在的语言模型基本上都是指的统计语言模型。统计语言模型是将一个句子的产生看做一个随机事件，以分词为例，存在很多种切分方式，但是最好的切分方式一定是生成概率最大的那一种。

具体来说，统计语言模型中实际是指的N元模型（N-Gram Model)，我们知道自然语言中一个词的含义是跟上下文相关的，但是用计算机来处理的话，我们需要指定一个词与前面多少个词相关，这就产生了N元文法。就是说当前词产生的概率只跟前N-1个词相关，这种假设称为N-1阶马尔可夫假设，当N=1为一元模型（unigram），也就是上下文无关的模型，当N=2时，就是当前词只跟上一个词有关，为二元模型（bigram）。对应于N-1阶马尔可夫假设就可以很容易引入统计学习方法隐马尔可夫模型HMM来进行自然语言处理了。

$$P(w_i|w_1,w_2,...,w_{i-1}) = P(w_i|w_{i-N+1},w_{i-N+2},...,w_{i-N+i})$$

例 句子“I study English every day.”的所有3元文法。（Tri-grams）

(\, I, study), (I, study, English), (study, English, every), (English, every, day), (every, day, \)

这里的\和\是句子首尾添加的标志，为了保证i=1时有意义，并且保证概率和为1。一般使用交叉熵和困惑度来评价语言模型的性能，交叉熵和困惑度越小越好。在根据训练语料计算句子的概率时可能会出现某些句子的概率为0，但是这些句子总有出现的可能，所以需要进行数据平滑。

关于数据平滑最简单的处理方式就是加1平滑，即认为所有二元语法出现的次数都比实际出现的次数多1次，这样就不会出现概率为0的条件概率，也不会出现概率为0的句子。增加的次数不一定为1，也可以采用加\(\delta\)次，\((0<=delta<=1)\)

另外一种平滑策略就是Good-Turing估计法，古德-图灵估计法的基本思路是对于任何一个出现r次的n元文法，都假定其出现了\(r^*\)次

$$r^* = (r+1)\frac{n_{r+1}}{n_r}$$

这里\(n_r\)是训练语料中出现r次的n元文法的数目，则对应的就可以得到出现r次的n元语法的概率为

$$p_r = \frac{r^*}{N}$$

其中N为所有\(r^*\)的总和，一般来说r越小，\(n_r\)越大，因为经常出现的n元语法其实并不多，大部分出现的次数都较小。

神经网络语言模型

对于词的表示，主要包括one-hot representation和distributed representation，也就是独热表示和分布式表示。传统的独热表示就是有多少种词就用多少维的向量来表示，并且一个词对应的维度上用1表示，其余为0，所以最终文本的表示为一个很大的稀疏矩阵，当然独热表示也有着它的用处，比如在文本分类时，可以直接用一个向量来表示一篇文本，这样比较两篇文档的相似度就可以直接计算余弦相似度，还可以将所有要分类的文本对应的向量组成一个文本词项矩阵，对矩阵做svd分解，也可以用来进行文本的分类。

但是对于其它方面，如自然语言处理中的信息抽取，用one-hot表示效果显然很差，因为它只是进行了一个编码，并没有反映出词的语义信息，不能反映出相近意思的词的关系，对于词的训练和学习而言，最好的方式就是对相同意思的词进行归类，没必要重复学习，比如对于相同词cat和Kitty，都表示小猫。词的分布式表示包括基于矩阵的分布式表示、基于聚类的分布表示以及基于神经网络的分布表示（词嵌入word embedding），在基于矩阵的表示中每一行都表示一个词，并且用向量的空间距离来表示词之间的语义的相似度。

关于word embedding 和 word2vec，Embedding就是嵌入，在数学上表示一个映射，具有injective和structure-preserving的特点，而word embedding就是将单词word映射到另一个空间，并且保留原来的语义信息，类似的还有image embedding和video embedding。Word embedding其实就是对一个词进行低维向量表示，低维正是其相对于one-hot的区别，word embedding的学习过程就是词和语义（上下文）之间的模型建立过程。Word embedding可以是基于矩阵分解和基于预测的方法来得到，基于矩阵分解就是基于语料库来构建word context的共现矩阵，矩阵中每个单元表示横纵两个词的关系，可以是TF-IDF或互信息等来表示，然后对矩阵进行分解获得词的向量表示，可以是SVD分解等。

获得word embedding另一种方式是基于预测的方法，这就是基于神经网络的方法了，比如在word2vec中直接用二者的向量表示的內积\(\vec w * \vec c\)表示二者之间的关联，然后以logistic回归函数作为概率分布，这里要学习的就是向量w和c了，如下为word2vec使用的模型

$$P(D=1 | w,c) = \sigma (\vec w * \vec c)=\frac{1}{1+e^{-(\vec w * \vec c)}}$$

词嵌入的优点体现在词映射到低维连续向量，相似词映射到相似方向，余弦相似度衡量，无监督学习，容易获得大量语料，一个向量可以编码一词多义，word2vec是使用最广泛的词嵌入方法，速度快、效果好、易扩展。

分词命名实体识别及词性标注

汉语自动分词是汉语句子分析的基础，一般来说汉语分词的方法包括基于字典的方法、基于规则的方法以及基于统计的方法，基于字典的方法包括最大匹配法以及最小分词法。前者又包括正向最大匹配算法、逆向最大匹配算法以及双向最大匹配算法。后者最少分词法其实就是最短路径法，其实就是要使得分词的结果中词的个数最少。

例1 假设词典中最长单词字数为7，则对于字符串：他是研究生物化学的一位科学家，则对于正向最大匹配算法FMM来说，首先匹配最长的7个字，看是否为一个词，如“他是研究生物化学”，不是一个词就看前面6个词，直到把“他”切分出来，然后顺次后移。逆向匹配就是从相反的方向进行。

例2 对于字符串“他只会诊断一般的疾病”，首先从前往后根据词典把所有可能的词语都连起来构成一个DAG图，然后根据最短路径算法查找最优分词结果。对于此例，输出候选会有“他/只会/诊断/一般/的/疾病”和“他/只/会诊/断/一般/的/疾病”，显然前者的分词词语个数更少。

自动分词方法还包括基于语言模型的方法、基于HMM的分词方法、由字构成词的分词方法以及生成式与判别式结合的方法等。汉语分词中一个重要的问题包括未登录词的识别，未登录词可以是词表中没有收录的词，也可以是训练语料中没出现过的词语。未登录词包括命名实体以及专业术语等词，其中命名实体主要包括人名、地名、组织机构名以及时间和数字表示四类。

对于自动分词的评价指标主要包括准确率、召回率以及F-测度

$$准确率 P = \frac{系统输出中正确结果个数}{全部结果个数}$$ $$召回率 R = \frac{系统输出中正确结果个数}{测试集中正确的答案个数}$$ $$F1 = \frac{2*P*R}{P+R}$$

例3 对于一句话：2013年轻工业产品质量大幅度提升。正确的分词和词性标注结果应该是：

$$2013年/NT 轻工业/NN 产品/NN 质量/NN 大幅度/JJ 提升/VV 。/PU$$

而某个分词和词性标注系统给出的结果是：

$$2013/QQ 年轻/AA 工业/NN 产品/NN 质量/NN 大/AA 幅度/ML 提升/VV 。/PU$$

其中正确分词的词包括：‘产品’、‘质量’、‘提升’和‘。’，总共四个，系统输出总共有9个，测试集的句子正确分词有7个，所以

$$P = 4/9 = 0.444$$ $$R = 4/7 = 0.571$$ $$F1 = \frac{2*P*R}{P+R} = 0.500$$

句法语义篇章分析

句法分析中一般用句法树来描述句子的句法结构，其中一般符号的意思即为英文的缩写，比如NP表示名词短语（Noun Phrase），同样的VP表示动词短语，PP表示介词短语。

PCFG法

基于概率的上下文无关文法即PCFG是CFG的扩展，对于语法中的规则，左部的产生式的概率分布满足归一化条件，也就是比如两条规则：VP->V NP 和 VP->VP PP的概率和应该为1，这两条规则的意思分别是动词短语可以分解为动词加名词短语，也可以分解为动词短语加介词短语。很直白的描述了句子的句法结构，使用树型结构来表示时直接是两个分支，有的句子以及语法规则对应着多个语法树，每个语法树的概率为上面所有节点的概率之积。

注：NP-名词短语，VP-动词短语，Det-冠词，PP-介词短语，Pu-标点符号，P-代词

句法分析包括短语结构分析以及依存句法分析，对于短语结构分析其评价指标与自动分词类似，也是准确率、召回率以及F1-测度值。短语结构分析方法也有很多种，上面介绍的是PCFG，另一种方法是线图分析法。

线图分析法

线图分析法中几个概念分别为：

线图(Chart)：保存分析过程中已经建立的成分(包括终结符和非终结符)、位置(包括起点和终点)。通常以 n×n 的数组表示(n 为句子包含的词数)。

代理表(待处理表)(Agenda)：记录刚刚得到的一些重写规则所代表的成分，这些重写规则的右端符号串与输入词性串(或短语标志串)中的一段完全匹配，通常以栈或线性队列表示。

活动边集(ActiveArc)：记录那些右端符号串与输入串的某一段相匹配，但还未完全匹配的重写规则，通常以数组或列表存储。

例： 对于文法G(S):S->NP VP, NP->Det N, VP->V NP, VP->VP PP, PP->Prep NP 输入句子：the boy hits the dog with a rod

1. 形态分析： the boy hit the dog with a rod

2. 词性标注： 1Det 2N 3V 4Det 5N 6Prep 7Det 8N

3. 句法分析1： (1)Agenda:Det(1,2) (2)ActiveArc:NP->Det◦N(1,2) (3)Chart:Det(1,2) Acts:返回

这里首先待处理表Agenda为空，然后加入第一个词，也就是介词the，用Det(1,2)来表示，跟它相关的规则就是NP->Det◦N，表示一个介词加一个名词可以规约（reduce）到介词短语NP，由于只能与前面的进行结合也就是扩展，所以现在还只能把边Det(1,2)加入

4. 句法分析2： (4)Agenda:N(2,3) ActiveArc:暂时无新的活动边加入 (5)Chart:N(2,3) Acts：扩展

现在待处理表中的Det(1,2)和新加入的N(2,3)能够进行扩展，得到边NP(1,3)，所以又将NP(1,3)加入到Agenda中，扩展的活动边表示为：(6)ActiveArc:NP->Det N ◦(1,3)

5. 句法分析3： (7)Agenda:N(1,3) (8)ActiveArc:S->NP◦VP(1,3) (9)Chart:N(1,3) Acts:返回

这里才将N(1,3)正式加入到线图中，之后继续考量下一个Agenda，以此类推，最终完成线图。将线图中的边改为节点，节点改为边就可以得到对应的句法结构树。

CYK分析算法

CYK算法是一种比较简答的句法结构分析的方法，比如对于给定文法G(S):(1)S->P VP, (2)VP->V V, (3)VP->VP N, (4)P->他, (5)V->喜欢，(6)V->读, (7)N->书，用CYK算法分析句子：他喜欢读书

1. 汉语分词和词性标注 他/P 喜欢/V 读/V 书/N n=4

2. 构造识别矩阵

矩阵中左下角单元全为空，对角线上元素为分词的词语，每个词语的上方初始化为其词性，然后根据语法规则用三角形的形式向右和向上进行合并，比如喜欢和读都是V，对应的文法规则VP->V V，可以进行合并成VP，依此类推

依存句法分析

用词与词之间的依存关系来描述语言结构的框架称为依存语法，一般句子中的词语之间都有着一定的依存关系，比如北京是中国的首都，其中“北京是”是一个SBV的依存关系，也就是主谓关系，而“是首都”又是一个动宾关系，称为VOB，“中国的首都”又包含了DE和ATT（定语）的关系。

对于句子“外资企业成为外贸重要增长点。”句子的root是其谓语“成为”，而企业是root的sbj，也就是主语。“外资”又是“企业”的nmod（名词修饰语）。依存句法分析器性能评价指标包括：

无标记依存正确率(unlabeled attachment score, UA)：所有词中找到其正确支配词的词所占的百分比，没有找到支配词的词(即根结点)也算在内。

带标记依存正确率(labeled attachment score, LA)：所有词中找到其正确支配词并且依存关系类型也标注正确的词所占的百分比，根结点也算在内。

依存正确率(dependency accuracy, DA)：所有非根结点词中找到其正确支配词的词所占的百分比。

根正确率(root accuracy, RA)：有两种定义方式：(1)正确根结点的个数与句子个数的比值；(2)另一种是所有句子中找到正确根结点的句子所占的百分比。对单根结点语言或句子来说，二者是等价的。

完全匹配率(complete match, CM)：所有句子中无标记依存结构完全正确的句子所占的百分比。

在计算某一种评价指标之前首先先查看正确输出和分析器输出的词对应的依存关系，比如对于上面的句子有依存关系：1外资 2企业 3成为 4外贸 5重要 6增长点 7。

外资(2,nmod)，企业(3,sbj)，成为(0,root)，外贸(6,nmod)，重要(6,nmod)，增长点(3,obj),。(3,p)

简单来看无标记依存正确率就是计算所有词找到正确的支配词（包括根节点）的百分比，而带标记的就是要考虑标记是否正确，只是依存正确率就不考虑根节点

知识图谱

NTN知识图谱补全

张量神经网络也就是NTN是Richard Socher在2013年的论文《Reasoning With Neural Tensor Networks for Knowledge Base Completion》中提出来的应用于KBC也就是知识库补全的一种神经网络结构。这篇论文是深度学习end to end应用于KBC的很重要的一篇文章，之后KBC方面的大部分的论文都引用了NTN。

知识库中表示的其实是一系列的fact，一般使用网络结构进行表示，采用三元组\((e1,R,e2)\)来表示两个实体e1和e2之间的关系，对于一般的知识库而言，其中有很多隐藏的关系并没有显示出来，所以需要根据已有的关系来推断未知的信息，比如对于位置信息，有 A in B 和 B in C就能够推断出来A in C，类似于这种简单的推理。

以前的KBC补全的方法都是将一个实体（entity）表示为一个单独的向量，这篇文章提出一种新的思路，就是用几个词向量的平均来表示一类实体，这样的话对于包含相同单词的实体就可以共享这一部分的统计信息，比如对于虎和孟加拉虎，在一个知识库里面这是两个不同的实体，但是老虎和孟加拉虎实际上是包含很多相似性的，使用词向量平均的话就能够很好的保留这种相似性

如上为NTN论文中对于实体的表示情况，从中可以看出比如Bengal tiger，可以映射到两个entity，分别为tiger和Bengal，一个表示的是地理信息，然后使用这两个词向量的平均来表示实体e1，然后将e1和e2，以及测试的关系"has part"，组成一个三元组，通过一个NTN张量神经网络来获得对于其关系的一个推理，并根据获得的评分来判断"has part"这个关系是否存在。

先看一下双线性模型的评分函数，双线性模型相较之前的算法的能够简单高效的整合两个实体的相互作用。

$$g(e_1,R,e_2) = u_R^Tf(e_1^TW_R^{[1:k]}e_2 + V_R[e1,e2]^T + b_R)$$

NTN则在双线性模型的基础上利用张量网络的的思想以扩充多层权重矩阵，并增加了标准层和偏移来优化模型。NTN张量神经网络学习的主要是实体的向量表示，模型的输入为实体关系表示的三元组，如果模型返回一个较高的评分，就表示是输入的这种关系。

NTN张量神经网络使用一个双线性的张量层来代替标准神经网络层，这样可以直接从多个维度来将两个实体联系在一起，如下为评分函数

$$g(e_1,R,e_2) = u_R^Tf(e_1^TW_R^{[1:k]}e_2 + V_R[e1,e2]^T + b_R)$$

其中f为激活函数tanh，Wr为一个k层的dxd的张量，保存了关系权重，Vr和br为神经网络标准形式的参数。

1. 三元组表示为

$$T^{(i)} = (e_1^{(i)}, R^{(i)}, e_2^{(i)})$$

2. 构造一个corrupted的三元组，利用随机实体ec来替换\(e_2^{(i)}\)

$$T_c^{(i)} = (e_1^{(i)}, R^{(i)}, e_c)$$

3. 损失函数为

4. 利用L-BFGS最优化，对第j层slice求偏导

5. 训练目标

• 提高正确三元组的评分
• 降低corrupted三元组的评分

Appendix

• LICSTAR的博客
• 我爱自然语言处理
• 夜露gaussic