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

VŨ THỊ TUYẾN

MỘT SỐ MÔ HÌNH HỌC MÁY TRONG PHÂN LOẠI
CÂU HỎI

Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60480104

TÓM TẮT LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Hà Nội -2016


1

MỤC LỤC
MỤC LỤC ....................................................................................................................... 1
LỜI MỞ ĐẦU ................................................................................................................. 3
Chương 1: TỔNG QUAN VỀ PHÂN LOẠI CÂU HỎI ................................................. 4
1.1. Tổng quan về hệ thống hỏi đáp ............................................................................ 4
1.1.1.Đặt vấn đề ....................................................................................................... 4
1.1.2. Hệ thống hỏi đáp (Question Answering System) .......................................... 4
1.1.2.1. Giới thiệu ................................................................................................ 4
1.1.2.2. Cấu trúc của một hệ thống hỏi đáp ......................................................... 4
1.1.2.3. Tại sao phải phân loại câu hỏi? .............................................................. 5
1.2. Bài toán phân loại câu hỏi .................................................................................... 6
1.2.1. Định nghĩa phân loại câu hỏi ......................................................................... 6

3.5. Huấn luyện và kiểm thử với LibSVM ................................................................ 20
3.6. Kết quả thực nghiệm........................................................................................... 21
3.7. Kết luận............................................................................................................... 21
TỔNG KẾT ................................................................................................................... 22


3
LỜI MỞ ĐẦU
Ngày nay, với sự phát triển mạnh mẽ của Internet toàn cầu cùng với nhu cầu
tìm kiếm thông tin ngày càng cao của con người đòi hỏi hệ thống hỏi đáp ngày một
thông minh hơn.Những thắc mắc của người dùng dướidạng truy vấn cần được tìm
kiếm và trả về một cách ngắn gọn, súc tích và chính xác nhất những gì mà họ mong
muốn.
Một trong những thành phần quan trọng ảnh hưởng trực tiếp đến kết quả tìm
kiếm trong hệ thống hỏi đáp là giai đoạn phân loại câu hỏi.Một phân loại tốt sẽ giúp
đưa ra câu trả lời chính xác hơn.Đã có nhiều phương pháp tiếp cận được đưa ra cho bài
toán phân loại này, tuy nhiên phương pháp học máy là được áp dụng nhiều hơn cả.
Chính vì lý do này mà tác giả chọn và nghiên cứu đề tài “Một số mô hình học máy
trong phân loại câu hỏi”. Luận văn bao gồm 3 phần như sau:
Chương 1: Tổng quan về phân loại câu hỏi
Chương này trình bày tổng quan về phân loại câu hỏi, giới thiệu về hệ thống hỏi
đáp, bài toán phân loại câu hỏi, cách tiếp cận giải quyết bài toán, tổng quan về các tiếp
cận học máy như: biểu diễn câu hỏi, phân lớp câu hỏi, các đặc trưng câu hỏi.
Chương 2: Một số mô hình học máy trong phân loại câu hỏi
Chương này tập trung trình bày về 3 bộ phân loại thường được sử dụng: Naïve
Bayes, K-láng giềng gần, Máy vector hỗ trợ và liệt kê một số bộ phân loại khác. So
sánh hiệu suất phân loại của các bộ phân loại đó dựa trên kết quả tham khảo.
Chương 3: Thực nghiệm và đánh giá
Áp dụng bộ phân loại SVM thực hiện thí nghiệm trên tập dữ liệu UIUC, lựa
chọn đặc trưng bag-of-word.Nhận xét kết quả trả về.

như lĩnh vực y học.
 Hệ thống hỏi đáp miền mở (Open-domain Question Answering): hệ thống
này liên quan đến các câu hỏi gần như về tất cả mọi thứ.
1.1.2.2. Cấu trúc của một hệ thống hỏi đáp
Có nhiều hệ thống QA đã được đưa ra, nhưng hầu hết chúng đều tuân theo một
khung làm việc chung. Thông thường, một hệ thống hỏi đáp xử lý 3 nhiệm vụ sau [6]:


