知識グラフのリンク予測におけるGANを用いたネガティブサンプルの生成

Transcript

1. リンク予測におけるGANを用い たネガティブサンプルの生成 studio_graph3
   
2. リンク予測におけるGANを用いた
 ネガティブサンプルの生成
   
3. リンク予測におけるGANを用いた
 ネガティブサンプルの生成
    ! ! !
4. 今日の発表
   
5. いっぱい喋ります
   
6. 数式(そこそこ)
 出てきます
   
7. 実務には(あんまり) 役立ちません
   
8. !"# (を目指す)
   
9. もくじ • リンク予測 • 知識グラフ • ネガティブサンプリング • GANを用いたネガティブサンプリング
   
10. リンク予測 • ネットワーク構造はさまざまな
 システムを示すのに有効 ‣ SNS，交通網，電話網，
 タンパク質の結合 • ネットワーク構造から
 データマイニングしたい • ノード同士にリンクが
 存在しているかどうか ‣ 新たなノード同士についてリンク を予測
     ノード リンク ノード リンク ？
11. リンク予測の定式化 • グラフ構造 とする • ノード 間のリンクを と表 す • このような に対してスコアリング 関数 を定めることにより
 を予測するタスク
     G = (V, E) x, y ∈ V e x,y ∈ E x, y s c (x, y) p(e x,y |(x, y))
12. リンク予測手法の種類 • 類似度に基づいた手法 ‣ 似ているノード同士はリンクを持つ • 類似度に基づかない手法 ‣ 分類モデルでリンクの存在を直接予測 ‣ 行列の因子分解を利用
    
13. 実世界における知識 • AIにおける主要な話題 • さまざまなAIのタスクで有用 ‣ 質問応答, 知識推論, web検索 • 伝統的な知識ベース ‣ Wordnet (Miller, 1995), Freebase (Bollacker+, 2008) ‣ 抽象的かつ論理的 • すべてをカバーするのは大変 • 人手による構築が大変 ‣ 関係抽出というタスクも存在する
    
14. 知識グラフってなに？ • 知識ベースをグラフ にする ‣ 計算のため • 人間に理解しやすい
     Italian Pasta Pizza Arrabbiata Dish Japanese Sushi Ramen Tonkotsu Carbonara Miso Margueritte Drink Plant Object
15. 知識グラフにおけるリンク予測 • 知識グラフは (head, relation, tail) の triplet (三つ組) で表される ‣ 例: (Pasta, is_a, dish) • 訓練データに登場しないペアについても 予測 ‣ 存在するペアたちから学習する • 知識グラフを連続ベクトル特徴空間に ‣ 知識グラフを数値計算可能に ‣ 意味的な類似性を包含したい
     知識ベース
 データセット Train Test Triplet→Vector モデル Train Predict 分割
16. リンク予測の種類
     (h,r,t) に対するスコア関数 TransE TransH TransR TransD Structured Embedding Unstructured Model Single Layer Model s c (h , r, t) = |h + r − t| L1/L2 s c (h , r, t) = |h ⊥ + r − t ⊥ | L1/L2 , (h ⊥ = h − w⊤ r hw r , t ⊥ = t − w⊤ r tw r ) s c (h , r, t) = |M r h + r − M r t| L1/L2 M rh = r p h⊤ p + I M rt = r p t⊤ p + I s c (h , r, t) = M r,h h − M r,t t s c (h , r, t) = − u⊤ r tanh (M r,h h + M r,t t + b r) s c (h , * ,t) = |h − t|
17. ネガティブサンプリング • データセットは正例しか保持し ていない • 訓練する時 ‣ 訓練データから得られた正例 ‣ 人手で作られた負例 • マージンに基づいた
 ランキングのlossを最小化する
     正 負 ↑スコア高 ↓スコア低
18. 人手で作られた負例の問題点 • (head entity, relation, tail entity)
     head または tail のどちらかをランダムに入れ替える 正 負 決定境界(のようなもの) ↓こういう決定境界から遠い負例を生成 →決定境界に近い負例がほしい
19. ネガティブサンプル生成の例 • (Steve Jobs, FounderOf, Apple Inc.) • ランダムにサンプリングすると: ‣ (London, FounderOf, Apple Inc.) ‣ (baseball, FounderOf, Apple Inc.) • 訓練時に有効ではない • 場合によってはモデルの収束の邪魔になる
     Even not a human!!
20. ネガティブサンプリングの難しさ • データセットそれぞれに強く依存する ‣ WordNet - ほとんどが一般的な単語で構成 - それらを語彙的や意味的な関係
 でつないでいる ‣ Freebase - ほとんどが固有名詞 - つよく型付けされた会計でつながれている
     Type エンティ ティ数 関係の数 三つ組の 数 WN11 38,696 11 112,581 FB15k 14,591 1,345 483,442
21. WN11とFB15kの三つ組の例
     Head Relation Tail address part_of letter WN11 line type_of text health_problem has_instance infection star_wars_episode_IV produced_by george_lucas FB15k alexandre_dumas people_profession writer professor profession_people albert_einstein
22. ネガティブサンプリングの技術 • 正例を使うもの ‣ Random sampling (ランダム),
 Corrupting positive instances (正例を壊して) • 型の情報を使うもの ‣ Typed sampling, (型を利用する)
 Relational sampling (関係性を利用する) • ネガティブサンプリングモデルを使うもの ‣ Nearest neighbor sampling, (最近傍を持ってくる)
 Near miss sampling (↑を改善したもの)
    
23. GANを元にした
 ネガティブサンプリング • (Wang+, 2018) • 知識表現におけるネガティブサンプリ ング性能の向上をGANで行う • Discriminator ‣ 3つ組が存在するかどうかを識別 ‣ 生成された3つ組も使って学習 • Generator ‣ 学習に有効なネガティブサンプルを生成 • 敵対的学習
     Dataset Discriminator Generator Pos Neg Score of triplet
24. GAN モデルの全体
     •　•　•　•　• Entity Relation + •　•　•　•　• ReLU Softmax Generator Discriminator Neg Triplet Pos Triplet •　• •　• Loss / Reward Neg Triplets Reward Score
25. Discriminator • 入力 ‣ 正例と負例のtriplet • 出力 ‣ tripletのスコア • 構成 ‣ それぞれのリンク予測モデル • Max Margin Loss関数 ‣
     l(h , r, t) = max{0,( f r (h ′, t′) − f r (h , t) + γ)} Discriminator Neg Triplet Pos Triplet •　• •　• Loss / Reward Score
26. Generator • 入力 ‣ 正例から得られたエンティティと関係性 • Output ‣ 適切なネガティブサンプル • Structure ‣ 2層のパーセプトロン ‣ ReLU and Softmax for activation function • 方策勾配法を用いて学習 • 報酬 ‣ •
     R = tanh(f r (h , t) − f r (h ′, t′) + γ)) •　•　•　•　• Entity Relation + •　•　•　•　• ReLU Softmax Generator ∇ θ J(θ) = ∇ θ log p(e|(h , r, t), z; θ) ⋅ R
27. 結果
    
28. 提案手法の問題点 • モデルが大きくなる ‣ GANを用いることにより収束がやや困難に ‣ 精度は出るが計算時間がかかる • 既存のネガティブサンプリング手法から得ら れた知見 ‣ 全エンティティと関係の組についてスコアを 計算
    
29. まとめ • リンク予測というタスクがある • データセットにつよく依存する • ネガティブサンプリングをうまくやる必要が ある • GANを用いて適切なネガティブサンプルを生 成することができた ‣ すべてでうまくいくというわけではない
    
30. 参考文献 • Ictor Mar Inez, Fernando Berzal, and Juan-carlos Cubero. A Survey of Link Prediction in Complex Networks. ‣ https://arxiv.org/abs/1010.0725 • PeiFeng Wang, Shuangyin Li, and Rong Pan. Incorporating GAN for negative sampling in knowledge representation learning. ‣ https://aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16094 • Bhushan Kotnis and Vivi Nastase. Analysis of the impact of negative sampling on link prediction in knowledge graphs. ‣ https://arxiv.org/abs/1708.06816