Tóm tắt Luận văn - Ứng dụng mạng nơ ron hopfield giải bài toán lập thời khóa biểu

..................................... Phản biện 2:......................................................................................... Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn họp tại: Vào hồi...... giờ...... ngày....... tháng........ năm 2011. Cĩ thể tìm hiểu luận văn tại trung tâm học liệu ðại học Thái Nguyên Và thư viện Trường/Khoa: . Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên i LỜI CẢM ƠN Xin chân thành cảm ơn Thầy PGS TS. Đặng Quang Á đã tận tình chỉ dạy, hướng dẫn tơi trong suốt thời gian học tập và làm luận văn. Tơi cũng xin biết ơn chân thành đến các Thầy giáo Viện Cơng nghệ Thơng tin đã giảng dạy, giúp đỡ trong suốt thời gian học tập. Xin cảm ơn tất cả các anh chị học viên Cao học khĩa 8, cám ơn các cán bộ cơng chức, giảng viên Khoa Cơng nghệ thơng tin- ĐH Thái Nguyên đã tạo điều kiện tốt cho tơi trong suốt trong hai năm học qua. Xin cám ơn các bạn bè, đồng nghiệp đã chỉ bảo tơi rất nhiều trong thời gian thực hiện luận văn này. Cuối cùng, xin chân thành cảm ơn các thành viên trong gia đình đã động viên và tạo mọi điều kiện thuận lợi để tơi cĩ được kết quả như ngày hơm nay. THÁI NGUYÊN 10/2011 Người viết luận văn Hà Tuấn Việt Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên ii LỜI CAM ĐOAN Tơi xin cam đoan đề tài luận văn “ Ứng dụng mạng nơ-ron Hopfield giải bài tốn thời khĩa biểu” là cơng trình nghiên cứu của bản thân tơi. Các số liệu, kết quả nghiên cứu nêu trong luận văn này là trung thực và chưa từng được ai cơng bố trong một cơng trình nào khác. Tơi xin chịu trách nhiệm về luận văn của mình. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 tố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 tốn tối ưu................................................ 28 1.3.4. Mạng Hopfield với bài tố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 TỐN LẬP THỜI KHĨA BIỂU CHO TRƯỜNG ĐẠI HỌC...................................................... 33 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên iv 2.1 Bài tố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 tố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 tốn thời khĩa biểu.......... 38 2.3.1. Mạng nơ ron Hopfield................................................................... 38 2.3.2. Ánh xạ bài tốn thời khĩa biểu lên mạng nơ-ron Hopfield .......... 40 2.4. Thuật tốn mạng nơ-ron Hopfield trong bài tố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 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 tố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 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 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 tốn nơ-ron cho phép giải quyết tốt những bài tố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 tốn học giữa các biến. Ngồi ra phương pháp này cịn cho phép tìm ra nghiệm của nhưng bài tố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 tốn lập thời khĩa biểu đại học là một bài tố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 tố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 tố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 tố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 tố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 tốn nơ-ron cho phép giải quyết tốt các bài tố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 tố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 tố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 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 chưa 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 tố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 tố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 tốn xếp thời khĩa biểu. Chương 2: Trình bày phương pháp giải bài tố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 tốn, đưa ra những nhận xét về hiệu quả của các mơ hình bài tố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 tốn lập thời khĩa biểu, đánh giá về kết quả đạt được. Ngồ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. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 tố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 hố như thiết bị ngưỡng (giới hạn) để thực hiện tính tố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 hồ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à Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 tố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 tố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 tố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ị tồ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, hố 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 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 ngồ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 tồ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 hố của một loại nơ-ron như vậy. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 tố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 tố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 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 jS được gán một trọng số ijW tương ứng. Ta ước lượng tổng tín hiệu đi vào nơ-ron inet theo một số dạng sau: (i)Dạng tuyến tính: 1 N i ij j j net W s = =∑ (1.1) (ii)Dạng tồn phương: 2 1 N i ij j j net W s = =∑ (2.2) (iii)Dạng mặt cầu: ( )22 ij 1 w N i j j net sρ = = − −∑ (3.3) Trong đĩ: ρ và ( )ijw 1,j 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 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 tồ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, ( ) 0, nếu x g x nếu x θ θ  ≥ =  < (1.4) ở đây θ là ngưỡng. Đồ thị hàm bước nhị phân (Binary step function) Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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: 1( ) 1 x g x e λ− = + (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 tố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 tố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 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10 4) Hàm sigmoid lưỡng cực (Bipolar sigmoid function (tan(sig)) 1( ) 1 x x e g x e − − − = + (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=fi(Ui) Ui= ∑ Vi Vi Wi1 Vj VN Wij WiN Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11 Hình 1.2. Mơ hình một nơ-ron ∑ = += N ij j ijiji VWU # 1 θ (1.7) ( )iii UfV = (1.8) Trong đĩ: i U : là tín hiệu vào tại nơ-ron i i V : là tín hiệu ra tại nơ ron i ijW : là trọng số liền kề từ nơ-ron j đến nơ-ron i θ i : là ngưỡng (đầu vào ngồi) kích hoạt nơ-ron i. i f : 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 tốn học hay mơ hình tính tố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 tố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 ngồ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 tốn, mạng nơ- ron cĩ thể giải quyết được các lớp bài tốn nhất định, như: Bài tốn người du lịch, bài tốn tơ màu bản đồ, bài tốn xếp loại, bài tốn lập thời khĩa biểu, bài tốn tìm kiếm, bài tốn nhận dạng mẫu... Các bài tốn phức tạp cao, khơng Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 xác định. Tuy nhiên, sự liên kết giữa một bài tố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 :
Là mơ hình tố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 tố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, 0, i i i nếu net out nếu net θ θ  ≥ =  < (1.9) Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 Với neti = wij jx∑ 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 đượ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. Hình 1.3. Mạng truyền thẳng một lớp Với mỗi giá trị đầu vào. . 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à được xác định như sau : Trong đĩ : m : Số tín hiệu vào n : Số tín hiệu ra y1 yn y2 Xm x1 x2 [ ]Tnyyyy ...,,2,1= nixwfy m j ijijii ,1, 1 =        −= ∑ = θ (1.10) [ ]Tnxxxx ...,,2,1= Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 [ ]TiniiTi wwwW ,...,, 21= : là véc tơ trọng số của nơ-ron thứ i. if : 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 tốn phân lớp. Một đối tượng sẽ được nơ-ron i phân vào lớp A nếu : Tổng thơng tin đầu vào w ij j x∑ > 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 tố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 tố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. Hình 1.4. Mạng truyền thẳng nhiều lớp y y y xm x x Lớp vào Lớp ra Lớp ẩn Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 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 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. Hình 1.6. Mạng nhiều lớp cĩ nối 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ị đĩ. . . . . . . . . . X1 X2 XN Y1 Y2 YM Y1 Y2 Y . . . . . . X1 X2 X . . . . . . Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16 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 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 tốn thuộc lớp bài tố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. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17 - 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: trong đĩ: ∆ ijW : là sự thay đổi trọng số liên kết từ nơ ron j đến nơ ron i. j x : 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. 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