Graph Convolutionを自然言語処理に応用する Part4

piqcy
piqcy
Sep 21, 2018 · 19 min read

Part4では、Graph Convolutionを自然言語処理に応用した研究をサーベイします。これにより、どんなタスクに適用可能なのか、どう実装するのが良いのか、の2点について知見を得たいと思います。

最終的には、文の特徴抽出器として使いたいところです。本連載の端緒となったTransformerは、元が翻訳ということもありEncoder-Decoderの構成で学習することが可能です。学習済みのTransformerは文の特徴抽出機と見ることができ、OpenAIではTransformerで言語モデルを学習させることで転移学習に成功しています(Improving Language Understanding by Generative Pre-Training)。

つまり、Graph Convolutionを以下のように活用できるとポイントが高いことになります。

  1. 言語モデルのような、教師なしのタスクに適用できる
  2. 教師なしの次点として、大規模なコーパスがあるタスク(翻訳など)に適用できる
  3. AutoEncoder/Encoder-Decoder的な機構により、潜在表現を得ることができる

この観点から、既存の研究を調査していきたいと思います。

Graph Convolution × NLPの既存研究

これから研究の紹介を行っていきますが、各研究の関連は以下のようになっています。

取り上げている研究の関連図

全部目を通すのは面倒、という人もいると思うので最終的な結論を書いておきます。

Graph ConvolutionをSentenceに使う時は、直接でなくBi-directional LSTMを経由したほうが良い。これは以下2点の弱点を補完するため。

  • Graph Convolutionは長期の依存パスや位置情報を考慮するのが苦手(周辺ノードの周辺ノードの・・・とたどる必要がある)。これをLSTMで補完する。
  • Dependency Parseの結果から隣接行列を作成する場合、Parseが間違った場合にダメージを受ける。Bi-directionalなどで周辺コンテキストの情報を渡してやれば、この影響を軽減できる。

つまり、基本構成は以下のような形になります。Word Vectorを一旦LSTM系のモデルに入れて長期依存の情報を取得した後、Graph Convolutionに入れるというスタイルです。

Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling Figure 3
  • ノードは単語表現、エッジは係り受け関係でGraphを構築するのがセオリーだが、他の手法もある
    ノード・エッジをどう定義するかは大きなポイントとなります。ノードは単語表現が主ですが、”Graph Convolutional Networks for Text Classification”ではノードとして文書と単語を併用するといった変わったアプローチを取っています(文書=>単語のエッジはTF-IDFスコア、単語=>単語のエッジは共起頻度(PMI)を使用)。エッジとしては単語の類似度、また以下で紹介するGLoMoではエッジの重み自体を学習させています(Key/Queryで別々に畳み込みを行い、双方をかけあわせる)。
  • 係り受け関係ごとに重みを用意するとOverfitする可能性が高い。そのため、何らかの正則化方法と併用する必要がある。
  • Semantic Roleの分類については、LSTMとGraph Convolutionを併用することで約1~2ポイントのF1スコアの上昇が期待できる。
  • 一方、翻訳ではそれほど高いスコアは出ていない。グラフ構造が明らかに寄与するケース(知識グラフや関係推論など)でないとメリットは得られないのかもしれない。

以上になります。Part5では、この知見を用いて実装を試みていきたいと思います。以下は、各研究の紹介となります。なお、Graph系の論文解説をまとめたリポジトリがあるため、そちらも参考になります。

言語モデル

Structured Sequence Modeling with Graph Convolutional Recurrent Networks

Structured Sequence Modeling with Graph Convolutional Recurrent Networks Figure1, 2

この研究ではConvLSTMのConvをGraph Convolutionに置き換えています。ConvLSTMはLSTMの重みをかける処理をConvolutionに置き換えたモデルです。このConvolutionのパートを、SpectralなGraph Convolutionに置き換えています。Graphの構築に際しては、単語分散表現のcosine similarityトップ4までを接続する形で作成しています(4-nearest neighbor graph with cosine distance, Section 5.2参照)。

なお、この研究は自然言語処理がメインテーマではありません。ConvLSTMは動画などにも使われるモデルなので、自然言語への適用は実験の一つとして行われています。ICLR 2017のレビューではLSTMのチューニングが足りないのではと突っ込まれ、またネットワーク構造についてもConvLSTMに比べて新規性がかけるとしてRejectされています。

Structured Sequence Modeling with Graph Convolutional Recurrent Networks Figure5, Table 2

本研究が登場したのはGraph Convolution=Spectralな頃だったので、Graph ConvolutionをGraph Attention Networkに置き換えるなどすることは可能そうです。これにより、Self-Attention的な要素を加味できるはずです。

翻訳

Graph Convolutional Encoders for Syntax-aware Neural Machine Translation

