검색 엔진의 발전 과정

0. 개요
 
검색 기술이 어떤 식으로 변화해왔는지에 대한 전반적인 흐름을 알아본다.
 
Google과 같은 검색 엔진을 생각해보자. "DB Vector"라는 검색어를 입력했다. 이는 "DB Vector"라는 쿼리를 검색 엔진에 날렸다는 것과 동일한 표현이다. Google에는 수천만개의 페이지가 있는데, 여기서 "DB Vector"와 관련있는 페이지를 어떻게 뽑아낼 수 있을까? "DB", "Vector"가 등장하는 페이지를 모두 다 가져올 것인가? 일차적으로 드는 생각은, "DB"와 "Vector"라는 단어가 많이 있는 것을 먼저 가져올 것 같다. 각 단어가 등장하는 비율이 다를 때는 또 어떤 페이지를 뽑아야할까? 모든 페이지를 가져오는 것이 아니라, 최대한 사용자가 원하는 것을 가져오는 것이 중요하다. 검색 엔진이 어떻게 발전해왔고, 현재는 어떤 기술이 사용되고 있는지 벡터디비의 간단한 개념까지 알아보고자 한다.
 
 
 
 
1. 디렉토리 기반 검색
 
Yahoo 검색 엔진을 사용해보았는가? 사실 나는 사용해본 적이 없다.
Yahoo는 모든 정보를 폴더 단위로 구성한다. 토픽별로 폴더를 구성하고 있는 것이다. 사람들이 토픽을 직접 모아 정리하고 있다고 한다. 예를 들어, 스포츠에 관한 정보를 알고 싶다고 하면, 나는 스포츠 페이지로 들어가서 정보를 찾아야 한다.
이는 "검색"이라기보다는 내가 필요한 정보의 폴더를 "직접 찾아들어가는" 구조이다.
 
 
 
 
2. 희소 벡터 기반 (= 전통 검색 엔진)
 
Google을 생각해보자. 구글은 유명한 검색 엔진이다. Yahoo처럼 직접 정보를 찾아 들어갈 필요가 없이, 키워드 검색을 하면 관련된 페이지를 정렬해서 보여준다. 개요에서 언급했듯이, 구글은 어떻게 수천만개의 페이지에서 사용자가 검색한 키워드와 관련있는 페이지를 적절하게 찾아서 제공하는 것일까?
 
아이디어는 다음과 같다.
"DB Vector"라고 검색을 했다고 하자. (= "DB Vector" 쿼리 날린 것)
방금 날린 쿼리문에 대해서 "DB", "Vector"의 빈도수를 매겨본다. → 쿼리 벡터
모든 문서(page)에 대해서도 "DB", "Vector"의 빈도수를 매겨본다. → 문서 벡터
이렇게 빈도수로 생성된 쿼리 벡터와 문서 벡터 사이의 유사도를 계산하여, 가장 유사한 문서를 반환한다.
이 벡터를 좌표평면에 찍는다면, 방향과 거리의 차이의 관점에서 유사도를 계산할 수 있게 된다. 이 예시에서는 DB, Vector 2개의 키워드라서 2차원 벡터가 될 것이다.
 
유사도를 가장 쉬운 유클리디안 거리로 계산했다고 하자. 이때 발생할 수 있는 문제가 있다.
만약 두 벡터가 같은 방향을 가리키고 있는데도 불구하고 화살표 길이의 차이 때문에 유클리디안 거리가 크게 나왔다면, 이는 올바른 유사도가 계산된 것이 아니다. 내용이 비슷하여 같은 방향을 가리키지만, 빈도수의 차이로 거리가 크게 나오게 된다.이를 해결하기 위해서는 코사인 유사도를 사용하면 된다.
 
이렇게 Google 초기 검색 엔진의 원리를 한문장으로 요약하자면, Bow내에서 내가 원하는 것을 찾는 방법으로 빈도수 벡터의 코사인 유사도 값을 기반으로 한 검색 기법이다.
 
 
 
 
3. PageRank = 전통 검색 엔진의 품질 개선
 
희소 벡터 기반의 전통적인 검색 엔진으로는 관련된 문서가 너무 많이 매칭된다. 가장 관련성이 높은 문서를 앞쪽에 배치해야 사용자의 만족도가 올라간다. 따라서, "품질"을 반영한 문서 랭킹이 필요해졌고, PageRank라는 링크 기반 신뢰도 점수를 만들어 해결했다.
 
링크의 개념은 투표(Vote)로 이해하면 편하다. 어떤 페이지가 다른 페이지에 의해 많이 링크 된다면 그 페이지는 중요하다고 판단되어 랭크가 올라간다. 예를 들어, A페이지가 100개의 페이지로부터 링크되면, A의 중요도는 높고, PageRank는 올라간다. B페이지는 2개의 페이지로부터 링크가 되었다면, B의 중요도는 낮고, PageRank는 낮아진다. 사람들이 클릭하는 것 또한 링크를 거는 효과를 낸다.
 
따라서 이 PageRank 방법을 사용하게 한다면 인위적으로 품질 관리를 할 필요 없이, 사람들이 많이 클릭하는 페이지가 자연스럽게 순위가 올라가면서 품질 관리가 되는 것이다. 최적화 작업을 사용자들이 알아서 해준다.
 
 
4. 대규모 문서 분산 처리 시스템
 
이제 Google의 웹 페이지가 너무 커지기 시작했다. 초기 검색 엔진으로 검색을 진행한다면, 수억~수십억 개의 웹 페이지를 모두 크롤링해서 각 페이지의 단어를 세고 역색인을 만들고 PageRank를 계산해야 한다. 이는 너무나 많은 계산을 요구하여 서버 한대로는 불가능하다.
 
그렇다면 여러 서버가 분산적으로 처리하면 어떨까?
 
4.1 MapReduce
 
MapReduce는 대규모 데이터를 여러 서버에 나눠 병렬로 처리하고 결과를 다시 합치는 분산 처리 모델이다. 간단한 예시가 있다.
1) Map 단계 : 문제를 잘게 나눠서 여러 서버가 나눠 처리한다.

서버 1 → 문서 1~100만 처리 → (DB, 120,000)
서버 2 → 문서 100만~200만 → (DB, 98,314)
서버 1000 → 문서 9억~10억 → (DB, 124,082)

 
2) Reduce 단계 : 나눠 처리된 결과를 다시 하나로 합친다.

(DB, 120000 + 98314 + ... + 124082)

 
4.2 Hadoop = MapReduce를 오픈소스로 구현한 시스템
 
MapReduce는 구글의 내부 기술로, 소스코드를 공개하지 않았다. 따라서 Hadoop은 MapReduce를 오픈소스로 재현한 프로젝트이다.
구글의 Google File System은 Hadoop Distributed File System으로, MapReduce는 Hadoop MapReduce 엔진으로 구현했다.
 
4.3 Spark = Hadoop MapReduce 보다 100배 빠른 최신 분산 처리 시스템
 
Spark는 메모리 기반 처리로 속도 향상을 도모하였다. 지금은 대부분 Spark를 사용하고 다고 보면 된다.
 
 
 
 
5. Word2vec = Dense Vector 등장
 
지금까지는 알아본 방식은 모두 희소 벡터(BoW, TF-IDF)를 기반으로 하였다. 희소 벡터는 단어의 빈도수로만 문서를 표현하는 방식이다. 이러한 방식은 크게 2가지 문제점을 가진다. 첫째는 단어의 임베딩이 매우 sparse하다는 점이다. 두번째는 단어 사이의 의미 관계를 담지 못한다는 점이다.
 
그래서 word2vec이 등장하였다. 단어의 의미를 벡터로 표현하고자 하는 시도이다. word2vec은 단어를 밀집 벡터로 만들고, 주변 단어(문맥)으로부터 의미를 학습할 수 있다. 예를 들어, "보르도"라는 단어 주변에 "위치, 프랑스, 도시" 라는 단어가 자주 나온다면 보르도는 "도시"이다. 반면, "향, 품종, 와인"이 많이 나온다면 보르도는 "와인"이다.
skip-gram 방식은 중심 단어를 통해서 주변 단어를 예측하는 것이다. NN은 보르도에 가장 어울리는 주변 단어 분포를 만들어내도록 학습되며, 그 결과 보르도의 의미를 포함하는 latent vector가 생성된다.
 
 
 
 
6. Attention → Transformer → LLM → RAG
 
word2vec는 주변 단어의 의미를 고려한다. 그럼에도 Word2vec의 한계는 존재한다.
"보르도 날씨가 좋네" 라는 문장이 있다. 여기서 "보르도"와 "날씨"는 단지 문장에서 같이 등장했을 뿐, 둘이 의미적으로 강하게 연결되어 있지는 않다. Word2vec은 단어 간의 관계가 어떤지는 파악하지 못한다는 것이다.
 
6.1 Attention
 
Attention Mechanism을 도입하자. 상관성을 attention이라고 한다. "보르도는 프랑스 남서부에 있는 도시이다." 이 문장에서 "보르도"의 진짜 중요한 단어는 "프랑스, 남서부, 도시"이지 "날씨"같은 단어가 아니다. Attention은 이러한 단어 간의 관계(연관성)을 학습한다.
 
6.2 Transformer
 
Transformer는 Attention을 기반으로 한 아키텍처이다.
word2vec보다 훨씬 발전된 구조로, 문장 전체를 한번에 보고, 모든 단어 쌍의 관계를 계산하고, 문맥을 더 정확하게 이해한다.
LLM이 모두 Transformer 기반인 이유가 여기에 있다.
 
6.3 RAG
 
RAG(Retrieval-Augmented Generation)의 정의를 먼저 알아보자.
1) Retrieval = 검색, 찾아오기, 불러오기
외부 데이터베이스(벡터DB)에서 필요한 문서를 가져온다.
2) Augmented = 증강된, 강화된
검색해서 가져온 정보를 LLM 답변 생성에 더한다.
3) Generation = 생성
LLM이 답변을 만든다.
 
RAG는 모델 바깥에서 작동하는 구조이다.
벡터디비에서 쿼리와 유사한 문서를 검색한 후, 검색된 문서를 LLM에 넣어 답변을 생성한다. 즉, LLM을 크게 바꾸지 않고 벡터DB로 외부 지식을 실시간으로 공급하는 시스템이다.
 
 
 
7. 추가적인 내용
 
7.1 DBSCAN
 
Density-Based Spatial Clustering of Applications with Noise
DBSCAN은 밀도 기반 군집화 알고리즘이다. 데이터가 촘촘히 모여있는 밀도 높은 부분을 자동으로 찾아서 클러스터링하는 방법이다. 클러스터 개수를 미리 지정할 필요가 없으며, 밀도가 낮은 곳(노이즈, outlier)은 자동으로 버린다.
임베딩 벡터를 만들면 비슷한 문장 벡터끼리 군집화가 가능하며, 서로 떨어진 문장들은 noise로 거를 수가 있게 된다.
 
7.2 양자화(Quantization)
벡터가 길어지면 양자화를 해야 한다. 여기서 양자화는 벡터의 각 숫자를 더 적은 비트로 압축하는 기술이다. 벡터 차원이 크면 메모리와 검색 속도에 비용이 많이 들기 때문에, 벡터를 압축해야 할 필요가 있다.