`
kofsky
  • 浏览: 195769 次
  • 性别: Icon_minigender_1
  • 来自: 重庆
社区版块
存档分类
最新评论

不确定有穷自动机 NFA 与 隐马尔可夫模型 HMM 比较

 
阅读更多

不确定有穷自动机 NFA 定义为一个五元组
如下:


比如说下面的NFA:

其状态转移图如下:


*上的符号串tNFA M接受也可以这样理解<o:p></o:p>

对于Σ﹡中的任何一个串t,若存在一条从某一初态节点到某一终态节点的道路,且这条道路上所有弧的标记依序连接成的串(不理采那些标记为ε的弧)等于t,则称t可为NFA M所识别(读出或接受)。若M的某些节点既是初态节点又是终态节点,或者存在一条从某个初态节点到某个终态节点的道路,其上所有弧的标记均为ε,那么空字可为M所接受。<o:p></o:p>



再来看一下隐马尔可夫模型 HMM的相关定义
<p:colorscheme colors="#0066ff,#ffffff,#000000,#ffff00,#00cccc,#ff33cc,#ff4568,#ccecff"></p:colorscheme>
n用模型五元组     =( N, M, π AB)用来描述HMM,或简写为    =(π AB)

<p:colorscheme colors="#0066ff,#ffffff,#000000,#ffff00,#00cccc,#ff33cc,#ff4568,#ccecff"></p:colorscheme>
参数
含义
N
状态数目
M
每个状态可能的观察值数
A
与时间无关的状态转移概率矩阵
B
给定状态下,观察值概率分布
π
初始状态空间的概率分布


NFA     由一个状态可能会转移到不同的状态;
HMM    由一个状态可能会转移到不同的状态;

NFA     转移到不同的状态由输入字母确定
HMM   转移到不同的状态由状态转移概率矩阵决定

NFA     中的输入字母与 HMM 的观察值是非常类似的

对于一个给定的字符串
NFA     给出的判断是 接收该串(1)或者拒绝该串(0)
HMM    给出的判断是  该观测值序列(串)出现的概率(01之间)


针对同一个输入

NFA状态转移不确定

HMM状态转移概率是确定的

 
NFA     状态转移函数通过固定规则指定
HMM    状态转移概率通过统计学习获得

最大的差别就是:

NFA是规则的

而HMM是统计的


暂时就想到这么多了

想到了再来完善

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics