Thuật toán đánh giá _score trong Elasticsearch

Trên Viblo cũng đã có rất nhiều bài viết về ES, các bạn có thể tham khảo thêm bài viết này của bạn @dinhhoanglong91 về kiến trúc cũng như series này về cách hoạt động của anh @nguyen.van.ngoc

Mục đích chính để dùng Elasicsearch là gì ? - Tìm kiếm, dĩ nhiên là ES có thể làm được nhiều điều hơn thế, nhưng cái quan trọng nhất vẫn là tìm kiếm. Và theo mình thì khi dùng bất cứ công cụ gì, ngoài việc biết cách sử dụng nó, thì việc tìm hiểu xem nó hoạt động ra sao cũng quan trọng và thú vị không hề kém.

Khi tìm kiếm, Elascticsearch (ES) trả về cho mình ngoài các kết quả tìm được, còn có đánh giá relevance (độ liên quan) của kết quả dựa trên giá trị thực dương _score. ES sẽ sắp xếp các kết quả trả về của các query theo thứ tự _score giảm dần. Đây là điểm mà mình thấy rất thú vị trong ES, và mình sẽ dành bài viết này để nói về cách làm thế nào người ta tính toán và đưa ra được giá trị _score đó.

Note:
Elasticsearch là tên của search engine, không phải là tên thuật toán!
Một số thuật ngữ rất hay được sử dụng trong Elasticsearch, mình sẽ giữ nguyên để giữ gìn sự trong sáng của thuật ngữ, đồng thời cũng tiện cho việc tra cứu. Các thuật ngữ mình nhắc tới ở đây là: relevance (độ liên quan), index (tương đương với database trong mysql), type (tương đương với table trong mysql), document (tương ứng với record trong mysql), term (từ, từ khóa), field (có thể gọi là trường - nhưng mình không thích lắm vì nó có cấu trúc, nên quyết định giữ nguyên)

TF/IDF
Thuật toán đánh giá được sử dụng rất phổ biến trong Elasticsearch có tên gọi là term frequency/inverse document frequency, gọi tắt là TF/IDF, bao gồm các yếu tố đánh giá: Term frequency, Inverse document frequency, Field-length norm.

Term frequency
Yếu tố này đánh giá tần suất xuất hiện của term trong field. Càng xuất hiện nhiều, relevance càng cao. Dĩ nhiên rồi, một field mà từ khoá xuất hiện 5 lần sẽ cho relevance cao hơn là field mà từ khoá chỉ xuất hiện 1 lần.

Ví dụ: nếu bạn search với từ khoá "quick", thì rõ ràng field bên trên sẽ cho TF cao hơn (xuất hiện 2 lần) filed bên dưới (xuất hiện 1 lần):





TF được tính theo công thức sau:


Giải thích: term frequency (tf) của t trong document d được tính bằng căn bậc hai của số lần t xuất hiện trong d.

Inverse document frequency
Yếu tố này đánh giá tần suất xuất hiện của term trên toàn bộ index. Điều đáng chú ý ở đây là càng xuất hiện nhiều, càng ít thích hợp!

Tại sao lại như vậy ? nghe chừng hơi khó hiểu nhưng thực sự nó rất hợp lý.

Ví dụ thế này, bạn muốn tìm kiếm thông tin về Framgia. Khi bạn search google với từ khoá "công ty", thì nhận được khoảng 170,000,000 kết quả, nhưng với 170,000,000 kết quả đó, rất khó để biết được kết quả nào là kết quả chúng ta thực sự muốn tìm, suy ra rằng từ khoá "công ty" sẽ có giá trị rất thấp. Tuy nhiên, nếu bạn search với từ khoá "công ty Framgia", số lượng kết quả thu gọn lại chỉ còn khoảng 3,000,000 kết quả, và bạn thấy rõ ràng rằng các kết quả này rất sát với kết quả bạn mong muốn. Vì thế từ khoá ít xuất hiện hơn ("công ty Framgia") sẽ cho relevance cao hơn là từ khoá xuất hiện nhiều hơn ("công ty") trên toàn bộ index.

Mặc dù vậy, kết quả trên không có nghĩa là từ khoá "công ty Framgia" tốt hơn từ khoá "công ty" gần 60 lần. IDF được đánh giá theo công thức sau:


Giải thích: inverse document frequency (idf) của t là logarit cơ số e (logarit tự nhiên) của thương giữa tổng số documents trong index và số documents xuất hiện t (giá trị công thêm 1 ở đây để tránh xảy ra lỗi Division by zero).

Theo đó thì kết quả đã được lấy logarit đi nên con số 60 bên trên đã giảm kha khá rồi.

Field-length norm
Yếu tố này đánh giá độ dài của field. Field càng ngắn, thì term sẽ có giá trị càng cao; và ngược lại. Điều này hoàn toàn dễ hiểu, bạn có thể thấy một từ xuất hiện trong title sẽ có giá trị hơn rất nhiều cũng từ đó nhưng xuất hiện trong content.

Công thức:


Giải thích: field-length norm (norm) là nghịch đảo của căn bậc hai số lượng term trong field. (có thể hiểu là số lượng chữ của field đó)

Putting it together
_score cuối cùng sẽ là tích của 3 giá trị trên:



Note:
numDocs chính là maxDocs, đôi khi bao gồm cả những document đã bị delete
fieldNorm được tính toán và lưu trữ dưới dạng 8 bit floating point number. Nên khi tính toán, hệ thống sẽ encode và decode giá trị của fieldNorm về 8 bit, và theo đó, bạn sẽ thấy giá trị filedNorm đôi khi hơi khác so với tính toán một chút xíu xíu thôi. Nếu muốn hiểu thêm bạn có thể tham khảo tại đây

Time for action
Ta tạo và test thử với dữ liệu như sau:



Expected kết quả:
tf: có 1 kết quả/1 doc, vậy tf = 1.0
idf: tính toán theo công thức 1 + log((numDocs)/(docFreqs+1)) = 1 + log(1/2.) = 0.306852
fieldNorm: field "quick brown fox" có độ dài 3, vậy filedNorm = 1/sqrt(3) =0.577350

Actual:


Yeah, kết quả giống với mong đợi (về fieldNorm thì đã có giải thích phía bên trên).

Everything is not so simple
Cảm ơn bạn đã đọc đến đây, nhưng trên thực tế, kể từ bản 5.0, TF/IDF đã không còn được sử dụng như thuật toán default cho similarity trong Elasticsearch nữa rồi. Nghĩa là bạn không cần đọc từ đầu tới giờ cũng không sao!

Mình nhận ra được điều này khi chạy thực tế đoạn code mình viết bên trên kia (yaoming again =))).

Đùa chút thôi, các bạn vẫn hoàn toàn có thể sử dụng thuật toán TF/IDF như cũ, chỉ cần thay đổi config của similarity thôi.


Note:

Trong Elasticsearch có rất nhiều similarity module implement thuật toán đánh giá similarity giữa các kết quả, TF/IDF và BM25 là một trong số đó, các thuật toán khác các bạn có thể tham khảo thêm tại đây
Elasticsearch phiên bản 2.4 trở về trước thì sẽ mặc định similarity là classic (tức TF/IDF)
Elasticsearch phiên bản 5.0 trở lên thì sẽ mặc định similarity là BM25