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

SAVADY Sathaphone

Nghiên cứu phương pháp Máy véc tơ hỗ trợ với lề mềm
và ứng dụng phân lớp dữ liệu tuyến tính có nhiễu

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

THÁI NGUYÊN - 2019

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN




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

SAVADY Sathaphone

Nghiên cứu phương pháp Máy véc tơ hỗ trợ với lề mềm
và ứng dụng phân lớp dữ liệu tuyến tính có nhiễu

Chuyên ngành: Khoa học máy tính
Mã số: 8480101

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

Người hướng dẫn khoa học: TS. Đàm Thanh Phương

Tác giả xin chân thành cảm ơn TS Đàm Thanh Phương, trường Đại học
Công nghệ thông tin và truyền thông - Đại học Thái Nguyên, là giáo viên
hướng dẫn khoa học đã hướng dẫn tác giả hoàn thành luận văn này, xin được
cảm ơn các thầy, cô giáo trường Đại học công nghệ thông tin và truyền thông
nơi tác giả theo học và hoàn thành chương trình cao học đã nhiệt tình giảng
dạy và giúp đỡ.
Xin cảm ơn nơi tác giả công tác đã tạo mọi điều kiện thuận lợi để tác giả
hoàn thành chương trình học tập.
Và cuối cùng xin cảm ơn gia đình, bạn bè, đồng nghiệp đã động viên, giúp
đỡ tác giả trong suốt thời gian học tập, nghiên cứu và hoàn thành luận văn
này.
Xin chân thành cảm ơn.
Thái Nguyên, ngày 18 tháng 7 năm 2019
Tác giả luận văn
SAVADY Sathaphone

ii


DANH SÁCH HÌNH VẼ
2.1

Các mặt phân cách hai lớp tuyến tính . . . . . . . . . . . . . . . 26

2.2

Lề của hai lớp không bằng nhau. . . . . . . . . . . . . . . . . . . 26

2.3



3.2

Dữ liệu tuyến tính có nhiễu . . . . . . . . . . . . . . . . . . . . . 49

3.3

Đường phân chia tìm được bởi sklearn . . . . . . . . . . . . . . . 52

3.4

Đường phân chia tìm được bởi hinge loss . . . . . . . . . . . . . 52

3.5

Đường phân chia tìm được bởi đối ngẫu. Các kết quả là như nhau 52

3.6

Nghiệm tìm bằng sklearn, C =0.1. . . . . . . . . . . . . . . . . . 53

3.7

Nghiệm tìm bằng sklearn, C=1 . . . . . . . . . . . . . . . . . . . 53

3.8

Nghiệm khi C=10 . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.9

||.||

Chuẩn Euclide.
Suport vector machine - máy véc tơ hỗ

SVM
trợ
Soft SVM

Máy véc tơ hỗ trợ với lề mềm.

Argmin

Bài toán tối ưu tham số.

Duality

Tính chất đối ngẫu, đối ngẫu

Lagrangian

Đối ngẫu Lagrange

Strong duality Tính chất đối ngẫu mạnh
Weak duality

Tính chất đối ngẫu yếu

KKT


Hàm xác định dấu.

∂f
∂x

∇x f

Đạo hàm của hàm số f theo biến số

x∈R
Gradient (đạo hàm ) của hàm số f
theo véc tơ x.

v


MỤC LỤC
Lời cam đoan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

Danh sách hình vẽ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

Danh mục ký hiệu, từ viết tắt . . . . . . . . . . . . . . . . . . . . . . .


2.2. Bài toán SVM với lề mềm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

Chương 3. ỨNG DỤNG VÀ LẬP TRÌNH MÔ PHỎNG . . . . . . .

46

3.1. Lập trình tìm nghiệm cho SVM . . . . . . . . . . . . . . . . . . . . . . . .

46

3.2. Lập trình tìm nghiệm cho Soft SVM . . . . . . . . . . . . . . . . . . .

48

Kết luận chung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

vi


MỞ ĐẦU
Những năm gần đây, AI - Artificial Intelligence (Trí Tuệ Nhân Tạo), và cụ

Khoảng cách như nhau này được gọi là margin (lề). Ngoài ra, việc margin
rộng hơn sẽ mang lại hiệu ứng phân lớp tốt hơn vì sự phân chia giữa hai
classes là rạch ròi hơn. Việc này là một điểm khá quan trọng giúp Support
Vector Machine mang lại kết quả phân loại tốt hơn so với Neural Network
với 1 layer, tức Perceptron Learning Algorithm.[1], [2]
Bài toán tối ưu trong Support Vector Machine (SVM) chính là bài toán
đi tìm đường phân chia sao cho margin là lớn nhất. Đây cũng là lý do vì sao
SVM còn được gọi là Maximum Margin Classifier. [7]
Tuy nhiên ngay cả SVM với lề cứng cũng sẽ không giải quyết được một số
bài toán phân lớp có nhiễu, việc nghiên cứu SVM với lề mềm sẽ giải quyết
tốt hơn trường hợp này.
Nội dung của luận văn gồm 3 chương:
Chương 1. Các kiến thức cơ sở
Chương này trình bày các kiến thức chuẩn bị cho việc nghiên cứu.
1.1 Giới thiệu về học máy
1.2 Giới thiệu về ngôn ngữ lập trình Python
1.3 Các kiến thức cơ sở về Đại số tuyến tính
Chương 2. Phương pháp máy véc tơ hỗ trợ SVM
Nội dung chương 2 tập trung vào vấn đề nghiên cứu các phương pháp máy
véc tơ hỗ trợ, cụ thể như sau:
2.1 Xây dựng bài toán tối ưu cho SVM
2.2 Bài toán đối ngẫu cho SVM
2.3 Bài toán đối ngẫu Lagrange.
2.4 Bài toán tối ưu không ràng buộc cho Soft SVM.
Chương 3. Ứng dụng và lập trình mô phỏng
Sau khi nắm rõ các nội dung trong chương 2, chương 3 trình bày một số ví
2


dụ minh họa ứng dụng và lập trình:

Python là ngôn ngữ có hình thức khá đơn giản và rõ ràng, do đó tạo nên
sự dễ dàng tiếp cânh cho những lập trình viên mới bắt đầu.
Ban đầu, Python được phát triển để chạy trên nền Unix. Nhưng rồi theo
thời gian, nó đã "bành trướng" sang mọi hệ điều hành từ MS-DOS đến Mac
OS, OS/2, Windows, Linux và các hệ điều hành khác thuộc họ Unix. Mặc
dù sự phát triển của Python có sự đóng góp của rất nhiều cá nhân, nhưng
Guido van Rossum hiện nay vẫn là tác giả chủ yếu của Python. Ông giữ vai
trò chủ chốt trong việc quyết định hướng phát triển của Python.
Kiến thức tham khảo về Python được tham khảo từ tài liệu [8], [9].
1.1.2.

Một số tính chất

• Python is Interpreted: Nhờ chức năng thông dịch mà trình thông dịch
(Interpreter) của Python có thể xử lý lệnh tại thời điểm chạy chương
trình (runtime). Nhờ đó mà ta không cần biên dịch chương trình trước
4


khi thực hiện nó (tương tự như Perl và PHP).

• Python is Interactive: Tính năng tương tác của Python giúp ta có thể
tương tác trực tiếp với trình thông dịch của nó ngay tại dấu nhắc lệnh.
Cụ thể: Ta có thể thực hiện lệnh một cách trực tiếp tại dấu nhắc của
Python.

• Python is Object-Oriented: Python hỗ trợ mạnh cho phong cách lập
trình hướng đối tương và kỹ thuật lập trình gói mã trong đối tượng.

• Python is a Beginner’s Language: Mặc dầu Python được xem là ngôn

không phải lo lắng những nhiệm vụ khó khăn như quản lý bộ nhớ, dọn dẹp
những dữ liệu vô nghĩa,... Khi chạy code Python, nó sẽ tự động chuyển đổi
code sang ngôn ngữ máy tính có thể hiểu. Ta không cần lo lắng về bất kỳ
hoạt động ở cấp thấp nào.
Thư viện tiêu chuẩn lớn để giải quyết những tác vụ phổ biến: Python có
một số lượng lớn thư viện tiêu chuẩn giúp cho công việc lập trình của ta trở
nên dễ thở hơn rất nhiều, đơn giản vì không phải tự viết tất cả code. Ví dụ:
Ta cần kết nối cơ sở dữ liệu MySQL trên Web server? Ta có thể nhập thư
viện MySQLdb và sử dụng nó. Những thư viện này được kiểm tra kỹ lưỡng
và được sử dụng bởi hàng trăm người. Vì vậy, ta có thể chắc chắn rằng nó
sẽ không làm hỏng code hay ứng dụng của mình.
Hướng đối tượng: Mọi thứ trong Python đều là hướng đối tượng. Lập trình
hướng đối tượng (OOP) giúp giải quyết những vấn đề phức tạp một cách
trực quan. Với OOP, ta có thể phân chia những vấn đề phức tạp thành những
tập nhỏ hơn bằng cách tạo ra các đối tượng.
1.1.4.

Các lĩnh vực sử dụng lập trình python phổ biến

Lập trình ứng dụng web: ta có thể tạo web app có khả năng mở rộng
(scalable) được bằng cách sử dụng framework và CMS (Hệ thống quản trị
nội dung) được tích hợp trong Python. Vài nền tảng phổ biến để tạo web
app là: Django, Flask, Pyramid, Plone, Django CMS. Các trang như Mozilla,
Reddit, Instagram và PBS đều được viết bằng Python.
Khoa học và tính toán: Có nhiều thư viện trong Python cho khoa học và
tính toán số liệu, như SciPy và NumPy, được sử dụng cho những mục đích
chung chung trong tính toán. Và, có những thư viện cụ thể như: EarthPy cho
khoa học trái đất, AstroPy cho Thiên văn học,... Ngoài ra, Python còn được
6


trình thu nhận kiến thức, kỹ năng do người khác truyền lại hoặc đọc đi, đọc
lại, nghiềm ngẫm ghi nhớ ( học thuộc lòng). Rộng hơn, học bao gồm cả quá
trình đúc rút tri thức từ các quan sát, trải nghiệm thực tiễn.
Học máy ( machine learning) mang hai nghĩa thông dụng:

7


1. sử dụng máy tính để khám phá tri thức từ dữ liệu,
2. sự học trong máy (tác tử: agent). Về phương diện công nghệ, học máy
là một lĩnh vực của trí tuệ nhân tạo, trong đó nghiên cứu các kỹ thuật
xây dựng và phát triển các chương trình máy tính có thể thích nghi và
“học” từ các dữ liệu mẫu hoặc kinh nghiệm.
Đến nay, đã có nhiều định nghĩa khái niệm này, tuy nhiên khó có một định
nghĩa thỏa đáng được mọi người thừa nhận. Định nghĩa sau phát triển từ
định nghĩa của T. Mitchell cho ta cách nhìn toán học của một chương trình
học khi nghiên cứu, thiết kế.
Định nghĩa 1.2.1. Một chương trình máy tính được gọi là học từ dữ liệu,
kinh nghiệm E đối với lớp nhiệm vụ T và độ đo mức thực hiện P nếu việc
thực hiện các nhiệm vụ T của nó khi đo bằng P được cải tiến nhờ dữ liệu
hoặc kinh nghiệm E . [1].
Theo định nghĩa này, người ta cần tối ưu hóa độ đo thực hiện P dựa trên
phân tích dữ liệu, kinh nghiệm E để tìm cách thực hiện nhiệm vụ T tốt nhất.
Ví dụ 1: Phân tích dữ liệu bán lẻ của siêu thị
Hằng ngày các siêu thị bán ra một lượng lớn những mặt hàng phong phú
và lưu lại các hóa đơn thanh toán(bản sao giỏ hàng). Từ các dữ liệu bán lẻ
có được, ta có thể phân tích các giỏ hàng để tiên đoán được một khách hàng
mua mặt hàng A thì sẽ mua mặt hàng B với xác suất bao nhiêu? Nếu xác
suất này là lớn thì ta nên xếp các mặt hàng này gần nhau, như thế tiện cho
khách hàng và lượng hàng bán được cũng tăng lên so với việc để khách hàng


Tại sao cần nghiên cứu học máy?

Sự thâm nhập mạnh mẽ của công nghệ thông tin tinh tế, xã hội công nghệ
tri thức phát triển và tạo nên nhu cầu ứng dụng rộng rãi. Sau đây là một số
phạm vi nghiên cứu, ứng dụng điển hình:

• Xây dựng các hệ nhận dạng mẫu dùng cho các thiết bị nghe nhìn cho
robot và trong lĩnh vực tự động hóa, nhận dạng chữ viết tay, chuyển đổi
các bài nói thành văn bản, phân tích ảnh tự động...

• Tạo ra các chương trình máy tính có thể hoạt động thích nghi với môi
trường thay đổi hay thực hiện các nhiệm vụ mà ban đầu chưa xác định
9


rõ, chẳng hạn, hệ lái tự động ( máy bay, ô tô, tàu thủy,...) , trò chơi hay
các điều khiển robot đa năng.

• Khám phá tri thức từ dữ liệu đặc biệt là các cơ sở dữ liệu lớn, để trợ
giúp ra quyết định. Chẳng hạn, phân tích thị trường, chẩn đoán bệnh
của bệnh nhân và xác định phương án điều trị nhờ phân tích các bệnh
án lưu trữ...
1.2.3.

Một số lĩnh vực liên quan

Trong mấy chục năm qua, các nghiên cứu khoa học và ứng dụng của học
máy phát triển nhanh, kết hợp các tiến bộ của nhiều lĩnh vực khác. Sau đây
là các lĩnh vực góp phần quan trọng cho nghiên cứu học máy:

Các bài toán học thiết lập đúng đắn

Bài toán học được cho là thiết lập đúng khi thực sự có thể cải tiến được

P qua kinh nghiệm E . Thông thường mô hình toán học để xây dựng thuật
toán cho một bài toán học đòi hỏi phải đúng đắn theo Hadamard. Trong các
bài toán thực tế,Hadamard cho rằng một mô hình toán học ứng dụng được
xem là thiết lập đúng đắn (well-posed problem) nếu nó có các tính chất:
1. Luôn tồn tại lời giải
2. Chỉ có duy nhất một lời giải
3. Khi các điều kiện ban đầu thay đổi ít thì lời giải cũng thay đổi ít
Tuy nhiên, trong nhiều bài toán, điều kiện duy nhất một lời giải nhiều khi
khó đáp ứng trong trường hợp đó người ta hay dùng phương pháp chính quy
hóa (hiệu chỉnh hàm mục tiêu) để bài toán trở nên thiết lập đúng đắn.
Bài toán học phải được xác định đúng đắn dựa trên việc xác định rõ nhiệm
vụ cụ thể, độ đo việc thực hiện và nguồn dữ liệu, kinh nghiệm.
Phương pháp thông dụng nhất để đưa ra thuật toán cho các bài toán học
là xây dựng một mô hình toán học phụ thuộc các tham số và dùng dữ liệu
hoặc kinh nghiệm đã có thể xác định giá trị thích hợp cho các tham số này.
[7]

1.3.

Một số kiến thức toán học bổ trợ

Các kiến thức toán học bổ trợ được tham khảo từ [7] và [10].
1.3.1.

Phép nhân hai ma trận


(AB)T = BT AT ;

(AB)H = BH AH

Theo định nghĩa trên, bằng cách coi véc tơ là trường hợp đặc biệt của ma
trận, tích vô hướng của hai véc tơ (inner product) x, y ∈ Rn được định nghĩa
là
n
T

T

x y=y x=

x i yi

(1.3.2)

i=1

Chú ý, xH y = yH x

H

= yH x. Chúng bằng nhau khi và chỉ khi chúng là

các số thực. Nếu tích vô hướng của hai véc tơ khác không mà bằng không
thì chúng vuông góc với nhau.

xH x ≥ 0, ∀x ∈ Cn vì tích của một số phức với liên hợp của nó luôn là một


1 0 0



I3 =  0 1 0

0 0 1




,


1 0


0 1
I4 = 

0 0

0 0

0 0





13

(1.3.4)


Ma trận nghịch đảo thường được sử dụng để giải hệ phương trình tuyến
tính. Giả sử rằng A ∈ Rn×n là một ma trận khả nghịch và một véc tơ bất
kỳ b ∈ Rn . Khi đó phương trình:

Ax = b

(1.3.5)

có nghiệm duy nhất là x = A−1 b. Thật vậy, nhân bên trái cả hai phương
trình với A−1 , ta có Ax = b ⇔ A−1 Ax = A−1 b ⇔ x = A−1 b.
Khi A không khả nghịch hay không vuông, phương trình tuyến tính có
thể không có nghiệm hoặc vô số nghiệm.
Quy tắc tính ma trận nghịch đảo của ma trận tích: (AB)−1 = B−1 A−1 .
1.3.3.

Hạng của ma trận

Hạng của ma trận A được định nghĩa là số lượng lớn nhất các cột độc lập
tuyến tính, ký hiệu là rank(A)
Các tính chất:
1. Một ma trận có hạng bằng 0 khi và chỉ khi nó là ma trận 0.
2. rank(A) = rank AT
3. Nếu A ∈ Rm×n , thì rank(A) ≤ min(m, n)
4. rank(AB) ≤ min(rank(A), rank(B))
5. rank(A + B) ≤ rank(A) + rank(B).



1, i = j
T
ui uj =

0, i = j

(1.3.7)

Gọi U = [u1 , u2 , . . . , um ] với {u1 , u2 , . . . , um ∈ Rm } là trực chuẩn, từ (1.3.7)
có thể suy ra

UUT = UT U = I

(1.3.8)

trong đó I là ma trận đơn vị bậc n. Nếu một ma trận thỏa mãn điều kiện
(1.3.8), ta gọi nó là ma trận trực giao (orthogonal matrix). Không có định
nghĩa cho ma trận trực chuẩn.
Nếu một ma trận vuông phức U thỏa mãn UUH = UH U = I, ta nói rằng

U là một ma trận Unitary.
1.3.4.2.

Tính chất của ma trận trực giao

1. U−1 = UT : Nghịch đảo của một ma trận trực giao chính là ma trận
chuyển vị của nó.
2. Nếu U là ma trận trực giao thì chuyển vị của nó UT cũng là ma trận

Cho một ma trận vuông A ∈ Rn×n , một véc tơ x ∈ Rn (x = 0) và một số
vô hướng (có thể thực hoặc phức) λ. Nếu Ax = λx, thì ta nói λ và x là một
cặp giá trị riêng, véc tơ riêng (eigenvalue, eigenvector) của ma trận A
Từ định nghĩa ta cũng có, (A − λI)x = 0, tức là x nằm trong không gian
Null của A − λI. Vì x = 0, nên A − λI là ma trận không khả nghịch. Vậy

det(A − λI) = 0, hay λ là nghiệm của phương trình det(A − tI) = 0. Định
thức này là một đa thức bậc n của t, gọi là đa thức đặc trưng (characteristic
polynomial) của A, ký hiệu là pA (t). Tập hợp tất cả các giá trị riêng của một
ma trận còn gọi là phổ (spectrum) của ma trận đó.
1.3.5.2.

Tính chất

1. Nếu x là một véc tơ riêng của A ứng với giá trị riêng λ thì với mọi

k ∈ R, k = 0, kx cũng là một véc tơ riêng của A ứng với giá trị riêng đó.
Nếu x1 , x2 là hai véc tơ riêng ứng với cùng một giá trị riêng λ thì tổng của
chúng cũng là một véc tơ riêng ứng với giá trị riêng đó. Từ đó suy ra tập
các véc tơ riêng ứng với một giá trị riêng của ma trận vuông tạo thành
một không gian véc tơ con, được gọi là không gian riêng (eigenspace )
ứng với giá trị riêng đó.
2. Mọi ma trận vuông bậc n đều có n giá trị riêng (kể cả lặp, phức).
3. Tích của tất cả các giá trị riêng của ma trận bằng định thức, tổng của
16


tất cả các giá trị riêng của ma trận bằng tổng các phần tử trên đường
chéo của ma trận.
4. Phổ của ma trận bằng phổ của ma trận chuyển vị của nó.

tên gọi là chéo hóa ma trận.
Tính chất:
1. Khái niệm chéo hóa ma trận chỉ áp dụng với ma trận vuông. Vì không
có định nghĩa giá trị riêng, véc tơ riêng cho ma trận không vuông.
17