6Phân loại tuyến tính#

Chương 4 và 5 dự đoán giá căn hộ, một số thực. Phần lớn bài toán thực tế lại cần dự đoán một lớp: thư là rác hay không, giao dịch có gian lận không, sinh viên đỗ hay trượt. Ta lấy một ví dụ nhỏ để đi suốt chương: sáu sinh viên, số giờ mỗi người ôn thi và kết quả.

Nhìn chung ôn nhiều thì dễ đỗ hơn, nhưng sinh viên 3 ôn 3 giờ đã đỗ còn sinh viên 4 ôn 4 giờ lại trượt, nên không có ngưỡng giờ ôn nào chia đúng cả sáu người. Dữ liệu thật thường như vậy, và cách mỗi thuật toán xử lý những điểm chồng lấn như sinh viên 3 và 4 là chỗ chúng khác nhau.

Cách đơn giản nhất là dùng lại mô hình tuyến tính, nhưng lấy dấu của $w^\top x + b$ làm nhãn. Ba thuật toán kinh điển làm đúng như vậy: perceptron, hồi quy logistic và hồi quy softmax. Chúng dùng chung mô hình và chung cách tối ưu, chỉ khác nhau ở hàm mất mát, và chính khác biệt đó quyết định perceptron có hội tụ hay không, hồi quy logistic có cho ra xác suất hay không. Ta bắt đầu bằng việc đặt các hàm mất mát cạnh nhau.

6.1Mô hình tuyến tính và các hàm mất mát cho phân loại#

Xét bài toán phân loại hai lớp với nhãn $y_i \in \{-1, +1\}$. Một bộ phân loại tuyến tính tính điểm số $s = w^\top x + b$ rồi dự đoán lớp $+1$ nếu $s > 0$ và lớp $-1$ nếu $s < 0$. Theo Mục 2.2, biên quyết định $w^\top x + b = 0$ là một siêu phẳng. Với sáu sinh viên, một bộ phân loại tự nhiên là $s = x - 3{,}5$, tức dự đoán đỗ khi ôn hơn 3,5 giờ; nó đoán sai đúng hai người, sinh viên 3 và 4.

Định nghĩa 6.1 (Lề của một điểm)

Lề (margin) của điểm $(x_i, y_i)$ đối với bộ phân loại $(w, b)$ là

$$m_i = y_i\,(w^\top x_i + b).$$

Lề dương nghĩa là điểm được phân loại đúng, lề âm nghĩa là phân loại sai, và trị tuyệt đối của lề cho biết điểm nằm xa biên quyết định tới mức nào, tỉ lệ với khoảng cách ở Định lý 2.1. Với bộ phân loại $s = x - 3{,}5$ và nhãn đỗ là $+1$, trượt là $-1$, lề của sáu sinh viên là 2,5; 1,5; $-0{,}5$; $-0{,}5$; 1,5; 2,5. Hai người bị đoán sai có lề âm, còn hai người ở hai đầu, ôn 1 giờ và 6 giờ, nằm xa biên nhất. Mọi hàm mất mát cho phân loại hai lớp trong chương này đều viết được như một hàm của lề, như Hình 5 và bảng dưới cho thấy.

Áp dụng bốn hàm mất mát cho sáu sinh viên với bộ phân loại $s = x - 3{,}5$:

Bảng cho thấy mỗi hàm mất mát chú ý tới ai. Perceptron chỉ phạt hai người bị đoán sai, và phạt nhẹ vì họ nằm sát biên. Hinge cũng chỉ phạt hai người đó nhưng nặng hơn, và sẽ phạt cả người được đoán đúng nếu lề của họ nhỏ hơn 1. Logistic phạt tất cả, kể cả người được đoán đúng ở xa biên, chỉ là phạt rất nhẹ: nó luôn còn lý do để đẩy các điểm ra xa biên hơn nữa.

Mất mát 0–1 đếm số điểm bị phân loại sai, đúng là thứ ta muốn giảm. Nhưng nó là hàm bậc thang: đạo hàm bằng 0 ở mọi chỗ khả vi và không tồn tại tại $m = 0$, nên gradient không chỉ ra hướng nào để cải thiện. Hơn nữa, bài toán cực tiểu hoá mất mát 0–1 trên một tập dữ liệu là bài toán NP-khó. Vì vậy người ta thay nó bằng một hàm thay thế lồi (convex surrogate) để có thể tối ưu bằng gradient.

Hinge và logistic viết theo logarit cơ số 2 còn là chặn trên của mất mát 0–1: với mọi $m$, giá trị của chúng lớn hơn hoặc bằng $\mathbb{1}[m \le 0]$. Do đó làm nhỏ tổng mất mát hinge hoặc logistic kéo theo làm nhỏ số điểm bị phân loại sai trên tập huấn luyện. Mất mát perceptron không có tính chất này: tại $m = 0$ nó bằng 0 trong khi mất mát 0–1 bằng 1, và với lề âm rất nhỏ nó gần bằng 0. Đây là một cách nhìn vì sao perceptron yếu hơn hai thuật toán kia, như Mục 6.2 sẽ cho thấy bằng thí nghiệm. Dùng logarit tự nhiên thay cho cơ số 2 chỉ nhân hàm mất mát logistic với hằng số $\ln 2$, không làm thay đổi nghiệm.

6.2Perceptron#

Perceptron (Rosenblatt, 1958) là thuật toán học đầu tiên cho bộ phân loại tuyến tính. Để đơn giản, ta gộp hệ số chặn vào $w$ bằng cách thêm thành phần hằng 1 vào $x$ như ở Chương 4.

Định nghĩa 6.2 (Thuật toán perceptron)

Khởi tạo $w = 0$. Lần lượt duyệt các điểm dữ liệu; mỗi khi gặp một điểm bị phân loại sai hoặc nằm đúng trên biên, tức $y_i\, w^\top x_i \le 0$, cập nhật

$$w \leftarrow w + y_i x_i.$$

Dừng khi một lượt duyệt toàn bộ dữ liệu không có cập nhật nào.

Bước cập nhật có ý nghĩa trực quan: nếu một điểm lớp $+1$ bị đoán sai, cộng $x_i$ vào $w$ làm tăng $w^\top x_i$ thêm $\|x_i\|^2$, kéo điểm số của nó về phía dương. Quy tắc này chính là SGD trên mất mát perceptron với tốc độ học 1, vì đạo hàm của $\max(0, -m_i)$ theo $w$ bằng $-y_i x_i$ khi $m_i < 0$ và bằng 0 khi $m_i > 0$.

Với dữ liệu tách được tuyến tính, perceptron có một bảo đảm hội tụ rất gọn.

Định lý 6.1 (Novikoff, 1962)

Giả sử mọi điểm dữ liệu thoả $\|x_i\| \le R$, và tồn tại vector đơn vị $u$ sao cho $y_i\,u^\top x_i \ge \gamma > 0$ với mọi $i$ (dữ liệu tách được với lề $\gamma$). Khi đó perceptron thực hiện không quá $(R/\gamma)^2$ lần cập nhật.

Chặn trên trong định lý không phụ thuộc số điểm dữ liệu $n$ hay số chiều $d$, mà chỉ phụ thuộc tỉ số giữa kích thước của dữ liệu và độ rộng của lề. Thí nghiệm sinh dữ liệu tách được với lề $\gamma$ cho trước để kiểm tra.

Ở cả bốn trường hợp, số lần cập nhật nằm dưới chặn lý thuyết, và tăng lên khi lề hẹp lại, đúng xu hướng mà định lý dự báo. Chặn khá lỏng so với số đo, điều thường gặp với các chặn trong trường hợp xấu nhất.

Trên dữ liệu không tách được tuyến tính, tình hình khác hẳn:

hoi tu = False, so lan sai sau 2000 luot = 17,977

Thuật toán không dừng. Định lý Novikoff chỉ áp dụng cho dữ liệu tách được; ngoài trường hợp đó, perceptron không có bảo đảm nào và có thể dao động mãi mãi. Nguyên nhân nhìn thấy được trên Hình 5: mất mát perceptron bằng 0 ngay khi $m \ge 0$, nên thuật toán ngừng điều chỉnh một điểm ngay khi điểm đó vừa được phân loại đúng, dù nó nằm sát biên. Khi các lớp chồng lấn, sửa một điểm sai này lại làm một điểm khác thành sai, và quá trình lặp lại không kết thúc. Sáu sinh viên là phiên bản nhỏ nhất của tình huống này: muốn đoán đúng sinh viên 3 thì ngưỡng phải dưới 3 giờ, muốn đoán đúng sinh viên 4 thì ngưỡng phải trên 4 giờ, nên mỗi lần perceptron sửa cho người này thì người kia lại sai.

6.3Hồi quy logistic#

Hồi quy logistic khắc phục hạn chế của perceptron bằng một hàm mất mát trơn và không bao giờ bằng 0. Thay vì chỉ đưa ra nhãn, mô hình đưa ra xác suất. Trong mục này ta dùng nhãn $y_i \in \{0, 1\}$, cách viết thuận tiện hơn cho xác suất.

Định nghĩa 6.3 (Hồi quy logistic)

Mô hình hồi quy logistic cho xác suất lớp dương là

$$p(y = 1 \mid x) = \sigma(w^\top x), \qquad \sigma(z) = \frac{1}{1 + e^{-z}},$$

trong đó $\sigma$ là hàm sigmoid. Tham số được học bằng cách cực tiểu hoá hàm mất mát cross-entropy

$$\begin{aligned} L(w) &= -\frac{1}{n}\sum_{i=1}^{n}\Big[y_i \log p_i + (1-y_i)\log(1-p_i)\Big], \\ p_i &= \sigma(w^\top x_i). \end{aligned}$$

Hàm sigmoid ép mọi số thực vào khoảng $(0, 1)$, với $\sigma(0) = 0{,}5$. Nghịch đảo của nó cho một cách hiểu hệ số rất cụ thể: $w^\top x = \log\frac{p}{1-p}$, tức mô hình tuyến tính đang dự đoán log tỉ lệ cược (log-odds). Tăng đặc trưng $x_j$ thêm một đơn vị làm log tỉ lệ cược tăng $w_j$, tức nhân tỉ lệ cược với $e^{w_j}$. Tên gọi "hồi quy" đến từ đây: mô hình hồi quy log tỉ lệ cược theo $x$, dù bài toán là phân loại.

Ví dụ 6.1

Với $w = 1$ và hệ số chặn $-3{,}5$, xác suất đỗ mà mô hình gán cho sáu sinh viên là $\sigma(x - 3{,}5)$:

$$0{,}076;\quad 0{,}182;\quad 0{,}378;\quad 0{,}622;\quad 0{,}818;\quad 0{,}924.$$

Sinh viên 3 được cho 38% khả năng đỗ dù thực tế đã đỗ, sinh viên 4 được cho 62% dù đã trượt. Mỗi giờ ôn thêm nhân tỉ lệ cược đỗ với $e^1 \approx 2{,}72$. Cross-entropy cộng $-\log p_i$ cho người đỗ và $-\log(1 - p_i)$ cho người trượt; sáu số hạng là 0,079; 0,201; 0,974; 0,974; 0,201; 0,079, trung bình $L = 0{,}418$. Hai người bị đoán sai đóng góp hơn ba phần tư tổng mất mát.

Gradient của cross-entropy có dạng rất gọn. Dùng tính chất $\sigma'(z) = \sigma(z)\,(1 - \sigma(z))$, đạo hàm của số hạng thứ $i$ theo $w$ là

$$\begin{aligned} &\frac{\partial}{\partial w}\Big[-y_i\log p_i - (1-y_i)\log(1-p_i)\Big] \\ &\qquad = -y_i(1-p_i)\,x_i + (1-y_i)\,p_i\, x_i = (p_i - y_i)\,x_i. \end{aligned}$$

Lấy trung bình trên mọi điểm, ta được

$$\nabla_w L = \frac{1}{n}X^\top(p - y).$$

Mỗi điểm dữ liệu kéo trọng số theo hướng $x_i$ của chính nó, với độ mạnh bằng sai lệch $p_i - y_i$ giữa xác suất dự đoán và nhãn: điểm được đoán gần đúng gần như không kéo, điểm bị đoán sai kéo mạnh nhất. Ở Ví dụ 6.1, các sai lệch là 0,076; 0,182; $-0{,}622$; 0,622; $-0{,}182$; $-0{,}076$. Chúng có tổng bằng 0, nên đạo hàm theo hệ số chặn bằng 0, còn đạo hàm theo $w$ là $\tfrac16\sum_i (p_i - y_i)\,x_i \approx -0{,}051$. Đạo hàm âm nên tăng $w$ còn giảm được mất mát. Chạy tối ưu tới hội tụ được $w \approx 1{,}214$ và hệ số chặn $\approx -4{,}249$: biên quyết định vẫn ở 3,5 giờ, mất mát giảm còn 0,413, và mỗi giờ ôn thêm nhân tỉ lệ cược với khoảng 3,37.

Công thức có cùng dạng với gradient của hồi quy tuyến tính, $\tfrac{2}{n}X^\top(Xw - y)$: ma trận dữ liệu chuyển vị nhân với vector sai lệch giữa dự đoán và nhãn. Đây không phải trùng hợp. Mục 10.3 giải thích rằng cả hai đều là mô hình tuyến tính tổng quát với hàm liên kết chính tắc, và mọi mô hình như vậy đều có gradient dạng này.

Hàm mất mát cross-entropy của hồi quy logistic là hàm lồi theo $w$ (Mục 11.4 kiểm tra bằng số), nên gradient descent với tốc độ học phù hợp hội tụ về cực tiểu toàn cục, nếu cực tiểu đó tồn tại. Mục 6.5 trình bày trường hợp nó không tồn tại.

Lưu ý (Vì sao không dùng bình phương sai số cho phân loại)

Có hai lý do. Thứ nhất, $\sum_i (y_i - \sigma(w^\top x_i))^2$ không lồi theo $w$, nên mất bảo đảm hội tụ về cực tiểu toàn cục. Thứ hai, khi mô hình đoán sai với độ tự tin cao, ví dụ $p_i \approx 0$ trong khi $y_i = 1$, đạo hàm của bình phương sai số chứa thừa số $\sigma'(z) = p_i(1-p_i) \approx 0$ nên gần như triệt tiêu, và mô hình học rất chậm từ chính những lỗi nặng nhất. Gradient của cross-entropy là $(p_i - y_i)x_i \approx -x_i$, không bị triệt tiêu.

6.4Hồi quy softmax#

Khi kết quả có nhiều hơn hai mức, chẳng hạn trượt, đỗ và đỗ loại giỏi, ta có $K > 2$ lớp. Mỗi lớp $k$ có một vector trọng số $w_k$ và một điểm số $s_k = w_k^\top x$. Hàm softmax biến $K$ điểm số thành $K$ xác suất.

Định nghĩa 6.4 (Hồi quy softmax)

Mô hình hồi quy softmax cho

$$p(y = k \mid x) = \frac{\exp(w_k^\top x)}{\sum_{j=1}^{K}\exp(w_j^\top x)}, \qquad k = 1, \dots, K,$$

và được huấn luyện bằng cross-entropy nhiều lớp $L = -\frac1n\sum_i \log p(y = y_i \mid x_i)$.

Softmax có một tính chất cần biết: cộng cùng một vector $c$ vào mọi $w_k$ không làm thay đổi xác suất, vì cả tử số và mẫu số đều nhân thêm $\exp(c^\top x)$. Do đó chỉ hiệu giữa các vector trọng số được dữ liệu xác định, còn bản thân từng vector thì không. Trên thực tế người ta cố định một vector bằng 0, hoặc thêm regularization để chọn ra một nghiệm.

Tính chất này dẫn tới một liên hệ quan trọng. Với $K = 2$,

$$p(y = 1 \mid x) = \frac{e^{w_1^\top x}}{e^{w_1^\top x} + e^{w_0^\top x}} = \frac{1}{1 + e^{-(w_1 - w_0)^\top x}} = \sigma\big((w_1 - w_0)^\top x\big).$$

Vậy hồi quy softmax với hai lớp chính là hồi quy logistic, với vector trọng số $w = w_1 - w_0$. Thí nghiệm khớp cả hai mô hình trên cùng dữ liệu, không dùng regularization, chạy tới hội tụ:

Sai khac lon nhat giua xac suat cua logistic va cua softmax(K=2): 3.331e-16
Hieu hai cot trong so cua softmax:  [ 0.10864027  1.53215349 -1.83422929]
Trong so cua hoi quy logistic:      [ 0.10864027  1.53215349 -1.83422929]
  -> lech 1.554e-15
Tong hai cot trong so cua softmax (phai bang 0): 6.661e-16

Hai mô hình cho xác suất lệch nhau $3{,}3 \times 10^{-16}$ và trọng số lệch nhau $1{,}6 \times 10^{-15}$, tức trùng nhau tới sai số làm tròn. Dòng cuối cho thấy thuật toán, xuất phát từ $w_0 = w_1 = 0$, luôn giữ tổng hai vector bằng 0, vì gradient của hai lớp luôn đối nhau.

Lưu ý (Tính softmax ổn định số học)

Khi các điểm số lớn, $\exp(s_k)$ có thể vượt quá giới hạn của số thực dấu phẩy động. Vì cộng cùng một hằng số vào mọi điểm số không đổi kết quả, các thư viện luôn tính $\operatorname{softmax}(s - \max_k s_k)$ để số mũ lớn nhất bằng 0.

6.5Dữ liệu tách được và sự cần thiết của regularization#

Có một trường hợp hồi quy logistic không có nghiệm, và trường hợp này gặp trên thực tế nhiều hơn người ta nghĩ.

Giả sử dữ liệu tách được hoàn toàn: tồn tại $w$ sao cho mọi điểm lớp 1 có $w^\top x > 0$ và mọi điểm lớp 0 có $w^\top x < 0$. Nhân $w$ với một số $c > 1$ không đổi biên quyết định, nhưng đẩy mọi xác suất $p_i$ về gần 0 hoặc 1 hơn, tức gần nhãn đúng hơn, nên hàm mất mát giảm. Hàm mất mát giảm mãi khi $c \to \infty$ mà không bao giờ đạt giá trị nhỏ nhất. Do đó không tồn tại nghiệm hữu hạn, và gradient descent làm $\|w\|$ tăng không giới hạn.

Sáu sinh viên cho thấy điều này bằng số. Đổi kết quả của sinh viên 3 và 4 cho nhau thì dữ liệu tách được ở ngưỡng 3,5 giờ. Giữ biên ở 3,5 giờ và tăng dần độ dốc $w$, cross-entropy là 0,2515 ở $w = 1$, 0,1229 ở $w = 2$, 0,0431 ở $w = 4$ và 0,0061 ở $w = 8$: càng dốc càng tốt, không có điểm dừng. Thí nghiệm dưới chạy gradient descent trên một tập dữ liệu tách được lớn hơn.

Không có regularization, chuẩn của $w$ tăng chậm dần nhưng không có dấu hiệu dừng. Về lý thuyết, trên dữ liệu tách được, gradient descent làm $\|w\|$ tăng theo logarit của số vòng lặp, còn hướng của $w$ tiến dần tới hướng của siêu phẳng có lề lớn nhất (Soudry và cộng sự, 2018). Thêm thành phần regularization $\lambda\|w\|^2$ với $\lambda = 0{,}01$ làm hàm mất mát có cực tiểu duy nhất, và $\|w\|$ đứng yên ở 3,993 từ vòng lặp thứ 500.

Hiện tượng này có mấy hệ quả thực tế. LogisticRegression của scikit-learn mặc định dùng regularization $\ell_2$ với $C = 1{,}0$, trong đó $C$ là nghịch đảo của cường độ regularization, và đây là lựa chọn có chủ đích. Khi thấy hệ số hồi quy logistic lớn bất thường, nên kiểm tra xem có đặc trưng nào làm lộ nhãn không, vì dữ liệu tách được hoàn toàn thường là dấu hiệu của rò rỉ dữ liệu. Và hiện tượng tương tự xuất hiện với mạng nơ-ron phân loại, là một trong các lý do dùng weight decay (xem Chương 6 của Học sâu).

6.6Các lỗi thường gặp#

Bảng dưới gom các phát biểu sai hay gặp về phân loại tuyến tính, cùng điều đúng tương ứng.

6.7Tóm tắt#

Perceptron, hồi quy logistic và hồi quy softmax dùng chung mô hình tuyến tính và khác nhau ở hàm mất mát, viết được như hàm của lề $m = y(w^\top x + b)$. Mất mát 0–1 không tối ưu trực tiếp được, nên được thay bằng các hàm lồi; hinge và logistic là chặn trên của nó, còn mất mát perceptron thì không. Với sáu sinh viên, perceptron và hinge chỉ phạt hai người bị đoán sai, còn logistic phạt cả những người được đoán đúng nhưng chưa đủ xa biên. Perceptron hội tụ sau không quá $(R/\gamma)^2$ lần cập nhật trên dữ liệu tách được, nhưng dao động mãi trên dữ liệu chồng lấn. Hồi quy logistic dự đoán log tỉ lệ cược, có gradient $\tfrac1n X^\top(p - y)$ cùng dạng với hồi quy tuyến tính, trong đó mỗi điểm kéo trọng số theo sai lệch của chính nó; softmax hai lớp trùng với nó tới sai số làm tròn. Trên dữ liệu tách được hoàn toàn, hồi quy logistic không có nghiệm hữu hạn và cần regularization.

Cả ba thuật toán trên đều học trực tiếp một biên quyết định. Chương 7 xét hai cách tiếp cận khác: không học tham số nào mà tra cứu những điểm gần nhất, hoặc mô tả dữ liệu của từng lớp rồi suy ngược bằng định lý Bayes.