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

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

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.

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

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

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 <q
j
,c
i
> giá trị T (True = 1) nghĩa là q
i
được đánh giá là thuộc
nhóm c
i

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

Class label
Question text
Feature Extraction
Classification
m SVM
Classifiers
Combiner
One of n class
labels
Feature vectorHì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

và bán giám sát” bằng việc cải tiến giải thuật Tri-Train và đưa ra hai đề xuất cải
tiến để loại bỏ nhược điểm bootstrap-sample trong giải thuật Tri-Train gốc [10].
Trong thực tế, dữ liệu câu hỏi có đặc điểm là thưa và phân bố không đều. Do
phân bố không đều nên sau thủ tục lấy mẫu Bootstrap-Sampling, mỗi tập gán
nhãn mới nhất được tạo ra sẽ bị mất một số câu hỏi so với tập có nhãn ban đầu.
Nếu những câu hỏi bị mất này lại nằm trong các lớp có rất ít câu hỏi thì tỷ lệ lỗi
sẽ tăng trong mỗi bộ phân lớp khi luyện từ tập dữ liệu này. Đ ể khắc phục nhược
điểm này, Nguyễn Trí Thành đã đưa ra giải pháp sử dụng nhiều hơn một giải
thuật cho ba bộ phân lớp. Mỗi bộ phân lớp được khởi tạo từ tập được gán nhãn.
Thử nghiệm của ông cũng chỉ ra rằng điều kiện cần thiết để tăng hiệu quả của
phân lớp là cả ba bộ phân lớp đều phải có hiệu quả phân lớp tương đương nhau.
Nghiên cứu [3] của Baoli Li, Y. Liu và Eugene Agichtein năm 2008 đã giới
thiệu hệ thống CoCQA cho phân lớp bán giám sát của các câu hỏi và các câu trả
lời trong hệ thống thảo luận CQA. CoCQA là một nền tảng đồng luyện cho mô
hình tương tác nguyên bản trong trao đổi hỏi đáp nó có thể khai thác cấu trúc
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à
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

cứu và có những thành công nhất định nhưng gặp phải khó khăn khi mở rộng hệ
thống. Hướng giải quyết dựa vào xác suất có hai hướng chính là giải quyết dựa
vào mô hình ngôn ngữ và học máy. Trong đó học máy là hướng giải quyết được
quan tâm và đang mở ra nhiều triển vọng. Trong các nghiên cứu từ 2002 đến
bây giờ, đã có nhiều nghiên cứu, thử nghiệm chứng minh rằng giải thuật SVM tỏ
ra có ưu thế hơn đối với bài toán phân lớp câu hỏi. Ngoài ra, với tính chất phong
phú, phức tạp, đa nghĩa của các câu hỏi trong hệ thống thực tế, thuật toán học
bán giám sát đang tỏ ra có ưu thế hơn cả trong các phương pháp học máy.
18!
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
Các hướng tiếp
cận cho phân lớp
câu hỏi
Statistical
(Xác suất)
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)

tâm đ ến hướ ng tiếp cận thứ hai - học máy. Trải qua hơn 10 năm kể từ khi hướng
giải quyết học máy áp dụng cho bài toán phân lớp câu hỏi được đưa ra, đã có rất
nhiều thuật toán học máy được nghiên cứu áp dụng đồng thời đối chiếu so sánh
hiệu quả lẫn nhau. Trong hệ thống các giải pháp học máy, định hướng học có
giám sát đã đạt được nhiều thành công, nhiều nghiên cứu của các tác giả nổi
tiếng đã đạt được kết quả phân lớp gần như tuyệt đối. Tuy nhiên trong phạm vi
luận văn tác giả lựa chọ n nghiên cứu học bán giám sát vì đây là đ ịnh hư ớng
đang mở ra nhiều triển vọng với chi phí thấp và kết quả phân lớp có mức tin cậy
đủ chấp nhận được.

20!
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 2. Mô hình giải quyết bài toán
Trong chương này, tác giả trình bày khái quát về họ c bán giám sát và điểm
sơ qua một vài phương pháp sử dụng cho học bán giám sát cùng với các ưu
nhược điểm của chúng. Tiếp theo tác giả trình bày kỹ phần lý thuyết về giải
thuật Tri-Train và các đề xuất cải tiến của Nguyễn Trí Thành. 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.
2.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.
2.2. Cơ sở lý thuyết
2.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

mình đã đưa ra những đề xuất khắc phục một vài nhược điểm của giải thuật này.
Trong phạm vi luận văn, tác giả lựa chọn Tri-Train để nghiên cứu, cải tiến và áp
dụng vào bài toán phân lớp câu hỏi. Do vậy ở phần tiếp theo tác giả sẽ trình bày
kĩ hơn về thuật toán Tri-Train và đưa ra đề xuất cải tiến.
2.2.3. Tri-Train
2.2.3.1. Tri-Train gốc
Giải thuật Tri-Train gốc mà Zhou và Li đề xuất [13] sử dụ ng ba bộ phân lớp
với cùng một giải thuật. Tri-Train: luyện ba phân lớp với cùng một thuật toán
giống nhau. Trong giải thuật này, 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ó. Ba bộ phân
lớp h1, h2, h3 được khởi tạo là ba tập được luyện bởi thủ tục Bootstrap-
Sampling của cùng một tập nguồn đã được gán nhãn. Đối với bất kì bộ phân lớp
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à
đủ.
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.
22!
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ả mã của thuật toán được mô tả tại tài liệu [10] như sau:

1

S
i
← BootstrapSample(L)
h
i
← Learn(S
i
)
e’
i
← 0.5; l’
i
← 0
end for
repeat until none of h
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 (l’
i
< |L
i
|) then
if (e
i
|L
i
|<e’
i
l’
i
) then update
i
←TRUE
else if l’
i
> e
i
/(e’
i
- e
i
)
then L
i
← Subsample(L
i
,[(e’

!:!
!
! !!
!!!∈!!"#$!
!"# !"#

Trong giả mã thuật toán trên:
23!
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
- Learn: là một giải thuật phân lớp.
- L: Tập nguồn.
- S
i
: là các tập hợp được gán nhãn từ thủ tục Bootstrap-Sampled từ cùng
một tập nguồn L.
- h
i
: là bộ phân lớp thứ i
- 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

- Đề xuất sử dụng nhiều hơn một giải thuật cho ba bộ phân lớp, với ràng
buộc là cho hiệu quả tương tự nhau đối với cả ba bộ phân lớp.
- Đề xuất sử dụng nhiều hơn một khung nhìn, mỗi bộ phân lớp có thể được
luyện từ các tập được gán nhãn gốc với với các không gian đặc trưng khác
nhau.
1
2
3
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

24!
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
4
5
6

25
h

: là giải thuật phân lớp thứ i
- Các bước thực hiện giống như ở thuật toán Tri-Train gốc (a), chỉ khác ở
chỗ thay vì sử dụng hàm BootstrapSample(L) để tạo ra tập S
i
, rồi sử dụng
thuật toán Learn để sinh ra bộ phân lớp h
i
thì ta sử dụng thuật toán thứ i
để tạo ra h
i
từ tập nguồn L ban đầu.

1
2
3
4
5
6

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

i
|
…
Trong giả mã thuật toán trên:
- View
i
: là khung nhìn thứ i
- Các bước thực hiện giống như ở thuật toán Tri-Train được cải tiến với
nhiều giải thuật học (b), chỉ khác ở chỗ thay vì sử dụng thuật toán Learn
i

để tạo ra h
i
từ tập nguồn L ban đầu thì ta dùng thuật toán Learn
i
để tạo ra
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:
25!
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
- 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.

Tri-Train sử dụng nhiều view
Tri-Train(L,U,Learn)
for i є {1 3} do
L
i
=GenerateView(L);
h
i
← Learn
i
(L)
e’
i
← 0.5; l’
i
← 0
end for
…