# 複数意図のエンティティクエリに対する 絞り込み検索のためのクエリ生成法の提案

豊田 樹生 齋藤 純 小松 広弥 熊谷 賢 菅原 晃平
ヤフー株式会社
\{itoyota, junsait, hkomatsu, kenkumag, ksugawar\}@yahoo-corp.jp

## 概要

本論文では複数意図を持つエンティティクエリに 対する絞り込み検索のためのクエリ生成に取り組 む. 複数の正例生成器とラベル未付与事例生成器を 組み合わせることで訓練事例を自動生成することを 提案する.クエリの組の CRR(Cumulative Reciprocal Rank) の差を含めた複数の素性を用いて Random Forest[4] による PU(Positive Unlabeled) 学習を行う.提案手法により CRR の差を単独で用いる場合より も $\mathrm{F}$ 值が 4.4 ポイント向上することを示す.

## 1 はじめに

ウェブ検索においては，しばしば複数意図を持つ エンティティクエリ [11]が発行される. 例えば，メ ディア作品名のクエリ “ゆるキャン $\triangle$ ”では, 漫画・ ドラマ・アニメなどの複数の意図がある. 人物名の クエリ “森麻季” では, アナウンサーや歌手などの 複数の意図がある.このようなクエリに対して，そ れぞれの意図に対応した絞り込み検索をできるよう することは検索体験を向上させるうえで重要であ る. 先行研究の複数意図クエリのブレンド検索 [12] や関連クエリの自動補完 [10] はエンティティクエリ を考慮したモデリング・評価が十分であるとは言い 難い。そこで，本論文では次のような貢献を行う：

(i)複数意図のエンティティクエリに対して絞り込 み検索を行えるようにするための再検索クエリ の生成方法として, 検索ログに蓄積された元ク エリ・再検索クエリの組を順位付けして利用す ることを提案する。

(ii)複数のラベル生成器を用いた訓練事例の自動生成法を提案し, PU(Positive Unlabeled) 学習を行 えることを示す.

(iii)Random Forest[4] により学習を行い，単独のラ ベル生成器を用いた場合と比較して $\mathrm{F}$ 值が 4.4 ポイント向上したことを報告する.

## 2 問題設定

元クエリ $q_{a}$ に対して, 再検索クエリ $q_{b}$ の順位付 けされたリストを生成する。

このとき, 次のクエリの要件を全て満たす候補の みを選択する：1) $q_{a} ， q_{b}$ はいずれもエンティティ クエリである 2) $q_{a}$ は複数のエンティティを指して いる 3) $q_{b}$ は特定のエンティティを指す意図の絞り 込みのクエリである

## 3 挑戦的課題

本タスクの挑戦的課題を次に示す：

意図の絞り込みではない再検索の除外 1) 力点の変化 を判定できなければならない。例えば“アガサクリ スティ” $\rightarrow$ “アガサクリスティねじれた家”の場合は 付加された“ねじれた家” に力点が変化している. こういった組は除外するべきである．2) 周辺語を含 まない部分一致はクエリの表層だけでは判定が難し い，例えば“東京” “東京タワー”の場合は意図を 絞り込んでいるわけではないため除外するべきであ る。一方, 同じ部分一致でも取り違える可能性の高 い組は絞り込みのための再検索として残す必要が

などが挙げられる.

知識外の再検索候補の順位付け 所与の知識ベースに 格納されているエンティティが再検索先の候補とし て最もふさわしくなるとは限らない。例えば“RHP” というクエリでは “バイトル RHP”(ホームページ作成サービス) などが再検索クエリの候補として挙げ られる。しかし, これと対応するエンティティは Wikipedia などの知識べースには格納されていない.

## 4 フレームワーク

図 1 に提案手法のフローチャートを示す.手順は 次のとおりである。まず，検索ログを二種類取得す る。一つ目は素性抽出用のログである。あらかじめ
学習時に参照するための素性を保存しておく. 二つ 目は順位付け対象となる元クエリおよび再検索クエ リの組を取得するためのログである (4.1 節)。この ログから取得された順位付け対象のクエリの組に対 し, 複数のラベル生成器を用いて正例とラベル未付与の事例とに分割する (4.2 節, 4.3 節). さいごに, $\mathrm{PU}$ 学習 [4] を行い, 順位付けのための回帰器の学習 およびそれを用いた予測確率の付与を行う (4.4 節).

図 1: フローチャート

## 4.1 検索ログの取得

ウェブ検索のセッションログ1)を取得する。この ログから再検索クエリ $q_{b}$ の発行された時刻 $t\left(q_{b}\right)$ と 元クエリ $q_{a}$ の発行された時刻 $t\left(q_{a}\right)$ の差が 30 秒以内のもののみを抽出する.

## 4.2 正例生成器

次の 3 つの正例生成器を提案する：

4.2.1 元クエリに対するエンティティリンカー 元クエリを内製のエンティティリンカー $[14,15,16]$ の入力とし, エンティティ ID を出力す る. 知識ベースからエンティティ ID と紐づく正式名称を取得する. 元クエリが正式名称に対する部分一致文字列になっている場合は元クエリ, 正式名称 の組を正例とする.

## 4.2.2クエリの組に対するエンティティリンカー元クエリと再検索クエリの組を内製のエンティ ティリンカー $[14,15,16]$ の入力とし, それぞれのエ ンティティ ID を取得する. 元クエリと再検索クエ リでそれぞれ異なるエンティティ IDを出力してい る組を残す2).さいごに，次の条件をすべて満たす 組を正例とする：1) 人物エンティティ間，または， メディア作品間の遷移である 2) 元クエリに周辺語

1） セッションとは, ある特定のユーザーが一定時間内に発行 した一連のクエリとそれに伴うユーザ行動のことを指す。

2）同一 ID を指す再検索クエリが複数ある場合は生起確率の最 も高い候補を選択する
は含まれない3)3) 遷移前後で主要語と周辺語の入れ 替わりが起きていない

## 4.2.3クェリの組に対する CRR の差

クエリの組に対する CRR(Cumulative Reciprocal Rank)[5] の差 $\triangle C R R$ はクエリ自動補完の分野におい てしばしば用いられる指標である $[10,12]^{4)}$. 本論文 では $\triangle C R R$ を次のように表現する：

$
\Delta C R R=\sum_{d \in D_{b}}\left(\frac{1}{r\left(q_{b}, d\right)}-\frac{1}{r\left(q_{a}, d\right)}\right)
$

ここで $D_{b}$ は再検索クエリ $q_{b}$ によってクリック されうる文書の集合, $r\left(q_{b}, d\right)$ は再検索クエリ $q_{b}$ に 対する文書 $d$ の順位, $r\left(q_{a}, d\right)$ は元クエリ $q_{a}$ に対す る文書 $d$ の順位である.

元クエリ $q_{a}$ では上位に順位付けできなかった文書を再検索クエリ $q_{b}$ が上位にできれば $\triangle C R R$ は正 の值をとる.このとき再検索クエリ $q_{b}$ はユーザー にとって役に立ったとみなすことができる [12].

本論文では, $r\left(q_{b}, d\right)$ および $r\left(q_{a}, d\right)$ の順位は所与のクエリに対するクリック先文書の CTR(Click Through Rate) の順位によって算出する5). CTR の算出に用いられた文書の延べ数が各 10 以上，かつ,再検索クエリ側の文書の延べ数が元クエリ側の延 べ数の $10 \%$ 以上, かつ, $\triangle C R R$ が 0 より大きく 1.5 以下の場合に元クエリ・再検索クエリの組を正例と する。 $\triangle C R R$ に対するしきい值の決定方法の詳細は 5.5 節で述べる.

## 4.3 ラベル未付与事例生成器

次のラベル未付与事例生成器を提案する：

生成器 1 元クエリがあいまいさ回避ぺージ6) と対応 するエンティティの名称と一致する事例をラベル未付与とする

生成器 2 クエリの組に対する正例の生成時 (4.2.2 節) に正例と判定されなかった事例のうち周辺語を含ま ず ID が異なるクエリの組をラベル未付与とする

生成器 $3 \quad \Delta C R R$ による正例の生成時 (4.2.3 節) に正例 と判定されなかった事例をラベル未付与とする

3）元クエリの主要語が空白で区切られている場合, 空白の後 の文字列は周辺語とはしない

4）順位に対数を適用した重みづけ [10]，セッション後半のク リック先を利用したスコア補正 [12] などいずれも派生的な $\triangle C R R$ の定義をしている

5）本論文では滞在時間による足切りは行わない

6) https://w.wiki/4dcg

ここで，すでに正例と判定されていた事例につい てはラベル未付与とはせず正例とした.

## 4.4 PU 学習

本論文では次のように PU 学習 [7] を行う. まず ラベル未付与の事例に対してラベルを付与する：

1) 正例およびラベル未付与の事例を訓練用とテス ト用の 2 つに分割する．2）訓練用の正例およびラべ ル未付与の事例を入力とし, ラベル付与確率の回帰器を生成する.3) テスト用の正例に対してこの回帰器を適用し, ラベル付与確率 $g(x)$ の平均 $c$ を求め る. 4) テスト用のラベル未付与の事例に対して回帰器を適用し $w(x)=p(y=1 \mid x, s=0)$ の重みによりラ ベリングを行う. ここで $w(x)$ は定数 $c$ への依存を 持つ.5) テスト用の事例と訓練用の事例を入れ替 え，2 4 のステップを行う.

全ての事例にラベルが付与されたら二分割交差検定を行い，各テスト用事例に対して付与された予測確率を順位付けに用いる。

## 4.4.1 素性

PU 学習の際に用いる素性を表 1 に示す.

表 1: 素性

 \\

$\mathrm{i}$ 取得期間のログでの生起回数が合計 10 未満である場合は除外

以下，詳細が必要な素性について説明する：

クェリの分散表現クエリログからトークン数 が 2 以上のレコードを抽出し, トークンの生起回数に基づくShifted Positive PMI の行列 $X$ を生成 する.この行列に Randomized SVD[6,8] を適用し $X=U \Sigma V^{*}$ を得る. ここで， $U, V$ は直交行列， $\Sigma$ は特異値の対角行列である。トークンの分散表現に行列 $W^{S V D_{\alpha}}=U(\Sigma)^{\alpha}$ を用いる [9] ${ }^{7) 8)}$ 。クエリの分散表現はトークンの分散表現の加算により生成する9).

## 5 評価

## 5.1 データセット

各データセットの詳細を次に示す：

参照用素性 2021 年 11 月 01 日 11 月 30 日までの期間のセッションログを用いて素性を抽出した。

内製のエンティティリンカー 2021 年 12 月 01 日付け のモデル (モデルの訓練には 12 月 01 日付けの内製知識ベース [13] および 12 月 01 日以前の直近 1 年間 のヤフー検索のクリックログを利用)

順位付け対象事例 2021 年 12 月 17 日 12月 23 日ま での期間に発行された元クエリと再検索クエリの 組. 4 章で示した操作により順位付け対象事例に対 して確率を付与した ${ }^{10)}$.このときの素性は前述の参照用素性を利用した. ${ }^{11)}$

開発・評価事例 順位付け対象事例のうち元クエリに 対するエンティティリンカーの推定結果の一位が あいまいさ回避エンティティと対応し, かつ, 元 クエリあたりの再検索クエリの異なり数が 50 以上 の事例のみを残した。まず元クエリ 100 事例を非復元抽出し,この元クエリを含む組を評価用とし た。評価用として使用されなかった組から $\triangle C R R$ が $[0.5,2.0]$ の範囲の 0.25 刻みで各 10 事例ずつ非復元抽出した.この計 70 事例を開発用事例とした.

## 5.2 比較手法

比較手法を次に示す ${ }^{12)}:$

RF Random Forest[4]によりPU 学習を行った. Spark MLlib 2.4.6を使用. Randomized SVD には Criteo Spark-RSVD ${ }^{13)}$ を使用.

DCRR 素性抽出用ログの期間に計算した $\triangle C R R$ の値 を適用した。このときしきい値を 1.5 に設定した。

7） パラメータは $\alpha=1.0$, negative-sampling の值 $k=5.0$ に設定

8）クエリ発行時間間隔の制約を一旦解除してトークンの生起回数を計算した。制約下で生起しないトークンの分散表現は 除外した。

9）クエリが 1 トークンで構成される場合は，クエリの分散表現はトークンの分散表現と等しくなる.

10） 正例は $1,225,010$ 事例, ラベル未付与事例は 9,036,884 事例 であった。PU 学習前にランダムオーバーサンプリング [1] に より両方の数を均等にした。

11）紙面の都合により本論文では交差検定の結果について取り 扱わないが，時系列データなどに対する交差検定の手法はい くつか提案されている。予測対象の直近の区間の素性は利用 しないという点で noDepCV[3] に近い手法といえる.

12）評価事例に対する DCRR 以外の正例生成器 (4.2.1 節, 4.2.2

節) の正例生成数はゼロであったため比較手法から除外した

13) https://github.com/criteo/Spark-RSVD

## 5.3 評価方法

2022 年 1 月 5 日にヤフー検索 ${ }^{14)}$ に対してクエリ を発行した。これらの事例に対して次の 3 段階のス コアを付与した : 1.0：クエリの要件 (2 章)を満た し, かつ, 検索結果 1 2 ページ目のいずれかの文書 に対応している. 0.5 ：クエリの要件を満たさない が，検索結果 1 ページ目の上位 5 件以内の文書と対応している. 0.0 ：上記以外

表 2 にクエリの要件の具体例を示す.

表 2: クエリ要件の具体例。下線部は元クエリ。

## 5.4 正例生成器 $(\Delta C R R)$ のしきい值の設定

開発事例に対して 3 段階のスコアを付与した $(5.3$節). このとき $\mathrm{F}$ 值が最大となったしきい值 1.5 を設定した15).

## 5.5 評価結果

評価事例に対して 3 段階のスコアを付与した $(5.3$節). 付与結果をもとにして適合率, 再現率, $\mathrm{F}$ 値を 計測した. 表 3 に結果を示す. 適合率@3 について DCRR がRF 12.4 ポイント上回った. 再現率@3 および F 值について，RF が DCRR をそれぞれ 12.3 ポイント, 4.4 ポイント上回った.

表 3: 適合率, 再現率, $\mathrm{F}$ 值. Bootstrap 検定 [2] ではいずれ の差分も統計的に有意 $(p<0.05)$ であった.

表 4 に順位付け結果の例を示す．RF はクエリ“花鳥風月”に対して知識外の花鳥風月 (ビール) も含め て順位付けできた。また，クエリ“山頭火”に対し て周辺語を含まない部分一致の再検索クエリである “種田山頭火”も含めて順位付けできた。

表 4: 順位付け結果. 下線かつ太字はスコア 1.0 , 下線のみ はスコア 0.5 , 下線無しはスコア 0 . 左から順に $1,2,3$ 位

 \\

14) https://search.yahoo.co.jp

15）このときの $\mathrm{F}$ 值は 0.735

## 5.6 素性の重要度の分析

Random Forest[4] の出力した分散に基づく素性の 重要度の上位 25 件を図 2 に示す。上位を独占した のは $\triangle C R R$ 関連の素性であった。 $\triangle C R R$ 自身の值 DeltaCRR $\left(q_{a}, q_{b}\right)$ よりもその算出に関わったクリッ ク先の文書数の比率 DeltaCRRRatio $\left(q_{a}, q_{b}\right)$ の方が 重要という結果となった。この素性は暗黙的に候補間での相対的な再検索クエリの人気度を包含してい るため, これが重要だったのではないかということ が考えられる。次点は検索補助関連の素性という結果となった。上位の $\operatorname{Assist}\left(q_{a}\right)_{16}, A \operatorname{sist}\left(q_{b}\right)_{14}$ は同一素性でもベクトルの位置が異なっている．元クエリ と再検索クエリでは注目するべき検索行動が異なる ということが示唆される。クエリの分散表現関連の 素性は上位 25 件内に確認できなかった。この理由 としては, 正例生成器において $\Delta C R R$ とエンティ ティリンカーの判定の論理和を利用したため, 本来 クエリの意味の観点からは正例に算入するべきでは ない事例 (e.g., “XXX 店舗” の構成の再検索クエリを 含む組) が一律に正例として混じってしまい，回帰器の学習時にこの素性が利用される場面が限定的に なってしまったのではないかと考えられる。

図 2: 素性の重要度. 添え字はベクトルでの位置 (0-base).

## 6 おわりに

本論文では複数の正例生成器とラベル未付与事例生成器を組み合わせることで訓練事例を生成す ることを提案した。 $\triangle C R R$ を単独で用いる場合より も，複数の素性を用いた Random Forest[4] による順位付けのほうが $\mathrm{F}$ 值が 4.4 ポイント向上することを 示した。

## 参考文献

[1]Gustavo EAPA Batista, Ronaldo $\mathrm{C}$ Prati, and Maria Carolina Monard. A study of the behavior of several methods for balancing machine learning training data. ACM SIGKDD explorations newsletter, Vol. 6, No. 1, pp. 20-29, 2004

[2]Taylor Berg-Kirkpatrick, David Burkett, and Dan Klein. An empirical investigation of statistical significance in NLP. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 995-1005. Association for Computational Linguistics, 2012.

[3]Christoph Bergmeir and José M Benítez. On the use of cross-validation for time series predictor evaluation. Information Sciences, Vol. 191, pp. 192-213, 2012.

[4]Leo Breiman. Random forests. Machine learning, Vol. 45, No. 1, pp. 5-32, 2001.

[5]Allison JB Chaney, David M Blei, and Tina EliassiRad. A probabilistic model for using social networks in personalized item recommendation. In Proceedings of the 9th ACM Conference on Recommender Systems, pp. 43-50, 2015.

[6]Paul G Constantine and David F Gleich. Tall and skinny qr factorizations in mapreduce architectures. In Proceedings of the second international workshop on MapReduce and its applications, pp. 43-50, 2011.

[7]Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 213-220, 2008.

[8]Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, Vol. 53, No. 2, pp. 217-288, 2011.

[9]Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. Advances in neural information processing systems, Vol. 27, pp. 2177-2185, 2014.

[10]Umut Ozertem, Olivier Chapelle, Pinar Donmez, and Emre Velipasaoglu. Learning to suggest: a machine learning framework for ranking query suggestions. In
Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval, pp. 25-34, 2012.

[11]Jeffrey Pound, Peter Mika, and Hugo Zaragoza. Adhoc object retrieval in the web of data. In Proceedings of the 19th international conference on World wide web, pp. 771-780. ACM, 2010.

[12]Milad Shokouhi, Marc Sloan, Paul N Bennett, Kevyn Collins-Thompson, and Siranush Sarkizova. Query suggestion and data fusion in contextual disambiguation. In proceedings of the 24th international conference on world wide web, pp. 971-980, 2015.

[13]Tomoya Yamazaki, Kentaro Nishi, Takuya Makabe, Mei Sasaki, Chihiro Nishimoto, Hiroki Iwasawa, Masaki Noguchi, and Yukihiro Tagami. A scalable and plug-in based system to construct a production-level knowledge base. In Proceedings of the 1st International Workshop on Challenges and Experiences from Data Integration to Knowledge Graphs co-located with the 25th ACM SIGKDD International Conference on Knowledge Discovery \&Data Mining, 2019.

[14]豊田樹生, 小松広弥, 熊谷賢, 菅原晃平. ウェブ検索クエリのための部分一致文字列に対するエン ティティ名称予測モデルの提案. 言語処理学会第 27 回年次大会発表論文集, pp. 590-594, 2021.

[15]豊田樹生, 土沢誉太, 築地毅, 菅原晃平, 野口正樹. dishpam: A distributable seeded hierarchical pachinko allocation model. 言語処理学会第 26 回年次大会発表論文集, pp. 217-220, 2020.

[16]豊田樹生, 夜久真也, 石川葉子, 土沢誉太, Kulkarni Kaustubh, Bhattacharjee Anupam, 宰川潤二. ウェブ 検索クエリに対する周辺語を考慮した教師なし エンティティリンキング. 言語処理学会第 25 回年次大会発表論文集, pp. 81-84, 2019.
 豊田 樹生 齋藤 純 小松 広弥 熊谷 賢 菅原 晃平 ヤフー株式会社 \{itoyota, junsait, hkomatsu, kenkumag, ksugawar\}@yahoo-corp.jp  