2. Language Modeling Problem

Chilly_Rain posted @ 2014年3月08日 19:05 in Coursera_NLP , 1362 阅读

语言模型问题的定义

词汇表:\(V \) = {the, man, telescope, ...}

语句:\(V^{+}\),无限多个,由词汇表中的若干个词加上结尾处的STOP标记组成;例如,the fan saw Beckham STOP,甚至the the the STOP也属于这其中。

输入:训练样本,各种各样实际中使用的句子,可以从报纸来,也可以从网页来。

输出:一个面向语句的概率分布,满足以下条件;实际表达的意义就是让像人话的句子概率更高,反之则更低。

\[ p(x) >= 0, \sum_{x \in V^{+}} p(x) = 1\]

这个模型有啥用

原始的出发点是语音识别,因为一段语音通常可以被识别成不同的句子,例如,recognize speech vs wrench a nice beach,但是前者明显更像人话,这时应用语言模型就可以辨识出这段话是前者的可能性更大。

另外,语言模型中的估计方法(estimation/smoothing method)也会很广泛地应用到NLP的其它问题之中,这也算是一个用途吧。

一个简单的方法

想解决语言模型问题,实际就是想得到一个合适的\(p(x)\),如何做呢?一个简单的方法就是记数,假设训练样本的规模是N,统计下训练样本中每个x出现的次数,然后\( p(x) = C(x) / N\)。但是这样做的问题是,如果有一个训练样本中从未出现的句子,那么它的概率就是0了,也就是说这个未出现的句子无论具体内容是啥,\( p(x)\)都认为它不是人话。

马尔科夫模型

马尔科夫模型假设第n个词出现的可能性只依赖于它的前k个词,即第n-1至第n-k个词。由于后面要讲是三元模型,所以这里用的是就三阶马尔科夫模型。具体来说,

\[p(x_1, ..., x_n) = p(x_1)*p(x_2|x_1)*p(x_3|x_1, x_2)*...*p(x_n|x_1, ..., x_{n-1})\]

这个是没有加入马尔科夫的链式规则,精确的等式,但是如果我们想用这个来算语言模型的话,就得从训练数据中估计出每个\(p(x_i|x_1, x_2, ..., x_{i-1}) \),这样我们就需要估计出\(O(|V|^{n})\)个参数。参数太多显然是没法搞的,因为参数越多,需要的训练数据就越多,否则就是造成参数极不稳定,甚至没什么意义。

如果加入前面提到的三阶马尔科夫假设的话,问题就简化了

\[p(x_1, ..., x_n) = p(x_1)*p(x_2|x_1)*p(x_3|x_1, x_2)*...*p(x_n|x_{n-2}, x_{n-1})\]

这样参数的个数就降到了\(O(|V|^3)\)(其实这个量级仍然太大,后面会讲到解决方法)。如果我们假设\(x_{-1} = x_0 = *\),表示开始符号,那么就可以将上式写成

\[p(x_1, ..., x_n) = \Pi_{i=1...n} p(x_i|x_{i-2}, x_{i-1})\]

还有个问题,就是上式只能表示长度为n的句子,而我们想要的是对任意长度的任意句子都有效的分布p。实际上,融合我们前面的定义\(x_n = STOP\),我们已经可以表示任意的句子了。

三元语法模型

把前面的三阶马尔科夫模型直接应用,就是三元语法模型,它包括以下两个部分

  • 一个有限的词汇表\(V\)
  • 对每个\(w \in V \cup {STOP}, u, v \in V \cup {*}\),都有一个参数\(q(w|u, v)\)

于是对任何一个句子\(x_1, ..., x_n\),其中\(x_1, ..., x_{n-1} \in V, x_n = STOP\),都可以直接它所对应的概率

\[p(x_1, ..., x_n) = \Pi_{i=1,...,n} q(x_i|x_{i-2}, x_{i-1})\]

举个例子,

\[p(the dog barks STOP) = q(the|*, *) * q(dog|*, the) * q(barks|the, dog) * q(STOP|dog barks)\]

好了,到这里,剩下的最后一个问题就是参数\(q(w|u, v)\)怎么从训练数据中估计出来了,最简单的方式就是MLE(极大似然估计法),即

\[q(x_i|x_{i-2}, x_{i-1}) = \frac{Count(x_{i-2}, x_{i-1}, x_i)}{Count(x_{i-2}, x_{i-1})}\]

正如前面所述的,这里参数的个数是\(O(|V|^3)\),依然不少,要使用这种方法得到稳定的参数估计值就需要使用大量的数据。否则的话,上式的分子分母都极有可能是零,那么得到的参数意义就不大了。

使用Perplexity对模型进行评估

假设我们除了有用于训练模型参数的训练数据之外,还有一些测试数据,表示为\(s_1, s_2, ..., s_m\),那么就可以用这些测试数据来评估训练得到的模型的可用性。这里定义了perplexity这个概念,本质上就是模型对这些测试数据的对数似然性:

\[Perplexity = 2^{-l}, where l = \frac{1}{M} \sum_{i=1...m} log p(s_i)\]

其中M表示测试数据是总的单词数据,因此l代表的就是模型对单个词的似然性;测试数据与模型的适应程度越好,似然性越大,perplexity就越小。

下面是对几个模型的比较

  • 均匀分布:\(q(w|u, v) = \frac{1}{|V|+1}\),无论上下文是啥,也不管当前词是啥,这个概率值总是固定的,这是一个很粗的模型,所以perplexity也很高为\(|V|+1\);
  • 一元语法模型:也就是unigram,就是在训练数据上记数,完全不管上下文,在Goodman的实验中(|V|=50000),它的perplexity为955;
  • 二元语法模型:就是只考虑前一个单词对当前词的影响,同一个实验中perplexity为137;
  • 三元语法模型:就是前面花大篇幅讲的那个模型,考虑当前词前面两个单的影响,perplexity为74;这已经是足够好的效果了。

但是三元语法模型也有它的不足,它无法捕获长距离的依赖关系,但是考虑的上下文太多了,就又会出现sparse data的问题,使参数估计很困难。其实这里也就是一个bias-variance tradeoff,上下文考虑得多,自然bias就小,但是由于训练数据相对不足,variance就大了;相反地,如果上下文考虑得少,variance小,但是bias就大了,所以不得不做一些折衷, 讲师说trigram的方法就是一个比较好的折衷。

参数平滑方法

我觉得下面这些内容才是这段课程的重点,就是怎样解决前面提到的由于数据稀疏问题而造成的MLE估计不可靠的问题。课程里介绍了两个方法,一种是线性插值,另一种是katz-backoff的类递归方法。实际上还有很多其它的方法,可以参考Foundations of Statistical Natural Language Processing中的第6章,也许未来这章的内容我也会总结一下写在blog上。

线性插值

这个方法的动机就是上一小节最后提到的bias-variance trade-off,既然unigram的variance小,而trigram的bias小,为啥不想个办法整合一下呢?于是就有了

\[q(w_i|w_{i-1}, w_{i-2}) = \lambda_1 \dot q_{ML}(w_i|w_{i-1}, w_{i-2}) + \lambda_2 \dot q_{ML}(w_i|w_{i-1}) + \lambda_3 q_{ML}(w_i)\]

\[\lambda_1 + \lambda_2 + \lambda_3 = 1, \lambda_i >=0\]

容易证明这个线性插值所产生的\(q(w_i|w_{i-1}, w_{i-2})\)也是一个合法的概率分布,符合归一化及>=0的条件。

各个\(q_{ML}\)都可以从训练数据中直接计算得到,那么剩下的事就是如何计算\(\lambda_i\)了。这里使用的方法是搞一份validation data,记这份数据中各个三词序列出现次数为\(c'(w_1, w_2, w_3)\),那么log-likelihood的表达式即为

\[L(\lambda_1, \lambda_2, \lambda_3) = \sum_{w_1, w_2, w_3} c'(w_1, w_2, w_3)logq(w_3|w_1, w_2)\]

表达式中未知参数只有\(\lambda_i\),所以使用这个表达式对其求偏导应该就可以了。另外,前面提到的perplexity实际就是log-likelihood的变形,所以这种方法就也是在寻找一组参数,使perplexity最大化。

再进一步,前面这种方式得到是一个不依赖于具体\(w_1, w_2\)的\(\lambda_i\)。极端情况下,如果我们已知\(w_1, w_2\)出现的次数足够多,还不如直接用trigram就好了(\(\lambda_3 = 1\),其它两个为0),相反地如果\(w_1, w_2\)出现极少,那么\(\lambda_1\)就应该相应的更重一些。总结一下就是说,最好是能让\(\lambda_i\)能随着具体\(w_1, w_2\)出现的次数而变化。于是就出现了下面\(\Pi(w_{i-2}, w_{i-1})\)这个东西

\[C(w_{i-2}, w_{i-1}) = 0, \Pi(w_{i-2}, w_{i-1}) = 1\]

\[1 <= C(w_{i-2}, w_{i-1})  <= 2, \Pi(w_{i-2}, w_{i-1}) = 2\]

\[3 <= C(w_{i-2}, w_{i-1})  <= 5, \Pi(w_{i-2}, w_{i-1}) = 3\]

\[C(w_{i-2}, w_{i-1}) >= 5, \Pi(w_{i-2}, w_{i-1}) = 4\]

再然后就是依赖于\(\Pi(w_{i-2}, w_{i-1})\)的\(q\)

\[q(w_i|w_{i-1}, w_{i-2}) = \lambda^{\Pi(w_{i-2}, w_{i-1})}_1 q_{ML}(w_i|w_{i-1}, w_{i-2}) + \lambda^{\Pi(w_{i-2}, w_{i-1})}_2 q_{ML}(w_i|w_{i-1}) + \lambda^{\Pi(w_{i-2}, w_{i-1})}_3 q_{ML}(w_i)\]

实际上就是按照每个\(w_i\)的context出现的次数,即\(C(w_{i-2}, w_{i-1})\),来对\(w_i\)分组,每组使用一套\(\lambda\)参数。

Katz Back-off Model

这种方法的动机的是从训练数据里得到的ML估计是对存于在训练数据里的词的过高估计(尤其是对仅出现一次的词),而对未登陆词的过低估计(ML估计都是0),所以需要从已有词的概率中抽取出一部分,分给这些未登陆词。以bigram为例,已存在词的次数被折掉了一部分(0.5这个数是个经验值,也可以使用前面的validation set方法来估计出来),

\(Count^{*}(w_{i-1}, x) = Count(w_{i-1}, x) - 0.5\)

而折掉的概率一共是

\[\alpha(w_{i-1}) = 1 - \sum_{w} \frac{Count^{*}(w_{i-1}, w)}{Count(w_{i-1})}\]

这些概率会根据unigram中各个x的概率比例再重新分配。具体如下:定义两个集合,\(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}) = Count^{*}(w_{i-1}, w_i) / Count(w_{i-1}), w_i \in A(w_{i-1})\]

\[q_{BO}(w_i|w_{i-1}) = \alpha(w_{i-1}) \frac {q_{ML}(w_i)} {\sum_{B}q_{ML}{w_j}}, w_i \in B(w_{i-1})\]

也就是说如果\(w_i\)出现在了训练语料中就使用高阶模型,否则的话就回退到低阶的模型中,在bias和variance中取一个折衷。基于上面bigram的定义,可以继续定义trigram模型,使未登陆词回退到bigram中。

最后是说可能对trigram模型的进一步改进方法,包括topic model,语法模型等,但是"It's generally hard to improve on trigram models though!!"

Avatar_small
BSNL Broadband Plan 说:
2023年2月07日 16:10

ISP provides unlimited calls to any network round the clock in all the BSNL broadband plans over fiber and DSL networks, and Here we update the latest BSNL broadband unlimited plans daily across India as and when the update released for home and business tariff, BSNL Broadband Plan So check each plan in detail to opt for best tariff. BSNL broadband plans over DSL and Bharat Fiber (FTTH) technologies are available, we categorize each plan and provide the updated information of all the circles with new plans and tariff.

Avatar_small
truecaller en ligne 说:
2023年7月13日 19:58

Nous avons tous reçu un appel d’un numéro inconnu ou d’un appelant indésirable à un moment donné de notre vie. Et au fil du temps, le besoin de connaître l’identité de l’appelant se renforce. truecaller en ligne Le portail Truecaller fournit une recherche de numéro de téléphone en ligne sur sa plate-forme, et nous sommes là pour vous aider et c’est entièrement gratuit.

Avatar_small
Meghalaya SSLC Mode 说:
2023年9月14日 19:40

MBOSE SSLC Important Question Paper 2024 for Hindi, English Medium Subject Wise Available on the our Website Along with the Students Click on the Subject name Link below to Download the Paper Pdf, this MBOSE SSLC Blueprint 2024 Developed by Senior Experts only, It will help you in Analyzing your Mistakes a better way of Representing your answer in the SSLC Final Exam, Meghalaya 10th Question Meghalaya SSLC Model Paper 2024 Paper 2024 will give Students an Exact idea about the Final Exam 2024, Students can Download the PDFs Format.Students who are Searching Internet for Meghalaya Board SSLC Model Paper 2024, Students can use These old Exam Paper as a Reference to Prepare for the Exam.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter