Vector Database

BM25 Ranking

Inverse document frequency

$$IDF(q_i) = ln\left(1 + \frac{docCount - df(q_i, D) + 0.5}{df(q_i, D)+0.5}\right)$$

docCount: số lượng tài liệu

df(qi, D) là số lượng tài liệu chứa query term

BM25 Score

$$score = \sum_{i=1}^n{IDF(q_i)\frac{f(q_i, d)*(k+1)}{f(q_i, d) + k * \left(1 - b + b * \frac{fieldLen}{avgFieldLen}\right)}}$$

b = 0.75

k = 1.2

fieldLen: số lượng term trong document

avgFieldLen: số lượng term trung bình của các document

f(qi, d) là tần suất xuất hiện query thứ i trong document

Example

Cho tập dữ liệu copus như sau

d1: the cats are in the house
d2: the dogs are in the house and outside
d3: the cats and dogs are friends
idf
andarecatsdogsfriendshouseinoutsidethe
d1011001102
d2110101112
d3111110001
df(t, D)232212213
IDF $$ln\left(1+\frac{3-2+0.5}{2+0.5}\right) = 0.47$$ $$ln\left(1+\frac{3-3+0.5}{3+0.5}\right) = 0.1335$$ 0.47 0.47 $$ln\left(1+\frac{3-1+0.5}{1+0.5}\right) = 0.98$$ 0.47 0.47 0.98 0.1335

Query

q = "cats friends"

$$avgFieldLen = \frac{6 + 8 + 6}{3} = 6.67$$

$$score(cats, d_3) = 0.47 * \frac{1(1.2 + 1)}{1 + 1.2*\left(1-0.75 + 0.75\frac{6}{6.67}\right)}=0.49$$

$$score(friends, d_3) = 0.98 * \frac{1(1.2 + 1)}{1 + 1.2*\left(1-0.75 + 0.75\frac{6}{6.67}\right)}=1.023$$

$$score(q, d3) = 0.49 + 1.023 = 1.513$$

Elastic Search Code

Prepare
from elasticsearch import Elasticsearch
client = Elasticsearch(hosts='http://localhost:9200/')
client.ping()

Corpus

corpus = [
    'the cats are in the house',
    'the dogs are in the house and outside',
    'the cats and dogs are friends'
]

Create Index

bulks = []
for i in range(len(corpus)):
    bulks.append({ "index": {"_id": (i + 1)}})
    bulks.append({ "title": corpus[i]})
client.bulk(index='exam02', body=bulks)

Query

q = 'cats friends'
client.search(index='exam02', body={
    "query": {
        "match": {
            "title": q
        }
    }
}, filter_path='hits.hits')