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

Learn & Enjoy …

Posts Tagged ‘generalization error’

« Những bài viết trước

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

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

Trong bài trước, ta đã tìm hiểu quá trình mềm hóa các ràng buộc của bài toán tìm siêu phẳng có lề lớn nhất. Ở một cách nhìn khác, việc đưa vào hàm mục tiêu các đại lượng \displaystyle \left(\sum_{i=1}^N \xi_i\right)^2 hoặc \displaystyle \sum_{i=1}^N \xi_i còn có một ý nghĩa khác. Các đại lượng này còn là cận trên của số mẫu học bị phân lớp nhầm. Như vậy, khi tối thiểu hóa hàm mục tiêu, cùng lúc ta tối thiểu hóa cận trên của số mẫu học bị phân lớp nhầm. Đây là một kĩ thuật tối ưu hóa rất hay được sử dụng khi hàm mục tiêu không liên tục (số lỗi phân lớp không liên tục), người ta tạo một cận trên của hàm mục tiêu và tối thiểu hóa cận trên này (còn gọi là kỹ thuật nới lỏng các ràng buộc nguyên – relaxation).

Để ý rằng, khi tìm được nghiệm tối ưu \displaystyle \lambda,\xi, theo điều kiện KKT, xảy ra những trường hợp sau:

  • \displaystyle \lambda_i = 0 hay \displaystyle x_i không là véctơ hỗ trợ. Khi đó \displaystyle \gamma_i = \delta - \lambda_i > 0, tức là \displaystyle \xi_i = 0 và \displaystyle y_i(\langle w,x_i\rangle-b)\geq 1, mẫu học \displaystyle x_i đã được phân lớp đúng.
  • \displaystyle \lambda_i > 0 suy ra \displaystyle y_i(\langle w,x_i\rangle-b)=1-\xi_i. Có 3 trường hợp con:
    • \displaystyle \xi_i = 0, suy ra \displaystyle y_i(\langle w,x_i\rangle-b)=1 hay mẫu học \displaystyle x_i vẫn được phân lớp đúng (nằm trên lề của siêu phẳng.
    • \displaystyle 0 < \xi_i < 1 , suy ra \displaystyle y_i(\langle w,x_i\rangle-b)=1-\xi_i > 0 hay mẫu học \displaystyle x_i vẫn được phân lớp đúng (mặc dù nằm ở bên trong lề).
    • \displaystyle \xi_i \geq 1, suy ra \displaystyle y_i(\langle w,x_i\rangle-b)=1-\xi_i \leq 0 và mẫu học bị phân lớp sai.

Tổng kết lại:

  • \displaystyle 0\leq \xi_i < 1: phân lớp đúng (không có lỗi).
  • \displaystyle \xi_i \geq 1: phân lớp sai (có lỗi).

Để ý là, tại mỗi mẫu học \displaystyle x_i, chỉ có thể có khả năng có \displaystyle 1  lỗi hoặc \displaystyle {0} lỗi (còn gọi là hàm lỗi 0-1 – 0-1 loss). Nói cách khác \displaystyle \xi_i là cận trên của số lỗi phân lớp tại mẫu học \displaystyle x_i. Vậy số lỗi trên toàn bộ tập mẫu học có cận trên là

\displaystyle N\{error\} \leq \sum_{i=1}^N \xi_i

Dễ thấy, nếu \displaystyle \sigma \geq 1 thì

\displaystyle N\{error\} \leq \sum_{i=1}^N \xi_i^\sigma

Cận trên của số lỗi

Đồng thời, do tối thiểu hóa \displaystyle \sum_{i=1}^N \xi_i^\sigma tương đương với việc tối thiểu hóa \displaystyle F\left(\sum_{i=1}^N \xi_i^\sigma\right) với \displaystyle F là hàm đơn điệu tăng, người ta có thể chọn một hàm \displaystyle F lồi và đơn điệu tăng bất kì để đưa vào hàm mục tiêu

\displaystyle \frac{1}{2}\|w\|^2 + C F\left(\sum_{i=1}^N \xi_i^\sigma\right)

Như vậy, bài toán quy hoạch với hàm mục tiêu trên vẫn là bài toán quy hoạch lồi với hàm mục tiêu lồi và các ràng buộc tuyến tính. Phương pháp SVM với lề mềm không những tìm siêu phẳng có lề lớn nhất mà còn hướng tới việc tối thiểu hóa xác suất lỗi trên tập mẫu học.

Đăng trong Lý thuyết học máy | Tagged: , , , , , , , , , , | Leave a Comment »

Phân lớp bằng siêu phẳng (1) – Perceptron, tế bào thần kinh nhân tạo

Đăng bởi tqlong on Tháng Bảy 31, 2008

Có lẽ dạng hàm phân lớp đơn giản nhất là hàm tuyến tính (hoặc affine). Hàm phân lớp tuyến tính chỉ cho ranh giới phân lớp là một siêu phẳng. Mặc dù vậy, ứng dụng của dạng hàm phân lớp này vô cùng rộng rãi. Khoảng từ những năm 1990, các thuật toán phân lớp có độ chính xác, tốc độ học và bảo đảm toán học mạnh nhất chính là các thuật toán sử dụng hàm phân lớp tuyến tính. Ví dụ như: mạng các hàm cơ sở dạng bán kính (Radial Basis Functions network – RBF), máy phân lớp sử dụng véctơ hỗ trợ (Support Vector Machines – SVM), v.v… đều là các hàm phân lớp tuyến tính. Trong bài này, ta xét một dạng hàm phân lớp đơn giản, gọi là Perceptron, một trong những tế bào thần kinh nhân tạo đầu tiên.

Hàm phân lớp tuyến tính: Ta biết rằng, hàm phân lớp tuyến tính có ranh giới phân lớp là 1 siêu phẳng, vì vậy nó chỉ phân tách được 2 lớp. Tất nhiên, ta có thể kết hợp nhiều hàm phân lớp lại để phân tách được nhiều lớp hơn. Nhưng trong ví dụ này, ta chỉ xét hàm tuyến tính phân tách \displaystyle \mathbb{R}^n  thành 2 nửa không gian (half-space).

Để cho tiện, ta gán \displaystyle \omega_1 = +1, \omega_2 = -1, luật phân lớp khi sử dụng hàm phân lớp tuyến tính là

\displaystyle f(x)=\theta( \langle w,x\rangle -b)

\displaystyle \theta(t) = \begin{cases}+1 & t\geq 0\\ -1 & t < 0\end{cases}

trong đó, \displaystyle f(x) là hàm phân lớp, \displaystyle \theta(t) là hàm ngưỡng (threshold function), \displaystyle \langle w,x\rangle là tích vô hướng của \displaystyle w,x, \displaystyle w là trọng số (weight) trên các tọa độ/đặc trưng của \displaystyle x, \displaystyle b là ngưỡng (threshold).

Phân lớp bằng siêu phẳng

Như vậy, nửa không gian \displaystyle R_+=\{x|\langle w,x\rangle \geq b\} được phân vào lớp \displaystyle \omega_1=+1, nửa không gian còn lại R_-=\displaystyle \{x|\langle w,x\rangle \geq b\} được phân vào lớp \displaystyle \omega_2=-1. Người ta còn thể hiện hàm phân lớp trên như sau

Perceptron

Perceptron

Với cách thể hiện này, người ta có ý đồ nối các Perceptron lại với nhau để tạo thành một mạng lưới gọi là Mạng nơron nhân tạo (Artificial Neural Networks) giống như hệ thần kinh gồm mạng lưới các tế bào thần kinh của con người. Bây giờ ta sẽ tìm hiểu làm thế nào để huấn luyện một Perceptron.

Bài toán huấn luyện Perceptron phát biểu như sau:

Cho một tập các mẫu học \displaystyle D=\{(x_i,y_i)\}_{i=1}^N với \displaystyle x_i\in \mathbb{R}^n, y_i=\pm 1, tìm giá trị của \displaystyle w,b sao cho

\displaystyle f(x_i) = \theta( \langle w,x_i\rangle -b) = y_i, \forall i=1,\ldots, N

Nếu tồn tại \displaystyle (w,b) như vậy, ta nói tập mẫu học \displaystyle D phân tách tuyến tính được (linear separable).

Do \displaystyle y_i=\pm 1, điều kiện trên tương đương với

\displaystyle y_i (\langle w,x_i\rangle -b) > 0, \forall i=1,\ldots, N

Nếu đặt \displaystyle \gamma = \min_i y_i (\langle w,x_i\rangle -b) thì

\displaystyle y_i (\langle w,x_i\rangle -b) \geq \gamma > 0, \forall i=1,\ldots, N

Như vậy, ta có thể nói tập mẫu học \displaystyle D phân tách tuyến tính được nếu tồn tại \displaystyle (w,b) và \displaystyle \gamma>0 sao cho bất đẳng thức trên đúng với mọi \displaystyle i=1,\ldots, N.

Năm 1957, Rosenblatt đề xuất Perceptron và một thuật toán huấn luyện rất đơn giản. Đến năm 1962, Novikoff chứng minh rằng thuật toán huấn luyện này luôn dừng sau một số hữu hạn bước lặp nếu tập mẫu học phân tách tuyến tính được.

Thuật toán huấn luyện Perceptron: Thuật toán ở dạng trực tuyến (online), ta lần lượt cung cấp cho thuật toán các mẫu học trong \displaystyle D, có thể lặp lại nhiều lần. Mỗi lần có mẫu học mới, thuật toán sẽ chỉnh sửa \displaystyle (w,b) để cố gắng phân lớp được mẫu học này

Bước thứ \displaystyle t: Đầu vào là mẫu học \displaystyle (x_t, y_t)

  1. Nếu \displaystyle f(x_t) = y_t, không làm gì cả vì đã phân lớp đúng.
  2. Nếu \displaystyle f(x_t) \neq y_t (phân lớp sai), tức là

    \displaystyle y_i (\langle w,x_t\rangle - b) \leq 0

    thì cập nhật (update) lại \displaystyle (w,b) như sau

    \displaystyle w^{\mathrm{new}} = w^{\mathrm{old}} + y_t x_t
    \displaystyle b^{\mathrm{new}} = b^{\mathrm{old}} - y_t

  3. Chuyển sang bước thứ \displaystyle t+1.

Để ý là ở bước 2, khi phân lớp sai, giả sử \displaystyle y_t = +1, khi đó ta phải có

\displaystyle \langle w^{\mathrm{old}},x_t\rangle -b^{\mathrm{old}} \leq 0

Sau khi cập nhật, ta có

\displaystyle \langle w^{\mathrm{new}},x_i\rangle -b^{\mathrm{new}} = \langle w^{\mathrm{old}},x_i\rangle -b^{\mathrm{old}} + \langle x_t,x_t\rangle + 1 > \langle w^{\mathrm{old}},x_i\rangle -b^{\mathrm{old}}

Nghĩa là khả năng phân lớp đúng mẫu học \displaystyle (x_t,y_t) sẽ lớn hơn sau khi cập nhật các trọng số \displaystyle (w,b).

Định lý (tính dừng của thuật toán huấn luyện Perceptron): Nếu tập mẫu học \displaystyle D=\{(x_i,y_i)\}_{i=1}^N phân tách tuyến tính được thì thuật toán huấn luyện Perceptron cho ra các trọng số \displaystyle (w,b) phân tách tập mẫu học này sau một số hữu hạn lần cập nhật (bước 2).

Chứng minh: Để cho tiện, ta đặt

\displaystyle W = \left[\begin{array}{cc}w & b\end{array}\right]^T, z = \left[\begin{array}{cc}x & -1\end{array}\right]^T

như vậy \displaystyle \langle W,z\rangle = \langle w,x\rangle -b và cập nhật ở bước 2 tương đương với

\displaystyle W^{\mathrm{new}} = W^{\mathrm{old}} + y_t z_t

Do tập mẫu học \displaystyle D=\{z_i,y_i\}_{i=1}^N phân tách tuyến tính được, phải tồn tại \displaystyle W^* và \displaystyle \gamma>0 sao cho

\displaystyle y_i \langle W^*,z_i\rangle \geq \gamma,\forall i=1,\ldots,N

Giả sử thuật toán bắt đầu với trọng số \displaystyle W_1 = 0 và tại một thời điểm nào đó trong quá trình huấn luyện, thuật toán đã cập nhật trọng số \displaystyle W tất cả \displaystyle K lần, không mất tính tổng quát, giả sử

\displaystyle y_t\langle W_t,z_t\rangle\leq 0, t=1,\ldots,K (phân lớp sai)

\displaystyle W_{t+1} = W_t + y_t z_t, t=1,\ldots,K (cập nhật trọng số)

Suy ra

\displaystyle \|W_{t+1}\|^2 = \|W_t + y_t z_t\|^2 = \|W_t\|^2 + 2y_t\langle W_t,z_t\rangle + \|z_t\|^2 \leq \|W_t\|^2 + \|z_t\|^2

\displaystyle \Rightarrow \|W_{K+1}\|^2 \leq \sum_{i=1}^K \|z_i\|^2 \leq KR^2

trong đó \displaystyle R = \max_t \|z_t\|.

Mặt khác, do \displaystyle W_1 = 0 nên

\displaystyle W_{K+1} = \sum_{i=1}^K y_i z_i\displaystyle \Rightarrow \langle W^*,W_{K+1}\rangle = \sum_{i=1}^K y_i \langle W^*,z_i\rangle \geq K\gamma

Theo bất đẳng thức Swartz: \displaystyle \|x\|^2\|y\|^2\geq \langle x,y\rangle^2 , ta có

\displaystyle \|W^*\|^2\|W_{K+1}\|^2\geq \langle W^*,W_{K+1}\rangle ^2 \geq K^2\gamma^2\displaystyle \Rightarrow \|W_{K+1}\|^2 \geq \frac{K^2\gamma^2}{\|W^*\|^2}

Vậy

\displaystyle \frac{K^2\gamma^2}{\|W^*\|^2} \leq KR^2\displaystyle \Rightarrow K \leq \|W^*\|^2\left(\frac{R}{\gamma}\right)^2

Nghĩa là nếu tồn tại \displaystyle W^* phân cách tập mẫu học, số lần cập nhật \displaystyle K sẽ bị chặn trên.

Nhận xét:

  1. Để ý rằng \displaystyle h_i = \left|\frac{\langle W^*,z_i\rangle}{\|W^*\|}\right| chính là khoảng cách từ điểm \displaystyle z_i đến siêu phẳng phân cách \displaystyle \langle W^*,z\rangle = 0. Do đó

    \displaystyle \gamma = \min_i \{y_i\langle W^*,z_i\rangle\} = h\|W^*\|

    với \displaystyle h = \min_i h_i là khoảng cách nhỏ nhất từ các mẫu học đến siêu phẳng (còn gọi là lề của siêu phẳng – margin). Suy ra

    \displaystyle K \leq \left(\frac{R}{h}\right)^2

    Tức là nếu lề của siêu phẳng \displaystyle h càng lớn thì thuật toán hội tụ càng nhanh (số lần cập nhật càng ít). Hơn nữa, theo lý thuyết VC, \displaystyle h còn liên quan chặt chẽ đến ước lượng xác suất lỗi (generalization error), nếu \displaystyle h càng lớn thì ước lượng càng chính xác.

Lịch sử nghiên cứu mạng nơron nhân tạo:

Định lý trên do Novikoff chứng minh lần đầu tiên vào năm 1962, nó cho thấy có thể dùng một thuật toán cập nhật trọng số rất đơn giản để tìm ra hàm phân lớp tuyến tính nếu tập mẫu học có thể phân tách tuyến tính được. Kết quả này đã khởi nguồn cho phong trào nghiên cứu các phương pháp học máy có mô hình đơn giản tương tự trong những năm 60. Đến năm 1969, một quyển sách nhỏ tựa đề “Perceptrons” của hai nhà khoa học rất có ảnh hưởng lúc đó là Minsky và Papert (giáo sư này bị tai nạn xe máy ở trường Bách Khoa năm 2006) chỉ ra những bài toán phân lớp mà các mô hình học đơn giản này không thể phân lớp được. Hai ông cho rằng, dù các perceptron có được nối lại với nhau thành nhiều tầng, nhiều lớp cũng không thể vượt qua những hạn chế này. Kết quả là suốt thập kỉ 70, nghiên cứu về mạng nơron nhân tạo không được cấp tiền hỗ trợ nghiên cứu. Phải đến năm 1986, với thuật toán lan truyền ngược sai số (error back-propagation), nghiên cứu về mạng nơron mới nở rộ trở lại. Vào năm 1987, Minsky và Papert xuất bản cuốn sách “Perceptrons – Expanded edition” chỉ ra và chỉnh sửa lại những lỗi của lần xuất bản trước.

Đăng trong Lý thuyết học máy | Tagged: , , , , , , , , , , , , , , , , , , , , , , , , , , , , | 4 phản hồi »

« Những bài viết trước