その中でも、埋め込み技術に関して、我々リサーチチームは先日、論文 Hyperbolic Disk Embeddings for Directed Acyclic Graphs をarXiv に公開しました。また、先日のイベント scouty Knowledge Graph and Embedding Night でその内容を紹介しました。
この論文では、推移的な関係性を持つデータの最新の埋め込み手法を統一的に扱うフレームワークである Disk Embedding を提案し、さらに双曲空間における Disk Embedding である Hyperbolic Disk Embedding を提案しました。
理論的な詳細は本論文とスライドを参照いただくとして、ここではまず、背景として最新の埋め込み手法を概観し、その後に論文のアウトラインを紹介したいと思います。
背景
自然言語処理における単語の1-hot ベクトルのように高次元・スパースなベクトルを低次元の実数行列として表現する手法は、機械学習における非常に様々な分野で注目を集めています。
word2vec [Mikolov, 2013] に代表されるこのような埋め込み手法は、「離散的な点の集合を、その点と点の関係性を保ったまま連続な空間の中に埋め込む」手法であると言えます。
ここで、空間とは、集合 \(S\) と、 \(S\) の上で定義された数学的な構造 \(\mathcal{X}\) との組 \((S,\mathcal{X})\) と理解できます。たとえば、ユークリッド空間 \(\mathbb{R}^n\) は、位相構造(連続性に関する構造)、距離構造(ユークリッド距離など)、代数構造(ベクトルの加減算、スカラー倍)、順序構造など、様々な構造を持っています。
機械学習では、様々なデータに現れる様々な関係性に着目し、それらをいかに綺麗に埋め込むことができる空間を考えるかによって、様々な埋め込み手法が提案されています。
このように、データ間の関係性と空間に着目して、近年の埋め込み手法を見ていきましょう。
word2vec
word2vec [Mikolov, 2013] (解説記事) は、文章に現れる単語間の共起関係を(shifted) PMI で表し、これをユークリッド空間 \(\mathbb{R}^n\) の内積として表現する手法であると言えます [Levy, 2014]。
すなわち、単語 \(i\) と \(j\) のPMI を \(\mathrm{PMI}(i,j)\) とすると、これをユークリッド空間の内積として、
\(\langle \mathbf{v}_i, \mathbf{v}_j \rangle \approx \mathrm{PMI}(i,j)\)
さらに、点と点の内積構造を保つということは、角度や距離を含む点と点の位置関係が定まるということになります。これにより、単語のベクトル表現の間で以下のような「演算」のようなことが可能となります。
\(\displaystyle \mathbf{v}_\mathrm{queen} \,\approx\, \mathbf{v}_\mathrm{king} - \mathbf{v}_\mathrm{man} + \mathbf{v}_\mathrm{woman} \)
Order Embedding
埋め込む際に着目する構造は、内積(や距離)だけではありません。
単語や文章の含意関係などでは、「AはBの抽象化」や、「AはBの具体例」のように、方向を持った関係性があります。これらを、半順序構造をもつ空間への埋め込みとして表現したのが Order Embedding [Vendrov, 2016] です。
この手法では、単語や文章などのエンティティ間の上下関係 \(\succeq\) を、次のようなユークリッド空間における reversed product order (逆直積順序) によって表現します。
\(\displaystyle x \succeq y \, \Longleftrightarrow \, u_x^{(i)} \leq u_y^{(i)} \; ( i=1, \cdots, n)\)
これを用いることによって、例えば、「馬と人と象の写真」と「馬と人と犬の写真」から、共通部分である「馬と人が写ったの写真」を検索するような演算が可能になります。
[Vendrov, 2016]
Poincaré Embedding
Poincaré Embedding[Nickel, 2017] は、以前、当 AI Labでも取り上げました。
Poincaré Embedding では、埋め込む空間として、双曲空間を用いることにより、ユークリッド空間には埋め込むことができない、指数的にノードが増えていくような木構造を、その距離構造を保ったまま埋め込むことができます。
双曲空間への木の埋め込みの可視化の例 http://nunuki.hatenablog.com/entry/2018/12/15/055136
Hyperbolic Entailment Cones
Hyperbolic Entailment Cones [Ganea, 2018] は、上記の Order Embedding と Poincaré Embedding を組み合わせたような手法となっています。
この手法では、双曲空間のポアンカレ円板モデルの中心から外側に広がる円錐によって表される半順序構造の中に、推移的関係を埋め込んでいます。
[Ganea, 2018]
| 名前 | 関係性 | 空間 | 着目する構造 |
|---|---|---|---|
| word2vec [Mikolov, 2013] | 共起関係 | ユークリッド空間 | 内積(代数)構造 |
| Order Embedding [Vendrov, 2016] | 推移的関係 | ユークリッド空間 | 順序構造 |
| Poincaré Embedding [Nickel, 2017] | 共起関係・推移的関係 | 双曲空間 | 距離構造 |
| Hyperbolic Entailment Cones [Ganea, 2018] | 推移的関係 | 双曲空間 | 順序構造 |
DAGの埋め込みとDisk Embedding
さて、ここから、冒頭の論文 "Hyperbolic Disk Embeddings for Directed Acyclic Graphs" の内容について説明していきます。本論文で提案する Disk Embedding は、上述の Order Embeddingsや Hyperbolic Entailment Cones のように、推移的関係を順序構造の中に埋め込む手法を一般的に扱うためのフレームワークとなっています。
非循環有向グラフ(DAG)と半順序
単語の is-a 関係や、文章の含意関係などは、非循環有向グラフ(DAG)で表すことができます。たとえば、単語の is-a 関係(概念の包含関係)の場合、それぞれの単語ノードとし、B is Aが成り立つ(BはAの一種である)場合にはAからBへの(有向)エッジがあるといった具合です。
この場合、単語AがBに含まれ、BがCに含まれる時、AはCに含まれるという関係性(推移的関係)が成り立っています。すなわち、B is A という関係は、DAGの到達可能性(AからBに、有向パスを辿って到達可能か)という関係性として表されます。
このような推移的関係は半順序と呼ばれる順序構造に対応しています1。
ここで、半順序(解説記事)とは、任意の異なる2点x,y について、その関係が「xよりもyが大きい」「yよりもxが大きい」「xとyは比較不能」のいずれかであるような二項関係です。
半順序をもつ空間において、ある点 x を考えると、空間全体は「xよりも大きい点の領域」「xよりも小さい点の領域」「xと比較不可能な点の領域」の3つの領域に分割されます。
特に、xよりも大きい領域は upper cone (または upper closure)、小さい領域は lower cone (lower closure) と呼ばれ、特に、回転対称性を仮定すると、これらは円錐の形になります。
Disk Embedding
これまでの議論をまとめると、以下の4つは全て同じことを指しているということがわかります。
- 単語の is-a 関係や文章の含意関係
- DAG の到達可能性
- 半順序
- lower cones の包含関係
さらにこの考えを推し進め、下図のように、lower cones をある平面で輪切りにした切り口の図形(円板)を考えると、上述の関係性はさらに、
- lower cones の切り口の円板の包含関係
と同値であることがわかります。
このように、推移的な関係を、円板の包含関係として表現する方法を Disk Embedding と呼んでいます。
例えば、2次元の(ユークリッド)平面を考えると、ちょうど、円のみからなるオイラー図によって包含関係を表現することに対応しています。
\(l := d(\mathbf{x},\mathbf{y}) - r_x + r_y \leq 0\) (1)
それ以外(負例)の場合には、 \(l\) を大きくするように最適化を行うことで、適切な埋め込み表現 \({\mathbf{x}, r_x }\) を学習することができます。
具体的には、次のような目的関数を最小化します。
\(\displaystyle L=\sum_{(i,j) \in \mathcal{T}} \max(0, l_{ij}) + \sum_{(i,j) \in \mathcal{N}} \max(0,\mu - l_{ij})\) (2)
ここで、式(1)の関係について、半径 \(r_x, r_y\) の値は、必ずしも正の値である必要がない点に注意してください。つまり、仮想的に「負の半径をもつ円板」を考えることができるということです。さらに、式(1)のx とyを交換し、半径 \(r_x, r_y\) の符号を反転させても、 \(l\) の値が変わらないという性質(反対称性)があります。これは、「全ての半径を負にするということは、順序関係を反転させることに対応する」ということを意味しています。
既存手法が Disk Embedding の一種であること
上述のように、Disk Embedding を用いることで、DAG 円板の集合として埋め込むことができることがわかりました。本論文では、最新の既存手法である Order Embedding [Vendrov, 2016] や Hyperbolic Entailment Cones [Ganea, 2018] が、実
は Disk Embdding の一種であるということを証明しました。
Order Embedding
Order Embedding [Vendrov, 2016] はユークリッド空間における Disk Embedding と等価です。
このことは、下図(a) から次のようにわかります。 Order Embedding における n 次元ユークリッド空間の点 x の lower cone の超平面 \(H^{n-1}\) による切り口(三角形の青い領域)を考えると、点と点の推移的な関係は、超平面 \(H^{n-1}\) 上の三角形領域の包含関係として表されます。この図形は三角形ですが、通常のユークリッド距離ではなく、quasi-metric というちょっと変わった"距離"を考えることによって、円板の一種(Formal disk)と考えることができます。
このことから、Order Embedding は n-1次元の超平面(ユークリッド空間)への Disk Embedding の一種であることがわかります。
Hyperbolic Entailment Cones
Hyperbolic Entailment Cones [Ganea, 2018] は球面における Disk Embedding と等価です。
上図(b) のように、ポアンカレ球モデルにおいて、点 x の lower cone (entailment cone) のポアンカレ球の表面(双曲空間における天球)を考えると、これは球面上の円板になります。
すなわち、Hyperbolic Entailment Cones による半順序の埋め込みは、球面への円板の埋め込みであるとみなすことができます。
既存手法の弱み
上述のように、推移的な関係を埋め込む最新の既存手法2つが、Disk Embedding の一種であることがわかりました。これらの手法を Disk Embedding の一種として比較することで、既存手法の様々な問題点が見えてきます。
- 既存手法には"原点"が存在するため、木構造のような、上に行くほどノードの数が収斂していく構造を暗に仮定している。
- 既存手法は、負の半径を許していないため、反転対称性が成り立たない。
- 既存手法のロス関数は、負例に対して勾配が消失する領域があり、最適化が非効率である。
これらの問題点は、Disk Embedding という統一的なフレームワークを考え、このフレームワークの中で既存手法を捉え直すことによって明らかになった問題点であり、本論文の貢献の1つと言えます。
Hyperbolic Disk Embedding
さて、これまで、Order Embedding と Hyperbolic Entailment Cones がそれぞれユークリッド空間と球面における Disk Embedding の一種であることを見てきました。
ユークリッド空間や球面に限らず、もっと様々な空間における Disk Embedding を考えることができます。
ユークリッド空間において、1つの円の周りに同じサイズの円を敷き詰めると、ちょうど6つの円が並びます。
一方、双曲空間においては、1つの円の周りに7個以上の円を敷き詰めることが可能です。さらに、円の半径が大きければ大きいほど、周りに並べられる円の個数が増えます。
このように、大きな半径をもつ円板(=他の多くの円板を包含している)ほど、その周囲に多くの円板を配置することができるため、ユークリッド空間や球面に比べ、より複雑なDAGを埋め込むことができると考えられます。
実験
私たちは、Disk Embedding の有効性を示すため、既存手法と Disk Embedding の手法を試しました。
実験のデータには、大規模な単語のコーパスであるWordNet を用いました。今回は、WordNet に含まれる名詞間の is-a 関係を推移的な関係と見て、Disk Embedding で学習を行いました。
単語のis-a 関係は、抽象的な語になるほど数が少なくなる性質があるため、DAGの形状としては、木構造に似たピラミッド構造となっています。ピラミッド構造ではないDAGの例として、Word Net の is-a 関係を全て反転させたデータ(reversed WordNet)についても同様の実験を行いました。
これは、先行手法のロス関数が勾配消失などの問題を抱えているためであると考えられます。Disk Embedding のフレームワークを用いることで、先行手法の抱えるロス関数の問題が明らかになったことによる成果であると言えます。
また、下段の reversed WordNet では、WordNet データに比べて既存手法の性能が大きく落ちているのに比べて、Disk Embedding 手法はほとんど性能が落ちていないことがわかります。
これは、既存手法が明確な“原点”の存在を仮定していたため、ピラミッド型構造のDAGを埋め込むことはできても、逆ピラミッド型のDAGを埋め込むことが苦手であるということを反映していると言えます。一方で、負の半径を許す Disk Embedding の場合、上述のとおり反転対称性があるため、DAGの向きを反転させても性能が劣化しないという性質を反映しています。
今回の実験では、ピラミッド型のDAGと、逆ピラミッド型のDAGにおいて、既存手法に対する Disk Embedding の性能向上に着目しましたが、今後は、より大規模で複雑なDAG、例えば、論文の引用・被引用関係や、家系図などのデータでの実験を行って行きたいと思います。また、このような複雑なDAGにおいては、Hyperbolic Disk Embedding がその真価を発揮するのではないかと考えています。
まとめ
本稿では、今回公開した論文 "Hyperbolic Disk Embeddings for Directed Acyclic Graphs" の背景となった先行研究を概観し、論文の内容について解説しました。
研究の背景として、機械学習の様々な分野で応用されている「埋め込み」手法について、「データの関係を連続的な空間の構造で表現する」という視点から整理しました。
特に、推移的な関係性を埋め込む手法について考察し、DAGや半順序、lower cone などの概念を導入し、Disk Embedding という統一的なフレームワークを導入し、さらに全く新しいモデルである Hyperbolic Disk Embedding を提案ました。さらに、最新の埋め込み手法である Order Embedding[Vendrov, 2016] や Hyperbolic Entailment Cones [Ganea, 2018] が、Disk Embedding の一種であることを示し、これらの手法の暗黙的な仮定を取り除くことにより、欠点を取り除くことができ、実験においても、高い性能を示すことを確認しました。
LAPRAS では、今後も、「世の中のミスマッチをなくす」ための基礎技術として有望な分野(埋め込み、自然言語処理、知識グラフなど)への研究を進めていきます。今後の展開にどうぞご期待ください！
参考文献
[Ganea, 2018] Ganea et. al., ICML 2018.
[Levy, 2014] Levy & Goldberg 2014, NeurIPS 2014.
[Mikolov, 2013] Mikolov et. al., NeurIPS 2013.
[Nickel, 2017] Nickel & Keila, NeurIPS 2017.
[Suzuki, 2014] R. Suzuki and A. Koga, "Supersolid States in a Hard-Core Bose-Hubbard Model on a Layered Triangular Lattice", J. Phys. Soc. Jpn. 83, 064003 (2014).
[Suzuki, 2017] R. Suzuki, S. Kohmoto and T. Ogatsu, "Non-intrusive Condition Monitoring for Manufacturing Systems", EUSIPCO2017.
[Vendrov, 2016] Ivan Vendrov et. al., ICLR 2016.