7k láng giềng gần nhất và Naive Bayes#

Cả ba thuật toán ở Chương 6 đều học trực tiếp một biên quyết định tuyến tính. Trở lại sáu sinh viên và hỏi: một người ôn 3,6 giờ có đỗ không? Có hai cách trả lời rất khác với cách của Chương 6. Cách thứ nhất không học tham số nào cả: xem những người ôn số giờ gần 3,6 nhất đã đỗ hay trượt. Cách thứ hai mô tả số giờ ôn của nhóm đỗ và của nhóm trượt trông như thế nào, rồi dùng định lý Bayes để xem người này giống nhóm nào hơn. Hai cách này lần lượt dẫn tới k láng giềng gần nhất và Naive Bayes, và cách thứ hai còn cho thấy Naive Bayes, LDA và QDA thực ra là cùng một mô hình với ba ràng buộc khác nhau.

7.1Mô hình phân biệt và mô hình sinh#

Có hai cách để xây dựng một bộ phân loại theo xác suất. Mô hình phân biệt (discriminative model) mô hình hoá trực tiếp $p(y \mid x)$, tức xác suất của nhãn khi đã biết đầu vào. Hồi quy logistic ở Chương 6 là ví dụ điển hình; SVM và cây quyết định cũng được xếp vào nhóm này, dù chúng học thẳng biên quyết định mà không qua xác suất. Mô hình sinh (generative model) thì mô hình hoá $p(x \mid y)$ và $p(y)$, tức mô tả dữ liệu của mỗi lớp trông như thế nào và mỗi lớp phổ biến tới đâu, rồi dùng định lý Bayes để tính $p(y \mid x) \propto p(x \mid y)\,p(y)$. Naive Bayes, LDA và QDA thuộc nhóm này. Với sáu sinh viên, hồi quy logistic mô hình hoá thẳng xác suất đỗ theo số giờ ôn; một mô hình sinh thì mô tả số giờ ôn của những người đỗ, của những người trượt và tỉ lệ đỗ chung, rồi mới suy ra xác suất đỗ. Bảng dưới đặt hai cách cạnh nhau.

Mô hình sinh đặt nhiều giả định hơn về dữ liệu. Khi giả định đúng, nó cần ít dữ liệu hơn để đạt hiệu năng tốt; khi giả định sai, nó bị giới hạn bởi chính giả định đó. Ng và Jordan (2002) so sánh cặp Naive Bayes và hồi quy logistic và thấy đúng xu hướng này: Naive Bayes đạt tới mức sai số tiệm cận của nó nhanh hơn theo số mẫu, nhưng hồi quy logistic thường đạt mức sai số tiệm cận thấp hơn khi có đủ dữ liệu.

7.2Thuật toán k láng giềng gần nhất#

Định nghĩa 7.1 (k láng giềng gần nhất, k-NN)

Để phân loại một điểm mới $x$, tìm $k$ điểm trong tập huấn luyện gần $x$ nhất theo một khoảng cách cho trước, rồi dự đoán lớp chiếm đa số trong $k$ điểm đó. Với hồi quy, dự đoán trung bình nhãn của $k$ điểm đó.

k-NN không có bước huấn luyện theo nghĩa thông thường: nó chỉ lưu lại dữ liệu. Vì vậy nó được gọi là phương pháp lười (lazy learning) và phi tham số, vì "tham số" chính là toàn bộ dữ liệu và tăng theo $n$. Toàn bộ chi phí dồn vào lúc dự đoán: tìm láng giềng gần nhất bằng cách so với mọi điểm tốn $O(nd)$ cho mỗi truy vấn.

Với người ôn 3,6 giờ, láng giềng gần nhất là sinh viên 4, cách 0,4 giờ và đã trượt, nên 1-NN đoán trượt. Ba láng giềng gần nhất là sinh viên 4, 3 và 5, gồm hai người đỗ và một người trượt, nên 3-NN đoán đỗ; năm láng giềng gần nhất có ba người đỗ, nên 5-NN cũng đoán đỗ. Nhìn trên cả trục giờ ôn, 1-NN chia trục thành bốn đoạn: trượt dưới 2,5 giờ, đỗ từ 2,5 tới 3,5 giờ, trượt từ 3,5 tới 4,5 giờ, rồi đỗ từ 4,5 giờ trở lên. Đoạn trượt quanh 4 giờ tồn tại chỉ vì một người, sinh viên 4. Với $k = 3$, biên chỉ còn một điểm ở 3,5 giờ, đúng chỗ hồi quy logistic đặt biên ở Chương 6.

Chất lượng của k-NN phụ thuộc vào ba lựa chọn. Lựa chọn quan trọng nhất là số láng giềng $k$. Với $k = 1$, biên quyết định bám theo từng điểm dữ liệu và rất gồ ghề: độ chệch thấp nhưng phương sai cao, vì chỉ cần một điểm nhiễu là đủ đổi dự đoán của cả vùng quanh nó, như sinh viên 4 ở trên. Tăng $k$ làm biên trơn hơn, phương sai giảm và độ chệch tăng; ở cực điểm $k = n$, mọi dự đoán đều là lớp phổ biến nhất. Đây là đánh đổi độ chệch – phương sai ở dạng dễ thấy nhất, và $k$ được chọn bằng cross-validation (Mục 9.5). Lựa chọn thứ hai là khoảng cách. Khoảng cách Euclid là lựa chọn mặc định, nhưng nó chỉ có nghĩa khi các đặc trưng cùng thang đo: nếu một đặc trưng là thu nhập tính bằng đồng, cỡ hàng triệu, và một đặc trưng là tuổi, cỡ hàng chục, thì khoảng cách gần như chỉ phản ánh thu nhập. Lựa chọn thứ ba là cách bỏ phiếu: có thể cho mỗi láng giềng một phiếu như nhau, hoặc cho láng giềng gần hơn trọng số lớn hơn, chẳng hạn tỉ lệ với nghịch đảo khoảng cách.

Lưu ý

Luôn chuẩn hoá đặc trưng trước khi dùng k-NN hoặc bất kỳ phương pháp nào dựa trên khoảng cách (K-means ở Chương 15 cũng vậy). Tham số chuẩn hoá (trung bình, độ lệch chuẩn) chỉ ước lượng trên tập huấn luyện.

Dù đơn giản, k-NN có một bảo đảm lý thuyết khá mạnh. Gọi sai số Bayes $R^*$ là sai số nhỏ nhất mà bất kỳ bộ phân loại nào có thể đạt được trên phân phối dữ liệu.

Định lý 7.1 (Cover và Hart, 1967)

Với bài toán hai lớp, khi số điểm huấn luyện $n \to \infty$, sai số $R_{1\text{-NN}}$ của bộ phân loại 1 láng giềng gần nhất thoả

$$R^* \le R_{1\text{-NN}} \le 2R^*(1 - R^*) \le 2R^*.$$

Như vậy, với đủ dữ liệu, chỉ nhìn vào một láng giềng gần nhất đã cho sai số không quá hai lần sai số tốt nhất có thể. Nhưng "đủ dữ liệu" có thể là một lượng không tưởng khi số chiều lớn, vì một hiện tượng gọi là lời nguyền số chiều (curse of dimensionality). Giả sử dữ liệu phân bố đều trong hình lập phương đơn vị $[0, 1]^d$. Để một hình lập phương con quanh một điểm chứa được tỉ lệ $f$ số điểm dữ liệu, cạnh của nó phải dài $f^{1/d}$. Với $f = 0{,}01$, tức láng giềng là 1% dữ liệu gần nhất, cạnh cần dài $0{,}1$ khi $d = 2$, $0{,}63$ khi $d = 10$ và $0{,}955$ khi $d = 100$. Ở 100 chiều, "vùng lân cận" chứa 1% dữ liệu trải gần hết chiều dài mỗi cạnh, tức láng giềng gần nhất không còn gần theo nghĩa thông thường. Một hệ quả liên quan là ở số chiều cao, khoảng cách từ một điểm tới điểm gần nhất và tới điểm xa nhất trở nên gần bằng nhau, nên thứ hạng theo khoảng cách mang ít thông tin.

