前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Beam Search

Beam Search

作者头像
CodeInHand
发布2018-06-07 11:53:40
1.7K0
发布2018-06-07 11:53:40
举报
文章被收录于专栏:Pytorch实践

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,...等得分都很高,这样导致最后得到的回复非常相似。例如“你好”,“你好啊”,“你好呢”,“你好吗”等。

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-04-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 CodeInHand 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
腾讯智能对话平台
腾讯智能对话平台(Tencent Bot Platform,TBP)专注于“对话即服务”的愿景,全面开放腾讯对话系统核心技术,为大型企业客户、开发者和生态合作伙伴提供开发平台和机器人中间件能力,实现便捷、低成本构建人机对话体验和高效、多样化赋能行业。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档