ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NG
I
C
I
N
N
NG N
N ẠNG
ẠN C
LU N VĂN T ẠC SĨ
Hà Nội - 2011
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
H
I
C
NG N
N ẠNG
ẠN C
I
gành: Công nghệ thông tin
Chuyên ngành: Công nghệ phần mềm
Mã số: 60 48 10
LUẬ VĂ THẠC SĨ
NGƯỜI HƯỚNG ẪN K
ỌC: PGS.TS Ngô Quốc ạo
Hà Nội – 2011
3
MỤC LỤC
LỜI CAM ĐOAN ....................................................................................................................... 1
LỜI CẢM ƠN............................................................................................................................. 2
DANH MỤC CÁC KỲ HIỆU, CÁC CHỮ VIẾT TẮT ............................................................. 4
DANH MỤC CÁC HÌNH VẼ .................................................................................................... 5
MỞ ĐẦU.................................................................................................................................... 6
Chương 1 .................................................................................................................................... 7
GIỚI THIỆU CHUNG VỀ NHẬN DẠNG CHỮ VIẾT ............................................................ 7
1.1. Trình bày về lịch sử của nhận dạng chữ viết tay ........................................................ 7
1.2. Giới thiệu các hướng tiếp cận trong việc nhận dạng chữ viết tay ............................. 7
1.2.1. Nhận dạng chữ in ..................................................................................................... 7
1.2.2. Nhận dạng chữ viết tay ............................................................................................. 8
Chương 2 – GIỚI THIỆU VỀ SVM ......................................................................................... 10
2.1. Giới thiệu chung .......................................................................................................... 10
2.2. Chiều VC (Vapnik Chervonenkis dimension) .......................................................... 11
2.3. Hàm phân lớp .............................................................................................................. 12
2.4. Siêu phẳng phân cách .................................................................................................. 12
2.5. Support vector ............................................................................................................. 16
2.6. SVM với dữ liệu không nhiễu ..................................................................................... 18
2.7. SVM với dữ liệu có nhiễu ............................................................................................ 20
2.8. Biên độ (Margin).......................................................................................................... 21
2.9. Phân lớp dữ liệu tuyến tính và không tuyến tính ..................................................... 21
2.9.1. Trường hợp dữ liệu có thể phân chia tuyến tính được. .......................................... 21
2.9.1. Trường hợp dữ liệu không thể phân chia tuyến tính được. .................................... 22
Chương 3 .................................................................................................................................. 24
SỰ CẦN THIẾT CỦA SVM NHẬN DẠNG CHỮ VIẾT TAY .............................................. 24
3.1. Học máy có giám sát .................................................................................................... 24
3.2. Phân lớp dữ liệu ........................................................................................................... 24
3.3. Nhận xét ........................................................................................................................ 27
3.4. Bài toán cho mô hình SVM ......................................................................................... 27
3.5. Xây dựng mô hình học cho SVM ............................................................................... 30
3.5.1. Nguyên lý chung để chia nhỏ bài toán. .................................................................. 31
3.5.2. Chọn tập con để huấn luyện. .................................................................................. 31
3.5.3. Thu hẹp điều kiện tối ưu. ........................................................................................ 31
Chương 4 – CHƯƠNG TRÌNH THỬ NGHIỆM ..................................................................... 33
4.1. Giới thiệu về hệ nhận dạng dùng LIBSVM............................................................... 33
4.1.1. Các chức năng chính của hệ nhận dạng................................................................. 34
4.1.2. Dữ liệu hệ thống ..................................................................................................... 34
4.2. Sử dụng libsvm-3.1 ...................................................................................................... 35
4.3. Kết quả chạy thử nghiệm trên tập dữ liệu libsvm .................................................... 38
4.3.1. Kết quả thực nghiệm được tiến hành trên tập dữ liệu MNIST ............................... 39
4.3.2. Kết quả thực nghiệm được tiến hành trên tập dữ liệu SATIMAGE.SCALE ........... 40
4.3.3. Kết quả thực nghiệm được tiến hành trên tập dữ liệu DNA.SCALE ...................... 41
4.3.4. Kết quả thực nghiệm được tiến hành trên tập dữ liệu LETTER.SCALE ................ 42
4.3.5. Kết quả thực nghiệm được tiến hành trên tập dữ liệu USPS.SCALE ..................... 43
Chương 5 .................................................................................................................................. 44
ỨNG DỤNG SVM VÀO NHẬN DẠNG CHỮ VIẾT TAY ................................................... 44
5.1. Tiền xử lý ...................................................................................................................... 44
5.2. Xây dựng các máy phân lớp SVM ............................................................................. 45
KẾT LUẬN .............................................................................................................................. 49
TÀI LIỆU THAM KHẢO ........................................................................................................ 50
4
DANH MỤC CÁC KỲ HIỆU, CÁC CHỮ VIẾT TẮT
Thuật ngữ,chữ viết tắt
KKT
MMH
SVM
Giải thích
Karush Kuhn Tucker
Maximum Marginal Hyperplane
Siêu phẳng có biên độ lớn nhất
Support Vector Machine
Máy véc tơ hỗ trợ
5
DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Các giai đoạn trong quá trình xử lý và nhận dạng ảnh ......................... 9
Hình 2-2: Đường phân chia đối với tập dữ liệu gồm hai thuộc tính ................... 13
Hình 2-3: Một bộ dữ liệu hai chiều được phân chia tuyến tính. ......................... 14
Hình 2-4: Hai siêu phẳng phân chia tuyến tính cùng với biên độ của nó. .......... 15
Hình 2-5: Đường biểu diễn H1 và H2 ................................................................. 17
Hình 2-6: Các support vector trong SVM. .......................................................... 18
Hình 2-7: Một trường hợp đơn giản trên không gian 2 chiều. ............................ 23
Hình 3-1: Bước 1 - Học để xây dựng mô hình phân lớp .................................... 25
Hình 3-2: Bước 2 - Kiểm tra và đánh giá ............................................................ 26
Hình 4.1: Các bước cơ bản của quá trình nhận dạng chữ bằng mô hình SVM .. 34
Hình 5.2: Chuẩn hóa ảnh. .................................................................................... 44
Hình 5-3: Chuẩn hóa các vùng liên thông........................................................... 45
Hình 5.4: Quá trình trích chọn đặc trưng ............................................................ 46
6
MỞ ĐẦU
Cho đến nay mặc dù khoa học công nghệ không ngừng phát triển để
đáp ứng ngày càng cao những nhu cầu của con người nhưng không phải
nhu cầu nào cũng có thể dễ dàng giải quyết và đáp ứng được. Nhận dạng
chữ viết tay hiện nay vẫn đang 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ó phụ thuộc
quá nhiều vào người viết với sự biến đổi quá đa dạng trong cách viết và
trạng thái tinh thần của từng người viết. Nhưng trong nhiều năm qua, bài
toán nhận dạng chữ viết tay cũng đã có một số kết quả khả quan, chủ yếu
tập trung trên các tập dữ liệu chữ số viết tay như MNIST [6], một số kết
quả khác mở rộng đối với các chữ cái hệ La tinh, Hy lạp… Đặc biệt đối với
việc nhận dạng chữ viết tay tiếng Việt lại càng khó khăn hơn do bộ ký tự
tiếng Việt có nhiều chữ có hình dáng rất giống nhau, chỉ khác chút ít về
phần dấu. Do đó có rất ít kết quả nghiên cứu về nhận dạng chữ viết tay
tiếng Việt và các nghiên cứu chủ yếu cũng chỉ tập trung vào chữ viết tay
online.
Nhận dạng chữ viết tay là một đề tài rất quan trọng trong nhiều ứng
dụng khác nhau, trong lĩnh vực máy tính nó giúp cho máy tính có thể đọc
được và hỗ trợ nhập liệu. Các nghiên cứu về nhận dạng chữ viết tay đã
được phát triển từ hơn nửa thập kỷ qua và đạt được nhiều thành quả thiết
thực nhưng độ chính xác phụ thuộc quá nhiều vào ngôn ngữ và sự thay đổi
trong cách viết. Cho đến nay, bài toán nhận dạng chữ viết tay cũng đã có
một số nghiên cứu khả quan, nhưng chưa có ứng dụng thực tiễn. Bài toán
chúng tôi đặt ra ở đây là xây dựng một mô hình nhận dạng chữ viết tay hạn
chế.
Luận văn được bố cục thành 5 chương. Chương 1 giới thiệu về nhận
dạng chữ viết tay. Chương 2 giới thiệu về SVM. Chương 3 sự cần thiết của
SVM vào việc nhận dạng chữ viết tay. Chương 4 bộ phân loại SVM.
Chương 5 ứng dụng của SVM vào nhận dạng chữ viết tay.
7
Chương 1
GIỚI THIỆU CHUNG VỀ NHẬN DẠNG CHỮ VIẾT
Chương 1 tập trung tìm hiểu về lịch sử và các hướng nghiên cứu của
nhận dạng chữ viết. Nội dung của chương được bố cục thành hai mục. Mục
một trình bày về lịch sử của nhận dạng chữ viết. Mục hai giới thiệu các
hướng tiếp cận trong việc nhận dạng chữ viết tay.
1.1. Trình bày về lịch sử của nhận dạng chữ viết tay
Ngày nay khoa học công nghệ phát triển mạnh cũng không ngoài
mục đích khác là để đáp ứng nhu cầu ngày càng cao của con người. Mỗi
quốc gia đều phải có ít nhất một ngôn ngữ, chữ viết để giao tiếp, từ năm
1922 khái niệm nhận dạng chữ đã được hình thành cho đến năm 1950, 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 [5]. 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.
Năm 1954, máy nhận dạng chữ đầu tiên đã được phát triển bởi J.Rainbow
dùng để đọc chữ in hoa nhưng rất chậm. Năm 1967, Công ty IBM đã
thương mại hóa hệ thống nhận dạng chữ. Từ năm 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 đã
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ữ [3]. Từ 1990 đến nay, 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 nơ
ron, mô hình Markov ẩn và SVM (Support Vector Machines)…
1.2. Giới thiệu các hướng tiếp cận trong việc nhận dạng chữ viết tay
1.2.1. Nhận dạng chữ in
Phục vụ cho công việc tự động hóa đọc tài liệu, tăng tốc độ và chất
lượng nhập thông tin vào máy tính trực tiếp từ các nguồn tài liệu. Vấn đề
này đã được giải quyết gần như trọn vẹn (sản phẩm FineReader 9.0 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
Hà Nội 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%).
8
1.2.2. Nhận dạng chữ viết tay
Với những mức độ ràng buộc khác nhau về cách viết, kiểu chữ…
phục vụ cho các ứng dụng đọc và xử lý các chứng từ, hóa đơn, phiếu ghi,
văn bản viết tay… Nhận dạng chữ viết tay được tách ra hai hướng phát
triển: nhận dạng chữ viết tay trực tuyến (online) và chữ viết tay ngoại tuyến
(offline). Trong đó nhận dạng chữ viết tay trực tuyến là khi viết lên màn
hình thì máy tính sẽ chuyển những hình ảnh viết tay thành dạng text. Khác
với chữ offline, chữ online có thêm thông tin về thứ tự các điểm, các nét
được viết. Hiện nay việc nhận dạng chữ viết tay tiếng Anh online hầu như
đã giải quyết xong và đã được tích hợp vào máy tính cầm tay thậm chí là
máy để bàn và điện thoại di động. Nhưng đối với tiếng Việt thì chưa có
một phần mềm nào tương tự. Còn trong nhận dạng chữ viết tay offline
chúng ta nghiên cứu về nhận dạng chữ viết tay tự nhiên và nhận dạng chữ
viết tay hạn chế. Nhận dạng chữ viết tay tự nhiên là dùng để xử lý các văn
bản viết tay thông thường, công việc này cực kỳ khó khăn nếu không nói là
không thể. Vì có người viết xấu người khác cũng không đọc được thì máy
làm sao “đọc” được??? Nhận dạng chữ viết tay hạn chế là nhận dạng các
chữ cái, chữ số được viết tay rõ ràng, rời nhau, hoặc nhận dạng các form
điều tra xã hội, có các thông tin về chữ số, tên người, địa chỉ, điện thoại…
Những người được điều tra sẽ điền các thông tin bằng chữ viết tay vào
form. Để nhập thông tin hàng trăm nghìn các phiếu điều tra vào máy tính sẽ
mất rất nhiều thời gian khi làm thủ công bằng tay. Nếu ta dùng một chương
trình để nhận dạng các chữ viết tay trên các phiếu điều tra đó thì công việc
sẽ đơn giản hơn. Các chữ trong phiếu điều tra thường là các chữ viết tay
hạn chế: viết rõ ràng, rời nhau, hoặc không dính liền nhau nhiều, thậm chí
là viết hoa. Hiện nay, phần mềm MarkRead cũng đã có tích hợp đặc trưng
nhận dạng chữ viết tay hạn chế, nhưng kết quả mới chỉ dừng lại ở phòng thí
nghiệm. 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.
Trong bản luận văn này sẽ tìm hiểu về nhận dạng chữ Việt viết tay
hạn chế sử dụng mô hình SVM. Mục tiêu chính của luận văn là nghiên cứu
cách xây dựng một hệ thống nhận dạng mà đầu vào là ảnh cần nhận dạng
sau quá trình nhận dạng đưa đầu ra là dữ liệu dạng text của những ký tự
được viết tay. Việc xây dựng hệ thống có thể được mô tả trực quan bằng sơ
đồ hình 1.1. Trong hệ thống này phần chúng ta cần tập trung quan tâm nhất
9
là phần hệ huấn luyện và nhận dạng. Chúng ta sẽ sử dụng mô hình SVM
trong việc huấn luyện và nhận dạng đó.
Lưu trữ
SCANNER
Thu nhận ảnh
Số hóa
Phân tích ảnh
Nhận dạng
Hệ huấn
luyện
Hình 1.1. Các giai đoạn trong quá trình xử lý và nhận dạng ảnh
Vì vậy muốn xây dựng được hệ thống có khả thi thì chúng ta cần
phải tìm hiểu về SVM nói chung và ứng dụng của SVM nói riêng trong
việc nhận dạng chữ viết.
10
Chương 2 – GIỚI THIỆU VỀ SVM
2.1. Giới thiệu chung
Trong vài năm qua đã có sự phát triển rất quan trọng trong sự hiểu
biết lý thuyết về Máy véc tơ hỗ trợ (SVM) cũng như chiến lược thuật toán
để thực hiện chúng, và các ứng dụng của phương pháp này để tiếp cận vấn
đề thực tế. SVM là một họ các phương pháp dựa trên cơ sở hàm nhân
(kernel) để tối thiểu hóa rủi ro ước lượng. Các thử nghiệm thực tế cho thấy,
SVM là một trong những phương pháp phân lớp có độ chính xác rất cao và
nó cũng được áp dụng nhiều trong các bài toán nhận dạng chữ viết tay.
Phương pháp SVM ra đời (1992) từ lý thuyết học thống kê do Vapnik và
Chervonenkis xây dựng (1960). SVM có thể được xem như là trường hợp
riêng của học máy (SVM là một phương pháp học máy có giám sát giải
quyết được bài toán phân lớp), SVM là một phương pháp trong việc phân
loại dữ liệu tuyến tính và không tuyến tính [8]. Có nhiều phương pháp phân
lớp dữ liệu như: phân lớp dựa vào cây quyết định, phân lớp dựa vào luật,
phân lớp Bayesian, phân lớp theo lan truyền ngược, phân lớp K láng giềng
gần nhất… Tuy nhiên trong lĩnh vực của luận văn thì SVM là phương pháp
phân lớp được chọn để sử dụng. SVM có nhiều tiềm năng cả trong lý
thuyết và trong thực tiễn đặc biệt là trong lĩnh vực nhận dạng, phân loại và
khai phá dữ liệu.
Trình bày giới thiệu toàn diện SVM nói chung và ứng dụng của
phương pháp phân lớp SVM trong việc nhận dạng nói riêng đòi hỏi sự tổng
hợp của một phạm vi rộng kiến thức, bao gồm không gian đặc trưng
(feature spaces), lý thuyết học (learning theory), lý thuyết tối ưu hóa
(optimisation theory), và một số thuật toán (algorithmics). Hoạt động
nghiên cứu về SVM vẫn đang được theo đuổi trong tất cả các lĩnh vực này
để tạo thành cơ sở cho khái niệm SVM [8].
Đặc trưng cơ bản quyết định khả năng phân loại của một bộ phân
lớp là hiệu suất tổng quát hóa, hay là khả năng phân loại những dữ liệu mới
dựa vào những tri thức đã tích lũy được trong quá trình huấn luyện. Thuật
toán huấn luyện được đánh giá là tốt nếu sau quá trình huấn luyện, hiệu
suất tổng quát hóa phụ thuộc vào hai tham số là sai số huấn luyện và năng
lực của máy học. Trong đó sai số huấn luyện là tỷ lệ lỗi phân loại trên tập
dữ liệu huấn luyện. Còn năng lực của máy học được xác định bằng kích
thước Vapnik-Chervonenkis (kích thước VC). Kích thước VC là một khái
niệm quan trọng đối với một họ hàm phân tách (hay là bộ phân lớp). Đại
11
lượng này được xác định bằng số điểm cực đại mà họ hàm có thể phân tách
hoàn toàn trong không gian đối tượng. Một bộ phân loại tốt là bộ phân loại
đơn giản nhất và đảm bảo sai số huấn luyện nhỏ [8].
2.2. Chiều VC (Vapnik Chervonenkis dimension)
Xét các hàm f (x): R{+1,-1}, có 2l cách để gán nhãn cho l điểm.
Nếu với mỗi một cách gán nhãn ta đều có thể tìm thấy một thành phần của
tập hợp {f(x)} mà nhận dạng chính xác cách gán nhãn này. Khi đó tập hợp
của l điểm được nói là bị phá vỡ bởi tập hợp các hàm {f(x)}. Chiều VC của
{f(x)} là số lớn nhất của các điểm dữ liệu mà có thể bị phá vỡ bởi nó. Chiều
VC của các siêu phẳng trong không gian Rn thường là n+1. VC của các
đường thẳng có hướng trong không gian 2 chiều (R2) là 3 [9].
Giả sử tập không gian giả thiết là tập các siêu phẳng có dạng f s(x)=
w.x+b. Nếu tất cả các véc tơ mẫu xi được bao trong hình cầu có bán kính R,
và thỏa |wxi+b|1.
Đặt ║x║=A, khi đó chiều VC h của tập các siêu phẳng {fs} được
giới hạn bởi:
h ≤min([R2 A2], n)+1
12
2.3. Hàm phân lớp
SVM là một phương pháp trong việc phân lớp dữ liệu tuyến tính và
không tuyến tính. Khoảng từ những năm 1990, các thuật toán phân lớp có
độ chính xác cao, tốc độ học và bảo đảm toán học mạnh nhất chính là các
thuật toán sử dụng hàm phân lớp tuyến tính. Hàm phân lớp tuyến tính có
ranh giới phân lớp là một siêu phẳng, vì vậy nó chỉ phân tách được hai lớp.
Tất nhiên, ta có thể kết hợp nhiều hàm phân lớp lại để tách được nhiều lớp
hơn. Xét hàm tuyến tính phân tách Rn thành hai nửa không gian, ta
gán 1 1, 2 1 , luật phân lớp khi sử dụng hàm phân lớp tuyến tính
là:
f ( x) ((, x) b)
1
1
(t )
t0
t0
Trong đó, f (x) là hàm phân lớp, (x) là hàm ngưỡng, , x là tích vô
hướng của , x , là trọng số trên các tọa độ đặc trưng của x , b là
ngưỡng.
Hình 2-1: Phân lớp bằng siêu phẳng
Như vậy, nửa không gian R x | , x b được phân vào lớp
1 1 , nửa không gian còn lại R x | , x b được phân vào lớp
1 1 .
2.4. Siêu phẳng phân cách
Cho trước tập dữ liệu D gồm (X1, y1), (X2, y2), ..., (X|D|, y|D|).
13
Trong đó Xi là một tập các bộ huấn luyện tương ứng với nhãn lớp yi. Mỗi yi
sẽ nhận một trong hai giá trị hoặc là +1 hoặc là -1 (yi {+1, -1}).
Phương pháp phân lớp SVM sẽ tìm ra đường phân lớp “tốt nhất” để phân
chia tập dữ liệu này thành từng lớp tách biệt ra với nhau. Phương trình tổng
quát của một đường phân chia như vậy được biểu diễn dưới dạng sau:
.x b 0
Trong đó:
- w: Vector trọng số, w = {w1, w2,…,wn).
- x: Số thuộc tính (hay còn gọi là số chiều của dữ liệu).
- b: Một đại lượng vô hướng, thường được xem như là một độ nghiêng .
Đối với trường hợp dữ liệu hai chiều (hai thuộc tính) thì phương
trình trên biểu diễn của đường thẳng phân chia. Nếu dữ liệu của chúng ta là
ba chiều thì đường phân chia giữa hai tập sẽ là một mặt phẳng phân cách.
Tổng quát cho dữ liệu n chiều thì sẽ được phân cách bởi một siêu phẳng.
Chúng ta sẽ sử dụng thuật ngữ “siêu phẳng” (hyperplane) để chỉ đến ranh
giới quyết định mà chúng ta muốn tìm kiếm bất chấp số lượng thuộc tính.
Hình 2-2: Đường phân chia đối với tập dữ liệu gồm hai thuộc tính
14
Tuy nhiên trong thực tế ta có thể tìm được vô số những siêu phẳng
phân chia trên cùng một tập dữ liệu. Và chúng ta muốn tìm đường thẳng
phân chia sao cho tốt nhất, có nghĩa là có sai sót phân loại bé nhất trên bộ
dữ liệu.
Hình 2-3: Một bộ dữ liệu hai chiều được phân chia tuyến tính. Có vô hạn
đường thẳng phân chia tuyến tính có thể . Vậy cái nào là tốt nhất?
Do đó mục tiêu của phương pháp phân lớp SVM là tìm một siêu
phẳng phân cách giữa hai lớp sao cho khoảng cách lề (margin) giữa hai lớp
đạt cực đại.
Siêu phẳng có biên độ lớn nhất (maximum marginal hyperplane) sẽ
được chọn như là siêu phẳng phân chia tập dữ liệu một cách tốt nhất. Trong
hình bên dưới, ta thấy có hai siêu phẳng có thể phân chia được và những
biên độ của nó. Trước khi đi vào định nghĩa của biên độ (margin), hãy nhìn
vào hình trên một cách trực quan. Cả hai siêu phẳng đều phân tách tất cả
những bộ dữ liệu cho trước. Một cách trực quan, siêu phẳng với biên độ lớn
hơn sẽ chính xác hơn trong việc phân loại các bộ dữ liệu trong tương lai so
với siêu phẳng có biên độ nhỏ hơn. Điều này là lý do tại sao (trong suốt
giai đoạn học hay huấn luyện), SVM tìm những siêu phẳng có biên độ lớn
nhất, gọi là MMH (maximum marginal hyperlane). Siêu phẳng có biên độ
lớn nhất là siêu phẳng có khoảng cách từ nó tới hai mặt bên của nó thì bằng
15
nhau (mặt bên song song với siêu phẳng). Khoảng cách đó thật ra là
khoảng cách ngắn nhất từ MMH tới bộ dữ liệu huấn luyện gần nhất của
mỗi lớp. Siêu phẳng có biên độ lớn nhất này cho chúng ta một sự phân loại
tốt nhất giữa các lớp.
Hình 2-4: Hai siêu phẳng phân chia tuyến tính cùng với biên độ của nó. Cái
nào tốt hơn? Cái có biên độ lớn hơn thì sẽ có độ chính xác cao hơn.
Siêu phẳng phân cách có vai trò quan trọng trong việc phân lớp, nó
quyết định xem một bộ dữ liệu sẽ thuộc về lớp nào. Để thực hiện việc phân
lớp, SVM chỉ cần xác định xem một bộ dữ liệu nằm về phía nào của siêu
phẳng phân cách
Dx sign.x b
16
Với:
- D(x) < 0: bộ dữ liệu sẽ nằm phía dưới siêu phẳng phân cách
- D(x) = 0: bộ dữ liệu sẽ nằm trên siêu phẳng phân cách
- D(x) > 0: bộ dữ liệu sẽ nằm phía trên siêu phẳng phân cách
2.5. Support vector
Ta có phương trình tổng quát của siêu phẳng
.x b 0
Ta xét trên ví dụ sau:
Với bộ dữ liệu huấn luyện có hai thuộc tính A1 và A2: X={x1, x2}, với x1, x2
là giá trị của thuộc tính A1, A2. W = {w1, w2}. Phương trình siêu phẳng có
thể viết lại:
0 1 x1 2 x2 0
Trong đó:
- w0 tương đương với hằng số b trong phương trình tổng quát của siêu
phẳng
Vì vậy mỗi điểm nằm trên siêu phẳng phân cách thỏa mãn:
0 1 x1 2 x2 0
Tương tự, những điểm nằm dưới siêu phẳng phân cách phải thỏa mãn:
0 1 x1 2 x2 0
Bằng cách điều chỉnh trọng số w0 ta có:
H1 : 0 1 x1 2 x2 1,
H 2 : 0 1 x1 2 x2 1,
yi 1
yi 1
17
Hình 2-5: Đường biểu diễn H1 và H2, đường màu đỏ là khoảng cách Euclidean
của hai điểm 1 và 2. Đường màu xanh là khoảng cách Euclidean nhỏ nhất
Điều này có nghĩa là nếu bất kì bộ nào nằm tại hoặc trên H1 đều thuộc về
lớp +1, và bất kì bộ nào nằm tại hoặc dưới H2 đều thuộc về lớp -1.Kết hợp
2 bất đẳng thức trên ta có:
yi 0 12 22 1, i
Mỗi bộ huấn luyện nằm tại các mặt biên H1 hay H2 thỏa mãn phương trình
trên được gọi là support vectors. Support vectors là những bộ gần với siêu
phẳng phân chia tuyến tính (MMH) nhất.
Trong hình bên dưới, support vectors là hình tròn có viền dày hơn.
Ta thấy rằng các support vectors là những bộ khó phân lớp nhất và cung
cấp nhiều thông tin nhất cho việc phân lớp.
18
Hình 2-6: Các support vector trong SVM. Các support vector là những hình có
viền dày hơn
2.6. SVM với dữ liệu không nhiễu
Xét tập dữ liệu huấn luyện
D={(x1, y1), …, (xl, yl)}, xRn, y{-1,1},
Và siêu phẳng: wx+b=0
Với các ràng buộc: |wxi+b| 1
{x|(w.x)+b1}
{x|(w.x)+b-1}
x1
yi = +1
x2
yi = -1
w
{x|(w.x)+b=0}
19
Vấn đề đặt ra bây giờ là xác định các hệ số w và b như thế nào để siêu
phẳng tìm được là tốt nhất? Khoảng cách từ một điểm dữ liệu x i đến siêu
phẳng là
d ( w, b; xi )
w.xi b
w
Trong đó:
.xi b : là giá trị tuyệt đối của biểu thức .xi b
: là độ dài Ơcơlit của vector w
Giả sử h(w,b) là tổng của khoảng cách từ điểm dữ liệu gần nhất của lớp
một đến siêu phẳng và khoảng cách từ điểm dữ liệu gần nhất của lớp -1 đến
siêu phẳng. Ta có:
h(w, b) min d (w, b; xi ) min d (w, b; xi )
xi , yi 1
min
xi , yi 1
xi , yi 1
w.xi b
w
min
xi , yi 1
w.xi b
w
1
w.xi b min w.xi b
xmin
,
y
1
xi , yi 1
w i i
2
w
Siêu phẳng tối ưu là siêu phẳng có
nhỏ nhất. Bài toán tìm siêu
phẳng tối ưu tương đương với bài toán (OP1):
1 2
w
w
2
Với: yi[wxi+b] 1, i=1,2,…l
OP1 tương đương với bài toán tối ưu sau:
1 l l
max LD ( ) i j yi y j xi x j
2 i 1 j 1
Min ( w)
Với ràng buộc:
i 0
i 1,...l
l
y 0
i 1
i
i
Giả sử là nghiệm của bài toán, khi đó
20
l
w i* yi xi
*
i 1
1
b* w * ( xr xs )
2
Hàm quyết định:
f ( x) sgn w* x b
xr, xs tương ứng là các svm thuộc lớp 1, -1
2.7. SVM với dữ liệu có nhiễu
Tập dữ liệu huấn luyện Tr có thể phân chia được tuyến tính nhưng
có nhiễu
Bài toán tìm siêu phẳng tối ưu tương đương với bài toán (OP2):
Min ( w, )
w,
l
1 2
w C i
2
i 1
Với:
y i w.xi b 1 i ,
i 0
i 1, ..., l
- Xem thêm -