Yeongmin Baek
6 min read

Categories

Tags

이전 글에서 Masked Hierarchical Transformer에 대해 리뷰했었는데요, 해당 논문의 레퍼런스들을 살펴보다가 대화를 Graph로 모델링하려는 또 다른 논문을 발견했습니다. 이번 포스트에서는 대화 그래프와 화자 그래프를 이용하여 response generation 문제를 풀고자 했던 GSN: A Graph-Structured Network for Multi-Party Dialogues (IJCAI 2019)을 리뷰하려고 합니다.


Main Idea

기존의 대화 모델링 방법들(HRED 등)은 대화를 발화들의 Sequential하게 구성되었다고 가정하고 모델링을 진행합니다. 하지만 Multi-Party Dialogue(단톡방과 같은 형태)에서는 화자가 여러명이기 때문에 여러 대화가 병렬적으로 동시에 상호작용할 수 있고, 이 가정이 유효하지 않습니다. 본 논문은 이러한 대화 구조를 모델링 하기 위해 대화 및 화자 정보를 그래프의 형태로 모델링합니다.

아래 그림과 같은 경우에, utterance3, utterance4utterance2의 대답이지만, Sequential한 구조의 경우 이를 고려할 수 없습니다. 본 논문에서는 오른쪽의 Graph 구조를 고려한 모델링 방법을 제시합니다.

dialogue


HRED

본 논문에서 베이스라인 모델로 제시하고있는 Hierarchical Reccurent Encoder-Decoder(HRED)는 Multi-turn의 대화를 모델링하기 위한 구조입니다. 크게 아래 그림과 같이 두개의 Reccurent 인코더 구조를 가지며, 각 발화를 인코딩하는 인코더, 해당 발화의 state를 받아서 세션 전체를 인코딩하는 인코더로 구성됩니다. 이렇게 컨텍스트를 인코딩하고, 이를 바탕으로 다음 발화를 생성합니다. 이 방법론은 논문의 서론에서 제시하듯이 각 발화들이 Sequential하게 구성되었다는 가정을 갖고 있습니다.

hred


Problem Formulation

본 논문에서는 “response generation” 문제를 풉니다. 이는 주어진 대화(컨텍스트)를 바탕으로 이에 알맞는 대답을 생성해내는 문제입니다. 저자들은 컨텍스트를 방향성 그래프, 로 표현합니다. 여기서 는 그래프를 구성하는 m개의 Vertice로, 대화를 구성하는 각 발화를 의미합니다. 는 그래프를 구성하는 edge로, 발화가 발화의 대답이라면 나머지는 의 값을 가집니다. 각 발화()는 라는 발화를 대표하는 인코딩 벡터(발화 RNN에 의해 생성되는)로 나타내어집니다.

위와 같은 그래프 가 주어졌을 때, 가장 좋은 답변 를 찾는(생성하는) 문제를 풉니다.

여기에 추가적으로 화자에 대한 정보 (i,j가 같은 화자이면 나머지는 )를 모델링에 이용합니다.


Graph-Structured Neural Network(GSN)

architecture

본 논문에서 제시하는 모델의 구조는 위의 그림처럼 도식화될 수 있습니다. 모델은 크게 word-level encoder(W-E), utterance-level graph-structured encoder(UG-E), decoder(UG-D)의 3가지 부분으로 구성됩니다. UG-E이 본 논문에서 핵심으로 제시하는 구조로, Graph 구조를 이용하여 발화들의 관계를 인코딩하는 역할을 합니다.

1. Word-level Encoder(W-E)

세션에서 주어진 발화들에 대해 각각의 발화들을 하나의 representation으로 인코딩합니다. Bi-LSTM을 이용했고, 각 방향의 마지막 hidden state를 concat하여 세션에 속하는 각 발화들의 representation (i는 각 발화)를 얻습니다.

2. Utterance-level Graph-Structured Encoder(UG-E)

2.1. UG-E & Information Flow Over Graph

Graph 구조의 대화를 모델링하기 위해 dynamic iteration을 가지는 RNN 구조를 제시합니다. 한번의 iteration에서는 주어진 그래프상 각 선행 노드들의 정보만 다음 노드로 전달됩니다. 즉 에서 인 경우, 의 정보를 이용하여 의 정보를 업데이트 하고 이를 다음 iteration에서 이용합니다. Main Idea의 예시에서 2번의 iteration을 수행하면 아래 그림과 같이, 1번 발화의 정보가 3번 발화 에 전달될 수 있습니다.

info_flow

word-level 인코딩의 결과 가 주어졌을 때, 번째 iteration을 수식으로 나타내면 다음과 같습니다.

이를 해석해보면 번째 iteration에서 발화의 representation은 이전 iteration(번째)의 representation에서 선행 노드로 부터의 정보(첫번 째 식 우변의 두번째 항)를 더하여 만들어집니다. 이 때 선행 노드로 부터의 정보는 두번 째 식과 같이 (선행 노드가 두 개 이상이라면) 모든 선행 노드들 정보의 합을 의미합니다. 위 식에서 은 새로운 정보를 얼마나 반영할지의 계수로, non-linear “squasing 함수”를 이용하여 다음과 같이 계산합니다.

는 하이퍼 파라메터로 위 식은 텀이 작으면 의 값을, 크면 1의 값을 갖게 됩니다. (정보의 양이 많을 수록 많이 반영됩니다.)

텀(위 그림의 연산)은 선행노드()의 정보를 반영하여 현재 노드()로 업데이트할 정보입니다. hidden state를 선행 노드의 representation , input state를 현재 노드의 representation 로 하는 GRU 모듈을 이용해 계산할 수 있습니다.

2.2. Bi-directional Information Flow

위의 방식대로 연산을 하면, 아래 그림 왼쪽의 forward flow와 같이 utterance 3, utterance 4 는 각각에 대한 대답을 생성하기 위해 utterance 2 의 정보를 이용할 수 있습니다. 그러나 utterance 4 의 정보는 utterance 3 의 정보를 이용할 수 없습니다.(반대의 경우도 동일) 즉 forward flow를 통해 선행 노드의 정보를 전달해 그래프 구조에 대한 정보를 모델에게 줄 수 있었지만, 형재 노드들(그래프의 depth가 같은 노드들)은 서로에 대한 정보를 이용할 수는 없게 되었고, 이는 생성 결과에 영향을 미칠 수 있습니다.

이를 해결하기 위해 저자들은 backward 방향의 정보도 이용하도록 하는 BIF(Bi-directional Information Flow) 알고리즘을 소개합니다. 아래 그림의 오랜지색 path로, forward path로 정보를 업데이트 하기 전에 backward path로 먼저 정보를 업데이트 합니다. 이렇게 되면 형제 노드들의 정보가 선행 노드를 거쳐 또 다른 형제 노드로 전파될 수 있습니다.

bi_flow

2.3. Speaker Information Flow

대화에서 latent embedding space 상에서 화자에 대한 정보를 나타내는 것(임베딩 단에서 화자에 대한 정보를 추가 해주는 방식)은 대화 모델링에서 향상을 가져왔습니다. 하지만 이 방식은 다양하게 변경되는 화자와 그에 따른 생각 변화를 모델링하기는 부족합니다.

저자들은 동일 화자들의 발화를 그래프의 형태로 만드는 방법을 제시합니다. 또한 이렇게 만들어진 그래프를 이용하여 위의 2.1번 과 동일한 연산을 진행합니다. (단 모든 파라메터는 별도로 생성합니다.)

speaker information flow까지 합치면 번째 representation의 최종 형태는 다음과 같습니다.(우변 세번째 항이 화자에 관련된 항입니다.)

3. Decoder

디코더는 컨텍스트 인코딩 결과를 이용해서 진행되는데, 생성되기 전 마지막 발화의 Context 인코딩 결과와 GRU를 이용하여 연산을 진행합니다. 독특한 점은 인코더에서 마지막 발화의 번의 iteration 중간 값을 갖고 있다가, 이와 디코더 현 시점의 hidden state 사이의 attention을 계산하여 이를 다음 스탭의 디코더 계산에 이용했다는 점입니다. (번역에서 각 단어의 encoder 결과를 이용하여 attention을 계산하는 과정과 유사함.)


Experiment

1. Setup

  • 데이터는 Ubuntu Dialogue Corpus를 이용했습니다.
    • 코퍼스에 등장하는 “@” 심볼을 이용해서 그래프를 구성하였습니다. “A @ B” 의 뜻은 이 발화가 화자 A에 의해 화자 B에게 전달됨을 뜻합니다.
  • 비교 대상으로 HRED와 Seq2Seq 모델 (+ 화자 정보 임베딩)을 이용하였습니다.
  • 학습 파라메터
    • 단어 임베딩: 300차원
    • Word-level encoder & decoder: 2-layer
    • Optimizer: Adam (lr: 0.0001)
    • epoch: 25

2. Result

result_1

위와 같이 제시한 방법론은 기존 방법들에서 화자 정보를 추가한 경우들을 포함하여 모든 베이스라인을 뛰어넘는 성능을 보여주었습니다. iteration의 횟수가 증가할 수록 multi-hop의 노드들을 반영할 수 있고, 더 좋은 결과를 얻음을 알 수 있습니다. 또한 제시한 방법은 화자의 정보가 없는 경우에도 (화자 정보를 사용한) 모든 베이스 라인 성능을 능가했습니다. 표에는 등장하지 않지만 4,5번째 iteration 까지 실험한 경우 성능이 3 iteration과 유사하고, 6번째 iteration 부터는 성능이 떨어진다고 언급했습니다. (이는 GCN등 다른 Graph 기반 모델들과 비슷한 양상입니다.)

저자들은 제시한 방법론이 Multi-party인 경우 외에 Sequential 한 경우에도 일반적으로 잘 동작함을 보이기 위해 Sequential 데이터 (화자 두 명만으로 구성)와 Graph 데이터(Multi-party 데이터)를 구분하여 추가적인 실험을 진행했습니다.

result_2

결과적으로 두 경우 모두 베이스라인을 뛰어넘었고, 제시한 대화의 구조 그래프와 화자 정보 그래프를 이용한 컨텍스트 인코딩 방식(UG-E)이 일반적인 대화 모델링에 있어서 기존 방법들을 뛰어넘었음을 증명했습니다.


Reference

Iulian V Serban, Alessandro Sordoni, Yoshua Bengio, Aaron Courville, 2016 and Joelle Pineau. Building end-to-end dialogue systems using generative hierarchical neural network models. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.

Hu, W.; Chan, Z.; Liu, B.; Zhao, D.; Ma, J.; and Yan, R. 2019 Gsn: A graph-structured network for multi-party dialogues. (IJCAI 2019)