OKapi BM25 算法详解

BM25（Best Match25）是在信息检索系统中根据提出的query对document进行评分的算法。It is based on the probabilistic retrieval framework developed in the 1970s and 1980s by Stephen E. Robertson, Karen Spärck Jones, and others.BM25算法首先由OKapi系统实现，所以又称为OKapi BM25。

BM25属于bag-of-words模型，bag-of-words模型只考虑document中词频，不考虑句子结构或者语法关系之类，把document当做装words的袋子，具体袋子里面可以是杂乱无章的。It is not a single function, but actually a whole family of scoring functions, with slightly different components and parameters. One of the most prominent instantiations of the function is as follows.

对于一个query $Q$ , 包括关键字 $q_1, ..., q_n$ , 一个文档的BM25得分:

$text{score}(D,Q) = sum_{i=1}^{n} text{IDF}(q_i) cdot frac{f(q_i, D) cdot (k_1 + 1)}{f(q_i, D) + k_1 cdot (1 - b + b cdot frac{|D|}{text{avgdl}})},$ 其中IDF是上篇文章《TD-IDF》中的IDF，f是《TD-IDF》中的TF，|D|是文档D的长度，avgdl是语料库全部文档的平均长度。k₁和b是参数。usually chosen, in absence of an advanced optimization, as $k_1 in [1.2,2.0]$ and $b = 0.75$ 。

TF-IDF

词语频率( Term Frequency), 简称 “TF”, 是一个很简单的度量标准：一个特定的词语在文档出现的次数。你可以把这个值除以该文档中词语的总数，得到一个分数。例如文档中有 100 个词， ‘the’ 这个词出现了 8 次，那么 ‘the’ 的 TF 为 8 或 8/100 或 8%（取决于你想怎么表示它）。

逆向文件频率（Inverse Document Frequency）, 简称 “IDF”，要复杂一些：一个词越稀有，这个值越高。它由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到。越是稀有的词，越会产生高的 “IDF”。

如果你将这两个数字乘到一起 (TF*IDF), 你将会得到一个词语在文档中的权重。“权重”的定义是：这个词有多稀有并且在文档中出现的多么频繁？

你可以将这个概念用于文档的搜索查询。在查询中的对于查询中的每个关键字，计算他们的 TF-IDF 分数，并把它们相加。得分最高的就是与查询语句最符合的文档。

很酷吧！

Okapi BM25

上述算法是一个可用的算法，但并不太完美。它给出了一个基于统计学的相关分数算法，我们还可以进一步改进它。

Okapi BM25 是到目前为止被认为最先进的排名算法之一（所以被称为 ElasticSearch ）。Okapi BM25 在 TF-IDF 的基础上增加了两个可调参数，k1 和 b，, 分别代表 “词语频率饱和度（term frequency saturation）” 和 “字段长度规约”。这是什么鬼？

为了能直观的理解“词语频率饱和度”，请想象两篇差不多长度的讨论棒球的文章。另外，我们假设所有文档(除去这两篇)并没有多少与棒球相关的内容，因此 “棒球” 这个词将具有很高的 IDF – 它极稀少而且很重要。这两篇文章都是讨论棒球的，而且都花了大量的篇幅讨论它，但是其中一篇比另一篇更多的使用了“棒球”这个词。那么在这种情况，是否一篇文章真的要比另一篇文章相差很多的分数呢？既然两个两个文档都是大篇幅讨论棒球的，那么“棒球”这个词出现 40 次还是 80 次都是一样的。事实上，30 次就该封顶啦！

这就是 “词语频率饱和度。原生的 TF-IDF 算法没有饱和的概念，所以出现 80 次“棒球”的文档要比出现 40 次的得分高一倍。有些时候，这时我们所希望的，但有些时候我们并不希望这样。

此外，Okapi BM25 还有个 k1 参数，它用于调节饱和度变化的速率。k1 参数的值一般介于 1.2 到 2.0 之间。数值越低则饱和的过程越快速。（意味着两个上面两个文档有相同的分数，因为他们都包含大量的“棒球”这个词语）

字段长度归约（Field-length normalization）将文档的长度归约化到全部文档的平均长度上。这对于单字段集合（single-field collections）（例如 ours）很有用，可以将不同长度的文档统一到相同的比较条件上。对于双字段集合（例如 “title” 和 “body”）更加有意义，它同样可以将 title 和 body 字段统一到相同的比较条件上。字段长度归约用 b 来表示，它的值在 0 和 1 之间，1 意味着全部归约化，0 则不进行归约化。

算法

在Okapi BM25 维基百科中你可以了解Okapi算法的公式。既然都知道了式子中的每一项是什么，这肯定是很容易地就理解了。所以我们就不提公式，直接进入代码:

BM25.Tokenize = function(text) {
    text = text
        .toLowerCase()
        .replace(/W/g, ' ')
        .replace(/s+/g, ' ')
        .trim()
        .split(' ')
        .map(function(a) { return stemmer(a); });
 
    // Filter out stopStems
    var out = [];
    for (var i = 0, len = text.length; i < len; i++) {
        if (stopStems.indexOf(text[i]) === -1) {
            out.push(text[i]);
        }
    }
 
    return out;

我们定义了一个简单的静态方法Tokenize()，目的是为了解析字符串到tokens的数组中。就这样，我们小写所有的tokens（为了减少熵）。我们运行Porter Stemmer 算法来减少熵的量同时也提高匹配程度（“walking”和”walk”匹配是相同的）。而且我们也过滤掉停用词（很普通的词）为了更近一步减少熵值。在我所写的概念深入之前，如果我过于解释这一节就请多担待。

BM25.prototype.addDocument = function(doc) {
    if (typeof doc.id === 'undefined') { throw new Error(1000, 'ID is a required property of documents.'); };
    if (typeof doc.body === 'undefined') { throw new Error(1001, 'Body is a required property of documents.'); };
 
    // Raw tokenized list of words
    var tokens = BM25.Tokenize(doc.body);
 
    // Will hold unique terms and their counts and frequencies
    var _terms = {};
 
    // docObj will eventually be added to the documents database
    var docObj = {id: doc.id, tokens: tokens, body: doc.body};
 
    // Count number of terms
    docObj.termCount = tokens.length;
 
    // Increment totalDocuments
    this.totalDocuments++;
 
    // Readjust averageDocumentLength
    this.totalDocumentTermLength += docObj.termCount;
    this.averageDocumentLength = this.totalDocumentTermLength / this.totalDocuments;
 
    // Calculate term frequency
    // First get terms count
    for (var i = 0, len = tokens.length; i < len; i++) {
        var term = tokens[i];
        if (!_terms[term]) { 
            _terms[term] = {
                count: 0,
                freq: 0
            }; 
        };
        _terms[term].count++;
    }
 
    // Then re-loop to calculate term frequency.
    // We'll also update inverse document frequencies here.
    var keys = Object.keys(_terms);
    for (var i = 0, len = keys.length; i < len; i++) {
        var term = keys[i];
        // Term Frequency for this document.
        _terms[term].freq = _terms[term].count / docObj.termCount;
 
        // Inverse Document Frequency initialization
        if (!this.terms[term]) {
            this.terms[term] = {
                n: 0, // Number of docs this term appears in, uniquely
                idf: 0
            };
        }
 
        this.terms[term].n++;
    };
 
    // Calculate inverse document frequencies
    // This is SLOWish so if you want to index a big batch of documents,
    // comment this out and run it once at the end of your addDocuments run
    // If you're only indexing a document or two at a time you can leave this in.
    // this.updateIdf();
 
    // Add docObj to docs db
    docObj.terms = _terms;
    this.documents[docObj.id] = docObj;
};

这就是addDocument()这种方法会奇迹般出现的地方。我们基本上建立和维护两个类似的数据结构:this.documents.和this.terms。

this.documentsis 是一个保存着所有文档的数据库，它保存着文档的全部原始文字，文档的长度信息和一个列表，列表里面保存着文档中的所有词语和词语的数量与出现频率。使用这个数据结构，我们可以很容易的和快速的（是的，非常快速，只需要时间复杂度为O(1)的哈表查询时间）回答如下问题：在文档 #3 中，’walk’ 这个词语出现了多少次？

我们在还使用了另一个数据结构，this.terms。它表示语料库中的所有词语。通过这个数据结构，我们可以在O(1)时间内回答如下问题：’walk’ 这个词在多少个文档中出现过？他们的 id 是什么？

最后，我们记录了每个文档的长度，并记录了整个语料库中文档的平均长度。

注意，上面的代码中， idf 被初始化 0，而且 updateidf() 方法被注释掉了。这是因为这个方法运行的非常慢，并且只需在建立索引之后运行一次就可以了。既然运行一次就能满足需求，就没有必要运行5000次。先把它注释掉，然后在大批量的索引操作之后运行，就可以节省很多时间。下面是这个函数的代码：

BM25.prototype.updateIdf = function() {
    var keys = Object.keys(this.terms);
    for (var i = 0, len = keys.length; i < len; i++) {
        var term = keys[i];
        var num = (this.totalDocuments - this.terms[term].n + 0.5);
        var denom = (this.terms[term].n + 0.5);
        this.terms[term].idf = Math.max(Math.log10(num / denom), 0.01);
    }
};

这是一个非常简单的函数，但是由于它需要遍历整个语料库中的所有词语，并更新所有词语的值，这就导致它工作的就有点慢。这个方法的实现采用了逆向文档频率 (inverse document frequency) 的标准公式（你可以在 Wikipedia 上找到这个公式）— 由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到。我做了一些修改，让返回值一直大于0。

BM25.prototype.search = function(query) {
 
    var queryTerms = BM25.Tokenize(query);
    var results = [];
 
    // Look at each document in turn. There are better ways to do this with inverted indices.
    var keys = Object.keys(this.documents);
    for (var j = 0, nDocs = keys.length; j < nDocs; j++) {
        var id = keys[j];
        // The relevance score for a document is the sum of a tf-idf-like
        // calculation for each query term.
        this.documents[id]._score = 0;
 
        // Calculate the score for each query term
        for (var i = 0, len = queryTerms.length; i < len; i++) {
            var queryTerm = queryTerms[i];
 
            // We've never seen this term before so IDF will be 0.
            // Means we can skip the whole term, it adds nothing to the score
            // and isn't in any document.
            if (typeof this.terms[queryTerm] === 'undefined') {
                continue;
            }
 
            // This term isn't in the document, so the TF portion is 0 and this
            // term contributes nothing to the search score.
            if (typeof this.documents[id].terms[queryTerm] === 'undefined') {
                continue;
            }
 
            // The term is in the document, let's go.
            // The whole term is :
            // IDF * (TF * (k1 + 1)) / (TF + k1 * (1 - b + b * docLength / avgDocLength))
 
            // IDF is pre-calculated for the whole docset.
            var idf = this.terms[queryTerm].idf;
            // Numerator of the TF portion.
            var num = this.documents[id].terms[queryTerm].count * (this.k1 + 1);
            // Denomerator of the TF portion.
            var denom = this.documents[id].terms[queryTerm].count 
                + (this.k1 * (1 - this.b + (this.b * this.documents[id].termCount / this.averageDocumentLength)));
 
            // Add this query term to the score
            this.documents[id]._score += idf * num / denom;
        }
 
        if (!isNaN(this.documents[id]._score) && this.documents[id]._score > 0) {
            results.push(this.documents[id]);
        }
    }
 
    results.sort(function(a, b) { return b._score - a._score; });
    return results.slice(0, 10);
};

最后，search() 方法遍历所有的文档，并给出每个文档的 BM25 分数，然后按照由大到小的顺序进行排序。当然了，在搜索过程中遍历语料库中的每个文档实是不明智。这个问题在 Part Two （反向索引和性能）中得到解决。

上面的代码已经做了很好的注释，其要点如下：为每个文档和每个词语计算 BM25 分数。词语的 idf 分数已经预先计算好了，使用的时候只需要查询即可。词语频率作为文档属性的一部分也已经预先计算好了。之后只需要简单的四则运算即可。最后给每个文档增加一个临时变量 _score，然后根据 score 做降序排列并返回前 10 个结果。