chenfh5

elasticsearch relevance scoring 检索相关性计算

  • Nov 16, 2017

记录一下，elasticsearch/lucene关于文档与query之间相关性的计算方式，

Lucene/es评分机制

https://www.elastic.co/guide/en/elasticsearch/guide/current/scoring-theory.html http://mp.weixin.qq.com/s/By340-7g5rDxVKehY1izeQ

es使用Boolean model来匹配文档；使用practical scoring function(tfidf, BM25)来计算文档与query的相关性；使用vector space model来增加额外特征计算（如queryNorm，coord，norm，boost）。

注，一般query为指定在某个field中查询的。即score(field, query)；而如果不指定field，且_all字段enable，那么就在该条doc中查询，即score(doc, query)。

Query & Term
query = quick brown fox
term1 = quick
term2 = brown
term3 = fox
Boolean Model

full AND text AND search AND (elasticsearch OR lucene).

Term Frequency/Inverse Document Frequency (TF/IDF)

词频/逆向文档频率，term的重要性随着它在文档doc中出现的次数成正比增加，但同时会随着它在语料库docs中出现的频率成反比下降。主要包含三部分，

  • tf，该词在一篇文档中出现的次数，tf(t in d) = √frequency
  • idf，该词出现在多少篇文档中（出现一次也算出现），idf(t) = 1+ log((numDocs + 1)/(docFreq + 1))
  • field-length norm，doc/field的文本长度，norm(d) = 1 / √numTermsInDoc

image

tfidf

//disable field-length norm可以减少index时候的计算量，加快index速度
PUT /my_index
{
  "mappings": {
    "doc": {
      "properties": {
        "text": {
          "type": "string",
          "norms": { "enabled": false }
        }
      }
    }
  }
}
Vector Space Model

使得query与doc之间的相关性可以比较。

image

query与三文档的对比

上图中，query = “happy hippopotamus”，权重分别是2, 5， doc1 = I am happy in summer. doc2 = After Christmas I’m a hippopotamus. doc3 = The happy hippopotamus helped Harry. 文档3与query最相关(夹角最小)。

Lucene’s Practical Scoring Function

lucene的计分函数，对于multiterm查询，lucene将布尔模型（Boolean）、词频/逆向文档频率（tfidf）、向量空间模型（vector space）合并到一个统一的jar包里面，用以收集匹配文档和分数计算。

//原生multiterm query语句
GET /my_index/doc/_search
{
  "query": {
    "match": {
      "text": "quick fox"
    }
  }
}

//布尔模型实现的改写
GET /my_index/doc/_search
{
  "query": {
    "bool": {
      "should": [
        {"term": { "text": "quick" }},
        {"term": { "text": "fox"   }}
      ]
    }
  }
}

只要一个文档与查询匹配，lucene就会对该文档算分，然后合并每个term的得分，用到了practical scoring function，

score(q, d)  =  #1
            queryNorm(q)  #2
          · coord(q, d)    #3
          · ∑ (           #4
                   tf(t in d)   #5
                 · idf(t)²      #6
                 · t.getBoost() #7
                 · norm(t, d)    #8
            ) (t in q)    #9
  1. score(q, d)，文档d 与查询q 的相关度分数（relevance score）
  2. queryNorm(q)，查询正则因子（query normalization factor）
  3. coord(q, d)，协调因子（coordination factor）
  4. sum with #9
  5. tf(t in d)，term t 在文档d 中的词频
  6. idf(t)，term t 的逆向文档频率
  7. t.getBoost()，查询中使用的自定义boost
  8. norm(t, d)，文档d的文本长度正则值
  9. sum with #4，查询 q 中每个term t 对于文档d 的权重和
queryNorm

queryNorm试图将查询正则化，以便可以比较两个不同query的结果。（不是很有效）

coord

协调因子，

query = "quick brown fox"

//without coord (the weight for each term is 1.5)
Document with fox → score: 1.5
Document with quick fox → score: 3.0
Document with quick brown fox → score: 4.5

//with coord
Document with fox → score: 1.5 * 1 / 3 = 0.5
Document with quick fox → score: 3.0 * 2 / 3 = 2.0
Document with quick brown fox → score: 4.5 * 3 / 3 = 4.5
{norm

文本长度。文本越短，文本的权重越高。norm(d) = 1 / √numTermsInDoc

boost}

自定义权重。

Query-Time Boosting

查询时权重提升，在搜索时令一个查询语句的自定义权重有别于其他查询语句，会更加符合个性化定制搜索的需求。

GET /_search
{
  "query": {
    "bool": {
      "should": [
        {
          "match": {
            "title": {
              "query": "quick brown fox",
              "boost": 2
            }
          }
        },
        {
          "match": {
            "content": "quick brown fox"
          }
        }
      ]
    }
  }
}

query在title字段的自定义权重比在content字段的大(2>1)，默认是1。

Ignoring TF/IDF

有时我们只关心一个term是否在某个doc中出现过，而不在乎它在doc中是否频繁出现，此时可以省去计算tfidf的耗时，加快检索速度。

constant_score

constant_score替代match，不计算tfidf，但是计算其余项的分数。

//match
GET /_search
{
	"query": {
		"match": {
			"description": "wifi garden pool"
		}
	}
}

//constant_score
GET /_search
{
    "query": {
        "constant_score" : {
            "filter" : {
                "term" : { "user" : "kimchy"}
            },
            "boost" : 1.2
        }
    }
}
function_score query

https://www.elastic.co/guide/en/elasticsearch/reference/6.0/query-dsl-function-score-query.html#function-decay

es检索时默认会以文档的相关性进行排序，而如果想要改变默认的排序规则，可以通过sort指定一个或多个排序字段。

GET /_search
{
    "query" : {
        "bool" : {
            "filter" : { "term" : { "user_id" : 1 }}
        }
    },
    "sort": { "date": { "order": "desc" }}
}

但是直接指定sort排序过于直接，可能效果不好（除非sort字段index前已经计算好）。此时就需要对多个字段进行综合评估，用到function_score，它允许我们为每个与query查询匹配的doc应用一个scoring函数，以达到改变默认规则的目的。es已有的function_score，如下，

  • weight，为每个doc应用一个直接而不被正则化的权重提升值：当 weight=2 时，最终结果为 2 * _score（与constant_score的boost=2不同，constant_score的boost参与到_score的正则化计算中，只是constant_score没有计算tfidf，其余项quertNorm, coord, norm, boost都要参与到正则化计算中）
  • random_score，根据seed随机种子，返回一个0到1的分数；seed相同，随机分相同。多用于个性化推荐
  • field_value_factor，通过doc中指定filed从而计算出一个排序分
    • field，指定的字段名
    • factor，缩放系数，默认为1
    • modifier，字段加工方式
      • none，不处理
      • log，对数
      • log1p，字段值+1后取对数
      • square，平方
      • sqrt，开方
      • reciprocal，倒数，etc.
  • decay_function，linear线性，exp指数，gauss高斯，入参如下，
    • orgin，原点
    • scale，衰减点
    • offset，非零偏移量，默认0
    • decay，从原点衰减到scale点的所得分，默认0.5，即scale点的文档得分是0.5
  • script_score，通过脚本自定义不同字段的不同得分逻辑
//weight & random_score & score_mode & boost_mode
GET /_search
{
  "query": {
    "function_score": {
      "filter": {
        "term": { "city": "Barcelona" }
      },
      "functions": [
        {
          "filter": { "term": { "features": "wifi" }},
          "weight": 1
        },
        {
          "filter": { "term": { "features": "garden" }},
          "weight": 1
        },
        {
          "filter": { "term": { "features": "pool" }},
          "weight": 2
        },
        {
          "random_score": {
            "seed":  "the_users_session_id"
          }
        }
      ],
      "score_mode": "sum",
      "boost_mode": "multiply"
    }
  }
}

//field_value_factor
GET /_search
{
    "query": {
        "function_score": {
            "field_value_factor": {
                "field": "likes",
                "factor": 1.2,
                "modifier": "sqrt",
                "missing": 1
            }
        }
    }
}

//delay function(d = day)
GET /_search
{
    "query": {
        "function_score": {
            "gauss": {
                "date": {
                      "origin": "2013-09-17",
                      "scale": "10d",
                      "offset": "5d",
                      "decay" : 0.5
                }
            }
        }
    }
}

image

decay_function

score combination
  • score_mode，function_score与function_score之间的相处方式，
    • multiply，默认
    • sum
    • avg
    • max/min
    • first
  • boost_mode，function_score与_score之间的相处方式，
    • multiply，默认
    • sum
    • avg
    • max/min
    • replace

Pluggable Similarity Algorithms

es配置了多种检索相关性算法可供选择，

  • tfidf，默认
  • BM25
  • DFR, DFI, IB, etc.

其中，lucene自6.0起使用BM25代替了之前的tfidf。

//configure BM25 in mapping setting
PUT /my_index
{
  "mappings": {
    "doc": {
      "properties": {
        "title": {
          "type":       "string",
          "similarity": "BM25"
        },
        "body": {
          "type":       "string",
          "similarity": "default"
        }
      }
  }
}
BM25

http://fjdu.github.io/coding/2017/03/16/bm25-elasticsearch-lucene.html http://www.jianshu.com/p/0b372804ff45 https://en.wikipedia.org/wiki/Okapi_BM25

Best Match 25，发布于1994年，是调整相关性计算的第25次迭代。 引入了Term frequency saturation（词频饱和度)，计算如下，

image

BM25

其中，

  • D ：文档长度
  • avgdl：所有文档的平均文档长度
  • k1，b是自由参数，lucene默认k1=1.2，b=0.75
  • IDF = log((#Docs - #DocsHit + 0.5)/(#DocsHit + 0.5))
  • TF = query count in one doc

image

词频饱和度snapshot (blue)

image

Term frequency saturation for TF/IDF vs. BM25

BM25F

http://www.cnblogs.com/bentuwuying/p/6730891.html

BM25F是BM25的改进版本，BM25在计算文档与query的相关性时将文档当做整体来考虑；但是随着advanced search的发展，文档的结构化（即每个文档都可以切分成多个独立的域field，比如title，abstract，keyword，body text等）需要被考虑，不同的域对相关性的贡献应该要更精细地处理，而BM25F就是query在文档的各个field中分值的加权求和。

chenfh5 © 2024
Search