Khi tìm hiểu về Support Vector Machines và Kernels, chúng ta đã liên tục dựa vào việc sử dụng tối ưu lồi để đảm bảo rằng các nghiệm tồn tại và có thể tính toán được. Tuy nhiên, có nhiều trường hợp mà giả định về hàm mục tiêu và các ràng buộc là lồi (hoặc tựa-lồi/quasi convex) không còn đúng/ hợp lệ, và vì vậy các phương pháp trên các hàm lồi mà chúng ta đã phát triển không thể được áp dụng.
Để giải quyết những vấn đề này, chúng ta phải phát triển một lý thuyết tối ưu cho một siêu lớp (superclass) của các hàm lồi, được gọi là hàm DC - Difference of Convex (Hiệu của các hàm lồi). Bây giờ chúng ta sẽ bắt đầu định nghĩa các hàm như vậy.
Trong phần còn lại của bài giảng này, chúng ta sẽ thảo luận về các giải pháp cho bài toán sau đây - bài toán Quy Hoạch DC (DCP): $$ \begin{align} \min_{x \in \mathbb{R}^n} & \quad f_0(x) \ \quad\text{s.t.} & \quad f_i(x) \leq 0, \quad i = 1, \ldots, m. \end{align} $$ trong đó $f_i: \mathbb{R}^n \rightarrow \mathbb{R}$ là một hàm DC khả vi đối với $i = 0, \ldots, m$.
Trước khi chúng ta tiếp tục thảo luận về nghiệm cho Bài toán (1), ta thảo luận về một số trực quan về hàm DC. Nhắc lại rằng một hàm $f: \mathbb{R}^n \rightarrow \mathbb{R}$ là lồi nếu với mọi $x_1, x_2 \in \mathbb{R}^n$ và mọi $\alpha \in [0, 1]$, thì $f(\alpha x_1 + (1-\alpha)x_2) \leq \alpha f(x_1) + (1-\alpha)f(x_2)$.
Đặc biệt, nếu $f$ là một hàm khả vi hai lần, thì nó là lồi khi và chỉ khi ma trận Hessian của nó là nửa xác định dương. Để có cảm giác về những gì hàm DC có thể trông như thế nào, chúng ta sẽ xem xét một số hàm lồi phổ biến và các hàm DC mà chúng có thể tạo thành.
Ví dụ 1.2. Xem xét các hàm lồi $f_1(x) = \frac{1}{x}$ và $f_2(x) = x^2$.
Ví dụ 1.3. Xem xét các hàm lồi $f_1(x) = |x|$ và $f_2(x) = -\log(x)$.
Lưu ý rằng trong khi trong các ví dụ này, cực tiểu dễ tìm bằng cách quan sát trong các hàm lồi, thì việc này ít rõ ràng hơn trong hàm DC kết quả. Rõ ràng, có các hàm DC như một phần của bài toán tối ưu hóa thêm một mức độ phức tạp vào bài toán mà chúng ta không gặp phải trong các vấn đề với các hàm lồi. May mắn thay, như ta sẽ thấy sớm, sự phức tạp này không phải là không thể vượt qua.
Tiếp theo chúng ta sẽ chứng minh rằng lớp hàm DC lớn như thế nào.
Trước khi chúng ta có thể thảo luận về các điều kiện tối ưu toàn cục và địa phương trong bài toán Quy hoạch DC chính tắc, chúng ta cần giới thiệu một số khái niệm liên quan đến tính đối ngẫu trong DCP, và phát triển một số trực giác về những gì điều này mang lại cho chúng ta. Để bắt đầu với điều này, chúng ta giới thiệu các hàm liên hợp và sử dụng chúng để chứng minh mối quan hệ giữa DCP và bài toán đối ngẫu của nó.
Để hiểu tại sao các hàm liên hợp lại quan trọng, chúng ta cần thêm một định nghĩa nữa.
Lưu ý rằng $g$ là lồi khi và chỉ khi $\text{epi}(g)$ là một tập lồi.
Đã định nghĩa epigraph, chúng ta giờ đây có thể đưa ra một diễn giải hình học của hàm liên hợp: Hàm liên hợp $g^*$ ‘bao quanh (encloses)’ bao lồi của $\text{epi}(g)$ với các siêu phẳng hỗ trợ (supporting hyperplanes) của $g$. Đặc biệt, chúng ta có thể thấy rằng khi $f$ là khả vi, $$\frac{df}{dx} = \text{argsup}\{x^T y - g^*(y) : y \in \mathbb{R}^n\} = y(x)$$
Tức là, $y$ là một biến đối ngẫu cho $x$, và do đó có thể được diễn giải (xấp xỉ) như gradient (hoặc độ dốc trong $\mathbb{R}^2$) của $f$ tại $x$. Đây phải là một kết quả quen thuộc từ bài giảng về phân tích lồi.
Chúng ta cung cấp định lý này mà không cần chứng minh, và bỏ qua thảo luận thêm về tính nửa liên tục dưới, nhưng chúng ta có thể an toàn giả định rằng các hàm mà chúng ta sẽ xử lý đều thỏa mãn điều này. Lưu ý rằng điều kiện này ngụ ý rằng $g^{**} = g$, tức là, liên hợp của liên hợp của $g$ là $g$, nghĩa là định nghĩa của $g$ và $g^*$ là đối xứng. (Điều này có ý nghĩa gì đối với việc cực tiểu hóa $g$?)
Bây giờ chúng ta chứng minh mối quan hệ giữa DCP và bài toán đối ngẫu của nó. Đầu tiên lưu ý dạng của hàm liên hợp $f^*$ cho $f \equiv g - h$: $$(f(x))^* = ((g - h)(x))^* = \sup{x^T y - (g - h)(x) : x \in \mathbb{R}^n} = h^*(y) - g^*(y)$$
Gọi $\alpha$ là giá trị tối ưu cho DCP. $$ \begin{align*} \alpha &= \inf{g(x) - h(x) : x \in X} \\ &= \inf{g(x) - \sup{x^T y - h^*(y) : y \in Y} : x \in X} \\ &= \inf{\inf{g(x) - x^T y + h^*(y) : x \in X} : y \in Y} \\ &= \inf{h^*(y) - g^*(y) : y \in Y} \end{align*} $$
Do đó, chúng ta có rằng giá trị tối ưu cho DCP là giống với giá trị tối ưu cho bài toán đối ngẫu của nó! Đó thực sự là sự đối xứng! Điều này có nghĩa là chúng ta có thể giải quyết bài toán gốc hoặc bài toán đối ngẫu và thu được giải pháp cho cả hai - thuật toán mà chúng ta sẽ sử dụng để giải quyết DCP sẽ phụ thuộc rất nhiều vào sự kiện này.
$$\partial_{\varepsilon}g(x_0) = {y \in \mathbb{R}^n : g(x) - g(x_0) \geq (x - x_0)^T y - \varepsilon \quad \forall x \in \mathbb{R}^n}$$
Định nghĩa một vi phân (differential) của $g$ tại $x_0$ là $$\partial g(x_0) = \bigcap_{\varepsilon>0} \partial_{\varepsilon}g(x_0)$$
Với hai định nghĩa này, chúng ta có các điều kiện sau cho tính tối ưu toàn cục:
Cho $x^*$ là nghiệm tối ưu của bài toán Quy hoạch DC (gốc). Khi đó
$$\partial h(x^*) \subset \partial g(x^*)$$
Cho $y^*$ là nghiệm tối ưu của bài toán Quy hoạch DC đối ngẫu. Khi đó
$$\partial g^*(y^*) \subset \partial h^*(y^*)$$
$$ \alpha = \inf{g(x) - h(x) : x \in X} = \inf{h^*(y) - g^*(y) : y \in Y} $$
Khi đó nếu $\alpha$ là hữu hạn, chúng ta phải có $\text{dom } g \subset \text{dom } h$ và $\text{dom } h^* \subset \text{dom } g^*$ trong đó $\text{dom } g = {x \in \mathbb{R}^n : g(x) < \infty}$, miền của $g$. Tức là, $h$ (tương ứng, $g^*$) là hữu hạn bất cứ khi nào $g$ (tương ứng, $h^*$) là hữu hạn. Lưu ý rằng chúng ta yêu cầu phép bao hàm này bởi vì chúng ta đang cực tiểu hóa hàm mục tiêu, và do đó nếu tồn tại một $x \in \mathbb{R}^*$ sao cho $g(x) < \infty, h(x) = \infty$, thì $g(x) - h(x)$ sẽ được cực tiểu hóa tại $x$, cho một giá trị mục tiêu là $-\infty$. Lưu ý rằng phát biểu này không phải là một phát biểu nếu và chỉ nếu, vì chúng ta làm việc dưới quy ước rằng $\infty - \infty = \infty$.
Do đó, chúng ta có rằng nếu $x^*$ là tối ưu cho DCP gốc, thì $x^* \in \text{dom } g$, và theo tính đối ngẫu yếu,
$$g(x^*) - h(x^*) \leq h^*(y) - g^*(y), \quad \forall y \in \text{dom } h^*$$
và do đó (cho $x^* \in \text{dom } h$) nếu $x^* \in \partial h(x^*)$, thì
$$x^T y \geq h(x^*) + h^*(y) \geq g(x^*) + g^*(y)$$
trong đó bất đẳng thức đầu tiên là theo định nghĩa của $\partial h(x^*)$ và bất đẳng thức thứ hai xuất phát từ bất đẳng thức đối ngẫu yếu đã trình bày.
Chúng ta cũng có thể nghĩ về điều này theo các diễn giải của bài toán đối ngẫu. Chúng ta có rằng nếu $g, h$ là khả vi, và do đó $\partial h(x^*) = \emptyset \neq \partial g(x^*)$, thì $\partial h(x^*)$ chỉ là tập hợp các gradient của $h$ tại $x^*$, và theo sự bằng nhau của tối ưu gốc và đối ngẫu, nó là tập hợp các $y^*$ tối ưu hóa bài toán đối ngẫu. Do đó, điều kiện tối ưu này theo các dưới vi phân là tương tự như điều kiện mà chúng ta đã thảo luận về miền.
$$\bigcup{\partial h(x) : x \in \mathbf{P}} \subset \mathbf{D} \subset \text{dom } h^*$$
và
$$\bigcup{\partial g^*(y) : y \in \mathbf{D}} \subset \mathbf{P} \subset \text{dom } g$$
Lưu ý rằng định lý này ngụ ý rằng giải quyết DCP gốc ngụ ý giải quyết DCP đối ngẫu.
Chúng ta muốn xây dựng một thuật toán để tìm các nghiệm tối ưu toàn cục dựa trên các điều kiện đã thảo luận trong phần trước. Tuy nhiên, việc tìm một thuật toán làm việc này một cách hiệu quả trong trường hợp tổng quát là một vấn đề mở, và hầu hết các cách tiếp cận là tổ hợp, thay vì dựa trên tính lồi, và do đó phụ thuộc nhiều vào công thức của một vấn đề đã cho, và thường không hiệu quả. Do đó, chúng ta trình bày các điều kiện tối ưu địa phương, mà (không giống như các điều kiện tối ưu toàn cục) có thể được sử dụng để tạo ra một cách tiếp cận dựa trên tính lồi cho tối ưu hóa địa phương. Chúng ta trình bày các định lý này mà không chứng minh vì, mặc dù chúng rất quan trọng để giải các bài toán quy hoạch DC, nhưng chứng minh của chúng không thêm nhiều thông tin nữa. Do đó, chúng tôi giới thiệu việc nghiên cứu thêm đến Hurst và Thoai hoặc Tao và An.
Khi đó $x^*$ là một cực tiểu địa phương của $g - h$.
Như đã thảo luận trước đó, các điều kiện tối ưu toàn cục trong quy hoạch DC không mang lại các thuật toán tổng quát hiệu quả. Do đó, trong khi có một số kỹ thuật phổ biến - trong số đó, các thuật toán nhánh và cận và mặt cắt, chúng tôi bỏ qua việc thảo luận về chúng và thay vào đó tập trung vào cách tiếp cận dựa trên tính lồi cho tối ưu hóa địa phương. Trên thực tế, mặc dù không có kết quả phân tích nào biện minh cho điều này, theo tài liệu về lập trình DC, cách tiếp cận tối ưu hóa địa phương thường cho kết quả tối ưu toàn cục, và một số phương pháp điều chỉnh và chọn điểm xuất phát tồn tại để hỗ trợ việc kết hợp thuật toán tối ưu hóa địa phương sau đây để tìm tối ưu toàn cục trong các trường hợp khác nhau.
Bây giờ chúng ta trình bày một thuật toán để tìm tối ưu địa phương cho một bài toán quy hoạch DC tổng quát. Đầu tiên, chúng ta cung cấp thuật toán ở dạng thô, sau đó chúng ta sẽ giải thích từng bước trong một lần lặp, và cuối cùng, chúng ta sẽ trình bày một vài kết quả liên quan đến hiệu quả và hiệu suất của thuật toán.
Thuật toán:
Hãy đi qua từng bước của thuật toán DCA một cách chi tiết hơn. Phương pháp tổng thể của thuật toán là tạo ra hai chuỗi biến, ${x_k}_k$, ${y_k}_k$ sao cho ${x_k}$ hội tụ đến cực tiểu địa phương của bài toán gốc, $x^*$, và ${y_k}$ hội tụ đến cực tiểu địa phương của bài toán đối ngẫu, $y^*$. Ý tưởng chính là thao tác với tính đối xứng của bài toán gốc và đối ngẫu để theo một biến thể của phương pháp giảm dưới gradient thường được sử dụng trong tối ưu hóa lồi.
Bây giờ hãy xem xét từng bước một cách riêng lẻ.
Ở đây chúng ta trình bày một vài kết quả liên quan đến tính hiệu quả và tính hiệu suất của thuật toán DCA. Chúng ta sẽ đưa ra các kết quả mà không chứng minh, và hướng bất kỳ ai quan tâm đến việc đi sâu hơn vào vấn đề này đến Thoai.
Tài liệu có tham chiếu đến nhiều ứng dụng của Quy hoạch DC trong Nghiên cứu Hoạt động, Học máy và Kinh tế học.
Một ứng dụng thú vị của Quy hoạch DC được thảo luận trong bài báo năm 2006 “A DC-Programming Algorithm for Kernel Selection”. Trong bài báo này, các tác giả thảo luận về một thuật toán tham lam để học một kernel từ một bao lồi của các kernel cơ bản. Mặc dù cách tiếp cận này đã được phổ biến trước đó, nó bị giới hạn trong một tập hữu hạn các kernel cơ bản. Các tác giả nhận xét rằng giới hạn là do tính không lồi của một cực đại hóa quan trọng liên quan đến việc thực hiện việc học, nhưng nhận thấy rằng bài toán tối ưu hóa có thể được công thức hóa như một bài toán quy hoạch DC. Đặc biệt, hàm mục tiêu được sử dụng để đánh giá các kernel cơ bản là DC như là giới hạn của các hàm DC.
Một ứng dụng thú vị khác của Quy hoạch DC được thảo luận trong bài báo năm 2008 “A DC programming approach for feature selection in support vector machines learning”. Ở đây, Quy hoạch DC được sử dụng trong một thuật toán SVM cố gắng chọn các đặc trưng đại diện tối ưu trong dữ liệu trong khi xây dựng một bộ phân loại SVM đồng thời. Các tác giả cân bằng vấn đề này với việc cực tiểu hóa một hàm chuẩn-không trên các vector đặc trưng bước-k. Sử dụng phân rã DC hiển thị dưới đây, các tác giả sử dụng thuật toán DCA để tìm các cực tiểu địa phương và áp dụng nó cho mười bộ dữ liệu - một số trong số đó đặc biệt thưa - để thấy rằng thuật toán DCA tạo ra các bộ phân loại nhất quán tốt thường có tỷ lệ chính xác cao nhất trong số các bộ phân loại được kiểm tra (bao gồm cả SVM tiêu chuẩn, ví dụ). Mặc dù điều này, DCA nhất quán sử dụng ít đặc trưng hơn SVM tiêu chuẩn và các bộ phân loại khác, và kết quả là hiệu quả hơn và sử dụng ít khả năng CPU hơn so với nhiều bộ phân loại thông thường khác. Do đó, nhìn chung, DCA chứng minh là một thuật toán rất hấp dẫn để phân loại dữ liệu, và đặc biệt xuất sắc cho các bộ dữ liệu rất lớn và thưa.
Như chúng ta có thể thấy, Quy hoạch DC khá mới mẻ. Mặc dù kết quả lâu đời nhất được trình bày trong bài giảng này có từ những năm 1950 (của Hartman), nhiều kết quả và thuật toán được thảo luận ở đây được phát triển vào những năm 1990, và các ứng dụng của chúng vẫn còn rất mới đối với cộng đồng khoa học. Tuy nhiên, như có thể thấy từ các ví dụ mà chúng ta đã trình bày, Quy hoạch DC có tiềm năng to lớn để mở rộng và đẩy nhanh nhiều thuật toán và kỹ thuật trung tâm của Học máy, cũng như các lĩnh vực khác. Do đó, có khả năng tương lai gần sẽ mang lại nhiều thuật toán hơn được lấy cảm hứng từ DCA và các cách tiếp cận liên quan đến DCA cũng như các cách tiếp cận tổ hợp toàn cục khác nhau được sử dụng để giải quyết các bài toán Quy hoạch DC, nhưng không được thảo luận ở đây.