精华内容
下载资源
问答
  • forward, backward, forward... Viterbi algorithm vs Viterbi algorithm 其实已经有r包可以实现了,自己写一遍过程便于理解。 r包实现 exp(forward(hmm, observations))#forward exp(backward(hmm, observatio...

    forward, backward, forward-backward procedure by r

    其实已经有r包可以实现了,自己写一遍过程便于理解。

    • r包实现
    exp(forward(hmm, observations))#forward
    exp(backward(hmm, observations)) #backward
    posterior(hmm, observations) #forward-backward
    • 自己的代码实现
    #set the probs
    transProbs <- as.data.frame(matrix(c(0.7 , 0.4 , 0.3 , 0.6), nrow = 2))
    States <- c("CpG","N")
    rownames(transProbs) <- States
    colnames(transProbs) <- States
    startProbs <- data.frame('CpG' = 0.4, 'N' = 0.6)
    emissionProbs <- as.data.frame(matrix(c(0.1, 0.3, 0.4, 0.2, 0.4, 0.2, 0.1, 0.3), nrow = 2))
    colnames(emissionProbs) <- c("A","C","G","T")
    rownames(emissionProbs) <- States
    sequence <-  'AGGCGT'
    seqlist <- unlist(strsplit(sequence, ""))
    
    ##forward procedure
    forp = array(0, c(2, length(seqlist)))
    dimnames(forp) = list(island <- c("CpG","N"), fwd_step <- 1:length(seqlist))
    # when index = 1
    for(i in States){
      forp[i,1] <- startProbs[1,i]*emissionProbs[i,1]
    }
    for(obs_ind in 2:length(seqlist)){
      for(i in 1:2){
        forp[i,obs_ind] <- forp[1,obs_ind-1]*transProbs[1,i]*emissionProbs[i,seqlist[obs_ind]]+forp[2,obs_ind-1]*transProbs[2,i]*emissionProbs[i,seqlist[obs_ind]]
      }
    }
    forp#Output the forward probabilities
    
    #backward procedure
    bakp = array(0, c(2, length(seqlist)))
    dimnames(bakp) = list(island <- c("CpG","N"), bkwd_step <- 1:length(seqlist))
    # when index = 6
    for(i in States){
      bakp[i,length(seqlist)] = 1
    }
    
    for(obs_ind in (length(seqlist) - 1):1){
      for(i in 1:2){
          bakp[i,obs_ind] <- bakp[1,obs_ind+1]*transProbs[i,1]*emissionProbs[1,seqlist[obs_ind+1]]+bakp[2,obs_ind+1]*transProbs[i,2]*emissionProbs[2,seqlist[obs_ind+1]]
      }
    }
    bakp#Output the backward probabilities
    
    #fwd-bkwd procedure
    fbp = array(0, c(2, length(seqlist)))
    dimnames(fbp) = list(island <- c("CpG","N"), fwdbkwd_step <- 1:length(seqlist))
    for(i in 1:length(seqlist)){
      for(j in 1:2){
        fbp[j,i] <- (forp[j,i]*bakp[j,i])/(forp[1,i]*bakp[1,i] + forp[2,i]*bakp[2,i])
      }
    }
    fbp#Output the Forward-backward probabilities

    Viterbi algorithm vs Viterbi algorithm

    Calculation steps

    • similarity
      1) Both of them need 3 matrix input, which are initial state distribution, state transition probability and emission probability.

    • differences
      1) Forward-backward algorithm first computing forward probabilities, then computing backward probabilities, and finally divide the product of the forward and backward probabilities by the sum of all the product of the forward and backward probabilities.
      2) Viterbi algorithm:Max instead of plus, and keep track path.And the termination is picking state that gives final best δ score, and backtrack to get path.

    R command

    • Forward-backward algorithm
    posterior(hmm, observations)
    • Viterbi algorithm
    viterbi(hmm, observations)

    Final paths

    • differences
      1) Forward-Backward gives marginal probability for each individual state, Viterbi gives probability of the most likely sequence of states.
      2) The probabilities of forward-Backward for each point are calculated independently of each other. They do not take into account the transition probabilities between states, and it is thus possible to get states at two moments (t and t+1) that are both most probable at those time points but which have very little probability of occurring together.So, Forward-Backward be used to find the most likely state for any point in time,while viterbi is a better way to predict the path.
    展开全文
  • Viterbi algorithm

    2017-12-03 19:22:42
    HMM(隐马尔可夫模型)是用来描述隐含未知参数的统计模型 任何一个HMM都可以通过下列五元组来...:param emit_p: 发射概率 (隐状态表现为显状态的概率)而Viterbi算法是解决隐马第三问题(求观察序列的最可能标注序

    HMM(隐马尔可夫模型)是用来描述隐含未知参数的统计模型
    任何一个HMM都可以通过下列五元组来描述:

    :param obs:观测序列
    :param states:隐状态
    :param start_p:初始概率(隐状态)
    :param trans_p:转移概率(隐状态)
    :param emit_p: 发射概率 (隐状态表现为显状态的概率)

    而Viterbi算法是解决隐马第三问题(求观察序列的最可能标注序列)。
    算法大概就是通过已知的可以观察到的序列,和一些已知的状态转换之间的概率情况,通过综合状态之间的转移概率和前一个状态的情况计算出概率最大的状态转换路径,从而推断出隐含状态的序列的情况。

    维基百科的这个例子的动态图


    问题描述来源知乎

    隐含的身体状态 = { 健康 , 发烧 }
    可观察的感觉状态 = { 正常 , 冷 , 头晕 }
    月儿预判的阿驴身体状态的概率分布 = { 健康:0.6 , 发烧: 0.4 }
    月儿认为的阿驴身体健康状态的转换概率分布 = {健康->健康: 0.7 ,健康->发烧: 0.3 ,发烧->健康:0.4 ,发烧->发烧: 0.6}
    月儿认为的在相应健康状况条件下,阿驴的感觉的概率分布 = {健康,正常:0.5 ,冷 :0.4 ,头晕: 0.1 ;发烧,正常:0.1 ,冷 :0.3 ,头晕: 0.6 }
    
    阿驴连续三天的身体感觉依次是: 正常、冷、头晕 。

    利用五元组来描述问题

    states = ('Health', 'Fever')
    observations = ('normal', 'cold', 'dizzy') 
    start_probability = {'Health': 0.6, 'Fever': 0.4}
    transition_probability = {
            'Health' : {'Health': 0.7, 'Fever': 0.3},
            'Fever' : {'Health': 0.4, 'Fever': 0.6},
            }
    emission_probability = {
            'Health' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
            'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
            }

    代码实现Viterbe算法

    import numpy
    def Viterbi () :
        #已知条件
        states = ('Health', 'Fever')
        observations = ('normal', 'cold', 'dizzy') 
        start_probability = {'Health': 0.6, 'Fever': 0.4}
        transition_probability = {
            'Health' : {'Health': 0.7, 'Fever': 0.3},
            'Fever' : {'Health': 0.4, 'Fever': 0.6},
            }
        emission_probability = {
            'Health' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
            'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
        }
        day = 3
        s = len(states)
        V = []      
    
        Wether = []
        Temp = []
        #求解初始状态可能
        for j in list(range(s)):
            Temp.append(start_probability.get(states[j]) * emission_probability.get(states[j])[observations[0]])
        V.append(Temp)
        #根据初始状态求解
        Wether.append(states[V[0].index(max(V[0]))]);
    
        #求解第2 - day 状态转换概率
        prob = []
        for d in [i + 1 for i in list(range( day - 1))]:
            prob = []
            pp = -1
            for j in list(range(s)):
                Temp = []
                for k in list(range(s)):
                    np = V[d-1][j] * transition_probability.get(states[j])[states[k]] * emission_probability.get(states[k])[observations[d]]
                    Temp.append(np)
                    #记录路径
                    if np > pp:
                        m1 = j
                        m2 = k
                        pp = np
                prob.append(Temp)
    
            print('Compute_Probability:')
            print(prob)
            Wether.append(states[m2])
            V.append(prob[m1])
            print('Large_One:')
            print(prob[m1])
    
        print(V)
        print(Wether)
    
    if __name__ == '__main__':
        Viterbi()

    运行结果
    这里写图片描述

    展开全文
  • the viterbi algorithm

    2018-01-14 10:50:53
    viterbi算法在HMM模型应用的算法文档。从IEEE下载,如果需要,可以下载。
  • Abstrucf-The Viterbi algorithm (VA) is a recursive optimal solution to the problem of estimating the state sequence of a discretetime finite-state Markov process observed in memoryless noise. Many ...
  • Viterbi Algorithm Analysis.

    2018-12-10 22:26:17
    Viterbi 算法在语音领域的hmm求解时有很重要应用,这个是本人的笔记。我认为最重要的地方就是中间层的入口大的概率把小的概率给淘汰了。 当然还有动态规划方面的意涵,也就是后面的每一步都是在前面一个运算的基础...

    Viterbi 算法在语音领域的hmm求解时有很重要应用,这个是本人的笔记。我认为最重要的地方就是中间层的入口大的概率把小的概率给淘汰了。

    当然还有动态规划方面的意涵,也就是后面的每一步都是在前面一个运算的基础上。并且假定后面的状态只依赖前一个状态。

    参考文献:

    1、https://www.zhihu.com/question/20136144

    2、https://www.cnblogs.com/Anker/archive/2013/03/15/2961725.html

    3、https://viterbischool.usc.edu/about-andrew-viterbi/

     

    展开全文
  • 1、简介 维特比算法是一个特殊但应用最广的动态规划算法,它是针对篱笆网络的有向图(Lattice)的最短路径问题而提出的。凡是使用隐含马尔可夫模型描述的问题都可以用维特比算法来解码,包括今天的数字通信、...
    

    1、简介

      维特比算法是一个特殊但应用最广的动态规划算法,它是针对篱笆网络的有向图(Lattice)的最短路径问题而提出的。凡是使用隐含马尔可夫模型描述的问题都可以用维特比算法来解码,包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。
    2、维特比算法的基础


    (1)如果概率最大的路径P(或叫最短路径)经过某个点,比如下图中的X22,那么这条路径上从起始点S到X22的这一段子路径Q,一定是S到X22之间的最短路径。否则,用S到X22的最短路径R替代Q,便构成了一条比P更短的路径,这显然是矛盾的。

    (2)从S到E的路径必定经过第i时刻的某个状态,假定第i时刻有k个状态,那么如果记录了从S到第i个状态的所有k个节点的最短路径,最终的最短路径必经过其中的一条。这样,在任何时刻,只需要考虑非常有限条最短路径即可。

     (3)结合上述两点,假定当我们从状态i进入状态i+1时,从S到状态i上各个节点的最短路径已经找到,并且记录在这些节点上,那么在计算从起点S到前一个状态i所有的k个结点的最短路径,以及从这k个节点到Xi+1,j的距离即可。
    3、维特比算法总结


    (1)从点S出发,对于第一个状态X1的各个节点,不妨假定有n1个,计算出S到它们的距离d(S,X1i),其中X1i代表任意状态1的节点。因为只有一步,所以这些距离都是S到它们各自的最短距离。

    (2)对于第二个状态X2的所有节点,要计算出从S到它们的最短距离。对于特点的节点X2i,从S到它的路径可以经过状态1的n1中任何一个节点X1i,对应的路径长度就是d(S,X2i) = d(S,X1i) + d(X1i,X2i)。由于j有n1种可能性,我们要一一计算,找出最小值。即:

    d(S,X2i) = minI=1,n1 d(S,X1i) + d(X1i,X2i)

    这样对于第二个状态的每个节点,需要n1次乘法计算。假定这个状态有n2个节

    点,把S这些节点的距离都算一遍,就有O(n1·n2)次计算。

    (3)接下来,类似地按照上述方法从第二个状态走到第三个状态,一直走到最后一个状态,就得到了整个网格从头到尾的最短路径。每一步计算的复杂度都和相邻两个状态Si和Si+1各自的节点数目ni,ni+1的乘积成正比,即O(ni·ni+1)

    (4)假设这个隐含马尔可夫链中节点最多的状态有D个节点,也就是说整个网格的宽度为D,那么任何一步的复杂度不超过O(D2),由于网格长度是N,所以整个维特比算法的复杂度是O(N·D2)。







    每个时刻有K个状态,每个状态需要遍历K个数才能得到,最终有T个时刻,时间复杂度和观察值序列和状态空间有关,和观察值空间无关。



    展开全文
  • HMM 学习+Viterbi Algorithm

    2014-04-19 11:36:57
    参见:http://www.52nlp.cn/hmm-learn-best-practices-six-viterbi-algorithm-1
  • Viterbi-Algorithm(维特比)算法

    千次阅读 2018-07-08 16:39:01
    Viterbi-Algorithm算法 维特比算法是一个特殊但应用最广的动态规划算法。利用动态规划,可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图-篱笆网了(Lattice)的有向图最短路径问题而提出来的...
  • 腓特比演算法(Viterbi Algorithm) for MATLAB
  • http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/s1_pg1.html Finding the most probable sequence of hidden states 给出一个HMM,以及某个观测序列,你可能想得到概率...
  • 维特比算法(Viterbi Algorithm)

    千次阅读 2017-04-21 13:42:16
    寻找最可能的隐藏状态序列 (Finding most probable sequence of hidden states)对于一个特殊的隐马尔科夫模型(HMM)及一个相应的观察序列,我们常常希望能找到生成此序列最可能的隐藏状态序列。之前的那个问题变转,...
  • 维特比算法(英语:Viterbi algorithm)是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列,特别是在马尔可夫信息源上下文和隐马尔可夫模型中。 术语“维特比路径”和“维特比...
  • 见同名纸质笔记。 课件参考https://www.cl.cam.ac.uk/teaching/1617/MLRD/slides/slides9.pdf
  • 维特比算法定义(Viterbi algorithm definition) 1、维特比算法的形式化定义  维特比算法可以形式化的概括为:  对于每一个i,i = 1,… ,n,令:    ——这一步是通过隐藏状态的初始概率和相应的观察...
  • CLRS Problems 15-5 的解法
  • 维特比算法(英语:Viterbi algorithm)是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列,特别是在马尔可夫信息源上下文和隐马尔可夫模型中。 维特比算法利用动态规划,可以...
  • HMM学习(6)-Viterbi Algorithm 分类: HMM学习 2007-12-22 20:42 3279人阅读 原文:http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html Wangben at mcrc, hit, Harbin 2007.12.22 ...
  • 简述维特比算法(Viterbi Algorithm

    千次阅读 2018-09-07 13:30:40
    维特比算法是一个特殊但应用最广的动态规划算法。利用动态规划,可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆网络(Lattice)的有向图最短路径的问题而提出的。...
  • 该图(图片来源: 通俗易懂讲解HMM(隐马尔可夫模型))清晰地显示了隐马模型的状态转移过程: 下面展示Viterbi algorithm 的完整代码(Python)。 import numpy as np #寻找最短路径(最大概率)函数 def ...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 242
精华内容 96
关键字:

algorithmviterbi