📚 지식 노트

검색 엔진의 흐름

검색 엔진은 질의가 들어온 순간 웹을 뒤지지 않는다. 미리 해 둔 일과 질의 때 하는 일이 나뉜다. 구글의 설명도 같은 세 단계다. 크롤링은 크롤러(봇)가 이미 아는 페이지에서 링크를 따라가며 새 페이지를 내려받는 일이다. 색인은 받은 페이지의 글·제목·링크를 분석해 찾기 좋은 자료 구조로 저장하는 일이다. 마지막으로 질의가 오면 결과를 내보낸다. 질의를 토큰으로 자르고 맞춤법을 고친 뒤(질의 처리), 색인에서 후보를 꺼내 점수를 매겨 줄 세운다(랭킹).

이 구조는 웹 검색만의 것이 아니다. 쇼핑몰 상품 검색, 사내 문서 검색, 코드 검색, 로그 검색(Elasticsearch·OpenSearch)이 모두 "미리 색인, 질의 때 꺼내 점수"라는 같은 뼈대 위에 있다. 크롤링 자리에 데이터베이스 변경 이벤트나 파일 업로드가 들어갈 뿐이다. 색인을 만들고 갱신하는 일이 대량 데이터 처리라는 점은 빅데이터 노트의 일괄·스트림 처리와 이어진다.

역색인: 낱말에서 문서로

문서 목록을 처음부터 끝까지 훑어 "고양이"가 든 문서를 찾으면 문서 수에 비례해 느려진다. 그래서 검색 엔진은 방향을 뒤집은 표, 역색인(inverted index)을 만든다. 책 뒤의 찾아보기처럼 낱말마다 그 낱말이 나오는 문서 번호 목록을 적어 두는 것이다. 이 목록을 포스팅 목록(postings list)이라 한다. 질의 때는 낱말 하나에 목록 하나를 읽으면 되니, 전체 문서 수가 아니라 그 낱말이 든 문서 수만큼만 일한다.

만드는 과정은 단순하다. 문서를 하나씩 읽어 토큰으로 자르고, 토큰마다 목록 끝에 문서 번호를 붙인다. 실제 엔진은 여기에 몇 가지를 더한다. 낱말이 문서에 몇 번 나왔는지(빈도), 어느 위치에 나왔는지(구절 검색용)를 함께 적고, 목록은 번호 차이를 작은 정수로 압축해 저장한다. 한국어는 띄어쓰기 단위로 자르면 "고양이가"와 "고양이를"이 다른 낱말이 되므로, 형태소 분석기로 조사를 떼거나 글자 n-gram으로 잘라 색인한다.

질의 처리: 분석기, 동의어, 오타

역색인은 낱말이 정확히 같아야 찾는다. 그래서 문서를 색인할 때와 질의를 받을 때 같은 분석기(analyzer)로 글을 다듬는다. 토큰으로 자르고, 소문자로 바꾸고, 어간만 남기고(foxes → fox), 동의어를 한 낱말로 모은다. Elasticsearch 문서가 강조하듯 색인과 질의에 같은 토큰화·정규화 규칙을 써야 한다(Text analysis). 문서는 형태소 분석으로 색인했는데 질의는 띄어쓰기로만 자르면 “고양이를”이 영영 안 걸린다. 분석기를 바꾸면 이미 색인한 문서도 다시 색인해야 하는 이유다.

• 동의어: “노트북”과 “랩톱”, 업계 약어처럼 같은 뜻의 다른 낱말을 규칙으로 묶어, 한쪽으로 찾아도 다른 쪽이 든 문서가 나오게 한다(synonyms). 너무 넓게 묶으면 정밀도가 떨어지므로, 실제 검색 기록에서 결과가 0건이었던 질의를 보고 하나씩 더한다.
• 오타: 퍼지 검색은 글자 하나를 바꾸거나 빼거나 넣는 횟수, 곧 편집 거리(레벤슈타인 거리)가 작은 낱말까지 맞춘다(box → fox는 1). Elasticsearch의 fuzziness: AUTO는 길이 0~2인 낱말은 정확히, 3~5는 한 번, 그보다 길면 두 번까지 편집을 허용한다(Fuzzy query). 짧은 낱말에 편집을 허용하면 엉뚱한 낱말이 너무 많이 걸리기 때문이다.

불리언 질의와 포스팅 교집합

가장 오래된 검색 방식은 불리언 질의다. "고양이 AND 가격"은 두 낱말이 모두 든 문서, OR은 하나라도 든 문서, NOT은 빼기다. 역색인 위에서 이것은 포스팅 목록끼리의 집합 연산이 된다. 목록이 문서 번호 순으로 정렬돼 있으니, AND는 두 목록 앞에 포인터를 하나씩 두고 작은 쪽을 한 칸씩 밀며 같은 번호를 줍는 것으로 끝난다. 비교 횟수는 두 목록 길이의 합을 넘지 않는다. 정렬 노트의 병합 정렬에서 두 정렬된 배열을 합치는 것과 같은 걸음이다.

낱말이 여럿이면 가장 짧은 목록부터 교집합하는 것이 요령이다. 결과는 가장 짧은 목록보다 길어질 수 없으니, 이후 비교가 금방 줄어든다. 아주 긴 목록에는 중간중간 건너뛰기 표시(skip pointer)를 두어 한참 앞의 번호로 바로 뛰기도 한다. 다만 불리언 질의는 "든다/안 든다"만 알려 줄 뿐 어느 문서가 더 맞는지는 말하지 않는다. 결과가 수만 개면 순서가 필요하다.

점수 매기기: TF-IDF와 BM25

문서에 점수를 주는 직관은 두 가지다. 질의 낱말이 문서에 자주 나올수록(TF, term frequency), 그리고 그 낱말이 전체 문서 가운데 드물수록(IDF, inverse document frequency) 그 문서가 질의와 맞는다. "고양이"처럼 거의 모든 문서에 있는 낱말은 문서를 가려 주지 못한다. 고전 TF-IDF는 tf × ln(N/df)다. 위 예에서 "고양이"는 문서 4개 중 3개에 있어 IDF가 ln(4/3) ≈ 0.288뿐이고, D1의 점수 0.288에 비해 "고양이"가 두 번 나온 D4는 0.575로 두 배가 된다.

문제는 tf에 그대로 비례한다는 점이다. 낱말을 백 번 반복한 문서가 열 배 좋은 문서는 아니고, 긴 문서는 그저 길어서 낱말이 많다. BM25는 이 둘을 고친다. 점수는 질의 낱말마다 IDF × tf(k1 + 1) / (tf + k1(1 − b + b·|D|/avgdl))을 더한 것이다. tf가 늘어도 이 몫은 k1 + 1을 넘지 못하고 포화된다(평균 길이 문서에서 tf = 1이면 1.00, 2면 1.38, 10이면 1.96). b는 문서 길이 |D|를 평균 길이 avgdl로 나눠 긴 문서의 tf를 깎는 정도다. Elasticsearch는 BM25를 기본 유사도로 쓰고 k1 = 1.2, b = 0.75를 기본값으로 둔다. IDF도 ln((N − n + 0.5)/(n + 0.5) + 1)로 바꿔 흔한 낱말이 음수가 되지 않게 했다. 예에서 "가격"의 IDF는 0.693, "고양이"는 0.357다.

실제 검색은 BM25 하나로 끝나지 않는다. 제목에 나온 낱말에 가중치를 더 주고, 최신성·클릭률·페이지 품질 같은 여러 신호를 묶어 학습된 랭킹 모델(learning to rank)로 다시 줄 세운다. BM25는 그 앞단에서 후보를 빠르게 고르는 역할을 한다. 이 "가볍게 고르고 무겁게 줄 세우기" 구조는 아래 추천 절에서 다시 나온다.

페이지랭크: 링크로 매긴 중요도

질의와 얼마나 맞는지와 별개로 페이지 자체의 중요도도 있다. 1996년 스탠퍼드의 래리 페이지와 세르게이 브린이 만든 페이지랭크는 링크를 추천표로 본다. 많은 페이지가 가리키는 페이지가 중요하고, 중요한 페이지가 가리키면 더 중요하다. 정의가 자기 자신을 부르는 셈인데, 반복해서 풀면 된다. 모든 페이지를 1/N에서 시작해 PR(p) = (1 − d)/N + d · Σ PR(q)/L(q)를 되풀이한다. q는 p를 가리키는 페이지, L(q)는 q가 내보내는 링크 수, d는 보통 0.85 정도로 두는 감쇠 계수다.

