隐马可夫模型？

隐马可夫模型？

隐马可夫模型简介一、关于马可夫链的几个基本概念1、马尔可夫性－无后效性，表示在已知系统现在所处的状态下，系统的将来的演变和去无关。其数学表示如下；对于一随机过程{X(t),t∈T}，其状态空间S可数我们可以看到(n+1)的状态仅由n的状态决定，而与之前的状态无关。2、马尔可夫过程和马尔可夫链马尔可夫过程的状态空间S是连续的区间，马尔可夫链则是离散的可列集，在研究基因，我们使用的显然是马尔可夫链。3、马尔可夫链的转移概率和转移矩阵称作从α向β转移的概率4、齐次性（与具体时间无关性） 对任何m、n成立二、隐马可夫模型假设对于一个随机事件，有一个观察值序列：O1, …,Ot，该事件隐含着一个状态序列：X1, …,Xt假设1：马尔可夫假设（状态构成一阶马尔可夫链） P(Xi|Xi-1，…，X1) = P(Xi|Xi-1)假设2：不动性假设（状态与具体时间无关） P(Xi+1|Xi) = P(Xj+1|Xj)，对任意i,j成立假设3：输出独立性假设（输出仅与当前状态有关） P(O1, …,Ot | X1, …,Xt) = Π P(Ot | Xt)在基因的识别模型中，观察值序列显然对应于DNA序列（或蛋白质序列），状态序列对于基因的功能区段（或蛋白质中类似结构域的片段）；而假设1和假设2定义的是基因的功能序列的马尔可夫性和与起始状态无关性，假设3的意思可以理解为某一基因功能区对应的DNA序列只与该功能区段有关。这些假设在基因的模型中是否完全适用有待进一的检验，但从现有的知识和应用的结果来看是合理的。三、隐马可夫模型的定义一个隐马可夫模型包括五个参数：(Ωx，Ωo，A，B，π)其中： ΩX = {q1,...qN}：状态的有限集合 ΩO = {v1,...,vM}：观察值的有限集合 A = {aij}，aij = P(Xt+1 = qj |Xt = qi)：转移概率 B = {bik}，bik = P(Ot = vk | Xt = qi)：输出概率 π = {πi}， πi = P(X1 = qi)：初始状态分布有了这些参数，我们就可以构建一个完整的模型来解决实际问题，但在这之前，先要问自己三个基本问题，几乎每一本讲隐马可夫模型的书里都会提到。1、 likelihood question(可能性的评估问题)对于给定模型，如何评估某个观察值序列符合这个模型的可能性，也就是说这个观察值序列在多大程度上符合给定的模型。2、 decoding question(解码问题)对于给定的模型和观察值序列，求可能性最大的状态序列。3、 learning question(学习问题)对于给定的一个观察值序列，如何根据此序列调整参数{A，B，π}，获得合适的模型。四、隐马可夫模型的算法1、基本算法向前算法、向后算法、Viterbi算法2、学习算法EM算法、gradient descent、viterbi learning五、隐马可夫模型的应用1. multiple alignments2. database mining and classification of sequence and fragments3. structural analysis and pattern discovery