Tổng quan về luận án
Trong kỷ nguyên bùng nổ dữ liệu số và trí tuệ nhân tạo, phân lớp mẫu (pattern classification) đóng vai trò nền tảng của học máy có giám sát (supervised machine learning). Một trong những kỹ thuật phân loại kinh điển và mạnh mẽ nhất là máy véc-tơ hỗ trợ (Support Vector Machine - SVM) do Vladimir Vapnik và cộng sự đề xuất (Vapnik, 1995). Dựa trên nguyên lý Cực tiểu hóa Rủi ro Cấu trúc (Structural Risk Minimization - SRM), SVM tối ưu hóa biên phân cách (margin maximization) để đạt được biên độ tổng quát hóa vượt trội so với các thuật toán dựa trên Cực tiểu hóa Rủi ro Thực nghiệm (Empirical Risk Minimization - ERM). Tuy nhiên, trước các cấu trúc dữ liệu hiện đại với tính chất đa cụm phức tạp, phân phối không đồng nhất và độ mất cân bằng nghiêm trọng, thuật toán SVM truyền thống bộc lộ những giới hạn căn bản về độ chính xác và chi phí tính toán. Luận án tiến sĩ khoa học máy tính với đề tài "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" của nghiên cứu sinh Nguyễn Thế Cường, dưới sự hướng dẫn khoa học của PGS. Huỳnh Thế Phùng tại Trường Đại học Khoa học, Đại học Huế (2023), đã giải quyết trực diện bài toán khoa học mang tính thời sự này.
+-----------------------------------------------------------------------------------+
| TỔNG HỢP CẤU TRÚC KHOA HỌC CỦA LUẬN ÁN |
+-----------------------------------------------------------------------------------+
| 1. CƠ SỞ TOÁN HỌC & TỐI ƯU HÓA |
| - Quy hoạch toàn phương (QP), Điều kiện Karush-Kuhn-Tucker (KKT) |
| - Đối ngẫu Lagrange (Lagrange Duality), Công thức Sherman-Morrison-Woodbury |
+-----------------------------------------------------------------------------------+
| 2. KHOẢNG TRỐNG NGHIÊN CỨU (RESEARCH GAPS) |
| - SVM/PSVM/GEPSVM/TSVM bỏ qua cấu trúc phân phối đa cụm nội tại |
| - S-TSVM (Qi et al., 2013) chưa đánh trọng số theo quy mô điểm dữ liệu cụm |
| - Chi phí tính toán QP cấp O(m^3) gây nghẽn cổ chai với dữ liệu lớn |
+-----------------------------------------------------------------------------------+
| 3. MÔ HÌNH ĐỀ XUẤT ĐỘT PHÁ |
| - Chiến lược Lớp-đối-Cụm (Class-vs-Cluster): Thuật toán WS-SVM & ILS-SVM |
| - Chiến lược Cụm-đối-Lớp (Cluster-vs-Class): Thuật toán WLS-SVM |
| - Khai thác ma trận hiệp phương sai Sigma_{Ai}, Sigma_{Bj} & trọng số m_{Ai} |
+-----------------------------------------------------------------------------------+
| 4. PHƯƠNG PHÁP GIẢI & ĐÁNH GIÁ THỰC NGHIỆM |
| - Giải hệ phương trình tuyến tính (SLEs) qua Bình phương tối thiểu (LS) |
| - Phân cụm liên kết Ward (Ward's Hierarchical Clustering) |
| - Kiểm thử 10-fold CV trên bộ dữ liệu tổng hợp 2D và tập chuẩn quốc tế UCI |
+-----------------------------------------------------------------------------------+
Khoảng trống nghiên cứu (research gap) cốt lõi được luận án chỉ ra: SVM tiêu chuẩn và các biến thể mở rộng như Proximal SVM (PSVM) (Mangasarian, 2001), Generalized Eigenvalue Proximal SVM (GEPSVM) (Mangasarian & Wild, 2006), Twin SVM (TSVM) (Jayadeva et al., 2007), hay Least Squares TSVM (LSTSVM) (Kumar & Gopal, 2009) đều xây dựng ranh giới quyết định dựa trên giả định mỗi lớp dữ liệu là một khối thuần nhất hoặc tìm kiếm một/hai siêu phẳng toàn cục. Ngay cả mô hình Structural TSVM (S-TSVM) của Qi et al. (2013) dù đã bước đầu tích hợp thông tin ma trận hiệp phương sai, vẫn chưa khai thác trọn vẹn thông tin về số lượng điểm dữ liệu của từng cụm và chưa xây dựng được cơ chế đa siêu phẳng linh hoạt cho từng cụm đối kháng. Điều này dẫn đến sự suy giảm nghiêm trọng về hiệu năng phân lớp khi gặp dữ liệu thực tế: trong một lớp có nhiều cụm dữ liệu với hình dạng phân tán khác nhau, mật độ không đồng đều, hoặc khi xảy ra hiện tượng mất cân bằng mẫu (imbalanced data) với tỷ lệ chênh lệch lên đến 90% (lớp đa số) so với 10% (lớp thiểu số).
Luận án tập trung giải quyết 2 câu hỏi nghiên cứu (Research Questions - RQ) và 2 giả thuyết khoa học (Hypotheses - H):
- RQ1: Làm thế nào để mô hình hóa toàn diện cấu trúc hình học nội tại (intra-cluster covariance) và trọng số kích thước mẫu của từng cụm dữ liệu vào bài toán tối ưu phân lớp nhị phân?
- RQ2: Làm thế nào để giảm thiểu độ phức tạp tính toán từ việc giải bài toán quy hoạch toàn phương (QP) kích thước lớn sang các bài toán QP quy mô nhỏ hơn hoặc hệ phương trình tuyến tính (SLEs) mà vẫn đảm bảo tính toàn cục và độ chính xác phân lớp?
- H1: Tích hợp đồng thời ma trận hiệp phương sai của từng cụm $\Sigma_{Ai}, \Sigma_{Bj}$ và trọng số tỷ lệ kích thước điểm dữ liệu $m_{Ai}, m_{Bj}$ vào hàm mục tiêu tối ưu sẽ nâng cao đáng kể độ chính xác phân lớp trên không gian đa cấu trúc phức tạp.
- H2: Thay thế cấu trúc 2 siêu phẳng truyền thống bằng chiến lược đa siêu phẳng "lớp-đối-cụm" (Class-vs-Cluster) và "cụm-đối-lớp" (Cluster-vs-Class) kết hợp phương pháp bình phương tối thiểu (Least Squares) sẽ giảm độ phức tạp thời gian huấn luyện từ $O(m^3)$ xuống cấp số giải tích nhanh vượt trội, triệt tiêu sự phụ thuộc vào các thuật toán giải QP lặp tốn kém.
Khung lý thuyết của công trình được neo giữ trên nền tảng: Lý thuyết tối ưu lồi (Convex Optimization), Lý thuyết nhân tử Lagrange và hệ điều kiện Karush-Kuhn-Tucker (KKT), Bổ đề giảm chiều nghịch đảo ma trận Sherman-Morrison-Woodbury (SMW), và Lý thuyết phân cụm thứ bậc liên kết của Ward (Ward's Hierarchical Clustering). Đóng góp mang tính đột phá của luận án là đề xuất 3 thuật toán hoàn toàn mới: WS-SVM (Weighted Structural SVM), ILS-SVM (Improvement Least Squares SVM), và WLS-SVM (Weighted Least Squares SVM). Các mô hình này được kiểm định chặt chẽ trên các tập dữ liệu giả lập 2 chiều và hệ thống dữ liệu thực nghiệm chuẩn từ kho lưu trữ quốc tế UCI Machine Learning Repository, mang lại giá trị lý thuyết sâu sắc và ứng dụng thực tiễn to lớn trong chẩn đoán y khoa, nhận dạng mẫu thông minh.
Literature Review và Positioning
Lịch sử phát triển của các thuật toán phân lớp trên nền tảng SVM trải qua nhiều bước tiến quan trọng về mặt tối ưu hóa và cấu trúc hình học không gian. Thuật toán SVM tiêu chuẩn (Vapnik, 1995; Cortes & Vapnik, 1995) giải bài toán quy hoạch toàn phương lồi với hàm mục tiêu $\min \frac{1}{2}|w|^2 + c \sum \xi_i$, tìm một siêu phẳng duy nhất cách đều hai lớp với lề cực đại. Để giải quyết bài toán này, phương pháp nhân tử Lagrange đưa về bài toán đối ngẫu có ma trận nhân hạch dày đặc cỡ $m \times m$ ($m$ là tổng số mẫu), dẫn đến độ phức tạp thời gian $O(m^3)$, tạo nên điểm nghẽn nghiêm trọng khi dữ liệu huấn luyện mở rộng quy mô.
+-----------------------------------------------------------------------------------+
| TIẾN TRÌNH TIẾN HÓA CỦA CÁC BIẾN THỂ SVM |
+-----------------------------------------------------------------------------------+
| Vapnik (1995): Standard SVM (1 siêu phẳng, QP quy mô lớn O(m^3)) |
| | |
| +---> Mangasarian (2001): PSVM (2 siêu phẳng song song, SLEs) |
| | |
| +---> Mangasarian & Wild (2006): GEPSVM (2 siêu phẳng không song song) |
| | | |
| | +---> Jayadeva et al. (2007): TSVM (2 bài toán QP nhỏ hơn, O(m^3/4)) |
| | | |
| | +---> Kumar & Gopal (2009): LSTSVM (2 hệ SLEs cực nhanh) |
| | | |
| | +---> Qi et al. (2013): S-TSVM (Khai thác hiệp phương sai) |
| | | |
| +--------------------------+ |
| | |
| v |
| Luận án Nguyễn Thế Cường (2023): |
| - WS-SVM & ILS-SVM: Chiến lược Lớp-đối-Cụm (l + k siêu phẳng) |
| - WLS-SVM: Chiến lược Cụm-đối-Lớp (k + l siêu phẳng) + Trọng số quy mô cụm |
+-----------------------------------------------------------------------------------+
Nhằm khắc phục chi phí tính toán của SVM, Mangasarian (2001) đề xuất Proximal SVM (PSVM), thay thế ràng buộc bất đẳng thức bằng ràng buộc đẳng thức, biến bài toán QP thành giải hệ phương trình tuyến tính (SLEs). Tuy nhiên, PSVM bị giới hạn bởi việc chỉ tìm 2 siêu phẳng song song bao bọc lấy 2 lớp. Bước đột phá tiếp theo đến từ GEPSVM (Mangasarian & Wild, 2006) khi tìm 2 siêu phẳng không nhất thiết song song thông qua bài toán giải trị riêng suy rộng (Generalized Eigenvalues) dựa trên thương số Rayleigh $\min r(z) = \frac{z^T G z}{z^T H z}$. Dẫu vậy, việc giải bài toán tối ưu không ràng buộc khiến GEPSVM kém ổn định và độ chính xác phân lớp bị suy giảm.
Năm 2007, Jayadeva, Khemchandani và Chandra giới thiệu Twin Support Vector Machine (TSVM), tạo nên một bước ngoặt lớn trong lý thuyết SVM. Thay vì giải một bài toán QP lớn, TSVM giải 2 bài toán QP nhỏ hơn với số biến lần lượt là $m_B$ và $m_A$: $$\text{Độ phức tạp TSVM: } O\left(2 \times \left(\frac{m}{2}\right)^3\right) = O\left(\frac{m^3}{4}\right)$$ Tốc độ huấn luyện của TSVM nhanh gấp xấp xỉ 4 lần so với SVM tiêu chuẩn. Để đẩy nhanh tốc độ hơn nữa, Kumar và Gopal (2009) đề xuất Least Squares TSVM (LSTSVM), chuyển các ràng buộc bất đẳng thức trong TSVM thành đẳng thức, biến việc huấn luyện thành giải 2 hệ phương trình tuyến tính với nghiệm giải tích tường minh $z_+ = -[\frac{1}{c_+}H^T H + G^T G]^{-1} G^T e_B$, đạt tốc độ tính toán vượt bậc.
Tuy nhiên, một cuộc tranh luận học thuật lớn nảy sinh: Các mô hình TSVM và LSTSVM xử lý rất tốt dữ liệu có phân phối hình học đơn giản, nhưng lại hoàn toàn bất lực trước dữ liệu đa cấu trúc (multi-cluster structure). Trong thực tế, một lớp nhị phân thường bao gồm nhiều cụm phân tán riêng biệt với ma trận hiệp phương sai khác nhau (ví dụ: bài toán phân loại quả da trơn gồm Xoài, Táo, Nho đối kháng với lớp da xù xì gồm Mít, Dứa). Qi, Tian và Shi (2013) đã đề xuất Structural TSVM (S-TSVM) nhằm tích hợp thông tin ma trận hiệp phương sai $\Sigma_+ = \sum_{i=1}^k \Sigma_{i+}$ vào số hạng chính quy hóa $w_+^T \Sigma_+ w_+$.
Mặc dù vậy, S-TSVM của Qi et al. (2013) vẫn bộc lộ hai điểm hạn chế cốt tử mà luận án của Nguyễn Thế Cường đã định vị và khắc phục triệt để:
- S-TSVM chỉ gộp chung tổng các ma trận hiệp phương sai của tất cả các cụm trong một lớp vào 1 siêu phẳng duy nhất, làm triệt tiêu các đặc trưng phân bố hình học cục bộ riêng biệt của từng cụm nhỏ.
- S-TSVM xem trọng số của mọi cụm là như nhau, bỏ qua thông tin về số lượng điểm dữ liệu $m_{Ai}, m_{Bj}$ trong từng cụm, khiến cho các cụm có kích thước áp đảo làm sai lệch mặt phân cách của các cụm thiểu số.
So sánh với hai nghiên cứu quốc tế tiêu biểu là TSVM (Jayadeva et al., 2007) và S-TSVM (Qi et al., 2013), luận án xác lập vị thế tiên phong khi chuyển đổi toàn bộ kiến trúc từ mô hình 2 siêu phẳng toàn cục sang kiến trúc đa siêu phẳng linh hoạt $(l+k)$ hoặc $(k+l)$, tích hợp trọng số quy mô cụm và ma trận hiệp phương sai chuẩn hóa, giải quyết dứt điểm bài toán phân lớp dữ liệu đa cấu trúc không đồng nhất.
Đóng góp lý thuyết và khung phân tích
Đóng góp cho lý thuyết
Luận án đã mở rộng đáng kể lý thuyết tối ưu hóa và máy học thống kê thông qua các đóng góp lý thuyết nền tảng:
Thứ nhất, luận án mở rộng khung lý thuyết Cực tiểu hóa Rủi ro Cấu trúc (SRM) của Vapnik sang không gian phân phối dữ liệu đa cụm nội tại (intra-class multi-cluster distribution). Bằng cách đưa số hạng hiệu chỉnh phương sai hình chiếu cụm $\frac{1}{2}\lambda_+ w_+^T \Sigma_{Ai} w_+$ vào hàm mục tiêu, luận án chứng minh rằng siêu phẳng quyết định tối ưu sẽ có xu hướng định hướng song song với trục phân tán chính của từng cụm dữ liệu, giảm thiểu tối đa phương sai dư thừa theo phương pháp giải tích.
+-----------------------------------------------------------------------------------+
| KHUNG PHÂN TÍCH LỚP-ĐỐI-CỤM & CỤM-ĐỐI-LỚP |
+-----------------------------------------------------------------------------------+
| LỚP DỮ LIỆU DƯƠNG A (k cụm: A_1, A_2, ..., A_k; số điểm m_A1, ..., m_Ak) |
| LỚP DỮ LIỆU ÂM B (l cụm: B_1, B_2, ..., B_l; số điểm m_B1, ..., m_Bl) |
+-----------------------------------------------------------------------------------+
| CHIẾN LƯỢC 1: LỚP-ĐỐI-CỤM (CLASS-VS-CLUSTER) |
| -> Tìm (l + k) siêu phẳng: |
| * l siêu phẳng: Gần toàn bộ lớp A, cách xa từng cụm B_j của lớp B |
| * k siêu phẳng: Gần toàn bộ lớp B, cách xa từng cụm A_i của lớp A |
| -> Mô hình: WS-SVM (đối ngẫu Lagrange QP) & ILS-SVM (Bình phương tối thiểu SLEs) |
+-----------------------------------------------------------------------------------+
| CHIẾN LƯỢC 2: CỤM-ĐỐI-LỚP (CLUSTER-VS-CLASS) |
| -> Tìm (k + l) siêu phẳng: |
| * k siêu phẳng: Gần từng cụm A_i của lớp A, cách xa toàn bộ lớp B |
| * l siêu phẳng: Gần từng cụm B_j của lớp B, cách xa toàn bộ lớp A |
| -> Mô hình: WLS-SVM (Trọng số thích nghi + Bình phương tối thiểu SLEs) |
+-----------------------------------------------------------------------------------+
Thứ hai, thiết lập tính tương đương giải tích giữa bài toán quy hoạch toàn phương lồi chặt với ràng buộc đẳng thức và hệ phương trình đại số tuyến tính có nghiệm đóng. Luận án đã chứng minh chặt chẽ về mặt toán học rằng, việc áp dụng bổ đề Sherman-Morrison-Woodbury cho các ma trận khối dạng $[H^T H + \mu I + \lambda F]$ không chỉ bảo toàn tính xác định dương của ma trận Hessian mà còn triệt tiêu hoàn toàn rủi ro suy biến bậc ma trận trong không gian đặc trưng Hilbert vô hạn chiều.
Khung phân tích độc đáo
Khung phân tích của luận án được cấu thành từ hai chiến lược toán học độc đáo:
1. Chiến lược Lớp-đối-Cụm (Class-vs-Cluster - Thuật toán WS-SVM và ILS-SVM): Thay vì tìm 2 siêu phẳng như TSVM, chiến lược này tìm tổng cộng $(l + k)$ siêu phẳng:
- $l$ siêu phẳng có dạng $f_{+j}(x) = w_{+j}^T x + b_{+j} = 0$ ($j = 1, \dots, l$), trong đó mỗi siêu phẳng nằm sát với toàn bộ lớp dữ liệu ${+}$ (ma trận $A$) và cách xa cụm thứ $j$ của lớp ${-}$ (ma trận $B_j$).
- $k$ siêu phẳng có dạng $f_{-i}(x) = w_{-i}^T x + b_{-i} = 0$ ($i = 1, \dots, k$), trong đó mỗi siêu phẳng nằm sát với toàn bộ lớp dữ liệu ${-}$ (ma trận $B$) và cách xa cụm thứ $i$ của lớp ${+}$ (ma trận $A_i$).
Hàm mục tiêu của bài toán tối ưu WS-SVM cho siêu phẳng thứ $j$ phía lớp ${+}$ được mô hình hóa: $$\min_{w_{+j}, b_{+j}, \xi_j} \frac{1}{2}|A w_{+j} + e_A b_{+j}|^2 + c_{+j} e_{B_j}^T \xi_j + \frac{1}{2}\mu_{+j}(|w_{+j}|^2 + b_{+j}^2) + \frac{1}{2}\lambda_{+j} w_{+j}^T \Sigma_{B_j} w_{+j}$$ ràng buộc: $$-(B_j w_{+j} + e_{B_j} b_{+j}) + \xi_j \ge e_{B_j}, \quad \xi_j \ge 0$$
2. Chiến lược Cụm-đối-Lớp (Cluster-vs-Class - Thuật toán WLS-SVM): Chiến lược này tiếp cận đảo ngược hoàn toàn để thích ứng tối đa với cấu trúc phân mảnh: tìm $(k + l)$ siêu phẳng, trong đó mỗi siêu phẳng nằm áp sát vào một cụm cụ thể $A_i$ của lớp ${+}$ đồng thời đẩy toàn bộ lớp ${-}$ ra xa. Sử dụng phương pháp bình phương tối thiểu có trọng số (Weighted Least Squares), hàm mục tiêu loại bỏ hoàn toàn biến phụ bất đẳng thức: $$\min_{w_{+i}, b_{+i}} \frac{1}{2}|A_i w_{+i} + e_{A_i} b_{+i}|^2 + \frac{1}{2}c_{+i} |B w_{+i} + e_B b_{+i} + e_B|^2 + \frac{1}{2}\mu_{+i}(|w_{+i}|^2 + b_{+i}^2) + \frac{1}{2}\lambda_{+i} w_{+i}^T \Sigma_{A_i} w_{+i}$$ Cho các đạo hàm riêng theo $w_{+i}$ và $b_{+i}$ bằng 0, nghiệm giải tích tối ưu $z_{+i} = [w_{+i}^T, b_{+i}]^T$ được xác định trực tiếp qua ma trận nghịch đảo cấp số đại số: $$z_{+i} = -\left[H_i^T H_i + c_{+i} G^T G + \mu_{+i} I + \lambda_{+i} F_{A_i}\right]^{-1} c_{+i} G^T e_B$$ trong đó $H_i = [A_i, e_{A_i}]$, $G = [B, e_B]$, và $F_{A_i} = \begin{bmatrix} \Sigma_{A_i} & 0 \ 0 & 0 \end{bmatrix}$.
Điều kiện biên (boundary conditions) của khung phân tích được xác lập rõ: Ma trận dữ liệu được chuẩn hóa về vector trung bình $\mu_X = 0$, ma trận hiệp phương sai $\Sigma_X = \frac{1}{m_X} X^T X$ nửa xác định dương, và số lượng mẫu trong mỗi cụm $m_{Ai} \ge n + 1$ để đảm bảo tính khả nghịch của các toán tử ma trận.
Phương pháp nghiên cứu tiên tiến
Thiết kế nghiên cứu
Nghiên cứu được thiết kế theo triết lý Thực chứng luận (Positivism) và Diễn dịch toán học (Deductive Mathematical Modeling), kết hợp kiểm định thực nghiệm định lượng nghiêm ngặt. Hệ thống phương pháp luận tích hợp liền mạch giữa kỹ thuật học không giám sát (Unsupervised Clustering) ở giai đoạn tiền xử lý và học có giám sát (Supervised Optimization) ở giai đoạn phân lớp.
+-----------------------------------------------------------------------------------+
| QUY TRÌNH NGHIÊN CỨU RIGOROUS CỦA LUẬN ÁN |
+-----------------------------------------------------------------------------------+
| BƯỚC 1: TIỀN XỬ LÝ & PHÂN CỤM LIÊN KẾT WARD |
| - Chuẩn hóa vector đặc trưng x in R^n về khoảng [0, 1] hoặc [-1, 1] |
| - Áp dụng thuật toán Ward tối thiểu hóa phương sai nội cụm |
| - Trích xuất k cụm A_i (quy mô m_Ai) và l cụm B_j (quy mô m_Bj) |
+-----------------------------------------------------------------------------------+
| BƯỚC 2: TÍNH TOÁN CẤU TRÚC HÌNH HỌC KHÔNG GIAN |
| - Tính vector trung bình mu_{Ai}, mu_{Bj} |
| - Xây dựng ma trận hiệp phương sai Sigma_{Ai}, Sigma_{Bj} |
| - Thiết lập ma trận đặc trưng khối F_{Ai}, F_{Bj} |
+-----------------------------------------------------------------------------------+
| BƯỚC 3: MÔ HÌNH HÓA TOÁN HỌC & GIẢI TỐI ƯU |
| - Lựa chọn chiến lược: WS-SVM, ILS-SVM (Lớp-đối-Cụm) hoặc WLS-SVM (Cụm-đối-Lớp) |
| - Tuyến tính hoặc Phi tuyến hóa qua Kernel K(x^T, C^T) |
| - Giải qua KKT Dual QP hoặc hệ SLEs với công thức Sherman-Morrison-Woodbury |
+-----------------------------------------------------------------------------------+
| BƯỚC 4: THỰC NGHIỆM ĐÁNH GIÁ ĐỐI CHỨNG (10-FOLD CV) |
| - Tập dữ liệu giả lập 2D (Synthetic 2D Datasets) |
| - Tập dữ liệu chuẩn quốc tế UCI Machine Learning Repository |
| - So sánh trực tiếp: Standard SVM, PSVM, GEPSVM, TSVM, LSTSVM, S-TSVM |
| - Đo lường: Accuracy (%), Training Time (s), p-value kiểm định thống kê |
+-----------------------------------------------------------------------------------+
Luận án sử dụng thuật toán phân cụm liên kết của Ward (Ward's Hierarchical Agglomerative Clustering) (Ward, 1963) thay vì thuật toán k-means hay k-nearest neighbors (k-NN). Cơ sở khoa học của việc lựa chọn này là: k-means bị giới hạn bởi giả định cụm dạng hình cầu đồng kích thước và nhạy cảm với khởi tạo tâm ngẫu nhiên; k-NN không biểu diễn được thông tin cấu trúc phân phối toàn thể. Trong khi đó, phương pháp Ward tối thiểu hóa tổng bình phương độ lệch nội cụm tại mỗi bước hợp nhất: $$\Delta ESS = \frac{m_A m_B}{m_A + m_B} |\mu_A - \mu_B|^2$$ giúp bảo toàn cấu trúc hình học tự nhiên và phân lập chính xác các phân phối phức tạp.
Quy trình nghiên cứu rigorous
Quy trình thực nghiệm tuân thủ tiêu chuẩn đánh giá chéo 10 lần (10-fold Cross-Validation) độc lập để loại bỏ hoàn toàn hiện tượng thiên lệch chọn mẫu (selection bias). Không gian tìm kiếm siêu tham số được tối ưu hóa thông qua Grid Search trên lưới logarit:
- Hệ số phạt $c, c_+, c_- \in {10^{-5}, 10^{-4}, \dots, 10^4, 10^5}$
- Tham số chính quy hóa $\mu, \mu_+, \mu_- \in {10^{-5}, \dots, 10^5}$
- Trọng số cấu trúc $\lambda, \lambda_+, \lambda_- \in {10^{-5}, \dots, 10^5}$
- Tham số nhân hạch Gaussian RBF $\gamma \in {2^{-5}, 2^{-4}, \dots, 2^4, 2^5}$
Tính hợp lệ cấu trúc (Construct Validity) được đảm bảo bằng việc chứng minh toán học tường minh thông qua định lý KKT. Tính giá trị bên ngoài (External Validity) được chứng thực qua việc kiểm thử trên hàng loạt bộ dữ liệu đa dạng về số chiều và số lượng mẫu từ UCI.
Data và phân tích
Nghiên cứu được triển khai thực nghiệm toàn diện trên ngôn ngữ lập trình Python, sử dụng các thư viện tính toán khoa học chuyên sâu như NumPy, SciPy, Scikit-learn và các bộ giải quy hoạch toàn phương chuyên dụng (QP Solvers như CVXOPT, Quadprog). Toàn bộ mã nguồn thực nghiệm được đóng gói và lưu trữ công khai trên GitHub, đảm bảo khả năng tái lập khoa học 100%.
Dữ liệu kiểm thử bao gồm hai nhóm chính:
- Tập dữ liệu tổng hợp 2 chiều (Synthetic 2D Datasets): Được thiết kế có chủ đích với các hình thái phân bố phi tuyến khắc nghiệt (dạng hình chữ thập lồng ghép, cấu trúc xoắn ốc hai dải - two spiral, cụm tròn bị bao bọc đa hướng, mật độ điểm phân tán không đều).
- Tập dữ liệu chuẩn quốc tế từ UCI Machine Learning Repository: Bao gồm cả các tập dữ liệu quy mô nhỏ và quy mô lớn với số chiều thuộc tính từ 4 đến hàng chục chiều, số lượng điểm dữ liệu từ hàng trăm đến hàng chục nghìn mẫu (ví dụ: Iris, Wine, Breast Cancer, Pima Indians Diabetes, Heart Disease, Ionosphere, Sonar, Banknote Authentication, v.v.).
Phát hiện đột phá và implications
Những phát hiện then chốt
Kết quả thực nghiệm trên các bộ dữ liệu đối chứng mang lại những phát hiện có ý nghĩa đột phá:
Thứ nhất, sự vượt trội về độ chính xác phân loại trên dữ liệu đa cụm phức tạp: Trên các tập dữ liệu giả định 2D có ranh giới phân tách phi tuyến uốn lượn cao, các thuật toán tiêu chuẩn như SVM, PSVM và TSVM đều tạo ra các mặt quyết định bị méo mó, dẫn đến việc phân lớp sai hàng loạt điểm dữ liệu ở các cụm giao thoa. Ngược lại, thuật toán WS-SVM và WLS-SVM phân tách chính xác 100% các cụm dữ liệu nhờ việc định hướng mặt quyết định men theo ma trận hiệp phương sai $\Sigma_{Ai}, \Sigma_{Bj}$ của từng cụm cụ thể.
Thứ hai, đột phá về tốc độ huấn luyện của mô hình bình phương tối thiểu có trọng số (WLS-SVM và ILS-SVM): Bằng cách chuyển đổi toàn bộ bài toán tối ưu sang giải hệ phương trình tuyến tính (SLEs) và áp dụng công thức Sherman-Morrison-Woodbury để nghịch đảo ma trận cấp $(n+1)$ thay vì ma trận cỡ dữ liệu $(m+1)$, thuật toán WLS-SVM đạt tốc độ thực thi nhanh gấp hàng chục lần so với SVM tiêu chuẩn và nhanh hơn vượt trội so với S-TSVM (vốn phải giải bài toán QP lặp).
+-----------------------------------------------------------------------------------+
| SO SÁNH ĐỘ PHỨC TẠP VÀ HIỆU NĂNG HUẤN LUYỆN |
+-----------------------------------------------------------------------------------+
| Thuật toán | Dạng bài toán tối ưu | Độ phức tạp tính toán | Tốc độ |
+-------------+---------------------------------+-----------------------+-----------+
| SVM | 1 bài toán QP cỡ m x m | O(m^3) | Cơ sở |
| TSVM | 2 bài toán QP cỡ (m/2) x (m/2) | O(m^3 / 4) | Nhanh ~4x |
| S-TSVM | 2 bài toán QP cấu trúc cỡ m/2 | O(m^3 / 4) + O(K) | Nhanh ~3x |
| ILS-SVM | (l + k) hệ SLEs tuyến tính | O((l+k) * n^3) | Nhanh ~15x|
| WLS-SVM | (k + l) hệ SLEs có trọng số | O((k+l) * n^3) | Nhanh ~25x|
+-----------------------------------------------------------------------------------+
Thứ ba, năng lực xử lý dữ liệu mất cân bằng nghiêm trọng (Imbalanced Data Robustness): Khi thử nghiệm trên các tập dữ liệu có tỷ lệ mất cân bằng mẫu 90% (lớp chiếm đa số) và 10% (lớp chiếm thiểu số), các thuật toán SVM truyền thống có xu hướng kéo mặt quyết định về sát lớp thiểu số để tối đa hóa độ chính xác tổng thể, dẫn đến tỷ lệ lỗi rất cao trên lớp thiểu số (sai lầm loại II). Thuật toán WLS-SVM với hệ số phạt có trọng số $\delta^+, \delta^-$ và điều chỉnh theo tỷ lệ kích thước điểm cụm $m_{Ai}$ đã duy trì độ nhạy (Sensitivity) và độ đặc hiệu (Specificity) cân bằng, triệt tiêu hiện tượng thiên vị lớp đa số.
Thứ tư, tính ổn định cao của cơ chế Kernelization trong không gian Hilbert: Khi mở rộng sang trường hợp phi tuyến với hạch nhân RBF $K(x_i, x_j) = \exp(-\gamma |x_i - x_j|^2)$, nghiệm giải tích của WLS-SVM trong không gian con $S = \text{span}(\Phi(C^T))$ không gặp hiện tượng quá khớp (overfitting), nhờ thành phần chính quy hóa $\frac{1}{2}\mu (|u|^2 + b^2)$ kiểm soát chặt chẽ độ phức tạp của hàm phân lớp.
Implications đa chiều
- Về mặt lý thuyết (Theoretical Advances): Công trình làm phong phú thêm lý thuyết tối ưu hóa ứng dụng trong học máy, chứng minh rằng sự kết hợp giữa phân cụm hình học và quy hoạch toán học tạo ra một hệ hình phân lớp mạnh hơn việc chỉ tiếp cận thuần túy từ một phía.
- Về mặt phương pháp luận (Methodological Innovations): Framework phân tách lớp-đối-cụm và cụm-đối-lớp có thể chuyển giao và ứng dụng trực tiếp cho các họ thuật toán học máy khác như Support Vector Regression (SVR), Extreme Learning Machine (ELM), hay các mạng nơ-ron sâu dạng phân nhánh (Branching Deep Networks).
- Về mặt thực tiễn (Practical Applications): Thuật toán cung cấp giải pháp tối ưu cho bài toán chẩn đoán y tế tự động (như chẩn đoán sốt xuất huyết qua vector bệnh án 9 chiều $\mathbf{x} \in \mathbb{R}^9$, phân loại tế bào ung thư vú Wisconsin Diagnostic Breast Cancer), nơi mà các triệu chứng của bệnh nhân thường phân cụm phức tạp và tỷ lệ ca bệnh dương tính luôn chiếm thiểu số so với quần thể khỏe mạnh.
- Về mặt chính sách và triển khai (Policy & Deployment): Giúp các doanh nghiệp công nghệ và trung tâm dữ liệu y tế tối ưu hóa chi phí hạ tầng máy chủ nhờ giảm thiểu tài nguyên CPU/GPU trong quá trình huấn luyện và tái huấn luyện mô hình theo thời gian thực.
Limitations và Future Research
Mặc dù đạt được những kết quả đột phá, luận án duy trì góc nhìn phê phán học thuật khi thẳng thắn chỉ ra các giới hạn nghiên cứu:
- Sự phụ thuộc vào chất lượng phân cụm tiền xử lý: Hiệu năng của WS-SVM, ILS-SVM và WLS-SVM phụ thuộc trực tiếp vào kết quả phân cụm ban đầu của thuật toán Ward. Nếu dữ liệu có mật độ nhiễu cực lớn hoặc ranh giới cụm bị mờ nhạt hoàn toàn, việc xác định số lượng cụm tối ưu ($k, l$) có thể gặp sai số, ảnh hưởng đến ma trận hiệp phương sai $\Sigma_{Ai}$.
- Không gian siêu tham số mở rộng: Do mỗi cụm hoặc mỗi siêu phẳng có thể mang các tham số điều chỉnh riêng biệt ($c_{+i}, \mu_{+i}, \lambda_{+i}$), việc tìm kiếm tổ hợp siêu tham số tối ưu bằng Grid Search đòi hỏi nhiều thời gian thử nghiệm, dù thời gian chạy mỗi vòng lặp đơn lẻ là rất ngắn.
- Phạm vi phân loại nhị phân: Luận án tập trung giải quyết trọn vẹn bài toán phân loại 2 lớp (binary classification). Việc mở rộng sang bài toán đa lớp (multi-class) hiện vẫn dựa trên các cơ chế phân rã truyền thống như One-vs-Rest (OvR) hoặc One-vs-One (OvO).
Chương trình nghiên cứu 10 năm tiếp theo (Future Research Agenda) bao gồm 4 định hướng trọng tâm:
- Tự động hóa tối ưu siêu tham số: Tích hợp các thuật toán tối ưu hóa bầy đàn (Particle Swarm Optimization - PSO) hoặc Tối ưu hóa Bayes (Bayesian Optimization) để tự động hóa hoàn toàn quá trình tinh chỉnh $(c, \mu, \lambda)$.
- Mở rộng trực tiếp sang phân lớp đa lớp (Multi-Class SVM): Thiết lập công thức toán học thống nhất cho bài toán phân lớp đa lớp trực tiếp dựa trên cấu trúc siêu cụm (Hyper-cluster) mà không cần phân rã nhị phân trung gian.
- Xử lý dữ liệu lớn theo luồng (Online Streaming Data): Phát triển phiên bản học tăng cường (Incremental / Online WLS-SVM) cho phép cập nhật ma trận nghịch đảo tức thời khi có thêm luồng dữ liệu mới mà không cần huấn luyện lại từ đầu.
- Ứng dụng trên dữ liệu y sinh học siêu chiều (Genomics & Proteomics): Kiểm thử mô hình trên dữ liệu giải trình tự gen với số chiều $n \gg m$ kết hợp các kỹ thuật trích chọn đặc trưng thưa (Sparse Feature Selection).
Tác động và ảnh hưởng
Công trình nghiên cứu mang lại những tác động sâu sắc trên nhiều bình diện:
- Ảnh hưởng học thuật (Academic Impact): Toàn bộ các kết quả cốt lõi của luận án đã được bình duyệt và công bố chính thức trong 5 công trình khoa học uy tín, bao gồm 01 bài báo tại kỷ yếu hội thảo quốc tế, 01 bài tại chuyên san hội thảo quốc gia, và 03 công trình đăng trên các tạp chí khoa học chuyên ngành trong nước (Tạp chí Khoa học và Công nghệ - Đại học Khoa học Huế, Tạp chí Kỹ thuật và Công nghệ - Đại học Huế, Tạp chí Tin học và Điều khiển học). Đây là nguồn tài liệu tham khảo giá trị cho các nhóm nghiên cứu về tối ưu hóa và học máy tại Việt Nam và quốc tế.
- Chuyển đổi công nghiệp (Industry Transformation): Thuật toán cung cấp giải pháp xử lý phân loại thời gian thực cho các hệ thống nhúng (Embedded AI), thiết bị IoT và thiết bị y tế thông minh vốn bị giới hạn nghiêm ngặt về bộ nhớ và năng lượng tính toán.
- Lợi ích xã hội (Societal Benefits): Góp phần nâng cao độ chính xác trong chẩn đoán y tế sớm, giảm thiểu tỷ lệ chẩn đoán sai các ca bệnh hiểm nghèo (như đau ruột thừa cấp, sốt xuất huyết nặng, ung thư), giảm áp lực cho hệ thống y tế công cộng.
Đối tượng hưởng lợi
- Nghiên cứu sinh và Học viên cao học (Doctoral & Master Researchers): Luận án cung cấp một cẩm nang toán học chuẩn mực từ việc thiết lập bài toán tối ưu QP, điều kiện KKT, kỹ thuật đối ngẫu Lagrange, đến kỹ thuật chứng minh sự hội tụ và lập trình thuật toán giải tích trên Python.
- Các nhà khoa học máy tính và Giảng viên đại học: Cung cấp tài liệu tham khảo chuyên sâu và hệ thống mã nguồn mở chuẩn mực để giảng dạy và phát triển các hướng nghiên cứu nâng cao về Support Vector Machines.
- Kỹ sư Trí tuệ nhân tạo và Nhà khoa học dữ liệu trong Công nghiệp (Industry R&D): Được tiếp cận các thuật toán phân lớp hiệu năng cao, mã nguồn mở, sẵn sàng triển khai trực tiếp vào các sản phẩm phân tích dữ liệu kinh doanh, phát hiện gian lận tài chính và chẩn đoán hình ảnh.
- Các nhà hoạch định chính sách y tế và công nghệ: Có thêm bằng chứng thực nghiệm về tính khả thi của việc ứng dụng các thuật toán học máy tối ưu vào chuyển đổi số y tế và tự động hóa dịch vụ công.
Câu hỏi chuyên sâu
1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và đã mở rộng lý thuyết nào? Trả lời: Đóng góp lý thuyết độc đáo nhất là việc thiết lập Mô hình tối ưu hóa cấu trúc có trọng số thích nghi (Weighted Structural Optimization), mở rộng trực tiếp Lý thuyết Cực tiểu hóa Rủi ro Cấu trúc của Vapnik (1995) và mô hình S-TSVM của Qi et al. (2013). Luận án đã tích hợp đồng thời ma trận hiệp phương sai cục bộ của từng cụm $\Sigma_{Ai}, \Sigma_{Bj}$ và trọng số quy mô điểm dữ liệu $m_{Ai}, m_{Bj}$ vào hàm mục tiêu, giải quyết trọn vẹn mâu thuẫn giữa việc bảo toàn hình thái phân tán cụm và loại bỏ sự thiên lệch do chênh lệch kích thước mẫu.
2. Đột phá về phương pháp luận của luận án khi so sánh với ít nhất 2 nghiên cứu quốc tế trước đó? Trả lời: So với TSVM (Jayadeva et al., 2007) và S-TSVM (Qi et al., 2013):
- TSVM và S-TSVM chỉ tìm 2 siêu phẳng phân lớp toàn cục, bỏ qua cấu trúc phân tán đa cụm. Luận án đề xuất cấu trúc $(l+k)$ siêu phẳng (lớp-đối-cụm) và $(k+l)$ siêu phẳng (cụm-đối-lớp), cho phép các mặt phân cách uốn lượn chính xác theo từng cụm dữ liệu cục bộ.
- Về mặt tính toán, trong khi TSVM và S-TSVM phải giải 2 bài toán QP đối ngẫu lặp phức tạp, mô hình WLS-SVM và ILS-SVM của luận án chuyển đổi sang giải các hệ phương trình đại số tuyến tính (SLEs), kết hợp công thức Sherman-Morrison-Woodbury để giảm chiều ma trận nghịch đảo về cỡ $(n+1) \times (n+1)$, tăng tốc độ huấn luyện lên hàng chục lần.
3. Phát hiện bất ngờ nhất trong quá trình thực nghiệm là gì? Trả lời: Phát hiện bất ngờ nhất là việc phương pháp bình phương tối thiểu có trọng số (WLS-SVM) không chỉ vượt trội về tốc độ tính toán mà còn đạt độ chính xác phân lớp cao hơn đáng kể so với các mô hình QP đối ngẫu trên dữ liệu mất cân bằng cực độ (90% - 10%). Thông thường, phương pháp bình phương tối thiểu dễ bị ảnh hưởng bởi nhiễu do mất tính thưa (loss of sparsity), nhưng nhờ có số hạng định hướng ma trận hiệp phương sai cụm $\frac{1}{2}\lambda w^T \Sigma w$ đóng vai trò như một bộ lọc không gian, mô hình đã triệt tiêu hoàn toàn tác động tiêu cực của các điểm dữ liệu biên giả mạo.
4. Luận án có cung cấp giao thức tái lập (Replication Protocol) hoàn chỉnh không? Trả lời: Có. Luận án cung cấp giao thức tái lập khoa học đầy đủ bao gồm: công thức toán học chi tiết, giải thuật tường minh dạng mã giả (pseudocode), mô tả chi tiết các tham số lưới Grid Search, đường dẫn kho lưu trữ mã nguồn mở trên GitHub chứa toàn bộ mã nguồn Python cài đặt các thuật toán đề xuất và các thuật toán đối chứng, cùng với tập dữ liệu thực nghiệm UCI và dữ liệu mô phỏng 2D trong phần Phụ lục.
5. Chương trình nghiên cứu 10 năm tới được vạch ra như thế nào? Trả lời: Chương trình 10 năm tới tập trung vào 3 trụ cột: (1) Phát triển lý thuyết phân lớp đa lớp trực tiếp (Direct Multi-Class Structural SVM); (2) Tích hợp thuật toán WLS-SVM vào các kiến trúc mạng nơ-ron sâu (Deep Neural Networks) đóng vai trò như tầng phân lớp tối ưu thay thế Softmax; (3) Tối ưu hóa thuật toán phân tán trên nền tảng tính toán song song GPU để xử lý dữ liệu lớn (Big Data) trong lĩnh vực tin sinh học và gen y tế.
Kết luận
Luận án tiến sĩ của NCS. Nguyễn Thế Cường đã hoàn thành xuất sắc các mục tiêu nghiên cứu đề ra, tạo nên một dấu ấn khoa học đậm nét trong lĩnh vực máy học và tối ưu hóa với các đóng góp cốt lõi:
- Hệ thống hóa và phân tích sâu sắc cơ sở toán học của bài toán quy hoạch toàn phương (QP), hệ điều kiện KKT và đối ngẫu Lagrange trong họ các thuật toán SVM từ cổ điển đến hiện đại.
- Đề xuất chiến lược phân lớp Lớp-đối-Cụm (Class-vs-Cluster) với hai thuật toán WS-SVM (giải bằng đối ngẫu Lagrange) và ILS-SVM (giải bằng bình phương tối thiểu), giúp phân tách chính xác các cụm dữ liệu đối kháng phân tán.
- Đề xuất chiến lược phân lớp Cụm-đối-Lớp (Cluster-vs-Class) với thuật toán WLS-SVM, khai thác trọn vẹn thông tin ma trận hiệp phương sai và trọng số kích thước mẫu của từng cụm, giải quyết triệt để bài toán phân lớp dữ liệu đa cấu trúc phức tạp.
- Triệt tiêu điểm nghẽn tính toán của SVM thông qua việc chuyển đổi bài toán QP cỡ lớn sang giải các hệ phương trình tuyến tính (SLEs) kết hợp công thức Sherman-Morrison-Woodbury, gia tăng tốc độ huấn luyện vượt bậc.
- Chứng thực tính ưu việt của các mô hình thông qua thực nghiệm khoa học nghiêm ngặt trên dữ liệu mô phỏng 2D và tập dữ liệu chuẩn quốc tế UCI, mở ra giải pháp phân loại hiệu quả cao cho dữ liệu thực tế bị mất cân bằng mẫu.
Công trình không chỉ đánh dấu bước tiến quan trọng về mặt lý thuyết học máy có giám sát tại Việt Nam mà còn sở hữu giá trị ứng dụng thực tiễn sâu rộng, sẵn sàng chuyển giao cho các hệ thống thông minh, chẩn đoán y tế kỹ thuật số và thị giác máy tính trong tương lai.