Vì vậy k-NN trên dữ liệu thô chỉ hiệu quả ở số chiều thấp. Ở số chiều cao, người ta áp dụng nó sau khi giảm chiều (Chương 14), hoặc trong một không gian embedding đã được học sao cho khoảng cách phản ánh độ giống nhau về nghĩa. Tìm kiếm ảnh, tìm kiếm văn bản theo ngữ nghĩa và bước truy xuất trong hệ thống RAG đều là k-NN trong không gian embedding, kết hợp với các chỉ mục tìm kiếm gần đúng để tránh chi phí $O(nd)$ mỗi truy vấn. Giáo trình Ứng dụng LLM trình bày các chỉ mục đó.

7.3Naive Bayes#

Theo định lý Bayes, bộ phân loại tối ưu chọn lớp có hậu nghiệm lớn nhất:

$$\hat y = \arg\max_k \; p(y = k \mid x) = \arg\max_k \; p(x \mid y = k)\,p(y = k).$$

Ước lượng $p(y = k)$ thì đơn giản: tỉ lệ các điểm thuộc lớp $k$ trong tập huấn luyện. Khó khăn nằm ở $p(x \mid y = k)$ khi $x$ có nhiều chiều. Với $d$ đặc trưng nhị phân, một phân phối tổng quát trên $x$ cần $2^d - 1$ tham số cho mỗi lớp, quá nhiều để ước lượng từ dữ liệu.

Định nghĩa 7.2 (Giả thiết Naive Bayes)

Các đặc trưng độc lập có điều kiện khi đã biết lớp:

$$p(x \mid y = k) = \prod_{j=1}^{d} p(x_j \mid y = k).$$

Với giả thiết này, thay vì một phân phối $d$ chiều ta chỉ cần ước lượng $d$ phân phối một chiều cho mỗi lớp, và số tham số giảm từ cấp số mũ xuống tuyến tính theo $d$. Mỗi phân phối một chiều có thể là Bernoulli với đặc trưng nhị phân, như từ có xuất hiện trong thư hay không, là đa thức với số lần xuất hiện của từ, hoặc là Gauss với đặc trưng liên tục.

Cần chú ý chữ "có điều kiện". Giả thiết không nói các đặc trưng độc lập với nhau, mà nói chúng độc lập khi đã biết lớp. Trong một thư rác, từ "miễn phí" và từ "khuyến mãi" hay cùng xuất hiện, tức không độc lập; Naive Bayes giả định rằng trong riêng nhóm thư rác, biết thư có "miễn phí" không cho thêm thông tin gì về việc có "khuyến mãi". Giả thiết này gần như luôn sai với dữ liệu thật. Tuy vậy Naive Bayes vẫn thường phân loại tốt, vì để chọn đúng nhãn chỉ cần thứ tự của các $p(y = k \mid x)$ đúng, không cần giá trị của chúng đúng. Ngược lại, các xác suất do Naive Bayes đưa ra thường bị đẩy về gần 0 hoặc 1 quá mức, vì những bằng chứng tương quan với nhau bị đếm nhiều lần như thể độc lập, nên không nên dùng đầu ra của nó như xác suất đã hiệu chuẩn.

Ví dụ 7.1 (Lọc thư rác với hai từ)

Tập huấn luyện có 4 thư rác và 6 thư thường. Từ "miễn phí" xuất hiện trong 3 thư rác và 1 thư thường; từ "cuộc họp" xuất hiện trong 0 thư rác và 4 thư thường. Dùng mô hình Bernoulli và ước lượng mỗi xác suất bằng tần suất:

$$\begin{aligned} p(\text{miễn phí} \mid \text{rác}) &= \tfrac34, & p(\text{miễn phí} \mid \text{thường}) &= \tfrac16, \\ p(\text{cuộc họp} \mid \text{rác}) &= 0, & p(\text{cuộc họp} \mid \text{thường}) &= \tfrac46. \end{aligned}$$

Mô hình Bernoulli tính cả những từ vắng mặt: thư không chứa "cuộc họp" nhận thừa số $1 - p(\text{cuộc họp} \mid \text{lớp})$. Một thư mới chỉ chứa "miễn phí" mà không chứa "cuộc họp". Điểm của lớp rác là $0{,}4 \times \tfrac34 \times 1 = 0{,}3$, điểm của lớp thường là $0{,}6 \times \tfrac16 \times \tfrac13 \approx 0{,}033$, nên $p(\text{rác} \mid x) = 0{,}9$. Một thư khác chứa cả hai từ thì điểm của lớp rác là $0{,}4 \times \tfrac34 \times 0 = 0$, và $p(\text{rác} \mid x) = 0$.

Kết quả thứ hai không ổn. Vì Naive Bayes nhân các xác suất, một thừa số bằng 0 làm cả tích bằng 0: mọi thư chứa "cuộc họp" sẽ có xác suất là rác bằng đúng 0, bất kể nó chứa bao nhiêu từ đáng ngờ khác, chỉ vì "cuộc họp" chưa từng xuất hiện trong 4 thư rác của tập huấn luyện. Một từ chưa từng gặp trong một lớp đủ để phủ quyết mọi bằng chứng còn lại. Cách khắc phục là cộng thêm một lượng nhỏ vào mọi ô đếm. Với đặc trưng rời rạc có $V$ giá trị,

$$p(x_j = v \mid y = k) = \frac{N_{kjv} + \alpha}{N_k + \alpha V},$$

trong đó $N_{kjv}$ là số lần đặc trưng $j$ nhận giá trị $v$ trong lớp $k$, và $N_k$ là số điểm của lớp $k$. Với $\alpha = 1$ ta có làm trơn Laplace; với $0 < \alpha < 1$, cách làm gọi là làm trơn Lidstone. Mục 10.4 chỉ ra rằng công thức này là một ước lượng MAP với tiên nghiệm Dirichlet.

Tính lại Ví dụ 7.1 với $\alpha = 1$; mỗi từ là đặc trưng nhị phân nên $V = 2$:

$$\begin{aligned} p(\text{miễn phí} \mid \text{rác}) &= \tfrac{3+1}{4+2} = 0{,}667, \\ p(\text{miễn phí} \mid \text{thường}) &= \tfrac{1+1}{6+2} = 0{,}25, \\ p(\text{cuộc họp} \mid \text{rác}) &= \tfrac{0+1}{4+2} = 0{,}167, \\ p(\text{cuộc họp} \mid \text{thường}) &= \tfrac{4+1}{6+2} = 0{,}625. \end{aligned}$$

Với thư chứa cả hai từ, điểm của lớp rác giờ là $0{,}4 \times 0{,}667 \times 0{,}167 = 0{,}0444$ và điểm của lớp thường là $0{,}6 \times 0{,}25 \times 0{,}625 = 0{,}0938$. Chuẩn hoá, $p(\text{rác} \mid x) = 0{,}0444/(0{,}0444 + 0{,}0938) \approx 0{,}32$: thư được xếp là thư thường, nhưng bằng chứng từ "miễn phí" vẫn được tính. Với thư chỉ chứa "miễn phí", điểm của hai lớp là $0{,}4 \times 0{,}667 \times 0{,}833 = 0{,}222$ và $0{,}6 \times 0{,}25 \times 0{,}375 = 0{,}056$, cho $p(\text{rác} \mid x) \approx 0{,}80$ thay vì 0,9: sau khi làm trơn, các ước lượng bớt cực đoan hơn.

Lưu ý (Tính trong không gian logarit)

Tích của hàng nghìn xác suất nhỏ nhanh chóng nhỏ hơn số dương nhỏ nhất biểu diễn được bằng số thực dấu phẩy động và bị làm tròn về 0. Các cài đặt thực tế luôn cộng logarit thay vì nhân xác suất: $\log p(y=k) + \sum_j \log p(x_j \mid y = k)$.

7.4Naive Bayes, LDA và QDA#

Khi đặc trưng liên tục, lựa chọn tự nhiên cho $p(x \mid y = k)$ là phân phối Gauss nhiều chiều $\mathcal{N}(\mu_k, \Sigma_k)$. Mô hình này gọi chung là phân tích biệt thức Gauss (Gaussian discriminant analysis). Ba thuật toán quen thuộc là ba cách ràng buộc các ma trận hiệp phương sai $\Sigma_k$, như bảng dưới cho thấy.

Dòng đầu thể hiện ý chính của mục này: với đặc trưng Gauss, giả thiết độc lập có điều kiện của Naive Bayes tương đương với việc ép $\Sigma_k$ thành ma trận đường chéo. Lý do là một phân phối Gauss nhiều chiều có ma trận hiệp phương sai đường chéo phân tích được thành tích các phân phối Gauss một chiều, và ngược lại. Naive Bayes Gauss vì vậy không phải một thuật toán riêng biệt, mà là bộ phân loại Gauss với một ràng buộc cụ thể.

Thí nghiệm kiểm tra điều này bằng hai cài đặt độc lập: một bên nhân các mật độ Gauss một chiều lại với nhau đúng như định nghĩa Naive Bayes, không đụng tới ma trận hiệp phương sai; một bên dùng mật độ Gauss nhiều chiều với $\Sigma$ đường chéo.

sai khac lon nhat cua hieu diem phan biet: 1.222e-08
hai mo hinh du bao giong nhau o 100.0% so mau
ham quyet dinh cua LDA co TUYEN TINH khong? sai so khop tuyen tinh = 4.441e-15  -> co
con QDA thi sao? sai so khop tuyen tinh = 1.780e+01 -> khong, no bac hai

Hai cài đặt cho hàm phân biệt lệch nhau $1{,}2 \times 10^{-8}$, giới hạn bởi lượng nhỏ thêm vào đường chéo để nghịch đảo ma trận ổn định, và dự đoán trùng nhau trên 100% số mẫu.

Hai dòng cuối kiểm chứng một kết quả lý thuyết. Viết logarit tỉ số hậu nghiệm của hai lớp:

$$\begin{aligned} \log\frac{p(y=1 \mid x)}{p(y=0 \mid x)} &= -\tfrac12 (x-\mu_1)^\top\Sigma_1^{-1}(x-\mu_1) \\ &\quad + \tfrac12 (x-\mu_0)^\top\Sigma_0^{-1}(x-\mu_0) + \text{hằng số}. \end{aligned}$$

Khai triển hai dạng toàn phương, số hạng bậc hai theo $x$ là $-\tfrac12 x^\top(\Sigma_1^{-1} - \Sigma_0^{-1})\,x$. Nếu hai lớp dùng chung ma trận hiệp phương sai, $\Sigma_1 = \Sigma_0 = \Sigma$, số hạng này triệt tiêu và phần còn lại tuyến tính theo $x$:

$$\log\frac{p(y=1 \mid x)}{p(y=0 \mid x)} = (\mu_1 - \mu_0)^\top \Sigma^{-1} x + \text{hằng số}.$$

Vì vậy LDA có biên quyết định tuyến tính: trong thí nghiệm, khớp hàm quyết định của LDA bằng một hàm tuyến tính cho sai số $4{,}4 \times 10^{-15}$. Khi mỗi lớp có ma trận riêng, số hạng bậc hai còn lại và biên là mặt bậc hai: khớp tuyến tính cho sai số 17,8.

Công thức trên còn cho thấy hậu nghiệm của LDA có dạng $p(y = 1 \mid x) = \sigma(w^\top x + b)$, đúng dạng của hồi quy logistic. Hai phương pháp cho ra cùng họ hàm nhưng ước lượng tham số theo hai cách: LDA ước lượng $\mu_k$ và $\Sigma$ rồi suy ra $w$, còn hồi quy logistic tối ưu trực tiếp $w$ trên $p(y \mid x)$. Khi dữ liệu đúng là Gauss với $\Sigma$ chung, LDA dùng dữ liệu hiệu quả hơn; khi giả định sai, hồi quy logistic thường bền vững hơn. Đây là một trường hợp cụ thể của so sánh giữa mô hình sinh và mô hình phân biệt ở Mục 7.1.

Sáu sinh viên cho thấy khác biệt đó bằng số. Gọi đỗ là lớp 1 và trượt là lớp 0. Với một đặc trưng là số giờ ôn, trung bình của nhóm trượt là $\mu_0 = 7/3 \approx 2{,}33$ giờ, của nhóm đỗ là $\mu_1 = 14/3 \approx 4{,}67$ giờ, và phương sai chung ước lượng bằng hợp lý cực đại là $\sigma^2 = 14/9 \approx 1{,}56$. Ở một chiều, hệ số của $x$ trong công thức trên là $(\mu_1 - \mu_0)/\sigma^2 = (7/3)/(14/9) = 1{,}5$. Hằng số là $-(\mu_1^2 - \mu_0^2)/(2\sigma^2) = -5{,}25$, cộng thêm $\log(\pi_1/\pi_0)$ với $\pi_k$ là tỉ lệ của lớp $k$, ở đây bằng 0 vì hai nhóm đông như nhau. Vậy log tỉ lệ cược của LDA là $1{,}5x - 5{,}25$. Biên quyết định nằm ở 3,5 giờ, trùng với hồi quy logistic ở Chương 6, nhưng độ dốc 1,5 lớn hơn độ dốc 1,214 của hồi quy logistic: với người ôn 3 giờ, LDA cho xác suất đỗ 0,321, còn hồi quy logistic cho 0,353. Hai nhóm ở đây tình cờ có cùng phương sai $14/9$, nên QDA cho đúng kết quả của LDA; và với một đặc trưng duy nhất, ma trận hiệp phương sai nào cũng là đường chéo, nên Naive Bayes Gauss cũng cho cùng kết quả.

Về chi phí, QDA cần ước lượng $K$ ma trận hiệp phương sai, mỗi ma trận có $d(d+1)/2$ tham số, trong khi LDA chỉ cần một ma trận. Với $d = 100$ và $K = 10$, QDA cần khoảng 50 000 tham số cho các ma trận hiệp phương sai, LDA cần khoảng 5 000 và Naive Bayes Gauss chỉ cần 1 000. Khi $n$ nhỏ, QDA dễ overfitting và ma trận ước lượng có thể suy biến.

7.5Tóm tắt#

Mô hình phân biệt học trực tiếp $p(y \mid x)$, còn mô hình sinh học $p(x \mid y)$ và $p(y)$ rồi suy ngược bằng định lý Bayes; mô hình sinh cần ít dữ liệu hơn khi giả định đúng nhưng bị giới hạn khi giả định sai. k-NN không học tham số mà tra cứu các điểm gần nhất: với sáu sinh viên, 1-NN tạo ra một đoạn trượt quanh 4 giờ chỉ vì một người, còn 3-NN cho lại biên 3,5 giờ. Nó cần chuẩn hoá đặc trưng, chọn $k$ theo đánh đổi độ chệch – phương sai, và mất tác dụng ở số chiều cao vì lời nguyền số chiều. Naive Bayes giả định các đặc trưng độc lập khi đã biết lớp, nên chỉ cần ước lượng các phân phối một chiều; nó vẫn phân loại tốt dù giả định sai, nhưng cho xác suất quá tự tin, và nếu không làm trơn Laplace thì một số đếm bằng 0 đủ để phủ quyết mọi bằng chứng khác. Với đặc trưng Gauss, Naive Bayes, LDA và QDA là cùng một mô hình với ba ràng buộc trên ma trận hiệp phương sai, và ma trận dùng chung làm biên của LDA tuyến tính; trên sáu sinh viên, LDA đặt biên ở đúng chỗ hồi quy logistic đặt, chỉ khác độ dốc.

Đến đây ta đã có năm bộ phân loại. Câu hỏi tự nhiên tiếp theo là làm sao so sánh chúng, và câu hỏi đó khó hơn vẻ ngoài: Ví dụ 3.3 đã cho thấy một xét nghiệm "đúng 99%" có thể sai ở 5 trên 6 ca dương tính. Chương 8 bàn về cách đánh giá một mô hình phân loại.