Đề tài Semi – Supervised learning

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 MỤC LỤC NHẬN XÉT CỦA HỘI ĐỒNG ………………………………………………………………………………………………................................................................................................................................................................................................................................................................................................................................................................................................................................................ ………………………………………………………………………………………………................................................................................................................................................................................................................................................................................................................................................................................................................................................ ………………………………………………………………………………………………................................................................................................................................................................................................................................................................................................................................................................................................................................................ ………………………………………………………………………………………………................................................................................................................................................................................................................................................................................................................................................................................................................................................ ………………………………………………………………………………………………................................................................................................................................................................................................................................................................................................................................................................................................................................................ ………………………………………………………………………………………………................................................................................................................................................................................................................................................................................................................................................................................................................................................ ………………………………………………………………………………………………................................................................................................................................................................................................................................................................................................................................................................................................................................................ ………………………………………………………………………………………………................................................................................................................................................................................................................................................................................................................................................................................................................................................ ………………………………………………………………………………………………................................................................................................................................................................................................................................................................................................................................................................................................................................................ ………………………………………………………………………………………………................................................................................................................................................................................................................................................................................................................................................................................................................................................ 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ế. Đị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 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 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 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ử: Đ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 ) 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, … 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. 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 Mạng nơ-ron Cây quyết định Gene expression programming Lập trình di truyền Gaussian process regression Linear discriminant analysis k láng giềng gần nhất Minimum message length Perceptron Radial basis function Support vector machine Mô hình hóa các hàm mật độ xác suất qua các generative model: Thuật toán cực đại kì vọng (expectation-maximization algorithm) Các mô hình đồ họa gồm mạng Bayes và mạng Markov (Markov random field) Generative Topographic Mapping Các kỹ thuật suy diễn xấp xỉ đúng (appromixate inference techniques): Chuỗi Markov phương pháp Monte Carlo 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. 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). Để 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: 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. 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. 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. 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. 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 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. 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. 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. 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... 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: 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: 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. 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 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 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 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 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 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. 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ế.