NLP自然语言处理之HMM词性标注_裴大帅2021

http://blog.sina.com.cn/u/1653392055

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

NLP自然语言处理之HMM词性标注

(2017-08-21 22:44:38)

标签：

nlp

自然语言

hmm

维特比

viterbi

分类：机器学习

一、词性标注引言

词性用来描述一个词在上下文中的作用，比如描述一个概念的词叫作名词，在下文引用这个名词的词叫作代词。在文本挖掘中，有时候根据词性我们能够寻找到想要的关键字。

一个词可能会有多个词性，解决标注歧义问题最简单的一个方法是从单词所有可能的词性中选出这个词最常用的词性作为这个词的词性，也就是一个概率最大的词性。比如“改革”大部分时候作为一个名词出现，那么可以机械地把这个词标注成名词，但是这样标注的准确率会比较低，因为只考虑了频率特征。考虑词所在的上下文可以提高标准的准确率。比如在动词后接名词的概率很大。"推进/改革"中的"推进"是动词，所以后面的"改革"很有可能是名词。这样的特征叫作上下文特征。

二、隐马尔科夫模型

词性标注的任务是：给定词序列W=w1,w2,...,wn，寻找词性标注序列T=t1,t2,...,tn，使得P(t1,t2,...,tn | w1,w2,...,wn)这个条件概率最大。

使用贝叶斯公式和马尔科夫链（n=2）计算这个公式：

上述推导可以很容易记录HMM的几个关键要素，而不用去死记硬背。

因为词是已知的，所以这里把词w叫作显状态。

因为词性是未知的，所以把词性t叫作隐状态。

条件概率P(ti|ti-1)叫作隐状态之间的转移概率。

条件概率P(wi|ti)叫作隐状态到显状态的发射概率，也叫作隐状态生成显状态的概率。

词性标注中的隐马尔科夫模型示意图：

在初始概率、转移概率以及发射概率已知的情况下，可以从观测到的显状态序列计算出可能性最大的隐状态序列。

三、词性标注示例

以标注[他][会][来]这句话为例，说明隐马尔科夫模型的计算过程。为了简化计算，假设只有词性：代词(r)、动词(v)、名词(n)和方位词(f)。这里，[他]只可能是代词，[会]可能是动词或者名词，[来]可能是方位词或者动词。

简化版的语言模型描述如下：

