Chương 1. Kết quả của thiết kế đạt yêu cầu kỹ thuật như thế nào đã được trình bày trong chương này. GIỚI THIỆU Trong chương này, các kiến thức tổng quan về Artificial Neural Network, FPGA, FSMD, và kiểm chứng thiết kế sẽ được trình bày. Giới thiệu về Artificial Neural Network 1.
Lịch sử hình thành và phát triển Artificial Neural Network (viết tắt là ANN), thường được gọi tắt Neural Network, là mạng neuron nhân tạo. Neural Network cũng giống như các lĩnh vực khác của khoa học, có lịch sử phát triển trải qua nhiều thăng trầm. Trong cuốn sách online A brief introduction to neural network [1] tác giả đã liệt kê ra một số mốc thời gian trong lịch sử hình thành và phát triển của nó. Neural Network ra đời từ khoảng đầu những năm 1940 và gần như cùng thời điểm với sự ra đời của việc lập trình máy tính điện tử.
Năm 1943, Warren McCulloch và Walter Pitts đã giới thiệu mô hình mạng neuron và cho thấy loại mạng đơn giản này có thể tính được gần chính xác các hàm logic và toán học. Hơn nữa, với sự giúp đỡ của Konrad Zuse, tiền thân của thiết bị điện tử sử dụng Neural Network cũng được bắt đầu phát triển [1]. Hebb xây dựng công thức luật Hebbian, là luật khái quát về quy tắc cơ bản cho quá trình học tập của mạng neuron. Quy tắc này ngụ ý rằng, liên kết giữa hai neuron được củng cố khi cả hai neuron được kích hoạt cùng một lúc.
Hebb đã tin là quy tắc này đúng, nhưng vì không có công trình nghiên cứu về mạng neuron nên ông không thể chứng minh nó [1]. Năm 1957 – 1958, tại MIT, Frank Rosenblatt, Charles Wightman và các đồng nghiệp đã chế tạo thành công máy tính sử dụng mạng neuron, gọi là Mark I perceptron, có khả năng nhận dạng các số đơn giản bằng cảm biến hình ảnh 20x20 điểm ảnh (pixel), với cơ chế là 512 chiết áp điều khiển động cơ, mỗi chiết áp đại diện cho một tham số thay đổi được của mạng [1]. Năm 1959, Frank Rosenblatt đã mô tả các phiên bản khác nhau của perceptron trong mạng neuron, xây dựng công thức và chứng minh được định lý gọi là perceptron convergence theorem. Ông đã mô phỏng các lớp neuron bắt chước võng mạc, các ngưỡng chuyển đổi và một nguyên tắc học tập để điều chỉnh các tham số của các kết nối trong mạng.
[1] Năm 1965, trong cuốn sách Machine Learning của mình, Nils Nilsson đã đưa ra cái nhìn tổng quát về sự tiến triển và thành quả của các công trình nghiên cứu về ANN 2 trong thời kì này. Nó được coi là lý thuyết cơ bản cho việc tự học của các trí thông minh nhân tạo [1]. Khoảng thời gian tiếp theo là khoảng thời gian trầm lặng đối với việc nghiên cứu về Neural Network, bởi tài trợ cho các công trình nghiên cứu này còn hạn chế. Các công bố và hội thảo về lĩnh vực này có ít, chỉ có các nhà nghiên cứu hoạt động riêng lẻ và không có sự trao đổi lẫn nhau [1].
Đến năm 1985, Neural Network bước vào thời kỳ phục hưng khi John Hopfield tìm được lời giải chấp nhận được cho bài toán Travelling Salesman Problem (TSP) sử dụng mạng Hopfield. Nội dung của TSP là: cho danh sách các thành phố và khoảng cách giữa mỗi cặp thành phố, từ thành phố gốc ta cần tìm con đường ngắn nhất có thể đến thăm từng thành phố và trở về thành phố gốc. Đây là một bài toán quan trọng trong lĩnh vực khoa học máy tính [1]. Năm 1986, quy tắc học lan truyền ngược của mạng neuron được phát triển và xuất bản rộng rãi.
Từ đó đến nay, nghiên cứu về Neural Network gần như là bùng nổ với nhiều nghiên cứu không thể liệt kê hết [1]. Nguyên lý hoạt động Artificial Neural Network là thuật ngữ chung chỉ các loại mạng neuron nhân tạo. Qua lịch sử phát triển, các nhà nghiên cứu đã công bố rất nhiều loại mạng neuron nhân tạo khác nhau. Trong phần này, nguyên lý hoạt động được trình bày là nguyên lý chung của Neural Network được giới thiệu bởi tổ chức LSI Design Contest [2].
Não người có rất nhiều neuron, nó nhận tín hiệu đầu vào và tạo tín hiệu đầu ra. Ví dụ như khi tay ta chạm vào một vật nóng, thì đầu vào là nóng được truyền tới tủy sống thông qua các tế bào thần kinh bên trong, và nó sẽ đưa ra đầu ra là phản xạ rụt tay khỏi vật nóng. Neural Network là một mô hình toán học bắt chước hệ thần kinh của con người. Về cơ bản thì Neural Network có 3 lớp, đó là (1) lớp đầu vào, (2) lớp ẩn và (3) lớp đầu ra được minh họa trên Hình 1.
Cấu trúc này được gọi là cấu trúc 3 lớp. Đối với những mạng phức tạp hơn thì có thể có nhiều hơn một lớp ẩn [2].1 Cấu trúc 3 lớp [2] Tín hiệu được đưa vào ở lớp (1) và đi ra ở lớp (3). Trước khi đưa tín hiệu vào (1) thì tại đầu ra chúng ta có một giám sát viên (supervisor). Giám sát viên chính là đầu ra kỳ vọng của mạng với mục tiêu là điều chỉnh các tham số trong mạng sao cho sai lệch giữa đầu ra thực tế (output) và giám sát viên là nhỏ nhất có thể [2].2 Cấu trúc 3 lớp với các tham số [2] Hình 1.2 minh họa một mạng neuron theo cấu trúc 3 lớp với các tham số ứng với từng lớp.
Định nghĩa của các tham số trong hình như sau: ki là tín hiệu vào tại lớp đầu vào. 2 w ij là weight nối từ lớp đầu vào đến lớp ẩn. b 2 i là bias của lớp ẩn. z 2 i là đầu vào của lớp ẩn.
2 a i là đầu ra của lớp ẩn. w 3 ij là weight nối từ lớp ẩn đến lớp đầu ra. bi 3 là bias của lớp ẩn. z 3 i là đầu vào của lớp đầu ra.
ai 3 là đầu ra của lớp đầu ra. ti là giám sát viên với t 1 =1 và t 2 =0. Mối liên hệ giữa các tham số trên được biểu diễn theo chiều thuận và chiều nghịch. 5 Theo chiều thuận, ta coi tín hiệu vào tại lớp đầu vào ( k i ), các weight và bias ( w , bi , w ij , bi ) là các số đã biết, mục tiêu là tính đầu ra ai của lớp đầu 2 2 3 3 3 ij ra theo các công thức (1.4) Trong công thức (1.4), chúng ta có thể sử dụng bất kỳ hàm nào có khả năng phân biệt và chuẩn hóa để làm hàm kích hoạt (activate function) [2], ví dụ như dùng hàm tansig thì công thức (1.5) 2 −2 zi với i=1,2,3 1+e Đặt: K= [] k1 k2 [ ] 2 2 w11 w21 2 2 W 2= w 12 w22 2 2 w 13 w23 [] 2 b1 B 2= b22 b23 6 z 12 [] Z 2= z 22 2 z3 [] 2 a1 A 2= a22 2 a3 [ ] 3 3 3 w11 w21 w 31 W 3= w312 w322 w 32 3 [] 3 b1 B 3= b 23 Z 3= [] z31 z32 A 3= [] a13 a23 Các công thức (1.9) Với mỗi vector K thứ n đưa vào lớp đầu vào ta sẽ tính được một hàm lỗi bình phương (square error function) như công thức (1.10) 2 Khi đưa n vector vào lớp đầu vào, ta có hàm giá (cost function) C là tổng của các hàm lỗi bình phương đã có, như công thức số (1.11), với Cn tính như công thức (1.11) 7 Từ bây giờ chúng ta bắt đầu xây dựng công thức theo chiều nghịch sử dụng thuật toán lan truyền ngược (backpropagation).
Từ các công thức (1.10), ta thấy C là một hàm của các weight và bias ( w ij2 , bi2 , w ij3 , b3i ). Bởi vậy ta có công thức đạo hàm của C theo các weight và bias đó. Để tính đạo hàm của C theo các weight và bias, ta cần áp dụng quy tắc tính đạo hàm của hàm hợp. Quy tắc đạo hàm của hàm hợp như sau.
Với f là hàm của u và v, tức là f = f(u,v); u và v là hàm của x, tức là u = u(x) và v = v(x); nếu f(u), f(v), u(x), v(x) tồn tại đạo hàm thì ta có: ∂f ∂f ∂u ∂f ∂v = + (1.12) ∂ x ∂u ∂ x ∂ v ∂ x Giả sử ta cần tính đạo hàm của C theo w 11 , áp dụng quy tắc đạo hàm của 2 hàm hợp ta có: ∂C ∂ C1 ∂ C2 ∂C n (1.17) =( a13 [ n ] −t 1[ n] ) ( w11 + 3 w 12 ) 2 k 1 [n] ∂ z31 [ n] 2 ∂w 11 ∂ z2 [n] ∂ z1 [n] ∂C Từ công thức (1.17) ta tính được ∂ w112 2 Theo thuật toán gradient descent, ta cập nhật giá trị mới của w 11 để tối ưu C.18) 2 ∂ w11 8 Trong công thức (1.18), η là một số dương gọi là tốc độ học (learning rate). Chi tiết về thuật toán gradient descent sẽ được trình bày trong phần sau, qua đó sẽ trả lời được câu hỏi rằng tại sao cập nhật w 11 2 theo công thức (1.18) sẽ tối ưu được C. Để tối ưu C thì các weight và bias khác cũng được cập nhật theo cách tương tự. Sau khi thay đổi, chúng ta lại bắt đầu lại bằng việc đưa K vào và tiếp tục tính toán, cho đến khi đầu ra đạt giá trị gần với giám sát viên nhất [2].
Mỗi lần duyệt qua tất cả các vector K trên toàn bộ dữ liệu được gọi là một epoch [3]. Thuật toán Gradient Descent Trong toán tối ưu, chúng ta thường xuyên phải tìm các giá trị nhỏ nhất của một hàm số. Việc tìm giá trị nhỏ nhất của hàm số phức tạp là không khả thi, nên ta thường tìm các điểm cực tiểu cục bộ (local minimum), và coi đó là một nghiệm cần tìm của bài toán. Các điểm cực tiểu cục bộ là nghiệm của phương trình đạo hàm bằng không.
Tuy nhiên, trong nhiều trường hợp, việc giải phương trình đạo hàm bằng không để tìm nghiệm chính xác cũng là không khả thi, nên cần có hướng giải quyết là tìm nghiệm gần đúng [3]. Hướng tiếp cận phổ biến nhất để giải quyết các bài toán tối ưu là xuất phát từ một điểm được coi là gần với nghiệm của bài toán, sau đó dùng một phép toán lặp để tiến dần đến điểm đạo hàm bằng không [3]. Xét hàm số một biến f : R → R 9 Hình 1.3 Khảo sát sự biến thiên của một đa thức bậc 2 một biến [3] Trên Hình 1.3 là sự biến thiên của một đa thức bậc 2 một biến. Điểm cực tiểu ¿ cục bộ thực sự của f (x) là x =− 2.
Ta dùng thuật toán gradient descent để tìm ¿ điểm gần với x nhất.