Luận án Nghiên cứu khoa học toán ứng dụng

Cụ thể hơn, trong hình 2.3 giả sử tất cả các mẫu cần phân lớp đều có nhiễu so với các mẫu huấn luyện. Ví dụ, cho mẫu huấn luyện (x,y), tạo ra các mẫu cần phân lớp theo công thức (x+Δx,y), trong đó Δx được giới hạn bởi r > 0. Rõ ràng nếu tách tập huấn luyện theo khoảng cách lề δ > r thì sẽ phân lớp chính xác tất cả các mẫu. Điều này giải thích tại sao siêu phẳng với khoảng cách lề cực đại có khả năng phân lớp tốt nhất. Hình 2.3. Siêu phẳng tách hai lớp ‘o’ và ‘+’. Nếu siêu phẳng có khoảng cách lề δ và giới hạn nhiễu r < δ thì siêu phẳng vẫn tách được chính xác các mẫu bị nhiễu. 2.2.2. Tìm siêu phẳng tối ưu Đối với dữ liệu khả tách tuyến tính, thuật toán huấn luyện đơn giãn chỉ là tìm một hàm tuyến tính f(x) = wT.x + b với một khoảng cách lề lớn nhất có thể. Không 38 mất tính tổng quát, giả sử tất cả các mẫu huấn luyện đều có khoảng cách đại số lớn hơn hoặc bằng hằng số δ = 1, tức là wT.xi + b ≥ +1, với yi = +1 (2.5) wT.xi + b ≤ - 1, với yi = -1 (2.6) hoặc viết gọn hơn: yi(wT.xi + b) ≥ 1, i=1,...,l (2.7) Khoảng cách của một điểm nằm trên H1 hoặc H2 tới H là 22 | . | 1 || || Tw x b w w + = nên khoảng cách giữa H1 và H2 là 2 2 || ||w . Vì vậy, có thể tìm siêu phẳng với khoảng cách lề cực đại bằng cách cực tiểu ||w||2 = wT.w sao cho thỏa mãn ràng buộc (2.7). Từ đó, bài toán tìm siêu phẳng tối ưu có thể phát biểu lại như sau: T , 1min w .w 2w b (2.8) sao cho yi(wT.xi + b) ≥ 1, i=1,...,l (2.9) Kết quả của việc giải bài toán (2.8) sẽ thu được những mẫu nằm trên H1 và H2. Các mẫu này được gọi là các véc tơ tựa, chỉ có chúng mới tham gia vào việc xác định siêu phẳng tối ưu, còn các mẫu khác có thể loại bỏ. 2.2.3. Phân lớp mềm Hình 2.4. Phân lớp mềm. 39 Máy phân lớp với khoảng cách lề cực đại ở phần trên chỉ áp dụng được đối với các tập dữ liệu khả tách tuyến tính, còn thực tế thì thường gặp các tập dữ liệu không khả tách tuyến tính. Để xây dựng một máy phân lớp với khoảng cách lề cực đại phù hợp với các loại dữ liệu bị nhiễu, cần phải nới lõng ràng buộc của (2.9). Nghĩa là không ép buộc dữ liệu phải nằm hoàn toàn về hai phía của H1 và H2 (hình 2.4). Để thực hiện điều này, thêm vào các biến trể (slack variables) không âm ξi≥0 sao cho: yi(wT.xi + b) ≥ 1 - ξi, i=1,...,l (2.10) (2.11) i 0, iξ ≥ ∀ và hàm mục tiêu ở trong (2.8) được thay bằng hàm mục tiêu có dạng hàm phạt [2]: T 1 1 w w .( ) 2 l m i i C = + ξ∑ (2.12) trong đó C > 0 là một tham số tùy chọn (C càng lớn thì lượng phạt lỗi càng cao). Với m ≥ 1, việc tìm siêu phẳng tối ưu sẽ có dạng bài toán quy hoạch lồi, đặc biệt với m = 1 thì ta có bài toán quy hoạch toàn phương và trong trường hợp này bài toán tìm siêu phẳng tối ưu có thêm một lợi thế nữa là cả ξi lẫn các nhân tử Lagrange đều không xuất hiện trong bài toán đối ngẫu của Wolfe [14]. Khi đó, bài toán tìm siêu phẳng tối ưu được phát biểu lại như sau: , 1 1min w w 2 ml T iw b i C = ⎛ ⎞+ ξ⎜⎝ ⎠∑ ⎟ (2.13) Thông thường chọn m = 1, như vậy bài toán tối ưu trở thành: , 1 1min w .w 2 l T iw b i C = + ξ∑ (2.14) sao cho thỏa mãn ràng buộc (2.10) và (2.11). 2.3.4. Giải bài toán tối ưu 40 Để thuận tiện cho việc trình bày, bài boán tìm siêu phẳng tối ưu được viết lại như sau: , 1 1min w .w 2 l T iw b i C = + ξ∑ (2.15) sao cho yi(wT.xi + b) ≥ 1 - ξi, i=1,...,l (2.16) ξi ≥ 0, i=1,...,l (2.17) Lý thuyết Lagrange thường được sử dụng để giải các bài toán tối ưu lồi nhưng chỉ với các ràng buộc phương trình. Trong khi đó, các ràng buộc tối ưu của (2.15) chứa các ràng buộc bất phương trình, vì vậy cần biến đổi bài toán này thành một dạng khác để giải một cách dễ dàng hơn. Phương pháp giải bài toán tối ưu lồi có ràng buộc [2] được trình bày tóm tắt như sau: Định nghĩa 2.4: Cho bài toán tối ưu với tập lồi Ω ⊆ RD (min f w), w∈Ω (2.18) sao cho gi(w) ≤ 0, i=1,...,k (2.19) hi(w) = 0, i=1,...,m (2.20) Hàm Lagrange tổng quát gắn với bài toán trên là hàm có dạng 1 1 ( ) ( ) k m i i i i i i L w, , )=f(w g w h w) = = α β − α + β∑ ∑ ( (2.21) Định nghĩa 2.5: Bài toán Lagrange đối ngẫu của bài toán gốc (2.18) là bài toán có dạng max θ(α,β) (2.22) sao cho α ≥ 0 (2.23) trong đó θ(α,β) = . ( Dw R inf L w, , ) ∈ α β 41 Mối quan hệ giữa bài toán gốc và bài toán đối ngẫu là giá trị hàm mục tiêu tại đáp án tối ưu trong bài toán đối ngẫu bị chặn trên bởi giá trị hàm mục tiêu tại đáp án tối ưu trong bài toán gốc: sup{θ(α,β); α ≥ 0} ≤ inf{f(w); g(w) ≤ 0, h(w) = 0} (2.24) Hơn nữa, nếu w* là nghiệm của bài toán (2.18) và (α*,β*) là nghiệm của bài toán (2.22) thì f(w*) = θ(α*,β*). Định lý Kuhn-Tucker nói rằng nếu hàm mục tiêu f của bài toán (2.18) là hàm lồi và gi, hi là các hàm tuyến tính thì điều kiện cần và đủ để tồn tại nghiệm w* là phải tồn tại (α*,β*). Định lý 2.1: (Định lý Kuhn-Tucker) Điều kiện cần và đủ để w* là nghiệm tối ưu của bài toán gốc (2.18) là tồn tại α* và β* sao cho * *( , , ) 0 *L w w ∂ α β =∂ (2.25) * *( , , ) 0 *L w∂ α β =∂β (2.26) * ( ) 0, 1,...,*i ig w i kα = = (2.27) ( ) 0, 1,...,*ig w i k≤ = (2.28) 0, 1,...,i iα ≥ = k (2.29) Bài toán gốc có thể biến đổi thành bài toán đối ngẫu đơn giản hơn bằng cách cho đạo hàm của hàm Lagrange triệt tiêu theo các biến của bài toán gốc rồi thay thế các kết quả thu được ngược trở lại hàm Lagrange thì sẽ loại bỏ được các biến của bài toán gốc. Quay lại bài toán tìm siêu phẳng tối ưu, hàm Lagrange tương ứng của nó là: 1 1 1 1 . [ ( . ) 1 ] 2 l l l T T P i i i i i i i i L = w w C y w x b = = = + ξ − α + − + ξ − μ∑ ∑ ∑ i iξ (2.30) trong đó μi là các nhân tử Lagrange ứng với các tham biến mới ξi. Cho đạo hàm của LP triệt tiêu theo các biến w, ξ và b: 42 ( 0 l l i i i i i i i=1 i=1 L w, , ) w- y x w= y x w ∂ α μ = α = ⇔ α∂ ∑ ∑ (2.31) ( 0i i i L w, , ) C∂ α μ = −α −μ =∂ξ (2.32) ( 0 l i i i=1 L w, , ) y b ∂ α μ = α =∂ ∑ (2.33) Thay (2.31), (2.32) và (2.33) vào (2.30) sẽ thu được hàm mục tiêu của bài toán đối ngẫu: LD = , 1 1 , 1 1 1 1 1 0 1 . . 2 l l l l l l i j i j i j i i j i j i j i i i i i i i i j i i j i i i i y y x x C y y x x b y = = = = = = = α α + ξ − α α − α − α ξ + α − μ ξ∑ ∑ ∑ ∑ ∑ ∑  l = ∑ = , 1 1 10 1 . ( ) 2 l l i j i j i j i i i i i j i i y y x x C = = = − α α + ξ −α −μ +∑ ∑   l = α∑ = 1 , 1 1 . 2 l l i i j i j i i j i jy y x = = α − α α∑ ∑ x (2.34) Chú ý rằng, trong phần trình bày ở trên luận án sử dụng hai ký hiệu khác nhau LP và LD để phân biệt hàm Lagrange của bài toán gốc và hàm Lagrange của bài toán đối ngẫu. Trên thực tế, bài toán gốc và bài toán đối ngẫu có tập ràng buộc khác nhau và mục tiêu ”min”, ”max” cũng khác nhau nhưng chúng có chung một đáp án tối ưu theo lý thuyết đối ngẫu. Vì C - αi - μi = 0 và μi ≥ 0 suy ra αi ≤ C. Từ đó, việc giải bài toán tối ưu (2.15) sẽ tương đương với việc giải bài toán đối ngẫu sau đây: 1 , 1 1 . 2 l l i i j i j i i j max y y x x α = = α − α α∑ ∑ i j (2.35) 1 0 l i i i sao cho y = α =∑ (2.36) 0 ≤ αi ≤ C, i = 1,...,l (2.37) Điều kiện KKT (Karush-Kuhn-Tucker): Điều kiện tối ưu KKT của bài toán gốc có thể phát biểu như sau: 43 • Đạo hàm của LP phải triệt tiêu theo các biến w,b,ξ : xem (2.31), (2.32) và (2.33). • và , 1≤ i ≤ l( ( . ) 1) 0Ti i i iy w x bα + + ξ − (2.38) = 0=iiξμ (2.39) Khi giải bài toán đối ngẫu, hàm mục tiêu LD chỉ còn phụ thuộc vào các biến αi, vì vậy có một số nhận xét sau: i = C > 0, i = 1,...,l. 1. Nếu αi = 0 thì từ (2.32) ⇒ μi = C – α iξ = 0, i = 1,..., i = 1,...,Từ (2.39) ⇒ l. Do đó từ (2.38) ⇒ . ( ) 1Ti iy w .x b+ − ≥ 0, 0 l Điều này có nghĩa là mẫu có αi = 0 nằm về hai phía đối với H1 và H2. 2. Nếu 0 < αi < C, i = 1,...,l thì từ (2.38) ta có: ( ) 1Ti i iy w .x b+ +ξ − = , i = 1,...,l. (2.40) Mặt khác: μi = C – αi > 0 ⇒ iξ = 0, i = 1,...,l. Thế iξ vào phương trình (2.40) ta được: , i = 1,...,l. ( ) 1Ti iy w .x b+ − = 0 Điều này có nghĩa là mẫu có 0 < αi < C nằm trên hai siêu phẳng H1 hoặc H2. 3. Nếu αi = C, i = 1,...,l: từ (2.38) ta cũng suy ra được (2.40). Mặt khác: μi = C – αi = 0 và iξ ≥ 0, i = 1,...,l ⇒ ( ) 1Ti iy w .x b 0+ − ≤ , i = 1,...,l. Điều này có nghĩa là mẫu có αi = C là mẫu bị nhiễu (mẫu có khoảng cách đại số bé hơn khoảng cách lề của tập huấn luyện). Đặt Ri = , đại lượng này có thể được tính như sau: 1)( −+ bxwy iTi Ri = = 2)( iiTi ybxwy −+ ( ) i T i i E iy w x b y+ −  = yiEi trong đó Ei = = u i T i u w x b y+ −  i i – yi là lỗi dự đoán. Tóm lại, điều kiện KKT muốn nói rằng: 44 αi = 0 ⇒ Ri ≥ 0 (mẫu nằm về hai phía đối với H1 và H2), 0 < αi < C ⇒ Ri ≈ 0 (mẫu nằm trên hai siêu phẳng H1 hoặc H2), αi = C ⇒ Ri ≤ 0 (mẫu bị nhiễu). Trong hai trường hợp sau, điều kiện KKT bị vi phạm: • αi < C và Ri < 0, • αi > 0 và Ri > 0. Trong bài toán (2.35), các αi tương ứng với mỗi mẫu học. Khi đã huấn luyện xong, SVM chỉ lưu lại những mẫu có αi > 0, các mẫu này được gọi là các véc tơ tựa, còn tất cả các mẫu học khác có αi = 0 đều bị loại bỏ vì chúng không tham gia vào việc tạo siêu phẳng tối ưu. Điều kiện KKT là lý thuyết đóng vai trò rất quan trọng trong việc tìm lời giải của bài toán tối ưu. Bài toán huấn luyện SVM cũng chính là bài toán đi tìm lời giải thỏa mãn điều kiện KKT. Sau khi giải bài toán đối ngẫu (2.35), ta thu được các giá trị αi tương ứng với các mẫu (xi,yi), từ đó có thể tính được 1 l i i i i w α y x = =∑ và b theo (2.38). Khi đó, một mẫu x sẽ được phân lớp theo hàm quyết định: 0 . i i i isign α y x x b α ≠ ⎛ ⎞+⎜⎜⎝ ⎠∑ T f(x) = sign(w .x + b) = ⎟⎟ (2.41) 2.3. SVM PHI TUYẾN Hình 2.5. Ánh xạ dữ liệu vào không gian đặc trưng. 45 Trong các ứng dụng thực tế, thông thường các tập dữ liệu không khả tách tuyến tính, vì vậy đòi hỏi các máy huấn luyện phải sử dụng các hàm phân lớp mạnh hơn so với các hàm tuyến tính. Phần này sẽ mở rộng bài toán phân lớp SVM trong trường hợp tập dữ liệu huấn luyện không khả tách tuyến tính. Với tập dữ liệu không khả tách tuyến tính, có thể ánh xạ chúng sang một không gian khác với số chiều cao hơn sao cho trong không gian mới này tập dữ liệu sẽ khả tách tuyến tính (hình 2.5). 2.3.1. Không gian đặc trưng Cho ánh xạ biến đổi: : RD → H Φ x (x). Φ6 trong đó RD là không gian đầu vào và H là không gian có số chiều lớn hơn D (chiều của H cũng có thể vô hạn). Đối với dữ liệu không khả tách tuyến tính trong không gian RD thì mục tiêu của bài toán là tìm cách ánh xạ chúng sang không gian H sao cho ở trong không gian này chúng khả tách tuyến tính, H được gọi là không gian đặc trưng. Như vậy, hàm mục tiêu LD có thể viết lại: 1 , 1 1 ( ). ( ) 2 l l D i i j i j i j i i j L = y y x x = = α − α α Φ Φ∑ ∑ (2.42) Một vấn đề nảy sinh là làm thế nào để xử lý độ phức tạp tính toán xuất hiện trong (2.42) khi tích vô hướng ( ). ( )i jx xΦ Φ có số chiều rất lớn? Để giải quyết vấn đề này, một giải pháp hiệu quả khác là thay thế tích vô hướng ( ). ( )i jx xΦ Φ bằng một hàm nhân (kernel) K nào đó, giả sử = K(xi,xj). Với giải pháp này thì không cần phải tính trực tiếp tích vô hướng ( ). ( )i jx xΦ Φ ( ). ( )i jx xΦ Φ mà chỉ cần tính thông qua hàm nhân K(xi,xj). Bằng cách thay thế tích vô hướng ( ). ( )i jx xΦ Φ bởi một hàm nhân thích hợp, bài toán hoàn toàn có thể thực hiện được thông qua ánh xạ phi tuyến từ không gian đầu 46 vào sang không gian đặc trưng với số chiều cao hơn và việc tìm khoảng cách lề cực đại sẽ được thực hiện gián tiếp trong không gian đặc trưng mà không cần phải xác định rõ ánh xạ . Φ 2.3.2. Hàm nhân Vai trò của hàm nhân trong việc tìm siêu phẳng tối ưu là để tính tích vô hướng giữa hai véc tơ trong không gian đặc trưng. Vì vậy, các thuật toán huấn luyện SVM được thực hiện gián tiếp trong không gian đặc trưng thông qua hàm nhân. Một hàm nhân được định nghĩa như sau: Định nghĩa 2.6: Cho ánh xạ Φ từ không gian đầu vào X vào không gian đặc trưng F. ∀x,y∈X, một hàm nhân K có dạng K(x,y) = Φ(x).Φ(y) (2.43) Vấn đề đặt ra ở đây là làm thế nào để nhận biết một hàm có phải là hàm nhân hay không? Điều kiện Mercer sẽ cho biết một hàm cho trước có phải là hàm nhân hay không: Định lý 2.2: (Định lý Mercer) Để đảm bảo cho một hàm liên tục đối xứng K(x,y) trong không gian L2(C) có một khai triển 1 ( , ) ( ) ( )k k k k K x y a z x z y ∞ = =∑ (2.44) với các hệ số ak >0 (tức K(x,y) là tích vô hướng trong không gian đặc trưng), thì điều kiện cần và đủ là ( , ) ( ) ( ) 0 C C K x y g x g y dxdy ≥∫ ∫ (2.45) với mọi g∈L2(C) (C là một tập compact của RD). Sau đây là một số hàm nhân thông dụng: ƒ Hàm nhân tuyến tính: K(x, y) = x.y ƒ Hàm nhân đa thức: K(x, y) = ((x . y) + θ )d, d∈N, θ ∈R. 47 ƒ Hàm nhân Gausse (RBF - Radial Basic Function): 2 2 || || 2( , ) x y K x y e − − σ= Như vậy, bài toán tìm siêu phẳng tối ưu trong không gian đặc trưng sẽ được giải thông qua bài toán tối ưu sau: 1 , 1 1 ( , ) 2 l l i i j i j i i i j max y y K x x α = = α − α α∑ ∑ j (2.46) 1 0 l i i i sao cho y = α =∑ (2.47) 0 ≤ αi ≤ C, i = 1,...,l (2.48) Và hàm quyết định phân lớp cuối cùng có dạng: 0 ( ) ( , ) i i i if x sign y K x x b α ≠ ⎛ ⎞= α⎜⎜⎝ ⎠∑ + ⎟⎟ (2.49) 2.4. LÝ THUYẾT CHIỀU VC Các phần trên đã thảo luận về giải pháp tìm siêu phẳng tối ưu với khoảng cách lề cực đại bằng cách sử dụng hàm nhân trong một không gian đặc trưng với số chiều cao hơn. Vấn đề đặt ra trong phần này là tại sao siêu phẳng tối ưu phân lớp tốt hơn trong không gian đặc trưng với số chiều cao hơn? cụ thể hơn, tại sao một tập dữ liệu không khả tách tuyến tính trong không gian đầu vào lại trở nên khả tách tuyến tính trong không gian đặc trưng? Xét họ hàm {f(x,α)} (mỗi α tương ứng với một hàm cụ thể) và tập dữ liệu S gồm l điểm {xi,yi}i=1,..,l với xi∈RD và yi∈{-1,+1}. Mục đích của SVM là xây dựng máy huấn luyện M để xác định các hệ số α sao cho với mỗi mẫu xi thì M sẽ cho một kết quả là f(xi,α). Tuy nhiên, kết quả huấn luyện của máy M tại xi là f (xi,α) có thể bị sai lệch so với nhãn yi. Đại lượng 1 ( , ) 2 i i y f x− α được gọi là tổn thất (hay độ lệch) của máy M tại xi. 2.4.1. Cực tiểu hóa rủi ro cấu trúc 48 Theo lý thuyết xác suất, tập dữ liệu S có tất cả 2l cách gán nhãn, giả sử việc gán nhãn tuân theo một phân bố xác suất P(x,y) nào đó. Khi đó, gọi ),(),( 2 1)( yxdPxfyR ∫ −= αα (2.50) là rủi ro kỳ vọng, rủi ro thực tế (actual risk) hay rủi ro cấu trúc (Structural Risk) để nhấn mạnh điều mà bài toán thực sự quan tâm. Vấn đề đặt ra là xác định α để R(α) đạt cực tiểu. 2.4.2. Cực tiểu hóa rủi ro thực nghiệm Tuy nhiên, R(α) không thể tính được một cách trực tiếp vì chưa biết P(x,y). Do đó, phải cố gắng ước lượng hàm f(x,α) một cách tốt nhất dựa trên các thông tin đã biết, nghĩa là phải dựa trên tập dữ liệu huấn luyện S đã cho và cách lựa chọn hàm f(x,α). Thông thường, xấp xỉ việc cực tiểu hoá (2.50) bằng việc cực tiểu hoá rủi ro thực nghiệm: 1 1( ) | ( , ) | 2 l emp i i i R y f l = α = − α∑ x (2.51) Vapnik (1995) [9] đã chứng minh rằng: (log(2 / ) 1) log( / 4)( ) ( )emp h l hR R l + − η⎛α ≤ α + ⎜⎝ ⎠ ⎞⎟ (2.52) trong đó: 0 ≤ η 1, ≤ l là số mẫu huấn luyện, h là một số không âm được gọi là chiều VC. Trong (2.52) chỉ còn một giá trị chưa biết đó là h, nếu biết được h thì dễ dàng tính được vế phải. Vì vậy h là một trong những giá trị dùng để đánh giá khả năng phân lớp của họ hàm {f(x,α)}. Vế phải của (2.52) được gọi là cận rủi ro và phần căn thức được gọi là độ tin cậy VC. 49 Như vậy, việc giảm giá trị của vế phải của (2.52) sẽ làm giảm giá trị của R(α). Trên thực tế, không thể tính đuợc chính xác R(α), do đó mọi cố gắng của bài toán đều tập trung vào việc cực tiểu hóa cận rủi ro. Theo (2.52), khi h càng bé hay l càng lớn thì giá trị độ tin cậy VC càng nhỏ. 2.4.3. Cực tiểu hóa cận rủi ro Vì độ tin cậy VC là hàm đơn điệu tăng theo h nên để cực tiểu độ tin cậy VC, cần phải cực tiểu h. Hình 2.6. Độ tin cậy VC tăng theo h. Xét sự biến thiên của độ tin cậy VC theo h/l với độ tin cậy được chọn là 95% (η= 0.05) và tập mẫu học l =10.000 mẫu, ta có đồ thị ở hình 2.6. Cũng theo đồ thị trên, khi h/l > 0.37 thì độ tin cậy VC lớn hơn 1, điều này có nghĩa là bất đẳng thức (2.52) đánh giá rủi ro trở nên lỏng lẻo hơn. Hình 2.7. Họ hàm được chia làm các tập con theo chiều VC tăng dần. Trong bất đẳng thức đánh giá rủi ro (2.52) có ba thành phần: độ tin cậy VC phụ thuộc vào h (chiều VC của lớp hàm được chọn), còn rủi ro thực tế và rủi ro thực nghiệm lại phụ thuộc vào một hàm cụ thể nào đó được chọn ra trong quá trình huấn 50 luyện. Cần chỉ ra một tập con các hàm được chọn sao cho cận rủi ro đối với những hàm này đạt cực tiểu. Để thực hiện việc này, chia họ hàm thành các tập con lồng nhau (hình 2.7), với mỗi tập con ta phải tính được h hoặc giới hạn của h. Việc cực tiểu hóa rủi ro cấu trúc sau đó được thực hiện bằng cách xác định tập con của họ hàm có cận rủi ro đạt cực tiểu. Điều này được thực hiện bằng cách huấn luyện các máy khác nhau (mỗi máy tương ứng với một tập con các hàm) theo hướng cực tiểu hóa rủi ro thực nghiệm, sau đó chọn các máy đã được huấn luyện có tổng rủi ro thực nghiệm và độ tin cậy VC nhỏ nhất. Sau đây là một số định nghĩa và định lý quan trọng về chiều VC: Định nghĩa 2.7: Đối với mỗi cách gán nhãn trong số 2l cách gán nhãn của tập dữ liệu S, nếu tồn tại một α sao cho f(xi,α) = yi, ∀i=1,...,l thì ta nói tập dữ liệu S tách được bởi họ hàm {f(x,α)}. Định nghĩa 2.8:[9] Chiều VC (hay dimVC) của một họ hàm {f(x,α)} đối với tập dữ liệu S là số lượng phần tử lớn nhất trong một tập con của S tách được bởi họ hàm {f(x,α)}. Nếu dimVC = h thì tồn tại ít nhất một tập con h điểm của tập S tách được bởi họ hàm {f(x,α)}. Tuy nhiên, không phải mọi tập có không quá h điểm đều có thể tách được bởi họ hàm {f(x,α)}. Ví dụ, xét tập S trong R2 và họ hàm {f(x,α)} là tập các đường thẳng, nếu dimVC = 3 thì không phải với 3 điểm nào cũng tách được bởi họ các đường thẳng (hình 2.8). Hình 2.8. Không phải 3 điểm nào cũng tách được bởi đường thẳng. Định lý 2.3:[12] Cho k điểm {x1,x2,...,xk} trong không gian Rn. Các điểm này tách được bởi họ hàm các siêu phẳng nếu và chỉ nếu chúng độc lập tuyến tính, nghĩa là ∃xt∈{x1,x2,...,xk} sao cho hệ véc tơ { } 1kt j j j t x x =≠ JJJJG là độc lập tuyến tính. Hệ quả 2.3.1: DimVC của họ các siêu phẳng trong không gian Rn là n+1. 51 Chứng minh: Vì dimRn = n nên trong Rn luôn có một hệ véc tơ độc lập tuyến tính chứa n+1 phần tử và không thể có nhiều hơn thế. Theo định lý 2.3 suy ra điều phải chứng minh . Ví dụ: Trong không gian R2, dimVC của họ các đường thẳng là 3 (hình 2.9). Hình 2.9. Với 3 điểm không thẳng hàng trong R2 thì luôn tách được bởi đường thẳng. 2.5. CÁC THUẬT TOÁN HUẤN LUYỆN SVM Trong số những thuật toán thông dụng được thiết kế để huấn luyện SVM, có ba thuật toán kinh điển đã được cung cấp trong hầu hết ứng dụng SVM: thuật toán chặt khúc, thuật toán phân rã [12] và thuật toán SMO [13]. Ý tưởng chính của các thuật toán này có thể trình bày tóm tắt như sau: 2.5.1. Thuật toán chặt khúc Thuật toán này bắt đầu với một tập con bất kỳ (chunk) của tập dữ liệu huấn luyện, sau đó huấn luyện SVM theo một phương án tối ưu trên chunk dữ liệu vừa chọn. Tiếp đến, thuật toán giữ lại các véc tơ tựa (các mẫu có αi > 0) từ chunk sau khi đã loại bỏ các phần tử khác (tương ứng với αi = 0) và dùng các véc tơ tựa này để kiểm tra các phần tử trong phần còn lại của tập dữ liệu. Phần tử nào vi phạm điều kiện KKT thì được bổ sung vào tập các véc tơ tựa để tạo ra chunk mới. Công việc này được lặp đi lặp lại, việc khởi tạo lại α cho mỗi bài toán con mới phụ thuộc vào giá trị đầu ra của trạng thái trước đó và tiếp tục tối ưu bài toán con mới với các tham số tối ưu đã được lựa chọn. Thuật toán sẽ dừng lại khi thỏa mãn điều kiện tối 52 ưu. Chunk của dữ liệu tại thời điểm đang xét thường được hiểu như một tập làm việc (working set). Kích thước của tập làm việc luôn thay đổi, nhưng cuối cùng nó bằng số lượng αi ≠ 0 (bằng số lượng véc tơ tựa). Phương pháp này được sử dụng với giả thiết rằng ma trận Gram dùng để lưu tích vô hướng của từng cặp các véc tơ tựa phù hợp với kích thước bộ nhớ (có thể tính lại ma trận Gram bất cứ lúc nào khi thấy cần thiết, nhưng điều này sẽ làm giảm tốc độ huấn luyện). Trong thực nghiệm, có thể xẩy ra trường hợp số lượng véc tơ tựa quá lớn, làm cho ma trận Gram vượt quá khả năng lưu trữ của máy tính. 2.5.2. Thuật toán phân rã Thuật toán này khắc phục nhược điểm của thuật toán chặt khúc bằng cách cố định kích thước của bài toán con (kích thước của ma trận Gram). Vì vậy tại mọi thời điểm, một phần tử mới được bổ sung vào tập làm việc thì một phần tử khác bị loại ra. Điều này cho phép SVM có khả năng huấn luyện với tập dữ liệu lớn. Tuy nhiên, thực nghiệm cho thấy phương pháp này hội tụ rất chậm. Trong thực nghiệm, có thể chọn mỗi lần vài mẫu để bổ sung vào hoặc loại bỏ ra khỏi bài toán con để tăng tốc độ hội tụ. Thuật toán này được trình bày tóm tắt như sau: Input: - Tập S gồm l mẫu huấn luyện {(xi,yi)}i=1,..,l - Kích thước của Working Set B là m. Output: Tập {αi}i=1,...,l 1. Khởi tạo • Đặt các αi = 0; • Chọn Working Set B với kích thước m; 2. Tìm nghiệm tối ưu 53 Repeat • Giải bài toán tối ưu cục bộ trên B; • Cập nhật lại B; Until ; 2.5.3. Thuật toán SMO SMO là một thuật toán đơn giản để giải bài toán QP một cách nhanh chóng mà không cần lưu trữ ma trận Gram và cũng không cần phải giải bài toán QP ở mỗi bước. Thuật toán này phân rã bài toán QP tổng quát thành các bài toán con, sử dụng định lý của Osuma [85] để đảm bảo sự hội tụ. Khác với các thuật toán trước, SMO chỉ giải các bài toán tối ưu với kích thước nhỏ nhất. Tại mỗi bước lặp, SMO chọn hai nhân tử Lagrange để giải, tìm các giá trị tối ưu cho hai nhân tử này và cập nhật lại các tham số của SVM. Ưu điểm của thuật toán này là có thể tối ưu hai nhân tử Lagrange bằng giải pháp phân tích, vì vậy không cần phải giải bài toán QP. Hơn nữa, SMO không đòi hỏi lưu trữ ma trận Gram, vì vậy các bài toán huấn luyện SVM với số lượng mẫu lớn có thể lưu trữ ở bộ nhớ trong của một một máy tính cá nhân bình thường. Thuật toán SMO thực hiện hai công việc chính: Giải bài toán tối ưu cho hai nhân tử Lagrange bằng phương pháp phân tích và chọn hai nhân tử để tối ưu bằng phương pháp lựa chọn heuristic. 2.5.3.1. Tối ưu hai nhân tử Lagrange Không mất tính tổng quát, giả sử đang tối ưu hai phần tử αi, αj từ một tập các phương án trước đó: , , αold1α old2α 3, ..., αl (để khởi tạo, có thể đặt αold=0). Vì , ta có: 1 0 l i i i α y = =∑ y1α1 + y2α2 = y1 old1α + y2 old2α = Const (2.53) Cố định các αi khác, hàm mục tiêu trở thành hàm hai biến và có thể được viết lại: 54 ( 2 21 2 1 1 1 1 1 2 2 2 2 2 1 2 1 2 1 1 1 1 2 2 2 3 2 2 ( ) T T T D l T i i i i 1L Const- y y x x y y x x y y x x 2 y x y x y x Const = = α +α + α + α + α α ⎞⎛ ⎞+ α α + α + ⎟⎜ ⎟⎝ ⎠ ⎠∑ 2 (2.54) Đặt K11 = x1Tx1, K22 = x2Tx2, K12 = x1Tx2 và η = 2K12 – K11 – K22 (tính toán chi tiết có thể tham khảo ở [13]). Tiếp tục cố định α1, hàm mục tiêu sẽ trở thành hàm một biến theo α2: 2 2 2 1 2 2 2 1 ( ( ) ) 2 old old old DL y E E Const= ηα + − −ηα α + (2.55) trong đó . Vì hàm mục tiêu chứa nên không cần phải tính b trong mỗi bước lặp. 1 ( , ) l old old i k k k i k E y K x x b = = α + −∑ iy 21old oldE E− Lấy đạo hàm cấp một và cấp hai theo α2: 2 2 1 2 2 2 ( ( ) )old old oldDL y E E∂ = ηα + − −ηα∂α (2.56) 2 2 2 DL∂ = η∂α (2.57) Cho đạo hàm cấp một bằng 0, ta có: 2 2 1 2 2 ( old oldold y E E−α = α + η ) (2.58) Vì α2 cũng phải thỏa mãn ràng buộc 0 ≤ α2 ≤ C nên giá trị mới của α2 phải cắt xén để đảm bảo một đáp án khả thi: Low ≤ α2 ≤ Hight (2.59) trong đó ƒ nếu y1≠ y2 thì old old 2 1Low=max(0, - )α α (2.60) old old 1 2Hight=min(C,C- + )α α (2.61) 55 ƒ ngược lại: old old 1 2Low=max(0, -C)α +α (2.62) old old 1 2Hight=min(C, + )α α (2.63) Và giá trị α1 tính được từ α2 như sau: 1 1 1 2 2 2( old oldy yα = α + α −α ) (2.64) 2.5.3.2. Chọn hai nhân tử để tối ưu theo phương pháp heuristic Việc chọn hai nhân tử αi, αj cho bài toán tối ưu trong thuật toán SMO được thực hiện như sau: • Ở vòng lặp ngoài chọn αi; vòng lặp trong chọn αj sao cho |Ej-Ei| cực đại. • Ở vòng lặp ngoài, luân phiên duyệt qua tất cả các mẫu và các véc tơ tựa (các mẫu có 0 < αi < C) (ưu tiên duyệt qua các véc tơ tựa, nếu không tìm thấy mới duyệt toàn bộ mẫu) để chọn ra một mẫu vi phạm điều kiện KKT. • Với αi được chọn, vòng lặp trong tìm kiếm một mẫu αj sao cho |Ej – Ei| cực đại. Đầu tiên nó duyệt qua các véc tơ tựa, nếu không tìm được mới duyệt qua toàn bộ mẫu. 2.6. SVM ĐA LỚP SVM chỉ là bài toán phân lớp nh