랭킹

랭킹은 검색에 걸린 문서 가운데 무엇을 먼저 보여 줄지 정하는 일입니다. 문서마다 검색어와 잘 맞는 정도를 점수로 매겨 높은 순으로 줄 세웁니다. 사람은 맨 위 몇 개만 보므로 이 순서가 검색의 쓸모를 가릅니다. 추천 목록이나 점수판을 줄 세우는 일도 같은 이름으로 부릅니다.

상세

서점 직원에게 「초보가 읽을 파이썬 책」을 물었다고 해 봅니다. 서가에는 파이썬 책이 수십 권 꽂혀 있습니다. 직원은 그중 가장 알맞아 보이는 책부터 차례로 몇 권을 골라 내밉니다.

랭킹은 직원이 무엇을 먼저 내밀지 정하는 일에 해당합니다. 이 절은 검색 결과가 줄을 서는 과정을 골라내기부터 순위 평가까지 따라갑니다.

골라내기와 줄 세우기

검색은 두 가지 일로 나뉩니다. 첫째는 검색어에 맞는 문서를 골라내는 일입니다. 둘째는 골라낸 문서의 순서를 정하는 일입니다. 랭킹은 둘째 일입니다.

사용자가 검색창에 넣은 말이 질의입니다. 골라내기는 질의의 낱말이 든 문서를 찾는 일입니다.

검색 엔진은 이 일을 빠르게 하려고 목록을 미리 만들어 둡니다. 낱말마다 그 낱말이 든 문서 번호를 적은 목록입니다. 이 목록이 역색인입니다.

골라내기만으로는 끝나지 않습니다. 「커넥션 풀」로 찾으면 두 낱말이 든 문서가 수천 개 걸릴 수 있습니다. 골라내기는 어느 문서가 걸렸는지만 알려 줍니다. 무엇이 먼저인지는 말하지 않습니다.

순서가 검색의 쓸모를 가르는 까닭

사람은 검색 결과의 첫 화면만 보는 일이 많습니다. 다음 쪽으로 넘기는 사람은 적습니다. 몇 쪽씩 넘기는 사람은 더 적습니다.

그래서 찾던 문서가 걸렸어도 800번째에 있으면 못 찾은 것과 같습니다. 반대로 걸린 문서가 적어도 맨 위가 맞으면 사람은 원하는 것을 얻습니다. 검색의 쓸모는 얼마나 많이 찾았나보다 무엇을 위에 놓았나에서 갈립니다.

점수를 매겨 줄 세우기

랭킹은 대개 점수로 순서를 정합니다. 질의 하나와 문서 하나를 받아 수 하나를 돌려주는 함수를 둡니다. 이 함수가 점수 함수입니다.

점수 함수가 돌려준 수를 관련도라고 합니다. 관련도는 문서가 질의와 얼마나 잘 맞는지를 나타낸 점수입니다. 값이 클수록 잘 맞는다는 뜻입니다.

골라낸 문서마다 관련도를 구한 뒤 큰 순으로 줄 세웁니다. 이때 전부를 줄 세울 필요는 없습니다. 첫 화면에 보일 몇 개만 있으면 됩니다.

점수가 가장 높은 몇 개만 뽑아냅니다. 뽑을 개수는 k 로 적습니다. 위에서 k 개만 고르는 일이 상위 k 선택입니다. 수천 개를 다 줄 세우는 것보다 계산이 적게 듭니다.

ORDER BY 와 다른 점

백엔드 개발자에게 줄 세우기는 익숙한 일입니다. SQL(Structured Query Language)의 ORDER BY 는 테이블에 저장된 열을 기준으로 행을 줄 세웁니다. 작성일 순이나 가격 순이 그렇습니다.

랭킹의 기준은 저장된 값이 아닙니다. 관련도는 질의가 들어온 뒤에 계산합니다. 같은 문서도 「커넥션 풀」로 찾을 때와 「스레드 풀」로 찾을 때 점수가 다릅니다.

랭킹의 어려운 부분은 줄 세우기가 아닙니다. 점수 함수를 짓는 쪽이 어렵습니다. 점수를 다 구한 뒤의 줄 세우기는 평범한 정렬입니다.

관련도 랭킹이 필요 없는 조회도 많습니다. 주문 번호로 주문 하나를 찾는 조회는 답이 하나라 순서가 없습니다. 사용자가 가격 낮은 순을 고르면 관련도 대신 가격으로 줄 세웁니다. 랭킹은 걸린 결과가 많고 사용자가 순서를 정하지 않았을 때 씁니다.

낱말 수만 세는 점수 함수

점수 함수를 가장 단순하게 지어 봅니다. 문서에 질의 낱말이 몇 번 나오는지 세어 더한 값을 점수로 씁니다. 아래 코드가 문서 셋에 이 점수를 매깁니다.

docs = {
    "A": "커넥션 풀 크기 설정",
    "B": "스레드 풀 설정",
    "C": "커넥션 풀 커넥션 커넥션 누수",
}
query = ["커넥션", "풀", "설정"]

def score(text):
    words = text.split()
    return sum(words.count(q) for q in query)

def key(d):
    return -score(docs[d])

score(docs["A"])  # 3
score(docs["B"])  # 2
score(docs["C"])  # 4
sorted(docs, key=key)  # ['C', 'A', 'B']

score 는 질의 낱말마다 문서 안에서 나온 횟수를 세어 더합니다. key 는 점수에 마이너스를 붙여 큰 점수가 앞에 오게 합니다. 결과는 C 가 맨 위입니다.

그런데 C 는 커넥션 누수 이야기입니다. 설정을 찾던 사람에게는 A 가 더 알맞습니다. C 가 이긴 것은 「커넥션」을 세 번 되풀이했기 때문입니다.

문제는 둘 더 있습니다. 「풀」은 세 문서에 다 나옵니다. 문서를 가르는 데 쓸모가 없는데도 똑같이 1점을 줍니다. 그리고 긴 문서는 낱말이 많아서 질의 낱말에 우연히 더 많이 걸립니다.

이 세 문제를 다듬은 점수 함수가 있습니다. TF-IDF(Term Frequency-Inverse Document Frequency)는 낱말이 문서에 나온 횟수에 값 하나를 곱합니다. 그 낱말이 든 문서가 적을수록 커지는 값입니다. 「풀」처럼 세 문서에 다 나오는 낱말은 점수를 거의 올리지 못합니다.

BM25(Best Matching 25)도 여러 문서에 흔한 낱말의 무게를 낮춥니다. 여기에 더해 같은 낱말이 되풀이될수록 점수가 덜 오르게 합니다. 긴 문서의 점수도 깎습니다.

점수에 넣는 신호

점수 함수가 보는 재료를 신호라고 부릅니다. 앞 절의 세 문제는 전부 낱말을 세는 신호에서 나왔습니다. 검색 엔진은 글 밖의 신호도 함께 씁니다. 아래 표가 그런 신호 여섯을 보입니다.

낱말 빈도와 낱말의 드묾은 질의가 들어와야 셀 수 있습니다. 문서 길이와 가리키는 링크와 최신성은 질의와 상관없이 문서마다 미리 정해 둘 수 있습니다. 사용자 반응은 질의마다 따로 쌓아 둔 기록이라 질의가 들어오면 꺼내 씁니다. 다른 문서가 가리키는 링크를 점수로 바꾼 계산 방식이 PageRank입니다.

신호가 여럿이면 하나로 합쳐야 줄을 세울 수 있습니다. 흔한 방법은 신호마다 가중치를 곱해 더하는 것입니다. 가중치를 얼마로 둘지가 다음 문제가 됩니다.

가중치를 기록에서 배우기

신호가 몇 개뿐이면 사람이 가중치를 정합니다. 결과를 보며 조금씩 고칩니다. 신호가 수십 개로 늘면 손으로 맞추기 어렵습니다.

그래서 가중치를 데이터에서 배우게 하기도 합니다. 재료는 「이 질의에는 이 문서가 맞았다」는 기록입니다. 사람이 매긴 정답표나 클릭 기록이 그런 기록입니다. 순위 매기는 법을 이렇게 머신러닝으로 배우는 방식을 Learning to Rank라고 부릅니다.

대가는 설명하기 어려워진다는 것입니다. 사람이 가중치를 정했다면 어느 신호가 이 문서를 올렸는지 되짚을 수 있습니다. 배운 가중치가 많아지면 왜 이 순서가 나왔는지 따라가기 힘듭니다.

줄 세우기를 두 번 하는 구조

신호가 많을수록 문서 하나의 점수를 구하는 비용이 커집니다. 골라낸 문서 수천 개에 계산이 비싼 점수 함수를 다 돌리면 응답이 늦어집니다.

그래서 줄 세우기를 두 번 합니다. 먼저 계산이 싼 점수 함수로 후보 전체를 줄 세워 위쪽 일부만 남깁니다. 그다음 남은 문서에만 계산이 비싼 점수 함수를 돌려 다시 줄 세웁니다. 두 번째 줄 세우기를 재순위화라고 부릅니다.

flowchart TD
    A["모든 문서"] --> B["골라내기 · 질의 낱말이 든 문서만"]
    B --> C["첫 줄 세우기 · 계산이 싼 점수 함수"]
    C --> D["위쪽 일부만 남긴다"]
    D --> E["재순위화 · 계산이 비싼 점수 함수"]
    E --> F["맨 위 k 개를 돌려준다"]

아래로 내려갈수록 다루는 문서가 줄어듭니다. 비싼 계산은 문서가 가장 적은 단계에서만 합니다. 싼 쪽은 BM25 같은 낱말 점수가 흔히 맡습니다. 비싼 쪽은 앞 절의 배운 가중치가 맡습니다.

순위를 잘 매겼는지 재는 법

점수 함수를 고쳤으면 순위가 나아졌는지 재야 합니다. 재료는 질의마다 어느 문서가 맞는지 적어 둔 정답표입니다.

가장 쉬운 지표는 맨 위 k 개 가운데 맞는 문서가 몇 개인지 보는 것입니다. 맨 위 10개 중 맞는 문서가 7개면 0.7 입니다. 이 값이 위 k 개의 정밀도입니다.

정밀도는 위 k 개 안의 순서를 보지 않습니다. 맞는 문서가 1위에 있든 10위에 있든 같은 값입니다. 순서까지 따지려면 위쪽 순위에 더 큰 무게를 주는 지표를 씁니다. NDCG(Normalized Discounted Cumulative Gain)가 그런 지표입니다.

검색 밖에서 쓰는 랭킹

랭킹이라는 말은 검색 밖에서도 씁니다. 줄을 세운다는 뜻은 같습니다. 점수가 어디서 오는지가 다릅니다.

추천 시스템의 랭킹은 질의 대신 사용자를 넣은 검색 랭킹과 같은 꼴입니다. 줄 세우기를 두 번 하는 구조도 함께 씁니다.

점수판 순위는 점수를 새로 계산하지 않습니다. 저장된 값으로 줄만 세우므로 앞에서 본 ORDER BY 와 같은 일입니다.

관련 항목

랭킹이 점수를 매기는 계산 방식

관련도 · 관련도 점수 · TF-IDF · BM25 · 벡터 공간 모델 · 확률적 관련성 모델 · PageRank · Learning to Rank · 순위 모델

랭킹 앞뒤에 서는 검색 처리 단계

질의 · 분석기 · 토큰화 · 역색인 · 상위 k 선택 · 재순위화

랭킹을 안에 품은 검색 시스템

검색 엔진 · 전문 검색 · Apache Lucene · Elasticsearch · OpenSearch · Apache Solr

랭킹의 품질을 재는 지표

정밀도 · 재현율 · 정밀도와 재현율 · NDCG · MRR · 클릭률

랭킹이 속하는 상위 분류

정보 검색 · 검색 · 추천 시스템 · 머신러닝

랭킹과 헷갈리는 이웃

정렬 · ORDER BY · 리더보드 · 필터링