维特比算法参数估计

⑴ 纠错码的基本原理和性能参数

纠错码能够检错或纠错，主要是靠码字之间有较大的差别。这可用码字之间的汉明距离d(x，y)来衡量。它的定义为码字x与y之间的对应位取不同值的码元个数。一种纠错码的最小距离d定义为该种码中任两个码字之间的距离的最小值。一种码要能发现e个错误,它的最小距离d应不小于e+1。若要能纠正t个错误，则d应不小于2t+1。一个码字中非零码元的个数，称为此码字的汉明重量。一种码中非零码字的重量的最小值，称为该码的最小重量。对线性码来说，一种码的最小重量与其最小距离在数值上是相等的。
在构造线性码时，数字上是从n维空间中选一k维子空间，且使此子空间内各非零码字的重量尽可能大。当构造循环码时,可进一步将每一码字看成一多项式,将整个码看成是多项式环中的理想,这一理想是主理想,故可由生成多项式决定；而多项式完全可由它的根规定。这样,就容易对码进行构造和分析。这是BCH码等循环码构造的出发点。一般地说，构造一种码时，均设法将它与某种代数结构相联系，以便对它进行描述，进而推导它的性质，估计它的性能和给出它的译码方法。若一种码的码长为n，码字数为M,或信息位为h,以及最小距离为d，则可把此码记作【n,M,d】码。若此码为线性码，常简记作(n，k)或(n,k,d)码。人们还常用R=log2M/n表示码的信息率或简称码率,单位为比特/码元。R越大,则每个码元所携带的信息量越大，编码效率越高。 纠错码实现中最复杂的部分是译码。它是纠错码能否应用的关键。根据式(1),采用的码长n越大,则误码率越小。但n越大，编译码设备也越复杂,且延迟也越大。人们希望找到的译码方法是:误码率随码长n的增加按指数规律下降;译码的复杂程度随码长n的增加接近线性地增加；译码的计算量则与码长n基本无关。可惜，已经找到的码能满足这样要求的很少。不过由于大规模集成电路的发展，即使应用比较复杂的但性能良好的码，成本也并不太高。因此，纠错码的应用越来越广泛。
纠错码传输的都是数字信号。这既可用硬件实现，也可用软件实现。前者主要用各种数字电路，主要是采用大规模集成电路。软件实现特别适合计算机通信网等场合。因为这时可以直接利用网中的计算机进行编码和译码，不需要另加专用设备。硬件实现的速度较高，比软件可快几个数量级。
在传信率一定的情况下，如果采用纠错码提高可靠性，要求信道的传输率增加，带宽加大。因此，纠错码主要用于功率受限制而带宽较大的信道，如卫星、散射等系统中。纠错码还用在一些可靠性要求较高，但设备或器件的可靠性较差，而余量较大的场合，如磁带、磁盘和半导体存储器等。
在分组码的研究中，谱分析的方法受到人们的重视。纠同步错误码、算术码、不对称码、不等错误纠正码等，也得到较多的研究。 分组码是对信源待发的信息序列进行分组（每组K位）编码，它的校验位仅同本组的信息位有关。自20世纪50年代分组码的理论获得发展以来，分组码在数字通信和数据存储系统中已被广泛应用。
分组码的码长n和码字个数M是一个码的主要构造参数。码长为n的码中所有码字的位数均为n；若要用一个码传送k比特信息，则码字的个数M必须满足。典型的分组码是由k位信息位和r位监督位组成的，这样构成的码一般称为系统码。
分组码中应用最广的线性分组码。线性分组码中的M个码字之间具有一定线性约束关系，即这些码字总体构成了n维线性空间的一个k维子空间。称此k维子空间为（n，k）线性分组码。线性系统码的特点是每个码字的前k位均由这个码字所对应的信息位组成，并通过对这k位信息位的线性运算得到后面n—k是位监督位。
线性分组码中应用最广的是循环码，循环码的主要特征是任何码字在循环移位后个码字。循环码的优点在于其编码和解码手续比一般线性码简单，因而易于在设备上实现。在循环码中，码字可表示为多项式。循环码的码字多项式都可表示成为循环码的生成多项式与这个码字所代表的信息多项式的乘积，即，因此一个循环码可以通过给出其生成多项式来规定。常用的循环码有BCH码和RS码。
网格码有多种描述方法，网格图是常用方法之一，它能表示出编码过程。一个码率为1/2、包含四种状态的网格码的网格图如图所示。图1中00，01，10，11表示编码器所具有的四种状态，以“·”示出，从每一状态出发都存在两条支路，位于上面的一条支路对应于编码器输入为“0”的情况，位于下面的一条支路对应于编码器输入为“1”的情况，而每一支路上所列出的两个二进位码则表示相应的编码输出。因而可知，编码输出不仅决定于编码器的当前输入，还决定于编码器的状态，例如在图中从“00”状态出发；，若输入的二进制数据序列为1011，则编码器的状态转移过程为00→01→10→01→11，而相应的编码输出序列为11010010。在网格图中任意两条从同一状态出发；，经不同的状态转移过程后又归于另一相同状态（该状态也可与初始状态相同）的路径间的距离的最小值称为码的自由距离。如该图中的为5。对于卷积码来说，的计算可简化为始于且终于零状态的非全零路径与全零路径间距离的最小值。是表征网格码纠错能力的重要参数。维特比算法是广泛采用的网格码的译码方法。由于网格码的状态越多，译码越复杂，所以状态个数是度量网格码译码复杂性的重要参数。一般说来可以通过增大译码复杂性来增加，从而提高码的纠错能力。
BCH码、网格码已被广泛地应用于移动通信、卫星通信和频带数据传输中。RS码也被广泛应用于光盘的存储中。
大多数纠错码是设计来纠随机误码的，可以通过交织的方法使它适用于对突发误码的纠错。交织是一种使得集中出现的突发误码在解码时进行分散化的措施，从而使其不超出纠错码的纠错能力范围。 卷积码不对信息序列进行分组编码，它的校验元不仅与当前的信息元有关，而且同以前有限时间段上的信息元有关。卷积码在编码方法上尚未找到像分组码那样有效的数学工具和系统的理论。但在译码方面，不论在理论上还是实用上都超过了分组码，因而在差错控制和数据压缩系统中得到广泛应用。

⑵ crf模型原理及解释

在明白crf之前，首先我们来看看概率图。概率图是用图来表示变量概率依赖关系，是概率论和图论的结合。从概率图衍生而来的算法有很多，包括朴素贝叶斯、最大熵、hmm、条件随机场、主题模型等。
概率图分为有向概率图，又叫贝叶斯网络，其中的有向代表的是单边依赖关系；无向概率图，又叫马尔科夫网络，其中的无向代表的是双边依赖关系。

上面已经说了马尔科夫就是说当前状态只跟上一状态有关，而跟其他状态无关。

设X与Y是随机变量，P(Y∣X)是在给定X的条件下Y的条件概率分布。若随机变量Y构成一个由无向图G=(V,E)表示的马尔可夫随机场，即

对任意结点v成立，则称条件概率分布P(Y∣X)为条件随机场。其中w~v表示与v相连的节点w≠v表示除v外的所有节点，这就是条件独立的概念。
实际上，我们通常考虑线性链的情况，并且X和Y具有相同的结构，这个可以理解为隐藏状态和观察状态，X就是我们能观察到的，但是Y我们观察不到：

条件随机场最终求的都是一个联合概率，根据马尔科夫性，我们可以把联合概率表示成相邻节点的函数。

Z（x）就是exp那一坨的求和，tk和sl是特征函数，这个我们可以自己定义，剩下的是权重。
这样一来相乘的问题我们化简成相加的问题了。
这样写不太好理解和推导，需要化简，于是我们假设有K1个转义特征和K2个状态特征，定义一个分段函数：

然后定义一个分段的权重：

矩阵是最容易计算的了，因此进一步表示为矩阵形式。首先定义一个m阶矩阵，这个好理解，就是m个y可能的取值。

这个式子呢，从后往前看，最下面那个是不是眼熟，就是条件随机场向量化表达公式的前半部分，然后取exp以后就可以得到m阶矩阵了，这个懒得解释自己想一下就行了。提示一下m阶的意思是呢，yi-1有m种表达，yi有m种表达，最后综合起来就是m阶了。
最终矩阵相乘就表示一个概率的可能性，然后规范化以后就可以得到概率分布。

要时刻记得这事一个判别式模型，是要直接计算P(x|y)的。

我们都知道条件随机场有一个转移特征和状态特征，这些都可以事先定义好。我们定义好特征函数后，从模型表达式上来看就剩一个wk序列的参数需要计算了。参数求解方法有很多，牛顿法、拟牛顿法等等，这些都是运筹里的优化算法，需要了解的话我会单独的写一个专题出来。这里不展开了。

其实就是两个递推公式，具体不展开了，不太好理解：

目标函数，参考极大似然估计，跟逻辑回归类似，取下边这个：

然后采用拟牛顿法求解，太难了，不说了，知道怎么回事就行。

预测过程简而言之就是找到概率最大的那个状态序列，采用维特比算法，用到了动态规划，可以减少计算量。具体也不多说，因为这篇文章偏向于让大家都懂计算流程，不太考虑细节，可以参考下边这个文章。 https://www.cnblogs.com/bei/p/9391014.html

基本上碎碎念的就这么多，大家一般用crf都是用在Bilstm之后，巧的是tensorflow已经封装好crf层，同志们直接用好了。

⑶ 程序员必须掌握哪些算法

1. A搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A*搜索算法是最佳优先搜索的范例。

2. 集束搜索（又名定向搜索，BeamSearch）——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字——集束的宽度。

3. 二分查找（BinarySearch）——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。

4. 分支界定算法（BranchandBound）——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。

5. Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

6. 数据压缩——采取特定编码方案，使用更少的字节数（或是其他信息承载单元）对信息编码的过程，又叫来源编码。

7. Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。

8. Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。

9. 离散微分算法（Discretedifferentiation）

10. 动态规划算法（DynamicProgramming）——展示互相覆盖的子问题和最优子架构算法

11. 欧几里得算法（Euclideanalgorithm）——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。

12. 期望-最大算法（Expectation-maximizationalgorithm，又名EM-Training）——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值；第二步是最大化，最大化在第一步上求得的最大可能值来计算参数的值。

13. 快速傅里叶变换（FastFouriertransform，FFT）——计算离散的傅里叶变换（DFT）及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算大整数乘积。

14. 梯度下降（Gradientdescent）——一种数学上的最优化算法。

15. 哈希算法（Hashing）

16. 堆排序（Heaps）

17. Karatsuba乘法——需要完成上千位整数的乘法的系统中使用，比如计算机代数系统和大数程序库，如果使用长乘法，速度太慢。该算法发现于1962年。

18. LLL算法（Lenstra-Lenstra-Lovaszlatticerection）——以格规约（lattice）基数为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用：背包加密系统（knapsack）、有特定设置的RSA加密等等。

19. 最大流量算法（Maximumflow）——该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更复杂的网络流问题的特定情况。最大流与网络中的界面有关，这就是最大流-最小截定理（Max-flowmin-cuttheorem）。Ford-Fulkerson能找到一个流网络中的最大流。

20. 合并排序（MergeSort）

21. 牛顿法（Newton'smethod）——求非线性方程（组）零点的一种重要的迭代法。

22. Q-learning学习算法——这是一种通过学习动作值函数（action-valuefunction）完成的强化学习算法，函数采取在给定状态的给定动作，并计算出期望的效用价值，在此后遵循固定的策略。Q-leanring的优势是，在不需要环境模型的情况下，可以对比可采纳行动的期望效用。

23. 两次筛法（QuadraticSieve）——现代整数因子分解算法，在实践中，是目前已知第二快的此类算法（仅次于数域筛法NumberFieldSieve）。对于110位以下的十位整数，它仍是最快的，而且都认为它比数域筛法更简单。

24. RANSAC——是“RANdomSAmpleConsensus”的缩写。该算法根据一系列观察得到的数据，数据中包含异常值，估算一个数学模型的参数值。其基本假设是：数据包含非异化值，也就是能够通过某些模型参数解释的值，异化值就是那些不符合模型的数据点。

25. RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用，大家也相信它有足够安全长度的公钥。

26. Schönhage-Strassen算法——在数学中，Schönhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为：O(Nlog(N)log(log(N)))，该算法使用了傅里叶变换。

27. 单纯型算法（SimplexAlgorithm）——在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组，以及一个等待最大化（或最小化）的固定线性函数。

28. 奇异值分解（Singularvaluedecomposition，简称SVD）——在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵（以求解最小二乘法问题）、解决超定线性系统（overdeterminedlinearsystems）、矩阵逼近、数值天气预报等等。

29. 求解线性方程组（）——线性方程组是数学中最古老的问题，它们有很多应用，比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组，可以使用高斯—约当消去法（Gauss-Jordanelimination），或是柯列斯基分解（Choleskydecomposition）。

30. Strukturtensor算法——应用于模式识别领域，为所有像素找出一种计算方法，看看该像素是否处于同质区域（homogenousregion），看看它是否属于边缘，还是是一个顶点。

31. 合并查找算法（Union-find）——给定一组元素，该算法常常用来把这些元素分为多个分离的、彼此不重合的组。不相交集（disjoint-set）的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作：

32. 查找：判断某特定元素属于哪个组。

33. 合并：联合或合并两个组为一个组。

34. 维特比算法（Viterbialgorithm）——寻找隐藏状态最有可能序列的动态规划算法，这种序列被称为维特比路径，其结果是一系列可以观察到的事件，特别是在隐藏的Markov模型中。

⑷ 大数据最常用的算法有哪些

奥地利符号计算研究所(Research Institute for Symbolic Computation，简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做了一个调查，参与者大多数是计算机科学家，他请这些科学家投票选出最重要的算法，以下是这次调查的结果，按照英文名称字母顺序排序。

大数据等最核心的关键技术：32个算法

1、A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A*搜索算法是最佳优先搜索的范例。

2、集束搜索(又名定向搜索，Beam Search)——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字——集束的宽度。

3、二分查找(Binary Search)——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。

4、分支界定算法(Branch and Bound)——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。

5、Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

6、数据压缩——采取特定编码方案，使用更少的字节数(或是其他信息承载单元)对信息编码的过程，又叫来源编码。

7、Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。

8、Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。

9、离散微分算法(Discrete differentiation)。

10、动态规划算法(Dynamic Programming)——展示互相覆盖的子问题和最优子架构算法

11、欧几里得算法(Euclidean algorithm)——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。

12、期望-最大算法(Expectation-maximization algorithm，又名EM-Training)——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值;第二步是最大化，最大化在第一步上求得的最大可能值来计算参数的值。

13、快速傅里叶变换(Fast Fourier transform，FFT)——计算离散的傅里叶变换(DFT)及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算大整数乘积。

14、梯度下降(Gradient descent)——一种数学上的最优化算法。

15、哈希算法(Hashing)。

16、堆排序(Heaps)。

17、Karatsuba乘法——需要完成上千位整数的乘法的系统中使用，比如计算机代数系统和大数程序库，如果使用长乘法，速度太慢。该算法发现于1962年。

18、LLL算法(Lenstra-Lenstra-Lovasz lattice rection)——以格规约(lattice)基数为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用：背包加密系统(knapsack)、有特定设置的RSA加密等等。

19、最大流量算法(Maximum flow)——该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更复杂的网络流问题的特定情况。最大流与网络中的界面有关，这就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一个流网络中的最大流。

20、合并排序(Merge Sort)。

21、牛顿法(Newton’s method)——求非线性方程(组)零点的一种重要的迭代法。

22、Q-learning学习算法——这是一种通过学习动作值函数(action-value function)完成的强化学习算法，函数采取在给定状态的给定动作，并计算出期望的效用价值，在此后遵循固定的策略。Q-leanring的优势是，在不需要环境模型的情况下，可以对比可采纳行动的期望效用。

23、两次筛法(Quadratic Sieve)——现代整数因子分解算法，在实践中，是目前已知第二快的此类算法(仅次于数域筛法Number Field Sieve)。对于110位以下的十位整数，它仍是最快的，而且都认为它比数域筛法更简单。

24、RANSAC——是“RANdom SAmple Consensus”的缩写。该算法根据一系列观察得到的数据，数据中包含异常值，估算一个数学模型的参数值。其基本假设是：数据包含非异化值，也就是能够通过某些模型参数解释的值，异化值就是那些不符合模型的数据点。

25、RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用，大家也相信它有足够安全长度的公钥。

26、Sch?nhage-Strassen算法——在数学中，Sch?nhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为：O(N log(N) log(log(N)))，该算法使用了傅里叶变换。

27、单纯型算法(Simplex Algorithm)——在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组，以及一个等待最大化(或最小化)的固定线性函数。

28、奇异值分解(Singular value decomposition，简称SVD)——在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵(以求解最小二乘法问题)、解决超定线性系统(overdetermined linear systems)、矩阵逼近、数值天气预报等等。

29、求解线性方程组(Solving a system of linear equations)——线性方程组是数学中最古老的问题，它们有很多应用，比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组，可以使用高斯—约当消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。

30、Strukturtensor算法——应用于模式识别领域，为所有像素找出一种计算方法，看看该像素是否处于同质区域( homogenous region)，看看它是否属于边缘，还是是一个顶点。

31、合并查找算法(Union-find)——给定一组元素，该算法常常用来把这些元素分为多个分离的、彼此不重合的组。不相交集(disjoint-set)的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作：

查找：判断某特定元素属于哪个组。

合并：联合或合并两个组为一个组。

32、维特比算法(Viterbi algorithm)——寻找隐藏状态最有可能序列的动态规划算法，这种序列被称为维特比路径，其结果是一系列可以观察到的事件，特别是在隐藏的Markov模型中。

以上就是Christoph博士对于最重要的算法的调查结果。你们熟悉哪些算法?又有哪些算法是你们经常使用的?

⑸ 声学模型GMM-HMM

在语音识别中，HMM的每个状态都可对应多帧观察值，观察值概率的分布不是离散的，而是连续的，适合用GMM来进行建模。HMM模块负责建立状态之间的转移概率分布，而GMM模块则负责生成HMM的观察值概率。

模型自适应： 由于各地口音、采集设备、环境噪声等音素的差异，已训练过的GMM-HMM很可能和新领域的测试数据不匹配，导致识别效果变差，需要做自适应训练。

MAP(最大后验概率估计)： 算法本质是重新训练一次，并且平衡原有模型参数和自适应数据的估计。

MLLR（最大似然线性回归）： 算法核心思想是将原模型的参数进行线性变换后再进行识别，其优点是使用少量语音即可以对所有模型进行自适应训练，只要得到线性变换矩阵即可。

每个音素（或三音素）用一个 HMM 建模，每个 HMM 状态的发射概率对应一个 GMM。GMM-HMM 的目的即是找到每一帧属于哪个音素的哪个状态。GMM-HMM 的训练使用自我迭代式的 EM 算法，更直接的方式是采用维特比训练，即把EM算法应用到GMM参数的更新上，要求显示的输入每一帧对应的状态，使用带标注的训练数据更新GMM的参数，这种训练方法比Baum-Welch算法速度更快，模型性能却没有明显损失。

1、首次对齐时把训练样本按该句的状态个数平均分段。

2、每次模型参数的迭代都需要成对的使用gmm-acc-stats-ali和gmm-est工具。

3、进行多轮迭代训练后使用gmm-align-compiled工具通过其内部的维特比算法生成对齐结果。

单因子模型的基本假设是：一个音素的实际发音，与其左右相邻或相近的音素（上下文音素）无法。三因子结构中的每一个音素建模实例，都由其中心音素及其左右各一个上下文音素共同决定。无论是单因子还是三因子，通常都使用三状态的HMM结构来建模。为了解决三因子模型参数爆炸问题，将所有的三因子模型放到一起进行相似性聚类（决策树），发音相似的三因子被聚类到同一个模型，共享参数。训练脚本：steps/train_deltas.sh，目标训练一个10000状态的三因子系统：

1、以单因子为基础，训练一个5000状态的三因子模型

2、用5000状态的模型重新对训练数据进行对齐，其对齐质量必然比单因子系统对齐质量高

3、用新的对齐再去训练一个10000状态的三因子系统

 phone-id：音素的 ID，参见 data/lang/phones.txt，强制对齐的结果不含 0（表示<eps>）和消歧符 ID；

hmm-state-id：单个 HMM 的状态 ID，从 0 开始的几个数，参见 data/lang/topo；

 pdf-id：GMM 的 ID，从 0 开始，总数确定了 DNN 输出节点数，通常有数千个；

 transition-index：标识单个 Senone HMM 中一个状态的不同转移，从 0 开始的几个数；

 transition-id：上面四项的组合 (phone-id,hmm-state-id,pdf-id,transition-index)，可以涵盖所有可能动作，表示哪个 phone 的哪个 state 的哪个 transition 以及这个 state 对应的 pdf 和这个 transition 的概率，其中元组 (phone-id,hmm-state-id,pdf-id) 单独拿出来，叫 transition-state，与 transition-id 都从1开始计数。

关系：transition-id可以映射到唯一的transition-state，而transition-state可以映射到唯一的pdf-id，因此transition-id可以映射到唯一的pdf-id。pdf-id不能唯一的映射成音素，因此kaldi使用transition-id表示对齐的结果。

语音识别过程是在解码空间中衡量和评估所有的路径，将打分最高的路径代表的识别结果作为最终的识别结果。传统的最大似然训练是使正确路径的分数尽可能高，而区分性训练则着眼于加大这些路径之间的打分差异，不仅要使正确路径的分数仅可能高，还要使错误路径尤其是易混淆路径的分数尽可能低。

常用的区分性训练准则有最大互信息、状态级最小贝叶斯风险、最小音素错误。

分子：对于某条训练数据，其正确标注文本在解码空间中对应的所有路径的集合。

分母：理论上值整个搜索空间。通常会通过一次解码将高分路径过滤出来，近似整个分母空间，从而有效的减小参与区分性优化的分母规模。

词格（Lattice）：分子、分母其实都是解码过程中一部分解码路径的集合，将这些路径紧凑有效的保存下来的数据结构就是词格。

⑹ Turbo码的译码算法

如前所述，turbo码需要一种软输入软输出的译码算法。软输出译码器的输出不仅应包含硬判决值，而且包括做出这种判断的可信程度。译码算法应该考虑到三方面的问题，及外信息的引入；如何在迭代译码中充分利用各类信息，防止简单正反馈的形成，确保算法收敛；充分利用码原件的相关信息。常见的算法有一下几种： 其运算量为标准维特比算法的两倍。维特比算法是最大似然序列估计算法，但由于在它的每一步都要删除一些低似然路径，为每一状态只保留一条最优路径，它无法提供软输出。为了给他输出的每个比特赋予一个可信度，需要在删除低似然路径是做一些修正，以保留必要的信息。其基本思想是利用最优留存路径和被删路径的度量差，这个差越小意味着这次算去的可靠性越好。然后用这个差去修正这条路径上各个比特的可信度。

⑺ 隐马尔可夫模型

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。

隐马尔可夫模型的形式定义如下：

设 是所有可能 状态的集合 ， 是所有可能 观测的集合 ：

其中 为可能状态数， 为可能观测数。

是长度为 的 状态序列 ， 是对应的 观测序列 ：

是 状态转移概率矩阵 ：

其中：

是 观测概率矩阵 ：

其中：

是 初始状态概率向量 ：

其中：

隐马尔可夫模型由初始状态概率向量 、状态转移概率矩阵 和观测概率矩阵 决定。 因此隐马尔可夫模型 可表示为：

具体来说，长度为 的观测序列的生成过程如下：按照初始状态分布 产生状态 ，按状态 的观测概率分布 生成 ，按状态 的状态转移概率分布 产生状态 ，依次递推。

（1） 齐次马尔可夫性假设 ，即隐藏的马尔科夫链在任意时刻 的状态只依赖于其前一时刻的状态，与其他时刻状态及观测无关，也与时刻 无关。

（2） 观测独立性假设 ，即任意时刻的观测只依赖于该时刻的马尔科夫链状态，与其它观测状态无关。

（1） 概率计算问题 ：给定模型 和观测序列 ，计算在模型 下序列 出现的概率 。

（2） 学习问题 ：已知观测序列 ，估计模型 参数，使得在该模型下观测序列 最大。

（3） 预测问题 ：已知模型 和观测序列 ，求使得 最大的状态序列 。

接下来分别阐述这三个问题的解决方法。

状态 的概率是：

对固定的 观测序列 的概率是：

同时出现的联合概率为：

从而：

可以看到，上式是对所有可能的 序列求和，而长度为 的 序列的数量是 数量级的，而 的计算量是 级别的，因此计算量为 ，非常大， 这种算法在实际中不可行 。

首先定义 前向概率 ：给定隐马尔可夫模型 ，定义到时刻 部分观测序列为 且状态为 的概率为前向概率，记作：

观测序列概率的前向算法 如下：

（1）初值：

（2）递推，对 ：

（3）终止：

前向算法高效的关键是 局部计算前向概率，然后利用路径结构将前向概率递推到全局，得到 。前向概率算法计算量是 级别的。

首先定义 后向概率 ：给定隐马尔可夫模型 ，定义在时刻 状态为 的条件下，从 到 部分观测序列为 的概率为后向概率，记作：

观测序列概率的后向算法 如下：

（1）初值：

（2）递推，对 ：

（3）终止：

若有 个长度相同观测序列和对应状态序列 则可利用极大似然估计得到隐马尔可夫模型参数：

设样本中时刻 处于状态 时刻 转移到状态 的频数为 ，那么状态转移概率 的估计为：

设样本中状态为 观测为 的频数为 ，那么观测概率 的估计为：

初始状态 的估计 为 个样本中初始状态为 的频率。

假设给定训练数据只包含 个长度为 的观测序列 而没有对应状态序列，我们可以把状态数据看作不可观测的隐数据 ，则隐马尔可夫模型事实上是一个含有隐变量的概率模型：

其参数可由EM算法实现。

近似算法的思想是，在每个时刻 选择在该时刻最有可能出现的状态 ，从而得到一个状态序列 。

近似算法的优点是计算简单，缺点是不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分，比如存在转移概率为0的相邻状态。尽管如此，近似算法还是有用的。

维特比算法实际上是用动态规划解隐马尔可夫模型预测问题，即用动态规划求概率最大路径（最优路径），此路径对应一个状态序列。

定义 在时刻 状态为 的所有单个路径 中概率最大值 为：

由定义得递推式：

定义 在时刻 状态为 的所有单个路径 中概率最大路径的第 个结点 为：

维特比算法 如下：

（1）初始化：

（2）递推，对 :

（3）终止：

（4）回溯，对 ：

最优路径为

⑻ Python实现viterbi算法原理流程是什么样的

维特比算法说白了就是动态规划实现最短路径，只要知道“动态规划可以降低复杂度”这一点就能轻松理解维特比算法
维特比算法是一个特殊但应用最广的动态规划算法，利用动态规划，可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆网络的有向图（Lattice )的最短路径问题而提出的。 它之所以重要，是因为凡是使用隐含马尔可夫模型(Hidden Markov Model，HMM)描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。——《数学之美》 ps 多处摘录此书，不再赘述。
篱笆网络有向图的特点是同一列节点有多个，并且和上一列节点交错地连接起来。同一列节点代表同一个时间点上不同的状态的并列，大概因为这种一列一列整齐的节点和交错的边很像篱笆而得名。

假设上图每一列分别有n1……nn个节点，如果不使用动态的话，那么计算复杂度就是O(n1*n2……nn)。
而维特比算法的精髓就是，既然知道到第i列所有节点Xi{j=123…}的最短路径，那么到第i+1列节点的最短路径就等于到第i列j个节点的最短路径+第i列j个节点到第i+1列各个节点的距离的最小值。
这是一句大白话，所谓中文伪码。
分析一下复杂度，假设整个篱笆有向图中每一列节点最多有D个（也就是图的宽度为D），并且图一共有N列，那么，每次计算至多计算D*D次（从i列的D个节点中挑一个计算到i+1列D个节点的距离）。至多计算N次。那么复杂度骤减为O（ND2），远远小于穷举O（DN）。