ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ NGỌC ANH NGHIÊN CỨU PHƢƠNG PHÁP LÀM TĂNG
CHẤT LƢỢNG PHÂN LỚP CÂU HỎI TRONG
HỆ THỐNG HỎI ĐÁP 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Ĩ HỆ THỐNG THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: TS.NGUYỄN TRÍ THÀNH
Hà Nội - 2013
ĐẠI HỌC QUỐC GIA HÀ NỘI

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ 6
MỞ ĐẦU 7
Chƣơng 1. Giới thiệu bài toán 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 10
1.3. Bài toán phân lớp câu hỏi 11
Chƣơng 2. Các công trình nghiên cứu liên quan 13
2.1. Các đề tài nghiên cứu liên quan 13
2.2. Các hướng giải quyết bài toán phân lớp câu hỏi hiện nay 18
2.3. Lựa chọn định hướng giải quyết bài toán của luận văn 19
Chƣơng 3. Mô hình giải quyết bài toán 20
3.1. Lựa chọn giải pháp và mô hình giải quyết bài toán 20
3.2. Cơ sở lý thuyết 20
3.2.1. Học bán giám sát 20
3.2.2. Các thuật toán học bán giám sát 21
3.2.3. Tri-Train 21
3.2.3.1. Tri-Train gốc 21
3.2.3.2. Tri-Train cải tiến 23
3.3. Giải pháp cải tiến 25
3.3.1. Đề xuất cải tiến 25
3.3.2. Công việc xử lý đặc trưng 26
3.3.2.1. Valuefit 26
3.3.2.2. Related 31
3.3.2.3. N-grams 34
3
Nghiên cứu phương pháp làm tăng chất lượng phân lớp câu hỏi trong hệ thống hỏi đáp
Chƣơng 4. Thực nghiệm 36
4.1. Dữ liệu và công cụ cho thực nghiệm 36
4.2. Kết quả xây dựng các đặc trưng 37
4.2.1. Value Fit 37

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 5
Nghiên cứu phương pháp làm tăng chất lượng phân lớp câu hỏi trong hệ thống hỏi đáp
DANH MỤC CÁC BẢNG
Bảng 2.1: Phân lớp 6 mục thô và 50 mục tinh được đưa ra bởi Li và Roth
(2002).
6
Nghiên cứu phương pháp làm tăng chất lượng phân lớp câu hỏi trong hệ thống hỏi đáp
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1: Hệ thống hỏi đáp tự động.
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 2.1: 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 2.2: Các hướng giải quyết bài toán phân lớp câu hỏi.
Hình 4.1: Hiệu quả phân lớp của ValueFit với tập train 5500 câu hỏi.

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 đầy đủ 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 cải tiến 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. Cảm ơn gia đình, bạn bè cùng những người thân
luôn bên cạnh tác giả giúp tác giả vượt qua những khó khăn trong cuộc sống.
Hà Nội, ngày 06 tháng 10 năm 2013
Nguyễn Thị Ngọc Anh
8
Nghiên cứu phương pháp làm tăng chất lượng phân lớp câu hỏi trong hệ thống hỏi đáp
Chương 1. Giới thiệu bài toán
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

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.

Hình 1.1: Hệ thống hỏi đáp tự động.
10
Nghiên cứu phương pháp làm tăng chất lượng phân lớp câu hỏi trong hệ thống hỏi đáp
Bên cạnh đó các sản phẩm thương mại liên quan đến QA (hình 1.1) cũng
được các công ty phát triển như: Yahoo Answers của Yahoo
hệ thống hỏi đáp của Google
(phiên bản tiếng Việt được gọi là “Hệ thống

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
Nghiên cứu phương pháp làm tăng chất lượng phân lớp câu hỏi trong hệ thống hỏi đáp
A được xếp
vào lớp i

j
,c
i
> giá trị T (True = 1) nghĩa là q
i
được đánh giá là thuộc
nhóm c
i
, và ngược lại nếu <q
j
,c
i
> bằng F (Fales=0) nghĩa là q
i
không thuộc
nhóm c
i
. 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
13
Nghiên cứu phương pháp làm tăng chất lượng phân lớp câu hỏi trong hệ thống hỏi đáp
Chương 2. Các công trình nghiên cứu liên quan
Trong chương này tác giả sẽ trình bày sơ lược một vài đề tài nghiên cứu liên
quan đến bài toán phân lớp câu hỏi theo trình tự thời gian. Phần cuối của chương
tác giả tổng kết lại khung nhìn chung của các hướng giải quyết bài toán phân lớp
câu hỏi hiện nay. Dựa trên việc khảo sát những thành tựu và khó khăn của các
hướng giải quyết này tác giả đưa ra định hình ban đầu cho việc giải quyết bài
toán của mình.
2.1. 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

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 2.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,
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

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ữ.
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
16
Nghiên cứu phương pháp làm tăng chất lượng phân lớp câu hỏi trong hệ thống hỏi đáp
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 các câu hỏi và các câu trả lời phù hợp. Ngoài thừa kế sự khó khăn của phân
tích chủ quan cho các câu hỏi người dùng thực, họ còn chỉ ra rằng bằng cách
ứng dụng CoCQA cho công việc này, giúp cải thiện đáng kể hiệu quả dự báo và
17
Nghiên cứu phương pháp làm tăng chất lượng phân lớp câu hỏi trong hệ thống hỏi đáp
thực chất giảm bớt yêu cầu kích thước dữ liệu luyện.
Năm 2009, nhóm tác giả Mohan John Blooma, Dion Hoe-Lian Goh, Alton
Yeow Kuan Chua đã trình bày nghiên cứu về phân lớp câu hỏi đơn giản. Họ sử
dụng phương pháp SVM và đưa ra kết luận rằng SVM là giải pháp mang lại hiệu
quả phân lớp tốt nhất trong các nghiên cứu của họ. Nghiên cứu [1] đã được ứng
dụng để phân lớp theo cấp bậc dựa trên thuật toán học máy SVM với các câu hỏi
của người dùng được lấy từ hệ thống hỏi đáp của Yahoo. Điểm nổi bật của
nghiên cứu này là các tác giả đã cố gắng trực tiếp phân lớp các câu hỏi phức tạp
là các câu hỏi của người dùng thực. Họ đã sử dụng cả bộ phân lớp thô và bộ
phân lớp tinh để đánh giá hiệu quả của nghiên cứu và đưa ra một ma trận phân
tích các kết quả nghiên cứu của mình.
Ali Harb, Michel Beigbeder, Kristine Lund và Jean-Jacques Girardot đã trình
bày một phương pháp cải thiện chất lượng phân lớp câu hỏi theo định hướng tập
trung vào phân tích ngôn ngữ và phương pháp tiếp cận thống kê vào năm 2011
[2]. Họ đã đề xuất ra hai phương pháp phân lớp câu hỏi mở rộng. Họ đã nghiên
cứu về giá trị đại diện các câu hỏi, trọng số và các thuật toán học máy và làm
các thực nghiệm trên dữ liệu thực tế. Kết quả thực nghiệm cũng đã chỉ ra những
dấu hiệu tốt trong việc cải thiện chất lượng phân lớp câu hỏi.
Năm 2012, trong bài báo [7], Jinzhong Xu và các cộng sự đã đưa ra một giải
pháp phân lớp câu hỏi dựa trên SVM và sự tương tự về ngữ nghĩa của câu hỏi.
Nó được ứng dụng thực tế trong một hệ thống hỏi đáp trực tuyến về du lịch. Với
hai mức phân lớp câu hỏi: SVM được sử dụng để phân lớp các câu hỏi ở mức
thô và mô hình tương tự về mặt ngữ nghĩa được sử dụng để phân loại câu hỏi ở
mức sâu hơn. Nhờ sử dụng khái niệm trọng số của miền dữ liệu họ đã cải thiện
được chất lượng của các đặc trưng và mô hình tương tự về ngữ nghĩa của câu

Keywords
(Các từ khóa)
Regular expresstions
(Các biểu thức chính quy)
Mô hình
ngôn ngữ
Học máy

SNoW
SVM
DT
MEMNN
NB
Rule-Based
(Dựa trên luật)

Hình 2.2: Các hướng giải quyết bài toán phân lớp câu hỏi.
Đối với cách tiếp cận dựa trên các luật: việc phân lớp câu hỏi dựa vào một số
các luật được thiết lập bằng tay. Các luật này có được là do đề xuất từ các
chuyên gia. Đối với cách tiếp cận này, một loạt các biểu thức thông dụng
(regular expression) được tạo ra để so khớp với câu hỏi từ đó quyết định phân
lớp của câu hỏi và loại câu trả lời. Nhưng nó có một số hạn chế như sau:
- Sự phân lớp dựa trên các luật gặp nhiều khó khăn và tốn nhiều thời gian
xử lý do dựa trên kiến thức chủ quan của con người trên một tập dữ liệu
câu hỏi.
- Có sự giới hạn về mức độ bao quát và phức tạp trong việc mở rộng phạm
19
Nghiên cứu phương pháp làm tăng chất lượng phân lớp câu hỏi trong hệ thống hỏi đáp
vi của hệ thống.
Trong ca

p na
̀
y , classifier (bô
̣
phân lơ
́
p ) sẽ được học một cách có k iê
̉
m soa
́
t hoặc
không kiểm soát trên tập mẫu. Các thuật toán học máy hay dùng bao gồm: mạng
nơ-ron (Neural NetWork), xác suất có điều kiện (Naïve Bayes), mô hình cực đại
Entropy (Maximum Entropy), cây quyết định (decision Tree), người láng giềng
gần nhất (Nearest-Neighbors), mạng lọc thưa (Sparse Network of Winnows -
SNoW), máy hỗ trợ vector (Support Vector Machine - SVM), Vơ
́
i ca
́
ch tiếp
câ
̣
n học máy, ta dễ dàng thấy nó sẽ gia
̉
i quyết đươ
̣
c nhiều ha
̣
n chế tư
̀

đưa ra đề xuất của mình cải tiến Tri-Train bằng cách thay vì sử dụng hai khung
nhìn hai thuật toán thì sử dụng ba khung nhìn cùng với các đề xuất xây dựng các
bộ dữ liệu đặc trưng mới (khung nhìn) nhằm mục đích cải tiến chất lượng các
khung nhìn và tạo ra sự phong phú giữa các khung nhìn để phát huy được hết
điểm mạnh của Tri-Train. Phần cuối cùng, tác giả trình bày kỹ việc tạo ra các
khung nhìn mới.
3.1. Lựa chọn giải pháp và mô hình giải quyết bài toán
Trong phạm vi luận văn, tác giả lựa chọn học bán giám sát và cải tiến thuật
toán Tri-Train để nâng cao chất lượng phân lớp câu hỏi.
3.2. Cơ sở lý thuyết
3.2.1. Học bán giám sát
Trong khoa học máy tính, học bán giám sát là một lớp của kỹ thuật học máy,
sử dụng cả dữ liệu đã gán nhãn và chưa gán nhãn để huấn luyện - điển hình là
một lượng nhỏ dữ liệu có gán nhãn cùng với lượng lớn dữ liệu chưa gán nhãn.
Học bán giám sát đứng giữa học không giám sát (không có bất kì dữ liệu có
nhãn nào) và có giám sát (toàn bộ dữ liệu đều được gán nhãn). Nhiều nghiên cứu
cho thấy dữ liệu không gán nhãn, khi được sử dụng kết hợp với dữ liệu có gán
nhãn, có thể cải thiện đáng kể độ chính xác. Để gán nhãn dữ liệu cho một bài
toán học máy thường đòi hỏi một chuyên viên có kỹ năng để phân loại bằng tay
các mẫu huấn luyện. Chi phí cho quá trình này khiến tập dữ liệu được gán nhãn
hoàn toàn trở nên không khả thi, trong khi dữ liệu gán nhãn thường tương đối rẻ
tiền. Vì lý do này, học bán giám sát có giá trị thực tiễn lớn lao.
Bài toán phân lớp câu hỏi đã được nghiên cứu và giải quyết bằng phương
pháp học có giám sát từ cách đây hơn 10 năm, tuy nhiên chi phí cho việc gán
nhãn là khá cao và số lượng mẫu cần thiết là khá lớn. 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 áp dụng cho việc
khai thác dữ liệu chưa được gán nhãn. Năm 2008 Nguyễn Trí Thành cùng nhóm
nghiên cứu của mình đã công bố giải thuật Tri-Train cải tiến với đề xuất khắc
phục nhược điểm của Tri-Train mà Zhou và Li đã đề xuất năm 2005 đồng thời
làm các thử nghiệm kiểm tra chất lượng của thuật toán khi đưa vào giải quyết

nào, một mẫu chưa được gán nhãn cũng có thể được gán nhãn giống với nhãn
được hai bộ phân lớp còn lại “đồng ý”. Ví dụ: nếu h1 và h2 cùng “đồng ý” nhãn
của một mẫu x trong tập chưa được gán nhãn U thì x có thể được gán nhãn cho
h3. Rõ ràng trong sơ đồ này nếu dự đoán của h1 và h2 là đúng thì h3 cũng được
nhận một giá trị mới cho vòng lặp tiếp theo, nếu không thì h3 sẽ nhận một mẫu
với nhãn sai. Tuy nhiên Zhou và Li đã khẳng định trong trường hợp tệ hơn thì sự
gia tăng của tỷ lệ lỗi có thể được bù lại nếu số lượng mẫu được gán nhãn mới là
đủ.
22
Nghiên cứu phương pháp làm tăng chất lượng phân lớp câu hỏi trong hệ thống hỏi đáp
Do mỗi bộ phân lớp đều được luyện từ thủ tục Bootstrap-Sampling của cùng
một tập nguồn đã được gán nhãn theo một thứ tự tạo ra các bộ phân lớp khác
nhau. Nếu tất cả các bộ phân lớp được đồng nhất và có thể một trong ba bộ phân
lớp vẫn còn các mẫu chưa được gán lại nhãn mới bởi hai bộ phân lớp còn lại thì
chẳng khác nào “tự luyện” (self-train) với một bộ phân lớp đơn.
Giả mã của thuật toán được mô tả tại tài liệu [10] như sau:

1
2
3
4
5
6
7
8
9
10
11
12
13

i
(i є {1 3}) changes
for i є {1 3} do
L
i
← ø; update
i
← FALSE
e
i
← MeasureError (h
j
&h
k
) (j, k≠i)
if (e
i
<e’
i
) then
for every x є U do
if h
j
(x) = h
k
(x) (j, k≠i)
then L
i
← L
i

←TRUE
else if l’
i
> e
i
/(e’
i
- e
i
)
then L
i
← Subsample(L
i
,[(e’
i
l’
i
)/e
i
- 1])
update
i
←TRUE
end for
for i є {1 3} do
if update
i
= TRUE then
23

- e
i
’: là tỷ lệ lỗi của h
i
trong lần lặp thứ (t-1). Với giả thuyết tỷ lệ lỗi ban
đầu là nhỏ hơn 0.5, e
i
’ được khởi tạo là 0.5.
- e
i
: là tỷ lệ lỗi của h
i
tại vòng lặp thứ t.
- L
i
: là tập hợp mẫu được gán nhãn cho h
i
tại vòng lặp thứ t.
- l
i
’: là kích thước của L
i
tại vòng lặp thứ (t-1), trong vòng lặp đầu tiên, nó
được ước lượng bằng (e
i
/( e
i
’- e
i
) +1).

b) Tri-Train with multiple learning algorithms (Tri-Train đƣợc cải tiến
với nhiều giải thuật học)
Tri-Train(L,U,Learn
1
,Learn
2
,Learn
3
)
for i є {1 3} do

h
i
← Learn
i
(L)
e’
i
← 0.5; l’
i
← 0
end for
…
h
i
← Learn
i
(L L
i
); e’


25
c) Tri-Train with multiple learning algorithms and views (Train đƣợc
cải tiến sử dụng nhiều giải thuật và khung nhìn)
Tri-Train(L,U,Learn
1
,Learn
2
,Learn
3
)
for i є {1 3} do

h
i
← Learn
i
(View
i
(L))
e’
i
← 0.5; l’
i
← 0
end for
…
h
i
← Learn

h
i
từ View
i
của tập nguồn ban đầu L.
Các thực nghiệm của [10] đã sử dụng hai giải thuật SVM và MEM với hai
khung nhìn bag-of-word và bag-of-pos&word. Hai bộ phân lớp đầu tiên sử dụng
giải thuật thứ nhất và hai khung nhìn khác nhau, bộ phân lớp thứ ba sử dụng giải
thuật còn lại với đặc trưng bag-of-word:
- Bộ phân lớp thứ nhất: giải thuật SVM, đặc trưng bag-of-word.
- Bộ phân lớp thứ hai: giải thuật SVM, đặc trưng bag-of-pos&word.
- Bộ phân lớp thứ ba: giải thuật MEM, đặc trưng bag-of-word.
Trong đó, bag-of-word: là đặc trưng chỉ bao gồm các từ gốc trong câu, bag-
of-pos&word: là đặc trưng bao gồm từ gốc và các cấu trúc của nó.
3.3. Giải pháp cải tiến
3.3.1. Đề xuất cải tiến
Luận văn tập trung vào nghiên cứu cách cải thiện chất lượng phân lớp câu
hỏi sử dụng học bán giám sát trên cơ sở cải tiến giải pháp Tri-Train mà Nguyễn
Trí Thành đã đưa ra ở [10] theo hướng: thay vì sử dụng hai khung nhìn và hai
giải thuật khác nhau ta sử dụng ba khung nhìn khác nhau làm các tập dữ liệu đầu
vào. Ngoài ra một điều kiện để đảm bảo chất lượng phân lớp của Tri-Train được
phát huy hiệu quả, cần có các bộ đặc trưng với chất lượng phân lớp tốt và độc
lập nhau (khác nhau càng nhiều càng tốt). Ở đây, ngoài các bộ đặc trưng đã
được nghiên cứu và sử dụng trước đó: WordRoot, Pos,… tác giả đưa ra ba đề
xuất đặc trưng khác, mục đích cuối cùng là chuẩn bị các bộ dữ liệu (các khung
nhìn) phong phú và độc lập nhau.
Cải tiến của luận văn so với đề xuất của [10] là sử dụng ba khung nhìn cho
giải thuật Tri-Train. Trong phần thực nghiệm tác giả đã xây dựng chín khung
nhìn tổ hợp thành các bộ dữ liệu đầu vào cho Tri-Train để thực hiện các thử
nghiệm của mình.