Sansan Tech Blog

Sansanのものづくりを支えるメンバーの技術やデザイン、プロダクトマネジメントの情報を発信

【ML Tech RPT.】第22回 構造に関連する機械学習を学ぶ(8) ~グラフ その4~ Knowledge Graph

f:id:sansan_yoshimura:20210222095528p:plain DSOC 研究員の吉村です. 最近はR&Dの他のメンバーが食べていたのに感化されて, BASE FOOD という完全食のパンを毎朝食べています. 特にその中でもメープル味がお気に入りで, 非常に美味しく食べやすいです.

さて, 今回は Heterogeneous Graph の一つの表現の方法である Knowledge Graph に焦点を当てていきます. この両者はほぼ同じものを表しますが, 数式における Graph の表現方法の定義や, 研究対象の範囲が異なるようです.

はじめに

Knowledge Graph (KG) は, Knowledge Base をグラフ構造により表したものです. KG においては, 大きく次の二つの研究の方向性があります. 一つ目が, KG を活用する研究, もう一つが KG の作成/拡張する研究です. 加えて, これら二つの基盤となる研究として KG の表現学習 (Knowledge Representation Learning; KRL) についても盛んに研究されています. 活用, 作成/拡張の両面において, KRL は重要な技術となります. これらについては, 基本的には静的な KG を考えていますが, 昨今では知識や事実が時間変化の影響を受けるような動的な場合に対する研究として Temporal Knowledge Graph などもあります. 今回は, 基盤となる KRL についての概要のみを扱っていきます.

KG の定義

KG は  \mathcal{G}= \left\{ \mathcal{E}, \mathcal{R}, \mathcal{F} \right\} で定義されます. ここで,  \mathcal{E}, \mathcal{R}, \mathcal{F} はそれぞれ, entity (e.g. "太宰治", "走れメロス" など), relation (e.g. "Wrote" など), そして, facts (e.g. ("太宰治", "Wrote", "走れメロス") など) の集合を表します[*1]. これまでのブログで書いてきたグラフの表記と照らし合わせると, entity は頂点, relation は枝に対応します. KG を考える上で重要なのがこの facts です. facts は二つの entity の間の関係を表現するもので,  (h, r, t) \in \mathcal{F} (ただし  h, t \in \mathcal{E},  r \in \mathcal{R}) で定義されます. この  h, t はそれぞれ head と tail を表してます.

Knowledge Representation Learning

Knowledge Representation Learning (KRL) とは, 簡単に言うと Knowledge Graph 内の entity と relation のベクトル表現を得るための学習についての研究分野です. entity と relation については, それぞれ同じ空間で扱う研究 (e.g. TransE [*2]) もありますし, entity と relation を別の空間で扱う研究 (e.g. TransR [*3]) もあります. ちなみに, KRL の評価には, リンク予測, 三つ組分類 (triple classification) などの様々な downstream のタスクが用いられます. ここでいう三つ組分類は, facts の一つの要素  (h, r, t) が真か偽かを分類するタスクです. さて, ここでは KRL の各手法の特徴を表す 4 つの観点について見ていきます. [S. Ji et. al. 2020.] によれば, KRL は次の 4 つの側面に分類できると言われています.

  1. entity と relation を表現する空間
  2. facts のもっともらしさを測定するスコアリング関数
  3. 関係を表現/学習するためのエンコーディングモデル
  4. 埋め込みを行う際に組み込まれる補助情報

ここからは, この 4 つについてそれぞれ基本となる手法を見ていきます.

entity と relation を表現する空間

もっともオーソドックスなものとしては Euclidean space を用いる手法があります [A. Bordes et.al. 2013.]. entity と relation が同じ空間で表されるとした時に, 三つ組  (h, r, t) のそれぞれの要素に対応する分散表現を  \bf{h}, \bf{r}, \bf{t} とすると, Euclidean space 上で  \bf{h} + \bf{r} \approx \bf{t} が成立するように学習するのが, TransE という手法です. [S. Ji et. al. 2020.] によれば, 単純な Euclidean space を用いる以外にも, 複素ベクトル空間を用いるもの (e.g. ComplEx [*4]), ガウス分布空間を用いるもの (e.g. KG2E [*5]), 球や超平面を用いるもの (e.g. ManifoldE [*6]) などが, また, 変わり種としては, 双曲空間 (e.g. MuRP [*7])やトーラス空間 (e.g. TorusE [*8])を使うものなどもあるようです.

それぞれの空間を用いる嬉しさを簡単に説明します. ComplEx では複素ベクトル空間を利用することで, 計算量が軽いエルミート積演算だけで, 対象関係 (e.g. IsSimilarTo など) と反対象関係 (e.g. FatherOf, OlderThan など) を扱えるようになります. KG2E ではガウス分布空間を用いることで, facts の三つ組を真か偽かだけではなく不確実性を持って扱うことができるようになります. [H. Xiao et.al. 2016.] では, KRL においてリンク予測の性能が高いことが重要とした上で, Euclidean space だと学習が不良設定になる一方で, 多様体空間による制約をかける ManifoldE ではほぼ良設定問題にできることがモチベーションとなっています. MuRP では双曲空間を用いることで, より正確で簡単な形で階層構造の情報を分散表現に入れることができます. [T. Ebisu, and R. Ichise 2018.] では, Euclidean space を用いる場合に重要となる正則化が埋め込みを歪めることを指摘した上で, 正則化が不要になる適切な空間の条件が "コンパクトなリー群" であるとして, その中で簡単に実現できるトーラス空間を用いた TorusE を提案しています.

facts のもっともらしさを測定するスコアリング関数

基本的には次の二つが考えられます. 一つが距離に基づくもの (Distance-Based Scoring Function)で, もう一つが類似度に基づくもの (Similarity-Based Scoring Function)です. Distance-Based は射影行列を使ったりはするものの, 基本的には head と tail の二つの entity の距離をスコアリング関数として用います (e.g. TransE [S. Ji et. al. 2020.]). 一方で, Similarity-Based では, 多少のバリエーションはあれど, head と tail の cosine 類似度のようなものを用いてスコアリング関数とします (e.g. ANALOGY [*9]).

関係を表現/学習するためのエンコーディングモデル

分散表現を得るためのモデルのアーキテクチャの側面です. [S. Ji et. al. 2020.] では次の 7 つの種類が挙げられています.

  1. 線形/双線形モデル
  2. (行列/テンソル) 分解モデル
  3. NNs
  4. CNNs
  5. RNNs
  6. Transformers
  7. GNNs

これらは, 基本的には計算量と表現力のトレードオフを鑑みて, 適切なものを選択することになります.

埋め込みを行う際に組み込まれる補助情報

ここでは entity と relation を埋め込む際に別の情報があるときにそれも合わせて分散表現を学習する場合を考えます. 補助情報として考えられるものとしては, テキスト情報や, 画像情報 があります.

テキスト情報を用いるものとしては, TransE を拡張した Description-Embodied Knowledge Representation Learning (DKRL) [*10] などがあります. DKRL は KG を構成する entity には通常それを説明する記述があるにもかかわらず, それが十分に利用できていなかったところを解決する手法として提案されており, Zero-Shot のシナリオにおいても優れたパフォーマンスが示されています.

画像情報を用いるものとしては, Image-embodied Knowledge Representation Learning (IKRL) [*11] などがあります. IKRL は二段階の手法で, 最初のステップで全ての entity に対応する画像の分散表現を得るためのエンコーダを学習し, 次のステップでその画像の分散表現を Attention を用いて KG の分散表現の取得のためのモデルに適用します.

まとめ

今回は, Heterogeneous graph の一つの表現としての Knowledge Graph を扱いました. Knowledge Graph については, それを利用する研究と作成/拡張する研究の二つに分かれることを説明した上で, それらの基盤となる Knowledge Representation Learning (KRL) の基本となる部分をまとめました. 長く続いてきたグラフのトピックと, 構造に関連する機械学習の紹介は一旦ここまでで終了です. 次回からはまた別のトピックを紹介していこうと思いますので, ご期待ください. それでは, 次回も引き続きお付き合いください!


▼【ML Tech RPT. 】シリーズ buildersbox.corp-sansan.com

*1:S. Ji, S. Pan, E. Cambria, P. Marttinen, P. S. Yu, "A Survey on Knowledge Graphs: Representation, Acquisition and Applications," arXiv, in 2020.

*2:A. Bordes, N. Usunier, and A. G.-Duran, "Translating Embeddings for Modeling Multi-relational Data," NIPS, in 2013.

*3:Y. Lin, Z. Liu, M. Sun, Y. Liu, and X. Zhu, "Learning Entity and Relation Embeddings for Knowledge Graph Completion," AAAI, in 2015

*4:T. Trouillon, J. Welbl, S. Riedel, E. Gaussier, and G. Bouchard, "Complex Embeddings for Simple Link Prediction," ICML, in 2016.

*5:S. He, K. Liu, G. Ji, and J. Zhao, "Learning to Represent Knowledge Graphs with Gaussian Embedding," CIKM, in 2015.

*6:H. Xiao, M. Huang, X. Zhu, "From One Point to a Manifold: Knowledge Graph Embedding for Precise Link Prediction," IJCAI, in 2016.

*7:I. Balazevic, C. Allen, and T. Hospedales, "Multi-relational Poincare Graph Embeddings," NeurIPS, 2019.

*8:T. Ebisu, and R. Ichise, "TorusE: Knowledge Graph Embedding on a Lie Group," AAAI, 2018.

*9:H. Liu, Y. Wu, and Y. Yang, "Analogical Inference for Multi-relational Embeddings," ICML, in 2017.

*10:R. Xie, Z. Liu, J. Jia, H. Luan, and M. Sun, “Representation Learning of Knowledge Graphs with Entity Descriptions,” AAAI, in 2016.

*11:R. Xie, Z. Liu, H. Luan, and M. Sun, “Image-Embodied Knowledge Representation Learning,” IJCAI, in 2017.

© Sansan, Inc.