NLP（三十一）短语的语序问题

素颜马尾好姑娘i 2023-02-09 11:57 3阅读 0赞

所谓的短语的语序问题，即给定一个打乱顺序的短语，我们要按照语义信息将其重新组合，新的语序通顺的短语。  
  举个简单例子，比如我们在识别验证码中的文字的时候，识别出来的文字分别为“哲”，“思”，“学”，“想”，那么重合调整语序后形成的短语应该为“哲学思想”。  
  这样的问题也会经常出现，除了验证码识别，还有语音识别等。解决这类的语序问题，我们通常会用到统计方面的语言模型（Language Model，LM），常见的有N-gram问题等。  
  下面将讲述n-gram问题的解决办法。

### 原理篇 ###

N-gram模型是一种语言模型，语言模型是一个基于概率的判别模型，它的输入是一句话（单词的顺序序列），输出是这句话的概率，即这些单词的联合概率（joint probability）。  
  假设一个句子由n个词组成： S = ( w 1 , w 2 , . . . , w n − 1 , w n ) S=(w\_\{1\}, w\_\{2\}, ...,w\_\{n-1\}, w\_\{n\}) S=(w1,w2,...,wn−1,wn)，如何衡量这些词的联合概率呢？我们不妨假设每一个词语 w i w\_\{i\} wi都依赖于前 i − 1 i-1 i−1个词语的影响，则联合概率如下：

p ( S ) = p ( w 1 w 2 . . . w n − 1 w n ) = p ( w 1 ) p ( w 2 ∣ w 1 ) . . . p ( w n ∣ w 1 w 2 . . . w n − 1 ) p(S)=p(w\_\{1\}w\_\{2\}...w\_\{n-1\}w\_\{n\})=p(w\_\{1\})p(w\_\{2\}|w\_\{1\})...p(w\_\{n\}|w\_\{1\}w\_\{2\}...w\_\{n-1\}) p(S)=p(w1w2...wn−1wn)=p(w1)p(w2∣w1)...p(wn∣w1w2...wn−1)

上述的假设是合情合理的，但实际我们在计算的过程中，会发现参数空间过大和数据稀疏等问题，尤其是 i i i值越大，前 i − 1 i-1 i−1个的组合情况越少，甚至为0。  
  为了避免上述问题，我们需要`马尔科夫假设`，即一个词的出现仅与它之前的N个词有关。如果一个词的出现仅依赖于前一个词，那么为`Bi-gram`的情形（N=2），公式如下：

p ( S ) = p ( w 1 w 2 . . . w n − 1 w n ) = p ( w 1 ) p ( w 2 ∣ w 1 ) . . . p ( w n ∣ w n − 1 ) p(S)=p(w\_\{1\}w\_\{2\}...w\_\{n-1\}w\_\{n\})=p(w\_\{1\})p(w\_\{2\}|w\_\{1\})...p(w\_\{n\}|w\_\{n-1\}) p(S)=p(w1w2...wn−1wn)=p(w1)p(w2∣w1)...p(wn∣wn−1)

如果一个词的出现仅依赖于前两个词，那么为`Tri-gram`的情形（N=3），公式如下：

p ( S ) = p ( w 1 w 2 . . . w n − 1 w n ) = p ( w 1 ) p ( w 2 ∣ w 1 ) p ( w 3 ∣ w 2 w 1 ) . . . p ( w n ∣ w n − 1 w n − 2 ) p(S)=p(w\_\{1\}w\_\{2\}...w\_\{n-1\}w\_\{n\})=p(w\_\{1\})p(w\_\{2\}|w\_\{1\})p(w\_\{3\}|w\_\{2\}w\_\{1\})...p(w\_\{n\}|w\_\{n-1\}w\_\{n-2\}) p(S)=p(w1w2...wn−1wn)=p(w1)p(w2∣w1)p(w3∣w2w1)...p(wn∣wn−1wn−2)

在实际我们计算上述等式最后面的值时，可以用频数来代替（这是根据条件概率得到的），比如：

p ( w n ∣ w n − 1 ) = C ( w n − 1 w n ) / C ( w n − 1 ) p(w\_\{n\}|w\_\{n-1\})=C(w\_\{n-1\}w\_\{n\})/C(w\_\{n-1\}) p(wn∣wn−1)=C(wn−1wn)/C(wn−1)

p ( w n ∣ w n − 1 w n − 2 ) = C ( w n − 2 w n − 1 w n ) / C ( w n − 2 w n − 1 ) p(w\_\{n\}|w\_\{n-1\}w\_\{n-2\})=C(w\_\{n-2\}w\_\{n-1\}w\_\{n\})/C(w\_\{n-2\}w\_\{n-1\}) p(wn∣wn−1wn−2)=C(wn−2wn−1wn)/C(wn−2wn−1)

其中， C ( w n − 1 w n ) C(w\_\{n-1\}w\_\{n\}) C(wn−1wn)表示 w n − 1 w n w\_\{n-1\}w\_\{n\} wn−1wn一起在文章中出现的概率，其余类似。

### 实战篇 ###

根据上面的原理，我们来解决短语的语序问题。  
  首先，我们需要语料，语料就用人民日报的NER语料，前几行如下：

> 海钓比赛地点在厦门与金门之间的海域。  
> 这座依山傍水的博物馆由国内一流的设计师主持设计，整个建筑群精美而恢宏。  
> 在发达国家，急救保险十分普及，已成为社会保障体系的重要组成部分。  
> 日俄两国国内政局都充满变数，尽管日俄关系目前是历史最佳时期，但其脆弱性不言自明。  
> 克马尔的女儿让娜今年读五年级，她所在的班上有30多名同学，该班的“家委会”由10名家长组成。  
>   解决短语的语序问题的脚本代码如下：

# -*- coding: utf-8 -*-
    # author: Jclian91
    # place: Pudong Shanghai
    # time: 2020/5/18 4:04 下午
    from itertools import permutations
    from pprint import pprint
    from operator import itemgetter
    
    # read corpus data in sentence format
    with open("corpus.txt", "r", encoding="utf-8") as f:
        content = [_.strip() for _ in f.readlines()]
    
    # random characters input order
    string = "哲学思想"
    # string = "景德镇陶瓷"
    # string = "突出贡献"
    # string = "哈萨克斯坦"
    # string = "管理局"
    # string = "博物馆"
    # string = "北京大学"
    # string = "浦东发展银行"
    # string = "世界杯决赛"
    word_list = set(list(string))
    print("模拟输入:", word_list)
    candidate_list = list(permutations(word_list, r=len(word_list)))
    
    # check if a character in the corpus
    for word in word_list:
        if word not in "".join(content):
            raise Exception("%s不在语料库中！" % word)
    
    # Language Model
    word_prob_dict = { }
    for candidate in candidate_list:
        candidate = list(candidate)
        prob = "".join(content).count(candidate[0])/len("".join(content))
        # 2-gram
        # prob = Count(W_{i}W_{i-1})/Count(W_{i-1})
        for i in range(1, len(candidate)):
            char_cnt = "".join(content).count(candidate[i-1])
            word_cnt = "".join(content).count("".join(candidate[i-1:i+1]))
            prob *= (word_cnt/char_cnt)
            if prob == 0:
                break
    
        word_prob_dict["".join(candidate)] = prob
    
    # recognize result
    # pprint(word_prob_dict)
    print("最终输出结果:")
    print(sorted(word_prob_dict.items(), key=itemgetter(1), reverse=True)[0])

输出结果如下：

> 模拟输入: \{‘思’, ‘想’, ‘哲’, ‘学’\}  
> 最终输出结果:  
> (‘哲学思想’, 4.851640701745029e-08)

> 模拟输入: \{‘陶’, ‘镇’, ‘德’, ‘瓷’, ‘景’\}  
> 最终输出结果:  
> (‘景德镇陶瓷’, 4.402324066467249e-12)

> 模拟输入: \{‘贡’, ‘出’, ‘突’, ‘献’\}  
> 最终输出结果:  
> (‘突出贡献’, 4.4461494672771407e-07)

> 模拟输入: \{‘坦’, ‘克’, ‘萨’, ‘斯’, ‘哈’\}  
> 最终输出结果:  
> (‘哈萨克斯坦’, 4.65260719191311e-09)

> 模拟输入: \{‘理’, ‘局’, ‘管’\}  
> 最终输出结果:  
> (‘管理局’, 4.5911913512038205e-06)

> 模拟输入: \{‘馆’, ‘物’, ‘博’\}  
> 最终输出结果:  
> (‘博物馆’, 5.9318486186358995e-06)

> 模拟输入: \{‘大’, ‘京’, ‘北’, ‘学’\}  
> 最终输出结果:  
> (‘北京大学’, 3.491890788613219e-06)

> 模拟输入: \{‘银’, ‘行’, ‘发’, ‘东’, ‘浦’, ‘展’\}  
> 最终输出结果:  
> (‘浦东发展银行’, 2.8403362134844498e-11)

> 模拟输入: \{‘决’, ‘世’, ‘界’, ‘杯’, ‘赛’\}  
> 最终输出结果:  
> (‘世界杯决赛’, 6.28999814981479e-07)

### 总结 ###

上面的代码只是给出了如何解决短语的语序问题的一个实现思路，实际我们在应用的过程中还需要考虑以下问题：