Xem bên trong

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi

36 tr. + CD-ROM
Luận văn TS. Hệ thống thông tin — Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2014
Electronic Resources

0.00

Tải về miễn phí bản đầy đủ PDF luận văn tại Link bản đầy đủ 1

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN MINH HẢI

MỘT GIẢI THUẬT TRI-TRAIN CHỈNH SỬA
VÀ ỨNG DỤNG VÀO BÀI TOÁN PHÂN LỚP
CÂU HỎI

Ngành: Công nghệ Thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 01 04

LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS.NGUYỄN TRÍ THÀNH

Hà Nội – 2014
2

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
LỜI CAM ĐOAN
Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá
nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung của luận
văn, những điều đã trình bày là của cá nhân tôi hoặc là được tôi tổng hợp từ
nhiều nguồn tài liệu. Tất cả các nguồn tài liệu tham khảo có xuất xứ rõ ràng và
được trích dẫn hợp pháp.
Tôi xin chịu toàn bộ 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 tôi.

Hà Nội, tháng 10 năm 2014

Nguyễn Minh Hải

3

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
MỤC LỤC
LỜI CAM ĐOAN ……………………………………………………………………………………………. 2

MỤC LỤC ………………………………………………………………………………………………………. 3

DANH MỤC CÁC TỪ VIẾT TẮT …………………………………………………………………… 5

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ……………………………………………………………. 6

MỞ ĐẦU ………………………………………………………………………………………………………… 7

Chương 1. Giới thiệu bài toán và các nghiên cứu liên quan ……………………………….. 8

1.1. Hệ thống hỏi đáp ………………………………………………………………………………………… 8

1.2. Vị trí của bài toán phân lớp câu hỏi trong hệ thống hỏi đáp ……………………………… 9

1.3. Bài toán phân lớp câu hỏi …………………………………………………………………………… 11

1.4. Các đề tài nghiên cứu liên quan ………………………………………………………………….. 12

1.5. Các hướng giải quyết bài toán phân lớp câu hỏi hiện nay ………………………………. 17

1.6. Lựa chọn định hướng giải quyết bài toán của luận văn ………………………………….. 18

Chương 2. Mô hình giải quyết bài toán ……………………………………………………………. 20

2.1. Lựa chọn giải pháp và mô hình giải quyết bài toán ……………………………………….. 20

2.2. Cơ sở lý thuyết …………………………………………………………………………………………. 20

2.2.1. Học bán giám sát ……………………………………………………………………………. 20

2.2.2. Các thuật toán học bán giám sát ……………………………………………………….. 20

2.2.3. Tri-Train ……………………………………………………………………………………….. 21

2.2.3.1. Tri-Train gốc …………………………………………………………………………… 21

2.2.3.2. Tri-Train cải tiến ……………………………………………………………………… 23

2.3. Giải pháp cải tiến ……………………………………………………………………………………… 25

2.3.1. Đề xuất cải tiến ………………………………………………………………………………. 25

Chương 3. Thực nghiệm …………………………………………………………………………………. 27

3.1. Dữ liệu và công cụ cho thực nghiệm ……………………………………………………………. 27

3.2. Kết quả thực nghiệm Tritrain ……………………………………………………………………… 28

3.2.1. Kịch bản thực hiện: ………………………………………………………………………… 28

4

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
3.2.2. Đánh giá hiệu quả của việc sử dụng Tri-Train ……………………………………. 28

3.2.2.1. Hiệu quả cải thiện với 1000 dữ liệu đã được gán nhãn …………………. 28

3.2.2.2. Hiệu quả cải thiện với 2000 dữ liệu đã được gán nhãn …………………. 29

3.2.2.3. Hiệu quả cải thiện với 3000 dữ liệu đã được gán nhãn …………………. 30

3.2.2.4. Hiệu quả cải thiện với 4000 dữ liệu đã được gán nhãn …………………. 31

3.3. Đánh giá chung ………………………………………………………………………………………… 31

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN TƯƠNG LAI ………………………………….. 34

TÀI LIỆU THAM KHẢO ……………………………………………………………………………… 35

5

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi

DANH MỤC CÁC TỪ VIẾT TẮT
QA Question Answering System
TREC Text Retrieval Conference
NN Nearest Neighbors
NB Naïve Bayes
DT Decision Tree
SNoW Sparse Network of Winnows
SVM Support Vector Machines
MEM Maximum Entropy Model
CQA Community Question Answering
CoCQA Co-Training Over Questions and Answers

6

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.2: Các module chức năng chính của một hệ thống hỏi đáp.

Hình 1.3: Bài toán phân lớp câu hỏi.

Hình 1.4: Mô hình tổng quan hệ thống phân lớp câu hỏi của Kadri Hacioglu và
Wayne Ward.

Hình 1.5: Các hướng giải quyết bài toán phân lớp câu hỏi.

Hình 4.1: Biểu đồ đánh giá hiệu quả cải thiện kết qủa với tập dữ liệu đã được gán
nhãn là 1000.

Hình 4.2: Biểu đồ đánh giá hiệu quả cải thiện kết qủa với tập dữ liệu đã được gán
nhãn là 2000.

Hình 4.3: Biểu đồ đánh giá hiệu quả cải thiện kết qủa với tập dữ liệu đã được
gán nhãn là 3000

Hình 4.4: Biểu đồ đánh giá hiệu quả cải thiện kết qủa với tập dữ liệu đã được
gán nhãn là 4000

7

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
MỞ ĐẦU
Các hệ thống hỏi đáp (Question Answering System) là một trong những
hướng quan trọng trong xử lý ngôn ngữ tự nhiên. Một trong những thành phần
quan trọng của các hệ thống này là module phân lớp câu hỏi. Chất lượng của
module này có ý nghĩa rất quan trọng vì nó xác định được miền dữ liệu cũng
như phương pháp trích chọn câu trả lời cho câu hỏi đưa ra. Luận văn tập trung
tìm hiểu các phương pháp nhằm làm tăng hiệu năng phân lớp của module phân
lớp câu hỏi.
Bài toán phân lớp câu hỏi đã được đặt ra và giải quyết từ khá lâu với hai
hướng chủ đạo: dựa trên luật và dựa trên xác suất, tuy nhiên cho đến nay nó vẫn
là bài toán được nhiều người quan tâm. Luận văn tập trung khảo sát các phương
pháp được áp dụng cho phân lớp câu hỏi. Trên cơ sở đó lựa chọn nghiên cứu về
giải thuật học bán giám sát. Trong các giải thuật học bán giám sát, tác giả lựa
chọn nghiên cứu cách cải tiến giải thuật Tri-Train áp dụng cho bài toán phân lớp
câu hỏi. Kế thừa trên một đề xuất cải tiến của Nguyễn Trí Thành và các cộng sự
được công bố vào năm 2008, luận văn đưa ra đề xuất cải tiến và thực hiện nhiều
thử nghiệm minh họa sau đó thống kê và phân tích các thử nghiệm.
Luận văn được tổ chức như sau:
Chương 1: giới thiệu về hệ thống hỏi đáp, tầm quan trọng của module phân
lớp câu hỏi và phát biểu bài toán phân lớp câu hỏi.
Chương 2: khảo sát các đề tài nghiên cứu liên quan đến phân lớp câu hỏi và
những thành tựu nghiên cứu trên thế giới đã đạt được.
Chương 3: trình bày sơ lược về học bán giám sát, giải thuật Tri-Train, đưa ra
và trình bày chi tiết đề xuất chỉnh sửa nhằm tăng hiệu quả cho bài toán phân lớp
câu hỏi.
Chương 4: trình bày quá trình làm thực nghiệm và các kết quả đạt được.
Tác giả xin chân thành cảm ơn sự hướng dẫn và chỉ bảo tận tình của thầy
Nguyễn Trí Thành, cảm ơn các thầy cô giáo trong khoa Hệ Thống Thông Tin
trường Đại học Công nghệ – Đại học Quốc Gia Hà Nội đã tạo điều kiện giúp tác
giả hoàn thành luận văn này.

