【Elasticsearch】「童貞男子」から始まった検索ロジック改善
はじめに
こんにちは! テラーノベルでサーバーサイドを担当している@yuhasです。
テラーノベルには作品や作家さんの検索機能があり、ユーザーさんの読みたい作品や興味のある作家さんを提示できる検索機能は重要な機能の一つです。
直近でその検索まわりを一新し、Cloud RunでElasticsearchを運用し始めました。
(その話はこちらの記事に書いているのでよければご覧ください)
その中で意図しない検索結果が返ってくることがあり、検索ロジックの改善を行いました。
今回はその話についてできればと思います。
モチベーション
テラーノベルの検索には大きく分けて「作品検索」と「ユーザー検索」があります。
これはそれぞれ作品名とユーザー名に対して検索をしています。作品の中身やユーザーの自己紹介文は使われていません。
最初は標準に近い形で検索ロジックを構成していました。しかし、「童貞男子」という検索文字列で(検索文字列のマッチ度が高い順に返す)作品検索行ったとき、一番上に「童貞」という作品が来て、それよりいくつか下に「童貞男子と姉御女子」という作品が来ていました。
直感的にこうあってほしいというところでいくと、「童貞男子」と検索したら、「童貞男子と姉御女子」の方が「童貞」より上に来て欲しいなと思います。
ということで検索ロジックの調査・改善を行うことにしました。
今回は以下の流れで説明します。
- マッチ度がどのように計算されているか(Elasticsearchの一般的な話)
- 「童貞男子」で検索して「童貞」の方が「童貞男子と姉御女子」より上に来る理由
- どのように改善させたか
マッチ度がどのように計算されているか
まず、検索というシステムがどのように成り立っているかについて説明します。
検索には、大きく
- データを登録する
- データを検索する
の2つの操作があります。その概要を示した図が以下です。
データ登録においては、登録されるデータをanalyzerにかけてから保存します。
テラーノベルでは上図の通り、「縁結びの呪い」というワードを3種類のanalyzerにかけてから保存しています。
どういう検索をさせたいかに応じて、様々なanalyzerを選んで利用することになります。
analyzerによって、助詞(縁結び「の」呪い)が落とされたりなどの正規化も行われています。
データ検索においては、検索文字列をanalyzerにかけてから検索(マッチ度を確認)をします。
上図だと、「呪い」というワードを3種類のanalyzerにかけてから検索をしています。
それぞれの登録と検索で別々のanalyzerを使うこともできますが、同じものを使うことが一般的です。
「呪い」と検索するとそれがanalyzerを通して色々に分割されますが、そのうちの「呪い」や「ノロイ」などが、「縁結びの呪い」を analyzerを通して分割した結果である「呪い」や「ノロイ」に一致して、「縁結びの呪い」が検索結果として返ってくるわけです。
3種類のanalyzerを使っているのには理由があります。
1つ目の単語単位で分割するanalyzerの必要性は明らかだと思います。
2つ目の単語ごとの読み仮名で分割するanalyzerは、「ねこ」や「ネコ」で検索したら、「猫」や「猫にこばん」が返ってきてほしいという意図などがあります。
3つ目の文字単位で分割するanalyzerは、辞書に載っていない単語を扱う場合に必要になります。「呪い」などは辞書に載っている言葉になりますが、辞書に載っていない単語を使う場合は単語ごとに分割されている必要があります。(もしくはその辞書に載っていない単語を辞書登録するという方法もあります)。
ということでこの3つのanalyzerを使うわけですが、1つ目の単語単位で分割するanalyzerで作成したインデックスにマッチしたらマッチ度を高くする傾向にしていました。
マッチ度というのはElasticsearchではsimilarity
という言葉で表されています。
ElasticsearchではデフォルトでBM25(TF-IDF法)という方法でsimilarityを計算しています。
ある1つの検索対象(=「童貞男子と姉御女子」)に対する検索文字列(=「童貞男子」)を与えた時のsimilarityは以下のように表せます。
ここで
-
は検索文字列をanalyzerによって加工した文字列の集合W -
は集合w の要素W -
はterm frequencyの略で、1つの検索対象における{tf}(w) の頻度w - 「猫猫犬」に対して「猫」と検索するのと、「猫犬」に対して「猫」と検索するのは、前者の方がsimilarityが高くなるということ。前者は全体の2/3が猫だが、後者は全体の1/2が猫なので、前者の方がこの値は大きくなる。
-
はinverse document frequencyの略で、全体における対象の{idf}(w) の頻度の逆数w - データ全体で「猫」「猫犬」「猫猫」という3つのデータだけのとき、「犬猫」と検索すると、「犬」の方がデータ全体で頻度が少ないので、より価値が高いと評価されて、「犬」をもつ「猫犬」のsimilarityが最も高くなるということ
- 助詞などの実質的な意味をもたないものは省いた上で計算されます
を表します。
「童貞男子」で検索して「童貞」の方が「童貞男子と姉御女子」より上に来る理由
「童貞男子」で検索したのに「童貞」の方が「童貞男子と姉御女子」より上位にきた理由を探ってみましょう。
まずは「童貞男子」「童貞」「童貞男子と姉御女子」の3つがanalyzerによってどのように分割されるかを確認してみましょう。
これにはAnalyze APIを使うことで確認できます。「文字列」と「対象のanalyzer」を渡すことで、どのように分割されるかが返されます。
それぞれのanalyzerにかけると、以下のように分割されることがわかりました。
- 「童貞男子」
- 「童貞」「男子」
- 「ド」「ドウ」「ドウテ」「ドウテイ」「ダ」「ダン」「ダンシ」
- 「童」「貞」「男」「子」
- 「童貞」
- 「童貞」
- 「ド」「ドウ」「ドウテ」「ドウテイ」
- 「童」「貞」
- 「童貞男子と姉御女子」
- 「童貞」「男子」「姉御」「女子」
- 「ド」「ドウ」「ドウテ」「ドウテイ」「ダ」「ダン」「ダンシ」「ア」「アネ」「アネゴ」「ジョ」「ジョシ」
- 「童」「貞」「男」「子」「姉」「御」「女」「子」
そしてExplain APIを使うと、これをもとにどのようにsimilarityが計算されているのかを確認できます。
1つ目のanalyzerに対するsimilarityを高くするように設定していたので、その値が支配的になります。なので、1つ目のanalyzerに関してのみ見ていきます。
Explain APIでも同じような説明を得られますが、先ほどのsimilarityの公式に当てはめると、
- 「童貞男子」と検索したときの「童貞」に対するsimilarityは・・・
tf(童貞 of 童貞) \times idf(童貞)
- 「童貞男子」と検索したときの「童貞男子と姉御女子」に対するsimilarityは・・・
tf(童貞 of 童貞男子と姉御女子) \times idf(童貞) + tf(男子 of 童貞男子と姉御女子) \times idf(男子)
となります。
ここで
-
は、童貞の中の童貞は完全に一致していて高い値になります。tf(童貞 of 童貞) -
は、「童貞」「男子」「姉御」「女子」の中の「童貞」なので頻度は小さく低い値になります。tf(童貞 of 童貞男子と姉御女子) も同様です。tf(男子 of 童貞男子と姉御女子) -
は、「童貞」という単語があまり使われない希少な単語であることから高い値になります。idf(童貞) はよく使われる単語であることから低い値になります。idf(男子)
以上をふまえると、「童貞」のsimilarityの方が「童貞男子と姉御女子」のsimilarityより高くなります。(より直感的にいえば、「童貞」という希少な単語が全体の多く(100%)を占めているためにsimilarityが高くなります)
どのように改善するか
結論からいうと、
もともとこのTF-IDF法の利用されるところは、(長文の)文書検索における利用のようでした。そのため、文書全体における検索文字列の頻度という要素が重要でした。しかし、作品名や作家さんのお名前を検索する際には、文字列が短いため、term frequencyを考えてしまうと直感に反するレベルで単語ごとの値が割り引かれてしまいました。なのでterm frequencyを無視する(定数にする)ことで解決することにしました。
以下は実際の設定の例です。similarityの計算方法を定義しておいて、それを各カラムで参照させることができます。
{
"settings": {
"analysis": {
...
},
"similarity": {
"scripted_idf": {
"type": "scripted",
"script": {
"source": "double idf = Math.log((field.docCount+1.0)/(term.docFreq+1.0)) + 1.0; return query.boost * idf;"
}
}
}
},
"mappings": {
"properties": {
"title": {
"type": "text",
"fields": {
"------": {
"type": "text",
"analyzer": "------",
"similarity": "scripted_idf"
},
"------": {
"type": "text",
"analyzer": "------",
"similarity": "scripted_idf"
}
},
"similarity": "scripted_idf"
},
...
}
}
}
これで、「童貞男子」で検索することで「童貞男子と姉御女子」が「童貞」よりも上に来るようになりました。
また、もう一つの方法として、「童貞男子」という言葉を1単語として認識させる方法もあると思います。そのような分割をしたanalyzerにおいては「童貞」はマッチしなくなります。しかし、そういった特別な単語を逐次追加していく運用の手間もあると考えて、いったん上記の方法をとりました。
まとめ
検索結果がどのような順番で返ってくるのかを知るためには、similarityがどのように計算されるのかを知る必要がありました。
そのためにAnalyze APIで文字列がどのように分割されるのかを知り、Explain APIでそれがどのようにsimilarityの計算に使われるのかを知ることが必要でした。
作品の名前やユーザー名の検索においては、対象の文字列が短いため、デフォルトのTF-IDF法はあまり適していない場合もあります。今回はTF(term frequency)を定数にすることで改善を行いました。
Discussion