本文主要译自paper 1.

Abstract

神经网络概率语言模型(NPLM)与过去广泛使用的n-gram语言模型相互竞争,甚至偶尔优于后者NPLM最大的缺点是训练和测试时间超长。Morin和Bengio提出了一种层次化语言模型,它会构建一棵关于词的二叉树,它比非层次化的使用专家知识的模型快2个数量级。我们引入了一种快速的层次化语言模型,它使用一种简单的基于特征的算法,可以从数据中自动构建word树。我们接着展示,产生的模型胜过非层次化神经网络模型、n-gram模型。

介绍

统计语言模型的关注点是,构建基于词序列的概率模型。这样的模型可以被用于区分可能的序列与不可能的序列,广泛用于语音识别,信息检索,机器翻译。大多数统计语言模型都基于Markov猜想:一个词的分布只依赖于 在它之前出现的固定数目的词。该猜想明显是错误的,但它很简洁方便,因为它将固定长度的词序列的概率分布建模问题,缩减成:给定前面固定数目的词(称为上下文:context),建模下一个词的分布。此处,我们使用:$P(w_n | w_{1:n-1})$来表示分布,wn是下一个词, $ w_{1:n-1} $表示上下文$(w_1,..,w_{n-1}) $。

目前n-gram模型是最流行的统计语言模型,因为简单,并且性能很好。这些模型的条件概率表$ P(w_n | w_{1:n-1}) $,通过统计训练数据中的n元组,并进行归一化进行估计。因为n元组的数据是n的指数级,对raw counts进行平滑会达到很好的性能。n-gram模型有许多平滑方法,详见paper 2. 尽管n-gram模型有许多复杂的平滑方法,n-gram模型很难利用大量上下文,因为数据的稀疏性问题很严重。这种现象的主要原因是,经典的n-gram模型是本质上有界的条件概率表,里面的条目都是相互独立的。这些模型不会利用这样的事实:即相似的词常出现在相似的上下文中,因为它们没有相似性的概率。基于分类的n-gram模型(paper 3)主要解决该问题,通过将词和上下文,基于使用模式聚类到分类中,使用这些分类信息来提升泛化。它会提升n-gram的性能,这种方法引入了严格死板的相似性,因为每个词很典型,都属于确定的某个类。

另一种可选的、更灵活的抵消数据稀疏性问题的方法是,将每个词使用一个real-valued的特征向量,它会捕获该特性,以便相似的上下文中的词,具有相似的特征向量。接着,下一个词的条件概率可以被建模成一个关于上下文词和下一个词的平滑函数。这种方法提供了自动平滑,因为对于一个给定的上下文,相似的词可以保证分配到相似的概率。同样的,相似的上下文现在也可能具有相似的表示,并会生成对下一个词相似的预测。大多数基于该方法的模型,使用一个前馈神经网络(feed-forwark NN),将上下文词汇的特征向量映射到下一个词的分布上。这种方法的可能最好模型是神经网络语言模型NPLM(paper 4),在100w词级别的语料上,它胜过n-gram模型。

层次化神经网络语言模型

NPLM的主要缺点是,这样的相类似模型,训练和测试时间很慢。因为下一个词的概率计算,需要显式对词汇表中所有词进行归一化,对于给定下一个词的概率计算开销,以及对于在下一个词之上的所有分布的计算开销,事实上两者几乎一样:它们会花费关于词汇表size的线性时间开销。由于在这样的模型上,计算精确的梯度,需要重复计算给定上下文的下一个词的概率,通过增加概率来更新模型参数,训练时间与词汇表size成线性关系。通常,自然语言数据集包含着上万的词汇,这意味着即使以最简单方式训练这种类NPLM模型,在实际中的计算开销仍过大。一种加速该过程的方法是,使用专门的重要性sampling过程,来逼近要学习所需的梯度(paper 5)。然而,该方法可以本质上加速训练时间,测试时间的开销依然很快。

我们引入了层次化NPLM(paper 6),对比普通的NPLM,它在训练和测试的时间复杂度均做到了指数级的衰减。通过二叉树替代NPLM中非结构化的词汇表,可以表示成一个层次化的词汇表词簇。每个词对应于树上的叶子节点,可以由顶点到叶子节点的路径唯一确定。如果N是词汇表的词数,并且树是一棵平衡树,任何词都可以由一串O(log N)二分决策来指定,它会指定两个子节点,当前节点可以访问到下一节点。该过程将N-way选择替换成一串O(log N)的二分选择。在概率术语中,N-way归一化,可以替换成一串O(log N)的局部(二分)归一化。结果上,词汇表中的词分布,可以通过提供访问左子节点的概率来指定。在层次化NPLM中,这样NPLM方式的局部概率的计算:采用一个特征向量作为上下文词汇,同时给当前节点的一个特征向量作为输入。下一个词的概率,由该词所对应路径的二分决策的概率指定。

当数据集包含上百万的词时,该模型的表现优于基于分类的3-gram,但比paper 6中的NPLM表现差。这种层次化NPLM模型,比普通的NPLM快2个数量级。这种方法的主要限制,主要是用于构建word树的过程。该树可以从WordNet IS-A分类体系开始,通过结合人工和数据驱动处理,并将它转换成一个二叉树。我们的目标是,将该过程替换成从训练数据中自动构建树,不需要任何专家知识。我们也探索了使用树(里面的词汇至少出现一次)的性能优点。

log-bilinear model

我们使用log-bilinear语言模型(LBL:Paper 7)作为我们层次化模型的基础,因为它的性能十分出色,并且很简洁。类似于所有神经网络语言模型,LBL模型将每个词表示成一个real-valued的特征向量。我们将词w的特征向量表示成:$ r_w $,所有词的特征向量组成矩阵R. 模型的目标:给定上下文$ w_{1:n-1} $,预测下一个词$w_n$。我们将要预测下一个词的的特征向量表示成$ \hat{r} $,它可以通过对上下文词汇的特征向量进行线性组合得到:

公式一:$ \hat{r}=\sum_{i=1}^{n-1}C_{i}r_{w_i} $

其中,$C_i$是权重矩阵,它与位置i的上下文有关。接着,要预测的特征向量,和词汇表中每个词的特征向量,两者间的相似度通过内积计算。该相似度接着进行指数化,归一化,从而获取下一个词的分布:

公式二: \(P(w_n=w | w_{1:n-1})= \frac{exp(\hat{r}^T r_{w} + b_{w})}{\sum_{j} exp(\hat{r}^T r_{j} + b_{j})}\)

这里的$ b_w $是词w的偏置bias,它被用于捕获上下文独立的词频。

注意,LBL模型可以被解释成一种特殊的前馈神经网络,它只有一个线性隐层,以及一个softmax输出层。该网络的输入是上下文词汇的特征向量,而从隐层到输出层的权重矩阵,则可以简单通过特征向量矩阵R指定。该向量隐单元的激活,对应于下一个词的预测特征向量。不同于NPLM,LBL模型需要计算隐层激活,每次预测只计算一次,隐层不存在非线性。虽然LBL模型很简单,但表现很好,在相当大的数据集上,优于NPLM和n-gram模型。

4.层次化log-bilinear模型

我们的层次化语言模型基于该模型. 该模型的特点是,使用log-bilinear语言模型来计算每个节点的概率,并处理树中每个词的多次出现率。注意,使用多个词出现率的思想,由papar 6提出,但它并没有实现。

HLBL的第一部分是:一棵关于词作为叶子的二叉树。接着,我们假设词汇表中每个词对应一个叶子结点。接着,每个词可以通过从树顶点到叶子节点的路径唯一指定。该路径本身可以编码成一串二进制字符串d(每个节点会做二分决策),$ d_i=1 $对应于:访问当前节点的左子节点。例如,字符串”10”表示的是:从顶点,到左子节点,然后到右子节点。这样,每个词可以被表示成一串二进制码。

HLBL模型的第二部分是:每个节点会做出二分决策的概率模型,在我们的case中,使用了一个LBL模型的改进版本。在HLBL模型中,和非层次化的LBL类似,上下文词汇表示成real-valued特征向量。树上的每个非叶子节点,也具有一个特征向量与它相关联,它用于区分词是在该节点的左子树还是在右子树。不同于上下文词汇,被预测的词,被表示成使用它们的二进制码。然而,这种表示相当灵活,因为编码中的每种二进制数字,相当于该节点做出的决策,它依赖于节点的特征向量。

在HLBL模型中,给定上下文,下一个词是w的概率,就是由该词编码指定的一串二分决策的概率。因为在一个节点上做出一个决策的概率,只取决于要预测的特征向量(由上下文决定),以及该节点的特征向量,我们可以将下一个词的概率表示成二分决策的概率乘积:

