Tìm kiếm và trình diễn thông tin - Mô hình ngôn ngữ

(IT4853) Tìm kiếm và trình diễn thông tin Mô hình ngôn ngữ 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: 2 Nội dung chính  Mô hình sinh  Các giả thuyết cơ bản  Thử nghiệm 3 Mô hình sinh văn bản  Máy trạng thái hữu hạn  I wish I wish I wish I wish . . . Không thể sinh: “wish I wish” hoặc “I wish I”. 4 Máy một trạng thái frog said that toad likes frog STOP P(string) = 0.01 · 0.03 · 0.04 · 0.01 · 0.02 · 0.01 · 0.2 = 0.0000000000048 Trong đó STOP là trạng thái dừng. 5 Xếp hạng văn bản  “frog said that toad likes frog” STOP P(string|Md1) = 0.01 · 0.03 · 0.04 · 0.01 · 0.02 · 0.01 · 0.2 = 0.0000000000048 = 4.8 · 10-12  P(string|Md2 ) = 0.01 · 0.03 · 0.05 · 0.02 · 0.02 · 0.01 · 0.2 = 0.0000000000120 = 12 · 10-12  P(string|Md2 ) > P(string|Md1 )  Thứ tự xếp hạng: d2 d1 6 Nội dung chính  Mô hình sinh  Các giả thuyết cơ bản  Thử nghiệm 7 Xác suất sinh chuỗi từ  Giả thuyết Unigram:  Xác suất sinh một từ là độc lập với xác suất sinh các từ còn lại:  Giả thuyết đa thức: 8 Xác suất phù hợp truy vấn  Query likelihood language model  Xếp hạng văn bản theo xác suất P(d|q): xác suất văn bản d phù hợp với truy vấn q.  Theo luật Bayes  P(q) là hằng số;  Giả sử P(d) là đồng nhất; 9 Có thể xếp hạng theo P(q|d): xác suất mô hình văn bản d sinh truy vấn q. Giả thuyết Unigram và phân bố đa thức Trong đó Kq là hệ số đa thức – là hằng số với một câu truy vấn q xác định, có thể bỏ qua trong xếp hạng. 10 𝐾𝑞 = 𝐿𝑞! 𝑡𝑓𝑡1,𝑞! 𝑡𝑓𝑡2,𝑞! 𝑡𝑓𝑡𝑀,𝑞! Ước lượng sử dụng khả năng cực đại  Hàm xếp hạng: 𝑅𝑎𝑛𝑘 𝑑, 𝑞 = 𝑡∈𝑞 𝑝(𝑡|𝑀𝑑) 𝑅𝑎𝑛𝑘 𝑑, 𝑞 = 𝑡 𝑑𝑢𝑦 𝑛ℎấ𝑡 ∈𝑞 𝑝(𝑡|𝑀𝑑) 𝑡𝑓𝑡,𝑞 𝑝 𝑡 𝑀𝑑 = 𝑡𝑓𝑡,𝑑 𝐿𝑑 Nếu d không chứa một từ truy vấn t thì Rank(d, q) = 0 ==> Cần làm mịn để tránh giá trị 0. 11 Maximum likelihood estimation: Mô hình bộ dữ liệu  Tương tự văn bản, xác suất bộ dữ liệu sinh từ t: 𝑝 𝑡 𝑀𝐶 = 𝑐𝑓𝑡,𝐶 𝐿𝐶  MC là mô hình sinh xác định trên bộ dữ liệu C  𝐿𝐶 = 𝑑∈𝐶 𝐿𝑑, là số từ trong bộ dữ liệu 12 Làm mịn tuyến tính  Linear interpolation  Kết hợp mô hình văn bản và mô hình bộ dữ liệu p(t|d) = λp(t|Md) + (1 - λ)P(t|Mc) 𝑤𝑡,𝑑 = λ 𝑡𝑓𝑡,𝑑 𝐿𝑑 + (1 − λ) 𝑐𝑓𝑡,𝐷 𝐿𝐷 13 Tổng hợp các giả thuyết  Giả thuyết Unigram: Unigram Assumption  Phân bố đa thức: Multinomial distribution  Làm mịn tuyến tính: Linear interpolation  Ước lượng khả năng cực đại: Maximum Likelihood Estimation (MLE) 𝑅𝑎𝑛𝑘 𝑞 𝑑 = 𝑡∈𝑉 λ 𝑡𝑓𝑡,𝑑 𝐿𝑑 + (1 − λ) 𝑐𝑓𝑡,𝐶 𝐿𝐶 14 Giá trị tham số  Sử dụng λ lớn có xu hướng trả về văn bản chứa tất cả từ truy vấn  Hiệu ứng sử dụng điều kiện AND  Giá trị λ nhỏ thích hợp cho xử lý truy vấn dài  Hiệu ứng sử dụng điều kiện OR  Cần tùy chỉnh λ để đạt được chất lượng cao. 15 Giả thuyết mô hình ngôn ngữ  Người dùng có những hình dung nhất định về văn bản cần tìm. Chính mô hình văn bản trong tưởng tượng đó đã làm nảy sinh câu truy vấn.  Xác suất p(q|d) thể hiện khả năng văn bản d chính là văn bản trong tưởng tượng của người dùng. 16 Nội dung chính  Mô hình sinh  Các giả thuyết cơ bản  Thử nghiệm 17 Thử nghiệm của Ponte và Croft  Mô hình ngôn ngữ trả về kết quả tốt hơn so với VSM trong thử nghiệm này  Tuy nhiên chưa đủ cơ sở vững chắc để thay thế VSM trong thực tế 18 Ví dụ 1  Bộ dữ liệu: d1 và d2  d1: Jackson was one of the most talented entertainers of all time  d2: Michael Jackson anointed himself King of Pop  Truy vấn q: Michael Jackson  Sử dụng mô hình như trên slide 14 với λ = 1/2 19 Ví dụ 1  Rank(q|d1) = [(0/11 + 1/18)/2] · [(1/11 + 2/18)/2] ≈ 0.003  Rank(q|d2) = [(1/7 + 1/18)/2] · [(1/7 + 2/18)/2] ≈ 0.013 d2 được xếp hạng cao hơn d1 20 Ví dụ 2  Bộ dữ liệu: d1 và d2  d1 : Xerox reports a profit but revenue is down  d2: Lucene narrows quarter loss but decreases further  Truy vấn q: revenue down  Sử dụng mô hình như trên slide 14 với λ = 1/2 21 Ví dụ 2  P(q|d1) = [(1/8 + 2/16)/2] · [(1/8 + 1/16)/2]  P(q|d1) = 1/8 · 3/32 = 3/256  P(q|d2) = [(1/8 + 2/16)/2] · [(0/8 + 1/16)/2] =  P(q|d2) = 1/8 · 1/32 = 1/256  Xếp hạng d2 cao hơn d1 22 23