HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
----------------------------------
Trần Minh Hùng
LUẬN VĂN THẠC SĨ KỸ THUẬT
(Theo định hướng ứng dụng)
HÀ NỘI – 2019
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
----------------------------------
Trần Minh Hùng
TỔNG HỢP Ý KIẾN PHẢN HỒI CỦA ĐỘC GIẢ THEO
SỰ KIỆN PHẢN ÁNH BỞI BÁO CHÍ
Chuyên ngành:
Hệ thống thông tin
Mã số:
08.48.01.04
LUẬN VĂN THẠC SĨ KỸ THUẬT
(Theo định hướng ứng dụng)
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN MẠNH HÙNG
HÀ NỘI - 2019
i
LỜI CAM ĐOAN
Tôi cam đoan đề tài: “Tổng hợp ý kiến phản hồi của độc giả theo sự kiện phản
ánh bởi báo chí” là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn của TS.
Nguyễn Mạnh Hùng.
Các kết quả, phân tích, kết luận trong luận văn thạc sỹ này (ngoài phần được
trích dẫn) đều là kết quả làm việc của tác giả, các số liệu nêu trong luận văn là trung
thực và chưa từng được công bố trong bất kỳ công trình nào khác.
Nếu sai tôi xin hoàn toàn chịu trách nhiệm.
Hà Nội, ngày
tháng
năm 2019
Tác giả
Trần Minh Hùng
ii
LỜI CẢM ƠN
Lời đầu tiên cho em xin gửi lời cảm ơn chân thành đến các thầy, cô giáo
thuộc Khoa CNTT, Khoa QT&ĐT sau đại học thuộc Học viện Công nghệ Bưu
chính viễn thông đã tận tình giảng dạy, truyền đạt các nội dung kiến thức, kinh
nghiệm quý báu trong suốt quá trình em theo học tại Học viện. Với những bài học
quý giá, sự kèm cặp, chỉ bảo và truyền thụ tâm huyết của các thầy, cô đã giúp cá
nhân em hoàn thiện hơn nữa hệ thống kiến thức chuyên ngành, phục vụ tốt hơn yêu
cầu công tác của đơn vị đồng thời nâng cao hơn vốn tri thức của bản thân.
Đặc biệt, em xin gửi lời cảm ơn trân thành tới thầy hướng dẫn khoa học TS.
Nguyễn Mạnh Hùng, Khoa Công nghệ thông tin đã tận tình chỉ bảo, hướng dẫn,
cung cấp tài liệu và các nội dung kiến thức quý báu, đồng thời có sự định hướng
đúng đắn giúp em hoàn thành được luận văn này.
Em cũng xin được bày tỏ sự cảm ơn sâu sắc tới gia đình, đồng nghiệp đã tạo điều
kiện, dành sự ủng hộ đối với bản thân em để có nhiều thời gian cho khóa học, đạt
được những kết quả khả quan trong quá trình học tập. Đồng thời xin chân thành
cảm ơn tập thể lớp Cao học Hệ thống thông tin – Đợt 1 năm 2016 đã đồng hành,
khích lệ và chia sẻ trong suốt quá trình học tập.
Em rất mong nhận được sự chỉ dạy, đóng góp tận tình của các thầy, cô để
luận văn của em được hoàn thiện hơn nữa và có tính ứng dụng cao hơn trong thực
tiễn.
Xin trân trọng cảm ơn!
Hà Nội, ngày
tháng
năm 2019
Học viên
Trần Minh Hùng
iii
MỤC LỤC
LỜI CAM ĐOAN ............................................................................................ i
LỜI CẢM ƠN ................................................................................................. ii
MỤC LỤC ...................................................................................................... iii
DANH MỤC CÁC HÌNH ................................................................................v
DANH MỤC CÁC BẢNG ............................................................................ vi
THUẬT NGỮ TIẾNG ANH......................................................................... vii
MỞ ĐẦU ..........................................................................................................1
Chương 1 TỔNG QUAN VỀ PHÂN LOẠI NỘI DUNG VĂN BẢN ..........3
1.1.
Tổng quan về bài toán phân loại nội dung văn bản .........................3
1.1.1. Giới thiệu về bài toán phân loại văn bản ......................................3
1.1.2. Ứng dụng bài toán phân loại văn bản ...........................................5
1.2.
Mô hình cho bài toán phân loại văn bản ..........................................6
1.2.1. Yêu cầu đối với bài toán phân loại văn bản ..................................6
1.2.2. Giai đoạn huấn luyện ....................................................................7
1.2.3. Giai đoạn phân lớp ........................................................................8
1.3.
Tiền xử lý văn bản ...........................................................................8
1.3.1. Tách từ trong văn bản ...................................................................8
1.3.2. Trọng số của từ trong văn bản ....................................................13
1.3.3. Trích chọn đặc trưng văn bản .....................................................16
1.3.4. Các mô hình biểu diễn văn bản ...................................................18
1.4.
Đặc trưng văn bản Tiếng Việt ........................................................21
1.4.1. Đặc trưng của tiếng Việt .............................................................21
iv
1.4.2. Đặc trưng văn bản tin tức ............................................................22
1.4.3. Xử lý tiếng Việt trong phân loại văn bản ....................................22
1.5.
Kết luận ..........................................................................................23
Chương 2 Thuật toán phân loại nội dung văn bản.......................................24
2.1
Thuật toán Naive Bayes .................................................................24
2.2
Thuật toán Long Short Term Memory networks ...........................26
2.2.1 Ý tưởng cốt lõi của LSTM ...........................................................27
2.2.2 Bên trong LSTM ..........................................................................28
2.3
Thuật toán phân loại văn bản dựa trên từ đại diện .........................30
2.3.1 Mô tả thuật toán chọn từ đại diện ................................................30
2.3.2 Phân loại văn bản dựa trên độ tương đồng văn bản .....................32
2.4
Kết luận ..........................................................................................35
Chương 3 Cài Đặt Thuật Toán và Đánh giá kết quả ...................................36
3.1
Mô tả cài đặt thuật toán ..................................................................36
3.1.1 Bộ dữ liệu kiểm thử .....................................................................37
3.1.2 Xây dựng kịch bản kiểm thử ........................................................38
3.2
Kết quả thực nghiệm và đánh giá...................................................40
3.2.1 Môi trường thực nghiệm ..............................................................40
3.2.2 Kết quả thực nghiệm ....................................................................41
3.2.3 Đánh giá kết quả thuật toán .........................................................44
3.3
Kết luận ..........................................................................................45
KẾT LUẬN ....................................................................................................46
TÀI LIỆU THAM KHẢO..............................................................................47
v
DANH MỤC CÁC HÌNH
Hình 1. 1 Mô tả bài toán phân loại nội dung văn bản . ...............................................4
Hình 1. 2 Mô hình thực hiện bài toán phân loại văn bản . .........................................6
Hình 1. 3 Chi tiết giai đoạn huấn luyện .....................................................................7
Hình 1. 4 Biểu diễn văn bản theo mô hình xác suất..................................................19
Hình 2. 1 The repeating module in a standard RNN contains a single layer ............26
Hình 2. 2 The repeating module in an LSTM contains four interacting layers ........27
Hình 2. 3 các ký hiệu sử dụng trong mô hình LSTM ...............................................27
Hình 2. 4 Mô tả thuật toán LSTM .............................................................................28
Hình 2. 5 Mô tả thuật toán LSTM .............................................................................29
Hình 2. 6 Mô tả thuật toán LSTM .............................................................................29
Hình 2. 7 Mô tả thuật toán LSTM .............................................................................30
Hình 3. 1 Mô hình xử lý và cài đặt thuật toán ..........................................................36
vi
DANH MỤC CÁC BẢNG
Bảng 3. 1 Tổng quan về tập dữ liệu training cho thuật toán .....................................38
Bảng 3. 2 Contingency Table ....................................................................................42
Bảng 3. 3 Kết quả thực nghiệm thu được từ thuật toán phân loại ............................43
Bảng 3. 4 Kết quả thực nghiệm thu được từ thuật toán Naive Bayes .......................43
Bảng 3. 5 Kết quả thực nghiệm thu được từ thuật toán LSTM .................................44
Bảng 3. 6 Bảng tổng hợp kết quả của 3 thuật toán ...................................................44
vii
THUẬT NGỮ TIẾNG ANH
Từ viết tắt
Tiếng Anh
Tiếng Việt
NB
Naïve Bayes
Thuật toán Naïve Bayes
WFST
Weighted Finite State Transducer
Máy chuyển đổi trạng thái
hữu hạn có trọng số
TBL
Transformation-Based Learning
Giải thuật học cải biến
TF
Term Frequency
Tần suất xuất hiện của từ
IDF
Inverse Document Frequency
Tần số nghịch của 1 từ trong
tập văn bản
LSTM
Long Short Term Memory networks
Mạng bộ nhớ dài-ngắn
RNN
Recurrent Neural Network
Mạng nơ-ron hồi quy
1
MỞ ĐẦU
Hiện nay với sự phát triển mạnh mẽ của công nghệ thông tin, sự phổ biến của
mạng Internet là môi trường phổ biến dùng để lưu trữ các thông tin. Một lượng lớn
tri thức đã được sản sinh và chia sẻ trên mạng Internet. Ngoài ra, hàng ngày có rất
nhiều bài báo, sách được chia sẻ hàng ngày trên mạng Internet để cập nhật thông
tin về cuộc sống quanh chúng ta. Cùng với đó là nhu cầu tiếp thu kiến thức, lượng
thông tin, tri thức trên mạng Internet của con người ngày càng tăng lên do vậy khi
chúng ta tiếp thu, chắt lọc nội dung bằng phương pháp thông thường sẽ mất rất
nhiều thời gian. Ứng dụng phân loại nội dung của một văn bản tiếng Việt cung cấp
thêm một phương pháp tiếp cận thông tin dựa trên nội dung đã được phân phân loại
chủ đề giúp người đọc dễ dàng tiếp cận thông tin mình mong muốn.
Phân loại nội dung của của một văn bản đó là xử lý, phân tích , trích xuất và
tổng hợp nội dung của một văn bản tiếng Việt, từ đó phân loại nội dung văn bản
theo các chủ đề khác nhau, giúp người đọc dễ dàng nắm bắt được các văn bản có
nội dung theo chủ đề mà người dùng quan tâm. Đây là một đề tài có tính ứng dụng
cao trong thực tiễn nên được nghiên cứu và giải quyết bằng nhiều phương pháp
khác nhau trên toàn thế giới. Trong phạm vi của luận văn này chỉ làm việc trên văn
bản bằng tiếng Việt, cụ thể là các bài báo trên mạng Internet
Vì vậy, Học viên xin chọn đề tài “Tổng hợp ý kiến phản hồi của độc giả
theo sự kiện phản ánh bởi báo chí” nhằm phân loại nội của một bài báo trên mạng
Internet theo các thuật toán phân loại văn bản và từ đó chọn ra thuật toán phân loại
nội dung bài báo tiếng Việt tốt nhất trong khuôn khổ nghiên cứu. Dựa vào việc cài
đặt thuật toán và kết quả thu được về bài báo để phân loại bài toán và đưa ra kết quả
đánh giá về các thuật toán thực hiện phân loại văn bản.
Luận văn sẽ trình bày tổng quan về bài toán phân loại nội dung văn bản và
các thuật toán xử lý phân loại nội dung văn bản. Cài đặt thuật toán phân loại nội
dung văn bản Tiếng việt được mô tả trong luận văn với dữ liệu đầu vào là các bài
báo trên mạng Internet và đưa ra kết quả đánh giá nhận được.
2
Luận văn có bố cục gồm: Phần mở đầu, 3 chương chính, phần kết luận, tài
liệu tham khảo và phụ lục. Được bố trí theo thứ tự:
- Mở đầu.
- Chương 1: Tổng quan về phân loại nội dung văn bản
Trong chương này, luận văn sẽ trình bày tổng quan về xử lý và phân loại nội
dung, đặc trưng của một văn bản tiếng Việt , phương pháp tiếp cận bài toán phân
loại văn bản và các bước trong giai đoạn tiền xử lý văn bản trước khi thực hiện phân
loại văn bản. Các thuật toán sử dụng để phân loại văn bản sẽ được giới thiệu ở
chương 2.
- Chương 2: Thuật toán phân loại nội dung văn bản
Trong chương này, luận văn sẽ trình bày một số thuật toán hay dùng để phân
loại văn bản. Luận văn cũng sẽ trình bày chi tiết các thuật toán sử dụng để phân loại
nội dung văn bản tiếng Việt. Việc cài đặt thuật toán và đánh giá kết quả nhận được
sẽ được thực hiện trong chương 3.
- Chương 3: Cài đặt thuật toán và đánh giá kết quả
Trong chương này, luận văn sẽ trình bày các bước cài đặt thuật toán phân
loại nội dung văn bản, kết quả thực nghiệm thu được từ việc cài đặt và sử dụng
thuật toán. Từ đó đưa ra kết luận và đánh giá về thuật toán sử dụng để phân loại nội
dung văn bản.
- Kết luận luận văn.
- Tài liệu tham khảo
3
CHƯƠNG 1 TỔNG QUAN VỀ PHÂN LOẠI
NỘI DUNG VĂN BẢN
Trong chương này, luận văn sẽ trình bày tổng quan về xử lý và phân loại nội
dung của một văn bản tiếng Việt, các phương pháp tiếp cận bài toán phân loại văn
bản và các bước hay dùng trong giai đoạn tiền xử lý văn bản.
1.1. Tổng quan về bài toán phân loại nội dung văn bản
Trong thực tế ứng dụng quan trọng nhất của bài toán phân loại văn bản là
xây dựng công cụ tìm kiếm thông tin nhanh hơn. Bài toán phân loại văn bản giúp
giới hạn phạm vi tìm kiếm thông tin bằng việc phân loại được nội dung của các bài
viết có liên quan đến một chủ đề nhất định, từ đó đưa ra các gợi ý đúng với mục
đích tìm kiếm. Phân loại văn bản góp phần quan trọng trong việc tổ chức và quản lý
hiệu quả thông tin, tri thức. Ứng dụng phổ biến nhất của phân loại văn bản là trợ
giúp cho việc tìm kiếm và lọc văn bản do đó tăng tốc độ truy cập thông tin, tối ưa
hóa các kết quả đưa ra phù hợp với yêu cầu tìm kiếm. Phân loại văn bản cũng đóng
vai trò quan trọng trong việc xây dựng hiệu quả các công việc quản lí thông tin như
là sắp xếp loại thư điện tử, các file trong các hệ thống, phân loại nội dung các tin
tức điện tử, xác minh chủ đề của thông tin để trợ giúp cho các tiến trình xử lí, duyệt,
tìm kiếm các thông tin cấu trúc, các loại tài liệu mà người dùng quan tâm.
Trong chương này, luận văn trình bày các khái niệm cơ bản về phân loại văn
bản tự động, một vài thuật toán hay được sử dụng cho bài toán phân loại nội dung
văn bản, từ đó giới thiệu một số các phương pháp nghiên cứu liên quan dựa trên
cách tiếp cận học máy và một số phương pháp đánh giá hiệu năng của hệ thống
phân loại văn bản tự động
1.1.1. Giới thiệu về bài toán phân loại văn bản
Các nghiên cứu về khai phá dữ liệu, học máy dạng văn bản đang được quan
tâm hơn trong thời gian gần đây vì số lượng các tài liệu, thông tin điện tử chứa tri
thức tăng rất nhanh với rất nhiều nguồn khác nhau như mạng Internet,.... Bao gồm
4
tất cả những văn bản có cấu trúc, các văn bản không cấu trúc cũng tăng lên rất lớn.
Mục đích chính của việc khai phá dữ liệu văn bản là cho phép người dùng trích
xuất, rút gọn thông tin của các nguồn văn bản và sử dụng các thông tin đó để xây
dựng các công cụ như: tra cứu, hỏi đáp, phân loại và tóm tắt sử dụng ngôn ngữ tự
nhiên. Phân loại văn bản là một trong những bài toán quan trọng của việc khai phá
dữ liệu văn bản, rất nhiều các hệ thống phân loại văn bản sử dụng kỹ thuật dựa trên
tri thức (knowledge based) hoặc dựa trên các luật được xây dựng sẵn để tạo thành
một tập hợp các quy tắc logic để hiểu và phân loại văn bản. Mỗi lớp (class) tương
đương với một chủ đề được định nghĩa ví dụ “pháp luật”, “đời sống” ,“thể thao”.
Nhiệm vụ phân loại được bắt đầu xây dựng từ một tập các văn bản D =
{d1,d2,..,dn} được gọi là tập huấn luyện và trong đó các tài liệu di được gán nhãn cj
với cj thuộc tập các chủ đề C={c1,c2,...,cm}. Nhiệm vụ tiếp theo đó là xác định
được mô hình phân loại mà có thể gán đúng lớp để một tài liệu bất kỳ có thể phân
loại chính xác vào một trong những chủ đề của tập chủ đề.
Hình 1. 1 Mô tả bài toán phân loại nội dung văn bản [12].
Vậy phân loại văn bản là quá trình phân loại, gán nhãn (lớp) cho các tài liệu
văn bản bao gồm các văn bản có cấu trúc hoặc không cấu trúc vào một tập hợp của
một hay nhiều chủ đề đã được định nghĩa trước đó.
5
1.1.2. Ứng dụng bài toán phân loại văn bản
Lọc thư rác
Thư rác được gửi với các mục đích chính như sau:
- Các thông tin sai lệch, các hình thức kiếm tiền trực tuyến không đúng sự
thật nhằm lừa gạt người dùng.
- Quảng cáo sản phẩm, dịch vụ của một tổ chức, công ty trên mạng
- Gửi kèm virus trong tập tin kèm theo của thư điện tử, từ đó đưa virus vào
vào hệ thống mạng và lấy cắp các thông tin quan trọng.
- Nói xấu, xuyên tạc, tuyên truyền những điều sai trái về chính trị.
Việc phân loại được nội dung thư rác sẽ giúp chúng ta loại trừ được những
thư chứa các nội dung mà chúng ta không muốn tiếp cận. Ngoài ra chúng ta có thể
tránh được các nguy cơ tiềm ẩn như virus, trojan... xâm nhập vào máy tính cá nhân,
hệ thống chúng ta đang sử dụng
Phân loại tin tức điện tử
- Ngày nay sự phát triển của mạng Internet, các tin tức điện tử có chứa thông
tin, tri thức ngày càng nhiều.
- Người dùng muốn tìm hiểu các tin tức điện tử liên quan đến chủ đề mà
người dùng quan tâm, các hệ thống muốn phân loại các tin tức điện tử để dễ
dàng quản lý.
- Ứng dụng thành công bài toán phân loại điện tử giúp giải quyết được nhu
cầu của người dùng cũng như các hệ thống muốn tiếp cận nhanh, chính xác
cả tin tức điện tử liên quan đến chủ đề.
Xây dựng các cỗ máy tìm kiếm
- Đây là ứng dụng quan trọng nhất của bài toán phân loại văn bản.
- Việc phân loại văn bản sẽ giúp hệ thống tìm kiếm thông tin tổ chức, xếp
xếp, quản lý thông tin do đó tăng tốc độ truy cập thông tin của hệ thống.
6
- Các văn bản đã được phân loại (gán nhãn) sẽ giúp cho hệ thống tìm kiếm
dễ dàng tiếp cận, xử lý, lọc thông tin và trả lại các kết quả chính xác hơn với yêu
cầu của người dùng.
1.2. Mô hình cho bài toán phân loại văn bản
Chúng ta có thể tưởng tượng bài toán phân loại văn bản như sau : Cho một
tập gồm nn văn bản - document đầu vào kí hiệu D={𝑑1 , 𝑑2 ,..., 𝑑𝑛 } bằng các kĩ
thuật xử lý, thuật toán nào đó chúng ta sẽ phân tập văn bản trên vào một tập gồm
mm phân lớp - categories kí hiệu là C={𝑐1 , 𝑐2 ,..., 𝑐𝑚 }.
Trong phần này, luận văn sẽ giới thiệu mô hình để thực hiện phân loại văn
bản vào các lớp.
Hình 1. 2 Mô hình thực hiện bài toán phân loại văn bản [9] .
1.2.1. Yêu cầu đối với bài toán phân loại văn bản
Minh họa trực quan nhất cho việc phân loại văn bản đó chính là việc sắp xếp
các tin tức trên báo vào các danh mục tương ứng như thể thao, giải trí, xã hội... như
các tờ báo điện tử thường làm. Việc này có thể được thực hiện thủ công bởi các
7
biên tập viên tuy nhiên nó rất là mất thời gian và công sức. Thay vào đó chúng ta sẽ
sử dụng một số kĩ thuật học máy để tiến hành phân loại tự động các tin tức đó.
Vậy để giải quyết được bài toán phân loại văn bản chúng ta cần phải nắm được:
- Dữ liệu đầu vào cho việc phân loại (tin tức điện tử, bài báo khoa học, nghị
luận chính trị ....)
- Mô hình thực hiện phân loại văn bản
- Thuật toán sử dụng để phân loại văn bản
- Kết quả và đánh giá.
Trong luận văn này, dữ liệu đầu vào sẽ các bài báo trên mạng Internet.
1.2.2. Giai đoạn huấn luyện
Các văn bản đầu vào được gán nhãn và được trích chọn đặc trưng để nhận
dạng và sử dụng thuật toán học để lưu trữ lại các giá trị của đặc trưng theo một mô
hình chuẩn
Hình 1. 3 Chi tiết giai đoạn huấn luyện [5].
Giai đoạn huấn luyện gồm các bước sau:
Tiền xử lý dữ liệu: là bước làm sạch dữ liệu trước khi bắt đầu bất kì xử lý
nào trên tập dữ liệu, việc này bao gồm các bước xử lý ngôn ngữ tự nhiên như loại
bỏ stop words (từ dừng), kiểm tra chính tả, tách từ ...
Tách từ: đây một bước rất quan trọng khi xử lý tiền văn bản, nhất là đối với
tiếng Việt. Bởi vì cấu trúc cũng như đặc trưng của tiếng Việt nên việc tách từ trong
8
văn bản dữ liệu đầu vào là rất quan trọng, đảm bảo tính chính xác khi thực hiện
bước tiếp theo.
Trích chọn đặc trưng: bằng các kĩ thuật, phương pháp, thuật toán, ta sẽ trích
chọn đặc trưng các từ trong bài báo để được phiên bản cô đọng của văn bản, dễ
dàng thao tác trên dữ liệu nhận được. Kết quả của bước này là dữ liệu đầu vào cho
các thuật toán phân loại văn bản.
Huấn luyện: đây là bước dựa vào thuật toán phân loại sử dụng và tập dữ liệu
mẫu để xây dựng mô hình phân loại sử dụng cho các văn bản cần phân loại.
1.2.3. Giai đoạn phân lớp
Đây là giai đoạn thực hiện phân loại cho một văn bản chưa có nhãn dựa trên
mô hình mẫu đã được xây dựng từ giai đoạn huấn luyện. Giai đoạn này gồm các
bước sau:
- Trích trọn đặc trưng: văn bản đầu vào sẽ được xử lý qua một số bước như ở
giai đoạn huấn luyện gồm tiền xử lý, tách từ, trích trọn đặc trưng...
- Biểu diễn văn bản: sau khi trích trọn được những đặc trưng của văn bản đầu
vào, chúng ta cần biểu diễn văn bản dưới các mô hình tiện cho việc thực hiện phân
loại.
- Phân loại: Dựa trên mô hình chuẩn đã được huấn luyên để phân loại nội
dung văn bản theo đúng chủ đề.
- Đưa ra kết quả.
1.3. Tiền xử lý văn bản
Trong phần này, luận văn sẽ trình bày các bước cơ bản được thực hiện trong
giai đoạn tiền xử lý văn bản và một số mô hình và phương pháp áp dụng để thực
hiện trong giai đoạn này.
1.3.1. Tách từ trong văn bản
Khi thực hiện phân loại văn bản, trong bước tiền xử lý, việc đầu tiên cần xử
lý văn bản đó chính là việc tách từ. Bời vì sự phức tạp của tiếng Việt, nên việc áp
9
dụng phương pháp phù hợp để thực hiện tách từ khi xử lý văn bản đầu vào là việc
rất quan trọng. Trong phần này luận văn giới thiệu một vài phương pháp dùng để
tách từ trong văn bản
Phương pháp khớp tối đa
Tư tưởng của phương pháp khớp tối đa (Maximum Matching) [6] là duyệt
một câu từ trái qua phải và chọn từ có nhiều tiếng nhất mà có mặt trong từ điển
tiếng Việt. Thuật toán có 2 dạng sau:
Dạng đơn giản: Giả sử có một chuỗi các tiếng trong câu là t1, t2, ..., tN. Thuật
toán kiểm tra xem t1 có mặt trong từ điển hay không, sau đó kiểm tra tiếp t1-t2 có
trong từ điển hay không. Tiếp tục như vậy cho đến khi tìm được từ có nhiều tiếng
nhất có mặt trong từ điển và đánh dấu từ đó. Sau đó tiếp tục quá trình trên với tất
các các tiếng còn lại trong câu và trong toàn bộ văn bản. Dạng này khá đơn giản,
nhưng nó gặp phải rất nhiều nhập nhằng trong tiếng Việt. Ví dụ, nó bị gặp phải lỗi
khi phân đoạn từ câu sau: “học sinh | học sinh | học”, câu đúng phải là “học sinh|
học| sinh học”.
Dạng phức tạp: Dạng này có thể tránh được một số nhập nhằng gặp phải
trong dạng đơn giản. Đầu tiên thuật toán kiểm tra xem t1 có mặt trong từ điển
không, sau đó kiểm tra tiếp t1-t2 có mặt trong từ điển không. Nếu t1-t2 đều có mặt
trong từ điển, thì thuật toán thực hiện chiến thuật chọn 3-từ tốt nhất, cụ thể như sau:
- Độ dài trung bình của 3 từ là lớn nhất. Ví dụ, chuỗi “cơ quan tài chính”
được phân đoạn đúng thành “cơ quan | tài chính”, tránh được việc phân đoạn sai
thành “cơ | quan tài | chính” vì cách phân đúng phải có độ dài trung bình lớn nhất.
- Sự chênh lệch độ dài của 3 từ là ít nhất. Ví dụ, chuỗi “công nghiệp hoá
chất phát triển” được phân đoạn đúng thành “công nghiệp | hoá chất | phát triển”,
thay vì phân đoạn sai thành “công nghiệp hoá | chất | phát triển”. Cả 2 cách phân
đoạn này đều có độ dài trung bình bằng nhau, nhưng cách phân đoạn đúng có sự
chênh lệch độ dài 3 từ ít hơn.
10
Phương pháp này thực hiện tách từ đơn giản, nhanh và chỉ cần dựa vào từ
điển để thực hiện. Tuy nhiên, hạn chế của phương pháp này cũng chính là từ điển,
bởi độ chính xác khi thực hiện tách từ phụ thuộc hoàn toàn vào tính đủ, tính chính
xác của từ điển.
Mô hình tách từ bằng WFST và mạng Neural
Phương pháp WFST (Weighted Finite - State Transducer) [1] còn gọi là
phương pháp chuyển dịch trạng thái hữu hạn có trọng số. Ý tưởng chính của
phương pháp này áp dụng cho phân đoạn từ tiếng Việt là các từ được gán trọng số
bằng xác suất xuất hiện của từ đó trong dữ liệu. Sau đó duyệt qua các câu, cách
duyệt có trọng số lớn nhất được chọn là cách dùng để phân đoạn từ. Phương pháp
WFST đã được áp dụng trong công trình [9] đã được công bố của tác giả Đinh Điền
năm 2001. Trong đó, tác giả đã sử dụng WFST kèm với mạng Neural để xây dựng
hệ thống tách từ gồm hai tầng: Tầng WFST để tách từ; tầng mạng Neural dùng để
khử nhập nhằng về ngữ nghĩa (nếu có).
Tầng WFST: Gồm có ba bước
Bước 1: Xây dựng từ điển trọng số
Từ điển trọng số D được xây dựng như là một đồ thị biến đổi trạng thái hữu
hạn có trọng số. Giả sử:
- H là tập các tiếng trong tiếng Việt (hay còn gọi là các từ chính tả).
- P là tập các loại từ trong tiếng Việt.
- Mỗi cung của D có thể là:
Từ một phần tử của H tới một phần tử của H;
Từ phần tử (xâu rỗng) đến một phần tử của P.
Mỗi từ trong D được biểu diễn bởi một chuỗi các cung bắt đầu bởi một cung
tương ứng với một phần tử của H, kết thúc bởi một cung có trọng số tương ứng với
một phần tử của P.
11
Trọng số biểu diễn một chi phí ước lượng (estimated cost) cho bởi công
thức:
𝑓
𝐶 = − log ( )
𝑁
(1.1)
Trong đó, f là tần số xuất hiện của từ; N là kích thước tập mẫu.
Đối với các trường hợp từ mới chưa gặp, mô hình áp dụng xác suất có điều
kiện Goog-Turning (Baayen) để tính toán trọng số.
Bước 2: Xây dựng các khả năng tách từ
Bước này thống kê tất cả các khả năng phân đoạn của một câu. Giả sử câu có
n tiếng, thì có tới 2n-1 cách phân đoạn khác nhau. Để giảm sự bùng nổ các cách phân
đoạn, thuật toán loại bỏ ngay những nhánh phân đoạn mà chứa từ không xuất hiện
trong từ điển.
Bước 3: Lựa chọn khả năng tách tối ưu
Sau khi liệt kê tất cả các khả năng phân đoạn từ, thuật toán chọn cách tách từ
tốt nhất, đó là cách tách từ có trọng số bé nhất.
Tầng mạng Neural
Tầng này được sử dụng để khử nhập nhằng khi tách từ bằng cách kết hợp so
sánh với từ điển.
Phương pháp này có độ chính xác khá cao (>98% đối với tách từ trong lĩnh vực
khoa học - kỹ thuật; >94% đối với tiểu thuyết văn học), bằng việc kết hợp mạng
Neural với từ điển để khử các nhập nhằng có thể có khi tách ra nhiều từ từ một câu.
Khi đó tầng mạng Neural sẽ loại bỏ đi các từ không phù hợp bằng cách kết hợp với
từ điển. Tuy nhiên, việc xây dựng tập ngữ liệu học đầy đủ đáp ứng yêu cầu là rất
công phu, tốn kém về thời gian và công sức
Phương pháp học dựa vào sự biến đổi trạng thái
Học trên sự biến đổi trạng thái (TBL - Transformation-Based Learning) [9]
là một phương pháp học “hướng lỗi” (error-driven) dựa trên tập luật đã được sắp
- Xem thêm -