Elasticsearchで使われているLucene's Practical Scoring Functionを数式から説明する

はじめに

この記事ではLucene's Practical Scoring Functionについて説明する。これはオープンソースのRESTful分散検索/分析エンジンで、Apache Lucene を基盤として構築されたElastic Searchという検索エンジンにデフフォルトで使われている。ある検索クエリに対する文章の関連性を表すスコアを求める関数である。この記事で出てくる数式はここから引用した。
tf-idf、BM25についても以前記事にしたのでこちらを理解してからこの記事を読んだ方が理解しやすいと考えられる。

数式を眺めてみる

##定義
まずはじめに数式に出てくる変数を定義する。文章全体の集合(以後全文章と呼ぶ)を$D$とし、その部分集合である文章一つ一つを$d_i$とする。また、検索クエリは$q$とし、検索クエリに含まれる単語一つ一つを$q_i$とする。検索クエリ$q$が「すもももももももものうち」であれば$q_1$が「すもも」$q_2$が「も」$q_3$が「もも」$q_4$が「も」$q_5$が「もも」$q_6$が「も」$q_7$が「うち」のようになる。

数式

はじめにLucene's Practical Scoring Functionの数式を見せる。
$$
score(q, d) = queryNorm(q) \times coord(q, d) \times \sum_i tf(q_i, d) \times idf(q_i)^2 \times q_i.getBoost()\times norm(q_i, d)
$$
初めてこの数式を見た場合出てきた関数が何をしているかわからず、難しく感じると思うので簡単に説明する。

• $queryNorm(q)$は検索クエリ$q$の正規化項
• $cord(q, d)$は検索クエリ$q$のうち文章$d$中に含まれる単語$q_i$の割合
• $tf(q_i, d)$は文章$d$における単語$q_i$の出現頻度
• $idf(q_i)$は全文章$D$における単語$q_i$のレア度
• $q_i.getBoost()$は検索のスコアを大きくするためのパラメータ
• $norm(q_i, d)$は文章$d$の単語数の平方根の逆数を取った正規化項

この式を変形し、簡単にしてから部分部分についてさらに説明する(一箇所まとめただけで見通しは良くならないが)。

score(q, d) = queryNorm(q) \times coord(q, d) \times \sum_i tf(q_i, d) \times idf(q_i)^2 \times q_i.getBoost()\times norm(q_i, d)\\
= queryNorm(q) \times coord(q, d)\times \sum_i idf(q_i) \times tfidf(q_i, d) \times q_i.getBoost()

ここでは式中の関数を組み合わせることでtd-idfの項を作成した。

tf-idfとnorm

先ほどの変形でnormが消えて不思議に感じられたと考えられる。これは

tf(q_i, d) = \sqrt{\#\{i|q_i\in d\}} \\
idf(q_i) = 1 + \log_2 \frac{\#D}{\#\{d\in D|q_i\in d\}+1} \\
norm(q_i, d) = \sqrt{\frac{1}{\#d}}

のように定義されているので

tfidf(q_i, d) = tf(q_i, d)\times norm(q_i, d) \times idf(q_i) 

のようにtf-idfを定義したからである(このページを信用して集合の要素数を表す記号として#を使用した)。$tfidf$にnormを含めた理由としてはtfはterm frequencyにも関わらず、frequencyしかなく、normと組み合わせることでterm frequecencyとなるからである(ルートを取っているのが気になるが普通のtfと同様の性質は持っているので値を小さくしたものと考えると良い。助詞とか大量に含まれるであろう単語の値が大きくなりすぎるのを防いでる？)。引用先でtfとnormで別れているのはElastic Searchではnormをオフにすることが可能であることが原因だと考えられる。文章の長さによる影響が重要でないときはnormをオフにすることでメモリの節約ができるのでこのような機能がある。

idfとquertNorm

tf-idfにまとめられなかった$idf$はこのスコア関数が他のスコア関数(tf-idfやBM25)に比べ単語$q_i$のレア度を重要視するために存在していると考えられる。ただ、この項を追加しただけではレア度が高い単語を羅列した検索クエリのスコアが必然的に高くなる。$queryNorm$はそれを抑えてるための関数である。実際、数式で表すと$$queryNorm(q)=\frac{1}{\sqrt{\sum_i{idf(q_i)^2}}}$$であり、確かに異なる検索クエリ間によって過剰にスコアが高くならないような正規化項となっている。これによって異なる検索クエリ間のスコアの比較が可能となる。

coord

$coord(q, d)$は検索クエリ$q$のうち文章$d$に含まれている単語$q_i$の割合を表しており、以下のように書ける。

coord(q, d) = \frac{\# \{i|q_i \in d\} }{\# q}

これは文章$d$における検索クエリの一致度によってスコアの大きさを変えている(全部含まれていたら1、一つも含まれていなかったら0)。

getBoost

getBoostは$q_i.getBoost()$のように書かれ任意の単語のスコア値を大きく設定することができる(特定の単語に重み付けをすることができる)。また、単語だけではなく任意の場所(タイトルなど)にある単語のスコアを大きくすることもできる。ここは人為的にいじるパラメータであり、0以上の実数または$%$で設定する。ElasticSearchでは場所にgetBoostを設定することをやめるように強く推奨している(パフォーマンスが悪い)。

まとめ

Lucene's Practical Scoring Functionは

score(q, d) 
= coord(q, d) \times queryNorm(q) \times \sum_i idf(q_i) \times \{tf(q_i, d) norm(q_i, d) idf(q_i)\} \times q_i.getBoost()

のように4つの部分(分かりにくいけど)に分けると理解しやすく、$coord$は検索クエリ$q$のうち文章$d$に出てきた単語の割合、$queryNorm\sum idf$はidfによる重みづけとそれに対する正規化、$tf(q_i, d) norm(q_i, d) idf(q_i)$はtf-idf、$q_i.getBoost()$は単語ごとに与える人為的なブースティングパラメータであった。
性質としてはtf-idfより単語のレア度に重点を置いたものに、検索クエリの一致度も考慮し、任意の単語の値を意図的に大きくできるものである。