公式三:$ P(w_{n}=w | w_{1:n-1}) = \prod P(d_{i} | q_i,w_{1:n-1}) $

di是词汇w的第i位数字编码,qi是编码所对应路径上第i个节点的特征向量。每个决策的概率为:

公式四:$ P(d_{i}=1 | q_{i},w_{1:n-1})= \delta (\hat{r}^T q_{i}+b_{i}) $

其中,$ \delta(x) $是logistic函数,而$ \hat{r} $是使用公式一计算得到的要预测的特征向量,在该公式中的bi是该节点的偏置bias,它可以捕获当离开该节点到它的左子节点上的上下文独立的趋势。

\[P(w_n =w | w_{1:n-1}) =\sum_{d \in D(w)} \prod_{i} P(d_i |q_i,w_{1:n-1})\]

D(w)表示词汇w所对应的一串编码集合。每个词允许多个编码,可以更好地预测词,具有多种含义或者多种使用模式。每个词使用多种编码,也可以使它更容易将多种不同的词层次结构,组合成单一的结构。这也反映了一个事实:没有单一的层次结构可以表示词之间的所有关系。

使用LBL模型(而非NPLM)来计算局部概率,允许我们避免计算隐层的非线性,这可以让我们的层次模型,比层次化NPLM模型更快作出预测。更重要的是,对于O(log N)个决策中的每一个,层次化NPLM都需要计算一次隐层激活,而HLBL模型只在每次预测时计算一次要预测的特征向量。然而,在LBL模型中,单个二分决策的概率计算的时间复杂性,仍然是特征向量维度D的二次方,这会使高维特征向量的计算开销很高昂。我们可以使时间复杂度与D是线性关系,通过将权重矩阵Ci限制为对角阵。注意,对于上下文size=1的情况,该限制条件不会减小模型表示的幂(power),我们相信,这种损失(loss),多于可以通过使用更复杂的树更快的训练时间的补偿。

HLBL模型可以通过最大化(带罚项的)log似然进行训练。因为下一个词的概率只依赖于上下文权重、上下文词汇的特征向量、以及从顶点到词汇所在叶子节点路径上的节点的特征向量,在每个训练case上,只有一小部分(log级别)的参数需要更新。

参考

介绍

word2vec中的logistic function计算使用的是快速算法,初始先算好值,然后在神经网络训练迭代中直接查表加快计算和训练速度。设计也还算精巧。

代码

在初始化时,有代码片段一,会对expTable做专门的初始化:

#define EXP_TABLE_SIZE 1000
#define MAX_EXP 6



// step 4: 分配logistic查表.
expTable = (real *)malloc((EXP_TABLE_SIZE + 1) * sizeof(real));
  
// 初始化: 预先计算好指数运算表. 
for (i = 0; i < EXP_TABLE_SIZE; i++) {
    expTable[i] = exp((i / (real)EXP_TABLE_SIZE * 2 - 1) * MAX_EXP); // Precompute the exp() table
    expTable[i] = expTable[i] / (expTable[i] + 1);                   // Precompute f(x) = x / (x + 1)
  }

expTable数据的大小为1000,存了1000个值用于查表。

而在模型训练阶段,代码片段二:

// 前向传播: f=∑ neu1*syn1
// Propagate hidden -> output
for (c = 0; c < layer1_size; c++) {
  f += neu1[c] * syn1[c + l2];
}

// 范围判断,查表
if (f <= -MAX_EXP) 
  continue;
else if (f >= MAX_EXP) 
  continue;
else 
  f = expTable[(int)((f + MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))];

将代码片段二代入到代码片段一,我们可以发现很神奇的现象:

将上式简单做个替换,把f替成z,整体输入看成i:

而再做一次运算,即知该表的值刚好与 logit函数 y = 1/(1+e^-z) 相同。

为什么要这么设计呢?

通过查表法,当然是为了加快指数运算。如果在每次迭代时,都去做指数运算,cpu开销蛮大。这样的设计,可以优化训练时间。

我来来看前前一段代码中,expTable[0 … EXP_TABLE_SIZE]中具体对应的值是哪些?这里,我提供了它的python实现:代码下载 ,绘制出实际的取值曲线(logistic regression的某一段取值),详见上面链接提供的代码:

另外,还有一点,就是这样的分割:EXP_TABLE_SIZE=1000, MAX_EXP=6? 把数字代入,即知:

\[e_{raw}=e^{(\frac{2*i}{1000}-1)*6}\] \[logit=\frac{e_{raw}}{e_{raw}+1}\] \[i=\frac{(f+6)*(1000)}{6*2}\]

为什么要做这样的trick进行分解呢?上图展示的是从输入z的角度去理解。要真正理解为什么这样取,还要结合实际代码中Hierarchical softmax代码里的情况去理解。

里面的f输入范围在(-MAX_EXP, MAX_EXP), 即(-6, 6)。

第一阶段:(f + MAX_EXP)/MAX_EXP/2 * EXP_TABLE_SIZE 所做的操作:

  • f + MAX_EXP: 平移,(0, 12)
  • (f + MAX_EXP)/MAX_EXP: 压缩,(0,2)
  • (f + MAX_EXP)/MAX_EXP/2: 归一化,(0,1)
  • (f + MAX_EXP)/MAX_EXP/2 * EXP_TABLE_SIZE: 即将归一化后的f映射到[0,1000)个expTable的格子里,即是第一式的输入i

第二阶段:(i / (real)EXP_TABLE_SIZE * 2 - 1) * MAX_EXP 所做的操作:

  • i / EXP_TABLE_SIZE: 将上面第一阶段的i,重新压缩到(0,1)
  • i / (real)EXP_TABLE_SIZE * 2: 拉伸成(0,2)
  • i / (real)EXP_TABLE_SIZE * 2 - 1: 平移为(-1,1)
  • (i / (real)EXP_TABLE_SIZE * 2 - 1) * MAX_EXP: 放大为(-6,6)

ok,这时候,我们就会明白,为啥取(-6,6)了。因为:

  • logit(6)=0.997527376843
  • logit(-6)=0.00247262315663

这个范围内的值足够了。

但如果你细发现,两步合在一起,我们发现仿佛又回到了原点,于是可能开始会怀疑,为什么不干脆直接用f,省去中间这么多的变换,直接原封不动地输入expTable呢?

比如类似这样的实现:

def logit(x):
    e = math.exp(x)
    return e/(e+1)

我们可以推导下,如果让你设计一个需要1000个值的数组,存储logit函数值。假设数组名为expTable,即:

  • 输入x为(0,1000)
  • expTable[x]的输出值对应概率值(0,1)

由于logit(0)=0.5,常用的一个实现是:

\[y=\frac{1}{1+e^{-(x*2-1)}}\]

从0开始刚好为0,输入(0,+inf),输出(0,1)。如果想让x刚好对应索引,刚在原基础上除以1000即可。即:

\[y=\frac{1}{1+e^{-(x*2/1000-1)}}\]

再在原基础上做一下范围控制,就是我们上面的:

\[y=\frac{1}{1+e^{-(x*2/1000-1)*6}}\]

如果希望得到更精准的值,将EXP_TABLE_SIZE和MAX_EXP调大些即可以。

介绍

Mikolov在Distributed Representations of Words and Phrases and their Compositionality中,提到高频词的subsampling问题,以下我对相关节选进行的简单中文翻译:

在非常大的语料中,最高频的词汇,可能出现上百万次(比如:in, the, a这些词)。这样的词汇通常比其它罕见词提供了更少的信息量。例如,当skip-gram模型,通过观察”France”和”Paris”的共现率(co-occurrence),Skip-gram模型可以从中获益;而”France”和”the”的共现率则对模型贡献很少;而几乎每个词都常在句子中与”the”共同出现过。该思路也常用在相反的方向上;高频词的向量表示,在上百万样本训练完后不会出现大变化。

为了度量这种罕见词与高频词间存在不平衡现象,我们使用一个简单的subsampling方法:训练集中的每个词\(w_i\),以下面公式计算得到的概率进行抛弃:

\[P(w_i)=1-\sqrt{\frac{t}{f(w_i)}}\]

\(f(w_i)\)是\(w_i\)的词频,t为选中的一个阀值,通常为\(10^{-5}\)周围(1e-5=0.00001)。我们之所以选择该subsampling公式,是因为:它可以很大胆的对那些词频大于t的词进行subsampling,并保留词频的排序(ranking of the frequencies)。尽管subsampling公式的选择是拍脑袋出来的(启发式的heuristically),我们发现它在实践中很有效。它加速了学习,并极大改善了罕见词的学习向量的准确率(accuracy)。

具体实现

在当中的描述是:

\[P(w_i)=1-(\sqrt{\frac{sample}{freq(w_i)}}+\frac{sample}{freq(w_i)})\]

实际代码如下:

// 进行subsampling,随机丢弃常见词,保持相同的频率排序ranking.
// The subsampling randomly discards frequent words while keeping the ranking same
if (sample > 0) {

  // 计算相应的抛弃概率ran.
  real ran = (sqrt(vocab[word].cn / (sample * train_words)) + 1) * (sample * train_words) / vocab[word].cn;

  // 生成一个随机数next_random.
  next_random = next_random * (unsigned long long)25214903917 + 11;

  // 如果random/65535 - ran > 0, 则抛弃该词,继续
  if (ran < (next_random & 0xFFFF) / (real)65536) 
      continue;
}

为此,我简单地写了一个python程序,做了个测试。程序托管在github上,点击下载

词频越大,ran值就越小。subsampling进行抽样时被抽到的概率就越低。

1.png

参考:

Distributed Representations of Words and Phrases and their Compositionality

介绍

如果你在大学期间学过信息论或数据压缩相关课程,一定会了解Huffman Tree。建议首先在wikipedia上重新温习下Huffman编码与Huffman Tree的基本概念: Huffman编码wiki

简单的说(对于文本中的字母或词),Huffman编码会将出现频率较高(也可认为是:权重较大)的字(或词)编码成短码,而将罕见的字(或词)编码成长码。对比长度一致的编码,能大幅提升压缩比例。

而Huffman树指的就是这种带权路径长度最短的二叉树。权指的就是权重W(比如上面的词频);路径指的是:从根节点到叶子节点的路径长度L;带权路径指的是:树中所有的叶结点的权值乘上其到根结点的路径长度。WPL=∑W*L,它是最小的。

word2vec的Huffman-Tree实现

为便于word2vec的Huffman-Tree实现,我已经将它单独剥离出来,具体代码托管到github上: huffman_tree代码下载。示例采用的是wikipedia上的字母:

即:F:2, O:3, R:4, G:4, E:5, T:7

这里有两个注意事项:

  • 1.对于单个节点分枝的编码,wikipedia上的1/0分配是定死的:即左为0,右为1(但其实分左右是相对的,左可以调到右,右也可以调到左)。而word2vec采用的方法是,两侧中哪一侧的值较大则为1,值较小的为0。当然你可以认为(1为右,0为左)。
  • 2.word2vec会对词汇表中的词汇预先从大到小排好序,然后再去创建Huffman树。在CreateBinaryTree()调用后,会生成最优的带权路径最优的Huffman-Tree。

最终生成的图如下:

此图中,我故意将右边的T和RG父结节调了下左右,这样可以跳出上面的误区(即左为0,右为1。其实是按大小来判断0/1)

相应的数据结构为:

/**
 * word与Huffman树编码
 */
struct vocab_word {
  long long cn;     // 词在训练集中的词频率
  int *point;       // 编码的节点路径
  char *word,       // 词
       *code,       // Huffman编码,0、1串
       codelen;     // Huffman编码长度
};

最后,上面链接代码得到的结果:

1
2
3
4
5
6
word=T	cn=7	codelen=2	code=10	point=4-3-
word=E	cn=5	codelen=2	code=01	point=4-2-
word=G	cn=4	codelen=3	code=111	point=4-3-1-
word=R	cn=4	codelen=3	code=110	point=4-3-1-
word=O	cn=3	codelen=3	code=001	point=4-2-0-
word=F	cn=2	codelen=3	code=000	point=4-2-0-

整个计算过程设计的比较精巧。使用了三个数组:count[]/binary[]/parent_node[],这三个数组构成相应的Huffman二叉树。有vocab_size个叶子节点。最坏情况下,每个节点下都有一个叶子节点,二叉树的总节点数为vocab_size * 2 - 1就够用了。代码使用的是 vocab_size * 2 + 1。

当然,如果你有兴趣关注下整棵树的构建过程的话,也可以留意下这部分输出:

count[]:	7 5 4 4 3 2 1000000000000000 1000000000000000 1000000000000000 1000000000000000 1000000000000000 1000000000000000
binary[]:	0 0 0 0 0 0 0 0 0 0 0 0
parent[]:	0 0 0 0 0 0 0 0 0 0 0 0
	
