[논문 리뷰] SEAL: Autoregressive Search Engines: Generating Substrings as Document

 
ODQA와 같은 Konwledge intensive task에서 Reader component에는 autoregressive model이 de-facto이나 Retrieval system에는 몇몇 시도들이 있지만 autoregressive model이 자리 잡고 있진 않다. 본 연구에서 autoregressiv model과 FM-Index를 활용한 generative retrieval을 제안한다. KILT의 여러 dataset에 대해 SoTA를 달성하였다.
 
논문 : https://arxiv.org/pdf/2204.10628.pdf

 

Abstract

Knowledge-intensive language task는 주어진 corpus에 대해 correct answer과 그 결과의 supporting evidence를 retrieve하도록 한다.
Autoregressive model은 reader component의 de-facto standard이다. 이 논문에서는 이를 retrieval problem에도 적용할 수 있음을 언급하며, search space를 hierarchical structures로 나누어 retrieve하는 이전의 연구(DSI)와 달리 search space내에 어떠한 structure를 강제하지 않는 방법을 제안한다. passage내의 모든 ngram을 possible identifier로 사용한다.
 
Autoregressive model이 query에 대해 distinctive ngrams을 생성하고 scoring하도록 한다. ngrams은 full passage에 매핑되어 있으므로 passage를 retrieve할 수 있다.
 
이 제안은 이전의 Autoregressive approach보다 outperform하며, KILT benchmark의 몇몇 dataset에서 SoTA를 달성했다. 훨씬 적은 memory로!

---

Current

ODQA나 Fact-checking와 같은 Knowledge-intensive tasks의 popular paradigm은 search engine과 machine reader component를 결합하는 것이다. 최근에 Autoregressive language model 연구가 급등하고 모델 사이즈가 커지면서 reader component의 de-facto가 되었다. 그러나 여전히 retrieval approach에는 autoregressive model로 갈아탈 만큼의 변화 없는 상태이다. 어느정도 evidence를 생성할 순 있지만 hallucinate non-factual content 문제로 신뢰하기가 어려운 상태이다.

---

Previous work

최근에 autoregressive language model이 intermediate target for retrieval로서 identifier strings for document를 생성하도록 하는 연구들이 있다. (e.g. Wikipedia page titles, cluster tree) 이렇게 evidence를 바로 생성하지 않고 identifier를 활용하면 search space내에서 structure를 유도할 수 있고, full unstructured passage에 바로 접근하는 것보다 memorize, learn, retrieve 모든게 더 쉽다. 또한 valid identifier만 생성하도록 하기 위한 constrain beam search decoding with prefix tree를 적용하기도 쉽다.

---

In this work, we propose a solution that does not force any structure in the search space, but rather uses all the ngrams occurring in a document as its identifiers.

 

SEAL (Search Engines with Autoregressive LMs)

Autoregressive model과 FM-Index(compressed full-text substring index)를 결합한 retrieval solution

• Autoregressive model의 생성을 the FM-Index으로 제한하여 document에 없는 ngram을 생성하지 않도록 한다.
• FM-Index는 모든 document의 정보를 제공하므로 SEAL이 어떠한 위치에 있는 어떠한 span도 모두 생성할 수 있도록 한다. 각 document에 있는 모든 substring들을 explicitly하게 인코딩할 필요도 없이!
• 참신한 scoring fuction설계 하였는데, 이는 LM probabilities와 FM-Index frequencies를 결합하여 multiple ngrams의 결과를 intersect하도록 한다.
  • FM-Index frequencies: the number of occurrences of the ngram in the whole corpus

---

Related work - Retrieval with Identifiers (ex. title, hierarchical clustering)

• title: title identifier은 passage-level retrieval에는 적합하지 않음. (title은 document에 매핑되지만 더 세분화된 passage를 위한 건 아니니까)
• hierarchical clustering: 이것과 달리 SEAL은 Identifier strings가 반드시 하나의 document에서 나타나야하는 것이 아니다.

---

Background

Retrieval system은 Retrieval corpus R에서 ordered list of documents d1, d2, . . . , dn를 불러오는 것이며, query와 document는 lists of tokens <t1, t2, . . . , tN> 이고 각 token은 vocabulary에서 온다.
Span of tokens in text를 ngram이라 부르며, 전체 retrieval corpus에서 해당 ngram이 나온 빈도수를 F(n, R)로 표기한다.
 

FM-Index

SEAL은 hallucination을 방지하기 위해 모든 substring이 corpus에 있는 것을 보장하면서도 효율적으로 substring을 identification 할 수 있는 data structure를 필요로 한다. 그것이 바로 compressed suffix array로 구성된 FM-Index이다.

• ({token1: doc_id1, doc_id5, … }의 형태인 inverted indice도 아니고 document내의 모든 k suffixes를 explicitly하게 인코드 해야하는 prefix tree도 아님)

 
FM-Index는 corpus size에 linear하며, small vocabularies만 가지므로 상당히 작다! 이렇게 만들어진 FM-Index는 추후 scoring할 때 any sequence of tokens의 빈도수를 세기 위해서도 사용된다.
 
FM-Index는 Burrows-Wheeler Transform(BWT)기반으로 생성된다. BW결과 및 활용 방안은 다음과 같다.
 
 

BWT

query로 'AN'이 주어지고, database에 'BABABA'가 있을 때, 어떻게 찾는지 살펴볼 것이다. (reference)
크게 database의 내용을 BWT로 바꾸는 방법, BWT의 성질, BWT를 활용하여 query를 찾는 방법으로 나누어 설명한다.
 
 
1) database의 내용을 BWT로 바꾸는 방법

• BANANA(database 내용) 끝에 database에서 등장하지 않은 문자로 null termination을 붙인다. 여기선 $ 로 설정하여 "BANANAS$" 가 된다.
• BANANA$를 오른쪽으로 한글자씩 rotation하며 복제한다. 결과는 그림 ① rotate가 된다.
• 행렬을 알파벳순으로 정렬한다. termination character($)는 가장 처음 순서이다. 결과는 그림 ② sort alphabetically가 된다.
• 이렇게 생성된 행렬의 마지막 column이 BWT결과이다. BWT("BANANA$") = ANNB$AA 따라서 BWT column은 database의 original text를 모두 들고 있다. (permutation)
• 앞으로 우리가 활용할 정보는 가장 첫 column과 마지막 column이다. BWT의 결과인 마지막 column만 들고있으면 된다! 첫번째 column은 그 BWT 결과로 reconstruct할 수 있기 때문이다.

 
2) BWT의 성질

• BWT는 invert 성질을 가지고 있다. 즉 BWT의 결과를 활용하여, 적용하기 전의 원본 행렬을 만들 수 있다.
• 먼저 가장 첫 column을 reconstruct하기 위해서는 BWT column을 알파벳순으로 정렬하면 된다. 그림 ①설명
• 중간 column들을 reconstruct하기 위해서 먼저 글자에 인덱싱을 하여 같은 글자들을 구분하자! 그 다음 이 행렬을 만들 때 row별로 오른쪽으로 한글자씩 rotation했다는 점을 떠올려보자. 마지막 column글자 다음에 오는 글자는 바로 가장 첫 column의 글자이다. 이 정보를 활용하여 첫번째 row를 복구해보자. $ 다음에 올 글자를 찾기 위해 마지막 column이 $ 인 row를 보면 첫번째 column이 B1이다. 계속하여 마지막 column이 B1인 row의 첫번째 column을 찾으면 A3이다. 이를 끝까지 반복하면 $BANANA가 복구 된다. 이러한 방식으로 original text를 복구할 수 있다. BWT를 통해 정보를 굉장히 압축할 수 있다는 걸 알게되었다!

 
3) BWT를 활용하여 원하는 패턴(query)을 찾는 방법

• 패턴을 더 빠르게 찾기 위해 두 가지 전처리가 필요하다. 먼저 row를 나타내는 index를 표시한다.
• 다음 마지막 column이 첫 column에 있는 인덱스를 표시하는 L2F(i)를 표시한다. 이것을 만드는 이유는 backward로 searching하기 때문이다.(e.g. query가 "AN"이라면 N부터 찾고 A를 찾는 방식) 어떻게 찾는지 보자!
• backward로 찾기 때문에 반대로 N부터 찾고 나서 N '이전에' 올 글자를 찾아야 한다. 맨 처음에는 모든 행이 searching 대상이 된다(top=0 ~ bottom=6). 먼저 Last에서 검색을 시작한다. Last에서 N이 있는 곳은 i=1, i=2이다. N 이전에 올 글자를 찾기 위해서는 First에서 현재 글자 N이 있는 곳을 찾아야 하므로 L2F(i)를 활용한다. L2F(1)=5, L2F=6이므로 searching 대상은 top=5 ~ bottom=6이다. 두 행 모두 Last로 A를 들고 있기 때문에 둘다 정답 instances가 된다.
• query "AN"에 대해 검색된 instances는 A2와 A3이다. 이 instances는 위에서 복구된 첫번째 row(database의 original text)와 매핑되어 있으므로 database내에서 위치를 찾아올 수 있다. 복구된 첫번째 rows는 $B1A3N2A2N1A1였다. A3을 시작으로 query length만큼 살펴보면 A3N2를 찾을 수 있고, 마찬가지로 A2를 시작으로 살펴보면 A2N1을 찾을 수 있다.
  • FM-Index에서 ngrams와 full passage가 매핑되어 있는 이유

 
 
여기까지 BWT에 대해 알아보았다. FM-Index도 이것을 기반으로 하여 First column, Last column으로 압축된 정보 안에서 ngram을 찾는다.

---

Method

1) autoregressive retrieval → LM scoring

O(|V| log|V|)는 prefix tree → 처음엔 모든 vocab에 대해 검토하는데 그 다음부턴 unattested continuations들은 block하고 attested ones들만 top~bottom설정 후 search하여 log|V|이 든다.

• AR모델을 통해 구한 P(n|q)가 document에 대한 점수가 된다. ngram의 length길이에 따른 monotonically decreasing score문제가 있으므로 length를 고정하였다.

2) Factoring in FM-index frequencies → LM + FM scoring

• distinctive ngram을 뽑기 위해 ngram의 unconditional probability인 frequency를 활용한다. (모든 document에 흔하게 있는 span이면 패널티!)
•  distinctive ngram을 생성하기 위해 해당 ngram이 query에 상관없이 모든 문서에 등장하는 FM-Index frequency를 활용하여 unconditional probability를 구한 후 패널티로 수식에 적용한다. (inspired by BM25, TF-IDF)

unconditional prob

LM+FM scoring 수식

• 분모에서 해당 ngram이 question과 관련 없는 곳에도 등장하는 정도를 확률로 계산하여 패널티를 부여한다.
• 분자에서 P(n|q)에서 question과 무방하게 빈도가 높은 정도를 확률로 계산하여 뺌으로써 패널티를 부여한다
• 추가로 beam search를 수정하여 (과정에서 고려되었던) 디코딩된 모든 시퀀스를 트래킹하였고 따라서 beam size보다 훨씬 많은 ngram을 scoring하고 있다.

* 이 LM+FM scoring 수식을 통해 ngram의 길이에 따른 monotonically decreasing scores 문제도 완화하였다는데, distinctive ngram을 뽑도록 한 것이지 길이에 어떻게 영향을 미치는지는 더 알아보아야 겠다.
*혹시 알고 계시는 분이 있다면 댓글 달아주시면 감사하겠습니다.
 

3) An Intersective Scoring for Multiple Ngrams → LM + FM intersective scoring

• document간 점수가 같을 때 우위를 가리기 힘들고, 중요한 정보들이 흩어져있을 수 있으므로 document 내 하나의 ngram만 고려할 수도 없다. 따라서 document 내의 여러 ngram의 contribution을 aggregate한다.
• 이때 document 내에 같은 ngram이 여러개면 중복 계산되어 overscoring되므로 ngram들의 subset K를 생성하여 한번 등장한 것은 중복 계산하지 않도록 하였다.LM+FM intersective scoring 
• cover(n, K)는 여러 유사한 ngram이 반복적으로 등장하는 문서에 대한 overscoring을 피하기 위한 weight이다.

LM+FM intersective scoring 수식

 

 

(※ 아래 그림에서는 ①번 뒤에 LM + FM scoring과정이 생략되어 있음)

 

---

SEAL Training (passage-level)

• supervised
  • input: question
  • output: span in ground truth document or title
  • e.g. (ngrams of length=k) 
    • question → span 1
    • question → span 2
    • question → span |d| - k
    • question → title
• unsupervised (example별 unsupervised 방식과 jointly 학습하며, unsupervised 예시는 아래와 같음)
  • input: any span in the document (uniformly)
  • output: another span in the document or title
  • e.g. 
    • span1 → span2
    • span3 → span5
    • span 2 → title

supervised, unsupervised 두 가지를 co-training task로 학습하며, (DSI)에서 사용된 프롬프트를 참고하였다.
 

---

 
<comment>
 
SEAL은 FM-Index를 통해 corpus의 모든 정보를 매우 압축적으로 활용하였으며, hallucination없이 passage내(title포함)에 존재하는 ngram identifier를 생성하고 scoring함으로써 passage를 retrieve한다.
 
무엇보다 knowlege를 굉장히 압축하는 BWT기법을 활용한 것이 좋았고, 그 덕에 가능했던 document(passage-level)내에 있는 모든 ngram들을 possible identifier로 사용한 점이 기억에 남는다. 또 unsupervised & supervsied task를 co-training했던 것도 좋았다 (이건 여기서 제안된 건 아니지만!)