ĐẠ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