Word Embedding
One-hot表示
One-hot简称读热向量编码，也是特征工程中最常用的方法。其步骤如下：
- 构造文本分词后的字典，每个分词是一个比特值，比特值为0或者1。
- 每个分词的文本表示为该分词的比特位为1，其余位为0的矩阵表示。
每个词典索引对应比特位
One-hot表示文本信息的缺点：
- 随着语料库的增加，数据特征的维度会越来越大，产生一个维度很高，又很稀疏的矩阵。
- 这种表示方法的分词顺序和在句子中的顺序是无关的，不能保留词与词之间的关系信息。
词袋模型
词袋模型(Bag-of-words model)，像是句子或是文件这样的文字可以用一个袋子装着这些词的方式表现，这种表现方式不考虑文法以及词的顺序。
文档的向量表示可以直接将各词的词向量表示加和。
词袋模型同样有一下缺点：
- 词向量化后，词与词之间是有大小关系的，不一定词出现的越多，权重越大。
- 词与词之间是没有顺序关系的。
TF-IDF
TF意思是词频(Term Frequency)，IDF意思是逆文本频率指数(Inverse Document Frequency)。
字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。一个词语在一篇文章中出现次数越多, 同时在所有文档中出现次数越少, 越能够代表该文章。
那么，
，从这个公式可以看出，当w在文档中出现的次数增大时，而TF-IDF的值是减小的，所以也就体现了以上所说的了。
**缺点：**还是没有把词与词之间的关系顺序表达出来。
n-gram模型
n-gram模型为了保持词的顺序，做了一个滑窗的操作，这里的n表示的就是滑窗的大小，例如2-gram模型，也就是把2个词当做一组来处理，然后向后移动一个词的长度，再次组成另一组词，把这些生成一个字典，按照词袋模型的方式进行编码得到结果。改模型考虑了词的顺序。
**缺点：**随着n的大小增加，词表会成指数型膨胀，会越来越大。
离散表示存在的问题
由于存在以下的问题，对于一般的NLP问题，是可以使用离散表示文本信息来解决问题的，但对于要求精度较高的场景就不适合了。
- 无法衡量词向量之间的关系。
- 词表的维度随着语料库的增长而膨胀。
- n-gram词序列随语料库增长呈指数型膨胀，更加快。
- 离散数据来表示文本会带来数据稀疏问题，导致丢失了信息，与我们生活中理解的信息是不一样的。
共现矩阵
共现矩阵顾名思义就是共同出现的意思，词文档的共现矩阵主要用于发现主题(topic)，用于主题模型，如LSA。
中间的每个格子表示的是行和列组成的词组在词典中共同出现的次数，也就体现了共现的特性。
存在的问题：
- 向量维数随着词典大小线性增长。
- 存储整个词典的空间消耗非常大。
- 一些模型如文本分类模型会面临稀疏性问题。
- 模型会欠稳定，每新增一份语料进来，稳定性就会变化。
NNLM
NNLM (Neural Network Language model)，神经网络语言模型是03年提出来的，通过训练得到中间产物–词向量矩阵，这就是我们要得到的文本表示向量矩阵。
NNLM说的是定义一个前向窗口大小，其实和上面提到的窗口是一个意思。把这个窗口中最后一个词当做y，把之前的词当做输入x，通俗来说就是预测这个窗口中最后一个词出现概率的模型。
Word2Vec
谷歌2013年提出的Word2Vec是目前最常用的词嵌入模型之一。Word2Vec实际是一种浅层的神经网络模型，它有两种网络结构，**分别是CBOW（Continues Bag of Words）连续词袋和Skip-gram。**Word2Vec和上面的NNLM很类似，但比NNLM简单。
CBOW
CBOW获得中间词两边的的上下文，然后用周围的词去预测中间的词，把中间词当做y，把窗口中的其它词当做x输入，x输入是经过one-hot编码过的，然后通过一个隐层进行求和操作，最后通过激活函数softmax，可以计算出每个单词的生成概率，接下来的任务就是训练神经网络的权重，使得语料库中所有单词的整体生成概率最大化，而求得的权重矩阵就是文本表示词向量的结果。
Skip-gram：
Skip-gram是通过当前词来预测窗口中上下文词出现的概率模型，把当前词当做x，把窗口中其它词当做y，依然是通过一个隐层接一个Softmax激活函数来预测其它词的概率。如下图所示：
优化方法：
- 层次Softmax：至此还没有结束，因为如果单单只是接一个softmax激活函数，计算量还是很大的，有多少词就会有多少维的权重矩阵，所以这里就提出层次Softmax(Hierarchical Softmax)，使用Huffman Tree来编码输出层的词典，相当于平铺到各个叶子节点上，瞬间把维度降低到了树的深度，可以看如下图所示。这课Tree把出现频率高的词放到靠近根节点的叶子节点处，每一次只要做二分类计算，计算路径上所有非叶子节点词向量的贡献即可。
Glove
GloVe的全称叫Global Vectors for Word Representation，它是一个基于全局词频统计（count-based & overall statistics）的词表征（word representation）工具，它可以把一个单词表达成一个由实数组成的向量，这些向量捕捉到了单词之间一些语义特性，比如相似性（similarity）、类比性（analogy）等。**我们通过对向量的运算，比如欧几里得距离或者cosine相似度，可以计算出两个单词之间的语义相似性。
2.1 构建共现矩阵
什么是共现矩阵？
共现矩阵顾名思义就是共同出现的意思，词文档的共现矩阵主要用于发现主题(topic)，用于主题模型，如LSA。
局域窗中的word-word共现矩阵可以挖掘语法和语义信息，例如：
- I like deep learning.
- I like NLP.
- I enjoy flying
有以上三句话，设置滑窗为2，可以得到一个词典：{“I like”,“like deep”,“deep learning”,“like NLP”,“I enjoy”,“enjoy flying”,“I like”}。
我们可以得到一个共现矩阵(对称矩阵)：
中间的每个格子表示的是行和列组成的词组在词典中共同出现的次数，也就体现了共现的特性。
GloVe的共现矩阵
根据语料库（corpus）构建一个共现矩阵（Co-ocurrence Matrix）X，**矩阵中的每一个元素 Xij 代表单词 i 和上下文单词 j 在特定大小的上下文窗口（context window）内共同出现的次数。*一般而言，这个次数的最小单位是1，但是GloVe不这么认为：它根据两个单词在上下文窗口的距离 d，提出了一个衰减函数（decreasing weighting）：decay=1/d 用于计算权重，也就是说*距离越远的两个单词所占总计数（total count）的权重越小。
2.2 词向量和共现矩阵的近似关系
构建词向量（Word Vector）和共现矩阵（Co-ocurrence Matrix）之间的近似关系，论文的作者提出以下的公式可以近似地表达两者之间的关系：
其中，是我们最终要求解的词向量；
分别是两个词向量的bias term。当然你对这个公式一定有非常多的疑问，比如它到底是怎么来的，为什么要使用这个公式，为什么要构造两个词向量
？请参考文末的参考文献。
2.3 构造损失函数
有了2.2的公式之后我们就可以构造它的loss function了：
这个loss function的基本形式就是最简单的mean square loss，只不过在此基础上加了一个权重函数，那么这个函数起了什么作用，为什么要添加这个函数呢？我们知道在一个语料库中，肯定存在很多单词他们在一起出现的次数是很多的（frequent co-occurrences），那么我们希望：
- 这些单词的权重要大于那些很少在一起出现的单词（rare co-occurrences），所以这个函数要是非递减函数（non-decreasing）；
- 但我们也不希望这个权重过大（overweighted），当到达一定程度之后应该不再增加；
- 如果两个单词没有在一起出现，也就是
，那么他们应该不参与到 loss function 的计算当中去，也就是f(x) 要满足 f(0)=0。
满足以上三个条件的函数有很多，论文作者采用了如下形式的分段函数：
这个函数图像如下所示：
2.4 训练GloVe模型
虽然很多人声称GloVe是一种无监督（unsupervised learing）的学习方式（因为它确实不需要人工标注label），但其实它还是有label的，这个label就是以上公式中的 log(Xij)，而公式中的向量 w和w~w和w~ 就是要不断更新/学习的参数，所以本质上它的训练方式跟监督学习的训练方法没什么不一样，都是基于梯度下降的。
具体地，这篇论文里的实验是这么做的：**采用了AdaGrad的梯度下降算法，对矩阵 X 中的所有非零元素进行随机采样，学习曲率（learning rate）设为0.05，在vector size小于300的情况下迭代了50次，其他大小的vectors上迭代了100次，直至收敛。**最终学习得到的是两个vector是 w和w~w和w，因为 X 是对称的（symmetric），所以从原理上讲 w和ww和w~ 是也是对称的，他们唯一的区别是初始化的值不一样，而导致最终的值不一样。
所以这两者其实是等价的，都可以当成最终的结果来使用。但是为了提高鲁棒性，我们最终会选择两者之和 **作为最终的vector（两者的初始化不同相当于加了不同的随机噪声，所以能提高鲁棒性）。**在训练了400亿个token组成的语料后，得到的实验结果如下图所示：
这个图一共采用了三个指标：语义准确度，语法准确度以及总体准确度。那么我们不难发现Vector Dimension在300时能达到最佳，而context Windows size大致在6到10之间。
3. GloVe与LSA、Word2Vec的比较
LSA（Latent Semantic Analysis）是一种比较早的count-based的词向量表征工具，它也是基于co-occurance matrix的，只不过采用了基于奇异值分解（SVD）的矩阵分解技术对大矩阵进行降维，而我们知道SVD的复杂度是很高的，所以它的计算代价比较大。还有一点是它对所有单词的统计权重都是一致的。而这些缺点在GloVe中被一一克服了。
而word2vec最大的缺点则是没有充分利用所有的语料，所以GloVe其实是把两者的优点结合了起来。从这篇论文给出的实验结果来看，GloVe的性能是远超LSA和word2vec的，但网上也有人说GloVe和word2vec实际表现其实差不多。
textRNN
什么是textRNN
textRNN指的是利用RNN循环神经网络解决文本分类问题，文本分类是自然语言处理的一个基本任务，试图推断出给定文本(句子、文档等)的标签或标签集合。
文本分类的应用非常广泛，如：
- 垃圾邮件分类：2分类问题，判断邮件是否为垃圾邮件
- 情感分析：2分类问题：判断文本情感是积极还是消极；多分类问题：判断文本情感属于{非常消极，消极，中立，积极，非常积极}中的哪一类。
- 新闻主题分类：判断一段新闻属于哪个类别，如财经、体育、娱乐等。根据类别标签的数量，可以是2分类也可以是多分类。
- 自动问答系统中的问句分类
- 社区问答系统中的问题分类：多标签多分类(对一段文本进行多分类，该文本可能有多个标签)，如知乎看山杯
- 让AI做法官：基于案件事实描述文本的罚金等级分类(多分类)和法条分类(多标签多分类)
- 判断新闻是否为机器人所写：2分类
1.1 textRNN的原理
在一些自然语言处理任务中，当对序列进行处理时，我们一般会采用循环神经网络RNN，尤其是它的一些变种，如LSTM(更常用)，GRU。当然我们也可以把RNN运用到文本分类任务中。
这里的文本可以一个句子，文档(短文本，若干句子)或篇章(长文本)，因此每段文本的长度都不尽相同。在对文本进行分类时，我们一般会指定一个固定的输入序列/文本长度：该长度可以是最长文本/序列的长度，此时其他所有文本/序列都要进行填充以达到该长度；该长度也可以是训练集中所有文本/序列长度的均值，此时对于过长的文本/序列需要进行截断，过短的文本则进行填充。总之，要使得训练集中所有的文本/序列长度相同，该长度除之前提到的设置外，也可以是其他任意合理的数值。在测试时，也需要对测试集中的文本/序列做同样的处理。
首先我们需要对文本进行分词，然后指定一个序列长度n（大于n的截断，小于n的填充），并使用词嵌入得到每个词固定维度的向量表示。对于每一个输入文本/序列，我们可以在RNN的每一个时间步长上输入文本中一个单词的向量表示，计算当前时间步长上的隐藏状态，然后用于当前时间步骤的输出以及传递给下一个时间步长并和下一个单词的词向量一起作为RNN单元输入，然后再计算下一个时间步长上RNN的隐藏状态，以此重复…直到处理完输入文本中的每一个单词，由于输入文本的长度为n，所以要经历n个时间步长。
基于RNN的文本分类模型非常灵活，有多种多样的结构。接下来，我们主要介绍两种典型的结构。
2. textRNN网络结构
2.1 structure 1
流程：embedding—>BiLSTM—>concat final output/average all output—–>softmax layer
结构图如下图所示：
一般取前向/反向LSTM在最后一个时间步长上隐藏状态，然后进行拼接，在经过一个softmax层(输出层使用softmax激活函数)进行一个多分类；或者取前向/反向LSTM在每一个时间步长上的隐藏状态，对每一个时间步长上的两个隐藏状态进行拼接，然后对所有时间步长上拼接后的隐藏状态取均值，再经过一个softmax层(输出层使用softmax激活函数)进行一个多分类(2分类的话使用sigmoid激活函数)。
上述结构也可以添加dropout/L2正则化或BatchNormalization 来防止过拟合以及加速模型训练。
2.2 structure 2
流程：embedding–>BiLSTM—->(dropout)–>concat ouput—>UniLSTM—>(droput)–>softmax layer
结构图如下图所示：
与之前结构不同的是，在双向LSTM(上图不太准确，底层应该是一个双向LSTM)的基础上又堆叠了一个单向的LSTM。把双向LSTM在每一个时间步长上的两个隐藏状态进行拼接，作为上层单向LSTM每一个时间步长上的一个输入，最后取上层单向LSTM最后一个时间步长上的隐藏状态，再经过一个softmax层(输出层使用softamx激活函数，2分类的话则使用sigmoid)进行一个多分类。
2.3 总结
TextRNN的结构非常灵活，可以任意改变。比如把LSTM单元替换为GRU单元，把双向改为单向，添加dropout或BatchNormalization以及再多堆叠一层等等。TextRNN在文本分类任务上的效果非常好，与TextCNN不相上下，但RNN的训练速度相对偏慢，一般2层就已经足够多了。
3. 什么是textCNN
在“卷积神经⽹络”中我们探究了如何使⽤⼆维卷积神经⽹络来处理⼆维图像数据。在之前的语⾔模型和⽂本分类任务中，我们将⽂本数据看作是只有⼀个维度的时间序列，并很⾃然地使⽤循环神经⽹络来表征这样的数据。其实，我们也可以将⽂本当作⼀维图像，从而可以⽤⼀维卷积神经⽹络来捕捉临近词之间的关联。本节将介绍将卷积神经⽹络应⽤到⽂本分析的开创性⼯作之⼀：textCNN。
3.1 ⼀维卷积层
在介绍模型前我们先来解释⼀维卷积层的⼯作原理。与⼆维卷积层⼀样，⼀维卷积层使⽤⼀维的互相关运算。在⼀维互相关运算中，卷积窗口从输⼊数组的最左⽅开始，按从左往右的顺序，依次在输⼊数组上滑动。当卷积窗口滑动到某⼀位置时，窗口中的输⼊⼦数组与核数组按元素相乘并求和，得到输出数组中相应位置的元素。如下图所⽰，输⼊是⼀个宽为7的⼀维数组，核数组的宽为2。可以看到输出的宽度为 7 - 2 + 1 = 6，且第⼀个元素是由输⼊的最左边的宽为2的⼦数组与核数组按元素相乘后再相加得到的：0 × 1 + 1 × 2 = 2。
多输⼊通道的⼀维互相关运算也与多输⼊通道的⼆维互相关运算类似：在每个通道上，将核与相应的输⼊做⼀维互相关运算，并将通道之间的结果相加得到输出结果。下图展⽰了含3个输⼊ 通道的⼀维互相关运算，其中阴影部分为第⼀个输出元素及其计算所使⽤的输⼊和核数组元素： 0 × 1 + 1 × 2 + 1 × 3 + 2 × 4 + 2 × (-1) + 3 × (-3) = 2。
由⼆维互相关运算的定义可知，多输⼊通道的⼀维互相关运算可以看作单输⼊通道的⼆维互相关运算。如下图所⽰，我们也可以将上图中多输⼊通道的⼀维互相关运算以等价的单输⼊通道的⼆维互相关运算呈现。这⾥核的⾼等于输⼊的⾼。下图的阴影部分为第⼀个输出元素及其计算所使⽤的输⼊和核数组元素：2 × (-1) + 3 × (-3) + 1 × 3 + 2 × 4 + 0 × 1 + 1 × 2 = 2。
以上都是输出都只有⼀个通道。我们在“多输⼊通道和多输出通道”⼀节中介绍了如何在⼆维卷积层中指定多个输出通道。类似地，我们也可以在⼀维卷积层指定多个输出通道，从而拓展卷积层中的模型参数。
3. 2 时序最⼤池化层
类似地，我们有⼀维池化层。textCNN中使⽤的时序最⼤池化（max-over-time pooling）层实际上对应⼀维全局最⼤池化层：假设输⼊包含多个通道，各通道由不同时间步上的数值组成，各通道的输出即该通道所有时间步中最⼤的数值。因此，时序最⼤池化层的输⼊在各个通道上的时间步数可以不同。为提升计算性能，我们常常将不同⻓度的时序样本组成⼀个小批量，并通过在较短序列后附加特殊字符（如0）令批量中各时序样本⻓度相同。这些⼈为添加的特殊字符当然是⽆意义的。由于时序最⼤池化的主要⽬的是抓取时序中最重要的特征，它通常能使模型不受⼈为添加字符的影响。
3.3 textCNN模型
textCNN模型主要使⽤了⼀维卷积层和时序最⼤池化层。假设输⼊的⽂本序列由n个词组成，每个词⽤d维的词向量表⽰。那么输⼊样本的宽为n，⾼为1，输⼊通道数为d。textCNN的计算主要分为以下⼏步：
- 定义多个⼀维卷积核，并使⽤这些卷积核对输⼊分别做卷积计算。宽度不同的卷积核可能会捕捉到不同个数的相邻词的相关性。
- 对输出的所有通道分别做时序最⼤池化，再将这些通道的池化输出值连结为向量。
- 通过全连接层将连结后的向量变换为有关各类别的输出。这⼀步可以使⽤丢弃层应对过拟合。
下图⽤⼀个例⼦解释了textCNN的设计。这⾥的输⼊是⼀个有11个词的句⼦，每个词⽤6维词向量表⽰。因此输⼊序列的宽为11，输⼊通道数为6。给定2个⼀维卷积核，核宽分别为2和4，输出通道数分别设为4和5。因此，⼀维卷积计算后，4个输出通道的宽为 11 - 2 + 1 = 10，而其他5个通道的宽为 11 - 4 + 1 = 8。尽管每个通道的宽不同，我们依然可以对各个通道做时序最⼤池化，并将9个通道的池化输出连结成⼀个9维向量。最终，使⽤全连接将9维向量变换为2维输出，即正⾯情感和负⾯情感的预测。
seq2seq
1. 什么是seq2seq
在⾃然语⾔处理的很多应⽤中，输⼊和输出都可以是不定⻓序列。以机器翻译为例，输⼊可以是⼀段不定⻓的英语⽂本序列，输出可以是⼀段不定⻓的法语⽂本序列，例如：
英语输⼊：“They”、“are”、“watching”、“.”
法语输出：“Ils”、“regardent”、“.”
当输⼊和输出都是不定⻓序列时，我们可以使⽤编码器—解码器（encoder-decoder）或者seq2seq模型。序列到序列模型，简称seq2seq模型。这两个模型本质上都⽤到了两个循环神经⽹络，分别叫做编码器和解码器。编码器⽤来分析输⼊序列，解码器⽤来⽣成输出序列。两 个循环神经网络是共同训练的。
下图描述了使⽤编码器—解码器将上述英语句⼦翻译成法语句⼦的⼀种⽅法。在训练数据集中，我们可以在每个句⼦后附上特殊符号“
2. 编码器
编码器的作⽤是把⼀个不定⻓的输⼊序列变换成⼀个定⻓的背景变量 c，并在该背景变量中编码输⼊序列信息。常⽤的编码器是循环神经⽹络。
让我们考虑批量⼤小为1的时序数据样本。假设输⼊序列是 x1, . . . , xT，例如 xi 是输⼊句⼦中的第 i 个词。在时间步 t，循环神经⽹络将输⼊ xt 的特征向量 xt 和上个时间步的隐藏状态 变换为当前时间步的隐藏状态ht。我们可以⽤函数 f 表达循环神经⽹络隐藏层的变换：
接下来，编码器通过⾃定义函数 q 将各个时间步的隐藏状态变换为背景变量：
例如，当选择 q(h1*, . . . ,* hT ) = hT 时，背景变量是输⼊序列最终时间步的隐藏状态hT。
以上描述的编码器是⼀个单向的循环神经⽹络，每个时间步的隐藏状态只取决于该时间步及之前的输⼊⼦序列。我们也可以使⽤双向循环神经⽹络构造编码器。在这种情况下，编码器每个时间步的隐藏状态同时取决于该时间步之前和之后的⼦序列（包括当前时间步的输⼊），并编码了整个序列的信息。
3. 解码器
刚刚已经介绍，编码器输出的背景变量 c 编码了整个输⼊序列 x1, . . . , xT 的信息。给定训练样本中的输出序列 y1, y2, . . . , yT′ ，对每个时间步 t′（符号与输⼊序列或编码器的时间步 t 有区别），解码器输出 yt′ 的条件概率将基于之前的输出序列
和背景变量 c，即：
为此，我们可以使⽤另⼀个循环神经⽹络作为解码器。在输出序列的时间步 t′，解码器将上⼀时间步的输出 
以及背景变量 c 作为输⼊，并将它们与上⼀时间步的隐藏状态 
变换为当前时间步的隐藏状态st′。因此，我们可以⽤函数 g 表达解码器隐藏层的变换：
有了解码器的隐藏状态后，我们可以使⽤⾃定义的输出层和softmax运算来计算 
，例如，基于当XQ前时间步的解码器隐藏状态 st′、上⼀时间步的输出以及背景变量 c 来计算当前时间步输出 yt′ 的概率分布。
4. 训练模型
根据最⼤似然估计，我们可以最⼤化输出序列基于输⼊序列的条件概率：
并得到该输出序列的损失：
在模型训练中，所有输出序列损失的均值通常作为需要最小化的损失函数。在上图所描述的模型预测中，我们需要将解码器在上⼀个时间步的输出作为当前时间步的输⼊。与此不同，在训练中我们也可以将标签序列（训练集的真实输出序列）在上⼀个时间步的标签作为解码器在当前时间步的输⼊。这叫作强制教学（teacher forcing）。
5. seq2seq模型预测
以上介绍了如何训练输⼊和输出均为不定⻓序列的编码器—解码器。本节我们介绍如何使⽤编码器—解码器来预测不定⻓的序列。
在准备训练数据集时，我们通常会在样本的输⼊序列和输出序列后面分别附上⼀个特殊符号“
种。这些输出序列中所有特殊符号“
5.1 贪婪搜索
贪婪搜索（greedy search）。对于输出序列任⼀时间步t′，我们从|Y|个词中搜索出条件概率最⼤的词：
作为输出。⼀旦搜索出“
。我们将该条件概率最⼤的输出序列称为最优输出序列。而贪婪搜索的主要问题是不能保证得到最优输出序列。
下⾯来看⼀个例⼦。假设输出词典⾥⾯有“A”“B”“C”和“
接下来，观察下面演⽰的例⼦。与上图中不同，在时间步2中选取了条件概率第⼆⼤的词“C” 。由于时间步3所基于的时间步1和2的输出⼦序列由上图中的“A”“B”变为了下图中的“A”“C”，下图中时间步3⽣成各个词的条件概率发⽣了变化。我们选取条件概率最⼤的词“B”。此时时间步4所基于的前3个时间步的输出⼦序列为“A”“C”“B”，与上图中的“A”“B”“C”不同。因此，下图中时间步4⽣成各个词的条件概率也与上图中的不同。我们发现，此时的输出序列“A”“C”“B”“
5.2 穷举搜索
如果⽬标是得到最优输出序列，我们可以考虑穷举搜索（exhaustive search）：穷举所有可能的输出序列，输出条件概率最⼤的序列。
虽然穷举搜索可以得到最优输出序列，但它的计算开销
很容易过⼤。例如，当|Y| =10000且T′ = 10时，我们将评估 个序列：这⼏乎不可能完成。而贪婪搜索的计算开销是
，通常显著小于穷举搜索的计算开销。例如，当|Y| = 10000且T′ = 10时，我们只需评估个序列。
5.3 束搜索
束搜索（beam search）是对贪婪搜索的⼀个改进算法。它有⼀个束宽（beam size）超参数。我们将它设为 k。在时间步 1 时，选取当前时间步条件概率最⼤的 k 个词，分别组成 k 个候选输出序列的⾸词。在之后的每个时间步，基于上个时间步的 k 个候选输出序列，从 k |Y| 个可能的输出序列中选取条件概率最⼤的 k 个，作为该时间步的候选输出序列。最终，我们从各个时间步的候选输出序列中筛选出包含特殊符号“
束宽为2，输出序列最⼤⻓度为3。候选输出序列有A、C、AB、CE、ABD和CED。我们将根据这6个序列得出最终候选输出序列的集合。在最终候选输出序列的集合中，我们取以下分数最⾼的序列作为输出序列：
其中 L 为最终候选序列⻓度，α ⼀般可选为0.75。分⺟上的 Lα 是为了惩罚较⻓序列在以上分数中较多的对数相加项。分析可知，束搜索的计算开销为
。这介于贪婪搜索和穷举搜索的计算开销之间。此外，贪婪搜索可看作是束宽为 1 的束搜索。束搜索通过灵活的束宽 k 来权衡计算开销和搜索质量。
6. Bleu得分
评价机器翻译结果通常使⽤BLEU（Bilingual Evaluation Understudy）(双语评估替补)。对于模型预测序列中任意的⼦序列，BLEU考察这个⼦序列是否出现在标签序列中。
具体来说，设词数为 n 的⼦序列的精度为 pn。它是预测序列与标签序列匹配词数为 n 的⼦序列的数量与预测序列中词数为 n 的⼦序列的数量之⽐。举个例⼦，假设标签序列为A、B、C、D、E、F，预测序列为A、B、B、C、D，那么：
预测序列一元词组：A/B/C/D，都在标签序列里存在，所以P1=4/5，以此类推，p2 = 3/4, p3 = 1/3, p4 = 0。设 分别为标签序列和预测序列的词数，那么，BLEU的定义为：
其中 k 是我们希望匹配的⼦序列的最⼤词数。可以看到当预测序列和标签序列完全⼀致时，BLEU为1。
因为匹配较⻓⼦序列⽐匹配较短⼦序列更难，BLEU对匹配较⻓⼦序列的精度赋予了更⼤权重。例如，当 pn 固定在0.5时，随着n的增⼤，
。另外，模型预测较短序列往往会得到较⾼pn 值。因此，上式中连乘项前⾯的系数是为了惩罚较短的输出而设的。举个例⼦，当k = 2时，假设标签序列为A、B、C、D、E、F，而预测序列为A、 B。虽然p1 = p2 = 1，但惩罚系数exp(1-6/2) ≈ 0.14，因此BLEU也接近0.14。