HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN

BÀI TẬP TRÍ TUỆ NHÂN TẠO
Học tăng cường và ứng dụng trong nhận dạng ký tự viết tay

Người hướng dẫn: TS Ngô H u Phúcữ
Người thực hiện: Nguy n Anh C ngễ ườ
Lớp: Cao học CNTT - HN1 - K23
Hà Nội 2014
Nguyễn Anh Cường  2/15
1. HỌC TĂNG CƯỜNG
Học tăng cường là phương pháp học thông qua tương tác với môi trường. Mô hình
của học tăng cường gồm có 3 thành phần chính: tác tử (agent), môi trường (environment)
và giá trị phản hồi (reward). Quá trình học là một quá trình lặp đi lặp lại (iteration) các
hành động (action). Sau khi thực hiện mỗi hành động thì agent nhảy từ vị trí (hay trạng
thái - state) này sang vị trí (trạng thái) khác, và đồng thời nhận được giá trị phản hồi
(reward) từ hành động cũ. Dựa vào các giá trị phản hồi nhận được agent có thể điều chỉnh
luật chọn hành động (policy) của mình trong các bước tiếp theo. Việc điều chỉnh và tối
ưu hóa luật chọn hành động dựa vào các giá trị phản hồi chính là quá trình học tăng
cường. Rõ ràng là quy luật chọn lựa hành động của agent thu được sau quá trình học càng
gần tối ưu nếu quá trình học càng kéo dài và số lượng các tình huống mà agent gặp phải
là càng nhiều.
Hình 1. Mô hình tương tác agent - môi trường
Với mô hình học tăng cường như vậy thì vấn đề cần giải quyết là các thông
tin phản hồi (reward) được xử lý như thế nào. Sau mỗi hành động thì agent nhận
được một giá trị phản hồi và sau một quá trình học lâu dài thì số lượng các thông
tin phản hồi này là rất lớn mà tại mỗi thời điểm không thể quan tâm đến tất cả mọi
giá trị này được. Để giải quyết vấn đề này thì mô hình học tăng cường được đưa về
mô hình Markov (MDP - Markov Decision Process), là sự mở rộng của chuỗi
Markov. Chuỗi Markov là một quá trình ngẫu nhiên mà giá trị hàm xác suất

= = = =
Ta gọi giá trị “return” là tổng của các giá trị phản hồi tính từ thời điểm hiện
tại cho đến khi agent đạt đến đích, hoặc đến cuối giai đoạn (nếu quá trình học được
chia thành nhiều giai đoạn - episode).
R
t
= r
t+1
+ r
t+2
+…+r
T
Trong đó T là bước cuối cùng trước khi đến đích.
Thực nghiệm cho thấy nếu ta giảm dần mức độ quan trọng của các bước ở
các thời điểm xa với thời điểm hiện tại thì quá trình học sẽ hội tụ nhanh hơn. Điều
đó có nghĩa là ta cần thêm vào hệ số khấu hao γ. Giá trị phản hồi ở thời điểm cách
hiện tại bao nhiêu bước thời gian thì sẽ được nhân với giá trị khấu hao γ bấy nhiêu
lần. Như vậy giá trị “return” sẽ được tính như sau:
2
1 2 3 1
0

k
t t t t t k
k
R r r r r
γ γ γ
∞
+ + + + +
=

t t t t k t t
k
Q s a E R s s a a E r s s a a
π
π π
γ
∞
+ +
=
= = = = = =
∑
Quá trình học tăng cường là quá trình tìm kiếm policy tối ưu, có nghĩa là quá
trình điều chỉnh giá trị của hàm giá trị về giá trị tối ưu. Quá trình điều chỉnh được
thực hiện bởi việc lặp đi lặp lại một số lượng lớn bước thực hiện các hành động,
Nguyễn Anh Cường  4/15
gọi là iteration. Một luật chọn hành động là tối ưu nếu và chỉ nếu giá trị của hàm
giá trị ứng với luật chọn hành động đó luôn lớn hơn hoặc bằng hàm giá trị của các
luật chọn hành động khác. Gọi V* và Q* là các hàm giá trị tối ưu ta có thể xác
định các hàm này bằng cách sau:
*( ) max ( )V s V s
π
π
=
*( , ) max ( , )Q s a Q s a
π
π
=
Có nghĩa là giá trị các hàm V* và Q* chính là giá trị của các hàm V và Q
ứng với luật chọn hành động tối ưu (cho ra giá trị V(s) hay Q(s, a) lớn nhất tại mỗi
vị trí s) [2].

Ở đây ta đưa ra một cách hình thức việc biểu diễn các đối tượng. Giả sử đối
tượng ảnh X được biểu diễn bởi n thành phần (n đặc trưng): X = {x1, x2, , xn},
mỗi xi biểu diễn một đặc tính. Không gian biểu diễn đối tượng thường gọi tắt là
không gian đối tượng X được định nghĩa:
X = {X1, X2, , Xm}
trong đó mỗi Xi biểu diễn một đối tượng.
Không gian này có thể là vô hạn.
Để tiện xem xét chúng ta chỉ xét tập X là hữu hạn.
+ Không gian diễn dịch
Không gian diễn dịch là tập các tên gọi của đối tượng. Kết thúc quá trình
nhận dạng ta xác định được tên gọi cho các đối tượng trong tập không gian đối
tượng hay nói là đã nhận dạng được đối tượng. Một cách hình thức gọi (là tập tên
đối tượng:

Ω
= {w
1
, w
2
, ,w
k
} với w
i
, i = 1, 2, , k là tên các đối tượng
Quá trình nhận dạng đối tượng f là một ánh xạ f: X >
Ω
với f là tập các
quy luật để định một phần tử trong X ứng với một phần tử trong
Ω
. Nếu tập các

N
=
∑
y
i
là toạ độ tâm điểm. Như vậy, moment trung tâm bậc p, q của đường bao là:
µ
pq
=
1
1
N
i
N
=
∑
(x
i
-x
0
)
p
(y
i
-y
0
)
q
Véctơ tham số trong trường hợp này chính là các moment µ
ij

S là dạng (ký hiệu bắt đầu).
3. Bản chất của quá trình nhận dạng
Quá trình nhận dạng gồm 3 giai đoạn chính:
- Lựa chọn mô hình biểu diễn đối tượng.
- Lựa chọn luật ra quyết định (phương pháp nhận dạng) và suy diễn quá trình học.
- Học nhận dạng.
Khi mô hình biểu diễn đối tượng đã được xác định, có thể là định lượng (mô
hình tham số) hay định tính (mô hình cấu trúc), quá trình nhận dạng chuyển sang
giai đoạn học. Học là giai đoạn rất quan trọng. Thao tác học nhằm cải thiện, điều
chỉnh việc phân hoạch tập đối tượng thành các lớp. Quá trình này có hai dạng, đó là
học có thầy và học không có thầy. Học có thầy là phương pháp nhận dạng dựa trên
các kiến thức biết trước để thực hiện thành công các thao tác phân biệt và phân
hoạch ảnh. Đặc điểm mấu chốt của kỹ thuật này là sử dụng một thư viện chứa đựng
các mẫu chuẩn có sẵn. Đối tượng ảnh cần nhận dạng được đối sánh với mẫu chuẩn
để xem nó thuộc loại nào. Khi đó công việc chủ yếu là thiết kế một hệ thống để có
thể đối sánh đối tượng ảnh với mẫu chuẩn và ra quyết định gán chúng vào một lớp
nhãn tương ứng.Việc nhận dạng chính là tìm ra quy luật và các thuật toán để có thể
gán đối tượng vào một lớp hay nói một cách khác gán cho đối tượng một tên.
Học không có thầy là kỹ thuật nhận dạng phải tự định ra các lớp khác nhau
và phải xác định các tham số đặc trưng cho từng lớp. Theo phương pháp học này
thì số lớp và các đặc trưng của từng lớp không được biết trước nên công việc đối
sánh ảnh phải tiến hành bằng mọi cách nhằm gộp nhóm có thể và chọn lựa cách
phân tích và phân đoạn tốt nhất và nâng cấp dần để đạt được một phương án xử lý
nhận dạng hiệu quả.
Nhìn chung, dù là mô hình nào và kỹ thuật nhận dạng ra sao, một hệ thống
nhận dạng có thể tóm tắt theo sơ đồ sau:
Nguyễn Anh Cường  7/15
Hình 2. Sơ đồ tổng quát một hệ nhận dạng
4. Các phương pháp thống kê trong nhận dạng ảnh
a. Phương pháp thống kê dựa vào lý thuyết Bayes

}
- Không gian diễn dịch: Ω={C
1
, C
2
, C
r
} với C
i
là lớp phân bố tế bào ảnh thứ
i (i=1 r).
Quy tắc nhận dạng ảnh theo xác suất có điều kiện của Bayes được phát biểu:
Nếu ε là sai số của phép ánh xạ F từ X tới Ω sao cho X∈C
k
khi và chỉ khi
P(C
k
/X)>P(C
i
/X) ∀i≠k và i=1 r. Trong thực tế, luôn luôn tồn tại sai số ε khi phân
tích và phân đoạn nhận dạng ảnh. Do đó vấn đề tối ưu dữ liệu ảnh ở bước này là
phải xây dựng quy tắc nhận dạng với sai số ε là nhỏ nhất.
b. Phương pháp thống kê xác suất sử dụng logic mờ
+ Tập mờ và hàm phụ thuộc: Cho tập hợp X và A là tập con của X khi đó ta
có thể xây dựng một hàm xác định các phần tử của tập A như sau:
Xét µ: X → {0,1 }; với x ∈ X
trong đó: µ(x)=1 nếu x∈ A; µ(x)=0 nếu x∉ A
Nguyễn Anh Cường  8/15
Khối nhận dạng
Khối tiền xử lý

pháp theo chiều ngang (Gọi H
1
là số điểm cắt ngang của dòng thứ i. Như vậy
H
1
,H
2
, ,H
w
sẽ là dãy các điểm cắt ngang) hay thẳng đứng (Tương tự, gọi Wi là số
điểm cắt dọc của dòng thứ i. Như vậy W
1
, W
2
, ,W
h
sẽ là các điểm cắt dọc.
Khi đó quy tắc nhận dạng ở đây là:
Hx’
⊆
Hx hoặc Hx
⊆
Hx’; X được xem là X’ nếu Vx’
⊆
Vx hoặc Vx
⊆
Vx’).
Tuy nhiên ở đây ta có H
1
= β (ξ*i), V1 = β (ξ*i). Tiếp đó, nếu trong chuỗi H

=
1
)(
),1(
),1(
α
α
3. BÀI TOÁN NHẬN DẠNG THỐNG KÊ ĐỐI TƯỢNG TRÊN ẢNH
1. Phát biểu bài toán
Bài toán: Các phương pháp thống kê trong nhận dạng đối tượng trên ảnh.
2. Hướng giải quyết (ý tưởng và cách giải)
Với đề bài đã cho, ở đây sử dụng phương pháp thống kê xác suất kết hợp
logic mờ để nhận dạng ký tự (ký tự ở đây là chữ viết, chữ số là ảnh được soạn thảo
trên máy tính, hoặc là ký tự ta quét trực tiếp trên máy tính).
Nội dung cụ thể như sau:
a) Xác định dữ liệu cho từng ký tự
Với mục tiêu ban đầu là nhận dạng ký tự của một số loại phông chữ có sẵn
(kích thước có thể tùy ý), vì vậy việc xác định xác xuất điểm ảnh ở một vị trí nào
đó là rất quan trọng. Với nhận xét trên thì với bất kỳ một ký tự có kích cỡ như thế
nào cũng có thể được xử lý để đưa về một mẫu có kích thước cố định để từ đó ta có
thể tính toán xác xuất của một điểm ảnh xuất hiện trong một tập các ảnh mẫu nào
đó. Ở đây ta có thể phân ra làm 3 lớp đặc trưng cho một ký tự.
- Lớp thứ nhất lấy xác xuất theo vị trí của điểm ảnh.
- Lớp thứ 2 lấy xác xuất theo chiều dọc
- Lớp thứ 3 lấy xác xuất theo chiều ngang.
Để làm được điều này thì dữ liệu ban đầu phải qua một bước tiền xử lý.
Ở bước tiền xử lý thực hiện đóng khung (đóng bao) theo kích thước điểm
ảnh thực tế thể hiện của ký tự, sau đó tính toán theo tỷ lệ để đưa về kích thước xác
định từ trước.
Đối với ảnh ký tự 2 chiều có thể quy giá trị các điểm ảnh của ký tự có kích

ak
∑
=
=
1
)(
)1,(
)1,(
β
β
M
yxyx
d
nm
yx
ak
k
∑
==
−
=
,
1,1
11
1
|),(),(|
µµ
nxn
d
n

b) Nhận dạng ký tự
Để nhận dạng một ký tự trước hết ta cũng phải thực hiện bước tiền xử lý dữ
liệu của ký tự cần nhận dạng để đưa về một kích thước xác định theo dữ liệu tri
thức mà ta đang lưu trữ (dữ liệu của các ký tự ta đã cho máy tính học). Sau đó, với
mỗi lớp ta có thể tính toán thông qua độ lệch (khoảng cách) của ký tự cần nhận
dạng so với dữ liệu của ký tự mẫu.
+ Với lớp 1, gọi d
1k
là độ lệch, µ
1k
là hàm phụ thuộc của dữ liệu ký tự k so
với ký tự cần nhận dạng. Khi đó µ
1k
được tính theo công thức:
µ
1k
= 1- d
1k
Để xác định độ lệch d ta có thể dựa vào một nhận xét sau: Giả sử ma trận
lưu trữ dữ liệu tri thức có kích thước mxn. Tại các vị trí (x,y) mà ở đó có µ
1ak
(x,y)
≥ delta hoặc µ
1
(x,y) =1, giá trị của dữ liệu mẫu của ký tự k là µ
1ak
(x,y), và giá trị
của ký tự cần nhận dạng là µ
1
(x,y). Khi đó độ lệch giá trị tại vị trí (x,y) là

m
x
x
xak
k
∑
=
−
=
1
)1,
()1,(
3
||
ββ
+ Với lớp 3, µ
3k
và d
3k
lần lượt được tính theo công thức:
µ
3k
=1 - d
3k
Như vậy sau khi tính toán toàn bộ µ
1k
, µ
2k
, µ
3k

kmax
lớn hơn hay bằng Beta (
β
) thì k chính là ký
tự nhận dạng được, còn nếu µ
kmax
< Beta thì ký tự đó coi như không nhận dạng
được trong dữ liệu mẫu mà ta đã học được.
c) Học tăng cường
Khi dữ liệu mẫu của có thể bổ sung được hoặc nhận dạng sai một ký tự, ta
cũng có thể thực hiện học bổ sung, tăng cường nhằm hiệu chỉnh lại bảng dữ liệu tri
thức. Vấn đề đặt ra là, nếu như một mẫu được nhân bản nhiều lần thì coi như việc
học đó sẽ chú trọng theo mẫu đó là chính. Việc cập nhật lại bảng dữ liệu tri thức
như vậy hệ số sẽ phân bố theo xu hướng những dữ liệu nào là phổ biến hơn là
những dữ liệu ít được cập nhật. Việc tăng cường học đi học lại một vài dữ liệu
quen thuộc sẽ dẫn đến những dữ liệu có sự phổ biến thấp sẽ ảnh hưởng đến kết quả
nhận dạng ít hơn.
Mỗi bộ dữ liệu theo từng cá nhân sẽ cần được học riêng và cho phép nhận
dạng riêng cho cá nhân đó. Khi chuyển đổi dạng dữ liệu là phần chữ viết khác,
thay vì học tăng cường, ta nên lưu sang một CSDL tri thức mới, điều này sẽ tránh
được sự hỗn độn và lai tạp nhiều kiểu dữ liệu tránh được sự nhầm lẫn đáng tiếc.
d) Ví dụ mẫu trong chương trình minh họa.
Bộ mẫu và bộ test lấy từ học viên Lê Anh (vẽ tay) để nhận dạng
Nguyễn Anh Cường  12/15
Có thể nạp nhiều lần để học.
Khi nhận dạng cần học bổ sung (tăng cường) thêm một số mẫu nhận sai, chọn mẫu rồi
chọn “học lại ảnh này”. Nếu có nhiều ảnh nhận dạng sai, có thể cho nó vào 1 thư mục rồi
quay trở lại Quá trình học để học lại.
Nguyễn Anh Cường  13/15
4. Kết luận

[ 9 ] Richard O. Duda, Peter E. Hart, David G. Stork (2001) Pattern classification
(2nd edition), Wiley, New York
[ 10 ] Dietrich Paulus and Joachim Hornegger (1998) Applied Pattern
Recognition (2nd edition), Vieweg
[ 11 ] J. Schuermann: Pattern Classification: A Unified View of Statistical and
Neural Approaches, Wiley&Sons, 1996
[ 12 ] Sholom Weiss and Casimir Kulikowski (1991) Computer Systems That
Learn, Morgan Kaufmann
Nguyễn Anh Cường  15/15