Máy phân lớp sử dụng véctơ hỗ trợ (Support Vector Machines) (2) – Trường hợp không phân tách tuyến tính được « CS Study Fun

Tháng tám 2008
T2	T3	T4	T5	T6	T7	CN
« Tháng 7		Tháng 1 »
	1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Máy phân lớp sử dụng véctơ hỗ trợ (Support Vector Machines) (2) – Trường hợp không phân tách tuyến tính được

Đăng bởi tqlong on Tháng tám 3, 2008

Trong bài trước, ta đã tìm hiểu cách SVM chọn siêu phẳng với lề lớn nhất. Tuy nhiên, bài toán tối ưu chỉ giải được (có nghiệm) nếu tập mẫu học phân tách tuyến tính được. Vì thế, cách tìm lề lớn nhất như trong bài trước còn gọi là lề cứng (hard margin). Vậy còn trường hợp không phân tách tuyến tính được thì sao? Rõ ràng, nếu ta vẫn dùng siêu phẳng thì phải chấp nhận có một số mẫu học không thể phân lớp được. Trường hợp này, giáo sư Vapnik gợi ý ta “mềm hóa” các ràng buộc của lề (phương pháp này gọi là lề mềm (soft margin)). Cụ thể bài toán tối ưu (gốc) chuyển thành như sau

$\displaystyle \min_{w,b,\xi}~\frac{1}{2}\|w\|^2+\frac{1}{2} C\left(\sum_{i=1}^N\xi_i\right)^2$ với các ràng buộc $\displaystyle \begin{array}{l} y_i(\langle w,x_i\rangle-b) \geq 1-\xi_i\\\xi_i\geq 0\end{array},\forall i=1,\ldots, N$

Như vậy các ràng buộc cứng $\displaystyle y_i(\langle w,x_i\rangle-b) \geq 1$ được cho phép vi phạm (mềm hóa). Đồng thời, độ “mềm” của ràng buộc bị giới hạn vì hàm mục tiêu chứa đại lượng $\displaystyle C\left(\sum_{i=1}^N\xi_i\right)^2$ . Bây giờ ta tìm bài toán đối ngẫu Lagrange:

$\displaystyle L(w,b,\xi,\lambda,\gamma)=\frac{1}{2}\|w\|^2+ \frac{1}{2}C\left(\sum_{i=1}^N\xi_i\right)^2$ $\displaystyle -\sum_{i=1}^N \lambda_i [y_i(\langle w,x_i\rangle-b)-1+\xi_i]-\sum_{i=1}^N\gamma_i\xi_i$

Lấy đạo hàm theo $\displaystyle w,b,\xi$ ta có

$\displaystyle \begin{cases}\displaystyle \frac{\partial L(w,b,\lambda)}{\partial w} = w - \sum_{i=1}^N \lambda_i y_i x_i = 0\\ \displaystyle \frac{\partial L(w,b,\lambda)}{\partial b} = \sum_{i=1}^N \lambda_i y_i = 0\\ \displaystyle \frac{\partial L(w,b,\lambda)}{\partial \xi_i} = C\left(\sum_{j=1}^N \xi_j\right) - \lambda_i - \gamma_i = 0\end{cases}$ $\displaystyle \Leftrightarrow \begin{cases}\displaystyle w = \sum_{i=1}^N \lambda_i y_i x_i \\ \displaystyle \sum_{i=1}^N \lambda_i y_i = 0 \\ \displaystyle \lambda_i+\gamma_i = C\sum_{j=1}^N \xi_j = \delta\end{cases}$

Thay vào ta được

$\displaystyle \underline{L}(\lambda,\gamma,\delta) = \inf_{w,b,\xi} L(w,b,\xi,\lambda,\gamma) = \sum_{i=1}^N\lambda_i - \frac{1}{2}\sum_{i,j=1}^N\lambda_i\lambda_j y_i y_j\langle x_i,x_j\rangle-\frac{\delta^2}{2C}$

Vậy bài toán đối ngẫu Lagrange là

$\displaystyle \max_{\lambda,\gamma,\delta} \sum_{i=1}^N\lambda_i - \frac{1}{2}\sum_{i,j=1}^N\lambda_i\lambda_j y_i y_j\langle x_i,x_j\rangle-\frac{\delta^2}{2C}$ với các ràng buộc $\displaystyle \sum_{i=1}^N \lambda_i y_i = 0 \\ \lambda_i + \gamma_i = \delta \\ \lambda_i,\gamma_i \geq 0$

Loại bỏ biến $\displaystyle \gamma$ , bài toán trên tương đương với

$\displaystyle \max_{\lambda,\delta} \sum_{i=1}^N\lambda_i - \frac{1}{2}\sum_{i,j=1}^N\lambda_i\lambda_j y_i y_j\langle x_i,x_j\rangle-\frac{\delta^2}{2C}$ với các ràng buộc $\displaystyle\sum_{i=1}^N \lambda_i y_i = 0\\\lambda_i\leq\delta \\\lambda_i,\delta\geq 0$

Đây cũng là bài toán tối ưu hóa bậc 2 (Quadratic Programming) giống như trong trường hợp sử dụng lề cứng.

Nhận xét:

Bằng việc mềm hóa các ràng buộc và thay đổi hàm mục tiêu, bài toán tối ưu vẫn là bài toán quy hoạch bậc 2. Tuy nhiên, các véctơ hỗ trợ lúc này sẽ bao gồm:
- Các véctơ nằm trên lề $\displaystyle y_i(\langle w,x_i\rangle-b) = 1$ (khi $\displaystyle \xi_i = 0$ )
- Các véctơ nằm bên trong lề $\displaystyle y_i(\langle w,x_i\rangle-b) = 1 - \xi_i < 1$ khi $\displaystyle \xi_i > 0$ . Lưu ý là các véctơ này có thể bị phân lớp sai nếu $\displaystyle \xi_i \geq 1$
Có nhiều cách để mềm hóa ràng buộc, thay vì dùng hoảng cách Euclid $\displaystyle C\left(\sum_{i=1}^N \xi_i\right)^2$ ta có thể dùng khoảng cách $\displaystyle L_1$ và thêm vào hàm mục tiêu đại lượng $\displaystyle C\sum_{i=1}^N \xi_i$ . Nói chung, ta có thể thêm vào hàm mục tiêu một lượng bằng
$\displaystyle C F\left(\sum_{i=1}^N \xi_i^\sigma\right)$

trong đó $\displaystyle F$ là một hàm lồi đơn điệu tăng, còn $\displaystyle \sigma\geq 1$ .
Khi thêm đại lượng $\displaystyle C\sum_{i=1}^N \xi_i$ vào hàm mục tiêu, bài toán tối ưu hóa chuyển thành
$\displaystyle \max_{\lambda} \sum_{i=1}^N\lambda_i - \frac{1}{2}\sum_{i,j=1}^N\lambda_i\lambda_j y_i y_j\langle x_i,x_j\rangle$ với các ràng buộc $\displaystyle\sum_{i=1}^N \lambda_i y_i = 0\\ 0\leq\lambda_i\leq C$

Đây có lẽ là cách sử dụng SVM thông dụng nhất. Tại nghiệm tối ưu $\displaystyle \lambda$ , một mẫu học là véctơ hỗ trợ khi và chỉ khi

$\displaystyle 0< \lambda_i \leq C$
Tại sao người ta lại muốn giải bài toán tối ưu ở dạng đối ngẫu? Lý do là
- Các ràng buộc tuyến tính ở bài toán gốc khá phức tạp, trong khi đó, ràng buộc ở bài toán đối ngẫu lại ở dạng hộp $\displaystyle 0\leq\lambda_i\leq C$ .
- Các thuật toán tối ưu có thể tận dụng sự đơn giản của ràng buộc dạng hộp để đơn giản hóa và tăng tốc độ quá trình tối ưu hóa.
- Khi đã biết $\displaystyle \lambda_i,i=1,\ldots,N$ có thể dễ dàng tinh $\displaystyle w,b,\xi$ như sau:
  $\displaystyle w = \sum_{i=1}^N \lambda_i y_i x_i$
  
  Để tính $\displaystyle b$ , chọn một $\displaystyle i$ nào đó để $\displaystyle 0<\lambda_i < C$ suy ra
  
  $\displaystyle \gamma_i > 0 \Rightarrow \xi_i = 0$
  $\displaystyle y_i(\langle w,x_i\rangle-b)=1-\xi_i = 1\Rightarrow b = \langle w,x_i\rangle - y_i$
  
  Để tính $\displaystyle \xi$ , ta có
  
  $\displaystyle \lambda_i < C \Rightarrow \gamma_i > 0 \Rightarrow \xi_i = 0$
  $\displaystyle \lambda_i = C \Rightarrow y_i(\langle w,x_i\rangle-b)=1-\xi_i \Rightarrow \xi_i = 1- y_i(\langle w,x_i\rangle-b)$ .
Để ý là tích vô hướng $\displaystyle \langle w,x\rangle$ có thể thay bằng
$\displaystyle \langle w,x\rangle=\sum_{i=1}^N \lambda_i y_i \langle x_i,x\rangle$

Nghĩa là ta không cần phải tính véctơ $\displaystyle w$ mà chỉ cần ngầm hiểu ta có tính tích vô hướng $\displaystyle \langle w,x\rangle$ với mọi vectơ $\displaystyle x$ . Lưu ý, ở biểu thức trên ta chỉ cần tính với các $\displaystyle \lambda_i>0$ , tức là chỉ cần tính toán với các véctơ hỗ trợ mà thôi.

Bài viết này được đăng vào Tháng tám 3, 2008 lúc 9:43 sáng và tập tin được lưu ở Lý thuyết học máy. Tagged: bài toán tối ưu bậc 2, bài toán đối ngẫu, hard margin, Lagrange, lề cứng, lề mềm, máy phân lớp sử dụng véctơ hỗ trợ, Quadratic Programming, soft margin, Support Vector Machines, SVM. Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin. Bạn có thể bỏ qua phần còn lại và gửi phản hồi. Ping đã bị khóa.

Để lại hồi âm

« Phân lớp bằng siêu phẳng (4) – Máy phân lớp sử dụng véctơ hỗ trợ (Support Vector Machines) (1)

Máy phân lớp sử dụng véctơ hỗ trợ (Support Vector Machines) (3) – Cận trên của xác suất lỗi »

	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Phân lớp bằng siêu phẳng (1) …
	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Bất đẳng thức xác suất (1) …
	H.T.D. trong bài Bất đẳng thức xác suất (1) …

CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Phân loại

Lưu trữ

Thống kê

Bài gần đây

Lời bình gần đây

Trang

Blogroll

Quản trị

Lịch

Theo dõi

Blog D.Q. Huy

Các phương pháp điểm trong

Xem nhiều nhất

Từ khóa

Máy phân lớp sử dụng véctơ hỗ trợ (Support Vector Machines) (2) – Trường hợp không phân tách tuyến tính được

Để lại hồi âm