Mục lục
Danh mục thuật ngữ 3
Danh mục các hình vẽ 4
Danh mục các bảng 4
Mở đầu 5
Chương 1: Tổng quan 6
1.1 Giới thiệu bài toán xử lý văn bản 6
1.2 Các phương pháp phân loại văn bản 6
1.3 Vấn đề giảm chiều đặc trưng 7
1.3.1. Giới thiệu 7
1.3.2. Các tiếp cận và tình hình nghiên cứu ở Việt Nam 8
1.4 Đặc điểm của tiếng Việt 9
1.5 Mục tiêu của luận văn 10
Chương 2: Biểu diễn văn bản 11
2.1 Giới thiệu 11
11
2.2 Mô hình Boolean 12
2.3 Mô hình tần suất (Term Frequency – TF) 12
2.4 Mô hình nghịch đảo tần số văn bản (Inverse Document Frequency - IDF) 13
2.5 Mô hình kết hợp TFxIDF 13
2.6 Áp dụng phương pháp véc-tơ thưa trong lưu trữ văn bản 13
Chương 3: Các phương pháp phân loại văn bản 15
3.1 Giới thiệu 15
3.2 Quy trình phân loại văn bản 15
3.3 Đặc điểm của Tiếng Việt và ảnh hưởng trong phân loại văn bản 16
3.3.1. Đặc điểm tiếng Việt 16
3.3.2. Ảnh hưởng trong phân loại văn bản 18
3.4 Phương pháp phân loại Naïve Bayes 18
3.5 Phương pháp phân loại Centroid- based vector 19
3.6 Phương pháp phân loại k–Nearest Neighbor (kNN) 19
3.7 Phân loại văn bản bằng phương pháp Support Vector Machines 20

4.5.4. Thuật toán giảm số chiều LDA/GSVD 56
Chương 5: Cài đặt chương trình và kết quả thử nghiệm 57
5.1 Chức năng tiền xử lý văn bản 58
5.1.1. Chuẩn hóa 58
5.1.2. Xây dựng bộ từ điển 58
5.1.3. Biểu diễn văn bản 58
5.1.4. Thuật toán giảm số chiều văn bản 59
5.1.4.1. Thuật toán giảm số chiều LSI/SVD 59
5.1.4.2. Thuật toán giảm số chiều Centroid 60
5.1.4.3. Thuật toán giảm số chiều Orthogonal Centroid 60
5.2 Huấn luyện và phân loại 61
5.2.1. Phương pháp SVM 61
5.2.1.1. Quá trình huấn luyện 61
5.2.1.2. Quá trình kiểm tra 63
5.2.1.3. Phân loại văn bản 64
5.3 Kết quả thực nghiệm 64
5.3.1. Văn bản được tách thành các từ (word segments) 65
5.3.2. Văn bản được tách thành các âm tiết 67
Kết luận 70
Tài liệu tham khảo 71
2
Danh mục thuật ngữ
Số
TT
Từ viết
tắt
Tiếng Anh Tiếng Việt
1 High Dimension Số chiều đặc trưng lớn (Cao)
2 kNN k-Nearest Neighbor k láng giềng gần nhất (phân loại
văn bản)

Centroid 66
Bảng 4. Chi phí thời gian huấn luyện và phân loại sử dụng hàm nhân Poly (d=2) trường
hợp văn bản được tách thành các từ 66
Bảng 5. Chi phí thời gian thực hiện các thuật toán giảm chiều trường hợp văn bản được
tách thành các từ 67
Bảng 6. Độ chính xác phân loại trên mỗi chuyên mục và trên toàn bộ tập dữ liệu trường
hợp văn bản tách thành các âm tiết sử dụng thuật toán giảm chiều LSI/SVM 67
Bảng 7. Độ chính xác phân loại trên mỗi chuyên mục và trên toàn bộ tập dữ liệu trường
hợp văn bản tách thành các âm tiết sử dụng thuật toán giảm chiều Centroid và
Orthogonal Centroid 68
Bảng 8. Chi phí thời gian huấn luyện và phân loại sử dụng hàm nhân Poly (d=2) trường
hợp văn bản được tách thành các âm tiết 68
Bảng 9. Chi phí thời gian thực hiện các thuật toán giảm chiều trường hợp văn bản được
tách thành các âm tiết 69
4
Mở đầu
Phân loại văn bản là một trong những bài toán quan trọng trong xử lý văn bản
tiếng Việt. Một trong những thách thức của bài toán phân loại văn bản là số lượng đặc
trưng (thuộc tính) dùng để phân loại thì thường rất lớn. Bên cạnh đó, khi áp dụng vào
trong xử lý tiếng Việt chúng ta cần phải khảo sát hiệu quả của các phương pháp phân loại
trên một số đặc điểm riêng của tiếng Việt như việc sử dụng từ hay âm tiết.
Luận văn trình bày phương pháp phân loại Máy Véc-tơ hỗ trợ, đây được cho là
một trong những phương pháp phân loại tốt nhất hiện này đồng thời kết hợp tập trung
giải quyết vấn đề “số chiều đặc trưng lớn” bằng cách áp dụng các phương pháp giảm
chiều đặc trưng. Sau khi trình bày tổng quan về các tiếp cận giảm chiều đặc trưng luận
văn đi sâu vào trình bày các tiếp cận Lantent semantic index, Centroid, Orthogonal
Centroid, GSVD/LDA được áp dụng cho dữ liệu phân cụm phù hợp với bài toán phân
loại văn bản. Trên cơ sở đó chúng tôi cài đặt và thử nghiệm, đưa ra bảng so sánh đánh giá
các kết quả phân loại được ứng dụng cho bài toán phân loại văn bản tiếng Việt trong hai
trường hợp dựa vào đặc điểm riêng của tiếng Việt là sử dụng tách từ và âm tiết.

nhận dạng và phân loại (Joachims, 1998). SVM là một họ các phương pháp dựa trên cơ
sở các hàm nhân (kernel) để tối thiểu hóa rủi ro ước lượng.
6
Phương pháp SVM ra đời từ lý thuyết học thống kê do Vapnik và Chervonenkis
xây dựng và có nhiều tiềm năng phát triển về mặt lý thuyết cũng như ứng dụng trong
thực tiễn. Các thử nghiệm thực tế cho thấy, phương pháp SVM có khả năng phân loại
khá tốt đối với bài toán phân loại văn bản cũng như trong nhiều ứng dụng khác (như nhận
dạng chữ viết tay, phát hiện mặt người trong các ảnh, ước lượng hồi quy, ). So sánh với
các phương pháp phân loại khác, khả năng phân loại của SVM là tương đương hoặc tốt
hơn đáng kể (Nguyễn Linh Giang và Nguyễn Mạnh Hiển, 2005).
Hệ thống phân loại văn bản tiếng Việt ở nước ta đã có nhiều nhà nghiên cứu và
phát triển xây dựng trong những năm gần đây (Huỳnh Quyết Thắng và Đinh Thị Phương,
1999) (Nguyễn Linh Giang và Nguyễn Mạnh Hiển, 2005). Các hướng tiếp cận bài toán
phân loại văn bản đã được nghiên cứu bao gồm: hướng tiếp cận bài toán phân loại bằng
lý thuyết đồ thị (Đỗ Bích Diệp, 2004), cách tiếp cận sử dụng lý thuyết tập thô (Nguyễn
Ngọc Bình, 2004), cách tiếp cận thống kê (Nguyễn Linh Giang và Nguyễn Duy Hải,
1999), cách tiếp cận sử dụng phương pháp học không giám sát và đánh chỉ mục (Huỳnh
Quyết Thắng và Đinh Thị Phương, 1999). Nhìn chung, những cách tiếp cận này đều cho
kết quả chấp nhận được.
:
1. Số chiều đặc trưng lớn
Trong phân loại văn bản tất cả các phương pháp gặp một khó khăn chung khi
không gian dữ liệu với số chiều lớn. Khi đó đòi hỏi không gian bộ nhớ dữ liệu lớn và mất
nhiều thời gian xử lý văn bản phân loại. Để giải quyết vấn đề khó khăn này luận văn sẽ
trình bày và xây dựng hệ thống phân loại kết hợp với các phương pháp tối ưu kích thước
dữ liệu được áp dụng cho văn bản Tiếng Việt.
2. Phân tách câu thành các từ
Khác với tiếng Anh, văn bản tiếng Việt có thể được biểu diễn bởi danh sách các từ
hoặc âm tiết. Để biểu diễn văn bản bởi các từ, chúng ta phải xử lý bài toán tách từ (word
segmentation) cho tiếng Việt. Hai cách sử dụng này (âm tiết và từ) sẽ được khảo sát so

hạn trung tâm (central limit): Giá trị trung bình của các sự thể hiện ngẫu nhiên có hành vi
giống như biến Gauss, khi ta chọn ngẫu nhiên một sự thể hiện trong dãy các sự thể hiện
thì kích thước dãy các sự thể hiện càng lớn thì các đặc trưng thống kê (trung bình,
phương sai,…) của sự thể hiện càng gần với đặc trưng của dãy.
Giảm chiều không gian đặc trưng trong bài toán phân loại văn bản nói riêng và các
bài toán có số chiều lớn nói chung có vai trò quan trọng trong việc:
– Giảm thiểu không gian bộ nhớ dữ liệu
– Tăng tốc độ xử lý dữ liệu cho giải thuật xử lý văn bản
1.3.2. Các tiếp cận và tình hình nghiên cứu ở Việt Nam
1. Các tiếp cận
8
Được chia làm hai loại:
Các phương pháp giảm chiều đặc trưng cho dữ liệu chưa được phân cụm hay còn
gọi là dữ liệu không giám sát (Unsupervised) như Principal components analysis (Karl
Pearson , 1901), Independent Component Analysis (Pierre Comon, 1994), Locally linear
Embedding (Sam T. Roweis và Lawrence K. Saul , 2000). Khi dữ liệu chưa phân cụm thì
có thể áp dụng các giải thuật phân cụm để gom dữ liệu thành các nhóm sau đó áp dụng
các phương pháp giảm số chiều cho dữ liệu đã được phân cụm.
Các phương pháp giảm chiều đặc trưng cho dữ liệu đã được phân cụm hay còn gọi
là dữ liệu giám sát (Supervised) như Latent semantic indexing (Scott Deerwester,ext,
1988), Centroid (Park et al, 2003) , Orthogonal centroid (Park et al, 2003), Generalized
singular value decompositon (GSVD/LDA) (Park et al, 2003), Linear discriminant
analysis (Fisher, 1936),…
2. Tình hình nghiên cứu ở Việt Nam
Ở Việt Nam cũng đã có những nghiên cứu về giảm chiều đặc trưng như cách tiếp
cận LSI (lantent semantic indexing) đánh chỉ mục ngữ nghĩa ẩn (Dương Thanh Tịnh,
2005) làm giảm chiều đặc trưng áp dụng trong hệ thống hỗ trợ tư vấn cho thương mại
điện tử, sử dụng giải thuật phân tán cho mạng máy tính (Đỗ Thanh Nghị, 2002) phân
phối công việc cho mạng máy tính xử lý bài toán phân loại văn bản có số chiều đặc trưng
cao, xong vẫn còn ít và chưa được quan tâm nhiều đến lớp bài toán có số chiều đặc trưng

doc, định nghĩa bài toán giảm chiều, trình bày 4 phương pháp được áp dụng cho dữ liệu
đã được phân cụm LSI, Centroid, Orthogonal Centroid, LDA/GSVD.
• Chương 5. Cài đặt và kết quả thử nghiệm: Trình bày các bước cài đặt và các thành
phần của chương trình phân loại văn bản Tiếng Việt, đưa ra kết quả so sánh giữa các
phương pháp giảm chiều đặc trưng áp dụng trong bài toán.
• Kết luận: Đánh giá kết quả đạt được của luận văn và hướng nghiên cứu tiếp theo của
luận văn
10
Chương 2: Biểu diễn văn bản
2.1 Giới thiệu
Như ta đã biết, để có thể xử lý được các văn bản, ta phải chuyển chúng về dạng dữ
liệu có cấu trúc. Để thực hiện được công việc này, người ta đưa ra các mô hình biểu diễn
văn bản. Mô hình biểu diễn văn bản có ảnh hưởng rất nhiều đến hiệu quả và hiệu suất xử
lý các văn bản. Tuỳ mục đích, yêu cầu đặt ra của ứng dụng mà chúng ta lựa chọn mô
hình biểu diễn và phương pháp xử lý phù hợp.
Các mô hình biểu diễn văn bản đã được sử dụng như mô hình dựa trên tập mờ
(Nguyễn Hoàng Phương, 2001)(Đoàn Sơn, 2002), mô hình tập thô dung sai (Hồ Tú Bảo
et al, 2001), mô hình không gian vectơ (Vector Space Model) (Sparck Jones, 1972)( G.
Salton et al, 1975). Trong luận văn này trình bày mô hình không gian vec- tơ.
Bản chất của mô hình không gian vec-tơ là mỗi văn bản được biểu diễn thành một
véc-tơ. Mỗi thành phần của véc-tơ biểu diễn một thuật ngữ riêng biệt trong tập văn bản
gốc và được gán một giá trị là hàm f của từng thuật ngữ trong văn bản. Giá trị f này
thường là trọng số của từ trong văn bản, được xác định theo nhiều cách khác nhau. Hình
sau biểu diễn các véc-tơ văn bản trong không gian chỉ có 2 thuật ngữ.
. Biểu diễn các véc-tơ văn bản trong không gian chỉ có 2 thuật ngữ
Có nhiều biến thể của mô hình không gian véc-tơ, dưới đây là một số dạng của mô
hình không gian véc-tơ:
11
2.2 Mô hình Boolean
Đây là mô hình biểu diễn véc-tơ với hàm f cho ra giá trị rời rạc với duy nhất hai

ij
= f
ij
w
ij
= 1 + log(f
ij
)
w
ij
=
ij
f
Trong đó: log(X) - logarit cơ số 10 của X.
Trong phương pháp này, trọng số w
ij
đồng biến với số lần xuất hiện của thuật ngữ
t
i
trong văn bản d
j
. Khi số lần xuất hiện thuật ngữ t
i
trong văn bản d
j
càng lớn thì điều đó
có nghĩa là văn bản d
j
càng phụ thuộc vào thuật ngữ t
i

