隐马尔可夫模型
简介
序列建模方法
应用于自然语言处理、语音识别、生物信息学、金融等领域
基本组成
模型参数
初始状态概率
状态转移概率
发射概率
描述状态之间的转移和状态与观测之间的关系
概率分布
每个时刻的状态都有一个概率分布
表示可能处于各个状态的概率
每个状态对应一个发射概率分布
表示在该状态下观测到不同元素的概率
发射概率
表示在某个隐藏状态下，观测变量的取值的概率分布，也就是描述隐藏状态到观测变量的映射关系
通俗地说，发射概率是观测到某个特定的数据，是由哪个隐藏状态生成的概率
假设有一个音频信号被分成了多个时间片段，那么发射概率就描述了每个时间片段在某个语音状态下所对应的语音特征的概率分布，这些语音状态可能是"说话者A在说'你好'"或"说话者B在说'再见'"等等
状态转移概率
表示从一个隐藏状态转移到另一个隐藏状态的概率，也就是描述隐藏状态之间的转移关系。
通俗地说，状态转移概率是在一个隐藏状态下，转移到另一个隐藏状态的概率。
例如，在自然语言处理中，状态转移概率可以描述从名词状态转移到动词状态的概率，从形容词状态转移到名词状态的概率等等。
维特比搜索
维特比搜索（Viterbi Algorithm）是一种常见的动态规划算法，主要用于在概率图模型（如隐马尔可夫模型）中寻找最可能的序列。
假设我们有一个序列（如单词、音频信号等）和一个隐含的状态序列（如单词序列对应的词性序列），我们想要找到最可能的词性序列，即给定序列的条件下，对应的最可能的状态序列。
维特比搜索算法的核心思想是使用动态规划技术，将问题分解为多个子问题，并利用子问题的最优解构建整个问题的最优解。在隐马尔可夫模型中，我们首先将观测序列中的每个元素（如单词）与每个可能的状态（如不同的词性）进行配对，并计算从该状态开始产生观测序列中该元素的概率。这些概率值被称为发射概率。
然后，我们考虑如何从上一个状态中转移到当前状态，即转移概率。我们使用先前计算的发射概率和转移概率，以及先前状态的最优路径，来计算当前状态的最优路径。通过这种方式，我们递归地构建出所有状态的最优路径，并找到概率最大的路径，即为最可能的状态序列。<br><br>
具体来说，维特比搜索算法包括以下步骤：
初始化：将第一个观测元素（如第一个单词）与所有可能的状态进行匹配，并将每个状态的概率值初始化为对应的发射概率。
递推：对于每个后续的观测元素（如第二个单词、第三个单词等），对于每个可能的状态，计算从先前的状态转移到当前状态的概率（即转移概率），并将该概率值加上当前状态的发射概率。然后，选择具有最大概率值的路径作为当前状态的最优路径，并将该路径的概率值存储在一个表格中。
终止：在观测序列的最后一个元素处，选择具有最大概率值的状态作为终止状态，并回溯所有状态的最优路径。
通过维特比搜索算法，我们可以在隐马尔可夫模型等概率图模型中，高效地寻找最可能的序列，这在自然语言处理等领域有广泛的应用。
ctc prefix beam search 与 Viterbi搜索的区别是什么
它们的区别在于搜索策略和计算方式上
CTC前缀束搜索算法是一种基于前缀搜索的算法，它维护多个前缀，并根据概率分布计算每个前缀的得分，得分高的前缀被保留，得分低的前缀被丢弃。同时，CTC前缀束搜索算法还引入了前缀约束，即对搜索过程中每个前缀的约束，通过引入前缀约束，CTC前缀束搜索可以更好地控制搜索空间，提高搜索效率和解码准确率。在CTC中，CTC前缀束搜索算法用于寻找最优的输出序列。
Viterbi解码是一种基于动态规划的算法，用于寻找最优的状态序列，即使得观测序列概率最大的状态序列。Viterbi算法的基本思想是通过递推计算每个时刻每个状态的最大概率值，并保存最大值对应的状态路径。在CTC中，Viterbi算法用于寻找最优的输出序列，即最可能的标记序列。
CTC Prefix Beam Search 与 CTC WFST Beam Search的区别
CTC Prefix Beam Search和CTC WFST Beam Search的主要区别在于解码方式的不同。
CTC Prefix Beam Search是一种基于前缀树的贪心算法，它通过维护候选路径集合来扩展搜索空间；
而CTC WFST Beam Search是一种基于WFST的解码方法，它通过将输出转化为一个WFST图来描述标签序列，并在该图上进行限制搜索。与CTC Prefix Beam Search不同，CTC WFST Beam Search使用基于最小规则的剪枝算法来减少搜索空间，提高搜索效率。
