ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

MAI VĂN THỦY

NGHIÊN CỨU VỀ MÔ HÌNH THỐNG KÊ HỌC SÂU
VÀ ỨNG DỤNG TRONG NHẬN DẠNG CHỮ VIẾT
TAY HẠN CHẾ

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN - 2015

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

MAI VĂN THỦY

NGHIÊN CỨU VỀ MÔ HÌNH THỐNG KÊ HỌC SÂU
VÀ ỨNG DỤNG TRONG NHẬN DẠNG CHỮ VIẾT
TAY HẠN CHẾ
Chuyên ngành : Khoa Học Máy Tính
Mã số
: 60 48 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH


http://www.lrc-tnu.edu.vn/


iv

MỤC LỤC
LỜI CAM ĐOAN ....................................................................................................... i
MỤC LỤC ................................................................................................................. iv
DANH MỤC HÌNH ẢNH ........................................................................................ vi
DANH MỤC BẢNG BIỂU .....................................................................................vii
LỜI MỞ ĐẦU ............................................................................................................ 1
Chương 1: GIỚI THIỆU ĐỀ TÀI............................................................................ 3
1.1. Giới thiệu về bài toán nhận dạng .................................................................. 3
1.1.1. Các giai đoạn phát triển ............................................................................. 3
1.1.2. Tình hình nghiên cứu trong nước .............................................................. 4
1.1.3. Tình hình nghiên cứu ở nước ngoài ........................................................... 4
1.2. Các bước xử lý cho bài toán nhận dạng hoàn chỉnh ................................... 6
1.3. Kết luận chương ............................................................................................. 8
Chương 2: MÔ HÌNH SVM VÀ MÔ HÌNH THỐNG KÊ HỌC SÂU ................. 9
2.1. Tổng quan về mô hình SVM (Support Vector Machine) ........................... 9
2.1.1. Cơ sở lý thuyết ........................................................................................... 9
2.1.1.1. Giới thiệu bài toán phân lớp nhị phân ................................................. 9
2.1.1.2. Máy SVM tuyến tính......................................................................... 10
2.1.1.3. Máy SVM phi tuyến .......................................................................... 17
2.1.2. Các thuật toán huấn luyện SVM .............................................................. 19
2.1.2.1. Thuật toán chặt khúc ......................................................................... 19
2.1.2.2. Thuật toán phân rã............................................................................. 19
2.1.2.3. Thuật toán cực tiểu tuần tự................................................................ 20
2.2. Cơ sở lý thuyết mô hình thống kê học sâu ................................................. 23

3.5. Đánh giá kết quả thực nghiệm của hai mô hình. ....................................... 50
3.6. Kết luận chương ........................................................................................... 51
KẾT LUẬN CHUNG .............................................................................................. 52
TÀI LIỆU THAM KHẢO ...................................................................................... 54
PHỤ LỤC: HUẤN LUYỆN MÔ HÌNH ................................................................ 56

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


vi

DANH MỤC HÌNH ẢNH
Hình 1-1: Các bước trong nhận dạng chữ viết tay ...................................................... 6
Hình 2-1: Các siêu phẳng H 1 , H 2 phân cách giữa hai lớp ......................................... 9
Hình 2-2: Siêu phẳng tách tuyến tính ....................................................................... 10
Hình 2-3: Không thể phân hoạch tập mẫu trên bằng một siêu phẳng ....................... 13
Hình 2-4: Một mặt phân chia phi tuyến có thể trở thành một siêu phẳng trong không
gian lớn hơn. ............................................................................................ 17
Hình 2-5: Cấu trúc của một neuron .......................................................................... 24
Hình 2-6: Cấu trúc chung của mạng neuron ............................................................. 26
Hình 2-7: Cấu trúc của mạng Hopfield ..................................................................... 31
Hình 2-8: Đồ thị hàm satlins ..................................................................................... 32
Hình 2-9: Mạng Hopfield liên tục sử dụng mạch điện tử. ........................................ 35
Hình 2-10: Một Boltzmann Machine với 3 nút ẩn .................................................... 36
Hình 2-11: Một RBM đơn giản với 3 hidden units và 2 visible units. .................... 39
Hình 3-2: Giao diện chính của chương trình nhận dạng chữ viết tay hạn chế ......... 48
Hình 3-3: Chương trình khi nhận dạng 1 ảnh bất kỳ ................................................ 48
Hình 3-4: Nhận dạng và thống kê nhiều ảnh ............................................................ 49

các bài toán trong thực tế. Cũng như nhiều bài toán nhận dạng tiếng nói, hình
ảnh… khác, thì độ chính xác của hệ thống vẫn tiếp tục cần phải cải thiện nhằm
vươn tới khả năng nhận dạng giống như con người.
Tuy nhiên, với bài toán nhận dạng chữ viết tay thì vấn đề trở nên phức tạp hơn
nhiều so với bài toán nhận dạng chữ in thông thường ở những vấn đề sau đây [3]:
 Với chữ viết tay thì không thể có các khái niệm font chữ, kích cỡ chữ. Các
kí tự trong một văn bản chữ viết tay thường có kích thước khác nhau. Thậm
chí, cùng một kí tự trong một văn bản do một người viết nhiều khi cũng có
độ rộng, hẹp, cao, thấp khác nhau,...
 Với những người viết khác nhau chữ viết có độ nghiêng khác nhau (chữ
nghiêng nhiều/ít, chữ nghiêng trái/phải...).
 Các kí tự của một từ trên văn bản chữ viết tay đối với hầu hết người viết
thường bị dính nhau vì vậy rất khó xác định được phân cách giữa chúng.
 Các văn bản chữ viết tay còn có thể có trường hợp dính dòng (dòng dưới bị
dính hoặc chồng lên dòng trên).
Trong những năm gần đây, mô hình mạng Neuron theo hướng học sâu đã cho
thấy những kết quả tốt trong nhiều bài toán khác nhau, trong đó có nhận dạng chữ.
Xuất phát từ yêu cầu thực tế, đang rất cần có nhưng nghiên cứu về vấn đề này.
Chính vì vậy học viên đã chọn đề tài “Nghiên cứu về mô hình thống kê học sâu
và ứng dụng trong nhận dạng chữ viết tay hạn chế” làm luận văn tốt nghiệp với
mong muốn phần nào áp dụng vào bài toán thực tế.
Bài toán đã đặt ra phải giải quyết được những yêu cầu sau:
 Nhận dạng được các ký tự từ ảnh đầu vào
Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


2


Giới thiệu về bài toán nhận dạng

Nhận dạng chữ in: đã được giải quyết gần như trọn vẹn (sản phẩm FineReader
11 của hãng ABBYY có thể nhận dạng chữ in theo 192 ngôn ngữ khác nhau, phần
mềm nhận dạng chữ Việt in VnDOCR 4.0 của Viện Công nghệ Thông tin – Viện
Hàn lâm Khoa học và Công nghệ Việt Nam có thể nhận dạng được các tài liệu chứa
hình ảnh, bảng và văn bản với độ chính xác trên 98%).
Nhận dạng chữ viết tay vẫn còn là vấn đề thách thức lớn đối với các nhà nghiên
cứu. Bài toàn này chưa thể giải quyết trọn vẹn được vì nó hoàn toàn phụ thuộc vào
người viết và sự biến đổi quá đa dạng trong cách viết và trạng thái sức khỏe, tinh
thần của từng người viết.
1.1.1. Các giai đoạn phát triển
 Giai đoạn 1 (1900 - 1980)
-

Nhận dạng chữ được biết đến từ năm 1900, khi nhà khoa học người Nga Alan
Turing (1912-1954) phát triển một phương tiện trợ giúp cho những người mù.

-

Các sản phẩm nhận dạng chữ thương mại có từ những năm1950, khi máy tính
lần đầu tiên được giới thiệu tính năng mới về nhập và lưu trữ dữ liệu hai chiều
bằng cây bút viết trên một tấm bảng cảm ứng.Công nghệ mới này cho phép các
nhà nghiên cứu làm việc trên các bài toán nhận dạng chữ viết tay online.

-

Mô hình nhận dạng chữ viết được đề xuất từ năm 1951 do phát minh của M.
Sheppard được gọi là GISMO, một robot đọc-viết.