j
j
i
ij
d0
d
h
m
w
i
ii
tif
tif )log(h-log(m) log
với m là số lượng văn bản và h
i
là số văn bản mà thuật ngữ t
i
xuất hiện. Trọng số
w
ij
trong công thức này được tính dựa trên độ quan trọng của thuật ngữ t
i
trong văn bản
d
j
. Nếu t
i
xuất hiện trong càng ít văn bản, điều đó có nghĩa là nếu nó xuất hiện trong d
j
thì

tif
tif log)].log(1[
Phương pháp này kết hợp được ưu điểm của cả hai phương pháp trên. Trọng số w
ij
được tính bằng tần số xuất hiện của thuật ngữ t
i
trong văn bản d
j
và độ hiếm của thuật
ngữ t
i
trong toàn bộ cơ sở dữ liệu.Tuỳ theo yêu cầu ràng buộc cụ thể của bài toán mà ta
sử dụng các mô hình biểu diễn văn bản cho phù hợp.
2.6 Áp dụng phương pháp véc-tơ thưa trong lưu trữ văn bản
Khi biểu diễn văn bản theo mô hình véc-tơ chuẩn, việc xử lý các phép toán trên
véc-tơ sẽ phụ thuộc vào độ lớn của ma trận W
ij
, i= {1,…,n}, j = {1,…,m} với n là số lượng
13
thuật ngữ hay số chiều của véc-tơ và m là số lượng văn bản có trong cơ sở dữ liệu. Trên
thực tế, số lượng thuật ngữ và số văn bản thường rất lớn, có thể lên đến hàng nghìn hoặc
hơn nữa. Khi đó số lượng phần tử trong ma trận W
ij
sẽ lên đến con số hàng triệu và việc
lưu trữ ma trận W
ij
sẽ tốn quá nhiều tài nguyên bộ nhớ đồng thời các phép toán trên các
véc-tơ sẽ rất phức tạp. Để khắc phục vấn đề này có thể sử dụng kỹ thuật xử lý trên véc-tơ
thưa thay vì việc lưu trữ và xử lý trên các véc-tơ chuẩn.
Véc-tơ thưa là kiểu véc-tơ chỉ lưu trữ những thành phần từ khoá có số lần xuất


(2, 3, 0, 0, 0, 0)
d
1
= (1, 0, 1, 4, 0, 0)
d
2
= (1, 0, 0, 0, 3, 2)
Đối với véc-tơ thưa:
d
0
=

((1, 2), (2, 3))
d
1
= ((1,1), (3,1), (4,4))
d
2
= ((1,1), (5,3), (6,2))
14
Chương 3: Các phương pháp phân loại văn
bản
3.1 Giới thiệu
Phân loại văn bản là nhiệm vụ học có giám sát khi cho một số lớp văn bản đã được
xác định trước, yêu cầu gán nhãn cho các văn bản vào một (hay một số) lớp văn bản thích
hợp dựa vào nội dung của các văn bản đó. Các văn bản đã được phân lớp (các mẫu huấn
luyện) trở thành nguồn. Trong trường hợp thuận lợi nhất là chúng đã có sẵn, khi đó quá
trình phân loại bắt đầu bằng việc học từ tập dữ liệu này, sau đó sẽ thực hiện phân loại tự
động với các văn bản khác. Trường hợp ít thuận lợi, không có sẵn văn bản đã phân loại

FTCD ,: →×Φ

với mọi
Ccd
ij
×Ω∈,
. Một văn bản d
j
là mẫu dương của c
i
nếu
Tcd
ij
=Φ ),(

, là một mẫu âm
nếu
Fcd
ij
=Φ ),(

.
Với mỗi cách phân loại được đưa ra, người ta mong muốn đánh giá được hiệu quả
phân loại của chúng. Bởi vậy, trước khi xây dựng phân loại người ta chia tập văn bản ban
15
đầu thành 2 tập hợp, số các văn bản trong hai tập hợp này không nhất thiết phải bằng
nhau:
- Tập huấn luyện (training (-and-validation) set) Tr={d
1
, …, d


của chuyên gia. Hiệu quả của phân lớp
dựa trên sự phù hợp giữa
),(
ij
cdΦ
và
),(
ij
cdΦ

.
Trong đó, Tr
∩
Te =
∅
. Nếu điều kiện này bị vi phạm thì kết quả đánh giá hiệu quả
của mô hình mất đi yếu tố khách quan, khoa học.
Hầu hết các phương pháp phân loại văn bản dựa trên kỹ thuật học máy hiện nay
đều dựa vào tần xuất xuất hiện (số lần xuất hiện) của từ hoặc cụm từ trong văn bản, hoặc
dựa vào tần xuất xuất hiện của từ trong văn bản và tần xuất văn bản (số các văn bản trong
tập dữ liệu huấn luyện có chứa từ đó).
3.3 Đặc điểm của Tiếng Việt và ảnh hưởng trong phân loại văn
bản
(Trung tâm từ điển học Việt Nam, 2000)
3.3.1. Đặc điểm tiếng Việt
Tiếng Việt thuộc ngôn ngữ đơn lập, tức là mỗi một tiếng (âm tiết) được phát âm
tách rời nhau và được thể hiện bằng một chữ viết. Đặc điểm này thể hiện r• rệt ở tất cả
các mặt ngữ âm, từ vựng, ngữ pháp.
 !"##: Trong tiếng Việt có một loại đơn vị đặc biệt gọi là "tiếng".

Việc sắp xếp các từ theo một trật tự nhất định là cách chủ yếu để biểu thị các quan
hệ cú pháp. Trong tiếng Việt khi nói "Anh ta lại đến" là khác với "Lại đến anh ta". Khi
các từ cùng loại kết hợp với nhau theo quan hệ chính phụ thì từ đứng trước giữ vai trò
chính, từ đứng sau giữ vai trò phụ. Nhờ trật tự kết hợp của từ mà "củ cải" khác với "cải
củ", "tình cảm" khác với "cảm tình". Trật tự chủ ngữ đứng trước, vị ngữ đứng sau là trật
tự phổ biến của kết cấu câu tiếng Việt.
Phương thức hư từ cũng là phương thức ngữ pháp chủ yếu của tiếng Việt. Nhờ hư
từ mà tổ hợp "anh của em" khác với tổ hợp "anh và em", "anh vì em". Hư từ cùng với trật
tự từ cho phép tiếng Việt tạo ra nhiều câu cùng có nội dung thông báo cơ bản như nhau
nhưng khác nhau về sắc thái biểu cảm. Ví dụ, so sánh các câu sau đây:
17
- Ông ấy không hút thuốc.
- Thuốc, ông ấy không hút.
- Thuốc, ông ấy cũng không hút.
Ngoài trật tự từ và hư từ, tiếng Việt còn sử dụng phương thức ngữ điệu. Ngữ điệu
giữ vai trò trong việc biểu hiện quan hệ cú pháp của các yếu tố trong câu, nhờ đó nhằm
đưa ra nội dung muốn thông báo. Trên văn bản, ngữ điệu thường được biểu hiện bằng
dấu câu. Chúng ta thử so sánh 2 câu sau để thấy sự khác nhau trong nội dung thông báo:
- Đêm hôm qua, cầu gãy.
- Đêm hôm, qua cầu gãy.
3.3.2. Ảnh hưởng trong phân loại văn bản
Độ chính xác của kết quả tách từ có ảnh hưởng rất lớn đến kết quả của phân loại,
không thể có một kết quả phân loại tốt nếu như không tách được đúng các từ trong văn
bản. Bởi vậy, một vấn đề quan trọng đối với phân loại văn bản là phải tách được chính
xác các từ trong văn bản. Các văn bản được viết bằng các ngôn ngữ khác nhau thì có đặc
trưng riêng của ngôn ngữ đó, và không có một phương pháp chung nào để tách các từ
trong các văn bản được viết bằng các ngôn ngữ khác nhau. Trong luận văn này chúng tôi
sử dụng lại kết quả tách từ (C. T. Nguyen et al, 2006).
3.4 Phương pháp phân loại Naïve Bayes
Naïve Bayes là phương pháp phân loại dựa vào xác suất được sử dụng rộng rãi

P C d P d C P C=
():
1. Tính xác xuất của mỗi từ
i
word
(i=1 m) xuất hiện trong mỗi chủ đề
j
C
2. Tính tổng số từ của mỗi lớp
j
C
3. Tính xác xuất của chủ đề
j
C
đối với văn bản d theo công thức
4.
( )
i
P C d
=
1 2
( ( | )* ( | )* * ( | ))
j j m j
P word C P word C P word C
*(Tổng số từ của
chủ đề
j
C
)/ (Tổng số từ của tất cả các chủ đề)
5. Nếu

x i
d C d C=
thì văn bản d thuộc lớp x
3.6 Phương pháp phân loại k–Nearest Neighbor (kNN)
kNN là phương pháp truyền thống khá nổi tiếng về hướng tiếp cận dựa trên thống
kê đã được nghiên cứu trong nhận dạng mẫu hơn bốn thập kỷ qua (Dasarathy, 1991).
kNN được đánh giá là một trong những phương pháp tốt nhất (áp dụng trên tập dữ liệu
Reuters phiên bản 21450), được sử dụng từ những thời kỳ đầu của việc phân loại văn bản
Marsand et al, 1992) (Yang, 1994) (Iwayama, Tokunaga, 1995)
Khi cần phân loại một văn bản mới, thuật toán sẽ tính khoảng cách (khoảng cách
Euclide, Cosine ) của tất cả các văn bản trong tập huấn luyện đến văn bản này để tìm ra
19
k văn bản gần nhất (gọi là k “láng giềng”), sau đó dùng các khoảng cách này đánh trọng
số cho tất cả chủ đề. Trọng số của một chủ đề chính là tổng tất cả khoảng cách ở trên của
các văn bản trong k láng giềng có cùng chủ đề, chủ đề nào không xuất hiện trong k láng
giềng sẽ có trọng số bằng 0. Sau đó các chủ đề sẽ được sắp xếp theo mức độ trọng số
giảm dần và các chủ đề có trọng số cao sẽ được chọn là chủ đề của văn bản cần phân
loại.
():
1. Tính
*
cos( , )
*
i
i
i
d d
d d
d d
=

đoán văn bản này có thuộc loại văn bản đang xét hay không. Vì SVM xuất phát từ lý
thuyết học thống kê, dựa trên nguyên tắc tối thiểu hoá rủi ro cấu trúc.
Nên trước hết ta hãy xem xét một số lý thuyết học thống kê có liên quan.
3.7.1. Lý thuyết học thống kê
'*+,(+-./+00/12#013
Xét các hàm f(x): R
→
{+1,-1}, có 2
ns
cách để gán nhãn cho n
s
đ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 n
s
đ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 R
n
là n+1. Ví dụ, chiều VC của các
đường thẳng có hướng trong không gian 2 chiều (R
2
) là 3.
20
$ Minh họa chiều VC của tập các hàm {f(x)} trong không
gian hai chiều với 3 điểm dữ liệu
Trên đây là ví dụ về chiều VC của không gian 2 chiều. Khi số điểm dữ liệu >3, ví
dụ là 4, thì số cách gán nhãn (số hàm f(x)) sẽ không còn là 2
4


y
Giả sử mối liên quan giữa x và y được cho bởi phân bố xác suất liên kết
P(x,y)=P(x).P(y|x). Mục đích của bài toán học có giám sát là tìm một hàm f
s
trong tập
hợp các hàm {f
s
| f
s
: X
→
Y , và f
s
được học trên tập dữ liệu huấn luyện S} để tối thiểu.
( )
∫
×
=
YX
ss
dxdyyxPyxfcfR ),(),()(
Trong đó: R(f
s
): là rủi ro toàn cục của f
s
(x).
22
c: là hàm thiệt hại (loss function), dùng để đo sự sai lệch của f
s

1
), …, (x
ns
, y
ns
)} sao cho rủi ro R là tối thiểu. Vì trong thực tế,
chúng ta không biết được phân bố thực sự P(x, y) nên chúng ta không thể biết được tất cả
các khả năng xảy ra của tập dữ liệu kiểm tra. Tuy nhiên, chúng ta có thể tính toán được
rủi ro thực nghiệm (Emprical Risk) dựa trên tập dữ liệu huấn luyện S.
'*'45&#
Cho S={(x
1
, y
1
), …, (x
ns
, y
ns
)}, và c là hàm thiệt hại của f
s
(x) thì rủi ro thực nghiệm
R
emp
(f
s
) của hàm f
s
(x) trên tập dữ liệu huấn luyện S được tính như sau:
∑
=

thì rủi ro thực nghiệm R
emp
(f
s
) sẽ bằng 0, mặc dù vậy, trường hợp này là không tổng quát.
Vì hàm f
s
có thể đạt được rủi ro tối thiểu trên tập dữ liệu S (hiện tượng tài liệu tốt, well-
documented), nhưng có thể gây ra rủi ro lớn trong các tập dữ liệu khác. Hiện tượng này
còn được gọi là hiện tượng tràn lỗi (overfitting), nghĩa là giả thuyết fs chỉ tốt với tập dữ
liệu huấn luyện S (tối ưu cục bộ), nhưng không tốt với các tập dữ liệu khác.
'*8(9:;<"(5=(>
Mặc dù, không trực tiếp tối thiểu được rủi ro toàn cục, nhưng nếu chúng ta tìm
được một hàm f
s
để có thể tối thiểu giới hạn trên của rủi ro toàn cục, thì R(f
s
) cũng sẽ là
tối thiểu. Giới hạn trên của rủi ro toàn cục là:
s
s
SempS
n
h
n
h
fRfR




: là giá trị của xác suất liên kết P(x,y)
Ví dụ: Độ tin cậy của P(x,y) là 90% (δ=0.1), tập S có 100 mẫu thì rủi ro toàn cục
không lớn hơn R
emp
(f
s
)+T.
T =
6.11
200
ln
10
1
+






+
h
h
Nếu h=1 thì T=0.281, nếu h=2 thì T=0.357, nếu h=10 thì T=0.645.
Ta thấy rằng, h càng nhỏ thì số hạng thứ 2 trong vế phải của (*) càng nhỏ. Tuy
nhiên, vì chiều VC nhỏ thì có thể gây ra lỗi thực nghiệm lớn, do đó, để tối thiểu rủi ro
toàn cục, người ta làm như sau:
- Đầu tiên, chọn các hàm có rủi ro thực nghiệm là nhỏ nhất, tập các hàm này kí
hiệu là F
empmin

; b
∈
R .
x

là biến,
w

và b là các tham số của
)(xf

.
Thì bổ đề về số chiều VC của tập các hàm {
)(xf

} được Vapnik phát biểu như sau:
Coi các hàm
}.{)( bxwsignxf +=

như là các giả thuyết. Nếu tất cả các véc-tơ
i
x

(i=1, 2, ,n
s
) trong tập mẫu, được bao trong một hình cầu có bán kính R và thỏa mãn:
1. ≥+ bxw
i

, đặt

- Bài toán: Kiểm tra xem một văn bản d bất thuộc hay không thuộc một phân loại
c cho trước? Nếu d
∈
c thì d được gán nhãn là 1, ngược lại thì d được gán nhãn là –1.
Ở đây thực hiện việc lựa chọn các đặc trưng (từ) để biểu diễn văn bản. Giả sử,
chúng ta lựa chọn được tập các đặc trưng là T={t
1
, t
2
, …, t
n
}, thì mỗi văn bản d
i
sẽ được
biểu diễn bằng một véc-tơ dữ liệu x
i
=(w
i1
, w
i2
, …, w
in
), w
ij
∈
R là trọng số của từ t
j
trong
văn bản d
i

i
∈
R
n
),
y
i
∈
{+1, -1},
cặp (x
i
, y
i
) được hiểu là véc-tơ x
i
(hay văn bản d
i
) được gán nhãn là y
i
.
Nếu coi mỗi văn bản d
i
được biểu diễn tương ứng với một điểm dữ liệu trong
không gian R
n
, thì ý tưởng của SVM là tìm một mặt hình học (siêu phẳng) f(x) “tốt nhất”
trong không gian n-chiều để phân chia dữ liệu sao cho tất cả các điểm x
+
được gán nhãn
+1 thuộc về phía dương của siêu phẳng (f(x