Luận văn Thạc sĩ Công nghệ thông tin: Nghiên cứu ứng dụng mạng Nơ ron trong nhận dạng chữ Hán-Nôm

ĐẠI HỌC QUỐC GIA HÀ NỘI ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

TRƢƠNG THỊ HƢƠNG TRƢƠNG THỊ HƢƠNG NGHIÊN CỨU ỨNG DỤNG MẠNG NƠ RON TRONG NGHIÊN CỨU ỨNG DỤNG MẠNG NƠ RON TRONG NHẬN DẠNG CHỮ HÁN-NÔM NHẬN DẠNG CHỮ HÁN-NÔM LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2014

Hà Nội – 2014

ĐẠI HỌC QUỐC GIA HÀ NỘI ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

TRƢƠNG THỊ HƢƠNG TRƢƠNG THỊ HƢƠNG

NGHIÊN CỨU ỨNG DỤNG MẠNG NƠ RON TRONG NGHIÊN CỨU ỨNG DỤNG MẠNG NƠ RON TRONG NHẬN DẠNG CHỮ HÁN-NÔM NHẬN DẠNG CHỮ HÁN-NÔM

Ngành: Công nghệ thông tin Ngành: Công nghệ thông tin

Chuyên ngành: Kỹ thuật phần mềm Chuyên ngành: Kỹ thuật phần mềm

Mã số: 60480103 Mã số: 60480103

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN NGƢỜI HƢỚNG DẪN KHOA HỌC: NGỌC BÌNH PGS.TS. NGUYỄN NGỌC BÌNH Hà Nội – 2014

Hà Nội – 2014

LỜI CAM ĐOAN

Tên tôi là Trƣơng Thị Hƣơng, học viên cao học K18, chuyên ngành Công nghệ phần mềm, khoá 2011-2013. Tôi xin cam đoan luận văn thạc sĩ “Nghiên cứu ứng dụng mạng Nơ ron trong nhận dạng chữ Hán-Nôm” là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kỳ công trình nào khác.

Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này đã đƣợc cảm ơn và các thông tin trích dẫn trong Luận văn đã đƣợc chỉ rõ nguồn gốc.

Học viên thực hiện Luận văn

Trƣơng Thị Hƣơng

LỜI CẢM ƠN

Tôi xin gửi lời cảm ơn sâu sắc tới Phó giáo sƣ - Tiến sĩ Nguyễn Ngọc Bình, ngƣời thầy kính mến đã hết lòng giúp đỡ tạo mọi điều iện thuận lợi cho tôi trong suốt quá trình học tập và hoàn thành luận văn tốt nghiệp

Tôi xin gửi lời cảm ơn tới Tiến sĩ Nguyễn Tuấn Cƣờng, Tiến sĩ Nguyễn Đức D ng đã giúp giới thiệu cho tôi về chữ Nôm, lịch sử hình thành và phát triển, các thành phần cấu tạo của chữ Nôm, chia s cho tôi những inh nghiệm nghiên cứu và các công nghệ nhận dạng.

Tôi xin gửi lời cảm ơn đến NCS. Phạm Văn Hƣởng, ngƣời đã có nhiều kinh nghiệm làm việc trong vấn đề nhận dạng chữ Nôm, và đã chia s với tôi nhiều kiến thức và kinh nghiệm quý báu để tôi hoàn thành luận văn này.

Tôi c ng xin đƣợc gửi lời cảm ơn đến các bạn trong nhóm nghiên cứu nhận dạng chữ Nôm của trƣờng Đại học Công nghệ, Đại học Quốc gia Hà Nội, những ngƣời đã cùng tôi chia s kết quả nghiên cứu, đóng góp cho tôi những ý kiến quý báu và chia s những kinh nghiệm hay cho tôi trong mỗi muổi semina hàng tuần.

Tôi xin đƣợc gửi lời cảm ơn đến các tác giả, nhóm tác giả của những giáo trình, những công trình khoa học và những bài báo khoa học mà tôi tham khảo để hoàn thiện luận văn này.

Tác giả

DANH MỤC BẢNG BIỂU

Bảng 2.1 Một số hàm truyền thông dụng ............................................................ 15

Bảng 4.1 Kết quả khảo sát sự hội tụ của mạng nơ-ron ....................................... 47

Bảng 4.2 Kết quả thực nghiệm với mạng GANN ............................................... 54

Bảng 4.3 Kết quả thực nghiệm với mạng ANN .................................................. 55

DANH MỤC HÌNH VẼ

Hình 1.1 Mô hình nhận dạng chữ Hán - Nôm .................................................... 10

Hình 2.1 Cấu tạo của tế bào nơ-ron sinh học ...................................................... 13

Hình 2.2 Nơ-ron nhân tạo ................................................................................... 14

Hình 2.3 Mạng tự kết hợp ................................................................................... 17

Hình 2.4 Mạng kết hợp khác kiểu ....................................................................... 17

Hình 2.5 Mạng truyền thẳng ............................................................................... 18

Hình 2.6 Mạng hồi quy ....................................................................................... 18

Hình 2.7 Mối liên hệ giữa sai số và ích thƣớc mẫu .......................................... 21

Hình 2.8 Cấu trúc của SAINT ............................................................................. 31

Hình 4.1 Sơ đồ thuật toán GANN ....................................................................... 48

Hình 4.2 Quy trình tiến hành thực nghiệm ..................................................... 49

Hình 4.3 một số mẫu chữ Nôm trong bộ dữ liệu thực nghiệm ................... 50

Hình 4.4 Giao diện cấu hình mạng ...................................................................... 52

Hình 4.5 Giao diện lựa chọn tham số cho GA .................................................... 52

Hình 4.6 Giao diện huấn luyện mạng và nhận dạng ........................................... 53

MỤC LỤC

MỞ ĐẦU ............................................................................................................... 1

Chƣơng 1. TỔNG QUAN ..................................................................................... 3

1.1. Lịch sử ra đời chữ Nôm [1, 3] .................................................................... 3

1.2. Cấu tạo của chữ Nôm ................................................................................. 5

1.2.1 Mƣợn cả âm và nghĩa của chữ Hán ...................................................... 5

1.2.2 Mƣợn nghĩa chữ Hán, hông mƣợn âm. .............................................. 5

1.2.3 Mƣợn âm chữ Hán, không nhất thiết mƣợn nghĩa ............................... 6

1.2.4 Ghép hai chữ Hán với nhau. ................................................................. 6

1.2.5 Thêm, bớt các nét ................................................................................. 7

1.3. Các nghiên cứu về chữ Nôm ...................................................................... 8

1.4 Mô hình nhận dạng tổng thể và phạm vi nghiên cứu .................................. 9

Chƣơng 2. MẠNG NƠ-RON .............................................................................. 12

2.1 Nơ-ron sinh học ......................................................................................... 12

2.2 Mạng nơ-ron nhân tạo ............................................................................... 13

2.3 Các kiểu mô hình mạng Nơ-ron ................................................................ 16

2.4 Huấn luyện và xây dựng mạng Nơ-ron ..................................................... 18

2.4.1 Các phƣơng pháp học ......................................................................... 18

2.4.2 Các vấn đề trong xây dựng mạng nơ-ron ........................................... 20

2.5 Đánh giá các nhân tố của quá trình học .................................................... 25

2.5.1 Khởi tạo các trọng số ......................................................................... 25

2.5.2 Bƣớc học α ......................................................................................... 25

2.5.3 Hằng số quán tính ............................................................................... 26

2.6 Một số ứng dụng của mạng Nơ-ron trong nhận dạng chữ tƣợng hình ..... 26

2.6.1 Back-Propagated Neural Network [5, 6, 9] ....................................... 26

2.6.2 Mạng nơ-ron xác suất (ProbabilisticNeural Networks – PNN). [8] .. 28

2.6.3 Mạng nơ-ron thông minh tự thích nghi (structurally adaptive intelligent neural tree - SAINT) [12] .......................................................... 31

Chƣơng 3: GIẢI THUẬT DI TRUYỀN ............................................................. 34

3.1 Cơ sở thực tiễn của giải thuật di truyền .................................................... 34

3.2 Cơ chế thực hiện giải thuật di truyền ........................................................ 35

3.3 Các thành phần trong giải thuật di truyền ................................................. 37

3.4 Các toán tử di truyền ................................................................................. 39

3.4.1 Toán tử chọn lọc ................................................................................. 39

3.4.2 Toán tử lai ghép .................................................................................. 40

3.4.3 Toán tử đột biến ................................................................................. 43

3.5 Các tham số trong giải thuật di truyền ...................................................... 44

Chƣơng 4. NHẬN DẠNG CHỮ HÁN-NÔM DỰA TRÊN MẠNG NƠ-RON KẾT HỢP GA ..................................................................................................... 46

4.1 Khảo sát sự hội tụ của mạng nơ-ron ......................................................... 46

4.2 Thuật toán GANN ..................................................................................... 47

4.3 Thực nghiệm ............................................................................................. 49

4.3.1 Quy trình thực nghiệm ....................................................................... 49

4.3.2 Xây dựng bộ dữ liệu thực nghiệm ...................................................... 50

4.3.3 Tiến hành thực nghiệm ....................................................................... 51

4.4 Đánh giá ết quả ........................................................................................ 53

KẾT LUẬN ......................................................................................................... 57

MỞ ĐẦU

Chữ Nôm đƣợc hình thành và phát triển từ thế kỷ X tới thế kỷ XX. Là một di sản văn hóa, có vai trò đặc biệt quan trọng trong việc tạo nên một nền văn học rực rỡ xuyên suốt nhiều thế kỷ. Viện Nghiên cứu Hán Nôm Việt Nam hiện đang lƣu giữ hàng trăm ngàn đơn vị tƣ liệu chữ Nôm rất có giá trị trong việc nghiên cứu đời sống của ngƣời Việt thời xa xƣa ở nhiều mảng lĩnh vực: văn học, tƣ tƣởng, triết học, ngôn ngữ, luật pháp, đạo đức… Tuy nhiên số ngƣời có thể đọc và viết chữ Nôm ở nƣớc ta hiện nay còn không nhiều, do đó việc đƣa chữ Nôm vào máy tính, xây dựng từ điển chữ Nôm, nhận dạng, đoán nhận và khôi phục chữ Nôm lỗi, thiếu là lĩnh vực nghiên cứu có ý nghĩa thực tiễn quan trọng.

Mạng nơ-ron là một trong những công cụ nhận dạng tốt nhất vì các đặc trƣng sau: Khả năng học từ kinh nghiệm (khả năng đƣợc huấn luyện), khả năng xử lý song song với tốc độ xử lý nhanh, khả năng học thích nghi, khả năng hái quát hoá cho các đầu vào không đƣợc huấn luyện, ví dụ dựa vào cách học mạng có thể sẽ tiên đoán đầu ra từ đầu vào không biết trƣớc [15, 16].

Tuy nhiên một nhƣợc điểm khi dùng mạng nơ-ron là chƣa có phƣơng pháp luận chung khi thiết kế cấu trúc mạng cho các bài toán nhận dạng và điều khiển mà phải cần tới kiến thức của chuyên gia. Mặt khác khi xấp xỉ mạng nơ- ron với một hệ phi tuyến sẽ hó hăn hi luyện mạng vì có thể không tìm đƣợc điểm tối ƣu toàn cục... Vì vậy tồn tại lớn nhất gặp phải là tìm nghiệm tối ƣu toàn cục, đặc biệt áp dụng cho các bài toán lớn, các hệ thống điều khiển quá trình.

Trong luận văn tôi trình bày hoàn chỉnh một phƣơng pháp ứng dụng mạng nơ-ron trong nhận dạng chữ Hán-Nôm với mong muốn đƣa ra một phƣơng pháp nhận dạng tốt, góp phần xây dựng một công cụ có thể nhận dạng, chuyển đổi các văn bản chữ Hán-Nôm thành chữ Quốc ngữ nhằm làm sáng tỏ những giá trị văn hóa lƣu trữ trong nó. Cấu trúc luận văn gồm các phần nhƣ sau:

Chương 1. Tổng quan: Nội dung chƣơng 1 trình bày tổng quan về chữ Nôm, lịch sử hình thành và phát triển chữ Nôm, mô hình tổng quan của hệ thống nhận dạng chữ Nôm.

Chương 2. Mạng Nơ-ron: Nội dung chƣơng này trình bày tổng quan về mạng Nơ-ron, cách xây dựng mạng, đánh giá các yếu tố trong

quá trình huấn luyện mạng và tổng hợp một số phƣơng pháp nhận dạng chữ tƣợng hình dựa trên mạng Nơ-ron.

Chương 3. Giải thuật di truyền: Chƣơng này giới thiệu về giải thuật

di truyền, các thành phần của giải thuật di truyền.

Chương 4. Nhận dạng chữ Hán-Nôm dựa trên mạng nơ-ron kết hơn GA: Chƣơng này đề xuất một phƣơng pháp ết hợp giải thuật di truyền trong quá trình huấn luyện mạng Nơ-ron nhằm tìm ra bộ trong số tối ƣu cho mạng. Trình bày kết quả thực nghiệm nhận dạng 2970 chữ Hán-Nôm.

Phần kết luận: Phần này trình bày những đóng góp của luận văn, những tồn tại, hạn chế chƣa đƣợc giải quyết và hƣớng giải quyết tiếp theo.

Chƣơng 1. TỔNG QUAN

1.1. Lịch sử ra đời chữ Nôm [1, 3]

Cách cấu tạo chữ Nôm "có thể" đã manh nha ló dạng từ những năm đầu khi ngƣời Trung Hoa chinh phục đất Giao Chỉ(Miền Bắc Việt Nam) và đặt nền đô hộ trên các bộ lạc ngƣời Việt vào đầu Công nguyên. Vì ngôn ngữ khác biệt, những "chữ Nôm" đầu tiên xuất hiện vì nhu cầu ghi địa danh, tên ngƣời hoặc những khái niệm hông có trong Hán văn. Song chứng cứ còn lƣu lại hết sức ít ỏi, khó kiểm chứng đƣợc một cách chính xác. Phạm Huy Hổ trong "Việt Nam ta biết chữ Hán từ đời nào?" thì cho rằng chữ Nôm có từ thời Hùng Vƣơng. Văn Đa cƣ sĩ Nguyễn Văn San lại cho rằng chữ Nôm có từ thời Sĩ Nhiếp cuối đời Đông Hán thế kỷ thứ 2. Nguyễn Văn Tố dựa vào hai chữ "bố cái" trong danh xƣng "Bố Cái đại vƣơng" do nhân dân Việt Nam suy tôn Phùng Hƣng mà cho rằng chữ Nôm có từ thời Phùng Hƣng thế kỷ thứ 8. Ý kiến khác lại dựa vào chữ "cồ" trong quốc hiệu "Đại Cồ Việt" để cho rằng chữ Nôm có từ thời Đinh Tiên Hoàng. Trong một số nghiên cứu vào thập niên 1990, các học giả căn cứ vào đặc điểm cấu trúc nội tại của chữ Nôm, dựa vào cứ liệu ngữ âm lịch sử tiếng Hán và tiếng Việt, so sánh đối chiếu hệ thống âm tiếng Hán và tiếng Hán Việt đã đi tới kết luận rằng âm Hán Việt (âm của ngƣời Việt đọc chữ Hán) ngày nay bắt nguồn từ thời nhà Đƣờng-nhà Tống thế kỷ 8-9. Và nếu âm Hán Việt có từ thời Đƣờng, Tống thì chữ Nôm không thể ra đời trƣớc khi cố định cách đọc Hán Việt (nếu xét chữ Nôm với tƣ cách hệ thống văn tự) và chỉ có thể ra đời sau khoảng thế kỷ thứ 10 hi ngƣời Việt thoát khỏi nghìn năm Bắc thuộc với chiến thắng của Ngô Quyền vào năm 938.

Mặc dù lịch sử hình thành chữ Nôm còn không ít vấn đề cần làm sáng tỏ, nhƣng về ý nghĩa của sự ra đời của chữ Nôm, các nhà nghiên cứu đều thống nhất nhận định rằng: trong suốt quãng thời gian tồn tại, chữ Nôm là công cụ duy

nhất, hoàn toàn Việt Nam, ghi lại lịch sử, văn hóa của dân tộc Việt. Sự hình thành và phát triển của chữ Nôm là bƣớc ngoặt trong lịch sử ngôn ngữ văn tự của ngƣời Việt và c ng là một bƣớc ngoặt trong lịch sử văn hóa Việt nam, chữ Nôm ra đời đáp ứng đòi hỏi của việc trực tiếp ghi chép hoặc diễn đạt lời ăn tiếng nói cùng tâm tƣ, suy nghĩ và tình cảm của bản thân ngƣời Việt bắt nguồn từ ý thức phản vệ của dân tộc chống lại xu hƣớng Hán hóa của ngƣời phƣơng Bắc, khẳng định tinh thần dân tộc của ngƣời Việt.

Chữ Nôm là cách viết biểu ý ngày xƣa của tiếng Việt. Sau khi Việt Nam thoát khỏi ách đô hộ của Trung Quốc vào năm 939, chữ Nôm lần đầu tiên thành chữ quốc ngữ để diễn đạt tiếng Việt qua mẫu tự biểu ý. Hơn 1000 năm sau đó - từ thế kỷ 10 cho đến thế kỷ 20 - chữ Nôm đã tạo nên những thành tựu rực rỡ làm phong phú ho tàng văn hóa Việt: văn học, triết học, sử học, luật pháp, y khoa, tôn giáo, điều mà trƣớc nó chữ Hán trên đất Việt không hề có đƣợc.

Bắt đầu từ thế kỷ 15 với Quốc âm thi tập của Nguyễn Trãi, kế đến thế kỷ 16 với Bạch Vân Am thi tập của Nguyễn Bỉnh Khiêm, chữ Nôm đã chứng tỏ có nhiều khả năng diễn tả không những tình cảm mà còn tƣ tƣởng của ngƣời Việt. Chỉ tính riêng ở lĩnh vực văn học, chữ Nôm đã có vai trò đặc biệt quan trọng trong việc tạo nên một nền văn học Việt nam rực rỡ xuyên suốt nhiều thế kỷ. Từ chữ Nôm, nền văn học Việt nam sinh ra ba thể loại độc đáo của riêng Việt nam là Truyện thơ Nôm Lục Bát, Ngâm Khúc (song thất lục bát) và Hát Nói (trong ca trù). Sự sáng tạo đó đã để lại cho đời sau những di sản thơ Nôm vô giá.

Tuy nhiên việc dùng chữ Nôm song song với chữ Hán chỉ đƣợc duy trì cho đến thế kỷ 16. Khi các nhà truyền đạo phƣơng Tây vào Việt Nam, họ đã dùng kí tự La Tinh để phiên âm tiếng Việt, và chữ Quốc ngữ dựa trên kí tự La Tinh đƣợc hình thành. Mặc dù dễ học, dễ nhớ, việc dùng chữ Quốc ngữ sau đó chỉ phổ biến trong cộng đồng giáo dân trong phạm vi ghi chép Kinh Thánh chứ hông đƣợc sử dụng nhiều trong việc làm phƣơng tiện trứ tác hay truyền đạt thông tin.

Chữ Nôm vì vậy vẫn là văn tự chính trong nền văn chƣơng Việt Nam mãi cho tới hết thế kỷ 19. Sang đầu thế kỷ 20 chính quyền Pháp cho giải thể phép thi cử chữ Nho (1915 ở Bắc Kỳ và 1919 ở Trung Kỳ) và đƣa chữ Quốc ngữ lên hàng văn tự chính thức. Bắt đầu từ năm 1908 chữ Quốc ngữ mới bắt đầu thay thế chữ Nôm. Phong trào Đông Kinh Nghĩa Thục (1907) và Hội Truyền bá Quốc ngữ (1938) c ng nhƣ sự phát triển báo chí vào đầu thế kỷ 20 đã góp phần trong

việc thâu nhận chữ Quốc ngữ là văn tự chính đáng của ngƣời Việt, khép lại thời kỳ dùng chữ Nôm để truyền đạt tƣ duy cùng những cảm hứng của dân tộc Việt.

Sau khi chữ quốc ngữ đƣợc phổ biến vào đầu thế kỷ 20, chữ Nôm dần dần mai một. Chính quyền thực dân Pháp có chính sách cấm dùng chữ Nôm. Điều đó hiến cho di sản này hiện nay có nguy cơ tiêu vong. Thực tế là hiện nay, trên thế giới có chƣa đến 100 ngƣời đọc đƣợc chữ Nôm. Một phần to tát của lịch sử Việt Nam nhƣ thế nằm ngoài tầm tay của 80 triệu ngƣời nói tiếng Việt.

1.2. Cấu tạo của chữ Nôm

Dựa vào chữ Hán, chữ Nôm đã đƣợc hình thành bằng nhiều cách khác nhau. Trong đó, có thể tóm tắt thành 5 loại dựa vào ba yếu tố hình-âm-nghĩa nhƣ sau:

1.2.1 Mượn cả âm và nghĩa của chữ Hán

Chữ Hán đƣợc mƣợn cả âm và nghĩa để ghi lại các âm gốc Hán. Âm đọc

có ba loại là:

- Âm Hán Việt tiêu chuẩn: bắt nguồn từ ngữ âm tiếng Hán thời Đƣờng. Ví

dụ: "thành" 城, "hoa" 花, "thuyền" 船, "ngọc" 玉.

- Âm Hán Việt cổ: bắt nguồn từ ngữ âm tiếng Hán trƣớc thời Đƣờng. Ví

dụ: "mùa" 務 (âm Hán Việt tiêu chuẩn là "vụ), "bay" 飛 (âm Hán Việt tiêu

chuẩn là "phi"), "buồng" 房 (âm Hán Việt tiêu chuẩn là "phòng"), "xe" 車 (âm

Hán Việt tiêu chuẩn là "xa").

- Âm Hán Việt Việt hoá: là các âm gốc Hán bị biến đổi cách đọc do ảnh

hƣởng của quy luật ngữ âm tiếng Việt. Ví dụ: "thêm" 添 (âm Hán Việt tiêu

chuẩn là "thiêm"), "nhà" 家 (âm Hán Việt tiêu chuẩn là "gia"), "khăn" 巾 (âm

Hán Việt tiêu chuẩn là "cân"), "ghế" 几 (âm Hán Việt tiêu chuẩn là "kỉ"),

1.2.2 Mượn nghĩa chữ Hán, không mượn âm.

Mƣợn chữ Hán đồng nghĩa hoặc cận nghĩa để ghi lại âm tiếng Việt.

1.2.3 Mượn âm chữ Hán, không nhất thiết mượn nghĩa

- Đọc chính xác âm Hán Việt tiêu chuẩn: chữ "một" 沒 có nghĩa là "chìm"

Mƣợn chữ Hán đồng âm hoặc cận âm để ghi âm tiếng Việt. Âm mƣợn có thể là âm Hán Việt tiêu chuẩn, âm Hán Việt cổ hoặc âm Hán Việt Việt hoá. Khi đọc có thể đọc giống với âm mƣợn hoặc đọc chệch đi. Ví dụ:

đƣợc mƣợn dùng để ghi từ "một" trong "một mình", chữ "tốt" 卒 có nghĩa là

"binh lính" đƣợc mƣợn dùng để ghi từ "tốt" trong "tốt xấu", chữ "xƣơng" 昌 có

nghĩa là "hƣng thịnh" đƣợc mƣợn dùng để ghi từ "xƣơng" trong "xƣơng thịt",

chữ "qua" 戈 là tên gọi của một loại binh hí đƣợc mƣợn dùng để ghi từ "qua"

- Đọc chệch âm Hán Việt tiêu chuẩn: "gió" 這 (mƣợn âm "giá"), "cửa" 舉

trong "hôm qua".

- Đọc chính xác âm Hán Việt cổ: chữ "vạn" 萬 đọc là "muôn", chữ "tuế" 歲

(mƣợn âm "cử"), "đêm" 店 (mƣợn âm "điếm"), "chạy" 豸 (mƣợn âm "trãi").

đọc là "tuổi"

1.2.4 Ghép hai chữ Hán với nhau.

Loại này hết sức phổ biến và thƣờng ghép một thành tố biểu âm với một thành tố biểu ý (giống nhƣ chữ hình-thanh trong Lục thƣ). Ví dụ:tháng = nguyệt

月 (biểu ý) + thƣớng 尚 (biểu âm); mắt = mục 目 (biểu ý) + mạt 末 (biểu

âm); năm (con số) = ng (五 biểu ý) + nam (南 biểu âm); năm (năm tháng) =

niên (年 biểu ý) + nam (南 biểu âm).

Ngoài ra thỉnh thoảng c ng có những chữ ghép hai chữ Hán nhƣng cả hai

đều biểu ý nhƣ trời= thiên 天 + thƣợng 上; sáng=quang 光 + minh 明. Những

chữ này hông nhiều.

Thêm nét và thêm chữ Hán

Ví dụ: Bố (đối lập với mẹ) = vƣơng 王 + bố 布 + nét giản lƣợc của 司)

Thêm bộ thủ khác

Ví dụ: 渃 nước (thủy 氵+ nhƣợc 若); 扜 vo [vo tròn] (thủ 扌+ vu 于);

Phật (nhân イ+ thiên 天). Các bộ thủ thƣờng đƣợc dùng là: 亠, 刂, イ, 厂, 广,

氵, 忄, 辶, 土, 寸, 口, 巾, 山, 犭, 子, 小, 女, 礻, 灬, 木, 艹, 日, 月, 牛, 毛, 片,

牙, 疒, 瓦, 石, 衤, 白, 目, 皮, 田, 米, 耳, 竹, 舟, 羽, 雨, 色, 耒, 糸, 貝, 走, 足,

車, 角, 酉, 金, 風, 食, 髟, 馬, 魚, 赤.

1.2.5 Thêm, bớt các nét

Ví dụ: 女< nỡ, nợ, nữa (bằng dấu < cộng với chữ 女 nữ); 馬< mỡ, mựa

(dấu < cộng với chữ 馬 mã). “朱< cho (dấu < cộng với 朱 chu); “貝< buổi (dấu

< cộng với 貝 bối)

" hệnh hạng" (đều dùng chữ "cộng" 共 bớt nét, trong đó chữ " hệnh" bỏ

nét phảy ノ, chữ " hạng" ヽ bỏ nét mác). " hề hà" (đều dùng chữ " ỳ" 其, chữ

" hề" bỏ nét phảy ノ, chữ " hà" bỏ nét mác ヽ).

Ngoài ra còn một số chữ đƣợc viết tắt từ chữ Hán gốc và hông đổi cả âm lẫn nghĩa. Những chữ này tƣơng đƣơng với chữ Giản thể của Trung Quốc, nhƣng c ng có nhiều chữ hông trùng với chữ Giản thể do đƣợc viết tắt theo lối

Nôm. Ví dụ: 渃 phong (viết tắt chữ 風 phong); 乙 v (viết tắt 雨 v , hông phải

là "ất"); り tiền (viết tắt chữ 錢 tiền).

Ngoài ra một vài dân tộc thiểu số hác nhƣ Tày, Dao, Ngạn, v.v. c ng tạo

ra chữ Nôm dựa trên chữ Hán để lƣu lại ngôn ngữ của họ.

Qua cách cấu tạo của chữ Nôm nhƣ vậy, có thể nhận thấy rằng: chữ Nôm thƣờng có nhiều nét hơn, phức tạp hơn chữ Hán (do phần lớn là những chữ buộc phải ghép 2 chữ Hán lại) nên khó nhớ hơn cả chữ Hán vốn c ng đã hó nhớ. Cách đọc c ng có hi hông thống nhất hoặc một chữ có thể có nhiều cách đọc, cách viết, nên có ngƣời nói rằng "chữ Nôm phải vừa đọc vừa đoán". Ngoài ra,

việc "tam sao thất bản" là khó tránh khỏi, phần vì trình độ ngƣời thợ khắc chữ ngày xƣa, phần vì khâu in mộc bản có chất lƣợng không cao (chữ bị nhòe, mất nét).

1.3. Các nghiên cứu về chữ Nôm

Chúng ta có thể khẳng định rằng Việt Nam có hai thứ chữ viết ghi lại tiếng Việt, một là chữ latinh(quốc ngữ), và hai là Hán-Nôm thuộc loại chữ biểu ý. Và chúng ta có hai lựa chọn: một là để mất hiểu biết chữ Hán Nôm, nghĩa là mất đi một phần lớn truyền thống và tri thức quá khứ của dân tộc, hai là dùng mọi loại kỹ thuật tiên tiến nhất để phục hồi và bảo tồn truyền thống văn hoá dân tộc ghi lại bằng chữ Hán Nôm. Với mục đích bảo tồn di sản Hán – Nôm, ngày 13/9/1979 Viện nghiên cứu Hán Nôm đƣợc thành lập trên cơ sở ban Hán Nôm, theo quyết định số 326/CP của hội đồng Chính phủ và đƣợc tái khẳng định thuộc trung tâm Khoa học xã hội và Nhân văn Quốc gia trong Nghị định số 23/CP ngày 22/5/1993 của Chính phủ. Đây là cơ quan duy nhất ở Việt Nam vừa là trung tâm bảo tồn vừa là trung tâm hai thác các tƣ liệu chữ Hán và chữ Nôm. Với mục đích bảo tồn di sản Hán Nôm bằng công nghệ, bao gồm:

1. Chia s các cơ sở dữ liệu có liên quan tới Hán Nôm.

2. Truy nhập công cộng vào các bản lƣu trữ và di sản Hán Nôm.

3. Giáo dục Hán Nôm bằng công nghệ: học tập và nghiên cứu Hán Nôm dựa

trên các tƣ liệu đã số hóa.

Với những nỗ lực bảo tồn di sản của dân tộc, hiện nay đã có bộ phông Arial Unicode MS chứa khoảng hơn 5.000 chữ Nôm trùng hình chữ Hán. Viện Mojikyo tại Nhật Bản đã làm ra phông chữ truetype cho 9.299 chữ Nôm mà Việt Nam đã đề nghị với quốc tế. Công ti DynaLab Đài Loan có trụ sở tại Thƣợng Hải và Hồng Kông đã xây dựng bộ font DFSongLight_Vietnam2.ttf c ng cho 9.299 chữ Nôm này. Nhóm Đạo Uyển (Đỗ Quốc Bảo (Đức) và Thiền viện Viên Chiếu) đã phát triển bộ font HanNom (trên 30.000 chữ) có thể sử dụng trên triển bộ phông đầy đủ True Type mạng. Nhóm Nôm Na đã phát NomNaTongLight.ttf (trên 15.000 chữ).

Đến năm 2000, trong phiên bản 11.1, tổng số chữ đƣợc lựa chọn và cấp mã Unicode là 70.205 chữ (trong đó có 9.229 chữ do Việt Nam đề nghị, nếu trừ đi số chữ trùng lặp thì có 4.232 chữ Nôm Việt tự tạo). Tổng số chữ trên nằm trong 2 tập Extension A và Extension B. Tập Extension C đang biên soạn sẽ có thêm khoảng 2.300 chữ Nôm tự tạo nữa (trong đó sẽ có gần 400 chữ Nôm Tày

tự tạo). Vậy nếu tính cả 3 tập Extension A, B, C, thì tổng số mã Unicode dành cho chữ Nôm Việt (tự tạo) là khoảng 6150 chữ.

Vấn đề về phần mềm hỗ trợ khai thác và sử dụng chữ Nôm đã phát triển phần mềm tra cứu chữ Nôm NLT đƣợc sử dụng rộng rãi trên mạng cả trong nƣớc và trên thế giới. Các phần mềm gõ chữ Nôm và phần mềm từ điển đã đƣợc một số nhóm chuyên gia tin học trong nƣớc phát triển: các nhóm của Phan Anh D ng (Huế) và Tống Phƣớc Khải-Lê Anh Minh (TP Hồ Chí Minh).

Về việc in ấn đã thực hiện việc in ấn chữ Nôm từ máy tính cho một số bộ từ điển chữ Nôm. Nhiều tác phẩm chữ Nôm đã và đang đƣợc in ấn trực tiếp từ máy tính và tra cứu trên mạng.

1.4 Mô hình nhận dạng tổng thể và phạm vi nghiên cứu

Xây dựng phần mềm nhận dạng chữ Nôm (Nôm-OCR) là một yêu cầu tất yếu nhƣ với các ngôn ngữ khác. Nôm-OCR sẽ đóng vai trò một động lực mạnh thúc đẩy việc nghiên cứu chữ Nôm, khai phá nguồn tƣ liệu quý giá của dân tộc hàng ngàn năm về chính trị, văn hóa, xã hội… Hệ thống nhận dạng chữ Nôm về mặt kỹ thuật có thể tham khảo các mô hình kỹ thuật của các OCR hác, đặc biệt là các OCR chữ tƣợng hình nhƣ tiếng Hán, tiếng Nhật. Trên cơ sở nghiên cứu các mô hình về OCR, nhóm nghiên cứu của tác giả đƣa ra mô tổng thể cho bài toán nhận dạng chữ Nôm nhƣ hình 1.1. [2]

Hình 1.1 Mô hình nhận dạng chữ Hán - Nôm

Trong sơ đồ trên, nguồn tài liệu có thể là ảnh, tệp PDF…. Trong nguồn đầu vào của hệ thống OCR có thể bao gồm nhiều loại thông tin ví dụ hình ảnh, các loại ngôn ngữ hác nhau. Do đó, cần đƣợc tiến hành thao tác phân tích trang, nhận diện phần ký tự. Sau khi tách phần ký tự khỏi trang, ta tiến hành các bƣớc tiền xử lý cần thiết, tách thành các khối, tách các khối thành các dòng, tách dòng thành các ký tự rời rạc. Từ các ký tự rời rạc, ta tiến hành trích chọn đặc trƣng của ký tự để đƣa vào tiến hành nhận dạng. Kết quả của bƣớc nhận dạng có thể chƣa phải là bƣớc cuối cùng, mà sẽ đƣợc qua bƣớc hậu xử lý, có thể kiểm tra trên cơ sở từ điển, ngữ pháp… để quyết định kết quả cuối cùng.

Tổng kết chƣơng 1

Chƣơng 1 đã trình bày tổng quan về chữ Nôm, từ lịch sử ra đời tới đặc điểm cấu tạo của chữ, tình hình nghiên cứu về chữ Hán-Nôm và bài toán nhận dạng chữ Nôm. Mặc dù đƣợc hình thành trên cơ sở là chữ Hán nhƣng chữ Nôm phức tạp hơn rất nhiều do ông cha ta không chỉ mƣợn âm và nghĩa của chữ Hán mà đã thay đổi rất nhiều về cấu trúc, tạo ra các chữ nhiều nét hơn. Do đó cần thiết phải xây dựng bộ nhận dạng mới cho chữ Nôm trên cơ sở nghiên cứu các kỹ thuật nhận dạng chữ Hán c ng nhƣ các chữ tƣợng hình khác.

Chƣơng 2. MẠNG NƠ-RON

2.1 Nơ-ron sinh học

Theo các nhà nghiên cứu sinh học về bộ não, hệ thống thần kinh của con ngƣời bao gồm khoảng 100 tỷ tế bào thần inh, thƣờng gọi là các nơ-ron. Mỗi tế bào nơ-ron gồm ba phần:

- Thân nơ-ron với nhân bên trong (gọi là soma), là nơi tiếp nhận hay phát ra

các xung động thần kinh.

- Một hệ thống dạng cây các dây thần kinh vào (gọi là dendrite) để đƣa tín hiệu tới nhân nơ-ron. Các dây thần kinh vào tạo thành một lƣới dày đặc xung quanh thân nơ-ron, chiếm diện tích khoảng 0,25 mm2.

- Đầu dây thần kinh ra (gọi là sợi trục axon) phân nhánh dạng hình cây, có thể dài từ một cm đến hàng mét. Chúng nối với các dây thần kinh vào hoặc trực tiếp với nhân tế bào của các nơ-ron khác thông qua các khớp nối (gọi là synapse). Thông thƣờng mỗi nơ-ron có thể có từ vài chục cho tới hàng trăm ngàn khớp nối để nối với các nơ-ron khác. Có hai loại khớp nối, khớp nối kích thích (excitatory) sẽ cho tín hiệu qua nó để tới nơ-ron còn khớp nối ức chế (inhibitory) có tác dụng làm cản tín hiệu tới nơ-ron. Ngƣời ta ƣớc tính mỗi nơ- ron trong bộ não của con ngƣời có khoảng 104 khớp nối (hình 2.1).

Chức năng cơ bản của các tế bào nơ-ron là liên kết với nhau để tạo nên hệ thống thần inh điều khiển hoạt động của cơ thể sống. Các tế bào nơ-ron truyền tín hiệu cho nhau thông qua các dây thần kinh vào và ra, các tín hiệu đó có dạng xung điện và đƣợc tạo ra từ các quá trình phản ứng hoá học phức tạp. Tại nhân tế bào, hi điện thế của tín hiệu vào đạt tới một ngƣỡng nào đó thì nó sẽ tạo ra một xung điện dẫn tới trục dây thần kinh ra. Xung này truyền theo trục ra tới các nhánh rẽ và tiếp tục truyền tới các nơ-ron khác.

Hình 2.1 Cấu tạo của tế bào nơ-ron sinh học

Nhƣ vậy nơ-ron sinh học hoạt động theo cách thức sau: nhận tín hiệu đầu vào, xử lý các tín hiệu này và cho ra một tín hiệu output. Tín hiệu output này sau đó đƣợc truyền đi làm tín hiệu đầu vào cho các nơ-ron khác. Dựa trên những hiểu biết về nơ-ron sinh học, con ngƣời xây dựng nơ-ron nhân tạo với hy vọng tạo nên một mô hình có sức mạnh nhƣ bộ não.

2.2 Mạng nơ-ron nhân tạo

Định nghĩa: Mạng nơ-ron nhân tạo (Artificial Neural Network-ANN)gọi tắt là mạng nơ-ron (neural network), là một mô hình xử lý thông tin phỏng theo cách thức xử lý thông tin của các hệ nơ-ron sinh họcvới mong muốn có thể thực hiện đƣợc những nhiệm vụ thông minh nhƣ bộ não của con ngƣời. Nó đƣợc tạo nên từ một số lƣợng lớn các phần tử (gọi là phần tử xử lý hay nơ-ron) kết nối với nhau thông qua các liên kết (gọi là trọng số liên kết) làm việc nhƣ một thể thống nhất để giải quyết một vấn đề cụ thể nào đó.

Một mạng nơ-ron nhân tạo đƣợc cấu hình cho một ứng dụng cụ thể (nhận dạng mẫu, phân loại dữ liệu,...) thông qua một quá trình học từ tập các mẫu huấn luyện. Về bản chất học chính là quá trình hiệu chỉnh trọng số liên kết giữa các nơ-ron.

Cấu trúc: Cấu trúc của một mạng nơ-ron đƣợc mô tả trên hình 2.2

Hình 2.2 Nơ-ron nhân tạo

- Tập các đầu vào: Là các tín hiệu vào (input signals) của mạng, các tín

hiệu này thƣờng đƣợc đƣa vào dƣới dạng một vector N chiều.

- Tập các liên kết: Mỗi liên kết đƣợc thể hiện bởi một trọng số (gọi là trọng số liên kết – Synaptic weight). Trọng số liên kết giữa tín hiệu vào thứ j với nơ- . Thông thƣờng, các trọng số này đƣợc khởi tạo ron thƣờng đƣợc kí hiệu là w kj

một cách ngẫu nhiên ở thời điểm khởi tạo mạng và đƣợc cập nhật liên tục trong quá trình học mạng.

- Hàm tổng(Summing function): Thƣờng dùng để tính tổng của tích các đầu

vào với trọng số liên kết của nó.

- Ngƣỡng: Ngƣỡng này thƣờng đƣợc đƣa vào nhƣ một thành phần của hàm

truyền.

- Hàm truyền (Transfer function) : Hàm này đƣợc dùng để giới hạn phạm vi đầu ra của mỗi nơ-ron. Nó nhận đầu vào là kết quả của hàm tổng và ngƣỡng đã cho. Thông thƣờng, phạm vi đầu ra của mỗi nơ-ron đƣợc giới hạn trong đoạn [0,1] hoặc [-1, 1]. Các hàm truyền rất đa dạng, có thể là các hàm tuyến tính hoặc phi tuyến. Việc lựa chọn hàm truyền nào là tuỳ thuộc vào từng bài toán và kinh nghiệm của ngƣời thiết kế mạng. Một số hàm truyền thƣờng sử dụng trong các mô hình mạng nơ-ron đƣợc đƣa ra trong bảng 2.1.

- Đầu ra: Là tín hiệu đầu ra của một nơ-ron, với mỗi nơ-ron sẽ có tối đa là

một đầu ra.

Bảng 2.1 Một số hàm truyền thông dụng

Hàm tru ền Đồ thị Định nghĩa

Symmetrical Hard Limit (hardlims)

Linear (purelin) y=x

Saturating Linear (satlin)

với λ>0 Log-Sigmoid (logsig)

Mạng nơ-ron có hả năng rút ra ý nghĩa từ dữ liệu phức tạp hoặc không chính xác, có thể đƣợc sử dụng để trích xuất các mẫu và phát hiện ra các xu hƣớng quá phức tạp. Một mạng lƣới thần inh đƣợc đào tạo có thể đƣợc coi nhƣ một "chuyên gia" trong danh mục của thông tin đã đƣợc đƣa ra để phân tích. Chuyên gia này sau đó có thể đƣợc sử dụng để cung cấp dự đoán của tình hình mới. Ngoài ra mạng nơ-ron còn có hả năng:

- daptive learning (học thích nghi): có thể biết đƣợc làm thế nào để thực hiện nhiệm vụ dựa trên các dữ liệu đƣa ra cho đào tạo hoặc từ inh nghiệm ban đầu.

- Self-Organization (Tự tổ chức): Một ANN có thể tạo ra các tổ chức của mình hoặc đại diện của các thông tin mà nó nhận đƣợc trong suốt thời gian học tập.

- Real Time Operation (hoạt động thời gian thực): hệ thống sử dụng NN có thể đƣợc thực hiện song song với các thiết bị phần cứng đặc biệt đƣợc thiết kế và sản xuất mà tận dụng khả năng này.

- Fault Tolerance via Redundant Information Coding (Dung sai lỗi thông qua thông tin dự phòng): sự phá hủy từng phần của một mạng dẫn đến sự suy thoái tƣơng ứng về hiệu suất. Tuy nhiên, một số khả năng của mạng có thể đƣợc giữ lại ngay cả với những thiệt hại mạng lớn.

Ứng dụng: mạng nơ-ron ngày càng đƣợc ứng dụng nhiều trong thực tế. Đặc biệt là các bài toán nhận dạng mẫu, xử lý, lọc dữ liệu, và điều khiển. Ứng dụng của mạng nơ-ron đƣợc chia thành các loại sau:

- Xử lý ngôn ngữ

o Xử lý ngôn ngữ tự nhiên

- Nhận dạng mẫu

o Nhận dạng ảnh

o Nhận giọng nói

o Nhận dạng chữ viết

- Xử lý tín hiệu

o Điều khiển tự động

- Lọc và phân loại dữ liệu

o Chuẩn đoán bệnh

o Tìm kiếm

2.3 Các kiểu mô hình mạng Nơ-ron

Cách thức kết nối các nơ-ron trong mạng xác định kiến trúc (topology) của mạng. Các nơ-ron trong mạng có thể kết nối đầy đủ (fully connected) tức là mỗi nơ-ron đều đƣợc kết nối với tất cả các nơ-ron khác, hoặc kết nối cục bộ

(partially connected) chẳng hạn chỉ kết nối giữa các nơ-ron trong các tầng khác nhau. Ngƣời ta chia ra hai loại kiến trúc mạng chính:

- Tự kết hợp (autoassociative): là mạng có các nơ-ron đầu vào c ng là các nơ-ron đầu ra. Mạng Hopfield là một kiểu mạng tự kết hợp(Hình 2.3).

Hình 2.3 Mạng tự kết hợp

- Kết hợp khác kiểu (heteroassociative): là mạng có tập nơ-ron đầu vào và đầu ra riêng biệt. Perceptron, các mạng Perceptron nhiều tầng (MLP: MultiLayer Perceptron), mạng Kohonen, … thuộc loại này(hình 2.4).

Hình 2.4 Mạng kết hợp khác kiểu

Ngoài ra tùy thuộc vào mạng có các kết nối ngƣợc (feedback connections) từ các nơ-ron đầu ra tới các nơ-ron đầu vào hay hông, ngƣời ta chia ra làm 2 loại kiến trúc mạng.

- Mạng truyền thẳng (feedforward architechture): là kiểu kiến trúc mạng không có các kết nối ngƣợc trở lại từ các nơ-ron đầu ra về các nơ-ron đầu vào; mạng hông lƣu lại các giá trị output trƣớc và các trạng thái kích hoạt của nơ-ron. Các mạng nơ-ron truyền thẳng cho phép tín hiệu di chuyển theo một đƣờng duy nhất; từ đầu vào tới đầu ra, đầu ra của một

tầng bất kì sẽ không ảnh hƣởng tới tầng đó. Các mạng kiểu Perceptron là mạng truyền thẳng(Hình 2.5).

Hình 2.5 Mạng truyền thẳng

- Mạng hồi quy (Feedback architecture): là kiểu kiến trúc mạng có các kết nối từ nơ-ron đầu ra tới nơ-ron đầu vào. Mạng lƣu lại các trạng thái trƣớc đó, và trạng thái tiếptheo không chỉ phụ thuộc vào các tín hiệu đầu vào mà còn phụ thuộc vào các trạng thái trƣớc đó của mạng. Mạng Hopfield thuộc loại này(Hình 2.6).

Hình 2.6 Mạng hồi quy

2.4 Huấn lu ện và xâ dựng mạng Nơ-ron

2.4.1 Các phương pháp học

Khái niệm: Học là quá trình thay đổi hành vi của các vật theo một cách

nào đó làm cho chúng có thể thực hiện tốt hơn trong tƣơng lai.

Một mạng nơ-ron đƣợc huyấn luyện sao cho với một tập các vector đầu vào X, mạng có khả năng tạo ra tập các vector đầu ra mong muốn Y của nó. Tập X đƣợc sử dụng cho huấn luyện mạng đƣợc gọi là tập huấn luyện (training set). Các phần tử x thuộc X đƣợc gọi là các mẫu huấn luyện (training example). Quá trình huấn luyện bản chất là sự thay đổi các trọng số liên kết của mạng. Trong quá trình này, các trọng số của mạng sẽ hội tụ dần tới các giá trị sao cho với mỗi

vector đầu vào x từ tập huấn luyện, mạng sẽ cho ra vector đầu ra y nhƣ mong muốn

Có ba phƣơng pháp học phổ biến là học có giám sát (supervised learning), học không giám sát (unsupervised learning) và học tăng cƣờng (Reinforcement learning):

- Học có giám sát: Là quá trình học có sự tham gia giám sát của một “thầy

x R

K ]}, ) là vector đặc trƣng N chiều của mẫu huấn luyện và t N

giáo”. Tập mẫu huấn luyện đƣợc cho dƣới dạng D = {(x,t) | (x,t) ∈ [IR trong đó: x = (x , ..., x , x

= (t , t , ..., t ) là vector mục tiêu K chiều tƣơng ứng, nhiệm vụ của thuật toán là K

phải thiết lập đƣợc một cách tính toán trên mạng nhƣ thế nào đó để sao cho với mỗi vector đặc trƣng đầu vào thì sai số giữa giá trị đầu ra thực sự của mạng và giá trị mục tiêu tƣơng ứng là nhỏ nhất. Chẳng hạn mạng có thể học để xấp xỉ một hàm t = f(x) biểu diễn mối quan hệ trên tập các mẫu huấn luyện (x, t).

Nhƣ vậy với học có giám sát, số lớp cần phân loại đã đƣợc biết trƣớc. Nhiệm vụ của thuật toán là phải xác định đƣợc một cách thức phân lớp sao cho với mỗi vector đầu vào sẽ đƣợc phân loại chính xác vào lớp của nó.

Học có giám sát trong các mạng nơ-ron thƣờng đƣợc thực hiện theo các

bƣớc sau:

o B1: Xây dựng cấu trúc thích hợp cho mạng nơ-ron, chẳng hạn có (n + 1) nơ-ron vào (n nơ-ron cho biến vào và 1 nơ-ron cho ngƣỡng x0), m nơ-ron đầu ra, và khởi tạo các trọng số liên kết của mạng.

o B2: Đƣa một vector x trong tập mẫu huấn luyện X vào mạng

o B3: Tính vector đầu ra o của mạng

o B4: So sánh vector đầu ra mong muốn y (là kết quả đƣợc cho trong tập huấn luyện) với vector đầu ra o do mạng tạo ra; nếu có thể thì đánh giá lỗi.

o B5: Hiệu chỉnh các trọng số liên kết theo một cách nào đó sao cho ở lần tiếp theo hi đƣa vector x vào mạng, vector đầu ra o sẽ giống với y hơn. o B6: Nếu cần, lặp lại các bƣớc từ 2 đến 5 cho tới khi mạng đạt tới trạng

thái hội tụ.

Việc đánh giá lỗi có thể thực hiện theo nhiều cách, cách dùng nhiều nhất là sử dụng lỗi tức thời: Err = (o - y), hoặc Err = |o - y|; lỗi trung bình bình phƣơng (MSE: mean-square error): Err = (o- y)2/2;

Có hai loại lỗi trong đánh giá một mạng nơ-ron. Thứ nhất, gọi là lỗi rõ ràng (apparent error), đánh giá hả năng xấp xỉ các mẫu huấn luyện của một mạng đã đƣợc huấn luyện. Thứ hai, gọi là lỗi kiểm tra (test error), đánh giá hả năng tổng quá hóa của một mạng đã đƣợc huấn luyện, tức khả năng phản ứng với các vector đầu vào mới. Để đánh giá lỗi kiểm tra chúng ta phải biết đầu ra mong muốn cho các mẫu kiểm tra.

Thuật toán tổng quát ở trên cho học có giám sát trong các mạng nơ-ron có nhiều cài đặt khác nhau, sự khác nhau chủ yếu là cách các trọng số liên kết đƣợc thay đổi trong suốt thời gian học. Trong đó tiêu biểu nhất là thuật toán lan truyền ngƣợc.

- Học không giám sát: Là việc học không cần có bất kỳ một sự giám sát

nào.

, ..., x , ..., x , x dạng: D = {(x Trong bài toán học không giám sát, tập dữ liệu huấn luyện đƣợc cho dƣới ) là vector đặc trƣng của mẫu huấn N )}, với (x 1 N , x 2

luyện. Nhiệm vụ của thuật toán là phải phân chia tập dữ liệu D thành các nhóm con, mỗi nhóm chứa các vector đầu vào có đặc trƣng giống nhau.

Nhƣ vậy với học không giám sát, số lớp phân loại chƣa đƣợc biết trƣớc, và tùy theo tiêu chuẩn đánh giá độ tương tự giữa các mẫu mà ta có thể có các lớp phân loại khác nhau.

- Học tăng cƣờng: đôi hi còn đƣợc gọi là học thƣởng-phạt (reward- penalty learning), là sự tổ hợp của cả hai mô hình trên. Phƣơng pháp này cụ thể nhƣ sau: với vector đầu vào, quan sát vector đầu ra do mạng tính đƣợc. Nếu kết quả đƣợc xem là “tốt” thì mạng sẽ đƣợc thƣởng theo nghĩa tăng các trọng số kết nối lên; ngƣợc lại mạng sẽ bị phạt, các trọng số kết nối không thích hợp sẽ đƣợc giảm xuống. Do đó học tăng cƣờng là học theo nhà phê bình (critic), ngƣợc với học có giám sát là học theo thầy giáo (teacher).

2.4.2 Các vấn đề trong xây dựng mạng nơ-ron

Mặc dù, về mặt lý thuyết, có tồn tại một mạng có thể mô phỏng một bài toán với độ chính xác bất ỳ. Tuy nhiên, để có thể tìm ra mạng này hông phải là điều đơn giản. Để định nghĩa chính xác một iến trúc mạng nhƣ: cần sử dụng bao nhiêu lớp ẩn, mỗi lớp ẩn cần có bao nhiêu đơn vị xử lý cho một bài toán cụ thể là một công việc hết sức hó hăn.

Dƣới đây trình bày một số vấn đề cần quan tâm hi ta thiết ế một mạng.

a. Chuẩn bị dữ liệu

Kích thƣớc mẫu: Không có nguyên tắc nào hƣớng dẫn ích thƣớc mẫu phải là bao nhiêu đối với một bài toán cho trƣớc. Hai yếu tố quan trọng ảnh hƣởng đến ích thƣớc mẫu:

o Dạng hàm đích: hi hàm đích càng phức tạp thì ích thƣớc mẫu cần càng

lớn.

o Nhiễu: khi dữ liệu bị nhiễu(thông tin sai hoặc thiếu thông tin) thì kích

thƣớc mẫu cần tăng.

Đối với mạng truyền thẳng (feedforward), cho hàm đích có độ phức tạp nhất định, kèm một lƣợng nhiễu nhất định thì độ chính xác của mô hình luôn có một giới hạn nhất định.Có thể cần tập mẫu vô hạn để đạt đến giới hạn chính xác. Nói cách hác độ chính xác của mô hình là hàm theo ích thƣớc tập mẫu. Khi kích thƣớc mẫu tăng, độ chính xác sẽ đƣợc cải thiện - lúc đầu nhanh, nhƣng chậm dần khi tiến đến giới hạn.

Dạng tổng quát của mối liên hệ giữa sai số và ích thƣớc mẫu nhƣ hình

2.7:

Hình 2.7 Mối liên hệ giữa sai số và kích thƣớc mẫu

Trong thực hành thƣờng gặp phải 2 vấn đề sau:

o Đối với hầu hết bài toán thực tế, mẫu bị ràng buộc chặt chẽ với dữ liệu có

sẵn. Ta thƣờng hông có đƣợc số lƣợng mẫu mong muốn.

o Kích thƣớc mẫu c ng có thể bị giới hạn bởi bộ nhớ hoặc khả năng lƣu trữ của máy tính. Nếu tất cả các dữ liệu đồng thời đƣợc giữ trong bộ nhớ suốt thời gian luyện, ích thƣớc bộ nhớ máy tính sẽ bị chiếm dụng nghiêm trọng.

Nếu lƣu trữ trên đĩa sẽ cho phép dùng mẫu lớn hơn nhƣng thao tác đọc đĩa

từ thế hệ này sang thế hệ khác khiến cho tiến trình chậm đi rất nhiều.

Chú ý: việc tăng ích thƣớc mẫu hông làm tăng thời gian luyện. Những tập mẫu lớn hơn sẽ yêu cầu ít thế hệ luyện hơn. Nếu ta tăng gấp đôi ích thƣớc của mẫu, mỗi thế hệ luyện sẽ tốn thời gian khoảng gấp đôi, nhƣng số thế hệ cần luyện sẽ giảm đi một nửa. Điều này có nghĩa là ích thƣớc mẫu (c ng có nghĩa là độ chính xác của mô hình) không bị giới hạn bởi thời gian luyện.

Luật cơ bản là: Sử dụng mẫu lớn nhất có thể sao cho đủ khả năng lƣu trữ trong bộ nhớ trong (nếu lƣu trữ đồng thời) hoặc trên đĩa từ (nếu đủ thời gian đọc từ đĩa).

Chọn biến: Khi tạo mẫu cần chọn các biến sử dụng trong mô hình. Có 2

vấn đề cần quan tâm:

o Thứ nhất: Cần tìm hiểu cách biến đổi thông tin sao cho có lợi cho mạng hơn: thông tin trƣớc hi đƣa vào mạng cần đƣợc biến đổi ở dạng thích hợp nhất, để mạng đạt đƣợc hiệu xuất cao nhất. Xét ví dụ về bài toán dự đoán một ngƣời có mắc bệnh ung thƣ hay hông. Khi đó ta có trƣờng thông tin về ngƣời này là “ngày tháng năm sinh”. Mạng sẽ đạt đƣợc hiệu quả cao hơn khi ta biến đổi trƣờng thông tin này sang thành “tuổi”. Thậm chí ta có thể quy tuổi về một trong các giá trị: 1 = “tr em” (dƣới 18), 2 = “thanh niên” (từ 18 đến dƣới 30), 3 = “trung niên” (từ 30 đến dƣới 60) và 4 = “già” (từ 60 trở lên).

o Thứ hai: Cần chọn trong số các biến đã đƣợc biến đổi biến nào sẽ đƣợc đƣa vào mô hình: hông phải bất kì thông tin nào về mẫu c ng có lợi cho mạng. Trong ví dụ dự đoán ngƣời có bị ung thƣ hay hông ở trên, những thuộc tính nhƣ “nghề nghiệp”, “nơi sinh sống”, “tiểu sử gia đình”,… là những thông tin có ích. Tuy nhiên những thông tin nhƣ “thu nhập”, “số con cái”, … là những thông tin không cần thiết.

b. Xác định tham số

Chọn hàm truyền: Không phải bất kỳ hàm truyền nào c ng cho ết quả nhƣ mong muốn. Để trả lời cho câu hỏi: “Hàm truyền như thế nào được coi là tốt?” là điều không hề đơn giản. Có một số quy tắc khi chọn hàm truyền nhƣ sau:

o Không dùng hàm truyền tuyến tính ở tầng ẩn. Vì nếu dùng hàm truyền tuyến tính ở tầng ẩn thì sẽ làm mất vai trò của tầng ẩn đó: Xét tầng ẩn thứ i:

Tổng trọng số ni = wiai-1+ bi

ai = f(ni) = wf ni +bf (hàm truyền tuyến tính)

Khi đó: tổng trọng số tại tầng thứ (i + 1)

ni+1= wi+1ai + bi+1

= wi+1[wf ni +bf] + bi+1

= wi+1[wf(wiai-1+ bi) + bf] + bi+1

= Wai-1+ b

Nhƣ vậy ni+1= Wai-1+ b, và tầng i đã hông còn giá trị nữa.

o Chọn các hàm truyền sao cho kiến trúc mạng nơ-ron là đối xứng (tức là với đầu vào ngẫu nhiên thì đầu ra có phân bố đối xứng). Nếu một mạng nơ-ron hông đối xứng thì giá trị đầu ra sẽ lệch sang một bên, không phân tán lên toàn bộ miền giá trị của output. Điều này có thể làm cho mạng rơi vào trạng thái bão hòa, hông thoát ra đƣợc.

Trong thực tế ngƣời ta thƣờng sử dụng các hàm truyền dạng – S. Một hàm

s(u) đƣợc gọi là hàm truyền dạng – S nếu nó thỏa mãn 3 tính chất sau:

– s(u) là hàm bị chặn: tức là tồn tại các hằng số C1 ≤ C2 sao cho:

C1 ≤ s(u) ≤ C2 với mọi u.

– s(u) là hàm đơn điệu tăng: giá trị của s(u) luôn tăng hi u tăng. Do tính chất thứ nhất, s(u) bị chặn, nên s(u) sẽ tiệm cận tới giá trị cận trên khi u dần tới dƣơng vô cùng, và tiệm cận giá trị cận dƣới khi u dần tới âm vô cùng.

– s(u) là hàm khả vi: tức là s(u) liên tục và có đạo hàm trên toàn trục số.

Một hàm truyền dạng - S điển hình và đƣợc áp dụng rộng rãi là hàm

Sigmoid.

Xác định số nơ-ron tầng ẩn :

Câu hỏi chọn số lƣợng noron trong tầng ẩn của một mạng MLP thế nào là khó, nó phụ thuộc vào bài toán cụ thể và vào kinh nghiệm của nhà thiết kế mạng. Nếu tập dữ liệu huấn luyện đƣợc chia thành các nhóm với các đặc tính tƣơng tự nhau thì số lƣợng các nhóm này có thể đƣợc sử dụng để chọn số lƣợng

nơ-ron ẩn. Trong trƣờng hợp dữ liệu huấn luyện nằm rải rác và không chứa các đặc tính chung, số lƣợng kết nối có thể gần bằng với số lƣợng các mẫu huấn luyện để mạng có thể hội tụ. Có nhiều đề nghị cho việc chọn số lƣợng nơ-ron tầng ẩn h trong một mạng MLP. Chẳng hạn h phải thỏa mãn h > (p1)/(n+2), trong đó p là số lƣợng mẫu huấn luyện và n là số lƣợng đầu vào của mạng. Càng nhiều nút ẩn trong mạng, thì càng nhiều đặc tính của dữ liệu huấn luyện sẽ đƣợc mạng nắm bắt, nhƣng thời gian học sẽ càng tăng.

Một kinh nghiệm khác cho việc chọn số lƣợng nút ẩn là số lƣợng nút ẩn bằng với số tối ƣu các cụm mờ(fuzzy clusters). Phát biểu này đã đƣợc chứng minh bằng thực nghiệm. Việc chọn số tầng ẩn c ng là một nhiệm vụ khó. Rất nhiều bài toán đòi hỏi nhiều hơn một tầng ẩn để có thể giải quyết tốt.

Để tìm ra mô hình mạng nơ-ron tốt nhất, Ishikawa and Moriyama (1995) sử dụng học cấu trúc có quên (structural leanrning with forgetting), tức là trong thời gian học cắt bỏ đi các liên ết có trọng số nhỏ. Sau khi huấn luyện, chỉ các noron có đóng góp vào giải quyết bài toán mới đƣợc giữ lại, chúng sẽ tạo nên bộ xƣơng cho mô hình mạng nơ-ron.

Khởi tạo trọng số :

Trọng số thƣờng đƣợc khởi tạo bằng phƣơng pháp thử sai, nó mang tính chất kinh nghiệm và phụ thuộc vào từng bài toán. Việc định nghĩ thế nào là một bộ trọng sốtốt c ng hông hề đơn giản. Một số quy tắc khi khởi tạo trọng số:

o Khởi tạo trọng số sao cho mạng nơ-ron thu đƣợc là cân bằng (với đầu vào ngẫu nhiên thì sai số lan truyền ngƣợc cho các ma trận trọng số là xấp xỉ bằng nhau):

|ΔW1/W1| = |ΔW2/W2| = |ΔW3/W3|

Nếu mạng nơ-ron không cân bằng thì quá trình thay đổi trọng số ở một số ma trận là rất nhanh trong khi ở một số ma trận khác lại rất chậm, thậm chí hông đáng ể. Do đó để các ma trận này đạt tới giá trị tối ƣu sẽ mất rất nhiều thời gian.

o Tạo trọng số sao cho giá trị kết xuất của các nút có giá trị trung gian. (0.5 nếu hàm truyền là hàm Sigmoid). Rõ ràng nếu ta không biết gì về giá trị kết xuất thì giá trị ở giữa là hợp lý. Điều này c ng giúp ta tránh đƣợc các giá trị thái quá.

Thủ tục khởi tạo trọng thƣờng đƣợc áp dụng:

B1: Khởi tạo các trọng số nút ẩn (và các trọng số của các cung liên kết trực tiếp giữa nút nhập và nút xuất, nếu có) giá trị ngẫu nhiên, nhỏ, phân bố đều quanh 0.

B2: Khởi tạo một nửa số trọng số của nút xuất có giá trị là 1, và nửa kia có giá trị là -1.

2.5 Đánh giá các nhân tố của quá trình học

2.5.1 Khởi tạo các trọng số

Kỹ thuật lan truyền ngƣợc hội tụ đến một giải pháp mà nó tối thiểu hoá đƣợc sai số trung bình bình phƣơng vì cách thức hiệu chỉnh trọng số và hệ số bias của thuật toán là ngƣợc hƣớng với vectơ Gradient của hàm sai số trung bình bình phƣơng đối với trọng số. Tuy nhiên, đối với mạng MLP thì hàm sai số trung bình bình phƣơng thƣờng phức tạp và có nhiều cực trị cục bộ, vì thế các phép lặp huấn luyện mạng có thể chỉ đạt đƣợc đến cực trị cục bộ của hàm sai số trung bình bình phƣơng mà hông đạt đến đƣợc cực trị tổng thể. Các giá trị khởi tạo của các trọng số ảnh hƣởng rất mạnh đến lời giải cuối cùng. Các trọng số này thƣờng đƣợc khởi tạo bằng những số ngẫu nhiên nhỏ. Việc khởi tạo tất cả các trọng số bằng nhau sẽ làm cho mạng học không tốt. Nếu các trọng số đƣợc khởi tạo với giá trị lớn thì ngay từ đầu tổng tín hiệu vào đã có giá trị tuyệt đối lớn và làm cho hàm sigmoid chỉ đạt 2 giá trị 0 và 1. Điều này làm cho hệ thống sẽ bị tắc ngay tại một cực tiểu cục bộ hoặc tại một vùng bằng phẳng nào đó gần ngay tại điểm xuất phát. Giá trị khởi tạo ban đầu của các trọng số trên lớp thứ l của mạng sẽ đƣợc chọn ngẫu nhiên nhỏ trong khoảng [-1/n, 1/n], trong đó n là số trọng số nối tới lớp l. Do bản chất của giải thuật học lan truyền ngƣợc sai số là phƣơng pháp giảm độ lệch gradient nên việc khởi tạo các giá trị ban đầu của các trọng số các giá trị nhỏ ngẫu nhiên sẽ làm cho mạng hội tụ về các giá trị cực tiểu khác nhau. Nếu gặp may thì mạng sẽ hội tụ đƣợc về giá trị cực tiểu tổng thể.

2.5.2 Bước học α

Một nhân tố khác ảnh hƣởng đến hiệu lực và độ hội tụ của giải thuật lan truyền ngƣợc sai số là bƣớc học α. Không có một giá trị xác định nào cho các bài toán khác nhau. Với mỗi bài toán, bƣớc học thƣờng đƣợc lựa chọn bằng thực nghiệm theo phƣơng pháp thử và sai. Giá trị α lớn làm tăng tốc quá trình hội tụ.

Điều này không phải lúc nào c ng có lợi vì nếu ngay từ đầu ta đã cho là mạng nhanh hội tụ thì rất có thể mạng sẽ hội tụ sớm ngay tại một cực tiểu địa phƣơng gần nhất mà hông đạt đƣợc độ sai số nhƣ mong muốn. Tuy nhiên, đặt giá trị bƣớc học quá nhỏ thì mạng sẽ hội tụ rất chậm, thậm chí mạng có thể vƣợt

đƣợc qua các cực tiểu cục bộ và vì vậy dẫn đến học mãi mà không hội tụ. Do vậy, việc chọn hằng số học ban đầu là rất quan trọng. Với mỗi bài toán ta lại có phƣơng án chọn hệ số học khác nhau. Nhƣ vậy, khi một quá trình huấn luyện theo kỹ thuật lan truyền ngƣợc hội tụ, ta chƣa thể khẳng định đƣợc nó đã hội tụ đến phƣơng án tối ƣu. Ta cần phải thử với một số điều kiện ban đầu để đảm bảo thu đƣợc phƣơng án tối ƣu.

2.5.3 Hằng số quán tính

Tốc độ học của giải thuật làm truyền ngƣợc sai số có thể dao động khi hằng số học lớn. Một phƣơng pháp thƣờng dùng cho phép sử dụng hằng số học lớn là thêm thành phần quán tính vào các phƣơng trình hiệu chỉnh các trọng số. Ngoài ra, hằng số quán tính ngăn cản sự thay đổi đột ngột của các trọng số theo hƣớng khác với hƣớng mà lời giải đang di chuyển đến. Mặt trái của việc sử dụng thành phần quán tính là chúng ta phải tăng đáng ể bộ nhớ của máy tính gần nhƣ gấp đôi để lƣu trữ các giá trị hiệu chỉnh ở chu kỳ trƣớc.

2.6 Một số ứng dụng của mạng Nơ-ron trong nhận dạng chữ tƣợng hình

thuật

Mạng nơ-ron đã đƣợc áp dụng thành công trong phân loại mẫu nhờ khả năng học thích nghi, phân biệt và hái quát hóa cao. Nó đã đƣợc sử dụng rộng rãi trong nghiên cứu nhận dạng chữ tƣợng hình nhƣ: Hàn Quốc [5, 12], Ấn Độ [6], Trung Quốc [7, 8], Nhật Bản [10],… Xuất phát từ nghiên cứu về mạng nơ- ron đa tầng truyền thẳng, các phƣơng pháp lấy đặc trƣng đƣợc nghiên cứu, thử nghiệm, đặc biệt là các phƣơng pháp huấn luyện mới đã cho những kết quả rất khả quan. Cụ thể: thuật toán lan truyền ngƣợc sai số cho kết quả nhận dạng là toán LVQ(Learning Vector Quantization) và 93,53% [5, 6, 9], DSM(Decision Surface Mapping) đƣợc áp dụng với chữ Trung Quốc đạt kết quả tốt nhất là 98,82% với bộ dữ liệu gồm 37000 ký tự [7], Mạng nơ-ron xác suất với cùng phƣơng pháp lấy đặc trƣng nhƣ [7] nhƣng thực hiện với 39644 ký tự Trung Quốc đạt kết quả thực nghiệm là 97,61% [8], và mạng nơ-ron thông minh tự thích nghi (structurally adaptive intelligent neural tree - SAINT) cho kết quả nhận dạng lên tới 97,5% [12].

2.6.1 Back-Propagated Neural Network [5, 6, 9]

Các mạng nơ-ron truyền thẳng rất phổ biến trong mạng nơ-ron. Nó hông có các ết nối thông tin phản hồi, nhƣng các lỗi truyền ngƣợc thƣờng xảy ra trong quá trình huấn luyện, ít nhất là các lỗi bình phƣơng. Lỗi ở đầu ra xác định lỗi ở các lớp ẩn đầu ra, chúng đƣợc sử dụng nhƣ một cơ sở để điều chỉnh trọng số ết nối giữa các lớp, quá trình này đƣợc lặp đi lặp lại cho tới hi tỉ lệ lỗi giảm

xuống dƣới một hoảng nhất định. Tham số về tốc độ học điều chỉnh các trọng số. Các thuật toán lan truyền ngƣợc (bac -propagation algorithm - BP ) đƣợc sử dụng để tính toán gradient của các hàm lỗi bằng cách sử dụng quy tắc lan truyền sự hác biệt. Các lỗi sau hi tính toán ban đầu trên đƣờng truyền sẽ đƣợc truyền ngƣợc lại từ đầu ra qua từng tầng, gọi là "bac -propagation".

Thuật toán lan truyền ngƣợc:[6]

1. Gọi A là số lƣợng đơn vị trong lớp đầu vào, đƣợc xác định bởi chiều dài của vector đào tạo đầu vào. Cho C là số lƣợng đơn vị trong lớp ra. Chọn B là số lƣợng các đơn vị trong lớp ẩn. Đầu vào lớp và ẩn từng có thêm một đơn vị đƣợc sử dụng để ngƣỡng. Chúng ta ký hiệu "cấp độ" kích hoạt của các đơn vị trong lớp đầu vào bởi xj, Trong lớp ẩn bằng các hi, và trong lớp ra bởi oj. Trọng số kết nối các lớp đầu vào cho lớp ẩn đƣợc biểu thị bằng wlij. Mỗi lớp đầu vào và lớp ẩn có thêm một đơn vị đƣợc sử dụng đó là ngƣỡng. Kí hiệu các đơn vị trong lớp đầu vào là xj, các đơn vị trong lớp ẩn là hi và trong lớp đầu ra là Oj. Trọng số ết nối lớp đầu vào với lớp ẩn là 1ij, trọng số ết nối giữa lớp ẩn và lớp đầu ra là 2ij.

2. Khởi tạo trọng số của mạng. Mỗi trọng số đƣợc thiết lập ngẫu nhiên

giữa -0.1 và 0.1.

Wlij = random (-0.1, 0.1) for all i = 0..A, j = 1..B

W2ij = ran-dom (-0.1, 0.1) for all i = 0..B, j = 1..C

3. Khởi tạo các giá trị ngƣỡng. Các giá trị ngƣỡng hông bao giờ thay

đổi.

a) Xo = 1.0

b) ho = 1.0'

4. Chọn cặp input-output. Giả sử vec tơ đầu vào là xi và vec tơ đầu ra mong muốn là yi. Đƣợc chỉ định là mức độ ích hoạt cho các đơn vị vào.

5. Truyền sự ích hoạt từ các đơn vị trong lớp đầu vào tới các đơn vị

trong lớp ẩn sử dụng hàm ích hoạt.

6. Lan truyền các kích hoạt từ các đơn vị trong lớp ẩn cho các đơn vị

trong lớp ra

7. Tính toán lỗi trong các đơn vị đầu ra δ2j, lỗi đƣợc tính dựa vào đầu ra

thực tế(oj) và đầu ra mong muốn(yj).

8. Tính toán lỗi trong các đơn vị ở tầng ẩn

9. Điều chỉnh trọng số giữa lớp ẩn và lớp đầu ra. Tốc độ học đƣợc ký

hiệu là η.

10. Điều chỉnh trọng số giữa lớp vào và lớp ẩn.

11. Quay lại bƣớc 4, lặp lại quá trình cho tất cả các cặp input-output. Nhƣ

vậy là đã hoàn thành 1 chu trình huấn luyện.

2.6.2 Mạng nơ-ron xác suất (ProbabilisticNeural Networks – PNN). [8]

Việc triển khai mạng nơ-ron xác suất với mong muốn mô hình hóa sự phân bố xác suất thực tế của các mẫu học với sự kết hợp của Gaussians. Cho phép tính toán hậu kết hợp với mỗi mẫu đƣợc phân loại.

Phƣơng pháp PNN chuẩn yêu cầu lƣu trữ của tất cả các những hình mẫu để tính toán xác suất cuối cùng của các lớp thành viên.Thay vào đó, tác giả đã sử dụng hỗn hợp Gaussian PNN của Streit và Luginbuhl để tạo ra phân phối xác suất sử dụng một số cố định của các thành phần Gaussian.Sự phân bố kết quả đƣợc hình thành qua tổng quát hóa, huấn luyện lặp đi lặp lại và ƣớc lƣợng tối đa địa phƣơng cho các lớp.

Việc huấn luyện sẽ tính toán ba bộ giá trị: các phƣơng tiện cho các thành phần của mỗi lớp, tỷ lệ kết hợp để sử dụng cho các thành phần cá nhân, và cuối

cùng là ma trận hiệp phƣơng sai. Cho là thành phần thứ i của lớp j, là tỉ lệ

kết hợp của nó, và ∑ là ma trận hiệp phƣơng sai. Khi đó, hàm mật độ xác suất kết hợp với phân loại mẫu nhƣ một thành viên của lớp đƣợc cho bởi:

Trong đó Gj là số các thành phần Gaussian đƣợc sử dụng cho mô hình lớp

j và pij (x) đƣợc định nghĩa:

Giả định rằng các chi phí liên quan đến việc lựa chọn kí tự bất kỳ là nhƣ nhau. Bằng cách lựa chọn các lớp học với hàm mật độ xác suất có giá trị cao nhất,

Bayes quyết định rủi ro tối thiểu có thể đƣợc thực hiện. Ngoài ra, xác suất xuất hiện một kí tự đƣợc ƣu tiên có thể đƣợc nhúng vào hệ thống này. Khả năng cải thiện sự phân loại sẽ phụ thuộc vào tỷ lệ sự xuất hiện các kí tự ƣu tiên cho bộ tài liệu cụ thể. Nếu tỷ lệ nhúng vào hệ thống phân loại hông tƣơng quan tốt với những lần xuất hiện ký tự đƣợc quan sát, kết quả nhận dạng có thể bị cản trở.

Huấn luyện mạng nơ-ron xác suất: Việc huyến luyện mạng đƣợc thực

hiện qua các bƣớc sau:

1) Khởi tạo giá trị cho các lớp và các thành phần. Nó đƣợc thực hiện bằng

cáh sử dụng thuật toán trung bình cho mỗi lớp. là lớp j và thành phần

i. Giá trị ƣớc lƣợng ban đầu cho các thành phần đƣợc lựa chọn ngẫu nhiên từ tập hợp các dữ liệu mẫu mực. Các mẫu đƣợc phân loại với các thành phần gần nhất của nó.

2) Mỗi đƣợc tính toán lại với từng thành phần trong tập hợp này. Thuật

toán dừng hi hông có thay đổi nào đƣợc thực hiện với .

3) Tỉ lệ kết hợp đối với mỗi thành phần đƣợc tính toán với mỗi mẫu có

trong các tập hợp i chia cho tổng số các mẫu có trong lớp j. Ma trận hiệp phƣơng sai đƣợc khởi tạo nhƣ sau:

Trong đó: N là tổng số các lớp, xjk là mẫu thứ k của lớp j.

Việc huấn luyện đƣợc bắt đầu với: Gj = G và Tj = T, một hằng số cho các

mẫu và các thành phần của tất cả các lớp.

4) Việc huấn luyện PNN đƣợc lặp lại tới bƣớc n:

5) Cập nhật tỉ lệ kết hợp:

Và các thành phần mới:

6) Tính toán lại ma trận hiệp phƣơng sai:

2.6.3 Mạng nơ-ron thông minh tự thích nghi (structurally adaptive intelligent neural tree - SAINT) [12]

Phần lớn các mạng thần inh thƣờng bị một số hó hăn nhƣ việc xác định cấu trúc và ích thƣớc của mạng, các tính toán phức tạp. Để đối phó với những hó hăn này, tác giả đã đề xuất một cấu trúc mạng nơ-ron thông minh tự thích nghi (Saint). Ý tƣởng cơ bản là phân vùng không gian mô hình phân cấp đầu vào sử dụng một mạng lƣới cấu trúc cây trong đó bao gồm các mạng con với khả năng lập bản đồ bảo toàn cấu trúc liên kết. Ƣu điểm chính của SAINT là nó cố gắng để tự động tìm kiếm một cấu trúc mạng với ích thƣớc phù hợp với việc phân loại tập mẫu lớn và phức tạp thông qua sự thích nghi cấu trúc. Kết quả thử nghiệm cho thấy SAINT rất hiệu quả trong việc phân loại ký tự viết tay với các biến thể cao, c ng nhƣ đa ngôn ngữ, multifont, và multisize bộ dữ liệu lớn.

Hình 2.8 Cấu trúc của SAINT

SAINT là một mạng nơ-ron cấu trúc cây với mạng con có cấu trúc hai chiều mạng. Để bảo toàn cấu trúc liên kết mạng của mỗi mạng con, chúng ta xem xét hệ thống láng giềng gần nhất, có thể đƣợc định nghĩa nhƣ sau.

Nút là láng giềng của i nếu và chỉ nếu:

1) i ;

2) Nếu j thì i với mọi i

Khi đó tập láng giềng gần nhất đƣợc định nghĩa nhƣ sau:

= { i } }, = { ||lj –li ||

Để thực hiện các mục tiêu đã đặt ra: thiết kế mạng nơ-ron với đầu vào phức tạp và phân loại đƣợc bộ dữ liệu lớn, thuật toán học của SAINT cần có các tính chất sau:

- Việc điều chỉnh tham số phải đƣợc thực hiện trƣớc hi điều chỉnh cấu trúc

của mạng.

- Mạng cần có các thuộc tính tƣơng ứng với mạng tổng thể.

Do đó thuật toán học của mạng nhƣ sau:

1) Khởi tạo các biến

k 1; // trong đó là số mức trong cấu trúc mạng

// Ngƣỡng để khởi tạo hay xóa một nút

0 ; // r: thứ tự của láng giềng,

2) HILE (điều kiện dừng) DO

// tốc độ học

WHILE (epoch?) DO

-Tính toán lỗi giữa input và nút ở mức cuối cùng, lựa chọn nút có lỗi tối thiểu nc với:

- Cập nhật trọng số của nút đƣợc chọn và nút láng giềng của

nó:

- Tính toán:

Trong đó: là thời gian w với ích thƣớc khởi tạo.

là lỗi ở thời điểm t

tL là thời điểm cuối cùng mà nút c đƣợc chọn

là hàm bƣớc nhảy

- tăng bộ đếm tham chiếu cho nút đƣợc chọn

- giảm ích thƣớc của láng giềng r và tốc độ học

END WHILE Xóa những nút không hoạt động trong một khoảng thời gian dài Hòa nhập những nút mà mạng con cảu nó ở cùng mức k - Lựa chọn nút Ni, Nj với điều kiện :

Trong đó và M là số nút trong mạng con

wnew = 0.5 (wi+ wj)

- Tính toán lại việc khởi tạo trọng số của nút đƣợc hòa nhập - Xóa nút Ni, Nj

Tạo mạng con với nút

Xóa

Trong đó 0 < <1

END WHILE

3) Tối ƣu mạng 4) Gắn địa chỉ các lớp vào các nút lá

Tổng kết chƣơng 2

Chƣơng này tình bày kiến thức về mạng nơ-ron, ƣu, nhƣợc điểm của mạng, đồng thời tìm hiểu các nghiên cứu ứng dụng mạng nơ-ron trong nhận dạng chữ tƣợng hình(Nhật bản, Hàn Quốc, Trung Quốc) trên thế giới. Từ đó làm cơ sở để nghiên cứu, cải tiến mạng nơ-ron để nhận dạng tốt chữ Hán-Nôm.

Chƣơng 3: GIẢI THUẬT DI TRUYỀN

3.1 Cơ sở thực tiễn của giải thuật di tru ền

Giải thuật di truyền (GA-Genetic lgorithms) c ng nhƣ các thuật toán tiến hóa nói chung, hình thành trên quan niệm cho rằng quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lí nhất và tự nó đã mang tính tối ƣu. Quan niệm này có thể đƣợc xem nhƣ một tiên đề đúng, hông chứng minh đƣợc nhƣng phù hợp với thực tế khách quan. Quá trình tiến hóa thể hiện tính tối ƣu ở chỗ: thế hệ sau bao giờ c ng tốt hơn (phát triển hơn, hoàn thiện hơn) thế hệ trƣớc. Xuyên suốt quá trình tiến hóa tự nhiên, các thế hệ mới luôn đƣợc sinh ra để bổ sung, thay thế cho thế hệ c nhờ hai quá trình cơ bản: sinh sản và chọn lọc tự nhiên, mỗi cá thể muốn tồn tại và phát triển phải thích nghi với môi trƣờng, cá thể nào thích nghi hơn thì tồn tại, cá thể nào kém thích nghi thì bị tiêu diệt.

Trong mỗi cá thể có một tập các nhiễm sắc thể (NST), mỗi NST gồm nhiều gen liên kết với nhau theo cấu trúc dạng chuỗi, quy định các tính trạng của cá thể đó. Các cá thể thuộc cùng một loài có số lƣợng và cấu trúc NST đặc trƣng nhƣng cấu trúc các gen thì hác nhau, điều đó tạo nên sự khác biệt giữa các cá thể trong cùng loài và quyết định sự sống còn của cá thể đó. Do môi trƣờng tự nhiên luôn biến đổi nên cấu trúc NST c ng thay đổi để thích nghi với môi trƣờng và thế hệ sau luôn thích nghi hơn thế hệ trƣớc. Cấu trúc này có đƣợc do sự trao đổi thông tin có tính ngẫu nhiên với môi trƣờng bên ngoài hoặc giữa các NST với nhau.

Từ ý tƣởng đó, các nhà hoa học đã nghiên cứu và xây dựng nên giải thuật di truyền dựa trên cơ sở chọn lọc tự nhiên và quy luật tiến hoá. Giải thuật di truyền mô phỏng bốn quá trình cơ bản của tự nhiên: lai ghép, đột biến, sinh sản và chọn lọc tự nhiên. Ở đây mỗi cá thể chỉ có một NST. Các NST đƣợc chia nhỏ thành các gen đƣợc sắp xếp theo một dãy tuyến tính. Mỗi cá thể (hay NST) biểu diễn một lời giải có thể của bài toán. Một xử lý tiến hoá duyệt trên tập các

NST tƣơng đƣơng với việc tìm kiếm lời giải trong không gian lời giải của bài toán. Quá trình tìm kiếm phải đạt đƣợc hai mục tiêu:

- Khai thác những lời giải tốt nhất - Xem xét trên toàn bộ không gian tìm kiếm

3.2 Cơ chế thực hiện giải thuật di tru ền

Một thuật giải di truyền (hay một chƣơng trình tiến hóa bất kỳ) để giải

một bài toán cụ thể phải bao gồm năm thành phần sau đây:

- Mã hoá lời giải - Cách biểu diễn di truyền cho lời giải của bài toán. - Cách khởi tạo quần thể ban đầu. - Một hàm lƣợng giá đóng vai trò môi trƣờng để đánh giá các lời giải theo

mức độ “thích nghi” của chúng.

- Các phép toán di truyền (chọn lọc, lai tạo, đột biến). - Các tham số hác ( ích thƣớc quần thể, xác suất áp dụng các phép toán di

truyền).

GA sẽ thực hiện tiến trình tìm kiếm lời giải tối ƣu theo nhiều hƣớng, bằng cách duy trì một quần thể các lời giải và thúc đẩy sự hình thành và trao đổi thông tin giữa các hƣớng này. Quần thể trải qua quá trình tiến hóa: ở mỗi thế hệ sẽ tạo ra các cá thể mới bằng cách lai ghép các cá thể đã có và đột biến chúng theo một xác suất nhất định. Sau đó các cá thể tƣơng đối “tốt” sẽ đƣợc giữ lại trong khi các cá thể tƣơng đối “xấu” thì chết đi, tạo ra thế hệ mới tốt hơn thế hệ trƣớc.

Cấu trúc của giải thuật di truyền đƣợc mô phỏng theo thuật toán:

Procedure Giải_thuật_di_truyền;

Begin

t:=0;

Khởi tạo ngẫu nhiên quần thể P(t);

Đánh giá độ phù hợp từng cá thể trong P(t);

Repeat

t:=t +1;

Chọn các cá thể từ P(t - 1);

Lai tạo các cá thể đã chọn tạo ra P(t) mới;

Đột biến các cá thể trong P(t) theo xác suất pm;

Đánh giá độ phù hợp các cá thể trong tập P(t);

Until (thoả điều kiện dừng);

End;

1, xt

Giải thích:

Tại lần lặp thứ t, G xác định một tập hợp các lời giải có thể (các cá thể 2,..., xt hay NST) gọi là quần thể P(t) = { xt m } (số cá thể m gọi là kích cỡ quần thể). Mỗi lời giải xt i đƣợc đánh giá nhằm xác định độ phù hợp của nó. Sau đó, một tập hợp các lời giải đƣợc hình thành nhờ sự lựa chọn các lời giải phù hợp hơn. Một số phần tử của tập hợp này đƣợc tái sản xuất thông qua lai ghép và đột biến. Từ đó hình thành quần thể mới P(t+1) với hy vọng chứa các cá thể phù hợp hơn quần thể trƣớc đó.

Nhƣ vậy, bản chất GA là một giải thuật lặp, nhằm giải quyết các bài toán tìm kiếm dựa trên cơ chế chọn lọc nhân tạo và sự tiến hoá của các gen. Trong quá trình đó, sự sống còn của cá thể phụ thuộc vào hoạt động của các NST và quá trình chọn lọc (tham gia vào việc tái tạo ra các chuỗi NST mới bằng cách giải mã các chuỗi NST và tạo ra mối liên kết giữa các NST trong các cá thể khác nhau).

GA sử dụng các toán tử: chọn lọc, lai ghép, đột biến trên các NST để tạo ra chuỗi mới. Những toán tử này thực chất là việc sao chép chuỗi, hoán vị các chuỗi con và sinh số ngẫu nhiên.

Cơ chế của G đơn giản nhƣng lại có sức mạnh hơn các giải thuật thông thƣờng khác nhờ có sự đánh giá và chọn lọc sau mỗi bƣớc thực hiện. Do vậy khả năng tiến gần đến lời giải tối ƣu của GA sẽ nhanh hơn nhiều so với các giải thuật khác.

Có thể nói GA khác với những giải thuật tối ƣu thông thƣờng ở những đặc

điểm sau:

- GA làm việc với tập mã của biến chứ không phải bản thân biến - GA thực hiện tìm kiếm trên một quần thể các cá thể chứ không phải trên một điểm nên giảm bớt khả năng ết thúc tại một điểm tối ƣu cục bộ mà không thấy tối ƣu toàn cục.

- GA chỉ cần sử dụng thông tin của hàm mục tiêu để phục vụ tìm kiếm chứ

hông đòi hỏi các thông tin hỗ trợ khác.

- Các thao tác cơ bản trong giải thuật dựa trên khả năng tích hợp ngẫu

nhiên, mang tính xác suất chứ không tiền định.

3.3 Các thành phần trong giải thuật di tru ền

Mã hoá lời giải - Biểu diễn di truyền cho lời giải của bài toán

Đây là công việc đầu tiên cần thực hiện khi giải bài toán với GA. GA làm việc với tập mã của biến chứ không phải bản thân biến, do đó hi mã hóa lời giải ta đồng thời phải tiến hành hai công việc:

- Xây dựng cấu trúc gen cho mỗi lời giải của bài toán để từ mỗi lời giải ta

có thể mã hoá thành một NST (chuỗi các gen).

- Giải mã các NST để nhận đƣợc lời giải.

Tuỳ thuộc vào đặc điểm của từng bài toán mà ta có cách mã hoá khác

nhau. Sau đây là các phƣơng pháp mã hoá hay đƣợc sử dụng:

Mã hoá dạng chuỗi nhị phân:

Đây là phƣơng pháp thông dụng và cơ bản nhất đƣợc sử dụng ngay từ

bƣớc ban đầu khi nghiên cứu GA.

Trong phƣơng pháp này mỗi NST(lời giải) là một chuỗi nhị phân (chuỗi các bit

0 và 1) có chiều dài: m= trong đó m bit đầu tiên biểu diễn giá trị của

x (các giá trị trong khoảng [a ,b ]), m bit tiếp theo biểu diễn giá trị của x … và m bit cuối cùng biểu diễn giá trị của x .

Ví dụ: Muốn tìm cực đại hàm n biến f(x1,x2,…,xn) với (x1, x2, …, xn) R . Và ta muốn tối

thuộc một miền D nào đó của không gian Rn , D =[a ,b ] ƣu hóa hàm f với độ chính xác cho trƣớc là 6 số l với giá trị của các biến. Khi đó mỗi miền Di sẽ đƣợc phân cắt thành (bi – ai) x 106 miền con bằng nhau, mi sẽ là số nguyên nhỏ nhất sao cho:

(bi – ai) x 106 ≤ 2mi

Để tính giá trị thực của xi (giải mã các NST) ta thực hiện theo công thức:

xi = ai + decimal(chuỗi2) x

Trong đó decimal(chuỗi2) cho biết giá trị thập phân của chuỗi nhị phân đó.

Nhƣ vậy nếu bài toán có số chiều, miền giá trị của các biến lớn và yêu cầu độ chính xác tính toán cao thì chiều dài của các NST sẽ vô cùng lớn, do đó mà cách mã hóa này chỉ phù hợp với các bài toán có số chiều, miền giá trị các biến nhỏ (hay không gian tìm kiếm không lớn).

Mã hoá thứ tự:

Mỗi NST là một chuỗi các số nguyên thể hiện thứ tự phân bố lời giải của bài toán. Ví dụ: Trong bài toán ngƣời du lịch, mỗi NST(lời giải) là một chuỗi các số nguyên thể hiện thứ tự các thành phố đƣợc thăm.

Cách mã hóa này đƣợc sử dụng trong bài toán có sắp xếp thứ tự, không

gian tìm kiếm không phải là một miền liên tục.

Mã hoá dạng cây:

Đƣợc sử dụng chủ yếu trong các biểu thức toán học, trong phƣơng pháp

mã hoá này mỗi NST là một cây của một nhóm đối tƣợng nào đó.

Ví dụ: Biểu thức sau x+(y / 8) đƣợc mã hoá thành:

x /

y 8

Mã hoá số thực :

Mỗi NST đƣợc mã hoá là một véc tơ trong hông gian Rn, mỗi phần tử buộc phải nằm trong khoảng mong muốn và các phép toán đƣợc thiết kế một cách cẩn thận để đảm bảo yêu cầu này.

Chẳng hạn ở bài toán trên mỗi NST là một vectơ: =(a1, a2, ..., an) với

các ai  R biểu hiện giá trị thực của x .

Cách mã hoá này thƣờng tự nhiên đối với các bài toán tối ƣu số, và phát huy hiệu quả khi áp dụng giải bài toán cần độ chính xác cao, trong một không gian với số chiều lớn, do đó đƣợc phát triển rất mạnh trong thời gian gần đây.

Khởi tạo quần thể ban đầu

Tập lời giải ban đầu thƣờng đƣợc khởi tạo ngẫu nhiên từ miền xác định của các lời giải. Cách tạo lập tập lời giải ban đầu phụ thuộc rất nhiều vào cách mã hoá NST:

- Với phƣơng pháp mã hoá nhị phân: xây dựng NST bằng cách tạo ngẫu nhiên chuỗi các bit 0 hoặc 1, c ng có thể sử dụng những hiểu biết về phân phối xác suất để khởi tạo.

- Với phƣơng pháp mã hoá thứ tự: xây dựng NST ban đầu bằng cách hoán

vị ngẫu nhiên các thứ tự.

- Với mã hoá số thực: tạo ngẫu nhiên m véc tơ thực trong Rn.

Xác định hàm lượng giá

Hàm lƣợng giá đóng vai trò môi trƣờng, đánh giá hả năng phù hợp của tập lời giải theo yêu cầu bài toán. Hàm này đƣợc xây dựng cho từng bài toán với yêu cầu cụ thể. Thông thƣờng trong các bài toán tối ƣu hàm này chính là hàm mục tiêu của bài toán.

3.4 Các toán tử di tru ền

3.4.1 Toán tử chọn lọc

Toán tử chọn lọc có vai trò rất quan trọng trong quá trình tiến hóa, nhờ

quá trình này mà sau mỗi lần tiến hóa các cá thể có độ phù hợp cao đƣợc giữ

lại còn các cá thể phù hợp thấp bị loại bỏ.

Việc chọn lọc các cá thể căn cứ vào độ thích nghi đối với môi trƣờng

của chúng. Thông thƣờng, mỗi cá thể đƣợc gắn với một hàm để đánh giá độ

thích nghi (chính là hàm lƣợng giá). Hàm này là hàm thực dƣơng, có thể

không liên tục, không tuyến tính, không khả vi.

Tuy nhiên ngƣời ta c ng phát triển nhiều sơ đồ chọn khác nhau, dựa theo

các căn cứ khác nhau nhằm làm tăng tính đa dạng của quần thể, tránh sự hội tụ

sớm đến các cực trị địa phƣơng.

 Chọn lọc dựa trên độ thích nghi trung bình: Mỗi quần thể đặc trƣng

bởi một độ thích nghi trung bình. Mỗi lần tiến hoá ta chỉ giữ lại các cá thể có độ

phù hợp cao (độ thích nghi > độ thích nghi trung bình), còn các cá thể phù hợp

thấp bị loại bỏ.

 Chọn theo kỹ thuật quay bánh xe (bánh xe Rulet)

Ta xây dựng bánh xe Rulet nhƣ sau:

- Tính độ thích nghi của mỗi cá thể cti (i = 1 .. size).

- Tìm tổng giá trị thích nghi của toàn quần thể:

F =

- Tính xác suất chọn pi cho mỗi cá thể cti (i = 1.. size):

pi = f(cti) /F

- Tính vị trí xác suất qi của mỗi cá thể:

qi =

Tiến trình chọn lọc đƣợc thực hiện bằng cách quay bánh xe Rulet size lần,

mỗi lần chọn một cá thể từ quần thể hiện hành vào quần thể mới theo cách sau:

- Nếu r < qi thì chọn cá thể đầu tiên, ngƣợc lại thì chọn cá thể thứ i:

- Phát sinh ngẫu nhiên một số r trong khoảng [0..1].

cti(i = 2..size) sao cho qi-1 < r ≤ qi

 Chọn lọc dựa trên sự cạnh tranh: chọn ngẫu nhiên 2 cá thể trong quần

thể, so sánh độ thích nghi giữa chúng, giữ lại cá thể có độ thích nghi cao

hơn.

3.4.2 Toán tử lai ghép

Lai ghép là quá trình hình thành nhiễm sắc thể mới trên cơ sở các nhiễm

sắc thể cha-mẹ, bằng cách ghép một hay nhiều đoạn gen của hai nhiễm sắc thể

cha-mẹ với nhau. Lai ghép giúp tạo ra các thế hệ thích nghi hơn thế hệ trƣớc

thoả mãn quy luật tiến hoá của tự nhiên.

Sau khi chọn lọc đƣợc m NST, lần lƣợt lấy ra từng cặp NST để lai ghép

tạo ra hai NST mới. Một số dạng toán tử lai ghép hay dùng là:

 Lai ghép 1 điểm: Chọn ngẫu nhiên một vị trí sau đó hoán vị phần

đứng sau vị trí vừa chọn giữa hai NST cha và mẹ để nhận đƣợc hai NST con.

Ví dụ: nếu cặp NST cha mẹ đƣợc biểu diễn dƣới dạng hai véctơ:

(a1, b1, c1,| d1, e1, g1 )

và

(a2, b2, c2,| d2, e2, g2)

Với vị trí lai là 3 thì 2 NST con nhận đƣợc sau khi lai ghép sẽ là:

(a1, b1, c1, |d2, e2, g2)

và

(a2, b2, c2, |d1, e1, g1 )

Lai ghép hai điểm: Chọn ngẫu nhiên hai vị trí trong một NST, sau đó hoán vị các giá trị đứng giữa hai điểm đã chọn của hai NST cha mẹ để nhận đƣợc hai NST con.

Ví dụ: nếu cặp NST cha mẹ đƣợc biểu diễn dƣới dạng hai véctơ:

(a1,| b1, c1,| d1, e1, g1 )

và

(a2, |b2, c2, |d2, e2, g2)

Với 2 vị trí lai là 1 và 3 thì 2 NST con nhận đƣợc sau khi lai ghép sẽ là:

(a1,| b2, c2, |d1, e1, g1)

và

(a2, |b1, c1, |d2, e2, g2)

Lai ghép mặt nạ: Tạo một mặt nạ ngẫu nhiên có số bit bằng chiều dài của NST. Ta sẽ hoán vị các giá trị của hai NST cha và mẹ ở những vị trí tƣơng ứng với vị trí bit 1 của mặt nạ.

Ví dụ: Nếu cặp NST cha mẹ đƣợc biểu diễn dƣới dạng hai véctơ:

(a1, b1, c1, d1, e1 )

và

(a2, b2, c2, d2, e2)

Mặt nạ lai ghép: (10110) thì 2 NST con nhận đƣợc sẽ là:

(a2, b1, c2, d2, e1)

và

(a1, b2, c1, d1, e2)

Đối với phƣơng pháp mã hoá thực, mỗi NST đƣợc mã hoá bằng một

vectơ số thực có cùng độ dài với vectơ lời giải nên khi mã hoá thực ta còn sử

dụng các phép lai sau:

 Lai số học: Phép lai này đƣợc định nghĩa là tổ hợp tuyến tính của hai

vectơ: x1 và x2, các con sinh ra sẽ là :

' = a* x1 + (1 - a)* x2

' = a*x2 + (1 - a)*x1

Toán tử này dùng giá trị ngẫu nhiên , để bảo đảm

 Lai Heuristic: Toán tử này là phép lai một con vì những lý do sau:

(1) nó dùng các giá trị hàm mục tiêu để quyết định hƣớng tìm kiếm, (2) nó chỉ

tạo ra một con, và (3) c ng có thể không tạo ra con nào cả.

Toán tử này phát sinh một con duy nhất x từ hai cá thể cha mẹ x1 và x2

theo luật sau đây:

x = r*(x2 - x1) + x2

Trong đó: r là số ngẫu nhiên giữa 0 và 1, và x2 không xấu hơn x1, nghĩa là, f(x2)

f(x1) đối với bài toán cực đại hoá và f(x2) f(x1) đối với bài toán cực tiểu hoá.

Có thể toán tử này phát sinh một vectơ con hông thoả mãn ràng buộc.

Trƣờng hợp này, một giá trị ngẫu nhiên r hác đƣợc phát sinh và một con khác

đƣợc tạo. Nếu sau w lần thử mà hông tìm đƣợc một lời giải mới thoả mãn các

ràng buộc, toán tử này sẽ bỏ cuộc và sẽ không tạo ra con nào.

 Lai ghép BLX-α: Phép lai này chỉ tạo ra một cá thể con từ hai cá thể

cha mẹ. Mỗi thành phần zi của cá thể con đƣợc chọn theo phân phối ngẫu nhiên

đều trong khoảng:

[min(xi, yi) – I.α, max(xi, yi)+ I.α]

Trong đó I = max(xi, yi) - min(xi, yi).

Tham số α thƣờng đƣợc chọn là 0.5. Khi đó toán tử này còn đƣợc gọi là

BLX-0.5

3.4.3 Toán tử đột biến

Khác với phép lai, phép đột biến thay đổi một cách ngẫu nhiên một hay

nhiều gen của NST đƣợc chọn, thay đổi này đƣợc thực hiện với một xác suất thể

hiện tốc độ đột biến. Các cá thể (NST) con mang một (một số) tính trạng không

có trong di truyền của cha-mẹ cho phép đƣa thêm các thông tin mới vào quần

thể làm cho chất liệu di truyền phong phú thêm.

Đột biến giúp cho giải thuật di truyền thoát khỏi tối ƣu cục bộ trong

không gian tìm kiếm.

Sau đây là một số phƣơng pháp đột biến:

 Đột biến đảo bít :

Toán tử này đƣợc sử dụng với mã hoá nhị phân.

Phép đột biến này thay đổi vị trí một bit trong NST một cách ngẫu nhiên

với xác suất bằng xác suất đột biến.

VD: NST (1000111001) sau hi đột biến ở vị trí thứ 3 sẽ tạo thành cá thể

mới với NST là (1010111001).

 Đột biến đồng dạng:

Toán tử này tạo ra một con duy nhất x' từ cá thể cha x. Ta chọn một thành

',..., xn), trong đó xk

phần ngẫu nhiên k (1,...,n) của vectơ x=(x1, x2,..., xk,.. xn) và sản sinh ra ' là giá trị ngẫu nhiên (phân bố xác suất đều) x'=(x1,..., xk

trong khoảng .

 Đột biến biên: Phép đột biến này c ng tạo ra một con duy nhất x' từ cá

thể cha x, bằng cách chọn ngẫu nhiên k (1, 2,…, n) của vectơ x =

(x ,…,x ,…, x ) và sản sinh ra x = (x ,…,x ,…, x ), trong đó x là left(k)

hoặc right(k) với cùng xác suất.

Toán tử này đƣợc xây dựng cho các bài toán tối ƣu mà lời giải tối ƣu nằm

trên biên hoặc gần biên của không gian tìm kiếm. Do đó nếu tập ràng buộc C

rỗng và biên thật lớn, thì toán tử này gây phiền toái. Nhƣng nó lại có ích khi có

các ràng buộc và nghiệm đúng gần biên.

 Đột biến không đồng dạng:

Phép đột biến này đƣợc xác định nhƣ sau: Đối với cá thể cha x, nếu thành

phần xk đƣợc chọn thì kết quả là:

nếu chữ số nhị phân ngẫu nhiên là 0

nếu chữ số nhị phân ngẫu nhiên là 1

Hàm trả về một giá trị trong khoảng [0,y] sao cho xác suất của

gần bằng 0 tăng hi t tăng (t là số thế hệ). Thuộc tính này khiến toán tử

ban đầu sẽ tìm trong hông gian đồng dạng (khi t nhỏ), và rất cục bộ ở những

giai đoạn sau. Ta dùng hàm sau đây:

Trong đó, r là hệ số ngẫu nhiên trong khoảng [0,1], T là số thế hệ tối đa,

còn b là tham số hệ thống, xác định mức độ hông đồng dạng.

3.5 Các tham số trong giải thuật di tru ền

 Kích thước quần thể

Kích thƣớc quần thể cho biết có bao nhiêu cá thể (NST) trong 1 thế hệ

của quần thể.

Đây là tham số quan trọng nhất mà ta phải xác định khi sử dụng giải thuật

di truyền. Nếu ích thƣớc quần thể quá nhỏ, giải thuật di truyền hội tụ quá

nhanh, khả năng mới chỉ có một vùng tìm kiếm nhỏ đƣợc khảo sát. Còn nếu

ích thƣớc quần thể quá lớn sẽ dẫn tới hao phí tài nguyên và làm kéo dài quá

trình giải toán.

 Xác suất lai ghép

Là tham số cho biết tần suất thực hiện toán tử lai ghép. Chẳng hạn, nếu

xác suất lai là 0.25 nghĩa là mỗi cá thể trong quần thể có 25% cơ hội đƣợc chọn

để tiến hành lai ghép.

Lai ghép tạo ra sự đa dạng cho quần thể, do vậy việc xác định xác suất lai

ghép c ng rất quan trọng: nếu không có lai ghép, cá thể con sẽ chính là bản sao

của cá thể cha mẹ, còn nếu xác suất lai ghép là 1 thì mọi cá thể con đều đƣợc tạo

ra qua quá trình lai ghép. Thông thƣờng xác suất lai ghép đƣợc chọn khá lớn

(trên 0.8).

 Xác suất đột biến

Là tham số cho biết tần suất đột biến của các cá thể.

Xác suất đột biến c ng có vai trò quan trọng không kém: nếu không có

đột biến (xác suất đột biến là 0), các cá thể con tạo ra ngay sau giai đoạn lai

ghép mà không bị thay đổi, không có gen mới đƣợc bổ sung vào quần thể,

nhƣng nếu tất cả các cá thể sinh ra sau lai tạo đều bị đột biến (xác suất đột biến

là 1), có khả năng lại làm mất đi các gen tốt.

Thông thƣờng xác suất đột biến đƣợc chọn xấp xỉ 0.1.

Chƣơng 4. NHẬN DẠNG CHỮ HÁN-NÔM DỰA TRÊN MẠNG NƠ-RON KẾT HỢP GA

Nhƣ đã phân tích trong chƣơng 2, bộ trọng số ban đầu c ng là một yếu tố ảnh hƣởng tới quá trình huấn luyện mạng. Nếu các trọng số đƣợc khởi tạo với giá trị lớn thì ngay từ đầu tổng tín hiệu vào đã có giá trị tuyệt đối lớn và làm cho đầu ra của mạng chỉ đạt 2 giá trị 0 và 1. Điều này làm cho hệ thống sẽ bị tắc tại một cực tiểu cục bộ hoặc tại một vùng bằng phẳng nào đó gần ngay điểm xuất phát. Do đó các trọng số này thƣờng đƣợc khởi tạo bằng những số ngẫu nhiên nhỏ. Wessels và Barnard [17] đã nghiên cứu và chỉ ra rằng việc khởi tạo các

với ki là số liên kết của các

trọng số Wij chỉ nên trong phạm vi nơ-ron j tới nơ-ron i.

Các nghiên cứu về GA kết hợp với ANN bắt đầu bởi Montana and Davis [16]. Năm 1989 các ông đã có báo cáo về việc ứng dụng thành công GA trong mạng ANN và đã chứng minh đƣợc rằng G tìm đƣợc bộ trọng số tối ƣu tốt hơn BP trong một số trƣờng hợp. Kumar Reddy [18] và Yas Abbas Alsultanny [20] đạt tới c ng đạt đƣợc kết quả tốt hơn và giảm thời gian huấn luyện khi sử dụng G để khởi tạo bộ trọng số ban đầu cho mạng nơ-ron đa tầng truyền thẳng. Những nghiên cứu trên là động lực khiến tôi áp dụng G để tối ƣu bộ trọng số cho ANN trong bài toán nhận dạng chữ Hán-Nôm với hi vọng cải thiện đƣợc tỉ lệ nhận dạng và với những ƣu điểm của ANN có thể áp dụng thành công trong việc nhận dạng những bộ dữ liệu lớn.

4.1 Khảo sát sự hội tụ của mạng nơ-ron

Khảo sát đƣợc tiến hành với mạng 3 lớp, lớp đầu vào gồm 25 nơ-ron, lớp ẩn 5 nơ-ron và lớp đầu ra 1 nơ-ron. Bộ trọng số khởi tạo ban đầu đƣợc lấy ngẫu nhiên quanh điểm 0.5, là trung điểm của hàm kích hoạt sigmoid. Sau khi lập trình và cho luyện mạng 14 lần ta có đƣợc bảng 4.1

Bảng 4.1 Kết quả khảo sát sự hội tụ của mạng nơ-ron

STT Số vòng lặp STT Số vòng lặp

1 Thất bại 8 Thất bại

2 81007 9 Thất bại

3 Thất bại 10 35672

4 85060 11 65742

5 14542 12 Thất bại

6 Thất bại 13 78649

7 42335 14 65903

Căn cứ vào bảng 4.1 ta thấy với một thuật toán hông đổi, cấu trúc, tham số của mạng chọn nhƣ nhau thì kết quả của quá trình luyện mạng phụ thuộc vào bộ khởi tạo trọng số ban đầu, thậm chí còn có 6 lần luyện mạng thất bại trong tổng số 14 lần luyện mạng. Điều đó đƣợc giải thích: do bản chất của giải thuật học lan truyền ngƣợc sai số là phƣơng pháp giảm độ lệch gradient nên việc khởi tạo giá trị ban đầu của bộ trọng số các giá trị nhỏ ngẫu nhiên sẽ làm cho mạng hội tụ về các giá trị cực tiểu khác nhau. Nếu gặp may thì mạng sẽ hội tụ đƣợc về giá trị cực tiểu tổng thể, còn nếu không mạng có thể rơi vào cực trị địa phƣơng và hông thoát ra đƣợc dẫn đến luyện mạng thất bại.

4.2 Thuật toán GANN

Nhờ cơ chế tìm kiếm trải rộng, ngẫu nghiên và mang tính chọn lọc tự nhiên nên: GA thƣờng tìm ra đƣợc vùng chứa cực trị toàn cục, nhƣng hó đạt đƣợc cực trị toàn cục. Một mặt ta muốn GA duy trì sự đa dạng quần thể (trải rộng không gian tìm kiếm) để tránh hội tụ sớm đến cực trị cục bộ; mặt khác, khi “đã khoanh vùng được cực trị toàn cục”, ta muốn GA thu hẹp vùng tìm kiếm để “chỉ ra được cực trị toàn cục”. Mục tiêu thứ nhất thƣờng dễ đạt đƣợc bằng cách chọn hàm thích nghi và phƣơng pháp tái tạo quần thể phù hợp. Để đạt đƣợc mục tiêu thứ hai đòi hỏi chúng ta phải chia quá trình tiến hóa thành hai giai đoạn, trong giai đoạn hai ta phải chỉnh lại: các toán tử lai, đột biến, tái tạo; phƣơng pháp chọn lọc; đánh giá độ thích nghi; c ng nhƣ chỉnh sửa lại các tham số của quá trình tiến hóa để có thể đến cực trị toàn cục. Việc thực thi một mô hình nhƣ

thế sẽ rất phức tạp. Do đó, cần phải kết hợp GA với các phƣơng pháp tối ƣu cục bộ khác.

Các phƣơng pháp học trong ANN thực hiện việc “tìm iếm cục bộ” trong không gian trọng số (dựa trên thông tin về đạo hàm của lỗi) nên có hai nhƣợc điểm. Thứ nhất bộ trọng số thu đƣợc thƣờng không là tối ƣu toàn cục. Thứ hai quá trình học có thể không hội tụ hoặc hội tụ rất chậm. Do đó, cần phải kết hợp các phƣơng pháp học “mang tính cục bộ” của ANN với các thuật giải “mang tính toàn cục” nhƣ thuật giải di truyền. Từ những nhận xét đó ta thấy rằng có thể kết hợp GA và ANN nhằm nâng cao hiệu quả của ANN. GA sẽ khoanh vùng chứa cực tiểu toàn cục của hàm lỗi, sau đó NN xuất phát từ bộ trọng số này để tiến đến cực tiểu toàn cục. Thuật toán đề xuất nhƣ sau:

Hình 4.1 Sơ đồ thuật toán GANN

Thuật toán kết hợp giải thuật di truyền và thuật toán lan truyền ngƣợc cho

mạng MLP đƣợc đề xuất trong hình 4.1. Nó bao gồm hai giai đoạn luyện mạng.

Giai đoạn đầu tiên sử dụng thuật toán di truyền với bƣớc truyền thẳng nhằm đẩy nhanh toàn bộ quá trình luyện mạng. Thuật toán di truyền thực hiện

tìm kiếm toàn cục và tìm kiếm tối ƣu gần điểm ban đầu (trọng lƣợng vec-tơ) cho giai đoạn thứ hai. Trong đó, mỗi nhiễm sắc thể đƣợc sử dụng để mã hóa các trọng số của mạng nơ-ron. Hàm thích nghi (hàm mục tiêu) cho các thuật toán di truyền đƣợc xác định là tổng bình phƣơng lỗi của mạng nơ-ron tƣơng ứng. Do đó, bài toán sẽ trở thành tối ƣu hóa không giới hạn nhằm tìm một tập hợp các biến quyết định giảm thiểu hàm mục tiêu.

Trong giai đoạn thứ 2 sẽ sử dụng kỹ thuật lan truyền ngƣợc với hệ số học

nhỏ.

4.3 Thực nghiệm

4.3.1 Quy trình thực nghiệm

Quy trình thực nghiệm đƣợc tiến hành theo 3 bƣớc chính: chuẩn bị dữ

liệu, huấn luyện mạng và nhận dạng.

Chọn ký tự

Tạo ảnh

Tách ảnh

In và Scan ảnh

Tập 495 chữ Nôm

Các file ảnh

Các file ảnh scan

Các file ảnh chữ Nôm rời

Chuẩn bị dữ liệu

Huấn luyện mạng

Lấy ảnh, trích chọn đặc trƣng

Mạng đã huấn luyện

Tập ảnh huấn luyện

Huấn luyện

Nhận dạng

Đánh giá

Lấy ảnh, trích chọn đặc trƣng

Kết quả nhận dạng

Tập ảnh nhận dạng

Kết quả đánh giá

Nhận dạng

Hình 4.2 Quy trình tiến hành thực nghiệm

4.3.2 Xây dựng bộ dữ liệu thực nghiệm

Dữ liệu là thành phần quan trọng trong việc thử nghiệm và đánh giá phƣơng pháp nhận dạng và c ng là cơ sở để đánh giá ết quả nhận dạng có chính xác hay không. Do cơ sở dữ liệu để phục vụ đề tài chƣa có, nên nhóm nghiên cứu phòng thì nghiệm hệ thống nhúng đã tiến hành xây dựng bộ dữ liệu thực bằng cách thống kê những chữ xuất hiện trên 10 lần trong bộ Truyện Kiều của đại thi hào Nguyễn Du. Kết quả thống ê thu đƣợc 495 chữ. Với bộ dữ liệu 495 chữ đó, chúng tôi sử dụng 3 loại font khác nhau là Hán Nôm A, Hán Nôm B, Nôm Na Tông, mỗi font lấy hai kiểu chữ là chữ đậm và chữ thƣờng. Nhƣ vậy mỗi chữ có 6 mẫu, tổng số mẫu của bộ dữ liệu là 2970. Mỗi mẫu ký tự đặt tên theo quy tắc: ID_Mẫu_Font_ Kiểu.

Trong đó: - ID là mã đặt cho ý tự, mỗi ý tự có 1 ID khác nhau. - Mẫu là chế độ lấy mẫu, đánh số 0, 1, 2… với bộ dữ liệu này thì Mẫu luôn là 0 vì đƣợc lấy theo c ng một chế độ scan chữ in trên giấy trắng hổ 4, mực in màu đen.

- Font là tên font chữ của mẫu. - Kiểu là 0_0 nếu là chữ thƣờng, và 0_1 nếu là chữ đậm.

Hình 4.3 một số mẫu chữ Nôm trong bộ dữ liệu thực nghiệm

Bộ dữ liệu thử nghiệm này có chất lƣợng tốt, độ nhiễu loạn gần nhƣ không có, sau khi thành công với bộ dữ liệu này chúng tôi sẽ tiếp tục xây

dựng những bộ dữ liệu với mức độ nhiễu khác nhau nhằm cải tiến khả năng nhận dạng của chƣơng trình ở những điều kiện chữ nhiễu loạn khác nhau.

4.3.3 Tiến hành thực nghiệm 4.3.3.1 Phương pháp kiểm chứng

K-fold cross validation [14] là một phƣơng pháp iểm chứng chéo, bộ dữ liệu kiểm chứng đƣợc chia ra làm K tập. Lần lƣợt thực hiện K lần kiểm chứng quay vòng, mỗi lần dùng 1 tập mẫu để thử nghiệm và K-1 tập còn lại để huấn luyện. Lỗi xuất hiện qua K lần kiểm chứng đƣợc tính trung bình.

Để thực nghiệm với K-fold cross validation thì việc lấy mẫu thử và mẫu huấn luyện phải lấy ngẫu nhiên, tuy nhiên để kiểm tra tính suy đoán của phƣơng pháp, chúng tôi thực nghiệm theo phƣơng pháp tựa K-fold cross validation, nghĩa là với bộ dữ liệu thực nghiệm trên chúng tôi quyết định lựa chọn 5 tập mẫu thuộc 5 bộ chữ hác nhau để huấn luyện, 1 bộ mẫu thuộc tập còn lại để thực nghiệm. Nhƣ vậy tập huấn luyện và tập nhận dạng thử nghiệm không giao nhau về kiểu chữ và font chữ, khả năng suy diễn của phƣơng pháp nhận dạng đƣợc kiểm tra, chƣơng trình sẽ sử dụng bộ tri thức của kiểu font này nhận dạng bộ ảnh chữ của font ia đƣợc thử nghiệm đánh giá. Từ đó có thể đánh hả năng ứng dụng thực tế của phƣơng pháp.

4.3.3.2 Thực nghiệm

Chƣơng trình đƣợc thực nghiệm trên máy tính Lenovo X220, có bộ vi xử lý Intel(R) Core(TM) i5-2520M CPU @2.5GHz 2.5GHz, Ram 2GB và đƣợc cài đặt hệ điều hành indows 7.

Chƣơng trình đƣợc thiết kế với giao diện nhƣ trong các hình 4.4, 4.5, 4.6.

Hình 4.4 Giao diện cấu hình mạng

Lựa chọn cấu hình mạng khi tiến hành thử nghiệm bao gồm số lớp trong mạng, số nơ-ron trong mỗi lớp, và lựa chọn các tham số cho quá trình học nhƣ ngƣỡng lỗi, hệ số học, hàm truyền.

Hình 4.5 Giao diện lựa chọn tham số cho GA

Cấu hình NST cho phép lựa chọn các tham số cho giải thuật di truyền bao gồm: tỷ lệ lai ghép, đột biến, số thế hệ, ích thƣớc quần thể. Và cho phép ta thấy đƣợc bộ trong số tối ƣu có đƣợc sau quá trình thực hiện với giải thuật di truyền.

Hình 4.6 Giao diện huấn luyện mạng và nhận dạng

4.4 Đánh giá kết quả

Để đảm bảo việc kết hợp giải thuật di truyền tìm ra đƣợc bộ trọng số tốt nhất phục vụ cho quá trình huấn luyện tiếp theo, tôi đã tiến hành thử nghiệm GA với các phép toán lai ghép và đột biến hác nhau (đã đƣợc trình bày trong chƣơng 3) và nhận thấy rằng phép lai BLX 0,5 và phép đột biến đồng dạng tỏ ra hiệu quả hơn cả.

Và để tiện so sánh việc thực hiện giải thuật GANN với việc dùng thuật toán lan truyền ngƣợc nguyên thủy, tôi dùng chung bộ tham số cho cả 2 thử nghiệm này. Về cấu hình mạng nơ-ron: số lớp trong mạng là 5, trong đó 3 lớp ẩn, mỗi lớp đều có 10 nơ-ron, lớp vào là 100 nơ-ron và lớp ra là 1 nơ-ron, hệ số học: 0,02 và ngƣỡng lỗi là 0,001. Đối với giải thuật GA và GANN: phép lai đƣợc sử dụng là BLX 0,5 với tỷ lệ lai ghép 0,8 và phép đột biến đồng dạng với tỷ lệ đột biến là 0,1, kích cỡ quần thể là 100 và tiến hành tìm kiếm qua 1000 thế hệ.

Kết quả thực nghiệm đƣợc thể hiện qua các bảng 4.2, 4.3.

Bảng 4.2 Kết quả thực nghiệm với mạng GANN

Tập nhận dạng Tập mẫu huấn luyện Số ký tự nhận dạng Số ký tự huấn luyện Tỷ lệ nhận dạng đúng

2685 HanNomA_0_0 495 90,01%

2685 HanNomA_0_1 495 84,48%

2685 HanNomB_0_0 495 87,27%

2685 HanNomB_0_1 495 88,28%

2685 NomNaTong_0_0 495 82,82%

2685 NomNaTong_0_1 495 85,45%

HanNomA_0_1, HanNomB_0_0, HanNomB_0_1, NomNaTong_0_0, NomNaTong_0_1 HanNomA_0_0, HanNomB_0_0, HanNomB_0_1, NomNaTong_0_0, NomNaTong_0_1 HanNomA_0_0, HanNomA_0_1, HanNomB_0_1, NomNaTong_0_0, NomNaTong_0_1 HanNomA_0_0, HanNomA_0_1, HanNomB_0_0, NomNaTong_0_0, NomNaTong_0_1 HanNomA_0_0, HanNomA_0_1, HanNomB_0_0, HanNomB_0_1, NomNaTong_0_1 HanNomA_0_0, HanNomA_0_1, HanNomB_0_0, HanNomB_0_1, NomNaTong_0_0

Tỷ lệ nhận dạng trung bình: 86,39%

Bảng 4.3 Kết quả thực nghiệm với mạng ANN

Tập huấn luyện Tập nhận dạng Số ký tự nhận dạng Số ký tự huấn luyện Tỷ lệ nhận dạng đúng

2685 HanNomA_0_0 495 89.89%

2685 HanNomA_0_1 495 60.00%

2685 HanNomB_0_0 495 75.55%

2685 HanNomB_0_1 495 74.54%

2685 NomNaTong_0_0 495 86.26%

2685 NomNaTong_0_1 495 60.67%

Tỷ lệ nhận dạng trung bình: 74,49%

Từ kết quả nhận dạng trên, ta có thể thấy hiệu quả của việc áp dụng giải thuật di truyền trong việc khởi tạo bộ trọng số ban đầu cho mạng. Khi thực hiện với GANN kết quả cao nhất đạt tới 90,01%, kết quả nhận dạng trung bình đạt 86,39 % trong khi sử dụng thuật toán lan truyền ngƣợc nguyên thủy chỉ đạt mức 74,49%. Kết quả nhận dạng này khẳng định việc khởi tạo trọng số ban đầu ảnh hƣởng tới kết quả việc huấn luyện mạng nơ-ron và c ng cho thấy rằng việc áp dụng giải thuật di truyền để tối ƣu đầu vào cho việc huấn luyện mạng thực sự mang lại kết quả tốt hơn hẳn so với mạng nơ-ron và thuật toán lan truyền ngƣợc nguyên thủy.

Tổng kết chƣơng 4

Chƣơng 4 trình bày ết quả khảo sát sự hội tụ của mạng nơ-ron, khẳng định thêm nhận xét về ƣu nhƣợc điểm khi sử dụng mạng nơ-ron và giải thuật di truyền trong bài toán tìm kiếm tối ƣu. Từ cơ sở đó đƣa ra giải thuật kết hợp mạng nơ-ron và giải thuật di truyền nhằm tạo ra bộ nhận dạng hiệu quả cho bài toán nhận dạng chữ Hán-Nôm. Trình bày quy trình hực nghiệm, đánh giá kết quả sử dụng thuật toán đề xuất trong việc nhận dạng chữ Hán-Nôm. So sánh với việc áp dụng mạng nơ-ron và thuật toán lan truyền ngƣợc nguyên thủy. Khẳng định nhận định ban đầu là đúng và là cơ sở cho những nghiên cứu tiếp theo về ứng dụng mạng nơ-ron trong nhận dạng chữ Hán-Nôm.

KẾT LUẬN

Kết quả đạt đƣợc

Luận văn đã trình bày hái quát về chữ Nôm, lịch sử hình thành, cấu tạo chữ. Từ đó chỉ ra rằng chữ Nôm có cấu tạo Luận văn đã trình bày hái quát về chữ Nôm, lịch sử hình thành, cấu tạo chữ. Từ đó chỉ ra rằng chữ Nôm có cấu tạo Luận văn đã trình bày hái quát về chữ Nôm, lịch sử hình thành, cấu tạo chữ. Từ đó chỉ ra rằng chữ Nôm có cấu tạo phức tạp hơn chữ Hán rất nhiều, vì vậy các kỹ thuật áp dụng tốt cho chữ Hán chƣa hẳn đã tốt cho chữ Nôm. Do đó việc xây dựng bộ nhận dạng chữ Hán-Nôm là yêu cầu cấp thiết để bảo tồn di sản chữ Nôm của nƣớc nhà.

Luận văn c ng tìm hiểu và trình bày các kiến thức cơ bản về mạng nơ-ron và giải thuật di truyền. Phân tích ƣu điểm c ng nhƣ hạn chế của từng phƣơng pháp. Trên cơ sở tìm hiểu kinh nghiệm của các nƣớc trên thế giới về việc sử dụng mạng nơ-ron trong nhận dạng chữ tƣợng hình, c ng nhƣ các nghiên cứu về kết hợp mạng nơ-ron với giải thuật di truyền trong nhận dạng chữ viết tay. Từ đó đề xuất giải thuật GANN(giải thuật kết hợp mạng nơ-ron với giải thuật di truyền ).

Trên cơ sở đó tiến hành thực nghiệm với bộ dữ liệu gồm 2970 chữ do nhóm nghiên cứu Les Nôm xây dựng. Kết quả thu đƣợc đã thể hiện sự tốt hơn đáng ể so với việc chỉ sử dụng mạng nơ-ron và thuật toán lan truyền ngƣợc nguyên thủy. Khẳng định nhận định ban đầu là đúng và là cơ sở cho những nghiên cứu tiếp theo về ứng dụng mạng nơ-ron trong nhận dạng chữ Hán-Nôm.

hơn chữ Hán rất nhiều, vì vậy các kỹ thuật áp dụng tốt cho chữ Hán chƣa hẳn đã tốt cho chữ Nôm. Do đó việc xây dựng bộ nhận dạng chữ Hán-Nôm là yêu cầu cấp thiết để bảo tồn di sản chữ Nôm của nƣớc nhà.

Trên cơ sở đó tiến hành thực nghiệm với bộ dữ liệu gồm 2970 chữ do nhóm nghiên cứu Les Nôm xây dựng. Kết quả thu đƣợc đã thể hiện sự tốt hơn

đáng ể so với việc chỉ sử dụng mạng nơ-ron và thuật toán lan truyền ngƣợc nguyên thủy. Khẳng định nhận định ban đầu là đúng và là cơ sở cho những nghiên cứu tiếp theo về ứng dụng mạng nơ-ron trong nhận dạng chữ Hán-Nôm.

Hƣớng phát triển

Tiếp tục thử nghiệm giải thuật GANN với các phƣơng pháp trích chọn đặc

trƣng hác nhau.

Kết hợp giải thuật di truyền để lựa chọn các kết nối giữa các nơ-ron, nhằm tăng tốc độ trong quá tình huấn luyện.

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] Nguyễn Tuấn Cƣờng, “Thời điểm xuất hiện chữ Nôm và sơ đồ cấu

trúc chữ Nôm”, 2009.

[2] Phạm Văn Hƣởng, Trần Minh Tuấn, Nguyễn Thị Ngọc Hƣơng, Bùi Thị Hồng Hạnh, Lê Hồng Trang, V Thanh Nhân, Trƣơng nh Hoàng, V Quang D ng, Nguyễn Ngọc Bình (2008), “Một số phƣơng pháp nhận dạng chữ Nôm”, Hội thảo Khoa học Quốc gia Lần thứ IV về CNTT-TT (ICT.rda’2008), Hà Nội.

[3] GS.TSKH. Nguyễn Quang Hồng, hái ược văn tự học ch Nôm, Nhà xuất

bản giáo dục, 2008.

Tiếng Anh

[4] Mingrui Wu, Bo Zhang, Ling Zhang, “A Neural Network Based Classifier for Handwritten Chinese Character Recognition”, ICPR'00 - Volume 2, 2000.

[5] Il-SeokOh, Ching Y. Suen, “A class-modular feedforward neural network

for handwriting recognition”, Pattern Recognition 35 (2002) 229-244

[6] Srinivasa Kumar Devireddy, Settipalliappa Rao(2009), “Hand written character recognition using back propagation network”, Journal of Theoretical and Applied Information Technology.

[7] Richard Romero, Robert Berger, Robert Thibadeau, and Dave Touretsky, “Neural Network Classifiers for Optical Chinese Character Recognition”.

[8] Richard Romero, David Touretzky, and Robert Thibadeau, “Optical Chinese

Character Recognition using Probabilistic Neural Networks”.

[9] D.E. Rumelhart; G.E. Hinton and R.J. Williams (1986), “Learning internal representations by error propagation”, Parallel distributed processing: Explorations in the microstructure of cognition (Cambridge MA.: MIT Press), 318-362.

[10] Tadashi Horiuchi, Satoru Kato, “a study on japanese historical character recognition using modular neural networks”, International Journal of InnovativeComputing, Information and Control, Volume 7, Number 8, August 2011

[11] Geva, Shlomo, and Joaquin Sitte: “Adaptive Nearest Neighbor Pattern C assiﬁcation, IEEE Transactions on Neural Networks”, 1991, Vol.2, No. 2.

[12] H.-H. Song, S.-W.Lee, “A self-organizing neural tree forlarge-set pattern

classication”, IEEE Trans. Neural Net-works 9 (3) (1998) 369}380.

[13] H.-M. Lee, C.-C.Lin, J.-M.Chen, “A preclassi"cationmethod

for handwritten Chinese character recognition viafuzzy rules and SEART neural net”, Int. J. Pattern Recogni-tion Artif.Intell.12 (6) (1998) 743}761.

[14] Juan Diego Rodrıguez, ritz Perez, Jose ntonio Lozano, Member, IEEE, “Sensitivity Ana ysis of k-Fold Cross Validation in Prediction Error Estimation”, IEEE Transactions on pattern analysis and machine intelligence, Vol. 32, No. 3, March 2010.

[15] Jeffrey T. Spooner, Mangredi Maggiore, Raúl Ordónez, Kelvin M. Passino (2002), “Stable Adaptive Control and Estimation for Nonlinear Systems: Neural and Fuzzy Approximator Techniques”, Wiley Interscience, USA.].

[16] Jyh-Shing Roger Jang, Chuen-Tsai Sun, Eiji Mizutani (1996), “Neuro- Fuzzy and Soft Computing: A Computational Approach to Learning and Machine Intelligence”, Prentice Hall, USA.].

[17] L.F.A. Wessels, E. Barnard, “Avoiding false local minima by proper initialization of connections”, IEEE Trans. Neural Networks 3 (1992) 899- 905.

[18] R.Ashok Kumar Reddy, G. Venkata Narasimhulu, Dr. S. A. K. Jilani, Dr D.Seshappa, “Genetic Algorithm based Gait Recognition”, International Journal of Electronics and Computer Science Engineering ISSN- 2277-1956.

[19] David J. Montana, Lawrence Davis “Training feedforward neural networks using genetic algorithms” IJC I'89 Proceedings of the 11th international joint conference on Artificial intelligence - Volume 1.

[20] Yas bbas lsultanny, Musbah M. qel, “Pattern recognition using multilayer neural-genetic algorithm”, Neurocomputing 51 (2003) 237 – 247.

Luận văn Thạc sĩ Công nghệ thông tin: Nghiên cứu ứng dụng mạng Nơ ron trong nhận dạng chữ Hán-Nôm

ĐẠI HỌC QUỐC GIA HÀ NỘI ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

Hà Nội – 2014

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

TRƢƠNG THỊ HƢƠNG TRƢƠNG THỊ HƢƠNG

NGHIÊN CỨU ỨNG DỤNG MẠNG NƠ RON TRONG NGHIÊN CỨU ỨNG DỤNG MẠNG NƠ RON TRONG NHẬN DẠNG CHỮ HÁN-NÔM NHẬN DẠNG CHỮ HÁN-NÔM

Ngành: Công nghệ thông tin Ngành: Công nghệ thông tin

Chuyên ngành: Kỹ thuật phần mềm Chuyên ngành: Kỹ thuật phần mềm

Mã số: 60480103 Mã số: 60480103

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN NGƢỜI HƢỚNG DẪN KHOA HỌC: NGỌC BÌNH PGS.TS. NGUYỄN NGỌC BÌNH Hà Nội – 2014

Có thể bạn quan tâm

Bài giảng Phân tích và thiết kế hệ thống thông tin giáo dục

Bài giảng Công nghệ phần mềm: Bài 1 - Tổng quan về phần mềm và công nghệ phần mềm

Bài giảng Công nghệ phần mềm: Bài 2 - Đặc tả yêu cầu phần mềm

Bài giảng Công nghệ phần mềm: Bài 3 - Thiết kế phần mềm

Bài giảng Công nghệ phần mềm: Bài 4 - Đảm bảo chất lượng phần mềm

Bài giảng Công nghệ phần mềm: Bài 5 - Mô hình CMMI

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Đồ án tốt nghiệp: Xây dựng app nghe nhạc kết hợp các tiện ích AI

Áp dụng mạng Bayes xây dựng mô hình dự đoán xác suất có điều kiện phức hợp

Bài giảng Mạng định nghĩa bằng phần mềm và ảo hóa chức năng mạng (SDN và NFV)

Bài tập lớn: Tổng quan về mạng cảm biến không dây (WSN)

Bài giảng Tin học căn bản: Chương 1 - Kiến thức cơ bản về máy tính và hệ điều hành windows

Bài giảng Tin học căn bản: Chương 2 - Microsoft Word

Bài giảng Tin học căn bản: Chương 3 - Microsoft Excel

Bài giảng Tin học căn bản: Chương 4 - Microsoft PowerPoint

Bài giảng Tin học căn bản: Chương 5 - Internet và email

Báo cáo đồ án: Quản lý nhà sách

Đồ án cơ sở: Xây dựng ứng dụng nghe sách audiobook trực tuyến

Báo cáo đồ án: Thiết kế mạng cho doanh nghiệp

Báo cáo đồ án: Xây dựng website bán sách HHH-BOOK

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok