chương 1 Trên đây chúng tôi đã giới thiệu về xử lý ngôn ngữ tự nhiên như khái niệm và một số bài toán NLP; giới thiệu khái niệm số hóa văn bản, giới thiệu một số công nghệ số hóa tài liệu như công nghệ nhận dạng OCR, công nghệ soát lỗi chính tả tiếng Việt, công nghệ tách bộ và lập chỉ mục. Trên cơ sở đó, luận văn đưa ra giải pháp là xây dựng một hệ thống số hóa văn bản tiếng Việt với tên là FSCANNER. Mỗi bước trong quy trình số hóa của hệ thống liên quan mật thiết với mỗi bài toán trong xử lý ngôn ngữ, cụ thể là bài toán nhận dạng chữ OCR, bài toán soát lỗi chính tả tiếng Việt, bài toán trích chọn thông tin với bài toán con là trích chọn metadata. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 16 CHƯƠNG 2.
CÁC KỸ THUẬT XỬ LÝ NGÔN NGỮ TRONG SỐ HÓA VĂN BẢN Bài toán số hóa văn bản tiếng Việt là bài toán lớn, vì vậy trong phạm vi luận văn tập trung vào một số kỹ thuật nhận dạng OCR, kỹ thuật soát lỗi chính tả tiếng Việt dựa trên mô hình ngôn ngữ n-gram, kỹ thuật trích rút metadata tập trung vào nghiên cứu các đặc trưng lưu trữ để xây dựng metadata cho văn bản được số hóa. Một số kỹ thuật nhận dạng OCR 2. Giới thiệu Nhận dạng ký tự quang học (Optical Character Recognition – OCR) là loại phần mềm máy tính có chức năng chuyển các hình ảnh của chữ viết tay hoặc chữ đánh máy (thường được quét bằng máy scanner, chụp ảnh) thành các văn bản tài liệu. Giả sử ta có một văn bản tài liệu bản cứng, sau khi quét bằng máy scanner thành file ảnh, phần mềm OCR sẽ nhận dạng file ảnh đã quét đó thành file văn bản lưu trữ trên máy tính có thể chỉnh sửa được trên máy tính.
Lịch sử của OCR đã có từ hơn nửa thế kỷ, nó xuất hiện đầu tiên để giải quyết bài toán đọc mã số trong bưu điện, tiếp đó phát triển để tự động đọc các địa chỉ và đọc các thông tin trong các mẫu đơn, văn bản. Ngày nay với sự phát triển mạnh mẽ, OCR trở nên phổ biến và thường được ứng dụng như một phần mềm cài đặt trên máy tính hoặc tích hợp kèm với phần cứng như tích hợp trong máy scan. Hiện nay trên thế giới cũng như ở Việt Nam đã có những sản phẩm nhận dạng chữ in có giá trị thực tế cao, có thể kể đến như: sản phẩm ABBYY FineReader (hiện nay là phiên bản FineReader 12) có thể nhận dạng được 190 ngôn ngữ trên thế giới [19]; sản phẩm OmniPage của Nuance nhận dạng được trên 119 ngôn ngữ khác nhau [21]; sản phẩm VnDOCR nhận dạng chữ Việt in của Viện Công nghệ thông tin-Viện Khoa học và Công nghệ Việt Nam; sản phẩm VietOCR nhận dạng chữ in tiếng Việt là chương trình mã nguồn mở do người Việt phát triển sử dụng bộ nhận dạng Tessecract,. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 17 Mô hình tổng quát của một hệ nhận dạng chữ [26] như hình 2.1 Ảnh quét Tiền xử lý Phân đoạn Trích chọn đặc trưng Văn bản đã nhận dạng Hậu xử lý Phân lớp Hình 2.
Sơ đồ tổng quát của một hệ thống nhận dạng OCR Các tài liệu giấy (chữ in hoặc chữ viết tay) được chuyển thành các file ảnh bằng máy quét. Các ảnh quét đó là đầu vào cho quá trình nhận dạng OCR. Tiếp theo là bước tiền xử lý ảnh quét, bước tiền xử lý thực hiện một số chức năng như: nhị phân hóa ảnh, lọc nhiễu, chuẩn hóa kích thước ảnh, làm trơn biên chữ, làm đầy chữ, điều chỉnh độ nghiêng văn bản. Bước phân đoạn thực hiện việc việc tách từng ký tự ra khỏi ảnh văn bản như tách dòng, tách từ, tách kí tự.
Với mỗi ảnh ký tự, khâu trích chọn đặc trưng phân tích ảnh ký tự tìm ra đặc trưng riêng của ký tự đó. Các đặc trưng đã được lựa chọn trong bước trích chọn đặc trưng được sử dụng cho việc huấn luyện và nhận dạng ở bước tiếp theo. Đầu ra của quá trình nhận dạng có thể bị lỗi, bước hậu xử lý sẽ thực hiện việc ghép nối các kí tự đã nhận dạng thành các từ, các câu, các đoạn văn để tái hiện lại văn bản, đồng thời sửa lỗi đảm bảo kết quả nhận dạng tốt nhất. Tất cả các bước thực hiện trên đều quan trọng, nhưng bước quan trọng nhất quyết định độ chính xác của nhận dạng là trích chọn đặc trưng và phân lớp.
Thuật toán phân lớp là yếu tố có vai trò quyết định đến chất lượng của một hệ thống nhận dạng. Các phương pháp nhận dạng truyền thống như đối sánh mẫu, nhận dạng cấu trúc đã được ứng dụng khá phổ biến trong các hệ thống nhận dạng và cũng đã thu được những thành công nhất định. Tuy vậy, với những trường hợp văn bản đầu vào có chất lượng không tốt (nhiễu, đứt nét, dính nét.) thì các thuật toán này tỏ ra không hiệu quả. Để khắc phục điều này, trong những năm gần đây nhiều nhóm nghiên cứu đã sử dụng các thuật toán phân lớp dựa trên mô hình LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 18 SVM [12] , mô hình Markov ẩn HMM [11], mô hình mạng nơron ANN [13] cho các bài toán nhận dạng nói chung và nhận dạng chữ nói riêng.
Kỹ thuật nhận dạng dựa trên mô hình máy vectơ hỗ trợ (SVM) Máy vectơ hỗ trợ (Support vector machine – SVM) là một phương pháp phân lớp dựa trên lý thuyết học thống kê, được đề xuất bởi V.Vapnik và các đồng nghiệp của ông [15] vào những năm 1970 ở Nga, và sau đó đã trở nên nổi tiếng và phổ biến vào những năm 1990. SVM là một phương pháp phân lớp tuyến tính với mục đích xác định một siêu phẳng để phân tách hai lớp của dữ liệu, ví dụ lớp các ví dụ có nhãn dương và lớp các ví dụ có nhãn âm. Có thể mô tả một cách đơn giản về bộ phân lớp SVM như sau: cho trước 2 tập dữ liệu học, mỗi tập thuộc về một lớp cho trước, bộ phân lớp SVM sẽ xây dựng mô hình phân lớp dựa trên 2 tập dữ liệu này. Khi có một mẫu mới được đưa vào, bộ phân lớp sẽ đưa ra dự đoán xem mẫu này thuộc lớp nào trong 2 lớp đã định.
Các hàm nhân (kernel functions)-cũng được gọi là các hàm biến đổi, được dùng cho trường hợp phân lớp phi tuyến. Các lớp phân Hình 2. Siêu phẳng tối ưu và biên tách tuyến tính. lề tương ứng, các vectơ hỗ trợ.
Nếu biểu diễn tập D gồm r các ví dụ huấn luyện như sau D={(x1,y1), (x2,y2),. Khi đó SVM xác định một hàm phân tách tuyến tính f(x)=<w.x>+b, trong đó w là vectơ trọng số các thuộc tính, b là một giá trị số thực. Mặt siêu phẳng phân tách các ví dụ huấn luyện lớp dương và các ví dụ huấn luyện lớp âm là <w.x>+b=0 được thể hiện ở hình 2. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.a: Siêu phẳng phân tách 2 lớp Hình 2.b: Siêu phẳng phân tách (Liu, 2006) có lề cực đại (Liu, 2006) Tuy nhiên trên thực tế có thể tìm được vô số những mặt siêu phẳng phân tách trên cùng một tập dữ liệu thì khi đó ta chọn mặt siêu phẳng phân tách có lề cực đại (Hình 2.
Quá trình học SVM nhằm cực đại hóa mức lề.b, giả sử rằng tập các ví dụ huấn luyện có thể phân tách được một cách tuyến tính. Xét một ví dụ của lớp dương (x+,1) và một ví dụ của lớp âm (x-,1) gần nhất đối với siêu phẳng phân tách H0 (<w. Mức lề (margin) là khoảng cách giữa 2 siêu phẳng lề H+ (<w.x>+b=- 1) trong đó H+ đi qua x+ và song song với H0, H- đi qua x- và song song với H0, d+ là khoảng cách giữa H+ và H0; d- là khoảng cách giữa H- và H0, thì (d+ + d-) chính là lề (margin). Theo lý thuyết đại số vectơ, khoảng cách từ một điểm xi w .xi + b đến mặt siêu phẳng <w.x>+b=0 là (1) w Trong đó ||w|| là độ dài của w : w 12 + w 22 +.
+ w 2n Áp dụng biểu thức (1) tính d+ là khoảng cách từ x+ đến <w.x - + b -1 1 Tương tự: d- = = = w w w Như vậy, tính toán mức lề = d+ + d- = 1 1 2 + = w w w LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 20 SVM học một phân lớp nhằm cực đại hóa mức lề tương đương với việc 2 giải quyết bài toán tối ưu bậc 2 sau: Tìm w và b sao cho margin = đạt cực w đại với điều kiện: ì < w.xi > + b ³ 1 , nếu yi=1 ; với mọi ví dụ huấn luyện xi (i=1.xi > + b £ -1 , nếu yi=-1 SVM có một nền tảng lý thuyết chặt chẽ, dựa trên nhiều định lý toán học, nó là một phương pháp phù hợp đối với những bài toán phân lớp có không gian biểu diễn thuộc tính lớn – các đối tượng cần phân lớp được biểu diễn bởi một tập rất lớn các thuộc tính. SVM được biết đến là một trong số các phương pháp phân lớp tốt nhất đối với bài toán phân lớp văn bản. SVM cơ bản dùng cho hai lớp. Để có thể dùng cho nhiều lớp thì ta phải kết hợp nhiều bộ phân loại hai lớp hoặc xây dựng SVM cho nhiều lớp.
Cách tiếp cận để giải bài toán phân loại k lớp SVM là one-versus – the –rest (OVR) dùng k bộ nhận dạng và cách tiếp cận one-versus-one (OVO) dùng k(k-1)/2 bộ SVM [22]. Mặc dù SVM được đánh giá là một hướng tiếp cận phân lớp đạt độ chính xác cao nhưng có hạn chế là với số lớp nhận dạng quá lớn đòi hỏi bộ nhớ lớn và thời gian huấn luyện rất lớn. Kỹ thuật nhận dạng dựa trên mô hình Markov ẩn (HMM) Mô hình Markov ẩn (Hiden Markov Model - HMM) được giới thiệu vào cuối những năm 1960 và là một trong những mô hình học máy quan trọng nhất ứng dụng trong xử lý ngôn ngữ tự nhiên và nhận dạng. Mô hình này là trường hợp mở rộng của máy hữu hạn trạng thái có hướng, có trọng số.
HMM thường được dùng để xử lý những sự kiện không quan sát trực tiếp được (sự kiện ẩn). HMM là một mô hình xác suất hữu hạn trạng thái theo kiểu phát sinh tiến trình bằng cách định nghĩa xác suất liên kết trên các chuỗi quan sát. Mỗi chuỗi quan sát được sinh ra bởi một chuỗi các phép chuyển trạng thái, bắt đầu từ trạng thái khởi đầu cho đến khi thu được trạng thái kết thúc. Tại mỗi trạng thái thì một phần tử của chuỗi quan sát được phát sinh ngẫu nhiên trước khi chuyển sang trạng thái tiếp theo.