--step 1:
count[]:	7 5 4 4 3 2 5 1000000000000000 1000000000000000 1000000000000000 1000000000000000 1000000000000000
binary[]:	0 0 0 0 1 0 0 0 0 0 0 0
parent[]:	0 0 0 0 6 6 0 0 0 0 0 0
	
--step 2:
count[]:	7 5 4 4 3 2 5 8 1000000000000000 1000000000000000 1000000000000000 1000000000000000
binary[]:	0 0 1 0 1 0 0 0 0 0 0 0
parent[]:	0 0 7 7 6 6 0 0 0 0 0 0
	
--step 3:
count[]:	7 5 4 4 3 2 5 8 10 1000000000000000 1000000000000000 1000000000000000
binary[]:	0 1 1 0 1 0 0 0 0 0 0 0
parent[]:	0 8 7 7 6 6 8 0 0 0 0 0
	
--step 4:
count[]:	7 5 4 4 3 2 5 8 10 15 1000000000000000 1000000000000000
binary[]:	0 1 1 0 1 0 0 1 0 0 0 0
parent[]:	9 8 7 7 6 6 8 9 0 0 0 0
	
--step 5:
count[]:	7 5 4 4 3 2 5 8 10 15 25 1000000000000000
binary[]:	0 1 1 0 1 0 0 1 0 1 0 0
parent[]:	9 8 7 7 6 6 8 9 10 10 0 0

参考

1.Huffman编码

Y Bengio在2003年发布了paper《A Neural Probabilistic Language Model》,即NNLM。我们来看一下这篇10多年前的paper中的主要内容:

1.介绍

语言建模和其它学习问题很难,因为存在一个基础问题:维度灾难(curse of dimensionality)。当你想建模许多离散随机变量间(比如:一个句子中的词,或者在一个数据挖掘任务中的离散变量)的联合分布时,这个现象特别明显。例如,如果你想建模自然语言中在一个size=10w的词汇表V的10个连续词的联合分布,潜在会有\(100000^{10}-1=10^{50}-1\)个自由参数(free parameters)。当建模连续变量时,我们可以更轻易地获得泛化(例如:使用多层神经网络或高斯混合模型的平滑分类函数),因为学到的函数可以具有一些局部平滑属性。对于离散空间,泛化结果并不明显:这些离散变量的任何变化,都可能对要估计的函数值具有一个剧烈的影响;当离散变量的值可取的数目很大时,大多数观察到的目标相互之间在hamming距离上差距很大

受非参数化密度估计的启发,对不同学习算法如何泛化进行可视化的一种有效方法是,认为将初始集中在training points(例如:训练句子)上的概率质量(probability mass)在一个更大的空间(volume)中分散是的(distributed)。在高维中,将概率质量(probability mass)进行分散(distribute)很重要,而非围绕在每个training point周围的所有方向上均匀。我们在本paper会展示提出的这种方法与state-of-art统计语言建模方法的不同。

统计语言模型可以通过下面的公式进行表示,给定所有之前出现的词,对下一个词的条件概率:

\[\hat{P}(W_1^T) = \prod\limits_{1}^{T} \hat{P}(w_t | w_t^{t-1})\]

其中,\(w_t\)是第t个词,子序列可以写成:\(w_i^j = (w_i, w_{i+1}, \cdots, w_{j-1}, w_j)\)。这样的统计语言模型在许多应用中很有用,比如:语音识别,语言翻译,信息检索。统计语言模型对这样的应用有极大影响。

当构建自然语言的统计模型时,可以通过使用词序(word order)来减小建模问题的难度,实际上在词序列中时序更接近的词在统计学上相互依赖更强。因而,对于一个大数目的上下文(比如:最近n-1个词的组合)中的每个词,可以近似使用n-gram模型来构建对于下一个词的条件概率表

\[\hat{P}(w_t | w_1^{t-1}) \approx \hat{P}(w_t | w_{t-n+1}^{t-1})\]

