Giáo trình Xử lý ảnh - Chương 12: Mạng thần kinh nhân tạo cho phân lớp màu sắc

Chương 12 mạng thần kinh nhân tạo cho phân lớp màu sắc 12.1 Chỉ dẫn Không nghi ngờ gì nữa, con người là cách tốt nhất để phân loại màu sắc. Tuy nhiên, các ứng dụng đòi hỏi sự phân loại màu trực tuyến và sửa lại tín hiệu sắc màu một cách có lựa chọn như trong tín hiệu truyền hình màu, thay thế cho sự phân lớp của con người là cần phải có. May mắn thay, một nhóm các kiểu phân loại được mô hình hoá theo kiểu trí tuệ sinh vật (hệ thống thần kinh nhân tạo) đã được phát triển và nghiên cứu trong một thời gian dài. Mục tiêu của các nghiên cứu này là đạt được tới mức giống như con người. Chúng ta chưa đạt được mục tiêu này. Sự thách thức là chúng ta phải hiểu được bằng cách nào mà một loạt các tác động thần kinh đem lại cho chúng ta khả năng nhìn, nghe, cảm giác, chuyển động... Mặc dù chúng ta đã có những hiểu biết đúng đắn cấu tạo của tổ chức bộ não con người, chúng ta vẫn không hiểu một cách đầy đủ bằng cách nào mà con người có thể có một loạt các chức năng như vậy. Khả năng học hỏi và thích nghi của con người vẫn còn là một điều bí ẩn. Một trích dẫn rất đáng quan tâm, "Tôi đã để lại các dấu hiệu như một bằng chứng về sự tồn tại của tôi, cái nào trong số các dấu hiệu này bạn phản đối? Tôi đã tạo ra con người, tôi đã dạy [lập trình] cho họ có khả năng nhận biết..." (Kinh Coran, Suret Al-Rahman). Con người nhận ra họ có khả năng phát minh ra các công cụ ngay từ khi họ mới được tạo ra. Phần lớn các sáng tạo của con người đều dựa trên ham muốn tìm hiểu trong lĩnh vực vật lý. Bằng tất cả các khám phá, con người lại quay trở về để tìm hiểu chính bản thân mình. Cùng với sự ra đời của phần mềm, tự động hoá, phỏng sinh học ta đã có thể mô phỏng một số chức năng của con người qua các phần cứng và phần mềm mô phỏng. Giống như khi bắt đầu, hệ thống thần kinh nhân tạo vẫn chưa mô phỏng được dạng thức con người; tuy nhiên, các cấu trúc này có rất nhiều ứng dụng hữu ích. Một trong những ứng dụng sẽ trình bày ở phần dưới đây là phân lớp màu sắc. Trong chương này chúng ta sẽ xem xét một loạt các mô hình thần kinh nhân tạo, cách thức nhận thức của chúng, và hiệu quả trong phân lớp màu. 12.2 Hệ thống thần kinh sinh vật Mắt cảm nhận ánh sáng xung quanh chúng ta và chuyển chúng thành các xung điện, sau đó đưa về bộ nhớ qua các dây thần kinh. Tại phía sau của mắt, một lưới dây thần kinh từ giác mạc tạo thành các dây thần kinh cảm quang. Hai lưới dây thần kinh cảm quang gặp nhau tại một miền có tên là giao thoa thị giác (optic chiasm). Tại miền này hai dây tạo thành một lưới, và được chia làm hai vùng cảm quang đi tới bên trái và bên phải của não. Tất cả các miền này mang tín hiệu từ hai mắt, và não tổng hợp được hình ảnh thực sự. Vùng của não cho các đáp ứng của hình ảnh gọi là vỏ não thị giác (Hình 12.1). Nếu mỗi vùng của não nhận được hai ảnh của vật thể, mỗi ảnh lấy từ một mắt với một góc nhìn khác nhau nhỏ thì kết quả ta sẽ nhận được một hình ảnh ba chiều hay còn gọi là hình ảnh nổi. Tại não, một số khổng lồ các liên lạc của các tế bào thần kinh tạo ra xử lý thông tin. Hình 12.1 Các đường thị giác của bộ não. Hình 12.2 là một sơ đồ đơn giản hoá của tế bào thần kinh. Nó bao gồm một tế bào (soma) với dây thần kinh vào (dendrites) và dây thần kinh ra (axons). Các dây thần kinh vào nhận các tín hiệu kích thích hoặc các tín hiệu kiềm chế. Các tín hiệu kích thích làm tăng và các tín hiệu kiềm chế làm chậm khả năng phát tín hiệu của thần kinh. Các dây thần kinh ra đưa tín hiệu đến một tế bào khác. Thông tin được chuyển qua các hình hành cuối khớp thần kinh (synaptic-end bulbs) và nhận bởi dây thần kinh vào thông qua vùng chuyển tiếp. Hình hành cuối khớp thần kinh và vùng chuyển tiếp được chia ra bằng một lỗ hở vào khoảng một phần triệu inch, và chuyển tiếp tín hiệu qua lỗ hổng này bởi cơ chế hoá điện (hình 12.3). Phần cuối hành và miền chuyển tiếp được gọi là khớp thần kinh (synapse). Tín hiệu đi trong dây thần kinh vào và dây thần kinh ra như một dòng điện. Có rất nhiều kiểu dây thần kinh trong não và một số lớn các tế bào trạng thái và chức năng. Một số hạn chế các xung mà có khả năng làm quá tải mạch cảm biến. Một số đưa tin tức tổng hợp đến bề mặt não, một số khác nhận tín hiệu đưa vào. Các hành ở khớp thần kinh chứa các túi nhỏ bé gọi là các túi khớp thần kinh (hình 12.3). Mỗi túi chứa hàng ngàn các phân tử gọi là chuyển tiếp thần kinh (neurotransmitter). Khi một tín hiệu thần kinh đến hành của khớp thần kinh, các túi hợp nhất với màng, làm tràn các chất chứa bên trong vào các lỗ của khớp thần kinh. Các chuyển tiếp thần kinh gắn chặt với các phần tử tiếp nhận ở tâm của tế bào; làm mở các tuyến tiếp nhận và cho phép các ion natri đi vào trong tâm tế bào và các ion kali đi ra. Dòng của các ion kích thích các màng của tâm tế bào và tạo ra xung điện trong tế bào trung tâm. Hình 12.2 Sơ đồ đơn giản hoá của tế bào thần kinh. Hình 12.3 Các khớp thần kinh. Con người có vào khoảng xấp xỉ 1011 tế bào thần kinh, ước lượng có khả năng thực hiện trên 100 tỷ phép tính một giây. Một siêu máy tính Cray X_MP, một loại máy tính nhanh nhất hiện nay, có khả làm được 0.8 tỷ phép tính một giây. Con người nhanh hơn 100 lần bất kỳ một loại máy tính hiện đại nào, với ưu điểm hơn hẳn về kích thước nhỏ gọn và đòi hỏi ít hơn hẳn năng lượng. Một tính chất cũng cần phải nói tới là bộ não con người được thiết kế để xử lý ba chiều. Trong khi đó, các mạch tích hợp thường là hai chiều, và với sự tiến bộ ngày nay việc thiết kế mạch tích hợp ba chiều vẫn chưa được hoàn thiện hoặc thậm chí cũng không gần được như kiểu tích hợp ba chiều của bộ não con người. 12.3 Perceptron Hình 12.4 giới thiệu cái mà người ta tin rằng đó là mô hình thuật toán học cho một tế bào thần kinh đơn lẻ. Chú ý là có N đầu vào, cung cấp giá trị ngưỡng q..., và cho kết quả đi qua một hàm phi tuyến. Tín hiệu ra có thể là giá trị 1 kích thích cho một dây thần kinh, hoặc là 0 (-1 cũng có thể được dùng). Hàm phi tuyến hay được dùng là hàm xichma và hàm giới hạn (logic ngưỡng). Cấu trúc trong hình 12.4 gọi là perceptron, và là cơ sở cho một cách phân lớp tuyến tính mà có thể chia ra làm hai lớp tách rời nhau như trong hình 12.5. Tín hiệu ra từ perceptron có thể viết dưới dạng (12.1) ở đây (12.2) Một sơ đồ xác định các trọng số {w0, w1, w2, ..., wN} và có hàm f(a) chia thành hai lớp A và B phân biệt gọi là sơ đồ nhận thức. q gọi là giá trị ngưỡng, và thường nằm trong khoảng 0 đến 1. Xuất phát từ sơ đồ nhận thức, chúng ta sẽ xem xét một perceptron chỉ có hai đầu vào: (12.3) x0 ký hiệu cho đặc điểm màu x của sơ đồ màu, x1 là đặc điểm màu y. Nếu chúng ta muốn perceptron phân biệt hai màu A và B, chúng ta sẽ chờ đầu ra cho giá trị 1 nếu (x0,x1) thuộc về màu A, và 0 nếu đầu vào thuộc B. Theo các giả thiết trên chúng ta có thể viết: nếu (x0, x1) ẻ A dP = 1 nếu (x0, x1) ẻ B dP = 0 ở đây ký hiệu p biểu thị cho một mẫu của (x0, x1) và dP biểu thị cho đáp ứng mong muốn cho mẫu này. Nếu (w0, w1) đã biết thì đáp ứng ra thực sự y có thể tính từ biểu thức (12.1). Sai số cho việc đọc mẫu này có thể cho bởi (12.4) Hình 12.4 Các phần tử tính toán của một hệ thống thần kinh. Hình 12.5 Một hàm phân chia đơn giản của một lớp. Vấn đề cần giải quyết là tối thiểu hoá EP đối với w0 và w1 cho tất cả các mẫu lấy vào (x0,x1)P. Biểu thức (12.1) cung cấp sự phân chia chính xác giữa hai lớp màu như trong hình (12.5). EP là hàm phi tuyến của các biến w0 và w1 và vì vậy các giản đồ phi tuyến cần được sử dụng để tối thiểu hoá nó. Nếu y cho bởi hàm xichma và sau đó nếu lấy vi phân EP theo w0 ta được: và theo w1 ta được : Thuật toán rút ra giá trị của các trọng số theo các bước sau: 1.Cho các trọng số (w0, w1) và q các giá trị ngẫu nhiên nhỏ. Tại bước lặp thứ k: 2. Cho một giá trị đầu vào (x0, x1) và chọn giá trị đầu ra theo ý thích: 1 nếu thuộc về một lớp màu và 0 nếu thuộc về lớp màu còn lại. 3. Tính tín hiệu ra thực sự y. 4. Tính 5. Tính các gradient 6. Thay đổi các trọng số dùng biểu thức : ở đây Wk = [ w0 w1](k) = các trọng số tại bước lặp thứ k và h là một phân số dương nhỏ hơn 1. 7. Cho đầu vào giá trị mới hoặc nếu dữ liệu đã được đọc tất cả, đọc lại tập các giá trị của dữ liệu. Quay lại bước 2 và lặp lại cho đến khi hàm trọng số thoả mãn, cụ thể là i= 0 ,1. Hội tụ trong một số trường hợp sẽ nhanh hơn nếu xung lượng (moment) được cộng thêm vào và trọng số được làm giảm đi bởi: ở đây 0 < a <1. Thuật toán trên gọi là quy tắc "delta", được dùng rộng rãi trong tài liệu. Mặc dù thuật toán trên có thể tính trọng số cho các lớp, nhưng nó đòi hỏi một số rất lớn các phép lặp để hội tụ. Việc chọn hai tham số a và h có vẻ như là tuỳ ý. Để cho bạn có thể kiểm tra thuật toán quy tắc delta chúng tôi cho ở dưới đây một chương trình C thiết kế cho một perceptron với hai đầu vào. Chương trình 12.1 “PERECEPT.C” Perceptron học nhận thức bằng quy tắc denlta /*Program 12.1 "PERECEPT.C". Perceptron learning using the delta rule. */ /************************************ * Developed by M.A.Sid_Ahmed. * * ver. I.O. 1992. * * @ 1994 * *************************************/ /* Teaching a single pereptrjon using the delta rule. */ #include #include #include #include #include #include #define eta 0.8 #define alpha 0.2 void main() { unsigned int d[200]; unsigned int N,ind,iter,i; float w[2],x[2],x1[200],x2[200],net,E; float dEp[2],sum,y,theta,dEp_old[2],delta; FILE *fptr; char file_name[14]; clrscr(); N=0; iter=0; gotoxy(1,1); printf("Enter file name containing data -->"); scanf("%s", file_name); fptr=fopen(file_name,"r"); if(fptr==NULL) { printf("file %s does not exist.",file_name); exit(1); } while((fscanf(fptr,"%f %f %d ",&x1[N], &x2[N],&d[N])!=EOF)) N++; fclose(fptr); srand(1); w[0]=(float)rand()/32768.00; srand(2); w[1]=(float)rand()/32768.00; theta=0.1; i=0; sum=0.0; ind=1; gotoxy(1,10); printf("Press ESC to exit before convergence."); while(ind) { x[0]=x1[i]; x[1]=x2[i]; gotoxy(1,3); printf("Iteration # %5d ",iter); net=w[0]*x[0]+w[1]*x[1]+theta; if(net>=20) E=0.0; else E=exp(-(double)net); y=1.0/(1.0+E); delta=(d[i]-y)*y*(1.0-y); dEp[0]=x[0]*delta; dEp[1]=x[1]*delta; if(i==0) { w[0]+=eta*dEp[0]; w[1]+=eta*dEp[1]; dEp_old[0]=dEp[0]; dEp_old[1]=dEp[1]; } else { w[0]+=eta*dEp[0]+alpha*(dEp[0]-dEp_old[0]); w[1]+=eta*dEp[1]+alpha*(dEp[1]-dEp_old[1]); dEp_old[0]=dEp[0]; dEp_old[1]=dEp[1]; } sum+=fabs((double)(d[i]-y)); i++; if(i>=N) { gotoxy(1,6); printf(" Square error= %f",sum); i=0; sum=0; iter++; } if(d[i]==1) gotoxy(1,4); else gotoxy(1,5); printf("%d %f", d[i],y); if((i==N)&&(sum<=1.0e-1)) { gotoxy(1,7); printf("\n w[0]=%f W[1]=%f",w[0], w[1]); exit(1); } if(kbhit()!=0) { gotoxy(1,7); if(getch()==27) { printf("\n w[0]=%f w[1]=%f",w[0],w[1]); exit(1); } } } } Trên đĩa đi kèm đã có sẵn file dữ liệu có tên là "TINT.DAT" rút ra từ sơ đồ màu. Dùng h = 0.8 và a = 0.2, phải mất gần 200 lần lặp để làm cho sai số giảm từ ằ28 xuống ằ9,55. Sau 15,000 phép lặp sai số đã giảm xuống nhỏ hơn 1 và tiếp tục giảm xuống. Thay h = 0.2 và a = 0.8 sự hội tụ sẽ chậm hơn. Trước khi chúng ta nghiên cứu một phương pháp tốt hơn cho tính toán giá trị cảm nhận, chúng tôi sẽ cung cấp cho bạn công cụ thu nhập dữ liệu. 12.4 Thu nhập dữ liệu cho các lớp màu sắc Chương trình cho ở dưới đây chỉ làm việc trên vỉ mạch ATI PIB đã được đề cập đến trong chương 11. Bạn có thể sửa đổi làm cho nó tương thích với các phần cứng thông dụng; các sửa đổi này không có gì là khó khăn lắm. Chương trình này có sử dụng chuột. Nếu bạn có vỉ mạch ATI PIB , đầu tiên bạn cần nạp một ảnh trên màn hình PIB. Chạy chương trình và con trỏ sẽ xuất hiện trên màn hình. Dùng chuột, thay thế con trỏ trên sắc màu mà bạn muốn tách ra (một perceptron đơn thì sẽ không thể tách ra được một sắc màu; chúng ta sẽ đề cập đến việc tách các sắc màu ở phần cuối chương này). Lấy rất nhiều các giá trị từ một loạt các điểm trên miền đã lựa chọn sắc màu bằng cách nhắp đơn nút trái chuột. Chú ý là màn hình VGA sẽ hiện lên biểu đồ màu và cường độ màu tại nơi mà bạn trỏ tới. Nơi mà bạn kích vào sẽ đánh dấu bằng một dấu thập màu đỏ trên biểu đồ màu vẽ trên màn hình VGA (xem hình 12.6) và lưu nó vào một mảng. Nếu bạn muốn dời dấu thập đi chỗ khác trong trường hợp các điểm nhập vào lớn hơn một, thì nhắp nút trái chuột nhiều lần. Hành động này sẽ làm dời đi rất nhiều điểm tuỳ theo bạn chọn (bắt đầu từ điểm cuối cùng) từ biểu đồ màu và lưu trong mảng. Khi bạn ấn ESC, con trỏ sẽ xuất hiện trên màn hình VGA. Đưa con trỏ vào sơ đồ màu vẽ trên màn hình VGA, bằng cách kích lại nút trái chuột ta sẽ thu được dữ liệu cho một lớp màu khác. Nhắp nút trái chuột, như trước đây, sẽ làm dịch chuyển đến đầu vào cuối cùng. Chú ý rằng một dấu thập màu xanh sẽ xuất hiện bất cứ khi nào bạn nhắp trái chuột, và sẽ bị dời đi khi bạn nhắp phải chuột. Nhấn ESC để thoát. Bạn sẽ được hỏi tên file cho chứa dữ liệu. Dữ liệu được lưu trữ bao gồm 3 số: số đầu tiên biểu diễn cho x, số thứ hai biểu diễn cho y, và số cuối cùng xác định lớp. Giá trị lớp này được gán bằng 1 trong trường hợp lựa chọn sắc màu và 0 trong các trường hợp còn lại. Dữ liệu được cho dưới dạng "%f%f%d". Kết quả ta thu được là một cung màu trên biểu đồ màu được tách ra từ phần còn lại của phổ màu. Hình 12.6 Thu thập dữ liệu cho phân lớp màu sắc. Chương trình 12.2 “COLORRDM.C”. Chương trình thu thập dữ liệu; Được dùng với PIB. /************************************ * Developed by M.A.Sid_Ahmed. * * ver. 1.0, 1992. * * @ 1994 *************************************/ /* Program to read color from PIB screen. It also classifies color according to colors in Chromaticity diagram. Use mouse left button to enter x.y coordinates and right button to erase as many previous entries as you wish. The cursor will initially point to the PIB screen, use the mouse to enter the tone you wish to classify as one color set. Press ESC to exit from PIB screen. The cursor mouse will appear on VGA screen. Use mouse to point at points in the Chromaticity diagram that do not belong to the set of colors you wish to classify. Use left button to enter a point, right button to erase previous entry or entries. Press ESC again to exit and store data. */ #include #include #include #include #include #include #define white (circ<0) #define green (l[0]&&l[6]) #define yellow ((!l[0])&&l[1]) #define skin_tone ((!l[1])&&l[2]) #define red ((!l[2])&&l[3]) #define magenta ((!l[3])&&l[4]) #define blue ((!l[4]&&(!l[53)) #define cyan (l[5]&&(!l[6])) #define ESC 0x1B #define LBUTTON 0x01 #define RBUTTON 0x02 void make_cursor(int,int); void find_color(int,int); void move_cursor(int,int); void get_video_mode(int *,int *); void set_video_mode(int); void mouse_cursor_on(void); void mouse_cursor_off(void); void read_mouse(int *, int *, int *); void draw_line(int,int,int,int,int); void draw_circle(int,int,int,int); void set_pixel(int,int,int); void mouse_vrange(int,int); void mouse_hrange(int,int); void set_mouse(int,int); void CIE(void); void draw_cross(float,float,int); int kount=-1; float xold[200],yold[200]; int set[200]; void main() { int mode,page,row,col,button,ind,i; float x,y; char ch,file_name[14]; FILE *fptr; clrscr(); InitPIB(); SetScreen(0); SetInDispMode(); get_video_mode(&mode,&page); set_video_mode(0x12); CIE(); for(i=0;i<100;i++) read_mouse(&row,&col,&button); row=100; col=200; set_mouse(row,col); read_mouse(&row, &col, &button); gotoxy(1,18); make_cursor(col, row); find_color(col, row); move_cursor (col, row); mouse_vrange(5,480); mouse_hrange( 5,640); mouse_cursor_on(); ind=1; while(ind) { for(i=0;i<100;i++) read_mouse(&row,&col,&button); gotoxy(1,19); printf("row_%d, col_%d",row,col); if(button==LBUTTON) { delay(150); x=((float)col-200.0)/400.0; y=(400.0-(float)row)/250.0; gotoxy(1,15); printf("x=%f y=%f ",x,y); draw_cross(x,y,GREEN); if(kount<200) kount++; else { gotoxy(1,4); printf("Max. total number data points should not exceed 200.\n"); } xold[kount]=x; yold[kount]=y; set[kount]=0; gotoxy(1,3); printf("x=%f y=%f set=%2d total number of points=%4d", xold[kount],yold[kount],set[kount],kount); } else if(button==RBUTTON) { delay(150); draw_cross(xold[kount],yold[kount],BLACK); if(kount>-1) kount--; gotoxy(1,3); printf("x=%f y=%f set=%2d total number of points=%4d", xold[kount],yold[kount],set[kount],kount); } if(kbhit()!=0) { if(getch()==ESC) ind=0; } } gotoxy(1,5); printf("Do you wish to save data? (y or n)-->"); while(((ch=getch())!='y')&&(ch!='n')); switch(ch) { case 'y': printf("\n Enter file name -->"); scanf("%s",file_name); ind=access(file_name,0); while(!ind) { printf("File exists. Wish to overwrite? (y or n)-->"); while(((ch=getch())!='y')&&(ch!='n')); switch(ch) { case 'y': ind=1; break; case 'n': gotoxy(1,6); printf("\n Enter file name --> "); scanf("%s",file_name); ind=access(file_name,0); } } fptr=fopen(file_name,"w"); for(i=0;i<kount;i++) fprintf(fptr,"%f %f %d ", xold[i],yold[i],set[i]); break; case 'n': break; } fclose(fptr); set_video_mode(mode); } /* Routine to draw cursor on PIB screen. */ void make_cursor(x,y) int x,y; { int i,j; unsigned value=0xffff; for(i=x-5;i<x+6;i++) PutPixel(&value,i,y,1); for(j=y-5;j<y+6;j++) PutPixel(&value,x,j,1); } #define sqr(x) ((x)*(x)) /* Routine to read and classify colors from PIB screen. */ void find_color(x1,y1) { unsigned int color,R,G,B; float X,Y,Z,D,x,y; int row,col,button; float m[]={3.3600, 1.260274, 0.663317, -1.029762, -61.75, 0.384, -0.875}; float c[]={-0.785880, -0.086671, 0.112116, 0.675911, 20.89575, 0.205128, 0.624375}; float r=0.01; float lt,circ; int l[7], i; GetPixel(&color,x1,y1); B=(0x001F & color); G=(0x03E0 & color)>>5; R=(0x7C00 & color)>>10; gotoxy(1,1); printf(" blue= %5u, oreen=%5u, red=%5u ",B,G,R); if(R+G+B) { X=2.769*R+1.7518*G+1.1300*B; Y=R+4.5907*G+0.0601*B; Z=0.0565*G+5.5943*B; D=X+Y+Z ; x=X/D; y=Y/D; circ=sqr(x-0.333)+sqr(y-0.333)-sqr(r); for(i=0;i<7;i++) { lt=m[i]*x+c[i]-y; if(lt<0.0) l[i]=1; else l[i]=0; } gotoxy(1,2); printf("Color is:"); if(white) { gotoxy(11,2); printf("white. "); } else if(green) { gotoxy(11,2); printf("green. "); } else if(yellow) { gotoxy(11,2); printf("yellow. "); } else if(skin_tone) { gotoxy(11,2); printf("Skin tone."); } else if(red) { gotoxy(11,2); printf("red. "); } else if(magenta) { gotoxy(11,2); printf("magenta. "); } else if(blue) { gotoxy(11,2); printf("blue. "); } else if(cyan) { gotoxy(11,2); printf("cyan. "); } for(i=0;i<100;i++) read_mouse(&row,&col,&button); if(button==LBUTTON) { delay(150); if(kount<200) kount++; else { gotoxy(1,4); printf("Max. total number data points should not exceed 200.\n"); } draw_cross(x,y,RED); xold[kount]=x; yold[kount]=y; set[kount]=(char)1; gotoxy(1,3); printf("x=%f y=%f set=%2d total number of points=%4d", xold[kount],yold[kount],set[kount],kount); } else if(button==RBUTTON) { delay(150); gotoxy(1,3); printf("x=%f y=%f set=%2d total number of points=%4d", xold[kount],yold[kount],set[kount],kount); draw_cross(xold[kount],yold[kount],BLACK); if(kount>-1) kount--; } } else { gotoxy(11,2); printf("black. "); } } /* Routine to translate mouse movements to PIB screen. */ void move_cursor(x,y) int x,y; { int ind,row,col,button; char ch; mouse_vrange(5,250); mouse_hrange(5,500); ind=1; while (ind) { make_cursor(x,y); read_mouse(&row,&col,&button); x=col; y=row; make_cursor(x,y); find_color(x,y); if(kbhit()!=0) { ch=getch(); if(ch==ESC) { make_cursor(x,y); ind=0; } } } } /* Routine to obtain video mode and active page. */ void get_video_mode(int *display_mode,int *active_page) { union REGS reg; reg.h.ah=0x0F; int86(0x10,®,®); *display_mode=reg.h.al; *active_page=reg.h.bh; } /* Routine to change to one of the VGA/EGA modes. */ void set_video_mode( int set_mode) { union REGS reg; reg.h.ah=0x00; reg.h.al=set_mode; int86(0x10,®,®); } /* Routine to draw a straight line of any standard color to join two end points (xl,yl) and (x2,y2) using Bresenham's algorithm. */ void draw_line(x1,y1,x2,y2,color) { int dx,dy,x,y,x_end,y_end,p,const1,const2,ind; /* Bresenham's line algorithm. */ dx=abs(x1-x2); dy=abs(y1-y2); if((dx==0)&&(dy==0)) { set_pixel(x1,y1,color); return; } else if(dy==0) { if(x1>x2) { x_end=x1; x=x2 ; } else { x_end=x2; x=x1; } while(x<=x_end) { set_pixel(x,y1,color); x++; } return; } else if(dx==0) { if(y1>y2) { y_end=y1; y=y2; } else y_end=y2 ; y=y1; } while(y<=y_end) { set_pixel(x1,y,color); y++; } return; } else { if(dy<=dx) { if(x1>x2) { x_end=x1; y_end=y1; x=x2; y=y2; } else { x=x1; y=y1; x_end=x2; y_end=y2; } if(y_end>y) ind=1; else ind=0; p=2*dy-dx; const1=2*dy; const2=2*(dy-dx); set_pixel(x,y,color); while((x < x_end)) { x++; if(p<0) p+=const1; else { if(ind) y++; else y--; p+=const2; } set_pixel(x,y,color); } set_pixel(x,y,color); } else { if(y1>y2) { x_end=x1; y_end=y1; x=x2; y=y2; } else { x_end=x2; y_end=y2; x=x1; y=y1; } if(x_end>x) ind=1; else ind=0; p=2*dx-dy ; const1=2*dx; const2=2*(dx-dy); set_pixel(x,y,color); while((y < y_end)) { y++; if(p<0) p+=const1; else { if(ind) x++: else x--; p+=const2; } set_pixel(x,y,color); } set_pixel(x,y,color); } } } /* Routine to draw a circle of any color given the radius, land cent re. It uses Bresenham's algorithm for circle drawing . */ void draw_circle(int x_centre, int y_centre, int radius,int color) { int p,x,y; x=0; y=radius; p=3-2*radius; while(x<y) { set_pixel(x_centre+x,y_centre+y,color); set_pixel(x_centre-x,y_centre+y,color); set_pixel(x_centre+x,y_centre-y,color); set_pixel(x_centre-x,y_centre-y,color); set_pixel(x_centre+y,y_centre+x,color); set_pixel(x_centre-y,y_centre+x,color); set_pixel(x_centre+y,y_centre-x,color); set_pixel(x_centre-y,y_centre-x,color); if(p<0) p+=4*x+6; else { p+=4*(x-y)+10; y--; } x++; } if (x==y) { set_pixel(x_centre+x,y_centre+y,color); set_pixel(x_centre-x,y_centre+y,color); set_pixel(x_centre+x,y_centre-y,color); set_pixel(x_centre-x,y_centre-y,color); set_pixel(x_centre+y,y_centre+x,color); set_pixel(x_centre-y,y_centre+x,color); set_pixel(x_centre+y,y_centre-x,color); set_pixel(x_centre-y,y_centre-x,color); } } /* Routine to set a pixel on the VGA screen to any of the standard colors.*/ void set_pixel(int x,int y, int color) { union REGS reg; reg.h.ah=0x0c; reg.h.al=color; reg.h.bh=0; reg.x.cx=x; reg.x.dx=y: int86(0x10,®,®); } /* Routine to turn on cursor mouse on the VGA screen. */ void mouse_cursor_on(void) { union REGS reg; reg.x.ax=0x01; int86(0x33,®,®); } /* Routine to turn off cursor mouse on the VGA screen.*/ void mouse_cursor_off(void) { union REGS reg; reg.x.ax=0x02; int86(0x33,®,®); } /* Routine to read mouse row and column location. It also provides mouse button status.*/ void read_mouse( int *row, int *col, int *button ) { union REGS reg: reg.x.ax=0x03; int86(0x33,®,®); *button=reg.x.bx; *col=reg.x.cx; *row=reg.x.dx; } /* Routine to set vertical range for mouse. */ void mouse_vrange(int min, int max) { union REGS reg; reg.x.ax=0x08; reg.x.cx=min; reg.x.dx=max; int86(0x33,®,®); } /* Routine to set horizontal range for mouse. */ void mouse_hrange(int min, int max) { union REGS reg; reg.x.ax=0x07; reg.x.cx=min; reg.x.dx=max; int86(0x33,®,®); } /* Routine to move mouse cursor to a specified location. */ void set_mouse(int row, int col) { union REGS reg; reg.x.ax=0x04; reg.x.cx=col; reg.x.dx=row; int86(0x33,®,®); } /* Routine to draw the chromaticity diagram on the VGA screen. */ #define xxp(x) (int)((x)*400.0+200.0) #define yyp(y) (int)(400.0-(y)*250.0) float xx[]={ 0.7347, 0.2757, 0.1661 }; float yy[]={ 0.2653, 0.7147, 0.0094 }; struct coord { float xc; float yc; }; struct coord p[7]={ { 0.408, 0.585 }, {0.479, 0.517}, {0.532, 0.465},{ 0.501, 0.160 }, {0.337, 0.086}, {0.208, 0.285}, {0.229, 0.424 }}; struct coord w={0.333, 0.333}; void CIE(void) { float x1,Y1,x2,y2; int i,radius; x1=xxp(xx[0]); y1=yyp(yy[0]); x2=xxp(xx[1]); y2=yyp(yy[1]); draw_line(x1,y1,x2,y2,LIGHTGRAY); x1=x2; y1=y2; x2=xxp(xx[2]); y2=yyp(yy[2]); draw_line(x1,y1,x2,y2,LIGHTGRAY); x1=x2; y1=y2; x2=xxp(xx[0]); y2=yyp(yy[0]); draw_line(x1,y1.x2,y2,LIGHTGRAY); x1=xxp(w.xc); y1=yyp(w.xc); for(i=0;i<7;i++) { x2=xxp(p[i].xc); y2=yyp(p[i].yc); draw_line(x1,y1,x2,y2,LIGHTGRAY); } radius=(int)((xxp(((float)(w.xc)+0.01))-x1)+0.5); draw_circle(x1,y1,radius,LIGHTGRAY); } /* Routine to draw a cross on the VGA screen. */ void draw_cross( float x. float y, int color) { int xx,yy; xx=xxp(x); yy=yyp(y); draw_line(xx-2,yy-2,xx+2,yy+2,color); draw_line(xx-2,yy+2,xx+2,yy-2,color); } 12.5 Dạy nhận biết bằng phương pháp tối thiểu hoá hàm sai lệch tổng Quy tắc delta như chúng ta đã chứng kiến, là sơ đồ lặp hội tụ rất chậm. Sự lựa chọn giá trị của a và h quyết định tốc tốc độ hội tụ. Phép hội tụ này chậm, đòi hỏi hàng trăm phép lặp, và để giải quyết hết các vấn đề thì số phép lặp lên đến hàng nghìn. Một perceptron có hai đầu vào và vì vậy có hai trọng số có thể thay đổi được, phần tử mà tự nó có thể chia được hai lớp màu riêng biệt nhau, đòi hỏi một số lượng phép tính như trong trường hợp phân chia lớp màu trong file "TINT.DAT". Nếu tất cả các phép tính này cần thoả mãn cho một bài toán đơn giản như vậy, thì bạn tưởng tượng điều gì sẽ xảy ra nếu chúng ta dùng phương pháp này để dạy cho một cấu trúc thần kinh đa chức năng. Vấn đề cấp thiết đặt ra là phải tìm cách để đảm bảo sự hội tụ xảy ra với tốc độ nhanh hơn. Yêu cầu thực tế bây giờ là phải tối thiểu hoá, và đòi hỏi cho sự tối thiểu hoá này là hàm sai lệch tổng: (12.5) ở đây di là đáp ứng ra mong muốn cho các mẫu Xi = [ x0, x1,..., xN-1], và yi là đáp ứng ra thực sự cho cùng các mẫu đầu vào này. Nếu yi là một hàm phi tuyến của trọng số có thể thay đổi được : W = [ w0 , w1, ... , wN], vấn đề trở thành bài toán tối thiểu hoá một hàm phi tuyến. Vì vậy, chúng ta sẽ tìm kiếm các phương pháp từ phạm vi phi tuyến đã được chứng minh để có kết quả trong việc giải quyết các vấn dề tương tự. 12.5.1 Phương pháp tìm kiếm bất biến Một phương pháp hay dùng nhất để rút ra giá trị nhỏ nhất của một hàm đơn biến là phương pháp tỷ lệ vàng (Golden Section). Phương pháp này dựa trên một giản đồ loại trừ miền, và giả thiết rằng hàm chỉ có một giá trị nhỏ nhất trong một miền xác định trước. Hàm như thế gọi là hàm đơn điệu. Giản đồ loại trừ miền trong trường hợp tổng quát có thể giải thích bằng biểu đồ như trong hình 12.7. Hình 12.7 Sơ đồ loại trừ miền. Trong hình 12.7, nếu hai điểm được chọn trong miền giữa w0 và w1, và nếu y2 > y1 thì rõ ràng giá trị cực tiểu nằm giữa w1 và a2. Vì vậy, miền [a2, w2] có thể loại trừ khỏi vùng tìm kiếm. Nếu hai điểm khác được lựa chọn trong miền nhỏ hơn và phép xử lý được lặp lại, miền tìm kiếm sẽ bị co hẹp lại. Cuối cùng, giá trị nhỏ nhất được thu hẹp nằm trong một vùng rất nhỏ. Một câu hỏi đặt ra: Bằng cách nào chúng ta chọn được các điểm nằm bên trong này? Một câu hỏi khó hơn nữa sẽ là: Có điều kiện gì cho việc tìm kiếm một dãy các điểm này để giá trị nhỏ nhất thu hẹp trong một vùng có độ rộng 2e sau một số xác định các bước? Câu trả lời cho vấn đề này đã được Kiefer tìm ra vào năm 1953. Cách tìm kiếm lần lượt được biết dưới tên tìm kiếm Fibonacci. Phép tìm kiếm này dựa trên dãy số nguyên do Fibonacci đưa ra vào thế kỉ 13. Một phương pháp tìm kiếm không đòi hỏi toàn bộ dãy số nguyên Fibonacci được đưa ra dưới tên là tìm kiếm tỷ lệ vàng (Golden Section). Chứng minh của phương pháp này vẫn chưa được trình bày trong cuốn sách này; nhưng bởi vì nó đơn giản và tôi đoán chắc là bạn muốn tìm hiểu, nên tôi sẽ trình bày với bạn phần chứng minh: Chúng ta sẽ giả sử rằng việc tìm kiếm cho tìm kiếm Fibonacci sẽ tiến hành trên miền chuẩn hoá [0, 1]. Dãy số nguyên Fibonacci được định nghĩa bằng các biểu thức: F0 = F1 = 1 (12.6) Fn = Fn-1 + Fn-2 n = 2,3,... Nếu N các giá trị hàm được dùng để tính e, nếu chúng ta đã bắt đầu lùi từ phía sau kết quả và chuyển dịch về phía trước tới đầu miền trong khi mở rộng miền trong tất cả các bước giới thiệu dưới đây Hình 12.8 Tìm kiếm Fibonacci. LN = 2 e = F2 e LN-1 = 3 e = F3 e (12.7) LN-2 = 5 e = F4 e . . . L2 = FN e L1 = FN+1 e ở đây Li là khoảng cách trong lần lặp thứ i, và Fk, k = 2, 3, ..., N+1 là các số Fibonacci. Nếu khoảng cách đầu tiên là [0,1] thì biểu thức cuối cùng của (12.7) có thể viết thành hoặc và vì thế, nếu e được cho, thì N có thể xác định từ tương tự, nếu N đã được cho, thì một kết quả lớn hơn không được mong đợi. Các bước thực hiện của tìm kiếm Fibonacci rất đơn giản. Hai giá trị hàm ban đầu được xác định tại a2 = L2 = FNe và a1 = 1 - L2 = 1 - FNe. Dựa trên kết quả, khoảng cách giữa [0,a1] hoặc [a2,1] được loại trừ và một điểm mới được lấy ra trong phần đối xứng khoảng cách còn lại với sự lưu tâm đến điểm bên trong. Bước xử lý này được lặp lại cho đến khi tất cả N giá trị hàm đã được xác định. Tìm kiếm tỷ lệ vàng được tính từ tìm kiếm Fibonacci. Nếu và thì Giả sử L2 được chọn từ giả thuyết rằng một số lớn các giá trị hàm sẽ được tạo ra (thậm chí ngay cả khi chúng ta không có ý định tạo ra chúng). Hãy xấp xỉ L2 bằng . Vì thế Cho N lớn hoặc (12.8) Trong khoảng [0,1], điểm bắt đầu tìm kiếm là a1 = 1 – 0.618 = 0.382 và a2 = 0.618, không phụ thuộc vào N hoặc e. Tỷ lệ được biết trong toán học và kiến trúc cổ điển dưới tên tỷ lệ vàng (Golden Section). Nó chia một đoạn thành hai phần, làm cho một tỷ lệ rất lớn của đoạn ban đầu tương đương tỷ lệ nhỏ hơn. Vì lý do này nên kỹ thuật loại trừ này gọi là kỹ thuật tìm kiếm tỷ lệ vàng. Thuật toán cho tìm kiếm tỷ lệ vàng bây giờ có thể trình bày bằng các bước sau: 1. Xác định hai điểm w1 và w2 mà chứa điểm giá trị nhỏ nhất (w1 > w2). 2. Tính L = w2 - w1, a2 = 0.618L + w1, và a1 = w1 + w2 - a2 (tham khảo hình 12.7). 3. Tính tol = w2 - w1; 4. Nếu tol < e thì dừng lại. 5. Tính y1 = f(a1) và y2 = f(a2). 6. Nếu y1 a2 thì loại trừ miền [w1,a2], cụ thể, w1 = a2 và a2 = w1 + w2 - a1. Nếu y1 < y2 và a1 < a2 thì loại trừ miền [a2, w2], cụ thể, w2 = a1 và a2 = w1 + w2 - a1. Nếu y1 > y2 và a1 > a2 thì loại trừ miền [a1, w2], cụ thể, w2 = a1 và a1 = w1 + w2 - a2. Nếu y1 > y2 và a1 < a2 thì loại trừ miền [w1,a1], cụ thể, w1 = a1 và a1 = w1 + w2 - a1. 7. Chuyển tới bước ba . Bài tập 12.1 Lập một chương trình C cho tìm kiếm tỷ lệ vàng. Kiểm tra chương trình theo các hàm dưới đây: f(x) = 6.0 - 11x + 6x2 - x3 (Trả lời : 1.42256 cho khoảng [0,2]) f(x) = (100 - x)2 (Trả lời : 100) f(x) = ex - 3x2 - 2e-2x (Trả lời : 2.8316) Một phương pháp đòi hỏi ít các giá trị hàm hơn phương pháp tỷ lệ vàng được phát triển bởi Powell. Cơ sở của phương pháp này dựa trên đánh giá bậc hai liên tiếp. Phương pháp đánh giá bậc hai cho rằng một khoảng giới hạn một hàm có thể xấp xỉ bởi một hàm bậc hai. Giá trị cực tiểu của hàm bậc hai này dùng như đánh giá đầu tiên cho giá trị nhỏ nhất của hàm. Giá trị cực tiểu này cùng với hai điểm nữa dùng để tính ra một xấp xỉ tốt hơn, và cứ tiếp tục như vậy. Cuối cùng, giá trị cực tiểu của hàm bậc hai sẽ xấp xỉ giá trị nhỏ nhất thực sự trong giới hạn sai số nào đó. Phương pháp xấp xỉ bậc hai có thể mô tả bằng các bước sau: Cho ba điểm liên tiếp nhau x1, x2, x3 và giá trị hàm tương ứng của nó f1, f2, f3 chúng ta xác định ba hằng số của hàm bậc hai q(x) = a0 + a1(x-x1) + a2(x-x1)(x-x2) (12.9) Vì f1 = f(x1) = q(x1) = a0 chúng ta có a0 = f1 (12.0) Vì f2 = f(x2) = q(x2) =f1 + a1 (x2 - x1) chúng ta có (12.11) Cuối cùng tại x = x3 (12.12) Để rút ra giới hạn cực đại (hoặc cực tiểu) chúng ta lấy vi phân q(x) theo x và cho biểu thức này bằng 0. Giải biểu thức trên theo biến x chúng ta rút ra giá trị đánh giá (12.13) Chú ý rằng giá trị nhỏ nhất rút ra nếu (12.14) Thuật toán Powell dùng để đánh giá bậc hai liên tiếp được cho bởi Powell. Tuy nhiên, nếu như a2 bằng 0 thì hàm này không thể xấp xỉ bằng hàm bậc hai. Một phương pháp bao gồm tìm kiếm tỷ lệ vàng và xấp xỉ bậc hai liên tiếp được cho bởi Brent. Phương pháp của Brent được dùng cho hàm nhiều biến cho ở phần kế tiếp dưới đây. 12.5.2 Thu hẹp giá trị nhỏ nhất Không có phương pháp nào dùng các phần trên là không có bước thu hẹp giá trị nhỏ nhất lúc ban đầu. Một lưu đồ do Swann phát triển được tôi lựa chọn để dùng. Phương pháp này được trình bày tốt nhất qua các thuật toán dưới đây. 1. Lựa chọn giá trị ban đầu x0 và một bước nhỏ dx. 2. Tính x1 = x0 + dx y1 = f(x0) y2 = f(x1) 3. Nếu y1 ³ y0 thì cho dx = -dx và tính x1 = x0 + dx y1 = f(x1) 4. Tính dx = 2.0 * dx x2 = x1 + dx y2 = f(x2) 5. Lặp lại các bước dưới đây cho đến khi y2 > y1 dx = 2.0 * dx x0 = x1 y0 = y1 x1 = x2 y1 = y2 x2 = x1 + dx y2 = f(x2) 6. Miền thu gọn là (x0,x1) 12.5.3 Phương pháp tối thiểu hoá hàm nhiều biến Có một số kỹ thuật có hiệu quả cho tối thiểu hoá một hàm nhiều biến. Phương pháp mà hay được dùng sẽ xác định một hướng tìm kiếm trong không gian nhiều chiều. Tiếp theo, một phép xấp xỉ một biến sẽ xác định giá trị tối thiểu dọc theo hướng này. Mỗi lần một giá trị tối thiểu được tìm thấy, một hướng mới được tìm tìm thấy và quá trình tìm kiếm lại bắt đầu lại từ đầu. Điều này tiếp tục cho đến khi đạt được hội tụ. Quy tắc delta mô tả ở phần trên có liên hệ với một kỹ thuật gọi là sự hạ thấp dốc nhất. Tuy nhiên, vẫn chưa có một kết quả nào được tạo ra để đưa ra một sự tìm kiếm đơn biến dọc theo sự hạ thấp dốc nhất. Một sự khác biệt nữa là các mẫu được cho lần lượt tại từng thời điểm bằng sự sửa lại các trọng số. Trong sơ đồ hay được dùng nhất thì điều này không xảy ra, tất cả các mẫu được cung cấp cho chương trình để tính một hướng tìm kiếm thuận tiện nhất. Bởi vì đây không phải là một quyển sách tối ưu, nên tôi sẽ trình bày với các bạn tất cả các phương pháp tối ưu hoá cho hàm nhiều biến. Nhưng tôi sẽ chỉ trình bày với bạn hai phương pháp mà tôi thấy có kết quả nhất. Phương pháp đầu tiên mà tôi trình bày được phát triển bởi Fletcher và Reeves gọi là phương pháp gradient kết hợp. Gradient kết hợp là một hướng cơ sở được thiết kế dùng để tối thiểu hoá một hàm bậc hai đầy đủ có N biến sau đúng N bước. Một phương pháp khác được phát triển bởi Daviđon, Fletcher, Reeves. Phương pháp này thường hay được dùng để tối thiểu hoá các hàm có số biến lớn. Bạn sẽ không cần phải hiểu các chứng minh của các thuật toán này khi áp dụng. Nếu bạn muốn tìm hiểu thêm, tôi đề nghị bạn hãy tìm đọc các cuốn sách được xuất bản gần đây nhất về tối ưu hoá. Tiếp theo tôi sẽ trình bày hai thuật toán này. Chúng ta sẽ giả thiết rằng hàm N biến được tối thiểu hoá cho dưới dạng y = f(x0,x1,x2,...,xN-1) = f(X) và X = [ x0 x1 x2 ... xN-1] Phương pháp gradient kết hợp Fletcher-Reeves. 1. Chọn các giá trị ban đầu cho X = [x0 x1 x2 ... xN-1], và đặt biến đếm số lần lặp bằng không, ví dụ, iter = 0. Chọn số lần lặp lớn nhất cho phép. 2. Tính 3. Đặt S = = [s0 s1 s2 ... sN-1] 4. Tính Nếu test < e thì hội tụ đã đạt được, trả lại giá trị X và ra khỏi chương trình. 5. Đặt ẹfp = ẹf. 6. Tối thiểu hoá, dùng một giả thiết không biến, các hàm sau theo a 7. Sửa lại X = X + aS. 8. Tính ẹf(X). 9. Cập nhật giá trị của S dùng: 10. Nếu cho i bất kỳ , đặt S = -ẹf, ví dụ , dùng sự hạ thấp dốc nhất. 11. Tính iter = iter + 1 12. Nếu (iter < số lớn nhất của phép lặp cho phép) thì chuyển tới bước 4, nếu không thì trả lại giá trị X và thoát ra khỏi chương trình. Phương pháp Davidon-Fletcher- Powell. Chúng ta coi rằng hàm N biến được tối thiểu cho bởi y = f(x0, x1 , x2, ..., xN-1) = f(X). Thuật toán này bao gồm các bước: 1. Chọn các giá trị ban đầu cho X = [x0 x1 x2 ... xN-1], và đặt biến đếm số lần lặp bằng 0, ví dụ, iter = 0. Chọn số lần lặp lớn nhất cho phép. 2. Tính 3. Đặt S = -ẹf = [s0 s1 s2 ... sN-1]. 4. Thiết lập ma trận H đồng nhất N ´ N phần tử, ví dụ H = I. 5. Tính Nếu test < e thì hội tụ đã đạt được, trả lại giá trị X và ra khỏi chương trình. 6. Đặt ẹfp = ẹf. 7. Để tối thiểu hoá, dùng một phương pháp một biến cho hàm dưới đây theo biến a 8. Thay X = X + aS. 9. Tính ẹf(X). 10. Tính Y = ẹf - ẹfp. 11. Cập nhật giá trị của H dùng các biểu thức dưới đây: 12. Tính S = -Hẹf. 13. Nếu cho i bất kỳ, đặt S = -ẹf, cụ thể, dùng quãng dốc nhất. 14. Tính iter = iter +1. 15. Nếu (iter < giá trị lớn nhất của số lần lặp cho trước) thì quay về bước 5, nếu không thì trả lại giá trị X và ra khỏi chương trình. Cho cả hai phương pháp trên thì a có thể rút ra bằng kỹ thuật tìm kiếm hàng của Brent. Để dùng các lưu đồ này, gradient của hàm cần tính sẽ phải được tính. Các gradient này được cho bởi (12.15) và (12.16) Xấp xỉ gradient kết hợp dùng hàm sai lệch tổng chỉ đòi hỏi 36 lần lặp để đạt được hội tụ. Giá trị ban đầu được cho ngẫu nhiên và kết quả là w0= 0.010559, w1= 0.021119, và q được chọn là 0.1. Giá trị sai lệch ban đầu của hàm là 7.3. Sau 36 lần lặp sai số giảm xuống 0.000134 và kết quả cho bởi w0 = 115.72, w1 = -104.03, và q = 0,1. Nhắc lại là quy tắc delta yêu cầu 15,000 phép lặp để sai số giảm xuống nhỏ hơn một một ít. Từ đây, ta có thể lựa chọn mà không nghi ngờ gì một kỹ thuật khi dạy một hệ thống thần kinh nhiều lớp. 12.6 Perceptron nhiều lớp Một perceptron đơn lẻ với hai đầu vào có thể biểu diễn dưới dạng sơ đồ bằng một đường thẳng chia hai lớp (Hình 12.5). Rõ ràng, để vây quanh một miền trong hệ thống hai đầu vào (2-D sysem) đòi hỏi ít nhất ba đường thẳng (Hình 12.9). Điều này dẫn chúng ta một cách tự nhiên đến sơ đồ perceptron hai lớp cho trong hình (12.10). Hệ thống này bao gồm một lớp đầu vào, một lớp bị che khuất và một lớp đầu ra. Không khó khăn lắm để chỉ ra rằng cho một hệ thống ba đầu vào (3-D system) cần ít nhất bốn mặt dùng để bao kín miền, ví dụ, bốn perceptron hoặc nút sẽ phải cần tới trong lớp bị che khất. Tổng quát, cho một siêu không gian N chiều, (N + 1) siêu mặt phẳng sẽ cần để bao kín miền được cho, N + 1 perceptron hoặc nút được cần trong lớp bị che khuất. Một miền lồi là một miền mà trong nó bất cứ đường nào nối các điểm trên đường bao của miền cũng chỉ đi qua những Hình 12.9 Miền được bao quanh. Hình 12.10 Perceptron ba lớp. Hình 12.11 Các kiểu khác nhau của miền quyết định. Hình 12.12 Mạng ba lớp tổng quát. điểm trong phạm vi miền đó. Một perceptron ba lớp, nói một cách khác, có thể chia thành các miền tuỳ ý và có thể tách thành các lớp khớp nhau như trong hình 12.11. Hình 12.12 miêu tả một phần tử hệ thống cảm nhận ba lớp. Các quan hệ nối liền nhau không được thể hiện để làm cho sơ đồ không bị phức tạp. Chúng ta sẽ nhận được các đạo hàm theo các trọng số cho trường hợp ba lớp. Chúng ta sẽ tính các biểu thức trong trường hợp tổng quát, sau đó chúng ta cũng áp dụng các biểu thức này perceptron hai lớp. Sau đây chúng tôi sẽ cung cấp cho các bạn file nguồn cho một chương trình tổng quát tính có thể dùng cho một hệ thống có kích thước bất kỳ. Tất nhiên là một ví dụ cũng được cho theo kèm. Các trọng số được đánh số là wijl , ở đây i = vị trí nút trong lớp l - 1 j = vị trí nút trong lớp l Tổng của các tín hiệu vào vào bất kỳ nút nào được ký hiệu là netil, ở đây i = vị trí nút trong lớp l +1 . Tín hiệu ra của từ bất kỳ nút nào trong mạng được ký hiệu là yil, ở đây i = vị trí nút trong lớp l+1. Từ sơ đồ hình 12.12 chúng ta có thể viết hàm sai lệch tiếp theo: (12.17) Để rút ra đạo hàm của E theo các trọng số chúng ta sẽ bắt đầu với các trọng số cung cấp cho lớp ra. Bởi thế, Chúng ta có thể viết Cho nên Bằng định nghĩa (12.18) chúng ta có thể viết: (12.19) Đạo hàm của E theo các trọng số cung cấp cho lớp ẩn thứ hai có thể rút ra theo: Bây giờ Công thức cuối cùng được đưa ra như sau: Bởi vậy Bằng định nghĩa (12.20) Chúng ta có thể trình bày (12.21) Bằng cách sử dụng các phép toán trên chúng ta có thể rút ra đạo hàm của E theo các trọng số cung cấp cho lớp bị che khuất đầu tiên. Chúng được cho theo các biểu thức sau đây: (12.22) (12.23) Tổng quát, cho một hệ thống nhiều lớp chúng ta có thể suy ra từ các biểu thức trên các tập hợp tiếp theo. Nếu lớp cuối cùng là L, thì và và Chú ý rằng nếu hàm f(net) là hàm xichma chúng ta có thể thay Tập hợp cuối cùng có thể dùng để phát triển một chương trình C cho "đào tạo" một mạng nhiều lớp. Nếu các đạo hàm được tính bằng cách đầu tiên xem xét lớp ra và làm việc quay trở lại với lớp vào, phương pháp tính các đạo hàm này được gọi là phương pháp lan truyền ngược (Back-propagation). Lan truyền ngược cũng chỉ ra rằng sai lệch ở tín hiệu ra sẽ lan truyền trở lại tới tín hiệu vào. Chương trình dưới đây dùng phương pháp gradient kết hợp kèm theo phương pháp của Brent tìm kiếm tuyến tính để tập luyện cho một hệ thống thần kinh với một số bất kỳ lớp ẩn và nút. Giải thuật thu gọn, mô tả ở phần trước cũng được sử dụng. Chương trình 12.3 “PERNCONJG.C” /*Program 12.3 "PERNCONJG.C". Training a multilayer neural network using the conjugate gradient method.*/ /************************************ * Developed by M.A.Sid-Ahmed. * * ver. 1.0, 1992. * * @ 1994 * *************************************/ /* Program for training a multi -layer perceptron using the conjugate gradient method.*/ void conj_grad( float (*)(float *), void (*)(float *, float *, int), float *, int, float, float, int); float fun(float *); void dfun(float *, float *,int) #include #include #include #include #include #include int M,*NL,*NS,L; int *d; float *xp,*y,*net,*delta,theta; void main() { float *w,q,xt; int i,j,N,xd,ind,Nt; char file_name[14],file_name2[14],ch; FILE *fptr,*fptr2; clrscr(); printf("\nDo you wish to use previously trained weights? (y or n)-->"); while(((ch=getch())!='y')&&(ch!='n')); putch(ch); switch(ch) { case 'y' : printf("\nEnter file name -->"); scanf("%s",file_name); fptr=fopen(file_name,"r"); if(fptr==NULL) { printf("No such file exists."); exit(1); } fscanf(fptr,"%d ",&L); NL=(int *)malloc(L*sizeof(int)); NS=(int *)malloc(L-2)*sizeof(int); for(i=0;i<L;i++) fscanf(fptr,"%d ",&NL[i]); NS[0]=NL[0]*NL[1]; for(i=1;i<(L-2);i++) NS[i]=NS[i-1]+NL[i]*NL[i+1]; N=NS[L-3]+NL[L-2]*NL[L-1]; /* Total # of weights */ /* Assigning memory for weights. */ w=(float *)malloc(N*sizeof(float)); for(i=0;i<N;i++) fscanf(fptr,"%f ", &w[i]); fscanf(fptr,"%f ",&theta); fclose(fptr); break; case 'n': /* Entering number of layers. */ printf("\nEnter number of hidden layers-->"); scanf("%d",&L); L+=2; /*adding input and output layers. */ NL=(int *)malloc(L*sizeof(int)); NS=(int *)malloc((L-2)*sizeof(int)); printf("Enter number of nodes in input layer-->"); scanf("%d",&NL[0]); for(i=1;i<=(L-2);i++) { printf("Enter number of nodes in hidden layer %d-->",i); scanf("%d",&NL[i]); } printf("Enter number of nodes in output layer-->"); scanf("%d",&NL[L-1]); NS[0]=NL[0]*NL[1]; for(i=1;i<(L-2);i++) NS[i]=NS[i-1]+NL[i]*NL[i+1]; N=NS[L-3]+NL[L-2]*NL[L-1]; /* Total # of weights. */ /* Assigning memory for weights. */ w=(float *)malloc(N*sizeof(float)); randomize(); for(i=0;i<N;i++) w[i]=(float)random(N)/(float)N; theta=0.1; } Nt=0; for (i=1; i<L; i++) Nt+=NL[i]; /* Total number of neurals. */ gotoxy(1,10); printf("Enter file name for storing trained weights--> "); scanf ( "%s" , file_name) ; ind=access(file_name,0); while(!ind) { gotoxy(1,12); printf("File exists. Wish to overwrite? (y or n)-->"); while(((ch=getch())!='y')&&(ch!='n')); putch(ch); switch(ch) { case 'y': ind=1; break; case 'n' : gotoxy(1,7); printf(" "); gotoxy (1,10); printf ( " "); gotoxy(1,100); printf("Enter file name -->"); scanf("%s",file_name); ind=access(file_name,0); } } fptr=fopen(file_name,"w"); /* Assigning memory to *net, *z, *delta. */ net=(float *)malloc(Nt*sizeof(float)); y=(float *)malloc(Nt*sizeof(float)); delta=(float *)malloc(Nt*sizeof(float)); printf("\nEnter file - name containing training data -->"); scanf("%s",file_name2); fptr2=fopen(file_name2,"r"); if(fptr2==NULL) { printf("file %s does not exist. ", file_name); exit(1); } /* Determining the size of the data.*/ M=0; ind=1; while(1) { for(i=0;i<NL[0];i++) { if((fscanf(fptr2,"%f ",&xt))==EOF) /*input data. */ { ind=0; break; } } if(ind==0) break; for(i=0;i<NL[L-1];i++) /* desired output. */ fscanf(fptr2,"%d ",&xd); M++; } printf("\n# of data points=%d",M); rewind(fptr2); /* Assigning memory to *xp, *d */ xp=(float *)malloc((M*NL[0])*sizeof(float)); d=(int *)malloc((M*NL[L-1])*sizeof(int)); /* Reading in the data. */ for(i=0; i<M; i++) { for(j=0;j<NL[0];j++) fscanf(fptr2,"%f ",&xp[j*M+i]); for(j=0;j<NL[L-1];j++) fscanf(fptr2,"%d ",&d[j*M+i]); } fclose(fptr2); /*Call the Fletcher-Reeves conj. grad. algorithm.*/ clrscr(); gotoxy(1, 1); printf("Press ESC to exit and save latest update for weights."); conj_grad(fun, dfun, w, N, 1.e-3,1.e-3, 10000); fprintf(fptr, "%d", L); for( i=0; i<L; i++) fprintf(fptr , "%d ", NL[i]); for(i=0; i<N; i++) fprintf(fptr,"%f ",w[i]); fprintf(fptr, "%f ", theta); fclose(fptr); q=fun(w); printf("\nError=%f ", q); printf ( "\n File name used to store weights i s %s" , file_name); printf ( "\n File name for the trai ning data is %s" , file_name2); } extern float *net, *w, *delta, *y ; extern int *d; extern int *NS,*NL; /* Generating the function. */ float fun(float *w) { int i,j,k,m,n,Nt1,Nt2; float q, error, E; q=0.0; for(k=0; k<M; k++) { for(i=0;i<NL[1];i++) /* From input layer to first */ { /* hidden layer. */ net[i]=0.0; for(j=0;j<NL[0];j++) net[i]+=w[i+j*NL[1]]*xp[j*M+k]; net[i]+=theta; E=(float)exp(-(double)net[i]); y[i]=1.0/(1.0+E); } Nt1=NL[1]; Nt2=0; for(n=2;n<L;n++) /* From layer n-1 to layer n. */ { for(i=0;i<NL[n];i++) { m=Nt1+i; net[m]=0.0; for(j=0;j<NL[n-1];j++) net[m]+=w[NS[n-2]+i+j*NL[n]]*y[j+Nt2]; net[m]+=theta; E=(float)exp(-(double)net[m]); y[m]=1.0/(1.0+E); } Nt1+=NL[n]; Nt2+=NL[n-1]; } for(i=0;i<NL[L-1];i++) /* Caculating the error. */ { error=d[k+i*M]-y[Nt2+i]; q+=error*error; } } /*k-loop*/ q/=2 ; return q; } extern float *df,*w,*net; extern *NL,*NL; #define fd(i) y[i]*(1.0-y[i]) /* Define derivative. */ void dfun(float *w, float *df, int N) { int i,j,k,m,n,Nt1,Nt2,Nt3,ii; float E,error,sum; /* Initialize derivative vector. */ for(i=0;i<N;i++) df[i]=0.0; /* Start. */ for(k=0;k<M;k++) { /* Forward propagation. */ for(i=0;i<NL[1];i++) /* From input layer to first */ { /* hidden layer. */ net[i]=0.0; for(j=0;j<NL[0];j++) net[i]+=w[i+j*NL[1]]*xp[j*M+k]; net[i]+=theta; E=(float)exp(-(double)net[i]); y[i]=1.0/(1.0+E); } Nt1=NL[1]; Nt2=0; for(n=2;n<L;n++) /*From layer n-1 to layer n. */ { for(i=0;i<NL[n];i++) { m=Nt1+i; net[m]=0.0; for(j=0;j<NL[n-1];j++) net[m]+=w[NS[n-2]+i+j*NL[n]]*y[j+Nt2]; net[m]+=theta; E=(float)exp(-(double)net[m]); y[m]=1.0/(1.0+E); } Nt1+=NL[n]; Nt2+=NL[n-1]; } Nt1=0; for(i=1; i<(L-1);i++) Nt1+=NL[i]; for(i=0; i<NL[L-1]; i++) /* delta's for output layer. */ { ii=Nt1+i; error=d[k+i*M]-y[ii]; delta[ii]=-error*fd(ii); } for(m=0;m<(L-2);m++) /* delta's by back propagation. */ { Nt2=Nt1-NL[L-2-m]; for(i=0;i<NL[L-2-m];i++) { ii=Nt2+i ; sum=0.0; for(j=0;j<NL[L-1-m];j++) sum+=delta[Nt1+j]*w[NS[L-3-m]+j+i*NL[L-1-m]]; delta[ii]=fd(ii)*sum; } Nt1=Nt2; } for(i=0;i<NL[1];i++) for(j=0;j<NL[0];j++) df[i+j*NL[1]]+=delta[i]*xp[k+j*M]; Nt1=NS[0]; Nt2=0; Nt3=NL[1]; for(m=1;m<(L-1) ;m++) { for(i=0;i<NL[m+1];i++) for(j=0;j<NL[m];j++) df[Nt1+i+j*NL[m+1]]+=delta[Nt3+i]*y[Nt2+j]; Nt1=NS[m] ; Nt2+=NL[m]; Nt3+=NL[m+1]; } } /*k-loop*/ } #include #include #include #include void conj_grad( float (*)(float *), void(*)(float *, float*, int), float *, int, float ,float, int ); float f( float, float (*)(float *),float *, float *, float *, int); float fun(float *); void dfun(float*, float*,int); void bracket(float , float , float *,float *,float (*)(float *), float *, float *, float *, int); float Brent(float, float, float (*)(float *),float, float *,float *, float *, int ); /* Conjugate gradient method. fun:is a subprogram that returns the value of the function to be minimized. The arguments are: vector of variables, number of variables. dfun:is subprogram that provides the gradients. Arguments: variables, gradients, number of variables. x[]: contain the variables. An initial value need to be supplied. N: number of variables. eps1: overall convergence criteria. eps2: line search convergence criteria. no_iter: Maximum number of iterations. */ #define ESC 0x1B float EPS; /*square-root of machine epsilon. */ void conj_grad( float (*fun)(float *), void (*dfun)(float *, float *, int), float *x, int N, float eps1, float eps2, int no_iter) { float *df,*dfp,*xt,*S,q,astar,sum,test,sum1,sum2; int i,j,iter; float a,b,tol1; EPS=1.0; do { EPS/=2.0; tol1=1.0+EPS; } while(tol1>1.0); EPS=(float)sqrt((double)EPS); df=(float *)malloc(N*sizeof(float)); dfp=(float *)malloc(N*sizeof(float)); S=(float *)malloc(N*sizeof(float)); xt=(float *)malloc(N*sizeof(float)); dfun(x,df,N); for(i=0;i<N;i++) S[i]=df[i]; gotoxy(1,6); q=fun(x); printf(" Initial value of error function=%f",q); iter=0; while(iter<no_iter) { if(kbhit()!=0) { if(getch()==ESC); return; } iter++; /* test convergence. */ test=0.0; for(i=0;i<N;i++) test +=(float)fabs((float)df[i]); if(test < eps1) { printf("\nConvergence by gradient test."); break; } /* If df*S<0.0 restart. */ test=1.0; for(i=0;i<N;i++) { if( df[i]*S[i]>0.0){ test=-1.0; break; } } if(test<0.0) { for(i=0;i<N;i++) S[i]=df[i]; } /* Save previous gradient vector.*/ for(i=0;i<N;j++) dfp[i]=df[i]; /* Line Search. */ bracket(0.01, 0.001,&a,&b,fun,x,xt,S,N); astar=Brent(a,b,fun,eps2,x,xt,S,N); /* Adjust variables.*/ for(i=0;i<N;i++) x[i]-=astar*S[i]; dfun(x,df,N); sum1=sum2-0.0; for(i=0;i<N;i++) { sum1+=dfp[i]*dfp[i]; sum2+=df[i]*df[i]; } sum=sum2/sum1; for(i=0;i<N;i++) S[i]=sum*S[i]+df[i]; q=fun(x); gotoxy(1,7); printf(" Error function=%f at iteration # %-5d",q,iter); } printf("\nNumber of iterations = %d \n",iter); free(S); free(xt); } /* Function evaluation for line search. */ float f( float alpha, float (*fun)(float *),float *x, float *xt, float *S, int N) { int i; float q; for(i=0;i<N;i++) xt[i]=x[i]-alpha*S[i]; q=fun(xt); return q; } /* Function to bracket the minimum of a single variable function. */ void bracket(float ax, float dx, float *a,float *b,float (*fun)(float *), float *x, float *xt, float *s, int N) { float y1,x1,x0,y0,x2,y2; int iter; x0=ax ; x1=x0+dx; y0=f(x0,fun,x,xt,s,N); y1=f(x1,fun,x,xt,s,N); if(y1>=y0) { dx=-dx; x1=x0+dx; y1=f(x1,fun,x,xt,s,N); } dx=2.0*dx; x2=x1+dx; y2=f(x2,fun,x,xt,s,N); iter=0 ; while(y2<y1) { iter++; dx=2.0*dx; x0=x1; y0=y1; x1=x2; y1=y2; x2=x1+dx; y2=f(x2,fun,x,xt,s,N); } *a=x0; *b=x2; } /* Brent's algorithm for obtaining the minimum of a single variable function. */ #define CGOLD 0.381966 float Brent(float ax, float bx , float (*fun) (float *) , float TOL, float *x,float *xt, float *S, int N) { float a,b,u,v,w,xx,e,fx,fv,fu,fw,xm,tol1,tol2,c,r,q,p; int iter; a=ax; b=bx; v=a+CGOLD*(b-a); w=v; xx=v; e=0.0; fx=f(xx,fun,x,xt,S,N); fv=fx; fw=fx; c=0.0; iter=0; while(iter<100) { iter++; xm=0.5*(a+b); tol1=EPS*(float)fabs((double)xx)+TOL/3.0; tol2=2.0*tol1; if((float)fabs((double)(xx-xm))<=(tol2-0.5*(b-a))) { return xx; } if((float)fabs((double)e)>tol1) { r=(xx-w)*(fx-fv); q=(xx-v)*(fx-fw); p=(xx-v)*q-(xx-w)*r; q=2.0*(q-r); if(q>0.0) p=p; q=(float)fabs((float)q); r=e; e=c; /* is parabola acceptable.*/ if(((float)fabs((double)p)<(float)fabs((double)(0.5*q*r)))|| (p > q*(a-xx))|| (p < q*(b-xx))) {/* fit parabola.*/ if(q==0.0) q=1.e-10; c=p/q; u=xx+c; /* f must not be evaluated too close to a or b. */ if( (((u-a)<tol2))|| ((b-u)<tol2) ) c=((xm-xx)>0.0) ? tol1 : -tol1; goto l2; } else goto l1; } else { /* A tỷ lệ vàng step. */ l1: if(xx>=xm) e=a-xx; else e=b-xx; c=CGOLD*e; } /* update a,b,v,w, and x. */ l2: if(fabs((double)c)>=tol1) u=xx+c; else u=xx+((c>0.0)?tol1:-tol1); fu=f(u,fun,x,xt,S,N); if(fu<=fx) { if(u>=xx) a=xx; else b=xx; v=w; fv=fw; w=xx; fw=fx; xx=u ; fx=fu; continue; } else { if(u<xx) a=u; else b=u; } if((fu<=fw)||(w==xx)) { v=w; fv=fw; w=u; fw=fu; continue; } if((fu<=fv)||(v==xx)||(v==w)) { v=u; fv=fu; } } } Để kiểm tra chương trình 12.3 chúng ta lấy dữ liệu dùng chương trình 12.2 từ ảnh "AUTHOR.IMG". Các màu ở đây được chia thành các sắc màu liên tiếp nhau. Dữ liệu đã có sẵn trên đĩa, chứa trong file "TINT2.DAT", dữ liệu có thể biểu diễn trên sơ đồ màu như hình 12.13. Chương trình có thể bị ngắt tại bất kỳ lúc nào bằng cách ấn phím ESC. Kết quả của hệ thống sẽ được lưu một cách tự động trong một file đặc biệt có tên ban đầu do người dùng đặt. Nếu sau đó bạn muốn tiếp tục với "đào tạo", bạn cần quay trở về chương trình chính, nhưng lần này trả lời "y" khi chương trình hỏi bạn: Bạn có muốn dùng các trọng số được đào tạo trước không? Lý do phải có phím ESC là đào tạo đòi hỏi một thời gian dài và bạn muốn ngắt chương trình, dùng máy tính vào các việc khác. Để áp dụng, chúng ta dùng một một perceptron ba lớp (cũng có thể dùng perceptron hai lớp), với lớp che khuất đầu tiên có tám nút, lớp che khuất thứ hai có bốn nút, và lớp ra chỉ có một nút. Lớp vào, tất nhiên là chỉ có hai nút, một cho x và một cho y - các biến của biểu đồ màu. Tín hiệu ra của hệ thống sẽ là 1 nếu dữ liệu biểu diễn cho sắc màu skin, và 0 cho các trường hợp còn lại. Chương trình bắt đầu bằng một số tính ngẫu nhiên giữa 0 và 1, và đòi hỏi gần 17,000 phép lặp và hơn 5 giờ tính toán trên máy 486-25 MHz. Sai lệch giảm xuống từ 32 xuống 0.0057. File chứa hệ thống này, chẳng hạn như, số các lớp, số các điểm trong mỗi lớp, và trọng số có sẵn trên đĩa dưới tên " WTSST.DAT". Hình 12.13 "TINT2.DAT" dùng thử mạng thần kinh. Bây giờ chúng ta cần phát triển một chương trình để kiểm tra cách làm việc thực sự của hệ thống. Liệt kê cho tất cả các thuật toán này trong một chương trình được cho ở dưới đây. Chương trình 12.4 “TESNLYE.C”. Kiểm tra. /* Program 12.4 "TESNLYE.C". Testing a multilayer network.*/ /************************************ * Developed by M.A.Sid-Ahmed. * * ver. 1.0, 1992. * * @ 1994 * *************************************/ /* Program for testing a multi-layer perceptron. */ void float fun(float *); #include #include #include #include int M,*NL,*NS,L; int *d; float *xp,*y,*net,*delta,theta; void main() { float *w,q,xt; int i,j,N,xd,ind,Nt; char file_name[14],file_name2[14],ch; FILE *fptr,*fptr2; clrscr(); printf("\nEnter file_name for weights-->"); scanf("%s",file_name); fptr=fopen(file_name,"r"); if(fptr==NULL) { printf("file %s does not exist. ",file_name); exit(1); } fscanf(fptr,"%d ",&L); NL=(int *)malloc(L*sizeof(int)); NS=(int *)malloc((L-2)*sizeof(int)); for(i=0;i<L;i++) fscanf(fptr,"%d ",&NL[i]); NS[0]=NL[0]*NL[1]; for(i=1;i<(L-2);i++) NS[i]=NS[i-1]+NL[i]*NL[i+1]; N=NS[L-3]+NL[L-2]*NL[L-1]; /* Total # of weights. */ /* Assigning memory for weights. */ w=(float *)malloc(N*sizeof(float)); for(i=0;i<N;i++) fscanf(fptr,"%f ",&w[i]); fscanf(fptr,"%f ",&theta); fclose(fptr), Nt=0 ; for(i=1;i<L;i++) Nt+=NL[i]; /* Total number of neurals. */ /* Assigning memory to *net, *z, *delta. */ net=(float *)malloc(Nt*sizeof(float)); y=(float *)malloc(Nt*sizeof(float)); delta=(float *)malloc(Nt*sizeof(float)); printf("\nEnter file - name containing training data -->"); scanf("%s",file_name2); fptr2=fopen(file_name2,"r"); if(fptr2==NULL) { printf("file %s does not exist. ", file_name); exit(1); } /* Determining the size of the data. */ M=0; ind=1; while(1) { for(i=0;i<NL[0];i++) { if((fscanf(fptr2,"%f ",&xt))==EOF) /* input data. */ { ind=0; break; } } if(ind==0) break; for(i=0;i<NL[L-1];j++) /* desired output. */ fscanf(fptr2,"%d ",&xd); M++; } printf("\n# of data points=%d",M); rewind(fptr2); /* Assigning memory to *xp, *d */ xp=(float *)malloc((M*NL[0])*sizeof(float)); d=(int *)malloc((M*NL[L-1])*sizeof(int)); /* Reading in the data. */ for(i=0; i<M; i++) { for(j=0;j<NL[0];j++) fscanf(fptr2,"%f ",&xp[j*M+i]); for(j=0;j<NL[L-1];j++) fscanf(fptr2,"%d ",&d[j*M+i]); } fclose(fptr2); gotoxy(1,7); printf ("Press any key to see network response for next input."); fun(w); } extern float *net,*w,*delta,*y; extern int *d; extern int *NS,*NL; /* Generating the function. */ void fun(float *w) { int i,j,k,m,n,Nt1,Nt2; float error, E; for(k=0;k<M;k++) { for(i=0;i<NL[1];i++) /* From input layer to first */ { /* hidden layer. */ net[i]=0.0; for(j=0;j<NL[0];j++) net[i]+=w[i+j*NL[1]]*xp[j*M+k]; net[i]+=theta; E=(float)exp(-(double)net[i]); y[i]=1.0/(1.0+E); } Nt1=NL[1]; Nt2=0; for(n=2;n<L;n++) /* From layer n-1 to layer n. */ { for(i=0;i<NL[n];i++) { m=Nt1+i; net[m]=0.0; for(j=0;j<NL[n-1];j++) net[m]+=w[NS[n-2]+i+j*NL[n]]*y[j+Nt2]; net[m]+=theta; E=(float)exp(-(double)net[m]); y[m]=1.0/(1.0+E); } Nt1+=NL[n]; Nt2+=NL[n-1]; } gotoxy(1,10); for(i=0;i<NL[L-1];i++) /* Calculating the error. */ { error=d[k+i*M]-y[Nt2+i]; printf("response to data # %d",k+1); if (NL[L-1]!=1) printf("\noutput # %d",i); printf("\ndesired=%d actual=%f error=%f", d[k+i*M],y[Nt2+i],error); } getch(); } /*k-loop*/ } Bài tập 12.2 1. Dùng hệ thống, với các trọng số "WTSST.DAT" có sẵn trên đĩa, để kiểm tra liệu hệ thống này có thể "nhận ra " sắc màu skin như được cho trong "TINT2.DAT". 2. Phát triển một chương trình C mà dùng một hệ thống nhiều lớp để sửa lại một cách có lựa chọn một màu đặc biệt. Dùng hệ thống xác định bằng các trọng số chứa trong " WTSS.DAT" áp dụng trên ảnh "AUTHOR.IMG" 3. Lập lại chương trình 12.3 PERNCONJG.C dùng thuật toán Davidon - Fletcher - Powell để thay thế . Lưu lại chương trình vào file PERNDFP.C. 4. Kiểm tra PERNDFP.C trên TINT2.DAT. 12.7 Quá trình nhận biết Thật không rõ ràng lắm là tại sao sự nhận biết lại chiếm một vị trí quan trọng trong mối quan tâm của con người. Dù có thế nào thì quá trình nhận biết luôn luôn được kết hợp một cái tên hoặc một cách gọi nào đó. Để xác định một vật thể, cho ví dụ, là quá trình xử lý kết hợp giữa nhận ra hình dạng và kết hợp với một cái tên đặc biệt. Câu hỏi là: bạn có cần phải biết tất cả các hình dạng khác nhau để nhận ra hình dạng của một vật thể? Trong thuật toán nhận biết đã dùng (thuật toán này cũng áp dụng quy tắc delta), tất cả dữ liệu biểu diễn cho một màu đặc biệt và dữ liệu biểu diễn cho tất cả các màu khác còn lại cần phải được biết. Điều này có vẻ hơi khác với cách mà chúng ta nhận biết. Có vẻ như chúng ta không cần những thông tin ngoài thông tin xác định cấu trúc một lớp màu đặc biệt mà chúng ta muốn nhận biết. Các dữ liệu về phân lớp đối tượng hoặc cảm nhận màu sắc sẽ có thể dạy cho hệ thống thần kinh về một đối tượng đặc biệt, hoặc màu sắc, mà không cần một sự tham khảo các điểm ngoài tập hợp này. Trong sự quan sát của tôi, tôi nhận ra rằng trẻ em bắt đầu nhận ra rất sớm sự khác nhau về hình dạng của các vật thể biểu diễn các ký tự của bảng chữ cái, mỗi ký tự một thời điểm. Phương pháp nhận biết là công nhận, tiếp nối nhau bởi các lần đặt tên. Sự kết hợp của hình dạng, cảm nhận hoặc cảm giác với gọi tên là một xử lý đặc biệt cho nhận dạng. Chú ý là nếu bạn nghe giọng nói của một người trên điện thoại lần đầu tiên, và người gọi cho bạn tên của anh hoặc cô ta thì suy nghĩ đầu tiên của bạn là tưởng tượng ra một khuôn mặt với cái tên ấy - một khuôn mặt mà trí tưởng tượng của bạn tạo ra trên cơ sở của kết hợp của giọng nói và tên gọi. Sau này, khi bạn gặp người đó, một câu nói cửa miệng hay dùng là "Bạn hoàn toàn không giống như tôi đã nghĩ". Điều đó có nghĩa là sự gặp gỡ này đã hoàn thành một nhận biết. Một cái tên thì gắn với một vật thể và một vật thể sẽ tự động được gắn với một cái tên. Điều đó có nghĩa là "nhận biết" trong trường hợp này là một phương pháp còn xa mới hoàn thiện như nhận biết xác định bằng thuật toán được miêu tả trong phần trước. Trong kinh nghiệm của mình, qua quá trình theo dõi con trai tôi lớn lên và phát triển, tôi nhớ lại rằng khi con tôi vào khoảng một tuổi rưỡi, cháu thường đi vào bếp trước giờ đi ngủ và bắt đầu chỉ vào một vật nào đó. Tại tuổi này, khả năng thể hiện bằng lời nói của cháu còn rất hạn chế. Cháu đầu tiên chỉ vào một chiếc ghế, tôi lập tức gọi tên của vật này cho cháu. Cháu nhắc lại từ "ghế", và tiếp tục chỉ vào một vật khác. Tôi cho tên của vật, cháu nhắc lại. Cháu quay lại với vật thể đầu tiên, thốt ra tên, sau đó quay sang với vật thể thứ hai và lại gọi tên. Điều này cứ tiếp tục diễn ra cho đến khi mà nó cảm thấy nó đã học đủ cho ngày hôm ấy. Cái cách nhận biết bằng cách tự gọi tên mà tôi đã chứng kiến này đã làm cho tôi suy nghĩ tới tận hôm nay. Từ kinh nghiệm này, tôi nhận thấy rằng sự nhìn nhận vật thể và gọi tên phải luôn luôn đi liền với nhau. Có lẽ phần lớn là cháu muốn nhìn nhận vật thể, có lẽ phần lớn là cháu muốn tạo ra một cái tên cho chúng (ngôn ngữ trẻ em); cháu chỉ muốn biết bằng cách nào tôi gọi được tên của vật thể - và có thể cháu sẽ có thể giao tiếp hoàn thiện hơn với tôi hoặc có thể đó chỉ là một sự tò mò cố hữu (một điều rất khó thể mô phỏng bằng máy tính). 12.8 Nhận biết theo phân nhóm Không có một cấu trúc sinh lý học hoặc hiểu biết nào chứng minh cho giả thiết cho rằng tất cả các tế bào thần kinh đều giống nhau và có thể biểu diễn bằng một hàm xichma, hoặc tất cả các tín hiệu vào được nhân với các trọng số. Tế bào thần kinh như chúng ta biết có các hình dạng khác nhau và đóng các vai trò khác nhau. Điều này cho phép chúng ta cho ra một lý thuyết mới. Dựa trên kết luận trong phần trước, một cấu trúc khác và một thuật toán nhận biết đã được phát triển bởi Abou-El-Nasr. Cấu trúc này có tên gọi là LBAQ - "nhận biết bằng cách đặt ra các câu hỏi". Nó giống như thuật toán phân nhóm mô tả bởi Hartigan, và được áp dụng trong phân lớp Carpenter/Grossberg. Thuật toán này theo các bước sau: 1. Chỉ ra các đặc điểm hoặc thuộc tính của một đầu vào ký hiệu cho đối tượng cần phân lớp. 2. Các đặc điểm này định nghĩa trung tâm của nhóm đầu tiên. Cho một hệ thống hai đầu vào: (12.24) ở đây xp[0] và xp[1] là đặc điểm của sơ đồ màu đã cho. Những thông số này là x và y trong bài toán phân lớp màu của chúng ta. Mỗi nhóm được định nghĩa bằng tâm, bán kính, và số điểm của nhóm. 3. Bước tiếp theo Nếu Ê radius (12.25) thì điều chỉnh tâm điểm của nhóm theo công thức ở đây i = 0,1,...,số nhóm j = 0,1 (12.26) và tăng số điểm của nó. Mặt khác, dạng của một nhóm mới với tâm của nó là mẫu mới. 4. Tiếp theo việc đưa vào thì khoảng cách tới mỗi nhóm được tính. Nếu mẫu trong nhóm gần nhất, theo công thức (12.25), tâm của mẫu đó được điều chỉnh. Mặt khác một nhóm mới được tạo khuôn. 5. Quá trình xử lý được lặp lại với tất cả các điểm trong lớp. Một nhãn có thể được thiết kế cho mỗi nhóm bằng cách cho phép giải thuật hỏi tên để đặt cho nhóm đó. Một vài hay tất cả các nhóm có thể được cùng một tên hay nhãn. Một thuận lợi của phương pháp này là nó nghiên cứu dữ liệu đang được đưa ra, và không đòi hỏi nhắc lại. Nếu hệ thống được đòi hỏi để nghiên cứu một màu nó không cần biết dữ liệu bên ngoài lớp trực tiếp định nghĩa màu đó. Sự lựa chọn bán kính cho các nhóm khác nhau là giới hạn về sự thành công của giải pháp, và là dữ liệu phụ thuộc. Nếu bán kính là quá lớn, thì sự phân lớp sai là có thể xảy ra; nếu quá nhỏ thì phải cần đến một số lượng lớn các nhóm, lỗ hổng giữa các nhóm lại có thể dẫn đến sự phân lớp sai. Bởi vì giải thuật đòi hỏi rất ít thời gian tính toán những sai số khá nhỏ này có thể bỏ qua. Bán kính có thể được chọn cơ bản dựa trên phép thử và sai. Bài tập 12.3 1. Mạng thần kinh nhận biết thuộc một lớp của phân lớp thần kinh được biết như phân lớp thần kinh nguyên mẫu. Phát triển chương trình để định ra bán kính của lớp thần kinh nguyên mẫu. 2. Phát triển một giải thuật để có thể thay đổi được bán kính lớp nguyên mẫu thần kinh. Giải thuật bắt đầu với bán kính định trước cho tất cả các nhóm, tiếp theo nhóm những nhóm lân cận với cùng một nhãn. 3. Viết chương trình với giải thuật được viết trong phần 2 của bài tập này. 4. Kiểm tra chương trình với phân lớp nguyên mẫu. Sử dụng bán kính = 0.01 và dữ liệu được định nghĩa trong "TINT2.DAT" giải pháp được đưa ra với thời gian thực hiện rất ít. Hệ thống kết thúc với 16 nhóm. Hình 12.14 là trực quan hoá kết quả. Hình 12.15 chỉ ra cách giải pháp này liên kết thành một mạng thực sự. Như bạn có thể nhìn thấy, một vài nơron là cơ sở để tính tổng giá trị, những nơron khác thực hiện chức năng hình vuông, những nơron này đóng vai trò giới hạn, và một kiểu thực hiện là phép toán logic OR. Chủ đề nhận biết màu sắc là chủ đề quan trọng - không chỉ trong xử lý ảnh màu như chúng ta đã chứng kiến, nhưng cũng là bài toán của máy nhìn. Bởi vì mục đích chính của quyển sách này là trực tiếp đi theo hướng xử lý ảnh và ứng dụng tín hiệu vô tuyến, chúng ta sẽ không đi chệch hướng đến chủ đề máy hay người máy nhìn. Tuy nhiên, tôi muốn chỉ ra rằng hệ thống nhìn sử dụng cho người máy trong công nghiệp là cứng và không có sự linh động được đưa ra trong chương này. Một hệ thống nhận biết màu bằng AEG của Frankfurt, Đức được miêu tả trong bài báo, tác giả Gosch. 12.9 Máy ô-tô-nôm Một cảm nhận tôi thấy khi tôi bắt đầu nghiên cứu chủ đề nhận biết của con người và mạng thần kinh nhân tạo đó chúng rất gần gũi để tạo ra trí thông minh thực sự, máy Ô-tô-nôm (Autonomous - hoạt động độc lập). Cảm giác mà tôi nhận được nhiều hơn cả từ sự cường điệu hoá từ hiện thực. Thực ra chúng ta còn xa với việc tạo ra máy Ô-tô-nôm thực sự tại thời điểm này. Tuy nhiên, chúng ta có thể nói tương lai sẽ như thế nào? Có thể một ngày với những cải tiến vượt bậc trong phần cứng, phần mềm, và sự hiểu biết về chính bản thân chúng ta, chúng ta cũng có thể tạo được một máy giống với "Dữ liệu" của "Star Trek: Thế hệ tiếp theo." Hình 12.14 Trực quan hoá mạng thần kinh. Bây giờ tôi muốn kể một câu truyện với bạn. Câu truyện như sau: Đấng sáng tạo quyết định sáng chế một máy Ô-tô-nôm, máy có tổ chức rất lớn, nhưng có giới hạn, có khả năng sáng tạo. Sau đó máy được trao trách nhiệm chăm lo cho trái đất. Trái đất là quà sáng tạo trời cho. Đấng sáng tạo tụ họp các thần phụ tá (các thiên thần) của ông ta và truyền cho họ ý định của ông ta. Các phụ tá hỏi, nếu như có một máy có khả năng lớn như vậy sẽ có thể trở thành nguyên nhân của sự phá hoại và đổ máu. Đấng sáng tạo đáp lại rằng ông ta biết họ không biết những gì. Sau đó ông ta đưa tác phẩm mới của ông ta ra, ông đặt tên là Adam. Trước tiên ông ta dạy (lập trình) cho Adam đặt tên các đồ vật. Ông ta hỏi các thần đặt tên cho các đồ vật mà họ hay Adam chưa thấy bao giờ. Các thần đáp lại rằng họ chỉ biết những cái gì mà họ đã được dạy. Sau đó ông ta hỏi Adam đặt tên cho đồ vật. Adam có thể đưa ra tất cả các tên cho các đồ vật (nhận ra hoặc nhóm lại, theo nhãn). Đó là khả năng rất mạnh sẽ gián tiếp dẫn Adam đến việc phát minh ngôn ngữ để giao tiếp, đó là công cụ phần mềm, và công cụ phần cứng để xây dựng và phát triển xa hơn nữa. Các thần không có khả năng như vậy. Dù vậy, vẫn còn một vấn đề nhỏ cần được kiểm tra trước khi đưa phát minh này xuống trái đất. Adam đã hoạt động độc lập được chưa? Phương pháp tốt nhất là cung cấp cho Adam một lệnh không có cơ sở logic và tiến hành nếu anh ta theo sự đánh dấu đó hay lý luận với lý lẽ ngược trở lại. Đấng sáng tạo quyết định rằng cách tốt nhất là đưa Adam ra kiểm tra trước khi đưa Adm xuống quản lý trái đất. Vì thế, đấng sáng tạo đưa Adam vào một khu vườn và tự do làm những gì anh ta muốn, ngoại trừ ăn quả của những cây được chỉ rõ. Tuy nhiên, một vài điều trục trặc đã xảy ra.... Adam tuân lệnh theo một nghĩa hẹp. Anh ta thiếu tính chất của một máy Ô-tô-nôm. Rõ ràng, đấng sáng tạo cần phải sửa lỗi phần mềm đã điều khiển Adam. Trong thời gian chờ đợi, ông ta quyết định làm Adam theo mẫu một sinh vật khác trên trái đất bằng cách cung cấp cho Adam một người bạn. Ông cũng giới hạn tuổi thọ cho Adam (vì thế ông không chần chừ) và khả năng mở rộng sự hiện diện trên trái đất thông qua việc sinh sôi nảy nở. Lần này Adam tuân theo logic nội quy. Anh ta đứng dưới cây bị cấm đoán và hỏi một câu làm anh ta trở thành người sáng tạo thực sự "Cái gì xảy ra nếu...". Đó là câu hỏi rất hay để sáng tạo, vì vậy ông ta đã đặt Adam xuống trái đất. Hình 12.15 Cấu trúc hai cụm tế bào thần kinh. Cậu bé Adam được tạo ra từ công cụ đơn giản để thám hiểm nhân loại. Bước tiếp theo của khoa học dường như đi thẳng về hướng hiểu chính chúng ta và có thể tạo ra máy Ô-tô-nôm của chúng ta, giống như câu truyện hư cấu "Dữ liệu" trong "Star Trek (sự di cư của các vì tinh tú): Thế hệ tiếp theo."