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

Tháng Bảy 2008
T2	T3	T4	T5	T6	T7	CN
« Tháng 4		Tháng 8 »
	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

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

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)$

Nếu $\displaystyle f(x_t) = y_t$ , không làm gì cả vì đã phân lớp đúng.
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$
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:

Để ý 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.

Bài viết này được đăng vào Tháng Bảy 31, 2008 lúc 8:48 chiều và tập tin được lưu ở Lý thuyết học máy. Tagged: xác suất lỗi, generalization error, hàm phân lớp, Support Vector Machines, SVM, hàm tuyến tính, affine, mạng các hàm cơ sở bán kính, Radial Basis Functions network, RBF, máy phân lớp sử dụng véctơ hỗ trợ, perceptron, nửa không gian, half space, trọng số, ngưỡng, weight, threshold, mạng nơron nhân tạo, Artificial Neural Networks, huấn luyện, phân tách tuyến tính, linear separable, Rosenblatt, Novikoff, thuật toán lan truyền ngược sai số, error back-propagation, Minsky, Papert. 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.

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

hoanghuyctm03 đã nói

Tháng Bảy 3, 2009 lúc 5:25 sáng
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!

Trả lời
Khuyen Nguyen đã nói

Tháng Chín 21, 2009 lúc 2:20 sáng
Xin chào, mình đang tìm hiểu SVM, có thể giải thích giúp mình : giả sử ta có các mẫu xi(i=1..n)được phân vào các lớp A,B,C. Nếu như theo những gì mình hiểu thì mình sẽ xây dựng 3 bộ phân lớp SVM( 1 bộ dùng để phân mẫu xi vào lớp A,1 bộ dùng để phân mẫu xi vào lớp B,1 bộ dùng để phân mẫu xi vào lớp C). Vấn đề mình còn mơ hồ là làm thể nào để tạo ra 3 bộ phân lớp đó, sự khác nhau của các bộ phân lớp có phải la bộ (w,b) không ?
-Nếu được xin cho mình một ví dụ cụ thể. Ví dụ, mình có 4 từ “learn, love, the, a” và có 3 lớp “V,adj,Det”, kết quả sao khi phân lớp mình sẽ được V: learn ; adj:love ; Det:the,a. Thì cách xây dựng các bộ phân lớp này sẽ như thế nào khi ta áp dụng SVM( chỉ cần ý tưởng)

Mong sớm nhận được hồi âm
Kính chào.

Trả lời
- tqlong đã nói
  
  Tháng Chín 21, 2009 lúc 6:42 sáng
  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.
  
  Trả lời
Khuyen Nguyen đã nói

Tháng Chín 23, 2009 lúc 5:05 chiều
Xin chào, cám ơn về câu trả lời của bạn.
Cho mình hỏi sâu hơn một chút. Mình đang muốn ứng dụng SVM vào việc gán nhãn từ loại(POS TAGGER). Mình trình bày cách hiểu của mình, anh(chị) xem và cho mình ý kiến(hiểu đúng hay sai)
- SVM này là khả tách tuyến tính linear classified (?)
- Giai đoạn huấn luyện:
+ Chọn khoảng 90% ngữ liệu đã được gán nhãn đúng(lấy từ penntreebank)
+ Lần lượt cho các từ trong ngữ liệu huấn luyện vào trong các bộ phân lớp(ví dụ: C1, C2,…)=> tính w,b(MỤC TIÊU CHÍNH)
(nếu vào bộ phân lớp Noun thì những từ có nhãn là Noun sẽ có giá trị y = 1,ngược lại y = 1)
- Giai đoạn test
+ Lấy 10% ngữ liệu còn lại, gỡ bỏ nhãn.
+ Cũng lần lượt cho qua các bộ phân lớp => xác định từ loại
* Nếu như trong câu “I CAN CAN A CAN” thì từ CAN có 3 từ loại. Trong trường hợp này ta sẽ sử dụng thêm các yếu tố khác(vd: tiền tố, hậu tố, từ đứng trước, từ đứng sau,..) để xác đinh lại từ CAN trong từng trường hợp cụ thể thí nó có từ loại gì trong các từ loại đã được xác định.

Đây là nhận định của mình khi áp dụng SVM cho POS TAGGER. Nếu mình chưa hiểu cặng kẽ vấn đề hay hiểu sai thì xin góp ý.
* Cho mình hỏi them, khi đọc tài liệu có đề 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), mình chưa hiểu lý do tại sao lại có thể giới hạn được như vậy?
Mong nhận được hồi âm
Thân chào

Trả lời

Để lại hồi âm

« Các khái niệm trong Học máy (Machine Learning) (7) – Một số ví dụ

Phân lớp bằng siêu phẳng (2) – Sử dụng các đại lượng thống kê (linear discriminant analysis) »

	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

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

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

hoanghuyctm03 đã nói

Khuyen Nguyen đã nói

tqlong đã nói

Khuyen Nguyen đã nói

Để lại hồi âm