Luận văn Phương pháp học bán giám sát cho bài toán trích chọn thông tin và ứng dụng trích chọn thực thể tên máy ảnh số

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRƯƠNG THỊ PHƯƠNG THẢO PHƯƠNG PHÁP HỌC BÁN GIÁM SÁT CHO BÀI TOÁN TRÍCH CHỌN THÔNG TIN VÀ ỨNG DỤNG TRÍCH CHỌN THỰC THỂ TÊN MÁY ẢNH SỐ Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60.48.05 LUẬN VĂN THẠC SĨ Cán bộ hướng dẫn khoa học: TS. Nguyễn Trí Thành Hà Nội - 2011 2 Lời cam đoan Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm nghiên cứu, tìm hiểu của riêng cá nhân tôi. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân tôi hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Học viên Trương Thị Phương Thảo 3 Mục lục Lời cam đoan ..................................................................................................... 2 Mục lục .............................................................................................................. 3 Danh mục các ký hiệu, các chữ viết tắt............................................................... 4 Danh mục các bảng ............................................................................................ 5 Danh mục các hình vẽ, đồ thị ............................................................................. 6 Mở đầu............................................................................................................... 7 CHƯƠNG 1. GIỚI THIỆU ................................................................................ 8 CHƯƠNG 2. HỆ THỐNG TRÍCH CHỌN THÔNG TIN................................. 14 2.1. Xây dựng hệ thống trích chọn thông tin..................................................... 14 2.1.1. Công nghệ tri thức .................................................................................. 14 2.1.2. Huấn luyện tự động ................................................................................ 14 2.2. Các phương pháp trích chọn ...................................................................... 15 2.2.1. Học có giám sát trích chọn quan hệ ........................................................ 16 2.2.2. Học không giám sát trích chọn quan hệ .................................................. 18 2.2.3. Học bán giám sát trích chọn quan hệ ...................................................... 21 2.2.3.1. DIPRE: Dual Iterative Pattern Relation Extraction .............................. 22 2.2.3.2. Hệ thống SNOWBALL ....................................................................... 26 2.3. Nhận xét .................................................................................................... 32 CHƯƠNG 3. MÔ HÌNH HỌC BÁN GIÁM SÁT TRÍCH CHỌN THỰC THỂ VÀ ỨNG DỤNG.............................................................................................. 33 3.1. Mô tả bài toán............................................................................................ 33 3.2. Mô hình giải quyết bài toán ....................................................................... 33 3.3. Mô hình hệ thống ...................................................................................... 35 3.3.1. Pha tiền xử lí .......................................................................................... 36 3.3.2. Pha sinh các mẫu .................................................................................... 43 3.3.3. Pha sinh các bộ quan hệ mới................................................................... 48 CHƯƠNG 4. THỰC NGHIỆM ........................................................................ 50 4.1. Môi trường thực nghiệm............................................................................ 50 4.2. Dữ liệu thực nghiệm .................................................................................. 50 4.3. Đánh giá hệ thống...................................................................................... 51 4.4. Thực nghiệm ............................................................................................. 51 Kết luận và hướng phát triển tương lai ............................................................. 61 Tài liệu tham khảo............................................................................................ 62 Phụ lục. Mối quan hệ ngữ nghĩa trong WordNet .............................................. 64 4 Danh mục các ký hiệu, các chữ viết tắt IE Information Extraction NE Named Entity MUC Message Understanding Conferences NER Named Entity Recognition IR Information Retrieval DIPRE Dual Iterative Pattern Relation Extraction 5 Danh mục các bảng Bảng 1: Các luật của AutoSlog......................................................................... 18 Bảng 2: Năm bộ quan hệ hạt giống của hệ thống DIPRE.................................. 24 Bảng 3: Ví dụ các sự kiện được mô tả dưới dạng bộ - 7 ................................... 24 Bảng 4: Ví dụ về việc sinh các mẫu DIPRE ..................................................... 26 Bảng 5: Năm bộ quan hệ hạt giống của hệ thống Snowball .............................. 27 Bảng 6: Một số lớp thường dùng trong WordNet ............................................. 45 Bảng 7: Cấu hình của máy PC dùng trong thực nghiệm ................................... 50 Bảng 8: Các công cụ sử dụng trong thực nghiệm.............................................. 50 Bảng 9: Các thư viện sử dụng trong thực nghiệm ............................................. 50 Bảng 10: Dữ liệu kiểm thử và dữ liệu huấn luyện............................................. 51 Bảng 11: Tập các quan hệ hạt giống ban đầu.................................................... 51 Bảng 12: Một số cặp ở lần lặp đầu tiên ............................ 52 Bảng 13: Giá trị Precision, Recall và F1 sau các vòng lặp ................................ 52 Bảng 14: Giá trị Precision, Recall, F1 của hệ thống theo giá trị sup................ 54 Bảng 15: Giá trị của Precision, Recall, F1 thực nghiệm trên tập 5000 .............. 55 Bảng 16: Kết quả so sánh giữa thực nghiệm 1 và 2 .......................................... 55 Bảng 17: Kết quả trích chọn khi áp dụng giải thuật DIPRE trên Tập 1200 ....... 56 Bảng 18: Kết quả trích chọn khi áp dụng giải thuật DIPRE trên Tập 5000 ....... 56 Bảng 19: Bảng thống kê kết quả trích chọn khi áp dụng giải thuật DIPRE cho bài toán trích chọn tên máy ảnh số ................................................................... 56 Bảng 20: Kết quả thực nghiệm 5 với số lượng các cặp tìm được ...................... 58 Bảng 21: Kết quả thực nghiệm 5 - Một số mẫu có độ chính xác cao và xuất hiện nhiều ................................................................................................................ 58 Bảng 22: Kết quả thực nghiệm 5 - Thống kê các loại máy ảnh phổ biến nhất ... 59 Bảng 23: Kết quả thực nghiệm 5 - Thống kê số lượng máy ảnh theo hãng sản xuất .................................................................................................................. 60 Bảng 24: Các quan hệ ngữ nghĩa trong WordNet ............................................. 64 6 Danh mục các hình vẽ, đồ thị Hình 1: Minh họa về một hệ thống trích chọn thông tin...................................... 8 Hình 2: Ví dụ về khai phá quan điểm ............................................................... 10 Hình 3: Sơ đồ hoạt động của hệ thống AutoSlog .............................................. 17 Hình 4: Sơ đồ hoạt động của hệ thống AutoSlog – TS...................................... 19 Hình 5: Ví dụ về AutoSlog - TS ....................................................................... 21 Hình 6: Mô hình hoạt động của hệ thống DIPRE ............................................. 22 Hình 7: Mô hình hoạt động của hệ thống Snowball .......................................... 27 Hình 8: Các sự kiện tìm được dựa vào bộ quan hệ hạt giống ............................ 28 Hình 9: Mô hình hệ thống trích chọn tên máy ảnh số ....................................... 35 Hình 10: Mô hình của pha tiền xử lí ................................................................. 36 Hình 11: Mô hình thuật toán sinh mẫu từ một bộ quan hệ ................................ 43 Hình 12: Giá trị của Precision, Recall, F1 thực nghiệm trên tập 1200 .............. 53 Hình 13: Giá trị Precision, Recall, F1 của hệ thống theo giá trị sup ................ 54 Hình 14: Kết quả thực nghiệm 3 (a) và thực nghiệm 4 (b) đối với giá trị F1..... 57 7 Mở đầu Trích chọn thực thể là bài toán cơ bản nhất trong các bài toán trích chọn thông tin nhưng lại đóng vai trò khá quan trọng. Thực thể tên ngày càng được ứng dụng trong nhiều bài toán trong khai phá dữ liệu web cũng như nhiều các bài toán trong xử lý ngôn ngữ tự nhiên. Do đó việc xây dựng các giải thuật trích chọn các thực thể tên này từ web là bài toán có ý nghĩa quan trọng. Luận văn tập trung vào tìm hiểu việc xây dựng một mô hình trích chọn thực thể tên và ứng dụng vào trích chọn thực thể tên máy ảnh trên web. Cấu trúc luận văn gồm 4 chương: Chương 1: Giới thiệu một cách khái quát nhất bài toán trích chọn thông tin, tính ứng dụng thực tiễn của bài toán. Chương 2: Trình bày một số các khái niệm liên quan đến bài toán trích chọn thông tin, các phương pháp trích chọn thông tin. Với mỗi phương pháp trình bày một mô hình minh họa. Đây là cơ sở luận quan trọng để luận văn đề xuất một mô hình áp dụng với bài toán trích chọn thực thể. Cụ thể luận văn lựa chọn hướng tiếp cận học bán giám sát. Chương 3: Ứng dụng phương pháp học bán giám sát vào hệ thống trích chọn tên máy ảnh kĩ thuật số. Chương 4: Kết quả thực nghiệm của luận văn, đánh giá phương pháp và kết quả đạt được. Phần kết luận: Tóm lược những nội dung chính đạt được của luận văn đồng thời cũng chỉ ra những điểm cần khắc phục và đưa ra những định hướng nghiên cứu trong tương lai. 8 CHƯƠNG 1. GIỚI THIỆU Với sự bùng nổ của Internet và các phương tiện lưu trữ đã tạo ra một lượng thông tin khổng lồ. Bên cạnh đó nhu cầu về tốc độ xử lý thông tin cũng như tính chính xác ngày càng tăng. Hiện nay, các máy tìm kiếm (search engine) thực hiện việc tìm những trang web phù hợp với yêu cầu câu hỏi người dùng. Mặc dù chất lượng của các máy tìm kiếm đã được cải thiện nhưng kết quả trả về chỉ là những tài liệu có liên quan, chúng không dễ dàng gì rút ra được các mối quan hệ tiềm ẩn và tạo được các câu trả lời cho các truy vấn phức tạp, chẳng hạn như “danh sách các công ty liên doanh” hoặc “danh sách các nhà lãnh đạo quốc tế trên toàn thế giới”. Người ta phân loại câu trả lời các truy vấn ở dạng: có phân tích các tài liệu liên quan để tập hợp những thông tin cần thiết. Nếu nhiều mối quan hệ như “Công ty A liên doanh với công ty B” được lưu trong các tài liệu thì nó tự động tổng hợp và cấu trúc hóa, điều này rất tốt không chỉ cho các hệ thống truy vấn thông tin mà còn cho các hệ thống hỏi đáp tự động và tóm tắt văn bản. Do đó khai thác được những tri thức đó sẽ mang lại nhiều thông tin bổ ích. Đó là lĩnh vực mà “trích chọn thông tin” nghiên cứu. Trích chọn thông tin (Information Extraction - IE) là công việc trích ra các thông tin có cấu trúc từ các văn bản không có cấu trúc. Nói cách khác, một hệ thống trích chọn thông tin rút ra những thông tin đã được định nghĩa trước về các thực thể và mối quan hệ giữa các thực thể từ một văn bản dưới dạng ngôn ngữ tự nhiên và điền những thông tin này vào một văn bản ghi dữ liệu có cấu trúc hoặc một dạng mẫu được định nghĩa trước đó. Không giống như hiểu toàn bộ văn bản, các hệ thống trích chọn thông tin chỉ cố gắng nhận biết một số thông tin đáng quan tâm ở một lĩnh vực nào đó. Ví dụ hệ thống trích chọn các bộ quan hệ từ các tài liệu web, bổ sung chúng vào cơ sở dữ liệu. Canon has posted a firmware update for its EOS 7D digital SLR. Pentax has announced the Optio RS1500 compact camera with interchangeable, user designable covers. Casio and Ricoh have released firmware updates for the Exilim EX-H20G and G700SE digital cameras respectively Hình 1: Minh họa về một hệ thống trích chọn thông tin Producer Camera Canon EOS 7D Pentax Optio RS1500 Casio Exilim EX-H20G Ricoh G700SE 9 Có rất nhiều mức độ cũng như nội dung công việc trích chọn thông tin khác nhau. Một số bài toán trích chọn có thể liệt kê như sau:  Trích chọn là thực thể tên (Named Entity –NE). Một thực thể tên là một thực thể được đặt một tên riêng, ví dụ như “Barack Obama” là một thực thể tên người, “Microsoft Corporation” là thực thể tên công ty/ tổ chức [7, 17].  Trích chọn thông tin là đi tìm những quan hệ giữa các đối tượng có tên được chỉ định trước. Ví dụ: từ một câu “Bill Gates là chủ tịch của Microsoft”, chúng ta muốn hệ thống có thể đưa ra được kết quả: Bill Gates là một tên người, Microsoft là tên một tổ chức và Bill Gates ông chủ của Microsoft. Một số quan hệ khác có thể là: quan hệ sát nhập (affiliation); quan hệ vai trò (role); quan hệ về vị trí, địa điểm (location); quan hệ toàn thể-bộ phận (part-whole); quan hệ nhân quả (cause-effect); các mối quan hệ xã hội … giữa các cặp thực thể. Ví dụ, câu “George Bush được bầu làm tổng thống của Mỹ.” Thì quan hệ, “George Bush” (Person) là “tổng thống” của “Mỹ”, có thể được rút ra. [5]  Trích chọn sự kiện cho miền dữ liệu tin tức dưới dạng khung mẫu (template). Mỗi khung mẫu bao gồm tập hợp các slot cần được lấp đầy bởi một hoặc nhiều giá trị. Những giá trị này có thể bao gồm văn bản thuần túy, các con trỏ trỏ tới các đối tượng khung mẫu khác [4, 9]. Ví dụ: “4 Apr. Dallas - Early last evening, a tornado swept through northwest Dallas. The twister occurred without warning at about 7:15 pm and destroyed two mobile homes. The Texaco station at 102 Main St. was also severely damaged, but no injuries were reported.” Đoạn văn bản tóm tắt câu chuyện về thảm họa tự nhiên lốc xoáy, trích chọn các thông tin về ngày và thời gian xảy ra, và thiệt hại tài sản hay thương tích về con người do sự kiện gây ra. Hệ thống có thể trích chọn ra khung mẫu sau: Event: tornado Date: 4/3/97 Time: 19:15 Location: “northwest Dallas”: Texas: USA Damage: “mobile homes” (đối tượng bị thiệt hại – Damaged Object) “Texaco station” (đối tượng bị thiệt hại)  Khai phá quan điểm (opinion mining): trong lĩnh vực này ta cần trích chọn ra các nhận định của người dùng về một đối tượng nào đó [14]. Hình 2 chỉ ra một trong các quan điểm mà ta có thể trích ra là thông tin 10 người dùng nhận thấy “the colors of pictures” được chụp bởi sản phẩm Powershot là “great”. Hình 2: Ví dụ về khai phá quan điểm  Ngoài ra tùy vào từng ứng dụng cụ thể mà ta có thể cần trích chọn các đối tượng khác trong văn bản, chẳng hạn trích chọn các nguyên nhân dẫn đến một loại bệnh nào đó [10], … Con người, thời gian, địa điểm, các con số, ... là những đối tượng cơ bản trong một văn bản dù ở bất kì ngôn ngữ nào. Do đó thực thể tên là một đối tượng được quan tâm rất nhiều và ngày càng trở nên quan trọng, nó đang được khai thác và ứng dụng trong nhiều bài toán trong lĩnh vực xử lý ngôn ngữ tự nhiên (Natural Language Processing) cũng như khai phá văn bản và khai phá web (Web Mining). Mục đích chính của bài toán nhận biết các loại thực thể là xác định những đối tượng này từ đó phần nào giúp cho chúng ta trong việc hiểu văn bản. Rõ ràng trước khi có thể xác định được các mối quan hệ giữa các thực thể ta phải xác định được đâu là các thực thể tham gia vào mối quan hệ đó. Ví dụ về một số ứng dụng của thực thể tên trong lĩnh vực xử lý ngôn ngữ tự nhiên và khai phá dữ liệu văn bản, web là:  Dịch máy (Machine Translation): khi chúng ta phát hiện ra được một thực thể tên trong một văn bản thì khi dịch sang ngôn ngữ mới ta thường để nguyên thực thể tên đó chứ không dịch [12]. I just bought a Powershot a few days ago. I took some pictures using the camera. Here are my feelings: (1) colors are so great even when flash is used (2) easy to grip since the body has a grip handle Opinion holder (writer) Suject Part Attribute Evaluation Condition Opinion unit 1 Opinion holder (writer) Suject Part Attribute Evaluation Condition <body has a grip handle> Opinion unit 2 11  Tóm tắt văn bản: Khi xác định được nội dung của một văn bản nói về một thực thể tên nào đó thì chúng ta sẽ gán trọng số cao cho các câu có đề cập đến thực thể tên, cách này có thể làm tăng chất lượng của hệ tóm tắt [11].  Phân lớp văn bản: khi tìm ra được một thực thể tên thường thuộc một phân lớp văn bản nào đó, thì đó sẽ là một thông tin quan trọng để giúp làm tăng chất lượng của các giải thuật phân lớp. Chẳng hạn như tin nói về tổng thống Obama thường hay xuất hiện ở thể loại tin tức là: Thế giới [15].  Tìm kiếm thực thể: đây là một hướng phát triển mới của các máy tìm kiếm. Khi nhu cầu người dùng tăng cao thì người ta muốn các máy tìm kiếm trở nên thông minh hơn, và người ta mong muốn có một hệ thống tìm kiếm có thể trả về các thực thể người ta cần chứ không phải là các văn bản chứa các thực thể như những máy tìm kiếm hiện tại [13].  Hệ thống hỏi đáp [16], chẳng hạn giúp trả lời các câu hỏi liên quan đến thực thể như “Ai là người đầu tiên đặt chân lên mặt trăng?” - Tên lửa được phóng ra từ đâu? - Ai là chủ nhân và điều khiển tên lửa đó? - Khối lượng chất nổ trong tên lửa? - Chất nổ sử dụng là gì?  Ứng dụng trong phân tích một đối tượng nào đó. Ví dụ như trong một tài liệu văn bản mô tả bằng ngôn ngữ tự nhiên, ta có thể tìm hiểu sự di chuyển của các giám đốc điều hành từ vị trí này đến vị trí khác ở các công ty khác nhau dựa vào các thực thể kiểu: Tên nhà điều hành, Tên công ty cũ, Vị trí cũ, Tên công ty mới, Vị trí mới, Ngày chuyển đi. Thông tin này có ích trong việc phân tích, chẳng hạn như các phân tích liên kết, trình bày tiến trình thời gian, địa vị, và vẽ đồ thị của xu hướng. Ngày nay những thông tin trích chọn cũng được sử dụng để hỗ trợ và tăng cường các loại khác của các ứng dụng xử lý văn bản như các hệ thống truy vấn thông tin, hệ thống hỏi đáp, phân loại văn bản…  … Muốn khai thác được thực thể tên vào các bài toán cụ thể thì công việc đầu tiên là phải nhận dạng ra được các thực thể tên có trong văn bản. Do đó bài toán nhận dạng thực thể tên (Named Entity Recognition – NER) ngày càng trở nên bài toán mang tính chất rất quan trọng và rất cần làm tăng chất lượng của nó. Luận văn tập trung vào bài toán trích chọn thực thể tên và quan hệ của nó trong văn bản. 12 Nhận dạng thực thể có tên là một công việc của xử lý ngôn ngữ tự nhiên trên máy tính, được giới thiệu lần đầu tiên tại hội nghị MUC lần thứ 6 [8], bao gồm các nhiệm vụ: nhân dạng tên người (PERSON), địa danh (LOCATION), tổ chức (organization) (ENAMEX); ngày tháng (date), thời gian (time) (TIME); và tỷ lệ (percentage), tiền tệ (monetary) (NUMEX). Giờ các thực thể tên được mở rộng hơn như tên các loại bệnh, tên các loại protin, tiêu đề bài báo, tên các cuộc hành trình… WWW chứa đựng một nguồn thông tin khổng lồ, và cực kỳ phân tán, từ cơ sở dữ liệu DNA đến danh sách các nhà hàng ưu thích. Tuy nhiên dữ liệu rải rác trong hàng ngàn nguồn thông tin với nhiều định dạng khác nhau. Nếu các mẩu thông tin này có thể được trích chọn từ WWW và tích hợp vào một dạng có cấu trúc, chúng sẽ tạo thành một nguồn thông tin chưa từng có. Nó sẽ bao gồm một thư mục quốc tế lớn nhất của con người, các cơ sở dữ liệu lớn và đa dạng nhất các sản phẩm, và nhiều nguồn tài nguyên hữu ích khác. Chúng ta sẽ trích chọn một quan hệ từ hàng nghìn nguồn dữ liệu, để lấy được những mẩu quan hệ trong WWW. Nhưng một thực tế là khối lượng thông tin quá lớn, việc trích chọn thủ công là điều không tưởng, bởi ta không chỉ làm việc trên khoảng 10 tài liệu mà phải thực hiện trên hàng nghìn tài liệu. Vậy mục đích ở đây là để khai phá các nguồn thông tin và trích chọn các thông tin liên quan từ chúng một cách tự động, hay sự cực tiểu sự can thiệp của con người. Kết quả của việc trích chọn thực thể tên phụ thuộc vào mục đích được xác định trước như tên người, tổ chức, địa điểm, biểu thức của thời đại, số lượng, giá trị tiền tệ, tỷ lệ phần trăm…, người dùng có thể thu lượm được một loạt các tri thức ẩn dưới các thực thể tên đó. Ở đây luận văn tập trung vào việc trích chọn tên máy ảnh kĩ thuật số có sử dụng giải thuật học bán giám sát. Thị trường máy ảnh kỹ thuật số hiện có không dưới 10 nhãn hiệu nổi tiếng trên thế giới như Sony, Canon, Fujifilm, Olympus đến Konica, Nikon, Samsung, Pentax... Nhiều nhà sản xuất chuyên về công nghệ thông tin cũng tham gia vào thị trường này như Epson, HP... cho thấy đây là một thị trường đầy hứa hẹn. Cuộc đua giữa các nhà sản xuất vô cùng sôi động thông qua việc liên tục đưa ra thị trường các sản phẩm có kiểu dáng mới, độ phân giải máy cao, giá mềm. Cuộc cạnh tranh của các nhà sản xuất vẫn đang tiếp tục gia tăng, đem lại cho người tiêu dùng những sản phẩm có chất lượng ngày càng cao với giá ngày càng thấp. Doanh số trên thị trường máy ảnh kỹ thuật số lại bắt đầu có xu hướng tăng lên. Nguyên nhân là do đâu? Hàng năm, số lượng các loại máy ảnh mới ra đời ngày càng nhiều, người tiêu dùng đang bắt đầu thay thế những chiếc máy ảnh kỹ thuật số đã cũ của mình. Nhiều người thậm chí còn mua những chiếc 13 máy ảnh thứ hai, thứ ba cho gia đình. Điều này đòi hỏi người dùng cần phải luôn luôn cập nhật thông tin mỗi khi muốn mua một loại máy ảnh mới, đồng thời đòi hỏi các nhà kinh doanh phải biết chính xác các thông tin liên quan đến các loại máy ảnh mới để đưa ra các chính sách buôn bán cho phù hợp. Tuy nhiên các thông tin trên mạng rất đa dạng và không có sự phân loại, người dùng dễ bị ngột thở bởi rất nhiều các luồng thông tin và các dạng thông tin, việc lấy ra các thông tin cần thiết cho nhu cầu sử dụng của mình là rất khó khăn. Một nhu cầu đơn giản của người dùng là xác định tên máy ảnh này do hãng nào sản xuất từ hàng nghìn các thông tin trên mạng Internet. Một ứng dụng khác của việc trích chọn tên các máy ảnh số là tìm thêm các thông số kỹ thuật liên quan đến từng loại máy ảnh để so sánh, đánh giá sản phẩm giữa các nhà sản xuất. Hoặc có thể ứng dụng vào bài toán khai phá quan điểm. 14 CHƯƠNG 2. HỆ THỐNG TRÍCH CHỌN THÔNG TIN 2.1. Xây dựng hệ thống trích chọn thông tin Có hai hướng tiếp cận: Công nghệ tri thức (Knowledge Engineering) và Huấn luyện tự động (Automation Training). 2.1.1. Công nghệ tri thức Cần một kỹ sư tri thức (Knowledge Engineer): một người quen thuộc với hệ thống truy tìm thông tin (Information Retrieval –IR), hình thức hóa các quy tắc cho hệ thống, hoặc tự bản thân hoặc kết hợp với một chuyên gia trong miền ứng dụng này sẽ viết các quy tắc cho các thành phần của hệ thống IR để đánh dấu hoặc trích lọc thông tin sau khi tìm kiếm [5]. Kỹ sư tri thức sẽ phải truy cập đến một kho văn bản có kích thước vừa phải của các miền liên quan. Rõ ràng rằng các kỹ năng của kỹ sư tri thức đóng một yếu tố lớn trong mức độ thực hiện cần đạt đến của toàn bộ hệ thống. Ngoài việc đòi hỏi kỹ năng và kiến thức chi tiết của một hệ thống trích chọn thông tin cụ thể, Với cách tiếp cận này thì hệ thống hoạt động theo một chu trình. Để xây dựng một hệ thống hoạt động tốt phải luôn luôn có sự tương tác giữa người viết luật và hệ thống cùng với kho ngữ liệu huấn luyện và tập luật luôn luôn được cập nhật để cho hệ thống có thể hoạt động tốt nhất. Việc xây dựng một hệ thống thực hiện cao thường là một quá trình lặp đi lặp lại nhiều lần, nhờ vào một tập các quy tắc được viết ra, hệ thống sẽ chạy qua một tập dữ liệu văn bản được huấn luyện và đầu ra được kiểm tra xem nơi nào các quy tắc này được tạo ra. Kỹ sư tri thức sau đó tạo ra những cải biến cho các quy tắc và lặp lại quá trình. Ưu điểm: thích hợp với hệ thống làm việc một cách thủ công, phụ thuộc nhiều vào kỹ năng và kinh nghiệm của người viết ra luật. Nhược điểm: yêu cầu một chu trình kiểm tra và sửa lỗi khá là khó khăn, phụ thuộc vào rất nhiều nguồn tài nguyên ngôn ngữ như bộ từ điển phù hợp, khả năng của người viết luật. Nếu một nhân tố nào bị mất mát, hệ thống có thể trở lên không còn chắc chắn nữa. Thích hợp với những hệ thống có sẵn nguồn tài nguyên về ngôn ngữ (bộ từ điển) và con người (người viết luật), dữ liệu huấn luyện ít hoặc tốn kém, các đặc tả trích chọn thay đổi nhiều theo thời gian. 2.1.2. Huấn luyện tự động Trong hướng tiếp cận này, chúng ta không cần thiết phải có kiến thức chi tiết về việc hệ thống trích chọn thông tin xem làm việc như thế nào, hay các quy tắc được viết ra sao. Chỉ cần thiết phải có một ai đó biết một cách đầy đủ về 15 miền và công việc này để lấy được kho dữ liệu văn bản, và chú thích những văn bản phù hợp cho thông tin được trích chọn. Các chú thích này sẽ tập trung vào một khía cạnh đặc biệt của quá trình xử lý của hệ thống. Một bộ đoán nhận tên sẽ được huấn luyện bằng việc chú thích kho dữ liệu văn bản cùng với các tên phù hợp với miền liên quan. Sau khi tập dữ liệu huấn luyện phù hợp đã được chú thích, thuật toán huấn luyện được sử dụng, hệ thống sẽ sử dụng kết quả trả về phục vụ cho quá trình phân tích văn bản mới. Một cách sử dụng bộ quan hệ huấn luyện khác là để tương tác với người dùng trong suốt quá trình xử lý. Người sử dụng được phép chỉ ra liệu rằng các giả thuyết của hệ thống về văn bản có đúng không, nếu không đúng, hệ thống sẽ thay đổi các quy tắc của chính nó để điều tiết thông tin mới [5]. Hướng tiếp cận này bao gồm các hướng tiếp cận nhánh như sau: - Hệ thống học có giám sát - Hệ thống học không giám sát - Hệ thống học bán giám sát Ưu điểm: nhấn mạnh đến việc tạo dữ liệu huấn luyện. Có thể dễ dàng tạo ra được những chú thích để tạo ra bộ quan hệ huấn luyện. Miễn là ai đó quen thuộc với các miền liên quan đều có thể chú thích văn bản, hệ thống có thể được tùy biến đến một miền đặc biệt mà không cần sự can thiệp từ bất kỳ nhà phát triển nào. Ví dụ: nhận dạng tên: dễ dàng để tìm được những người có thể viết chú thích để tạo ra một số lượng lớn các dữ liệu huấn luyện. Nhược điểm: Phụ thuộc vào tập huấn luyện. Nếu việc chú thích đòi hỏi ở mức cao hơn trực giác của con người, nghĩa là đòi hỏi một sự phức tạp hay các kiến thức về chuyên môn, thì khó mà tìm ra được các chú thích, và khó có thể tạo ra dữ liệu chú thích đầy đủ cho một tập huấn luyện tốt. Thực tế rằng, việc thu thập tập dữ liệu huấn luyện với chất lượng tốt có khi khá tốn kém, hoặc việc thu thập dữ liệu huấn luyện không tốn kém về mặt thời gian và con người nhưng lại tốn kém trong giai đoạn viết các luật cho hệ thống. Thích hợp: với hệ thống không có sẵn tài nguyên về ngôn ngữ và kỹ năng của người viết luật, dữ liệu huấn luyện phong phú và không tốn kém, các bản đặc tả ổn định. Nếu bản đặc tả thay đổi theo thời gian, thì hệ thống sẽ chú thích lại tất cả những dữ liệu huấn luyện đã tồn tại bằng những đặc tả mới và sau đó huấn luyện lại. Đây là một công việc khá khó khăn. 2.2. Các phương pháp trích chọn Vì các giải thuật dựa trên luật đòi hỏi tri thức của các chuyên gia và khả năng thích ứng với các miền dữ liệu mới là hạn chế, nên luận văn sẽ tập trung 16 vào các giải thuật học máy. Phần này sẽ giới thiệu một số giải thuật học máy trong trích chọn thông tin. 2.2.1. Học có giám sát trích chọn quan hệ a. Giới thiệu: Một hướng tiếp cận thường sử dụng trong nhiều hệ thống trích chọn có giam sát là để huấn luyện hệ thống trên một tập tài liệu được gán nhẵn thủ công, dựa vào đó hệ thống có thể áp dụng các kĩ thuật máy học để sinh ra các mẫu trích chọn. Nhược điểm của phương pháp này là phụ thuộc vào tập dữ liệu được gán nhãn, bao gồm số lượng lớn các thao tác thủ công để tạo ra nó. Mục tiêu của học có giám sát là tìm hiểu một mô hình để phân loại các thể hiện một cách tự động. Học có giám sát được biết đến nhiều nhất là việc phân lớp. Ví dụ, nếu một người muốn xây dựng một hệ thống giúp ai đó mua một chiếc ô tô, nó có thể lựa chọn hãng, màu, năm sản xuất như các đặc trưng. Hệ thống phải có một danh sách các ví dụ thể hiện cùng với các giá trị riêng biệt cho mỗi đặc tính. Mỗi thể hiện sẽ được đánh giá bởi một chuyên gia và được xếp vào một lớp nào đó phục vụ để phân loại các thông tin, với bài toán mua xe ô tô, các lớp có thể là mua hoặc không mua. Với các thể hiện này, nhãn lớp đó tạo thành một tập huấn luyện để có thể được sử dụng như là đầu vào cho một chương trình học có giám sát. Học có giám sát có thể được dùng để học các mẫu từ tập huấn luyện (dưới dạng một tập tài liệu được gán nhãn) mà không cần sự trợ giúp của con người. Tuy nhiên, thành công của hệ thống lại phụ thuộc vào độ tin cậy của dữ liệu huấn luyện. Mặc dù học có giám sát tiết kiệm nhiều thời gian của các chuyên gia, nhưng chi phí ẩn cho việc gán nhãn của tập huấn luyện thì lại rất lớn. b. Hệ thống AutoSlog AutoSlog [18] là một hệ thống cấu trúc từ điển, sinh ra các mẫu trích chọn một cách tự động sử dụng các luật heuristic trên một miền chuyên biệt nào đó. AutoSlog sử dụng thuật toán học có giám sát, sử dụng tập tài liệu đã được chú thích trong đó danh sách các cụm từ cần được trích chọn phải được gán nhãn, coi đây như đầu vào của thuật toán (Ví dụ, trong miền khủng bố, các cụm danh từ chỉ thủ phạm, mục tiêu, nạn nhân có thể được gán nhãn). Ví dụ một câu đã được gán nhãn: “It was officially reported that a policeman nạn nhân was wounded today when urban guerrillas attacted the guards at a power substation thủ phạm nạn nhân located in downtown San Salvador.” địa điểm 17 Hoạt động của hệ thống AutoSlog được mô tả trong hình 3. Hình 3: Sơ đồ hoạt động của hệ thống AutoSlog Cho một cụm danh từ đã được gán nhãn và một đoạn văn bản nguồn, AutoSlog đầu tiên sẽ xác định câu chứa cụm danh từ trên. Nếu có nhiều hơn một câu và việc chú thích không chỉ ra cái nào là thích hợp thì AutoSlog sẽ lựa chọn câu đầu tiên. AutoSlog sẽ gọi bộ phân tích câu được gọi là CIRCUS để xác định các biên mệnh đề và các thành phần ngữ pháp. AutoSlog cần duy nhất một phân tích cú pháp nông để nhận diện chủ ngữ, động từ, đối tượng trực tiếp, và các cụm giới từ của mỗi mệnh đề, vì thế bất kì phân tích nào đều có thể được sử dụng. AutoSlog sử dụng tập các luật heuristic, tập các luật này được lắp vào cho câu đã xác định ở trên, những luật nào phù hợp sẽ sinh ra các mẫu trích chọn trên cơ sở các từ đặc trưng trong câu. Trong hầu hết các trường hợp, họ giả sử rằng động từ quyết định vai trò. Các luật nhận dạng vài dạng thức của động từ như chủ động, bị động, nguyên thể. Tập các luật heuristics được trình bày trong bảng 1. Ví dụ, có câu “Luke Johnson was killed in Iraq by insurgents.”. Giả sử rằng Luke Johnson được gán nhãn như một nạn nhân liên quan, AutoSlog phân tích câu đó và nhận dạng Luke Johnson như một chủ thể. Các luật chủ thể heuristic được kiểm tra và nhận thấy duy nhất luật #1 passive – verb phù hợp với mệnh đề trên. Luật này được so khớp với các từ chuyên dụng trong câu đó để tạo ra mẫu trích chọn was killed. Mẫu này sẽ được sử dụng để trích chọn cụm danh từ ở bất kì nơi nào mà động từ killed xuất hiện trong cấu trúc bị động và chủ thể của nó sẽ được trích chọn như một nạn nhân. 18 Tương tự, nếu insurgents được gán nhãn là thủ phạm, AutoSlog sẽ sinh ra mẫu was killed by dựa trên luật #12. Mẫu này sẽ sinh ra tất cả các cụm danh từ đi sau giới từ by và gắn với dạng thức bị động của động từ killed. Mẫu luật heuristic Các mẫu học được từ các luật 1 passive-verb was murdered 2 active-verb bombed 3 verb infinitive attempted to kill 4 aux noun was victim 5 Passive-verb Killed 6 Active-verb Bombed 7 Infinitive To kill 8 Verb infinitive Tried to attack 9 Gerund Killing 10 Noun aux Fatality was 11 Noun preposition Bomb against 12 Passive-verb preposition Killed with 13 Active-verb preposition Was aimed at Bảng 1: Các luật của AutoSlog Tuy nhiên các luật heuristic của AutoSlog không được hoàn hảo, dẫn đến việc tạo ra một số các mẫu không mong muốn. Do đó con người phải xem xét lại các mẫu được sinh ra, quyết định xem mẫu nào sẽ được giữ lại để phục vụ cho quá trình trích chọn sau này. 2.2.2. Học không giám sát trích chọn quan hệ a. Giới thiệu: Với số lượng gần như vô hạn của văn bản không có nhãn có thể truy cập vào các trang web và các nguồn khác, các phương pháp học không giám sát có thể khai thác văn bản không được chú thích làm cho nó trở lên có giá trị, giảm bớt chi phi cho việc chú thích, gán nhãn cho tài liệu như ở phương pháp học có giám sát. Hướng tiếp cận cơ bản của học không giám sát bao gồm các bước. Thứ nhất, các hệ thống học không giám sát được bắt đầu với một số mẫu hoặc sự kiện đã được gán nhãn. Sau đó, hệ thống sẽ tìm kiếm trên tập dữ liệu lớn chưa được chú thích để tìm các mẫu tiềm năng trên cơ sở các mẫu ban đầu. Sau khi các mẫu mới được tìm thấy, hệ thống có thể sử dụng chúng để khai phá thêm các sự kiện bổ xung. Hệ thống sẽ thêm các sự kiện đó vào tập hạt giống. Sau đó, 19 hệ thống được huấn luyện lại dựa trên tập hạt giống mở rộng mới. Quá trình này lặp cho đến khi không còn mẫu nào được tìm thầy nữa. b. AutoSlog – TS AutoSlog – TS [18] là sự mở rộng của AutoSlog, không đòi hỏi việc gán nhãn, tự động sinh các mẫu trích chọn cho mọi cụm danh từ. Thay vào đó, AutoSlog TS học từ hai tập văn bản không được gán nhãn: một tập liên quan đến miền quan tâm, một tập không liên quan đến miền. Ví dụ, nếu một hệ thống muốn học các mẫu trích chọn cho miền khủng bố, người dùng sẽ cung cấp một tập văn bản mô tả các sự kiện khủng bố và một tập không liên quan các sự kiện khủng bố. AutoSlog – TS tạo ra mọi mẫu có thể trong tập văn bản, sau đó tính toán thống kê dựa trên tần xuất xuất hiện của mỗi mẫu trong tập các văn bản liên quan so với tập các văn bản không liên quan. Sau đó hệ thống sẽ tạo ra một danh sách xếp hạng các mẫu trích chọn được cùng với số liệu thống kê để chỉ ra mẫu nào hỗ trợ nhiều nhất với miền đang xét. AutoSlog TS sử dụng tập gồm 15 luật heuristic, bao gồm 13 luật của AutoSlog ở bảng 1, cộng thêm 2 mẫu heuritic mới: active-verb dobj ( attacked embassy); infinitive preposition (to sell for ). Hai mẫu thêm vào này được tạo ra cho các miền kinh doanh từ các kinh nghiệm đã có. Hình 4: Sơ đồ hoạt động của hệ thống AutoSlog – TS Hoạt động của hệ thống AutoSlog được thể hiện trong hình 4. 20  Giai đoạn 1: + phân tích ngữ pháp để xác định các cụm danh từ + với mỗi cụm danh từ, các luật heuristic sinh ra các mẫu (gọi là các nút khái niệm - concept node trong CIRCUS) + có thể sinh ra các luật phức tạp. Giả sử có câu “terrorists bombed the US embassy”, và cụm danh từ terrorists đã được gán nhãn thủ phạm thì cả luật active-verb và active-verb dobj đều được áp dụng vào  Ta có các mẫu được sinh ra là: bombed bombed embassy Giai đoạn này tạo ra một số lượng lớn các mẫu trích chọn, đến hàng chục nghìn mẫu riêng biệt, các mẫu này có khả năng trích chọn mọi cụm danh từ trong tập tài liệu.  Giai đoạn 2: Tiến hành quá trình huấn luyện tập dữ liệu lần 2 sử dụng các mẫu trích chọn mới. Với mỗi mẫu trích chọn được, AutoSlog TS sẽ tính toán hai giá trị tần xuất: total_freqi là số lần xuất hiện của mẫu thứ I trong toàn bộ tập tài liệu, và rel_freqi là số lần xuất hiện của mẫu thứ I trong tập tài liệu liên quan. Sau đó hệ thống sẽ tính toán giá trị thống kê: freqtotal freqrel)patterns|relevantPr( i i i    Sau đó, hệ thống xếp hạng các mẫu theo thứ tự độ quan trọng trong miền theo công thức: )patterns|relevantPr(*)freq_rel(log)pattern(FlogR iii 2 Hình 5 chỉ ra một số ví dụ về đầu vào và đầu ra của AutoSlog TS. Relevant Text CNN reported that three people died today in Bogota in a terrorist event. Armed guerrillas shot 3 judges with a machine gun. They died in an attack at the court house. The FMLN claimed responsibility for the death of the judges and claimed that the death of more judges would soon follow. Irrelevant Text The Los Angeles Times reported that Marlon Brando died today in California. Marlon Brando died at the UCLA Hospital at the age of 80. Sources claimed that he had been diagnosed with pulmonary fibrosis.  Total_Freq Rel_Freq Prob RlogF Pattern 4 3 0.750 1.189 died in 2 2 1.000 1.000 death of 21 3 2 0.667 0.667 claimed 4 2 0.500 0.500 died 1 0 0.000 0.000 was diagnosed with 1 0 0.000 0.000 was diagnosed 1 0 0.000 0.000 age of 1 1 1.000 0.000 follow 1 1 1.000 0.000 responsibility for 1 1 1.000 0.000 claimed 1 1 1.000 0.000 claimed responsibility 3 1 0.333 0.000 died at 1 1 1.000 0.000 shot with 1 1 1.000 0.000 shot 1 1 1.000 0.000 shot judges 1 1 1.000 0.000 shot 2 1 0.500 0.000 reported Hình 5: Ví dụ về AutoSlog - TS 2.2.3. Học bán giám sát trích chọn quan hệ Những hướng tiếp cận trước đây chủ yếu là học có giám sát. Hướng tiếp cận này khó khăn ở chỗ cần phải có ngữ liệu đã được gán nhãn hỗ trợ quá trình học. Brin đã đưa ra phương pháp lặp tương hỗ (bootstrapping) cho việc trích chọn quan hệ [3]. Kĩ thuật này nhận đầu vào là một tập nhỏ các hạt giống (seed) của một mối quan hệ cụ thể đã được xác định trước, từ đó tiến hành cho học để trích xuất ra một tập các mẫu quan hệ ngữ nghĩa và tiến hành sinh thêm các quan hệ mới. Kết quả thu được là một tập dữ liệu lớn biểu diễn mối quan hệ được quan tâm. Hướng tiếp cận này cần một tập dữ liệu hạt giống nhỏ ban đầu. Và nó cũng không rõ ràng trong việc xây dựng tập khởi đầu này như thế nào, chọn lựa dữ liệu ra sao, số lượng bao nhiêu là đủ. Sử dụng phương pháp học bán giám sát, một hệ thống có thể học từ việc pha trộn giữa dữ liệu có gán nhãn và dữ liệu không được gán nhãn. Trong nhiều ứng dụng thì đó là một tập nhỏ dữ liệu được gán nhãn cùng với tập lớn dữ liệu không được gán nhãn. Không tốt khi sử dụng chỉ một tập nhỏ dữ liệu được gán nhãn để huấn luyện hệ thống bởi tỉ lệ giữa số lượng các ví dụ huấn huận với số lượng các đặc trưng là nhỏ, kết quả huấn luyện sẽ không chính xác. Vì thế, hệ thống cần kết hợp giữa dữ liệu có gán nhãn và dữ liệu không gán nhãn trong suốt quá trình huấn luyện để cải thiện việc thực hiện. 22 Hệ thống có thể trích chọn các mẫu từ dữ liệu đã được gán nhãn, và gán nhãn các dữ liệu chưa được chú thích một cách tự động bằng việc sử dụng các mẫu. Và kết quả, tất cả các dữ liệu sẽ được gán nhãn trong khi huấn luyện. 2.2.3.1. DIPRE: Dual Iterative Pattern Relation Extraction Segrey Brin đã đưa ra một ý tưởng là rút trích ra các cặp (title, author) của cuốn sách. Đặc điểm của cặp được rút trích này là chúng có quan hệ với nhau – tên sách và tên tác giả viết cuốn sách. Ví dụ: cặp (The Comedy of Errors, W.Shakespeare) thể hiện quyển sách The Comedy of Errors do W.Shakespeare viết ra. Điểm nổi bật trong nghiên cứu này là thuật toán DIPRE, một kỹ thuật trích chọn các quan hệ cùng với việc tạo để sử dụng tính đối ngẫu của mẫu – quan hệ. D = một CSDL lớn thông tin không có cấu trúc như là www R = r1, ….rn là các quan hệ đích. Một bộ dữ liệu t, của R xuất hiện một hoặc nhiều lần trong D, là một quan hệ. Ví dụ trong [3], tập quan hệ đích R là bảng chứa các cặp (author, title). Tính đối ngẫu giữa mẫu và quan hệ: từ một tập các mẫu tốt, ta có thể xây dựng một tập các bộ quan hệ tốt. Ngược lại, chúng ta mong muốn đưa ra một tập các bộ quan hệ tốt, chúng ta có thể xây dựng một tập các mẫu tốt. Giải thuật DIPRE làm việc theo mô tả trong hình 6. Hình 6: Mô hình hoạt động của hệ thống DIPRE Quy trình rút trích dựa theo thuật toán DIPRE: 1. Lấy R’ là một tập nhỏ của tập quan hệ đích (danh sách 5 quyển sách với tác giả). 2. O  FindOccurrences(R’; D): thủ tục tìm sự xuất hiện của các cặp quan hệ hạt giống của R’ trong tập D. Là đoạn văn bản chứa đồng thời tên tác giả và tiêu đề của quyển sách trong văn bản (sự kiện chứa tên tác giả và tên sách). Với bộ quan hệ tìm được, giữ ngữ cảnh xung quanh tên tác giả và tên sách (url và văn bản xung quanh). 3. P  GenPatterns(O): Sinh các mẫu từ các sự kiện đã tìm được Initial Seed Tuples Occurrences of Seed Tuples Generate Extraction Patterns Generate New Seed Tuples 23 Thủ tục này phải sinh ra các mẫu cho các tập sự kiện cùng với ngữ cảnh tương tự. Các mẫu cần phải có tỉ lệ lỗi thấp. Tỉ lệ bao phủ càng cao càng tốt. 4. R’ MD(p): Tìm kiếm CSDL cho bộ quan hệ phù hợp với bất kỳ mẫu nào. 5. Nếu R’ đủ lớn thì dừng, không thì trở lại bước 2. a. Quy ước  Bộ quan hệ: cặp (title, author). Ví dụ: cặp (The Robots of Dawn, Issac Asimov) là một bộ quan hệ.  Một sự kiện là một bộ - 7: (author, title, order, url, prefix, middle, suffix) Trong đó; + url là url của tài liệu chứa cặp (title, author) + Prefix: gồm m ký tự đứng trước author (hoặc title nếu title đứng trước) + Middle: là phần văn bản nằm giữa author và title + Suffix: gồm m ký tự đứng sau title (hoặc author) Ví dụ: Cho cặp quan hệ (Charles Dickens, Great Expectations), trong miền www.books.com có đoạn thể hiện “The famous writer Charles Dickens wrote Great Expectations book” thì tương ứng ta có sự kiện: (The famous writer, Charles Dickens, wrote, Great Expectations, book, true, www.books.com/TopRated).  Mẫu là một bộ - 5: (order, urlprefix, prefix, middle, suffix) Trong đó: + Order có giá trị Boolean, chỉ thứ tự xuất hiện của author và title trong câu, + Các phần tử còn lại là một chuỗi ký tự. Ví dụ: Mẫu có dạng title by author ( , thì: + Order = true + Urlprefix = www.books.com + Prefix = + Middle = by + Suffix = (  Một cặp (title, author) được trích chọn nếu có một URL trên web hợp với urlprefix* và nội dung của nó có chứa đoạn hợp với biểu thức chính quy “*prefix, author, middle, title, suffix*”, đồng thời khi đó biến order = true. Biểu thức chinh quy cho author và title lần lượt là: [A-Z][A-Za-z .,&]5;30[A-Za-z.] [A-Z0-9][A-Za-z0-9 .,:'#!?;&]4;45[A-Za-z0-9?!] 24 b. Bộ quan hệ ban đầu Title Author The Robots of Dawn Issac Asimov Startide Rising David Brin Chaos: Making a New Science James Gleick Great Expectations Clarles Dickens The Comedy of Errors W. Shakespeare Bảng 2: Năm bộ quan hệ hạt giống của hệ thống DIPRE c. Tìm các sự kiện dựa trên tập bộ quan hệ ban đầu Ở công đoạn này, hệ thống cần trải qua hai lần lọc fgrep: fgrep author và fgrep title. Lần thứ nhất tìm các dòng tương ứng với author hợp lệ, lần thứ hai tìm các dòng tương ứng với Title hợp lệ. Sau đó kiểm tra sự phù hợp giữa author và title này trên một dòng, nhận dạng chúng rồi đưa ra các sự kiện tương ứng.  www.sff.net/locus/c3.html --> có sự kiện: The Robots of Dwan by Isaac Asimov (Bantam Spectra, Jan ’90)  www.sff.net/locus/c5.html --> có sự kiện: Startide Rising by David Brin (Pulphouse, Jul ’90)  --> có sự kiện Foundation by Isaac Asimov (1951)  --> có sự kiện: Nightfall by Isaac Asimov (1941) Các sự kiện mô tả theo bộ - 7 được thể hiện trong bảng 3 dưới đây. Title Author Order url Prefix Middle suffix The Robots of Dwan Issac Asimove F www.sff.net /locus/c3.ht ml by (Bantam Spectra, Jan ’90) Startide Rising David Brin F www.sff.net /locus/c5.ht ml by (Pulphouse, Jul ’90) Foundation Isaac Asimov F www.scifi.o rg/bydecade /1950.html by (1951) Nightfall Isaac Asimov F www.scifi.o rg/bydecade /1940.html by (1941) Bảng 3: Ví dụ các sự kiện được mô tả dưới dạng bộ - 7 25 d. Sinh ra các mẫu *Thủ tục sinh ra một mẫu GenOnePattern(O) 1. Xác minh các thành phần order và middle của tất cả các thể hiện có trùng nhau không. Nếu không, không thể sinh ra các mẫu phù hợp với tất cả chúng. Gán giá trị cho outpattern.order và outpattern.middle tương ứng là order và middle. 2. Tìm tiền tố chung dài nhất của tất cả các url. Giá trị của outpattern.urlprefix chính là tiền tố này. 3. Outpattern.prefix là giá trị hậu tố chung dài nhất của tất cả các prefix. 4. Outpattern.suffix là giá trị tiền tố chung dài nhất của tất cả các suffix. Thành phần Order và Middle của các sự kiện phải giống nhau. Nếu không ta không thể sinh ra được mẫu phù hợp với tất cả các sự kiện. Outpattern.order  order Outpattern.middle  middle Outpattern.urlprefix  prefix dài nhất của các url Outpattern.prefix  suffix dài nhất của tất cả các prefix Outpattern.suffix  prefix dài nhất của tất cả các suffix Ví dụ về thủ tục sinh mẫu được thể hiện trong bảng 4. Tính đặc trưng của mẫu: Một mẫu sinh ra như trên có thể quá chung chung hoặc quá chuyên biệt. Chúng ta không quan tâm đến các mẫu quá chuyên biệt vì như vậy sẽ có rất nhiều mẫu được sinh ra, khi kết hợp chúng sẽ tạo ra quá nhiều quyển sách. Tuy nhiên một mẫu quá chung chung có khả năng không đưa ra được thực thể là tên sách. Để giải quyết vấn đề này, ta sẽ gắn mỗi mẫu với một độ đo specificity specificity(p) = |p.middle||p.urlprefix||p.prefix||p.sufix| trong đó: p.middle, p.urlprefix, p.prefix, p.sufix là middle, urlprefix, prefix, sufix của mẫu p; |s| chỉ độ dài của xâu s. Hệ thống sẽ loại bỏ các mẫu có độ specificity quá thấp, tuy nhiên specificity(P)n > t với n là số lượng các quyển sách trong các thể hiện tương ứng với mẫu P (n>1) và t là một ngưỡng nào đó. * Thuật toán sinh nhiều mẫu GenPatterns(O). 1. Nhóm tất các sự kiện o trong O theo trường order và middle. Gọi các nhóm này là O1, …, OK. 2. Với mỗi nhóm Oi, p GenOnePattern(Oi). Nếu p thoả mãn điều kiện về độ “riêng biệt” thì đưa ra p. Nếu không:  Nếu tất cả các sự kiện o trong Oi có cùng url, ta không thể mở rộng được urlprefix thì loại bỏ Oi đó. 26  Còn không, phân chia các sự kiện o trong Oi thành các nhóm nhỏ có cùng đặc tính url. Lặp lại thủ tục trên ở bước 2 cho các nhóm con. Pattern Order Urlprefix Prefix Middle Suffix F www.sff.net/locus/c* by ( F www.scifi.org/bydecade/19* by (19 … … … …  Pattern www.sff.net/locus/c* title by author ( www.scifi.org/bydecade/19* title by author (19 Bảng 4: Ví dụ về việc sinh các mẫu DIPRE 2.2.3.2. Hệ thống SNOWBALL Các tài liệu văn bản thường chứa dữ liệu cấu trúc có giá trị ẩn trong các câu tiếng Anh đơn thuần. Dữ liệu này được sử dụng tốt nhất nếu có sẵn như một bảng quan hệ, chúng ta có thể sử dụng chúng để trả lời một cách chính xác các câu truy vấn hoặc để chạy các công việc khai phá dữ liệu. Cũng dựa trên tư tưởng của DIPRE, Eugene Agichtein và Luis Gravano giới thiệu những chiến lược mới để sinh các mẫu và trích chọn các bộ quan hệ từ các tài liệu văn bản đơn giản - hệ thống Snowball, để rút trích cặp quan hệ <Organization, Location> - tên tổ chức và địa điểm [2]. Tại mỗi vòng lặp của quá trình trích chọn, Snowball đánh giá chất lượng của những mẫu và bộ quan hệ mà không cần sự can thiệp của con người, chỉ giữ lại những mẫu và bộ quan hệ tin cậy nhất cho vòng lặp kế tiếp. Một tập hợp các mục trong bài báo có thể chứa thông tin về vị trí của các trụ sở các tổ chức. Nếu chúng ta cần tìm vị trí của các trụ sở này, chúng ta cố gắng sử dụng các kỹ thuật tìm kiếm truyền thống để tìm các tài liệu chứa câu trả lời cho truy vấn của mình. Chúng ta sẽ có câu trả lời chính xác hơn nếu chúng ta có sẵn một bảng danh sách tất cả các cặp tổ chức – vị trí được đề cập trong tập tài liệu của chúng ta. Một bộ trong bảng chỉ trụ sở của tổ chức Organization là vị trí Location. Hệ thống Snowball dựa trên ý tưởng DIPRE: trích chọn quan hệ cấu trúc (bảng) từ tập các tài liệu HTML. Phương pháp này hoạt động tốt nhất trong môi trường giống như WWW, các bộ quan hệ dạng bảng được trích chọn có xu hướng xuất hiện các ngữ cảnh lặp lại trong tập tài liệu. Snowball khai thác các 27 cấu trúc giảm bớt và vốn có trong tập hợp để trích chọn được quan hệ đích với tập huấn luyện nhỏ nhất từ người dùng, thêm vào đó người dùng có thể cung cấp thêm một biểu thức chính quy mà các thực thể phải phù hợp. Snowball tìm các thể hiện của cặp trong các tài liệu văn bản. Sau đó Snowball sẽ kiểm tra ngữ cảnh xung quanh bộ quan hệ ban đầu. Ví dụ từ câu “computer servers at Microsoft’s headquarters in Redmond” để xây dựng lên một mẫu có dạng ‘s headquarters in . Hình 7: Mô hình hoạt động của hệ thống Snowball Mô hình hoạt động của hệ thống Snowball được thể hiện trong hình 7. Xuất phát từ bộ quan hệ huấn luyện ban đầu, tìm các sự kiện liên quan, sinh các mẫu và trích chọn bộ quan hệ từ các tài liệu văn bản, đánh giá chất lượng của mẫu và bộ quan hệ được sinh ra tại mỗi vòng lặp của quá trình trích chọn, chỉ các mẫu và bộ quan hệ thật sự tin cậy mới được giữ lại cho Snowball dùng cho lần lặp tiếp theo của hệ thống. Snowball cũng có thêm chiến lược đánh giá chất lượng của mỗi mẫu và cặp quan hệ, nếu cái nào đủ tin cậy thì mới được sử dụng cho các vòng lặp tiếp theo. Việc sinh và lọc các mẫu và bộ quan hệ cải thiện chất lượng của các bảng được trích chọn một cách đáng kể. Tuy nhiên Snowball cần đến sự hỗ trợ của NER. Hệ thống Snowball độc đáo với cách biểu diễn pattern mềm dẻo, cộng với sự hỗ trợ của NER nên có kết quả thu được tốt nhất. a. Bộ quan hệ hạt giống MICROSOFT REDMOND EXXON IRVING IBM ARMONK BOEING SEATTLE INTEL SANTA CLARA Bảng 5: Năm bộ quan hệ hạt giống của hệ thống Snowball b. Tìm các sự kiện liên quan Dựa vào bộ quan hệ hạt giống ban đầu ta có thể tìm được các sự kiện liên quan như sau. Với mỗi cặp , Snowball tìm các mẩu tin Initial Seed Tuples Occurrences of Seed Tuples Tag Entities Generate Extraction Patterns Generate New Seed Tuples 28 trong tập các tài liệu chứa Organization và Location xuất hiện gần nhau, phân tích văn bản để kết nối Organization và Location để sinh ra các mẫu. Ví dụ các sự kiện tìm được dựa vào các bộ quan hệ hạt giống được thể hiện trong hình 8. Hình 8: Các sự kiện tìm được dựa vào bộ quan hệ hạt giống c. Gắn các thực thể có tên Sự cải thiện so với DIPRE là các mẫu Snowball có thêm các thẻ gắn các thực thể được đặt tên. Ví dụ từ sự kiện 2 như trên ta có thể đưa ra mẫu có dạng - based . Tuy nhiên mẫu này không phải phù hợp với bất kỳ cặp chuối ký tự nào được liên kết bởi – based, ví dụ: a producer of apple-based jelly. chỉ phù hợp với những chuỗi được xác định thuộc loại Location. chỉ phù hợp với những chuỗi được xác định thuộc loại Organization. Các thực thể trong các tài liệu văn bản được xác định loại tên, hệ thống sẽ bỏ qua các thực thể không mong muốn, chỉ tập trung vào các mẩu tin chứa thực thể Location và Organization, và phân tích ngữ cảnh bao quanh mỗi cặp của các thực thể như vậy để kiểm tra xem họ được kết nối bởi cụm từ mong muốn và do đó sẽ phù hợp với các mẫu. d. Sinh các mẫu ĐN1: Một mẫu Snowball là bộ 5: trong đó tag1 và tag2 là các thẻ thực thể được gắn tên; left, middle, right là các véctơ cùng với trọng số (0  1) của các thuật ngữ. Trọng số này chỉ sự quan trọng của mỗi thuật ngữ trong ngữ cảnh tương ứng. Ví dụ một mẫu trong Snowball: },LOCATION, {, }, ORGANIZATION,{}> Sau khi xác định 2 thực thể tag1 và tag2, Snowball tạo 3 vectơ lS, rS, mS từ S bằng việc phân tích ngữ cảnh bên trái, phải, giữa xung quanh các thực thể đó. Với mỗi vectơ có các từ với trọng số khác không xuất hiện trong ngữ cảnh 29 tương ứng; lS, rS được giới hạn bởi m từ cách bên trái và phải của mỗi cặp thực thể (m = 10). Trọng số của mỗi thuật ngữ trong mỗi vectơ là một hàm của tần số xuất hiện của thuật ngữ đó trong ngữ cảnh tương ứng. Thông thường gán các thuật ngữ của vectơ middle cao hơn trọng số của vectơ left và right. VD: ’s headquarters in -based , * Phân cụm các sự kiện tương tự nhau: ĐN2: Độ đo sự phù hợp Match(tP, tS) giữa hai bộ tP và ts trong đó: tP=< lP, t1, mP, t2, rP > với 2 thẻ t1, t2 và tS = với 2 thẻ t1’ và t2’ được định nghĩa là:      0 SPSPSP SP r.rm.ml.l )t,t(Match Snowball sinh ra các bộ 5 cho mỗi sự kiện xuất hiện trong tập hợp, sau đó phân cụm các bộ này sử dụng thuật toán phân cụm đơn giản, sử dụng hàm Match phía trên để tính toán sự tương tự giữa các vectơ và ngưỡng sim. Mẫu cuối cùng được sinh ra bằng việc lấy các phần tử đại diện của các cụm. Mẫu mới  SSS rtmtl ,,,, 21 Ví dụ ta có hai bộ quan hệ trong một cụm như sau: 1 - , }, ORGANIZATION, { <central 0.5> }, LOCATION, {}> 2 - , }, ORGANIZATION, { }, LOCATION, {}> Tương ứng ta có mẫu Snowball: , LOCATION, {}> 2.5.2.5. Sinh các bộ quan hệ mới Sử dụng các mẫu vừa sinh ra, quét trên toàn bộ tập hợp để lấy ra những bộ quan hệ mới. Thủ tục sinh bộ quan hệ mới từ các mẫu là: Sub GenerateTuples(Patterns) For each text_segment in corpus (1) {;} = CreateOccurrence(text_segment); tC = ; SimBest = 0; For each p in Patterns 30 (2) sim = Match(; p); if (sim >= sim) (3) UpdatePatternSelectivity(p, TC); if(sim >= SimBest) SimBest = sim; PBest = p; if(SimBest >= sim) CandidateTuples[TC].Patterns[PBest] = SimBest; return CandidateTuples; Đầu tiên Snowball xác định các câu chứa các thẻ organization và location. Từ những mẩu tin văn bản chứa cặp , Snowball sinh ra bộ - 5 t = <lc; t1; mc; t2; rc >. Bộ được lấy ra nếu có một mẫu tP mà Match(t, tp) > = sim với sim là ngưỡng tương tự trong cụm. e. Đánh giá độ tin cậy của mẫu và bộ quan hệ Sinh ra các mẫu chất lượng là một thách thức lớn. Ví dụ hệ thống có thể sinh ra mẫu như sau: , LOCATION, {}> từ đoạn văn bản “Intel, Santa Clara, announced...” Mẫu này phù hợp với bất kì chuỗi nào bao gồm một tổ chức theo sau một dấu phẩy, theo sau là một địa điểm. Đánh giá độ tin cậy confidence của mẫu này, ta có thể thấy mẫu này mà có xu hướng tạo ra bộ quan hệ sai. Do đó ta có thể đánh trọng số cho các mẫu này dựa trên cơ sở tính chọn lọc của chúng, và tin tưởng rằng chúng sẽ tạo ra các bộ quan hệ phù hợp. Do đó, một mẫu không có tính chọn lọc sẽ được gắn trọng số thấp. Các bộ quan hệ được tạo ra bởi mẫu như vậy sẽ bị loại bỏ, trừ khi họ được hỗ trợ bởi các mẫu chọn lọc khác. Tương tự, một bộ quan hệ không tốt có thể sinh ra các mẫu xa lạ, có thể trả về các bộ quan hệ sai hơn nhiều trong lần lặp Snowball kế tiếp. Để ngăn chặn điều này, chúng ta phải giữ lại các bộ quan hệ có độ tin cậy confidence cao. Độ tin cậy của một bộ quan hệ là một hàm của tính chọn lọc và số lượng các mẫu sinh ra nó. Độ tin tưởng của một bộ quan hệ cao nếu nó được sinh ra bởi vài mẫu có tính chọn lọc tương đối cao. Sau quá trình lọc ban đầu, chúng ta sẽ loại bỏ tất cả các mẫu có độ supported nhỏ hơn Sup của bộ quan hệ ban đầu. Sau đó chúng ta sẽ cập nhật confidence của mỗi mẫu trong bước 3 của thuật toán, kiểm tra mỗi mẫu tiền năng t = được sinh bởi mẫu đó. Nếu mẫu t’ có độ tin cậy cao các bộ quan hệ sinh ra trong suốt quá trình lặp trước đó của hệ thống cho cùng một tổ chức o như trong t, thì chính hàm này so sánh vị trí l và l’. Nếu hai vị trí này giống nhau, thì bộ t được xem là một phù hợp positive của mẫu. Ngược lại, sự phù hợp là negative. 31 * ĐN3: Độ tin cậy confidence của một mẫu P là: )..( .)( negativePpositiveP positivePPconf   với P.positive là số lượng các bộ quan hệ phù hợp positive cho mẫu P và P.negative là số lượng các bộ quan hệ phù hợp negative cho P. MICROSOFT REDMOND EXXON IRVING IBM ARMONK BOEING SEATTLE INTEL SANTA CLARA Xét mẫu P = , LOCATION, {}> với các sự kiện phù hợp: 1 - Boeing, Seattle, said…  positive 2 - Intel, Santa Clara, cut prices…  positive 3 - invest in Microsoft, New York-based Negative analyst Jane Smith said…  negative  Mẫu P có độ tin cậy là conf(P) = 67.0 12 2   * ĐN4: Độ tin cậy RlogF của một mẫu P là: ConfRlogF(P) = Conf(P). log2(P.Positive) Xem xét bộ quan hệ T và tập mẫu P = {Pi} được sử dụng để sinh ra T. Giả sử ta biết xác xuất Prob(Pi) cùng với mỗi mẫu Pi sinh ra các bộ quan hệ hợp lệ.    P i iPobTob 0 ))(Pr1(1)(Pr Độ đo Conf(Pi) được thiết kế để ước lượng Prob(Pi), xác xuất của mẫu Pi sinh ra một bộ quan hệ hợp lệ. * ĐN5: Độ tin cậy của một bộ quan hệ:    P i iii PCMatchPConfTConf 1 ))),().((1(1)( với P = {Pi} là tập các mẫu sinh ra T và Ci là ngữ cảnh hỗ trợ cùng với sự kiện của T phù hợp với Pi với độ phù hợp Match(Ci, Pi) Một bộ quan hệ sẽ có độ tin cậy cao nếu được sinh ra bởi nhiều mẫu Pi có độ tin cậy cao. Sau khi tính toán độ tin cậy của các bộ quan hệ thích hợp, Snowball sẽ loại bỏ những bộ quan hệ có độ tin cậy thấp. Các bộ quan hệ này có thể gây ra sự nhiễu trong quá trình sinh các mẫu mới, có thể đưa ra những bộ quan hệ không hợp lệ, làm giảm sút sự thực hiện của hệ thống. Do đó bộ quan hệ được sử dụng 32 cho lần lặp tiếp theo là {T / Conf(T) > t} với là một ngưỡng xác định trước nào đó. Thường t = 0.8; sim = 0.6 để đánh giá cho hệ thống Snowball. 2.3. Nhận xét Cả ba loại học không giám sát, có giám sát và bán giám sát đều thể hiện được những ưu và nhược điểm riêng của mình. Đối với học có giám sát, chất lượng trích chọn của hệ thống trên những miền dữ liệu cụ thể là rất tốt, tuy nhiên chi phí đối với việc xây dựng tập dữ liệu là rất tốn kém, do đó khả năng mở rộng miền ứng dụng là khó khăn. Đối với phương pháp học không giám sát cho khả năng học với lượng dữ liệu lớn hơn và tốc độ nhanh tuy nhiên mô hình học lại phức tạp hơn học có giám sát. Trong khi đó, học bán giám sát được xem như là một phương pháp tối ưu để giảm thiểu chi phí cũng như tài nguyên xây dựng. Phương pháp này kết hợp được ưu điểm, giảm bớt những nhược điểm của phương pháp học có giám sát và học không giám sát. 33 CHƯƠNG 3. MÔ HÌNH HỌC BÁN GIÁM SÁT TRÍCH CHỌN THỰC THỂ VÀ ỨNG DỤNG Trên cơ sở phân tích ưu và nhược điểm của các phương pháp trích chọn quan hệ, luận văn đã lựa chọn phương pháp học bán giám sát trích chọn thực thể tên. Trong chương này luận văn đề xuất một mô hình trích chọn thực thể mới sau đó áp vào trích chọn tên máy ảnh kĩ thuật số. Cụ thể luận văn sẽ đề xuất một mô hình mới dựa trên thuật toán trích chọn quan hệ DIPRE. 3.1. Mô tả bài toán Cho một tập tài liệu là các văn bản dạng thô, trích chọn ra các cặp quan hệ , trong đó một bộ trong bảng chỉ ra máy ảnh “camera” do hãng “producer” sản xuất. Chẳng hạn, với cặp <DSLR- A900, Sony> có trong bảng danh sách, nghĩa là loại máy ảnh DSLR-A900 do hãng Sony tạo ra. Cụ thể, bài toán được phát biểu như sau:  Đầu vào: - Tập dữ liệu D: gồm các tệp văn bản được lấy từ các trang web liên quan đến máy ảnh. - Tập quan hệ đích R: mỗi phần tử là một quan hệ gồm một cặp <camera, producer>. Mỗi quan hệ r  R xuất hiện một hoặc nhiều lần trong tập tài liệu D. - Tập quan hệ hạt giống R’: một tập nhỏ của quan hệ đích  Đầu ra: Tập quan hệ đích R gồm tất cả các cặp xuất hiện trong tập dữ liệu D. Ví dụ, có câu “Fujifilm release FinePix Z35 digital compact” ta trích ra được một cặp quan hệ . 3.2. Mô hình giải quyết bài toán Bài toán dựa trên bài toán của Brin về việc tìm ra cặp quan hệ (tên sách, tên tác giả) của cuốn sách, đặc biệt là kỹ thuật DIPRE [3]. Cứ sau mỗi vòng lặp lại sinh ra những cặp thực thể mới và mẫu (patterns) mới. Các vòng lặp tiếp theo sử dụng kết quả của vòng lặp trước đó để thu được kết quả mới. Quá trình đó cứ tiếp tục quay vòng cho đến khi đạt được một yêu cầu đưa ra. Cụ thể:  Bước 1: Xuất phát từ các cặp quan hệ hạt giống trong R’, tìm tất cả các thể hiện là các câu chứa đồng thời tên nhà sản xuất P và tên máy ảnh C.  Bước 2: Hệ thống sẽ phân tích ngữ cảnh xung quanh các câu tìm được ở bước 1, trích chọn ra các mẫu. 34  Bước 3: Từ tập các mẫu thu được, hệ thống sẽ đối chiếu với tập dữ liệu ban đầu để kiểm tra xem chúng có thể trích chọn ra được các hạt giống mới nào không; nếu cặp chưa có trong tập quan hệ đích thì thêm cặp hạt giống mới này vào tập quan hệ đích R, coi đây là quan hệ hạt giống sử dụng cho các vòng lặp tiếp theo.  Bước 4: Quay lại bước 2 để tìm ra những hạt giống và mẫu mới cho tới khi số lượng tập quan hệ R gần như không thay đổi, hay số lượng các cặp quan hệ mới phát hiện ra thêm là rất ít. Bài toán mà luận văn đề cập đến là trích chọn cặp quan hệ tên máy ảnh – nhà sản xuất, với mỗi loại máy ảnh sẽ có một hãng sản xuất ra nó. Do vậy cách biểu diễn nó trên tài liệu sẽ có một quy luật nào đó. Nhận thấy rằng, ngữ cảnh ở giữa cặp thực thể tên máy ảnh số và nhà sản xuất thường ở một dạng nhất định, quy luật có thể lặp lại nhiều lần ở các tài liệu khác nhau. Ví dụ như: “Sony has announced the SLT A35, the latest addition to its innovative range of fixed-mirror DSLRs”, “Panasonic has announced the DMC-G3 Micro Four Thirds mirrorless interchangeable lens camera”. Cấu trúc “has announced the” có xu hướng xuất hiện nhiều lần trong các bài báo giới thiệu về các loại máy ảnh. Do đó mẫu này có khả năng dẫn đến các trích dẫn khác như: “Pentax has announced the Optio RS1500 compact camera with interchangeable, user designable covers” hay “Samsung has announced the ST93 compact camera”… Từ các cặp quan hệ mới này, ta có thể sử dụng để sinh ra các mẫu trích chọn mới. Và có một đặc điểm thuận lợi nữa để giải quyết bài toán đã đề xuất là tên các loại máy ảnh thường ở dạng kí tự in hoa, có thể bao gồm cả chữ và số; tập các hãng sản xuất máy ảnh là hữu hạn, ta có thể liệt kê một cách dễ dàng. Trong bài toán trích chọn tên máy ảnh số:  Bộ quan hệ: cặp  Một mẫu là bộ - 4: (order, tag1, middle, tag2); trong đó tag1 và tag2 là thực thể và . Order là thứ tự xuất hiện của tag1và tag2 trong câu. Middle là ngữ cảnh ở giữa giới hạn bởi tag1và tag2.  Một bộ quan hệ sẽ được trích chọn vào bảng quan hệ đích nếu có một thể hiện trong văn bản phù hợp với một trong hai biểu thức: camera middle producer hoặc producer middle camera 35 3.3. Mô hình hệ thống Hình 9: Mô hình hệ thống trích chọn tên máy ảnh số Xuất phát từ tập tài liệu HTML, sau pha tiền xử lí, ta sẽ thu được tập các câu chứa tên các hãng sản xuất máy ảnh, việc trích chọn sẽ sử dụng tập các câu này. Dựa vào 5 quan hệ hạt giống ban đầu, hệ thống sẽ tiến hành tìm kiếm các câu chứa đồng thời tên hãng sản xuất và tên máy ảnh trong bộ quan hệ hạt giống, phân tích ngữ cảnh xung quanh các bộ quan hệ, sinh ra các mẫu, dựa vào các mẫu này, hệ thống sẽ sinh ra được các bộ quan hệ mới, đưa vào bảng quan hệ đích. Bảng quan hệ đích này lại trở thành bảng quan hệ hạt giống mới, và quá trình trích chọn lại bắt đầu ở vòng lặp mới. Mỗi vòng lặp luôn có sự đánh giá các mẫu được sinh ra để việc trích chọn ra các bộ quan hệ mới càng nhiều cáng tốt và phải bảo đảm sự chính xác cao. Quá trình trích chọn sẽ dừng lại khi không có một bộ quan hệ mới nào được sinh ra. Chi tiết mô hình hệ thống được mô tả trong hình 9. Tuy nhiên, để việc trích chọn hiệu quả, hệ thống sẽ được tích hợp thêm tập các tri thức của con người, bao gồm 2 bộ từ điển: - Tập tên các hãng sản xuất máy ảnh: P ={Canon, Casio, Concord, Contax, Cool-icam, Creative, Fujifilm, GE, Gateway, HP, Kodak, Konica, Kyocera, Minolta, Mustek, Nikon, Olympus, Panasonic, Pentax, Polaroid, Ricoh, Samsung, Sanyo, Sealife, Sharp, Sigma, Sony, Toshiba} - Tập các thuộc tính liên quan đến tên các nhà sản xuất máy ảnh: {PowerShot, EOS, Exilim, Optio, Lumix, Finepix, FineCam, DC-Cam, CoolPix, Tài liệu html Các câu chứa tên các hãng sản xuất máy ảnh Pha sinh các bộ quan hệ mới Tập các thuộc tính đi kèm với tên máy ảnh Pha tiền xử lí Tìm các sự kiện liên quan Pha sinh các mẫu Bảng quan hệ đích <camera, Tập hãng sản xuất máy ảnh 36 Digimax, DSC, Cyber-Shot, DMC, EasyShare, SD, GXR, Alpha, Tough, Stylus, IXUS, DSLR, Mju} 3.3.1. Pha tiền xử lí Hình 10: Mô hình của pha tiền xử lí Trong pha này, nhận đầu vào một tập các trang web trên một miền ứng dụng quan tâm là máy ảnh kĩ thuật số, sau quá trình xử lý hệ thống thu được một tập các câu tiềm năng có thể chứa các quan hệ cần trích chọn, chứa tên các hãng sản xuất máy ảnh đang xem xét. Công việc trích chọn sau này chỉ thực hiện trên tập các câu tiềm năng thu được sau pha này. a. Bước 1: Loại bỏ các thẻ html Trong một trang web, không chỉ chứa nội dung trang web, còn chứa các thông tin khác như dòng quảng cáo, các đường liên kết đến hình ảnh, đến các trang web khác… Tất cả các thông tin đó không phải đều có lợi cho hệ thống trích chọn. Các thông tin này thường được đánh dấu trong các thẻ html. Việc cần làm là loại bỏ các thẻ hmtl, chỉ giữa lại nội dung của các trang web. Nội dung trong các trang web thường được đánh dấu trong cặp thẻ và . Tuy nhiên tiêu đề của các bài báo thường cũng ẩn chứa những thông tin có giá trị, cụ thể trong tiêu đề của các bài báo nói về máy ảnh, thường trong đó chứa cặp quan hệ tên máy ảnh và hãng sản xuất, do đó ngoài việc giữ lại nội dung của trang web, ta cần giữ lại cả tiêu đề của các trang web đó. Đọc từng file có trong tập các trang web, với mỗi file, từng dòng được đọc, nếu dòng đó chứa thẻ bắt đầu bằng thẻ và kết thúc là thẻ hoặc nếu trong dòng văn bản đó chứa thì ghi lại nội dung chứa trong cặp thẻ đó vào file văn bản sau khi đã loại bỏ các dấu \t, chuyển các kí tự html về dạng chuẩn. Giải thuật: Đầu vào: tập các tài liệu HTML Đầu ra: tập tài liệu ở dạng trơn (plain text) B1: Loại bỏ thẻ html B2: Tách câu B3: Loại bỏ các câu không liên quan 37 void StripHTML() for each file_html in corpus_html for each line in file_html if line Contain () { RemoveTag(line); Write(file_text, line); } if (line Contain ()) or (line Contain ()) { RemoveTag(line); Write(file_text, line); } return file_text; b. Bước 2: Tách câu Việc trích chọn các loại tên máy ảnh kĩ thuật số giới hạn trong một câu, có nghĩa nếu tên hãng sản xuất và tên máy ảnh xuất hiện trong cùng một câu thì ta sẽ đưa chúng vào bảng quan hệ đích, và thông thường mỗi câu ta chỉ trích chọn một bộ quan hệ mà thôi. Do đó, khi có một tập các tài liệu, công việc đầu tiên hệ thống cần phải làm là tách các câu trong một đoạn thành các câu đơn lẻ, và việc trích chọn chỉ thực hiện trên từng câu đơn lẻ. Thông thường, trong một đoạn văn bản, các câu thường được ngăn cách bởi một trong các dấu ngắt ‘.’, ‘!’, ‘?’. Nếu chúng ta có một đoạn văn bản đưa vào một biến xâu input, cách đơn giản để cắt chúng thành các câu là ta sẽ sử dụng input.Split(‘.’, ’!’, ’?’), cách này rất hiệu quả với các tài liệu văn bản tiếng Việt. Tuy nhiên với tiếng Anh các dấu ngắt đó có thể đánh dấu kết thúc một câu nhưng cũng có thể xuất hiện giữa câu ví dụ như dấu “.” trong văn bản thường để ngăn cách hàng thập phân trong số thực, ngăn cách địa chỉ IP,... trong khi hệ thống trích chọn đang thực hiện trên tập tài liệu tiếng Anh, do đó việc sử dụng các dấu ngắt và phương thức Split để tách câu không đem lại hiệu quả thực sự. Chẳng hạn như câu: “The Coolpix P80 comes with a 10.1 MP sensor. The camera features an electronic viewfinder to allow accurate composition throughout the zoom range and also includes a large 2.7 inch monitor with anti-reflection coating and a wide viewing angle.” Nếu sử dụng phương thức Split thì kết quả trả về gồm 4 thành phần: 1. The Coolpix P80 comes with a 10 2. 1 MP sensor 38 3. The camera features an electronic viewfinder to allow accurate composition throughout the zoom range and also includes a large 2 4. 7 inch monitor with anti-reflection coating and a wide viewing angle trong khi ta cần đầu ra chỉ gồm có 2 câu: 5. The Coolpix P80 comes with a 10.1 MP sensor 6. The camera features an electronic viewfinder to allow accurate composition throughout the zoom range and also includes a large 2.7 inch monitor with anti- reflection coating and a wide viewing angle Để thực hiện việc này, hệ thống sẽ quét trên toàn bộ đoạn văn bản đầu vào, mỗi khi gặp các kí tự ngắt câu, ta cần quyết định xem liệu chúng có phải đánh dấu điểm kết thúc của câu hay không. Một đặc điểm dễ nhận ra đó là nếu một trong các dấu ‘.’, ‘!’, ‘?’ đánh dấu kết thúc câu thì liền sau chúng là một dấu cách và kí tự tiếp theo phải là một trong các kí tự in hoa. Ta sẽ sử dụng biểu thức quy tắc để tách các câu. "(?<=[A-Za-z0-9][\.\!\?])\s+(?=[A-Z])" Biểu thức này được diễn giải là: bắt bằng một nhóm các kí tự chữ hoa, chữ thường và số, tiếp theo các là kí tự dấu ngắt ‘.’, ‘!’, ‘?’, kết thúc là một dấu cách; nhóm thứ 2 bắt đầu là các kí tự viết hoa từ A đến Z. Biểu thức so khớp tất cả các chuỗi con nào có chứa các dấu ‘.’, ‘!’, ‘?’ và sau nó là một kí tự chữ hoa, nếu so khớp là đúng, kết quả trả về là một chuỗi con từ vị trí đầu câu đến trước dấu. ! hoặc ?. Giải thuật tách câu: Đầu vào: Đoạn văn bản Đầu ra: Danh sách các câu đơn trong đoạn văn bản void SplitSentences(sSourceText) sTemp = sSource Text ; if sTemp Start_with {‘A’..’Z’} and sTemp Contain {‘.’, ‘?’, ‘!’} and Next_Char in {‘A’..’Z’} splitSentences = sTemp.Split(); for each single_sentence in splitSentences { RemoveSpace(single_sentence); return single_sentence; } Để tiết kiệm không gian lưu trữ và thời gian tìm kiếm, hệ thống loại bỏ các từ dừng - những từ xuất hiện thường xuyên trong văn bản mà sự xuất hiện của nó không có ý nghĩa gì trong việc tìm kiếm và trích chọn thông tin. 39 Sau khi tách các câu, hệ thống tiến hành tách các từ trong mỗi câu, với mỗi từ vừa tách, kiểm tra xem từ đó có phải là từ dừng không, nếu đúng loại bỏ từ đó ra khỏi văn bản. Mỗi bài báo thường có những định dạng khác nhau, bài này có từ viết hoa nhưng bài kia thì không, có động từ ở dạng nguyên thể, nhưng cũng động từ đó ở bài báo khác lại ở thì bị động, chẳng hạn như “announces”, “announed”… Đặc biệt liên quan đến tên các hãng sản xuất, tên các thuộc tính kèm theo, ví dụ cặp từ “Panasonics” và “Panasonic”, hoặc “PowerShot” và “powershot” thực chất ý nghĩa của chúng đều giống nhau, nhưng cách viết khác nhau, điều này sẽ gây nhiễu cho quá trình tìm kiếm và kết quả trích chọn thường không chính xác. Hệ thống tiến hành chuyển hóa tất cả các từ trong văn bản thành các kí tự chữ thường, chuyển tất cả các thể hiện về tên máy ảnh, tên thuộc tính kèm theo về một dạng thống nhất chung, chuyển tất cả các động từ ở các thời khác nhau về dạng nguyên thể của nó. Giải thuật chuyển các từ về dạng gốc của nó: Các động từ thường có các dạng: nguyên thể, V_ed, V_ing, V_s - Nếu động từ có dạng V_s: Nếu động từ kết thúc bằng: + “sses”  “ss” caresses  caress + “ies”  “i” nếu trước nó có nhiều hơn 1 kí tự, còn lại ies  ie ties  tie skies  ski + “s”: xóa bỏ “s” nếu kí tự trước nó là một phụ âm rồi kế trước là một nguyên âm caress  caress cats  cat + “ss”, “us”: giữ nguyên - Nếu động từ có dạng V_ed hoặc V_ing: Nếu động từ kết thúc bằng: + “eed”  “ee” agreed  agree + Xóa “ed” hoặc “ing”, và sau khi xóa từ còn lại: +) kết thúc bằng: “at”, “bl”, “iz” thì thêm “e” luxuriaitng  luxuriate +) kết thúc bằng một kí tự kép khác ‘l’, ‘s’, ;z’ thì xóa một kí tự cuối hopping  hop +) là âm tiết ngắn thì thêm “e” hoped  hope 40 Giải thuật chuẩn hóa các từ về dạng gốc: Đầu vào: Một từ Đầu ra: Từ gốc của nó void Stemmer(verb) 1. k = Length(verb); if (verb[k] = ‘s’) { if (verb End_With “sses” ) k = k - 2; else if (verb End_With “ies” ) and (Length(verb) > 4) k = k - 2; else k = k - 1; else if (verb[k-1] != ‘s’) k = k - 1; } 2. if (verb End_With “eed”) k = k - 1; 3. if (verd End_With “ed”) or (verb End_With “ing”) { Remove(verb, “ed”, “ing”); k = Length(verb); if (verb End_With {at”, “bl”, “iz”}) Add(verb, “e”); else if (verb End_With double(k)) { k = k – 1; ch = verb[k]; if (ch in {“l”, “s”, “z”}) k = k + 1; } else if Is_short_word(verb) add(verb, “e”); } 3. return verb; Tuy nhiên dựa vào đặc điểm của một tên máy ảnh, ví dụ có dạng DMC- FX500, thường có dạng một chuỗi kí tự gồm các kí tự chữ cái được viết hoa, kèm theo là các kí tự số. Do đó ta dễ dàng kiểm tra được một xâu có phải là một tên máy ảnh xác định hay không, loại bỏ những trường hợp không thỏa mãn để kết quả trích chọn sẽ chính xác hơn. Nếu ta chuyển toàn bộ các kí tự về dạng chữ thường thì việc kiểm tra một chuỗi có phải là tên máy ảnh hay không sẽ khó khăn hơn, nên việc chuẩn hóa các từ về dạng chữ thường không áp dụng với tên của hãng máy ảnh, tên máy ảnh và tên các thuộc tính kèm theo máy ảnh. 41 Giải thuật loại bỏ từ dừng, chuẩn hóa các từ trong câu: Đầu vào: Một câu văn bản Đầu ra: Một câu mới loại bỏ các từ dừng, các động từ ở dạng gốc. void Token(sentence) 1. filter = ; tokens =  tokens = sentence.Split(); for each token in tokens { if (not Is_Stop_Word(token)) filter = filter  {token}; } 2. s = “”; for each token in filter { for each attribute in set_attributes { if (Lower(token) = Lower(attribute)) token = attribute; } for each producer in set_producers { if (Lower(token) contain Lower(producer)) token = producer; } if (not Check_Camera(token) and not Check_Producer(token) and not Check_Attribute(token)) Stemmer(Lower(token); s = s + token; } 3. return s; c. B3: Loại bỏ các câu không liên quan Công việc tiếp theo là tìm các câu tiềm năng, những câu có khả năng chứa các cặp quan hệ cần trích chọn. Vì số lượng tập tài liệu là khá lớn, số lượng câu sau khi tách cũng rất nhiều, trong các câu có những câu không giúp ích gì trong quá trình trích chọn. Việc trích chọn ra được bộ quan hệ đích chỉ thực hiện khi tên hãng sản xuất và tên máy ảnh đứng gần nhau trong cùng một câu, do đó ta chỉ quan tâm đến những câu nào chứa một trong các tên hãng sản xuất máy ảnh, 42 các câu còn lại ta sẽ loại bỏ khỏi CSDL, tránh mất thời gian trong việc tìm kiếm và trích chọn. Hệ thống tiến hành quét trên tất cả các câu, nếu chúng chứa một trong các tên các hãng máy ảnh có trong tập P, giữ lại các câu đó, loại bỏ các câu không thỏa mãn. Chẳng hạn ta có đoạn bài báo: “Samsung has released the TL110 and TL105 ultra compact cameras. The 14.2 megapixel TL110 (ST70 in Europe) and 12 megapixel TL105 (ST60) offer 2.7 inch LCDs, wide angle zoom lenses starting at 27mm equivalent and offer 720p HD video recording using H.264 compression. Both include scene modes such as Fisheye, Lomo and a DeFog Clear/Fog Lifting mode that claims to cut through haze to take clearer images.“, sau pha tiền xử lí, kết quả thu được là câu “Samsung release TL110 TL105 ultra compact cameras”. Giải thuật: Đầu vào: Tập các tài liệu dạng text Đầu ra: Các câu chứa tên các hãng sản xuất máy ảnh void ExploreDirectory( ) 1. set_sentences = ; paragraph = “”; 2. for each file_text in corpus_text { read_to_end(file_text, paragraph); for each single_sentence in SplitSentences(paragraph) { s = token(single_sentence); for each pro in producers if (s Contain pro) set_sentences = set_sentences  {s}; } } return set_sentences; 43 3.3.2. Pha sinh các mẫu Hình 11: Mô hình thuật toán sinh mẫu từ một bộ quan hệ a. Bước1: Sinh các mẫu Dựa vào các quan hệ trong tập hạt giống ban đầu, tìm tất cả các thể hiện chứa các quan hệ hạt giống đó, trích chọn ra các mẫu. Giả sử với một cặp quan hệ hạt giống nào đó, ta lấy toàn bộ ngữ cảnh giữa P và C đưa vào vectơ mc. Tuy nhiên ta giới hạn chỉ giữ lại những vectơ mc có độ dài không quá 5 từ. Mẫu mc nếu P đứng trước C trong câu, hoặc mc nếu P đứng sau C trong câu, được sinh ra. Bộ quan hệ Thể hiện Fujifilm release finepix Z35 digital compact Casio release EX-Z1000 firmware update  release b. Bước 2: Làm giàu tập mẫu Tuy nhiên, để việc sinh ra các bộ quan hệ mới có hiệu quả, tập các mẫu càng nhiều càng tốt. Trong bước này luận văn đề xuất sử dụng WordNet [1, 6]. WordNet là dự án từ điển đơn ngữ (tiếng Anh) thiên về ngữ nghĩa, do Princeton University phát triển. WordNet đã tạo ra một tập hợp từ vựng khá lớn, theo đó các từ được sắp xếp trong dãy của những tập hợp đồng nghĩa (synonym set viết tắt là synset), giúp cho việc xác định nghĩa của từ và để phân biệt được nghĩa đang xét với các nghĩa khác. Nguyên lí tổ chức chung của WordNet là mạng lưới quan hệ ngữ nghĩa. [Phụ lục] WordNet phân biệt giữa danh từ, động từ, tính từ, trạng từ bởi chúng theo các quy tắc ngữ pháp khác nhau. Mọi synset (tập các từ đồng nghĩa) đều chứa một nhóm các từ đồng nghĩa; ý nghĩa khác nhau của một từ được đặt vào các Tập các mẫu WordNet B2: Làm giàu tập mẫu B1: Sinh các mẫu Google B3: Thẩm định các mẫu 44 synset khác nhau. Nghĩa của một từ được trình bày bởi một danh sách các dạng thức của từ đó có thể được sử dụng để biểu thị nó. Chẳng hạn, thông tin tập đồng nghĩa của từ “introduce” được miêu tả trong WordNet như sau: The verb introduce has 10 senses (first 8 from tagged texts) 1. (22) introduce, present, acquaint -- (cause to come to know personally; "permit me to acquaint you with my son"; "introduce the new neighbors to the community") 2. (11) introduce, innovate -- (bring something new to an environment; "A new word processor was introduced") 3. (9) insert, enclose, inclose, stick in, put in, introduce -- (introduce; "Insert your ticket here") 4. (7) bring in, introduce -- (bring in a new person or object into a familiar environment; "He brought in a new judge"; "The new secretary introduced a nasty rumor") 5. (1) introduce -- (bring in or establish in a new place or environment; "introduce a rule"; "introduce exotic fruits") 6. (1) insert, infix, enter, introduce -- (put or introduce into something; "insert a picture into the text") 7. (1) introduce, bring out -- (bring before the public for the first time, as of an actor, song, etc.) 8. (1) introduce -- (put before (a body); "introduce legislation") 9. precede, preface, premise, introduce -- (furnish with a preface or introduction; "She always precedes her lectures with a joke"; "He prefaced his lecture with a critical remark about the institution") 10. inaugurate, usher in, introduce -- (be a precursor of; "The fall of the Berlin Wall ushered in the post-Cold War period") Trong đó mỗi một mục là một nghĩa (sense) của từ “introduce”. Như vậy chúng ta có thể khai thác để sử dụng WordNet vào làm giàu tập mẫu. Giả sử ta có mẫu announce , sử dụng Wordnet, tìm tất cả các từ đồng nghĩa với “announce”, giả sử là {present, declare, post, introduce, communicate, launch, inform...}. Khi đó ta có các mẫu mới: present declare post introduce communicate launch … Ở đây, hệ thống chỉ làm giàu các mẫu trong trường hợp mẫu này có độ dài bằng 1, nghĩa là mẫu chỉ là một động từ, còn các trường hợp còn lại, ta bỏ qua giai đoạn làm giàu. 45 Giả sử ta đưa vào trong WordNet một từ text nào đó, ta cần xác định tập từ đồng nghĩa của text. Trước tiên, WordNet kiểm tra xem từ đó có trong cơ sở dữ liệu WordNet không, nếu có sẽ tiến hành xác định từ loại của text. WnLexicon.WordInfo wordinfo = WnLexicon.Lexicon.FindWordInfo(text, true); Một mảng xâu chứa các từ đồng nghĩa của text sẽ được trả về dựa vào thông tin về loại từ đã xác định. string[] synonyms = WnLexicon.Lexicon.FindSynonyms(text, wordinfo.partOfSpeech, true); Việc tìm các từ đồng nghĩa có thể được thực hiện thông qua một số giao diện lập trình được WordNet cung cấp như trong bảng 6. Tên hàm Tham số Thông tin trả về findtheinfo findtheinfo_ds word syntantic category search type sense number Các kết quả tìm kiếm đã được định dạng trong bộ đệm hoặc cấu trúc dữ liệu. is_defined word pos Tìm từ word có trong từ điển với kiểu từ loại pos. morphstr morphword word pos Dạng thức cơ bản của từ word hoặc null nếu không tìm thấy bất kì sự phù hợp nào trong CSDL. bin_search word streamreader Tìm kiếm từ trong file index, trả về chỉ mục của bản ghi chứa từ đó. search() word morph pos searchtype sn Thực hiện việc tìm kiếm từ word theo loại từ pos, kiểu tìm kiếm searchtype, sử dụng MorphStr nếu morph nhận giá trị true. Trả về tất cả các ý nghĩa của từ nếu sn có giá trị bằng 0. Bảng 6: Một số lớp thường dùng trong WordNet Tuy nhiên việc xây dựng tập đồng nghĩa cho động từ gặp nhiều khó khăn do khó xác định từ đồng nghĩa. Ta thấy trong tiếng Anh, có một số động từ đồng nghĩa như begin – commence, end – terminate, buy – purchase, hide – conceal… nhưng thực chất việc dùng lẫn lộn các động từ đồng nghĩa này không phải lúc nào cũng đúng. Do đó việc thay thế một động từ nào đó bằng từ đồng nghĩa của nó không phải luôn đúng trong mọi ngữ cảnh trong văn bản. Ở đây hệ thống cần phải thẩm định xem tập mẫu vừa làm giàu liệu có khả năng sinh ra bộ quan hệ nào hay không. 46 c. Bước 3: Thẩm định các mẫu Các mẫu tiềm năng sẽ góp phần sinh ra các quan hệ đúng, chính xác. Tuy nhiên, sau thao tác làm giàu tập mẫu, sẽ có những mẫu có xu hướng tạo ra các quan hệ không chính xác, gây nhiễu cho quá trình trích chọn. Do đó, với mỗi mẫu vừa sinh ra, ta cần đánh giá độ tin cậy của mẫu đó. Các mẫu có xu hướng được sử dụng nhiều sẽ tiềm ẩn khả năng tạo ra nhiều quan hệ tiềm năng. Vì tập dữ liệu được lấy từ các trang web, nên ta sẽ sử dụng công cụ tìm kiếm Google để thẩm định các mẫu. Ví dụ với câu Pentax announce Optio E90 budget camera … tương ứng với mẫu announce , ta tra cứu cụm Pentax * Optio E90, nếu cụm từ “Pentax announce Optio E90” xuất hiện ít nhất 1 lần trong 10 kết quả tìm kiếm đầu tiên  mẫu announce được đánh giá là có tiềm năng  đưa mẫu đó vào tập các mẫu để sinh ra các cặp mới. Để lấy được các kết quả tìm kiếm khi nhập vào một khóa trong Google, hệ thống sử dụng Google Search API for.NET 0.4 alpha dựa trên Google Ajax Search API.[19] The Google Web search API cho phép chúng ta đặt kết quả tìm kiếm Google vào các trang web của mình, ta có nhúng một hộp tìm kiếm động đơn giản và hiển thị kết quả tìm kiếm bao gồm các đoạn trích dẫn và các url vào trong các trang web hoặc sử dụng các kết quả một cách sáng tạo theo nhu cầu mục đích của từng cá nhân. Hỗ trợ 8 dịch vụ tìm kiếm là: 1. Tìm kiếm web 3. Tìm kiếm video 2. Tìm kiếm tin tức 5. Tìm kiếm địa phương 4. Tìm kiếm blog 6. Các bản đồ Google Google AJAX Search API được tạo bởi nhiều lớp đối tượng: - GSearchControl - Lớp này cung cấp giao diện người sử dụng và phối hợp với một số đối tượng tìm kiếm, trong đó mỗi đối tượng tìm kiếm được thiết kế để thực hiện các công việc tìm kiếm và trả về một lớp cụ thể của kết quả (Web Search, Local Search vv.) - GSearch - Lớp cơ sở này là lớp mà từ đó tất cả đối tượng tìm kiếm kế thừa. Nó định nghĩa các giao diện mà tất cả các dịch vụ tìm kiếm phải thực hiện. - GResult - Lớp cơ sở đóng gói các kết quả tìm kiếm được tạo ra bởi các đối tượng tìm kiếm. - GsearchOptions - Lớp này thiết lập hành vi của các đối tượng tìm kiếm khi thêm vào một điều khiển tìm kiếm. 47 Hệ thống sử dụng dịch vụ tìm kiếm web, giới hạn 10 kết quả tìm kiếm đầu tiên, việc tìm kiếm trên các trang web tiếng Anh. Kết quả trả về gồm CacheUrl Content; Title; Url; VisibleUrl., tuy nhiên ta chỉ quan tâm đến các kết quả trích dẫn, do đó hệ thống chỉ giữ lại phần Content trong kết quả tìm kiếm để thẩm định các mẫu. Giải thuật sinh ra các mẫu từ bộ quan hệ nào đó trong tập các bộ quan hệ hạt giống. Đầu vào: các bộ quan hệ hạt giống , tập các câu trong CSDL Đầu ra: tập các mẫu sinh bởi void Generate_Pattern_One_Tuple(pro, cam) 1. list_pattern = ; 2. for each sentence in set_sentences if (sentence Contain ) pattern = Cut_Middle(s, pro, cam); 3. synonym = generate_synonym(pattern); for each syn in synonym string = pro + " " + syn + " " + cam; for each result in Search_google(pro + " * " + cam) if (result Contain string) list_pattern = list_pattern  {syn}; 4. return list_pattern; Tuy nhiên không phải bất kì mẫu nào được sinh ra hệ thống đều đưa vào tập mẫu của mình, chỉ có những mẫu có tiềm năng tạo ra nhiều bộ quan hệ thì mới được giữ lại. Với mỗi mẫu được sinh ra, tạm thời ta lưu vào một danh sách, đánh dấu số lượng các bộ quan hệ hỗ trợ để sinh ra mẫu đó. Kết thúc, ta sẽ kiểm tra, nếu số lượng bộ quan hệ hỗ trợ vượt qua ngưỡng sup nào đó, ta sẽ thêm mẫu đó vào tập mẫu trích chọn. Trong thực nghiệm sup có giá trị bằng 2. Do đó hệ thống loại bỏ tất cả các mẫu được hỗ trợ bởi ít hơn 2 bộ quan hệ hạt giống. Thuật toán sinh ra tất cả các mẫu dựa vào các bộ quan hệ hạt giống, chỉ giữ lại các mẫu được hỗ trợ bởi ít nhất sup bộ quan hệ. Đầu vào: Tập các bộ quan hệ hạt giống Đầu ra: Tập các mẫu tiền năng set_patterns = ; Void Generate_Pattern() 1. for each in set_tuples 48 list_pattern = generate_pattern_one_tuple(cam, pro); 2. for each pattern in list_pattern If (Count_Appear(pattern, list_pattern) >= sup ) and (not set_patterns Contain pattern) set_patterns = set_patterns  {pattern}; 3. return set_pattern; 3.3.3. Pha sinh các bộ quan hệ mới Quét tất cả các câu có chứa tên các hãng sản xuất máy ảnh, nếu câu có chứa mẫu pattern, hệ thống phân tích ngữ cảnh phía trước before, ngữ cảnh phía sau after của pattern trong câu:  Nếu before phù hợp với tên nhà sản xuất và after phù hợp với tên máy ảnh (tương ứng với thể hiện middle ) thì ta thêm cặp vào trong bảng kết quả.  Hoặc nếu before phù hợp với tên máy ảnh và after phù hợp với tên nhà sản xuất (tương ứng với thể hiện middle ) thì ta thêm cặp vào bảng kết quả đích. Thuật toán được trình bày như sau: Đầu vào: Một mẫu nào đó trong tập các mẫu đã được sinh ra ở pha trước Đầu ra: Các bộ quan hệ mới void Generate_Tuple(pattern) for each s in set_sentences if (s Contain pattern) before  copy_before(s, pattern); after  copy_after(s, pattern); 1. if Check_Camera(after) and Check_Producer(before) and after  set_tuples) set_tuples = set_tuples  {}; 2. if Check_Camera(before) and Check_Producer(after) and before  set_tuples) set_tuples = set_tuples  {}; 3. return set_tuples; Chẳng hạn với câu “Fujifilm announce introduction Finepix S1000fd” và mẫu “announce introduction” thì quan hệ ta có thể trích chọn được là <Finepix S1000fd, Fujifilm>. Hoặc với câu “Panasonic release DMC-FS25 digtal camera” và mẫu “release” thì hệ thống phải trích chọn ra được bộ quan hệ <DMC-FS25, Panasonic>. 49 Trong tập văn bản, có những thể hiện tên máy ảnh đi liền với tên hãng sản xuất, ví dụ ta có câu “Canons 40D update version 1” thì ta trích chọn được bộ quan hệ . Những thể hiện dạng này, ngữ cảnh giữa tên máy ảnh và tên hãng sản xuất là rỗng, do đó ta sẽ có thủ tục để trích chọn ra các bộ quan hệ có thể hiện hoặc thể hiện . Để thực hiện việc này, hệ thống sẽ kiểm tra tất cả các câu thu được sau pha tiền xử lí, với mỗi tên hãng sản xuất producer máy ảnh:  Lấy ngữ cảnh bên phải after của nó (tương ứng với thể hiện )  Hoặc lấy ngữ cảnh bên trái before của nó (tương ứng với thể hiện ) Sau đó kiểm tra liệu after hoặc before có khả năng là tên một loại máy ảnh hay không, nếu đúng, đưa cặp hoặc vào tập quan hệ đích. Giải thuật: Đầu vào: Tập các câu tiền năng chứa tên các hãng máy ảnh Đầu ra: Các bộ quan hệ sinh bởi mẫu void Generate_Empty_Tuple(); for each s in set_sentences for each producer in set_producers after  copy_after(s, producer); 1. If (Check_Camera(after) and after  set_tuples) set_tuples = set_tuples  {}; 2. else If (Check_Camera(before) and before  set_tuples) set_tuples = set_tuples  {}; 3. return set_tuples; 50 CHƯƠNG 4. THỰC NGHIỆM 4.1. Môi trường thực nghiệm Thực nghiệm được tiến hành trên máy PC có cấu hình phần cứng như bảng 7. Công cụ phát triển là ngôn ngữ C#, cụ thể được liệt kê trong bảng . Ngoài ra còn sử dụng một số thư viện chẳng hạn như thư viện truy cập WordNet bằng giao diện C#, công cụ truy vấn Google như liệt kê trong bảng 9. Thành phần Chỉ số Bộ xử lí Intel(T) Core™2 Dual T5870 @ 2.00GHz Bộ nhớ trong 2GB Ổ cứng 80GB Hệ điều hành Microsoft Windows XP2 Bảng 7: Cấu hình của máy PC dùng trong thực nghiệm STT Tên phần mềm Tác giả Nguồn 1 Visual studio 2008 Microsoft Corporation 2 WordNet 2.1 Princeton University Bảng 8: Các công cụ sử dụng trong thực nghiệm STT Tên thư viện Tác giả Nguồn 1 WordNet.Net Troy Simpson, Malcolm Crowe 2 Google Search API for.NET 0.4 alpha for-dotnet/ #Google_Search_API_for _.NET_0.4_alpha Bảng 9: Các thư viện sử dụng trong thực nghiệm 4.2. Dữ liệu thực nghiệm Dữ liệu dùng trong thực nghiệm được lấy từ hai địa chỉ, nơi chứa nhiều thông tin liên quan đến máy ảnh kĩ thuật số, đó là: 1. 2. Dữ liệu thực nghiệm được chia thành 2 tập:  Tập 1200 (tập kiểm thử) bao gồm 1263 trang web, chuyển các trang này thành các tài liệu, sau đó tiến hành gán nhãn bằng tay. Tập dữ liệu này được dùng để đánh giá chất lượng giải thuật.  Tập 5000 bao gồm 4934 trang web, cũng tiến hành chuyển các trang này thành các tài liệu dạng thô. Tập này dùng để sinh ra tập 51 các mẫu trích chọn, sau đó áp dụng tập mẫu này vào tập 1200 để sinh ra các bộ quan hệ trong tập 1200. Thông tin chi tiết về hai tập dữ liệu này được liệt kê ở trong bảng 10. Dữ liệu Nguồn Số lượng 587 Tập 1200 676 2016 Tập 5000 2918 Bảng 10: Dữ liệu kiểm thử và dữ liệu huấn luyện 4.3. Đánh giá hệ thống Hệ thống được đánh giá chất lượng qua các độ đo: Precision (độ chính xác) và Recall (độ hồi tưởng) và F1 được tính theo công thức dưới đây: oducedPr_Answers Answers_CorrectPrecision  Correct_Possible_Total Answers_CorrectcallRe  callReecisionPr callRe*ecisionPr*F   2 1 Để thẩm định các cặp quan hệ được tạo ra, luận văn tạo ra một file kết quả, chứa tất cả các cặp quan hệ có thể được tạo ra trong tập dữ liệu kiểm thử - tập 1200, từ đó so sánh với các cặp quan hệ do hệ thống trích chọn, tính toán được giá trị Precision, Recall và F1 qua các vòng lặp. 4.4. Thực nghiệm FinePix A345 Fujifilm NX10 Samsung PowerShot S3IS Canon PowerShot SD780 Canon DSC-T30 Sony Bảng 11: Tập các quan hệ hạt giống ban đầu Thực nghiệm 1 Thực nghiệm thứ nhất chúng tôi tiến hành trên tập dữ liệu kiểm thử (Tập 1200). Bắt đầu với 5 quan hệ ở bảng 11, hệ thống tạo ra được 10 mẫu. Trong 10 mẫu này chúng tôi chỉ giữ lại các mẫu được hỗ trợ bởi ít nhất 2 cặp quan hệ hạt giống, và dùng các mẫu này để trích chọn các cặp quan hệ mới. Các mẫu rút trích được trong lần lặp đầu tiên là: post firmware update release firmware update 52 Tại vòng lặp đầu tiên sử dụng các mẫu vừa được tạo cùng với mẫu và , hệ thống sinh ra được 457 cặp quan hệ mới, trong đó có 415 cặp quan hệ chính xác trên tổng số 746 cặp quan hệ có thể lấy ra được từ tập CSDL ban đầu. Một số cặp quan hệ được trích chọn ở vòng lặp đầu tiên được liệt kê trong bảng 12. Tên hãng sản xuất Tên máy ảnh Nikon CoolPix S230 Fujifilm FinePix JZ500 Pentax Optio RS1000 Nikon CoolPix L110 Olympus FE-5010 Panasonic Lumix ZS1 Olympus C8080 Olympus SP-800UZ Kodak DC215 Canon EOS 500D Canon 430EX Sony TRV30 Kodak DVC325 Nikon CoolPix S8100 Canon S600 Kodak EasyShare CX6230 Nikon CoolPix S630 Nikon CoolPix 900 Bảng 12: Một số cặp ở lần lặp đầu tiên Từ vòng lặp thứ 4, số lượng cặp quan hệ được tạo ra không thay đổi. Giá trị của Precision và Recall, F1 qua mỗi vòng lặp được chỉ ra ở bảng 13. Số lần lặp Precision Recall F1 1 90.81 55.93 69.22 2 87.32 81.67 84.40 3 85.87 86.79 86.33 4 85.36 87.20 86.27 Bảng 13: Giá trị Precision, Recall và F1 sau các vòng lặp Hướng tiếp cận của hệ thống xuất phát từ các mẫu có độ hồi tưởng thấp, độ chính xác cao, kết hợp các tri thức để lọc kết quả. Ở vòng lặp đầu tiên, tuy rằng số lượng các cặp quan hệ trích chọn được còn ít (457 trên tổng số 746 bộ quan hệ), nhưng độ chính xác của các bộ quan hệ đó lại khá cao (khoảng 90%), 53 do đó kết quả nhận được có giá trị độ hồi tưởng thấp. Tại các vòng lặp tiếp theo, số lượng các bộ quan hệ trích chọn được tăng dần, tuy nhiên độ chính xác lại có xu hướng giảm dần. Từ vòng lặp số 4, số lượng các bộ quan hệ mà hệ thống trích ra được không thay đổi, lúc này giá trị độ hồi tưởng đã vượt quá 87%, còn giá trị độ chính xác dao động quanh khoảng 85%. Biểu đồ mô tả độ chính xác và độ hồi tưởng được trình bày ở hình 12. 50 55 60 65 70 75 80 85 90 95 1 2 3 4 Số lần lặp % Precision Recall F1 Hình 12: Giá trị của Precision, Recall, F1 thực nghiệm trên tập 1200 Hệ thống trích chọn còn sử dụng một tham số là sup để đánh giá độ chất lượng của các mẫu được sinh ra, hệ thống chỉ sử dụng các mẫu được sinh bởi từ sup bộ quan hệ hạt giống trở lên. Bảng 14 phía dưới thể hiện số lượng các bộ quan hệ mà hệ thống trích chọn được, số lượng các bộ quan hệ chính xác tùy thuộc vào các giá trị khác nhau của sup. Từ kết quả chúng tôi nhận thấy rằng, nếu giá trị sup càng lớn, số lượng các bộ quan hệ trích chọn được lại giảm. Là do giá trị sup càng tăng, số lượng các mẫu trích chọn được và được sử dụng cho vòng lặp tiếp theo càng ít, chỉ những mẫu được sinh bởi càng nhiều bộ quan hệ mới được dùng để trích chọn các bộ quan hệ mới, những mẫu ít chất lượng hơn sẽ bị loại bỏ, do đó những bộ quan hệ được sinh bởi những mẫu kém chất lượng hơn sẽ không được hệ thống 54 trích chọn và đưa vào bảng quan hệ đích. Do đó, độ chính xác có xu hướng tăng, còn độ hồi tưởng có xu hướng giảm dần. Số lượng các bộ quan hệ trích chọn được Giá trị các độ đo sup Tổng số Chính xác Precision Recall F1 1 802 662 82.54 89.22 85.75 2 758 647 85.36 87.20 86.27 3 703 612 87.06 82.48 84.71 4 639 569 89.05 76.68 82.40 5 637 567 89.01 76.42 82.24 Bảng 14: Giá trị Precision, Recall, F1 của hệ thống theo giá trị sup Biểu đồ thể hiện sự tương quan giữa các giá trị Precision, Recall, F1 phụ thuộc vào giá trị của sup được trình bày ở hình 13. 70 75 80 85 90 95 100 1 2 3 4 5 tsup % Precision Recall F1 Hình 13: Giá trị Precision, Recall, F1 của hệ thống theo giá trị sup Thực nghiệm 2 Thực nghiệm tiếp theo chúng tôi cho hệ thống chạy thử trên Tập 5000 để thu các tập mẫu được sinh ra. Sau đó chúng tôi dùng tập mẫu này để trích chọn các cặp quan hệ trong Tập 1200. 55 Kết quả cho thấy, khi thực nghiệm với Tập 5000, số lượng mẫu thu được khá lớn là 435 mẫu (so với 100 mẫu khi thực nghiệm trên Tập 1200), tuy nhiên số lượng các bộ quan hệ sinh ra lại tăng không đáng kể. Kết quả cụ thể của thực nghiệm được liệt kê ở bảng 15 và 16. Số lần lặp Precision Recall F1 1 83.18 88.01 85.53 2 82.98 90.03 86.36 3 81.86 90.03 85.75 4 81.86 90.03 85.75 Bảng 15: Giá trị của Precision, Recall, F1 thực nghiệm trên tập 5000 Số lượng các bộ quan hệ trích chọn được Giá trị các độ đo Thực nghiệm Tổng số Chính xác Precision Recall F1 Thực nghiệm 1 758 647 85.36 87.20 86.27 Thực nghiệm 2 816 668 81.86 90.03 85.75 Bảng 16: Kết quả so sánh giữa thực nghiệm 1 và 2 So sánh kết quả của thực nghiệm này với thực nghiệm thứ nhất chúng tôi thấy chất lượng không chênh lệch nhau là mấy. Việc sử dụng huấn luyện để trích chọn ra tập các mẫu, với số lượng các tài liệu lớn hơn, các mẫu trích chọn được sẽ nhiều hơn và có tính chuyên biệt hơn, do đó kết quả sẽ tốt hơn với việc không sử dụng tập 1200 (thu được nhiều bộ quan hệ chính xác hơn). Tuy nhiên số lượng các bộ quan hệ trích chọn ra được tăng không đáng kể, là do dữ liệu trên tập 1200 và 5000 đều lấy từ 2 địa chỉ website, các bài viết trên mỗi địa chỉ thường có định dạng giống nhau nhau, những mẫu chất lượng sinh ra bởi tập 5000 cũng được sinh ra ở tập 1200, những mẫu còn lại trong tập 5000 có tính khả dụng kém hơn nên khi áp dụng các mẫu này cho tập 1200, số lượng bộ quan hệ sinh ra không đáng kể. Thậm chí, số lượng mẫu tăng, bộ quan hệ sinh ra có tăng, kèm theo đó là độ chính xác của các bộ sinh ra thấp, làm cho giá trị Precision cuối cùng thấp hơn, giá trị F1 vì thế thấp hơn so với thực nghiệm 1. Để đánh giá tính hiệu quả của giải mà luận văn đã đề xuất, chúng tôi cũng cài đặt giải thuật DIPRE. Thực nghiệm 3 Chúng tôi cho giải thuật DIPRE thực hiện trên tập 1200. Ở vòng lặp đầu tiên, số lượng bộ quan hệ trích chọn được là vô cùng nhỏ - 14 bộ quan hệ, trong đó chỉ có 11 bộ quan hệ là chính xác. Ở các vòng lặp tiếp theo, số lượng bộ quan hệ trích chọn được có tăng, nhưng với số lượng thấp. Cụ thể, kết quả thực nghiệm được chỉ ra ở bảng 17. 56 Số lần lặp Precision Recall F1 1 71.43 1.28 2.51 2 50.00 4.85 8.84 3 47.62 8.93 15.04 4 42.54 14.54 21.67 7 41.16 18.11 25.15 Bảng 17: Kết quả trích chọn khi áp dụng giải thuật DIPRE trên Tập 1200 Thực nghiệm 4 Chúng tôi cũng tiến hành thực nghiệm đối với giải thuật DIPRE thực hiện trên tập 5000, thu thập các mẫu, sau đó sử dụng tập mẫu này để trích chọn các bộ quan hệ trên tập 1200. Kết quả khả quan hơn thực nghiệm 3, kết quả cụ thể được trình bày trong bảng 18. Số lần lặp Precision Recall F-score 1 36.10 34.44 35.25 2 33.67 38.52 35.93 3 31.88 39.16 35.15 4 31.15 39.41 34.80 Bảng 18: Kết quả trích chọn khi áp dụng giải thuật DIPRE trên Tập 5000 Kết quả thực nghiệm với DIPRE thống kê trên số lượng các bộ quan hệ trích chọn được trình bày trong bảng 19. Số lượng các bộ quan hệ trích chọn được Thực nghiệm Tổng số Chính xác Thực nghiệm 3 345 142 Thực nghiệm 4 992 309 Bảng 19: Bảng thống kê kết quả trích chọn khi áp dụng giải thuật DIPRE cho bài toán trích chọn tên máy ảnh số Dựa vào kết quả thực nghiệm 3 và 4 đối với giải thuật DIPRE, nhận thấy giải thuật do luận văn đề xuất hiệu quả hơn rất nhiều so với giải thuật DIPRE áp dụng cho bài toán trích chọn tên máy ảnh số. Biểu đồ so sánh kết quả trích chọn của giải thuật DIPRE và giải thuật do luận văn đề xuất được chỉ ra ở hình 14. 57 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 Số lần lặp % Luận văn DIPRE (a) 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 Số lần lặp % Luận văn DIPRE (b) Hình 14: Kết quả thực nghiệm 3 (a) và thực nghiệm 4 (b) đối với giá trị F1 Thực nghiệm 5 Chúng tôi tiến hành thực nghiệm trích chọn các cặp trên Tập 1200; giá trị sup = 2; độ dài lớn nhất của mỗi mẫu = 10. 58 Kết quả thực nghiệm được thống kê trong bảng 20. Tổng số cặp hệ thống trích chọn được Tổng số cặp trong CSDL Chính xác Không chính xác Tổng 746 648 111 758 Bảng 20: Kết quả thực nghiệm 5 với số lượng các cặp tìm được Trong thực nghiệm này, chúng tôi tiến hành thống kê những mẫu có chất lượng nhất, có khả năng trích chọn ra được nhiều tên máy ảnh nhất. Danh sách các mẫu này cùng với một số bộ quan hệ được sinh bởi chúng được trình bày trong bảng 21, trong đó mẫu chất lượng nhất là mẫu . Mẫu Ví dụ Nikon D3 Samsung NX10 update firmware Canon EOS 7D Ricoh CX3 unveil Toshiba PDR-M3 Panasonic Lumix DMC-ZS7 introduce Canon PowerShot SX210 Fujifilm FinePix S3 launch Panasonic Lumix DMC-TS2 Fujifilm FinePix XP10 release Canon PowerShot S1 Panasonic Lumix DMC-FX66 announce firmware update Canon EOS 5D Panasonic DMC-G1 release firmware update Panasonic DMC-LX3 Nikon CoolPix P90 post firmware update Olympus E-P1 Pentax K-7 announce price Panasonic DMC-GH1 Nikon D100 Bảng 21: Kết quả thực nghiệm 5 - Mộ