Elasticsearchのスコアリングを眺めてみる

前置き

この記事は Retty Advent Calendar 23日目です。
昨日は@kazushikawamuraのReact & Firebaseで簡単なChatアプリを作ってみたでした。

Elasticsearchとは

今更なにを。。。と思う方がほとんどだと思います。
釈迦に説法で非常に恐縮ですが、5.1.1も出たところですし一回お浚いということで。。。

Elasticsearchは、Elastic社が展開する強力な検索エンジン？です。
正直なんて定義できるものかよく分からないですが、全文検索でよく使う、あとデータ分析にめっちゃ強いというところでいろんなところで重宝してます。
この前行ってたelastic{on}では、ある発表でElasticsearchのいいところを
「貯める、検索する、集計する」が一つのプロダクトで出来る
というのをあげていました。
強力なビジュアライズツールKibanaを加えることで、分析結果のビジュアライズも簡単にできますし、LogstashやBeatsのようなデータ収集ツールを使って簡単にデータ貯めることもできます。

多機能にも関わらず、
スキーマレスにデータを格納できることや、
ダウンタイムなく簡単に出来るスケーリング、
強力なRESTAPI、
充実したドキュメントや世界にも使い手が多く事例も豊富な
素晴らしいプロダクトです。そして基本無料！

今回はそのElasticsearchの中でも、基本と言えるスコアリングの話をしようと思います。

簡単に用語とその説明

本格的にスコアリングの話をする前に、Elasticsearchで使われる用語を簡単にまとめておきます。（普通に自然言語処理の用語もあります）

• index
  • RDBSのデータベースに当たる。多くの場合、論理的な区切りとして使われる？
• type
  • RDBSのテーブルに当たる。こちらはRDBSのその概念と大きくずれることはないです。
• field
  • カラムです。データタイプの指定が可能です。
• document
  • レコードです。
• TF(Term Frequency)
  • 一つのDocumentの中で、該当単語の出現頻度を表します。
  • 公式
    • tf(t in d) = √frequency
    • tはtermで単語、dはdocumentです。
• DF(Document Frequency)
  • Document全体の中での該当単語の出現頻度です。頻度が少なければ特徴性は高くなりますね。
• IDF(Inverse Document Frequency)
  • DFの対数で、該当単語が特定Documentにおいて特徴とされる程度を　DFを使って表すために対数にします。
  • 公式
    • idf(t) = 1 + log ( numDocs / (DF + 1))
    • numDocsはDocument全体の数です。

簡単にこんな感じで、スコアリングの話をしてみます。

スコアリング

Elasticsearchは全文検索エンジンなので、投げられた検索語で「検索」してその結果を返すのが仕事です。
そのためには検索語に適合した項目を返すのですが、そのためには一定の基準があって、どれがもっと適合したやつか？を判断して返すことになります。

もっと簡単にいうと、
Googleで検索語入れて出てくる検索結果の順位をどう決めるのか
的な話ですね。もちろんそういう複雑なものではなく、もっと単純です。
だけど、
「似てる程度」「含有してる頻度」などでやってるわけでもないので、情報なく使おうとしたら結構戸惑うので、ここで説明するわけです。

ざっくり説明

以下の項目でスコアリングされます。

• TF
• IDF
• fieldの長さ

つまり、
一つのDocumentに対して
一つの検索語を構成している単語が
どれだけ含有されているか
その単語はどれだけそのdocumentに対して特徴的なのか
を計算され、
検索対象のfieldの文字列の長さが短いのをもっと高く
評価する仕組みです。

思想的には
一つの文書の中で該当検索語がよくマッチしていて、しかもそれは他の文書ではあんまり見られない該当文書のユニークな検索語で、しかもそれが短い文書であれば、マッチ度は高いということになります。

どうやってるのか細かいところが知りたい方は下の細かい説明を読んでください。

細かい説明

参考してほしいページは
Theory Behind Relevance Scoring| Elasticsearch: The Definitive Guide 2.x| Elastic
Lucene’s Practical Scoring Function| Elasticsearch: The Definitive Guide 2.x| Elastic
Advanced text scoring in scripts| Elasticsearch Reference 5.1| Elastic
とかですね。

詳しく説明されてるので、実は上の読んで！と言いたいところですが、
そもそもそうなるとこの記事を読んでいただき理由がなくなるので。
ここは一回簡単に説明させていきたいと思います。

まずは公式から。

score(q,d)  =  
    queryNorm(q)  
  * coord(q,d)    
  * SUM (           
        tf(t in d)   
      , idf(t)²      
      , t.getBoost() 
      , norm(t,d)    
    ) (t in q)   

これがElasticsearchのスコアリングです。どっかでみたことある方はきっとLuceneを思い出すと思います。
ElasticsearchはLuceneベースなので、スコアリングもLuceneとそれになります。

上の内容を少し項目ごとに説明します。

• score
  • スコアリングの結果を表す数字。表示順を決める基準となる。
• queryNorm
  • Query Normalization Factorで、下記の数式で決まります。
    • queryNorm = 1 / √sumOfSquaredWeights
      • sumOfSquaredWeightsは、検索語を形態素解析した上で、その形態素でIDFを自乗した値の合計です。
  • 実際スコアリングで何か基準になるわけではなく、検索語毎に違う数字を持たせるためだと思ってください。なので、同じ検索語を同じdocument群に投げない限り、この数字はいつも変化して、スコアリングされた数字が異なることになります。
  • ということで、伝えたいのは一つの検索で出てきたスコアは、他の検索と比較しても全く意味を持たない、ということです。
• coord(Coordination Factor)
  • これは、検索語を構成する単語のマッチ数によって、documentに対してもっとスコアの差別化できるようにします。
  • 例えば、「野菜塩ラーメン」という検索語で、各単語を同じ1.5という重さをかけて検索を行う場合には
    • coordなし
      • 野菜がマッチするdoc：1.5
      • 野菜、塩がマッチするdoc：3.0
      • 野菜、塩、ラーメンがマッチするdoc：4.5
    • coordあり
      • 野菜がマッチするdoc：1.5 * 1 / 3 = 0.5
      • 野菜、塩がマッチするdoc：3.0 * 2 / 3 = 2.0
      • 野菜、塩、ラーメンがマッチするdoc：4.5 * 3 / 3 = 4.5
  • 上のように、もっと多くの検索語がマッチした場合を優遇する形の数値が出るようになります。
• 以下は検索語の単語がdocumentに対して全て計算され、足されます。
  • documentに対する検索語の各単語のTF
  • 検索語の各単語のIDFの自乗
  • 検索語の各単語のブースト値
    • ブーストは特定fieldに対しての重さの増加を意味します。
    • 基本、Indexを作成するときに指定しておくのですが、検索のたびに指定して重さを変えることもできます。ただし、その場合はパフォーマンスに悪影響をもたらすので、極力index作成時に指定することをElasticsearchの本家マニュアルからオススメされてます。
  • norm(field length norm)
    • fieldの文字列の長さで、重さを与えます。文字列が短ければ、重さは大きくなります。
    • その理由は、例えばタイトル的な短い文字列のfieldで該当単語の表出は大きな意味を持ちます。それを反映する数値ですね。
    • 公式
      • norm(d) = 1 / √numTerms

以上がまとまって、一つの検索語に対する一つのDocumentへのスコアが決まります。
同じ検索語で対象になる全Documentに対して評価が行われるので、Documentのスコアが決まり、そのスコアで表示順が決まる、ということですね。

私は検索エンジンや自然言語処理に詳しくはないですが、上記の内容から検索語に対して価値のある内容を持っている文書を優先的に出してくれそうなイメージは湧きました。

この詳細のところはあんまり理解しなくてもいいかもしれませんが、スコアリングの調整とか行う際には理解しておいた方が良いでしょう。
例えば、function_scoreのようにスコアリングをゴリゴリいじれるところで使える

• _index['FIELD'].docCount()
• _index['FIELD'].sumttf()
• _index['FIELD']['TERM'].df()

のような関数を使って、その結果がどういうものでどういう影響をするのかを理解していればやれることは増えてくると思います。
一旦パフォーマンスの話はしないことにします

終わりに

書いてみれば結構長くなりました。
それもそうで、上にはあえて言ってないところもあります。

• indexではなくshard毎に計算されるとか
• explainAPIというのがあって、各項目がいくつで評価されたかわかるとか
• function_scoreというスコアゴリゴリいじれる奴があるとか
• Vector Space Modelという、検索語を構成する単語毎の重さを差別に付与して精度をあげるところとか

掘ろうとすれば掘るところがまだまだあります。気が遠くなりますよね。
私も何回か挫けてます。が、やっぱ必要だし面白くなってきます。
微調整で検索結果を変えて、それでユーザ体験をよくするというところは、ゲームのパラメータ設定にも似てると思うところもあって、そういうロジックを考えるのが好きな人にはたまらないところだと思います。

とはいえ、実際サービスで使うこととなると、これぐらいの演算をさせるためのマシーンリソースやこのスコアリングの部分を理解して設計可能なヒューマンリソースなどがボトルネックになったりもするので、そういうところをいかに解決できるかも課題だったりします。

それでも大好きなElasticsearchを使う人が増えることを願いながら、今回の記事はここまでとします。

ここまで読んでいただきありがとうございました！