ノードの分散表現間の距離を計算する

こんにちは。taijest です。

この記事は、Sansan Advent Calendar 2020 12日目 の記事です。

はじめに

本日は、分散表現間の関係について記事を書こうと思います。自然言語処理系のカンファレンスである ACL 2020 で、RPD: A Distance Function Between Word Embeddings という論文が発表されています。この論文では、単語の分散表現間の距離関数を定義し、様々な単語の分散表現の学習アルゴリズム間の関係性について分析を行っています。本記事では、この距離関数を利用して、ノードの分散表現の学習アルゴリズム間の関係性について分析を行います。

Relative pairwise inner Product Distance (RPD)

定義

ある学習アルゴリズムによって学習された単語の分散表現を  E で表現します。 E は、 i 行目が単語  w_i の意味ベクトルを表している行列です。二つの異なる分散表現の学習アルゴリズム  E_1,E_2 間の距離関数を Relative pairwise inner Product Distance (RPD) として以下の式で定義します。

 \displaystyle
RPD(E_1, E_2) = \frac{1}{2}\frac{\|\tilde{E}_1\tilde{E}_1^{\top} - \tilde{E}_2\tilde{E}_2^{\top} \|^2}{\|\tilde{E}_1\tilde{E}_1^{\top}\|\|\tilde{E}_2\tilde{E}_2^{\top}\|}

ただし、 \tilde{E} は単語ベクトルの各次元の値をその標準偏差で正規化した値であり、 || \cdot || はフロベニウスノルムです。

特性

上述した RPD という関数はいくつかの性質を持っています。

まず、 E の要素  e_{i,j} が標準正規分布  \mathcal{N}(0,1)に従うと仮定した場合、単語数を  n\rightarrow\infty とした場合に RPD は  1 に収束します。つまり、大量の語彙を持つコーパスに対して、二種類のアルゴリズムで分散表現を推定した場合、推定された分散表現間の構造が類似していないほど、RPDは  1 に近づきます。

また、同様の仮定で、 E_1 E_2 が独立である場合、 RPD(E_1, E_2)正規分布に従うという性質を持っています。この性質を利用することで、二つの埋め込み空間  E_1, E_2 の独立性の検定を行うことが可能になります。

単語の分散表現間の距離

f:id:taijest:20201213123222p:plain:w400:h250
分散表現間の距離と後段タスクでの性能差の関係

RPDは、二つの分散表現で、各分散表現をあるタスクの入力とした時の性能の差と相関があります。距離が近い = 類似した分散表現で後段タスクでは同じような性能になると直感的に解釈することができます。また、論文では、広く使われている単語の分散表現のアルゴリズム間の距離関係について分析をしています。

アルゴリズム 概要
SGNS( k ) negative sample size = k であるような Skip-gram モデル *1
Glove Glove モデル*2
SVD(LC) 対数頻度行列の特異値分解
SVC(PMI) 相互情報量行列の特異値分解

RPDを用いて、上の表に示すアルゴリズムで学習された単語の分散表現間の距離を可視化したものが以下の図になります。

f:id:taijest:20201211231954p:plain:w400:h250
アルゴリズムで学習された単語の分散表現間の距離関係

この図から以下のようなことがわかります。

ノードの分散表現間の距離

ここからは、RPDの概念を応用して、ノードの分散表現間の距離を計算していきたいと思います。グラフデータはその構造が特殊なため、様々なノードの分散表現アルゴリズムが提案されています。

データセットは kaggle で公開されている The Marvel Universe Social Network です。今回はグラフの構造に関しては興味がないため、ランダムに 500 件のノードをサンプリングし、サンプリングされたノード間のエッジを復元して学習対象のグラフとしました。以下は、今回適用したアルゴリズムです。(簡単に利用できるものを選んでいます)

アルゴリズム 概要
DeepWalk ランダムウォークにより得られたパス上でWord2Vecを適用するモデル *4
Node2vec DeepWalkで幅探索のしやすさを調整できるようにしたアルゴリズム *5
GraphWave Spectral Graph Wavelet の拡散に基づきノードの分散表現を学習するアルゴリズム*6
Watch Your Step Graph Attention に基づいたノード分散表現の学習アルゴリズム*7

アルゴリズムで学習された分散表現間の距離を以下に示します。パラメータについては各ライブラリのデフォルトの数値を利用しています。分散表現の次元などを気にせず距離を計算できるのは楽だと思いました。

f:id:taijest:20201213125736p:plain
ノードの分散表現間の距離

データサイズの影響か、距離がかなり大きな値をとっていることが気になります。全体の傾向を見ると、類似したアルゴリズムを採用している DeepWalk と Node2vec が近い値をとっていることは納得がいきます。GraphWave と Watch Your Step は SttelarGraph という同じライブラリのアルゴリズムを用いているので、共通の処理がある可能性があります。

最後に

今回は、RPDという関数に基づいて、ノードの分散表現間の距離を計算しました。

分散表現という技術は、自然言語やグラフなどのそのままでは扱いづらいデータを、特徴をとらえた数値表現に変換できるため、様々な分野で用いられています。しかし、後段タスクでの性能に注目が集まることが多く、分散表現そのものの解析や理解が行われることは少ないです。

次回、機会があれば、実際に後段タスクとの関係を確認したり、他のノードの分散表現間のアルゴリズムを交えて、関係性を分析していきたいと思います。