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

MỞ RỘNG THỰC THỂ ĐỊNH DANH TRÊN NỀN WEBSinh viên: Nguyễn Tiến TùngNội dungGiới thiệu bài toán mở rộng thực thể định danhSet Expander for Any Language (SEAL)FetcherExtractorRankerIterative SEAL (iSEAL)Mở rộng có giám sát lặpMở rộng không có giám sát lặpGiớ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 SMột hệ thống mở rộng thực thể nổi tiếng đó là Google 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ảnKhông đòi hỏi phải chuẩn bị dữ liệuThực hiện tốt với tập mồi nhỏKiến trúc hệ thốngFetcher: Tải về các trang web từ WebExtractor: 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ọnCanonNikonOlympusPentaxSonyKodakMinoltaPanasonicCasioLeicaFujiSamsungThe FetcherProcedure:Bao gồm câu truy vấn cho tất cả tập mồiSử dụng Google API để trả về Top N URLsCrawler URLsGửi các documents mà fetcher tới extractorThe ExtractorHọc wrappers cho các trang webMỗi văn bản phải dùng wrapper riêng1 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 candidate8 / 20Language-Independent Set ExpansionExtractor E1 finds maximally-long contexts that bracket all instances of every seedIt seems to be working but what if I add one more instance of “toyota”?It seems to be working too but how about a more complex example?9 / 20Language-Independent Set ExpansionExtractor E2 finds maximally-long contexts that bracket at least one instance of every seedThe RankerXế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 WalkPageRankBayesian SetsWrapper LengthBuilding a graphThe RankerRandom 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.The RankerPageRank: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ấtThe RankerBayesian SetsPhươ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ảnhHàm length: trả về tổng độ dài của các cặp strings đó trong wjNhận xétTừ thực nghiệm R.C.Wang đã đưa ra kết quả cho một số thuật toán rank mà ông đề cậpTừ 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ốngRanker \ #Seeds23456Random Walk77.183.984.583.778.9Page Rank74.182.683.483.078.5Bayesian Sets77.084.184.884.079.3Wrapper Length77.583.283.382.278.0Average76.483.584.083.278.7Iterative 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ớnGọi SEAL nhiều lầnPhươ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. Mở rộng có giám sát lặpHai 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:Mở rộng có giám sát lặpISS: 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.Mở rộng không giám sát lặpHai 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: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:Nhận xét từ quá trình thực nghiệmNhận xét từ quá trình thực nghiệmReferencesR. C. Wang and W. W. Cohen. “Language-independent set expansion of named entities using the web”, ICDM: 342–350, IEEE Computer Society, 2007R. C. Wang and W. W. Cohen. “Iterative Set Expansion of Named Entities using the web”, ICDM, IEEE Computer Society, 2008O. 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, 2005H. 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.