我们只考虑这些在训练语料中实际出现、或者发生足够频繁的连续词的组合。当n个词的一个新组合出现在训练语料中,会发生什么?我们不想分配零概率到这样cases中,因为这些新组合很可能会出现,而且他们可能对于更大的上下文size会出现的更频繁。一个简单的答案是,使用一个更小的上下文size来看下预测概率,比如:back-off trigram模型、或者smoothed trigram模型。在这样的模型中,从在训练语料中的词序列获取的的模型如何泛化到新的词序列上呢?一种方式是,给这样的插值或back-off ngram模型对应一个生成模型。本质上,一个新的词序列可以通过“粘合(gluning)”在训练语料中频繁出现的非常短或长度为1,2…,n的重叠块来生成。在特别的back-off或插值n-gram算法中,获得下一块(piece)的概率的规则是隐式的。通常,研究者们使用n=3(比如:trigrams),并获取state-of-art结果。。。。

1.1 使用分布式表示来解决维度灾难

简单的,提出的方法可以如下进行总结:

  • 1.将词表中的每个词与一个distributed word feature vector(在\(R^m中\)一个real-valued vector)进行关联。
  • 2.采用在序列中的词的feature vectors来表示词序列的联合概率函数.
  • 3.同时学习word vectors和概率函数的参数

feature vector可以表示词的不同方面:每个词与一个向量空间中的一个点(point)相关联。features的数目(比如:实验中采用m=30, 60或100)比词汇表的size要小很多。概率函数被表示成:给定之前的词,一个关于下一个词的条件概率乘积(例如:使用一个multi-layer NN来预测)。该函数具有这样的参数,它以最大化训练数据的log似然来进行迭代调参。feature vectors是通过学习得到的,但它们可以使用语义特征的先验知识进行初始化。

为什么会有效?在之前的示例中,如果我们知道,dog和cat扮演着相似的角色(语义上和结构上),对于(the,a), (bedroom, room), (is, was), (running, walking)是相似的,我们可以很自然地对下面的句子进行泛化:

The cat is walking in the bedroom

泛化成:

A dog was running in a room

或者:

The cat is running in a room

A dog is walking in a bedroom

The dog was walking in the room

以及许多其它组合。在我们提出的模型中,它是可以泛化的,因为“相似”的词被认为是具有一个相似的feature vector,因为概率函数是一个关于这些feature values的平滑函数,在特征上的微小变化在概率上只会引入很小的变化。因些,在训练数据中上述句子之一的出现将会增加概率,不仅仅是那些句子,而且包括在句子空间中它们的“邻居”的组合数目。

1.2 之前工作

略。

2.一个神经模型

训练集是关于\(w_t \in V\)的一个序列\(w_1, \cdots, w_T\),其中词汇表V是一个有限的大集合。学习目标是学习一个好的模型,使得:

\[f(w_t, \cdots, w_{t-n+1}) = \hat{P}(w_t \mid w_1^{t-1})\]

也就是说给出很高的out-of-sample likelihood。下面,我们会上报关于\(1/\hat{P}(w_t \mid w_1^{t-1})\)的几何平均,它被称为“困惑度(perplexity)”,它也是平均负log似然的指数。模型的唯一限制是,对于\(w_1^{t-1}\)的任意选择,\(\sum\limits_{i=1}^{\mid V\mid} f(i, w_{t-1}, \cdots, w_{t-n+1}) = 1\),其中\(f>0\)。通过将这些条件概率相乘,可以获得一个关于这些词序列的联合概率的模型。

我们将函数\(f(w_t, \cdots, w_{t-n+1})= \hat{P}(w_1^{t-1})\)解耦成两部分:

  • 1.一个映射函数C,它将V的任意元素i映射到一个真实向量\(C(i) \in R^m\)。它表示与词典中每个词相关的分布式特征向量(distributed feature vectors)。实际上,C被表示成一个关于自由参数的\(\mid V \mid \times m\)的矩阵。
  • 2.词上的概率函数,由C进行表示:对于在上下文中的词,\((C(w_{t-n+1}), \cdots, C(w_{t-1}))\),会使用一个函数g将一个关于feature vectors的输入序列映射到一个关于下一个词\(w_t \in V\)的条件概率分布上。g的输出是一个vector,它的第i个元素可以估计概率\(\hat{P}(w_t = i \mid w_1^{t-1})\),如图1所示。
\[f(i, w_{t-1}, \cdots, w_{t-n+1}) = g(i, C(w_{t-1}), \cdots, C(w_{t-n+1}))\]

1.png

图1: 神经网络结构:\(f(i, w_{t-1}, \cdots, w_{t-n+1}) = g(i, C(w_{t-1}), \cdots, C(W_{t-n+1}))\),其中g是神经网络,C(i)是第i个word feature vector。

函数f是这两个mappings(C和g)的一个组合,其中C对于在上下文中所有词是共享的(shared)。这两部分每一个都与一些参数有关。mapping C的参数就简单的是feature vectors自身,通过一个\(\mid V\mid \times m\)的矩阵C进行表示,其中第i行表示第i个词的feature vector C(i)。函数g通过一个feed-forward或RNN或其它参数化函数(parametrized function)来实现,它使用参数\(\mathcal{W}\)。

训练通过搜索\(\theta\)来完成,它会在训练语料上最大化penalized log-likelihood:

\[L = \frac{1}{T} \sum\limits_{t} log f(w_t, w_{t-1}, \cdots, w_{t-n+1}; \theta) + R(\theta)\]

其中\(R(\theta)\)是一个正则项。例如,在我们的实验中,R是一个权重衰减项(weight cecay penalty),它只应用于神经网络的weights和矩阵C上,而非应用在biases上。

在上述模型中,自由参数(free parameters)的数目与词汇表中词数目V成线性比例。它也只与阶数n成线性比例:如果介入更多共享结构,例如,使用一个time-decay神经网络或一个RNN(或者一个关于两种网络的组合),比例因子可以被减小到sub-linear。

在以下大多数实验上,除word features mapping外,神经网络具有一个hidden layer,可选的,还有从word features到output上的直接连接(direct connections)。因此,实际有两个hidden layers:

  • 1.shared word features layer C:它是线性的
  • 2.普通的双曲正切( hyperbolic tangent) hidden layer

更精准的,神经网络会计算如下的函数,它使用一个softmax output layer,它会保证正例概率(positive probabilities)求和为1:

\[\hat{P}(w_t | w_{t-1}, \cdots, w_{t-n+1}) = \frac{e^{y_{w_t}}}{\sum\limits_{i} e^{y_i}}\]

其中,\(y_i\)是对于每个output word i的未归一化log概率,它会使用参数b, W, U, d和H,具体计算如下:

\[y = b + W x + U tanh(d+Hx)\]

…(1)

其中,双曲正切tanh以element-by-element的方式进行应用,W可选为0(即没有直接连接),x是word features layer activation vector,它是从矩阵C的input word features的拼接(concatenation):

\[x = (C(w_{t-1}), C(W_{t-2}), \cdots, C(W_{t-n+1}))\]

假设h是hidden units的数目,m是与每个词相关的features的数目。当从word features到outputs上没有直接连接(direct connections)时,矩阵W被设置为0。该模型的自由参数是output biases b(具有\(\mid V \mid\)个元素),hidden layer biases d(具有h个元素),hidden-to-output weights U(一个\(\mid V \mid \times h\)的矩阵),word features到output weights W(一个\(\mid V\mid \times (n-1) m\)的矩阵),hidden layer weights H(一个 \(h \times (n-1) m\)的矩阵),word features C(一个\(\mid V\mid \times m\)的矩阵):

\[\theta = (b,d,W,U,H,C)\]

自由参数的数目是 \(\mid V\mid (1 + nm + h) + h(1 + (n-1) m)\)。主导因子是\(\mid V\mid (nm+h)\)。注意,在理论上,如果在weights W和H上存在一个weight decay(C上没有),那么W和H可以收敛到0,而C将会增长。实际上,当使用SGA(随机梯度上升)训练时,我们不会观察到这样的行为。

在神经网络上进行SGA包含,包含在执行以下的在训练语料的第t个词之后的迭代更新中:

\[\theta \leftarrow \theta + \epsilon \frac{\partial log \hat{P}(w_t | w_{t-1}, \cdots, w_{t-n+1})}{\partial \theta}\]

其中,\(\epsilon\)是learning rate。注意,大部分参数不需要更新、或者在每个样本之后训练:\(C(j)\)的word features,不会出现在input window中。

混合模型。在我们的实验中,我们已经发现,通过将神经网络的概率预测与一个interpolated trigram model相组合,可以提升效果,使用一个固定的权重0.5,一个可学习权重(在验证集上达到最大似然),或者一个weights集合,是基于在context的频率为条件的(使用相似的过程:在interpolated trigram上组合trigram, bigram, and unigram)。

其它

略.

参考:

http://www.jmlr.org/papers/volume3/bengio03a/bengio03a.pdf