I HC THI NGUYấN
TRNG I HC CễNG NGH THễNG TIN & TRUYN THễNG

MAI VN THY

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ế

LUN VN THC S KHOA HC MY TNH

THáI NGUYÊN - 2015


I HC THI NGUYấN
TRNG I HC CễNG NGH THễNG TIN & TRUYN THễNG

MAI VN THY

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 ngnh : Khoa Hc Mỏy Tớnh
Mó s
: 60 48 01

LUN VN THC S KHOA HC MY TNH
NGI HNG DN KHOA HC

TS. V Tt Thng

THáI NGUYÊN - 2015


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
2.2.1. Một số lý thuyết về mạng Neuron ......................................................... 23
2.2.1.1. Giới thiệu về mạng Neuron ............................................................ 23
2.2.1.2. Cấu trúc và hoạt động của mạng Neuron ........................................ 23
2.2.1.3. Quá trình huấn luyện mạng và các thuật toán học mạng ................. 28


v

2.2.2. Hopfield Network ................................................................................. 31
2.2.2.1. Cấu trúc mạng Hopfield ................................................................. 31
2.2.2.2. Mạng Hopfield rời rạc .................................................................... 33
2.2.2.3. Mạng Hopfield liên tục .................................................................. 34
2.2.3. Boltzmann Machines ............................................................................ 36

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


vii

DANH MỤC BẢNG BIỂU

Bảng 2-1: Các hàm truyền cơ bản.......................................................................... 27
Bảng 3-1: Kết quả thực nghiệm mô hình SVM trên 2 tập dữ liệu MNIST và Tuyển
Sinh ....................................................................................................... 44
Bảng 3-2: Kết quả thực nghiệm mô hình SVM trên tập dữ liệu MNIST ................ 44
Bảng 3-3: Kết quả thực nghiệm mô hình SVM trên tập dữ liệu Tuyển Sinh .......... 45
Bảng 3-4: Kết quả thực nghiệm trên 2 tập dữ liệu MNIST và Tuyển Sinh ............. 49
Bảng 3-5: Kết quả thực nghiệm trên tập dữ liệu Tuyển sinh .................................. 50
Bảng 3-6: Bảng so sánh kết quả giữa hai mô hình ................................................. 50


1

LỜI MỞ ĐẦU
Nhận dạng chữ viết tay là bài toán khó trong lớp các bài toán nhận dạng chữ, và

 Tiến hành nhận dạng kí tự đơn lẻ sử dụng mạng Neuron nhân tạo
theo phương pháp học sâu Restricted Boltzmann machine (RBM).
 Đánh giá kết quả và so sánh với mô hình Support Vector Machine
Với nhưng yêu cầu đã đặt ra ở trên, cấu trúc của luận văn sẽ bao gồm những
nội dung sau đây:
 Chương 1:Tổng quan về đề tài
Giới thiệu về bài toán nhận dạng chữ viết tay, tình hình nghiên cứu trong và
ngoài nước, quy trình chung để giải quyết bài toán và các phương pháp điển
hình trong việc huấn luyện nhận dạng, phạm vi của đề tài.
 Chương 2: Mô hình SVM và mô hình thống kê học sâu
Trình bày về cơ sở lý thuyết của mô hình SVM (Support Vector Machine)
và huấn luyện trong bài toán nhận dạng chữ viết tay. Cơ sở lý thuyết của mô
hình thống kê học sâu: Hopfield network, Boltzmann Machines, Restricted
Boltzmann Machines và thuật toán lan truyền ngược.
 Chương 3: Kết quả thực nghiệm và đánh giá
Trình bày các kết quả thực nghiệm của hai mô hình SVM và mô hình thống
kê học sâu, đưa ra kết quả đánh giá nhận dạng chữ viết tay hạn chế giữa mô
hình SVM và mô hình thống kê học sâu.


3

Chương 1
GIỚI THIỆU ĐỀ TÀI
1.1.

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


-

Năm 1967, Công ty IBM đã thương mại hóa hệ thống nhận dạng chữ.

 Giai đoạn 2 (1980 - 1990)
-

Với sự phát triển của các thiết bị phần cứng máy tính và các thiết bị thu nhận dữ
liệu, các phương pháp luận nhận dạng đã được phát triển trong giai đoạn trước


4

đã có được môi trường lý tưởng để triển khai các ứng dụng nhận dạng chữ.
-

Các hướng tiếp cận theo cấu trúc và đối sánh được áp dụng trong nhiều hệ
thống nhận dạng chữ.

-

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)
-


5

các chữ được viết lên màn hình ngay sau khi nó được viết. Đối với những hệ nhận
dạng này, máy tính sẽ lưu lại các thông tin về nét chữ như thứ tự nét viết, hướng và
tốc độ của nét viết trong khi nó đang được viết ra. Đây chính là cơ sở để máy tính
nhận dạng được chữ cái, do đó việc nhận dạng không gặp quá nhiều khó khăn. Hệ
thống nhận dạng chữ viết tay hạn chế trực tuyến trên một trạm làm việc của IBM
[11] do nhóm nghiên cứu gồm H.S.M.Beigi, C.C.Tapert, M.Ukeison và C.G.Wolf ở
phòng thực hành Watson IBM cài đặt là một trong những sản phẩm nhận dạng chữ
viết tay online tiêu biểu nhất. Tuy nhiên, do chưa có nhiều ứng dụng thực tế nên
nhận dạng chữ viết tay trực tuyến chưa được biết đến nhiều và khi nhắc đến nhận
dạng chữ viết tay chúng ta thường hiểu hình thức nhận dạng ở đây là offline.
Các kết quả nhận dạng chữ viết tay offline hiện này còn rất hạn chế. Các kết quả
nghiên cứu chưa tìm được giải pháp đủ tốt để giải quyết hết những khó khăn tiêu
biểu sau của bài toán nhận dạng chữ viết tay:
 Kích thước của chữ viết tay không đồng đều.
 Kiểu dáng chữ của mỗi người viết đều rất khác nhau.
 Giữa các kí tự trong cùng một từ thường có nét nối, thậm chí dính liền vào
nhau.
 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]….


nhân tạo hay dùng phương pháp kết hợp các phương pháp trên.Trong luận
văn này, tôi sử dụng mô hình thống kê học sâu (deep learning) để huấn
luyện và nhận dạng, nội dung này sẽ được trình bày trong các chương sau
của luận văn.
 Hậu xử lý (postprocessing): sử dụng các thông tin về ngữ cảnh để giúp tăng
cường độ chính xác, dùng từ điển dữ liệu.
Ban đầu các văn bản chữ viết tay được scan và đưa vào hệ thống nhận
dạng, với quá trình tiền xử lý thì ảnh sẽ được một ảnh mà do hệ thống yêu
cầu để huấn luyện và nhận dạng (có thể là ảnh nhị phân hay ảnh đa mức
xám). Trong mô hình thống kê học sâu, ảnh được sử dụng để huấn luyện và
nhận dạng là ảnh đa mức xám (các pixel được biểu diễn bởi các giá trị từ 0
đế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]




Giới thiệu bài toán phân lớp nhị phân

Bài toán phân lớp nhị phân [7] này được phát biểu như sau: Cho tập dữ liệu
gồm N mẫu huấn luyện { ( x1 , y1 ),...,( xN , yN ) } 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 H1 , H 2 phân cách giữa hai lớp


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
siêu phẳng song song với nó:

H1 : y  wx  b  1


giữa H1 và H 2 :
w.x + b> +1, với các mẫu dương yi  1
w.x + b< -1, với các mẫu âm yi  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  b)  1
w ,b 2

(*)

Thay vì giải bài toán (*), ta có thể giải bài toán đối ngẫu của Wolfe để thay thế: cực
đại L (w, b, α) theo α, sao cho đạo hàm của L (w, b, α) triệt tiêu theo các biến w và
b:

L
0
w

(1)

L
0
b

(2)

Và α ≥ 0

i 1

Thế vào L (w, b, α), ta có:
N

LD    i 
i 1

1
 i j yi y j xi x j
2 i, j

Ở đây chúng ta có các hệ số Largrang
huấn luyện xong, những mẫu có
khác có

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

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

và

. [4][6]

ta có thể tính:
N

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 với yi  1

i  0i  1,2,..., N
Bổ sung vào hàm mục tiêu một giới hạn cân bằng:

1
min wT w  C ( i )m
w ,b , 2
i
Trong đó m thường được chọn là 1, như vậy bài toán tối ưu trở thành:
N
1
min wT w  C  i
w ,b , 2
i 1

Sao cho:
yi ( wT xi  b)   i  1  0, 1  i  N


14

i  0 1  i  N
Với các hệ số Lagrange α, công thức Lagrange sẽ là:

L( w, b, i ; ) 




i 1

1
  i j yi y j xi x j
2 i, j

(**)

Sao cho:
N

0  i  C và

 y
i

i

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:


Chú ý rằng i  C  i  0 , vì vậy i  0 (phương trình 4). Thế vào phương
trình (5) ta có:
yi ( wT xi  b)  1  0

3. Nếu i  C , từ phương trình (3) ta có:
yi ( wT xi  b )   i  1  0

Chú ý rằng i  C  i  0 , ta có i  0 . Vì vậy:
yi ( wT xi  b)  1  0

Đại lượng yi ( wT xi  b )  1 có thể được tính với lỗi dự đoán là:
Ri  yi ( wT xi  b ) - yi2  yi ( wT xi  b - yi )  yi Ei
Ei  wT xi  b - yi  ui - yi

Trong đó :

Tóm lại, điều kiện KKT muốn nói rằng:

i  0



Ri  0 ,

0  i  C



Ri  0 ,


 i ,  j .)
Ký hiệu này là hữu ích bởi điều kiện KKT

i  0



yi ( Fi  b)  0 ,

0  i  C



yi ( Fi  b)  0 ,

i  C



yi ( Fi  b)  0 .

Có thể viết là

i  I 0  I1  I 2



Fi  b


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ừ

R n vào một khoảng không gian R d có số chiều cao lớn hơn (d > n, d có thể bằng vô
cùng). R d được gọi là không gian đặc trưng (feature space). Sau đó áp dụng phương
pháp SVM tuyến tính để tìm ra một siêu phẳng phân hoạch trong không gian đặc trưng

R d . Siêu phẳng này sẽ là ứng với mặt phi tuyến trong không gian R n . [2]

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.
Ánh xạ từ không gian R n vào không gian R d ;
Gọi ánh xạ được áp dụng là  , như vậy:

 : Rn  Rd
x  ( x )

Áp dụng siêu phẳng phân hoạch mềm (soft-margin hyperplane) trong không
gian R d cho các mẫu ( xi ) thì siêu phẳng này sẽ là:


18

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 )  x. y