HMM VS CRF

一、区别

  1. HMM是生成模型(由数据学习联合概率分布P(X,Y), 然后由P(Y|X)=P(X,Y)/P(X)求出概率分布P(Y|X)作为预测的模型),CRF是判别模型(由数据直接学习决策函数Y=f(X)或条件概率分布P(Y|X)作为预测模型)
  2. HMM是概率有向图CRF是概率无向图
  3. HMM求解过程可能是局部最优CRF可以全局最优
  4. CRF打破了HMM的两种假设:
    • 齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态;
    • 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态3
  5. 任意的HMM都可以由CRF表达出来

二、HMM

隐马尔可夫模型 HMM

三、CRF

CRF条件随机场(部分)

四、Refs

生成模型和判别模型

zhihu

线段树

数组下标[i, j]–>线段树[i, (i+j)/2]和[(i+j)/2+1, j]

线段树数组空间为4*len(arr)=4n,证明如下:
预备:二叉树用满二叉树存储
情况一:所有的元素都在最后一层,则分支节点个数为n-1,共需要2n-1空间,已经为满二叉树,不需要补空间;
情况二:只有2个节点在最有一层,另外n-2个节点在倒数第二层,则需要对这n-2个节点补充左右孩子,则需要2(n-2)=2n-4,原始二叉树共有2n-1个节点,那么一共有2n-1+2n-4=4n-5<4n;
综上:开4n空间

307. 区域和检索 – 数组可修改

线段树详解

【数据结构】线段树(Segment Tree)

线段树开4N空间证明

processon