Một mô hình tìm kiếm thông tin văn bản xác suất trong thư viện số

Kỷ Yếu Hội Thảo Quốc tế về Thư Viện Số 
 Trang 134
MỘT MÔ HÌNH TÌM KIẾM THÔNG TIN VĂN BẢN XÁC SUẤT TRONG THƯ VIỆN SỐ 
TS. ĐỖ QUANG VINH 
Bộ môn Công nghệ thông tin 
Trường Đại học Văn hóa Hà Nội 
Tóm tắt: Xếp hạng thường không xảy ra ngoại tuyến và không được chú ý đến. Như với động cơ tìm 
kiếm trên World Wide Web, các tài liệu hoặc tóm tắt tài liệu được hiển thị trên một máy trạm và khi xuất hiện, 
người sử dụng (NSD) có thể chấp nhận các tài liệu liên quan và không chấp nhận tài liệu không liên quan. Động 
cơ tìm kiếm có thể đánh giá lại xếp hạng định kỳ, hoặc thậm chí sau mỗi một quyết định của người dùng tin, 
nâng hạng tài liệu giống với các tài liệu được chấp nhận và giảm hạng tài liệu giống với các tài liệu không được 
chấp nhận. Ở đây, chúng tôi khảo sát một mô hình tìm kiếm thông tin văn bản xác suất trong thư viện số. Nội 
dung chính của bài báo: 1. Đặt vấn đề; 2. Mô hình tìm kiếm thông tin xác suất ; 3. Sự phản hồi liên quan; 4. Hiệu 
suất tìm kiếm. 
Từ khóa: tìm kiếm thông tin, thư viện số. 
1. ĐẶT VẤN ĐỀ 
Xếp hạng thường không xảy ra ngoại tuyến và không được chú ý đến. Như với động cơ tìm kiếm trên 
World Wide Web, các tài liệu hoặc tóm tắt tài liệu được hiển thị trên một máy trạm và khi xuất hiện, người dùng 
tin có thể chấp nhận các tài liệu liên quan và không chấp nhận tài liệu không liên quan. Động cơ tìm kiếm có thể 
đánh giá lại xếp hạng định kỳ, hoặc thậm chí sau mỗi một quyết định của người dùng tin, nâng hạng tài liệu 
giống với các tài liệu được chấp nhận và giảm hạng tài liệu giống với các tài liệu không được chấp nhận. Ở đây, 
chúng tôi khảo sát một mô hình tìm kiếm thông tin văn bản xác suất trong thư viện số. 
2. MÔ HÌNH TÌM KIẾM THÔNG TIN XÁC SUẤT 
Tìm kiếm thông tin IR đề cập đến tổ chức, lưu trữ, tìm kiếm và đánh giá thông tin có liên quan tới nhu 
cầu thông tin của người sử dụng. 
Mô hình IR tổng quát là một cặp bao gồm các đối tượng và một ánh xạ tìm kiếm một số đối tượng với 
một đối tượng đại diện cho một truy vấn. 
Kỷ Yếu Hội Thảo Quốc tế về Thư Viện Số 
 Trang 135
Cho D = {d1, d2, ..., dM}, M  2 (1) 
là một tập hữu hạn không rỗng đối tượng. 
Cho  là một ánh xạ tìm kiếm từ D vào trong lực lượng của nó (D), nghĩa là, 
  : D  (D). (2) 
Bằng cách kết hợp tập đối tượng D và ánh xạ tìm kiếm , chúng tôi định nghĩa cấu trúc tìm kiếm thông 
tin như sau: 
Định nghĩa 1 (cấu trúc tìm kiếm thông tin): 
Cấu trúc tìm kiếm thông tin SIR là một bộ đôi: S = . (3) 
Định nghĩa 1 là một định nghĩa tổng quát: nó không đề cập đến về các dạng riêng biệt của ánh xạ tìm 
kiếm  và đối tượng D. Từ đó, các mô hình IR riêng biệt khác nhau có thể nhận được bằng cách đặc tả D và . 
Chúng tôi trình bày một định nghĩa thống nhất đối với các mô hình IR dùng SIR. 
Định nghĩa 2 (mô hình tìm kiếm thông tin MIR): 
Mô hình tìm kiếm thông tin MIR là một SIR S = với 2 thuộc tính sau đây: 
(i) q =   ãi(q, ) = 1 i, q,  (tính phản xạ); (4) 
(ii) i (q) = {  D| ãi(q, ) = max ãk(q, k)} ai, i cố định tùy ý. 
trong đó: 
+ T = {t1, t2, ..., tN} là một tập hữu hạn thuật ngữ chỉ mục, N  1; 
+ O = {o1, o2, ..., oU} là một tập hữu hạn đối tượng, U  2; 
+ (Dj)j  J = {1, 2, ..., M} là một họ cluster đối tượng, Dj  (O), M  2; 
+ D = {j| j  J} là một tập tài liệu, trong đó tập mờ đã chuẩn hóa j = {(tk , j(tk))| tk  T, k = 1, ..., N}, j 
= 1, ..., M, j : T  S  [0, 1]  R là đại diện cluster của cluster đối tượng Dj. 
+ A = {ã1, ..., ãC} là một tập hữu hạn tiêu chuẩn, C  1, trong đó ãi = {((q, j), ãi(q, j)) | j D, j =1, ..., 
M}, i = 1, ..., C là một quan hệ mờ chuẩn hóa, ãi : D x D  [0, 1]  R, q  D cố định tùy ý. Theo truyền thống, 
IR kinh điển có thuộc tính lưỡng cực trong đó có 2 tiêu chuẩn rõ ràng: 
(i) có mặt và không có mặt; 
(ii) tìm kiếm được thực hiện dựa vào (i). 
Kỷ Yếu Hội Thảo Quốc tế về Thư Viện Số 
 Trang 136
Chúng ta giả thiết rằng có thể có 1, 2 hoặc nhiều hơn tiêu chuẩn (nghĩa là, liên quan, không liên quan, 
không thể quyết định được) với mỗi một mức độ khác nhau. Từ đó, chúng ta bắt buộc phải chấp nhận tiêu chuẩn 
là quan hệ mờ. 
+ ai = {  D| ãi(q, ) > i}, i = 1, ..., C là một i-lát cắt tiêu chuẩn mạnh ãi, i  0, q  D cố định tùy 
ý; 
+  : D  (D) là một ánh xạ tìm kiếm. Về mặt hình thức, tìm kiếm nghĩa là liên kết một tập con tài liệu 
với một truy vấn nếu chúng liên quan với nhau – tuân theo một tiêu chuẩn lựa chọn - đủ mạnh. Từ đó, chúng ta 
bắt buộc phải xem truy vấn là một tài liệu và tìm kiếm được định nghĩa dùng -lát cắt. 
Định nghĩa 3 (mô hình tìm kiếm thông tin xác suất PIR): 
Mô hình tìm kiếm thông tin xác suất PIR là một MIR S = thỏa mãn điều kiện sau đây: C = 
2 (5) 
Chúng ta lấy C = 2 là vì ở mô hình IR xác suất truyền thống có 2 tiêu chuẩn: có liên quan và không liên 
quan. 
Định nghĩa 4 (PIR): định nghĩa 3 có thể được định nghĩa lại như sau: 
Mô hình tìm kiếm thông tin xác suất PIR là một MIR S = 
trong đó: C = 2 và (q) = {|ãi(q,)  ãj(q, )}, j = i + (-1)i+1, ãi(q, ) > i}. (6) 
Định nghĩa 5 (mô hình tìm kiếm thông tin xác suất kinh điển): 
Cho D là một tập tài liệu, q  D một truy vấn và P(R|(q, d)) xác suất tài liệu d  D là có liên quan/không 
liên quan với truy vấn q tương ứng. Cho R(q) là tập tài liệu tìm kiếm đáp ứng truy vấn q. Một tài liệu d được lựa 
chọn đáp ứng một truy vấn q nếu 
P(R|(q, d))  P(I|(q, d)) (Luật quyết định Bayes) (7) 
nghĩa là, R(q) = {d| P(R|(q, d))  P(I|(q, d))} (8) 
Chính xác hơn, P(R|(q, d)) và P(I|(q, d)) là xác suất liên đới tới d khi nó được xét có liên quan và không 
liên quan tới q tương ứng. 
Các tài liệu đã lựa chọn có thể được xếp hạng giảm dần của độ liên quan của chúng (nguyên lý xếp hạng 
theo xác suất). Một giá trị ngưỡng thường được sử dụng. 
Đánh giá P(R|(q, d)) và P(I|(q, d)) dựa vào công thức Bayes. 
Kỷ Yếu Hội Thảo Quốc tế về Thư Viện Số 
 Trang 137
Từ quan điểm toán học, chúng ta chú ý: đối với xác suất có điều kiện P(R|(q, d)) có ý nghĩa R và (q, d) là 
các thực thể đồng nhất, nghĩa là, chúng là các sự kiện có -đại số giống nhau trên một trường sự kiện  (khái 
niệm xác suất của Kolmogoroff). Tượng tự đối với P(I|(q, d)). Dù ký hiệu P(R|(q, d)) hoặc P(I|(q, d)) được gọi là 
xác suất liên quan R hoặc không liên quan I của tài liệu d đối với truy vấn q, thực chất nó là xác suất được gán 
cho tài liệu d để biểu thị độ liên quan hoặc không liên quan tới truy vấn q. 
Cho D là một tập đối tượng, một đối tượng cố định bất kỳ q  D và 2 tiêu chuẩn ã1 và ã2 là liên quan và 
không liên quan tương ứng. Cho ãi(q, ), i = 1, 2 là mức độ mà một đối tượng bất kỳ d  D thỏa mãn tiêu chuẩn 
ãi liên quan tới q. 
Định nghĩa 6 (PIR) 
Mô hình tìm kiếm thông tin xác suất PIR là một MIR S = 
trong đó: (q) = {|ã1(q,)  ã2(q, )}, ã1(q, ) > 1}. (9) 
PIR là một trường hợp đặc biệt của MIR (ở định nghĩa 4, ta lấy i =1). 
Dominich đã chứng minh PIR ở định nghĩa 6 và mô hình tìm kiếm thông tin xác suất kinh điển ở định 
nghĩa 5 là tương đương. 
Bookstein và Swanson đề xuất một mô hình tìm kiếm, trong đó một số tài liệu được nhận dạng một lần là 
có liên quan với truy vấn. Ở mô hình xác suất, sự xuất hiện của một thuật ngữ riêng biệt trong một tài liệu được 
hiểu hoặc là một bằng chứng tài liệu có liên quan hoặc không liên quan. Để thiết lập một trọng số đối với mỗi 
một thuật ngữ, các xác suất có điều kiện về “có liên quan tới truy vấn, căn cứ vào thuật ngữ xuất hiện” và 
”không liên quan tới truy vấn, căn cứ vào thuật ngữ xuất hiện” được đánh giá dựa trên một số xét đoán liên quan 
đã biết. Ở một cơ sở dữ liệu (CSDL) có N tài liệu, R của nó có liên quan, giả sử Rt của các tài liệu liên quan chứa 
thuật ngữ t và thuật ngữ t xuất hiện ở ft tài liệu. Ở đây, N, ft và R là các giá trị đối với tập tài liệu huấn luyện nào 
đó mà đối với nó các xét đoán liên quan đã được quyết định. Chẳng hạn, chúng có thể do trình bày với một NSD 
một số tài liệu xếp hạng cao nhất từ một truy vấn vòng đầu đã đánh giá dùng cơ chế tìm kiếm khác như phương 
pháp cosin [8]. 
Bảng – Các xác suất có điều kiện. 
 Số tài liệu 
Có liên quan Không liên quan Tổng 
Thuật ngữ t có mặt Rt ft - Rt ft 
Kỷ Yếu Hội Thảo Quốc tế về Thư Viện Số 
 Trang 138
Thuật ngữ t vắng mặt R - Rt N - ft - (R - Rt) N - ft 
Tổng R N – R N 
Từ đó, một trọng số wt đối với thuật ngữ t nhận được dùng công thức Bayes: 
))RR(fN/()Rf(
)RR/(R
w
tttt
tt
t 
 (10) 
trong đó các giá trị > 1 chỉ thị sự xuất hiện của thuật ngữ t nên được lấy như là trợ giúp cho giả thuyết tài liệu là 
có liên quan và các giá trị < 1 chỉ thị sự xuất hiện của thuật ngữ giả thiết tài liệu là không liên quan. 
Giả thiết sự xuất hiện của các thuật ngữ ở các tài liệu là độc lập thì trọng số đối với một tài liệu Dd được 
tính bằng cách nhân trọng số của các thuật ngữ: 

 dDt
td wDw )( (11) 
Các tài liệu với trọng số cao được lựa chọn như câu trả lời với truy vấn. Vì tất cả được yêu cầu là thứ tự 
tài liệu, không phải là giá trị số chính xác của trọng số, thường biểu diễn là một tổng logarit: 
 

 dDt tttt
tt
dDt
t RRfNRf
RRR
w
))(/()(
)/(
loglog (12) 
Ở đây, một kết quả âm chỉ thị tài liệu được dự báo là không liên quan. Một tổng trọng số của 0 chỉ thị có 
nhiều bằng chứng chống lại sự liên quan là phải bị phạt và tài liệu nên sinh ra bởi một quá trình ngẫu nhiên nào 
đó. 
3. SỰ PHẢN HỒI LIÊN QUAN 
Sự phản hồi liên quan là quá trình sửa đổi truy vấn để nâng cao hiệu suất tìm kiếm. Giả sử một truy vấn 
Q0 được đưa ra với một hệ tìm kiếm và một số tài liệu được trả lại. Sau đó, NSD khảo sát một số hoặc tất cả 
chúng và quyết định là chúng có hoặc không liên quan. Trong một môi trường xử lý theo lô, đây là điểm cuối 
của quá trình – hệ thống cho phép chỉ định các tài liệu có liên quan và sau đó, không thực sự nghi ngờ sự lựa 
chọn này, NSD làm việc với tập con các tài liệu này. Nhưng nó không cần kết thúc ở đó. Một dãy truy vấn 
được thực hiện hiệu quả, trong đó Qi+1 được mong đợi gần hơn với truy vấn tối ưu so với Qi . 
Salton, Buckley và Harman đề xuất phương pháp lặp lại truy vấn. Tất cả sử dụng biểu diễn vectơ mô tả ở 
trên, trong đó tài liệu Dd và truy vấn Q đều được coi là n-vectơ trọng số, trong đó n là số thuật ngữ truy vấn riêng 
biệt. Chiến lược đơn giản nhất như sau: 
Kỷ Yếu Hội Thảo Quốc tế về Thư Viện Số 
 Trang 139

 Rd dnii
DDQQ 1 (13) 
trong đó: Dn là tài liệu xếp hạng cao nhất không liên quan; 
R là tập tài liệu có liên quan. 
Chỉ một tài liệu không liên quan được phép phủ định các thuật ngữ trong truy vấn, nhưng tất cả tài liệu 
liên quan được phép trợ giúp các thuật ngữ mà chúng chứa. Ba quyết định phải được thực hiện. 
1. Thường hạn chế phép tính trừ vectơ sao cho không một thuật ngữ nào nhận được một trọng số < 0 – tài 
liệu không liên quan không được phép cho bất kỳ thuật ngữ có trọng số âm. 
2. Các tài liệu có xu hướng có trọng số  0 nhiều hơn nữa so với truy vấn ban đầu Q0 , như vậy, biểu thức 
này có thể tạo lập một truy vấn mới với hàng trăm hoặc hàng nghìn thuật ngữ, là đánh giá đắt. Do đó, nó thường 
sắp xếp các thuật ngữ trong các tài liệu liên quan theo trọng số giảm dần và chỉ lựa chọn một tập con trong chúng 
ảnh hưởng đến truy vấn tăng lên Qi+1. 
3. Mỗi một trong ba thành phần có thể được lấy trọng số để cho có xu hướng Qi+1 hoặc gần với Qi hoặc 
gần hơn tới các tài liệu liên quan. 
Các biểu thức phản hồi tổng quát hơn cho phép một số lớn hơn trong những tài liệu không liên quan ảnh 
hưởng đến truy vấn mới và bao hàm dự trữ sẵn cho truy vấn ban đầu nhằm ảnh hưởng đến tất cả truy vấn tiếp 
theo: 


 
Id
d
Rd
di01i DDQQQ (14) 
trong đó: , ,  và  là các hằng trọng số (với   0); 
R là tập con tài liệu có liên quan; 
I là một tập con tài liệu không liên quan bởi vì đáp ứng của NSD với các phép lặp truy vấn. 
Sự đánh giá các kỹ thuật phản hồi liên quan là phức tạp bởi vì xếp hạng đã duyệt lại, độ chính xác sẽ cao 
bởi vì hệ thống sẵn sàng cho biết một số tài liệu liên quan và không liên quan. Để đơn giản, thường giả thiết các 
tài liệu xem xét bởi NSD đơn giản không có mặt trong CSDL ở vòng đánh giá thứ hai và các truy vấn duyệt lại 
được thực hiện chống lại một CSDL đã duyệt lại. Nhưng bởi vì các tài liệu đã xoá được xếp hạng cao ở vòng thứ 
nhất, chúng có thể có liên quan và ở vòng thứ hai sự vắng mặt của các tài liệu này chắc chắn nghĩa là độ chính 
xác giảm dần. Do đó, một truy vấn lặp có thể được báo cáo như là có hiệu năng tìm kiếm kém hơn tại mỗi một 
đánh giá, mặc dù sự phản hồi đang hoạt động tốt để đưa vào các tài liệu liên quan mới. Sự lựa chọn là bỏ CSDL 
không đề cập đến khi đánh giá hiệu suất tìm kiếm trong các vòng hai và tiếp theo về thực hiện truy vấn. Ở đây, 
Kỷ Yếu Hội Thảo Quốc tế về Thư Viện Số 
 Trang 140
hiệu suất tìm kiếm tăng mạnh, chỉ vì các tài liệu được xem xét có liên quan ở một vòng được đẩy lên đỉnh của 
xếp hạng ở vòng tiếp theo vì nội dung của chúng được bao hàm trong truy vấn duyệt lại. 
Kinh nghiệm chỉ ra một vòng của phản hồi thường đem đến truy vấn tốt hơn đáng kể và một vòng hai 
đem đến lợi ích phụ thêm nhỏ. Tuy nhiên, có nhiều thay đổi được lựa chọn, bao gồm số tài liệu nên trình bày và 
các nhân tử trọng số khác nhau bao hàm trong các công thức ở trên và không có một hướng dẫn rõ ràng như về 
các kỹ thuật với các tham số gì, là tốt nhất đối với bất kỳ tình huống đã cho. Như với lựa chọn độ đo tương tự ở 
vị trí đầu tiên, các luật phản hồi khác nhau hoá ra là có hiệu quả đối với các loại CSDL khác nhau và các kiểu 
truy vấn khác nhau. 
Đơn giản hơn, chúng ta có các sơ đồ phản hồi thực dụng hơn trong đó hệ thống tính toán một danh sách 
thuật ngữ tuân theo công thức trọng số là quan trọng ở các tài liệu liên quan và sau đó, trình bày với NSD theo 
thứ tự trọng số. Sau đó, NSD tự do lựa chọn trong số thuật ngữ này, mở rộng truy vấn gốc để bao gồm các từ có 
thể bị bỏ sót tại thời điểm truy vấn ban đầu được tạo thành. 
Tất cả lựa chọn này giả thiết ít nhất một tài liệu liên quan được trích lọc trong khi xử lý truy vấn ban đầu 
Q0. Tuy nhiên, dù không có tài liệu nào được tìm thấy, vẫn có một số kỹ thuật có thể được áp dụng để mở rộng 
truy vấn. Đơn giản nhất là báo cáo trong khi không có câu trả lời nào với truy vấn gốc, NSD có thể được lợi 
bằng cách thử lại với một mô tả lựa chọn và các từ khác. Chúng ta sử dụng một từ điển đồng nghĩa trực tuyến có 
ích hơn, hoặc hiển thị một danh sách các từ đồng nghĩa đối với mỗi một thuật ngữ truy vấn và yêu cầu NSD lựa 
chọn các từ bổ sung được thêm vào truy vấn hoặc tự động mở rộng truy vấn không kiểm tra với NSD. 
4. HIỆU SUẤT TÌM KIẾM 
Ở đây, chúng tôi trình bày định nghĩa hai độ đo quan trọng về hiệu suất: độ phục hồi và độ chính xác. 
Cách thông thường nhất mô tả hiệu suất tìm kiếm là tính số tài liệu có liên quan tìm kiếm được và chúng được 
liệt kê theo hạng như thế nào [4], [5]. 
4.1 Độ phục hồi và độ chính xác 
Định nghĩa 7 (độ chính xác P): 
RNP (15) 
Định nghĩa 8 (độ phục hồi R): 
T
R
N
N
R  (16) 
trong đó: NT là tổng số tài liệu có liên quan tới một truy vấn q, NT  0; 
Kỷ Yếu Hội Thảo Quốc tế về Thư Viện Số 
 Trang 141
| (q) | =  là số tài liệu tìm kiếm được đáp ứng q,   0; 
NR là số tài liệu có liên quan tìm kiếm được. 
Định đề: Tỉ số giữa độ phục hồi và độ chính xác R / P thay đổi tuyến tính đối với . 
Chứng minh: 
 NR = R NT = P   R / P =  / NT (17) 
Van Rijsbergen đưa ra một tổ hợp có trọng số của độ phục hồi và độ chính xác như sau: 
 1 – ((a . P . R)/ (b . P + R)) (18) 
4.2 Đường cong P-R 
Vì độ phục hồi là một hàm không giảm của hạng, độ chính xác có thể được coi là một hàm của độ phục 
hồi đúng hơn là hàm của hạng. Thật vậy, hiệu suất tính toán được trình bày là hiệu quả. Quan hệ được tạo thành 
ở một đồ thị đã biết như một đường cong P-R, vẽ đồ thị độ chính xác là một hàm của độ phục hồi. Bởi vì độ 
chính xác thường cao tại các mức độ phục hồi thấp và thấp tại các mức độ phục hồi cao, đường cong nói chung 
giảm dần. Đường cong P-R đối với mẫu được trình bày ở hình sau. 
Duong cong P-R doi voi hang
0
50
100
150
R
P
R
P
Do thi hieu suat tinh toan
0
200
R
P
R
P
Kỷ Yếu Hội Thảo Quốc tế về Thư Viện Số 
 Trang 142
Tài liệu tham khảo 
[1] W. Abramowicz, Knowledge-based Information Retrieval and Filtering from Web, Kluwer Academic 
Publishers, Boston, 2003. 
[2] W.Y. Arms, Digital Libraries, MIT Press, Cambridge, 2003. 
[3] E.A. Fox, Advanced Digital Libraries, Virginia Polytechnic Institue and State University, 2000. 
[4] R.A. Korfhage, Information Storage and Retrieval, John Wiley, New York, 1997. 
[5] G. Kowalski, Information Retrieval Systems, Kluwer Academic Publishers, Boston, 1997. 
[6] B.R. Schatz, Information Retrieval in Digital Libraries, Science 275, 1997, pp. 327-334. 
[7] W. Wu, H. Xiong, S. Shekhar, Clustering and Information Retrieval, Kluwer Academic Publishers, 
Boston, 2004. 
[8] Do Quang Vinh, Ranked Query Text Documents in Digital Libraries, National Conference on Information 
and Communication Technology IX, Da Lat, 2006.