Trong giai đoạn này, các hướng nghiên cứu chỉ tập trung vào các kỹ thuật
nhận dạng hình dáng chứ chưa áp dụng cho thông tin ngữ nghĩa. Điều này
dẫn đến sự hạn chế về hiệu suất nhận dạng, không hiệu quả trong nhiều ứng
dụng thực tế.

 Giai đoạn 3 (1990 - nay)
-

Các hệ thống nhận dạng thời gian thực được chú trọng trong giai đoạn này.

-

Các kỹ thuật nhận dạng kết hợp với các phương pháp luận trong lĩnh vực học
máy (Machine Learning) được áp dụng rất hiệu quả.

-

Một số công cụ học máy hiệu quả như mạng Neuron, mô hình Markov ẩn,
SVM (Support Vector Machines) và xử lý ngôn ngữ tự nhiên...

1.1.2. Tình hình nghiên cứu trong nước
Tại Việt Nam, trong những năm gần đây có rất nhiều những nhóm nghiên cứu
về nhận dạng chữ viết tay sử dụng các mô hình phổ biến hiện nay như: SVM
(Support Vector Machine), HMM (Hidden Markov Model), mạng Neuron… Nhưng
nhìn chung thì chất lượng nhận dạng của các mô hình này đều chưa cao vì chữ viết
tay còn nhiều các yếu tố tác động đến như: độ cao, độ nghiêng, các nét liền… của
chữ viết đều ảnh hưởng rất nhiều đến quá trình nhận dạng. Hiện tại, chúng ta mới
chỉ có được những sản phẩm thử nghiệm như hệ thống nhận dạng chữ số và chữ cái
viết tay rời rạc trên các phiếu xuất nhập cảnh của nhóm nghiên cứu ở Đại học quốc
gia thành phố Hồ Chí Minh,…

 Các kí tự có thể thiếu hoặc thừa nét.
 Xuất hiện tình trạng dính dòng.
Do những khó khăn trên nên khi giải quyết bài toán nhận dạng chữ viết tay đều
buộc phải giới hạn trong một phạm vi nào đó với những tiêu chuẩn cụ thể cho mẫu
chữ nhận dạng. Chính vì vậy, các kết quả thu được cũng chỉ được áp dụng một cách
hạn chế ở lĩnh vực hẹp trong một bài toán cụ thể nào đó.
Một số hệ nhận dạng chữ viết tay tiêu biểu có thể kể đến như: hệ thống nhận
dạng chữ viết tay trong lĩnh vực kiểm tra tài khoản ở ngân hàng của nhóm nghiên
cứu Simon và O.Baret (Laoria/CNRS & ENPC, Paris) [11], hệ thống phân loại tự
động địa chỉ thư ở bưu điện của M.Pfister, S.Behnke và R.Rojas ở Đại học tổng hợp
Berlin, Đức [5]….

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


6

1.2.

Các bước xử lý cho bài toán nhận dạng hoàn chỉnh

Nhận dạng chữ viết tay thường bao gồm năm giai đoạn: tiền xử lý (preprocessing),
tách chữ (segmentation), trích chọn đặc trưng (representation), huấn luyện và nhận
dạng (training and recognition), hậu xử lý (postprocessing).

Hình 1-1: Các bước trong nhận dạng chữ viết tay
 Tiền xử lý (preprocessing): giảm nhiễu cho các lỗi trong quá trình quét ảnh,
hoạt động viết của con người, chuẩn hóa dữ liệu và nén dữ liệu.

đến 255). Tại quá trình tiền xử lý thì ảnh cũng đã được xử lý loại bỏ nhiễu,
các giá trị không cần thiết trong ảnh đầu vào.
Tại bước tách chữ thì với ảnh đã được tiền xử lý, khi đi qua bước này sẽ
được thực hiện tách dòng, tách chữ, tách kí tự để thực hiện nhận dạng, tùy
theo quy định của một hệ thống khi huấn luyện. Khi đã được tách rời các kí
tự thì việc tiếp theo ảnh để nhận dạng sẽ được lưu dưới dạng ma trận điểm,
với tùy từng vị trí của điểm ảnh mà giá trị có thể khác nhau (từ 0 đến 255),
trong mô hình Deep Learning thì ma trận điểm ảnh sẽ được quy về dạng
chuẩn là 28 x 28.
Sau khi qua các bước xử lý ở trên thì ảnh chính thức được đưa vào huấn
luyện và nhận dạng, trong quá trình huấn luyện và nhận dạng sẽ sử dụng các mô
hình và thuật toán cần thiết để thực hiện tính toán và xử lý, những thuật toán và
quá trình xử lý sẽ được trình bày chi tiết trong các phần sau của luận văn.
Cuối cùng khi các ảnh đầu vào đã được đưa vào nhận dạng và cho ra kết
quả thì bước quan trọng không kém là quá trình hậu xử lý với các kết quả ở
trên, và trả lại kết quả cho người dử dụng. [3]

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


8

1.3.

Kết luận chương

Luận văn “Nghiên cứu về mô hình thống kê học sâu và ứng dụng trong nhận
dạng chữ viết tay hạn chế” được thực hiện với mục đích giải quyết một lớp con các

gồm N mẫu huấn luyện { ( x1 , y1 ),...,( xN , y N ) } trong đó xi

RD và yi

{±1}. Tìm

một siêu phẳng phân cách w.x + b = 0 để tách tập dữ liệu trên thành 2 lớp, trong đó
w là véc tơ pháp tuyến của siêu phẳng, có tác dụng điều chỉnh hướng của siêu
phẳng, giá trị b có tác dụng di chuyển siêu phẳng song song với chính nó. Có thể có
nhiều siêu phẳng để phân cách được hai tập dữ liệu đó (hình dưới) và cũng đã có
nhiều thuật toán để giải bài toán này, chẳng hạn như thuật toán Perceptron của
Rosenblatt, thuật toán biệt thức tuyến tính của Fisher. Tuy nhiên vấn đề là cần tìm
ra siêu phẳng nào làm cho khoảng cách Euclid giữa hai lớp trên là lớn nhất, khi đó
bài toán phân lớp mới được giải quyết triệt để và phương pháp SVM được sử dụng
để giúp tìm ra siêu phẳng này. [2]

Hình 2-1: Các siêu phẳng H 1 , H 2 phân cách giữa hai lớp
Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


10

2.1.1.2.

Máy SVM tuyến tính

SVM trong trường hợp tập mẫu phân hoạch tuyến tính được
Ý tưởng chính của SVM là tìm một siêu phẳng phân cách H: w.x + b = 0 [8] và hai

khoảng cách giữa H 1 và H 2 là

tới H là

| wx b |
|| w ||

1
và
|| w ||

2
. Do đó, trong trình tự để cực đại hóa khoảng
|| w ||

cách này, ta sẽ cực tiểu || w || wT .w với điều kiện không có điểm dữ liệu nào nằm
giữa H 1 và H 2 :
w.x + b> +1, với các mẫu dương yi
w.x + b< -1, với các mẫu âm yi

1
1

Hai điều kiện này có thể kết nối lại thành

yi ( wxi b) 1
Từ đó bài toán có thể được phát biểu lại như sau:
1
min wT w sao cho yi ( wxi
w ,b 2

2

Số hóa bởi Trung tâm Học liệu - ĐHTN

N

N
i yi ( wxi

i 1

:

b)

i
i 1

http://www.lrc-tnu.edu.vn/


12

Từ (1) và (2) ta có:
N

N

và
i yi xi

yi y j xi x j

i, j

tương ứng với mỗi mẫu học. Khi đã

được gọi là vectơ hỗ trợ, tất cả các mẫu học

thì nằm về hai phía của siêu phẳng

khác có

Khi đã giải được các

và

. [4][6]

ta có thể tính:
N

w

i

yi xi và b

i 1

Như vậy, một đối tượng mới x sẽ được phân lớp theo hàm mực tiêu:

tính được bằng siêu phẳng.

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


13

Hình 2-3: Không thể phân hoạch tập mẫu trên bằng một siêu phẳng
Tuy nhiên ta vẫn muốn dùng siêu phẳng để phân chia tập mẫu này. Để có thể áp
dụng được phương pháp trong phần trên, ta phải gán cho mỗi mẫu xi một sai số
không âm để “xem như có thể phân chia tuyến tính”.

wxi b

1

i

với yi

1

wxi b

1

i


yi ( wT xi

b)

i

1 0, 1 i

Số hóa bởi Trung tâm Học liệu - ĐHTN

N

http://www.lrc-tnu.edu.vn/

i


14

01 i

i

N

Với các hệ số Lagrange α, công thức Lagrange sẽ là:
N
1 T
w w C
2


1 T
w w
2
Cả

N

N
T
(
i yi xi ) w

(

i

i 1

i 1

N
i yi )b

i 1

i
i 1

và các hệ số Lagrange đều không xuất hiện trong bài toán đối ngẫu của


i

yi

0

i 1

Sự khác nhau duy nhất so với trường hợp phân lớp cứng là

bị chặn trên bới C

thay vì ∞.
Giải pháp này một lân nữa được cho bởi:
N

w

i

yi xi

i 1

Để huấn luyện SVM, chúng ta nghiên cứu thông qua miền xác định của bài toán đối
ngẫu và cực đại hàm mục tiêu. Giải pháp tối ưu này có thế được kiểm tra bằng cách
sử dụng điều kiện KKT.
Định lý KKT: Điều kiện tối ưu KKT của bài toán đối ngẫu (**) là:
Đạo hàm L (w, b, ξ; α) theo các biến w, b, ξ phải triệt tiêu (điều này buộc


i

i

C

Từ phương trình (4),

, ta có ba trường hợp để xem xét:
i

i

C

0

0 . Vì vậy ta có: yi ( wT xi b) 1 0

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


15

2. Nếu 0

i


b) 1 0

C , từ phương trình (3) ta có:

i

yi ( wT xi

Chú ý rằng

C

i

0 , ta có

i

b)

0 . Vì vậy:

i

yi ( wT xi

Đại lượng yi ( wT xi
Ri


0

0
C

i

i

c

Ri

0,

Ri

0,

Ri

0

Trong hai trường hợp sau, điều kiện KKT không thỏa mãn:



i

C và Ri


b)

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


16

yi ( F b)
Trong đó:

wT xi - yi .

Fi

Chú ý: Với Ei

Fi - Fj . (Phương trình này rất có ích,

Fi b , ta có Ei - E j

vì thuật toán SMO của Platt sử dụng Ei - E j khi tối ưu hai hệ số Lagrange
i

,

j


I2

Fi

b

i

I0

I3

I4

Fi

b

Trong đó:

Sao cho

i

I0

I0

i:0


I4

i : yi

1,

i

0

I1

C

i

j

I 2 và

I0

I3

I 4 , ta sẽ có Fi

Fj nếu điều kiện

KKT thỏa mãn.
Để kiểm tra nếu điều kiện này đúng, ta định nghĩa:


blow , và tương tự
I0

I3

I 4 , Fup

bup . Việc so sính này không

sử dụng ngưỡng b .
Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


17

2.1.1.3.

Máy SVM phi tuyến

Trong trường hợp tổng quát, thực tế mặt phân hoạch có thể là một mặt
phi tuyến bất kỳ (Hình 2-4). Nếu dữ liệu không khả tách tuyến tính, ta có thể ánh xạ
các dữ liệu đầu vào sang một không gian đặc trưng mới có số chiều cao hơn sao cho
dữ liệu này sẽ khả tách tuyến tính. Giả sử các mẫu xi thuộc không gian R n , không
gian này được gọi là không gian giả thiết (hypothesis space). Để tìm mặt phẳng phi
tuyến trong không gian này, có thể áp dụng một thủ thuật là ánh xạ vector mẫu xi từ

Rn vào một khoảng không gian Rd có số chiều cao lớn hơn (d > n, d có thể bằng vô


LD

i
i 1

Giả sử:

( xi ). ( x j )

1
2

i

j

yi y j ( xi ). ( x j )

i, j

K ( xi , x j ) . Nghĩa là, tích vô hướng trong không gian

đặc trưng tương đương với một hàm nhân (kernel) của không gian đầu vào. Vì vậy,
ta không cần phải tính trực tiếp

( xi ). ( x j )

mà chỉ cần thông qua hàm nhân


K ( x, y) ( x. y

)d

d

N,

R

 Hàm nhân Gauss (Gaussian RBF-Radial Basic Function):
K ( x, y ) e

|| x y||2
2 2

 Hàm nhân tuyến tính (Linear)

K ( x, y )

Số hóa bởi Trung tâm Học liệu - ĐHTN

x. y

http://www.lrc-tnu.edu.vn/