野次馬エンジニア道

野次馬な気持ちでプログラミングをあれこれと綴ります

ElasticSearch入門 (3) スコアの計算

フィルタリングの話の前にスコアの計算が気になったので深く見てみることにした。

基本的な知識

ベクトル空間モデル

単語を一つのベクトルとして表現して扱うベクトル空間モデルでは、ドキュメントの類似度をコサイン距離で計算する。

{\displaystyle
  cosine-similarity(q,d) = \frac{ V(q) \cdot V(d) }{ |V(q)| |V(d)| }
}

正規化することでドキュメントの長さの情報が失われてしまうのが問題点。

TF・IDF

より良い結果を得る方法として各タームを出現頻度によって重みづけるというやり方が知られている。{\displaystyle
D=\left\{ d_{1},d_{2},...,d_{n}\right\}
} をドキュメントの集合として、 各タームの {w_{j}}に対して{n_{ij}}を文書{d_{i}}における {w_{j}}の出現回数、{n_{j}}{w_{j}}が一回以上含まれる文書の数としたときに

{ \displaystyle
tf_{ij} \doteq \frac{n_{ij}}{|d_{i}|}
}

{ \displaystyle
idf_{j} \doteq \log \frac{n}{n_{j}}
}

IDFはドキュメント全体におけるタームの重要性なイメージ。{d_{i}}における{w_{j}}の重みは{ tf_{ij} \cdot idf_{j} }。 他にも定義は色々存在するようだ*1

Luceneのスコア計算

概念的なスコア計算

Luceneでは、{|V(d)|}のノルムの部分を以下のように分解している。

{
 score(q,d) = coord(q,d) * queryBoost(q) * \frac{ V(q) \cdot V(d) }{ |V(q)| } * lengthNorm(d) * docBoost(d)
}

説明
coord ドキュメントに含まれるタームの数による調整項。他のドキュメントに比べてどれだけ多くの検索タームを含むか。
queryBoost 特定のフィールドに対するクエリへのブースト
lengthNorm 正規化項、短いワードでドキュメントが構成される方がスコアが高い
docBoost 特定のドキュメントに対するブースト

実際のスコア計算

コンセプトとしては上記だが実際のLuceneではTF・IDFでも重み付けも合わせて下記のように算出している。

{ \displaystyle
score(q,d) =
}

{ \displaystyle
coord(q,d) * queryNorm(q) * \sum_{t\ in\ q}(tf(t\ in\ d)*idf(t)^2 * boost(t) * norm(t,d))
}

説明
coord ドキュメントに含まれるタームの数による調整項。他のドキュメントに比べてどれだけ多くの検索タームを含むか。
queryNorm 異なるクエリ間でスコアを比較するための正規項。{|V(q)|}の部分
boost {queryBoost(q)}の部分をターム毎に分解
norm {docBoost(d)}{lengthNorm(d)}をまとめてターム毎に分解

正規化のための項やインデックス時に計算できる項は予め別に切り出し、さらにターム毎にブーストが設定できる。 それぞれを見ていくと、

TF・IDF

Luceneでは下記の通り算出する。意味合いとしては上で見たのと同じ。ここがスコア算出の中心となる。

{ \displaystyle
tf(t\ in\ d) = frequency^{1/2}
}

{ \displaystyle
idf(t) = 1 + \log{}\frac{numDocs}{docFreq+1}
}

queryNorm, boost

{
queryNorm(q) = queryNorm(sumOfSquaredWeights) = \frac{1}{sumOfSquaredWeights^{1/2}}
}

{
sumOfSquaredWeights = q.getBoost()^{2} \cdot \sum_{t\ in\ q} \left( idf(t) \cdot t.getBoost() \right)^{2}
}

{t.getBoost()} の部分は検索時にターム毎に設定するブースト値。

norm(t.d)

インデックス時に設定するブーストと長さをまとめたもの。

{norm(t,d) = lengthNorm \cdot } \prod_{field\ f\ in\ d\ named\ as\ t} f.boost()

