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 , t