Hướng dẫn svm loss function python - chức năng mất svm python
1. Giới thiệuGiống như Perceptron Learning Algorithm (PLA), Support Vector Machine (SVM) thuần chỉ làm việc khi dữ liệu của 2 classes là linearly separable. Một cách tự nhiên, chúng ta cũng mong muốn rằng SVM có thể làm việc với dữ liệu gần linearly separable giống như Logistic Regression đã làm được. Show
Bạn được khuyến khích đọc bài Support Vector Machine trước khi đọc bài này. Xét 2 ví dụ trong Hình 1 dưới đây: Hình 1: Soft margin SVM. Khi a) có nhiễu hoặc b) dữ liệu gần linearly separable, SVM thuần sẽ không hoạt động hiệu quả. Có hai trường hợp dễ nhận thấy SVM làm việc không hiệu quả hoặc thậm chí không làm việc:
Trong cả hai trường hợp trên, margin tạo bởi đường phân chia và đường nét đứt mảnh còn được gọi là soft margin (biên mềm). Cũng theo cách gọi này, SVM thuần còn được gọi là Hard Margin SVM (SVM biên cứng). Trong bài này, chúng ta sẽ tiếp tục tìm hiểu một biến thể của Hard Margin SVM có tên gọi là Soft Margin SVM. Bài toán tối ưu cho Soft Margin SVM có hai cách tiếp cận khác nhau, cả hai đều mang lại những kết quả thú vị và có thể phát triển tiếp thành các thuật toán SVM phức tạp và hiệu quả hơn. Cách giải quyết thứ nhất là giải một bài toán tối ưu có ràng buộc bằng cách giải bài toán đối ngẫu giống như Hard Margin SVM; cách giải dựa vào bài toán đối ngẫu này là cơ sở cho phương pháp Kernel SVM cho dữ liệu thực sự không linearly separable mà tôi sẽ đề cập trong bài tiếp theo. Hướng giải quyết này sẽ được tôi trình bày trong Mục 3 bên dưới. Cách giải quyết thứ hai là đưa về một bài toán tối ưu không ràng buộc. Bài toán này có thể giải bằng các phương pháp Gradient Descent. Nhờ đó, cách giải quyết này có thể được áp dụng cho các bài toán large cale. Ngoài ra, trong cách giải này, chúng ta sẽ làm quen với một hàm mất mát mới có tên là hinge loss. Hàm mất mát này có thể mở rộng ra cho bài toán multi-class classification mà tôi sẽ đề cập sau 2 bài nữa (Multi-class SVM). Cách phát triển từ Soft Margin SVM thành Multi-class SVM có thể so sánh với cách phát triển từ Logistic Regression thành Softmax Regression. Hướng giải quyết này sẽ được tôi trình bày trong Mục 4 bên dưới. Trước hết, chúng ta cùng đi phân tích bài toán. 2. Phân tích toán họcNhư đã đề cập phía trên, để có một margin lớn hơn trong Soft Margin SVM, chúng ta cần hy sinh một vài điểm dữ liệu bằng cách chấp nhận cho chúng rơi vào vùng không an toàn. Tất nhiên, chúng ta phải hạn chế sự hy sinh này, nếu không, chúng ta có thể tạo ra một biên cực lớn bằng cách hy sinh hầu hết các điểm. Vậy hàm mục tiêu nên là một sự kết hợp để tối đa margin và tối thiểu sự hy sinh. Giống như với Hard Margin SVM, việc tối đa margin có thể đưa về việc tối thiểu \(||\mathbf{w}||_2^2\). Để xác định sự hy sinh, chúng ta cùng theo dõi Hình 2 dưới đây:
Với mỗi điểm \(\mathbf{x}_n\) trong tập toàn bộ dữ liệu huấn luyện, ta giới thiệu thêm một biến đo sự hy sinh \(\xi_n\) tương ứng. Biến này còn được gọi là slack variable. Với những điểm \(\mathbf{x}_n\) nằm trong vùng an toàn, \(\xi_n = 0\). Với mỗi điểm nằm trong vùng không an toàn như \(\mathbf{x}_1, \mathbf{x}_2\) hay \(\mathbf{x}_3\), ta có \(\xi_i > 0\). Nhận thấy rằng nếu \(y_i= \pm 1\) là nhãn của \(\mathbf{x}_i\) trong vùng không an toàn thì \(\xi_i = |\mathbf{w}^T\mathbf{x}_i + b - y_i|\). (Bạn có nhận ra không?) Nhắc lại bài toán tối ưu cho Hard Margin SVM: \[ \begin{eqnarray} (\mathbf{w}, b) &=& \arg \min_{\mathbf{w}, b} \frac{1}{2}{||\mathbf{w}||_2^2} \newline \text{subject to:}~ && y_n(\mathbf{w}^T\mathbf{x}_n + b) \geq 1, \forall n = 1, 2, \dots, N ~~~~(1) \end{eqnarray} \] Với Soft Margin SVM, hàm mục tiêu sẽ có thêm một số hạng nữa giúp tối thiểu sự hy sinh. Từ đó ta có hàm mục tiêu: \[ \frac{1}{2}{||\mathbf{w}||_2^2} + C \sum_{n=1}^N \xi_n \] trong đó \(C\) là một hằng số dương và \(\xi = [\xi_1, \xi_2, \dots, \xi_N]\). Hằng số \(C\) được dùng để điều chỉnh tầm quan trọng giữa margin và sự hy sinh. Hằng số này được xác định từ trước bởi người lập trình hoặc có thể được xác định bởi cross-validation. Điều kiện ràng buộc sẽ thay đổi một chút. Với mỗi cặp dữ liệu \((\mathbf{x}_n, y_n)\), thay vì ràng buộc cứng \(y_n(\mathbf{w}^T\mathbf{x}_n + b) \geq 1\), chúng ta sẽ có ràng buộc mềm: \[ y_n(\mathbf{w}^T\mathbf{x}_n + b) \geq 1 - \xi_n \Leftrightarrow 1 - \xi_n - y_n(\mathbf{w}^T\mathbf{x}_n + b) \leq 0, ~~ \forall n = 1, 2, \dots, n \] Và ràng buộc phụ \(\xi_n \geq 0, ~\forall n = 1, 2, \dots, N\). Tóm lại, ta sẽ có bài toán tối ưu ở dạng chuẩn cho Soft-margin SVM: \[ \begin{eqnarray} (\mathbf{w}, b, \xi) &=& \arg \min_{\mathbf{w}, b, \xi} \frac{1}{2}{||\mathbf{w}||_2^2} + C \sum_{n=1}^N \xi_n \newline \text{subject to:}~ && 1 - \xi_n - y_n(\mathbf{w}^T\mathbf{x}_n + b) \leq 0, \forall n = 1, 2, \dots, N ~~~~(2) \newline && -\xi_n \leq 0, ~\forall n = 1, 2, \dots, N \end{eqnarray} \] Nhận xét:
Dưới đây, chúng ta sẽ cùng giải quyết bài toán tối ưu \((2)\) bằng hai cách khác nhau. 3. Bài toán đối ngẫu LagrangeChú ý rằng bài toán này có thể giải trực tiếp bằng các toolbox hỗ trợ QP, nhưng giống như với Hard Margin SVM, chúng ta sẽ quan tâm hơn tới bài toán đối ngẫu. Trước kết, ta cần kiểm tra tiêu chuẩn Slater cho bài toán tối ưu lồi \((2)\). Nếu tiêu chuẩn này được thoả mãn, strong duality sẽ thoả mãn, và ta sẽ có nghiệm của bài toán tối ưu \((2)\) là nghiệm của hệ điều kiện KKT. (Những kiến thức được đề cập trong mục này có thể được tìm thấy trong Bài 18). 3.1. Kiểm tra tiêu chuẩn SlaterRõ ràng là với mọi \(n = 1, 2, \dots, N\) và mọi \((\mathbf{w}, b)\), ta luôn có thể tìm được các số dương \(\xi_n, n = 1, 2, \dots, N\) đủ lớn sao cho: \[ y_n(\mathbf{w}^T\mathbf{x}_n + b) + \xi_n > 1, ~\forall n = 1, 2, \dots, N \]dương \(\xi_n, n = 1, 2, \dots, N\) đủ lớn sao cho: \[ y_n(\mathbf{w}^T\mathbf{x}_n + b) + \xi_n > 1, ~\forall n = 1, 2, \dots, N \] Vậy nên bài toán này thoả mãn tiêu chuẩn Slater. 3.2. Lagrangian của bài toán Soft-margin SVMLagrangian cho bài toán \((2)\) là: \[ \mathcal{L}(\mathbf{w}, b, \xi, \lambda, \mu) = \frac{1}{2}{||\mathbf{w}||_2^2} + C \sum_{n=1}^N \xi_n + \sum_{n=1}^N \lambda_n ( 1 - \xi_n - y_n(\mathbf{w}^T\mathbf{x}_n + b)) - \sum_{n=1}^N \mu_n \xi_n ~ (3) \] với \(\lambda = [\lambda_1, \lambda_2, \dots, \lambda_N]^T \succeq 0\) và \(\mu = [\mu_1, \mu_2, \dots, \mu_N]^T \succeq 0\) là các biến đối ngẫu Lagrange (vector nhân tử Lagrange). 3.3. Bài toán đối ngẫuHàm số đối ngẫu của bài toán tối ưu \((2)\) là: \[ g(\lambda, \mu) = \min_{\mathbf{w}, b, \xi} \mathcal{L}(\mathbf{w}, b, \xi, \lambda, \mu) \] Với mỗi cặp \((\lambda,\mu)\), chúng ta sẽ quan tâm tới \((\mathbf{w}, b, \xi)\) thoả mãn điều kiện đạo hàm của Lagrangian bằng 0: \[ \begin{eqnarray} \frac{\partial \mathcal{L}}{\partial \mathbf{w}} & = & 0 \Leftrightarrow \mathbf{w} = \sum_{n=1}^N \lambda_n y_n \mathbf{x}_n &&(4)\newline \frac{\partial \mathcal{L}}{\partial b} & = & 0 \Leftrightarrow \sum_{n=1}^N \lambda_n y_n = 0 && (5)\newline \frac{\partial \mathcal{L}}{\partial \xi_n} & = & 0 \Leftrightarrow \lambda_n = C - \mu_n && (6) \end{eqnarray} \] Từ \((6)\) ta thấy rằng ta chỉ quan tâm tới những cặp \((\lambda, \mu)\) sao cho \(\lambda_n = C - \mu_n\). Từ đây ta cũng suy ra \(0 \leq \lambda_n, \mu_n \leq C, n = 1, 2, \dots, N\). Thay các biểu thức này vào Lagrangian ta sẽ thu được hàm đối ngẫu: \[ g(\lambda, \mu) = \sum_{n=1}^N \lambda_n - \frac{1}{2} \sum_{n=1}^N\sum_{m=1}^N \lambda_n \lambda_m y_n y_m \mathbf{x}_n^T\mathbf{x}_m \] Chú ý rằng hàm này không phụ thuộc vào \(\mu\) nhưng ta cần lưu ý ràng buộc \((6)\), ràng buộc này và điều kiện không âm của \(\lambda\) có thể được viết gọn lại thành \(0 \leq \lambda_n \leq C\), và ta đã giảm được biến \(\mu\). Lúc này, bài toán đối ngẫu được xác định bới: \[ \begin{eqnarray} \lambda &=& \arg \max_{\lambda} g(\lambda) &&\newline \text{subject to:}~ && \sum_{n=1}^N \lambda_ny_n = 0 && (7)\newline && 0 \leq \lambda_n \leq C, ~\forall n= 1, 2, \dots, N && (8) \end{eqnarray} \] Bài toán này gần giống với bài toán đối ngẫu của Hard Margin SVM, chỉ khác là ta có chặn trên cho mỗi \(\lambda_n\). Khi \(C\) rất lớn, ta có thể coi hai bài toán là như nhau. Ràng buộc \((8)\) còn được gọi là box constraint vì không gian các điểm \(\lambda\) thoả mãn ràng buộc này giống như một hình hộp chữ nhật trong không gian nhiều chiều. Bài toán này cũng hoàn toàn giải được bằng các công cụ giải QP thông thường, ví dụ CVXOPT như tôi đã thực hiện trong bài Hard Margin SVM. Sau khi tìm được \(\lambda\) của bài toán đối ngẫu, ta vẫn phải quay lại tìm nghiệm \((\mathbf{w}, b, \xi)\) của bài toán gốc. Để làm điều này, chúng ta cùng xem xét hệ điều kiện KKT. 3.4. Hệ điều kiện KKTHệ điều kiện KKT của bài toán tối ưu Soft Margin SVM là, với mọi \(n = 1, 2, \dots, N\): \[ \begin{eqnarray} 1 - \xi_n - y_n(\mathbf{w}^T\mathbf{x}_n + b) &\leq& 0 && (9) \newline -\xi_n &\leq& 0 &&(10)\newline \lambda_n &\geq& 0 &&(11)\newline \mu_n &\geq & 0 && (12)\newline \lambda_n ( 1 - \xi_n - y_n(\mathbf{w}^T\mathbf{x}_n + b)) &=& 0 && (13)\newline \mu_n \xi_n &=& 0 &&(14)\newline \mathbf{w} &=& \sum_{n=1}^N \lambda_n y_n \mathbf{x}_n &&(4)\newline \sum_{n=1}^N \lambda_n y_n &=& 0 && (5)\newline \lambda_n &=& C - \mu_n && (6) \end{eqnarray} \] (Để cho dễ hình dung, tôi đã viết lại các điều kiện \((4), (5), (6)\) trong hệ này.) Ta có một vài quan sát như sau:
Ngoài ra, những điểm tương ứng với \(0 < \lambda_n \leq C\) bây giờ là sẽ là các support vectors. Mặc dù những điểm này có thể không nằm trên margins, chúng vẫn được coi là support vectors vì có công đóng góp cho việc tính toán \(\mathbf{w}\) thông qua phương trình \((4)\). Như vậy, dựa trên các giá trị của \(\lambda_n\) ta có thể dự đoán được vị trí tương đối của \(\mathbf{x}_n\) so với hai margins. Đặt \(\mathcal{M} = \{n: 0 < \lambda_n < C \}\) và \(\mathcal{S} = \{m: 0 < \lambda_m \leq C\}\). Tức \(\mathcal{M}\) là tập hợp các chỉ số của các điểm nằm chính xác trên margins - hỗ trợ cho việc tính \(b\), \(\mathcal{S}\) là tập hợp các chỉ số của các support vectors - hỗ trợ trực tiếp cho việc tính \(\mathbf{w}\). Tương tự như với Hard Margin SVM, các hệ số \(\mathbf{w}, b\) có thể được xác định bởi: \[ \begin{eqnarray} \mathbf{w} &=& \sum_{m \in \mathcal{S}} \lambda_m y_m \mathbf{x}_m & ~~~(15) \newline b &=& \frac{1}{N_{\mathcal{M}}} \sum_{n \in \mathcal{M}} (y_n - \mathbf{w}^T\mathbf{x}_n) = \frac{1}{N_{\mathcal{M}}} \sum_{n \in \mathcal{M}} \left(y_n - \sum_{m \in \mathcal{S}} \lambda_m y_m \mathbf{x}_m^T\mathbf{x}_n\right) & ~~~ (16) \end{eqnarray} \] Nhắc lại rằng mục đích cuối cùng là xác định nhãn cho một điểm mới chứ không phải là tính \(\mathbf{w}\) và \(b\) nên ta quan tâm hơn tới cách xác định giá trị của biếu thức sau với một điểm dữ liệu \(\mathbf{x}\) bất kỳ: \[ \mathbf{w}^T\mathbf{x} + b = \sum_{m \in \mathcal{S}} \lambda_m y_m \mathbf{x}_m^T \mathbf{x} + \frac{1}{N_{\mathcal{M}}} \sum_{n \in \mathcal{M}} \left(y_n - \sum_{m \in \mathcal{S}} \lambda_m y_m \mathbf{x}_m^T\mathbf{x}_n\right) \] Và trong cách tính này, ta chỉ cần quan tâm tới tích vô hướng của hai điểm bất kỳ. Ở bài sau các bạn sẽ thấy rõ lợi ích của việc này nhiều hơn. 4. Bài toán tối ưu không ràng buộc cho Soft Margin SVMTrong mục này, chúng ta sẽ đưa bài toán tối ưu có ràng buộc \((2)\) về một bài toán tối ưu không ràng buộc, và có có khả năng giải được bằng các phương pháp Gradient Descent. 4.1. Bài toán tối ưu không ràng buộc tương đươngĐể ý thấy rằng điều kiện ràng buộc thứ nhất: \[ 1 - \xi_n -y_n(\mathbf{w}^T\mathbf{x} + b)) \leq 0 \Leftrightarrow \xi_n \geq 1 - y_n(\mathbf{w}^T\mathbf{x} + b)) \] Kết hợp với điều kiện \(\xi_n \geq 0\) ta sẽ thu được bài toán ràng buộc tương đương với bài toán \((2)\) như sau: \[ \begin{eqnarray} (\mathbf{w}, b, \xi) &=& \arg \min_{\mathbf{w}, b, \xi} \frac{1}{2}{||\mathbf{w}||_2^2} + C \sum_{n=1}^N \xi_n \newline \text{subject to:}~ && \xi_n \geq \max(0, 1 - y_n(\mathbf{w}^T\mathbf{x} + b)), ~\forall n = 1, 2, \dots, N~~~ (17) \end{eqnarray} \] Tiếp theo, để đưa bài toán \((17)\) về dạng không ràng buộc, chúng ta sẽ chứng minh nhận xét sau đây bằng phương pháp phản chứng: Nếu \((\mathbf{w}, b, \xi)\) là nghiệm của bài toán tối ưu \((17)\), tức tại đó hàm mục tiêu đạt giá trị nhỏ nhất, thì: \[ \xi_n = \max(0, 1 - y_n(\mathbf{w}^T\mathbf{x}_n + b)), ~\forall n = 1, 2, \dots, N ~~~ (18) \] Thật vậy, giả sử ngược lại, tồn tại \(n\) sao cho: \[ \xi_n > \max(0, 1 - y_n(\mathbf{w}^T\mathbf{x}_n + b)) \] ta chọn \(\xi_n’ = \max(0, 1 - y_n(\mathbf{w}^T\mathbf{x}_n + b))\), ta sẽ thu được một giá trị thấp hơn của hàm mục tiêu, trong khi tất cả các ràng buộc vẫn được thoả mãn. Điều này mâu thuẫn với việc hàm mục tiêu đã đạt giá trị nhỏ nhất! Vậy nhận xét \((18)\) được chứng minh. Khi đó, ta thay toàn bộ các giá trị của \(\xi_n\) trong \((18)\) vào hàm mục tiêu: \[ \begin{eqnarray} (\mathbf{w}, b, \xi) &=& \arg \min_{\mathbf{w}, b, \xi} \frac{1}{2}{||\mathbf{w}||_2^2} + C \sum_{n=1}^N \max(0, 1 - y_n(\mathbf{w}^T\mathbf{x}_n + b)) \newline \text{subject to:}~ && \xi_n = \max(0, 1 - y_n(\mathbf{w}^T\mathbf{x}_n + b)), ~\forall n = 1, 2, \dots, N~~~ (19) \end{eqnarray} \] Rõ ràng rằng biến số \(\xi\) không còn quan trọng trong bài toán này nữa, ta có thể lược bỏ nó mà không làm thay đổi nghiệm của bài toán: \[ (\mathbf{w}, b)= \arg \min_{\mathbf{w}, b} \frac{1}{2}{||\mathbf{w}||_2^2} + C \sum_{n=1}^N \max(0, 1 - y_n(\mathbf{w}^T\mathbf{x}_n + b)) \triangleq \arg\min_{\mathbf{w}, b} J(\mathbf{w}, b) ~~~~ (20) \] Đây là một bài toán tối ưu không ràng buộc với hàm mất mát \(J(\mathbf{w}, b)\). Bài toán này có thể giải được bằng các phương pháp Gradient Descent. Nhưng trước hết, chúng ta cùng xem xét hàm mất mát này từ một góc nhìn khác, bằng định nghĩa của một hàm gọi là hinge loss 4.2. Hinge lossNhắc lại một chút về hàm cross entropy chúng ta đã biết từ bài Logistic Regression và Softmax Regression. Với mỗi cặp hệ số \((\mathbf{w}, b)\) và cặp dữ liệu, nhãn \((\mathbf{x}_n, y_n)\), đặt \(z_n = \mathbf{w}^T\mathbf{x}_n + b\) và \(a_n = \sigma(z_n)\) ( \(\sigma\) là sigmoid function). Hàm cross entropy được định nghĩa là: \[ J_n^1(\mathbf{w}, b) = -(y_n \log(a_n) + (1 - y_n) \log(1 - a_n)) \] Chúng ta đã biết rằng, hàm cross entropy đạt giá trị càng nhỏ nếu xác suất \(a_n\) càng gần với \(y_n\) \((0 < a_n < 1)\). Ở đây, chúng ta làm quen với một hàm số khác cũng được sử dụng nhiều trong các classifiers: \[ J_n(\mathbf{w}, b) = \max(0, 1 - y_nz_n) \] Hàm này có tên là hinge loss. Trong đó, \(z_n\) có thể được coi là score của \(\mathbf{x}_n\) ứng với cặp hệ số \((\mathbf{w}, b)\), \(y_n\) chính là đầu ra mong muốn. Hình 3 đưới dây mô tả hàm số hinge loss \(f(ys) = \max(0, 1 - ys)\) và so sánh với hàm zero-one loss. Hàm zero-one loss là hàm đếm các điểm bị misclassified.
Trong Hình 3, biến số là \(y\) là tích của đầu ra mong muốn (ground truth) và đầu ra tính được (score). Những điểm ở phía phải của trục tung ứng với những điểm được phân loại đúng, tức \(s\) tìm được cùng dấu với \(y\). Những điểm ở phía trái của trục tung ứng với các điểm bị phân loại sai. Ta có các nhận xét:
4.3. Xây dựng hàm mất mátBây giờ, nếu ta xem xét bài toán Soft Margin SVM dưới góc nhìn hinge loss: Với mỗi cặp \((\mathbf{w}, b)\), đặt: \[ L_n(\mathbf{w}, b) = \max(0, 1 - y_n(\mathbf{w}^T\mathbf{x}_n + b)) \] Lấy tổng tất cả các loss này (giống như cách mà Logistic Regression hay Softmax Regression lấy tổng của tất cả các cross entropy loss) theo \(n\) ta được: \[ L(\mathbf{w}, b) = \sum_{n=1}^N L_i = \sum_{n=1}^N \max(0, 1 - y_n(\mathbf{w}^T\mathbf{x}_n + b)) \] Câu hỏi đặt ra là, nếu ta trực tiếp tối ưu tổng các hinge loss này thì điều gì sẽ xảy ra? Trong trường hợp dữ liệu trong hai class là linearly separable, ta sẽ có giá trị tối ưu tìm được của \(L(\mathbf{w}, b)\) là bằng 0. Điều này có nghĩa là: \[ 1 - y_n (\mathbf{w}^T\mathbf{x}_n + b) \leq 0, ~\forall n = 1, 2, \dots, N \] Nhân cả hai về với một hằng số \(a > 1\) ta có: \[ \begin{eqnarray} a - y_n (a\mathbf{w}^T\mathbf{x}_n + ab) &\leq& 0, ~\forall n = 1, 2, \dots, N \newline \Rightarrow 1 - y_n (a\mathbf{w}^T\mathbf{x}_n + ab) &\leq& 1 - a < 0, ~\forall n = 1, 2, \dots, N \end{eqnarray} \] Điều này nghĩa là \((a\mathbf{w}, ab)\) cũng là nghiệm của bài toán. Nếu không có điều kiện gì thêm, bài toán có thể dẫn tới nghiệm không ổn định vì các hệ số của nghiệm có thể lớn tuỳ ý! Để tránh bug này, chúng ta cần thêm một số hạng nữa vào \(L(\mathbf{w}, b)\) gọi là số hạng regularization, giống như cách chúng ta đã làm để tránh overfitting trong neural networks. Lúc này, ta sẽ có hàm mất mát tổng cộng là: \[ J(\mathbf{w}, b) = L(\mathbf{w}, b) + \lambda R(\mathbf{w}, b) \] với \(\lambda\) là một số dương, gọi là regularization parameter, hàm \(R()\) sẽ giúp hạn chế việc các hệ số \((\mathbf{w}, b)\) trở nên quá lớn. Có nhiều cách chọn hàm \(R()\), nhưng cách phổ biến nhất là \(l_2\), khi đó hàm mất mát của Soft Margin SVM sẽ là: \[ J(\mathbf{w}, b) = \sum_{n=1}^N \max(0, 1 - y_n(\mathbf{w}^T\mathbf{x}_n + b)) + \frac{\lambda}{2} ||\mathbf{w}||_2^2 ~~~~~~~~~~~(21) \] Kỹ thuật này còn gọi là weight decay. Chú ý rằng weight decay thường không được áp dụng lên thành phần bias \(b\). Ta thấy rằng hàm mất mát \((21)\) giống với hàm mất mát \((20)\) với \(\lambda = \frac{1}{C}\). Ở đây, tôi đã lấy \(\lambda /2\) để biểu thức đạo hàm được đẹp hơn. Trong phần tiếp theo của mục này, chúng ta sẽ quan tâm tới bài toán tối ưu hàm mất mát được cho trong \((21)\). Nhận thấy rằng ta có thể khiến biểu thức \((19)\) gọn hơn một chút bằng cách sử dụng bias trick như đã làm trong Linear Regression hay các bài về neurel networks. Bằng cách mở rộng thêm một thành phần bằng 1 vào các điểm dữ liệu \(\mathbf{x}_n \in \mathbb{R}^d\) để được \(\bar{\mathbf{x}}_n \in \mathbb{R}^{d+1}\) và kết hợp \(\mathbf{w}, b\) thành một vector \(\bar{\mathbf{w}} = [\mathbf{w}^T, b]^T \in \mathbb{R}^{d+1}\) ta sẽ có một biểu thức gọn hơn. Khi đó, hàm mất mát trong \((21)\) có thể được viết gọn thành: \[ J(\mathbf{\bar{w}}) = \underbrace{\sum_{n=1}^N \max(0, 1 - y_n\bar{\mathbf{w}}^T\mathbf{\bar{x}}_n)}_{\text{hinge loss}} + \underbrace{\frac{\lambda}{2} ||\mathbf{w}||_2^2}_{\text{regularization}} \] Các bạn có thể nhận thấy rằng đây là một hàm lồi theo \(\mathbf{\bar{w}}\) vì:
Vì bài toán tối ưu bây giờ là không ràng buộc, chúng ta có thể sử dụng các phương pháp Gradient Descent để tối ưu. Hơn nữa, vì tính chất lồi của hàm mất mát, nếu chọn learning rate không quá lớn và số vòng lặp đủ nhiều, thuật toán sẽ hội tụ tới điểm global optimal của bài toán. 4.4. Tối ưu hàm mất mátTrước hết ta cần tính được đạo hàm của hàm mất mát theo \(\mathbf{\bar{w}}\). Việc này thoáng qua có vẻ hơi phức tạp vì ta cần tính đạo hàm của hàm \(\max\), nhưng nếu chúng ta nhìn vào đạo hàm của hinge loss, ta có thể tính được đạo hàm theo \(\mathbf{\bar{w}}\) một cách đơn giản. Chúng ta tạm quên đi đạo hàm của phần regularization vì nó đơn giản bằng \(\lambda \left[\begin{matrix} \mathbf{w}\newline 0 \end{matrix}\right]\) với thành phần 0 ở cuối chính là đạo hàm theo bias của thành phần regularization. Với phần hinge loss, xét từng điểm dữ liệu, ta có hai trường hợp:
Để tính gradient cho toàn bộ dữ liệu, chúng ta cần một chút kỹ năng biến đổi đại số tuyến tính. Đặt: \[ \begin{eqnarray} \mathbf{Z} &=& [y_1 \mathbf{\bar{x}}_1, y_2 \mathbf{\bar{x}}_2, \dots, y_N\mathbf{\bar{x}}_N] & ~~~(22) \newline \mathbf{u} &=& [y_1\mathbf{\bar{w}}^T\mathbf{\bar{x}}_1,y_2\mathbf{\bar{w}}^T\mathbf{\bar{x}}_2, \dots, y_N \mathbf{\bar{w}}^T \mathbf{\bar{x}}_N] = \mathbf{\bar{w}}^T\mathbf{Z} & ~~~ (23) \end{eqnarray} \] với chú ý rằng \(\mathbf{u}\) là một vector hàng. Tiếp tục, ta cần xác định các vị trí của \(\mathbf{u}\) có giá trị nhỏ hơn 1, tức ứng với TH2 ở trên. Bằng cách đặt: \[ \mathcal{H} = \{n: u_n < 1\} \] ta có thể suy ra cách tính đạo hàm theo \(\mathbf{\bar{w}}\) của hàm mất mát là \[ \nabla J(\mathbf{\bar{w}}) = \sum_{n \in \mathcal{H}} - y_n\mathbf{\bar{x}}_n + \lambda \left[\begin{matrix} \mathbf{w}\newline 0 \end{matrix}\right] ~~~ (24) \] Các bạn sẽ thấy cách tính toán giá trị này một cách hiệu quả trong phần lập trình. Vậy quy tắc cập nhật của \(\mathbf{\bar{w}}\) sẽ là: \[ \mathbf{\bar{w}} = \mathbf{\bar{w}} - \eta \left(\sum_{n \in \mathcal{H}} - y_n\mathbf{\bar{x}}_n + \lambda \left[\begin{matrix} \mathbf{w}\newline 0 \end{matrix}\right]\right) ~~~ (25) \] với \(\eta\) là learning rate. Với các bài toán large-scale, ta có thể sử dụng phương pháp Mini-batch Gradient Descent để tối ưu. Đây chính là một ưu điểm của hướng tiếp cận theo hinge loss. 5. Kiểm chứng bằng lập trìnhTrong mục này, chúng ta cùng làm hai thí nghiệm nhỏ. Thứ nghiệm thứ nhất sẽ đi tìm nghiệm của một bài toán Soft Margin SVM bằng ba cách khác nhau: Sử dụng thư viện sklearn, Giải bài toán đối ngẫu bằng CVXOPT, và Tối ưu hàm mất mát không ràng bằng phương pháp Gradient Descent. Nếu mọi tính toán ở trên là chính xác, nghiệm của ba cách làm này sẽ giống nhau, khác nhau có thể một chút bởi sai số trong tính toán. Ở thí nghiệm thứ hai, chúng ta sẽ thay \(C\) bởi những giá trị khác nhau và cùng xem các margin thay đổi như thế nào. 5.1. Giải bài toán Soft Margin bằng 3 cách khác nhauSource code cho phần này có thể được tìm thấy tại đây. 5.1.1. Khai báo thư viện và tạo dữ liệu giả
Hình 4 minh hoạ các điểm dữ liệu của hai classes.
5.1.2. Giải bài toán bằng thư viện sklearnTa chọn \(C = 100\) trong thí nghiệm này:
Nghiệm tìm được:
5.1.3. Tìm nghiệm bằng giải bài toán đối ngẫuTương tự như việc giải bài toán Hard Margin SVM, chỉ khác rằng ta có thêm ràng buộc về chặn trên của các nhân thử Lagrange:
Trong các thành phần của 1 tìm được, có rất nhiều thành phần nhỏ tới 2 hay 3. Đây chính là các 4. Có rất nhiều phần tử xấp xỉ 5, đây chính là các 6 bằng với 7, tương ứng với các support vectors không nằm trên margins, các sai số nhỏ xảy ra do tính toán. Các giá trị còn lại nằm giữa 8 và 9 là các giá trị tương ứng với các điểm nằm chính xác trên hai margins.Tiếp theo, ta cần tính 0 và 1 theo công thức \((15)\) và \((16)\). Trước đó ta cần tìm tập hợp các điểm support và những điểm nằm trên margins.
Kết quả:
Kết quả này gần giống với kết quả tìm được bằng sklearn. 5.1.4. Tìm nghiệm bằng giải bài toán không ràng buộcTrong phương pháp này, chúng ta cần tính gradient của hàm mất mát. Như thường lệ, chúng ta cần kiểm chứng này bằng cách so sánh với numerical gradient. Chú ý rằng trong phương pháp này, ta cần dùng tham số 2.
Vì sự khác nhau giữa hai cách tính gradient là bằng 0, ta có thể yên tâm rằng gradient tính được là chính xác. Sau khi chắc chắn rằng gradient tìm được đã chính xác, ta có thể bắt đầu làm Gradient Descent:
Kết quả: 0Ta thấy rằng kết quả tìm được bằng ba cách là như nhau. Hình 5 dưới đây minh hoạ kết quả bằng ba cách tính: Trong thực hành, phương pháp 1 chắc chắn được lựa chọn. Hai phương pháp còn lại được dùng làm cơ sở cho các phương pháp SVM nâng cao hơn trong các bài sau. 5.2. Ảnh hưởng của \(C\) lên nghiệmHình 6 dưới đây minh hoạ nghiệm tìm được cho bài toán phía trên nhưng với các giá trị \(C\) khác nhau. Nghiệm được tìm bằng thư viện sklearn. Hình 6: Ảnh hưởng của \(C\) lên nghiệm của Soft Margin SVM. Khi \(C\) càng lớn thì biên càng nhỏ. Chúng ta nhận thấy rằng khi (C) càng lớn thì biên càng nhỏ đi. Điều này phù hợp với suy luận của chúng ta ở Mục 2. 6. Tóm tắt và thảo luận
7. Tài liệu tham khảo[1] Bishop, Christopher M. “Pattern recognition and Machine Learning.”, Springer (2006). (book) [2] Duda, Richard O., Peter E. Hart, and David G. Stork. Pattern classification. John Wiley & Sons, 2012. [3] 3[4] LIBSVM – A Library for Support Vector Machines [5] Bennett, K. P. (1992). “Robust linear programming discrimination of two linearly separable sets”. Optimization Methods and Software 1, 23–34. [6] Sch¨olkopf, B., A. Smola, R. C.Williamson, and P. L. Bartlett (2000). “New support vector algorithms”. Neural Computation 12(5), 1207–1245 [7] Rosasco, L.; De Vito, E. D.; Caponnetto, A.; Piana, M.; Verri, A. (2004). “Are Loss Functions All the Same?”. Neural Computation. 16 (5): 1063–1076 Nếu có câu hỏi, Bạn có thể để lại comment bên dưới hoặc trên Forum để nhận được câu trả lời sớm hơn. Bạn đọc có thể ủng hộ blog qua 'Buy me a cofee' ở góc trên bên trái của blog. Tôi vừa hoàn thành cuốn ebook 'Machine Learning cơ bản', bạn có thể đặt sách tại đây. Cảm ơn bạn. |