自然语言处理学习（一）_三元模型 katz

观看了哥伦比亚大学的自然语言处理公开课视频后，做出的学习与总结。

这是week one 和week two 的总结

-------------------------------------------------------------------------------------------------------

一、自然语言处理基本可以分为：

自然语言理解：将自然语言文本输入计算机，计算机自己进行处理，获取有利信息。

自然语言生成：计算机生成一种与人类交流的语言。

 

二、在自然语言处理中的一些关键应用：

1、 机器翻译：将一种语言的句子映射到另一种语言上。

2、 信息抽取：将一些文本作为输入，将文本核心内容以结构化的，数据库形式表示的方式作为输出。

3、 文本摘要：输入一个或多个文档，将它们融合为一个显示这些文档主要内容的摘要。

4、 对话系统：人类可以和计算机使用自然语言进行交流。（既有自然语言理解，又有自然语言生成）

 

三、自然语言处理的一些基础问题：

1、 标注问题（将词语映射到标注序列，使每个词语都有自己的标注）：词性标注和命名实体识别。

2、 句法分析：输入一些句子，输出一个解析树（依照其语法知识对句子进行基本的层次分解）。

 

四、自然语言处理困难的一个重要问题：歧义问题

Eg. “at last,a computer that understandsyou like your mother”

1.它就像你妈妈一样了解你

2.它了解你像你妈妈

2.它就像了解你妈妈一样了解你

在声音层次上歧义：likeyour ===lie cured

在句法层次上歧义：understand/you/likeyour mother  or  understand/you like your mother

在语义层次上歧义：一词多义

在篇章层次上歧义：人称代词歧义

 

五、语言模型问题：

假设V是有限集合，包含语言中所有单词。V⁺是所有可能存在的句子或字符串集合。已经存在一个由示例句子组成的训练样本。

任务：通过训练样本，学习到这种语言的分布p，同时p满足p(x)>=0(xV⁺)，且=1。

注意：一个好的语言模型会赋予较高的概率值给更合理的句子，赋予较低的概率值给不合理的句子。

 

六、为什么要建立语言模型：

1、 语言模型在很多自然语言处理应用中有着作用：语音识别、光学字符识别、手写识别和机器翻译等。

语音识别：把语音记录作为输入，任务是把这些声波映射成单词，实际处理中会遇到发音相似的句子，导致真正的句子和相似句子混淆。如果存在一个语言模型，就可以评估每个句子的可能性p，有利于摆脱混淆问题。

2、 语言模型估计方法在处理其他自然语言处理问题中很有帮助：词性标注、句法分析和机器翻译等。

 

七、一个朴素方法建立语言模型：

假设有N个训练句子，每个句子用x₁…x_n表示，c(x₁…x_n)表示句子在训练语料中出现的次数，

定义：p(x₁…x_n)=c(x₁…x_n)/N

问题：对很多在训练语料中没有出现的新句子赋予0，（没有能力生成新句子）

 

八、马尔科夫过程（三元语言模型基础）

假设V是有限集合，包含语言中所有单词。存在一系列随机变量X₁…X_n,X _iV。先假设长度n是固定的。

建立模型：P(X₁= x₁ , X₂ = x₂ ,…,X_n = x_n)

 

九、一阶马尔科夫过程

P(X₁ = x₁ , X₂ =x₂ ,…,X_n = x_n)

=P(X₁ = x₁)P(X_i = x_i | X₁ = x₁ ,…,X_i-1= x_i-1)        根据链式规则

= P(X₁ = x₁)P(X_i = x_i | X_i-1 = x_i-1)                 根据马尔科夫预测（无后效性）

 

十、二阶马尔科夫过程（利用更多信息）

P(X₁ = x₁ , X₂ =x₂ ,…,X_n = x_n)

==P(X₁ = x₁)P(X₂= x₂ |X₁ = x₁)P(X_i = x_i | X_i-2 = x_i-2,X_i-1= x_i-1)

=P(X_i = x_i | X_i-2 = x_i-2,X_i-1= x_i-1)

假设：x_-1 =x₀ =*（开始标记）

问题：如果长度n是变化的

解决：定义X_n=STOP（语句结束标志）

十一、三元语言模型:

组成：1、有穷单词集合V      2、对每个三元组u,v,w 有一个参数q(w|u,v)，其中w, u,v

定义：对于任意句子x₁…x_n，x_i (i=1…n-1)且x_n =STOP, x_-1 = x₀ =*，则三元语言模型下的语句概率为p(x₁…x_n)=q(x_i | x_i-2 , x_i-1)

问题：q(w_i |w_i-2 , w_i-1)的估计问题

解决：利用最大似然估计q(w_i| w_i-2 , w_i-1)=count(w_i-2 , w_i-1 ,w_i)/count(w_i-2 , w_i-1)

问题：单词集V很大，求解q很多，count(w)为w在训练集中出现的次数，分子或分母很可能为0，导致q为0或无意义。

 

十二、评估不同语言模型的好坏：perplexity

假设一个训练集，m个测试语句（s₁, s₂, s₃,…s_m）,语言模型的参数是通过训练集学习到的，测试语句是一些没有使用过的语句。

测试语句的概率     

Perplexity = 2^-l 其中l=，M是测试语句中单词总数。

因此，perplexity越小，语言模型对于测试数据的适合度越好。

 

十三、语言模型方面的估计方法：差值法

三元最大似然估计q_ML(w_i | w_i-2 , w_i-1)= count(w_i-2 ,w_i-1 , w_i)/count(w_i-2 , w_i-1)

优点：利用了很多语境信息，缺点：需要非常大的训练集

二元最大似然估计q_ML(w_i | w_i-1)= count(w_i-1 , w_i)/count(w_i-1)

一元最大似然估计q_ML(w_i)= count(w_i)/count()

优点：可以快速收敛到期望值，缺点：忽视了语境信息

差值法：q(w_i| w_i-2 , w_i-1)=₁ q_ML (w_i | w_i-2 ,w_i-1)+₂ q_ML (w_i | w_i-1)+₃ q_ML (w_i)，其中₁+₂+₃=1，_i>=0

 

十四、语言模型方面的估计方法：折扣法

定义一个折扣数：Count^*(x)=Count(x)-0.5

丢失的概率：(w_i-1)=1-Count^*( w_i-1 , w)/ Count(w_i-1)

Katz 回归模型（二元）

定义两个结合：A(w_i-1)={w:Count(w_i-1 ,w)>0}   B(w_i-1)={w:Count(w_i-1,w)=0}

二元模型：q_BO(w_i|w_i-1 )=

其中(w_i-1)=1-

Katz回归模型（三元）

定义两个结合：A(w_i-2,w_i-1)={w:Count(w_i-2,w_i-1 ,w)>0}   B(w_i-2,w_i-1)={w: Count(w_i-2,w_i-1,w)=0}

三元模型： q_BO(w_i| w_i-2,w_i-1 )

=

其中(w_i-1)=1-

十五、标注问题：词性标注

将某个句子作为输入，词性标注序列作为输出。

需要解决的问题：一词多词性问题

十六、标注问题：命名实体标注

某个句子作为输入，句子的命名实体标注序列作为输出。

十七、监督学习：从日常使用中获得很多标注好了的训练语句，通过这些语句，学习一个函数或者算法，把新语句映射到对应的标注序列。

假设有两个训练集x⁽ⁱ⁾，y⁽ⁱ⁾ ，（i=1…m）每个x⁽ⁱ⁾代表一个句子输入，每个y⁽ⁱ⁾表示句子对应的标注。

监督学习任务：学习一个函数f，使得每个输入语句x可以映射到对应的标注f(x)

 

十八、监督学习模型：

条件模型（判别模型）

通过训练数据学习一个分布p(y|x)，对于每个测试语句x，定义f(x)=arg max_yp(y|x)

生成模型（产生式模型）

通过训练数据学习一个联合分布p(x,y)。

由贝叶斯规则可知p(x,y)=p(y)p(x|y)和p(y|x)= p(y)p(x|y)/p(x)，其中p(x)= 。由此可知条件模型和生成模型之间可以转换。

输出f(x)= argmax_yp(y|x)= arg max_y p(y)p(x|y)/p(x)= arg max_yp(y)p(x|y)

 

十九、生成模型方法的一个实例：隐藏马尔科夫模型（HMM）

假设有一个输入语句x=x₁,x₂,…,x_n。有一个标注序列y=y₁,y₂,…,y_n。对于每个句子和标注序列，定义一个联合分布p(x₁,x₂,…,x_n, y₁,y₂,…,y_n)。则对于句子x的最大可能标注序列为f(x)=arg max_y1,y2,…,ynp(x₁,x₂,…,x_n , y₁,y₂,…,y_n)。

 

二十、三元HMMs

对于每个句子x₁x₂…x_n(x_i ,i=1…n)，每个标注序列y₁y₂…y_n+1(y_i ,i=1…n, y_{n +1}=STOP)，联合分布p(x₁x₂…x_n, y₁y₂…y_n+1)= ，其中x₀ =x_-1 =*，参数q(s|u,v)对于任意s，u,v，参数e(x|s)对于任意s，x。

 

二十一、参数q(s|u,v)和e(x|s)的估计：平滑估计

q(s|u,v)= ₁ q_ML (s|u,v)+₂ q_ML (s|v)+ ₃ q_ML (s)，其中₁+₂+₃=1，_i>=0

e(x|s)= q_ML (x|s)

问题：对于所有的y，如果x从未在训练数据中出现过，则e(x|y)=0,意味着没有关于这个单词的任何有用信息。

解决方法：将V集合分为两个集合：普通词语（在训练数据中出现次数大于等于5）和低频率词语。把低频率词语按照他们的特征映射到较小的有穷集合中。

 

二十二、将HMMs应用到新句子中：Viterbi算法

输入一个句子x₁x₂…x_n，输出arg max_y1,y2,…,ynp(x₁,x₂,…,x_n , y₁,y₂,…,y_n+1)。

定义r(y_-1 ,y₀,y₁ ,…,y_k)= 

定义表示在k位置标注为u,v的最大可能性标注。

=max_{(y-1,y0,…,yk):yk-1=u,yk=v} r(y_-1 ,y₀,y₁ ,…,y_k)。

使用递归算法：=max_w (q(v|w,u)e(x_k|v))

算法：for k=1…n

        For u,v

           =max_w (q(v|w,u)e(x_k|v))

     Return max (q(STOP|u,v))

带有后指针的Viterbi算法：

for k=1…n

        For u,v

           =max_w (q(v|w,u)e(x_k|v))

           bp(k,u,v)=arg max_w (q(v|w,u)e(x_k|v))

令（y_n-1,y_n）=arg max_(u,v)(q(STOP|u,v))

For k=(n-2)…1

y_k =bp(k+2,y_k+1 , y_k+2)

return  标注序列y ₁,y ₂,…,y _n