Skip to content
blog.tatsuroh.com

Algoliaのランキングについて

Algolia

本記事は Algolia Advent calendar 二日目の記事になります。

こんにちは、Algolia サポートエンジニアの半田です。 12月に入り一段と寒さが厳しくなってきましたがいかがお過ごしでしょうか。

昨日の篠原さんの記事ではInstantSearch.jsを使って無料でAlgoliaの検索UIを試す方法を紹介してくれました。 アドベントカレンダー二日目に当たるこの記事では、Algoliaの検索エンジンの裏側の動き、中でも検索処理において重要なランキングについてご紹介してみたいと思います。 すでにAlgoliaをバリバリ使いこなしている方には当たり前の内容かと思いますが、これからAlgolia触り始める方やランキングについて深く知りたいという方に向けた内容として読んでいただけると幸いです。

検索エンジンとランキングアルゴリズム、Algoliaの場合

一般的に検索エンジンでのランキングというと、LuceneをベースとしたSolrやElasticsearchでのスコアリングを思い浮かべる方も多いのではないでしょうか。 Luceneベースの検索エンジンでは、検索処理の中で検索結果の取得とともに個々の文書に対するスコアを算出し、その値によって検索結果の順番が決定されます。 スコアの計算式としてはBM25あるいはTF-IDF といった文書の関連度を評価するアルゴリズムが用いられ、必要に応じてフィールドごとの重み付けやカスタムスコアリングを用いてチューニングをしていく形になるかと思います。 この方式では検索対象全体における単語の出現頻度など統計的な情報をスコアとして考慮できる一方、検索クエリの都度スコアの計算が必要となり、またカスタマイズが重なると結果の解釈が複雑になるケースがあります。

これに対し、Algoliaの検索エンジンではこうしたスコアリングは行わず タイブレーキング と呼ばれるランキング決定の方式を採用しています。 タイブレーキング方式では、検索結果の並び順は複数の優先順位付けされたルール群を検索結果の集合に対して適用することで決定されます。 これにより爆速の検索速度を維持しつつ、結果の解釈や調整が比較的行いやすい検索結果のランキングを実現しています。

といってもなかなか文字では伝わりにくい部分もあると思うので、こちらの解説ビデオで紹介されている例を参考に、どういう挙動をするものなのか実際に見ていきたいと思います。

タイブレーキングアルゴリズムの動き

ビデオの中では、以下の図に出てくる6つのブロックのランキングを例として説明しています。 この記事でも、これらをあるクエリに対する検索結果とした場合の実際にタイブレーキングを適用して並べ替えていく過程を考えてみます。

2B16856FC9FD4A1F4CDF4C3F59B562EF

タイブレーキングでは、優先順位されたルールの集合をあらかじめ設定します。 今回は以下の3つのルールに基づいて並び順が決定するよう構成されています。

  • ルール1: Colors(色) を基準に並べる = 青 > 赤 > 白
  • ルール2: Shapes(形)を基準に並べる = ■ > ●
  • ルール3: # Studs(突起の数)を基準に並べる = 多い順に並べる
B0ED6C330BFF02FB3E4B4F4B609C63EF

それでは実際にこの順番のルールを設定し、ブロックを並べ替えてみましょう。 まずはじめに適用されるルールは Colors(色) なので、これを基準に並び替えます。 すると、青いブロックが3個、赤いブロックが1個、白いブロックが2個の順に並べる(以下の図)ことができました。 しかし、青いブロック・白いブロックはそれぞれ複数あるため、同じ色のグループ内での順位が決まりません。 このようにルールによって順位が決まりきらない状態をタイ(tie / 同点・同着といった意味)と呼び、タイブレーキングではタイとなったアイテム同士については下位のルールを適用して改めて並び替えを試みます。

98EFF8512493C6AD130E526775803179

それでは次に、2番目のルールである Shapes(形) を適用して並び替えてみます。 このルールでは四角いものを丸いものよりも前に並び替えます。

このルールにより、青いブロックのグループは、四角いブロック2個と丸いブロック1個に並べ直すことができました。 しかし、四角いブロック同士は(どちらも青く四角いため)引き続きタイの状態です。 こうした場合、タイブレーキングのため更に下位のルールで並び替えを試みます。

4C99248E647691AA9645B384D18AE1D6

3番めのルールは # Studs(突起の数) です。 より多い突起のついたブロックが上位に来るため、8個の突起があるブロックが1位、4個の突起のあるブロックが2位と順番を確定させる事ができました。 3番目には青い丸型のブロック、4番目には赤いブロックがすでに上位のルールによって確定していますが、まだ白い図形については順位が確定していていないため、こちらも下位のルールで順位を試みます。

B43CC19F15035FC30D61D8A1AB7F56AF

白のグループは四角と丸のブロックが含まれるため、Shapes(形)ルールで順位を確定することができます。 白い四角が5番目、白い丸が6番目となりました。 これによりすべてのブロックの順位が確定となり、無事に検索結果を返すことができるようになります。

148F03E16ECF9EDBA7F4EDDAA379A153

タイブレーキングにおいては、適用するルールの順番も大変重要です。 試しに、Colors(色)Shapes(形) のルールを入れ替えて実際に並べてみると以下のようになります。

83A660C8517F761AE6FFCF42A98ED182

さっきの結果と並べて比べてみましょう。左では Colors(色) が最上位のルールであるため、最終的な結果にもこれが反映されていることがわかります。 また、右のルールでは Shapes(形) が最上位のルールであるため、最終的な結果もブロックの形がランキングにより大きい影響を及ぼしていることがわかります。 このように、ルールの組み合わせだけでなく順位も検索結果のランキングに大きく影響します。

07FB72E9F0608421C80AE2A66E785839

タイブレーキングの動作のまとめ

ということで、ブロックの色・形・突起の数を例にタイブレーキングアルゴリズムの動きを見てみました。 改めてその動きをまとめると以下のようになります。

  • (クエリにマッチする検索結果を取得する)
  • 一番優先順位の高いルールに沿って並び替える
  • もしタイ(同順位)のレコードがあれば、2番目のルールに従って並び替えを行う
  • すべての文書のタイがブレークされるまで(あるいはすべてのルールが適用し終わるまで)これを繰り返す

個々のランキングルールで行っている処理は比較的シンプルなため、チューニングを行う際にも検索結果への影響が比較的わかりやすい点が特徴として挙げられます。 例えば色の順位を変更したい場合、Colorsルールの順番を変更するだけで結果の再チューニングが可能です。

Algolia のデフォルトランキングストラテジー

それでは、実際の文書を検索するにあたってはどのようなタイブレーキングのルールを適用するのが良いのでしょうか。 Algoliaでインデックスを作ると、文書検索に最適化されたデフォルトのランキングストラテジーがあらかじめ設定された状態となります。

BB0CE721486A65AD8B67024075B167D3

このランキングストラテジーはデフォルトのまま、十分なテキスト的関連性によるランキングを実現できるように、複数のルールを組み合わせて設定されます。 具体的にデフォルトランキングルールに含まれるルールは以下のものです。

  • typo : タイポ(誤字)が少ない順に並べる
  • geo : 地理的な距離が近い順に並べる(緯度経度情報での検索時に有効)
  • words : マッチした単語数が多い順に並べる
  • filters : マッチしたフィルターが多い順に並べる(optionalFiltersとの組み合わせで有効)
  • proximity : マッチした単語同士の距離が近い順に並べる
  • attribute : クエリがマッチした attribute(属性)の優先順位に従って並べる
  • exact : (prefix 検索ではなく)完全一致するレコードを上位に並べる

Algolia では、これらのランキングルールについてはひとまず変更せずにご利用いただくことをおすすめしています。これらのルールはAlgoliaのこれまでの経験の蓄積に基づいたものであり、また、変更時の影響範囲が大きいためです。変更が必要な場合には A/B テストなども含めた十分なテストを実施することをおすすめします。

カスタムランキングの追加

上記に加え、Algoliaではカスタムランキングと呼ばれる、追加のランキング基準を設定することをおすすめしています。カスタムランキングはダッシュボード上から、対象となるアトリビュートを指定して追加することが可能です。

338599248799F2E29EBFCB90EF3E11AF

タイブレーキングの動作上、デフォルトのルールがすべて同じ場合(タイブが解消しなかった場合)には、インデックス内部のもともとの順番でそのまま検索結果が表示されることになりますが、これは実際には必ずしも意味のある順序になりません。 カスタムランキングは、こうした場合に「新しいものから並べる」あるいは「人気のあるものから並べる」といった「インデックスに含まれるレコードデータの意味」を踏まえて調整を効かせるためのルールを追加するものです。

例えば、電子書籍の販売サイトで「鬼滅の刃」というクエリで検索してみたとします。 すると、検索結果としては既刊の鬼滅の刃全22巻(今週にはいよいよ最終巻が出ますね!)を含む一覧が取得されます。 アイテムのタイトルはいずれも「鬼滅の刃」なので、テキストの関連性では差がつきません。 こうした場合、検索結果の上位に1巻が出てくるよりも最新の23巻や映画原作になった7巻・8巻が出てくるほうがエンドユーザーの検索体験が良くなる可能性があります。 言い換えれば、最終的な検索結果の色付けを行うための機能がカスタムランキングなのです。

データのソート

さて、ここまで見てきたデフォルトランキング+カスタムランキングで構成されたランキングルールでは、あくまでもクエリに対するテキスト関連性(textual relevance)を第一基準として検索結果を並べることになります。 これは、例えばショッピングサイトで検索した商品を「関連性の高い順に並べる」状態に相当するものです。 しかしユーザーの行動として検索結果を「新しい順」や「価格の安い順」にならべた状態で商品を閲覧したいケースもありますから、そのような並びの検索結果も確認できることが検索体験としては望ましいと考えられます。

Alogliaではこうした場合に対応するため、テキストの関連性に先立ってこれらの基準で検索結果をランキングとし、その後テキスト関連性を考慮するといったランキング構成とすることができます。 以下の図はダッシュボード上のイメージとなりますが、デフォルトランキングの上に赤色で囲われた 'SORT-BY' フィールドが割り当てられていることが確認できます。

ranking formula 6c0498d3

裏側の挙動としては、AlgoliaではこのSORT-BY属性を追加すると、あらかじめインデックス内のデータをこの属性の値でソートし、検索時にはその順番をベースにランキングルールを適用するといった動作をします。 このため、複数の並び順を用意する必要がある場合にはマスターとなるインデックスのレプリカを作成し、複製したインデックス上でランキング設定のみ変更するといった形で用意することになります。

上記に対するフロントエンド側の実装としては、例えばドロップダウンリストとしてこれらの並び順を選択できるようにするパターンが考えられます。選択項目に応じて検索クエリを投げるインデックスを張り替えることで、ドロップダウンで選択された並び順に応じた検索結果の取得処理が実行できます。

InstantSearch.jsはこうしたユースケースへの対応として sortBy widgetを提供しています。こちらを活用することで、ドロップダウンを迅速に実装することができます。

C4CFBEF6038C135A1217000DB6383A07

まとめ

ということで、Algolia をご利用いただく上で重要となるランキングについてまとめてみました。 タイブレーキングやカスタムランキング、データのソートなどをAlgoliaを使って検索機能を作る際に考慮いただきたいポイントを駆け足ながら概観することができたのではないかと思います。 なお、Algolia検索エンジンでは個々のランキングクライテリアに対し更に細かい動作を定義するパラメータが用意されており、これらを利用したチューニングも可能です。ご興味のある方はぜひAlgoliaのドキュメントを参照してみてください。

次回は本日の内容を踏まえ、実際にDashboardなどを活用してランキングストラテジーの情報を確認し、検索結果の改善につなげて行く方法をご紹介したいと思います。 どうぞお楽しみに!

参考文献

Algolia 公式ブログの記事でAlgoliaがどのようにランキングの問題に取り組んできたかを解説した記事です。

https://www.algolia.com/blog/how-algolia-tackled-the-relevance-problem-of-search-engines/

© 2020 by blog.tatsuroh.com. All rights reserved.
Theme by LekoArts