START: go(R, 1.0） emit(start, 1.0)

F: emit(来, 0.1) go(N, 0.9) go(END, 0.1)

V: emit(来, 0.4) emit(会, 0.3) go(F, 0.1) go(V,0.3) go(N, 0.5) go(END, 0.1)

N: emit(会, 0.1) go(F, 0.5) go(V, 0.3) go(END, 0.2)

R: emit(他, 0.3) go(V, 0.9) go(N, 0.1)

1、初始概率表

2、转移概率表

3、发射概率

4、"他/会/来"的转移概率加发射概率图

从上图可见，G依赖E和F的结果，而E和F又分别依赖C和D的计算结果。因为重复求解节点C和D，所以采用动态规划的方法求解最佳节点序列。当前节点概率的计算依据是：

（1）上一个阶段的节点概率P(Prev)

（2）上一个阶段的节点到当前节点的转移概率P(ti | ti-1)

（3）当前节点的发射概率P(wi | ti)

寻找当前节点的最大概率示意图如下：

6、对于每一个节点Next，循环考察这个节点的上一个阶段所有可能的节点Prev1到Prevm，计算节点概率的循环等式是：

实际计算时，采用log相加的方式来避免向下溢出。所以循环等式变成log累计概率、log转移概率和log发射概率三项相加的形式。这个用动态规划求解最佳词性序列的思想叫作维特比(Viterbi)算法。

维特比求解方法由两个过程组成：前向累计概率计算过程和反向回溯过程。

（1）在阶段"start"计算：

Best(A) = 1

（2）在阶段"他"计算：

Best(B) = Best(A) * P(r|start) * P(他|r) = 1 * 1 * 0.3 = 0.3

（3）在阶段"会"计算：

Best(C) = Best(B) * P(v|r) * P(会|v) = 0.3 * 0.9 * 0.3 = 0.081

Best(D) = Best(B) * P(n|r) * P(会|n) = 0.3 * 0.1 * 0.6 = 0.018

（4）在阶段"来"计算：

Best(E) = Max[Best(C) * P(v|v), Best(D) * P(v|n)] * P(来|v) = 0.081 * 0.3 * 0.4 = 0.00972

Best(F) = Max[Best(C) * P(f|v), Best(D) * P(f|n)] * P(来|f) = 0.081 * 0.1 * 0.1 = 0.00081

（5）在阶段"end"计算：

Best(G) = Max[Best[E] * P(end|v), Best(F) * P(end|f)] * P(|end) = 0.00972 * 0.1 * 0.1 = 0.000972

执行回溯过程即可发现最佳隐状态序列。G的最佳前驱节点是E，E的前面是C，C的前面是B，B的前面是A，所以猜测词性输出：他/r 会/v 来/v。

四、存储数据

1、计算转移概率

2、POSTransFreq.txt的数据格式：

a:b:62

a:c:451

a:d:296

...

五、HMM的代码实现

1、词的标注类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

package pos;

// 词的标注类型
public enum PartOfSpeech {
    start,//开始
    end,//结束
    a,//形容词
    ad,//副形词
    ag,//形语素
    an,//名形词
    b,//区别词
    c,//连词
    d,//副词
    dg,//副语素
    e,//叹词
    f,//方位词
    g,//语素
    h,//前接成分
    i,//成语
    j,//简称略语
    k,//后接成分
    l,//习用语
    m,//数词
    n,//名词
    ng,//名语素
    nr,//人名
    ns,//地名
    nt,//机构团体
    nx,//字母专名
    nz,//其他专名
    o,//拟声词
    p,//介词
    q,//量词
    r,//代词
    s,//处所词
    t,//时间词
    tg,//时语素
    u,//助词
    ud,//结构助词
    ug,//时态助词
    uj,//结构助词的
    ul,//时态助词了
    uv,//结构助词地
    uz,//时态助词着
    v,//动词
    vd,//副动词
    vg,//动语素
    vn,//名动词
    w,//标点符号
    x,//非语素字
    y,//语气词
    z,//状态词
    unknown //未知
}

2、加载语料库的hmm值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

package pos;

import java.io.*;
import java.util.StringTokenizer;

// 加载语料库的hmm值
public class HMMProb {
    private static HMMProb dic = null;

    public static HMMProb getInstance(){
        if(dic == null){
            dic = new HMMProb();
        }
        return dic;
    }

    // 定义语料库的转移概率
    private int[][] transFreq = new int[PartOfSpeech.values().length][PartOfSpeech.values().length];
    // 每个词性的频次
    private int[] typeFreq = new int[PartOfSpeech.values().length];
    // 所有词的总频次
    private int totalFreq;


    public double getTypeProb(PartOfSpeech curState) {
        return (double) typeFreq[curState.ordinal()];
    }


    public double getTransProb(PartOfSpeech curState, PartOfSpeech toTranState) {
        double transValue = 0.9 * (double) transFreq[curState.ordinal()][toTranState.ordinal()] / (double) typeFreq[curState.ordinal()];
        double smoothValue = 0.1 * typeFreq[curState.ordinal()] / totalFreq;
        return Math.log(transValue + smoothValue);
    }

    // 加载语料库
    public HMMProb(){
        try {
            FileInputStream file = new FileInputStream("D:\\workspace\\IDEA\\NLPSystem\\src\\data\\POSTransFreq.txt");
            BufferedReader in = new BufferedReader(new InputStreamReader(file, "gbk"));

            String line = null;
            while((line = in.readLine()) != null){
                StringTokenizer st = new StringTokenizer(line, ":");
                int pre = PartOfSpeech.valueOf(st.nextToken()).ordinal();
                int next = PartOfSpeech.valueOf(st.nextToken()).ordinal();
                int freq = Integer.parseInt(st.nextToken());

                transFreq[pre][next] = freq;
                typeFreq[next] += freq;
                totalFreq += freq;
                if(pre == 0){
                    typeFreq[0] += freq;
                }
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }

    }
}

3、词性序列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

package pos;

import java.util.Iterator;

// 词性序列
public class WordTypes implements Iterable {

    public static class WordTypeInf{
        public PartOfSpeech pos; // 类型
        public long weight = 0; // 频率

        public WordTypeInf(PartOfSpeech p, long f){
            pos = p;
            weight = f;
        }

        public PartOfSpeech getPos() {
            return pos;
        }

        public void setPos(PartOfSpeech pos) {
            this.pos = pos;
        }

        public long getWeight() {
            return weight;
        }

        public void setWeight(long weight) {
            this.weight = weight;
        }

        @Override
        public String toString(){
            return pos + ":" + weight;
        }
    }

    public static class LinkNode{
        public WordTypeInf item;
        public LinkNode next;

        public LinkNode(WordTypeInf data, LinkNode next){
            item = data;
            this.next = next;
        }
    }

    private LinkNode  head;

    public WordTypes(){
        head = null;
    }

    public WordTypes(WordTypeInf item){
        head = new LinkNode(item, null);
    }

    // 不断插入新的节点
    // 1.新生成的节点指向head
    // 2.head又指向新生成的节点
    public void put(WordTypeInf item){
        head = new LinkNode(item, head);
    }

    public LinkNode getHead(){
        return head;
    }

    public int size(){
        int count = 0;
        LinkNode t = head;
        while(t != null){
            count++;
            t = t.next;
        }
        return count;
    }

    public long totalCost(){
        long cost = 0;

        LinkNode t = head;
        while(t != null){
            cost += t.item.weight;
            t = t.next;
        }

        return cost;
    }

    @Override
    public Iterator iterator(){
        return new LinkIterator(head);
    }

    private class LinkIterator implements Iterator{

        LinkNode itr;

        public LinkIterator(LinkNode begin){
            itr = begin;
        }

        @Override
        public boolean hasNext() {
            return itr != null;
        }

        @Override
        public WordTypeInf next() {
            LinkNode cur = itr;
            itr = itr.next;
            return cur.item;
        }

        @Override
        public void remove() {

        }
    }

    @Override
    public String toString(){
        StringBuilder buf = new StringBuilder();
        LinkNode pCur = head;

        while(pCur != null){
            buf.append(pCur.item.toString());
            buf.append(' ');
            pCur = pCur.next;
        }

        return buf.toString();
    }

}

4、词图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

package pos;

// 词图：有向边，边的权重不能是负数
public class WordTokenInf {
    public String termText;
    public WordTypes data;
    public int start;
    public int end;
    public long cost = 5; // 默认的单子平滑系数

    public WordTokenInf(int vertexFrom, int vertexTo, String word, WordTypes d){
        start = vertexFrom;
        end = vertexTo;
        termText = word;
        data = d;
        if(d != null){
            cost = d.totalCost();
        }
    }

    @Override
    public String toString(){
        return "text:" + termText + " start:" + start + " end:" + end
                + "------data:" + data;
    }
}

5、词性标注器

package pos;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Iterator;

// 词性标注器
public class POSTagger {
    private static HMMProb hmmProb = new HMMProb();


    public static PartOfSpeech[] hmm(ArrayList observations){
        // 增加start和end节点
        WordTypes startType = new WordTypes();
        startType.put(new WordTypes.WordTypeInf(PartOfSpeech.start, 1));
        observations.add(0, new WordTokenInf(-1, 0, "Start", startType));

        WordTypes endType = new WordTypes();
        endType.put(new WordTypes.WordTypeInf(PartOfSpeech.end, 100));
        observations.add(new WordTokenInf(-1, 0, "End", endType));

        // 初始化各个节点的隐状态，每个节点都有PartOfSpeech.values().length种隐状态
        // 形成了一个row=stageLength,line=WordTypes.values().length的二维数组
        int stageLength = observations.size();
        double[][] prob = new double[stageLength][];
        for(int i = 0; i < stageLength; ++i){
            prob[i] = new double[PartOfSpeech.values().length];
            for(int j = 0; j < PartOfSpeech.values().length; ++j){
                prob[i][j] = Double.NEGATIVE_INFINITY;
            }
        }

        // 在隐马尔科夫模型中，每个隐状态都有一个最佳前驱，此二维数组用来存储每个状态的最佳前驱
        PartOfSpeech[][] bestPre = new PartOfSpeech[stageLength][];
        for(int i = 0; i < observations.size(); ++i){
            bestPre[i] = new PartOfSpeech[PartOfSpeech.values().length];
        }
        prob[0][PartOfSpeech.start.ordinal()] = 1;

        // viterbi算法计算最佳前驱
        for(int stage = 1; stage < stageLength; stage++){// 从前向后遍历阶段
            WordTokenInf nextInf = observations.get(stage);
            if(nextInf.data == null){
                continue;
            }

            Iterator nextIt = nextInf.data.iterator();
            while(nextIt.hasNext()){// 遍历当前节点
                WordTypes.WordTypeInf nextTypeInf = nextIt.next();

                WordTokenInf preInf = observations.get(stage - 1);
                if(preInf.data == null){
                    continue;
                }

                double emiprob = Math.log((double)nextTypeInf.weight / hmmProb.getTypeProb(nextTypeInf.pos)); // 发射概率，待确认为什么不是word的weight
                Iterator preIt = preInf.data.iterator();
                while(preIt.hasNext()){ // 遍历前面的节点，寻找最佳前驱
                    WordTypes.WordTypeInf preTypeInf = preIt.next();
                    // log(转移概率)
                    double transprob = hmmProb.getTransProb(preTypeInf.pos, nextTypeInf.pos);
                    // log(前驱最佳概率)
                    double preProb = prob[stage - 1][preTypeInf.pos.ordinal()];
                    // log(前驱最佳概率)+log(发射概率)+log(转移概率)
                    double currentprob = preProb + transprob + emiprob;
                    // 计算最佳前驱
                    if(prob[stage][nextTypeInf.pos.ordinal()] <= currentprob){
                        // 记录当前节点的最大累计概率
                        prob[stage][nextTypeInf.pos.ordinal()] = currentprob;
                        // 记录当前节点的最佳前驱
                        bestPre[stage][nextTypeInf.pos.ordinal()] = preTypeInf.pos;
                    }

                }
            }
        }

        // 逆向求解路径
        PartOfSpeech tmpTag = PartOfSpeech.end;
        PartOfSpeech[] bestTag = new PartOfSpeech[stageLength];
        for(int i = (stageLength - 1); i > 1; i--){
            bestTag[i - 1] = bestPre[i][tmpTag.ordinal()];
            tmpTag = bestTag[i - 1];
        }

        // 构造返回结果
        PartOfSpeech[] resultTag = new PartOfSpeech[stageLength - 2];
        System.arraycopy(bestTag, 1, resultTag, 0, resultTag.length);

        // 将observation之前台添加的start和end节点去除
        observations.remove(stageLength - 1);
        observations.remove(0);

        return resultTag;
    }

}

6、测试用例

词性标注的测试用例示意图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

package test.pos;

import org.junit.Test;
import pos.*;
import java.util.ArrayList;

public class POSTest {


    @Test
    public void testTransProb(){
        HMMProb hmmProb = HMMProb.getInstance();
        System.out.println(hmmProb.getTransProb(PartOfSpeech.m, PartOfSpeech.q)); // 测试从数词到量词的转移概率
        System.out.println(hmmProb.getTransProb(PartOfSpeech.m, PartOfSpeech.v)); // 测试从数词到动词的转移概率
    }


    @Test
    public void testPOSTag(){
        ArrayList observations = new ArrayList();

        // 第一个词
        WordTypes t1 = new WordTypes();
        t1.put(new WordTypes.WordTypeInf(PartOfSpeech.r, 1));
        WordTokenInf w1 = new WordTokenInf(0, 1, "他", t1);
        observations.add(w1);

        // 第二个词
        WordTypes t2 = new WordTypes();
        t2.put(new WordTypes.WordTypeInf(PartOfSpeech.v, 1));
        t2.put(new WordTypes.WordTypeInf(PartOfSpeech.n, 1));
        WordTokenInf w2 = new WordTokenInf(1, 2, "会", t2);
        observations.add(w2);

        // 第三个词
        WordTypes t3 = new WordTypes();
        t3.put(new WordTypes.WordTypeInf(PartOfSpeech.v, 1));
        t3.put(new WordTypes.WordTypeInf(PartOfSpeech.f, 1));
        WordTokenInf w3 = new WordTokenInf(2, 3, "来", t3);
        observations.add(w3);

        // 输出viterbi算法标注的词性序列
        PartOfSpeech[] bestTag = POSTagger.hmm(observations);
        for(int i = 0; i < bestTag.length; i++){ // 输出词和对应的标注结果
            System.out.println(observations.get(i).termText + "|" + bestTag[i].name() + "\t");
        }

    }
}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：spring中mock的应用

后一篇：从PageRank到TextRank

新浪BLOG意见反馈留言板　欢迎批评指正