Bài này có khá nhiều khái niệm mới, mong bạn đọc thông cảm khi tôi sử dụng các khái niệm này ở cả tiếng Anh và tiếng Việt.
Đang xem: Convexity là gì
Bài chủ yếu nói về toán, nếu bạn đọc không hiểu ngay cũng không sao, ngày đầu tôi làm quen với những khái niệm này cũng không thể hấp thụ được ngay. Làm nhiều, đọc nhiều rồi sẽ ngấm dần.
Bạn đọc có thể xem bản pdf tại đây.
1. Giới thiệu 2. Convex sets 2.1. Định nghĩa 2.2. Ví dụ 2.2.1. Hyperplanes và halfspaces 2.2.2. Norm balls 2.3. Giao của các tập lồi là một tập lồi. 2.4. Convex combination và Convex hulls 3. Convex functions 3.1. Định nghĩa 3.2. Các tính chất cơ bản 3.3. Ví dụ 3.3.1. Các hàm một biến 3.3.3. Affine functions 3.3.3. Quadratic forms 3.3.4. Norms 3.4. (alpha-) sublevel sets 3.5. Kiểm tra tính chất lồi dựa vào đạo hàm. 3.5.1. First-order condition 3.5.2. Second-order condition 4. Tóm tắt 5. Tài liệu tham khảo
1. Giới thiệu
Từ đầu đến giờ, chúng ta đã làm quen với rất nhiều bài toán tối ưu. Học Machine Learning là phải học Toán Tối Ưu, và để hiểu hơn về Toán Tối Ưu, với tôi cách tốt nhất là tìm hiểu các thuật toán Machine Learning. Cho tới lúc này, những bài toán tối ưu các bạn đã nhìn thấy trong blog đều là các bài toán tối ưu không ràng buộc (unconstrained optimization problems), tức tối ưu hàm mất mát mà không có điều kiện ràng buộc (constraints) nào về nghiệm cả.
Không chỉ trong Machine Learning, trên thực tế các bài toán tối ưu thường có rất nhiều ràng buộc khác nhau. Ví dụ:
Tôi muốn thuê một ngôi nhà cách trung tâm Hà Nội không quá 5km với giá càng thấp càng tốt. Trong bài toán này, giá thuê nhà chính là hàm mất mát (loss function, đôi khi người ta cũng dùng cost function để chỉ hàm số cần tối ưu), điều kiện khoảng cách không quá 5km chính là ràng buộc (constraint).
Quay lại bài toán dự đoán giá nhà theo Linear Regression, giá nhà là một hàm tuyến tính của diện tích, số phòng ngủ và khoảng cách tới trung tâm. Rõ ràng, khi làm bài toán này, ta dự đoán rằng giá nhà tăng theo diện tích và số phòng ngủ, giảm theo khoảng cách. Vậy nên một nghiệm được gọi là có lý một chút nếu hệ số tương ứng với diện tích và số phòng ngủ là dương, hệ số tương ứng với khoảng cách là âm. Để tránh các nghiệm ngoại lai không mong muốn, khi giải bài toán tối ưu, ta nên cho thêm các điều kiện ràng buộc này.
Trong Tối Ưu, một bài toán có ràng buộc thường được viết dưới dạng:
< egin mathbf^* &=& argmin_} f_0(mathbf) ext~ && f_i(mathbf) leq 0, ~~ i = 1, 2, dots, m && h_j(mathbf) = 0, ~~ j = 1, 2, dots, p end >
Trong đó, vector (mathbf =
ightarrow mathbb) được gọi là hàm mục tiêu (objective function, các hàm mục tiêu trong Machine Learning thường được gọi là hàm mất mát). Các hàm số (f_i, h_j: mathbb^n
ightarrow mathbb, i = 1, 2, dots, m; j = 1, 2, dots, p) được gọi là các hàm ràng buộc (hoặc đơn giản là ràng buộc – constraints). Tập hợp các điểm (mathbf) thỏa mãn các ràng buộc được gọi là feasible set. Mỗi điểm trong feasible set được gọi là feasible point, các điểm không trong feasible set được gọi là infeasible points.
Chú ý:
Nếu bài toán là tìm giá trị lớn nhất thay vì nhỏ nhất, ta chỉ cần đổi dấu của (f_0(mathbf)).
Xem thêm: Súp Cà Rốt Trắng ( Parsnip Là Gì, Nghĩa Của Từ Parsnip, Parsnip Là Gì, Nghĩa Của Từ Parsnip
Nếu ràng buộc là lớn hơn hoặc bằng, tức (f_i(mathbf) geq b_i), ta chỉ cần đổi dấu của ràng buộc là sẽ có điều kiện nhỏ hơn hoặc bằng (-f_i(mathbf) leq -b_i).
Các ràng buộc cũng có thể là lớn hơn hoặc nhỏ hơn.
Nếu ràng buộc là bằng nhau, tức (h_j(mathbf) = 0), ta có thể viết nó dưới dạng hai bất đẳng thức (h_j(mathbf) leq 0) và (-h_j(mathbf) leq 0). Trong một vài tài liệu, người ta bỏ các phương trình ràng buộc (h_j(mathbf)= 0) đi.
Trong bài viết này, (mathbf, mathbf) được dùng chủ yếu để ký hiệu các biến số, không phải là dữ liệu như trong các bài trước. Biến tối ưu chính là biến được ghi dưới dấu (arg min). Khi viết một bài toán Tối Ưu, ta cần chỉ rõ biến nào cần được tối ưu, biến nào là cố định.
Các bài toán tối ưu, nhìn chung không có cách giải tổng quát, thậm chí có những bài chưa có lời giải. Hầu hết các phương pháp tìm nghiệm không chứng minh được nghiệm tìm được có phải là global optimal hay không, tức đúng là điểm làm cho hàm số đạt giá trị nhỏ nhất hay lớn nhất hay không. Thay vào đó, nghiệm thường là các local optimal, tức các điểm cực trị.
Để bắt đầu học Tối Ưu, chúng ta cần học một mảng rất quan trọng trong đó, có tên là Tối Ưu Lồi (convex optimization), trong đó hàm mục tiêu là một hàm lồi (convex function), feasible set là một tập lồi (convex set). Những tính chất đặc biệt về local optimal và global optimal của một hàm lồi khiến Tối Ưu Lồi trở nên cực kỳ quan trọng. Trong bài viết này, tôi sẽ giới thiệu tới các bạn các định nghĩa và tính chất cơ bản của tập lồi và hàm lồi. Bài toán tối ưu lồi (convex optimization problems) sẽ được đề cập trong bài tiếp theo.
2. Convex sets
2.1. Định nghĩa
Khái niệm về convex sets có lẽ không xa lạ với các bạn học sinh Việt Nam khi chúng ta đã nghe về đa giác lồi. Lồi, hiểu đơn giản là phình ra ngoài, hoặc nhô ra ngoài. Trong toán học, bằng phẳng cũng được coi là lồi.
Xem thêm: Xem Phim Cô Gái Đến Từ Hôm Qua Phim Chiếu Rạp, Bộ Phim Cô Gái Đến Từ Hôm Qua Chính
Định nghĩa 1: Một tập hợp được gọi là tập lồi (convex set) nếu đoạn thẳng nối hai điểm bất kỳ trong tập hợp hợp đó nằm trọn vẹn trong tập hợp đó.
Một vài ví dụ về convex sets:
