Bỏ qua

Tối ưu hóa

Tối ưu hóa là cốt lõi toán học của việc huấn luyện mô hình, tìm các tham số làm tối thiểu hàm mất mát. Tài liệu này bao quát các điểm tới hạn, tính lồi, hạ gradient, phương pháp Newton, tối ưu hóa có ràng buộc với nhân tử Lagrange, và các thuật toán tối ưu (SGD, Adam) thúc đẩy học sâu hiện đại.

  • Huấn luyện mạng nơ-ron, khớp một đường hồi quy, điều chỉnh siêu tham số: ở trung tâm của hầu hết mọi thuật toán học máy là một bài toán tối ưu hóa.

  • Ta có một hàm nào đó (mất mát, chi phí, mục tiêu) và ta muốn tìm các đầu vào làm cho nó nhỏ nhất (hoặc lớn nhất) có thể.

  • Trước khi tối ưu hóa, ta cần hiểu không điểm (zeros) hay nghiệm của hàm. Một không điểm của \(f(x)\) là một giá trị \(x\) mà tại đó \(f(x) = 0\). Về mặt đồ thị, đó là các giao điểm trục hoành.

  • Ví dụ, \(f(x) = x^2 - 3x + 2 = (x-1)(x-2)\) có các không điểm tại \(x = 1\) và \(x = 2\). Giữa các không điểm, hàm âm (\(f(1.5) = -0.25\)); bên ngoài các không điểm, hàm dương. Các không điểm chia trục số thành các vùng nơi hàm có dấu không đổi.

  • Bội số (multiplicity) của một không điểm là số lần nhân tử tương ứng xuất hiện.

  • Tại một không điểm đơn (bội 1), đồ thị cắt trục x. Tại một không điểm kép (bội 2), đồ thị chạm trục x nhưng bật ngược lại mà không cắt qua, trông "bằng phẳng" tại điểm đó.

  • Việc tìm không điểm quan trọng vì các không điểm của đạo hàm \(f'(x)\) là các điểm tới hạn (critical points) của \(f(x)\), các ứng cử viên cho cực đại và cực tiểu.

  • Tại một cực đại hoặc cực tiểu, đường tiếp tuyến bằng phẳng (độ dốc = 0), nên \(f'(x) = 0\).

Điểm tới hạn: nơi đạo hàm bằng không, hàm có đỉnh, đáy, hoặc yên ngựa

  • Nhưng không phải điểm tới hạn nào cũng là cực đại hay cực tiểu. Một điểm có \(f'(x) = 0\) cũng có thể là điểm uốn (inflection point) (như \(x = 0\) với \(f(x) = x^3\)), nơi hàm phẳng đi trong chốc lát nhưng không đổi hướng.

  • Kiểm tra đạo hàm bậc hai (second derivative test) giải quyết điều này. Tại một điểm tới hạn \(x = c\) với \(f'(c) = 0\):

    • Nếu \(f''(c) > 0\): đường cong lõm lên (như một cái bát), nên \(c\) là cực tiểu địa phương.
    • Nếu \(f''(c) < 0\): đường cong lõm xuống (như một quả đồi), nên \(c\) là cực đại địa phương.
    • Nếu \(f''(c) = 0\): kiểm tra không kết luận được; cần đạo hàm bậc cao hơn hoặc các phương pháp khác.

  • Ví dụ, \(f(x) = x^3 - 3x\). Đạo hàm là \(f'(x) = 3x^2 - 3 = 3(x-1)(x+1)\), nên các điểm tới hạn là \(x = -1\) và \(x = 1\). Đạo hàm bậc hai là \(f''(x) = 6x\). Tại \(x = -1\): \(f''(-1) = -6 < 0\) (cực đại địa phương). Tại \(x = 1\): \(f''(1) = 6 > 0\) (cực tiểu địa phương).

  • Một hàm được gọi là lồi (convex) nếu đoạn thẳng giữa hai điểm bất kỳ trên đồ thị của nó nằm phía trên (hoặc nằm trên) đồ thị. Hãy nghĩ về nó như một hình dạng cái bát, cong lên trên ở mọi nơi. Về mặt toán học, \(f\) là lồi nếu \(f''(x) \geq 0\) với mọi \(x\).

Hàm lồi có một cực tiểu toàn cục duy nhất; hàm không lồi có thể có nhiều cực tiểu địa phương

  • Tính lồi rất mạnh mẽ vì các hàm lồi có một tính chất đáng chú ý: mọi cực tiểu địa phương đều đồng thời là cực tiểu toàn cục (global minimum). Không có các thung lũng địa phương lừa đảo để mắc kẹt. Nếu bạn thả một quả bóng vào một cái bát lồi, nó sẽ luôn chạm đến đáy.

  • Một hàm được gọi là lõm (concave) (cong xuống dưới) nếu \(-f\) là lồi. Các điểm nơi hàm chuyển tiếp giữa lõm và lồi là các điểm uốn, xảy ra khi \(f''(x) = 0\).

  • Phương pháp Newton tìm không điểm của hàm (và mở rộng, các điểm tới hạn của đạo hàm của chúng) sử dụng các đường tiếp tuyến. Bắt đầu từ một dự đoán ban đầu \(x_0\), nó tinh chỉnh lặp đi lặp lại:

\[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\]

Phương pháp Newton: đi theo đường tiếp tuyến để tìm xấp xỉ tốt hơn của nghiệm

  • Ý tưởng: tại \(x_n\), vẽ đường tiếp tuyến và tìm nơi nó cắt trục x. Điểm cắt đó trở thành \(x_{n+1}\). Với các hàm cư xử tốt và một điểm bắt đầu tốt, phương pháp Newton hội tụ rất nhanh (bậc hai, nghĩa là số chữ số đúng khoảng gấp đôi mỗi bước).

  • Ví dụ, để tìm \(\sqrt{5}\) (một không điểm của \(f(x) = x^2 - 5\)): \(f'(x) = 2x\), nên \(x_{n+1} = x_n - \frac{x_n^2 - 5}{2x_n}\). Bắt đầu với \(x_0 = 2\): \(x_1 = 2.25\), \(x_2 = 2.2361\ldots\), đã chính xác đến bốn chữ số thập phân.

  • Phương pháp Newton có thể thất bại nếu dự đoán ban đầu ở xa nghiệm, nếu \(f'(x) = 0\) gần nghiệm, hoặc nếu hàm có điểm uốn ở gần. Nó cũng yêu cầu tính đạo hàm, có thể tốn kém.

  • Đối với tối ưu hóa (tìm cực tiểu thay vì không điểm), ta áp dụng phương pháp Newton cho \(f'(x) = 0\), cho ta cập nhật:

\[x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)}\]

  • Trong nhiều chiều, điều này trở thành \(\mathbf{x}_{n+1} = \mathbf{x}_n - H^{-1} \nabla f(\mathbf{x}_n)\), với \(H\) là ma trận Hessian. Đây là xấp xỉ Taylor bậc hai từ tài liệu trước được áp dụng: xấp xỉ hàm là một bậc hai, nhảy đến cực tiểu của bậc hai đó, lặp lại.

  • Nhân tử Lagrange (Lagrange multipliers) giải quyết tối ưu hóa có ràng buộc (constrained optimisation): tìm cực trị của \(f(x, y)\) với một ràng buộc \(g(x, y) = c\). Thay vì tìm kiếm toàn bộ \(\mathbb{R}^n\), ta bị giới hạn trên tập nơi ràng buộc có hiệu lực (một đường cong hoặc mặt cong).

  • Trực giác chính là hình học: tại điểm tối ưu có ràng buộc, gradient của \(f\) phải song song với gradient của \(g\). Nếu chúng không song song, ta có thể di chuyển dọc theo ràng buộc theo một hướng vẫn cải thiện \(f\), nên ta sẽ chưa ở điểm tối ưu.

  • Ta đưa vào một biến mới \(\lambda\) (nhân tử Lagrange) và định nghĩa Lagrangian:

\[\mathcal{L}(x, y, \lambda) = f(x, y) - \lambda(g(x, y) - c)\]
  • Đặt tất cả các đạo hàm riêng bằng không cho một hệ phương trình mà nghiệm của nó là các điểm tối ưu có ràng buộc:
\[\frac{\partial \mathcal{L}}{\partial x} = 0, \quad \frac{\partial \mathcal{L}}{\partial y} = 0, \quad \frac{\partial \mathcal{L}}{\partial \lambda} = 0\]

Nhân tử Lagrange: tại điểm tối ưu, gradient của f và g song song

  • Ví dụ, cực đại hóa \(f(x,y) = x^2 y\) với ràng buộc \(x^2 + y^2 = 1\). Lagrangian là \(\mathcal{L} = x^2 y - \lambda(x^2 + y^2 - 1)\). Lấy đạo hàm riêng:
\[2xy - 2\lambda x = 0, \quad x^2 - 2\lambda y = 0, \quad x^2 + y^2 = 1\]

  • Từ phương trình đầu (giả sử \(x \neq 0\)): \(\lambda = y\). Thế vào phương trình thứ hai: \(x^2 = 2y^2\). Kết hợp với ràng buộc: \(2y^2 + y^2 = 1\), nên \(y = \frac{1}{\sqrt{3}}\). Giá trị cực đại là \(f = \frac{2}{3\sqrt{3}}\).

  • Với các ràng buộc bất đẳng thức (\(g(x,y) \leq c\) thay vì \(= c\)), các điều kiện Karush-Kuhn-Tucker (KKT) khái quát hóa nhân tử Lagrange. Ràng buộc hoặc là đang tác động (binding, được xử lý như đẳng thức) hoặc không tác động (lời giải nằm trong phần bên trong và ràng buộc không liên quan).

  • Trong thực tế, ta hiếm khi tối ưu hóa bằng tay. Dưới đây là các họ thuật toán chính:

    • Phương pháp bậc nhất (chỉ sử dụng gradient): hạ gradient, hạ gradient ngẫu nhiên (SGD), Adam. Chúng rẻ mỗi bước nhưng có thể hội tụ chậm, đặc biệt trên các bài toán điều kiện hóa kém.

    • Phương pháp bậc hai (sử dụng gradient và Hessian): phương pháp Newton hội tụ nhanh nhưng tính và nghịch đảo ma trận Hessian rất đắt (\(O(n^3)\) với \(n\) tham số). Các phương pháp gần-Newton (quasi-Newton) (như BFGS và L-BFGS) xấp xỉ ma trận Hessian chỉ bằng thông tin gradient, đạt được hội tụ nhanh hơn phương pháp bậc nhất mà không phải trả toàn bộ chi phí của phương pháp bậc hai.

    • Gradient liên hợp (conjugate gradient): hiệu quả cho các hệ thưa lớn, chỉ dùng tích ma trận-vector thay vì lưu toàn bộ ma trận Hessian.

    • Gauss-Newton và Levenberg-Marquardt: chuyên biệt cho các bài toán bình phương tối thiểu (phổ biến trong hồi quy), xấp xỉ Hessian thông qua ma trận Jacobi.

    • Hạ gradient tự nhiên (natural gradient descent): tính đến hình học của không gian tham số sử dụng ma trận thông tin Fisher, có thể hiệu quả hơn cho các mô hình xác suất.

  • Việc chọn thuật toán tối ưu phụ thuộc vào bài toán. Đối với học sâu, các phương pháp bậc nhất (đặc biệt là Adam) chiếm ưu thế vì số lượng tham số là rất lớn (hàng triệu đến hàng tỷ), khiến việc tính Hessian trở nên bất khả thi. Đối với các bài toán nhỏ hơn với mục tiêu trơn, các phương pháp bậc hai có thể nhanh hơn đáng kể.

Bài tập lập trình (dùng CoLab hoặc notebook)

  1. Cài đặt phương pháp Newton để tìm \(\sqrt{7}\) (một không điểm của \(f(x) = x^2 - 7\)). Quan sát sự hội tụ nhanh chóng. 

    import jax.numpy as jnp

f = lambda x: x**2 - 7
df = lambda x: 2*x

x = 3.0  # initial guess
for i in range(6):
    x = x - f(x) / df(x)
    print(f"step {i+1}: x = {x:.10f}  (error: {abs(x - jnp.sqrt(7.0)):.2e})")

  2. Dùng hạ gradient để tối thiểu hóa \(f(x, y) = (x - 3)^2 + (y + 1)^2\). Giá trị tối thiểu là tại \((3, -1)\). Thử nghiệm với các tốc độ học khác nhau. 

    import jax
import jax.numpy as jnp

def f(params):
    x, y = params
    return (x - 3)**2 + (y + 1)**2

grad_f = jax.grad(f)
params = jnp.array([0.0, 0.0])
lr = 0.1

for i in range(20):
    g = grad_f(params)
    params = params - lr * g
    if i % 5 == 0 or i == 19:
        print(f"step {i:2d}: ({params[0]:.4f}, {params[1]:.4f})  loss={f(params):.6f}")

  3. Giải một bài toán tối ưu hóa có ràng buộc bằng phương pháp số. Cực đại hóa \(f(x,y) = xy\) với ràng buộc \(x + y = 10\) bằng cách tham số hóa \(y = 10 - x\) và tìm cực trị của hàm một biến. 

    import jax
import jax.numpy as jnp

# Substitute constraint: y = 10 - x, so f = x(10 - x) = 10x - x²
f = lambda x: x * (10 - x)
df = jax.grad(f)

# Gradient ascent (we want maximum, so add gradient)
x = 1.0
lr = 0.1
for i in range(20):
    x = x + lr * df(x)
print(f"x={x:.4f}, y={10-x:.4f}, f={f(x):.4f}")  # should be x=5, y=5, f=25