Meaningful

Meaningful

Greeting :)

[논문리뷰]KG-RAG: Bridging the Gap Between Knowledge and Creativity

Date:     Updated:

카테고리:

Sanmartin, D. (2024, May 20). KG-RAG: Bridging the gap between knowledge and creativity. arXiv.org. https://arxiv.org/abs/2405.12035

Problem Statement

1. Hallucination

LLMs(대형 언어 모델)는 종종 사실과 일치하지 않는 정보를 생성하는 경향이 있다. 이는 “환각(Hallucination)”이라고 불리며, 모델이 존재하지 않는 사실을 만들어내거나 잘못된 정보를 제공하는 문제이다. 특히 LLMs에서 잘못된 정보를 마치 사실인 것 처럼 생성해내는 경우가 종종 발생하며, 이는 LLMs의 신뢰성을 떨어트린다.

2. Catastrophic forgetting

재앙적 망각(Catastrophic forgetting)은 LLMs가 새로운 정보로 학습될 때 이전에 학습된 지식을 잊어버리는 문제를 말한다. 이는 모델이 지속적으로 새로운 데이터를 학습할 때 기존의 지식을 유지하기 어렵게 만든다.

3. Processing Long-Context

LLMs는 긴 문맥을 처리하는 데 어려움을 겪는다. 긴 대화나 문서에서 중요한 정보를 놓치거나 잃어버리는 경우가 발생한다. 이는 긴 문서나 대화에서 연관된 정보를 유지하고 처리하는 데 한계를 보인다.



Related Work

1. AI Agent

1

AI 에이전트는 지각(Perceptron), 뇌(Brain), 행동(Action)이라는 세 가지 핵심 구성 요소로 이루어져 있으며, 이들은 감지-계획-행동의 자율적 운영 주기를 통해 상호 작용한다. 이 세가지 구성 요소들을 통해 AI 에이전트의 자율적인 운영 주기인 ‘감지-계획-행동’ 사이클을 구현한다.

  • 지각(Perceptron)은 환경을 감지하고 이해하는 기능을 담당한다. 예를 들어 이지미 인식, 음성 인식, 텍스트 이해 등을 포함하여 에이전트가 외부 지식을 수집하는 전 과정이다.
  • 뇌(Brain)은 의사 결정을 내리고, 계획을 세우며, 에이전트의 지식과 기억을 저장하는 중추 역할을 한다. LLMs을 통합하여 동적 추론과 의사 결정을 수행하고 Knowledge Graph(KG)를 통해 구조화된 지식과 기억을 저장한다. 프롬프트 엔지니어링(Prompt Engineering)과 지식 증강(Knowledge Augmented) 등 LLMs의 추론 능력과 특정 task에 대한 성능을 향상시키는 연구가 활발히 진행되고 있다. 예를 들어, Chain of Thought (CoT), Tree of Thought (ToT), Graph of Thoughts (GoT), ReAct (Reason and Act) 등이 있습니다.
  • 행동(Action)은 의사 결정에 따라 행동을 실행하는 기는을 담당한ㄴ다. 예를 들어, 로봇 제어, 이메일 자동 발송, 챗봇등이 이에 해당한다.

2. Retrieval-Augmented Generation(RAG)

RAG(Retrieval-Augmented Generation)는 질의(query)에 대한 결과를 찾기 위해 외부 지식을 활용하는 방법이다. 특히, RAG는 외부 지식을 검색하는 Retrieval 모듈과 생성 모듈(Generator)을 결합하여 Open-Domain QA(ODQA)와 Knowledge Intensive Task(KIT)를 효과적으로 수행할 수 있다. 이 방식의 가장 큰 특징은 특정 작업에 구애받지 않는 Task-agnostic한 접근법을 제공한다는 점이다. RAG는 검색된 정보를 동적으로 주입하여, 모델이 최신 정보와 맥락을 기반으로 정확하고 일관된 응답을 생성할 수 있도록 한다. 이를 통해 다양한 응용 분야에서 높은 정확도와 신뢰성을 유지할 수 있다. 이전 포스터에서 자세하게 확인할 수 있다.([논문리뷰]RAG: Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks)



Method

1. Preliminaries

Large Language Models (LLMs)
기존의 언어 모델 학습 패러다임은 사전 학습(pre-training)과 미세 조정(fine-tuning) 두 단계로 구성되어 있었다. 그러나 초거대 언어 모델(LLMs)이 등장하면서 새로운 데이터셋에 대해 매번 미세 조정을 수행하는 데 막대한 자원이 필요하다. 이러한 이유로, 프롬프팅(prompting)에 대한 연구가 주목받고 있으며, 학습 패러다임도 사전 학습(pre-training), 프롬프팅(prompt), 예측(predict)이라는 세 단계로 전환되었다.

1

Language Model(LM)의 입력 프롬프트(입력 시퀀스)를 \(x\)라 하고, \(x = (x_1, x_2, \cdots, x_q)\)이며, \(x_i\)는 입력 프롬프트 시퀀스의 \(i\)번째 위치한 토큰이다. LM이 생성해내는 출력 시퀀스는 \(y\)로 정의하며, \(y = (y_1, y_2, \cdots, y_m)\)이다. LM은 위의 식과 같이 보통 \(P(y \vert x)\)의 조건부 확률을 최적화 하는 것으로 학습을 진행하게 된다. 이 때, \(P(y_i \vert y_{<i}, x)\)는 입력 프롬프트 \(x\)와 생성된 \(i-1\)번째 출력 토큰들을 고려한 \(i\)번째 출력 토큰의 확률이다.

Knowledge Graph Question Answering(KGQA)
Knowledge Graph는 트리플로 구선된 Knowledge의 집합이며, 트리플은 엔티티(Entity)와 릴레이션(Relation)으로 구성된다. 즉, \(G = (E, R)\)로 표현할 수 있다. 트리플은 \((e, r, e^{'})\) 혹은 \((h, r, t)\)로 표현 가능하다.

1

본문에서는 위와 같이 KG를 정의한다.

Knowledge Graph Question Anwering(KGQA)는 KG를 이용한 QA를 문제를 푸는 것으로, 정답을 찾기 위해서는 KG에서 여러 hop을 거쳐야 한다. 이 때, 이 multi-hop을 meta path라 하며, \(w_z = e_0 \xrightarrow{r_1} e_1 \xrightarrow{r_2} \ldots \xrightarrow{r_l} e_l\)로 표현한다. KGQA는 자연어로 구성된 질문 \(q\)와 KG인 \(G\)를 입력으로 받아 정답인 \(a \in A_q\)를 추론하는 문제인 것이다.

1

이를 수식으로 표현하면 위와 같다. \(P(w_z \vert q, G)\)는 가장 연관성 있는 path를 KG로부터 뽑아내는 확률이고, \(P(a \vert w_z)\)는 그 path로부터 정답으로 도달하는 확률값이다.


1) Storage

저장(Storage) 단계는 비구조화된 텍스트 데이터를 구조화된 지식 그래프(KG)로 변환하는 과정이다. 이 과정의 목표는 텍스트에서 엔티티와 관계를 추출하여 삼중(triple) 형태로 저장하는 것이다. 이를 위해 몇 가지 중요한 개념과 절차가 필요하다.

1

첫 번째로 Triple Extraction이다. 트리플은 (엔티티 - 릴레이션 - 엔티티)로 구성된다. 예를 들어, “Seth MacFarlane created Family Guy in 1999”를 트리플로 표현하면 다음과 같이 나타낼 수 있다. 이는 2개의 트리플로 구성된 2-hop path이다.

  • (Seth MacFarlane) - [is creator of] -> (Family Guy)
  • (Family Guy) - [created in] -> (1999)

논문에서는 트리플을 \(t = (e, r, e')\)로 표현하고, 위의 문장과 같이 텍스트 청크를 \(T\)로 표현한다. 위의 왼쪽 수식처럼 텍스트를 LM에 입력시켰을 때 관련이 깊은 n개의 트리플을 추출하는 과정이 Triple Extraction이다.

이 때, LM은 사전 학습된 언어 모델(pre-trained Language Model)을 나타내며, 이는 자연어 지시문(natural language instruction)으로 구성된 텍스트 프롬프트 \(T\)를 처리한다. 또한, 몇 가지 예시 텍스트를 트리플로 변환하는 예제들과 트리플을 추출하기 위한 텍스트 청크가 포함된다. 출력 \(\{t_i\}^n_{i=1}\)은 추출된 삼중 집합 \(\{(e, r, e')_i\}_{i=1}^n\)으로 구성되며, 여기서 \(i\)는 \(n\)개의 트리플 중 \(i\)번째 트리플을 의미한다. 이러한 과정은 위의 오른쪽 수식으로 표현되며, 특정 task에 대한 조건부 확률 분포 \(P(T^{'} \vert T)\)를 최적화하기 위해 LM을 설계한 것입니다. 여기서 \(T^{'}\)는 트리플 형태의 구조화된 출력이다.


2) Retrieval

1

Retrieval은 입력으로 들어온 질문(query) \(q\)를 기반으로 KG에 검색해 유의미한 meta-path를 검색하는 과정이다. 위와 같은 수식으로 표현되며, \(w_z\)가 meta-path이다. 즉, KG와 입력 query에 대한 여러 meta-path를 구하고 그 중 가장 확률값이 큰 path를 추출하는 것이다.

3) Answer Generation

1

앞서 두 과정을 통해서 최종적으로 path \(w_z\)를 얻었으면, 질문과 path를 LM에 입력시킨다. 이후 LM은 이 프롬프트에 알맞는 출력을 생성해내게되며, 위와 같이 수식으로 표현할 수 있다.

2. Model Architecture

1) Hypernode

KG-RAG에서 가장 핵심이 되는 부분은 Storage를 하는 방법이다. KG-RAG에서는 더 복잡한 정보 구조를 처리하기 위해 Hypernode라는 개념을 도입한다. Hypernode는 날짜와 같은 특정 맥락과 연결된 트리플을 나타내며, 이는 KG 내에서 다층적 관계를 표현할 수 있다. 예를 들어 “Seth MacFarlane created Family Guy in 1999”라는 프롬프트가 가정한다. 이 때, 위 문장은 다음과 같이 두 개의 트리플로 분해할 수 있다. 하지만, Hypernode를 도입할 경우 이는 다음과 같이 하나의 트리플로 표현이 가능하다.

  • Without hypernode
    • (Seth MacFarlane) - [is creator of] -> (Family Guy)
    • (Family Guy) - [created in] -> (1999)
  • With hypernode
    • ((Seth MacFarlane)-[created]→(Family Guy))-[in]→(1999)

이처럼 hypernode는 이러한 복잡한 구조를 더 잘 표현하고, 여러 레벨의 관계를 하나의 노드 내에서 관리할 수 있다는 장점이 있다. 다음의 그림이 Hypernode를 도식화한 그림이다.

1

위의 그림을 다시 한 번 살펴보면, 하나의 트리플을 하나의 노드로 만들고, 날짜와 같은 특정 맥락과 함께 트리플을 구성하는 것을 볼 수 있다. 이처럼, 기존 지식에 특정 맥락을 추가해 좀 더 복잡한 정보를 표현하게 하는 것이 hypernode이다. 현재 그래프 DB에 하이퍼노드로 이루어진 트리플을 저장하기 위해, 저자들은 객체를 해당 하이퍼노드와 연결하며, 하이퍼노드의 전체 의미를 레이블로 표시하는 것이다. 위의 그림처럼 기존 트리플을 남겨둔 상태로, 하이퍼 노드를 추가하여 그래프에 저장하는 것이다. 마지막으로, 생성된 KG를 사용하여 모든 엔티티, hypernode, relation에 대한 임베딩을 계산하고 이를 해당 meta data(e.g., 날짜, 시간)와 함께 벡터 데이터베이스에 저장한다. 이를 통해 KG-RAG 파이프라인의 검색 단계에서 KG를 통해 밀집 벡터 유사성(dense vector similarity) 검색을 수행할 수 있다.


2) Chain of Exploration(CoE)

1

KG-RAG는 이름에서도 알 수 있듯이, RAG에 기반한 QA모델이다. RAG의 핵심은 검색(Retrieval)이다. KG-RAG는 앞서 Storage단계를 통해 복잡한 정보를 포함하는 hypernode를 그래프 DB에 추가하였다. 이제 입력된 질문(query)로부터 정답을 추론하기 위해 생성된 KG에서 검색을 실시해야 한다. KG-RAG에서는 이 과정을 Chain of Exploration(CoE)라고 한다. 다시 말해, CoE는 사용자 질의에 응답하기 위해 생성된 KG 내의 엔티티와 릴레이션을 탐색하여 관련 정보를 추출한다. 위의 그림은 CoE의 과정을 보여준다.

이 CoE 알고리즘은 계획(planning), 검색(KG Lookups), 평가(Evaluation) 세 단계로 진행된다. 먼저 계획(planning)단계에서는 사용자의 쿼리를 바탕으로 그래프 탐색을 계획한다. 이는 몇 가지 샘플과 함께 사용자 쿼리를 프롬프트로 사용하여 탐색 계획을 수립하는 과정이다.

그 다음으로 검색(KG Lookups) 단계에서는 다시 두 가지 주요 과정으로 나눠진다. 먼저 초기 노드(엔티티)를 찾기 위해 벡터 유사성 검색(Vector Similarity Search)을 수행한다. 이는 쿼리와 가장 유사한 벡터를 가진 노드를 식별한다. 이후 KG에서 관련 노드와 관계를 검색하기 위해 사이퍼 쿼리(Cypher query)를 사용한다. 사이퍼 쿼리는 그래프 데이터베이스에서 데이터를 질의하는 데 사용되는 언어이다. (Neo4j 같은 그래프 DB)

마지막으로 평가(Evaluation)이다. 탐색 경로와 초기 쿼리의 일치 여부를 평가하여 탐색을 계속할지, 조정할지, 답변을 생성할지 결정한다. LLM을 사용하여 현재 탐색 상태를 평가하고 필요에 따라 탐색 계획을 조정한다.

Algorithm 1 Chain of Exploration (CoE) for KG Retrieval

1: procedure CoE(q, G)
2: exploration_plan ← Plan steps to explore through the graph
3: current_nodes ← ∅
4: path_traveled ← ∅
5: current_step ← 0
6: failed_tries ← 0
7: while current_step ≤ length(exploration_plan) and failed_tries < 3 do
8:     if is_node_exploration(step) then
9:         node_candidates ← VectorDB.Search(step)
10:        selected_nodes ← LM(prompt, node_candidates)
11:        path_traveled.add(selected_nodes)
12:    end if
13:    if is_relationship_exploration(step) then
14:        explorable_rels ← Cypher.Query(current_nodes)
15:        rel_candidates ← VectorSimilarity.Rank(explorable_rels, step)
16:        selected_rels ← LM(prompt, rel_candidates)
17:        current_nodes ← get_target_nodes(current_nodes, selected_rels)
18:        path_traveled.add(selected_rels, current_nodes)
19:    end if
20:    eval_outcome ← eval_state(path_traveled, q)
21:    if eval_outcome = needs refinement then
22:        exploration_plan ← redefine_CoT_steps(exploration_plan, q)
23:        current_step ← 1
24:        path_traveled ← {}
25:        failed_tries ← failed_tries + 1
26:    else if eval_outcome = continue then
27:        current_step ← current_step + 1
28:    else if eval_outcome = respond then
29:        return generate_answer(path_traveled, q)
30:    end if
31: end while
32: return "I am sorry, I could not find an answer to your question."
33: end procedure

CoE 알고리즘의 주요 요소는 다음과 같이 정리할 수 있다.

  • 탐색 계획 수립 (Exploration Plan): 초기 샘플과 쿼리를 기반으로 탐색 경로를 계획한다.
  • 노드 후보 검색 (Node Candidates Search): 쿼리와 관련된 초기 노드를 벡터 유사성 검색을 통해 찾는다.
  • LLM을 통한 필터링 (Filtering with LLM): 검색된 노드 후보를 LLM을 사용하여 필터링하고, 가장 관련성이 높은 노드를 선택한다.
  • 관계 탐색 (Relationship Exploration): 선택된 노드에서 가능한 관계를 탐색하고, 벡터 유사성 검색을 통해 관련성이 높은 관계를 선택한다.
  • 탐색 상태 평가 (Evaluation of Exploration State): 현재 탐색 경로가 쿼리에 얼마나 적합한지 평가하고, 필요시 탐색 계획을 재정립한다.

이 알고리즘의 이해를 돕기 위해 하나의 예시를 통해 과정을 살펴보도록 하겠다. 예시 질문은 “Which former husband of Elizabeth Taylor died in Chichester?”이다. 이 때, 시작 노드(타겟 엔티티)는 “Elizabeth Taylor”이다.

  • Step 1. 타겟 엔티티 “Elizabeth Taylor”에서 시작
    • 선택된 노드: [“Elizabeth Taylor”, “Liz Taylor”]
  • Step 2: 이전 남편 리스트
    • 선택된 관계: [“married to”, “married”, “was married to”]
    • 선택된 노드: [“Michael Wilding”, “Conrad Nicky Hilton Jr”, “Eddie Fisher”]
  • Step 3: 각 남편의 사망 장소 식별
    • 선택된 관계: [“died in”]
    • 선택된 노드: [“hospital near his home in Sussex town of Chichester”, “Chichester, West Sussex”]
  • Step 4: Chichester에서 사망한 남편 식별
    • 최종 경로: (Elizabeth Taylor) - [married] → (Michael Wilding) - [died in] → (Chichester, West Sussex)
    • 생성된 답변: “Michael Wilding”

결론적으로 CoE는 복잡한 질의에 대해 정확한 답변을 제공하기 위해 지식 그래프를 효율적으로 탐색하는 강력한 도구이다. 이 알고리즘은 LLM과 벡터 유사성 검색, 사이퍼 쿼리를 결합하여 높은 정확도와 신뢰성을 유지하면서도 효율적인 검색이 가능하게 한다.


3) Answer Generation

1



Experiments

1. Experiments Setup

1) Setup

  • 벡터 유사도 검색(Vector Similarity Search)을 위해 SentenceTransformer를 사용.
  • M2 Ultra with 128GB of unifired memory
  • Sentence Embedding을 계산하고 저장하는 것은 RedisDB 인스턴스에 저장.
    • Redis는 메모리 내 벡터 데이터베이스로 사용되며, Redis Search 모듈을 통해 데이터베이스에서 관련 데이터를 빠르게 찾기 위해 벡터 유사성 검색 연산을 수행한다.
  • 사용된 LLM은 Azure Cloud에 호스팅되어 있으며, 항상 GPT-4 Turbo 1106-Preview 버전을 사용

Dataset은 KGQA의 벤치마크인 ComplexWebQuestion(CWQ) Dataset을 사용하였다. CWQ 데이터셋은 Multi-hop reasoning, temporal constraints, 그리고 aggregation을 포함하는 복잡한 쿼리로 시스템을 테스트하기 위해 특별히 설계되었다.

2) Evaluation Metric

1

모델을 평가하기 위해서 Exact Match(EM), F1 Score, Accuracy, Hallucination 네 개의 지표를 사용하였다.

  • Exact Match(EM): Ground truth answer가 정확히 일치하는 답변을 출력한 비율
  • F1 Score: Precision과 Recall의 조화평균
    • Precision은 모델이 positive로 판별한 것 중에 실제 positive의 비율이다.
    • Recall은 실제 positive들 중 모델이 positive로 판별한 비율이다.
  • Accuracy늖: Gound truth와 모델이 출력한 정답간에 overlapping되는 비율이다.
  • Hallucination: Ground truth와 완전히 다른 답을 내거나, ‘I don’t know’와 같은 출력을 생성해 낸 비율이다.

2. Main Result

1

모델의 성능이 전반적으로 선행 연구인 Embedding-RAG나 사람이 직접평가하는 Human에 비해 많이 떨어지는 것을 볼 수 있다. 하지만, Hallucination의 비율이 선행 연구에 비해 매우 낮은 수치라는 점에서 contribution이 있다.

3. Analysis

1

LLM과 KG-RAG를 사용했을 때 정답을 정확하게 추론하는 Case study를 보여준다.



Limitiation and Contribution

  • Limitation
    • 아직 연구가 진행 중이고, 아이디어만 선점한 느낌이라 실험이 부족하다.
    • 또한 성능 측면에서도 아직 KG-RAG를 사용해야할 merit가 없다
  • Contribution
    • Hypernode라는 개념을 도입해 복잡한 사실 관계를 하나의 트리플로 표현
    • CoE알고리즘을 통해 Retrieval을 효과적으로 수행하고, hallucination을 일부 완화하였다.

또한 이 논문을 읽으면서 몇 가지 의문점이 생겼다.

  1. Hypernode는 기존의 triple들과 추가적으로 연결되는 노드이기 때문에 KG의 density를 높이게 된다. Multi-hop reasoning을 함에 있어서 과연 이 density가 증가하는 것이 올바른가?
  2. CoE알고리즘을 수행함에 있어 few-short in-context learning의 구조를 띄기 때문에, 하나의 정답을 생성하기 위해서 LLM을 여러 번 호출해야하는데, time cost가 크지 않을까?



Reference

NR 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)