NLP

BM25算法

BM25算法，通常用作搜索相关性评分，计算某个 Query 与某篇文档的相似度。

我们在提取自动摘要时，需要计算句子与文本的相似度，从而能得出一个重要度的排名，排名靠前的即为摘要语句；其中计算句子与文本的相似度，就可以用BM25算法来进行处理.

BM25算法原理

核心思想 : 对 Query 进行语素解析，生成语素 $q_i$；然后对于每个搜索结果 $D$，计算每个语素 $q_i$ 与 $D$ 的相关性得分，最后将 $q_i$ 相对于 $D$ 的相关性得分进行加权求和，从而得到 Query 与 D 的相关性得分.

Query 为一次查询，比如用户在浏览器上输入的一句查询语句.

语素是最小的语音、语义结体，是最小的有意义的语言单位；在中文处理中，通常对 Query 的分词作为语素分析，分词后的每个词即表示一个语素.

---

BM25算法的一般性公式为 :

$$Score(Q,D) = \sum_i^n W_i \cdot R(q_i,D)$$ 其中 :

• $Q$ 表示 Query语句，$q_i$ 表示 $Q$ 解析之后的一个语素

• $D$ 表示一个搜索结果文档

• $W_i$ 表示语素 $q_i$ 的权重

• $R(q_i,D)$ 表示语素 $q_i$ 与文档 $D$ 的相关性得分

---

下面考察如何来定义 $W_i$。判断一个词与一个文档的相关度的权重，方法有很多，较常用的是 IDF，所以下面以 IDF 为例来说明 :

$$IDF(q_i) = log{\frac{N-n(q_i) + 0.5}{n(q_i) + 0.5}}$$ 其中，$N$ 为索引中的全部文档数，$n(q_i)$ 为包含了 $q_i$ 的文档数.

于是根据 IDF 的定义可知，对于给定的文档集合，包含了 $q_i$ 的文档数越多，$q_i$ 的权重则越低。

也即是说，当很多文档都包含 $q_i$ 时，$q_i$ 的区分度就不高，因此使用 $q_i$ 来判断相关性的重要度就不高.

---

再来考察语素 $q_i$ 与文档 $D$ 的相关性得分 $R(q_i,D)$ :

$$R(q_i,d) = \frac{f_i \cdot (k_1 + 1)}{f_i + K} \cdot \frac{qf_i \cdot (k_2 + 1)}{qf_i + k_2} \\ K = k_1 \cdot (1 - b + b \cdot \frac{dl}{avg(dl)})$$ 其中 :

• $k_1,k_2,b$ 为调节因子，通常根据经验设置，一般是 $k_1 = 2,b = 0.75$

• $f_i$ 为 $q_i$ 在 $D$ 中出现的频率

• $qf_i$ 为 $q_i$ 在 Query 中出现的频率

• $dl$ 为文档 $D$ 的长度

• $avg(dl)$ 为文档集中所有文档的平均长度

由于绝大部分情况下，$q_i$ 在 Query 中只会出现一次，即 $qf_i = 1$，所以公式可以简化为 :

$$R(q_i,D) = \frac{f_i \cdot (k_1 + 1)}{f_i + K}$$

---

从 $K$ 的定义可以看出，参数 $b$ 的作用是调整文档长度对相关性影响的大小。$b$ 越大，文档长度的相关性得分的影响越大，反之越小。

而文档的相对长度越长，$K$ 值将越大，则相关性得分会越小。这可以理解为，当文档较长时，包含 $q_i$ 的机会越大，因此，同等 $f_i$ 的情况下，长文档与 $q_i$ 的相关性应该比短文档与 $q_i$ 的相关性弱。

综上，BM25算法的相关性得分公式总结为 :

$$Score(Q,D) = \sum_i^n IDF(q_i) \cdot \frac{f_i \cdot (k_1 + 1)}{f_i + k_1 \cdot \left( 1 - b + b \cdot \frac{dl}{avg(dl)} \right)}$$

从BM25的公式可以看出，通过使用不同的语素分析方法、语素权重判定方法，以及语素与文档的相关性判定方法，我们可以衍生出不同的搜索相关性得分计算方法，这就为我们设计算法提供了较大的灵活性.

---

举例说明

假设现在有文档集为 :

我爱吃苹果
苹果是我最爱吃的水果
香蕉我也爱吃

查询语句为 :

香蕉和苹果

分别对文档集合查询语句做分词，得到语素单元 :

我 爱 吃 苹果
苹果 是 我 最 爱 吃 的 水果
香蕉 我 也 爱吃
香蕉 和 苹果

根据 IDF 的计算公式，则有 :

$$IDF(香蕉) = \log \frac{3 - 1 + 0.5}{1 + 0.5} \\ IDF(和) = \log \frac{3 - 0 + 0.5}{ 0 + 0.5} \\ IDF(苹果) = \log \frac{3-2 + 0.5}{2 + 0.5} \\ f(香蕉) = 1 \\ f(和) = 0 \\ f(苹果) = 2 \\ dl_1 = 5 \\ dl_2 = 10 \\ dl_3 = 6 \\ avg(dl) = \frac{5 + 10 + 6}{3}$$ 则， $$Score(Q,D) = IDF(香蕉) \cdot \frac{f(香蕉) \cdot (k_1 + 1)}{f(香蕉) + k_1 \cdot (1 - b + b \cdot \frac{dl}{avg(dl)})} \\ + IDF(和) \cdot \frac{f(和) \cdot (k_1 + 1)}{f(和) + k_1 \cdot (1 - b + b \cdot \frac{dl}{avg(dl)})} \\ + IDF(苹果) \cdot \frac{f(苹果) \cdot (k_1 + 1)}{f(苹果) + k_1 \cdot (1 - b + b \cdot \frac{dl}{avg(dl)})}$$ 其中，$k_1 = 2,b = 0.75$

---

java 源码分析

这里的BM25实现是用的是上篇自动摘要的工程代码，下载地址为 : https://github.com/hankcs/TextRank

我们之间从代码开始分析：

//传入文档句子列表，每个句子又是单词列表
public BM25(List<List<String>> docs){
    this.docs = docs;
    //计算句子总数
    D = docs.size();
    for (List<String> sentence : docs){
        avgdl += sentence.size();
    }
    //计算所有文档的平均句子长度
    avgdl /= D;
    f = new Map[D];
    df = new TreeMap<String, Integer>();
    idf = new TreeMap<String, Double>();
    init();
}
//计算单词的词频、IDF值
private void init(){
    int index = 0;
    for (List<String> sentence : docs){
        Map<String, Integer> tf = new TreeMap<String, Integer>();
        for (String word : sentence){
            Integer freq = tf.get(word);
            freq = (freq == null ? 0 : freq) + 1;
            tf.put(word, freq);
        }
        f[index] = tf;
        for (Map.Entry<String, Integer> entry : tf.entrySet()){
            String word = entry.getKey();
            Integer freq = df.get(word);
            //使用平滑处理
            freq = (freq == null ? 0 : freq) + 1;
            df.put(word, freq);
        }
        ++index;
    }
    for (Map.Entry<String, Integer> entry : df.entrySet()){
        String word = entry.getKey();
        Integer freq = entry.getValue();
        //计算idf，对数线性处理
        idf.put(word, Math.log(D - freq + 0.5) - Math.log(freq + 0.5));
    }
}

初始化做了几步，计算了句子长度，平均句子长度，以及各个单词的词频、 idf值.

public double sim(List<String> sentence, int index){
    double score = 0;
    for (String word : sentence){
        if (!f[index].containsKey(word)) continue;
        int d = docs.get(index).size();
        Integer wf = f[index].get(word);
        //此即为上述最后的BM25算法计算公式
        score += (idf.get(word) * wf * (k1 + 1)
                / (wf + k1 * (1 - b + b * d/ avgdl)));
    }
    return score;
}

此算法相对还比较简单，读者可以自己仿照实现 R版本的BM25算法.