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) \] 这样就完了，后面两部分比较简单，都是在讲前面的模型用现在的对数线性模型替换后的结果及其对比，就不再做笔记了，此部分完结。。。