Bài giảng Xử lý ngôn ngữ tự nhiên (Natural Language Processing) - Bài: Phản hồi thông tin - Lê Thanh Hương

Nội dung text: Bài giảng Xử lý ngôn ngữ tự nhiên (Natural Language Processing) - Bài: Phản hồi thông tin - Lê Thanh Hương

1. Phản hồi thông tin „ Phản hồi thông tin (Information Phản hồi thông tin Retrieval - IR) là việc tìm các tài liệu phi cấutrúcu trúc (thường là vănbn bản) th ỏa điều kiện tìm kiếm từ một kho dữ liệu lớn Lê Thanh Hương (thường được lưu trong máy tính) Bộ môn Hệ thống thông tin Viện CNTT&TT 1 2 Các hệ thống dựa trên từ khóa Các vấn đề „ tập các từ khóa có khả năng xuất hiện trong „ Đa nghĩa: 1 từ - n nghĩa tài liệu (vd., JFK, assasination) „ Đồng nghĩa: n từ - 1 nghĩa „ Các phép toán AND OR: AND(Kennedy, conspiracy, OR(assasination, murder)) „ Kích thước: các hệ thống IR phải có khả or năng xử lý tập ngữ liệu cỡ ~Gb AND(OR(Kennedy,JFK), OR(conspiracy, plot), „ Độ phủ: Các hệ thống IR phải có khả năng OR(assasination,assasinated,assasinate,murder, xử lý câu truy vấn thuộc bất kỳ lĩnh vực nào murdered,kill,killed) 3 4 Lấy từ gốc Từ dừng „ Gắn các thuật ngữ trong câu truy vấn với các „ Là các từ thường xuất hiện ở hầu hết các biến thể của từ (cùng gốc từ) trong các tài liệu tài liệu. Các từ này không chứa nhiều „ VD: assassination Æ assassinat thông tin Assassination Assassinations Assassinate Assassinated „ Không đưa vào file nghịch đảo Æ giảm Assassinating kích thước của file này „ Vấn đề: „ Các từ dừng: a, an, the, he, she, of, to, by, „ Lỗi: organization - organ past - paste should, can, „ Bỏ qua: analysis - analyzes matrices - matrix 5 6 1
2. Sec. 1.2 Sec. 1.2 Bước đánh chỉ số: Chuỗi từ Bước đánh chỉ số: Sắp xếp „ Chuỗi các cặp „ Sắp theo từ, rồi theo (từ đã biến đổi, Document ID) docID Bước đánh chỉ số cốt lõi Doc 1 Doc 2 I did enact Julius So let it be with Caesar I was killed Caesar. The noble i' the Capitol; Brutus hath told you Brutus killed me. Caesar was ambitious Sec. 1.2 Sec. 1.2 Bước đánh chỉ số: Từ điển và danh sách Lưu trữ Danh sách docIDs „ Nhiều chỉ mục từ trong 1 tài liệu được trộn lẫn Thuật ngữ và s ố lần „ Đưa vào trong từ xuất hiện điển và danh sách „ Thêm số lần xuất hiện của tài liệu Con trỏ Sec. 1.3 Sec. 1.3 Xử lý truy vấn: AND Phép trộn „ Xét câu truy vấn: „ Duyệt qua 2 danh sách, thời gian tỉ lệ Brutus AND Caesar với số nút „ Định vị Brutus trong từ điển; „ Lấy danh sách của nó. „ Định vị Caesar trong từ điển; 2 4 8 16 32 64 128 Brutus „ Lấy danh sách của nó. 2 8 1 2 3 5 8 13 21 34 Caesar „ Trộn 2 danh sách 2 4 8 16 32 64 128 Brutus 1 2 3 5 8 13 21 34 Caesar Nếu 2 danh sách có độ dài là x và y, phép trộn có độ phức tạp O(x+y) . Vấn đề cốt yếu: các danh sách sắp theo docID 17 18 3
3. Sec. 1.3 Tối ưu hóa truy vấn Bài tập „ vd., (madding OR crowd) AND (ignoble „ Đưa ra trình tự xử lý truy vấn cho OR strife) Term Freq „ Lấyty tầnsun suấtxut xuấthit hiệnchomn cho mọithui thuậtngt ngữ (tangerine OR trees) AND eyes 213312 (marmalade OR skies) AND kaleidoscope 87009 „ Đánh giá kích thước của mỗi câu lệnh OR (kaleidoscope OR eyes) marmalade 107913 bằng cách tính tổng các tần suất của nó skies 271658 „ Xử lý theo trật tự tăng của kích thước các tangerine 46653 danh sách trong phép OR trees 316812 25 26 Bài tập Các kỹ thuật nâng cao „ Cụm từ: Stanford University „ Cho câu truy vấn friends AND romans AND (NOT countrymen), ta sử dụng „ Xấp xỉ: Tìm Gates NEAR Microsoft. „ Cần đánh chỉ số để lấy thông tin về vị trí trong các tài liệu tầnsun suấtct của countrymen như thế nào? „ Vị trí trong tài liệu: Tìm các tài liệucó(u có (author = Ullman) AND (text contains automata). „ Mở rộng phép trộn cho câu truy vấn „ Từ khóa tìm kiếm xuất hiện trong 1 tài liệu nhiều hơn ngẫu nhiên. Có thể đảm bảo thực hiện thì tốt hơn trong thời gian tuyến tính với tổng kích „ Cần thông tin về tần suất của thuật ngữ trong các tài liệu „ Cần độ đo xấp xỉ câu truy vấn với tài liệu thước các danh sách không „ Cần quyết định trả về 1 tài liệu thỏa câu truy vấn hay một nhóm tài liệu phủ các khía cạnh khác nhau của câu truy vấn 27 28 Từ và thuật ngữ Từ và thuật ngữ „ What kind of monkeys live in Costa „ IR quan tâm đến thuật ngữ Rica? „ VD: câu truy vấn „ WhtkidfWhat kind of mon keys liiCtRi?live in Costa Rica? „ từ? „ từ nội dung? „ gốc từ? „ các nhóm từ? „ các đoạn? 29 30 5
4. data from Manning & Schütze textbook (14 million words of NY Times) data from Manning & Schütze textbook (14 million words of NY Times) Mức độ quan trọng nhị thức Mức độ quan trọng nhị thức new ___ ¬new ___ TOTAL new ___ ¬new ___ TOTAL ___ companies 8 4,667 4,675 ___ companies 8 4,667 4,675 ___ ¬companies 15,820 14,287,181 14,303,001 ___ ¬companies 15,820 14,287,181 14,303,001 TOTAL 15,828 14,291,848 14,307,676 TOTAL 15, 828 14, 291, 848 14, 307, 676 „ Giả sử có 2 đồng xu dùng để sinh văn bản. ƒ Giả thiết Null: cùng 1 đồng xu „ Tiếp theo new, ta dùng xu A để quyết định xem có từ companies tiếp theo không ƒ giả sử pnull(co’s | new) = pnull(co’s | ¬new) = pnull(co’s) = 4675/14307676 „ Tiếp theo ¬ new, ta dùng xu B để quyết định xem có từ companies tiếp theo không ƒ pnull(data) = pnull(8 out of 15828)*pnull(4667 out of 14291848) = .00042 ƒ Giả thiết đồng xuất hiện: 2 đồng xu khác nhau „ Ta thấy A được tung 15828 lần và 8 lần có mặt ngửa ƒ giả sử pcoll(co’s | new) = 8/15828, pcoll(co’s | ¬new) = 4667/14291848 „ B được tung 14291848 lần và 4667 lần có mặt ngửa ƒ pcoll(data) = pcoll(8 out of 15828)*pcoll(4667 out of 14291848) = .00081 „ Câu hỏi: 2 đồng xu có trọng số khác nhau không? Nói cách khác, cùng 1 đồng xu hay 2 đồng xu „ Do đó giả thiết đồng xuất hiện gấp đôi dữ liệu p(data). „ Ta có thể sắp xếp bigrams theo giá trị log pcoll(data)/pnull(data) „ nghĩa là, mức độ chắc chắn “companies” đi sau “new” như thế nào 37 38 data from Manning & Schütze textbook (14 million words of NY Times) Mức độ quan trọng nhị thức Phân tích ngữ nghĩa tiềm ẩn new ___ ¬new ___ TOTAL „ Mỗi tài liệu được coi là 1 vector có độ dài k ___ companies 1 583 584 ___ ¬companies 1978 1,785,898 1,787,876 TOTAL 1979 1, 786, 481 1, 788, 460 ƒ Giả thiết Null: cùng 1 đồng xu „ giả sử pnull(co’s | new) = pnull(co’s | ¬new) = pnull(co’s) = 584/1788460 „ pnull(data) = pnull(1 out of 1979)*pnull(583 out of 1786481) = .0056 (0, 3, 3, 1, 0, 7, . . . 1, 0) ƒ Giả thiết đồng xuất hiện: 2 đồng xu khác nhau „ giả sử p (co’s | new) = 1/1979, p (co’s | ¬new) = 583/1786481 coll coll 1 tài liệu „ pcoll(data) = pcoll(1 out of 1979)*pcoll(583 out of 1786418) = .0061 ƒ Giả thiết đồng xuất hiện vẫn tăng p(data), nhưng khá nhỏ. ƒ Nếu không có nhiều dữ liệu, mô hình 2 đồng xu không thuyết phục. ƒ Thông tin tương hỗ vẫn có giá trị, nhưng dựa trên ít dữ liệu hơn. Do vậy có thể tin rằng giả thiết Null chỉ là sự trùng hợp ngẫu nhiên. 39 40 Phân tích ngữ nghĩa tiềm ẩn Phân tích ngữ nghĩa tiềm ẩn „ Mỗi tài liệu được biểu diễn thành 1 điểm trong không „ Giảm điểm: các điểm thực được chuyển về không gian ít chiều hơn gian vector „ ∃ một lựa chọn tốt nhất cho các chiều - có thể biểu diễn một cách tốt nhất các đặc tính của dữ liệu „ Tìm được nhờ sử dụng đại số tuyến tính “Singular Value Decomposition” (SVD) Các điểm trong không gian thu g ọn Các điểm trong không gian k chi ều Các điểm trong không gian thu g ọn Các điểm trong không gian k chi ều 41 41 42 42 7
5. Phân tích ngữ nghĩa tiềm ẩn Phân tích ngữ nghĩa tiềm ẩn „ Thuật ngữ 5 và 8 đóng vai trò quan trọng trong tài liệu nào „ Ngược lại, các thuật ngữ nào mạnh trong tài liệu 5? terms terms 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 Điều này trả lời cho câu truy vấn cho các tọa độ của tài liệu 5 chứa thuật ngữ 5 và 8 1 2 3 4 5 6 7 1 2 3 4 5 6 7 documents đó chỉ là phép nhân ma trận: documents vector thuật ngữ(query) x trọng số của ma trận = vector tài liệu . 49 50 Phân tích ngữ nghĩa tiềm ẩn Phân tích ngữ nghĩa tiềm ẩn „ Nghĩa là, làm trơn dữ liệu thưa bằng ma trận xấp xỉ: M ≈ A B „ SVD xấp xỉ bằng mạng nơron 3 tầng „ A được mã hóa qua các chủ đề, B – mỗi tài liệu sẽ có tập thuật „ Đưa các dữ liệu thưa qua 1 nút cổ chai và làm trơn nó ngữ mới terms terms 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 A matrix themes themes M B 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 documents documents documents documents 51 52 Phân tích ngữ nghĩa tiềm ẩn Phân tích ngữ nghĩa tiềm ẩn Coi A và B là các thuật ngữ và các tài liệu được chuyển về không „ Phân nhóm tài liệu (có thể giải quyết được dữ gian chủ đề ít chiều, tại đó có thể xác định độ tương tự giữa chúng liệu thưa) 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 „ Phân nhóm từ „ So sánh 1 từ vớii1tàili 1 tài liệu A „ Xác định các chủ đề của 1 từ với các nghĩa matrix themes của nó M B „ Phân giải nhập nhằng bằng cách nhìn vào nghĩa của tài liệu „ Xác định các chủ đề con của tài liệu với chủ đề 1 2 3 4 5 6 7 1 2 3 4 5 6 7 của nó documents documents „ phân loại chủ đề 53 54 9