Supervised Learning - Học có giám sát

Supervised Learning - Học có giám sát

Trong Supervised Learning (Học có giám sát), tập dữ liệu huấn luyện là một danh sách các cặp câu hỏi và đáp án đúng:

Nhiệm vụ của máy là tìm ra một quy tắc dự đoán (gọi là hàm giả thuyết $h$ - hypothesis) sao cho với bất kỳ dữ liệu mới $x^*$ nào trong tương lai, giá trị dự đoán $\hat{y} = h(x^*)$ càng gần với đáp án thật $y^*$ càng tốt.

⚠️ Quy tắc vàng: Mục tiêu của học có giám sát không phải là học thuộc lòng (memorize) toàn bộ $n$ ví dụ trong quá khứ, mà là rút ra quy luật tổng quát để dự đoán chính xác cho dữ liệu chưa từng thấy.

1. Hai bài toán kinh điển: Classification vs Regression

Tùy thuộc vào bản chất của đáp án $y$, học có giám sát được chia làm hai nhánh chính:

1.1 Phân loại (Classification) - Chọn nhãn hộp

• Đặc điểm: $y \in \{c_1, c_2, \dots, c_K\}$ là một tập hữu hạn các nhãn phân loại rời rạc.
• Ví dụ:
  • Nhị phân (Binary): Tin nhắn rác (0) hay Hợp lệ (1), Khối u Lành tính (0) hay Ác tính (1).
  • Đa lớp (Multiclass): Nhận diện chữ số viết tay từ 0 đến 9, nhận diện loài hoa.

1.2 Hồi quy (Regression) - Đo lường đại lượng

• Đặc điểm: $y \in \mathbb{R}$ là một giá trị số thực liên tục trên trục số.
• Ví dụ:
  • Dự đoán thời gian tài xế giao đồ ăn đến nơi (ví dụ: $24.5$ phút).
  • Dự đoán giá thuê phòng trọ dựa vào diện tích và khoảng cách tới trường đại học.

💡 Góc nhìn thực tế: Ranh giới giữa hai bài toán có thể chuyển đổi linh hoạt. Ví dụ: Dự đoán chính xác điểm thi môn AI (từ $0.0$ đến $10.0$) là bài toán Regression. Nhưng nếu trường chỉ quan tâm sinh viên Đậu ($y \ge 5.0$) hay Rớt ($y < 5.0$), bài toán ngay lập tức trở thành Classification.

2. Thuật toán k-Nearest Neighbors (k-NN) - “Gần mực thì đen, gần đèn thì rạng”

k-NN là thuật toán đơn giản và trực quan nhất trong toàn bộ thế giới Machine Learning.

2.1 Ý tưởng cốt lõi

Muốn biết một người có tính cách thế nào, hãy nhìn $k$ người bạn thân nhất xung quanh họ. Muốn phân loại một mẫu dữ liệu mới $x$, hãy tìm $k$ điểm dữ liệu trong quá khứ nằm gần nó nhất và lấy nhãn xuất hiện nhiều nhất (bỏ phiếu đa số - majority voting).

2.2 Đo khoảng cách thế nào?

Để biết ai “gần” ai, ta dùng các công thức khoảng cách hình học. Phổ biến nhất là Khoảng cách Euclidean (khoảng cách đường chim bay).

Trong không gian 2 chiều với hai điểm $x = (x_1, x_2)$ và $z = (z_1, z_2)$:

Tổng quát trong không gian $d$ chiều:

2.3 Ví dụ tính tay từng bước

Giả sử ta cần dự đoán một sinh viên mới $X_{\text{new}}$ có đặc trưng $(x_1, x_2) = (3, 2)$, tức vắng 3 buổi và muộn 2 buổi, có nguy cơ Trượt môn (1) hay Đậu môn (0):

• Nếu chọn $k=1$: Điểm gần nhất là B ($d = 1.00$, nhãn Trượt). Dự đoán: Trượt.
• Nếu chọn $k=3$: Ba điểm gần nhất là B ($1.00$), C ($1.41$), A ($2.24$).
  • Nhãn gồm: 1 phiếu Trượt (B) và 2 phiếu Đậu (C, A).
  • Bỏ phiếu đa số: 2 phiếu Đậu thắng 1 phiếu Trượt. Dự đoán: Đậu.

2.4 Chọn $k$ thế nào?

• $k=1$: Rất nhạy cảm với nhiễu (noise) hoặc điểm gán nhãn sai. Ranh giới quyết định rất ngoằn ngoèo $\to$ Dễ bị Overfitting.
• $k$ quá lớn (ví dụ $k=N$): Luôn luôn dự đoán lớp chiếm số đông trong toàn bộ dữ liệu, bất kể điểm mới nằm ở đâu $\to$ Dễ bị Underfitting.
• Kinh nghiệm thực hành:
  • Với bài toán nhị phân 2 lớp, nên chọn $k$ là số lẻ ($k = 3, 5, 7, \dots$) để không bao giờ xảy ra tình trạng hòa phiếu.
  • Chọn $k$ tối ưu bằng phương pháp Cross-Validation (sẽ học ở bài sau).

2.5 Bẫy chết người: Tại sao BẮT BUỘC phải Scale dữ liệu khi dùng k-NN?

Hãy nhìn vào ví dụ thực tế này:

• Đặc trưng 1: Thu nhập (từ $5,000,000$ đến $50,000,000$ VNĐ).
• Đặc trưng 2: Số con (từ $0$ đến $4$ con).

Khoảng cách giữa hai người:

Số con lệch nhau $2$ hoàn toàn bị con số $20$ triệu của thu nhập “nuốt chửng”. k-NN sẽ coi như đặc trưng số con không hề tồn tại! $\to$ Bắt buộc phải chuẩn hóa (Feature Scaling) đưa mọi đặc trưng về cùng một thang đo (ví dụ dùng Z-score: $z = \frac{x - \mu}{\sigma}$ hoặc Min-Max scaling về đoạn $[0, 1]$).

2.6 Góc nhìn chuyên sâu: Bản chất “Lazy Learning” và Tai ương số chiều (Curse of Dimensionality)

1. Lazy Learning (Học lười): k-NN không hề trải qua giai đoạn huấn luyện (training phase tốn $O(1)$ thời gian, chỉ việc lưu dữ liệu vào bộ nhớ). Nhưng khi dự đoán, nó phải quét qua toàn bộ $n$ điểm trong dataset để tính khoảng cách (inference tốn $O(n \cdot d)$ thời gian). Nếu hệ thống có hàng triệu người dùng, k-NN sẽ chạy cực kỳ chậm!
2. Tai ương số chiều: Khi số đặc trưng $d$ tăng lên hàng trăm/nghìn chiều, thể tích không gian tăng theo cấp số nhân khiến dữ liệu trở nên cực kỳ thưa thớt (sparse). Mọi cặp điểm đều cách xa nhau một khoảng tương đương nhau, khiến khái niệm “hàng xóm gần nhất” mất đi ý nghĩa. Do đó, k-NN không phù hợp với ảnh thô hoặc văn bản trừ khi đã qua bước giảm số chiều.

3. Linear Classifier - Chia đôi thế giới bằng một đường thẳng

Thay vì phải ôm khư khư toàn bộ tập dữ liệu như k-NN, liệu ta có thể học ra một ranh giới quyết định (Decision Boundary) cố định?

Trong mặt phẳng 2D, một đường thẳng có phương trình:

Trong không gian $d$ chiều, đường thẳng trở thành một siêu phẳng (hyperplane):

Trong đó:

• $w = [w_1, w_2, \dots, w_d]^T$ là vector trọng số (weights).
• $b$ (hoặc $w_0$) là hệ số tự do (bias).

Quy tắc phân loại:

4. Thuật toán Perceptron (Rosenblatt, 1958)

Perceptron là mô hình học máy tự động tìm các trọng số $w$ bằng cách học từ sai lầm.

4.1 Luật cập nhật Perceptron (Perceptron Learning Rule)

Khởi tạo trọng số $w = [0, 0, \dots, 0]$ và bias $b = 0$. Với mỗi mẫu huấn luyện $(x, y)$, mô hình đưa ra dự đoán $\hat{y}$. Sau đó cập nhật:

Trong đó:

• $\alpha > 0$ là tốc độ học (learning rate), ví dụ $\alpha = 0.1$.
• $y$ là nhãn thật ($0$ hoặc $1$), $\hat{y}$ là nhãn dự đoán ($0$ hoặc $1$).

4.2 Cơ chế sửa sai trực giác

Hãy xem hiệu số sai lệch $(y - \hat{y})$ hoạt động vi diệu thế nào:

• Nếu dự đoán đúng ($\hat{y} = y$): $(y - \hat{y}) = 0 \to$ Trọng số giữ nguyên không đổi.
• Nếu đoán thiếu ($y = 1$ nhưng đoán $\hat{y} = 0$): $(y - \hat{y}) = +1 \to$ Trọng số được cộng thêm một lượng $\alpha x$. Điều này làm cho tổng $w^T x + b$ ở lần sau sẽ tăng lên, kéo dự đoán tiến gần về $1$.
• Nếu đoán thừa ($y = 0$ nhưng đoán $\hat{y} = 1$): $(y - \hat{y}) = -1 \to$ Trọng số bị trừ đi một lượng $\alpha x$. Điều này làm cho tổng $w^T x + b$ ở lần sau sẽ giảm xuống, kéo dự đoán tiến về $0$.

4.3 Bảng tính tay vết chạy Perceptron (Step-by-step Trace)

Cho bài toán học cổng logic OR với 2 đặc trưng $x_1, x_2$, học với $\alpha = 1$, ban đầu $w = [0, 0], b = 0$:

Chỉ sau vài vòng lặp, Perceptron sẽ tìm được đường thẳng ngăn cách chính xác!

4.4 Giới hạn lịch sử của Perceptron: Vấn đề XOR (Minsky & Papert, 1969)

Năm 1969, hai nhà khoa học Marvin Minsky và Seymour Papert xuất bản cuốn sách chứng minh một sự thật chấn động: Perceptron đơn tầng không thể học được hàm XOR.

Cổng AND (Tách được)         Cổng OR (Tách được)          Cổng XOR (BÓ TAY!)
x₂                           x₂                           x₂
1 |   O       X              1 |   X       X              1 |   X       O
  |                            |                            |
0 |   O       O              0 |   O       X              0 |   O       X
  +------------- x₁            +------------- x₁            +------------- x₁
    0       1                    0       1                    0       1
 (Vẽ được 1 đường thẳng)      (Vẽ được 1 đường thẳng)     (Không thể vẽ 1 đường thẳng)

• Nhãn của XOR nằm chéo nhau: $(0, 0) \to 0$, $(1, 1) \to 0$, nhưng $(0, 1) \to 1$, $(1, 0) \to 1$.
• Dữ liệu này phi tuyến tính (Non-linearly Separable). Một nhát cắt thẳng không bao giờ chia tách được hình chữ X.
• Phát hiện này đã nhấn chìm ngành nghiên cứu AI vào “Mùa đông AI” suốt hơn một thập kỷ, cho đến khi con người chứng minh được: Nếu xếp nhiều Perceptron thành nhiều tầng (Multi-Layer Perceptron) và dùng hàm kích hoạt phi tuyến, mạng neural có thể học được bất kỳ hình dạng nào! (Đây là nội dung của chương Neural Networks tiếp theo).

5. Từ Hard Threshold sang Xác suất: Hàm Sigmoid

Perceptron dùng hàm bước nhảy cứng (step function): hoặc là $0$, hoặc là $1$. Nhưng trong thực tế, ta thường muốn biết mức độ chắc chắn: “Mô hình đoán bệnh nhân này bị ung thư với xác suất 92% hay chỉ 51%?”

Hàm Sigmoid (Logistic Function) biến mọi số thực $z \in (-\infty, +\infty)$ thành một xác suất nằm trọn vẹn trong khoảng $(0, 1)$:

   1.0 +---------------------------------*****
       |                           ******
       |                        ***
   0.5 |---------------------*----------------
       |                  ***
       |           ******
   0.0 *****----------------------------------
      -6  -4  -2   0   2   4   6    (z)

• Nếu $z = 0 \to \sigma(0) = 0.5$ (Lưỡng lự 50-50).
• Nếu $z = +5 \to \sigma(5) \approx 0.993$ (Rất tự tin nhãn 1).
• Nếu $z = -5 \to \sigma(-5) \approx 0.007$ (Rất tự tin nhãn 0).

Đây chính là nền tảng của thuật toán Logistic Regression và là hàm kích hoạt kinh điển trong các mạng nơ-ron sơ khai.

6. Support Vector Machine (SVM) - Ranh giới an toàn tối đa

Nếu dữ liệu có thể phân tách tuyến tính, có vô số đường thẳng có thể chia tách hoàn hảo hai lớp. Vậy đường nào là tốt nhất?

6.1 Ý tưởng cốt lõi: Tối đa hóa Margin (Maximum Margin)

• Margin (Lề): Khoảng cách ngắn nhất từ đường phân chia tới các điểm dữ liệu gần nó nhất của cả hai phía.
• SVM tìm siêu phẳng sao cho Margin là lớn nhất có thể.
• Tại sao cần Margin lớn nhất? Vì một đường phân chia có khoảng đệm an toàn rộng sẽ ít bị tổn thương nhất khi dữ liệu mới trong thực tế bị xê dịch nhẹ.

6.2 Support Vectors là gì?

Những điểm dữ liệu nằm sát mép đường lề (chạm vào ranh giới margin) được gọi là Support Vectors (Các vector hỗ trợ).

• Điểm kỳ diệu của SVM: Vị trí của đường phân chia hoàn toàn chỉ phụ thuộc vào các Support Vectors này.
• Tất cả những điểm dữ liệu nằm sâu bên trong vùng an toàn dù có bị xóa đi hay dịch chuyển nhẹ thì đường biên của SVM vẫn giữ nguyên không đổi!

6.3 Soft Margin và Tham số $C$

Trong dữ liệu thực tế, các lớp thường lẫn vào nhau do nhiễu, không thể vẽ đường nào tách rời 100% (Hard Margin). SVM giải quyết bằng Soft Margin, cho phép một số điểm được phép lọt vào trong margin hoặc bị phân loại sai, nhưng đi kèm một khoản tiền phạt được kiểm soát bởi tham số $C$:

• $C$ lớn: Phạt rất nặng mỗi lỗi sai $\to$ Cố gắng phân loại đúng từng điểm huấn luyện $\to$ Margin hẹp $\to$ Dễ bị Overfitting.
• $C$ nhỏ: Chấp nhận lỗi sai dễ dãi hơn $\to$ Ưu tiên mở rộng margin rộng rãi $\to$ Dễ bị Underfitting.

6.4 Trực giác về Kernel Trick: “Uốn cong không gian để bẻ khóa phi tuyến”

Làm sao SVM phân loại được dữ liệu không phân tách tuyến tính (như bài toán XOR hoặc các vòng tròn đồng tâm)?

• Ý tưởng: Nếu không thể kẻ đường thẳng ở không gian 2D, hãy chiếu dữ liệu lên không gian 3D cao hơn.
• Ví dụ kinh điển: Các điểm nằm trong vòng tròn bán kính $R$. Trong 2D với $(x_1, x_2)$, ta không thể dùng đường thẳng tách được hình tròn. Nhưng nếu tạo thêm chiều thứ ba $x_3 = x_1^2 + x_2^2$, tất cả các điểm bên trong hình tròn sẽ chìm xuống dưới, còn các điểm bên ngoài sẽ nổi lên cao. Lúc này, chỉ cần lấy một mặt phẳng ngang cắt ngang qua là tách đôi được dữ liệu!
• Kernel Trick: SVM có thể tính toán trong không gian vô hạn chiều mà không cần thực sự biến đổi tọa độ của từng điểm, nhờ các hàm nhân (Kernel) như RBF (Radial Basis Function), Polynomial Kernel.

7. Triển khai chuẩn công nghiệp với scikit-learn

Trong thực tế, ta luôn bọc các bước tiền xử lý (Scaling) và mô hình (Model) vào trong một Pipeline duy nhất để code gọn gàng và ngăn chặn rò rỉ dữ liệu:

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.svm import SVC
from sklearn.linear_model import LogisticRegression

# 1. Pipeline cho k-NN
knn_pipeline = make_pipeline(
    StandardScaler(),
    KNeighborsClassifier(n_neighbors=5, metric="euclidean")
)

# 2. Pipeline cho SVM với RBF Kernel
svm_pipeline = make_pipeline(
    StandardScaler(),
    SVC(kernel="rbf", C=1.0, gamma="scale")
)

# 3. Pipeline cho Logistic Regression
lr_pipeline = make_pipeline(
    StandardScaler(),
    LogisticRegression(C=1.0, max_iter=1000)
)

# Huấn luyện và dự đoán cực kỳ nhất quán:
# knn_pipeline.fit(X_train, y_train)
# y_pred = knn_pipeline.predict(X_test)

8. Bảng so sánh tổng kết các thuật toán

9. Câu hỏi tự kiểm tra & Thảo luận

10. Tài liệu tham khảo

• CS50 AI Lecture 4 - Learning: Nearest-Neighbor, Perceptron, Support Vector Machines.
• Rosenblatt, F. (1958), The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain.
• Minsky, M., & Papert, S. (1969), Perceptrons: An Introduction to Computational Geometry, MIT Press.
• Cortes, C. & Vapnik, V. (1995), Support-Vector Networks, Machine Learning, 20, 273–297.
• Scikit-learn Documentation: Nearest Neighbors, Support Vector Machines, Preprocessing Data.

Bản tiếng Anh đang soạn.