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

×