5
xử lý câu hỏi, xử lý tài liệu và xử lý câu trả lời. Hình 1.1 dưới đây là kiến trúc tổng
quan về một hệ thống hỏi đáp.

Hình 1.1: Kiến trúc một hệ thống hỏi đáp
1.1.2.3. Tại sao phải phân loại câu hỏi?
Về cơ bản có hai động cơ thúc đẩy chính về phân loại câu hỏi: xác định câu trả
lời và lựa chọn chiến lược tìm kiếm.
Xác định câu trả lời: biết được loại câu hỏi không chỉ có thể thu gọn được
không gian tìm kiếm cần tìm câu trả lời, nó còn có thể tìm kiếm chính xác câu trả lời
trong một tập lớn các ứng viên trả lời. Cho ví dụ biết được loại của câu hỏi “Who was
the president of U.S. in 1934?” có kiểu là “human”, hệ thống trả lời có thể chỉ quan
tâm đến các ứng viên là tên các thực thể có kiểu là “human” mà không cần phải kiểm
tra toàn bộ các đoạn văn bản để tìm ở đâu có thể chứa câu trả lời hoặc không.
Lựa chọn chiến lược tìm kiếm: lớp câu hỏi có thể được sử dụng để lựa chọn
chiến lược tìm kiếm khi câu hỏi được viết dưới dạng một truy vấn để tìm kiếm trên
máy tìm kiếm. Cho ví dụ đưa ra câu hỏi “What is a pyrotechnic display ?”. Xác định


6
được lớp của câu hỏi này là “definition”, mẫu tìm kiếm cho việc xác định câu trả lời
có thể dùng như “pyrotechnic display is a ...” or “pyrotechnic displays are ...”, nó tốt

Theo [3,6]có 2 cách tiếp cận để phân loại câu hỏi: dựa trên luật (rule-based)và
dựa trên học máy (machine learning based). Ngoài ra, có một vài cách tiếp cận lai là sự
kết hợp của tiếp cận dựa trên luật và học máy.
1.3.1. Tiếp cận dựa trên luật
Đây là cách tiếp cận được cho là đơn giản nhất để phân loại câu hỏi. Trong cách
tiếp cận này thì việc phân loại câu hỏi dựa vào các luật ngữ pháp viết 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 chính quy (regular expression) được tạo ra để so khớp với câu hỏi từ đó quyết
định phân loại của câu hỏi và loại câu trả lời.


7
1.3.2. Tiếp cận dựa trên học máy
Đây là cách tiếp cận được sử dụng phổ biến để giải quyết bài toán phân loại câu
hỏi.Cách tiếp cận này sẽ thay thế các kiến thức chuyên môn bằng một tập lớn các câu
hỏi được gán nhãn (tập dữ liệu mẫu).Sử dụng tập này, một bộ phân lớp sẽ được huấn
luyện có giám sát. Một số thuật toán thường được sử dụng như là: Mạng nơ-ron
(Neural NetWork), tính xác suất Naïve Bayes, Maximum Entropy , cây quyết định
(decision Tree) , lân cận (Nearest-Neighbors), Mạng lọc thưa (Sparse Network of
Winnows - SNoW), Máy Vector hỗ trợ (Support Vector machine-SVM) ... Cách tiếp
cận bằng học máy đã giải quyết được các hạn chế trong cách tiếp cận dựa trên luật.
1.4. Biểu diễn câu hỏi
Một trong những nhiệm vụ đầu tiên trong việc xử lý phân loại câu hỏi là chọn
được một mô hình biểu diễn câu hỏi thích hợp. Tùy thuộc vào từng thuật toán phân
loại khác nhau mà chúng ta có mô hình biểu diễn riêng. Một trong những mô hình đơn
giản và thường được sử dụng là mô hình không gian vector.
Trong mô hình này, các câu hỏi được thể hiện trong một không gian có số chiều
lớn, trong đó mỗi chiều của không gian tương ứng với một từ trong câu hỏi. Phương
pháp này có thể biểu diễn một cách hình tượng như sau: mỗi câu hỏi được biểu diễn
dưới dạng ⃗ (vector đặc trưng của câu hỏi đó). Trong đó, ⃗

Li và Roth đưa ragồm 2 cấp theosự phân loại ngữ nghĩa tựnhiên của câu trả lời trong
hội nghị TREC. Cấu trúc phân cấp bao gồm 6 lớp thô: ABBREVIATION (viết tắt),
ENTITY (thực thể),DESCRIPTION (mô tả), HUMAN (con người), LOCATION (địa
điểm) và NUMERIC VALUE (giá trị số) cùng với 50 lớp con (fine class).
1.6. Các đặc trưng phân loại
1.6.1. Các đặc trưng về từ vựng
Các đặc trưng từ vựng của một câu hỏi thường được rút trích dựa trên ngữ cảnh
của các từ của câu hỏi, nghĩa là, các từ đó xuất hiện trong một câu hỏi. Trong nhiệm
vụ phân loại câu hỏi, một câu hỏi được biểu diễn giống như biểu diễn tài liệu trong mô
hình không gian vectơ, tức là, một câu hỏi là một vectơ mà được mô tả bởi các từ bên
trong nó. Do đó một câu hỏi x có thể được biểu diễn như sau:

Trong đó: xi là tần số xuất hiện của từ i trong câu hỏi x và N là tổng số các từ. Do
sự thưa thớt của các đặc trưng, chỉ các đặc trưng có giá trị khác không mới được giữ
lại trong vectơ đặc trưng. Vì vậy đôi khi các câu hỏi cũng được biểu diễn dưới hình
thức sau:
{

(

)}

Trong đó: ti là từ thứ i trong câu hỏi x và fi là tần số xuất hiện của ti trong câu hỏi
x. Không gian đặc trưng này được gọi là các đặc trưng bag-of-words và thứ tự của các
từ trong câu hỏi là không quan trọng trong cách biểu diễn. Việc biểu diễn các câu hỏi
theo công thức (1.2) làm cho kích thước của tập mẫu tương đối nhỏ mặc dù kích thước
của không gian đặc trưng là rất lớn.
Tần số xuất hiện của các từ trong câu hỏi (các giá trị của đặc trưng) có thể được
xem như là giá trị trọng số, nó biểu thị cho tầm quan trọng của một từ trong câu hỏi.
Không gian đặc trưng bag-of-word còn được gọi là unigram. Unigram là một



10

Hình 1.2: Cây phân tích cú pháp sử dụng bộ phân tích Berkeley
Ý tưởng của việc trích rút từ đầu từ cây cú pháp đầu tiên được giới thiệu bởi
Collins [6]. Ông đã đề xuất một vài luật, được biết như là luật Collins, để xác định từ
đầu của một câu. Xem xét một luật ngữ pháp X → Y1...Yn trong đó X và Yi là nonterminal trong một cây cú pháp. Một thuật toán sử dụng tập các luật có sẵn để xác định
Y1...Yn là từ đầu hoặc một cây con chứa nó. Quá trình này sẽ được lặp lại cho đến khi
một head word được tìm thấy.
1.6.2.3. Biểu thức chính quy
Trong thực tế, một số câu hỏi vốn không có từ đầu. Chẳng hạn như với câu hỏi
“What is biosphere ?”, không có từ đầu nào phù hợp để góp phần phân loại như là
“definition”. Vấn đề tương tự cũng xuất hiện trong câu hỏi “Why does the moon turn
orange ?”, không có các từ nào trong câu hỏi này ngoại trừ từ để hỏi giúp bộ phân loại
phân loại câu hỏi này là “reason”.
Để định nghĩa một đặc trưng thay thế cho từ đầu của câu hỏi, nhóm tác giả
Huang đã giới thiệu một vài mẫu biểu thức chính quy để ánh xạ các kiểu của câu hỏi
tới một mẫu và sau đó sử dụng mẫu tương ứng như là đặc trưng. Danh sách các mẫu
của Huang [15] như sau:
DESC:def pattern 1 Các câu hỏi bắt đầu bằng what is/are, không bắt buộc theo
sau nó là a, an, hoặc the và tiếp theo là 1 hoặc nhiều từ.
DESC:def pattern 2 Các câu hỏi bắt đầu bằng what do/does và kết thúc là mean.
ENTY:substance pattern Các câu hỏi bắt đầu là what is/are và kết thúc là
composed of/made of/made out of.
DESC:desc pattern Các câu hỏi bắt đầu với what does và kết thúc là do.
ENTY:term Các câu hỏi bắt đầu là what do you call.
DESC:reason pattern 1 Các câu hỏi bắt đầu là what causes/cause.



=>physical entity -- (an entity that has physical existence)
=>entity -- (that which is perceived or known or inferred to have its
own distinct existence)


12
Chương 2: MỘT SỐ MÔ HÌNH HỌC MÁY TRONG PHÂN LOẠI CÂU HỎI
2.1. Thuật toán Naïve Bayes
2.1.1. Định lý
Thuật toán Naïve Bayesdựa trên định lý Bayes được phát biểu như sau:
|

|
Trong đó:

* P(X): Xác suất của sự kiện X xảy ra, không quan tâm đến Y
* P(Y): Xác suất của sự kiện Y xảy ra, không quan tâm đến X
* P(X|Y): Xác suất (có điều kiện)của sự kiệnX xảy ra, nếu biết rằng sự kiệnY
xảy ra
* P(Y|X): Xác suất hậu nghiệm của Y nếu biết X
Naïve Bayes classifer là một bộ phân loại xác suất dựa trên việc ứng dụng định lý
Bayes với giả định độc lập bền vững [13]. Một Naïve Bayes classifer độc lập điều kiện
giả định rằng sự hiện diện (hay không hiện diện) của một đặc trưng của một lớp học là
không liên quan đến sự có mặt (hay thiếu vắng) của bất kỳ đặc trưng nào khác. Áp
dụng cho bài toán phân loại, các dữ kiện cần có:
* D: tập dữ liệu huấn luyện đã được vector hóa dưới dạng ⃗
* Ci: phân lớp i, với i={1,2,…,m}
* Các thuộc tính x1,x2,…,xn độc lập điều kiện đôi một với nhau
Theo định lý Bayes:
|

 Tính xác suất P(Ci)
 Tính xác suất P(xk|Ci)
Bước 2: Xnew được gán vào lớp có giá trị lớn nhất theo công thức:
∏

|

Thuật toán Naïve Bayes áp dụng cho bài toán phân loại câu hỏi như sau:
Giai đoạn huấn luyện:
Input:
- Các vector đặc trưng của câu hỏi trong huấn luyện.
- Tập nhãn/lớp cho từng vector đặc trưng của tập huấn luyện.
Output:
- Các giá trị xác suất

và

Giai đoạn phân lớp:
Input:
- Các vector đặc trưng của câu hỏi trong huấn luyện.
- Các giá trị xác suất

và

( )

Output:
- Nhãn/phân loại của câu hỏi.
Gọi P(ck|qj) là xác suất mà câu hỏi qj có khả năng thuộc vào loại ck. Theo định lý
Bayes:


Ý tưởng của thuật toán này như sau: Để phân loại một câu hỏi mới, thuật toán sẽ
tính khoảng cách (có thể dựa vào các công thức tính khoảng cách như Euclide, Cosine,
…) của câu hỏi này đến tất cả các câu hỏi trong tập huấn luyện để tìm ra k câu hỏi có
khoảng cách gần nhất, gọi là k nearest neighbours (k láng giềng gần). Dùng khoảng
cách này, đánh trọng số cho tất cả các chủ đề đã có.Khi đó, trọng số của một chủ đề sẽ
được tính bằng tổng các khoảng cách từ câu hỏi cần phân loại đến các câu hỏi trong k
láng giềng mà có cùng chủ đề đó.Chủ đề nào không xuất hiện trong tập k câu hỏi sẽ có
trọng số bằng 0. Sau đó, các chủ đề được sắp xếp theo độ giảm dần của các trọng số và
chủ đề có trọng số cao sẽ được chọn làm chủ đề của câu hỏi cần phân loại.
Trọng số của chủ đề Ci đối với câu hỏi d được tính như sau:
∑
Trong đó:

(

) (

)


15
- KNN(d) là k láng giềng gần nhất của câu hỏi d
- (

)xác định câu hỏi djthuộc vào phân loại Ci với:
(

)


thỏa mãn:

Trong đó: w là một vector pháp tuyến của siêu phẳng và b đóng vai trò là tham
số của mô hình.
Để tìm được siêu phẳng phân cách có lề cực đại, xây dựng các vector hỗ trợ và
các siêu phẳng H1, H2 song song với H và có cùng khoảng cách đến H. Khi đó, với
mọi xi trong tập huấn luyện ta có 2 bất phương trình sau:
w.xi + b +1 với yi = +1
w.xi + b -1 với yi = -1


16
Và được viết lại như sau:
yi(w.xi + b) +1
hoặc yi(w.xi + b) - 1 0

Hình 2.2: Siêu phẳng với lề cực đại cho một SVM phân tách dữ liệu thuộc hai lớp.
Lúc này, những support vector xi thỏa mãn phương trình w.xi + b -1 thì nằm
trên siêu phẳng H1, và thỏa mãn phương trình w.xi + b +1 thì nằm trên siêu phẳng H2.
Khoảng cách lề giữa siêu phẳng H1 và H2 được tính như sau:
Gọi x0 là một điểm nằm trên siêu phẳng H và x1 là điểm nằm trên siêu phẳng H1.
Như vậy, (x0-x1)vuông góc với 2 siêu phẳng này. Các điểm này thỏa mãn hệ phương
trình sau:
{
Lấy hai đẳng thức của(2.12) trừ cho nhau, ta được:

Vì

vuông góc với siêu phẳng H và w cũng vuông góc với siêu phẳng


‖

‖ ‖

Từ (2.15) và (2.17) suy ra, khoảng cách phân hoạch giữa siêu phẳng H1và H2là
‖ ‖.
Do đó, để có biên lớn nhất thì ‖ ‖ phải nhỏ nhất hay nói cách khác là giải bài
toán tối ưu tìm

‖ ‖ với ràng buộc gi(x)= yi(w.xi + b) 1 với i=1,2,…,n.
‖ ‖ với ràng buộc gi(x)=yi(w.xi + b) 1

Để giải bài toán tối ưu tìm

với i=1,2,…,n. Ta đưa về phương trình Lagrange, bài toán trên trở thành:
{ ‖ ‖

∑

Trong đó

}
0} là các nhân tử Lagrange. Khi đó, tất cả các

điểm không nằm trên lề nghĩa là

đều không ảnh hưởng đến giá

trị hàm mục tiêu vì ta có thể chọn



18
∑
Với

∑∑

là hạt nhân đo độ tương tự giữa

.

Công thức (2.21) có thể được viết lại dưới dạng sau:
∑

∑∑

Có 4 loại hàm hạt nhân được giới thiệu: linear, popynomial, radial basis và
sigmoid. Loại đơn giản nhất là hàm hạt nhân tuyến tính cho hai câu hỏi

được xác

định như sau:
(

)

∑

2.4. Hiệu suất trong phân loại câu hỏi
Thông thường hiệu suất của bộ phân loại câu hỏi được đo bằng việc tính toán chính


2GB

3

Hệ điều hành

Windows

Bảng 3.2: Các công cụ phần mềm được sử dụng
STT

Tên phần mềm

Chức năng

Nguồn

1

LIBSVM 3.21

Phân loại câu hỏi

/>~cjlin/libsvm/

2

Eclipse Java EE


