세상의 변화에 대해 관심이 많은 이들의 Tech Blog search

BLEURT - Learning Robust Metrics for Text Generation(BLEU 개선 버전, BLEURT 논문 설명)

|

이 글에서는 2020년 ACL에 Google Research 팀의 Thibault Sellam 등이 게재한 BLEURT: Learning Robust Metrics for Text Generation를 살펴보도록 한다.

구글 AI 블로그에서 이 논문에 대한 설명을 볼 수 있다.

중요한 부분만 적을 예정이므로 전체가 궁금하면 원 논문을 찾아 읽어보면 된다.


BLEURT: Learning Robust Metrics for Text Generation

논문 링크: BLEURT: Learning Robust Metrics for Text Generation

홈페이지: 구글 AI 블로그

Tensorflow code: Official Code

초록(Abstract)

텍스트 생성은 지난 몇 년간 상당한 발전을 이루었다. 그러나 아직 그 평가 방법은 매우 뒤떨어져 있는데, 가장 자주 사용되는 BLEU나 ROUGE는 사람의 판단과는 낮은 연관성을 갖는다(즉, 사람이 보기에 별로 적절치 않다). 이 논문에서는 BLEURT라는 새 평가 방법을 제안하는데, BERT에 기반한 학습된 평가방법으로 수천 개 정도의 학습 예시만으로도 사람의 판단 방식을 모델링할 수 있다. 이 접근법의 핵심은 수백만 개의 합성된 예시를 모델을 일반화하기 위해 사용하는 새로운 사전학습 방식이라는 것이다. BLEURT는 WMT Metrics와 WebNLG Competition 데이터셋에서 state-of-the-art 결과를 얻었다. 바닐라 BERT 기반 방식과는 다르게, BLEURT는 학습 데이터가 드물고 기존 분포에서 벗어나도 훌륭한 결과를 보여준다.


1. 서론(Introduction)

지난 몇 년간, 자연어생성 분야에서의 연구는 번역, 요약, 구조화된 데이터 → 텍스트 생성, 대화 및 이미지 캡션 등을 포함한 많은 문제에서 encoder-decoder 신경망을 통해 상당한 발전을 이루었다. 하지만, 평가 방법의 부족으로 인해 발전이 적지 않게 지연되었다.

인간 평가(Human Evaluation)는 시스템의 품질을 측정하는 데 있어서 종종 최선의 지표가 되지만, 이는 매우 비싸며 상당히 시간이 많이 소요되는 작업으로 매일 모델 개발의 pipeline에 넣을 수는 없다. 그래서, NLG 연구자들은 보통 계산이 빠르고 그럭저럭 괜찮은 품질의 결과를 주는 자동 평가방법(automatic evaluation metrics)을 사용해 왔다. 이 논문에서는 문장 수준의, 참조 기반 평가 방법으로, 어떤 후보 문장이 참조 문장과 얼마나 비슷한지를 측정하는 방법을 제시한다.

1세대 평가방법은 문장 간의 표면적 유사도를 측정하기 위해 수동으로 만들어졌다. BLEU와 ROUGE라는 두 개의 방법이 N-gram 중첩(overlap)에 기반하여 만들어졌다. 이러한 평가방법은 오직 어휘의 변화에만 민감하며, 의미적 또는 문법적인 측면의 변화는 제대로 측정하지 못하였다. 따라서, 이러한 방식은 사람의 판단과는 거리가 멀었으며, 특히 비교할 시스템이 비슷한 정확도를 가질 때 더욱 그렇다.

NLG 연구자들은 이 문제를 학습된 구성 요소를 이 평가방법에 집어넣음으로써 다뤄 왔다. WMR Metrics Shard Task라는, 번역 평가에서 자주 사용되는 평가방법이 있다. 최근 2년간은 신경망에 기반한 RUSE, YiSi, ESIM이 많이 사용되었다. 최근의 방법들은 다음 가지로 나뉜다:

  1. 완전히 학습된 평가방법.
    • BEER, RUSE, ESIM
    • 일반적으로 end-to-end 방식으로 학습되었으며, 보통 수동으로 만든 feature나 학습된 embedding에 의존한다.
    • 훌륭한 표현능력(expressivity)를 가진다.
    • 유창성, 충실함, 문법, 스타일 등 task-specific한 속성을 가지도록 튜닝할 수 있다.
  2. Hybrid 평가방법.
    • YiSi, BERTscore
    • 학습된 요소(contextual embeddings)를 수동으로 만든 논리(token alignment 규칙)와 결합한다.
    • 강건성(Robustness)를 확보할 수 있다.
    • 학습 데이터가 적거나 없는 상황에서 좋은 결과를 얻을 수 있다.
    • train/test 데이터가 같은 분포에 존재한다는 가정을 하지 않는다.

사실, IID 가정은 domain drift 문제에 의해 NLG 평가에서 특히 문제가 되었다. 이는 평가방법의 주 목적이지만, quality drift 때문이기도 하다: NLG 시스템은 시간이 지남에 따라 더 좋아지는 경향을 보이며, 따라서 2015년에 rating data로 학습한 모델은 2019년의 최신 모델을 구별하지 못할 수 있다(특히 더 최근 것일수록). 이상적인 학습된 평가방법은 학습을 위해 이용가능한 rating data를 완전히 활용하고, 분포의 이탈(drift)에 강간한 것을 모두 확보하는 것이다. 즉 추론extrapolate할 수 있어야 한다.

이 논문에서 통찰한 바는 표현능력과 강건성을 인간 rating에 미세조정하기 전 대량의 합성 데이터에서 사전학습하는 방식으로 결합하는 것이 가능하다는 것이다.
여기서 BERT에 기반한 텍스트 생성 평가방법으로 BLEURT를 제안한다. 핵심은 새로운 사전학습 방법으로, 어휘적 그리고 의미적으로 다양한 감독 signal(supervision signals)를 얻을 수 있는 다양한 Wikipedia 문장에서 임의의 변화(perturbation)을 준 문장들을 사용하는 방법이다.

BLEURT를 영어에서 학습하고 다른 일반화 영역에서 테스트한다. 먼저 WMT Metrics Shared task의 모든 연도에서 state-of-the-art 결과를 보인다. 그리고 스트레스 테스트를 하여 WMT 2017에 기반한 종합평가에서 품질 이탈에 대처하는 능력을 측정한다. 마지막으로, data-to-text 데이터셋인 WebNLG 2017으로부터 얻는 3개의 task에서 다른 도메인으로 쉽게 조정할 수 있음을 보인다. Ablation 연구는 이 종합 사전학습 방법이 IID 세팅에서 그 성능을 증가시키며, 특히 학습 데이터가 편향되어 있거나, 부족하거나, 도메인을 벗어나는 경우에 더 강건함을 보인다.

코드와 사전학습 모델은 온라인에서 볼 수 있다.


2. 서두(Preliminaries)

$x = (x_1, …, x_r)$는 $r$개의 token을 갖는 참조 문장이며 $\tilde{x} = (\tilde{x}_1, …, \tilde{x}_p)$는 길이 $p$의 예측 문장이다. $y$가 예측 문장이 참조 문장과 관련하여 얼마나 좋은지를 사람이 정한 값이라 할 때 크기 $N$의 학습 데이터셋은 다음과 같이 쓴다.

[\lbrace (x_i, \tilde{x}i, y_i) \rbrace^N{n=1}]

학습 데이터가 주어지면, 우리의 목표는 사람의 평가를 예측하는 함수 $f : (x, \tilde{x}) \rightarrow y$를 학습하는 것이다.


3. 품질 평가를 위한 미세조정 BERT(Fine-Tuning BERT for Quality Evaluation)

적은 양의 rating(rating) 데이터가 주어졌을 때, 이 task를 위해 비지도 표현을 사용하는 것이 자연스럽다. 이 모델에서는 텍스트 문장의 문맥화된 표현을 학습하는 BERT를 사용하였다. $x$와 $\tilde{x}$가 주어지면, BERT는 문맥화된 벡터의 sequence를 반환하는 Transformer이다:

[v_{[\text{CLS}]}, v_{x_1}, …, v_{x_r}, v_1, …, v_{\tilde{x}_p} = \text{BERT}(x, \tilde{x})]

$ v_{[\text{CLS}]}$는 특수 토큰 $\text{[CLS]}$의 표현이다. 여기서 rating를 예측하기 위해 $\text{[CLS]}$ 벡터에 선형 레이어를 하나 추가했다:

[\hat{y} = f(x, \tilde{x}) = W\tilde{v}_{[\text{CLS}]} + b]

$W$와 $b$는 각각 weight matrix와 bias이다. 위의 선형 레이어와 BERT parameter는 대략 수천 개의 예시를 사용하여 미세조정(fine-tuned)된다. Regression Loss로 다음을 쓴다.

[l_{\text{supervised}} = \frac{1}{N} \Sigma^N_{n=1}\Vert y_i - \hat{y}\Vert^2]

이 접근법은 상당히 간단하지만, Section 5에서 WMT Metrics Shared Task 17-19에서 state-of-the-art 결과를 얻을 수 있음을 보인다. 하지만, 미세조정 BERT는 많은 양의 IID data를 필요로 하며, 이는 다양한 task와 모델의 변형에 일반화할 수 있는 평가 방법으로는 아주 이상적이지는 않다.


4. 합성 데이터에서 사전학습(Pre-Training on Synthetic Data)

이 접근법의 핵심 부분은 rating data에 미세조정하기 전 BERT를 “warm up”하기 위해 사전학습 기술을 사용했다는 것이다. 많은 양의 참조-후보 쌍 $(z, \tilde{z})$을 생성하여, 여러 어휘적 & 의미적 수준의 감독 signal를 multi-task loss를 사용하여 BERT를 학습시켰다. 실험이 보여주듯이, BLEURT는 이 단계 이후로 매우 성능이 좋아지며, 특히 데이터가 부족할 때에 더욱 그렇다.

어떤 사전학습 접근법이든지 데이터셋과 사전학습 task 뭉치가 필요하다. 이상적으로, 이러한 구조는 최종 NLG 평가 task(i.e., 문장 쌍은 비슷하게 분포되어야 하고 사전학습 signal는 사람의 판단과 연관되어 있어야 한다)와 비슷할 수밖에 없다. 안타깝게도, 우리는 우리가 미래에 평가할 NLG 모델에 접근할 수 없다.
따라서, 우리는 일반성을 위해 방법을 다음 3가지 요구사항으로 최적화했다:

  1. 참조 문장 집합은 반드시 크고 다양성을 가져야 하며, 이는 BLEURT가 다양한 NLG domain과 task를 처리할 수 있을 만큼 충분해야 한다.
  2. 문장 쌍은 매우 다양한 의미적, 구문론적, 의미적 차이점을 포함해야 한다.
  3. 사전학습 objective는 BLEURT가 식별할 수 있을 만큼 효과적으로 그 현상들을 잡아내야 한다.

아래 섹션들에서 상세히 설명한다.

4.1. 문장 쌍 생성(Generating Sentence Pairs)

BLEURT를 매우 다양한 문장에 노출시키기 위한 하나의 방법은 존재하는 문장 쌍 데이터셋(Bowman et al., 2015; Williams et al., 2018; Wang et al., 2019)을 사용하는 것이다. 이 데이터셋들은 다양한 출처의 연관된 문장들을 포함하지만 NLG 시스템이 만드는 오류와 변형을 잡아내지 못할 수 있다(생략, 반복, 터무니없는 대체 등). 대신 자동적 접근법을 선택하여, 이는 임의로 늘일 수 있고 또한 적은 비용으로 실행할 수 있다: 우리는 합성 문장 쌍 $(z, \tilde{z})$를 Wikipedia에서 가져온 문장에 180만 개의 부분 perturbing을 수행하여 얻었다. 여기서는 BERT에서 mask-filling, 역 번역, 단어를 임의로 빼는 세 가지 기술이 사용되었다. 이를 살펴보자.

Mask-filling with BERT:

BERT의 초기 학습 task는 토큰화된 문장에서 masked 토큰을 채우는 task이다. 이 기술은 Wikipedia 문장의 임의의 위치에 mask를 삽입한 후 언어 모델로 이를 채우는 과정이다. 따라서, 문장의 유창성을 유지하면서 어휘적 변형을 모델에 소개하였다. Masking 전략은 두 가지가 있는데, 문장의 임의의 위치에 mask를 만들거나, masked 토큰에 근접한 문장을 만드는 것이다. 더 자세한 내용은 부록 참조.

Backtranslation:

역 번역을 통해 문단과 문장 동요(perturbation)을 생성하였고, 이는 번역 모델을 사용하여 영어를 다른 언어로 번역했다가 다시 영어로 바꾸는 왕복 과정이다. 주 목표는 의미를 유지하는 참조 문장에 변형을 추가하는 것이다. 추가적으로, 역 번역 모델의 예측 실패한 것을 현실적 변형의 출처로 사용하였다.

Dropping words:

위의 합성 예시에서 단어를 무작위로 삭제하여 다른 예시를 만드는 것이 실험에서 유용하다는 것을 알아내었다. 이 방법은 BLEURT가 “병적인” 행동이나 NLG 시스템: 의미없는 예측, 문장 절단 등에 대비할 수 있게 한다.

4.2. 사전학습 signal(Pre-Training Signals)

다음 단계는 각 문장 쌍 $(z, \tilde{z})$과 사전학습 signal 집합 $\lbrace \tau_k \rbrace$ 을 늘리는 것이다. $\tau_k$는 사적학습 task $k$의 목표 벡터이다. 좋은 사전학습 signal는 매우 다양한 어휘적, 의미적 차이점을 잡아내야 한다. 이는 또한 얻기 쉬워야 하며, 따라서 이 접근법은 대량의 합성 데이터에도 크기를 늘려 사용할 수 있어야 한다. 다음 섹션에서는 표 1에 요약한 9가지 학습 task를 소개한다. 추가 구현 세부는 부록을 참조한다.

Automatic Metrics:

문장 BLEU, ROUGE, BERTscore와 연관하여 3가지 signal $\tau_{\text{BLEU}}$, $\tau_{\text{ROUGE}}$, $\tau_{\text{BERTscore}}$를 만들었다. precision을 사용하며 뒤의 2개는 recall과 F-score를 사용한다.

Backtranslation Likelihood:

이 signal의 아이디어는 존재하는 번역 모델을 의미적 동등을 측정하는 도구로 사용하는 것이다. 문장 쌍 $(z, \tilde{z})$이 주어지면, 이 학습 signal은 $\tilde{z}$가 그 length로 정규화되었을 때 $z$의 역 번역일 확률 $P(\tilde{z}\vert z)$를 측정한다.

아래 식의 첫 번째 항을 영어 문장 $z$을 조건으로 하여 프랑스어 문장 $z_{fr}$일 확률을 할당하는 번역 모델이라 하자.
두 번째 항은 프랑스어 $\rightarrow$ 영어에 대한 번역 모델이다.

[P_{en \rightarrow fr}(z_{fr} \vert z) , P_{fr \rightarrow en}(z \vert z_{fr})]

만약 $\vert \tilde{z} \vert$가 $\tilde{z}$ 안의 토큰의 수라면, 점수를 다음과 같이 정의한다.

[\tau_{en-fr, \tilde{z} \vert z} = \frac{\log P(\tilde{z} \vert z)}{\vert \tilde{z} \vert} , P(\tilde{z} \vert z) = \sum_{z_{fr}} P_{fr \rightarrow en}(z \vert z_{fr}) \ P_{en \rightarrow fr}(z_{fr} \vert z)]

모든 가능한 프랑스어 문장에 대해 합을 계산하는 것은 불가능하기 때문에, 합은 다음과 같이 근사한다:

[\text{assume}: P_{en \rightarrow fr}(z_{fr} \vert z) \approx 1]

[P(\tilde{z} \vert z) \approx P_{fr \rightarrow en}(\tilde{z} \vert z^_{fr}) , where \ z^{fr} = \text{argmax} P{en \rightarrow fr}(z_{fr} \vert z)]

$P(z \vert \tilde{z})$를 계산하는 것은 자명하게도 과정을 역으로만 하면 되므로 영어 $\leftrightarrow$ 독일어와 영어 $\leftrightarrow$ 프랑스어 간 다음 4개의 사전학습 signal을 만들었다.

[\tau_{\text{en-fr}, z \vert \tilde{z}}, \ \tau_{\text{en-fr}, \tilde{z} \vert z}, \ \tau_{\text{en-de}, z \vert \tilde{z}}, \ \tau_{\text{en-de}, \tilde{z} \vert z}]

Textual Entailment:

signal $\tau_{\text{entail}}$은 $z$가 $\tilde{z}$를 수반하는지 혹은 상충하는지를 분류기를 통해 표현한다. 이와 관련하여 수반 데이터셋 MNLI에서 미세조정된 BERT를 사용하여 가능성을 수반(Entail), 모순(Contradict), 중립(Neutral)으로 분류하였다.

Backtranslation flag:

signal $\tau_{\text{backtran_flag}}$는 perturbation이 역 번역에 의해 생성되었는지 혹은 mask-filling에 의해 생성되었는지를 나타내는 Boolean 값이다.

4.3. 모델링(Modeling)

각 사전학습 task에서, 모델은 회귀 또는 분류 loss를 사용한다. 그리고 task 수준의 loss의 가중합을 구한다.

$\tau_k$를 각 task에 대한 목표 벡터라 하자(Entail, Contradict, Neutral, precision, recall, ROUGE F-score 등).

만약 $\tau_k$가 회귀 task이면, loss는 $\vert \tau_k \vert $가 $\tau_k$의 차원이고 $\vert \hat{\tau}_k\vert$가 [CLS] embedding에 선형 레이어를 붙여 계산한 것이라면 $\ell_2$ loss는 다음과 같다.

[\ell_k = \Vert\tau_k - \hat{\tau}k \Vert^2_2 / \vert \tau_k \vert \quad \text{where} \ \hat{\tau}_k = W{\tau_k}\tilde{v}{[\text{CLS}]} + b{\tau_k}]

만약 $\tau_k$가 분류 task이면, 각 class $c$에 대한 logit을 예측하기 위한 선형 레이어를 분리하였고 multi-class cross-entropy loss를 사용하였다. 사전학습 손실함수는 다음과 같다.

\(\ell_{\text{pre-training}} = \frac{1}{M} \sum^M_{m=1} \sum^K_{k=1} \gamma_k \ell_k (\tau^m_k, \hat{\tau}^m_k)\) \(\text{where} \ \hat{\tau}_{kc} = W_{\tau_{kc}}\tilde{v}_{[\text{CLS}]} + b_{\tau_{kc}}\)

  • $\tau^m_k$: 예시 $m$에 대한 목표 벡터
  • $M$: 합성 예시의 숫자
  • $\gamma_k$: grid search로 얻은 초모수 가중치(hyper-parameter weights)

보다 자세한 것은 부록을 참조한다.

Examples

5. 실험(Experiments)

번역과 data $\to$text task에서 실험 결과를 적는다. 먼저, BLEURT를 이미 존재하는 텍스트 생성 평가방법과 WMT Metrics Shared Task의 최근 3년간에 대해 평가한다. 그리고 WMT17에 기반한 일련의 합성 데이터에 따라 움직이는 품질 이탈(drifts)에 대한 BLEURT의 강건성을 평가한다. 또 WebNLG 2017 Challenge Dataset와 다른 task에 적용시키는 BLEURT의 능력을 평가한다. 마지막으로, ablation을 통해 각 사전학습 task이 기여하는 바를 측정한다.

Our Models:

모든 BLEURT 모델은 다음 3단계를 거친다:

  1. BERT 모델의 기본 사전학습
  2. 합성 데이터에 대한 사전학습
  3. task-specific rating에 대한 미세조정(번역 그리고/혹은 data $\to$ text)

BLEURT는 2가지 버전이 있다.

  1. BLEURT: BERT-Large uncased 기반(24 layer, 1024 hidden units, 16 heads)
  2. BLEURTbase: BERT-Base uncased 기반(12 layer, 768 hidden units, 12 heads)

batch size는 32, learning rate는 1e-5, 사전학습에 80만 step, 미세조정에 4만 step을 적용하였다. 더 자세한 사항은 부록 참조.

5.1. WMT Metrics Shared Task

Datasets and Metrics:

WMT Metrics Shared Task의 2017-2019년, to-English 언어 쌍 데이터를 사용하였다. 각 연도에 대해, 공식 WMT test set(사람의 평가와 같이 뉴스 도메인에서 얻은 수천 개의 문장 쌍으로 구성)을 사용하였다.
training set은 5360, 9482, 147691개의 예시가 있다. 2018년과 2019년의 test set은 더 noise가 많은데, 좀 더 낮은 상관관계를 보인다.

자동화된 평가 방법과 인간 평가와 일치하는 정도를 평가한다. 각 연도에 대해, Kendall’s Tau $\tau$(실험 간 일관성을 위해)와 공식 WMT 평가(완전성을 위해)를 둘 다 사용하였다. 공식 WMT 평가방법은 Pearson’s correlation이나 DARR라 불리는 Kendall’s Tau의 강건한 변형이며, 부록에서 볼 수 있다. 모든 숫자는 벤치마크의 구현에서 가져왔다. 결과는 전체적으로 공식 결과와 일관되지만 2018년과 2019년에서 약간의 차이를 발견하였고, 표에서 확인할 수 있다.

Models:

4가지 버전이 있다: BLEURT, BLEURTbase, BLEURT -pre, BLEURTbase -pre. 첫 2개는 BERT-large와 BERT-base에 기반하였다. 뒤 2개는 사전학습 단계를 생략하고 바로 WMT ratings에 미세조정한 것이다. WMT shared task의 각 연도의 작년 test set을 training과 validation set으로 사용하였다. 이는 부록에서 더 자세히 설명한다.

BLEURT를 shared task의 다른 후보 데이터와 자동화된 평가방법과 비교하였다. 전자의 경우에는 각 연도의 최고 성능 평가방법인 chrF++, BEER, Meteor++, RUSE, Yisil, ESIM, Yisil-SRL를 사용하였다. 모든 후보는 같은 WMT 학습 데이터와 추가적으로 존재하는 문장 또는 token embedding을 사용하였다. 후자의 경우에는 Moses sentenceBLEU, BERTscore, MoverScore를 사용하였다. BERTscore에 대해서는 공정성을 위해 BERT-large uncased 모델을, 완전성을 위해 roBERTa를 사용하였다. MoverScore는 WMT 2017의 scripts를 사용하여 평가하였다.

Results:

Examples
Examples

표 2~4에서 볼 수 있다. 2017년과 2018년에서는 BLEURT-based 평가가 각 언어 쌍에서 다른 벤치마크를 압도한다. 2019년에서도 Kendall’s Tau에서 모든 언어 쌍에 대해 최고의 결과를, DARR에서 7개 중 3개에서 최고의 결과를 냈다는 점에서 BLEURT와 BLEURTbase 역시 경쟁력이 있다.
기대한 대로, BLEURT는 대부분의 경우 BLEURTbase를 압도한다. 사전학습은 일관되게 BLEURT와 BLEURTbase의 성능을 높인다.

2017년에서 가장 큰 효과는 BLEURTbase(zh-en)에서 7.4 Kendall Tau 점수를 더 얻었다는 것이다. 이 효과는 2018년과 2019년에서는 더 약하다(tr-en, 2018년에서 2.1점). 이 차이는 2017년에 사용된 학습 데이터는 이후 연도보다 더 적기 때문이며, 사전학습이 더 도움이 되었기 때문이라 설명할 수 있다. 일반적으로 사전학습은 BERT-large보다 BERT-base에서 더 큰 효과를 가지는데, 사실, 사전학습을 포함한 BLEURTbase는 포함하지 않을 때 BLEURT보다 더 좋은 경우도 있었다.

Takeaways:

사전학습은 일관적으로 성능 향상을 가져다주며, 특히 BLEURT-base에서 그렇다. BLEURT는 WMT Metrics Shared task의 모든 연도에서 가장 좋은 성능을 보인다.

5.2 Robustness to Quality Drift

사전학습이 품질 이탈(quality drift)에 대한 BLEURT의 강건성을 증가시킨다는 것은 추론 비중이 증가하는 일련의 task를 구성함으로써 평가하였다. 모든 실험은 WMT Metrics Shared Task 2017에 기반하였다. 이 rating이 특별히 믿을 만하기 때문이다.

Methodology:

WMT Metrics shared task의 예시들을 부차표본추출하여 저평가된 번역을 학습으로 고평가된 번역을 테스트로 하여 난이도가 점점 높아지는 데이터셋들을 생성하였다. 중요한 parameter는 skew factor $\alpha$인데 이는 학습 데이터가 얼마나 좌편향되었고 테스트 데이터가 얼마나 우편향되었는지를 측정한다. 학습 데이터는 $\alpha$가 커질수록 줄어든다. 가장 극단적인 경우인 $\alpha=3.0$의 경우 학습 데이터로는 전체(5344개)의 11.9%만 사용한다. 더 자세한 건 부록 참조.

BLEURT는 사전학습을 한 것과 안 한 것으로 나누어 Moses sentBLEU와 BERTscore와 비교한다. BERT-large uncased를 기본으로 사용한다.

Results:

Examples

그림 2는 학습/테스트 데이터의 skew를 독립적으로 변화시키면서 측정한 BLEURT의 성능을 보여준다. 첫 번째 관찰할 점은 test skew가 증가할수록 모든 평가방법의 일치성이 하락한다는 것이다. 이 효과는 2019 WMT Metrics 보고서에서도 이미 보고되었다. 일반적인 설명은 rating이 가까워질수록 task가 어려워진다는 것이고, “good* 시스템을 그냥 평가하는 것보다 “good”과 “bad”를 구별하는 것이 더 쉽다는 것이다.

학습 skew는 사전학습이 없는 BLEURT에 치명적인 효과를 가진다: $\alpha=1.0$에서 BERTscore보다 낮으며, $\alpha \ge 1.5$인 경우에는 sentBLEU보다 낮다. 사전학습된 BLEURT는 훨씬 더 강건하다: 유일하게 낮아지는 때는 가장 극단적인 drift(학섭 데이터는 부정확한 번역, 테스트할 때에는 훌륭한 번역)가 존재하는 $\alpha=3.0$일 때 뿐이다.

Takeaways:

사전학습은 BLEURT의 quality drift에 대한 강건성을 크게 증가시킨다.

5.3 WebNLG Experiments

이 섹션에서는, data $\to$ text 데이터셋(WebNLG Challenge 2017)에서 나온 3가지 task에 대한 BLEURT의 성능을 평가한다. 목표는 학습 데이터가 제한되었을 때 BLEURT의 새로운 task에 대한 적응능력을 평가하는 것이다.

Dataset and Evaluation Tasks:

WebNLG challenge 벤치마크 시스템은 1~5개의 RDF triple 집합의 객체(예: 빌딩, 도시, 예술가 등)에 대한 자연어 설명을 생성한다. 223개의 입력에 대해 9개의 시스템에 인간 평가를 수행하여 4677 문장 쌍에 대한 데이터가 있다. 각 입력당 1~3개의 참조 설명이 있다. 각 제출은 의미, 문법, 유창성 측면에서 평가된다. ratings의 각 종류는 독립된 모델링 task로 여겨진다.
데이터는 train/test 집합 사이에 자연스러운 구분이 없으므로 여러 전략을 통해 실험하였다. 학습에는 0~50%의 데이터를 사용하고, 다른 일반화 가능 범위를 평가하기 위해 평가할 시스템과 RDF 입력을 모두 분리하였다.

Systems and Baselines:

BLEURT -pre -wmt는 WebNLG ratings에서 직접 학습된 일반적인 BERT-large uncased이며, BLEURT -wmt는 합성 데이터에서 처음 사전학습되어 WebNLG 데이터에서 미세조정된 것이다. BLEURT는 1) 합성 데이터, 2) WMT 데이터, 3) WebNLG 데이터에서 차례로 학습된다. 어떤 샘플이 여러 참조에서 올 때, BLEURT를 각 참조에서 실행시켜서 가장 높은 점수만을 기록한다.

4가지의 기준 모델은 각각 BLEU, TER, Meteor, BERTscore이다. 첫 3개는 WebNLG competition organizers에 의해 계산된다. 마지막 하나는 공정한 비교를 위해 BERT-large uncased 모델을 사용해 직접 평가하였다.

Results:

Examples

그림 3은 학습에 할당되는 데이터의 비율의 변화에 따라 평가방법과 인간 평가 사이의 상관관계를 보여준다. 더 많이 사전학습된 BLEURT가 더 잘 적응함을 볼 수 있다. vanilla BERT 접근법인 BLEURT -pre -wmt는 대부분의 task에서 기준 모델을 압도하려면 WebNLG 데이터의 1/3이 필요하며, 그러고도 의미론적인 측면에서 여전히 뒤처진다.
이와 대조적으로, BLEURT -wmt는 836개 정도의 샘플을 사용한 경우에 경쟁력이 있으며, BLEURT는 미세조정을 하지 않았을 때 BERTscore와 비교할 만하다.

Takeaways:

사전학습 덕분에 BLEURT는 새로운 task에 빠르게 적응할 수 있다. BLEURT는 합성 데이터와 WMT 데이터에 총 2번 사전학습 함으로써 학습 데이터 없이도 모든 task에서 괜찮은 결과를 보여 준다.

5.4 Ablation Experiments

Examples

그림 4는 WMT 2017에 진행한 ablation 실험을 보여주며, 각 사전학습 task의 상대적 중요성을 보여준다. 왼쪽에서는 BLEURT이 하나의 task에 대해 사전학습된 것과 아닌 것의 차이를 보여준다. 오른쪽은 full BLEURT와 하나를 제외한 모든 task에 사전학습된 BLEURT를 비교한다. BERTscore, entailment, 역 벅역 score에 사전학습하는 것은 성능 향상을 이끌어낸다(비슷하게, 이를 없애는 것은 BLEURT의 성능을 낮춘다). 반대로, BLEU와 ROUGE는 음의 영향력을 갖는다. 높은 품질의 signal 하에서 사전학습하는 것은 BLEURT에 도움이 되지만, 사람의 평가와 낮은 상관관계를 갖는 평가방법은 모델의 성능을 떨어뜨릴 수 있다.


6. 관련 연구(Related Work)

WMT shared metrics competition은 많은 학습된 평가방법의 생성에 영감을 주었다. 최근 MoverScore와 같은 다른 평가방법도 소개되었는데, 이는 문맥적 embedding과 Earth Mover’s Distance를 결합한 것이다. 우리는 head-to-head 실험을 제공하여 실험과 최고 성능의 평가방법을 비교하였다. 다른 접근법은 품질을 직접 추정하지는 않지만, 추출이나 질답을 대안으로 쓸 수 있다. 이는 이 연구에 상호 보완을 할 수 있다.

평가를 위해 BERT를 사용하는 최근 연구들이 있다. BERTScore는 BLEU의 hard n-gram overlap을 BERT embedding을 사용하여 soft-overlap으로 대체하였다. 이는 본 연구 전체에서 사용되었다. Bertr과 YiSi는 유사성을 잡아내기 위해 역시 BERT embedding을 사용하였다. SumQE는 품질 추정을 위해 BERT를 미세조정했다.
이 논문의 초점은 다르다$-$이 논문에서는 전통적인 IID 실험 setup에서 state-of-the-art뿐만 아니라 학습 데이터가 분포를 벗어나거나 부족한 경우에서도 평가방법을 학습시켰다. NLG 문맥에서 사전학습과 추론의 영역을 탐사하였다.

이전 연구들은 참조가 없는 평가를 위해 noising을 사용하였다. Noisy한 사전학습은 의역과 같은 다른 task를 위해 제안되었지만 일반적으로 합성 데이터에는 그렇지 않았다. 의역과 perturbation으로 합성 데이터를 생성하는 것은 일반적으로 적대적 예시를 생성하는 데 사용되며, 이는 (이) 연구의 파향선이다.


7. 결론(Conclusion)

영어를 위한 참조 기반 텍스트 생성 평가방법인 BLEURT를 제안하였다. 이 평가방법은 end-to-end 방식이미 때문에, BLEURT는 높은 정확도로 인간 평가를 모델링할 수 있다. 더욱이, 사전학습은 특히 도메인과 품질 이탈이 있는 경우에도 강건성을 가진다. 추후 연구 방향은 다중 언어 NLG 평가를 포함하며, 사람과 분류기 모두를 포함하는 혼합 방식이 될 것이다.

Acknowledgements

언제나 있는 감사의 인사


Refenrences

논문 참조. 많은 레퍼런스가 있다.


Appendix A Implementation Details of the Pre-Training Phase

이 섹션에서는 본문에서 기술된 사전학습 기술에 대한 상세를 설명한다.

A.1. Data Generation

Random Masking:

2개의 masking 전략을 사용했다. 두 경우 모두 15개의 mask를 생성한다.

  1. 문장에서 임의의 단어를 선택하여 mask(각 토큰당 1개)로 대체한다. 따라서 mask가 문장에 산재되어 있다.
  2. 두 번째 전략은 연속적인 sequence를 생성한다: 처음 위치 $s$에서 길이 $l$만큼을 균등분포로 선택하여 그 안의 모든 token을 mask로 대체한다.

언어모델을 한 번 실행시키고 각 위치에서 가장 (원래 단어였을 것 같은) token을 선택하는 대신, 크기 8의 beam search를 사용했다. 이는 , , ,와 같은 반복적인 sequence를 피하고 일관성을 갖도록 강제한다.

Backtranslation:

영어-프랑스어를 고려한다.

정방향 번역 모델과 역방향 번역 모델이 주어졌을 때, $\tilde{z}$를 다음과 같이 생성한다:

[\tilde{z} = \text{argmax}{z{en}} P_{fr \to en}(z_{en} \vert z^*_{fr})]

[where \ z^*{fr} = \text{argmax} P{fr \rightarrow en}(z_{fr} \vert z)]

[\text{forward translation model: } P_{en \rightarrow fr}(z_{fr} \vert z_{en})]

[\text{backward translation model: } P_{fr \rightarrow en}(z_{en} \vert z_{fr})]

번역 모델로는 tensor2rensor framework로 영어-독일어를 사용하여 학습된 Transformer를 사용했다.

Word dropping:

합성 예시 $(z, \tilde{z})$가 주어질 때 $\tilde{z}$에서 임의로 단어들을 빼서 $(z, \tilde{z}^{‘})$ 쌍을 생성한다. 탈락시키는 단어의 수는 문장 길이를 최대치로 균등하게 정했다. 이러한 변형을 이전 방법과 같이 생성된 데이터의 30%에 적용하였다.

A.2 Pre-Training Tasks

이제 사전학습을 위해 사용한 signal의 상세를 살펴본다.

Automatic Metrics:

표에서 보았듯이, BLEU, ROUGE, BERTscore 3가지 signal을 사용하였다.

  • BLEU에 대해서는, 원본 Moses SENTENCEBLEU 구현을 사용, Moses tokenizer와 기본 parameter를 사용하였다.
  • ROUGE에 대해서는, ROUGE-N의 seq2seq 구현을 사용하였다.
  • BERTscore는 BERT-large uncased에 기반한 custom 구현을 사용하였다.

ROUGE와 BERTscore는 precision, recall, F-score 3개의 점수를 반환한다. 이 3가지를 모두 사용한다.

Backtranslation Likelihood:

custom Transformer 모델을 사용하여 tensor2tensor framework를 사용, 영어$\leftrightarrow$프랑스어에서 학습시켜 모든 loss를 계산하였다.

Normalization:

모든 회귀 label은 학습 전 정규화되었다.

A.3 Modeling

Setting the weights of the pre-training tasks:

BLEURT의 성능을 WMT 17의 validation set에서 최적화하는 $\gamma_k$를 grid search로 찾아 정했다. grid의 크기를 줄이기 위해 같은 weight를 공유하는 다음 사전학습 그룹을 만들었다.

[\tau_{\text{BLEU}}, \tau_{\text{ROUGE}}, \tau_{\text{BERTscore}}]

[\tau_{\text{en-fr}, z \vert \tilde{z}}, \ \tau_{\text{en-fr}, \tilde{z} \vert z}, \ \tau_{\text{en-de}, z \vert \tilde{z}}, \ \tau_{\text{en-de}, \tilde{z} \vert z}]

[\tau_{\text{entail}}, \tau_{\text{backtran_flag}}]

Appendix B Experiments–Supplementary Material

B.1 Training Setup for All Experiments

BERT’s의 기본 설정을 따라 Adam optimizer, learning rate 1e-5, batch size 32를 사용했다. 다른 설정은

  • 8만 training step
  • 4만 step의 미세조정

학습과 평가를 병행하여 매 1500 step마다 checkpoint를 저장, 가장 괜찮은 validation 결과를 보인 것을 최종 선택한다.

하드웨어는 학습에 Google Cloud TPUs v2, 평가에는 Nvidia Tesla V100 가속기를 사용했다. 코드는 Python 2.7과 Tensorflow 1.15 버전이다.

B.2 WMT Metric Shared Task

Metrics.

평가방법은 여러 연도에 걸쳐서 평가 시스템을 비교하는 데 사용된다. organizer는 2017년의 모든 부분에 대해 정규화된 인간 평가와 연관한 Pearson’s correlation을 사용한다. 그리고 “DARR”이라 칭하는 Kendall’s Tau의 개조 버전을 2018년과 2019년의 인간 평가와의 연관성을 비교한다.
organizer는 같은 참조 부분에 대한 모든 번역을 모아서 가능한 모든 쌍 조합을 찾아(translation1, translation2) 100점 만점에 25점 이하인 “비슷한” 점수를 가진 모든 쌍을 제거했다.
그리고 남은 쌍에 대해, 번역이 인간 평가와 후보 평가방법 모두에서 최고점을 갖는 것을 제일 좋은 번역이라 한다.

|Concordant|를 NLG 평가방법이 ‘agree’하는 쌍의 수라 하고 |Discordant|를 ‘disagree’하는 쌍의 수라 할 때 점수는 다음과 같다.

[ \text{Concordant} - \text{Discordant} \over \text{Concordant} + \text{Discordant} ]

25점 필터의 아이디어는 WMT 2018과 2019의 평가 데이터가 noisy하기 때문에 평가를 좀 더 강건하게 하는 것이다.
Kendall’s Tau는 이상적이지만, 필터를 사용하지 않는다.

Training setup.

train/validation set을 분리하기 위해 데이터셋에 누수가 없는 고정 비율을 쓰는 방법을 사용했다(train, validation 예시는 같은 출처를 공요한다). 2017년과 2018년의 validation의 10%를, 2019년의 5%를 사용했다.
여기서 모든 validation data에서 가장 높은 Kendall Tau 점수를 낸 모델을 결과로 표시하였다. 각 사전학습 task에 연관된 weights는 WMT 2017년의 train/validation setup을 사용하여 grid search를 통해 설정하였다.

Baselines.

3개의 평가방법(sentenceBLEU의 Moses 구현, BERTscore, MoverScore)을 사용하였고 이는 모두 온라인으로 사용 가능하다. sentenceBLEU를 계산하기 전 Moses tokenizer를 참조와 후보 segment에서 실행하였다.

B.3 Robustness to Quality Drift

Data Re-sampling Methodology:

training/test set을 분리하여 샘플링하였다. 10개의 동일한 크기의 bin으로 데이터를 나누고, train/test 에 대해 각각 $1\over B^{\alpha}$와 $1\over (11-B)^{\alpha}$의 확률로 샘플링하였다. $B$는 1~10의 bin 번호, $\alpha$는 미리 정의된 skew factor로 drift를 조절한다. 0은 아무 영향이 없고(ratings은 0을 중심으로 함), 3.0은 극단적인 차이(difference)를 만든다. $\alpha$가 증가함에 따라 데이터셋의 크기는 줄어든다: 5344개의 training 샘플에 대해 각각 다음과 같은 설정으로 실험하였다.

alpha dataset ratio
0.5 50.7%
1.0 30.3%
1.5 20.4%
3.0 11.9%

B.4 Ablation Experiment–How Much Pre-Training Time is Necessary?

사전학습 시간과 downstream 정확도의 관계를 이해하기 위해, 사전학습 횟수가 다른 여러 버전의 BLEURT를 학습시켜 WMT17 데이터에 미세조정시켰다. 아래 그림이 그 결과를 보여준다. 첫 40만 step에서 가장 많은 발전이 있고, 이는 합성 데이터셋의 2 epoch에 해당한다.

Examples

Comment  Read more

GraphSAGE (Inductive Representation Learning on Large Graphs) 설명

|

본 글에서는 2017년에 발표된 Inductive Representation Learning on Large Graphs란 논문에 대한 Review를 진행할 것이다.

torch_geomectric을 이용하여 GraphSAGE를 사용하는 방법에 대해서 간단하게 Github에 올려두었으니 참고해도 좋을 것이다.


Inductive Representation Learning on Large Graphs Paper Review

1. Introduction

큰 Graph에서 Node의 저차원 벡터 임베딩은 다양한 예측 및 Graph 분석 과제를 위한 Feature Input으로 굉장히 유용하다는 것이 증명되어 왔다. Node 임베딩의 기본적인 아이디어는 Node의 Graph 이웃에 대한 고차원적 정보를 Dense한 벡터 임베딩으로 만드는 차원 축소 기법을 사용하는 것이다. 이러한 Node 임베딩은 Downstream 머신러닝 시스템에 적용될 수 있고 Node 분류, 클러스터링, Link 예측 등의 문제에 도움이 될 수 있다.

하지만 이전의 연구들은 고정된 단일 Graph로부터 Node를 임베딩하는 것에 집중하였는데 실제 현실에서는 새로운 Node와 (sub) Graph가 빠르게 생성되는 것이 일반적이다. (Youtube를 생각해보라!) 고정된 Graph에서 추론을 행하는 것을 transductive한 경우라고 부르고 틀에서 벗어나 새로운 Node에 대해서도 합리적인 추론을 행할 수 있는 경우를 inductive라고 부른다. Node 임베딩을 생성하기 위한 inductive한 접근은 또한 같은 형태의 feature가 존재할 때 Graph 전체에 대해 일반화된 결과를 제공하게 된다.

이러한 inductive Node 임베딩 문제는 굉장히 어렵다. 왜냐하면 지금껏 본 적이 없는 Node에 대해 일반화를 하는 것은 이미 알고리즘이 최적화한 Node 임베딩에 대해 새롭게 관측된 subgraph를 맞추는 (align) 작업이 필요하기 때문이다. inductive 프레임워크는 반드시 Node의 Graph 내에서의 지역적인 역할과 글로벌한 위치 모두를 정의할 수 있는 Node의 이웃의 구조적인 특성을 학습해야 한다.

Node 임베딩을 생성하기 위한 대부분의 기존 접근은 본질적으로 transductive하다. 다수의 이러한 접근 방법들은 행렬 분해 기반의 목적함수를 사용하여 각 Node에 대해 임베딩을 직접적으로 최적화하고 관측되지 않은 데이터를 일반화하지 않는다. 왜냐하면 이러한 방법들은 고정된 단일 Graph에 대해 예측하기 때문이다.

이러한 접근법들은 inductive한 방법에서 작동하도록 수정될 수 있는데, 이를 위해서는 굉장한 연산량이 수반되고 새로운 예측이 만들어지기 전에 추가적인 Gradient Descent 단계를 필요로 한다. 최근에는 Graph Convolution 연산을 이용한 방법들이 논의되었다. 지금까지는 Graph Convolutional Network 또한 transductive한 환경에서만 적용되었다. 본 논문에서 우리는 이 GCN을 inductive unsupervised learning으로 확장하고 단순한 합성곱 이상의 학습 가능한 Aggregation 함수를 사용하여 GCN을 일반화하는 프레임워크를 제안할 것이다.

본 논문에서는 Inductive Node Embedding을 위해 일반화된 프레임워크, Graph Sage를 제안한다. 이름은 SAmple과 aggreGatE를 결합하였다. 좀 끼워 맞춘 느낌이 들긴 하다. 행렬 분해에 기반한 임베딩 접근법과 달리 관측되지 않은 Node에서도 일반화할 수 있는 임베딩 함수를 학습하기 위해 Node Feature(텍스트, Node 프로필 정보, Node degree 등)를 Leverage한다. 학습 알고리즘에 Node Feature를 통합함으로써 우리는 이웃한 Node Feature의 분포와 각 Node의 이웃에 대한 위상적인 구조를 동시에 학습할 수 있다. 풍부한 Feature를 가진 Graph에 집중하여 우리의 접근법은 또한 (Node Degree와 같이) 모든 Graph에 존재하는 구조적인 Feature를 활용할 수 있다. 따라서 본 논문의 알고리즘은 Node Feature가 존재하지 않는 Graph에도 적용될 수 있다.

각 Node에 대한 고유의 임베딩 벡터를 학습하는 대신에, 우리는 Node의 지역 이웃으로부터 Feature 정보를 규합하는 Aggregator Function의 집합을 학습한다. 중요한 포인트이다. 왜냐하면 이 컨셉을 통해 각 Node에 귀속된 임베딩 벡터의 한계를 돌파할 수 있기 때문이다.


논문 참조


3. Proposed method: GraphSAGE

우리의 접근법의 가장 중요한 아이디어는 Node의 지역 이웃으로부터 Feature Information을 통합하는 방법에 대해 학습한다는 것이다. 먼저 1.3.1에서는 GraphSAGE 모델의 파라미터가 이미 학습되어 있다고 가정하고 GraphSAGE의 임베딩 생성 알고리즘에 대해 설명할 것이다. 이후 1.3.2에서는 Stochastic Gradient DescentBackpropagation 기술을 통해 모델이 어떻게 학습되는지 설명할 것이다.

3.1. Embedding Generation (i.e. forward propagation) Algorithm

본 섹션에서는 일단 모델의 파라미터가 모드 학습되었고 고정되어 있다고 가정하고 Embedding Generation 혹은 Propgation 알고리즘에 대해 설명할 것이다. 일단 2종류의 파라미터가 있다.

첫 번째는 $K$ 개의 Aggregator Function으로, $AGGREGATE_k, \forall k \in {1, …, K}$ 라고 표현되며, 이 함수는 Node 이웃으로부터 정보를 통합하는 역할을 수행한다.

두 번째는 Weight Matrices의 집합으로, $\mathbf{W}^k, \forall k \in {1, …, K}$ 라고 표현되며, 이들은 모델의 다른 layer나 search depth 사이에서 정보를 전달하는데 사용된다. 다음은 파라미터 학습 과정을 나타낸 것이다.

위에서 확인할 수 있는 직관은 각 iteration 혹은 search depth에서 Node는 그의 지역 이웃으로부터 정보들을 모으고, 이러한 과정이 반복되면서 Node는 Graph의 더 깊은 곳으로부터 정보를 증가시키면서 얻게 된다는 것이다.

알고리즘1은 Graph 구조와 Node Features가 Input으로 주어졌을 때의 임베딩 생성 과정에 대해 기술하고 있다. 아래에서는 Mini-batch 환경에서 어떻게 일반화할 수 있을지 설명할 것이다. 알고리즘1의 바깥 Loop의 각 단계를 살펴보면, $\mathbf{h}^k$ 는 그 단계에서의 Node의 Representation을 의미한다.

첫 번째로, 각 Node $v$ 는 그것의 바로 이웃(Immediate Neighborhood)에 속하는 Node들의 Representation을 하나의 벡터 $\mathbf{h}_{\mathcal{N}(v)}^{k-1}$ 로 합산한다. 이 때 이 합산 단계는 바깥 Loop의 이전 반복 단계(k-1)에서 생성된 Representation에 의존하고 $k=0$ 일 때는 Input Node Feature가 Base Representation의 역할을 하게 된다.

이웃한 Feature 벡터들을 모두 통합한 다음, 모델은 Node의 현재 Representation과 통합된 이웃 벡터를 결합한 뒤 비선형 활성화 함수를 통과시킨다.

[\mathbf{h}v^{k-1}, \mathbf{h}{\mathcal{N}(v)}^{k-1}]

최종적으로 depth $K$ 에 도달하였을 때의 Representation은 아래와 같이 표현할 수 있다.

[\mathbf{z}_v = \mathbf{h}_v^K, \forall v \in \mathcal{V}]

사실 Aggregator Function은 다양하게 변형될 수 있으며, 여러 방법에 대해서는 1.3.3에서 다루도록 하겠다.

알고리즘1을 Mini-batch 환경으로 확장하기 위해서는 우리는 먼저 depth $K$ 까지 필요한 이웃 집합을 추출해야 한다. 이후 안쪽 Loop(알고리즘1의 3번째 줄)를 실행하는데, 이 때 모든 Node를 반복하는 것이 아니라 각 depth에서의 반복(recursion)을 만족하는데 필요한 Represention에 대해서만 계산한다. (Appendix A 참조)

Relation to the Weisfeiler-Lehman Isomorphism Test
GraphSAGE 알고리즘은 개념적으로 Graph Isomorphism(동형 이성)을 테스트하는 고전적일 알고리즘에서 영감을 얻어 만들어졌다. 만약 위에서 확인한 알고리즘1에서 $K= \vert \mathcal{V} \vert$ 로 세팅하고 Weight Matrices를 단위 행렬로 설정하고 비선형적이지 않은 적절한 Hash 함수를 Aggregator로 사용한다면, 알고리즘1은 Naive Vertex Refinement라고 불리는 Weisfeiler-Lehman: WL Isomorphism Test의 Instance라고 생각할 수 있다.

이 테스트는 몇몇 경우에는 들어맞지 않지만, 여러 종류의 Graph에서는 유효하다. GraphSAGE는 Hash 함수를 학습 가능한 신경망 Aggregator로 대체한 WL Test의 연속형 근사에 해당한다. 물론 GraphSAGE는 Graph Isomorphism을 테스트하기 위해서 만들어진 것이 아니라 유용한 Node 표현을 생성하기 위함이다. 그럼에도 불구하고 GraphSAGE와 고전적인 WL Test 사이의 연결성은 Node 이웃들의 위상적인 구조를 학습하기 위한 본 알고리즘의 디자인의 기저에 깔려 있는 이론적 문맥을 이해하는 데에 있어 큰 도움을 준다.

Neighborhood Definition
본 연구에서 우리는 알고리즘1에서 기술한 것처럼 모든 이웃 집합을 사용하지 않고 고정된 크기의 이웃 집합을 샘플링하여 사용하였다. 이렇게 함으로써 각 Batch의 계산량을 동일하게 유지할 수 있었다.

다시 말해, $\mathcal{N}(v)$ 을 집합 ${u \in \mathcal{V}: (u, v) \in \mathcal{E}}$ 에서 각 반복 $k$ 에서 고정된 크기로 균일하게 뽑은 Sample이라고 정의할 수 있다.

이러한 샘플링 과정이 없으며, 각 Batch의 메모리와 실행 시간은 예측하기 힘들며 계산량 또한 엄청나다.

GraphSAGE의 per-batch space와 time complexity는 $O(\prod_{i=1}^K S_i)$ 로 고정되어 있으며, $S_i, i \in {1, …, K}$와 $K$ 는 User-specified 상수이다.

실제 적용할 때, $K=2$ 와 $S_1 * S_2 <= 500$ 으로 했을 때 좋은 성능을 보였다. (자세한 사항은 1.4.4를 참조)

3.2. Learning the Paremeters of GraphSAGE

완전한 비지도 학습 상황에서 유용하고 예측 능력이 있는 Representation을 학습하기 위해 우리는 Graph 기반의 Loss 함수를 $\mathbf{z}_u, \forall u \in \mathcal{V}$ 라는 Output Represnetation에 적용하고, Weight Matrices $\mathbf{W}^k, \forall k \in {1, …, K}$ 및 Stochastic Gradient Descent를 통해 Aggregator Funciton의 파라미터를 튜닝해야 한다.

Graph 기반의 Loss 함수는 인접한 Node들이 유사한 Representation을 갖도록 하게 하고 서로 멀리 떨어져 있는 Node들은 다른 Representation을 갖게 만든다.

[J_{\mathcal{G}} = \log (\sigma (\mathbf{z}u^T \mathbf{z}_v)) - Q \cdot \mathbb{E}{v_n \sim P_n(v)} \log (\sigma (\mathbf{z}u^T \mathbf{z}{v_n}))]

이 때 $v$ 는 고정된 길이의 Random Walk 에서 $u$ 근처에서 동시에 발생한 Node를 의미한다. $P_n$ 은 Negative Sampling Distribution을 $Q$ 는 Negative Sample의 개수를 의미한다.

중요한 것은 이전의 여러 임베딩 방법론에서와는 다르게, Loss 함수에 집어넣는 Representation $\mathbf{z}_u$ 가 Embedding Look-up을 통해 각 Node를 위한 고유의 Embedding을 학습하는 방식으로 형성되지 않는다. Node의 지역 이웃 안에서 포함된 feature로 부터 생성된다. (the representations z are generated from the features contained within a node’s local neighborhood)

이러한 비지도 학습 세팅은 Node Feature가 서비스 혹은 정적인 Repository에 있는 downstream 머신러닝 application에 적용될 때의 상황을 모방하게 된다. 위에서 설명한 Representation이 특정한, 구체적인 downstream task에 이용되어야 할 경우, 앞서 보았던 비지도 Loss는 그 일에 더욱 적합한 (예: cross-entropy loss) 목적함수로 대체되거나 변형될 수 있을 것이다.

3.3. Aggregator Architectures

N차원의 격자 구조 데이터를 이용한 머신러닝 예(텍스트, 이미지 등)들과 달리, Node의 이웃들은 자연적인 어떤 순서를 갖고 있지 않다. 따라서 알고리즘1에서 보았던 Aggregator Function은 반드시 순서가 정해져있지 않은 벡터의 집합에 대해 연산을 수행해야 한다.

이상적으로는 Aggregator Function이 여전히 학습이 가능하고 수준 높은 Representational Capacity를 갖고 있으면서도 대칭적인 형태를 띠고 있으면 좋을 것이다. Input이 순서를 바꿔도 상관 없게 말이다.

Aggregator Funcion의 대칭성은 우리의 신경망 모델이 임의의 순서를 갖고 있는 Node 이웃 feature 집합에도 학습/적용될 수 있게 한다. 본 논문은 이에 대해 3가지 후보를 검증해 보았다.

1) Mean Aggregator
단지 $h_u^{k-1}, \forall u \in \mathcal{N}(v)$ 에 있는 벡터의 원소 평균을 취한 함수이다.

Mean Aggregator는 Transductive GCN 프레임워크에서 사용되는 합성곱 순전파 규칙을 거의 따른다. 특히 우리는 알고리즘의 4~5줄을 다음과 같이 변형하면 GCN의 inductive한 변형 버전을 만들어낼 수 있다.

[h_v^k \leftarrow \sigma ( \mathbf{W} \cdot mean( { h_v^{k-1} } \cup { h_u^{k-1} } ),]

[\forall u \in \mathcal{N}(v)]

우리는 위 식이 Localized Spectral Convolution의 개략적인 선형 근사이기 때문에 이를 수정된 평균 기반 Aggregator Convolutional이라고 부를 것이다. (Modified Mean-based Aggregator Convolutional)

2) LSTM Aggregator
앞서 확인한 형태에 비해 조금 더 복잡한 형태의 함수이다. LSTM의 경우 표현력에 있어서 장점을 지니지만 본질적으로 대칭적이지 않기 때문에 permutation invariant 하지 않다.

따라서 본 논문에서는 LSTM을 Node의 이웃의 Random Permutation에 적용함으로써 순서가 없는 벡터 집합에 대해서도 LSTM이 잘 동작하도록 하였다.

3) Pooling Aggregator
Pooling Aggregator는 대칭적이면서도 학습 가능하다. 각 이웃의 벡터는 독립적으로 fully-connected된 신경망에 투입된다. 이후 이웃 집합에 Elementwise max-pooling 연산이 적용되어 정보를 통합한다.

[AGGREGATE^{pool}k = max({ \sigma (\mathbf{W}{pool} \mathbf{h}_{u_i}^k + \mathbf{b}) })]

[\forall u_i \in \mathcal{N}(v)]

이론 상으로 max-pooling 이전에 여러 겹의 layer를 쌓을 수도 있지만, 본 논문에서는 간단히 1개의 layer 만을 사용하였는데, 이 방법은 효율성 측면에서 더 나은 모습을 보여준다.

계산된 각 피쳐에 대해 max-pooling 연산을 적용함으로써 모델은 이웃 집합의 다른 측면을 효과적으로 잡아내게 된다. 물론 이 때 어떠한 대칭 벡터 함수든지 max 연산자 대신 사용할 수 있다.

본 논문에서는 max-pooling과 mean-pooling 사이에 있어 큰 차이를 발견하지 못하였고 이후 논문에서는 max-pooling을 적용하는 것으로 과정을 통일하였다.


4. Experiments

본 논문에서 GraphSAGE의 성능은 총 3가지의 벤치마크 task에서 평가되었다.

(1) Web of Science citation 데이터셋을 활용하여 학술 논문을 여러 다른 분류하는 것

(2) Reddit에 있는 게시물들이 속한 커뮤니티를 구분하는 것

(3) 다양한 생물학적 Protein-protein interaction 그래프 속에서 protein 함수를 구별하는 것

본 챕터의 경우 논문을 직접 참고하길 바라며, 몇 가지 포인트에 대해서만 정리를 하도록 하겠다.

일단, GraphSAGE의 비교 군으로 총 4가지 방법론이 사용되었다. 완전 무작위, 그래프 구조를 고려하지 않고 raw feature만을 사용한 로지스틱 회귀, DeepWalk 그리고 마지막으로 DeepWalk + raw features, 이렇게 4가지이다.

GraphSAGE도 총 4가지 스타일을 실험하였다. GCN구조, mean aggregator 구조, LSTM aggregator 구조, pooling aggregator 구조 이렇게 4가지이다. vanilla Gradient Descent Optimizer를 사용한 DeepWalk를 제외하고는 모두 Adam Opimizer를 적용하였다. 또한 공평한 비교를 위해 모든 모델은 동일한 미니배치 환경에서 작동하였다.

아래는 테스트 결과이다.

LSTM, Pooling 기반의 Aggregator가 가장 좋은 성능을 보여주었다. K=2로 설정하는 것이 효율성 측면에서 좋은 모습을 보여주었고, 이웃 개체들을 sub-sampling하는 것은 비록 분산을 크게 만들지만 시간을 크게 단축되기 때문에 꼭 필요한 단계라고 할 수 있겠다.


5. Theoretical Analysis

본 Chapter에서는 어떻게 GraphSAGE가 내재적으로는 feature에 의존하면서도 Graph 구조에 대해 학습할 수 있는지에 대해 설명하도록 하겠다.

케이스 스터디의 일환으로, 본 논문에서는 GraphSAGE가 Node의 Clustering Coefficient를 예측할 수 있는지에 대해 알아보았다. Clustering Coefficient는 Node의 지역 이웃들이 얼마나 잘 모여있는지를 측정하는 기준이며 더욱 복잡한 구조적 모티프를위한 토대 역할을 한다.

우리는 GraphSAGE의 임베딩 생성 알고리즘(1.3.1의 알고리즘1)이 Clustering Coefficient를 근사할 수 있음을 증명할 수 있다.

Theorem 1
$x_v$ 가 알고리즘1에서의 feature input을 의미한다고 하자. 모든 Node 쌍에 대해 아래와 같은 조건을 만족하는 고정된 양의 상수 $C$ 가 존재한다고 가정한다.

[C \in \mathbb{R}^+, \Vert x_v - x_{v^{‘}} \Vert_2 > C]

$K = 4$ 반복 후에 알고리즘1에 대한 파라미터 학습이 이루어졌을 때 $\forall \epsilon > 0$ 에 대해 아래 식이 존재한다.

[\vert z_v - c_v \vert < \epsilon, \forall v \in \mathcal{V}]

이 때 $z_v$ 는 알고리즘1에 의해 생성된 최종 아웃풋 벡터, 즉 Embedding 벡터이고 $c_v$ 는 Clustering Coefficient을 의미한다.

위 정리는, 만약 모든 Node의 feature가 고유한 값을 가질 때, Graph 속에서 Clustering Coefficient을 근사할 수 있는 파라미터 세팅이 존재함을 의미한다. 이에 대한 증명은 Appendix에서 확인할 수 있다.

증명의 기본적인 아이디어는, 각 Node가 고유한 feature representation을 갖고 있다면 우리는 Node를 indicator 벡터로 연결시키고 이 Node의 이웃을 찾는 방법에 대해 학습할 수 있다는 것이다. 또한 이 증명을 통해 위 정리는 Pooling Aggregator의 몇몇 특징에 의존적임을 밝혔는데, 이를 통해 Pooling을 이용한 GraphSAGE가 다른 GCN이나 Mean-based Aggregator에 비해 더 좋은 성능을 보여준다는 인사이트를 얻을 수 있다.


6. Conclusion

GraphSAGE는 directed 혹은 multi-model graph를 통합하는 것과 같이 무궁무진한 발전 가능성이 있는 모델이다. 최적화를 위해 Non-uniform Neighborhood Sampling 함수를 연구해보는 것과 같이 굉장히 흥미로운 주제들도 남아있다.


Reference

1) 논문 원본
2) 논문 원본 내 참고 사이트
3) 논문 저자 깃헙

Comment  Read more

Graph Convolutional Matrix Completion (GCMC) 설명

|

본 글은 2017년에 발표된 Graph Convolutional Matrix Completion에 대한 리뷰를 담은 글이다. Graph Neural Network에 대해서는 최근 수 년간 여러 연구가 이루어져 왔으며, 이 방법론은 다양한 분야에서 기존과는 사뭇 다른 새로운 해결 방안에 대해 제시하고 있다.

본 논문은 이러한 Graph 구조의 방법론을 추천 시스템, 그 중에서도 Matrix Factorization에 투영시킨 과정에 대해 설명하고 있다. 비록 적용에 있어 일부 한계점이 존재하기도 하지만, 추가적인 개선이 이루어진다면 여러 추천 시스템에서 참고할만한 중요한 인사이트들을 담고 있다고 할 수 있다. 먼저 논문 리뷰를 진행해보자.


1. Introduction

본 논문에서 우리는 Matrix Completion을 Graph에서의 Link 예측 문제라고 바라보고 있다. Collaborative Filtering에서의 상호작용 데이터는 Link로 표현되는 평점/구매 기록 그리고 User와 Item Node 사이의 Bipartite Graph (이분 그래프)로 표현된다. 컨텐츠 정보는 Node Feature로서 표현될 수 있다. 이제 평점을 예측하는 문제는 이분 User-Item Graph에서 라벨이 존재하는 Link를 예측하는 문제로 귀결된다.

본 논문에서는 Graph에 대한 최근 딥러닝 발전 과정 속에서 설계한, Matrix Completion을 위한 Graph-based Auto-encoder 프레임워크인 Graph Convolutional Matrix Completion: GCMC를 제안한다. 이 때 Auto-encoder는 User와 Item Node의 잠재 벡터를 생성하는데, 이는 이분 상호작용 그래프에서느 Message Passing의 형태로 구현된다. 이 User와 Item (잠재) 표현은 Bilinear Decoder를 통해 평점 Link를 재구성(Reconstruct)하는데 이용된다.

추천 시스템에서 일반적으로 사업자는 특정 User에게 Item Pool에서 이 User에게 잘 어울린다고 생각하는 특정 Item를 골라서 제시하게 된다. 그런데 이러한 논리의 기저에는 유사한 User들은 유사한 Item들을 좋아할 것이라는, 그 User와 Item가 갖고 있는 근본적인 특성의 동질성이 취향에 발현될 것이라는 전제가 깔려있다. 이전의 Matrix Factorization 기반 방법론들은 User/Item Feature의 잠재벡터의 내적 계산을 통해 이러한 철학을 구현하였다.

본 논문에서 제시한 GCMC도 이러한 철학을 계승하고 있다. Graph 구조라고 해서 이 틀을 벗어나지는 않는 것이다. 가장 큰 차이는 바로 위 단락에서 언급한 Message Passing이 될 것인데, 이에 대해서는 추후에 자세히 설명할 것이다.

Matrix Completion 문제를 이분 그래프에서의 Link 예측 문제로 형상화하는 것은 추천 그래프가 구조화된 외부 정보(예: Social Network)를 동반할 때 더욱 빛을 발하게 된다. 이렇게 외부 정보를 추가하는 것은 Cold Start 문제를 완화하는데 도움을 준다.


평점 행렬 $M$ 은 $N_u, N_v$ 의 크기를 가졌고, 행과 열의 수는 각각 User/Item의 수를 의미한다. 평점 행렬의 원소인 $M_{ij}$ 는 관측된 평점 값을 의미하는데, 이 값은 이산적인 (예: 1 ~ 5점) 값이고 미관측된 값은 0으로 처리한다. 최종 목적은 관측되지 않은 값을 예측하는 것이다.

Graph Network의 핵심 중 하나는 이러한 상호작용 데이터를 Undirected Graph (비방향성 그래프)로 표현한다는 것인데, 기호로 나타내자면 아래와 같다.

[G = (\mathcal{W}, \mathcal{E}, \mathcal{R}),]

[\mathcal{W} = \mathcal{U} \cup \mathcal{V},]

[(u_i, r, v_j) \in \mathcal{E},]

[r \in [1, …, R] = \mathcal{R}]

$\mathcal{W}, \mathcal{E}, \mathcal{R}$ 은 차례 대로, User/Item 집합, Edge 집합, Rating 집합을 의미한다. 즉, Graph라는 존재는 이와 같이 Node, Edge, Link로 이루어져 있다는 것을 의미한다.

2.1. Graph Auto-encoders

Graph Auto-encoder는 크게 2가지로 구성된다. 첫 번째는 Graph Encoder 모델로, $Z=f(X, A)$ 라고 정의할 수 있겠다. 이 때 각각의 Shape은 아래와 같다.

행렬 역할 Shape
$Z$ Node Embedding Matrix $N, E$
$X$ 원본 Feature Matrix $N, D$
$A$ Graph Adjacency Matrix $N, N$

$D$ 는 모든 변수의 개수를 의미하며, $N$ 은 $N_u + N_v$ 를 의미한다.

두 번째는 Pairwise Decoder 모델로 $\hat{A} = g(Z) $ 로 정의할 수 있으며 Node Embedding 쌍 $(z_i, z_j)$ 를 Input으로 받아 Adjacency Matrix의 원소인 $\hat{A}_{ij}$ 를 예측하는 역할을 수행하게 된다.

$X$ 는 원본 Feature를 의미하고 이 행렬의 Shape은 $(N=N_u + N_v, D)$ 이다. 한 가지 궁금할 수 있는 부분은 이와 같은 표기에서는 User Feature의 변수의 수와 Item Feature의 변수의 수가 $D$ 로 동일한 것처럼 보이는데, 다음 Chapter를 보면 그렇게 만들 필요는 없다고 설명이 나온다. 처음부터 설명해주는 친절함은 조금 부족했던 것 같다. 어찌 되었든 여기에서의 $D$ 는 편의를 위해 통일 된 것으로 생각하면 좋을 것 같다.

$A$ 는 Adjacency Matrix (인접 행렬)를 의미하는데, 평점 데이터를 기반으로 설명하자면 이 $A$ 는 여러 조각으로 나뉠 수 있다. 즉, 1점의 평점을 준 Link를 모두 모은 인접 행렬을 $M_1$ 이라고 하고, R점의 평점을 준 Link를 모두 모은 인접 행렬을 $M_R$ 이라고 한다면, 우리는 Encoder 모델의 함수를 다음과 같이 달리 표현할 수 있을 것이다.

[Z = f(X, M_1, …, M_R)]

$Z$ 는 $[U, V]$ 로 표현되는데, User Embedding Matrix와 Item Embedding Matrix를 쌓아놓은 형태이다.

최종적으로 해결해야 하는 문제는 예상하는 그대로이다. Decoder $g(U, V)$ 는 $\hat{M}$ 이라는 평점에 대한 예측 값을 생성하게 되고, 이 행렬의 Shape은 당연히 기존 $M$ 과 동일한 $(N_u, N_v)$ 이다.

예측 행렬 $\hat{M}$ 과 관측된 Ground-Truth 행렬 $M$ 사이의 Reconstruction Error 를 줄이는 것이 본 모델의 목적이다.

2.2. Graph Convolutional Encoder

지금부터는 조금 더 진보된 형태의 Encoder 모델을 소개할 것이다. 이 모델은 Graph에서 location에 대한 효율적인 Weight Sharing을 특징으로 한다. 또한 이 모델은 각 평점 종류(Edge Type)에 대해 별도의 Processing Channel을 만든다. 즉 각각의 평점 종류(1점인지, 2점인지)에 따라 (형식은 같지만) 다른 처리 과정이 존재한다는 것이다.

Weight Sharing의 형식은 Graph 구조의 데이터에 직접적으로 작동하는 최근 CNN class에 영감을 받았는데, Graph Convolutional Layer가 Node의 1차 이웃만을 고려하여 지역 연산을 수행하면, 같은 Transformation이 Graph에 있는 모든 위치에서 수행된다는 것이다.

Graph 구조의 모델에 대해 처음 설명을 듣는다면 위 단락이 잘 이해가 되지 않을 수도 있다. 잠시 그림을 살펴보자.

User 1이 존재한다. 이 User는 총 3개의 Item에 대해 평점을 남겼는데, 이렇게 User 1이 평점을 남긴 Item을 우리는 1차 이웃이라고 부른다. 즉 User 1과 직접적인 관계를 맺고 있는 Node라고 할 수 있다. 그렇다면 2차 이웃은 무엇일까? User 1이 평점을 남긴 1차 이웃 Item이 직접적인 관계를 맺고 있는 User 집합이라고 할 수 있는데, 이들은 그림 상에서 초록색 원형으로 표시되었다. 3차 이웃은 이제 감이 올 것이다. 2차 이웃 User가 직접적으로 관계를 맺고 있는 Item 집합을 의미한다. 이렇게 차수를 높여감에 따라 우리가 알고 싶은 User 1의 관계의 깊이가 점점 깊어진다는 것을 알 수 있다. 더 깊게 알고 싶을 수록 연산량이 늘어나는 것은 당연한 숙제가 될 것이다.

그렇다면 하나 더, 위 그림에서 추론할 수 있는 것은 무엇일까? 간단하게 말해서 User 1은 파란색 상자로 표현한 Item 1, 2, 4 중에서 Item 1과 2에 대해서는 아주 좋은 평점을 남기지는 않았는데, User 2도 이와 유사한 평점을 남겼다. 그렇다면, 오직 이 Graph만 보았을 때는 User 1과 User 2가 나름 취향이 비슷할 수도 있을 것이다. 이 때 평점이 몇 점인지도 중요하지만 어떤 Item에 대해 평점을 남겼는지도 중요하다. 그 User의 행동 반경을 정의하는 단서가 되기 때문이다. 반대로 User 3은 User 1이 좋아했던 Item 4에 대해 안 좋은 평점을 남겼다. 어쩌면 이 두 User는 상극일지도 모른다.

다시 논문으로 돌아오겠다.

Local Graph Convolution은 Vector 값으로 만들어진 Message가 Graph의 모든 Edge를 타고 전달 및 변형되는 일종의 Message Passing의 형태로 볼 수 있다. 본 논문에서는 각 평점에 따라 별도의 Transformation을 행했다. Item j가 User i에게 주는 Edge-type Specific Message는 아래와 같은 형식으로 표현할 수 있다.

[\mu_{j \rightarrow i, r} = \frac {1} {c_{ij}} W_r x_j]

여기서 $c_{ij}$ 는 정규화 상수인데, 만드는 방법에는 2가지가 있다. Left Normalization을 택할 경우, $\vert{\mathcal{N}_i}\vert$ 을, Symmetric Normaliztion을 선택할 경우 $\vert{\mathcal{N}_i}\vert \vert \mathcal{N_j} \vert$ 로 택할 수 있다.

$\mathcal{N_i}$ 는 Node $i$ 의 이웃들의 집합을 의미한다. 따라서 위 기호는 그 이웃 집합의 길이를 의미하게 될 것이다. $W_r$ 은 Edge-type Specific Parameter를 의미한다. 참고로 뒤에 나올 $W$ 행렬과는 별개의 것이다. 논문에서 다소 혼란스럽게 적어 놓았으니 구별하길 바란다. $x_j$ 는 Node $j$ 의 (Initial) Feature 벡터를 의미한다. 이 예시에서는 Node $j$ 가 Item 이지만, 반대의 경우도 당연히 성립한다.

이렇게 $r$ 이라는 평점에서 Node $j$ 에서 Node $i$ 로 향하는 Message Passing을 정의하는 단계가 끝나면, 이제 $r$ 이라는 평점 하의 모든 이웃 $\mathcal{N_{i, r}}$ 의 입수되는 모든 Message를 규합해야 한다. 그렇게 합쳐서 아래와 같이 하나의 벡터 표현을 만들게 된다. 아래 벡터를 반드는 층을 Graph Convolution Layer라고 명명하겠다.

[h_i = \sigma [accum (\Sigma_{j \in \mathcal{N_{i, 1}}} \mu_{j \rightarrow i, 1}, …, \Sigma_{j \in \mathcal{N_{i, R}}} \mu_{j \rightarrow i, R}) ]]

평점의 종류가 총 $R$ 개라고 할 때 위 식은 모든 평점의 종류에 대해 Node $i$ 의 1차 이웃에 속하는 Item Node $j$ 들에 대해 모든 Message를 합치는 과정으로 설명할 수 있다. 합친다는 것을 의미하는 $accum$은 Stacking으로 생각할 수도 있고, Sum으로 생각할 수도 있는데, Sum이 좀 더 구현하기 편리하니 Sum으로 일단 생각해두자.

이제 최종적으로 Node $i$ 의 Embedding Vector를 생성하면 된다. 아래와 같이 만들 수 있다. 최종 Embedding Vector를 생성하는 아래 층은 Dense Layer라고 명명하겠다.

[u_i = \sigma(W h_i)]

Item Embedding Vector $v_j$ 역시 같은 Paramter 행렬 $W$ 에 의해 유사한 방식으로 생성된다. 만약 User, Item에 대한 Side Information, 즉 별개의 Feature Vector를 사용할 경우 이 Parameter 행렬 $W$ 는 User, Item에 따라 별도로 구성해야 할 것이다. ( $W_{user}, W_{item}$ )

여러 층을 추가하여 더욱 깊은 모델을 만들 수도 있고, Message Passing 구성을 위와 같이 하는 대신 새로운 신경망이나 Attention 모델을 통해 구성하는 방안도 생각해볼 수 있다. 그러나 본 논문에 따르면 위와 같이 구성하는 방법이 가장 효율적인 것으로 나타났다.

논문에서는 이렇게 소 Chapter를 마무리하는데, 보충 설명을 하도록 하겠다.

Message Passing 단위는 $\mu_{j \rightarrow i, r}$ 라는 벡터이다. 예시를 들어보자. 만약 평점이 1점, 2점 이렇게 2종류만 존재한다고 해보자. 그리고 User Node $i$ 가 1점을 준 Item Node는 $1, 2$ 이렇게 2가지가 있고, 2점을 준 Item Node는 $3$ 이렇게 1가지만 존재한다고 해보자.

그렇다면 User Node $i$ 의 이웃은 아래와 같이 구성할 수 있다.

위 그림과 같은 구조에서 우리는 다음과 같은 Message Passing 벡터를 얻을 수 있다.

[\mu_{1 \rightarrow i, 1}, \mu_{2 \rightarrow i, 1}, \mu_{3 \rightarrow i, 2}]

위 벡터들의 의미는 무엇일까? 위 3개의 벡터 중 첫 번째를 예시로 들어보자. $1$ 이라는 Item Node가 User $i$ 에게 미치는 영향으로 해석가능하다. 이 때 어떻게 영향을 미칠 것인가에 대해서는 $W_1$ Parameter 행렬이 역할을 수행하게 될 것이다. 그런데 User $i$ 에게 1점의 관계를 맺고 있는 Item Node는 총 2개이다. 따라서 앞서 보았던 $c_{ij}$라는 정규화 상수를 통해 영향의 크기를 분산시켜주는 것이다.

이렇게 만들어진 단위 벡터들은 Graph Convolution Layer에서 합쳐지고 최종적으로 User, Item Embedding Vector을 형성하게 된다.

2.3. Bilinear Decoder

행렬 분해를 기반으로 하는 추천 시스템에 대해 한 번이라고 공부를 해보았다면, 이전 Chapter에서 언급한 임베딩 벡터의 의미를 알아챘을 것이다. 가장 Classic하게 평점을 예측하는 방법은 User 임베딩 벡터와 Item 임베딩 벡터를 바로 내적 계산하는 것이다.

[\hat{y}_{ij} = u_i \cdot v_j]

본 논문에서는 이러한 역할을 수행하기 위해 Bilinear Decoder라는 형태를 제안한다. 이 때 각 평점 종류 마다 다른 Parameter Update를 수행한다는 점에 주의하기 바란다. ( $Q_1, Q_2, …, Q_R$ )

$M$ 평점 행렬의 한 원소를 예측하는 과정은 아래와 같이 Softmax 함수에 의해 Bilinear 연산을 가능한 평점 종류에 대해 수행하고 이에 대한 확률 분포를 생성하는 방식으로 이루어진다.

[p(\hat{M}{ij}) = \frac {e^{u_i^T Q_r v_j}} {\Sigma{s \in R} e^{u_i^T Q_s v_j}}]

여기서 $Q_r$ 은 학습 가능한 Parameter 행렬로, $(E, E)$ 의 Shape을 지녔다. 물론 여기서 $E$ 는 Embedding 차원을 의미한다. 최종적으로 평점 예측은 아래 식으로 계산된다.

[\hat{M}{ij} = g(u_i, v_j) = \mathbf{E}{p(\hat{M}{ij = r}} [r] = \Sigma{r \in R} r * p(\hat{M}_{ij})]

식을 보면 평점의 종류에 따라 확률이 가중 평균됨을 알 수 있다.

2.4. Model Training

논문의 흥미로운 내용만큼이나 학습시키는 것은 상당히 까다롭다. 어떻게 진행되는지 알아보자.

Loss Function은 다음과 같은 Negative Log Likelihood로 설정된다.

[\mathcal{L} = \Sigma_{i, j; \Omega_{i,j} = 1} \Sigma_{r=1}^R I[r=M_{ij}] logp(\hat{M_{ij}} = r)]

여기서 $I$ 함수는 Indicator Function으로 $[]$ 안이 참일 때 1, 그렇지 않을 때 0의 값을 가지게 된다. 이는 일종의 Mask 역할을 수항하게 되는데, 왜냐하면 오직 평점 기록이 존재하는 Link에 대해서만 Loss를 계산한다는 의미가 되기 대문이다.

Node Dropout
관측되지 않은 평점에 대해 모델이 잘 일반화하기 위해서는 또다른 장치가 필요하다. 특정 Node에 대해 $p_{dropout}$ 확률로 밖으로 나가는 모든 Message를 무작위로 drop out하는 방식으로 학습하는 것을 Node Dropout이라고 한다.

Message는 Dropout 단계 이후에 Rescaled된다. Node Dropout을 적용한 결과 임베딩 결과물이 특정 User나 Item에 좀 더 독립적이 된 것을 확인할 수 있었다. 추가적으로 Hidden Layer Unit에 Regular Dropout 역시 적용하였다.

Mini-batching
미니 배치는 User-Item Pair 총합에서 오직 고정된 수의 Contribution 만을 추출하여 학습에 사용한다는 것을 의미한다. 이렇게 함으로써 현재 Batch에서 존재하지 않는, 각 평점 Class의 User/Item 행을 제거할 수 있다.

이러한 과정은 또한 효율적인 정규화의 수단으로 기능하며 모델을 학습시키기 위해 필요한 메모리 역시 경감시키는 효과를 발휘한다.

2.5. Vector Implementation

실제로 코드를 구현하여 모델을 학습할 때, 지금까지 설명한 것처럼 일일히 벡터를 하나씩 구하는 것은 정말 어리석은 행위일 것이다. 간단히 (사실 간단하지 않다) 행렬을 활용하여 수많은 연산을 좀 더 효율적으로 수행해보자.

User Feature와 Item Feature의 수가 $D$ 로 같다고 가정해보자. 이 때 Embedding 행렬은 아래와 같이 구할 수 있다.

[\begin{bmatrix} U \ V \end{bmatrix} = f(X, M_1, …, M_R) = \sigma( \begin{bmatrix} H_u \ H_v \end{bmatrix} W^T )]

[with \begin{bmatrix} H_u \ H_v \end{bmatrix} = \sigma(\Sigma_{r=1}^R D^{-1} \mathcal{M}_r X W_r^T),]

[\mathcal{M}_r = \begin{bmatrix} 0 M_r \ M_r^T 0 \end{bmatrix}]

이 때 $D$ 는 대각행렬이며, 대각원소 $D_{ii} = \vert \mathcal{N}_i \vert$ 을 의미한다.

각 행렬의 크기는 아래와 같다.

행렬 역할 Shape
$\begin{bmatrix} U \ V \ \end{bmatrix}$ Node Embedding Matrix $N+M, E$
$\begin{bmatrix} H_u \ H_v \ \end{bmatrix}$ Hidden Matrix $N+M, E$
$W^T$ Weight Matrix $E, E$
$D^{-1}$ Normalization Matrix $N+M, N+M$
$A$ Graph Adjacency Matrix $N+M, N+M$
$X$ Feature Matrix $N+M, D$
$W_r^T$ Edge-type Specific Weight Matrix $D, E$

위와 같이 Encoder에서 벡터화한 방식을 그대로 Decoder에 적용하면 된다. 그리고 이러한 방식은 오직 관측된 원소를 평가할 때만 필요할 것이다.

2.6. Input Feature Representation and Side Information

컨텐츠 정보와 같이 각 Node에 대한 정보를 담고 있는 Feature는 Feature Matrix $X$ 라는 형태로 Input 레벨에서부터 투입될 수 있다. 그러나 만약 그러한 정보가 다른 User(Item)나 그들의 관심 사항을 제대로 구분할만한 충분한 정보를 갖고 있지 못하다면, 이 정보를 처음부터 Graph Convolutional Layer에 집어 넣으면 심각한 정보 병목현상이 발생할 수도 있다.

이러한 경우에는 Side Information으로 활용하는 방안을 생각해볼 수 있다. Node $i$ 에 대해 User/Item Feature Vector $x_i^f$ 를 만들고, 이를 Dense Hidden Layer에 독립적인 채널을 통해 직접적으로 투입하는 것이다.

[u_i = \sigma(W h_i + W_2^f f_i),]

[f_i = \sigma(W_1^f x_i^f + b)]

이 때 $W_1^f, W_2^f$ 는 학습 가능한 Weight 행렬이며, User Weight Matrix와 Item Weight Matrix는 구분된다. Graph Convolutional Layer를 위한 Node Feature를 담고 있는 Input Feature Matrix $X$ 는 Graph에 있는 모든 Node에 대한 고유한 One-Hot 벡터와 함께 Identity Matrix로 선택된다. 본 논문에서 사용된 데이터셋에 한해서는, User/Item Content 정보는 제한적인 크기를 갖고 있고 따라서 본 논문에서는 이들을 Side Information으로 이용하고자 한다.

Side Information은 꼭 Per-Node Feature 벡터의 형태일 필요는 없다. 사실 그래프 구조여도 되고, NLP 혹은 이미지 데이터일수도 있다. 물론 이 경우 위에서 보았던 식은 미분 가능한 적절한 다른 모듈로 대체되어야 할 것이다. RNN, CNN, GNN 같은 형태로 말이다.

논문에서의 이 부분은 기술적으로 다루기가 좀 어려운 부분이 있을 수는 있지만, 적절히 설계된다면 GCMC의 확장성에 관한 기술로 생각해볼 수 있으며 우리에게 주어진 Task에 유연하게 적용해볼 수도 있을 것이다.

2.7. Weight Sharing

One-Hot 벡터가 Input으로 주어지는 Collaborative Filtering 환경에서, Weight 행렬 $W_r$ 의 열은 특정 평점 값 $r$ 에 대해 독립적인 Node의 잠재 요인으로서의 역할을 갖게 된다. 참고로 $W_r$ 의 Shape은 $(E, D)$ 인데, 논문에서 말한 의 의미를 생각해보면 Weight 행렬을 $W_r^T$ 로 전치하여 $(D, E)$ 의 Shape을 갖고 있다고 생각하고 바라보는 것이 좀 더 편할 것이다.

어쨌든 이 잠재 변수들은 Message Passing이라는 형태를 통해 연결된 User/Item Node로 전달된다. 그러나 모든 User와 Item이 각 평점 레벨에서 갖은 수의 평점을 갖고 있지는 않을 것이다. 이 말은, $W_r$의 특정 열은 다른 열들에 비해 상대적으로 덜 최적화되는 결과를 야기할 수도 있다는 것이다.

따라서 이러한 최적화 문제를 해결하기 위해 다른 평점 class $r$ 에 대해 $W_r$ 에 대한 어떤 형태의 Weight Sharing이 필요하다. 다음과 같은 식을 보자.

[W_r = \Sigma_{s=1}^r T_s]

본 논문에서는 위와 같은 방식의 Weight SharingOrdinal Weight Sharing이라고 명명한다. 왜냐하면 높은 평점 레벨에는 더 많은 Weight 행렬이 들어가기 때문이다.

[W_1 = T_1]

[W_2 = T_1 + T_2]

[W_3 = T_1 + T_2 + T_3]

Pairwise Bilinear Decoder의 효과적인 정규화 수단으로 Basis Weight 행렬 $P_s$ 의 집합의 선형 결합의 형태로 Weight Sharing을 정의할 수 있겠다.

[Q_r = \Sigma_{s=1}^{n_b} a_{rs} P_s]

이 때 $n_b$ 는 기본 Basis Weight 행렬의 개수를 의미한다. $a_{rs}$ 는 학습 가능한 계수로, 각 Decoder Weight 행렬 $Q_r$ 의 선형 결합을 결정한다. 과적합을 피하고 파라미터의 수를 줄이기 위해 $n_b$ 는 평점 Class의 수보다는 작아야 할 것이다.

(중략)


5. Conclusions

Encoder는 Graph Convolutional Layer를 포함하는데, 이 layer는 User-Item 상호작용 Graph에서 오가는 Message 속에서 User/Item Embedding을 구성하게 된다. Bilinear Decoder와 결합하여 새 평점은 labeled edge의 형태로 예측되게 된다.

본 논문에서 제안한 모델은 여러 Benchmark 모델을 능가하는 결과를 보여주었다. 또한 본 논문에서는 확률적 미니배치를 통해 더 큰 데이터셋에서 학습될 수 있다는 것을 보여준다.

미래에 이 모델을 더욱 크고 Multi-modal 형태의 데이터 (Text, Image, Graph-based Information으로 구성된)에도 적용할 수 있기를 바란다. 이러한 세팅에서는 GCMC 모델은 Recurrent 또는 Convolutional Neural Network와 결합하여 사용될 수 있을 것이다.

더욱 확장하기 위해서는 효율적인 근사 방법이 필요한데, 예를 들어 Local Neighborhood를 Sub-sampling하는 방법이 그 예가 될 수 있을 것이다. 이 방법에 대해서는 Inductive Representation Learning on Large Graphs라는 논문을 참고하길 바란다. 이 논문에 대한 리뷰는 곧 블로그에 업데이트될 것이다.

마지막으로 Attention Mechanism은 이러한 종류의 모델의 성능을 더욱 향상시키는 방법이 될 수 있을 것이다.


Reference

1) 논문 원본
2) 리뷰 블로그

Comment  Read more

KnowIT VQA - Answering Knowledge-Based Questions about Videos(KnowIT VQA 논문 설명)

|

이 글에서는 KnowIT VQA: Answering Knowledge-Based Questions about Videos에 대해 알아보고자 한다.

VQA task는 이미지(Visual, 영상으로도 확장 가능)와 그 이미지에 대한 질문(Question)이 주어졌을 때, 해당 질문에 맞는 올바른 답변(Answer)을 만들어내는 task이다.

KnowIT VQA는 VQA 중에서도 Video를 다루는 QA이며, 전통적인 VQA와는 달리 이미지 등 시각자료에서 주어지는 정보뿐만 아니라 외부 지식(상식 베이스, Knowledge Base)이 있어야만 문제를 풀 수 있는 질의들로 이루어진 새로운 task이다.

KnowIT VQA 홈페이지는 https://knowit-vqa.github.io/ 이다.
데이터셋 중 Annotation도 같은 링크에서 다운받을 수 있다.

중요한 부분만 적을 예정이므로 전체가 궁금하면 원 논문을 찾아 읽어보면 된다.


KnowIT VQA: Answering Knowledge-Based Questions about Videos

논문 링크: KnowIT VQA: Answering Knowledge-Based Questions about Videos

초록(Abstract)

지식기반 그리고 Video QA를 결합한 새로운 영상이해(video understanding) task를 제안한다. 먼저, 유명한 시트콤(참고: 빅뱅이론이다)에 대해 24,282개의 사람이 만든 질답 쌍을 포함하는 video dataset인 KnowIT VQA를 소개한다. 데이터셋은 시각적, 텍스트, 시간적 일관성 추론을 지식기반 질문과 결합하여 이는 시리즈를 봄으로써 얻을 수 있는 경험을 필요로 한다. 그리고 시트콤에 대한 세부적인 지식과 함께 시각적, 텍스트 비디오 자료를 모두 사용하는 영상이해 모델을 제안한다. 이 논문의 주된 결과는 1) (외부) 지식의 결합이 Video QA에 대한 성능을 크게 높여주는 것과 2) KnowIT VQA에 대한 성능은 사람의 정확도에 비해 많이 낮다는 것(현 video 모델링의 한계에 대한 연구의 유용성을 내포함)이다.


서론(Introduction)

VQA는 자연어와 이미지 이해를 함께 평가하는 중요한 task로 지난 몇 년간 많은 종류의 VQA가 제안되고 연구되어왔다. 특히 초기 연구와 그 모델들은 주로 이미지의 내용에만 집중하는 형태를 보여 왔다(질문의 예: 안경을 쓴 사람이 몇 명이나 있는가?).

단지 이미지-이미지에 대한 질문을 묻는 것은 한계가 명확했다.

  1. 이미지의 features는 오직 이미지의 정적인 정보만을 잡아낼 뿐 video에 대한 시간적인 일관성이나 연관성은 전혀 고려하지 않았다(예: 그들은 어떻게 대화를 끝내는가?).
  2. 시각 자료(이미지나 영상)는 그 자체로는 외부 지식을 필요로 하는 질문에 대답하는 충분한 정보를 포함하지 않는다.

이러한 한계를 해결하기 위해 단순 이미지와 질문만을 사용하는 Visual QA에서 1) 영상을 사용하는 VideoQA, 2) 외부 지식을 활용하는 KBVQA 등이 등장하였다. 하지만, 여러 종류의 질문을 다루는 일반적인 framework는 여전히 나오지 않았다.

이 논문의 기여하는 바는 여기서부터 출발한다. 영상에 대한 이해와, 외부 지식에 기반한 추론을 모두 활용하는 방법을 제안한다.

  1. 영상을 활용하기 위해 유명 시트콤인 빅뱅이론에다 annotation을 더하여 KnowIT VQA dataset을 만들었다. 질문들은 시트콤에 익숙한 사람만이 대답할 수 있는 수준으로 만들어졌다.
  2. 특정 지식을 continuous representation으로 연결하여 각 질문에 내재된 의도를 추론하는 모듈과 얻어진 지식을 영상 및 텍스트 내용과 결합하여 추론하는 multi-modal 모델을 제안한다.
KnowIT VQA

관련 연구(Related Work)

  • Video Question Answering은 행동인식, 줄거리 이해, 시간적 연관성을 추론하는 등의 시간적 정보를 해석하는 문제들을 다뤄 왔다. 영상의 출처에 따라 시각자료는 자막이나 대본 등 텍스트 자료와 연관되어 해석을 위한 추가 수준의 문맥을 제공한다. 대부분의 연구는 영상이나 텍스트 자체의 정보를 추출할 뿐 두 modality의 결합은 제대로 활용하지 않았다. MovieFIB, TGIF-QA, MarioVQA는 행동인식, Video Context QA는 시간적 일관성을 다룬다.
    • 오직 몇 개의 데이터셋, PororoQA와 TVQA만이 multi-model video representation을 함께 해석하는 benchmark를 제안하였다. 하지만 영상자료를 넘어서는 추가 지식에 대한 고려는 이루어지지 않았다.
  • Knowledge-Based Visual Question Answering: 시각자료와 텍스트만 가지고서는 그 자체에 내재된 정보 외에 추가 지식은 전혀 쓸 수가 없다. 그래서 외부 지식을 포함하는 VQA가 여럿 제안되었다. KBVQA(Knowledge-based VQA)는 외부 지식을 활용하는 대표 VQA 중 하나이다. 이는 지식을 포함하는 데이터셋이지만 초기 단계에 머물러 있다.
    • 그 중 일부 dataset은 질문의 형태가 단순하거나 외부 지식이 정해진 형태로만 제공되었다. KB-VQA는 template에서 만들어진 질문-이미지 쌍을 활용했으며, R-VQA는 각 질문에 대한 relational facts만을 사용했다. FVQA는 entity 식별, OK-VQA는 자유형식의 질문을 사용하였으나 지식에 대한 annotation이 없었다.
    • KnowIT-VQA는 영상을 활용하며, 지식을 특정 데이터에서 직접 추출한 것이 아닌 일반지식을 가져왔기에 이러한 단점들을 해결하였다고 한다.

KnowIT VQA 데이터셋(KnowIT VQA Dataset)

TV Show는 인물, 장면, 줄거리의 일반적인 내용들을 사전에 알 수 있기에 영상이해 task에서 현실 시나리오를 모델링하는 좋은 과제로 여겨진다. 그래서 이 논문에서는 유명 시트콤인 빅뱅이론을 선정하여 KnowIT VQA dataset으로 만들었고, 이는 영상과 show에 대한 지식기반 질답을 포함한다.

Video Collection

영상은 빅뱅이론 TV show에서 가져왔으며, 이는 각 20분 정도의 207개의 episode들로 구성된다. 텍스트 데이터는 DVD에 있는 자막(대본)을 그대로 가져왔다. 각각의 대사는 시간과 화자(speaker)의 순서에 맞게 주석을 달았다. 영상은 scene으로 나누어지며 이는 또 20초 정도의 clip으로 분리되어, 총 12,264개의 clip이 있다.

QA Collection

Amazon Mechanical Turk (AMT)를 사용하였으며 빅뱅이론에 대해 깊은 이해도를 갖는 사람들로 하여금 질답을 생성하도록 했다. 목표는 show에 친숙한 사람들만이 질문에 대답할 수 있도록 하는 질문(그리고 답)을 만드는 것이었다. 각 clip에 대해, 영상과 자막을 각 episode의 대본과 요약과 연결시키도록 했다. 각 clip은 질문, 정답, 3개의 오답과 연관된다.

Knowledge Annotations

여기서 “knowledge”(지식)이란 주어진 영상 clip에 직접 포함되지 않는 정보를 가리킨다. 질답 쌍은 추가 정보로 annotated되어:

  • Knowledge: 짧은 문장으로 표현되는 질문에 대답하기 위해 필요한 정보.
    • 질문: 왜 Leonard는 Penny를 점심에 초대했는가?
    • Knowledge: Penny는 이제 막 이사를 왔다.
    • 정답: 그는 Penny가 빌딩에서 환영받는다고 느끼기를 원했다.
  • Knowledge Type: Knowledge가 특정 episode에서 왔는지, 아니면 show의 많은 부분에서 반복되는지(recurrent)를 말한다. 6.08%의 Knowledge만이 반복되며 나머지 9개의 season에 속하는 Knowledge는 거의 균등하다. 분포와 Knowledge의 예시를 아래 그림에서 볼 수 있다.
KnowIT VQA
  • Question Type: 범용 모델의 개발을 장려하기 위해 test set에서만 제공되며, 4가지 종류로 구분된다:
    • visual-based(22%): video frame 안에서 답을 찾을 수 있다.
    • textual-based(12%): 자막에서 답을 찾을 수 있다.
    • temporal-based(4%): 현재 video clip의 특정 시간에서 답을 예측 가능하다.
    • knowledge-based(62%): clip만으로는 답을 찾을 수 없다(외부 지식이 필요하다).
KnowIT VQA

Data Splits

12,087개의 video clip으로부터 24,282개의 sample을 추출하였으며 train/val/test set으로 구분되었다. 일반적인 QA dataset처럼 정답은 오답보다 살짝 더 길이가 긴 편향이 존재한다.

KnowIT VQA

Dataset Comparison

KnowIT VQA 데이터셋과 다른 데이터셋을 비교한 표를 아래에서 볼 수 있다:

KnowIT VQA
  • QA 생성이 더 까다롭기 때문에 KBVQA의 크기가 작다.
  • KnowIT VQA는 질문의 수가 24k개로 2.4k의 KB-VQA, 5.8k의 FVQA, 14k의 OK-VQA에 비해 훨씬 많다.
  • TVQA와 영상이 일부 겹치지만 KnowIT VQA는 더 많은 clip을 사용하였다.

인간 평가(Human Evaluation)

다음의 목적에 따라 평가를 진행하였다:

  1. video clip이 질문에 답하는 것과 연관이 있는지
  2. 질문이 답변하는데 Knowledge를 실제로 필요로 하는지
  3. Knowledge가 답변하는 데 정말로 도움이 되는지
  4. 모델 비교를 위한 human performance baseline을 설정하기 위해

Evaluation Design

AMT를 사용하였고, worker를 1) 9개의 시즌 전부를 적어도 한 번은 본 masters 그룹과 2) 빅뱅이론을 조금도 본 적 없는 rookies로 구분하였다. 질문에 대한 평가와 knowledge에 대한 평가를 중심으로 진행하였다.


Evaluation on the questions

위의 두 그룹은 각각 Blind(질답만 제공), Subs(질답과 자막 제공), Video(질답, 자막, 영상 clip 제공)으로 구분되었다. worker들은 4지선다형 중 맞는 답과 그 답을 선택한 이유를 6지선다형으로 풀게 하였다.

  • SubsVideo 그룹의 차이는 video의 영향을 보여준다.
  • mastersrookies 그룹의 차이는 knowledge의 중요성을 보여주며 KnowIT VQA는 show를 보지 않았을 때 굉장히 어려운 task임을 보여준다.

Evaluation on the knowledge

모아진 Knowledge의 품질과 질문 간 연관성을 분석하였다. rookies들에게 test set의 질문에 대답하도록 하였다. 각 질문과 선택지에 대해 자막과 video clip이 제공되었다. 답을 한 후에는 연관된 Knowledge를 보여주고 다시 답변하도록 하였다. 결과적으로 Knowledge가 주어지기 전후로 정확도는 0.683에서 0.823으로 증가하였다. 이는 답변을 하는 데 있어 Knowledge의 연관성(그리고 그 중요성)을 보여 준다.

KnowIT VQA

ROCK Model

ROCK (Retrieval Over Collected Knowledge) 모델의 구조는 다음과 같다.

KnowIT VQA
  • Knowledge Base(KB)에 있는 show 정보를 표현하는 언어 instance에 기초한다.
  • 언어와 시공간적 영상 표현을 합하여 질문에 대해 추론하고 답을 예측한다.

Knowledge Base

시청자가 시리즈를 볼 때 정보를 습득하는 것을 모방한다. show에 대해 특정 정보에 접근해야 하기 때문에, Knowledge의 AMT worker 주석에 의존한다.

모아진 Knowledge는 자연어 문장의 형태로 주어진다. ‘Raj가 Penny 집에서 한 것은 무엇인가?’라는 질문에서 주석 Knowledge는 다음과 같다:

Raj는 Missy에게 데이트하자고 요청하길 원했는데, Howard와 Leonard는 이미 그녀에게 물어봤지만 실패했기 때문이지만, (그가 먹었던) 약효가 사라졌고 그는 그럴(요청할) 수 없었다.

Knowledge Graphs와 같은 복잡한 구조에서 어떻게 정보를 가져오는지 불분명하기에, knowledge instance $w$는 자연어 문장으로 표현된다. 거의 중복되는 instance를 제거하였고, $N$은 24,282에서 19,821로 줄어들었다.

Knowledge base $K$는 다음과 같다.

[K = \lbrace w_j \vert j=1, …, N \rbrace]

Knowledge Base Cleaning

거의 중복되는 문장을 제거하기 위해 Knowledge instance 사이의 유사도를 측정하였다. 각 $w_j \in K$에 대해 다음과 같은 입력 문장을 만들었다:

[w_j^{‘} = [\text{CLS}] + w_j + [\text{SEP}]]

[CLS]는 문장의 시작을, [SEP]은 끝을 나타내는 token이다. 이를 60개의 token으로 나눈 뒤 BERT를 통과시켜 고차원의 projection을 얻었다.

[\mathbf{p}j = \text{BERT}{\mathbf{p}}(\tau_j)]

두 문장의 유사도는 cosine 유사도를 사용하였으며 다음과 같이 구해진다.

[\beta_{i, j} = sim(\mathbf{p}_i, \mathbf{p}_j)]

그리고 무향 그래프 $V$를 만들고 유사도 $\beta$가 0.998 초과인 경우에만 edge를 만들었다. 해당 그래프에서 크기 $L$ 이상의 clique를 찾아 임의로 1개만 남기고 나머지는 삭제하였다.

[V = \lbrace w_j \vert j=1, …, N\rbrace]

Knowledge Retrieval Module

전체 과정은 다음과 같다.
질문과 답안 선택지 $q_i, a_i^c, \quad c \in \lbrace 0, 1, 2, 3\rbrace$를 사용하여 Knowledge base $K$에 질의를 한다.
그리고 연관도 점수 $s_{ij}$에 따라 $w_j \in K$의 순위를 매긴다.

먼저 입력이 될 표현 $x_{ij}$를 다음과 같이 문자열들을 이어 붙여 구한다.

[x_{ij} = [\text{CLS}] + q_i + \sum_{k=0}^3 a_i^{\alpha_k} + [\text{SEP}] + w_j + [\text{SEP}]]

이전 연구들은 $a_i^c$의 순서는 별다른 영향이 없다고 하였지만, 불변성을 확보하기 위해 연관도가 높은 순($a_i^0 \rightarrow a_i^3$)으로 정렬하였다.

  • 그리고 입력 표현을 $n$개의 단어로 이루어진 sequence $\textbf{x}_{ij}^{10}$으로 토큰화하고 BERT에 입력으로 준다.
  • 점수를 매기기(scoring) 때문에 $\text{BERT}^{\text{S}}(\textbf{x}_{ij})$로 표기한다.
  • $s_{ij}$를 계산하기 위해 fully connected layer를 사용하고 sigmoid를 붙인다.
  • $\textbf{w}, b$를 각각 FC Layer의 weight와 bias라 할 때

[s_{ij} = \text{sigmoid} (\textbf{w}{\text{S}}^{\top} \cdot \text{BERT}^\text{S}(\textbf{x}{ij}) + b_{\text{S}} )]

$\text{BERT}^{\text{S}}, \textbf{w}, b$는 매칭되거나 되지 않는 QA-knowledge 쌍과 다음의 Loss로 미세조정(fine-tuned)된다:

[\mathcal{L} = -\sum_{i=j} \log(s_{ij}) -\sum_{i\neq j} \log(1 - s_{ij})]

각 $q_i$에 대해 $K$ 안의 모든 $w_j$는 $s_{ij}$에 의해 순위가 매겨진다. 이중 상위 $k$개가 질의로 주어진 질문과 가장 연관 있는 것으로써 이것들이 얻어진다.

Prior Score Computation

모델이 다른 답변 후보에 대해 다른 출력을 내는 것을 막기 위해 답안들을 정렬함으로써 순서에 불변적인 모델을 만들었다. prior score $\xi^c$에 따라

[a^c, \quad c \in \lbrace 0, 1, 2, 3\rbrace]

질문 $q$가 주어지면, $\xi^c$는 정답에 대한 $a^c$의 점수를 예측함으로써 얻어진다. 먼저 입력문장 $e^c$를 문자열을 이어 붙여 얻는다:

[e^c = [\text{CLS}] + q + [\text{SEP}] + a^c + [\text{SEP}]]

그리고 $e^c$를 120개의 토큰 $\mathbf{e}^c$로 토큰화한다. $\text{BERT}_{\text{E}}(\cdot)$를 output이 [CLS]인 BERT 네트워크라 한다면,

[\xi^c = \textbf{w}{\text{E}}^{\top} \text{BERT}{\text{E}}(\mathbf{e}^c) + b_E]

이제 모든 $\xi^c$를 내림차순으로 정렬한 후 이에 맞춰 답변 후보 $\alpha_c$를 재배열한다.

Video Reasoning Module

이 모듈에서는 얻어진 knowledge들이 영상 내용으로부터 얻은 multi-modal 표현과 함께 처리되어 정답을 예측한다. 이 과정은 다음 3가지 과정을 포함한다.

  1. Visual Representation
  2. Language Representation
  3. Answer Prediction

Visual Representation

각 video clip으로부터 $n_f$개의 프레임을 뽑아 영상 내용을 설명하기 위해 아래 4가지의 다른 과정을 거친다:

  1. Image features: 각 frame은 마지막 FC Layer가 없는 Resnet50에 들어가 2048차원의 벡터로 변환된다. 모든 frame에서 나온 벡터를 모아 새로운 FC Layer를 통과시켜 512차원으로 만든다.
  2. Concepts features: 주어진 frame에 대해, bottom-up object detector를 사용하여 object과 특성들의 리스트를 얻는다. 이를 전부 인코딩하여 $C$차원의 bag-of-concept 표현으로 만들고, FC Layer를 통해 512차원으로 변환된다. $C$는 가능한 모든 object와 특성들의 전체 수이다.
  3. Facial features: 주요 인물의 사진 3~18개를 사용하여 최신 얼굴인식 네트워크를 학습시켰다. 각 clip에 대해 $F$차원의 bag-of-faces 표현으로 인코딩하여, FC Layer를 통과시켜 512차원으로 만든다. $F$는 네트워크에서 학습되는 모든 사람의 수이다.
  4. Caption features: 각 frame에 대해 영상 내용을 설명하는 캡션을 Xu et al. 2015으로 만들었다. 각 clip으로부터 얻은 $n_f$개의 캡션은 언어표현 모델의 입력으로 사용된다.

Language Representation

텍스트는 미세조정된 BERT-reasoning을 통과한다. 언어입력은 다음과 같이 구해진다.

[y^c = [\text{CLS}] + caps + subs + q + [\text{SEP}] + a^c + w + [\text{SEP}]]

$caps$는 $n_f$개의 캡션을 시간순으로 이어 붙인 것이고 $subs$는 자막, $w$는 $k$개의 knowledge instance를 합친 것이다.
각 질문 $q$에 대해, 답변 후보 $a^c, \ c = \lbrace 0, 1, 2, 3\rbrace$ 하나당 하나씩 총 4개가 생성된다.

$m$개의 단어로 이루어진 $\mathbf{y}^c$로 토큰화하고 언어표현 $\mathbf{u}^c = \text{BERT}_{\text{R}}(\mathbf{y}^c)$를 얻는다. (R은 reasoning)

Answer Prediction

정답을 예측하기 위해, 시각표현 $\textbf{v}$(images, concepts, facial features)를 언어표현 $\mathbf{u}^c$를 이어 붙인다:

[\textbf{z}^c = [\mathbf{v}, \mathbf{u}^c]]

$ \textbf{z}^c$는 scalar로 사영된다.

[o^c = \textbf{w}_{\text{R}}^{\top}\textbf{z}^c + b_R]

예측된 답안 $\hat{a} = a^{\text{argmax}_c\textbf{o}}$는 $\textbf{o} = (o^0, o^1, o^2, o^3)^\top$ 중 최댓값의 index로 구해진다. $c^*$를 정답이라고 하면 multi-class cross-entropy loss를 써서 미세조정한다:

[\mathcal{L}(\mathbf{o}, c^) = - \log \frac{\exp(o^{c^})}{\Sigma_c \exp{(o^c)}} \qquad \text{for} \ \text{BERT}{\text{R}}, \textbf{w}{\text{R}}, b_{\text{R}}]


실험 결과(Experimental Results)

ROCK 모델을 여러 기준 모델과 비교하여 아래에 정리하였다. SGD를 사용하여 momentum 0.9, learning rate는 0.001을 사용하였으며 BERT는 사전학습된 초기값을 사용한 uncased based 모델을 사용하였다.

KnowIT VQA

Answers

데이터셋에 존재할 수 있는 잠재적 편향을 찾기 위해서 단지 답변 자체만을 고려하여 정답을 예측하는 평가를 진행하였다:

  • Longest / Shortest: 예측 답변이 가장 많거나 적은 단어를 포함하는 답을 선택한다.
  • word2vec / BERT sim: word2vec은 300차원의 사전학습된 벡터를 사용하였다. BERT에서는 3번째~마지막 layer의 출력을 사용하였다. 답변은 word representation의 평균으로 인코딩되었다. 예측은 가장 높은 코사인 유사도를 갖는 것을 선택한다.

전체적으로, baseline은 매우 낮은 성능을 보였으며, Longest만이 찍는 것보다 간신히 나은 성능을 보였다. 정답이 긴 경우가 조금 많은 것을 제외하면 데이터셋에서는 특별한 편향은 발견되지 않았다.

KnowIT VQA

QA

오직 질문과 답변만을 고려하여 여러 baseline에 대해 실험을 진행하였다.

  • word2vec / BERT sim: 위의 Answers와 비슷하게 진행되었으며 질문이 고려 대상에 추가되었다.
  • TF IDF: tf-idf에 의한 단어벡터 가중으로 질문과 답변을 표현한 후 512차원으로 만들었다. 질문과 4개의 답변을 이어 붙여 4-class 분류기에 집어넣었다.
  • LSTM Emb. / BERT: 질문과 답변들의 단어를 사전학습된 BERT와 LSTM에 통과시킨다. LSTM의 마지막 layer는 512차원의 문장표현으로 사앵되었다. 역시 각각을 이어 붙여 4-class 분류기에 넣었다.
  • ROCK_QA: $m = 120$ token을 사용하는 ROCK 모델을 질문과 답변만으로 학습시켰다.

유사도에 기반한 방법을 찍는 것보다 형편없지만, 분류기를 사용한 경우는 훨씬 더 나은 결과를 보이며, 사람보다 더 잘하기도 했다.

KnowIT VQA

Subs, QA

자막, 질문, 답변을 사용한다.

  • LSTM Emb. / BERT: 자막은 LSTM에 의해 인코딩된 후 자막-질문-답변으로 이어 붙여 4-class 분류기에 넣는다.
  • TVQA_SQA: 언어는 LSTM layer에 의해 인코딩되며 다른 시각정보는 쓰지 않았다.
  • ROCK_SQA: $m = 120$ token을 사용하는 ROCK 모델을 자막, 질문, 답변만으로 학습시켰다.

LSTM BERT와 ROCK_SQA는 질문과 답변만을 사용할 때보다 성능이 5.7% 향상되었다. LSTM Emb.는 전혀 향상되지 않았으며 자막의 긴 문장을 인코딩하는 데 한계가 있었기 때문이라 생각된다.

KnowIT VQA

Vis, Sub, QA

이제 언어와 시각 정보 둘 다에 기반한 Video QA 모델이다.

  • TVQA: SOTA VideoQA 방법이다. 언어는 LSTM layer로, 시각 데이터는 visual concepts으로 인코딩된다.
  • ROCK_VSQA: $m = 120$ token과 $n_f=5$ frame을 사용하는 ROCK 모델을 질문과 답변만으로 학습시켰다. 4개의 다른 시각표현이 사용되었다.

ROCK_VSQA는 TVQA를 6.6%만큼 앞질렀다. 그러나, 어떤 visual 모델이든지 ROCK_SQA를 능가하는데 이는 현 영상모델링 기법의 큰 한계를 암시한다.

KnowIT VQA

Knowledge

모델이 이제 Knowledge를 정답을 예측하는 데 사용한다. 전체 버전의 ROCK 모델은 $n=128, k=5$의 지식검색 모듈과 $m=512$의 영상추론 모듈을 사용한다.
non-knowledge 모델과 비교하여, 지식검색 모듈을 포함함으로써 6.5%의 성능 향상이 있으며, 지식기반 접근법의 상당한 잠재력을 보인다(시각표현인 Image, Concepts, Facial과 같이). 그러나, 전문가인 사람과 비교하여, ROCK은 여전히 뒤처지며, 이는 향상시킬 여지가 충분하다는 것을 뜻한다. 지식검색 대신 딱 맞는 지식을 그대로 갖고 오는 모델(ROCK_GT)를 사용하면 정확도는 0.731까지 오르며, 지식검색 모듈도 개선할 여지가 있음을 보여준다.

KnowIT VQA

마지막으로 아래 그림에서 질적 평가 결과를 볼 수 있다.

KnowIT VQA

Knowledge Retrieval Results

지식검색 모듈에 대한 결과로, recall at K와 median rank(MR)에 대한 결과를 아래 표에서 볼 수 있다.

  • 질문만 있는 경우
  • QA parameter sharing: 같은 parameter가 4개의 후보 답변에 사용됨
  • QA prior score: prior score에 따라 순서를 배열하는 방법
KnowIT VQA

질문만 사용하는 경우와 다른 두 경우에 큰 차이가 있는데 이는 후보 답변에 올바른 지식을 가져오는 데 필요한 정보가 포함되어 있음을 나타낸다. 가장 좋은 결과는 prior score에 따라 순서를 정한 것인데, 이는 모든 후보 답변을 전부 사용하는 것이 더 정확한 정보를 얻는 데 도움이 된다는 뜻이다.


결론(Conclusion)

새로운 지식 필요 영상 VQA를 제시하였고 multi-modal 영상정보와 지식을 결합하여 사용하는 영상추론 모델을 제시하였다. 진행된 실험은 영상이해 문제에서 지식기반 접근법의 상당한 잠재력을 보였다. 그러나, 사람의 능력에 비하면 크게 뒤처지며, 이 데이터셋을 통해 더 강력한 모델의 개발을 장려하며 이를 바라는 바이다.

Acknowledgements

New Energy and Industrial Technology Development Organization


참고문헌(References)

논문 참조!


Comment  Read more

KVQA - Knowledge-Aware Visual Question Answering(KVQA 논문 설명)

|

이 글에서는 KVQA: Knowledge-Aware Visual Question Answering에 대해 알아보고자 한다.

VQA task는 이미지(Visual, 영상으로도 확장 가능)와 그 이미지에 대한 질문(Question)이 주어졌을 때, 해당 질문에 맞는 올바른 답변(Answer)을 만들어내는 task이다.

KVQA는 VQA의 일종이지만, 전통적인 VQA와는 달리 이미지 등 시각자료에서 주어지는 정보뿐만 아니라 외부 지식(상식 베이스, Knowledge Base)이 있어야만 문제를 풀 수 있는 질의들로 이루어진 새로운 task이다.

KVQA 홈페이지는 http://malllabiisc.github.io/resources/kvqa/ 이다.
데이터셋도 같은 링크에서 다운받을 수 있다(총 90G 상당).

중요한 부분만 적을 예정이므로 전체가 궁금하면 원 논문을 찾아 읽어보면 된다.


KVQA: Knowledge-Aware Visual Question Answering

논문 링크: KVQA: Knowledge-Aware Visual Question Answering

초록(Abstract)

Visual Question Answering(VQA)는 CV, NLP, AI에서 중요한 문제로 떠오르고 있다. 전통적인 VQA에서는, 이미지에 대한 질문이 주어지는데 이는 이미지에 있는 정보만으로도 답변할 수 있다: 예를 들어, 사람들이 있는 이미지가 주어지면, 이미지 안에 사람이 몇 명이나 있는지를 묻는 것과 같은 식이다.
좀 더 최근에는 고양이/개 등 일반명사를 포함하는 일반상식(commonsense knowledge)을 요구하는 질문에 답변하는 것이 주목받고 있다. 이러한 흐름에도 버락 오바마 등 고유명사에 대한 세계 지식(world knowledge)를 요하는 질문에 답변하는 것은 다뤄진 적이 없었다. 그래서 이러한 부분을 이 논문에서 다루며, (세계) 지식을 알아햐 하는 VQA인 KVQA를 제안한다.
이 데이터셋은 18K개의 고유명사와 24K개의 이미지를 포함하는 183K개의 질답 쌍으로 이루어져 있다. 데이터셋의 질문들은 여러 객체와 다중 관계, 큰 Knowledge Graphs(KG) 상에서 다중도약 추론을 요구한다. 이러한 점에서 KVQA는 KG를 갖는 VQA에서 가장 큰 데이터셋이다. 또한, KVQA에 SOTA 방법을 사용한 결과도 보인다.


서론(Introduction)

ovieQA Dataset

VQA는 AI와 소통하는 데 있어 아주 훌륭한 도구로 자리잡았다. 지난 몇 년간 많은 발전이 있었는데, 우선은 VQA의 시초가 되는 VQA 논문가 있다. 전통적인 VQA는 이미지 등의 시각자료가 주어지면, 이미지에 관련한 질문을 묻고, 이미지에서 얻은 정보를 바탕으로 답변을 하는 방식이다.

위 그림이 주어졌을 때, 전통적인 VQA 질문의 예시는 다음과 같다.

  • Q: 이미지에 몇 명의 사람이 있는가?
  • A: 3

최근에는 Commonsense Knowledge를 사용해야만 문제를 풀 수 있는 VQA가 더 관심을 받고 있다. 이러한 일반상식의 예시는 다음과 같다.

  • Microphone은 소리를 증폭시키는 데 쓴다.
    • Microphone은 일반명사이다.

일반상식을 필요로 하는 질문은 다음과 같다.

  • Q: 이미지에 있는 것 중 무엇이 소리를 증폭시키는 데 쓰이는가?
  • A: Microphone

그러나 실생활에서 문제는 이렇게 간단하지 않고 이미지에 존재하는 고유명사(named entities)에 대한 정보를 필요로 하는 경우가 많다. 예를 들면,

  • Q: 버락 오바마의 왼쪽에 있는 사람은 누구인가?
  • A: Richard Cordray

  • Q: 이미지에 있는 사람들은 공통 직업을 가지는가?
  • A: Yes

그래서 이러한 경우를 다루기 위해 논문에서 KVQA(Knowledge-aware VQA)를 제안한다. 이러한 방향의 연구는 별로 다뤄지지 않았고 또한 필요할 것이라 생각된다.

Wikidata(Vrandecic and Kr¨otzsch 2014)는 대규모 KG로서 사람들, 생물 분류, 행정상 영토, 건축구조, 화합물, 영화 등 5천만 개의 객체를 포함하는 KG이다. 여기서 필요한 것을 추출하는 것은 어렵기 때문에, 논문에선 생략되었다. 대신 이에 대한 배경지식과 관련한 사람들과 수동으로 검증된 질답 쌍을 포함하는 KVQA 데이터셋을 제안한다.

KVQA 데이터셋에서는 visual 고유명사와 Wikidata의 객체를 연결하기 위해 Wikidata에서 69K 명의 사람들 이미지를 포함하도록 했다.

이 논문이 기여한 바는:

  1. 이미지의 고유명사를 다로는 VQA를 처음으로 다룬다.
  2. Knowledge-aware VQA인 KVQA 데이터셋을 제안하며 이는 일반상식을 요구하는 기존 데이터셋보다 12배 크며 고유명사를 다룬 것으로는 유일하다.
  3. KVQA에 SOTA 방법을 적용하여 그 성능을 제시하였다.

관련 연구(Related Works)

  • VQA는 2015년 제시된 이후 계속해서 발전하여 2017년 v2.0 데이터셋 발표, (2020년까지) 챌린지를 매년 열고 있다. 비슷한 연구가 많이 발표되었지만 문제가 단순하다는 점에서 한계점이 명확하다.
  • 이후에는 일반상식을 필요로 하는 VQA가 많이 연구되어 왔다.
  • Computer Vision and Knowledge Graph: 컴퓨터비전과 KG를 연결하려는 데 관심이 늘고 있다. 이는 단지 VQA의 활용에만 그치는 것이 아니라 이미지 분류 등의 전통적인 CV 문제에서도 사용된다. 하지만, 대부분은 이미지와 일반상식 그래프를 연결짓는 데에 치중하고 있다.
  • Other Datasets: CV에서 사람을 인식하고 판별하는 것은 주류 연구 분유 중 하나이다. 유명인사나 사람의 자세 추정, 장소 추정 등이 있다.
  • Face identification and context: 이미지에 나타나는 고유명사와 KG를 연결하는 것은 web scale에서 얼굴식별의 필요로 이어진다. 얼굴식별은 연구가 많이 이루어졌지만 대부분 작은 규모에서 이루어지고 있다. KVQA이 더 규모가 크기 때문에 좋다는 뜻이다.

KVQA 데이터셋과 다른 데이터셋을 비교한 표를 아래에서 볼 수 있다:

ovieQA Dataset

KVQA 데이터셋(KVQA)

간략한 통계는 아래 표와 같다. 이미지와 질문의 수 등을 볼 수 있고, train/val/test set이 구분되어 있다.

ovieQA Dataset

데이터는 다음 과정을 통해 모았다:

  1. Image Collection: Wikidata로부터 운동선수, 정치인, 배우 등의 사람들의 리스트를 가져와 Wikipedia에서 사람(30K)의 이미지(70K)와 설명을 가져왔다.
  2. Counting, identifying and ordering persons in image: 이미지의 사람 수를 세고, 사람 수에 따라 human annotator를 부여하였다. 사람이 없거나 너무 많은 경우 등은 제외하고 중복 제거 등을 수행하였다. 그리고 왼쪽부터 오른쪽으로 맞는 human annotator를 부여하였다.
  3. Obtaining ground-truth answers: 이제 고유명사(사람)와 이미지 안의 관계(왼쪽/오른쪽 등)를 파악하였으니 이미지에 있는 사람에 어떤 질문을 할 수 있는지를 정하여 질문 템플릿을 정하고 SPARQL는 오직 ground truth를 얻기 위해 사용되었다.
  4. Training, Validation, and testing: train/val/test set을 70/20/10%의 비율로 다른 VQA와 동일하게 구분하였다.
  5. Paraphrasing questions: task의 복잡도를 늘리고 실세계와 유사하게 만들기 위해 test set의 질문을 다른 표현으로 바꿔서(https://paraphrasing-tool.com/) 이를 수동으로 검증하여 일부를 사용하였다. 예시는:
  • 원래 질문: 이미지에 있는 사람들 중 Paula Ben-Gurion와 결혼했던 사람은 누구인가?
  • 바뀐 질문: Paula Ben-Gurion과 어떤 시점에선 결혼한 적 있는 사람은 누구인가?
ovieQA Dataset

KVQA 데이터셋 분석(Analysis of KVQA)

KVQA는 자세나 인종 등 광범위한 사람들을 다루거나 KG에서 다중도약 추론을 해야 하는 challenge를 포함한다. 질문은 총 10가지 분류로 나뉜다:

spatial, 1-hope, multi-hop, Boolean, intersection, subtraction, comparison, counting, multi-entity, multi-relation

위 분류는 상호 배제적인 것은 아니다. 위 그림의 (c)에서, 추론은 다음과 같이 여러 단계를 거쳐야 한다:

  • 왼쪽부터 2번째 사람을 찾고
  • Narendra Modi는 BJP의 일원이며
  • BJP는 Syama Prasad Mookerjee에 의해 설립되었다.

질문의 종류와 답변의 간략한 분포는 아래와 같이 확인할 수 있다.

ovieQA Dataset

일반적인 VQA에서는 ‘어떤 스포츠인가’라는 질문에는 높은 확률로 ‘테니스’가 정답이고, Yes/no 질문에서는 ‘Yes’가 87%으로 꽤 편향된 것을 볼 수 있다.
단 KVQA는 꽤 균등한 분포를 보이는데, 이는 질문을 다양하게 바꿈으로써 해결한 것이라 한다.

Knowledge Graph(KG)

논문 발표 시점 최신인 2018-05-05 버전의 Wikidata를 KG로 사용하였다. 이는 ‘주어-관계-목적어’의 triplet 형태를 가지고 각 객체와 관계는 고유한 Qid와 Pid로 표현된다(예. Barack Obama는 Q76, has-nickname은 P1449). 이 KG는 5200개의 관계, 1280만개의 객체와 5230만 개의 지식을 포함한다. 이럴 114명K의 사람에 대한 것을 고려하여 Wikidata에서 사람들의 이미지를 가져왔다. 단 데이터가 불완전하여 69K명의 것만 가져왔다. 이 이미지는 visual entity를 연결하는 데 사용된다.

Baseline을 평가하는 두 세팅은 다음과 같다:

  1. Closed-world setting: 18K의 객체와 3단계 추론을 사용한다. 사실(Facts)은 18종류의 관계만을 포함한다(직업, 시민권 국적, 출생지 등).
  2. Open-world setting: 훨씬 open된 3단계 추론 실험적 세팅이다. 69K의 객체와 상위 200개의 관계를 포함한다.

접근법(Approach)

Visual Entity Linking

Visual entity linking은 visual entity를 KG에 연결하는 것인데, KVQA에서 visual entity는 사람이다. 그래서 visual entity linking은 안면 식별이 되는데, 사람의 수가 매우 많으므로 그 규모가 매우 크다.

Face identification at scale

Face Localization은 KVQA에서 안면 식별의 선구자격 역할을 한다. 그래서 두 가지 방법(Zhang et al. 2016; Hu and Ramanan 2017)을 사용해보고 더 좋은 방법(Zhang)을 써서 face localization을 수행한다. 이후 얼굴 식별(face identificatino)을 수행하는데, Baseline으로 Facenet을 선정하여 사용하였다.

그래서 참고 이미지의 face representation을 얻고 1-최근접 이웃을 18K/69K명의 고유명사 이미지에 대해 찾았다. 결과는 아래에서 볼 수 있다.

ovieQA Dataset

VQA over KG

일단 Visual Entity를 KG에 열결하면, VQA 문제는 KG로부터 (질문과) 관련 있는 fact를 찾아 추론한 뒤 답변하는 것을 학습하는 것과 같아진다. 이 논문에서는 visual entity linking과 QA를 두 개의 분리된 모듈로 다룬다(end-to-end를 쓰지 않음).

KVQA의 baseline으로 memNet(memory network, Weston at al., 2014)을 썼는데 이 모델은 외부 지식으로부터 학습하는 일반적인 구조를 제공한다(memNet은 상식 요구 VQA에서 SOTA 성능을 보임). 이 논문에서 사용한 모델의 구조는 다음과 같다:

ovieQA Dataset

1. Entity Linking

이미지, Wikipedia 캡션(선택적 요소), 질문이 주어지면 이미지와 질문에 있는 entity(visual entities: 사람)를 찾는 것이다. Wikidata에서 가져온 참고 이미지를 활용하며, 텍스트(캡션과 질문)에 있는 entity를 찾기 위해 Dexter 라고 하는 오픈소스 entity recognizer를 사용한다. Visual entity linking과 Text entity linking은 위 그림에서 보듯이 따로 이루어진다.

이 부분에서 entity를 모두 찾고 또한 추가적으로 이미지 상의 entity들의 위치(상대적 위치나 얼굴의 좌표 등)를 얻는다.

2. Fetching facts from KG

이제 entity와 연관 있는 정보를 KG에서 찾는다. 여기서는 3단계(3-hop)만 거치도록 제한하였다. 이러한 knowledge fact들을 공간적 fact(ex. Barack Obama(의 얼굴의 중심)는 (x1, y1) 좌표에 있다)와 함께 보강한다.

그림에서 Facts + Face coornidates라 표시된 부분이다.

3. Memory and question representation

각 knowledge와 공간적 fact는 연관된 memory embedding $m_i$를 얻기 위해 BLSTM에 입력으로 주어진다. 질문 $Q$에 대한 embedding ($q$) 또한 비슷하게 얻어진다.

그리고 $q$와 $m_{ij}$ 사이의 매치되는 정도를 구하기 위해 내적과 softmax를 거친다:

[p_{ij} = \text{softmax}(q^Tm_{ij})]

여기서 $p_{ij}$는 knowledge fact들과 $Q$ 사이의 soft attention과 같은 역할을 한다. 이를 얻으면 모든 fact에 대한 출력 representation을 선형결합하여 출력 representation을 구한다:

[O = \sum_j p_{ij}o_{ij}]

$o_{ij}$는 fact $j$에 대한 representation이다.

4. Question answering module

출력 representation $O$와 $q$의 합은 MLP $f_\theta$에 입력으로 들어간다($\theta$는 학습가능한 parameter). 그리고 정답 $\hat{a}$를 구하기 위해 softmax를 적용한다:

[\hat{a} = \text{softmax}(f_\theta(O+q))]

학습하는 동안, memory/question representation과 QA 모듈을 함께 학습한다. 손실함수는 cross-entropy loss를 사용하였으며 SGD로 최소화한다.

다중도약(multi-hop) facts 탐색을 효율적으로 하기 위해 memory layer를 쌓고 질문 representation을 다음과 같이 구한다:

[q_{k+1} = O_{k+1} + q_k]

첫 번째 레이어의 질문 representation은 BLSTM으로부터 구해진다. 최상층 레이어(layer K)에서 질문에 대한 답은 다음과 같이 구해진다.

[\hat{a} = \text{softmax}(f_{\theta}(O_K+q_{K-1}))]

이 논문에서는 3-hop을 사용하므로 $K=3$이다.

Memory Network의 대안은 knowledge facts를 표현하기 위해 BLSTMs를 사용하는 것이다. 이는 baseline의 하나로 사용되었다.

KVQA의 양적평가(quantitative results)는 아래 표의 왼쪽 부분과 같다.

ovieQA Dataset

Closed/Open World 각각에 대해 평가하였으며, Wikipedia Caption을 사용했으면 +wikiCap, 아니면 -wikiCap으로 표시되어 있다. 질문을 paraphrase했으면 PRP, 아니면 ORG(original)이다.
모든 평가에서는 고정된 크기의 사전을 사용하였으며 질문에서 각 token, Wikipedia caption, visual entity들은 1-hot 벡터로 표현하였다.

결과를 보면,

  • BLSTMs는 fact의 수가 증가할수록 비효율적이었으며 memNet이 이를 압도한다.
    • visual entity linking은 많은 수의 다른 요인에 의해 open world에서 실수가 많았으며
    • 수많은 fact에서 질문과 관련된 fact를 찾는 것이 어려워지기 때문이다.
  • Ablation study에서(위 표에서 오른쪽 부분)는
    • KG에서 논리적 추론만에 의한 부분을 연구하기 위한 세팅을 oracle setting이라 한다.
    • 이 oracle setting은 각 사람과 이미지 내에서 사람의 순서는 알려져 있다고 가정한다.
    • memNet은 공간적, 다중도약, 다중관계, subtraction 등에서 부적합했지만 1-hop, 이지선다 및 교차질문에서는 괜찮은 성능을 보였다.
    • 이것은 질문의 종류에 따라 어떤 가이드가 필요하다는 것을 뜻할 수 있다. 이는 추후 연구로 남겨둔다.

논의 및 요약(Discussion and Summary)

얼굴 식별과 VQA에서의 진전에도 불구하고 Knowledge-aware VQA에서 더 많은 연구가 필요함을 보였다. 기존의 Facenet이나 memory network는 수많은 distractor가 존재하거나 규모가 커진 경우에는 제대로 성능을 내지 못하였다.

이 논문에서는 Knowledge-aware VQA인 KVQA를 제안하였고 평가방법과 baseline을 제시하였다. KVQA의 현재 버전은 KG의 중요 entity인 사람에만 국한되어 있다. 하지만 Wikidata와 같은 KG는 기념물이나 사건 등 여러 흥미로운 entity에 대한 정보도 갖고 있기 때문에 추후 확장할 수 있다. 이 분야에 많은 연구가 이루어지길 희망한다.

Acknowledgements

MHRD와 인도 정부, Intel이 지원하였다고 한다..


참고문헌(References)

논문 참조!


Comment  Read more