Hà Nội, tháng 10 năm 2014
Nguyễn Minh Hải
8

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
Chương 1. Giới thiệu bài toán và các nghiên cứu liên quan
Mở đầu chương này sẽ giới thiệu về hệ thống hỏi đáp nói chung. Sau đó chỉ
ra vị trí, vai trò của bài toán phân lớp câu hỏi trong hệ thống hỏi đáp. Cuối cùng,
phát biểu dưới dạng toán học bài toán phân lớp câu hỏi.
1.1. Hệ thống hỏi đáp
Hệ thống hỏi đáp có thể được xem như bước kế tiếp của quá trình tìm kiếm
thông tin, cho phép người dùng đặt các câu hỏi bằng ngôn ngữ tự nhiên và nhận
về những câu trả lời ngắn gọn. Để đáp ứng nhu cầu tìm kiếm hiệu quả cho các
yêu cầu của người dùng cần có một hệ thống đủ thông minh, nhanh chóng và trả
lời chính xác nhất cho các câu hỏi. Chính từ nhu cầu này, hệ thống hỏi đáp tự
động QA (Question Answering System) đã được đề xuất, nghiên cứu tìm hướng
giải quyết. Hệ thống này nhằm mục đích trả lời cho các câu hỏi tự nhiên trong
thời gian ngắn nhất, chi phí tối thiểu và hiệu quả tối đa.
Năm 2000, Jaime Carbonell và các cộng sự đã sớm đưa ra các tiêu chuẩn
chung cho việc nghiên cứu QA [6]. Theo đó, một hệ thống hỏi đáp được người
dùng đánh giá là hữu ích nếu đáp ứng được các tiêu chuẩn:
– Tính hợp lý về thời gian: câu trả lời phải được đưa ra trong thời gian
ngắn, ngay cả khi có hàng ngàn người dùng cùng truy nhập hệ thống một
lúc. Các nguồn dữ liệu mới cần phải được tích hợp vào hệ thống ngay khi
chúng sẵn sàng để có thế cung cấp cho người dùng câu trả lời cho những
câu hỏi về các sự kiện có tính thời sự.
– Tính chính xác: thách thức này là cực kì quan trọng bởi việc đưa ra câu trả
lời sai còn tai hại hơn nhiều là không đưa ra câu trả lời. Nghiên cứu về
QA cần tập trung vào việc đánh giá tính đúng đắn của câu trả lời đưa ra,
bao gồm cả phương thức để phát hiện các trường hợp mà dữ liệu hiện thời
không chứa câu trả lời cho câu hỏi. Các thông tin mâu thuẫn trong dữ liệu
cũng cần được tìm ra và các thông tin này cần được xử lý theo một cách
phù hợp, nhất quán. Để đạt được sự chính xác, hệ thống QA cần được tích
hợp các nguồn tri thức và quá trình học suy luận thông thường.
– Tính khả dụng: hệ thống QA cần đáp ứng được các yêu cầu cụ thể của
một người dùng. Các ontology trên từng miền cụ thể và ontology trên
miền mở cần được tích hợp trong hệ thống. Hệ thống QA cần có khả năng
khai phá câu trả lời từ bất kì dạng dữ liệu gì (văn bản, web, cơ sở dữ liệu,
…) và đưa ra câu trả lời dưới định dạng mà người dùng mong muốn, cho
phép người dùng miêu tả ngữ cảnh của câu hỏi và cung cấp các thông tin
9

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
giải thích, trích dẫn nguồn cho câu trả lời.
– Tính hoàn chỉnh: câu trả lời hoàn chỉnh cho câu hỏi của người dùng là
điều mà các hệ thống QA hướng tới. Trong nhiều trường hợp (câu hỏi về
danh sách, nguyên nhân, cách thức…), các phần của câu trả lời nằm rải
rác trong một văn bản, thậm chí trong nhiều văn bản. Vì vậy cần phải hợp
nhất các phần này dựa trên các thông tin liên kết để tạo ra câu trả lời hoàn
chỉnh.
– Tính thích hợp của câu trả lời: trong ngôn ngữ tự nhiên, câu hỏi đưa ra
luôn gắn với ngữ cảnh nào đó và câu trả lời cũng nằm trong một ngữ cảnh
nhất định. Câu trả lời mà hệ thống QA đưa ra phải phù hợp ngữ cảnh với
câu hỏi. Một hệ thống QA có khả năng tương tác là cần thiết trong nhiều
trường hợp bởi chuỗi các câu hỏi liên quan đến một vấn đề sẽ giúp làm
sáng tỏ thông tin mà người dùng đang hỏi. Việc đánh giá một hệ thống
QA cần hướng người dùng bởi ý kiến người dùng là đánh giá tốt nhất cho
tính thích hợp của câu trả lời.
Hệ thống hỏi đáp tự động là hệ thống được xây dựng để thực hiện việc tìm
kiếm tự động câu trả lời từ một tập lớn các tài liệu cho câu hỏi đầu vào một cách
chính xác. QA hiện đang thu hút sự quan tâm của rất nhiều nhà nghiên cứu từ
các trường đại học, các viện nghiên cứu cũng như các công ty lớn hàng đầu trên
thế giới [15]. Nhiều hội nghị lớn về xử lý ngôn ngữ tự nhiên được tổ chức hàng
năm như Coling, Text Retrieval Conference (Trec)… đều có những phần dành
riêng cho những nghiên cứu liên quan đến hệ thống hỏi đáp.

1.2. Vị trí của bài toán phân lớp câu hỏi trong hệ thống hỏi đáp
Hệ thống hỏi đáp ngày càng trở nên phổ biến và phong phú trong nhiều lĩnh
vực và ứng dụng trong cuộc sống. Phân lớp câu hỏi là một module quan trọng
trong hệ thống này (hình 1.2). Do vậy bài toán phân lớp câu hỏi càng trở nên cần
thiết và quan trọng. Chức năng chính của nó là phân các câu hỏi vào các lớp
giúp giảm đáng kể không gian tìm kiếm câu trả lời, độ chính xác của nó đóng
vai trò quan trọng trong hiệu quả của hệ thống hỏi đáp.
10

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi

Hình 1.2: Các module chức năng chính của một hệ thống hỏi đáp.
Trong đó các bước tiến hành như sau
1. Người dùng nhập câu hỏi qua giao diện web/mobile app…
2. Hệ thống sử dụng module phân lớp câu hỏi để xác định lĩnh vực của
câu hỏi để tìm kiếm, bước này là bước rất quan trọng, nếu bước này
phân lớp sai lĩnh vự cần hỏi thì gần như hoàn toàn là câu trả lời sẽ
không chính xác.
3. Sau khi đã xác định được lĩnh vực/nội dung cần tìm câu trả lời, hệ
thống sẽ chuẩn hoá câu hỏi theo format của hê thống, format này có
11

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
thể khác nhau tuỳ theo mô hình các hệ thống được xây dựng
4. Tìm kiếm câu trả lời trong lĩnh vực đã được xác định ở (2) và theo
format câu hỏi ở (3).
5. Hiển thị câu trả lời cho người dùng từ nội dung tìm được từ(4).
Hệ thống QA bao gồm nhiều thành phần: thành phần phân tích câu hỏi, thành
phần phân lớp câu hỏi, thành phần truy vấn dựa trên những tập tài liệu liên quan
đến câu truy vấn,… Trong các thành phần này, thành phần phân lớp câu hỏi
đóng vai trò quan trọng. Đầu tiên, người dùng đưa vào hệ thống một câu hỏi, sau
đó câu hỏi sẽ được phân tích để tìm từ khóa tìm kiếm hoặc định dạng thành một
loại câu truy vấn xuống cơ sở dữ liệu chứa thông tin. Kết quả của quá trình đó
không thể trả về ngay lập tức một câu trả lời duy nhất và chính xác. Trên thực tế
nó sẽ đưa ra một tập các câu trả lời đề cử có liên quan đến vấn đề được hỏi. Vậy,
công việc chính của phân lớp câu hỏi là lọc và loại bỏ những câu trả lời nào
không phù hợp, hơn thế nữa có thể dựa trên một số tiêu chí để đánh giá xếp hạng
các câu trả lời theo mức độ liên quan đến câu hỏi. Ngoài ra, phân lớp câu hỏi
còn có thể giúp ta xác định được kiểu câu trả lời một khi ta biết được phân lớp
của nó. Việc này giúp hệ thống đưa ra một câu trả lời gần gũi với ngôn ngữ tự
nhiên.
Håkan Sundblad cũng chỉ ra rằng để có một hệ thống hỏi đáp thành công,
việc phân lớp các câu hỏi chính xác là một nhân tố quan trọng [5]. Hệ thống
phân lớp câu hỏi bao gồm hai thành phần chính: một nguyên tắc phân loại các
câu trả lời và một máy phân loại.
1.3. Bài toán phân lớp câu hỏi
Phân lớp câu hỏi có thể được hiểu theo cách thông thường là: cho một câu
hỏi (đại diện bởi các đặc trưng), gán câu hỏi đó vào một nhóm hoặc một tập
nhóm (hình 1.3).
Đầu vào: câu hỏi ở dạng ngôn ngữ tự nhiên.
Đầu ra: lĩnh vực/miền/nhóm của câu hỏi.
Phát biểu: cho tập hợp N các câu hỏi đã được gán nhãn và danh sách các
nhãn lớp. Cho một câu hỏi A bất kỳ, xác định nhãn lớp cho câu hỏi A.
12

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
A được xếp
vào lớp i
A được xếp
vào lớp j
Lớp n-1
Lớp n

Lớp 1
Lớp j

Lớp i
Câu hỏi A chưa
được phân lớp
Module phân lớp câu
hỏi
Dữ liệu mẫu
và danh sách
các lớp
Trích chọn các
đặc trưng và
gán nhãn lớp
Thuật toán
luyện và các
quy luật phân
lớp

Hình 1.3: Bài toán phân lớp câu hỏi.
Tuy nhiên bằng cách áp dụng định nghĩa của phân loại văn bản vào vấn đề
phân lớp câu hỏi, Håkan Sundblad cũng đã phát biểu lại bài toán phân lớp câu
hỏi như sau [5]:
Định nghĩa 1: phân lớp câu hỏi là công việc gán một giá trị kiểu bool cho
mỗi cặp < 𝑞! , 𝑐! >∈ 𝑄×𝐶 với Q là lĩnh vực các câu hỏi và C là một tập danh
mục nhóm được định nghĩa sẵn 𝐶 = 𝐶!,𝐶!,…𝐶|!| .
Việc gán cho <qj,ci> giá trị T (True = 1) nghĩa là qi được đánh giá là thuộc
nhóm ci, và ngược lại nếu <qj,ci> bằng F (Fales=0) nghĩa là qi không thuộc
nhóm ci. Trong một thiết lập học máy, đây chính là việc gán những hàm mục
tiêu chưa biết Φ:𝑄×𝐶 → {𝑇,𝐹} về hàm xấp xỉ đã biết Φ:𝑄×𝐶 → {𝑇,𝐹}.
1.4. Các đề tài nghiên cứu liên quan
Trong một nghiên cứu được trình bày vào năm 2002 [11], Xin Li và Dan
Roth đã chỉ ra rằng một module phân lớp câu hỏi trong hệ thống hỏi đáp sẽ bao
gồm hai yêu cầu chính:
– Cung cấp ràng buộc trong các loại câu trả lời cho phép xử lý thêm để định
vị chính xác và kiểm nghiệm câu trả lời.
– Cung cấp thông tin cho quá trình thuận để có thể sử dụng chiến lược lựa
chọn loại câu trả lời cụ thể. Ví dụ câu hỏi “Ai là người phụ nữ đầu tiên bị
13

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
giết ở chiến tranh Việt Nam? “, chúng ta không muốn kiểm tra tất cả các
cụm danh từ trong câu hỏi để đưa ra câu trả lời. Tối thiểu chúng ta có thể
xác định được mục tiêu của câu hỏi này là một người. Bằng cách đó có
thể giảm bớt không gian các đáp án một cách đáng kể.
Cũng trong bài báo này tác giả đã đưa ra hướng giải quyết bằng phương pháp
học máy cho phân lớp câu hỏi. Rất nhiều nghiên cứu trong những năm về sau
của nhiều tác giả trên thế giới đã khá thành công khi áp dụng các giải pháp bằng
học máy cho bài toán phân lớp câu hỏi và càng chứng minh sự đúng đắn của
hướng giải quyết này. Trong nghiên cứu [11] Xin Li và Dan Roth đã phát triển
phân lớp có thứ tự được xây dựng bởi một lớp ngữ cảnh có thứ tự của các loại
câu trả lời và sử dụng chúng để phân loại câu hỏi thành các lớp tinh. Ngoài ra,
họ còn tiến hành các thực nghiệm chứng minh rằng vấn đề phân lớp câu hỏi có
thể được giải quyết khá chính xác bằng phương pháp học và chỉ ra những lợi ích
của các đặc trưng nền tảng trong sự phân tích ngữ cảnh.
Một đóng góp không nhỏ của Xin Li và Dan Roth trong nghiên cứu của mình
là đã xây dựng một bộ dữ liệu chuẩn sử dụng để kiểm thử tính đúng đắn của các
giải pháp phân lớp câu hỏi. Dữ liệu được thu thập từ 4 nguồn: 4500 câu hỏi tiếng
Anh được công bố bởi USC bao gồm 500 cấu trúc câu hỏi thủ công cho một vài
lớp hiếm, 894 câu hỏi TREC 8 sử dụng làm dữ liệu luyện (train) và 500 câu hỏi
từ TREC 10 sử dụng làm dữ liệu kiểm tra (test). Các câu hỏi này được gán nhãn
một cách thủ công và để đơn giản, mỗi câu hỏi được gán chính xác bằng một
nhãn lớp. Các câu hỏi được phân lớp theo 6 mục thô và 50 mục tinh (bảng 2.1).
Các bài báo nghiên cứu sau này về phân lớp câu hỏi cũng đựa trên các mục này
để nghiên cứu và đánh giá.
Bảng 1.1: Phân lớp 6 mục thô và 50 mục tinh được đưa ra bởi Li và Roth
(2002).
Mục thô Mục tinh
ABBR abbreviation, expansion
DESC definition, description, manner, reason
ENTY animal, body, color, creation, currency, disease, event, food,
instrument, language, letter, other, plant, product, religion, sport,
subtance, symbol, technique, term, vehicle, word
HUM description, group, individual, title
LOC city, country, mountain, other, state
NUM code, count, date, distance, money, order, other, percent, period,
14

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
speed, temperature, size, weight
Bộ dữ liệu nổi tiếng này hiện nay vẫn đang được sử dụng trong các nghiên
cứu liên quan đến bài toán phân lớp câu hỏi, thậm chí còn được dịch ra nhiều
thứ tiếng để phục vụ các nghiên cứu mang tính đặc trưng của ngôn ngữ.
Zhang D. và Lee W.S năm 2003 đã nghiên cứu và tiến hành cài đặt thử
nghiệm cách giải quyết bài toán phân lớp câu hỏi với 5 thuật toán học máy:
Nearest Neighbors (NN), Naïve Bayes (NB), Decision Tree (DT), Sparse
Network of Winnows (SNoW), và Support Vector Machines (SVM) sử dụng hai
đặc trưng bag-of-words và bag-ofN-grams. Các kết quả nghiên cứu được chỉ ra
trong tài liệu [12] cho thấy SVM tỏ ra có hiệu quả nổi trội hơn so với các
phương pháp khác. Ngoài ra họ còn đưa ra giải thuật Kernel Tree để nâng cao
chất lượng phân lớp của SVM nhờ tận dụng đặc điểm có cấu trúc cú pháp của
câu hỏi.
Kernel Tree được trình bày ở [12] là một hàm đặc biệt được đề xuất để nhúng
vào SVM nhằm mang lại hiệu quả tốt hơn đối với cấu trúc ngữ cảnh của các câu
hỏi. Theo kết quả thực nghiệm các tác giả của bài báo này đưa ra thì SVM kết
hợp với Tree Kernel có thể giảm bớt được 20% lỗi.
Cũng trong năm 2003 Kadri Hacioglu và Wayne Ward [8] đã đề cập đến việc
lựa chọn giải pháp học máy SVM cho phân lớp câu hỏi để thay thế cách phân
lớp bằng các biểu thức chính quy và đưa ra mô hình tổng quan hệ thống phân
lớp câu hỏi của họ (hình 1.4).
Indexing DimensionReduction Tranformation ClassifierPreprocessor
Class labelQuestion text
Feature Extraction Classification
m SVM
Classifiers Combiner
One of n class
labelsFeature vector …

Hình 1.4: Mô hình tổng quan hệ thống phân lớp câu hỏi của Kadri Hacioglu và
Wayne Ward.
Họ chỉ ra rằng mặc dù các SVM hỗ trợ được phân lớp nhị phân, nhưng có thể
mở rộng việc sử dụng chúng như phân loại đa lớp sử dụng mã nhị phân. Đối
chiếu với các phương pháp khác cho thấy phương pháp này là lĩnh vực hứa hẹn
cho việc cải thiện hiệu quả phân lớp câu hỏi với việc phân tích phi ngôn ngữ.
15

Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi
Năm 2005, Zhi-Hua Zhou và Ming Li đã đề xuất thuật toán học bán giám sát
Tri-Train [13], thuật toán này tạo ra ba bộ phân lớp từ cùng một tập hợp dữ liệu
được gán nhãn cho trước, các bộ phân lớp này sẽ được tinh chế lại sử dụng các
mẫu chưa được gán nhãn trong quá trình Tri-Train. Trong mỗi vòng lặp của Tri-
Train, một mẫu chưa được gán nhãn sẽ được gán nhãn nếu hai bộ phân lớp khác
đồng ý gán cùng một nhãn cho nó. Tri-Train không yêu cầu không gian mẫu
được mô tả đầy đủ hay dư thừa cũng không hạn chế bất kỳ thuật toán học có
giám sát hay khung nhìn nào, do đó ứng dụng của nó mở rộng hơn thuật toán
học bán giám sát Co-Train trước đây.
Năm 2007, Nguyễn Trí Thành cùng nhóm nghiên cứu của mình đã đề xuất
giải pháp sử dụng phân loại theo cấp bậc câu hỏi nhằm mục đích giảm số lượng
các lớp để cải thiện hiệu suất phân lớp khi số lượng lớp là khá lớn. Các câu hỏi
được phân lớp một cách tuần tự bởi phân lớp thô và một phân lớp tinh. Nghiên
cứu được công bố trong bài báo [9]. Họ cũng đưa ra khuyến cáo: mặc dù một
câu hỏi có thể thuộc về nhiều lớp nhưng đề xuất chỉ nên phân câu hỏi vào lớp có
xác suất cao nhất trong số các lớp có thể xếp vào.
Ngoài ra, bài báo [9] còn đề xuất hướng giải quyết bài toán phân lớp câu hỏi
có thứ tự kết hợp với thuật toán học bán giám sát và đưa ra đề xuất ba phương
án phân lớp:
– Ứng dụng học có giám sát: dễ dàng tạo tập luyện cho phân lớp thô. Mỗi
phân lớp tinh cần có một tập con được gán nhãn. Có thể chiết xuất phù
hợp các tập con cho việc luyện mỗi phân lớp tinh. Áp dụng: sử dụng
MEM cho tất cả các phân lớp. Kết luận: khi kích thước mẫu nhỏ, tỷ lệ lỗi
của phân lớp phẳng cao hơn phân lớp tuần tự.
– Ứng dụng được kết hợp học có giám sát và bán giám sát: sử dụng bán
giám sát cho mức đầu tiên, các phân lớp còn lại vẫn sử dụng thuật toán
học có giám sát. Áp dụng Tri-Train cải tiến. Kết quả: học bán giám sát
giúp cải thiện dự báo của phân lớp tinh, khi kích thước tập luyện tăng thì
hiệu quả phân lớp tinh của MEM tỏ ra có hiệu quả hơn của SVM.
– Ứng dụng bán giám sát: sử dụng học bán giám sát cho tất cả các mức. Kết
quả thực nghiệm cho thấy không có nhiều hứa hẹn.
Kết quả thực nghiệm của họ cho thấy học bán giám sát không cho hiệu quả
tốt đối với các phân lớp tinh. Do đó không áp dụng học bán giám sát cho các
phân lớp tinh và có giám sát cho phân lớp thô. Tuy nhiên phương pháp ứng
dụng bán giám sát cho phân lớp tinh chưa mang lại kết quả tốt nhưng mở ra một
vấn đề mới cho việc nghiên cứu xa hơn.

Tác giả

Nguyễn Minh Hải

Nhà xuất bản

ĐHCN

Năm xuất bản

2014

Người hướng dẫn

Nguyễn Trí Thành

Định danh

00050004258

Kiểu

text

Định dạng

text/pdf

Nhà xuất bản

Khoa công nghệ thông tin,

Trường đại học Công nghệ

Các đánh giá

Hiện chưa có đánh giá cho sản phẩm.

Hãy là người đầu tiên đánh giá “Một giải thuật Tri-train chỉnh sửa và ứng dụng vào bài toán phân lớp câu hỏi”

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *