Đồ án Các đặc trưng ngôn ngữ cho bài toán phân loại câu hỏi tiếng Việt

HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG

KHOA CÔNG NGHỆ THÔNG TIN 1

------------

ĐỒ ÁN

TỐT NGHIỆP ĐẠI HỌC

Đề tài: “Các đặc trƣng ngôn ngữ cho bài

toán phân loại câu hỏi tiếng Việt”

Giảng viên hƣớng dẫn

Sinh viên thực hiện

Lớp

: TS. NGÔ XUÂN BÁCH

: NGUYỄN ĐÌNH NGHỊ

: D11CNPM3

Khóa:

: 2011 – 2016

Hệ đào tạo

: ĐẠI HỌC CHÍNH QUY

Hà Nội 12/2015

ĐỒ ÁN TỐT NGHIỆP

TÓM TẮT

Trong thời đại bùng nổ Công nghệ thông tin hiện nay, phương thức sử dụng giấy

tờ trong giao dịch đã dần được số hóa chuyển sang các dạng văn bản lưu trữ trên máy

tính hoặc truyền tải trên mạng. Bởi nhiều tính năng ưu việt của tài liệu số như: cách

lưu trữ gọn nhẹ, thời gian lưu trữ lâu dài, tiện dụng trong trao đổi, đặc biệt là qua

Internet, nên ngày nay, số lượng văn bản số tăng lên một cách chóng mặt, đặc biệt là

trên World Wide Web. Cùng với sự gia tăng về số lượng văn bản, nhu cầu tìm kiếm

văn bản cũng tăng theo. Với số lượng văn bản đồ sộ thì yêu cầu cần có những hệ thống

khai thác thông tin hiệu quả. Các công cụ tìm kiếm hiện thời chỉ trả về cho người dùng

một tập các tài liệu liên quan có chứa từ khóa trong câu truy vấn của người dùng. Tuy

nhiên, người dùng mong muốn một câu trả lời chính xác và cụ thể hơn, dẫn đến yêu

cầu cần phải có một hệ thống hỏi đáp tự động.

Trong những năm gần đây, hệ thống hỏi đáp tự động đã nhận được sự quan tâm

đặc biệt của các nhà nghiên cứu, các công ty (Yahoo, Google, Mcrosoft, IBM, v.v.),

các hội nghị lớn về trích chọn thông tin, xử lý ngôn ngữ tự nhiên (TREC, CLEF, ACL,

v.v.) và đã đạt được những kết quả nhất định. Tuy nhiên các nghiên cứu về hệ thống

hỏi đáp cho tiếng Việt vẫn còn rất hạn chế. Điều này một phần là do thiếu các công cụ

đủ tốt để xử lý tiếng Việt như nhận dạng thực thể tên, phân tích cú pháp, v.v.

Đồ án “Các đặc trưng ngôn ngữ cho bài toán phân loại câu hỏi tiếng Việt” tập

trung nghiên cứu về vấn đề phân loại câu hỏi cho tiếng Việt, đây là pha đầu tiên trong

một hệ thống hỏi đáp tiếng Việt, có ý nghĩa đặc biệt quan trọng với hoạt động của cả

hệ thống. Khi một câu hỏi được phân loại sẽ giúp chúng ta thu hẹp được không gian

tìm kiếm câu trả lời cho câu hỏi và từ đó giúp hệ thống hỏi đáp có thể đưa ra được các

câu trả lời ngắn gọn và chính xác hơn.

Trên cơ sở các nghiên cứu đã có và điều kiện thực tế của các công cụ xử lý ngôn

ngữ tiếng Việt, chúng tôi tiến hành thực nghiệm việc phân loại câu hỏi tiếng Việt trên

hai bộ dữ liệu: bộ dữ liệu một gồm 3000 câu hỏi tiếng Việt, bộ dữ liệu hai gồm 3000

câu hỏi tiếng Việt và đi kèm với mỗi câu hỏi là 5 câu truy vấn từ Google. Chúng tôi sử

dụng một số phương pháp học máy thống kê như Máy véc tơ hỗ trợ (SVM), Naïve

Bayes (NB), K-láng giềng gần nhất và tiến hành thực nghiệm trên các đặc trưng ngôn

ngữ tiếng Việt như đặc trưng từ vựng, đặc trưng âm tiết, n-grams, đặc trưng nhãn từ

loại và đặc trưng cú pháp của câu. Các kết quả ban đầu đạt được khá khả quan. Bộ

phân lớp câu hỏi đạt được kết quả tốt nhất là 85.53% khi sử dụng thuật toán SVM cho

đặc trưng âm tiết 1+2 grams kết hợp với đặc trưng nhãn từ loại và đặc trưng cú pháp.

Từ khóa: Hệ thống hỏi đáp, phân loại câu hỏi, Máy véc tơ hỗ trợ, K-láng giềng

gần nhất, Naïve Bayes, cây cú pháp, n-grams.

GVHD: TS. Ngô Xuân Bách

i

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

LỜI CẢM ƠN

Em xin chân thành cảm ơn TS. Ngô Xuân Bách, bộ môn Khoa học máy tính, Khoa

Công nghệ thông tin 1 đã tận tình chỉ dạy và hướng dẫn cho em trong việc lựa chọn đề

tài, thực hiện đề tài và viết báo cáo đồ án, giúp cho em có thể hoàn thành tốt đồ án này.

Em xin cảm ơn các thầy cô giáo Học viện Công nghệ Bưu chính Viễn thông, đặc

biệt các thầy cô trong khoa Công nghệ thông tin 1 đã tận tình dạy dỗ và chỉ bảo em

trong suốt 4 năm học.

Cuối cùng em xin cảm ơn gia đình, bạn bè, đồng nghiệp, những người đã luôn bên

cạnh động viên em những lúc khó khăn, và giúp đỡ em trong suốt thời gian học tập và

làm đồ án, tạo mọi điều kiện tốt nhất cho em để có thể hoàn thành tốt đồ án của mình.

Em xin chân thành cảm ơn!

Hà Nội, 12/2015

Sinh viên

Nguyễn Đình Nghị

GVHD: TS. Ngô Xuân Bách

ii

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

NHẬN XÉT

(Của giảng viên phản biện)

…………………………………………………………………………………………..

Hà Nội, 12/2015

Giảng viên phản biện

GVHD: TS. Ngô Xuân Bách

iii

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

NHẬN XÉT

(Của giảng viên hƣớng dẫn)

…………………………………………………………………………………………..

Hà Nội, 12/2015

Giảng viên hướng dẫn

GVHD: TS. Ngô Xuân Bách

iv

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

MỤC LỤC

TÓM TẮT .............................................................................................................................i

LỜI CẢM ƠN ......................................................................................................................ii

DANH MỤC HÌNH VẼ .....................................................................................................v ii

DANH MỤC BẢNG BIỂU ...............................................................................................viii

BẢNG THUẬT NGỮ TIẾNG AN H ...................................................................................i x

LỜI NÓI ĐẦU ...................................................................................................................... 1

CHƢƠNG 1: GIỚI THIỆU HỆ THỐNG HỎI ĐÁP VÀ BÀI TOÁN PHÂN LOẠI CÂU

HỎI ....................................................................................................................................... 3

1.1 Giới thiệu hệ thống hỏi đáp tự động ......................................................................... 3

1.2 Bài toán phân loại câu hỏ i ........................................................................................ 6

1.3 Các nghiên cứu liên qua n ......................................................................................... 7

1.4 Đóng góp của đồ án ................................................................................................. 8

CHƢƠNG 2: HỆ THỐNG PHÂN LOẠI CÂU HỎI TIẾNG VIỆT ................................... 9

2.1 Vấn đề phân loại câu hỏi cho tiếng Việt ................................................................... 9

2.2 Trích chọn đặc trưn g .............................................................................................. 10

2.2.1 Từ vựn g .......................................................................................................... 10

2.2.2 Âm tiết ............................................................................................................ 11

2.2.3 N-grams.......................................................................................................... 11

2.2.4 Nhãn từ loạ i .................................................................................................... 12

2.2.5 Cây cú phá p .................................................................................................... 14

2.3 Các thuật toán học má y .......................................................................................... 17

2.3.1 Máy véc tơ hỗ trợ (Support Vector Machine) .................................................. 17

2.3.2 Naïve Bayes.................................................................................................... 20

2.3.3 K láng giềng gần nhất (K -nearest neighbors)................................................... 22

CHƢƠNG 3: THỰC NGHIỆM VÀ ĐÁNH GIÁ .............................................................. 26

3.1 Dữ liệu thực nghiệm .............................................................................................. 26

3.1.1 Chuẩn bị dữ liệu ............................................................................................. 26

3.1.2 Tiền xử lý dữ liệu ........................................................................................... 27

3.2 Thiết lập thực nghiệm ............................................................................................ 32

3.2.1 Thực nghiệm với 3000 câu hỏi ........................................................................ 32

GVHD: TS. Ngô Xuân Bách

v

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

3.2.2 Thực nghiệm bổ sung câu truy vấn .................................................................. 42

KẾT LUẬN ........................................................................................................................ 45

PHỤ LỤC ........................................................................................................................... 46

TÀI LIỆU THAM KHẢO ................................................................................................. 49

GVHD: TS. Ngô Xuân Bách

vi

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

DANH MỤC HÌNH VẼ

Hình 1-1: Kiến trúc hệ thống hỏi đáp [12]. ............................................................................. 5

Hình 1-2: Mô hình gi ai đoạn huấn luyện [14]......................................................................... 6

Hình 1-3: Mô hình giai đoạn phân lớp [14]. ........................................................................... 7

Hình 2-1: Kiến trúc hệ thống phân loại câu hỏi tiếng Việt. ..................................................... 9

Hình 2-2: Phân tích phụ thuộc của một câu tiếng Việt [2]..................................................... 16

Hình 2-3: Siêu phẳng phân chia dữ liệu học thành 2 lớp + và – với khoảng cách biên lớn nhất

[17]...................................................................................................................................... 17

Hình 2-4: Minh họa bài toán phân 2 lớp bằng phương pháp SVM [17]................................. 18

Hình 3-1: File questions.txt .................................................................................................. 26

Hình 3-2: File labels.txt........................................................................................................ 27

Hình 3-3: File questions.tok. ................................................................................................ 28

Hình 3-4: File questions.tagger. ........................................................................................... 29

Hình 3-5: File questions.pos................................................................................................. 30

Hình 3-6: File questions.DEP.CONLL. ................................................................................ 31

Hình 3-7: File questions.root ................................................................................................ 31

Hình 3-8: File questions.child. ............................................................................................. 32

Hình 3-9: File từ điển ........................................................................................................... 32

Hình 3-10: Định dạng dữ liệu cho libsvm ............................................................................. 33

Hình 3-11: Giao diện màn hình chính của Weka. ................................................................. 35

Hình 3-12: Định dạng dữ liệu file arrff ................................................................................. 36

Hình 3-13: So sánh độ chính xác giữa đặc trưng âm tiết và đặc trưng từ vựng. ..................... 39

Hình 3-14: Độ chính xác cho mỗi nhãn (âm tiết 1+2 grams)................................................. 39

Hình 3-15: So sánh độ chính xác giữa các đặc trưng............................................................. 41

Hình 3-16: Phương pháp thực nghiệm bổ sung câu truy vấ n ................................................. 42

Hình 3-17: File question_and_query.txt. .............................................................................. 43

Hình B-1: Giao diện nhập câu hỏi bằng tay. ......................................................................... 47

Hình B-2: Giao diện nhập câu hỏi bằng file .......................................................................... 47

Hình B-3: Giao diện chạy chương trình ................................................................................ 48

GVHD: TS. Ngô Xuân Bách

vii

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

DANH MỤC BẢNG BIỂU

Bảng 2 -1: Tập nhãn từ loại [20] ........................................................................................... 13

Bảng 2 -2: Nhãn thành phần cú pháp [13] ............................................................................. 14

Bảng 2 -3: Nhãn chức năng cú pháp [13]............................................................................... 15

Bảng 3 -1: Số lượng câu hỏi của mỗi nhãn. ........................................................................... 26

Bảng 3 -2: Các tệp sau khi chuyển đổi ................................................................................... 33

Bảng 3 -3: Kết quả thực nghiệm SVM sử dụng n -grams, âm tiết và từ vựng .......................... 37

Bảng 3 -4: Kết quả phân lớp cho mỗi nhãn (âm tiết 1+2grams) ............................................. 37

Bảng 3 -5: Kết quả thực nghiệm khi bổ sung thêm các đặc trưng ........................................... 40

Bảng 3 -6: Kết quả phân lớp cho mỗi nhãn (âm tiết 1+2grams + nhãn từ loại + root)............. 40

Bảng 3 -7: Kết quả thực nghiệm của các thuật toán khác nhau ............................................... 41

Bảng 3 -8: Kết quả thực nghiệm bổ sung câu truy vấn ........................................................... 43

Bảng A -1: Các công cụ sử dụng ........................................................................................... 46

GVHD: TS. Ngô Xuân Bách

viii

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

BẢNG THUẬT NGỮ TIẾNG ANH

Viết tắt

Từ tiếng Anh

Giải nghĩa

Hiệp hội ngôn ngữ học tính toán

Association for Computational

Linguistics

ACL

The Cross-Language Evaluation Diễn đàn đánh giá ngôn ngữ

CLEF

KNN

Forum

chéo

Thuật toán K láng giềng gần

nhất

K-Nearest Neighbors

Maximum Entropy Model

Naïve Bayes

Mô hình Entropy cực đại

Phương pháp Bayes đơn giản

Nhãn từ loại

MEM

NB

POS

QA

Part Of Speech

Question Answering

Support Vector Machine

Text Retrieval Conference

Hệ thống hỏi đáp

Máy véc tơ hỗ trợ

SVM

TREC

Hội nghị truy xuất văn bản

GVHD: TS. Ngô Xuân Bách

ix

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

LỜI NÓI ĐẦU

Nghiên cứu về hệ thống hỏi đáp tự động (Q&A) [15] đã được quan tâm từ rất lâu

trên thế giới. Ngay từ những năm 1960, các hệ thống hỏi đáp đầu tiên sử dụng cơ sở

dữ liệu đã được ra đời. Đến những năm 1970-1980, rất nhiều dự án lớn hướng đến việc

“hiểu văn bản” và xây dựng hệ thống hỏi đáp dựa trên các mô hình ngôn ngữ thống kê.

Cuối những năm 1990, World Wide Web ra đời và phát triển nhanh chóng trở thành

một kho ngữ liệu khổng lồ. Các nhà nghiên cứu về hệ thống hỏi đáp cũng bắt đầu khai

thác web như là một nguồn dữ liệu cho việc tìm kiếm câu trả lời. Các kĩ thuật mới đòi

hỏi tốc độ cao, khả năng xử lý lượng dữ liệu web lớn đang rất được quan tâm. Tuy

nhiên các nghiên cứu về xây dựng hệ thống hỏi đáp cho tiếng Việt vẫn còn rất nhiều

hạn chế. Một trong những lý do chính là chúng ta còn thiếu các công cụ xử lý tiếng

Việt, các tài nguyên ngôn ngữ học.

Phân loại câu hỏi [15] là pha đầu tiên trong kiến trúc chung của một hệ thống hỏi

đáp, có nhiệm vụ tìm ra các thông tin cần thiết làm đầu vào cho quá trình xử lý của các

pha sau (trích chọn tài liệu, trích xuất câu trả lời, v.v.). Vì vậy phân loại câu hỏi có vai

trò hết sức quan trọng, ảnh hưởng trực tiếp đến hoạt động của toàn bộ hệ thống. Phân

loại câu hỏi là việc gán các nhãn phân loại cho một câu hỏi dựa trên mức độ tương tự

của câu hỏi đó so với các câu hỏi đã được gán nhãn trong tập huấn luyện. Phân loại

câu hỏi nhận đầu vào là câu hỏi của người dùng dưới dạng ngôn ngữ tự nhiên, và đầu

ra là nhãn phân loại của câu hỏi. Khi một câu hỏi được phân loại đúng thì việc tìm câu

trả lời cho câu hỏi đó sẽ được chính xác hơn. Ví vụ với câu hỏi “Thành phố nào có

diện tích lớn nhất Việt Nam?”, nếu chúng ta biết được kiểu câu trả lời là thành phố thì

nó có thể giúp chúng ta giới hạn được các câu trả lời, thay vì việc phải đi kiểm tra các

danh từ trong các tài liệu cung cấp câu trả lời.

Đồ án “Các đặc trưng ngôn ngữ cho bài toán phân loại câu hỏi tiếng Việt” thực

hiện khảo sát, nghiên cứu các phương pháp xây dựng hệ thống hỏi đáp và phân loại

câu hỏi đang được quan tâm hiện nay, từ đó đưa ra phương pháp phân loại câu hỏi phù

hợp nhất cho hệ thống hỏi đáp tiếng Việt. Những nghiên cứu trong đồ án có thể coi là

tiền đề cho các nghiên cứu tiếp theo để xây dựng một hệ thống hỏi đáp hoàn thiện cho

tiếng Việt.

Hiện nay có nhiều phương pháp khác nhau để tiếp cận với bài toán phân loại câu

hỏi, trong phạm vi đồ án này, chúng tôi thực hiện phân loại câu hỏi sử dụng cách tiếp

cận học máy thống kê, cụ thể là sử dụng 3 thuật toán: Máy véc tơ hỗ trợ (SVM), Naïve

Bayes (NB) và K-láng giềng gần nhất (KNN). Với thuật toán SVM, chúng tôi sử dụng

công cụ libsvm [21] để tiến hành làm thực nghiệm, với các thuật toán còn lại, chúng

tôi sử dụng công cụ Weka [22] để làm thực nghiệm. Các thuật toán được áp dụng làm

thực nghiệm trên các đặc trưng ngôn ngữ tiếng Việt gồm có: đặc trưng từ vựng, đặc

trưng âm tiết, n-grams, đặc trưng nhãn từ loại, và đặc trưng về cú pháp phụ thuộc của

tiếng Việt. Các đặc trưng này sẽ được biểu diễn dưới dạng các vector đặc trưng, làm

đầu vào cho các thuật toán. Kết quả thực nghiệm tốt nhất đạt được khi sử dụng thuật

GVHD: TS. Ngô Xuân Bách

1

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

toán SVM trên đặc trưng âm tiết 1+2 grams kết hợp với đặc trưng nhãn từ loại và đặc

trưng cú pháp là 85.53%, với các thuật toán Naïve Bayes, K-láng giềng gần nhất, kết

quả tốt nhất lần lượt là: 77.56%, 70.83%.

Đồ án được trình bày thành 3 chương như sau:

CHƢƠNG 1: GIỚI THIỆU HỆ THỐNG HỎI ĐÁP VÀ BÀI TOÁN PHÂN

LOẠI CÂU HỎI

Nội dung của chương này giới thiệu tổng quan về hệ thống hỏi đáp tự động, bài

toán phân loại câu hỏi và trình bày những đóng góp chính của đồ án.

CHƢƠNG 2: HỆ THỐNG PHÂN LOẠI CÂU HỎI TIẾNG VIỆT

Chương 2 trình bày một số phương pháp lấy đặc trưng ngôn ngữ tiếng Việt cho

bài toán phân loại câu hỏi tiếng Việt và các thuật toán học máy thống kê được sử dụng

để tiến hành thực nghiệm trên các đặc trưng đó.

CHƢƠNG 3: THỰC NGHIỆM VÀ ĐÁNH GIÁ

Trong chương 3, đồ án trình bày chi tiết về quá trình làm thực nghiệm gồm có

cách thu thập dữ liệu, cách xử lý dữ liệu, chi tiết từng bước làm thực nghiệm, đánh giá

kết quả thực nghiệm.

GVHD: TS. Ngô Xuân Bách

2

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

Chương 1: Giới thiệu

CHƢƠNG 1: GIỚI THIỆU HỆ THỐNG HỎI ĐÁP VÀ BÀI TOÁN

PHÂN LOẠI CÂU HỎI

Trong chương 1, đồ án trình bày cái nhìn tổng quan về hệ thống hỏi đáp tự động,

bao gồm các khái niệm cơ bản liên quan tới hệ thống hỏi đáp, phân loại hệ thống hỏi

đáp và kiến trúc chung của một hệ thống hỏi đáp. Ngoài ra, chương 1 cũng giới thiệu

về bài toán phân loại câu hỏi, các cách tiếp cận với bài toán phân loại câu hỏi và mô

hình của các giai đoạn phân loại câu hỏi, các nghiên cứu liên quan và những đóng góp

mà đồ án đã thực hiện được.

1.1

Giới thiệu hệ thống hỏi đáp tự động

Với nhu cầu trao đổi thông tin của con người ngày càng cao, thông tin tràn ngập

trên mọi phương tiện truyền thông, đặc biệt là sự phát triển rộng rãi của mạng toàn cầu

Internet, hằng ngày con người phải xử lý một lượng thông tin khổng lồ. Những thắc

mắc của người dùng dưới dạng truy vấn sẽ được tìm kiếm và trả về một cách ngắn

gọn, súc tích, chính xác nhất những gì mà họ mong muốn. Đó chính là mục tiêu của hệ

thống hỏi đáp tự động. Rất nhiều hệ thống hỏi đáp thông tin qua mạng ra đời nhằm đáp

ứng nhu cầu này.

Nghiên cứu về hệ thống hỏi đáp tự động [15] hiện đang thu hút sự quan tâm của

rất nhiều các nhà nghiên cứu từ các trường đại học, các viện nghiên cứu và cả các

doanh nghiệp lớn trong ngành công nghệ thông tin, có ý nghĩa khoa học lẫn ý nghĩa

thực tế. Rất nhiều các hội nghị thường niên về khai phá dữ liệu, trích chọn thông tin

dành một chủ đề riêng cho các nghiên cứu về hệ thống hỏi đáp như TREC [24], CLEF

[25], v.v. Ngoài ra còn có các phần mềm thương mại liên quan đến QA cũng được

phát triển như Yahoo Answers [26] của Yahoo, Google Question [27] của Google,

Live QnA của Microsoft, v.v. và đặc biệt có hai phần mềm là Answers.com của

Answer Corp đạt được 9.5 triệu đô la và Ask của InterActive Corp đạt được 227 triệu

đô la mỗi năm [8].

Hệ thống hỏi đáp tự động (Question Answering - QA) là một hệ thống được xây

dựng để thực hiện việc tìm kiếm câu trả lời cho một câu hỏi của người dùng từ một tập

lớn các tài liệu một cách chính xác và ngắn gọn. Hệ thống hỏi đáp tự động liên quan

đến 3 lĩnh vực lớn là xử lý ngôn ngữ tự nhiên (Natuaral Language Processing), tìm

kiếm thông tin (Information Retrieval) và rút trích thông tin (Information Extraction).

Hệ thống hỏi đáp nhận đầu vào là câu hỏi dưới dạng ngôn ngữ tự nhiên của người

dùng và trả lại các đoạn văn bản ngắn chứa câu trả lời trực tiếp cho câu hỏi.

Bài toán xây dựng hệ thống hỏi đáp [15] là một bài toán khó thuộc lĩnh vực xử lý

ngôn ngữ tự nhiên. Ngôn ngữ tự nhiên vốn nhập nhằng, đa nghĩa, việc xác định được

ngữ nghĩa của câu hỏi cũng như phát hiện ra câu trả lời là một thách thức không nhỏ.

Không những vậy, giữa câu hỏi và câu trả lời còn tồn tại các quan hệ “ngầm” hay phụ

thuộc vào ngữ cảnh.

GVHD: TS. Ngô Xuân Bách

3

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

Chương 1: Giới thiệu

Ví dụ câu hỏi: “Ai là tác giả Nhật ký trong tù?”

Câu trả lời mong đợi: “Hồ Chí Minh”.

Tuy nhiên hiện nay, đa phần các hệ thống hỏi đáp chỉ trả lời ở mức đưa ra các

đoạn trích dẫn có chứa thông tin về câu trả lời như sau:

- “Hồ Chí Minh viết Nhật ký trong tù trong thời gian Người bị chính quyền

Tưởng Giới Thạch bắt giam và giải đi khắp các nhà giam ở Quảng Tây,

Trung Quốc.”

- “Nhật ký trong tù, dịch tiếng Hán – Ngục trung nhật ký là một tập thơ của

Hồ Chí Minh,…”.

Hay câu hỏi “Mozart sinh năm nào?” và câu trả lời “…Mozart(1751 - 1791)…”

Để tìm được câu trả lời trên cho câu hỏi, hệ thống cần có cơ chế để biết được

rằng “tác giả của một tập thơ là người viết tập thơ đó” hoặc cần học được các mẫu

thường gặp của câu trả lời (các mẫu về ngày tháng năm sinh, về thời gian, địa chỉ v.v.)

tương ứng với từng loại câu hỏi. Các hệ thống QA trên thế giới hiện nay sử dụng rất

nhiều các công cụ xử lý ngôn ngữ như: Bộ gán nhãn từ loại (POS Tagger), bộ nhận

dạng tên thực thể (Named Entity Recognizer), bộ phân tích ngữ pháp (Parser) v.v. và

các tài nguyên ngôn ngữ như Wordnet, ontology để phân tích câu hỏi và trích xuất câu

trả lời [15].

Có 2 loại hệ thống hỏi đáp:

- Hệ thống hỏi đáp lĩnh vực hẹp (Closed-domain Question Answering): hệ

thống này liên quan đến các câu hỏi trong một lĩnh vực cụ thể, chẳng hạn như

lĩnh vực y học, du lịch, kinh tế, thể thao, v.v.

- Hệ thống hỏi đáp lĩnh vực rộng (Open-domain Question Answering): hệ

thống này liên quan đến các câu hỏi gần như là về tất cả mọi thứ.

Có nhiều phương pháp được đề xuất để xây dựng hệ thống hỏi đáp. Năm 1997,

hệ thống trực tuyến START sử dụng một cơ sở dữ liệu để phân tích câu hỏi và đưa ra

câu trả lời [4]. Hầu hết các hệ thống QA hiện đại sử dụng kĩ thuật trích xuất mối quan

hệ ngữ nghĩa. Ví dụ, năm 2002 Ravichandran và Hovy đề xuất trích mối quan hệ ngữ

nghĩa sử dụng máy tìm kiếm [5]. Năm 2009, Fahmi tăng độ bao phủ của các mối quan

hệ bằng cách sử dụng học nửa giám sát để tự động tạo ra các mối quan hệ từ một tập

lớn dữ liệu [1].

GVHD: TS. Ngô Xuân Bách

4

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

Chương 1: Giới thiệu

Kiến trúc hệ thống hỏi đáp:

Hình 1-1: Kiến trúc hệ thống hỏi đáp [12].

- Giao diện ngƣời dùng: cung cấp giao diện cho phép người dùng nhập câu

hỏi vào. Các câu hỏi sau đó được gửi đi, hệ thống sẽ xử lý và trả về cho người

dùng một câu trả lời dưới định dạng tương tự.

- Phân tích câu hỏi: câu hỏi được phân tích và xử lý để trích lọc càng nhiều

thông tin càng tốt mà có thể được sử dụng sau này trong giai đoạn tìm kiếm

dữ liệu.

- Tìm kiếm dữ liệu: một số thông tin đã được trích xuất trong giai đoạn phân

tích câu hỏi sẽ được sử dụng để tìm kiếm thông tin trong cơ sở tri thức.

- Rút trích câu trả lời: rút trích câu trả lời thuộc lĩnh vực rút trích thông tin.

Thông tin đã được trả về trong giai đoạn này có thể là các tài liệu hoặc các

văn bản từ việc truy vấn cơ sở dữ liệu.

- Xếp hạng: nếu các kết quả của giai đoạn rút trích câu trả lời có nhiều hơn

một câu trả lời thì các câu trả lời sẽ được xếp hạng dựa trên mức độ liên quan

về mặt ngôn ngữ với câu hỏi của người dùng.

- Xác minh câu trả lời: một số hệ thống QA cải thiện tính chính xác bằng cách

phân tích các câu trả lời thu được, qua việc sử dụng phương pháp xử lý ngôn

ngữ tự nhiên bằng cách phân tích sâu hơn để xác minh lại câu hỏi. Các câu

hỏi và câu trả lời được phân tích cú pháp và chuyển đổi sang cùng một hình

GVHD: TS. Ngô Xuân Bách

5

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

Chương 1: Giới thiệu

thức logic. Các câu hỏi và câu trả lời sau đó được so sánh với nhau để xác

minh tính hợp lý của câu trả lời.

1.2

Bài toán phân loại câu hỏi

Phân loại câu hỏi đóng một vai trò quan trọng trong hệ thống trả lời câu hỏi.

Trước khi tìm ra được câu trả lời cho câu hỏi, hệ thống cần phải xác định được câu hỏi

đó thuộc loại nào, hỏi về cái gì. Ví dụ câu hỏi “Dân số Việt Nam là bao nhiêu?” là câu

hỏi về “số lượng”, hay câu “Ai là tổng thống Mỹ?” là câu hỏi về “người”. Xác định

được loại câu hỏi sẽ giúp thu hẹp được không gian tìm kiếm câu trả lời.

Bài toán phân loại câu hỏi thực chất có thể xem là bài toán phân lớp. Phân loại

câu hỏi là việc gán các nhãn phân loại cho các câu hỏi dựa trên mức độ tương tự của

câu hỏi đó so với các câu hỏi đã được gán nhãn trong tập huấn luyện. Nó ánh xạ một

câu hỏi vào một chủ đề đã biết trong một tập hữu hạn các chủ đề dựa trên các đặc

trưng của câu hỏi. Phân loại câu hỏi [15] nhận đầu vào là câu hỏi dưới dạng ngôn ngữ

tự nhiên của người dùng, đưa ra nhãn phân loại cho câu hỏi đó, xem câu hỏi đó thuộc

loại nào. Các câu hỏi có thể được phân vào các loại như địa điểm, số lượng, người, mô

tả, khoảng cách, v.v. Ví dụ câu hỏi “Hồ Chí Minh là ai?” là câu hỏi thuộc loại Người,

hay câu hỏi “Trường Học viện Công nghệ Bưu chính Viễn thông nằm ở đâu?” là câu

hỏi thuộc loại Địa điểm.

Nhiều kĩ thuật máy học và khai phá dữ liệu đã được áp dụng vào bài toán phân

loại câu hỏi như: cây quyết định (decision tree), NaiveBayes, K-láng giềng gần nhất

(KNN), mạng nơron (neural network), v.v. Phân loại câu hỏi [14] thường gồm 2 giai

đoạn: giai đoạn huấn luyện và giai đoạn phân lớp:

 Giai đoạn huấn luyện:

Ngữ liệu

huấn luyện

Tiền xử lý

Vector hóa

Mô hình

phân loại

Trích chọn

đặc trưng

Thuật toán

huấn luyện

Hình 1-2: Mô hình giai đoạn huấn luyện [14].

Giai đoạn huấn luyện nhận đầu vào là tập ngữ liệu huấn luyện gồm các câu hỏi

đã được gán nhãn, sau khi xử lý tập ngữ liệu và áp dụng các thuật toán huấn luyện sẽ

cho ra đầu ra là một mô hình phân loại.

GVHD: TS. Ngô Xuân Bách

6

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

Chương 1: Giới thiệu

 Giai đoạn phân lớp:

Câu hỏi

Tiền xử lý

Vector hóa

Trích chọn

đặc trưng

Nhãn cho

câu hỏi

Sử dụng mô

hình phân lớp

Hình 1-3: Mô hình giai đoạn phân lớp [14].

Giai đoạn phân lớp nhận đầu vào là câu hỏi của người dùng dưới dạng ngôn ngữ

tự nhiên, sau quá trình xử lý và áp dụng mô hình phân loại sẽ cho ra nhãn phân loại

của câu hỏi đầu vào.

1.3

Các nghiên cứu liên quan

Hiện nay đã có một số nghiên cứu về bài toán phân loại câu hỏi, đặc biệt là tiếng

Anh như nghiên cứu của Zhiheng Huang và các cộng sự [3]. Nghiên cứu này sử dụng

5 đặc trưng gồm wh-word, head word, wordnet semantic, n-grams, word shape và sử

dụng hai cách tiếp cận là Máy vector hỗ trợ (SVM) và Mô hình entropy cực đại

(MEM) với kết quả đạt được lần lượt là 89.2% và 89.0%. Nghiên cứu của Dell Zhang

và Wee Sun Lee [9] sử dụng hai đặc trưng là bag-of-word và n-grams. Nghiên cứu đã

tiến hành thực nghiệm với 5 thuật toán gồm: Support Vector Machine (SVM), K-

nearest neighbors (KNN), Naïve Bayes (NB), Decision Tree (DT), Sparse Network of

Winnows (SNoW), và các thực nghiệm được thực hiện với các kích thước dữ liệu khác

nhau. Với bộ dữ liệu 1000 câu hỏi, sử dụng đặc trưng từ vựng, độ chính xác của các

thuật toán lần lượt là: KNN đạt được 70%, NB đạt 53.8%, DT đạt 78.8%, SnoW đạt

71.8% và SVM đạt 76.8%. Với bộ dữ liệu 3000 câu hỏi, độ chính xác của các thuật

toán lần lượt là: KNN đạt 74.8%, NB đạt 74.2%, DT đạt 82%, SnoW đạt 74.2% và

SVM đạt 87.4%. Khi áp dụng trên đặc trưng n-grams, với bộ dữ liệu 1000 câu hỏi,

KNN đạt được độ chính xác 72%, NB đạt 73%, DT đạt 73.8%, SnoW đạt 59.8% và

SVM đạt 77.6%. Với bộ dữ liệu 3000 câu hỏi, độ chính xác của KNN, NB, DT, SnoW

và SVM lần lượt là: 79.8%, 80%, 83%, 80.6%, 84%. Hầu hết các thực nghiệm đều cho

thấy kết quả phân loại sử dụng thuật toán SVM đạt được độ chính xác cao nhất.

Một số nghiên cứu về phân loại câu hỏi trong tiếng Việt như nghiên cứu của Trần

Vũ Mai và các cộng sự [8], nghiên cứu này đã kết hợp hệ thống SnowBall và phương

pháp trích xuất mối quan hệ ngữ nghĩa sử dụng máy tìm kiếm cho tập văn bản tiếng

Việt. Thực nghiệm ban đầu của mô hình cho thấy hệ thống có thể trả lời chính xác

được 89.1% câu hỏi của người dùng đưa vào và khả năng đưa ra câu trả lời là 91.4%.

Nghiên cứu của Trần Hải Đăng và các cộng sự [7] đã sử dụng công cụ Weka để chạy

các thuật toán học máy Cây quyết định (DT), Naïve Bayes (NB), Máy véc tơ hỗ trợ

(SVM) với các đặc trưng được sử dụng là từ vựng và từ khóa. Với 6 lớp phân loại,

GVHD: TS. Ngô Xuân Bách

7

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

Chương 1: Giới thiệu

phương pháp cây quyết định đạt được độ chính xác là 86.2%, phương pháp Naïve

Bayes đạt được độ chính xác là 87.4%, và độ chính xác của phương pháp SVM là

94.1%. Với 50 lớp phân loại, độ chính xác của phương pháp cây quyết định là 80.3%,

phương pháp Naïve Bayes là 81.1%, và phương pháp SVM là 94%.

1.4

Đóng góp của đồ án

Đồ án có một số đóng góp cơ bản sau:

- Nghiên cứu về hệ thống hỏi đáp và bài toán phân loại câu hỏi với các đặc

trưng từ vựng, âm tiết, n-grams, nhãn từ loại và cây cú pháp.

- Thực nghiệm đánh giá với một số phương pháp học máy gồm có Máy véc tơ

hỗ trợ, Naïve Bayes và K-láng giềng gần nhất.

- Đồ án cung cấp dữ liệu về nhãn từ loại và cây cú pháp của 3000 câu hỏi tiếng

Việt.

- Ngoài ra đồ án còn cung cấp bộ dữ liệu các câu truy vấn tiếng Việt được thu

thập từ trang web google.com. Các câu truy vấn này được bổ sung vào 3000

câu hỏi tiếng Việt.

GVHD: TS. Ngô Xuân Bách

8

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

Chương 2: Hệ thống phân loại câu hỏi tiếng Việt

CHƢƠNG 2: HỆ THỐNG PHÂN LOẠI CÂU HỎI TIẾNG VIỆT

Trong chương 2, đồ án trình bày một số phương pháp lấy đặc trưng cho phân loại

câu hỏi tiếng Việt gồm có đặc trưng từ vựng, đặc trưng âm tiết, n-grams, đặc trưng

nhãn từ loại, đặc trưng cú pháp. Ngoài ra, đồ án còn trình bày các thuật toán được sử

dụng khi làm thực nghiệm gồm có Máy véc tơ hỗ trợ, Naïve Bayes và K-láng giềng

gần nhất.

2.1

Vấn đề phân loại câu hỏi cho tiếng Việt

Chúng ta có một tập câu hỏi tiếng Việt, mục đích của chúng ta là phân loại cho

các câu hỏi đó, xác định xem câu hỏi đó thuộc lĩnh vực nào như: số lượng, địa điểm,

mô tả, v.v.

Đầu vào: câu hỏi tiếng Việt của người dùng

Đầu ra: nhãn phân loại cho câu hỏi của người dùng

Ví dụ: câu hỏi “Cầu thủ nào giành quả bóng vàng năm 2014?” sẽ có nhãn phân

loại là Người. Hay câu “Sân vận động Bernabeu nằm ở đâu?” sẽ có nhãn phân loại là

Địa điểm.

Chúng ta có mô hình phân loại câu hỏi:

Trích chọn

đặc trưng

Thuật toán

học máy

Đầu vào

Đầu ra

Câu hỏi tiếng

Việt

- Từ vựng

- Âm tiết

- SVM

- NB

Kiểu câu hỏi

- n-grams

- Nhãn từ loại

- Cú pháp

- KNN

Hình 2-1: Kiến trúc hệ thống phân loại câu hỏi tiếng Việt.

Hệ thống phân loại câu hỏi cho tiếng Việt gồm có 2 thành phần chính:

- Bộ trích chọn đặc trƣng: trích xuất ra các đặc trưng từ câu hỏi của người

dùng như đặc trưng từ vựng, đặc trưng âm tiết, n-grams, đặc trưng nhãn từ

loại và đặc trưng cú pháp của câu hỏi, các đặc trưng này sẽ là đầu vào cho bộ

phân loại câu hỏi.

- Bộ phân loại: có thể sử dụng các thuật toán khác nhau, trong phạm vi đồ án

chúng tôi sử dụng 3 thuật toán học máy gồm: Máy véc tơ hỗ trợ (SVM),

Naïve Bayes (NB) và K-láng giềng gần nhất (KNN).

GVHD: TS. Ngô Xuân Bách

9

SVTH: Nguyễn Đình Nghị – D11CNPM3

ĐỒ ÁN TỐT NGHIỆP

Chương 2: Hệ thống phân loại câu hỏi tiếng Việt

2.2

Trích chọn đặc trƣng

Trích chọn đặc trưng có ý nghĩa quan trọng, ảnh hưởng trực tiếp đến kết quả

phân lớp. Các loại đặc trưng chính thường được sử dụng là tập từ (bag-of-word) và tập

các từ/nhãn từ loại (bag-of-word/POS tag). Ngoài ra, trong phạm vi đồ án, chúng tôi

còn sử dụng thêm các đặc trưng khác như n-grams, đặc trưng âm tiết (bag-of-syllable),

đặc trưng về cú pháp phụ thuộc của câu (dependency feature).

2.2.1 Từ vựng

Với đặc trưng từ vựng, một câu sẽ được biểu diễn dưới dạng một tập các từ riêng

biệt, không quan tâm tới ngữ pháp hay thứ tự của các từ trong câu, chỉ giữ lại số lần

xuất hiện của từ trong câu.

Không giống như tiếng Anh, mỗi một âm tiết là một từ và được viết cách nhau

bởi một khoảng trắng. Với tiếng Việt, một từ có thể được viết bởi một hoặc nhiều âm

tiết, do đó không thể dùng khoảng trắng làm ranh giới phân cách các từ. Ví dụ trong

tiếng anh chúng ta có từ mobile, khi dịch ra tiếng Việt mobile có nghĩa là điện thoại,

được tạo thành từ 2 âm tiết là điện và thoại. Vì vậy để xác định được các từ tiếng Việt,

chúng ta phải sử dụng một công cụ tách từ hiệu quả cho tiếng Việt, và trong đồ án

chúng tôi sử dụng công cụ tách từ vnTokenizer [19].

Ví dụ với 2 câu:

Câu 1: Trong hai thành phố Hà Nội và Bắc Ninh, thành phố nào có diện tích lớn

hơn?

Câu 2: Hà Nội là thành phố có diện tích lớn nhất Việt Nam phải không?

Khi tách từ chúng ta có:

Câu 1: Trong hai thành_phố Hà_Nội và Bắc_Ninh, thành_phố nào có diện_ tích

lớn hơn ?

Câu 2: Hà_Nội là thành_phố có diện_tích lớn nhất Việt_ Nam phải không ?

Biểu diễn đặc trưng:

- Xây dựng từ điển:

{

1 : Trong, 2 : hai, 3 : thành_phố, 4 : Hà_Nội, 5 : và, 6 : Bắc_Ninh, 7 :

nào, 8 : có, 9 : diện_tích, 10 : lớn, 11 : hơn, 12 : là, 13 : nhất, 14 :

Việt_Nam, 15 : phải, 16 : không

}

- Biểu diễn 2 câu trên dưới dạng vector đặc trưng, mỗi phần tử của vector có

dạng: <vị trí của từ trong từ điển> : <số lần xuất hiện của từ trong câu>, dựa

vào chỉ số trong từ điển ta có 2 vector:

Câu 1: [1:1, 2:1, 3:2, 4:1, 5:1, 6:1, 7:1, 8:1, 9:1, 10:1, 11:1, 12:0, 13:0, 14:0,

15:0, 16:0]

GVHD: TS. Ngô Xuân Bách

10

SVTH: Nguyễn Đình Nghị – D11CNPM3