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

Learn & Enjoy …

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

Posted by Trần Quốc Long 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)hàm phân lớp, \displaystyle \theta(t)hàm ngưỡng (threshold function), \displaystyle \langle w,x\rangle tích vô hướng của \displaystyle w,x, \displaystyle wtrọng số (weight) trên các tọa độ/đặc trưng của \displaystyle x, \displaystyle bngưỡ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)\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^*\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ẳngmargin). 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.

4 phản hồi to “Phân lớp bằng siêu phẳng (1) – Perceptron, tế bào thần kinh nhân tạo”

  1. hoanghuyctm03 said

    xin chào, mình đang làm bài liên quan đến phân lớp điểm trên mặt phẳng theo mô hình perceptron, có thể giúp mình giải thích về thuật toán perceptron cụ thể ko? Thank!

  2. Khuyen Nguyen said

    Xin chào, mình đang tìm hiểu SVM, có thể giải thích giúp mình : giả sử ta có các mẫu xi(i=1..n)được phân vào các lớp A,B,C. Nếu như theo những gì mình hiểu thì mình sẽ xây dựng 3 bộ phân lớp SVM( 1 bộ dùng để phân mẫu xi vào lớp A,1 bộ dùng để phân mẫu xi vào lớp B,1 bộ dùng để phân mẫu xi vào lớp C). Vấn đề mình còn mơ hồ là làm thể nào để tạo ra 3 bộ phân lớp đó, sự khác nhau của các bộ phân lớp có phải la bộ (w,b) không ?
    -Nếu được xin cho mình một ví dụ cụ thể. Ví dụ, mình có 4 từ “learn, love, the, a” và có 3 lớp “V,adj,Det”, kết quả sao khi phân lớp mình sẽ được V: learn ; adj:love ; Det:the,a. Thì cách xây dựng các bộ phân lớp này sẽ như thế nào khi ta áp dụng SVM( chỉ cần ý tưởng)

    Mong sớm nhận được hồi âm
    Kính chào.

    • tqlong said

      Sự khác nhau giữa 2 bộ phân lớp chính là (w, b), hoặc nếu bạn dùng (alpha) thay cho (w,b) thì khác nhau ở (alpha).

      Có 2 cách:
      – Cách 1: Xây dựng 3 bộ phân lớp như bạn nói, gọi tên là C1, C2, C3. C1 phân lớp giữa A và “không phải A”, C2 phân lớp giữa B và “không phải B”, C3 phân lớp giữa C và “không phải C”.
      Trong ví dụ của bạn, các mẫu học cho C1 sẽ là
      V: learn
      not V: love, the, a

      Các mẫu học cho C2 là
      adj: love
      not adj: V, the, a

      Các mẫu học cho C3 là:
      Det: the, a
      not Det: learn, love

      Cách 2: Xây dựng 3 bộ phân lớp tách 2 lớp từng đôi một.

  3. Khuyen Nguyen said

    Xin chào, cám ơn về câu trả lời của bạn.
    Cho mình hỏi sâu hơn một chút. Mình đang muốn ứng dụng SVM vào việc gán nhãn từ loại(POS TAGGER). Mình trình bày cách hiểu của mình, anh(chị) xem và cho mình ý kiến(hiểu đúng hay sai)
    – SVM này là khả tách tuyến tính linear classified (?)
    – Giai đoạn huấn luyện:
    + Chọn khoảng 90% ngữ liệu đã được gán nhãn đúng(lấy từ penntreebank)
    + Lần lượt cho các từ trong ngữ liệu huấn luyện vào trong các bộ phân lớp(ví dụ: C1, C2,…)=> tính w,b(MỤC TIÊU CHÍNH)
    (nếu vào bộ phân lớp Noun thì những từ có nhãn là Noun sẽ có giá trị y = 1,ngược lại y = 1)
    – Giai đoạn test
    + Lấy 10% ngữ liệu còn lại, gỡ bỏ nhãn.
    + Cũng lần lượt cho qua các bộ phân lớp => xác định từ loại
    * Nếu như trong câu “I CAN CAN A CAN” thì từ CAN có 3 từ loại. Trong trường hợp này ta sẽ sử dụng thêm các yếu tố khác(vd: tiền tố, hậu tố, từ đứng trước, từ đứng sau,..) để xác đinh lại từ CAN trong từng trường hợp cụ thể thí nó có từ loại gì trong các từ loại đã được xác định.

    Đây là nhận định của mình khi áp dụng SVM cho POS TAGGER. Nếu mình chưa hiểu cặng kẽ vấn đề hay hiểu sai thì xin góp ý.
    * Cho mình hỏi them, khi đọc tài liệu có đề cập ngữ liệu huấn luyện(Giới hạn lại bộ mẫu huấn luyện từ 635000 trong ngữ liệu còn 20000 mẫu huấn luyện), mình chưa hiểu lý do tại sao lại có thể giới hạn được như vậy?
    Mong nhận được hồi âm
    Thân chào

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: