Tiến trình tìm kiếm thông tin
Phương pháp phù hợp phản hồi
Giải thuật Rocchio
36 trang |
Chia sẻ: Mr Hưng | Lượt xem: 1071 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Tìm kiếm và trình diễn thông tin - Tiến trình tìm kiếm và phù hợp phản hồi, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
(IT4853) Tìm kiếm và trình diễn thông tin
Tiến trình tìm kiếm và phù hợp phản hồi
Giảng viên
TS. Nguyễn Bá Ngọc
Địa chỉ: Viện CNTT & TT/BM HTTT/B1-603
Email: ngocnb@soict.hust.edu.vn
Website:
3Nội dung chính
Tiến trình tìm kiếm thông tin
Phương pháp phù hợp phản hồi
Giải thuật Rocchio
4Tiến trình tìm kiếm thông tin
5Tiến trình tìm kiếm thông tin
Người dùng tiếp nhận thông tin mới trong quá
trình tìm kiếm:
Kéo theo sự thay đổi nhu cầu thông tin;
Kéo theo những hiệu chỉnh truy vấn;
Nảy sinh những nhu cầu thông tin mới.
Thông thường nhu cầu thông tin không được
thỏa mãn bởi một văn bản đơn lẻ:
Trong thực tế nhu cầu thông tin thường được thỏa
mãn bởi nhiều đoạn thông tin thấy được trong quá
trình tìm kiếm
6Mô hình “Berry-picking”
7Nội dung chính
Tiến trình tìm kiếm thông tin
Phương pháp phù hợp phản hồi
Giải thuật Rocchio
8Các bước tìm kiếm cơ bản với phù
hợp phản hồi
1. Người dùng cung cấp một truy vấn ban đầu;
2. Công cụ tìm kiếm trả về tập kết quả tương ứng.
3. Người dùng phản hồi thông tin về những văn bản phù hợp
và những văn bản không phù hợp.
4. Công cụ tìm kiếm sinh câu truy vấn mới:
Hy vọng sẽ tốt hơn truy vấn hiện tại.
5. Thực hiện truy vấn mới và cập nhật lại kết quả:
Hy vọng sẽ đầy đủ hơn.
Có thể lặp nhiều vòng phản hồi (Các bước 3, 4, 5).
9Giả thuyết phù hợp phản hồi
Mục đích: Tăng tính đầy đủ của kết quả tìm kiếm.
Điều kiện 1: Truy vấn ban đầu thể hiện đúng nhu cầu
thông tin của người dùng.
Điều kiện 2: Những văn bản phù hợp chứa những thuật
ngữ tương tự
Giải quyết vấn đề từ đồng nghĩa, vd: Ô tô / xe máy
Nhờ đó có thể thu được những văn bản phù hợp khác khi sử dụng
thông tin phản hồi.
Tuy nhiên có thể làm giảm tính chính xác vì các văn bản phù hợp
chứa từ không liên quan đến chủ đề.
10
Ví dụ tập kết quả tìm kiếm
Truy vấn: “xe máy”
11
Thông tin phản hồi
12
Tập kết quả mới
13
Ví dụ phù hợp phản hồi trong không
gian vec-tơ
truy vấn “canine”
Fernando Díaz
14
Ví dụ phù hợp phản hồi trong không
gian vec-tơ
Fernando Díaz
15
Ví dụ phù hợp phản hồi trong không
gian vec-tơ
Fernando Díaz
16
Ví dụ phù hợp phản hồi trong không
gian vec-tơ
Fernando Díaz
17
Nội dung chính
Tiến trình tìm kiếm thông tin
Phương pháp phù hợp phản hồi
Giải thuật Rocchio
18
Giải thuật Rocchio
Rocchio lựa chọn truy vấn để cực đại hóa hàm
Dr tập văn bản phù hợp; Dnr tập văn bản không phù hợp.
xu hướng: ~qopt là vec-tơ tách biệt tối đa văn bản phù hợp
và không phù hợp.
))](,())(,([maxarg nrr
q
opt DqsimDqsimq
Vấn đề: Không biết được tập văn bản phù hợp thực tế
rjrj Dd
j
nrDd
j
r
opt d
D
d
D
q
11
Truy vấn tối ưu trên lý thuyết
19
x
x
x
x
o
o
o
Truy vấn
tối ưu
x Văn bản không phù hợp
o Văn bản phù hợp
o
o
o
x x
xx
x
x
x
x
x
x
x
x
x
x
20
Trọng tâm của bộ văn bản
Trong mô hình không gian vec-tơ, mỗi văn bản được biểu
diễn như một điểm trong không gian đa chiều:
Trọng tâm của một bộ văn bản D được định nghĩa như sau:
Trọng tâm của một tập điểm được xác định tương tự khối
tâm của vật rắn.
Dd
d
D
D
||
1
)(
21
Ví dụ trọng tâm
22
Giải thuật Rocchio 1971 (SMART)
qm: vec-tơ truy vấn đã thay đổi; q0: vec-tơ truy vấn gốc;
Dr và Dnr : tập văn bản phù hợp và không phù hợp đã biết;
α, β, và γ: là các trọng số
Sự cân bằng giứa α vs. β/γ: Có thể sử dụng β/γ cao nếu
có nhiều thông tin phản hồi.
Đặt trọng số âm bằng 0.
Được sử dụng trong hệ thống SMART (1971)
nrjrj Dd
j
nrDd
j
r
m d
D
d
D
qq
11
0
23
Phản hồi phù hợp vs. phản hồi không
phù hợp
Phản hồi phù hợp được đánh giá cao hơn phản
hồi không phù hợp.
Ví dụ, đặt β = 0.75, γ = 0.25 để có trọng số lớn
hơn cho những phản hồi phù hợp.
24
Nhược điểm của phù hợp phản hồi
Chi phí cao
Phù hợp phản hồi sinh ra truy vấn dài.
Chi phí xử lý truy vấn dài sẽ cao hơn.
Người dùng cần nhiều hời gian để đưa ra phản hồi.
Có thể gây khó hiểu vì sao một tài liệu cụ thể được
trả về sau khi áp dụng phù hợp phản hồi.
Công cụ tìm kiếm Excite có phù hợp phản hồi đầy
đủ ở một thời điểm nhưng đã loại bỏ nó sau đó.
25
Phù hợp phản hồi giả lập
Giả thiết rằng k văn bản đầu tiên trong danh sách
xếp hạng là những kết quả phù hợp.
Thực hiện phù hợp phản hồi (v.d., Rocchio)
Áp dụng phản hồi giả lập có thể làm xê dịch hoàn
toàn truy vấn.
Trong hệ thống SMART:
Đánh giá tốt trên nhiều truy vấn
Kết quả rất thấp cho một vài truy vấn.
26
Bài tập
Các vòng tròn: những văn bản phù hợp, Xs: những văn bản không
phù hợp
q0 là tâm của tập văn bản phù hợp,
Hãy xác định qm theo phương pháp Rocchio
27
Minh họa thuật toán Rocchio
: Trọng tâm của những văn bản phù hợp
28
Minh họa Rocchio
không tách biệt những văn bản phù hợp / không phù hợp.
29
Minh họa Rocchio
trọng tâm của những văn bản không phù hợp.
30
Minh họa Rocchio
31
Minh họa Rocchio
- hiệu vec-tơ
32
Minh họa Rocchio
cộng vec-tơ khác biệt vào
33
Minh họa Rocchio
để lấy
34
Minh họa Rocchio
phân biệt văn bản phù hợp / không phù hợp rất hiệu quả.
35
Minh họa Rocchio
tách biệt văn bản phù hợp / không phù hợp rất hiệu quả.
36
Tài liệu tham khảo
Chương 9 của IIR
Tài nguyên tại địa chỉ
Salton and Buckley 1990 (tài liệu gốc về phù hợp
phản hồi)
Spink, Jansen, Ozmultu 2000: Relevance feedback
at Excite
Các file đính kèm theo tài liệu này:
- bai_9_tien_trinh_tim_kiem_va_phu_hop_phan_hoi_8979.pdf