[Paper Review] Dense Passage Retrieval for Open-Domain Question Answering

Dense Passage Retrieval for Open-Domain Question Answering

arxiv pdf link for DPR

0. Abstract 🎬

Open-domain question answering 은 답변에 효과적인 passage를 retrieval 하는 방식에 의존한다. 이 방식은 지금까지 TF-IDF, BM25와 같은 sparse vector space를 생성하는 방법에 기인해 왔다. 본 논문에서는 이 retrieval을 위한 vector representation이 적은 수의 question & passage를 사용한 dual-encoder framework를 이용하여, dense representation으로도 사실상 가능하다는 것을 보인다.

광범위한 open-domain QA dataset을 이용하여 평가했을 때, 본 논문의 dense retriever은 상위 20개의 retrieval 정확도에서 기존의 Lucene-BM25 시스템 절대적으로 9% ~ 19% 능가했다. 또한, 이는 open-domain QA 에서 새로운 SOTA를 달성했다.

1. Introduction ☕️

QA (Open-domain Question Answering) 은 거대한 문서의 집합을 사용하여 factoid question에 답변하는 task이다. 이전의 QA system은 다소 복잡하고, 다양한 요소로 이루어져 있었다. 하지만 Comprehension model의 발달로 인해, 매우 간단한 two-stage framework로 나누어졌다.

1. context retriever이 먼저 답변을 위한 passage들의 작은 집합을 선택한다.

2. 그리고 reader이 retrieved 된 context들을 분석하여 올바른 정답을 도출한다.

물론 QA task를 machine reading만의 task로 바라보는 관점 또한 충분히 고려할 만 하지만, huge performance degradation의 사례가 존재하기에, retrieval에 대한 향상이 필요하다고 여겨진다.

QA에서 retrieval은 주로 TF-IDF 이나 BM25로 구현되어 왔는데, 이는 keyword 를 중점으로 sparse vector로 표현하는 방법이였다. 반대로, dense vector을 latent semantic encoding 을 활용하여 앞선 sparse vector과는 상보적인 관계에 있다.

예를 들어 아래와 같은 예시를 살펴보자.

Q : Who is the bad guy in lord of the rings?

Useful context : Sala Baker is best known for portraying the villain Sauron in the Lord of the Rings trilogy.

Term-based system은 villain 과 bad guy에 대한 semantic similarity를 가지고 있지 않기 떄문에, 해당 context를 retrieval 하기 어렵지만, dense retrieval system은 이 두 단어를 연결지어 해당 context를 reteival 할 가능성이 높다.

더 나아가서 Dense encoding 은 learable 하기 때문에, 특정 task에 대해 specific 하게 학습하여 유연성 또한 가지고 있다. 이런 과정은 MIPS (maximum inner product search) Algorithm을 통해서 계산된다.

그러나, 일반적으로 좋은 dense vector representation을 학습하는 것은 큰 수의 question & context pair 이 필요하다고 여겨져 왔다. Dense retrieval 방법은 TF-IDF/BM25와 같은 고전 방식을 능가하지 못했었지만, ICT (inverse cloze task) training을 이용한 모델인 ORQA가 처음으로 이 방식을 능가하게 되었다.

여기서 ICT (inverse cloze task) 란, context 내에서 특정 sentence를 추출하여, 해당 sentence 가 어느 context에 속하는지를 학습하는 것이다.

하지만, 앞선 ORQA의 성능에도 불구하고, multiple domain 상에서의 SOTA를 달성하기에는 2가지 부분에서 문제점이 있었다.

1. ICT는 computationally intensive 하고, 단순히 sentence를 matching 시키는 것이 Question anwsering에 효과적이라는 것이 명확하지 않다.
2. context encoder은 question-answer 쌍을 이용해 fine-tuned 되지 않았기 때문에, 해당 encoder을 통한 representation이 최적의 값이 아닐 수 있다.

본 논문에서는, 추가적인 pre-training 없이 question-answer 의 쌍들(Not so much)만 이용하여 더 나은 dense embedding model 을 만드는 것을 목표로 한다. Pretrained BERT model과 dual-encoder을 활용하여, 상대적으로 적은 수의 question-passage(answer) 쌍을 이용하도록 할 것이다.

이 과정에서, 유사한 question-passage 들의 내적을 최대화하는 방향으로 최적화를 진행할 것이며, batch 내의 모든 question, passage 쌍을 비교할 것이다. 본 논문의 DPR method은 BM25 방식을 큰 차이로 능가하며, 단순히 representation이 아닌 end-to-end QA 정확도 또한 ORQA에 비해 큰 차이를 냈다.

본 논문은 이러한 방식으로 간단하게 question-answer 의 쌍들을 학습하는 것만으로도, BM25의 성능을 능가한다. 또한, 이는 추가적인 pre-train을 요구하지 않는다. 또한 Open-domain 에서 retrieval의 성능이 높을수록, end-to-end 의 QA 성능 또한 높아진다.

2. Background 🧐

open-domain 의 주요 task는 다음과 같은 factoid question이 주어졌을 때, 다양한 주제의 topic 에 대한 corpus를 참조하여 정답을 찾아내는 것이다.

Q : Who first voiced Meg on Family Guy?
Q: Where was the 8th Dalai Lama born?

더 구체적으로는, QA 를 extractive 한 question 에 한정짓는다. 다시 말해 question에 대한 정답은 항상 corpus set의 document 에 하나 이상 존재한다고 가정한다.

하지만 이런 메커니즘의 경우, open-domain question의 특성상 매우 많은 document가 존재해야 하며, corpus의 크기는 millions of document 에서 billion까지 매우 큰 수량을 가진다다.

따라서 이를 위한 efficient retriever component, 즉 정확한 정답을 찾아내기 전에 query와 유사한 집합 (전체 corpus의 부분집합)을 구할 수 있는 방법이 필요하다. Retriever $R$ 을 $R : (q, \mathcal{C}) \rightarrow \mathcal{C}_{\mathcal{F}}$ , $\mathcal{C}$를 corpus, $q$ 를 question 이라고 했을 때, retriever은 $\mathcal{C}_{\mathcal{F}} \in \mathcal{C},\;\; |\mathcal{C}_{\mathcal{F}}| = k \ll |\mathcal{C}|$ 한 corpus $\mathcal{C}$의 subset인 $\mathcal{C}_{\mathcal{F}}$를 구해내어야 한다.

3. Dense Passage Retriever (DPR) 🥽

이 논문에서는 open-domain QA task에서 retrieval component 를 향상시키는 데에 중점을 둔다. $M$ 개의 text passage 가 주어졌을 때, DPR 의 목표는 이 모든 passage를 모두 low-dimensional로 변환시켜 top-k relevant passage 를 실시간으로 효과적으로 retrieval 할 수 있도록 하는 것이다. (당연하게도 $M$은 매우 큰 집합으로, 본 논문에서는 21 million 정도이다.)

3.1 Overview

본 논문의 DPR은 text passage를 $d$-dimensional real-valued vector로 encoding 하는 dense encoder $E_p()$ 를 사용한다. run-time 때는, 이와 다른 encoder인 $E_Q()$ 가 사용되는데, 이는 input question 을 $d$-dimensional vector로 변환하여, 이 벡터들간의 계산을 통해 top-k relevant passage 를 retrieval 하게 된다. 이 relevantness 계산은 다음과 같은 dot product로 계산된다.

\[sim(q, p) = E_Q(q) \cdot E_P(p)\]

물론 Cross Attention 과 같이 두 context 간의 유사도를 더욱 정확하게 측정할 수 있는 방식 또한 존재하지만, 매우 큰 수량의 passage 들을 계산하기 위해서는 decomposable 한 방식이 더욱 효율적이다. 대부분의 decomposable 한 similarity function 은 Euclidean distance (L2) 이며, cosine similarity 또한 unit vector 들에 대한 유사도를 계산하기 용이하지만, 본 논문에서는 L2 와 cosine similarity를 이어주며, 더욱 간단한 dot product 를 사용한다.

Encoders

question 과 passage 를 encoding 하는 방식에는 neural network 도 있지만, 본 논문에서는 2개의 독립적인 BERT 를 사용해 [CLS] 토큰을 representation으로 사용할 것이다.

Inference

Inference 시간에는, passage encoder $E_P$를 모든 passage 에 대해서 적용하며, FAISS를 이용하여 indexing 한다. FAISS는 open-source library로, dense vector들에 대한 효율적인 clustering을 통해서 매우 많은 수의 vector들을 다룰 수 있다. Question $p$가 주어지면, $v_q = E_Q(q)$를 통해 top-$k$ passage들을 찾는다.

이 과정에서 HNSW 라는 ANN 방식을 사용하는데, 다음 링크에 상세하게 설명되어 있다.

3.2 Training

Encoder들을 학습시켜 dot-product similarity를 활용해 retrieval을 효과적으로 만드는 것은 metric learning problem이다. 이 목적은 곧 relevant question-passage 쌍에 대한 distance를 최소화하는 것에 있다.

question $q$ 에 대해서 학습을 진행할 때, $p_i^+$를 positive passage (relevant passage for $q$)라고 했을 때, training data $\mathcal{D}$ 는 다음과 같이 정의할 수 있다.

\[\mathcal{D} = \{\left\langle q_i, p_i^+, p_{i,1}^-, \cdots, p_{i, n}^- \right\rangle\}_{i=1}^m\]

$\mathcal{D}$는 n개의 instance를 가지며, 1쌍의 올바른 question-answer 과 question 에 관계없는 negative passage 를 m 개 가지고 있다. 우리는 이 data에 대한 loss function을 positive passage에 대한 negative log likelihood를 이용하여 다음과 같이 정의할 수 있다.

\[L(q_i, p_i^+, p_{i,1}^-, \cdots, p_{i, n}^-) = -log\frac{e^{sim(q_i, p_i^+)}}{e^{sim(q_i, p_i^+)} + \sum_{j=1}^{n}{e^{sim(q_i, p_{i,j}^-)}}}\]

Positive and negative passages

이 학습을 위해서는, question-passage의 적절한 쌍을 찾기에는 명확하지만, negative passage들을 찾기 위해서는 매우 큰 풀에서 sampling 되어야 한다. 예를 들어, positive passage는 QA dataset내에 context가 존재하거나 answer를 searching 해서 찾을 수 있다. 그리고 다른 모든 passage, 즉 relevant 하지 않은 passage는 negative passage 이다. 실제로도 어떠한 방식으로 negative passage를 구하느냐는 주로 중요하게 여겨지지 않지만, 때로는 높은 성능의 encoder을 구현하는 데에 주요한 역할을 한다.

따라서 본 논문에서는 negative passage를 구하는 방식을 3가지 종류로 나누었다.

1. Random passage : corpus 내부에 있는 랜덤한 passage
2. BM25 : BM25를 통해 계산되어 answer이 포함되어 있지는 않지만, question 의 토큰을 가장 많이 포함된 passage
3. Gold : training set 내부의 다른 question에 대해서 positive passage로 판별된 passage

이러한 방법들에 대해서는 Section 5.2 에서 다룰 것이며, 가장 높은 성능을 보였던 방법은 gold passage들을 같은 크기의 mini-batch에 대해서 사용하는 것에 1개의 BM25 기반 negative passage을 더하는 것이다. 더 나아가서, gold 기반의 negative passage를 재사용하는 것은 computational 적인 관점에서 효율성을 보인다.

In-batch negatives

하나의 mini-batch에 $B$개의 question이 존재한다고 하자. 그리고 respectively 하게 relevant 한 passage와 쌍을 이루고 있다. 이 questions 들과 passages 들을 vector로 나타낸 것을 행렬화한 것을 각각 $Q$, $P$ 라고 하면 (각각의 크기는 $(B\times d)$가 된다.), $S=QP^T$ 는 곧 각 question과 passage 간의 독립적인 similarity를 나타내게 된다.

이렇게 $S$를 구하면, $(q_i, p_j)$ 에서 $i=j$인 경우에만 positive passage가 되고, 나머지의 경우에는 gold 기반의 negative passage가 되어 B-1개의 negative passage를 구할 수 있다. 또한 이 방식은 computational efficency를 보장하게 된다.

4. Experimental Setup 🔬

4.1 Wikipedia Data Pre-processing

따로 추가적인 설명이 불필요하여 원문 그대로 가져왔다.

Following (Lee et al., 2019), we use the English Wikipedia dump from Dec. 20, 2018 as the source documents for answering questions. We first apply the pre-processing code released in DrQA (Chen et al., 2017) to extract the clean, text-portion of articles from the Wikipedia dump. This step removes semi-structured data, such as tables, infoboxes, lists, as well as the disambiguation pages. We then split each article into multiple, disjoint text blocks of 100 words as passages, serving as our basic retrieval units, following (Wang et al., 2019), which results in 21,015,324 passages in the end.5 Each passage is also prepended with the title of the Wikipedia article where the passage is from, along with an [SEP] token.

4.1 Question Answering Datasets

이 논문에서는 5가지 QA dataset을 이용하여 학습을 진행했다. 그 목록은 다음과 같다.

1. Natural Questions (NQ) : end-to-end QA의 목적에 맞게 design 되었으며, real Google search quesries 과 Wikipedia의 answer을 기반으로 작성되었다.
2. TriviaQA : Web 상에 존재하는 trivia questions를 이용하여 만들어졌다.
3. WebQuestions (WQ) : Google Suggest API를 이용하여 answer들은 Freebase 내부에 있도록 하는 dataset
4. CuratedTREC (TREC) : TREC QA track과 여러 Web soruce를 기반으로 하는 open-domain QA dataset
5. SQuAD v1.1 : Reading comprehension을 통해 얻은 유명한 dataset

4.2 Selection of positive passages

TREC, WebQuestions, 그리고 TriviaQA는 적은 수의 question-answer 쌍이 주어졌기 때문에, BM25를 이용하여 가장 answer 이 있을 확률이 높은 context를 찾는다. 만약 상위 100개의 passage들 모두 정답을 포함하고 있지 않다면, 해당 question은 무시될 것이다.

SQuAD와 Natural Questions들에 대해서는, 기존의 passage가 나뉘어져 있고, candidate passage 와 pool 내부가 서로 다르게 processing 되었기 때문에, 각 gold passage를 그에 상응하는 passage와 교체시킨다. 만약 이 작업에 실패한다면, 그 질문을 삭제한다.

5. Experiments: Passage Retrieval 🧪

이 섹션에서는, retrieval performance 를 다룬다. 기존의 retrieval method에 대해서 어떤 효과를 가지는지에 대해서 살펴본다.

본 논문의 main experiement에서 사용된 DPR 모델은 batch size가 128이며, BM25 기준의 negative passage를 포함한 in-batch negative 를 사용한다. 그리고 question-passage 쌍들을 큰 데이터셋 (NQ, TriviaQA, SQuAD) 에 대해서는 40 epoch 만큼, 작은 데이터셋 (TREC, WQ)에 대해서는 100 epoch 학습시킨다. 또한 lr 은 $10^{-5}$ 로 설정하고, optimizer은 Adam 을 사용했다. (dropout : 0.1)

각 데이터셋에 대해서 잘 학습되는 retriever을 유연하게 다루는 것도 좋지만, 다양한 데이터셋에 대해서 전반적으로 좋은 학습률을 가지는 retriever 을 찾아내는 것 또한 좋은 접근이 딜 것이다.

따라서 본 논문에서는 multi-dataset encoder을 학습하기 위하여 SQuAD 데이터셋을 제외한 다른 데이터셋을 병합하였다. 또한 BM25, BM25 + DPR, traditional retriever 을 모두 실험해보았다. 이 과정에서 BM25 와 DPR의 결과를 결합하기 위해서 $BM25(q, p) + \lambda * sim(q,p)$ 와 같이 선형적 결합으로 모델을 구현하였다. ($\lambda = 1.1$일 때가 가장 성능이 높았다.)

5.1 Main Results

본 논문에서 5가지 데이터셋에 대해서 top-k passage를 뽑아내는 passage retrieval을 진행했다. SQuAD dataset를 제외하고, DPR은 BM25 보다 모든 데이터셋에 대해 더 높은 성능을 보였고, k가 작을 때 특히 다른 데이터셋들 간의 정확도의 gap이 커졌다.

multiple dataset을 이용하여 학습을 진행한 결과, 5가지 데이터셋 중 가장 작은 크기를 가진 TREC dataset 이 매우 큰 성능 향상을 보였다. 반대로, Natural Questions 와 WQ 는 작은 성능 향상을 보이며, TriviaQA의 경우 오히려 조금 낮아지기도 했다. 이 결과는 추후 DPR 과 BM25의 결합에 의해 더욱 향상될 수 있을 것이다.

So why the SQuAD performs better in BM25?
1. anntoators 들이 passage를 본 후에 질문을 작성했기 때문에, passage의 키워드가 포함되어 있을 확률이 높다.
2. data들이 Wikipeidia 에서 500개 정도의 데이터를 추출했기 때문에, bias 가 있을 가능성이 높다.

5.2 Ablation Study on Model Training

Sample efficiency

각 training dataset의 크기에 따라서 정확도가 달라지게 되는데, 그래프에서 보다시피 dataset의 크기가 1k 개만 되어도 BM25의 성능을 능가하는 것을 볼 수 있다. 또한, retrieve 하는 top-k 수가 증가할수록 성능 또한 증가하게 된다.

In-batch negative training

위 표는 negative passage의 선정 방식, Negative passage의 개수, In-batch negative 사용 유무, retrieve 하는 passage의 수에 따른 성능의 차이를 나타낸다.

뚜렷하게, #N(negative passage의 수) 가 커짐에 따라서 성능이 좋아짐이 나타났으며, Gold 방식 단일로 사용하는 것보다, BM25 기준 negative passage를 1개씩 섞어서 사용해 주는 것이 높은 성능을 나타냈다.

하지만, BM25 기준 negative passage의 수를 1개에서 2개로 늘린 결과, 성능의 차이가 거의 나타나지 않은 것으로 보아, BM25의 수는 모델에 크게 영향을 주지 않는다.

개인적으로 조금 흥미로웠던 것은, In-batch negative passage method를 활용한 결과가 단지 computational efficency를 보장하는 것 뿐만 아니라, 성능적인 측면에서도 의의가 있었다.

Impact of gold passages

Gold passage의 필요성은 다음과 같이 실험을 통해 알아냈다. Dist. Sup은 BM25에 따른 negative passage를 의미하는데, 이에 비해 1% 정도의 성능 향상을 보이는 것으로 보아, Gold passage가 더욱 좋은 방법이라는 것을 알 수 있다.

Similarity and loss

먼저, similarity function 에 대해서 두가지 방식인 Dot Product, L2 distance 를 비교하게 된다. 마찬가지로 Loss function 에 대해서 2가지 방식을 비교하는데, NLL (Negative log likelihood)와 triplet loss 를 비교한다.

결과적으로 Dot Product 와 NLL 을 사용했을 경우 retrieval 성능이 좋았기 때문에, 이 두 가지 방식을 이용하여 모델을 구성했다.

Cross-datset generalization

이외에도, 추가적인 fine-tuning 이 필요하지 않다. 본 논문에서는, 특정 dataset 을 이용해 학습한 모델을 다른 dataset에 적용해봄으로써 이를 증명한다. NQ dataset에 대해서만 DPR를 학습시킨 후, WQ, TREC에 실험을 해본 결과, 유의미한 결과를 띄며, 상당히 높은 성능을 내는 것을 확인하였다.

5.3 Qualitative Analysis

BM25 보다 DPR이 더 높은 성능을 내는 것에도 불구하고, BM25과 같은 Term-matching 방법은 특정 구나 선택적 키워드에 대해 sensitive 하다. 반면 DPR은 semantic relationship을 더욱 잘 표현하게 된다.

5.4 Run-time Efficiency

The main reason that we require a retrieval component for open-domain QA is to reduce the number of candidate passages that the reader needs to consider, which is crucial for answering user’s questions in real-time. We profiled the passage retrieval speed on a server with Intel Xeon CPU E5-2698 v4 @ 2.20GHz and 512GB memory. With the help of FAISS in-memory index for real-valued vectors10, DPR can be made incredibly efficient, processing 995.0 questions per second, returning top 100 passages per question. In contrast, BM25/Lucene (implemented in Java, using file index) processes 23.7 questions per second per CPU thread.

On the other hand, the time required for building an index for dense vectors is much longer. Computing dense embeddings on 21-million passages is resource intensive, but can be easily parallelized, taking roughly 8.8 hours on 8 GPUs. However, building the FAISS index on 21-million vectors on a single server takes 8.5 hours. In comparison, building an inverted index using Lucene is much cheaper and takes only about 30 minutes in total.

6. Experiments: Question Answering 🧐

6.1 End-to-end QA System

본 논문에서는 서로 다른 retriever system에 대해서 유연하게 적용할 수 있는 end-to-end QA system을 구현했다. 이 시스템은 neural reader 로 구성되어 있다.

먼저, retriever이 top-k retrieved passage를 제공하면, reader model은 passage들에 대한 selection score 을 각 passage에 부여하게 된다. 그리고 각 passage들에 대해서 answer span을 추출하고, 각 span 마다의 점수를 부여하게 된다. 결론적으로 가장 높은 passage score에서의 answer span 이 정답으로 추출된다.

이 과정에서 passage selection model은 reranker 이라는 새로운 모델을 사용하는데, question 과 passage 간의 cross attention을 이용해서 passage 간의 similarity 를 계산한다. 이 연산은 decomposable 하기 때문에 많은 passage에 대해서 적용할 수는 없지만, dual-encoder보다 성능이 좋기 때문에, 작은 top-k 에 대해서 이 과정을 수행한다.

식은 위와 같은데, $\hat{P}$ 라는 모든 Top-k passage 에 대해서 cross-attention 을 수행하고, 해당 값을 softmax 로 학습시켜 가장 연관도가 높은 passage를 찾는다. 그 후에, 해당 passage에서 $w$ 라는 learnable vector을 이용해서 start token, end token 을 곱한 값을 answer span score 로 적용하여 answer span 을 찾게 된다.

reader의 학습 과정은, positive-passage 에 대한 selection score의 log-likelihood 를 통해 학습되며, answer span은 positive passage에서의 모든 answer span의 marginal log-likelihood를 최대화하는 방향으로 학습된다. 하나의 passage 내부에서 정답이 여러 번 나타날 수 있기 때문에, 모든 answer span 에 대해서 학습한다.

6.2 Results

각 Model, dataset의 통합을 기준으로 위와 같이 정확도를 측정했다. 전체적으로 retriever의 정확도가 높을수록 end-to-end 정확도가 높아진다. 다른 모델들 (ORQA, REALM, etc)은 모델을 위한 pre-training을 수행했고, 높은 계산복잡도를 지니고 있지만, 본 논문의 DPR 모델은 추가적인 pre-training 없이 간단하게 구현하여 더 높은 성능을 보였다.

추가적으로, Retrieval model 과 reader model을 joint 하여 같은 하나의 모델로써 동시에 훈련시키는 실험 또한 해보았으나, 39.8EM을 달성하며 독립적인 retrieval, reader model을 사용하는 것이 더욱 높은 성능을 가진다는 것을 확인했다.

8. Conclusion 🎬

본 논문에서 제시한 dense retrieval method가 기존의 traiditional sparse retrieveal componet 를 능가하고, 잠재적으로 대체하였다. 간단하게 dual-encoder를 사용함으로써 놀라운 성능을 보였으며, 이 속에 몇몇 중요 요소들이 존재하기도 했다. 더 나아가서 이 논문에서의 시험적 분석은, 더욱 복잡한 모델들이 항상 추가적인 value를 제공하는 것은 아니라는 것 또한 알게 되었다. 이러한 방식으로, 결국 본 논문의 방식으로 SOTA를 달성하였다.