Trong phạm vi bài viết này, chóng t«i chỉ đề cập đến việc ứng dụng phương pháp thống kê toán học để giải quyết bài toán nhận dạng các ngôn ngữ tự nhiên. Ý tưởng của phương pháp là, để nhận dạng được một ngôn ngữ tự nhiên thì trước hết cần phải toán học hoá ngôn ngữ đó như là một xích Markov hữu hạn trạng thái, sau đó dựa vào các tiêu chuẩn thống kê toán học víi các đặc trưng của nó để phân lớp.
Bài toán được đặt ra một cách tổng quát như sau:
Giả sử ta có một tập hữu hạn X = {x1, x2, …, xn} các đối tượng, mỗi đối tượng xi được đặc trưng bởi m tham số nào đó (như vậy ta hoàn toàn có thể coi X là một tập con, hữu hạn trong không gian ¬c¬lit m chiều Rm). Vấn đề đặt ra là: Hãy chia tập X thành K tập con rời nhau G1, G2, …, GK (với K ³ 2) ; sao cho:
- Gi ¹ Æ, " i =1, 2, …, K
- Gi Ç Gj = Æ; với i ¹ j và 1 £i, j £ K
3.
với độ chính xác cao nhất có thể được.
Bài toán này có ý nghĩa thực tiễn quan trọng trong nhiều lĩnh vực KHKT, Tin học, Kinh tế Xã hội và đặc biệt là trong An ninh quốc phòng, như: phân biệt giọng nói của một đối tượng hình sự nào đó với giọng nói của người khác; hoặc phân biệt các ngôn ngữ tự nhiên thuộc một lớp các ngôn ngữ nào đó trong an ninh thông tin khi kiểm soát tự động thư tín điện tử trên Internet,…Chính vì vậy, bài toán này đã được rất nhiều nhà khoa học quan tâm nghiên cứu.
Trong thực hành, tập X tuy là hữu hạn, nhưng có thể rất lớn (có thể có hàng triệu, hàng chục triệu đối tượng). Vì vậy, trong nhiều ứng dụng thực tiễn, cần tạo ra một thuật toán phân loại, không những phải đảm bảo độ chính xác cao, mà còn phải tính đến thời gian tính toán, xử lý để đưa ra các quyết định càng nhanh càng tốt.
Việc giải quyết bài toán nhận dạng các ngôn ngữ tự nhiên gặp phải những khó khăn đáng lưu ý sau:
- Giả sử chúng ta muốn phân biệt hai mẫu văn bản: một văn bản tiếng Anh và một văn bản tiếng Pháp chẳng hạn. Nếu bằng mắt thường và độ dài hai mẫu là khá lớn thì việc phân biệt không khó khăn lắm (tốc độ chậm), nhưng nếu độ dài của mẫu là ngắn và lại nhận dạng tự động thì đây là lại là một vấn đề khó khăn.
- Bản rõ của một ngôn ngữ mà ta cần phân biệt thường có độ dài ngắn và nhiều lúc mất lỗ chỗ hoặc trong đó có đoạn được viết tắt, như “Infomatic Technology” được viết là IT,…
- Các ngôn ngữ thường có những từ, cụm từ vay mượn của nhau, do đó nếu độ dài của mẫu kiểm tra mà quá ngắn thì việc phân lớp rõ ràng là rất khó khăn.
Bài báo này giới thiệu một thuật toán phân lớp các ngôn ngữ tự nhiên một cách đơn giản, tự động khá nhanh với sai số không quá 5% và do vậy, nó có thể đảm bảo được yêu cầu trong ứng dụng thực tiễn.
Nội dung của thuật toán, là:
Ta kí hiệu các đặc trưng của mỗi xi Î X (với i = 1,2,…,n) là , (với l =1,2,…,m). Nếu đối tượng xj Î X nào đó mà có các đặc trưng thì ta đưa nó vào tập Gi.
Có hai loại sai lầm khi thực hiện phân lớp các đối tượng của X, là:
- Sai lầm thứ nhất: §áng lẽ xl Î Gi thì ta lại đưa nó vào Gj với i ¹ j.
- Sai lầm thứ hai: §áng lẽ xl Ï Gi thì ta lại đưa nó vào Gi.
Ta sẽ xây dựng thuật toán sao cho về trung bình cả 2 sai lầm trên là chấp nhận được trong thực tế (sai lầm chấp nhận được là khoảng 0,02).
Và có hai trường hợp xẩy ra là:
- Trường hợp 1: Số tập K là biết trước.
- Trường hợp 2: Số tập K là chưa biết.
Bài báo này sẽ đưa ra thuật toán giải bài toán ở trường hợp 1 (biết trước K), cụ thể ta giả thiết là X là tập chỉ gồm các văn bản mẫu tiếng Anh và tiếng Pháp, có cùng độ dài m; với m ³ 50 kí tự. (trường hợp 2 – chưa biết số tập K sẽ được trình bày ở số báo tiếp theo).
Một số khái niệm cơ bản.
Mô hình Markov.
Ta coi xích Markov hữu hạn trạng thái là một bộ 4 thành phần (m, A, {Yt}, r), trong đó:
m Î Z+ là số các trạng thái của xích.
A = {a1, a2, …, am} là không gian các trạng thái (cụ thể, trong bài toán ta luôn coi các trạng thái này ứng với các chữ cái trong bảng chữ cái của ngôn ngữ cần phân loại).
Yt là biến ngẫu nhiên nhận các giá trị trong tập A, với t Î Z+, nó dùng để mô tả trạng thái của xích tại thời điểm thứ t.
Tham số r Î Z+ là cấp của xích; tức r là số cực đại các trạng thái trước đó mà biến ngẫu nhiên Yt phụ thuộc theo nghĩa xác suất.
Với mọi t ³ 2, phân bố xác suất của biến ngẫu nhiên Yt,với điều kiện Yt-1 cho trước, được xác định bởi các xác suất chuyển trạng thái. Đối với một xích Markov hữu hạn trạng thái cấp 1 (r=1) bất kỳ, thì các xác suất chuyển trạng thái được mô tả bởi ma trận P = (Pr(s/t)), với 0 £s, t £m-1, hoặc bằng ký hiệu thông thường:
(1).
Ps,t chính là xác suất chuyển trạng thái (hay xác suất hậu nghiệm) từ trạng thái thứ s sang trạng thái thứ t của xích. Ngoài ra một mô hình Markov đầy đủ còn có một phân bố tiên nghiệm của các trạng thái của xích. Người ta đã chứng minh được mô hình Markov đối với hầu hết các ngôn ngữ tự nhiên đều là Egordic (dừng, không hậu quả và phi chu kỳ).
Để xây dựng mô hình xích Markov của một ngôn ngữ cơ sở nào đó, ta cần chọn không gian các trạng thái (A), cấp của xích (r) và các xác suất chuyển trạng thái Ps,t với 0 £s, t £m-1. Trong phạm vi bài toán này, ta chọn:
Không gian các trạng thái A º Z26 = {a, b, c, …, x, y,z};
Việc chọn cấp của nguồn là một vấn đề quan trọng - cấp r càng lớn thì độ chính xác của mô hình càng cao, tuy nhiên, cấp càng cao thì việc tính toán càng phức tạp. Vấn đề cấp r được chọn bằng bao nhiêu để đạt độ chính xác đảm bảo yêu cầu mà việc tính toán lại có thể thực hiện trong thời gian chấp nhận được. Trên quan điểm đó, ta chọn r = 1; khi đó ma trận chuyển P sẽ là ma trận vuông cấp 26 x 26.
Việc ước lượng các xác suất chuyển trạng thái Ps,t được thực hiện bằng phương pháp hợp lý cực đại. Tuy nhiên, nếu sử dụng phương pháp hợp lý cực đại thông thường thì chúng ta sẽ thu được các ma trận chuyển của nhiều ngôn ngữ khác nhau lại gần bằng nhau, do đó sẽ gây khó khăn cho việc phân lớp. (ví dụ giữa tiếng Anh và tiếng Pháp). Vì vậy, chúng ta sẽ phải dùng một phương pháp đặc biệt.
Định nghĩa 1: Một bản tin X = (x0x1…xn-1) được thể hiện bằng bảng chữ cái Zm được gọi là rõ nếu nó có thể đọc được theo cú pháp của ngôn ngữ đó.
Ví dụ: Trong ngôn ngữ tiếng Anh, thì X = (abcde) là một bản tin, nhưng bản tin này không đọc được theo cú pháp tiếng Anh; còn X = (Vietnamese people) thì đây là một bản tin rõ.
Định nghĩa 2: Một bản tin rõ X = (x0x1…xn-1) được gọi là được sinh ra bởi n chữ cái theo xích Markov với ma trận chuyển và vectơ cố định f = (f(0), f(1), …, f(25)) nếu phân bố xác suất của X là:
P(x) = P(x0, x1, …, xn-1) = f(x0) P(x1/x0) P(x2/x1) …P(xn-1/xn-2).
Và vectơ f thoả các điều kiện sau:
1. P(s/t) ³ 0; " t Î Z26 0 £s, t £25
2. ứng với mỗi t Î Z26 nào đó, thoả f(t) > 0
3. f(t) ³ 0; " t Î Z26
4.
5. ; " s Î Z26
Vectơ f là nghiệm của hệ phương trình tuyến tính f = P.f (2); với P được cho ở (1).
Nếu P cho trước ứng với một lớp các ngôn ngữ Latin nào đó, thì người ta đã chứng minh được rằng, có tồn tại duy nhất nghiệm f của (2). Tuy nhiên, trong thực tế, ma trận chuyển P cấp 26 x 26 là chưa biết mà ta phải ước lượng. Kí hiệu P1 và P2 là hai ma trận chuyển của ngôn ngữ tiếng Anh và tiếng Pháp tương ứng, trong phép ước lượng này, ta lấy tần số thay cho tần suất:
Thuật toán:
Trên cơ sở tính toán trên, ta có thuật toán như sau:
Giả sử có một mẫu với i = 1, 2, 3,…; n ³ 50 là các văn bản rõ nào đó trong lớp ngôn ngữ tiếng Anh và tiếng Pháp. Hãy phân các mẫu văn bản trên vào hai tập G1 và G2 chỉ chứa tiếng Anh hoặc tiếng Pháp tương ứng?
- Với mỗi i = 1, 2, 3, ..; thực hiện:
- Tính tần số bộ đôi móc xích của mẫu xi, kí hiệu là
- Lập tổng , với Pl (l=1, 2) là ma trận chuyển trạng thái tương ứng của tiếng Anh và tiếng Pháp; là ma trận chuyển vị của ma trận Pl.
- Tính m = Max(Sl[i]); l=1,2. Nếu m = S1[i] thì mẫu xi là văn bản tiếng Anh; ngược lại nếu m = S2[i] thì xi là văn bản tiếng Pháp.
- Return(G1 và G2); là tập các mẫu văn bản tiếng Anh và tiếng Pháp tương ứng đã được phân loại từ các mẫu đã cho.
Một số kết quả:
Thuật toán phân loại được viết bằng Visual Basic 6.0, thực hiện trên máy Pentium 4, tốc độ 3.06 Ghz. Toàn bộ các số liệu để thử được tạo/lấy từ các file text/word có sẵn với độ dài tuỳ ý.
Số mẫu thử
Tiếng Anh
Tiếng Pháp
Tổng số
75 (64 text+11word)
60 (53T + 7W)
15 (11T + 4W
Độ chính xác trong các trường hợp lấy độ dài kiểm tra khác nhau.
Độ dài (K.tự)
Tiếng Anh
Tiếng Pháp
Thời gian
T.số
Đúng
Tỷ lệ
T.số
Đúng
Tỷ lệ
50
60
48
80%
15
14
93%
<1/1000 giây
100
60
51
85%
15
15
100%
<1/1000 giây
150
60
52
87%
15
15
100%
<1/1000 giây
200
60
53
88%
15
15
100%
<1/1000 giây
250
60
56
93%
15
15
100%
<1/1000 giây
300
60
56
93%
15
15
100%
<1/1000 giây
Nhận xét:
- Độ chính xác của thuật toán phụ thuộc vào số kí tự của mẫu được lấy ra để kiểm tra, cụ thể:
Tiếng Anh: Độ chính xác chấp nhận được với độ dài của mẫu kiểm tra là 250
Tiếng Pháp: Độ chính xác chấp nhận được với độ dài của mẫu kiểm tra là 50
- Khi tăng độ dài lấy mẫu kiểm tra (>250 kí tự) thì thấy độ chính xác tăng không đáng kể.
=> Vì vậy trong thực hành, ta có thể lấy độ dài mẫu kiểm tra khoảng 250 kí tự là đủ, trường hợp lấy nhiều hơn chỉ làm tăng thời gian tính toán.
Một số thuật ngữ (Glossaries).
1. Mathematic recognition: Nhận dạng toán học2. Frequency of language biagrams without regard to word boundaries: Biểu đồ tần số bộ đôi của ngôn ngữ không tính tới biên của từ.
3. Word boundaries: Giãn cách từ.
4. Pattern recognition: Nhận dạng (Phân lớp)
5. Finite Markov chain: Xích Markov hữu hạn
6. Parametric estimation: Ước lượng tham số
7. Non-parametric estimation: Ước lượng phi tham số.
8. Theoretical frequency of a language biagrams: Tần số lý thuyết về bộ đôi của ngôn ngữ.
9. Simple frequency of language: Tần số ngôn ngữ ví dụ.
10. Candidate: Mẫu
11. Plaintext: Văn bản rõ- Ciphertext: Văn bản mã
- Candidate Plaintext: Văn bản mẫu để kiểm tra
- Classification: Phân lớp
- Measurement: Độ đo
- Posterior Probability: Xác suất tiên nghiệm
- Initial Distribution: Phân bố tiên nghiệm
