ウェブ検索ログを用いた
ラベル伝播による意味カテゴリ獲得
小町守（奈良先端大）
牧本慎平・内海慶・颯々野学（Yahoo!）
2009-05-21
情報処理学会第191回自然言語処理研究会
第76回音声言語情報処理研究会
背景: 検索ユーザの関心を見つけることが重要
• ターゲット広告
男性
既婚
30代
就職活動中
…
!
• クエリ書き換え・クエリ提案・クエリ展開
ipot
アイポット
ipod
search
iPot
ipot price
i-pot
i-Pot
あいぽっと
2
コーパスに基づく意味カテゴリ獲得
入力
（コーパスから抽出する）
出力
単語
パターン
新しいクエリ
Singapore
___ visa
Hong Kong
Singapore visa
Australia
Singapore map
Hong Kong
___ history
China
Egypt
このステップを繰り返す
3
本研究のポイント
大規模化・クリックログ・グラフ理論の適用
100万検索クエリ
before
Tchai
after
Quetchup
検索クエリログ
（以前作った）
検索ログ
DB
DBサイズ
巨大
検索ログ
検索ログ
DB
DB
1,000万検索クエリ
ブートストラップ
検索クエリ
+
クリックログ
グラフ理論
4
Quetchup アルゴリズム
(QUEry Term CHUnk Processor)
• 情報獲得源としてクリックスルーログを用いる
アップル
クリック
コンピュータ
• グラフ理論による半教師ありアルゴリズム
• 並列分散環境を用いたラベル伝播の大規模化
5
ブートストラップにおいては意味ドリフトが大問題
入力
（コーパスから抽出した）
出力
単語
パターン
新しい単語
___ visa
UFJ
Singapore
ANA
意味カテゴリが変わってしまった
ANA
___ airlines
United
Delta
次のステップにエラーが伝播してしまう6
クリックスルーパターンを使って意味カテゴリを学習
入力
（クエリからクリックされたアドレス）
出力
単語
パターン
新しい単語
Singapore
en.wikipedia.org/wiki/Singapore
新加波
昭南島
同じアドレスをクリックする単語は同じ意味
新加波
www.singaporeair.com/saa/zh_CN
大規模に入手可能
検索クエリと比較して曖昧性が少ない
Kuala
Lumpur
Penan
7
グラフ理論に基づく意味カテゴリ学習
• ブートストラップアルゴリズムの一部はグラフ上の類似度計
算と見なせる（Komachi et al. EMNLP-2008）
Singapore
UFJ
Hong Kong
ANA
China
？
___ history
___ map
似たパターンと共
起するクエリは似
ている
___ visa
___ airlines
リンク解析（Googleの
PageRank等）の手法を
用いて計算できる
8
クリックスルーによるインスタンス・パターン共起グラフ
• クエリ“Hong Kong”→http://en.wikipedia.org/wiki/Hong_Kong
Singapore
http://www.cikm2009.org/
http://www.acl-ijcnlp-2009.org/
UFJ
Hong Kong
ANA
http://www.singaporair.com/hk.jsp
http://en.wikipedia.org/wiki/Hong_Kong
http://www.bk.mufg.jp/
http://www.china-airlines.co.jp/
China
http://www.ana.co.jp/
9
Quetchup アルゴリズム
(QUEry Term CHUnk Processor)
• 情報獲得源としてクリックスルーログを用いる
• グラフ理論による半教師ありアルゴリズム
• 並列分散環境を用いたラベル伝播の大規模化
DBサイズ
巨大
DBサイズ
DBサイズ
巨大
巨大
Pierre-Simon Laplace (1749-1827)
10
Zhou et al. (NIPS-2004) によるラベル伝播アルゴリズム
X はインスタンスの集合
xi はインスタンス
• 類似度行列 W を以下のように定める。
2 2
W
exp(
x
x
2
)
if i != j and Wii = 0.
ij
i
j/
1
/
2
1
/
2
• 行列 S
を構築する。
D
WD
Dは要素 (i,i) が W のi番目の行の和となるような次数対
角行列である。
• 収束するまで F
(
t
1
)
SF
(
t
)
(
1
)
Y
を反復する。αは（0,1）の範囲のパラメータである。
•
F*
を列 {F(t)} の極限とし、各点 xi を
によってラベル付けする。
*
j ij
y
arg
m
F
a
i
11
提案手法: ラプラシアンラベル伝播アルゴリズム
T
• 類似度行列 W を右のように定める。W
A
A
ただし、A はインスタンス・パターン共起行列である。
並列分散計算が可能なように分解
1
/
2
1
/
2
• 正規化ラプラシアン行列 L
を構築する。
I
D
WD
Dは要素 (i,i) が W のi番目の行の和となるような次数対
角行列である。 グラフラプラシアンによって意味ドリフトの影響を抑制
• 収束するまで F
(
t
1
)
(
L
)
F
(
t
)
(
1
)
Y
を繰り返す。ただしαは (0,1) の範囲のパラメータである。
•
F*
を列 {F(t)} の極限とし、各点 xi を
によってラベル付けする。
*
j ij
y
arg
m
F
a
i
12
列 {F(t)} は F* = (1-α)(I-αS)-1Y に収束する
証明:
• F(0) = Y とする。
t
1
t
1
i
F
(
t
)
(
(
L
))
Y
(
1
)
(
(
L
))
Y
.
• 反復的に計算すると、
i
0
• 0 < α < 1 かつ (-L) の固有値は
[-1, 1] にあるので、
t
1
t
1
(
m
(
L
))
(
I
(
L
))
(
I
L
)
lim
((
L
))
0
,
li
t
t
i
1
i
0
1
*
1
F
l
F
i
(
t
)
m
(
1
)(
I
L
)
Y
,
• 従って
t
また、分類タスクでは、これは以下と同値である。
*
1
F
(
I
L
)
Y
.
正則化ラプラシアンカーネル
(Smola and Kondor, COLT-2003)と一致する
13
グラフに基づく手法は単純だが、
ウェブ文書などの大規模なデータにスケールする
利点
• 大規模な生データにスケールする（並列分散計算）
• 数学的背景が確立している（PageRank のように求める
ことができる）
欠点
•
•
•
•
計算効率（→近似することができる）
なにが「よい」グラフか自明ではない
計算リソースが必要（CPU・ディスク・メモリ・などなど）
扱うために（バッド）ノウハウが必要
14
実験
検索ログからの意味カテゴリ学習
15
実験設定
検索ログ
• 日本語ウェブ検索ログ2008年8月分
• 頻度上位1,000万件（異なり）
• 圧縮状態で60GB（展開すると300GB）
DBサイズ
巨大
DBサイズ
DBサイズ
巨大
巨大
パターン
• 2単語クエリパターン・クリックパターン
使用カテゴリ（Komachi and Suzuki, IJCNLP-2008）
カテゴリ
旅行
金融
シード
jal, ana, jr, じゃらん, his
みずほ銀行, 三井住友銀行, jcb, 新生銀行, 野村證券
16
実験の評価
比較手法
• Tchai（クエリ）・Quetchup（クリック・クエリ）
アノテーション
• 複数単語の場合は全ての単語についてドメインを付与
• 1単語について複数のドメインを付与
評価尺度
• 精度
• 相対再現率（Pantel and Ravichandran, NAACL-2004）
R
C
C
|
A
| RA|B はシステムAのBに対する相対再現率
AC
A
AP
A
R
A
|
B
CX はシステム X の出力中の正解の数
R
C
C
C
P
|
B
|
B B
B B
あるシステムから見た別のシステムのカバー率
C は真の正解の数
PX はシステム X の精度
|X| はシステム X の入力の数
17
旅行ドメインでの精度
クリックスルーを用いた
手法が一番高い精度
18
金融ドメインでの精度
金融ドメインもクリックスルー
ログを用いた手法が一番高い精度
19
旅行ドメインでの相対再現率
クリックスルーログを用いた手法
は精度が高いだけではなく相対
再現率も高い水準
20
金融ドメインでの相対再現率
21
抽出したクエリの上位1万件のランダムサンプル
タイプ（頻度）
例
交通（54）
広島 新幹線, 東海道線, jr飯田線, jr博多,京都 新幹線
宿泊（10）
ホテルビーナス, リーガロイヤルホテル大阪, www.routeinn.co.jp, ホテル京阪ユニバーサル・シティ, 札幌全日空ホテル
旅行情報
（10）
外務省 安全, チケットショップ 大阪, 観光 関西, 高山観光協会,
グーグル ナビ
旅行代理店
（6）
jr おでかけネット, 近畿ツー, タビックス 静岡, フレックスインター
ナショナル, オリオンツアー
その他（2）
プロテカ（Proteca; 旅行かばんのブランド名）, jal紀行倶楽部
無関係（20）
格安航空チケット 海外, 新幹線予約状況, 新幹線 時刻表, 温泉
宿,新幹線 停車駅, 虎, youtubu海外ドラマ, 法務部採用, おくりび
と, 社会人野球
25
パラメータαによる Quetchupclick の性能の違い
クリックスルーグラフはクエリグラフより密な
グラフを作るため、大きなαの値（初期ラベ
ルをあまり信用しない）でも小さなαの値より
精度が高かった
27
関連研究
Pasca et al. (WWW-2007, IJCAI-2007)
• 自然言語処理の分野で初めてウェブ検索クエリログの重要性
を説いた
• 固有表現の属性を学習することに焦点を当てている
Talukdar et al. (EMNLP-2008), Pasca and Durme (ACL-2008)
• ウェブ文書とウェブ検索クエリログを組み合わせる
Hagiwara and Suzuki (NAACL 2009)
• グラフカーネル（ノイマンカーネルと拡散カーネル）をクエリ書
き換えタスクに適用
28
まとめ
• クリックスルーログは意味知識抽出に効果
が高い情報源である
• グラフ理論に基づく手法はブートストラップ
よりはるかに少ないパラメータで扱いやす
く、理論的背景も確立されている
29
今後の予定
• 自然言語処理タスクで有用な情報源につ
いてさらに調査する
• マルコフランダムウォークとラベル伝播手
法の関係について考える
• 大規模なカテゴリ・粒度の異なるカテゴリで
の実験
30
© Copyright 2024 ExpyDoc
