http://www.ictu.edu.vn
iii
MỤC LỤC
TRANG PHỤ BÌA
Trang
LỜI CẢM ƠN ……………………………………………………………… i
LỜI CAM ĐOAN…………………………………………………………... ii
MỤC LỤC………………………………………………………………….. iii
DANH MỤC CÁC BIỂU ĐỒ, HÌNH VẼ………………………………….. v
MỞ ĐẦU...........................................................................................................1
CHƯƠNG I.......................................................................................................3
TỔNG QUAN VỀ MẠNG NƠ RON NHÂN TẠO..........................................3
1.1. GIỚI THIỆU VỀ MẠNG NƠ-RON NHÂN TẠO.................................3
1.1.1 Lịch sử phát triển..............................................................................3
1.1.2. Mô hình mạng nơ-ron nhân tạo.......................................................4
1.2. PHẠM VI ỨNG DỤNG CỦA MẠNG NƠ RON NHÂN TẠO..........19
1.2.1. Những bài toán thích hợp.............................................................19
1.2.2. Các lĩnh vực ứng dụng mạng nơ ron.............................................23
1.3. MẠNG HOPFIELD............................................................................24
1.3.1. Mạng Hopfield rời rạc...................................................................25
1.3.2. Mạng Hopfield liên tục..................................................................27
1.3.3. Mạng Hopfield với bài toán tối ưu................................................28
1.3.4. Mạng Hopfield với bài toán lập thời khóa biểu.............................30
1.4. NHẬN XÉT..........................................................................................32
CHƯƠNG II....................................................................................................33
ỨNG DỤNG MẠNG NƠ-RON HOPFIELD TRONG BÀI TOÁN LẬP THỜI
KHÓA BIỂU CHO TRƯỜNG ĐẠI HỌC.......................................................33
http://www.ictu.edu.vn
iv
2.1 Bài toán lập thời khóa biểu và những khó khăn trong việc lập thời khóa
biểu cho trường đại học...............................................................................33
2.2. Tình hình giải quyết bài toán lập thời khóa biểu..................................37
2.3. Xây dựng mô hình mạng Hopfield cho bài toán thời khóa biểu..........38
2.3.1. Mạng nơ ron Hopfield...................................................................38
2.3.2. Ánh xạ bài toán thời khóa biểu lên mạng nơ-ron Hopfield...........40
2.4. Thuật toán mạng nơ-ron Hopfield trong bài toán lập thời khóa biểu cho
trường Đại học.............................................................................................43
2.5. Kết luận chương 2................................................................................46
CHƯƠNG 3:
CÀI ĐẶT THỬ NGHIỆM..................................................47
3.1 Thiết kế chương trình ứng dụng mạng nơ ron Hopfield trong việc lập
thời khóa biểu cho trường đại học...............................................................47
3.2 Chuẩn bị dữ liệu....................................................................................50
3.3. Kết quả thử nghiệm..............................................................................50
3.4. Đánh giá kết quả...................................................................................51
KẾT LUẬN VÀ ĐỀ NGHỊ.............................................................................52
Kết quả đạt được của luận văn....................................................................52
Các định hướng nghiên cứu tiếp theo..........................................................52
TÀI LIỆU THAM KHẢO...............................................................................53
PHỤ LỤC........................................................................................................55
http://www.ictu.edu.vn
v
DANH MỤC CÁC BIỂU ĐỒ, HÌNH VẼ
Hình 1.1. Mô hình nơ-ron sinh học...................................................................6
Đồ thị hàm đồng nhất (Identity function)..........................................................8
Đồ thị hàm bước nhị phân (Binary step function).............................................8
Đồ thị hàm sigmoid...........................................................................................9
Đồ thị hàm sigmoid lưỡng cực........................................................................10
Hình 1.2. Mô hình một nơ-ron........................................................................11
Hình 1.3. Mạng truyền thẳng một lớp.............................................................13
Hình 1.4. Mạng truyền thẳng nhiều lớp..........................................................14
Hình 1.5. Mạng một lớp có nối ngược............................................................15
Hình 1.6. Mạng nhiều lớp có nối.....................................................................15
Hình 1.7. Mô hình mạng Hopfield..................................................................25
Đồ thị hàm Sigmoid........................................................................................28
Đồ thị hàm Hàm y=tanh(x).............................................................................28
Hình 3.1: Giao diện chương trình thời khóa biểu............................................48
Hình 3.2: Danh sách các form dữ liệu.............................................................49
Hình 3.3: Minh họa tìm kiếm dữ liệu theo lớp................................................49
Hình 3.4: Nhập tham số công thức cho bài toán thời khóa biểu....................50
Hình 3.5: Minh họa kết quả sau khi xếp thời khóa biểu..................................50
1
http://www.ictu.edu.vn
MỞ ĐẦU
Nhờ các khả năng: học, nhớ lại và khái quát hóa từ các mẫu huấn luyện
hoặc dữ liệu, mạng nơ-ron nhân tạo trở thành một phát minh đầy hứa hẹn của
hệ thống xử lý thông tin. Các tính toán nơ-ron cho phép giải quyết tốt những
bài toán đặc trưng bởi một số hoặc tất cả các tính chất sau: sử dụng không
gian nhiều chiều, các tương tác phức tạp, chưa biết hoặc không thể biết về mặt
toán học giữa các biến. Ngoài ra phương pháp này còn cho phép tìm ra
nghiệm của nhưng bài toán đòi hỏi đầu vào là các cảm nhận của con người
như: tiếng nói, nhìn và nhận dạng..
Bài toán lập thời khóa biểu đại học là một bài toán tối ưu dạng NP-hard
và tìm được một thời khóa biểu có chất lượng tốt là một thử thách thực sự.
Bài toán với một số lượng lớn các sự kiện và bao gồm nhiều ràng buộc cứng
khác nhau để thực hiện việc tìm kiếm thời khóa biểu tối ưu là phức tạp và tốn
nhiều thời gian. Để xử lý độ phức tạp của bài toán và để cung cấp việc tự
động hỗ trợ con người trong xếp thời khóa biểu, đã có nhiều cách tiếp cận
trong các tài liệu tập trung vào bài toán này. Những công việc nghiên cứu thể
hiện trong luận văn nhằm xây dựng theo tình trạng phát biểu tìm kiếm phương
pháp luận cho bài toán thời khóa biểu. Nghiên cứu tập trung vào phần xếp lịch
dạy của thời khóa biểu nhằm đảm bảo lớp - giáo viên - phòng học tránh bị
xung đột. Các tính toán nơ-ron cho phép giải quyết tốt các bài toán có nhiều
tương tác phức tạp. Vì vậy, ứng dụng mạng nơ-ron Hopfield trong bài toán
thời khóa biểu sẽ hứa hẹn là một giải pháp hiệu quả góp phần nâng cao khả
năng xếp thời khóa biểu nhờ tính hội tụ nhanh đến một trạng thái ổn định của
mạng nơ-ron Hopfield.
Trên thế giới, đã có một số nghiên cứu ứng dụng mạng nơ-ron trong bài
toán xếp lịch thời khóa biểu cho trường đại học. Tuy nhiên, lĩnh vực này còn
khá mới mẻ và chưa được ứng dụng rộng rãi ở nước ta. Trong nước cũng chưa
http://www.ictu.edu.vn
2
có một tài liệu chính thống nào về lĩnh vực này. Với những ứng dụng ngày
càng rộng rãi của mạng nơ-ron, việc nghiên cứu và áp dụng vào bài toán thời
khóa biểu trở nên cấp thiết, và đang rất được quan tâm. Chính vì những lý do
trên em đã quyết định chọn đề tài: “Ứng dụng mạng nơ-ron Hopfield trong
việc lập thời khóa biểu cho trường đại học“ làm hướng nghiên cứu. Với
mục tiêu đưa những ý tưởng khác nhau nhằm tăng hiệu quả tổng quan với
thuật toán xếp thời khóa biểu và tìm cách ứng dụng vào thực tế.
Luận văn gồm 3 chương với các nội dung cơ bản sau:
Chương 1: Trình bày tổng quan về cơ sở mạng nơ-ron nhân tạo, và nêu
khái quát ứng dụng mạng nơ-ron trong bài toán xếp thời khóa biểu.
Chương 2: Trình bày phương pháp giải bài toán lập thời khóa biểu,
dùng mạng Hopfield sửa đổi nhằm giảm độ phức tạp và tăng tốc giải
bài toán, đưa ra những nhận xét về hiệu quả của các mô hình bài toán.
Chương 3: Thiết kế cài đặt thử nghiệm chương trình ứng dụng mạng
nơ-ron Hopfield cho bài toán lập thời khóa biểu, đánh giá về kết quả
đạt được.
Ngoài ra, luận văn còn phần phụ lục và tài liệu tham khảo kèm theo ở cuối đề
tài.
http://www.ictu.edu.vn
3
CHƯƠNG I
TỔNG QUAN VỀ MẠNG NƠ RON NHÂN TẠO
1.1. GIỚI THIỆU VỀ MẠNG NƠ-RON NHÂN TẠO
1.1.1 Lịch sử phát triển
Khái niệm mạng nơ-ron được bắt đầu vào cuối thế kỷ 19, đầu thế kỷ 20
do có sự tham gia của ba ngành Vật lý học, Tâm lý học và Thần kinh học. Các
nhà khoa học như Hermann Von Hemholtz, Earnst Mach, Ivan Pavlov với các
công trình nghiên cứu đi sâu vào lý thuyết tổng quát mô tả hoạt động của trí
tuệ con người như: Học, nhìn, và lập luận, .. nhưng không đưa ra được mô
hình toán học cụ thể mô tả hoạt động của nơ-ron.
Về lịch sử, quá trình nghiên cứu và phát triển mạng nơ-ron nhân tạo có
thể chia thành bốn giai đoạn như sau:
+ Giai đoạn một: Từ nghiên cứu của William (1890) về tâm lý học với
sự liên kết các nơ-ron thần kinh. Năm 1943, nhà thần kinh học Warren
MeCulloch và nhà logic học Walter Pitts đã chỉ ra rằng:về nguyên tắc mạng
các nơ-ron nhân tạo có thể được mô hình hoá như thiết bị ngưỡng (giới hạn)
để thực hiện tính toán bất kỳ một hàm số học hay các phép tính logic nào.
Tiếp theo hai ông là Donald Hebb với giải thuật huấn luyện mạng ra đời năm
1949.
+ Giai đoạn hai: Vào khoảng những năm 1960, một số mô hình nơ-ron
hoàn thiện hơn có tính ứng dụng thực tiễn đã được đưa ra như: mô hình
Perceptron của Frank Rosenblatt (1958), mô hình Adaline của Bernard
Widrow (1962). Trong đó mô hình Perceptron rất được quan tâm vì nguyên lý
đơn giản, nhưng nó cũng có hạn chế vì như Marvin Minsky và Seymour
Papert của MIT (Massachurehs Insritute of Technology) đã phát hiện ra và
http://www.ictu.edu.vn
4
chứng minh nó không dùng được cho các hàm logic phức (1969). Còn
Adaline là mô hình tuyến tính, tự chỉnh, được dùng rộng rãi trong điều khiển
thích nghi, tách nhiễu và vẫn phát triển cho đến nay.
+ Giai đoạn ba: Vào khoảng đầu thập niên 80, việc nghiên cứu mạng
nơ-ron diễn ra rất mạnh mẽ cùng với sự ra đời của máy tính cá nhân PC.
Những đóng góp lớn cho mạng nơ-ron trong giai đoạn này phải kể đến
Stephen Grossberg, Teuvo Kohonen, Rumelhart và John Hopfield. Trong đó
đóng góp lớn của nhà vật lý học người Mỹ John Hopfield gồm hai mạng phản
hồi: Mạng rời rạc năm 1982 và mạng liên tục năm 1984. Đặc biệt, ông đã dự
kiến nhiều khả năng tính toán lớn của mạng mà một nơ-ron không có khả
năng đó. Cảm nhận của Hopfield đã được Rumelhart, Hinton và Williams đề
xuất thuật toán sai số truyền ngược (back –propagation) nổi tiếng để huấn
luyện mạng nơ-ron nhiều lớp nhằm giải bài toán mà mạng khác không thực
hiện được. Nhiều ứng dụng mạnh mẽ của mạng nơ-ron ra đời cùng với các
mạng theo kiểu máy Boltzmann và mạng Neocognition của Fukushima.
+ Giai đoạn bốn: từ năm 1987 - đến nay, hàng năm thế giới đều mở hội
nghị toàn cầu chuyên ngành nơ-ron IJCNN (International Joint Conference on
Neural Networks). Rất nhiều công trình được nghiên cứu để ứng dụng mạng
nơ-ron vào các lĩnh vực cuộc sống, ví dụ như: Kỹ thuật tính, tối ưu, sinh học, y
học, thống kê, giao thông, hoá học… Cho đến nay, mạng nơ-ron đã tìm được và
khẳng định được vị trí của mình trong rất nhiều ứng dụng khác nhau.
1.1.2. Mô hình mạng nơ-ron nhân tạo
1.1.2.1. Nơ-ron sinh học
Bộ não con người có khoảng 1010 tế bào thần kinh liên kết chặt chẽ với
nhau được gọi là các nơ-ron. Mỗi nơ-ron gồm có ba phần: Thân nơ-ron với nhân
ở bên trong (soma), một đầu sợi trục thần kinh ra (axon) và một hệ thống tế bào
hình cây (dendrite). Tế bào hình cây có nhiệm vụ mang các tín hiệu điện tới các
http://www.ictu.edu.vn
5
tế bào thân, tế bào thân sẽ thực hiện gộp (Sum) và phân ngưỡng ( Thresholds)
các tín hiệu đến. Sợi trục thần kinh làm nhiệm vụ đưa các tín hiệu thân ra ngoài
Trong thực tế có rất nhiều dây thần kinh vào và chúng bao phủ một diện
tích rất lớn (0.25 mm2) để nhận các tín hiệu từ các nơ-ron khác. Đầu thần kinh ra
được rẽ nhánh nhằm chuyển giao tín hiệu từ thân nơ-ron tới nơ-ron khác. Các
nhánh của đầu thần kinh được nối với các khớp thần kinh (synapse). Các khớp
thần kinh này được nối với thần kinh vào của các nơ-ron khác. Sự sắp xếp của
các nơ-ron và mức độ mạnh yếu của các khớp thần kinh được quyết định bởi quá
trình hóa học phức tạp, sẽ thiết lập chức năng của mạng nơ-ron, các nơ-ron có
thể sửa đổi tín hiệu tại các khớp, trong các nơ-ron nhân tạo được gọi là trọng số.
Có thể nói, mạng nơ-ron sinh học hoạt động chậm hơn rất nhiều so với
các linh kiện điện tử (10-3 giây so với 10-9 giây), nhưng bộ não có thể thực hiện
nhiều công việc nhanh hơn rất nhiều so với máy tính thông thường. Do cấu trúc
song song của mạng nơ-ron sinh học thể hiện toàn bộ các nơ-ron thực hiện đồng
thời tại một thời điểm. Mạng nơ-ron nhân tạo cũng có được đặc điểm này. Các
mạng nơ-ron nhân tạo chủ yếu thực nghiệm trên các máy tính mạnh có vi mạch
tích hợp rất lớn, các thiết bị quang, bộ xử lý song song. Điều này cũng giải thích
tại sao những nghiên cứu khoa học về mạng nơ-ron nhân tạo có điều kiện phát
triển cùng với sự phát triển về kỹ thuật công nghệ phần cứng máy tính.
Có nhiều loại nơ-ron khác nhau về kích thước và khả năng thu phát tín
hiệu. Tuy nhiên, chúng có cấu trúc và nguyên lý hoạt động chung.
Hình vẽ (1.1) là một hình ảnh đơn giản hoá của một loại nơ-ron như vậy.
http://www.ictu.edu.vn
6
Hình 1.1. Mô hình nơ-ron sinh học
- Hoạt động của nơ-ron sinh học có thể mô tả tóm tắt như sau:
Mỗi nơ-ron nhận tín hiệu vào từ các tế bào thần kinh khác.Chúng tích
hợp các tín hiệu vào, khi tổng tín hiệu vượt quá một ngưỡng nào đó chúng tạo
tín hiệu ra và gửi tín hiệu này tới các nơ-ron khác thông qua dây thần kinh.
Các nơ-ron liên kết với nhau thành mạng. Mức độ bền vững của các liên kết
này xác định một hệ số gọi là trọng số liên kết.
1.1.2.2. Nơ-ron nhân tạo
Để mô phỏng các tế bào thần kinh và các khớp nối thần kinh của bộ
não con người, mạng nơ-ron nhân tạo có các thành phần có vai trò tương tự là
các nơ-ron nhân tạo và kết nối giữa chúng (kết nối này gọi là weights). Nơron là một đơn vị tính toán có nhiều đầu vào và một đầu ra, mỗi đầu vào đến
từ một khớp nối thần kinh (synapse). Đặc trưng của nơ-ron là một hàm kích
hoạt phi tuyến chuyển đổi một tổ hợp tuyến tính của tất cả các tín hiệu đầu
vào thành tín hiệu đầu ra.
Một nơ-ron nhân tạo là một đơn vị tính toán hay đơn vị xử lý thông tin
cơ sở cho hoạt động của một mạng nơ-ron.
Các thành phần cơ bản của một mô hình nơ-ron
http://www.ictu.edu.vn
7
Trọng số và tổng tín hiệu đầu vào:
Mỗi nơ-ron có rất nhiều dây thần kinh vào, nghĩa là mỗi nơ-ron có thể
tiếp nhận đồng thời nhiều tín hiệu. Giả sử tại nơ-ron i có N tín hiệu vào, mỗi
tín hiệu vào S j được gán một trọng số Wij tương ứng. Ta ước lượng tổng tín
hiệu đi vào nơ-ron
net i
theo một số dạng sau:
(i)Dạng tuyến tính:
N
neti Wij s j
(1.1)
j 1
(ii)Dạng toàn phương:
N
neti Wij s 2j
(2.2)
j 1
(iii)Dạng mặt cầu:
neti
2
N
s
j 1
j
w ij
2
(3.3)
Trong đó: và w ij j 1, N lần lượt là tâm và bán kính mặt cầu
Hàm kích hoạt (hàm chuyển):
Hầu hết các đơn vị trong mạng nơ-ron chuyển net input bằng cách sử dụng
một hàm vô hướng (scalar – to – scalar function) gọi là hàm kích hoạt, kết quả
của hàm này là một giá trị gọi là mức độ kích hoạt của đơn vị. Trừ khả năng
đơn vị đó thuộc lớp ra, giá trị kích hoạt được đưa vào một hay nhiều đơn vị
khác. Các hàm kích hoạt thường bị ép vào một khoảng giá trị xác định, do đó
thường được gọi là các hàm nén (squashing).
Hàm biến đổi tín hiệu đầu vào net cho tín hiệu đầu ra out được gọi là hàm
kích hoạt. Hàm này có đặc điểm là không âm và bị chặn, dùng để giới hạn biên
http://www.ictu.edu.vn
8
độ đầu ra của nơ-ron. Có nhiều dạng hàm kích hoạt, người ta thường sử dụng
một hàm kích hoạt chung cho toàn mạng.
Một số hàm kích hoạt thường được sử dụng
1) Hàm đồng nhất (Linear function, Identity function)
g(x) = x
(1.3)
Nếu coi các đầu vào là một đơn vị thì chúng sẽ sử dụng hàm này. Có khi một
hằng số được nhân với net-input tạo thành một hàm đồng nhất.
Đồ thị hàm đồng nhất (Identity function)
2) Hàm bước nhị phân (Binary step function, Hard limit function)
Hàm này còn gọi là hàm ngưỡng (Threshold function hay Heaviside
function). Đầu ra của hàm này giới hạn một trong hai giá trị:
1, ne�
ux
g( x )
u x
0, ne�
ở đây là ngưỡng.
Đồ thị hàm bước nhị phân (Binary step function)
(1.4)
http://www.ictu.edu.vn
9
Dạng hàm này thường sử dụng trong mạng một lớp. Trong hình vẽ được
chọn bằng 1.
3) Hàm sigmoid (Sigmoid function (logsig))
Hàm sigma là dạng chung nhất của hàm kích hoạt được sử dụng trong
cấu trúc mạng nơ-ron nhân tạo. Nó là một hàm tăng và nó thể hiện một sự
trung gian giữa tuyến tính và phi tuyến. Một ví dụ của hàm này là hàm
logistics, xác định như sau:
g( x )
1
1 e x
(1.5)
ở đó là tham số độ dốc của hàm sigma. Bằng việc biến đổi tham số ,
chúng ta thu được các hàm sigma với các độ dốc khác nhau. Thực tế, hệ số
góc tại x= 0 là /4. Khi tham số hệ số góc tiến tới không xác định, hàm sigma
trở thành một hàm ngưỡng đơn giản. Trong khi một hàm ngưỡng chỉ có giá
trị là 0 hoặc 1, thì một hàm sigma nhận các giá trị từ 0 tới 1. Cũng phải ghi
nhận rằng hàm sigma là hàm phân biệt, trong khi hàm ngưỡng thì không
(Tính phân biệt của hàm là một đặc tính quan trọng trong lý thuyết mạng
neuron). Hàm này thường được dùng cho các mạng được huấn luyện (trained)
bởi thuật toán lan truyền ngược (back –propagation), bởi nó dễ lấy đạo hàm,
làm giảm đáng kể tính toán trong quá trình huấn luyện. Hàm được dùng cho
các chương trình ứng dụng mà đầu ra mong muốn rơi vào khoảng [0,1].
Đồ thị hàm sigmoid
http://www.ictu.edu.vn
10
4) Hàm sigmoid lưỡng cực (Bipolar sigmoid function (tan(sig))
g( x )
1 e x
1 e x
(1.6)
Hàm này có đặc tính tương tự hàm sigmoid. Hàm làm việc tốt đối với các ứng
dụng có đầu ra yêu cầu trong khoảng [-1,1].
Đồ thị
hàm
sigmoid
lưỡng cực
Các hàm chuyển của các đơn vị ẩn (hidden units) là cần thiết để biểu diễn sự
phi tuyến vào trong mạng.
Nút bias:
Là một nút thêm vào nhằm tăng khả năng thích nghi của mạng nơ-ron
trong quá trình học. Trong các mạng nơ-ron có sử dụng bias, mỗi nơ-ron có
thể có một trọng số tương ứng với bias. Trọng số này luôn có giá trị là 1.
Mô hình của một nút xử lý (nút thứ i):
Vi
Vj
Wi1
Wij
WiN
Ui= V =f (U )
i
i
i
Vi
VN
Hình 1.2. Mô hình một nơ-ron
http://www.ictu.edu.vn
11
N
U i Wij Vj θ i
j 1
j #i
Vi f i U i
(1.7)
(1.8)
Trong đó:
Ui : là tín hiệu vào tại nơ-ron i
Vi : là tín hiệu ra tại nơ ron i
Wij : là trọng số liền kề từ nơ-ron j đến nơ-ron i
i : là ngưỡng (đầu vào ngoài) kích hoạt nơ-ron i.
fi : là hàm kích hoạt của nơ-ron i
1.1.2.3. Mạng nơ-ron nhân tạo
Mạng nơ-ron nhân tạo (gọi tắt là mạng nơ-ron) là mô hình toán học hay
mô hình tính toán được xây dựng dựa trên các mạng nơ-ron sinh học. Nó gồm
có một nhóm các nơ-ron nhân tạo(nút) nối với nhau, và xử lý thông tin bằng
cách truyền theo các kết nối và tính giá trị mới tại các nút (cách tiếp cận
connectionism đối với tính toán). Phần lớn mạng nơ-ron nhân tạo là một hệ
thống thích ứng (adaptive system) tự thay đổi cấu trúc của mình dựa trên các
thông tin bên ngoài hay bên trong chảy qua mạng trong quá trình học.
Với việc giả lập các hệ thống sinh học, các cấu trúc tính toán, mạng nơron có thể giải quyết được các lớp bài toán nhất định, như: Bài toán người du
lịch, bài toán tô màu bản đồ, bài toán xếp loại, bài toán lập thời khóa biểu, bài
toán tìm kiếm, bài toán nhận dạng mẫu... Các bài toán phức tạp cao, không
xác định. Tuy nhiên, sự liên kết giữa một bài toán bất kỳ trong thực tế với một
giải pháp mạng nơ-ron lại là một việc không dễ dàng.
Xét một cách tổng quát, mạng nơ-ron là một cấu trúc xử lý song song
thông tin phân tán mang các đặc tính nổi bật sau :
http://www.ictu.edu.vn
12
Là mô hình toán học dựa trên bản chất của nơ-ron.
Bao gồm một số lượng rất lớn các nơ-ron liên kết với nhau.
Mạng nơ-ron có khả năng học, khái quát hóa tập dữ liệu học
thông qua việc gán và hiệu chỉnh các trọng số liên kết.
Tổ chức theo kiểu tập hợp mang lại cho mạng nơ-ron khả năng
tính toán rất lớn, trong đó không có nơ-ron nào mang thông tin
riêng biệt.
Ví dụ : Hình 1.2, 1.3,1.4, 1.5 là một số mô hình mạng thông dụng.
Các hình trạng của mạng
Hình trạng mạng được định nghĩa bởi: số lớp (layers), số đơn vị trên
mỗi lớp, và sự liên kết giữa các lớp đó. Các mạng thường được chia làm hai
loại dựa trên cách thức liên kết các đơn vị:
1.1.2.3.1. Mạng truyền thẳng
- Mạng truyền thẳng một lớp
Mạng perceptron một lớp do F.Rosenblatt đề xuất năm 1960 là mạng
truyền thẳng chỉ một lớp vào và một lớp ra không có lớp ẩn. Trên mỗi lớp này
có thể có một hoặc nhiều nơ-ron. Mô hình mạng nơ-ron của F.Rosenblatt sử
dụng hàm ngưỡng đóng vai trò là hàm chuyển. Do đó, tổng của tín hiệu vào
lớn hơn giá trị ngưỡng thì giá trị đầu ra của nơ-ron sẽ là 1, còn trái lại sẽ là 0.
1, ne�
u neti
outi
u neti
0 , ne�
Với neti =
(1.9)
wij x j là tổng thông tin đầu vào của nơ-ron i.
Mô hình mạng nơ-ron truyền thẳng một lớp là mô hình liên kết cơ bản
và đơn giản nhất. Các nơ-ron tổ chức lại với nhau tạo thành một lớp, đường
truyền tín hiệu được truyền theo một hướng nhất định nào đó. Các đầu vào
http://www.ictu.edu.vn
13
được nối với các nơ-ron theo các trọng số khác nhau, sau quá trình xử lý cho
ra một chuỗi các tín hiệu ra.
x1
y1
x2
y2
Xm
yn
Hình 1.3. Mạng truyền thẳng một lớp
Với mỗi giá trị đầu vào.
x x1, x2 , ..., xn
T
. Qua quá trình xử lý của
mạng ta sẽ thu được một bộ tương ứng các giá trị đầu ra là
y y1, y 2, ..., y n
T
được xác định như sau :
m
yi f i wij x j i , i 1, n
j 1
(1.10)
Trong đó :
m : Số tín hiệu vào
n : Số tín hiệu ra
: Wi T wi1 , wi 2 ,..., win T là véc tơ trọng số của nơ-ron thứ i.
f i : Là hàm kích hoạt nơ-ron thứ i
i : Là ngưỡng của nơ-ron thứ i.
Ngay từ khi mạng Perceptron được đề xuất nó được sử dụng để giải quyết bài
toán phân lớp. Một đối tượng sẽ được nơ-ron i phân vào lớp A nếu:
http://www.ictu.edu.vn
Tổng thông tin đầu vào
14
wij x j > i
Trong trường hợp trái lại nơ-ron sẽ được phân vào lớp B.
- Mạng truyền thẳng nhiều lớp (Multilayer Perceptron –MLP)
Với mạng nơ-ron truyền thẳng một lớp ở trên, khi phân tích một bài
toán phức tạp sẽ gặp rất nhiều khó khăn, để khắc phục vấn đề này người ta
đưa ra mô hình mạng nơ-ron truyền thẳng nhiều lớp bằng việc kết hợp một số
lớp nơ-ron lại với nhau. Lớp nhận tín hiệu vào gọi là lớp vào, lớp đưa tín hiệu
ra của mạng được gọi là lớp ra. Các lớp ở giữa lớp vào và lớp ra được gọi là
lớp ẩn và các nơ-ron trong các lớp ẩn có hàm chuyển (hàm kích hoạt) dạng
phi tuyến. Mạng nơ-ron nhiều lớp có thể giải quyết các bài toán phi tuyến nhờ
vào các lớp ẩn. Càng nhiều lớp ẩn thì khả năng mở rộng thông tin càng cao và
xử lý tốt mạng có nhiều lớp vào và lớp ra.
Hình (1.4) mô tả cấu trúc của mạng nơ-ron truyền thẳng nhiều lớp.
x1
Lớp vào
Lớp ẩn
Lớp ra
x2
xm
y1
y2
yn
Hình 1.4. Mạng truyền thẳng nhiều lớp
1.1.2.3.2. Mạng hồi quy (Recurrent Neutral Network)
Mạng hồi quy một lớp có nối ngược
X1
Y1
X2
...
XN
Y2
...
...
YM
http://www.ictu.edu.vn
15
Hình 1.5. Mạng một lớp có nối ngược
Mạng hồi quy nhiều lớp có nối ngược.
X1
Y1
X2
...
Y2
...
...
...
X
N
Y
Hình 1.6. Mạng nhiều lớp có nối
M
1.1.2.4. Luật học
Tiến trình học là tiến trình quan trọng của con người, nhờ học mà bộ
não ngày càng tích lũy các kinh nghiệm để thích nghi với môi trường và xử lý
tình huống tốt hơn. Mạng nơ-ron xây dựng lại cấu trúc bộ não thì phải cần có
khả năng nhận biết dữ liệu thông qua tiến trình học, với các thông số tự do
của mạng có thể thay đổi liên tục bởi những thay đổi của môi trường và mạng
nơ-ron ghi nhớ giá trị đó.
Trong quá trình học, giá trị đầu vào được đưa vào mạng và theo dòng
chảy trong mạng tạo thành giá trị đầu ra.
Tiếp đến là quá trình so sánh giá trị tạo ra bởi mạng nơ-ron với giá trị
mong muốn. Nếu hai giá trị này giống nhau thì không thay đổi gì cả. Tuy
nhiên, nếu có một sai lệch giữa hai giá trị này vượt quá giá trị sai số mong
muốn thì đi ngược mạng từ đầu ra về đầu vào để thay đổi một số kết nối.
Đây là quá trình lặp lại liên tục và có thể không dừng khi không tìm
được giá trị W sao cho đầu ra tạo bởi mạng nơ-ron bằng đúng đầu ra mong
muốn. Do đó trong thực tế người ta phải thiết lập một số tiêu chuẩn dựa trên
http://www.ictu.edu.vn
16
một giá trị sai số nào đó của hai giá trị này, hay dựa trên một số lần lặp nhất
định.
Để tiện cho việc trình bày, ta kí hiệu y là giá trị kết xuất của mạng nơron, t là giá trị ra mong muốn, e là sai lệch giữa hai giá trị này.:
e=t-y
Mạng nơ-ron có một số ưu điểm so với máy tính truyền thống. Cấu trúc
song song của mạng nơ-ron rất thích hợp cho những ứng dụng đòi hỏi tốc độ
nhanh theo thời gian thực. Khả năng huấn luyện của mạng nơ-ron có thể khai
thác để phát triển hệ thống thích nghi. Mặt khác, với khả năng tổng quát hóa
của mạng nơ-ron, nó có thể áp dụng để điều khiển nhiều tham số phức tạp
đồng thời từ đó giải quyết dễ dàng một số bài toán thuộc lớp bài toán NP- đầy
đủ (NP-Complete ).
Các luật học đóng vai trò quan trọng trong việc xác định một mạng
nơ-ron nhân tạo. Một cách đơn giản về khái niệm học của mạng nơ-ron là cập
nhật trọng số trên cơ sở các mẫu. Theo nghĩa rộng thì học có thể được chia ra
làm hai loại: Học tham số và học cấu trúc.
- Học tham số: Các thủ tục học này nhằm tìm kiếm ma trận trọng số sao
cho mạng có khả năng đưa ra dự báo sát với thực tế. Dạng chung của luật học
tham số có thể được mô tả như sau:
Wij rx j , i 1, N , j 1, M
(1.11)
trong đó:
Wij : là sự thay đổi trọng số liên kết từ nơ ron j đến nơ ron i.
x j : là tín hiệu vào nơ ron j.
: là tốc độ học, nằm trong khoảng (0,1).
r : là hằng số học.
Vấn đề đặt ra ở đây là tín hiệu học r được sinh ra như thế nào để hiệu
chỉnh trọng số của mạng.
http://www.ictu.edu.vn
17
Có thể chia thủ tục học tham số ra thành ba lớp học nhỏ hơn: Học có
chỉ đạo, học tăng cường và học không chỉ đạo. Việc xác định r tùy thuộc vào
từng kiểu học.
+ Học có tín hiệu chỉ đạo: Là quá trình mạng học dựa vào sai số giữa
đầu ra thực và đầu ra mong muốn để làm cơ sở cho việc hiệu chỉnh trọng số.
Sai số này chính là hằng số học r. Luật học điển hình của nhóm này là luật
học Delta của Widrow (1962) nêu ra đầu tiên dùng để xấp xỉ trọng của
Adaline dựa trên nguyên tắc giảm gradient.
Trong nhóm luật học này cũng cần phải kể đến luật học Perceptron của
Rosenblatt (1958). Về cơ bản luật học này thay đổi các giá trị trọng trong thời
gian học, còn luật Perceptron thì thêm hoặc bỏ trọng tùy theo giá trị sai số
dương hay âm.
Một loạt các luật học khác cũng được dựa trên tư tưởng này. Luật Oja
là cải tiến và nâng cấp của luật Delta. Luật truyền ngược là luật mở rộng của
luật Delta cho mạng nhiều lớp. Đối với mạng truyền thẳng thường sử dụng
luật truyền ngược để chỉnh trọng với tín hiệu chỉ đạo từ bên ngoài và người ta
gọi mạng này là mạng lan truyền ngược.
+ Học không có tín hiệu chỉ đạo: Luật học này sử dụng đầu ra của
mạng làm cơ sở để hiệu chỉnh các trọng số liên kết. Hay trong luật này chính
là tín hiệu ra của mạng. Điển hình là luật Hebb (1949) thường dùng cho các
mạng tự liên kết, luật LVQ (Learning Vector Quantization) dùng cho mạng tự
tổ chức một lớp thuộc lớp mạng ánh xạ đặc trưng của Kohonen.
Luật học Hebb là luật sinh học xuất phát từ tiên đề của Hebb cho rằng:
Giữa hai nơ-ron có quan hệ và có thay đổi thế năng thì giữa chúng có sự thay
đổi trọng số liên kết. Nói cách khác, trọng số được điều chỉnh theo mối tương
quan trước và sau, nghĩa là:
- Xem thêm -