BỘ GIÁO DỤC VÀ ĐÀO TẠO TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG VIỆT NAM

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
BÙI ĐỨC TRUNG NGHIÊN CỨU KỸ THUẬT GÁN NHÃN CHO DỮ LIỆU
DẠNG CHUỖI VÀ ỨNG DỤNG CHUYÊN NGÀNH :
TRUYỀN DỮ LIỆU VÀ MẠNG MÁY TÍNH

MÃ SỐ: 60.48.15
TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT
HÀ NỘI – 2010


Luận văn được hoàn thành tại:
Học viện Công nghệ Bưu chính Viễn thông
Tập đoàn Bưu chính Viễn thông Việt Nam

Người hướng dẫn khoa học:
PGS.TS. TỪ MINH PHƯƠNG

Phản biện 1: ……………………………………………………
……………………………………………………

Phản biện 2: ……………………………………………………
……………………………………………………

Luận văn sẽ được bảo vệ trước hội đồng chấm luận văn tại Học viện Công nghệ
Bưu chính Viễn thông
Vào lúc: giờ ngày tháng năm

Có thể tìm hiểu luận văn tại:
- Thư viện Học viện Công nghệ Bưu chính Viễn thông

1

LỜI MỞ ĐẦU

Bưu điện tỉnh Lạng Sơn là một doanh nghiệp kinh doanh các dịch vụ Bưu
chính, viễn thông trên địa bàn tỉnh Lạng Sơn, các dữ liệu dạng chuỗi ngày càng
2

xuất hiện nhiều trong quá trình sản xuất kinh doanh tại đơn vị và cho thấy có thể có
nhiều ứng dụng. Vì lý do đó, tôi chọn đề tài: “Nghiên cứu kỹ thuật gán nhãn cho
dữ liệu dạng chuỗi và ứng dụng”
Mục đích nghiên cứu: Nghiên cứu các dạng dữ liệu dạng chuỗi, các kỹ
thuật gán nhãn cho dữ liệu dạng chuỗi và các ứng dụng trong các bài toán có cấu
trúc trong thực tế.
Với mục tiêu cụ thể như sau:
- Nghiên cứu bài toán gán nhãn cho dữ liệu dạng chuỗi.
- Nghiên cứu một sỗ kỹ thuật gán nhãn cho dữ liệu dạng chuỗi cụ thể là
máy vecto hỗ trợ (Support Vector Machines –SVM)
s
, Mô hình Markov ẩn (Hidden
Markov Model – HMM), Mạng Markov với lề cực đại (Max Margin Markov
Network -M3N) và Trường ngẫu nhiêu điều kiện (Conditional Random Field –
CRF).
- Minh hoạ các kỹ thuật trên bằng hai bài toán thường gặp.
Đối tượng và phạm vi nghiên cứu:
Luận văn tập trung vào nghiên cứu các dữ liệu dạng chuỗi có cấu trúc, các
kỹ thuật gán nhãn cho dữ liệu dạng chuỗi, đây là một lĩnh vực giành được nhiều sự
chú ý trong Machine Learning và lĩnh vực mới thu hút sự quan tâm của nhiều đối
tượng. Kỹ thuật gán nhãn cho dữ liệu dạng và ứng dụng cụ thể của kỹ thuật này.
Phương pháp nghiên cứu:
Nghiên cứu lý thuyết trong các kỹ thuật gán nhãn cho dữ liệu dạng chuỗi,
nghiên cứu cụ thể kỹ thuật SVM, HMM, M3N và CRF. Nghiên cứu bài toán “Gán
nhãn từ loại” và bài toán “Nhận dạng ký tự viết tay” cùng với các ứng dụng trong
thực tế từ đó có hướng giải quyết cụ thể.

