はじめに

検索基盤グループの加藤です。

ビズリーチプロダクトでは2年ほど前に検索機能に関する開発や改善を行うチームが組成されました。 最初はプラットフォームの検索APIリプレイスから始め、現在はサービス内の検索結果ランキング（並び順）の継続的な改善に取り組み始めています。

検索結果のランキングを改善するためには、その効果を正確に評価できる仕組みが不可欠です。 しかし、これまでのところ評価の仕組みが不足していて、改善の効果を客観的に測定することが難しい状況にありました。 そのためランキング改善を進めるにあたって、まず評価のための仕組みを整備することからはじめました。

今回はその取り組みの中でもABテストでInterleavingを導入した際の話をします。
Interleavingは評価手法として便利なシステムですが、どんな状況でも安易に導入するものではありません。 実装にあたっても検討すべきことがいくつかあります。

この記事では、我々がどういう課題を解決するために、どういう意思決定のもとInterleaving導入に至ったのか、また、実装するにあたってどういう工夫をしたのか、導入までの過程を紹介します。 Interleavingの詳しいアルゴリズムや評価方法については触れません。

Interleavingとは

Interleavingとは、検索結果のリストを生成する際に、複数のランキングアルゴリズムの結果を交互に組み合わせて表示する手法です。

alt text
Interleavingの仕組み

といったメリットがあります。 とてもよさそうな手法ですが、以下のようなデメリットもあります。

直面していた課題

評価を始めた当初はABテストの仕組みがなかったため、施策評価をリリース前後(たとえばリリース前2週間とリリース後の2週間)の比較で行っていました。 しかしこの方法には問題があり、正確な比較が難しい上に、評価のための前処置や分析に時間がかかり、改善サイクルが早く回せない状況が続いていました。

この状況の改善のため、実験的にABテストも導入してみました。 データのランダムな変動・外部要因の影響・グループに分ける際に正しくランダム化が行われているかを確認するために、2つのグループに同じロジックを使うAAテストも実施しましたが、同じロジックを使った場合でも結果が大きく異なる問題が発生し、うまくいったとはいえない状況でした。

これらの原因は、サービスでのお客様の検索行動に起因していました。 分析を進める上で、施策評価においては以下のような課題があることが分かりました。

我々が提供している検索機能は、企業様が採用候補者様を探す際に利用されます。 採用活動として、検索画面で採用候補者様を検索した後に、スカウトメッセージを送ることができます。

この検索機能のユーザーは各企業の採用担当者様であり、基本的に業務時間に利用されます。 そのため、祝日が何日あるか、月初か月末か、期初や期末か、といった時期的な要因によって、採用活動にかける時間も変わるため、検索条件およびその後の行動が大きく変わります。

また、採用活動自体に起因する要因もあります。 例えば、エンジニアを2人採用したい場合、同じユーザーが「エンジニア」というクエリで検索しても、採用開始初期で採用候補者様がまだ存在しない時期か、数名の選考が進んでいるが採用に至っていない状況か、1人の採用が決まりもう1人採用したい状況かによって、スカウトを送るかどうかが変わります。 採用活動は日々状況が変わるため、2週間や1ヶ月単位で比較する場合、ユーザーであるお客様の採用状況は全く異なります。

このような、時期による影響とお客様の採用活動の状況による影響が重なることで、リリース前後の比較や偏りのないグループ分けが難しくなっていました。

我々の状況としては、既にKPIを集計する仕組みはあるものの、上述の課題により新旧検索ロジックの比較評価が難しく、改善サイクルを迅速に回せない状態でした。 そのため、改善サイクルを早く回すために、新旧ロジックの良し悪しを効率的に判断できる仕組みが求められていました。 この点において、Interleavingの導入はデメリットよりメリットが大きいと判断しました。

実現方法

アルゴリズムの選択

Interleavingには複数のアルゴリズムがありますが、我々はBalanced Interleavingを採用しました。 この手法では、2つの異なるランキングアルゴリズムの結果を交互に並べます。

Balanced Interleavingには、ランキングAとBが類似する場合に、ユーザーがランダムに検索結果をクリックしてもどちらか一方が優れている結果が得られることがあると指摘されています。 しかし、今回対象とする検索画面は企業様が採用候補者様を検索する画面であり、我々が追っているKPIは検索結果の採用候補者様のクリック数ではなく、採用候補者様をクリックした後のメッセージの送信数でした。

メッセージの送信には1通あたりの費用がかかるため、ランダムに送信される可能性はクリックよりも少ないです。 メッセージを大量に送るケースもありうるのですが、そういった検索行動は特殊なため評価対象から除外しています。 以上のことから、ランダムにアクションを起こすことによるバイアスの影響は小さくなると判断しました。

また、Balanced Interleavingはシンプルなアイディアであり、実装やテストがしやすい利点もあります。 初めての取り組みであることから、まずは最もシンプルなものから始め、今後の改善を図ることにしました。

アーキテクチャ

我々の検索システムは、クライアントからのリクエストを受け取り、Elasticsearchにクエリを投げて検索結果を取得する仕組みになっています。

alt text
アーキテクチャ

このアーキテクチャでInterleavingを実現するためには、1度のリクエストで2つのクエリを作成し、同時にElasticsearchにリクエストする必要があります。 したがって、Interleavingを行うと、単純に検索エンジンへのリクエスト数が倍になります。

一般的にInterleavingを導入する際には、システムの負荷やパフォーマンスを慎重に考慮する必要があります。

もともと弊社のElasticsearchクラスタは様々な要因で負荷が高い状況でした。 しかし、負荷問題を解決する目処が立ちパフォーマンス面での懸念がなくなったため、Interleavingの実施する選択をすることができました。

実装

Interleavingを実現するにあたり、実装上頭を悩ませたのがページングの問題でした。 Interleavingを導入する際には、ページングの問題に対しても慎重に設計し、ユーザー体験を損なわないようにすることが重要です。

我々のサービスでは、1ページあたり100件を表示し、ページネーションありの検索画面になっています。 2ページ目以降の検索リクエストをどのように処理するかが論点で、以下2つをどうするか決める必要がありました。

2ページ目以降のInterleavingも実施するのか

もし2ページ目以降もInterleavingを実施するとなると、アイテムの管理が複雑になります。 我々が今回Interleavingを導入する目的はランキングの改善であり、特に上位の結果が重要です。

以上のことから、2ページ目以降を評価することはないと判断し、1ページ目だけで新ロジックと旧ロジックを混ぜたInterleavingを実施することにしました。 2ページ目以降の検索では旧ロジックのみを利用するようにしています。

1ページ目のInterleavingの結果を2ページ目以降の検索でどうやって反映するか

2ページ目以降の検索では旧ロジックを利用すると述べましたが、単純に2ページ目に移行すると、Interleavingで旧ロジックから採用されなかったアイテムが2ページ目以降にも表示されない問題が生じます。 また、Interleavingで新ロジックから採用されたアイテムが旧ロジックの2ページ目に表示される可能性もあります。

alt text
paging課題

これらの問題を解決するために、以下の仕組みを採用しました。

このキャッシュ時間は1時間としました。 この設定は、我々の検索の利用方法に基づいています。

お客様は採用候補者様を探すために一度行った検索結果を吟味することが多く、キャッシュ時間が短すぎると再度検索する際にキャッシュが効かない可能性があるためです。 このキャッシュ時間はサービスの特性に応じて調整することが重要です。

ログの設計

Interleavingでの評価のためには、Interleavingの入力と出力をログに残す必要があります。

具体的には最低限以下の情報が必要です。

我々は追加で以下の情報を残すようにしました。

これらの情報を残すため、以下のようなログ設計を行いました。 Interleavingに関わるところだけを抜粋してkey名は一部改変しています。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

{
    "searchId": "検索ごとのid",
    "algorithm": "Balanced Interleaving",
    "inputs": {
        "rankingA": [
            {
                "doc_id": "1",
                "logic_id": "A",
                "rank": 1
            },
            {
                "doc_id": "3",
                "logic_id": "A",
                "rank": 2
            }
        ],
        "rankingB": [
            {
                "doc_id": "2",
                "logic_id": "B",
                "rank": 1
            },
            {
                "doc_id": "4",
                "logic_id": "B",
                "rank": 2
            }
        ]
    },
    "outputs": [
        {
            "doc_id": "1",
            "logic_id": "A",
            "rank": 1
        },
        {
            "doc_id": "2",
            "logic_id": "B",
            "rank": 1
        },{
            "doc_id": "3",
            "logic_id": "A",
            "rank": 2
        },
        {
            "doc_id": "4",
            "logic_id": "B",
            "rank": 2
        }
    ]
}

また、KPI評価のために以下のような検索結果のログも残しています。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

{
    "searchId": "検索ごとのid",
    "results": [
        {
            "doc_id": "1",
            "rank": 1,
            "clicked": true,
            "sent": true,
        },
        {
            "doc_id": "2",
            "rank": 1,
            "clicked": true,
            "sent": false,
        }
    ]
}

最後に

Interleavingを導入したことで、検索結果のランキング評価を効率的に行えるようになりました。 その結果、改善サイクルも短くなり、検索結果の質向上とKPIの改善に寄与しています。

しかし、まだ改善の余地は残されています。

今回Interleavingの導入に伴い、既存の設計を大きく変更しました。 Interleavingの実施と検索処理を分離し、複数の検索処理を管理しやすくするよう努めましたが、ページング処理などで依然として複雑さが残っています。

また、Balanced Interleavingでは偏りが発生することから、Team Draft Interleavingなどの別のアルゴリズムの採用も検討したいと考えています。 さらに、評価の自動化やオフラインテストとの連携強化にも取り組んでいきたいです。

今後は、検索品質の改善だけでなく、精度評価にも一層注力して、継続的な改善を進めていきたいと考えています。

ryo kato
ryo kato

検索エンジニアを目指しています。