Đăng ký Đăng nhập
Trang chủ 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...

Tài liệu 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ố

.PDF
64
189
82

Mô tả:

ĐẠ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 Mục lục Lời cam đoan ..................................................... Error! Bookmark not defined. Mục lục .............................................................................................................. 2 Danh mục các ký hiệu, các chữ viết tắt ............................................................... 3 Danh mục các bảng ............................................................................................ 4 Danh mục các hình vẽ, đồ thị ............................................................................. 5 Mở đầu ............................................................................................................... 6 CHƢƠNG 1. GIỚI THIỆU ................................................................................ 7 CHƢƠNG 2. HỆ THỐNG TRÍCH CHỌN THÔNG TIN ................................. 13 2.1. Xây dựng hệ thống trích chọn thông tin ..................................................... 13 2.1.1. Công nghệ tri thức .................................................................................. 13 2.1.2. Huấn luyện tự động ................................................................................ 13 2.2. Các phƣơng pháp trích chọn ...................................................................... 14 2.2.1. Học có giám sát trích chọn quan hệ ........................................................ 15 2.2.2. Học không giám sát trích chọn quan hệ .................................................. 17 2.2.3. Học bán giám sát trích chọn quan hệ ...................................................... 20 2.2.3.1. DIPRE: Dual Iterative Pattern Relation Extraction .............................. 21 2.2.3.2. Hệ thống SNOWBALL ....................................................................... 25 2.3. Nhận xét .................................................................................................... 31 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.............................................................................................. 32 3.1. Mô tả bài toán............................................................................................ 32 3.2. Mô hình giải quyết bài toán ....................................................................... 32 3.3. Mô hình hệ thống ...................................................................................... 34 3.3.1. Pha tiền xử lí .......................................................................................... 35 3.3.2. Pha sinh các mẫu .................................................................................... 42 3.3.3. Pha sinh các bộ quan hệ mới ................................................................... 47 CHƢƠNG 4. THỰC NGHIỆM ........................................................................ 49 4.1. Môi trƣờng thực nghiệm ............................................................................ 49 4.2. Dữ liệu thực nghiệm .................................................................................. 49 4.3. Đánh giá hệ thống...................................................................................... 50 4.4. Thực nghiệm ............................................................................................. 50 Kết luận và hƣớng phát triển tƣơng lai ............................................................. 60 Tài liệu tham khảo ............................................................................................ 61 Phụ lục. Mối quan hệ ngữ nghĩa trong WordNet .............................................. 63 3 Danh mục các ký hiệu, các chữ viết tắt IE NE MUC NER IR DIPRE Information Extraction Named Entity Message Understanding Conferences Named Entity Recognition Information Retrieval Dual Iterative Pattern Relation Extraction 4 Danh mục các bảng Bảng 1: Các luật của AutoSlog ......................................................................... 17 Bảng 2: Năm bộ quan hệ hạt giống của hệ thống DIPRE.................................. 23 Bảng 3: Ví dụ các sự kiện đƣợc mô tả dƣới dạng bộ - 7 ................................... 23 Bảng 4: Ví dụ về việc sinh các mẫu DIPRE ..................................................... 25 Bảng 5: Năm bộ quan hệ hạt giống của hệ thống Snowball .............................. 26 Bảng 6: Một số lớp thƣờng dùng trong WordNet ............................................. 44 Bảng 7: Cấu hình của máy PC dùng trong thực nghiệm ................................... 49 Bảng 8: Các công cụ sử dụng trong thực nghiệm.............................................. 49 Bảng 9: Các thƣ viện sử dụng trong thực nghiệm ............................................. 49 Bảng 10: Dữ liệu kiểm thử và dữ liệu huấn luyện ............................................. 50 Bảng 11: Tập các quan hệ hạt giống ban đầu .................................................... 50 Bảng 12: Một số cặp ở lần lặp đầu tiên ............................ 51 Bảng 13: Giá trị Precision, Recall và F1 sau các vòng lặp ................................ 51 Bảng 14: Giá trị Precision, Recall, F1 của hệ thống theo giá trị sup ................ 53 Bảng 15: Giá trị của Precision, Recall, F1 thực nghiệm trên tập 5000 .............. 54 Bảng 16: Kết quả so sánh giữa thực nghiệm 1 và 2 .......................................... 54 Bảng 17: Kết quả trích chọn khi áp dụng giải thuật DIPRE trên Tập 1200 ....... 55 Bảng 18: Kết quả trích chọn khi áp dụng giải thuật DIPRE trên Tập 5000 ....... 55 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ố ................................................................... 55 Bảng 20: Kết quả thực nghiệm 5 với số lƣợng các cặp tìm đƣợc ...................... 57 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 ................................................................................................................ 57 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 ... 58 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 .................................................................................................................. 59 Bảng 24: Các quan hệ ngữ nghĩa trong WordNet ............................................. 63 5 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...................................... 7 Hình 2: Ví dụ về khai phá quan điểm ................................................................. 9 Hình 3: Sơ đồ hoạt động của hệ thống AutoSlog .............................................. 16 Hình 4: Sơ đồ hoạt động của hệ thống AutoSlog – TS ...................................... 18 Hình 5: Ví dụ về AutoSlog - TS ....................................................................... 20 Hình 6: Mô hình hoạt động của hệ thống DIPRE ............................................. 21 Hình 7: Mô hình hoạt động của hệ thống Snowball .......................................... 26 Hình 8: Các sự kiện tìm đƣợc dựa vào bộ quan hệ hạt giống ............................ 27 Hình 9: Mô hình hệ thống trích chọn tên máy ảnh số ....................................... 34 Hình 10: Mô hình của pha tiền xử lí ................................................................. 35 Hình 11: Mô hình thuật toán sinh mẫu từ một bộ quan hệ ................................ 42 Hình 12: Giá trị của Precision, Recall, F1 thực nghiệm trên tập 1200 .............. 52 Hình 13: Giá trị Precision, Recall, F1 của hệ thống theo giá trị sup ................ 53 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 ..... 56 6 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. 7 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. Producer Canon Pentax Casio Ricoh Camera EOS 7D Optio RS1500 Exilim EX-H20G G700SE 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 8 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 9 ngƣời dùng nhận thấy “the colors of pictures” đƣợc chụp bởi sản phẩm Powershot là “great”. Opinion unit 1 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 2 Opinion holder (writer) Suject Part <> Attribute <> Evaluation Condition 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]. 10  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. 11 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 12 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. 13 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ề 14 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 15 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 16 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. 17 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 6 7 8 9 10 Passive-verb Active-verb Infinitive Verb infinitive Gerund Noun aux Killed Bombed To kill Tried to attack Killing 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 đó, 18 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. 19  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ê: rel  freqi Pr( relevant | patterns i )  total  freqi 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: R log F ( pattern i )  log 2 ( rel _ freqi )* Pr( relevant | patterns i ) 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 20 3 4 1 1 1 1 1 1 1 3 1 1 1 1 2 2 2 0 0 0 1 1 1 1 1 1 1 1 1 1 0.667 0.667 claimed 0.500 0.500 died 0.000 0.000 was diagnosed with 0.000 0.000 was diagnosed 0.000 0.000 age of 1.000 0.000 follow 1.000 0.000 responsibility for 1.000 0.000 claimed 1.000 0.000 claimed responsibility 0.333 0.000 died at 1.000 0.000 shot with 1.000 0.000 shot 1.000 0.000 shot judges 1.000 0.000 shot 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.
- Xem thêm -

Tài liệu liên quan