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
NER
IR
Message Understanding Conferences
Named Entity Recognition
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 <camera, producer> ở 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ên máy ảnh, hãng sản xuất> 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
Camera
EOS 7D
Optio RS1500
Exilim EX-H20G
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
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”.
Opinion unit 1
Opinion holder (writer)
Suject
Part
<Powershot>
<picture>
Attribute
Evaluation <great>
Condition <flash is used>
<colors>
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 unit 2
Opinion holder (writer)
Suject
<Powershot>
Part
< >
Attribute
Evaluation
Condition
handle>
< >
<easy to grip>
<body has a grip
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].
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
located in downtown San Salvador.”
địa điểm
nạn nhân
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 <subj> 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 <victim> 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 <np> 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
<subj> passive-verb
Các mẫu học được từ các luật
<victim> was murdered
<perpetrator> bombed
1
2
3
4
<subj> active-verb
<subj> verb infinitive
<subj> aux noun
<perpetrator> attempted to kill
<victim> was victim
5
6
7
8
9
Passive-verb <dobj>
Active-verb <dobj>
Killed <victim>
Bombed <target>
To kill <victim>
Infinitive <direct-obj>
Verb infinitive <direct-obj>
Gerund <direct-obj>
Tried to attack <target>
Killing <victim>
10 Noun aux <direct-obj>
Fatality was <victim>
11 Noun preposition <noun-phrase>
Bomb against <target>
12 Passive-verb preposition <noun-phrase> Killed with <instrument>
13 Active-verb preposition <noun-phrase> Was aimed at <target>
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: <subj> active-verb dobj
(<perpetrator> attacked embassy); infinitive preposition <noun-phrase > (to sell for
<np>). 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 <subj>
active-verb và <subj> active-verb dobj đều được áp dụng vào Ta có các mẫu
được sinh ra là: <perpetrator> bombed
<perpetrator> 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|patternsi )
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:
Rlog F( patterni ) log2 ( rel _ freqi )* Pr( relevant| patternsi )
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
2
3
2
0.750
1.000
1.189 died in <np>
1.000 death of <np>
21
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.500
0.000
0.000
0.000
1.000
1.000
1.000
1.000
0.333
1.000
1.000
1.000
1.000
0.500
0.667
<subj> claimed
0.500 <subj> died
0.000 was diagnosed with <np>
0.000 <subj> was diagnosed
0.000
age of <np>
0.000 <subj> follow
0.000 responsibility for <np>
0.000 claimed <dobj>
0.000 <subj> claimed responsibility
0.000 died at <np>
0.000 shot with <np>
0.000 shot <dobj>
0.000 <subj> shot judges
0.000 <subj> shot
0.000 <subj> 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.
Initial Seed Tuples
Occurrences of Seed Tuples
Generate New Seed Tuples
Generate Extraction Patterns
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
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
Expectations book” thì tương ứng ta có sự kiện: (The famous writer, Charles Dickens,
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 <LI><B>title</B> by author ( , thì:
+ Order = true
+ Prefix = <LI><B>
+ Middle = </B> 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
Issac Asimov
The Robots of Dawn
Startide Rising
David Brin
Chaos: Making a New Science
Great Expectations
James Gleick
Clarles Dickens
W. Shakespeare
The Comedy of Errors
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.
<LI><B> The Robots of Dwan </B> by Isaac Asimov (Bantam Spectra,
Jan ’90)
<LI><B> Startide Rising </B> by David Brin (Pulphouse, Jul ’90)
<LI><B> Foundation </B> by Isaac Asimov (1951)
<P><B> Nightfall </B> 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 Issac
F
F
F
F
</B>
by
(Bantam
of Dwan
Asimove
/locus/c3.ht <B>
ml
Spectra, Jan
’90)
(Pulphouse,
Jul
Startide
Rising
David
Brin
/locus/c5.ht <B>
ml
</B>
by
’90)
(1951)
Foundation Isaac
Asimov
rg/bydecade <B>
/1950.html
</B>
by
Nightfall
Isaac
Asimov
rg/bydecade <B>
/1940.html
</B>
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
</B> by
</B> by
…
Suffix
F
F
www.sff.net/locus/c*
<LI><B>
(
www.scifi.org/bydecade/19* <B>
(19
…
…
…
Pattern
www.sff.net/locus/c*
<LI><B>title </B> by author (
www.scifi.org/bydecade/19*
<B>title </B> 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ộ <Organization, Location> 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 <Organization, Location> 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 <string1>‘s headquarters in <string 2>.
Initial Seed Tuples
Tag Entities
Generate New Seed Tuples
Generate Extraction Patterns
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
EXXON
IBM
REDMOND
IRVING
ARMONK
SEATTLE
BOEING
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 <Organization, Location>, Snowball tìm các mẩu tin
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
<Location> - based <Organization>. 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. <Location> chỉ phù hợp với những chuỗi được xác định thuộc
loại Location. <Organization> 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: <left, tag1, middle, tag2, right> 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: <{<the, 0.2>},LOCATION, {<-, 0.5>,
<based, 0.5>}, 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:
<ORGANIZATION>’s headquarters in <LOCATION>
<LOCATION>-based <ORGANIZATION>
<ORGANIZATION>, <LOCATION>
* 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 = < ls, t01, mS, t02, rS > với 2 thẻ t1’ và t2’ được
định nghĩa là:
l .l m .m r .r
P
S
P
S
P
S
Match(t ,t )
P
S
0
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
lS ,t1,mS ,t2 ,rS
Ví dụ ta có hai bộ quan hệ trong một cụm như sau:
1 - <{<servers 0.75>, <at 0.75>}, ORGANIZATION, {<’s 0.5> <central
0.5> <headquarters 0.5> <in 0.5>}, LOCATION, {}>
2 - <{<operate 0.75>, <from 0.75>}, ORGANIZATION, {<’s 0.7>
<headquarters 0.7> <in 0.7>}, LOCATION, {}>
Tương ứng ta có mẫu Snowball:
<{}, ORGANIZATION, {<’s 0.7> <headquarters 0.7><in 0.7>,
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) {<o;l>;<ls; t1; ms; t2; rs>} = CreateOccurrence(text_segment);
tC = <o; l>;
SimBest = 0;
For each p in Patterns
30
(2) sim = Match(< ls; t1; ms; t2; rs >; 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 <o, l>, Snowball sinh ra bộ - 5 t = <lc; t1;
mc; t2; rc >. Bộ <o, l> đượ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: <{ }, ORGANIZATION, <”, 1 >, 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 = <o, l> đượ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.
Tải về để xem bản đầy đủ
65 trang
25/04/2025
290
Bạn đang xem 30 trang mẫu của tài liệu "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ố", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_phuong_phap_hoc_ban_giam_sat_cho_bai_toan_trich_cho.pdf
