WWW-2015採択論文

能動学習による多関係データセットの構築
梶野 洸1, 岸本 章宏2, Adi Botea2,Elizabeth Daly2, Spyros Kotoulas2
1. 東京大学
2. IBM Research - Ireland
1手作業での多関係データセット構築支援という新たな枠組みを提案■ 研究対象: 手作業での多関係データセット構築
テキストからの自動抽出が困難なデータが存在
Q: 効率的に構築するにはどうしたらよいか?

■ 提案: 能動学習 + 多関係データ学習
能動学習により人間へのクエリ数を削減
多関係データ
1. モデルがデータを選択
モデル
ラベルを要求人間

2. ラベルを返送
3. データセットを更新・モデルの再学習
2 /29

■ 目次
□ 問題設定:• 多関係データとその応用• 2つの定式化:– データセット構築問題– 予測モデル構築問題□ 提案手法 (AMDC):• 能動学習を用いた枠組み• 多関係データ学習□ 実験3 /29

■ 目次
□ 問題設定:• 多関係データとその応用• 2つの定式化:– データセット構築問題– 予測モデル構築問題□ 提案手法 (AMDC):• 能動学習を用いた枠組み• 多関係データ学習□ 実験4 /29

多関係データセットは、二値ラベル付き三つ組の集合■ 多関係データ: 三つ組 + ラベル□ 三つ組: t = (i, j, k)• 主体: i, j ∈ E

部分集合
犬動物

同じ

• 関係: k ∈ R

部分集合
人間

□ ラベル:• t が正例 ⇔ 主体 i が主体 j に対して関係 k にある• t が負例 ⇔ 主体 i が主体 j に対して関係 k にない□ 多関係データセット: (Δp, Δn)Δp = {t ∈ Δ | t が正例}, Δn = {t ∈ Δ | t が負例}
（仮定: |Δp| ≪ |Δ|, ラベルなし三つ組も存在）
全三つ組の集合

|E|
|E|

|R|

5 /29

人によるアノテーションが必要なデータが存在■ 手作業によるデータセット構築の動機□ 知識ベース: 人間の知識を多関係データで表現
データセット

正例の例

WordNet [Miller, 95](dog, canine, synset), (dog, poodle, hypernym)

ConceptNet [Liu+,04](saxophone, jazz, UsedFor),(learn, knowledge, MotivatedByGoal)

ポイント: 常識的な知識は文書に明示的には現れない→ 自動抽出が難しい□ 生物学のデータベース:
相互作用

タンパク質

参加

DNA

→ ラベル付けには実験が必要

細胞周期6 /29

データセットの用途に応じて2つの定式化をする■ 2つの定式化□ 入力:

・ 誤りなし・ B 回クエリ可能

主体の集合 E, 関係の集合 R, オラクル O: Δ→{正例, 負例}□ 問題 1: データセット構築問題
目標: なるべく多くの正例を収集□ 問題 2: 予測モデル構築問題
目標: 多関係データモデル M: Δ → R を学習（出力: 正例らしさ）※ モデルが欲しい場合、より直接的な定式化
7 /29

■ 目次
□ 問題設定:• 多関係データとその応用• 2つの定式化:– データセット構築問題– 予測モデル構築問題□ 提案手法 (AMDC):• 能動学習を用いた枠組み• 多関係データ学習

□ 実験
8 /29

AMDC はラベル取得と学習を B 回繰り返す■ Active Multi-relational Data Construction (AMDC)□ 概要:
現状のデータセットでモデルを学習
多関係データ
1. モデルがデータを選択
モデル
ラベルを要求人間

2. ラベルを返送
3. データセットを更新・モデルの再学習

訓練データ (Δp, Δn)
9 /29

AMDC はラベル取得と学習を B 回繰り返す■ Active Multi-relational Data Construction (AMDC)□ 概要:
AMDC は予測スコア st を計算可能
0より 大きい / 小さい st ⇔ t を 正例 / 負例 と予測多関係データ
1. モデルがデータを選択
モデル
ラベルを要求人間

2. ラベルを返送
3. データセットを更新・モデルの再学習

訓練データ (Δp, Δn)
10 /29

AMDC はラベル取得と学習を B 回繰り返す■ Active Multi-relational Data Construction (AMDC)□ 概要:
予測スコア st を用いて クエリスコア qt を計算
qt が小さい ⇔ t のラベルが欲しい
多関係データ
1. モデルがデータを選択
モデル
ラベルを要求人間

2. ラベルを返送
3. データセットを更新・モデルの再学習

訓練データ (Δp, Δn)
11 /29

AMDC はラベル取得と学習を B 回繰り返す■ Active Multi-relational Data Construction (AMDC)□ 概要:

多関係データ
1. モデルがデータを選択
モデル
ラベルを要求人間

2. ラベルを返送
3. データセットを更新・モデルの再学習

訓練データ (Δp, Δn)
12 /29

AMDC を構成する2つのスコアを紹介する■ Active Multi-relational Data Construction (AMDC)□ 詳細:• クエリスコア qt• 予測スコア st （多関係データモデル）

多関係データ
1. モデルがデータを選択
モデル
ラベルを要求人間

2. ラベルを返送
3. データセットを更新・モデルの再学習
13 /29

AMDC を構成する2つのスコアを紹介する■ Active Multi-relational Data Construction (AMDC)□ 詳細:• クエリスコア qt• 予測スコア st （多関係データモデル）

多関係データ
1. モデルがデータを選択
モデル
ラベルを要求人間

2. ラベルを返送
3. データセットを更新・モデルの再学習
14 /292つの定式化それぞれに対しクエリスコアを設計■ AMDC (1/2): クエリスコア qt (t ∈ Δ)
qt が小さいほどデータセット構築に有用
入力: 予測スコア stst > 0 (< 0)

正例 (負例) と予測

出力:• 正例スコア (問題 1): qt := - st
正例と予測された三つ組 (st が大)を選択• 不確実スコア (問題 2): qt = |st |予測が不確実な三つ組（境界上）を選択※ クエリスコアを切り替えることで2つの問題設定に対応
15 /292つの定式化それぞれに対しクエリスコアを設計■ AMDC (1/2): クエリスコア qt (t ∈ Δ)
qt が小さいほどデータセット構築に有用
入力: 予測スコア stst > 0 (< 0)

正例 (負例) と予測効果を実験で検証

出力:• 正例スコア (問題 1): qt := - st
正例と予測された三つ組 (st が大)を選択• 不確実スコア (問題 2): qt = |st |予測が不確実な三つ組（境界上）を選択※ クエリスコアを切り替えることで2つの問題設定に対応
16 /29

AMDC を構成する2つのスコアを紹介する■ Active Multi-relational Data Construction (AMDC)□ 詳細:• クエリスコア qt• 予測スコア st （多関係データモデル）

多関係データ
1. モデルがデータを選択
モデル
ラベルを要求人間

2. ラベルを返送
3. データセットを更新・モデルの再学習
17 /29

過学習防止のために制約を導入■ AMDC (2/2): 多関係データモデル□ ベース: RESCAL [Nickel+,11]• モデル:– ai ∈ RD: 主体 i の潜在表現（ベクトル）– Rk ∈ RD D : 関係 k の潜在表現（行列（対称とは限らない））• 予測スコア: st = aiT Rk aj
New大きい / 小さい st ⇔ t は 正例 / 負例

□ 新たな制約: |ai| = 1, Rk = 回転行列
初期段階（ラベル数が少ない）の学習を安定化(→ 実験で検証)
18 /29

ランキングベースの目的関数を利用■ AMDC (2/2): 最適化問題
s(正例) > s(非正例)s(non-neg) > s(neg)s(pos) > 0s(neg) < 0□ アルゴリズム: SGD□ パラメタ:,□ ハイパーパラメタ: γ, γ’, Cn, Ce, D
毎反復、検証用データセットを用いて決定
19 /29

ランキングベースの目的関数を利用■ AMDC (2/2): 最適化問題
s(正例) > s(非正例)s(non-neg) > s(neg)s(pos) > 0 毎反復で得られるラベルのs(neg) < 0□ アルゴリズム: SGD

多くは負例・ラベル無しと負例を区別していない□ パラメタ:,・正例 / 負例 の境界が 0 となるとは限らない□ ハイパーパラメタ: γ, γ’, Cn, Ce, D
毎反復、検証用データセットを用いて決定
20 /29

ランキングベースの目的関数を利用■ AMDC (2/2): 最適化問題
s(正例) > s(非正例)s(非負例) > s(負例)s(pos) > 0s(neg) < 0□ アルゴリズム: SGD
・ラベル無しと負例を区別していない□ パラメタ:,・正例 / 負例 の境界が 0 となるとは限らない□ ハイパーパラメタ: γ, γ’, Cn, Ce, D
毎反復、検証用データセットを用いて決定
21 /29

ランキングベースの目的関数を利用■ AMDC (2/2): 最適化問題
s(正例) > s(非正例)s(非負例) > s(負例)s(正例) > 0s(負例) < 0□ アルゴリズム: SGD
・ラベル無しと負例を区別していない□ パラメタ:,・正例 / 負例 の境界が 0 となるとは限らない□ ハイパーパラメタ: γ, γ’, Cn, Ce, D
毎反復、検証用データセットを用いて決定
22 /29

毎反復、複数のモデルをSGDで最適化し、最良のものを選択■ AMDC (2/2): 最適化問題
s(正例) > s(非正例)s(非負例) > s(負例)s(正例) > 0s(負例) < 0□ アルゴリズム: SGD□ パラメタ:,□ ハイパーパラメタ: γ, γ’, Cn, Ce, D
毎反復、検証用データセットを用いて決定
23 /29

毎反復、複数のモデルをSGDで最適化し、最良のものを選択■ AMDC (2/2): 最適化問題
効果を実験で検証

s(正例) > s(非正例)s(非負例) > s(負例)s(正例) > 0s(負例) < 0□ アルゴリズム: SGD□ パラメタ:,□ ハイパーパラメタ: γ, γ’, Cn, Ce, D
毎反復、検証用データセットを用いて決定
24 /29

■ 目次□ 問題設定:• 多関係データとその応用• 2つの定式化:– データセット構築問題– 予測モデル構築問題□ 提案手法 (AMDC):• 能動学習を用いた枠組み• 多関係データ学習□ 実験25 /29

3つの改良点の貢献を検証する■ 実験□ 目的: 3つの改良点の貢献を2つの問題設定で検証• クエリスコア(vs. AMDC + random query)• Neg AUC-loss(vs. AMDC - neg-AUC)• RESCAL に加えた制約(vs. AMDC - constraints)□ データセット:
既に与えられているラベルを用いてオラクルをシミュレート
#(主体)

#(関係)

#(正例)

#(負例)

Kinships [Denham, 73]

104

26

10,790270,426

Nations [Rummel, 50-65]

125

57

2,565

8,626

UMLS [McCray,03]

135

49

6,752

886,273

26 /29

AMDC はベースラインと比べ 2.4 – 19 倍の正例を収集■ 実験 (1/2): データセット構築問題評価指標: %(AMDC が収集した正例ラベル)□ クエリスコア: Random の 2.4 – 19 倍の正例を収集□ Neg AUC loss: 負例が多い場合に有効 (K, U)□ 制約: 性能が下がることもある

Completion rate

0.350.300.35

Full AMDC

0.30

w/o constraints

0.25
0.20
0.15

0.20
0.15

w/o neg-AUC

0.10

0.10

2000 4000 6000 8000 10000 12000 14000 16000#(Queries)

Kinships

0.00
0Random

0.35
0.30

AMDC
AMDC rand
AMDC pos only
AMDC no const

0.25
0.20
0.15
0.10

0.05

0.05
0.00
00.25

0.40

AMDC
AMDC rand
AMDC pos only
AMDC no const

Completion rate

0.40

AMDCAMDC rand
AMDC pos only
AMDC no const

Completion rate

0.45

0.05200400

600 800 1000 1200 1400 1600#(Queries)

Nations

0.0002000 4000 6000 8000 10000 12000 14000 16000#(Queries)

UMLS

10 trials, (Q, q) = (105, 103) ((2 103,102) for Nations)

27 /29

AMDC はほぼ常に最良の予測スコアを達成■ 実験 (2/2): 予測モデル構築問題
評価指標: ROC-AUC□ クエリスコア: Random と比べ、有意に高いAUC (K, U)□ Neg AUC loss: どのデータでも有効□ 制約: 過学習を防ぎ、高い予測性能を達成
Random

0.9

0.8

0.8

0.7
0.6
0.5
0.4
0w/o constraints
w/o neg-AUC
2000 4000 6000 8000 10000 12000 14000 16000#(Queries)

Kinships

1.0

1.0

ROC-AUC

ROC-AUC

0.9

Full AMDC

AMDC
AMDC rand
AMDC pos only
AMDC no const

0.9
0.8

ROC-AUC

1.0

0.7
0.6
AMDC
AMDC rand
AMDC pos only
AMDC no const

0.5
0.4
0200

400

600 800 1000 1200 1400 1600#(Queries)

Nations

0.7
0.6
0.5

AMDC
AMDC rand
AMDC pos only
AMDC no const

0.4
0.3
0

2000 4000 6000 8000 10000 12000 14000 16000#(Queries)

UMLS

10 trials, (Q, q) = (105, 103) ((2 103,102) for Nations)

28 /29

手作業による多関係データセット構築問題を導入した■ 結論□ 手作業での多関係データセット構築は未だに重要• ある種のデータは人によるアノテーションが必要• クラウドソーシングを通じて依頼可能□ AMDC = 能動学習 + 多関係データ学習
RESCAL を元に、データが少ない時の学習を安定化□ 3 つの工夫により性能向上することを確認• 能動学習によりコストを大幅に削減• RESCALに加えた制約により過学習を防止• 負例が多い場合に neg AUC-loss が有効
29 /29