12Tối ưu lồi và đối ngẫu Lagrange#

SVM ở Chương 13 là một bài toán tối ưu có ràng buộc: tìm siêu phẳng có lề lớn nhất, với điều kiện mọi điểm nằm đúng phía. Gradient descent không xử lý trực tiếp được ràng buộc, nên ta cần một công cụ khác. Công cụ đó là phương pháp Lagrange, với ý tưởng thay việc cấm vi phạm ràng buộc bằng việc tính giá cho mỗi đơn vị vi phạm. Từ ý tưởng này sẽ ra bài toán đối ngẫu và điều kiện KKT, và từ điều kiện KKT sẽ ra khái niệm vector hỗ trợ. Một ví dụ một biến được dùng xuyên suốt chương để mọi khái niệm đều có thể tính tay.

12.1Bài toán tối ưu có ràng buộc#

Định nghĩa 12.1 (Dạng chuẩn)

Bài toán tối ưu có ràng buộc ở dạng chuẩn là

$$\begin{aligned} \min_x \quad & f_0(x) \\ \text{với} \quad & f_i(x) \le 0, \quad i = 1, \dots, m, \\ & h_j(x) = 0, \quad j = 1, \dots, p. \end{aligned}$$

Điểm thoả mọi ràng buộc gọi là điểm chấp nhận được. Giá trị tối ưu ký hiệu là $p^*$. Bài toán gọi là bài toán lồi nếu $f_0, f_1, \dots, f_m$ là hàm lồi và mọi $h_j$ là hàm affine.

Ràng buộc đẳng thức phải là affine, không chỉ lồi, vì tập $\{x : h(x) = 0\}$ với $h$ lồi nhưng không affine thường không lồi. Chẳng hạn $h(x) = \|x\|^2 - 1$ lồi, nhưng $\{x : \|x\|^2 = 1\}$ là mặt cầu, không phải tập lồi.

Ví dụ 12.1 (Ví dụ xuyên suốt chương)

Tìm $\min_x x^2$ với ràng buộc $x \ge 1$. Viết ở dạng chuẩn: $f_0(x) = x^2$, $f_1(x) = 1 - x \le 0$. Nghiệm hiển nhiên là $x^* = 1$ với $p^* = 1$: không có ràng buộc thì cực tiểu ở $x = 0$, nhưng điểm này không chấp nhận được, nên nghiệm nằm ở biên của miền ràng buộc.

12.2Hàm Lagrange và hàm đối ngẫu#

Ý tưởng của phương pháp Lagrange là thay việc cấm vi phạm ràng buộc bằng việc tính giá cho mỗi đơn vị vi phạm. Ta gắn cho mỗi ràng buộc bất đẳng thức một giá $\alpha_i \ge 0$ và cho mỗi ràng buộc đẳng thức một giá $\nu_j$.

Định nghĩa 12.2 (Hàm Lagrange, hàm đối ngẫu)

Hàm Lagrange của bài toán ở Định nghĩa 12.1 là

$$\mathcal{L}(x, \alpha, \nu) = f_0(x) + \sum_{i=1}^{m}\alpha_i f_i(x) + \sum_{j=1}^{p}\nu_j h_j(x),$$

với các nhân tử Lagrange $\alpha_i \ge 0$ và $\nu_j \in \mathbb{R}$. Hàm đối ngẫu là cực tiểu của hàm Lagrange theo $x$:

$$g(\alpha, \nu) = \inf_x \mathcal{L}(x, \alpha, \nu).$$

Điều kiện $\alpha_i \ge 0$ là bắt buộc: khi ràng buộc bị vi phạm, tức $f_i(x) > 0$, số hạng $\alpha_i f_i(x)$ phải làm tăng giá trị hàm, nghĩa là một khoản phạt.

Hàm đối ngẫu $g$ luôn là hàm lõm theo $(\alpha, \nu)$, kể cả khi bài toán gốc không lồi. Lý do là với mỗi $x$ cố định, $\mathcal{L}$ là hàm affine theo $(\alpha, \nu)$, và cận dưới đúng (infimum) của một họ hàm affine luôn là hàm lõm. Nhờ vậy bài toán cực đại $g$ luôn là một bài toán tối ưu lồi, dù bài toán gốc khó tới đâu.

Ví dụ 12.2

Với Ví dụ 12.1, $\mathcal{L}(x, \alpha) = x^2 + \alpha(1 - x)$. Cực tiểu theo $x$: đạo hàm $2x - \alpha = 0$ cho $x = \alpha/2$. Thay vào:

$$g(\alpha) = \frac{\alpha^2}{4} + \alpha\Big(1 - \frac{\alpha}{2}\Big) = \alpha - \frac{\alpha^2}{4}, \qquad \alpha \ge 0.$$

Đây là một parabol úp xuống, đúng là hàm lõm.

12.3Đối ngẫu yếu và đối ngẫu mạnh#

Định lý 12.1 (Đối ngẫu yếu)

Với mọi $\alpha \ge 0$ và mọi $\nu$: $g(\alpha, \nu) \le p^*$.

Chứng minh

Lấy $x$ bất kỳ chấp nhận được. Vì $f_i(x) \le 0$, $\alpha_i \ge 0$ và $h_j(x) = 0$, ta có $\mathcal{L}(x, \alpha, \nu) \le f_0(x)$. Do đó $g(\alpha, \nu) \le \mathcal{L}(x, \alpha, \nu) \le f_0(x)$. Lấy cận dưới đúng theo mọi $x$ chấp nhận được, vế phải trở thành $p^*$.

Mỗi giá trị của hàm đối ngẫu là một chặn dưới của giá trị tối ưu. Với ví dụ xuyên suốt, $g(0) = 0$, $g(1) = 0{,}75$, $g(3) = 0{,}75$ và $g(4) = 0$, đều không vượt quá $p^* = 1$. Bài toán đối ngẫu là tìm chặn dưới tốt nhất:

$$d^{*} = \max_{\alpha \ge 0,\, \nu} g(\alpha, \nu) \;\le\; p^{*}.$$

Hiệu $p^* - d^* \ge 0$ gọi là khe đối ngẫu. Khi khe bằng 0 ta có đối ngẫu mạnh, và giải bài toán đối ngẫu cho đúng giá trị tối ưu của bài toán gốc.

Định lý 12.2 (Điều kiện Slater)

Nếu bài toán là lồi và tồn tại một điểm chấp nhận được thoả mọi ràng buộc bất đẳng thức một cách chặt, $f_i(x) < 0$ với mọi $i$, thì đối ngẫu mạnh xảy ra.

Điều kiện Slater yêu cầu miền chấp nhận được có "phần trong", và hầu hết các bài toán lồi trong học máy thoả điều kiện này. Chẳng hạn, với SVM lề cứng trên dữ liệu tách được, nhân một siêu phẳng tách đúng với một hệ số đủ lớn cho một điểm thoả mọi ràng buộc một cách chặt.

Ví dụ 12.3

Tiếp tục Ví dụ 12.2: $g(\alpha) = \alpha - \alpha^2/4$ đạt cực đại tại $\alpha^* = 2$, với $d^* = g(2) = 1$. Vậy $d^* = p^* = 1$ và khe đối ngẫu bằng 0. Điều kiện Slater thoả vì điểm $x = 2$ có $f_1(2) = -1 < 0$.

Có thể hiểu vì sao giá tốt nhất là 2. Với giá $\alpha$, cực tiểu của hàm Lagrange theo $x$ là $x = \alpha/2$. Giá quá thấp thì vi phạm ràng buộc vẫn có lời: với $\alpha = 1$, cực tiểu là $x = 0{,}5$, nằm ngoài miền $x \ge 1$. Giá quá cao thì ràng buộc bị thoả thừa: với $\alpha = 3$, cực tiểu là $x = 1{,}5$. Ở $\alpha = 2$, cực tiểu rơi đúng vào $x = 1$, điểm biên của ràng buộc, và chặn dưới chạm giá trị tối ưu.

12.4Điều kiện KKT#

Định lý 12.3 (Điều kiện Karush–Kuhn–Tucker)

Xét bài toán lồi có các hàm khả vi và thoả điều kiện Slater. Điểm $x^*$ là nghiệm tối ưu khi và chỉ khi tồn tại $(\alpha^*, \nu^*)$ sao cho bốn nhóm điều kiện sau thoả:

Điều kiện bù là điều kiện quan trọng nhất cho Chương 13. Nó nói rằng với mỗi ràng buộc, một trong hai điều phải xảy ra: hoặc ràng buộc chặt tại nghiệm, $f_i(x^*) = 0$, tức nghiệm nằm đúng trên biên của ràng buộc đó, hoặc giá của nó bằng 0, $\alpha_i^* = 0$. Một ràng buộc không chặt thì không ảnh hưởng tới nghiệm: bỏ nó đi, nghiệm không đổi.

Ví dụ 12.4

Với Ví dụ 12.1: điều kiện dừng $2x^* - \alpha^* = 0$, điều kiện bù $\alpha^*(1 - x^*) = 0$. Nếu $\alpha^* = 0$ thì $x^* = 0$, vi phạm ràng buộc $x \ge 1$. Vậy $\alpha^* > 0$, kéo theo $x^* = 1$ và $\alpha^* = 2$, khớp với Ví dụ 12.3. Nếu đổi ràng buộc thành $x \ge -1$, nghiệm là $x^* = 0$, ràng buộc không chặt ($0 > -1$), và điều kiện bù cho $\alpha^* = 0$: ràng buộc này không có vai trò gì.

Nhân tử Lagrange còn có ý nghĩa giá bóng (shadow price): nó đo giá trị tối ưu thay đổi bao nhiêu khi ràng buộc được nới lỏng. Nếu ràng buộc $f_i(x) \le 0$ được nới thành $f_i(x) \le u$, thì $\partial p^*/\partial u = -\alpha_i^*$. Trong ví dụ, nới $1 - x \le u$ cho $x \ge 1 - u$ và $p^*(u) = (1-u)^2$, có đạo hàm tại $u = 0$ bằng $-2 = -\alpha^*$. Ràng buộc có giá lớn là ràng buộc đang "cản" nghiệm nhiều nhất.

Áp dụng vào SVM ở chương sau, điều kiện bù có nghĩa là chỉ những điểm dữ liệu nằm đúng trên lề mới có nhân tử $\alpha_i > 0$ và mới ảnh hưởng tới nghiệm. Đó là định nghĩa của vector hỗ trợ, và nó là hệ quả của điều kiện KKT chứ không phải một lựa chọn thiết kế.

12.5Ý nghĩa của bài toán đối ngẫu#

Có ba lý do để giải bài toán đối ngẫu thay vì bài toán gốc. Lý do đầu tiên là kích thước: bài toán gốc của SVM có $d$ biến là các trọng số, còn bài toán đối ngẫu có $n$ biến, mỗi điểm dữ liệu một nhân tử, nên khi $d$ lớn hơn $n$ nhiều thì bài toán đối ngẫu nhỏ hơn. Lý do thứ hai là chặn dưới: với bất kỳ $\alpha \ge 0$ nào, $g(\alpha)$ là chặn dưới của $p^*$, nên hiệu $f_0(x) - g(\alpha)$ giữa một điểm chấp nhận được và một điểm đối ngẫu cho biết nghiệm hiện tại cách tối ưu tối đa bao xa, và nhiều thuật toán dùng khe này làm tiêu chí dừng. Với ví dụ xuyên suốt, điểm chấp nhận được $x = 1{,}2$ có $f_0 = 1{,}44$ và $g(1) = 0{,}75$, nên $x = 1{,}2$ cách tối ưu không quá 0,69 mà không cần biết $p^*$; thực tế nó cách 0,44. Lý do thứ ba, quan trọng nhất, là cấu trúc: bài toán đối ngẫu của SVM chỉ phụ thuộc vào dữ liệu qua các tích vô hướng $x_i^\top x_j$. Nhận xét này dẫn thẳng tới kernel, vì thay tích vô hướng bằng một hàm kernel là SVM làm việc được trong không gian đặc trưng phi tuyến. Ở dạng bài toán gốc, cấu trúc này không lộ ra.

12.6Tóm tắt#

Phương pháp Lagrange thay ràng buộc bằng khoản phạt có giá $\alpha_i \ge 0$, và hàm đối ngẫu, cực tiểu của hàm Lagrange theo $x$, luôn lõm. Mỗi giá trị của hàm đối ngẫu là một chặn dưới của giá trị tối ưu, và với bài toán lồi thoả điều kiện Slater, chặn dưới tốt nhất đúng bằng giá trị tối ưu. Điều kiện KKT đặc trưng cho nghiệm tối ưu, trong đó điều kiện bù nói rằng ràng buộc nào không chặt thì có giá bằng 0 và không ảnh hưởng tới nghiệm. Nhân tử Lagrange là giá bóng, đo giá trị tối ưu thay đổi bao nhiêu khi nới ràng buộc. Ví dụ $\min x^2$ với $x \ge 1$ cho $x^* = 1$, $\alpha^* = 2$ và khe đối ngẫu bằng 0; $\alpha^* = 2$ là giá làm cực tiểu không ràng buộc của hàm Lagrange rơi đúng vào biên của ràng buộc.

Chương 13 áp dụng toàn bộ bộ công cụ này cho SVM: bài toán gốc tìm siêu phẳng có lề lớn nhất, điều kiện bù chỉ ra vector hỗ trợ, và bài toán đối ngẫu dẫn tới kernel.