検索のランキング計算、インデックス作成時にするかクエリ実行時にするか

これは何？

検索のランキングスコア（並び順）を計算するときに、計算時間のかかる複雑な処理はオンライン処理（リアルタイム処理）ではなく、オフライン処理（バッチ処理）に寄せます。この分岐が自明ではないので、その感覚を伝えるために、実際のランキングアルゴリズムを題材に、「こっちはオフライン処理だよね」を書き下してみました。

なお、検索結果を再度並び替えるリランクは想定していません。こちらは上位N件に絞った後なので複雑な処理（深い決定木とかニューラルネットワークとか）が比較的適用しやすいです。

背景

ChatGPTによる検索改善の考察 という記事を書いたところ、「ChatGPTの応答を挟むとレスポンスタイムが悪くなりすぎるのでは？それは検索APIとして致命的では？」というもっともな指摘を脳内の友人から受けたので、「いやいやインデックス生成時に計算すればバッチ処理でいけるっしょ？」と脳内に返したら、「インデックス生成時ってどれだよ」と再度ツッコミを受けたので、クエリ実行時（オンライン処理）とインデックス生成時（オフライン処理）について記事を書いてみます。

なお、前回の記事の内容の多くはクエリ実行時のものであるので、あれをプロダクションに適用しようとしたらだいぶ工夫が必要であることを、この場を借りて謝罪します。(ChatGPTが独立したWebアプリなのでレイテンシがかかる。もし検索エンジンの内部実装に組み込めたらその限りではない、かも)

さすがやで。。。
とはいえ、具体例がないとわかりにくいと思うので、具体例をもとに語ります。

今回の具体例

嘘が本当かはわからないが、実際の検索エンジンのランキングアルゴリズムが流出したらしく、中身をみたらだいぶそれっぽいので、こちらを題材にします。

こんな感じ

Name: "web_production"

Factor {
    Index:              0
    CppName:            "FI_PAGE_RANK"
    Name:               "PR"
    Wiki:               "https://wiki.yandex-team.ru/jandekspoisk/kachestvopoiska/factordev/web/factors/PageRank"
    AntiSeoUpperBound:  1.0
    Tags:               [TG_DOC, TG_LINK_GRAPH, TG_STATIC, TG_L2, TG_UNUSED]
    Description:        "Page rank. Фактор ремапится."
    Authors:            "aavdonkin"
    Responsibles:       "aavdonkin"
}

Factor {
    Index:              1
    CppName:            "FI_TEXT_RELEV"
    Name:               "TR"
    AntiSeoUpperBound:  0.95
    Group:              "LegacyTR"
    Tags:               [TG_DOC, TG_DOC_TEXT, TG_DYNAMIC, TG_REARR_USE, TG_UNDOCUMENTED, TG_NN_OVER_FEATURES_USE]
    Description:        "Текстовая релевантность (maxfreq – частота самого частого слова, которая имеет смысл длины документа)."
    Authors:            ["gulin", "iseg", "leo", "maslov"]
    Responsibles:       ["gulin", "leo", "maslov"]
}

これらのFactorを結合（線形和が使われがち。情報検索 :検索エンジンの実装と評価 - 森北出版の用語だとバギング。PRMLでの用語と違って重み係数は一様ではない。）してランキングスコアを作り、それでソートする処理は間違いなくクエリ実行時に行われるでしょう。なぜなら後で見るようにFactorによってはクエリの内容に応じて値を変えるものが多く含まれるため、事前にアイテムごとにスコアを計算してそれで並び替えといった手法はとれないからです。

では、上から一つ一つみていきます

１　FI_PAGE_RANK

ページランクですね。Googleで有名なあれと同じようなものだとすると、(1)クエリに依存しないため事前に計算可能(2)計算コストが高いため、インデックス生成時にアイテムごとの値を計算し、クエリ実行時はその値を参照するだけ、でしょう。このパターンをここではインデックス作成時に計算とよぶことにします。

２　FI_TEXT_RELEV

おそらくクエリとアイテム中のテキストとの関連度です。Groupが"LegacyTR"とあるので、Tはたぶんtokenで、tokenがどのくらい含まれるか、でしょう、多分。tokenとはざっくりいえば文を形態素解析とかn-gramとかで分割して、大文字小文字とかシノニムとか効かせたやつです。これはクエリがないと計算できないのでインデックス時に実行不可能なため、クエリ実行時に計算してるでしょう。クエリ実行時の計算はレスポンスタイムの悪化やサーバスペックが要求されるなど嬉しくないことが多いので、基本的にはできるものならインデックス生成時に計算したいものです。ただし、下記で見る通り良い検索を作るためにはいかにクエリのいうことを聞くか（ユーザの検索需要をシステムに正確に反映するか）が非常に重要であるため、クエリ実行時に計算せざるを得ないです。ちなみに、世の検索エンジン（ElasticsearchとかSolrとか）はそのクエリ実行時の計算を柔軟に実装しやすいように作られています。

３　FI_LINK_RELEV

これは名前だけだとちょっとわからないです。本文中のテキストとではなくアイテムの被リンクとの関連度を計算していると想像して進めます。RELEVとついているのでクエリとの関連度を計算しているものだと想像します。Groupが"Dynamic"となっているので詳細は不明ですが、伝統的なtoken単位ではなく、Sentence BERTなどを使っているのかもしれません（以前、そちらも解説記事を書きました。もう実装は古くなりましたがご参考までに）。SBERTを使う場合、アイテム情報の埋め込み表現の計算はindex作成時で、クエリの埋め込み表現の計算はたぶんquery実行時（計算コストが高いため頻出単語だけindex生成時に計算してキャッシュしている可能性もある）、埋め込み表現同士の距離（cos類似度など）はクエリ実行時に計算しているでしょう。cos類似度のような計算は軽いのでクエリ実行時でできます。Elasticsearchだとdence_vectorというものがあり、そちらで実装できます。またクエリ実行時での埋め込み表現の計算はElandというもので簡単に実装できます。

４　FI_PAGE_RANK_BONUS

中身はよくわかりませんが、ページランクの亜種なのでしょう。インデックス生成時に計算している気がします。

５　FI_TEXT_RELEV_ALL_WORDS　FI_TEXT_RELEV_PHRASE　FI_LINK_RELEV_ALL_WORDS　FI_LINK_RELEV_PHRASE　FI_TEXT_RELEV_TITLE

この辺はクエリとアイテムのURLやテキストとの関連度を細かく変えたものでしょう。このように関連度を複数の仕方で計算し、後で合成するやり方は、各手法の弱点をいい感じに補完する風に動くので、よく使われます。これらの計算はクエリ実行時でしょう。

６　FI_NEWS　FI_CATALOG　FI_CATALOG

この辺は記事の種類を内部で判別して、それをスコアに反映させているのでしょう。インデックス生成時に計算できるはずなので、インデックス生成時に行ってる可能性が高いです。

ちょっと上から見ていくと終わりそうもないので（全部で1923個ある）、いくつか興味深いものを抜粋し、この記事を終わらせたいと思います。ここで解説されているものから抜粋します。

７　FI_LINK_AGE

これは最近被リンクされると有利のようです。Descriptionを翻訳（ロシア語だったのでDeepLを利用）すると

LRに貢献したリンクの平均年齢 LinkAge=Min(log(average link age)/7, 1), over 1 adopted 3 years.

とのこと。

年単位の集計で十分であればインデックス作成時にできそうです

８　FI_DOC_CREATE_MONTH　FI_DOC_UPDATE_MONTH

アイテムの鮮度を使っているように見えます。新鮮なアイテムの方を上位にする、はよくあるやつです。これの計算はいつクエリが実行されたかの情報が必要になるので、クエリ実行時だと思います（もし月単位でいいならインデックス生成時にもできるかもしれないですが）。ニュースサイトのような情報の鮮度が重要なサービスや、フリマアプリのような在庫が極端に少ないサービスだとここの要素は極めて重要です。

とここまで書いてみて、Descriptionを翻訳したら月単位ってありました。失礼しました。インデックス作成時に計算だと思います。

９　FI_QUERY_DOC_RANDOM

なんらかのランダム性でしょう、たぶん。
Descritptionを見ると（英語だ！やった！）"Random float in [0,1] by user request and document"とあるので、リクエスト単位でのランダムなようです。間違いなくクエリ実行時での計算でしょう。
ランキングアルゴリズムにランダム性をいれるモチベーションは

1. ユーザの再検索時に新しい結果を出す
2. 検索関連のログを機械学習の学習データに使うための揺らぎにする

などが考えられます。これはどの単位（ユーザ単位、セッション単位、時間単位）でランダムにしたいかで変わってきて、もし時間単位かつインデックス作成頻度よりも長くて良い場合はインデックス作成時に計算できますが、それ以外だとクエリ実行時ではないと実現性ないです（例えば潜在的なユーザの数分だけ事前にインデックス作成時に計算の実行は現実感がない。）

---

ちょっとキリがないので、あとは思いついたら追記していきます。

このように検索のランキングアルゴリズムは多くの要因（一つ一つは単純なもの）の集合で作られることが多いです。それぞれの要因に応じてクエリ実行時に計算するのかインデックス作成時に計算するかに分岐があり、それを適切に設計することが、ランキングアルゴリズムの良い実装には必要です。

さて、このようなFactorを大量に作るにはどうしたら良いでしょうか？GoogleではFactor（Signalと呼んでる）候補が挙がった場合、会議をしていたらしいのですが（https://www.youtube.com/watch?v=JtRJXnXgE-A）

システム的には

1. Factorの追加を行いやすい設計にしておく
2. Factor追加の影響を調査しやすいようA/Bテストの仕組みを整える

などが考えられます。A/Bテストの仕組みを整えるにはこの本がおすすめです（https://www.kadokawa.co.jp/product/302101000901/）

最後に

Q

もう少し具体的に教えていただけますか？具体例があると嬉しいです

A

Q

とある検索エンジンの内部では、ランキングアルゴリズムを構成する要素に「FI_LINK_RELEV」という名前がついたものがありました。これが何で具体的にどういう働きをするかについて、推測で良いので教えていただけませんか？

Q

とある検索エンジンの内部では、ランキングアルゴリズムを構成する要素に「FI_LINK_RELEV」という名前がついたものがありました。RELEVはおそらくですが、クエリとの関連度を指します。これが何で具体的にどういう働きをするかについて、推測で良いので教えていただけませんか？

あ、こっちのほうがそれっぽいかも！うーん、廃業！！！