Tài liệu ứng dụng học máy trong nhận dạng công văn các cơ quan đảng tỉnh quảng bình

ii LỜI CẢM ƠN Trước tiên, tôi xin gởi lời cảm ơn chân thành sâu sắc nhất tới Thầy giáo TS. Phạm Minh Tuấn, người Thầy đã tận tình hướng dẫn, động viên và giúp đỡ tôi trong suốt thời gian nghiên cứu và thực hiện luận văn này. Tôi xin gửi lời cảm ơn tới Ban giám hiệu Trường Đại Học Bách Khoa - Đà Nẵng, Ban chủ nhiệm khoa Công nghệ thông tin, Phòng Đào tạo sau đại học của hai trường đã tạo điều kiện thuận lợi trong quá trình học tập, nghiên cứu và hoàn thành luận văn. Tôi xin cảm ơn quí Thầy giáo, Cô giáo những người đã tận tình hướng dẫn và truyền đạt cho tôi những kiến thức quí báu trong những năm nghiên cứu và học tập. Tôi xin gởi lời cảm ơn đến Văn phòng Tỉnh ủy Quảng Bình đã giúp đỡ tạo mọi điều kiện tốt nhất để tôi hoàn thành luận văn. Và để có được kết quả như ngày hôm nay, tôi rất biết ơn Gia đình đã động viên, khích lệ, tạo mọi điều kiện thuận lợi nhất trong suốt quá trình nghiên cứu, học tập cũng như quá trình thực hiện đề tài luận văn tốt nghiệp này. Mặc dù có rất nhiều cố gắng, nhưng chắc chắn luận văn không tránh khỏi những thiếu sót nhất định. Tôi rất mong nhận được ý kiến đóng góp quý báu của các Thầy Cô giáo và các bạn để luận văn ngày càng được hoàn thiện hơn. Một lần nữa tôi xin chân thành cám ơn! Đà Nẵng, tháng 9 năm 2019 Tác giả luận văn Trần Trung Thông iii MỤC LỤC MỞ ĐẦU ............................................................................................................... 1 1. Lý do chọn đề tài ........................................................................................... 1 2. Mục đích nghiên cứu ..................................................................................... 1 3. Ý nghĩa khoa học và thực tiễn của đề tài ...................................................... 1 4. Mục tiêu và nhiệm vụ .................................................................................... 2 5. Bố cục của luận văn ...................................................................................... 2 Chương 1- CƠ SỞ LÝ THUYẾT ......................................................................... 3 1. 1. Học máy .................................................................................................... 3 1.1.1. Tổng quan về học máy......................................................................... 3 1.1.2. Các phương pháp học máy.................................................................. 4 1.1.3. Các ứng dụng của học máy ................................................................. 8 1.2. Các phương pháp nhận dạng ...................................................................... 8 1.2.1. Mô hình Markov ẩn (HMM – Hidden Markov Model) ....................... 8 1.2.2. Máy véc-tơ hỗ trợ (SVM) .................................................................. 10 1.2.3. Phương pháp tiếp cận cấu trúc ......................................................... 12 1.2.4. Đối sánh mẫu .................................................................................... 13 1.2.5. Mạng nơ ron ...................................................................................... 14 1.2.6. Nhận dạng ký tự quang học – OCR .................................................. 16 1.3. Thư viện nhận dạng Tessract ................................................................... 17 1.3.1 . Chức năng của Tesseract ................................................................. 17 1.3.2. Kiến trúc giải thuật nhận dạng chữ in .............................................. 18 1.3.3. Huấn luyện dữ liệu nhận dạng với Tesseract ................................... 20 1.4. Thách thức đối với hệ thống nhận dạng ................................................... 25 1.5. Kết chương ............................................................................................... 25 Chương 2- XÂY DỰNG ỨNG DỤNG NHẬN DẠNG CÔNG VĂN ............... 26 TRONG CÁC CƠ QUAN ĐẢNG TỈNH QUẢNG BÌNH ................................. 26 2.1. Xây dựng hệ thống ................................................................................... 26 2.1.1. Giới thiệu bài toán ............................................................................ 26 2.1.2. Phương pháp đề xuất ........................................................................ 26 2.2. Quy trình xử lý nhận dạng ....................................................................... 26 2.2.1. Tiền xử lý ........................................................................................... 26 2.2.2. Khối tách chữ .................................................................................... 27 2.2.3. Trích chọn đặc trưng ......................................................................... 28 2.2.4. Huấn luyện và nhận dạng ................................................................. 28 2.2.5. Hậu xử lý ........................................................................................... 28 2.3. Bố cục văn bản thực tế tại các cơ quan Đảng tỉnh Quảng Bình .............. 28 2.4. Hệ thống văn bản tại các cơ quan Đảng tỉnh Quảng Bình ....................... 31 2.4.1. Thể loại Nghị quyết ........................................................................... 31 2.4.2. Thể loại Công văn ............................................................................. 31 2.4.3. Thể loại Chương trình ....................................................................... 31 2.4.4. Thể loại Chỉ thị.................................................................................. 32 iv 2.4.5. Thể loại Báo cáo ............................................................................... 32 2.4.6. Thể loại Kết luận ............................................................................... 32 2.4.7. Thể loại Kế hoạch ............................................................................. 32 2.4.8. Thể loại Quyết định ........................................................................... 33 2.4.9. Thể loại Quy định .............................................................................. 33 2.4.10. Thể loại Thông báo ......................................................................... 33 2.4.11. Thể loại Tờ trình ............................................................................. 34 2.4.12. Thể loại Hướng dẫn ........................................................................ 34 Chương 3- TRIỂN KHAI VÀ ĐÁNH GIÁ ........................................................ 35 3.1. Mô tả bài toán ........................................................................................... 35 3.1.1. Nhận văn bản đầu vào....................................................................... 36 3.1.2. Tiền xử lý ........................................................................................... 36 3.1.3. Nhận dạng ......................................................................................... 36 3.2. Môi trường thực nghiệm .......................................................................... 37 3.2.1. Dữ liệu sử dụng ................................................................................. 37 3.2.2. Giao diện chương trình ..................................................................... 37 3.3. Đánh giá về kết quả .................................................................................. 38 3.3.1. Về cài đặt........................................................................................... 38 3.3.2. Về thực nghiệm .................................................................................. 39 KẾT LUẬN ......................................................................................................... 40 1. Đã làm được ................................................................................................ 40 2. Hướng phát triển ......................................................................................... 40 TÀI LIỆU THAM KHẢO ................................................................................... 41 PHỤ LỤC ............................................................................................................ 42 A.1. Chuyển đổi các file ảnh, PDF về một định dạng và crop ảnh theo tỉ lệ .. 42 A.2. Cấu hình Maven được định nghĩa trong file pom.xml ............................ 43 A.3. Modul nhận dạng thể loại văn bản .......................................................... 43 v TÓM TẮT LUẬN VĂN ỨNG DỤNG HỌC MÁY TRONG NHẬN DẠNG CÔNG VĂN CÁC CƠ QUAN ĐẢNG TỈNH QUẢNG BÌNH Học viên: Trần Trung Thông; Chuyên ngành: Khoa học máy tính. Mã số: 8480101; Khóa: 35; Trường Đại học Bách khoa - ĐHĐN Tóm tắt: Ngày nay phương thức sử dụng văn bản giấy truyền thống đã dần được số hóa, chuyển sang dạng các văn bản điện tử lưu trữ trên máy tính và được chia sẻ, truyền tải trên mạng. Cùng với sự phát triển của các giải pháp nhận dạng ký tự quang học OCR đã đặt ra cho người dùng trước lựa chọn tìm ra phương thức lưu trữ, khai thác thông tin văn bản sẳn có một cách hiệu quả. Với mong muốn tìm hiểu về lĩnh vực học máy áp dụng trong nhận dạng, đặc biệt là nhận dạng ký tự quang học OCR, luận văn tập trung nghiên cứu kỹ thuật học máy dựa trên hệ thống nhận dạng ký tự quang học OCR, hiểu được các thuật toán nhận dạng ký tự quang học, nắm được những điểm chính cần quan tâm giải quyết và đề xuất phần mềm ứng dụng để nhận dạng công văn trong các cơ quan Đảng tỉnh Quảng Bình. Từ khóa: Hệ thống nhận dạng, nhận dạng ký tự quang học, nhận dạng công văn, học máy trong nhận dạng, OCR APPLICATION OF MACHINE LEARNING IN RECOGNITION OF OFFICIAL DOCUMENTS PARTY’S AGENCIES OF QUANG BINH PROVINCE Abstract: Today, the method of using traditional paper documents has gradually been digitized. These documents have converted into electronic ones, stored on computers, shared and transmitted in the network. Due to having many preeminent features, the number of electronic documents used in agencies has increased rapidly. Therefore, the problem is how to find and exploit information from this abundant source of data. Along with the development of technology, optical character recognition has created new technical solutions with a breakthrough in building electronic databases. With a desire to learn about machine learning in recognition, especially OCR optical character recognition, the thesis focuses on studying machine learning methods, understanding the methods of recognition, studying about Tessract open source code tools to perform extraction of Vietnamese text from image files and propose application of software to recognise official documents in Party’s agencies of Quang Binh province. Keywords: recognition method, optical character recognition, text filtering, machine learning in recognition, OCR vi DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT AI Artificial Intelligence HAC Hierarchial Agglomerative Clustering HMM Hidden Markov Model ICR Intelligent Character Recognition ML Machine learning OCR Optical Character Recognition PDA thiết bị nhập cho những thiết bị hỗ trợ cá nhân SOM Self-Organizing Map SV Support Vector SVM Support Vector Machines VLSI Very-large-scale-intergrated vii DANH MỤC CÁC HÌNH Số hiệu hình vẽ Tên hình vẽ Trang 1.1 Supervised Learning Algorithms 4 1.2 Ảnh minh hoạ cho tập dữ liệu chữ số viết tay 6 1.3 Unsupervised Learning Algorithms 6 1.4 Semi-Supervised Learning Algorithms 7 1.5 Mô hình Markov ẩn 10 1.6 Biểu đồ chuyển tiếp trạng thái mô hình Markov 10 1.7 Mô hình máy véc-tơ hỗ trợ 12 1.8 Kiến trúc nhận dạng văn bản chữ in trong Tesseract 20 1.9 Đường cơ sở hình cong 21 1.10 Cắt các ký tự liền nhau 21 1.11 Sơ đồ nhận dạng từ 22 1.12 Các đặc trưng ký tự được nhận dạng 22 1.13 Sơ đồ đào tạo dữ liệu của Tesseract 23 1.14 Các chức năng chính của bộ biên tập văn bản mẫu 24 1.15 Nhận dạng phác thảo ký tự 25 1.16 Thuộc tính phông chữ 26 1.17 Kết quả huấn luyện dữ liệu 27 2.1 Quy trình xử lý của một ứng dụng nhận dạng ký tự quang học 29 2.2 Ví dụ về các vùng văn bản tại các cơ quan Đảng tỉnh 32 viii 2.3 Thể loại Nghị quyết 33 2.4 Thể loại Công văn 33 2.5 Thể loại Chương trình 34 2.6 Thể loại Chỉ thị 34 2.7 Thể loại Báo cáo 34 2.8 Thể loại Kết luận 34 2.9 Thể loại Kế hoạch 35 2.10 Thể loại Quyết định 35 2.11 Thể loại Quy định 35 2.12 Thể loại Thông báo 36 2.13 Thể loại Tờ trình 36 2.14 Thể loại Hướng dẫn 36 2.15 Thể loại Quy chế 37 3.1 Mô hình hoạt động 38 3.2 Giao diện chương trình nhận dạng 40 3.3 Giao diện các chức năng chính 40 3.4 Giao diện chức năng kiểm tra kết quả nhận dạng 41 1 MỞ ĐẦU 1. Lý do chọn đề tài Hiện nay, nhu cầu về việc rút trích từ ngữ từ hình ảnh đang ngày càng phát triển, bên cạnh sự gia tăng về nhu cầu là sự phát triển của công nghệ nhận dạng ký tự quang học (Optical Character Recognition) hay còn được gọi tắt là OCR. Đây là một công nghệ giúp chuyển đổi hình ảnh của chữ viết tay hoặc đánh máy thành các ký tự đã được mã hóa trong máy tính. Công nghệ OCR đã tạo ra giải pháp kỹ thuật mới, mang tính đột phá trong việc xây dựng cơ sở dữ liệu điện tử. Cùng với sự phát triển ứng dụng công nghệ thông tin trên các lĩnh vực đời sống xã hội, trong các hoạt động công tác, nhu cầu phân loại các tài liệu có ký hiệu để lưu trữ, khai thác các thông tin trên hệ thống máy tính là một bài toán đang được đặt ra. Trên thực tế, cách duy nhất để sử dụng thông tin ký hiệu và phân loại thì phải gõ lại văn bản trên bàn phím để có thể thêm nó vào hệ thống máy tính hay sử dụng làm đầu vào. Với mong muốn tìm hiểu về ứng dụng học máy trong nhận dạng, lĩnh vực nhận dạng kí tự quang học (Optical character recognition – OCR) và đóng góp thêm vào kho ứng dụng về nhận dạng một hệ thống nhận dạng thiết thực, hữu ích. Vì vậy trong luận văn sẽ tập trung tìm hiểu các kỹ thuật, các công nghệ cần thiết để xây dựng hệ thống Ứng dụng học máy trong nhận dạng công văn các cơ quan Đảng tỉnh Quảng Bình làm đề tài luận văn thạc sỹ của mình. Nội dung luận văn gồm phần mở đầu, 3 chương nội dung, phần kết luận, tài liệu tham khảo. Chương 1: Cơ sở lý thuyết Chương 2: Xây dựng ứng dụng nhận dạng công văn trong các cơ quan Đảng tỉnh Quảng Bình Chương 3: Triển khai hệ thống và đánh giá kết quả 2. Mục đích nghiên cứu - Nghiên cứu lý thuyết nhận dạng, xử lý ảnh. - Hệ thống OCR - Công nghệ mã nguồn mở Tesseract OCR - Tạo ra một ứng dụng nhận dạng ký hiệu văn bản dựa trên mã nguồn mở Tesseract OCR. 3. Ý nghĩa khoa học và thực tiễn của đề tài 3.1. Ý nghĩa khoa học - Nghiên cứu lý thuyết nhận dạng và xử lý ảnh dựa trên mã nguồn mở Tesseract OCR và hệ thống OCR. 2 3.2. Ý nghĩa thực tiễn - Đề xuất giải pháp góp phần tăng hiệu quả việc quản lý văn bản tại các cơ quan Đảng tỉnh Quảng Bình 4. Mục tiêu và nhiệm vụ 4.1. Mục tiêu - Hỗ trợ cán bộ văn thư trong việc sao lưu văn bản, quản lý văn bản phát hành và văn bản đến. - Tự động hóa việc lưu trữ để giúp cán bộ văn thư dễ dàng tìm kiếm văn bản khi cần. 4.2 Nhiệm vụ - Tìm hiểu tổng quan về các phương pháp dạy máy học - Nghiên cứu lý thuyết nhận dạng, xử lý ảnh. - Tạo ra một ứng dụng nhận dạng ký hiệu văn bản rời rạc dựa trên mã nguồn mở Tesseract OCR. - Xây dựng chương trình, cài đặt, kiểm thử và đánh giá. 5. Bố cục của luận văn Cấu trúc của luận văn được trình bày bao gồm các phần chính sau: MỞ ĐẦU: Giới thiệu sơ bộ về lý do chọn đề tài, mục đích nghiên cứu, đối tượng và phạm vi nghiên cứu, phương pháp nghiên cứu, ý nghĩa khoa học và thực tiễn của đề tài. CHƯƠNG 1: CƠ SỞ Ý THUYẾT Giới thiệu tổng quan các phương pháp học máy, các phương pháp nhận dạng văn bản, nhận dạng ký tự quang học OCR. CHƯƠNG 2: XÂY DỰNG ỨNG DỤNG NHẬN DẠNG CÔNG VĂN TẠI CÁC CƠ QUAN ĐẢNG TỈNH QUẢNG BÌNH Trong chương này tác giả nghiên cứu bộ thư viện mã nguồn mở tessract, đề xuất phương pháp xây dựng hệ thống nhận dạng công văn trong các cơ quan Đảng tỉnh Quảng Bình và trình bày các khối chức năng của phương pháp nhận dạng văn bản theo từng loại tại cơ quan. CHƯƠNG 3: TRIỂN KHAI HỆ THỐNG VÀ ĐÁNH GIÁ KẾT QUẢ Trong chương này, tác giả xin được trình bày ứng dụng học máy trong nhận dạng công văn trong các cơ quan Đảng tỉnh Quảng Bình và xây dựng quá trình thực nghiệm và đánh giá kết quả. 3 Chương 1- CƠ SỞ LÝ THUYẾT 1. 1. Học máy 1.1.1. Tổng quan về học máy Học máy là một phần của khoa học máy tính đã dần được cải tiến từ các nghiên cứu về nhận dạng mẫu và trí tuệ nhân tạo. Năm 1959, Arthur Samuel định nghĩa máy học như là một lĩnh vực nghiên cứu cung cấp cho máy tính khả năng học mà không được lập trình một cách rõ ràng. Máy học tìm hiểu nghiên cứu và xây dựng các thuật toán có thể học hỏi và đưa ra dự đoán về dữ liệu. Thuật toán này hoạt động bằng cách xây dựng một mô hình từ ví dụ đầu vào để đưa ra dự đoán dựa trên dữ liệu hoặc quyết định. Học máy là một tập con của AI. Theo định nghĩa của Wikipedia, Machine learning is the subfield of computer science that “gives computers the ability to learn without being explicitly programmed”. Nói đơn giản, Ta có thể hiểu: Học máy là một lĩnh vực của trí thông minh nhân tạo (AI) cung cấp cho máy tính khả năng học hỏi mà không được lập trình một cách rõ ràng. Máy học tập trung vào sự phát triển của các chương trình máy tính để có thể tự mình phát triển và thay đổi khi tiếp xúc với dữ liệu mới. Quá trình học máy cũng tương tự như khai thác dữ liệu. Cả hai hệ thống đều thông qua dữ liệu để tìm kiếm các mẫu. Tuy nhiên, thay vì giải nén dữ liệu để hiểu con người như các ứng dụng khai thác dữ liệu thì học máy sử dụng dữ liệu đó để phát hiện các mẫu trong dữ liệu và điều chỉnh chương trình hành động phù hợp. Học máy được tổ chức lại thành một lĩnh vực riêng biệt và bắt đầu phát triển mạnh những năm 1990. Các lĩnh vực thay đổi mục tiêu của mình từ việc đạt được trí thông minh nhân tạo thành giải quyết các vấn đề có tính chất thực tế. Chuyển trọng tâm từ cách tiếp cận mang tính biểu tượng thừa hưởng từ trí tuệ nhân tạo, và hướng tới các phương pháp, mô hình từ thống kê và lý thuyết xác suất. Máy học, khai thác dữ liệu thường sử dụng cùng phương pháp và lồng ghép lên nhau. Có thể chia thành các giai đoạn như sau: - Máy học tập trung vào dự đoán, dựa trên dữ liệu học được từ dữ liệu huấn luyện. - Khai thác dữ liệu tập trung vào việc phát hiện thuộc tính chưa biết trước trong dữ liệu. Đây là bước phân tích kiến thức, khai phá trong cơ sở dữ liệu. 4 - Máy học và khai thác dữ liệu được lồng ghép lên nhau theo cách: khai thác dữ liệu sử dụng nhiều phương pháp học máy, nhưng mỗi phương pháp thường có mục đích khác nhau. Mặt khác, học máy cũng sử dụng phương pháp khai thác dữ liệu là "học không giám sát" như là một bước tiền xử lý để cải thiện độ chính xác của việc học. Học máy cũng có quan hệ mật thiết với tối ưu hóa: nhiều vấn đề học được xây dựng nhằm giảm thiểu một số chức năng bị mất trên một tập huấn luyện. Chức năng mất thể hiện sự khác biệt giữa các tiên đoán của mô hình được đào tạo và những trường hợp thực tế. Sự khác biệt giữa hai trường phát sinh từ mục tiêu tổng quát. Trong khi các thuật toán tối ưu hóa có thể giảm thiểu sai số trên một tập huấn luyện thì học máy liên quan với việc giảm thiểu sự mất mát trên các mẫu ẩn. 1.1.2. Các phương pháp học máy 1.1.2.1. Học có giám sát Học có giám sát (Supervised Learning) là thuật toán dự đoán đầu ra (outcome) của một dữ liệu mới (new input) dựa trên các cặp (input, outcome) đã biết từ trước. Cặp dữ liệu này còn được gọi là (data, label), tức (dữ liệu, nhãn). Học có giám sát là nhóm phổ biến nhất trong các thuật toán Machine Learning. Hình 1. 1: Supervised Learning Algorithms [2] Một cách toán học, học có giám sát là khi chúng ta có một tập hợp biến đầu vào X={x1,x2,…,xN} và một tập hợp nhãn tương ứng Y={y1,y2,…,yN}, trong đó xi,yi là các vector. Các cặp dữ liệu biết trước (xi,yi)  X×Y được gọi là tập training data (dữ liệu huấn luyện). Từ tập traing data này, chúng ta cần tạo ra một hàm số ánh xạ mỗi phần tử từ tập X sang một phần tử (xấp xỉ) tương ứng của tập Y: yi ≈ f(xi), ∀i=1,2,…,N Mục đích là xấp xỉ hàm số f thật tốt để khi có một dữ liệu x mới, chúng ta có thể tính được nhãn tương ứng của nó y=f(x). Thuật toán Học có giám sát còn được tiếp tục chia nhỏ ra thành hai loại chính: 5 Phân loại (Classification) Một bài toán được gọi là classification nếu các label của input data được chia thành một số hữu hạn nhóm. Ví dụ: Gmail xác định xem một email có phải là spam hay không; các hãng tín dụng xác định xem một khách hàng có khả năng thanh toán nợ hay không. Hồi quy (Regression) Nếu label không được chia thành các nhóm mà là một giá trị thực cụ thể. Ví dụ: một căn nhà rộng xm2, có y phòng ngủ và cách trung tâm thành phố z km sẽ có giá là bao nhiêu? Có rất nhiều thuật toán học không giám sát được ra đời và phát triển nhằm giải quyết bài toán phân cụm phục vụ khai thác hiệu quả nguồn dữ liệu chưa gán nhãn nhiều và rất đa dạng. Việc lựa chọn sử dụng thuật toán nào tuỳ thuộc vào dữ liệu và mục đích của từng bài toán. Trong đó các thuật toán thường được sử dụng như: Kmean, HAC (Hierarchial Agglomerative Clustering), SOM (Self-Organizing Map), DBSCAN… Phân lớp: k-Nearest Neighbors, mạng nơron nhân tạo, SVM, … Hồi quy: Linear Regression, Logistic Regression, … Ví dụ: Trong nhận dạng chữ số viết tay, ta có ảnh của hàng nghìn trường hợp ứng với mỗi chữ số được viết bởi nhiều người khác nhau. Ta đưa các bức ảnh này vào một thuật toán học và chỉ cho nó biết “mỗi bức ảnh tương ứng với chữ số nào”. Sau khi thuật toán tạo ra một mô hình, tức là một hàm số nhận đầu vào là một bức ảnh và cho ra kết quả là một chữ số. Khi nhận được một bức ảnh mới mà mô hình “chưa từng gặp qua” và nó sẽ dự đoán xem bức ảnh đó tương ứng với chữ số nào. Hình 1. 2: Ảnh minh hoạ cho tập dữ liệu chữ số viết tay – MNIST [1] 6 1.1.2.2. Học không giám sát (Unsupervised Learning) Học không giám sát là thuật toán dự đoán nhãn của một dữ liệu mới dựa trên tập dữ liệu huấn luyện mà trong đó tất cả các mẫu dữ liệu đều chưa được gán nhãn hay nói cách khác là ta không biết câu trả lời chính xác cho mỗi dữ liệu đầu. Hình 1. 3: Unsupervised Learning Algorithms [2] Khi đó, mục tiêu của thuật toán học không giám sát không phải là tìm đầu ra chính xác mà sẽ hướng tới việc tìm ra cấu trúc hoặc sự liên hệ trong dữ liệu để thực hiện một công việc nào đó, ví như gom cụm (clustering) hoặc giảm số chiều của dữ liệu (dimension reduction) để thuận tiện trong việc lưu trữ và tính toán. Các bài toán học không giám sát tiếp tục được chia nhỏ thành hai loại là phân cụm (Clustering) và luật kết hợp (Association Rule). *Phân cụm Một bài toán phân cụm / phân nhóm toàn bộ dữ liệu X thành các nhóm/cụm nhỏ dựa trên sự liên quan giữa các dữ liệu trong mỗi nhóm. Chẳng hạn như phân nhóm khách hàng dựa vào độ tuổi, giới tính. *Luật kết hợp Là bài toán mà khi chúng ta muốn khám phá ra một quy luật dựa trên nhiều dữ liệu cho trước. Ví như những khách hàng mua mặt hàng này sẽ mua thêm mặt hàng kia; hoặc khan giả xem phim này sẽ có xu hướng thích xem phim kia, dựa vào đó ta có thể xây dựng những hệ thống gợi ý khách hàng (Recommendation System) nhằm thúc đẩy nhu cầu mua sắm hoặc xem phim…. Một số thuật toán thuộc nhóm học không giám sát như Apriori (Association Rule), k-Means (Clustering), … 1.1.2.3. Học bán giám sát (Semi-Supervised Learning) Là bài toán mà khi tập dữ liệu đầu vào X là hỗn hợp các mẫu có nhãn và không có nhãn, trong đó số lượng có nhãn chỉ chiếm một phần nhỏ. 7 Phần lớn các bài toán thực tế của ML thuộc nhóm này vì việc thu thập dữ liệu có nhãn tốn rất nhiều thời gian và có chi phí cao. Rất nhiều loại dữ liệu thậm chí cần phải có chuyên gia mới gán nhãn được, chẳng hạn như ảnh y học hoặc các cặp câu song ngữ. Ngược lại, dữ liệu chưa có nhãn có thể được thu thập với chi phí thấp từ internet. Hình 1. 4: Semi-Supervised Learning Algorithms [2] Với bài toán này, mô hình phải tìm hiểu các cấu trúc để tổ chức dữ liệu cũng như đưa ra dự đoán. Vì đặc điểm trung gian nên ta có thể sử dụng học không giám sát để khám phá và tìm hiểu cấu trúc trong dữ liệu đầu vào, đồng thời sử dụng học có giám sát để dự đoán cho dữ liệu không được gán nhãn. Sau đó đưa dữ liệu vừa dự đoán trở lại làm dữ liệu huấn luyện cho học có giám sát và sử dụng mô hình sau khi huấn luyện để đưa ra dự đoán về dữ liệu mới. 1.1.2.4. Học tăng cường(Reinforcement learning) Học tăng cường hay học củng cố là bài toán giúp cho một hệ thống tự động xác định hành vi dựa trên hoàn cảnh để đạt được lợi ích cao nhất. Hiện tại, học tăng cường chủ yếu được áp dụng vào lý thuyết trò chơi (Game Theory), các thuật toán cần xác định nước đi tiếp theo để đạt được điểm số cao nhất. AlphaGo - một phần mềm chơi cờ vây trên máy tính được xây dựng bởi Google DeepMind hay chương trình dạy máy tính chơi game Mario là những ứng dụng sử dụng học tăng cường. Cờ vậy được xem là trò chơi có độ phức tạp cực kỳ cao với tổng số nước đi là xấp xỉ 1076110761, so với cờ vua là 1012010120, vì vậy thuật toán phải chọn ra một nước đi tối ưu trong số hàng tỉ tỉ lựa chọn. Về cơ bản, AlphaGo bao gồm các thuật toán thuộc cả Supervised learning và Reinforcement learning. Trong phần Supervised learning, dữ liệu từ các ván cờ do con người chơi với nhau được đưa vào để huấn luyện. Tuy nhiên, mục tiêu cuối cùng của AlphaGo không phải là chơi như con người mà phải thắng được con người. Vì vậy, sau khi học xong các ván cờ của con người, AlphaGo tự chơi với chính nó thông qua hàng triệu ván cờ để tìm ra các nước đi mới 8 tối ưu hơn. Thuật toán trong phần tự chơi này được xếp vào loại Reinforcement learning. Một số thuật toán học tăng cường như: Self Training, Generative models, S3VMs, Graph-Based Algorithms, Multiview Algorithms, … 1.1.3. Các ứng dụng của học máy Học máy có ứng dụng rộng khắp trong các khoa học/sản xuất, đặc biệt là những ngành cần phân tích dữ liệu lớn. Một số ứng dụng thường thấy: Xử lý ngôn ngữ tự nhiên (Natural language Processing): Xử lý văn bản, giao tiếp người...máy,... Nhận dạng (Pattern Recognition): nhận dạng tiếng nói, chữ viết tay, vân tay, thị giác máy (computer Vision)... Tìm kiếm (Search Engine). Chẩn đoán trong y tế: phân tích X quang, các hệ chuyên gia chẩn đoàn tự động. Tin sinh học: phân loại chuổi gene, quá trình hình thành gene/protein. Vật lý: phân tích ảnh thiên văn, tác động giữa các hạt... Phát hiện giai lận tài chính (tinancial fraud): gian lận thể tín dụng. Phân tích thị trường chứng khoán (stock merket analysis). Chơi trò chơi: tự động chơi cờ, hành động của các nhân vật ảo 1.2. Các phương pháp nhận dạng 1.2.1. Mô hình Markov ẩn (HMM – Hidden Markov Model) Mô hình Markov ẩn (tiếng Anh là Hidden Markov Model - HMM) là mô hình thống kê trong đó hệ thống được mô hình hóa được cho là một quá trình Markov với các tham số không biết trước và nhiệm vụ là xác định các tham số ẩn từ các tham số quan sát được, dựa trên sự thừa nhận này. Các tham số của mô hình được rút ra sau đó có thể sử dụng để thực hiện các phân tích kế tiếp, ví dụ cho các ứng dụng nhận dạng mẫu. Trong một mô hình Markov điển hình, trạng thái được quan sát trực tiếp bởi người quan sát, và vì vậy các xác suất chuyển tiếp trạng thái là các tham số duy nhất. Mô hình Markov ẩn thêm vào các đầu ra: mỗi trạng thái có xác suất phân bổ trên các biểu hiện đầu ra có thể. Vì vậy, nhìn vào dãy của các biểu hiện được sinh ra bởi HMM không trực tiếp chỉ ra dãy các trạng thái. 9 Đây là một mô hình toán thống kê có ứng dụng rộng rãi trong Tin sinh học. Hình 1. 5: Mô hình Markov ẩn [3] Các chuyển tiếp trạng thái trong mô hình Markov ẩn - x — Các trạng thái trong mô hình Markov - a — Các xác suất chuyển tiếp - b — Các xác suất đầu ra - y — Các dữ liệu quan sát Sự tiến hóa của mô hình Markov Biểu đồ trên đây làm nổi bật các chuyển tiếp trạng thái của mô hình Markov ẩn. Nó cũng có ích để biểu diễn rõ ràng sự tiến hóa của mô hình theo thời gian, với các trạng thái tại các thời điểm khác nhau t1 và t2 được biểu diễn bằng các tham biến khác nhau, x(t1) và x(t2). Hình 1. 6: Biểu đồ chuyển tiếp trạng thái mô hình Markov [3] Trong biểu đồ này, nó được hiểu rằng thời gian chia cắt ra (x(t), y(t)) mở rộng tới các thời gian trước và sau đó như một sự cần thiết. Thông thường lát cắt sớm nhất là thời gian t=0 hay t=1. Sử dụng các mô hình Markov Có ba vấn đề cơ bản để giải quyết bằng HMM: Cung cấp cho mô hình các tham số, tính xác suất của dãy đầu ra cụ thể. Giải bằng thuật toán tiến trước (thuật toán tham lam). 10 Cung cấp cho mô hình các tham số, tìm dãy các trạng thái (ẩn) có khả năng lớn nhất mà có thể sinh ra dãy đầu ra đã cung cấp. Giải bằng thuật toán Viterbi. Cung cấp dãy đầu ra, tìm tập hợp có khả năng nhất của chuyển tiếp trạng thái và các xác suất đầu ra. Giải bằng thuật toán Baum-Welch. Các ứng dụng Sự nhận biết lời nói hay sự nhận biết ký tự quang học. Quy trình ngôn ngữ tự nhiên. Tin sinh học và hệ gen học: Dự đoán các vùng mang mã (khung đọc mở) trên một trình từ gene. Xác định các họ gene hoặc họ protein liên quan. Mô phỏng cấu trúc không gian của protein từ trình tự amino acid. và còn nhiều nữa... 1.2.2. Máy véc-tơ hỗ trợ (SVM) Máy vectơ hỗ trợ (SVM – viết tắt tên tiếng Anh support vector machine) là một khái niệm trong thống kê và khoa học máy tính cho một tập hợp các phương pháp học có giám sát liên quan đến nhau để phân loại và phân tích hồi quy. SVM dạng chuẩn nhận dữ liệu vào và phân loại chúng vào hai lớp khác nhau. Do đó SVM là một thuật toán phân loại nhị phân. Với một bộ các ví dụ luyện tập thuộc hai thể loại cho trước, thuật toán luyện tập SVM xây dựng một mô hình SVM để phân loại các ví dụ khác vào hai thể loại đó. Một mô hình SVM là một cách biểu diễn các điểm trong không gian và lựa chọn ranh giới giữa hai thể loại sao cho khoảng cách từ các ví dụ luyện tập tới ranh giới là xa nhất có thể. Các ví dụ mới cũng được biểu diễn trong cùng một không gian và được thuật toán dự đoán thuộc một trong hai thể loại tùy vào ví dụ đó nằm ở phía nào của ranh giới. 11 Hình 1. 7: Mô hình máy véc-tơ hỗ trợ [4] Một máy vectơ hỗ trợ xây dựng một siêu phẳng hoặc một tập hợp các siêu phẳng trong một không gian nhiều chiều hoặc vô hạn chiều, có thể được sử dụng cho phân loại, hồi quy, hoặc các nhiệm vụ khác. Một cách trực giác, để phân loại tốt nhất thì các siêu phẳng nằm ở càng xa các điểm dữ liệu của tất cả các lớp (gọi là hàm lề) càng tốt, vì nói chung lề càng lớn thì sai số tổng quát hóa của thuật toán phân loại càng bé. Trong nhiều trường hợp, không thể phân chia các lớp dữ liệu một cách tuyến tính trong một không gian ban đầu được dùng để mô tả một vấn đề. Vì vậy, nhiều khi cần phải ánh xạ các điểm dữ liệu trong không gian ban đầu vào một không gian mới nhiều chiều hơn, để việc phân tách chúng trở nên dễ dàng hơn trong không gian mới. Để việc tính toán được hiệu quả, ánh xạ sử dụng trong thuật toán SVM chỉ đòi hỏi tích vô hướng của các vectơ dữ liệu trong không gian mới có thể được tính dễ dàng từ các tọa độ trong không gian cũ. Tích vô hướng này được xác định bằng một hàm hạt nhân K(x,y) phù hợp. Một siêu phẳng trong không gian mới được định nghĩa là tập hợp các điểm có tích vô hướng với một vectơ cố định trong không gian đó là một hằng số. Vectơ xác định một siêu phẳng sử dụng trong SVM là một tổ hợp tuyến tính của các vectơ dữ liệu luyện tập trong không gian mới với các hệ số αi. Với siêu phẳng lựa chọn như trên, các điểm x trong không gian đặc trưng được ánh xạ vào một siêu mặt phẳng là các điểm thỏa mãn:  a K ( X , X )  hằng số i i i Ghi chú rằng nếu K(x,y) nhận giá trị ngày càng nhỏ khi y xa dần khỏi x thì mỗi số hạng của tổng trên được dùng để đo độ tương tự giữa x với điểm x i tương ứng trong dữ liệu luyện tập. Như vậy, tác dụng của tổng trên chính là so sánh khoảng cách giữa điểm cần dự đoán với các điểm dữ liệu đã biết. Lưu ý là tập hợp các điểm x được ánh xạ vào một siêu phẳng có thể có độ phức tạp tùy ý trong không gian ban đầu, nên có thể phân tách các tập hợp thậm chí không lồi trong không gian ban đầu. Ưu điểm của SVM - Cho kết quả nhận dạng với độ chính xác cao - Bài toán huấn luyện SVM thực chất là bài toán quy hoạch toàn phương trên một tập lồi, do đó SVM luôn có nghiệm toàn cục và duy nhất, đây chính là điểm khác biệt rõ nhất giữa SVM so với phương pháp mạng Neural, vì mạng Neural vốn tồn tại nhiều điểm cực trị địa phương. 12 Nhược điểm của SVM - Hạn chế lớn nhất của SVM là tốc độ phân lớp rất chậm, tùy thuộc vào số lượng các véc tơ hỗ trợ. - Giai đoạn huấn luyện SVM đòi hỏi bộ nhớ rất lớn, do đó các bài toán huấn luyện với số lượng mẫu lớn sẽ gặp trở ngại trong vấn đề lưu trữ. Hiệu quả phân lớp của SVM phụ thuộc vào hai yếu tố: giải bài toán quy hoạch toàn phương và lựa chọn hàm nhân. 1.2.3. Phương pháp tiếp cận cấu trúc Cách tiếp cận của phương pháp này dựa vào việc mô tả đối tượng nhờ một số khái niệm biểu diễn đối tượng cơ sở trong ngôn ngữ tự nhiên. Để mô tả đối tượng người ta dùng một số dạng nguyên thủy như đoạn thẳng, cung,… Mỗi đối tượng được mô tả như một sự kết hợp của các dạng nguyên thủy. Các quy tắc kết hợp các dạng nguyên thủy được xây dựng giống như việc nghiên cứu văn phạm trong một ngôn ngữ, do đó quá trình quyết định nhận dạng là quá trình phân tích cú pháp. Phương pháp này đặt vấn đề để giải quyết bài toán nhận dạng chữ tổng quát. Tuy vậy, cho đến nay còn nhiều vấn đề liên quan đến hệ nhận dạng cú pháp chưa được giải quyết độc lập và xây dụng được các thuật toán phổ dụng. Hiện nay, nhận dạng theo cấu trúc phổ biến là trích trọn các đặc trung của mẫu học, phân hoạch bảng ký tự dựa trên các đặc trưng này, sau đó ảnh cần nhận dạng sẽ được trích chọn đặc trưng, sau đó so sánh bảng phân hoạch để tìm ra ký tự có các đặc trưng phù hợp. Các phương pháp cấu trúc áp dụng cho các bài toán nhận dạng chữ được phát triển theo hai hướng sau: 1.2.3.1. Phương pháp đồ thị (Graphical Methods) Các đơn vị chữ viết được mô tả bởi các cây hoặc các đồ thị. Các dạng nguyên thủy của ký tự (các nét) được lựa chọn bởi một hướng tiếp cận cấu trúc. Đối với mỗi lớp, một đồ thị hoặc cây được thành lập trong giai đoạn huấn luyện để mô tả các nét, các ký tự hoặc các từ. Giai đoạn nhận dạng gán một đồ thị chưa biết vào một trong các lớp bằng cách sử dụng một độ đo để so sánh các đặc điểm giống nhau giữa các đồ thị. 1.2.3.2. Phương pháp ngữ pháp (Grammatical Methods) Giữa thập niên 1960, các nhà nghiên cứu bắt đầu xét các luật của ngôn ngữ học để phân tích tiếng nói và chữ viết. Sau đó, các luật đa dạng của chính tả, từ vựng và ngôn ngữ học đã được áp dụng cho các chiến lược nhận dạng. Phương pháp ngữ pháp 13 khởi tạo một số luật sinh để hình thành các ký tự từ một tập các công thức ngữ pháp nguyên thủy. Các luật sinh này có thể kết nối bất kỳ kiểu đặc trưng thống kê và đặc trưng hình thái nào dưới một số cú pháp hoặc các luật ngữ nghĩa. Giống như lý thuyết ngôn ngữ, các luật sinh cho phép mô tả các cấu trúc câu có thể chấp nhận được các trích chọn thông tin theo ngữ cảnh về chữ viết bằng cách sử dụng các kiêu ngữ pháp khác nhau. Trong phương pháp này, việc huấn luyện được thực hiện bằng cách mô tả mỗi ký tự bằng một văn phạm Gi. Còn trong pha nhận dạng thì chuỗi, cây hoặc đồ thị của một đơn vị viết bất kỳ (ký tự, từ hoặc câu) được phân tích để quyết định văn phạm của mẫu đó thuộc lớp nào. Các phương pháp ngữ pháo hầu hết được sử dụng trong giai đoạn hậu xử lý để sửa các lỗi mà khối nhận dạng đã thực hiện sai. 1.2.4. Đối sánh mẫu Kỹ thuật nhận dạng chữ đơn giản nhất dựa trên cơ sở đối sánh các nguyên mẫu (prototype) với nhau để nhận dạng ký tự hoặc từ. Nói chung, toán tử đối sánh xác định mức độ giống nhau giữa hai véc tơ (nhóm các điểm, hình dạng, độ cong...) trong một không gian đặc trưng. Các kỹ thuật đối sánh có thể nghiên cứu theo ba hướng sau: Đối sánh trực tiếp: Một ký tự đầu vào là ảnh đa cấp xám hoặc ảnh nhị phân được so sánh trực tiếp với một tập mẫu chuẩn đã được lưu trữ. Việc so sánh dựa theo một độ đo về sự tương đồng nào đó (chẳng hạn như độ đo Euclide) để nhận dạng. Các kỹ thuật đối sánh này có thể đơn giản như việc so sánh một – một hoặc phức tạp hơn như cây quyết định. Mặc dù phương pháp đối sánh trực tiếp đơn giản và có một cơ sở toán học vững chắc nhưng kết quả nhận dạng của nó cũng rất nhạy cảm với nhiễu. Các mẫu biến dạng và đối sánh mềm: Một phương pháp đối sánh khác là sử dụng các mẫu biến dạng, trong đó một phép biến dạng ảnh được dùng để đối sánh một ảnh chưa biết với một cơ sở dữ liệu ảnh đã biết. Ý tưởng cơ bản của đối sánh mềm là đối sánh một cách tối ưu mẫu chưa biết với tất cả các mẫu có thể mà các mẫu này có thế kéo giãn ra hoặc co lại. Chỉ một không gian đặc trung được thành lập, các véc tơ chưa biết được đối sánh bằng cách sử dụng quy hoạch động và một hàm biến dạng. Đối sánh giảm nhẹ: Đây là một kỹ thuật đối sánh ảnh ở mức độ tượng trưng, kỹ thuật này sử dụng hình dáng đặc trưng cơ bản của ảnh ký tự. Thứ nhất, các vùng đối sánh đã được nhận biết. Sau đó, trên cơ sở với các vùng đối sánh này. Công việc này