Khóa luận Mạng neural rbf và ứng dụng nhận dạng chữ viết tay

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Tiến Mười MẠNG NEURAL RBF VÀ ỨNG DỤNG NHẬN DẠNG CHỮ VIẾT TAY KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Tiến Mười MẠNG NEURAL RBF VÀ ỨNG DỤNG NHẬN DẠNG CHỮ VIẾT TAY KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: PGS.TS Hoàng Xuân Huấn HÀ NỘI - 2009 LỜI CẢM ƠN Tôi muốn bày tỏ sự cảm ơn sâu sắc của mình tới thầy Hoàng Xuân Huấn, thuộc bộ môn Khoa học máy tính, khoa Công nghệ thông tin, trường Đại học Công nghệ, ĐHQGHN. Trong thời gian thực hiện khóa luận, thầy đã nhiệt tình hướng dẫn và giúp đỡ tôi rất nhiều. Ngoài thời gian tìm hiểu và cung cấp tài liệu, thầy cũng chỉ ra những vướng mắc trong qua trình làm, giúp đỡ tôi khắc phục để đạt hiệu quả cao hơn. Thầy cũng đã tận tình giúp đỡ tôi có một chỗ làm việc yên tĩnh trong suốt quá trình làm khóa luận. Tôi cũng muốn bày tỏ sự cảm ơn của mình tới các các thầy, các cô trong bộ môn, cũng như các thầy, các cô trong khoa, trường đã hết sức tạo điều kiện tốt và giúp đỡ cho tôi hoàn thành khóa luận của mình. TÓM TẮT NỘI DUNG Mặc dù đã được nghiên cứu từ rất lâu, nhưng đến nay bài toán nội suy và xấp xỉ hàm nhiều biến vẫn còn có rất ít công cụ toán học để giải quyết. Mạng Neural nhân tạo là một phương pháp hay để giải quyết bài toán nội suy, xấp xỉ hàm nhiều biến. Năm 1987 M.J.D. Powell đã đưa ra một cách tiếp cận mới để giải quyết bài toán nội suy hàm nhiều biến sử dụng kỹ thuật hàm cơ sở bán kính (Radial Basis Function - RBF), năm 1988 D.S. Bromhead và D. Lowe đề xuất kiến trúc mạng Neural RBF và đã trở một công cụ hữu hiệu để giải quyết bài toán nội suy và xấp xỉ hàm nhiều biến(xem [11]). Nội dung chính của khóa luận là trình bày khảo cứu về mạng Neural RBF để giải quyết bài toán nội suy, xấp xỉ hàm nhiều biến sau đó ứng dụng cơ sở lý thuyết trên để xây dựng phần mềm nhận dạng chữ số viết tay. MỤC LỤC MỞ ĐẦU................................................................................................................... 1 Chương 1 BÀI TOÁN NỘI SUY, XẤP XỈ HÀM SỐ VÀ MẠNG NEURAL RBF 1 1.1 PHÁT BIỂU BÀI TOÁN NỘI SUY VÀ XẤP XỈ HÀM SỐ ............................ 1 1.1.1 Bài toán nội suy.......................................................................................... 1 1.1.1.1 Nội suy hàm một biến số ...................................................................... 1 1.1.1.2 Bài toán nội suy hàm nhiều biến .......................................................... 2 1.1.2 Bài toán xấp xỉ ........................................................................................... 2 1.1.3 Các phương pháp giải quyết bài toán nội suy và xấp xỉ hàm số .................. 2 1.2 MẠNG NEURAL NHÂN TẠO ....................................................................... 3 1.2.1 Giới thiệu mạng Neural nhân tạo ................................................................ 3 1.2.1.1 Mạng Neural sinh học.......................................................................... 4 1.2.1.2 Mạng Neural nhân tạo ......................................................................... 5 1.3 MẠNG NEURAL RBF..................................................................................... 8 1.3.1 Giới thiệu mạng Neural RBF ...................................................................... 8 1.3.1.1 Bài toán nội suy nhiều biến và kỹ thuật hàm cơ sở bán kính................. 8 1.3.1.2 Kiến trúc mạng Neural RBF............................................................... 10 1.3.1.3 Ứng dụng của mạng Neural RBF ....................................................... 10 1.4 CÁC PHƯƠNG PHÁP HUẤN LUYỆN MẠNG NEURAL RBF ................... 11 1.4.1 Phương pháp huấn luyện một pha............................................................. 11 1.4.2 Phương pháp huấn luyện hai pha .............................................................. 12 1.4.3 Phương pháp huấn luyện 2 pha HDH ....................................................... 13 1.4.4 Phương pháp huấn luyện ba pha đầy đủ.................................................... 16 1.5 KẾT QUẢ THỰC NGHIỆM .......................................................................... 16 1.5.1 Kết quả..................................................................................................... 16 1.5.2 Nhận xét................................................................................................... 19 Chương 2 NHẬN DẠNG CHỮ VIẾT TAY........................................................... 20 2.1 NHẬN DẠNG MẪU ...................................................................................... 20 2.1.1 Nhận dạng mẫu ........................................................................................ 20 2.1.1.1 Mẫu là gì ? ........................................................................................ 20 2.1.1.2 Nhận dạng mẫu là gì ?...................................................................... 20 2.1.1.3 Lịch sử của lĩnh vực nhận dạng mẫu .................................................. 21 2.1.1.4 Ứng dụng của nhận dạng mẫu ........................................................... 21 2.1.1.5 Các bài toán nhận dạng mẫu ............................................................. 22 2.1.1.6 Các bước xử lý trong hệ thống nhận dạng mẫu ................................. 22 2.2 BÀI TOÁN NHẬN DẠNG CHỮ VIẾT TAY................................................. 24 2.2.1 Tình hình chung về nhận dạng chữ viết tay............................................... 24 2.2.2 Giới thiệu bài toán nhận dạng chữ viết tay................................................ 24 2.2.3 Hướng giải quyết cho bài toán nhận dạng ký tự viết tay ........................... 24 2.3 CÁC PHƯƠNG PHÁP TRÍCH CHỌN ĐẶC TRƯNG CHỮ VIẾT TAY ....... 25 2.2.1 Phương pháp trích chọn đặc trưng kết hợp biến đổi DCT và thuật toán phân tích thành phần chính PCA................................................................................ 25 2.2.1.1 Thuật toán PCA ................................................................................. 26 2.2.1.2 Phương pháp trích chọn đặc trưng kết phép biến đổi DCT và thuật toán PCA....................................................................................................... 27 2.2.2 Phương pháp trích đặc trưng sử dụng Momen Legendre ........................... 28 2.2.2.1 Momen và Momen Legendre ............................................................. 28 2.2.2.2 Phương pháp trích chọn đặc trưng chữ viết tay bằng Momen Legendre30 2.2.3 Phương pháp sử dụng mạng Neural nhân chập(Convolution neural network)............................................................................................................ 32 2.2.3.1 Khái niệm cơ sở ................................................................................. 32 2.2.3.2 Phương pháp trích đặc trưng sử dụng mạng Neural nhân chập ......... 33 2.4 THỰC NGHIỆM ............................................................................................ 34 2.4.1 Kết quả..................................................................................................... 35 2.4.2 Nhận xét................................................................................................... 35 Chương 3 CÁC PHƯƠNG PHÁP CẢI THIỆN HIỆU SUẤT CỦA MẠNG NEURAL RBF........................................................................................................ 36 3.1 CÁC PHƯƠNG PHÁP CẢI THIỆU HIỆU SUẤT CỦA MẠNG NEURAL RBF...................................................................................................................... 36 3.1 CÁC PHƯƠNG PHÁP CẢI THIỆU HIỆU SUẤT CỦA MẠNG NEURAL RBF...................................................................................................................... 36 3.1.1 Tăng tập dữ liệu huấn luyện ..................................................................... 36 3.1.1.1 Tăng tập dữ liệu bằng các phép biến đổi hình học ............................. 36 3.1.2 Phương pháp học tập hợp ......................................................................... 37 3.1.2.1 Phương pháp học tập hợp cải tiến...................................................... 38 3.1.3 Phương pháp tăng tốc độ nhận dạng ......................................................... 39 3.1.3.1 Phương pháp bộ nhận dạng ba lớp .................................................... 40 3.2 THỰC NGHIỆM ............................................................................................ 41 Chương 4 GIỚI THIỆU CHƯƠNG TRÌNH NHẬN DẠNG CHỮ SỐ VIẾT TAY VÀ TỔNG KẾT...................................................................................................... 42 4.1 GIỚI THIỆU CHƯƠNG TRÌNH NHẬN DẠNG CHỮ SỐ VIẾT TAY .......... 42 4.1.1 Chương trình nhận dạng chữ viết tay ........................................................ 42 4.1.1.1 Giới thiệu chương trình...................................................................... 42 4.2 TỔNG KẾT VÀ PHƯƠNG HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI ............... 43 4.2.1 Tổng kết ................................................................................................... 43 4.2.1.1 Những công việc đã làm được............................................................ 43 4.2.2.2 Hướng phát triển của đề tài ............................................................... 44 TÀI LIỆU THAM KHẢO...................................................................................... 45 BẢNG DANH MỤC CÁC HÌNH MINH HỌA Hình 1: Minh họa bài toán nội suy hàm một biến ..............................................................1 Hình 2: Minh họa một Neuron thần kinh sinh học.............................................................4 Hình 3: Cấu tạo một Neural nhân tạo ................................................................................5 Hình 4: Đồ thị hàm ngưỡng ..............................................................................................6 Hình 5: Đồ thị hàm tuyến tính...........................................................................................6 Hình 7: Đồ thị hàm tanh....................................................................................................6 Hình 8: Đồ thị hàm Gauss.................................................................................................7 Hình 9: Kiến trúc mạng Neural truyền tới .........................................................................7 Hình 10: Minh họa sự ảnh hưởng của hàm bán kính .........................................................9 Hình 11: Kiến trúc của mạng RBF ..................................................................................10 Hình 12: Quá trình hội tụ đến giá trị cực tiểu của thuật toán Gradient .............................12 Hình 13: Thuật toán HDH huấn luyện mạng RBF...........................................................15 Hình 14: Các bước xử lý trong hệ thống nhận dạng mẫu .................................................22 Hình 15 : Các bước giải quyết bài toán nhận dạng chữ viết tay .......................................25 Hình 16: Ảnh hưởng của vector riêng, giá trị riêng lên tập dữ liệu ..................................26 Hình 17 : Các bước thực hiện của thuật toán PCA ..........................................................27 Hình 18: Các bước trích chọn đặc trưng bằng biến DCT kết hợp PCA ............................27 Hình 19: Biến đổi DCT và cách lấy dữ liệu theo đường zigzag .......................................28 Hình 21: Các bước thực hiện của phương pháp trích chọn đặc trưng sử dung momen Legendre.........................................................................................................................32 Hình 22: Thao tác nhân chập ..........................................................................................33 Hình 23: Quá trình trích chọn đặc trưng sử dụng mạng Neural nhân chập.......................34 Hình 24: Minh họa quá trình lấy đặc trưng bằng mạng Neuron nhân chập ......................34 Hình 21: Ma trận vector cho phép biến đổi Elastic ..........................................................37 Hình 22: Ví dụ về phép biến đổi Elastic..........................................................................37 Hình 23: Kiến trúc của phương pháp học tập hợp cải tiến ...............................................39 Hình 24: Kiến trúc của bộ nhận dạng ba lớp ...................................................................40 Hình 25: Biểu đồ so sánh độ chính xác nhận dạng và thời gian huấn luyện của các phương pháp huấn luyện khác nhau ................................................................................41 Hình 26: Giao diện chính của chương trình.....................................................................43 Hình27: Bảng thông báo kết quả nhận dạng ....................................................................43 BẢNG DANH MỤC TỪ VIẾT TẮT Ký hiệu Nghĩa tiếng Anh Nghĩa tiếng Việt ANN Artificial neural network Mạng nơ-ron nhân tạo DCT Discrete cosin transform Biến đổi cosin rời rạc IDE Integrated Development Environment Môi trường thiết kế hợp nhất MLP Multi layer perceptron Mạng nơ-ron truyền thẳng nhiều tầng PCA Principal component analysis Phân tích thành phần chính PDA Personal Digital Assistant Thiết bị hỗ trợ cá nhân(thường ám chỉ các máy tính cầm tay) RBF Radial Basis Function Hàm cơ sở bán kính SVM Support Vector Machine Máy vec-tơ hỗ trợ MỞ ĐẦU Bài toán nội suy và xấp xỉ hàm số đã được biết đến từ lâu vì nó có ứng dụng trong rất nhiều lĩnh vực trong khoa học kỹ thuật cũng như đời sống. Ngày nay bài toán nội suy và xấp xỉ hàm nhiều biến đã trở thành một vấn đề thời sự vì để giải quyết được các bài toán ứng dụng (ví dụ trong nhận dạng mẫu) nhiều khi buộc con người phải giải quyết được bài toán nội suy, xấp xỉ hàm nhiều biến. Trong toán học bài toán nội suy, xấp xỉ hàm một biến đã được giải quyết khá đầy đủ bằng rất nhiều các phương pháp khác nhau. Tuy nhiên bài toán nội suy, xấp xỉ hàm nhiều biến thì các công cụ toán học vẫn còn rất hạn chế. Khái niệm mạng “Neural nhân tạo” xuất hiện đầu thế kỷ 20 trong thời kỳ con người tìm cách để chế tạo ra những bộ máy có khả năng suy nghĩ, tư duy như con người. Trải qua một thời gian dài phát triển và nghiên cứu thì cơ sở lý thuyết cũng như thực nghiệm về mạng Neural nhân tạo đã đạt được những kết quả rất khả quan. Nhờ khả tính toán mạnh của máy tính, mạng Neural nhân tạo ngày nay là một công cụ rất tốt để giải quyết bài toán nội suy và xấp xỉ hàm nhiều biến. Vì thế mạng Neural nhân tạo được sử dụng rất nhiều trong các lĩnh vực tính toán, nhận dạng mẫu cũng như trong các lĩnh vực khoa học quan trọng khác (xem [11]-chapter 4). Là một loại mạng Neural nhân tạo, mạng Neural RBF cũng là một công cụ hiệu quả để giải quyết bài toán nội suy và xấp xỉ hàm nhiều biến với điểm mạnh hơn hẳn các loại mạng Neural khác ở chỗ nó có thời gian huấn luyện rất nhanh. Bài toán nhận dạng chữ viết tay là một bài toán quen thuộc và có ứng dụng rất lớn trong thực tế vì thế từ lâu nó đã thu hút rất nhiều người nghiên cứu. Mặc dù đã đạt được những kết quả rất cao trong bài toán nhận dạng chữ viết tay (mạng Neural nhân chập đã đạt độ chính xác 99.61% trên bộ dữ liệu MNIST [8]) song ngày nay người ta vẫn tiếp tục nghiên cứu những phương pháp nhận dạng tốt hơn hướng đến dùng cho các thiết bị di động, và các bài toán thời gian thực. Từ các nhận xét trên, với lòng đam mê muốn nghiên cứu, học hỏi về kiến trúc của mạng Neural nhân tạo (cụ thể ở đây là mạng Neural RBF) qua đó ứng dụng để viết phần mềm nhận dạng chữ viết tay, được sự chỉ bảo và giúp đỡ tận tình của thầy giáo PGS.TS Hoàng Xuân Huấn tôi đã tiến hành thực hiện khóa luận tốt nghiệp với đề tài “Mạng Neural RBF và ứng dụng nhận dạng chữ viết tay”. Nội dung của khóa luận sẽ đi sâu nghiên cứu những vấn đề sau: - Khảo cứu về mạng Neural RBF. - Tìm hiểu bài toán nhận dạng chữ viết tay và các phương pháp trích chọn đặc trưng chữ viết tay. - Nghiên cứu các phương pháp cải tiến hiệu suất của mạng Neural RBF áp dụng cho bài toán nhận dạng chữ viết tay. - Tiến hành cài đặt các ứng dụng để thực hiện so sánh hiệu suất các phương pháp huấn luyện mạng Neural RBF, hiệu suất các phương pháp trích chọn giá trị đặc trưng, cài đặt các phương pháp để cải thiện hiệu suất của mạng RBF áp dụng cho bài toán nhận dạng chữ viết tay. - Tiến hành viết chương trình nhận dạng chữ số viết tay nhận dạng chữ viết tay tổng hợp tất cả các phần kiến thức đã nghiên cứu. Với mục tiêu dẫn dắt từ cơ sở lý thuyết mạng Neural RBF đến ứng dụng nhận dạng chữ viết tay, bài khóa luận được phân thành bốn chương lớn: +Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF Chương này sẽ cung cấp những khái niệm cơ bản nhất về bài toán nội suy, xấp xỉ hàm cũng như vẽ nên bức tranh tổng quan về mạng Neural nhân tạo. Phần lớn nội dung của chương này sẽ tập trung đi sâu nghiên cứu về mạng Neural RBF bao gồm kiến trúc và các phương pháp huấn luyện mạng. Phần cuối chương (1.4) giới thiệu kết quả thực nghiệm so sánh hiệu suất các phương pháp huấn luyện mạng Neural RBF thông qua bài toán phân tích thành phần trong ống dầu. +Chương 2: Nhận dạng chữ viết tay Phần đầu chương sẽ trình bày sơ lược về bài toán nhận dạng mẫu, ở phần tiếp theo của chương sẽ làm rõ hơn về các bước để giải quyết bài toán nhận dạng chữ viết tay. Phần lớn nội dung của chương sẽ tập trung nghiên cứu các phương pháp lấy đặc trưng chữ viết tay. Phần cuối chương đưa ra kết quả thực nghiệm so sánh hiệu suất các phương pháp trích chọn đặc trưng chữ viết tay khác nhau. +Chương 3: Các phương pháp tăng hiệu suất mạng Neural RBF Nội dung chủ yếu của chương này là giới thiệu một số phương pháp nhằm cải thiện hiệu suất mạng Neural RBF áp dụng cho bài toán nhận dạng chữ viết tay. Phần đầu chương giới thiệu phương pháp làm tăng số lượng dữ liệu huấn luyện sử dụng các phương pháp biến đổi ảnh affine, elastic. Tiếp đó sẽ giới thiệu phương pháp làm tăng tốc độ và độ chính xác nhận dạng bằng cách sử dụng bộ nhận dạng ba tầng. Phương pháp học tập hợp (Ensemble Learning) để cải thiện độ chính xác nhận dạng cũng được đề cập ở chương này. Ở chương này tôi xin đề xuất phương pháp học tập hợp cải tiến đạt độ chính xác nhận dạng gần 98% cho bộ dữ liệu MNIST và có thời gian huấn luyện rất nhanh. Ở cuối chương sẽ giới thiệu kết quả thực nghiệm so sánh hiệu suất nhận dạng của phương pháp hợp cải tiến so với các phương pháp thông thường. +Chương 4: Giới thiệu chương trình nhận dạng chữ số viết tay và kết luận Phần đầu chương giới thiệu phần mềm nhận dạng ký tự chữ số viết tay mà tôi đã xây dựng dựa trên cơ sở tổng hợp toàn bộ nền tảng lý thuyết của bài khóa luận. Cuối cùng là phần tổng kết của khóa luận. Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 1 CHƯƠNG 1 BÀI TOÁN NỘI SUY, XẤP XỈ HÀM SỐ VÀ MẠNG NEURAL RBF Nội dung chương này gồm có: 1.1 Phát biểu bài toán nội suy và xấp xỉ hàm số 1.2 Mạng Neural nhân tạo 1.3 Mạng Neural RBF 1.4 Các thuật toán huấn luyện mạng Neural RBF 1.5 Kết quả thực nghiệm và đánh giá 1.1 PHÁT BIỂU BÀI TOÁN NỘI SUY VÀ XẤP XỈ HÀM SỐ 1.1.1 Bài toán nội suy 1.1.1.1 Nội suy hàm một biến số Bài toán nội suy hàm một biến tổng quát được đặt ra như sau: Một hàm số  xfy  chưa biết và chỉ xác định được tại các điểm 0 1 Nx a x x b    K với các giá trị yi= f(xi). Ta cần tìm một biểu thức giải tích  (x) để xác định gần đúng giá trị  y x tại các điểm  bax , của hàm f(x) sao cho tại các điểm xi thì hàm số trùng với giá trị yi đã biết (với  bax , ta gọi là ngoại suy). Về phương diện hình học, ta cần tìm hàm  (x) có dạng đã biết sao cho đồ thị của nó đi qua các điểm(xi,yi) với mọi i=0,1,...,N. Hình 1: Minh họa bài toán nội suy hàm một biến x0 x1 xn f(x0) f(x)  (x) Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 2 Hàm f thường là hàm thực nghiệm hoặc các hàm khó tính giá trị hàm số nên chỉ đo được ở các điểm nhất định. Các điểm   0 N i ix  sẽ gọi là các mốc nội suy. 1.1.1.2 Bài toán nội suy hàm nhiều biến Xét một hàm chưa biết : ( )n mf D R R  và một tập huấn luyện     1 , ; , Nk k k n k m k x y x R y R    sao cho ( ) ; 1,k kf x y k N   . Chúng ta cần tìm một hàm số  ở một dạng đã biết để thỏa mãn điều kiện nội suy đó là : ( ) ; 1,k kx y k N    1.1.2 Bài toán xấp xỉ Hàm  xfy  đo được tại N điểm thuộc đoạn  ba, 1 2 Nx x x  L ;  i iy f x Với 1k N  , ta tìm hàm    1, , ,kx c c x   K (1) Trong đó  là hàm cho trước, jc là các tham số cần tìm sao cho sai số trung bình bình phương   2 1 1 N i i i x y N      nhỏ nhất khi các tham số jc thay đổi. Khi đó ta nói  x là hàm xấp xỉ tốt nhất của y trong lớp hàm có dạng (1) theo nghĩa bình phư- ơng tối thiểu. Thường thì bài toán tìm cực tiểu toàn cục của sai số trung bình bình ph- ương là bài toán khó. Trong trường hợp  là hàm tuyến tính của các jc thì cực trị toàn cục có thể xác định nhờ giải hệ phương trình tuyến tính của điều kiện các đạo hàm cấp một triệt tiêu.    1 1 , , , N k k k k c c x c x   K (2) trong đó  xk là các hàm đơn giản và độc lập tuyến tính. 1.1.3 Các phương pháp giải quyết bài toán nội suy và xấp xỉ hàm số Bài toán nội suy hàm một biến là một lĩnh vực nghiên cứu nghiên cứu khá quan trọng trong ngành giải tích thế kỷ 18. Đầu tiên bài toán nội suy được giải quyết bằng phương pháp sử dụng đa thức nội suy: đa thức Lagrange, đa thức Chebysev... tuy nhiên khi số Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 3 mốc nội suy lớn thì nội suy bằng đa thức thường xảy ra hiện tượng phù hợp trội(over- fitting) do bậc của đa thức thường tăng theo số mốc nội suy. Để giải quyết hiện tượng phù hợp trội thay vì tìm đa thức nội suy người ta chỉ tìm đa thức xấp xỉ (thường giải quyết bằng phương pháp xấp xỉ bình phương tối thiểu của Gauss...) Một phương pháp khác được đề xuất vào đầu thế kỷ 20 đó là phương pháp nội suy Spline. Trong đó hàm nội suy được xác định nhờ ghép trơn các hàm nội suy dạng đơn giản (thường dùng đa thức bậc thấp) trên từng đoạn con. Phương hay được áp dụng niều trong kỹ thuât. Để hiểu rõ hơn về các phương pháp trên xem [1,14]. Cùng với phát triển của các ứng dung CNTT, bài toán nội suy nhiều biến được quan tâm giải quyết và đạt nhiều tiến bộ trong khoảng 30 năm gần đây, với các cách tiếp cận như: -Học dựa trên mẫu, bao gồm các phương pháp: k-láng giềng gần nhất với trọng số nghịch đảo khoảng cách và hồi quy trọng số địa phương. -Mạng neural truyền thẳng MLP -Mạng neural RBF Để rõ hơn về các phương pháp trên xem [11]. 1.2 MẠNG NEURAL NHÂN TẠO 1.2.1 Giới thiệu mạng Neural nhân tạo Bộ não con người chứa đựng những bí mật mà đến bây giờ khoa học vẫn chưa giải đáp được, chính nhờ có bộ não hoàn chỉnh mà con người đã trở thành động vật bậc cao thống trị muôn loài. Đã từ lâu con người đã nghiên cứu cấu trúc đặc biệt của bộ não từ đó ứng dụng để giải quyết những bài toán khoa học kỹ thuật. Người ta đã phát hiện ra rằng bộ não con người là mạng lưới chằng chịt các Neural liên kết với nhau, đây là cơ sở hình thành nên cấu trúc của mạng Neural nhân tạo. Về bản chất toán học thì mạng Neural nhân tạo như là một mặt trong không gian đa chiều để xấp xỉ một hàm chưa biết nào đấy. Nhưng mạng Neural nhân tạo lại giống mạng Neural sinh học ở chỗ đó là khả năng có thể huấn luyện (học), đây là đặc điểm quan trọng nhất của mạng Neural nhân tạo. Chính vì đặc điểm này mà mạng Neural nhân tạo có khả năng thực hiện tốt các công việc sau khi đã được huấn luyện, và đến Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 4 khi môi trường thay đổi ta lại có thể huấn luyện lại mạng Neural nhân tạo để nó thích nghi với điều kiện mới. 1.2.1.1 Mạng Neural sinh học Mạng Neural sinh học là một mạng lưới (plexus) các Neuron có kết nối hoặc có liên quan về mặt chức năng trực thuộc hệ thần kinh ngoại biên (peripheral nervous system) hay hệ thần kinh trung ương (central nervous system). Hình 2: Minh họa một Neuron thần kinh sinh học Trên đây là hình ảnh của một tế bào thần kinh (Neuron thần kinh), ta chú ý thấy rằng một tế bào thần kinh có ba phần quan trọng: -Phần đầu cũng có nhiều xúc tu (Dendrite) là nơi tiếp xúc với các với các điểm kết nối(Axon Terminal) của các tế bào thần kinh khác -Nhân của tế bào thần kinh (Nucleus) là nơi tiếp nhận các tín hiệu điện truyền từ xúc tu. Sau khi tổng hợp và xử lý các tín hiệu nhận được nó truyền tín hiệu kết quả qua trục cảm ứng (Axon) đến các điểm kết nối (Axon Terminal) ở đuôi. -Phần đuôi có nhiều điểm kết nối (Axon Terminal) để kết nối với các tế bào thần kinh khác. Khi tín hiệu vào ở xúc tu kích hoạt nhân Neuron có tín hiệu ra ở trục cảm ứng thì Neuron được gọi là cháy. Mặc dù W. Mculloch và W.Pitts (1940) đề xuất mô hình mạng neural nhân tạo khá sớm nhưng định đề Heb (1949) mới là nền tảng lý luận cho mạng neural nhân tạo. Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 5 Định đề Heb: Khi một neuron (thần kinh) A ở gần neuron B, kích hoạt thường xuyên hoặc lặp lại việc làm cháy nó thì phát triển một quá trình sinh hoá ở các neuron làm tăng tác động này. 1.2.1.2 Mạng Neural nhân tạo Mạng Neural nhân tạo được thiết kế để mô hình một số tính chất của mạng Neural sinh học, tuy nhiên, khác với các mô hình nhận thức, phần lớn các ứng dụng lại có bản chất kỹ thuật. Mạng Neural nhân tạo (ANN) là máy mô phỏng cách bộ não hoạt động thực hiện các nhiệm vụ của nó. Một mạng Neural là bộ xử lý song song phân tán lớn, nó giống bộ não người về 2 mặt: -Tri thức được nắm bắt bởi Neural thông qua quá trình học. -Độ lớn của trọng số kết nối Neural đóng vai trò khớp nối cất giữ thông tin. a) Cấu tạo một Neuron trong mạng Neural nhân tạo Hình 3: Cấu tạo một Neural nhân tạo Một neuron bao gồm các liên kết nhận tín hiệu vào bằng số có các trọng số kết nối wi tương ứng với tín hiệu xi, hàm F gọi là hàm kích hoạt để tạo tín hiệu ra dựa trên giá trị hàm tổng có trọng số của các giá trị đầu vào, Y là giá trị đầu ra của Neuron. Ta có thể biểu diễn một Neural nhân tạo theo công thức toán học như sau: 0 1 w N i i i Y F x w          Tùy vào thực tế bài toán hàm F là một hàm cụ thể nào đấy, trong quá trình huấn luyện (học) thì các tham số wi được xác định. Trên thực tế F thường được chọn trong những hàm sau: F ∑ x1 x2 xN w1 w2 wN w0 Y Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 6 1) Hàm ngưỡng 1 0 ( ) ( ) 1 0 x F x x x          -1.5 -1 -0.5 0 0.5 1 1.5 -6 -4 -2 0 2 4 6 Hình 4: Đồ thị hàm ngưỡng 2) Hàm tuyến tính ( )F x ax -4 -3 -2 -1 0 1 2 3 4 -6 -4 -2 0 2 4 6 Hình 5: Đồ thị hàm tuyến tính 3) Hàm sigmoid 1( ) 1 x F x e   0 0.5 1 -6 -4 -2 0 2 4 6 Hình 6: Đồ thị hàm sigmoid 4) Hàm tanh 1( ) 1 x x eF x e      -1 -0.5 0 0.5 1 -6 -4 -2 0 2 4 6 Hình 7: Đồ thị hàm tanh Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 7 5) Hàm bán kính (Gauss) 2 ( ) xF x e 0 0.5 1 -6 -4 -2 0 2 4 6 Hình 8: Đồ thị hàm Gauss Trên thực tế thì các họ hàm sigmoid thường dùng cho mạng Neural truyền thẳng nhiều tầng MLP vì các hàm này dễ tính đạo hàm: '( ) ( )(1 ( ))f x f x f x  , trong khi đó mạng Neural RBF lại dùng hàm kích hoạt là hàm bán kính. b) Kiến trúc của mạng Neural nhân tạo Kiến trúc của mạng Neural nhân tạo lấy tư tưởng chính của mạng Neural sinh học đó là sự kết nối của các Neuon. Tuy nhiên, mạng Neural nhân tạo có kiến trúc đơn giản hơn nhiều, về cả số lượng Neuron và cả kiến trúc mạng, trong khi ở mạng Neural tự nhiên một Neuron có thể kết nối với một Neuron khác bất kỳ ở trong mạng thì ở mạng Neural nhân tạo các Neuron được kết nối sao cho nó có thể dễ dàng được biểu diễn bởi một mô hình toán học nào đấy. Ví dụ trong mạng Neural truyền tới các Neuron được phân thành nhiều lớp, các Neuron ở lớp trước chỉ được kết nối với các Neuron ở lớp sau. INPUT OUTPUT HIDDEN Hình 9: Kiến trúc mạng Neural truyền tới c) Quá trình học Như đã nói ở trên mạng Neural nhân tạo có khả năng huấn luyện được (học), quá trình huấn luyện là quá trình mà mạng Neural nhân tạo tự thay đổi mình dưới sự kích thích Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 8 của môi trường (bộ dữ liệu huấn luyện) để phù hợp với điều kiện của môi trường. Quá trình huấn luyện chỉ có thể được thực hiện khi mạng Neural nhân tạo đã xây dựng được kiến trúc cụ thể, và hàm kích hoạt F đã được xác định. Về bản chất quá trình học là quá trình xác định các tham số wi của các Neuron trong mạng Neural. Có ba kiểu học chính, mỗi kiểu mẫu tương ứng với một nhiệm vụ học trừu tượng. Đó là học có giám sát, học không có giám sát và học tăng cường. Dưới đây xin nêu ra phương pháp học có giám sát các phương pháp khác xem thêm [10] – chapter 4. Học có giám sát Trong học có giám sát, ta được cho trước một tập ví dụ gồm các cặp ( , , 1.. ), ,i ix y i N x X y Y   và mục tiêu là tìm một hàm :f X Y (trong lớp các hàm được phép) khớp với các ví dụ. Trên thực tế người ta thường tìm hàm f sao cho tổng bình bình phương sai số đạt giá trị nhỏ nhất trên tập ví dụ:  2 1 ( ) N i i i E f x y    . 1.3 MẠNG NEURAL RBF 1.3.1 Giới thiệu mạng Neural RBF Hàm cơ sở bán kính được giới thiệu bởi M.J.D. Powell để giải quyết bài toán nội suy hàm nhiều biến năm 1987. Ngày nay, đây là vấn đề hết sức quan trọng được nghiên cứu trong ngành giải tích số. Trong lĩnh vực mạng Neural, mạng Neural RBF được đề xuất bởi D.S. Bromhead và D. Lowe năm 1988 cho bài toán nội suy và xấp xỉ hàm nhiều biến (xem [12]). 1.3.1.1 Kỹ thuật hàm cơ sở bán kính Bài toán nội suy hàm nhiều biến đã được giới thiệu ở phần 1.1.1.2, như đã nói ở trên để giải quyết bài toán này D. Powell đã đề xuất dạng của hàm  là hàm cơ sở bán kính. Dưới đây sẽ trình bày sơ lược kỹ thuật sử dụng hàm cơ sở bán kính để giải quyết bài toán nội suy hàm nhiều biến. Kỹ thuật hàm cơ sở bán kính Không mất tính tổng quát giả sử m=1 khi đó hàm  có dạng như sau : Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 9 0 1 ( ) ( ) N k k k x w x w     (1) ở đây k là hàm cơ sở bán kính thứ k. Thông thường k có những dạng sau: 2 2 k ( ) k k x v x e     (2) 2 2 k ( ) k kx x v    (3) k 2 2 1( ) k k x x v      (4) Trên thực tế thì người ta thường cho k ở dạng (2) và trong khuôn khổ khóa luận này chỉ xét k ở dạng (2). 2 2 k ( ) k k x v x e     chú ý rằng ở đây ta dùng chuẩn ||.|| là chuẩn Euclide 2 1 N i i u u    ; kv là tâm của mỗi hàm cơ sở bán kính k ; k là bán kính của k . Với mỗi k thì giá trị của bán kính k điều khiển miền ảnh hưởng của hàm bán kính k . Nếu 3k kx v   thì giá hàm ( )k x là rất nhỏ, không có ý nghĩa. Hình 10: Minh họa sự ảnh hưởng của hàm bán kính Ví dụ như ở hình trên một vòng tròn to tượng trưng cho một hàm cơ sở bán kính, các hàm này chỉ ảnh hưởng đến các điểm bên trong bán kính của nó. Thay công thức (2) vào (1) ta được biểu diễn toán học của kỹ thuật hàm cơ sở bán kính như sau: 2 2 0 0 1 1 ( ) ( ) j k k x v N N j j j k k k k k x w x w w e w y            (6) Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 10 Một đặc điểm rất lợi thế khi sử dụng hàm bán kính để giải quyết bài toán nội suy hàm nhiều biến, đó là khi xét giá trị bình phương sai số   2 1 N i i i E x y    thì người ta đã chứng minh được rằng E chỉ có một cực trị duy nhất. Do vậy việc tìm các tham số của các hàm cơ sở bán kính( , ,kk kw v  ) để cho E đạt cực tiểu sẽ được giải quyết rất nhanh và hiệu quả. 1.3.1.2 Kiến trúc mạng Neural RBF Mạng RBF là một loại mạng Neural nhân tạo truyền thẳng gồm có ba lớp. Nó bao gồm n nút của lớp đầu vào cho vector đầu vào nx R , N neuron ẩn (giá trị của neuron ẩn thứ k chính là giá trị trả về của hàm cơ sở bán kính k ) và m neuron đầu ra. Hình 11: Kiến trúc của mạng RBF Như đã nêu ở trên mạng RBF có thể biểu diễn bằng công thức toán học sau:   2 2 0 0 1 1 ( ) ( ) j k k x v N N j j j k k k k k k k x w x w w e w y                     1.3.1.3 Ứng dụng của mạng Neural RBF Nhờ ưu điểm vượt trội là có thời gian huấn luyện mạng rất ngắn ngày nay mạng Neural RBF được sử dụng trong rất nhiều lĩnh vực: -Xử lý ảnh -Nhận dạng tiếng nói IN PU T O U TPU T HIDDEN k xi wi w0 w0 Y X Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 11 -Xử lý tín hiệu số -Xác định mục tiêu cho Radar -Chuẩn đoán y học -Quá trình phát hiện lỗi -Nhận dạng mẫu 1.4 CÁC PHƯƠNG PHÁP HUẤN LUYỆN MẠNG NEURAL RBF Huấn luyện mạng Neural RBF thực ra là quá trình tìm các tham số ( , ,kk kw v  ) của các hàm bán kính để phù hợp với bài toán nào đấy. So với các mạng Neural khác mạng Neural RBF có điểm mạnh hơn hẳn đó có có thời gian huấn luyện ngắn. Xét tổng bình phương sai số   2 1 N i i i E x y    , do E chỉ có một cực trị duy nhất, vì thế nên việc đi tìm điểm cực trị cho E sẽ rất nhanh chóng do không có cực trị địa phương. Có rất nhiều phương pháp huấn luyện mạng hầu hết các phương pháp này đều có đặc điểm chung là đều có xu hướng cực tiểu hóa giá trị bình phương sai số E cho tập dữ liệu huấn luyện. Có thể chia các kiểu huấn luyện mạng RBF ra thành ba loại: huấn luyện một pha, huấn luyện hai pha và huấn luyện ba pha (huấn luyện đầy đủ) (xem [4,5]). 1.4.1 Phương pháp huấn luyện một pha Xét tập dữ liệu huấn luyện     1 , ; , Nk k k n k m k x y x R y R    ở phương pháp này, người ta thường chọn tâm kv của các hàm bán kính là một tập con của tập dữ liệu huấn luyện   1 Nk k x  , còn các bán kính k được gán giá trị là một hằng số nào đấy, trên cơ sở thực nghiệm người ta thường đặt 1 1 (2 ) nk M   (trong đó M là số hàm cơ sở bán kính, n là số Neural đầu vào). Giá trị của các tham số wk thường được tìm ra bằng các phương pháp học có giám sát như là phương pháp giả nghịch đảo hoặc phương pháp tụt dốc Gradient. Về bản chất thì hai phương pháp này đều tìm các trong số wk để giá trị bình phương sai số E đạt cực tiểu. 1) Phương pháp giả nghịch đảo Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 12 Với tập huấn luyện     1 , ; , Nk k k n k m k x y x R y R    , giả sử mạng RBF của ta có M Neuron ở tầng ẩn. Ta xét ma trận N MH  như sau 2 ( , ) ( ) i k k x v i kH i k x e      và ma trận Y là ma trận hàng các yk khi đó giá trị của các wk được tính như sau : W H Y trong đó 1( )T TH H H H  . 2) Phương pháp tụt dốc Gradient Với phương pháp này, đầu tiên các tham số wk được tạo ra ngẫu nhiên sau đó các tham số này được cập nhật bằng công thức sau : ( 1) ( )k k kw i w i w         1 N i i i k k i w x y x      chú ý ở đây ta xét mạng RBF có một Neural ở đầu ra. Hệ số  được gọi là tốc độ học, nếu  nhỏ thì giá trị của các trọng số w tiến chậm đến điểm cực tiểu, nhưng nếu  lớn thì giá trị của các trong số w thường có xu hướng dao động quanh điểm cực tiểu, nói chung để tìm được giá trị  hợp lí thì phải qua quá trình thực nghiệm. Thông thường người ta vẫn chọn  có giá trị nhỏ để đảm bảo quá trình lặp sẽ hội tụ về giá trị cực tiểu cho dù hơi mất thời gian. Hình 12: Quá trình hội tụ đến giá trị cực tiểu của thuật toán Gradient, đường nét đứt ứng với giá trị  lớn, đường nét liền ứng với giá trị  nhỏ 1.4.2 Phương pháp huấn luyện hai pha Với phương pháp huấn luyện hai pha thông thường các giá trị tâm vk và bán kính k của hàm cơ sở bán kính k được tính bằng các thuật toán phân cụm như thuật toán Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 13 phân cụm k-mean, k-mean có ngưỡng… Sau đó giá trị của các trọng số wk được tính bằng các phương pháp giả nghịch đảo, hay tụt dốc Gradient như đã nêu ở trên. 1) Thuật toán phân cụm k-mean -Phát biểu bài toán: Cho tập dữ liệu  1 2, ..., ; dn iX x x x x R  chúng ta cần phân tập dữ liệu này thành k tập  1 2 1 1 , ,.. : ; ; k k k i i i i S S S k n S S X            I U sao cho thỏa mãn: 2 1 arg min j i k j i S i x S x     với i là tâm của tập iS . Về mặt toán học thì bài toán phân cụm trên thuộc loại NP-khó tuy nhiên trên thực tế thì người ta thường giải bài toán bằng phương pháp heuristic như sau: Đầu tiền ta khởi tạo ngẫu nhiên tập  1 2, ,... k   sau đó thực hiện vòng lặp qua hai bước sau: +Bước 1: tạo các cụm  ( ) **: ; 1,ti j j i j iS x x x i k       +Bước 2: điều chỉnh lại tâm ( ) ( 1) ( ) 1 i t j i t jt x Si x S      Thuật toán sẽ dừng cho đến khi tập  1 2, ,... k   không còn có sự thay đổi giá trị(để hiểu chi tiết hơn về thuật toán phân cụm k-mean có thể tham khảo thêm [18]). Sau khi chạy thuật toán k-mean ta sẽ chọn tâm vk của các hàm cơ sở bán kính k chính là tập  1 2, ,... k   còn bán kính 1 || || j k k j k x Sk x S      . 1.4.3 Phương pháp huấn luyện 2 pha HDH Xét tập huấn luyện     1 , ; , Nk k k n k m k x y x R y R    , không mất tính tổng quát, ở đây ta xét mạng RBF có một Neuron output (m=1), khi đó biểu diễn toán học của mạng RBF là: Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 14 0 1 ( ) ( ) N i i i k k k x w x w y      (1) Xét ma trận  ,k i N N   trong đó 2 2|| || / , ( ) i k kx xi k i k x e      , chú ý rằng ở đây ta chọn tâm của các hàm cơ sở bán kính chính là tất cả các điểm thuộc tập dữ liệu input X. Ta ký hiệu I là ma trận đơn vị cấp N ; W=           Nw w ... 1 , Z=           Nz z ... 1 là các véc tơ trong không gian N-chiều RN trong đó: zk = yk w0, Nk  (2) và đặt ,k j N N I          (3) thì 2 2, || || / 0 j k k k j x x k j e k j          (4) Khi đó hệ phương trình (1) tương đương với hệ : W=  W +Z (5) Với các tham số k đã chọn và w0 tùy ý, hệ (1) và do đó hệ (5) luôn có duy nhất nghiệm W. Về sau giá trị w0 được chọn là trung bình cộng của các giá trị yk: w0 =   N k ky N 1 1 (6) Với mỗi kN, ta có hàm qk của k xác định như sau:    N j jkkq 1 , (7) Hàm qk là đơn điệu tăng và với mọi số dương q < 1 luôn tồn tại giá trị k sao cho qk( k )=q. Mô tả thuật toán. Với sai số  và các hằng số dương q,  <1 cho trước, thuật toán bao gồm 2 pha để xác định các tham số k và W*. Trong pha thứ nhất, ta sẽ xác định các k để qk q và gần với q nhất (nghĩa là nếu thay k=k/ thì qk>q). Vì vậy, với mọi k, chuẩn của ma trận  tương ứng với chuẩn vector * . (cho bởi công thức (16) dưới đây) thuộc đoạn này. Pha sau tìm nghiệm gần đúng W* của (5) bằng phương pháp lặp đơn giản. Thuật toán được đặc tả trong hình 13. Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 15 Hình 13: Thuật toán HDH huấn luyện mạng RBF Để tìm nghiệm W* của hệ (5) ta thực hiện thủ tục lặp như sau. Khởi tạo W0=Z ; Tính Wk+1= kW +Z ; (8) Nếu điều kiện kết thúc chưa thỏa mãn thì gán W0 := W1 và trở lại bước 2 ; Với mỗi vectơ N-chiều u, ta ký hiệu chuẩn    N j juu 1 * , điều kiện kết thúc có thể chọn một trong biểu thức sau. a)   * 01 1 WW q q (9) b) q qZ q Z q t ln )1ln(lnln ln )1(ln **       , với t là số lần lặp. (10) Đặc tính hội tụ. Với mỗi vectơ N-chiều u, ta ký hiệu chuẩn * u cho bởi công thức :    N j juu 1 * (11) Thì thuật toán trên luôn kết thúc sau hữu hạn bước và đánh giá sau đúng.  * *1 WW (12) Ký hiệu chuẩn *  của ma trận  tương ứng với chuẩn vectơ (11) là : *  =   ],[max qqqkNk   q (13) ta có đánh giá : 1 1 1 * 1 0 ** *1 1 t tq qW W u u Z q q         (14) Proceduce Thuật toán 2 pha huấn luyện mạng RBF for k=1 to N do Xác định các k để qk q, và nếu thay k=k/ thì qk>q; // Pha 1 Tìm W* bằng phương pháp lặp đơn (hoặc phương pháp lặp Seidel); //Pha 2 End Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 16 Biểu thức (10) tương đương với vế phải của (14) nhỏ hơn hoặc bằng  . Mặt khác ở bước cuối của pha 2, nếu áp dụng (14) cho t=0 ; 1100 ; WuWu  ; áp dụng (14) cho t=0 thì ta có : 1 * 1 0 * *1 qW W w w q     (15) Thuật toán này có ưu điểm là cài đặt rất đơn giản và tốc độ hội tụ rất nhanh và ta có thể điều chỉnh giá trị sai số nội suy nhỏ tùy ý. Song do kiến trúc mạng phức tạp nên thường xảy ra hiện tượng phù hợp trội(over-fitting) cho tập dữ liệu huấn luyện. Để hiểu chi tiết hơn về thuật toán HDH xem thêm [2,3]. 1.4.4 Phương pháp huấn luyện ba pha đầy đủ Phương pháp này sử dụng phương pháp tụt dốc Gradient để tìm kiếm cả ba tham số dùng các công thức lặp dưới đây:  ( ( )) ( ) ( )11 1 1 2w Q J k q q q mj mj mj j j m q jmj Ew w z y w M                                        ( ) ( ) 22 1 1 2 Q J k q q q q mm m n n j j mj m n n q j v v z w y x v M                                 2 2 2 3 4 1 1 1 2 2 q q q Q J M mj mk q q m m j j q j m m w x v w z M                        Chú ý ở đây ta dùng tập dữ liệu huấn luyện     1 , ; , Qk k k n k m k x y x R y R    trong đó ( )k q là dữ liệu huấn luyện thứ q. Để rõ hơn về phương pháp trên xem [5]. Nhìn chung phương pháp này cho kết quả huấn luyện khá tốt, song nhược điểm là thời gian huấn luyện dài nên không phù hợp với các bài toán có dữ liệu lớn. 1.5 KẾT QUẢ THỰC NGHIỆM 1.5.1 Kết quả Dưới đây tôi xin giới thiệu kết quả thực nghiệm khi tiến hành cài đặt các phương pháp khác nhau để huấn luyện mạng RBF. Bộ dữ liệu huấn luyện ở đây là dữ liệu được lấy từ bài toán phân tích thành phần trong ống dầu. Phương pháp lấy dữ liệu như sau: Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 17 người ta dùng tia gamma chiếu vào ống dầu để thu được các đặc trưng khác nhau đồng thời tại thời điểm đó người ta phân tích tỉ lệ dầu và nước có trong ống dầu. Do tỉ lệ thành phần dầu và nước có liên quan đến các đặc trưng thu được khi chiếu tia gamma, người ta mong muốn dự đoán được thành phần dầu và nước dựa vào các đặc trưng thu được khi chiếu tia gamma vào ống dầu. Bộ dữ liệu bao gồm 900 bộ dữ liệu huấn luyện và 100 bộ dữ liệu kiểm tra. Mỗi dữ liệu bao gồm 12 giá trị đầu vào (các đặc trưng thu được khi chiếu tia gamma) và 2 giá trị đầu ra (tỉ lệ dầu và nước), tất cả đều được biểu diễn bằng số thực. Dữ liệu được tải từ địa chỉ: Tôi đã tiến hành xây dựng mạng Neural RBF với kiến trúc như sau: có 12 neuron đầu vào, 2 neuron đầu ra, còn số lượng neuron tầng ẩn tùy vào thuật toán huấn luyện. Sau đó tiến hành huấn luyện với 4 phương pháp huấn luyện khác nhau để so sánh hiệu suất(thời gian huấn luyện, sai số của bộ dữ liệu huấn luyện, sai số của bộ dữ liệu kiểm tra) của chúng. Các phương pháp dùng để huấn luyện đó là: 1) Phương pháp huấn luyện 2 pha HDH(xem 1.4.3) 2) Phương pháp huấn 3 pha đầy đủ(xem 1.4.4) 3) Phương pháp huấn luyện 1 pha, sử dụng phương pháp giả nghịch đảo để tìm tham số wi.(xem 1.4.1) 4) Phương pháp huấn luyện 2 pha, sử dụng phương pháp giả nghịch đảo để tìm tham số wi. (xem 1.4.2) Chương trình được chạy trên máy cấu hình như sau: HĐH Windows XP Professinal, CPU Intel Core 2 Duo E6300 1.86GHz, Ram 1G. Sau đây là bảng kết quả so sánh hiệu suất các phương pháp huấn luyện: Chương 1: Bài toán nội suy, xấp xỉ hàm số và mạng Neural RBF 18 Phương pháp huấn luyện Sai số trên tập dữ liệu kiểm tra(tổng bình phương sai số) Sai số trên tập dữ liệu huấn luyện(tổng bình phương sai số) Thời gian huấn luyện(giây) Phương pháp huấn luyện 2 pha HDH q=0.9, alpha=0.7, epsilon= 1e-5 3.095031 3.2938e-11 1.921000 q=0.9, alpha=0.75, epsilon= 1e-5 2.929305 2.8989e-11 1.859000 q=0.9, alpha=0.9, epsilon= 1e-5 2.275569 2.9517e-11 2.609000 q=0.99, alpha=0.7, epsilon= 1e-5 2.93460 3.7486e-11 1.703000 q=0.99, alpha=0.8, epsilon= 1e-5 2.47516 1.0336e-11 2.750000 q=0.99, alpha=0.9, epsilon= 1e-5 2.13895 1.2286e-11 1.984000 Phương pháp huấn luyện 3 pha đầy đủ Số neuron tầng ẩn 20, loop = 1000 0.40966 0.18352 1312.266000 Số neuron tầng ẩn 50, loop = 500 0.38691 0.17951 4198.204000 Số neuron tầng ẩn 100, loop = 500 0.38206 0.24483 11961.4530 Phương pháp huấn luyện 1 pha + giả nghịch đảo Số neuron tầng ẩn 180 0.2270 1.0226 1.968000 Số neuron tầng ẩn 280 0.14226 0.54680 2.437000 Số neuron tầng ẩn 350 0.091694 0.3864 2.828000 Phương pháp huấn luyện 2 pha + giả nghịch đảo Số neuron tầng ẩn 180 0.2666 1.2269 2.093000 Số neuron tầng ẩn 280 0.17365 0.9048 2.593000 Số neuron tầng ẩn 350 0.20062 0.5255 3.046000 Bảng 1: Kết quả thực nghiệm hiệu suất các phương pháp huấn luyện mạng Neural RBF Chương II: Nhận dạng chữ viết tay 19 1.5.2 Nhận xét Dựa vào bảng số liệu trên ta thấy rằng: +Thuật toán 1) có thời gian huấn luyện rất nhanh, cho kết quả sai số trên bộ dữ liệu huấn luyện là rất tốt, nhưng nó có sai số trên bộ kiểm tra là khá cao, như vậy phương pháp huấn luyện HDH là lựa chọn tốt để giải quyết bài toán nội suy, hoặc giải quyết các bài toán mà dữ liệu đầu vào có mật độ tập trung dày đặc. +Thuật toán 2) cho kết quả sai số trên cả bộ dữ liệu huấn luyện và bộ dữ liệu kiểm tra là rất nhỏ, tuy nhiên nó có điểm rất hạn chế đó là thời gian huấn luyện mạng là rất lâu. Nói chung phương pháp này không phải là một lựa chọn tốt để giải quyết các bài toán có bộ dữ liệu huấn luyện lớn. +Thuật toán 3), 4) cho kết quả sai số trên cả bộ dữ liệu huấn luyện và bộ dữ liệu kiểm tra là rất nhỏ và thời gian huấn là rất nhanh. Tuy nhiên cả 2 thuật toán này có một nhược điểm đó là sử dụng phương pháp giả nghịch đảo để tìm các tham số wi mà phương pháp giả nghịch đảo lại sử dụng nhiều phép tính nhân, nghịch đảo ma trận đây là các phép tính khó cài đặt và thường cho sai số tính toán cao. Ở đây tôi sử dụng thư viện MATLAB để thực hiện các phép tính toán này. Chương 2: Nhận dạng chữ viết tay 20 CHƯƠNG 2 NHẬN DẠNG CHỮ VIẾT TAY Nội dung chương này gồm có: 2.1 Nhận dạng mẫu 2.2 Bài toán nhận dạng chữ viết tay 2.3 Các phương pháp trích chọn đặc trưng chữ viết tay 2.4 Kết quả thực nghiệm 2.1 NHẬN DẠNG MẪU Nhận dạng chữ viết tay là một lĩnh vực con của nhận dạng dạng mẫu, do vậy trước khi đi sâu vào trình bày chi tiết bài toán nhận dạng chữ viết tay, tôi xin trình bày sơ lược về lĩnh vực nhận dạng mẫu và bài toán nhận dạng mẫu. 2.1.1 Nhận dạng mẫu 2.1.1.1 Mẫu là gì ? Mẫu(pattern) có thể phân thành 2 loại : mẫu trừu tượng và mẫu cụ thể. Các ý tưởng, lập luận và khái niệm... là những ví dụ về mẫu trừu tượng, nhận dạng các mẫu như vậy thuộc về lĩnh vực nhận dạng khái niệm. Các mẫu cụ thể bao gồm các đối tượng có tính không gian, thời gian và hình ảnh... Các đối tượng vật lý, chữ ký, chữ viết, ký hiệu, ảnh, đoạn sóng âm thanh, điện não đồ hoặc điện tâm đồ, hàm số... là những ví dụ về mẫu cụ thể. 2.1.1.2 Nhận dạng mẫu là gì ? Không có một định nghĩa thống nhất cho nhận dạng mẫu (Pattern recognition) nhưng điều này không gây tranh cãi gì trong giới nghiên cứu. Sau đây là một số định nghĩa theo ngữ cảnh nghiên cứu : - Duda Et Al: Nhận dạng mẫu là việc quy những đối tượng vật lí hay sự kiện vào một loại (nhóm) nào đó đã xác định từ trước. Chương 2: Nhận dạng chữ viết tay 21 - Jürgen Schürmann: Nhận dạng mẫu là việc gán nhãn w cho một quan sát x. - Selim Aksoy: Nhận dạng mẫu là việc nghiên cứu cách làm cho một máy có thể thực hiện: + Quan sát môi trường + Học cách phân biệt được các mẫu cần quan tâm + Đưa ra các quyết định đúng đắn về loại (nhóm) của các mẫu 2.1.1.3 Lịch sử của lĩnh vực nhận dạng mẫu Nhận dạng mẫu đã có lịch sử khá lâu đời, trong thập kỷ 60 của thế kỷ 20 hầu hết vấn đề nhận dạng mẫu dừng lại ở việc nghiên cứu lí thuyết thống kê. Về sau với sự phát triển mạnh mẽ của máy tính thì phần thực nghiệm cũng trở nên đơn giản hơn. Khi mà xã hội chúng ta đang phát triển từ thời kỳ công nghiệp sang hậu công nghiệp, đối với vấn đề tự động hóa thì việc thông tin được nhận và xử lý một cách tự động là rất cần thiết. Khuynh hướng này làm cho vấn đề nhận dạng mẫu trở nên rất quan trọng trong ứng dụng kỹ thuật và trong nghiên cứu ngày nay. Nhận dạng mẫu tích hợp hầu hết vào các hệ thống máy móc thông minh, có khả năng tự đưa ra quyết định để giải quyết vấn đề. 2.1.1.4 Ứng dụng của nhận dạng mẫu Nhận dạng mẫu có rất nhiều ứng dụng trong đời sống cũng như trong khoa học kỹ thuật : -Trong nông nghiệp : Nhận dạng mẫu được sử dụng để phân tích mùa màng, dự báo các đại dịch như châu chấu, sâu bệnh, cúm gia cầm, cúm lợn... Ngoài ra nhận dạng mẫu cũng còn được dùng để phân loại đất từ các ảnh được chụp từ vệ tinh. -Khám phá tri thức trên Web : Ngày nay việc bùng nổ lượng thông tin khổng lồ trên Internet làm cho việc tìm kiếm và lọc thông tin trên mạng là hết sức quan trọng. Nhận dạng mẫu được nhúng vào các máy tìm kiếm để trả lại kết quả tìm kiếm thông minh và chính xác. Ngoài ra nó cũng được trong các hệ thống lọc thư rác, nhận dạng tự động các trang web đen. -Trong lĩnh vực y học : Phân tích và biểu diễn gene, phân loại sinh học dựa trên thông tin di truyền. -Trong lĩnh kinh tế : Phân tích đánh giá sự thay đổi kinh tế, chỉ số chứng khoán... Chương 2: Nhận dạng chữ viết tay 22 2.1.1.5 Các bài toán nhận dạng mẫu Trên thực tế thường gặp các bài toán nhận dạng mẫu sau : -Phân lớp (classify) : Dựa trên một tập con đã biết nhãn, đưa ra một cách phân các đối tượng thuộc tập nền thành các lớp. -Phân cụm (cluster) : Chia tập đối tượng thành nhóm sao cho các đối tượng trong mỗi nhóm tương đối giống nhau còn các đối tượng khác nhóm thì khác nhau. -Phân tích hồi quy (regression) hay nhận dạng hàm : Xác định một biến (hàm) qua tập các biến khác. -Nhận thực (Identify) : Xác định đối tượng trong tập đã cho có là đối tượng đang quan tâm hay không. Chẳng hạn như nhận thực vân tay, nhận thực mặt người... -Mô tả : Mô tả các đối tượng dưới hình thức dễ phân tích. Ví dụ đối tượng. mô tả điện tâm đồ dưới dạng biểu đồ đặc trưng hoặc xâu mã. 2.1.1.6 Các bước xử lý trong hệ thống nhận dạng mẫu Mặc dù có rất nhiều loại bài toán nhận dạng mẫu, tuy nhiên để giải quyết một bài toán thì một hệ thống nhận dạng mẫu phải thực hiện qua các bước cơ bản dưới đây : Hình 14: Các bước xử lý trong hệ thống nhận dạng mẫu 1)Thu nhận tín hiệu Nếu là hệ nhận dạng đối tượng vật lý, ở đầu vào của hệ thống thường là một loại thiết bị chuyển đổi như máy ghi hình hay ghi âm… Thiết bị này thu nhận tín hiệu về đối tượng để nhận dạng. Các tín hiệu này thông thường sẽ được số hóa, sau đó sẽ được tiến hành tiền xử lý như: lọc nhiễu, tách ngưỡng… 2) Phân đoạn (segmentation) Phân đoạn là một trong những bài toán rất khó trong nhận dạng mẫu. Chẳng hạn, trong bài toán nhận dạng văn bản in ra dữ liệu text thì giai đoạn phân đoạn chính là Đầu vào Thu tín hiệu, tiền xử lý Phân đoạn Trích chọn đặc trưng Nhận dạng Hậu xử lý Chương 2: Nhận dạng chữ viết tay 23 việc xác định đâu là vùng dữ liệu text để nhận dạng, tiếp đó ta phải tách được những vùng có thể là một từ, rồi lại tách tiếp ra từng ký tự... Như vậy có thể nói việc phân đoạn trong bài toán nhận dạng mẫu là quá trình xác định được đâu là vùng dữ liệu cần quan tâm. 3) Trích chọn đặc trưng Ranh giới khái niệm giữa việc trích chọn đặc trưng và phân lớp ở mức độ nào đó có phần không rõ ràng: một bộ trích chọn đặc trưng lý tưởng phải làm cho công việc còn lại của bộ phân lớp trở nên dễ dàng Mục tiêu chung của bộ trích chọn đặc trưng là dựa trên tín hiệu thu được mô tả các đối tượng bằng các giá trị của chúng mà chúng có giá trị gần xấp xỉ nhau đối với các đối tượng thuộc cùng loại và khác xa nhau nếu khác loại. Hơn nữa để tiện xử lý thì càng ít đặc trưng càng tốt. Điều này dẫn đến việc phải tìm ra các đặc trưng khác nhau và chúng không phụ thuộc hoàn cảnh ta thu tín hiệu về đối tượng. Đầu ra của công đoạn này được gọi là vector đặc trưng của đối tượng, thông thường đây là một vector số thực. 4) Nhận dạng Nhiệm vụ của thành phần này trong hệ thống là sử dụng các vector đặc trưng được cung cấp từ bước trước (trích chọn đặc trưng) để gắn các đối tượng vào các lớp hoặc phân tích hồi quy hay mô tả đối tượng. Các kỹ thuật thường được sử dụng cho công đoạn nhận dạng đó là: thuật toán k-láng giềng gấn nhất, mạng neural, máy vector hỗ trợ SVM... Nói chung, ở bước này gần như đã có công thức xử lý cố định thường không bị phụ thuộc vào bài nhận dạng mẫu cụ thể nào. 5) Hậu xử lý Một bộ nhận dạng hiếm khi chỉ để dùng đơn lẻ. Thay vào đó nó thường dùng để đưa ra thao tác tương ứng, mỗi thao tác mất một chi phí tương ứng. Hậu xử lý sẽ dùng đầu ra của bộ phân lớp để quyết định thao tác tương ứng. Theo quan niệm, cách đơn giản nhất để đánh giá hoạt động của một bộ nhận dạng là xem tỷ lệ nhận dạng sai với các mẫu mới. Do đó chúng ta cần phải nhận dạng với tỷ lệ lỗi thấp nhất. Tuy nhiên chúng ta cần các thao tác tương ứng phải làm cho tổng chi phí là thấp nhất. Có thể phải kết hợp các tri thức đã biết về chi phí, và nó sẽ có ảnh hưởng đến việc ra các quyết định hành động. Chúng ta cũng cần ước lượng trước chi phí để xem có thỏa mãn hay không. Chương 2: Nhận dạng chữ viết tay 24 2.2 BÀI TOÁN NHẬN DẠNG CHỮ VIẾT TAY 2.2.1 Tình hình chung về nhận dạng chữ viết tay Bài toán nhận dạng chữ viết tay được ứng dụng rất nhiều trong thực thế : được tích hợp vào hệ thống nhận dạng form tự động, tích hợp trong các máy PDA có màn hình cảm ứng, nhận dạng chữ ký... Do có nhiều ứng dụng quan trọng như vậy nên từ lâu bài toán nhận dạng chữ viết tay đã thu hút rất nhiều người nghiên cứu, tìm cách giải quyết. Ngày nay bài toán nhận dạng chữ viết tay đã được giải quyết gần như trọn vẹn trên thế giới cũng như ở Việt Nam. Hệ nhận dạng sử dụng mạng Neural nhân chập giới thiệu ở [8] đã đạt độ chính xác đến 99.60% (trên bộ dữ liệu MNIST). Đây là độ chính xác gần như tuyệt đối và nhanh chóng được áp dụng vào rất nhiều ứng dụng. Các sản phẩm ứng dụng khác có ý nghĩa thực tế lớn có thể kể đến như sản phẩm FineReader của hãng AABYY có thể nhận dạng 20 thứ tiếng khác nhau, sản phẩm OmniPage của hãng ScanSoft nhận dạng chữ in tiếng Anh,…. và ở Việt Nam, chúng ta có sản phẩm VNDOCR của Viện Công nghệ thông tin nhận dạng chữ in tiếng Việt với độ chính xác tới 99%. 2.2.2 Giới thiệu bài toán nhận dạng chữ viết tay Nhận dạng chữ viết tay được thực hiện qua hai hình thức đó là nhận dạng online và nhận dạng offline. Nhận dạng online có nghĩa là máy tính sẽ nhận dạng các chữ được viết lên màn hình ngay khi nó được viết. Đối với những hệ nhận dạng này, máy tính sẽ lưu lại các thông tin về nét chữ như thứ tự nét viết, hướng và tốc độ của nét viết trong khi nó đang được viết. Còn nhận dạng offline tức là việc nhận dạng được thực hiện sau khi chữ đã được viết hay in lên giấy rồi, lúc đó thông tin đầu vào là hình ảnh văn bản hoặc ký tự cần nhận dạng. Trong khuôn khổ nội dung khóa luận này tôi chỉ xét hình thức nhận dạng offline cho từng ký tự một. 2.2.3 Hướng giải quyết cho bài toán nhận dạng ký tự viết tay Như đã nói ở trên bài toán nhận dạng chữ viết tay thuộc lớp bài toán nhận dạng mẫu, như vậy để giải quyết bài toán nhận dạng chữ viết tay thì phải tuân theo các bước của bài toán nhận dạng mẫu đã nêu ở phần 2.1.1.6. Tuy nhiên do ở đây ta chỉ xét việc nhận Chương 2: Nhận dạng chữ viết tay 25 dạng từng ký tự viết tay một nên bước tiền xử lý và bước phân đoạn xem như không cần thiết. Có thể khái quát quá trình nhận dạng chữ viết tay thông qua hình vẽ dưới đây : Hình 15 : Các bước giải quyết bài toán nhận dạng chữ viết tay Đầu vào là bức ảnh của một ký tự cần nhận dạng, sau khi qua bộ trích chọn đặc trưng chữ viết tay ta thu được vector đặc trưng của ký tự đó, vector đặc trưng được chuyển đến bộ nhận dạng để thực hiện lượng giá và đưa ra kết quả nhận dạng. Trong bài toán nhận dạng chữ viết tay có rất nhiều phương pháp trích chọn đặc trưng chữ viết, dưới đây tôi sẽ trình bày chi tiết 3 phương pháp trích chọn đặc trưng chữ viết đó là : phương pháp sử dụng bộ phân tích thành phần chính, phương pháp sử dụng momen Legendre, phương pháp sử dụng mạng Neural nhân chập. Trong bài toán nhận dạng chữ viết tay bộ nhận dạng thường sử dụng các công cụ sau : phương pháp k-láng giềng gần nhất, mạng Neural truyền thẳng MLP, máy vector hỗ trợ SVM, mạng Neural RBF... Trong khuôn khổ của khóa luận này tôi chỉ xét bộ nhận dạng là mạng Neural RBF. 2.3 CÁC PHƯƠNG PHÁP TRÍCH CHỌN ĐẶC TRƯNG CHỮ VIẾT TAY Trích chọn đặc trưng đóng vai trò hết sức quan trọng để giải quyết bài toán nhận dạng chữ viết tay. Thực chất quá trình trích chọn đặc trưng của chữ viết tay tức là ta đi tìm các đại lượng để biểu diễn cho các ký tự viết tay, mà các đại lượng này ít bị thay đổi khi ký tự có sự biến đổi về hình dạng. Một phương pháp trích đặc trưng chữ viết tốt cho ra được các đặc trưng ít bị biến đổi khi ký tự bị biến dạng nhiều. Dưới đây xin dưới thiệu 3 phương pháp trích chọn đặc trưng hay được sử dụng cho bài toán nhận dạng chữ viết tay đó là : 2.2.1 Phương pháp trích chọn đặc trưng kết hợp biến đổi DCT và thuật toán phân tích thành phần chính PCA Khái niệm giá trị riêng và vector riêng (xem chi tiết ở [22])được các nhà toán học tìm ra vào cuối thể kỷ 19 đầu thế kỷ 20. Có hàng loạt tính chất quan trọng liên quan đến giá trị riêng và vector riêng, các tính chất này được ứng dụng rất nhiều trong các lĩnh Dữ liệu đầu vào (dạng ảnh) Trích chọn đặc trưng chữ viết Nhận dạng Đưa ra kết quả nhận dạng Chương 2: Nhận dạng chữ viết tay 26 vực kỹ thuật. Dưới đây là một trong các tính chất đó: cho tập dữ liệu X, A là ma trận hiệp phương sai của tập dữ liệu X (A là ma trận vuông). Khi đó tập vector riêng của A là tập các vector trực giao, và khi chiếu tập dữ liệu X lên tập các vector riêng này, thì dữ liệu sẽ dao đông nhiều quanh các vector riêng tương ứng với giá trị riêng lớn, dữ liệu ít dao động xung quanh các vector riêng tương ứng với các giá trị riêng nhỏ. Hình 16: Ảnh hưởng của vector riêng, giá trị riêng lên tập dữ liệu Thuật toán phân tích thành phần chính (PCA) là hệ quả trực tiếp của tính chất đã nêu trên. Trong kỹ thuật thuật toán PCA là một thuật toán phổ biến được sử dụng để giảm số chiều của dữ liệu nhưng vẫn giữ được nhiều thông tin khi phân biệt với các dữ liệu khác. Thuật toán PCA được đề xuất đầu tiên bởi H. Hotelling (ban đầu được biết với tên là biến đổi Hotelling-Hotelling’s transform). Dưới đây là nội dung thuật toán PCA, sau đó xin giới thiệu phương pháp trích chọn đặc trưng bằng cách sử dụng biến đổi cosin rời rạc (DCT) kết hợp với thuật toán PCA để thu gọn số chiều của dữ liệu. 2.2.1.1 Thuật toán PCA Giả sử ta có tập dữ liệu 1{ } D N i iX x R   trong đó các xi được sắp xếp thành các hàng để được ma trận X có kích thước N D . Ta mong muốn làm giảm số chiều dữ liệu tập X có D chiều thành tập dữ liệu Y có L chiều, L < D. Có thể tóm tắt thuật toán PCA như sau(xem chi tiết thuật toán ở [10,19], các khái niệm cơ sở xem thêm ở [10]) : +Bước 1: Tính giá trị trung bình trên từng chiều dữ liệu Sau tính giá trị trung bình trên từng chiều dữ liệu 1...D của tập dữ liệu X ta được vector giá trị trung bình u có kích thước 1D trong đó 1 1[ ] [ , ] N n u d X d n N    Chương 2: Nhận dạng chữ viết tay 27 +Bước 2: Thực hiện giảm giá trị của dữ liệu trên từng chiều với giá trị trung bình u[d] tương ứng: Ta lưu giá trị tính được vào ma trận B B = X – dh trong đó h là ma trận có kích thước 1 x N; [1, ] 1; 1...h n n N   +Bước 3: Tính ma trân hiệp phương sai của ma trận B   1· ·D D T TN       C B B B B B BE E +Bước 4: Tìm giá trị riêng và vector riêng của ma trận hiệp phương sai C Đầu tiên ta tính tập giá trị riêng ; 1..d d D  của ma trận C bằng cách giải phương trình det( ) 0C I  sau đó ta tìm tập vector riêng 1{ } D d dV v  cách giải phương trình 1V CV D  trong đó  MxM ; D i, j 0; i i j i j      +Bước 5 : Sắp xếp tập giá trị riêng d và tập vector riêng tương ứng theo chiều giảm dần của giá trị riêng +Bước 6 : Chọn lấy L vector đầu tiên từ tập vector riêng sau khi đã sắp xếp. [ , ] [ , ]; 1, , ; 1, ,W p q V p q p D q L       +Bước 7 : Tính giá trị của Y * TY X W Hình 17 : Các bước thực hiện của thuật toán PCA Nhìn chung việc tính giá trị riêng và vector riêng là một bài toán khó trong toán học. Trong phần thực nghiệm của mình, tôi sử dụng thư viện MATLAB để thực hiện tìm giá trị riêng và vector riêng của ma trận. 2.2.1.2 Phương pháp trích chọn đặc trưng kết phép biến đổi DCT và thuật toán PCA Ở đây ta xem dữ liệu đầu vào là ma trận điểm ảnh, hình vẽ dưới đây mô tả các bước của thuật toán: Hình 18: Các bước trích chọn đặc trưng bằng biến DCT kết hợp PCA Dữ liệu đầu vào (ma trận điểm ảnh NxM) Biến đổi DCT Lấy dữ liệu theo đường zigzag PCA Output (vector đặc trưng) Chương 2: Nhận dạng chữ viết tay 28 Từ ảnh dữ liệu ban đầu kích thước MxN dùng phép biến đổi Cosin rời rạc (DCT xem [20]) ta được ma trận MxN các hệ số thực. Sau đó ta lấy dữ liệu theo đường zigzag như hình vẽ bên dưới ta được vector với MxN đặc trưng. Tiếp đó ta dùng thuật toán PCA để thu gọn số chiều của vector đặc trưng, khi đó kết quả đầu ra sau bước này xem như là vector đặc trưng của bước ảnh đầu vào. Hình 19: Biến đổi DCT và cách lấy dữ liệu theo đường zigzag Ta thấy rằng bức ảnh gốc qua phép biến đổi DCT thì ta không bị mất thông tin vì ta có thể sử dụng phép biến đổi DCT nghịch đảo để thu được hình ảnh gốc. Ở ma trận hệ số của phép biến đổi DCT, các điểm ở gần gốc (1,1) thể hiện mức sáng nền của bức ảnh gốc, còn các điểm điểm càng xa điểm gốc thể hiện mức độ chi tiết của bước ảnh( trong thuật toán nén ảnh JPEG sau khi biến đổi DCT người ta thường lược bỏ các hệ số xa điểm gốc, mà mắt người vẫn không nhận thấy sự thay đổi), như vậy sau khi lấy dữ liệu cho vector đặc trưng theo đường zigzag thì các điểm gần nhau trên đường zigzag(cũng như trong vector đặc trưng) luôn có quan hệ về mặt giá trị cũng như ảnh hưởng đối với ảnh gốc. Điều này giúp cho vector đặc trưng mạng nhiều thông tin cho việc nhận dạng. Cuối cùng vector đặc trưng được xử lý qua thuật toán PCA để thu gọn số chiều dữ liệu giúp cho việc nhận dạng được hiệu quả hơn. 2.2.2 Phương pháp trích đặc trưng sử dụng Momen Legendre Trước khi đi sau vào chi tiết thuật toán xin giới thiệu các khái niệm cơ sở: 2.2.2.1 Momen và Momen Legendre 1) Khái niệm Momen (toán học) Trong toán học khái niệm momen xuất phát từ khái niệm momen trong vật lý, giá trị momen bậc n của hàm số thực f(x) tại c được định nghĩa như sau: Chương 2: Nhận dạng chữ viết tay 29 ( ) ( )nn x c f x dx      (1) Trong trường hợp f là hàm hai biến số thì momen bậc (n+m) của hàm số f(x,y) tại điểm (c1, c2) được định nghĩa như sau: 1 2( ) ( ) ( , ) n m n m x c y c f x y dxdy           (2) 2) Khái niệm Momen trong xử lý ảnh: Momen ảnh (image moments) là trọng số trung bình cụ thể nào đó của độ sáng các điểm ảnh, nếu ảnh là ảnh liên tục thì định nghĩa momen ảnh giống công thức (2), nếu ảnh đã rời rạc hóa thì momen bậc (m+n) tại điểm (c1,c2) của ảnh được định nghĩa như sau: 1 2 1 1 ( ) ( ) ( , ) M N m n m n x y x c y c I x y        (3) Trong đó M N  là kích thước của ảnh, I(x,y) là độ sáng của ảnh tại điểm (x,y). Giá trị momen ảnh được có thể dùng để mô tả các đối tượng ảnh sau khi đã được phân đoạn. Một số thuộc tính cơ bản của đối tượng ảnh có thể được phát hiện thông qua momen ảnh: diện tích, tâm, hướng của vật thể... Các momen bất biến (invarians moments) trong phép biến đổi ảnh được nghiên cứu vào thập niên 60 của thế kỷ 20. Momen bất biến là những giá trị momen không thay đổi trong các phép biến đổi ảnh như dời hình, xoay, đồng dạng... Trong giai đoạn nghiên cứu này rất nhiều loại momen được giới thiệu: Momen Legendre, momen Zernike... Kèm theo đó là rất nhiều thuật toán nhanh và hiệu quả để tính giá trị các momen này. 3) Định nghĩa momen Legendre: Momen Legendre bậc (m+n) của ảnh liên tục f(x,y) được định nghĩa như sau: 1 1 1 1 (2 1)(2 1) ( ) ( ) ( , ) 4mn m n m n P x P y f x y dx dy        Trong đó , 0,1,2,...,m n   , Pm, Pn là đa thức Legendre. Họ đa thức Legendre là tập các đa thức trực giao trên đoạn [-1,1]. Để tồn tại momen Legendre được xác định thì hàm f(x,y) phải xác định trên đoạn [-1,1]. Đa thức Legendre bậc n được định nghĩa như: Chương 2: Nhận dạng chữ viết tay 30 0 ( ) n j n nj j P x a x   trong đó ( )/2 1 ( )!( 1) ( ) 0 mod 2( ) ( )2 ( )!( )! ! 2 2 0 ( ) 1 mod 2 n j n nj n j n jn j n j ja n j                     M M -1 -0.5 0 0.5 1 1.5 2 -1 -0.5 0 0.5 1 n=0 n = 1 n = 2 n = 3 n = 4 n = 5 Hình 20: Họ đa thức Legendre Ta có thể xây dựng lại ảnh f(x,y) từ momen Legendre bằng công thức sau: 0 0 ( , ) ( ) ( ) k kl k l k l f x y p x p y     Với ảnh đã được rời rạc hóa Pxy ta có công thức sau để tính momen Legendre: (2 1)(2 1) ( ) ( ) 4 mn m n xy x y m n P x P y P     . Người ta đã chứng minh được rằng giá trị momen Legendre là đại lượng bất biến trong các phép dời hình, và đồng dạng (xem [7,15]). Vì thế momen Legendre thường được sử dụng để nhận dạng các đối tượng hình học khi nó bị biến đổi bằng phép dời hình hay phép đồng dạng. Tuy nhiên nhược điểm của momen Legendre đó là nó không phải là momen bất biến trong phép xoay hình vì vậy tầm ứng dụng của nó vẫn còn hạn chế. Dưới đây xin giới thiệu phương pháp trích chọn đặc trưng chữ viết bằng cách sử dụng momen Legendre. 2.2.2.2 Phương pháp trích chọn đặc trưng chữ viết tay bằng Momen Legendre Chương 2: Nhận dạng chữ viết tay 31 Tư tưởng chính của phương pháp như sau: Giả sử ta có ảnh đầu vào X, ta đặt MAX_ORDER là một giá trị cho trước nào đấy, sau đó ta tính tất cả các giá trị Momen Legendre bậc(m+n) sao cho m < n < MAX_ORDER. Các giá trị Momen này được lưu và ma trận L: (2 1)([ , 2 1) ( ) ( ) 4 ] mn m n xy x y m nL m n P x P y X     . Ta gọi ma trận L là ma trận momen Legendre. Sau khi tính xong ma trận L ta viết các giá trị của ma trận L thành một hàng và xem đó như là giá trị đặc trưng của ảnh đầu vào X. Do tính chất của Momen Legendre đó là bất biến với các phép biến đổi ảnh: dời hình và xoay hình nên nếu dữ liệu kiểm tra đồng dạng hay bị dời hình so với dữ liệu huấn luyện thì sẽ cho kết quả nhận dạng rất tốt. Sau đây là từng bước cụ thể của phương pháp trích chọn đặc trưng chữ viết tay bằng Momen Legendre: Bước 1: Chuyển đổi tọa độ: Chú ý rằng momen Legendre chỉ được xác định trên đoạn [-1,1] nên để áp dụng được với một bức ảnh kích thước M N bất kỳ thì ta phải thực hiện bước đổi tọa độ như sau: ta gọi i,j là tọa độ trên ảnh gốc 0 ,0i N j M    , x,y là tọa độ sau khi đổi 1 1, 1 1x y      , , 2 2c c N Mi j           và  max ,c cD i i j j   khi đó công thức chuyển đổi tọa độ là ( , ) ,c ci i j jx y D D        . Bước 2: Tính toán giá trị của ma trân Momen Legendre: Dưới đây là thủ tục viết bằng giả mã để tính giá trị của ma trận Momen Legendre For k:=0 to MAX_ORDER do For l:=0 to k do ( , ) : 0k l l   For i:= 0 to N do For j:=0 to M do : ci ix D   : cj jy D   ( , ) : ( , ) ( )* ( )* ( , )k l lk l l k l l P x P y f x y      End End ( , )*(2 2 1)*(2 1)( , ) : ( 1) *( 1) k l l k l lk l l N M           End Chương 2: Nhận dạng chữ viết tay 32 Chú ý để tính nhanh được Pn(x) ta có thể sử dụng công thức truy hồi sau (xem [7,15]):  0 1 1 2( ) 1; ( ) ; ( ) 2 1 ( ) ( 1) ( ) /n n nP x P x x P x n xP x n P x n          . Bước 3: Chuyển ma trận Legendre thành vector đặc trưng Thực chất ở bước này ta thực hiện viết giá trị các điểm trong ma trận Legendre thành một hàng (hay vector) và ta xem đó là vector đặc trưng của ảnh đầu vào. Hình 21: Các bước thực hiện của phương pháp trích chọn đặc trưng sử dung momen Legendre 2.2.3 Phương pháp sử dụng mạng Neural nhân chập (Convolution neural network) Phương pháp trích chọn đặc trưng sử dụng mạng neural nhân chập (chi tiết xem [8, 16]) được đề xuất đầu tiên bới LeCun và Bengio vào năm 1995. Đây là phương pháp trích chọn đặc trưng cho độ chính xác nhận dạng cao nhất hiện nay (đạt độ chính xác đến 99.6% với bộ dữ liệu MNIST). Trước khi đi sâu vào chi tiết thuật toán xin giới thiệu khái niệm cơ sở đó là: thao tác nhân chập trong xử lý ảnh (convolution operator). 2.2.3.1 Khái niệm cơ sở 1) Thao tác nhân chập Nhân chập là một khái niệm quen thuộc trong xử lý số tín hiệu (xem [23]), trong lĩnh vực xử lý ảnh thao tác nhân chập được dùng để biến đổi ảnh thành một dạng mong muốn nào đấy: như làm nổi cạnh (detect edge), là mượt ảnh (smoothing), làm sắc nét(sharpening)... Trong thao tác nhân chập người ta sử dụng mặt nạ nhân chập (convolution mask)- là ma trận vuông 2 chiều có kích thước là số lẻ(thông thường là 3x3 và 5x5) và tác động nhân chập vào tất cả các điểm của ảnh gốc. Thao tác nhân chập lên một điểm của ảnh gốc được thực hiện như sau: Chương 2: Nhận dạng chữ viết tay 33 +Bước 1: Đầu tiên tâm của mặt nạ nhân chập được đặt trùng vào điểm cần tính nhân chập. +Bước 2: Thực hiện nhân từng giá trị của mặt nạ nhân chập với giá trị độ sáng của điểm ảnh tương ứng +Bước 3: Cộng tổng của từng giá trị đã tính ở bước 2 kết quả lưu vào vị trí nhân chập của ảnh gốc. Hình 22: Thao tác nhân chập (nguồn 2.2.3.2 Phương pháp trích đặc trưng sử dụng mạng Neural nhân chập Tư tưởng chính của phương pháp này là biến một bức ảnh từ độ phân giải cao về ảnh có độ phân giải thấp hơn nhưng lại mang nhiều thông tin hơn cho quá trình nhận dạng hơn (bằng phép nhân chập và thu nhỏ ảnh). Phương pháp này đạt hiệu quả cao cho việc trích đặc trưng chữ viết tay là bởi vì nhờ thao tác nhân chập nó làm nổi bật lên được các đường nét, hình dạng, các giao điểm... của ký tự viết tay. Hơn nữa các đặc trưng của nó ít bị thay đổi bởi các phép dịch ảnh và phép biến dạng bóp méo ảnh (distortion). 1) Kiến trúc mạng Ta giả thiết ảnh đầu vào có kích thước 29x29, dưới đây là kiến trúc mạng để lấy đặc trưng: +Bước 1: Đầu tiên ta sử dụng 5 mặt nạ nhân chập khác nhau kích thước 5x5 thực hiện thao tác nhân chập lên ảnh gốc, sau khi nhân chập ta thực hiện phép thu nhỏ ảnh đi 2 lần. Vì quá trình nhân chập không tác động lên những điểm biên nên sau một phép nhân chập và thu nhỏ thì kích thước mới của ảnh sẽ là (n-3)/2 (n là kích thước ảnh ban đầu). +Bước 2: Với mỗi ảnh ở lớp thứ 2 ta dùng 10 mặt nạ nhân chập khác nhau kích thước 5x5 thực hiện nhân chập và thu nhỏ ảnh đi 2 lần, ta được 50 ảnh ở lớp thứ 3. Chương 2: Nhận dạng chữ viết tay 34 +Bước 3: với mỗi ảnh ở lớp thứ 3 ta lại dùng 2 mặt nạ nhân chập khác nhau kích thước 5x5 thực hiện nhân chập ta thu được 100 ảnh kích thước 1x1. Ta xem đây chính là 100 đặc trưng của ảnh gốc ban đầu. Hình 23: Quá trình trích chọn đặc trưng sử dụng mạng Neural nhân chập Hình 24: Minh họa quá trình lấy đặc trưng bằng mạng Neuron nhân chập 2) Huấn luyện mạng Quá trình huấn luyện mạng Neural nhân chập là quá trình xác định các hệ số của các mặt nạ nhân chập. Để làm được điều này người ta xem kiến trúc ở hình 23 như là một mạng Neural tuyến tính truyền thẳng nhiều tầng sau đó thêm bộ phân lớp tuyến tính vào sau, rồi người ta huấn luyện mạng bằng phương pháp lan truyền ngược (chi tiết xem thêm [8,16]). 2.4 THỰC NGHIỆM Input Lớp 2 Lớp 3 Đặc trưng Input 29x29 5x13x13 50x5x5 100x1x1 Convolution+ Subsampling Convolution+ Subsampling Convolution Chương 2: Nhận dạng chữ viết tay 35 2.4.1 Kết quả Dưới đây xin giới thiệu giới thiệu kết quả thực nghiệm so sánh hiệu suất của các phương pháp trích chọn đặc trưng chữ viết đã nêu ở trên. Ở tôi đây sử dụng bộ dữ liệu MNIST để thực hiện huấn luyện và kiểm tra. Bộ dữ liệu gồm 60000 dữ liệu huấn luyện, và 10000 dữ liệu kiểm tra, một dữ liệu là một bức ảnh kích thước 28x28 của một ký tự chữ số Arap. Tôi sử dụng bộ phân lớp là mạng Neural RBF với các phương pháp huấn luyện là: phương pháp huấn luyện 2-pha HDH, 1-pha+giả nghịch đảo, 2- pha + giả nghịch đảo. Cấu hình máy tiến hành thực nghiệm: HĐH Windows XP Professional, CPU Intel Core 2 Duo E6300 1.86GHz, RAM 2G. Dưới đây là bảng kết quả thực nghiệm: Bảng 2: Kết quả so sánh hiệu suất của các phương pháp trích chọn đặc trưng 2.4.2 Nhận xét Từ bảng số liệu trên ta thấy ta thấy ưu điểm vượt trội của phương pháp trích đặc trưng sử dụng mạng Neural nhân chập(Convolution), ta thấy ở cả 3 phương pháp huấn luyện mạng đều cho kết quả nhận dạng chính xác trên 99.1%. Phương pháp huấn luyện mạng HDH có thời gian huấn luyện mạng nhanh hơn nhưng có độ chính xác nhận dạng kém hơn phương pháp huấn luyện mạng 2 pha + giả nghịch đảo. Chú ý thời gian huấn luyện ở đây không tính thời gian trích chọn giá trị đặc trưng. Phương pháp trích chọn đặc trưng Phương pháp huấn luyện mạng Thời gian huấn luyện mạng(phút) Số lần nhận dạng sai trên bộ dữ liệu kiểm tra Độ chính xác(%) DCT+PCA 2 pha HDH 15.59 834 91.66% Legendre 2 pha HDH 8.94 818 91.82% Convolution 2 pha HDH 10.73 82 99.18% DCT+PCA 1 pha+giả nghịch đảo 15.56 1633 83.67% Legendre 1 pha+giả nghịch đảo 12.45 1713 82.87% Convolution 1 pha+giả nghịch đảo 11.34 96 99.14% DCT+PCA 2 pha+giả nghịch đảo 25.00 354 96.46% Legendre 2 pha+giả nghịch đảo 15.51 500 95% Convolution 2 pha+giả nghịch đảo 17.70 72 99.28% Chương 3: Các phương pháp cải thiện hiệu suất của mạng Neural RBF 36 CHƯƠNG 3 CÁC PHƯƠNG PHÁP CẢI THIỆN HIỆU SUẤT CỦA MẠNG NEURAL RBF Nội dung chương này gồm có: 3.1 Các phương pháp cải thiệu hiệu suất của mạng Neural RBF 3.2 Thực nghiệm 3.1 CÁC PHƯƠNG PHÁP CẢI THIỆU HIỆU SUẤT CỦA MẠNG NEURAL RBF Dưới đây là nội dung một số phương pháp nhằm cải thiện hiệu suất của mạng Neural RBF trong vấn đề nhận dạng chữ viết tay. Cải thiện hiệu suất ở đây có nghĩa là làm sao để tăng được chất lượng nhận dạng cũng như làm giảm được thời gian huấn luyện mạng và chi phí cài đặt mạng. 3.1.1 Tăng tập dữ liệu huấn luyện Ta thấy rằng trong bài toán phân lớp dữ liệu huấn luyện đóng vai trò rất quan trọng, nó ảnh hưởng trực tiếp đến chất lượng phân lớp, tập dữ liệu huấn luyện càng lớn thì chất lượng phân lớp càng cao. Tuy nhiên để tạo ra một tập dữ liệu tốt thì mất rất nhiều chi phí do đa phần việc tạo tập dữ liệu huấn luyện là phải làm thủ công. Vì vậy nếu có một cách nào đó làm tăng số lượng dữ liệu cho tập dữ liệu huấn luyện thì sẽ làm cho kết quả nhận dạng sẽ tốt hơn và chi phí cũng giảm đáng kể. Việc tăng số lượng tập dữ liệu phải đảm bảo được chất lượng và tính tự nhiên vốn có của nó, cũng như việc trích chọn đặc trưng thì việc tăng số lượng tập dữ liệu huấn luyện không có cách tổng quát đủ tốt, phải tùy vào bài toán cụ thể. Dưới đây tôi giới thiệu phương pháp tăng tập dữ liệu huấn luyện cho bài toán nhận dạng chữ viết tay bằng các biến phép biến đổi hình học. 3.1.1.1 Tăng tập dữ liệu bằng các phép biến đổi hình học Chương 3: Các phương pháp cải thiện hiệu suất của mạng Neural RBF 37 a) Biến đổi Elastic Phép biến đổi ảnh này thực ra người ta dùng một ma trận mặt nạ dạng vector với ý nghĩa là điểm nào trên ảnh gốc trùng với điểm gốc của một vector nào đấy thì sẽ bị dịch chuyển đến điểm ngọn của vector tương ứng. Hình 21: Ma trận vector cho phép biến đổi Elastic Hình 22: Ví dụ về phép biến đổi Elastic Hình 22 là ví dụ về phép biến đổi elastic, ta thấy rằng từ ảnh gốc bên trái sau 2 phép biến đổi elastic ta được thêm 2 ảnh khác cho dữ liệu đầu vào, bằng trực quan ta thấy rằng dữ liệu này rất đảm bảo chất lượng. Ngoài phép biến đổi Elastic người ta còn dùng kết hợp các phép biến đổi affine như: dịch ảnh, xoay ảnh, hay phóng to thu nhỏ… để cho được dữ liệu mới. Tuy nhiên phép biến đổi Elastic vẫn thông dụng hơn trong bài toán nhận dạng chữ viết tay do dữ liệu nó sinh ra đảm bảo chất lượng hơn và việc cài đặt thuật toán cũng như thời gian chạy của nó là rất nhanh. 3.1.2 Phương pháp học tập hợp Học tập hợp là các phương pháp học mà hàm mục tiêu được học bằng cách huấn luyện một số bộ học độc lập sau đó kết hợp chúng lại với nhau. Có thể mô hình toán học bằng công thức sau: 1 2( , ,..., )nh F h h h trong đó h có thể coi là phương pháp học tập hợp, 1 2, ,..., nh h h là các bộ học độc lập, F là một cách kết hợp nào đấy. Như vậy với phương pháp học tập hợp chúng ta phải giải quyết 2 vấn đề: +Thứ nhất: làm sao để tạo ra được các bộ học độc lập, độc lập ở đây có nghĩa là các bộ học phải có các phương pháp huấn luyện khác nhau, hay phải có các bộ dữ liệu huấn luyện khác nhau. +Thứ hai: làm sao để kết hợp hiệu quả các bộ học này. Chương 3: Các phương pháp cải thiện hiệu suất của mạng Neural RBF 38 Vấn đề thứ hai thường được giải quyết bằng cách kết hợp tuyến tính các bộ học lại với nhau tức là: 1 n i i i h w h   trong đó các trọng số wi được nhận giá trị lớn nếu bộ hi được đánh giá là tin cậy hơn các bộ học khác, ngược lại với các bộ học hi không đáng tin cậy thì ta cho trọng số wi tương ứng có giá trị nhỏ. Để giải quyết vấn đề thứ nhất có nhiều phương pháp để tiếp cận, xin giới thiệu 2 phương pháp thường được hay dùng đó là phương pháp: bagging và boosting. +Bagging(Bootstrap aggregating) Có thể tóm tắt phương pháp như sau: Giả sử ta có một bộ dữ liệu huấn luyện D gồm có n dữ liệu, phương pháp bagging sinh M bộ dữ liệu huấn luyện iD D có số lượng 'n n , các bộ học hi được huấn luyện bằng bộ dữ liệu Di tương ứng. Sau đó các bộ học được kết hợp bằng cách sau: 1 M i i i h w h   với 1 ; 1..iw i MM    +Boosting Tư tưởng chính của thuật toán như sau: Giả sử ta có bộ dữ liệu huấn luyện D, ta đánh trọng số cho các dữ liệu trong tập dữ liệu huấn luyện, đầu tiên các trọng số được gán bằng nhau. Tại mỗi bước thứ t của thuật toán, ta chọn bộ dữ liệu tD D sao cho các dữ liệu trong bộ dữ liệu Dt là những dữ liệu được đánh trọng số cao nhất, sau đó ta huấn luyện bộ học ht bằng bộ dữ liệu Dt. Sau khi huấn luyện xong ta dùng bộ học ht để thẩm định lại tập dữ liệu D những dữ liệu nào bị phân lớp sai thì ta tăng trọng số của nó lên 1, những dữ liệu phân lớp đúng ta giảm trọng số của nó đi 1. Lặp lại T lần như thế ta được T bộ học độc lập, ta có thể gán trọng số các bộ học này theo số lượng mà nó phân lớp đúng. 3.1.2.1 Phương pháp học tập hợp cải tiến Phương pháp này lấy tư tưởng chính của phương pháp học tập hợp như đã nêu ở trên, chỉ khác là kết quả của đầu ra cuối cùng không phải là tổ hợp tuyến tính của các bộ học mà đầu ra của các bộ học lại được huấn luyện một lần nữa cho kết quả cao hơn (nghĩa là ta tổ hợp phi tuyến tính các bộ học với nhau, thông qua mạng Neural RBF). Dưới đây là kiến trúc tổng thể của phương pháp học tập hợp cải tiến để giải quyết cho bài nhận dạng chữ số viết tay: Chương 3: Các phương pháp cải thiện hiệu suất của mạng Neural RBF 39 Hình 23: Kiến trúc của phương pháp học tập hợp cải tiến Ở đây tôi sử dụng các phương pháp trích chọn đặc trưng đơn giản có tốc độ tính toán nhanh (PCA, LEGENDRE, SUBSAMPLING-thu nhỏ ảnh) để tạo ra các bộ học khác nhau. Sau khi huấn luyện chúng qua mạng neural RBF tôi lại tổng hợp các đầu ra của các mạng Neural này và huấn luyện chúng lại một lần nữa bằng mạng Neural RBF. Phương pháp này tận dụng tối đa ưu điểm của mạng Neural RBF đó là thời gian huấn luyện mạng rất nhanh, trong khi để có một mạng có chất lượng tốt phương pháp mạng Neural nhân chập phải mất nhiều giờ thậm chí là nhiều ngày huấn luyện mạng để trích chọn giá trị đặc trưng thì với phương pháp này chỉ mất hơn một 1h để huấn luyện mạng và trích đặc trưng cho bộ dữ liệu MNIST. 3.1.3 Phương pháp tăng tốc độ nhận dạng Ở 2 phương pháp nêu trên tôi chỉ mới đề cấp đến vấn đề làm tăng độ chính xác nhận dạng cũng như làm làm giảm thời gian huấn luyện mà chưa đề cập đến vấn đề làm giảm thời gian nhận dạng của mạng. Đây là vấn đề then chốt trong các ứng dụng, vì thực ra quá trình huấn luyện thông thường được chạy ít hơn nhiều lần so với quá trình thực hiện nhận dạng (quá trình đưa dữ liệu đầu vào để cho mạng tính toán). Thời gian nhận dạng = thời gian trích chọn đặc trưng + thời gian tính toán trong mạng, như vậy việc tăng hiệu suất nhận dạng thông qua việc tinh chỉnh quá trình trích chọn đặc trưng sẽ làm cho thời gian trích chọn đặc trưng tăng lên đồng nghĩa với thời gian nhận dạng cũng tăng. Nói tóm lại là việc làm tăng hiệu suất nhận dạng và tăng tốc độ huấn luyện mạng thì sẽ dẫn đến việc làm tăng thời gian nhận dạng. Dưới đây tôi xin giới thiệu một phương pháp khá hay để vừa nâng cao tốc độ nhận dạng nhưng lại không giảm độ chính xác nhận đó là phương pháp Bộ phân nhận dạng ba lớp (chi tiết ở [13]). IN P U T SUB SAM PLIN G DCT+ PCA LEGE NDRE RBF RBF RBF RBF O U TP U T Chương 3: Các phương pháp cải thiện hiệu suất của mạng Neural RBF 40 3.1.3.1 Phương pháp bộ nhận dạng ba lớp Có thể tóm tắt phương pháp này như sau: người ta tạo ra ba bộ phân lớp có đặc điểm như sau: +Bộ phân lớp thứ nhất sử dụng phương pháp trích chọn đặc trưng đơn giản lấy ít đặc trưng và sử dụng mạng Neural có kiến trúc rất đơn giản để thực hiện nhận dạng tất nhiên là bộ phân lớp này sẽ có tốc độ nhận dạng rất nhanh nhưng lại có hiệu suất nhận dạng kém. +Bộ phân lớp thứ 2 ta sẽ lấy nhiều đặc trưng hơn bộ phân lớp trên đồng thời kiến trúc của mạng Neural nhận dạng cũng phức tạp hơn bộ phân lớp thứ nhất như vậy bộ phân lớp này sẽ có tốc độ nhận dạng chậm hơn nhưng bù lại lại có hiệu suất nhận dạng tốt hơn bộ thứ nhất. +Bộ phân lớp thứ 3 ta sẽ kết hợp giữa cách trích chọn đặc trưng tốt nhất và bộ phân lớp có kiến trúc phức tạp để đảm bảo được hiệu suất nhận dạng cao tất nhiên là có thời gian nhận dạng chậm. Sau khi đã xây dựng được ba bộ phân lớp như trên quá trình nhận dạng được xử lý như sau: dữ liệu đầu vào được đưa vào bộ phân lớp thứ nhất sau khi thực hiện nhận dạng nếu kết quả nhận dạng không bị nghi ngờ là sai thì ta chọn đó là kết quả nhận dạng cuối cùng, nếu không thì ta lại đưa dữ liệu đầu vào cho bộ phân lớp thứ 2 xử lý. Sau khi xử lý ở bộ phân lớp thứ 2 nếu kết quả nhận là tốt thì ta xác nhận kết quả nhận dạng này còn không ta lại chuyển dữ liệu đầu vào cho bộ phân lớp cuối cùng. Tất nhiên là với phương pháp này ta phải có thuật toán tốt để xác định độ nhập nhằng của kết quả nhận dạng. Hình 24: Kiến trúc của bộ nhận dạng ba lớp INPUT Bộ nhận phân lớp thứ nhất OUTPUT Nhập nhằng? Bộ nhận phân lớp thứ 2 Nhập nhằng? Bộ nhận phân lớp thứ 3 yes yes no no Chương 3: Các phương pháp cải thiện hiệu suất của mạng Neural RBF 41 Ta thấy với kiến trúc như trên thì phần lớn quá trình xử nhận dạng rơi vào bộ phân lớp thứ nhất (vì dựa vào kết quả thực nghiệm cho dù là bộ phân lớp tồi như cũng rất dễ dàng để đạt được độ chính xác nhận dạng > 70%). Xác xuất để việc nhận dạng xử lý trên bộ nhận dạng thứ 2 sẽ thấp và càng thấp hơn đối với bộ nhận dạng thứ ba. Hiển nhiên ta thấy rằng kiến trúc này sẽ có thời gian nhận dạng nhanh hơn nhiều so với cách chỉ sử dụng bộ phân lớp thứ 3 và cũng có độ chính xác tốt hơn nhiều so với cách chỉ sử dụng bộ phân lớp thứ nhất (xem chi tiết [13]). 3.2 THỰC NGHIỆM Biều đồ dưới đây so sánh hiệu suất của phương pháp học tập hợp cải tiến so với các phương pháp thông thường. Ở đây sử dụng bộ dữ liệu MNIST cho quá trình huấn luyện và kiểm tra. 90 91 92 95 94.5 95 97.75 99.3 84 86 88 90 92 94 96 98 100 1 2 3 4 5 6 7 8 8 8 8 8 18 13 63 1020 0 200 400 600 800 1000 1200 1 2 3 4 5 6 7 8 Hình 25: Biểu đồ so sánh độ chính xác nhận dạng và thời gian huấn luyện của các phương pháp huấn luyện khác nhau Ta thấy rằng phương pháp mạng Neural nhân chập vẫn cho độ chính xác nhận dạng là tốt nhất, song thời gian huấn luyện mạng của nó là quá lớn. Phương pháp học tập hợp cải tiến cho kết quả nhận dạng là khá cao trong khi thời gian huấn luyện của nó thấp hơn nhiều lần so với phương pháp mang Neural nhân chập. 1,2,3,4. Subsambling 5. PCA 6.Legedre 7.Học tập hợp cải tiến 8. Mạng Neural nhân chập Chương 4: Giới thiệu chương trình nhận dạng chữ số viết tay và tổng kết 42 CHƯƠNG 4 GIỚI THIỆU CHƯƠNG TRÌNH NHẬN DẠNG CHỮ SỐ VIẾT TAY VÀ TỔNG KẾT Nội dung chương này gồm có: 4.1 Giới thiệu chương trình nhận dạng chữ viết tay 4.2 Tổng kết và phương hướng phát triển của đề tài 4.1 GIỚI THIỆU CHƯƠNG TRÌNH NHẬN DẠNG CHỮ SỐ VIẾT TAY Dưới đây tôi xin giới thiệu chương trình ứng dụng nhận dạng chữ viết tay mà tôi đã viết. Chương trình là phần thực nghiệm của tất cả các phần lý thuyết mà tôi đã nêu ra xuyên suốt trong toàn bộ nội dụng của khóa luận mà tôi đã trình bày ở trên. 4.1.1 Chương trình nhận dạng chữ viết tay 4.1.1.1 Giới thiệu chương trình 1) Tính năng của chương trình Chương trình có khả năng nhận dạng chữ số viết tay do người dùng nhập file ảnh của ký tự nào đấy để thực hiện nhận dạng. Để nhận dạng chương trình cho phép người dùng tùy chọn phương pháp trích, và tùy chọn phương pháp huấn luyện mạng RBF. Sau khi thực hiện nhận dạng thì chương trình trả về cho người dùng biểu đồ thể hiện xác suất bức ảnh người dùng đã nhập vào là số nào. 2) Môi trường và công cụ phát triển Chương trình được viết hoàn toàn bằng ngôn ngữ C++, giao diện sử dụng IDE Microsoft Visio Studio 2008 để thiết kế, ngoài ra chương trình còn sử dụng một số thư viện của Matlab để tính toán ma trận. 3) Hướng dẫn sử dụng chương trình Để chương trình chạy được tốt, ta phải cài đặt thư viện Matlab vào máy và thêm thư mục bin của Matlab vào biến môi trường PATH của hệ điều hành. Người dùng có thể Chương 4: Giới thiệu chương trình nhận dạng chữ số viết tay và tổng kết 43 nhập ảnh với các định dạng như *.jpg, *.bmp, *. gif, *.png vào chương trình sau đó thực hiện nhận dạng chữ số, sau khi chương trình thực hiện xong nó sẽ đưa ra biểu đồ đánh giá xác suất bức ảnh là số nào dưa trên kết quả nhận dạng của mạng Neural. Ngoài ra người dùng có thể chọn chế độ để huấn luyện mạng Neural với các phương pháp trích chọn đặc và phương pháp huấn luyện khác nhau. Sau đây là giao diện chính của chương trình: Hình 26: Giao diện chính của chương trình Hình27: Bảng thông báo kết quả nhận dạng 4.2 TỔNG KẾT VÀ PHƯƠNG HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI 4.2.1 Tổng kết Đến đây tôi đã hoàn thành khóa luận tốt nghiệp với đề tài “Mạng Neural RBF và Ứng dụng nhận dạng chữ viết tay”. Với mục tiêu kết hợp giữa nghiên cứu lý thuyết mạng Neural RBF đi đôi với việc tìm hiểu bài toán nhận dạng chữ viết tay để thực hiện tạo chương trình ứng dụng nhận dạng chữ viết tay. 4.2.1.1 Những công việc đã làm được Chương 4: Giới thiệu chương trình nhận dạng chữ số viết tay và tổng kết 44 +Tìm hiểu được kiến trúc mạng Neural RBF, hiểu được các phương pháp huấn luyện mạng RBF, nhờ đó đã tiến hành cài đặt thành công được mạng Neural RBF với các thuật toán huấn luyện khác nhau (xem chương 1). +Tìm hiểu được bài toán nhận dạng chữ viết tay, hiểu được các bước để xử lý bài toán nhận dạng chữ viết tay. Tìm hiểu và tiến hành cài đặt được 3 phương pháp trích chọn đặc trưng chữ viết tay đó là: phương pháp kết hợp biến đổi DCT và thuật toán PCA, phương pháp sử dụng momen Legendre, phương pháp sử dụng mạng Neural nhân chập (xem chương 3). +Tìm hiểu các phương pháp để tăng hiệu suất cho mạng Neural RBF áp dụng cho bài toán nhận dạng chữ viết tay. Đề xuất phương pháp học tập hợp cải tiến cho hiệu suất nhận dạng 98% với bộ dữ liệu MNIST và có thời gian huấn luyện mạng rất nhanh. +Xây dựng được phần mềm nhận dạng chữ số viết tay. 4.2.2.2 Hướng phát triển của đề tài Do thời gian nghiên cứu có hạn nên đề tài khóa luận chưa thể đi sát vào các vấn đề được đưa ra. Nếu được phát triển thêm tôi sẽ nghiên cứu kỹ hơn về mạng neural RBF, nghiên cứu các cách huấn luyện khác cũng như các kiến trúc mạng RBF cải tiến làm cho việc huấn luyện nhanh hơn và hiệu suất nhận dạng tốt hơn. Bài toán nhận dạng chữ viết tay mặc dù đã được nghiên cứu từ lâu nhưng đến ngày nay vẫn được tiếp tục phát triển, đặc biệt là các bài toán nhận dạng văn bản tiếng việt, nhận dạng form... Do chưa thể đầu tư thời gian nhiều cho việc giải quyết bài toán nhận dạng chữ viết tay, nên chắc chắn tôi còn mắc thiếu sót rất nhiều ở phần này. Nếu phát triển tiếp thì ở phần nhận dạng chữ viết tay tôi sẽ nghiên cứu kỹ hơn các phương pháp trích chọn đặc trưng chữ viết cũng như các kỹ thuật làm tăng tốc độ nhận dạng của mạng (trong khóa luận tôi chưa dành thời gian nhiều để giải quyết vấn đề tăng tốc độ nhận dạng của mạng). Ở phần ứng dụng tôi cũng chỉ mới dừng lại mới dừng lại ở việc viết phần mềm nhận dạng chữ số viết tay, ứng dụng này không thực sự có ý nghĩa thực tiễn. Nếu tiếp tục nghiên cứu phát triển thêm thì tôi sẽ phát triển ứng dụng hướng đến việc nhận dạng ký tự tiếng việt, cũng như phát triển các ứng dụng thời gian thực. Tóm lại hướng phát triển của tôi cho đề tài khóa luận này là kết hợp giữa việc nghiên cứu sát hơn phần lý thuyết của mạng Neural RBF và việc đưa ra cách giải quyết hợp lý nhất cho bài toán nhận dạng chữ viết tay tiếng việt sử dụng mạng Neural RBF. TÀI LIỆU THAM KHẢO [1] Hoàng Xuân Huấn, Giáo trình các phương pháp số, NXB Đại học quốc gia Hà Nội, 2004 [2] Hoang Xuan Huan, Dang Thi Thu Hien and Huu Tue Huynh, A Novel Efficient Algorithm for Training Interpolation Radial Basis Function Networks, Signal Processing 87 ,2708 – 2717, 2007. [4] F. Schwenker, H.A. Kestler, Gu Ènther Palm, Three learning phases for radial-basis-function networks, Neural Networks 14 (2001) 439±458 [5] C.G. Looney, Pattern Recognition Using Neural Network, Theory and algorithm for engineers and scientist, Oxford University press, 1997. [6] N.B. Karayiannis, Member, IEEE, and Glenn Weiqun Mi. Growing Radial Basis Neural Networks: MergingSupervised and Unsupervised Learning with Network Growth Techniques. IEEE transactions on neural networks, vol. 8, no. 6, November 1997 [7] M. Vatkin, M. Selinger the system of handwritten characters recognition on the basis of legendre moments and neural network, The International Workshop on Discrete-Event System Design, DESDes’01, June 27÷29, 2001; Przytok near Zielona Gora, Poland [8] P.Y. Simard, Dave Steinkraus, John C. Platt, Best Practices for Convolutional Neural Networks Applied to Visual Document Analysis, Microsoft Research, One Microsoft Way, Redmond WA 98052 [9] S.Theodoridis, K.Koutroumbas Pattern recognition Second edition, 2ed., Elsevier, 2003 [10] J. Shlens, A Tutorial on Principal Component Analysis, April 22, 2009 [11] T.M. Mitchell, Machine learning, McGraw-Hill, 1997 [12] D.S. Broomhead and D. Lowe. Multivariable functional interpolation and adaptive networks. Complex Systems, vol. 2, 321-355, 1988. [13] D. Gorgevik, D. Cakmakov. An Efficient Three-Stage Classifier for Handwritten Digit Recognition. Proceedings of the 17th International Conference on Pattern Recognition (ICPR’04). [14] R. H. Bartels, J. C. Beatty and B. A. Barsky, An introduction to Splines for use in computer graphics & geometrics modeling, Morgan Kaufmann Publishers, 1987 [15] K.M. Hosny, New Set of Rotationally Legendre Moment Invariants, International Journal of Electrical and Electronics Engineering 2:3 2007 [16] D. Bouchain, Character Recognition Using Convolutional Neural Networks, 2006 [17] R. Esposito, Ensemble Learning [18] Wikipedia®, k-means clustering, means_clustering [19] Wikipedia®, Principal component analysis, [20] Wikipedia®, Discrete cosine transform, [21] Wikipedia®, Image moments, [22] Wikipedia®, Eigenvalue, eigenvector and eigenspace, [23] Wikipedia®,Convolution