Survey: Timeline Summarization based on Event Graph Compression via Time-Aware Optimal Transport
Tags: nlp, machinelearning
Published: 2023-09-19 15:00:02

## 選定理由

[Timeline Summarization](https://paperswithcode.com/task/timeline-summarization) の主力論文と思われる。このタスク自体は新し目の印象。IBM Research, EMNLP2021採択。似たタスクに [multi-document summarization(MDS)](https://en.wikipedia.org/wiki/Multi-document_summarization) があるが、こちらは時間アラインメントがない。

Paper: https://aclanthology.org/2021.emnlp-main.519/
Code(N/A): https://github.com/limanling/event-graph-summarization
Slide: https://aclanthology.org/2021.emnlp-main.519.mp4

## 概要

【社会課題】
タイムライン要約は、ニュース・文書の集合から主要なキーイベントを識別し、それらを時系列順に説明するタスクである。近年の情報過多に対処し、キーイベントを迅速に抽出し、理解する技術が求められている。

【技術課題】
大きくまとめると以下３つ：(1)ドキュメント集合全体の情報を把握した表現(=特徴ベクトル)を獲得しなければならない(2)複数のドキュメント間で一貫したストーリーの情報を時系列順に集約しなければならない(3)キーイベントを抽出するためのラベリングコストは非常に高く、教師ありはほぼ不可能。

【従来技術】
キーイベントを決定した後に、各キーイベントの要約を生成する。このアプローチはイベントの内部構造（アーギュメント）とイベント間の構造（イベント-イベントの接続）を捉えることができず、LLMのような大きな記憶量を持つモデルの能力を活用できない。

【提案】
周辺ノードと情報を共有し時系列順に接続されたイベント列は、入力となるイベントグラフ上で高い意味的関連性、構造的顕著性を持ち、一貫したストーリーの骨格を表現するという仮説を置く。これによりニュース記事をイベントグラフとして表現すると、タイムライン要約はイベントグラフ全体をそのキーイベントとなるサブグラフに圧縮するタスクと捉えることができる。定式化では時間を考慮した最適輸送問題として捉え、教師なし学習のアプローチで要約モデルの学習・推論を行う。

【効果】
三つの実際のデータセット（公開されている二つの標準ベンチマークと新しく収集されたTimeline100データセットを含む）において、提案したアプローチがSOTAであることを示した。

##　提案手法

入力グラフから要約グラフを推定する問題を最適輸送として捉え、時間アラインメントの取れた情報損失を評価する最適輸送距離によって解くTime-Aware Optimal Transportを提案する。具体的には、入力文書から入力となるイベントグラフを抽出し、それをエンコードして要約グラフに圧縮する。こうすることでドキュメント間の関連を構造的に捉え、時間アラインメントがとれているイベントリストを取得することができる。

### Event Graph Construction

情報抽出システム[OneIE](https://aclanthology.org/2020.acl-main.713/)を使用して、エンティティやイベントを抽出し、共参照解決を行った。時間的関係は特定の方法で抽出され、各イベントの日付は時間表現の正規化や文脈からの時間属性抽出を通じて取得される。文脈から直接日付を取得できない場合、隣接するイベントや文書の出版日から日付を決定した。

### Time-Aware Optimal Transport (OT)

入力グラフGの部分グラフである要約グラフSが最適輸送距離を持つように定式化する。これは一般的に以下のようなアダマール積⊙を最小化する最適化問題と表せる。

![obj](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ywe6lzryrw0sq3h5hldi.png)

Tは輸送計画を示し、二つのグラフ間でのアライメントを最適化する。具体的には、Gの各ノードはSの複数のノードに異なる重みで輸送し、GのノードiからSのノードiへの輸送量はTで表す。Cはコスト行列であり、GとSのノード間のコストを表す。

![detail1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s9x758qot6rdnzx31d0w.png)

イベントグラフは多種多様であり、タイムラインの要約がイベント間の時間的依存に対して鋭敏であることを考慮して、[Gromov-Wasserstein距離](https://link.springer.com/article/10.1007/s10208-011-9093-5)[[Slide](https://speakerdeck.com/eumesy/optimal-transport-for-natural-language-processing?slide=130)]をグラフ上で定義する。これによって二つのグラフ内の対応するノードは、２つの異なる空間（=グラフ）内で、遠い・近いの序列が保たれるようにする。

![detail2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tffa69ar9juhscsugbbi.png)

時間的前後関係（本論文のtemporal ordering はイベントとしての時間的前後関係を指す）を捉えるために上記のような定式化を行なった。

![detail3](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zcgj5a3pvo0ffvwbconp.png)

時間的に遠すぎるイベントには時間正則化項を加え、輸送経路として接続される場合は大きなペナルティを与えた。

### Event Graph Encoder

Time-Aware Optimal Transport を実行するために各ノード（イベント{% katex inline %} v {% endkatex %} or エンティティ{% katex inline %} e {% endkatex %})が持つ情報からグラフ表現を構築する。

![eq1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9owe1q43nffc9fpg3gb8.png)

Semantic Encoding：{% katex inline %} w {% endkatex %}　は記事文章から獲得した[文脈考慮エンべディング](https://medium.com/analytics-vidhya/contextual-word-embeddings-part1-20d84787c65)である。１つのノードに複数のトピックが含まれる場合はノード種エンべディング{% katex inline %} \phi {% endkatex %}を入れるとともに平均化する。これらは事前学習済みBERT等のエンコーダを用いる。イベント頻度がタイムライン要約に有効であることは[Martschat2018]で明らかとなっており、{% katex inline %} |w| {% endkatex %}で表現する。ここで[;]はベクトルの接合を示す。

![eq2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zlrh3vxankswqmfxfczw.png)

Graph Encoding: グラフのグローバルな情報を利用するためにGNNを活用する。エッジ種とエッジ名を同様に事前学習済みBERTでエンコードし、{% katex inline %} \alpha, r {% endkatex %}で表現する。ノードi, j間のメッセージmは一層のNNで表現する。ここでWはモデルパラメータである。

![eq3](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0uckb5gli90qfb2hngal.png)

上記のようにエッジアテンションを定める。

![eq4](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/06bogyj2nqpz9r9dox7i.png)

最終的に各ノードは上記式で接続しているノードからのメッセージmで更新される。

### Training Objective

目的関数の最小化は以下のような Sinkhorn-Knopp algorithm を用いる。

![sinkhorn](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/aykcqo0q8u0dkupboy4l.png)

重要な点として上記定式化は微分可能で、完全なE2Eとして学習することができる。もう一つの重要な点は教師なしであることで、イベントノード数上限m(={% katex inline %} q {% endkatex %}の長さ)などのハイパーパラメータを設定してしまえば要約グラフを生成できる。モデルのパラメータには、グラフエンコーダ（セマンティック関連性、構造的中心性、時間的顕著性を捉える）、輸送距離行列（時間的整合性を捉える）、圧縮モデル（異なる方法でトップランクのノードを選択）、および輸送計画（最小距離を取得するためのグローバルな決定を行う）のためのものがある。これらは、要約グラフと入力グラフとの間の距離を最小化するように最適化される。

### Extractive Summarization

推定された要約グラフSのm個のイベントをその重み {% katex inline %} \alpha {% endkatex %}  に基づき最終的な要約を生成する。各日付には最大kのイベントを選択する制約が設定されており、この制限を超えた場合、他はランキングから除外する。要約グラフSの各イベントに対して、要約文を抽出し、これらは日付順にタイムラインとしてリスト化する。同じ日付のイベントは、イベントの時間的順序に従ってトポロジカルソートにより結合する。