Log-Linear Models

Introduction

log-linear 模型在自然语言处理上使用非常广泛,其最主要的原因在于其灵活性,允许很多特征被使用在该模型上,相比于之前的简单估计技术(比如HMMs的标记问题,PCFGs的解析问题)。

Motivation

再次思考语言模型问题,其任务是得出下面条件概率的估计: \[ P(W_i=w_i|W_1=w_1...W_{i-1}=w_{i-1})=p(w_i|w_1...w_{i-1}) \] 对于任一序列\(w_1...w_i\),得出在序列\(w_1...w_{i-1}\)条件下,出现单词\(w_i\)的概率。在trigram语言模型中,我们有如下假设: \[ p(w_i|w_1...w_{i-1})=q(w_i|w_{i-2},w_{i-1}) \] 对于上面的概率求解,我们前面提到过使用一种平滑技术: \[ q(w|u,v)=\lambda_1q_{ML}(w|u,v)+\lambda_2q_{ML}(w|v)+\lambda_3q_{ML}(w) \] Trigram语言模型十分有效,但是在使用上下文 对于任一序列\(w_1...w_i\),得出在序列上相对狭窄了,比如我们想去估计单词model出现的概率在 对于任一序列\(w_1...w_i\),得出在序列条件下: \[ P(W_i=model|W_1=w_1...W_{i-1}=w_{i-1}) \]

我们可以思考在单词\(w_{i-2}\)下的概率,而忽略\(w_{i-1}\)\(P(W_i=model|W_{i-2}=any)\);我们也可以考虑前一个单词的词性来对当前单词的概率:\(P(W_i=model|pos(W_{i-1})=adj)\);实考前一个单词后缀对当前单词的影响:\(P(W_i=model|suff4(W_{i-1})=ical)\)等等很多,这样我们给每一个赋予权重参数,就可以写成如下形式: \[ p(model|w_1...w_{i-1})=\\ \lambda_1q_{ML}(model|w_{i-2}=any,w_{i-1}=statistical)+\\ \lambda_2q_{ML}(model|w_{i-1}=statistical)+\\ \lambda_3q_{ML}(model)+\\ \lambda_4q_{ML}(model|w_{i-2}=any)+\\ \lambda_5q_{ML}(model|w_{i-1}\,\,is\,\,an\,\,adj)+\\ \lambda_6q_{ML}(model|w_{i-1}\,\,ends\,\,in\,\,"ical")+\\ ... \]

显然如果这样做的话,会非常的麻烦,那么如何做呢,见下面部分。

Log-Linear Models

基本定义:\(X\)作为输入集,\(Y\)作为输出集(标签集,假设是一个有限集)。d表示模型特征和参数的个数,函数f表示任意一个\((x,y)\)对匹配的特征向量\(f(x,y)\),参数向量\(v \in R^d\). 将模型\(p(y|x)\)加上参数后定义的条件概率模型如下: \[ p(y|x;v)=\frac{e^{v\cdot f(x,y)}}{\sum_{y' \in Y}e^{v \cdot f(x,y')}} \] 其中\(v\cdot f(x,y)=\sum_{k=1}^{d}v_kf_k(x,y)\)\(p(y|x;v)\)读作在参数\(v\)下,基于x的y的条件概率。

Features

关于上面提到的特征向量\(f\)的计算如下图所示:

这里提到了trigram模型的例子,如上面所示,如果词汇表的大小为\(V\),那么对trigram模型来说将会有\(V^3\)个特征,这里用\(N(u,v,w)\)表示将每一个trigram对应到一个独一无二的整数。同理bigram模型,Unigram模型也是如此,而且这三个模型对应的整数不重叠。 从上面来说,特征会非常的稀疏,这里我们只取值为1的特征: \[ Z(x,y)=\{k:f_k(x,y)=1\} \] 这样就将特征的复杂度从\(O(d)\)降到\(O(|Z(x,y)|)\),且\(|Z(x,y)| \ll d\),这样特征向量的求解就变成如下: \[ v\cdot f(x,y)=\sum_{k=1}^{d}v_kf_k(x,y)=\sum_{k \in Z(x,y)}v_k \]

Parameter Estimation in Log-Linear Models

这里对上面的条件概率取对数就是我们的对数线性模型,假设我们有训练集\((x^{(i)},y^{(i)}), \,\,i \in \{1...n\},\,\,x^{(i)} \in X,\,\,y^{(i)} \in Y\),给定一个参数\(v\),对于任意的例子i,其对数条件概率如下: \[ log \,p(y^{(i)}|x^{(i)};v) \] 那么全部训练集中最大似然的对数条件概率和如下: \[ L(v)=\sum_{i=1}^{n}log\,p(y^{(i)}|x^{(i)};v) \] 我们要找到使\(L(v)\)最大的\(v\),即: \[ v_{ML}=arg\,\,\max_{v \in R^d} L(v) \] 这里举个例子,假设在训练集中的第100个例子中的trigram有: \[ f_{N(any,statistical,model)}(x^{(100)},y^{(100)})=1 \] 在其它例子中都没有,我们的目的是希望\(L(v)\)最大,这样在\(v_100\)就会取无穷大,那么对应例子的对数条件概率就会最大: \[ p(y^{(100)}|x^{(100)};v)=1 \] 由于其它例子没有该特征,\(v_100\)不会对其它例子产生影响,但是显然这样是不合理的,模型只会对当前的训练集起到很好的作用,即过拟合,泛化能力变差,我们需要模型的泛化能力变强,需要对参数v进行约束,即加上惩罚项: \[ L'(v)=\sum_{i=1}^{n}log\,p(y^{(i)}|x^{(i)};v)-\frac{\lambda}{2}\sum_{k}v_k^2 \] 上面这个式子就是机器学习中的损失函数,使用梯度下降就可以找到最优解。 对\(L'(v)\)求导: \[ \frac{dL'(v)}{dv_k}=\sum_{i=1}^{n}f_k(x^{(i)},y^{(i)})-\sum_{i=1}^{n}\sum_{y \in Y}p(y|x^{(i)};v)f_k(x^{(i)},y)-\lambda v_k \] 关于上面的证明如下: 取其中的一部分分析 \[ log\,p(y^{(i)}|x^{(i)};v)=v\cdot f(x^{(i)},y^{(i)})-log\sum_{y' \in Y}e^{v\cdot f(x^{(i)},y')} \] 对上面的第一部分求导: \[ \frac{d}{dv_k}\bigg(v\cdot f(x^{(i)},y^{(i)})\bigg)=\frac{d}{dv_k}\bigg(\sum_kv_k\cdot f_k(x^{(i)},y^{(i)})\bigg)=f_k(x^{(i)},y^{(i)}) \] 对上面第二部分(应该是看成以e为底,不过常数不影响): \[ 记 g(v)=\sum_{y' \in Y}e^{v\cdot f(x^{(i)},y')}\\ \frac{d}{dv_k}log\,g(v)=\frac{\frac{d}{dv_k}(g(v))}{g(v)}\\ =\frac{\sum_{y' \in Y}f_k(x^{(i)},y')e^{v\cdot f(x^{(i)},y')}}{\sum_{y' \in Y}e^{v\cdot f(x^{(i)},y')}}\\ =\sum_{y' \in Y}\bigg(f_k(x^{(i)},y')\frac{e^{v\cdot f(x^{(i)},y')}}{\sum_{y' \in Y e^{(v\cdot f(x^{(i)},y'))}}}\bigg)\\ =\sum_{y' \in Y}f_k(x^{(i)},y')p(y'|x;v) \] 这样就完了,后面两部分比较简单,都是在讲前面的模型用现在的对数线性模型替换后的结果及其对比,就不再做笔记了,此部分完结。。。




评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×