Bài giảng Mở rộng thực thể định danh trên nền Web - Nguyễn Tiến Tùng

Nội dung text: Bài giảng Mở rộng thực thể định danh trên nền Web - Nguyễn Tiến Tùng

1. MỞ RỘNG THỰC THỂ ĐỊNH DANH TRÊN NỀN WEB Sinh viên: Nguyễn Tiến Tùng
2. Nội dung • Giới thiệu bài toán mở rộng thực thể định danh • Set Expander for Any Language (SEAL) – Fetcher – Extractor – Ranker • Iterative SEAL (iSEAL) – Mở rộng có giám sát lặp – Mở rộng không có giám sát lặp
3. Giới thiệu bài toán mở rộng thực thể • Ví dụ: – Tập mồi: {“acer”, “hp”, “asus”} – Câu trả lời: {“lenovo”, “dell”, } • Khái niệm: − Từ một tập nhỏ các thực thể mồi: x1, x2, , xk trong đó xi S – Đưa ra được danh sách các thực thể tiềm năng: e1, e2, , en trong đó ei S • Một hệ thống mở rộng thực thể nổi tiếng đó là Google Set:
4. Set Expander for Any Language (SEAL) • Năm 2007 R.C.Wang đã công bố hệ thống mở rộng thực thể trên nền web là Set Expander for Any Language (SEAL): • Đặc điểm: – Không phụ thuộc vào ngôn ngữ của văn bản – Không đòi hỏi phải chuẩn bị dữ liệu – Thực hiện tốt với tập mồi nhỏ
5. 1. Canon 4. Pentax 2. Nikon 5. Sony 3. Olympus 6. Kodak Kiến trúc hệ thống 7. Minolta 8. Panasonic 9. Casio 10. Leica 11. Fuji 12. Samsung 13. • Fetcher: Tải về các trang web từ Web • Extractor: Học wrapper cho các trang web tải về • Ranker: Xếp hạng các thực thể được trích chọn
6. The Fetcher • Procedure: – Bao gồm câu truy vấn cho tất cả tập mồi – Sử dụng Google API để trả về Top N URLs – Crawler URLs – Gửi các documents mà fetcher tới extractor
7. The Extractor • Học wrappers cho các trang web – Mỗi văn bản phải dùng wrapper riêng – 1 wrapper gồm 2 phần: left(L) và right(R). Phần ở giữa L và R sẽ được lấy vào tập candidate
8. Extractor E It seems to be1 finds maximally- working working too but long contexts whatbut how if I addabout one a that bracket more instance of allmore instances complex of “toyota”? everyexample? seed Language-Independent Set 8 / 20 Expansion
9. Extractor E2 finds maximally-long contexts that bracket at least one instance of every seed Language-Independent Set 9 / 20 Expansion
10. The Ranker • Xếp hạng các thực thể tiềm năng. R.C.Wang có đề cập tới một số thuật toán rank: – Random Walk – PageRank – Bayesian Sets – Wrapper Length
11. Building a graph
12. The Ranker • Random Walk with Restart (RWR) – Biểu diễn mối quan hệ giữa các documents, các wrappers và các mentions đã được trích chọn. – Đồ thị bao gồm các nodes và các cạnh có hướng được gán nhãn.
13. The Ranker • PageRank: – Gọi u là một trang web; Fu là tập các trang mà u trỏ tới; Bu là tập các trang mà trỏ tới u; Nu = | Fu | là số liên kết từ u và c là một hệ số dùng để tiêu chuẩn hóa. – Chú ý rằng c < 1 vì có một số trang web không có forward links và trọng số của chúng bị mất
14. The Ranker • Bayesian Sets – Phương pháp này xây dựng một bảng đặc trưng hai chiều trong đó mỗi cột đại diện cho một thuộc tính và mỗi hàng là một thực thể đã được trích chọn và mỗi ô (j,k) chỉ ra sở hữu của thực thể xk của đặc trưng fj. – Kết hợp chặt chẽ hai đặc trưng: chính sách ngăn chặn văn bản và trích chọn bao gói. • Wrapper Length: – Wj: bao gói thứ j hình thành bởi một cặp trái và phải xâu ngữ cảnh – Hàm length: trả về tổng độ dài của các cặp strings đó trong wj
15. Nhận xét • Từ thực nghiệm R.C.Wang đã đưa ra kết quả cho một số thuật toán rank mà ông đề cập Ranker \ #Seeds 2 3 4 5 6 Random Walk 77.1 83.9 84.5 83.7 78.9 Page Rank 74.1 82.6 83.4 83.0 78.5 Bayesian Sets 77.0 84.1 84.8 84.0 79.3 Wrapper Length 77.5 83.2 83.3 82.2 78.0 Average 76.4 83.5 84.0 83.2 78.7 • Từ bảng kết quả cho thấy hệ thống hoạt động tốt với tập mồi gồm 3-4 thực thể. • Qua thực nghiệm, tác giả lựa chọn việc sử dụng thuật toán Random Walk làm phương pháp xếp hạng chính cho hệ thống
16. Iterative Set Expander for Any Language (iSEAL) • Hệ thống iSEAL khắc phục được hạn chế của SEAL • Đặc điểm: – Có thể hoạt động trên tập mồi lớn – Gọi SEAL nhiều lần • Phương pháp: – Mở rộng tập có giám sát lặp: Xử lý được số lượng tập mồi ban đầu không giới hạn. – Mở rộng tập không giám sát lặp: Yêu cầu tối thiểu sự giám sát lặp.
17. Mở rộng có giám sát lặp • Hai hướng lựa chọn tập mồi đó là Fixed Seed Size (FSS) và Increasing Seed Size (ISS) – FSS: Yêu cầu mỗi vòng lặp đều sử dụng hai thực thể làm tập mồi. Pseudo-code của thuật toán:
18. Mở rộng có giám sát lặp – ISS: Vòng lặp đầu tiên sử dụng tập mồi gồm 2 mồi trong tập mồi được cung cấp, sau đó sẽ tăng số lượng mồi lên 1 sau mỗi bước mở rộng thành công.
19. Mở rộng không giám sát lặp • Hai hướng lựa chọn tập mồi đó là Fixed Seed Size (FSS) và Increasing Seed Size (ISS) – FSS: Sử dụng tập mồi gồm 2 phần tử mới và được tin cậy nhất trích chọn được từ vòng lặp gần nhất. Pseudo-code của thuật toán:
20. Mở rộng không giám sát lặp – ISS: Sử dụng mồi mới tại bước lặp thứ i là thực thể mới được đánh giá cao nhất trong vòng lặp thứ (i-1). Pseudo-code của thuật toán này:
21. Nhận xét từ quá trình thực nghiệm
22. Nhận xét từ quá trình thực nghiệm
23. References • R. C. Wang and W. W. Cohen. “Language-independent set expansion of named entities using the web”, ICDM: 342–350, IEEE Computer Society, 2007 • R. C. Wang and W. W. Cohen. “Iterative Set Expansion of Named Entities using the web”, ICDM, IEEE Computer Society, 2008 • O. Etzioni, M. J. Cafarella, D. Downey, A.-M. Popescu, T. Shaked, S. Soderland, D. S. Weld, and A. Yates. “Unsupervised named-entity extraction from the web: An xperimental study”. Artif. Intell., 165(1):91–134, 2005 • H. Tong, C. Faloutsos, and J.-Y. Pan. “Fast random walk with restart and its applications”. In ICDM, pages 613–622. IEEE Computer Society, 2006. • L. Page, S. Brin, R. Motwani, and T. Winograd. “The PageRank citation ranking: Bringing order to the web”. Technical report, Stanford Digital Library Tech. Project, 1998.