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. CRF由于得分进行全局softmax归一化,所以得到的是全局最优值;并且解决了最大熵马尔可夫模型(MEMM)中的标注偏置问题(MEMM只去除了观测独立性假设,没有去除齐次马尔科夫链假设 Thus, states with a single outgoing transition effectively ignore their observations. More generally, states with low-entropy next state distributions will take little notice of observations)。
      局部归一化,局部最优。
  • CRF打破了HMM的两种假设:
    • 齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态;
    • 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态
  • CRF可以定义数量更多,种类更丰富的特征函数,并且加权求和(score)
  • CRF在特征函数中还包含了整条观测序列的信息,都可以被利用
  • 任意的HMM都可以由CRF表达出来

二、HMM

隐马尔可夫模型 HMM

三、CRF

CRF条件随机场

四、Refs

生成模型和判别模型

0

线段树

数组下标[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. 区域和检索 – 数组可修改

给定一个整数数组  nums,求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和,包含 i,  j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
说明:

数组仅可以在 update 函数下进行修改。
你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。
class NumArray {
    public static int[] tree;
    public static int[] nums;
    public static int len;

    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0)
            return;
        this.len = nums.length;
        this.nums = nums;
        this.tree = new int[4 * len];
        buildTree(1, 0, len - 1);
    }

    //start/end是数组的下标,current/left_node/right_node为树的下标
    public void buildTree(int current, int start, int end) {
        if (start == end)
            tree[current] = nums[start];
        else {
            int left_node = 2 * current;
            int right_node = 2 * current + 1;
            int mid = (start + end) / 2;
            buildTree(left_node, start, mid);
            buildTree(right_node, mid + 1, end);
            tree[current] = tree[left_node] + tree[right_node];
        }
    }

    public void update(int i, int val) {
        updateTree(1, 0, len - 1, i, val);
    }

    public void updateTree(int current, int start, int end, int pos, int val) {
        if (start == end) {
            nums[pos] = val;
            tree[current] = val;
        } else {
            int left_node = 2 * current;
            int right_node = 2 * current + 1;
            int mid = (start + end) / 2;
            if (start <= pos && pos <= mid)
                updateTree(left_node, start, mid, pos, val);
            else
                updateTree(right_node, mid + 1, end, pos, val);
            tree[current] = tree[left_node] + tree[right_node];
        }

    }

    public int sumRange(int i, int j) {
        return sumTree(1, 0, len - 1, i, j);
    }

    public int sumTree(int current, int start, int end, int left, int right) {
        if (right < start || left > end)//需要求解的区间不在[start,end]内
            return 0;
        else if (left <= start && right >= end)//[left,right]将[start,end]包含,已经没必要向子节点走了
            return tree[current];
        else if (start == end)
            return tree[current];
        else {
            int left_node = 2 * current;
            int right_node = 2 * current + 1;
            int mid = (start + end) / 2;
            return sumTree(left_node, start, mid, left, right) + sumTree(right_node, mid + 1, end, left, right);
        }
    }
}

线段树详解

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

线段树开4N空间证明

processon

0