検索サジェストにおける多様性評価指標とゴール指標の相関について

はじめに

こんにちは、検索基盤部の広渡です。検索基盤部では、検索クエリのサジェスト（以下、サジェスト）の改善を行なっています。ここでサジェストは一般的に「Query Auto Completion」と呼ばれる、検索クエリを入力した際に入力の続きを補完したキーワードを提示する機能を指します。

ZOZOTOWNにおいては検索クエリを入力したとき、最大10件の検索クエリのサジェスト（以下、サジェストリスト）が表示されます（なお、ランキングを考慮しない場合はサジェスト集合と呼ぶこととします）。また、サジェストリストのランキングはユーザーの行動ログを用いて計算されたスコアによって決定されます。サジェストの具体的な説明や過去の改善事例は以下の記事を参照してください。

techblog.zozo.com

サジェストリストをチーム内で定性評価したところ、類似したサジェストが多く表示されることによる、多様性の乏しさを指摘する声が多くありました。多様性の乏しいサジェストリストの具体例は、「ゾゾ」「ZOZO」など表記揺れした同じ意味のサジェストや、「パンツ」「パンツレディース」など性別のみ加わっただけのサジェストを含むものです。このような多様性の乏しいサジェストリストは、ユーザーに価値のあるサジェストが含まれず、結果的にユーザーの入力文字数が増えてしまい、検索体験の質を下げてしまう可能性があるため重要な課題です。

本記事では、サジェスト集合の多様性度を計測するdiversityと、サジェストリストの多様性度を計測するD#-nDCGについて紹介し、それらの指標とゴール指標との相関についての検証結果を解説します。ゴール指標は後ほど詳しく説明しますが、CTR（Click Through Rate）とCVR（Conversion Rate）です。多様性評価指標とゴール指標の相関を調査する目的は、多様性評価指標がZOZOTOWNのサジェスト改善に有効かを調べるためです。有効な指標を用いて新規サジェスト手法を計測することで、実際のユーザーの反応を見る前に改善が見込めるかどうかを判断でき、改善サイクルの効率化につなげられます。

多様性評価指標

ここでは、ランキングを考慮しないサジェスト集合の多様性度を表す指標について紹介し、その後、多様性を考慮したランキング指標について紹介します。

サジェスト集合の多様性度を表す指標

まず、Ma, Hao et al, AAAI 2010¹で提案されたdiversityと呼ばれるサジェスト集合の多様性度を測る指標について紹介します。

入力クエリ $p \in P$ が与えられた際のサジェスト集合を $S_{\, p}$ とし、 $j$ 番目のサジェストを $q_{\,j}$ とします。サジェスト集合 $S_{\, p}$ に対する多様性度はMa, Hao et al, AAAI 2010の定義に従うと、以下のように定義されます。

diversity

ここで $K = |S_{\, p}|$ であり、 $D(q_{\,j}, q_{\,l})$ は $j$ 番目のサジェスト $q_{\,j}$ と $l$ 番目のサジェスト $q_{\,l}$ との距離を表します。

このサジェスト間の距離 $D(q_{\,j}, q_{\,l})$ として、様々な定義が提案されています。Ma, Hao et al, AAAI 2010では、サジェスト経由で表示されたWebページのうち、クリックされた各ページに関連する検索クエリの集合のコサイン類似度を用いています。Zhu, Xiaofei et al, WWW 2011²では、サジェストを経由して表示された上位10件のWebページのうち重複した割合で定義しています。

サジェスト間の距離が遠ければ遠いほど $SD(S_{\, p})$ の値が大きくなり、サジェスト集合は多様であると判断できます。

多様性を考慮したランキング指標

diversityではサジェスト間の距離をもとに多様性度を測定していましたが、ランキングは考慮されていませんでした。ここでは多様性を考慮したランキング指標である、α-nDCGとD#-nDCGについて紹介します。ここからの説明は情報アクセス評価方法論³を参考にしています。

α-nDCGとD#-nDCGは、サジェストリストがユーザーの多様な検索意図に適合するかを評価できるようにnDCG（normalized Discounted Cumulative Gain）を拡張したものです。ここでいう多様な検索意図とは、例えば"パンツ"を入力したユーザーはズボンを探している場合もあれば、下着を探している場合もあるなど、同一の検索クエリに対してユーザーの求める情報が異なることを指しています。

α-nDCG

本節では、Clarke, Charles L.A. et al, SIGIR 2008⁴で提案されているα-nDCGについて紹介します。α-nDCGは、すでに検索された意図の利得を減衰させる特徴があります。

まず、 $j$ 番目のサジェスト $q_{\,j}$ が $i$ 番目の意図 $n_{\, i}( i= \{ 1,\dots, m\})$ に適合するとき $J(q_{\,j}, n_{\,i})=1$ 、しないとき $J(q_{\,j}, n_{\,i})=0$ とします。

ここで、意図 $n_{\, i}$ に適合すると判断された $k-1$ 番目までのサジェストの個数を $\displaystyle r_{\,n_{\, i},\, k-1}=\sum_{j=1}^{k-1}J(q_{\,j}, n_{\, i})$ で表します。

このとき、 $k$ 番目までサジェストリストを評価するための指標α-DCG(Discounted Cumulative Gain)は以下のように表されます。

alpha-dcg

ここで $\alpha(0 \lt \alpha \leq 1)$ はパラメータであり、情報アクセス評価方法論によると通常0.5に設定されます。

そして理想的なランキングのα-DCGを求め、正規化したものがα-nDCGです。

α-nDCGによる評価は、Zhu, Xiaofei et al, WWW 2011, Cai, Fei et al, Foundations and Trends 2016⁵, Cai, Fei et al, ACM 2016⁶でも採用されています。

しかし、理論的には理想的なランキングを求める計算はNP完全であるとClarke, Charles L.A. et al, SIGIR 2008で述べられています。

D#-nDCG

α-nDCGにおけるNP完全を回避できる指標が、Sakai, Tetsuya et al, SIGIR 2011⁷で提案されているD#-nDCGです。

D#-nDCGはサジェストリストを評価するD-nDCGと、検索意図の再現性を評価する意図再現率I-recの2つの要素から構成されています。まず、D-nDCGについて説明します。

検索窓に入力されたキーワード $p$ に対する意図 $n_{\, i}$ の確率を意図確率 $Pr(n_{\, i} \mid p)$ とし、 $j$ 番目のサジェスト $q_{\,j}$ の意図 $n_{\, i}$ に対する利得を $g_{\, n_{\, i}, q_{\,j}}$ とします。意図確率 $Pr(n_{\, i} \mid p)$ のイメージとしては、"パンツ"が検索窓に入力されたとき、70パーセントがズボン、30パーセントが下着を意図しているといったものです。

このとき、 $k$ 番目までのサジェストリストを評価するための指標D-DCGは以下のように表されます。

d-dcg

この式の分子 $\displaystyle \sum_{i=1}^m \text{Pr}(n_{\, i} \mid p)g_{\, n_{\, i}, q_{\, j}}$ はグローバル利得と呼ばれます。

グローバル利得は、サジェスト $q_{\, j}$ が入力キーワード $p$ に適合する確率 $\displaystyle \text{Pr}(rel=1 \mid p, q_{\, j})=\sum_{i=1}^{m} \text{Pr}(n_{\, i} \mid p)Pr(rel=1 \mid n_{\, i}, q_{\, j})$ を近似したものです。

このグローバル利得によりソートすることで理想的なランキングを求め、正規化したものがD-nDCGです。

次に、Zhu, Xiaofei et al, WWW 2011で提案されている意図再現率I-recについて説明します。

まず、 $B_{\, n_{\, i}}(j)$ を、 $j$ 番目までのサジェストリストの中で意図 $n_{\, i}$ に適合したものがあれば1、なければ0を表す変数とします。先ほどの $J(q_{\, j}, n_{\, i})$ を用いると、 $\displaystyle B_{\, n_{\, i}}(k) = \min \left( \sum_{j=1}^k{J(q_{\, j}, n_{\, i})}, 1 \right)$ で表されます。

このとき、 $k$ 番目までのサジェストリストの意図再現率I-recは以下のように表されます。

i-rec

ここまでで求めたD-nDCGと意図再現率I-recを線形結合させたものがD#-nDCGであり、以下のように表されます。

d#-ndcg

$\gamma (0 \lt \gamma \lt 1)$ はパラメータであり0.5に設定されることが多いようです。

ゴール指標と多様性評価指標の相関

ここからは、上記で紹介した多様性評価指標であるdiversityとD#-nDCGが通常のnDCGと比べてゴール指標に相関するのか調査します。

ゴール指標であるCTR（Click Through Rate）とCVR（Conversion Rate）について説明します。CTRは（サジェストリストのクリック数/サジェストリストの表示数）で、CVRは（サジェストリストを経由して商品詳細に遷移した数/サジェストリストクリック数）としています。

α-nDCGではなくD#-nDCGを採用した理由は、先ほど説明にもある通りα-nDCGで生じるNP完全が回避できるためです。

本章では、各指標の計測方法を説明し、結果について述べます。

測定方法

まず、diversityの計測方法を説明します。

サジェスト間の距離 $D(q_{\,j}, q_{\,l})$ を計測するために、「サジェストを経由して遷移した商品の類似性」に着目しました。具体的な定義としては、遷移先商品の頻度をベクトル $v_{\, j}, v_{\, l}$ で表現し、そのコサイン類似度を用いました。

div-cos

次に、D#-nDCGの計測方法を説明します。

はじめに、入力キーワードの意図 $n_{\, i}$ を定義する必要があります。α-nDCGを採用していたCai, Fei et al, ACM 2016では、クエリを通じてクリックされたURLをODP(Open Directory Project)に基づき分類することで意図としていました。

ここから、ZOZOTOWNにおける商品URLも何らかの粒度で分類する必要がありました。クエリを通じてクリックされた商品URLをブランドとカテゴリーの組み合わせにより分類することで意図と定義しました。例えば、ユーザーがブランド「Hoge」のスニーカー商品をクリックするとURLはbrand/hoge/shoes/sneakers/になります。このURLからユーザーの検索意図は「Hoge　スニーカー」と分類し定義しました。

この定義に基づき、意図確率 $\text{Pr}(n_{\, i}\mid p)$ は、検索窓に文字列 $p$ を入力した後に検索された意図を集計することにより求めました。また、 $j$ 番目のサジェスト $q_{\,j}$ の意図 $n_{\, i}$ に対する利得 $g_{\, n_{\, i}, q_{\,j}}$ は、サジェストを経由してクリックした商品が意図に適合していれば1、していなければ0としました。

最後に、nDCGの計測方法を説明します。

$y_{\,j}$ を $j$ 番目サジェストに対する利得としたとき、nDCGにおけるDCGは以下の式で表されます。

dcg

ここで利得 $y_{\,j}$ は、以下のようにサジェストを経由して商品詳細に遷移した回数によって定義しました。

利得=3: 100回以上
利得=2: 10回以上100回未満
利得=1: 1回以上10回未満
利得=0: 上記以外

ZOZOTOWNで実際にある1日で表示されたサジェストを使用して実験をしました。実験にあたっては、はずれ値の影響を抑えるために、以下に該当するサジェストリストのフィルタリング処理を事前に行いました。

CTRやCVRが0もしくは1
同じ商品を除き商品詳細に遷移した回数が3回未満
検索回数が5回未満

結果

以下の表にそれぞれの指標におけるCTR, CVRの相関係数を示します。有効数字3桁となるように四捨五入してあります。

	nDCG	diversity	D#-nDCG
CTR	-0.00257	-0.153	0.253
CVR	0.177	-0.0353	0.219

D#-nDCGにおいては、弱い相関ではありますがnDCGよりも相関するという結果になりました。このことから、他の2指標と比較すると、D#-nDCGの値が高くなれば、ユーザーの検索体験の質が向上する傾向にあると言えます。

特に、CTRについてはnDCGとの差が大きいという結果になりました。これは、D#-nDCGはnDCGと比べ、クリックされた情報だけでなく、入力キーワードの意図をどの程度再現できるかを考慮している特徴が影響していると考察しました。

diversityがnDCGと比べ相関が弱くなった原因として、下記の影響が考えられます。

ZOZOTOWNではユーザーごとに異なる検索結果を表示しているため、いかなるサジェスト集合でも、サジェスト間の距離が大きく計測され多様性度も高くなる傾向にある。
入力キーワードによっては、多様なサジェストが表示される必要のない場合を考慮できない。例えば、入力キーワードが特定の商品名の場合は、遷移先の商品の多様性が乏しいためサジェスト集合の多様性度は低くなるが、CTRは低くならない。

まとめ

本記事では、サジェストにおける多様性評価指標と、それらの指標とCTR/CVRとの相関について紹介しました。実際に多様性評価指標を使うと、通常のnDCGに比べてCTR/CVRと相関することが分かりました。

引き続きサジェストの評価指標を調査し、さらにオフライン精度評価体制を整えていきます。

おわりに

ZOZOでは検索エンジニア・MLエンジニアのメンバーを募集しています。ご興味のある方は、以下のリンクからぜひご応募ください。

corp.zozo.com

参考文献

Ma, Hao and Lyu, Michael and King, Irwin. (2010, January). Diversifying Query Suggestion Results. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (pp. 1399-1404).↩
Zhu, Xiaofei and Guo, Jiafeng and Cheng, Xueqi and Du, Pan and Shen, Hua-Wei. (2011, March). A Unified Framework for Recommending Diverse and Relevant Queries. In Proceedings of the 20th International Conference on World Wide Web (pp. 37–46).↩
酒井哲也.（2015, 6月）. 情報アクセス評価方法論ー検索エンジンの進歩のためにー. コロナ社 (pp. 73-82).↩
Clarke, Charles L.A. and Kolla, Maheedhar and Cormack, Gordon V. and Vechtomova, Olga and Ashkan, Azin and Buttcher, Stefan and MacKinnon, Ian. (2008, July). Novelty and diversity in information retrieval evaluation. In Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval (pp. 659–666).↩
Cai, Fei and de Rijke, Maarten. (2016). A Survey of Query Auto Completion in Information Retrieval. In Foundations and Trends in Information Retrieval (pp. 1-92).↩
Cai, Fei and Reinanda, Ridho and Rijke, Maarten De. (2016, September). Diversifying Query Auto-Completion. In ACM Transactions on Information Systems (pp. 1-33).↩
Sakai, Tetsuya and Song, Ruihua. (2011, July). EvaLuating diversified search results using per-intent graded relevance. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval (pp. 1043–1052).↩

ZOZO TECH BLOG

TECH BLOG