本研究では、構文解析結果を基にしたGraph Convolutionを翻訳に利用しています。係り受けの方向・関係性ごとに重みをもち、さらに方向×関係性ごとにゲートを設け、特定の組み合わせの場合値を増大/減衰させるようにしています。これをSyntactic GCNと呼んでいます(著者らの先行研究になります)。例として”The monkey eats a banana”の場合、monkeyはeatsの主語(nsubj)となるのですが、eats->monkeyという方向、nsubjという関係性毎に重みを用意するということです。

論文中ではGraph Convolution単独ではなく、Bag of Words、CNN、RNNと組み合わせることを提案しています。以下は、CNNと組み合わせた例です。

Graph Convolutional Encoders for Syntax-aware Neural Machine Translation Figure 2

先ほどのStructured Sequence Modelingとは、Graph Convolutionの位置が逆になっています。どこにGraph Convolution Layerを入れるかは、一つの検討点になりそうです。各モデルと組み合わせた結果は以下のようになっています。

Graph Convolutional Encoders for Syntax-aware Neural Machine Translation Table 3~5

どのモデルと組み合わせても、1~2pt程度の上昇幅が得られるという結果です(基礎力の高いBi-directional RNNとの組み合わせが最良)。また、レイヤを重ねることでよりスコアが向上しています。Graph Convolutionではレイヤを重ねるほど考慮される周辺ノードが多くなるため、その効果であると言えます。

Graph-to-Sequence Learning using Gated Graph Neural Networks

こちらはGraph Convolutionの内部にGRUを組み込んだような手法を利用しています。Gated Graph Neural Network(GGNN)と呼ばれる手法で、これにAttention、Position Encodingの付与、self-loop/逆loopの付与、といった幾つかの工夫を盛り込んだものが本研究の手法となっています。これにより、前述の翻訳モデルより良好な結果が出たとしています。

Graph-to-Sequence Learning using Gated Graph Neural Networks Figure1

GGNNの伝搬処理は以下のようになっています(cはノード数に応じてかかる正則化のための定数です)。

Graph-to-Sequence Learning using Gated Graph Neural Networks 2.1

GRUの伝搬処理は以下で、とてもよく似ていることがわかると思います。

Gated recurrent unit

モデル全体としては、以下の複合といった形です。

  • Gated Graph Neural Network(GGNN)
  • Attention(bilinear attention)
  • self/逆方向の係り受けEdge: Bi-directional的な要素を導入
  • Positional Embeddings: 構文木上の位置を意識させる

この研究は2018年で新しいのですが、その意味では既存研究の工夫をうまくミックスした形になっています。ただ、翻訳として紹介した研究2つは何れも評価指標であるBLEUスコアがそれほど高くないのが気になります。

表現抽出

Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling

前述のSyntactic GCNを提案した論文です。Graph Convolutionに、以下3点の工夫を盛り込んでいます。

  1. Incorporating directions and labels: 係り受け方向/係り受け種別ごとのWeight/bias(ただ、実際には方向の分のみ(式(2)参照))
  2. Edge-wise gating: 係り受け方向, 種別によりゲートをかける: 係り受けのパーサーが間違ったときを考慮しており、例えばあり得ない関係が発生した場合の影響を低減する
  3. Complementarity of GCNs and LSTMs: Graph Convolutionは、近傍の関係をとらえるのには強いが、遠く離れた単語との関係をとらえるのは難しい(近傍の近傍の近傍・・・とたどる必要がある)。LSTMはそこが強いので、LSTMにかけた後Graph Convolutionを行う。
Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling Figure 2

この研究では、作成したEncoderを使用して単語間の意味関係(Semantic Role)の推定を行っています。これは、ちょうど本リサーチの目指している所です。

Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling Figure 3

結果としては、Graph ConvolutionによりLSTMの精度を底上げできています。Graph Convolution単独では、LSTMには劣るようです。

Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling Table 1

GLoMo: Unsupervisedly Learned Relational Graphs as Transferable Representations

こちらは言語モデルでAttentionのかけ方を学び、それを転移するという手法です。Graph Convolutionは使っていませんが、「言語モデルの枠組みで学習して転移する」という点はポイントが高いです。

以下の図の左側のパート(青色/黄色のネットワーク)が言語モデルで学習されるパート、右側のパート(緑色)が転移先のパートです。言語モデルの学習中にAttentionのかけ方=Graph(黄色のネットワーク)を学習し、それを別タスクでも利用することで精度を上げようという試みです。

GLoMo: Unsupervisedly Learned Relational Graphs as Transferable Representations Figure 2

この手法のメリットは、単語分散表現と組み合わせて使えるという点です。イメージ的には、単語分散表現は単語の意味、GLoMoは単語の「組み合わせ方」を転移するという形になります。様々なタスク、また分散表現を使った上でどれくらいGLoMoにより精度がブーストされるかを検証しています。

GLoMo: Unsupervisedly Learned Relational Graphs as Transferable Representations Table 2

一応精度は上がっていますが、uniformな場合に比べての上がり幅はちょっといまいちかなという印象です。試みとしては割合画期的と思うのですが、ほとんど引用も話題にもされていない所に悲しみがあります。

関係推定

Graph Convolution over Pruned Dependency Trees Improves Relation Extraction

Graph Convolutionを使用して意味関係推定を行うという研究です。手法は、先ほど紹介したEncoding Sentences with Graph Convolutional Networks for Semantic Role Labelingを下地にしています。そこからいくつか工夫を行っていますが、メインの工夫は主な係り受け関係以外のパートを枝刈りしてしまうというものです。不要な関係情報を除去することで、精度を上げています。なお、関係推定時は推定対象の単語の情報をConcatします。

Graph Convolution over Pruned Dependency Trees Improves Relation Extraction Figure2

枝刈りとは、メインの依存関係以外を落としてしまうことです。メインとは、関係を推定する2つのEntityの係り受けです。ただ、そうしてしまうと情報が落ちてしまう側面もあります。上図では、He, relative, Mike Caneは残りますが、その関係を否定する”not”はメインの関係に含まれないため落ちてしまいます。そこで、メイン関係からの距離が一定以内のものは残すとしています。

本研究では、既存研究の工夫についても評価を行っています。各手法について、以下のような結果だったと報告しています。

  • 係り受け関係の方向/自己関係ごとに重みを分ける: 精度に影響なし
  • 関係方向/関係種別によるGating: パフォーマンスを毀損する

結果として、Graph Convolutionを組み合わせることで精度の向上に成功しています。PA-LSTMはposition-awareなLSTMで、位置情報をいれたLSTMになっています。

Graph Convolution over Pruned Dependency Trees Improves Relation Extraction Table1

Modeling Relational Data with Graph Convolutional Networks

最後は、ストレートにGraph Convolutionを使って知識グラフに関するタスクを行った論文です。具体的には、Link Prediction、Node Classificationの2つのタスクを行っています。

基本的なネットワークは、関係の向きを考慮したGraph Convolutionです。以下の図は、1~Nの関係について、inごとに重み、outごとに重みをかけた結果、さらに自己ループに重みをかけた結果を合算し活性化関数(ReLU)で伝搬する様子を示しています。

Modeling Relational Data with Graph Convolutional Networks Figure 2

ただ、関係の種別が多い場合その分重みを用意することになり、過学習してしまいます。そこで、関係の重みを限られた重みの掛け合わせで表現するよう正則化をかけています(2.2 Regularization 参照)。また、関係によるGatingは搭載していません。

前述の結果を含めて考えると、関係ごとに重みを用意するのはOver parameterで、何らかの正則化が必要なことが推察できます。

研究の紹介は以上になります。研究調査の結果から、冒頭に述べた知見が得られました。Part5では、この知見を活用し実装を試みていきたいと思います。

参考文献

  1. Alec Radford, Karthik Narasimhan, Tim Salimans and Ilya Sutskever. Improving Language Understanding with Unsupervised Learning. 2018.
  2. Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst and Xavier Bresson. Structured Sequence Modeling with Graph Convolutional Recurrent Networks. arXiv preprint arXiv:1612.07659, 2016.
  3. Xingjian Shi, Zhourong Chen, Hao Wang, Dit-Yan Yeung, Wai-kin Wong and Wang-chun Woo. Convolutional LSTM Network: A Machine Learning Approach for Precipitation Nowcasting. In NIPS, 2015.
  4. Joost Bastings, Ivan Titov, Wilker Aziz, Diego Marcheggiani and Khalil Sima’an. Graph Convolutional Encoders for Syntax-aware Neural Machine Translation. In EMNLP, 2017.
  5. Daniel Beck, Gholamreza Haffari andTrevor Cohn. Graph-to-Sequence Learning using Gated Graph Neural Networks. In ACL, 2018.
  6. Yujia Li, Daniel Tarlow, Marc Brockschmidt and Richard Zemel. Gated Graph Sequence Neural Networks. In ICLR, 2016.
  7. Diego Marcheggiani and Ivan Titov. Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling. In EMNLP, 2017.
  8. Zhilin Yang, Jake Zhao, Bhuwan Dhingra, Kaiming He, William W. Cohen, Ruslan Salakhutdinov and Yann LeCun. GLoMo: Unsupervisedly Learned Relational Graphs as Transferable Representations. arXiv preprint arXiv:1806.05662, 2018.
  9. Yuhao Zhang, Peng Qi and Christopher D. Manning. Graph Convolution over Pruned Dependency Trees Improves Relation Extraction. In EMNLP, 2018.
  10. Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov and Max Welling. Modeling Relational Data with Graph Convolutional Networks. arXiv preprint arXiv:1703.06103, 2017.
  11. Liang Yao, Chengsheng Mao and Yuan Luo. Graph Convolutional Networks for Text Classification. arXiv preprint arXiv:1809.05679, 2018.

programming-soda

Exciting research & programming like soda!

piqcy

Written by

piqcy

All change is not growth, as all movement is not forward. Ellen Glasgow

programming-soda

Exciting research & programming like soda!

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade