Tài liệu Nghiên cứu về mô hình thống kê học sâu và ứng dụng trong nhận dạng chữ viết tay hạn chế

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG MAI VĂN THỦY NGHIÊN CỨU VỀ MÔ HÌNH THỐNG KÊ HỌC SÂU VÀ ỨNG DỤNG TRONG NHẬN DẠNG CHỮ VIẾT TAY HẠN CHẾ LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG MAI VĂN THỦY NGHIÊN CỨU VỀ MÔ HÌNH THỐNG KÊ HỌC SÂU VÀ ỨNG DỤNG TRONG NHẬN DẠNG CHỮ VIẾT TAY HẠN CHẾ Chuyên ngành : Khoa Học Máy Tính Mã số : 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Vũ Tất Thắng THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ iii LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Qua đây tôi xin chân thành cảm ơn toàn thể các thầy cô trong khoa đào tạo sau đại học Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên, những người đã trực tiếp giảng dạy, truyền đạt cho tôi kiến thức chuyên môn và phương pháp làm việc khoa học. Đặc biệt, tôi xin chân thành cảm ơn TS. Vũ Tất Thắng, đã tận tình hướng dẫn để tôi có thể hoàn thành luận văn này. Tôi cũng xin gửi lời cảm ơn tới gia đình bạn bè đã giúp đỡ, động viên và tạo điều kiện cho tôi trong quá trình làm luận văn. Tác giả luận văn Mai Văn Thủy Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ iv MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i MỤC LỤC ................................................................................................................. iv DANH MỤC HÌNH ẢNH ........................................................................................ vi DANH MỤC BẢNG BIỂU .....................................................................................vii LỜI MỞ ĐẦU ............................................................................................................ 1 Chương 1: GIỚI THIỆU ĐỀ TÀI............................................................................ 3 1.1. Giới thiệu về bài toán nhận dạng .................................................................. 3 1.1.1. Các giai đoạn phát triển ............................................................................. 3 1.1.2. Tình hình nghiên cứu trong nước .............................................................. 4 1.1.3. Tình hình nghiên cứu ở nước ngoài ........................................................... 4 1.2. Các bước xử lý cho bài toán nhận dạng hoàn chỉnh ................................... 6 1.3. Kết luận chương ............................................................................................. 8 Chương 2: MÔ HÌNH SVM VÀ MÔ HÌNH THỐNG KÊ HỌC SÂU ................. 9 2.1. Tổng quan về mô hình SVM (Support Vector Machine) ........................... 9 2.1.1. Cơ sở lý thuyết ........................................................................................... 9 2.1.1.1. Giới thiệu bài toán phân lớp nhị phân ................................................. 9 2.1.1.2. Máy SVM tuyến tính......................................................................... 10 2.1.1.3. Máy SVM phi tuyến .......................................................................... 17 2.1.2. Các thuật toán huấn luyện SVM .............................................................. 19 2.1.2.1. Thuật toán chặt khúc ......................................................................... 19 2.1.2.2. Thuật toán phân rã............................................................................. 19 2.1.2.3. Thuật toán cực tiểu tuần tự................................................................ 20 2.2. Cơ sở lý thuyết mô hình thống kê học sâu ................................................. 23 2.2.1. Một số lý thuyết về mạng Neuron ........................................................... 23 2.2.1.1. Giới thiệu về mạng Neuron ............................................................... 23 2.2.1.2. Cấu trúc và hoạt động của mạng Neuron .......................................... 23 2.2.1.3. Quá trình huấn luyện mạng và các thuật toán học mạng .................. 28 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ v 2.2.2. Hopfield Network .................................................................................... 31 2.2.2.1. Cấu trúc mạng Hopfield .................................................................... 31 2.2.2.2. Mạng Hopfield rời rạc ....................................................................... 33 2.2.2.3. Mạng Hopfield liên tục ..................................................................... 34 2.2.3. Boltzmann Machines ............................................................................... 36 2.2.4. Restricted Boltzmann Machines .............................................................. 39 2.2.3. Thuật toán lan truyền ngược .................................................................... 40 2.3. Kết luận chương ........................................................................................... 42 Chương 3: KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ .................................. 43 3.1. Môi trường thực nghiệm .............................................................................. 43 3.2. Dữ liệu thực nghiệm ..................................................................................... 43 3.3. Kết quả thực nghiệm với mô hình SVM..................................................... 44 3.4. Huấn luyện mô hình và kết quả thực nghiệm với mô hình thống kê học sâu .................................................................................................................. 45 3.4.1. Huấn luyện mô hình................................................................................. 45 3.4.1.1. Cấu trúc mô hình ............................................................................... 45 3.4.1.2. Phương pháp huấn luyện và quy trình nhận dạng ............................. 47 3.4.2. Giao diện chính của chương trình............................................................ 48 3.4.3. Kết quả thực nghiệm ................................................................................ 49 3.5. Đánh giá kết quả thực nghiệm của hai mô hình. ....................................... 50 3.6. Kết luận chương ........................................................................................... 51 KẾT LUẬN CHUNG .............................................................................................. 52 TÀI LIỆU THAM KHẢO ...................................................................................... 54 PHỤ LỤC: HUẤN LUYỆN MÔ HÌNH ................................................................ 56 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ vi DANH MỤC HÌNH ẢNH Hình 1-1: Các bước trong nhận dạng chữ viết tay ...................................................... 6 Hình 2-1: Các siêu phẳng H 1 , H 2 phân cách giữa hai lớp ......................................... 9 Hình 2-2: Siêu phẳng tách tuyến tính ....................................................................... 10 Hình 2-3: Không thể phân hoạch tập mẫu trên bằng một siêu phẳng ....................... 13 Hình 2-4: Một mặt phân chia phi tuyến có thể trở thành một siêu phẳng trong không gian lớn hơn. ............................................................................................ 17 Hình 2-5: Cấu trúc của một neuron .......................................................................... 24 Hình 2-6: Cấu trúc chung của mạng neuron ............................................................. 26 Hình 2-7: Cấu trúc của mạng Hopfield ..................................................................... 31 Hình 2-8: Đồ thị hàm satlins ..................................................................................... 32 Hình 2-9: Mạng Hopfield liên tục sử dụng mạch điện tử. ........................................ 35 Hình 2-10: Một Boltzmann Machine với 3 nút ẩn .................................................... 36 Hình 2-11: Một RBM đơn giản với 3 hidden units và 2 visible units. .................... 39 Hình 3-2: Giao diện chính của chương trình nhận dạng chữ viết tay hạn chế ......... 48 Hình 3-3: Chương trình khi nhận dạng 1 ảnh bất kỳ ................................................ 48 Hình 3-4: Nhận dạng và thống kê nhiều ảnh ............................................................ 49 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ vii DANH MỤC BẢNG BIỂU Bảng 2-1: Các hàm truyền cơ bản ............................................................................. 27 Bảng 3-1: Kết quả thực nghiệm mô hình SVM trên 2 tập dữ liệu MNIST và Tuyển Sinh ........................................................................................................... 44 Bảng 3-2: Kết quả thực nghiệm mô hình SVM trên tập dữ liệu MNIST ................. 44 Bảng 3-3: Kết quả thực nghiệm mô hình SVM trên tập dữ liệu Tuyển Sinh ........... 45 Bảng 3-4: Kết quả thực nghiệm trên 2 tập dữ liệu MNIST và Tuyển Sinh .............. 49 Bảng 3-5: Kết quả thực nghiệm trên tập dữ liệu Tuyển sinh .................................... 50 Bảng 3-6: Bảng so sánh kết quả giữa hai mô hình ................................................... 50 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 1 LỜI MỞ ĐẦU Nhận dạng chữ viết tay là bài toán khó trong lớp các bài toán nhận dạng chữ, và vẫn luôn thu hút được nhiều sự quan tâm nghiên cứu của các nhà khoa học. Đặc biệt là trong vài thập niên gần đây, do sự thúc đẩy của quá trình tin học hóa trong mọi lĩnh vực, ứng dụng nhận dạng chữ càng có nhiều ý nghĩa khi được sử dụng cho các bài toán trong thực tế. Cũng như nhiều bài toán nhận dạng tiếng nói, hình ảnh… khác, thì độ chính xác của hệ thống vẫn tiếp tục cần phải cải thiện nhằm vươn tới khả năng nhận dạng giống như con người. Tuy nhiên, với bài toán nhận dạng chữ viết tay thì vấn đề trở nên phức tạp hơn nhiều so với bài toán nhận dạng chữ in thông thường ở những vấn đề sau đây [3]:  Với chữ viết tay thì không thể có các khái niệm font chữ, kích cỡ chữ. Các kí tự trong một văn bản chữ viết tay thường có kích thước khác nhau. Thậm chí, cùng một kí tự trong một văn bản do một người viết nhiều khi cũng có độ rộng, hẹp, cao, thấp khác nhau,...  Với những người viết khác nhau chữ viết có độ nghiêng khác nhau (chữ nghiêng nhiều/ít, chữ nghiêng trái/phải...).  Các kí tự của một từ trên văn bản chữ viết tay đối với hầu hết người viết thường bị dính nhau vì vậy rất khó xác định được phân cách giữa chúng.  Các văn bản chữ viết tay còn có thể có trường hợp dính dòng (dòng dưới bị dính hoặc chồng lên dòng trên). Trong những năm gần đây, mô hình mạng Neuron theo hướng học sâu đã cho thấy những kết quả tốt trong nhiều bài toán khác nhau, trong đó có nhận dạng chữ. Xuất phát từ yêu cầu thực tế, đang rất cần có nhưng nghiên cứu về vấn đề này. Chính vì vậy học viên đã chọn đề tài “Nghiên cứu về mô hình thống kê học sâu và ứng dụng trong nhận dạng chữ viết tay hạn chế” làm luận văn tốt nghiệp với mong muốn phần nào áp dụng vào bài toán thực tế. Bài toán đã đặt ra phải giải quyết được những yêu cầu sau:  Nhận dạng được các ký tự từ ảnh đầu vào Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 2  Tiến hành nhận dạng kí tự đơn lẻ sử dụng mạng Neuron nhân tạo theo phương pháp học sâu Restricted Boltzmann machine (RBM).  Đánh giá kết quả và so sánh với mô hình Support Vector Machine Với nhưng yêu cầu đã đặt ra ở trên, cấu trúc của luận văn sẽ bao gồm những nội dung sau đây:  Chương 1:Tổng quan về đề tài Giới thiệu về bài toán nhận dạng chữ viết tay, tình hình nghiên cứu trong và ngoài nước, quy trình chung để giải quyết bài toán và các phương pháp điển hình trong việc huấn luyện nhận dạng, phạm vi của đề tài.  Chương 2: Mô hình SVM và mô hình thống kê học sâu Trình bày về cơ sở lý thuyết của mô hình SVM (Support Vector Machine) và huấn luyện trong bài toán nhận dạng chữ viết tay. Cơ sở lý thuyết của mô hình thống kê học sâu: Hopfield network, Boltzmann Machines, Restricted Boltzmann Machines và thuật toán lan truyền ngược.  Chương 3: Kết quả thực nghiệm và đánh giá Trình bày các kết quả thực nghiệm của hai mô hình SVM và mô hình thống kê học sâu, đưa ra kết quả đánh giá nhận dạng chữ viết tay hạn chế giữa mô hình SVM và mô hình thống kê học sâu. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 3 Chương 1 GIỚI THIỆU ĐỀ TÀI 1.1. Giới thiệu về bài toán nhận dạng Nhận dạng chữ in: đã được giải quyết gần như trọn vẹn (sản phẩm FineReader 11 của hãng ABBYY có thể nhận dạng chữ in theo 192 ngôn ngữ khác nhau, phần mềm nhận dạng chữ Việt in VnDOCR 4.0 của Viện Công nghệ Thông tin – Viện Hàn lâm Khoa học và Công nghệ Việt Nam có thể nhận dạng được các tài liệu chứa hình ảnh, bảng và văn bản với độ chính xác trên 98%). Nhận dạng chữ viết tay vẫn còn là vấn đề thách thức lớn đối với các nhà nghiên cứu. Bài toàn này chưa thể giải quyết trọn vẹn được vì nó hoàn toàn phụ thuộc vào người viết và sự biến đổi quá đa dạng trong cách viết và trạng thái sức khỏe, tinh thần của từng người viết. 1.1.1. Các giai đoạn phát triển  Giai đoạn 1 (1900 - 1980) - Nhận dạng chữ được biết đến từ năm 1900, khi nhà khoa học người Nga Alan Turing (1912-1954) phát triển một phương tiện trợ giúp cho những người mù. - Các sản phẩm nhận dạng chữ thương mại có từ những năm1950, khi máy tính lần đầu tiên được giới thiệu tính năng mới về nhập và lưu trữ dữ liệu hai chiều bằng cây bút viết trên một tấm bảng cảm ứng.Công nghệ mới này cho phép các nhà nghiên cứu làm việc trên các bài toán nhận dạng chữ viết tay online. - Mô hình nhận dạng chữ viết được đề xuất từ năm 1951 do phát minh của M. Sheppard được gọi là GISMO, một robot đọc-viết. - Năm 1954, máy nhận dạng chữ đầu tiên đã được phát triển bởi J. Rainbow dùng để đọc chữ in hoa nhưng rất chậm. - Năm 1967, Công ty IBM đã thương mại hóa hệ thống nhận dạng chữ.  Giai đoạn 2 (1980 - 1990) - Với sự phát triển của các thiết bị phần cứng máy tính và các thiết bị thu nhận dữ liệu, các phương pháp luận nhận dạng đã được phát triển trong giai đoạn trước Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 4 đã có được môi trường lý tưởng để triển khai các ứng dụng nhận dạng chữ. - Các hướng tiếp cận theo cấu trúc và đối sánh được áp dụng trong nhiều hệ thống nhận dạng chữ. - Trong giai đoạn này, các hướng nghiên cứu chỉ tập trung vào các kỹ thuật nhận dạng hình dáng chứ chưa áp dụng cho thông tin ngữ nghĩa. Điều này dẫn đến sự hạn chế về hiệu suất nhận dạng, không hiệu quả trong nhiều ứng dụng thực tế.  Giai đoạn 3 (1990 - nay) - Các hệ thống nhận dạng thời gian thực được chú trọng trong giai đoạn này. - Các kỹ thuật nhận dạng kết hợp với các phương pháp luận trong lĩnh vực học máy (Machine Learning) được áp dụng rất hiệu quả. - Một số công cụ học máy hiệu quả như mạng Neuron, mô hình Markov ẩn, SVM (Support Vector Machines) và xử lý ngôn ngữ tự nhiên... 1.1.2. Tình hình nghiên cứu trong nước Tại Việt Nam, trong những năm gần đây có rất nhiều những nhóm nghiên cứu về nhận dạng chữ viết tay sử dụng các mô hình phổ biến hiện nay như: SVM (Support Vector Machine), HMM (Hidden Markov Model), mạng Neuron… Nhưng nhìn chung thì chất lượng nhận dạng của các mô hình này đều chưa cao vì chữ viết tay còn nhiều các yếu tố tác động đến như: độ cao, độ nghiêng, các nét liền… của chữ viết đều ảnh hưởng rất nhiều đến quá trình nhận dạng. Hiện tại, chúng ta mới chỉ có được những sản phẩm thử nghiệm như hệ thống nhận dạng chữ số và chữ cái viết tay rời rạc trên các phiếu xuất nhập cảnh của nhóm nghiên cứu ở Đại học quốc gia thành phố Hồ Chí Minh,… 1.1.3. Tình hình nghiên cứu ở nước ngoài Nhận dạng chữ viết đã được nghiên cứu hơn 40 năm qua. Ngày nay nhận dạng chữ viết đã nhận được sự quan tâm đáng kể do sự phát triển của các máy tính cầm tay và điện thoại cầm tay dựa trên các bàn phím, chuột và nhiều dạng thiết bị định vị khác. 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 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 5 các chữ được viết lên màn hình ngay sau 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 ra. Đây chính là cơ sở để máy tính nhận dạng được chữ cái, do đó việc nhận dạng không gặp quá nhiều khó khăn. Hệ thống nhận dạng chữ viết tay hạn chế trực tuyến trên một trạm làm việc của IBM [11] do nhóm nghiên cứu gồm H.S.M.Beigi, C.C.Tapert, M.Ukeison và C.G.Wolf ở phòng thực hành Watson IBM cài đặt là một trong những sản phẩm nhận dạng chữ viết tay online tiêu biểu nhất. Tuy nhiên, do chưa có nhiều ứng dụng thực tế nên nhận dạng chữ viết tay trực tuyến chưa được biết đến nhiều và khi nhắc đến nhận dạng chữ viết tay chúng ta thường hiểu hình thức nhận dạng ở đây là offline. Các kết quả nhận dạng chữ viết tay offline hiện này còn rất hạn chế. Các kết quả nghiên cứu chưa tìm được giải pháp đủ tốt để giải quyết hết những khó khăn tiêu biểu sau của bài toán nhận dạng chữ viết tay:  Kích thước của chữ viết tay không đồng đều.  Kiểu dáng chữ của mỗi người viết đều rất khác nhau.  Giữa các kí tự trong cùng một từ thường có nét nối, thậm chí dính liền vào nhau.  Các kí tự có thể thiếu hoặc thừa nét.  Xuất hiện tình trạng dính dòng. Do những khó khăn trên nên khi giải quyết bài toán nhận dạng chữ viết tay đều buộc phải giới hạn trong một phạm vi nào đó với những tiêu chuẩn cụ thể cho mẫu chữ nhận dạng. Chính vì vậy, các kết quả thu được cũng chỉ được áp dụng một cách hạn chế ở lĩnh vực hẹp trong một bài toán cụ thể nào đó. Một số hệ nhận dạng chữ viết tay tiêu biểu có thể kể đến như: hệ thống nhận dạng chữ viết tay trong lĩnh vực kiểm tra tài khoản ở ngân hàng của nhóm nghiên cứu Simon và O.Baret (Laoria/CNRS & ENPC, Paris) [11], hệ thống phân loại tự động địa chỉ thư ở bưu điện của M.Pfister, S.Behnke và R.Rojas ở Đại học tổng hợp Berlin, Đức [5]…. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 6 1.2. Các bước xử lý cho bài toán nhận dạng hoàn chỉnh Nhận dạng chữ viết tay thường bao gồm năm giai đoạn: tiền xử lý (preprocessing), tách chữ (segmentation), trích chọn đặc trưng (representation), huấn luyện và nhận dạng (training and recognition), hậu xử lý (postprocessing). Hình 1-1: Các bước trong nhận dạng chữ viết tay  Tiền xử lý (preprocessing): giảm nhiễu cho các lỗi trong quá trình quét ảnh, hoạt động viết của con người, chuẩn hóa dữ liệu và nén dữ liệu.  Tách chữ (segmentation): chia nhỏ văn bản thành những thành phần nhỏ hơn, tách các từ trong câu hay các kí tự trong từ.  Trích trọn đặc trưng (representation): giai đoạn đóng vai trò quan trọng nhất trong nhận dạng chữ viết tay. Để tránh những phức tạp của chữ viết tay cũng như tăng cường độ chính xác, ta cần phải biểu diễn thông tin chữ viết dưới những dạng đặc biệt hơn và cô đọng hơn, rút trích các đặc điểm riêng nhằm phân biệt các ký tự khác nhau. Trong luận văn này, tôi nghiên cứu và tìm hiểu về mô hình học thống kê học sâu, trong mô hình này thì khi huấn luyện và sử dụng dữ liệu chúng ta không cần sử dụng đặc trưng của ảnh đầu vào nên có thể bỏ qua bước trích rút đặc trưng.  Huấn luyện và nhận dạng (training and recognition): phương pháp điển hình so trùng mẫu, dùng thống kê, mạng neuron, mô hình markov ẩn, trí tuệ Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 7 nhân tạo hay dùng phương pháp kết hợp các phương pháp trên.Trong luận văn này, tôi sử dụng mô hình thống kê học sâu (deep learning) để huấn luyện và nhận dạng, nội dung này sẽ được trình bày trong các chương sau của luận văn.  Hậu xử lý (postprocessing): sử dụng các thông tin về ngữ cảnh để giúp tăng cường độ chính xác, dùng từ điển dữ liệu. Ban đầu các văn bản chữ viết tay được scan và đưa vào hệ thống nhận dạng, với quá trình tiền xử lý thì ảnh sẽ được một ảnh mà do hệ thống yêu cầu để huấn luyện và nhận dạng (có thể là ảnh nhị phân hay ảnh đa mức xám). Trong mô hình thống kê học sâu, ảnh được sử dụng để huấn luyện và nhận dạng là ảnh đa mức xám (các pixel được biểu diễn bởi các giá trị từ 0 đến 255). Tại quá trình tiền xử lý thì ảnh cũng đã được xử lý loại bỏ nhiễu, các giá trị không cần thiết trong ảnh đầu vào. Tại bước tách chữ thì với ảnh đã được tiền xử lý, khi đi qua bước này sẽ được thực hiện tách dòng, tách chữ, tách kí tự để thực hiện nhận dạng, tùy theo quy định của một hệ thống khi huấn luyện. Khi đã được tách rời các kí tự thì việc tiếp theo ảnh để nhận dạng sẽ được lưu dưới dạng ma trận điểm, với tùy từng vị trí của điểm ảnh mà giá trị có thể khác nhau (từ 0 đến 255), trong mô hình Deep Learning thì ma trận điểm ảnh sẽ được quy về dạng chuẩn là 28 x 28. Sau khi qua các bước xử lý ở trên thì ảnh chính thức được đưa vào huấn luyện và nhận dạng, trong quá trình huấn luyện và nhận dạng sẽ sử dụng các mô hình và thuật toán cần thiết để thực hiện tính toán và xử lý, những thuật toán và quá trình xử lý sẽ được trình bày chi tiết trong các phần sau của luận văn. Cuối cùng khi các ảnh đầu vào đã được đưa vào nhận dạng và cho ra kết quả thì bước quan trọng không kém là quá trình hậu xử lý với các kết quả ở trên, và trả lại kết quả cho người dử dụng. [3] Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 8 1.3. Kết luận chương Luận văn “Nghiên cứu về mô hình thống kê học sâu và ứng dụng trong nhận dạng chữ viết tay hạn chế” được thực hiện với mục đích giải quyết một lớp con các bài toán nhận dạng chữ viết tay mà cụ thể là nhận dạng các kí tự đơn lẻ là các chữ số từ 0 đến 9, đây là bước cần thiết trong bài toán nhận dạng chữ viết tiếng Việt. Từ đó sẽ tạo cơ sở tiếp theo để có thể xây dựng tiếp mô hình nhận dạng các kí tự tiếng Việt đơn lẻ, và sẽ tiến tới xây dựng một hệ thống nhận dạng văn bản viết tay tiếng Việt hoàn chỉnh, và cũng có thể xây dựng nên các phần mềm trên các thiết bị di động áp dụng vào việc hỗ trợ việc học tập và sinh hoạt của người khiếm thị. Luận văn sẽ tập trung vào nghiên cứu về cơ sở lý thuyết mô hình Deep Learning, các thuật toán được sử dụng, thực hiện huấn luyện bằng mô hình Deep Learning, từ đó cài đặt chương trình mô phỏng trên các ngôn ngữ như Matlab, PHP, C#. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 9 Chương 2 MÔ HÌNH SVM VÀ MÔ HÌNH THỐNG KÊ HỌC SÂU 2.1. Tổng quan về mô hình SVM (Support Vector Machine) 2.1.1. Cơ sở lý thuyết 2.1.1.1. Giới thiệu bài toán phân lớp nhị phân Bài toán phân lớp nhị phân [7] này được phát biểu như sau: Cho tập dữ liệu gồm N mẫu huấn luyện { ( x1 , y1 ),...,( xN , y N ) } trong đó xi RD và yi {±1}. Tìm một siêu phẳng phân cách w.x + b = 0 để tách tập dữ liệu trên thành 2 lớp, trong đó w là véc tơ pháp tuyến của siêu phẳng, có tác dụng điều chỉnh hướng của siêu phẳng, giá trị b có tác dụng di chuyển siêu phẳng song song với chính nó. Có thể có nhiều siêu phẳng để phân cách được hai tập dữ liệu đó (hình dưới) và cũng đã có nhiều thuật toán để giải bài toán này, chẳng hạn như thuật toán Perceptron của Rosenblatt, thuật toán biệt thức tuyến tính của Fisher. Tuy nhiên vấn đề là cần tìm ra siêu phẳng nào làm cho khoảng cách Euclid giữa hai lớp trên là lớn nhất, khi đó bài toán phân lớp mới được giải quyết triệt để và phương pháp SVM được sử dụng để giúp tìm ra siêu phẳng này. [2] Hình 2-1: Các siêu phẳng H 1 , H 2 phân cách giữa hai lớp Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 10 2.1.1.2. Máy SVM tuyến tính SVM trong trường hợp tập mẫu phân hoạch tuyến tính được Ý tưởng chính của SVM là tìm một siêu phẳng phân cách H: w.x + b = 0 [8] và hai siêu phẳng song song với nó: H1 : y wx b H2 : y w.x b 1 1 với điều kiện không có phần tử nào nằm giữa H1 và H2 sao cho khoảng cách (margin) giữa H 1 và H 2 đạt cực đại (Hình 2.2). Hình 2-2: Siêu phẳng tách tuyến tính Mục đích của ta là cực đại khoảng cách giữa H1 và H2. Vì vậy, chúng ta phải xác định cho được những mẫu dương nằm trên H1 và mẫu âm nằm trên H2. Các mẫu này được gọi là vector hỗ trợ bởi vì chỉ có chúng tham gia vào việc xác định siêu phẳng phân cách, còn các mẫu khác thì có thể loại bỏ. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 11 Ta có hai khoảng cách của một điểm nằm trên khoảng cách giữa H 1 và H 2 là tới H là | wx b | || w || 1 và || w || 2 . Do đó, trong trình tự để cực đại hóa khoảng || w || cách này, ta sẽ cực tiểu || w || wT .w với điều kiện không có điểm dữ liệu nào nằm giữa H 1 và H 2 : w.x + b> +1, với các mẫu dương yi w.x + b< -1, với các mẫu âm yi 1 1 Hai điều kiện này có thể kết nối lại thành yi ( wxi b) 1 Từ đó bài toán có thể được phát biểu lại như sau: 1 min wT w sao cho yi ( wxi w ,b 2 b) 1 (*) Thay vì giải bài toán (*), ta có thể giải bài toán đối ngẫu của Wolfe để thay thế: cực đại L (w, b, α) theo α, sao cho đạo hàm của L (w, b, α) triệt tiêu theo các biến w và b: L w L b (1) 0 (2) 0 Và α ≥ 0 Ở đây, L (w, b, α) là đa thức Lagrange với hệ số Lagrange L( w, b, ) 1 T w w 2 Số hóa bởi Trung tâm Học liệu - ĐHTN N N i yi ( wxi i 1 : b) i i 1 http://www.lrc-tnu.edu.vn/ 12 Từ (1) và (2) ta có: N N và i yi xi w i 1 i yi 0 i 1 Thế vào L (w, b, α), ta có: N LD 1 2 i i 1 i Ở đây chúng ta có các hệ số Largrang huấn luyện xong, những mẫu có j yi y j xi x j i, j tương ứng với mỗi mẫu học. Khi đã được gọi là vectơ hỗ trợ, tất cả các mẫu học thì nằm về hai phía của siêu phẳng khác có Khi đã giải được các và . [4][6] ta có thể tính: N w i yi xi và b i 1 Như vậy, một đối tượng mới x sẽ được phân lớp theo hàm mực tiêu: N f ( x) sgn( wx b) sgn(( N b) i yi xi ) x i 1 sgn( i yi ( xi x) b) i 1 Chú ý rằng trong hàm mực tiêu này, các vector huấn luyện chỉ xuất hiện trên công thức của tích vô hướng. SVM tuyến tính trong trường hợp tập mẫu không phân hoạch tuyến tính được Trường hợp tập mẫu có thể phân chia tuyến tính được chỉ là một trường hợp đặc biệt. Trong trường hợp tổng quát, tập mẫu là một tập không phân chia tuyến tính được bằng siêu phẳng. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 13 Hình 2-3: Không thể phân hoạch tập mẫu trên bằng một siêu phẳng Tuy nhiên ta vẫn muốn dùng siêu phẳng để phân chia tập mẫu này. Để có thể áp dụng được phương pháp trong phần trên, ta phải gán cho mỗi mẫu xi một sai số không âm để “xem như có thể phân chia tuyến tính”. wxi b 1 i với yi 1 wxi b 1 i với yi 1 i 0i 1, 2,..., N Bổ sung vào hàm mục tiêu một giới hạn cân bằng: 1 min wT w C ( w ,b , 2 i )m i Trong đó m thường được chọn là 1, như vậy bài toán tối ưu trở thành: N 1 min wT w C w ,b , 2 i 1 i Sao cho: yi ( wT xi b) i 1 0, 1 i Số hóa bởi Trung tâm Học liệu - ĐHTN N http://www.lrc-tnu.edu.vn/ i