Okapi

Okapi 는 검색어를 받아 잘 맞는 글부터 줄 세워 보여 주던 연구용 검색 시스템입니다. 영국 런던의 대학에서 책과 논문을 찾는 용도로 만들었습니다. 오늘날 검색 엔진이 널리 쓰는 점수 공식 BM25(Best Match 25)가 이 시스템에서 나왔습니다. 그래서 둘을 붙여 흔히 「Okapi BM25」라고 씁니다.

쉽고 빠른 이해

무슨 일을 하던 물건인가. 낱말 몇 개를 받아 잘 맞는 글부터 차례로 보여 주던 검색 시스템입니다. 「고양이 사료 추천」을 치면 세 낱말이 다 든 책이 맨 위, 두 낱말만 든 책이 그 아래에 옵니다.

왜 이렇게 했나. 예전 도서관 검색은 조건에 맞는 책만 보여 주고 순서를 따지지 않았습니다. 조건을 조금만 빡빡하게 걸어도 결과가 0건이 됐습니다. 잘 맞는 순으로 늘어놓으면 이용자가 조건을 궁리하지 않아도 됩니다.

어떻게 돌았나.

1. 검색어의 낱말마다 무게를 매깁니다. 드문 낱말일수록 무겁습니다
2. 글마다 든 낱말의 무게를 더해 점수를 내고 높은 순으로 보여 줍니다
3. 이용자가 맞는 글을 고르면 그 글의 낱말로 검색어를 보태 다시 찾습니다

대가. 「세 낱말이 꼭 다 들어야 한다」 같은 조건은 걸 수 없습니다. 덜 맞는 책이 늘 뒤에 섞여 나옵니다.

지금은. 이 시스템을 설치해 쓰지는 않습니다. 여기서 다듬은 BM25 가 검색 제품 안에 들어가 쓰입니다. Lucene 과 Elasticsearch 도 기본 점수 공식으로 BM25 를 씁니다.

상세

이 절은 Okapi 가 무엇을 하려고 만든 시스템인지, 그 안에서 무엇을 시험했는지 봅니다. 도서관 이용자가 「고양이 사료 추천」으로 책을 찾는 장면 하나를 가지고 따라갑니다.

백엔드 개발자는 이 이름을 대개 BM25 라는 점수 공식과 붙은 「Okapi BM25」로 만납니다.

책과 논문을 찾던 시스템

Okapi 는 연구용 정보 검색 시스템입니다. 정보 검색은 글 더미에서 사람이 찾는 글을 골라 주는 일입니다. 웹 검색도, 쇼핑몰의 상품 검색도 이 일입니다.

처음에는 도서관 목록처럼 책과 논문의 서지 정보를 찾는 시스템이었습니다. 서지 정보는 제목 · 저자 · 주제어처럼 책 한 권을 가리키는 기록입니다. 검색 전문가가 아닌 이용자가 도서관 컴퓨터 앞에서 낱말만 쳐서 찾도록 만들었습니다. 대학 도서관의 책 목록과 과학 논문 초록 모음이 검색 대상이었습니다.

Okapi 는 1980년대부터 1990년대까지 런던의 City University 에서 검색 실험의 시험대로 쓰였습니다. 검색 공식을 연구하던 Stephen Robertson 이 이 실험을 함께 꾸렸습니다.

이름은 동물 오카피와 철자가 같습니다. 검색 분야에서 Okapi 라고 하면 이 시스템을 가리킵니다. 왜 이 이름을 붙였는지는 확인하지 못했습니다(미확인).

불리언 검색 대신 best match

Okapi 가 나올 무렵 도서관 검색은 대개 불리언 검색을 썼습니다. 불리언 검색은 낱말을 AND · OR 같은 조건으로 묶어 그 조건에 맞는 글만 골라 줍니다. 결과는 맞는 글과 안 맞는 글로 갈립니다. 맞는 글끼리는 순서가 없습니다.

이 방식은 이용자에게 조건을 짜는 일을 떠넘깁니다. 「고양이 AND 사료 AND 추천」으로 찾으면 세 낱말이 다 든 책만 나옵니다. 두 낱말만 든 책은 찾던 책이어도 빠집니다. 조건을 OR 로 풀면 이번에는 책이 너무 많이 쏟아집니다. 어느 것부터 볼지 알 수 없습니다.

Okapi 는 다른 길을 골랐습니다. 검색어를 조건이 아니라 낱말 몇 개로 받습니다. 그리고 잘 맞아 보이는 글부터 순서대로 늘어놓습니다. 이 방식을 best match 검색이라고 부릅니다. 가장 잘 맞는 것부터 보여 준다는 뜻입니다.

같은 검색어로 두 방식을 견주면 이렇습니다.

표에서 눈여겨볼 줄은 「두 낱말만 든 책」입니다. best match 검색은 덜 맞는 책도 버리지 않고 뒤로 보냅니다. 그래서 결과가 0건이 되는 일이 드뭅니다. 이용자는 위에서부터 읽으면 됩니다.

대가도 있습니다. 「세 낱말이 꼭 다 들어야 한다」처럼 이용자가 조건을 강제할 수 없습니다. 덜 맞는 책이 늘 뒤에 섞여 나오므로 어디까지가 맞는 책인지 경계도 없습니다.

점수를 매기는 바탕

순서대로 늘어놓으려면 「얼마나 잘 맞나」를 숫자로 내야 합니다. Okapi 는 그 숫자를 확률 모델로 냈습니다. 확률 모델은 글마다 이용자가 찾던 글일 확률을 어림합니다. 그리고 그 확률이 높은 글부터 위에 올립니다.

다만 확률 값을 글마다 그대로 계산하지는 않습니다. 확률이 높은 순서와 같은 순서가 나오도록, 낱말마다 무게를 매기고 그 무게를 더한 값으로 대신 잽니다. 그래서 점수는 확률 자체가 아니라 줄 세우는 데 쓰는 숫자입니다.

그러면 무게는 어떻게 정할까요. 많은 글에 흔히 나오는 낱말은 가볍습니다. 드물게 나오는 낱말은 무겁습니다. 「추천」은 수많은 책에 들어 있지만 「사료」는 몇 권에만 들어 있습니다. 그러니 「사료」가 든 책이 이 검색어에 더 가깝다고 봅니다. 이렇게 드문 낱말에 무게를 더 주는 생각을 역문서 빈도라고 부릅니다.

책의 점수는 그 책에 든 검색어 낱말의 무게를 더한 값입니다. Okapi 는 이 점수로 책을 줄 세웠습니다. 이 무게 공식은 Stephen Robertson 과 Karen Spärck Jones 가 확률 모델에서 끌어낸 것입니다.

관련 피드백과 질의 확장

Okapi 는 이용자의 반응을 받아 검색을 고치는 방법도 시험했습니다. 처음 낸 결과는 어림일 뿐입니다. 이용자는 어느 책이 맞는지 보면 압니다. 그 판단을 시스템에 돌려주게 한 것입니다.

이용자가 결과에서 맞는 책을 고르면, 시스템은 고른 책들을 보고 낱말의 무게를 다시 계산합니다. 이 일을 관련 피드백이라고 부릅니다. 고른 책에 자주 든 낱말은 무거워집니다.

질의 확장은 고른 책에 자주 나온 낱말을 검색어에 보태는 일입니다. 이용자가 치지 않은 「영양」이나 「습식」 같은 낱말이 검색어에 들어오는 식입니다. Okapi 는 이 둘을 실험에 넣어 결과가 얼마나 나아지는지 쟀습니다.

아래 그림은 이 한 바퀴를 순서대로 보입니다.

sequenceDiagram
    participant 이용자
    participant Okapi
    이용자->>Okapi: 「고양이 사료 추천」
    Okapi-->>이용자: 점수가 높은 순으로 책 목록
    이용자->>Okapi: 맞는 책을 고른다
    Note over Okapi: 고른 책으로 낱말 무게를 다시 계산하고<br/>자주 나온 낱말을 검색어에 보탠다
    Okapi-->>이용자: 보탠 검색어로 다시 낸 목록

이용자는 고르기만 합니다. 무게를 고치고 낱말을 보태는 일은 시스템이 합니다. 그래서 이용자가 검색어를 다시 궁리하지 않아도 두 번째 목록이 처음보다 나아질 수 있습니다.

BM 공식과 TREC

공식은 종이 위에서 그럴듯해 보여도 많은 글과 많은 질문에 돌려 봐야 나은지 압니다. 그 시험장이 TREC(Text REtrieval Conference, 텍스트 검색 대회)입니다. 미국 NIST(National Institute of Standards and Technology, 국립표준기술연구소)가 1992년부터 해마다 여는 검색 평가 대회입니다.

TREC 은 참가팀에게 같은 문서 더미와 같은 질문 묶음을 나눠 줍니다. 팀들이 낸 결과를 같은 기준으로 재므로 공식끼리 견줄 수 있습니다. Okapi 팀은 1992년 첫 대회부터 참가했습니다.

Okapi 팀은 대회마다 점수 공식을 고쳐 가며 시험했습니다. 공식마다 BM(Best Match)과 번호를 붙였습니다. 앞에서 본 best match 검색에서 따온 이름입니다. 첫 대회의 공식은 드문 낱말에 무게를 주는 계산만 했습니다.

두 번째 대회부터는 점수에 두 가지를 더 넣었습니다. 첫째는 낱말이 글 안에 몇 번 나왔는지입니다. 「사료」가 열 번 나오는 책은 한 번 나오는 책보다 고양이 사료 이야기에 더 가깝다고 봅니다.

둘째는 글의 길이입니다. 긴 글에는 어떤 낱말이든 우연히 여러 번 나오기 쉽습니다. 그래서 같은 횟수가 나와도 긴 글은 점수를 그만큼 깎습니다.

이 두 값을 넣은 공식이 BM11(Best Match 11)과 BM15(Best Match 15)입니다. 둘은 글 길이로 점수를 얼마나 깎느냐가 달랐습니다. 자세한 차이는 BM25 항목이 다룹니다.

1994년 세 번째 대회에서 Okapi 팀은 BM25 를 냈습니다. 길이로 깎는 정도를 조절할 수 있게 해서 BM11 과 BM15 를 한 공식에 담은 것입니다. 「Okapi BM25」라는 이름이 여기서 나왔습니다.

지금 이 이름을 만나는 곳

검색 기능을 만들 때 Okapi 시스템을 설치해 쓰지는 않습니다. 쓰는 것은 BM25 를 넣어 둔 검색 제품입니다. 검색 라이브러리 Lucene 과 그것을 품은 검색 서버 Elasticsearch 가 기본 점수 공식으로 BM25 를 씁니다.

그래서 문서나 설정에 나오는 Okapi 는 대개 BM25 를 가리킵니다. 「Okapi BM25」는 「Okapi 시스템에서 나온 BM25 공식」이라는 뜻입니다. 공식의 내용은 BM25 항목이 다룹니다.

관련 항목

Okapi 가 속하는 상위 분류

정보 검색 · 검색 엔진 · 전문 검색 · 랭킹 · 순위 모델 · OPAC

Okapi 에서 다듬어진 점수 공식

BM25 · BM25F · BM1 · BM11 · BM15 · 확률 모델 · 이진 독립 모델 · 확률 순위 원리

Okapi 가 점수에 쓴 값

역문서 빈도 · 문서 빈도 · 낱말 빈도 · 문서 길이 · TF-IDF

Okapi 가 시험한 검색 개선 기법

관련 피드백 · 유사 관련 피드백 · 질의 확장 · best match 검색

Okapi 와 겨룬 검색 방식과 시스템

불리언 검색 · 벡터 공간 모델 · SMART · 언어 모델 검색

Okapi 를 시험한 평가 대회와 지표

TREC · NIST · 테스트 컬렉션 · 정밀도 · 재현율 · Cranfield 실험

Okapi 의 BM25 를 넣은 검색 제품

Apache Lucene · Elasticsearch · OpenSearch · Apache Solr · Terrier · Xapian