원제: Dense Passage Retrieval for Open-Domain Question Answering

Karpukhin, V., Oğuz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., & Yih, W.-t. (2020). Dense Passage Retrieval for Open-Domain Question Answering. arXiv. https://doi.org/10.48550/arXiv.2004.04906

잡소리
이후에 읽게 될 RAG의 Retrival을 담당하는 기술이다.
사실 ATLAS 읽다가 생각보다 더 빡세서 잠깐 쉬러왔다.

1. Introduction

QA: 대규모 문서 집합을 사용하여 사실형 질문에 답하는 과제
reading model의 2단계 프레임워크
1) Context Retriever을 활용해서 답을 포함할 가능성이 있는 소수의 문단을 선택하고
2) Machine Reader가 검색된 문맥들을 검토해서 정답을 찾아낸다.
하지만 오픈 도메인 QA를 위의 방식으로 환원했을 때 실제 환경에서 성능이 크게 저하되는 경우가 자주 관찰된다고 한다. 이는 곧 검색 성능(Context Retriever)의 문제라고 이해할 수 있다.

기존의 Retriever

1) Inverted index(키워드 매칭): TF-IDF, BM25 등 질문-문맥을 고차원 희소 벡터로 표현해서 매칭한다.
2) dense/latent semantic encoding: 설계상의 희소표현을 보완(단어는 다르지만 같은 의미)
Dense위주의 검색 시스템은 문맥에 따른 단어를 제대로 검색할 수 있고, 임베딩 함수의 조정을 통해 과제 특화 표현을 가질 수 있다는 장점이 있다. 이때 검색의 효율성을 위해 특후산 메모리내 데이터 구조와 인덱싱 기법을 사용하여 MIPS 알고리즘을 활용한다.

MIPS: 주어진 Query(q)와 벡터 집합($p_N$)에 대해 $argmax_{p_i}q \cdot p_i$. 즉 벡터 집합에서 query에 가장 잘 맞는 벡터를 내적을 통해 구함.

그러나 Dense-vector 표현을 학습하기 위해선 대규모의 질문-답변 쌍이 필요하기에 기존에는 TF-IDF의 성능이 더 좋았다. 이를 해결하기 위해 ORQA가 등장한다.

ORQA

ICT Objective: 추가적인 사전학습을 위해 mask된 문장을 포함하는 블록을 예측하는 함수
이후에 Question Encoder(질문 -> 벡터로 만드는 모델), Reader(문단에서 정답 span을 찾아내는 모델)를 joint fine-tuning한다. 즉, Reader가 정답을 맞혔는지를 바탕으로 Reader뿐만 아닌 Question Encoder의 파라미터까지 업데이트를 진행한다.
그러나 여전히 두가지 한계가 존재한다.
1) ICT의 pre-training의 계산 비용이 크다.
2) Passage Encoder은 joint fine-tuning을 진행하지 않기에 최적의 표현이 아닐 가능성이 있다.

DPR

추가적인 fine-tuning없이 기존의 질문-문단/답변 쌍을 활용해 더 나은 Dense embedding 모델을 학습하는것이 목적이다. 즉,
1) 적절한 학습 설정으로 기존의 질문-문단/답변 쌍만으로 Question Encoder와 Passage Encoder을 fine-tuning하는 것만으로 기존의 BM25를 능가하도록 한다. 즉 추가적인 pre-training이 반드시 필요한 것은 아님을 시사한다.
2) 더 높은 검색 정밀도가 실제로 더 높은 end-to-end QA 정확도로 이어진다는 것을 검증한다.

2. Background

Open Domain QA의 전제조건

사실형 질문에 대해 다양한 주제를 포함하는 대규모의 corpus(말뭉치?)를 사용해 답을 찾아야 한다. 이때
1) 정답은 반드시 주어진 corpus 내에 존재해야 한다.
2) Generate가 아닌 Extract로 token단위로 시작 위치와 끝 위치를 골라 잘라낸다.
3) 정답은 반드시 span, 즉 연속된 텍스트 구간이여야 한다.(중간에 자르는 것 x)

원리

문서 집합에 포함된 D개의 문서 $d_1, d_2, ...,d_D$가 있고, 각 문서를 동일한 길이의 텍스트 문단으로 구분해서 기본 검색 단위로 사용한다. 즉, $C = \{p_1, p_2,...,p_M\}$로 전체 corpus를 구성한다.
목적은 질문 q가 주어졌을 떄, 질문에 답할 수 있는 텍스트 구간을 포함하는 문단 $q_i$를 찾아내는 것이다.
즉, 형식적으로 검색기는
$R:(q,C) \rightarrow C_k$ (이때 $C_k \subset C$ and $|C_k|=k<|C|$)
로 정의된다. 고정된 k값에 대해 검색기는 to-k 정확도로 평가할 수 있고, 이는 $C_k$가 질문에 대한 정답 구간을 포함하는 문단을 포함하는 질문의 비율(${정답 구간을\, 포함하는\, 문단}\over{전체\, 질문\, 개수}$)이다.

3. DPR

DPR의 목적은 QA의 두 단계 중에서 1단계인 Context Retriever를 개선하는 것이다. 간단한 원리는 문단을 low-dimensional의 연속적인 공간에 index하여 실행 시에 입력과 관련된 상위 k개의 문단을 reader에 효율적으로 검색할 수 있도록 하는 것이다. 이때 입력 문단 M개는 매우 큰 개수(해당 논문에선 2100만 개)이고, 최종적으로 20~100개정도의 작은 개수 K개만 추려내는 것이 목적이다.

원리

$E_p$: Passage Encoder: 텍스트 문단의 종류와 관계없이 d차원의 실수값 벡터로 매핑하는 Encoder. 검색에 사용할 모든 M개의 문단에 대한 index를 구축한다.
$E_q$: 런타임시에 입력 질문을 d차원 벡터로 매핑하는 Encoder.
$E_p$와 $E_q$의 내적, 즉 $sim(q,p)=E_q(q)\top E_p(p)$가 질문과 문단 간 유사도이다.
$E_p$와 $E_q$를 나눈 이유는 매 질문마다 모든 문단을 다 확인하는 것은 불가능하기 때문이다. 그래서 cross-attention과 같이 표현력이 높은 구조가 존재해도 분해시킬수 없기에 사용할 수 없다.
분해가능(decomposable)한 구조는 코싸인 유사도와 같이 L2의 변형들인데, 이 중 어떤 함수를 선택해도 유사한 성능이 나온다고 한다.

Encoder

어떤 신경망으로도 가능하지만, 해당 논문에서는 두 Encoder 모두 BERT를 사용했다. 이때 d = 768이다.

Inference

$E_p$를 적용해서 벡터를 계산하고 FAISS를 사용해 indexing.

FAISS: Query와 가장 비슷한 벡터(top-K)를 빠르게 찾기 위한 라이브러리
ANN을 활용해서 약간의 정확성을 포기하고 속도를 높임. 특히 DPR에선 HNSW를 사용

HNSW: 벡터를 다층 그래프로 연결해 가까운 이웃을 빠르게 찾아가는 근사 검색 구조
상위층에서 적은 노드수로 멀리 이동하고, 더 이상 가까워질 수 없을 때 아래층으로 내려가며 최하층에 실제 벡터가 존재한다. created by ChatGPT

런타임시에 질문 q가 주어지면 Embedding $v_q$ = $E_q(q)$를 계산하고, $v_q$에 가장 가까운 임베딩을 가진 top-k의 문단을 검색한다.

Training

앞서 언급된 $sim(q,p)=E_q(q)\top E_p(p)$가 검색을 위한 좋은 ranking 함수가 되도록 encoder를 학습하는 것은 metric learning 문제이다. 즉, 관련 잇는 질문-문단 쌍은 L2거리가 더 작도록하고, 관련이 없으면 L2거리가 더 커지도록 임베딩 함수를 학습해야 한다.

학습 데이터 $D = \{(q_i, p_i^+, p_{i,1}^-,...,p_{i,n}^-)\}$
로 하나의 질문 $q$, 하나의 관련 문단인 $p_i$, n개의 관련없는 문단 $p_{i,j}^-$를 갖는다. 이때 $q$와 $p_i$ 사이의 거리는 최소가 되어야 하고, $q$와 $p^-$사이의 거리는 최대가 되어야 하기에, 손실 함수는
$L(q_i, p_i^+, p_{i,1}^-,...,p_{i,n}^-) = -log{{exp(sim(q_i,p_i^+))}\over{exp(sim(q_i, p_i^+)) + \sum_{j=1}^n exp(sim(q_i, p_{i,j}^-))}}$

Positive/Negative passage

Positive: 데이테셋에 명시적으로 제공된다.
Negative: Positive 외의 passage를 기본적으로 Negative로 간주할 수 있다. 이때 Negative passage를 어떻게 선택하는지는 3가지로 나누니다.
1) Random: corpus에서 랜덤으로 선택한 passage
2) BM25: 정답을 포함하지 않지만 Question과 가장 많이 매칭되는 BM25 상위 passage(의미적으로 헷갈리기 쉬운 passage)
3) Gold: Training Set에서 등장하는 다른 질문과 짝지어진 Positive passage
DPR에서는 같은 mini-batch의 gold passage와 BM25 Negative passage 한개를 활용한다.

In-batch negatives

Mini-batch에 B개의 질문이 있고, 질문마다 하나의 관련 passage가 연관되어 있다고 가정한다. 그리고 B에 대해 질문 임베딩 Q와 Passage 임베딩 P를 두면
(각각 $B \times d$ matrix)
$S = QP^\top$의 S가 ($B\times B$) 크기의 유사도 점수 행렬이 된다. 즉, 각 행은 하나의 질문과 B개의 passage간 유사도를 나타낸다.
이 행렬의 대각행렬$(q_i, p_i)$는 Positive passage이고, $i \neq j$인 경우라면 Negative Passage이다.

4. Experimental Setup

위키피디아

DrQA의 Pre-training 코드를 적용하여 정제된 텍스트를 추출하고 동음이의어 페이지를 제거한다.
서로 겹치지 않는 여러 개의 텍스트 블록(100단어 길이의 passage)으로 분할한다. 이때 각 passage 앞에 해당 passage가 속한 위키피디아의 문서 제목을 덧붙이고, 끝에 [SEP]토큰을 추가한다.
해당 passage들이 검색의 기본 단위로 사용되고, 최종적으로 2천만개의 passage가 생성된다.

Question Answering Datasets

NQ: End-to-End 질문 응답을 위해 설계된 데이터 셋
TriviaQA: 웹에서 수집된 정답 기반 Trivia 질문 집합(영화, 역사 등 잡학 지식)
WebQeustions: Google Suggest API를 사용해 선택된 질문 - Freebase entity의 정답
CuratedTREC: TREC QA 트랙에서 질문을 수집
SQuAD v1.1: 독해 벤치마크 데이터셋. 주석자에게 위키피디아 문단 제시 - 텍스트에서 답변
BM25로 검색한 상위 passage 중 정답을 포함하는 가장 높은 순위의 passage를 Positive Passage로 사용.
해당 데이터셋들을 Train / Dev / Test로 나누어서 사용

5. Passage Retrieval Test

여기선 간단하게만 설명한다. 세세한 설정이나 구체적인 수치는 논문을 직접 확인해보자.
기존의 BM25에 비해 SQuAD를 제외한 데이터셋에서 더 높은 성능을 보이고, 특히 top-k의 k가 작을수록 차이가 더 커졌다.
멀티 데이터셋에선 큰 개선이 나타나지 않았다. + 일부는 DPR과 BM25를 결합한 방식이 더 나았다.
BM25는 선택적 키워드나 구문에는 강하지만 어휘 변형에나 의미적 관계에는 약하다. 반면 DPR은 의미적 표현에는 강하지만 드물게 나타나는 핵심 구문은 놓친다.
Run-time Efficieny에선 BM25는 CPU 스레드당 초당 약 23개의 질문을 처리하는 반면, DPR에선 초당 995개의 질문을 처리한다.
단, 구축 비용에서 BM25는 30분이면 충분하지만 DPR에선 임데이 생성에 8.8시간, FAISS index 구축에 8.5시간이 필요하다.

6. QA Test

End-to-End 질문 응답 시스템을 구현하여 신경망 reader가 k개의 검색된 passage에서 각 passage에 대해 점수를 할당하고, 가장 높은 점수를 갖는 passage에서 선택된 최고 점수의 span으로 결정된다.
이때 passage 선택 모델은 소수의 검색 후보에서 선택하기에 cross-attention을 활용한다. 즉, $P_i \in R^{L \times H}$이 i번째 passage의 BERT라고 할 때(L은 passage 최대 길이, h는 hidden state dimension)

이때 $P_i=[P_i[CLS],...,P_i[L]] \in R^{L \times h}$ 이고,
$W_{start}, W_{end}, W_{selected} \in R^h$는 학습 가능한 벡터이다.
i번째 passage에서 s번째 단어에서부터 t번째 단어까지의 span score은
$P_{start,i}(s) \times P_{end,i}(t)$이고, passage 선택 점수가 $P_{selected}(i)$이다.

결과

검색 정확도가 높을수록 최종 QA의 성능도 일반적으로 향상된다. 전반적으로 5개의 데이터셋 중 4개에서 기존 SOTA를 능가한다. 또한 joint learning을 제거했을 때, 검색기와 리더를 분리하여 각각 학습하는 전략이 더 단순하지만 더 나은 성능을 낼 수 있음을 보인다.
또한 DPR 기반 reader은 더 많은 passage를 고려하지만, 단일 GPU의 한 batch에 모두 적재할 수 있어서 지연 시간은 단일 passage와 거의 동일하게 유지된다.

결론

Question Encoder을 Reader와만 joint fine-tuning하는 것이 아닌, Passage Encoder와 joint fine-tuning하며 완전한 dual-encoder을 만든다. 그리고 기존의 BM25와 달리 Passage Encoder로 위키피디아를 FAISS에 미리 indexing한다.
즉, Retreival을 학습 대상으로 규정하여 $E_q$와 $E_p$를 학습한다.

Final

최근따라 느끼는거지만 엄청 혁신적인 뭔가보다 기존의 관념을 약간만 뒤집는 것 만으로도 엄청난 발명이 되는 것 같다.
근데 뭔가 이전의 Titans와는 다르게 새로운 모델을 만들었다보단 기존의 모델에 이것저것 추가했다의 느낌이기에 코드도 뜯어보려고 한다.