Báo cáo Semi – Supervised Learning

Nội dung text: Báo cáo Semi – Supervised Learning

1. TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO NGHIÊN CỨU KHOA HỌC Đề tài SEMI – SUPERVISED LEARNING Giáo viên hướng dẫn : Ths. Phạm Thọ Hoàn Sinh viên thực hiện : Nguyễn Ngọc Tùng Lớp : K54B Khoa : Công Nghệ Thông Tin HÀ NỘI 04/2008
2. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT MỤC LỤC NHẬN XÉT CỦA HỘI ĐỒNG 3 Chƣơng I: GIỚI THIỆU VỀ MÁY HỌC 4 ( Machine learning ) 4 I GIỚI THIỆU: 4 1.1 Định nghĩa „học‟ 5 1.2. Khái niệm về học máy 6 1.3 Các tiếp cận học 7 1.4 Tƣơng tác với con ngƣời 7 II. QUÁ TRÌNH HỌC MÁY 8 2.1 Quá trình trích tri thức từ dữ liệu 8 2.2 Phân loại học 8 2.3 Dữ liệu 8 2.4 Giao thức 8 2.5 Tiêu chuẩn thành công 8 2.6 Không gian biểu diễn 9 2.7 Bản chất của các thuộc tính 10 2.8 Tiền xử lý dữ liệu 10 2.10 Tập mẫu 11 2.11 Tìm kiếm trong không gian giải thuyết 11 III. CÁC LOẠI GIẢI THUẬT TRONG MÁY 11 3.1 Các loại giải thuật. 11 3.2 Các chủ đề về học máy 12 Chƣơng II: HỌC NỬA GIÁM SÁT 14 (Semi-supervised learning ) 14 I. TỔNG QUAN 14 1.1 Giới thiệu về học có giám sát (supervised learning) và không có giám sát (unsupervised learning) 14 a. Học có giám sát: 14 b. Học không có giám sát: 17 1.2 Khái niệm về học nửa giám sát 18 II. MỘT SỐ GIẢI THUẬT TRONG HỌC NỬA GIẤM SÁT 19 2.1 Generative Models 19 2.1.1 Giới thiệu về “Generative Models” 19 2.1. Generative Models trong Semi - supervised learning 19 2.1.3 Ưu điểm và nhược điểm của giải thuật 22 2.1.5 Ứng dụng của mô hình 22 2.2 Semi – superviesd Suport vector machines 23 2.2.1 Giới thiệu về S3VM 23 2.2.2 Giải thuật S3MV 24 2.2.3 Kết luận về S3VM 25 2.3 Self-training 26 CHƢƠNG III. SELF – TRAINING VÀ BÀI TOÁN NHẬN DẠNG KÝ TỤ TRÊN ẢNH 27 I. GIẢI THUẬT SELF – TRAINING 27 1
3. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT 1.1 Giới thiệu về Self – training 27 1.2 Giải thuật 27 1.3 Đánh giá giải thuật 28 II. BÀI TOÁN NHẬN DẠNG KÝ TỰ TRÊN ẢNH 28 2.1 Phân tích bài toán 28 2.2 Hướng giải quyết bài toán. 28 I. KẾT QUẢ BAN ĐẦU ĐÃ ĐẠT ĐƢỢC 30 II. HƢỚNG PHÁT TRIỂN 30 2
4. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT NHẬN XÉT CỦA HỘI ĐỒNG 3
5. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT Chƣơng I: GIỚI THIỆU VỀ MÁY HỌC ( Machine learning ) I GIỚI THIỆU: Khi đƣợc hỏi về những kỹ năng thông minh nào là cơ bản nhất đồng thời khó tự động hóa nhất của con ngƣời ngoài các hoạt động sáng tạo nghệ thuật, hành động ra quyết định mang Trãi qua nhiều năm, hai lĩnh vực này vẫn là mục tiêu, thách thức của khoa học TTNT. Tầm quan trọng của việc học thì không cần phải tranh cãi, vì khả năng học chính là một trong những thành tố quan trọng của hành vi thông minh. Mặc dù tiếp cận hệ chuyên gia đã phát triển đƣợc nhiều năm, song số lƣợng các hệ chuyên vẫn còn hạn chế. Một trong những nguyên nhân chủ yếu là do quá trình tích lũy tri thức phức tạp, chi phí phát triển các hệ chuyên gia rất cao, nhƣng chúng không có khả năng học, khả năng tự thích nghi khi môi trƣờng thay đổi. Các chiến lƣợc giải quyết vấn đề của chúng cứng nhắc và khi có nhu cầu thay đổi, thì việc sửa đổi một lƣợng lớn mã chƣơng trình là rất khó khăn. Một giải pháp hiển nhiên là các chƣơng trình tự học lấy cách giải quyết vấn đề từ kinh nghiệm, từ sự giống nhau, từ các ví dụ hay từ những „chỉ dẫn‟, „lời khuyên‟, Mặc dù học vẫn còn là một vấn đề khó, nhƣng sự thành công của một số chƣơng trình học máy thuyết phục rằng có thể tồn tại một tập hợp các nguyên tắc học tổng quát cho phép xây dựng nên các chƣơng trình có khả năng học trong nhiều lĩnh vực thực tế. 4
6. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT 1.1 Định nghĩa ‘học’ Theo Herbert Simon: „Học đƣợc định nghĩa nhƣ là bất cứ sự thay đổi nào trong một hệ thống cho phép nó tiến hành tốt hơn trong lần thứ hai khi lặp lại cùng một nhiệm vụ hoặc với một nhiệm vụ khác rút ra từ cùng một quần thể các nhiệm vụ đó‟ Định nghĩa này mặc dù ngắn nhƣng đƣa ra nhiều vấn đề liên quan đến việc phát triển một chƣơng trình có khả năng học. Học liên quan đến việc khái quát hóa từ kinh nghiệm: hiệu quả thực hiện của chƣơng trình không chỉ cải thiện với „việc lặp lại cùng một nhiệm vụ‟ mà còn với các nhiệm vụ tƣơng tự. Vì những lĩnh vực đáng chú ý thƣờng có khuynh hƣớng là to lớn, nên các chương trình học – (learner) chỉ có thể khảo sát một phần nhỏ trong toàn bộ các ví dụ có thể; từ kinh nghiệm hạn chế này, chƣơng trình học vẫn phải khái quát hóa đƣợc một cách đúng đắn những ví dụ chƣa từng gặp trong lĩnh vực đó. Đây chính là bài toán quy nạp (induction), và nó chính là trung tâm của việc học. Trong hầu hết các bài toán học, dữ liệu luyện tập sẵn có thƣờng không đủ để đảm bảo đƣa ra đƣợc một khái quát hóa tối ƣu, cho dù chƣơng trình học sử dụng giải thuật nào. Vì vậy, các giải thuật học phải khái quát hóa theo phƣơng pháp heuristic, nghĩa là chúng sẽ chọn một số khía cạnh nào đó mà theo kinh nghiệm là cho hiệu quả trong tƣơng lai để khái quát. Các tiêu chuẩn lựa chọn này gọi là thiên lệch quy nạp (inductive bias). Có nhiều nhiệm vụ học (learning task) khác nhau. Nhiệm vụ của chƣơng trình học là học một khái quát (generalization) từ một tập hợp các ví dụ. Học khái niệm (concept learning) là một bài toán học quy nạp tiêu biểu: cho trƣớc một số ví dụ của khái niệm, chúng ta phải suy ra một định nghĩa cho 5
7. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT phép ngƣời dùng nhận biết một cách đúng đắn những thể hiện của khái niệm đó trong tƣơng lai. Một số khái niệm:  Học thuộc lòng  Học tăng cƣờng  Học khái niệm  Giải quyết vấn đề  Khái quát hoávà đặc biệt hoá  Bias: . Cố định một họ khái niệm . Tìm kiếm trong họkhái niệm giải thích tốt nhất dữliệu . Lựa chọn BIAS là một sự thoả hiệp 1.2. Khái niệm về học máy Học máy (còn gọi là Máy học) là một lĩnh vực của trí tuệ nhân tạo liên quan đến việc phát triển các kĩ thuật cho phép các máy tính có thể "học". Cụ thể hơn, học máy là một phƣơng pháp để tạo ra các chƣơng trình máy tính bằng việc phân tích các tập dữ liệu. Học máy có liên quan lớn đến thống kê, vì cả hai lĩnh vực đều nghiên cứu việc phân tích dữ liệu, nhƣng khác với thống kê, học máy tập trung vào sự phức tạp của các giải thuật trong việc thực thi tính toán. Nhiều bài toán suy luận đƣợc xếp vào loại bài toán NP-khó, vì thế một phần của học máy là nghiên cứu sự phát triển các giải thuật suy luận xấp xỉ mà có thể xử lí đƣợc. Học máy có tính ứng dụng rất cao bao gồm máy truy tìm dữ liệu, chẩn đoán y khoa, phát hiện thẻ tín dụng giả, phân tích thị trƣờng chứng khoán, phân 6
8. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT loại các chuỗi DNA, nhận dạng tiếng nói và chữ viết, chơi trò chơi và cử động rô-bốt (robot locomotion). 1.3 Các tiếp cận học Có ba tiếp cận học: tiếp cận ký hiệu (symbol-based learning), tiếp cận mạng neuron hay kết nối (neural or connectionist networks) và tiếp cận nổi trội (emergent) hay di truyền và tiến hóa (genetic and evolutionary learning). Các chƣơng trình học thuộc tiếp cận dựa trên ký hiệu biểu diễn vấn đề dƣới dạng các ký hiệu (symbol), các giải thuật học sẽ tìm cách suy ra các khái quát mới, hợp lệ, hữu dụng và đƣợc biểu diễn bằng các ký hiệu này. Ngƣợc lại với tiếp cận ký hiệu, tiếp cận kết nối không học bằng cách tích lũy các câu trong một ngôn ngữ ký hiệu. Giống nhƣ bộ não động vật chứa một số lƣợng lớn các tế bào thần kinh liên hệ với nhau, mạng neuron là những hệ thống gồm các neuron nhân tạo liên hệ với nhau. Tri thức của chƣơng trình là ngầm định trong tổ chức và tƣơng tác của các neuron này. Tiếp cận thứ ba là tiếp cận nổi trội mô phỏng cách thức các hệ sinh học tiến hóa trong tự nhiên, nên còn đƣợc gọi là tiếp cận di truyền và tiến hóa. 1.4 Tƣơng tác với con ngƣời Một số hệ thống học máy nỗ lực loại bỏ nhu cầu trực giác của con ngƣời trong việc phân tích dữ liệu, trong khi các hệ thống khác hƣớng đến việc tăng sự cộng tác giữa ngƣời và máy. Không thể loại bỏ hoàn toàn tác động của con ngƣời vì các nhà thiết kế hệ thống phải chỉ định cách biểu diễn của dữ liệu và những cơ chế nào sẽ đƣợc dùng để tìm kiếm các đặc tính của dữ liệu. Học máy có thể đƣợc xem là một nỗ lực để tự động hóa một số phần của phƣơng pháp khoa học. Một số nhà nghiên cứu học máy tạo ra các 7
9. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT phƣơng pháp bên trong các framework của thống kê Bayes (Bayesian statistics). II. QUÁ TRÌNH HỌC MÁY 2.1 Quá trình trích tri thức từ dữ liệu  Làm sạch dữ liệu  Sử dụng một phƣơng pháp học để đề nghị mô hình  Hợp thức hoá mô hình đƣợc đề nghị 2.2 Phân loại học  Cơ chế cơ sở: Quy nạp = phƣơng pháp cho phép rút ra các kết luận từ một dãy các sự kiện.  Học giám sát classification, regression, logistic regression Dãy "sự kiện" đƣợc "gán nhãn"  Học không giám sát ( không thầy) : clustering. Dãy sự kiện không đƣợc "gán nhãn". 2.3 Dữ liệu  Bản chất: số, ký hiệu, pha trộn  Chất lƣợng: nhiễu, gốc 2.4 Giao thức  Giám sát / không giám sát  Giới thiệu các ví dụ cho học: . Từng vi dụ một ( theo một cách rút) - incremental . Tất cả các ví dụ đồng thời 2.5 Tiêu chuẩn thành công  Cách ứng xử: 8
10. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT . Đo lƣờng tỷ suất lỗi của sự phân lớp . Sự hội tụ  Sự diễn giải: . Giải thích . Tính dễ hiểu 2.6 Không gian biểu diễn  Không gian biểu diễn, ký hiệu X, các phần tử của nó đƣợc gọi là các dữ liệu / các thể hiện / cácđối tƣợng / các ví dụ.  Mỗi phần tử x thuoc X đƣợc biểu diễn bởi một tập k thuộc tính ( bộ mô tả / biến ) x = ( x1, x2, ,xk)  Một đối tƣợng x cũng có thể đƣợc kết hợp với lớp liên thuộc của nó (nhãn) : z = ( x, c ) 9
11. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT 2.7 Bản chất của các thuộc tính  Số ( giá trị trong R )  Rời rạc / chất / tên / tử số ( giá trị trong N )  Nhị phận ( giá trị trong { 0, 1 } )  Dãy các phần tử trong một alphabet Σ  Không gian biểu diễn: . Thuần nhất ( thuộc tính cùng kiểu) . Trộn ( mixte) 2.8 Tiền xử lý dữ liệu  Chọn thuộc tính mô tả dữ liệu . Chọnthuộctính( feature selection ): Loại bỏ các thuộc tính ít phù hợp đối với việc học. Đích là làm giảm số chiều. . Trích / xây dựng thuộc tính ( feature construction ): giảm số chiều không gian đầu vào bằng các phép biến đổi ( tuyến tính hoặc không) các thuộc tính khởi đầu. Đích là giảm số chiều của vấn đề và xây dựng biến tổng hợp ( kể đén các tƣơng tác).  Xử lý nhiễu: Lỗi thuộc tính mô tả hoặc nhãn–phát hiện bất thƣờng bàng visualization, sử dụng chuyên gia. Thay thế các dữ liệu thiếu. 2.9 Rời rạc hoá dữ liệu liên tục - Một số thuật toán học không có khả năng xử lý trực tiếp các thuộc tính liên tục. Cần thiết biến đổi các thuộc tính liên tục thành thuộc tính giá trị rời rạc - Một số phƣơng pháp giả thiết dữ liệu tuân theo một luật phân phối ( Gauss , đều ) → Rời rạc thành các khoảng phân phối tƣơng ứng với các phân phối đó. - Một số phƣơng pháp rời rạc hoá khác: phân đoạn, đo lƣờng entropy, 10
12. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT 2.10 Tập mẫu Tập mẫu = tập hữu hạn các ví dụ. 3 kiểu tập mẫu: Tập mẫu học / tập học •Tập mẫu hợp thức hoá / tập hợp thức -Tập mẫu thử / tập thử 2.11 Tìm kiếm trong không gian giải thuyết -Mỗi khi không gian giả thiết H đã đƣợc lựa chọn, học trở thành tìm kiếm giả thiết tốt nhất trong H. -Nếu có một sự đánh giá mỗi giả thiết bởi một hàm "giá", có thể xét học nhƣ một vấn đề tối ƣu hoá: Tìm phần tử của H làm tối ư u hàm "giá". • Tối ƣu không ràng buộc & Tối ƣu với ràng buộc Hàm tối ƣu rất thƣờng dùng là hàm "lỗi" - Các phƣơng pháp tối ƣu hoá: Gradient, Nhân tử Lagrange, Annealing III. CÁC LOẠI GIẢI THUẬT TRONG MÁY 3.1 Các loại giải thuật. Các thuật toán học máy đƣợc phân loại theo kết quả mong muốn của thuật toán. Các loại thuật toán thƣờng dùng bao gồm: Học có giám sát (supervised learning) trong đó, thuật toán tạo ra một hàm ánh xạ dữ liệu vào tới kết quả mong muốn. Một phát biểu chuẩn về một việc học có giám sát là bài toán phân loại: chƣơng trình cần học (cách xấp xỉ biểu hiện của) một hàm ánh xạ một vector tới một vài lớp (class) bằng cách xem xét một số ví dụ mẫu dữ_liệu- kết_quả của hàm đó. Học không giám sát (unsupervised learning) mô hình hóa một tập dữ liệu, không có sẵn các ví dụ đã đƣợc gắn nhãn. 11
13. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT Học nửa giám sát (semi-supervised learning) kết hợp các ví dụ có gắn nhãn và không gắn nhãn để sinh một hàm hoặc một bộ phân loại thích hợp. Học tăng cƣờng (reinforcement learning) trong đó, thuật toán học một chính sách hành động tùy theo các quan sát về thế giới. Mỗi hành động đều có tác động tới môi trƣờng, và môi trƣờng cung cấp thông tin phản hồi, các thông tin này hƣớng dẫn thuật toán học. transduction tƣơng tự học có giám sát nhƣng không xây dựng hàm. Thay vào đó, cố gắng đoán kết quả mới dựa vào dữ liệu huấn luyện, kết quả huấn luyện, và dữ liệu mới. Học cách học (learning to learn) trong đó thuật toán học thiên kiến quy nạp (inductive bias) của chính mình, dựa theo các kinh nghiệm đã gặp. Phân tích hiệu quả các thuật toán học máy là một nhánh của ngành thống kê, đƣợc biết với tên lý thuyết học tính toán (computational learning theory). 3.2 Các chủ đề về học máy Mô hình hóa các hàm mật độ xác suất điều kiện (conditional probability density functions): hồi quy và phân loại o Mạng nơ-ron o Cây quyết định o Gene expression programming o Lập trình di truyền o Gaussian process regression o Linear discriminant analysis o k láng giềng gần nhất 12
14. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT o Minimum message length o Perceptron o Radial basis function o Support vector machine Mô hình hóa các hàm mật độ xác suất qua các generative model: o Thuật toán cực đại kì vọng (expectation-maximization algorithm) o Các mô hình đồ họa gồm mạng Bayes và mạng Markov (Markov random field) o Generative Topographic Mapping Các kỹ thuật suy diễn xấp xỉ đúng (appromixate inference techniques): o Chuỗi Markov phƣơng pháp Monte Carlo o Variational method Tối ƣu hóa: hầu hết các phƣơng pháp trên đều sử dụng tối ƣu hóa hoặc là các thể hiện của các thuật toán tối ƣu hóa. 13
15. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT Chƣơng II: HỌC NỬA GIÁM SÁT (Semi-supervised learning ) I. TỔNG QUAN 1.1 Giới thiệu về học có giám sát (supervised learning) và không có giám sát (unsupervised learning) a. Học có giám sát: Học có giám sát là một kĩ thuật của ngành học máy để xây dựng một hàm (function) từ dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các cặp gồm đối tƣợng đầu vào (thƣờng dạng vec-tơ), và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị liên tục (gọi là hồi qui), hay có thể là dự đoán một nhãn phân loại cho một đối tƣợng đầu vào (gọi là phân loại). Nhiệm vụ của chƣơng trình học có giám sát là dự đoán giá trị của hàm cho một đối tƣợng bất kì là đầu vào hợp lệ, sau khi đã xem xét một số ví dụ huấn luyện (nghĩa là, các cặp đầu vào và đầu ra tƣơng ứng). Để đạt đƣợc điều này, chƣơng trình học phải tổng quát hóa từ các dữ liệu sẵn có để dự đoán đƣợc những tình huống chƣa gặp phải theo một cách "hợp lí". Học có giám sát có thể tạo ra 2 loại mô hình. Phổ biến nhất, học có giám sát tạo ra một mô hình toàn cục (global model) để ánh xạ đối tƣợng đầu vào đến đầu ra mong muốn. Tuy nhiên, trong một số trƣờng hợp, việc ánh xạ đƣợc thực hiện dƣới dạng một tập các mô hình cục bộ (nhƣ trong phƣơng pháp lập luận theo tình huống (case-based reasoning) hay giải thuật láng giềng gần nhất). 14
16. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT Để có thể giải quyết một bài toán nào đó của học có giám sát ngƣời ta phải xem xét nhiều bƣớc khác nhau: 1. Xác định loại của các ví dụ huấn luyện. Trƣớc khi làm bất cứ điều gì, ngƣời kĩ sƣ nên quyết định loại dữ liệu nào sẽ đƣợc sử dụng làm ví dụ. Chẳng hạn, đó có thể là một kí tự viết tay đơn lẻ, toàn bộ một từ viết tay, hay toàn bộ một dòng chữ viết tay. 2. Thu thập tập huấn luyện. Tập huấn luyện cần đặc trƣng cho thực tế sử dụng của hàm chức năng. Vì thế, một tập các đối tƣợng đầu vào đƣợc thu thập và đầu ra tƣơng ứng đƣợc thu thập, hoặc từ các chuyên gia hoặc từ việc đo đạc tính toán. 3. Xác định việc biễu diễn các đặc trƣng đầu vào cho hàm chức năng cần tìm. Sự chính xác của hàm chức năng phụ thuộc lớn vào cách các đối tƣợng đầu vào đƣợc biểu diễn. Thông thƣờng, đối tƣợng đầu vào đƣợc chuyển đổi thành một vec-tơ đặc trƣng, chứa một số các đặc trƣng nhằm mô tả cho đối tƣợng đó. Số lƣợng các đặc trƣng không nên quá lớn, do sự bùng nổ tổ hợp (curse of dimensionality); nhƣng phải đủ lớn để dự đoán chính xác đầu ra. 4. Xác định cấu trúc của hàm chức năng cần tìm và giải thuật học tƣơng ứng. Ví dụ, ngƣời kĩ sƣ có thể lựa chọn việc sử dụng mạng nơ-ron nhân tạo hay cây quyết định. 5. Hoàn thiện thiết kế. Ngƣời kĩ sƣ sẽ chạy giải thuật học từ tập huấn luyện thu thập đƣợc. Các tham số của giải thuật học có thể đƣợc điều chỉnh bằng cách tối ƣu hóa hiệu năng trên một tập con (gọi là tập kiểm chứng -validation set) của tập huấn luyện, hay thông qua kiểm chứng chéo (cross-validation). Sau khi học và điều chỉnh tham số, hiệu năng 15
17. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT của giải thuật có thể đƣợc đo đạc trên một tập kiểm tra độc lập với tập huấn luyện. Mục tiêu của việc học có giám sát một mô hình toàn cục là tìm ra một hàm g, khi cho sẵn một tập các điểm có dạng (x, g(x)). Giả thiết rằng đã biết trƣớc đặc điểm của hàm g đối với một tập điểm. Tập điểm đó đã đƣợc lấy mẫu độc lập và có cùng phân bố (independent and identically distributed (i.i.d.)) theo một xác xuất phân bố p chƣa biết từ một tập lớn hơn và có thể vô hạn. Ngoài ra, giả sử tồn tại một hàm hàm tổn thất (loss function) theo tác vụ L có dạng: trong đó Y là trùng với miền xác định của g và L ánh xạ tới các số thực không âm (có thể đặt thêm hạn chế cho L). Giá trị L(z, y) là tổn thất nảy sinh khi đoán giá trị của g tại một điểm cho trƣớc là z trong khi giá trị thực của nó là y. Hàm rủi ro f đƣợc định nghĩa là giá trị kỳ vọng của hàm tổn thất và có công thức nhƣ sau: nếu xác suất phân bố p là rời rạc (trƣờng hợp xác suất phân bố liên tục cần một tích phân xác định (definite integral) và một hàm mật độ xác suất. Mục tiêu là tìm một hàm f* trong số một lớp con cố định các hàm để cho rủi ro R(f*) là cực tiểu. 16
18. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT Tuy nhiên, do thƣờng chỉ biết đƣợc đặc điểm của hàm g cho một tập hữu hạn điểm (x1, y1), , (xn, yn), ngƣời ta chỉ có thể xác định gần đúng rủi ro thực sự, ví dụ, với rủi ro kinh nghiệm (empirical risk): Nguyên lý của cực tiểu hóa rủi ro kinh nghiệm là chọn hàm f* sao cho rủi ro kinh nghiệm là nhỏ nhất. Lý thuyết học bằng thống kê tìm hiểu xem việc cực tiểu hóa rủi ro kinh nghiệm có thể đạt đƣợc trong những điều kiện nào và có thể trông đợi các tính toán xấp xỉ tốt đến đâu. b. Học không có giám sát: Học không có giám sát ( unsupervised learning) là một phƣơng pháp của ngành học máy nhằm tìm ra một mô hình mà phù hợp với các quan sát. Nó khác biệt với học có giám sát ở chỗ là đầu ra đúng tƣơng ứng cho mỗi đầu vào là không biết trƣớc. Trong học không có giám sát, một tập dữ liệu đầu vào đƣợc thu thập. Học không có giám sát thƣờng đối xử với các đối tƣợng đầu vào nhƣ là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ đƣợc xây dựng cho tập dữ liệu đó. Học không có giám sát có thể đƣợc dùng kết hợp với suy diễn Bayes (Bayesian inference) để cho ra xác suất có điều kiện (nghĩa là học có giám sát) cho bất kì biến ngẫu nhiên nào khi biết trƣớc các biến khác. Học không có giám sát cũng hữu ích cho việc nén dữ liệu: về cơ bản, mọi giải thuật nén dữ liệu hoặc là dựa vào một phân bố xác suất trên một tập đầu vào một cách tƣờng minh hay không tƣờng minh. 17
19. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT 1.2 Khái niệm về học nửa giám sát Trong “học có giám sát”, các dữ liệu đƣợc gắn nhãn nên việc giải quyết vấn đề thƣờng là thuận lợi hơn rất nhiều. Tuy nhiên, với một số lƣợng dữ liệu lớn thì công việc gắn nhãn cho dữ liệu không còn đơn giản chút nào. Thực tế cho thấy những dữ liệu đƣợc gắn nhãn thƣờng đắt đỏ, việc tạo nhãn cho nó đòi hỏi nỗ lực của con ngƣời Còn “học không có giám sát” là mô hình hóa một tập dữ liệu, trong đó dữ liệu đầu vào chƣa đƣợc gắn nhãn mà nó dựa trên một mô hình phù hợp với các quan sát, vì vậy với một số lƣợng dữ liệu lớn thì sự chính xác của kết quả thu đƣợc không cao. Thực tế cho thấy rằng, dữ liệu chƣa đƣợc gắn nhãn có thể thu thập đƣợc rất nhiều và một cách dễ dàng, tuy nhiên để xử lý số lƣợng dữ liệu đó có kết quả tốt nhất cũng là cả một vấn đề. Học nửa giám sát là sự kết hợp giữa “học có giám sát” và “học không có giám sat”. Với một số lƣợng lớn dữ liệu, kể cả dữ liệu chƣa gắn nhãn và những dữ liệu đã đƣợc gắn nhãn, sẽ đƣợc “máy học” giải quyết một cách tốt nhất bằng các giải thuật “học nửa giám sát” vừa mất ít thời gian, yêu cầu nỗ lực của con ngƣời không nhiều và đạt hiệu quả cao . Nói chung “Học nửa giám sát” là một kĩ thuật của ngành học máy để xây dựng một hàm (function) từ dữ liệu huấn luyện, sau đó tổng quát mô hình chung cho tất cả dứ liệu gắn nhãn và chƣa đƣợc gắn nhãn. Nhằm tìm ra môt kết quả nhƣ mong muốn. 18
20. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT II. MỘT SỐ GIẢI THUẬT TRONG HỌC NỬA GIẤM SÁT 2.1 Generative Models 2.1.1 Giới thiệu về “Generative Models” “Generative Models” là phƣơng pháp cố điển nhất trong “semi - supervied learning”. Cũng nhƣ nhiều kiểu hệ thống làm mô hình, sinh sản những mô hình là những mô hình đƣợc mô tả bởi những chức năng và thao tác toán học đƣợc xắp xếp theo một sự phân cấp trên cùng một tập hợp dữ liệu điểm. Mô hình Sinh đƣợc dựa trên ý tƣởng theo một sự đa dạng bao gồm những thao tác toán học, kể cả giải pháp ràng buộc, phép lấy vi phân, sự hợp nhất và những thao tác làm mô hình truyền thống của những sự biến đổi và hình học nổi xây dựng có thứ bậc. Mô hình sinh sản hình thành một ngôn ngữ tự nhiên cho việc thuyết minh hình dạng. Những đề xuất làm mô hình sinh sản một tập hợp toán học đƣợc con ngƣời tạo ra những thao tác có thứ bậc tiêu chuẩn cho các đối tƣợng đa dạng khác nhau ( sự đẩy, quần thể, hình bánh xe, dịch, đặt tên đối tƣợng, ), những thao tác hình học nổi xây dựng (sự giao nhau, liên hiệp, sự trừ đi ), và những thao tác để tạo ra những bề mặt phụ thuộc và những hình dạng khác thời gian (nhƣ sự cực tiểu hóa đƣợc quét bằng những thao tác, phép lấy vi phân, sự hợp nhất, những hàm ngƣợc, giải pháp ràng buộc, cƣỡng ép ). Những thao tác này là tất cả kỹ thuật toán học đƣợc sử dụng một cách linh hoạt trong việc phân tích khoảng, đoạn và cung cấp một kiến trúc mô hình đa dạng, phong phú. 2.1. Generative Models trong Semi - supervised learning Generative Models thƣờng đƣợc biết đến với việc giải quyết các bài toán nhận dạng ảnh, nhận dạng văn bản, nhận dạng tiếng nói 19
21. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT a. Mô tả Generative Models Chúng ta giả thiết rằng, có một tập hợp dữ liệu đã đƣợc gắn nhãn ( x1, y1 ). Trong đó x1 là dữ liệu và y1 là nhãn của dữ liệu tƣợng ứng, đƣợc phân theo các lớp nhƣ hình dƣới đây: Khi thêm các dữ liệu chƣa đƣợc gắn nhãn, giả thiết mỗi lớp có một sự phân bố Gauss. Sẽ có một mô hình sao cho phù hợp với tập dữ liệu này nhất? để có thể phân lớp tất các các dữ liệu đƣợc đƣa vào: 20
22. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT b. Giải thuật Expectation-Maximization (EM) : - Giới thiệu về EM: Giải thuật EM nhằm giải quyết vấn đề tìm mô hình phân bố dữ liệu hợp lý nhất. Là một phƣơng pháp để tìm ra sự tối ƣu của việc phân lớp các dữ liệu dán nhãn và dữ liệu không gắn nhãn Gải thuật EM đƣợc xây dựng nhƣ sau: Tham số của mô hình: θ = {w1,w2, μ1, μ2, ∑1, ∑2} w1,w2: là các phân bố μ1, μ2: Là trung bình mẫu ∑1, ∑2: : Phƣơng sai mẫu Tập dữ liệu xử lý: D = (Xl, Yl,Xu) Tập dữ liệu chƣa gắn nhãn: H = Yu P(D/θ) = ∑Hp(D, H/θ) Gải thuật EM cần phải tìm ra hàm ƣớc lƣợng cực đại MLE. nghĩa là giá trị P(D/θ) cực đại trong không gian θ {W,µ,∑}. Mô hình sinh đầy đủ p(X, Y | θ). Các ký hiệu quy ƣớc: Phân lớp đƣợc tính theo công thức: Độ phù hợp với mô hình đƣợc tinh sheo công thức: P(x, y| θ) = P(y| θ)P(x|y, θ) = WyN(x; μy, ∑y) Số lƣợng các điểm: P(Xl, Yl,Xu|θ) = ∑yu P(Xl, Yl,Xu, Yu|θ) Tìm hàm ƣớc lƣợng cực đại của θ (MLE) Các bước giải quyết của Generative Models: 21
23. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT 1. Tìm hàm ƣớc lƣợng cực đại MLE θ {W,µ,∑}. từ tập dữ liệu đã đƣợc gắn nhãn. 2. Các dữ liêu gắn nhãn tiếp theo đƣợc xử lý: cho tất cả các giá trị x thuoc vào tập Xu 2.1.3 Ưu điểm và nhược điểm của giải thuật Ưu điểm: . Rõ ràng, học theo khung mô hình xác suất khá tốt . Có hiệu quả rất tốt nếu mô hình đó là mô hình dạng đóng. . Hạn chế: . Phải xác định đƣợc tính chính xác của mô hình . Xác minh đƣợc tính đồng nhất của mô hình . Xác định tối ƣu bằng giải thuật EM . Sẽ làm ảnh hƣởng đến những dữ liệu không đƣợc dán nhãn nếu mô hình bị sai. 2.1.5 Ứng dụng của mô hình Mô hình Sinh là cách tiếp cận tốt, cung cấp một công cụ chung cho những hệ thống khác để tƣơng tác toán học với các mô hinh khác. Thông qua giao diện này, những mô hình sinh có thể đƣợc sử dụng nhƣ thuyết minh thuộc hình học (cho) một sự đa dạng lớn (của) những ứng dụng. 22
24. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT Trong từng trƣờng hợp cụ thể, có thể xảy ra các kiểu phân bố dữ liệu khác nhau nên sẽ xử lý theo các các kiểu giải thuật tƣơng ứng. Sự pha trộn dữ liệu theo phân bố kiểu Gauss (GMM): Phân loại ảnh Sử dụng giải thuật EM Sự pha trộn dữ liệu theo phân bố kiểu đa thức (Na¨ıve Bayes) Nhận dạng văn bản Sử dụng giải thuật EM Hidden Markov Models (HMM) Nhận dạng tiếng nói Giải thuật Baum-Welch 2.2 Semi – superviesd Suport vector machines 2.2.1 Giới thiệu về S3VM Đặc trƣng cơ bản quyết định khả năng phân loại của một bộ phân loại là hiệu suất tổng quát hóa, hay là khả năng phân loại những dữ liệu mới dựa vào những tri thức đã tích lũy đƣợc trong quá trình huấn luyện. Thuật toán huấn luyện đƣợc đánh giá là tốt nếu sau quá trình huấn luyện, hiệu suất tổng quát hóa của bộ phân loại nhận đƣợc cao. Hiệu suất tổng quát hóa phụ thuộc vào hai tham số là sai số huấn luyện và năng lực của máy học. Trong đó sai số huấn luyện là tỷ lệ lỗi phân loại trên tập dữ liệu huấn luyện. Còn năng lực của máy học đƣợc xác định bằng kích thước Vapnik- Chervonenkis (kích thước VC). Kích thƣớc VC là một khái niệm quan trọng đối với một họ hàm phân tách(hay là bộ phân loại). Đại lƣợng này đƣợc xác định bằng số điểm cực đại mà họ hàm có thể phân táchhoàn toàn trong không gian đối tƣợng. Một bộ phânloại tốt là bộ phân loại có năng lực thấp nhất (có nghĩa là đơn 23
25. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT giản nhất) và đảm bảo sai số huấn luyện nhỏ. Phƣơng pháp S3VM đƣợc xây dựng dựa trên ý tƣởng này. 2.2.2 Giải thuật S3MV Xét bài toán phân loại đơn giản nhất - phân loại hai phân lớp với tập dữ liệu mẫu: {(xi, yi)| i = 1, 2, , N, xi Rm } Trong đó mẫu là các vector đối tượng được phân loại thành các mẫu dương và mẫu âm: − Các mẫu dƣơng là các mẫu xi thuộc lĩnh vực quan tâm và đƣợc gán nhãn yi = 1; − Các mẫu âm là các mẫu xi không thuộc lĩnh vực quan tâm và đƣợc gán nhãn yi = −1 Trong trƣờng hợp này, bộ phân loại SVM là mặt siêu phẳng phân tách các mẫu dương khỏi các mẫu âm với độ chênh lệch cực đại, trong đó độ chênh 24
26. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT lệch còn gọi là lề (margin) xác định bằng khoảng cách giữa các mẫu dƣơng và các mẫu âm gần mặt siêu phẳng nhất (hình 1). Mặt siêu phẳng này đƣợc gọi là mặt siêu phẳng lề tối ưu. Các mặt siêu phẳng trong không gian đối tƣợng có phƣơng trình là Wt + b = 0, trong đó w là vector trọng số, b là độ dịch. Khi thay đổi w và b, hƣớng và khoảng cách từ gốc tọa độ đến mặt siêu phẳng thay đổi. Bộ phân loại SVM đƣợc định nghĩa nhƣ sau f(x) = sign(Wt x + b) (1) Trong đó sign(z) = +1 nếu z ≥ 0, sign(z) = −1 nếu z < 0. Nếu f(x) = +1 thì x thuộc về lớp dƣơng (lĩnh vực đƣợc quan tâm), và ngƣợc lại, nếu f(x) = −1 thì x thuộc về lớp âm (các lĩnh vực khác). Bộ phân loại S3VM là một họ các mặt siêu phẳng phụ thuộc vào các tham số w và b. Mục tiêu của phƣơng pháp S3VM là ƣớc lƣợng w và b để cực đại hóa lề giữa các lớp dữ liệu dƣơng và âm. Các giá trị khác nhau của lề cho ta các họ mặt siêu phẳng khác nhau, và lề càng lớn thì năng lực của máy học càng giảm. Nhƣ, vậy, cực đại hóa lề thực chất là việc tìm một máy học có năng lực nhỏ nhất. Quá trình phân loại là tối ƣu khi sai số phân loại là cực tiểu. 2.2.3 Kết luận về S3VM Huấn luyện SVM là việc giải bài toán quy hoạch toàn phƣơng SVM. Các phƣơng pháp số giải bài toán quy hoạch này yêu cầu phải lƣu trữ một ma trận có kích thƣớc bằng bình phƣơng của số lƣợng mẫu huấn luyện. Trong những bài toán thực tế, điều này là không khả thi vì thông thƣờng kích thƣớc của tập dữ liệu huấn luyện thƣờng rất lớn (có thể lên tới hàng chục nghìn mẫu). Nhiều thuật toán khác nhau đƣợc phát triển để giải quyết vấn đề nêu 25
27. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT trên. Những thuật toán này dựa trên việc phân rã tập dữ liệu huấn luyện thành những nhóm dữ liệu. Điều đó có nghĩa là bài toán quy hoạch toàn phƣơng lớn đƣợc phân rã thành các bài toán quy hoạch toàn phƣơng với kích thƣớc nhỏ hơn. Sau đó, những thuật toán này kiểm tra các điều kiện KKT để xác định phƣơng án tối ƣu.  Ưu điểm: S3MV thích hợp cho nhiều kiểu xủ lý dữ liệ Mô hình toán học dễ hiểu, sáng sủa.  Hạn chế: Độ phức tạp cao, giải quyết bài toán tối ƣu khó 2.3 Self-training 26
28. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT CHƢƠNG III. SELF – TRAINING VÀ BÀI TOÁN NHẬN DẠNG KÝ TỤ TRÊN ẢNH I. GIẢI THUẬT SELF – TRAINING 1.1 Giới thiệu về Self – training Self – training là giải thuật trong “semi – superviesd learning”. 1.2 Giải thuật Giả thiết có một tập dữ liệu đã đƣợc gắn nhãn (Xl, Yl). Mục tiêu của thuật toán là phân loại các dữ liệu chƣa đƣợc gắn nhãn. Để giải quyết vấn đề bằng giải thuật self – training, đàu tiên cúng ta thiết lập một tập huấn luyện f tù các dữ liệu đã đƣợc gắn nhãn. Khi đa sinh ra hàm f, chúng ta sẽ đoán nhận, phân loại đƣợc các dứ liệu chƣa gắn nhãn theo các bƣớc sau: Bƣớc 1: Tìm tập huấn luyện f từ tập dữ liệu đã dƣợc gắn nhãn (Xl, Yl) Bƣớc 2: Dự đoán, phân loại dữ liệu x chƣa có nhãn đƣợc đua vào từ tập Xi Bƣớc 3: Bổ sung vào tập huấn luyện ban đầu (x, f(x)) Bƣớc 4: Lặp lại quá trình từ bƣớc 1 27
29. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT 1.3 Đánh giá giải thuật Ưu điểm: Là phƣơng pháp đơn giản nhất trong semi – superviesd learning. Thƣờng sử dụng trong những nhiệm vụ thực sự nhƣ xử lý ngôn ngữ tự nhiên Giải thuật dể hiểu, dễ học. Hạn chế của giải thuật: II. BÀI TOÁN NHẬN DẠNG KÝ TỰ TRÊN ẢNH 2.1 Phân tích bài toán Đầu vào dữ liệu là ảnh bitmap, đen trắng. Ảnh bao gồm các ký tự cần đoán nhận. Đầu ra dữ liệu là các ký tự ( bản Text ). Hướng xử lý dữ liệu: Phân tích ảnh để tìm ra các đặc tính Chuyển đổi các ký hiệu thành pixel matrices Khôi phục các đặc tính đầu ra tƣơng ứng và chuyển về dạng Unicode So sánh đầu ra tƣơng ứng và tính toán lỗi. Update các giá trị trọng lƣơng, huấn luyện lại và lặp lại quá trình 2.2 Hướng giải quyết bài toán. Sử dụng giải thuật self – training (semi – superviesd learning), xây dƣng mô hình bằng mạng nơron. 28
30. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT 29
31. Semi – Superviesd learning Nguyễn Ngọc Tùng – K54B - CNTT CHƢƠNG IV. MỘT SỐ KẾT QUẢ ĐẠT ĐƢỢC VÀ HƢỚNG PHÁT TRIỂN I. KẾT QUẢ BAN ĐẦU ĐÃ ĐẠT ĐƢỢC Tìm hiêu đƣợc bản chất của giải thuật semi - superviesd, các giải thuật trong semi – superviesd. Semi – superviesd là lựa chọn hữu ích cho các bài toán nhận dang, phân loại Bài toán nhận dạng ký tự trên ảnh đang đƣợc tìm hiểu và phát triển thêm để có đƣợc kết quả cuối cùng. II. HƢỚNG PHÁT TRIỂN Semi – superviesd là phƣơng pháp học tốn ít thời gian và dảm bảo tối đa hiệu quả công việc. Nó là sự kết hợp của “học không có giám sát” và “học có giám sát”, vì vậy rất thích hợp để xử lý vào các bài toán thực tế. Semi – superviesd cùng với các mô hình mạng noron, SVM là lĩnh vực đang đƣợc nghiên cứu rất nhiều trong các dự án nhận dạng, phân loại, xử lý ảnh trong thực tế. 30