1.1 DỮ LIỆU DẠNG CHUỖI
Dữ liệu dạng chuỗi là một tập các phần tử được sắp thứ tự s:= a
1
, a
2
, a
n
.
Trong đó mỗi phần tử a
i
có thể là kiểu số hoặc có thể nhận giá trị rời rạc. Độ dài n
của chuỗi là không cố định, chuỗi được sắp theo thứ tự thời gian hoặc vị trí và có
thể sắp đều hoặc không.
Ngày nay, dữ liệu dạng chuỗi được ứng dụng thực tế trong nhiều ngành và
có vai trò quan trọng trong các bài toán phân loại hay nhận dạng.
1.2 BÀI TOÁN GÁN NHÃN CHO DỮ LIỆU DẠNG CHUỖI
Gán nhãn cho chuỗi là xác định nhãn phân loại cho từng thành phần trong
chuỗi quan sát được. Để xác định nhãn cho các thành phần của một chuỗi, ta có thể
xác định nhãn cho từng thành phần độc lập với các thành phần khác. Khi đó, bài
toán có thể coi như là một tập các nhiệm phụ phân lớp độc lập đối với các thành
phần của chuỗi. Tuy nhiên, có thể nhận thấy nhãn phân loại của mỗi thành phần lại
phụ thuộc vào nhãn các thành phần xung quanh. Vì vậy, việc gán nhãn cho chuỗi
cần được thực hiện theo phương pháp cho phép tính tới sự phụ thuộc giữa các nhãn
trong chuỗi với nhau. Từ đây dẫn tới nhu cầu phát triển và sử dụng kỹ thuật phân
loại đặc thù cho dữ liệu có dạng chuỗi.
Trong bài toán gán nhãn cho dữ liệu dạng chuỗi, đầu ra là chuỗi của các
nhãn y = (y
1
, y
2

Khi đó, với mỗi x, hãy tiên đoán y.
Gán nhãn cho dữ liệu dạng chuỗi được sử dụng nhiều trong các bài toán gán
nhãn từ loại, nhận dạng hình ảnh, âm thanh hay các bài toán về dự đoán gen. Mô
hình Markov ẩn đã thành công trong một thời gian dài với bài toán gán nhãn cho
dữ liệu dạng chuỗi. Gần đây, một số mô hình có điều kiện như Maximum Entropy
Markov Model (MEMM) và Conditional Random Field (CRF) được sử dụng nhiều
bởi khả năng cho phép các tính năng chồng chéoTrong đó CRF là phương pháp
được chú ý nhiều nhất.
Sự quan tâm dành cho bộ môn Trí tuệ nhân tạo cũng như bài toán gán nhãn
cho dữ liệu dạng chuỗi trong những năm gần đây là rất đáng kể. Nhiều công trình
nghiên cứu trong và ngoài nước đã và đang sử dụng gán nhãn cho dữ liệu dạng
chuỗi và có những ứng dụng nhất định. Trong những năm gần đây, việc giải bài
toán gán nhãn cho dữ liệu dạng chuỗi với dữ liệu có cấu trúc thu hút được nhiều sự
chú ý trong các vấn đề về xử lý ngôn ngữ tự nhiên. Mục đích của bài toán học có
cấu trúc là dự đoán được các cấu trúc phức tạp như chuỗi, cây hay đồ thị.

6 Chương 2
MỘT SỐ MÔ HÌNH GIẢI BÀI TOÁN GÁN NHÃN CHO DỮ

i,t+d-1
, x
i,t+d
>. Kết quả là với mỗi chuỗi đầu
vào x
i
được thêm vào một giá trị d null ở cuối và sau đó được chuyển thành N
i
mẫu
riêng biệt.
7

Phương pháp cửa sổ trượt cho kết quả tương đối tốt trong một số ứng dụng.
tuy nhiên phương pháp này không cho phép tính đến sự phụ thuộc giữa giá trị của
y
t
với các giá trị y khác gần đó.
Một cách để cải tiến mô hình cửa sổ trượt đã nêu ở trên là làm cho nó hồi
quy. Trong mô hình cửa sổ trượt hồi quy, các giá trị được dự đoán 
,
được cung
cấp như là đầu vào để hỗ trợ trong việc dự đoán giá trị y
i,t+1
. Cụ thể, với một cửa sổ
của nửa độ dài d, hầu hết các dự đoán d gần đây 
,
,
,
,…,
,

là một tập gồm m mẫu huấn luyện. Giả sử
rằng mỗi mẫu ̅

là được đưa vào từ miền  ⊆ 

và mỗi nhãn 

là một giá trị
nguyên từ tập =
{
1,…,
}
. Một bộ phân loại đa lớp là một hàm : → mà
ánh xạ một ̅ tới một phần tử y trong . Trong phần này ta tập trung vào nền tảng
mà sử dụng bộ phân loại được cho bởi


(
̅
)
= arg


{



.̅
}


|
Σ
|


ở đây 

= (= ), SVM học vector trọng số w và
biến lỏng ξ cho vấn đề tối ưu bậc hai sau đây
8

min
,

1
2
‖

‖

+







Với điều kiện ∀,∀∈ \


〉
với sự tìm kiếm đầy đủ của nhãn y.
Phương pháp này bao gồm một tham số điều chỉnh C là sự thoả hiệp giữa lỗi
huấn luyện và biên
2.3 MÔ HÌNH MARKOV ẨN (HMM)
Ta đã biết mô hình Markov là mô hình mà mỗi trạng thái tương ứng với một
sự kiện có thể quan sát được. Tuy nhiên các mô hình như vậy có ứng dụng rất hạn
chế trong các bài toán thực tế. Do đó, mô hình được mở rộng bao gồm cả những
trường hợp thống kê chồng kép với một quá trình thống kê mà bên trong không
quan sát được (ẩn sâu bên trong), chỉ có thể quan sát được thông qua một tập các
quá trình thống kê khác, các quá trình mà tạo ra dãy quan sát được. Mô hình như
vậy được gọi là mô hình Markov ẩn (HMM).
Một mô hình Markov ẩn học một mô hình có khả năng sinh qua các cặp đầu
vào, mỗi cặp gồm một chuỗi của các quan sát và chuỗi của các nhãn. Mô hình
Markov ẩn đã có được nhiều thành công trước đây, các mô hình Markov ẩn khó
mô hình các đa đặc trưng không độc lập. Đúng ra thì, cho trước một chuỗi quan
sát, ta có thể tìm được tuyến trạng thái có khả năng nhất cho chuỗi quan sát bằng
thuật toán Viterbi.
9

max


,

,…

P(q

q


=
Countq

,q


Count
(
q

)

Ở đây Countq

,q

 là số các lần qj xuất hiện theo qi.
Thứ hai, phân bố xác suất khởi tạo được tính như sau:
π

= P
(
q

)
=
Count
(
q

ở đây Counto

,q

 là số các lần ok được gán nhãn qj, và α là thông số làm
mịn. Thông số điều chỉnh cho trường hợp rời rạc là α.
Đối với các trường hợp khi các quan sát là các vector như bài toán nhận
dạng ký tự viết tay, ta sử dụng mô hình Markov ẩn với mật độ liên tục Gaussian để
mô hình xác suất từ trạng thái,
b

(
k
)
= Po

,q

= (μ

,Σ

)
10

Ở đây 

và 

là giá trị trung bình và ma trận hiệp phương sai (covariance)

,

= exp 




,

,


ở đây 
,
,

,

 là cặp hàm cơ bản. Tất cả các cạnh trong đồ thị biểu thị
cùng loại tương tác, do đó ta có thể định nghĩa một ánh xạ


(
,
)
=  

,

,

dụng công thức giống như trong công thức (2.4.6). Tuy nhiên M3N cũng cung cấp
một cách thông số hoá các biến đôi để có được các ưu điểm của cấu trúc mạng của
vấn đề gán nhãn cho dữ liệu dạng chuỗi.
2.5 MÔ HÌNH CÁC TRƯỜNG ĐIỀU KIỆN NGẪU NHIÊN (CRF)
CRF đưa ra một định nghĩa tốt về sự phân bổ xác suất dựa trên khả năng gán
nhãn, được huấn luyện bởi khả năng lớn nhất hay sự ước lượng MAP. CRF cũng
dễ dàng tổng quát hoá để tương tự với ngữ pháp phi ngữ cảnh ngẫu nhiên mà có
thể có ích trong một số vấn đề như dự đoán cấu trúc ARN bậc hai và xử lý ngôn
ngữ tự nhiên.
Định nghĩa. Lấy G = (V,E) là một đồ thị với Y = (

)
∈
, Y là tập các chỉ
mục các đỉnh của G. Với (X,Y) là một trường điều kiện ngẫu nhiên trong trường
hợp này, khi điều kiện được đặt trên X, các biến ngẫu nhiên Y
v
tuân theo thuộc tính
Markov đối với đồ thị: p(Y
v
|X, Y
w
, w≠v) = p(Y
v
|X, Y
w
, w ~ v), ở đây w ~ v nghĩa là
w và v là hàng xóm trong G.
Do đó, CRF là một trường ngẫu nhiên hoàn toàn có điều kiện trên quan sát
X.





(

)
,
(

)
∝
∑

(
,
)
log
,
(y|x)
12

Các đặc trưng là thành phần rất quan trọng trong thành công của các hệ
thống dựa trên CRF do các đặc trưng lọc những thông tin quan trọng nhất của dữ
liệu quan sát và mối quan hệ giữa dữ liệu đầu vào với đầu ra.
Vấn đề lựa chọn đặc trưng được biết đến một cách rộng rãi trong học máy
đối với các không gian đầu ra không có cấu trúc. Nói rộng ra, có ba hướng tiếp cận
đối với vấn đề này. Tiếp cận theo hướng lọc sử dụng một số thuật toán heuristic
nhanh và đơn giản để chọn các đặc trưng theo một vài tiêu chuẩn độc lập. Tiếp cận
theo hướng bao đánh giá rộng rãi các đặc trưng kết hợp theo biện pháp thực hiện

độ dài xấp xỉ 8 ký tự, từ 150 người khác nhau, dữ liệu này được thu thập bởi
Kassel. Tập dữ liệu này được chia thành 10 phần, mỗi phần xấp xỉ 600 dữ liệu
huấn luyện, 100 dữ liệu xác thực và xấp xỉ 5.400 mẫu kiểm tra. Các đặc trưng đầu
vào cho mỗi tín hiệu là một vector miêu tả bằng một hình ảnh nhị phân 16 x 8 của
chữ cái.
Để đánh giá hiệu suất của tất cả các mô hình, ta sử dụng lỗi trung bình
(AverageLoss) trên chuỗi:
=
1


1


(
(


)

≠
(


)






= s
(trạng thái bắt đầu) và y
T+1
= e

(trạng thái kết thúc). Tại thời điểm t một nhóm các
hàm đặc trưng 

được thiết lập.
Đối với bài toán gán nhãn từ loại, tập quan sát là các câu, đoạn văn trong văn
bản được sắp xếp theo một kiểu nhất định. Trong đó, mỗi từ và dấu nằm trên một
dòng. Tập các nhãn là các nhãn như trong Penn Treebank
Trong bảng 3.2.2, mỗi lỗi trung bình của các mô hình riêng biệt trên dữ liệu
kiểm tra đạt được bằng cách sử dụng sự thiết lập thông số với lỗi xác thực là tốt nhất.
Trong tất các mô hình trên, ta có thể thấy được mô hình CRF được coi như một
phương thức cho ta một kết quả tốt nhất trong bài toán này. Lý do có thể là các đặc
trưng đầu vào cho mỗi từ có chứa đựng nhiều thông tin của nó và các từ hàng xóm
của nó, với tập dữ liệu càng lớn thì CRF đạt độ chính xác càng cao. Các mô hình
SVM và M3N cũng đạt được kết quả khá tốt, gần với kết quả của CRF.
Kích thước tập
huấn luyện
500 1.000 2.000 4.000 8.000
SVM

8,76 6,93 5,77 5,32 5,13
M3N 10,19 7,26 6,34 5,54 5,01
CRF 12,25 7,11 6,28 5,03 4,62
HMM 23,46 19,95 17,96 17,58 15,87
Bảng 3.2.2 Lỗi trung bình của các mô hình đối với bài toán gán nhãn từ loại
với các kích thước tập dữ liệu khác nhau (tính theo %)

0.2300
0.2350
0.2400
0.2450
0.2500
0.2550
0.2600
0.2650
SVM
-
Multiclas
CRF
M3N
HMM
Do ton that trung binh
16

để đạt được kết quả tốt nhất. Ta cũng thấy CRF đã cho hiệu quả tốt nhất trong việc
giải bài toán gán nhãn từ loại cũng như bài toán nhận dạng ký tự viết tay. Bên cạnh
đó, các phương pháp SVM và M3N cũng thực hiện tương đối tốt công việc này.


Mặc dù có rất nhiều cố gắng trong nghiên cứu thực hiện luận văn, được sự
chỉ bảo nhiệt tình của thầy giáo hướng dẫn, PGS.TS Từ Minh Phương, và sự động
viên giúp đỡ của bạn bè, đồng nghiệp nhưng luận văn không thể tránh khỏi những
thiếu sót. Rất mong nhận được sự góp ý bổ sung của các thầy giáo, cô giáo và mọi
người để luận văn được hoàn thiện hơn.