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

MA THỊ HỒNG THU

HỌC NỬA GIÁM SÁT DỰA TRÊN
ĐỒ THỊ VÀ ỨNG DỤNG
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: PGS.TS. ĐOÀN VĂN BAN

THÁI NGUYÊN - 2015


i

LỜI CẢM ƠN

Trong quá trình làm luận văn “Học nửa giám sát dựa trên đồ thị và ứng dụng”
tôi đã nhận được sự giúp đỡ tận tình của các cá nhân và tập thể.
Trước hết, tôi xin bày tỏ lòng biết ơn sâu sắc đến thầy giáo PGS.TS Đoàn
Văn Ban, người đã tận tình hướng dẫn, chỉ bảo cho tôi trong suốt quá trình thực
hiện luận văn.
Xin cùng bày tỏ lòng biết ơn chân thành tới các thầy, cô giáo trong Viện Công
nghệ Thông tin cũng như các thầy, cô giáo trong Trường Đại học Công nghệ Thông
tin & Truyền thông Thái Nguyên, đã đem lại cho tôi những kiến thức vô cùng có ích
trong những năm học tập tại trường.

Cuối cùng tôi xin gửi lời cám ơn đến gia đình, bạn bè, đồng nghiệp những
người đã luôn bên cạnh, động viên và khuyến khích tôi trong quá trình thực hiện đề
tài nghiên cứu của mình.
Tôi xin chân thành cảm ơn!
Thái Nguyên, ngày 10 tháng 4 năm 2015


MỤC LỤC
LỜI CẢM ƠN ..........................................................................................................i
DANH MỤC HÌNH VẼ .......................................................................................... v
LỜI MỞ ĐẦU ......................................................................................................... 1
1. Lý do chọn đề tài............................................................................................................ 1
2. Mục đích nghiên cứu...................................................................................................... 2
3. Đối tượng và phạm vi nghiên cứu.................................................................................. 2
4. Tóm tắt luận điểm cơ bản............................................................................................... 2
5. Phương pháp nghiên cứu ............................................................................................... 3
6. Nội dung luận văn .......................................................................................................... 3

CHƯƠNG 1: TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP HỌC MÁY ..................... 4
1.1. Giới thiệu về học máy ................................................................................................. 4
1.2. Các phương pháp học máy.......................................................................................... 7
1.2.1. Học có giám sát .................................................................................................... 7
1.2.2. Học không giám sát.............................................................................................. 8
1.2.3. Học tăng cường .................................................................................................. 11
1.2.4. Học nửa giám sát ................................................................................................ 12
1.3. Một số phương pháp học nửa giám sát ..................................................................... 14
1.3.1. Phương pháp tự huấn luyện................................................................................ 14
1.3.2. Phương pháp đồng huấn luyện ........................................................................... 15
1.3.3. Phương pháp Máy véc tơ hỗ trợ truyền dẫn ....................................................... 18
1.3.4. Phương pháp dựa trên đồ thị .............................................................................. 22

1.4. Kết luận ..................................................................................................................... 24

CHƯƠNG 2: PHƯƠNG PHÁP HỌC NỬA GIÁM SÁT DỰA TRÊN ĐỒ THỊ .... 25
2.1. Giới thiệu .................................................................................................................. 25
2.2. Các loại đồ thị phổ biến có thể sử dụng trong học nửa giám sát .............................. 27
2.2.1. Đồ thị kết nối đầy đủ .......................................................................................... 27
2.2.2. Đồ thị rời rạc ...................................................................................................... 27
2.2.3. Đồ thị

-láng giềng gần nhất ............................................................................ 28

2.2.4. Đồ thị -láng giềng gần nhất ............................................................................. 28
2.2.5. Đồ thị trọng số exp ............................................................................................ 29


2.3. Các phương pháp xác định khoảng cách giữa các điểm dữ liệu ............................... 29
2.3.1. Khoảng cách cục bộ, khoảng cách toàn cục và trọng số .................................... 29
2.3.2. Khoảng cách Hamming ...................................................................................... 30
2.3.3. Khoảng cách Manhattan cho các thuộc tính số học ........................................... 30
2.3.4. Các hàm khoảng cách cục bộ không đồng nhất ................................................. 31
2.3.5. Hàm khoảng cách tri thức chuyên gia ................................................................ 31
2.4. Thuật toán lan truyền nhãn trong đồ thị .................................................................... 32
2.4.1. Ký hiệu ............................................................................................................... 32
2.4.2. Nội dung thuật toán ............................................................................................ 33
2.4.3. Sự hội tụ của thuật toán ...................................................................................... 34
2.4.4. Phương pháp xác định siêu tham số của đồ thị .................................................. 36
2.4.5. Độ phức tạp của thuật toán................................................................................. 38
2.5. Thuật toán học nửa giám sát dựa trên đồ thị - Mincut .............................................. 38
2.6. Các trường Gaussian ngẫu nhiên và các hàm điều hòa ............................................. 40
2.6.1. Các trường Gaussian ngẫu nhiên........................................................................ 40

2.6.2. Đồ thị Laplacian ................................................................................................. 42
2.6.3. Các hàm điều hòa ............................................................................................... 43
2.7. Đánh giá .................................................................................................................... 44
2.8. Kết luận chương ........................................................................................................ 44

CHƯƠNG 3: CÀI ĐẶT VÀ THỬ NGHIỆM THUẬT TOÁN ............................... 45
3.1. Mô tả bài toán ........................................................................................................... 45
3.2. Mô tả dữ liệu đầu vào ............................................................................................... 45
3.3. Trích chọn đặc trưng ................................................................................................. 47
3.4. Cài đặt và thử nghiệm ............................................................................................... 50
Môi trường cài đặt và thử nghiệm ................................................................................ 50
Các chức năng của chương trình .................................................................................. 51
3.5. Kết quả thực nghiệm và đánh giá độ phức tạp.......................................................... 54
3.6. Kết luận ..................................................................................................................... 56

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.............................................................. 57
TÀI LIỆU THAM KHẢO ..................................................................................... 58


DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT
Thuật ngữ

Viết tắt

Ý nghĩa

Concept

Concept


Khái niệm

Self-training

Self-training

Tự huấn luyện

Co-training

Co-training

Đồng huấn luyện

Machine learning

Machine learning

Học máy

Supervised learning

Supervised learning

Học có giám sát

Unsupervised learning

Unsupervised learning


Học không giám sát

Reinforcement learning

Reinforcement learning

Học tăng cường

Semi-supervised learning
Support vector machine
Transductive support
vector machine

Semi-supervised
learning
SVM
TSVM

Học nửa giám sát
Máy véc tơ hỗ trợ
Máy véc tơ hỗ trợ truyền
dẫn

Labeled Propagation

Labeled Propagation

Lan truyền nhãn

Graph-based


Graph-based

Dựa trên đồ thị


DANH MỤC HÌNH VẼ
Hình 1.1: Phương pháp phân cụm dữ liệu. ............................................................... 9
Hình 1.2: Khung nhìn dữ liệu giữa văn bản và liên kết .......................................... 17
Hình 1.3: Dữ liệu được học theo phương pháp Co-training. ................................... 18
Hình 1.4: Phương pháp Máy véc tơ hỗ trợ ............................................................. 19
Hình 1.5: Phương pháp máy vecto hỗ trợ truyền dẫn ............................................. 22
Hình 1.6: Minh họa đồ thị được gán nhãn .............................................................. 23
Hình 2.1: Phương pháp dựa trên đồ thị .................................................................. 25
Hình 2.2: Đồ thị kết nối đầy đủ.............................................................................. 27
Hình 2.3: Đồ thị rời rạc.......................................................................................... 27
Hình 2.4: Đồ thị

-láng giềng gần nhất ................................................................ 28

Hình 2.5: Đồ thị -láng giềng gần nhất .................................................................. 28
Hình 2.6: Trọng số cạnh giữa hai đỉnh của đồ thị ................................................... 29
Hình 2.7: Đồ thị với các trọng số cạnh ................................................................... 32
Hình 3.1: Tệp dữ liệu tin nhắn mẫu ....................................................................... 45
Hình 3.2: Nội dung tin nhắn được chuyển thành dạng vector ................................ 46
Hình 3.3: Nội dung file dữ liệu dạng vector .......................................................... 47
Hình 3.4: Trích chọn đặc trưng ............................................................................ 48
Hình 3.5: Trích chọn thuộc tính cho file đầu vào của chương trình ....................... 49
Hình 3.6: Dữ liệu của chương trình....................................................................... 49
Hình 3.7: Dữ liệu của chương trình mở bằng Notepad .......................................... 50

Hình 3.8: Giao diện chọn tệp dữ liệu .................................................................... 51
Hình 3.9: Kết quả khi lựa chọn phương pháp tự huấn luyện.................................. 52
Hình 3.10: Giao diện đồ thị lan truyền nhãn trước khi thực hiện ........................... 53
Hình 3.11: Giao diện đồ thị lan truyền nhãn sau khi thực hiện .............................. 54
Hình 3.12: Kết quả đồ thị sau khi được gán nhãn ở dạng đồ thị ............................ 54


1

LỜI MỞ ĐẦU
1. Lý do chọn đề tài
Học máy (Machine learning) là một ngành khoa học nghiên cứu các kĩ thuật,
các phương pháp cho phép các máy tính có khả năng "học" giống như con người.
Hay nói một cách khác cụ thể hơn, học máy là một phương pháp để tạo ra các
chương trình máy tính bằng việc phân tích các tập dữ liệu, qua đó máy tính có khả
năng tích lũy được tri thức thông qua việc học được các khái niệm để có thể ra
quyết định trong các trường hợp tương tự.
Lĩnh vực học máy truyền thống thường được chia thành bốn lĩnh vực con,
bao gồm: Học có giám sát (Supervised learning), Học không giám sát
(Unsupervised learning), Học nửa giám sát (Semi-Supervised learning) và Học tăng
cường (Reinforcement learning).
Học nửa giám sát sử dụng cả dữ liệu đã gán nhãn và chưa gán nhãn để huấn
luyện - điển hình là một lượng nhỏ dữ liệu có gán nhãn cùng với lượng lớn dữ liệu
chưa gán nhãn. Học nửa giám sát đứng giữa học không giám sát (không có bất kì dữ
liệu có nhãn nào) và có giám sát (toàn bộ dữ liệu đều được gán nhãn). Để gán nhãn
dữ liệu cho một bài toán học máy thường đòi hỏi một phân loại bằng tay các ví dụ
huấn luyện. Chi phí cho quy trình này khiến tập dữ liệu được gán nhãn hoàn toàn
trở nên không khả thi, trong khi dữ liệu không gán nhãn thường có chi phí thấp.
Trong tình huống đó, học nửa giám sát có giá trị thực tiễn lớn lao. Chính vì vậy, học
nửa giám sát là sự kết hợp một số lượng lớn các dữ liệu chưa được gán nhãn cùng

với các dữ liệu đã được gán nhãn để xây dựng các bộ phân lớp tốt hơn.
Một số phương pháp điển hình trong lĩnh vực này được kể đến như: Phương
pháp EM với mô hình sinh hỗn hợp (EM with generative mixture models), phương
pháp Tự huấn luyện (Self-training), phương pháp Đồng huấn luyện (Co-training),
phương pháp máy véc tơ hỗ trợ (Transductive support vector machines) và phương
pháp Dựa trên đồ thị (Graph-based). Trong đó phương pháp học nửa giám sát dựa
trên đồ thị (Graph-based) đang là hướng nghiên cứu mở và đem lại hiệu quả lớn.
Với những lý do trên, tác giả đã chọn đề tài “Học nửa giám sát dựa trên đồ


thị và ứng dụng” làm đề tài nghiên cứu luận văn tốt nghiệp thạc sĩ chuyên ngành
Khoa học máy tính.
2. Mục đích nghiên cứu
Nghiên cứu tổng quan về học nửa giám sát và một số phương pháp học nửa
giám sát.
Nghiên cứu phương pháp học nửa giám sát dựa trên đồ thị
Cài đặt thử nghiệm thuật toán lan truyền nhãn trên đồ thị và thuật toán tự
huấn luyện.
3. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu: Học nửa giám sát.
Phạm vi nghiên cứu:
- Nghiên cứu tổng quan về học có giám sát, học không giám sát và học nửa
giám sát.
- Các phương pháp học nửa giám sát phổ biến.
- Phương pháp học nửa giám sát dựa trên đồ thị (Graph-based) và một số
thuật toán.
- Cài đặt thử nghiệm thuật toán lan truyền nhãn trong phương pháp học nửa
giám sát dựa trên đồ thị và thuật toán tự huấn luyện.
4. Tóm tắt luận điểm cơ bản
Các luận điểm chính mà luận văn đã thể hiện được:

Nghiên cứu tổng quan và đánh giá các phương pháp học nửa giám sát, tập
trung vào phương pháp học nửa giám sát dựa trên đồ thị.
Tập trung tìm hiểu một số thuật toán trong lĩnh vực học nửa giám sát như:
Phương pháp EM với mô hình sinh hỗn hợp, phương pháp Tự huấn luyện, phương
pháp Đồng huấn luyện và phương pháp máy véc tơ hỗ trợ. Đồng thời tập trung
nghiên cứu chi tiết phương pháp dựa trên đồ thị.
Cài đặt phần mềm thử nghiệm mô phỏng thuật toán lan truyền nhãn và thuật
toán tự huấn luyện, đánh giá độ phức tạp của hai thuật toán này.


5. Phương pháp nghiên cứu
- Đọc tài liệu, phân tích, tổng hợp.
- Thống kê, phân tích dữ liệu.
- Thực nghiệm và đánh giá kết quả.
- Kết hợp nghiên cứu lý thuyết, tìm hiểu tình hình ứng dụng, đánh giá khả
năng ứng dụng và đề xuất giải pháp.
6. Nội dung luận văn
Nội dung luận văn gồm 03 chương:


Chương 1: Tổng quan về các phương pháp học máy
Chương này trình bày tổng quan về các phương pháp học máy gồm
phương pháp Học có giám sát (Supervised learning), Học không giám sát
(Unsupervised learning), Học nửa giám sát (Semi-Supervised learning).



Chương 2: Phương pháp học nửa giám sát dựa trên đồ thị
Tập trung tìm hiểu một số thuật toán trong lĩnh vực học nửa giám sát như:
Phương pháp EM với mô hình sinh hỗn hợp, phương pháp Tự huấn

luyện, phương pháp Đồng huấn luyện và phương pháp máy véc tơ hỗ trợ.
Đồng thời tập trung nghiên cứu chi tiết phương pháp dựa trên đồ thị.



Chương 3: Cài đặt và thử nghiệm thuật toán
Cài đặt thử nghiệm thuật toán tự huấn luyện và lan truyền nhãn dựa trên
đồ thị, đánh giá độ phức tạp của hai thuật toán này.


CHƯƠNG 1:
TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP HỌC MÁY
1.1. Giới thiệu về học máy
Học máy (Machine Learning) là một ngành khoa học nghiên cứu các thuật
toán cho phép máy tính có thể học được các khái niệm (concept)[7].
Có hai loại phương pháp học máy chính:


Phương pháp quy nạp: Máy học/phân biệt các khái niệm dựa trên dữ liệu đã

thu thập được trước đó. Phương pháp này cho phép tận dụng được nguồn dữ liệu rất
nhiều và sẵn có.


Phương pháp suy diễn: Máy học/phân biệt các khái niệm dựa vào các luật.

Phương pháp này cho phép tận dụng được các kiến thức chuyên ngành để hỗ trợ
máy tính.
Hiện nay, các thuật toán đều cố gắng tận dụng được ưu điểm của hai phương
pháp này.

Các ngành khoa học liên quan đến lĩnh vực học máy điển hình là:


Lý thuyết thống kê: các kết quả trong xác suất thống kê là tiền đề cho rất

nhiều phương pháp học máy. Đặc biệt, lý thuyết thống kê cho phép ước lượng sai số
của các phương pháp học máy.


Các phương pháp tính: các thuật toán học máy thường sử dụng các tính toán

số thực/số nguyên trên dữ liệu rất lớn. Trong đó, các bài toán như: tối ưu có/không
ràng buộc, giải phương trình tuyến tính v.v… được sử dụng rất phổ biến.


Khoa học máy tính: là cơ sở để thiết kế các thuật toán, đồng thời đánh giá

thời gian chạy, bộ nhớ của các thuật toán học máy.


Lĩnh vực học máy truyền thống thường được chia thành bốn lĩnh vực con:



Học có giám sát: Máy tính được xem một số mẫu gồm đầu vào và đầu

ra tương ứng trước. Sau khi học xong các mẫu này, máy tính quan sát một đầu vào
mới và cho ra kết quả.



Học không giám sát: Máy tính chỉ được xem các mẫu không có đầu ra, sau

đó máy tính phải tự tìm cách phân loại các mẫu này và các mẫu mới.




Học nửa giám sát: Một dạng lai giữa hai nhóm giải thuật trên.



Học tăng cường: Máy tính đưa ra quyết định hành động và nhận kết quả phản

hồi từ môi trường. Sau đó máy tính tìm cách chỉnh sửa cách ra quyết định hành
động của mình.
Học máy có ứng dụng rộng khắp trong các ngành khoa học/sản xuất, đặc biệt
những ngành cần phân tích khối lượng dữ liệu khổng lồ. Một số ứng dụng thường thấy:


Xử lý ngôn ngữ tự nhiên (Natural Language Processing): xử lý văn bản, giao

tiếp người – máy, …


Nhận dạng (Pattern Recognition): nhận dạng tiếng nói, chữ viết tay, vân tay,

thị giác máy (Computer Vision) …


Tìm kiếm (Search Engine)




Chẩn đoán trong y tế: phân tích ảnh X-quang, các hệ chuyên gia chẩn đoán

tự động.


Tin sinh học: phân loại chuỗi gene, quá trình hình thành gene/protein



Vật lý: phân tích ảnh thiên văn, tác động giữa các hạt …



Phát hiện gian lận tài chính (financial fraud): gian lận thẻ tỉn dụng



Phân tích thị trường chứng khoán (stock market analysis)



Chơi trò chơi: tự động chơi cờ, hành động của các nhân vật ảo



Rôbốt: là tổng hợp của rất nhiều ngành khoa học, trong đó học máy tạo nên


hệ thần kinh/bộ não của người máy.
Trong đó phải kể đến các ứng dụng quan trọng nhất của nó trong khai phá dữ
liệu. Khai phá dữ liệu (Data mining) là quá trình khám phá các tri thức mới và các
tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có. Khai phá dữ liệu là một
bước của quá trình khai phá tri thức, bao gồm:


Xác định vấn đề và không gian dữ liệu để giải quyết vấn đề.



Chuẩn bị dữ liệu, bao gồm các quá trình làm sạch dữ liệu, tích hợp dữ liệu,

chọn dữ liệu, biến đổi dữ liệu.


Khai phá dữ liệu: xác định nhiệm vụ khai phá dữ liệu và lựa chọn kĩ thuật

khai phá dữ liệu. Kết quả cho ta một nguồn tri thức thô.




Đánh giá: dựa trên một số tiêu chí tiến hành kiểm tra và lọc nguồn tri thức

thu được.


Triển khai.
Quá trình khai phá tri thức không chỉ là một quá trình tuần tự từ bước đầu


tiên đến bước cuối cùng mà là một quá trình lặp và có quay trở lại các bước đã qua.
Về cơ bản, khai phá dữ liệu có thể ứng dụng cho bất kỳ kho thông tin nào
bao gồm: Các cơ sở dữ liệu quan hệ, kho dữ liệu, các cơ sở dữ liệu giao tác, các hệ
thống cơ sở dữ liệu tiên tiến, các tệp, ...
Phân lớp dữ liệu
Phân lớp dữ liệu là kĩ thuật dựa trên tập dữ liệu huấn luyện và những giá trị
trong một thuộc tính phân lớp (hay còn gọi là nhãn của lớp), sử dụng nó trong việc
phân lớp dữ liệu mới. Phân lớp cũng là tiên đoán loại lớp của nhãn. Bên cạnh kĩ
thuật phân lớp còn có một hình thức tương tự gọi là kĩ thuật tiên đoán, kĩ thuật tiên
đoán khác với phân lớp ở chỗ phân lớp chỉ liên quan đến tiên đoán loại lớp của nhãn
còn kĩ thuật tiên đoán mô hình những hàm đánh giá liên tục[6].
Kĩ thuật phân lớp được tiến hành bao gồm 2 bước: Xây dựng mô hình và sử
dụng mô hình.
Xây dựng mô hình: là mô tả một tập những lớp được định nghĩa trước, trong
đó mỗi bộ hoặc mẫu được gán thuộc về một lớp được định nghĩa trước như là được
xát định bởi thuộc tính nhãn lớp, tập hợp của những bộ được sử dụng trong việc sử
dụng mô hình được gọi là tập huấn luyện. Mô hình được biểu diễn là những luật
phân lớp, cây quyết định và những công thức toán học .
Sử dụng mô hình: việc sử dụng mô hình phục vụ cho mục đích phân lớp dữ
liệu trong tương lai hoặc phân lớp cho những đối tượng chưa biết đến. Trước khi sử
dụng mô hình người ta thường phải đánh giá tính chính xác của mô hình, trong đó
nhãn được biết của mẫu kiểm tra được so sánh với kết quả phân lớp của mô hình, độ
chính xác là phần trăm của tập hợp mẫu kiểm tra mà phân loại đúng bởi mô hình,
tập kiểm tra là độc lập với tập huấn luyện.
Phân lớp là một hình thức học có giám sát, tức là: tập dữ liệu huấn luyện


(quan sát, thẩm định ...) đi đôi với những nhãn chỉ định lớp quan sát, những
dữ liệu mới được phân lớp dựa trên tập huấn luyện này.

Trong phương pháp học máy truyền thống, để phân lớp dữ liệu ta chỉ sử
dụng một tập dữ liệu đã được gán nhãn để huấn luyện. Tuy nhiên, để có được các
mẫu dữ liệu đã được gán nhãn thường khó khăn, tốn kém thời gian và chi phí hay
nó đòi hỏi những nỗ lực của các chuyên gia. Trong khi đó, dữ liệu chưa được gán
nhãn có thể sưu tầm tương đối dễ dàng, và có một số phương pháp để sử dụng
chúng. Học nửa giám sát đề cập tới vấn đề này bằng cách sử dụng một số lượng lớn
các dữ liệu chưa được gán nhãn cùng với các dữ liệu đã được gán nhãn để xây dựng
các bộ phân lớp tốt hơn. Do học nửa giám sát đòi hỏi nỗ lực của con người ít hơn và
đưa ra độ chính xác cao, đó là sự quan tâm lớn cả về lý thuyết và thực hành.
Để hiểu bản chất của học nửa giám sát, ta sẽ xem xét các khái niệm về học
có giám sát, học không giám sát và học tăng cường.
1.2. Các phương pháp học máy
1.2.1. Học có giám sát
Học có giám sát là một kỹ thuật của ngành học máy nhằm mục đích xây
dựng một hàm f từ dữ tập dữ liệu huấn luyện (Training data). Dữ liệu huấn
luyện bao gồm các cặp đối tượng đầu vào và đầu ra mong muốn. Đầu ra của hàm f
có thể là một giá trị liên tục hoặc có thể là dự đoán một nhãn phân lớp cho một đối
tượng đầu vào[8].
Nhiệm vụ của chương trình học có giám sát là dự đoán giá trị của hàm f cho
một đối tượng đầu vào hợp lệ bất kì, sau khi đã xét một số mẫu dữ liệu huấn luyện
(nghĩa là các cặp đầu vào và đầu ra tương ứng). Để đạt được điều này, chương trình
học phải tổng quát hóa từ các dữ liệu sẵn có để dự đoán được những tình huống
chưa gặp phải theo một cách hợp lý.
Phương pháp học có giám sát có thể được mô tả tóm tắt như sau:
Hệ thống học sẽ quan sát một tập dữ liệu huấn luyện đã được gán nhãn, bao
gồm các cặp (đặc tính, nhãn), được biểu diễn bởi {(x1, y1), (x2, y2), ..., (xn, yn)}.
Mục đích nhằm dự đoán nhãn y cho bất kỳ đầu vào mới với đặc tính x. Một nhiệm


vụ của học có giám sát được gọi là hồi quy khi y ∈


và phân lớp khi y có một tập

các giá trị rời rạc.
Để giải quyết bài toán học có giám sát, ta phải thực hiện các bước sau:
1. Xác định loại dữ liệu huấn luyện: Đầu tiên ta nên xác định xem loại dữ liệu
nào sẽ được sử dụng làm dữ liệu huấn luyện. Chúng có thể là dữ liệu liên tục hay dữ
liệu rời rạc, hoặc một dạng đặt biệt nào đó.
2. Xây dựng tập dữ liệu huấn luyện: Việc thu thập để tạo nên tập dữ liệu huấn
luyện là quan trọng vì nó sẽ phục vụ cho việc sử dụng hàm huấn luyện f. Dữ liệu
huấn luyện có thể thu thập được từ nhiều nguồn khác nhau: dữ liệu đầu vào, số liệu
đo đạc, tri thức hay kinh nghiệm của các chuyên gia lĩnh vực,…
3. Biễu diễn các đặc trưng đầu vào: Sự chính xác của hàm chức năng phụ thuộc
lớn vào cách các đối tượng đầu vào được biểu diễn. Thông thường, đối tượng đầu
vào được chuyển đổi thành một vec-tơ đặc trưng, chứa một số các đặc trưng nhằm
mô tả cho đối tượng đó. Số lượng các đặc trưng không nên quá lớn nhưng phải đủ
lớn để việc dự đoán đầu ra được chính xác.
4. Xác định cấu trúc của hàm chức năng cần tìm và giải thuật học tương ứng.
Ví dụ, có thể lựa chọn việc sử dụng giải thuật K-láng giềng gần nhất hay giải thuật
cây quyết định,…
5. Hoàn thiện thiết kế. Người kĩ sư sẽ chạy giải thuật học từ tập huấn luyện thu
thập được. Các tham số của giải thuật học có thể được điều chỉnh bằng cách tối ưu
hóa hiệu năng trên một tập con (gọi là tập kiểm chứng -validation set) của tập huấn
luyện, hay thông qua kiểm chứng chéo (cross-validation). Sau khi học và điều chỉnh
tham số, hiệu năng của giải thuật có thể được đo đạc trên một tập kiểm tra độc lập
với tập huấn luyện.
Các thuật toán sử dụng trong học có giám sát như: Cây quyết định (Decision Trees),
Máy véc tơ hỗ trợ (Support Vector Machine (SVM)), k-láng giềng gần nhất (kNearest Neighbor), Cực đại Entropy (Maximum Entropy (MaxEnt)), Naive Bayes,...
1.2.2. Học không giám sát
Học không giám sát là một phương pháp của ngành học máy nhằm tìm ra



một mô hình phù hợp với các quan sát. Nó khác với học có giám sát ở chỗ là đầu ra
đúng tương ứng cho mỗi đầu vào là không biết trước. Trong học không giám sát,
một tập dữ liệu đầu vào được thu thập. Học không giám sát thường đối xử với các
đối tượng đầu vào như là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật
độ kết hợp sẽ được xây dựng cho tập dữ liệu đó[8].
Học không giám sát có thể được dùng kết hợp với suy diễn Bayes (Bayesian
inference) để cho ra xác suất có điều kiện (nghĩa là học có giám sát) cho bất kì biến
ngẫu nhiên nào khi biết trước các biến khác.
Học không giám sát cũng hữu ích cho việc nén dữ liệu: về cơ bản, mọi giải
thuật nén dữ liệu hoặc là dựa vào một phân bố xác suất trên một tập đầu vào một
cách tường minh hoặc không tường minh.
Phân cụm dữ liệu
Một ứng dụng khác của học không giám sát là phân cụm dữ liệu (data
clustering). Phân cụm được xem như vấn đề quan trọng nhất trong học không giám
sát, vì như các vấn đề khác của phân cụm dữ liệu, nó có liên quan tới việc tìm kiếm
một cấu trúc trong một tập các dữ liệu không có nhãn[3].
Một định nghĩa rộng hơn về phân cụm: “ phân cụm là quá trình tổ chức các
đối tượng dữ liệu vào trong các nhóm trong đó các đối tượng giống nhau theo một
cách nào đó”. Do đó, một cụm là một tập hợp các đối tượng mà giữa chúng có sự
giống nhau và khác với các đối tượng thuộc về các cụm khác.

Hình 1.1: Phương pháp phân cụm dữ liệu.
Trong ví dụ trên, chúng ta có thẻ dễ dàng xác định được 4 cụm mà trong đó


dữ liệu được phân chia. Tiêu chí giống nhau ở đây là “khoảng cách”, hai hay nhiều
đối tượng thuộc về một cụm nếu chúng gần nhau hơn dựa theo khoảng cách đưa ra.
Điều này gọi là phân cụm dựa trên khoảng cách.

Một dạng khác của phân cụm là Phân cụm khái niệm, hai hay nhiều đối
tượng thuộc về một cụm nếu ta định nghĩa một khái niệm phổ biến cho tất cả các
đối tượng. Tóm lại, các đối tượng được nhóm lại theo điều kiện mô tả chúng.
Mục đích của phân cụm dữ liệu
Mục đích của việc phân cụm dữ liệu là để xác định các nhóm trong một tập
các dữ liệu không có nhãn. Nhưng làm thế nào để quyết định được điều gì tạo nên
việc phân cụm tốt. Có thể nói rằng, không có một tiêu chuẩn tuyệt đối nào là tốt
nhất, do đó người sử dụng phải đưa ra các tiêu chuẩn này để các dữ liệu sau khi
được phân cụm sẽ phù hợp với yêu cầu của người sử dụng.
Các ứng dụng của Phân cụm dữ liệu
Các thuật toán phân cụm dữ liệu có thể áp dụng trong nhiều lĩnh vực, ví dụ như:
 Tiếp thị: việc tìm ra các nhóm khách hàng có hành vi giống nhau sẽ đưa ra
một CSDL lớn chứa thông tin khách hàng và thông tin mua sắm của họ.
 Sinh học: phân loại động vật và thực vật dựa trên các đặc trưng của chúng
 Thư viện: đặt sách
 www: phân lớp văn bản, phân cụm dữ liệu weblog để xác định các nhóm
người truy cập tương tự nhau.
Các yêu cầu với thuật toán phân cụm:
Các yêu cầu chính mà một thuật toán phân cụm cần đáp ứng là:
 Khả năng mở rộng
 Đối xử với các loại thuộc tính khác nhau của đối tượng dữ liệu
 Phát hiện ra các cụm với hình dạng có thể là bất kỳ.
 Tối thiểu hóa yêu cầu cho miền tri thức để xác định các tham số đầu vào.
 Khả năng xử lý các dữ liệu tạp và sự chênh lệch,...
Các thuật toán được sử dụng phổ biến nhất hiện nay: K-means, Fuzzy C-means,
Phân cụm có thứ bậc, Hỗn hợp Gaussian.


1.2.3. Học tăng cường
Học tăng cường là một lĩnh vực con của ngành học máy, nghiên cứu cách

thức để một Agent nên chọn thực hiện các hành động nào trong một “môi
trường” để cực đại hóa số “phần thưởng” nào đó. “Môi trường” trong học tăng
cường được biểu diễn dưới dạng một quá trình trạng thái quyết định hữu hạn
Markov (Markov decision process – MDP)[8].
Cụ thể hơn, trong học tăng cường, các Agent tương tác với môi trường của
nó bằng cách đưa ra các hành động a1, a2, ... Những hành động này ảnh hưởng tới
trạng thái của môi trường do đó kết quả nhận được trong Agent lần lượt là số phần
thưởng hoặc hình phạt r1, r2,... Mục đích của Agent là học một hành động trong một
cách nào đó để cực đại hóa thuộc tính phần thưởng nó nhận được (hay cực tiểu hóa
rủi ro) trên vòng đời của nó.
Khác với học có giám sát, học tăng cường không có các cặp dữ liệu vào hay
kết quả đúng, các hành động gần tối ưu cũng không được đánh giá đúng sai một
cách tường minh.
Mô hình học tăng cường[9] bao gồm các thành phần sau:
-

Tập các trạng thái môi trường, ký hiệu là: S

-

Tập các hành động, ký hiệu là: A

-

Tập các phần thưởng, ký hiệu:

Quá trình học như sau:
Tại mỗi thời điểm t, Agent có trạng thái môi trường là st ∈ S và tập các hành
động có thể chọn A(st). Nó chọn một hành động a ∈ A(st) và nhận được từ môi
trường một trạng thái mới st+1 và một phần thưởng rt+1. Với việc học như vậy, agent

phải phát triển một hàm học π: S → A có tác dụng cực đại hóa số lượng phần
thưởng thu được: R = r0 + r1 + .. + rn với các MDP có một trạng thái kết thúc, hoặc
lượng R = Σtγtrt với các MDP không có trạng thái kết thúc (trong đó γ là một hệ số
giảm " phần thưởng trong tương lai" nào đó, với giá trị trong khoảng từ 0 đến 1).
Học tăng cường có liên quan mật thiết với lý thuyết quyết định và lý thuyết
điều khiển, do đó được áp dụng trong các bài toán như: điều khiển rô bốt, điều vận


thang máy, trò chơi cờ vua, ...
Ví dụ về học tăng cường:


Một kỳ thủ cờ vua muốn đi một nước cờ. Sự lựa chọn được đưa ra sẽ dựa

trên cả việc lập kế hoạch cho nước cờ mình đi, dự đoán các nước cờ tiếp theo của
đối thủ và xác định số nước cờ của đối thủ sẽ đi một cách tức thì.


Một con rô bốt di động quyết định có nên đi vào một căn phòng mới để tìm

kiếm đường về trạm sạc pin của nó. Nó đưa ra quyết định dựa trên việc làm thế nào
để có thể tìm được trạm sạc pin trong quá khứ một cách nhanh chóng và dễ dàng.
1.2.4. Học nửa giám sát
1.2.4.1. Tổng quan về học nửa giám sát
Ban đầu, học nửa giám sát giả sử có hai lớp và mỗi lớp có một phân phối
Gaussian. Điều này giả sử rằng dữ liệu hoàn chỉnh xuất phát từ một mô hình hỗn
hợp. Với số lượng lớn các dữ liệu chưa gán nhãn, các thành phần hỗn hợp có thể
được xác định với thuật toán EM (Expectation-Maximization). Thuật toán này chỉ
cần một mẫu dữ liệu đã gán nhãn trong số các thành phần để xác định đầy đủ mô
hình hỗn hợp. Mô hình này đã được áp dụng thành công để phân loại văn bản.

Một biến thể khác là phương pháp tự huấn luyện (Self-traning): Một bộ phân
lớp ban đầu huấn luyện với các dữ liệu đã gán nhãn. Sau đó nó được sử dụng để
phân lớp các dữ liệu chưa gán nhãn. Các điểm chưa được gán nhãn cùng với các
nhãn đã được dự đoán sẽ được thêm vào tập huấn luyện. Bộ phân lớp sẽ huấn luyện
lại và quá trình này được lặp đi lặp lại. Lưu ý rằng, bộ phân lớp sử dụng các dự
đoán của nó để dạy chính bản thân nó. Có một phiên bản khó của mô hình hỗn hợp
và thuật toán EM. Phương thức đó cũng được gọi là “Tự dạy” hay bootstrapping.
Nó cho rằng lỗi phân lớp có thể tăng cường cho nó.
Cả hai phương pháp đã được sử dụng từ lâu nhưng vẫn phổ biến vì khái niệm
và thuật toán của chúng đơn giản.
Phương pháp Co-training làm giảm các lỗi của phương pháp Self-training.
Phương pháp này giả sử rằng các đặc tính của một mẫu dữ liệu có thể được chia
thành hai tập con. Mỗi tập con đặc tính đủ để huấn luyện một bộ phân lớp tốt, và tập


con thứ hai là điều kiện độc lập để đưa ra phân lớp. Ban đầu, hai bộ phân lớp huấn
luyện với dữ liệu đã gán nhãn, mỗi bộ huấn luyện trên một tập con. Mỗi bộ phân
lớp sau đó lặp lại việc phân lớp với dữ liệu chưa gán nhãn và dạy bộ phân lớp khác
với các dự đoán của nó.
Phương pháp TSVM (Transductive Support Vector Machine) được biết đến
như việc mở rộng để chuẩn hóa SVM cho lĩnh vực học nửa giám sát. TSVM tìm
một cách gán nhãn cho tất cả các dữ liệu chưa gán nhãn và sự phân chia đồng đều,
ví dụ như lề cực đại đạt được trên cả dữ liệu đã gán nhãn và dữ liệu chưa gán nhãn.
Phương pháp học nửa giám sát dựa trên đồ thị (Graph-based) hiện nay đã thu
hút số lượng lớn các nhà nghiên cứu. Các phương pháp học nửa giám sát dựa trên
đồ thị bắt đầu với một đồ thị mà tại đó các đỉnh là các điểm dữ liệu đã được gán
nhãn và chưa được gán nhãn, và các cạnh (có trọng số) phản ánh sự tương tự của
các đỉnh. Giả sử, các đỉnh được kết nối với nhau bởi một cạnh có trọng số lớn thì có
khuynh hướng có cùng nhãn, các nhãn có thể lan truyền thông qua đồ thị. Các giải
thuật dựa trên đồ thị được thừa hưởng từ lý thuyết quang phổ đồ thị[10].

1.2.4.2. Bài toán học nửa giám sát
Học nửa giám sát là một trong số các kỹ thuật học máy, sử dụng cả dữ liệu
đã được gán nhãn và dữ liệu chưa được gán nhãn cho việc huấn luyện, điển hình là
một tập hợp nhỏ dữ liệu được gán nhãn kết hợp với một số lượng lớn các dữ liệu
chưa gán nhãn. Học nửa giám sát nằm giữa học không giám sát và học có giám sát.
Nhiều nhà nghiên cứu về học máy đã tìm ra dữ liệu chưa được gán nhãn trong khi
kết hợp với một lượng nhỏ dữ liệu đã được gán nhãn. Việc thu được dữ liệu gán
nhãn cho bài toán học thường yêu cầu kỹ năng cao của con người để tự phân loại dữ
liệu huấn luyện. Các chi phí liên quan tới quá trình gán nhãn có thể làm cho một tập
dữ liệu gán nhãn không khả thi, trong khi mua lại dữ liệu không có nhãn chi phí
tương thấp. Do đó, học nửa giám sát có thể mang lại giá trị thực tiễn lớn.
Với ý tưởng như vậy, học nửa giám sát được áp dụng cho việc phân lớp dữ
liệu. Trong bài toán phân lớp dữ liệu nửa giám sát, các mẫu dữ liệu có đặc tính
tương tự nhau thì sẽ được phân vào cùng một lớp. Ta có thể mô tả khái quát bài


toán phân lớp nhị phân như sau:
•

Cho tập dữ liệu: X = {x1..xℓ, xℓ+1..xn}  Rm

•

Tập các nhãn: L = {0,1}

•

Ban đầu, các dữ liệu đã được gán nhãn yi {0,1}, i=1,..,ℓ

•


Với các dữ liệu từ xℓ+1..xn , các nhãn yi là chưa biết.
Mục đích của bài toán là gán nhãn cho các dữ liệu chưa có nhãn dựa trên tập

dữ liệu đã cho.
1.3. Một số phương pháp học nửa giám sát
1.3.1. Phương pháp tự huấn luyện
Tự huấn luyện (Self-training) là một phương pháp phổ biến ra đời vào những
năm 1960 đến 1970, được sử dụng trong lĩnh vực học nửa giám sát. Trong phương
pháp này, một bộ phân lớp ban đầu sẽ huấn luyện số lượng ít các dữ liệu đã gán
nhãn. Bộ phân lớp sau đó được sử dụng để phân lớp cho các dữ liệu chưa gán nhãn.
Thông thường các điểm chưa gán nhãn cùng với các nhãn dự đoán của chúng sẽ
được thêm vào tập dữ liệu huấn luyện. Bộ phân lớp huấn luyện lại và quá trình này
được lặp lại. Lưu ý rằng bộ phân lớp sử dụng dự đoán của nó để dạy cho chính nó.
Quá trình này cũng được gọi là self-teaching hay bootstrapping[9].
Thuật toán Self-training:
Đầu vào : - Tập dữ liệu đã gán nhãn {(xi, yi)}ℓi=1.
- Tập dữ liệu chưa gán nhãn {(xj)}ℓ+uj= ℓ+1.
Thuật toán :
1. Khởi tạo, đặt L={(xi, yi)}ℓi=1 , và U={(xj)}ℓ+uj= ℓ+1.
2. Lặp:
3. Huấn luyện f từ tập L sử dụng một phương pháp học có giám sát.
4. Dự đoán nhãn cho các phần tử x ∈ U.
5. Bỏ đi tập con S từ tập U chứa các dữ liệu vừa được gán nhãn, đồng
thời thêm vào tập L các mẫu dữ liệu này và nhãn của chúng (thêm {(x,
f(x))| xϵS} vào L).
Ưu điểm:


-


Là phương pháp học nửa giám sát đơn giản nhất.

-

Được xem như là phương pháp “Bao trùm” (Wrapper), áp dụng cho các bộ
phân lớp sẵn có.

-

Thường được ứng dụng trong thực tế vào việc xử lý ngôn ngữ tự nhiên, phân
lớp văn bản,…

Độ phức tạp của thuật toán
Giả sử dữ liệu đầu vào bao gồm:
ℓ: số lượng dữ liệu đã gán nhãn.
u: số lượng dữ liệu chưa gán nhãn (u ≫ ℓ).
n = ℓ + u : tổng số lượng dữ liệu.
Độ phức tạp của thuật toán tự huấn luyện dựa trên việc đánh giá quá trình lặp ở
bước 2:
- Huấn luyện f từ tập L sử dụng một phương pháp học có giám sát.
- Dự đoán nhãn cho các phần tử x ∈ U.
- Bỏ đi tập con S từ tập U chứa các dữ liệu vừa được gán nhãn, đồng thời thêm
vào tập L các mẫu dữ liệu này và nhãn của chúng (thêm {(x, f(x))| xS} vào L).
- Thuật toán thực hiện số vòng lặp nhiều nhất có thể là: u vòng lặp. Trong đó:
Vòng lặp thứ nhất có độ phức tạp: O (ℓ).
Vòng lặp thứ hai có độ phức tạp là: O (ℓ + 1).
..........................................................................
Vòng lặp thứ u có độ phức tạp là: O (ℓ+u 1).
Do đó thuật toán có độ phức tạp là:

O (ℓ) + O (ℓ +1) + ... + O (ℓ +u 1) = O(ℓ +u 1). (O (ℓ +u)

O (ℓ))/ 2.

= O(ℓ +u 1). O (u) / 2.
≈ O(n2).
1.3.2. Phương pháp đồng huấn luyện
Đồng huấn luyện (Co-training) là một kỹ thuật học nửa giám sát yêu cầu hai
Khung nhìn dữ liệu (View). Nó giả sử rằng mỗi mẫu dữ liệu được mô tả bằng cách
sử dụng hai bộ đặc tính khác nhau, được cung cấp khác nhau, bổ sung thông tin về


mẫu dữ liệu đó. Lý tưởng nhất, hai khung nhìn được xem là điều kiện độc lập (ví
dụ: hai bộ đặc tính của mỗi mẫu dữ liệu là điều kiện độc lập để đưa ra phân lớp của
chúng) và mỗi khung nhìn là đủ (ví dụ: phân lớp của một mẫu dữ liệu có thể được
dự đoán chính xác từ mỗi khung nhìn độc lập). Co-training ban đầu học một bộ
phân lớp riêng cho mỗi khung nhìn, sử dụng bất kỳ mẫu dữ liệu đã gán nhãn nào.
Những dự đoán gần đúng nhất của mỗi bộ phân lớp trên các dữ liệu chưa gán nhãn
sau đó được sử dụng lặp đi lặp lại để xây dựng thêm các dữ liệu được gán nhãn[9].
Phương pháp
Giả sử các dữ liệu đưa ra đã được gán nhãn như sau:
-

Dữ liệu đã gán nhãn : (x1, y1),..., (xℓ, yℓ).

-

Dữ liệu chưa gán nhãn : xℓ+1, ..., xℓ+u .

-


Hàm học f: x

y.

 Giả sử véc tơ đặc trưng X có thể được chia thành hai Khung nhìn (View) như sau:

 Huấn luyện hai bộ học cơ bản f(1): x(1)

y và f(2): x(2)

y

 Đầu tiên, học từ các dữ liệu đã gán nhãn:
o f(1) học trên (x(1)1, y1),..., (x(1) ℓ, yℓ)
o f(2) học trên (x(2)1, y1),..., (x(2) ℓ, yℓ)
 Sau đó, sử dụng lặp lại các dữ liệu chưa gán nhãn:
o f(1) phân lớp các điểm chưa gán nhãn mà hầu hết chứa các điểm rỗng.
o f(1) thêm điểm này vào tập các nhãn của f(2)
f(2) lặp lại như f(1) tới khi dữ liệu được gán nhãn hết thì dừng.
 Ưu điểm của phương pháp Co-training
o Là một phương pháp đơn giản, được áp dụng cho hầu hết các bộ phân lớp
hiện nay.
o Ít xảy ra lỗi hơn so với phương pháp Self-training.
 Nhược điểm của phương pháp Co-training
o Các Khung nhìn được chia tách có thể tồn tại hoặc không tồn tại.
o Mô hình sử dụng cả hai Khung nhìn có thể sẽ tốt hơn.


Ví dụ về phân lớp trang web với phương pháp Co-training

Một ứng dụng của Co-training là sử dụng để phân lớp các trang web bằng
cách sử dụng các văn bản trên các trang như một Khung nhìn. Đơn giản chỉ cần đặt
văn bản trong một siêu liên kết trên một trang có thể đưa ra thông tin về trang web
đó liên kết tới. Co-training có thể làm việc trên các văn bản chưa gán nhãn mà chưa
được phân lớp hay gắn thẻ, điển hình cho các văn bản xuất hiện trên các trang web
và email. Các đặc trưng mô tả một trang web là các từ ngữ trên trang web đó và các
liên kết trỏ tới trang web đó. Mô hình Co-training sử dụng cả hai bộ phân lớp để xác
định rằng một trang web sẽ chứa dữ liệu liên quan đến các tiêu chí tìm kiếm. Văn
bản trên các trang web có thể đánh giá sự phù hợp của bộ phân lớp liên kết.
Bài toán được đưa ra là: Có một tập các trang web, nhiệm vụ của chúng ta là
huấn luyện một chương trình để tìm ra các trang web có cùng một đặc điểm nào đó
(phân lớp). Tuy nhiên, chi phí để có được các trang web đã được gán nhãn là lớn.
Vậy câu hỏi đặt ra là chúng ta chỉ có thể gán nhãn cho một vài trang web và sử dụng
dữ liệu chưa được gán nhãn để phục vụ cho việc gán nhãn cho các trang tiếp theo.
Với bài toán này, phương pháp Co-training có 2 bộ học sử dụng 2 Khung
nhìn của dữ liệu đã gán nhãn và chưa gán nhãn.
Hai Khung nhìn của dữ liệu như sau: Phần văn bản (Page text) và Phần liên
kết (Link)

Hình 1.2: Khung nhìn dữ liệu giữa văn bản và liên kết


Hình 1.3: Dữ liệu được học theo phương pháp Co-training.
1.3.3. Phương pháp Máy véc tơ hỗ trợ truyền dẫn
Để đề cập đến phương pháp máy véc tơ hỗ trợ truyền dẫn (Transductive
Support Vector Machine-TSVM) trước hết ta xem xét phương pháp Máy véc tơ hỗ
trợ (Support Vector Machines -SVM). Phương pháp SVM là một phương pháp phân
lớp nhị phân, ra đời từ lý thuyết học thống kê, do Vapnik và Chervonenkis xây
dựng. Phương pháp SVM có nhiều ứng dụng trong thực tế với các bài toán phân lớp
như: nhận dạng văn bản, nhận dạng chữ viết tay, phát hiện mặt người trong các ảnh

và ước lượng hồi quy,...[8].
Trong phương pháp SVM, một máy hỗ trợ vector xây dựng một siêu mặt
phẳng hay một tập các siêu mặt phẳng trong một không gian nhiều chiều. Bằng trực
giác, để phân lớp tốt nhất thì các siêu mặt phẳng nằm ở càng xa các điểm dữ liệu
của tất cả các lớp thì càng tốt, tức là lề (margin) càng lớn thì sai số tổng quát của
thuật toán phân lớp càng nhỏ.
Thuật toán được cho trước một số điểm dữ liệu đã được gán nhãn thuộc một
trong hai lớp (giả sử là lớp 1 và lớp +1). Mục tiêu của thuật toán là xác định xem
một điểm dữ liệu mới sẽ thuộc về lớp nào. Mỗi điểm dữ liệu sẽ được biểu diễn dưới
dạng một vector d chiều, và ta muốn biết liệu có thể chia tách hai lớp dữ liệu bằng


một siêu phẳng d – 1 chiều hay không?. Đây gọi là phân lớp tuyến tính. Có nhiều
siêu mặt phẳng có thể phân lớp được dữ liệu. Ở đây ta xét siêu mặt phẳng có lề cực
đại giữa hai lớp (Maximum margin).

Hình 1.4: Phương pháp Máy véc tơ hỗ trợ
Giả sử, cho tập dữ liệu huấn luyện T gồm n phần tử có dạng sau:
T={(xi, yi) | xi ∈

d

, yi ∈ { 1, 1}} với i=1..n

Trong đó yi xác định lớp của điểm xi, yi nhận giá trị 1 hoặc +1. Mỗi xi là
một vectơ thực d chiều. Ta cần tìm siêu phẳng có lề cực đại chia tách các điểm
có yi= 1 và các điểm có yi=1.
Mỗi siêu phẳng có thể được viết dưới dạng một tập hợp các điểm x thỏa mãn
w.x


b = 0. Trong đó dấu chấm ( ) kí hiệu của tích vô hướng và w là một vectơ

pháp tuyến của siêu phẳng.
Tham số

xác định khoảng cách giữa gốc tọa độ và siêu phẳng theo

hướng vectơ pháp tuyến của w.
Nhiệm vụ của chúng ta là cần chọn w và b sao cho lề đạt cực đại, hay
khoảng cách giữa hai siêu mặt phẳng song song ở xa nhau nhất có thể trong khi vẫn