WWW2009 MADRID!

於 WWW論文読み会（webkai）
東京大学岡崎直観（辻井研究室）

以下のURLに置いてあります
◦ http://www.chokkan.org/www2009/
E. Diemert, G. Vandelle.
(Yahoo! Search Innovation)
Unsupervised query categorization
using automatically-built concept
graphs, WWW2009, pp. 461-470.

クエリからカテゴリを推定したい
◦ 「音楽に関連するクエリに対して，アーティストの
ニュースやビデオなどを提示したい」

本研究の目標
◦ 教師無しの手法で高性能なクエリ分類システムを作る
◦ Webくらいの大規模なコーパスにスケールさせる
◦ Webの構造化されていないデータで分類システムを作る

研究の成果
◦ 提案手法でも教師有りの分類システムと肩を並べる
◦ 提案手法で構築した概念グラフが，クエリログやWeb文
書の知識の代わりとなり得ることを発見した

ノード = 概念
◦ 本研究では，名詞句とする（※NPチャンキングなどはやらないが）

エッジ：
1
xref N (t , t ' ) 
N
1
[ t 'd ]
d DtN
tで検索した検索結果上位
N件にt’が含まれる割合
◦ ノードt, t’間のエッジは必ず一方向（強い方だけ）

無向非循環グラフ
◦ サイクルが出来てしまうときは，サイクル中の再弱のエッジを切る

カテゴリを表すノードを概念グラフ内に取り込む
◦ 各カテゴリには10個以内のキーワードが付与されている
 カテゴリ名で検索して得られたスニペットに含まれる語をキーワードとする
 例: Helth: {diet, fitness, longevity, disease, symptoms, tretments}
◦ あるカテゴリのキーワードから0.5以上の関連度を持つ概念ノード（2次
以上も）をdescriptorノード群とする
◦ そのカテゴリのノードを概念グラフ内に作成し，descriptorノード群か
ら関連度1.0としてエッジを張る

クエリqが与えられたとき，そのクエリが属する
カテゴリの重み付きスコアを求める
◦ クエリから概念のスコア付けを行う
w0 (concept ) 
1
N
1
[ conceptd ]
d DqN
◦ 概念のノードからスコアを伝搬させる（４次まで）
w(v)  w(v) 
 w( p)  xref ( p, v)
p pred ( v )
◦ 最終的にカテゴリノード受け取ったスコアが，クエリの
カテゴリ所属スコアになる

Yahoo! Search USのクエリログのうち，3151クエリを
９カテゴリ（音楽，旅行，映画，･･･）に手作業で分類
SVM（RFBカーネル）

KDD Cup 2005データ
◦ MSN Searchの800のクエリに67カテゴリを手作業で付与
J. Hu, G. Wang, F. Lochovsky,
J.-T. Sun, Z. Chen.
(MSRA & HKU)
Understanding user’s query
intent with Wikipedia,
WWW2009, pp. 471-480

目標
◦ 入力クエリの意図クラスを推定するための意味表現形式
◦ 検索意図を正しく分類するための意図クラス境界の決定法
◦ 入力されたクエリの意図クラスを分類する方法

成果
◦ 意図カテゴリを，Wikipediaの概念とカテゴリで表現する
 例えば，意図クラス「旅行」をWikipedia検索にかけて，「旅行会
社」「航空券」などの関連カテゴリ，「時差ぼけ」「搭乗券」な
どのWikipedia記事で表現する
◦ Markovランダムウォークを使って，各概念・カテゴリが意図
クラスに属するスコアを求める
◦ 入力されたクエリをWikipediaの概念・カテゴリに直接対応付
けられないとき，関連する概念・カテゴリを見いだす

ノード
◦ Wikipedia概念（記事）
◦ カテゴリ

エッジ
◦ カテゴリの親子関係
◦ 記事間のリンク（Wikilink）
◦ 記事のカテゴリ所属関係

エッジの重み
◦ 上述の関係によるリンクの数
‘+’は意図クラスのシード概念・
カテゴリを表す（次のスライド）

意図クラスを表すシード概
念を用意する
◦ 「旅行」クラスなら，「旅行」
「ホテル」「カテゴリ：旅行」
「航空券」など
◦ これらのノードに対し1/N，そ
れ以外のノードに0を与えるベ
クトルv0を用意する（Nはその
意図クラスのシード概念数）


エッジの重みから遷移確率
行列（P）を求める
活性伝搬を行い，シードに
関連する概念・カテゴリを
スコア付きで求める
活性伝搬でスコアを受け取った
ノードの色が濃くなっている

入力されたクエリがグラフ上に存在するとき
◦ その活性値で識別（識別基準が書かれていなかった･･･，
多分何らかの閾値を設定しているはず）

入力されたクエリがグラフ上に存在しないとき
◦ Live Searchを使ってスニペットを得る
◦ スニペットに含まれる語と関連の深い概念を見つける
 スニペットの単語ベクトルと，Wikipedia記事の類似度
（BM25）で，概念のスコア付けを行う
◦ 見いだした概念の意図クラスに関する活性値の和を計算
 ある閾値θを超えたら，その意図クラスに属すると判定

手法
◦ LR: ロジスティック回帰
 ベース概念が素性
◦ LRE: LRと活性拡散
 拡張された概念が素性となる
◦ WIKI: 提案手法
◦ WIKI-R: 活性拡散を行わない

テストデータは自作
◦ 「旅行」「人名」「仕事」
X. Yi, H. Raghavan, C. Leggetter.
(Massachusetts Amherst &
Yahoo! Labs)
Discovering users’ specific geo
intention in Web search,
WWW2009, pp. 481-490

13%以上のWeb検索は，位置に関する問い合わせ
◦ “manhattan coffee” →「マンハッタンにあるコーヒーショッ
プを探している」

位置に関する検索意図があると思われるクエリの
50%しか，場所名が明示されていない
◦ “pizza” →「ピザの店を探している」らしいが，場所が不明

検索クエリによって，場所のローカルさが異なる
◦ “pizza” “dentist” →「近くのピザ屋」「近くの歯医者」
◦ “map” ”hotel” →「旅行先の地図」「旅行先のホテル」

検索クエリによって，場所の範囲が異なる
◦ “pizza” → 10マイル程度の粒度
◦ “dentist” → よい歯医者なら30マイルまでOK
◦ “2008 honda civic” → 安ければ100マイルまでOK

検索クエリに都市レベルの粒度の場所検索意図がある
かどうかを推定
◦ “pizza” → +1; “funny cats” → -1

検索クエリの（IPアドレスなどから推測される現在位
置に対する）ローカルさを推定
◦ local geo queries（高ローカル）: “pizza” “dentist” など
◦ neighbor region geo queries: “car dealer” “real estate”
◦ others（低ローカル）: “state map” “hotels”

場所に関するクエリに対応する都市を推定
◦ “Liberty Statue” → New York

クリックスルー・データから訓練例を自動獲得
no
yes
yes

システムからの出力
◦ Qに場所に関する検索意図があるかどうか
 その場所はlocal, neighbor, otherのどこにあるか
 Qに対応する場所を表す都市名

クエリQが与えられたとき，場所Ciを推定したい
◦ ナイーブベイズモデル（もどき）で推定
P(Ci | Q)  P(Ci ) P(Q | Ci )
 P(Ci)は一様分布として無視する（→「もどき」）

P(Q|Ci)は都市ごとのbi-gramモデルで推定
n
P (Q | Ck )   P ( wi | wi 1 , Ck )
i 1

基本的にはunigram, bigram, trigramを以下の
基準で重み付けしたもの
◦ クエリ中の場所以外（Qnc）に出現した回数，確率
◦ n-gramのコーパス中での出現頻度，確率
◦ n-gramと都市名に関するクエリ部分（Qc）の共起の強
さ（PMI）
◦ n-gramと共起する都市名の数
◦ 都市毎のP(w|Ck)
◦ すべての都市に関して最大のP(w|Ck)
◦ 確率分布P(w|Ck)と一様分布とのKL距離

訓練例は検索クエリログから自動構築
◦
◦
◦
◦

クエリQで検索 → DN+のサイトをクリック: +1
クエリQで検索 → DN+のサイトをクリック: -1
+1: 7.5M事例
-1: 57.8M事例
QをQcとQncに分解
◦ Qncから+1/-1を推定

検索クエリQをQcとQncに分解する
◦ Qcが表す場所と検索したIPアドレスの位置の距離を計算
 距離が50マイル未満: local geo
 距離が50マイル以上100マイル未満: neighbor region geo
 距離が100マイル以上: other
◦ Qncから上記の３つのラベルを当てる

検索クエリQをQcとQncに分解する
◦ Qcを場所名とみなしてP(Qc|Qnc)の確率モデルを作る

Qncから最大のP(Qc|Qnc)を与えるQc*を選び，
P(Qc*|Qnc)>ta ならば，Qc*を予測した都市とする
◦ taを変えながらprecision-recallカーブを描く

Download Report