해석은 무작위로 웹을 떠도는 사람이다. 그는 확률 d로 지금 페이지의 링크 하나를 골라 따라가고, 1 − d로 아무 페이지로 순간 이동한다. 아주 오래 떠돈 뒤 각 페이지에 머무는 시간의 비율이 페이지랭크다. 나가는 링크가 없는 페이지에 갇히지 않도록 그런 페이지는 모든 페이지로 고르게 나간다고 본다. 이 반복은 링크 행렬의 가장 큰 고윳값에 대응하는 고유벡터를 찾는 거듭제곱법과 같다. 고유벡터 이야기는 선형대수 노트의 고윳값 절에 있다.

링크로 순위가 정해지자 링크를 사고파는 스팸이 생겼고, 지금의 검색 랭킹에서 페이지랭크는 수많은 신호 가운데 하나일 뿐이다. 그래도 "그래프에서 중요한 노드 찾기"라는 문제는 그대로 남아, 소셜 그래프의 영향력 분석이나 인용 네트워크 분석 같은 곳에서 같은 계산이 쓰인다.

벡터 검색과 하이브리드 검색

낱말 일치 검색은 "노트북 화면이 깜빡여요"로 "디스플레이 떨림 해결"을 찾지 못한다. 같은 뜻을 다른 낱말로 썼기 때문이다. 벡터 검색은 문장을 임베딩 모델로 긴 실수 벡터로 바꿔, 뜻이 비슷한 글이 가까운 점이 되게 한다. 질의도 벡터로 바꾼 뒤 코사인 유사도가 높은(가까운) 문서를 찾는다. 문서가 수억 개면 모두와 비교할 수 없어서 HNSW·IVF 같은 근사 최근접 이웃(ANN) 색인을 쓴다. 그 색인의 구조와 pgvector·Qdrant 같은 벡터 DB는 데이터베이스 › 시계열·그래프·벡터에서 다룬다. LLM이 답하기 전에 관련 문서를 이렇게 찾아 붙이는 것이 RAG다.

벡터 검색에도 약점이 있다. 제품 번호 "A-1234"나 사람 이름, 드문 전문 용어처럼 정확히 그 글자를 찾아야 할 때는 BM25가 더 믿을 만하다. 그래서 둘을 함께 돌리는 하이브리드 검색이 흔하다. 문제는 BM25 점수와 코사인 유사도의 단위가 달라 그냥 더할 수 없다는 것이다. 간단하고 튼튼한 방법이 RRF(reciprocal rank fusion)다. 점수 대신 순위만 써서, 목록마다 순위 r인 문서에 1/(k + r)을 더한다. Elasticsearch의 기본 k는 60다. 두 목록 모두에서 위쪽에 있는 문서가 자연히 올라온다.

검색 평가: 정밀도, 재현율, NDCG

랭킹을 바꿨을 때 좋아졌는지 알려면 숫자가 필요하다. 질의마다 사람이 "관련 있다"고 표시한 정답 문서 모음을 두고 결과와 비교한다. 정밀도@k는 상위 k개 가운데 관련 문서의 비율이고, 재현율@k는 관련 문서 전체 가운데 상위 k개에 들어온 비율이다. 결과를 많이 보여 주면 재현율은 오르고 정밀도는 내리기 쉬워 둘은 함께 본다. 이 둘은 분류 모델 평가의 정밀도·재현율과 같은 정의다.

둘 다 순서를 보지 않는다는 약점이 있다. 사용자는 위쪽만 보므로 1위에 좋은 문서가 있는 편이 5위에 있는 것보다 낫다. DCG는 관련 등급(예: 0~3)을 순위가 내려갈수록 1/log₂(i + 1)로 깎아 더한다. 이를 가장 이상적인 순서로 줄 세웠을 때의 DCG(IDCG)로 나눈 것이 NDCG로, 0~1 사이라 질의끼리 평균 내기 좋다. 이 할인 공식은 Järvelin과 Kekäläinen의 2002년 논문에서 널리 퍼졌다. 이렇게 미리 만든 정답으로 재는 것이 오프라인 평가이고, 실제 사용자 반응으로 재는 온라인 평가는 맨 아래 절에서 다룬다.

추천: 콘텐츠 기반과 협업 필터링

추천은 질의 없는 검색이다. 질의 대신 사용자의 과거 행동(본 것, 산 것, 누른 것, 별점)이 단서다. 접근은 크게 둘이다. 콘텐츠 기반 추천은 아이템의 특징(장르, 감독, 글의 낱말, 이미지 임베딩)으로 사용자가 좋아한 것과 비슷한 아이템을 고른다. 새 아이템도 특징만 있으면 바로 추천할 수 있지만, 사용자가 이미 아는 취향 밖으로는 잘 나가지 못한다.

단서는 두 종류다. 사용자가 직접 매긴 별점 같은 명시적 피드백과, 보거나 끝까지 듣거나 산 것에서 관심을 짐작하는 암묵적 피드백이다(Google 추천 강의). 별점은 드물게 쌓이고 암묵적 기록은 훨씬 많지만, 누르지 않은 것이 싫어서인지 못 봐서인지는 알 수 없다. 클릭에는 순위 편향도 섞인다. 요아킴스 등이 2005년 SIGIR에서 시선 추적으로 살핀 연구는 사용자가 더 관련 있는 요약을 보고도 위쪽에 놓인 링크를 더 누르는 신뢰 편향을 보였다. 클릭을 절대적인 정답으로 쓰면 지난번 순위를 다시 배우게 되고, 같은 연구는 클릭에서 뽑은 상대적 선호(위의 것을 건너뛰고 아래 것을 눌렀다)가 더 믿을 만하다고 결론 내렸다.

협업 필터링은 아이템의 내용을 보지 않는다. 사용자–아이템 행렬에서 "나와 비슷하게 평가한 사람들이 좋아한 것"을 고른다. 사람마다 평점 벡터를 만들고 코사인 유사도로 이웃을 찾은 뒤, 내가 안 본 아이템에 이웃들의 평점을 유사도로 가중 평균한다. 아래 예에서 지우는 액션을 좋아하는 민준과 유사도 0.75, 로맨스를 좋아하는 하준과 0.19이라, 지우가 아직 안 본 액션3의 예측은 4.0점이 된다. 사람 대신 아이템끼리 유사도를 구하는 아이템 기반 방식도 있다. 아이템은 사람보다 취향이 덜 바뀌어 미리 계산해 두기 좋다.

행렬 분해: 숨은 요인으로 빈칸 채우기

이웃 방식은 사용자·아이템이 수억이면 유사도 계산이 버겁고, 겹치게 본 아이템이 적으면 유사도 자체가 불안하다. 행렬 분해는 평점 행렬 R을 두 개의 얇은 행렬의 곱 U·Vᵀ로 근사한다. 사용자마다, 아이템마다 짧은 벡터(잠재 요인)가 하나씩 생기고, 예측 평점은 두 벡터의 내적이다. 요인에 이름이 붙어 있지는 않지만 학습해 보면 "액션 성향", "가벼운 분위기" 같은 축이 저절로 생기곤 한다.

학습은 관측된 칸에서만 (실제 평점 − 내적)²을 줄이도록 U와 V를 고치는 것이다. 확률적 경사 하강법이나 U·V를 번갈아 푸는 교대 최소제곱(ALS)을 쓰고, 요인을 너무 많이 두면 관측값을 외워 버리므로 벡터 크기에 벌점(정규화)을 준다. 넷플릭스 프라이즈 때 사이먼 펑크가 2006년 블로그에 쓴 방식으로 널리 알려졌다. 이름에 SVD가 붙곤 하지만 실제로 특잇값 분해를 하는 것은 아니다. 요즘은 내적 대신 신경망을 쓰기도 하지만, "사용자와 아이템을 같은 공간의 벡터로 놓고 가까움으로 고른다"는 생각은 그대로다. 위 벡터 검색과 같은 색인으로 후보를 찾을 수 있는 이유다.

콜드 스타트

협업 필터링과 행렬 분해는 기록이 있어야 돈다. 막 가입한 사용자에게는 이웃도 요인 벡터도 없고, 막 올라온 아이템은 아무도 평가하지 않았다. 이것이 콜드 스타트 문제다. 정답이 하나인 문제가 아니라, 기록이 쌓일 때까지 쓸 다리를 놓는 문제다.

새 사용자에게는 인기·최신 목록을 보여 주거나, 가입할 때 좋아하는 장르 몇 개를 고르게 하거나, 시간대·지역·기기 같은 맥락을 쓴다. 새 아이템은 콘텐츠 기반 방식이 맡는다. 제목·설명·이미지를 임베딩으로 바꾸면 평점이 없어도 비슷한 아이템 옆에 놓을 수 있다. 일부 사용자에게 일부러 노출해 반응을 모으는 탐색도 필요하다. 늘 지금 가장 좋아 보이는 것만 보여 주면(활용) 새것은 영영 기록을 얻지 못한다. 탐색과 활용의 균형은 멀티암드 밴딧 문제로 다룬다.

후보 생성과 랭킹: 2단계 구조

아이템이 수백만 개인데 사용자마다 모두에 무거운 모델을 돌릴 수는 없다. 그래서 대규모 추천은 단계를 나눈다. 후보 생성은 싸고 빠른 방법 여러 갈래(협업 필터링 벡터의 최근접 이웃, 방금 본 것과 비슷한 아이템, 인기·최신)로 전체에서 작은 후보 묶음을 고른다. 랭킹은 그 후보에만 사용자·아이템·맥락 특징을 많이 넣은 모델을 돌려 클릭·시청·구매 확률을 예측해 줄 세운다. 마지막 재정렬에서 비슷한 것끼리 몰리지 않게 섞고, 이미 산 것을 빼고, 정책·광고 자리를 채운다. 구글의 추천 강의도 이 세 부품으로 설명하고, 2016년 유튜브 논문은 후보 생성 신경망과 랭킹 신경망을 따로 둔 구조를 보여 줬다.

이렇게 나누면 각 단계가 다른 목표를 가질 수 있다. 후보 생성은 좋은 것을 빠뜨리지 않는 재현율이, 랭킹은 위쪽의 정확도가 중요하다. 검색도 마찬가지로 BM25·벡터 색인이 후보를, 학습된 랭킹 모델이 순서를 맡는다. 특징을 미리 계산해 두고 빠르게 꺼내는 일(피처 스토어)과 행동 로그를 모아 모델을 다시 학습하는 파이프라인은 빅데이터 노트의 영역이다.

필터 버블과 다양성

클릭 확률만 최대로 하는 추천은 사용자가 이미 좋아하는 것과 비슷한 것만 계속 보여 준다. 보여 준 것만 클릭되니 그 기록이 다시 학습에 들어가 좁아짐이 스스로 강해진다. 이런 피드백 고리와 그 결과로 시야가 좁아지는 현상을 흔히 필터 버블이라 부른다. 인기 있는 것이 더 많이 노출돼 더 인기 있어지는 인기 편향도 같은 고리에서 나온다. 사용자에게는 금방 질리는 목록이, 새 창작자에게는 기회가 없는 시장이 된다.

그래서 정확도 말고도 지표를 함께 본다. 다양성(목록 안 아이템이 서로 얼마나 다른가), 새로움(사용자가 몰랐을 법한가), 뜻밖의 발견(serendipity), 노출이 창작자들에게 얼마나 고르게 가는가(공정성) 같은 것이다. 재정렬 단계에서 이미 고른 것과 비슷한 아이템의 점수를 깎아 가며 고르는 방법(MMR 등)이 흔하다. 정확도를 조금 내주고 오래 쓰는 만족을 사는 거래다.

온라인 평가: A/B 시험

오프라인 지표(NDCG, 예측 오차)가 좋아졌다고 사용자가 더 만족하는 것은 아니다. 과거 로그는 옛 모델이 보여 준 것에 대한 반응뿐이라, 새 모델이 고른 아이템에 대한 반응은 없다. 그래서 마지막 판단은 A/B 시험으로 한다. 사용자를 무작위로 나눠 한쪽은 기존 모델(A), 다른 쪽은 새 모델(B)을 보게 하고 클릭률·체류 시간·재방문 같은 지표를 비교한다.

차이가 우연인지는 통계 검정으로 본다. 아래 예는 노출 10,000번씩에서 클릭 400번과 460번이다. 두 비율 z 검정으로 z ≈ 2.09, 양측 p ≈ 0.036이 나온다. p값의 뜻과 흔한 오해는 확률과 통계 노트에 있다. 실무의 함정은 숫자보다 절차에 있다. 결과를 보다가 좋을 때 멈추면 우연한 차이를 잡기 쉬우니 기간과 지표를 미리 정하고, 클릭률만 올리는 자극적인 추천이 장기 만족을 깎지 않는지 보조 지표로 지킨다. 여러 모델의 결과를 한 목록에 섞어 어느 쪽이 더 클릭되는지 보는 인터리빙은 A/B보다 적은 트래픽으로 순위 차이를 잡는다.

핵심 자료

문서를 벡터로 바꾸는 임베딩과 LLM 쪽 이야기는 LLM 노트, 로그를 모아 지표를 내는 쪽은 빅데이터 노트에 있다.