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

Learn & Enjoy …

Phân lớp bằng siêu phẳng (3) – Mạng hàm cơ sở bán kính (Radial Basis Function networks)

Posted by Trần Quốc Long on Tháng Tám 2, 2008

Trong bài này, ta tìm hiểu một cách mở rộng hàm phân lớp tuyến tính gọi là mạng hàm cơ sở bán kính (Radial Basis Functions networks – RBF). Động lực thúc đẩy RBF phát triển là:

  1. Hàm phân lớp tuyến tính đơn thuần (Perceptron) không thể phân lớp trong một số trường hợp. Ví dụ như hàm XOR: \displaystyle \{(0,0),(1,1)\}\in\omega_1,\{(1,0),(0,1)\}\in\omega_2.
  2. Khả năng nhớ các mẫu học: nếu đầu vào của hàm phân lớp “gần giống” với một mẫu học đã biết trước đó thì kết quả phân lớp cũng phải “gần giống” kết quả phân lớp đã được học.
  3. Ý tưởng phân lớp trên không gian có nhiều chiều hơn: có nhiều ví dụ cho thấy, khi được ánh xạ lên không gian nhiều chiều hơn lúc đầu, bài toán phân lớp trở nên dễ dàng hơn.

Hàm bán kính (Radial function): Hàm bán kính là hàm chỉ phụ thuộc vào khoảng cách từ đối số \displaystyle x đến một điểm \displaystyle c (gọi là tâm) cho trước

\displaystyle \phi(x) = \phi(\|x-c\|) = \phi(r)

với \displaystyle r = \|x-c\|.

Một số hàm bán kính:

  • Hàm Gaussian: \displaystyle \phi(r) = \exp\{-\beta r^2\}.
  • Hàm đa thức:

    \displaystyle \phi(r) = r^{2k+1}
    \displaystyle \phi(r) = r^{2k} \ln r

  • Khoảng cách:

    \displaystyle \phi(r) = \sqrt{r^2+\beta^2}

Mạng hàm cơ sở bán kính (RBF): Giả sử ta có \displaystyle D tâm \displaystyle c_1,\ldots,c_D, khi đó mạng hàm cơ sở bán kính là tổ hợp tuyến tính của các hàm bán kính tại các tâm này

\displaystyle f(x) = \sum_{i=1}^D w_i \phi(\|x-c_i\|)

Nhận xét:

  1. Mạng hàm cơ sở bán kính đã tạo ra ánh xạ

    \displaystyle \Phi:\mathbb{R}^n\rightarrow \mathbb{R}^D

    với \displaystyle \Phi(x) = \left[\begin{array}{ccc}\phi(\|x-c_1\|)&\ldots&\phi(\|x-c_D\|\end{array}\right]^T.

  2. Kết quả của mạng là

    \displaystyle f(x) = \langle W,\Phi(x)\rangle

    vì vậy, đây là hàm tuyến tính phân lớp dữ liệu trên không gian \displaystyle \mathbb{R}^D.

  3. Mạng RBF còn có thể dùng để xấp xỉ hàm số nếu ta trực tiếp dùng đầu ra \displaystyle y(x).

Huấn luyện mạng RBF: Với tập mẫu học \displaystyle D=\{(x_i,y_i)\}_{i=1}^N ta phải tìm các tham số của mạng bao gồm: trọng số \displaystyle W=(w_1,\ldots,w_D)^T, tâm của các hàm bán kính \displaystyle C=\{c_1,\ldots,c_D\}, tham số của các hàm bán kính \displaystyle B=\{\beta_1,\ldots,\beta_D\}.

Hàm sai số (error function): Để xác định các tham số của mạng, ta phải đưa ra một tiêu chí đánh giá các tham số này khi áp dụng mạng RBF trên tập mẫu học \displaystyle D. Một tiêu chí đánh giá hay dùng là hàm tổng bình phương sai số

\displaystyle e_2(W, C, B) = \sum_{i=1}^N (y_i - f(x_i))^2

Lưu ý: Hàm tổng bình phương sai số hay được sử dụng vì thuận tiện trong tính toán đạo hàm. Gần đây, người ta nhận ra một số nhược điểm của loại hàm sai số này và có xu hướng chuyển sang các hàm sai số khác (mặc dù tính toán phức tạp hơn nhiều). Ví dụ, hàm tổng sai số tuyệt đối

\displaystyle e_1(W, C, B) = \sum_{i=1}^N \|y_i - f(x_i)\|

hoặc hàm sai số tuyệt đối lớn nhất

\displaystyle e_\infty(W, C, B) = \max_i\|y_i - f(x_i)\|

Trường hợp \displaystyle B,C cố định: Ta cần giải bài toán tối ưu

\displaystyle \min_W e_2(W) = \sum_{i=1}^N \left(y_i - \sum_{j=1}^D w_j \phi(\|x_i-c_j\|)\right)^2

Nếu ta đặt \displaystyle Y=(y_1,\ldots,y_N)^T

\displaystyle \Phi = \left[\begin{array}{c}\Phi(x_1)^T\\ \vdots\\ \Phi(x_N)^T\end{array}\right] = \left[\begin{array}{ccc}\phi(\|x_1-c_1\|)& \ldots & \phi(\|x_1-c_D\|)\\ \ldots & \ldots &\ldots \\ \phi(\|x_N-c_1\|)& \ldots & \phi(\|x_N-c_D\|)\end{array}\right]

thì bài toán trên tương đương với

\displaystyle \min_W e_2(W) = \|Y-\Phi W\|_2^2

Đây là bài toán tối thiểu bình phương sai số kinh điển. Trường hợp \displaystyle \Phihạng đầy đủ (full rank), giá trị tối ưu của \displaystyle W

\displaystyle W^* = \arg\min_W e_2(W) = (\Phi^T\Phi)^{-1}\Phi^TY

trong đó \displaystyle \Phi^+ = (\Phi^T\Phi)^{-1}\Phi^T gọi là ma trận giả nghịch đảo (pseudo-inverse). Trong thực hành, người ta không dùng ma trận giả nghịch đảo mà sử dụng biến đổi Gauss để giải (giống như giải hệ phương trình tuyến tính). Một đặc điểm nữa của \displaystyle W^* theo công thức trên là

\displaystyle \|W^*\| = \min_W \{\|W\|: e_2(W) = e_2(W^*)\}

nghĩa là \displaystyle W^* là vectơ có độ dài nhỏ nhất trong các véctơ \displaystyle W tối thiểu hóa \displaystyle e_2(W). Đặc điểm này có ý nghĩa lớn vì nó làm tăng tính ổn định của hệ thống (không làm \displaystyle f(x) quá lớn).

Trường hợp \displaystyle C=\{x_1,\ldots,x_N\}: Nghĩa là tâm của các hàm bán kính chính là các mẫu học. Khi đó, ma trận \displaystyle \Phi là ma trận vuông, ta có giá trị tối ưu của trọng số

\displaystyle W^* = \Phi^{-1}Y

Tất nhiên, trong thực hành, người ta không tính nghịch đảo của \displaystyle \Phi mà dùng biến đổi Gauss để giải phương trình \displaystyle \Phi W = Y.

Trường hợp \displaystyle B,C cũng là tham số cần tìm: Ta cần giải bài toán tối ưu

\displaystyle \min_W e_2(W,B,C) = \sum_{i=1}^N \left(y_i - \sum_{j=1}^D w_j \phi(\|x_i-c_j\|,\beta_j)\right)^2

Do hàm sai số này không còn là hàm lồi, cách giải quyết thường dùng là sử dụng phương pháp xuống đồi theo véctơ đạo hàm. Khi đó, người ta lấy đạo hàm của \displaystyle e_2(W, B,C) theo các biến \displaystyle W,B,C rồi chỉnh lại các tham số này. Một cách tối ưu hóa khác là:

  1. Cố định \displaystyle B, C, tính \displaystyle W theo phương pháp trên.
  2. Cố định \displaystyle W, chỉnh sửa \displaystyle B,C theo phương pháp đạo hàm.
  3. Lặp bước 1,2.

Trong thực hành, người ta thấy việc tìm \displaystyle B,C rất mất thời gian. Do đó, các tâm \displaystyle C thường được chọn là chính các mẫu học. Còn đặt giá trị \displaystyle \beta_1 = \beta_2 = \ldots = \beta_D = \beta sau đó chọn thử một vài giá trị \displaystyle \beta đến khi đạt được kết quả như ý.

Ví dụ 1: Hàm XOR

\displaystyle \begin{array}{ll}x_1=(0,0)&y_1 = -1\\ x_2=(1,1) & y_2 = -1 \\ x_3=(0,1)& y_3 = +1 \\ x_4=(1,0) & y_4 = +1\end{array}

Giả sử ta chọn \displaystyle \phi(r) = \exp\{-r^2\}, các tâm chính là các mẫu học, khi đó ma trận \displaystyle \Phi

\displaystyle \Phi = \left[\begin{array}{ccc}\phi(\|x_1-x_1\|)& \ldots & \phi(\|x_1-x_4\|)\\ \ldots & \ldots &\ldots \\ \phi(\|x_4-x_1\|)& \ldots & \phi(\|x_4-x_4\|)\end{array}\right] = \left[\begin{array}{cccc}1.0000&0.1353&0.3679&0.3679\\{0.1353}&1.0000&0.3679&0.3679\\{0.3679}&0.3679&1.0000&0.1353\\{0.3679}&0.3679&0.1353&1.0000\end{array}\right]

\displaystyle W = \Phi^{-1}Y = \left[\begin{array}{cccc}-2.5027 & -2.5027 & 2.5027 & 2.5027\end{array}\right] ^T

Thế \displaystyle W mới tìm được vào hàm \displaystyle f(x):

\displaystyle f(x) = \langle W,\Phi(x)\rangle

ta có thể tính được \displaystyle f(x) như trong hình sau

Xấp xỉ hàm XOR bằng mạng RBF

Để ý rằng tại các mẫu học, mạng RBF cho kết quả chính xác: \displaystyle f(x_i)=y_i, i=1,2,3,4.

Ví dụ 2: Vẫn xấp xỉ hàm XOR nhưng ta dùng ít tâm hơn

\displaystyle \begin{array}{l}c_1=(0,0)\\ c_2=(1,0)\\ c_3=(0.5,1)\end{array}

Ta có

\displaystyle \Phi = \left[\begin{array}{ccc}\phi(\|x_1-c_1\|)& \phi(\|x_1-c_2\| & \phi(\|x_1-c_3\|)\\ \ldots & \ldots &\ldots \\ \phi(\|x_4-c_1\|)& \phi(\|x_4-c_2\| & \phi(\|x_4-c_3\|)\end{array}\right] = \left[\begin{array}{ccc}1.0000&0.3679&0.2865\\{0.1353}&0.3679&0.7788\\{0.3679}&0.1353&0.7788\\{0.3679}&1.0000&0.2865\end{array}\right]

\displaystyle W = (\Phi^T\Phi)^{-1}\Phi^TY = \left[\begin{array}{ccc}-0.8808 &0.8808 &0.0000 \end{array}\right] ^T

Với trọng số \displaystyle W này, đồ thị của hàm \displaystyle f(x)=\langle W,\Phi(x)\rangle như sau

Xấp xỉ hàm XOR bằng mạng RBF với 3 tâm

Như vậy, nếu số tâm ít hơn số mẫu học, mạng có thể không học được toàn bộ tập mẫu học. Tuy nhiên, ở những vị trí mẫu học gần tâm, kết quả phân lớp vẫn chính xác.

Xác định số tâm của mạng: Ta thấy ở ví dụ trên, số tâm của mạng ảnh hưởng đến chất lượng xấp xỉ hàm số. Để xác định số tâm người ta thường làm như sau:

  1. Bắt đầu với số tâm bằng \displaystyle D=0 hay \displaystyle f(x) = 0,\forall x
  2. Tính sai số \displaystyle e(x_i) = \|y_i-f(x_i)\|^2, \forall i và chọn

    \displaystyle i_{\mathrm{max}} = \arg\max_i e(x_i)

  3. Thêm một tâm \displaystyle D\leftarrow D+1, c_D = x_{i_{\mathrm{max}}}
  4. Tính trọng số \displaystyle W của mạng mới và giá trị hàm sai số

    \displaystyle e_2(W,C) = \sum_{i=1}^n \|y_i-f(x_i)\|^2

  5. Dừng nếu \displaystyle e_2(W,C) < \epsilon cho trước, ngược lại, quay về bước 2.

Chi tiết thuật toán trên có thể xem trong bài báo của S. Chen, C. F. N. Cowan, and P. M. Grant, “Orthogonal Least Squares Learning Algorithm for Radial Basis Function Networks“, IEEE Transactions on Neural Networks, Vol 2, No 2 (Mar) 1991. Ý tưởng chính là:

  1. Mỗi lần thêm 1 tâm vào mạng tức là ta thêm 1 cột mới vào ma trận \displaystyle \Phi.
  2. Dùng biến đổi QR (Gram-Schmidt QR decomposition) để trực giao hóa cột mới thêm vào (lưu ý là không gian cột của \displaystyle \Phi vẫn giữ nguyên).
  3. Lợi dụng tính trực giao của các cột để tính sai số \displaystyle e(x_i).

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: