BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC DUY TÂN

NGÔ THÀNH TÂM
PHÂN LỚP ẢNH SỬ DỤNG
KỸ THUẬT MDS KẾT HỢP VỚI SVM
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
ĐÀ NẴNG – 2014
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC DUY TÂN

NGÔ THÀNH TÂM
PHÂN LỚP ẢNH SỬ DỤNG
KỸ THUẬT MDS KẾT HỢP VỚI SVM
Chuyên ngành : KHOA HỌC MÁY TÍNH
Mã số: 60.48.01.01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Người hướng dẫn khoa học: TS. ĐẶNG VIỆT HÙNG
ĐÀ NẴNG – 2014
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi.
Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai
công bố trong bất kỳ công trình nào khác.
Tác giả
Ngô Thành Tâm
3
LỜI CẢM ƠN
Luận văn này được hoàn thành trước hết là xuất phát từ sự nổ lực phấn đấu
của bản thân trong quá trình học tập, nghiên cứu và trong suốt thời gian làm đề tài.
Đề tài đã hoàn thành đúng với thời gian như kế hoạch đã lập ra và thời gian triển
khai thực tế, để đạt được như vây không thể không nhớ đến công ơn của thầy cô và

10 VC Vapnik Chervonenkis
11 VS Versus
12 OVR
One-vs-Rest
13 OVO
One-vs-One
14 2D Two Dimensionals
15 3D Three Dimensionals
5
DANH MỤC BẢNG
Số hiệu Tên bảng Trang
Bảng 1 Khoảng cách giữu 10 thành phố. 32
Bảng 2 Thứ tự khoảng cách của bảng 1, khoảng cách nhỏ nhất là 1. 34
Bảng 3
Khoảng cách giữa các thành phố Đan Mạch.
39
Bảng 4
Hàm khoảng cách giữa các điểm lân cận.
41
Bảng 5 Stress và goodness of fit. 42
Bảng 6
Bảng kết quả kiểm tra sử dụng 60% để huấn luyện và 40% kiểm tra
của cơ sở dữ liệu att sử dụng phương pháp PCA-SVM, MDS-SVM.
59
Bảng 7
Bảng kết quả kiểm tra sử dụng 70% để huấn luyện và 30% kiểm tra
của cơ sở dữ liệu att sử dụng phương pháp PCA-SVM, MDS-SVM.
60
Bảng 8
Bảng kết quả kiểm tra sử dụng 60% để huấn luyện và 40% kiểm tra

Hình 1.10
Minh họa PCA tìm các trục tọa độ mới sao cho dữ liệu có độ biến
thiên cao nhất.
25
Hình 1.11
Hình hiển thị dung PCA giảm số chiều những vẫn đảm bảo được các
thông tin quan trọng nhất.
25
Hình 1.12 Ảnh gốc ban đầu chuyển sang eigenfaces.
28
Hình 1.13 Sơ đồ hoạt động của hệ thống PCA và SVM.
29
Hình 2.1
Bước đầu tiên của MDS với khoảng cách trong bảng 1.
33
Hình 2.2 Vị trí điểm số 9 trên bảng đồ.
33
Hình 2.3 Vị trí điểm 5 trên bảng đồ.
33
Hình 2.4 Kết quả cuối cùng của MDS cho bảng dữ liệu 1.
33
Hình 2.5 Xác định các điểm và Sử dụng la bàn địa lý.
33
Hình 2.6
Phản ánh ngang cấu hình trong hình 2.5 để hướng Đông nằm bên phải.
33
Hình 2.7 Xoay hình 2.6 để North nằm trên.
34
Hình 2.8
Cấu hình của các Hình 2.7 trên bảng đồ châu Âu.

43
Hình 2.17 Sơ đồ Shepard.
44
Hình 2.18
Mặt phẳng Cartesian với các điểm i, j được nối với nhau bởi các đoạn
thẳng và được tính bằng khoản cách Euclidean.
44
Hình 2.19 Các bước xác định tọa độ mới sử dụng MDS.
49
Hình 2.20 Sơ đồ mô tả các bước hoạt động của hệ thống MDS&SVM.
50
Hình 2.21 Ảnh sau khi được chuẩn hóa chuyển về dạng Gray.
51
Hình 3.1 Hình ảnh trong cơ sở dữ liệu Ifd.
53
Hình 3.2 Các ảnh trong cơ sở dư liệu att.
54
Hình 3.3 Giao diện hướng dẫn.
55
Hình 3.4 Giao diện chính của chương trình.
55
Hình 3.5
Giao diện huấn luyện và kiểm tra kết quả so sánh giữa hai phương
pháp PCA-SVM và MDS-SVM.
56
Hình 3.6 Hình kết quả số chiều/vector, độ chính xác, thời gian xử lý.
57
Hình 3.7 Hình kết quả ID các ảnh dung Train & Test.
57
Hình 3.8 Hình bảng tổng hợp kết quả.

phân lớp và nhận dạng vào các ứng dụng quan trọng đó luôn luôn cần, nó góp phần
vào phát triển kinh tế, tăng hiệu quả công việc và giúp đỡ con người thực hiện được
các công việc khó khăn và phức tạp.
Đối với các hệ thống phân lớp và nhận dạng với lượng thông tin khổng lồ để
thực hiện tốt trên phần dữ liệu lớn này đòi hỏi phải có những kỹ thuật phân lớp và
nhận dạng phải thực hiện một vừa chóng vừa chính xác thì mới đáp ứng được yêu cầu
cho ứng dụng ngày nay.
Xuất phát từ những lý do trên mà tôi đã chọn đề tài: “Phân lớp ảnh sử dụng kỹ
thuật MDS kết hợp SVM”.
2. Mục tiêu nghiên cứu:
• Tìm hiểu các kỹ thuật áp dụng trong phân lớp và nhận dạng: MDS-SVM, PCA-
SVM.
• Xây dựng chương trình mô phỏng để lấy kết quả hoạt động các kỹ thuật trên.
• Đánh giá và kết luận hiệu quả và hiệu năng làm việc của các kỹ thuật.
• Xây dựng mô hình hệ thống phân lớp và nhận dạng của các phương pháp trên áp
dụng vào phân lớp nhận dạng mặt người.
3. Đối tượng và phạm vi nghiên cứu:
a. Đối tượng nghiên cứu:
• Xử lý ảnh.
• Lý thuyết nhận dạng.
9
• Các kỹ thuật loại bỏ không gian chứa ít thông tin và nhận dạng như:
PCA, MDS, SVM
b. Phạm vi nghiên cứu:
• Luận văn chủ yếu nghiên cứu tập trung vào phân lớp ảnh mặt người.
• Tìm hiểu phân lớp dữ liệu ảnh các đối tượng ảnh khác nhau.
• Tìm ra thông số đánh giá hiệu năng các kỹ thuật áp dụng trong hệ thống
phân lớp ảnh.
4. Phương pháp nghiên cứu
Nghiên cứu, tìm hiểu các phương pháp kỹ thuật áp dụng vào bài toán phân lớp,

6. Ý nghĩa khoa học và thực tiễn của luận văn
• Về mặt lý thuyết: Luận văn đã chứng tỏ rằng phương pháp MDS kết hợp
SVM có nhiều ưu điểm hơn đối với phương pháp PCA kết hợp SVM. Một
trong những tối ưu cơ bản của phương pháp MDS là giảm chiều của dữ liệu
tuy nhiên không làm mất nhiều thông tin như phương pháp PCA.
• Về mặt thực tiễn: Đây là một phương pháp có ứng dụng phổ biến trong rất
nhiều ngành. Cách hoạt động của hệ thống đơn giản phù hợp cho việc cài
đặt ở nhiều hệ thống.
7. Cấu trúc luận văn
Luận văn được chia làm bố cục 3 phần:
 Phần mở đầu: Nêu lên lý do chọn đề tài, mục tiêu nghiên cứu, đối tượng và
phạm vi nghiên cứu, phương pháp nghiên cứu, ý nghĩa khoa học và thực
tiễn của luận văn.
 Phần nội dung: Có cấu trúc 3 chương
• Chương 1: Khái quát về xử lý ảnh, tổng quan về các kỹ thuật phân lớp ảnh
và nhận dạng. Chương này giới thiệu về bài toán phân lớp và nhận dạng, giới
thiệu các kỹ thuật tiếp cận trong phân lớp như SVM, PCA, PCA-MDS. Xác
định phạm vi thực hiện đề tài cũng như giới thiệu mô hình hệ thống phân lớp
PCA kết hợp MDS.
• Chương 2: Giới thiệu về kỹ thuật MDS, MDS kết hợp SVM, xây dựng mô
hình phân lớp MDS-SVM, mô tả hoạt động của hệ thống phân lớp cũng như
lưu đồ giải thuật của hệ thống.
• Chương 3: Cài đặt và chạy chương trình thử nghiệm, đưa ra các thông số mô
11
phỏng, giới thiệu giao diện chương trình. Thể hiện kết quả mô phỏng các
phương pháp PCA-SVM và MDS-SVM, so sánh đánh giá kết quả của hai
phương pháp này bằng sơ đồ. Kiểm tra độ chính xác của phương pháp MDS-
SVM sử dụng cho việc nhận dạng khuôn mặt.
 Phần kết luận: Đánh giá những vấn đề luận văn đã làm được, những thách
thức chưa giải quyết được và hướng phát triển của đề tài.

màu nhất định. Kích thước và khoảng cách giữa các điểm ảnh đó được chọn thích hợp
sao cho mắt người cảm nhận sự liên tục về không gian và mức xám (hoặc màu) của
ảnh số gần như ảnh thật. Mỗi phần tử trong ma trận được gọi là một phần tử ảnh.
• Mức xám của ảnh
Mức xám: Là kết quả của sự biến đổi tương ứng 1 giá trị độ sáng của 1 điểm
ảnh với 1 giá trị nguyên dương. Thông thường nó được xác định trong [0, 255] tuỳ
thuộc vào giá trị mà mỗi điểm ảnh được biểu diễn.
Các thang giá trị mức xám thông thường: 16, 32, 64, 128, 256 (Mức 256 là mức
phổ dụng. Lý do: từ kỹ thuật máy tính dùng 1 byte (8 bit) để biểu diễn mức xám. Mức
xám dùng 1 byte biểu diễn: 28 = 256 mức, tức là từ 0 đến 255).
• Độ phân giải của ảnh
Định nghĩa: Độ phân giải (Resolution) của ảnh là mật độ điểm ảnh được ấn
định trên một ảnh số được hiển thị.
Theo định nghĩa, khoảng cách giữa các điểm ảnh phải được chọn sao cho mắt
người vẫn thấy được sự liên tục của ảnh. Việc lựa chọn khoảng cách thích hợp tạo nên
một mật độ phân bổ, đó chính là độ phân giải và được phân bố theo trục x và y trong
không gian hai chiều.
Ví dụ: Độ phân giải của ảnh trên màn hình CGA (Color Graphic Adaptor) là
một lưới điểm theo chiều ngang màn hình: 320 điểm chiều dọc * 200 điểm ảnh
(320*200). Rõ ràng, cùng màn hình CGA 12” ta nhận thấy mịn hơn màn hình CGA
17” độ phân giải 320*200. Lý do: cùng một mật độ (độ phân giải) nhưng diện tích màn
hình rộng hơn thì độ mịn (liên tục của các điểm) kém hơn.
• Các cách phân loại ảnh
Ảnh nhị phân: Giá trị xám của tất cả các điểm ảnh chỉ nhận giá trị 1 hoặc 0
như vậy mỗi điểm ảnh trong ảnh nhị phân được biểu diễn bởi 1 bit.
Ảnh xám: Giá trị xám nằm trong [0, 255] như vậy mỗi điểm ảnh trong ảnh nhị
phân được biểu diễn bởi 1 byte.
Ảnh màu:
 Hệ màu RGB: Một pixel được biểu diễn bằng 3 giá trị (R, G, B) trong đó R,
G, B là một giá trị xám và được biểu biểu diễn bằng 1 byte. Khi đó ta có một

danh.
15
Trong các ứng dụng rõ ràng là không thể chỉ dùng có một cách tiếp cận đơn lẻ
để phân loại “tối ưu” do vậy cần sử dụng cùng một lúc nhiều phương pháp và cách tiếp
cận khác nhau. Do vậy, các phương thức phân loại tổ hợp hay được sử dụng khi nhận
dạng và nay đã có những kết quả có triển vọng dựa trên thiết kế các hệ thống lai
(hybrid system) bao gồm nhiều mô hình kết hợp.
Việc giải quyết bài toán nhận dạng trong những ứng dụng mới, nảy sinh trong
cuộc sống không chỉ tạo ra những thách thức về giải thuật, mà còn đặt ra những yêu
cầu về tốc độ tính toán. Đặc điểm chung của tất cả những ứng dụng đó là những đặc
điểm, đặc trưng cần thiết thường là nhiều, không thể do chuyên gia đề xuất, mà phải
được trích chọn dựa trên các thủ tục phân tích dữ liệu.
1.2 Tổng quan về phân lớp và nhận dạng:
Phân loại (hay phân lớp) là một tiến trình xử lý nhằm xếp các mẫu dữ liệu hay
các đối tượng vào một trong các lớp đã được định nghĩa trước. Các mẫu dữ liệu hay
các đối tượng được xếp về các lớp dựa vào giá trị của các thuộc tính (attributes) cho
một mẫu dữ liệu hay đối tượng. Sau khi đã xếp tất cả các đối tượng đã biết trước vào
các lớp tương ứng, lúc này mỗi lớp được đặc trưng bởi tập các thuộc tính của các đối
tượng chứa trong lớp đó.
Các thuật toán phân loại tiêu biểu bao gồm như mạng neural, cây quyết định,
suy luận quy nạp, mạng Beyesian, Support Vector Machine…. Tất cả các cách tiếp cận
này xây dựng nên những mô hình đều có khả năng phân loại cho một mẫu mới chưa
biết dựa vào những mẫu tương tự đã được học. Bài toán phân loại có thể xử lý thông
tin được thu thập từ mọi lĩnh vực hoạt động của con người và thế giới tự nhiên được
biểu diễn dưới dạng các bảng. Bảng này bao gồm các đối tượng và các thuộc tính. Các
phần tử trong bảng là các giá trị xác định các thuộc tính (attributes hay features) của
các đối tượng. Trong đó số cột chính là số thuộc tính của các đối tượng, mỗi cột là một
thuộc tính và số dòng chính là số đối tượng chứa trong dữ liệu này. Mọi dữ liệu được
biểu diễn dưới các dạng khác có thể được chuyển thành dạng bảng như trên để thực
hiện quá trình phân loại.

thử, so sánh lớp đúng mà mẫu thử đó thuộc về với lớp mà mô hình phân lớp này dự
đoán cho mẫu thử đó.
17
1.2.2 Một số bộ phân loại phổ biến
1.2.2.1 Cây quyết định
Một cây quyết định là một cấu trúc cây, trong đó mỗi node trong biểu thị cho
một phép phân nhánh tương ứng cho một thuộc tính, mỗi nhánh biểu thị cho một kết
quả của một phép thử, các node lá biểu thị cho lớp hoặc các phân bố lớp. Node trên
cùng trong một cây được gọi là gốc. Để phân lớp một mẫu chưa biết, những giá trị
thuộc tính của mẫu đó được thử ngược lại trên cây quyết định. Một đường dẫn từ gốc
đến một node lá là cơ sở cho việc dự đoán lớp của một mẫu. Cây quyết định có thể dễ
dàng chuyển đổi sang một tập các luật phân lớp. Cơ sở toán học của cây quyết định là
thuật toán tham lam, thuật toán này đã xây dựng cây quyết định đệ quy từ trên xuống
dưới, theo phương pháp chia để trị.
1.2.2.2 Mạng Bayes
Bayesian là phương pháp phân lớp dựa vào thống kê. Ta có thể dự đoán xác
suất của các lớp trong tập dữ liệu, dựa vào xác suất này có thể xếp các mẫu vào các lớp
riêng biệt. Thuật toán phân lớp Bayesian giả thiết rằng giá trị các thuộc tính của một
lớp độc lập với giá trị của các thuộc tính khác, giả thiết này còn được gọi là lớp độc
lập có điều kiện, nó làm đơn giản các tính toán sau này. Mạng Bayesian là một đồ thị,
trên đồ thị cho phép biểu diễn mối quan hệ giữa các thuộc tính.
1.2.2.3 Kỹ thuật K người láng giềng gần nhất:
Bộ phân lớp dựa trên thuật toán K người láng giềng gần nhất là một bộ phân
lớp dựa trên bộ nhớ, đơn giản vì nó được xây dựng bằng cách lưu trữ tất cả các đối
tượng trong tập huấn luyện. Để phân lớp cho một điểm dữ liệu mới x, trước hết bộ
phân lớp sẽ tính khoảng cách từ điểm dữ liệu trong tập huấn luyện. Qua đó tìm được
tập N(x, D, k) gồm k điểm dữ liệu mẫu có khoảng cách đến x là gần nhất. Ví dụ nếu
các dữ liệu mẫu được biểu diễn bởi không gian vector thì chúng ta có thể sử dụng
khoảng cách Euclide để tính khoảng cách giữa các điểm dữ liệu với nhau. Sau khi xác
định được tập N(x, D, k), bộ phân lớp sẽ gán nhãn cho điểm dữ liệu x bằng lớp chiếm

Bước 3: Trích chọn đặc trưng đối tượng
Mục đích:
Mục đích của việc trích chọn đặc trưng là lựa chọn các thuộc tính của các mẫu
để xây dựng độ đo về sự khác biệt giữa các lớp mẫu. Trích chọn đặc trưng đóng vai trò
cực kỳ quan trọng trong một hệ thống nhận dạng. Đặc trưng được trích chọn phải rút
gọn lại càng nhỏ càng tốt nhưng vẫn phải đảm bảo được thông tin của ảnh.
a. Dựa vào đặc trưng hình học:
Những đặc trưng hình học thường là những vị trí đặc biệt trên khuôn mặt như
góc của mắt, miệng…hoặc là hình dáng của các bộ phận trên khuôn mặt như mắt,
miệng, lông mày…
b. Dựa vào đặc trưng diện mạo:
Xác định những thay đổi trên khuôn mặt và được áp dụng trên toàn bộ bề mặt
của bức ảnh hoặc một phần để trích ra các đặc trưng và phát hiện ra sự thay đổi của
khuôn mặt.
Một số kỹ thuật:
+ Trích chọn đặc trưng wavelet Haar.
+ Phương pháp PCA(Phân tích các thành phần chính ).
+ Phương pháp MDS(Hướng tiếp cận dựa trên diện mạo).
Bước 4: Huấn luyện:
Chọn mô hình huấn luyện phù hợp như sử dụng một trong số các kỹ thuật phân
lớp để huấn luyện ví dụ như SVM, mạng Nơron cho ra kết quả huấn luyện. Đối với
SVM sẽ cho ra các support vector của các lớp đối tượng.
Bước 5: Nhận dạng:
Quá trình nhận dạng cũng tiến hành các bước tuần tự như huấn luyện, tuy nhiên
đối tượng cần nhận dạng sau khi được trích chọn đặc trưng sẽ được sử dụng để phân
lớp dữ liệu dựa vào kết quả huấn luyện đã thực hiện trước đó. Kết quả cuối cùng là đối
tượng sẽ thuộc về lớp của một trong số đối tượng được huấn luyện trước đó hoặc
không có đối tượng nào trong dữ liệu huấn luyện.
20
1.2.4 Giới thiệu về kỹ thuật SVM, PCA, PCA-SVM

xuất sẽ là f (x, α). Việc chọn α có thể có nhiều cách khác nhau, ở đây chúng ta sẽ tiếp
cận theo phương pháp máy học.
Lỗi thử nghiệm đối với một hệ máy học đã được huấn luyện:
(1.1)
Nếu tồn tại hàm mật độ p(x,y) thì dP(x,y) có thể được viết thành dP(x,y) =
P(x,y)dxdy. Đây là cách viết khác của trung bình lỗi, nhưng trong trường hợp đã ước
lượng được P(x,y) thì cách viết này sẽ không còn ý nghĩa nữa.
21
R(α) được gọi là lỗi kì vọng, hay lỗi. Ở đây ta gọi nó là lỗi thực. Lỗi huấn luyện
(thực nghiệm) được định nghĩa là độ đo tỷ lệ lỗi trung bình xảy ra trên tập học (Ở đây
chỉ chú trọng vào trường hợp dữ liệu là hữu hạn):
(1.2)
R
emp
(α) là một giá trị tường minh tương ứng với một hệ số α riêng từ dữ liệu
huấn luyện riêng {x
i
, y
i
}.
Đại lượng được gọi là độ lệch. Trong trường hợp này, nó chỉ có thể lấy giá trị
0 và 1. Chọn η sao cho 0 ≤ η ≤ 1 và cho độ lệch nhận các giá trị này, với xác suất 1-η,
ta có:
(1.3)
h là một số nguyên không âm và còn được gọi là chiều VC (Vapnik
Chervonenkis) (VC-dimension). Gọi vế phải của (1.3) là đường bao lỗi hay biên lỗi.
Các thuật ngữ trước đây của một số nhà nghiên cứu: (Guyon et al., 1992) gọi là lỗi
được thừa nhận nhưng cách gọi này có thể gây ra một số nhầm lẫn, vì nó thực sự chỉ là
đường bao trên miền lỗi chứ không phải là giá trị chính xác của lỗi, và nó chỉ đúng ở
một xác suất nào đó nên thật sự là không đảm bảo được độ đo này là chính xác. Thuật

Định lý 1: Khảo sát tập mẫu gồm m điểm trong không gian R
n
. Chọn một điểm
bất kỳ làm điểm tọa độ gốc. Khi đó m điểm này có thể bị phân rã bằng các siêu mặt
(đường thẳng có định hướng) nếu và chỉ nếu vị trí các vector của các điểm đang đề cập
là độc lập tuyến tính (“Mangasarian, 1969”).
Hệ quả: VC-dimension cho các siêu mặt có hướng trong Rn là n+1, vì ta luôn
có thể chọn n+1 điểm dữ liệu, và sau đó chọn một điểm bất kì trong số đó làm điểm
gốc, để vị trí các vector của các điểm đang đề cập là độc lập tuyến tính.
Cực tiểu đường bao lỗi trên cơ sở cực tiểu chiều VC.
23
0.2
0.4
0.6
0.8
1.0
1.2
1.4
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
3!456%7
83!456%71 9 :
h/l = số chiều VC /số mẫu dữ liệu
Hình 1.5: Cho thấy nhóm biểu thức thứ hai bên vế phải của phương trình (1.3)
biến thiên theo số chiều h, bằng cách chọn độ tin cậy 95% (η = 0.05), tập mẫu huấn
luyện l =10,000 (mẫu). Chiều VC là hàm tăng đều theo h. Điều này đúng với bất kỳ
giá trị của l.
e. SVM tuyến tính
Trường hợp dữ liệu có thể phân cách được
Bắt đầu với trường hợp đơn giản nhất: máy học được huấn luyện trên dữ liệu có
thể phân loại tuyến tính. Gán nhãn dữ liệu huấn luyện {x

i
w + b) –1 ≥ 0 ∀i (1.6)
24
;<=>
);<=>?
<
?
;<=>@
A$B1C556DEFG"H55 FH5
Lề = 2/||w||
Các mẫu dữ liệu thỏa công thức (2.4) nằm trên siêu mặt H1: x
1
w + b = 1 có
pháp tuyến là vector w, và khoảng cách đến gốc tọa độ là |1-b|/||w||. Tương tự, các mẫu
thỏa công thức (1.5) nằm trên siêu mặt H2: x
i
w + b = -1, có pháp tuyến là w và khoảng
cách đến gốc toạ độ là |-1-b|/||w||. Khi đó, (d+) = (d-) = 1 / ||w|| và lề r = 2/||w||. Lưu ý
rằng H1 và H2 song song với nhau, và không có điểm dữ liệu nào nằm giữa chúng. Vì
vậy, ta có thể tìm cặp siêu mặt có bờ (r) cực đại, bằng việc cực tiểu ||w|| với ràng buộc
(1.6).
`
Ta mong muốn lời giải cho trường hợp không gian hai chiều có dạng như trong
Hình 1.6. Những điểm huấn luyện thoả phương trình (1.6) (tức những điểm nằm trên
một trong hai siêu mặt H1, H2), và việc loại bỏ chúng làm thay đổi lời giải, được gọi
là các vector hỗ trợ; đó là các điểm được bao bằng các hình tròn trong Hình 1.6.
Các support vector chính là các điểm được bao bằng viền tròn.
Một cách để giải quyết bài toán là dùng hàm Largange. Có hai lý do cho điều
này.
Thứ nhất là ràng buộc (1.6) sẽ được thế bằng ràng buộc trên hệ số nhân