新词发现算法优化 - HelloNLP_皇马娱乐建站工程集团

新词发现算法优化 - HelloNLP

发布时间：2024-04-07

阅读量：

字号：

目前，在一些NLP任务中，往往遇到一些没有见过的词即"未登录词"，那么发现这些新词往往是我们当下需要解决的问题。对于新词的发现，主流的深度学习框架CNN/LSTM/Attention和BERT/RoBERTa/Albert等都无法解决这个问题，因为这是一个无监督任务需要解决的问题。那么，我们接下来就会利用无监督的方法，一种基于自信息和互信息的方法，将新词发现的算法做了一个较大的升级（对比HaNLP和SmoothNLP）。

什么样的词符合新词的标准呢？

目前，主要有2个指标可以衡量一个字符串的组合是否可以做为新词。

自信息（信息熵）：Entropy
互信息：MI(Mutual Information)

下面，我们分别如果从这两个方面来介绍下。在此之前，我们先介绍下分字的优化。

在做新词发现的过程中，往往会遇到特殊字符串的困扰。其中，最常见的有2种，分别是阿拉伯数字和英文字母。所以，在做分词之前，我们还需要做一个分字的工作。也许很多人会比较陌生，为什么还要分字呢？

举个例子，一般做新词发现的过程种，我们选择的最大词窗口为4或者5。但是几个数字或者几个英文字母随便组合一下，他们的程度就大于5。这个时候，会导致很多问题。例如，有些数字会被识别为新词，新发现的英文单词最大程度为5。此外，在这两种情况下，它们对前后字符串的分词也会造成不利的影响。

所以，在分词之前，我做了一个分字的处理，主要是解决数字和英文字母的问题。代码链接：

https://github.com/hellonlp/hellonlp/blob/master/ChineseWordSegmentation/tokenization.py

信息熵如何应用到分词呢？首先我们来看看熵的定义：

2.1. 定义：（维基百科）

依据Boltzmann's H-theorem，香农把随机变量X的熵值 Η（希腊字母Eta）定义如下，其值域为{x1, ...,xn}：
$H(X)=E[I(X)]=E[-ln(P(X))]$
其中，P为X的概率质量函数（probability mass function），E为期望函数，而I(X)是X的信息量（又称为自信息）。I(X)本身是个随机变数。当取自有限的样本时，熵的公式可以表示为：
$H(X)=\\sum_{i}^{}{P(x_{i})I(x_{i})}=-\\sum_{i}^{}{P(x_{i})}log_{b}P(x_{i})$
在这里b是对数所使用的底，通常是2,自然常数e，或是10。当b=2，熵的单位是bit；当b=e，熵的单位是nat；而当b=10,熵的单位是Hart。

了解熵的定义后，现在我们将熵的理念引入到字符串的组合。已知一个字符串的组合string，在已知的文本数据库中，出现在它左边相邻的字有m种，出现在它右边边相邻的字有n种。那么这两种情况下，我们分别可以计算两个熵，分别为左邻熵和右邻熵。

2.2. 左邻熵和右邻熵

左邻熵：

$EL=Entropy_{left}(string)=- \\sum_{w_{i}\\in W_{m}}^{}{P(w_{i}|string)log_{e}P(w_{i}|string)}$

其中， $W_{m}$ 为左邻字符串集合。string为字符串的组合（长度1-5）。

右邻熵：

$ER=Entropy_{right}(string)=- \\sum_{w_{i}\\in W_{n}}^{}{P(w_{i}|string)log_{e}P(w_{i}|string)}$

其中， $W_{n}$ 为右邻字符串集合。

根据上面的2个公式，我们可以得知，当 $W_{m}$ 或者 $W_{n}$ 集合越大，以及当 $w_{i}$ 的值越大时，我们得到的熵就会越大。熵越大，代表的信息量也就越大。

2.3. 左右邻字丰富程度

下面，我们介绍2种评估左右相邻字丰富程度的方法，第一种是SmoothNLP提供的；第二种是我们提供的（HelloNLP），在评估的计算方法上做了优化。

SmoothNLP方法：

$L_{S}(EL,ER)=ln\\frac{EL\\cdot e^{ER}+ER\\cdot e^{EL}}{|EL-ER|}$

HelloNLP方法

$L_{H}(EL,ER)=ER\\cdot ln\\frac{EL}{|EL-ER|}+ EL\\cdot ln\\frac{ER}{|EL-ER|}$

当 $L(string)$ 的值越大时，意味着string可以独立作为一个词的可能性就越大。其中，为了避免ER或者EL其中某一个值非常大，而另外一个值非常小，导致该情况下得到的 $L(string)$ 值过大，我们计算了LE与LR的差绝对值|EL-ER|。举一个实际的例子，假设“我们的”右邻熵会非常的大，但是左邻熵却非常的小，如果我们直接将左右邻熵相加就会得到一个较大的值，那么“我们的”这个字符串就会被当作为一个词了。

我们现在对比下这两种方法：

$L_{S}$ (2,38)=35.08; $L_{S}$ (20,20)=23.68
$L_{S}$ (10,70)=68.19 ; $L_{S}$ (40,40)=44.38
$L_{S}$ (100,400)=398.89; $L_{S}$ (200,300)=300.68
$L_{H}$ (2,38)=37.10; $L_{H}$ (20,20)=45.99
$L_{H}$ (10,70)=78.32 ; $L_{H}$ (40,40)=87.37
$L_{H}$ (100,400)=499.18; $L_{H}$ (200,300)=501.77

从上面的对比来看，对HelloNLP而言，当(EL,ER)的和一定的时候，EL和ER的差距越小，L的值就会越大。但是，对SmoothNLP而言，却是是相反的。

我们需要的是左右的信息熵都相对较大时，此时的词可以独立作为一个词的可能性越大，所以HelloNLP使用的左右邻字丰富程度评估函数更好。在实际测试中，也取得了很好的效果，例如类似"的xx/很xx"这样的字符串计算得到评估值L小了很多。

下面，我们从另外一个指标互信息（MI）来判断一个字符串的组合是否可以做为新词。

2.4. 例子

举一个小例子，例如"老板"在文本出现的次数为5000次，"天天向"在文本中出现的次数为2000次。分别出现在他们左边和右边的字如下所示：

3.1. 定义 (维基百科)

一般地，两个离散随机变量 X 和 Y的互信息可以定义为：
$I(X,Y)=\\sum_{y\\in Y}^{}{\\sum_{x\\in X}^{}{p(x,y)}log_{b}(\\frac{p(x,y)}{p(x)p(y)})}$
其中，p(x,y)是X和Y的联合概率分布函数，而p(x)和p(y)分别是X和Y的边缘概率分布函数。

如果只计算两个对象间（字符）的互信息，既有：

$I(x,y)=p(x,y)log_{e}(\\frac{p(x,y)}{p(x)p(y)})=p(x,y)ln(\\frac{p(x,y)}{p(x)p(y)})$

3.2. 应用

我们首先来看一些正例和反例的词语。

两个字符串之间的互信息评估的是他们在一起的意义，互信息越大，说明彼此依赖更强，而不是可以有可无的。在实际的文本数据中，很多字符一起出现的频数很高，但这并不意味着他们的组合可以做为一个词。所以，这个时候，互信息可以用来评估，他们中哪些字符串的组合是真正有意义的，哪些是可有可无的。

例如，"的"、"个"和很多字符串的组合频数都比较高。例如一句话："美丽的山水画"，其中，"的山水"和"山水画"都出现的频数较高，分别为200和300。另外，"的"、"山水"、"画"的频数分别为1000000、1000和2000。另外，一共有10^8个组合。

那么，"的山水"和"山水画"的互信息分别为：

$MI(string1，string2)=p(string1,string2)ln(\\frac{p(string1,string2)}{p(string1)p(string2)})$

$MI(的，山水)=\\frac{N(的,山水)}{n}ln(\\frac{n\\cdot N(的,山水)}{N(的)N(山水)})=5.99e-06$

$MI(山水，画)=\\frac{N(山水，画)}{n}ln(\\frac{n\\cdot N(山水，画)}{N(山水)N(画)})=2.88e-05$

由此，我们可以得出“山水画”的互信息量比“的山水”的互信息大很多，即“山水画”的组合更有意义。

3.3. 平均互信息（AMI：Average Mutual Infomation）

由于对象间互信息量会受到候选词长度的影响（候选词越长，互信息取值偏大），我们使用平均互信息作为词语内聚程度的度量。

公式：

$AMI(W)=\\frac{MI(W)}{n}=\\frac{p(W)}{n}ln(\\frac{p(W)}{p(s_{1})\\cdot\\cdot\\cdot p(s_{n})})$

其中，n为候选词W的长度。

在得到信息熵（自信息）和互信息这两个评估指标后，候选词的打分即为：

$score=\\alpha\\cdot L(W)+\\beta \\cdot AMI(W)$

其中， $\\alpha$ 和 $\\beta$ 这两个变量需要评估。如果都设置为1，那么我们认为信息熵（自信息）和互信息同样的重要，反之我们会偏向其中的一个。

实验数据为36氪新闻，都取了TOP 500的分词结果。

5.1. SmoothNLP实验结果

错误词：

可以帮助宣布获得可以通过很容易都可以
已经开始

5.2. HelloNLP实验结果

错误词：

很容易都可以

5.3. 结果对比

从上面的结果可以看到，在TOP 500的词汇中，SmoothNLP错误词有6个，HelloNLP错误词有2个。另一方面，SmoothNLP得到的英文单词的字母长度都是小于5的，HelloNLP得到的单词长度大部分大于等于5。

安装HelloNLP：

pip3 install hellonlp

使用：

from hellonlp.ChineseWordSegmentation import segment_entropy
words = segment_entropy.get_words(["HelloNLP会一直坚持开源和贡献",
                            "HelloNLP专注于NLP技术",
                            "HelloNLP第一版终于发布了，太激动了",
                            "HelloNLP目前支持无监督的分词",
                            "HelloNLP之后还会支持深度学习的分词",
                            "HelloNLP目前只支持python",])
print(words[:100])

参数：

corpus:     list or string
top_k:      float or int,top k best words
chunk_size: int,chunksize to read data
max_n:      int,extract max ngram
min_freq:   int,extract the minimum word frequence

返回列表

优化算法2--遗传算法(原理)

SQL优化简介