珍しいタームにマッチした方が高いスコアになり、フィールド内のタームの数が少ない方がスコアが高くなる。 インデックス時、検索時に双方でブーストを設定できることでより重要度の高いタームを含むドキュメントにつくスコアを調整することができる。

ElasticSearchでのスコア計算

下記のようなデータを入れる。

POST scoring/doc/1
{ "name" : "one two" }
POST scoring/doc/2
{ "name" : "one three" }
POST scoring/doc/3
{ "name" : "one two three" }
POST scoring/doc/4
{ "name" : "one two three four" }

下記で検索。

GET scoring/_search
{
  "query" : {
    "match" : {
      "name" : "one two"
    }
  }
}

スコア順だと

{
  "_index": "scoring",
  "_type": "doc",
  "_id": "1",
  "_score": 0.79143506,
  "_source": {
    "name": "one two"
  }
}
{
  "_index": "scoring",
  "_type": "doc",
  "_id": "3",
  "_score": 0.6331481,
  "_source": {
    "name": "one two three"
  }
}
{
  "_index": "scoring",
  "_type": "doc",
  "_id": "4",
  "_score": 0.6331481,
  "_source": {
    "name": "one two three four"
  }
}
{
  "_index": "scoring",
  "_type": "doc",
  "_id": "2",
  "_score": 0.14893481,
  "_source": {
    "name": "one three"
  }
}

フィールド内のタームの数が少ない方がスコアが高くなる。

explain API

下記のようにElasticSearch内部のスコア計算過程を確認できる*2

GET scoring/doc/1/_explain
{
  "query" : {
    "match" : {
      "name" : "one two"
    }
  }
}

{
  "_index": "scoring",
  "_type": "doc",
  "_id": "1",
  "matched": true,
  "explanation": {
    "value": 0.79143506,
    "description": "sum of:",
    "details": [
      {
        "value": 0.79143506,
        "description": "sum of:",
        "details": [
          {
            "value": 0.29786962,
            "description": "weight(name:one in 0) [PerFieldSimilarity], result of:",
            "details": [
              {
                "value": 0.29786962,
                "description": "score(doc=0,freq=1.0), product of:",
                "details": [
                  {
                    "value": 0.6134871,
                    "description": "queryWeight, product of:",
                    "details": [
                      {
                        "value": 0.7768564,
                        "description": "idf(docFreq=4, maxDocs=4)",
                        "details": []
                      },
                      {
                        "value": 0.7897047,
                        "description": "queryNorm",
                        "details": []
                      }
                    ]
                  },
                  {
                    "value": 0.48553526,
                    "description": "fieldWeight in 0, product of:",
                    "details": [
                      {
                        "value": 1,
                        "description": "tf(freq=1.0), with freq of:",
                        "details": [
                          {
                            "value": 1,
                            "description": "termFreq=1.0",
                            "details": []
                          }
                        ]
                      },
                      {
                        "value": 0.7768564,
                        "description": "idf(docFreq=4, maxDocs=4)",
                        "details": []
                      },
                      {
                        "value": 0.625,
                        "description": "fieldNorm(doc=0)",
                        "details": []
                      }
                    ]
                  }
                ]
              }
            ]
          },
// 途中まで

1番目のドキュメント("one two")のスコアは、

{
 0.79143506 = 0.29786962("one") + 0.49356544("two")
}

{
= (0.6134871 * 0.48553526) + (0.7897047 * 0.625)
}

のように分解される。 前半の {0.6134871 * 0.48553526} はさらに

{
 0.6134871 =  idf(docFreq=4, maxDocs=4) * queryNorm
}

{
= 0.7768564 * 0.7897047
}

{
0.48553526 = tf(freq=1.0) * idf(docFreq=4, maxDocs=4) * fieldNorm(doc=0)
}

{
= 1 * 0.7768564 * 0.625
}

になる。{idf}{queryNorm} は上の式の通り算出可能。

最後のfieldNormだけ計算が合わないが、理由は浮動小数点を限られたビット数でエンコードされているからのようだ*3

参考