# ウェブ検索クエリのための
部分一致文字列に対するエンティティ名称予測モデルの提案

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

## 1 はじめに

ウェブ検索クエリの多くには部分一致文字列が 含まれている。例えば，クエリ“かぐや様”はエン ティティ名称“かぐや様は告らせたい〜天才たちの 恋愛頭脳戦〜”に対する部分一致文字列である1). しかし，検索クエリとして発行された部分一致文字列が，ウェブページに対するクリック回数がわ ずかか，またはゼロのテイルクエリである場合は， フィードバックを取得することが困難になる。こう いったティルクエリに対してもエンティティリンキ ングを適切に行えるようにすることは検索性能の高 いシステムを作るうえでとても重要である.

そこで, 本研究では, エンティティリンキングの 構成要素のひとつとして, ウェブ検索クエリのため の部分一致文字列に対するエンティティ名称予測モ デルを提案し，次のような貢献を行う：

(i)ブロッキング [8] を用いた大規模分散処理のた めの効率的な訓練事例の自動生成方法を提案 する.

(ii)名称予測モデルのための新たな素性を提案 する.

(iii)フィードバックの取得できない事例に対する PU(Positive Unlabelled) 学習 [4] を用いたラベリ ング手法を提案する.

(iv)比較実験において, Random Forest[2] の予測値 とクリック頻度に基づくモデルの予測值を線形補間により組み合わせることで, nDCG@5 の観点で高い性能を達成したことを示す.

## 2 問題定義

クエリ $q$ 中の主要語 $s_{s}$, 周辺語 $s_{c}$ が与えられ たときにエンティティの名称の候補のランキング
 2020 年 12 月現在の検索意図を考慮している $\left.\langle s_{1}, \ldots, s_{n}\right.\rangle$ を算出する.

各々の $s_{k}($ for $k=1 \ldots n)$ は次のようにスコアリング される:

$\operatorname{score}\left(s_{k}\right)=\max \left.\{\psi\left(s_{k}, s_{s}, s_{c}, e\right) \mid e \in E, s_{k} \in S_{e}\right.\}$

ここで， $\psi$ はスコアリング関数， $E$ は知識ベース 内でのエンティティの集合, $S_{e}$ はエンティティ $e$ から展開できるエンティティ名称の候補の集合で ある.

## 3 提案手法

本研究は，ブロッキングを用いた訓練事例の生成 (3.1), PU 学習 (3.2)の二つから構成されている.

## 3.1 訓練事例の生成

正例の取得 次の条件をすべて満たした場合，ク エリ $q$ とエンティティ名称 $s$ は部分一致していると 判定し, クエリ $q$ 中の主要語 $s_{s}$, 周辺語 $s_{c}$, およ び，エンティティ名称 $s$ の組を正例とする:

(i)主要語 $s_{s}$ とエンティティ名称 $s$ が pkduck[13] の判定式 $\left|s_{s}\right|-\left|L C S\left(s_{s}, s\right)\right| \leq \delta$ を満たす $(\delta=0)$. あるいは事前に辞書登録されている。

(ii) $q$ 中の周辺語 $s_{c}$ がエンティティ $e$ の許可リスト に登録されている2)

(iii)エンティティ名称 $s$ と対応するウェブページに 対してクエリ $q$ でクリックがある.

ラベル未付与の事例の取得 正例と判定された事例から q-gram[5] を基にした手法によりブロッキン グのためのキーを抽出する．手順は次のとおりであ る: 1) エンティティ名称 $s$ を通常の q-gram と同様 に文字 n-gram に分割する。例えば $\mathrm{n}=2$ のとき “伊藤健太郎” は “伊藤”, “藤健”, “健太”, “太郎” の 4 つの キー (主キー)に分割される。2) クエリ $q$ 中の周辺語 $\left.s_{c}(\text { サブキー })^{3}\right)$ と主要語から抽出されたキーを結合

2）この許可リストはエンティティ $e$ と対応する概要文に周辺語 $s_{c}$ を照合するなどの操作により自動的に生成される.

3）周辺語が欠損している場合は周辺語モデルを参照し確率最

する．例えば $\mathrm{n}=2, s_{c}$ =“声優” のとき，“伊藤_声優”, “藤健_声優”, “健太_声優”, “太郎_声優” という 4 つの キーが生成される。3) 結合後のキーの生起頻度を計測し，一定頻度を超えるキーは除外する。

ラベル未付与の事例に対しても同様の方法でブ ロッキングのためのキーを抽出する.ここで，ラベ ル未付与の事例は, 周辺語モデルおよび名前エン ティティモデル [17] のエンティティ ID 同士を結合 したレコードから生成される.このレコードのエン ティティ名称および周辺語からそれぞれ主キー, サ ブキーを生成する．全ての事例を対象として，同一 のキーを持つもの同士でブロックを構成する. ブ ロックの要素がラベル未付与事例のみで構成されて いる場合はそのブロックを除外する. ラベル未付与 の事例に対する主要語 $s_{s}$ を同ブロック内の正例の 主要語を複製することで生成する. ${ }^{4)}$ 最後に残った 事例を学習に用いる。

素性の抽出 正例およびラベル未付与の事例そ れぞれに対し，クエリ素性 $(\mathrm{Q})$ ，エンティティ素性 $(\mathrm{E}) ，$ クエリエンティティ素性 $(\mathrm{QE})$ の 3 種類の素性 の抽出を行った。素性の一覧を表 1 に示す.

Randomized SVD 本研究では素性のうちの一部 を Randomized SVD[3, 7] により次元圧縮したうえで Random Forest への入力とする:

$
\begin{aligned}
X & =U \Sigma V^{*} \\
X V & =U \Sigma
\end{aligned}
$

ここで $X$ は各行が素性のベクトルである行列, $U, V$ は回転行列， $\Sigma$ は特異値の対角行列である． $X$ に対して次元圧縮の回転行列 $V$ を適用することは $V \Sigma$ を求めることと等価であるため, これを求める ことで次元圧縮を行う.

## 3.2 PU 学習

本研究では次のように PU 学習における Double Weighting[4] を適用する:

1) 正例およびラベル未付与の事例を訓練用とテス ト用の 2 つに分割する．2) 訓練用の正例およびラべ ル未付与の事例を入力とし, ラベルが付与されてい るか否かの予測器 $\mathrm{A}$ を生成する. 3) テスト用の正例 に対して予測器 $\mathrm{A}$ を適用し, ラベル付与確率 $g(x)$ の 平均 $c$ を求める. 4) テスト用のラベル未付与の事例 に対して予測器 $\mathrm{A}$ を適用し $w(x)=p(y=1 \mid x, s=0)$


の重みによりラベリングを行う。ここで $w(x)$ は定数 $c$ への依存を持つ. 5) テスト用事例と訓練用事例 を入れ替え，2 4 のステップを行う．6) 全ての事例 にラベルが付与されたことを利用し, エンティティ 名称の生成確率の予測器 B を生成する.

## 4 評価

## 4.1 比較手法

DMククエリ補完モデル $[17]^{5}$ ，クリックログを用いて 所与のクエリに対するエンティティ名称候補の生起確率をディリクレ-多項分布により表現したモデル.遷移先と遷移元のクエリが同一になりやすいか否か によりパラメータベクトルを設定．候補には遷移元 のクエリの複製も含まれる。

CLKDM からクエリの複製操作を取り除き，多項分布化した (パラメータベクトルのすべての要素をゼ ロにした) モデル

RF Random Forest[2]. Spark MLlib 2.4.5を使用. SVD による次元圧縮には Criteo Spark-RSVD ${ }^{6}$ を使用.

COMB(RF+CLK) RF と CLK の予測值の線形補間モデ ル: $\psi_{\text {score }}=\beta * \psi_{C L K}+(1-\beta) * \psi_{R F}$

COMB(RF+DM) RF とDM の予測值の線形補間モデ ル: $\psi_{\text {score }}=\beta * \psi_{D M}+(1-\beta) * \psi_{R F}$

## 4.2 データセット

クリックログ 2019 年 12 月 14 日から 2020 年 12 月 14 日の 1 年間にヤフー検索に対して発行されたクエ リ，および，そのとび先 URL のログ.

タクソノミーおよび知識ベース 2020 年 12 月 15 日付 けの内製の統合的知識ベース [15].

訓練事例 3.1 に示した手順により訓練事例の作成 を行った。正例 8,600,161 件，ラベル未付与事例 4,773,930 件が生成された。

## 4.3 評価用事例の作成

次の手順により評価用事例を作成した: 1) RF と CLK の予測結果間で順位一位のエンティティ名称 が異なるようなクエリを抽出する7)2) 周辺語の付与 されたクエリのうち人物, 建造物, 漫画, 映画カテ ゴリに属するクエリをそれぞれ 25 例ランダムサン
$ に要素を加える条件は pkduck の判定式を満たすか否かに変更した

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

7）一位の異なるクエリは 551,039 例, 同一のクエリは $7,084,003$例
}

プリングして抽出する 3) 周辺語の付与されていな いクエリのうち空白文字を含むクエリ，含まないク エリをそれぞれ 25 例ランダムサンプリングして抽出する 4) 計 150 クエリをヤフー検索に対して発行 する ${ }^{8)}$. 返却されたウェブページのそれぞれに対し て, 対応するエンティティ名称を記録する9). 5) ク エリ-エンティティ名称に対して，3 スケールで評価值を付与する: 所与のエンティティ名称が検索結果 の 1 位 ${ }^{10)}$ ，もしくは上位 10 件の $50 \%$ 以上を占めて いる場合は 2 , それ以外で検索結果に含まれる場合 は 1 ，検索結果に含まれない場合は 0 とする.

## 4.4 nDCG@5 の比較

4.3 で作成された評価用事例を用いて $\mathrm{nDCG} @ 5$ の計測を行った. 図 1 に線形補間の係数 $\beta$ を $[0,1]$ の範囲で変えたときの値の変化を示 す. $\beta$ の值が $[0,0.25)$ の範囲では CLK が提案手法の $\mathrm{COMB}(\mathrm{RF}+\mathrm{CLK})$ を上回る 0.568 を示し た. $\beta$ の値が $[0.25,1.0]$ の範囲では提案手法の COMB(RF+CLK) が CLKを上回る 0.593 を示し $た^{11)}$. 表 2 に $\operatorname{COMB}(\mathrm{RF}+\mathrm{CLK})$ がnDCG@5 の改善 に貢献した実例を示す。一方, DM は比較手法間で 最も低い性能となった。DM は遷移元のクエリを複製し, エンティティ名称の候補に加えるという操作 が含まれている. そのため, 1 位のエンティティ名称が正答と一致しにくくなり, nDCG のように順位 の影響を受けやすい評価指標において不利に働いた のではないかと考えられる.

## 4.5 素性の分析

図 2 に Random Forest の出力したジニ不純度に基 づく素性の重要度の上位 20 件を示す.

全体で最も効果が高かったのは MinMaxClickFreqで, 次点は MinMaxContProbで あった。一方, 最小最大スケーリングを行わなかっ た ClickFreq および ContProb は上位 20 件内では あるものの効果は大幅に劣るという結果になった.絶対值ではなくエンティティ名称候補間での相対值 が重要であるということがわかった。

全体で三番目に効果が高かったのは GrubbsSmirnovであった。訓練事例の中に, あ るクエリに対する候補エンティティ名称間での


ClickFreqのの分布を考えた時に，外扎値を含むよ うな分布が多く含まれていたということが考えら れる。

Randomized SVD により次元圧縮を行った ClassVec, SfreqVec, ContLocVec の 3 つのベク トルに関しては, この 3 つの中では相対的に ContLocVec の効果が最も高かった. ContLocVec の分散表現は, エンティティのクラスや周辺語を ClassVec およびSfreqVec よりも細かな粒度で表現 しているため, これら 2 素性の役割を包含している のではないかということが考えられる.

またContLocVec 自身よりもそこから派生し た ContLocVecCosMean, ContLocVecCosVar の方 が効果が高かった。ベクトル間の関係性を要約統計量で表現することで，より効果が高まったのではな いかと考えられる。

図 1: nDCG@5 の比較. RF, CLK, DM は $\beta$ とは非依存で ある

図 2: Random Forest の出力した素性の重要度. ContLocVec に対する添え字はベクトルの要素の番号

## 5 おわりに

本研究ではエンティティ名称の予測モデルの提案 を行った。今後の課題としては，より大規模な評価 を行うということやタイプクエリ判定 [10] や人物の 本業判定 [12] などの関連分野の技術をうまく組み合 わせるということがあげられる.

## 参考文献

[1]Roi Blanco, Giuseppe Ottaviano, and Edgar Meij. Fast and space-efficient entity linking for queries. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, pp. 179-188. ACM, 2015.

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

[3]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.

[4]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.

[5]Luis Gravano, Panagiotis G Ipeirotis, Hosagrahar Visvesvaraya Jagadish, Nick Koudas, Shanmugauelayut Muthukrishnan, Divesh Srivastava, et al. Approximate string joins in a database (almost) for free. In $V L D B$, Vol. 1, pp. 491-500, 2001.

[6]Frank E Grubbs. Procedures for detecting outlying observations in samples. Technometrics, Vol. 11, No. 1, pp. 1-21, 1969.

[7]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.

[8]George Papadakis, Dimitrios Skoutas, Emmanouil Thanos, and Themis Palpanas. Blocking and filtering techniques for entity resolution: A survey. ACM Computing Surveys (CSUR), Vol. 53, No. 2, pp. 1-42, 2020.

[9]Marius Paşca, Benjamin Van Durme, and Nikesh Garera. The role of documents vs. queries in extracting class attributes from text. In Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, pp. 485-494. ACM, 2007.

[10]Ellie Pavlick and Marius Pasca. Identifying 1950s american jazz musicians: Fine-grained isa extraction via modifier composition. In Proceedings of the 55th
Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 2099-2109, 2017.

[11]John W Pratt. Remarks on zeros and ties in the wilcoxon signed rank procedures. Journal of the American Statistical Association, Vol. 54, No. 287, pp. 655$667,1959$.

[12]Mahsa S Shahshahani, Faegheh Hasibi, Hamed Zamani, and Azadeh Shakery. Towards a unified supervised approach for ranking triples of type-like relations. In European Conference on Information Retrieval, pp. 707-714. Springer, 2018.

[13]Wenbo Tao, Dong Deng, and Michael Stonebraker. Approximate string joins with abbreviations. Proceedings of the VLDB Endowment, Vol. 11, No. 1, 2017.

[14]Frank Wilcoxon and Roberta A Wilcox. Some rapid approximate statistical procedures. Lederle Laboratories, 1964.

[15]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.

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

[17]豊田樹生, 夜久真也, 石川葉子, 土沢誉太, Kulkarni Kaustubh, Bhattacharjee Anupam, 宰川潤二. ウェブ 検索クエリに対する周辺語を考慮した教師なし エンティティリンキング. 言語処理学会第 25 回年次大会発表論文集, pp. 81-84, 2019.
表 1: 素性の一覧. クエリ素性 (Q)，エンティティ素性 (E)，クエリエンティティ素性 (QE)

 & Q \\

表 2: 実際の出力例. スコア順にエンティティ名称を列挙した. 評価点 2 の事例は太字にした. 正答と一致す るエンティティ名称には下線を引いた。

 & 南アフリカ国立動物園 & 南アフリカ国立動物園,アフリカンサファリ \\


部分一致文字列に対するエンティティ名称予測モデルの提案  豊田 樹生 小松 広弥 熊谷 賢 菅原 晃平 ヤフー株式会社 \{itoyota, hkomatsu, kenkumag, ksugawar\}@yahoo-corp.jp  