Nhóm 2

Phân loại — Classification

Nhóm thuật toán có mục tiêu gán cho mỗi mẫu đầu vào một nhãn rời rạc (class) trong tập hữu hạn các lớp — ví dụ: email spam / không spam, ảnh là chó / mèo, khối u lành tính / ác tính. Khác với hồi quy (đầu ra là số liên tục), phân loại trả về một trong các nhãn định trước. Trang này đi từ bộ phân loại tuyến tính cơ bản đến SVM, kernel SVM và biểu diễn thưa (SRC).

1. Linear Classifier — Bộ phân loại tuyến tính

Phân tách bằng siêu phẳng

Ý tưởng nền tảng của phân loại tuyến tính là dùng một siêu phẳng (hyperplane) để chia không gian đặc trưng thành hai nửa, mỗi nửa ứng với một lớp. Siêu phẳng được mô tả bởi:

$$ w^\top x + b = 0 $$

trong đó $w$ là vector trọng số (pháp tuyến của siêu phẳng), $x$ là vector đặc trưng và $b$ là bias. Với một điểm mới, ta tính giá trị $f(x)=w^\top x+b$ rồi dự đoán nhãn theo dấu:

$$ \hat{y} = \operatorname{sign}(w^\top x + b) $$

Nếu $w^\top x + b \gt 0$ thì mẫu thuộc lớp dương ($+1$); nếu $\lt 0$ thì thuộc lớp âm ($-1$). Đường (mặt) ứng với $f(x)=0$ chính là ranh giới quyết định (decision boundary) — biên ngăn cách hai lớp.

Perceptron: thuật toán cổ điển nhất, cập nhật $w$ mỗi khi phân loại sai một điểm; hội tụ nếu dữ liệu khả tách tuyến tính.
Logistic Regression: cũng dùng ranh giới tuyến tính nhưng đưa $f(x)$ qua hàm sigmoid để cho ra xác suất thuộc lớp, tối ưu bằng cross-entropy.

Một tập dữ liệu được gọi là khả tách tuyến tính (linearly separable) nếu tồn tại ít nhất một siêu phẳng phân tách hoàn toàn hai lớp. Khi đó thường có vô số siêu phẳng cùng làm được — và câu hỏi tự nhiên là: siêu phẳng nào tốt nhất? Đó chính là động lực dẫn tới SVM.

2. Support Vector Machine (SVM)

Cực đại hoá biên (margin)

SVM chọn siêu phẳng phân tách sao cho biên (margin) — khoảng cách từ siêu phẳng tới điểm gần nhất của mỗi lớp — là lớn nhất có thể. Trực giác: biên càng rộng thì bộ phân loại càng "an toàn" với nhiễu và tổng quát hoá tốt hơn trên dữ liệu mới.

Khi chuẩn hoá để các điểm gần nhất thoả $|w^\top x + b| = 1$, độ rộng biên (khoảng cách giữa hai mặt $w^\top x+b=\pm 1$) bằng:

$$ \text{margin} = \frac{2}{\lVert w\rVert} $$

Cực đại hoá $\frac{2}{\lVert w\rVert}$ tương đương với cực tiểu hoá $\frac12\lVert w\rVert^2$. Với dữ liệu khả tách hoàn toàn, ta có bài toán hard margin:

$$ \min_{w,b}\ \tfrac12\lVert w\rVert^2 \quad \text{s.t. } y_i(w^\top x_i+b)\ge 1,\ \forall i $$

Ràng buộc $y_i(w^\top x_i+b)\ge 1$ đòi hỏi mọi điểm đều nằm đúng phía và cách biên ít nhất một đơn vị. Trong thực tế dữ liệu thường chồng lấn / nhiễu, nên ta nới lỏng bằng soft margin: thêm biến bù (slack) $\xi_i\ge 0$ cho phép một số điểm vi phạm biên, và tham số $C$ điều khiển mức phạt:

$$ \min_{w,b,\xi}\ \tfrac12\lVert w\rVert^2 + C\sum_i \xi_i \quad \text{s.t. } y_i(w^\top x_i+b)\ge 1-\xi_i,\ \xi_i\ge 0 $$

$C$ lớn: phạt nặng lỗi → biên hẹp, bám sát dữ liệu (dễ overfit).
$C$ nhỏ: chấp nhận nhiều vi phạm → biên rộng, mượt hơn (dễ underfit).

Các điểm nằm ngay trên biên hoặc vi phạm biên chính là support vectors (vector hỗ trợ) — chỉ chúng quyết định vị trí siêu phẳng; bỏ các điểm còn lại không làm thay đổi nghiệm.

Dạng đối ngẫu (dual). Dùng nhân tử Lagrange $\alpha_i\ge 0$ cho mỗi ràng buộc, bài toán được viết lại chỉ qua tích vô hướng giữa các mẫu:

$$ \max_{\alpha}\ \sum_i \alpha_i - \tfrac12\sum_{i,j}\alpha_i\alpha_j\, y_i y_j\, x_i^\top x_j \quad \text{s.t. } 0\le\alpha_i\le C,\ \sum_i \alpha_i y_i = 0 $$

Chỉ các support vector có $\alpha_i \gt 0$; những điểm khác có $\alpha_i = 0$. Điểm mấu chốt: dạng dual chỉ phụ thuộc vào $x_i^\top x_j$ — đây là cánh cửa cho kernel trick ở phần sau.

3. Kernel SVM

Xử lý dữ liệu phi tuyến

Nhiều bài toán thực tế không khả tách tuyến tính trong không gian gốc. Giải pháp: ánh xạ dữ liệu lên một không gian cao chiều hơn bằng hàm $\phi(x)$, nơi mà các lớp trở nên khả tách tuyến tính, rồi áp dụng SVM tuyến tính ở đó.

Vấn đề là $\phi(x)$ có thể rất nhiều chiều (thậm chí vô hạn), tính tường minh rất tốn kém. May mắn là (nhờ dạng dual) SVM chỉ cần tích vô hướng giữa các mẫu. Kernel trick thay tích vô hướng trong không gian ánh xạ bằng một hàm kernel tính trực tiếp trên dữ liệu gốc:

$$ K(x_i, x_j) = \phi(x_i)^\top \phi(x_j) $$

Như vậy ta không bao giờ phải tính $\phi(x)$ tường minh — chỉ cần biết hàm $K$. Một số kernel phổ biến:

Kernel	Công thức	Đặc điểm
Linear	$K(x_i,x_j)=x_i^\top x_j$	Tương đương SVM tuyến tính; nhanh, tốt khi dữ liệu nhiều chiều
Polynomial	$K(x_i,x_j)=(x_i^\top x_j + c)^d$	Bậc $d$ tạo ranh giới cong; $c,d$ kiểm soát độ phức tạp
RBF / Gaussian	$K(x_i,x_j)=\exp(-\gamma\lVert x_i-x_j\rVert^2)$	Phổ biến nhất; linh hoạt, ánh xạ vào không gian vô hạn chiều
Sigmoid	$K(x_i,x_j)=\tanh(\gamma\, x_i^\top x_j + c)$	Gợi nhớ mạng nơ-ron; ít dùng hơn, không luôn là kernel hợp lệ

Hai siêu tham số quan trọng:

$\gamma$ (với RBF): điều khiển "tầm ảnh hưởng" của mỗi điểm. $\gamma$ lớn → ảnh hưởng cục bộ, ranh giới gồ ghề (dễ overfit); $\gamma$ nhỏ → mượt hơn.
$C$: như ở soft margin, đánh đổi giữa biên rộng và số điểm bị phân loại sai.

Cặp $(\gamma, C)$ thường được chọn bằng cross-validation / grid search.

4. Sparse Representation-based Classification (SRC)

Phân loại dựa trên biểu diễn thưa

SRC dựa trên một giả thiết đẹp: một mẫu thử thuộc lớp nào thì có thể biểu diễn (xấp xỉ) như tổ hợp tuyến tính thưa của chính các mẫu huấn luyện thuộc lớp đó. Ta xếp toàn bộ mẫu huấn luyện thành các cột của một từ điển (dictionary) $D = [D_1, D_2, \dots, D_C]$, trong đó $D_c$ gom các mẫu của lớp $c$. Khi đó mẫu thử $y$ được viết:

$$ y \approx D\alpha $$

với $\alpha$ là vector hệ số. Kỳ vọng: nếu $y$ thuộc lớp $c$ thì các hệ số tương ứng với $D_c$ sẽ lớn, còn lại gần 0 — tức $\alpha$ thưa. Để tìm nghiệm thưa, ta giải bài toán tối thiểu chuẩn $\ell_1$:

$$ \hat\alpha = \arg\min_{\alpha}\ \lVert\alpha\rVert_1 \quad \text{s.t. } \lVert y - D\alpha\rVert_2 \le \epsilon $$

Chuẩn $\ell_1$ khuyến khích đa số hệ số bằng 0 (đặc tính chọn lọc đặc trưng), $\epsilon$ là dung sai sai số tái tạo. Sau khi có $\hat\alpha$, ta phân loại theo lớp có sai số tái tạo (residual) nhỏ nhất:

$$ \hat{c} = \arg\min_{c}\ \lVert y - D_c\,\hat\alpha_c\rVert_2 $$

trong đó $\hat\alpha_c$ là phần hệ số ứng với lớp $c$. Lớp nào tái tạo lại $y$ tốt nhất (residual bé nhất) thì $y$ được gán vào lớp đó.

Ứng dụng nổi bật: nhận diện khuôn mặt (face recognition) — SRC rất bền với che khuất và nhiễu, vì phần lỗi cũng có thể mô hình hoá thưa.
Liên hệ LASSO: bài toán tối thiểu $\ell_1$ ở đây chính là họ regularization $\ell_1$ (LASSO) — xem thêm trang Regularization.

So sánh các bộ phân loại

Chọn thuật toán theo tình huống

Thuật toán	Ranh giới	Điểm mạnh	Hạn chế
Linear (Perceptron / Logistic)	Tuyến tính	Đơn giản, nhanh, dễ diễn giải; Logistic cho xác suất	Chỉ tốt khi dữ liệu khả tách tuyến tính
SVM (linear)	Tuyến tính, biên cực đại	Tổng quát hoá tốt, ít nhạy với nhiễu, tốt khi nhiều chiều	Chọn $C$ cần tinh chỉnh; chậm khi rất nhiều mẫu
Kernel SVM (RBF)	Phi tuyến	Bắt được ranh giới cong phức tạp mà không tính $\phi$ tường minh	Tốn bộ nhớ/thời gian với dữ liệu lớn; nhạy với $\gamma, C$
SRC	Dựa trên residual	Bền với che khuất/nhiễu; mạnh cho nhận diện khuôn mặt	Giải $\ell_1$ tốn kém; cần đủ mẫu train mỗi lớp

Thực hành: SVM với scikit-learn

Kernel RBF

Ví dụ huấn luyện một Kernel SVM (kernel RBF) trên dữ liệu mẫu, có chuẩn hoá đặc trưng:

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline
from sklearn.svm import SVC

X, y = load_breast_cancer(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y)

# Chuẩn hoá + SVM kernel RBF gói trong 1 pipeline
clf = make_pipeline(
    StandardScaler(),
    SVC(kernel="rbf", C=1.0, gamma="scale"),
)
clf.fit(X_tr, y_tr)
print("Accuracy:", clf.score(X_te, y_te))

# Dò siêu tham số C và gamma bằng cross-validation
grid = {"svc__C": [0.1, 1, 10],
        "svc__gamma": ["scale", 0.01, 0.1]}
gs = GridSearchCV(clf, grid, cv=5)
gs.fit(X_tr, y_tr)
print(gs.best_params_, gs.best_score_)

Luôn chuẩn hoá dữ liệu cho SVM: kernel RBF và biên dựa trên khoảng cách $\lVert x_i - x_j\rVert$, nên nếu các đặc trưng có thang đo khác nhau (ví dụ tuổi 0–100 vs thu nhập hàng triệu) thì đặc trưng lớn sẽ áp đảo. Dùng StandardScaler (đưa về trung bình 0, phương sai 1) trước khi đưa vào SVM — gói trong Pipeline để tránh rò rỉ dữ liệu giữa train và test.

Kernel	Công thức	Đặc điểm
Linear	\(K(x_i,x_j)=x_i^\top x_j\)	Tương đương SVM tuyến tính; nhanh, tốt khi dữ liệu nhiều chiều
Polynomial	\(K(x_i,x_j)=(x_i^\top x_j + c)^d\)	Bậc \(d\) tạo ranh giới cong; \(c,d\) kiểm soát độ phức tạp
RBF / Gaussian	\(K(x_i,x_j)=\exp(-\gamma\lVert x_i-x_j\rVert^2)\)	Phổ biến nhất; linh hoạt, ánh xạ vào không gian vô hạn chiều
Sigmoid	\(K(x_i,x_j)=\tanh(\gamma\, x_i^\top x_j + c)\)	Gợi nhớ mạng nơ-ron; ít dùng hơn, không luôn là kernel hợp lệ