CHƯƠNG 1. CƠ SỞ TOÁN HỌC CỦA SVM Trong chương này, trước tiên chúng tôi cung cấp các khái niệm và kết quả cơ bản về toán mà sẽ được dùng xuyên suốt nội dung luận án. Cụ thể đó là hàm toàn phương, bài toán quy hoạch toàn phương (QP), điều kiện tối ưu của bài toán QP, bài toán đối ngẫu của bài toán QP lồi. Tiếp theo là trình bày về cơ sở toán học của SVM cho các trường hợp từ đơn giản đến phức tạp.
Hàm toàn phương Trong suốt luận án này hàm toàn phương luôn được trình bày dưới dạng chuẩn như sau: 1 Q(x) = xT Gx + gT x + α; x ∈ Rn , (1.1) 2 trong đó, G ∈ Rn×n là một ma trận vuông đối xứng, g, x ∈ Rn là các véc-tơ cột và α ∈ R là một số thực. Kí hiệu T để chỉ chuyển vị của một ma trận hay véc-tơ. Hàm toàn phương (1.1) có gradient và Hessian được tính trực tiếp như sau: ∇Q(x) = Gx + g; ∇2 Q(x) = G.2) Do đó, hàm Q lồi khi và chỉ khi G là ma trận nửa xác định dương. Hơn nữa, khi G xác định dương thì Q là hàm lồi chặt.
Bài toán quy hoạch toàn phương (QP) Bài toán quy hoạch toàn phương là một dạng đơn giản của bài toán tối ưu. Cụ thể, đó là bài toán với hàm mục tiêu là hàm toàn phương và các ràng buộc tuyến tính. Bài toán quy hoạch toàn phương, kí hiệu (QP), có dạng tổng quát như sau: Q(x) = 21 xT Gx + gT x + α −→ min, (QP) : aTi x ≥ bi , i ∈ I := {1, 2,. , k}, 7 Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM trong đó G là ma trận vuông đối xứng cấp n; g, ai , cj là các véc-tơ, α, bi , dj là các số thực, còn I và J là tập hợp hữu hạn các chỉ số: I = {1,.
Khi G là ma trận nửa xác định dương, tức hàm mục tiêu Q lồi, ta có bài toán quy hoạch toàn phương lồi. Ta có thể biểu diễn bài toán gọn hơn dưới dạng ma trận. Cụ thể, đặt A = [a1 , a2 ,. , am ]T là ma trận cấp m × n, gồm m véc-tơ hàng aTi , C = [c1 , c2 ,.
, ck ]T là ma trận cấp k × n, gồm k véc-tơ hàng cTj , b ∈ Rm và d ∈ Rk là các véc-tơ cột với các thành phần bi và dj. Lúc đó, bài toán có thể viết lại dưới dạng ma trận như sau: Q(x) = 21 xT Gx + gT x + α −→ min, (QP) : Ax ≥ b, Cx = d. Điều kiện tối ưu của bài toán QP Định lý 1. (a) Giả sử x∗ là nghiệm của bài toán QP được cho ở (1.
Khi đó tồn tại các bộ hệ số λ∗ = (λ∗1 ,. , µ∗k ) ∈ Rk thoả mãn: Xm X k ∗ µ∗j cj , ∗ Gx + g = λ a + i i i=1 j=1 T ∗ ai x ≥ bi , λ∗i ≥ 0, i ∈ I, (1.4) được gọi là hệ KKT (Karush − Kuhn − T ucker) của bài toán quy hoạch toàn phương (1.3), x∗ được gọi là điểm KKT, và các hệ số λ∗ , µ∗ được gọi là các nhân tử Lagrange tương ứng với x∗. (b) Nếu G là ma trận nửa xác định dương, và nếu x∗ là một điểm KKT cùng với các nhân tử Lagrange λ∗ , µ∗ , thì x∗ cũng là nghiệm của bài toán QP. Như vậy, nếu QP là bài toán quy hoạch toàn phương lồi, thì việc tìm nghiệm của bài toán tương đương với việc tìm điểm KKT của nó.
8 Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM Chú ý rằng, hệ KKT có thể viết lại dưới dạng ma trận như sau: Gx∗ + g = AT λ∗ + CT µ∗ , Ax∗ ≥ b, λ∗ ≥ 0, (1. Bài toán đối ngẫu Mục này trình bày cách lập bài toán đối ngẫu của quy hoạch toàn phương lồi. Đối với một số lớp bài toán thực tiễn ta có thể khai thác cấu trúc đặc biệt của bài toán đối ngẫu để giải bài toán ban đầu một cách hiệu quả hơn. Để đơn giản ta xét bài toán QP với α = 0.
Với mỗi bài toán quy hoạch toàn phương lồi ta xét bài toán đối ngẫu tương ứng. Giả sử bài toán QP ở (1.3) lồi, tức G là ma trận nửa xác định dương. Ta có hàm Lagrange của bài toán là 1 L(x, λ, µ) = xT Gx + gT x − λT (Ax − b) − µT (Cx − d), (1.6) 2 ∗ với các biến (x, λ, µ) ∈ Rn × Rm k + × R. Lúc này, điểm KKT x cùng với các nhân tử Lagrange λ∗ , µ∗ chính là điểm yên ngựa (x∗ , λ∗ , µ∗ ) của hàm L và thỏa mãn hệ KKT (1.5), hay thỏa mãn điều kiện tối ưu (Định lí 1.
Thực ra, điều kiện KKT (1.5) chính là: ∇x L = 0, ∇λ L ≥ 0, λ ≥ 0, λ∇λ L = 0, ∇µ L = 0 Bài toán QP lúc đó tương đương với bài toán minimax sau: inf sup L(x, λ, µ).8) (λ,µ)∈Rm k x∈R + ×R Với giả thiết G là nửa xác định dương, với mỗi (λ, µ), ta giải bài toán inf L(x, λ, µ), x∈Rn 9 Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM theo cách sau. Từ phương trình dừng ∇x L(x, λ, µ) = Gx + g − AT λ − CT µ = 0, giải ra ta được nghiệm x (phụ thuộc (λ, µ)) thoả mãn Gx = AT λ + CT µ − g hay g = AT λ + CT µ − Gx. Thay vào hàm Lagrange ta có 1 L(x, λ, µ) = xT Gx + gT x − λT (Ax − b) − µT (Cx − d) 2 1 T = x Gx + (λT A + µT C − xT G)x − λT (Ax − b) − µT (Cx − d) 2 1 = − xT Gx + λT b + µT d. 2 Vì vậy bài toán đối ngẫu chính là: − 21 xT Gx + λT b + µT d −→ max, λ ∈ Rm k +, µ ∈ R , (1.9) Gx = AT λ + CT µ − g.
Nếu G là xác định dương thì từ Gx = AT λ + CT µ − g suy ra x = G−1 (AT λ + CT µ − g), nên hàm mục tiêu của (1.9) là 1 1 − xT Gx + λT b + µT d = − (AT λ + CT µ − g)T G−1 (AT λ + CT µ − g) + λT b + µT d. 2 2 Do đó, bài toán đối ngẫu (1.9) trở thành − 1 (AT λ + CT µ − g)T G−1 (AT λ + CT µ − g) + λT b + µT d −→ max, 2 λ ∈ Rm ; µ ∈ Rk. + Đây cũng là một bài toán quy hoạch toàn phương lồi, với dạng đơn giản hơn nhiều bài toán QP ban đầu. Phần sau của chương, luận án trình bày chi tiết về cơ sở toán học của thuật toán SVM cho bài toán phân loại hai lớp dữ liệu.
10 Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM 1. Bài toán phân lớp dữ liệu Xét bài toán phân loại nhị phân có tập dữ liệu được kí hiệu bởi ma trận C ⊂ Rm×n , bao gồm m điểm (mỗi điểm là một hàng của C) xTj ∈ Rn , 1 ≤ j ≤ m. Giả sử rằng, yj ∈ Ω = {−1, 1} là nhãn của điểm dữ liệu xj. Lớp {+} gồm mA điểm và được kí hiệu bởi ma trận A ⊂ RmA ×n , lớp {−} gồm mB điểm được kí hiệu bởi ma trận B ⊂ RmB ×n.
Điểm dữ liệu xi được xếp vào lớp A nếu tương ứng ta có yi = 1, và được xếp vào lớp B nếu yi = −1. Bài toán đặt ra là: Cần tìm một hàm phân lớp f : Rn → {−1, 1} thỏa mãn: f (xi ) = yi , ∀ i ∈ Q := {1, 2, .10) Để hiểu ý nghĩa của bài toán này ta xét ví dụ sau. Trong mùa dịch sốt xuất huyết, tại một trung tâm y tế X người ta đã tiếp nhận và đã có hồ sơ bệnh án đầy đủ của 100 bệnh nhân. Thông tin của mỗi bệnh nhân được số hóa thành một véc-tơ x ∈ R9 gồm các thành phần: giới tính, tuổi, cân nặng, nhiệt độ, huyết áp, đau đầu, đau bụng, buồn nôn (trong đó huyết áp là cặp số, giới tính, đau đầu, đau bụng, buồn nôn được số hóa bởi 0 hoặc 1).
Chẳng hạn, x = (1, 25, 57, 39, 90, 150, 1, 1, 0) biểu thị cho bệnh nhân nam, 25 tuổi, nặng 57 kg, thân nhiệt 39◦ C, huyết áp 150/90, có triệu chứng đau đầu, đau bụng, nhưng không buồn nôn. Với mỗi bệnh nhân xi như vậy sau một thời gian điều trị ta đã biết người ấy có bị sốt xuất huyết (và gán yi = 1) hay không (gán yi = −1). Trên cơ sở m = 100 mẫu thử như thế chúng ta cần thiết lập một hàm f : R9 → {−1, 1} nhằm để chẩn đoán cho những bệnh nhân mới. Dĩ nhiên hàm f đó khi thực hiện trên các mẫu cũ phải cho chẩn đoán đúng, nghĩa là f (xi ) = yi với mọi i ∈ {1, 2,.
Trở lại bài toán ở (1. Nếu có một hàm g : Rn → R sao cho g(xi ) > 0 với mọi xi ∈ A, và g(xi ) < 0 với mọi xi ∈ B, thì hiển nhiên ta có thể chọn f (x) = sgn(g(x)) để làm hàm phân lớp. Lúc đó mặt mức Sg = {x ∈ Rn | g(x) = 0} được gọi là mặt biên hay mặt quyết định (xem Hình 1. Mặt quyết định chia Rn ra làm hai miền, tương ứng với hai lớp A và B.
Đặc biệt nếu g là hàm affine: g(x) = wT x + b (w ∈ Rn , b ∈ R; wT x là tích vô hướng của w và x) thì Sg là một siêu phẳng nhận w làm véc-tơ pháp mà ta gọi là mặt quyết định tuyến tính (xem Hình 1. Ngược lại, nếu g không phải là hàm affine, ta nói mặt quyết định là phi tuyến. 11 Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM Hình 1.1: Mặt quyết định phi tuyến Hình 1.