我只是很困惑,因为我很难理解这种差异。如果我们将光束大小设置为等于可能状态的数量,那是不是意味着光束搜索算法等效于维特比算法?
我能想到的两者之间唯一真正的区别是波束搜索不能保证找到最佳解决方案,而维特比算法可以。但是,假设计算能力不是问题,如果我们将光束大小设置为与输出空间相等,那么我们最终不是也找到了最优解吗?
我只是很困惑,因为我很难理解这种差异。如果我们将光束大小设置为等于可能状态的数量,那是不是意味着光束搜索算法等效于维特比算法?
我能想到的两者之间唯一真正的区别是波束搜索不能保证找到最佳解决方案,而维特比算法可以。但是,假设计算能力不是问题,如果我们将光束大小设置为与输出空间相等,那么我们最终不是也找到了最优解吗?
是的,你完全正确。如果您将光束大小设置为等于 HMM 或 CRF 状态空间的大小(我假设您所说的“输出空间”的意思),那么您可以保证找到最佳解决方案。这是因为您的搜索现在已经详尽无遗。
束大小是在您浏览时间序列时要在搜索中扩展的候选者数量。如果你把它们全部展开,那么这就是维特比算法。
回想一下,维特比算法的时间复杂度是, 在哪里是时间序列的长度,并且是状态空间的大小。二次缩放的事实是激发光束搜索的原因:减少至对于一些,以准确性为代价。如果状态空间很小,那并不是很大的改进。但是,如果可能有数千个状态(如使用 WFSA 语言模型),那么这会产生很大的不同。
如果我们将光束大小设置为等于可能状态的数量,那是不是意味着光束搜索算法等效于维特比算法?
资料来源:NLP Programming Tutorial 13 - Beam and A* Search by Graham Neubig 教授
然后反过来就是将beam search转化为Viterbi的过程。
如果我们将光束大小设置为与输出空间相等,那么我们最终不会找到最优解吗?
因为在 Beam Search 中,搜索空间中一些没有希望的部分被剪掉了,然后我们不能应用广义分配律,因此它不能保证最优路径。同样,如果考虑到所有搜索空间,则可以通向最佳路径。