Beam Search

Beam Search并不是很陌生的算法,它和深度优先算法、广度优先算法一样都曾被使用于树结构的搜索。本文重提Beam Search主要是因为在智能对话生成式模型中,Beam Search被应用在解码过程。而对话系统的生成式模型,本公众号也曾经进行过介绍。

本文主要解决如下三个问题:

Q1: 在生成式对话系统中,为什么会使用Beam Search算法?

Q2: Beam Search的具体原理是什么?

Q3: 对话系统中,为生成更好的回复,对Beam Search可以做什么改进?

对于Q1,首先就要回顾一下生成式模型了,简单的理解为给定一句话X=[x1,x2,x3,...,xn],需要生成对应的回复Y=[y1,y2,...,ym],何为生成式模型,其实就和机器学习中的生成模型一样(机器学习中的模型一般分为判别模型和生成模型),也就是按照条件概率P(Y|X)去生成答案。首先对X进行建模(一般使用RNN模型),然后得到X的编码之后,解码生成回复Y中的每个词语(同样使用RNN模型)。那Beam Search是用在哪呢?就是解码过程,使用RNN只能得到一个序列的隐层输出,如何由隐层状态得到对应的词语,就需要计算概率了,而这个概率一般是通过softmax函数得到。最早的解码过程中,t时刻的词语是通过计算概率P(yt | y1,y2,...yt-1,X)得到,然后在词典中采样得到,但是这种结果没考虑前后词语,容易出现叠词或无意义的助词,例如“你好啊啊啊啊啊”,这样出现多个“啊”。使用Beam Search的原因,不是保证每个时刻得到单个词的概率最大,而是要保证y1,y2,...ym这个序列的联合概率最大。

对于Q2,这里主要从解码过程进行介绍Beam Search的基本原理。之前也说过,解码的模型是使得P(Y|X)最大。Beam Search简单地可以理解为包搜索,就是每次算法会维持一个Beam,Beam里就是已经解码出来的Top K个候选,K表示Beam Size大小,Top K的计算就是按概率的大小排序。例如在t-1时刻,我们得到了K个候选,每个候选的得分可以表示为:

在t时刻,每个候选需要保存前K个词语,此时得到的y1,y2...,yt-1, yt的序列个数为K*K个,再将这K*K个候选重新按照上述得分计算公式排序,选取Top K作为下一时刻的候选。以此循环,如下所示。

需要解释的是,为啥下一时刻的score是上一时刻的score加上此时刻的概率。主要在于对概率取log对数,其实相当于p(y1)*p(y2)*...*p(yt),是概率乘积,对应于独立事件的概率计算。

对于Q3,由于上述的Beam Search容易陷入局部最优,或者说容易让某个Beam起到主导作用,这时解码产生的回复,Beam中的候选很相似,让回复比较单一。目前为使得回复比较有意义,而不是通用的一些回复类似“好的”、“是的”、“嗯”这样的,有大量工作对Beam Search进行改进,其中一个就是针对Beam中候选集排序加入惩罚项,具体如下所示:

加入惩罚项的原因在于,避免一个Beam中Top 1得分很高时,对应的Top 2,3,4,...等得分都很高,这样导致最后得到的回复非常相似。例如“你好”,“你好啊”,“你好呢”,“你好吗”等。

(欢迎关注公众号,一起学习探讨)

本文分享自微信公众号 - CodeInHand(CodeInHand),作者:小左

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-04-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Pytorch实现CNN时间序列预测

    本公众号曾经推出过PyTorch实现的LSTM时间序列预测,并开源了其源码。细心的童鞋可能发现了,我之前使用的LSTM是生成式模型,而不是使用判别式进行预测。换...

    CodeInHand
  • Tensorflow实现部分参数梯度更新

    在深度学习中,迁移学习经常被使用,在大数据集上预训练的模型迁移到特定的任务,往往需要保持模型参数不变,而微调与任务相关的模型层。本文主要介绍,使用tensorf...

    CodeInHand
  • 微软小冰的设计与实现

    小冰设计相关的论文多年来一直没有对外公布,得益于近几年小冰的快速发展,在对话领域形成技术壁垒。与此同时拥有大量的用户和数据,我们才有幸看到如下的...

    CodeInHand
  • PHP之父:PHP7 性能翻倍关键大揭秘

    原文出处: ithome 20岁老牌网页程序语言PHP,最快将在10月底释出PHP 7新版,这是十年来的首次大改版,最大特色是在性能上的大突破,能比前一版PHP...

    wangxl
  • PHP7 性能翻倍关键大揭露

    20岁老牌网页程序语言PHP,最快将在10月底释出PHP 7新版,这是十年来的首次大改版,最大特色是在性能上的大突破,能比前一版PHP 5快上一倍,PHP之...

    wangxl
  • PHP小白要知道:PHP7 性能为何能翻倍的关键因素是什么

    沈唁
  • 用Swift写一个响应式编程库

    关键时刻,第一时间送达! ? ? 2017年又快过去了,忙了一年感觉没啥收获,感觉是不是应该写点啥,想了好久没想出要写什么。下半年因为工作的原因,狗狗也没养了,...

    企鹅号小编
  • 用Swift写一个响应式编程库

    2017年又快过去了,忙了一年感觉没啥收获,感觉是不是应该写点啥,想了好久没想出要写什么。下半年因为工作的原因,狗狗也没养了,吉他上也积满了灰尘,兴致勃勃的学习...

    企鹅号小编
  • 蓝桥楼赛第23期-新冠疫情数据统计

    2020 年,新冠疫情肆掠全球。约翰·霍普金斯大学 跟踪了全球病例数据,包括总病例数、COVID-19 传播速度以及全球爆发情况。我们拿到了截止于某日的疫情数据...

    Spaceack
  • 定制rpm包-Yum环境搭建

    1.1 在yum服务器上创建yum仓库命令 1 mkdir -p /application/nginx/html/yum 2 cd /application/n...

    惨绿少年

扫码关注云+社区

领取腾讯云代金券