nghiệm của mình.
Ví dụ của một dòng dữ liệu trong tập dữ liệu UIUC:
HUM:ind Who was The Pride of the Yankees ?
Nguyên tắc phân loại đã được sử dụng để gán nhãn cho các câu hỏi là nguyên
tắc phân loại đã được giải thích trong chương 1.Nó bao gồm 6 lớp thô và 50 lớp mịn.
3.4. Xử lý dữ liệu
Để bắt đầu sử dụng với bộ thư viện này, ta cần phải xây dựng một tập tin huấn
luyện theo đúng dịnh dạng. Định dạng của tập tin chứa dữ liệu huấn luyện và tập tin
kiểm thử là:
<label><index1>:<value1><index2>:<value2>
Trong đó:
<label> là giá trị đích của tập huấn luyện. Đối với việc phân loại, nó là một số nguyên
xác định một lớp.
<index> là một số nguyên bắt đầu từ 1. Cụ thể trong bài toán phân loại nó đại diện cho
các đặc trưng.
<value> là một số thực. Giá trị này thể hiện mức độ liên quan của đặc trưng đối với
một phân loại nằm trong khoảng [-1,1]. Do các đặc trưng trong phân loại câu hỏi đều
là đặc trưng nhị phân nên lúc huấn luyện giá trị này sẽ là 1.
Câu hỏi “Who was the Pride of Yankees” sẽ được chuyển thành như sau:
44 1:1 15:2 24:2 98:1 235:1 1934:1 4376:1
ở đó số đầu tiên (44) cho biết số của lớp và các cặp còn lại (đặc trưng, giá trị) được
phân cách bởi một khoảng trống trong khi trong mỗi cặp được phân cách bởi dấu hai
chấm (:). Hơn nữa các cặp đặc trưng này nên được sắp xếp theo thứ tự tăng dần của số
các đặc trưng.
Khi tất cả các tập dữ liệu huấn luyện và kiểm tra được chuyển về định dạng như
trên, sau đó thực hiện huấn luyện bộ phân loại với tập dữ liệu huấn luyện và kiểm tra
lại nó trên tập dữ liệu kiểm tra độc lập.
3.5. Huấn luyện và kiểm thử với LibSVM
Sau khi có file với định dạng được chấp nhận bởi thư viện LIBSVM, thực hiện
huấn luyện và test. Trong giai đoạn này, khóa luận sử dụng ngôn ngữ lập trình Python


Bảng 3.4: Độ chính xác phân loại trên tập mịn với đặc trưng unigram và bigram
Đặc trưng
Unigram
Bigram

Độ chính xác
80,2%
73,8%

3.7. Kết luận
Như vậy, sau khi thực nghiệm đánh giá bộ phân loại SVM sử dụng 2 đặc trưng
unigram và bigram, nhận thấy rằng kết quả phân loại đạt được với độ chính xác khá
cao (80.2% trên tập mịn). Đặc trưng unigram cho kết quả phân loại cao hơn đặc trưng
bigram.


22
TỔNG KẾT
Phân loại câu hỏi là một vấn đề khó.Thực tế là máy cần phải hiểu được câu hỏi
và phân loại nó vào loại chính xác.Điều này được thực hiện bởi một loạt các bước
phức tạp.Luận văn này đã trình bày các kiến thức cơ bản của bài toán phân loại câu hỏi
và giới thiệu một số thuật toán để giải quyết bài toán phân loại.Tuy nhiên, luận văn chỉ
mang tính tìm hiểu và ứng dụng cái đã có, không có đề xuất hay cải tiến gì để làm tăng
độ chính xác phân loại. Ngoài ra, luận văn chỉ thực nghiệm trên ngôn ngữ Tiếng Anh
mà chưa mở rộng thực nghiệm sang ngôn ngữ Tiếng Việt.
Trong tương lai gần, hướng phát triển trước mắt của luận văn là cần tìm hiểu và
kết hợp các đặc trưng khác để làm tăng độ chính xác phân loại.Thực hiện phân loại
trên nhiều ngôn ngữ hơn nữa.