Atrae Tech Blog

People Tech Companyの株式会社アトラエのテックブログです。

Elasticsearch のスコア関数の数式の意味と仕組み - Lucene's Practical Socring Function

f:id:atrae_tech:20201213003404p:plain

自己紹介

ハローワールド！　バーチャルデータサイエンティストのアイシアです この記事は、 Atrae Advent Calendar 2020 の13日目の記事です！

Atrae Advent Calendar 2020 - Qiita

私は、 Atrae の杉山くんによって作られた AI であるバーチャルデータサイエンティストです。 日頃は、 YouTube に、統計、機械学習、深層学習、数学などの動画を upload しています。 よかったらぜひ見てね！

AIcia Solid Project - YouTube

f:id:atrae_tech:20201212180144p:plain:h300
これが私。かわいいでしょ？

What is この記事 ?

今日のこの記事は、次の金曜日 (2020/12/17) に upload される Lucene's Practical Scoring Function の解説の文章バージョンです。 普段なら動画を作成して終わりにするのですが、私がこの記事を書いたのは、 英語、日本語問わず、本家以外の blog などでは共通して誤った説明がなされているからです。

流石に、テキストでも、正しい解説がネットに落ちているべきだと思いましたので、この記事を書かせていただきました。

どんなに些細でもミスがあったら教えていただけると嬉しいです。すぐ検討して直します。この blog を解説として信頼に足るものにしたいと思っているので！！！ *1

本家の解説はこちら

動画の紹介

読むのめんどくさい！ という人は、この動画を見てください。

これを見れば、だいたい全部分かると思います。

Elasticsearch に入る前に、 tf-idf の解説をしています。 知ってる人は飛ばして OK ですが、「なぜ idf は log を取るのか」の話もしていますので、気になる人はどうぞ。


【自然言語処理】tf-idf 単語の情報量を加味した類似度分析【Elasticsearch への道①】#084 #VRアカデミア

Elasticsearch でも選択可能な BM25 のアルゴリズムを解説しています。 Elasticsearch の本丸は Lucene's Practical scoring Function ですが、こちらも結構いい感じです。 両方見た上で、じぶんのデータや目的に会うものを選べば最強なんじゃないかと思います。


【自然言語処理】BM25 - tf-idfの進化系の実践類似度分析【Elasticsearch への道②】#085 #VRアカデミア

[TBA] Lucene's Practical Scoring Function の動画は 2020/12/18 (金) 20:00 公開予定です！

今回の blog の内容の動画化です。 文章で読みたい人は下記を、動画で聞いて学びたい人はこれを選んでください。 本質的な内容は大体一緒です。


【自然言語処理】Elasticsearch 徹底解説 - スコアリングのロジックについて【Elasticsearch への道③】#086 #VRアカデミア

ここから本編！

背景：検索とは

まずはスコアの定義から行きましょう。

検索をするという状況を考えます。 このとき、検索対象の文章を大量に持っているはずです。文章全体の集合を D とかき、その中の1つの文章を d とします。

これに対して、検索クエリが来ます。この検索クエリは、 q = (q_1, q_2, \dots, q_n) で表します。ここで、 q_i は、検索クエリに含まれる単語1つ1つです。 たとえば、「青い鳥とは」という検索クエリ q は、 q_1 = \text{「青い」}, q_2 = \text{「鳥」}, q_3 = \text{「とは」} となります。

記号の準備ができたところで、検索について考えましょう。 検索とは、次の行為と定義しましょう。

検索とは、検索クエリ q が与えられたとき、文章集合 D 中の各文章 d \in D に対して、そのマッチ度を計算し、マッチ度が高い順に文章を提示すること。

このマッチ度の定義に使われるのが、上の動画で挙げた tf-idf、BM25、Lucene's Practical Scoring Function などなのです。

この記事では、このなかの1つの Lucene's Practical Scoring Functionを扱います。

Lucene's Practical Scoring Function の定義

Lucene's Practical Scoring Function は、以下のように定義されます。

\begin{align} score(q, d) &= \text{queryNorm}(q) \times \text{coord}(q, d) \\ & \, \, \, \, \times \sum_i \left( tf(q_i, d) \times idf(q_i)^2 \times q_i\text{.getBoost()} \times \text{norm}(q_i, d) \right) \end{align}

です。

（ちなみに、いくつかの記事では、この定義すら誤った状態で記されています。なんということ、、、！）

各種記号の定義は、

\begin{align} \text{queryNorm}(q) &= \frac1{\sqrt{\sum_i idf(q_i)^2}} \\ \text{coord}(q, d) &= \frac{\# \{ i | 1 \leq i \leq n, q_i \in d \}}{\# q} \\ tf(q_i, d) &= \sqrt{\text{frequency}} = \sqrt{(\text{the number of } q_i \text{ in the document } d)} \\ idf(q_i) &= 1 + log \frac{\#D + 1}{\#\{ d \in D | q_i \in d \} + 1} \\ q_i\text{.getBoost()} &= \text{boost value of } q_i \\ \text{norm}(q_i, d) &= \frac1{\sqrt{\#d+1}} \times \text{boost value (index time boosting)} \end{align}

です。 *2 （ただし、 \# A は、集合 A の要素の個数です。）

いやー、これ見せられても全然わからないですよねｗ

安心してください。以下で、それぞれがどういう意味で、どういう役割を担っているのかを説明していきます。 基本的に全て、検索結果がいい感じになるような工夫として追加されています。 気持ちさえ分かれば怖くない！　と思います。

queryNorm と tf-idf - \text{queryNorm}(q) \times \sum_i tf(q_i, d) \times idf(q_i) ^ 2

これは、次のように書き直すと見通しが良いです。

\frac1{\sqrt{\sum_i idf(q_i)^2}} \times \sum_i idf(q_i) \times \bigg(tf(q_i, d) \times idf(q_i) \bigg)

まず、\bigg(tf(q_i, d) \times idf(q_i) \bigg) は tf-idf を表します。（若干定義違いますが）

\sum_i idf(q_i) \times \dots で、tf-idf を、さらに idf で重みづけて足しています。 idf は、その単語のレア度を表す数値なので、レア単語が含まれている場合、そのポイントを多めに加点しようという発想です。 確かに、「青い鳥とは」という検索をしていて、「とは」が含まれているかどうかより、「鳥」が含まれているかどうかのほうが大事ですよね。 そういう気持ちを数式に反映したものです。

先頭の \frac{1}{\sqrt{\sum_i idf(q_i) ^ 2}} は、 query normalization で、正規化のために入っています。 例えば、検索クエリが長くなると、足されるものの数が多くなり、強制的にスコアの値が大きくなります。 また、 idf が大きい単語ばかりを検索した場合、またスコアが大きくなります。 この様に、Σより右側は、クエリによって大きく値が変わってしまいます。 その差を補正するために、 idf の2乗の和のルートで割り算しているのです。

これによって、クエリが異なる場合でのマッチ度の比較が可能になります。 *3

boost - q_i\text{.getBoost()}

これは、検索のスコアをブーストするパラメタで、エンジニアさんが自由に設定できるものです。

例えば、検索クエリの単語が、文章の本文に含まれている場合と、文章のタイトルに含まれている場合は、なんか重さが違いますよね。 というわけで、

「件名に『鳥』を含む」 OR 「本文に『青い』を含む」という検索をする場合に、

  • 「件名に『鳥』を含む」のスコアを2倍（これが boost 値。「鳥」.getBoost() = 2）
  • 「本文に『青い』を含む」のスコアを1倍（「青い」.getBoost() = 1。）
  • 上記2つのスコアを足して最終スコアにする

という感じに適用できます。

ま、一言でいうと、検索のスコアをブースト（大きくする）ためのパラメタです。

normalization - \text{norm}(q_i, d)

これは、第2の normalization （正規化）項です。 \text{norm}(q_i, d) = \frac1{\sqrt{\#d+1}} \times \text{boost value (index time boosting)} であると定義しました。

ここには、第2の boost 項が入っているのですが、 Elasticsearch では、こちらの boost は利用非推奨です。 （詳細は https://www.elastic.co/guide/en/elasticsearch/guide/current/practical-scoring-function.html#index-boost ） *4

なので、\text{norm}(q_i, d) = \frac1{\sqrt{\#d+1}} と理解いただいていいかと思います。

tf と norm

tf が、いわゆる term frequency とは異なり、 \sqrt{\text{frequency}} でした。 ちょっと気持ち悪い定義に感じます、、、。

ですが、この norm とあわせると、

tf(q_i, d) \times \text{norm}(q_i, d) = \sqrt{\frac{\text{frequency}}{\# d+ 1}} \simeq \sqrt{\frac{\text{frequency}}{\# d}} = \sqrt{\text{普通の} tf}

となります。

まだ√が残りますが、この計算を見ると、 tf x norm で普通の tf っぽいものであると理解して良いのではないかと思います。

coordination factor - \text{coord}(q, d)

これは一番簡単です。 \text{coord}(q, d) = \frac{\# \{ i | 1 \leq i \leq n, q_i \in d \}}{\# q} です。 ちょっと数式の見た目はやばいですが、要は、分子は、「 q _ 1 〜 q _ n のうち、じっさいに d に登場するもの」で、分母は n です。

たとえば、「青い鳥とは」と検索した時に、文章 d に、「青い」「鳥」が出てくるけど「とは」は出てこない場合、 \text{coord} = \frac23 です。

要は、クエリの単語のうちどの割合でじっさいに含まれたかを加味して、全部が含まれていない場合のスコアを減点している項です。

まとめ

というわけでまとめましょう。 Elasticsearch に使われる Lucene's Practical Scoring Function は、

\begin{align} score(q, d) &= \text{queryNorm}(q) \times \text{coord}(q, d) \\ & \, \, \, \, \times \sum_i \left( tf(q_i, d) \times idf(q_i)^2 \times q_i\text{.getBoost()} \times \text{norm}(q_i, d) \right)\\ &= \text{coord}(q, d) \times \frac1{\sqrt{\sum_i idf(q_i)^2}} \times \sum_i idf(q_i) \times \left( \sqrt{\frac{\text{frequency}}{\#d + 1}} \times idf(q_i) \right) \times \text{boost} \end{align}

と見ると見通しが良くて、

  • \text{coord}(q, d) : q の単語のうち文章 d に出てくるものの割合
  • \frac{1}{\sqrt{\sum_i idf(q_i) ^ 2}} \times \sum_i idf(q_i) \times \dots : idf による重み付き和とその正規化
  • \sqrt{\frac{\text{frequency}}{\#d + 1}} \times idf(q_i) : tf-idf
  • \text{boost} : boost の値

という感じの意味であります。

基本的には、 tf-idf に idf の重みをつけて足したもので、更に coord と boost を加えて、いい感じの検索結果になるように工夫されたものです。

よくわかんなかったらこの動画を見てください。 話を聞くスタイルだと、なんか分かったりもすると思います。


【自然言語処理】Elasticsearch 徹底解説 - スコアリングのロジックについて【Elasticsearch への道③】#086 #VRアカデミア

おわりに

見た目がえげつない & あらゆる解説サイトの解説が誤っているというこの2つがあって、理解がむずかしい Lucene's Practical Scoring Function ですが、結構仲良くなっていただけたのではないかと思います。

もしよければこの動画たちも見てね！

チャンネル登録もよろしくお願いします！

あ、マスターの会社こと Atrae さん、採用やってるってよ！ 興味がある人は是非！

株式会社 アトラエの採用/求人 | 転職サイトGreen(グリーン)

株式会社アトラエ - 採用ページ| Atrae, Inc.

*1:ミスをご指摘いただいたp進大好きbotさんありがとうございました。

*2:バージョンによって微妙に定義が違います。 idf は普通の定義は log \frac{\#D}{\#\{ d \in D | q_i \in d \}} ですが、 Lucene's PSF のオフィシャルでは上記の定義で、 Elasticsearch では1 + log \frac{\#D + 1}{\#\{ d \in D | q_i \in d \} + 1}です。

*3:ここに関して、全く逆のことが書いてある記事が、日本語英語共にあります。やばい、、、！

*4:なんか、 index-time boosting は、DB に更新があるたびに boost 値の再計算が必要で、パフォーマンスに悪影響があるからだめらしいです。ここはあんまり詳しく走りません。誤ってたら教えて下さい