サジェスト機能の改善を評価する社内ツールの紹介

ogp

はじめに

こんにちは。検索基盤部の倉澤です。

私たちは、ZOZOTOWNの検索機能の改善に取り組んでいます。ZOZOTOWNには、ユーザーが検索クエリを入力した際に、候補となるキーワードを表示するサジェスト機能があります。

search-suggest

今回はこのサジェスト機能の改善を効率的に評価する社内ツールを以下3点に焦点をあてて紹介します。

  1. 社内ツールの各機能
  2. 実務にて利用している場面
  3. 開発する際に採用したバックエンド技術

目次

背景

ZOZOTOWNでは、サジェストの検索エンジンとしてElasticsearchを採用しています。

Elasticsearchからサジェスト機能がデフォルトで提供されていますが、日本語との相性を考慮し通常の検索クエリを使用して実装しています。

日本語との相性が悪いためサジェスト機能の実装が難しい理由は、Elasticsearch公式ブログの記事で詳しく言及されています。

www.elastic.co

私たちは、検索クエリに対するサジェスト候補の表示順序のロジックや表記揺れの改善に取り組んでいます。

サジェスト機能の改善を繰り返していくうちに、以下のような要望が出てきました。

  • 新たなロジックで作成したサジェストのElasticsearchのインデックスと、既存のインデックスの検索結果にどのような変化があるのかを素早く確認したい

  • A/Bテストを実施する前にオフラインの定性評価を実施したい

本ツールはこれらの要望に答えるため作成したものです。

サジェスト評価ツールの機能

上記の背景を踏まえて作成したツールの機能を紹介します。

evaluator-tool

サジェスト候補の表示

入力として、比較したい2つのElasticsearchのインデックス名、検索クエリを受け取ります。

検索ボタンを押下すると、検索クエリに対応するサジェスト候補がスコアの高い順に10件表示されます。

Elasticsearchでのクエリとドキュメントのマッチングに用いるスコアは、デフォルトのBM25をベースとしたものではなく独自に定義したスコアを用いています。

具体的には、過去のサジェスト候補に対するクリック率やクリック後の商品購入率などを元に計算した重みを使用しています。

また、出力されたサジェスト候補の違いをわかりやすくするため各順位毎に同じキーワードであればグレーアウトしています。

評価

入力した検索クエリに対して、どちらのインデックスが適切な結果を返しているのかを評価する機能を実装しています。また、適切と判断した理由も記録できます。

複数人が同じ2つのインデックスを確認するケースがあります。他の人の評価を元にどちらのインデックスが適切かを総合的に判断したい場合があるため、こちらの評価機能を提供しています。

インデックスを評価するにあたりどのサジェスト候補が適切ではなかったのかを記録するため、各キーワードの横にチェックボックスを用意しています。

評価結果の集計表示

複数人が同一のインデックスを評価するケースがあるので、評価した結果を集計しリアルタイムで表示する機能を提供しています。どのようなクエリを実行しどちらのインデックスが適切であったのかを表示しています。

各インデックス名の列には評価者が検索したクエリ単位に適切だと評価した回数が記録されています。

また、どちらのインデックスも適切だと評価した場合は「both_ok」、どちらのインデックスも適切ではないと評価した場合は「both_ng」の値が記録されます。

これらの集計結果を表示させることで、どのクエリでどのような評価をしたのかを素早く確認できるようになりました。

evaluation_result

類似度算出

similarity

2つのインデックスから出力されたサジェスト候補を定量的に評価する機能として、類似度を算出し表示しています。

具体的には、「A Similarity Measure for Indefinite Rankings」(著:William Webber, Alistair Moffat and Justin Zobel)の論文で提案されている"Ranking-Biased Overlap(RBO)"という手法により類似度を算出しています。

この手法は類似度を0〜1の範囲で計算し、2つのリスト内の上位のキーワードが異なっていた場合に類似度を大きく減衰させるという特徴があります。

以下の理由からこちらの手法を採用しました。

  • ある検索クエリに対する2つのサジェスト候補のリストにどの程度の差があるのか知りたいという目的と合致している
  • インデックスに対して加えた改修の影響が大きいのか小さいのかが直感的に理解できる

Ranking-Biased Overlap(RBO)の実装は、changyaochen/rboのコードを参考にGo言語へ書き換えました。

package main

import (
    "fmt"
    "math"
)

type State struct {
    p              float64
    depth          int
    weight         float64
    agreement      float64
    AverageOverlap float64
    sRunning       map[string]struct{}
    tRunning       map[string]struct{}
}

func NewState(s0, t0 string, p float64) *State {
    if 0.0 >= p || p > 1.0 {
        panic("p must be between (0, 1)")
    }

    weight := 1.0
    agreement := 0.0
    averageOverlap := 0.0
    if p != 1.0 {
        weight = 1 - p
    }
    if s0 == t0 {
        agreement = 1.0
        averageOverlap = weight
    }
    return &State{
        p:              p,
        depth:          1,
        weight:         weight,
        agreement:      agreement,
        AverageOverlap: averageOverlap,
        sRunning:       make(map[string]struct{}),
        tRunning:       make(map[string]struct{}),
    }
}

func (s *State) Update(sd, td string) {
    overlap := 0
    if sd == td {
        overlap++
    }
    if _, ok := s.tRunning[sd]; ok {
        overlap++
    }
    if _, ok := s.sRunning[td]; ok {
        overlap++
    }
    s.agreement = 1.0 * ((s.agreement * (float64(s.depth))) + float64(overlap)) / (float64(s.depth) + 1.0)
    s.weight = (1 - s.p) * math.Pow(s.p, float64(s.depth))
    if s.p == 1.0 {
        s.AverageOverlap = (s.AverageOverlap*float64(s.depth) + s.agreement) / (float64(s.depth) + 1.0)
    } else {
        s.AverageOverlap = s.AverageOverlap + s.weight*s.agreement
    }
    s.sRunning[sd] = struct{}{}
    s.tRunning[td] = struct{}{}
    s.depth++
}

func (s *State) GetSimilarity() float64 {
    if 0.0 <= s.AverageOverlap && s.AverageOverlap <= 1.0 {
        return s.AverageOverlap
    }
    fmt.Println("Value out of [0, 1] bound, will bound it")
    return math.Min(1.0, math.Max(0.0, s.AverageOverlap))
}

func main() {
    // 類似度を算出する対象のランキングリスト
    s := []string{"a", "b", "c", "d"}
    t := []string{"a", "c", "b", "d"}

    state := NewState(s[0], t[0], 1.0)

    for i := 1; i < len(s); i++ {
        state.Update(s[i], t[i])
    }
    similarity := state.GetSimilarity()
    fmt.Printf("similarity: %g", similarity) // similarity: 0.875
}

利用ケース

私たちは、サジェスト機能の改善を検証するためA/Bテストを実施していますが、ユーザーへの影響をできるだけ事前に把握するためオフラインでの定性・定量評価を実施しています。

本ツールはA/Bテストを実施する前に行うオフラインの定性評価時に利用します。以下は、A/Bテストを実施するまでのステップを簡易的にまとめた図です。

usecase

定性評価は以下の順序で行っています。

  1. ランダムに抽出した検索回数が多いTOPクエリと少ないTAILクエリを評価者に割り振る
  2. 評価者は本ツールにて割り振られたクエリを実行する
  3. 出力されたサジェスト候補を元に2つのインデックスを評価する
  4. 全ての評価者からのフィードバックを元にA/Bテストへ進むのか、改善方針を見直すのかを判断する

評価者は開発前に策定した方針が適切に検索結果に現れているのか、またTOPクエリ及びTAILクエリに対する影響をチェックしています。

また、評価者の構成は基本的にチーム内のメンバーですが、過去には社内で評価者を募ったこともあります。

上図の改善サイクルの詳細や改善事例については過去の記事で紹介していますので、併せてご覧ください。

techblog.zozo.com

バックエンドの技術

バックエンドで採用している技術スタックやアーキテクチャを紹介します。

技術スタック

おおまかな技術スタックを以下の表にまとめました。

カテゴリー 名称
実行環境 Google App Engine
データベース Google Cloud Datastore
開発言語 Go言語
httpパッケージ net/http
routingパッケージ gorilla/mux
Elasticsearchクライアントパッケージ olivere/elastic

Go言語を採用した背景は、属人的な実装にならないようにシンプルな文法で記述でき、将来チーム内で開発する際にも実装のブレが少ない言語仕様だからです。

評価した検索クエリやインデックス名、サジェスト候補を格納するデータベースとしては、Google Cloud Datastoreを採用しています。

社内ツールということもあり、運用にかかるコストを下げるためやApp Engineとの相性の良さからGoogle Cloud Datastoreを採用しました。

architecture

アーキテクチャ

プロダクトの設計として、ヘキサゴナルアーキテクチャを採用しています。アダプター層、ユースケース層、ドメイン層で責務を分け、依存関係の方向を担保し実装をしています。

ディレクトリ構成は以下の通りです。

. app
├── adapter
│   ├── datastore
│   ├── elasticsearch
│   ├── http
│   │   ├── controller
│   │   └── middleware
│   └── impl
├── domain
│   ├── model
│   └── repository
└── usecase
ディレクトリ名 概要
adapter/http/controller いわゆるコントローラ層。ユーザーからのデータを受け取り、処理をしたデータをユーザーへ返す実装。
adapter/http/middleware リクエストログの取得などAPI共通機能を実装。
adapter/impl interfaceで定義したメソッドの実装。
adapter/elasticsearch elasticsearchへの接続処理を実装。
adapter/datastore datastoreへの接続処理を実装。
domain/model アプリケーションに必要な構造体を定義。
domain/repository 依存性逆転のためinterfaceを定義。
usecase ユーザーからのインプットを元にAPIレスポンスに必要な情報を返す実装。

まとめ

本ツールにより、以下2つの要望を実現しました。

  • 開発者が新規に作成したインデックスと既存のインデックスの検索結果を素早く比較する
  • A/Bテスト前のオフライン評価の実施

今後の展望として、Elasticsearchのマッピングやクエリを変えて比較できるような機能を実装したいと思っています。

さいごに、ZOZOでは検索エンジニア・MLエンジニアを募集しています。検索機能の改善に興味のある方は、以下のリンクからご応募ください。

hrmos.co hrmos.co

カテゴリー